能量均衡环形无线传感器网络多跳路由算法

武莎莎， 王宏志*， 胡黄水, 王出航

(1.长春工业大学 计算机科学与工程学院， 吉林 长春 130012;2.长春师范大学 计算机科学与技术学院, 吉林 长春 130032)

0 引 言

近年来，在国内外研究学者的眼中无线传感器网络(Wireless Sensor Network, WSN)[1]研究炙手可热，主要应用于医疗检测、环境监测、军事防御等不同领域，WSN可以在一个小型设备中实现传感、计算和通信功能，但WSNs在功率、存储以及计算过程方面受到限制[2]。主要是因为组合成WSN传感器节点的能量有限，而且无法进行充电[3]。WSN的核心技术是网络层的路由协议，如何通过有效的路由算法减少网络通信能耗和延长网络的生命周期已经成为当今科研人员研究的热门话题。

平面路由协议和分层路由协议是两种路由算法[4]， LEACH协议作为经典的分簇路由协议[5]具有诸多优点,其核心思想是将网络划分为若干大小不同的簇，每一个簇中有一个簇头(CH)节点,每个簇中的普通节点把信息数据汇聚到CH节点，每个CH节点通过单跳将数据发送到基站(BS)。虽然各节点轮流担当CH节点，使得网络中能量消耗尽量均衡，但CH节点以单跳的方式将数据发送到接收器，而且簇头节点的选择具有随机性，导致BS附近的CH节点过早死亡。随后又有一些LEACH算法的改进算法被提出，如LEACH-C[6]，它是一种集中式协议，其主要思想是把节点的剩余能量作为选择CH节点的因素考虑进来，集中控制CH节点的选举,但是节点在每轮数据传输开始时需要将其剩余能量和位置数据发送到BS，这导致离BS较远的节点产生额外能量消耗。文献[7]提出了一种混合式节能聚类算法HEED，其主要目的是通过多对一的通信模式实现最小化WSN的能量消耗和控制开销来延长整个网络寿命。但是在多跳协议的情况下，更靠近BS的节点通常需要承受更多的通信负载。Chao Sha等[8]提出了一种基于环空的能量平衡数据采集方法(AEBDC)，此算法提出了在候选簇头的帮助下实现数据转发，不仅减少了CH节点的负荷，同时也减少了数据上传期间缓冲溢出的可能性。但是在数据传输过程中，越靠近网络内环，需要越多的候选簇头来转发数据，增加了候选簇头节点转发数据所消耗的能量。CAMP路由协议是一种用于无线传感器的簇群辅助多路径路由协议[9]，该算法是将网络区域中的非簇头节点划分两类，两类不同的非簇头节点按照不同的工作约束条件将其数据转发到下一跳节点，该算法实现了节点能耗的均匀消耗，但是CAMP协议将网络区域划分为相等的区域，忽略了数据传输期间的能量热点问题，而且把非簇节点分为两类，增加了网络的复杂度。EEMRP算法[10]中提出了一种基于通信管理(CM)节点的管理方法，用于重建簇群和中继多跳数据传输，CM节点共享了CH节点的工作量，减少了CH节点的能量开销，但是网络需要提前确定每个网格的划分，这限制了算法的可扩展性。为了提高网络的扩展性，Jianhua huang等[11]提出了一种环形扇形网格辅助路由协议(ASGRP)，主要通过使用层间最小能量消耗路由算法建立从CH节点到BS的路由，这种方法有效地平衡了节点的能量消耗，但是在划分簇时，每个簇群的大小一样，导致离BS较近的网格中CH节点的能量消耗过快。

文中提出了一种环形无线传感器网络能量平衡多跳路由算法(Energy balanced multi-hop routing algorithm for ring wireless sensor network， EMRA),主要是在LEACH算法的基础上，采用环形无线传感器网络，同时在每个簇中引入CM节点，缓解了单个CH节点的能量负荷。在网络数据传输过程中，考虑了CH节点到BS所消耗的能量与CH节点到下一环中距离CH节点最近的CM节点所消耗的能量关系，来估算CH节点将数据发送到BS所需的跳数。同时也考虑了CH节点到CM节点的最短距离与CH节点到BS的距离关系，这使网络的生命周期得到延长，也减少了网络的能量消耗。

1 EMRA路由模型

1.1 EMRA网络模型

假设检测区域是半径为R的圆形网络区域，区域中有n个传感器节点。该网络具有如下特征：

1)整个圆形网络被均分为b个圆环区域，BS位于整个圆形网络的中心处，网络部署后,BS把自己的坐标信息发送给网络中所有传感器及节点；

2)每个传感器节点的初始能量相同，并且每个节点的传输范围和传输速率也相同；

3)网络中的链路没有冲突和重传，网络具有很好的连接性。

1.2 EMRA能耗模型

采用文献[6]中的能量消耗模型，在距离为d的节点Ni和节点Nj之间发送和接收 1 bit数据所消耗的能量可以采用下式计算：

(1)

Er=Eelec,

(2)

(3)

式中:Eelec----一个传感器节点发送或者接收1 bit数据所消耗的能量;

εfs----自由空间放大模型参数;

εmp----多跳衰减放大模型参数;

d(Ni,Nj)----节点Ni和节点Nj之间的距离。

文中采用自由空间放大模型，所以

d(Ni,Nj)

式中：d0----通信距离阈值。

CH节点融合的m个分别携带k1,k2,…,kmbit的信息所消耗的能量

(4)

2 EMRA算法设计

2.1 基本思想

EMRA算法主要是假设网络中每一环的CH节点数目按照算术级数来分布，根据式(4)计算出每一个环的CH节点数，以及每一环中CH节点和CM节点的选举概率，然后根据每一环中节点的剩余能量和节点到BS的距离选举出CM节点和CH节点，最后比较CH节点到BS的通信能耗与CH节点到下一环中CM节点的通信能耗，来确定CH节点把数据传输到BS所需的跳数。其流程如图1所示。

图1 EMRA算法流程

2.2 CM节点和CH节点选举过程

为了平衡网络能量消耗，圆形网络被均分为b个环形区域，每个环域的宽度为R/b,假设网络中每一环中的簇头节点数Ca(a=1,2,…,b),按照算术级数分布，其表达式为

Ca=2a-1,

(5)

(6)

式中:a----网络的环数;

Ca----每一环中的CH节点数;

Nua----每一环节点数;

p----CH节点选举概率。

CM节点不仅承担着数据的转发重任，同时也对节点之间的通信起着重要作用，CM节点对自身的位置以及能量有着更严格的要求,所以EMRA算法先选择CM节点，然后在余下的节点中再按照CH节点的选举权值选择CH节点。CM节点的选举考虑到节点的剩余能量以及节点到BS的最短距离。

(7)

β=mindNiB,

(8)

式中：α----当前轮次中节点的剩余能量与节点初始能量比值的最大值;

β----当前轮次中节点到BS的最短距离。

CM节点的选举阈值

(9)

式中：E0----节点的初始能量;

dNiB----节点Ni到BS的距离;

Ec----当前节点的剩余能量;

r----当前网络CH节点的轮换次数;

S----每轮结束后网络中非簇头节点集。

网络的生命周期与CH节点的选举密切相关，网络中CH节点不仅需要融合簇内节点所发送的信息，同时也需要把融合后的信息发送到BS，所以CH节点的通信能耗比较大。LEACH算法中CH节点的选择具有随机性，而且CH节点的选举只考虑了CH节点的数目与网络节点总数的关系。EMRA算法中对CH节点的选择做了改进，不仅考虑了节点的剩余能量，同时也考虑了节点到CM节点的距离与CM节点到BS距离的关系。

(10)

式中：γ----Nj到CM节点距离与CM节点到BS距离的比值,γ越大，把数据传输到BS所需能量就越少。

CH节点的选举阈值

(11)

2.3 EMRA算法路由

无线传感器网络中节点的主要能量用来发送数据，在保证节点数据完整地传输到BS情况下，如何减少节点的能量消耗，延长网络的生命周期，已经成为当今研究的热门。EMRA算法中数据传输过程如图2所示。

路由主要流程如下：

1)在数据传输阶段开始时，网络a环中某一簇内的节点i把数据发送到CH节点Nic(xic,yic),i=1,2,3,…,n后，由CH节点Nic(xic,yic)进行融合。

2)a环中的CH节点把所携带有自己的坐标Nic(xic,yic)位置的信息mic在整个网络中广播。

3)当网络中a-1 环中的CM节点Nim(xim,yim)接收到网络中节点Nic发送的广播信息后，a-1 环中的CM节点Nim(xim,yim)同时也把自己的坐标信息mim发送给a环中的CH节点。

4)a环中的CH节点根据a-1 环中CM节点所发来的信息，把数据传输到a-1环中距离自身位置最近的CM节点， CM节点负责转发CH节点所传输的数据信息，然后数据再转发下一跳中距离自己最近的CM节点，最终数据信息发送到BS，No(x0,y0)。

LEACH算法中CH节点直接把数据传输到BS，导致距离BS较远的CH节点因为较大的通信能耗而过早死亡。EMRA算法采用多跳的方式将数据传输到BS，通过比较CH节点把数据传输到BS所消耗的能量E1与CH节点把数据传输到下一环中CM节点所消耗的能量E2，估算CH节点把数据传输到BS所需的跳数H。我们仅考虑CH节点把数据传输到CM节点和BS这个过程所消耗的能量。

(12)

(13)

(14)

(15)

(16)

式中:dHB----CH节点到BS的距离;

dHM----CH节点到下一跳CM节点的距离;

nc----CH节点Nic内的簇成员节点;

l----数据包的长度。

3 性能仿真分析

文中提出的算法是在MATLAB2014a中进行的仿真实验，主要是在WSN区域为100×100的仿真环境中进行了多次实验，同时与LEACH算法进行比较，主要从网络中的节点死亡率、网络总能耗、网络平均节点剩余能量三个方面分析了EMRA算法的性能。仿真实验环境参数设置见表1。

表1 仿真环境参数设置

LEACH算法和EMRA算法在不同节点死亡率的情况下，网络中CH节点的轮换次数变化如图3所示。

从图中可以看出，EMRA算法在CH节点轮换次数为942轮时网络中第一个节点开始死亡，而LEACH算法在385轮时已经有节点死亡。而且在网络中节点的死亡率为50%时，EMRA算法的CH节点的轮换次数已经达到1 325轮，而LEACH算法的CH节点轮换次数为779轮。这说明EMRA算法可以减少网络中节点的能量消耗，缓解CH节点的负荷。

网络能量消耗随着CH节点轮换次数的变化如图4所示。

从图中可见，随着网络中每一轮CH节点轮换次数的增加，无论是EMRA算法，还是LEACH算法，它们的网络能耗都在增加。在CH节点轮换次数为1 000轮时，EMRA算法中网络能耗曲线变得平缓。LEACH算法的网络能量消耗已经达到4.453 1 J,此时EMRA算法的网络能耗是3.388 4 J。这说明EMRA算法中采用多跳的路由算法可以减少网络的能量消耗，延长网络生命周期。

网络中平均节点剩余能量随着CH节点轮换次数增加的变化如图5所示。

从图中可见，在网络初始阶段时， EMRA算法和LEACH算法网络中节点平均剩余能量曲线不断减少，直到网络中开始出现节点死亡，网络中的平均节点剩余能量才突然变得缓慢且具有波动性，主要是因为网络中存活节点数开始不断减少，对网络中的剩余能量没有产生很大影响。EMRA算法中平均节点剩余能量曲线始终在LEACH算法上面，这进一步说明EMRA算法在减少网络节点能耗、平衡网络能耗以及延长网络生命周期上具有更优越的性能。

4 结 语

提出一种环形无线传感器网络能量平衡多跳路由算法EMRA，主要是在LEACH算法的基础上进行改进。首先在环形网络中的每一环中引入CM节点，然后又提出了对CH节点和CM节点选举的约束条件，最后在数据传输过程中考虑了CH节点到BS的跳数。仿真实验结果表明，EMRA算法在减少CH节点能耗、平衡网络能量以及延长网络生命周期上有明显的优势。