基于复杂网络的无线传感器网络能量脆弱性分析*

吴 蒋， 王 冬

(1.中南大学 软件学院,湖南 长沙 410083; 2.琼州学院 电子信息工程学院,海南 三亚 572022)

0 引 言

由于无线传感器网络(WSNs)中的传感器节点能量严重受限而且部署后难以回收，因而,针对无线传感器网络的能量效率的研究一直是该领域的热点和难点。无线传感器网络链路中，诸如：突发大流量、自然灾害、人为破坏、节点能量失效等突发事件可能会导致某条链路断开，从而影响网络通信的全局效率。不同节点能量失效引起全局网络效率变化的大小称为节点的脆弱性。分析无线传感网的网络拓扑性并定量计算各个节点的脆弱性以采取相应对策预防网络瘫痪，对保障整个无线传感器网络的通信畅通有重要意义。

国内外学者利用复杂网络理论，已对无线传感器网络做过大量研究。陈力军等人[1]借助于复杂网络理论，提出了一种基于随机行走的无线传感器网络簇间拓扑演化模型。该模型对完善无线传感器网络的容错机制起到了积极的作用，可防止节点出现因能量的耗尽而失效或链路因网络的入侵而失灵的现象。张成才等人[2]对无线传感器网络的联通性展开研究，结果表明增加通信半径则可以迅速地使网络联通。Guidoni D L等人[3]曾用小世界网络特性应用于无线传感网络的研究。以上学者侧重于研究无线传感器网络的整体效率变化情况，缺乏对每个节点脆弱性的定量分析。笔者在描述复杂网络理论的基础上，确定定量化评价节点脆弱性的指标，并以文献[4]网络为例，使用Space D法构造其拓扑网络，并用Matlab分析节点度、平均路径长度、聚类系数等指标和分布规律，最后定量计算各个节点能量消耗的脆弱性，以确定其中的关键节点，为维护和优化提供科学依据。

1 无线传感器网络节点能量脆弱性分析

1.1 复杂网络的统计参数

1998年，Watts D J等人[5]提出著名的小世界网络概念，1999 年，Barabbsi A L等人提出无标度网络的概念。可以做这样一个假设，就是将系统内部的各个元素的关系作为连接，把元素视为节点，那么系统就形成了一个网络，例如：大量随机节点通过簇头进行通信而组成的网络称之为无线传感器网络；神经网络的形成被看作是大量神经细胞通过神经纤维相互连接的结果；计算机网络被认为是计算机通过各种通信介质相互连接形成的网络，如光缆、双绞线、同轴电缆等；类似的还有人际关系网络、水利枢纽网络、火车轨道网络、公路交通网络等[6，7]。复杂网络的研究思路主要是强调系统的结构，值得注意的是从结构角度来分析系统的功能，区别在于这些抽象的真实网络拓扑结构性质和以往研究的网络不同，节点众多是其特点。关于复杂网络结构特点所描述的统计特征有很多,例如：最短路径、介数、平均度、聚类系数、平均距离、相关系数、连通片分布等，其中，有3个统计特征最尤为重要，即度、聚类系数和平均路径长度，下面就对此做简要的说明。

1.1.1 节点度与度分布

图论中与i节点连接的其他节点的数目ki，也可定义为i节点的度，从直觉上，一个节点的度越大就表示该节点在某种程度上越重要。正常情况下，大部分的节点都不具有相同的度，常用分布函数p(k)来描述度在网络中的分布情况，p(k)表示一个随机选定节点的度刚好是k的概率。节点度的分布特征往往被视为网络的重要几何性质，规则性网络中各个节点的度值是一样的，与Delta分布相吻合，随机网络的度分布与Poisson分布相类似，绝大部分的现实网络存在幂律形式的度分布，称之为无标度网络[8～10]，同时还有很多网络的度分布局限于指数分布。

1.1.2 聚类系数

很显然，假设网络G中一个节点i有ei条边与另外ki个节点连接，该ki个节点就称为节点i的邻居。显然，该ki个节点间最多可能有ki(ki-1)/2条边，ki个节点之间实际存在的边数Ei与总的可能边数的比值定义为节点i的聚类系数Ci，网络中所有节点i的聚类系数的平均值就是网络的聚类系数，用C表示，即

(1)

(2)

1.1.3 平均路径长度

网络G中2个节点i和j之间的距离dij定义为连接这2个节点的最短路径的边数。对于一个无向网络，定义平均路径长度L为网络中节点对之间距离dij的平均值

(3)

式中N为网络节点数。网络的平均路径长度用来衡量网络节点间的离散程度，也被称为网络的特征路径长度。研究表明，尽管许多实际网络的节点数巨大，但网络的平均路径长度L相对于N来说却很小，这种现象称之为“小世界效应[5]”。

1.2 无线传感器网络构建

根据文献[1]，假设所有簇头的最大通信半径可控，各个水源地入口相邻的簇头都在最大通信半径内，Space D拓扑结构模型即把簇头视为节点，若某一线路上的2个簇头是相邻的，它们之间就有通信链路，如图1所示。

图1 Space D网络构建方法

在无线传感器网络中，簇头和通信链路是基本的组成元素，链路连接着簇头节点相互感知和转发数据，因此，无线传感器网络可看成由链路和簇头所构成的复杂网络。这里可以定义为:无线传感器网络中的节点代表通信链路中的簇头，边代表各簇头之间的链路,这样，由很多的边和点组成的网络就构成了无线传感器网络的基本框架。

1.3 无线传感器网络脆弱性分析

脆弱性可以解释为：受事件影响而使服务水平降低的敏感系数。无线传感器网络的脆弱性则可定义为不同簇头节点在能量耗尽而影响无线传感器网络全局效率的大小。节点能量消耗与通信量大小有关，而通信量的大小可随路由选择的随机性有莫大的关系。因此，对于无线传感器网络，研究随机失效节点的脆弱性有助于识别脆弱环节并采取相应对策以预防整个网络瘫痪的发生。笔者通过计算文献[1]网络效率，来描述其脆弱性。网络效率E是用于度量网络中节点交换信息的效率。定义G的平均网络效率之前，需要计算任意2点间的最短路径{dij}。设定顶点i和j之间的效率为最短路径的倒数eij=1/dij，当i和j之间没有边连接时，dij=+∞，eij=0，这样，G的平均网络效率可以定义为

(4)

当E值很大时，表明网络效率很高且连通性很好。当节点i能量耗尽失效后，网络遭到破坏，网络效率也受到影响，不同节点失效时引起网络效率的变化大小不同，即脆弱性不同，则第i个节点的脆弱性ΔE定义为

(5)

2 文献[4]网络实证研究

2.1 文献[4]网络结构

本文用Space D方法对三亚半岭水库水质监控网络进行拓扑建模，拓扑后网络如图2所示。

图2 三亚半岭水库水质监控网络拓扑结构图

2.2 文献[4]网络的统计特性与分析

本文对三亚半岭水库的各个监测点采用的是环形的节点布置方式，相邻节点的数据链路唯一，某节点一旦失效，其数据接收为0或该节点效率逐渐降低趋向于0。对文献[4]网络分别计算其网络节点数、边数、平均度、平均路径长度和聚类系数，结果见表1。

表1 特征指标值

环形节点布置方式方便于计算，从表1可知，一共布置了36个监测节点，36条连接边，每个节点与2个相邻节点直接连接，平均链路长度为9.25，并拥有较小的聚类系数，同时有较小的链路长度。根据拓扑图，计算得到其平均聚类系数为0。

2.3 节点能量耗尽时网络的脆弱性

对文献[4]网络的36个节点进行电池更换，该电池能量为即将耗尽的电池，并用式(4)计算更换电池后的网络效率。经计算，网络正常情况下的网络效率为36.4 %。在一一更换电池后，网络效率的变化如图3所示。

图3 更换电池后的网络效率

由图3可知，面对大面积因能量问题导致失效节点的增多，整个网络效率受到影响较大。当节点数剩余36 %时，网络效率已接近于0。为避免能量耗尽导致网络瘫痪，应对网络中的节点进行有意识的保护，包括关键节点的保护。

表2中列出脆弱性最高的4个点。数据显示，这4个点分别位于水流变化比较大的区域，水质一旦发生变化，采集节点将持续工作，对能量的消耗也就相对较大。一旦这些节点失效，整个网络的效率降低超过25 %，表中列出的节点度都一致，均为2。因此，该网络对节点度数的依赖可以忽略不计，鉴于将来对无线传感器网络的设计在通信链路可控的前提下，尽量对簇头节点的度数保持一致，这样在对网络维护时重点对脆弱性高的节点进行优化保护而不用对全局节点进行高强度保护，可节约成本。

表2 网络节点失效后指标值

3 结 论

1)本文针对文献[4]网络脆弱性的定量分析方法，基于复杂网络理论，从节点度、平均路径长度等方面对该网络的拓扑特性进行分析，提出基于网络效率的节点脆弱性计算方法。案例研究结果表明：水流变化比较大的区域，水质一旦发生变化，采集节点将持续工作，对能量的消耗也就

相对较大，表2中所列的节点为该网络脆弱性最高的节点。

2)无线传感器网络脆弱性分析能够解决无线传感器网络中普遍存在负载不均衡和能量优化等问题提供理论依据[12]。在随机播撒节点组成的自组织网络中，尤其注重网络脆弱性分析，找到那些负载不均衡的节点，优化脆弱性高的节点，从而实现整个网络的拓扑优化。

3) 运用复杂网络理论对无线传感器网络的脆弱性进行分析，当网络正常运行时，其网络效率是最高的。面对突然失效节点时，不同节点失效的概率不同。如何快速的找到这些失效节点，进行网络重新优化，是保证网络通畅的前提。

参考文献:

[1] 陈力军,刘 明,陈道蓄,等.基于随机行走的无线传感器网络簇间拓扑演化[J].计算机学报，2009，32(1):71-75.

[2] 张成才,齐小刚.基于复杂网络理论的无线传感器网络特征度量分析[J].计算机科学,2010，37(11):44-46.

[3] Guidoni D L,Mini R A F,Loureiro A A F.Creating small-world models in wireless sensor networks[C]∥IEEE 19th International Symposium on Personal,Indoor and Mobile Radio Communications,2008:1-6.

[4] 吴 蒋,任崇勋.基于Zig Bee技术的饮用水水源地水质远程监控系统[J].东北农业大学学报,2010,41(10):120-123.

[5] Watts D J,Strogatz S H.Collective dynamic of“small-world”networks[J].Nature,1998,393(6684):440-442.

[6] Albert R,Barabsi A L.Statistical mechanics of complex network[J].Review of Modern Physics,2002,74:47-97.

[7] Newman M E J.The structure and function of complex network-s[J].SIAM Review,2003,45:167-256.

[8] Ablert R,Barabasi A L.Statistical mechanics of complex network-s[J].Reviews of Modern Physics,2002,74(1):47-97.

[9] Dorogovtsev S N,Mendes J F F.Evolution of networks [EB/OL].[2007—10—27]. http://arxiv.org/abs/cond-mat/0106144v2.

[10] Strogatz S H. Exploring complex network [J].Nature,2001,410(3):268-276.

[11] Latora Vito,Marchiori Massimo.How the science of complex networks can help developing strategies against terrorism[J].Chaos Soltons and Fractals,2004,20(1):69-75.

[12] 雷 磊,薛小龙,周进华,等.实现节点负载均衡的无线传感网能量高效分簇方法[J].应用科学学报,2010,28(6):552-554.