無線網(wǎng)狀網(wǎng)中的防干擾頻道分配

1、無線網(wǎng)狀網(wǎng)中的防干擾頻道分配Krishna N. Ramachandran, Elizabeth M. Belding,Kevin C. Almeroth, Milind M. Buddhikot摘要通過安裝無線網(wǎng)路由器使多頻信號變?yōu)闊o同頻信號來達到緩和無線網(wǎng)狀網(wǎng)中的容量問題。 然而，頻道分配變?yōu)榱颂魬?zhàn)因為無線網(wǎng)多了會導(dǎo)致同頻干擾。 其結(jié)果相反會增加干擾影響性能。本文就多信道無線網(wǎng)狀網(wǎng)絡(luò)的干擾問題通過防干擾頻道分配的方法提出了解決辦法和方案。該解決方案通過合理的分配無線頻道最大程度地減小了無線網(wǎng)之間的干擾。該方案利用了新的干擾估計技術(shù)手段并且付諸實施于無線中的每個路由器。 通過沖突圖模型及多信

2、道沖突圖的拓展來構(gòu)造路由器之間的干擾模型。我們通過 IEEE802.11 協(xié)議實驗平臺來驗證方案的可行性。 我們同時報告了大量實驗?zāi)M仿真的效果。 在多頻取樣上，我們解決方案對比于靜態(tài)頻道分配增加了百分之四十的取樣。第一章 .引言典型的靜態(tài)多跳無線網(wǎng)絡(luò)， 又稱無線網(wǎng)狀網(wǎng)絡(luò)， 其部署的路由器僅利用了 IEEE802.11 協(xié)議無線電廣播。 IEEE802.11 無線廣播是典型的單頻道廣播。因此，由于無線網(wǎng)的半雙工特性，單信道網(wǎng)狀無線網(wǎng)絡(luò)通信的容量受到嚴重地衰減。幸運的是，IEEE802.11 物理層協(xié)議允許多個不重復(fù)頻段的頻道同時運行工作。例如， 2.4 兆赫茲帶寬的頻帶內(nèi)的 3 個不重復(fù)頻段的

3、頻道能夠同時工作。 IEEE802.11a 協(xié)議最高允許 5.0 兆赫茲帶寬的頻帶內(nèi)劃分為 12 個不重復(fù)頻段的頻道。通過在無線網(wǎng)中布置頻率路由器和為不重復(fù)頻道分配無線接收機來劃分設(shè)置不同頻段的頻道， 這些路由器可以同時工作并且彼此之間的干擾能夠最小化。 從而，能夠提升無線網(wǎng)狀網(wǎng)的能力。通過多個無線接收機對應(yīng)多個路由器的策略， 使得無線電接收機的數(shù)量與正交頻道的數(shù)量相等。 由于數(shù)量眾多的不同頻段的頻道， 這個策略經(jīng)濟上代價過高。 而且，生產(chǎn)路由器的小型嵌入式系統(tǒng)僅僅能夠提供數(shù)量有限的無線電接收機。 因此，在一個無線網(wǎng)狀路由器上劃分所有的不重復(fù)頻段的頻道仍然是不可行的。這樣，為每個無線網(wǎng)狀路由器

4、劃分頻道的問題變成了按無線電接收機劃分頻道的問題。簡單的技術(shù)是用靜態(tài)頻道劃分法。然而，靜態(tài)劃分對于基于 IEEE802.11b 標(biāo)準(zhǔn)的無線局域網(wǎng)會產(chǎn)生爆炸性的結(jié)果，可能導(dǎo)致網(wǎng)狀網(wǎng)頻道被重復(fù)劃分。本文提及了頻道劃分的問題以及特別研究了無線網(wǎng)狀網(wǎng)頻道的動態(tài)劃分。我們主要闡述了抗干擾頻道劃分算法和以及劃分頻道的方案，旨在改進無線網(wǎng)狀網(wǎng)的容量來更有效的利用不重復(fù)頻段的頻道。 這個算法合理地為網(wǎng)狀無線電接收機選擇頻道從而把無線網(wǎng)狀網(wǎng)中的干擾以及不同無線網(wǎng)狀之間的干擾降低到最小。 每個網(wǎng)狀路由器利用新的干擾估計技術(shù)來檢測鄰近無線網(wǎng)產(chǎn)生的干擾的等級。 這個算法是對沖突圖模型和多頻沖突圖模型的拓展， 從而構(gòu)造

5、無線網(wǎng)狀網(wǎng)中的多頻路由器間干擾的模型。 多頻沖突圖被用來和頻道分配的干擾估計相結(jié)合從而為無線電接收機分配頻道。一個潛在的問題是動態(tài)頻道分配會導(dǎo)致網(wǎng)絡(luò)拓撲結(jié)構(gòu)的改變。 拓撲結(jié)構(gòu)的改變會導(dǎo)致次佳路由選擇以及由于節(jié)點錯誤所引起的網(wǎng)絡(luò)分隔。推薦的解決辦法是授權(quán)每個網(wǎng)狀路由器的無線電接收機在一個默認頻道上工作。另外一個潛在的問題是當(dāng)網(wǎng)狀無線電接收機被重新配置不同頻率時，頻道分配會導(dǎo)致流干擾。為了防止流干擾，每個網(wǎng)狀路由器間必須定向連接。這項技術(shù)重新定向直到頻道分配成功。我們通過網(wǎng)路模擬器來仿真實驗我們擬定解決方案的可行性。我們利用鏈路狀態(tài)路由優(yōu)化方法和加權(quán)累積預(yù)期傳輸來進行路由選擇。我們通過多信道IEE

6、E802.11b 協(xié)議平臺來驗證解決方案的可行性。（一）研究貢獻就我們掌握的知識，我們首先解決了受干擾的多重?zé)o線網(wǎng)中網(wǎng)狀無線網(wǎng)的頻道的靜態(tài)分配。 擬定解決方案的首要目標(biāo)是使用當(dāng)前可用的無線電設(shè)備來實現(xiàn)。 我們的工作與幾個推薦的解決方案不同之處在于需要專業(yè)的不可用的無線電設(shè)備或者網(wǎng)絡(luò)知識。特別地，本文的貢獻有如下幾點:·通過靜態(tài)，防干擾的頻道分配算法將無線網(wǎng)狀網(wǎng)和多重?zé)o線網(wǎng)間的干擾最小化。·利用多信道沖突圖，沖突圖模型的拓展來構(gòu)造無線網(wǎng)狀網(wǎng)中多頻路由器間的干擾模型。·新的干擾估計計劃，用路由器來估計他們鄰近區(qū)域的干擾等級。·定向連接方案防止了頻道分配時的流

7、破壞。·對于不同的干擾等級，通過標(biāo)準(zhǔn)根據(jù)經(jīng)驗主義測量方法來實驗研究展現(xiàn)改進手段。（二）本文概述本文剩余章節(jié)組織如下：第二章討論了頻道分配對網(wǎng)絡(luò)結(jié)構(gòu)的影響。第三章我們明確表述了頻道分配問題。第四章描述了我們的干擾估計技術(shù)和多頻沖突圖模型。第五章詳細講述了頻道分配算法。第二章頻道分配和網(wǎng)絡(luò)拓撲結(jié)構(gòu)在多頻網(wǎng)狀網(wǎng)絡(luò)中，無線電接收機的頻道分配能改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)。圖 1(a)是四節(jié)點拓撲結(jié)構(gòu)，節(jié)點C 配有 3 無線電接收機，其余三個節(jié)點每個各有一個。每個連接線上標(biāo)有其頻道數(shù)量。圖1（a）說明了所有無線電接收機都調(diào)成一個頻道時的拓撲結(jié)構(gòu)。圖 1（b）說明樂頻道分配后的網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化。網(wǎng)絡(luò)拓撲結(jié)

8、構(gòu)的變化有三個主要的缺點。首先，隨之產(chǎn)生的節(jié)點錯誤很可能引起網(wǎng)絡(luò)被隔斷。結(jié)果，網(wǎng)絡(luò)的部分不能通信，導(dǎo)致流破壞（通信中斷）。這個現(xiàn)象在圖 1（c）中可以看到。當(dāng)節(jié)點連接錯誤時，這四個節(jié)點的網(wǎng)絡(luò)被隔離成三個不多的部分。 這個網(wǎng)絡(luò)的重新連接需要復(fù)雜的同步同時性計劃付諸于每個網(wǎng)狀路由器。圖 1其次，拓撲結(jié)構(gòu)的改變能夠?qū)е聝蓚€節(jié)點間次佳的路由選擇，基于度量標(biāo)準(zhǔn)方面，如吞吐率，延遲，可靠性。再次通過圖 1 來說明怎樣發(fā)生這種情況。節(jié)點 A 能通過一條路徑直接和節(jié)點 B 通信。頻道分配后， A 點和 B 點只有通過二次路徑（經(jīng)過 C）才能相互通信，如圖 1（b）。高跳數(shù)的路徑選擇不是我們所期望的有以下三個原

9、因：（ 1）更長的，頻率多樣化的路徑相對于短路徑經(jīng)常會發(fā)生通信錯誤。（ 2）通信流量路徑的路徑數(shù)越多其干擾自然越厲害。 （3）更長的路徑更有可能發(fā)生通信失敗。 需要注釋的是， 我們不能夠肯定更長的路徑會比短路徑差，那是因為路徑的選擇肯定會遇到很多因素如交通路線，節(jié)點分布，無線電特性和地理環(huán)境等。因此，我們在這里強調(diào)：很難在實踐中精確地預(yù)測頻道分配的變化和網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化能否產(chǎn)生適宜的結(jié)果。第三個網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化的缺點是：可能影響當(dāng)前的信息流。例如，讓我們假設(shè)圖 1（b）的 CD 連線被分配一個新的頻道。這個頻道分配必須精確地協(xié)調(diào) ;另外，當(dāng)線路上一個無線電接收機變換到這個新的頻率而第二個無線電

10、接收機由于控制信息的丟失和延遲沒有變換到這個頻率時，會發(fā)生錯誤。因此，當(dāng)頻道分配的時候由節(jié)點 D 到網(wǎng)絡(luò)其余部分的信息流會在變換頻率時被損壞。 在實際中克服這些狀況很難，因為無線電接收機的配置需要在頻道分配期間網(wǎng)狀路由器之間同時合作。因為這些由于網(wǎng)絡(luò)拓撲結(jié)構(gòu)變化產(chǎn)生的缺陷，我們提倡不改變網(wǎng)絡(luò)拓撲結(jié)構(gòu)。我們授權(quán)將所有網(wǎng)狀網(wǎng)中的路由器將他們的無線電接收器的其中一個指定為無線電接入口。 這個指定的無線電接收器有著同樣地物理層技術(shù)，是符合 802.11a協(xié)議或者 802.11b或者 802.11g，通過網(wǎng)狀網(wǎng)調(diào)整為一個普通的頻道。 這個指定的頻道兼顧控制通信及數(shù)據(jù)通信。這個策略有幾個好處。首先，它防止

11、了網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化因為所有路由器可以通過這個指定的無線電接收入口彼此連接和斷開。 其次，它克服節(jié)點的失效變得簡單了由于一個路由器能繞過一個失效的節(jié)點選擇不同的路徑通信。 另外，目前路由協(xié)議除了頻率劃分外有別的選擇權(quán)，如果它比從頻率特性劃分上有更好地效果。 除此之外還有一個優(yōu)勢，信息流通過這個指定的無線電接收機可以重新傳送直到頻道分配完成，這樣，就能防止頻道分配時的信息流損壞。第三章 .問題陳述我們在本文中提及的頻道分配算法是為無線網(wǎng)狀網(wǎng)設(shè)計的。該網(wǎng)絡(luò)中的路由器是固定的。然而，用戶設(shè)備，如筆記本電腦，掌上電腦是移動的。諸如此類和路由器相連接的設(shè)備也同樣起著作為無線接入點的功能。圖 2 多信道無

12、線網(wǎng)狀網(wǎng)絡(luò)結(jié)構(gòu)圖 2 說明我們的多信道網(wǎng)狀網(wǎng)絡(luò)的模型。 在我們的模型中， 網(wǎng)狀路由器被假象配有多個 IEEE802.11 協(xié)議的接收機，如 802.11a或者802.11b或者 802.11g。這些路由器不需要配有同樣數(shù)量的無線接收機而且不要所有三種類型的接收機。 考慮到每個網(wǎng)狀網(wǎng)絡(luò)的接收機的數(shù)量，我們把路由器分為兩類：（1）多信道網(wǎng)狀路由器。（2）單信道網(wǎng)狀路由器。我們授權(quán)每個網(wǎng)絡(luò)中的多信道網(wǎng)狀路由器及單信道網(wǎng)狀路由器配有一臺無線接收機， 稱為默認接收機，它們都有相同的物理層，如 802.11b，并且都被調(diào)整為相同的頻道，如第二章中所詳述的。網(wǎng)絡(luò)中至少有一個路由器被指定為網(wǎng)關(guān)。 這些網(wǎng)關(guān)與外

13、網(wǎng)是可連接的。為了把頻道分配解釋的簡單明白，我們假設(shè)只存在一個網(wǎng)關(guān)。無線接入點提供了用戶設(shè)備和路由器的可連接性。多數(shù)網(wǎng)狀網(wǎng)絡(luò)通信是從用戶端到網(wǎng)關(guān)之間的通信，或者從網(wǎng)關(guān)到用戶端。 這種通信方式是無線網(wǎng)狀網(wǎng)中典型部署。 由于這種通信方式是與網(wǎng)關(guān)斜交的， 由信息流的路徑可能會形成一個樹狀結(jié)構(gòu)， 其中網(wǎng)關(guān)是樹的根， 用戶設(shè)備是葉子。信息流會在網(wǎng)關(guān)鄰近的路由器上聚集。因此，為了改進整個網(wǎng)絡(luò)的通信能力，最好在網(wǎng)關(guān)附近布置多信道網(wǎng)狀路由器從而提升網(wǎng)狀網(wǎng)絡(luò)的區(qū)域的利用率。 為了改善網(wǎng)絡(luò)的性能， 減少儀器的開支以及符合邏輯的約束，周密的網(wǎng)絡(luò)布置很重要。圖中點劃線的地方代表了多信道網(wǎng)狀路由器間調(diào)整為無重疊頻道的部

14、分。在我們的例子中，使用了五個這樣的頻道。第六個頻道用實線標(biāo)注，是默認頻道。與網(wǎng)關(guān)位置重疊的頻道分配服務(wù)器，起著給接收機分配頻道的作用。在分配頻道時，頻道分配服務(wù)器必須達到如下目標(biāo)：·使網(wǎng)狀路由器間的干擾最小化:實現(xiàn)需要三個次目標(biāo)。首先，頻道分配服務(wù)器必須滿足兩個路由器間存在一條線路的約束， 這兩個路由器上的終端接收機必須被分配給一個普通頻道。 其次，直接通信范圍的線路必須被調(diào)整為不重疊頻道。 另外，由于無線網(wǎng)狀網(wǎng)中的樹狀通信圖，頻道分配的優(yōu)先權(quán)應(yīng)該首先給從網(wǎng)關(guān)起始的路線然后給網(wǎng)絡(luò)邊緣的路線。·使無線網(wǎng)狀網(wǎng)之間的干擾最小化：為了達到這個目標(biāo)，頻道分配路由器必須定期檢測網(wǎng)狀網(wǎng)

15、絡(luò)重疊造成的干擾的數(shù)量。 干擾等級由獨立的網(wǎng)狀路由器檢測。 為了使頻道受到來自外部接收機的干擾程度最小，頻道分配路由器必須重置頻道。陳述了信道分配算法的目標(biāo)后， 我們接下來闡述干擾估計的細節(jié)及描述干擾建模技術(shù)。第四章干擾分析及建模本章節(jié)陳述了干擾分析的步驟。補充的細節(jié)部分在第五章中。本章也介紹多信道沖突圖模型。（一）干擾分析干擾分析的目的是定期的檢測每個網(wǎng)狀路由器環(huán)境下干擾等級。然而，精確的測量方法是個挑戰(zhàn)需要昂貴的硬件開支。取而代之的是， 用近似法，我們依靠每個頻道的干擾接收機的數(shù)量作為干擾分析， 這些頻道由路由器支持。 一個干擾接收機被定義為一個同時工作的接收機， 該接收機對路由器是可見的

16、而對網(wǎng)狀網(wǎng)絡(luò)來說是外置的?？梢姷慕邮諜C的數(shù)據(jù)包是按幀檢查序列傳送的因此會被無誤的接收。我們假設(shè)頻道分配路由器與網(wǎng)絡(luò)內(nèi)部的接收機的路由器通信。通信的內(nèi)容由一些列網(wǎng)址和詳盡的網(wǎng)絡(luò)中的介質(zhì)訪問地址組成。分析步驟要注意的一點是： 這些接收機是在一個分析路由器的傳感范圍內(nèi)但是不在接收范圍內(nèi)， 不會算在干擾分析內(nèi)。 這是因為由無線接收機傳送的數(shù)據(jù)包不能通過路由器幀檢查序列的校驗。 然而，傳感接收機仍然會影響干擾到路由器。 我們的干擾分析技術(shù)不考慮接收機有兩個原因。首先，最近研究表明現(xiàn)在的 IEEE802.11 介質(zhì)訪問在傳感原理上實現(xiàn)的過度保守了并且干擾接收器經(jīng)常受到不利的評價。因此，對于多個傳感無線接收

17、機，也許并不像先前所理解的那樣，接收機相鄰就會引起性能不佳。 其次，就算我們真地把傳感器無線接收機容納進我們的干擾分析解決辦法中， 也不可能決定能夠使用這類標(biāo)準(zhǔn)硬件的接收機因為目前軟件無法識別它們。 我們被建議用專門的軟件來克服。這種軟件可能在不久的將來會有并且投入市場。然而，僅有這些數(shù)量的干擾接收機的測量方法不充分因為并不能表明受干擾接收機影響的通信量。 例如，兩個頻道能有同樣數(shù)量的干擾接收機但是其中一個頻道相對于另一個可能被它的干擾接收機嚴重的占用。因此， 另外，每個網(wǎng)狀路由器也可評估被干擾接收機占用的頻道帶寬。干擾評估步驟如下： 一個網(wǎng)狀路由器通過每個支持的物理層規(guī)范設(shè)置一個接收機，從而

18、在每一段持續(xù)的短時間內(nèi)從每個支持的頻道上捕獲數(shù)據(jù)包。路由器利用捕獲的數(shù)據(jù)包來檢測干擾接收機的數(shù)量和每秒頻道利用率。干擾接收機的數(shù)量與網(wǎng)絡(luò)外介質(zhì)訪問控制點的數(shù)量相同。受干擾機的影響的每個頻道的利用率通過計算捕獲的數(shù)據(jù)結(jié)構(gòu)得到，其中包括數(shù)據(jù)包的大小和數(shù)據(jù)包傳輸?shù)乃俣?。頻道利用率的計算應(yīng)該同樣考慮介質(zhì)訪問控制層的系統(tǒng)開銷（在計算機網(wǎng)絡(luò)的幀結(jié)構(gòu)中，除了有用數(shù)據(jù)以外，還有很多控制信息，這些控制信息用來保證通信的完成。這些控制信息被稱作系統(tǒng)開銷。 ）在實施中，我們將數(shù)據(jù)捕獲的持續(xù)時間設(shè)置為三秒。三秒的時間設(shè)置考慮到了每秒測量的平均變化量并且對于干擾分析的快速計算足夠短暫。每個網(wǎng)狀路由器衍生出兩類頻道等級排

19、列。第一類等級排列根據(jù)干擾接收機的增加數(shù)量。另外一類是根據(jù)增加的頻道利用率。路由器然后通過單個級別的平均數(shù)來排列級別最終合并兩類頻道等級排列。最終的劃分結(jié)果被送給頻道分配服務(wù)器。圖 3（ a）一個簡單的網(wǎng)絡(luò)拓撲結(jié)構(gòu)G（ b）沖突圖F（ c）多信道沖突圖F（二）干擾模型沖突圖廣泛地被用來模擬蜂窩無線網(wǎng)絡(luò)的干擾模型。一個網(wǎng)狀網(wǎng)路的沖突圖定義如下：圖 G 具有節(jié)點類似于網(wǎng)絡(luò)中的路由器，節(jié)點間的邊線類似于無線線路。 一個沖突圖 F，有與 G 圖一致的節(jié)點并且節(jié)點間有連線，只要 F 圖中的兩個節(jié)點表示 G 中的線路，并且彼此干擾。作為沖突圖的例子，圖 3（a）展示了具有四個節(jié)點的網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖。圖中的每

20、個節(jié)點標(biāo)有節(jié)點名稱和接收機的數(shù)量。 圖 3（b）展示了這種沖突圖。乍一看，網(wǎng)狀網(wǎng)絡(luò)線路的頻道分配問題變成了沖突圖頂點著色的問題。然而，頂點著色不能直接分配頻道因為它沒有說明解釋其中的限制約束“一個路由器可分配的頻道數(shù)量必須與它的接收機的數(shù)量相同”。舉例來說明情況，我們假設(shè)圖 3（b）沖突圖中的四個頂點根據(jù)頂點著色法來給每個頂點分配三個不同的頻道。 意思是每個頂點的兩個接收機按照頂點的頻率工作。這意味著這個網(wǎng)絡(luò)中的節(jié)點C 在三個不同的頻道上工作，這是不可能的因為它只有兩臺接收機。沖突圖不能夠直接構(gòu)造具有多個無線接收機的路由器的模型。因此，我們擴展沖突圖來構(gòu)造多信道路由器的模型。在這個擴展的模型（

21、多信道沖突圖） 中，我們像原始的沖突圖那樣通過接收機作為頂點而不是路由器作為頂點來描繪頂點間的邊線。為了創(chuàng)建多信道沖突圖F，我們首先在 G 中以每個接收機作為頂點而不是像G 中以路由器代表頂點。因此，在上訴的例子中，節(jié)點C 由 G中的兩個頂點代替而不像 G 中只有一個頂點， G中兩個頂點對應(yīng)著兩個接收機。G圖中的邊線是處于接收機間而G 圖中的邊線是路由器間連接的。 F圖中的頂點代替 G圖中的每條連線。圖F中頂點間的連線的產(chǎn)生如同原始沖突圖那樣。 例如，圖 3（c）展示了圖 3（a）的多信道的干擾圖。在圖中，每個頂點都標(biāo)記著用接收機代替頂點。例如，頂點（ A-1：C-2）代表了路由器 A 的第一

22、臺接收機和路由器 C 的第二臺接收機之間的連接。當(dāng)用頂點著色法給多信道沖突圖著色時，我們利用了一條重要的限制規(guī)定：在給多信道沖突圖中所有頂點著色時，所用未著色的頂點包含了已著色且調(diào)整了位置的頂點的接收機。例如，對圖3（c）中的頂點（ A-1 ：C-2）著色后，沖突圖中所用包含 A-1 或者 C-2 的頂點都應(yīng)該移開。這是為了保證無線網(wǎng)狀網(wǎng)中每個接收機都只有一個頻道。第五章頻道分配算法（一）綜述網(wǎng)狀網(wǎng)絡(luò)的頻道分配問題與列表染色問題相似，列表染色定義如下：已知圖 G=（V,E），對于 V 中的每個 v，一列有色的 L （v），能否構(gòu)造固定的根據(jù) G 染色的頂點染色法以至于每個頂點 v 都有 L（v

23、）中的一種顏色？這個列表染色問題已經(jīng)解決了。 因此，我們依靠和其相近的算法來解決頻道分配的問題。 我們的算法成為 “優(yōu)先搜索頻道分配法”，用優(yōu)先搜索來為網(wǎng)狀接收機分配頻道。搜索從網(wǎng)關(guān)節(jié)點開始的連線。優(yōu)先搜索的基本原理是直觀的：通過優(yōu)先搜索，從網(wǎng)關(guān)開始的線路具有頻道分配的優(yōu)先權(quán)然后至網(wǎng)絡(luò)的邊緣優(yōu)先性遞減。在用優(yōu)先搜索頻道分配法之前，頻道分配服務(wù)器從網(wǎng)狀路由器獲取干擾評估。然后為默認接受機選擇一個頻道。 這個默認頻道的選擇可以將網(wǎng)絡(luò)間的干擾最小化。 頻道分配服務(wù)器為網(wǎng)中不是默認的接收機構(gòu)建多信道沖突圖。 我們用一個兩跳干擾模型來構(gòu)建多信道沖突圖。在這個模型中，網(wǎng)中的兩條線路是干擾的如果他們有一個普

24、通的路由器或者間隔一跳分開的。 Padhye etal建議用經(jīng)驗主義技術(shù)來防護網(wǎng)中受干擾的線路。 這個技術(shù)更精確因為其經(jīng)驗主義的特性， 但是需要很長時間完成。我們研究來改進該技術(shù)的速度。與此同時，我們在工作中利用兩跳模型。構(gòu)造好多信道沖突圖之后，頻道分配服務(wù)器利用優(yōu)先搜索頻道分配法為非默認接收機選擇頻道。一旦網(wǎng)狀接收器的頻道選擇好，頻道分配服務(wù)器會指示路由器設(shè)置它們的接收機變?yōu)樾碌念l道。為了在本章更清楚地解釋頻道選擇步驟，我們假設(shè)網(wǎng)狀接收機被同時重置。我們會在第五章 D 節(jié)中說明上述假設(shè)，我們會陳述重置頻道的特殊協(xié)議的細節(jié)部分。默認頻道選擇步驟會在優(yōu)先選擇頻道分配法之后詳述。頻道分配服務(wù)器定期

25、地調(diào)用上述的頻道選擇步驟來改變網(wǎng)絡(luò)中的干擾特性。本章以調(diào)用周期和其蘊含式的討論結(jié)束。（二）默認頻道選擇頻道分配服務(wù)器用頻道序列c 來為整個網(wǎng)絡(luò) Rc 選擇默認頻道。R c 計算如下：nii1 Rank cRcn這里路由器的數(shù)量是 n， Rankic 是路由器 c 的頻道序列。默認頻道被選擇為 R c 最小值的頻道。標(biāo)準(zhǔn)時把受干擾最小的頻道作為默認頻道。這個默認頻道可以使干擾最小化。（三） .非默認頻道選擇在這個階段，頻道分配服務(wù)器用所有相鄰的路由器的信息來構(gòu)建多信道沖突圖。相鄰的信息包括所有路由器接收機支持的頻道的相鄰識別，延遲，干擾估計。第五章C 中詳述了路由器延遲的計算。頻道分配服務(wù)器與多

26、信道沖突圖中的每個頂點相關(guān)， 一個頻道序列由單獨頻道序列的平均數(shù)衍生的。 這個平均數(shù)很重要因為多信道沖突圖中的每個定點的頻道分配應(yīng)當(dāng)考慮終端接收機的性能。對于多信道沖突圖的所有頂點，頻道分配服務(wù)器計算他們距離網(wǎng)關(guān)的長度。這個距離是兩個接收機距離網(wǎng)關(guān)的平均距離。接收機的距離通過由始于網(wǎng)關(guān)的信標(biāo)獲得。一個信標(biāo)是網(wǎng)關(guān)廣告?zhèn)魉吞酚?。每個信標(biāo)包含了計跳數(shù)部分，傳送時，每一跳都自然加一。路由器距離網(wǎng)關(guān)的長度是所有路由器接收的信標(biāo)距離中最短的路徑長度。路由器將這個距離通過周期心跳信息傳送給頻道分配服務(wù)器。算法：一旦計算好平均距離，頻道分配服務(wù)器用優(yōu)先搜索頻道分配法來給網(wǎng)狀接收機分配頻道。 這個算法在算法 1 中總結(jié)。首先把所從有多信道沖突圖的頂點變?yōu)橐涣校ǖ?1 行）。通過優(yōu)先搜索來訪問所有的頂點并且分配頻道。搜索的頂點從網(wǎng)關(guān)起始的線路開始（第3.4 行）。在第三行中， 在多信道沖突圖的所有頂點來決定最小跳數(shù)的頂點。第四行中，所有距離與最小跳數(shù)距離相等的編入一列， Q。如果頂點相當(dāng)于所有始于網(wǎng)關(guān)線路的頂點，他們的跳數(shù)為0.5。這些頂點通過增加延遲值來分類（第5 行）。分類是為了給予那些從最短跳數(shù)的路由器開始的線路更高地優(yōu)先權(quán)。算法然后對每個Q 中的頂點運算并且永久的分配他們最高排列的頻道，不與相鄰的頻道分配沖突。如果無沖突頻道不可得到，則任意的選擇一個頻道永