一種簡單的自適應(yīng)無線傳感器網(wǎng)絡(luò)信息流量控制方法

馬鐵英

（同濟(jì)大學(xué)軟件學(xué)院，上海 200031）

1 引言

隨著因特網(wǎng)的高速發(fā)展，網(wǎng)絡(luò)承載的信息流量越來越大，網(wǎng)絡(luò)擁塞時有發(fā)生，給讀者利用網(wǎng)絡(luò)信息資源帶來了障礙。圖書館可采用一種簡單的自適應(yīng)無線傳感器網(wǎng)絡(luò)信息流量控制方法，加強網(wǎng)絡(luò)信息流量控制，為讀者快捷利用網(wǎng)絡(luò)信息資源提供技術(shù)支持。

無線傳感器網(wǎng)絡(luò)是由一定的監(jiān)測區(qū)域內(nèi)的諸多微型傳感器節(jié)點組成，通過無線通信的方式形成一個多跳自組織網(wǎng)絡(luò)。一組功能有限的傳感器節(jié)點協(xié)作地完成大的感知任務(wù)是傳感器網(wǎng)絡(luò)的重要特點[1]。

無線傳感器網(wǎng)絡(luò)中的每個節(jié)點都具備路由的功能和計算功能。盡管無線傳感器網(wǎng)絡(luò)中存在諸多傳感器節(jié)點，但是會有某些節(jié)點負(fù)荷很大，需要轉(zhuǎn)發(fā)大量數(shù)據(jù)。當(dāng)待發(fā)送數(shù)據(jù)到達(dá)速率超過節(jié)點本身的處理速率時，數(shù)據(jù)會在此出現(xiàn)阻塞。長時間的阻塞會導(dǎo)致緩沖區(qū)快速溢出，這就造成數(shù)據(jù)分組丟失。為了不讓這些擁塞節(jié)點成為影響整個網(wǎng)絡(luò)工作效率的瓶頸，必需對這些瓶頸節(jié)點做好流量控制。無線傳感器網(wǎng)絡(luò)流量控制，是將網(wǎng)絡(luò)流量控制機制引入無線傳感器網(wǎng)絡(luò)，達(dá)到改善無線傳感器網(wǎng)絡(luò)性能的目的。

基于無線多跳Ad Hoc網(wǎng)的流量控制機制，是網(wǎng)絡(luò)中的節(jié)點根據(jù)隊列長度計算出個虛擬代價，然后將一條路由上所有的虛擬代價求和，將該和值發(fā)送到源節(jié)點，源節(jié)點再根據(jù)所獲得的值控制流量[2]。擁塞節(jié)點，通過計算傳輸隊列的長度，來判斷該節(jié)點的擁塞代價，然后不斷地向正在向該擁塞節(jié)點發(fā)送數(shù)據(jù)包的前跳節(jié)點反饋。前跳節(jié)點根據(jù)反饋信息決定數(shù)據(jù)包的速率[3]。

本文提出的一種簡單的自適應(yīng)無線傳感器網(wǎng)絡(luò)流量控制方法，僅通過對擁塞節(jié)點的前跳節(jié)點進(jìn)行流量控制，可實現(xiàn)控制流入擁塞節(jié)點的流量大小，平衡經(jīng)過擁塞節(jié)點的流入和流出速率，而不需要關(guān)注其他相鄰節(jié)點或者其他上游節(jié)點。

2 一種簡單的自適應(yīng)無線傳感器網(wǎng)絡(luò)流量控制方法

在自適應(yīng)無線傳感器網(wǎng)絡(luò)流量控制方法中，流量控制的關(guān)鍵在于對計算節(jié)點虛擬代價。虛擬代價標(biāo)志這一個節(jié)點的擁塞程度。

假設(shè)一個節(jié)點p只對它的后節(jié)點q負(fù)責(zé)，而這個節(jié)點q只需考慮來自前跳節(jié)點p的流量，即p節(jié)點只控制流入它的后節(jié)點的流量大小，q的虛擬代價只提供給它的前跳節(jié)點p。只有在q節(jié)點發(fā)生了擁塞的前提下，p節(jié)點才會需要q節(jié)點提供它的虛擬代價。P將會根據(jù)q節(jié)點了的虛擬代價調(diào)節(jié)流向q的流量大小，如果一段時間后前跳節(jié)點p也發(fā)生了擁塞，那么p的前節(jié)點o也會根據(jù)節(jié)點p的虛擬代價對其進(jìn)行流量控制。如果網(wǎng)絡(luò)內(nèi)部在一定時限，自己消化了擁塞，反而不需要驚動源節(jié)點，這樣網(wǎng)絡(luò)能對我保持一定的封閉性和獨立性。

每一個節(jié)點都可能會有多個前跳節(jié)點，也可能會有多個后節(jié)點，沒有前跳節(jié)點的節(jié)點稱為源節(jié)點，沒有后節(jié)點的節(jié)點稱為目標(biāo)節(jié)點。

2.1 流量的計算

在自適應(yīng)無線傳感器網(wǎng)絡(luò)的流量控制機制中，每個節(jié)點都有一個虛擬代價表示節(jié)點的擁塞程度，這個虛擬代價值隨著隊列長度變化而不斷變化。當(dāng)一定流量通過某節(jié)點時，該節(jié)點就會判斷當(dāng)前是否處于擁塞狀態(tài)，一旦確定發(fā)生了擁塞，就會根據(jù)當(dāng)前隊列長度計算虛擬代價，再將虛擬代價反饋至它的前跳節(jié)點p，節(jié)點p根據(jù)所獲得的虛擬代價及時調(diào)整發(fā)送給節(jié)點q的數(shù)據(jù)的流量值f的大小，這個過程簡單及時。

如圖1所示，當(dāng)目標(biāo)節(jié)點E發(fā)生擁塞時，就會生成虛擬代價C1，然后將C1發(fā)送到節(jié)點Q，而Q節(jié)點會減少給E的流入流量，這樣Q的流量平衡就會打破，一定時間Q就有可能發(fā)生擁塞；同樣，如果節(jié)點Q發(fā)生擁塞時，就會生成虛擬代價C2，然后將C2發(fā)送到節(jié)點P;如此，就可以將擁塞的情況反饋至初始節(jié)點S。

圖1 無線傳感器網(wǎng)絡(luò)流量示意圖

問題一般化，定義一個有N個靜態(tài)節(jié)點的無線ad hoc網(wǎng)絡(luò)W={1,2,…,N}，網(wǎng)絡(luò)中一個數(shù)據(jù)源節(jié)點s∈W沿著路由 R={s,i1,i2,…,ij,e}發(fā)送數(shù)據(jù)到目標(biāo)節(jié)點e∈W，其中ij∈W，源節(jié)點到目標(biāo)節(jié)點的跳數(shù)為j+1。

假設(shè)有Mk個流量通過節(jié)點k，其中流量fl(l∈1,…,Mk)并且流量fl的速率為rl(l∈1,…,Mk),那么節(jié)點k的總流量為

2.2 隊列長度的計算

無線傳感器網(wǎng)絡(luò)中的虛擬代價是網(wǎng)絡(luò)資源的需求。在自適應(yīng)的流量控制機制中，每個無線傳感節(jié)點k都有一個不斷變化的虛擬代價Ck。當(dāng)一個流量f通過節(jié)點k,那么Ck就等于原來的值加上流量f的代價。當(dāng)然不是直接加上流量，而是通過流量f產(chǎn)生的隊列長度進(jìn)行計算新的虛擬代價。

隊列長度反映了網(wǎng)絡(luò)負(fù)載和網(wǎng)絡(luò)計算能力的差異，在一個自適應(yīng)的無線傳感器網(wǎng)絡(luò)流量控制機制中,當(dāng)一個路由節(jié)點的隊列長度超過了所規(guī)定的上限，虛擬代價將會增加，反之會降低。而節(jié)點的吞吐率反映了該節(jié)點處理擁塞的能力。吞吐率越大，節(jié)點的處理擁塞的能力越強，隊列的長度就越短;相反，如果吞吐率越小，隊列的長度就越長。所以一個節(jié)點中的隊列長度反映了該節(jié)點的擁塞程度[4]。

由于網(wǎng)絡(luò)中流量發(fā)送的不確定性，每個節(jié)點中的隊列都在隨著時間不斷地變化，好在我們的方法只需計算擁塞節(jié)點的隊列長度。節(jié)點的隊列長度為單位時間內(nèi)該節(jié)點的流入量和流出量的差值，再加上該節(jié)點原有的隊列長度，當(dāng)流入量大于流出量時，節(jié)點隊列長度增大，想反，當(dāng)流入量小于流出量時，流量隊列長度變小。

k節(jié)點的隊列長度計算如下：

其中，Σfin、Σfout分別表示為k節(jié)點的流入流量和流出流量，T表示單位時間，即計算虛擬代價的時間間隔。

2.3 虛擬代價的計算

無線傳感器網(wǎng)絡(luò)中，每個無線節(jié)點都有一個隊列存儲待發(fā)送的數(shù)據(jù)包。隊列的最大長度等于傳感器中緩沖區(qū)的大小。假設(shè)節(jié)點的緩沖區(qū)的容量為V，那么節(jié)點所能緩存數(shù)據(jù)包的最大隊列長度也為V。根據(jù)傳感器節(jié)點中的隊列長度，使用下列的公式來計算節(jié)點k的虛擬代價：

其中，Qk(t)表示節(jié)點k在t時刻的隊列長度。

這樣，通過計算流量和隊列長度，就計算出來了節(jié)點的虛擬代價，然后將虛擬代價提交給上跳節(jié)點，由上跳節(jié)點來控制擁塞節(jié)點的流入流量。

3 仿真實驗與分析

如圖2，四節(jié)點組成的無線傳感器網(wǎng)絡(luò)，其中源節(jié)點S1和S2，一起流向節(jié)點B，然后經(jīng)由B流到目標(biāo)節(jié)點E，所以這里S1、S2為B的上跳節(jié)點，B為E的上跳節(jié)點。

圖2 四節(jié)點網(wǎng)絡(luò)圖

假設(shè)所有節(jié)點處理數(shù)據(jù)的能力相同，最大隊列長度都為100個數(shù)據(jù)包。如圖2所示，節(jié)點S1和S2同時向該節(jié)點B發(fā)送數(shù)據(jù)，如果不做控制，由于節(jié)點處理數(shù)據(jù)的能力和存儲數(shù)據(jù)的緩沖有限，B的緩沖區(qū)很快會用完，而處理數(shù)據(jù)的速度也不如數(shù)據(jù)的流入，B勢必會成為擁塞節(jié)點，從而成為整個網(wǎng)絡(luò)的瓶頸。設(shè)定不考慮無線傳輸?shù)淖畲髠鬏斔俾氏拗?，即帶寬限制，每個節(jié)點發(fā)送數(shù)據(jù)包的初始速率都為5個數(shù)據(jù)包/秒，t=0時，所有節(jié)點的隊列長度Qk(0)=0。通過仿真，得到仿真結(jié)果圖3、圖4和圖5。圖3、圖4和圖5分別是流入擁塞節(jié)點B的流量、隊列長度和虛擬代價隨時間的變化圖。圖3中，在t＞3后，流量f1和f2出現(xiàn)小幅度波動，這時顯然是由于B發(fā)生了擁塞，源節(jié)點S1和S2作出了流量控制，在t＞8后，趨于穩(wěn)定。

圖3 流量速率隨時間變化

圖4 隊列長度隨時間變化

圖5 虛擬代價隨時間變化

4 結(jié)果與結(jié)論

本文提出的一種簡單的自適應(yīng)無線傳感器網(wǎng)絡(luò)流量控制方法，通過僅計算擁塞節(jié)點的虛擬代價，僅對擁塞節(jié)點的前跳節(jié)點進(jìn)行流量控制，就實現(xiàn)了整個網(wǎng)絡(luò)的流量控制，充分降低所占用的節(jié)點的處理能力，也達(dá)到了節(jié)約能源的目的。

[1]Ye Wei,Heidemann J,Estrin D.Medium Access Control with Coordinated Adaptive Sleeping for Wireless Sensor Networks[J].IEEE/ACM Trans.on Network,2004,12(3):493-506.

[2]GaoHong,DingWei.ABR flow control algorithm in ATM networks:A neural network approach[J].CHUPT,2005,7(4).

[3]He Wen-bo,LiuXue,NahrstedtK.A feedback control scheme for resource allocation in wireless multi-hop ad hoc networks[C]//Proc of ACM MobiQuitous Conference 2005,July,2005.

[4]WangJun,SongMin.Rate-based active queue management for TCP flows overwired and wireless networks[J].EURASIP Journal on Wireless Communications and Networking,2007.