劉 邈

(中國西南電子技術(shù)研究所，成都 610036)

?

考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法*

劉 邈**

(中國西南電子技術(shù)研究所，成都 610036)

無人移動平臺無線ad hoc網(wǎng)絡(luò)在實際應(yīng)用中經(jīng)常會出現(xiàn)由于電磁環(huán)境、干擾等因素導致通信質(zhì)量不穩(wěn)定的情況，在上述條件下傳統(tǒng)的基于節(jié)點覆蓋度的最小主控集(MCS)生成算法難以獲得具有較好穩(wěn)定性、健壯性的最小主控集。為此，提出了一種考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法，將鏈路的通信質(zhì)量納入網(wǎng)絡(luò)最小主控集構(gòu)造的考慮因素，使網(wǎng)絡(luò)拓撲與鏈路通信質(zhì)量特性保持一致；并通過對候選節(jié)點集及擬覆蓋節(jié)點集的壓縮，有效控制了網(wǎng)絡(luò)最小主控集的節(jié)點數(shù)目。仿真表明,對敏感于通信質(zhì)量的應(yīng)用,該算法較基于節(jié)點覆蓋度算法能取得更好效果。

無人移動平臺；無線自組織網(wǎng)；通信質(zhì)量;最小主控集;網(wǎng)絡(luò)拓撲

1 引 言

無人平臺移動網(wǎng)絡(luò)在當今社會生活中有越來越廣泛的應(yīng)用，例如：通信基礎(chǔ)設(shè)施難以部署的應(yīng)急網(wǎng)絡(luò)通信、無人移動平臺傳感器網(wǎng)絡(luò)以及無控制中心的分布式軍事通信等均有應(yīng)用。無人平臺移動網(wǎng)絡(luò)具有無中心、分布式、自組織等特點，高效、準確的網(wǎng)絡(luò)拓撲維護至關(guān)重要。根據(jù)圖論理論，最小主控集(Minimum Control Set,MCS)很適宜在上述無中心、分布式網(wǎng)絡(luò)中構(gòu)建虛擬骨干網(wǎng)，其將在無線自組網(wǎng)的路由、廣播以及連通性維護中發(fā)揮重要作用[1]。

1997年,Das等人[2]首次提出了分布式架構(gòu)ad hoc虛擬骨干網(wǎng)絡(luò)的概念，其與網(wǎng)絡(luò)最小主控集概念一致。2001年,Stojmenovie等[3]首先提出采用極大獨立集(Maximum Independent Set,MIS)思路構(gòu)造最小主控集算法，其通過先求取網(wǎng)絡(luò)的若干MIS(由圖論理論,極大獨立集必為極小主控集)，再選取一些節(jié)點作為“橋梁”連接所求極大獨立集，最終獲得近似的網(wǎng)絡(luò)最小主控集。Qayyum等提出了多點中繼(Multipoint Relay,MPR)算法，這是一種基于鄰節(jié)點指派的主控集構(gòu)造算法。LI[4-5]探討了(1,m)、(2,m)兩種主控集算法，并在2012年提出了一種分布式確定主控集算法(Distributed Deterministic Algorithm,DDA)。Gao等[6]提出了一種分布式主控集算法(Dominating Set Based Algorithm,DSBA)。DDA算法、DSBA算法都是將網(wǎng)絡(luò)節(jié)點覆蓋度作為重要判斷依據(jù)，都屬于傳統(tǒng)MPR多點中繼算法思路。上述最小主控集構(gòu)造算法在針對多路徑節(jié)點進行選擇時沒有考慮網(wǎng)絡(luò)成員間鏈路通信質(zhì)量因素對實際運行時網(wǎng)絡(luò)負載、網(wǎng)絡(luò)通信效率等方面的影響，同時較多注重考慮如何快速地獲得最小主控集，在一定程度上導致最終的最小主控集節(jié)點規(guī)模過大。

本文針對網(wǎng)絡(luò)節(jié)點通信質(zhì)量在眾多應(yīng)用場景下對信息傳輸影響較大這一特點，提出一種考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法，其將鏈路的通信質(zhì)量納入網(wǎng)絡(luò)最小主控集構(gòu)造的考慮因素，使網(wǎng)絡(luò)拓撲與鏈路通信質(zhì)量特性保持一致；同時，算法通過對候選節(jié)點集及擬覆蓋節(jié)點集的壓縮，有效控制了網(wǎng)絡(luò)最小主控集的節(jié)點數(shù)目。

2 考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法

2.1 算法基本思路

考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法思路如下：

(1)根據(jù)網(wǎng)絡(luò)需求首先選定起始節(jié)點x開始算法運行；

(2)搜索節(jié)點x的下級主控節(jié)點集NLMCS(x)，包括搜索單路徑節(jié)點和搜索多路徑節(jié)點兩步；

(3)對于搜索獲得的起始節(jié)點x的下級主控節(jié)點y搜索其下級主控節(jié)點集NLMCS(y)，包括壓縮候選節(jié)點集和擬覆蓋節(jié)點集、搜索單路徑節(jié)點、搜索多路徑節(jié)點3步；

(4)將y替換x作為上級節(jié)點，對y的下級主控節(jié)點yi選取其下級主控節(jié)點集NLMCS(yi)；

(5)若網(wǎng)絡(luò)內(nèi)的所有節(jié)點已都屬于NLMCS的封閉鄰居集當中了，則認為本算法滿足結(jié)束條件。

網(wǎng)絡(luò)拓撲典型場景如圖1所示。

圖1 網(wǎng)絡(luò)拓撲的典型情況示意

在本算法中將量化的節(jié)點通信質(zhì)量作為多路徑節(jié)點選擇的依據(jù)，具體而言，針對有多路徑可選的下級主控節(jié)點，優(yōu)先在當前仍有效的候選節(jié)點中選擇通信質(zhì)量最優(yōu)的節(jié)點。

2.2 算法描述

NeiNodes1為一跳鄰節(jié)點集；NeiNodes2為兩跳鄰節(jié)點集；NeiIntersec(y,x)為節(jié)點y和節(jié)點x的公共鄰節(jié)點集；CandiNodes為候選節(jié)點集；IntendCov為擬覆蓋節(jié)點集；CovCapa為覆蓋能力集；NLMCS為下級主控節(jié)點集；Onlyone為唯一路徑節(jié)點寄存集；IntCovReg為擬覆蓋節(jié)點寄存集；SumCapa為覆蓋能力總和集；NodeComQua為節(jié)點通信質(zhì)量值；NetComLoad為網(wǎng)絡(luò)通信負載值，其值越小表示網(wǎng)絡(luò)通信負載情況越好；MCSnum為網(wǎng)絡(luò)主控集節(jié)點總數(shù)。

首先，對量化的節(jié)點通信質(zhì)量NodeComQua進行定義：節(jié)點y發(fā)送數(shù)據(jù)包到其n個鄰節(jié)點的丟包率分別為e1,e2,…,en，其鄰節(jié)點之一ri成功接收到其發(fā)送的消息時節(jié)點y所需發(fā)送的次數(shù)為隨機變量Xi，n個鄰節(jié)點都成功接收到其發(fā)送的消息時，節(jié)點y所需發(fā)送的次數(shù)為隨機變量Y，那么,

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

(1)

結(jié)合網(wǎng)絡(luò)實際運行情況可得，節(jié)點y與其各鄰節(jié)點通信在相應(yīng)鏈路上出現(xiàn)的丟包事件是相互獨立的。因此，節(jié)點y發(fā)送數(shù)據(jù)包最多發(fā)送m次就使其全部鄰節(jié)點均接收到的概率如下：

(2)

(3)

在此基礎(chǔ)上，考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法的具體實現(xiàn)過程描述如下：

Step 1 選取起始節(jié)點。按照應(yīng)用需求選取起始節(jié)點x，例如：起始節(jié)點根據(jù)應(yīng)用需求選為消息或路徑的發(fā)起節(jié)點，然后再按照下述算法步驟，選出節(jié)點x的各層下級主控節(jié)點。

Step 2 針對節(jié)點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)中是否存在節(jié)點w，使w滿足w∈NLMCS(x)；NodeComQua(w)

Step 2-3 重復Step 2-2，直至不存在滿足條件的節(jié)點w為止。

Step 3 針對節(jié)點y，選擇其下級單路徑節(jié)點。

Step 3-1 初始時NLMCS(y)=?、IntCovReg(y)=?，對節(jié)點i∈CandiNodes(y)，設(shè)置CovCapa(i)=NeiNodes1(i)∩IntendCov(y)，SumCapa(y)=∪CovCapa(i)。

Step 3-2 若存在節(jié)點w∈IntendCov(y)，使CandiNodes(y)中僅有一個節(jié)點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)中不存在符合條件的節(jié)點w。此時，判斷IntCovReg(y)是否等于IntendCov(y)，若等于則對節(jié)點y尋找其下級主控節(jié)點的過程結(jié)束；否則，繼續(xù)執(zhí)行算法Step 4。

Step 4 針對節(jié)點y，選擇其下級多路徑節(jié)點。

Step 4-1 在SumCapa(y)中搜索仍有效的CovCapa(q)，使得該CovCapa(q)其節(jié)點q的NodeComQua(q)最優(yōu)，即NodeComQua(q)=min{NodeComQua(i)/i為SumCapa(y)中仍有效的CovCapa(i)對應(yīng)的節(jié)點i。找到滿足條件的節(jié)點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)，若等于，則對節(jié)點y搜索其下級主控節(jié)點的過程結(jié)束；若不等于，則重復Step 4-1～Step 4-2，直至等于為止。

3 算法性能仿真

以下將利用Matlab 7.1通過仿真對考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法與傳統(tǒng)基于節(jié)點覆蓋度最小主控集生成算法進行性能分析，包括網(wǎng)絡(luò)通信負載值NetComLoad、最小主控集節(jié)點數(shù)MCSnum等主要性能指標的對比。其中，SelMCS算法選擇節(jié)點y的下級主控節(jié)點時，多路徑節(jié)點的選址將NodeComQua作為依據(jù)，對CandiNodes(y)、IntendCov(y)進行壓縮；QDBA算法選擇節(jié)點y的下級主控節(jié)點時，多路徑節(jié)點的選址將NodeComQua作為依據(jù)，但未對CandiNodes(y)、IntendCov(y)進行壓縮;MPR算法選擇節(jié)點y的下級主控節(jié)點時，多路徑節(jié)點的選址不以NodeComQua作為依據(jù)，而以鄰節(jié)點度作為依據(jù)，同時不對CandiNodes(y)、IntendCov(y)進行壓縮。仿真參數(shù)包括節(jié)點一跳通信距離ComDis、節(jié)點最大誤包率PERmax、網(wǎng)絡(luò)節(jié)點數(shù)n。

3.1 不同節(jié)點規(guī)模下各算法性能

節(jié)點一跳通信距離ComDis=30 km,節(jié)點最大誤包率PERmax=0.35,網(wǎng)絡(luò)節(jié)點數(shù)n=75∶10∶125,仿真結(jié)果如圖2所示。

(a)不同節(jié)點規(guī)模下各算法網(wǎng)絡(luò)通信負載

(b)不同節(jié)點規(guī)模下各算法MCS節(jié)點數(shù)

由圖2可以看出：

(1)隨網(wǎng)絡(luò)節(jié)點數(shù)增加NetComLoad和MCSnum值均增加，3種算法變化趨勢一致；

(2)SelCDS算法的NetComLoad和MCSnum值在網(wǎng)絡(luò)節(jié)點規(guī)模從75～125的變化過程中，均優(yōu)于QDBA算法和MPR算法。節(jié)點規(guī)模100：SelCDS算法NetComLoad和MCSnum值僅為100、37，明顯大幅低于QDBA算法和MPR算法；節(jié)點規(guī)模125：SelCDS算法NetComLoad和MCSnum值分別為180和62，而QDBA算法和MPR算法在成員規(guī)模為100～105時就達到了該值；

(3)網(wǎng)絡(luò)節(jié)點數(shù)保持中等規(guī)模時(75～100)，QDBA算法的NetComLoad和MCSnum值優(yōu)于MPR算法;網(wǎng)絡(luò)節(jié)點數(shù)達到大規(guī)模時(105～125)，QDBA算法的NetComLoad和MCSnum值與MPR算法相當。

結(jié)果表明，網(wǎng)絡(luò)節(jié)點規(guī)模以及節(jié)點通信質(zhì)量均對NetComLoad和MCSnum值產(chǎn)生影響。將兩種因素均進行處理的SelCDS算法在各種網(wǎng)絡(luò)節(jié)點規(guī)模條件下效果均較好；另一方面，隨網(wǎng)絡(luò)節(jié)點規(guī)模增大，由于候選節(jié)點選擇范圍增加，QDBA算法和MPR算法其多路徑節(jié)點選擇的差異將降低，因此最終效果差異減小。

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

網(wǎng)絡(luò)節(jié)點數(shù)n=70,節(jié)點最大誤包率PERmax=0.35,節(jié)點一跳通信距離取值范圍ComDis=28∶3∶46 km,仿真結(jié)果如圖3所示。

(b)不同通信半徑下各算法MCS節(jié)點數(shù)

由圖3可以看出：

(1)隨網(wǎng)絡(luò)節(jié)點通信半徑增大，NetComLoad和MCSnum值均減小，3種算法變化趨勢一致：在通信半徑從28增加到38階段NetComLoad和MCSnum值減小較快，在通信半徑從38增加到46階段NetComLoad和MCSnum值相對下降得較為平緩；

(2)SelCDS算法的NetComLoad和MCSnum值在節(jié)點通信半徑從28～46的變化過程中，均優(yōu)于QDBA算法和MPR算法；在通信半徑最小為28時，SelCDS算法的NetComLoad和MCSnum最大值僅為58、23，明顯大幅低于此時QDBA算法和MPR算法的結(jié)果；隨通信半徑增大，該差距有所減??；

(3)在節(jié)點通信半徑達到較大值(大于42)后，SelCDS算法和QDBA算法的NetComLoad和MCSnum值相當，但仍優(yōu)于MPR算法。

結(jié)果表明，網(wǎng)絡(luò)節(jié)點的通信半徑以及節(jié)點通信質(zhì)量均對NetComLoad和MCSnum值產(chǎn)生影響。將兩種因素均進行處理的SelCDS算法在各種通信半徑條件下效果均較好；另一方面，隨著網(wǎng)絡(luò)節(jié)點通信半徑的增大，由于連通整個網(wǎng)絡(luò)的跳數(shù)降低，故整個指標呈下降趨勢；在節(jié)點通信半徑達到較大值使得連通整個網(wǎng)絡(luò)所需跳數(shù)明顯大幅減小情況下，采用類似策略進行多路徑節(jié)點選擇的SelCDS算法和QDBA算法將有更大的概率選取到相同節(jié)點作為主控節(jié)點，因此會呈現(xiàn)上述第3點的情況。

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

網(wǎng)絡(luò)成員節(jié)點數(shù)n=70,節(jié)點一跳通信距離ComDis=25,節(jié)點最大誤包率取值范圍PERmax=0.1∶0.1∶0.7,仿真結(jié)果如圖4所示。

(b)不同最大丟包率下各算法MCS節(jié)點數(shù)

由圖4可以看出：

(1)隨最大丟包率增加，NetComLoad值增加，3種算法的變化趨勢一致,這是由于NetComLoad計算是根據(jù)所選連通主控節(jié)點計算其一個通信隨機過程中的節(jié)點通信質(zhì)量權(quán)值總數(shù)，因此節(jié)點最大丟包率增加，對于3種算法均會使其最終的NetComLoad值增大；

(2)隨最大丟包率增加，MCSnum值的變化：SelCDS算法和QDBA算法受節(jié)點通信質(zhì)量的影響，其主控節(jié)點選擇均會有所變化,但總體來說，SelCDS算法要優(yōu)于QDBA算法;而MPR算法由于其節(jié)點選擇的判決條件中未考慮節(jié)點通信質(zhì)量，因此其所選的連通主控節(jié)點保持不變;

(3)SelCDS算法的NetComLoad和MCSnum值，在最大丟包率的變化范圍內(nèi)均優(yōu)于QDBA算法和MPR算法。

結(jié)果表明，網(wǎng)絡(luò)節(jié)點通信質(zhì)量會對NetComLoad產(chǎn)生影響，對于MCSnum值是否會有影響，則取決于算法是否將節(jié)點通信質(zhì)量考慮進算法處理。將兩種因素均進行處理的SelCDS算法在各種最大丟包率條件下效果均較好；另一方面，隨著網(wǎng)絡(luò)節(jié)點最大丟包率增大，各算法NetComLoad值均呈增大趨勢。在最大丟包率取值較大(高于65%)時，SelCDS算法性能指標更優(yōu)，表明在網(wǎng)絡(luò)節(jié)點鏈路可能出現(xiàn)高丟包率的突發(fā)誤包條件下，采用SelCDS算法將更具優(yōu)勢。

4 結(jié) 論

本文考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法，將節(jié)點通信質(zhì)量納入網(wǎng)絡(luò)最小主控集構(gòu)造考慮因素。仿真對比表明，在節(jié)點數(shù)n=80、通信半徑22 km、最大丟包率0.32條件下,SelMCS算法NetComLoad=65,MCSnum=25個，均優(yōu)于QDBA、MPR算法。因此，本算法對于通信質(zhì)量敏感的應(yīng)用，如應(yīng)急救災(zāi)分布式通信網(wǎng)、戰(zhàn)術(shù)應(yīng)用自組織網(wǎng)等，將更有助于獲得高效、穩(wěn)定的虛擬骨干網(wǎng)，從而便于網(wǎng)絡(luò)運行維護,取得更好的通信效果。

[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

劉邈.考慮通信質(zhì)量的網(wǎng)絡(luò)最小主控集生成算法[J].電訊技術(shù)，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年于電子科技大學獲碩士學位,現(xiàn)為工程師，主要從事通信系統(tǒng)及網(wǎng)絡(luò)設(shè)計。

Email：liumiao_nj@163.com

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