摘 要：“小世界”现象的普遍性及平均路径长度小和集聚系数大的特点，使其在无线传感器网络中的应用越来越广泛。本文在对“小世界”理论的研究背景、网络模型、网络主要特征度量及“小世界”特性进行介绍后，重点分析了“小世界”理论在无线传感器网络的研究现状及其今后的发展趋势。
关键词：“小世界”理论；无线传感器网络；平均路径长度；集聚系数
引言
“小世界”现象普遍存在于大量真实网络中，如SARS传播、科学家合作网、电力网络、互联网控制、产品生产关系网等。由于“小世界”现象的普遍性及其具有小的平均路径长度和大的集聚系数的特点，使得“小世界”理论得到越来越广泛的应用，受到了研究人员的高度重视，成为一个极其重要而且富有挑战性的前沿科研方向。
无线传感器网络是由一组传感器以Ad hoc方式组成的无线网络，其目的是协作地感知、收集和处理传感器网络所覆盖地理区域中感知对象的信息，并将处理结果传递给观察者[2]。由于无线传感器网络具有资源有限等特点，因此，构建具有小世界效应的无线传感器网络，对于降低整个网络的通讯开销、提高数据查询处理的效率、减少每个节点的平均能量消耗及延长网络的生存时间都具有十分重要的意义。
1 小世界网络研究背景
l929年，匈牙利作家F．Karinthy最早提出了“小世界现象”的论断。Karinthy认为，地球上的任何两个人都可以通过一条平均为6个联系人组成的链条而联系起来。上世纪60年代，美国哈佛大学社会心理学教授斯坦利·米尔格兰姆(Stan．1ey Milgram)通过设计一个连锁信件实验，提出了著名的“六度分隔”(Six degrees of Separation)假说，即“小世界现象” (Small World Phenomenon)。体现了一个似乎很普遍的客观规律：在如今的信息化时代，人们之间的关系已经完全社会化，任何两位素不相识的人都可能通过“六度空间”产生必然联系或关联 。
为了描述“六度分离” 理论，Watts和Strogatz在对规则网络和随机网络理论进行研究的基础上，于1998年提出了著名的WS小世界网络(SWN)这一概念，并建立了模型。
图1 “小世界”网络模型
图1所示的小世界是在左图的规则网络基础上通过边的重连得到的。对于规则网络的所有边以概率p断开一个端点，并重新连接，连接的新端点从网络中的其它顶点里随机选择,如果所选的顶点已经与此顶点相连，则再随机选择别的顶点来重连。当P＝0时就是规则网络，P=1则为随机网络，对0
2.1主要度量
1．度分布。度分布表示节点度的概率分布函数P(k)，它指的是任意选择的一个节点有k条边连接的概率。
2．簇系数。簇系数又称作集聚系数，节点i的簇系数Ci描述的是网络中与该节点直接相连的节点之间的连接关系，即与该节点直接相邻的节点间实际存在的边数目占最大可能存在的边数的比例。
3．平均路径长度。平均路径长度指网络中所有节点对之间的平均最短距离。平均路径长度的计算公式为APL ，其中dij 为节点i和j之间的最短距离。
4．介数。介数分为顶点介数和边介数两种，它是一个全局变量，反映了节点或边的作用和影响力 。如果一对节点间共有N条不同的最短路径，其中有n条经过节点i，那么节点i对这对节点的介数的贡献为n／N。把节点i对所有节点对的贡献累加起来，就可得到节点i的介数。
2．2 主要特征
平均路径长度和集聚系数是衡量网络拓扑，刻画小世界特性的主要指标。小世界网络具有如下两个主要特征。
1．小的平均路径长度 小世界网络中具有小的平均路径长度，使得网络中节点之间数据的传输只需经过较少的跳数，有利于整个网络的路由机制，降低通讯开销及减少节点的能量消耗。
2．大的聚集系数 聚集系数是网络集团化的程度，即考察连接在一起的集团各自的近邻之中有多少是共同的近邻，这是网络的一种内聚倾向。小世界网络中具有大的聚集系数。
图2 归一化的平均路径长度和聚集系数
3 “小世界”理论在无线传感器网络中的研究
3．1异构传感网络的构造及性能改进
现有的无线传感器网络主要考虑同构网络，即所有节点具有相同的通信、计算能力和能量储备。同构传感器网络性能有限，可扩展性差，而且能量和计算资源有限。因此，通过部署少量具有稳定电源供给的节点或有线传输链路，构造具有“小世界”特性的异构传感器网络，可以有效提高系统的可靠性和延长网络的生命期。
Helmy等学者通过在无线传感器网络中引入逻辑链路形成具有小世界效应的无线网络，从而验证了小世界网络同样适用于具有空间属性的无线网络。文献通过在无线传感器网络中添加少数有线构成的网络捷径（short cuts），这些有线的添加是居于NIMS体系（Network Info-mechanical Systems), 它由一系列钢制的电缆组成，电缆的两端吸附在楼房、树等其它的自然基础设施上。每条电缆的两端带有无线收发器,充当节点的角色，可以收集从其它传感器节点发送的数据，也可以将接收的数据发送给其它传感器节点。这表明在无线传感器网络中通过添加捷径可以使整个网络的平均路径长度有显著的下降，并且所添加的捷径的长度只需达到网络直径的25 %～40 %。对均匀分布的1000个节点所构成的传感器网络，如果sink节点布置得当，平均路径长度最大降幅可达到60 %～70 %。
3．2 网络覆盖和网络生存时间
文献 同样借助NIMS基础设施在无线传感器网络中添加几条有线的形式构成了一种异构无线传感器网络。研究结果表明,在无线传感器网络中添加几条有线后,不但单个传感器节点的平均能耗显著降低,而且整个网络能耗的不均匀性也显著降低。此外实验还表明,通过在传感器节点之间添加少数随机连接,不但传感器网络的平均路径长度大大减小,而且网络中出现的孤立簇的数目也大大减少,无线传感器网络的整体覆盖效果和生存时间都大大改善。
文家焱等作者利用复杂网络的小世界效应探讨了无线传感器网络的近邻节点数问题，得出最佳近邻节点数为4－6的结论，进一步降低“小世界”无线传感器网络的平均路径长度，使网络能量的消耗进一步降低，进一步改进无线传感器网络的性能及网络覆盖效果。并且，是在网络工作时，无线传感器网络中的每个节点可以通过调整自身的通信功率，增大
或者减小通信距离 叶秀彩, 许力, 林力伟，一种基于小世界模型的无线传感器网络抗毁性评价方法，计算机系统应用，2010年第4期。
