王志強

濟源職業(yè)技術學院，河南 濟源 459000

傳感器網(wǎng)絡作為一項影響世界的新興技術，在各領域都擁有著非常廣闊的應用前景[1]。郝占軍等人提出了WSN 三維覆蓋空洞動態(tài)修復方法，以最少的節(jié)點完成整體網(wǎng)絡覆蓋[2]。鄒增輝等人設計了一種基于可信信息覆蓋模型的覆蓋空洞檢測策略，有效確定可信信息覆蓋空洞數(shù)目和邊界信息[3]。本文采用三角形分解法[4]，利用其中三個相鄰節(jié)點所形成的三角形的邊長、角度來計算出移動節(jié)點的最佳位置，通過在該位置部署移動節(jié)點，以不斷地填充三角形區(qū)域來修補傳感器網(wǎng)絡中覆蓋空洞。

1 基于三角形信息的覆蓋空洞修補算法設計

1.1 最佳移動節(jié)點位置的幾何模型

已知節(jié)點的通信半徑為R，設B 為首個覆蓋空洞修補發(fā)起點，通過與相鄰節(jié)點的通信確定邊緣節(jié)點A 和C 的位置，并且得到∠的大小，然后通過測距算法得到AB 和BC 的長度x、y，利用上述條件進行和的求解，具體過程如下。

圖1 移動節(jié)點的最佳位置模型

如圖1 所示，過節(jié)點E 作AC邊的垂直平分線，交AC 于F 點，而節(jié)點E 和A、C 之間保持最大的通信距離。

在得到了線段BE 的長度后，在△ABE 中，利用余弦定理可得

但是在求解出來后，可能存在另一種情況，即當移動節(jié)點E 不能與邊緣節(jié)點B 進行直接通信時，為了保證B、E 兩個節(jié)點之間的正常通信與△ABE內(nèi)空洞覆蓋率，就需要限定BE 的長度不能大于節(jié)點的通信半徑R。即最終線段BE 長度f 的限制條件為，在最終BE 的長度f 確定后，可在△中求解∠的大小

1.2 PATT 算法修復空洞的流程圖

下圖為使用PATT 算法進行修補整個覆蓋空洞的具體流程：

如圖2 所示，為利用PATT 算法進行整個傳感器網(wǎng)絡覆蓋空洞修補的具體流程，需要注意的是x、y 和分別為線段AB、BC 的長度和∠ABC 的大小，邊緣節(jié)點集合由橫坐標集合和縱坐標集合其中為常數(shù)，sum 表示的是總共所增加的節(jié)點數(shù)量，初始時令sum=0，每增加一個移動節(jié)點時sum 加1，并且算出當前覆蓋空洞的覆蓋度，當整個傳感器網(wǎng)絡中的空洞覆蓋率達到90%以上時，停止修補過程。

圖2 利用PATT 算法進行覆蓋空洞修補的具體流程

2 算法仿真和分析

2.1 仿真環(huán)境設置

本文算法在matlab7.10 上進行仿真，用邊長為a 的正n 邊形作為傳感器網(wǎng)絡的覆蓋空洞模型，所有的移動節(jié)點都是隨機分布并且處于休眠狀態(tài)，但是能被其他節(jié)點喚醒，移動到指定位置。傳感器網(wǎng)絡中的節(jié)點感知半徑為r，其通信半徑R=2r。在修補覆蓋空洞的仿真實驗中，并沒有考慮各節(jié)點在通信過程中所產(chǎn)生的能量消耗。一般是選擇最近的節(jié)點移動到指定位置進行修補。

2.2 修補效果分析

首先要驗證算法的可行性，在此仿真實驗中，需要在邊長a=13m，n=15 的正十五邊形的覆蓋空洞模型下進行修補，節(jié)點的感知半徑r=7.5m,。如圖3所示，為空洞修補仿真實驗的結(jié)果。

圖3 正15 邊形的修補效果圖

由上圖可以直觀的看出本算法具有修復空洞的可行性，修補完成后，得到相關數(shù)據(jù)進行分析：sum=9，即表示使用了9 個移動節(jié)點進行了整個正十五邊形的空洞修補；=0.9256，允許存在少量的覆蓋盲區(qū)，覆蓋度符合應用要求，具有可行性。

2.3 覆蓋率驗證

覆蓋率是衡量算法可行性的重要指標。在本文算法中，覆蓋率為被覆蓋的空洞面積與覆蓋空洞總面積的比值，修復完成后的覆蓋率的計算式如下：

圖4 正25 邊形的覆蓋空洞修復效果圖

圖5 覆蓋率p 與移動節(jié)點sum 的關系

由圖5 可以看出，當放置的移動節(jié)點數(shù)量sum 增加時，覆蓋率也隨之近似線性的增大，這種近似線性的關系表明，每當在覆蓋空洞中增加一個移動節(jié)點時，其空洞面積就會減少，本文算法也起到了避免修復過程中出現(xiàn)重復覆蓋的情況，最終當節(jié)點sum=54 時，與之對應的覆蓋率=0.9216，說明了本算法能保證覆蓋率在90%以上。

2.4 穩(wěn)定性分析

為了驗證本算法具有一定的穩(wěn)定性，在邊長a不變的情況下，改變正多邊形的邊長數(shù)n，計算所需的移動節(jié)點數(shù)sum。由于改變了邊長數(shù)n，從而覆蓋空洞的面積S 也隨之改變。在此仿真實驗中，本文計算了在邊長數(shù)分別為10、15…90 的27 個正多邊形覆蓋空洞下，修復完成所需的移動節(jié)點個數(shù)，記錄下來，并以對應的覆蓋空洞面積S 的變化為橫坐標x，以完成修補所需的節(jié)點數(shù)sum 的變化為縱坐標，繪制成曲線圖進行觀察。

圖6 移動節(jié)點冗余度與覆蓋空洞面積的關系

如圖6 所示，可以看出在正多邊形邊長a 不變的情況下，當覆蓋空洞的面積S 增大時，其完成修補空洞所需的移動節(jié)點數(shù)sum 也隨著近似線性增加，表明移動節(jié)點數(shù)目增長的速度幾乎與覆蓋空洞面積增長速度相同，代表著本文算法具有很好的執(zhí)行穩(wěn)定性。

2.5 冗余度分析

在上述算法穩(wěn)定性分析的基礎上，改變正多邊形的邊長數(shù)，即得到不同覆蓋空洞面積時，使用本文算法完成整個覆蓋洞的修補后，計算其不同覆蓋面積對應的冗余度。

其中M 為完成修補所需的節(jié)點數(shù)，r 為節(jié)點的感知半徑，S 為覆蓋空洞面積。以覆蓋空洞面積S 為橫坐標，冗余度δ 為縱坐標，繪制成圖進行分析。

3 結(jié)論

本文主要針對混合傳感器網(wǎng)絡中出現(xiàn)的覆蓋空洞問題，在混合傳感器網(wǎng)絡模型中利用移動節(jié)點來修補其內(nèi)出現(xiàn)的覆蓋空洞，在修補效果上，能夠?qū)崿F(xiàn)使用較少的移動節(jié)點修補空洞，且覆蓋度大于90%，節(jié)約了節(jié)點成本。并且算法具有良好的穩(wěn)定性，不會出現(xiàn)隨著覆蓋空洞面積增大而所需移動節(jié)點數(shù)量急劇增加的情況，兩者具有一定的線性關系。但漏洞修補過程會較為復雜，使得冗余度較大，因此還需考慮所增加節(jié)點在移動過程中產(chǎn)生的能耗以及最佳的移動路徑。