無線網絡負載均衡的干擾感知路由度量

李 雪，郁進明，史雨雨（東華大學 信息科學與技術學院，上海 201620）

無線網絡負載均衡的干擾感知路由度量

李 雪，郁進明，史雨雨
（東華大學 信息科學與技術學院，上海 201620）

無線信道干擾和負載分布不均勻嚴重影響無線網絡的網絡吞吐量、端到端延時等。在已有的路由度量的基礎上，充分繼承其通過鄰居節(jié)點負載描述干擾強度的優(yōu)勢，進一步分析節(jié)點負載的影響，提出負載均衡的干擾感知路由度量，將干擾鄰居節(jié)點的數量、負載和距離綜合作用結果作為流間干擾強度，使用節(jié)點處的平均隊列長度捕捉節(jié)點負載，并改進期望傳輸時間消除鏈路的不對稱性，實現(xiàn)負載均衡和干擾感知，避開熱點區(qū)域。同時將LBIA合并入路由協(xié)議。仿真結果表明：該路由度量可以有效地實現(xiàn)網絡負載均衡，提升網絡整體性能。

無線網狀網；路由度量；負載均衡；干擾感知

0 引言

在無線網絡中，無線網狀網（WMN）［1］因其綜合了傳統(tǒng)的AdHoc和WLAN的優(yōu)勢，作為3G蜂窩系統(tǒng)和無線局域網的替代方案，成為有前景的下一代無線網絡。而路由問題一直是面臨的技術挑戰(zhàn)之一，為了保證端到端的通信性能，進而獲得較高的網絡容量，作為路由問題的核心，有效的路由度量對于找到高吞吐量的路徑是必不可少的。

1 相關工作

決定路由協(xié)議性能最關鍵的部分是路由度量的設計，找到具有高數據速率、低丟包率和低水平干擾的路徑，是衡量路由度量好壞的標準。針對多接口多信道WMN路由度量研究已經廣泛展開。HOP［2］作為最早的路由度量機制已經廣泛應用到無線多跳網絡；ETX［3］引入丟包率來測量鏈路質量；ETT［4］在 ETX的基礎上考慮傳輸速率，但ETT和ETX均未考慮干擾對于路徑選擇的影響；MIC［5］是干擾感知路由度量，將延伸到同時考慮流間干擾和流內干擾，還有鏈路丟包率和傳輸速率。

ILA（Interference-Load Aware routing metric）［6］用鄰居節(jié)點的平均負載來衡量流間干擾的強度，但平均負載并不能真實反映流間干擾水平，對路徑選擇造成不小的偏差。此外ILA未考慮節(jié)點本身負載，且基于ETT，會造成鏈路質量不準確估計。

2 ILA路由度量

首先對現(xiàn)有的干擾負載感知路由度量進行簡要介紹，如式（1）所示：

其中，p為路徑，n為鏈路數，m為鏈路l上的節(jié)點數。MTI（Metric of Traffic Interference）捕捉流間干擾如式（2）所示，CSC（Channel Switching Cost）捕捉流內干擾。參數α是用來權衡流內干擾和流間干擾的權重。

其中，ALLij（Average Interference Load）是在信道 C上節(jié)點i、j之間干擾鄰居節(jié)點的平均負載。ETT用來確定傳輸速率和丟包率的差別。AIL描述干擾節(jié)點的鄰居節(jié)點活躍性，定義為：

其中，ILij（C）是干擾鄰居的負載，用平均隊列長度來表示。

CSC通過給定使用同一信道的連續(xù)鏈路更高的權重來減少流內干擾，下文將詳細討論。

ILA路由度量捕捉了流間和流內干擾，但仍存在局限性。

3 LBIA路由度量

本文提出負載均衡的干擾感知路由度量（Load Balanced Interference-Aware Routing Metric，LBIA），有以下改進：

（1）通過干擾鄰居節(jié)點距離對干擾鄰居節(jié)點負載的計算進行優(yōu)化，得到更準確的干擾水平。

（2）通過節(jié)點負載，選擇負載較小的節(jié)點作為傳輸路徑，節(jié)省等待隊列傳輸的時間，得到較低的端到端延遲。

（3）對原ETT進行改進，消除傳輸不對稱性，提高合理性，正確評估鏈路質量。

鏈路l的LBIA定義為：

LBIA由 3部分組成：NIL（Neighbout Interference Load）為鄰居干擾節(jié)點表征的流間干擾程度，是鄰居干擾節(jié)點的數量、負載和與受干擾節(jié)點間的距離共同作用的結果；NL（Node Load）為被干擾節(jié)點自身的負載，由緩存隊列的長度來捕捉負載；CSC為流內干擾大小。這樣通過關注通信負載、節(jié)點負載、丟包率、傳輸速率、流內干擾和流間干擾，突破現(xiàn)有路由度量的有限性。

3.1 ETT的改進

ETT是應用最廣泛的路由度量，但不對稱性使得高估鏈路質量，對路由選擇造成偏差，如式（6）所示：

其中，S是數據包大小，Bl是鏈路l的帶寬，ETX如式（7）所示：

其中，df為前向傳輸比率，是鄰居節(jié)點周期內成功接收到探測包的比率；dr為反向傳輸比率，是節(jié)點在相反方向成功接收到相應鄰居節(jié)點的廣播探測包。鄰居節(jié)點周期性地交換小探測包，進而算出ETX，找到有最大傳輸速率的路徑。

但這將導致鏈路質量估計不準確。式（7）中 df與 dr的權重相等，而實際傳輸中前向傳輸節(jié)點傳送的數據包遠大于反向傳輸收到的ACK數據包，并且反向ACK數據包的鏈路損失小，導致通信的不對稱性，如圖1所示。

圖1 ETX中數據包不對稱性問題

A節(jié)點有兩條可能的路線，A-B-D或A-C-D。因ETX分配給前向和反向鏈路相同的權重，所以得到式（8）：

故路徑A-B-D和A-C-D路由度量值相等，但根據數據包和大小不對稱性，合理地看出鏈路（A，B）比鏈路（A，C）性能更好。借鑒參考文獻［7］，提出改進 ETT，如式（9）所示：

Bi鏈路 i的傳輸速率，S是數據包大小，S/Bi評估出通過鏈路i傳輸一個數據包期望時間。改進的ETT很好地消除了傳輸的不對稱性，對基于ETT的LBIA網絡性能有很大提高，能夠正確評估鏈路質量。以下公式中ETT均為式（8）。

3.2 NIL鄰居干擾負載

NIL鄰居干擾負載為：

其中，ETTij（C）是節(jié)點 i、j在信道 C上的期望傳輸時間，ILij為鄰居干擾負載。由節(jié)點間距離的路徑損耗，干擾鄰居節(jié)點負載和數量表征為：

其中，Load是干擾鄰居節(jié)點的負載，用平均隊列長度來度量，即數據包的數量。PL是路徑損耗，ΣNlLoad/10∧（PL/10）為各干擾鄰居節(jié)點負載經過路徑損耗后的負載之和，Nl（C）如式（4）所示，是干擾節(jié)點i、j干擾鄰居集合。

PL路徑損耗為：

其中，d為節(jié)點與干擾鄰居節(jié)點間的距離，davg為兩個單跳節(jié)點間的平均距離，n為跳數，λ為波長。鄰居節(jié)點數量一定時，干擾強度隨鄰居節(jié)點與被干擾節(jié)點的距離增大而減小。被干擾節(jié)點與鄰居節(jié)點距離一定時，干擾節(jié)點數量和負載越少干擾越小。因此流間干擾水平與鄰居干擾節(jié)點的數量、負載和節(jié)點間距離相關。α為權重參數，定義為：

3.3 NL節(jié)點負載

被干擾節(jié)點負載為：

其中，Li為節(jié)點負載，由平均隊列長度表示。它表明節(jié)點自身負載強度，決定緩存包等待時間與通信能力的強弱，避開重負載區(qū)域，提升網絡的吞吐量，保證網絡性能。

3.4 流內干擾

流內干擾和流間干擾同時存在于WMN中，LBIA中NIL捕捉流間干擾，為了捕捉流內干擾，將 CSC應用于LBIA，與ILA類似。使用不同信道傳輸數據的節(jié)點比始終使用同一信道的節(jié)點有更低的流內干擾水平，因此給使用同一信道的連續(xù)鏈路更高的權重，定義為：

其中，CH（i）表示分配給節(jié)點i傳輸的信道，prev（i）是在路徑p上節(jié)點i的前一跳。設節(jié)點i配有多個信道。當節(jié)點i向下一節(jié)點傳輸時應使用不同于之前接收到的數據的信道以消除流內干擾。若節(jié)點i仍使用接收到數據的信道，則分配更高的權重；若節(jié)點i在傳輸和接收數據時使用不同的信道，則分配一個較低的權重，所以0≤w1≤w2。

綜上，LBIA繼承了ILA度量描述流內、流間干擾的優(yōu)勢，將干擾與被干擾節(jié)點間的距離引入流間干擾估計，得到鄰居干擾節(jié)點數量、負載和距離多重作用的流間干擾強度，使用節(jié)點處的平均隊列長度捕捉節(jié)點負載，并且通過改進期望傳輸時間來消除鏈路的不對稱性，這樣LBIA度量兼?zhèn)湄撦d均衡和干擾感知的能力，能夠準確地識別出重干擾重負載的區(qū)域，避開“熱點”區(qū)域，合理分配路由，達到提高網絡吞吐量，減少端到端時延的目的。

4 LBIA度量的實現(xiàn)

4.1 AODV的修改

對 AODV［8］路由協(xié)議進行改進，以 LBIA值取代跳數，即選擇LBIA值最小的路徑進行數據傳輸。

4.2 ETX參數獲取

利用AODV的HELLO消息來計算ETX。每個節(jié)點向鄰居節(jié)點廣播周期性HELLO消息，即1 s，TTL值為1。每個節(jié)點記錄在w秒內接收的消息，即可算出df和

一條路徑的ETX是該路徑上所有鏈路的ETX之和，繼而得出ETT。

4.3 負載參數獲取

載波偵聽會阻止相互干擾范圍內兩個節(jié)點同時傳輸。節(jié)點傳輸速率會隨著同時開始廣播連續(xù)數據包的節(jié)點增多，逐漸低于單獨傳播速率。據此可通過廣播速率判斷兩節(jié)點是否處于相互干擾范圍內。

HELLO消息包含當前負載信息。每個節(jié)點保存一張記錄其鄰居節(jié)點及其負載的表。當一個節(jié)點接收到從鄰居節(jié)點發(fā)來的HELLO消息，它將與鄰居表進行核查。若該鄰居已經在表中，則更新其負載，否則將該鄰居加入鄰居表內。如果一個節(jié)點從一個鄰居節(jié)點接收3個連續(xù)HELLO消息失敗，將會從鄰居表內把該鄰居節(jié)點移除。這樣，就可以用鄰居表中的負載信息來計算干擾鄰居的負載，同時獲得節(jié)點自身的負載。

5 性能仿真與結果分析

本文采用NS2［10］仿真工具進行仿真實驗，將 ILA和MIC作為比較，對LBIA性能進行驗證。將NS2模塊進行擴展，以支持多信道多接口和改進的AODV路由協(xié)議。

5.1 仿真場景和參數設置

用于NS2仿真的場景參數設置如表1所示。

表1 仿真場景參數設置

5.2 LBIA性能仿真及分析

圖2～圖4分別給出在改變網絡中流數情況下，LBI-A、ILA、MIC下網絡整體吞吐量、平均丟包率和平均端到端時延的仿真結果。

圖4 平均端到端時延與流數的關系

由圖2和圖3看出，隨著流數逐漸增多，平均流吞吐量均有所下降。LBIA平均流吞吐量始終高于 ILA、MIC。流數為6時，LBIA的值為8.5 kb/s，與MIC相比提高了15％。其中MIC最低，因其未動態(tài)檢測干擾并且為考慮通信負載，而且 MIC中的 ETT還高估了鏈路質量。ILA雖也基于ETT，由于將干擾和負載考慮在內，其值較MIC有所提升。網絡平均流吞吐量與平均丟包率之間存在互補關系［11］，如圖3所示，LBIA的值始終低于 MIC和ILA，這與圖2得出的結論是一致的。當流數為8時，LBIA的值為 17％，比MIC降低了 10.5％。從圖4看出，平均端到端時延隨著流數的增多呈現(xiàn)上升趨勢，其中LBIA的平均端到端時延增長速度最慢，且始終處于MIC和 ILA之下。流數為 10時，LBIA的值比 MIC降低46.23％。以上表明，LBIA能夠較好地均衡通信負載，感知有重負載和干擾的擁塞區(qū)域，有效地分配網絡通信，以免數據包緩沖很長時間，達到提高網絡吞吐量和降低端到端時延的目的。

6 結論

本文在分析ILA的基礎上，繼承了其利用負載描述流間干擾的優(yōu)勢，通過考慮鄰居干擾節(jié)點的距離、數量和負載的共同影響以及源節(jié)點本身的負載，消除度量的不對稱性，提出負載均衡的干擾感知路由度量LBIA，并且將LBIA應用于修改的AODV路由協(xié)議。仿真結果驗證了LBIA相對于MIC和ILA的優(yōu)勢，可以有效地提高網絡吞吐量，降低端到端時延和丟包率，提高網絡的整體性能。

［1］黃旭，王子歐，季愛明.基于 ZigBee無線 Mesh網絡的溫濕度測量系統(tǒng)［J］.微型機與應用，2014，33（9）：89-91.

［2］WILLIAM S.Dataand computer communications［M］.NewJersey：PrenticeHall，1997.

［3］COUTO D S J D，AAUAYO D，BICKET J，et al.Ahighthrough put path metric for multi－h(huán)op wireless routing［C］.The 9th MobiCom，San Diego，USA，2003：134-146.

［4］DRAVES R，PADHYE J，ZILL B.Routing in multi-radio，multi-hop wireless mesh networks［C］.MobiCom，Philadelphia，USA，2004：114－128.

［5］Yang Yaling，Wang Jun，ROBIN K.Interference aware load balancing for multihop wireless networks［C］.The Proceedings of the IEEE Workshop on Wireless Mesh Networks，Santa Clara，USA，2005.

［6］SHILA D M，ANJALI T.Load aware traffic engineering for meshnetworks［J］.Computer Communications，2008，31（7）：1460-1469.

［7］GENETZAKIS M，SIRIS V.Acontention-aware routing metric for multi-ratemulti-radio mesh networks［C］.Sensor，Mesh and AdHoc Communications and Networks，2008：242-250.

［8］藺紹良，龍海南.基于穩(wěn)定性的 AODV路由協(xié)議研究與仿真［J］.微型機與應用，2013，32（20）：48-50.

［9］孫志.基于WCETT的多信道WMN路由量度的研究［J］.通信技術，2013，46（6）：82－84.

［10］于斌等.NS2與網絡模擬［M］.北京：人民郵電出版社，2007.

［11］杜輝.無線 Mesh網絡路由協(xié)議研究［D］.武漢：武漢科技大學，2010.

Load balanced and interference-aw are routing metric for w ireless mesh netw orks

Li Xue，Yu Jinming，Shi Yuyu
（College of Information Science＆amp；Technology，Donghua University，Shanghai 201620，China）

Wireless channel interference and uneven distribution of load affect network throughput and end-to-end delay in WMN.Based on ILA，LBIA is proposed.It inherits advantage of describing the extent of interference by the load of neighbor nodes and further analyzes the influence of the node load.The inter-flow interference extent is measured by the combined result of number，load of interfering neighbor nodes and the distance between nodes and neighbor nodes.The buffer queue length of the node is used to capture traffic load.The expected transmission time is improved to remove the asymmetry of the link.Eventually it can balance the load，be aware of interference and avoid the hot area.The simulation results show that the LBIA routing metric can effectively achieve load balancing and improve the whole network performance.

WMN；routing metric；load balancing；interference-aware

文獻標識碼：A 文章編號：1674-7720（2015）22-0064-04

李雪，郁進明，史雨雨.無線網絡負載均衡的干擾感知路由度量［J］.微型機與應用，2015，34（22）：64-67.

2015-07-22）

李雪（1990-），女，工學碩士，主要研究方向：WMN無線通信系統(tǒng)，通信系統(tǒng)建模與仿真等。

郁進明（1965-），男，副教授，碩士生導師，主要研究方向：無線信道系統(tǒng)及其相關應用，無線傳感網等。

史雨雨（1990-），女，工學碩士，主要研究方向：Z igBee無線通信系統(tǒng)，路由算法與協(xié)議等。