基于节点向心性路由协议簇首的选举协议

王 军， 马德朋， 徐万一， 张亚君

(沈阳化工大学 计算机科学与技术学院， 辽宁 沈阳 110142)

无线传感器网络WSN(Wireless Sensor Network)是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成一个多跳的自组织的网络系统.它的目的是协作地感知、采集和处理网络覆盖区域中被感知对象的信息，并发送给观察者.传感器、感知对象和观察者构成了无线传感器的3个要素[1].由于WSN具有节点可以大规模部署、自组织网络、动态性的网络拓扑结构、数据和传输的可靠性以及传感器节点高度集成的特点，使其在军事监控、环境监测、地震与气候预测、抢险救灾、地下、深水以及外层空间探索等许多方面都具有广泛的应用前景[2-3].

当今WSN路由协议的研究已经成为国内外备受关注的热点[4].传感器节点的能量消耗问题直接影响着无线传感器网络的生命周期[5-6].本文是在原有LEACH路由协议的基础上，提出XX_LEACH路由协议.改进后的路由协议很大程度地延长了无线传感器网络的生命周期，提高了数据传输的效率.

1 WSN路由协议的介绍

无线传感器网络网络层路由协议执行效率的高低对传感器节点收发信息有直接的影响，进而影响到传感器节点的能量消耗，最终影响到整个WSN的性能[7].因此，网络层的路由协议是当今WSN研究的重要方向[8].这类协议主要是使监测区域节点和目的节点(sink)之间的数据得到最优化路径传输[9].

2 LEACH路由协议概述

LEACH是一种基于聚类的路由协议，是最早的路由协议[10-11].LEACH协议主要分为类准备和就绪两个阶段.在类准备阶段，LEACH协议随机地选取一个传感器节点作为簇头节点.类形成之后进入就绪阶段，簇头节点开始接收簇内节点采集的数据，经过数据融合技术的处理，将整合之后的数据传输给目的节点(sink)[12-13].

2.1 LEACH簇头的产生算法

首先在每个节点中选取0～1之间的随机数，与阈值T(n)比较，小于阈值的作为簇头.簇头向节点广播自己成为了簇头的消息，节点根据收到信号的强弱选择簇头，并回复簇头.其中T(n)的计算公式为：

(1)

其中：p是簇头占所有节点百分比；rmod(1/p)代表一轮循环中当选簇头节点的个数；G是最近1/p轮中还没有当选过簇头节点的集合；r是目前循环的轮数；n为节点的总数.

2.2 LEACH协议算法流程

图1为LEACH协议算法的流程，主要分为簇的建立、簇的形成、簇的路由、簇的循环几个步骤[14].

图1 LEACH协议算法流程Fig.1 LEACH Protocol algorithm flowchart

3 改进的LEACH路由协议

在LEACH路由协议中，为了减慢簇内节点的能量损耗，提高数据传输的准确性，使簇内节点的能量消耗更均匀且缓慢，提高节点的能量利用效率，设计了XX_LEACH路由协议.改进的LEACH路由协议主要是通过评估簇内各节点与簇内中心的距离和节点能量剩余以及节点温度的综合值来作为选取簇头的参考，进而使簇内边缘节点传递的数据更加可靠，避免簇内少数节点出现过早死亡的现象，有效地增强了无线传感器网络节点数据传递的全面性和真实性.

3.1 基本思想

3.1.1 节点向心性

节点的向心性指的是簇建成之后簇内各个节点距簇中心的距离.通常在簇头选举时用来衡量是否可以作为簇头的标准.

3.1.2 算法的基本思想

XX_LEACH协议算法的环境与LEACH协议的环境相同：(1)初始化网络节点都属于同种类型；(2)初始能量相同；(3)各节点在每一帧(Frame)中都有数据传送；(4)节点静止；(5)基站固定并远离WSN.假设初始值都为1，经过一次循环后，簇内节点的能量损耗各不相同，下一轮开始前，计算出每一个节点的位置距离簇内中心位置的距离、剩余能量和节点温度的综合值作为下一轮簇头选举的条件.

由LEACH路由协议，在第一轮结束时计算出簇内各节点位置的向心性、能量剩余和节点温度的综合值.将综合值和其他数据发送给簇头节点，由簇头经过数据融合之后传送给基站.再由基站计算出当前各簇内节点位置的向心程度、能量剩余和节点温度的综合值，并与第一轮的综合值比较，如果差值大于阈值T(n)时，在网络模型中删除该节点，再把剩余的节点依据LEACH路由协议中规定T(n)的选举下一轮的簇头.实验结果表明：该过程可以提高网络数据传输的可靠性，延长网络生命周期.

3.1.3 计算方法

(1) 计算节点的剩余能量

当节点n将k位的数据传送的距离为d时，剩余的能量公式为：

En(k,d)=Ec-(Efkd+Ejk)

(2)

其中，En(k,d)表示节点剩余的能量，k表示报文的长度，d表示传输的距离，Ec表示节点初始能量，Ef表示节点发送单位数据时消耗的能量，Ej表示节点接收单位数据时消耗的能量.通过计算簇内节点的剩余能量，将其作为评估节点是否可以作为簇头的条件之一，从而可以延长网络的生命周期.

(2) 计算节点的向心性

通过计算节点n的位置坐标(Si,Se)与簇内中心坐标(Za,Zb)的距离，解决节点边缘化带来的数据传输不准确、不及时的问题.其计算公式为：

Dn(S,Z)=(Si-Za)2+(Se-Zb)2

(3)

其中，Dn(S,Z)表示簇内节点到簇内中心的距离，Si表示节点的横坐标，Se表示节点的纵坐标，Za表示簇内中心的横坐标，Zb表示簇内中心的纵坐标.在无线传感器网络中，计算节点的向心性，将其作为评估节点是否可以成为簇首的另一个条件.节点向心性有效地提高了节点数据传输的可靠性，避免了不良位置节点传输数据的片面性和单一性.

(3) 计算节点的温度

无线传感器网络在运行的过程中，节点n随着能量消耗EX的变化，节点温度的计算公式为：

(4)

其中，Hn(t)表示节点的温度值；EX表示节点的消耗能量；EC表示节点的初始能量；β表示节点容热值的权值，其值根据实际应用选取；βEX/EC即表示温度的变化系数；HC表示节点的初始温度.通过计算无线传感器网络中节点的温度，将其作为簇首选择时的一个条件，可以更好地解决簇内节点负载过大时，能耗多的节点过早死亡的问题，有效地使簇内节点的能量均匀消耗，使网络的生命周期得到延长.

(4) 计算节点n的剩余能量、节点向心性以及节点温度的综合值

综合评估节点的剩余能量、节点的向心性和节点温度，作为最终节点可以选为簇头的条件.其计算公式为：

Pn=α1En(k,d)+α2Dn(S,Z)+α3Hn(t)

(5)

其中，α1、α2、α3分别表示节点剩余能量、节点的向心性和节点温度的权重值，具体权重值在应用中根据实际情况选取.

3.2 算法流程

在真实环境里的无线传感器网络中，簇首选举往往不能保证能量的均匀消耗以及簇内节点过渡边缘化造成的节点过早死亡、传输的数据不可靠等问题.XX_LEACH路由协议改进簇首选举的评估机制，通过计算簇形成后各节点到簇内中心的距离和节点的剩余能量以及节点温度的综合值来作为选择簇头的条件.该算法可以很大程度地提升数据传输的真实性，延长网络的生命周期，可以解决实际环境中无线传感器网络存在的问题.其具体的算法流程如图2所示.

图2 XX_LEACH协议算法流程Fig.2 XX_LEACH protocol algorithm flowchart

3.3 算法的伪代码

由XX_LEACH路由协议的算法流程，设计出算法的伪代码，可以更直观地看出该算法的执行过程.具体编写如下：

Begin

输入P1，Pn-1，Pn

输入T(n)

IFPn-Pn-1>=T(n)

则删除该节点，执行LEACH路由协议

否则执行LEACH路由协议

Print循环此过程

End

4 仿真

4.1 搭建仿真环境

在仿真环境中，为了更清晰地了解改进后的LEACH路由协议，XX_LEACH设置的仿真参数如表1所示.

表1 仿真参数Table 1 Simulation parameters

4.2 仿真结果与分析

使用OPNET网络仿真工具进行仿真，同时使用MATLAB数据分析软件进行数据结果比较分析，从无线传感器网络中网络的剩余能量和节点的存活数对LEACH协议、NPT_LEACH协议和XX_LEACH协议进行对比[15].

在LEACH协议、NPT_LEACH协议和XX_LEACH协议中，各自的节点剩余能量变化如图3所示.

图3 3种协议剩余能量的比较Fig.3 Comparison of residual energy of three protocols

在0～79轮时，LEACH协议、NPT_LEACH协议和XX_LEACH协议节点的剩余能量几乎相同；在79轮之后，随着时间的增加，3种协议下节点所剩的能量开始出现差距，LEACH协议和NPT_LEACH协议中节点的消耗能量增多，XX_LEACH协议中节点的剩余能量明显多于LEACH协议和NPT_LEACH协议中节点剩余能量.研究结果表明：改进的XX_LEACH能够减少能量的消耗，延长网络的生命周期.

观察LEACH协议、NPT_LEACH协议和XX_LEACH协议，3种协议在相同时间内，存活节点数的变化如图4所示.当最初都为100个节点存活时，LEACH协议、NPT_LEACH协议和XX_LEACH协议在600轮之后，XX_LEACH协议存活的节点个数明显高于LEACH协议和NPT_LEACH协议存活的节点个数；LEACH协议和NPT_LEACH协议在1 600轮时，节点全部死亡，而XX_LEACH协议直到1 800轮时才全部死亡.改进结果表明：XX_LEACH协议比LEACH协议和NPT_LEACH协议性能更好；XX_LEACH协议使节点存活的个数显著增多，能延长无线传感器网路的生命周期.

图4 3种协议存活节点的比较Fig.4 Comparison of survival nodes of three protocols

LEACH协议、NPT_LEACH协议和XX_LEACH协议中节点的分布情况如图5～图7所示.

图5 LEACH协议节点的分布Fig.5 LEACH protocols node map

图6 NPT_LEACH协议节点分布Fig.6 NPT_LEACH protocols node map

图7 XX_LEACH协议节点分布Fig.7 XX_LEACH protocols node map

从图5、图6中可以清楚地看到：LEACH协议节点和NPT_LEACH协议节点与簇头之间的距离比较分散，边缘节点时刻存在，造成簇头的负载不均衡，能量消耗不均匀等结果.而通过改进的XX_LEACH协议与LEACH协议和NPT_LEACH协议相比，可以明显地看出节点与簇头之间的距离趋近于均匀分布(见图7)，能更好地实现节点的能耗均匀，数据传输更有效.

根据仿真结果比较LEACH协议、NPT_LEACH协议和XX_LEACH协议的性能.从路由策略、以数据为中心、最优路径、稳定性和可靠性5个方面分析[9]，得出的结论如表2所示.

表2 3种路由协议性能的比较Table 2 Comparison of three routing protocols

5 算法分析与展望

基于节点向心性的路由协议簇首选举，在LEACH协议的基础之上，提出了XX_LEACH路由协议.以节点的向心性和节点的剩余能量以及节点温度综合值作为簇首选举的标准，有效解决了无线传感器网络中各节点，尤其是边缘节点数据传输时能量消耗不均匀的问题.XX_LEACH路由协议算法的提出，能够提高各节点的能量利用效率，延长网络的生命周期，解决LEACH路由协议簇首选取方法的不足.通过OPNET网络仿真工具，使用MATLAB进行数据分析比较，对新型的无线传感器路由协议XX_LEACH进行仿真.仿真结果表明：XX_LEACH协议与LEACH协议相比，能更好地减缓无线传感器网络中节点的能量消耗，延长网络的生命周期，该算法比LEACH的簇头选择方法更可靠.为了更好地解决无线传感器网络分簇路由的问题，对于 XX_LEACH路由协议，在以后簇头选取的研究中不能只局限于节点的向心性、节点的剩余能量和节点温度3个因素，还需要考虑簇头到基站的距离，以及节点的密集程度等因素.XX_LEACH协议的提出，在无线传感器网络的理论指导和实际发展中有着重大的意义.