一种基于无标度局域世界演化网络模型的无线传感器网络拓扑构建

北京信息科技大学 自动化学院，北京 100192

一、引言

1999年，Barabasi与Albert在研究万维网的度分布时发现，网络中节点的度分布并不符合泊松分布关系，而是符合一种幂律分布，即随着节点连接度的增加，其概率呈不断递减的规律，于是提出BA无标度网络模型。该模型的拓扑演化由“增长”和“择优连接”两个机制完成，所形成的网络拓扑结构相较于复杂网络中规则网络模型和随机网络模型更具有现实意义，符合现实世界中大多数网络的结构，更加便于对复杂网络的研究[1-3]。

此后，各学者着手在其基础上做了各种各样的扩展[4]。Bianconi等人[5]提出适应度模型，在优先连接的过程中，新加入网络的节点优先连接的概率并非是与节点的度成正比，而是与节点度和适应度的乘积成正比。Zhu等人[6]考虑无线传感器网络（Wireless Sensor Networks，WSNs）中节点能量损耗过快的问题，提出能量感知演化模型（Energy-Aware Evolution Model，EAEM），对适应度模型进行优化，将节点剩余能量作为适应度，进行择优连接时的概率计算。Barrat等人[7]提出一种加权网络模型——BBV模型，将节点的权重考虑进无标度网络模型中。李翔等人[8]根据某些网络的特点，提出局域世界演化网络模型，在新加入节点优先连接时，不是选择网络中原有旧节点作为备选范围，而是在旧节点中随机选择若干个节点，缩小了可连接节点的范围。张燕平等人[9]提出局域世界删除演化网络模型，论述了删除部分节点和边对现有网络的影响。罗小娟等人[10]从局域世界演化角度出发，提出了一种能量感知的局域世界动态演化模型，不仅考虑了传感器网络中节点能量感知连接机制，还考虑了节点和链路在演化过程中的动态变化。

韩涛[11]提出了无标度网络路径能耗优化模型，并指出节点通讯能耗与平均路径长度成正比。在模型仿真模拟中，平均路径能耗最低时，网络中最优节点度为10，即每个节点的节点度值阈值为10。本文参照其结论，对传统的局域世界演化网络模型进行优化，旨在降低网络平均最短路径，以达到降低能耗，延长网络生存周期，提高抗毁性的目的。

二、无标度网络及特征参数

1、无标度网络BA模型

Barabasi和Albert研究万维网的度分布，渐渐发觉万维网网络中节点的度分布不符合泊松分布，而是符合一种幂律分布，即随着节点度的增加，节点度的概率呈不断递减的趋势，于是提出BA无标度网络模型，其网络模型有两个重要特性：

（1）增长：网络在每一个时间步都会加入新节点，通过新加入的节点实现整个网络的动态变化；

（2）择优连接：新增的节点与原网络中节点度大的节点连接的概率大。

基于网络的增长和优先连接特性，BA无标度网络模型的构造算法如下：

（1）增长：从一个具有m0个节点的初始网络开始，每次加入一个新的节点，并且与网络中m个已存在的节点相连接，在这里m≤m0；

（2）优先连接：一个新节点j与一个已经存在的节点i相连接的概率Πi为：

其中，ki—已存在节点i的度；

kj—新节点j的度。

在经过时间步t后，该算法会产生一个有N=t+m0个节点、mt条边的网络。图1为当m=m0=2时的BA网络的演化过程。初始网络有两个原节点，每个时间步新增加的一个节点按优先连接机制与网络中已存在的两个节点度值大的节点相连。需要注意的是，在算法中，每个旧节点都有一个概率，而新节点选择是否连接旧节点，需要看随机数落在哪个节点的概率范围内。

平均路径长度[12]：网络中两个节点i和j之间的距离dij定义为连接这两个节点的最短路径上的跳数。网络的平均路径长度L定义为任意两个节点之间的最短路径数之和的平均值，即：

其中，N—网络节点数。

聚类系数[12]：若网络中的一个节点i与ki个节点直接相连，这ki个节点就称为节点i的邻居。由数学分析知，在这ki个节点之间最多可能有ki(ki-1)/2条边，而这ki个节点之间实际存在的边数和总的可能的边数之比就定义为节点i的聚类系数Ci，即：

其中，Ei—ki个节点之间实际存在的边数。

2、无标度网络局域世界演化网络模型

在BA无标度网络中，仅仅依赖各节点的度值来计算每一个节点的优先连接概率，由此可得到网络幂律形式的节点度分布。但在许多现实的网络中，局域世界连接性的存在，每一个节点都有各自的关系网，因而各节点也只能使用整个网络中局域关系网所连接的信息。李翔等人[8]提出一种局域世界演化网络模型来描述此种情况。模型构造算法如下：

（1）增长：网络初始时有m0个原始节点和e0条边，每个时间步新加入一个节点和附带的m条边；

（2）局域世界优先连接：从网络已有的节点中随机选取M个节点（M≥m），作为新加入节点的局域世界关系网。新加入的节点根据下面的优先连接概率来选择与局域世界关系网中的m个节点相连：

其中，LW—新选的M个节点组成的局域世界。

三、基于无标度局域世界演化模型的WSN网络拓扑

1、基于WSN的局域世界演化网络模型构造算法

从局域世界演化网络模型出发，结合传感器网络的特点，对传统的无标度局域世界演化网络模型进行优化。一个是在WSN中，每个节点都有其通讯半径，在增长的过程中，不能选取通讯范围外的节点进行连接；另一个是，在WSN优化中，考虑到网络中部分节点连接度过高，会影响整个网络的能量平衡性及抗毁性[11]，设定网络中节点度值阈值kmax≤10。该模型构造算法如下：

（1）增长：网络初始时有m0个原节点，每个时间步新加入一个节点和附带的m条边；

（2）改进的局域世界优先连接。选取新节点通讯范围（半径为r的圆形区域）内的M个节点（M≥m），作为新加入节点的局域世界。新加入网络的节点根据以下优先连接概率来选择与规定局域世界中的m个节点相连：

其中，S—由局域世界中（即新节点通讯范围内）随机选取的M个节点组成。

在新节点择优连接过程中，若将要连接的节点度=10，则新节点选取概率第二大的节点继续判断，直到找到符合节点度≤9的节点，才与之连接。具体流程如图2所示。

2、仿真及分析

（1）仿真设计

仿真环境设定：

面积：100m×100m的方形区域；

网络初始节点数m0：5（这里使初始节点间全连通）；

新增节点添加新边数m：1；

节点总数N：50；

节点通讯半径r：50m；

局域世界所选取的节点数M：5。

仿真结果如图3、图4所示。

（2）结果分析

在本次仿真环境下进行了10次实验，图3～5为首次仿真结果图，表1为 模型优化前后网络的平均路径长度和聚类系数比较。多次进行仿真实验是为了证明优化模型的适用性、普遍性。

图3和图4是模型优化前后的网络拓扑图，在仿真中，考虑现实场景下随机抛撒节点位置的不确定性，为了使新增节点在增长及择优连接的过程中可以找到符合条件的旧节点相连接，增大程序的可实现性，在不改变网络其他参数的前提下，适当增大节点通讯半径（一般设置节点通讯半径不超过区域边长的一半）。从图4中可以直观地看出，优化的模型较之图3中局域世界网络演化模型，节点间连边密度小，距离短。

图5给出优化的模型中各节点的度值大小，可以看出，仿真中各节点的度均未超过设定阈值。当网络规模较小，即节点总数较少时，模型优化前后的各节点度大小分布差别不大，因为在优化的模型中规定单个节点度的上限值不超过10，而网络中新增节点只增加一条边，从概率角度来讲，节点度值超过10的节点也很少。也就是说，当网络规模较小时，优化的模型在设定节点度值阈值方面的效用比较小。

根据尹文晓[13]构建的网络生命周期模型，网络生命周期Tnet为：

其中，Ei—节点的剩余能量；

L—平均路径长度；

δ(0) —负载量（具体可查询文献[13]）；

a、b—常量。

从公式中可以看出，当其他参数不变时，网络的平均路径最短长度L和节点生命周期Tnet的关系，即平均路径最短长度L越小，节点生命周期Ti越长。

由此，本文优化的模型旨在减小网络的平均最短路径长度，从而延长网络的生命周期，间接提高网络的抗毁性。

由表1可看出，仿真结果中，10次有7次优化后的模型平均最短路径比传统的局域世界演化网络模型小。因为算法中网络节点生成位置的随机性，造成少许情况下优化的网络模型中，部分新节点连接通讯范围内较远的节点，而传统网络中部分新节点连接范围内较近的节点，使得之后增长的过程中，网络整体平均最短路径增大。但在大部分情况下，优化的模型仍能有效降低网络的平均最短路径长度，达到提高网络抗毁性的目的。

表1 模型优化前后网络的平均路径长度和聚类系数比较

四、结束语

无标度网络抗毁性方法一直都是传感器网络抗毁性领域研究的重点。本文从无标度局域世界演化网络模型入手，结合传感器网络的特点，对局域世界演化网络模型进行改进优化。通过matlab仿真平台，分析对比传统的局域世界演化网络模型和改进的网络模型，其结果证明，该模型可有效降低网络平均最短路径，验证了模型的真实有效性，对网络抗毁性方法有借鉴意义。