一种新的无线传感网局域按需簇维护算法

胡向东，张 力

(重庆邮电大学 自动化学院，重庆，400065)

0 引言

随着物联网等国家战略性新兴产业的兴起与推动，无线传感网(wireless sensor networks，WSN)将在军事国防、工农业生产、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域远程监控等诸多领域得到大规模应用［1］。但无线传感网中的众多传感器节点面临着严格的能量约束问题，如何降低传感器节点的能量消耗、延长网络生命周期一直是无线传感网的研究重点。

对于大规模的无线传感网而言，基于分簇的网络拓扑结构在拓扑管理、能量效率、数据融合与节点协同处理方面都具有明显优势。分簇的结构将大规模的网络划分为多个小规模的网络，从而降低了拓扑管理的难度，同时可以引入节点睡眠机制而不影响网络连通性，便于数据融合，减少了信道接入的竞争，从而提高网络吞吐量，为节点的协同处理提供了良好的物理支持，可有效地降低网络开销，延长网络寿命［2］。

在这种分簇网络结构中，节点分布式地组织成以簇为单位的结构，每个簇包含一个簇头节点(cluster head，CH)与多个簇成员节点(cluster member，CM)。簇头节点承担簇内数据收集、处理与簇间路由与数据转发等功能;簇成员节点负责将收集的数据上传至其簇头节点。由于簇头节点负担的任务量大大超过簇成员节点，将比簇成员节点更快速地消耗完自身能量，因此，需要采取措施平衡簇内节点的能量消耗以延长整个网络的生命周期。簇头轮换是目前普遍采用的策略，通过簇头轮换，使得网络中的每个节点都有机会担当簇头，从而平衡各节点的能量消耗。现有分簇算法的簇头轮换策略大多采用周期性轮换，如低功耗自适应集簇分层型协议(low energy adaptive clustering hierarchy，LEACH)［3］，HEED［4］(a hybrid，energy-efficient distributed clustering approach)，ACE［5］(algorithm for cluster establishment)等以预设的时间周期为单位进行全网簇头轮换与拓扑重建。虽然基于时间周期的轮换策略可以较好地均衡网络能耗，但是其每次轮换都在全网内进行，不仅导致网络功能的周期性中断，同时会造成本身数据处理量不大或监控任务不重的区域产生大量不必要的能量浪费，而且全网内不同区域的能量消耗不均匀、轮换周期难以优化确定。为了应对上述问题，达到减少能量浪费和延长网络存活时间的目的，本文对无线传感器网络的分簇路由协议进行了分析与研究，并提出了一种新的算法。

新算法建立了局域按需簇维护机制，应用网络成簇之后基于动态能量阈值的轮换策略，把轮换的影响限制在一个较小的范围内(本簇内或扩展到邻簇)。同时，本文结合MAC层的动态TDMA调度机制，给出了实现分簇拓扑的快速建立与故障恢复的方法。

1 周期性轮换算法分析

典型的周期性轮换算法主要有LEACH，HEED，ACE等，这类算法都包括了簇头选举和数据传输2个阶段，其主要的区别在于簇头选举的算法，而在数据传输阶段，都采用了固定的TDMA调度机制，并基于预设的时间结束传输和重选簇头。

在簇头选举阶段，周期性轮换算法按照其簇头选举算法选出簇头节点后，就向外发送簇头广播信息。而其他节点根据收到的簇头广播信息的信号大小决定要加入哪个簇，并向决定加入簇的簇头发送加入请求。簇头在收到请求后将该节点加入自己的路由表，并为每个节点设定一个TDMA时间表，再将该表发送给所有簇内节点。

在数据传输阶段，各簇内成员节点按照自身的TDMA时隙将收集到的数据传送给簇头，若数据在一个时隙内未发送完，则在下一时隙到来时继续发送;簇头节点则需在本轮数据发送的全部时间里进行监听并接收簇内普通节点的监测数据，待本簇内所有普通节点传完数据后，簇头节点将接收到的全部数据与其自身监测到的数据进行融合处理，随后进入簇间通信阶段。此外，簇内成员节点只需在分配给自己的TDMA时隙内将数据发送至簇头节点，其他时间可处于休眠状态，起到节能的作用。

周期性轮换类的分簇算法与平面路由算法相比，网络整体生存时间得到了延长。但这类算法也存在不少的缺点，如簇头数目不确定，簇头分布不合理，能量损耗不平衡，簇更新周期很难优化确定等。这些问题制约了它们在大规模网络中的应用。

2 局域按需簇维护算法的提出

2.1 算法描述

局域按需簇维护算法的主要思路是用基于能量阈值的方式驱动簇头轮换，同时只在受影响的局域范围内用局域簇头轮换，以此解决簇更新周期难确定的问题，减少不必要的能量的消耗，延长网络的存活时间。

局域按需簇维护算法从网络首次成簇之后开始，直到网络死亡为止，由簇头维护算法、成员节点维护算法和待命节点维护算法3部分组成。它将网络中由于某些原因导致的无法正常工作的节点(如剩余能量低于阈值的簇头节点、簇头不再继续正常工作的簇内成员节点、新入网节点等)全当作待命节点，再按照网络当前的具体情况，对它们统一进行维护，使它们重新开始工作。图1描述了局域按需簇维护涉及的对象和节点状态转移。

图1 节点状态转移图Fig.1 Diagram of state shift of node

1)簇头节点维护算法。簇头节点维护的主要任务是判断簇头是否继续担任，当簇头满足自身当前剩余能量值高于能量阈值Eth，并且簇内成员节点数大于设定的最小成员个数member_min_时，则继续担任簇头，否则，广播辞职消息ADV_RESIGN，并转为待命节点。具体流程如图2a所示。

图2 维护流程Fig.2 Flow chart of maintenance

［7-8］中能量阈值的设定方法，本文设置能量阈值Eth的计算方法为

(1)式中:μ，ε∈R，μ，ε分别为预设值，并满足(μ+εpnow)∈［0，1］;Erec为担任簇头时的初始剩余能量;pnow为当前能耗速率，pnow每隔5个TDMA帧长更新一次，pnow越大，Eth越大，簇头工作时长越短。最小成员个数member_min_的计算方法为

(2)式中:p∈［0，1］，p为预设值，alive_node为存活节点个数。周期性轮换算法通过预设簇头个数来平衡网络负载，但由于簇头个数的随机性，网络的负载平衡因子(load balance factor，LBF)波动大、均值小。通过设置member_min_来控制簇头个数，可更有效地平衡负载，并提高负载平衡效果的稳定性。

2)成员节点维护算法。成员节点维护主要起侦听簇头异常、保护网络的作用。成员节点转为待命节点的条件有2种:1)成员节点在发现簇头被捕获或簇头死亡;2)成员节点接收到簇头的辞职消息ADV_RESIGN。具体流程如图2b所示。

3)待命节点维护算法。待命节点都是暂时无法工作的节点，因此对待命节点维护的目的就是要使节点重新工作，即重新成簇或者加入其他簇。本文采用在一个区域范围内，当待命节点个数大于λ倍member_min_时，选择重新成簇;否则，节点选择最邻近的簇头，请求加入该簇头所在的簇。具体算法将在2.2节详细叙述。

2.2 区域簇头轮换

区域簇头轮换是通过对待命节点的维护实现的。由于待命节点的产生方式有2种，区域簇头轮换的实现方式分为有簇头轮换(针对簇头辞职的方式)和无簇头轮换(针对簇头被捕获或死亡)。

有簇头轮换步骤如下。

步骤1 当簇头剩余能量低于设定的能量阈值时，簇头广播辞职消息ADV_RESIGN。

步骤2 收到ADV_RESIGN消息的簇内成员节点向簇头发送包含自身剩余能量信息的消息NODE_INFO，并转为待命节点。

步骤3 簇头根据收到的NODE_INFO消息统计出簇内成员节点的个数Num_CM，再根据簇内成员节点的个数Num_CM计算出将要生成簇的个数Num_CH。当Num_CM小于λ倍的member_min_时，Num_CH为1，在其他条件下，Num_CH的值由(3)式计算所得。

(3)式中，符号⎿a」为小于a的最大整数。

步骤4 簇头根据收到的NODE_INFO消息选出剩余能量最大节点的Num_CH个节点作为新簇头，广播新簇头ID列表消息NEW_CH，并转为待命节点。

步骤5 收到NEW_CH消息的待命节点检查NEW_CH消息中是否有自身ID。如果有自身ID，则转为簇头节点，并发布簇头广播ADV_CH;如果没有自身ID，则继续维持待命节点状态。

步骤6 收到ADV_CH广播的待命节点向新簇头发送加入请求JOIN_REQ;邻簇中收到广播的成员节点比较新簇头与现有簇头的通信距离，当与新簇头的通信距离更小时，向新簇头发送加入请求JOIN_REQ。

步骤7 簇头根据收到的JOIN_REQ消息，按通信距离进行排序，广播时隙消息ADV_SCH，完成成簇。

无簇头轮换步骤如下。

步骤1 发现簇头异常的成员节点，关闭睡眠状态，转为待命节点。

步骤2 发现簇头异常的成员节点在各自的下一时隙开始时，检查是否已收到信息收集广播ADV_COLLECT，如未收到ADV_COLLECT消息，则发送ADV_COLLECT消息。

步骤3 收到ADV_COLLECT消息的节点，向广播ADV_COLLECT消息的节点发送节点信息NODE_INFO消息。

步骤4 广播ADV_COLLECT消息的节点根据收集到的NODE_INFO消息判断剩余成员节点个数是否大于member_min_。当剩余成员节点个数大于member_min_时，依据有簇头轮换的方法，选出新簇头，广播NEW_CH消息，重新成簇;当剩余成员节点个数小于member_min_时，广播ADV_DISBAND消息，并向最近的簇头发送JOIN_REQ消息。

步骤5 收到ADV_DISBAND消息的待命节点向各自最近的簇头发送JOIN_REQ消息，在收到簇头节点的时隙广播ADV_SCH消息后，计算得到自身的发送时隙，转为成员节点，加入到该簇。

2.3 动态TDMA调度

周期性轮换算法在进行下一轮簇头选举之前，网络的拓扑结构是固定的，因此可以使用一个静态的TDMA调度方式，而局域按需簇维护的拓扑变化是非周期的，随时都有可能发生变化，若采用静态TDMA调度方式会产生大量的数据传输冲突，对网络造成巨大的危害。因此使用动态TDMA调度十分必要。

局域按需簇维护的拓扑变化主要有2种:1)成员节点的退出和加入;2)多跳网络中簇间路由的变化。簇头间的数据传输固定在data transmission时隙进行，如图3所示，在簇间路由恢复之后，就能将数据传到基站，因此不需要调度。成员节点向簇头传输数据在schedule时隙进行，schedule时隙被分为多个slot时隙，slot时隙与成员节点一一对应，1个slot时隙只允许1个成员节点使用。新成员节点加入时，要使其能发送数据，就必须分配一个slot时隙供其使用;原有成员节点退出时，簇头回收空出的时隙，有助于延长剩余的成员节点的slot时隙，从而提高网络的传输效率。

图3 TDMA结构Fig.3 Framework of TDMA

动态TDMA调度具有以下2个特点。

1)时隙的分配是根据成员节点与簇头间的通信距离决定的，通信距离越小，时隙越靠前。成员节点在请求加入消息JOIN_REQ中加入收到簇头广播消息ADV_CH的信号强度，簇头再根据信号强度从大到小排序，然后广播时隙消息ADV_SCH。

2)schedule时隙的时长是固定的，slot时隙时长可以改变。为保证在一个slot时隙内至少能完成一个数据包的传输，slot时隙有一个最小时长，最小时长由单个包的大小和带宽等因素决定。将schedule时隙按成员节点个数均分，均分后时长大于slot时隙的最小时长时，slot时隙的时长就等于均分的时长;均分后时长小于slot时隙的最小时长时，slot时隙的时长就等于slot时隙的最小时长，并从后向前复用时隙。

3 仿真与结果分析

3.1 仿真场景设置

本文采用网络仿真软件NS-2.34，仿真区域为100 m×100 m，在其中随机布设100个传感器节点，基站位于场景的上方。节点初始能量设为2 J;节点每进入一次自己的时隙，则发送一次数据。节点的参数具体设置如表1所示。

表1 节点参数设置Tab.1 Setting of node parameters

3.2 仿真结果分析

局域按需簇维护算法涉及4个重要的参数:μ，ε，p和λ。μ和ε为计算能量阈值的相关系数，能量阈值决定了簇头轮换的快慢，直接影响到网络存活时间，因此在不同μ和ε值的情况下，网络存活时间有着较大的差异，如图4所示。

图4是在仿真条件下网络存活时间随不同的μ和ε值的变化情况。在μ=0.4，ε=11时，网络存活时间达到最大值665 s，此时(μ+εpnow)的值在0.58～0.66 波动，接近于文献［9］中提出的最优能量阈值参数 popt=0.644，(Eth=p·Erec)。

图4 μ和ε对存活时间的影响Fig.4 Change of alive time with μ and ε

除μ和ε之外，网络中还有2个参数p和λ。p是计算最小成员节点个数的系数，λ是控制重新成簇个数的系数，这2个参数控制着网络拓扑，不同的p值和λ值会使网络的簇头个数和负载平衡发生变化。仿真结果如表2所示。

表2 不同p和λ下的簇个数情况Tab.2 Number of cluster under p and λ

表2的中间内容是簇个数信息，其数值是按照簇个数均值［最小簇个数，最大簇个数］的形式排列的。

由于LEACH，HEED，ACE等周期性轮换算法在网络运行和维护过程中的差异性不大，因此本文仿真中采用最典型的LEACH算法与新算法做对比验证。

图5为新算法与LEACH算法的LBF的变化对比，图5中LEACH算法设置的簇头个数为5，对应新算法中的p和λ分别为0.15和1.5，平均簇头个数维持在5个左右(如表2所示)。从图5中可以看出，在预设相同簇个数的条件下，新算法的负载平衡因子波动范围更小，均值更大，说明网络的负载更平衡。

图5 负载平衡因子随时间的变化Fig.5 Change of LBF with time

图6 网络存活时间对比Fig.6 Contrast of the number of alive nodes

图7 数据传输量对比Fig.7 Contrast of the amount of data received

图8 能量消耗对比Fig.8 Contrast of energy consumption

图6-8分别从网络存活时间、基站收到的数据总量和能量消耗情况3个方面将新算法与LEACH算法进行了比较。由图5可见，局域按需簇维护算法的网络存活时间为665 s，超过LEACH算法的存活时间525 s，增加了约26.7%;由图6可知，局域按需簇维护算法中基站收到的数据包有65 928个，超过LEACH算法的数据包总数52 374个，增加了25.9%;由图7可见，在能量消耗方面，随着时间的增加，局域按需簇维护算法比LEACH算法能量消耗更小，在给定能量耗尽时，局域按需簇维护算法所支持的网络存活时间持续更长。

4 结束语

无线传感网的生命周期一直是技术开发人员关注的焦点，本文基于目前得到普遍接受的分簇结构的无线传感网，提出并建立了局域按需簇维护算法，实现了基于能量阈值的非周期性、局域范围内的簇头轮换，能解决传统方法存在的能量浪费问题。与典型的LEACH算法的周期性时间驱动和整网簇头轮换方法相对比，仿真结果表明，本文提出的局域按需簇维护算法可有效提高负载平衡性、降低能量消耗，在网络存活时间和数据采集量上都优于LEACH算法。本文提出的动态TDMA时隙调度方法，还能对节点的退出或死亡做出快速响应，可确保网络链路得到快速修复。

参考文献:

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］，北京:清华大学出版社，2005:94-102.SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless Sensor Networks［M］.Beijing:Tshinghua University Press，2005:94-102.

［2］AHMED A，MOHAMED Y.A survey on clustering algorithms for wireless sensor networks［J］.Computer Communications，2007，30(14-15):2826-2841.

［3］HEINZELMAN WR， CHANDRAKASANA， BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks［C］//IEEE.Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.Hawaii:IEEE Computer Society，2000:10-15.

［4］YOUNIS O，FAHMY S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad hoc sensor networks［J］.IEEE Transaction on Mobile Computing，2004，3(4):366-379.

［5］CHAN H，PERRIG A.ACE:An Emergent Algorithm for Highly Uniform Cluster Formation［C］//HOLGER K，ANDREAS W.Wireless Sensor Networks:First European Workshop，EWSN 2004.Berlin:Springer，2004:154-171.

［6］游晓黔，李明隆，杨佳.无线传感器网络LEACH协议的研究与改进［J］.重庆邮电大学学报:自然科学版，2011，23(6):746-751.YOU Xiaoqian，LI Minglong，YANG Jia.Research and improvement of LEACH protocol for wireless sensor networks［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2011，23(6):746-751.

［7］WANG Y，ZHAO Q，ZHENG D.Energy-driven adaptive clustering data collection protocol in wireless sensor networks［C］//IEEE.Proceedings of International Conference on Intelligent Mechatronics and Automation.Chengdu:IEEE Press，2004:599-604.

［8］GAMWARIGE S，KULASEKERE E.An algorithm for energy driven cluster head rotation in a distributed wireless sensor network［C］//IEEE.Proceedings of the International Conference on Information and Automation(ICIA2005).Hong Kong:IEEE Press，2005:354-359.

［9］GAMWARIGE S，KULASEKERE C. Optimization of cluster head rotation in energy constrained wireless sensor networks［C］//IEEE.Proceedings of International Conference on Wireless and Optical Communications Networks.Singapore:IEEE Press，2007:1-5.