一種基于動態(tài)虛簇頭的WSN擁塞控制改進算法

胡平霞

摘要：針對多跳分簇層次結構WSN模型中簇頭出現(xiàn)的擁塞問題，該文提出了一種基于動態(tài)虛簇頭的擁塞控制改進算法，采用平均隊列長度和擁塞度兩個參數(shù)檢測擁塞，通過簇內(nèi)和簇外采取不同的機制解除和緩解擁塞，仿真實驗結果表明該算法在丟包率、網(wǎng)絡吞吐量、數(shù)據(jù)傳輸時延上都有較好的性能。

關鍵詞：WSN；分簇結構；動態(tài)虛簇頭；擁塞控制

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2015）20-0168-04

Congestion Control Algorithm Based on Dynamic Virtual Cluster Head

HU Ping-xia

（Journal of Hunan Environment-Biological Polytechnic， Hengyang 421001， China）

Abstract： Aiming at the congestion problem of cluster head in the WSN model of multi-hop clustering hierarchy， this paper presents an improved Congestion Control algorithm based on Dynamic Virtual Cluster head（CCDVC） to release network congestion. The occurrence of congestion is detected by the average queue length and the congestion degree， different algorithms are taken between inner-cluster and extra-cluster to eliminate congestion and release congestion， the simulation results show that the proposed algorithm performance better in packet loss rate， network throughput and data transmission delay.

Key words： WSN； clustering structure； dynamic virtual cluster head； congestion control

1 引言

無線傳感器網(wǎng)絡（Wireless Sensor Network， WSN）是由部署在監(jiān)測區(qū)域內(nèi)大量低成本且具有傳感、數(shù)據(jù)處理和通信能力的傳感器節(jié)點 （sensor nodes）、基站（Sink）以及任務管理用戶通過自組織方式形成的網(wǎng)絡[1]。隨著物聯(lián)網(wǎng)技術、無線網(wǎng)絡技術發(fā)展的日新月異，WSN廣泛應用于當今社會各個領域，高密度、大規(guī)模的應用使WSN無法承受負載所產(chǎn)生的擁塞問題已經(jīng)成為WSN應用的束縛?；诜执亟Y構的WSN由于采用了合理、有效的分層路由協(xié)議在WSN應用中突顯出優(yōu)勢，這也成為該領域研究熱點之一。

目前國內(nèi)外研究人員提出針對 WSN 的擁塞控制算法集中在CODA[2]、 ESRT[3]、Fusion[4]、 Siphon[5]等，其中STCP[6]（Sensor Transmission Control Protocol）和 COMUT[7]（Congestion control for Multi-class Traffic）是基于分簇結構的典型算法。

文獻[6]STCP算法以一定概率在節(jié)點發(fā)送的數(shù)據(jù)包包頭中設置擁塞比特，Sink節(jié)點在收到包含擁塞比特的數(shù)據(jù)包時通告數(shù)據(jù)源節(jié)點減小發(fā)送速率或變更發(fā)送路徑，使網(wǎng)絡擁塞得到緩和或解除。文獻[7]的COMUT 算法各節(jié)點向簇頭周期性地報告估計到的本地流量，簇頭結點在此基礎得到本地流量的估算值，當該值大于設定好的門限值時，表示網(wǎng)絡已經(jīng)發(fā)生了擁塞。本簇簇頭與其它簇簇頭以周期性廣播進行聯(lián)系，以AIMD 的策略對源節(jié)點速率進行調整。這兩種算法都是基于流量控制的，雖然在一定程度上解除了網(wǎng)絡擁塞，但在WSN實時應用環(huán)境中造成實時數(shù)據(jù)發(fā)送不及時或丟失造成損失，網(wǎng)絡吞吐量不穩(wěn)定，數(shù)據(jù)傳輸?shù)臅r延也會增大。

2 WSN分簇結構模型

分簇結構是基于分層的WSN拓撲結構，相對節(jié)點地位平等的平面結構，分簇結構中節(jié)點地位不平等。在分簇結構中節(jié)點被分簇，并定義簇頭節(jié)點[（Cluster Head，CH）]和成員節(jié)點[（ClusterMember，CM）]，。通常一個簇包括一個簇頭結點和多個普通結點為，由簇頭節(jié)點完成本簇內(nèi)部普通節(jié)點的管理和簇內(nèi)數(shù)據(jù)的采集，同時還需完成簇間數(shù)據(jù)轉發(fā)和整體路由更新和維護。成員結點僅負責完成自身數(shù)據(jù)收集和路由維護。

由于WSN分簇結構比平面結構在應用上具有顯著的優(yōu)勢，在高密度、大規(guī)模的WSN應用中已經(jīng)占據(jù)了重要的位置。但簇頭結點負責本簇和簇間的數(shù)據(jù)轉發(fā)，負荷加重容易產(chǎn)生擁塞，給WSN帶來網(wǎng)絡擁塞的問題。針對簇頭結點出現(xiàn)的擁塞問題，本文提出了一種基于動態(tài)虛簇頭的擁塞控制改進算法CCBDC（Congestion Control Algorithm Based on Dynamic Virtual Cluster Heads）。

WSN分簇結構網(wǎng)絡模型中，以一個無向圖[G=（V，E）]來表示節(jié)點和鏈路，其中[V={vi}，i∈L={1，2，…，n}]為WSN節(jié)點集合， [E={eij=（i，j）}]為WSN節(jié)點通信鏈路集合，如果[eij=1]，則表示節(jié)點i與j互為鄰接節(jié)點，兩節(jié)點間存在邊。見圖1，本文使用的網(wǎng)絡模型為兩層結構，成員結點CM將數(shù)據(jù)發(fā)送到簇頭結點CH需經(jīng)過[k（1≤k≤4）]跳。

圖1 兩層分簇結構網(wǎng)絡模型圖

針對上述網(wǎng)絡模型做如下假設：

（1）應用環(huán)境假設：WSN是密度的靜態(tài)網(wǎng)絡，節(jié)點是靜止的（部署后不移動），符合大多數(shù)應用要求；

（2）Sink節(jié)點假設：Sink節(jié)點唯一且位置固定于整個WSN區(qū)域外的某一處；

（3）簇及節(jié)點假設：簇間相對獨立，簇內(nèi)節(jié)點唯一且以[ID（n）]標記；節(jié)點能量用完進入死亡狀態(tài)，不補充能量，簇頭節(jié)點為（CH）儲備更多能量；無輔助定位設施獲知位置信息，算法所需信息從相鄰節(jié)點獲取。

3 WSN擁塞檢測方法

精準、及時的擁塞檢測是擁塞控制的關鍵之一，合理的擁塞檢測應結合多個因素進行判斷。基于分簇結構的WSN擁塞大多數(shù)發(fā)生在簇頭結點（CH），導致其發(fā)生擁塞有以下兩個方面的可能：（1）簇內(nèi)原因：本簇內(nèi)發(fā)生多個節(jié)點頻繁發(fā)送數(shù)據(jù)給簇節(jié)點的情況；（2）簇外原因：簇外多個簇頭節(jié)點同時給本簇頭發(fā)送需轉發(fā)的數(shù)據(jù)的情況。因此擁塞檢測首要明確引起簇頭擁塞的原因才能進行信息反饋。結合以上分析本文采用平均隊列長度和擁塞度兩個參數(shù)來判斷網(wǎng)絡狀態(tài)，并結合簇內(nèi)數(shù)據(jù)包個數(shù)和簇外數(shù)據(jù)包個數(shù)間的比值還確定擁塞原因。

3.1平均隊列長度

為實現(xiàn)擁塞控制，引入平均隊列長度。在每個簇頭緩存中由以下公式計算平均隊

列長度：

[Qave=（1-wq）×Q′ave+wq×q] （1）

[Q′ave]是上一時間點已計算的平均隊列長度；[wq]是權值；[q]是采樣測量時的平均長度。

3.2 擁塞度[C（n）]

節(jié)點存儲分組會對節(jié)點數(shù)據(jù)處理產(chǎn)生壓力，影響其處理分組的能力。節(jié)點擁塞度定義如下：

[C（n）=TsTa] （2）

[Ta=（1-p）×Ta+p×（t-t′）] （3）

[Ts=（1-p）×Ts+p×ts] （4）

使用節(jié)點MAC層接收數(shù)據(jù)包的平均時間和轉發(fā)數(shù)據(jù)包的平均時間之比來衡量擁塞度，其中[t]為本次數(shù)據(jù)包的到達時間，[t′]為上一數(shù)據(jù)包的到達時間，[Ts]為到達節(jié)點MAC層的兩個相鄰數(shù)據(jù)包的平均時間間隔；[Ta]表示數(shù)據(jù)包在本節(jié)點的平均處理時間；[ts]為剛剛發(fā)出的數(shù)據(jù)包的傳輸時間；p是通過經(jīng)驗設定的常量（SenTCP[9]算法中設定為[0.1]，在本文通過反復實驗設定為0.2實驗效果最佳）。擁塞度[C（n）≤1]說明節(jié)點n狀態(tài)正常，反之則表示節(jié)點趨于擁塞。

3.3 擁塞檢測

從擁塞檢測的精準性和節(jié)點耗能代價兩方面考慮，利用三個閾值[α1]、[α2] 和[α3]將節(jié)點緩存隊列分成四個區(qū)：0區(qū)、1區(qū)、2區(qū)和3區(qū)，分別表示安全區(qū)、恢復區(qū)、避免區(qū)、擁塞區(qū)，如圖2所示。

圖2 節(jié)點緩存隊列示意圖

結合平均隊列長度[Qave]通過三個參數(shù)[r1]、[r2] 和[r3]將節(jié)點緩存分成以下四種狀態(tài)，分別表示安全狀態(tài)，恢復狀態(tài)，擁塞避免狀態(tài)、擁塞狀態(tài)，如表1所示：

表1 網(wǎng)絡狀態(tài)表

[[Qave]值大?。?amp;節(jié)點緩存狀態(tài)＼&[Qave]<[r1]＼&安全狀態(tài)＼&[r1]<[Qave]<[r2]＼&恢復狀態(tài)＼&[r2]<[Qave]<[r3]＼&擁塞避免狀態(tài)＼&[Qave]>[r3]＼&擁塞狀態(tài)＼&]

處于安全狀態(tài)表示網(wǎng)絡運行平穩(wěn)，無需進行擁塞檢測；處于恢復狀態(tài)表示節(jié)點負荷大有可能進入擁塞，考慮WSN突發(fā)性因素結合擁塞度[C（n）]進行如下分析：

[C（n）≤1]不做任何處理，由節(jié)點自身調節(jié)恢復到安全狀態(tài)，[C（n）>1]，認為節(jié)點進入準擁塞狀態(tài)，需采用擁塞避免機制；在擁塞避免狀態(tài)直接啟動擁塞避免機制；在擁塞狀態(tài)表示擁塞避免已經(jīng)無效，節(jié)點采取一定策略進行丟包或降低發(fā)送速率以解除擁塞。

在安全狀態(tài)以外的節(jié)點采用數(shù)據(jù)包采樣方法在周期時間T內(nèi)計算簇外數(shù)據(jù)包及簇間數(shù)據(jù)包數(shù)，并根據(jù)二者的比值分析引發(fā)擁塞的原因，見式（5）。通過e的值分析擁塞產(chǎn)生的原因，本文通過反復實驗分析如下：當[01.5]時，擁塞原因為簇間擁塞。

[e=MN] （5）

式中M為來自簇內(nèi)CM節(jié)點的數(shù)據(jù)包總數(shù)，N指來自簇間CH節(jié)點的數(shù)據(jù)包總數(shù)。

3.4 最短路徑樹[（SPT）]定義和說明

最短路徑樹[（Shortest path tree，SPT）]是樹狀拓撲結構最合適用于WSN的一種，通過找到最短路徑即到目標節(jié)點轉發(fā)跳數(shù)最少的路徑，在網(wǎng)絡環(huán)境相當?shù)那闆r下其具有較低的數(shù)據(jù)傳輸時延。本文[SPT]符號及相關說明如下：

表2 最短路徑樹（SPT）符號和說明

[名稱＼&符號＼&說明＼&跳數(shù)＼&h（n）＼&普通節(jié)點n到簇首節(jié)點的最小跳數(shù)＼&鄰接點跳數(shù)＼&hn（m）＼&普通節(jié)點n的鄰接節(jié)點m到簇首節(jié)點的最小跳數(shù)＼&度數(shù)＼&d（n）＼&普通節(jié)點n與其鄰接節(jié)點相連接的邊數(shù)＼&鄰接點度數(shù)＼&dn（m）＼&普通節(jié)點n的鄰接節(jié)點m的度數(shù)＼&鄰接點集＼&N（n）＼&普通節(jié)點n的鄰接節(jié)點集＼&父節(jié)點集＼&F（n）＼&普通節(jié)點n的父節(jié)點集：[F（n）=uu∈V?u∈N（n）?h（u）=h（u）-1]＼&子樹節(jié)點個數(shù)＼&t（n）＼&以普通節(jié)點n為根的子樹中節(jié)點個數(shù)＼&]

每個傳感器節(jié)點都有一個唯一的ID號，根據(jù)節(jié)點的度數(shù)d（n）以及ID號的大小可以對G=（V，E）中任意節(jié)點n的父節(jié)點集F（n）構造一個全序集（F（n），[?]），公式（6）如下：

[m?n=ID（m）

4 基于CCBDC算法的WSN擁塞控制算法

本算法的主要思想是在通過在簇內(nèi)的尋找動態(tài)虛擬簇頭結點為本簇內(nèi)的簇頭節(jié)點分流。通過簇內(nèi)擁塞分析和檢測使用最短路徑樹算法尋找動態(tài)VCH，形成以此節(jié)點為根的子樹，重新計算樹成員節(jié)點的路由，樹成員節(jié)點通過此路由發(fā)送數(shù)據(jù)到VCH；簇間通過動態(tài)虛擬簇頭分流來緩解網(wǎng)絡擁塞。根據(jù)分析，簇頭節(jié)點最容易發(fā)生擁塞，在本算法中，簇頭節(jié)點周期性的運行著此算法，VCH根據(jù)網(wǎng)絡情況動態(tài)變化。周期內(nèi)算法步驟偽代碼表示如下：

（1）開始

（2）擁塞檢測

（3）是否發(fā)生擁塞，是轉入下一步，否轉入結束

（4）簇內(nèi)產(chǎn)生擁塞，轉入一下步，否則是轉入（9）

（5）通過最短路徑算法尋找VCH

（6）重定向路由

（7）擁塞緩解

（8）是否發(fā)生簇間擁塞，是轉入（10），否轉入結束

（9）通過能量算法尋找VCH

（10）構造多元路徑

（11）擁塞緩解

（12）銷毀多元路徑

（13）結束

算法開始進入擁塞檢測，產(chǎn)生擁塞，根據(jù)擁塞檢測算法判斷，若是簇內(nèi)擁塞，通過最短路徑算法尋找VCH，并重新計算路由更新節(jié)點路由，擁塞緩解后要判斷是簇間是否有擁塞發(fā)生，是則進行簇間控制，否則本輪擁塞處理結束，網(wǎng)絡進入平穩(wěn)狀態(tài)；如果擁塞不是簇內(nèi)原因引起，進入簇間控制，通過能量狀態(tài)來尋找VCH并進行簇間擁塞處理。若沒有檢測到擁塞返回開始，等待下一個周期的檢測。

5 算法實驗仿真與結果分析

5.1仿真平臺及參數(shù)設置

根據(jù)研究內(nèi)容及特點，本文選擇NS2網(wǎng)絡仿真平臺，網(wǎng)絡環(huán)境及參數(shù)設置見表

表3 仿真實驗參數(shù)

[仿真參數(shù)＼&數(shù)值＼&仿真參數(shù)＼&數(shù)值＼&Mac層協(xié)議＼&IEEE802.11＼&鏈路帶寬（bps）＼&1M＼&節(jié)點頻率＼&914MHz＼&發(fā)送功率＼&550mW＼&接收功率＼&395mW＼&監(jiān)聽功率＼&360mW＼&節(jié)點最大傳輸距離＼&15m＼&部署范圍＼&100m *100m＼&節(jié)點數(shù)目＼&1000＼&簇首數(shù)目＼&25＼&緩存區(qū)容量B＼&200個數(shù)據(jù)包＼&數(shù)據(jù)包大小＼&100bytes＼&α1、α2、α3＼&0.7、0.85、0.95＼&仿真時間＼&60s＼&]

本文從網(wǎng)絡吞吐量、數(shù)據(jù)傳輸時延及丟包率三個方面對算法在NS2網(wǎng)絡仿真平臺上進行了仿真，并對STCP和COMUT算法作對比實驗。

5.2 仿真結果與分析

在仿真實驗結束后，通過調用自動生成的[Trace]文件得到實驗中的反映狀態(tài)的數(shù)據(jù)和實驗結果數(shù)據(jù)。借助專業(yè)繪圖軟件[Origin]根據(jù)[Trace]文件中的數(shù)據(jù)形成數(shù)據(jù)圖表對各項性能指標進行分析。

（1）網(wǎng)絡吞吐量仿真實驗及結果分析

在本實驗中，通過10個源節(jié)節(jié)點不斷給Sink節(jié)點發(fā)送數(shù)據(jù)，仿真時間設置為60秒，網(wǎng)絡吞吐量即為統(tǒng)計Sink節(jié)點收到的數(shù)據(jù)包個數(shù)，通過修改速率重復實驗，實驗結果如圖3所示：

圖3 三種算法在不同速率下的網(wǎng)絡吞吐量

從實驗結果數(shù)據(jù)圖中可以得到三種算法在不同的發(fā)送速率下網(wǎng)絡吞吐量的情況對比，當節(jié)點發(fā)送速率小于時，吞吐量相差不大且隨著發(fā)送速率增大而以線性形式增長。當發(fā)送速率大于0.6packet/s時，CCBDC算法的吞吐量明顯大于COMUT、STCP算法兩算法的吞吐量，通過分析后兩種算法采取降低速率的方法緩解擁塞，而CCBDC算法采用了精準有效的簇間或簇內(nèi)的擁塞避免機制，吞吐量隨速率的增加略有增加并趨于平穩(wěn)。

（2）丟包率仿真實驗及結果分析

在此實驗中，通過設置普通節(jié)點的數(shù)據(jù)包發(fā)送速率，統(tǒng)計各節(jié)點到達包的個數(shù)、應達包個數(shù)為節(jié)點發(fā)送速率、節(jié)點數(shù)目、仿真時間三者的乘積，應達包和到達包之差得到丟包個數(shù)，其中丟包率按下公式計算：

[丟包率=丟包書目節(jié)點總發(fā)包數(shù)] （7）

圖4 三種算法在不同速率下的丟包率

實驗結果如圖4所示，從實驗結果數(shù)據(jù)圖中可以得到當數(shù)據(jù)包發(fā)送速率高于0.6packet/s時，CCBDC算法在丟包率這下指標上明顯強于COMUT算法和STCP算法，難過分析后兩種算法通過降低速率來避免丟包，CCBDC算法是采用調整網(wǎng)絡結構措施來避免擁塞造成丟包，因此在本次實驗中CCBDC算法性能強于COMUT算法和STCP算法。

（3）數(shù)據(jù)傳輸時延仿真實驗及結果分析

本次實驗通過遠距離（距離Sink節(jié)點）普通節(jié)點分別在不同速率下向目標Sink節(jié)點傳送數(shù)據(jù)包，計算數(shù)據(jù)包從源節(jié)點發(fā)送到Sink節(jié)點接收時間，修改速率反復實驗，得到平均傳輸時延，實驗結果如結果如圖5所示：

圖5 三種算法的數(shù)據(jù)傳輸時延

從實驗結果數(shù)據(jù)圖中可以得到三種算法的傳輸時延因發(fā)送速率的增加而加大，發(fā)送速率在0.6packet/s以下時，在種算法性能相當；當發(fā)送速率在0.6packet/s和 0.65packet/s之間時，由于此網(wǎng)絡狀態(tài)下，CCBDC正在尋找虛擬簇頭節(jié)點以及構造多元路徑增加了開銷，因此 CCBDC算法的傳輸時延會略大于其他兩種算法；當發(fā)送速率在0.65packet/s以上時，CCBDC算法虛擬簇頭已經(jīng)生成，擁塞緩解或減輕，因此CCBDC算法在速率0.65packet/s以上時在傳輸時延上明顯優(yōu)于COMUT算法和STCP算法。

6總結

本文在基于分簇結構的WSN基礎上，提出一種基于動態(tài)虛簇頭的擁塞控制算法處理網(wǎng)絡擁塞問題。采用平均隊列長度和擁塞度兩個參數(shù)來判斷網(wǎng)絡狀態(tài)，并結合簇內(nèi)數(shù)據(jù)包個數(shù)和簇外數(shù)據(jù)包個數(shù)間的比值還確定擁塞原因。通過構造多元路徑解決簇間擁塞及在簇內(nèi)尋找虛簇頭解決簇內(nèi)擁塞。通過仿真實驗平臺，與COMUT算法、STCP算法進行對比性實驗并分析實驗結果，本算法在網(wǎng)絡吞吐量、數(shù)據(jù)傳輸時延及丟包率三個方面有所改善，但是由于實驗都是在仿真平臺完成，對比實際應用環(huán)境的復雜性，存在著一定的局限性，如何將算法應用于實際應用環(huán)境中這是以后努力的方向。

參考文獻：

[1] 任豐原， 黃海寧， 林 闖. 無線傳感器網(wǎng)絡[J]. 軟件學報， 2003，14（7）：1284-1291.

[2] Wan C Y， Eiseman S B， Cambell A T. CODA： CongestionDetection and Avoidance in Sensor Networks[C].Proc. of the1st ACM Conference on Embedded Networked Sensor Systems.Los Angeles， USA： [s. n.]， 2003.

[3] Sankarasubramaniam Y， Akan O B， Akyidiz I F. ESRT： Event-tosink Reliable Transport in Wireless Sensor Networks[C].Proc. Of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing. Annapolis， USA： [s. n.]， 2003.

[4] Hull B， Jamieson K， Balakrishnan H. Mitigating Congestion in Wireless Sensor Networks[C].Proc. of the 2nd ACM Conf. on Embedded Networked Sensor Systems. Baltimore， USA： [s. n.]，2004.

[5] Wan C Y， Eisenman S B， Campbell A T， et al. Siphon： Overload Traffic Management Using Multi-radio Virtual Sinks[C].Proc. Of the 13th ACM Conf. on Embedded Networked Sensor Systems.·New York， USA： [s. n.]， 2005.

[6] Iyer Y G， Gandham S， Venkatesan S. STCP： A Generic Transport Layer Protocol for Wireless Sensor Networks[C].Proc. of the 14th International Conference on Computer Communication. San Diego， USA： [s. n.]， 2005.

[7] Karenos K， Kalogerak V， Krishnamurthy S V. Cluster-based Congestion Control for Supporting Multiple Classes of Traffic in Sensor Networks[C].Proc. of the 2nd IEEE Workshop on Embedded Networked Sensors. Washington D. C.， USA： [s. n.]， 2005.

[8]劉永帥，無線傳感器網(wǎng)絡擁塞控制的研究[D].燕山大學，2011.

[9]Wang C， Sohraby K，Li B.SenTCP：A Hop-by-Hop Congestion Control Protocol for Wireless Sensor Network[C].Proceedings of the 24th IEEE Conference on Computer Communications.USA：IEEE Computer Society， 2005.

[10]Charalambos Sergiou ， Vasos Vassiliou， Aristodemos Paphitis.Hierarchical Tree Alternative Path （HTAP） algorithm for congestion control in wireless sensor networks[C]. Ad Hoc Networks 2013 （11）： 257-272.