考虑通信质量的网络最小主控集生成算法*

刘 邈

(中国西南电子技术研究所，成都 610036)



考虑通信质量的网络最小主控集生成算法*

刘 邈**

(中国西南电子技术研究所，成都 610036)

无人移动平台无线ad hoc网络在实际应用中经常会出现由于电磁环境、干扰等因素导致通信质量不稳定的情况，在上述条件下传统的基于节点覆盖度的最小主控集(MCS)生成算法难以获得具有较好稳定性、健壮性的最小主控集。为此，提出了一种考虑通信质量的网络最小主控集生成算法，将链路的通信质量纳入网络最小主控集构造的考虑因素，使网络拓扑与链路通信质量特性保持一致；并通过对候选节点集及拟覆盖节点集的压缩，有效控制了网络最小主控集的节点数目。仿真表明,对敏感于通信质量的应用,该算法较基于节点覆盖度算法能取得更好效果。

无人移动平台；无线自组织网；通信质量;最小主控集;网络拓扑

1 引 言

无人平台移动网络在当今社会生活中有越来越广泛的应用，例如：通信基础设施难以部署的应急网络通信、无人移动平台传感器网络以及无控制中心的分布式军事通信等均有应用。无人平台移动网络具有无中心、分布式、自组织等特点，高效、准确的网络拓扑维护至关重要。根据图论理论，最小主控集(Minimum Control Set,MCS)很适宜在上述无中心、分布式网络中构建虚拟骨干网，其将在无线自组网的路由、广播以及连通性维护中发挥重要作用[1]。

1997年,Das等人[2]首次提出了分布式架构ad hoc虚拟骨干网络的概念，其与网络最小主控集概念一致。2001年,Stojmenovie等[3]首先提出采用极大独立集(Maximum Independent Set,MIS)思路构造最小主控集算法，其通过先求取网络的若干MIS(由图论理论,极大独立集必为极小主控集)，再选取一些节点作为“桥梁”连接所求极大独立集，最终获得近似的网络最小主控集。Qayyum等提出了多点中继(Multipoint Relay,MPR)算法，这是一种基于邻节点指派的主控集构造算法。LI[4-5]探讨了(1,m)、(2,m)两种主控集算法，并在2012年提出了一种分布式确定主控集算法(Distributed Deterministic Algorithm,DDA)。Gao等[6]提出了一种分布式主控集算法(Dominating Set Based Algorithm,DSBA)。DDA算法、DSBA算法都是将网络节点覆盖度作为重要判断依据，都属于传统MPR多点中继算法思路。上述最小主控集构造算法在针对多路径节点进行选择时没有考虑网络成员间链路通信质量因素对实际运行时网络负载、网络通信效率等方面的影响，同时较多注重考虑如何快速地获得最小主控集，在一定程度上导致最终的最小主控集节点规模过大。

本文针对网络节点通信质量在众多应用场景下对信息传输影响较大这一特点，提出一种考虑通信质量的网络最小主控集生成算法，其将链路的通信质量纳入网络最小主控集构造的考虑因素，使网络拓扑与链路通信质量特性保持一致；同时，算法通过对候选节点集及拟覆盖节点集的压缩，有效控制了网络最小主控集的节点数目。

2 考虑通信质量的网络最小主控集生成算法

2.1 算法基本思路

考虑通信质量的网络最小主控集生成算法思路如下：

(1)根据网络需求首先选定起始节点x开始算法运行；

(2)搜索节点x的下级主控节点集NLMCS(x)，包括搜索单路径节点和搜索多路径节点两步；

(3)对于搜索获得的起始节点x的下级主控节点y搜索其下级主控节点集NLMCS(y)，包括压缩候选节点集和拟覆盖节点集、搜索单路径节点、搜索多路径节点3步；

(4)将y替换x作为上级节点，对y的下级主控节点yi选取其下级主控节点集NLMCS(yi)；

(5)若网络内的所有节点已都属于NLMCS的封闭邻居集当中了，则认为本算法满足结束条件。

网络拓扑典型场景如图1所示。

图1 网络拓扑的典型情况示意

在本算法中将量化的节点通信质量作为多路径节点选择的依据，具体而言，针对有多路径可选的下级主控节点，优先在当前仍有效的候选节点中选择通信质量最优的节点。

2.2 算法描述

NeiNodes1为一跳邻节点集；NeiNodes2为两跳邻节点集；NeiIntersec(y,x)为节点y和节点x的公共邻节点集；CandiNodes为候选节点集；IntendCov为拟覆盖节点集；CovCapa为覆盖能力集；NLMCS为下级主控节点集；Onlyone为唯一路径节点寄存集；IntCovReg为拟覆盖节点寄存集；SumCapa为覆盖能力总和集；NodeComQua为节点通信质量值；NetComLoad为网络通信负载值，其值越小表示网络通信负载情况越好；MCSnum为网络主控集节点总数。

首先，对量化的节点通信质量NodeComQua进行定义：节点y发送数据包到其n个邻节点的丢包率分别为e1,e2,…,en，其邻节点之一ri成功接收到其发送的消息时节点y所需发送的次数为随机变量Xi，n个邻节点都成功接收到其发送的消息时，节点y所需发送的次数为随机变量Y，那么,

Y=maxi∈{1,2,…,N}Xi。

(1)

结合网络实际运行情况可得，节点y与其各邻节点通信在相应链路上出现的丢包事件是相互独立的。因此，节点y发送数据包最多发送m次就使其全部邻节点均接收到的概率如下：

(2)

(3)

在此基础上，考虑通信质量的网络最小主控集生成算法的具体实现过程描述如下：

Step 1 选取起始节点。按照应用需求选取起始节点x，例如：起始节点根据应用需求选为消息或路径的发起节点，然后再按照下述算法步骤，选出节点x的各层下级主控节点。

Step 2 针对节点y，压缩其CandiNodes和IntendCov。

Step 2-1 初始时,CandiNodes(y)=NeiNodes1(y)-NeiNodes1(x)、IntendCov(y)=NeiNodes2(y)-NeiNodes1(x)-NeiNodes1(NeiIntersec(y,x))。

Step 2-2 考察NeiNodes2(y)中是否存在节点w，使w满足w∈NLMCS(x)；NodeComQua(w)

Step 2-3 重复Step 2-2，直至不存在满足条件的节点w为止。

Step 3 针对节点y，选择其下级单路径节点。

Step 3-1 初始时NLMCS(y)=∅、IntCovReg(y)=∅，对节点i∈CandiNodes(y)，设置CovCapa(i)=NeiNodes1(i)∩IntendCov(y)，SumCapa(y)=∪CovCapa(i)。

Step 3-2 若存在节点w∈IntendCov(y)，使CandiNodes(y)中仅有一个节点o满足o∈NeiNodes1(w)，即w能使下述条件成立：NeiNodes1(w)∩CandiNodes(y)={o}，那么将按照Step 3-3步处理。

Step 3-3NLMCS(y)=NLMCS(y)∪{o}，IntCovReg(y)=IntCovReg(y)∪CovCapa(o)，SumCapa(y)=SumCapa(y)-CovCapa(o)，CandiNodes(y)=CandiNodes(y)-{o}，且对于当前所有的CovCapa(i)∈SumCapa(y)均有CovCapa(i)=CovCapa(i)-CovCapa(o)。

Step 3-4 重复Step 3-2～Step 3-3，直至IntendCov(y)中不存在符合条件的节点w。此时，判断IntCovReg(y)是否等于IntendCov(y)，若等于则对节点y寻找其下级主控节点的过程结束；否则，继续执行算法Step 4。

Step 4 针对节点y，选择其下级多路径节点。

Step 4-1 在SumCapa(y)中搜索仍有效的CovCapa(q)，使得该CovCapa(q)其节点q的NodeComQua(q)最优，即NodeComQua(q)=min{NodeComQua(i)/i为SumCapa(y)中仍有效的CovCapa(i)对应的节点i。找到满足条件的节点q后按照Step 4-2处理。

Step 4-2NLMCS(y)=NLMCS(y)∪{q}，IntCovReg(y)=IntCovReg(y)∪CovCapa(q)，SumCapa(y)=SumCapa(y)-CovCapa(q)，CandiNodes(y)=CandiNodes(y)-{q}，且对于当前所有的CovCapa(i)∈SumCapa(y)均有CovCapa(i)=CovCapa(i)-CovCapa(q)。

Step 4-3 判断IntCovReg(y)是否等于IntendCov(y)，若等于，则对节点y搜索其下级主控节点的过程结束；若不等于，则重复Step 4-1～Step 4-2，直至等于为止。

3 算法性能仿真

以下将利用Matlab 7.1通过仿真对考虑通信质量的网络最小主控集生成算法与传统基于节点覆盖度最小主控集生成算法进行性能分析，包括网络通信负载值NetComLoad、最小主控集节点数MCSnum等主要性能指标的对比。其中，SelMCS算法选择节点y的下级主控节点时，多路径节点的选址将NodeComQua作为依据，对CandiNodes(y)、IntendCov(y)进行压缩；QDBA算法选择节点y的下级主控节点时，多路径节点的选址将NodeComQua作为依据，但未对CandiNodes(y)、IntendCov(y)进行压缩;MPR算法选择节点y的下级主控节点时，多路径节点的选址不以NodeComQua作为依据，而以邻节点度作为依据，同时不对CandiNodes(y)、IntendCov(y)进行压缩。仿真参数包括节点一跳通信距离ComDis、节点最大误包率PERmax、网络节点数n。

3.1 不同节点规模下各算法性能

节点一跳通信距离ComDis=30 km,节点最大误包率PERmax=0.35,网络节点数n=75∶10∶125,仿真结果如图2所示。

(a)不同节点规模下各算法网络通信负载

(b)不同节点规模下各算法MCS节点数

由图2可以看出：

(1)随网络节点数增加NetComLoad和MCSnum值均增加，3种算法变化趋势一致；

(2)SelCDS算法的NetComLoad和MCSnum值在网络节点规模从75～125的变化过程中，均优于QDBA算法和MPR算法。节点规模100：SelCDS算法NetComLoad和MCSnum值仅为100、37，明显大幅低于QDBA算法和MPR算法；节点规模125：SelCDS算法NetComLoad和MCSnum值分别为180和62，而QDBA算法和MPR算法在成员规模为100～105时就达到了该值；

(3)网络节点数保持中等规模时(75～100)，QDBA算法的NetComLoad和MCSnum值优于MPR算法;网络节点数达到大规模时(105～125)，QDBA算法的NetComLoad和MCSnum值与MPR算法相当。

结果表明，网络节点规模以及节点通信质量均对NetComLoad和MCSnum值产生影响。将两种因素均进行处理的SelCDS算法在各种网络节点规模条件下效果均较好；另一方面，随网络节点规模增大，由于候选节点选择范围增加，QDBA算法和MPR算法其多路径节点选择的差异将降低，因此最终效果差异减小。

3.2 不同通信半径下各算法性能

网络节点数n=70,节点最大误包率PERmax=0.35,节点一跳通信距离取值范围ComDis=28∶3∶46 km,仿真结果如图3所示。

(b)不同通信半径下各算法MCS节点数

由图3可以看出：

(1)随网络节点通信半径增大，NetComLoad和MCSnum值均减小，3种算法变化趋势一致：在通信半径从28增加到38阶段NetComLoad和MCSnum值减小较快，在通信半径从38增加到46阶段NetComLoad和MCSnum值相对下降得较为平缓；

(2)SelCDS算法的NetComLoad和MCSnum值在节点通信半径从28～46的变化过程中，均优于QDBA算法和MPR算法；在通信半径最小为28时，SelCDS算法的NetComLoad和MCSnum最大值仅为58、23，明显大幅低于此时QDBA算法和MPR算法的结果；随通信半径增大，该差距有所减小；

(3)在节点通信半径达到较大值(大于42)后，SelCDS算法和QDBA算法的NetComLoad和MCSnum值相当，但仍优于MPR算法。

结果表明，网络节点的通信半径以及节点通信质量均对NetComLoad和MCSnum值产生影响。将两种因素均进行处理的SelCDS算法在各种通信半径条件下效果均较好；另一方面，随着网络节点通信半径的增大，由于连通整个网络的跳数降低，故整个指标呈下降趋势；在节点通信半径达到较大值使得连通整个网络所需跳数明显大幅减小情况下，采用类似策略进行多路径节点选择的SelCDS算法和QDBA算法将有更大的概率选取到相同节点作为主控节点，因此会呈现上述第3点的情况。

3.3 不同最大丢包率下各算法性能

网络成员节点数n=70,节点一跳通信距离ComDis=25,节点最大误包率取值范围PERmax=0.1∶0.1∶0.7,仿真结果如图4所示。

(b)不同最大丢包率下各算法MCS节点数

由图4可以看出：

(1)随最大丢包率增加，NetComLoad值增加，3种算法的变化趋势一致,这是由于NetComLoad计算是根据所选连通主控节点计算其一个通信随机过程中的节点通信质量权值总数，因此节点最大丢包率增加，对于3种算法均会使其最终的NetComLoad值增大；

(2)随最大丢包率增加，MCSnum值的变化：SelCDS算法和QDBA算法受节点通信质量的影响，其主控节点选择均会有所变化,但总体来说，SelCDS算法要优于QDBA算法;而MPR算法由于其节点选择的判决条件中未考虑节点通信质量，因此其所选的连通主控节点保持不变;

(3)SelCDS算法的NetComLoad和MCSnum值，在最大丢包率的变化范围内均优于QDBA算法和MPR算法。

结果表明，网络节点通信质量会对NetComLoad产生影响，对于MCSnum值是否会有影响，则取决于算法是否将节点通信质量考虑进算法处理。将两种因素均进行处理的SelCDS算法在各种最大丢包率条件下效果均较好；另一方面，随着网络节点最大丢包率增大，各算法NetComLoad值均呈增大趋势。在最大丢包率取值较大(高于65%)时，SelCDS算法性能指标更优，表明在网络节点链路可能出现高丢包率的突发误包条件下，采用SelCDS算法将更具优势。

4 结 论

本文考虑通信质量的网络最小主控集生成算法，将节点通信质量纳入网络最小主控集构造考虑因素。仿真对比表明，在节点数n=80、通信半径22 km、最大丢包率0.32条件下,SelMCS算法NetComLoad=65,MCSnum=25个，均优于QDBA、MPR算法。因此，本算法对于通信质量敏感的应用，如应急救灾分布式通信网、战术应用自组织网等，将更有助于获得高效、稳定的虚拟骨干网，从而便于网络运行维护,取得更好的通信效果。

[1] WANG Y M,ZHAO D S. Construction and analysis of connected dominting set based on serial maximum independent set[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2011,39(3): 66-70.

[2] DAS B,R SIVAKUMAR,BHARGHAVAN V. Routing in ad hoc networks using a spine[C]//Proceedings of 1997 IEEE International Conference on Computer Communications and Networks(ICCCN 1997).Las Vegas,NV,USA:IEEE,1997:34-39.

[3] STOJMENOVIE I,SEDDIGH M,ZUNIE J. Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(l):14-20.

[4] LI Y,SHUAI T,AI W. Construction of 1- and 2-connected k-totally dominating set in disk graph[C]//Proceedings of the 4th International Jiont Conference on Computational Sciences and Optimzation(CSO). Kunming:IEEE,2011:1296-1299.[5] LI Y,WU Y,AI C,BEYAH R. On the construction of k-connected m-dominating sets in wireless networks[J].Journal of Combinatorial Optimization,2012,23(1):118-139.

[6] GAO X F,XU B S,LI J. A distributed design for minimum 2-connected m-dominating set in bidirectional wireless ad-hoc networks[J].Tsinghua Science and Technology,2012,17(5):553-566.

A Network MCS Constructing AlgorithmConsidering Communication Quality

LIU Miao

(Southwest China Institute of Electronic Technology，Chengdu 610036,China)

In actual applications,the communication quality of wireless ad hoc networks for unmanned mobile platforms is probably instable due to the complex electromagnetic environment or the jamming. In this case,minimum control set(MCS) constructing algorithms based on nodes coverage struggle to obtain the MCS with good stability and robustness. So a network MCS constructing algorithm considering communication quality is discussed in this paper. The network topology is in accordance with the communication quality,because the communication quality is taken into consideration in constructing the MCS. In addition,this algorithm limits the amount of the network MCS nodes effectively,via reducing the amount of candidate nodes and nodes which will be covered. The simulation shows that this algorithm works better than MCS constructing algorithms based on nodes coverage for the applications sensitive to the communication quality.

unmanned mobile platform;wireless ad hoc network;minimum control set(MCS);communication quality;network topology

10.3969/j.issn.1001-893x.2017.06.012

刘邈.考虑通信质量的网络最小主控集生成算法[J].电讯技术，2017,57(6):685-689.[LIU Miao.A network MCS constructing algorithm considering communication quality[J].Telecommunication Engineering,2017,57(6):685-689.]

2016-11-10；

2017-03-20 Received date:2016-11-10；Revised date：2017-03-20

TN915.02

A

1001-893X(2017)06-0685-05

刘 邈(1982—),男,四川成都人，2015年于电子科技大学获硕士学位,现为工程师，主要从事通信系统及网络设计。

Email：liumiao_nj@163.com

**通信作者：liumiao_nj@163.com Corresponding author：liumiao_nj@163.com