现实生活中许许多多的网络都具有复杂网络的性质，如社会关系中的科学协作网、朋友关系网；生态系统中的蛋白质网、神经元网络；技术网络中的Internet以及信息网络中的WWW等。作为复杂网络重要特性之一的小世界特性，是复杂网络最普遍和最重要的拓扑结构属性之一，小世界现象普遍存在于大量真实网络中，如计算机互联网、科学家合作网、产品生产关系网和电力网络等。

1 小世界网络模型

小世界网络的本质特征是具有小的平均路径长度和大的聚类系数^[1]，将复杂网络的小世界现象引入无线传感器网络(Wireless Sensor Network, WSN)的研究，对分析WSN的拓扑结构、发现WSN中隐藏的规律以及预测WSN的行为具有十分重要的理论意义。

1) 平均路径长度：平均路径长度定义为所有节点间通信距离的平均值。计算公式如式(1) 所示：

$ L = \frac{2}{{N(N - 1)}}\sum\limits_{i = 1}^n {{d_{ij}}} $

(1)

其中：N表示的是传感器节点的数量，d_ij表示的是节点i和节点j之间的通信距离实际存在的边条数。

对小世界WSN平均路径长度的计算，目前还没有非常精确的解析表达式，如果小世界WSN通过“随机化重连”构成，则平均路径长度如式(2) 所示：

$ L\left( p \right) = \frac{{2N}}{K}f\left( {NKp/2} \right) $

(2)

其中：N表示的是传感器节点个数，K表示的是节点度数，p为重连概率，f(x)表示的是普适标度函数。

普适标度函数f(x)基于平均场方法给出：

$ f(x) \approx \frac{1}{{\sqrt {{x^2} + 2x} }}\arctan {\rm{h}}\sqrt {\frac{x}{{x + 2}}} $

(3)

当节点的平均度固定时，平均路径长度的增加速度与N的对数成正比。表明基于小世界的无线传感器网络其平均路径长度较小，且对于随机故障具有较强的鲁棒性。

2).聚类系数C：聚类系数描述了节点i与其直接相连的邻居节点的连接关系，如式(4) 所示：

$ {C_i} = 3{N_\Delta }(i)/{N_3}(i) $

(4)

其中：N_Δ(i)表示的是该网络中包含节点i的三角形总数，N₃(i)表示包含节点i的三元组总数。

对部分聚类系数较小的边进行一些必要的选择性删改，可提高网络整体的平均聚类系数，从而达到简化拓扑结构、优化路径选择的效果。

广大学者提出了很多无线传感器网络小世界特性的构造方法。文献[2]提出了基于NW(Newman-Watts)小世界WSN的构造方法，但是网络的抗毁性较差，性能低，造价昂贵。文献[3]提出了基于汇聚节点(sink node)构造小世界WSN，抗毁性较差，适用于小规模的网络。文献[4]提出了基于拓扑优化的小世界WSN构造，该算法形成了一种静态拓扑，抗毁性适中，网络规模适中。

针对现有算法的不足以及经验，本文提出了一种基于小世界特性的无线传感网层次型路由算法(Hierarchical routing Algorithm for wireless sensor networks based on Small World Network Model, HASWNM)，通过添加高性能节点以及在簇头间添加捷径的方法，使得无线传感器网络体现出小世界特性。该算法在簇间中继选择时候考虑了簇头自身的能量问题，达到了很好的节能效果。

2 本文算法 2.1 系统模型

1)N个传感器节点随机部署在M×M的正方形监控区域内，传感器节点分为普通节点和高性能节点。节点通过ID(Identification)进行标识，并且存储、计算能量受限。

2) 传感器节点一旦被部署，则一直处于静止状态。

3) sink节点存储、计算能量不受限，并且sink节点是固定的。

4) 假设节点i的通信半径为R_c(i)，节点j的通信半径为R_c(j)，节点i和节点j之间的距离为d_ij，那么节点i和节j能够直接通信的充要条件^[5]是R_c(i)≤d_ij∧R_c(j)≤d_ij。

2.2 基本概念

定义1  两个高性能节点之间的链接成为捷径^[6]。

定义2  高性能节点间的链接概率用p表示。

定义3  假设普通节点的通信半径为R_L，高性能节点的通信半径为R_H，在实验的过程中保证${R_{\rm{H}}} \gg {R_{\rm{L}}} $。

2.3 算法描述

算法是以轮数为单位，每一轮主要分为簇的划分以及簇头的选择，簇头的选择根据数据传输的可靠性；选择出来的簇头节点同时进行链路构建，包括候选捷径端点的确定以及捷径端点的确定；最后完成数据的通信过程。具体的流程如图 1所示。

1) 对监控区域进行随机撒点，主要分为两类传感器节点，具有高能量的传感器节点(High-energy sensor node, H-sensor)和具有低能量的传感器节点(Low-energy sensor node, L-sensor)。其中，高性能节点的个数应该大于等于簇头节点的数目，其余的是低能量的普通节点，这样做的好处就是尽可能地保证每个簇内都具有高性能节点。拥有高能量的传感器节点具有较大的通信半径R_H，拥有低能量的传感器节点具有较小的通信半径R_L。

2) 簇的建立阶段分为邻居发现阶段、控制数据广播以及网络配置。在邻居发现阶段，所有的传感器节点广播一个带有自己ID号的hello包，收到hello包的传感器节点会更新自己的邻居表和接收信号强度(Receive Signal Strength Indicator, RSSI)。控制数据广播，该算法使用泛洪的方法传输控制数据到基站，每个传感器节点的控制信息包括自身的ID号、剩余能量和它的邻居表数据。中继节点接收到数据包会继续广播直到数据包传输到基站为止。网络配置阶段，当基站收到网络中所有的传感器节点的控制包时，基站开始配置网络。配置广播，当基站完成网络配置，以泛洪的方式向所有的传感器节点广播网络配置，对子区域进行划分。每个传感器节点根据接收的消息确定要加入的簇。每个子区域的传感器节点构建单链路，并根据成簇的可靠性进行簇头节点的选举。

仿真的过程中，位于监控区域左下角位置的汇聚节点，根据距离汇聚节点的距离将监控区域划分为不同的环形等级，然后将每一层的面积平均化，得到每个簇的大小区域。规定距离基站越近的环形等级越低，分别为0, 1…, i，如图 2所示。环形等级level计算公式为：

$ level = i, i*{d_0} \le r \le (i + 1)*{d_0} $

(5)

其中：r表示的是环形的半径大小，d₀表示的是自由空间传播模型和多径衰减模型的临界距离，i表示的是环形等级的数值大小。

如图 3所示，在一个簇内有N个传感器节点，按照经典的PEGASIS(Power-Efficient Gathering in Sensor Information System)算法形成单链路，如果簇头节点C₄左边链路有m个传感器节点，那么C₄右边链路就有N－1－m个传感器节点。任何复杂的系统都可以通过并联与串联模块的组合来描述^[7]。如图 4可靠性模型(Reliability Block Diagram, RBD)所示，整个簇的数据传输可靠性R_cluster表示为：

$ {R_{{\rm{cluster}}}} = 1- (1- {R_{CH}})\{ 1- [1-\prod\limits_{i = 1}^m {(1-{R_{C{M_i}}}} )][(1-\prod\limits_{i = m + 1}^{N-1-m} {(1 - {R_{C{M_i}}}} )]\} $

(6)

其中：R_CH表示的是簇头节点的数据可靠性，R_CMi表示的是普通传感器节点的数据可靠性。

节点i的数据可靠性定义为：

$ {R_{C{M_i}}} = {E_{{\rm{re}}}}\left( i \right)/{E_{{\rm{init}}}}\left( i \right) $

(7)

其中：E_re(i)表示的是节点i的剩余能量，E_init(i)表示的是节点i的初始能量。

3) 确定簇头节点i的自适应搜索区域。

图 5描述了节点i的自适应搜索区域^[8]。假设所有节点都知道汇聚节点坐标为(0, 0)，过节点i和汇聚节点(sink节点)的直线为l，l的直线方程为y=mx+b。过点i，以直线l为中心的两条直线l₁和l₂分别为y₁=m₁x+b，y₂=m₂x+b，则直线l₁和l₂的夹角θ满足$\tan \;\theta = \left| {\frac{{{m_1}-{m_2}}}{{1 + {m_1}{m_2}}}} \right| $，夹角θ所包括的区域即为簇头节点i的搜索区域^[9]。位于汇聚节点附近的传感器节点，不仅要负责周围数据信息的采集，而且还要负责大量数据的处理和转发，导致能量消耗比较快^[10]。为此，本算法在确定搜索区域的时候，搜索角度θ如式(8) 所示：

$ \theta = \frac{{{d_{\max }} - {d_{{\rm{is}}}}}}{{{d_{\max }} - {d_{\min }}}}*{\theta _{{\rm{init}}}} $

(8)

其中：d_max表示的是头节点集合中距离基站的最远距离，d_is表示的是当前的簇头节点距离基站的距离，d_min表示的是簇头节点集合中距离基站的最近距离，θ_init表示的是距离基站最远的簇头的搜索角度。

本算法通过搜索角度控制簇头的搜索区域。距离基站最远的簇头节点的搜索区域为θ_init，其余簇头节点的搜索角度随着d_is的变化而变化，距离基站越近，簇头节点的搜索区域越大，则可以作为下一跳的节点的选择性就越多，从而避免个别节点点介数过高的情况，一定程度上缓解了“热点”问题的产生，延长了网络寿命。

根据文献[11]，无线传感器网络可以方便地表述为图G=〈V, E〉，其中，V代表图中顶点的集合，E代表图中边的集合，用G_d(a, b)表示节点a和节点b的最短距离，a∈V∧b∈V，σ_ab代表节点a和节点b之间的最短路径数目，a∈V∧b∈V，σ_ab(z)代表节点a到节点b经过节点z的路径数目，z∈V。节点z的点介数B_C(z)定义为：

$ {B_C}(z) = \sum\limits_{(a, b, z) \in V} {\frac{{{\sigma _{ab}}(z)}}{{{\sigma _{ab}}}}} $

(9)

4) 候选捷径端点的确定。

假设通过簇头节点i与在其通信范围内的簇头节点j的直线l₃为y=m₃x+b，l₃和l的夹角为β，β的计算公式为$\tan \beta = \left| {\frac{{m - {m_3}}}{{1 + m{m_3}}}} \right|$。那么如果节点j为所要确定的候选捷径端点, 需要满足β < θ/2。

如果该簇头在当前θ的搜索区域范围内没有发现候选捷径端点的存在，那么该簇头节点会继续扩大搜索范围，直至找到候选捷径端点。如果当θ达到360°时，该簇头仍然没有找到候选捷径端点，则选择距离该节点最近的簇头节点作为下一跳节点。如果该节点找不到离自己最近的簇头节点，那么会选择邻近区域的普通节点作为中继节点进行数据传输。

5) 捷径端点的确定。

捷径端点的确定如图 6流程所示，由于在部署传感器节点的时候采取的是随机撒点的方式，所以会导致选择出来的簇头节点不一定是H-sensor节点。如果该簇头节点i是L-sensor，则节点i选取离节点j距离最近的节点作为节点j的下一跳节点。如果是该簇头节点i是H-sensor节点，比较该节点的本轮剩余能量E_i和网络中簇头节点的平均剩余能量E_ave，E_ave的表达式如式(10) 所示:

$ {E_{{\rm{ave}}}} = \frac{1}{m}\sum\limits_{i = 1}^m {{E_{{\rm{res}}}}\left( i \right)} $

(10)

其中：m簇头节点的数目，E_res(i)表示的是节点i当前的剩余能量。

如果节点E_res(i)>E_ave，则节点i选择距离基站最近的候选捷径端点作为下一跳节点。如果E_res(i) < E_ave，根据节点i随机产生的0~1的随机Q及指定的捷径概率常数p，来判断是否将j作为节点i的下一跳节点。如果出现第一个节点使得节点i满足Q < p，则节点j为所要寻找的捷径端点。如果候选捷径端点集合中的所有节点都不满足Q < p，则会重复上步操作，继续产生随机数，直至找到第一个节点j使得满足Q < p。

图 7是HASWNM算法生成的拓扑结构图。传感器节点主要分为4类：当选为簇头的高性能节点；作为簇成员的高性能节点；当选为簇头的低性能节点；作为簇成员的低性能节点。簇间的通信采用了大量的捷径链路。每个簇头在中继节点的选择方法上呈现出差异性。

6) 数据传输阶段。

当基站接收到所有簇头传送过来的数据包时，即完成了一轮的通信。进入下一轮的数据采集。

2.4 算法复杂度分析

假设监控区域内有N个传感器节点，其中有m个簇头，那么普通节点的个数为N－m，每个簇内的节点个数平均为N/m。簇的建立阶段分为邻居发现阶段、控制数据广播以及网络配置。在邻居发现阶段，所有的传感器节点广播一个带有自己ID号的hello包，共有N个数据包。在控制数据广播阶段，每个传感器节点的控制信息包括自身的ID号、剩余能量和它的邻居表数据通过泛洪的方式传送给基站，共有N个数据包。基站收到所有的数据包信息之后，在网络配置阶段，会以泛洪的方式发送一个数据包，使得网络节点了解网络整体的情况。

在簇内拓扑的构建过程中，簇内节点之间需要交互的数据包个数为$m\left[{\left( {N/m-1} \right) + \left( {N/m-2} \right) + \cdots + 2} \right] = m\left( {\frac{{{N^2} -mN}}{{2{m^2}}} -1} \right) $，簇间拓扑构建的过程中，每个簇头同时构建到基站的链路，基站广播簇头节点的平均能量，需要泛洪发送一个数据包。最好的情况，每个簇头不需要进行中继节点的选择，直接与基站通信，簇头间不需要交互信息；最坏的情况，每个簇头要经过所有的中继簇头节点才能到达基站，此时需要交互的数据包个数为$m\left[{\left( {m-1} \right) + \left( {m-2} \right) + \cdots + 2} \right] = m\left[{\frac{{m\left( {m-1} \right)}}{2}-1} \right] $。

综上所述，算法复杂度最好情况，需要交互数据包个数为$m\left( {\frac{{{N^2}-mN}}{{2{m^2}}}-1} \right) + 2N + 2 $，最坏的情况下需要交互数据包的个数为$m\left( {\frac{{{N^2}- mN}}{{2{m^2}}}- 1} \right) + m\left[{\frac{{m\left( {m-1} \right)}}{2}-1} \right] + 2N + 2 $。因此，算法复杂度为O(N²)。

3 仿真结果与分析 3.1 实验场景设置

根据参考文献[3]，在实验仿真时，簇数K取值按照K=πR²/r²。其中，R表示的是高性能节点的通信半径，r表示的是低性能节点的通信半径。

实验验证借助Matlab平台，仿真实验的具体参数设置如表 1所示。

仿真的大致流程为：

1) 随机部署1 000个传感器节点，初始化网络，每个网络节点坐标为(x_i, y_i)，ID号为id_i，并进行簇的划分。每个簇内按照数据传输的可靠性选取出簇头节点，并对簇头节点打上标记flag。

2) 被打上标记的簇头节点同时进行中继节点的选择以及数据传输。对于不同簇头节点的搜索区域与距离基站的位置有关，并且满足$\theta = \frac{{{d_{\max }}-{d_{{\rm{is}}}}}}{{{d_{\max }}-{d_{\min }}}}*{\theta _{{\rm{init}}}} $。其中，$ {d_{{\rm{is}}}} = \sqrt {x_i^2 + y_i^2} $。比较簇头节点与所有簇头节点剩余能量的平均值，如果该节点为H-sensor，并且E_res(i)>E_ave，那么选择候选捷径端点集合中离基站最近的节点作为下一跳节点；如果该节点为H-sensor，并且E_res(i) < E_ave，那么会随机选择候选捷径端点集合中任一节点；如果该簇头为L-sensor，则选择距离自己最近的簇头节点作为下一跳节点。

3) 当基站收到了所有簇头的数据包后，一轮传输结束，进入到下一轮数据收集的准备阶段。

3.2 仿真结果分析

实验1 能量消耗和高性能节点数目关系实验。

从图 8中可以看出，HASWNM只是对簇头节点寻找相应的捷径端点，当网络中的高性能节点的数目不是很多的时候，由于高性能节点分布不均匀，可能会导致能量消耗比较快一点。但是随着高性能传感器节点个数的增加，基本能够保持每个簇内都有高性能节点，这样导致能量消耗比较低，所以能耗基本呈现出一个下降的趋势。DASM(Directed Angulation towards the Sink node Model)中，高性能节点在固定的搜索区域内搜索捷径端点，TSWN(Tree-based Small World Network)将自适应搜索区域内的所有高性能节点加入到捷径的创建中，当有多个高性能节点时，随机选择加入捷径，因此，故在初始时，两种模型的高性能节点利用率相对CSWN(topology Control based on Small World Network)、HASWNM高，其能耗会更加均衡，网络能量消耗相对较低。

实验2 网络生命周期和高性能节点数目关系实验。

从图 9可以看出，网络生命周期与能量消耗呈现出一定的关系，在高性能节点个数不是很多的时候，相比别的算法，HASWNM算法能耗要更高一些，导致其网络生命周期比较短，随着高性能节点个数的增加，HASWNM在网络生命周期方面表现出一定的优越性。

实验3 小世界特性和高性能节点数目关系实验。

本文定义C(0) 表示的是仅由普通节点构成的网络聚类系数大小，C(H)表示的是由H个高性能节点以及一些普通的传感器节点构成的网络聚类系数大小，L(0) 表示的是仅由普通节点构成的网络平均路径长度大小，L(H)表示的是由H个高性能节点以及一些普通的传感器节点构成的网络平均路径长度大小。

从图 10中可以看出，随着高性能节点个数的增加，L(H)/L(0) 呈下降的趋势，当高性能的节点个数达到100时，平均路径长度减少了72%左右。当高性能节点个数达到100以后，L(H)/L(0) 基本维持不变，C(H)/C(0) 也基本处于不变的状态。采用本实验的参数设置时，最佳的高性能节点个数为100个时，使得网络的平均路径长度最小。

实验4  网络剩余能量和仿真轮数的关系。

当实验仿真时，高性能的节点个数设置为100，那么低性能节点的个数就为900个。根据每轮能量消耗，可以估算出不同算法的最大工作轮数不超过700，因此，算法最大仿真周期设置为700轮。

图 11表示的节点总的剩余能量和仿真轮数的关系。通过前面图 8分析可知，高性能节点的个数为100时，HASWNM算法每轮的平均能耗是最低的。通过图 11可以直观地看出，节点总的剩余能量是最多的，其次是CSWN、TSWN，最差的是DASM算法。实验8和实验11的结果具有很强的关联性。

实验5 不同算法网络平均周期比较实验。

图 12表示的是不同算法的网络平均生命周期。从图中可以看出，HASWNM算法在第一个节点死亡、10%节点死亡以及50%节点死亡时，都具有最大的仿真轮数。第一个节点死亡时，HASWNM算法相比较CSWN延迟了6%，相比较TSWN延迟了6%，相比较DASM延迟了29%。10%节点死亡时，HASWNM算法相比较CSWN延迟了18%，相比较TSWN延迟了30%，相比较DASM延迟了63%。50%节点死亡时，HASWNM算法相比较CSWN延迟了19%，相比较TSWN延迟了23%，相比较DASM延迟了32%。全部节点死亡时，HASWNM算法相比较CSWN延迟了4%，相比较TSWN延迟了10%，相比较DASM延迟了19%。WSN生命周期的长短主要取决于网络的能耗情况，通过图 8知道，由于节点搜索区域以及捷径端点的选择规则的不同，导致当高性能节点数为100的时候，每一轮的能量消耗从小到大依次为：HASWNM、CSWN、TSWN、DASM。

4 结语

本文提出了一种基于小世界网络模型的无线传感器网络层次型路由算法，小世界模型的构造是通过添加高性能节点以及在选择出来的簇头节点间添加捷径的方法实现的。由于无线传感器的能耗主要集中在数据的发送阶段，所以只有能量高于所有簇头平均能量的簇头节点，才会选择候选捷径端点中距离基站最近的簇头作为下一跳节点，否则，会随机选择一个候选捷径端点作为下一跳节点。这样做的好处是节省了一定的能量，避免了个别节点能量消耗过快。簇头根据距离基站的位置，控制搜索区域的角度，避免了基站周围个别节点点介数过高的问题，有效地延长了网络的生命周期。通过仿真验证，基于小世界网络模型的无线传感器网络层次型算法使得网络具有大的聚类系数和小的平均路径长度，同时网络能耗相比较也比较低。本文提出的算法主要考虑节点的能耗，后续可以考虑从覆盖率、QoS以及有利于算法的扩展性等因素入手，展开进一步研究。