徐祥振，汪成亮

（重慶大學計算機學院信息物理社會可信服務計算教育部重點實驗室，重慶400044）

無線傳感器網絡（WSN）利用大量的傳感器節(jié)點通過無線通信自組織形成網絡，能夠有效地感應、監(jiān)控并傳輸網絡覆蓋區(qū)域的多種信息。由于具有節(jié)點成本低、易于布置等優(yōu)點，WSN在國防軍事、醫(yī)療健康、環(huán)境監(jiān)測等領域得到廣泛應用［1］。然而WSN中的傳感器節(jié)點能量絕大部分情況下只能以電池的方式提供，難以補充能量。并且WSN廣泛應用于偏遠危險地區(qū)，只能采取飛機播散等方式布置節(jié)點，將會出現(xiàn)節(jié)點分布不均勻現(xiàn)象，節(jié)點分布密集區(qū)域同一事件將被多個節(jié)點重復監(jiān)測，將會出現(xiàn)大量冗余數(shù)據(jù)。因此，如何優(yōu)化WSN能量消耗，延長網絡整體生存周期，避免節(jié)點間干擾，解決節(jié)點密集區(qū)域數(shù)據(jù)冗余問題已成為WSN領域研究的難點和熱點［2-6］。

針對以上問題，文獻［7］提出的LEACH協(xié)議通過隨機選擇簇首節(jié)點，將簇首能量開銷分攤至每個節(jié)點，以達到延長網絡整體生存周期的目的，同時在簇內采用時分多址（TDMA）、簇間采用碼分復用（CDMA）技術避免節(jié)點間相互干擾，但是LEACH協(xié)議存在著簇首分布不均勻導致網絡能耗過高，個別節(jié)點過早死亡等問題，而且采用CDMA技術將極大提高單個節(jié)點的成本，不適用于大規(guī)模布置的WSN。文獻［8］在LEACH協(xié)議的基礎上，通過在選舉簇首時考慮節(jié)點的剩余能量，解決了個別節(jié)點過早死亡的問題，但協(xié)議仍然存在簇首分布不均勻的問題。文獻［9］提出一種簇內多跳路由協(xié)議解決網絡節(jié)點能耗不均勻的問題，但是該協(xié)議復雜度過高。文獻［10］通過將節(jié)點密集區(qū)域部分節(jié)點休眠，解決了節(jié)點密集區(qū)域能量浪費和數(shù)據(jù)冗余性的問題，但未考慮簇間干擾現(xiàn)象。文獻［11］在簇間通信引入頻分多址（FDMA）技術，并采用著色定理劃分頻點，相比LEACH協(xié)議在一定程度上降低了節(jié)點生產成本，但依然存在著節(jié)點成本較高，協(xié)議擴展性差的問題。文獻［12］提出一種基于TDMA的方案避免WSN簇間干擾，但是該協(xié)議需所有節(jié)點均獲得全局節(jié)點位置信息，在實際應用中局限性較大。文獻［13］通過引入超級幀保證相鄰簇具有不同時隙，但是該協(xié)議會造成信道的嚴重浪費。文獻［14］要求簇首節(jié)點不斷監(jiān)聽鄰居簇首的調度和功率級別以便分配簇內TDMA時隙，該協(xié)議將導致簇首節(jié)點能耗過高，同時協(xié)議不能完全避免簇間干擾。

針對WSN及目前已有協(xié)議存在的問題，本文提出了一種基于節(jié)點密度與TDMA的WSN自適應集簇分層（DT-LEACH）協(xié)議。DT-LEACH協(xié)議通過在簇首選舉階段考慮節(jié)點剩余能量，避免低能量節(jié)點因成為簇首而過早死亡，同時限制簇首節(jié)點的廣播范圍，以保證簇首的均勻分布。在簇首選舉階段后，DT-LEACH協(xié)議引入TDMA時隙分配階段，各個節(jié)點根據(jù)所處區(qū)域節(jié)點密度對TDMA時隙進行競爭，節(jié)點密集區(qū)域節(jié)點將具有相對較低的競爭力，競爭失敗的節(jié)點將進入休眠模式，在不增加節(jié)點生產成本的情況下，僅采用TDMA技術有效地避免了簇間干擾，同時，部分節(jié)點密集區(qū)域節(jié)點因競爭失敗進入休眠模式，降低了節(jié)點密集區(qū)域數(shù)據(jù)冗余性和網絡能耗。

1 WSN網絡模型

為了易于描述提出的DT-LEACH協(xié)議以及論文表述的一致性，本文對WSN網絡模型有如下假設：

①網絡中節(jié)點密度分布不均勻，將節(jié)點密度大于網絡平均節(jié)點密度的區(qū)域稱之為密集區(qū)域；將節(jié)點密度小于網絡平均節(jié)點密度的區(qū)域稱之為稀疏區(qū)域［10］；②基站位置固定并且遠離WSN網絡監(jiān)控區(qū)域，基站能量可得到持續(xù)供應；③所有傳感器節(jié)點初始能量相同，記為E，節(jié)點能量有限且無法補充；④所有傳感器節(jié)點同構且在網絡中的作用和地位相同，每個傳感器具有唯一標識，文中分別標識為1～N，N為節(jié)點總數(shù)；⑤所有傳感器節(jié)點時鐘同步；⑥傳感器節(jié)點發(fā)射功率可控，數(shù)據(jù)傳輸能量消耗符合第一順序無線電模式［7］；⑦WSN網絡中簇首節(jié)點所占最優(yōu)比例約為P；⑧WSN網絡監(jiān)控區(qū)域面積為S。

根據(jù)第一順序無線電模式，節(jié)點i向與其距離為d的節(jié)點j發(fā)送K比特數(shù)據(jù)包時的能耗為：

其中，Eelec為節(jié)點發(fā)送/接收單位比特數(shù)據(jù)消耗的能量，參數(shù)εfs和εmp取決于信號放大器的放大倍數(shù)，錯誤!未找到引用源。，當節(jié)點i與節(jié)點j的距離d大于d0時，能量消耗采用多路徑衰減模型，當d小于d0時，能量消耗采用Friss自由空間模型。如果節(jié)點i的發(fā)送能量小于ETx（k，d），節(jié)點j將不能收到任何信號。

節(jié)點j接收節(jié)點i傳送的K比特數(shù)據(jù)包的能耗為

2 DT-LEACH協(xié)議

本文提出的DT-LEACH協(xié)議以輪為單位進行工作，每輪分為三個階段：簇首選擇階段、TDMA時隙分配階段和穩(wěn)定工作階段。其中簇首選擇階段各個節(jié)點競爭成為簇首，TDMA時隙分配階段各個簇內普通節(jié)點競爭TDMA時隙，穩(wěn)定工作階段各個普通工作節(jié)點收集數(shù)據(jù)并傳送至對應簇首，簇首匯總聚合數(shù)據(jù)并傳送至基站，穩(wěn)定工作階段持續(xù)時間遠大于前兩階段。本節(jié)將對DT-LEACH協(xié)議的簇首分配階段和TDMA時隙競爭階段進行詳細描述。

2.1 簇首選舉階段

由于簇首節(jié)點能耗遠高于普通節(jié)點，為了避免剩余能量較低的節(jié)點因當選簇首節(jié)點而過早死亡，均衡WSN網絡能耗負載，DT-LEACH協(xié)議通過考慮節(jié)點剩余能量因素，提出一種新的簇首選擇方案。

在簇首選擇階段，每個節(jié)點設定一個定時器，計時結束后成為簇首節(jié)點，并向范圍內節(jié)點廣播。

在設定定時器時，需要保證當選簇首的節(jié)點剩余能量較多，因此，在文獻［7］提出的LEACH協(xié)議基礎上，綜合考慮節(jié)點剩余能量的影響，提出式（3）設定定時器。

其中，W1和W2分別為隨機數(shù)和節(jié)點百分比剩余能量的加權系數(shù)，RData為0～1的隨機數(shù)，CE為節(jié)點每輪平均百分比能量消耗，r為當前輪數(shù)，Ei為節(jié)點i的剩余能量，E為節(jié)點的初始能量。式（3）中第一項能保證各個節(jié)點定時器倒計時不盡相同，第二項能保證剩余能量較大的節(jié)點倒計時時長較短，優(yōu)先結束倒計時并廣播成為簇首節(jié)點，而剩余能量較小的節(jié)點倒計時長則較長，能在倒計時結束前收到鄰居節(jié)點成為簇首的廣播消息而成為普通節(jié)點。

每個簇首的監(jiān)控面積Sc是以該簇首為圓心，簇首的偵聽半徑R為半徑的圓形區(qū)域，即Sc=π*R2。根據(jù)假設7和假設8，每個簇首的平均監(jiān)控面積Sc約為P*S，因此，簇首的偵聽半徑R估值為：

其中εr為修正系數(shù)，經驗值為1，可根據(jù)具體應用場景網絡節(jié)點分布特點對偵聽半徑R進行修正，確保簇首比例約為P。

根據(jù)假設［6］，各個節(jié)點根據(jù)偵聽半徑R的估值和式（1）確定發(fā)射功率ER，并根據(jù)式（3）設定定時器，統(tǒng)一開始倒計時，當節(jié)點倒計時順利結束時，則以發(fā)射功率ER廣播自己成為簇首節(jié)點的消息，根據(jù)式（1），廣播的有效覆蓋范圍為以節(jié)點為圓心，R為半徑的圓形區(qū)域。該范圍內其余節(jié)點接收到廣播信息后停止倒計時，成為普通節(jié)點。由于采用式（3）設定定時器，可避免能量較低的節(jié)點當選簇首節(jié)點。根據(jù)第1節(jié)中假設5和式（1），簇首節(jié)點的廣播消息能耗為：

其中KCH為廣播消息的比特長度。

若節(jié)點在定時器倒計時結束前收到了鄰居節(jié)點成為簇首的廣播消息，則該節(jié)點停止倒計時，成為普通節(jié)點，但節(jié)點繼續(xù)保持監(jiān)聽狀態(tài)，并記錄所有鄰居簇首，供TDMA時序分配階段使用。

下面將對DT-LEACH協(xié)議保證簇首均勻分布的原理進行分析：由于普通節(jié)點成為簇首的廣播消息將被以該節(jié)點為圓心，R為半徑的圓形區(qū)域內所有節(jié)點接收，所以該區(qū)域內將不會出現(xiàn)其它簇首，相鄰簇首間距離將大于R。下面，將采用反證法證明相鄰兩簇首間距離將小于2R。假定簇首i與簇首j為相鄰簇首，且簇首i與簇首j之間距離大于2R，那么在兩個簇首之間存在一片區(qū)域，該區(qū)域將無法接收到簇首i和簇首j成為簇首的廣播消息，假定根據(jù)式（3）節(jié)點k具有該區(qū)域最小倒計時時長，那么節(jié)點k倒計時結束后將廣播成為簇首k，且簇首k位于簇首i和簇首j之間，簇首i和簇首j為相鄰簇首假設不成立，相鄰簇首間距離小于2R。因此，采用DTLEACH協(xié)議相鄰簇首間距離將大于R小于2R，能有效避免簇首扎堆現(xiàn)象，保證簇首均勻分布。

因此，根據(jù)式（3），DT-LEACH協(xié)議能夠避免低能量節(jié)點因當選簇首而過早死亡，根據(jù)式（5）以及上述分析，DT-LEACH協(xié)議能夠保證簇首的均勻分布。DT-LEACH協(xié)議簇首選擇階段流程圖如圖1所示。

圖1 簇首選擇階段流程圖

2.2 TDMA時隙分配階段

在TDMA時隙分配階段，所有存活普通節(jié)點將根據(jù)所處區(qū)域節(jié)點密度同時對TDMA時隙進行競爭，競爭失敗的節(jié)點將進入休眠模式以避免因時隙不足發(fā)生簇間干擾。DT-LEACH協(xié)議通過讓密集區(qū)域節(jié)點具有較低的競爭力，部分密集區(qū)域節(jié)點進入休眠模式，降低了密集區(qū)域正常工作節(jié)點的密度，減少了監(jiān)控數(shù)據(jù)的冗余性。

TDMA時序分配初始階段，各個存活的普通節(jié)點以半徑RD向鄰居節(jié)點廣播，同時偵聽并統(tǒng)計鄰居節(jié)點的廣播消息，計算節(jié)點所處區(qū)域節(jié)點分布密度D（i），如式（6）所示［10］。

其中Nbroadcast為節(jié)點i接收到的不同鄰居節(jié)點的廣播數(shù)目。

普通節(jié)點在計算所處區(qū)域節(jié)點分布密度后，根據(jù)式（7）設置定時器，統(tǒng)一進入倒計時，并維護一張TDMA時隙占用表，初始時，所有時隙均標記為“空閑”。

其中，W3和W4分別為隨機數(shù)和節(jié)點i所處區(qū)域相對節(jié)點密度的加權系數(shù)，RData為0～1的隨機數(shù)，Daverage為WSN網絡節(jié)點平均分布密度，由式（8）計算。式（7）中第一項能保證各個節(jié)點定時器倒計時不盡相同，第二項能保證稀疏區(qū)域的節(jié)點倒計時時長較短，具有較強的TDMA時隙競爭力，優(yōu)先結束倒計時選取TDMA時隙并向鄰居節(jié)點廣播，而密集區(qū)域的節(jié)點倒計時長則較長，TDMA時隙競爭力較差，部分節(jié)點因TDMA時隙用盡進入休眠模式。

其中Nalive為普通節(jié)點存活數(shù)目。

對簇間干擾現(xiàn)象進行分析可知，發(fā)生簇間干擾需有以下兩個前提：①兩個普通節(jié)點處于同一個簇的偵聽范圍內；②兩個普通節(jié)點占用同一TDMA時隙傳送數(shù)據(jù)。

根據(jù)前提條件1可知，發(fā)生簇間干擾的兩個普通節(jié)點間的距離必然小于簇首偵聽半徑R的兩倍，即2R。由于WSN網絡節(jié)點在部署后位置固定，前提條件1無法改變，因此DT-LEACH協(xié)議通過給兩個普通節(jié)點分配不同TDMA時隙或者令其中一個節(jié)點休眠以避免簇間干擾。

當節(jié)點定時器倒計時順利結束時，該節(jié)點隨機選擇一個空閑TDMA時隙Ti，并以2R為半徑廣播宣布占用該TDMA時隙（所有可能與該節(jié)點發(fā)生簇間干擾的節(jié)點均在此范圍內），廣播消息同時包含該節(jié)點的分簇信息，即該節(jié)點處于哪些簇首偵聽范圍內。

若節(jié)點在定時器倒計時結束前收到鄰居節(jié)點的TDMA時隙占用廣播消息，則首先檢查是否與該鄰居節(jié)點處于同一簇首偵聽范圍內，若否，則丟棄該消息繼續(xù)倒計時，若是，則將維護的TDMA時隙占用表中該時隙標記為“已占用”，如果所有時隙均被標記為“已占用”，則該節(jié)點進入休眠模式，反之則繼續(xù)倒計時，并保持偵聽鄰居節(jié)點廣播信息。

圖2為DT-LEACH協(xié)議TDMA時隙分配階段流程圖。根據(jù)式（7），密集區(qū)域節(jié)點的倒計時較長，TDMA時隙競爭力較弱，稀疏區(qū)域節(jié)點的倒計時較短，TDMA時隙競爭力較強，因此DT-LEACH協(xié)議能保證稀疏區(qū)域節(jié)點優(yōu)先獲得TDMA時隙，部分密集區(qū)域節(jié)點因TDMA時隙用盡進入休眠狀態(tài)，在有效避免簇間干擾的情況下降低了密集區(qū)域正常工作節(jié)點的密度，進而降低了數(shù)據(jù)的冗余性和WSN網絡能耗。

圖2 TDMA時隙分配階段流程圖

3 仿真實驗與性能分析

為了對DT-LEACH協(xié)議性能進行測試與分析，本節(jié)將開展基于Matlab軟件的仿真實驗，如實驗中無特殊說明，實驗參數(shù)均根據(jù)第一順序無線電模式設置，如表1所示。

為了仿真節(jié)點分布密度不均勻情況，實驗設定WSN網絡監(jiān)控區(qū)域左下角為密集區(qū)域，例如40%密集度表示40%的節(jié)點位于左下角1/4區(qū)域，其余節(jié)點在剩余區(qū)域均勻分布［10］，公式（4）修正系數(shù)εr設為1。

仿真實驗將分別從簇首扎堆問題、網絡能耗優(yōu)化效果和簇間抗干擾能力三個方面對提出的DT-LEACH協(xié)議和對比組協(xié)議進行比較，其中簇首扎堆問題和網絡能耗優(yōu)化效果的對比組協(xié)議為LEACH協(xié)議［7］，簇間抗干擾能力的對比組協(xié)議選定為D-LEACH 協(xié)議［10］。

實驗1：本實驗旨在測試DT-LEACH協(xié)議確保簇首均勻分布，避免簇首扎堆的性能，圖3（a）與圖3（b）分別為采用LEACH協(xié)議［7］和DT-LEACH協(xié)議時WSN網絡穩(wěn)定工作階段的狀態(tài)圖，密集度為40%，網絡參數(shù)設定如表1所示。圖3中方塊表示簇首節(jié)點，圓圈表示普通節(jié)點，三角表示休眠節(jié)點。為了對實驗結果進行定量分析，采用文獻［15］中提出的均勻度來衡量簇首節(jié)點分布的均勻程度，圖 3（a）中LEACH協(xié)議簇首均勻度為 0.5091，圖3（b）中DT-LEACH協(xié)議簇首均勻度為0.816 9，可以看到，采用LEACH協(xié)議時簇首分布不均勻，出現(xiàn)扎堆現(xiàn)象，而采用DT-LEACH協(xié)議時簇首節(jié)點分布均勻，未出現(xiàn)扎堆現(xiàn)象，同時休眠節(jié)點集中在密集區(qū)域，有效地解決了密集區(qū)域數(shù)據(jù)冗余性問題。

圖3 40%密集度WSN節(jié)點功能劃分示意圖

表1 WSN網絡參數(shù)設置

實驗2：本實驗旨在測試DT-LEACH協(xié)議對WSN網絡能耗優(yōu)化的性能，實驗采用LEACH協(xié)議與DT-LEACH協(xié)議進行對比，其中LEACH協(xié)議簇內采用TDMA協(xié)議，簇間采用CDMA協(xié)議，實驗參數(shù)設定如表1所示，實驗結果如表2所示，可以看到，相比于LEACH協(xié)議，DT-LEACH協(xié)議能夠對網絡能耗進一步優(yōu)化，大幅提高WSN網絡的生存周期，同時，隨著網絡密集度的提升，DT-LEACH協(xié)議的優(yōu)勢愈加顯著。

實驗3：本實驗旨在測試DT-LEACH協(xié)議避免簇間干擾的性能，實驗以WSN網絡中除休眠節(jié)點和簇首節(jié)點外，能夠無干擾傳送數(shù)據(jù)的普通節(jié)點的平均數(shù)為評價指標。在不同節(jié)點分布密度下，采用文獻［10］中提出的D-LEACH協(xié)議作為對比組協(xié)議與本文提出的DT-LEACH協(xié)議進行比對。為了測試結果表述的清晰，將WSN網絡生存周期分為3個時間段，分別是：時間段1為網絡起始工作至第一個節(jié)點死亡，時間段2為網絡第一個節(jié)點死亡至半數(shù)節(jié)點死亡，時間段3為網絡半數(shù)節(jié)點死亡至全數(shù)節(jié)點死亡。測試結果如表3所示?？梢钥吹?，在任一時間段，采用D-LEACH協(xié)議時大部分普通節(jié)點均因為簇間干擾無法與簇首正常通信，而采用DT-LEACH協(xié)議時則極大提高了抗簇間干擾性能，大部分普通節(jié)點均能與簇首節(jié)點正常通信，很好地避免了簇間干擾。

表2 LEACH協(xié)議與DT-LEACH協(xié)議性能比較 單位：輪

表3 D-LEACH協(xié)議與DT-LEACH協(xié)議避免簇間干擾性能比較

4 結語

本文提出一種基于節(jié)點密度的WSN低功耗自適應集簇分層協(xié)議，通過對LEACH協(xié)議簇首選舉方案進行改進，克服了LEACH協(xié)議簇首分布不均勻和低能量節(jié)點過早死亡的缺點，同時引入TDMA時隙分配階段，節(jié)點根據(jù)所處區(qū)域節(jié)點分布密度自主競爭TDMA時隙，競爭失敗節(jié)點進入休眠模式，能夠在消除簇間干擾的情況下有效地降低WSN網絡能耗和節(jié)點密集區(qū)域的數(shù)據(jù)冗余性。由于DT-LEACH協(xié)議僅使用TDMA技術，對硬件要求低，有利于單個傳感器節(jié)點生產成本的降低。仿真實驗進一步驗證了DT-LEACH協(xié)議的優(yōu)越性。

［1］Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey［J］.Computer networks，2008，52（12）：2292-2330.

［2］Sumithra S，Victoire T A A.An Efficient Energy Clustering by Dy?namic Multi-Chain Model in WSN［J］.International Review on Computers and Software（IRECOS），2014，9（8）：1392-1398.

［3］Briff P，Lutenberg A，Vega L R，et al.A primer on energy-efficient synchronization of WSN nodes over correlated Rayleigh fading channels［J］.Wireless Communications Letters，IEEE，2014，3（1）：38-41.

［4］Rodrigues F，Brayner A，Maia J E B.Using fractal clustering to ex?plore behavioral correlation：a new approach to reduce energy con?sumption in WSN［C］//Proceedings of the 30th Annual ACM Sym?posium on Applied Computing.ACM，2015：589-591.

［5］劉端陽，暴占兵，程珍.一種可分負載WSN的能耗均衡負載調度算法［J］.傳感技術學報，2014，27（2）：225-232.

［6］歐縣華，武憲青，何熊熊.基于AIUKF的WSN節(jié)點定位算法［J］.傳感技術學報，2015，28（2）：234-238.

［7］Heinzelman W B，Chandrakasan A P，and Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsen?sor Networks［J］.IEEE Trans on Wireless Comm，2002，1（4）：660-670.

［8］Zhang W，Liang Z，Hou Z，et al.A power efficient routing protocol for wireless sensor network［C］.Networking，Sensing and Control，2007 IEEE International Conference on.IEEE，2007：20-25.

［9］Zhang Zhenghao，Ma Ming，Yang Yuanyuan.Energy-efficient mul?tihop polling in clusters of two layered heterogeneous sensor net?works［J］.Computers，IEEE Transactions，2008，57（2）：231-245.

［10］Kim J S，Byun T Y.A Density-Based Clustering Scheme for Wire?less Sensor Networks［M］.Advanced Computer Science and Infor?mation Technology.Springer Berlin Heidelberg，2011：267-276.

［11］石為人，易軍，許磊，等.基于點著色的無線傳感器網絡頻點分配算法［J］.傳感技術學報，2009，22（1）：111-115.

［12］Kulkarni S S.TDMA service for sensor networks［C］.Distributed Computing Systems Workshops 2004 Proceedings 24th Interna?tional Conference on Digital Object Identifier：10.1109/ICDCSW.2004.1284094，2004：604-609.

［13］SHU Tao，KRUNZ M.Energy-efficient power/rate control and scheduling in hybrid TDMA/CDMA wireless sensor networks［J］.Computer Networks，2009，53（9）：1395-1408.

［14］張震，石志東，單聯(lián)海，等.WSN中一種自適應功率控制及調度算法［J］.計算機工程，2013，39（4）：18-21.

［15］羅傳文，劉丹丹，王剛.均勻度理論［J］.生物數(shù)學學報2006，21（1）：105-112.