基于擁塞控制的無(wú)線路由算法研究

浦倩云，吳錫生

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

?

基于擁塞控制的無(wú)線路由算法研究

浦倩云，吳錫生

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

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

無(wú)線傳感器網(wǎng)絡(luò)；擁塞控制；路由算法；備份路由

0　引　言

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

1　擁塞控制路由協(xié)議隊(duì)列模型分析與改進(jìn)

1.1節(jié)點(diǎn)負(fù)載

現(xiàn)有無(wú)線路由協(xié)議在計(jì)算路由的過(guò)程中，大都以時(shí)延和跳數(shù)等因素作為計(jì)算鏈路代價(jià)的依據(jù)。由于沒(méi)有考慮鏈路和節(jié)點(diǎn)的擁塞狀態(tài)，導(dǎo)致無(wú)法避開(kāi)擁塞的鏈路和節(jié)點(diǎn)，從而導(dǎo)致部分鏈路和節(jié)點(diǎn)出現(xiàn)擁塞。如果在路由選擇前能通過(guò)擁塞檢測(cè)預(yù)知到鏈路和節(jié)點(diǎn)的擁塞并避開(kāi)，就能有效減少傳輸過(guò)程中的擁塞，提高分組成功投遞率。

一般用節(jié)點(diǎn)緩沖區(qū)待發(fā)送數(shù)據(jù)包個(gè)數(shù)與緩沖區(qū)最大容量的比值(即緩沖區(qū)占用率buffer occupation rate，BOR)來(lái)衡量節(jié)點(diǎn)的擁塞程度，但緩沖區(qū)占用率僅代表某一時(shí)刻的占用率，不能準(zhǔn)確預(yù)測(cè)節(jié)點(diǎn)將來(lái)的擁塞狀態(tài)，為此本文使用緩沖區(qū)占用率和堆積率一起來(lái)度量節(jié)點(diǎn)擁塞程度。

定義1：堆積率(accumulation rate，AR)為單位時(shí)間進(jìn)入節(jié)點(diǎn)數(shù)據(jù)包的個(gè)數(shù)和流出節(jié)點(diǎn)數(shù)據(jù)包個(gè)數(shù)的差值與緩沖區(qū)最大容量的比值。如果堆積率大于或等于0，說(shuō)明數(shù)據(jù)包到達(dá)的速度大于或等于流出的速度，AR值越大，出現(xiàn)擁塞的可能性越大。

定義2：擁塞度(congestion degree，CD)為預(yù)測(cè)節(jié)點(diǎn)擁塞的度量，其值可用式(1)表示：

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

(1)

約束條件為：

其中，BORi表示節(jié)點(diǎn)i的緩沖區(qū)占用率，0

(2)

1.2鏈路代價(jià)模型

定義3：鏈路代價(jià)(road weight，RW)為轉(zhuǎn)發(fā)數(shù)據(jù)包所要付出代價(jià)的衡量，其值用式(3)表示：

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

(3)

式中，RWij為將數(shù)據(jù)包從節(jié)點(diǎn)i轉(zhuǎn)發(fā)到鄰節(jié)點(diǎn)j所要付出的代價(jià)。

假設(shè)源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑表示為P(s→d)=a1,a2,…,an，此路徑的總代價(jià)為：

(4)

式中，metricsd為節(jié)點(diǎn)s到節(jié)點(diǎn)d的跳數(shù)。選擇使RWsd(t)值最小的路徑作為更新路由，這樣周期更新路由時(shí)即可避開(kāi)擁塞節(jié)點(diǎn)。由式(3)可知，當(dāng)節(jié)點(diǎn)處于空閑階段時(shí)公式的第二項(xiàng)為0，路由選擇結(jié)果與DSDV相同，當(dāng)節(jié)點(diǎn)出現(xiàn)擁塞時(shí)公式的第二項(xiàng)會(huì)根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的擁塞狀態(tài)確定“最短路徑”，以確保算法始終選擇全局最優(yōu)路徑。

2　局部擁塞路由策略的改進(jìn)

當(dāng)網(wǎng)絡(luò)中有節(jié)點(diǎn)發(fā)生擁塞時(shí)，為提高網(wǎng)絡(luò)的分組成功投遞率，可以將節(jié)點(diǎn)中的數(shù)據(jù)分流。為此，本文提出一種基于備份路由表的局部擁塞控制路由策略。這需為每個(gè)節(jié)點(diǎn)創(chuàng)建一張備份路由表，備份路線遵循以下規(guī)則：

(1)備份路線有無(wú)效和有效兩個(gè)狀態(tài)。

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

(3)有效備份路線的序列號(hào)應(yīng)與相應(yīng)主路線的序列號(hào)相同，而代價(jià)應(yīng)不小于相應(yīng)主路線的代價(jià)，且下一跳應(yīng)與相應(yīng)主路線的不同。確保備份路線是無(wú)循環(huán)的。

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

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

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

例如：當(dāng)節(jié)點(diǎn)C的擁塞標(biāo)志CU大于4時(shí)，則進(jìn)行以下操作：

(1)節(jié)點(diǎn)C中有一個(gè)來(lái)自節(jié)點(diǎn)B要轉(zhuǎn)發(fā)到節(jié)點(diǎn)D的分組，節(jié)點(diǎn)C向節(jié)點(diǎn)B發(fā)送擁塞信息并設(shè)置一個(gè)定時(shí)器。

(2) 節(jié)點(diǎn)B接收到擁塞信息，查詢(xún)主路由表并用備份路線代替下一跳節(jié)點(diǎn)為節(jié)點(diǎn)C目的節(jié)點(diǎn)為節(jié)點(diǎn)D的主路線。然后將備份路線的跳數(shù)設(shè)成無(wú)限大，將新的主路線的序列號(hào)設(shè)置為比舊的主路線的序列號(hào)大1(奇數(shù)序列號(hào))。

(3)如果定時(shí)時(shí)間到時(shí)節(jié)點(diǎn)C還處在擁塞狀態(tài)，則重復(fù)上述步驟。當(dāng)節(jié)點(diǎn)C的擁塞標(biāo)志CU等于0時(shí)，節(jié)點(diǎn)C發(fā)送以自己為目的節(jié)點(diǎn)的更新包。

本文對(duì)定時(shí)器時(shí)間的設(shè)置采用動(dòng)態(tài)設(shè)置方式。節(jié)點(diǎn)隊(duì)列被填滿(mǎn)的時(shí)間由緩沖區(qū)占用率BOR和堆積率AR共同決定，其關(guān)系如式(4)所示：

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

(5)

式中，BORi(t+ΔT)為節(jié)點(diǎn)i在時(shí)間間隔ΔT之后緩沖區(qū)的占用率，當(dāng)BORi(t+ΔT)>θ2時(shí)，表示在時(shí)間間隔ΔT之后節(jié)點(diǎn)i的緩沖區(qū)會(huì)進(jìn)入CS階段，當(dāng)BORi(t+ΔT)>1，表示在時(shí)間間隔ΔT之后節(jié)點(diǎn)i的緩沖區(qū)會(huì)進(jìn)入丟包階段。

當(dāng)節(jié)點(diǎn)CU>4時(shí)，完成第一次發(fā)送擁塞信息之后，根據(jù)BOR和AR的值計(jì)算定時(shí)器檢測(cè)的時(shí)間間隔，其值如式(6)所示：

(6)

式中，Ti(t)為定時(shí)器檢測(cè)的時(shí)間間隔，(1-BORi(t))是節(jié)點(diǎn)緩存區(qū)的剩余大小，ARi(t)是節(jié)點(diǎn)緩沖區(qū)的堆積率。

當(dāng)節(jié)點(diǎn)C檢測(cè)到其與鄰節(jié)點(diǎn)D之間的鏈路斷裂時(shí)，它將作以下操作：

(1)節(jié)點(diǎn)C查詢(xún)主路由表并用備份路線代替下一跳節(jié)點(diǎn)為節(jié)點(diǎn)D的任意主路線。然后將備份路線的跳數(shù)設(shè)成無(wú)限大。

(2)節(jié)點(diǎn)C將新的主路線的序列號(hào)設(shè)置為比舊的主路線的序列號(hào)大1(奇數(shù)序列號(hào))。

(3)節(jié)點(diǎn)C廣播主路由表中跳數(shù)為無(wú)限大或奇數(shù)序列號(hào)的路線。

每個(gè)接收到來(lái)自節(jié)點(diǎn)C的路由更新包，且包中包含到節(jié)點(diǎn)D的跳數(shù)為無(wú)限大的路線更新的節(jié)點(diǎn)，則做以下操作：

如果節(jié)點(diǎn)有到節(jié)點(diǎn)D的主路線且其下一跳為節(jié)點(diǎn)C，則：

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

(2)將新的主路線的序列號(hào)設(shè)置為比舊的主路線的序列號(hào)大1(奇數(shù)序列號(hào))。

(3)節(jié)點(diǎn)廣播主路由表中跳數(shù)為無(wú)限大或奇數(shù)序列號(hào)的路線。

否則

(1)如果節(jié)點(diǎn)有到節(jié)點(diǎn)D的主路線且它的下一跳不是節(jié)點(diǎn)C，則將其序列號(hào)設(shè)置為比舊的主路線的序列號(hào)大1(奇數(shù)序列號(hào))。

(2)節(jié)點(diǎn)廣播主路由表中跳數(shù)為無(wú)限大或奇數(shù)序列號(hào)的路線。

3　擁塞控制路由改進(jìn)算法描述

根據(jù)第2節(jié)提出的鏈路代價(jià)模型，計(jì)算節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的全局路由，同時(shí)當(dāng)節(jié)點(diǎn)發(fā)生擁塞時(shí)，用第3節(jié)提出的局部擁塞路由控制策略，在節(jié)點(diǎn)將擁塞時(shí)用備份路線代替主路線，從而得到本文提出的擁塞控制路由算法(Congestion Control Routing Algorithm，CCRA)。CCRA算法的具體過(guò)程如下：

輸入：節(jié)點(diǎn)集合，閾值θ1、θ2

BEGIN

初始化θ1、θ2

for節(jié)點(diǎn)iin nodes、

節(jié)點(diǎn)i利用式(4)計(jì)算到各個(gè)可到達(dá)節(jié)點(diǎn)目的節(jié)點(diǎn)的鏈路代價(jià)

end for

while有數(shù)據(jù)包Packet需要轉(zhuǎn)發(fā)時(shí) do

入隊(duì)Packet，查詢(xún)節(jié)點(diǎn)i的網(wǎng)卡隊(duì)列

if (CU==0)

轉(zhuǎn)發(fā)隊(duì)列中的數(shù)據(jù)包

if 上次定時(shí)器檢測(cè)時(shí)CU大于4

發(fā)送以節(jié)點(diǎn)i為目的節(jié)點(diǎn)的路由更新包，序列號(hào)加2

if(0

轉(zhuǎn)發(fā)隊(duì)列中數(shù)據(jù)包

if (CU>4)

通知Packet的上一跳節(jié)點(diǎn)，啟用備份路由，并設(shè)置定時(shí)器

end while

END

4　實(shí)驗(yàn)結(jié)果及分析

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

(1)DSDV、文獻(xiàn)[11-12]和本文算法(CCRA)，在源節(jié)點(diǎn)每秒發(fā)送1個(gè)分組(即網(wǎng)絡(luò)未擁塞)時(shí)的分組成功投遞率平均值和端到端延遲平均值情況如圖1和圖2所示。

圖1　分組成功投遞率隨節(jié)點(diǎn)移動(dòng)率變化曲線(1/s)

圖2　端到端延遲隨節(jié)點(diǎn)移動(dòng)率變化曲線(1/s)

由圖1、圖2可知，當(dāng)源節(jié)點(diǎn)每秒發(fā)送1個(gè)分組且未擁塞時(shí)，文獻(xiàn)[11-12]和本文算法在pause-time≤150時(shí)，比DSDV的分組成功投遞率高的多，其后差不多，這是因?yàn)榍叭叨加袘?yīng)對(duì)鏈路斷裂的機(jī)制；而當(dāng)pause-time≥200時(shí)，由于網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)時(shí)間大幅減少而網(wǎng)絡(luò)的負(fù)載又較小，鏈路斷裂對(duì)網(wǎng)絡(luò)中數(shù)據(jù)的傳輸影響大幅減小，且DSDV本身?yè)碛兄芷诟侣酚傻哪芰?，故而四種比較算法結(jié)果接近。而DSDV、文獻(xiàn)[12]和本文算法的端到端的延遲基本一樣，這是因?yàn)楫?dāng)鏈路斷裂時(shí)，Imp-DSDV和CCRA能根據(jù)備份路由表快速找到到達(dá)目的節(jié)點(diǎn)的有效路線。

(2)DSDV、文獻(xiàn)[11-12]和本文算法(CCRA)在源節(jié)點(diǎn)每秒發(fā)送10個(gè)分組(即網(wǎng)絡(luò)擁塞)時(shí)的分組成功投遞率平均值和端到端延遲平均值情況如圖3和圖4所示。

圖3　分組成功投遞率隨節(jié)點(diǎn)移動(dòng)率變化曲線(10 /s)

圖4　端到端延遲隨節(jié)點(diǎn)移動(dòng)率變化曲線(10個(gè)/s)

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

由圖4可知，本文算法的端到端延遲比DSDV和文獻(xiàn)[11-12]的小，這是因?yàn)楫?dāng)網(wǎng)絡(luò)局部發(fā)生擁塞時(shí)，本文算法采用備份路線轉(zhuǎn)發(fā)分組，減少了分組排隊(duì)產(chǎn)生的時(shí)延，大大降低了端到端的時(shí)延。

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

圖5　分組成功投遞率隨發(fā)送分組數(shù)變化曲線

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

5　結(jié)　語(yǔ)

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

[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]劉偉彥, 劉斌. 基于加權(quán)路由策略的復(fù)雜網(wǎng)絡(luò)擁塞控制研究[J]. 系統(tǒng)工程理論與實(shí)踐, 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]段小龍,郭承青,閆健恩等.基于擁塞預(yù)知的路由算法研究[J]. 高技術(shù)通訊,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]孫雅倩, 張達(dá)敏, 曾成等.BA網(wǎng)絡(luò)中一種基于節(jié)點(diǎn)動(dòng)態(tài)權(quán)值的局部路由策略[J].通信技術(shù), 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—)，女，碩士研究生，主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)和控制系統(tǒng)；

吳錫生(1959—)，男，教授, 碩士研究生導(dǎo)師，主要研究方向?yàn)閳D像處理，模式識(shí)別和智能控制。

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

國(guó)家自然科學(xué)基金(No.61103223)；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金項(xiàng)目(No.BY2013015-35)