王茂秋，張 江，張晶,3,4

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院,云南 昆明 650500;2.中國(guó)船舶集團(tuán)有限公司第七〇五研究所昆明分部，云南 昆明 650102;3.云南梟潤(rùn)科技服務(wù)有限公司,云南 昆明 650500;4.昆明理工大學(xué)云南省人工智能重點(diǎn)實(shí)驗(yàn)室，云南 昆明 650500)

1 引言

在信息化時(shí)代，實(shí)時(shí)掌握指定區(qū)域內(nèi)狀態(tài)的技術(shù)常被應(yīng)用到軍事、氣象等多個(gè)領(lǐng)域[1]，作為計(jì)算機(jī)網(wǎng)絡(luò)中最重要的技術(shù)，無線傳感器網(wǎng)絡(luò)也得到了前所未有的發(fā)展。無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)通過對(duì)覆蓋區(qū)域進(jìn)行數(shù)據(jù)的收集、信息的檢測(cè)、信息的識(shí)別、位置的定位和節(jié)點(diǎn)的操控來保證對(duì)指定區(qū)域的信息控制[2]。然而在無線傳感器網(wǎng)絡(luò)領(lǐng)域，仍有很多問題需要進(jìn)一步解決，傳感器節(jié)點(diǎn)通常容易因?yàn)闂l件復(fù)雜的環(huán)境而損壞，再加上節(jié)點(diǎn)需要控制自身體積，其所能擁有的能量有限，一旦部分節(jié)點(diǎn)損壞或者能量耗盡，會(huì)導(dǎo)致正常節(jié)點(diǎn)與失效節(jié)點(diǎn)無法通信，使得整個(gè)傳感器網(wǎng)絡(luò)被隔離成若干個(gè)獨(dú)立的分區(qū)，最終導(dǎo)致網(wǎng)絡(luò)癱瘓。因此，如何恢復(fù)傳感器網(wǎng)絡(luò)的連通并且保障恢復(fù)后網(wǎng)絡(luò)的高效性和健壯性成為了此領(lǐng)域的研究熱點(diǎn)[3]。

近年來，很多學(xué)者為無線傳感器網(wǎng)絡(luò)連通恢復(fù)相關(guān)工作做出了努力，Abbasi等人[4]提出了DARA(Distributed Actor Recovery Algorithm)算法，該算法通過綜合距離、節(jié)點(diǎn)度和節(jié)點(diǎn)標(biāo)號(hào)等因素來選擇現(xiàn)有節(jié)點(diǎn)，移動(dòng)被選節(jié)點(diǎn)到指定區(qū)域以恢復(fù)連通。Senel等人[5,6]將基于蜘蛛網(wǎng)結(jié)構(gòu)的仿生研究應(yīng)用到無線傳感器網(wǎng)絡(luò)連通恢復(fù)上，提出了1C-SpiderWeb算法，利用近似網(wǎng)狀的拓?fù)浣Y(jié)構(gòu)對(duì)癱瘓區(qū)域?qū)崿F(xiàn)了連通恢復(fù)，但是所需要的中繼節(jié)點(diǎn)RN(Relay Node)數(shù)量較多，增加了恢復(fù)連通的成本，并且這種拓?fù)浣Y(jié)構(gòu)較為復(fù)雜，導(dǎo)致其容錯(cuò)性較差。Lee等人[7]提出了用最小斯坦納樹恢復(fù)無線傳感器網(wǎng)絡(luò)多個(gè)同時(shí)故障的算法，算法以斯坦納樹為初始拓?fù)浣Y(jié)構(gòu)，研究了RN的放置位置，并以RN的放置位置計(jì)算出最少的中繼節(jié)點(diǎn)數(shù)量，通過移動(dòng)中繼節(jié)點(diǎn)來達(dá)到故障區(qū)域的連通恢復(fù)，但是該算法不能保證移動(dòng)RN冗余以及恢復(fù)連通后傳感器網(wǎng)絡(luò)的健壯性。Senel等人[8]在2011年提出FeSTA(Federate network Segments via triangular steiner Tree Approximation)算法,將三角形斯坦納樹結(jié)構(gòu)用于網(wǎng)絡(luò)的斷連恢復(fù)，利用三角形斯坦納樹結(jié)構(gòu)的特點(diǎn)有效地降低了中繼節(jié)點(diǎn)部署數(shù)量。

為了使連通恢復(fù)后的無線傳感器網(wǎng)絡(luò)高效且健壯，本文提出了基于斯坦納樹和泰森多邊形的連通恢復(fù)算法CRAST(Connectivity Restoration Algorithm based on Steiner tree and Tyson Polygon)。本文采用改進(jìn)泰森多邊形部署可移動(dòng)的備用節(jié)點(diǎn)。文獻(xiàn)[9]描述了泰森多邊形的性質(zhì)以及泰森多邊形的常規(guī)生成法，提出了相鄰離散點(diǎn)是以泰森多邊形邊對(duì)稱的。文獻(xiàn)[10]提出了使用三角剖分算法構(gòu)建泰森多邊形，該算法生成泰森多邊形的速度較快，并且提出了新的算法迅速分類出鄰近節(jié)點(diǎn)，提高了生成泰森多邊形的效率。

2 網(wǎng)絡(luò)模型

2.1 問題描述

四邊形斯坦納樹結(jié)構(gòu)部署RN相比于三角形斯坦納樹結(jié)構(gòu)和最小生成樹結(jié)構(gòu)[11]部署RN，可以以較少的RN實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)的連通恢復(fù)，故本文使用四邊形斯坦納樹結(jié)構(gòu)來部署RN使癱瘓區(qū)域?qū)崿F(xiàn)連通恢復(fù)。由于四邊形斯坦納樹的連通恢復(fù)方法過度依賴其中的關(guān)鍵節(jié)點(diǎn)KN(Key Node)，導(dǎo)致一方面這些KN相較其他節(jié)點(diǎn)而言需要消耗更多的能量，最終因能量消耗殆盡而停止工作，另一方面惡劣的外界環(huán)境極可能會(huì)毀壞這些KN，導(dǎo)致網(wǎng)絡(luò)的大片區(qū)域再次陷入癱瘓狀態(tài)。本文針對(duì)這個(gè)問題，提出了用泰森多邊形的算法在恢復(fù)區(qū)域內(nèi)部署KN的備用節(jié)點(diǎn)SN(Standby Node)，在KN損壞時(shí)能夠通過移動(dòng)SN及時(shí)地使傳感器網(wǎng)絡(luò)再次恢復(fù)到連通狀態(tài)。

2.2 系統(tǒng)模型

將M個(gè)離散點(diǎn)隨機(jī)部署在區(qū)域Ω中，表示區(qū)域Ω中的M個(gè)節(jié)點(diǎn)。一般情況下，能量耗盡和惡劣的外界條件會(huì)導(dǎo)致傳感器某些節(jié)點(diǎn)失效，從而使網(wǎng)絡(luò)在區(qū)域Ω中被拆分為多個(gè)節(jié)點(diǎn)群。我們把節(jié)點(diǎn)群內(nèi)所有節(jié)點(diǎn)能夠相互進(jìn)行通信的節(jié)點(diǎn)群稱為分區(qū)，將這些分區(qū)看作為點(diǎn)，每個(gè)分區(qū)用Segi表示，i∈[1,n]，故n為劃分的分區(qū)數(shù)量，如圖1所示，分區(qū)與分區(qū)之間無法進(jìn)行通信。

Figure 1 Partitioned area Ω圖1 分區(qū)后的區(qū)域Ω

2.3 算法基本理論

定義1(四邊形斯坦納點(diǎn)) 根據(jù)文獻(xiàn)[12]對(duì)于任意1個(gè)四邊形，其內(nèi)部存在2個(gè)點(diǎn)，使得四邊形的4個(gè)頂點(diǎn)通過這2個(gè)點(diǎn)連接的長(zhǎng)度最小。

定義2(凸非退化型四邊形) 若1個(gè)四邊形中的4個(gè)內(nèi)角均小于或等于120°，則這個(gè)四邊形為凸非退化四邊形。

定義3(斯坦納點(diǎn)) 對(duì)于任意凸非退化型四邊形ABCD，對(duì)其2條對(duì)角線的銳角夾角所對(duì)的2條邊分別向銳角開口方向作等邊三角形得到△ABE和△BCF,對(duì)△ABE和△BCF分別做外接圓；連接E、F得到線段EF，EF與2個(gè)外接圓相交的2個(gè)點(diǎn)即為ABCD的斯坦納點(diǎn)。

定義4(Delaunay三角網(wǎng)) 由若干個(gè)三角形組成的網(wǎng)絡(luò)，并且互為相鄰的三角形的相鄰邊為2個(gè)三角形公共的邊[13]，如圖2a和圖2b所示。

Figure 2 區(qū)域Ω內(nèi)散點(diǎn)和基于散點(diǎn)的Delaunay網(wǎng)圖2 Discrete points in region Ω, and Delaunay triangulation formed by discrete points

定義5(凸包插值算法) 該算法是基于多維空間中生成Delaunay三角網(wǎng)的算法，先后使用凸包生成、環(huán)切邊界凸包三角剖分和內(nèi)插法構(gòu)建Delaunay三角形，具體步驟可參照文獻(xiàn)[14]。

3 四邊形斯坦納樹連通恢復(fù)算法

由于連通恢復(fù)問題為NP難問題，本文使用作為啟發(fā)式算法的四邊形斯坦納樹算法。若要將區(qū)域Ω內(nèi)的所有分區(qū)用中繼節(jié)點(diǎn)RN連接，四邊形斯坦納樹連接算法是最節(jié)省中繼節(jié)點(diǎn)的，算法步驟如下所示：

(1)對(duì)區(qū)域Ω內(nèi)的所有分區(qū)以4個(gè)分區(qū)為1組的方式進(jìn)行組合，枚舉出全部非退化四邊形。

(2)計(jì)算枚舉出的全部非退化四邊形的周長(zhǎng)，并按照周長(zhǎng)從小到大將這些非退化四邊形存入數(shù)組NQ[]中。按照數(shù)組的順序?qū)λ蟹峭嘶倪呅芜M(jìn)行判別，若非退化四邊形的頂點(diǎn)被其他非退化四邊形占用的個(gè)數(shù)小于或等于1，則對(duì)此非退化四邊形按照定義3的方法標(biāo)出此非退化四邊形的斯坦納點(diǎn)，將斯坦納點(diǎn)與頂點(diǎn)連接起來即為斯坦納邊，再沿著斯坦納邊部署中繼節(jié)點(diǎn)。每條去掉端點(diǎn)的斯坦納邊的中繼節(jié)點(diǎn)RN個(gè)數(shù)用Numse表示，則：

(1)

其中,lengthse表示每條斯坦納邊的長(zhǎng)度；R表示中繼節(jié)點(diǎn)的通信半徑。連通的非退化四邊形被看作一個(gè)分區(qū)，繼續(xù)抽象為點(diǎn)與其他分區(qū)組合為非退化四邊形。

(3)在無法再用非退化四邊形方式連通后，枚舉出剩余分區(qū)的三角形組合，按照三角形斯坦納樹連通，無法構(gòu)建三角形斯坦納樹的分區(qū)則與距離最近并且已與主體連通的分區(qū)沿直線連通，如圖3所示，SegA～SegL為分區(qū)，K1～K6為關(guān)鍵節(jié)點(diǎn)KN。

Figure 3 Quadrilateral Steiner connectivity restoration圖3 四邊形斯坦納連通恢復(fù)

4 基于泰森多邊形的優(yōu)化算法

在保證中繼節(jié)點(diǎn)數(shù)量盡可能少的情況下，本文使用四邊形斯坦納樹的連通恢復(fù)算法恢復(fù)了癱瘓區(qū)域，使所有分區(qū)實(shí)現(xiàn)了相互連通。為了保證恢復(fù)網(wǎng)絡(luò)的健壯性，本文針對(duì)四邊形斯坦納點(diǎn)所在的關(guān)鍵節(jié)點(diǎn)KN，使用泰森多邊形的拓?fù)浣Y(jié)構(gòu)部署備用節(jié)點(diǎn)SN，保證在這些關(guān)鍵節(jié)點(diǎn)損壞時(shí)能夠及時(shí)移動(dòng)備用中繼節(jié)點(diǎn)替換。

4.1 泰森多邊形部署節(jié)點(diǎn)

根據(jù)泰森多邊形的性質(zhì)可知，泰森多邊形每個(gè)頂點(diǎn)是與另外2個(gè)以上的泰森多邊形的共同頂點(diǎn)，并且泰森多邊形的每個(gè)頂點(diǎn)到其對(duì)應(yīng)的2個(gè)離散點(diǎn)距離相等，所以對(duì)于整個(gè)傳感器網(wǎng)絡(luò)而言，使用泰森多邊形部署SN可以極大減少SN的部署數(shù)量，同時(shí)還能保證SN冗余。算法步驟如下所示：

(1)用KN構(gòu)建Delaunay三角形。

(2)將KN節(jié)點(diǎn)編號(hào)儲(chǔ)存入數(shù)組KN[]中，將三角形編號(hào)并儲(chǔ)存入數(shù)組TRI[]中，記錄每個(gè)三角形所對(duì)應(yīng)的3個(gè)KN節(jié)點(diǎn)，即TRI[]→KN[]。

(3)根據(jù)TRI[]→KN[]，對(duì)與每個(gè)KN節(jié)點(diǎn)相鄰的三角形標(biāo)號(hào)，如圖4所示，對(duì)于任意KN，假設(shè)此KN為K7，則找出與K7同為一個(gè)三角形頂點(diǎn)的另外一個(gè)頂點(diǎn)，假設(shè)此頂點(diǎn)為K8且此三角形為A，則能夠找出三角形A的第3個(gè)頂點(diǎn)并假設(shè)此頂點(diǎn)為K9，以K7和K9為頂點(diǎn)，則能找到三角形B的第3個(gè)頂點(diǎn)并假設(shè)為K10，以K7和K10為頂點(diǎn)，則能找到三角形C的第3個(gè)頂點(diǎn)并假設(shè)為K11，以此類推，直至回到以K7和K8為頂點(diǎn)時(shí)結(jié)束此KN相鄰三角形的排序[15,16]。按照排序?qū)⑾噜徣切蝺?chǔ)存入數(shù)組AD[]中。

Figure 4 Delaunay triangles are sorted counterclockwise圖4 Delaunay三角形逆時(shí)針排序

(4)構(gòu)建數(shù)組TRI[]內(nèi)每個(gè)三角形的外接圓圓心，將相鄰三角形的外接圓圓心連接起來,如圖5所示。

Figure 5 Constructing Tyson Polygon圖5 構(gòu)造泰森多邊形

(5)將區(qū)域Ω中形成的所有泰森多邊形標(biāo)記并儲(chǔ)存入數(shù)組TP[]中，并且記錄每個(gè)泰森多邊形所對(duì)應(yīng)的頂點(diǎn)，將頂點(diǎn)儲(chǔ)存入二維數(shù)組VER[][]中，并且將關(guān)鍵節(jié)點(diǎn)KN對(duì)應(yīng)相應(yīng)的泰森多邊形和泰森多邊形頂點(diǎn)，即KN[]→TP[]→VER[][]。

(6)根據(jù)數(shù)組VER[][]在所有泰森多邊形的頂點(diǎn)部署SN，將信息儲(chǔ)存入二維數(shù)組SN[][]中，則對(duì)應(yīng)關(guān)系為KN[]→TP[]→SN[][]，當(dāng)關(guān)鍵節(jié)點(diǎn)能量耗盡或者損壞時(shí)，移動(dòng)此KN所對(duì)應(yīng)的SN予以替換。

4.2 基于節(jié)點(diǎn)數(shù)量權(quán)重比較的移動(dòng)節(jié)點(diǎn)選擇

由于多個(gè)泰森多邊形共用同一個(gè)頂點(diǎn)，故在一個(gè)頂點(diǎn)上部署的SN將負(fù)責(zé)多個(gè)KN的替換，所以如何選擇SN去替換KN是保障網(wǎng)絡(luò)流暢工作的重要任務(wù)。假設(shè)失效的KN為Ka，與其相鄰的KN節(jié)點(diǎn)分別為Kb、Kc、Kd、Ke，與Ka對(duì)應(yīng)的SN編號(hào)分別為Sa和Sb，如圖6所示。算法初始化KN[]→SN[][]信息，分別計(jì)算SN節(jié)點(diǎn)Sa占KN節(jié)點(diǎn)Kb、Kc、Kd對(duì)應(yīng)的SN數(shù)量的加權(quán)比重，SN節(jié)點(diǎn)Sb占KN節(jié)點(diǎn)Kd、Ke對(duì)應(yīng)的SN數(shù)量的加權(quán)比重。選擇SN過程可用數(shù)學(xué)公式描述為：

Figure 6 Deploying a standby node圖6 部署備用節(jié)點(diǎn)

(2)

其中,SN[i][j]表示KN[i]的備用節(jié)點(diǎn)，i=1,2,3,…;j=1,2,3,…；PROPORTIONSN[i][j]表示SN[i][j]占其對(duì)應(yīng)KN的所有備用節(jié)點(diǎn)的加權(quán)比重；KN[m]SN[i][j]表示與備用節(jié)點(diǎn)SN[i][j]對(duì)應(yīng)的所有關(guān)鍵節(jié)點(diǎn)，m=1,2,3,…;NUMSN表示求KN所對(duì)應(yīng)的SN個(gè)數(shù)的運(yùn)算。由式(2)計(jì)算出最小加權(quán)比重的SN后，移動(dòng)此備用節(jié)點(diǎn)替換失效的關(guān)鍵節(jié)點(diǎn)。最后在SN節(jié)點(diǎn)移動(dòng)去替換KN節(jié)點(diǎn)后，更新KN[]→SN[][]信息。

算法1基于泰森多邊形的優(yōu)化算法CRAST偽代碼

輸入：分區(qū)集合Seg，中繼節(jié)點(diǎn)RN通信半徑R。

輸出：需要部署的RN和SN總個(gè)數(shù)及位置信息。

1. dealQuadrilateral;

2. dealTriangle;

3.IFthere are Segs that are not connectedTHEN

4. Find the shortestedge(u,v),uinSeg1andvinSeg2;

6.ENDIF

7. Define variableNUMBERSTand put the number of relay nodes intoNUMBERST;

8. Constructing Delaunay triangle with KN;

9. Store Delaunay triangle in the arrayTRI[];

10. StoreKNin the arrayKN[];

11.FORarrayKN[]DO

12.KN[] correspond toTRI[];

13. Sort adjacent triangles and store in arrayAD[]

14.FORarrayAD[]DO

15. Construct the center of the circumscribed circle;

16.ENDFOR

17.ENDFOR

18. Connect all centers of the circumscribed circles;

19. Store the vertices of Tyson polygon into arrayVER[][];

20.FORarrayVER[][]DO

21. Deploy SN on vertices and store SN in the arraySN[][];

22.KN[] correspond toSN[][];

23.ENDFOR

24. Define variableNUMBERTPand put the number of standby nodes intoNUMBERTP;

25. Define variableNUMBERRNandNUMBERRN=NUMBERST+NUMBERTP;

26.IFKN[i] is damagedTHEN

26. ReadKN[i]→SN[i][j];

28.FORminjDO

29. Calculate the proportion ofSN[i][m] to the sum of SN numbers of all KN corresponding toSN[i][m];

30.ENDFOR

31. Compare the minimum proportion;

32. MoveSN[i][j] with minimum proportion;

33.ENDIF

34.Output variableNUMBERRN

5 仿真分析

本節(jié)采用Matlab進(jìn)行仿真實(shí)驗(yàn)，在中繼節(jié)點(diǎn)部署數(shù)量和健壯性2個(gè)方面對(duì)CRAST算法與1C-SpiderWeb算法和FeSTA算法進(jìn)行比較。由于1C-SpiderWeb算法和FeSTA算法沒有備用節(jié)點(diǎn)替換損壞節(jié)點(diǎn)的功能，1C-SpiderWeb算法和FeSTA算法在仿真前期容易因?yàn)槟硞€(gè)中繼節(jié)點(diǎn)損壞而被再次斷連，不能完整地模擬在惡劣環(huán)境中的工作表現(xiàn)，故實(shí)驗(yàn)中為1C-SpiderWeb算法和FeSTA算法配備可移動(dòng)節(jié)點(diǎn)，以保證1C-SpiderWeb算法和FeSTA算法能夠在考慮惡劣外部環(huán)境影響的仿真中完整運(yùn)行。實(shí)驗(yàn)將1C-SpiderWeb算法和FeSTA算法的中繼節(jié)點(diǎn)以每3個(gè)為1組，余下節(jié)點(diǎn)成1組進(jìn)行分組，為每組配備1個(gè)可移動(dòng)節(jié)點(diǎn)。本實(shí)驗(yàn)將傳感器網(wǎng)絡(luò)區(qū)域Ω定義為1500 m×1500 m的正方形區(qū)域，通信半徑R∈[40,120]，每20 m取值一次，Segi個(gè)數(shù)取8，9，10，實(shí)驗(yàn)在多種隨機(jī)組合的情況下取平均值，以保證實(shí)驗(yàn)結(jié)果的普遍性。

5.1 中繼節(jié)點(diǎn)數(shù)量

在處理無線傳感器網(wǎng)絡(luò)連通恢復(fù)的算法中，往往中繼節(jié)點(diǎn)數(shù)量是非常重要的一項(xiàng)指標(biāo)，在保證癱瘓網(wǎng)絡(luò)恢復(fù)連通的同時(shí)減少中繼節(jié)點(diǎn)數(shù)量是無數(shù)相關(guān)學(xué)者的主要研究方向。實(shí)驗(yàn)在3個(gè)分區(qū)數(shù)下，改變中繼節(jié)點(diǎn)通信半徑來測(cè)試CRAST算法、1C-SpiderWeb算法和FeSTA算法的高效性。

通過如圖7所示的對(duì)8個(gè)分區(qū)、9個(gè)分區(qū)和10個(gè)分區(qū)下中繼節(jié)點(diǎn)數(shù)量與通信半徑的關(guān)系對(duì)比，可以發(fā)現(xiàn)在同一分區(qū)下CRAST算法、1C-SpiderWeb算法和FeSTA算法的中繼節(jié)點(diǎn)數(shù)量隨著通信半徑的增加而減少，由于1C-SpiderWeb算法的特殊拓?fù)浣Y(jié)構(gòu)，導(dǎo)致1C-SpiderWeb算法與CRAST算法和FeSTA算法相比在分區(qū)數(shù)越多的情況下，其所需要部署的中繼節(jié)點(diǎn)越多。對(duì)比圖7可知，在中繼節(jié)點(diǎn)通信半徑R較小時(shí)，由于CRAST算法中四邊形斯坦納樹結(jié)構(gòu)和泰森多邊形結(jié)構(gòu)都能有效降低中繼節(jié)點(diǎn)數(shù)量，F(xiàn)eSTA算法所需要的中繼節(jié)點(diǎn)數(shù)量多于CRAST算法的，當(dāng)中繼節(jié)點(diǎn)通信半徑R較大時(shí)，由于CRAST算法的備用節(jié)點(diǎn)更多，CRAST算法所需要的中繼節(jié)點(diǎn)數(shù)量略多于FeSTA算法的。通過對(duì)3個(gè)算法進(jìn)行仿真實(shí)驗(yàn)，發(fā)現(xiàn)CRAST算法比1C-SpiderWeb算法具有更強(qiáng)的高效性，而在中繼節(jié)點(diǎn)通信半徑R較小時(shí),CRAST算法比FeSTA算法更高效，在中繼節(jié)點(diǎn)通信半徑R較大時(shí)FeSTA算法比CRAST算法高效。

Figure 7 Relationship between the number of relay nodes and the communication radius in different partitions圖7 不同分區(qū)數(shù)下中繼節(jié)點(diǎn)個(gè)數(shù)與通信半徑的關(guān)系

5.2 健壯性

在對(duì)癱瘓網(wǎng)絡(luò)進(jìn)行連通恢復(fù)后，保證恢復(fù)后網(wǎng)絡(luò)的健壯性同樣是衡量連通恢復(fù)算法優(yōu)異性的重要指標(biāo)。傳統(tǒng)無線傳感器網(wǎng)絡(luò)連通恢復(fù)算法由于其關(guān)鍵節(jié)點(diǎn)能耗遠(yuǎn)大于其他中繼節(jié)點(diǎn)，導(dǎo)致關(guān)鍵節(jié)點(diǎn)工作壽命遠(yuǎn)小于其他中繼節(jié)點(diǎn)，繼而導(dǎo)致恢復(fù)后的工作壽命短。本實(shí)驗(yàn)采用在8個(gè)分區(qū)、9個(gè)分區(qū)和10個(gè)分區(qū)的情況下觀察失效中繼節(jié)點(diǎn)與工作壽命之間的關(guān)系來驗(yàn)證CRAST算法、1C-SpiderWeb算法和FeSTA算法在較高故障率下的健壯性，中繼節(jié)點(diǎn)通信半徑為80 m。實(shí)驗(yàn)結(jié)果如圖8所示。

Figure 8 Working life of three algorithms in different partitions圖8 不同分區(qū)下3種算法的工作壽命

通過直方圖對(duì)比可知，由于CRAST算法針對(duì)關(guān)鍵節(jié)點(diǎn)優(yōu)化，CRAST算法的網(wǎng)絡(luò)工作壽命比1C-SpiderWeb算法和FeSTA算法的網(wǎng)絡(luò)工作壽命更長(zhǎng)，而1C-SpiderWeb算法和FeSTA算法由于關(guān)鍵中繼節(jié)點(diǎn)消耗過多能量，導(dǎo)致網(wǎng)絡(luò)的工作壽命無法達(dá)到最大化。

6 結(jié)束語

本文提出的CRAST算法旨在解決無線傳感器網(wǎng)絡(luò)由于部分中繼節(jié)點(diǎn)失效導(dǎo)致網(wǎng)絡(luò)被分割成多個(gè)分區(qū)的問題，通過構(gòu)建四邊形斯坦納樹和泰森多邊形實(shí)現(xiàn)高效且健壯的連通恢復(fù)。通過多個(gè)實(shí)驗(yàn)與1C-SpiderWeb算法和FeSTA算法進(jìn)行對(duì)比，驗(yàn)證了CRAST算法相比1C-SpiderWeb算法和FeSTA算法具有更出色的高效性和健壯性。由于本文算法是基于二維空間的算法，無法解決自然環(huán)境中非平面地形的部署，所以接下來的工作將針對(duì)三維空間的網(wǎng)絡(luò)連通恢復(fù)進(jìn)行研究，以保證在三維空間中網(wǎng)絡(luò)出現(xiàn)癱瘓后能夠及時(shí)恢復(fù)。