基于作用力模型的传感器网络簇型协议*
2015-04-01何杏宇杨桂松周亦敏
何杏宇,杨桂松,周亦敏
(1.上海理工大学 实验室管理与服务中心,上海200093;2.上海理工大学 光电信息与计算机工程学院,上海200093)
0 引 言
无线传感器节点的能量限制一直以来是无线传感器网络应用中的瓶颈问题。为了避免因网络中能量消耗不均而导致的网络不稳定,一些层次型协议相继提出。LEACH[1]算法是较早提出的层次型算法,该算法以循环的方式随机选择簇头节点,使得网络中节点的能量均衡。随后,研究人员对LEACH 算法进行了各种改进,其中,HEED[2]算法要求在节点选取簇头时考虑其剩余能量。同样,文献[3,4]也基于节点剩余能量对LEACH 算法提出了改进。而文献[5,6]提出了基于节点密度的簇型算法,进一步提高网络能量均衡。文献[7,8]则对近年来关于LEACH 的改进算法进行了总结和比较。然而,这些算法中均未考虑到簇头节点和簇成员之间的通信代价均衡问题,以及是否存在“孤立簇头”的问题。
为此,本文提出了一种基于作用力模型的移动簇型协议,该算法基于节点剩余能量和节点密度进行轮换簇头选举,簇头节点能够根据基于簇成员剩余能量和距离的作用力模型进行自适应移动,以均衡簇头和簇成员之间的通信代价,另外,本文还提出了基于节点剩余能量的中继节点选举算法,以在簇头之间形成可连通的且有利于均衡的主干路径。
1 网络模型
本文定义的网络模型为:1)网络中的节点结构和初始能量相同,且能量不可补给,在部署后具有可移动性和获知其位置信息的能力;2)采用文献[9]中的无线通信能量计算模型。
2 基于作用力模型的移动簇型协议
本协议包括簇的建立阶段和主干路径建立阶段。
2.1 簇的建立阶段
2.1.1 簇头选举
本文提出基于节点邻居密度和节点剩余能量的簇头选举算法:每个节点产生[0,1]之间的一个随机数,若随机数小于阈值T(n),则该节点被选为簇头节点,为了让剩余能量较多的节点成为簇头,且加大节点密集区域中簇头节点的数量,T(n)的计算公式为
其中,Eresidual为节点的剩余能量,Eaverage为节点的邻居节点的平均剩余能量,如果节点的剩余能量大于邻居节点的平均能量则成为簇头节点的概率增大,反之,减小;1/p 为网络节点中簇头比例为p 时每个簇包含的节点数量,Nneigbor为邻居节点数量,N 为网络的节点总数量,当邻居节点数量比1/p 多时,该区域簇头节点数量增加,反之,减少。
2.1.2 簇头节点的自适应移动
在簇头选举后和簇头节点进行自适应移动之前,应先获取簇头节点移向的位置。为此,本文提出一个与距离和剩余能量相关的作用力模型,该模型设簇头节点最终移向的位置为目标点,假定q 个簇成员节点将在与簇头节点连线方向上分别产生q 个牵引力,牵引力大小与其剩余能量和其与簇头之间的距离相关,第i 个簇成员产生的牵引力fi的计算公式为
其中,α,β 为权重系数,Li为第i 个簇成员节点与簇头节点之间的距离,Ei为第i 个簇成员的剩余能量。这q 个簇成员对簇头分别产生q 个牵引力,距离簇头越远的节点产生的牵引力越大,反之,越小;剩余能量越小的节点产生的牵引力越大,反之,越小。该模型由势能最小原理(一个力学系统处于平衡状态时势能最小)要求这q 个簇成员在目标点位置所产生的多个牵引力的合力为0。
下面将以q=3 为例对利用作用力模型对目标点的位置求解进行简化说明。如图1 所示,原xy 坐标系以簇头为原点,其坐标为(X,Y)=(0,0)簇头节点接收到的3 个簇成员节点在原xy 坐标系中的坐标分别为(X1,Y1),(X2,Y2)和(X3,T3),设目标点的坐标为(X0,Y0)。
图1 簇成员和目标点的位置关系Fig 1 Location relationship between cluster members and target point
首先,将簇头节点和三个簇成员节点的坐标转换至以目标点为原点的(X',Y')坐标系中。转换后的目标点坐标为(X'0,Y'0),(X'0,Y'0)=((X0-X0),(Y0-Y0))=(0,0),而三个簇成员节点的坐标的计算公式分别为
然后,根据三个簇成员和目标点的位置关系和剩余能量可以获得以目标点为原点的作用力模型如图2 所示:三个簇成员产生的牵引力矢量坐标分别为
图2 作用力模型Fig 2 Force model
由式(4)可推导出
由于在目标点位置三个簇成员节点产生的三个牵引力f1,f2,f3对应的矢量和为0,亦即,X″1+X″2+X″3=0,Y″1+Y″2+Y″3=0,则可以推算出
根据式(5),进而可以推算出
当q=3 时,目标点的计算公式为
对上述模型进行推广,当簇头节点接收到q 个簇成员的节点的坐标信息分别为(Xi,Yi),i=1 ~q 时,则此时目标点的坐标计算公式为
2.2 主干路径建立阶段
在簇头自适应移动后,为了在簇头节点之间建立全连通的主干路径,本文提出如图3 所示的基于通信半径和剩余能量的中继节点选举算法。当存在“孤立簇头”时,便可按照图3 所示算法进行中继节点选举。
图3 中继节点选举算法流程图Fig 3 Flow chart of relay node election algorithm
设定V 为判断簇成员成为中继节点的可能性大小的参数,V 的计算公式为
其中,θ 和μ 为权重系数,Eresidual为簇成员的剩余能量大小,L1为簇成员到发起中继请求的簇头的距离,L2为簇成员到对接簇头的距离。由式(11)可知,当簇成员的剩余能量越高,其成为中继节点的可能性越高,反之,越低;簇成员到中继请求节点和对接簇头的距离和越小,其成为中继节点的可能性越高,反之,越低。
3 仿真与实验
本文使用NS2 平台对文献[5]所提出的基于节点剩余能量的LEACH—E 协议、文献[6]所提出的基于节点密度的LEACH—D 协议以及本文提出的算法分别进行了仿真,并对这三种协议的仿真结果进行了对比分析。
3.1 实验参数设置
本文的仿真场景为400 个节点随机部署在一个200 m×200 m 的正方形区域内,其Sink 节点位于正方形的中心。仿真参数如表1 所示。
表1 仿真参数Tab 1 Simulation parameters
3.2 实验结果分析
由图4 可知,LEACH—E 和LEACH—D 协议都有具有最高的能耗方差且波动较大,从而反映出较大的网络能耗不均衡性。相较之下,本文提出的协议有效地降低了方差,呈现出较好的能耗均衡状况。
图4 节点能量消耗方差Fig 4 Energy consumption variance of nodes
由图5 可知,LEACH—E 由于考虑到节点的剩余能量,在网络运行初期节点死亡数量比LEACH—D 协议少,但随着网络的运行时间推移,反映出没有考虑节点密度的缺陷,节点死亡率反而比LEACH—D 协议高;相较之下,本文提出的协议兼顾了节点剩余能量和节点密度,并采用了簇头自适应移动策略,使得网络中节点的能耗均衡性进一步提高,节点的使用寿命趋于一致,大部分节点都坚持到网络剩余周期的末期才死亡。
4 结 论
图5 节点存活的个数Fig 5 Number of alive nodes
本文提出的基于作用力模型的移动簇型协议在进行簇头选举时提高了剩余能量大的节点成为簇头的概率,同时增加了节点密度较大区域簇头节点的个数,该算法允许簇头节点基于簇成员剩余能量和距离的牵引力作用下进行自适应移动,均衡了簇头和簇成员之间的通信代价。同时,本文提出的中继节点选举算法,实现了簇头节点之间的全连通。实验结果证明:本文提出的协议能够有效地均衡网络能耗,显著地延长网络的生命周期。
[1] Heinzelan W R,Chandrakasan A,Balakrishnan H.An application-specific protocol architecture for wireless micro sensor networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.
[2] Youni O,Fahmy S.HEED:A hybrid,energy-efficient,distributed clustering approach for Ad Hoc sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(4):366-379.
[3] 龚本灿,蒋廷耀,汪祥莉.一种基于剩余能量的无线传感器网络分簇协议[J].计算机工程与应用,2008,44(8):31-33.
[4] Peng D,Zhang Q.An energy efficient cluster-routing protocol for wireless sensor networks[C]∥International Conference on Computer Design and Applications,Qinghuangdao:IEEE,2010:530-533.
[5] 乔俊峰,刘三阳,曹祥宇.无线传感器网络中基于节点密度的簇算法[J].计算机科学,2009,36(12):46-49.
[6] 路成杰,蒋海峰.一种基于节点密度的无线传感器网络协议[J].传感器与微系统,2014,33(9):114-116.
[7] Li Y,Zhang A,Liang Y.Improvement of leach protocol for wireless sensor networks[C]∥The third International Conference on Instrumentation,Measurement,Computer,Communication and Control,Shenyang:IEEE,2013:322-326.
[8] Keert N,Anand G.Improved cluster routing protocol for wireless sensor networks through simplification[C]∥18th Annual International Conference on Advanced Computing and Communications,Bangalore:IEEE,2012:1-3.
[9] Su I,Tsai C,Sung W.Area temperature system monitoring and computing based on adaptive fuzzy logic in wireless sensor networks[J].Applied Soft Computing,2012,12(5):1532-1541.