基于动态搜索区域的无线传感器网络小世界特性构建方案

谢启辉 黄 杰

(东南大学信息科学与工程学院，南京210096)

无线传感器网络(wireless sensor networks，WSNs)是一种大规模的自组织网络，它由大量的成本低、体积小、功耗低、能量有限的节点在预定区域内随机布撒而成.WSNs广泛地用于环境监测、军事作战、森林火灾预警、农业、卫生医疗、航天、城市管理等领域，并取得了很好的效果.但是，由于WSNs的节点能量有限，使得能耗问题成为WSNs发展的瓶颈，如何优化传感器节点能耗以延长WSNs的寿命是WSNs亟需解决的问题.

文献［1］提出了社会学领域的“六度分离理论”.文献［2-3］研究了小世界网络的群体动力学，对小世界网络进行了理论上的研究，分别提出了随机重连的WS(Watts and Strogatz)小世界模型和随机加边的NW(Newman and Watts)小世界模型.文献［4］讨论了捷径对无线网络的影响，指出只需添加少量的随机链路，并且这些链路的长度(以跳为单位)只需达到网络直径的0.25～0.4(假设网络任意2个节点通信所需的跳数构成一个集合，网络直径就等于这个集合中的最大值)，就可以构造出网络的小世界特性.

在WSNs中，构造小世界特性主要是通过添加逻辑链路即捷径来实现的［4-8］.添加捷径方式可以分为随机重连和随机加边［9］.文献［10］提出了数据骡子方案.文献［11-12］提出了全新的构建WSNs小世界特性的 DAS(directed angulation towards the sink)方案和SSD(sink node as source/destination)方案.文献［12］对DAS方案进行了修正并提出了on-line DAS方案.DAS模型首次为WSNs网络从理论上提出了一种具有可操作性的捷径添加方法.

本文针对DAS方案存在的缺点，提出一种利用菱形搜索区域构建具有小世界特性的无线传感器网络的方案，并对该方案进行了性能分析.

1 DZ方案

无线传感网络中，主要存在sink和sensor 2种节点.sensor节点用来收集信息，sink节点用来向sensor节点发送命令信息，并将各个sensor节点收集的数据信息融合汇总后，以有线或无线的方式将处理后的信息发送给客户机.但是，要在无线传感器网络中构建小世界特性，必须要求所有的sensor节点输出功率可以通过软件编程调整，增大其通信半径，以便用于构建捷径的sensor节点具有更大的通信半径(要比未用于构建捷径的普通sensor节点的通信半径大)，从而保证能够实现捷径端点间的通信.

在1 000 m×1 000 m的范围内随机布撒1 000个节点，按照文献［12］设置参数:p=0.08，r=70 m，R=800 m，α=π/18，仿真得到 DAS方案的网络拓扑图(见图1).从DAS方案搜索捷径端点的方式来看，任何节点进行捷径搜索时，Zs区域(以sink为中心300 m为半径的扇形区域，其中300 m是来源于仿真结果的假设条件)内的节点都要被搜索一遍，这样，就会导致区域Zs内的节点以较高的概率被选为捷径端点.由于这些节点最容易因能量耗尽而成为孤立节点，被选为捷径端点后，更增加了这些节点的能耗，导致其能量更早耗尽，使网络寿命(出现第一个能量耗尽的节点所用的时间)缩短，大大降低了以DAS方案为理论基础的online DAS方案的实用性.因此，为了延长网络的寿命，就必须减小区域Zs内的节点成为捷径端点的概率，为此本文提出了一种可以动态改变捷径端点搜索区域的菱形区域(diamond zone，DZ)方案.

图1 DAS方案的网络拓扑图

与DAS方案类似，假设节点布撒区域为一个规则长方形区域，唯一的1个sink节点部署在布撒区域的左下角，其他sensor节点随机布撒.DZ方案的实现步骤如下:

①确定节点i的捷径端点搜索区域.所有节点都知道sink节点坐标为(0，0)，节点i已知本节点和节点j的坐标，节点i坐标为(x(i)，y(i))，节点j坐标为(x(j)，y(j)).选定节点i为捷径的一端，以节点i与sink节点的连线为菱形的一条对角线L1，则L1的方程为y=m1x+c1;以过节点i的一条垂直线为另一对角线L2，则L2的方程为y=m2x+c2.选取sink节点所在的位置作为菱形的一个顶点，顶角为α，则由以上条件可以确定一个菱形区域，此区域即可作为节点i的捷径端点搜索区域，用来搜索与节点i构成捷径的另外一个端点.如图2所示.其中，m1=y(i)/x(i)，m2= － x(i)/y(i)，c2=(x2(i)+y2(i))/y(i).

②候选捷径端点判定.假设节点i和sink节点连线为L1，节点j和菱形的端点sink节点的连线为L3，直线方程为y=m3x+c3;节点j和菱形在L1上的另一顶点的连线为L4，直线方程为y=m4x+c4.L1和 L3的夹角为 γ，L1和 L4的夹角为 β.候选端点判断准则:如果满足tan β＜tan(α/2)且 tan γ＜tan(α/2)，则判定节点j为候选捷径端点.其中

图2 DZ方案原理图

③捷径端点判定.节点i根据随机产生的0～1之间的随机数Q及指定的概率常数p(概率常数p用来作为随机数Q的一个比较对象，来判断是否将节点j选为捷径的另一端点).如果随机数Q＜p，则将节点j选为捷径的另一端点，至此停止搜索;反之，则执行② 和③，继续判断下一个候选节点，直到找到第一个满足Q＜p的节点，才停止搜索，转入为第i+1个节点添加捷径;如果所有节点都不满足Q＜p，则转入为第i+1个节点添加捷径.

根据概率常数p，将每个节点按照上述步骤轮询一遍，可构建出WSNs的小世界特性.

添加捷径后，sensor节点分为2类.原始节点的通信半径为r，表示为空心圆点;候选捷径端点的节点表示为实心圆点，如图2所示.如果被选为捷径端点，则其通信半径为R(R≫r).DZ方案为节点i添加捷径的流程如下(ZD是为节点i构造的菱形区域):

该搜索方案的优点是:搜索区域的面积大小随着节点i到sink节点的距离的增大而增大，这样，在离sink节点较近的Zs区域具有较小的搜索面积，并且这些搜索区域的位置随着节点的改变而变动.由于区域Zs内的节点相对于区域外的节点离sink节点比较近，搜索区域的变小会使Zs内的节点成为捷径另一端点的概率减小，从而保证了这些节点保存较多的能量，延长这些节点的存活时间.这样，既可以防止网络中Zs内的节点过早将能量耗尽而成为孤立节点，又可以缩短节点间的通信距离.同时，DZ方案添加捷径后可以保证WSNs网络具有小世界特性.

2 DZ方案的评估与优化

2.1 小世界特性的评估

在1 000 m×1 000 m的范围内随机布撒1 000个节点，布撒后的节点均匀分布，节点的组网半径r=50 m，捷径端点的通信半径R=800 m，捷径端点的搜索角度为α=π/18，按照这些参数，对DZ方案进行了仿真分析，结果如图3所示.

图3(a)为度分布曲线，其中，捷径添加概率p=0.001，p(k)为度分布，k为度值.由仿真结果可知，度分布曲线符合泊松分布曲线的趋势，满足小世界特性对度分布的要求.

图3(b)是捷径添加概率-归一化平均最短路径曲线，L(p)/L(0)为归一化平均最短路径，C(p)/C(0)为归一化聚类系数.由仿真结果可知，构造小世界特性以后，WSNs网络的平均最短路径长度迅速下降，但网络的聚类系数下降缓慢，能够保证在平均最短路径长度迅速减小时，保持大的聚类系数，使整体和局部都保持很好的连通性，满足小世界特性的要求.

图3 DZ方案小世界特性仿真分析(α=π/18)

2.2 2种方案的对比分析

通过以上仿真证明了利用DZ方案可以在无线传感器网络中构建出小世界特性，为了将DZ方案和DAS方案的小世界特性进行对比，针对不同的p值和α值利用2种方案构建小世界特性，并通过对网络聚类系数及其归一化值的对比，证明在部分链路失效的情况下，DZ方案较DAS方案有更好的抗毁性及小世界特性.

2.2.1 固定α值和改变p值

设α=π/18，r=70 m，R=800 m，p从0～1依次递增的情况下，利用2种方案构建小世界特性，得到网络聚类系数的仿真对比如图4所示.从图4(a)仿真结果可以看出，随着p值的增加，DZ方案构建的小世界特性的归一化聚类系数值要比DAS方案的归一化聚类系数值大，能够保持一个较好的小世界特性.

从图4(b)和表1可以看出，对应不同的p值，DZ方案构建的小世界特性的网络聚类系数比DAS方案的要大.由于聚类系数反映了网络的局部连通性，聚类系数越大，网络的局部连通性就越好.所以，通过添加捷径构造的具有小世界特性的无线传感器网，DZ方案较DAS方案具有更好的局部连通性.

图4 2种方案仿真对比(p值改变)

表1 2种方案p值不同时对应的C(p)值

较好的局部连通性有利于提高网络的抗毁性，局部连通性越好，表明各个节点的一跳邻居节点间的实际通信链路越多，如此就可以保证节点和一跳邻居节点间有多条通信链路.当部分链路失效时，可以通过其他链路进行通信，从而有助于提高网络的抗毁性.所以，通过添加捷径构造的具有小世界特性的无线传感器网，DZ方案较DAS方案有更好的抗毁性.

2.2.2 固定p值和改变α值

设p=0.01，r=70 m，R=800 m，α从π/180～π/2递增情况下，利用2种方案构建小世界特性，得到网络聚类系数的仿真对比如图5所示.

图5 2种方案对比分析(α值改变)

随着α值的不断增加，图5(a)反映了DZ方案构建网络的归一化聚类系数要比DAS方案构建网络的好，具有较好的小世界特性.图5(b)和表2反映了DZ方案构建的网络比DAS方案构建的网络具有更好的局部连通性.结果表明，在部分链路失效时，DZ方案比DAS方案有更好的抗毁性.

表2 2种方案α值不同时对应的C(p)值

2.3 节能并延长网络生命周期的评估

与图1构建捷径的条件相同，图6是DZ方案构建捷径后的网络拓扑结构.图1和图6在区域Zs内，当捷径添加概率p一定时(p=0.08)，图6中的捷径端点数目明显比图1中减少了很多，意味着区域Zs内的节点被选为捷径端点的概率减小，即可以节省Zs内节点的平均耗能，从而延长网络的寿命.

图6 DZ方案的网络拓扑图

但是，由于DZ方案搜索捷径的区域相对于DAS方案有所减少，在为节点i搜索另一个捷径端点时，就需要搜索更多的节点，这样使得捷径构建时节点的能耗增加.假设构建捷径时DAS方案和DZ方案每个节点的平均耗能分别为ec-DAS和ec-DZ，捷径节点每接收并发送一次数据的平均能耗为e(即每减少一次数据中继的平均节能)，那么如果要证明DZ方案确实比DAS方案有效，就必须满足w＞ec－DZ－ec-DAS(w为捷径节点中继数据的次数)，即Zs区域内的节点w次中继数据节省的能量大于搜索捷径端点增加的能量(ec-DZ－ec-DAS)，从而在节能的前提下提高网络的寿命.下面采用极限化搜索区域的方法证明不等式w＞ec-DZ－ec-DAS在一定条件下成立.

假设2种方案的捷径端点的搜索区域极限化为整个节点撒布区域，下面以DAS方案为例，假设网络中除节点i以外的其他节点都满足tan β＜tan(α/2)，则此时每个节点构建捷径消耗的能量为ec-DAS的最大值，记为max{ec-DAS}.假设网络中布撒N个节点，由DZ方案的描述可知，每个节点要判断另一个端点是否可以和其组成捷径，所需判断次数n的取值范围为1≤n≤N－1，若节点每做一次判断消耗的能量为E，则节点i搜索到捷径的另一端点所消耗能量nE的概率为(1－p)n－1p(1≤n≤N－1).因此，可以得到 max{ec-DAS}的期望

式(1)×(1－p)可得

由式(1)和(2)可得

由于DZ方案的判断准则比DAS的多进行了一次tan β＜tan(α/2)判断，所以DZ方案的每个节点每进行一轮捷径构建的能量消耗约为2E，同理可得DZ方案每个节点构建捷径消耗的能量最大值为2E(max{ec-DAS}).

所以，ec-DAS∈(0，E(max{ec-DAS}))，ec-DZ∈(0，2E(max{ec-DAS})).由此可得

而e=2Eelec+EA，所以要保证DZ方案既节能又比DAS方案的寿命长，需要满足

式中，Eelec为节点发送/接收单位bit数据的电子能量消耗;EA为节点发送单位bit数据的功率放大能量消耗［13-14］.

所以，在w满足式(5)时，即

DZ方案优于DAS方案，既节省了能量，又延长了网络的生命周期.

3 结语

分析了DAS方案的性能，并针对其缺陷提出了DZ方案，使捷径端点搜索区域动态化，解决了DAS方案中临近sink节点的区域Zs内的节点能量过度消耗问题.通过仿真，验证了DZ方案的小世界特性，保证了网络较强的抗毁能力.然后，理论证明了在w满足一定条件的情况下，DZ方案较DAS方案既节能又能延长网络寿命.从而，找到了一种较DAS方案更加优越的小世界网络构建方案，提供了一种更好的理论依据，以改善网络拓扑，延长网络寿命.

References)

［1］Watts D J，Strogatz S H.Collective dynamics of“small-world” networks［J］. Nature，1998，393(6684):440-442.

［2］Milgram S.The small world problem［J］.Psychology Today，1967，1(1):61-67.

［3］Newman M E J，Watts D J.Renormalization group analysis of the small-world network model［J］.Physics Letters A，1999，263(4):341-346.

［4］Helmy A.Small worlds in wireless networks［J］.IEEE Communications Letters，2003，7(10):490-492.

［5］Luo X，Yu H.Constructing wireless sensor network model based on small world concept［C］//2010 3rd International Conference on Advanced Computer Theory and Engineering(ICACTE).Chengdu，China，2010:501-505.

［6］Hawick K，James H.Small world effect in wireless agent sensor networks［J］.International Journal of Wireless and Mobile Computing，2010，4(3):155-164.

［7］郑耿忠，刘三阳，齐小刚.基于小世界网络模型的无线传感器网络拓扑研究综述［J］.控制与决策，2010，25(12):1761-1768.Zheng Gengzhong，Liu Sanyang，Qi Xiaogang.Survey on topoloy of wireless sensor networks based on small world network model［J］.Control and Decision，2010，25(12):1761-1768.(in Chinese)

［8］Chinnappen-Rimer S，Hancke G P.Modelling a wireless sensor network as a small world network［C］//Proceedings of the 2009 International Conference on Wireless Networks and Information Systems.Shanghai，China，2009:7-10.

［9］王波，王万良，杨旭华.WS与NW两种小世界模型的建模及仿真研究［J］.浙江工业大学学报，2009，37(2):179-182，189.Wang Bo，Wang Wanliang，Yang Xuhua.Research of modeling and simulation on WS and NW small-world network model［J］.Journal of Zhejiang University of Technology，2009，37(2):179-182，189.(in Chinese)

［10］Jiang Chang-Jie，Chen Chien，Chang Je-Wei，et al.Construct small worlds in wireless networks using data mules［C］//Proceedings of IEEE International Conference on Sensor Networks，Ubiquitous，and Trustworthy Computing.Taichung，China，2008:28-35.

［11］Guidoni Daniel L，Mini Raquel A F，Loureiro Antonio A F.On the design of heterogeneous sensor networks based on small world concepts［C］//Proceedings of the 11th ACM International Conference on Modeling，Analysis，and Simulation of Wireless and Mobile Systems.Vancouver，Canada，2008:309-314.

［12］Guidoni Daniel L，Mini Raquel A F，Loureiro Antonio A F.On the design of resilient heterogeneous wireless sensor networks based on small world concepts［J］.Computer Networks，2010，54(8):1266-1281.

［13］Qin W，Hempstead M，Yang M.A realistic power consumption model for wireless sensor network devices［C］//2006 3rd Annual IEEE Communications Society.Reston，VA，USA，2006，1:286-295.

［14］Han B，Zhang D Z，Yang T.Energy consumption analysis and energy management strategy for sensor node［C］//International Conference on Information and Automation.Changsha，China，2008，6:211-214.