羅錦暉，劉春顏，王越濤，李洋，趙蘊(yùn)龍

南京航空航天大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106

無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor network,WSN)因?yàn)槠涑杀镜?、易部署、使用方便等特性被廣泛應(yīng)用于環(huán)境監(jiān)測(cè)、健康應(yīng)用、災(zāi)難救援、戰(zhàn)場(chǎng)監(jiān)控、交通控制、移動(dòng)計(jì)算以及軍事行動(dòng)等各場(chǎng)景中。在大規(guī)模無(wú)線傳感器部署過(guò)程中，特別是野外環(huán)境監(jiān)測(cè)場(chǎng)景，無(wú)線傳感器常被大量且隨機(jī)地投擲在覆蓋區(qū)域內(nèi)，由此構(gòu)建的無(wú)線傳感器網(wǎng)絡(luò)在信息收集與傳輸過(guò)程中極易造成擁塞、骨干節(jié)點(diǎn)過(guò)度消耗、網(wǎng)絡(luò)拓?fù)洳环€(wěn)定、網(wǎng)絡(luò)生命周期短等問(wèn)題。為解決以上問(wèn)題，常采取分層分簇路由和虛擬骨干路由等策略來(lái)引導(dǎo)信息定向傳輸。其中虛擬骨干網(wǎng)技術(shù)由Ephremides 等[1]于1987 年提出，并得到學(xué)術(shù)界廣泛支持和采用。在虛擬骨干網(wǎng)中，每個(gè)節(jié)點(diǎn)將消息發(fā)送到臨近虛擬骨干網(wǎng)中的骨干節(jié)點(diǎn)，信息沿這些骨干節(jié)點(diǎn)組成的虛擬路由網(wǎng)轉(zhuǎn)發(fā)至其目的節(jié)點(diǎn)。因此，當(dāng)路由路徑搜索空間被限制在虛擬骨干網(wǎng)中，可以得到更短的路由路徑搜索時(shí)間、更小的路由表以及更便捷的路由維護(hù)，從而大大提高無(wú)線傳感器網(wǎng)絡(luò)轉(zhuǎn)發(fā)效率，延長(zhǎng)網(wǎng)絡(luò)生命周期。

在虛擬骨干網(wǎng)絡(luò)中，通常以平均骨干路徑長(zhǎng)度(the average backbone path length，ABPL)[2]來(lái)衡量網(wǎng)絡(luò)中節(jié)點(diǎn)間傳輸路徑的長(zhǎng)度，間接反映網(wǎng)絡(luò)中信息傳輸?shù)某杀净蚰芎?。無(wú)線傳感器網(wǎng)絡(luò)中虛擬骨干網(wǎng)構(gòu)建問(wèn)題已轉(zhuǎn)化為圖論中的連通控制集(connected dominating set，CDS)問(wèn)題，學(xué)者們針對(duì)路由約束、最小權(quán)重、錯(cuò)誤容忍等特性的虛擬骨干網(wǎng)開展研究，設(shè)計(jì)了一系列可推導(dǎo)、可驗(yàn)證的近似算法，為通過(guò)連通控制集構(gòu)建特定約束下的極小虛擬骨干網(wǎng)提供了理論方法。

在一些特定無(wú)線傳感器網(wǎng)絡(luò)中，因?yàn)楣?jié)點(diǎn)的移動(dòng)、失效等原因?qū)е戮W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不穩(wěn)定，因此需要構(gòu)建具有容錯(cuò)性的虛擬骨干網(wǎng)。在圖論中此問(wèn)題可通過(guò)以k-連通m-控制集算法構(gòu)建連通控制集的方法來(lái)解決，即要求虛擬骨干網(wǎng)C以外的任一點(diǎn)都至少被C中m個(gè)點(diǎn)所控制，而C導(dǎo)出的子圖的連通度至少為k。采用(k,m)-CDS 作為虛擬骨干，即使min{k-1，m-1}個(gè)節(jié)點(diǎn)發(fā)生故障，虛擬骨干仍能正常工作。

本文提出同時(shí)考慮網(wǎng)絡(luò)容錯(cuò)性和平均路由長(zhǎng)度的虛擬骨干網(wǎng)構(gòu)建問(wèn)題，并將該問(wèn)題轉(zhuǎn)化為（1，m）-α路由約束的最小連通控制集(minimum connected dominating set, MCDS)問(wèn)題，同時(shí)給出時(shí)間復(fù)雜度為O(n3)的構(gòu)建算法，最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證其有效性。

1 國(guó)內(nèi)外研究現(xiàn)狀

1.1 考慮路徑長(zhǎng)度的連通控制集

在虛擬骨干網(wǎng)絡(luò)中，骨干節(jié)點(diǎn)越少，整個(gè)網(wǎng)絡(luò)的架設(shè)成本也越低，同時(shí)也能保證較高的通信效率。因此學(xué)者們從大量節(jié)點(diǎn)中選擇MCDS 組成骨干網(wǎng)絡(luò)，構(gòu)造MCDS 是一個(gè)非確定性多項(xiàng)式(non-deterministic polynomial， NP)完全問(wèn)題[3]。2005 年Mohammed 等[4]首次提出了以直徑和為附加因子生成控制集的算法，實(shí)驗(yàn)結(jié)果表明，該算法在不增加解的規(guī)模的情況下，可以生成直徑較小的控制集。2007 年Li 等[5]開始研究無(wú)線網(wǎng)絡(luò)中直徑有界的虛擬骨干網(wǎng)構(gòu)造問(wèn)題，并提出了一種啟發(fā)式算法，該算法的時(shí)間復(fù)雜度為O(n2)。Kim 等[6]改進(jìn)自己的原有算法，提出一個(gè)分布式CDS 構(gòu)造算法，使近似比減少到6.906。

2010 年，Ding 等[7]發(fā)現(xiàn)在之前的研究中只是意識(shí)到路由路徑長(zhǎng)度的重要性，沒(méi)有考慮最小路由約束(minimum routing cost，MOC)，不能保證通過(guò)其CDS 的路由路徑是原始網(wǎng)絡(luò)的最短路徑。在文獻(xiàn)[7]中提出了MOC-CDS，MOC-CDS 路由可以保證任意一對(duì)節(jié)點(diǎn)之間的每一條路由路徑也是網(wǎng)絡(luò)中的最短路徑，所以可以大大降低能耗和延遲，該算法的近似比為(1-ln2)+2lnδ，δ為網(wǎng)絡(luò)中的最大節(jié)點(diǎn)度。數(shù)值實(shí)驗(yàn)顯示MOC-CDS 的尺寸非常大，為了平衡虛擬骨干的尺寸和路由成本，Du 等[8-10]又提出了α倍路由約束問(wèn)題(αMOCCDS)。對(duì)于α≥5，他們給出了單位圓盤圖中αMOC-CDS 的常數(shù)近似算法。該算法首先以貪婪的方式構(gòu)造圖G（V，E）的極大獨(dú)立集I，然后把集合I中的元素都放入集合D。對(duì)于每一對(duì)屬于I的節(jié)點(diǎn)u,v，若它們滿足其經(jīng)過(guò)D的路徑長(zhǎng)度dD(u,v)≤4，那么找到它們之間的一條最短路徑，并把該路徑上的所有點(diǎn)放入D中，最終得到|D|≤121|I|。Liu 等[11]針對(duì)各節(jié)點(diǎn)傳輸半徑不同的異構(gòu)網(wǎng)絡(luò)提出了α-MOC-強(qiáng)聯(lián)通雙向控制集（ strongly connected bidirectional dominating set，

SCBDS）問(wèn)題，并給出了近似比為(3(8ρ+1)2(2ρ+1)2/2)Mopt（1,m）的近似算法，其中ρ為最大與最小傳輸半徑之比，Mopt（1,m）為二維空間下最小m重連通控制集問(wèn)題的最優(yōu)解。Putwattana 等[12]改進(jìn)了Liu 的算法，驗(yàn)證了對(duì)于任意在I中并且d(u,v)≤3 的一對(duì)點(diǎn)u,v，計(jì)算出連通u,v的最短路徑，并把最短路徑的中間節(jié)點(diǎn)全部放入C集合中，α倍路由約束連通控制集D=C∪I，D的導(dǎo)出子圖是連通的，同時(shí)滿足dD(u，v)≤5d(u，v)。改進(jìn)過(guò)后的α-MOCSCBDS 近似比為2(6ρ+1)2(2ρ+1)2。

1.2 考慮容錯(cuò)性的連通控制集

Dai 等[13]最先提出將k-連通m-控制集問(wèn)題引入容錯(cuò)性虛擬骨干網(wǎng)的研究中。他們提出了最小(k，m)-CDS 的3 種啟發(fā)式算法。但是生成的連通控制集的大小沒(méi)有給出上限。Wu 等[14]提出了一個(gè)構(gòu)造k-連通m-控制集的分布式算法，這個(gè)算法的優(yōu)點(diǎn)就在于它的信息開銷很低。THAI 等[15]研究了k-連通m-控制集并且首次提出了1-連通m-控制集和k-連通k-控制集的近似算法?；谶@2 個(gè)算法，提出了對(duì)于k-連通m-控制集的一般算法。Wang 等[16]提出了增強(qiáng)連通控制集(connecting dominating set augmentation，CDSA)，構(gòu)造一個(gè)能夠克服無(wú)線節(jié)點(diǎn)故障的2-連通CDS。其主要思想是首先構(gòu)造一個(gè)連通控制集，然后通過(guò)在主干中添加新的節(jié)點(diǎn)將其擴(kuò)充為2-連通，通過(guò)證明CDSA 具有72 的恒定近似比， 從而保證了CDSA 的質(zhì)量。Shang 等[17]指出考慮容錯(cuò)的虛擬骨干網(wǎng)中，利用單位圓盤圖和一個(gè)較小的m(m≤2)，迭代地選取m個(gè)極大獨(dú)立集，它們的并集構(gòu)成一個(gè)m-控制集，同時(shí)也給出了(1，m)-CDS 的常數(shù)近似比，并討論了如何設(shè)計(jì)具有任意大m問(wèn)題的近似算法。Kim 等[18]得到了單位圓盤圖中最小(3，m)-CDS 問(wèn)題的常數(shù)近似算法，但該算法非常復(fù)雜，近似比也很大，如(3，3)-CDS 的近似比為280。Wang 等[19]擴(kuò)展了文獻(xiàn)[17]中容錯(cuò)虛擬骨干網(wǎng)的研究，運(yùn)用2-連通但非3-連通圖的Tutte-分解簡(jiǎn)化了該算法，并改進(jìn)了近似比到5α，特別當(dāng)k=m=3 時(shí)，近似比可以降到62.3，其中α為(2,m)-CDS 的近似比。Shi 等[20]提出基于單位圓盤圖上最小節(jié)點(diǎn)加權(quán)Steiner 網(wǎng)絡(luò)問(wèn)題的常數(shù)近似算法，這個(gè)算法是k-連通m-控制集的虛擬骨干網(wǎng)，其中k和m為m≥k的2 個(gè)固定常數(shù)，得到(k，m)-CDS 問(wèn)題常數(shù)近似比。當(dāng)k≥3 時(shí)，該近似比為(α+5ρ)；當(dāng)k=2 時(shí)，該近似比為(α+2.5ρ)，其中α為最小m控制-CDS 的近似比，ρ為最小k-連通CDS 的近似比。Zhou 等[21]把容錯(cuò)性和異構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)同時(shí)考慮進(jìn)去，提出了異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)(3，m)-CDS 的近似算法。文中性能比最大為γ，其中α≥4 時(shí)，γ=α+8+2ln(2α-6)；α＜4 時(shí)，γ=3α+2ln2，α是極小(2，m)-CDS 問(wèn)題的近似比。如果將算法應(yīng)用到單位圓盤圖上，則近似比將小于27。

2 問(wèn)題描述

利用圖G=(V，E)描述網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，V為網(wǎng)絡(luò)中所有節(jié)點(diǎn)，E為網(wǎng)絡(luò)中的所有邊。假設(shè)C為V的一個(gè)子集，如果含有V/C中的每個(gè)頂點(diǎn)都在C中有鄰點(diǎn)，則子集C稱為控制集。如果由C導(dǎo)出的子圖GC是連通的，則稱C為連通控制集。為了進(jìn)一步解決傳感器網(wǎng)絡(luò)中由于網(wǎng)絡(luò)節(jié)點(diǎn)失效等原因?qū)е碌木W(wǎng)絡(luò)拓?fù)洳环€(wěn)定問(wèn)題，使用圖論中k-連通m-控制集解決網(wǎng)絡(luò)的容錯(cuò)性問(wèn)題；同時(shí)通常使用α倍路由約束來(lái)體現(xiàn)虛擬骨干網(wǎng)的高效。為此本文給出以下定義。

定義1k-連通m-控制集：給定圖G=(V,E)中的1 個(gè)連通控制集D是k-連通m-控制的，當(dāng)且僅當(dāng)任意大小不超過(guò)k-1 的子集D′?D使得GD-D′仍然是連通的，同時(shí)存在1 個(gè)連通控制集D是G的m控制集，當(dāng)且僅當(dāng)對(duì)于任意的節(jié)點(diǎn)u∈VD，則u在D中至少存在m個(gè)鄰居。

定義2最小路由約束連通控制集：MOCCDS 是尋找一個(gè)最小的點(diǎn)集合D?V，這個(gè)集合D有以下特性：

1)?u∈VD，?v∈D，使(u, v)∈E。

2) 導(dǎo)出子圖GD是連通的。

3) ?u,v∈V， 若Dist(u, v)＞1， 那么?pi(u,v)∈Pi(u,-v),pi(u,v){u,v}?D。其中pi(u, v)={u,w1,w2,···,wk,v}，表示點(diǎn)u, v之間第i條最短路徑；Dist(u,v)表示點(diǎn)u, v間的最短路徑跳數(shù)；Pi(u, v)表示u,v間所有的最短路徑。

定義3α倍路由約束連通控制集：αMOCCDS 為點(diǎn)集合D?V，這個(gè)集合D有以下特性：

1) ?u∈VD，?v∈D，使(u, v)∈E。

2) 導(dǎo)出子圖GD是連通的。

3) ?u,v∈V，若Dist(u, v)＞1，那么pD(u, v)上的所有中間節(jié)點(diǎn)都屬于D并且dD(u, v)≤αd(u,v)。其中pD(u, v)表示u, v間在D上的最短路徑；P(u,v)表示u, v間的最短路徑；dD(u, v)和d(u, v)分別表示pD(u, v)和P(u, v)上中間節(jié)點(diǎn)的數(shù)量。

定義4考慮容錯(cuò)性的α倍路由約束問(wèn)題(1,m)-αMOC-CDS：給定1 個(gè)單位圓盤圖G=(V,E)，子集S被稱為G的1 個(gè)考慮容錯(cuò)性α-路由約束的連通控制集，則S必須滿足以下4 個(gè)個(gè)條件：

1）S是G的1 個(gè)控制集。

2）由S導(dǎo)出的子圖GS是連通的，即GS中的任意2 點(diǎn)之間都至少存在1 條路徑，使得2 點(diǎn)之間可以相互傳輸信息。

3）對(duì)于給定的常數(shù)α≥1，任意u, v點(diǎn)都滿足dD(u, v)≤αd(u, v)。

4）G中所有非骨干節(jié)點(diǎn)都至少被m個(gè)骨干節(jié)點(diǎn)所支配。

3 算法與理論分析

3.1 理論分析

尋找最小路由約束連通控制集的問(wèn)題已經(jīng)被證明是NP 難問(wèn)題，部分文獻(xiàn)提出了通過(guò)尋找MOC-CDS 的近似算法來(lái)解決這個(gè)問(wèn)題。這些近似算法一般分為2 個(gè)階段：第1 階段構(gòu)造一個(gè)極大獨(dú)立集；在第2 階段，添加其他節(jié)點(diǎn)作為連接節(jié)點(diǎn)連通極大獨(dú)立集來(lái)構(gòu)成一個(gè)完整的最小路由約束連通控制集。引理1～3 將為算法第2 階段提供理論支撐。

引理1G為一個(gè)連通的圖，D為G的一個(gè)連通控制集。d(u, v)為圖G中u, v這2 點(diǎn)的最短路長(zhǎng)度，dD(u, v)為連接u, v這2 點(diǎn)的中間節(jié)點(diǎn)全在D中的最短路長(zhǎng)度。假設(shè)任意滿足d(u, v)=2 的一對(duì)節(jié)點(diǎn)u, v都有dD(u, v)-1≤α，那么dD(u, v)-1≤α(d(u, v)-1)。

引理2G為一個(gè)連通的圖，D為G的一個(gè)連通控制集。假設(shè)任意滿足d(u, v)=2 的一對(duì)節(jié)點(diǎn)u,v都有dD(u, v)-1≤α，那么dD(u,v)≤αd(u,v)。

證明：根據(jù)引理1，

引理3[8]I為圖G的一個(gè)極大獨(dú)立集，D為包含I的一個(gè)連通控制集。假設(shè)對(duì)任意滿足d(u,v)≤4 且u,v都在I中的一對(duì)節(jié)點(diǎn)u,v，都有dD(u,v)≤4，那么dD(u,v)≤5d(u,v)。

Du 等[8]證明了引理1～3。根據(jù)這3 個(gè)引理，可以得知在無(wú)向圖G中，求出G的控制集C后，將C中的所有節(jié)點(diǎn)放入D中。若任意一對(duì)節(jié)點(diǎn)u,v∈D并且d(u,v)＜4，把u和v之間最短路徑的所有節(jié)點(diǎn)都加到D上，可以得到dD(u,v)≤5d(u,v)。Putwattana 等[12]對(duì)異構(gòu)網(wǎng)絡(luò)中的路由約束提出了改進(jìn)。受此改進(jìn)的啟發(fā)，我們可以考慮無(wú)向圖G和G的控制集C，如果任意一對(duì)節(jié)點(diǎn)u, v∈D和d(u,v)＜3，把u和v之間最短路徑的所有節(jié)點(diǎn)都加到D上，同樣可以得到dD(u,v)≤5d(u,v)，理論分析過(guò)程如引理4。

引理 4I為由第1 階段構(gòu)造的極大獨(dú)立集，D為包含I的1 個(gè)連通控制集，如果對(duì)于每一對(duì)屬于I的節(jié)點(diǎn)u,v，若滿足dD(u,v)≤3，那么找到它們之間的一條最短路徑，并把該路徑上的所有點(diǎn)放入S中，它們的誘導(dǎo)子圖GS是連通的，并且對(duì)于圖中任意一對(duì)節(jié)點(diǎn)u,v，都滿足dD(u,v)≤5d(u,v)。

證明：考慮V中一對(duì)節(jié)點(diǎn)u,v，它們?cè)趫DG中的最短路徑為k，假設(shè)這條路徑為(u=w0,w1,· ··,wk-1,v=wk)(如圖1 所示)，已知GS是連通的，對(duì)該路徑中每一對(duì)相鄰的wi和wi+1：

圖1 連接u, v 的最短路徑

1）若wi和wi+1其中一個(gè)是I中的節(jié)點(diǎn)，不失一般性假設(shè)wi不是I中的節(jié)點(diǎn)，那么在原圖G中Ddom(wi)domD(wi)和wi之間必有1 條只經(jīng)過(guò)D中的點(diǎn)同時(shí)小于等于3 的路徑。（Ddom(wi)為I中支配wi的節(jié)點(diǎn)）。

2）若wi和wi+1都不是I中的節(jié)點(diǎn)，那么存在Ddom(wi)和Ddom(wi+1)分別支配w1和w2。 無(wú)論Ddom(wi)和Ddom(wi+1)是否為同一個(gè)點(diǎn)，均有圖G中Ddom(wi)和Ddom(wi+1)之間必有1 條只經(jīng)過(guò)D中的點(diǎn)同時(shí)小于等于3 的路徑。又因?yàn)橛梢阎獥l件可得原圖G中存在1 條長(zhǎng)度為3 的路徑(Ddom(wi),wi,wi+1,Ddom(wi+1))。那么可以得出：

式中：k≥1，Ddom(u)為集合C中控制u的的點(diǎn)。

3.2 算法設(shè)計(jì)與分析

本節(jié)設(shè)計(jì)一個(gè)3 階段算法(1,m)-αMOCCDS 構(gòu)建基于最小權(quán)重連通控制集的α倍路由約束虛擬骨干網(wǎng)，該算法是一種基于極大獨(dú)立集的連通控制集構(gòu)建方法，算法過(guò)程簡(jiǎn)述如下。

第1 階段：構(gòu)建極大獨(dú)立集I1作為骨干節(jié)點(diǎn)。

第2 階段：以動(dòng)態(tài)規(guī)劃思想連接I1中的節(jié)點(diǎn)構(gòu)建連通控制集。

第3 階段：通過(guò)一個(gè)迭代算法構(gòu)建m-控制集。不斷求解普通節(jié)點(diǎn)集中的極大獨(dú)立集Im，并加入第2 階段所求的連通控制集中，通過(guò)m-1 次迭代，確保網(wǎng)絡(luò)中任意一個(gè)普通節(jié)點(diǎn)都被至少m個(gè)骨干節(jié)點(diǎn)所控制。

算法1構(gòu)建αMOC-CDS。引用文獻(xiàn)[8]中的Algorithm 2 作為第1 階段構(gòu)造極大獨(dú)立集（maximum independent set, MIS）的算法1，該算法貪婪地尋找節(jié)點(diǎn)間度最小的節(jié)點(diǎn)作為骨干節(jié)點(diǎn)，最終構(gòu)成一個(gè)極大獨(dú)立集。

算法2構(gòu)建連通集合C。 對(duì)控制集(dominating set, DS)中任意一對(duì)滿足d(u,v)≤3的節(jié)點(diǎn)u, v，求出u, v間在圖G中的最短路徑，并把路徑中的點(diǎn)都加入集合C中，算法如下。

輸入：一個(gè)連通單位圓盤圖G= (V,E)，求出圖G的極大獨(dú)立集I

輸出：連通集合C

NodeNumber←|V|

D←I←Construct-MIS(G,V,NodeNumber)

W[v] ←0 for allv∈I

W[v] ←1 for allv∈VI

for allu∈I

w[u][L] ←∞, for allu∈Vand 0 ≤L≤2

w[u][0] ←0

p[u][0] ←?

Used←{u}

forL= 0 to 2 do

newUsed←?

for allv∈ Used do

for allx∈ Neighbor[v] do

ifw[v][L]+W[x] ＜w[x][L+1]

w[v][L+1]←w[v][L]+W[x]

p[x][L+1] ←v

newUsed←newUs∪{x}

end if

end for

end for

Used←newUsed

end for

for allv∈Isuch thatd(u,v) ≤ 3 do

ifw[v][l] is minimum inw[v][L] then

Path←Path ∪p[v][l]

end if

end for

C←C∪ Path

W[v]←0 for allv∈C

end for

引理5[13]無(wú)向圖G=(V，E)是一個(gè)單位圓盤圖，m是一個(gè)自然數(shù)并且δ(G)≥m-1，使Dm*為圖G的最?。?，m）-CDS，S為圖G的一個(gè)MIS，那么可以得到

具體證明過(guò)程在文獻(xiàn)[17]中給出。

算法3構(gòu)建基于(1,m)-連通控制集的α倍路由約束虛擬骨干網(wǎng)構(gòu)建算法。該算法的基本思想是首先使用算法1 和算法2 中提出的方法生成αMOC-CDS，然后依次使用算法1 產(chǎn)生一個(gè)(m-1)個(gè)MIS，使得每個(gè)非骨干節(jié)點(diǎn)都由m個(gè)以上骨干節(jié)點(diǎn)中的頂點(diǎn)控制，算法如下。

輸入：一個(gè)連通單位圓盤圖G=(V,E)

輸出：基于(1,m)-連通控制集的α倍路由約束虛擬骨干網(wǎng)D

NodeNumber←|V|

I1←Construct-MIS(G,V,NodeNumber)

C←Construct Connected Set (G,I1)

S1←VI1

D←I1∪C

fori=2 tomdo

Ii← Construct-MIS(G,Si-1, NodeNumber)

Si←Si-1Ii

D←D∪Ii

end for

returnD

3.3 算法近似比分析

引理6若I為極大獨(dú)立集，那么對(duì)于任意u∈I，|{v∈I|0 ＜d(u,v)≤3}|≤48。

證明：對(duì)于每個(gè)節(jié)點(diǎn)v∈I，且d(u,v)≤3，構(gòu)建中心為v、半徑為0.5 的圓盤，再構(gòu)建一個(gè)中心為u、半徑為3.5 的大圓盤，在這個(gè)大圓盤中能容納的互不相交的半徑為0.5 的圓盤數(shù)量，即為

因?yàn)閡點(diǎn)也在其中，所以

引理7由第2 階段構(gòu)成連通集合具有以下性質(zhì)|C|≤48|I|，其中I是第1 階段構(gòu)建的極大獨(dú)立集。

證明：構(gòu)造一個(gè)圖G，它的節(jié)點(diǎn)集為I，邊集為{(u, v)|u, v∈I，0＜d(u, v)≤3}。根據(jù)引理5 可知，G中節(jié)點(diǎn)最大的度為48，所以G包含最多24 |I|條邊。第2 階段中，因?yàn)閐(u, v)≤3，每對(duì)極大獨(dú)立集節(jié)點(diǎn)對(duì)之間最多加2 個(gè)點(diǎn)，所以|C′|≤2×24|I|=48|I|。

引理8通過(guò)算法3 構(gòu)成的（1，m）-αMOCCDS 中， 當(dāng)m≤5時(shí)，當(dāng)m＞5時(shí)其中為1 個(gè)圖G的最小(1,m)-CDS。

繼而可以推出

引理9算法3 中構(gòu)造的(1，m)-αMOCCDS 構(gòu)建的連通控制集D的上界大小如下：當(dāng)m≤5時(shí)，為(240/m+5)Mopt（1,m），其中Mopt（1,m）指極小(1，m)-CDS 的最優(yōu)解；m＞5時(shí)，為54Mopt（1,m）。同時(shí)對(duì)于任意一對(duì)節(jié)點(diǎn)u,v，都有dD(u,v)≤5d(u,v)。

證明：根據(jù)引理7、引理8 可知：當(dāng)m≤5時(shí)，當(dāng)m＞5時(shí)，

根據(jù)引理4 可知，在D中，任意一對(duì)節(jié)點(diǎn)u,v都有dD(u,v)≤5d(u,v)，同時(shí)每個(gè)非骨干節(jié)點(diǎn)都被m個(gè)以上的骨干節(jié)點(diǎn)支配。

4 仿真結(jié)果與分析

本節(jié)主要介紹了(1，m)-αMOC-CDS 的仿真實(shí)驗(yàn)結(jié)果以及與相關(guān)算法的對(duì)比分析。

4.1 實(shí)驗(yàn)環(huán)境

4.1.1 計(jì)算機(jī)平臺(tái)性能

處理器：AMD Ryzen 5 3500X 6-Core Processor，4.00 GHz；RAM，16.0 GB；系統(tǒng)類型：64 位操作系統(tǒng)，基于x64 的處理器；編程IDE：MATLAB。

4.1.2 無(wú)線傳感器網(wǎng)絡(luò)參數(shù)

在仿真中，具有不同傳輸范圍的無(wú)線傳感器網(wǎng)絡(luò)的參數(shù)設(shè)置如下。傳感器由一組隨機(jī)部署在以100×100 為邊界的歐幾里得平面上的節(jié)點(diǎn)來(lái)模擬，節(jié)點(diǎn)總數(shù)分別為100、200、300、400 個(gè)，傳輸半徑分別為15、20 和25，針對(duì)每組參數(shù)構(gòu)造100個(gè)隨機(jī)圖，每個(gè)隨機(jī)圖進(jìn)行100 次實(shí)驗(yàn)取平均值。

4.2 對(duì)比算法

目前只有分別考慮容錯(cuò)性的(k,m)-連通控制集問(wèn)題和α倍路由約束連通控制集問(wèn)題的解決方案，沒(méi)有同時(shí)考慮容錯(cuò)性和α倍路由約束問(wèn)題解決方案。仿真實(shí)驗(yàn)在參數(shù)m=1、2、3 時(shí)，分別用(1,m)-MOC-CDS 算法在隨機(jī)網(wǎng)絡(luò)圖中構(gòu)建虛擬骨干網(wǎng)，并進(jìn)行多次試驗(yàn)分別統(tǒng)計(jì)MOC-CDS、(1,2)-αMOC-CDS 和(1, 3)-MOC-CDS的規(guī)模大小。其中當(dāng)m=1 時(shí)，(1, 1)-MOC-CDS 就是一個(gè)普通的αMOC-CDS。

4.3 仿真結(jié)果

最后利用不同傳輸半徑CDS 的大小比較仿真結(jié)果。傳輸半徑為15 情況下的仿真結(jié)果如圖2 所示，傳輸半徑為20 情況下的仿真結(jié)果的描述如圖3 所示，傳輸半徑為25 情況下的仿真結(jié)果如圖4 所示。

圖2 傳輸距離為15 時(shí)3 種算法CDS 大小

圖3 傳輸距離為20 時(shí)3 種算法CDS 的大小

圖4 傳輸距離為25 時(shí)3 種算法CDS 大小

4.4 仿真結(jié)果比較分析

圖2～圖4 給出了MOC-CDS、(1,2)-MOC-CDS和(1,3)-MOC-CDS 算法生成的CDS 大小的仿真結(jié)果，由這3 個(gè)圖中可以看到，隨著傳感器節(jié)點(diǎn)的總數(shù)量從100 個(gè)增加到400 個(gè)，每個(gè)算法生成的CDS 的平均大小略有增加，這是合理的。因?yàn)樗械乃惴ǘ夹枰谧疃搪窂缴嫌懈嗟闹虚g節(jié)點(diǎn)連接更多的控制節(jié)點(diǎn)來(lái)構(gòu)建CDS。同時(shí)隨著傳感器節(jié)點(diǎn)的總數(shù)量從100 個(gè)增加到400 個(gè)，3 種算法骨干節(jié)點(diǎn)增長(zhǎng)速度在降低，這也是合理的。因?yàn)楫嫴伎偞笮〔蛔兊那闆r下，隨著節(jié)點(diǎn)個(gè)數(shù)的增加，整個(gè)傳感器網(wǎng)絡(luò)變得十分稠密，執(zhí)行算法1 和算法2 所需要增加的節(jié)點(diǎn)變少，骨干網(wǎng)節(jié)點(diǎn)數(shù)隨著網(wǎng)絡(luò)變得稠密逐漸趨于飽和。此外，我們還可以看到由算法MOC-CDS 生成的CDS 的平均大小受到引理8 近似比的限制。通過(guò)對(duì)比實(shí)驗(yàn)可以得出，在傳輸半徑為15、20 和25 時(shí)，構(gòu)建(1,2)-MOC-CDS和(1,3)-MOC-CDS 所需要增加的CDS 大小不超過(guò)15%和30%，這是一個(gè)可以接受的范圍，驗(yàn)證了(1,m)-MOC-CDS 算法的可行性。

綜上所述，(1,m)-MOC-CDS 算法有效地解決了考慮容錯(cuò)性的α倍路由約束問(wèn)題，在滿足了α倍路由約束(α≥5)的情況下，充分考慮了整個(gè)網(wǎng)路的容錯(cuò)性問(wèn)題。通過(guò)實(shí)驗(yàn)可以驗(yàn)證(1,m)-αMOC-CDS 的有效性，同時(shí)由引理3 證明可得，對(duì)于任意一對(duì)節(jié)點(diǎn)u,v都有dD(u, v)≤5d(u, v)。

5 結(jié)束語(yǔ)

本文研究了無(wú)線傳感器網(wǎng)絡(luò)中具有容錯(cuò)的虛擬骨干網(wǎng)構(gòu)建算法，該算法同時(shí)考慮容錯(cuò)性和路由約束兩方面約束。

關(guān)于如何有效延長(zhǎng)網(wǎng)絡(luò)生命周期問(wèn)題，還有一種方法是動(dòng)態(tài)更新骨干節(jié)點(diǎn)，形成輪換來(lái)實(shí)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)的負(fù)載均衡，從而延長(zhǎng)網(wǎng)絡(luò)生命周期。這種動(dòng)態(tài)更新虛擬骨干節(jié)點(diǎn)方法的正確性和有效性有待進(jìn)一步研究和驗(yàn)證。關(guān)于網(wǎng)絡(luò)魯棒性問(wèn)題，可使用基于k-連通m-控制集和α 倍路由約束的方法構(gòu)建虛擬骨干網(wǎng)，通過(guò)雙重約束來(lái)保證虛擬骨干網(wǎng)的魯棒性，其近似比和虛擬骨干網(wǎng)性能有待進(jìn)一步研究和論證。