溫懷玉，霍偉東

?

無線傳感器網(wǎng)絡(luò)流量重分配擁塞控制算法

溫懷玉1,2，霍偉東2

(1. 成都大學(xué)信息科學(xué)與工程學(xué)院 成都 610106; 2. 西南財經(jīng)大學(xué)經(jīng)濟信息工程學(xué)院 成都 610074)

基于流量分配與重分配的算法，提出了一種改進(jìn)的擁塞流量分配(ECOTA)和有效的擁塞檢測和緩解(ECODEM)算法。在衡量了所有路徑的能耗與傳輸延遲之后，選出若干條能耗低、延時短的路徑，增加了數(shù)據(jù)傳輸?shù)某晒β?。通過設(shè)定閾值與預(yù)測的方法對網(wǎng)絡(luò)中的擁塞區(qū)域進(jìn)行檢測，一旦擁塞發(fā)生，采用合理重分配流量的方式，使節(jié)點能夠更快地從擁塞狀況中恢復(fù)出來，并保證擁塞區(qū)域的數(shù)據(jù)能盡快被轉(zhuǎn)移到非擁塞區(qū)域。仿真結(jié)果表明，與其他算法相比，該算法能夠提高分組成功遞交率，降低端到端延時，提升網(wǎng)絡(luò)的整體性能。

擁塞控制; 數(shù)據(jù)轉(zhuǎn)移; 量重分配; 無線傳感器網(wǎng)絡(luò)

無線傳感器網(wǎng)絡(luò)不僅可應(yīng)用于軍事、環(huán)境、生態(tài)監(jiān)測、地震和火災(zāi)等突發(fā)災(zāi)難現(xiàn)場的監(jiān)控，而且可以應(yīng)用于醫(yī)療系統(tǒng)、交通和監(jiān)控等場景[1]。傳感器節(jié)點分布密集、范圍廣泛、鏈路質(zhì)量受環(huán)境影響很大，節(jié)點位置的變化或應(yīng)用數(shù)據(jù)的異常都可能造成擁塞。擁塞會降低網(wǎng)絡(luò)的質(zhì)量，增加端到端的延時，造成數(shù)據(jù)丟失或服務(wù)響應(yīng)時間過長，同時嚴(yán)重地浪費網(wǎng)絡(luò)的帶寬。由于傳感器節(jié)點會不間斷地進(jìn)入到休眠狀態(tài)，因此網(wǎng)絡(luò)結(jié)構(gòu)會不斷地變化，同時節(jié)點由于體積小，其存儲能力、計算能力及能量都是非常有限的，擁塞會極度地消耗這些有限的資源。所以使用擁塞檢測技術(shù)可盡早發(fā)現(xiàn)網(wǎng)絡(luò)中潛在的擁塞現(xiàn)象，提高網(wǎng)絡(luò)的服務(wù)質(zhì)量(QoS)，設(shè)計擁塞檢測和避免的策略使網(wǎng)絡(luò)盡快恢復(fù)到正常的工作狀態(tài)，成為了當(dāng)今的研究熱點[2-3]。

1 相關(guān)工作介紹

無線傳感器的擁塞分為節(jié)點級的擁塞和鏈路級的擁塞。其中節(jié)點級擁塞是指節(jié)點需要發(fā)送的數(shù)據(jù)包超過了自己的緩存能力，因此新到的分組會被丟棄，而且排隊分組的響應(yīng)時間明顯加長。鏈路級擁塞主要指信道共享，多個相鄰的節(jié)點同時使用同一條無線信道發(fā)送數(shù)據(jù)，此時會發(fā)生鏈路級擁塞，導(dǎo)致節(jié)點發(fā)送數(shù)據(jù)丟失，降低網(wǎng)絡(luò)整體的吞吐量，同時鏈路的使用率也會下降。

在擁塞檢測方面，文獻(xiàn)[4-7]采用判斷節(jié)點內(nèi)部數(shù)據(jù)隊列長度來判斷網(wǎng)絡(luò)的擁塞狀況，設(shè)定一個上限閾值，如果分組的緩存長度超過這個值那么就判定發(fā)生了擁塞，但是這類方法的缺點是閾值的大小不好把握，過大的閾值將會導(dǎo)致?lián)砣F(xiàn)象難以及時發(fā)現(xiàn)，導(dǎo)致網(wǎng)絡(luò)資源的浪費。同時也有基于信道的采樣檢測方式，擁塞發(fā)生的時候，擁塞區(qū)域內(nèi)的無線信道由于不同節(jié)點的競爭使用會呈現(xiàn)擁塞狀態(tài)。文獻(xiàn)[8]專門針對分簇的網(wǎng)絡(luò)來檢測擁塞，簇頭節(jié)點實時檢測簇內(nèi)的流量情況，并計算出簇里的節(jié)點緩存溢出的概率從而可計算出一個簇是否發(fā)生了擁塞，但是該方法需要底層通信協(xié)議的支持，以及增加節(jié)點能量的消耗。文獻(xiàn)[4]使用sink節(jié)點接受傳感器節(jié)點分組的速率來判斷網(wǎng)絡(luò)擁塞情況，但缺點是應(yīng)用的場景比較局限，只適用于周期性數(shù)據(jù)網(wǎng)絡(luò)，且檢測周期較長。

在擁塞避免方面，常用的方法是控制節(jié)點的發(fā)送速率，通過速率分配或者緩存通告來實現(xiàn)速率的控制。速率分配機制應(yīng)用于網(wǎng)絡(luò)結(jié)構(gòu)比較穩(wěn)定的網(wǎng)絡(luò)，網(wǎng)絡(luò)中每個節(jié)點的數(shù)據(jù)產(chǎn)生速率和發(fā)送速率都是嚴(yán)格分配計算的，使得網(wǎng)絡(luò)任何節(jié)點的數(shù)據(jù)產(chǎn)生速率和子節(jié)點的數(shù)據(jù)發(fā)送速率小于給節(jié)點分配的發(fā)送速率，從而網(wǎng)絡(luò)中的每一個局部區(qū)域內(nèi)的吞吐量高于其網(wǎng)絡(luò)流量。文獻(xiàn)[9]提出的擁塞避免機制使用了輕量級緩存管理，發(fā)送節(jié)點接收目標(biāo)節(jié)點的緩存信息，只有目標(biāo)節(jié)點有足夠的緩存來容納要接收的數(shù)據(jù)時，發(fā)送節(jié)點才會主動去發(fā)送數(shù)據(jù)，這樣防止路徑中間的節(jié)點因為緩存不夠而造成擁塞。文獻(xiàn)[10]在文獻(xiàn)[9]的基礎(chǔ)上增加了節(jié)點節(jié)能的功能。IPD[11]通過隊列的長度來檢測，當(dāng)分組的內(nèi)部排隊時間大于分組的內(nèi)部處理時間，隊列就會增加，通過隊列長度來計算緩存的占用率。當(dāng)檢測到擁塞發(fā)生時，IPD先計算分組的優(yōu)先級，根據(jù)優(yōu)先級丟棄一定的分組來達(dá)到分析和控制擁塞的目的。無線傳感器網(wǎng)絡(luò)是事件驅(qū)動的網(wǎng)絡(luò)，由于擁塞會影響可靠性和負(fù)載均衡，擁塞控制經(jīng)常會結(jié)合到路由算法中[12-14]。然而這些算法大都是基于緩存因子來進(jìn)行擁塞判斷與避免，而在傳感器網(wǎng)絡(luò)中需要考慮延時、節(jié)點能量等眾多因素，而且算法采用丟棄分組的辦法來控制擁塞會減少源數(shù)據(jù)采集量從而犧牲了數(shù)據(jù)的精度。

在擁塞解除方面，速率控制是最常見手段，當(dāng)系統(tǒng)檢測出擁塞發(fā)生時，中間節(jié)點降低數(shù)據(jù)發(fā)送速率，抑制了擁塞向下游擴散，并向上游節(jié)點發(fā)送擁塞發(fā)生的情況，上游節(jié)點可根據(jù)自己的狀態(tài)調(diào)節(jié)數(shù)據(jù)發(fā)送速率或者去進(jìn)一步轉(zhuǎn)發(fā)通告消息。TADR[15]采用了空閑或者空載的節(jié)點來緩解擁塞，通過在擁塞區(qū)域周圍的空閑節(jié)點的路由路徑來傳播分組，算法設(shè)計通過深度和隊列長度構(gòu)造一個混合虛擬的勢場來繞開擁塞造成的網(wǎng)絡(luò)擁堵最終到達(dá)目標(biāo)節(jié)點。COTA[16]采用了基于路徑的啟發(fā)式信息分配流量，避免給熱點區(qū)域增加負(fù)荷。但是其建立的路徑中存在節(jié)點重復(fù)使用的情況，而且沒有涉及到網(wǎng)絡(luò)中數(shù)據(jù)延遲的現(xiàn)象，同時也沒有考慮在分配過程中可能引起的分配流量的波動情況。

針對目前算法存在的不足，本文提出了一種改進(jìn)的擁塞流量分配算法(ECOTA)，在分配中避免了路徑中由于網(wǎng)絡(luò)擁塞造成的延遲波動；還提出了一種有效的擁塞檢測和緩解算法(ECODEM)，在網(wǎng)絡(luò)中出現(xiàn)擁塞情況下能夠?qū)砣麉^(qū)域的流量分配到非擁塞區(qū)域，同時保證網(wǎng)絡(luò)中的傳輸延遲最小，合理的利用網(wǎng)絡(luò)中節(jié)點的能量。

2 擁塞流量分配算法

本文提出的改進(jìn)型流量分配算法ECOTA，在對路徑進(jìn)行流量分配的基礎(chǔ)上，減少了網(wǎng)絡(luò)中的延遲。ECOTA創(chuàng)建的路徑除了源節(jié)點與目標(biāo)節(jié)點外，其余的節(jié)點均不相同。在傳輸路徑中，多條路徑的重合節(jié)點最有可能因為自身的緩存溢出造成路徑中的數(shù)據(jù)包丟棄而引起網(wǎng)絡(luò)擁塞，而ECOTA采用無重復(fù)多路徑的方法可避免因為幾個節(jié)點造成的網(wǎng)絡(luò)擁塞現(xiàn)象。

由于無線網(wǎng)絡(luò)自身的因素，導(dǎo)致在數(shù)據(jù)傳輸?shù)倪^程中會出現(xiàn)信道失敗的情況。針對這種情況，普遍的解決方法是采用建立多條路徑的方式來傳輸數(shù)據(jù)以增加數(shù)據(jù)傳輸?shù)目煽啃?。假設(shè)信道失敗率為，從源到目標(biāo)的平均跳數(shù)為，為達(dá)到期望的可靠性，至少要建立的路徑數(shù)目為：

當(dāng)路徑的數(shù)目小于時，其中的一些路徑就要分擔(dān)更多的任務(wù)，重復(fù)傳輸數(shù)據(jù)。但如果路徑的數(shù)目大于，則采用后續(xù)文章中的算法，從這些路徑中挑選條路徑來進(jìn)行傳輸，在傳輸?shù)倪^程中避免了擁塞的發(fā)生以及合理控制網(wǎng)絡(luò)中節(jié)點的剩余能量，解決在傳輸過程中的延遲問題。

在路徑建立的初期，先采用RTT(round time of trip)來計算路徑的往返時間，用RTT作為唯一的外部指示，從而實現(xiàn)總流量在條路徑上的動態(tài)分配功能。為了防止RTT的波動而引起流量分配的震蕩，所以采用下式對RTT進(jìn)行調(diào)整：

計算得出每一條路徑中的分配權(quán)重。最后路徑上的分配速率為：

則該條路徑上分配的流量為：

式中，是數(shù)據(jù)源的數(shù)據(jù)發(fā)送率；一共構(gòu)建的路徑數(shù)量為；算法復(fù)雜度為()。

ECOTA算法

Begin

End For

If≥

End If

End

3 擁塞檢測與緩解算法

在無線傳感器網(wǎng)絡(luò)中，檢測網(wǎng)絡(luò)中是否出現(xiàn)擁塞狀況最普遍的方法是判斷緩沖區(qū)的占用率(buffer occupancy, BO)是否超過某一個閾值，如果節(jié)點的占用率超過了閾值則說明在網(wǎng)絡(luò)中可能出現(xiàn)了擁塞狀況。但采用閾值作為網(wǎng)絡(luò)中出現(xiàn)擁塞的依據(jù)并不一定能夠真實地反映出網(wǎng)絡(luò)中的真實狀況。另一種普遍的方式是計算節(jié)點的報文發(fā)送率與接收率之間的比值，此方法可以用來檢測當(dāng)時節(jié)點緩沖區(qū)的狀況，但如果出現(xiàn)高擁塞的情況。緩沖區(qū)剩余的空間很小，造成大量的丟包情況，則有可能出現(xiàn)報文的接收率與發(fā)送率(congestion level, CL)的比值變得很小。本文結(jié)合了類似CODEM(cogestion detection and mitigation, ECODEM)的方法，利用以上的兩種技術(shù)來判斷網(wǎng)絡(luò)中是否出現(xiàn)擁塞狀況，提出了一種ECODEM的方法。由于CODEM在檢測擁塞過程中采用的是靜態(tài)判定方法，僅僅依靠幾個固定閾值來判定網(wǎng)絡(luò)中擁塞是否發(fā)生。ECODEM采用梯度的方式來對擁塞的發(fā)生進(jìn)行檢測。

通過節(jié)點緩沖區(qū)的變化幅度(buffer change, BC)可以直接預(yù)測出節(jié)點在下一時刻的狀況，并為BO設(shè)定閾值和，檢測的規(guī)則如下：如果預(yù)測到在下一時刻有可能會發(fā)生擁塞或擁塞解除，則控制節(jié)點的發(fā)送率為。

如果在網(wǎng)絡(luò)中出現(xiàn)了擁塞狀況，則應(yīng)該對路徑中的流量重新分配，盡可能多地使用那些未使用的路徑，同時減少路徑中的流量傳輸。由于ECOTA建立了無重復(fù)節(jié)點的狀況，因此在ECODEM中就可以不用考慮因路徑交叉而造成的流量重分配問題。ECODEM的主要思想是在采用無交叉的路徑的前提下，把網(wǎng)絡(luò)中擁塞區(qū)域的流量轉(zhuǎn)移到其他非擁塞區(qū)域。在判斷網(wǎng)絡(luò)檢測擁塞區(qū)域的位置時采用CODEM中擁塞深度(congestion depth, CD)的方法。而在最終重新分配時仍然會考慮到ECOTA中使用的節(jié)點的能量、延遲兩個方面的因素，算法復(fù)雜度為()。

ECODEM算法

Begin

End For

If 未使用的路徑數(shù)大于或等于擁塞路徑數(shù)，則將流量轉(zhuǎn)移到未使用路徑上

End If

If 未使用的路徑數(shù)小于擁塞路徑數(shù)

對于已擁塞的路徑

重新分配的流量為：

End If

End

算法中，為常量

4 仿真結(jié)果

為了驗證本文算法的性能，對算法使用NS2仿真器進(jìn)行仿真。在仿真中，無線傳感器網(wǎng)絡(luò)一共有50個節(jié)點隨機分布在1個1 000′1 000的空間內(nèi)，每個節(jié)點的傳輸半徑為250，數(shù)據(jù)傳輸率為1 Mb/s，節(jié)點初始能量為1 000 J，節(jié)點在發(fā)送數(shù)據(jù)和接收數(shù)據(jù)時都有能量消耗。仿真使用了分組遞交率和平均端到端延時兩種指標(biāo)來判斷算法的性能，每個設(shè)置均進(jìn)行了多次試驗來避免誤差。仿真中假設(shè)網(wǎng)絡(luò)拓?fù)渲忻總€目標(biāo)節(jié)點的路由路徑都是已知的。

本文使用了兩個性能指標(biāo)來對比ECOTA、ECODEM和傳統(tǒng)的COTA、CODEM算法的性能。

2) 端到端延時。該指標(biāo)表示分組從源節(jié)點到達(dá)目標(biāo)節(jié)點的時間。包括路由發(fā)現(xiàn)、接口排隊、重傳和傳播時延。其中表示路由發(fā)現(xiàn)時間，表示接口排隊時間，表示重傳時延，表示傳播時延。在仿真試驗中，對兩種算法進(jìn)行了對比，其中網(wǎng)絡(luò)的連接數(shù)為5。源節(jié)點和目標(biāo)節(jié)點在網(wǎng)絡(luò)中隨機選擇。網(wǎng)絡(luò)中的路由使用標(biāo)準(zhǔn)的路由算法，仿真中路由指標(biāo)為源節(jié)點數(shù)據(jù)發(fā)送率的函數(shù)。根據(jù)結(jié)果可以看出當(dāng)數(shù)據(jù)傳輸率為5 包/s的時候，兩種算法的協(xié)議的性能類似。當(dāng)數(shù)據(jù)率低的時候，網(wǎng)絡(luò)不擁塞基本沒有發(fā)生包丟失的情況。

圖1 分組遞交率對比

當(dāng)數(shù)據(jù)發(fā)送率低的時候兩種協(xié)議基本的性能基本相同，當(dāng)數(shù)據(jù)包發(fā)送速率增加為15 包/s的時候COTA+CODEM的性能開始急劇下降，而本文提出的ECOTA+ECODEM算法的分組遞交率只有緩慢的下降，可以看到擁塞對于發(fā)送數(shù)據(jù)的遞交率影響較小，能夠達(dá)到較大的可靠性。

圖2 端到端延時對比

從圖2中可以看出，隨著網(wǎng)絡(luò)負(fù)載的增加，端到端的延時不斷增加，在數(shù)據(jù)傳輸率為20 包/s的時候，兩張算法的分組遞交率差不多，接著ECOTA+ ECODEM的優(yōu)勢開始顯示，算法的端到端延時降低10%左右，網(wǎng)絡(luò)中報文排隊的時間明顯減少，用戶體驗提升。

5 結(jié) 束 語

本文針對網(wǎng)絡(luò)中出現(xiàn)的擁塞現(xiàn)象，提出了一種ECOTA+ECODEM算法，可實現(xiàn)網(wǎng)絡(luò)中的擁塞避免、檢測和緩解的策略。在衡量了路徑的能耗與延遲的前提下，合理地分配了路徑流量，使得節(jié)點能夠更快地從擁塞狀況中恢復(fù)出來。另外，還提出了對于擁塞的預(yù)測方法，能夠更準(zhǔn)確地分析出網(wǎng)絡(luò)中是否出現(xiàn)擁塞狀況。仿真結(jié)果表明，本文提出的算法比COTA+CODEM性能提高10%左右，能夠有效地提高分組成功遞交率和降低端到端延時，從而提高網(wǎng)絡(luò)的整體性能。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.

[2] KAFI M A, DJENOURI D, BEN-OTHMAN J, et al. Congestion control protocols in wireless sensor networks: a survey[J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1369-1390.

[3] SERGIOU C, ANTONIOU P, VASSILIOU V. A comprehensive survey of congestion control protocols in wireless sensor networks[J]. IEEE Communication Surveys & Tutorials, 2014, 16(4): 1839-1859.

[4] SANKARASUBRAMANIAM Y, AKAN O B, AKYIDIZ I F. ESRT: Event to sink reliable transport in wireless sensor networks[C]//Proc of the 4th ACM Int’ l Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2003: 177-188.

[5] WAN C Y, EISENMAN S B, CAMPBELL A T. CODA: Congestion detection and avoidance in sensor networks[C]// Proc of the 1st ACM Conf on Embedded Networked Sensor Systems. New York: ACM, 2003: 266-279.

[6] HU Yue-ming, XUE Yue-ju, LI Bo, et al. SenTCP: a hop-by-hop congestion control protocol for wireless sensor networks[C]//IEEE INFOCOM 2005. Miami, USA: [s.n.], 2005.

[7] DRESSL F. Locality driven congestion control in self-organizing wireless sensor networks[C]//The Int’ l Workshop on Software Architectures for Self-Organization, and Software Techniques for Embedded and Pervasive Systems. Munich, Germany: [s.n.], 2005.

[8] KARENOS K, KALOGERAKI V, KRISHNAMURTHY S V. Cluster-based congestion control for supporting multiple classes of traffic in sensor networks[C]//The 2nd IEEE Workshop on Embedded Networked Sensors. Sydney: [s.n.], 2005.

[9] CHEN Shi-gang, YANG Na. Congestion avoidance based on lightweight buffer management in sensor networks[J]. IEEE Trans on Parallel and Distributed Systems, 2006, 17(9): 934- 946.

[10] WAN C Y, EISENMAN S B, CAMPBELL A T. Energy- efficient congestion detection and avoidance in sensor networks[J]. ACM Transactions on Sensor Networks, 2011, 7(4): 289-307.

[11] CHAKRAVARTHI R, GOMATHY C. IPD: Intelligent packet dropping algorithm for congestion control in wireless sensor network[C]//T Trendz in Information Sciences & Computing(TISC2010). Chennai: IEEE, 2010: 222-225.

[12] LI Shan-cang, ZHAO Shan-shan. Adaptive and secure load-balancing routing protocol for service-oriented wireless sensor networks[J]. IEEE Systems Journal, 2014, 8(3): 858-867.

[13] QIAN Peng, DONG En-qing. Multipath routing protocol based on congestion control mechanism implemented by cross-lay design concept for WSN[C]//IEEE 17th International Conference on Computational Science and Engineering. [S.l.]: IEEE, 2014, 378-384.

[14] SUN Guan-nan, QI Jian-dong, ZANG Zhe , et al. A reliable multipath routing algorithm with related congestion control scheme in wireless multimedia sensor networks[C]//2011 3rd International Conference on Computer Research and Development. Shanghai: [s.n.], 2011, 4: 229-233.

[15] REN Feng-yuan, HE Tao, DAS S, et al. Traffic-aware dynamic routing to alleviate congestion in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011, 22(9): 1585-1599.

[16] 李姍姍, 廖湘科, 朱培棟, 等. 傳感器網(wǎng)絡(luò)中一種擁塞避免、檢測與緩解策略[J]. 計算機研究與發(fā)展，2007, 44(8): 1348-1356.

LI Shan-shan, LIAO Xiang-ke, ZHU Pei-dong, et al. Congestion avoidance, detection and mitigation in wireless sensor networks[J]. Journal of Computer Research and Development, 2007, 44(8): 1348-1356.

編 輯 蔣 曉

Wireless Sensor Network Traffic Reallocation Congestion Control Algorithm

WEN Huai-yu1, 2and HUO Wei-dong2

(1. College of Information Sciences and Engineering, Chengdu University Chengdu 610106; 2. College of Economic Information Engineering, Southwestern University of Finance and Economics Chengdu 610074)

An enhanced congestion traffic allocation (ECOTA) and an efficient congestion detection and mitigation (ECODEM) algorithm are proposed in this paper, based on the traffic allocation and reallocation algorithm. After measuring the energy consumption and transmission delay of all paths, some low energy consumption and short delay paths are selected to increase the success rate of data transmission. The congested area is detected by methods of setting the threshold and prediction. Once the congestion occurs, nodes can quickly recover from congested situations by using reasonable traffic reallocation. And traffic in the congested area can be transferred to the non-congested area as soon as possible. Simulation results show that compared with other algorithms, the proposed algorithm can improve the success rate of packet delivery, reduce the end to end delay and improve the overall performance of the network.

congestion control; data transfer; traffic reallocation; wireless sensor networks

TP393

A

10.3969/j.issn.1001-0548.2017.02.015

2015-05-16；

2016-12-16

四川省科技支撐計劃(2015GZ 0283, 2015GZ0284)；四川省教育廳科技計劃-四川省哲學(xué)社會科學(xué)重點研究基地-四川省農(nóng)村發(fā)展研究中心資助(CR1627)

溫懷玉(1977-)，男，博士，教授級高級工程師，主要從事智慧城市、網(wǎng)絡(luò)通信及軟件技術(shù)方面的研究.