基于最小覆盖的多点中继集及其选择算法

陈明刚,张陆勇,刘 贺,陈 鹏

(北京邮电大学信息与通信工程学院,北京100876)

0 引言

无线网状网(WMN)中,每个节点都可以在其他节点协助下以多跳方式与网络中任何节点进行通信。由于WMN的多跳特性,传统的泛洪(Flooding)广播会占用大量的网络资源。在WMN中,带宽是宝贵的资源,有效利用带宽,对提升网络性能十分关键。文献[1]提出了一种高效的广播机制:多点中继广播。多点中继广播在保证全网节点都收到广播分组的前提下,通过减少参与转发广播分组的节点数目来降低广播对网络的影响。同时文献[1]证明多点中继集的选取是一个NP完全问题,研究人员提出了不同的启发式算法来解决这个问题。其中文献[1]使用了一种贪婪构造算法来选取多点中继集合。除了贪婪算法,一些现代的启发式算法也被积极运用到多点中继集的选取中来。文献[1]使用遗传算法来解决多点中继集的选取问题,文献[2]应用蚁群算法解决这个问题。

多点中继集是多点中继广播机制实现的关键。目前基于图论中最小控制集理论的多点中继集是包含有最少1跳邻居节点数目的集合。在WMN中,存在不同1跳邻居节点对相同2跳邻居节点的重叠覆盖现象,导致同一个2跳邻居节点会从不同的1跳邻居节点接收到相同的广播分组。这不但会造成带宽和节点能量的浪费,甚至会引起分组碰撞,导致消息接收失败,影响广播的质量。但包含节点数目最少的多点中继集并没有考虑重叠覆盖的影响。为了减少重叠覆盖的影响,文章定义了一种使重叠覆盖数最少的多点中继集,并提出构造它的快速启发式算法。

1 多点中继广播

多点中继广播机制通过控制参与转发广播分组的节点数目来减小广播对网络的影响。每个节点从它的1跳邻居节点集合中选取一个子集来转发广播分组。这些被选中的1跳邻居节点组成了这个节点的多点中继集,这个节点自身被称为多点中继决策者。每个节点都维护一个多点中继决策者集合,集合中包含当前将本节点选为多点中继集的邻居节点。每个节点都可以接收和处理分组,转发来自多点中继决策者的广播分组,但并不能转发来自多点中继决策者集合以外的节点发送的广播分组。

1.1 多点中继集

多点中继集是实现多点中继广播机制的关键。网络中每个节点独立计算自己的多点中继集。一个节点的多点中继集必须保证与其全部1跳邻居节点集合具有相同的网络覆盖范围。

一个节点的所有1跳、2跳邻居节点以及1跳与2跳邻居节点之间的连接关系(不考虑1跳或2跳邻居节点内部的连接关系)组成了一个非连通偶图,非连通偶图由n个连通偶图组成。从每个连通偶图中选出节点的部分多点中继集,那么这些部分多点中继集的并集就是节点的多点中继集。所以文章将主要研究节点在连通偶图中的多点中继集及其选择算法。

节点S的多点中继集(记为MPR(S)),是能够覆盖所有2跳邻居节点,是具有最少节点数目的1跳邻居节点的集合。但是由于重叠覆盖现象的存在,仅仅使MPR(S)包含的1跳邻居节点数目最少,显然并不能使多点中继广播机制达到最好的效果。有效减少重叠覆盖的数量,能使广播对网络的影响更小。所以最优的多点中继集是在保证覆盖所有2跳邻居节点的同时,使重叠覆盖数最小的集合。

在理想情况下:

即MPR(S)中节点度的和等于2跳邻居节点的个数。这样既保证完全覆盖2跳邻居节点,又保证没有重叠覆盖现象的存在。

1.2 多点中继集与集合覆盖

构造2个向量 α和β,对应节点的1跳邻居节点集合和2跳邻居节点集合。通过 α和β,构造一个1跳邻居节点与2跳邻居节点之间的邻接矩阵γ。使 γ=αT*β。在 γ中每一行代表的是一个1跳邻居节点,每一列代表的是一个2跳邻居节点。第i行与第j列交叉的元素nij表示1跳邻居节点i和2跳邻居节点j的邻接关系。如果节点i和节点j直接相邻,则nij=1,否则nij=0。所以 γ是一个0-1矩阵。定义,为 1 跳邻居节点i所覆盖的2跳邻居节点数目。对于上面提到的2种多点中继集合,给出如下定义:

定义1:MN_MPR(Minimum Number MPR):包含最少1跳邻居节点数目并且覆盖所有2跳邻居节点的集合。

定义2:MC_MPR(Minimum Coverage MPR):累计覆盖2跳邻居节点数目最少并且覆盖所有2跳邻居节点的集合。

在 γ中,每一列代表一个2跳邻居节点,覆盖2跳邻居节点j必须满足所有2 跳邻居节点都被覆盖,就必须满足:在完全覆盖所有2跳邻居节点的同时,要求具备最小的这显然是对邻接矩阵 γ的集合覆盖问题。MC_ MPR便是集合覆盖问题中待选择的最小代价集,因此可以使用解决集合覆盖问题的方法来选取MC_MPR。

2 多点中继集选择算法

多点中继集选择算法获得的多点中继集的质量将直接影响多点中继广播的效果。MC MPR的选取问题是集合覆盖问题,集合覆盖问题是一个NP困难问题。解决集合覆盖问题,遗传算法和模拟退火算法是十分优秀的启发式算法,但是它们要求大量的计算资源,耗费较长的时间,这在WMN中是难以应用的。在WMN中,需要一个能够快速收敛的算法来计算节点的多点中继集,同时由于节点的运算能力有限,要求算法的尽可能简单,以减少节点的计算量。这样集合覆盖问题中基于拉格朗日松弛的渐进算法[3]需要大量的计算也无法在规定时间内完成MC_MPR的选取。贪婪算法作为一种成熟的快速启发式算法可以在很短时间内得到一个合适的解,这保证了它能够及时得到MC_ MPR,以保证多点中继广播的正常运行。结合WMN的特点,提出一种基于贪婪算法的快速启发式算法来解决MC_MPR 的选择问题。

2.1 多点中继集参数定义

在描述算法前首先做相关定义:N(x)为节点x的1跳邻居节点集合,N2(x)为节点x的2跳邻居节点集合。I为1跳邻居节点数目,J为2跳邻居节点数目。ci为1跳邻居节点i覆盖的2跳邻居节点数目。启发式算法是一种逐次迭代算法,在每一次迭代过程中都会选取一个合适的1跳邻居节点,将其从N(x)移入MPR(x),同时在N2(x)中将与选中1跳邻居节点关联的2跳邻居节点删除。N′(x)=N(x)-MPR(x)为待选1跳邻居节点集合。uN2(x)为N2(x)中将与选中节点关联的2跳邻居节点删除后,剩余未被MPR(x)覆盖的2跳邻居节点集合。ki为待选1跳邻居节点即N′(x)中节点i覆盖uN2(x)中的2跳邻居节点数目。ki在每次迭代过程中都是变化的,在算法开始前ki=ci。

2.2 MC_MPR 选择算法

MC_MPR选择算法分为4个阶段:

①初始化过程:完成算法所需数据的初始化工作。包括MPR(x)设置为空集,依据N2(x)初始化uN2(x),计算I,J,ci等参数;

②优选过程:由于存在某一2跳邻居节点被特定1跳邻居节点惟一覆盖的现象。所以这个特定的1跳邻居节点必然属于MPR(x)。通过优选过程,将这些特定1跳邻居节点直接选入MPR(x)。同时从uN2(x)将与它们关联的2跳邻居节点删除;

③迭代选择:判断uN2(x)是否为空,如果为空,说明MPR(x)已经完全覆盖所有2跳邻居节点,可以进入优化过程。如果uN2(x)非空,说明还有2跳邻居节点没有被覆盖。还需继续向MPR(x)填加合适的节点。计算N′(x)集合中每个节点的权值,比较它们的权值,从中选出权值最优的节点加入MPR(x)中。重新进入迭代选择过程;

④优化过程:判断MPR(x)是否存在冗余节点,删除冗余节点。

2.3 权值规则

在MC_MPR 选择算法的迭代选择步骤中,集合的依据。权值的计算方法直接影响算法的性能。可以选取ki作为权值,在每一次迭代过程中选出当前迭代过程中对uN2(x)中2跳邻居节点具有最大覆盖的节点加入MPR(x)。但仅仅考虑当前迭代过程中的最大ki,无法选出合适的MC_MPR。在MC_MPR的选择过程中,不仅需要考虑每次迭代过程中的ki,同时需要综合考虑ci以及迭代过程造成的影响。

由上述分析可知,MC MPR的选取是一个集合覆盖问题,在解决集合覆盖问题时是贪婪渐进算法合适的权值计算方法。使用这样的权值计算方能够得到与理论值十分接近的结果。因此,采用作为 MC_MPR选择算法中权值计算的规则。

2.4 算法性能分析

由以上MC_MPR选择算法获得的多点中继集为MPR(x),定义服从MC_MPR定义的最优解为MPR(x)*,Cmax为ci中的最大值。文献[4]证明在使用贪婪算法解决集合覆盖问题时有:

式中,Si为第i次迭代过程中选择的集合,即第i次迭代过程中MC_MPR选择算法选择的1跳邻居节点;为其所包含2跳邻居节点的个数;nij为相应γ矩阵中的元素;H(x)为x级调和级数。

由MC_MPR定义可知:

由式(2)经推导可以得到:

由MC_MPR 选择算法获得的MC MPR解,相对于MC_MPR最优解的近似率上界为H(Cmax)。

3 仿真结果

对MC_MPR多点中继广播进行仿真,并对仿真结果进行分析。为了尽可能减小网络中其他因素对仿真结果的影响,特假设如下:

①无线信道为理想信道;

②节点的物理载波侦听范围等于接收范围;N′(x)集合内节点的权值是选取节点进入MC_MPR

③网络中仅存在广播分组;

④对于每一个需要发送的广播分组,需要随机等待一个延迟时间T,然后发送;

⑤保证节点之间的连通性,不存在孤立节点。

3.1 仿真场景

在3 000 m×3 000 m的矩形区域中有200个节点,对不同节点密度的情况进行仿真。节点密度定义为:平均一个节点无线发射范围内的邻居节点数目。使用ns2仿真平台,仿真环境配置如表1所示。

表1 仿真环境配置

3.2 结果分析

在多点中继广播过程中,参与转发广播分组的节点数目随节点密度变化曲线如图1(a)所示。

图1 仿真结果

这个参数以相应节点密度MN_MPR的值归一化后得到。从图中可以看出随着节点密度的增大,MC_MPR较MN_MPR参与转发的节点的数目更少。在整个仿真过程中,每个节点以固定的速率发送广播消息,所以全网初始化的广播消息总量是固定的。仿真持续时间内,全网接收广播分组量以MN_MPR 的值归一化后随节点密度变化曲线如图1(b)所示。全网接收广播分组量是网络中所有节点在整个仿真过程中接收到的广播消息分组的总和,这其中包含重复接收的广播消息分组,这个参数反应了网络中重叠覆盖的情况。全网接收广播分组越多,说明相同分组被重复接收的次数越多,网络中重叠覆盖现象越严重。从图中可以看出,MC_ MPR可以明显降低全网接收的广播分组总数,特别是在网络密度较大的时候,MC_MPR 能够较MN_MPR降低30%左右,MC_MPR能够有效地降低广播对全网的影响,提高无线资源的利用率。

广播分组对网络的实际覆盖率随节点密度变化的曲线如图1(c)所示。广播分组对网络的实际覆盖率定义为:对于一个广播分组,网络中实际接收到这个分组的节点数量与全网节点数量的比值。广播的目的就是需要全网接收到被广播的信息分组,所以无论使用什么方法,都需要尽可能保证广播分组对网络的实际覆盖率尽可能等于1。从图1(b)可以看出,无论使用MN_MPR还是MC_MPR当节点密度大于20以后广播分组对网络的实际覆盖率都近似为1,说明它们都能完成广播的任务。但当节点密度小于10的时候,广播分组对网络的实际覆盖率就迅速恶化,在节点密度为4时,MC_MPR为0.7,同时MN_MPR 也仅为0.75,所以当网络节点密度很小时,MPR广播的实际覆盖率较小。

在洪泛广播过程中,一个广播分组在网络中的生存时间随节点密度变化的曲线如图1(d)所示。随着节点密度的增加,广播分组的生存时间也逐渐缩短。这是因为对于200个仿真节点,节点密度越大,网络的实际直径越小,需要的转发次数越少,使广播分组的生存时间更短。从图中可以看出在不同节点密度条件下MC_MPR 较MN_MPR广播分组的存活时间更短。

从仿真结果得出,使用MC_MPR可以有效提升多点中继广播的性能,特别在全网接收广播分组量、参与转发广播分组节点数目和广播分组实际生存时间这3个方面取得了很好的结果,仅仅在广播分组实际覆盖率这个指标上比其他权值的结果稍低,但是仍然能够确保实际覆盖率在0.96以上。

4 结束语

上述对多点中继广播,特别是多点中继集进行了研究。在WMN多跳环境下,考虑1跳邻居节点对相同2跳邻居节点的重叠覆盖现象,给出了一种最大限度避免重叠覆盖的多点中继集的定义MC_MPR ,并提出了一种快速启发式算法来构造这种多点中继集,对这种多点中继集的性能进行了仿真和分析。仿真结果表明,MC MPR 能够有效降低广播分组在网络中的存活时间,减少相同广播分组被重复接收的次数,降低广播对网络的影响,提高无线资源的利用率。

[1]CHIZARI H,HOSSEINI M,R S A.Multipoint Relay Selection Using GA[C].Kuala Lumpur:IEEE Symposium on Industrial Electronics and Applications(ISIEA 2009),2009:957-962.

[2]ZHAO X,SONG H,XIA H,et al.Using Ant Colony Algorithm for Solving Minimum MPR Set and OPENT Simulation[C].Nanjing:The1st International Conference on Information Science and Engineering(ICISE 2009),2009:3898-3901.

[3]CAPR ARA A,FISCHETTI M,TOTH P.A Heuristic Method for the Set Covering Problem[J].Operations Research,1999(47):730-743.

[4]HOCHBAUM D S.Approximation Algorithms for NP-hard Problems[M].Boston:PWS publishing company,1996:452-456.