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

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

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

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

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

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

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

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

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

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

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