基于节点密度与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.