劉 邈

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

?

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

劉 邈**

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

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

無(wú)人移動(dòng)平臺(tái)；無(wú)線自組織網(wǎng)；通信質(zhì)量;最小主控集;網(wǎng)絡(luò)拓?fù)?/p>

1 引 言

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

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

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

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

2.1 算法基本思路

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

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

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

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

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

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

網(wǎng)絡(luò)拓?fù)涞湫蛨?chǎng)景如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)涞牡湫颓闆r示意

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

2.2 算法描述

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

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

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

(1)

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

(2)

(3)

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

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

Step 2 針對(duì)節(jié)點(diǎn)y，壓縮其CandiNodes和IntendCov。

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

Step 2-2 考察NeiNodes2(y)中是否存在節(jié)點(diǎn)w，使w滿足w∈NLMCS(x)；NodeComQua(w)

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

Step 3 針對(duì)節(jié)點(diǎn)y，選擇其下級(jí)單路徑節(jié)點(diǎn)。

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

Step 3-2 若存在節(jié)點(diǎn)w∈IntendCov(y)，使CandiNodes(y)中僅有一個(gè)節(jié)點(diǎn)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}，且對(duì)于當(dāng)前所有的CovCapa(i)∈SumCapa(y)均有CovCapa(i)=CovCapa(i)-CovCapa(o)。

Step 3-4 重復(fù)Step 3-2～Step 3-3，直至IntendCov(y)中不存在符合條件的節(jié)點(diǎn)w。此時(shí)，判斷IntCovReg(y)是否等于IntendCov(y)，若等于則對(duì)節(jié)點(diǎn)y尋找其下級(jí)主控節(jié)點(diǎn)的過(guò)程結(jié)束；否則，繼續(xù)執(zhí)行算法Step 4。

Step 4 針對(duì)節(jié)點(diǎn)y，選擇其下級(jí)多路徑節(jié)點(diǎn)。

Step 4-1 在SumCapa(y)中搜索仍有效的CovCapa(q)，使得該CovCapa(q)其節(jié)點(diǎn)q的NodeComQua(q)最優(yōu)，即NodeComQua(q)=min{NodeComQua(i)/i為SumCapa(y)中仍有效的CovCapa(i)對(duì)應(yīng)的節(jié)點(diǎn)i。找到滿足條件的節(jié)點(diǎn)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}，且對(duì)于當(dāng)前所有的CovCapa(i)∈SumCapa(y)均有CovCapa(i)=CovCapa(i)-CovCapa(q)。

Step 4-3 判斷IntCovReg(y)是否等于IntendCov(y)，若等于，則對(duì)節(jié)點(diǎn)y搜索其下級(jí)主控節(jié)點(diǎn)的過(guò)程結(jié)束；若不等于，則重復(fù)Step 4-1～Step 4-2，直至等于為止。

3 算法性能仿真

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

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

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

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

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

由圖2可以看出：

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

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

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

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

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

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

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

由圖3可以看出：

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

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

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

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

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

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

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

由圖4可以看出：

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

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

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

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

4 結(jié) 論

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

[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年于電子科技大學(xué)獲碩士學(xué)位,現(xiàn)為工程師，主要從事通信系統(tǒng)及網(wǎng)絡(luò)設(shè)計(jì)。

Email：liumiao_nj@163.com

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