基于節點密度與TDMA的無線傳感器網絡集簇協議*

徐祥振，汪成亮

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

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

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

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

1 WSN網絡模型

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

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

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

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

節點j接收節點i傳送的K比特數據包的能耗為

2 DT-LEACH協議

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

2.1 簇首選舉階段

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

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

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

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

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

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

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

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

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

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

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

圖1 簇首選擇階段流程圖

2.2 TDMA時隙分配階段

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

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

其中Nbroadcast為節點i接收到的不同鄰居節點的廣播數目。

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

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

其中Nalive為普通節點存活數目。

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

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

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

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

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

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

3 仿真實驗與性能分析

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

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

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

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

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

表1 WSN網絡參數設置

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

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

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

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

4 結語

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

［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節點定位算法［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］張震，石志東，單聯海，等.WSN中一種自適應功率控制及調度算法［J］.計算機工程，2013，39（4）：18-21.

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