適用于WSNs的擁塞自適應多徑路由算法

施利利, 盧先領

(江南大學 物聯網工程學院,江蘇 無錫 214122)

適用于WSNs的擁塞自適應多徑路由算法

施利利, 盧先領

(江南大學 物聯網工程學院,江蘇 無錫 214122)

針對無線傳感器網絡(WSNs)數據匯聚特性易導致網絡擁塞的問題，結合改進AOMDV協議的多徑建立、選擇機制的缺陷，提出一種擁塞自適應的多徑路由算法。新協議首先引入相關因子模型建立相互干擾度最小的路徑集；其次建立路徑擁塞信息采集、更新機制，并利用HELLO消息傳遞。最終源節點通過實時感知路徑擁塞信息，自適應選擇低擁塞路徑來避免擁塞。仿真結果表明：改進的協議顯著提高了分組投遞速率，降低了端對端時延。

無線傳感器網絡； 擁塞避免； 多徑路由； 相互干擾度

0 引 言

在無線傳感器網絡(WSNs)中，多對一匯聚的傳輸方式導致網絡極易產生擁塞[1]。提高網絡資源利用率的同時盡量避免擁塞一直是網絡設計者追求的目標之一。因此，研究具有擁塞控制功能的路由協議具有重要意義。與單徑路由相比，多徑路由能平衡網絡負載，減少網絡擁塞，提高網絡整體性能。但傳統的多徑路由通常只使用主路徑發送分組，僅當主路徑失效時才啟用備份路由。這種路由選擇機制不僅沒有充分發揮出備份路徑的作用，且易導致備份路徑的過時失效；同時，多徑的建立過程沒有考慮降低路徑之間的干擾，在某一時刻，多條路徑同時處于擁塞區域的概率就增大。

國內外針對現有多徑路由協議不足的研究中，提出了大量的改進方案。在路由發現方面，文獻[2]通過監聽信道忙和閑的比例來判斷節點的擁塞，并以此作為是否繼續廣播RREQ消息的依據來實現網絡的負載均衡。ZD-AOMDV[3]考慮多徑路由之間干擾嚴重，提出建立區域不相交路徑機制來降低路徑之間的相互影響。MAOMDV-LB[4]根據緩存隊列長度來判別是否允許路由經過該節點，以均衡網絡中節點的負載。在路由選擇方面，文獻[5]選擇剩余能量最多的路徑進行分組傳遞，以實現能耗均衡。文獻[6,7]基于接收信號強度指示值選擇路徑，降低了因路由失效引發的路由發現頻率。文獻[8]指出因擁塞導致大量數據包的丟失和重傳不僅浪費節點的能量，而且導致更高的端對端延時和數據包丟失。而上述改進方案很少以此為出發點。

為了減輕WSNs中的網絡擁塞，本文對AOMDV的路由發現和路由選擇機制做出改進，提出了一種擁塞自適應的多徑路由算法。新算法最多只允許源節點維護3條可用路徑，以此來降低一定量的路由開銷；其次，當網絡產生局部擁塞時，源節點能避開擁塞區域選擇低擁塞區域路徑來減輕網絡擁塞。

1 AOMDV協議概述

AOMDV[9]協議旨在發現多條無回環、不相交路徑，當

源節點需要發送數據且無可用路由時，廣播RREQ消息啟動路由發現機制。由于RREQ以泛洪方式傳播，每個中間節點會收到多個相同的RREQ消息副本。AOMDV充分利用這些RREQ消息，檢查每一個接收到的RREQ消息來建立可利用的反向路徑。同時，利用源節點序列號和廣播跳數保證路徑無回環和不相交，規則偽碼如下：

if(本地目地序列號

更新序列號，清空路由列表，建立新的反向路徑；

}

else if((本地目地序列號=RREQ消息節點序列號)

and(本地廣播跳數>RREQ廣播跳數)){

選擇具有最小跳數的路徑插入路徑列表。

}

當中間節點建立起反向路徑之后，檢查是否有到達目的節點的前向路徑；如果存在，則生成RREP消息，并沿著反向路徑發送給源節點，同時建立起對應的前向路徑。當目的節點接收到了RREQ消息，首先同樣建立起反向路徑，但與中間節點不同的是，目的節點對所有鄰居節點發送過來的RREQ消息都會產生一次RREP路由回復消息。中間節點在收到RREP消息之后，若是檢查并選擇未被利用的反向路徑對應的節點作為RREP下一跳傳輸對象，則生成鏈路不相交路徑；若是只允許節點轉發一次RREP消息，則生成節點不相交路徑。

2 自適應多徑路由算法

2.1 算法原理

AOMDV協議可建立鏈路不相交或節點不相交路徑，但沒有考慮降低這些路徑間的干擾性。為此，首先引入相關因子模型來建立低干擾度的多路徑，同時為了降低路由維護的開銷，只保留1條主路徑和最多2條備份路徑。其次，改進AOMDV路由選擇機制，把路徑上節點擁塞度的最大值作為本路徑擁塞值，并利用HELLO消息周期性廣播機制，傳遞、更新路徑的擁塞值信息。最終源節點會收到實時的路徑擁塞值，并以此來自適應選擇路由。規則偽碼如下：

if(沒有到達目的節點的路由)

啟動路由發現過程；}∥和AOMDV協議相同

if(存在單條路徑到達目的)

{選擇該路徑傳輸數據；}

else{

if(主路徑不擁塞)

{選擇主路徑傳輸數據；}

else if(存在不擁塞的備份路徑)

{選擇低擁塞的備份路徑傳輸數據；}

else{選擇主路徑傳輸數據；

}

為實現上述自適應多徑路由算法需對路由表和RREP數據包進行相應的擴展。在路徑列表中添加cr和cg域，其中,cr存儲路徑相關因子值，cg存儲路徑擁塞值。在RREP分組中添加rp_f位和rp_cr,rp_cg字段。rp_f為主路徑標志位，當目的節點進行第一次回復RREP消息，就對此RREP消息rp_f位置1，表示該路徑為主路徑。rp_cr記錄路徑相關因子值。rp_cg記錄路徑擁塞信息并通過HELLO消息傳遞，但HELLO消息即是跳數為1的特殊RREP消息，所以,也在這里添加。

2.2 多徑建立

2.2.1 相關因子模型

在無線網絡中，所有節點共享同一無線信道，不同路徑之間存在相互干擾。如圖1(a)中的路徑S-A-B-D和S-E-F-D，當A向B傳輸數據時，由于F在A的傳輸范圍內，F也能收到此數據分組。因此，在A向B發送數據的過程中，F如果要發送或接收數據(非A發送)，都會發送沖突，導致A和E的動作都失敗。因此，即使是節點不相交路徑，路徑之間也可能存在干擾。為了量化地描述出路徑之間的干擾程度，引入相關因子[10]：

定義1 2條節點不相交路徑的相關因子C：由2條節點不相交路徑中的節點組成的拓撲圖中，相關因子就是2個端點分屬于2條節點不相交路徑的邊的條數。

如圖1(a)中的2條路徑S-A-B-D和S-E-F-D，其中有4條鏈路：(A，E),(A,F),(B,E)和(B,F)，它們有一個共同點：一個節點在路徑S-A-B-D上，一個節點在路徑S-E-F-D上，因此,這2條節點不相交路徑的相關因子就為4。而圖1(b)無分屬上述2條路徑的邊，因此,相關因子為0。顯然,相關因子越大，路徑之間的干擾就越大。因此，路徑之間的相關因子值越小，其干擾也就越小。

圖1 節點不相交路徑的相關因子Fig 1 Relevant factor of node-disjoin paths

2.2.2 低干擾度路徑建立

在AOMDV路由回復階段，RREP消息從目的節點沿反向路由進行傳遞，其他無關鄰居節點不會參與轉發RREP消息。因此，選擇RREP消息的個數作為相關因子的參數。為了節約能量，除產生網絡擁塞，其他情況選擇最短路徑來進行數據傳輸。因此,通過延時回復RREP消息策略來確保對最短路徑優先回復，并以該路徑為參照，找出與之干擾較小的備份路徑。協議路由發現過程，如圖2。

圖2 路由建立過程Fig 2 Establish process of routing

1)當源節點需發送數據且無可用路由時，發起路由請求，RREQ消息向目的節點擴散，并建立起反向路由(該過程與原AOMDV協議相同),如圖2(a)，(b)。

2)在目的節點接收到第一個RREQ請求消息后延時t秒,以確保收到足夠多的鄰居節點RREQ消息。同時為了避免建立過長的路徑，必須保證t值不能太大。

3)選擇最短跳數路徑優先回復RREP消息，并將rp_f置1。如圖2(b),(c)，選擇路徑d3進行優先回復，圖中標記為RREP_1。

4)依次對其他路徑進行RREP回復，并在路由回復過程中，計算對應路徑上節點接收到RREP_1消息個數的總和，作為本路徑與最優路徑的相關因子值。如圖2(c)節點E,F都檢測到了節點G的RREP_1消息。

5)選擇相關因子值最小的2條路徑作為備份路徑,如圖2(d)，選擇S-G-D為主路徑，S-A-B-C-D和S-H-I-J-D為備份路徑。

2.3 路徑擁塞判定與更新規則

2.3.1 擁塞判定規則

當一條路徑上某個節點產生了擁塞，就說明該路徑產生了擁塞。檢測擁塞的最簡單方法就是監視節點緩存隊列長度，考慮在WSNs中，頻繁的短時數據流造成即時隊列長度的震蕩，使用平均隊列長度來代替，即

queue_sizeave(n+1)=w×queue_sizeave(n)+(1-w)queue_size(n+1).

(1)

其中， queue_size(n)為第n次迭代時節點隊列長度，w為權值系數。w越大，平均隊列長度越能反應當前隊列的變化；反之，對當前隊列反應越不敏感。但此方法不能準確地指示WSNs的擁塞。因此，結合信道繁忙比率cb[11]來聯合檢測，cb的計算公式如下

(2)

其中，pi為空閑的退避時間的概率，ps為一次成功傳輸的概率，pc為在同一退避時間內2次并發傳輸的概率，Ts為一次成功傳輸的平均時間，Tcol為產生碰撞的平均時間，σ為空閑退避時間的長度。

信道繁忙比率是指在時間間隔內，信道因為成功傳輸數據或者碰撞引起的忙碌狀態時間與總時間的比值，可對網絡擁塞提供早期的預警。對于不同的網絡場景和活動的節點的數量來說，最優的信道利用率幾乎相同，一般為95 %[8]。設置信道利用率閾值Bth，當cbBth時，則認為信道被過度利用。

基于上述分析，節點擁塞判定規則如下：

If((cb>Bth‖(cq>Qth))

{cg=0xFFFF}∥節點產生擁塞

else{cg=queue_sizeave}∥節點無擁塞

其中，cq=queue_sizeave/queue_s,queue_s為節點總隊列大小，cq為隊列占用比，Qth為隊列占用閾值。

路徑擁塞判定規則：只要該路徑上的任一節點產生擁塞，即判定該路徑擁塞。

2.3.2 路徑擁塞更新規則

活動路由中節點會周期性的發送HELLO消息，每個節點在發送HELLO消息之前更新自己的擁塞值，并將更新的路徑擁塞值添加到HELLO消息的rp_cg域中。對于每個節點發送的HELLO消息，其所有鄰居節點都能接收到，為了不干擾到其他路徑的擁塞信息，規定在所有接收HELLO消息的鄰居節點中，只有以HELLO消息源節點為路由下一跳的節點才會對應更新其路徑擁塞信息，其他鄰居節點則視其為單純的HELLO消息。當節點接收到新的路徑擁塞信息，就更新對應的路徑擁塞值，并在節點準備廣播HELLO消息之前，檢測本節點的擁塞度并與收到的最新路徑擁塞值進行比較，選出較大值作為本輪最終的路徑擁塞值。

3 仿真與分析

3.1 仿真環境

主要仿真參數：拓撲大小為1 000m×1 000m；仿真時間為300s；節點數為50個；CBR對數為5，10，15，20，25；發送速度為5包/s；MAC層協議為IEEE802.11；仿真模型為Random-Way-Point。

利用NS2.34軟模擬了一個有50個節點的網絡，節點隨機分布在1000m×1000m的區域中，每個節點的最大傳輸范圍為250m。為了驗證協議運行參數隊列占用閾值Qth和隊列權值系數w對網絡性能的影響，實驗首先對參數Qth和w分別取值，觀察2個參數的變化對網絡丟包率和端對端時延的影響。其次，通過改變隨機產生的CBR連接對數來模擬不同擁塞度的網絡場景，與AOMDV協議在分組投遞率和平均端對端延時性能上進行了比較。其中CBR連接的源節點為隨機選擇，但目的節點始終是Sink節點。為了降低其他因素對擁塞度的影響，規定發送速率恒為5包/s，每個數據包大小為512bytes。

3.2 仿真結果分析

1)設定CBR連接對數為15，觀察參數Qth和w對網絡性能的影響，如圖3、圖4所示。當將w固定，且Qth設置過小時，節點只能存儲短隊列數據，盡管端對端延時較小，但導致丟包率很大；隨著Qth的增大，節點丟包率降低，但超過一定值后，丟包率又開始增大，這是由于長隊列及對無線信道的競爭導致數據包容易產生延時丟包，并導致端對端延時也迅速提高。參數w的變化，對感應網絡擁塞的靈敏度影響很大。對當w設置過小，如w=0.002時，節點對網絡擁塞度的反應不靈敏，導致節點隊列緩存易處于滿隊列狀態，端對端延時時間增長。但w設置也不能過大，如當w=0.02時，節點對網絡擁塞度過于靈敏，使節點很容易處于擁塞狀態，尤其當隊列占用閾值越小時，節點對分組數據存儲能力越弱，導致大量分組數據被直接丟棄。通過多次實驗比較得出，當隊列占用閾值設為總隊列長度的75 %，且w= 0.01時，改進的算法能較好地降低丟包率，減少端對端時延。

圖3 網絡丟包率比較Fig 3 Comparison of network packets loss

圖4 端對端時延比較Fig 4 Comparison of end-to-end delay

2)改進協議的2個參數分別設為：Qth=75 %，w=0.01，結果如圖5、圖6所示。從圖中可以看出:隨著CBR連接對的增加，二種協議的分組投遞率都隨之下降，平均端對端時延增大。這是由于CBR連接對的增加使信道競爭變的激烈并導致網絡產生了擁塞。改進后協議在網絡產生擁塞時獲得了較高的分組投遞率和較低的端對端時延，這是因為在改進后的協議中源節點一旦檢測到主路徑產生擁塞，選擇了低擁塞的備份路徑來避免網絡擁塞。同時當CBR連接對大于20時，改進后協議性能也迅速下降，此時網絡負荷已經大于網絡最大的吞吐能力，因此，通過單純的流量調度已不能解決問題，此時必須通過降低源節點速率或者進行分組丟棄來控制擁塞。

圖5 分組投遞率比較Fig 5 Comparison of grouping delivery ratio

圖6 端對端時延比較Fig 6 Comparison of end-to-end delay

4 結 論

針對WSNs的匯聚特性易引發網絡擁塞，提出了一種擁塞自適應的多徑路由算法。改進算法保留了原AOMDV協議的優點，同時充分考慮了無線鏈路的干擾特性，建立起相互干擾最小的多徑集，并利用HELLO消息傳遞更新路徑擁塞信息，最終通過選擇低擁塞路徑進行數據傳輸來提升網絡的性能。仿真的結果也表明:改進的協議在網絡產生局部擁塞時，能有效地通過選擇低擁塞區域路徑來減輕網絡擁塞，同時提高了網絡分組投遞率、減少了網絡時延。

[1] 孫利民,周新運.無線傳感器網絡的擁塞控制技術[J].計算機研究與發展,2008,45(1):3-72.

[2] Wannawilai P,Sathitwiriyawong C.AOMDV with sufficient bandwidth aware[C]∥2010 IEEE 10 th International Conference on Computer and Information Technology(CIT)：IEEE,2010:305-312.

[3] Javan N T,Kiaeifar R,Hakhamaneshi B,et al.ZD-AOMDV:A new routing algorithm for mobile Ad-Hoc networks[C]∥Eighth IEEE/ACIS International Conference on Computer and Information Science,ICIS 2009:IEEE,2009:852-857.

[4] Narayan D G,Nivedita R,Kiran S,et al.Congestion adaptive multipath routing protocol for multi-radio wreless mesh network-s[C]∥2012 International Conference on Radar, Communication and Computing(ICRCC):IEEE,2012:72-76.

[5] Sharma S,Agarwal P,Jena S K.Energy aware multipath routing protocol for wireless sensor networks[M]∥Computer Networks & Communications(NetCom).New York:Springer,2013:753-760.

[6] Mallapur S V,Terdal S.Enhanced Ad Hoc on demand multipath distance vector routing protocol[J].International Journal of Computer Science and Information Security,2010,7(3):166-170.

[7] Chintawar A,Chatterjee M,Vidhate A.AOMDV-APLP:An enhanced algorithm with accessibility and link breakage predic-tion[C]∥Proceedings of the International Conference & Workshop on Emerging Trends in Technology,ACM,2011:841-845.

[8] Hsu Y P,Feng K T.Cross-layer routing for congestion control in wireless sensor networks[C]∥Radio and Wireless Symposium,IEEE,2008:783-786.

[9] Periyasamy P,Karthikeyan E.Performance evaluation of AOMDV protocol based on various scenario and traffic patterns[J].International Journal of Computer Science,Engineering and Applications(IJCSEA),2012,1(6):33-48.

[10] Wu K,Harms J.Performance study of a multipath routing method for wireless mobile Ad Hoc networks[C]∥Proceedings of Ninth International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems,IEEE,2001:99-107.

[11] Zhai H,Chen X,Fang Y.Improving transport layer performance in multihop Ad Hoc networks by exploiting MAC layer informa-tion[J].IEEE Transactions on Wireless Communications,2007,6(5):1692-1701.

Congestion adaptive multipath routing algorithm for WSNs

SHI Li-li, LU Xian-ling

(College of Internet of Things,Jiangnan University,Wuxi 214122,China)

Aiming at problem that wireless sensor networks(WSNs)data gathering features easy lead to network congestion,a congestion adaptive multipath routing algorithm is proposed,combined with improving defect of mechanism of multipath establish and selection of AOMDV.Firstly,relevant factor mode is introduced in the new agreement to build a path set with minimal mutual interference；secondly,establish path congestion information collection,update mechanism,and use the HELLO message to transmit.Eventually source node adaptively selects the lower congestion path to avoid congestion by real-time sense path congestion information.Simulation results show that the improved protocol can effectively improve packet delivery and reduce end-to-end delay.

WSNs; congestion avoidance; multipath routing; mutual interference

10.13873/J.1000—9787(2014)08—0141—04

2014—01—13

TP 393

A

1000—9787(2014)08—0141—04

施利利(1989-),男,江蘇啟東人,碩士研究生,主要研究方向為無線傳感器網絡擁塞控制。