基于簇头优化的自供能无线传感网络路由算法

王 冠，王瑞尧

(平顶山学院信息工程学院，河南平顶山467000)(*通信作者电子邮箱wangguan0123@163.com)

0 引言

无线传感器网络由许多个传感器节点组成，它可以感知、监测与采集传感器的环境信息(如温度、热度以及环境中各种气体的浓度等)，并通过无线通信的方式将采集到的数据发送给对此数据感兴趣的观察者，无线传感器网络不需要固定的网络设备，它具有展开快速、抗毁性强等优点，在当前的应用研究中，网络的存活期是衡量一个无线传感器网络性能的重要指标［1－2］。

传统无线传感器节点采用的是不可充电电池，一旦电池的能量使用完毕，节点就会死亡，因此低能耗的无线传感器网络节点的设计成为热点［3］。近年来，随着环境能量采集技术的不断发展，研究人员已经能够采集环境中存在的能源，如太阳光照、机械振动、热力等，并将此技术用于无线传感器网络［4］，设计出了能够自动采集环境能量的传感器。传感器节点能够将环境中的太阳能、振动能、热能等转换为可用电能［5］，自动为自己补充能量，形成了具有自供能特点的无线传感器网络。结合这一特性，本文旨在设计出高效的具有自供能感知的路由，解决传统网络中由于电池能量受限而制约其生命周期的问题，进而改善网络性能。

1 相关工作

由于分簇路由算法具有易管理、易实现、资源利用高效等特点，因此在针对自供能无线传感器网络路由算法的研究中，目前国内外大部分的研究学者选择分簇路由算法为主要的研究对象。

最早自供能分簇路由算法是文献［6］提出的太阳能分簇路由 算 法——SLEACH(Solar-aware Low Energy Adaptive Clustering Hierarchy)，该算法网络中部分传感器节点可以采集太阳能，因此在进行簇头竞选时，通过在算法中考虑了太阳能量这一因素，增加了太阳能传感器节点当选簇头的概率;但是选举机制太简单，容易造成网络能耗的不均衡。

文献［7］提出了能量补给分簇(Power-Harvesting Clustering，PHC)路由算法，根据文献［8］经典的低功耗自适应集簇分层型(Low Energy Adaptive Clustering Hierarchy，LEACH)算法，同时考虑了节点的剩余能量和补给能量，完善了簇头选举机制以及簇成员节点的归属簇群机制;但是没有对补给能量特点进行分析，同时簇头节点无法连任，簇间通信为单跳的形式使簇头的能量消耗加剧，促使簇头加速死亡。

文献［9］提出了自适应分簇路由算法——ACSP(Adaptive Clustering routing based on Solar Power supplying)，它在PHC 算法的基础上根据补给能量水平起伏的特点，将网络的能量水平划分为能耗期、储能期和稳定期，通过分析不同时期的能量特点来设定不同的簇头选举阈值，并且该算法提出了簇间出最佳通信距离;但是节点在一个轮次内只能依次当选簇头节点，无法连任。

文献［10］提出了自适应能量感知路由协议(Adaptive Energy Harvesting Aware Clustering routing protocol，AEHAC)，该算法中节点不需要在一个周期内依次担任簇头，而是允许节点每轮均可参加竞选，从而使当前剩余能量较高的节点能够多次竞选和担任簇头;但是在竞选簇头时，并没有考虑之前节点所获得的补给能量，使得最终网络能耗的不均衡。

文献［11］提出了能耗均衡的自供能无线传感器网络分簇算法(Energy Balanced Clustering algorithm for Self-energized wireless sensor network，EBCS)，该算法在上述 ACSP和AEHAC的基础上进行完善，在选举簇头时考虑了节点在没有担任簇头期间总共获得到的补给能量值;同时在簇间路由方面，EBCS不是把数据直接发送给剩余能量最大的下一跳，而是结合簇头当前的能量补给水平来选择路由。但是EBCS的簇头选举机制仍旧存在不足，即没有对竞选的簇头进行能量限制;同时没有设立簇头的连任机制，再进行簇头选举只会导致该节点的加速死亡，节点无法胜任簇头的任务，不仅影响了网络性能，也导致了能量的浪费。

上述算法均没有节点的复活机制，即节点进入休眠状态直到积累的能量总值达到设定门限值时才复活。

综上所述，本文在EBCS的基础提出了基于簇头优化的自供能无线传感器网络分簇路由算法(Clustering routing algorithm based on Cluster-head Optimization for Self-energized wireless sensor network，CCOS)。主要改进如下:1)完善簇头选举机制，保证当前剩余能量足的节点才有资格参加簇头选举，以此提高网络寿命。2)引用并改进簇头连任机制，保证那些剩余能量高且能量补给水平高的簇头节点能够继续连任，以此减少竞选簇头的能量浪费。3)针对网络中簇头和簇成员的不同角色设计了阈值敏感的节点复活机制，当节点死亡后随机、按比例地判断自己在复活后需要担任的角色，并根据软、硬门限值来决定自己的休眠时间，保证节点复活后具有足够的能量完成数据的采集与发送任务，以此提高数据的成功传输率。

2 CCOS描述

本文提出的CCOS与其他分簇路由算法相似，网络运行均按轮循环，每一轮分为簇建立阶段和数据传输阶段。CCOS在EBCS的基础上改进了现有的簇头选举机制以及簇头连任机制，同时提出了阈值敏感的节点复活机制。

2.1 簇头选举机制

在CCOS中，为了避免能量较低的节点依然有机会当选簇头问题，该簇头优化方案设置了竞选簇头的门限Ek_th，即节点当前能量值低于门限值时，节点不能参加簇头竞选。

本文采用一阶无线通信能耗模型［12－13］，在簇的建立过程中，一个包含m个簇成员的簇头需要消耗的总能量EBuild为:

其中:lS、lR、lT分别代表簇头发送的宣告消息、接收的入簇消息、发送簇成员的时隙消息的比特数;ETx、ERx表示簇头节点发送、接收1 b数据所消耗的能量;εfs为采用自由空间模型时功率放大器的能耗因子;d表示通信距离。

在数据传输阶段，簇头节点需要接收簇成员的数据包，并对所有簇成员的数据进行融合、压缩后发送给下一跳簇头节点，如果没有合适的下一跳，簇头节点就需要通过单跳的方式将数据发送到Sink节点。簇头节点在数据传输阶段需要消耗的最大能耗为 Ech_cost，非簇头节点的簇成员最大能耗为Ench_cost，其计算分别如式(2)、(3)所示:

其中:εamp为采用多径衰减模型时功率放大器的能耗因子;Eelec代表发射电路损耗因子。

当节点能量小于Ek_th时，节点就可能无法完全完成簇头节点的功能。因此，当节点能量小于Ek_th时，节点不能竞选簇头节点。Ek_th的表达式为:

CCOS改进后的簇头自举阈值T(i)为:

其中:

式中:r为当前轮次;Estart为传感器初始能量;Eresidual(i)为节点i在当前轮的剩余能量;Eharvest(i，r－j)表示节点i在第r－j轮中总共获得的补给能量;Ecurrent为节点当前能量;P为簇头在全网的比例数;n表示当前轮次距离上一次当选簇头轮次的差值，一旦节点成功竞选簇头，那么n就重新置0。

2.2 簇头连任机制

假定簇头节点i当前的剩余能量为Eresidual(i)，当前第r轮总共补给的能量为Eharvest(i，r)，那么只要同时满足以下两个条件就可以担任簇头:

其中:Ech_cost簇头节点在下一轮整个簇的总能量消耗;Ench_costr为非簇头节点在一轮中最大的能耗，它等于它直接将数据包发送给Sink节点所需的能耗。

连任成功的簇头节点i广播一个RE_CH_MSG的消息告知它的簇成员在下一轮它仍为簇头，簇内所有成员接收到该广播消息后，就在下一轮的开始不再参与簇建立的过程，仍旧按照上一轮分配的时隙将采集到的数据发送给簇头节点。周围其他节点接收到该广播消息后对其进行存储。如果该节点在新的一轮成功竞选为簇头节点，那么就提取RE_CH_MSG消息中有关连任簇头节点的相关信息，作为它的邻居簇头节点;否则竞选簇头失败的节点就将RE_CH_MSG消息删除。

这样可有效避免那些剩余能量高但是能量补给水平不高的节点继续连任簇头，因为这样只会加快该节点的死亡。而那些上一轮总补给能量大于它当簇成员的能耗的节点，只要具有足够的剩余能量就可以继续担任簇头，这是因为一旦它的剩余能量不足以担任簇头了，由于它的能量补给水平高于当簇成员时的能耗，能量补给水平在短期内具有一定的连续性，那么在接下来担任簇成员的轮次中，节点就可以通过环境能源的补给而使自己的能量逐渐补充回来。

2.3 阈值敏感的节点复活机制

在自供能网络中，节点死亡后，如果复活的能量阈值过大，会造成节点需要休眠补充能量的时间过长，因而节点被抑制不能进行正常工作，从而影响了该区域的数据采集。如果复活能量阈值设置过小，又可能会造成某些节点整个采集、发送数据过程还没进行完再度死亡，造成了对补给能量的浪费，影响了数据传输成功率。

CCOS提出一种灵活的阈值敏感的复活机制，即针对网络中簇头和簇成员的不同角色设计了阈值敏感的节点复活机制，即当节点死亡后随机、按比例地判断自己在复活后需要担任的角色，并根据软、硬门限值来决定自己的休眠时间，保证节点复活后具有足够的能量完成数据的采集与发送任务，从而保证数据传输的成功率，避免了在全网能量水平很低时，监测区域长时间内无数据采集上报的情况。在CCOS中定义了两个复活能量门限概念:

1)软门限。定义了一个能量门限值，等于节点累积到大于它复活后担任角色所需的复活能量值，在本文中软门限的值分别为簇头能耗Ech_cost和簇成员能耗Ench_cost。

2)硬门限。定义了另一个能量门限值，网络预设的固定的能量复活值。

假定节点当前能量补给速率为α，每轮经历时间为T。根据式(2)和(3)可以依次计算出，簇头节点接收(N/K－1)个簇成员需要消耗的最大能量为Ech_cost，非簇头节点所需的最大能耗为Ench_cost。

CCOS中整个死亡与复活机制的执行过程如下:

1)每轮开始时，节点i首先进行判断，若Eresidual(i)大于等于死亡能量值Edead，即节点当前具有足够能量，直接按正常的分簇算法流程执行;若Eresidual(i)小于死亡能量值Edead，则节点死亡，不再进行簇头选举，直接执行步骤2)。

2)节点随机产生一个0～1的数，如果这个数小于预设簇头概率P，那么它在复活后担任簇头，执行步骤3);如果这个数大于等于P，那么它在复活后担任簇成员，执行步骤4)。

3)复活后担任簇头的节点i首先判断软门限Ech_cost(i)与硬门限Ere_th的大小。若Ech_cost(i)小于Ere_th，那么节点i就等到它采集到的总补给能量Ere_harvest(i)大于等于Ech_cost(i)时醒来;否则，节点就等到它采集到的总补给能量Ere_harvest(i)大于等于Ere_th时醒来。之后执行步骤5)。

4)复活后担任簇成员的节点i首先判断软门限Ench_cost(i)与剩余能量Eresidual(i)的大小。若Ench_cost(i)小于Eresidual(i)，则直接按正常分簇算法流程执行，等待周围簇头的广播消息。若Ench_cost(i)大于等于Eresidual(i)，那么再判断Ench_cost(i)与硬门限Ere_th的大小，如果Ench_cost(i)小于Ere_th，那么节点i就等到它采集到的总补给能量Ere_harvest(i)大于等于Ench_cost(i)时醒来;否则节点就等到它采集到的总补给能量Ere_harvest(i)大于等于Ere_th时醒来。醒来后等待周围簇头的广播消息。

5)发送簇头广播消息，簇头结合根据自己当前的剩余能量根据式(2)计算出m，之后按正常分簇算法流程执行，最多接收m个簇成员。

完整的节点死亡与复活流程如图1所示。

图1 节点死亡与复活流程Fig.1 Flow chart of node death and resurrection

当全网能量补给水平很低时，随着网络继续运行，大量节点将会进入死亡状态。在CCOS中，通过设计阈值敏感的节点复活机制，不仅可以保证网络中簇头的比例，使复活后的节点具有足够的能量来正常执行分簇算法的整个过程，提高了数据传输的成功率，也避免了死亡面积大的监测区域长时间没有节点采集数据的情况，增加了网络的寿命。

3 仿真实验与性能分析

本算法在计算机上使用OPNET仿真软件进行建模验证［14］，实验配置环境为:硬件环境为Intel Core i5-3570 CPU@3.40 GHz，操作系统为 Windows 7(64 位)，仿真软件为OPNET 14.5，其他软件 Microsoft VC++6.0。该仿真实验同时选取EBCS作为比较对象，并结合太阳能的特点，设置了两种不同的能量补给场景，通过仿真结果来比较分析这两种算法在对节点平均剩余能量、网络存活节点数、平均簇头个数以及数据传输成功率等方面性能指标的差异。

3.1 仿真场景及参数设置

CCOS中节点的自供能模型采用太阳能，根据文献［15］中的太阳能，设定采能功率密度为15 mW/cm3，电源体积为2节5号(约9 cm3)的电池。为了验证CCOS中的簇头优化方案以及复活机制的可行性，根据太阳能的能量补给特性，分别在两种不同的能量补给场景中进行仿真实验来验证CCOS的正确性与可靠性。这里规定仿真总时间为3000 s，每轮时间30 s。

表1 仿真参数设置Tab.1 Setting of simulation parameters

网络场景面积为300 m*300 m区域，其中有100个传感器节点随机均匀分布。仿真中能量补给场景结合日常太阳能的特点分为白天和夜间两种情况。1)白天时刻补给的能量值分别为:0 s～1 000 s为从0 J递增至0.000 2 J，1 000 s到2 000 s稳定在0.000 2 J，2 000 s～3 000 s能量从 0.000 2 J递减为0 J。2)夜间时刻，节点均处于低能量补给的稳定状态，能量补给值设置为0.000 01 J。

3.2 能量补给场景一的仿真结果与性能分析

在能量补给场景一中，节点所获得的太阳能在白天的变化分别为递增、稳定和递减状态，利用这一能量补给特点，分别分析在不同时刻下节点的平均剩余能量、网络存活节点数和数据传输成功率，仿真结果如图2所示。

图2 场景一不同算法的性能对比Fig.2 Performance comparison of different algorithms in scene one

1)节点平均剩余能量。

图2(a)表示两种算法网络中所有传感器节点在不同轮次时的平均剩余能量水平，可以看出，CCOS的节点平均剩余能量整体均大于EBCS。在前30轮中两种算法均处于下降趋势，随着补给能量逐渐增加，CCOS采用的簇头连任机制可以有效减少整个簇在建立过程中能量的消耗，因此CCOS的剩余能量水平在逐渐上升，同时CCOS对自举簇头阈值进行了深一步的优化，当前能量较低的节点只有等补给到足够的能量才能竞选簇头，避免了采集到的环境能量浪费。而在EBCS中，节点平均剩余能量仍旧处于下降趋势，但是下降幅度明显随着补给能量的增加而减小。在仿真2000 s后，随着补给能量的开始减少，CCOS和EBCS的节点平均剩余能量均开始下降，但CCOS仍然高于EBCS。

2)网络存活节点数。

当网络中有大量节点死亡后，死亡节点所处区域的数据信息就不能得到及时采集、监测。图2(b)表示的仿真结果是在不同轮次中两种算法网络中存活的可以正常工作的节点数，可以看出，CCOS的网络存活节点数量高于EBCS，是因为CCOS在设计簇头阈值时考虑了节点的当前能量能否胜任下一轮簇头的能量消耗，如果能胜任则该节点才有机会竞选簇头，否则就将自己当前轮的簇头选举阈值修改为零，这就保证了那些能量足的节点能够选举簇头，避免了簇通信过程中簇头节点能量不足而死去的情况。在EBCS中，节点随机选举簇头节点，当前能量小的节点也有可能成为簇头节点，最终导致过早死亡，因此网络存活节点数小于CCOS。

3)数据传输成功率。

图2(c)表示在不同轮次中两种算法网络中传感器节点在数据通信阶段的成功率计算，可以看出，在CCOS中，数据传输成功率要大于EBCS，这是由于改善后的簇头选举机制能够有效保证能量大的节点才有机会竞选簇头，在发送与转发数据时具有足够的能量，不会导致数据传输的失败，因此数据传输成功率也就增加。而在EBCS中，在每一轮开始选举簇头时，有可能会出现当前能量比较小的节点最终成功当选为簇头，导致簇头在发送与转发数据的过程中因为没有足够的能量而无法将数据成功发送出去，从而影响了数据传输成功率。

3.3 能量补给场景二的仿真结果与性能分析

在能量补给场景二中，节点所获得的太阳能在夜间的变化规律为低能量补给的稳定状态，利用这一能量补给特点来分析网络存活节点数、平均簇头个数和数据传输成功率，仿真结果如图3所示。

图3 场景二不同算法的性能对比Fig.3 Performance comparison of different algorithms in scene two

1)网络存活节点数。

图3(a)表示在夜间时两种算法网络中的存活节点数，可以看出，由于当前能量补给水平很低，节点所获得补给能量要远远小于节点的能量消耗，因此CCOS和EBCS两个算法的网络存活节点数均处于下降状态。由于EBCS的簇头选举阈值不够完善，同时采用了固定的能量阈值的复活机制，节点死亡后的总能量只有达到一个设定的能量值时才能复活。而在CCOS中，只有当前能量充足的节点才能竞选，避免了竞选出来的簇头过早死亡，此外CCOS采用的节点复活机制，使节点在满足软、硬阈值其中之一时就可以复活，因此节点复活速度要快于EBCS。

2)平均簇头个数。

图3(b)表示在夜间时两种算法网络的平均簇头个数计算，可以看出，随着网络运行，网络中的平均簇头个数逐渐减少。这是因为当前能量补给水平一直很低，在网络后期节点的大量死亡以及簇头自举阈值越来越小都会影响网络中的簇头个数。在CCOS中，当节点死亡后需要随机、按比例地判断自己在复活后需要担任簇头节点还是簇成员节点，因此，在网络能量水平不断下降的同时能够较好地保持网络中簇头的数目。而在EBCS中，当网络能量水平很低时，节点的选举阈值越来越小，同时节点复活后，不管自己当前的能量能否胜任簇头一职，都会开始参加簇头选举。但是由于刚复活时的能量特别小，因此节点的簇头自举阈值很小，导致选举出来的网络中簇头数目很少，从而使网络平均簇头个数较少。

3)数据传输成功率。

图3(c)表示在夜间时两种算法网络中节点的数据传输成功率，可以看出，CCOS的数据传输成功率高于EBCS。这是因为CCOS采用的簇头自举阈值函数保证了选举出来的簇头节点能够成功有效地传输数据，同时，当节点进入死亡状态时已经确定了复活后是当选簇头还是簇成员，如果担任簇头节点，那么就按簇头所需的能量计算自己的软门限，当它累积到足够建簇和簇间通信时所需能耗后复活，因此它具有足够的能量保证数据成功的传输。而EBCS在随机选举簇头时有可能让能量很低的节点当选簇头，簇头因为没有足够的能量发送或者转发数据，从而降低数据传输成功率。

4 结语

在现有自供能网络算法中簇头选举机制不合理、簇头不能连任以及没有节点复活机制的基础上，本文提出了一种基于簇头优化的自供能无线传感器网络分簇路由算法(CCOS)。CCOS对簇头选举阈值进行了深一步优化，引入并改进了簇头连任机制，使簇头结合自己的能量补给水平来决定自己能否在下一轮继续连任簇头。CCOS还提出了节点阈值敏感的复活机制，使节点的能量复活阈值不是固定的，而是更加地灵活。最后通过使用OPNET仿真工具，在两种不同的太阳能能量补给仿真场景中对CCOS和EBCS进行仿真分析，仿真结果分析表明:CCOS的节点剩余能量水平较高，其中网络存活节点数量增加约8%，数据传输成功率增加了约5%，因此可以更好合理地利用太阳能补给能量来增加网络的正常运行时间，保证网络通信数据传输速率。未来将结合更多复杂的能量补给环境、如振动能、风能等来研究传感器网络的路由算法。