著色算法解決數據聚集網絡中多信道時隙調度問題.pdf

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

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

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