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

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

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

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