李路偉， 楊洪勇

（魯東大學(xué)信息與電氣工程學(xué)院，煙臺 264025）

無線傳感器網(wǎng)絡(luò)自適應(yīng)擁塞控制的路由算法分析

李路偉， 楊洪勇

（魯東大學(xué)信息與電氣工程學(xué)院，煙臺 264025）

無線傳感器網(wǎng)絡(luò)中節(jié)點的覆蓋范圍有限，因而采用多跳路由傳輸方式.無線自組網(wǎng)中的多跳路由是由普通節(jié)點協(xié)作完成的，選擇不同的轉(zhuǎn)發(fā)節(jié)點，會對網(wǎng)絡(luò)的信息傳輸產(chǎn)生不同的影響.對不同路由（洪泛路由、最短路徑等）算法下的網(wǎng)絡(luò)自適應(yīng)擁塞控制進行了分析，研究了不同路由算法下的網(wǎng)絡(luò)性能和擁塞控制效果.根據(jù)節(jié)點跳數(shù)與緩存占用的關(guān)系，提出一種基于節(jié)點跳數(shù)和緩存占用的性能函數(shù)的改進最短路徑算法，算法選取使性能函數(shù)值最小的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點.最后，通過實驗比較了最短路徑算法與改進路由算法的網(wǎng)絡(luò)性能，發(fā)現(xiàn)改進路由算法相比最短路徑算法，具有較好的網(wǎng)絡(luò)性能和服務(wù)質(zhì)量.

無線傳感器網(wǎng)絡(luò)；自適應(yīng)；擁塞控制；路由算法

與物理世界緊密結(jié)合的無線傳感器網(wǎng)絡(luò)具有局部區(qū)域大規(guī)模部署、節(jié)點資源有限、無線帶寬小、拓撲結(jié)構(gòu)動態(tài)變化等特點［1］.此外，還具有多對一的通信方式、無線鏈路的相互干擾、網(wǎng)絡(luò)的動態(tài)變化和資源受限等特性，使得無線傳感器網(wǎng)絡(luò)極易產(chǎn)生擁塞，嚴重影響網(wǎng)絡(luò)的服務(wù)質(zhì)量和生存周期，因此擁塞控制成為保障無線傳感器網(wǎng)絡(luò)服務(wù)質(zhì)量的關(guān)鍵技術(shù)之一［2-5］.

網(wǎng)絡(luò)路由是指設(shè)備從一個接口上收到數(shù)據(jù)包，并根據(jù)數(shù)據(jù)包的目的地址進行定向并轉(zhuǎn)發(fā)到另一個接口的過程.在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，每一個節(jié)點都是一個終端，其路由問題就是產(chǎn)生數(shù)據(jù)的節(jié)點如何通過其它節(jié)點與sink節(jié)點建立起鏈接的問題［6-9］.

目前，無線傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境千差萬別，使得沒有一個路由機制適合所有的應(yīng)用，因此無線傳感器網(wǎng)絡(luò)的路由協(xié)議具有很強的應(yīng)用相關(guān)性.另外，WSNs（wireless sensor networks）節(jié)點隨機分布，是以數(shù)據(jù)為中心的網(wǎng)絡(luò)，所以傳統(tǒng)的無線路由協(xié)議在此并不適用.進而，根據(jù)不同應(yīng)用對WSNs敏感性要求的不同，可將無線傳感器網(wǎng)絡(luò)路由協(xié)議分為以下5種類型：數(shù)據(jù)查詢路由、能量最優(yōu)路由、位置信息路由、可靠路由和可編程路由［10］.總的來說，目前WSNs路由技術(shù)的研究還僅僅處于起步階段，雖然發(fā)展迅速、成果顯著，但距離很好地支持更高要求的無線傳感器網(wǎng)絡(luò)應(yīng)用，還有很大的差距［11-13］.

本文將路由技術(shù)與擁塞控制技術(shù)二者結(jié)合起來考慮，比較了洪泛路由、最短路徑算法下自適應(yīng)擁塞控制的網(wǎng)絡(luò)性能.針對最短路徑算法存在的不足之處，提出一種基于跳數(shù)和緩存占用的改進路由算法，并通過實驗比較和分析了最短路徑算法與改進路由算法在自適應(yīng)擁塞控制下的網(wǎng)絡(luò)性能.

1 無線傳感器網(wǎng)絡(luò)的自適應(yīng)擁塞控制

在研究中，假設(shè)在一定區(qū)域內(nèi)所有節(jié)點隨機自組形成網(wǎng)狀結(jié)構(gòu)模型.此時，一個節(jié)點可以與多個節(jié)點進行通信.實際應(yīng)用中，通常采用播撒一定數(shù)量節(jié)點到某一區(qū)域內(nèi)的做法來實現(xiàn)對某一區(qū)域特定事件的觀測，這個時候的網(wǎng)絡(luò)結(jié)構(gòu)趨向為圖1所示的網(wǎng)狀拓撲結(jié)構(gòu).

本文將以網(wǎng)狀拓撲結(jié)構(gòu)為模型，進行不同路由算法下基于自適應(yīng)擁塞控制的研究.假設(shè)擁塞調(diào)節(jié)策略為帶上、下跳節(jié)點協(xié)同進行擁塞調(diào)節(jié)的機制，該擁塞控制算法包含以下幾部分：

圖1 網(wǎng)狀拓撲結(jié)構(gòu)圖Fig.1 Mesh topology diagram

a.節(jié)點發(fā)送分組之前，判斷是否有增加發(fā)送速率的請求.

令request表示節(jié)點增加發(fā)送速率的請求.當request=1時，有增加發(fā)送速率的請求；否則，請求無效，按原速率進行發(fā)送.

其中，breg表示節(jié)點緩存占用，b2是算法中對節(jié)點緩存空間進行劃分的標記值之一，此外還有b 1和b 3.b 1，b 2，b 3依次增大，主要用來對緩存空間進行劃分，便于節(jié)點根據(jù)緩存占用處于不同的劃分區(qū)間對傳輸速率、操作請求等進行自適應(yīng)控制. request＿send（）表示請求發(fā)送操作，packet＿send（）為分組發(fā)送操作，ratio＿present表示節(jié)點的當前分組發(fā)送速率.

b.接收節(jié)點對增加發(fā)送速率的請求作出反饋.

假設(shè)允許節(jié)點增加發(fā)送速率的最大值為ratio＿initial，gain＿range表示允許增加發(fā)送速率的幅度.

其中，β1是在研究中預(yù)設(shè)的兩個擁塞閾值之一；另一個閾值為β2，兩者依次增大，主要用來控制緩存占用的擁塞程度；β表示節(jié)點的擁塞程度.首先，判斷是否有增加發(fā)送速率的請求.若request= 1，有請求，此時，若接收節(jié)點緩存占用的值breg∈［0，b1），則此時發(fā)送節(jié)點發(fā)送速率增加的幅度為一個平均值，即ratio＿initial*β1／node＿max；若接收節(jié)點緩存占用的值breg∈［b1，b2），則將擁塞閾值β1與節(jié)點當前擁塞程度β間的差值在多個發(fā)送節(jié)點間進行平均分配，并乘上發(fā)送速率增加的最大值.node＿max表示可以發(fā)送分組到該節(jié)點的所有鄰居節(jié)點數(shù)目.若接收節(jié)點緩存占用的值breg∈［b 2，∞），則拒絕節(jié)點請求，不允許增加.request＿feedback（）表示請求反饋函數(shù).

c.節(jié)點收到分組后，根據(jù)緩存占用breg計算擁塞程度值β.β計算算法［14］為

其中，breg表示節(jié)點緩存占用，bi（i=1，2，3），β1與β2如前所述.

d.根據(jù)節(jié)點擁塞程度β，執(zhí)行速率調(diào)節(jié)算法，計算下一分組接收的最大速率.分組速率調(diào)節(jié)算法為

其中，初始分組發(fā)送速率為ratio＿initial.packet＿lose（x）表示分組丟棄操作，x∈（0，1），表示節(jié)點將以x*ratio＿initial的速度丟棄分組.參數(shù)a，b是預(yù)設(shè)的兩個分組丟失比例，取值較大時，節(jié)點丟棄分組的速率也會很大，有助于迅速減小緩存占用.下一分組發(fā)送時，只準許分組發(fā)送速率小于或等于ratio.

2 3種路由算法下的自適應(yīng)擁塞控制性能分析

對3種不同的路由算法：Flooding算法、Gossiping算法、最短路徑算法（Shortest）進行分析，比較基于網(wǎng)絡(luò)自適應(yīng)擁塞控制下3種路由算法的性能.

2.1 3種路由算法簡介

Flooding是一種較傳統(tǒng)的網(wǎng)絡(luò)通信路由協(xié)議. Flooding算法對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和相關(guān)的路由計算并沒有要求，所以其路由算法下的節(jié)點采用廣播方式來傳遞分組.為克服Flooding算法的固有缺陷，Hedetniemi等［15］提出閑聊式策略Gossiping算法，使用隨機性原則，即節(jié)點發(fā)送數(shù)據(jù)時不再采用廣播形式，而是隨機選取一個相鄰節(jié)點轉(zhuǎn)發(fā)它接收到的數(shù)據(jù)副本.最短路徑算法可以使每個節(jié)點在分組發(fā)送之前，選擇最小跳數(shù)的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，繼而完成分組的發(fā)送和接收工作.

由于無線傳感器網(wǎng)絡(luò)多跳的數(shù)據(jù)傳輸方式，其拓撲結(jié)構(gòu)更像是一個分布式動態(tài)系統(tǒng).本文基于有向圖的基本理論對無線傳感器網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行建模.

2.2 3種路由算法下的自適應(yīng)擁塞控制性能分析

通過比較自適應(yīng)擁塞調(diào)節(jié)機制下3種路由算法的網(wǎng)絡(luò)性能，分析產(chǎn)生性能差異的原因，如圖2所示.

假設(shè)100個節(jié)點隨機均勻地播撒在100 m×100 m的方形區(qū)域內(nèi)，sink節(jié)點位于該方形區(qū)域的右邊界中點上.每次實驗隨機選取20，40，60或80個節(jié)點作為源節(jié)點進行分組的發(fā)送.節(jié)點緩存隊列劃分：b1= 200，b2=400，b3=500；節(jié)點緩存最大容量：cache= 600；擁塞閾值：β1=0.4，β2=0.6；分組丟棄比例：a= 0.1，b=0.3；節(jié)點初始分組發(fā)送速率：ratio＿initial= 10；源節(jié)點數(shù)目：source node-num=20／40／60／80；所有節(jié)點數(shù)目：sum-node-num=100；sink數(shù)目：sink-num=1；網(wǎng)絡(luò)發(fā)送packets任務(wù)：400／node；分布區(qū)域面積：100 m×100 m.

圖2 3種路由算法的網(wǎng)絡(luò)性能對比圖Fig.2 Network performance comparison between the three routing algorithms

圖2（a），（b）分別表示3種路由算法下，隨機選取源節(jié)點數(shù)目為20，40，60，80時，網(wǎng)絡(luò)的吞吐量和分組丟失率對比圖.由圖2（a）可知，最短路徑算法的網(wǎng)絡(luò)吞吐量要高于Gossiping算法而低于Flooding算法.由于Flooding算法下，節(jié)點在進行分組傳輸時，除對其發(fā)送分組的節(jié)點外，節(jié)點會向其所有鄰居節(jié)點發(fā)送相同數(shù)目的分組，該做法會使網(wǎng)絡(luò)中分組數(shù)量成倍增加，網(wǎng)絡(luò)吞吐量大幅增長.而Gossiping算法使用隨機性原則，放棄廣播形式，隨機選取一個鄰居節(jié)點轉(zhuǎn)發(fā)分組，相比Flooding算法，網(wǎng)絡(luò)吞吐量下降較大.最短路徑算法介于兩者之間，選取到sink節(jié)點的最短路徑節(jié)點進行分組傳輸，相比Gossiping算法，網(wǎng)絡(luò)吞吐量有所增加.

由圖2（b）可見，F(xiàn)looding算法下的分組丟失率一直很高.而最短路徑算法在分組丟失率上要明顯好于Flooding算法，且與Gossiping算法接近.由于“消息”內(nèi)爆，F(xiàn)looding算法會產(chǎn)生大量分組丟失.與之相比，Gossiping策略解決了“消息”內(nèi)爆問題，降低了分組丟失率.最后，最短路徑算法具有實現(xiàn)簡單、路徑最短、時延最短等優(yōu)點，能夠?qū)⒎纸M快速傳遞到sink節(jié)點，但也存在某一路徑節(jié)點傳輸壓力過大，造成分組大量丟失的問題.因而在保證分組快速傳輸?shù)耐瑫r，解決某一路徑負載過重問題，有利于改善最短路徑算法的網(wǎng)絡(luò)性能.

3 改進最短路徑算法下的擁塞控制

通過研究發(fā)現(xiàn)，最短路徑算法在節(jié)點選擇時，可能會選擇緩存空間剩余較小的節(jié)點作為其接下來的分組轉(zhuǎn)發(fā)節(jié)點，而這無疑會增加節(jié)點的擁塞處理壓力，造成分組的丟失.針對最短路徑算法的上述不足之處，提出一種基于節(jié)點跳數(shù)和緩存占用的改進最短路徑算法（Modified Shortest）.

基于有向圖的基本理論對無線傳感器網(wǎng)絡(luò)的拓撲結(jié)構(gòu)進行建模.假設(shè)n階加權(quán)有向圖G（V，E，K），其中，節(jié)點集V=｛vi｝，i∈L=｛1，2，…，n｝，邊集E=｛eij=（i，j）｝，加權(quán)鄰接矩陣K=（kij）∈?n*n（kij≥0，i，j∈L且i≠j）.

3.1 改進最短路徑算法

基于節(jié)點跳數(shù)和緩存占用的路由算法，通過將跳數(shù)與下一跳節(jié)點緩存占用兩者綜合考慮，實現(xiàn)適當降低傳輸速率的同時，緩解某一路徑傳輸壓力，降低分組丟失率的目的.

改進最短路徑算法以緩存占用和節(jié)點跳數(shù)的函數(shù)weight（pocketnum，hopcount）為依據(jù)，動態(tài)確定路由路徑，主要包括以下幾個部分：

a.緩存占用與節(jié)點跳數(shù)的性能函數(shù)

如分組發(fā)送節(jié)點為S，其鄰居節(jié)點分別為A，B，C，則它們的緩存占用與節(jié)點跳數(shù)分別為packetnum＿A，packetnum＿B，packetnum＿C和hopcount＿A，hopcount＿B，hopcount＿C.節(jié)點在完成分組發(fā)送或接收后，計算其weight（packetnum，hopcount）值，權(quán)值計算公式為

其中，max＿hopcount表示節(jié)點到sink的最大跳數(shù).α表示控制函數(shù)值weight對節(jié)點跳數(shù)和緩存占用的側(cè)重程度，α愈大，對跳數(shù)越為側(cè)重，相應(yīng)傳輸速度也大；反之，則小.cache表示節(jié)點的緩存大小.顯然，節(jié)點權(quán)值不再是一個預(yù)先設(shè)計好的定值而是一個隨網(wǎng)絡(luò)狀況不斷變化的自適應(yīng)值.

b.請求weight值

節(jié)點發(fā)送分組前，請求各鄰居節(jié)點的weight值，鄰居節(jié)點反饋weight值請求

其中，weight＿request表示對鄰居節(jié)點weight值的查詢請求.節(jié)點反饋查詢請求，將自己的weight值發(fā)送給請求節(jié)點.

c.確定轉(zhuǎn)發(fā)節(jié)點

節(jié)點S在收到3個鄰居節(jié)點的weight值weight＿A，weight＿B，weight＿C后，執(zhí)行算法為

其中，mini＿weight表示最小weight值，節(jié)點S根據(jù)比較，選定weight值最小的節(jié)點，并向其發(fā)送分組.weight值愈小，說明其距離sink節(jié)點愈近或分組占用緩存越少.節(jié)點選定其下一跳節(jié)點后，完成分組的發(fā)送，相應(yīng)的下一跳節(jié)點完成分組的接收. choose（）為節(jié)點選取操作.

假設(shè)α=0.8，cache=20，各節(jié)點緩存占用packetnum=10時，根據(jù)前述算法，可以得到類似圖3所示的節(jié)點weight值.

圖3 改進最短路徑算法下分組傳輸Fig.3 Packet transmission of improved shortest path algorithm

由圖3可以看到，從源節(jié)點到匯聚節(jié)點sink，需要經(jīng)過多個中間節(jié)點，每個節(jié)點都有一個weight值，該值由上述算法計算得到.分組發(fā)送時，選擇weight值最小的節(jié)點作為其下一跳節(jié)點，即值為0.3的節(jié)點.對于sink，假定其緩存無限，故其緩存大小可以始終設(shè)為0，所以其權(quán)值也為0.

由求最短路徑的Dijkstra算法可以得知，分組總是可以在一次傳遞過程中，找到一條到達sink節(jié)點的最短路徑，而這條路徑則是改進后的最短路徑.

3.2 改進最短路徑算法下自適應(yīng)擁塞控制性能分析

實驗中，通過隨機選取一定數(shù)量的源節(jié)點進行分組的發(fā)送，比較基于節(jié)點跳數(shù)和緩存占用算法與最短路徑算法的網(wǎng)絡(luò)吞吐量和分組丟棄率.

假設(shè)100個節(jié)點隨機均勻地播撒在100 m× 100 m的方形區(qū)域內(nèi)，sink節(jié)點位于該方形區(qū)域的右邊界中點上.實驗設(shè)置與上一實驗相同.此外，α的取值為0.8.

圖4（見下頁）給出了不同路由算法下，隨機選取源節(jié)點數(shù)目為20，40，60，80時，網(wǎng)絡(luò)采用自適應(yīng)擁塞控制機制所得到的網(wǎng)絡(luò)性能比較圖.

由圖4（a）可見，隨著源節(jié)點數(shù)目的增多，兩種算法的網(wǎng)絡(luò)吞吐量都不斷增加，但超過一定的節(jié)點數(shù)量后，改進算法的網(wǎng)絡(luò)吞吐量要高于最短路徑算法.由圖4（b）可以看出，隨著源節(jié)點數(shù)目的增多，兩者的分組丟失率都在不斷上升，但很顯然，改進最短路徑算法的分組丟失率要低于最短路徑算法.其中，“Shortest”表示最短路徑算法，“Modified shortest”表示改進最短路徑算法.由圖4不難看出，選取相同數(shù)目源節(jié)點的情況下，改進最短路徑算法的網(wǎng)絡(luò)性能相比最短路徑算法要好一些.改進最短路徑算法，在下一跳節(jié)點的選擇上，側(cè)重于選擇那些緩存空間剩余較多的節(jié)點，以避免過多分組的丟失，由此，在網(wǎng)絡(luò)性能上較最短路徑算法要好.

圖4 兩種路由算法下的網(wǎng)絡(luò)性能對比圖Fig.4 Network performance comparison of the two routing algorithms

4 總 結(jié)

首先分析了Flooding、Gossiping、最短路徑等路由算法在自適應(yīng)擁塞控制機制下的網(wǎng)絡(luò)性能.然后，由于最短路徑算法可能導(dǎo)致某一路徑節(jié)點負載過重，綜合考慮節(jié)點跳數(shù)與緩存占用，提出一種改進最短路徑算法，并以圖論思想予以證明和討論.最后，通過實驗比較了最短路徑算法與改進最短路徑算法的網(wǎng)絡(luò)性能，發(fā)現(xiàn)基于自適應(yīng)擁塞控制機制下的改進最短路徑算法相比最短路徑算法，具有較好的網(wǎng)絡(luò)性能.

［1］ 李凌，周興社，李士寧，等.基于無線傳感器網(wǎng)絡(luò)的擁塞控制算法的研究與比較［J］.計算機應(yīng)用研究，2006，23（3）：11-13.

［2］ 孫利民，李波，周新運.無線傳感器網(wǎng)絡(luò)的擁塞控制技術(shù)［J］.計算機研究與發(fā)展，2008，45（1）：63-72.

［3］ 崔莉，鞠海玲，苗勇，等.無線傳感器網(wǎng)絡(luò)研究進展［J］.計算機研究與發(fā)展，2005，42（1）：163-174.

［4］ Wang C，Li B，Sohraby K，et al.Upstream congestion control in wireless sensor networks through crosslayer optimization［J］.IEEEJournal on Selected Areas in Communication，2007，25（4）：786-795.

［5］ 文浩，林闖，任豐原，等.無線傳感器網(wǎng)絡(luò)的QoS體系結(jié)構(gòu)［J］.計算機學(xué)報，2009，32（3）：432-440.

［6］ Cheng Z，Heinzelman W B.Searching strategy for multi-target discovery in wireless networks［C］∥Proceedings of the 4th Workshop on Applications and Services in Wireless Networks，ASWN’04. Boston，2004.

［7］ Rezaiifar R，Makowski A M.From optimal search theory to sequential paging in cellular networks［J］. IEEE Journal on Selected Areas in Communication，1977，15（7）：1253-1264.

［8］ 于海斌，曾鵬，梁韡.智能無線傳感器網(wǎng)絡(luò)系統(tǒng)［M］.北京：科學(xué)出版社，2006.

［9］ 胡仕強.無線傳感器網(wǎng)絡(luò)的路由協(xié)議分析研究［J］.機械與電子，2010，7（1）：26-28.

［10］ 廖鷹，王育勤，陳楚湘.無線傳感器網(wǎng)絡(luò)路由技術(shù)研究［J］.計算機工程與設(shè)計，2008，29（9）：2156-2159.

［11］ 孫姬，陳霞，談?wù)褫x.無線傳感器網(wǎng)絡(luò)路由技術(shù)淺析［J］.傳感器世界，2005（11）：30-34.

［12］ 鄔春學(xué)，肖麗.基于蟻群算法的低能耗LEACH協(xié)議分析［J］.上海理工大學(xué)學(xué)報，2010，32（1）：99-102.

［13］ 于林峰，肖麗.一種基于WSN的協(xié)議改進算法分析［J］.上海理工大學(xué)學(xué)報，2009，31（4）：406-408.

［14］ 李路偉，楊洪勇.基于RED的無線傳感器網(wǎng)絡(luò)的擁塞控制［J］.計算機仿真，2012，29（3）：13-17.

［15］ Hedetniemi S M，Hedetniemi S T，Liestman A L.A survey of gossiping and broadcasting in communication networks［J］.Networks，1988，18（4）：319-349.

（編輯： 丁紅藝）

Analysis on Routing Algorithms of Adaptive Congestion Control of Wireless Sensor Networ ks

LILu-wei， YANGHong-yong
（College of Information and Electrical Engineering，Ludong University，Yantai 264025，China）

Since the coverage of wireless sensor network nodes is limited，the transmission of multi-hop routing is adopted.The multi-hop routing of wireless ad hoc networks is realized by common nodes cooperation and selecting different forwarding nodes will have a different effect upon the information transmission.By analyzing the network adaptive congestion control with different routing algorithms such as the flooding routing and the shortest path algorithm，the performances of network and congestion control with different kinds of routing algorithms were studied.According to the relationship between hop count and cache occupied，a kind of improved shortest path algorithm based on the performance function of node hop count and cache occupied was proposed，where the node with minimum value of function was selected as the forwarding node.Experiment examples were used to compare the network performances of the shortest path algorithm and the modified routing algorithm.It is shown that the modified one has better network performance and service quality than the shortest path algorithm.

wireless sensor networks；adaptability；congestion control；routing algorithms

TP 3

A

1007-6735（2013）03-0215-06

2012-10-21

國家自然科學(xué)基金資助項目（61273152）；山東自然科學(xué)基金資助項目（ZR2011M017）

李路偉（1988-），男，碩士研究生.研究方向：網(wǎng)絡(luò)通信技術(shù).E-mail：luweili1988＠126.com

楊洪勇（1967-），男，教授.研究方向：網(wǎng)絡(luò)擁塞控制、復(fù)雜網(wǎng)絡(luò)、多智能體協(xié)調(diào)控制等.E-mail：hyyang＠yeah.net