基于擁塞控制的無線路由算法研究

浦倩云，吳錫生

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

?

基于擁塞控制的無線路由算法研究

浦倩云，吳錫生

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

因網絡通信量大而導致的網絡擁塞，是制約網絡性能的主要因素。提出的擁塞控制路由算法(CCRA)根據節點跳數、緩存占用率和緩存占用趨勢的關系，并結合相關函數，得到計算擁塞標志值和鏈路代價的函數，從而得到一種改進的最佳路徑路由算法，同時使用基于備份路由和時間動態設置定時器的局部路由策略調整局部擁塞。仿真結果表明，改進的路由算法，減輕了網絡的擁塞狀態，縮短了網絡的傳輸時延，提高了分組成功投遞率。

無線傳感器網絡；擁塞控制；路由算法；備份路由

0　引　言

無線傳感器網絡中，終端覆蓋范圍有限，兩個相距較遠無法直接通信的節點，可借助其它節點進行分組轉發[1-2]，節點的緩存[3-4]、網絡的拓撲結構及采用的路由協議等，是造成網絡擁塞的主要原因，因而研究一種有效解決無線傳感器網絡擁塞的方法具有重要的意義。文獻[5-6]從拓撲結構方面，分析了導致網絡擁塞的原因，提出通過增加或刪除節點和鏈路來緩解網絡擁塞。該方法的實施會改變拓撲結構，可行性不高。文獻[7-8]采用了多徑路由機制，當網絡擁塞時，將數據包從不同的“下一跳”轉發出去，以緩解網絡擁塞。但此算法在計算鏈路代價時僅考慮了網絡的靜態特征或動態特征，不能保證選路時達到全局最優。目的節點序列距離矢量DSDV(destination sequenced distance vector)算法是一種基于最短路徑優先算法的路由協議，它具有無環路、收斂速度快等特點，但它的算法得到的路徑總是“最優路徑”，導致數據包總是沿著“最優路徑”發送。當網絡中各個最優路徑有部分重疊時，會產生某些鏈路被頻繁使用，以至其負載過大而導致網絡局部擁塞。文獻[9]提出了一種基于加權路由策略的擁塞控制機制，將節點的介數作為節點連接邊的權重，按加權網絡最短路徑路由傳輸數據包。它采用區域中心節點近似估算法計算介數，降低了介數計算的復雜度。文獻[10]提出了一種擁塞預知路由算法(CPRA)，通過周期性檢測隊列緩沖區的占用率(BOR)，來判斷鏈路是否有可能會發生擁塞，當BOR達到某個閾值時，認為鏈路有可能發生擁塞，此時結合局部拓撲結構與鏈路狀態計算備用路由，當BOR達到另一閾值時，啟用備用路由。文獻[9-10]都需計算全局路由表，僅適用于有線網絡。文獻[11] 提出了一種基于BA網絡的局部路由策略，基本思想是在數據包轉發過程中,將鄰居節點的度和發送能力以一定比例加和得到的值作為權值,根據權值大小選擇下一站點，但是只考慮了局部網絡狀態。I-DSDV[12]通過在路由表中增加參數‘type’來標記當前條目是有效還是無效。當節點檢測到鏈路斷裂時，節點先在一跳范圍內廣播并尋找重建鏈路，如果尋找失敗且此時被廣播節點沒有分組要經過該節點發送至對應目的節點，則等待下一周期更新重建路由，否則，立即重播無效的路由信息。Imp-DSDV協議[13]維護且更新一個所有可到達目的節點的備份路由表。當鏈路斷裂時，通過備份路由表，節點可快速找到到達目的節點的有效路由。但是文獻[12-13]都只考慮了鏈路斷裂對網絡性能的影響，沒有考慮到節點擁塞對網絡性能的影響。為解決該不足，本文在研究現有路由算法的基礎上，提出了一種擁塞控制路由算法(CCRA)。該算法根據節點跳數、緩存占用率和緩存占用趨勢的關系，得到一種改進的最佳路徑路由算法，并使用基于備份路由的局部路由策略解決局部擁塞。仿真結果表明，改進的路由算法，減輕了網絡的擁塞狀態，降低了網絡的傳輸時延，同時提高了分組成功投遞率。

1　擁塞控制路由協議隊列模型分析與改進

1.1節點負載

現有無線路由協議在計算路由的過程中，大都以時延和跳數等因素作為計算鏈路代價的依據。由于沒有考慮鏈路和節點的擁塞狀態，導致無法避開擁塞的鏈路和節點，從而導致部分鏈路和節點出現擁塞。如果在路由選擇前能通過擁塞檢測預知到鏈路和節點的擁塞并避開，就能有效減少傳輸過程中的擁塞，提高分組成功投遞率。

一般用節點緩沖區待發送數據包個數與緩沖區最大容量的比值(即緩沖區占用率buffer occupation rate，BOR)來衡量節點的擁塞程度，但緩沖區占用率僅代表某一時刻的占用率，不能準確預測節點將來的擁塞狀態，為此本文使用緩沖區占用率和堆積率一起來度量節點擁塞程度。

定義1：堆積率(accumulation rate，AR)為單位時間進入節點數據包的個數和流出節點數據包個數的差值與緩沖區最大容量的比值。如果堆積率大于或等于0，說明數據包到達的速度大于或等于流出的速度，AR值越大，出現擁塞的可能性越大。

定義2：擁塞度(congestion degree，CD)為預測節點擁塞的度量，其值可用式(1)表示：

CDi(t)=BORi(t)+ARi(t)

(1)

約束條件為：

其中，BORi表示節點i的緩沖區占用率，0

(2)

1.2鏈路代價模型

定義3：鏈路代價(road weight，RW)為轉發數據包所要付出代價的衡量，其值用式(3)表示：

RWij(t)=metricij+CUj×CDj(t)

(3)

式中，RWij為將數據包從節點i轉發到鄰節點j所要付出的代價。

假設源節點到目的節點的路徑表示為P(s→d)=a1,a2,…,an，此路徑的總代價為：

(4)

式中，metricsd為節點s到節點d的跳數。選擇使RWsd(t)值最小的路徑作為更新路由，這樣周期更新路由時即可避開擁塞節點。由式(3)可知，當節點處于空閑階段時公式的第二項為0，路由選擇結果與DSDV相同，當節點出現擁塞時公式的第二項會根據網絡中節點的擁塞狀態確定“最短路徑”，以確保算法始終選擇全局最優路徑。

2　局部擁塞路由策略的改進

當網絡中有節點發生擁塞時，為提高網絡的分組成功投遞率，可以將節點中的數據分流。為此，本文提出一種基于備份路由表的局部擁塞控制路由策略。這需為每個節點創建一張備份路由表，備份路線遵循以下規則：

(1)備份路線有無效和有效兩個狀態。

(2)無效備份路線的跳數為無限大。

(3)有效備份路線的序列號應與相應主路線的序列號相同，而代價應不小于相應主路線的代價，且下一跳應與相應主路線的不同。確保備份路線是無循環的。

(4)起初，所有備份路線都是有效的。

(5)如果接收到的路由更新的序列號與相應主路線的序列號相同，而代價不小于相應主路線的代價，且下一跳與相應主路線的不同，且當其序列號與備份路線的序列號相同，而代價不大于相應備份路線的代價，則相應的備份路線更新。

(6)如果主路線被備份路線代替，則備份路線設為無效。

例如：當節點C的擁塞標志CU大于4時，則進行以下操作：

(1)節點C中有一個來自節點B要轉發到節點D的分組，節點C向節點B發送擁塞信息并設置一個定時器。

(2) 節點B接收到擁塞信息，查詢主路由表并用備份路線代替下一跳節點為節點C目的節點為節點D的主路線。然后將備份路線的跳數設成無限大，將新的主路線的序列號設置為比舊的主路線的序列號大1(奇數序列號)。

(3)如果定時時間到時節點C還處在擁塞狀態，則重復上述步驟。當節點C的擁塞標志CU等于0時，節點C發送以自己為目的節點的更新包。

本文對定時器時間的設置采用動態設置方式。節點隊列被填滿的時間由緩沖區占用率BOR和堆積率AR共同決定，其關系如式(4)所示：

BORi(t+ΔT)=BORi(t)+ARi(t)×ΔT

(5)

式中，BORi(t+ΔT)為節點i在時間間隔ΔT之后緩沖區的占用率，當BORi(t+ΔT)>θ2時，表示在時間間隔ΔT之后節點i的緩沖區會進入CS階段，當BORi(t+ΔT)>1，表示在時間間隔ΔT之后節點i的緩沖區會進入丟包階段。

當節點CU>4時，完成第一次發送擁塞信息之后，根據BOR和AR的值計算定時器檢測的時間間隔，其值如式(6)所示：

(6)

式中，Ti(t)為定時器檢測的時間間隔，(1-BORi(t))是節點緩存區的剩余大小，ARi(t)是節點緩沖區的堆積率。

當節點C檢測到其與鄰節點D之間的鏈路斷裂時，它將作以下操作：

(1)節點C查詢主路由表并用備份路線代替下一跳節點為節點D的任意主路線。然后將備份路線的跳數設成無限大。

(2)節點C將新的主路線的序列號設置為比舊的主路線的序列號大1(奇數序列號)。

(3)節點C廣播主路由表中跳數為無限大或奇數序列號的路線。

每個接收到來自節點C的路由更新包，且包中包含到節點D的跳數為無限大的路線更新的節點，則做以下操作：

如果節點有到節點D的主路線且其下一跳為節點C，則：

(1)用備份路線替代主路線，然后將備份路線的跳數設為無限大。

(2)將新的主路線的序列號設置為比舊的主路線的序列號大1(奇數序列號)。

(3)節點廣播主路由表中跳數為無限大或奇數序列號的路線。

否則

(1)如果節點有到節點D的主路線且它的下一跳不是節點C，則將其序列號設置為比舊的主路線的序列號大1(奇數序列號)。

(2)節點廣播主路由表中跳數為無限大或奇數序列號的路線。

3　擁塞控制路由改進算法描述

根據第2節提出的鏈路代價模型，計算節點發送數據包的全局路由，同時當節點發生擁塞時，用第3節提出的局部擁塞路由控制策略，在節點將擁塞時用備份路線代替主路線，從而得到本文提出的擁塞控制路由算法(Congestion Control Routing Algorithm，CCRA)。CCRA算法的具體過程如下：

輸入：節點集合，閾值θ1、θ2

BEGIN

初始化θ1、θ2

for節點iin nodes、

節點i利用式(4)計算到各個可到達節點目的節點的鏈路代價

end for

while有數據包Packet需要轉發時 do

入隊Packet，查詢節點i的網卡隊列

if (CU==0)

轉發隊列中的數據包

if 上次定時器檢測時CU大于4

發送以節點i為目的節點的路由更新包，序列號加2

if(0

轉發隊列中數據包

if (CU>4)

通知Packet的上一跳節點，啟用備份路由，并設置定時器

end while

END

4　實驗結果及分析

本文使用NS2.35進行實驗。模擬網絡有100個節點隨機分布在1 000×1 000的平面區域。MAC層使用信道帶寬為2 Mb/s的IEEE 802.11 MAC協議。節點傳輸范圍250 m。仿真時間400 s。流動模型使用Random-Waypoint；在此模型中，當仿真開始時每個節點都靜止pause-time秒。然后隨機選擇一個目的地且以一個分布在0～maximum之間的速度勻速向該目的地前進。到達目的地后，再次靜止pause-time秒，然后隨機選擇另一個目的地并按前述方法繼續前進，重復上述行為直至仿真結束。本文的運動模型由9個不同的pause-time：0,50,100,150,200,250,300,350,400和一個最大速度(20 m/s)生成。流量源采用CBR，其數據包大小為512個字節，通信模式采用20個數據源，數據源開始的時間均勻分布在0～5 s之間。

(1)DSDV、文獻[11-12]和本文算法(CCRA)，在源節點每秒發送1個分組(即網絡未擁塞)時的分組成功投遞率平均值和端到端延遲平均值情況如圖1和圖2所示。

圖1　分組成功投遞率隨節點移動率變化曲線(1/s)

圖2　端到端延遲隨節點移動率變化曲線(1/s)

由圖1、圖2可知，當源節點每秒發送1個分組且未擁塞時，文獻[11-12]和本文算法在pause-time≤150時，比DSDV的分組成功投遞率高的多，其后差不多，這是因為前三者都有應對鏈路斷裂的機制；而當pause-time≥200時，由于網絡中節點的移動時間大幅減少而網絡的負載又較小，鏈路斷裂對網絡中數據的傳輸影響大幅減小，且DSDV本身擁有周期更新路由的能力，故而四種比較算法結果接近。而DSDV、文獻[12]和本文算法的端到端的延遲基本一樣，這是因為當鏈路斷裂時，Imp-DSDV和CCRA能根據備份路由表快速找到到達目的節點的有效路線。

(2)DSDV、文獻[11-12]和本文算法(CCRA)在源節點每秒發送10個分組(即網絡擁塞)時的分組成功投遞率平均值和端到端延遲平均值情況如圖3和圖4所示。

圖3　分組成功投遞率隨節點移動率變化曲線(10 /s)

圖4　端到端延遲隨節點移動率變化曲線(10個/s)

由圖3可知，當網絡發生擁塞時，文獻[11-12]比DSDV的表現要好，但是本文算法的表現最好。當pause-time很小時，DSDV同時受到鏈路斷裂和節點擁塞的影響，所以表現很差；而文獻[11-12]減輕了鏈路斷裂的影響，所以表現比DSDV稍好；而本文算法同時減輕了鏈路斷裂和節點擁塞的影響，所以表現最好。隨著pause-time逐漸增大，鏈路斷裂的影響逐漸減小，DSDV、文獻[11-12]的表現逐漸相近；因存在一個周期內每個節點的備用路由只有一個的限制，在網絡非常擁堵的情況下，已啟用過的備份路由無法二次使用，故會影響到最后的分組成功投遞率。但即使如此，因本文算法減輕了擁塞的影響，在本組實驗中仍能將分組成功投遞率提高到65%。仿真結果表明本文算法能減輕網絡的擁塞狀態，減少丟包，提高分組成功投遞率。

由圖4可知，本文算法的端到端延遲比DSDV和文獻[11-12]的小，這是因為當網絡局部發生擁塞時，本文算法采用備份路線轉發分組，減少了分組排隊產生的時延，大大降低了端到端的時延。

(3)在現實情況下，節點移動并不會出現很極端的情況，故本文將DSDV、文獻[11-12]和本文算法(CCRA)在pause-time為350s時的分組成功投遞率平均值進行比較，結果如圖5所示。

圖5　分組成功投遞率隨發送分組數變化曲線

由圖5可知在暫停時間固定為350 s時，DSDV、文獻[11-12]隨著發送分組從1到10增加，分組成功投遞率逐漸降低到近50%，而本文算法可使分組成功投遞率維持在65%以上，說明本文的全局和局部擁塞策略能有效緩解網絡中節點的擁塞，提高分組成功投遞率。

5　結　語

本文結合隊列模型、全局路由策略和局部路由策略三個方面進行研究，針對網絡擁塞問題，提出了擁塞控制路由算法(CCRA)，以克服DSDV的陳舊路由問題并提高節點擁塞時網絡的表現，該算法通過周期性地檢測節點的擁塞程度，并反饋給路由模塊，路由模塊以節點緩沖區的擁塞情況為依據，采用全局和局部路由相結合的策略處理路由。局部路由策略利用備份路由表重建路由，以減少因鏈路斷裂和節點擁塞導致的分組丟失。仿真結果表明，本文算法CCRA能減少因節點擁塞而產生的丟包，提高分組成功投遞率。

[1]TAN S, LI X, DONG Q. Trust based Routing Mechanism for Securing OSLR-based MANET[J]. Ad Hoc Networks,2015,30(1):84-98.

[2]Prabha R, Ramaraj N. An Improved Multipath MANET Routing using Link Estimation and Swarm Intelligence[J]. Eurasip Journal on Wireless Communications & Networking,2015,2015(1)：1-9.

[3]Khan K, Zaman R U, Reddy K A, et al. An Efficient DSDV Routing Protocol for Wireless Mobile Ad Hoc Networks and Its Performance Comparison[C]// Computer Modeling and Simulation,2008. EMS′08. Second UKSIM European Symposium. Liverpool,England,UK:IEEE,2008:506-511.

[4]LIU T, LIU K. Improvements on DSDV in Mobile Ad Hoc Networks[C]//Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference. Shanghai, China: IEEE, 2007:1637-1640.

[5]HUANG W, ZHOU T W S. An Efficient Strategy for Enhancing Traffic Capacity by Removing Links in Scale-Free Networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2010, 2010(4):577-611.

[6]HUANG W, ZHOU T W S. Effective Strategy of Adding Nodes and Links for Maximizing the Traffic Capacity of Scale-Free Network[J]. Chaos,2010,20(3):233-271.

[7]Cevher S, Ulutas M, Hokelek I. Performance Evaluation of Multiple Routing Configurations[C] //In: Proceedings of the 21st Signal Processing and Communications Applications Conference(SIU). Haspolat,Turkey:IEEE,2013:1-4.

[8]CHEN K C, LIN S Y, HUANG H S, et al. Traffic-Balanced Topology-Aware Multiple Routing Adjustment for Throttled 3D NOC Systems[C]//Proceedings of the 2012 IEEE Workshop on Signal Processing Systems. Quebec City,QC,Canada: IEEE Computer Society,2012:120-124.

[9]劉偉彥, 劉斌. 基于加權路由策略的復雜網絡擁塞控制研究[J]. 系統工程理論與實踐, 2015, 4(04):1063-1068.

LIU Wei-yan, LIU Bin. Study on Congestion Control for Complex Network based on Weighted Routing Strategy[J]. Systems Engineering Theory & Practice, 2015, 4(04):1063-1068.

[10]段小龍,郭承青,閆健恩等.基于擁塞預知的路由算法研究[J]. 高技術通訊,2014,11(11):1140-1146.

DUAN Xiao-long,GUO Cheng-qing, YAN Jian-en, et al. Research on a Congestion Perception Routing Algorithm[J]. Chinese High Technology Letters, 2014, 11(11):1140-1146.

[11]孫雅倩, 張達敏, 曾成等.BA網絡中一種基于節點動態權值的局部路由策略[J].通信技術, 2015,48(11):1275-1279.

SUN Ya-qian, ZHANG Da-min, ZENG Cheng, et al. A Local Routing Strategy based on Nodes Dynamic Weights in BA Networks[J]. Communications Technology, 2015, 48(11):1275-1279.

[12]LIU T,LIU K. Improvements on DSDV in Mobile Ad Hoc Networks[C]//Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007. International Conference. Shanghai,China:IEEE,2007:1637-1640.

[13]LU J,ZHANG B,HAN G, et al. A New Improvement on DSDV[C]//Wireless Communications, Networking and Mobile Computing (WiCOM), 2011 7th International Conference. Wuhan,China:IEEE,2011:1-4.

浦倩云(1991—)，女，碩士研究生，主要研究方向為傳感器網絡和控制系統；

吳錫生(1959—)，男，教授, 碩士研究生導師，主要研究方向為圖像處理，模式識別和智能控制。

National Natural Science Foundation of China (No.61103223); Joint Innovation Fund Project of Jiangsu Province (No.BY2013015-35)

Wireless Routing Algorithm based on Congestion Control

PU Qian-yun, WU Xi-sheng

(School of Internet of Things Engineering, Jiangnan University, Wuxi Jiangsu 214122, China)

Network congestion caused by large network traffic is the main factor in restricting network performance. The proposed CCRA (Congestion Control Routing Algorithm), according to the relation of between node hop, cache occupancy and cache occupancy trend, and in combination with the correlation function, obtains the function for calculating the value of congestion flag and link cost, thus acquiring a modified optimal path routing algorithm. Meanwhile, the local routing strategy based on backup routing and timer with dynamic time setting is applied to adjusting the local congestion. Simulation results indicate that the modified routing algorithm could ease the network congestion status,reduce the network transmission delay and improve the packet delivery ratio.

wireless sensor network; congestion control; routing algorithm; backup routing

10.3969/j.issn.1002-0802.2016.03.012

2015-10-16；

2016-02-06Received date:2015-10-16；Revised date：2016-02-06

TP393

A

1002-0802(2016)03-0312-06

國家自然科學基金(No.61103223)；江蘇省產學研聯合創新資金項目(No.BY2013015-35)