能量感知休眠的ELSS算法在WSN中的优化研究
2018-07-23王海花
王海花，刘 云，向 婵
(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)
在无线传感器网络(WSN)中，延长网络生命周期[1]是目前研究的一个关键领域。由于传感器节点数目庞大，且大多数节点离基站距离较远，导致能量利用效率过低，网络生命时间过短等问题[2]。
Heinzelman W[3]等人提出了LEACH协议，通过分簇，以循环的方式随机选举簇头，集中式处理节点到基站之间的数据传输，将整个网络的能量负载平均分配到每个节点上，一定程度上降低了节点的能耗[4]，延长了网络生命时间。但是由于LEACH协议存在多次分簇的缺陷，造成了能量浪费。
兰慎[5]等人又在LEACH协议的基础上提出了S_LEACH协议，该算法通过一次分簇，形成工作簇头和休眠簇头，并随机选择休眠簇头进入工作状态，节省了大量因多次分簇所造成的能量损失。
LEACH协议和S_LEACH协议都在原有基础上降低了能耗，延长了生命时间。但是LEACH协议多次分簇，且大量工作负载都集中在簇头节点上进行，造成能量浪费，S_LEACH协议随机选择休眠簇头，不能保障簇头之间的能量平衡，无法保障稳定性，并且让被替换掉的工作簇头继续充当普通节点工作，也造成了簇头节点的能量损失。
本文借助S_LEACH协议的优势提出了能量感知选择休眠簇头算法ELSS。
1 模型建立
在无线传感器网络中，为了使网络生命时间最大化，就必须使传感器节点能量得到最大利用。相对而言，在网络工作过程中，簇头节点工作负载更大，需要消耗的能量也就更多，因此若想保障网络生命时间，就必须保障簇头节点的正常工作，此时就必须寻找额外的传感器节点来分担簇头节点的工作压力[6-7]。显然，LEACH协议已不能提供足够的网络需求，而S_LEACH协议虽然可以提供休眠簇头来轮流充当簇头工作，但是由于其随机性仍然不能保障休眠簇头的能量平衡，以及其将替换掉的簇头作为普通节点继续探测工作也造成簇头节点能量损失，从而不能保障簇头节点能量最大化利用。
因此，本文在LEACH协议基础上对S_LEACH协议做出如下改进，从而提出能量感知选择簇头算法-ELSS，算法模型如图1所示。
图1 ELSS算法模型
首先，定义该无线传感网络中各子网络的工作簇头用集合{Aio|Aio=A1o,A2o,A3o,…,Ako}表示；某个子网络中的各休眠簇头用集合{Ais|Ais=A1s,A2s,…,Ans}表示；子网络中各节点整体的剩余平均能量为Ea，工作簇头节点剩余能量为E1，各休眠簇头节点剩余能量分别为E1l，E2l，E3l,…,Enl，除休眠簇头以外的各节点剩余能量为E1，E2，E3,…,En。
其次，假设有N个节点均匀分布在一个A=M×M区域，且基站离监测节点都相对较远。在这种情况下存在两种能量衰退模型，一种是多路径衰退模型，其衰退系数为εmp，另一种是自由空间衰退模型，其衰退系数为εfs。如果网络中各节点到基站的距离用dtoBS表示，那么网络中所存在的最优工作簇头个数kopt可通过式(1)[8]计算得出
(1)
其中节点到基站的平均距离dtoBS可由式(2)计算得出
(2)
其中，x和y是以基站为原点，任意方向为正方向下各节点的坐标值。
同理将监测区域内的每一个子网格看成是另一个分簇网络结构，其中的工作簇头就相当于基站，确定的休眠簇头就相当于整个网络中的工作簇头。此时，假设其中某个子网格中有n个节点均匀分布，子网格大小为a=m×m，工作簇头位于子网格的中心位置，子网格中各节点到工作簇头的平均距离用dtoHS表示，那么该子网格中所需要的休眠工作簇头的个数k1就可以由式(3)[9-10]计算得出
(3)
其中节点到工作簇头的平均距离dtoHS可由式(4)[11]计算得出
(4)
其中，x和y是以工作簇头为原点，任意方向为正方向下子网格中各节点的坐标值。
2 ELSS算法
2.1 算法描述
假设经计算所得最优簇头数为k，则根据计算所得簇头数k在监测区域等面积划分为k个子区域，并在相应区域寻找一个最接近中心位置的传感器节点作为首个工作簇头节点A1o，A2o，A3o,…,Ako。至此，各分簇簇头节点已经选定。
在各分簇簇头产生之后，簇头节点Aio向周围所有传感器节点普遍发送当选簇头信息，各传感器节点根据收到簇头节点信号的强度选择信号最强的簇头节点加入其所在簇，并将加入信息回复给簇头节点[12-14]。然后，簇头节点根据回复信号强弱选择信号最强的n个节点A1s，A2s,…,Ans作为休眠簇头(n为式(2)计算所得分簇休眠簇头数)，并根据节点ID将选举结果通知相应休眠簇头节点。最后簇头节点将收录得到的信息，包括休眠簇头信息通知基站，并收到基站的回复。这样，整个分簇过程才是成功的，簇头组形成，分簇阶段结束[15]。
在分簇阶段结束过后，WSN就将进入工作阶段。工作阶段首先由首次选定的工作簇头Aio开始工作，管理与收发所在簇内各节点信息。同时簇头节点不停地探测簇内各节点的剩余能量，并通过求均值函数式(5)取得整体剩余能量均值Ea。
(5)
然后将Ea与自身剩余能量El比较，若Ea
MAX{E1l，E2l，E3l，…，Enl}
(6)
当Ais接收到消息后做好工作准备并回复消息给Aio，Aio收到回复后立即将更换簇头消息发送给基站，得到基站的回复后再将更换簇头信息及新簇头ID发送给簇内所有节点，包括新簇头Ais，Ais收到信息后立即开始工作，并再次回复Aio，Aio收到回复进入休眠。这个过程依次反复，直到所有节点能量耗尽。
2.2 算法分析
相比较LEACH协议算法和S_LEACH协议，ELSS算法在延长网络生命周期方面做出了进一步的改进。由于ELSS算法在分簇阶段采用的是S_LEACH协议的分簇机制，所以相对于LEACH协议在延长生命时间方面做出的改进在文献[2]中已有分析，通过避免多次分簇所造成的能量损失来延长网络生命时间。因而本算法将不再针对LEACH协议进行比较分析，而将着力比较S_LEACH协议，从能耗和能量平衡两方面来分析本算法对延长网络生命时间所作出的改进。
(1)能耗分析。在子网络中，假设所有簇头(包括初始工作簇头和休眠簇头)的初始能量均为Em1，簇头节点工作平均每个单位时长消耗能量为m1；所有工作中的节点(包括普通传感节点和工作簇头节点)的初始平均能量为Em2，平均每个节点每单位时长消耗能量为m2；易知：Em1>Em2，m1>m2。在S_LEACH协议中，由于被替换掉的簇头节点将被降为普通节点，所以每个簇头节点只工作一次。于是令从第一个簇头节点开始，每个簇头节点工作的时长分别为T1，T2，T3，…，Tn。
在S_LEACH协议中，当初始簇头节点工作完毕时，已知其节点剩余能量约等于所有节点的平均剩余能量，于是可得等式
Em1=m1T1=Em2-m2T1
(7)
即可以表示出第1个簇头节点工作时间为
(8)
那么，第1个簇头节点所造成的能量损失为
(9)
第2个簇头节点工作完毕剩余能量等式为
(10)
即第2个簇头节点工作时间为
(11)
那么，第2个簇头节点所造成的能量损失为
(12)
同理可得第3个簇头节点所造成的能量损失为
(13)
(14)
因此，ELSS算法相对于S_LEACH协议在簇头组内所减少的能量损耗为
(15)
(2)能量均衡分析。能量平衡对于传感网络的稳定性有着至关重要的影响。S_LEACH协议在簇头节点更换时使用随机选择机制，这样有可能选择到能量较低的休眠簇头进行工作，而这样的簇头不能保证长时间的工作，就需要频繁更换簇头，不仅造成了能量在更换簇头时的浪费，而且容易造成部分簇头节点过早死亡，导致传感网络的稳定性下降。
当用ELSS算法来代替S_LEACH协议进行更换簇头，该算法将会对休眠簇头剩余能量进行比较选择能量最高的休眠簇头来代替原有工作簇头进行持续工作。这样可以使整个簇头组节点能量稳步减少，保障簇头组内节点能量的平衡，不仅避免了簇头频繁更换造成的能量损失，而且提高了整个网络的稳定性，从而保障网络更持续长久的工作。
3 仿真结果
本文以Matlab作为实验仿真平台，在区域为100 m×100 m的范围内随机部署100个节点，基站位置为(175，50)，节点初始能量为0，5 J。针对网络整体平均剩余能量随时间的变化趋势和死亡节点数随时间的变化趋势来研究网络的生命时间问题进行了仿真分析。
图2 3种算法的生命时间
图2表示随着时间的增加3种不同算法整体平均剩余能量的变化，表明了两个问题：其一，ELSS算法下整个网络的整体平均剩余能量相较于LEACH协议和S_LEACH协议下降趋势明显更缓慢，在减少到0之前持续的时间更长久；其二，ELSS算法下整个网络的整体平均剩余能量相较于LEACH协议和S_LEACH协议下降的趋势更平缓。从而验证了ELSS算法对延长整个网络生命时间周期起到了促进作用，同时也保障了整个无线传感网络工作的稳定性。
图3 3种算法的死亡节点数比较
图3表明ELSS算法下整个网络的节点的死亡时间相对于LEACH协议和S_LEACH协议得到有效的延迟。ELSS算法一部分减少了S_LEACH协议算法中簇头节点降为普通节点所造成的簇头组能量损失；另一部分又通过能量感知选择最高能量休眠簇头来分担工作簇头的工作压力，保障了簇头组之间的能量平衡，从而大幅降低簇头组节点的死亡概率。两部分的优势促使了ELSS算法能够有效保障整个网络持续工作，从而有效延长了网络的生命时间。
4 结束语
介绍了LEACH协议和S_LEACH协议协议的工作原理，并针对这两种算法的不足在其基础上提出了一种能量感知选择簇头的算法-ELSS，该算法通过感知休眠簇头的能量，选择能量最多的休眠簇头替换工作簇头。ELSS算法与LEACH协议相比避免了多次分簇造成的能量损失，与S_LEACH协议相比减少了簇头传感器的能量消耗并保障了休眠簇头传感器之间的能量平衡。仿真分析表明，ELSS算法的稳定性更好，并且能够在能量有限的前提下更大限度地延长网络生命时间。
