基于干擾感知的多接口無線Mesh網(wǎng)絡(luò)信道分配算法

王子凡+劉作學(xué)+代健美

摘 要： 針對無線Mesh網(wǎng)絡(luò)因受部署在本地的其他網(wǎng)絡(luò)干擾而導(dǎo)致的傳輸能力下降的問題，設(shè)計了一種基于干擾感知的多接口動態(tài)信道分配算法予以克服。同時采用鏈接重建的方法避免傳輸中的數(shù)據(jù)流因信道改變而被破壞的問題。通過實驗仿真，證明在復(fù)雜電磁環(huán)境下，該算法能有效降低網(wǎng)絡(luò)干擾，保證網(wǎng)絡(luò)服務(wù)質(zhì)量。

關(guān)鍵詞： 無線Mesh網(wǎng)絡(luò)； 干擾感知； 多接口； 鏈路重建

中圖分類號： TN915?34 文獻標識碼： A 文章編號： 1004?373X（2014）14?0024?04

Interference?aware based channel assignment algorithm for multi?interface

wireless Mesh networks

WANG Zi?fan， LIU Zuo?xue， DAI Jian?mei

（Equipment Academy of PLA， Beijing 101416， China）

Abstract： An interference?aware based channel assignment algorithm is presented in this paper to solve the problem that the transmission capacity of wireless Mesh networks declines due to the interference from other networks deployed in the same area. A methord of link reconstruction is used to prevent data flow disruption caused by channel change. The simulation experiment results demonstrate that the algorithm can effectively reduce the network interference in a complex electromagnetic environment and assure the quality of network service.

Keywords： wireless Mesh network； interference?aware； multi?interface； link reconstruction

0 引 言

靜態(tài)部署的無線多跳網(wǎng)絡(luò)被稱為無線網(wǎng)狀網(wǎng)（Wireless Mesh Networks，WMN）。P.Gupta等人研究發(fā)現(xiàn)，由于無線介質(zhì)具有的半雙工傳輸特性，會導(dǎo)致單信道無線網(wǎng)絡(luò)的傳輸能力嚴重的下降[1]。同時隨著WiFi熱點日益密集，僅通過進行功率控制已無法滿足頻率復(fù)用的要求。動態(tài)信道分配方案以其高效的信道利用率和良好的信道自適應(yīng)性，能夠較好地避免網(wǎng)內(nèi)數(shù)據(jù)流間的干擾。本文提出一種基于干擾感知的集中式多接口動態(tài)信道分配算法，著重解決因網(wǎng)內(nèi)或網(wǎng)間干擾造成的傳輸能力下降問題。

1 系統(tǒng)模型

在無線Mesh網(wǎng)絡(luò)中，用戶終端通過網(wǎng)絡(luò)提供的AP接入點實現(xiàn)網(wǎng)絡(luò)接入的功能。圖1所示的無線Mesh網(wǎng)絡(luò)較傳統(tǒng)網(wǎng)絡(luò)引入了部分多射頻接口Mesh路由器（MR）。網(wǎng)絡(luò)中單射頻接口路由器（SR）裝配有相同類型的射頻接口，稱為默認射頻接口。MR至少有一個射頻接口與SR的射頻接口類型相同。為提高網(wǎng)絡(luò)容量，MR應(yīng)部署在位靠近網(wǎng)關(guān)節(jié)點的位置。信道分配服務(wù)器（CAS）部署在網(wǎng)關(guān)節(jié)點，作用是為多射頻Mesh路由器的射頻接口分配信道。圖1中實線表示默認信道，點狀線表示非默認信道。

圖1 多射頻接口無線Mesh網(wǎng)絡(luò)結(jié)構(gòu)

2 關(guān)鍵算法研究

2.1 干擾估計

干擾估計的目標是周期性衡量每個Mesh路由器周邊的干擾程度。干擾評估的過程可以描述為：Mesh路由器上每個射頻接口短時間內(nèi)在各自的信道上獲取數(shù)據(jù)包。路由器根據(jù)非預(yù)期MAC地址數(shù)據(jù)包的數(shù)量衡量干擾射頻的數(shù)量和信道的使用情況。每個路由器根據(jù)評估的計算結(jié)果維護兩組隊列，第一組根據(jù)檢測到干擾源的數(shù)量多少排序，第二組根據(jù)數(shù)據(jù)流占用信道帶寬的大小來排序。Mesh路由器將兩組排序進行融合并向CAS傳遞。

2.2 信道分配

本文提出的信道分配算法稱為沖突距離掃描信道分配算法（Interference Distance Scan Channel Assignment，IDS?CA）。將信道與CAS的距離作為判定權(quán)值，進而構(gòu)造多射頻沖突圖（Multi?ratio Conflict Graph， MCG）。CAS從Mesh路由器得到干擾估計的情況，為默認射頻接口選擇一條信道。默認信道的選擇原則是選擇與當?shù)責o線網(wǎng)干擾最小的信道。之后CAS使用IDS?CA算法為每個非默認的射頻接口選擇信道。

（1） 默認信道選擇算法。CAS利用信道等級選擇默認信道。默認信道等級為Rc，表達式為：

[Rc=i=1nRankicn]

式中：n表示W(wǎng)MN中路由器的數(shù)量；[Rankic]表示使用信道c的接口i的等級。Rc最低的信道就是默認信道。

（2） 非默認信道選擇算法。CAS使用路由器收集的鄰居信息來構(gòu)建MCG。Mesh路由器向CAS發(fā)送的信息中包含鄰居的身份，數(shù)據(jù)傳輸延遲，和信道干擾情況。分配信道過程中CAS與MCG中每個頂點對應(yīng)的延遲密切相關(guān)。CAS同樣與每個頂點的信道等級有關(guān)，該信道等級為Rd，其表達式為：

[Rd=j=1mRankid]

式中：m表示MCG節(jié)點j包含接口數(shù)量；[Rankid]表示使用信道d的接口j的等級。得出信道距離之后，CAS使用IDS?CA算法來對WMN的射頻接口分配信道。算法總結(jié)如下（IDS?CA算法）：

（1） 初始化網(wǎng)絡(luò)，創(chuàng)建表V={v|v∈MCG}

（2） while 未遍歷完表V中所有節(jié)點 do

（3） h=min{HopCount（V）}

（4） Q={v|v∈V & notVisited（v） & HopCount（v）==h}

（5） 將表Q按照鏈路延時的增加排序

（6） while size（Q）>0 do

（7） vcurent=RemoveHead（Q）

（8） if Visited（vcurent） then

（9） continue

（10） end if

（11） 訪問鏈路vcurent

（12） Vn={u|u∈MCG & u與vcurent在位置上相鄰}

（13） 將等級較高的穩(wěn)定信道c分配給vcurent，并且該信 道不與ui相沖突，{ui∈Vn & 0≤i

（14） if c不存在 then

（15） 將一隨機信道長久分配給vcurent

（16） end if

（17） L= {v|v∈MCG & v中含有vcurent所包含的任意一 個射頻接口}

（18） 從MCG中移走包含有L因子的頂點

（19） 將信道c臨時分配給R={r|r∈v & r?vcurent， v∈L}

（20） 設(shè)路由器rf為鏈路vcurent的遠端射頻接口（相對 CAS而言）所在的路由器

（21） 構(gòu)造表Tail，Tail={v|v∈MCG & 鏈路v的一端為 rf 的射頻接口}

（22） 將Tail按照鏈路延遲的增加排序

（23） 將表Tail中的鏈路添加到表Q中

（24） end while

（25） 為未被分配穩(wěn)定信道的射頻接口分配相對穩(wěn)定信道

（26） end while

其中：HopCount（V）的作用是計算表V中所有鏈路的跳數(shù)；RemoveHead（Q）的作用為獲取表Q中級別最高的鏈路，并將該鏈路從表Q中移出；size（Q）的作用為計算表Q中鏈路的數(shù)量；Visited（vcurent）返回一個布爾值，判定vcurent是否被訪問過。當信道分配完畢，CAS通知Mesh路由器重新配置射頻端的信道。

3 相關(guān)技術(shù)研究

（1） 干擾估計。在WMN中，Mesh路由器通過捕獲數(shù)據(jù)包執(zhí)行干擾估計。在實現(xiàn)中采用無線網(wǎng)卡模塊普遍支持的RFMom模式（無線頻率檢測模式）進行數(shù)據(jù)包捕獲，該模式能同時捕獲管理幀和普通數(shù)據(jù)幀。當射頻接口被設(shè)置成RFMom模式，在感知階段不能傳輸數(shù)據(jù)。由于每個路由器的干擾估計與它的鄰居進行干擾估計相互獨立，因此不能保證兩個工作在同一信道的射頻端能夠通信成功。為了防止數(shù)據(jù)流被破壞，引入了鏈接重建技術(shù)。

（2） 鏈接重建。鏈接重建是將數(shù)據(jù)流從非默認信道調(diào)整到默認信道的過程。其工作過程可描述為：無論何時，當一個射頻接口需將它的狀態(tài)變?yōu)楦蓴_感知狀態(tài)時，在它改變其狀態(tài)的3 s之前，每秒廣播一個INTERFACE?INACTIVE消息。任何鄰居收到INTERFACE?INACTIVE消息后，從它的路由表中刪除即將要變成干擾感知射頻接口的地址。一旦刪除發(fā)生后，連接重新定向功能便被激活。

（3） 信道分配協(xié)議。非默認信道分配通過調(diào)用鏈路重建防止數(shù)據(jù)流損壞。執(zhí)行分配時，CAS向路由器發(fā)送射頻接口重置的消息。Mesh路由器收到重置消息后向CAS發(fā)送一個確認，并開始調(diào)用鏈路重建過程。使用ping功能向鏈路上的鄰居節(jié)點進行活躍確認，鄰居節(jié)點將其添加入路由表中。分配默認射頻端信道，我們假設(shè)一個可靠的廣播協(xié)議是可用的，這個協(xié)議可以用來通知所有的Mesh路由器關(guān)于新的信道分配情況。

4 仿真及結(jié)果分析

網(wǎng)絡(luò)仿真使用Matlab作為軟件平臺，使用OLSR（Optimized Link State Routing）路由協(xié)議作為Mesh網(wǎng)的路由協(xié)議。Mesh路由器的射頻接口設(shè)置為IEEE 802.11a，多徑傳播模式使用瑞利衰落。傳輸功率設(shè)定為18 dBm。干擾估計每5 min 1次。每個信道干擾估計的時間被設(shè)定為3 s，共12個信道。CAS每10 min調(diào)用1次IDS?CA算法。

首先通過在一個簡單的拓撲模型中來驗證算法的正確性。網(wǎng)絡(luò)拓撲由4個網(wǎng)絡(luò)節(jié)點和2個干擾節(jié)點構(gòu)成。節(jié)點a裝備了1個射頻接口，節(jié)點b和d裝備有2個射頻接口，節(jié)點c裝備有3個射頻接口，節(jié)點d為網(wǎng)關(guān)（如圖2所示）。節(jié)點a以8 Mb/s的恒定速率向節(jié)點d發(fā)送包含大小為1 024 B的數(shù)據(jù)包。

圖2 驗證網(wǎng)絡(luò)

仿真開始時，所有的默認的射頻接口被配置在同一信道上。節(jié)點a的數(shù)據(jù)流只能通過默認信道到達網(wǎng)關(guān)。第一次信道分配發(fā)生在第600 s。在第900 s前夕，一個低比特率數(shù)據(jù)流在兩個干擾節(jié)點e，f之間傳輸，該數(shù)據(jù)流能影響到節(jié)點b和節(jié)點c，且和鏈路sbc使用相同的信道。圖3為網(wǎng)關(guān)節(jié)點收到的數(shù)據(jù)包的實時數(shù)量。

在第600 s之前，節(jié)點d每秒收到200個數(shù)據(jù)包。第600 s時，CAS進行了信道分配。節(jié)點d每秒收到數(shù)據(jù)包的數(shù)量上升到1 000個數(shù)據(jù)包左右。在在700～736 s處，路由節(jié)點進行干擾估計。在此時間段，節(jié)點d接收的數(shù)據(jù)包數(shù)量從1 000包/s降到200包/s。由于進行了鏈接重建，數(shù)據(jù)包傳遞速度沒有降到0。在第900 s前一刻，引入了干擾數(shù)據(jù)流（紅線），網(wǎng)絡(luò)穩(wěn)定性下降。節(jié)點c和d在1 036～1 072 s期間探測到了干擾，并將干擾估計送到CAS。在1 200 s時，CAS重新為鏈接分配信道，網(wǎng)絡(luò)趨于穩(wěn)定。在大范圍性能評估中，網(wǎng)絡(luò)拓撲使用文獻所設(shè)計的4種拓撲結(jié)構(gòu)，每個拓撲中共有30個路由器分布在500×500 m的區(qū)域內(nèi)。在此仿真設(shè)計了兩種網(wǎng)絡(luò)流量方案。第一種方案為理想情況，網(wǎng)絡(luò)中沒有內(nèi)部或外部的干擾數(shù)據(jù)流。第二種方案允許WMN中同時存在多個數(shù)據(jù)流，數(shù)據(jù)流之間存在相互影響。

圖3 網(wǎng)關(guān)節(jié)點數(shù)據(jù)包吞吐量

在方案1中，評估了在四種拓撲網(wǎng)絡(luò)結(jié)構(gòu)使用多射頻接口代替單射頻接口所獲得的吞吐量增益。圖4標繪了10個FTP傳輸器在單射頻Mesh路由器網(wǎng)絡(luò)、多射頻動態(tài)信道分配、多信道靜態(tài)信道分配的平均吞吐量。相比單射頻接口路由器，多射頻接口路由器在拓撲1中吞吐量提高了200%，在拓撲2和3提高了100%；在拓撲4中提高了33%。值得注意的是，在拓撲2～4中，靜態(tài)信道分配比IDS?CA算法有更好的吞吐量，分別高出大約8%，5%，15%。這是因為在理想條件下相比靜態(tài)信道分配，IDS?CA算法在進行干擾估計的操作時要耗費額外的資源。

圖4 方案1三種信道分配方式在四種拓撲結(jié)構(gòu)中的對比

在方案2中網(wǎng)絡(luò)中同時存在多個數(shù)據(jù)流。由于IDS?CA算法采用干擾估計技術(shù)，相鄰信道相互正交，如圖5所示，其傳輸性能要優(yōu)于靜態(tài)信道分配算法。特別在拓撲2中吞吐量提高了72%，在拓撲1，3，4分別提高了48%，60%和13%。

圖5 方案2動態(tài)信道分配與靜態(tài)信道分配的吞吐量對比

5 結(jié) 語

IDS?CA作為一種集中式多接口動態(tài)信道分配算法，在存在本地網(wǎng)絡(luò)干擾的條件下能有效避免無線Mesh網(wǎng)絡(luò)性能下降。下一步將對算法進一步優(yōu)化，減少評估過程中流量波動，提高網(wǎng)絡(luò)的傳輸穩(wěn)定性。

參考文獻

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

[2] MARINA M K， DAS S R， SUBRAMANIAN A P. A topology control approach for utilizing multiple channels in multi?radio wireless mesh networks [J]. Computer networks， 2010， 54（2）： 241?256.

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.

圖3 網(wǎng)關(guān)節(jié)點數(shù)據(jù)包吞吐量

在方案1中，評估了在四種拓撲網(wǎng)絡(luò)結(jié)構(gòu)使用多射頻接口代替單射頻接口所獲得的吞吐量增益。圖4標繪了10個FTP傳輸器在單射頻Mesh路由器網(wǎng)絡(luò)、多射頻動態(tài)信道分配、多信道靜態(tài)信道分配的平均吞吐量。相比單射頻接口路由器，多射頻接口路由器在拓撲1中吞吐量提高了200%，在拓撲2和3提高了100%；在拓撲4中提高了33%。值得注意的是，在拓撲2～4中，靜態(tài)信道分配比IDS?CA算法有更好的吞吐量，分別高出大約8%，5%，15%。這是因為在理想條件下相比靜態(tài)信道分配，IDS?CA算法在進行干擾估計的操作時要耗費額外的資源。

圖4 方案1三種信道分配方式在四種拓撲結(jié)構(gòu)中的對比

在方案2中網(wǎng)絡(luò)中同時存在多個數(shù)據(jù)流。由于IDS?CA算法采用干擾估計技術(shù)，相鄰信道相互正交，如圖5所示，其傳輸性能要優(yōu)于靜態(tài)信道分配算法。特別在拓撲2中吞吐量提高了72%，在拓撲1，3，4分別提高了48%，60%和13%。

圖5 方案2動態(tài)信道分配與靜態(tài)信道分配的吞吐量對比

5 結(jié) 語

IDS?CA作為一種集中式多接口動態(tài)信道分配算法，在存在本地網(wǎng)絡(luò)干擾的條件下能有效避免無線Mesh網(wǎng)絡(luò)性能下降。下一步將對算法進一步優(yōu)化，減少評估過程中流量波動，提高網(wǎng)絡(luò)的傳輸穩(wěn)定性。

參考文獻

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

[2] MARINA M K， DAS S R， SUBRAMANIAN A P. A topology control approach for utilizing multiple channels in multi?radio wireless mesh networks [J]. Computer networks， 2010， 54（2）： 241?256.

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.

圖3 網(wǎng)關(guān)節(jié)點數(shù)據(jù)包吞吐量

在方案1中，評估了在四種拓撲網(wǎng)絡(luò)結(jié)構(gòu)使用多射頻接口代替單射頻接口所獲得的吞吐量增益。圖4標繪了10個FTP傳輸器在單射頻Mesh路由器網(wǎng)絡(luò)、多射頻動態(tài)信道分配、多信道靜態(tài)信道分配的平均吞吐量。相比單射頻接口路由器，多射頻接口路由器在拓撲1中吞吐量提高了200%，在拓撲2和3提高了100%；在拓撲4中提高了33%。值得注意的是，在拓撲2～4中，靜態(tài)信道分配比IDS?CA算法有更好的吞吐量，分別高出大約8%，5%，15%。這是因為在理想條件下相比靜態(tài)信道分配，IDS?CA算法在進行干擾估計的操作時要耗費額外的資源。

圖4 方案1三種信道分配方式在四種拓撲結(jié)構(gòu)中的對比

在方案2中網(wǎng)絡(luò)中同時存在多個數(shù)據(jù)流。由于IDS?CA算法采用干擾估計技術(shù)，相鄰信道相互正交，如圖5所示，其傳輸性能要優(yōu)于靜態(tài)信道分配算法。特別在拓撲2中吞吐量提高了72%，在拓撲1，3，4分別提高了48%，60%和13%。

圖5 方案2動態(tài)信道分配與靜態(tài)信道分配的吞吐量對比

5 結(jié) 語

IDS?CA作為一種集中式多接口動態(tài)信道分配算法，在存在本地網(wǎng)絡(luò)干擾的條件下能有效避免無線Mesh網(wǎng)絡(luò)性能下降。下一步將對算法進一步優(yōu)化，減少評估過程中流量波動，提高網(wǎng)絡(luò)的傳輸穩(wěn)定性。

參考文獻

[1] GUPTA P， KUMAR P R. The capacity of wireless networks [J]. IEEE Transactions on Information Theory， 2000， 46（2）： 388?404.

[2] MARINA M K， DAS S R， SUBRAMANIAN A P. A topology control approach for utilizing multiple channels in multi?radio wireless mesh networks [J]. Computer networks， 2010， 54（2）： 241?256.

[3] BUDDHIKOT M M， MILLER S C， SUBRAMANIAN A P. Interference aware routing in multi?radio wireless mesh networks： US， 8，532，023 [P]. 2013?9?10.

[4] MWENJA J M. Framework for securing wireless local area network [D]. [S.l.]： [s.n.]， 2014.

[5] WANG A， ZHU B. Realize node localization based on OLSR protocol in Ad Hoc networks [J]. International Journal of Networked and Distributed Computing， 2013， 1（1）： 61?71.

[6] BAR F， PARK N. Municipal Wi?Fi networks： The goals， practices， and policy implications of the US case [J]. Communications & Strategies， 2006， 61（1）： 107?125.