多接口多信道無線Mesh網(wǎng)絡(luò)信道分配關(guān)鍵技術(shù)研究.pdf

1、無線Mesh網(wǎng)作為高速率、高容量、移動性良好的新一代無線網(wǎng)絡(luò)，正以其特殊的軍事應(yīng)用價值和廣泛的商業(yè)應(yīng)用前景而引人矚目。但要將其巨大的潛能變成現(xiàn)實，還必須解決很多極具挑戰(zhàn)性的問題。
　　隨著人們對無線網(wǎng)絡(luò)需求的不斷激增，以及寬帶流媒體服務(wù)的日趨廣泛，有限的網(wǎng)絡(luò)容量問題成為當(dāng)前無線Mesh網(wǎng)絡(luò)應(yīng)用的瓶頸。多信道分配技術(shù)通過為網(wǎng)絡(luò)節(jié)點合理分配可用信道資源的方式，降低通信鏈路干擾，能夠從本質(zhì)上優(yōu)化網(wǎng)絡(luò)性能，提高網(wǎng)絡(luò)容量，從而成為無線Mes

2、h網(wǎng)絡(luò)研究的關(guān)鍵問題。已有研究表明，單接口多信道（SR-MC）分配是一個NP問題，而多接口多信道（MR-MC）分配相對SR-MC問題則更為復(fù)雜?，F(xiàn)有大多數(shù)無線協(xié)議是基于單接口的網(wǎng)絡(luò)結(jié)構(gòu)，然而無線Mesh網(wǎng)絡(luò)的研究和設(shè)計中多接口多信道已經(jīng)成為一種趨勢。相比單接口無線Mesh網(wǎng)絡(luò)，多接口多信道的無線Mesh網(wǎng)絡(luò)為節(jié)點的互聯(lián)提供了更多的通信接口和信道選擇，可以顯著增強Mesh網(wǎng)絡(luò)的連通效率，大幅提升Mesh網(wǎng)絡(luò)的服務(wù)性能。但多接口多信道環(huán)境下

3、的信道分配技術(shù)面臨著在傳統(tǒng)無線網(wǎng)絡(luò)中不會出現(xiàn)的一些新挑戰(zhàn)，比如隱終端問題，信道漣漪問題，連通性問題以及廣播問題等。
　　針對無線 Mesh網(wǎng)絡(luò)的諸多特點和現(xiàn)有研究中的不足，本文從信道分配策略、信道分配與網(wǎng)絡(luò)拓?fù)?、信道分配與廣播通信等多個角度對多信道多接口信道分配技術(shù)中涵蓋的多個層面展開深入研究，圍繞網(wǎng)絡(luò)性能優(yōu)化的關(guān)鍵問題提出相應(yīng)的解決方案。主要研究工作與創(chuàng)新性貢獻有：
　　針對高速Mesh網(wǎng)絡(luò)骨干網(wǎng)，設(shè)計了一種新的混合信道分

4、配機制——HCAM。
　　無線網(wǎng)現(xiàn)有信道分配方案中的集中式和分布式這兩種主流分配方式各存缺憾。本文提出一種混合信道分配機制 HCAM，將集中式和分布式兩種信道分配模式有機結(jié)合，構(gòu)建了信道預(yù)分配和優(yōu)化信道分配兩個子模塊，分階段予以實施。在信道預(yù)分配模塊中設(shè)計了一個集中式信道分配方式，使得節(jié)點相對于網(wǎng)關(guān)節(jié)點的潛在跳數(shù)最小，能夠快速構(gòu)建網(wǎng)絡(luò)拓?fù)洳⑶覍崿F(xiàn)骨干網(wǎng)絡(luò)的連通性，這對于滿足多媒體數(shù)據(jù)流的時延需求極為重要。而在優(yōu)化信道分配模塊中設(shè)計

5、了一個新的動態(tài)分布式信道分配算法，充分利用可用信道和接口資源，最小化信道干擾，從而最大限度保障相鄰鏈路可同時傳輸數(shù)據(jù)，有效提高無線Mesh網(wǎng)的網(wǎng)絡(luò)容量。HCAM機制的創(chuàng)新之處還在于提出兩個新的干擾評估因子，使得Mesh節(jié)點可根據(jù)本地獲取的相關(guān)信息計算干擾評估值，從而實現(xiàn)高效的信道分配。此外，HCAM機制還引入了次級鏈路這個概念，當(dāng)一個節(jié)點的父節(jié)點失效后，該節(jié)點可以迅速啟用次級鏈路尋找新的父節(jié)點，同已有算法相比，這種方式無需重新掃描鄰居節(jié)

6、點，能在更短時間內(nèi)響應(yīng)網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化，維護網(wǎng)絡(luò)節(jié)點的連通性。HCAM機制不依賴于特定的無線MAC協(xié)議和路由協(xié)議，能保證網(wǎng)絡(luò)連通性和避免信道漣漪問題。仿真實驗表明，HCAM機制在不同的網(wǎng)絡(luò)規(guī)模以及 Mesh節(jié)點可用信道數(shù)和配置接口數(shù)不同的網(wǎng)絡(luò)中均能降低通信信道干擾，優(yōu)化網(wǎng)絡(luò)吞吐量。
　　針對傳統(tǒng)著色模型應(yīng)用于多接口多信道無線 Mesh網(wǎng)絡(luò)信道分配中存在的局限性，從圖論建模的角度設(shè)計了新的基于強邊著色理論的信道分配解決方案。

7、>　　首先指出了T-著色模型及其特例 L(2,1)著色模型在多接口多信道復(fù)雜環(huán)境下存在信道干擾，而強邊著色模型在避免信道干擾方面具有明顯的優(yōu)勢。通過對一些特例如亞三度圖、平面圖特別是 K-退化圖的強邊著色特性的研究和分析，得到了k-退化圖強邊著色數(shù)的一個強化結(jié)論。按照這個結(jié)論，作為1-退化圖的樹的強邊著色數(shù)為2??1。這樣，只需找出無向圖的一個限制度數(shù)為?的生成樹，再按照研究給出的K-退化圖強邊著色邊排序和著色算法就可以完成強邊著色也就

8、是無線信道分配。在分析研究時間復(fù)雜度為O(|V(G)|2)的限制度數(shù)的生成樹算法存在理論缺陷的基礎(chǔ)上，給出時間復(fù)雜度為O(|V(G)|2log(|V(G)|))的基于蟻群算法的限制度數(shù)最小生成樹算法，該算法可完成從無向圖構(gòu)造限制度數(shù)的生成樹即1-退化圖這一關(guān)鍵步驟，從而實現(xiàn)對多接口多信道無線Mesh網(wǎng)絡(luò)信道分配問題的圖論解決方案。需要指出的是，該方案具備較好的推廣性，任何能夠在無向圖中構(gòu)造其它平面圖特例的算法，只要能達到強邊著色結(jié)論的要

9、求，都可以用來實現(xiàn)多接口多信道無線Mesh節(jié)點之間的信道分配。仿真實驗結(jié)果表明，隨著測試集中節(jié)點數(shù)目的遞增，相比其他研究的最優(yōu)結(jié)果，基于蟻群算法的限制度數(shù)最小生成樹算法對于較為隨機的測試圖得到的限制度數(shù)最小生成樹的成本更低，結(jié)果更為優(yōu)化。
　　針對廣播通信方式，設(shè)計了一種基于分枝定界的優(yōu)化廣播樹生成算法，并提出了一種新的基于該優(yōu)化廣播樹的廣播信道分配機制——B3TCAM。
　　現(xiàn)有基于層次信道分配算法Level-CA等方法存

10、在廣播冗余、信道干擾、轉(zhuǎn)播節(jié)點的選取無法達到最優(yōu)覆蓋等局限性。針對這個問題，本文提出了B3TCAM信道分配機制。B3TCAM沒有采用最常見的基于網(wǎng)絡(luò)分層選取轉(zhuǎn)播節(jié)點的方法，而是提出了一種采用分枝定界的優(yōu)化廣播樹生成算法來構(gòu)建由轉(zhuǎn)播節(jié)點組成的連通支配集。通過分枝、剪枝策略實現(xiàn)了轉(zhuǎn)播節(jié)點選取的優(yōu)化，進而達到了最優(yōu)覆蓋，并在優(yōu)化剪枝的同時進行廣播信道分配，一方面減少了不必要的廣播冗余，另外也規(guī)避了冗余轉(zhuǎn)播節(jié)點可能帶來的潛在信道干擾。仿真實驗表