著色算法解決數(shù)據(jù)聚集網(wǎng)絡(luò)中多信道時(shí)隙調(diào)度問(wèn)題.pdf

1、近年來(lái)，數(shù)據(jù)聚集網(wǎng)絡(luò)作為一種新興的、極具發(fā)展?jié)摿Φ木W(wǎng)絡(luò)技術(shù)，逐漸在國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域得到了越來(lái)越廣泛的應(yīng)用，為人們的生產(chǎn)生活提供了諸多便利。在多信道數(shù)據(jù)聚集網(wǎng)絡(luò)中，如何進(jìn)行信道和時(shí)隙的調(diào)度，從而最小化網(wǎng)絡(luò)通信沖突，最優(yōu)化網(wǎng)絡(luò)內(nèi)數(shù)據(jù)聚集性能是一個(gè)關(guān)鍵問(wèn)題。本文針對(duì)這一問(wèn)題進(jìn)行研究，提出了一種基于吉布斯采樣的多信道TDMA調(diào)度算法，并通過(guò)不同網(wǎng)絡(luò)參數(shù)下的大量仿真實(shí)驗(yàn)證明了該算法的有效性。
　　本文研究的主要內(nèi)容及主要?jiǎng)?chuàng)新之處在于:

2、r>　　(1)基于著色圖理論對(duì)數(shù)據(jù)聚集網(wǎng)絡(luò)中的多信道TDMA調(diào)度問(wèn)題進(jìn)行了建模。采用基于路由樹(shù)構(gòu)建的干擾圖來(lái)表示網(wǎng)絡(luò)中通信鏈路之間的調(diào)度干擾關(guān)系，干擾圖中的節(jié)點(diǎn)之間的著色關(guān)系與實(shí)際通信鏈路之間的通信沖突關(guān)系一一對(duì)應(yīng)。在此基礎(chǔ)上定義了節(jié)點(diǎn)的干擾域、干擾度和通信沖突等概念，以最小化網(wǎng)絡(luò)通信沖突為優(yōu)化目標(biāo)，公式化描述了數(shù)據(jù)聚集網(wǎng)絡(luò)中多信道TDMA調(diào)度問(wèn)題。
　　(2)提出了一種退火吉布斯采樣的圖頂點(diǎn)著色算法，用以解決上述問(wèn)題。本文證明了

3、上述頂點(diǎn)著色問(wèn)題是馬爾科夫隨機(jī)場(chǎng)問(wèn)題，符合吉布斯采樣理論應(yīng)用的充要條件。在此基礎(chǔ)上根據(jù)優(yōu)化目標(biāo)定義了吉布斯勢(shì)函數(shù)和吉布斯能量函數(shù)，由此構(gòu)造了目標(biāo)概率分布函數(shù)，同時(shí)引入退火策略，提出了退火吉布斯采樣圖頂點(diǎn)著色算法(Gibbs Sampler based Node Coloring Algorithm，GSNC)。大量仿真實(shí)驗(yàn)結(jié)果表明該算法可以解決數(shù)據(jù)聚集網(wǎng)絡(luò)中多信道TDMA調(diào)度問(wèn)題，并達(dá)到最小化網(wǎng)絡(luò)通信沖突，最小化調(diào)度長(zhǎng)度的目標(biāo)。