移动自组网基于能量效率的分布式拓扑控制算法

ＩＳＳＮ　１０００－９８２５．ＣＯＤＥＮ　ＲＵＸＵＥＷ　Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ。Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７，ＰＰ．７０２－７１３　１３ＯＩ：１０．１３６０／ｊｏｓ１８０７０２　Ｅ－ｍａｉｌ：ｊｏｓ＠ｉｓｃａｓ．ａｃ．ｃｎ　ｈｔｔｐ：／／ｗｗｗｊｏｓ．ｏｒｇ．ｃｎ　Ｔｅｌ，】１ａｘ：＋８６－ｌＯ．６２５６２５６３　ｏ２００７ｂｙＪｏｕｒｎａｌｏｆＳｏｆｔｗａｒｅ．Ａｌｌ　ｒｉｇｈｔｓ　ｒｅｓｅｒｖｅｄ．　移动自组网基于能量效率的分布式拓扑控制算法　罗玉宏　，王建新，黄家玮，陈松乔　（中南大学信息科学与工程学院，湖南长沙４１００８３）　Ａｎ　Ｅｎｅｒｇｙ－Ｅｆｉｆｃｉｅｎｔ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｔｏｐｏｌｏｇｙ—Ｃｏｎｔｒｏｌ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ａｄ　Ｈｏ￣Ｎｅｔｗｏｒｋｓ　ＬＵＯ　Ｙｕ－Ｈｏｎｇ　，ＷＡＮＧ　Ｊｉａｎ－Ｘｉｎ，ＨＵＡＮＧ　Ｊｉａ－Ｗｅｉ，ＣＨＥＮ　Ｓｏｎｇ－Ｑｉａｏ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｅｎｔｒａｌ　Ｓｏｕｔｈ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ　４１００８３，Ｃｈｉｎａ）　＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ａｕｔｈｏｒ：Ｐｌｍ：＋８６－７３１－８８３０２１２，Ｆａｘ：＋８６－７３１－８８３０２１２，Ｅ－ｍａｉｌ：ｌｙｈｙｓｔ＠ｐｕｂｌｉｃ．ＣＳ．ｈｎ．ｃｎ　Ｌｕｏ　ＹＨ，Ｗａｎｇ　ＪＸ，Ｈｕａｎｇ　ＪＷ，Ｃｈｅｎ　ＳＱ．Ａｎ　ｅｎｅｒｇｙ－ｅｆｉｆｃｉｅｎｔ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｏｐｏｌｏｇｙ－ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ａｄ　ｈｏ￣ｎｅｔｗｏｒｋｓ．Ｊｏｕｒｎａｌ　ｏｆＳｏｆｔｗａｒｅ，２００７，ｌ８Ｏ）：７０２－７１３．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／ｌＯ００－９８２５／１８／７０２．ｈｔｍ　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｔｏｐｏｌｏｇｙ　ｏｆ　ａ　ｗｉｒｅｌｅｓｓ　ｍｕｌｔｉ—ｈｏｐ　ｎｅｔｗｏｒｋ　Ｃａｌｌ　ｂｅ　ｃｏｎｔｒｏｌｌｅｄ　ｂｙ　ｖａｒｙｉｎｇ　ｔｈｅ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｐｏｗｅｒ　ａｔ　ｅａｃｈ　ｎｏｄｅ．Ｔｈｅ　ｐｒｉｍａｒｙ　ｇｏａｌ　ｏｆ　ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　ｉｓ　ｔｏ　ｄｅｓｉｇｎ　ｐｏｗｅｒ－ｅｆｉｆｃｉｅｎｔ　ａｌｇｏｒｉｈｔｍｓ　ｔｈａｔ　ｍａｉｎｔａｉｎ　ｎｅｔｗｏｒｋ　ｃｏｎｎｅｃｔｉｖｉｔｙ　ａｎｄ　ｏｐｔｉｍｉｚｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｍｅｔｒｉｃｓ　ｓｕｃｈ　ａｓ　ｎｏｄｅｓ　ｌｉｆｅｔｉｍｅ　ａｎｄ　ｔｈｒｏｕｇｈｐｕｔ．　Ａｎ　ｅｎｅｒｇｙ—ｅｆｉｆｃｉｅｎｔ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｏｐｏｌｏｇｙ－ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｐｒｏｐｏｓｅｄ，ｂｒｉｅｆｌｙ　ｃａｌｌｅｄ　ＶＣＧＧ（Ａ　ｖａｒｙｉｎｇ－ｃｏｎｅ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｏｐｏｌｏｇｙ—ｃｏｎｔｒｏｌ　Ｍｇｏｆｉｔｈｍ　ｏｎ　Ｇａｂｒｉｅｌ　ｇｒａｐｈ）．Ｕｓｉｎｇ　ａ　ｎｅｗ　ｍｅｃｈａｎｉｓｍ　ｏｆ　ｓｅｌｃｅｔｉｎｇ　ｔｈｅ　ｌｏｇｉｃ　ｎｅｉｇｈｂｏｒ　ｎｏｄｅｓ　ｂｙ　ｉｆｒｓｔｌｙ　ｄｅｌｅｔｉｎｇ　ｈｔｅ　ｆａｒｔｈｅｓｔ　ｎｏｄｅ（ＦＤＦＮ），ｔｈｅ　ＶＣＧＧ　ｌａｇｏｒｉｈｔｍ　ｂｕｉｌｄｓ　ａ　ｄｅｇｒｅｅ－ｂｏｕｎｄｅｄ，ｐｏｗｅｒ　ｓｐａｎｎｅｒ　ｎａｄ　ｐｌｎａａｒ　ｓｕｂｇｒａｐｈ　ｂｙ　ｍａｋｉｎｇ　ｕｓｅ　ｏｆ　ｍｅｒｉｔ　ｏｆ　ｔｈｅ　ｖａｒｙｉｎｇ　ｃｏｎｅ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ＶＣＧＧ　ａｌｇｏｒｉｔｈｍ　ｐｅｒｆｏｒｍｓ　ｂｅｔｔｅｒ，ｉｎ　ｔｅｒｍｓ　ｏｆ　ｐｏｗｅｒ　ｅｆｉｆｃｉｅｎｃｙ，ｎｕｍｂｅｒ　ｏｆ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｉｇｈｂｏｒｓ　ａｎｄ　ｉｎｔｅｒｆｅｒｅｎｃｅ，ｔｈａｎ　ｔｈｅ　ｅｘｉｓｔｉｎｇ　ＳＯＧＧａｎｄＳＹａｏＧＧａｌｇｏｒｉｔｈｍｓ．　Ｋｅｙ　ｗｏｒｄｓ：ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋ；ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ；ｅｎｅｒｇｙ－ｅｆｉｆｃｉｅｎｔ；ｏｐｔｉｍａｌ　ｐｏｗｅｒ；ｔ－ｓｐａｎｎｅｒ　摘要：移动自组网中，网络的拓扑结构可以通过调节每个节点的传输功率加以控制，拓扑控制的基本目标是　设计基于功率优化的算法，既能维护网络的连通性，又能降低节点的传输功率，延长节点的生存时间，达到优化网　络性能的目的．在ＧＧ图的基础上，提出了一种基于能量效率的拓扑控制算法ＶＣＧＧ（ａ　ｖａｒｙｉｎｇ－ｃｏｎｅ　ｄｉｓｔｒｉｂｕｔｄｅ　ｔｏｐｏｌｏｇｙ—ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｈｔｍ　ｏｎ　Ｇａｂｒｉｅｌ　ｇｒａｐｈ）．算法采用可变扇区的思想，运用优先删除最远节点的方法（ＦＤＦＮ）选　择逻辑邻居节点，建立了一个度有界、平面、干扰小的　支撑图．模拟结果显示：ＶＣＧＧ算法与ＳＯＧＧ￣ＳＹａｏＣ￣　等算法相比，减少了节点的传输功率，降低了通信邻居节点的数目，减轻了邻居节点的干扰，提高了能量的使用　效率．　关键词：　移动自组网；拓扑控制；能量效率；功率优化；　支撑图　・Ｓｕｐｐｏｒｔｄｅ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏｓ．９０３０４０１０，６０６７３１６４（国家自然科学基金）；ｔｈｅ　Ｐｒｏｇｒａｍ　ｆｏｒ　Ｎｅｗ　Ｃｅｎｔｕｒｙ　Ｅｘｃｅｌｌｅｎｔ　Ｔａｌｅｎｔｓ　ｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．ＮＣＥＴ－０５－０６８３（新世纪优秀人才支持计划）：ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ　Ｆｏｕｎｄａｔｉｏｎ　ｆｏｒ　ｔｈｅ　Ｄｏｃｔｏｒａｌ　Ｐｒｏｇｒａｍ　ｏｆ　Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｅｄｕｃａｔｉｏｎ　ｆｏ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．２００６０５３３０５７（国家教育部博　士点基金）：ｔｈｅ　Ｐｒｏｖｉｎｃｉａｌ　Ｎａｔｕｒｌａ　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｈｕ’ｎａｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　Ｇｒａｎｔ　Ｎｏ．０６ＪＪｌ０（［０９（湖南省杰出青年基金）；ｔｈｅ　Ｓｃｉｅｎｔ／ｉｔｃＲｅｓｅａｒｃｈＦｕｎｄ　ｏｆＨｕ’ｎａｎＰｒｏｖｉｎｃｉｌａＥｄｕｃａｆｉｏｎＤｅｐａｒｔｍｅｎｔｏｆＣｈｉｎａ　ｕｎｄｅｒＧｒａｎｔＮｏ．０５Ｄ０５４（湖南省教育厅资助科研项目）　Ｒｅｃｅｉｖｅｄ　２啡Ｏｌ－ｌｌ：Ａｃｃｅｐｔｅｄ　２００６－０４－０３　维普资讯 http://www.cqvip.com

罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７０３　中图法分类号：ＴＰ３９３　文献标识码：Ａ　移动自组网是在没有中心基础设施的情况下，由一些移动用户自组织形成的多跳无线移动网络，具有动态　变化的网络拓扑结构、有限的无线传输带宽、移动终端的能量限制等特点．由于移动终端设备依赖于电池供电，　为了延长节点的工作时间，要求尽量减少节点的能量消耗，从而延长网络的使用寿命．文献【ｌ，２】提到，节点发送的　信号既可以同时被传送范围内的多个节点接收，也可能对它们的通信造成干扰．因此，每个节点可以通过调整自　身的传输功率来控制邻居节点的数目，改变网络的拓扑结构．拓扑控制是设计基于功率优化的算法，既能维护网　络的连通性，又能降低节点的传输功率，延长节点的生存时间，达到优化网络性能的目的ｌｊ’　．　研究通常假设节点的传输功率为ｐ　）＝　样，即　，＝ｌ，ｃ＝０．拓扑控制问题描述如下：　ｃ，其ｑａ：Ｋ是天线属性的常量；　是节点Ｕ的传输距离；腥无线　传输介质能量损耗的常量（２　４）；ｃ是硬件和数据处理所消耗的能量．研究中通常假设所有节点的　和Ｃ都一　集合Ｖ中　个节点随机分布在一个二维的平面中。每个节点的最大传输范围是１．这些节点构成一个　ＵＤＧ（／／）（ｕｎｉｔｄｉｓｋｇｒａｐｈ）图：６　（　），层＝｛（“，ｖ）ｌｄ（ｕ，ｖ）　１），吠“，ｖ）是节点Ｕ和ｖ之间的距离【５】．我们的目标是找一个子　图Ｇ，，包含Ｇ中所有的节点和比Ｇ更少的边，并且满足以下要求：　（１）连通性：如果Ｇ是连通的，那么Ｇ　也是连通的．　（２）　支撑［］（ｔ－ｓｐａｎｎｅｒ）　卅：在图Ｇ中，对任意一对节点ｕ，ｖＥ　它们之间功率的最小消耗是ＰＧ（“，ｖ）．在子图Ｇ，　中，若满足条件ＰＧ，（　ｖ）　ｆ　Ｇ（“，ｖ），则称Ｇ，是Ｇ的　支撑图，ｔ称为功率伸长因子（ｐｏｗｅｒ　ｓｐａｎｎｉｎｇ　ｒａｔｉｏ）．如果ＰＧ（“，ｖ）　用长度来代替，则称ｔ为长度伸长因子．　（３）度有界（ｄｅｇｒｅｅ　ｂｏｕｎｄｅｄ）：子图Ｇ　的度被限制在一个小的常数范围内，即｛ｄｅｇｒｅｅ（ｖ）ｌｄｅｇｒｅｅ（ｖ）＜ｃ，　ｖＶＥＧ　），Ｃ是一个小的常数．限制节点的度，可以减少ＭＡＣ层的冲突和干扰，减轻隐终端和显终端问题，降低节点　的传输功率，提高网络的吞吐量【７’８】．　（４）平面（ｐｌａｎａｒ）性：在网络拓扑图中，任意两条边都是不相交的．拓扑图的平面特性可以使一些分布式的路　由协议（如ＧＰＳＲ［９］、ＧＯＡＦＲ！’Ｄ】等）在没有路由表的情况下实现信息的正确、高效转发．　１相关研究　拓扑控制的研究一般基于以下３种基本的网络拓扑结构…　：　ＲＮＧ（ｒｅｌａｔｉｖｅ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｇｒａｐｈ）［［１２１：包含所有的边ＵＶ。不存在任何点ｗ∈Ｖ满足Ｉｌｕｗｌｌ＜ｌｌｕｖｌｌＲＩ１ｗｖｌｌ＜ｌｌｕｖｌ１．　ＧＧ（Ｇａｂｒｉｅｌ　ｇｒａｐｈ）［ｔ　：包含所有的边ＵＶ，不存在任何点ｗ∈Ｖ位于以边ＵＶ为直径构成的圆区域内．　ＹＧ，（Ｖ）（Ｙａｏ　ｇｒａｐｈ）［ｔ¨　：对任一整数　６，以节点Ｕ为源点，发散出ｋ条等分射线，形成ｋ个扇区．在每个扇区　中，选择最短的边ＵＶ，如果这样的边存在，则增加一条有向边　，最终形成有向图ｙＧｔ（　）图．　文献［１５】提出了一种集中式算法ＰｌａｎａｒＳｐａｎｎｅｒ，建立一个度有界、平面的、低权值的　支撑图，时间复杂度　是Ｏ（ｎｌｏｇｎ），通信开销最坏达到Ｏ（ｎ　）．由于无线节点的资源限制，采用分布式算法来构造网络的拓扑结构更为合　理Ｉ　．文献【６】提出了集中式ＡＵＤｅｌ（ａｕｇｍｅｎｔ　ｕｎｉｔ　ｄｅｌａｕｎａｙ　ｔｒｉａｎｇｕｌａｔｉｏｎ）和相应的分布式算法，用来构造平面　的　支撑图，它的通信开销为Ｄ（　），但没有给出具体的功率伸长因子和度上界．文献【ｌ７】采用算法ＣＢＴＣ（ｃｏｎｅ　ｂａｓｅｄ　ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏ１）提出了一个类似于Ｙａｏ图的拓扑结构，能够较好地降低节点的传输功率．区别在于：Ｙａｏ　的扇区数目是一个常量｜ｊ｝；而ＣＢＴＣ的扇区数目是可变的，最大可达到２　．当ａ￣５ｒｃ／６时，如果ＵＤＧ图是连通的，　那么ＣＢＴＣ　图也一定是连通的，当ａ＞５ｒｃ／６时，则不能保证ＣＢＴＣ图的连通性．另外，ＣＢＴＣ图不满足平面、度有界、　支撑图等特性．文献【ｌ８】提出了一种分布式算法ＢＰＳ（Ｄｅｇｒｅｅ。ｂｏｕｎｄｅｄｐｌｎａｒａ　ｓｐａｎｎｅｒ），用于建立一个度有界、平　面的　支撑图，但它理论上的度边界可以达到一个很大的值．例如，当ａ＝ｇ／６时，度边界高达２５．另外，虽然ＢＰＳ的　通信开销理论上只有Ｄ（　），实际上，为了收集两跳邻居节点的信息所付出的开销是巨大的．文献【ｌ９】在ＧＧ图上　构造Ｙａｏ图，提出了ＯｒｄＹａｏＧＧ和ＳＹａｏＧＧ两种方法构造度有界、平面的　支撑图，比ＢＰＳ算法具有更好的性　能和更低的通信开销．ＳＹａｏＧＧ仅用了３　的通信开销，确保了在　９等分的每个圆锥扇形中至多有一个邻居节　维普资讯 http://www.cqvip.com

Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７　点．文献【ｌｌ】提出的Ｓ＠ＧＧ算法采用６控制域的方法构造了一个度有界、平面的ｆ一支撑图，比ＳＹａｏＧＧ算法具有　更少的节点的度、传输功率和节点干扰．　表１列出了几种常见拓扑控制算法的特征．由表１可以看出，Ｓ￣ＧＧ算法具有节点度最小、节点干扰少、通　信开销小等优点，是一种比较好的分布式算法．但是，实验结果ｆ¨】显示：它与ＳＹａｏＧＧ算法一样，都不能有效降低　ＧＧ图中节点的传输功率、减少最大邻居节点的干扰．　Ｔａｂｌｅ　１　Ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｃｕｒｒｅｎｔ　ａｐｐｒｏａｃｈｅｓ　表１几种常见拓扑控制算法的特征表　’Ｕｓｉｎｇ　ｌｅｎｇｔｈ　ｓｐａｎｎｉｎｇ　ｒａｔｉｏ　本文在ＧＧ图的基础上提出一种基于能量效率的拓扑控制算法ＶＣＧＧ（ａ　ｖａｒｙｉｎｇ—ｃｏｎｅ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｏｐｏｌｏｇｙ－ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｔｈｍ　ｏｎ　Ｇａｂｒｉｅｌ　ｇｒａｐｈ）．算法采用可变扇区的思想，运用优先删除最远节点的方法ＦＤＦＮ　（ｉｆｒｓｔｌｙ　ｄｅｌｅｔｉｎｇ　ｔｈｅ　ｆａｒｔｈｅｓｔ　ｎ０ｄｅ）选择逻辑邻居节点，建立一个度有界、平面、干扰小的ｆ一支撑图，能够较好地减　少通信节点的数目，降低节点的传输功率和最大邻居节点的干扰．　２　ＶＣＧＧ算法　２．１可变扇区的选取方法　ＶＧＧＧ算法在可变扇区使用了　控制域的概念，　控制域的定义如下：　定义１．　控制域…】：对于“的邻居节点ｖ，它的　控制域是以“为源点，“ｖ为轴心２倍缃扇形区域．　图ｌ给出了节点“的邻居节点ｖ的啦制域的图示．　ＶＣＧＧ算法是在ＧＧ图的基础上，采用优先删除最远节点的　方法ＦＤＦＮ选择逻辑邻居节点：　（１）对于节点“的黑色邻居节点（已经进行逻辑邻居节点选　择处理的节点，标记为黑色节点，未进行逻辑邻居节点选择的节　点，标记为白色节点），节点“依次按照距离　从近到远选择黑色　Ｆｉｇ．１　Ｎｏｄｅ　Ｖ＇Ｓ　ｇ—ｄｏｍｉｎａｔｉｎｇ　ｒｅｇｉｏｎ　ｗｉｔｈ　邻居节点　是节点Ｗ到节点“的距离），删除所有位于节点Ｗ　ｒｅｓｐｅｃｔ　ｔｏ　ｎｏｄｅ“　的啦制域内的节点的连接；　（２）处理完黑色邻居节点后，如果剩余的白色邻居节点中　最大，节点“优先选择邻居节点ｗ，使节点ｖ位于节点Ｗ的　控制　图１节点“的邻居节点ｖ的ｇ控制域　域内（所有满足这个条件节点中　最小）．删除所有与节点Ｗ冲突的节点的连接（包括节点ｖ）．重复这个步骤，直到　维普资讯 http://www.cqvip.com

罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７０５　小于已经选择的逻辑邻居节点距离，再按照（１）的方法处理剩下的白色节点．详细描述见算法１．　定理１．在ＶＣＧＧ算法中，对　控制域进行如下限制：　（１）如果节点Ｕ选择的邻居节点ｗ是黑色的，则节点ｗ对白色节点ｖ（　望　的　控制域小于　／３，对白色节点　＞ｄ０的　控制域小于　／４，对黑色节点的　控制域小于２ａｒｅｓｉｎ２　；　一　ｌ　一一／，●●　　２　一　哩　（２）如果节点Ｕ选择的邻居节点ｗ是白色的，则节点ｗ对白色节点ｖ（　的　控制域小于２ａｒｃｓｉｎ２　，　对白色节点　＞　的　控制域小于ｎ／６．　可以保证ＶＣＧＧ图的　支撑图的特性．　证明：如图２所示，假设ｗ，ｖ是节点Ｕ的邻居节点，Ｏ＝Ｌｗｕｖ＇，ｘ，Ｕ是节点ｗ的邻居节点，＿Ｊ　ｙ＝Ｌｕｗｘ，按照新的节点　选取方法。处理节点的方法分以下几种情况：　１）ｗ是黑色节点，ｖ是白色节点，Ｉｌｕｗｌｌ￣＜ｌｌｕｖｌｌ（如图２（ａ）所示）．节点Ｕ选择节点ｗ删除了与节点ｖ的连接，得到　的功率伸长因子为　／　、口　Ｉ　ｖＩｒ＝　叫ｒ＋ｐ（ｗ，…，ｖ）≤０　ｒ＋ｒ・Ｈ　≤０叫ｒ＋ｒ・【２・ｓｉｎ　．　ｌ　ｒ．　ｖＩｒ，　１洧ｆ＝　（当Ｏ＝ｎ／３一　０）时条件成立）；　２）ｗ是黑色币点，Ｖ是日色币点，Ｉｌｕｗｌｌ＞ｌｌｕｖｌｌ（￣幽２（ｂ）所不）．币点Ｕ　ｊ韪掸节点ｗ删除＇ｒ与节点Ｖ的踅援，得到　的功率伸长因子为：　令ｔ／＝Ｚｗｖｕ，由ＧＧ图的特性可知，ｒｌ＜ｎ／２．　ｓｉｎＴ／＝　‘　，Ｈ＝Ｈ‘　ｓｉｎ０，　・Ｈ　．１ｌ　（　．１ｌ　得到ｆ≥　万ｓ　ｉｎ　￣ｒ／　，有ｆ　巧（当　＞　／２，　／４一　ｏ），条件成立）；　３）ｗ是白色节点，ｌ　ｗＩＩ＜ＩＩ“ｖｌｌ　是黑色节点，ＩＩ￣ｘｌｌ＜－ｌｌ“ｗｌｌ（如图２（ｃ）所示）．首先，处理节点“时，选择节　ｗ删除　了与节点ｖ的连接；然后，处理节点ｗ时，选择节点　删除了与节点Ｕ的连接．得到的功率伸长因子为　Ｉ　＝ｐ（　．．，ｘ）＋ｌｌｗ￣ｌｌ　＋ｐ（ｗ，．．．，ｖ）＜ｆ．Ｉｌｕｑ　＋ＩＩ　¨０叫ｒ　。　『２．ｓ　＋　¨　“　圳　，　删　１习洧　１　（令　当０－２ａｒｃｓｉｎ２　一坐　占（　０）时条件成立）；　４）ｗ是白色节点，Ｉｌｕｗｌｌ＞ｌｌｕｖｌｌ，ｘ是黑色节点，ＩｌｗｘｌＮｌｕｗｌｌ（￣［］２（ｄ）所示）．首先，处理节点Ｕ时，选择节点ｗ删除　了与节点ｖ的连接；然后，处理节点ｗ时，选择节点　删除了与节点Ｕ的连接．得到的功率伸长因子为　Ｉ　＝ｐ（　．．，　）＋ｌｌｗ￣ｌｌ　＋ｐ（ｗ’．．．＇ｖ）＜ｆ．Ｉｌｕ￣ｌｌ　＋Ｉ　Ｉ　＋ｆ．０ｗ叫Ｉ　ｓ　Ｉ　．１Ｉ叫Ｉ）　¨　删ｓｉｎ０　维普资讯 http://www.cqvip.com

Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７　得到ｆ　：＝＝　：　：　１　成立、ｉ－．　，有ｆ　：：　二　：　１　（当　２ａｒｃｓｍ．２　一　’　７ｃ／６一　。）时条件　口　综上所述，ＶＣＧＧ算法通过对啦制域的限制可以保证ＶＣＧＧ图的卜支撑图特性．　（ａ）Ｔｈｅ　ｌｉｎｋ　ｍ　ｉｓ　ｋｅｐｔ　ｗｈｅｎ　Ｉｌｕｗｌｌ￣ｌｌｕｖｌｌ　（ａ）ｌｌｍ卅　“ｖｌｌ，连接“ｗ被保留　（ｂ）Ｔｈｅｌｉｎｋ“ｗｉｓｋｅｐｔｗｈｅｎ　ｗＩ　ｌｎ，Ｉ　（ｂ）ｌ￣ｌｌ＞ｌｌｕｖｌｌ，连接ｌｎ‘，被保留　‘　一ｌ＋口　一　一　０　ｖ　．　（ｃ）Ｔｈｅ　ｌｉｎｋ　ｕｗ　ｉｓ　ｒｅｍｏｖｅｄ　ｗｈｅｎ　Ｉｌｕｗｌｌ￣ｌｌｕｖｌ　（ｃ）Ｉｌｕ￣ｌｌｇｌｌｕｖｉｌ，连接ＵＷ被移走　Ｆｉｇ．２　Ｎｏｄｅ“ｓｅｌｅｃｔｓ　ｌｏｇｉｃａｌ　ｎｅｉｇｈｂｏｒｓ　图２节点“选择逻辑邻居节点　一　推论１．在ｖＣＧＧ算法中，　控制域的选取方式满足　＝２ａｘｃｓｉｎ２　一２ｎ／ｋ，　９，２　４，可以得到比ＳｙａｏＧＧ　和ＳＯＧＧ算法更好的功率伸长因子．　ｓＹ一和ｓ　…功…盱　’２　“＇１明．自趣旧　知：ＶＣＧＧ的功率伸长因子与节点的个数无关，只与啦制域中　的取值有关．令　＝２ａｘｃｓｉｎ２　一２ｎ／ｋ，ｋ≥９，　２≤　，则定理１中情形：　（１）０＝ｎｌ３一　ｌ一（２咖　一［２ｓｉｎ（　＋　６　Ｊｌ　’　（　）　只要证明　ｌ－（２　即　维普资讯 http://www.cqvip.com

罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７０７　ｃ√　（　一［２ｓ　［量＋詈一ａｒｃｓ　２　］］　］＋（２√　ｓ　．　对不等式左边函数　求导，有厂　（　＞Ｏ，得知　是一个单调递增的函数，当　２时取最小值：　２（　一４ｓ　ｎ　（量＋詈－ａｒｃｓｉｎ２－￣＇５］］＋８ｓ　量＞２（　一４ｓ　（号＋詈一２。．７。］］＋８ｓ　詈＞　．。　＞　．　所以情形（１）中，当／Ｌ＞＿９，２　４时，ＶＣＧＧ算法的功率伸长因子小于ＳＹａｏＧＧ和ＳＯＧＧ算法的功率伸长因子．　１　‘，　ｃｏｓｐ０一ｓｉｎｐ０　肿　…一　尚‘　所以情形（２）中，当　９，２Ｓ　４时，ＶＣＧＧ算法的功率伸长因子小于ＳＹａｏＧＧ和ＳＯＧＧ算法的功率伸长因子．　Ｉ＋ｐ（３）　：２ａｒｃｓｉｎ２　—　：孕，　‘　（２ｓ１　　詈］　一　２ｓ１　＜尚一（２　‘　所以情形（３）中，当　９，２　４时，ＶＣＧＧ算法的功率伸长因子小于ＳＹａｏＧＧ和ＳＯＧＧ算法的功率伸长因子．　‘，——．．．．．．．．．．．．．．．．．．．．．．．　！．．．．．．．．　．．．一——．．．．．．．．．．．．．．．．．．．．．．．！．．．．．．．．　．．．一　ｃ。ｓ　一ｓ　一（２ｓ　］　ｃ。ｓ　一ｓ；ｎ　一（２ｓｍ．量］　’　用（１）中的方法同理可证ｆ　—　丝　—　．　１一ｆ、　、　２　ｓｍ．　１／　所以情形（４）中，当　９，２　Ｉ＜４时，ＶＣＧＧ算法的功率伸长因子小于ＳＹａｏＧＧ和ＳＯＣＫ｝算法的功率伸长因子．　生　因此，节点“在选择邻居节点时，如果啦制域选取时，　＝２ａｒ￣ｓｉｎ２　一２ｒｃ／ｋ，娩９，２　４，可以得到比　ＳＹａｏＧＧ和ＳＯＧＧ算法更好的功率伸长因子．　口　定义２．扇区　为相邻两逻辑节点的夹角．　如图３所示，节点“选择了两个逻辑邻居节点ｗ，１，，扇区　为夹角Ｚｗｕｖ形成的扇形区域．当扇区驴２　时，如果　在　２　阴影部分至少存在一个邻居节点，为了保证ＶＣＧＧ图的ｆ－支撑图特性，必须增加＿个新的逻辑邻居节　点．由于各逻辑邻居节点的　控制域是可变的，它与各逻辑邻居节点的处理状态、到节点“的距离有关，因此，扇　区　的大小也是可变的．只有当扇区　或者ａ－２０的阴影部分不存在邻居节点时，ＶＣＧＧ图才是ｆ－支撑　图．ＶＣＧＧ算法采用可变扇区的思想，比ＳＹａｏＧＧ和ＳＯＧＧ算法的等分扇区和等分　控制域更加灵活，能够更好　地减少逻辑邻居节点的度，降低节点的传输功率，减少邻居节点的干扰．　／ｒ　、　定理２．令　＝２　Ｉ／　　ｒＪ６＋２ａｒｃｓｉｎ２　一２ｅ　／ＩＪ　，如果Ｍ为小数，则ｖｃｏｏ算法的度上界为２［ＭＪ；Ｗ￣Ｕ，ＶＣＧＧ　算法的度上界为２Ｍ－１．　维普资讯 http://www.cqvip.com

Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７　Ｆｉｇ．３　Ａ　ｃｇ￣ｃｏｎｅｂｅｔｗｅｅｎｔｈｅｎｅｉｇｈｂｏｒｎｏｄｅｗａｎｄ　Ｖｏｆｎｏｄｅ　图３节点“的邻居节点Ｗ。ｖ形成一个　区　证明：由定理１的　控制域的选取方式可知，在情形（４）选择白色节点时，ＶＣＧＧ的度可能达到最大．在最坏情　况下，节点“在选择逻辑邻居节点的时候，逻辑节点最小的啪制域分别为ｎ／６一占和２ａｒｃｓｉｎ２卢一　（　）．于是，在　“　一、　个圆形区域中，最多可以有Ｍ＝２兀／Ｉ／　　＋２ａｒｃｓｉｎ２　一２ｅ　１个这样的控制域，如果　是小数，每个节点和节　对节点的控制域之间是重合的，不需要选择节点，所以ＶＣＧＧ算法的度上界为２Ｍ－１．　口　点的控制域之间最多有１个节点，如图３阴影部分所示，则ＶＣＧＧ算法的度上界为２ｔ￣Ｊ；如果　是整数，至少有　一２．２　ＶＣＧＧ算法　ＶＣＧＧ算法运用了可变扇区的思想和ＦＤＦＮ逻辑节点选择策略，具体描述如下：　１．采用文献【ｌ９１中的分布式算法构造一个ＧＧ图，每个节点均为白色（未处理），并且具有唯一的ＩＤ．　２．当节点“比所有白色邻居节点具有更小的ＩＤ时，它选择逻辑邻居节点的方法如下：　（１）节点“先将它所有黑色邻居节点（已处理）按照距离从近到远的顺序排序，将排好序的结果写入到它的　邻居列表朋　），再将它所有的白色邻居节点按照从近到远的距离顺序排序，将排好序的结果写入到临时列表　Ｎｗ（ｕ）．　（２）从左到右依次扫描Ｎｂ（ｕ）中的节点．在每一步操作中，假设指针当前指向的节点是Ｗ，先保留指针位置，　删除列表Ｎｂ（ｕ）中节点Ｗ右边所有与Ｗ冲突的节点和列表Ｎｗ（ｕ）中所有与Ｗ冲突的节点，假设删除的节点为ｖ，　那么，节点ｖ位于节点Ｗ的啪制域（啪制域满足定理１中条件（１）要求）．节点Ｗ处理完毕后，指向节点Ｗ的指针　位置后移ｌ位．如果列表Ｎ＇ｂ（ｕ）中的节点都扫描完毕，进入第（３）步．　（３）如果邻居列表Ｎｗ（ｕ）不为空，并且列表Ｎｗ（ｕ）￣Ｏ最右边的节点到“的距离大于列表朋｝（“）中所有节点到　“的距离．从左到右搜索Ｎｗ（ｕ）中的节点，如果存在节点ｘ位于列表Ｎｗ（ｕ）最右边节点的　控制域　ｌ，　，　、　０＝２ａｒｃｓｉｎ２卢Ｉ，则删除列表ⅣＨ，（“）中节点ｘ右边所有与ｘ冲突的节点ｖ（啪制域满足定理１中条件（２）），将节　　＋点　移到列表Ｎｂ（ｕ），重复步骤（３）；否则，将列表Ｎｗ（ｕ）最右边的节点移到列表Ｎｂ（ｕ），进入步聚（４）．　（４）如果邻居列表Ｎｗ（ｕ）不为空，则从左到右扫描Ｎｗ（ｕ）中的节点，假设当前指针指向的节点是　那么删除　ｌ＋　列表ＪＶＷｆｕ）￣点Ｗ右边所有与ｗ冲突的节点　控制域　２ａｒｃｓｉｎ２　）．列表Ⅳ¨，（“）中所有节点扫描完毕后，　将列表ⅣＨ，（“）中剩余的节点移到列表Ｎｂ（ｕ）．　（５）标记节点１．１为黑色，广播一个ＵｐｄａｔｅＮ信息给所有被删除的邻居节点ｖ．　’节点“选择逻辑邻居节点的算法描述见算法１．　３．如果任意节点ｖ收到来自邻居节点“的ＵｐｄａｔｅＮ信息，它将检查自己是否属于被节点“删除的节点之　列，如果是，节点ｖ从它的邻居列表中删除“；否则，节点ｖ标记“为黑色邻居节点．　４．节点处理完毕后，所有的剩余连接｛“＇，　ＥⅣ（　）；＇，ＥＧＧ｝组成最后的拓扑图，节点“缩小它的传输范围，仅可　覆盖它的所有逻辑邻居节点．　算法１．节点“选择邻居节点的算法．　维普资讯 http://www.cqvip.com

罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７０９　Ａｌｇｏｒｉｔｈｍ　Ｓｅｌｃｅｔ　＿Ｎｏｄｅ；　｛　Ｓｏｒｔ　ａｌｌ　ｂｌａｃｋ　ｎｅｉｇｈｂｏｒｓ　ｂｙ　ｄｉｓｔａｎｃｅ　ｔｏ　ａｒｒａｙ　Ｍｌ，【】；　／／朋ｌ，【】ｉｓ　ｔｈｅ　ｎｅｉｇｈｂｏｒｓ　ｌｉｓｔ　ｏｆ　ｎｏｄｅ“　Ｓｏｒｔ　ａｌｌｗｈｉｔｅｎｅｉｇｈｂｏ￣ｂｙｄｉｓｔａｎｃｅｔｏ　ａｒｒａｙ＾　【】；　／／Ｎｗ［】ｉｓｔｈｅｔｅｍｐｌｉｓｔｏｆｎｏｄｅ“　Ｆｏｒ（ｉ＝Ｏ；ｉ＜ｓｉｚｅ；ｉ＋＋）　／／ｓｉｚｅ　ｉｓ　ｈｅ　ｔｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　ｏｆａｒｒａｙ册口　｛　上生　Ｆｏｒ（ｊ＝ｉ＋１ｊ＜ｓｉｚｅｊ＋＋）Ｉｆ（ｃｏｎｅ（Ｎｂ［ｉ］，Ｎｂ［，】）＜２ａｒｃｓｉｎ２　）Ｄｅｌｅｔｅ＾　［，】；　／／ｃｏｎｅ（Ｎｂ［ｉ］，Ｎｂ０７）ｉｓｔｈｅａｎｇｌｅｚ￣［ｌｆｕＮｂ［，】　／／ｗｓｉｚｅｉｓｔｈｅｎｕｍｂｅｒｏｆｎｏｄｅｓ　ｏｆａｒｒａｙＮｗ［】　Ｆｏｒ（ｊ－Ｏｊ＜ｗ＿ｓｉｚｅｉ　）　｛　Ｉｆ（ｃｏｎｅ（Ｎｂ明￣ｖｗｏ１）＜ｕ／３＆＆ｌｌｕ，Ｎｂ明ＩＪ＜　［，】ＩＩ）ＤｅｌｅｔｅⅣＩ．’［，】；　Ｉｆ（ｃｏｎｅ（Ｎｂ［ｌｆ，Ｎｗ［１］）＜ｎ／４＆＆Ｉｌｕ，Ｎｂ［Ｏｌｌ－＞Ｉｌｕ，Ｎｗ［，】ＩＩ）Ｄｅｌｅｔｅ　Ｎｗ［，】；　／／ｌｌｕ３Ｖｂ［ｉ］ｌＩ　ｉｓ　ｈｅ　ｔｄｉｓｔａｎｃｅ　ｂｔｗｗｅｎ　ｎｏｄｅ“ａｎｄ朋ｌ，【ｆ】　｝　—Ｗｈｉｌｅ　Ｍ】＜＞，ｌ“　Ｄｏ｛　／／ｓｏｍｅ　ｗｈｉｔｅ　ｎｏｄｅｓ　ｓｔｉｌｌ　ｎｏｔ　ｂｅ　ｓｅｌｅｃｔｅｄ　１＋ｐ．．．．．．——　Ｆｏｒ（ｉ＝Ｏ；ｉ＜ｗ＿ｓｉｚｅ－１；ｉ＋＋）Ｉｆ（ｃｏｎｅ（Ｎｗ［ｉ］，Ｎｗ［ｗ＿ｓｉｚｅ－１］）＜２ａｒｃｓｉｎ２　）ｂｒｅａｋ；　Ｉｆ（ｉ＜＞ｗ＿ｓｉｚｅ－１＆＆ｌ［Ｎｗ［ｗ　ｓｉｚｅ－－１］，ｕｌｌ＞ｍａｘ（１ｌＮｂ［］，ｕｌ１））　｛　Ｆｏｒ　＝　１；Ｊ，ｌ＜　￡　；Ｊ，ｌ＋＋）　｛　．．．．．．—＋１ｐ—　Ｉｆ（ｃｏｎｅ（Ｎｗ［Ｏ，Ｎｗ［ｍ］）＜２　ａｒｃｓｉｎ　２　＆＆ｌｌｕ，Ｎｗ［ｉ］ｌＬｑｌｕ，Ｎｗ　】ｌ１）Ｄｅｌｅｔｅ　Ｍ　】；　Ｉｆ（ｃｏｎｅ（Ｎｗ［Ｏ，Ｎｗ［ｍ］）＜ａ／６＆＆Ｉｌｕ，Ｎｗ［ｉ］ｌｌ＞ｌｌｕ，Ｎｗ［ｍ】ｌ１）ＤｅｌｅｔｅⅣ　Ｊ，ｌ】；　｝　ＭｏｖｅＮｗ［ｉ】ｔｏ肠【】；　｝　Ｅｌｓｅ｛　Ｉｆ（ｉ－￣－－ｗ＿ｓｉｚｅ－１）Ｍｏｖｅ　Ｎｗ［ｗ　ｓｉｚｅ－Ｉ】ｔｏ＾　】；　Ｆｏｒ（Ｊ，ｌ＝Ｏ；ｍ＜ｗ＿ｓｉｚｅ；ｍ＋＋）　生　Ｆｏｒ（ｆ：＝，，ｌ＋１；Ｊ，ｌ＜　；Ｊ，ｌ＋＋）Ｉｆ（ｃｏｎｅ（Ｎｗ【Ｊ，ｌ】，ⅣｌＷ［，］）＜２ａｒｃｓｉｎ２　ＭｏｖｅＮｗ［】ｔｏＮｂ【】；　｝　｝　Ｎｏｄｅ“ｓｅｔｓ　ｉｔｓ　ｃｏｌｏｒ　ａｓ　ｂｌａｃｋ；　）ＤｅｌｅｔｅＮｗ［，］；　Ｎｏｄｅ“ｂｒｏａｄｃａｓｔｓ　ｍｅｓｓａｇｅ　ＵｐｄａｔｅＮ　ｔｏ　ｉｔｓ　ｎｅｉｇｈｂｏ￣ｉｎｃｌｕｄｉｎｇ　ｈｅ　ｔｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｌａｌ　ｄｅｌｅｔｅｄ　ｎｏｄｅｊ．　｝　２．３　ＶＣＧＧ算法的性质　定理３．如果ＵＤＯ（　是一个连通图，那么ＶＣＧＧ图也是连通的．　证明：采用反证法．如图２所示，假设在ＶＣＧＧ算法中处理节点“时，因为选择节点Ｗ而移走了连接ＵＶ，“ｖ是　造成ＵＤＧ图的连通性被破坏的最短连接．　（１）如图２（ａ）和图２（ｂ）所示，节点Ｗ是已经处理的节点，节点ｖ是没有处理的节点．并且由ＧＧ图的性质可　知，Ｉｌｗｖｌｌ＜ｌｌｕｖｌｌ，即连接１．ｎ，小于“ｖ．因为节点Ｗ已经处理过，所以连接ＵＷ将保留在最终的ＶＣＧＧ图中．由假设可　知　（“…ｖ）ｔ终不连通是由于ｐ（ｗ…ｖ）不连通造成的．也就是说，如果连通性被破坏，“ｙ不是破坏连通性的最短连　接，这与假设矛盾．　（２）如图２（ｃ）所示，¨ｌ‘＿Ｈ，ｌｌ＜ｌ　ｖＩＩ，因为　ｗＭＫ　／４，有Ｉ１ｗ￣ｌｌ＜ｌｌｕｖｌ１．也就是说，连接ＵＷ和１．　都小于“Ｖ．根据假设，　只有路径ｐ（ｕ…　或ｐ（ｖ…ｗ）断裂，才会导致路径ｐ（ｕ…ｖ）断裂．因此，如果连通性被破坏，表示“Ｖ不是破坏连通性　的最短连接．与假设矛盾．　（３）如图２（ｄ）所示，因为Ｌｖｕｗ＜ｘ／４，有Ｉ１ｗｖｌｌ＜ｌｌｕｖｌｌ，即连接　・　小于“Ｖ．因为Ｉ１ｗｘｌｌ＜ｌｌｕｗｌｌ，Ｌｘｗｕ＜ｘ／４，有　维普资讯 http://www.cqvip.com

７１０　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７　Ｉｘｕｌｌ＜ｌｌｕｗｌｌ，由（２）可知，删除ＵＷ不会造成ＵＷ之间的不连通．所以，由假设可知　（　．　最终不连通，只有ｐ（ｗ…　不连通才成立．也就是说，如果连通性被破坏，ＵＹ不是破坏连通性的最短连接．这与假设矛盾．　所以，如果ＵＤＧ（　是一个连通图，那么ＶＣＧＧ图也一定是连通的．　定理４．ＶＣＧＧ图满足平面特性．　证明：很明显，因为ＧＧ图是平面的，ＶＣＧＧ图没有增加任何其他连接，所以也是平面的．　定理５．ＶＣＧＧ算法的通信开销最多是３　．　口　口　证明：构建ＧＧ图的通信开销仅为　㈣：每个节点仅需广播１个消息给它的邻居节点（包括它的ＩＩ）和坐标位　置）．ＶＣＧＧ算法的邻居选择过程中，因为ＧＧ图的边数为Ｉｎ，３ｎ一６】，算法要保持图的连通性至少要保留ｎ－１条边，　即最多从ＧＧ图中移走２　条边，广播移走邻居节点的通信开销为２　，因此，总的通信开销不超过３　．　口　推论２．ＶＣＧＧ算法中，ＦＤＦＮ逻辑邻居节点的选择策略可以降低节点的干扰和传输功率．　证明：如图４所示，节点Ｘ，ｗ，ｙ，１，都是白色节点，Ｉｌｕｗｌｌ＜ｌｌｕｘｌｌ￣ｌｕｙｌｌ＜ｌｌｕｖｌｌ，　厶　ｗ　ＶＣＧＧ算法选　取邻居节点的方式是：最远的邻居节点是　因为节点＇，位于节点Ｙ的啦制域范围内，并且节点Ｙ是满足这个条　件中距离节点Ｕ最近的节点，因此优先选择邻居节点．），；然后，删除节点Ｙ的　控制域中所有邻居节点的连接，包括　Ｉｌｕｖｌｌ和Ｉｌｕｗｌｌ；最后再选择节点　作为节点　的另一个逻辑邻居节点．这样，节点　的最大功率就是ｌ　ｌ一＇一　厂　，’开、　而文献【ｌｌ】　中，ＳＯＧＧ算法采用的依次从近到远选取邻居节点的方法，节点Ｕ的传输功率￣ｌｌｕｖｌ：．由ＧＧ图的定义可　知：８　ｌ　ｌｌｎ｛Ｉ・ｃｏｓ　（脸９），当ｋ＝９时，　１，ｌｌ最坏情况可以达到ｌｌ　ｌｌ的１．３倍Ｉ　１／ｃｏｓ　Ｉ７／　，功率达到１．３馏．因　此，ＶＣＧＧ算法中，逻辑邻居节点的选择策略ＦＤＦＮ可以降低节点的干扰和传输功率．　推论３．ＶＣＧＧ算法中，可变扇区的设计使节点的选择更加灵活，能够降低节点的干扰和传输功率．　证明：如图５所示，节点　，Ｗ是黑色节点，节点１，是白色节点，Ｉｌｕｗｌｌ－＜Ｉｌｕｘｌｌ＜ｌｌｕｖｌｌ，／ｗｕｘ＜２７ｔ／３，Ｌｘｕｖ＞Ｏ，／ｗｕｖ＞ａ，￣　口　２０＜２ｎ／３．在ＶＣＧＧ算法中，只会选择ｗ，ｘ两个节点，节点１，位于它的可变扇区ａ＝２ｘ／３，因此，节点Ｕ删除了与节点　１，的连接，节点Ｕ的传输功率为Ｉｌｕｘｌｌａ．如果按照ＳＹａｏＧＧ和Ｓ￣ＧＧ算法中等分扇区或等分控制域的　方法，节点　会选择节点１，作为逻辑邻居节点，节点　的功率为　１，　由ＧＧ图的特性可知０ｌ‘’，Ｉ　√２０姒ＩＩ，这种情　况下，ＶＣＧＧ的功率可缩小近（√２）ｐ倍．　口　５　Ｔｈｅ　ｍｏｒｅ　ｌｏｇｉｃ　ｎｅｉｇｈｂｏｒｓ　ｄｕｅ　ｔｏ　ｋ－ｅｑｕａｌｌｙ　ＣＯＩＩＣＳ　Ｆｉｇ．４　Ｔｈｅ　ｍｅｔｈｏｄ　ｏｆｎｏｄｅ　Ｕ　ｓｅｌｅｃｔｉｎｇ　ｌｏｇｉｃａｌ　ｎｅｉｇｈｂｏｒｓ　Ｆｉｇ．图４节点Ｕ的逻辑邻居节点的选择方法　图５　ｋ等分扇区增大了逻辑邻居节点个数　３性能评价　实验环境参照文献【ｌｌ】，产生　个节点随机分布在１６ｘ１６单元区域，节点数目的变化在３０￣３６０之间，即　ｎ＝３０ｉ．１＜ｉ＜１２。每个节点的最大传输半径设置为４个单元．测试网络的连通性，如果网络是连通的，建立相应的　ＵＤＧ（　图．在ＵＤＧ（　图的基础上构造ＶＣＧＧ图和其他已知的图，包括ＭＳ￣ＧＯ，ＳＯＧＧ，ＳＹａｏＧＧ等进行比较．　无线传输介质能量损耗　２，当构造ＳＹａ０ＧＧ和ＳＯＧＧ图时参数ｋ设置为９，ＶＣＧＧ算法中　ｅ＝２ａｒｃｓｉｎ２．＂１＇５－２ｎ／９￣１４。实验在不同的节点集合进行５００次，比较这些拓扑图的平均功率伸长因子、平均（最大）　．．逻辑邻居节点个数、平均（最大）物理邻居节点个数、平均（最大）节点传输能量．　（１）功率伸长因子　图６显示了几种拓扑图的平均功率伸长因子，从小到大的顺序依次是ＧＧ，ＳＹａｏＧＧ，ＳＯＧＧ，ＶＣＧＧ和ＭＳＴ．　维普资讯 http://www.cqvip.com

ｓＪｏ０最Ｉａ口＿｜矗ｕ商。　ＪａＤ罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７１１　其中。ＧＧ的功率伸长因子为１；ＳＹａｏＧＧ和ＳＯＧＧ的功率伸长因子小于１．０２；ＶＣＧＧ的功率伸长因子小于　１．０３；ＭＳＴ的功率伸长因子最大．ＶＣＧＧ算法对缆制域进行了严格限制，功率伸长因子可以通过对啦制域的调　节控制在常数范围内．ＶＣＧＧ的平均功率伸长因子比ＳＯＧＧ略有增大（＜Ｏ．ｏ１），主要原因是，ＶＣＧＧ更好地降低了　节点的传输功率和逻辑邻居节点的个数，减少了与更多邻居节点的连接．而ＭＳＴ的长度伸长因子至少是　，。　ｌ…．、　ｏ＿羞　—ＩＩＩｌＩｌ爵＾Ｉｓ．ＩＤ参。口Ｄ　爵．ＩＤ　《　Ｉ・　ｌｏｇｌｏｇｎ　ｌ，功率伸长因子达到，ｌ一１，所以有较大的平均伸长功率因子，并且随着节点数的增加而不断增大．　ｓＪｏ毫ＩａⅡｌ爵ｕ　ｏ＿【Ｊ０　ＩａｑⅢＮｕｍｂｅｒ　ｏｆｎｏｄｅｓ　Ｆｉｇ．６　Ｔｈｅ　ａｖｅｒａｇｅ　ｐｏｗｅｒ　ｓｐａｎｎｉｎｇ　ｒａｔｉｏ　ｏｆ　ｖａｒｉｏｕｓ　ｓｔｒｕｃｔｕｒｅｓ　图６不同图结构的平均功率伸长因子　（２）逻辑邻居节点的度　图７（ａ）和图７（ｂ）分别显示了几种拓扑图的平均逻辑邻居节点和最大逻辑邻居节点．可以看出，ＶＣＧＧ算法由　于采用了可变扇区的思想，比ＳＹａｏＧＧ和Ｓ￣ＧＧ算法的等分扇区和等分啦制域更加灵活，同时，采用ＦＤＦＮ逻　辑邻居节点的选择策略，降低了节点的传输功率，逻辑邻居节点的度有较明显的下降．ＶＣＧＧ的平均逻辑邻居节　点个数比Ｓ￣ＧＧ大约下降了Ｏ．２，最大逻辑邻居节点的个数大约下降了０．５左右．　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　（ａ）Ａｖｅｒａｇｅ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｉｇｈｂｏｒｓ　（ｂ）Ｍａｘｉｍｕｍ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｉｇｈｂｏｒｓ　（ａ）平均通信邻居节点　Ｃｏ）最大通信邻居节点　Ｆｉｇ．７　Ｔｈｅ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｉｇｈｂｏｒｓ　ｏｆ　ｖａｒｉｏｕｓ　ｓｔｒｕｃｔｕｒｅｓ　图７不同图结构的通信邻居节点　（３）物理邻居节点的度（干扰）　图８（ａ）和图８（ｂ）分别显示了几种拓扑图的物理邻居节点和最大物理邻居节点（用来衡量通信时节点之间的　相互干扰）．可以看出，由于缩小了节点的传输功率，有效地减少了节点的干扰，降低了节点的物理邻居节点的　度．ＶＣＧＧ的平均物理邻居节点个数比ＳＯＧＧ大约下降了Ｏ．５，最大物理邻居节点的个数大约下降了１．３左右．　（４）节点的功率　图９（ａ）和图９（ｂ）分别显示了几种拓扑图节点的平均传输功率和最大传输功率．同样，ＶＣＧＧ由于选择了　维普资讯 http://www.cqvip.com

７１２　叠Ｉ善Ｉａ葺ＩＩｐ　言　ｏ矗叠口Ｈ昌ｏｓ＇娶’＾ｖ　８　ｄ【０Ｉ墨晴　基ｄ—■鼻旦ｖｏｌＨ　ｏ　叠　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．１８，Ｎｏ．３，Ｍａｒｃｈ　２００７　ＦＤＦＮ逻辑邻居节点的选择策略以及更灵活的角度分区，节点的传输功率比ＳＯＧＧ有所下降．其中，节点的平均　传输功率大约下降了Ｏ．４左右；节点的最大传输功率大约下降了１．Ｏ左右，减少了节点的能量消耗，延长了节点的　使用寿命，同时也降低了邻居节点的干扰．　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　矗８　ＩＩｏ磊晴一昌曲——嚣扫旦ｖｏＩＩ昌ＩＩ雪聋　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　。喜【ａ日ｒＢ３夏暑Ｊｏ矗　蜀ｌＩＩ口曩一量尊苫　（ａ）Ａｖｅｒａｇｅ　ｎｏｄｅ　ｉｎｔｅｒｆｅｒｅｎｃｅ　（ａ）平均节点干扰　Ｃａ）Ｍａｘｉｍｕｍ　ｎｏｄｅ／ｎｔｅｒｆｅｒｅｎｃｅ　（ｂ）最大节点干扰　Ｆｉｇ．８　Ｔｈｅ　ｎｏｄｅ　ｉｎｔｅｒｆｅｒｅｎｃｅ　ｏｆ　ｖａｒｉｏｕｓ　ｓｔｒｕｃｔｕｒｅｓ　图８不同图结构的节点干扰　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　Ｎｕｍｂｅｒ　ｏｆｎｏｄｅｓ　（ａ）Ａｖｅｒａｇｅ　ｎｏｄｅ　ｐｏｗｅｒ　（ｂ）Ｍａｘｉｍｕｍ　ｎｏｄｅ　ｐｏｗｅｒ　（ａ）节点的平均功率　Ｃｏ）节点的最大功率　Ｆｉｇ．９　Ｔｈｅ　ｎｏｄｅ　ｐｏｗｅｒ　ｏｆ　ｖａｒｉｏｕｓ　ｓｔｒｕｃｔｕｒｅｓ　图９不同图结构的节点功率　４结论　在移动自组网中，网络的拓扑结构可以通过调节每个节点的传输功率进行控制．拓扑控制就是要设计基于　功率优化的算法，既能维护网络的连通性，又能减少每个节点的传输功率，延长节点的生存时间，达到优化网络　性能的目的．本文在ＧＧ图的基础上提出了一种基于能量效率的拓扑控制算法ＶＣＧＧ，建立了一个度有界、平　面、干扰小的　支撑图．ＶＣＧＧ算法采用可变扇区的思想，比ＳＹａｏＧＧ和ＳＯＧＧ算法的等分扇区和等分　控制域　更加灵活；对　控制域进行了严格限制，功率伸长因子可以控制在常数范围内：算法还采用了ＦＤＦＮ逻辑邻居节　点的选择策略，降低了节点的传输功率和节点干扰．实验表明，ＶＣＧＧ算法与已有的ＳＯＧＧ，ＳＹａｏＧＧ等算法相比，　更好地降低　了最大邻居节点干扰、最大功率、平均邻居节点干扰和平均功率，提高了能量的使用效率．进一步　的研究包括，考虑节点接收数据、侦听对能量消耗的影响，考虑节点加入、离开和移动性带来的影响等因素，对　算法做进一步的改进．同时考虑广播的能量效率，在ＶＣＧＧ算法的基础上设计新的分布式、低权值的算法．　维普资讯 http://www.cqvip.com

罗玉宏等：移动自组网基于能量效率的分布式拓扑控制算法　７１３　Ｒｅｆｅｒｅｎｅｅｓ：　【ｌ】Ｗｉｅｓｅｌｔｈｉｅｒ　Ｊ，Ｎｇｕｙｅｎ　Ｇ，Ｅｐｈｒｅｍｉｄｅｓ　Ａ．Ｄｉｓｔｒｉｂｕｔｅｄ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｅｎｅｒｇｙ－ｅｆｉｃｉｆｅｎｔ　ｂｒｏａｄｃａｓｔｉｎｇ　ｉｎ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｏ’Ｂｅｒｒｙ　ＣＧ，ｅｄ．Ｐｒｏｃ．ｏｆｔｈｅ　ＩＥＥＥ　Ｍｉｌｉｔａｒｙ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｃｏｎｆ．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｉｎｃ．，２００２．８１９－８２４．　【２】Ｌｕｏ　ＹＨ，Ｗａｎｇ　ＪＸ，Ｃｈｅｎ　ＪＥ，Ｃｈｅｎ　ＳＱ．Ａ　ｄｉｓｔｒｉｂｕｔｅｄ　ａｌｇｏｒｉｈｍ　ｂａｓｅｄ　ｏｎ　ｐｒｔｏｂａｂｉｌｉｔｙ　ｆｏｒ　ｒｅｆｉｎｉｎｇ　ｅｎｅｒｇｙ－ｅｆｉｃｉｅｆｎｃｙ　ｏｆ　ｍｕｌｔｉｃａｓｔ　ｔｒｅｅｓ　ｉｎ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｗｅｒｎｅｒ　Ｂ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｈｅ　ＩｔＥＥＥ　ｃｏｎ￡ｏｎ　Ｌｏｃａｌ　Ｃｏｍｐｕｔｒ　Ｎｅｔｅｗｏｒｋｓ（ＬＣＮ）．Ｎｅｗ　Ｙｏｒｋ：ＩＥＥＥ　Ｉｎｃ．，　２００５．４８２—４８３．　【３】　Ｒａｊａｒａｍａｎ　Ｒ．Ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　ａｎｄ　ｒｏｕｔｉｎｇ　ｉｎ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ：Ａ　ｓｕｒｖｅｙ．ＳＩＧＡＣＴ　Ｎｅｗｓ，２００２，３３（２）：６０－７３，　【４】Ｌｉ　ＸＹ．Ａｌｇｏｒｉｈｍｉｔｃ，ｇｅｏｍｅｔｒｉｃ　ａｎｄ　ｇｒａｐｈｓ　ｉｓｓｕｅｓ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ．Ｗｉｒｅｌｅｓｓ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ａｎｄ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ，２００２，　３（２）：ｌ　１９—１４０．　【５】Ｃａｐｋｕｎ　Ｉ，Ｈａｍｄｉ　Ｍ，Ｈｕｂａｕｘ　Ｊ．Ｏｐｓ－Ｆｒｅｅ　ｐｏｓｉｔｉｏｎｉｎｇ　ｉｎ　ｍｏｂｉｌｅ　ａｄ－ｈｏｃ　ｎｅｔｗｏｒｋｓｒ　Ｃｌｕｓｔｅｒ　Ｃｏｍｐｕｔｉｎｇ，２００２，５（２）：１５７－１６７．　【６】　Ｌｉ　Ｍ，Ｌｕ　ＸＣ，Ｐｅｎｇ　Ｗ．Ｐｌａｎａｒ　ｔ－ｓｐａｎｎｅｒ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋ．Ｊｏｕｒｎａｌ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２００５，２６（６）：６２－６９（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｈ　ｔＥｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．　【７】　Ｋｌｅｉｒｏｃｋ　ｕＬ，Ｓｉｌｖｅｓｔｅｒ　Ｊ．Ｏｐｔｉｍｕｍ　ｒｔｎｓｍｉａｓｓｉｏｎ　ｒａｄｉｉ　ｆｏｒ　ｐａｃｋｅｔ　ｒａｄｉｏ　ｎｅｔｗｏｒｋｓ　ｏｒ　ｗｈｙ　ｓｉｘ　ｉｓ　ａ　ｍａｇｉｃ　ｎｕｍｂｅｒ．Ｉｎ：Ｇｅｒｌａ　Ｍ，ｅｄ．Ｐｒｏｃ　ｏｆｔｈｅ　ＩＥＥＥ　Ｎａｔｉｏｎａｌ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｃｏｎｆ．Ｎｅｗ　Ｙｏｒｋ：ＩＥＥＥ　Ｉｎｃ．．１９７８．４３ｌ—４３５．　【８】Ｚｈｏｕ　ＳＨ，Ｃｈｅｎ　ＳＤ．Ａ　ｍｕｌｔｉ－ｒａｔｅ　ａｗａｒｅ　ｔｏｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｈｍ　ｉｔｎ　ｍｏｂｉｌｅ　ｅｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｊｏｕｒｎａｌ　ｏｆ　Ｓｏｆｔｗａｒｅ，２００４，１５（１２）：　ｌ８６９－１８７６（ｉｎ　Ｃｈｉｎｅｓｅ　ｗｉｔｈ　Ｅｎｇｌｉｓｈ　ａｂｓｔｒａｃｔ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００－９８２５／１５／１８６９．ｈＵｎ　【９】　Ｋａｒｐ　Ｂ，Ｋｕｎｇ　ＨＴ．ＧＰＳＲ：Ｇｒｅｅｄｙ　ｐｅｒｉｍｅｔｅｒ　ｓｔａｔｅｌｅｓｓ　ｒｏｕｔｎｇ　ｆｉｏｒ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｐｉｃｋｈｏｌｔｚ　Ｒ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｔｈｅ　ＡＣＭ　ＭｏｂｉＣｏｍ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２ｏｏＯ．２４３－２５４．　【１０】Ｋｕｈｎ　Ｆ，Ｗａｔｔｅｎｈｏｆｅｒ　Ｒ，Ｚｏｌｌｉｎｇｅｒ　Ａ．Ｗｏｒｓｔ－Ｃａｓｅ　ｏｐｔｉｍａｌ　ａｎｄ　ａｖｅｒａｇｅ－ｃａｓｅ　ｅｆｉｃｉｆｅｎｔ　ｇｅｏｍｅｔｒｉｃ　ａｄ－ｈｏｃ　ｒｏｕｔｉｎｇ．Ｉｎ：Ｊｏｈｎｓｏｎ　ＤＢ，ｅｄ．　Ｐｒｏｃ．ｏｆ　ｈｅ　ｔＡＣＭ　ＭｏｂｉＨｏｃ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ，２００３，２６７．２７８，　【ｌ１】Ｌｉ　ＸＹ，Ｓｏｎｇ　Ｗ，Ｗａｎｇ　Ｗ．Ａ　ｕｎｉｆｉｄ　ｅｎｅｒｅｇｙ　ｅｆｉｃｉｆｅｎｔ　ｔｏｐｏｌｏｇｙ　ｆｏｒ　ｕｎｉｃａｓｔ　ａｎｄ　ｂｒｏａｄｃａｓｔ，Ｉｎ：Ｐｏｒｔａ　ＴＬ，ｅｄ．Ｐｒｏｃ．ｏｆｔｈｅ　ＡＣＭ　ＭｏｂｉＣｏｍ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　ｒｅｓｓ．２００５．１－ｌ５．Ｐ　【１２】Ｔｏｕｓｓａｉｎｔ　Ｇ．Ｔｈｅ　ｅｌａｔｒｉｖｅ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ｒａｐｈ　ｇｏｆａ　ｉｆｎｉｔｅ　ｐｌｎａｒａ　ｓｅｔ．Ｐａｔｔｅｒｎ　Ｒｅｃｏｇｎｉｔｉｏｎ，１９８０，ｌ２（４）：２６１－２６８．　【１３】Ｇａｂｒｉｅｌ　ＫＲ，Ｓｏｋａｌ　ＲＲ．Ａ　ｎｅｗ　ｓｔａｔｉｓｔｉｃａｌ　ａｐｐｒｏａｃｈ　ｏ　ｇｅｏｇｔｒａｐｈｉｃ　ｖａｒｉａｔｉｏｎ　ｎａｌａｙｓｉｓ．Ｓｙｓｔｅｍａｔｉｃ　Ｚｏｏｌｏｇｙ，１９６９，１８（３）：２５９－２７８．　【１４】　Ｙａｏ　ＡＣ．Ｏｎ　ｃｏｎｓｔｒｕｅｒｉｎｇ　ｍｉｎｉｍｕｍ　ｓｐａｎｎｉｎｇ　ｔｒｅｅｓ　ｉｎ　ｋ・ｄｉｍｅｎｓｉｏｎａｌ　ｓｐａｃｅｓ　ａｎｄ　ｒｅｌａｔｅｄ　ｐｒｏｂｌｅｍｓ．ＳＩＡＭ　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ，　１９８２，ｌ　１（４）：７２１－７３６．　［１　５】Ｂｏｓｅ　Ｐ，Ｇｕｄｍｕｎｄｓｓｏｎ　Ｊ，Ｓｍｉｄ　Ｍ．Ｃｏｎｓｔｒｕｃｔｉｎｇ　ｐｌａｎｅ　ｓｐａｎｎｅｒｓ　ｏｆ　ｏｕｂｎｄｅｄ　ｄｅｇｒｅｅ　ａｎｄ　ｌｏｗ　ｗｅｉｈｔｇ．Ｉｎ：Ｒｓｍａｎ　Ｒ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｈｅ　ｔ１０ｔｈ　Ａｎｎｕａｌ　Ｅｕｒｏｐｅａｎ　Ｓｙｍｐ．ｏｆＡｌｇｏｒｉｔｈｍｓ．Ｌｏｎｄｏｎ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００２．２３４－２４６．　【１６】　Ｗａｔｔｅｎｈｏｆｅｒ　Ｒ，Ｌｉ　Ｌ，Ｂａｈｌ　Ｐ，Ｗａｎｇ　Ｙ．Ｄｉｓｔｒｉｂｕｔｅｄ　ｏｐｏｌｔｏｇｙ　ｃｏｎｔｒｏｌ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｍｕｌｔｉｈｏｐ　ａｄ－ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｓｅｎｇｕｐｔａ　Ｂ，ｅｄ．　Ｐｒｏｃ．ｏｆｔｈｅ　ＩＥＥＥ　ＩＮＦＯＣＯＭ　２００１．Ｐｉｓｃａｔａｗａｙ：ＩＥＥＥ　Ｉｎｃ，，２００１．１３７０－１３７９．　【ｌ７】Ｌｉ　Ｌ，Ｈａｌｐｅｒｎ　Ｊ，Ｂａｈｌ　Ｐ，Ｗａｎｇ　Ｙ，Ｗａｔｔｅｎｈｏｆｅｒ　Ｒ．Ａ　ｃｏｎｅ－ｂａｓｅｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｔｏｐｏｌｏｇｙ・ｃｏｎｔｒｏｌ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｗｉｒｅｌｅｓｓ　ｍｕｌｉｔ・ｈｏｐ　ｎｅｔｗｏｒｋｓ．ＩＥＥＥ，ＡＣＭ　Ｔｒａｎｓ．ｏｎ　Ｎｅｔｗｏｒｋｉｎｇ，２００５，１３（１）：１４７—１５９．　【１８】Ｃａｌｉｎｅｓｃｕ　Ｇ．Ｃｏｍｐｕｔｉｎｇ　２－ｈｏｐ　ｎｅｉｇｈｂｏｒｈｏｏｄｓ　ｉｎ　ｅｄ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ，Ｉｎ：Ｐｉｅｒｒｅ　Ｓ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｈｅ　ＡＤ－ｔＨＯＣ　ＮｅｔｗＯｒｓ　ａｋｎｄ　Ｗｉｒｅｌｅｓｓ　Ｃｏｎｆ．Ｂｅｒｌｎ：Ｓｐｒｉｉｎｇｅｒ－Ｖｅｒｌａｇ，２００３．１７５－１８６．　【１９】ＳｏｎｇＷ，ＷａｎｇＹ，ＬｉＸＹ．Ｌｏｃａｌｉｚｅｄ　ａｌｇｏｒｉｔｈｍｓｆｏｒ　ｅｎｅｒｇｙ　ｅｆｉｃｉｆｅｎｔｔｏｐｏｌｏｇｙｉｎｗｉｒｅｌｅｓｓ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ．Ｉｎ：Ｍｕｒａｉ　Ｊ，ｅｄ．Ｐｒｏｃ．ｏｆ　ｈｅ　ｔＡＣＭ　ＭｏｂｉＨｏｃ．Ｎｅｗ　Ｙｏｒｋ：ＡＣＭ　Ｐｒｅｓｓ．２００４．９８－１０８．　附中文参考文献：　【６】　李铭，卢锡城，彭伟．面向无线ａｄ　ｈｏｃ网络的一种平面ｆ－支撑图．通信学报，２００５，２６（６）：６２－６９．　【８】　邹仕洪，程时端．一种多速率移动自组网中的拓扑控制算法．软件学报，２００４，１５（１２）：１８６９—１８７６．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｅｎ／１０００－９８２５／　ｌ５１１８６９．ｈＵｎ　罗玉宏（１９７２－－），男，湖南邵阳人，博士，湖　南广播电视大学副教授，主要研究领域为　无线网中路由算法，网络性能评价．　黄家玮（１９７６一），男，博士生，湖南广播电视　大学讲师。主要研究领域为网络服务质量．　王建新（１９６９－－），男，教授，博士生导师，ＣＣＦ　高级会员，主要研究领域为计算机网络，　陈松乔（１９４０－－），男，教授，博士生导师。ＣＣＦ　高级会员，主要研究领域为软件工程．