傳感器網(wǎng)絡(luò)的修補算法仿真與性能分析

王志強

濟(jì)源職業(yè)技術(shù)學(xué)院，河南 濟(jì)源 459000

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

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

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

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

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

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

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

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

1.2 PATT 算法修復(fù)空洞的流程圖

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

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

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

2 算法仿真和分析

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

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

2.2 修補效果分析

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

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

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

2.3 覆蓋率驗證

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

圖4 正25 邊形的覆蓋空洞修復(fù)效果圖

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

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

2.4 穩(wěn)定性分析

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

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

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

2.5 冗余度分析

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

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

3 結(jié)論

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