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

王志強(qiáng)

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

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

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

1.1 最佳移動(dòng)節(jié)點(diǎn)位置的幾何模型

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

圖1 移動(dòng)節(jié)點(diǎn)的最佳位置模型

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

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

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

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

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

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

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

2 算法仿真和分析

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

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

2.2 修補(bǔ)效果分析

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

圖3 正15 邊形的修補(bǔ)效果圖

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

2.3 覆蓋率驗(yàn)證

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

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

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

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

2.4 穩(wěn)定性分析

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

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

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

2.5 冗余度分析

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

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

3 結(jié)論

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