裴曉黎 劉志坤 劉 忠

（1.海軍裝備部駐上海地區(qū)軍事代表局 上海 200083）（2.海軍工程大學(xué)電子工程學(xué)院 武漢 430033）

1 引言

無線傳感器網(wǎng)絡(luò)已在民用、軍事領(lǐng)域得到了廣泛的應(yīng)用，能量問題是制約其正常運行的一個瓶頸：其單個節(jié)點能量有限，且難以進行能量補充。分簇協(xié)議把網(wǎng)絡(luò)節(jié)點劃分為多個簇，每個簇包含一個簇頭（cluster head）節(jié)點和多個簇成員（cluster member）節(jié)點，簇內(nèi)節(jié)點間的通信由簇頭控制。合理的分簇協(xié)議可以有效地平衡節(jié)點的能量消耗，延長網(wǎng)絡(luò)的生存周期［1］。

簇組織可分為兩類：靜態(tài)簇和動態(tài)簇。其中靜態(tài)簇在完成組建后其結(jié)構(gòu)不再發(fā)生改變，具有組建方法簡單的優(yōu)點，但是適應(yīng)性較差。而動態(tài)簇由目標事件激發(fā)組建，其位置和規(guī)模由事件的具體狀態(tài)決定，因此具有很好的適應(yīng)性和生存能力，其組建方法相應(yīng)的也比較復(fù)雜。動態(tài)簇的這種特點，使其特別適用于目標定位跟蹤等領(lǐng)域［2～3］。目前，相對于在靜態(tài)分簇協(xié)議方面的大量研究成果［4～5］，對于動態(tài)分簇的研究顯得相對較少。文獻［6］給出了一種基于目標預(yù)測位置的動態(tài)簇組建方法，該方法強烈依賴于預(yù)測精度，容易出現(xiàn)目標丟失的情況。文獻［7］介紹了一種多層動態(tài)簇的組建方法，但是該方法管理代價較大。文獻［8］給出了一種基于Voronoi圖的動態(tài)分簇算法，其計算程度復(fù)雜且簇頭選擇方式不盡合理。文獻［9］提出的方法在簇頭選擇時綜合考慮了接收信號強度和節(jié)點剩余能量兩項因素，但是沒有考慮到簇頭與匯聚節(jié)點的距離，并且對簇的規(guī)模沒有做約束。

本文在文獻［9］的基礎(chǔ)上，提出了一種新的動態(tài)分簇協(xié)議，在簇頭選擇時增加了簇頭與匯聚節(jié)點距離這一因素，同時給出了簇規(guī)模的限定方法，仿真結(jié)果表明，該協(xié)議能夠有效地節(jié)省能量，延長網(wǎng)絡(luò)壽命。

2 模型及問題描述

2.1 網(wǎng)絡(luò)模型

本文提出的動態(tài)分簇協(xié)議針對的網(wǎng)絡(luò)模型如下：

1）除匯聚節(jié)點外，節(jié)點屬于同構(gòu)節(jié)點，具有相同的初始能量、信息處理能力、探測半徑和通信半徑，并且通信半徑遠大于探測半徑；

2）發(fā)射功率在允許范圍內(nèi)可調(diào)；

3）節(jié)點的位置固定，其自身的位置信息已知，可以通過GPS設(shè)備或者節(jié)點自定位算法［10］獲得，本文不討論WSN節(jié)點自定位問題；

4）匯聚節(jié)點唯一且位置固定，各網(wǎng)絡(luò)節(jié)點到匯聚節(jié)點的距離已知，可以通過節(jié)點與匯聚節(jié)點的信息交換獲取。

2.2 能量模型

節(jié)點的能量消耗主要用于數(shù)據(jù)收發(fā)和處理。文獻［13］指出，對于服從四次方衰減的無線電，在100m距離上傳輸1kb數(shù)據(jù)所消耗的能量大致相當于在100MIPS／W處理器上執(zhí)行300萬個指令，即節(jié)點的數(shù)據(jù)處理能耗要遠小于數(shù)據(jù)收發(fā)能耗，基于此結(jié)論，本文主要考慮數(shù)據(jù)收發(fā)的能耗。

按照時間順序?qū)Υ仡^和簇成員的能耗進行分析：

簇成員的能量消耗可分為：在構(gòu)建簇時，接收簇頭當選信息；簇構(gòu)建完成后，向簇頭節(jié)點發(fā)送目標的相關(guān)信息；簇壽命結(jié)束時，接收簇重組信息。

簇頭的能量消耗可分為：在構(gòu)建簇時，接收前一簇頭發(fā)出的簇重組信息，向簇成員發(fā)送當選信息；簇構(gòu)建完成后，接收簇成員的目標信息，進行數(shù)據(jù)處理估計目標狀態(tài)，將數(shù)據(jù)處理結(jié)果發(fā)送給匯聚節(jié)點；簇壽命結(jié)束時，發(fā)送簇重組信息。

本文采用無線通信模型，根據(jù)傳輸距離門限，分別采用自然空間模型和多徑衰落模型，傳感器節(jié)點發(fā)送kbit數(shù)據(jù)傳輸dm距離消耗的能量Etx為［14］：

傳感器節(jié)點接收kbit數(shù)據(jù)所需要的能量ERx為

其中，Eelec是發(fā)送電路和接收電路的能量消耗；εfs和εmp分別是自由空間模型和多徑衰減模型中功率放大器的能量消耗，d0是傳輸距離門限，決定了衰減模式。

2.3 信號衰減模型

采用文獻［15］的目標信號衰減模型：假定目標的信號強度隨距離成指數(shù)衰減，節(jié)點i在t時刻接收到的信號強度Si（t）為

其中，S表示目標源的信號強度；ri（t）是t時刻目標到節(jié)點i的距離；α是信號強度的衰減指數(shù)，一般取值為2；ni是測量噪聲。

2.4 問題描述

合理的動態(tài)分簇協(xié)議應(yīng)該遵循以下原則：

1）節(jié)點采集到的信號強度較大。較強的信號說明該節(jié)點距離目標較近，獲得的信息更可靠，數(shù)據(jù)處理更準確；

2）節(jié)點的剩余能量較多。因為簇頭節(jié)點要擔(dān)負更多的管理和通信任務(wù)，消耗的能量也相應(yīng)的更多，如果當選的簇頭節(jié)點能量不足，會造成簇組織的維持時間縮短，造成任務(wù)執(zhí)行失敗。

3）節(jié)點與匯聚節(jié)點的距離相對較近。簇頭節(jié)點根據(jù)簇成員節(jié)點匯報的目標信息進行初步的處理后，要將結(jié)果發(fā)送給匯聚節(jié)點，如果簇頭距離匯聚節(jié)點過遠，信號的發(fā)送將消耗大量的能量，會使得簇頭很快因能量耗盡而死亡。

4）簇頭節(jié)點激活的范圍要適當。適當就是指簇的規(guī)模不能太大，這會造成簇邊界成員與簇頭的通信距離過遠，此外，過多的成員節(jié)點與簇頭信息交互有可能造成不必要的數(shù)據(jù)沖突；簇的規(guī)模又不能太小，這會造成簇的檢測范圍減小，簇頭頻繁交接，造成不必要的能量消耗。因此，需要通過強制手段限定簇范圍，達到確保簇具有局部性的目的。

第1）～3）條原則，本文通過對簇頭選取計時器的合理設(shè)置來滿足，第4）條原則，則給出一種基于任務(wù)需求的自適應(yīng)簇范圍劃分方法。

3 動態(tài)分簇協(xié)議

本文提出的動態(tài)分簇協(xié)議，其工作過程如下：

1）當目標事件在監(jiān)測區(qū)域內(nèi)發(fā)生后，檢測到該事件的節(jié)點開始組簇，組簇過程包括簇頭競選和簇成員加入；2）簇成員將采集到的相關(guān)目標信息發(fā)送給簇頭節(jié)點；3）簇頭接收各成員發(fā)送的事件信息，處理后發(fā)送給匯聚節(jié)點；

4）簇壽命到期時，簇頭發(fā)出簇重組信息，組建新簇。

下面著重闡述協(xié)議的簇頭競選、簇成員加入以及簇重組等環(huán)節(jié)。

3.1 簇頭競選

當發(fā)現(xiàn)目標事件在監(jiān)測區(qū)域范圍內(nèi)發(fā)生時，傳感器網(wǎng)絡(luò)中信號強度超過檢測門限s0的節(jié)點成為簇頭候選節(jié)點，并廣播自身的位置和測量值。每個簇頭候選節(jié)點設(shè)置一個選取計時器（backoff timer），如果簇頭候選節(jié)點i的計時器終止時還沒有接收到其它節(jié)點的簇頭當選信息，那么i節(jié)點就向其它節(jié)點發(fā)送當選信息，成為簇頭。候選節(jié)點最終能否成為簇頭由選取計時器決定，設(shè)計計時器時權(quán)衡節(jié)點接收信號強度，節(jié)點剩余能量及節(jié)點與匯聚節(jié)點的距離三個因素。計時器的長度計算公式為

如果節(jié)點i的計時器終止前未收到簇頭當選消息，那么該節(jié)點就向其他節(jié)點發(fā)布當選消息，成為簇頭。當選信息包含簇頭節(jié)點的ID、位置信息和時間信息等。如果節(jié)點i在其計時器終止前接收到簇頭當選消息，則該節(jié)點停止競選進程，成為簇成員節(jié)點，存儲簇頭節(jié)點的ID等各種信息，并通過調(diào)整本地時鐘與簇頭節(jié)點實現(xiàn)時鐘同步。

3.2 簇成員加入

對于簇范圍的選擇，許多文獻將其簡單的以節(jié)點通信范圍劃分［16～17］，這種劃分無法保證簇的局部性，不利于節(jié)省能量。而如果具體指定簇范圍，由于網(wǎng)絡(luò)中節(jié)點的隨機分布和目標出現(xiàn)位置的不確定性，有可能造成簇內(nèi)的節(jié)點滿足不了任務(wù)要求。因此，本文提出一種自適應(yīng)的劃分方法來確定簇范圍。首先對探測到目標的節(jié)點數(shù)量設(shè)置一個閾值區(qū)間［NminNmax］，如果簇頭初始激活范圍內(nèi)的活躍節(jié)點數(shù)Na＜Nmin，則擴大激活半徑Ra，尺度為可調(diào)半徑梯度Radjust；如果Na＞Nmax，則縮小Ra。調(diào)整過程持續(xù)到Na∈［NminNmax］為止，此時對應(yīng)的Ra即為簇半徑。Nmin和Nmax可根據(jù)實際應(yīng)用中的具體需求確定，其基本原則是使簇頭能獲得足夠的目標信息，滿足對目標狀態(tài)信息獲取的要求。

分析該算法可以發(fā)現(xiàn)：當簇頭周圍活躍節(jié)點數(shù)量多時，就可以選擇較小的激活半徑，以減少通信造成的能量消耗；當活躍節(jié)點數(shù)量少時，簇頭就選擇較大的激活半徑以保證跟蹤質(zhì)量。從而自適應(yīng)地選擇簇范圍。

3.3 簇重組

當簇壽命結(jié)束時，簇頭發(fā)出重組信息，重組信息里包含了當前對目標事件的監(jiān)測信息，比如目標位置，速度和方向等，便于下一個簇的任務(wù)完成，以保證連續(xù)性。簇壽命結(jié)束的標志是當前簇?zé)o法滿足監(jiān)測任務(wù)要求。比如在二維平面內(nèi)，至少需要三個不在同一直線上的傳感器才能完成對目標的定位，在三維空間內(nèi)，完成定位至少需要四個不在同一平面內(nèi)的傳感器，因此，為了保證簇頭能獲得足夠的冗余信息，將簇生命結(jié)束的標志定為：簇內(nèi)接收到目標信號的成員節(jié)點數(shù)Na≤Nmin的時刻。為了避免由于目標機動造成簇頭誤以為壽命結(jié)束，發(fā)出不恰當?shù)闹亟M信息，在此設(shè)置一個簇壽命結(jié)束檢測計時器τdet，其長度等于系統(tǒng)允許的分簇時延上限τmax。當簇頭發(fā)現(xiàn)能夠檢測到目標的成員個數(shù)不超過Nmin時，啟動檢測計時器，如在計時器τdet結(jié)束時，能夠探測到目標的簇成員節(jié)點數(shù)仍不超過Nmin，簇頭就發(fā)出重組信息；如果在計時器τdet結(jié)束前Na的個數(shù)超過Nmin，則取消τdet，繼續(xù)進行目標定位跟蹤。簇成員節(jié)點在收到重組信息之后，清除存儲的當前簇頭信息，退出簇，而后判斷自身能否檢測到目標信號，如果能，則根據(jù)簇頭競爭計時器的長短，參與新簇頭的選舉；如果沒有檢測到目標信號，則轉(zhuǎn)入休眠狀態(tài)。

為了避免簇重組中斷，造成目標丟失，有必要加入目標丟失檢測機制和目標恢復(fù)機制［9］。

目標丟失檢測機制：簇頭發(fā)出簇重組信息后，設(shè)置一個目標丟失檢測計時器，其長度等于允許的分簇時延上限τmax。如果在此計時器終止前收到下一簇頭的當選信息，則取消此計時器，存儲下一個簇頭信息，作為簇成員加入。如果在此計時器到期時仍未收到下一個簇頭當選信息，則啟動目標恢復(fù)機制。

目標恢復(fù)機制：簇頭提高發(fā)射功率，激活更大范圍內(nèi)的節(jié)點，被激活的節(jié)點感應(yīng)目標，競選簇頭，重新組簇。如果仍然沒有新簇頭產(chǎn)生，則認為目標已不在網(wǎng)絡(luò)監(jiān)測區(qū)域內(nèi)。

4 仿真及性能評估

為了對本文提出的分簇協(xié)議性能進行評估，在相同條件下對本文協(xié)議和文獻［9］提出的協(xié)議進行仿真比較。實驗中取200m＊200m的區(qū)域，區(qū)域頂點的坐標分別為（0，0）、（200，0）、（200，200），（0，200）。隨機部署的節(jié)點的數(shù)為200個，q0取2J，Eelec取50nJ／bit，εfs取10pJ／bit／m2，εmp取0.0013pJ／bit／m4，d0取75m，數(shù)據(jù)包取4000bit，Nmin取10，Nmax取15。α1、α2、α3分別取0.3、0.5、0.2。目標信號源強度取100，檢測門限s0取0.5。

在簇頭競選時，本文提出的協(xié)議考慮到了與匯聚節(jié)點距離這一因素，其目的是降低簇頭向匯聚節(jié)點發(fā)送數(shù)據(jù)時的能量消耗。實驗中匯聚節(jié)點的橫坐標取100m不變，縱坐標依次從300m延伸到900m，即匯聚節(jié)點到網(wǎng)絡(luò)區(qū)域的距離不斷增加，節(jié)點的剩余能量服從［0，2］均勻分布，對兩種協(xié)議選出的簇頭與匯聚節(jié)點通信產(chǎn)生的能耗進行比較。

從圖中可以看出，隨著匯聚節(jié)點距離網(wǎng)絡(luò)越來越遠，兩種協(xié)議選出的簇頭與匯聚節(jié)點通信所產(chǎn)生的能耗都增加，本文提出的簇頭競選方案（協(xié)議2）在各個匯聚節(jié)點的位置消耗的能量都低于文獻［9］的簇頭競選方案（協(xié)議1），并且隨著匯聚節(jié)點距離的增大，能量節(jié)省的效果越明顯。說明在簇頭選舉時加入與匯聚節(jié)點距離這一因素對降低能耗起到了積極的效果。

兩種協(xié)議下節(jié)點死亡速度與網(wǎng)絡(luò)生存時間的對比仿真如圖2所示。仿真中匯聚節(jié)點的位置取（100，350）不變。

圖1 簇頭與匯聚節(jié)點的通信能耗

圖2 節(jié)點存活個數(shù)與網(wǎng)絡(luò)生存時間

仿真結(jié)果表明，協(xié)議1第一個節(jié)點死亡的時間出現(xiàn)在第75輪，協(xié)議2第一個節(jié)點死亡的時間出現(xiàn)在第102輪，新協(xié)議延長了36%。網(wǎng)絡(luò)的運行輪數(shù)從452輪延長到了688輪，延長了52.2%。說明本文提出的協(xié)議明顯延長了網(wǎng)絡(luò)壽命。分析其原因：一方面是由于本文的協(xié)議考慮到了簇頭與匯聚節(jié)點的距離因素，節(jié)省了簇頭向匯聚節(jié)點傳送數(shù)據(jù)的能量；另一方面是因為對簇的范圍進行了限制，節(jié)省了簇成員與簇頭節(jié)點之間數(shù)據(jù)發(fā)送的能量。

5 結(jié)語

本文提出了一種針對無線傳感器網(wǎng)絡(luò)的動態(tài)分簇協(xié)議，該協(xié)議在簇頭競選時綜合考慮了接收信號強度、剩余能量、與匯聚節(jié)點距離三個因素，在簇成員加入時，根據(jù)具體任務(wù)要求對簇規(guī)模進行了適當?shù)南拗疲軌蜃赃m應(yīng)的調(diào)節(jié)動態(tài)簇范圍。仿真實驗表明，該協(xié)議能有效地節(jié)省節(jié)點能量，延長網(wǎng)絡(luò)壽命。下一步的工作應(yīng)研究如何合理的對影響簇頭選舉的三個因素設(shè)置權(quán)重。

［1］沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報，2006，17（7）：1588－1600.

［2］申興發(fā)，李鴻斌，趙軍，等.面向目標跟蹤的傳感器網(wǎng)絡(luò)分布式組管理機制［J］.儀器儀表學(xué)報，2007，28（6）：966－972.

［3］林金朝，李國君，周曉娜，等.基于動態(tài)能量管理的無線傳感器網(wǎng)絡(luò)動目標定位跟蹤方法［J］.通信學(xué)報，2010，31（12）：90－96.

［4］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy－efficient communication protocol for wireless microsensor networks［C］／／Proc.of the 33rd Annual Hawaii Int'Conf.on System Sciences.Maui：IEEE Computer Society，2000：3005－3014.

［5］Younis O，F(xiàn)ahmy S.Heed：A hybrid，energy－efficient，distributed clustering approach for ad－h(huán)oc sensor networks［J］.IEEE Trans.on Mobile Computing，2004，3（4）：660－669.

［6］Yang H，Sikdar B.A protocol for tracking mobile targets using sensor networks［C］／／Proc IEEE Workshop Sensor Network Protocols and Applications，Piscataway，USA，2003：71－81.

［7］Zhang W，Cao G.DCTC：dynamic convoy tree－based collaboration for target tracking in sensor networks［J］.IEEE Transactions on Wireless Communications，2004，3（5）：1689－1701.

［8］Chen W，Hou J C，Sha L Dynamic clustering for acoustic target tracking in wireless networks［J］.IEEE Transactions on Mobile Computing，2004，3（3）：258－271.

［9］鄧克波，劉中.基于無線傳感器網(wǎng)絡(luò)動態(tài)簇的目標跟蹤［J］.兵工學(xué)報，2008，29（10）：1197－1202.

［10］Wang S S，Shih K P，Chang C Y.Distributed direction－based localization in wireless sensor networks［J］.Computer Communications，Elsevier，2007，31（10）：1424－1439.

［11］馬保國，喬玲玲，賈寅波.無線傳感器網(wǎng)絡(luò)研究綜述［J］.計算機與數(shù)字工程，2008，36（9）.

［12］康瑋杰，錢慧，余輪.多頻段無線傳感器網(wǎng)絡(luò)研究綜述［J］.計算機與數(shù)字工程，2010，38（5）.

［13］陳磊，趙寶華.低能耗自適應(yīng)分簇的面向數(shù)據(jù)融合的路由協(xié)議［J］.北京郵電大學(xué)學(xué)報，2009，32（5）：71－74.

［14］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless microsensor networks ［J］.IEEE Transactions on Wireless Communications，2002，1（4）：660－670.

［15］Li D，Hu Y H.Energy based on collaborative source localization using acoustic micro－sensor array［J］.Journal EUROSIP Applied Signal Processing，2003，4：321－337.

［16］Selvakennedy S，Sinnappan S，Yi S.A biologically－inspired clustering protocol for wireless sensor networks［J］.Elsevier Computer Communications （S0140－3664），2007，30（10）：2786－2801.

［17］Fan X N，Song Y L.Improvement on LEACH protocol of wireless senor network［J］.International Conference on Sensor Technologies and Application，2007，5（30）：260－264.