双向选择机制下权重约束的WSNs拓扑演化模型研究*

王传云，朱 涛，尹 燕，赵军辉,3

(1.华东交通大学 信息工程学院,江西 南昌 330013;2.华东交通大学 软件学院,江西 南昌330013;3.北京交通大学 电子与信息工程学院，北京 100044)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)是由大量具有计算和通信能力的传感器节点组成，一般部署在无人值守区域，用以自主完成指定的任务[1]。近些年，复杂网络理论已成为跨学科领域的重要分析工具和研究方法[2～4]。随着研究的不断深入，发现WSNs的很多特性及行为符合复杂网络的基本机制，因此，通过复杂网络研究WSNs演化模型已经成为当前研究的一个重要热点[5]。

2004年，BBV加权演化网络模型被提出，模型考虑了拓扑和权重在演化过程中的关系，重现出了真实网络情况[6]。文献[7]结合差额奖惩机制，提出了基于奖惩机制的信任演化模型，解决了WSNs节点间信任决策导致网络不稳定的问题。文献[8]考虑节点的强度和节点的吸引力，提出了基于节点适应度动态演化的加权复杂网络演化模型。在复杂网络演化模型基础上，将WSNs与演化模型相结合，文献[9]结合复杂网络分析了WSNs的拓扑特征和脆弱性对于节点能耗优化和网络生命周期的影响。文献[10]结合了节点剩余能量、信号强度和链路质量提出了能耗均衡路由协议，很好地均衡网络中的能量。文献[11]中根据网络中节点和链路数量增加和减少的动态性，结合复杂网络模型，提出了高效动态自组织演化模型，使整个WSNs的能量消耗更加平衡，拥有更好的随机节点容错性。由于网络对节点的权重没有进行限制，使得节点权重可以无限制增长。文献[12]结合加权演化动力学理论提出了权重强度约束加权演化模型，限制了节点强度的无限增加，可以平衡网络的流量负担，降低节点快速死亡的风险。文献[13]提出了基于双向吸引机制的WSNs拓扑控制算法，使得WSNs的成簇特性明显，构建层次型拓扑结构，为构建大规模的WSNs分簇拓扑结构提供参考。

本文在权重约束模型的基础上进行改进，结合优化的双向选择机制，提出了点权约束释放模型。利用MATLAB工具，对模型的簇头分布、点权分布、度分布和网络能耗进行仿真，仿真结果和理论分析相吻合，验证了理论的正确性。

1 基础理论

1.1 WSNs分簇拓扑结构

在分簇拓扑结构中，对节点进行分类，分为簇头节点和普通节点。普通节点负责收集信息，将信息发送给簇头节点，簇头节点将信息汇总再发送给基站。在WSNs中，分簇拓扑结构可以有效减少能量损耗，延长网络节点的寿命。同时，分簇拓扑结构具有可延展性，可以应用到大规模复杂WSNs中，降低网络通信负担。

1.2 权重约束演化模型

BBV加权演化网络模型中，当节点边缘权重增加时，将导致节点权重的增加。BBV模型中，新加入节点(以下简称新节点)连接已存在节点(以下简称老节点)的概率为p=si/∑ksk，从连接概率公式可以看出，节点i的点权越大，连接的概率也就越大，导致节点i的点权有无限增大的可能；权重约束模型中，给点权设置最大阈值smax，限制节点权重的无限增长，达到降低能量损耗的作用[12]。

2 基于双向选择机制的点权约束释放演化模型

2.1 算法前提假设

假设WSNs中节点随机分布，并具备以下特点：1)每个传感器节点都有自己唯一的标识符ID；2)每个传感器节点在部署时都具有相同的能量，且能量不能被补充；3)基站的能量充足，且可以检测到WSNs区域的内部或外部。

2.2 双向选择机制下权重约束的WSNs拓扑演化模型

本模型采用权重约束模型中的方法，给节点的权重设置最大阈值smax[12]。网络的演化步骤如下：

1)新节点的加入：每一个时间步加入一个新节点，新节点与m个老节点以一定概率连接,连接概率见式(1)和式(2)，新节点建立连边后，将边权值赋为w0

(1)

(2)

式中p(i←j)为节点j连接到节点i的概率，此处，i为老节点，j为新节点，si为节点i的权重，smax为节点权重的最大阈值，β为权重超过smax时，设置的si/smax固定数值，起到固定连接概率的作用，∑ksk(1-sk/smax)(k=1，2，…，N)为网络中已存在节点的权重总和。

2)老节点间相互连接及边权的更新：每一个时间步以概率α在网络已存在的节点中，增加n条新连接[14]。选择两个老节点i,j以式(1)、式(2)的连接概率进行连接，如果两个节点未建立连接，则建立连接，并将边权值赋为w0；如果已经建立连接，则将其边权值增加Δw。

在模型演化过程中，初始阶段本模型和一般演化模型类似，节点强度应远小于smax，si/smax≈0。随着时间的增加，节点连边数逐渐增加，会出现点权较大的节点。这时，通过smax的限制，可以降低该节点被连接的概率，使点权缓慢增加或停止增长。但是，在大规模WSNs中，会出现大量节点的点权达到smax，这会导致大量老节点无法连接新节点。使得在新节点加入时，新节点远距离连接其他节点，节点能量过多的消耗，所以在点权达到smax时，将si/smax替换成β，使得连接概率固定，这样新节点可以就近连接点权达到smax的老节点。

下面，本文将推导在节点权重si

(3)

内部老节点连边的方程为

(4)

式中Wij为两个节点i，j的边权，m为新节点连接老节点的个数，α为每个时间步老节点间新增连边的概率，n为老节点新增连边的个数。

点权的变化由内部老节点的连接和权重的更新以及新节点的加入引起，因此节点i权重的变化率方程为

(5)

由于大多数节点的权重远小于smax，因此近似得到了权重的总和

∑ksk(1-sk/smax)≈∑ksk=(m2+2n)t

(6)

将式(6)代入式(5)中，可以得到

(7)

将式(7)积分，并代入初始条件si(t=ti)=m求解，可得点权si随时间t变化的方程

(8)

从式(8)中可以看到，在si

点权si的概率可以通过式(9)计算

(9)

由于新节点以固定时间步加入网络，其遵循均匀分布。将p(ti)=1/t代入式(9)计算得到节点权重概率分布公式

(10)

由式(10)可以看出：si

(11)

(12)

由于此时新节点加入和老节点连边的情况较多，不能对公式进行统一推导，所以当新节点连接权重达到smax的老节点或者老节点权重一个达到smax，一个未达到smax时，使用式(11)进行计算；当两个老节点权重均达到smax时，使用式(12)进行计算。

2.3 算法步骤

1)初始网络：给定m0个初始节点，初始节点间两两连接，边权赋值为w0。

2)网络增长：依照双向选择机制，每个时间步加入一个新节点，以式(1)、式(2)的连接概率进行连接。同时，以概率α对老节点边权进行更新。当网络节点数达到N时，网络停止增长。

3)簇群形成：根据预设簇头数目，按照点权si的大小依次选取簇头，簇头通信半径范围内的其他节点，依照节点与簇头间的距离大小来选择相应的簇头节点，加入簇群。簇群完成后，每个簇头节点将自身ID广播至与其相连的节点，普通节点将自身ID发送给簇头节点并储存。

4)信息传输：节点信息传输时，普通节点将信息发送给簇头节点，簇头节点将信息发送给基站；远离基站的簇头选择其他簇群的簇头作为中继节点，对信息进行多跳传输，以减少能量损耗。

3 模型仿真与结果分析

本文利用MATLAB 2016b仿真工具，模型仿真场景为1 000 m×1 000 m，网络节点总数为1 000，节点随机分布，网络初始节点数m0=8，节点通信半径为80，每个新节点连接m=6个老节点，最大阈值smax=100，超出smax时si/smax的固定数值β=0.9，每个时间步老节点间新增连边的概率α=0.8，各边初始权重和增加权重w0=Δw=1。在本节中，将本文模型与双向选择模型和权重约束模型进行对比。通过四个方面比较这三个模型：簇头分布、点权分布、度分布和网络能耗。

图1中，取不同的β=0.8，0.85，0.9，0.95对节点权重分布进行比较。从仿真结果可以看出，随着β的增长，约束效果的增加，节点强度分布的尾端逐渐收缩。对比可以发现，当β=0.8，0.85时，尾部收缩不明显；当β=0.9时，尾部收缩效果明显；当β=0.95，尾部收缩相对密集。因此，本文模型选择β=0.9进行网络仿真。

图1 本文模型中β=0.8，0.85，0.9，0.95的节点权重分布

本文选择100个节点进行模型仿真。如图2所示，在双向选择模型中，会出现个别簇头大量连接节点，导致其他簇头连接节点过少的情况；而权重约束模型中簇头节点分布不均，出现簇头距离近的情况；而在本文模型中，簇头节点分布均匀，簇内节点也相对分布均匀。

图2 100节点5簇头模型仿真

从图3可以看出，当强度较小时，三个模型点权的分布基本上是一致的，但随着权重的增长，尾部明显不同。在双向选择模型中，由于点权的无限增长，导致一些节点的点权值接近104；同时，在权重约束模型中，由于点权被约束，尾部被限制在100左右；在本文的模型中，可以看到尾部的一些节点强度超出了smax，这是因为给达到smax的节点固定连接数值β的原因。这些超出smax的节点就可以继续连接近距离新节点。

图3 点权分布

如图4所示，比较了节点的度分布，当节点权重强度受到限制时，将影响其他节点的连接，但是，由于节点释放的原因，所以可以清楚地看到度的分布的尾部会有一些节点摆脱约束。

图4 度分布

图5通过对1 000个节点的能耗仿真可以看出，三个模型第一个节点死亡的轮数基本差不多。在双向选择模型和权重约束模型中系统能耗完全消耗分别在1 200轮和1 400轮左右。但是，本文模型中，在2 000轮时，系统中还有节点没有死亡。这是因为本文模型的节点受到约束，不会无限制点权增加；同时，在点权达到smax时，给予一定的选择概率，使节点可以突破smax，避免了大量节点的点权达到smax不增长的情况，为WSNs提供了相对均匀的簇头分布。

图5 三种模型的网络能耗分析比较

4 结 论

本文在双向选择模型的基础上增加老节点间连边和边权的更新，使模型更接近实际情况；通过对权重约束模型中点权约束的释放，使被约束节点可以连接新节点，避免能量过多损耗。对该模型的簇头分布、点权分布、度分布和网络能耗4个方面进行了仿真，结果表明：本文模型在簇头分布上比较合理；在点权和度分布上有着很好的限制和释放的效果。当对比模型节点全部死亡时，本文模型的节点死亡仅达到80 %左右，在减少网络能耗方面效果显著，可以有效地延长网络中节点的寿命。而且，通过分簇拓扑结构可以将模型延展到大规模复杂传感器网络，使得该模型更适用于大规模WSNs场景。