基于复杂网络理论的WSN 拓扑控制与安全维护

孙懋珩，郑 煜，周 轩

（1.同济大学 电子与信息工程学院，上海201804；2.华东理工大学 信息科学与工程学院，上海200237）

复杂网络普遍存在于大量真实网络中，如计算机互联网、科学家合作网、产品生产关系网和电力网络等［1］.复杂网络具有小世界特性和无标度特性.小世界的特征是具有小的平均路径长度和大的集聚系数.最近相关的研究表明，某些异质无线传感器网络同样表现出复杂网络才具有的小世界现象.Helmy等学者通过在无线传感器网络中引入逻辑链路，形成具有小世界特性的无线网络，验证了一般适用于关系网络的复杂网络模型，同样适用于具有空间属性的无线网络［2－4］.这为笔者构建具有复杂网络特性的无线传感器网络拓扑结构提供了可行性的依据.

回顾前人提出的多种WSN（wireless sensor network，无线传感器网络）拓扑控制方法，文献［5］提出一种分布式拓扑控制方案R ＆ M，它基于转播区域和闭包概念，通过计算转播区域和衡量转播代价，以低功率连通网络.然而，该算法所产生拓扑的连通冗余度偏高，会削弱上层协议的运行效率.Li等人提出一种基于本地最小生成树结构的拓扑控制算法LMST［6］，全局调整本地独立构建的最小功率生成树，以获得双连通的拓扑，具有较好的能量有效性.但其链路冗余度低，不利于路径失效恢复，维护困难.Andy等提出了一种节点度部分有界和满足能量有效性的本地化算法PLA［7］，构建的拓扑图记为NGr（V）（0＜r＜1）.其功率扩展因子在r取值于某个范围内时是有界的（即部分有界），最大节点度也给出了一个上界.该算法虽然实现了功率限制与网络连通性的折中，但并未考虑到网络的全局容量问题.H.A.James等人应用小世界网络模型研究无线传感器网络的网络覆盖、容错和传感器网络的寿命问题［8］.结果表明，通过在传感器节点之间添加少数随机连接，可以大大减少传感器网络的平均路径长度和网络中出现的孤立簇的数目，从而提高WSN 的整体覆盖效果和寿命.文献［9］同样借助NIMS（networked info－mechanical system）基础设施，在无线传感器网络中以有线的形式添加长程连接，构成一种混合的传感器网络.这种WSN 同样显示出小世界特性，添加的长程连接作为网络捷径，能够显著减少整个网络的平均跳数，从而减少每个节点的能量消耗.然而，文献［8－9］都是在假设整个网络的节点是均匀分布的前提下实现的，没有考虑到实际中的障碍、噪声等环境因素而导致的节点分布不均匀情况.文献［10］考虑到这种情况，先将节点分布不均匀的WSN 分簇，再在簇结构上添加捷径.笔者在前人的研究基础上，提出了一种拓扑控制方法.该方法具有以下特点：①适用于节点分布不均匀的WSN；②通过理论推导，得到了复杂网络参数与WSN 网络容量的关系式，算法以提高网络容量为目的；③拓扑控制通过删除冗余边及添加长程边实现.

通过运用复杂网络理论指导WSN 拓扑控制，发现越具有复杂网络小世界特性的WSN，网络容量越大.在此结论基础上，进一步研究具备小世界特性的WSN 拓扑结构与WSN 故障传播的关系，引入复杂网络的病毒传播模型来指导具备小世界特性的WSN 的维护，提出一种WSN 病毒传播控制方法，提高WSN 的抗毁性.

1 WSN 网络模型及相关定义

1.1 WSN 网络模型拓扑参数分析

本文中的无线传感器网络平均度、平均路径长度、积聚系数、平均积聚系数、节点介数等网络参数概念及性质，与参考文献［11－12］中的定义保持一致.

1.2 WSN 网络模型的优化目标分析

现以WSN 网络有效容量作为网络拓扑控制的目标函数，经过理论推导，得到WSN 网络的总容量、有效容量与WSN 拓扑参数的关系.

定理 设定1个WSN 网络，其总节点数为N，单个节点的最大节点容量为A0，网络的平均节点度数为d，平均路径长度为L，平均集聚系数为C.定义网络总容量A为网络在单位时间内能够传输的最大数据吞吐量.网络有效容量Ae为网络在单位时间内处理的源到目的的最大数据吞吐量，LAP为网络平均最短路径长度，则A和Ae的计算式为

证明见图1.

假定任意1个WSN 节点总数为N，单个节点单位时间内最大能够传输的数据量为x，则网络的总容量为N.但是，考虑到实际WSN 网络采用载波侦听多址接入＼撞回避（CSMA＼CA）机制，当1个节点要传输数据时，周围所有与其连接的节点都会主动退避.所以，在WSN 网络中，当1个通信链路传输数据时，其消耗的网络资源远大于2个节点.

当节点J向邻节点B传输数据时，用粗线将所有被J和B遏制的节点连接，形成一个折线框.其中，BC处在J，B覆盖范围的交集内，完全被J和B消耗.而DC，EC边则是在J和B覆盖范围的并集内交集外，被J和B消耗一部分.所以，J和B消耗C的边数的比例为：（1＋1×K1＋1×K2）÷dc（dc为C的总边数，等于节点度数；K1和K2分别为待定系数，表示分别消耗的2条边的比例）.同理，当J向B传输数据时，被遏制的其他节点，可以用同样的方法计算其被J和B消耗的比例.所有相邻节点的边的消耗，都分为完全消耗的边和部分消耗的边.由图1可知，折线框内的边完全被消耗（如BC），而在折线框边上的边是部分消耗的（如DC）.

下面计算被完全消耗的边和部分消耗的边的数量（以J向B传输数据为例）.

完全消耗的边的数量f为：J和B邻边的总量，减去重复计算的部分，即f＝dJ＋dB－1.

部分被消耗的边的数量为所有J和B邻节点之间的连边的数量总和.可以分别计算出J和B的邻节点之间的连边数，再减去重复计算的部分.利用集聚系数的概念，J所有邻节点之间的连边的数量为CJ·C2dJ.此时，B作为J的1 个邻节点，边BF和BG仍然被计算在内，但是这2条边在前面的全消耗中已经计算过，应该减去，即但是，从WSN 全局看，各节点的地位是平等的，网络特征可以近似为相同，可将B当作1个普通节点处理，则算术表达式可写作.同理，B所有邻节点之间的连边数量为：CBC2dB（1－1－dB）.所以，当J向B传输数据时，消耗的总边数f是

其中，K1和K2分别为待定系数，表示部分消耗的比例.从图中可以看出，在部分消耗的边中，有的被2个节点传输的覆盖范围共享，有些被多个节点传输的覆盖范围共享.因此，当J向B传输数据时，每一条边被J和B消耗的比例是不同的.在实际网络中，被2个节点传输的覆盖范围共享占的比重很大，因此，可以近似取K1和K2为0.5.所以，当J向B传输数据时，消耗的总边数f可以近似计算为

从整个网络看，将dJ和dB用平均统计量即平均节点度d来代替，CJ和CB用平均统计量即网络集聚系数C来代替，可以得到网络中1条通信边消耗的平均总边数为

相应消耗的网络节点数d0为

整个WSN 网络中能够同时传输数据的节点数为N／d0，代入式（1），可以得到网络总容量

可以用3个例子来验证上述定理.当网络中只有2个节点时，网络容量计算值和实际值都为A0.当网络为具有N个节点的全连接网络，且N趋向无穷大时，网络容量计算值和实际值都为A0.还可用数值模拟法网络容量结果，计算式所得结果与数值模拟一致.由于篇幅的关系就不详细列出.

定义网络的有效传输为：从源节点到目的节点之间的成功数据传输.在WSN 网络中，数据从源节点出发之后，要经历多次中间节点的转发，最终到达目的节点.若网络的平均最短路径长度为LAP，则网络中的任何2个节点之间的数据传输要经过LAP个节点转发，即每次在2个节点之间传输数据，要经历LAP次数据传输.因此，LAP越大，网络效率越低，反之亦然.所以，可推导出网络有效容量

2 基于复杂网络理论的WSN拓扑控制

从上节定理可以得到，当已知WSN 中的总负载量，WSN 的有效网络容量与［（2－1／d）＋C（d－1）.（1－1／d）／2］LAP的值成反比；值越小，WSN 有效网络容量越大.为了提高网络容量，思路是保持d不变，减小Cd（－）1 与LAP的值.根据参考文献［11］对网络聚集系数的几何特征的总结可知，Cd（－）1 与每个节点相连的三角形数的平均值除以网络的平均度的值成正比，所以，减小Cd（－）1 可以通过保持网络平均度不变、删除三角形的边来实现.并且，通过删除三角形中集聚系数较小的边（指该边所在2个点的集聚系数比较小或者该边的删除可以使网络的集聚系数变大），还可以使网络簇结构更明显.减小LAP的值可以通过在每个簇网络中加入长程边实现.通过控制删除冗余边与添加长程边的数目使它们相等，可以保持d值基本不变.由于复杂网络的小世界特性就是具有大的集聚系数和小的平均路径长度，所以，减小Cd（－）1 与LAP、提高网络有效容量的过程，就相当于构造WSN 小世界特性的过程.下面是具体的拓扑控制的实现步骤：

步骤一，WSN 拓扑初始化.采纳Andy等提出的满足节点度部分有界和能量有效性的拓扑算法PLA［5］，来构造WSN 拓扑的初始状态.

步骤二，构造WSN 的小世界特性.运用文献［13］中的RLOC算法，有选择性地删除一些冗余边，使网络更具明显的簇结构.运用文献［10］的方法，WSN 根据节点自身状况动态地选择每个簇的簇头和超级节点，通过功率控制，在普通节点和超级节点间添加长程边，减小每个簇的平均路径长度，并且保持添加长程边的总数与删除的冗余边数量相等.

在第1节的网络有效容量公式指导下，通过本节的拓扑控制方法，可以增加网络的有效容量，并且使WSN 网络具备复杂网络的小世界特性.

3 具有小世界特性的WSN 安全维护

3.1 小世界特性对病毒传播的影响

对疾病传播网络的研究发现，如果一个网络具有较小的路径长度和较高的集聚系数，那么对疾病的传播扩散有着很大的促进作用［14－15］.这对于经过上一节拓扑控制后具有小世界特性的WSN 网络也是如此.一般地，集聚系数对应故障传播的广度，平均路径长度代表故障传播的深度，由于小世界网络兼具大深度和宽广度，所以在传播强度相同的情况下，传播速度和影响范围大大高于相应的规则网络（随机网络），如图2所示.因此，如何对具有小世界特性的WSN 进行安全维护也是本研究的重点.

图2 平均扩散范围与传播强度的关系Fig.2 The relationship between average spread range and the spread intensity

3.2 网络节点安全敏感性评判

在具有小世界特性的WSN 中，网络节点的度数对故障扩散起着重要作用.某节点的度数越大，对应的传播路径就越多，扩散范围就越大.同时，考虑到具有小世界特性的网络之所以具有独特的几何性质，是因为边的重连过程为网络引入了少量长程边.在复杂网络中，当某节点具有长程连接时，其他节点对之间的最短路径通常会优先经过这类节点.结合参考文献［11］对节点介数的定义，可以表述为：节点介数越高，长程连接的可能性就越大，故障也越容易通过这些节点快速传播.因此，识别这些高介数节点，对改善和提高网络的安全稳定性具有重要意义.

根据以上分析，网络节点的度数、介数越大，安全敏感性越高.也就是说，这类节点既容易受到其他相关节点故障的影响，也容易导致和促进其他相关节点故障的发生.研究还发现，在复杂网络病毒传播模型中，为了抑制病毒的大范围传播，对距离感染源2步内的节点免疫，可较好地控制病毒传播［16］.而且局部控制策略也非常适用于大规模的有能量限制的WSN.为此，引入节点病毒传播强度评判节点的安全敏感度，节点病毒传播强度越大，节点的安全敏感度越高.通过对选中节点2步内的具有高病毒传播强度的邻节点免疫来维护WSN.下面给出任意节点i的病毒传播强度定义.

式中：wp，ws分别为疾病传播过程中节点度和节点负荷所对应的权重；di为节点i的度数；∑Si为通过节点i成功转发查询消息的数量，数量越多，说明经过i的节点间的最短路径越多，节点i的介数越大.V为当前工作节点所了解的、距离其2 跳内的节点集合.对病毒传播强度Ii归一化处理，得到I′i＝Ii／并设定一个门限值I0，将节点的病毒传播强度归一化值与I0比较，对归一化值大于I0的节点免疫.

3.3 免疫方法

对具有小世界特性的WSN 免疫过程描述如下：

步骤一，当系统检测到网络中有节点遭到病毒感染或恶意攻击时，迅速组织实施免疫响应.并将免疫信息（如病毒清除或攻击防御指令）或免疫更新信息（如新的病毒或恶意攻击定义），注入到这些被感染的节点上，并执行免疫操作.

步骤二，确定免疫目标.根据当前操作节点k所维护的本地邻近节点信息，确定距离k的2跳范围内的节点集合V.计算V中节点的病毒传播强度并归一化处理.将归一化值大于I0的节点选出，作为本地免疫目标节点.

步骤三，转发免疫信息，执行免疫操作.将免疫信息转发到所有免疫目标节点，并分别执行免疫操作.

步骤四，以并行方式在新的当前节点上依次执行步骤二、三，直至满足终止条件（如网络中的感染率降低到预先设定值以下）.

4 模拟仿真与分析

模拟仿真研究在VC＋＋6.0环境下进行.设置100个节点随机分布在边长a＝150 m 的正方形拓扑中，令节点最大传输半径r＝15m，节点传输功率可调.运用第2节提出的拓扑控制方法，对WSN 进行拓扑控制.表1为未经过拓扑控制和经过拓扑控制以后的WSN 的平均度d、平均集聚系数C、平均路径长度LAP（以跳数为单位）的对比表.表2 是WSN 节点的负载（以数据包为单位）从5到10，15，20，25过程中，经过拓扑控制与未经过拓扑控制的WSN 有效网络容量（用数据包的数量统计）对比表.

表1，2的仿真结果表明，运用本拓扑控制方法可以增强WSN 的小世界特性，有效提高WSN 的有效网络容量.该结果与第1，2节的理论结论一致.

经过基于复杂网络理论的拓扑控制后，对第3节提出的WSN 免疫方法进行免疫成本和免疫效率的性能仿真与测试.假设每个节点的数据传输速率为1 Mb·s－1、病毒感染初始概率为0.5，执行免疫操作的初始免疫节点的选择比例为2%，同时为计算方便，假设节点病毒传播强度中对应节点度和节点负荷的权重系数wp和ws均取值为1，判定是否对节点免疫的节点病毒传播强度的门限值I0＝0.35.

表1 经过与未经过拓扑控制的WSN 网络参数对比Tab.1 Comparison of network parameters between WSN with topology control and without control

表2 经过与未经过拓扑控制的WSN 有效网络容量对比Tab.2 Comparison of effective network capacity between WSN with topology control and without control

为评估本方法的性能，在相同实验条件下，选择两种常见的免疫方法作为比较，即文献［17］提出的目标免疫（选取少量度最大的节点免疫）、文献［18］提出的熟人免疫（对随机选出的节点邻居免疫）.并且定义免疫成本为在稳定状态下感染密度降为零或接近于零所需免疫的网络节点在总节点中所占的比例，这也是免疫方法成本经济性的度量指标；免疫效率为稳定状态下相对感染概率Pp／P0随免疫时间的增加而下降的速度.其中P0为网络未加免疫时的感染节点占总节点数的概率，Pp对网络节点实行免疫策略后的感染节点数占总节点数的概率.此时，执行免疫方法的节点数的比例为p.免疫效率是衡量免疫方法在复杂多变的网络感染环境中是否高效完成免疫任务的重要指标.

从图3中可见，随着p增大，本方法对应的相对感染概率曲线迅速下降，且在p＝0.18时接近零感染，远优于随机免疫方法（0.3），并十分接近熟人免疫方法（0.04）.这意味着本方法只需对少量的关键节点免疫，就能控制网络中病毒（或恶意攻击）的扩散，且仅利用局部拓扑控制信息以完全分散的方式进行.相较于其他免疫方法，在WSN中可行性更高.

图4描述了三种免疫方法的相对感染概率随免疫时间的变化曲线.结果表明，本方法的曲线下降速度远高于随机免疫方法，并在Pp／P0降至约0.68以下之后，超过了熟人免疫方法的速度，继续迅速下降接近于零，表现出高效的免疫效率.这表明，本法将节点度和节点负载的综合加权值作为免疫目标选取条件较合理，更适用于具有小世界特性的WSN.

图3 3种免疫方法的免疫成本比较Fig.3 Comparison of immune cost of the three immune methods

图4 3种免疫方法的免疫效率比较Fig.4 Comparison of immune effectivity of the three immune methods

5 结论

本文提出了一种基于复杂网络理论的网络拓扑控制方法，并设计了一种适合具有小世界特性WSN的病毒免疫方法.实验结果显示，这种拓扑控制方法使原WSN 网络容量提高了近30%，并通过基于复杂网络的病毒免疫措施后，WSN 的免疫成本、免疫效率等参数均有明显的性能改善.

［1］ Collins J，Chow C.It’s a small world ［J］.Nature，1998（393）：409.

［2］ Helmy A.Small worlds in wireless networks ［J］.IEEE Communication Letters，2003，7（10）：490.

［3］ Chiradurga R，Helmy A.Analysis of wired shortcuts in wireless sensor networks ［C］∥ACS International Conference.Washington DC：IEEE Computer Society，2004：167－176.

［4］ Sharma G，Mazumdar R.Hybrid sensor networks：a small world［C］∥The ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York：Association for Computing Machinery，2005：366－377.

［5］ Rodoplu V，Meng T H.Minimum energy mobile wireless networds［J］.Selected Areas in Communications，1999，17（8）：1333.

［6］ Li N，Hou J，Sha L.Design and analysis of an MST－based topology control algorithm［C］∥IEEE International Conference on Computer Communications.Sanfrancisco：IEEE，2003：1702－1712.

［7］ Andy A，Kai Jeng，Rong Hong Jan.The neighborhood graph：an adjustable structure for topology control in wireless ad hoc networds［J］.IEEE Computer Society，2007，18（4）：536.

［8］ Hawick K A，James H A.Small－world effects in wireless agent sensor networks ［J］.International Journal of Wireless and Mobile Computing，2010，4（3）：155.

［9］ Sharma G，Mazumdar R.Hybrid sensor networks：a small－world［C］∥Proceeding of the 6th Association for Computing Machinery International Symposium on Mobile Ad Hoc Networking and Computing.Chicago：Association for Computing Machinery，2005：366－377.

［10］ YE X，XU Li，LIN Liwei.Small－world model based clustering division scheme in wireless sensor network［C］∥WRI International Conference on Communications and Mobile Computiong.Kunming：IEEE，2009：87－91.

［11］ 汪小帆，李翔，陈关荣.复杂网络理论及其应用［M］.北京：清华大学出版社，2006.WANG Xiaofan，LI Xiang，CHEN Guanrong.Complex network theory and its applications［M］.Beijing：Tsinghua University Press，2006.

［12］ Bernardo M D，Garofalo F，Manfredi S，et al.Load distribution in small world network ［C］∥International Conference on Physics and Control.Petersburg：IEEE，2005：100－105.

［13］ YE Xiucai，XU Li，LIN Liwei.Small－world model based topology optimization in wireless sensor networks ［C］∥IEEE International Conference on Information Science and Engineering.Shanghai：IEEE，2008：102－106.

［14］ Pastor Satorras R，Vespignani A.Epidemic dynamics and endemic states in complex networks［J］.Phys Rev E，2001，63：066117.

［15］ Pastor Satorras R，Vespignani A.Epidemic dynamics and endemic states in complex networks［J］.Phys Rev E，2001，86：3200.

［16］ 许丹，李翔，汪小帆.复杂网络病毒传播的局域控制研究［J］.物理学报，2007，56（3）：1313.XU Dan，LI Xiang，WANG Xiaofan.An investigation on local area control of virus spreading in complex networks［J］.Acta Physica Sinica，2007，56（3）：1313.

［17］ Satorras R P，Vespignani A.Immunization of complex networks［J］.Physical Review E，2002，65（3）：036104.

［18］ Madar N，Kalisky T，Cohen R.Immunization and epidemics dynamics in complex networks ［J］.The European Physical Journal B：Condensed Matter and Complex Systems，2004（2）：269.