节点密度对优化Ad Hoc网络生存期的影响的研究

摘要: 节点密度会限制拓扑控制策略对Ad Hoc络生存期的有效优化范围.通过推导节点密度决定下的拓扑控制力的饱和状态趋向约束条件，阐述了节点密度与络生存期的优化程度及拓扑控制性能分析之间的关系.通过实验仿真验证发现，在Ad Hoc络中，通过平均度约束的拓扑控制确实可以延长络生存期;而且，在节点密度的制约下，拓扑控制策略对络生存期的优化将会达到饱和.

关键词: 拓扑控制；络生存期；平均通信半径；平均度；邻近图

中图分类号:TP393.03

文献标识码:A文章编号:1672-8513(2010)04-0235-06

Study on the Effect of the Nodal Density on Optimizing Ad Hoc Network Lifetime

WANG Dong1，LI Na1，3, WANG Wenyan1, L Geli2

（1. College of Computer and Communication, Hunan University, Changsha 410082, China；2. College of Information Science and Engineering, Central South University, Changsha 410083, China；3. RFID Research Center，Institute of Automation, Chinese Academy of Sciences，Beijing 100080, China）

Abstract: Nodal density limits the effective work range of the topology control strategy for optimizing the Ad Hoc network lifetime. Through deducing a constraint on the topology control's saturation trend, this paper presents the relationship between the network nodal density and both the network lifetime's optimized level and the topology control performance analysis. Further simulations not only show that the average-degree constraint topology can prolong the network lifetime in the Ad Hoc network, but also show that under the constraint of nodal density, the optimization of the network lifetime controlled by topology will reach saturation.

Key words: topology control; network lifetime; average communication radius; average degree; proximity graph

[HJ]

鉴于无线多跳Ad Hoc络在军事、商业和教育环境下的广泛应用，如办公室内无线局域的连接、家用设备络和传感器络等，关于Ad Hoc络的研究已经得到了广泛的关注［1］.特别是针对Ad Hoc络中节点能量的有限性，以及络生存期对络能耗的部分依赖性，如何提高节点及络能量的有效性，使络在有限的能量条件下尽可能工作更长的时间，已经成为该类络设计的主要目标之一.目前提出的一些拓扑控制算法，主要是通过降低发射功率来减少节点能耗，进而达到了延长络生存期的目的.但是一些研究表明，虽然通过减少节点能耗确实可以延长络生存期，但通过降低节点发射功率却不一定可以减少节点能耗.

对此，文献［2］另辟蹊径，通过关注到节点密度与通信半径及稀疏性之间的关系，指出约束节点平均度的拓扑控制在保证连通性的同时，使络的通信结构满足稀疏性的要求，以减少选出的工作节点数，简化通信节点间的路由机制，以降低对节点能量的消耗，从而延长了Ad Hoc络的生存周期.

但是，文献［2］在得出通过平均节点度约束可以延长Ad Hoc络生存期的结论后，却没有进行实验仿真验证.

本文利用4种实现了不同度有界状态的拓扑控制算法，实验仿真验证了该结论.进而发现，在节点密度的约束下，Ad Hoc络生存期的优化过程存在饱和状态.越过饱和状态后，Ad Hoc络生存期将无法得到继续的优化.

1 研究背景

文献［3］提出节点密度会影响到节点平均度.且在文献［2］提出平均度约束的无线传感器络拓扑控制之前，很多以维持某种拓扑形态为核心的拓扑控制策略都已经关注到节点度这个问题.但是，文献［4］等虽提出对络拓扑进行节点平均度的约束可以优化络性能，却没有考虑络拓扑的节点密度、络通信半径与稀疏性之间的关系.对此，文献［2］从无线传感器络节点的邻居数、节点的通信半径和络中节点的个数等参数寻求出了络连通性、路由机制简单性和节点稀疏性之间的关系.

与此同时，针对研究拓扑控制对络性能影响的工作逐渐从实验仿真、数值模拟和理论推导3个方面展开.其中，针对被研究对象拓扑控制算法的研究，主要是以最大限度地延长络的生存期作为设计目标，在保证络连通性的同时，通过控制节点的发射功率和激活/休眠状态等方式来改善络的通信结构.

显然，文献［2］在对络生存期的优化效果进行分析的过程中，缺少了3个方面中的实验仿真阶段.文献［5］指出现有的拓扑控制对于延长络的生存期等具有重要意义.明显，依据算法生成的拓扑图是对称、边稀疏和节点度有界这个性质，可以理论推导出该结论.但是文献［5］中也未能列举一些实验结论进行佐证.而其它考虑进了仿真实验阶段的同类研究，却由于没有意识到节点密度会带来的影响，而缺乏对仿真场景设计的考虑.如文献［6］中，仿真场景被随机地设置为60个节点随机地放置在1000m×1000m的区域内.

第4期 王 东，李 娜，王文艳，等：节点密度对优化Ad Hoc络生存期的影响的研究

云南民族大学学报（自然科学版） 第19卷

可见，由于没有认识到拓扑控制力的饱和状态的存在，现有研究中不但缺乏对实验仿真阶段中需要考察的节点密度的有效范围的统一约束，对节点密度可能带来影响的研究也不是很深入.

本文认为，在保证具有络连通性和稀疏性前提下的随机络中，络拓扑中的节点密度不仅会影响到通信半径的变化范围.同时还会影响到优化后的通信半径的变化范围，使得Ad Hoc络生存期的有效优化范围和拓扑控制策略的控制力出现饱和现象.

2 节点密度的影响

本文在保证网络拓扑的连通性和稀疏性的前提下，首先，运用几何方法得到一个网络拓扑固有参数决定下的具有优化网络生存期作用的通信半径r的趋势趋近范围；然后，根据拓扑控制中的固有参数对这个r的波动范围的约束性，得出拓扑控制力饱和状态的存在性.

2.1 节点密度对通信半径的优化范围的影响

由于节点个数和节点撒播范围决定了网络的基本空间布局，所以，当节点撒播范围A（这里假设网络为方形，则边长为M的网络面积为：A=M2）和节点个数N得到确定后，平均分布状态下网络的节点密度（λ=N/A）即已确定.其中，平均分布状态下网络空间的单位长度h=M/N［5］.

由于仿真环境多是设置为规则的矩形区域，基于保持网络的对称性与均匀分布性的考虑，本文对优化后的通信半径通用范围的推导将基于以下一个相比随机网络拓扑结构可以优化网络生存期的理想网络拓扑结构.定义如下：网络拓扑结构中每个节点的度均为4.该网络拓扑结构的相对邻近图［7］如图1所示，由于是相对邻近图，则节点间的通信半径r不一定相等，即r≠h.

利用上文中构建的理想网络拓扑下的相对邻近图（见图1），可推出，网络节点密度会影响到网络中节点平均通信半径的变化范围.根据文献［3］中得到的平均节点度与网络原始拓扑参数N间的关系z=(N－1)πR2A(其中R表示节点的通信半径，z表示平均节点度)和文献［2］中确定的在满足网络连通性的条件下的节点通信半径的范围R∈A(N－1)π,AlnN(N－1)π，可以确定网络节点密度会影响到网络中节点的通信半径的变化范围.而且利用节点平均度的拓扑控制策略可以延长网络生存期这个结论，可以进一步得到一个可以优化网络生存期的通信半径的估计范围.

如图1所示，在满足网络连通性要求的前提下，对网络中可容纳的最大干扰量进行一种假设后，得到一组可以优化网络生存期的通信半径估计范围的临界值Rmin和Rhypothesis.

根据网络中对连通性与半径值最小的需求，出现连接时节点平均通信半径的下界值将定义为Rmin的值；假设，在考虑了网络连通性和假设的网络中可容纳的最大干扰后，覆盖以下界Rmin为通信半径时节点4个最近非邻接点的邻接点的通信半径将作为Rhypothesis的估计值.由于本文的重点不是得到准确的通信半径的范围，而是想得出一个临界值的趋势，以得到一个通信半径的通用变化范围，其他假设状态下Rhypothesis的变化趋势与本文中的假设趋势类似.

设存在一个常数c（为简单起见，本文假设为c而不是一个函数，实现变化趋势的描述，而不是变化过程）有：

这里的A/(N-1)由决定节点密度的节点个数N和节点撒播范围A决定，体现了节点密度的变化.

2.2 节点密度约束了平均度约束下的通信半径的变化

过于稀疏的网络通信结构及过于密集的网络通信结构都会对网络的通信状态有所影响.过于稀疏会产生很多的瓶颈节点，从而降低网络的生存期.过于密集的网络通信结构则会产生节点间的通信干扰，大量的能量将花费在发送包上［8］.过于稀疏时，出现瓶颈节点时的拓扑结构图例如图2所示，主要表现在，受最大通信半径RadiusX的限制，诸如S-D和S′-D′这样的业务流都将经过瓶颈节点，导致此类节点过早失效.

[JP2]为了实现平均节点度的约束，当网络节点密度不是很高时，在满足一定的稀疏性要求后，通过增大通信半径，可以实现节点平均度约束，进而间接地平均了每个节点的能耗，但由对通信半径的临界值趋势分析可知，增大的通信半径可能不宜大于值Rhypothesis.[JP]

其中，Rhypothesis[KG-*3]=[KG-*2]αAπ(N－1) ， （lnN>α>1）.

可见，平均节点度约束下的拓扑控制算法对网络生存期的优化受节点密度的影响，即节点密度约束了平均度约束下的通信半径的变化，过饱和状态下仍要求拓扑控制做到更优化不一定现实.所以，在进行拓扑控制性能分析的实验仿真环境的搭建过程中，应尽可能考察到饱和状态所在范围内为止.

3 实验仿真与分析

实验的仿真平台选用Brickley大学的NS-2 vision2.31.仿真场景为：N(N∈［50,200］)个节点随机分布在1000m×1000m二维区域中；每个节点以最大发射功率发送数据时的通信半径为250m；用cbrgen工具随机产生20 对UDG数据流，每个CBR包的大小为512字节；网络层使用DSR 路由协议；MAC 层使用IEEE 802.11 的DCF协议；节点使用0 dB 增益的全向天线，天线高度1.5m；接收阀值为3.65262×10-10W；带宽为2Mbps；节点的初始能量10J，使用3.1.2节的节点能量消耗模型，其中参数设置为［9］：r=512，α11=8×10-4，α12=7.2×10-4，α2=8×10-9， μ=2；每次仿真时间为300s.

本文将通过选取分别基于位置信息、方向信息和概率思想的UDG,CBTC［10］,GG［11-12］和LMST［13］4种拓扑控制算法作为实验对象，考察不同方向上的拓扑控制策略的节点平均通信半径和平均度与网络中节点个数的关系，并灵活地利用4种策略对节点平均度不同程度上的约束差异来分析节点度约束对Ad Hoc网络生存期的影响.

3.1 相关模型

实验仿真过程中的网络拓扑性能主要利用网络能耗模型来考察网络的生存期.其中，考虑了网络平均能耗概念的网络生存期模型，不仅是进行实验仿真过程中所考察的唯一网络性能，同时也是在现有分析中加入节点平均能耗的分析的纽带.网络能耗模型将被用在网络仿真平台上.

3.1.1 网络生存期模型

关于网络的生存周期的定义有很多种［1］，它们遵循的基本原则大致可以总结为：依据维持有效通信量状态的网络中可以容纳的最大失效节点量.本文用到的2种网络生存期模型定义如下：

模型1［1］：网络生存期在出现第1个能量耗尽的节点为止.

模型2：网络生存期在出现半数节点的能量耗尽为止.

在由能量有限的节点组成的Ad Hoc网络中，提高网络能耗的有效性，是延长网络生存周期的主要途径.显然，单位时间内失效节点的个数越少，网络的生命周期就越有可能得到延长.那么根据概率论可推得，通过平均整个网络中每个节点的能耗量，可以改善网络的生命周期.

本文在对多个拓扑控制策略进行仿真分析时，考虑到模型1可以比较出不同的拓扑控制策略优化后出现第1个失效节点的时间先后顺序.所以，利用模型1来横向衡量出每个策略的平均能耗的优劣趋势.

模型2作为对模型1的一个补充，将用来避免因为考虑平均能耗而忽略了单个特殊节点能耗过多或过少的情况，并最后通过大量仿真来达到排除个别现象的目的.

3.1.2 网络能耗模型

Ad Hoc网络中节点的能量主要用于数据的发送和接收.假设所有节点具有相同的路径损耗模型，则节点j发送一个r字节的数据包需要的功率，即发送功率［14］为：

Pj_transmit(dj)=(α11+α2•dju)•r .(5)

而节点j接收一个r字节的数据包需要的功率，即接收功率［14］为：

Pj_receive=α12•r .(6)

其中α11，α12，α2为常量，与收发机处理数据的电子功耗相关；μ（2≤μ≤4）为路径损耗指数［14］.那么，假设网络带宽为D，则节点发送或接收一个r字节的数据包的时间为：

tj=8rD .(7)

假设在网络运行的某段时间T内，节点j发送了nj个数据包，接收了mj个数据包，则节点j在时间T内消耗的能量为：

Ej_node(dj)=nj(α11+α2•duj)•r•tj+mjα12•r•tj .(8)

则网络在时间T内消耗的能量为网络中所有节点消耗能量之和，即：

Eall=∑nj=1Ej_node .(9)

3.2 节点密度与节点平均度和节点的平均通信半径

图3分别为UDG,CBTC,GG和LMST 4种拓扑控制在给定的撒播范围内，节点平均度和节点平均通信半径随节点个数的变化趋势.节点平均度与Y轴的刻度的比例是1∶5.可以看出，UDG,CBTC,GG和LMST 4种拓扑控制表现出的对Ad Hoc网络中节点平均度的约束力依次增加.

而且，在保持了网络连通性的同时，随着网络中节点密度的增加，4种拓扑控制分别将节点平均度控制在了4种不同的范围（UDG:［27.01,30.13］，CBTC:［8.04,8.61］，LMST:［2.04,2.05］，GG:［3.6,3.74］），总体上观察发现，LMST与GG的平均度约束要优于UDG与CBTC.节点的平均通信半径开始逐渐进入一个小的波动范围.而在节点数为60的情况下，网络拓扑中的节点平均通信半径和平均度都还没有进入一个稳定值，是一个不确定的浮动区域，在此环境中得到的仿真结果具有随机性.

如图4所示，相同实验环境及实验参数下，在图3中对节点平均度约束得比较好的拓扑控制算法在提高网络的生存期方面比较占优势，这表示，在Ad Hoc网络中进行平均节点度的约束，确实可以延长网络生存期.

且从实验结果中可以发现，2种网络生存期模型支撑下，4种拓扑控制影响下的生命周期在节点数为［125,200］时，将陆续开始进入一种饱和状态.结果符合第3节的分析.本节仿真实验的结果验证了我们对网络拓扑固有参数的影响的分析.

3.4 实验结论

从仿真实验发现，当节点数处于［125,200］（节点密度为［0.125,0.2］，单位：个/单位面积）范围中的某一值时，不同的拓扑控制策略下的节点平均度和其影响下的节点平均通信半径开始进入一个很小的波动范围，近似于稳态.

由此可以推导出网络拓扑中的固有参数的拓扑控制力的饱和状态趋向约束条件：

N/A=λassumption0.15≤λassumption≤0.2,λassumption∈R(10)

此时，实施拓扑控制的网络的平均通信半径的值也将趋近在关系式(4)所示范围中.

所以，在用实验仿真考察拓扑控制性能时，节点密度的考察范围应该设置到饱和状态为止，即进入饱和状态趋向约束条件的下界，而不宜超过其上界.因为，考察的节点密度范围的上界设置过高或过低都会失去对拓扑控制策略的真正性能的把握.只考虑到过低的状态，则会导致忽略了拓扑控制策略在更大密度处更好发挥的可能性；而过高的扩大节点范围，则会由于已经进入饱和状态，而不会发现拓扑控制对网络生存期的进一步优化效果.

综上所述，在分析拓扑控制性能的时候，认知到饱和阶段的存在，是必不可少的.在对此类拓扑控制进行评估的过程中，仿真环境的搭建应该有针对性地考虑到这个阶段为止，以提升实验仿真过程的合理性.

4 结语

[JP2]

本文利用2种网络生存期模型，从节点平均能耗的角度出发，仿真实验结果证实节点平均度的约束可以延长网络生存期；理论推导过程中发现节点密度约束了平均度约束下的通信半径的变化；从实验结果发现，在一定的拓扑固有参数的制约下，拓扑控制策略对网络生存期的优化能力将陆续达到饱和.[JP]

因此，在分析拓扑控制对网络生存期的优化性过程中，节点密度的考察范围应该设置到饱和状态为止，从而提升对拓扑控制性能分析的有效性.[FL）]

参考文献:

［1］XU Y, BIEN S, MORI Y, et al. Topology control protocols to conserve energy in wireless Ad Hoc networks ［J］. IEEE Transaction on Mobile Computing,2003(1):174-192.

［2］陈力军,毛莺池,陈道蓄,等.平均度约束的无线传感器网络拓扑控制［J］.计算机学报,2007,30(9):1544-1550.

［3］NEWMAN M E J．Random graphs as models of networks［M］//BORNHOLDT S，SCHUSTER H G. Handbook of Graphs and NETWORKS．Berlin：Wiley-VCH，2003：35-68.

［4］BORKAR V S, MANJUNATH D. Distributed topology control of wireless networks［J］.Wireless Networks,2008,14(5):671-682.

［5］张学,陆桑璐,陈贵海,等.无线传感器网络的拓扑控制［J］.软件学报,2007,18(4):943-954.

［6］王炫,李建东,张文柱.拓扑控制对AdHoc网络性能的影响［J］.计算机科学,2006,33(6):44-47.

［7］路纲,周明天,牛新征,等.无线网络邻近图综述［J］.软件学报,2008,19(4):888-911.

［8］KAWADIA V, KUMAR P R. Principles and protocols for power control in wireless Ad Hoc networks［J］．IEEE JSAC,2005,23(1):76-88.

［9］FALL K,VARODHAN K. The ns manual［EB/OL］. www.isi.edu/nsnam/ns/doc/ns_doc.pdf.

［10］ LI N,HOU J C, SHA L. Design and analysis of an MSTbased topology control algorithm［C］// Proc IEEE INFOCOM'03. San Francisco,2003:1702-1712.

［11］BORBASH S A, JENNINGS E. Distributed topology control algorithm for multihop wireless networks［C］//Proc IEEE Int Joint Conference on Neural Networks. Hawaii,2002:355-360.

［12］LI L, HALPERN J Y, BAHL P, et al. A conebased distributed topologycontrol algorithm for wireless multihop networks［J］.IEEE/ACM Transactions on Networking, 2005,13(1):147-159.

［13］LI X Y. Algorithmic, geometric and graphs issues in wireless networks［J］. Wireless Comm and Mobile Computing, 2003,3(2):119-140.

［14］HEINZELMAN W. Applicationspecific protocol architectures for wireless networks［D］.Cambridge:Mass Inst Technol,2000.