無線Mesh 網絡負載與干擾感知傳輸時間路由度量

王繼紅，石文孝，尚 碩，許銀龍，李玉信，王春悅

(吉林大學 通信工程學院，長春130012)

0 引 言

無線Mesh 網絡(Wireless Mesh networks，WMN)是能夠解決“最后一公里”瓶頸問題的新型網絡架構［1］。WMN 有很多重要應用，比如:災難恢復、國土安全、會議中心等臨時按需組網;在難以部署光纜地區提供通信連接;更主要的應用是為密集城區提供寬帶Internet 接入，為蜂窩基站系統提供低成本回程網絡等［2］。因此WMN 受到了學術界和業界的廣泛關注。路由問題是WMN 面臨的一大技術挑戰，決定了業務的端到端性能，進而影響網絡容量。路由問題的核心是選取合理的路由度量進行路徑的計算和決策。

目前已經有文獻為WMN 提出各種路由度量。跳數［3］是多跳無線網絡中廣泛使用的路由度量，網絡通常選擇跳數最少的路徑進行數據包的傳輸;ETX(Expected transmission count)度量［4］考慮鏈路丟包率，使用一條鏈路上成功傳輸一個數據包所需要的期望傳輸次數(包括重傳)來反映鏈路質量;ETT(Expected transmission time)度量［5］通過整合鏈路傳輸速率改進ETX，但是ETX和ETT 都沒有考慮到干擾對路徑選擇的影響;WCETT(Weighted cumulative expected transmission time)度量［5］考慮了信道多樣性，將ETT 度量擴展到多收發信機多信道網絡場景，但是信道多樣性反映的是流內干擾，流間干擾未納入考慮;MIC(Metric of interference and channel switching)度量［6］在協議模型下同時考慮了流內、流間干擾、鏈路的丟包率和傳輸速率;IAWARE(Interference aware routing metric)度量［7］在物理干擾模型下使用接收信號功率衡量流內、流間干擾，更準確地捕捉干擾的加性特性。這些度量大多獨立地衡量流內干擾和流間干擾，導致度量非保序或引入可調參數等問題。CATT(Contention aware transmission time)度量［8］統一描述流內干擾和流間干擾，避免了上述問題。INX(Interferer neighbors count)度量［9］考慮了鏈路的遞交率和傳輸速率，使用干擾鄰居的傳輸速率來衡量負載，但是文獻［9］規定每條鏈路的傳輸速率相同，都使用標稱數據速率。因此，INX 度量與考慮鏈路遞交率的CATT 度量從本質上來說是相同的，且INX 和CATT 度量均未考慮負載對路由的影響，網絡可能會將數據流路由到網絡中的重負載區域，影響數據流的傳輸，甚至形成網絡瓶頸。因此本文在有效繼承CATT和INX 路由度量統一描述流內、流間干擾的基礎上，提出負載與干擾感知傳輸時間LIATT(Load and interference－aware transmission time)路由度量。LIATT 使用節點處的緩存隊列長度捕捉負載，使用鄰區平均負載強度捕捉干擾，實現有效的網絡負載均衡與干擾感知，提升網絡整體性能。

1 CATT 與INX 路由度量

首先對現有CATT 和INX 路由度量進行介紹。文獻［8］中提出的CATT 路由度量統一捕捉流內干擾和流間干擾，鏈路l 的CATT 度量由式(1)給出:

式中:Nl為與鏈路l 上的傳輸相干擾的鏈路集合，包括鏈路l本身;Lj是節點j 的包長度，對于網絡中所有節點取值相同，如512 B 或1024 B;Rj是節點j 的發包速率，對于網絡中所有節點，Rj取相同值，即信道的標稱數據速率，比如802.11 b/g 的2 Mbit/s 或11 Mbit/s，這樣Lj/Rj是個常數。因此，CATT 路由度量衡量的是鏈路l 的干擾鄰居數，即干擾范圍內使用相同信道的鏈路數，包括鏈路l 本身。

當考慮鏈路丟包時，CATT 路由度量擴展為CATTLD，鏈路l 的CATTLD度量由式(2)給出:

式中:ETXl表示鏈路l 的期望傳輸次數。

文獻［9］提出的INX 路由度量使用干擾鄰居的傳輸速率來衡量負載，鏈路l 的INX 度量由式(3)給出:

式中:ETTl表示鏈路l 的期望傳輸時間;|Nl|為與鏈路l 上的傳輸相干擾的鏈路數;S 為數據包大小，與式(1)中的Lj含義相同;Rl為鏈路l 的數據傳輸速率，文獻［9］中所有鏈路都使用相同的標稱數據速率，則Rl與式(1)中的Rj含義相同。由式(3)可以推導出如下表達式:

因此得出結論:INX 與考慮鏈路遞交率的CATTLD路由度量在本質上是相同的，均反映了干擾鏈路傳輸對鏈路l 上數據包傳輸的影響情況。

當考慮鏈路負載時，CATT 路由度量擴展為CATTL2D，鏈路l 的CATTL2D度量由式(6)給出:

式中:τj表示包的傳輸嘗試率，其余參數的含義與式(1)相同。實際上CATTL2D度量可以理解為使用干擾鄰居的沖突感知傳輸時間之和來表示負載，但是文獻［8］沒有給出τj的取值或獲取參數值的方法。

CATT 是一種保序［6］的路由度量，統一描述流內干擾和流間干擾。CATT 路由度量的優勢在于:

(1)可以避免路由度量的非保序性或使用復雜映射算法解決保序性問題。對于非保序路由度量，不能使用Dijkstra 和Bellman－Ford 等有效算法計算出最小權重路徑和非回環路由。使用映射算法實現保序性會增加路由算法的復雜度。

(2)可以避免引入可調參數。對于帶有可調參數的路由度量，需研究這些可調參數如何影響網絡整體性能以及如何根據不同網絡拓撲或業務類型合理調整參數值，這在實際應用中很難實現。

CATT 路由度量仍存在以下局限:

(1)沒有考慮節點處緩存包排隊的情況，新到達包必須等待隊列中前面的包服務完畢后才有傳輸機會。

(2)沒有考慮到鄰居的負載影響。鄰居的負載越重，發生信道競爭的概率越大;沒有負載(即不進行任何傳輸)的鄰居不會產生干擾。CATT沒有捕捉到這點，因此在某些情況下CATT 可能會放大干擾。

2 路由度量

2.1 LIATT 路由度量

本文充分繼承了CATT 度量的優勢，統一描述流內干擾和流間干擾影響，同時使用節點處的緩存隊列長度捕捉負載，使用鄰區平均負載強度捕捉干擾，提出了一種保序的負載與干擾感知傳輸時間路由度量LIATT。鏈路l 的LIATT 度量由式(7)～式(10)給出:

路徑p 的LIATT 度量由式(11)給出:

式中:Tl表示鏈路l 的實際傳輸速率;NLl是鏈路l的平均負載，使用鏈路端點處的緩存隊列長度表示;|Nl|表示干擾鏈路集合Nl中的干擾鏈路數，不包括鏈路l 本身;p 表示數據包經過的路由路徑，網絡會選擇LIATT 度量值最小的路徑進行數據包的傳輸。可以理解為節點j 排空緩存隊列所需的傳輸時間，即干擾鄰居j 的數據包總期望傳輸時間，其值越大表示與鏈路l 競爭的機會越大，對鏈路l 上數據傳輸的影響也就越大。由于節點業務負載隨時間變化較大，容易產生路由震蕩問題，因此采用干擾鏈路集合中各鏈路的期望傳輸時間標準差對負載進行平滑，同時也能更準確地衡量鏈路l 鄰區中的干擾。綜合以上分析，提出的LIATT 路由度量同時具備干擾感知和負載均衡的能力，能夠識別出網絡中的重干擾和重負載區域，指導網絡在路由選擇時避開這樣的區域，從而提升網絡的吞吐量。

2.2 考慮鏈路遞交率的E－LIATT 路由度量

LIATT 度量是在假設鏈路無丟包的理想情況下提出的。實際上鏈路遞交率會受到干擾等不穩定因素影響并隨時間變化，網絡不能保證所有數據正確完整的遞交。因此應考慮鏈路遞交率對路由選擇的影響，此時，LIATT 度量可擴展為ELIATT，如式(12)所示:

式中:ETXl表示鏈路l 的期望傳輸次數;LIAl由式(9)給出;df和dr分別表示鏈路l 的前、反向遞交率。

2.3 AODV 路由協議的修改及度量參數獲取

2.3.1 AODV 路由協議修改

AODV(Ad Hoc on － demand distance vector)［10］路由協議是一種按需路由協議。當有數據包要發送時，節點通過廣播路由請求(Routing request，RREQ)包發起路由請求過程，RREQ 包中攜帶源和目的節點的IP 地址和序列號、初始化為0 的路徑跳數值等信息。RREQ 包在向目的節點轉發過程中，中間節點更新路徑跳數值并建立到源節點的反向路由。當RREQ 包到達目的節點時，目的節點向源節點返回路由應答(Routing reply，RREP)包，更新路徑跳數值，建立到目的節點的正向路由。對AODV 路由協議進行了改進，使用路徑的LIATT 度量值字段取代跳數字段，當源節點和目的節點之間存在多條路由路徑時，選擇LIATT 度量值最小的路徑進行數據包的傳輸。

2.3.2 度量參數獲取

LIATT 路由的實現需要獲取關鍵參數，具體包括鏈路的實際傳輸速率Tl、干擾鏈路集合Nl和鏈路遞交率d(包括df和dr)，下面給出具體的參數獲取方法:

(1)鏈路的實際傳輸速率Tl:本文使用包對的方法獲取鏈路的實際傳輸速率，即節點周期性地發出兩個包，一個大包、一個小包，大小包分別為1137 B 和137 B，接收端記錄連續接收到兩個包的時間差，用大包大小除以時間差即得到鏈路實際傳輸速率的估計值。

(2)干擾鏈路集合Nl:兩條鏈路e1=(u1，v1)和e2=(u2，v2)之間的距離d(e1，e2)定義為鏈路e1的任一個端點與鏈路e2的任一個端點距離的最小值，具體表示如下:

式中:d(u1，u2)表示節點u1、u2之間的歐式距離;d(u1，v2)、d(v1，u2)和d(v1，v2)的含義與d(u1，u2)類似。

定義距離小于干擾范圍且使用同一信道的兩條鏈路互為干擾鏈路;一條鏈路l 的所有干擾鏈路構成的集合稱為干擾鏈路集合，干擾鏈路集合不包括鏈路l 本身。

干擾鏈路集合采用分布式信息交換方式獲得。每條鏈路的端節點周期性地廣播所使用的信道信息，其鄰居節點在接收到該廣播消息后會添加上自己的信道信息然后重新廣播出去。為了防止信道廣播消息的洪泛，同時考慮干擾范圍與傳輸范圍關系，本文在信道消息中加入跳數限制，使得信道信息只傳遞給干擾范圍內的節點，干擾范圍外的節點不需要也無法獲得該消息。根據收到的信道信息，節點可以判斷出干擾范圍內使用相同信道的鏈路集合，即獲取了干擾鏈路集合。

(3)鏈路遞交率d:鏈路遞交率使用探測包獲取［4］。節點每隔時間τ 周期性地向一跳鄰居發送探測包，每個探測包記錄前w 時間窗內接收到的探測包數Count(w)，則鏈路的遞交率如下:

3 性能評價與分析

本文使用NS－2.35 仿真工具對LIATT 及E－LIATT 路由度量的性能進行了仿真實驗。對NS－2 模塊進行擴展，以支持多信道多接口和改進的AODV 路由協議。在1000 m×1000 m 區域中部署了5×5 的格形拓撲，每個節點配置3 個網絡接口卡，網絡可用信道數為3。節點的傳輸范圍為250 m，干擾范圍為550 m。所有數據流均為CBR(Constant bit rate)流，包大小為512 B。

3.1 性能評價指標

仿真中使用網絡整體吞吐量、網絡平均丟包率和平均端到端時延對路由度量性能進行評價。

(1)網絡整體吞吐量Thr 定義為網絡中所有接收端單位時間內正確接收到的數據量，單位是kbit/s。表達式如式(6)所示:

式中:M 表示網絡中的數據流集合;Reci表示流i的接收端在流運行期間接收到的總數據量;Δt 表示網絡中第一個數據包發出時間與最后一個數據包接收時間之間的間隔，即網絡中數據流運行的總時間。

(2)網絡平均丟包率Err 定義為網絡中所有接收端未正確接收到的包數與發送端發送的總包數的比值。表達式如式(17)所示:

式中:N表示網絡中所有正確接收的數據包集合，|N|表示集合中的總包數;Ntotal表示網絡中所有發送端發送的總包數。

(3)端到端時延定義為數據包從開始發送到被接收端正確接收所需要的時間，平均端到端時延D 取為網絡中所有數據包端到端時延的平均值。表達式如式(18)所示:

式中:τj表示數據包j 的端到端時延。

3.2 LIATT 性能仿真及分析

首先固定節點發包速率，改變網絡中的流數，觀察流數變化對網絡性能的影響。CATT 和LIATT 度量下的網絡整體吞吐量、網絡平均丟包率和平均端到端時延的仿真結果如圖1 所示。

圖1 不同流數下CATT 與LIATT 的性能比較Fig.1 Performance comparison between CATT and LIATT with varying flow numbers

圖1 (a)表明隨著流數的增多，網絡整體吞吐量幾乎呈線性增長。由圖1(a)可以看出，LIATT度量的網絡整體吞吐量始終高于CATT 度量，當網絡中流數達到3 時，CATT 度量下的網絡整體吞吐量達到660.08 kbit/s，LIATT 度量下的網絡整體吞吐量達到710.19 kbit/s，吞吐量提高了7.6%。網絡平均丟包率與網絡整體吞吐量之間存在互補關系，如圖1(b)所示。由圖1(b)可以看出，LIATT 度量下的網絡平均丟包率始終低于CATT 度量，這與由圖1(a)得出的結論是一致的。圖1(c)給出了兩種度量下的平均端到端時延仿真結果，隨著網絡中流數的增多，平均端到端時延基本上呈現遞增的趨勢，但是LIATT 度量下的平均端到端時延始終低于CATT 度量，當網絡中流數達到3 時，CATT 度量下的平均端到端時延為0.4486 s，LIATT 度量下的平均端到端時延為0.2953 s，平均端到端時延降低34.2%。這表明LIATT 度量能較好地均衡網絡中的負載，感知重負載干擾區域，使網絡在為數據流選路時避開這些區域、能迅速傳遞這些數據流，從而實現提高網絡吞吐量性能和降低平均端到端時延的目的。

固定網絡中的流數，改變節點的發包速率，觀察發包速率改變對網絡性能的影響。由于篇幅限制，這里僅給出流數取為5 時的仿真結果，當流數取為其他值時結果類似。同樣使用網絡整體吞吐量、網絡平均丟包率和平均端到端時延來評價CATT 和LIATT 路由度量的性能，仿真結果如圖2所示。

圖2(a)表明隨著節點發包速率的增大，網絡整體吞吐量幾乎呈線性增長。由圖2(a)可以看出，LIATT 度量的整體網絡吞吐量始終高于CATT度量，當節點發包速率達到256 kbit/s 時，CATT度量下的網絡整體吞吐量達到1003.12 kbit/s，LIATT 度量下的整體網絡吞吐量達到1123.86 kbit/s，吞吐量提高了12%。

由圖2(b)可以看出，LIATT 度量下的網絡平均丟包率始終低于CATT 度量，與圖2(a)結論一致。圖2(c)為兩種度量下的平均端到端時延仿真結果，隨著節點發包速率的增大，平均端到端時延呈現線性增長的趨勢，但是LIATT 度量下的平均端到端時延始終低于CATT 度量，當節點發包速率達到256 kbit/s 時，CATT 度量下的平均端到端時延為0.416747 s，LIATT 度量下的平均端到端時延為0.318450 s，平均端到端時延降低23.6%。上述仿真結果同樣證明了LIATT 度量在提升網絡性能方面的優勢。

圖2 不同發包速率下CATT 與LIATT 的性能比較Fig.2 Performance comparison between CATT and LIATT with varying packet sending rates

圖3 E－LIATT 與LIATT 網絡整體吞吐量對比Fig.3 Total network throughput comparison between E－LIATT and LIATT

最后對考慮鏈路遞交率的E－LIATT 與LIATT 進行了簡單的性能比較，圖3 給出了兩種度量下網絡整體吞吐量的仿真結果。

由圖3 可以看出，當節點的發包速率改變時，E－LIATT 度量下的網絡整體吞吐量始終高于LIATT，即當考慮鏈路遞交率時，網絡整體吞吐量得到明顯提升，這主要是由于網絡在為數據包選路時會盡量避開丟包嚴重的鏈路，減少數據包重傳的次數，在相同條件下網絡可以傳輸更多的數據，從而實現網絡整體吞吐量的提升。

4 結束語

本文在分析CATT 路由度量優勢與局限性的基礎上，有效繼承其統一描述流內干擾和流間干擾的優勢，通過考慮節點的負載因素克服其局限性，提出負載與干擾感知傳輸時間路由度量LIATT 及考慮鏈路遞交率的路由度量E－LIATT。仿真結果驗證了本文路由度量相對于CATT 路由度量的優勢。IEEE 802.11 WMN 正交信道數有限，尤其是802.11 b/g 只有3 條正交信道。正交信道數的有限性使得為鄰近鏈路分配不同信道變得很難，鄰近鏈路使用相同信道引起的共干擾會導致網絡容量下降，因此僅利用正交信道難以解決干擾問題。部分重疊信道［11－12］的引入為WMN干擾減輕甚至消除帶來了新的思路，通過仔細規劃部分重疊信道的使用，增加網絡中的并行傳輸數，能顯著提升網絡容量。我們下一步的工作是研究部分重疊信道下的路由度量，以期進一步降低網絡中的干擾，提升網絡容量。

［1］Wu Di，Bao Li－chun，Regan Amelia C，et al.Large－scale access scheduling in wireless mesh networks using social centrality［J］.Journal of Parallel and Distributed Computing，2013，73(8):1049－1065.

［2］Subramanian P A，Buddhikot M，Miller S.Interference aware routing in multi－radio wireless mesh networks［C］∥The 2nd IEEE Workshop on Wireless Mesh Networks，Reston，USA，2006:55－63.

［3］Stallings William.Data and Computer Communications［M］.New Jersey:Prentice Hall，1997.

［4］Couto D S J D，Aauayo D，Bicket J，et al.A highthroughput path metric for multi－hop wireless routing［C］∥The 9th MobiCom，San Diego，USA，2003:134－146.

［5］Draves R，Padhye J，Zill B.Routing in multi－radio，multi－hop wireless mesh networks［C］∥MobiCom，Philadelphia，USA，2004:114－128.

［6］Yang Ya－ling，Wang Jun，Kravets Robin.Interference－aware load balancing for multihop wireless networks［C］∥The Proceeding of the IEEE Workshop on Wireless Mesh Networks，Santa Clara，USA，2005.

［7］Subramanian P A，Buddhikot M，Miller S.Interference aware routing in multi－radio wireless mesh networks［C］∥The 2nd IEEE Workshop on Wireless Mesh Networks，Reston，USA，2006:55－63.

［8］Genetzakis M，Siris A V.A contention－aware routing metric for multi－rate multi－radio mesh networks［C］∥The 5th Annual IEEE Communications Society Conference on Sensor，Mesh and Ad Hoc Communications and Networks，San Francisco，CA，United States，2008:242－250.

［9］Langar R，Bouabdallah N，Boutaba R.Mobility－aware clustering algorithms with interference constraints in wireless mesh networks［J］.Computer Networks，2009，53(1):25－44.

［10］Perkins E C，Royer B E.Ad hoc on－demand distance vector routing［S］.IEEE Workshop on Mobile Computing and Systems and Applications，1999.

［11］Sun Wei－feng，Fu Tong，Xia Feng，et al.A dynamic channel assignment strategy based on cross－layer design for wireless mesh networks［J］.International Journal of Communication Systems，2012，25(9):1122－1138.

［12］Ding Yong，Huang Yi，Zeng Guo－kai，et al.Using partially overlapping channels to improve throughput in wireless mesh networks［J］.IEEE Transactions on Mobile Computing，2012，11(11):1720－1733.