WSN中的最大冗余丟棄和覆蓋傳輸擁塞控制

周小玲，付銀蓮

(1.廣州鐵路職業技術學院 基礎課部，廣東 廣州 510430;2.華南農業大學 數學與信息學院，廣東 廣州 510642)

0 引 言

無線傳感器網絡(wireless sensor network，WSN)的應用已經擴展到諸多領域[1,2]，這種網絡的一個顯著特點就是在接收器附近傳感器節點高度密集。隨著網絡規模的擴大，這些節點間的擁塞效應會變得更加明顯。而這些節點的帶寬是有限的，因此，為了最大化網絡覆蓋，選擇合適的數據包進行緩沖和傳輸非常重要；一個數據包除了包含監測區域內某處事件的可用值外，往往還包含事件的位置。這些信息可以通過包含在數據包頭中的節點ID或檢測事件的節點坐標來傳輸。在前一種情況下，接收器節點需要采用預先計算的數據將節點ID映射到其位置。顯然，這僅對預先規劃的部署才是可行的。在后一種情況下，位置信息可以通過GPS或定位算法[3-5]來獲得。

傳感器網絡的一個極其重要的性能目標是其覆蓋范圍。正如文獻[6,7]所指出，覆蓋有不同的特定表述，但一般認為是通過網絡提供服務質量的一種度量。如果網絡擁塞，則來自不同源的數據包在到達接收器之前有可能被丟棄，從而導致事件未被檢測到或出現檢測差錯。因此，采用緩沖和調度機制來實現覆蓋感知是很有用的。

盡管緩沖區管理和調度已經在傳感器網絡中得到了研究，但大多數現有研究或者僅考慮調度，或者僅考慮緩沖區管理，或者僅考慮覆蓋，而沒有在網絡擁塞狀態下同時將這三者加以考慮。文獻[8]提出了一種無窗隊列管理技術來避免傳統同步顯式ACK和停止-等待隱式ACK方案的問題，還執行一種區分爭用控制，以減少任何必要的分組重傳帶來的擁塞；文獻[9]提出了延遲數據包調度方案，但文獻[10]指出，單獨采用延遲調度可能導致次優能量使用，因而提出了一種替代調度算法，算法同時考慮無線電關閉和延遲調度策略。

在傳感器網絡中，事件檢測至關重要。文獻[11]提出的事件到接收器可靠傳輸利用端到端擁塞控制來確保網絡事件可靠地傳輸到接收器；文獻[12]提出了一種改進的AOMDV協議和網絡擁塞控制及能耗均衡策略；文獻[13]提出的擁塞緩解和避免協議采用開環、逐跳后壓解決小時間段的擁塞，以及閉環、多源調節來解決更長時間的擁塞；文獻[14]提出了一種擁塞控制和公平協議。

拓撲控制也是緩解擁塞和確保所需覆蓋的另一種選擇方案。探測環境和自適應休眠[15]就是一種拓撲控制協議，它關閉冗余節點以節省電池功率，只有保持感知覆蓋所需的最小節點數量才能保持運行；文獻[16]提出的覆蓋控制協議采用了類似的思想，但增加了網絡動態配置自身以提供所需覆蓋程度的能力。

針對上述算法的單一目標性和不足，本文提出了一種最大冗余丟棄(maximum redundancy discarding，MRD)的緩沖區管理和覆蓋傳輸(coverage transmission，CT)的數據包調度機制，機制在選擇用于丟棄和傳輸的數據包時利用空間信息來提高覆蓋范圍。算法是完全分布式和應用獨立的，不需要節點間發送信號，僅要求數據包攜帶其源節點的地理位置坐標；仿真實驗結果表明，提出的算法機制能有效提高網絡的覆蓋范圍。

1 問題構建

為簡化起見，考慮監測區域A為一個單位正方形(如果是任意形狀的監測區域，可以將其細分為單位正方形)，其中隨機部署的無線傳感器節點集合為N。令X1、X2、Y1、Y2為獨立的隨機變量，分別表示N中兩個節點的坐標 (X1,Y1) 和 (X2,Y2)。 用R表示兩個節點間的距離，這是一個正方形線拾取問題(square line picking problem，SLPP)[17]。R的概率密度函數為

(1)

R的累積分布函數為

(2)

令γ表示每個節點的感知圓半徑。對于任意兩個節點有R<2γ，如圖1所示，則重疊感測區域為

圖1 相距R且每個傳感器的感知半徑為γ的兩個傳感器

(3)

如果R<2γ且L(R)=0，假設γ<<1，則期望的重疊區域為

(4)

令集合Sj?N包含從N中隨機選擇的j個節點，由這j個節點獲得的總覆蓋率用C(Sj)表示。對于每個節點n∈Sj，n的效用定義為

(C(Sj)-C(Sj(〗n}))/πγ2

(5)

即與其它節點的感知圓沒有重疊的n的感知圓的部分。

令節點s1∈Sj與n的距離為R1(<γ)，n(關于s1)的效用定義為

(6)

考慮Sk(〗n} 中全部節點的感知圓與n的感知圓有重疊的情形，設節點為s1,s2,…,sj且這j個節點與n的距離分別由隨機變量R1,R2,…,Rj給出。由于節點的放置是相互獨立的，所以n的效用為

(7)

如果考慮每個隨機變量R1,R2,…,Rj可以取值的范圍，則有j個重疊節點的n的期望效用為

(8)

如果我們構造Sj使得Sj中的每個節點與n的距離至少為h，則式(7)給出的期望效用就變成

(9)

圖2所示為對于γ=0.12的單位正方形上n的期望效用與h的關系，從上到下的曲線對應于j=1、2、3、4、5、20和100。當增大n與全部其它節點間的最小距離h時，Ej[θ(n)] 增大。對于足夠大的h，節點相距很遠，效用為1。此外，當j增大時，Ej[θ(n)] 就小，因為節點之間可能存在很高的重疊或冗余。

圖2 γ=0.12時的期望效用與h的關系

圖2所示結果為本文提出的緩沖區管理和數據包調度算法提供了啟發。當需要丟棄一個數據包時，就丟棄導致最小h值的數據包，刪除其來增大全部節點間的最小距離。圖2還表明，通過確保隊列中剩余的k個數據包盡可能彼此遠離，則每個數據包的期望效用就更高。同樣，調度算法也能很好地選擇與其它數據包的源節點盡可能遠離的數據包。下面提出利用這些啟發式思想的算法。

2 實現擁塞控制的緩沖區管理和數據包調度

2.1 虛擬隊列

在描述實現基于最大冗余丟棄的緩沖區管理和基于覆蓋傳輸的數據包調度算法之前，先引入虛擬隊列的思想，如圖3所示。從根本上說，虛擬隊列存儲最近傳輸的數據包的最前面部分。假設最前面的數據包的大小僅為總數據包大小的一小部分，則虛擬隊列允許節點以最小內存開銷緩存其傳輸歷史。對于本文后續部分，當需要區分數據和虛擬隊列時，我們將明確說明包含數據的隊列的真實隊列和虛擬隊列。

圖3 虛擬隊列向真實(數據)隊列添加歷史

2.2 最大冗余丟棄的緩沖區管理

MRD的基本思想是：對于任意兩個傳感器節點，由它們報告的數據之間的相關性隨著它們之間的距離的增大而減小。如果節點之間彼此靠得很近，則由兩個節點報告的感測數據將存在很大程度的冗余。在擁塞期間，相比于丟棄靠得很近的節點的數據包，丟棄一組相距很遠的節點的數據包可能會導致更多的信息丟失。

令Q為一個傳感器節點的隊列，它由兩部分構成：一個長度為k個數據包的真實隊列和一個長度為v個數據包的虛擬隊列。將真實隊列和虛擬隊列分別稱為Re(Q) 和Vir(Q)， 還將任意數據包pi的源節點ni稱為Src(pi)，用d(ni,nj) 表示節點ni和nj之間的距離，其中d(·,·) 為歐氏距離函數。為簡化起見，用d(pi,pj) 表示d(Src(pi),Src(pj))， 最后，令D(pi,S)=∑pj∈S(〗pi}d(pi,pj)。

如果當傳入的數據包p到達時Re(Q)是滿的，則采用以下規則找到兩個靠得最近的數據包p1和p2：

(1)p1∈Re(Q)∪{p} 且p2∈Q∪{p},p1≠p2；

(2)?pi∈Re(Q)∪{p} 且?pj∈Q∪{p},pi≠pj，d(p1,p2)≤d(pi,pj)。

丟棄策略如下：

(1)如果p2∈Vir(Q)， 則丟棄p1；

(2)如果p2∈Re(Q)∪{p}， 當且僅當D(p1,Q∪{p})

該緩沖區管理算法的特性是，如果Q是MRD執行之前的隊列，且Q′是丟包之后的隊列，則∑pi,pj∈Qd(pi,pj)≤∑pm,pn∈Q′d(pm,pn)。 因此，當一個傳感器節點遭遇擁塞時，隊列中的空間會偏向于較高效用值的數據包。算法實現的偽代碼如算法1所示。

算法1： 最大冗余丟棄算法實現偽代碼

Receive-Packet(p)

(1)Q為長度為(k+1)+v的隊列， 其中Re(Q)的最大長度為k+1且Vir(Q)的最大長度為v

(2)enqueue(Q,p)

(3)if length[Q]=k+1

(4) then Buffer-MGT(Q)

Maximum-Redundancy-Discarding(Q)

(1)dist←∞

(2)p1←Null

(3)p2←Null

(4)fori←1 to length[Re(Q)]

(5) do forj←i+1 to length[Q]

(6) do ifd(Q[i],Q[j])≤dist

(7) thenp1←i

(8)p2←j

(9)dist←d(Q[i],Q[j])

(10)ifp2>k+1

(11) then discarding(Q[p1])

(12) else ifD(p1,Q)

(13) then discarding(Q[p1])

(14) else discarding(Q[p2])

2.3 覆蓋傳輸的數據包調度

當采用先進先出(first-in first-out，FIFO)調度算法時，調度器總是傳輸來自于隊列頭部的數據包，且在高效用數據包達到之前，可能傳輸大量低效用的數據包。此外，考慮到傳感器節點的低帶寬，高效用數據包傳輸之間的時間間隔可能很大。這個問題可以通過從隊列中選擇具有最高效用的數據包傳輸來解決，所以本節提出一種調度算法——覆蓋傳輸(coverage transmit，CT)，它嘗試選擇最大化覆蓋的數據包傳輸。

盡管尋找具有高效用數據包的基本思想與緩沖區管理問題相似，但它實際上比尋找具有低效用的數據包要復雜得多。這是因為當兩個數據包非常靠近時，重疊或冗余與其它數據包高度無關。然而，只有當一個數據包與所有其它數據包具有最小的感知重疊時，它才有較高的效用。因此，尋找高效用或低冗余數據包需要同時考慮全部數據包，原理如下。

對于每個數據包pi∈Re(Q)， 令Vi={v|v是從Src(pi) 到Src(q)的一個矢量，其中q(Vir(Q) 且d(pi,q)≤2γ}。

圖4 Src(pi)=N時數據包pi的Vi的計算

2.4 數據包超時

由于我們感興趣的是傳感器網絡在最后一個Tc時間段提供的覆蓋，而早于Tc的數據包對覆蓋沒有貢獻。因此，我們從真實隊列中丟棄比Tc更早的數據包。對于虛擬隊列，將超時周期設置為1.5Tc。

3 仿真實驗結果及分析

3.1 仿真環境及設置

仿真采用GloMoSim[18]提供的無線網絡環境，它是一種可擴展仿真系統模型，在層與層之間提供了標準API接口函數，這樣就可在不同層或開發人員之間建立快速的綜合集成，以包含本文的緩沖區管理和調度協議；表1所示為用于GloMoSim仿真的參數設置。對于選擇的參數，網絡密集且感知密度為31.8，因此，平均每個點被31.8個節點覆蓋。僅有一個接收器節點位于正方形區域的中心。每個節點的數據包或事件生成速率為一個數據包/10 s，在600 s的仿真期間是持續恒定的。對于每個傳感器節點，事件生成的起始時間隨機分布在0 s～30 s之間。

表1 用于GloMoSim仿真的參數設置

將虛擬隊列的大小固定為24，這個虛擬隊列長度足夠大，以獲得最好的可能性能；仿真中采用由200個傳感器節點構成的兩個網絡拓撲，以計算得到的靜態路線和平均跳數值分別為5.73和8.23，每個網絡表示隨機分布在一個區域內的節點的可能布局。一個是典型的較開放的區域，有最小的無線電干擾(稱為網絡I)，一個是在雜亂環境中，在這種環境中，大量障礙物阻擋無線電信號，干擾節點的視距通信(稱為網絡II)；一般來說，在雜亂環境的網絡中的數據包必須進一步傳輸到達接收器。

將整個仿真時間間隔劃分為不相交的間隔，每個間隔Tc(s)。將任意Tc間隔的定時覆蓋定義為傳感器字段的百分比，該傳感器字段由接收器在該間隔中接收到的數據包覆蓋，且該數據包在小于Tc前生成。這個指標度量了網絡為被監測區域提供最新數據的能力；平均定時覆蓋為測得的全部定時覆蓋值的平均值。為便于比較，采用覆蓋增益指標，定義為通過緩沖區管理和調度算法獲得的平均定時覆蓋相對于通過丟尾(drop-tail,DT)和FIFO獲得的平均定時覆蓋的比值，即得到的結果圖形是通過組合C2、C3和C4獲得的覆蓋與組合C1獲得的覆蓋的比值，4種緩沖區管理和調度算法的組合如下：

C1：DT和FIFO；

C2：MRD和FIFO(即MRD+FIFO)；

C3：CT和DT(即CT+DT)；

C4：MRD和CT(即MRD+CT)。

在仿真中，改變數據隊列長度D從8到64個數據包，考慮到一般性，仿真選取隊列長度D=8和隊列長度D=64，帶寬β從38.4 kbps到153.6 kbps。

3.2 仿真實驗結果

圖5所示為網絡I和網絡II對于不同帶寬的數據包傳輸比。從圖5可見，對于相同的網絡帶寬，通常網絡I比網絡II有更低的包丟失。對于兩個網絡來說，當帶寬為38.4 kbps時，數據包傳輸比低于10%，當帶寬為153.6 kbps時，網絡II仍然只傳輸30%左右的數據包，而網絡I可傳輸80%以上的數據包。當然，這些結果與所采用的緩沖區管理和調度算法無關，只要不過早的丟棄且調度是工作守恒的。然而，當目標是最大化網絡覆蓋時，緩沖區管理和調度算法將產生很大差別，特別是在網絡II中，包丟失很高。

圖5 接收器接收的數據包百分比

圖6所示為對于網絡I、隊列大小分別為8和64個數據包時的覆蓋增益隨帶寬的變化關系。可見，對于較小的隊列大小和帶寬，緩沖區管理算法的影響最為明顯，如對于仿真的緩沖區大小D=8和最低的帶寬38.4 kbps，采用了MRD的組合算法MRD+CT和MRD+FIFO分別獲得了最大1.36和1.28的增益，采用了CT的DT(即CT+DT)獲得了最大1.24的增益。而隨著帶寬的增大，增益開始下降，且當帶寬達到115.2 kbps時，全部組合算法的增益基本保持不變，這是因為當帶寬較小時，同樣的數據包傳輸隊列會出現擁塞，如果采用了本文的緩沖區管理和覆蓋傳輸算法，就會有效地提高覆蓋增益。而當帶寬增大時，同樣的數據包傳輸隊列就不會出現擁塞，所以無論哪種組合算法都不會影響覆蓋增益；當D=64時，MRD+FIFO幾乎沒有增益，而MRD+CT和CT+DT仍然獲得了較高的增益，但當帶寬達到76.8 kbps時，增益開始下降，最后達到平衡；總的來說，MRD和CT的組合在仿真的整個緩沖區大小和帶寬范圍內執行最好。一般而言，覆蓋傳輸的數據包調度起著更重要的作用，每個數據包的傳輸都需要調度，而MRD僅在緩沖區滿時才執行。

圖6 不同隊列長度時網絡I的覆蓋增益與帶寬的關系

圖7所示為對于網絡II得到的覆蓋增益。網絡II由于其到接收器較長的平均節點距離，因而有更高的包丟失，且通常增益更大。對于較小的緩沖區大小和較低的帶寬，緩沖區管理更重要，對于較大的緩沖區和較高的帶寬，數據包調度非常有用。因此，在存在較高包丟失的情況下，采用覆蓋感知緩沖區管理和數據包調度算法可以提高覆蓋增益的性能。同樣，MRD和CT組合在仿真的整個緩沖區大小和帶寬范圍內執行最好。

圖7 不同隊列長度時網絡II的覆蓋增益與帶寬的關系

4 結束語

針對無線傳感器網絡中的擁塞控制和覆蓋率提高，本文提出了一種最大冗余丟棄的緩沖區管理和覆蓋傳輸的數據包調度機制；仿真實驗結果表明，在大多數情況下，采用MRD和CT獲得了最佳覆蓋增益；一般情況下，很難獲得節點精確的位置坐標，所以對于未來的研究，我們將進一步研究如何獲得節點近似坐標位置的技術和在這種情況下的算法性能，以及與精確位置坐標下的性能對比。