具备小世界网络拓扑特性的无线传感器网络鲁棒性分析

徐 野，袁邱伟

(沈阳理工大学 信息科学与工程学院，沈阳 110159)



具备小世界网络拓扑特性的无线传感器网络鲁棒性分析

徐 野，袁邱伟

(沈阳理工大学 信息科学与工程学院，沈阳 110159)

无线传感器网络(WSN)传感器节点数量多且分布广，将复杂网络理论引入无线传感器网络(WSN),对分析网络拓扑结构、发现其中隐藏的规律以及提高网络性能具有十分重要的意义。根据LEACH分簇算法，通过将网络中介数较小的链路删除，构建具备小世界网络特性的无线传感器网络。提出基于网络负载和冗余的传感器网络连通性的测度，在此基础上给出无线传感器网络鲁棒性分析的方法。针对两种攻击方法，随机攻击和蓄意攻击，对基于小世界网络模型的无线传感器网络鲁棒性能进行分析。仿真结果表明，减少网络负载增加网络冗余利于传感器网络鲁棒性的增强。

复杂网络；无线传感器网络；网络负载；网络冗余；鲁棒分析

无线传感器网络(wireless sensor network，WSN)是由部署在监测区域内大量的、廉价的、微型的传感器组成，通过无线通信方式形成的一个多跳的自组织的网络系统[1]。通过无线传感器网络，人们可以感知客观世界，丰富和扩展了现有的网络功能以及人们认识客观世界的能力。无线传感器网络由传感器节点、汇聚节点和管理节点组成。在无线传感器网络中，传感器节点将监测收集的数据经过多条路径传递到汇聚节点，之后通过互联网或卫星送达管理节点。通常无线传感器网络所处的环境恶劣且节点众多资源受限，传感器节点很容易出现故障，导致整个网络陷入瘫痪状态，因此对无线传感器网络鲁棒性的研究对于传感器网络的稳定高效运行显得尤为重要。

复杂网络并非指具体的网络，具体的网络包括通讯网络、Internet、交通网络等，复杂网络是对具体网络的抽象，研究网络的拓扑结构形成机制及演化规律，描述复杂网络内部元素之间相互作用和关系的理论。复杂网络有无标度网络、小世界网络、随机图、规则网络等多种类型，其中最为典型的复杂网络为小世界网络[2]。Watts在1998年提出了小世界网络模型，具有平均路径长度小和聚类系数大的特点[3]，是一种从规则网络向随机网络的过渡的网络。网络具有平均路径长度小的特性，节点之间的数据传输通过较少的跳数就可完成，利于网络路由机制的维护，同时降低网络节点能量的消耗；网络中节点的连通性可以用聚类系数来体现，小世界网络聚类系数大的特点反映网络内部协作性高，降低网络通信开销，利于网络的稳定运行。

1 WSN鲁棒性分析

小世界现象作为复杂网络的一个重要特征，存在于网络结构中，相关研究人员对无线传感器网络是否存在小世界现象进行了大量的研究，发现无线传感器网络也存在小世界现象[4]。在现实应用中，根据小世界复杂网络理论构建无线传感器网络，将会提高无线传感器网络的鲁棒性，改善网络的整体性能。

1.1 WSN鲁棒性

鲁棒性[5](robustness)是指网络节点移走后，网络中的绝大部分节点仍然保持连通，网络的结构和性能能够维持基本稳定的能力。在大规模无线传感器网络中，单个节点的失效是不可避免的，即使寻找到了网络中的失效节点也无能为力，这就需要构建鲁棒性强的无线传感器网络。无线传感器网络只有保证采集数据的覆盖，才能确保数据结果的真实可靠，提高网络的整体效率。为了更准确、客观地分析传感器网络的鲁棒性，提出传感器网络鲁棒性分析的新方法，充分考虑传感器节点的度量特征、网络的连通性、攻击方式等相关因素对传感器网络鲁棒性的影响。

1.2 节点的度和度分布

无线传感器网络节点的度为该节点与其他节点连接的数目，在传感器网络中，大部分节点地位性能相同，节点的度趋于一致。同时存在少数节点如簇头节点、汇聚节点，在节点能量、通信能力、网络优先级等方面具有一定的优势，因此这些高性能的节点具有较大的节点度数。正常情况下，传感器网络中的节点不具有相同的度，常用度分布函数P(k)来描述度在网络中的分布情况。计算公式为

(1)

式中，Ni(k)为度为k的节点数，N为节点总数。传感器网络中，每个节点的度数最小为0，最大为N-1 ，节点的度分布相加为1，即

(2)

在无线传感器网络中各节点的不平等性决定网络中存在小世界现象，网络中节点度数较大的节点拥有较强网络性能，当这些节点遭受到攻击或干扰时，网络会出现较大的异常，网络的整体性能下降。

1.3 节点的介数与网络负载

介数作为网络的全局统计量，在无线传感器网络中反映节点或边的重要性。如果传感器节点之间有B条不同的最短路径，其中有b条路径经过节点i在节点对的介数为b/B，节点i对所有节点对的介数之和称为节点i的介数[6]。节点i的介数Bi的计算公式如下：

(3)

式中,njk代表节点j与节点k之间的最短路径的数量；njk(i)代表在节点j与k之间的最短路径经过节点i的数量。研究结果表明，介数可以较好地反映节点在网络中的重要性，可以此来研究无线传感器网络的鲁棒性。

传感器网络中节点是沿着最短路径进行信息交换传递，可将节点的负载定义为该节点的介数，它反映了网络中通过节点的最短路径的数目。定义节点i的容量(可承载的最大负荷)正比于其初始负载L[7]，公式如下：

C=(1+θ)L

(4)

式中θ为网络冗余，其取值范围为[0，1]。在无线传感器网络的应用中，通常都具有大量节点，而由于制造成本等问题,很难保证在使用过程中每一个节点的可靠性。如果网络中的某一个节点遭遇故障，使得最短的路径分布产生影响，进而导致使得网络上的每个节点上的负荷也产生影响。如果节点中的负荷无法承受自己最大的容量时，网络就发生了故障，并引起所有的节点重新分配网络中的负荷。

1.4 网络的连通性

连通子图看成是一个个小的集团组合而成，小集团定义为从一条随机边的一端出发搜索，通过这个端点能直接到达的所有节点的集合即为一个集团。节点收到数会向周围通信节点发出访问信息，邻居节点收到信息后根据一定算法决定自己是否变为活动节点，同时向其他节点发出信息告知自身为活动节点，通过循环的节点信息发送确认，建立起通信集团。图1为传感器网络连通子图形成示意图。

图1 传感器网络连通子图形成示意图

令H1(x)为这些集团分布的生成函数，通过一条边去访问某个节点时，定义与这个节点相连的其他边的数目的分布生成函数为

(5)

式中qk表示与访问节点相连的其他边数目的归一化的概率分布。

(6)

式中：[H1(x)]k表示由qk所确定的k条边相连的k个集团的大小之和的分布函数；x表示与随机选择的边相连的一个节点；pk定义为与节点直接相连的边的分布。每条边的另一端连着其他的集团，这些集团的大小由函数H1(x)生成，任意取一个节点所在集团的大小的生成函数为

(7)

(8)

(9)

式中：r对应于网络的一个分布指数，取值范围为2

1.5 攻击方式

在传感器网络中，鲁棒性是衡量当网络中部分节点失效后的网络连通状况的性能指标。一般针对传感器网络进行的节点攻击方式主要有以下两种：随机攻击方式和蓄意攻击方式。随机攻击方式，即完全随机地去除网络中的一部分节点后，网络连通度的变化；蓄意攻击方式，一般是有目标地去除一些网络中的关键节点,如度大的节点，通信流量较大的节点等。

2 小世界特性无线传感器网络的构建

3 仿真与性能分析

图2 具备小世界网络特性的无线传感器网络的部分拓扑模型

3.1 无线传感器网络在不同攻击方式下鲁棒性分析

在θ=0、ω=0(网络空负载)情况下，取τ=0、τ=1观察具有小世界网络特性的无线传感器网络在确定攻击和随机攻击下所表现的鲁棒性，如图3所示。

图3 不同攻击方式下传感器网络鲁棒性能对比

由图3可知，具有小世界网络特性的无线传感器网络面对随机性网络攻击表现出很强的鲁棒性即使攻击点数达到500点时，G仍在0.3以上，从而保证无线传感器网络的覆盖率。在面对蓄意攻击方式时，传感器网络模型也表现出高的鲁棒性，在攻击节点接近总点数的一半时，G保持在0.3，表明即使有目的攻击传感器网络中比较重要的点时，具有小世界网络特性的无线传感器网络仍能保证覆盖率在0.3以上，确保网络稳定高效的运行。

3.2 传感器网络冗余对网络鲁棒性的分析

在上面分析的基础上，通过改变网络冗余，观察网络鲁棒性的变化，上面的情形是在θ=0、ω=0(网络空负载)情况下，当ω=0不变，网络冗余θ变为1时，研究传感器网络在不同攻击方式下所表现出的鲁棒性，如图4所示。

图4 增加网络冗余传感器网络鲁棒性能对比

由图4可知，无论是随机攻击方式还是蓄意攻击方式，网络冗余θ为1时，传感器网络的鲁棒性相比于原来网络冗余θ为0时鲁棒性能有所提高，表现为线段2、4相较于线段1、3普遍右移。同样的攻击方式，网络冗余的增加，处理数据的能力增强，传感器网络的鲁棒性能有所提高，网络整体呈现较强的鲁棒性。

3.3 节点负载对网络鲁棒性的分析

现实中，无线传感器网络在工作中，需要对接受的数据进行分析处理，同时将处理后的数据发送到下一节点，在此过程中网络是有负载的。为进一步真实反映具有小世界特性的无线传感器网络的鲁棒性能，网络冗余θ为1不变、ω=1(网络满载)情况下，真实的传感器网络在不同攻击方式下表现出的鲁棒性，如图5所示。

图5 增加节点负载传感器网络鲁棒性能对比

由图5可知，当传感器网络工作时，对传感器网络进行随机攻击和蓄意攻击，网络所表现出的鲁棒性比网络空载时鲁棒性低，在这种情况下无论采取何种方式的攻击线段3、4相较于线段1、2普遍左移，意味着在攻击节点数比原来大大减少的情况下，传感器网络面临崩溃，网络所表现出的鲁棒性大大降低。由以上仿真结果可知，传感器网络在攻击模式确定的情况下，提高网络冗余、降低网络负载可以增强传感器网络鲁棒特性，延长网络生存周期。表1为网络负载、网络冗余对传感器网络鲁棒性能的影响。

表1 网络负载、网络冗余对传感器网络鲁棒性能的影响

由表1可知，相同的攻击方式以及网络负载(τ=0、w=0),网络冗余增加可以增强传感器网络的鲁棒特性；相同的攻击方以及网络冗余(τ=0、θ=1)，降低网络负载同样可以提高传感器网络的鲁棒特性。

4 结论

将复杂网络理论引入无线传感器网络，研究具有小世界特性的无线传感器网络鲁棒特性，给出无线传感器网络连通性的新测度和无线传感器网络鲁棒性分析的新方法。仿真结果表明：具有小世界特性的无线传感器网络面对随机攻击和蓄意攻击两种网络攻击方式表现出较强鲁棒性，能够很好保障传感器网络稳定高效地运行。对网络冗余和负载对传感器网络鲁棒性影响的研究中发现，提高网络冗余、降低网络负载可以提高传感器网络的鲁棒特性，为现实中传感器网络的合理构建提供了新的思路。

[1]孙利民,李建中,陈渝.无线传感器网络[M].北京:清华大学出版社,2005:3-4.

[2]方锦清,汪小帆,郑志刚.一门崭新的交叉科学:网络科学[J].物理学进展,2007,27 (3):229-343.

[3]Watts D J.Collective dynamics of “small-world” networks[J].Nature,1998,393 (6684):440-442.

[4]HELMY A.Small worlds in wireless networks[J].IEEE Communication Letters,2003,7 (10):490-492.

[5]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006:29-33.

[6]Rahul C Shah,Jan M Rabaey.Energy Aware Routing for Low Energy AdHoc Sensor Networks[J].Proe IEEE Wireless Communications and Networking Conference(WCNC),March,2002,l (3):17-21.

[7]Motter A E,Nishikawa T,Lai Y C.Cascade-based attacks on complex networks[J].Physical Review E,2002,66 (2):1-4.

[8]Heinzelman W R,Chandrakasan A,Blakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaiv International Conference on System Sciences.IEEE Computer Society,San Francisco,2000:3005-2014.

(责任编辑：马金发)

Research of Wireless Sensor Network Fault Detection

XU Ye,YUAN Qiuwei

(Shenyang Ligong University,Shenyang 110159,China)

Wireless sensor network is characterized by numerous nodes and wide distribution.The application of complex network theory to WSN is very significant to analyze network topology,find hidden rule and improve network performance of WSN.According to LEACH clustering algorithm,a wireless sensor network is built，which has a small-world network characteristics,and the network construction may remove smaller betweenness links.A new measure of wireless sensor network robustness is proposed.The new method to analyze the robustness of wireless sensor network on the basis of the above.For two different damages,random attacks and deliberate attacks,the robustness of wireless sensor networks is studied by the small-world model.Simulation results indicate that network load reducing increases the robustness of wireless sensor networks in favor of enhanced redundancy.

complex network;wireless sensor network;robustness analysis;network redundant;robustness analysis

2015-06-29

国家自然科学基金资助项目(61373159)；沈阳市科技应用基础研究计划资助项目(F13-316-1-22)

徐野(1976—)，男，教授，博士，研究方向：复杂互联系统与大规模网络。

1003-1251(2016)04-0007-05

TP393

A