吳 儀，秦寧寧，2*

(1.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫214122；2.南京航空航天大學(xué)電磁頻譜空間認(rèn)知?jiǎng)討B(tài)系統(tǒng)工信部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京211106)

隨機(jī)部署的異構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)雖能節(jié)約人力，但會(huì)造成傳感器分布不均與網(wǎng)絡(luò)空洞繁多等通信覆蓋問(wèn)題，同時(shí)節(jié)點(diǎn)間的異構(gòu)屬性使網(wǎng)絡(luò)拓?fù)涓鼮閺?fù)雜。所以利用節(jié)點(diǎn)間位置信息探測(cè)出空洞，并使用節(jié)點(diǎn)移動(dòng)的方式對(duì)空洞進(jìn)行相應(yīng)的修復(fù)，成為高成本的二次部署之外的一種有效優(yōu)化網(wǎng)絡(luò)覆蓋的方案。

集中式算法廣泛用于解決傳感器網(wǎng)絡(luò)的探測(cè)與空洞修補(bǔ)，通過(guò)平臺(tái)或核心節(jié)點(diǎn)收集到所有傳感器節(jié)點(diǎn)的位置等信息，統(tǒng)一計(jì)算勾勒全局空洞，并指引節(jié)點(diǎn)調(diào)整位置優(yōu)化拓?fù)?。該模式精確度較高，偏差較小，但更依賴(lài)網(wǎng)絡(luò)全局信息。為探測(cè)空洞，文獻(xiàn)[1]利用Voronoi圖對(duì)網(wǎng)絡(luò)進(jìn)行劃分，并使用虛擬邊緣膨脹方法探測(cè)空洞；Li[2]通過(guò)判斷Delaunay剖分的三角形外心是否被三個(gè)節(jié)點(diǎn)所覆蓋，來(lái)確定空洞存在與否；穆天圓[3]利用泰森多邊形的大小指導(dǎo)蜂群算法中引領(lǐng)蜂的生成，以迅速定位全局空洞。在修補(bǔ)空洞的研究中，文獻(xiàn)[4]結(jié)合Voronoi與Delaunay，建立盲區(qū)與待修復(fù)位置的匹配模型以實(shí)現(xiàn)空洞修補(bǔ)；除上述利用網(wǎng)絡(luò)的計(jì)算幾何架構(gòu)信息外，凌春[5]也利用節(jié)點(diǎn)的覆蓋信息指引蟻群搜索的方向，以信息素濃度判斷節(jié)點(diǎn)的空洞邊界信息；周宇[6]提出了最小覆蓋圓與蜂窩生長(zhǎng)兩種修補(bǔ)空洞方法，對(duì)不同形狀的空洞采取不同的算法進(jìn)行修復(fù)。文獻(xiàn)[7]通過(guò)空洞建立虛擬修復(fù)位置和移動(dòng)節(jié)點(diǎn)的距離對(duì)照表，生成全局最佳的移動(dòng)策略。文獻(xiàn)[8]以非并行的方式選擇含空洞劣弧的邊界節(jié)點(diǎn)，并將其作為空洞修復(fù)驅(qū)動(dòng)節(jié)點(diǎn)，采用弧二分法確定最佳修補(bǔ)位置。

雖然以尋優(yōu)為目標(biāo)的集中式算法精度較高，但運(yùn)算復(fù)雜度也隨之更大。分布式的本地算法將中央處理器的計(jì)算任務(wù)分散到各節(jié)點(diǎn)中，采用并行或時(shí)間戳交換的方式加快探測(cè)和修補(bǔ)效率。分布式探測(cè)空洞研究中，文獻(xiàn)[9]建立極坐標(biāo)系，得到鄰居間相對(duì)位置與覆蓋弧信息，確定節(jié)點(diǎn)的單純覆蓋弧序列并生成覆蓋空洞；馬文鈺[10]提出了邊界線(xiàn)段檢測(cè)與圓周檢測(cè)進(jìn)階式雙算法，并將其擴(kuò)展到K－覆蓋場(chǎng)景。文獻(xiàn)[11]使用周長(zhǎng)邊界算法驗(yàn)證節(jié)點(diǎn)是否被指定節(jié)點(diǎn)覆蓋，并通過(guò)弧交點(diǎn)位置以確定是否為邊界節(jié)點(diǎn)。為了分布式修補(bǔ)空洞，文獻(xiàn)[12]通過(guò)覆蓋鄰居信息對(duì)節(jié)點(diǎn)建立模糊推理系統(tǒng)模型，選擇最適合的鄰居節(jié)點(diǎn)移動(dòng)修補(bǔ)。Khalifa B[13]對(duì)空洞臨界節(jié)點(diǎn)進(jìn)行判斷，量化其對(duì)空洞的重疊度和剩余能量，選擇節(jié)點(diǎn)以膨脹或移動(dòng)方式進(jìn)行修補(bǔ)。黃祎[14]在考慮節(jié)點(diǎn)剩余能量、覆蓋冗余率與移動(dòng)距離信息的基礎(chǔ)上，擇優(yōu)節(jié)點(diǎn)進(jìn)行空洞修復(fù)。

在已有的優(yōu)化空洞覆蓋問(wèn)題研究中，無(wú)論是利用復(fù)雜但準(zhǔn)確的集中式方案，還是低成本但粗糙的分布式方案，皆普遍地將探測(cè)與修補(bǔ)過(guò)程人為分裂成兩個(gè)獨(dú)立環(huán)節(jié)加以研究；并且相比于同構(gòu)網(wǎng)絡(luò)的空洞研究，直接面向異構(gòu)網(wǎng)絡(luò)場(chǎng)景的成果更為罕見(jiàn)。

基于研究過(guò)程的分裂性和對(duì)象的單一化問(wèn)題，論文提出的CHHA算法融入了異構(gòu)元素，并連貫一致地解決傳感網(wǎng)空洞的探測(cè)與修補(bǔ)。首先將連續(xù)空間面上尋找空洞的問(wèn)題轉(zhuǎn)化為在有限離散空間交點(diǎn)間尋找空洞；在節(jié)點(diǎn)收集的空洞信息順序穿連的同時(shí)，巧妙勾勒空洞軌跡；為體現(xiàn)探測(cè)與修補(bǔ)空洞間的耦合關(guān)系，算法對(duì)勾勒的空洞弧信息與節(jié)點(diǎn)特征加以區(qū)分，給出針對(duì)性的修補(bǔ)方案。針對(duì)異構(gòu)網(wǎng)絡(luò)的CHHA算法，基于本地化完成探測(cè)勾勒空洞的同時(shí)，對(duì)空洞進(jìn)行了較為高效的修補(bǔ)。

1 基本概念

1.1 場(chǎng)景架構(gòu)

考慮到傳感器節(jié)點(diǎn)間的異構(gòu)性且具有移動(dòng)屬性，將對(duì)網(wǎng)絡(luò)的模型做如下假設(shè):

網(wǎng)絡(luò)模型:矩形區(qū)域DetectArea＝X×Y內(nèi)隨機(jī)拋撒N個(gè)異構(gòu)可移動(dòng)的傳感器節(jié)點(diǎn)S＝{s i(x i，y i)｜i＝1，2，…N}[15]，其中(x i，y i)為s i的中心坐標(biāo)。

異構(gòu)模型:傳感器節(jié)點(diǎn)s i的多級(jí)異構(gòu)屬性體現(xiàn)在感知半徑R s i∈[Rsmin，Rsmax]，節(jié)點(diǎn)均采用布爾感知模型[16]，即節(jié)點(diǎn)可以監(jiān)測(cè)圓盤(pán)區(qū)域Sensori＝{(x，內(nèi)的任意點(diǎn)。為滿(mǎn)足節(jié)點(diǎn)間的通信要求，s i的通信半徑Rc i需滿(mǎn)足

1.2 相關(guān)定義

若點(diǎn)s i與s j間的歐式距離d(s i，s j)滿(mǎn)足d(s i，s j)

定義1 弧交點(diǎn)

Sensori與Sensorj的弧交點(diǎn)記為:

若s j?NeiListi，則｜AIi，j｜＝0；若d(s i，s j)＝R s i＋R s j，則｜AIi，j｜＝1；若d(s i，s j)

若?C∈Arci_AB滿(mǎn)足則Arci_AB為空洞弧，記為hole(Arci_AB)＝1；反之，hole(Arci_AB)＝0，其中，hole(·)＝1表示其中的元素·不被其他節(jié)點(diǎn)覆蓋。s i的空洞弧集合記 為 HoleListi＝ { Arci_AIListxiAIListx＋1i｜ hole(Arci_AIListxiAIListx＋1i)＝1}，HoleListn i記為HoleListi中的第n條空洞弧，1≤n≤｜HoleListi｜。若圓心角則Arci_AB該弧稱(chēng)為優(yōu)??；反之為劣弧。

定義3 覆蓋率[15]

DetectArea內(nèi)，S中所有節(jié)點(diǎn)感知圓盤(pán)并集的占比，作為該網(wǎng)絡(luò)的覆蓋率，記為:

定義4 平均移動(dòng)距離[16]

s i在優(yōu)化前后的位置分別為(x i，y i)和(x′i，y′i)，則S在算法運(yùn)行過(guò)程中的平均移動(dòng)距離記為

2 勾勒空洞

探測(cè)空洞是優(yōu)化網(wǎng)絡(luò)拓?fù)涞那疤?，?jié)點(diǎn)如何從分布不均的網(wǎng)絡(luò)中，準(zhǔn)確并快速地探測(cè)出自身覆蓋圓弧上的全部空洞弧是探測(cè)階段的關(guān)鍵。通過(guò)一跳覆蓋鄰居信息，節(jié)點(diǎn)分布式地探測(cè)本地覆蓋圓周上的空洞弧，并對(duì)其進(jìn)行勾勒。

2.1 空洞弧判斷策略

s i以自身為原點(diǎn)建立極坐標(biāo)系，收發(fā)一次信息即可得到NeiListi，繼而計(jì)算得出AIListi，AIListi中相鄰的弧交點(diǎn)會(huì)將s i覆蓋圓弧劃分成若干個(gè)首尾相連且互不相交的弧子段。

定理1 若?C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，則hole(Arci_AB)＝1。

證明:采用反證法。假設(shè)?C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，但hole(Arci_AB)＝0。因?yàn)锳和B是兩個(gè)連續(xù)的弧交點(diǎn)，所以?A′∈Arci_AB皆滿(mǎn)足hole(A′)＝hole(Arci_A B)；由結(jié)論得知，hole(Arci_AB)＝0且C∈Arci_AB，所以hole(C)＝hole(Arci_AB)＝0，與假設(shè)矛盾，不成立。所以若?C∈Arci_AB使得hole(C)＝1(C≠A＆C≠B)，則hole(Arci_AB)＝1，證畢。

2.2 空洞勾勒

通過(guò)兩個(gè)相鄰弧交點(diǎn)，即可得出兩者間弧子段的空洞屬性。按定理1對(duì)s i所有弧子段依次遍歷，判斷s i是否處于空洞邊界，進(jìn)而計(jì)算出s i的所有空洞弧段，并勾勒空洞弧。具體流程見(jiàn)表1偽代碼所示。

表1 空洞勾勒步驟

Line6是基于定理1篩選空洞弧的過(guò)程。節(jié)點(diǎn)僅需自身一跳鄰居位置信息，即可對(duì)自身覆蓋圓弧進(jìn)行拆分，進(jìn)而勾勒出節(jié)點(diǎn)的所有空洞弧。

3 修補(bǔ)空洞

節(jié)點(diǎn)如何利用空洞信息來(lái)最大化移動(dòng)效率，是網(wǎng)絡(luò)拓?fù)鋬?yōu)化的關(guān)鍵。論文中，si將會(huì)以HoleListi作為修補(bǔ)目標(biāo)，依照空洞弧的數(shù)量與半徑，選擇自修補(bǔ)或招募冗余節(jié)點(diǎn)修補(bǔ)的方式對(duì)空洞弧進(jìn)行相應(yīng)填充。

3.1 節(jié)點(diǎn)冗余評(píng)估

若將某節(jié)點(diǎn)移除，網(wǎng)絡(luò)覆蓋率不會(huì)因此降低，則該節(jié)點(diǎn)為完全冗余節(jié)點(diǎn)。顯然，完全冗余節(jié)點(diǎn)在網(wǎng)絡(luò)中的實(shí)際價(jià)值并不大，甚至?xí)a(chǎn)生信息沖突問(wèn)題；但該類(lèi)節(jié)點(diǎn)卻能作為修補(bǔ)空洞的候選節(jié)點(diǎn)。若以合適的方式評(píng)估出完全冗余節(jié)點(diǎn)并加以應(yīng)用，則能以較低的開(kāi)銷(xiāo)優(yōu)化網(wǎng)絡(luò)的拓?fù)湫阅堋?/p>

定義5K－覆蓋鄰居交點(diǎn)

若? 1≤p≠q≤Degreei，滿(mǎn)足條件｜AINeiListpi，NeiListqi∩Sensori｜≠0，則s i的覆蓋鄰居交點(diǎn)CAIListi＝AINeiListpiNeiListqi∩Sensori。 若s i∩NeiListi覆蓋該交點(diǎn)的次數(shù)為K，s i的所有K－覆蓋鄰居交點(diǎn)組成集合K-CAIListi。

如圖1所示，CAIListi＝{A，B，C，D，E，F(xiàn)，G，H，I}中，1－CAIListi＝{A，B，C，D，E，F(xiàn)，G}；2-CAIListi＝{H，I}，H、I被s i與s j同時(shí)覆蓋。顯而易見(jiàn)，對(duì)于s i的1－CAIListi，1對(duì)應(yīng)的就是s i節(jié)點(diǎn)本身，若將s i移除，則1－CAIListi中所有點(diǎn)皆為新產(chǎn)生空洞的邊界點(diǎn)。而對(duì)于si的K－覆蓋鄰居交點(diǎn)(K>1)，若將s i移除，仍有K－1個(gè)節(jié)點(diǎn)將該交點(diǎn)覆蓋。

圖1 空洞邊界節(jié)點(diǎn)的空洞弧集合

定理2 若Degreei≠0，｜1－CAIListi｜＝0，｜Hole-Listi｜＝0皆成立，則Sensori是一個(gè)完全冗余節(jié)點(diǎn)。

證明:采用反證法。假設(shè)Degreei≠0，｜1－CAIListi｜＝0，｜HoleListi｜＝0皆成立，但s i不是一個(gè)完全冗余節(jié)點(diǎn)。由于s i不是一個(gè)完全冗余節(jié)點(diǎn)且｜HoleListi｜＝＝0，所以若移除s i，新產(chǎn)生的邊界點(diǎn)一定在Sensori內(nèi)，而Sensori內(nèi)的邊界點(diǎn)必定是1－覆蓋鄰居交點(diǎn)，與｜1－CAIListi｜＝＝0矛盾。所以若Degreei≠0，｜1－CAIListi｜＝＝0，｜HoleListi｜＝＝0皆成立，則s i是一個(gè)完全冗余節(jié)點(diǎn)，證畢。

節(jié)點(diǎn)通過(guò)自身一跳覆蓋鄰居信息即可得到自身的1－CAIListi，并與HoleListi信息輔以比較從而判斷自身是否完全冗余。具體流程如表2所示。

表2 節(jié)點(diǎn)冗余評(píng)估步驟

上述流程中，s i收發(fā)一次信息得到NeiListi，并通過(guò)一跳覆蓋鄰居位置計(jì)算其1－覆蓋交點(diǎn)。s i通過(guò)Degreei、CAIListi和HoleListi三個(gè)指標(biāo)，即可精準(zhǔn)判斷自身于網(wǎng)絡(luò)是否冗余。

3.2 自修補(bǔ)

探測(cè)出自身覆蓋圓盤(pán)上的空洞弧之后，節(jié)點(diǎn)首先可以嘗試移動(dòng)自身填補(bǔ)空洞。

在｜HoleListi｜>1或∠HoleList1i>π/2的條件下，s i進(jìn)行移動(dòng)可能會(huì)產(chǎn)生更大的覆蓋冗余或空洞，所以自身移動(dòng)修補(bǔ)時(shí)僅選擇唯一劣弧進(jìn)行修復(fù)。另外，若s i移動(dòng)時(shí)始終保持對(duì)1－CAIListi全覆蓋，則s i不會(huì)新增空洞弧。

①自修補(bǔ)條件

Degreei>1的前提下，｜HoleListi｜＝1且為劣弧時(shí)，節(jié)點(diǎn)s i執(zhí)行自修補(bǔ)。

②移動(dòng)方向

為盡量填補(bǔ)空洞對(duì)網(wǎng)絡(luò)覆蓋造成的影響，將空洞弧中點(diǎn)設(shè)為目標(biāo)方向，記為:

③移動(dòng)距離

1－CAIListi中第k個(gè)點(diǎn)CAIListi｜)，以－αi為方向交Sensori于點(diǎn)Roundn。則s i執(zhí)行自修補(bǔ)時(shí)的移動(dòng)距離Disi為:

式中:k＝1，2，…，｜1－CAIListi｜。

3.3 招募修補(bǔ)

若節(jié)點(diǎn)s i不滿(mǎn)足自修補(bǔ)條件，可從NeiListi招募完全冗余節(jié)點(diǎn)對(duì)空洞弧進(jìn)行移動(dòng)修復(fù)。

若s i為HoleListi中所有弧進(jìn)行招募，會(huì)造成多段空洞弧對(duì)同一關(guān)聯(lián)節(jié)點(diǎn)的反復(fù)招募計(jì)算，引發(fā)復(fù)雜度極大提升；再者，該舉動(dòng)會(huì)使得s i的鄰居可能會(huì)面臨“無(wú)節(jié)點(diǎn)可招募”問(wèn)題，導(dǎo)致s i陷入局部最優(yōu)。所以s i執(zhí)行招募修補(bǔ)時(shí)，僅將弧targetArc滿(mǎn)足作為修補(bǔ)目標(biāo)。

3.3.1 招募匹配

給定s i，NeiListi中所有完全冗余節(jié)點(diǎn)組成招募候選節(jié)點(diǎn)集合表示ReListi中第n個(gè)節(jié)點(diǎn)在S中的編號(hào)，1≤n≤｜ReListi｜。

定義6 空洞匹配因子

若s j∈ReListi，DisSumj表示s j的總移動(dòng)距離，l(targetArc)表示targetArc的直徑，鄰居s j對(duì)s i的空洞匹配因子記為:式中:ω1、ω2與ω3皆為空洞匹配因子的控制系數(shù)。

s i招募節(jié)點(diǎn)時(shí)考慮到ReListi的DisSumj以節(jié)約能耗，并優(yōu)先招募Rs較小的節(jié)點(diǎn)以節(jié)約招募資源。

3.3.2 招募選擇

設(shè)targetArc的兩個(gè)弧交點(diǎn)分別為A(x a，y a)和B(x b，y b)，targetNodei目標(biāo)位置target的計(jì)算公式為

上式可能會(huì)出現(xiàn)兩個(gè)解target，target′，target滿(mǎn)足d(targetNodei，target)>d(targetNodei，target′)。

3.4 修補(bǔ)實(shí)例

圖2 與圖3分別為節(jié)點(diǎn)滿(mǎn)足自修補(bǔ)或招募修補(bǔ)條件時(shí)的移動(dòng)軌跡。

如圖2所示，1－CAIListi＝{A，B，C}，｜HoleListi｜＝1且所以s i執(zhí)行自修補(bǔ)，向空洞弧中點(diǎn)方向α移動(dòng)min(d A，d B，d C)＝d A，即點(diǎn)位置處。

圖2 自修補(bǔ)空洞弧

如圖3中所示，ReListi＝{s x，s y}。即使存在DisSumx＝DisSumy，但由于Rs xhMatchi，y成立，因此應(yīng)招募s x進(jìn)行修復(fù)。

圖3 招募節(jié)點(diǎn)修補(bǔ)

3.5 算法流程

CHHA算法基于本地優(yōu)化的操作，在精準(zhǔn)探測(cè)空洞的前提下，極大提升了覆蓋質(zhì)量，并兼顧了節(jié)點(diǎn)能耗。CHHA算法能有效提高網(wǎng)絡(luò)的應(yīng)用價(jià)值，其分布式屬性是貫穿整套識(shí)別、勾勒、修補(bǔ)空洞系統(tǒng)流程的精髓。對(duì)給定節(jié)點(diǎn)s i，CHHA算法僅需輻射其一跳范圍內(nèi)的通信鄰居，即可對(duì)自身拓?fù)湮恢蒙系目斩催M(jìn)行全流程處理，具體流程描述如表3所示。

表3 CHHA算法流程

S中每個(gè)節(jié)點(diǎn)利用CHHA算法以基于本地的方式進(jìn)行空洞探測(cè)與修補(bǔ)。Line1為探測(cè)階段，節(jié)點(diǎn)僅利用自身一跳鄰居信息即可檢測(cè)出HoleListi；Line2－4為自修補(bǔ)補(bǔ)償方案，節(jié)點(diǎn)通過(guò)場(chǎng)景拓?fù)溆?jì)算本地最佳位置移動(dòng)修補(bǔ)；Line5－13為招募修補(bǔ)方案，通過(guò)定義的空洞匹配因子，選擇最佳匹配冗余節(jié)點(diǎn)，實(shí)現(xiàn)移動(dòng)能耗與最優(yōu)選擇的多重增益。由于S在計(jì)算1－CAIListi時(shí)需要比較鄰居與鄰居的位置，所以算法的復(fù)雜度為o(｜NeiListi｜2)。

4 仿真實(shí)驗(yàn)

4.1 場(chǎng)景配置

論文的仿真實(shí)驗(yàn)采用MATLAB R2016a平臺(tái)進(jìn)行測(cè)試。仿真主要從可行性、空洞探測(cè)的算法復(fù)雜度及空洞修補(bǔ)的性能等方面進(jìn)行驗(yàn)證。鑒于實(shí)際應(yīng)用中傳感器節(jié)點(diǎn)布置方式為隨機(jī)布撒且節(jié)點(diǎn)具有異構(gòu)性能，各仿真部分的結(jié)果均為多次位置、性能隨機(jī)實(shí)驗(yàn)后的算術(shù)均值。

網(wǎng)絡(luò)的異構(gòu)差異主要體現(xiàn)在節(jié)點(diǎn)的感知半徑Rs在給定范圍內(nèi)的隨機(jī)性。默認(rèn)參數(shù)配置如下:DetectArea＝100 m×100 m，R smin＝4 m，R smax＝6 m，N＝200。經(jīng)大量實(shí)驗(yàn)結(jié)果分析得知，各算法在尋優(yōu)15輪左右后逐漸收斂，故設(shè)定算法的尋優(yōu)次數(shù)上限為times＝20。

4.2 效果測(cè)試

圖4 統(tǒng)計(jì)了CHHA算法對(duì)空洞的識(shí)別與勾勒效果，以及運(yùn)行前后對(duì)網(wǎng)絡(luò)拓?fù)鋬?yōu)化的對(duì)比。運(yùn)行初期(times＝1)，空洞約存在17個(gè)，CovRatio(S)＝78%，隨著算法的迭代運(yùn)算，當(dāng)達(dá)到次數(shù)上限(times＝20)時(shí)，CHHA算法的CovRatio(S)提升至98.12%，空洞個(gè)數(shù)僅為5個(gè)左右，且空洞面積極大縮小?？梢?jiàn)，CHHA算法能對(duì)所有空洞精準(zhǔn)判斷，同時(shí)將網(wǎng)絡(luò)逐漸鋪散，達(dá)到顯著提升場(chǎng)景覆蓋的效果。但由于分布式算法的特性，節(jié)點(diǎn)對(duì)通信范圍外的節(jié)點(diǎn)是不可見(jiàn)的；所以必須承認(rèn)，局部修補(bǔ)的效果受到初始隨機(jī)鋪撒的影響，不能避免零碎空洞。

圖4 CHHA算法的工作效果

4.3 效率測(cè)試

大多數(shù)算法為了更好地闡述問(wèn)題與研究區(qū)分，通常將探測(cè)與修補(bǔ)空洞人為地拆分成兩個(gè)問(wèn)題進(jìn)行解決，因此連貫而一體化完成空洞探測(cè)與修復(fù)的現(xiàn)有文獻(xiàn)并不多見(jiàn)。因此，論文不失一般性地將CHHA算法分別與VEBC[1]、EBDC[11]、CHDA[9]三種經(jīng)典空洞檢測(cè)方法，HHHA[12]、MDL[13]兩種經(jīng)典空洞修補(bǔ)算法進(jìn)行分步地性能測(cè)試與對(duì)比。

①空洞識(shí)別效率

探測(cè)空洞的效率可以通過(guò)機(jī)器的運(yùn)算速度ConsumeTime直接反映。S的平均度記為AvgDegree＝可以表示網(wǎng)絡(luò)的平均擁擠冗余程度。本實(shí)驗(yàn)將考察CHHA算法與同類(lèi)的VEBC、EBDC、CHDA三種算法的檢測(cè)效率對(duì)AvgDegree的敏感情況，即網(wǎng)絡(luò)冗余程度對(duì)算法勾勒空洞效率的影響。論文中節(jié)點(diǎn)布撒的個(gè)數(shù)N一般皆大于200個(gè)，使用密集網(wǎng)絡(luò)的主要原因是:密集網(wǎng)絡(luò)的空洞更為的繁雜，在招募節(jié)點(diǎn)進(jìn)行修補(bǔ)時(shí)有更多選擇的空間；而在稀疏網(wǎng)絡(luò)中，節(jié)點(diǎn)對(duì)空洞的探測(cè)效果與密集網(wǎng)絡(luò)基本相同，但在修補(bǔ)時(shí)不大具有可行性，所以為了達(dá)到網(wǎng)絡(luò)空洞的修補(bǔ)效果，論文的仿真部分皆從密集網(wǎng)絡(luò)入手。

如圖5(a)所示，隨著AvgDegree增長(zhǎng)，網(wǎng)絡(luò)的冗余量上升，從而導(dǎo)致執(zhí)行探測(cè)空洞過(guò)程的復(fù)雜度增大，因此四種算法的ConsumeTime呈遞增趨勢(shì)。由于CHHA算法僅需要一跳鄰居信息即可勾勒空洞弧，其ConsumeTime隨AvgDegree增長(zhǎng)僅呈線(xiàn)性增長(zhǎng)，因此其復(fù)雜度低于其他算法；VEBC算法由于使用到了通信半徑外的虛擬點(diǎn)，即需要獲取一跳以外的鄰居信息，所需消耗的運(yùn)算時(shí)間較高。

圖5 算法效率對(duì)比圖

②空洞修補(bǔ)效率

網(wǎng)絡(luò)整體覆蓋率的變化趨勢(shì)可以直觀評(píng)估空洞修補(bǔ)效率，因此該部分統(tǒng)計(jì)了CHHA算法與HHHA、MDL兩種算法的覆蓋性能提升情況。如圖5(b)所示，三種算法均可對(duì)空洞弧進(jìn)行不同程度的修補(bǔ)，有效優(yōu)化網(wǎng)絡(luò)的覆蓋拓?fù)銫ovRatio，并趨于平穩(wěn)。CHHA算法相較于HHHA、MDL兩種算法上升的速度更快，在times＝8時(shí)就到達(dá)了最高CovRatio(98.2%)的98%，比HHHA算法提前7輪收斂，即Δtimes＝7。這是因?yàn)樵谡心既哂喙?jié)點(diǎn)環(huán)節(jié)，符合要求的節(jié)點(diǎn)利用CHHA算法，可以有效招募并派遣自己覆蓋鄰居中的完全冗余節(jié)點(diǎn)，對(duì)自身覆蓋圓盤(pán)上的空洞弧進(jìn)行修補(bǔ)?？梢?jiàn)，CHHA算法能以更高的迭代效率達(dá)到相對(duì)穩(wěn)定與較優(yōu)的覆蓋率。

4.4 能耗對(duì)比

修補(bǔ)空洞弧時(shí)，傳感器節(jié)點(diǎn)的移動(dòng)會(huì)造成大量的能量損耗，通過(guò)能量損耗大小能夠評(píng)估出算法的可行性。論文以網(wǎng)絡(luò)S的平均移動(dòng)距離AvgDis作為能量損耗的尺度，衡量CHHA與HHHA、MDL三種算法的能耗受times與AvgDegree的影響程度。

如圖6所示，各算法的AvgDis隨times的增加呈遞減變化，這是因?yàn)殡S著算法的運(yùn)行，空洞弧區(qū)間越來(lái)越少，場(chǎng)景覆蓋率逐漸飽和；另一角度，AvgDegree的增加會(huì)導(dǎo)致節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)更為“緊湊”，在修補(bǔ)時(shí)節(jié)點(diǎn)需要移動(dòng)更遠(yuǎn)的距離才能鋪散開(kāi)。但CHHA算法的AvgDis圖形始終被HHHA、MDL所“覆蓋”，這是因?yàn)樵谶x擇冗余節(jié)點(diǎn)進(jìn)行修補(bǔ)時(shí)，綜合考慮冗余節(jié)點(diǎn)當(dāng)前已移動(dòng)距離以及冗余節(jié)點(diǎn)到空洞弧的距離，盡可能避免節(jié)點(diǎn)無(wú)效的移動(dòng)損耗。如圖所示，在實(shí)驗(yàn)中初始場(chǎng)景條件最好的Avg-Degree＝5條件下，CHHA算法(1.45 m)能比AvgDis最大的HHHA算法(1.98 m)節(jié)約四分之一左右的移動(dòng)損耗，且對(duì)AvgDegree具有更低的敏感性。

圖6 修補(bǔ)空洞能耗對(duì)比

4.5 對(duì)異構(gòu)性的敏感度

異構(gòu)性體現(xiàn)在網(wǎng)絡(luò)中節(jié)點(diǎn)在拓?fù)浜透采w范圍上的差異性，數(shù)值上體現(xiàn)為R smax與R smin間的跨度差異，其異構(gòu)率HeteroRatio＝R smax/R smin則反映了這種感知半徑的差異性。HeteroRatio不同的情況下，為保證節(jié)點(diǎn)間的連通性能，傳感器網(wǎng)絡(luò)的拓?fù)鋾?huì)不盡相同。本實(shí)驗(yàn)統(tǒng)計(jì)了CHHA與HHHA、MDL的覆蓋率對(duì)HeteroRatio改變的敏感程度。

記ΔCovRatio為網(wǎng)絡(luò)覆蓋率在算法執(zhí)行后的優(yōu)化量。如圖7可見(jiàn)，三種算法雖能在HeteroRatio不同的情況下，一定程度地有效提高ΔCovRatio(即ΔCovRatio>0)，但其增速在圖中體現(xiàn)為下降趨勢(shì)。原因在于，當(dāng)HeteroRatio提高時(shí)，節(jié)點(diǎn)的空洞弧增加，很多完全冗余節(jié)點(diǎn)的直徑(2Rs)小于空洞弧的跨度直徑距離，不能有效修復(fù)空洞??；同時(shí)節(jié)點(diǎn)異構(gòu)率的增大也會(huì)導(dǎo)致網(wǎng)絡(luò)中節(jié)點(diǎn)與節(jié)點(diǎn)間的拓?fù)涓拥亍熬o湊”，冗余度相對(duì)提高，從而導(dǎo)致CovRatio受到影響。但CHHA的ΔCovRatio始終大于HHHA與MDL，這是由于每次在修補(bǔ)空洞弧時(shí)，節(jié)點(diǎn)計(jì)算冗余節(jié)點(diǎn)的空洞匹配因子時(shí)，會(huì)優(yōu)先為目標(biāo)空洞弧招募半徑小、離空洞弧近的冗余節(jié)點(diǎn)進(jìn)行修補(bǔ)，從而達(dá)到分布式最佳的策略。

圖7 異構(gòu)程度對(duì)覆蓋率的影響

5 總結(jié)

論文針對(duì)異構(gòu)傳感器網(wǎng)絡(luò)的拓?fù)鋯?wèn)題，提出了一種分布式探測(cè)與修補(bǔ)空洞的算法。通過(guò)算法，節(jié)點(diǎn)僅需知道一跳鄰居的信息即可計(jì)算出自身覆蓋圓盤(pán)上的所有空洞?。还?jié)點(diǎn)將對(duì)空洞弧的數(shù)量及大小進(jìn)行判斷，從而使用合適的修補(bǔ)策略對(duì)目標(biāo)空洞弧進(jìn)行分布式地修補(bǔ)，從而增強(qiáng)網(wǎng)絡(luò)的覆蓋效能。仿真結(jié)果表明，相較于VEBC、EBDC、CHDA三個(gè)已有的空洞發(fā)現(xiàn)策略，CHHA算法能以更高的效率檢測(cè)空洞；且CHHA算法相較于HHHA、MDL也能以更高的效率、較低的能耗、對(duì)網(wǎng)絡(luò)異構(gòu)差異更低的敏感性對(duì)空洞弧進(jìn)行修補(bǔ)。