基于多链路无线传感器网络的级联模型及算法

王 勋, 王斐儒, 商国旭

(赤峰学院 物理与智能制造工程学院, 内蒙古 赤峰 024000)

无线传感器网络(WSNs)是物联网系统最重要的组成部分之一.在实际的WSN中,网络组件(即传感器节点和无线链路)的失效会导致网络负载被重新分配,这可能会导致一些节点和链路由于过载而失效,将导致新一轮的网络负载重新分配,最终可能会导致更多的节点或链接失效[1].

近年来WSN的级联失效得到了广泛的关注.已经提出了许多级联模型来模拟WSNs的级联过程[2-7],但这些模型主要基于一般的度负载度量或介数负载度量,没有考虑接收器节点的影响.在实际的WSNs中,因为所有信息最终将从一般的传感器节点传输到接收器节点,接收器节点的放置对网络负载分布有非常重要的影响[8-9],在研究级联失效时不容忽视.

为了研究多链路WSN的级联稳健性,本文提出了基于新的负载度量“多向链接介数(multi-directional link betweenness,MLB)”的现实级联模型.在此基础上,设计了进化算法MAS,通过优化接收器节点的位置来提高网络的鲁棒性.

1 多链路WSNs的多面向级联模型

为了正确地描述多链路WSNs的负载分布,引入了一种新的负载度量:多向链接介数(MLB),在链路容量和节点容量级联模型的基础上,提出了多链路WSNs级联失效的鲁棒性度量方法.

多链路WSN可以用无向图G=(V,E)来描述,其中V={1,2,…,N}是由传感器节点和接收器节点组成的集合.E={eij|i,j∈V}是传感器节点之间的无线链路集.如果节点i和节点j之间有无线链路,则N×N邻接矩阵[aij]中的aij=1.使用节点集Vg和VS分别表示一般传感器节点集和接收器节点集.根据上文所述,可以很容易地得到V=Vg∪VS.

1.1 多向链接介数

为了测量多链路WSN中每个链路的负载,MLB的定义如下:

(1)

其中:S(i)是从节点i接收消息的接收器节点集;wi,m,ejk(t)是在t时刻从节点i到边缘ejk的路径数;wi,S(i)(t)是从节点i到接收器节点的路径数;Ng是网络中传感器节点的数量;NS(i)是汇聚集S(i)的大小.当从传感器节点到其接收器节点的每条路径通过边缘ejk时,Dejk(t)的最大值为1;当传感器节点不需要通过边缘ejk就能到达其接收器节点时,Dejk(t)取的最小值为0.由于最短路径模式在实际的多链路WSN中应用最为广泛,在本工作中仍然使用该模式来分析网络负载分布.为了验证所提出的MLB的合理性和可靠性,提出了两种具有代表性的拓扑结构:单链层次拓扑和多链层次拓扑,如图1所示.

图1a只引入了一个接收器节点1,传感器节点2～8将它们的消息发送到接收器节点1.可以看出,从节点 2 到节点 8 的所有信息都必须通过e12到达接收器节点1;e23和e24分别从三个传感器节点获取流量负载;e35、e36、e47和e48仅从其本身的端点节点获取流量负载.表1展示了每个区域的多向链接介数(MLB),图1a中的每个链路e12取最大值1,即整个网络的所有流量负载都将通过.e23和e24的介数值为 0.47,表明需要承担几乎一半的网络负载.e35、e36、e47和e48取相同的值0.142,即只需要从其端点节点获取负载.

图1 单接收器和多接收器无线传感器网络的分层拓扑

表1 单接收器和多接收器分层中的多向链接介数

图1b引入了三个接收器节点 1～3,节点4～10将它们的消息发送到离它们最近的接收器节点,可以很容易地观察到,节点5、7、8通过e25到达离他们最近的接收器节点2;节点6、9、10通过e36到达最近的接收器节点3;节点4通过e14到达离它最近的接收器节点1;没有负载通过e45和e46;e57、e58、e69和e6,10仅从其端点节点接收负载.表1显示了图1b中每个环节的MOB,可以看出,e25和e36的介数值为 0.47,表明几乎承担了一半的网络负载;e14、e57、e58、e69和e6,10的介数值为0.16,即仅从一个传感器节点获取负载;e45和e46的介数值为 0,表示它们是无负载的.

1.2 负载和容量

为了确保级联模型可以应用于不同类型的WSN,有必要对网络组件的负载和容量进行标准化.由于所提出的MLB可以有效地反映网络负载分布,可将链路的初始负载定义为MOB的函数,即将t时刻的链路ejk的负载定义为

Lejk(t)=Dejk(t)α

(2)

其中:α≥0是负载指数系数,当α=1时,每个链路的负载与其MOB值呈线性相关.

在实际的WSN中,无线链路的传输容量受到带宽的限制,可将每个链接的容量定义为

(3)

其中:β为链路容差系数,表示每个链路的带宽;LE(0)为初始网络中链路负载的平均值;NE为网络中的链路数.由于在实际的WSN中,传感器节点的传输模块总是相同的,因此该模型中的每个链路都具有相同的容量.WL为链路可以传输的最大负载.当链路Lejk(t)的实时负载超出其容量WL时,只能传输负载WL,剩余的负载Lejk(t)-WL将留在缓冲区中,等待下一刻的传输.因此,对于任何时间t,可得到每个传感器节点i的负载:

(4)

其中:Ω(i)是由节点i的相邻节点组成的集合;Ueij(t)表示由于带宽限制而没有发送的链路eij上的负载.如果eij负载在其容量WL范围内,则无负载,否则产能过剩负载将返回发送节点;fij(t)用于识别节点i是否是链路eij承载负载的发送方.在本模型中,传感器节点的容量受到其缓冲区大小的限制,将每个传感器节点的容量定义为

(5)

其中:γ表示每个传感器节点的容差系数;Lg(0)为初始网络中的节点负载的平均值;Ng为网络中的传感器节点数.当节点i的Li(t)大于其容量WN时,将发生缓冲区溢出,节点i无法继续工作.

1.3 级联过程

本研究模型中,网络中所有传感器节点和链路的初始负载都小于其容量,链路节点不受容量的限制,所有通用传感器节点都将它们自己的信息传输到它们最近的接收器节点.

当一个传感器节点失效时,将更新每个链路的负载.假设链路eij的容量在t时间已饱和(即Leij>WL),即剩余负载Lejk-WL将返回到其发送方节点i.此时,节点i的负载将更新到LeijD-WL.节点i的失效将破坏网络向接收器节点的连通性,由于过载和中断而导致的节点失效将引发跨网络的新一轮负载重新分配,并且可能引起一些新的节点失效.这个级联的过程在网络中每个链路的负载达到饱和之前不会停止.

图2展示了多链路WSN中级联过程的示例,节点1和节点6是接收器节点.其余的节点为一般的传感器节点,假设负载指数系数α=1和WL=WN=0.6.图2a为网络的初始状态,此时,每个链路的负载低于其容量,不会返回给发送方节点.因此,所有传感器节点的负载均为0.在图2b,节点5受到攻击无法继续工作,所有负载通过链路e12到达接收器节点1.链路e12的负载被更新到0.833,带宽容量达到饱和.此时,未处理的负载被转移到其发送方节点2.节点2的负载更新到0.233.在图2c,当t=3时,节点2的负载增加到0.699,大于其容量.在图2d,一旦节点2失效,其余节点将被中断.

图2 多接收器无线传感器网络级联过程示例

1.4 稳健性度量

为了合理地衡量网络对级联失效的鲁棒性,本研究提出了鲁棒性度量.该度量是基于“有效组件”的概念,首先从初始网络中随机删除一个传感器节点j,并观察有效组件的大小.为了量化整个网络的网络鲁棒性,归一化有效组件最终规模,即:

(6)

当S=0时,表示任何节点的失效都会触发级联失效,整个网络将瘫痪.当S=1时,任何节点的失效都不会影响其余节点的正常运行,此时网络的鲁棒性最高.

2 多链路放置的模因算法(MAS)

2.1 初始化

在MAS算法中,每条染色体代表一个多链放置方案,可以用一个二进制向量X表示.X的大小等于网络N的大小,X的第i个元素xi表示节点i的状态,其中xi=0表示节点i为一般的传感器节点,xi=1表示节点i为接收器节点,X中每个元素的和等于给定的接收器节点数量Rs.多链路放置方案如图3所示,可以用染色体X=[10001000100]表示.

图3 使用染色体表示多链路放置的样本

最初,MAS为具有W染色体的种群.在初始化过程中,通过初始网络G0,随机选择Rs节点作为接收点,生成每条染色体.

2.2 交叉算子

交叉算子用于交换不同染色体之间的遗传信息.本文设计了一种新的交叉算子,可以有效地交换两种放置方案的信息.这个交叉算子作用于两个随机选择的父本染色体,并产生一对子代染色体.为了确保交叉算子中的汇节点数量不变,首先将接收点的状态信息拼接在一起,生成一个“复制子染色体”;然后,从复制子染色体中随机选择包含接收器节点状态信息的Rs元素,产生两条新的子染色体.交叉算子的示意图如图4所示.

图4 交叉算子示意图

2.3 局部搜索算子

为了获得优化的网络鲁棒性多链路放置方案,设计了新的局部搜索算子,使网络的负载更加平衡.首先引入了一种新的度量“多向网络熵”来衡量网络的负载平衡水平.网络结构越均匀,其熵就越大.将网络G=(V,E)的多向网络熵HG定义如下:

算法1局部搜索算法

输入:单染色体G与局部搜索概率pl

输出:局部搜索后的染色体Gl

ifU(0,1)

计算HG

将Gi置零

从G中随机选择为零的Gi,并将其设置为1

得到更新值HG*

ifHG*≤HG

将Gi设为1,将Gj设为0

结束

2.4 MAS的实现

在MAS中,第一步是使用初始算子生成初始种群,使用交叉算子生成子代群体.然后,通过对父群体和子群体执行局部搜索算子选择算子,可以得到下一代子群体.经过许多代的进化,所产生的群体具有高稳定性的染色体.

算法2MAS算法

输入:种群规模W,初始化网络G0,交叉概率pc以及局部搜索概率pl

输出:S值最高的染色体

fori=1:W

基于每条染色体鲁棒性的轮盘赌选择算法,从Pm中选择Gm,执行局部搜索运算

结束

结束

算法2给出了MAS的算法框架,每条染色体代表一个多链WSN的拓扑结构,通过前述所提出的评价方法,可以获得其鲁棒性.该方法通过依次计算每个节点失效引起的级联失效损失,可以获得级联鲁棒性.

在MAS中,使用了两种经典的概率选择算法(即轮盘赌选择算法和二进制锦标赛法).在轮盘赌选择算法中,选择目标的概率与其自身的适应值成正比.二进制锦标赛法是从种群中随机选择的两条染色体之间进行“锦标赛”,每个锦标赛的获胜者(最好的适应值)将被选为下一代种群.

3 模型的评估

3.1 多向级联模型的评估

本研究基于网络拓扑来评估所提出的级联模型.在该网络拓扑中,布置了300个传感器节点,传输半径设置为20 m,在模拟区域内随机放置3个接收器节点,网络拓扑结构如图5所示.

图5 网络拓扑结构示意图

图6分别描述了基于度的和基于介数的级联模型生成的网络负载分布,可以看出接收器节点附近的传感器节点的负载并不高于其他区域的节点.在基于度的级联模型产生的负载分布中,网络负载集中在无线链路分布更密集的区域.而在基于介数的级联模型产生的负载分布中,网络负载主要分布在网络的中心区域.

图6 网络负载分布情况

图7显示了由多向级联模型生成的网络负载分布,可以清楚地观察到接收点附近的负载远高于其他区域.在该模型中,可以使用到接收器节点的最短路径数来表征传感器节点的负载,从而反映接收器节点在网络负荷分配中的作用.

图7 多向级联模型产生的网络负载分布

3.2 算法比较

大规模WSNs中的多链路放置优化是一个非线性问题,为了验证MAS的优势,将MAS与PSO-MSPA[10]和DPSO[11](即经典PSO的改进版本)进行比较.在实验中,三种算法具有相同的目标函数,迭代次数均为2 000次.

从图8可以看出,MAS可以在较短时间的情况下获得更具有鲁棒性的多链路放置方案.在小规模网络(N=300)的情况下,这三种算法获得的多链路放置方案的鲁棒性比较接近,但MAS可以在900次迭代之前找到最优的鲁棒性方案,而其他两种算法需要超过1 400次迭代.

图8 不同算法的性能比较(α=1,β=0.5,γ=1.5)

可以看出,当网络规模扩展到N=600时,MAS与其他两种算法之间的性能开始出现差异.此时,MAS可以在1 500次迭代中获得最优的鲁棒性,而其他两种算法需要更长的时间.表2列出了三种算法中的最佳和最差的鲁棒性,进一步验证了所提的MAS在寻找级联失效最优多链放置方案方面的优越性.

表2 MAS算法与去其他算法的比较

4 结论

由于硬件成本有限,WSN容易发生级联失效.本文基于多链路网络,提出了一种无线传感器网络的级联模型,并设计了一种模因算法MAS,通过优化多链路放置来提高网络的鲁棒性.提出采用模因算法MAS来优化多链路布局,以抵抗级联失效.在新的网络平衡度量“多向网络熵”基础上设计了局部搜索操作算子.仿真表明,所提出的级联模型能够表征多链路WSN的级联过程,可有效提高系统稳定性能.与现有算法相比,MAS可以在短时间内获得更稳定的多链路放置方案.