基于灰色预测与演化博弈铀尾矿库无线传感网络路由算法*

余修武,夏 凡,周利兴,2,张 枫,2,刘 永,2,3,戴 李,姜 慧

(1.南华大学资源环境与安全工程学院,湖南 衡阳 421001;2.湖南省铀尾矿库退役治理工程技术研究中心,湖南 衡阳 421001;3.铀矿冶放射性控制技术湖南省工程研究中心,湖南 衡阳 421001)

由于铀尾矿库储存废渣中的核素具有放射性、易迁移、人工监测困难等特殊性,相较于传统有线布置,无线传感网络WSN(Wireless Sensor Network)监测一定程度上避免了对人体的辐照和线路布设维修费用,且具有自组织性,能够对放射性核素的迁移进行实时跟踪,具备明显优势[1-3]。但传感器节点大多采用电池供电且电源更换困难,其能耗问题一直备受关注。研究者就降低并均衡网络能耗问题提出了多种无线路由协议[4-7]。

分簇路由可以充分利用拓扑结构特征,提高网络可靠性并节约能耗,在无线传感网络中被广泛使用。文献[8]提出了能量均衡前行路由算法EBFA(Energy Balanced Forwarding Algorithms)引入社会福利函数预先评估数据转发路径上节点间的能量均衡程度,延长了网络的生存周期。文献[9]所提出的算法在选择中继簇头时综合考虑了邻近簇头相对自身的距离和方向,使无线传感器网络第1个节点的死亡时间明显延后。文献[10]提出基于混合压缩感知理论CS(Compressed Sensing)的WSN六边形格状优化分簇路由算法,减少了数据传输次数。以上分簇路由协议有一定优越性,但大多根据能量剩余先确定簇头,再通过一定的成簇机制招募簇成员,忽视了簇成员的剩余能量,不利于均衡网络负载。

文献[11]提出协作多输入多输出算法CMIMO(Cooperative Multi Input Multi Output),通过主簇头和从簇头对网络的管理达到节约能耗的目的。在此基础上,文献[12]提出了一种基于演化博弈的分簇协作路由算法CCREG(Cluster Cooperative Routing Algorithm Based on Evolutionary Game),先根据虚节点剩余能量确定簇头,参与演化博弈的节点经过时间的推移,有唯一确定的簇头与之联盟,在均衡网络负载上取得了一定成效。但其考虑了簇头节点剩余能量和区域内平均链路能耗,而没有考虑簇成员节点的信道质量,造成信道质量好的节点射频能量的浪费。因此本文针对铀尾矿库监测环境提出一种多簇头选择的路由算法MHSR(Multi-Host Selecting Routing algorithm)。一是通过Sink节点的合理布置,实现对核素迁移频繁区域的重点监测,确保监测的可靠性。二是在均衡网络负载的基础上,根据信道质量合理进行信道功率分配,减少射频能耗,延长网络寿命。分别考虑节点数目和监测区域大小的影响,将MHSR与CMIMO和CCREG对比进行仿真实验,结果显示MHSR网络生存周期较这两种算法均有效延长。

图1 坝体监测模型示意图

1 铀尾矿库监测模型

铀尾矿库监测面积大,放射性核素易随水体发生迁移,伴随降水延坝体下渗。因此必须对坝体结构薄弱处等放射性核素迁移频繁的区域加强监测,在关键区域布设Sink节点,加强Sink附近节点的布设密度。建立监测模型如图1所示。

监测区域可视为一带状环形铀尾矿坝的坝面,坝体坡面为倾斜平面,由平整的石块砌成。图1中箭头表示可能的数据传输途径,簇头将各成员节点的监测数据进行汇聚、去冗,并以协作传输方式汇总到Sink节点。Sink节点附近的节点布设密度高于其他区域。

2 确定Sink节点位置

(1)

则以生成序列x(1)={x1(1),x2(1),…,xn(1)}为基础建立灰色的生成模型,如式(2)所示。

(2)

即一阶灰色微分方程,记为GM(1,1),式中a,u为待辨识参数。

设参数向量a=[au]T,yn=[x2(0),x3(0),…,xn(0)]T和矩阵

(3)

则由式(4)求得最小二乘解:

a=(BTB)-1BTyn

(4)

时间响应方程,即式(2)的解:

(5)

离散响应方程:

(6)

(7)

实践操作中将收集监测到的历史数据作为预测数据序列,代入一阶灰色微分方程GM(1,1),即可得到放射性迁移频繁区域,并在该区域布设Sink节点。

3 多簇头协作路由模型

3.1 确定簇头集

为保证Sink附近节点密度,选取备选簇头时,节点i随机产生0～1之间的数,若此数小于阈值Ti,该节点就成为备选簇头;如果区域内没有小于阈值的节点,则优先选择接近阈值的节点作为簇头节点。选择备选簇头后再根据动态异构网络的演化结果确定最终成簇方式。根据铀尾矿库实际监测需要可以初步预测簇头的需要量,阈值Ti按下式计算:

(8)

式中:p表示簇头占全网总节点数的百分比,r表示当前簇头竞选轮数;H表示最近1/p轮没有担任簇头的节点集合;Es表示节点的剩余能量;E0表示传感器节点的初始能量;ds表示簇头到Sink节点的距离;d0表示通信距离阈值;mod( )为求余函数。

假设簇头集合为C={C1,C2,C3,…,CNhost}。簇头节点保留邻居表信息,此外由动态路由协议的要求,每个节点要时刻更新路由表信息,如果路由表中某项与接收到的新信息对应同一节点,说明该项已经陈旧,则用新信息覆盖该项;如果找不到对应的项,则将接受到的新信息加入路由表内。由于路由表容量有限,在路由表接近饱和时覆盖最没有价值的路由表项,即距离更新时间最长的陈旧信息。

3.2 簇内通讯策略

由图1所示,铀尾矿库监测区域可视为平整坝面,数据传输可使用一般自由空间传播模型。当信号强度大于节点的接收门限Pth时,才能够正确解码,保证接收节点正确接收数据时发送节点所需的最小功率为

(9)

式中:Gt为发送端的天线增益;Gr为接收端的天线增益;λ为电磁波波长;D为发送端天线和接收端天线之间的距离;L为系统损耗因子,L≥1。考虑信号的衰减特性,通常将Pmin乘以调整参数ξ(ξ≥1),以保证信号传输的可靠性。

则发送节点的最优发送功率为

Popt=ξPmin

(10)

为确保信号传输,取簇头以最优发送功率覆盖的通信区域为实际通讯区域,如图2所示。以簇头C1,C2,C3为例,通讯区域将空间划分为7部分,其中有区域重叠的有z1、z2、z3、z4。

图2 通信区域示意图

若将同一通讯区域内有限个节点作为一个群体,则这些群体的簇成员可以至少参与两个簇的组成,例如在z1内部任意节点可以与3个簇头联盟,基于复制动态,节点通讯策略会随时间不断演化,如果某一节点观测到的收益低于同一簇内节点的平均收益,则该节点放弃这一簇头,选择与其他簇头联盟,直到节点收益不再增加为止。假设节点具备有限理性,通过有限次演化博弈,最终能够达到演化平衡,群体收益达到最大。

对于z5、z6、z7内的任意节点,他们只能选择能够成簇的唯一簇头进行联盟,不需要进行收益评判和联盟选择即可成簇。

3.2.1 收益评判

用动态异构网络选择的收益函数计算重叠区域内任意节点i与每个簇头结成联盟的收益。复制动态过程如下:

单个节点在总可选择策略数S中选择某一策略s,Ns记为选择策略s的节点数,节点总数为N。

(11)

成员节点选择策略s的份额为is=Ns/N-Nhost。某一时刻群体的状态可以记为矢量i=[i1,i2,i3,…,iS]。在某一时刻t,复制动态可以定义成:

(12)

根据数学期望的求解办法:

(13)

无线异构网络的演化博弈问题描述如下:

(14)

PS(NS)=fNS=fiSN

(15)

假设所有选择与簇C联盟的节点被分配到的带宽都相同,区域z内任一节点网络效用函数U(N)可定义如下:

(16)

选择与某一簇头C联盟的成员节点数Ns等于区域z内的节点总数乘以选择与簇头C联盟的份额,ϖine为簇内通信修正量,其值为常数。A为簇头C的通信区域(即图2中的圆形区域),见式(17)。同理可求得其他簇内的节点总数。

(17)

不同区域内与同一个簇头联盟的收益值在达到演化平衡时都相等。以图2为例,各区域内与C1联盟的收益都相等。

(18)

由此可求解各重叠区域的效用值μ。

3.2.2 信道评级和功率分配

取演化平衡时的成簇策略,对重叠区域内节点两个或以上可能的信道进行评级,确定信道质量。

由节点路由表信息可获取节点与其上一节点之间的路由状态,通过链路质量指示LQI(Link Quality Indication)对无线通信信道进行评级,LQI反映信道链路质量,表示接受数据帧的能量与质量,其大小基于信号强度以及检测到的信号噪声比,通常情况下与正确接收到数据帧的概率有关。LQI动态范围大,分辨率高,可以快速准确得到信道质量评级结果。

因通信区域取值相对保守,因而不存在信道很差的情况,可将信道级别分为VERYGOOD、GOOD、NORMAL、NOTBAD 4级。

再根据平衡时的成簇策略和信道评级结果,对铀尾矿库监测区域内每个节点进行功率分配,既可保证网络负载均衡前提下,避免簇成员节点射频能量的浪费。且通过功率调整,簇成员成簇时不会因为信道问题破坏网络负载均衡,平衡了成簇合理性和信道质量问题。

可根据信道质量等级(VERYGOOD、GOOD、NORMAL、NOTBAD),选择合适射频功率进行数据传输,如表1所示。

表1 功率调整

3.3 MHSR算法分析

在铀尾矿库实际检测中,考虑通信策略前,可先根据灰色预测确定Sink节点,选取备选簇头。

再考虑具体通信策略:簇内通信成簇过程参照表2进行,信道功率分配参照表1进行。簇间通信可采取多跳的协作传输方式,这种协作传输是多输入多输出的VMIMO(Virtual Multi-Input Multi-Output)。如图1所示,在铀尾矿库带状环形监测环境下,这种传输方式在Sink附近可能是多对一,远离Sink时可能是一对多,甚至是一对一的通信模式,MHSR算法流程如图3所示。

图3 MHSR算法流程

分别分析算法各步骤的复杂性,以各步骤的渐进时间复杂度作为说明,暂不考虑空间复杂度。

①一阶灰色微分方程GM(1,1)以生成的序列x(1)为基础,原始放射性核素迁移序列n越大,语句运行次数越多,时间复杂度越大,且是n的线性阶。

②对于选取备选簇头过程,N个节点i经式(8)运算最多得到N个Ti值,因此N越大时间复杂度越大,且是节点总数N的线性阶。

③分析成簇过程各语句的运行次数,如表2,可知该环节时间复杂度最终取决于最高阶(N-Nhost)S。

④信道功率分配中,新路由表项数目和LQI个数难以定量,但与簇内通信频度有关。节点总数N越大,各节点可采取的策略数S越大,通信越频繁,语句运行次数越多,时间复杂度越大。

⑤对于簇间多跳协作通信:假设极限情况下,各簇头采取一对一的通信策略则运行次数等于Nhost。进而可知在VMIMO条件下,时间复杂度与簇头总数有关,且是Nhost的线性阶。

综上可知,MHSR算法复杂度取决于最高阶项,即认为近似等于O(NS)。

4 仿真实验

首先在有通信重叠的区域(如z2、z3、z4)内任意取一个簇成员节点,按上述步骤确定该节点成簇时各信道的功率分配。在MATLAB中首先模拟演化博弈过程以得到最优策略,再与不同算法进行性能比较,实验表明本文提出的MHSR能有效提高网络生存周期。

4.1 最优策略

模拟重叠区域内各成员节点的博弈过程,达到演化平衡时所对应的策略即为最优策略,如表2所示。取簇头数Nhost=3,z2,z3,z4内节点数为20。其他区域内节点均只与一个簇头联盟,不参与演化博弈。

随机设定各成员节点的初始策略,达到演化平衡时最终策略趋于一个定值并不再随时间变化,如图4所示,坐标轴isx,isy,isz分别表示与簇头C1,C2,C3联盟的节点份额,即各成员节点采取的策略。

结果显示(isx,isy,isz)无限趋向于(0.753 7,0.898 4,0.72)。改变节点数进行多次试验,结果显示无论节点数多少,最终都能达到博弈的平衡点,因此可以证明达到平衡。

表2 成簇分析

图4 成员节点的演化过程

4.2 性能分析

改变节点网络的大小及节点密度,比较MHSR与CCREG及CMIMO的网络生存周期。实验中数据按轮进行传输,若在成员节点的通信区域内簇头存在,则各个簇成员按照演化平衡时的最终策略依次进行数据传输。所有节点传输完成后进行下一轮传输,直至第1个节点能量耗尽死亡。簇头的能耗开销如式(19)所示。

(19)

式中:ψ为数据包长度,Ec为簇头节点的剩余能量,Etran为接受或发送1 bit数据消耗的能量,Eamp为放大器消耗的能量,d0表示通信距离阈值。

4.2.1 节点密度的影响

监测区域可视为平整坝面,且Sink附近节点密度大,为考虑节点密度对监测的影响,在固定大小的区域(320 m×320 m)内随机分布40个、60个、80个、100个、120个、140个、160个节点,对比3种算法的网络生存周期。得到MHSR比CCREG分别延长8.9%、20.0%、14.6%、12.1%、11.1%、11.4%、11.0%;MHSR比CMIMO分别延长51.7%、58.9%、37.5%、32.0%、26.5%、53.7%,48.6%,如图5所示。

图5 节点密度对寿命的影响

4.2.2 监测区域大小的影响

考虑到铀尾矿库监测面积大,路由协议应当满足可大规模组网的要求,设置大小不同的监测区域(160 m×160 m,200 m×200 m,240 m×240 m,280 m×280 m,320 m×320 m,360 m×360 m,400 m×400 m),随机分布160个节点,对比3种算法的网络生存周期。得到MHSR比CCREG分别延长11.6%、18.1%、20.7%、29.5%、26.0%、26.9%,34.4%;MHSR比CMIMO分别延长70.2%、52.3%、50.1%、59.9%、51.2%、47.3%、57.5%,如图6所示。

图6 网络大小对寿命的影响

考虑节点密度的影响,保持监测网络大小不变分别计算上述数据的平均值,得出MHSR算法网络生存周期较CCREG和CMIMO算法分别延长了12.7%、44.1%。考虑网络大小的影响,保持监测节点数目一定分别计算上述数据的平均值,得出MHSR算法网络生存周期较CCREG和CMIMO算法分别延长了23.8%、55.4%。由图5、图6中曲线变化的趋势可知,单一变量下,3种算法CMIMO、CCREG、MHSR的网络生存周期均随节点密度的增大而减少,随监测区域的增大而增大。

其中相较于CMIMO算法,MHSR的网络生存周期得到了显著延长,这是由于通过演化博弈实现了网络负载均衡,进而使网络中节点存活轮数显著增加,证明了所用理论的优势。

其次,MHSR较CCREG的网络生存周期得到了有效延长,说明在负载均衡的基础上,进行信道功率分配能最大限度的节省射频能耗,进而延长网络生存周期。

5 总结与讨论

本文提出了一种新的成簇方式。对于同一个簇成员节点,可以与不止一个的簇头结成联盟,通过有限的演化博弈,实现收益最大化,保证了网络负载均衡。在此基础上,节约了信道质量好的节点射频时所需的能量从而延长了网络寿命。此外,运用灰色预测法得到重点监测部位后,在这些部位布设Sink节点,增加节点布设密度,确保分簇路由中关键区域监测数据传输的连续性和稳定性,进而保障了铀尾矿库放射性核素迁移的安全和有效控制。

但当有多个通信区域重叠,节点可选择策略数S达到3个以上时,其成簇过程收益函数的计算会增加能量和时延开销,算法复杂性O(NS)也会增大。因此需结合监测实际,合理设置簇头占全网总节点数的百分比,即p值,使得网络拓扑结构更为合理,避免不必要的簇生成。