吳 儀，秦寧寧，2*

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

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

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

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

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

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

1 基本概念

1.1 場景架構(gòu)

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

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

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

1.2 相關(guān)定義

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

定義1 弧交點

Sensori與Sensorj的弧交點記為:

若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滿足則Arci_AB為空洞弧，記為hole(Arci_AB)＝1；反之，hole(Arci_AB)＝0，其中，hole(·)＝1表示其中的元素·不被其他節(jié)點覆蓋。s i的空洞弧集合記 為 HoleListi＝ { Arci_AIListxiAIListx＋1i｜ hole(Arci_AIListxiAIListx＋1i)＝1}，HoleListn i記為HoleListi中的第n條空洞弧，1≤n≤｜HoleListi｜。若圓心角則Arci_AB該弧稱為優(yōu)弧；反之為劣弧。

定義3 覆蓋率[15]

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

定義4 平均移動距離[16]

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

2 勾勒空洞

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

2.1 空洞弧判斷策略

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

定理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。因為A和B是兩個連續(xù)的弧交點，所以?A′∈Arci_AB皆滿足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 空洞勾勒

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

表1 空洞勾勒步驟

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

3 修補(bǔ)空洞

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

3.1 節(jié)點冗余評估

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

定義5K－覆蓋鄰居交點

若? 1≤p≠q≤Degreei，滿足條件｜AINeiListpi，NeiListqi∩Sensori｜≠0，則s i的覆蓋鄰居交點CAIListi＝AINeiListpiNeiListqi∩Sensori。 若s i∩NeiListi覆蓋該交點的次數(shù)為K，s i的所有K－覆蓋鄰居交點組成集合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同時覆蓋。顯而易見，對于s i的1－CAIListi，1對應(yīng)的就是s i節(jié)點本身，若將s i移除，則1－CAIListi中所有點皆為新產(chǎn)生空洞的邊界點。而對于si的K－覆蓋鄰居交點(K>1)，若將s i移除，仍有K－1個節(jié)點將該交點覆蓋。

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

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

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

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

表2 節(jié)點冗余評估步驟

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

3.2 自修補(bǔ)

探測出自身覆蓋圓盤上的空洞弧之后，節(jié)點首先可以嘗試移動自身填補(bǔ)空洞。

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

①自修補(bǔ)條件

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

②移動方向

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

③移動距離

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

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

3.3 招募修補(bǔ)

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

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

3.3.1 招募匹配

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

定義6 空洞匹配因子

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

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

3.3.2 招募選擇

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

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

3.4 修補(bǔ)實例

圖2 與圖3分別為節(jié)點滿足自修補(bǔ)或招募修補(bǔ)條件時的移動軌跡。

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

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

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

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

3.5 算法流程

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

表3 CHHA算法流程

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

4 仿真實驗

4.1 場景配置

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

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

4.2 效果測試

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

圖4 CHHA算法的工作效果

4.3 效率測試

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

①空洞識別效率

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

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

圖5 算法效率對比圖

②空洞修補(bǔ)效率

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

4.4 能耗對比

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

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

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

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

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

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

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

5 總結(jié)

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