基于跨層設計的CLRM-HWMP路由協議研究

蔣緯昌,龍昭華,侯堂杰(重慶郵電大學計算機科學與技術學院,重慶 400065)

?

基于跨層設計的CLRM-HWMP路由協議研究

蔣緯昌,龍昭華*,侯堂杰
(重慶郵電大學計算機科學與技術學院,重慶 400065)

在研究HWMP路由協議的基礎上引入跨層設計方法,綜合考慮數據鏈路層的數據幀傳輸成功率DFTE(Data Frame Transmission Efficiency)、網絡層的可用帶寬和節點跳數作為跨層路由度量值CLRM(Cross-Layer Routing Metric),提出一種綜合路由判據的跨層路由協議CLRM-HWMP路由協議。該協議有效解決單一的路由量度判據在提高無線Mesh網絡性能方面的局限問題。通過NS-3仿真工具對無線Mesh網絡中的HWMP路由協議和提出的CLRM-HWMP跨層路由協議進行分析對比,實驗結果表明:提出的CLRM-HWMP路由協議有效降低了節點間端到端時延、提高了數據包投遞成功率和網絡吞吐量。

無線Mesh網絡;路由判據;跨層路由度量;HWMP;CLRM-HWMP

無線Mesh網絡不僅具有傳統無線網絡方便管理的特性,還具有自組織、容量大、成本低、冗余性好、擴展靈活的特性[1]。近年來音視頻等多媒體數據業務的爆發式增長,使得原有的無線Mesh網絡路由協議難以滿足用戶的需求。

在IEEE802.11s標準中無線Mesh網絡默認采用HWMP[2]路由協議,該協議具有按需路由協議和先驗式路由協議的功能。例如基于網絡層的按需路由的AODV[3]路由協議是當節點需要時才開始廣播消息建立網絡,但是容易造成路由發現時間長和分組傳輸時延過大。DSDV[4]路由協議設置序列號,用序列號作為路由判據的依據,序列號大的作為優先路由,當序列號相同時以跳數少的路由作為優先路由,采用洪泛方法開銷較大,帶寬利用率低。OLSR[5]路由協議以網絡層的參數“最小跳數”為依據,沒有考慮鏈路的可靠程度和節點的負載程度等。

文獻[6]中使用3種基于跨層設計思想的路由判據EFW(Expected Forward Counter)、MEFW(Minimum Expected Forwarding Conuter)和JEFW(Joint Expected Forwarding Counter)來處理路由節點的自私行為。EFW路由判據采用跨層設計思路,結合路由層的轉發機制以及MAC層對無線鏈路的質量測量的結果來優化路徑選擇。

文獻[7]中Ding等提出了一個基于跨層的機會頻譜獲取和動態路由算法ROSA(Routing and Dynamic Spectrun Allocation)。ROSA算法通過結合跨層設計、聯合機會路由(Joint Opportunity Routing)、動態頻譜分配、分布式調度、傳輸功率控制等方面的機制,努力將網絡吞吐量最大化,同時又不對其他用戶產生干擾,并且還能將數據傳輸的誤碼率控制在一定范圍之內。

通過設計合適的策略能夠實現無線Mesh網絡中不同層次之間的跨層信息交互[8],可以避免單一層次的路由度量值帶來的不足。文獻[9]中提出的能量受限的路徑選擇和能量高效的跨層負載分配方法,就是通過利用隨機動態規劃技術以及MAC層和網絡層的跨層交互減少了節點能量的消耗,實現了能量高效的路由協議。

本文以無線Mesh網絡中默認的HWMP協議為基礎,提出了基于數據鏈路層數據幀傳輸成功率、網絡層的可用帶寬和節點跳數作為跨層路由度量值的CLRM-HWMP路由協議。實驗結果表明提出的基于跨層設計的CLRM-HWMP路由協議在平均端到端時延、平均數據包投遞率和網絡吞吐量方面有更好的效果。

1 跨層路由度量值CLRM的設計

由于擁塞或者數據幀的丟失,網絡節點在發送數據幀之后沒有收到回復的ACK或者在發送完RTS后沒有收到回復CTS就會重傳。MAC層每次完成傳輸RTS和數據的重傳次數概率就反應了當前鏈路的質量。因此,可以將其作為選擇最佳路徑的重要參數。但是在選擇路徑時,如果只考慮這一種參數顯然是不夠的,選擇出來的路徑可能會有較遠的距離即很大的跳數,這和那些信道質量較差的路徑相比較性能可能更差。所以在設計無線Mesh網絡的路由協議時,應當考慮多種因素,特別是要打破層的界限,綜合不同層之間的參數來設計新的路由判據。基于此文中提出基于數據鏈路層的數據幀傳輸成功率、網絡層的可用帶寬[10]和跳數作為綜合路由判據。

1.1 數據幀傳輸成功率DFTE

數據鏈路層的數據幀傳輸成功率將在節點向其鄰居節點轉發分組信息的時候更新,即對每個成功傳輸數據幀的重傳次數計數就能通過計算得到最新的數據幀傳輸成功率DFTE,然后將其傳遞給網絡層。MX-MAC同樣使用了IEEE802.11標準中的管理信息庫里的ACKFailureCount和RTSFailureCount,這兩個參數分別表示數據幀和RTS幀的重傳次數。另外,數據幀傳輸成功率在無線鏈路中的變化很快,起伏可能會很大,因此選擇出的路徑也可能變化很快而不是最佳路徑。為避免這種情況的發生,采用類似指數加權移動平均數EWMA[11](Exponentially Weighted Moving Average)的方法,在路由表更新周期T時間內使用DFTE移動平均數,同時根據當前的網絡狀況為最新的DFTE和舊的平均DFTE指定不同的權重系數。

使用RTS/CTS機制時,MAC層傳輸的過程如圖1所示。當節點1發送RTS幀請求連接從節點1到節點2的信道后,節點1會等待一個時間,這個時間是請求時間超時。如果在這個時間段之內沒有收到回復的CTS幀,節點1就會重新發送RTS幀,直到收到節點2回復的CTS幀。這時候節點1就獲得了一個沒有沖突的信道。RTS的重傳次數可以表示節點1到節點2之間信道鏈路的競爭程度,反映了該信道的鏈路質量。

圖1 RTS/CTS重傳機制示意圖

為了計算出當前鏈路的數據幀傳輸成功率DFTE,每個節點都使用MIB變量來獲得當前鏈路上完成一個數據幀的重傳次數。假設從節點A到節點B完成傳輸第i個分組的重傳次數為FailureAB(i),其值為式(1):

FailureAB(i)=ACKFailureCountAB(i)+RTSFailureCountAB(i)

(1)

FailureAB(i)實際上就是DATA和RTS的重傳次數和,在理想狀態下對于RTS和DATA應該僅有一次傳輸,因此從節點A到FailureAB(i)節點B的數據幀的成功傳輸率DFTEAB(i)可以按式(2)計算:

(2)

這個參數是DATA幀和RTS幀成功發送的概率。當重傳次數越大,DFTE的值將越小;當沒有發生幀丟失時,重傳的次數為0,FailureAB(i)為1,即數據分組一次性被全部發送成功。另一種情況則是:若重傳次數超過一定的閾值則停止發送,這個時候FailureAB(i)為0,這將減小傳輸成功率的移動平均值。

不使用RTS/CTS機制時,FailureAB(i)是ACK幀的重傳次數ACKFailureCountAB(i),則DFTEAB(i)如式(3):

(3)

在路由表的的更新周期T時間段內,發送節點A對得到的DFTEAB(i)求EWMA值,該值反映了鏈路AB之間的擁塞情況及鏈路質量。這個平均值為式(4):

DFTEAB(i)=αi×DFTEAB(i)+(1-αi)×DFTEAB(i-1)

(4)

式中:DFTEAB(i)是發送節點在傳輸第i個分組時該條鏈路DFTE的移動平均值,αi的值取決于信道變化的速度。為了避免選出的路徑變化過大,αi被設定為10%,即當前的DFTE值占權重的10%,之前的平均DFTE值占權重的90%。如果信道不穩定,可以將αi的值提到到30%或者更高。

1.2 可用帶寬估算

在無線Mesh網絡中,由于無線信道空間復用的特性,導致不經過相同節點的多條鏈路之間也會存在干擾,相互競爭帶寬資源。無線信道的沖突競爭和易受干擾的特性帶來了挑戰,其中一個挑戰是節點I在網絡層的參數可用帶寬Bavailable(I)。由于鄰居節點同時存在進行數據傳輸的干擾,其實際消耗的帶寬遠大于其所需要的帶寬。因此,在考慮路由判據因素時,也要充分考慮網絡的可用帶寬。節點I所在信道的總的業務Bagg(I)由式(5)所示的三部分的和組成。

Bagg(I)=Bself(I)+Bneighbor(I)+Bboundary(I)

(5)

式中:Bself(I)表示節點I與其鄰居節點間的業務占用帶寬,Bneighbor(I)表示節點I的鄰居節點間業務占用帶寬,Bboundary(I)表示節點I的非鄰居節點與I的鄰居節點間業務占用帶寬。由上可知,節點I的的可用帶寬Bavailable(I)則可表示如下式(6)。

(6)

由式(6)可以看出,如果想要求得節點I的可用帶寬Bavilable(I),則必須先求得其與鄰居節點間業務已經占用的帶寬。大多數算法采用發送HELLO分組的方式進行帶寬估計,這樣的方式大大消耗了網絡資源,鑒于此,本文并不采用這種方式,而是利用MAC協議的能力實現估算。無線網絡中,節點所在信道空閑的時間由該節點和所有鄰居節點的業務量共同決定,信道空閑預示著節點能夠傳輸數據。因此,信道空閑也就說明帶寬可用,空閑時間的長短間接反應節點傳輸數據能力的強弱。所以,可用式(7)計算節點可用帶寬。

(7)

式中:Tinteral表示時間間隔,Tidle表示在Tinteral時間段內信道的空閑時間。根據式(7),Bavilable(I)的估算主要取決于Tidle的計算。

由于CSMA載波監聽機制[12]能夠判斷當前信道是否空閑,因此,借助該機制可以進行網絡空閑時間的估算。載波監聽分為兩種:一種方式是虛擬方式,另一種方式是物理方式。其中物理層提供了物理載波監聽機制,MAC層提供了虛擬載波監聽機制,兩種監聽方式中如果有任何一種方式判定信道忙,則認為該信道處于忙的狀態,繼續監聽。假設在單位時間間隔內,檢測到信道忙的時間為Tbusy,則Tidle可以用式(8)進行計算。

Tidle=Tinteral-Tbusy

(8)

將式(8)代入式(7)就可以看出,節點可用帶寬的估算結果是否精確主要在于觀察時間間隔的選取。當選取的時間間隔過大時,則不能很好的反應帶寬變化的實時性,選取過小時,無法獲得精確的信息。針對此問題本文將帶寬的計算公式進行如式(9)的改進,改進的主要目的在于計算當前時刻的可用帶寬時,必須考慮上一時刻的觀察值,進而體現帶寬的動態特性。

Bavilable=Bt×?+Bt-interal×(1-?),0≤?≤1

(9)

實驗證明,?取0.8,Tinteral取0.3比較合適。結合式(7)～式(9)很容易得出節點當前可用帶寬。

1.3 跳數度量計算

在路由協議的判據因素中,跳數作為一個重要的參數被很多路由協議采用,其具有簡單性也能控制網絡規模大小。如果從發送節點A到目的節點B是一個多跳路徑,DFTEAB則由當前鏈路上的DFTEXY相乘得到,X、Y是指鏈路之間每一跳的兩個相鄰節點。為了避免選擇到一條跳數太大的鏈路則必須將跳數這一參數考慮進去,跳數記為HopMetricAB如式(10)所示:

(10)

式中:HopMetricAB反映了從發送節點A到目的節點B的最小跳數,該參數用作最后度量值的重要一部分,NodeNum是網絡中節點的最大數,HopCountAB是當前鏈路的跳數。從式(10)可以看出,鏈路的跳數越大,則參數HopMetricAB則會越小。

最終的跨層路由度量值CLRM如式(11)所示:

CLRMAB=DFTEAB×Bavilable×HopMetricAB

(11)

式(10)代入式(11)得式(12):

(12)

在HWMP協議中默認采用時空鏈路度量[13]Ca作為路由度量值,公式如(13)所示:

(13)

式中:Oca表示信道接入負載,OP表示MAC協議負載,Bt表示測試幀中的比特數,并且這3個參數都是常量,r是傳輸比特率,單位是Mbit/s,efr表示幀錯誤率。可以看出HWMP協議的路由判據主要由r和efr來確定。

對比式(12)和式(13)可以看出,新的路由度量值CLRMAB綜合考慮數據幀傳輸成功率、可用帶寬和跳數等不同層的因素,且包含HWMP協議中的路由判據因素,其路由度量值不再由單一的因素決定,這樣可以避免單一路由度量值帶來的不足。

2 仿真與性能分析

本文通過仿真實驗對提出的CLRM-HWMP跨層路由協議進行分析對比。仿真實驗平臺采用Ubutu14.01下的NS-3網絡仿真軟件,在平均端到端的時延、網絡吞吐量和數據包成功投遞率3個方面與HWMP路由協議進行分析對比。

在仿真實驗中,根據無線網絡的特性,設置在2 000m×2 000m的范圍內,產生50個節點的隨機拓撲。節點配置Single-radio單接口,傳輸域為200m,偵聽范圍[14]400m。采用UDP數據流,數據包大小為512byte。

圖2為數據包的端到端時延隨著網絡中數據流增加的變化情況。由圖所示,兩種路由協議的端到端延時均隨著網絡流量的增加而增加,因為當網絡流量增大時,網絡的負載增加,導致沖突的可能性也急劇增大,然而由于CLRM-HWMP路由協議中的路由判據充分考慮了鏈路質量這一因素,因此該協議可以選擇鏈路質量更優的路徑從而避開擁塞路徑,降低了端到端時延。

圖2 平均端到端時延

圖3為網絡中數據包投遞率隨著網絡流量增大的變化情況。由圖所示,隨著網絡流量的增加,數據包的成功投遞率都隨之降低,這是因為流量的增加導致網絡中數據沖突增加,致使數據包的投遞率也隨之下降。但是改進的協議的數據包投遞率明顯高于原有的協議,這是因為優化的MX-MAC協議中增加了退避機制,有效降低了移動節點之間的沖突,使得CLRM-HWMP協議的成功投遞率要高于HWMP。

圖3 數據包投遞成功率

圖4為網絡吞吐量隨著負載增加的變化趨勢。隨著網絡中數據流的增加,網絡吞吐量也隨之增大,當吞吐量達到峰值時,網絡中的數據包沖突的增加將導致網絡吞吐量的下降。從圖4可以看出,改進的協議吞吐量較HWMP協議較高,這一方面是因為CLRM-HWMP降低了網絡中的數據包的沖突,另一方面是因為優化的CLRM路由判據選擇了更優的路徑,使得網絡系統更加高效。

圖4 網絡吞吐量

3 總結

該文分析了傳統的單一度量值的無線Mesh網絡路由HWMP協議和基于跨層的CLRM-HWMP路由協議,通過在平均端到端時延、平均數據包投遞率和網絡吞吐量這3個方面進行仿真分析對比。仿真實驗結果表明該文提出的CLRM-HWMP路由協議較HWMP路由協議有良好的表現。這也充分說明了基于跨層的和多種因素設計的路由協議能夠有效的提升網絡的性能。

[1] 王繼紅,石文孝. 無線Mesh網絡負載與干擾感知傳輸時間路由度量[J]. 吉林大學學報(工學版),2015(1):297-303.

[2] 龍昭華,侯彥強,張林. 基于HWMP協議的路徑選擇判據研究[J]. 計算機工程與設計,2013(3):791-794.

[3] 梁建武,馬曉亮,徐龍龍. 移動Ad Hoc網絡AODV路由協議的研究與優化[J]. 重慶大學學報,2015(4):152-158.

[4] 吳全玉,孫怡寧. 井下無線傳感器網絡AODV和DSDV協議的仿真對比[J]. 傳感技術學報,2009,22(10):1515-1518.

[5] 李楊,劉航,郭達偉,等. 基于跨層快速鄰居感知的OLSR協議[J]. 傳感技術學報,2012,25(1):99-103.

[6] 王福生. 基于無線網狀網的AODV路由協議研究與改進[D]. 長春:吉林大學,2013.

[7] Ding L,Melodia T,Batalama S,et al. ROSA:Distributed Joint Routing and Dynamic Spectrum Allocation in Cognitive Radio Ad Hoc Networks[C]//ACM International Conference on Modeling,Analysis and Simulation of Wireless and Mobile Systems. ACM,2009:13-20.

[8] 任鵬,張劍英,馮小龍. 能耗均衡的煤礦井下巷道WSN跨層路由協議[J]. 煤炭學報,2016(2):522-530.

[9] 肖萍. 一種能量高效的無線Ad Hoc網絡跨層協議的研究[D]. 長春:吉林大學,2011.

[10] 余燕平,倪玲玲,鄭元琰. 無線自組織網絡中帶寬約束的分布式按需組播路由協議(英文)[J]. Journal of Southeast University(English Edition),2015(1):5-11.

[11] 李柏楠,錢葉魁,羅興國. 基于往返時延矩陣子空間的網絡異常檢測方法[J]. 南京理工大學學報,2015,39(2):215-224.

[12] 羅震鈞,張穎江,鐘珞,等. 無線傳感器網絡中基于貝葉斯可變頻的CSMA/CA算法研究[J]. 傳感技術學報,2014,27(9):1269-1274.

[13] 江曉力,陳兵. 一種具有負載均衡功能的多網關路由協議LBMP_HWMP[J]. 小型微型計算機系統,2014,12:2608-2611.

[14] Xu K,Gerla M,Bae S. How Effective is the IEEE802.11 RTS/CTS Handshake in Ad Hoc Networks[C]//Global Telecommunications Conference,2002(1):72-76.

蔣緯昌(1989-),男,河南南陽人,碩士研究生,CCF學生會員,主要研究方向為無線傳感器網絡、無線Mesh網絡,jiangwc_ny@163.com;

龍昭華(1962-),男,貴州遵義人,碩士生導師,教授,CCF會員,主要研究方向為網絡通信與嵌入式系統,longzha@cqupt.edu.cn。

The Research of CLRM-HWMP Routing Protocol Based on Cross-Layer Design

JIANG Weichang,LONG Zhaohua*,HOU Tangjie
(College of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)

Based on the research HWMP routing protocol on the introduction of cross-layer design approach,proposed an integrated cross-layer routing metric routing protocol CLRM-HWMP. Considering the success rate of the data frame transmission DFTE(Data Frame Transmission Efficiency)in data link layer,available bandwidth and the number of hops in network layer as a cross-layer routing metric(Cross-layer Routing Metric,CLRM),this method is effective to solve a single routing metric criterion confined to raise the issue in the wireless Mesh network performance.By NS-3 simulation software for wireless Mesh network routing protocols and HWMP CLRM-HWMP proposed cross-layer routing protocol analysis and comparison of experimental results show that:the proposed CLRM-HWMP routing protocol effectively reduces the end to end delay between nodes,improves the packet delivery success rate and network throughput.

wireless mesh network;routing metric;cross-layer routing metric;HWMP;CLRM-HWMP

2016-06-16 修改日期:2016-12-17

TP393

A

1004-1699(2017)04-0587-05

C:6150P

10.3969/j.issn.1004-1699.2017.04.018