一种基于Agent自信度的簇间多跳路由协议*

简玉梅,张韩飞,高 飞,阮麟杰,张登珠,洪晴骏,赵旭东

(1.上海工程技术大学电子电气工程学院,上海 201602;2.江苏淮阴师范学院,江苏 淮阴 223300)

一种基于Agent自信度的簇间多跳路由协议*

简玉梅1*,张韩飞2,高 飞1,阮麟杰1,张登珠1,洪晴骏1,赵旭东1

(1.上海工程技术大学电子电气工程学院,上海 201602;2.江苏淮阴师范学院,江苏 淮阴 223300)

为了均衡无线传感器网络中的能量消耗问题,延长网络的生存时间,提出了一种基于Agent自信度的无线传感器网络多跳路由协议。该协议引入节点剩余能量、初始能量和节点的自信度来调节传感器节点随机数的大小。簇间通信时,综合考虑簇头节点的剩余能量,簇头节点距离Sink节点的距离,簇头节点的自信度3个因素,簇头节点和Sink节点之间使用单跳和多跳相结合的传输方式。每次重选簇头前都动态的修改节点的自信度。通过实验表明,相较于LEACH协议和ASCH协议,提出的协议能够很好的延长网络的寿命。

无线传感器网络;非均匀分簇;agent自信度

无线传感器网络由具有感知、处理和无线通信能力的传感器节点通过自组织方式形成网络。如何合理地利用传感器节点有限的能量延长网络寿命是传感器网络设计的主要问题。每个节点能够通过拓扑控制机制自动转发监测数据。目前,拓扑控制已经形成功率控制和睡眠调度两个主流研究方向。在睡眠调度中,分簇被证明为解决这一问题的有效机制,簇中节点分为簇头节点和簇成员节点。

文献[1]总结了一个有效簇算法需要同时具有的特点:①完全分布式的簇算法有利于节省网络能量和提高网络的可扩展性。②簇头尽量均匀分布,尽量减少算法本身的开销。③簇算法能够很好的处理节点能量异构问题。

近年来,诸多学者对无线传感器网络分簇算法进行了大量研究,提出很多分布式分簇算法的同时也取得了大量成果。

常见簇算法有固定分簇算法和非均匀分簇算法。固定分簇算法将网络分为大小相等的区域,各区域内的节点分别构成一个簇,每轮只从每个簇中重新选择簇头,不改变各个簇的组成[2]。非均匀分簇构造出大小不等的簇,建簇时节点可以考虑放弃距离最近的簇头而选择距离基站较近的簇头,从而构造出离基站越远就越大的非均匀簇[3]。

分簇数据融合算法LEACH(Low-Energy Adaptive Clustering Hierarchy)[4]是最具有代表性的一种层次路由协议,基于轮的概念,每轮分为簇的建立和数据通信阶段,簇头角色需要周期性地在整个网络中轮转,节点成为簇头的选择概率P恒定,每个传感器节点根据每轮产生的随机数与P计算出的阈值T(n)进行比较决定是否成为簇头。簇头广播自己成为簇头的消息,其他节点根据自身到簇头的通信代价选择一个簇头加入。在稳定阶段,各个簇成员在相应通信时隙内将数据发送至簇头,簇头融合数据后发往基站。目前很多层次路由协议都是基于LEACH协议进行的相关改进,EADEEG协议[1]使用邻居节点平均剩余能量与节点本身剩余能量的比值,作为竞争簇头的参数,减少簇形成过程中控制消息的开销,但存在“孤点”问题。文献[5]以节点的“度”作为节点竞争簇头辅助参数,解决了EADEEG协议中“孤点”问题。文献[6]在“度”的基础上,也考虑了剩余能量,距离,并构造了最小生成树来传输数据。文献[7]提出分布式分簇算法EEDC,选择高能量和低通信开销的节点作为簇头,在簇头预选时,假设不断增加节点成为候选节点的选择概率P来保证候选簇头的个数。文献[8]提出LEACH-T算法,基于节点分布密度、节点剩余能量和节点信号强度等,降低了节点的使用能耗,延长网络使用时间。文献[9]提出将簇头节点分为管理节点,融合节点,转发节点,通过优化结构来节省网络能耗。文献[10]结合LEACH和PEGASIS算法将网络内所有传感器节点以区域为单位集合成簇,形成簇头链提高网络生命期。文献[11]将单跳通信方式改成多跳通信方式,由簇头负责将邻居簇首的数据转发给Sink节点。文献[12]将节点分为主要簇头和次要簇头,以此减少簇头的重选时间。文献[13]提出了SENMA算法,将移动Agent引入了分簇算法中,簇成员不和簇通信,由MA完成通信功能。

上述文献中,LEACH不考虑簇头当前剩余能量,需要较为严格的时间同步,由于P恒定,容易使低剩余能量的节点被选为候选簇头,LEACH协议在簇形成阶段,每个簇头需要向全网广播,能量消耗大;EEDC中虽然考虑了能量且动态的修改P,但没有给出具体修改方法,使得算法的可验证性不强;ASCH算法[14]根据簇头节点所处的地理位置、剩余能量及簇内成员节点数目,动态决定是否需要在簇内产生助理簇头,但存在每个簇头都要计算一次是否需要产生动态助理簇头的阈值,带来了额外的开销。

针对以上算法的不足,本文引入带有Agent中的自信度,将每个节点都设想为一个Agent,构建基于Agent自信度的多跳路由协议EACMRA(An Embedded Agent Cluster Head Multi-hops Routing Algorithm)。

1 网络模型

设在二维坐标系中,在一个边长为L的正方形区域内随机均匀分布n个传感器节点,具有如下性质:①传感器网络为静态网络,节点部署后不再移动。每个节点有一个全局唯一的id标识。假设编号为1,2,…,n,唯一的汇聚节点Sink编号为0。②节点有相同的初始能量,其能量是有限且不可再充。③节点的无线发射功率可控,即节点可以根据接收者的距离来调整其发射功率。④网络节点都是全双工通信,能与基站直接通信。假设能量从节点i传输到节点j消耗的能量等同于从节点j传输到节点i消耗的能量。

2 EACMRA协议

与LEACH类似,EACMRA也按轮运行,每轮包括候选簇头的选择和最终簇头的确定。候选簇头的选择主要是判断生成的随机数和每个节点的T(n),当T(n)大于随机数,则被标识为候选簇头,但是由于在相近的范围内,可能满足条件的节点很多,所以为了保证簇头节点的数量,有必要在候选簇头的基础上在进行一次簇头选择。减少由于簇头间距太小,簇与簇间重叠范围大而增加的网络总能量损耗。以保证选择的簇头同时满足3个条件:簇头节点有足够的剩余能量来保证数据传递;簇头与簇内节点之间的距离在正常通信范围内;簇头和簇头节点之间距离不会太近,避免簇头的冗余。

2.1 候选簇头选择

每轮首先由网关发出分簇广播启动本轮簇头的选举,该信息包含网络中所有簇头剩余能量的平均值Eav,凡是小于平均值的节点都被标示为普通节点,该节点不能参与候选簇头的竞争。与LEACH协议相似,网络中所有非普通节点随机产生一个0～1之间的随机数,如果这个随机数小于阈值T(n),则成为候选簇头,如果大于T(n)则该节点暂时成为普通节点。

文献[15]提出承担中继任务,越靠近Sink的簇头能耗越大,簇头概率应与节点到Sink的距离成反比,将LEACH协议中的阈值函数乘以经验因子,通过改变阈值,使簇头概率随距离连续变化。

节点成功传输数据的影响因素很多,比如硬件质量,现场的环境,以及有无遮挡等,当所有外在条件都一样的情况下,多个节点可以成为候选簇头,但是有的节点转发数据的成功率低(转发10次,成功3次),有的节点转发数据成功率高(转发10次,成功6次),为了防止小范围内多个节点都能选为簇头导致簇太密集,簇头过多,本文结合文献[15],提出引入Agent的自信度,将自信度引入到T(n)的选择过程中,将节点的自信度作为选择因素,自信度主要用来区别节点转发数据成功的情况,通过自信度在多个都可以成为最终簇头的候选簇头中选出数据转发成功率高的节点,从而减少数据的重传,进而减少能量消耗。

自信度定义如下:定义节点Agentm作为簇头能成功转发数据tj的信心为自信度。自信度是反应一个节点能否顺利完成指定任务的信誉(信誉越高,说明节点越满足条件,越有能力在接下来的任务中顺利完成任务)[15]。

本文在LEACH协议中使用的T(n)公式上进行了改进,T(n)的公式如(1):

(1)

式中:p为簇头节点数目占总节点数目的比率,为了保证协议的性能,我们参考LEACH协议中的最优簇头数取值,r为当前的轮数,G表示当前网络中还没有成为正式簇头的节点集合。

T(n)=

(2)

本文定义各个节点初始自信度C(Agenti,tj)为1,自信度大于0表示节点有能力传输数据,簇头节点成功传输数据后自信度更新如公式(3)所示:

(3)

从式(2)、式(3)可以看出,自信度C和簇头传输数据的成功率成正比。自信度的变化主要用来区别数据的传输是否成功。比如节点A和节点B,两个节点的其他因素都一样(硬件质量,现场环境,有无遮挡,剩余能量,离Sink节点的距离等),在传输相同次数的数据时,节点A传输成功5次,节点B传输成功4次,传输相同次数,传输过程中消耗的能量一样,节点剩余能量一样。但两个节点的自信度将会不一样,节点A的自信度大于节点B,在选择候选簇头时,将选择节点A,这样可以避免节点传输失败带来的数据重传产生的能量消耗。

从式(2)、式(3)可以看出,在自信度和剩余能量一样的情况下,节点离Sink节点越远被选为簇头节点的概率就越低。在相同条件下,第r轮节点i自信度越大,剩余能量越多,离Sink节点越近的节点成为簇头的概率就越高,就可以生成离Sink节点越远簇越小,可以让靠近Sink节点的簇头为簇间的数据转发预留能量。

2.2 最终簇头确定

在这个阶段,只有候选簇头节点才能竞争成为最终的簇头节点。通过比较候选簇头节点一阶无线通信范围内所有邻居节点的自信度,选择自信度最大的节点作为最终簇头[16]。

每个候选簇头节点以通信半径Rc广播一条Node_Msg消息(包含节点自身ID,节点剩余能量,到基站的距离,自信度),同时也接收其他候选簇头节点的消息。候选簇头节点根据接收的消息创建一个候选簇头邻居列表。如果候选簇头的自信度不低于其任意一个邻居候选簇头节点的自信度,则该候选簇头为最终簇头,并以通信半径Rc广播自己为簇头节点的消息RealCH_Msg(包含ID,剩余能量,通信代价,自信度和簇头标识)。

2.3 簇间通信

簇间通信主要负责完成数据转发。

EACMRA协议采用与LEACH协议相同的一阶无线电模型,当发送的距离很近时(d≤d0),采用自由空间信道模型,当距离远时使用多路径衰减模型。当两个在经过距离d传输1-bit信息时,发送端能量消耗如式(4)。式(5)表示接收kbit数据的能量耗损,仅仅是由电路耗损引起的。式6为将接收的数据和自身的数据进行数据融合所需要的能耗。

(4)

节点接收能量消耗为:

ERx(l)=l·Eelec

(5)

数据融合能量消耗为:

EGx(l)=l·Egather

(6)

式中:l为数据长度,Eelec为节点发送1bit数据能耗,单位为J/bit。若传输距离小于等于阈值d0,采用自由空间模型。当传输距离大于d0,采用多路径衰减模型;εfs和εmp分别为自由空间模型和多径模型下的能量损耗,单位为J/(bit·m2),J/(bit·m4)d0。论文取距离阈值为d0=87.7m[16]。

两个传感器节点Vi和Vj之间的距离di,j为式(7):

(7)

为了简化分析问题,假设通信采用自由空间模型,并假设节点Vj接收到Vi数据后,直接将数据传送到Sink,则传送1比特的数据至Sink节点,Vi消耗的能量如式(8):E2-hop=ETx(l,d(Vi,Vj))+[ERx(l)+ETx(l,d(Vj,DS))]

= l·Eelec+l·εfs·d2(Vi,Vj)+l·Eelec+l·Eelec+

l·εfs·d2d2(Vj,DS)=3·l·Eelec+

l·εfs(d2(Vi,Vj)+d2(Vj,DS)

(8)

由式(8)可知,能耗的高低取决于Vi和Vj间的距离,以及Vj和Sink节点间的距离。

在EACMRA协议中,按照前面的步骤,当节点被选为簇头后,经过以下几步完成数据的融合转发。

①簇头节点进行数据发送时刻t设置

簇头节点进行数据发送的时刻t设置为与它和Sink的距离成反比,发送时隙到来后将簇内节点采集的数据和其他簇头转来的数据一起发送,距离Sink较远的簇头等待时间较短,距离Sink较近的节点等待时间长[15]。本文的等待时间T为:

T=15-sqrt(d)/100

式中:d为节点到Sink的距离,时间单位为s。15和100都可以取其他值,可以根据具体情况设置不同的等待时间。

②各节点开始与簇首进行通信,将所采集到的数据周期性的发送给簇首节点,还没有轮到自己的时间片时,进入休眠状态(节省能量)。簇头将发送来的数据进行融合,在等待了T时间后进行数据的转发。

③考虑到距离Sink较远的簇首直接将数据发送到基站消耗的能量较大,所以区域内的簇头和基站的通信采用多跳的数据传输方式,这样可以有效的节省能耗。簇首和基站采用单跳通信,则能量损耗将采用多径衰落模型。

当节点vi被选为簇头以后,以较高的发射功率在网络中广播包括其ID,节点剩余能量Ei(r)和到基站的距离di的消息。簇头vi收到其他簇头vj的消息时,计算两个簇头之间的距离d(vi,vj),如果d(vi,vj)小于传感器节点的通信半径R,则把节vj的信息保存在邻居节点集合N(vi)中。表1为簇头节点vi的邻居簇头节点路由信息表。

表1 簇头节点vi的邻居簇头节点vj的路由信息表

传感器节点vi需要将数据发送或者转发时,它的下一跳节点只能从其邻居节点集合中选择。如果d(vj,DS)大于通信半径R,则选择使用多跳路由将数据传送给Sink节点。

④建立多跳路径的过程如下:在邻居节点中选择权值最大的节点作为下一跳节点,如式(9)。

(9)

式中:Ei为节点被选为中继节点的剩余能量,d(vi,vj)为簇头节点M和中继节点N之间的距离,d(vj,DS)为中继节点到Sink节点的距离,(C(Agenti,tj))为节点成为簇头节点的自信度。由cost计算公式可知,当距离和剩余能量相同时,自信度越大越容易成为下一跳节点。当节点到Sink节点的距离小于通信半径或者邻居节点集合中没有任何节点时,则节点直接将数据发送到Sink节点。

2.4 EACMRA算法伪代码

选择候选簇头和确定最终簇头的伪代码如下:

Ifrandom

Elseifrandom>T(n)//若随机数大于T(n),节点为普通节点

Ifstate==Vi//标记当前候选簇头的自信度

C[]theaverageconfidence//标识各节点的自信度

BroadcastComepete_Msg//广播信息

//邻居集合里面选择自信度大的节点作为最终的簇头节点

For(j=0;j

ifC[j]>C(Vi)//选择自信度最小的节点为下一跳节点

final_CH=Vj

elsefinal_CH=Vi

BroadcastRealCH_Msg//广播簇头信息

3 仿真实验及性能分析

本文使用Matlab作为模拟实验平台,对EACMRA算法进行仿真,分别从网络生存周期和网络能量消耗方面来评价EACMRA算法的性能。假设在100m×100m的网络中随机分布100个节点,Sink节点位置为(50,150)。由文献[8]仿真结果可知,当传感器节点为100,在100m×100m的区域里对应簇头个数为5时,每轮消耗能量最少,网络生命周期最长。所以本算法中规定簇头选择概率阈值为P1为0.05。定义各个节点的初始自信度为1,每个节点拥有相同的初始能量,仿真过程中的参数配置如表2。

表2 仿真参数设置

本文在相同场景下运行LEACH、ASCH和EACMRA,通过改进协议以平衡节点能量消耗、延长网络存活时间及提高整体网络能量效率为主要目标。在模拟环境中随机分布的100个节点如图1所示。

图1 随机分布节点

根据式(2)选出候选簇头,通过式(8)确定出最后的簇头节点,成功传输数据后相应的增加该节点的自信度。

3.1 存活节点比较

图2(a)为LEACH算法运行一段时间后节点的状态图,红色代表已经死亡的节点,o为正常能量节点,十字表示高能量节点。图2(b)为EACMRA算法运行1 500轮后节点的存活情况。从图中可以看出,LEACH在运行了1 500轮之后存活节点数很少,而EACMRA算法中存活节点数很多。

图2 节点的状态图

出现此情况主要是因为EACMRA算法在选择簇头节点时通过分步操作,先选出候选簇头,在候选簇头中选择出自信度大的节点作为最终簇头,此算法中添加了节点的自信度,保证了簇头节点的传输成功率,减少了在LEACH算法中因为随机产生簇头可能导致的数据重传的概率,进而减少了节点间的通信开销,延长了节点的寿命。

图3为网络剩余存活节点情况。LEACH在第943轮时出现死亡节点,ASCH协议在950轮出现死亡节点,相同条件下EACMRA算法死亡节点出现在第1 533轮,EACMRA算法从节点死亡到全部死亡的时间都往后延续了,而LEACH和ASCH算法节点死亡发生比较集中,这主要是因为在簇头选择时容易出现簇头节点集中在网络某一区域的现象,导致该区域的节点在很短的时间内能耗过高,逐渐死亡,后面选择出来的簇头将会出现远离Sink节点的节点作为簇头,这样在传输过程中能耗大,节点死亡快。改进协议EACMRA优于LEACH协议和ASCH协议的地方在于在簇头选择过程中加入了其他元素,避免了簇头节点集中的情况。

图3 存活节点数示意图

图4 网络剩余能量统计图

3.2 剩余能量比较

图4为网络的剩余能量示意图。虽然引入Agent的自信度,在每次计算通信代价时会带来了一定量的计算开销,但EACMRA算法节点总能量消耗速率低于LEACH算法和ASCH算法。EACMRA算法优势在于选择候选簇头时,随时更新节点的自信度,缓解了LEACH在选择候选簇头时的盲目性,减少了由于随机选择的簇头节点最终不能成功传输数据导致的数据重传,和二次选择簇头节点的通信开销。由于数据传输失败导致的簇头节点再次选择,以及数据传输带来的能量消耗将远远大于每次簇头节点进行自身自信度修改的通信代价。

图4中,LEACH算法和ASCH算法在1 500轮之前能量消耗情况基本相同,而EACMRA算法剩余能量明显高,这主要是由于EACMRA算法中减少了簇头节点的重新选择,进而减少能量消耗。

文献[12]的CHCI算法和EACMRA算法有着类似的思想,CHCI算法在选择主要簇头后,在每个簇里再进行一次次要簇头选择,以此来降低多次选择簇头的能耗,但是次要簇头的选择能耗远远大于节点自信度的修改所需要的能耗,在相同的情况下,EACMRA算法更加节约能耗,能有效的延长网络生存时间。

EACMRA算法和CMRAOL[16]算法在设计上有相同之处,EACMRA算法在CMRAOL算法的基础上添加了节点的自信度,主要是用来避免当出现相同的T(n)时,如何选择具体某个节点作为簇头节点,EACMRA算法较CMRAOL算法在每一次簇头选择的过程中增加的能耗为上一次簇头节点自信度的动态修改,而由此减少在CMRAOL算法中由于簇头节点传输失误带来的二次簇头选择所产生的能耗,增加的能耗远远低于二次簇头选择所产生的能耗。

4 结束语

本文针对以往分簇路由协议的不足,在无线传感器网络中提出一种能量高效的EACMRA分簇算法,引入了Agent的心智系数,并详细阐述了候选簇头和最终簇头的确定过程。在簇建立阶段,算法赋予每个节点相同的自信度,根据每个节点参与的情况动态修改自信度,自信度在反过来参与到每次簇头的重新选择过程。在候选簇头节点中选择自信度大的节点作为最终簇头节点,通过在MATLAB下进行仿真测试,文章分析了EACMRA算法中各个参数的作用及其对算法整体性能的影响。理论分析和仿真实验表明EACMRA较LEACH协议和ASCH协议延长了网络寿命,减少了网络中能量的消耗,更好地保证监测覆盖度。

[1] 刘明,曹建农,陈贵海,等. EADEEG:能量感知的无线传感器网络数据收集协议[J]. 软件学报,2007,18(5):1092-1109.

[2] Akl R,Sawant U. Grid-Based Coordinated Routing in Wireless Sensor Networks//Procof the Consumer Communications and Networking Conference[C]//Piscataway,NJ:IEEE,2007:860-864.

[3] 彭铎,黎锁平,杨喜娟. 一种能量高校的无线案传感器网络非均匀分簇路由协议[J]. 传感技术学报,2014,27(12):1687-1691.

[4] Heinzelman W,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks[C]//Proofs the 33rd Conf on System Sciences. Piscataway. NJ:IEEE,2000:3005-3014.

[5] 周新莲,吴敏,徐建波. BPEC_无线传感器网络中一种能量感知的分布式分簇算法[J]. 计算机研究与发展,2009:46(5):723-730.

[6] 张文梅,廖福保. 改进的无线传感器网络非均匀分簇路由算法[J]. 传感技术学报,2015,28(5):739-743.

[7] 齐迎迎,禹继国,王楠楠. 无线传感器网络的节能分布式分簇算法[J]. 计算机工程,2011:37(3):83-86.

[8] 李悦,孙力娟,王汝传,等. 一种改进的无线传感器网络LEACH算法[J]. 计算机研究与发展,2011:48(z2):131-134.

[9] 陈东海,李长庚. 基于簇头功能分化的无线传感器网络成簇算法[J]. 传感技术学报,2015,28(2):244-248.

[10] 常铁原,王彤,朱桂峰. 一种改进的簇头成链路由协议[J]. 计算机工程,2012:2(3):85-87.

[11] Sun Yanqing,Peng Jian,Liu Tang,et al. Uneven Clustering Routing Protocol Based on Dynamic Partition for Wireless Sensor Network[J]. Journal on Communication,2014,35(1):198-206.

[12] 康琳,董增寿. 基于簇头分级的改进的非均匀分簇算法[J]. 传感技术学报,2015,28(12):1841-1845.

[13] 程文娟,穆自立,唐昊. 基于带Mobile Agent的无线传感器网络的分簇算法[J]. 计算机研究与发展,2010,47(Suppl):88-91.

[14] 龙际珍,陈沅涛,邓冬梅. 基于LEACH协议的助理簇头分簇算法[J]. 计算机工程,2011,37(7):103-015.

[15] 李建洲,王海涛,陶安. 一种能耗均衡的WSN分簇路由协议[J]. 传感技术学报,2013,26(3):396-401.

[16] 陈炳才,么华卓,杨明川,等. 一种基于LEACH协议改进的簇间多跳路由协议[J]. 传感技术学报,2014,27(3):373-377.

An Inter-Cluster Multi-Hop Routing Protocol Based on the Confidence of Agen*

JIANYumei1*,ZHANGHanfei2,GAOFei1,RUANLinjie1,ZHANGDengzhu1,HONGQingjun1,ZHAOXudong1

(1.School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China;2.Huaiyin Normal University,Huaiyin Jiangsu 223300,China)

In order to balance energy consumption of wireless sensor networks,and prolong survival time of the networks,presents an Inter-Cluster Multi-Hop Routing Protocol based on the confidence of Agent. This paper introduces residual energy,initial energy of the sensor nodes and confidence as three important components to adjusts the size of the sensor nodes random numbers. In inter-cluster communication process,cluster head nodes communicate with Sink node by single-hop and multi-hop,which considers the residual energy of cluster head nodes,the distance between cluster head node and Sink node,the confidence of cluster head node. Before re-elected cluster head,it dynamically modified the confidence. The result of experiment shows that,compared to LEACH protocol and ASCH protocol,the new protocol processed can prolong the life wireless sensor network.

Wireless Sensor Network(WSN);non-uniform clustering;the confidence of Agent

简玉梅(1987-),女,硕士,实验师,研究方向为无线传感器网络,智能运算,jianyumei0628@126.com;张韩飞(1986-),男,硕士,中级,研究方向为物联网技术,无线传感器网络,zhanghanfei2006@163.com。

项目来源:上海市教育委员会科研创新项目重点项目(14ZZ156)

2016-03-17 修改日期:2016-08-29

TP393

A

1004-1699(2017)01-0126-07

C:7230

10.3969/j.issn.1004-1699.2017.01.023