基于改进GPSR的WSN多跳概率算法

2022-04-26龚瑞昆王彦植陈旭东张仲

华北理工大学学报(自然科学版) 2022年2期

龚瑞昆，王彦植，陈旭东，张仲

(1. 华北理工大学电气学院，河北唐山 063210；2. 河北省安装工程有限公司第二分公司，河北唐山 063000)

引言

在环境监测领域尤其是湿地环境下存在无法布线问题，许多设备需要依靠电池并通过无线节点传输数据。网络生存时间的长短影响着环境监测的效率。根据调查，能量洞内的节点电量消耗较快，但其余节点仍剩余大量电量，这导致外侧的节点无法将数据传送至sink节点，造成整个监测系统的瘫痪。因此，如何利用现有的计算机技术延长网络的生存时间，减少人力物力的浪费，成为许多研究人员的研究热点。

近年来，许多专家对此提出了不同的策略。文献[1]提出一种和当前电量挂钩的转发概率参数。电量越低，充当转发点的概率越低。该算法具有高动态性，可以很好地适应转发的及时性，但当电量过低时，转发概率过低，无疑降低了系统效率。且将其他节点的电量当作参考量，又要求实时查看其他节点的电量，查看过程中又浪费了更多电量。文献[2]提出一种将转发任务强制安排给剩余电量多的节点的方法。此方法照顾了电量均衡，却没有考虑整体耗电，整体耗电量反而增加了，这不利于网络寿命提高。文献[3-5]均提出改进GPSR算法，但是其条件函数复杂，需要频繁维护邻居列表，增加了能耗。还有文献提出了新的节点部署策略[7-9]，但这些布点方法较为复杂，现实情况下难以实施。

针对上述不足，研究提出了一种基于改进多跳模型的WSN能量均衡数据传输方法，该方法在解决节点能耗不均问题上，能够取得较好效果，相较于其他算法，其适用简单，稳定性强。

1节点多跳传输模型

假设节点有2种能耗不同的发射半径，其中r1半径能耗为c1、r2半径能耗为c2,且r2=2r1。接收1 bt数据能耗记为c0。节点间距离均为r1。sink节点放置在终点，不考虑电量。节点自身产生的数据量均为k bt。节点分别以Pi概率和1-Pi概率向距离r1和r2的节点发送数据。图1所示为节点跳跃传输模型。

图1 节点跳跃传输模型

如图1所示，假设在单位时间内，第i个节点以r1或r2传送的数据量为Gi或Hi，第i个节点接收的数据量为Fi。模型的初始条件为：F0=nk，Fn=0,Fn-1=Gn,H1=0。节点i自身产生的流量，此流量也将通过2种传送方式传送。依据流量守恒定律列式：

Fi=Gi+1+Hi+2

(1)

Fi+k=Gi+Hi

(2)

消去Hi后，由累加法得：

Gi=Fi+Fi-1+(i-n)k

(3)

代入选择概率Pi：

Fi+k=PiGi+(1-Pi)Hi

(4)

设节点i的能耗为Ei则有：

Ei=C0Fi+C1Gi+C2Hi

(5)

消去Hi：

Ei=(C0+C2)Fi+(C1-C2)Gi+C2k

(6)

记(C0+C2)为A, (C1-C2)为B，C2k为C。当全网的能耗均衡时，令Ei=Ei-1得：

(7)

(1+t)Δi+Δi-1=-k

(8)

消去常数k：

(1+t)Δi-tΔi-tΔi-1-Δi-2=0

(9)

令E1=En则：

(10)

-Δn=m(Δ1+nk)+k

(11)

由母函数法得：

(12)

(13)

Gi=Fi+Fi-1+(i-n)k

(14)

(15)

(16)

分析转发概率Pi的表达式，Pi只与网络规模n、特殊参数α和节点编号i相关，与节点数据产生量k无关。因此，只要确定n和α就可以确定节点的转发概率。

选取应用于环境监测的无线传输模块，通过查阅通信模块的数据手册可得，α的取值在2.8到10之间。为了研究方便，分别设立3组取值为3、6、9，研究n=10时α和Pi的关系。表1所示为Pi与α的关系。

表1 Pi与α的关系

表1的数据显示，当α取不同值时Pi随i变化时，由于概率的取值非负，故舍去小于0的部分。根据表1可以看出，α较大的通信模块，更有利于实现能量均衡。设n0为最大连续节点数。表1中的n0分别为5、8、10。当n

2改进GPSR算法

2.1 原始GPSR算法

GPSR算法由贪婪转发与边界转发组合而成。节点根据相对位置确定转发策略并周期性广播hello数据包来更新邻居路由表，确定相邻节点位置。首先通过贪婪算法转发数据，选择更接近终点的邻居节点。否则采用边界转发算法，把数据传送给网络平面图的临近节点，直到出现更接近终点的邻居节点。GPSR流程图如图2所示。GPSR使用贪婪算法达成局部最优，不需要在节点中构建并更新全部路由列表，路由开销小。

图2 GPSR协议流程图

2.2 改进GPSR算法

GPSR算法优化效果好，但在贪婪转发模式下，节点只与距离最近的节点通信，这样会在sink附近形成多个热点节点，热点节点负担增加会提前耗尽能量，进而产生能量洞，缩短网络生存时间。因此，对GPSR算法进行改良，增加能量均值函数，用能量均值限制GPSR选择能量较低的节点。

综上所述，改进GPSR多跳算法的基本思想是：前期采用改进GPSR算法对监测区域进行全局搜索，寻找全局最优解；后期通过多跳算法进行优化，通过式(16)计算跳跃概率，节点按概率选择单跳或多跳。2种算法优势结合，共同完成对节点路径的选择。

算法主要步骤如下：

(1)查找邻居列表，如列表中包含sink，则直接传递给sink，否则转到步骤(2)；

(2)记录当前节点到sink的距离，将小于此距离的节点纳入可选列表里；

(3)计算可选列表里的节点能量均值，剔除的节点；

(4)按照贪婪转发与周边转发选择下一跳节点。生成改进GPSR路径；

(5)按照多跳算法在GPSR已生成路径上根据式(16)计算多跳概率。生成多跳路径。

3实验结果与讨论

为了验证不同算法对网络能量消耗的均衡结果，采用NS2软件进行仿真实验。网络区域为1 000 mm×1 000 mm的正方形，在区域内随机分布200个节点，sink节点坐标设置为(0，500)所有节点开始携带的能量为2 J，sink节点无电量限制，节点通信半径可调，最大通信半径为300 m。Q设置为0.8。

3.1 平均能耗的比较

图3所示为节点平均能耗变化图。通过图3可以比较出LEACH算法、PEGASIS算法和改进GPSR多跳算法对节点能耗的优化效果。开始时不同算法在能量充足的条件下均找到了最优解,故起始阶段平均能耗相同。随后热点节点电量下降，改进GPSR多跳算法开始控制热点节点电量，其平均能耗少于另外2种算法。

图3 平均能耗随仿真时间的变化

3.2 存活节点数量的比较

从图4可以看出,仿真前期,各算法中节点能量均未耗尽,当40 s后,LEACH由于平衡性不佳,率先出现死亡节点。60 s后,PEGASIS算法开始出现死亡节点。改进GPSR多跳算法在第70 s后,出现死亡节点。并相继产生死亡节点。在180 s迭代后,所有算法均加快产生死亡节点,但改进GPSR多跳算法存活节点数量依旧多于其他算法。

图4 存活节点数随仿真时间的变化

从图3和图4中可以看出，相比于GPSR多跳算法,常见的无线自组网算法对节点能耗均衡的平衡效果较差。常用的WSN算法响应时间慢，更新邻居列表频繁。PEGASIS算法平均能耗较高，LEACH算法维护路由列表开销大。而采用改进GPSR多跳算法对延长网络生存时间的效果就比较好，反应速度快，邻居列表维护次数少。