一种最小化无线自组网干扰的拓扑控制算法

1、一种最小化无线自组网干扰的拓扑控制算法李晓鸿1，张大方2，蔡小莉1，王 东1(1. 湖南大学计算机与通信学院，湖南 长沙 410082；2. 湖南大学软件学院，湖南 长沙 410082 摘 要:针对无线自组网中，如何准确度量干扰并构建干扰最小化的网络结构的问题。根据无线通信的特点和网络协议的机制，设计了一种基于协议的网络干扰模型度量方法，并提出了一种启发式的干扰最小化拓扑控制算法，该分布式算法能保证网络连通，并使整个网络中节点间的路径干扰最小化。仿真结果验证了新算法降低了网络冲突，更好地改善了网络性能。关键词: 自组网; 拓扑控制; 干扰; 吞吐量中图法分类号: TP393 文献标识码: AA

2、n Interference-avoidance Topology Control Algorithm inAd hoc NetworksLi Xiao-hong1, ZHANG Da-fang2, Cai Xiao-li1, Wang Dong1(1. School of Computer and Communication, Hunan University, Hunan Changsha 410082, China(2. School of Software, Hunan University, Hunan Changsha 410082, ChinaAbstract: In order

3、 to concretely measure and explicitly reduce the interference of the entire network in Ad hoc networks, a new protocol interference model is presented as a measure to describe the interference of the entire network in this paper. Furthermore we propose a distributed interference-avoidance topology c

4、ontrol approximation algorithm, referred to as the ISPT. The algorithm minimizes the interference in the network according to our metrics while preserving the connectivity of the resulting topology. The simulation results show that ISPT decreases interference and improves network capacity in terms o

5、f throughput.Key words: Ad hoc networks; topology control; interference; throughput1引言自组网是一种无中心、自组织的多跳无线网络。由于其具有抗毁性、自组织性与机动性等特点，将在无线通信领域发挥越来越重要的作用。为保证无线自组网能即时、通畅和高效通信，提高自组网的传输能力和减少节点的能耗是自组网面临的关键问题12。拓扑控制是提高网络吞吐率和延长网络生命周期的一种重要途径。该技术通过调整节点的发送功率和建立合适的相邻关系，构建全局优化网络拓扑。其主要目标是降低节点能耗和减少通信干扰，为MAC 协议和路由协议的顺利执

6、行提供基础。近年来国内外一些学者已经初步展开了对构建自组网拓扑的理论研究和应用探讨34。早期的经典拓扑控制算法主要通过控制节点发送功率或尽量稀疏化网络拓扑图的思想，达到降低节点信道之间干扰的目的。近阶段有一些研究者，认为片面减少边的数量、长度及邻节点度不一定就能保证节点之间的干扰现象也降低4，并就干扰模型的定义和度量方法进行了研究5，其中定义的干扰模型有基于发送节点的干扰模型6，基于接收节点的干扰模型78和基于链路的干扰模型91011；而对于干扰的度量，则采用了基于网络拓扑的点覆盖或边覆 基金项目：国家973重点基础研究发展计划(No.2007CB310702；国家自然科学基金(No.6067

7、3155李晓鸿 男, 1973年出生，湖南长沙人, 讲师, 湖南大学计算机与通信学院博士研究生, 主要研究方向为可信系统与网络、无线网络和移动计算. Email: lixhong盖统计方法。但是，这些定义仅仅以节点位置和覆盖范围度量网络中的局部（一跳范围）干扰，没有考虑自组网中节点间经过路径（即多跳）传输的特性对度量干扰的影响。文献12则认为必须从网络协议的角度出发，结合自组网数据通信机制和网络拓扑中节点覆盖的特点，这样才能更准确的定义网络拓扑干扰模型。文献5综述了目前已有学者基于不同的干扰模型，提出的降低网络干扰的拓扑控制近似算法。其中文献9基于链路的干扰模型，首次提出LIFE 算法构建最小

8、化最大边干扰度的拓扑结构。文献13提出把平均最优路径的冲突作为衡量网络冲突性能指标，设计API 算法以构建干扰优化的拓扑结构，但是API 算法是基于GG 图进行剪枝处理以优化干扰，并没有从直接寻求最优干扰路径的角度设计算法，这使得构建的拓扑有可能没有获得最优干扰路径13。而文献14则分析并证明，全局网络节点对之间干扰最短路径的拓扑结构的优越性，但是没有提出有效的分布式构建方法。上述这些通过拓扑控制降低网络干扰的研究工作，其主要贡献在于对拓扑结构的干扰进行定性或半定量的分析描述，但在拓扑控制算法的研究中，更多地关注降低网络的局部或某些特殊情形的干扰，很少有算法把降低整个网络的干扰作为主要目的，也

9、没有充分考虑拓扑结构与网络协议的相互关系对网络传输性能的影响。而且构建算法大多不实用，时间复杂度高且大多是集中式算法，或需获得网络全局信息，通信代价过高。这些不足使得研究者无法就它们对网络性能的影响进行定量评估。本文首先根据无线通信的特点和网络协议的机制研究干扰可能发生的实际情况，提出干扰模型及度量方法，在此基础上提出一种分布式的启发式算法ISPT(An Interference-avoidance topology control algorithm based Shortest Path Tree。并理论证明新算法在保证整个网络连通的前提下，可以构建任意节点间的最短路径干扰最小化的拓扑图；

10、同时提出了一种准干扰瓶颈节点避免机制，通过减少稀疏拓扑结构中瓶颈节点的出现，避免路由造成的流间干扰概率增大对网络传输性能的影响。仿真结果验证了算法ISPT 降低了网络冲突，更好地改善了网络传输性能。2基于协议的干扰模型和干扰度量指标在无线通信中，一个正在发送射频信号的设备会影响周围其它设备接收信号。如果一个设备附近有其它设备正在发送信号，那么它将不能同时正确接收其它邻近设备发射的信号。通信中的这种相互信号扰乱称为干扰。无线自组网的无线信道是一个共享广播信道。目前基于CSMA/CA的IEEE802.11是一种最有效的单信道接入控制协议。通过研究802.11对无线链路通信的控制机制，发现发送节点和

11、接收节点在一次通信中都需要相互发送和接收不同的数据帧，由此提出基于MAC 的边干扰模型，即无线链路收发两端一次完整数据传输时，两个节点都不能受到干扰。并定义如下度量干扰的公式。定义1（边干扰）给定一个网络拓扑图G =(V , E ，若边< u, v >E ，定义uv 边的干扰为：IL(=covering( covered( covering( covered( uv u u v v （1）其中，covering(u 为节点u 的发射功率为p (u 时覆盖的邻近节点集合，covered(u 为节点u 被邻近节点的发射信号覆盖的节点集合。若节点可以设置不同的发射功率，那么节点u 和v

12、以d (u , v 为半径的圆盘覆盖的节点数可以认为等于IL(uv 的最小值（即uv 之间通信时实际干扰的下限），其度量公式如下。 minIL ( , , (, (, (, (, uv w w V u v d u w d u v or d v w d u v =（2）无线自组网采用多跳转发组网方式。数据成功到达目的节点往往需要多次转发，这就要求在转发过程中，不能出现流内干扰和流间干扰，即路径上所有节点不能互相干扰和受到其它路径上节点的干扰。所以，本文结合路径的长度（跳数）和每跳（边）的干扰情形，提出基于路由协议的路径干扰模型，并给出如下定义。定义2（路径干扰）给定一个网络拓扑图G =(V ,

13、E ，节点u 和v 之间的路径P uv e 1，e 2，, e k ,定义路径P uv 干扰为：(IL( IP uve uv e P =（3） 目前，IETF 专门成立MANET 工作组提出的经典的无线自组网的路由协议（DSDV 和DSR ）都是选择跳数较小的路由。本文用ISP (uv 表示节点uv 之间最短路径的路径干扰。同时文献1516的仿真实验表明：稀疏的拓扑结构大大降低了源节点到目的节点的所有路径的条数，即降低了网络的路由多样性，如果存在多个路径跳数长的数据流，它们汇聚到一个相同区域的概率相比在拓扑控制以前的网络中选路时大了很多。这些区域从而成为“热点区域”。 Fig. 1 The f

14、igures show the results of three different topology control algorithms being performed on theoriginal topology (a: the LIFE algorithm (b, the API algorithm (c, ISPT (d.图1 针对初始拓扑结构，三种不同拓扑控制算法生成的拓扑图。 如图1所示，通过观察在初始UDG 图（未经拓扑控制处理）上分别运行LIFE 和API 算法生成的图。（如图1中的节点16）我们发现，“热点”区域中的节点都有一个共同特点，就是它们不仅是其邻居节点间互相连接

15、的唯一通道，如果从更大的区域来观察，它们是几个节点簇的连通关键点，也就是说，如果这些节点所在区域一旦出现长时间的流间干扰，将产生大量的路由开销（参见本文第5节的仿真实验），那么将使得多个节点簇中的节点无法相互正常通信；同时由于拓扑控制生成的网络结构具有稀疏性，即使这些节点在全网中可能存在其它路径（如图1(b中，可以经过部署区域的上方的节点建立路径），但跳数很大，路由算法运行开销巨大，最终将影响网络的传输能力。本文从拓扑结构的角度出发，对这些区域中的特殊节点定义如下。定义3（准干扰瓶颈节点）在一个拓扑图中提取某个节点u 两跳邻居节点的拓扑子图，那么u 是“准干扰瓶颈节点”，当且仅当在该子图中删除

16、u 以及连接u 的边，原来u 节点的邻居集被划分成两个或者多个不连通的非空集合。目前已提出的干扰最小化拓扑控制算法没有考虑到稀疏化拓扑结构造成的干扰瓶颈节点增加的情况，也没有设计针对性的处理策略。3 ISPT拓扑控制算法依据无线通信的特点，节点的信号发射功率和接收信号的阈值的不同有可能造成不同的干扰，即使自组网中节点的位置不变，节点设置不同的信号发射功率，构建的不同拓扑结构将有可能影响网络的干扰程度。如何构建干扰最小化的网络拓扑结构，是拓扑控制技术研究的一个关键问题。本文针对面向网络传输性能最优化的干扰最小化拓扑控制NP 难问题5，提出了一个分(aUDG (b LIFE (c API (d I

17、SPT布式拓扑控制启发式算法ISPT ，节点分布式获取局部信息，采用启发式策略构建干扰最小化的拓扑树，在保证网络连通的基础上，使任意节点间的最短路径干扰最小化；同时提出了一种准干扰瓶颈节点避免机制，通过减少拓扑结构中瓶颈节点的出现，避免路由造成的流间干扰概率增大对网络传输性能的影响，最优化网络吞吐量。文献4指出设计一个有效实用的拓扑控制算法应满足下列性质：1 算法在设置节点的最小发射功率的同时必须保证网络连通；2 算法能分布式运行；3 算法简单，且只需要每个节点收集自己局部的信息，从而减少信息的交互开销，提高算法的收敛速度；4 算法生成的拓扑图是对称、边稀疏、节点度有界的；5）算法生成的拓扑图

18、具有Spanner 性质。基于以上性质，根据第二节定义的基于协议的网络拓扑干扰模型，ISPT 算法主要由四个阶段组成：信息收集、拓扑构建、功率设置和避免准干扰瓶颈节点的优化步骤。3.1 ISPT算法主要步骤3.1.1信息收集在信息收集阶段，每个节点需要与其邻近节点进行两轮消息交互。利用邻节点发现协议，节点以最大功率周期性地广播Hello 分组。通过收集邻近节点的Hello 消息中的节点ID 和位置等信息，每个节点u 可以获得一跳最大可达邻居集，记为1_MNBR(u 。节点然后进行第二轮Hello 消息交互，相互通告各自的一跳最大可达邻居集，每个节点u 就可构建两跳邻居集，记为2_MNBR(u

19、。3.1.2拓扑构建每个节点各自独立地进行拓扑构建。通过与邻近节点之间交换信息，节点u 可以建立其本地最大功率拓扑结构，用一个无向有权图max u G 表示，其中V(max uG = 1_MNBR(u U u ，E(max u G = ( i, j | ( i 1_MNBR( j and ( j 1_MNBR( i , i,j V(max u G ，对于max uG 中的每条边（i, j），利用2_MNBR(u 中的邻居集合，按照公式（2）计算干扰度，作为该边的权值w(i, j。根据max uG ，节点u 执行单源最短路径算法 (如Dijkstra 算法 求出以它为根的最短路径树Tree u

20、G ，值得注意的是，如果max uG 中有多条边具有相同的权值，为了保证最短路径树的唯一性，当权值相等时，算法优先选取节点ID 小的边。然后更新集合一跳逻辑邻居集1_LNBR(u 为树中u 的儿子节点。同时为了保证节点u 到max uG 中所有节点的最短路径（最短路径树）中所有边能存在于最后的拓扑子图中，u 分别记录其最短路径树中每个中间节点v 的儿子节点集合，并通过Hello 消息把该集合告知节点v ，也就是为了保证u 到每个节点的最短路径都存在，希望其每个邻近节点必须连通的节点集。3.1.3功率设置节点u 首先设置其数据通信时的传输功率为到达集合1_LNBR(u 中最远的节点所需的功率。同

21、时为了保证邻近节点通过u 到其它节点的路径存在，在收到邻近节点v 的Hello 通告时，提取出v 希望u 必须连通的节点集合加入1_LNBR(u 中，同时节点u 重新把功率设定为到达集合1_LNBR(u 中最远的节点所需的功率。由于每条边的两个节点都会收到通告，该方式可以保证最终拓扑图中边的对称性。3.1.4干扰瓶颈节点避免准干扰瓶颈节点的具体过程分如下几步进行：（1） 采用与ISPT 算法第一步相同的消息交互方法，每个节点u 构建两跳邻居节点的拓扑子图。（2） 按照准干扰瓶颈节点的定义判定自己是否满足条件：如果除去u 和与u 直接相连的边后的子图2hops uG ，所有节点仍然连通，那么u

22、不是干扰瓶颈节点；否则u 是干扰瓶颈节点，进行下一步消除干扰瓶颈节点。（3） 采用加边的方法消除干扰瓶颈节点。为了找到最“适合”加的边，我们考虑如下原则：一是要保证u 的多个不连通的邻节点集合连通；二是新增边的干扰度小；三是增加的边对节点u 的干扰小。在2hops uG 中选取任意节点对按照公式（2）计算干扰度作为权值，借鉴求解最小生成树的Prim 算法（2hops u G 已有的边依然保存），按照边干扰度从小到大依次选取。为了减小增加的边对节点u 的干扰，如果边的两个节点至少有一个不属于1_LNBR(u 的优先选取，若选取的边能连通两个不连通的集合，则加入2hops u G 中，继续选取过程

23、直到2hops uG 连通为止。 （4） 节点u 计算出所有新增的边后，采用与ISPT 算法第三步相同的方法，通过Hello 通告的方式告知相应的节点，希望其改变功率设置以保证这些边能够建立。3.2算法分析和拓扑结构性质分析在进行拓扑控制时，每个节点各自独立地运行ISPT 的四个步骤，所以ISPT 是一个完全分布式的算法。网络中的每个节点独立异步地运行该算法，在算法的第一步每对邻近节点之间交互两次，第三步交互一次，而准瓶颈节点处理步骤和第一步和第三步类似，需要交互三次。虽然节点异步执行，但由于每个节点仅仅只需与各自邻近节点进行消息交互而无需转发，利用CSMA/CA的冲突避免机制，所有节点可以在

24、一个常数时间区间内完成消息交互操作。交互消息的主要目的是使得每个节点获取局部信息，用以构建一个仅由邻近节点构成的拓扑子图，显见子图中的节点数m 和边数e 是远小于整个网络（即使网络中有很多节点或者很密集），这使得每个节点在第二步运行最短路径算法O (m 2 和第四步运行最小生成树算法O (eloge 的实际运行时间代价很小。定义网络所有节点以相同的最大功率构建的拓扑图为G (V , E ，而由ISPT 构建的拓扑子图为G = (V , E ，可证明该算法构建的拓扑图是连通图。定理1若初始拓扑图G 是连通图，那么G 也是连通图。证明：不失一般性，随机在图中选取两个节点u 和v ，由定义可知，两个

25、节点在图G 中一定连通。下面只需证明两个节点在图G 也一定双向连通即可。在图G 中根据u 和v 两个节点相距的位置，可以分下面两种情况：a ） 点u 和v 之间的距离小于最大功率覆盖的距离，即在图G 中u 和v 存在边。那么两个节点在运行ISPT 算法第二步时，都会把对方作为拓扑子图中的一个节点。那么也一定会求出到对方的干扰度最小的路径，并发出消息通告路径上的节点，以保证在最终的图G 中路径上所有的双向边都存在。b ） 节点u 和v 之间的距离大于最大功率覆盖的距离，即在图G 中u 和v 之间不存在边，但一定存在一些中间节点v 1, v 2, v 3, , vk 使u 和v 之间存在双向连通的

26、路径L uv 。根据初始拓扑图的定义，该路径上任意两个相邻节点之间的距离小于最大功率覆盖的距离。那么根据情况（a ）的分析，在图G 中两个相邻节点之间一定存在双向连通路径。由此，在图G 中u 和v 之间一定存在双向连通的路径。综合上述两种情况的分析，可以证明ISPT 算法可以保证G 是连通图。 证毕推论1 图G 任意两点的干扰度最小的路径，在图G 依然存在，即图G 具有干扰度的扩展因子有界的特性。证明：根据最短路径的性质，任意两个节点u 和v 之间的最短路径经过i 点，那么u 到i 的最短路径一定也是沿着这条最短路径的轨迹。对于图G 节点u 和v 之间的干扰度最短路径上的所有边，都将被路径上的

27、所有点执行ISPT 算法第二步构建最短路径树时求出，并通过第三步消息通告以保证存在与图G 中。而ISPT 算法的第四步处理准瓶颈节点是加边操作，对最短路径不会产生影响。由于ISPT 可以保证干扰度最小的路径的存在，按照spanner 扩展因子的定义4可知推论成立。 证毕由上述分析可知，ISPT 算法具有分布式、基于局部信息、算法简单、消息开销小、扩展性好和收敛快的特点。同时证明算法构建的拓扑图不仅是连通图，而且是任意节点间的最短路径干扰最小化的拓扑图。 4 性能仿真评估 性能仿真 仿真评估 为了评估 ISPT 算法的有效性，基于最大发送功率构建的初始拓扑结构（简称 UDG） ， 计算并比较算法

28、 LIFE、API 和 ISPT 导出的拓扑图的干扰值，在此基础上，采用网络仿真平 台，比较并分析了不同算法生成的拓扑结构对网络性能的影响。 4.1 网络拓扑结构干扰值比较 本文使用平均边干扰（公式 2）和平均最短跳数路径干扰（公式 3）作为拓扑图干扰的 评估参数。 仿真的区域为 1000×1000， 节点数从 50 到 250， 节点的初始最大传输半径为 250， 每个特定的节点数， 节点在仿真区域中均匀随机分布生成 1000 个网络场景。 对于每个场景， 分别运行三种拓扑控制算法，对其拓扑结构的干扰值进行计算后取平均值。 图 2 给出了随着网络节点数增加， 四种拓扑结构的平均边干

29、扰的变化趋势。 如图 2 所示， 与 UDG 图相比，三种拓扑控制算法显著减小了网络中边的干扰，而且随着节点数的增加， 拓扑控制后的拓扑图的平均边干扰增长幅度较慢。LIFE 算法生成的拓扑图的边干扰是最小 的。与 API 算法相比，ISPT 算法生成的拓扑图的边干扰较小。 图 3 给出了随着网络节点数增加，四种拓扑结构的平均最短跳数路径干扰的变化趋势。 如图 3 所示， ISPT 算法生成的拓扑图是平均最短跳数路径干扰最小的， LIFE 和 API 并没 而 有有效的降低最大功率拓扑图的最短跳数路径的干扰值。 通过仿真实验验证了本文 3.2 节的分析，基于最短干扰路径树的 ISPT 算法有效的

30、降低 了网络的整体干扰，相对于基于边干扰优化的 LIFE 算法和基于 GG 图进行局部路径优化的 API 算法，将更有效地控制通信过程中的干扰。 40 35 30 25 20 15 10 5 0 50 LIFE API ISPT UDG 平均最短跳数路径干扰 70 60 50 40 30 20 10 50 100 150 节点数(个 200 250 LIFE API ISPT UDG 平均边干扰 100 150 节点数(个 200 250 Fig. 2 The average edge interference 图 2 平均边干扰比较 Fig. 3 The average shortest-h

31、op path interference 图 3. 平均最短跳数路径干扰比较 4.2 网络拓扑结构对网络性能的影响 我们采用当前流行的网络仿真软件 OPNET10.5 作为仿真平台，定量分析干扰优化拓扑 控制算法对无线自组网性能的影响。根据上述拓扑图特性的仿真实验可知，节点数在 50 到 250 之间，各种算法生成的拓扑图特性变化趋势稳定。本文取 160 个节点随机分布在 1000m ×1000m 的二维区域中，仿真场景设置如下：每个节点传播损耗模型使用自由空间模型，使 用 0dB 增益的全向天线，天线高度为 1.5m，接收阈值为-80dbm，节点初始最大发射功率为 0.0064W(

32、此时每个节点传输半径为 250m。 每个节点在链路层和网络层分别使用基于 802.11 标准的 MAC 协议和 DSR 路由协议。每个 CBR 数据流的源节点和目的节点随机选择，数据 包的大小为 1K 字节，每个源节点产生分组速率(单位为 packets/s从 0.25 到 2.5，发送间隔 时间服从泊松分布。仿真时间为 500s。仿真中，根据节点最大功率构建的初始拓扑结构（简 称 UDG）和 3 种不同拓扑控制算法（LIFE、API 和 ISPT）生成的拓扑结构，设置每个节点 的发射功率。对于每一个拓扑结构，设置 CBR 数据流从 20 个增加到 50 个。我们统计了 10 次仿真后的结果，

33、取平均值，比较不同业务负载下 4 种不同结构网络的传输性能，即在不同 业务负载下的网络分组交付率的变化，交付率是指网络总接收数据量和总发送数据量的比 值，可以反映网络的数据传输效率。 仿真结果发现，对于每一个拓扑结构，随着数据流数量的增加和发包速率的增加，网络 的传输性能表现出逐渐下降的趋势。而对于相同数据流的数量，随着发包速率的增加，4 种 不同拓扑结构对网络性能的影响趋势和比较结果相同，本文取 40 个数据流的仿真结果进行 具体描述和分析。 4 和图 5 分别给出了随着网络负载的增加， 图 四种拓扑结构对网络路由请 求包数和网络分组交付率影响的变化趋势。 由图 4 可知，当负载较低时（网络

34、负载小于 10 包/秒） ，路由请求数小，说明网络中的 通信碰撞概率较低，路由稳定且开销小。如图 5 所示，网络的吞吐率接近 100%，有无拓扑 控制对网络的性能影响不是很大。但是，由 4.1 节的实验可知 LIFE 算法构建的网络是最稀 疏的，所以即使网络流速小，但由于网络流数多，经过路由后，汇聚到相同的干扰瓶颈节点 区域造成分组竞争信道失败的概率变大，引起 DSR 路由协议不断重新进行路由请求，如图 4 所示，LIFE 算法生成的拓扑图在低负载时，路由请求包数是其余三种结构的 5 倍，大量 的路由开销降低业务流的端到端通过量。 这说明按照局部干扰最小化思想设计拓扑控制算法 会造成网络拓扑过

35、于稀疏， 增加了路径长度和流间干扰， 最终并不能有效地优化网络传输能 力。 如图 4 所示，随着网络负载的增加，各个分组同时竞争信道的概率变大，而分组对信道 竞争的加剧会使得链路失败概率增加，导致 DSR 路由协议不断寻找新的路由，产生大量的 路由开销，如图 5 所示，业务流的端到端通过量从而显著降低。由 4.1 节的实验可知，按照 路径和全局网络最小化干扰思想设计的 API 和 ISPT 算法构造的拓扑结构，即减小了局部干 扰，又保证了路径长度稳定，也就减小了路径干扰，如图 5 所示，与 UDG 相比，提高了空 间复用度， 增加了网络吞吐率。 其中 ISPT 算法由于可保证生成的拓扑图中路径

36、干扰最小 （证 明见 3.2 节） ，与 API 算法相比，网络吞吐率提高了约 10%。 16000 14000 1 路由请求包数(packets 12000 10000 8000 6000 4000 2000 0 分组交付率(% ISPT API LIFE UDG 0.8 0.6 0.4 0.2 0 ISPT API LIFE UDG 10 20 30 40 50 60 70 80 90 100 网络输入流量(packets/s 10 20 30 40 50 60 70 80 90 100 网络输入流量(packets/s Fig. 4 Routing overhead obtained f

37、rom CBR flows Fig. 5 Fraction data Pks delivered obtained from at various loads 图 4 在不同业务负载下的路由请求包数比较 CBR flows at various loads 图 5 在不同业务负载下的分组交付率比较 5 结论 本文主要研究了如何定义并降低自组网中的干扰以提高网络传输能力的问题。 通过分析 现有的拓扑控制算法及其存在的局限性， 从拓扑结构的角度提出新的干扰度量方法； 在此基 础上给出干扰最小化拓扑控制算法ISPT。与其它的干扰模型相比，新的基于协议的干扰 模型兼顾了链路通信的干扰情形和整个路径上多

38、跳转发时的流内和流间干扰， 更全面直观地 反映现实网络的干扰情形。分布式算法ISPT的主要特点是获取算法执行所需数据的代价小， 且算法运行简单快速。该算法从全局的观点出发，更注重对网络的整体干扰的控制，而不是 只关注某些局部或者特殊情形下的干扰， 在保证网络连通的前提下使网络的路径干扰尽量最 小，并且通过在ISPT中加入准干扰瓶颈节点避免机制，较好地避免了在稀疏网络中路由瓶 颈问题造成的流间干扰概率增大现象。 仿真结果说明， ISPT算法与未经拓扑控制及已有的干 扰最小化拓扑控制算法LIFE、API相比，更好地改善了网络的性能。 由于干扰与网络负载情况和网络协议簇的机理紧密相关， 因此仅仅在网

39、络实际应用前运 用拓扑控制优化拓扑结构还不够。 在下一步的工作中， 我们将研究感知网络负载状态的自适 应拓扑控制技术以及干扰瓶颈节点处理技术， 并在协议簇各层上采用干扰最小化技术进一步 提高网络的性能。 参考文献： 参考文献： 1 Goldsmith A J, Wicker S BDesign challenges for energy-constrained Ad Hoc wireless networksJIEEE Wireless Communications, 2002, 9(4: 8-27. 2 SHEN Zhong, CHANG Yi-Lin, et al. A Distribut

40、ed Topology Control Algorithm for Self-Maintenance of the Minimum-Energy Property of a Wireless Networks TopologyJ. Chinese Journal of Computers, 2007, 30(4: 569-578. 沈中等. 一种建立可自维护且具有最小能 量特性的无线网络的分布式拓扑控制算法. 计算机学报, 2007, 30(4: 569-578. 3 P. Santi. Topology Control in Wireless Ad hoc and Sensor Networ

41、ksJ. ACM Comp. Surveys. 2005, 37(2: 164194. 4 Lu Gang, Zhou Mingtian, Niu Xinzheng, et al. A Survey of Proximity Graphs in Wireless NetworksJ. Journal of Software, 2008, 19(4: 888911. 路纲等. 无线网络临近图综述J. 软件 学报, 2008, 19(4: 888911 5 Davide Bilo, Guido Proiettib. On the complexity of minimizing interfere

42、nce in ad-hoc and sensor networksJ. Theoretical Computer Science, 2008, 402(1: 43-55. 6 K. Moaveni-Nejad and X. Li. Low-interference topology control for wireless ad hoc networksJ. Ad Hoc & Sensor Wireless Networks: An International Journal, Volume 1, Number 1-2, 2005: 41-64. 7 P. von Rickenbach

43、, S. Schmid, R. Wattenhofer, A. Zollinger. A robust interference model for wireless ad-hoc networksC/ Proceedings of 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN, USA, 2005:239-247. 8 Magnús M. Halldórsson, Takeshi Tokuyama. Minimizing interference of a wireless ad-hoc network in a planeJ. Theoretical Computer Science archive, 2008, 402(1: 29-42. 9 M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger. Does Topology Control Reduce Interference?C/ Proceedings of 5th ACM Int.