基于干扰度优化的连通子图生成算法

刘 迪

(河池学院 物理与电子工程系，广西 宜州 546300)

无线Ad Hoc网络［1］(Wireless Ad Hoc Network)是一种拓扑结构动态变化的无线通信网络，能够灵活地用于各种无固定基站支撑的应用环境。在军事侦察、环境监测、安监等领域有着广泛的应用前景。随着研究工作的不断深入和逐步走向应用，其作为一种新的互联模式又推动着科技的进步与社会的发展，成为目前研究的重点和热点［2－4］。但是，Ad Hoc网络容易因节点移动、障碍物阻挡而造成信号衰减等多种原因导致网络拓扑不能正常连通，而网络拓扑结构的连通是端到端数据传输的基本保障，也是路由算法正常工作的前提。因此，开展拓扑结构连通性相关研究是提高Ad Hoc网络性能的一个不可绕开的环节。

当前，国内外学者对Ad Hoc网络的连通性问题展开了相关的研究，也取得了一些进展，但研究并不充分。如文献［5］中提出了一种集中式拓扑生成算法—BICONN和一种分布式拓扑生成算法—LILT，通过以上算法来寻找关键节点并重构二连通拓扑结构，降低了路由协议的复杂度。文献［6］认为，在CBTC(α)中，当α=2π/3K时，GE相对于G0是K连通的，并对此进行了证明和验证。文献［7］在分析随机分布的传感器节点的信号覆盖半径与形成K+1点连通图G0的概率关系的基础上，提出Yp，K+1结构能够使GE保持G0的K+1点连通性，为连通子图的构建提供了一定的参考依据。文献［8］提出了分布式控制算法——FLSS，并从图的K点连通性出发，保证一个K点连通图G0经过拓扑重建后生成的新拓扑图GE仍然是一个K点连通的子图，实现了网络中部分传感器节点主动休眠和异常修复功能并降低了上层路由协议的算法复杂度。

从控制整个网络干扰度的基准点出发，本文提出了基于干扰度优化的连通子图生成算法DBSA(Disturbance Based Subgraph Generation Algorithm)。首先构建一张原始拓扑图的空子图，然后在分析影响整个网络干扰度相关因素的基础上利用优化算法筛选出干扰度较低的链路不断的加入到该子图中，直到形成K连通的拓扑结构图，在此连通子图的基础上进行路由选择时，其算法计算的复杂度能大幅度降低，从而达到提高网络性能和可持续性的目的。

1 网络模型定义

在Ad Hoc网络中，分布在其中的各传感器节点通过无线信道以自组织的方式聚合在一起工作，节点位置均匀分布并且相互独立，即节点的加入和退出自主决定，从而形成一张松耦合的动态网络。网络中每个节点都能感知并采集周围环境的信息并将数据分组以多跳转发的方式发送给汇聚节点，所有节点都拥有相同的传输功率，其无线信号覆盖半径为R。则有，当且仅当两节点V，E间的欧几里德距离小于或者等于无线信号覆盖半径R时，V和E才能够直接进行通信。于是，可以将Ad Hoc网络描述为几何随机图G(V，E)，也即网络的原始拓扑图。为了简化网络结构，在完成原始拓扑图初始化的同时还创建一张没有端点和边的空拓扑图用于构建子图，定义为G'(V，E')。模型的基本思想就是按照步骤在此空图中添加合适的边(链路)，边的选择要求保证通过多次添加后得到的新图仍是原始拓扑图的子图，并且新图的连通度大于或等于K。构建步骤如图1所示。

图1 连通子图生成步骤

2 算法具体实现

2.1 干扰度影响

假设图G(V，E)中有节点i，其周围共有n个可以直接到达的邻节点，分别记为i1，i2，i3，…，in。接着定义其中某条信道c上的干扰对节点 i能直接到达的其它各链路的影响为“干扰度影响(II:Impact of Interference)”［9］:

式中，L(i)是节点i上等待分配信道的下行接口的数据包流量，L(id)是节点id上对应的上行接口的数据包流量。ALc(i)和ALc(id)则分别表示节点i和节点id的K跳范围内的相邻节点在信道c上的总流量，并以此作为节点i和节点id在信道c上分别受到的干扰。这是后面算法选择哪条链路加入到连通子图的判断依据。

2.2 连通子图生成

算法执行步骤如图2所示:在初始状态下网络中不存在任何的链路和信道的信息，即此时网络中不存在干扰，整个网络的干扰度为0，可标记为I(G)=0。从初始的网络拓扑结构图G(V，E)中任意选取一条链路e添加到空的子图G'(V，E')中，成为新的子图。然后继续在G(V，E)中选取新的边(链路)加入到G'(V，E')中，如果新加的边和G'(V，E')中的所有边都没有产生干扰，那么操作继续。若新添加的这条边与原有的边e产生干扰，即e'∈IEe，那么对于链路e来说新链路的加入对它产生了干扰，其干扰度要加1，即I(e)加1。

为了避免网络中信道的利用率不断降低，必须有效控制G'(V，E')的干扰度。因此，不能采取随机选边的策略，而是要根据整个网络的干扰度的情况来选取链路。根据式(1)的定义进行分析和计算可知，网络的干扰度取决于其中干扰度最大的链路。因此，必须避免具有最大干扰度的链路被添加进G'(V，E')中。为了达到这个目的，需要对可到达i1，i2，i3，…，in的每条链路的干扰度进行分析并从中选择干扰度最低的链路加入到子图G'(V，E')中，以此来有效的控制新添加的链路对整个网络的信道产生的干扰。

通过以上的方法可以有效的控制整个网络的干扰度，但是，每次添加了新的链路后都必须要重新计算整个网络中所有链路的干扰度，对于计算能力较强、不用考虑能量供应的普通网络，该方法可行性较强。在Ad Hoc网络中，节点的计算能力和能量供应都受到严格限制，因此必须进行优化。通过节2.1中对于干扰影响的分析可知，某条链路的加入只会对其两端影响范围内的链路产生干扰，即只会影响其两跳范围内的节点。因此，为了降低算法的计算复杂度和节省节点的能量，添加新的链路后并不进行全局干扰度的计算，而是只计算新添加链路两端点两跳范围内其它节点的干扰度。

图2 算法执行步骤

通过上述操作，原始拓扑图G(V，E)中的链路会不断地被添加到新的子图G'(V，E')中，直到该子图所表示的拓扑结构是K连通的。一般情况下，我们判断拓扑子图是否为K连通的标准是——图中所有节点都是K连通，这样就需要遍历图中所有节点。考虑到Ad Hoc网络的实际情况，我们将已经达到K连通标准的节点从待计算集合中剔除，以便下次不再计算它们，节省计算量。最后，当G'(V，E')中的所有节点都实现了K连通后，该计算集合为空，算法结束。得到的最终子图G'(V，E')就是一个K连通的子图［10］。

3 模拟与仿真分析

3.1 模拟与仿真环境实现

DBSA算法没有涉及到MAC层和网络层，算法的模拟与仿真分析在VC平台下实现。具体的模拟与仿真环境参数设置如表1所示。

表1 模拟与仿真环境参数设置

3.2 仿真结果及分析

在当前节点分布密度情况下，当Rc/Rs的比值在2～3之间变化时，随着连通度K的变化，算法实现K连通所需的节点数的变化如图3所示。从结果可知:当Rc/Rs=3时，K值随着节点数的增加呈近乎线性提高;如果固定连通度K为3，变化活跃节点总数，在不同节点分布密度下，将本算法与CPC算法进行对比分析，结果如图4所示。从结果可知:要实现固定的K连通值，两种算法所需的节点数都随着节点密度值的增加而减少，即提高节点密度可以减少活跃节点的数量，从而延长整个网络的生命周期。DBSA算法比CPC［11］算法在该技术指标上有大约20% 的性能提升(Rc/Rs的比值为2时)，即转发代价更低。

图3 Rc/Rs为不同值时，所需节点数随K值的变化关系

图4 K=3时，节点数随Rc/Rs的变化关系

4 小结

在分析影响Ad Hoc网络干扰度影响因素的基础上，提出了一种适用于Ad Hoc网络的链路分析、选择方法，并以此为依据来选择合适的链路，逐步添加并完善连通子图，最终构建出一种基于干扰度优化的连通子图生成算法—DBSA。在此基础上，搭建实验模型并利用VC平台对算法可用性进行验证分析。结果表明:算法能用较少的节点数来实现有效的K连通，拥有较低的转发代价。

［1］R Ramanathan，J Redi.A brief overview of ad hoc networks:challenges and directions［J］.IEEE Communication Magazine，2002，40(5):20－22.

［2］田野，盛敏，李建东，等.一维 Ad Hoc网络二连通性研究［J］.电子学报，2008，36(4):715－719.

［3］黄晓，程宏兵，杨庚.无线传感器网络覆盖连通性研究［J］.通信学报，2009，30(2):129－135.

［4］张文铸，刘佳，张林，等.无线传感网络的非分簇拓扑控制方法研究［J］.计算机科学，2010，37(2):44－47.

［5］F Sun，M Shayman.Minimum interference algorithm for integrated topology control and routing in wireless optical backbone networks［C］.in Proceedings of IEEE International Conference on Communications，2004:20 －24.

［6］Ramanathan R，Rosales－Hain R.“Topology control of multihop wireless networks using transmitpower adjustment”Proc IEEE INFOCOM［C］.Tel－Aviv，Israel:IEEE communication society，2000:404 －413.

［7］M Bahramgiri，M T Hajiaghayi，V S Mirrokni.“Fault－ tolerant and 3 － dimensional distributed topology control algorithms in wireless multi－ hop networks”IEEE Int［C］.Conf on Computer Communications and Networks(ICCCN02).Miami，Florida，USA:ACM press，2002:392 －397.

［8］MHajiaghayi，N Immorlica，V S Mirrokni.Power optimization in fault－ tolerant topology control algorithms for wireless multihop networks［C］.Proc ACM International Conference on Mobile Computing and Networking(MOBICOM).SanDiego，CA，USA:ACM SIGMOBILE，2003:300－312.

［9］周斌.多接口无线Mesh网络信道分配机制研究［D］.杭州:浙江大学，2010.

［10］M Hajiaghayi，N Immorlica，V S Mirrokni.Power optimization in fault－ tolerant topology control algorithms for wireless multihop networks［C］.Proc ACM International Conference on Mobile Computing and Networking(MOBICOM).SanDiego，CA，USA:ACM SIGMOBILE，2003:300－312.

［11］徐涛，黄刘生，徐宏力，等.无线传感网络中覆盖保持的K－连通子集构造算法［J］.小型微型计算机系统，2010，31(5):871－874.