采用貪婪啟發(fā)式的異構(gòu)WSNs 部分覆蓋算法*

陳志國(guó)，滕桂法

（河北農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，河北 保定 071000）

0 引言

無(wú)線傳感網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）由多個(gè)微型傳感節(jié)點(diǎn)構(gòu)成［1］，其廣泛應(yīng)用于事件檢測(cè)，如入侵檢測(cè)、危險(xiǎn)區(qū)域檢測(cè)等。利用WSNs 中的節(jié)點(diǎn)感測(cè)環(huán)境，再將感測(cè)數(shù)據(jù)傳輸至控制中心，進(jìn)而實(shí)現(xiàn)對(duì)環(huán)境的監(jiān)測(cè)目的［2-3］。

在監(jiān)測(cè)區(qū)域部署WSNs 的目的在于監(jiān)測(cè)目標(biāo)區(qū)域的異常情況，如森林防火檢測(cè)。這就要求監(jiān)測(cè)區(qū)域被節(jié)點(diǎn)覆蓋或者滿足監(jiān)測(cè)區(qū)域的覆蓋要求［3］。若出現(xiàn)覆蓋空洞區(qū)域或覆蓋要求不能滿足，就可能會(huì)出現(xiàn)對(duì)異常情況的漏檢。覆蓋要求是指針對(duì)不同應(yīng)用環(huán)境，對(duì)監(jiān)測(cè)區(qū)域的覆蓋面積有不同要求。因?yàn)橛行?yīng)用并非要求100%覆蓋（全覆蓋），只需部分區(qū)域覆蓋，即部分覆蓋［4］。如圖1 所示，4 個(gè)不同監(jiān)測(cè)區(qū)域的覆蓋要求并不同，如A 區(qū)域的覆蓋要求為80%，而B(niǎo) 區(qū)域要求60%。

圖1 部分覆蓋等級(jí)

同時(shí)，通常WSNs 是由大量的微型傳感節(jié)點(diǎn)構(gòu)成，這些節(jié)點(diǎn)可能存在一些特性不同。即使是同類傳感節(jié)點(diǎn)，也可能因硬件故障問(wèn)題而表現(xiàn)出不同的特性。因此，本文討論的對(duì)象是異構(gòu)WSNs 的部分覆蓋問(wèn)題［5-7］。在異構(gòu)WSNs 中，傳感節(jié)點(diǎn)具有不同的感測(cè)和通信范圍。

為此，本文提出基于貪婪啟發(fā)式的部分覆蓋（Greedy Heuristic -based Partial Coverage ，GHPC）算法。GHPC 算法引用貪婪啟發(fā)式算法，并通過(guò)覆蓋冗余概念選擇節(jié)點(diǎn)，再利用這些節(jié)點(diǎn)滿足部分覆蓋要求。選擇覆蓋貢獻(xiàn)率大的節(jié)點(diǎn)感測(cè)環(huán)境，這有兩個(gè)原因：1）選擇覆蓋貢獻(xiàn)率大的節(jié)點(diǎn)，可以用更少的節(jié)點(diǎn)滿足覆蓋要求；2）保持節(jié)點(diǎn)連通，降低了能耗。本文的主要工作在于：1）對(duì)異構(gòu)WSNs 的部分覆蓋問(wèn)題進(jìn)行了形式表述；2）用貪婪啟發(fā)式算法求解；3）建立仿真平臺(tái)分析算法性能。

1 約束條件及問(wèn)題描述

1.1 約束條件

假定N 個(gè)節(jié)點(diǎn)隨機(jī)分布于L×W 的區(qū)域A 內(nèi)，且這些節(jié)點(diǎn)分為m 類，每類節(jié)點(diǎn)具有不同的感測(cè)半徑和通信半徑［8］。Ri、Ci分別表示節(jié)點(diǎn)Si的感測(cè)半徑、通信半徑。因此，不同類節(jié)點(diǎn)的通信和感測(cè)區(qū)域不同。圖2 顯示了不同類的節(jié)點(diǎn)Si和Sj的通信和感測(cè)區(qū)域。通常，感測(cè)半徑大于通信半徑。

圖2 不同節(jié)點(diǎn)的感測(cè)和通信區(qū)域

此外，如果節(jié)點(diǎn)Si在節(jié)點(diǎn)Sj的通信范圍內(nèi)，則節(jié)點(diǎn)Si能與節(jié)點(diǎn)Sj通信，反之亦然。同時(shí)，若節(jié)點(diǎn)Si與Sj的歐氏距離小于Ri，則節(jié)點(diǎn)Si與節(jié)點(diǎn)Sj有覆蓋重疊［9］。用σ 表示部分覆蓋率。若σ=100，則100%覆蓋。σ 等于覆蓋面積與總的監(jiān)測(cè)區(qū)域面積之比。

為了降低網(wǎng)絡(luò)能耗，每個(gè)節(jié)點(diǎn)具有空閑和激活兩種狀態(tài)［10］。若節(jié)點(diǎn)未被選擇去覆蓋（激活），則進(jìn)入休眠。

1.2 問(wèn)題描述

GHPC 算法的目的在于：從N 個(gè)節(jié)點(diǎn)中選擇部分節(jié)點(diǎn)進(jìn)行工作，即加入覆蓋集（Cover Set，CS），并由這些節(jié)點(diǎn)覆蓋監(jiān)測(cè)區(qū)域，進(jìn)而滿足覆蓋要求。

先定義覆蓋冗余變量ρij，其表示節(jié)點(diǎn)Si與節(jié)點(diǎn)Sj是否存在覆蓋重疊，定義如式（1）所示。

再定義二值變量γi，其表示節(jié)點(diǎn)Si是否加入了CS。如果節(jié)點(diǎn)Si加入CS，則γi值為1，否則為零，如式（2）所示：

因此，GHPC 算法需解決的問(wèn)題可形式化表述，如式（3）所示：

2 GHPC 算法

GHPC 算法要解決的問(wèn)題就是如何從N 個(gè)節(jié)點(diǎn)中選擇n 個(gè)節(jié)點(diǎn)滿足式（3）。然而，文獻(xiàn)［12］已分析證實(shí)式（3）是NP 問(wèn)題。為此，GHPC 算法引用貪婪啟發(fā)式算法求解。

GHPC 算法先從位于監(jiān)測(cè)區(qū)域中心位置的節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)加入CS 集。然后，再?gòu)乃囊惶従庸?jié)點(diǎn)中選擇覆蓋貢獻(xiàn)率最大的節(jié)點(diǎn)加入，重復(fù)執(zhí)行，直到滿足覆蓋要求σ。

具體而言，首先，從監(jiān)測(cè)區(qū)域中心隨機(jī)選擇節(jié)點(diǎn)為Sk，即Sk→CS。Mk表示節(jié)點(diǎn)Sk的一跳鄰居節(jié)點(diǎn)。然后，計(jì)算Mk內(nèi)每個(gè)節(jié)點(diǎn)的覆蓋貢獻(xiàn)率，再選擇覆蓋貢獻(xiàn)率最大的節(jié)點(diǎn)加入CS，如式（5）所示：

其中，|Mk|表示Mk內(nèi)節(jié)點(diǎn)個(gè)數(shù)。

然后，再判斷CS 內(nèi)節(jié)點(diǎn)的覆蓋區(qū)域是否滿足部分覆蓋要求σ，如果滿足，則停止；否則繼續(xù)向CS添加節(jié)點(diǎn)，直到滿足部分覆蓋要求。

圖3 GHPC 算法偽代碼

GHPC 算法是利用貪婪啟發(fā)式算法構(gòu)建CS。多數(shù)情況是在監(jiān)測(cè)區(qū)域內(nèi)密集部署傳感節(jié)點(diǎn)，因此，可建立多個(gè)CS。GHPC 算法的偽代碼如圖3 所示。

圖4 顯示GHPC 算法構(gòu)建CS 的示例。圖4 中有10 個(gè)節(jié)點(diǎn)，且這10 個(gè)節(jié)點(diǎn)分為兩類，這兩類節(jié)點(diǎn)的覆蓋半徑不同。圖4（a）顯示這10 個(gè)節(jié)點(diǎn)分布情況。

圖4 GHPC 算法構(gòu)建CS 示例

首先，先選擇覆蓋貢獻(xiàn)率最大的節(jié)點(diǎn)。從圖4可知，節(jié)點(diǎn)5 具有這種特性，因此，節(jié)點(diǎn)5 作為首選節(jié)點(diǎn)加入CS，如圖4（b）所示。然后，節(jié)點(diǎn)2、4、6、8和9 作為第2 輪加入CS 的候選節(jié)點(diǎn)，原因在于：1）它們能夠提高覆蓋率；2）它們是節(jié)點(diǎn)5 的鄰居節(jié)點(diǎn)，選擇它們可以保證網(wǎng)絡(luò)連通率。在這些節(jié)點(diǎn)中，再計(jì)算各自的覆蓋貢獻(xiàn)率，選擇具有覆蓋貢獻(xiàn)率最大的節(jié)點(diǎn)加入，節(jié)點(diǎn)4 具有這種特性。因此，節(jié)點(diǎn)4 加入CS，如圖4（c）所示。依次類推，節(jié)點(diǎn)8、節(jié)點(diǎn)1和節(jié)點(diǎn)6 分別加入CS，進(jìn)而滿足部分覆蓋要求。

3 性能仿真

為了更好地分析GHPC 算法的性能，利用NS-2.34 軟件建立仿真平臺(tái)［13］。N 個(gè)傳感節(jié)點(diǎn)分布于100 m×100 m 內(nèi)。考慮兩類節(jié)點(diǎn)（m=2），且第1類節(jié)點(diǎn)的感測(cè)半徑為15 m，通信半徑為15 m，而第2 類節(jié)點(diǎn)，感測(cè)半徑為18 m，通信半徑為20 m。此外，考慮3 類部分覆蓋要求（σ=0.95，0.80，0.60）。

第1 類節(jié)點(diǎn)感測(cè)半徑與通信半徑相同，而第2類節(jié)點(diǎn)不同。若N 個(gè)節(jié)點(diǎn)內(nèi)第1 類節(jié)點(diǎn)數(shù)越多，網(wǎng)絡(luò)同構(gòu)性越高。假定第1 類節(jié)點(diǎn)數(shù)與第2 類節(jié)點(diǎn)數(shù)的比例為m1∶m2。如果N=100，若m1∶m2=1∶1，則第1 類、第2 類節(jié)點(diǎn)各為50 個(gè)。

3.1 實(shí)驗(yàn)1

首先分析節(jié)點(diǎn)數(shù)對(duì)活動(dòng)節(jié)點(diǎn)數(shù)的影響。所謂活動(dòng)節(jié)點(diǎn)數(shù)就是指CS 內(nèi)的節(jié)點(diǎn)數(shù)。顯然，在滿足部分覆蓋要求情況下，活動(dòng)節(jié)點(diǎn)數(shù)越小，性能越好。圖5分別顯示了m1∶m2=1∶1 和m1∶m2=1∶3 兩種情況下的活動(dòng)節(jié)點(diǎn)數(shù)。

圖5 活動(dòng)節(jié)點(diǎn)數(shù)（實(shí)驗(yàn)1）

從圖5 可知，σ 越高，活動(dòng)節(jié)點(diǎn)數(shù)越多。原因在于需要更多的節(jié)點(diǎn)滿足更高的σ 要求。此外，節(jié)點(diǎn)數(shù)N 的增加對(duì)活動(dòng)節(jié)點(diǎn)數(shù)的影響并不大，活動(dòng)節(jié)點(diǎn)數(shù)主要取決于部分覆蓋要求σ。將圖5（a）與圖5（b）對(duì)比，發(fā)現(xiàn)第2 類節(jié)點(diǎn)數(shù)的增加，降低了活動(dòng)節(jié)點(diǎn)數(shù)，原因在于：第2 類節(jié)點(diǎn)的感測(cè)半徑大于第1 類節(jié)點(diǎn)。這樣的節(jié)點(diǎn)越多，越容易滿足覆蓋要求。

3.2 實(shí)驗(yàn)2

本次實(shí)驗(yàn)對(duì)比分析，選擇PCP［14］和CCP［15］作為參照。600 個(gè)節(jié)點(diǎn)隨機(jī)分布于100 m×100 m 內(nèi)。圖6 分別顯示了在m1∶m2=1∶0 和m1∶m2=0∶1兩種情況下，各自算法的活動(dòng)節(jié)點(diǎn)數(shù)。

圖6 活動(dòng)節(jié)點(diǎn)數(shù)（實(shí)驗(yàn)2）

從圖6 可知，部分覆蓋要求σ 的增加提高了活動(dòng)節(jié)點(diǎn)數(shù)。與PCP、CCP 算法相比，提出的GHPC 算法能夠有效地降低活動(dòng)節(jié)點(diǎn)數(shù)。此外，對(duì)比分析m1∶m2=1∶0 和m1∶m2=0∶1 兩種情況，不難發(fā)現(xiàn)：前者所需的活動(dòng)節(jié)點(diǎn)降低。原因在于m1∶m2=1∶0 表明600 個(gè)節(jié)點(diǎn)全是第1 類節(jié)點(diǎn)，即同構(gòu)網(wǎng)絡(luò)，而后者m1∶m2=0∶1，盡管全是第2 類節(jié)點(diǎn)，但它們的通信半徑和感測(cè)半徑并不相同。這不利于降低活動(dòng)節(jié)點(diǎn)數(shù)。這主要是因?yàn)椋涸诒ＷC網(wǎng)絡(luò)覆蓋率的同時(shí)，也需要滿足網(wǎng)絡(luò)連通率。

4 結(jié)論

針對(duì)異構(gòu)WSNs 部分覆蓋問(wèn)題進(jìn)行研究，先對(duì)部分覆蓋問(wèn)題進(jìn)行形式化表述，然后再利用貪婪啟發(fā)式算法求解，實(shí)現(xiàn)以最少的節(jié)點(diǎn)數(shù)滿足覆蓋要求。通過(guò)實(shí)驗(yàn)分析可知，提出的GHPC 算法能夠以少的節(jié)點(diǎn)數(shù)滿足覆蓋要求。

本文是在給定的覆蓋要求條件下，利用貪婪啟發(fā)式算法部署傳感節(jié)點(diǎn)。然而，本文并沒(méi)有考慮到網(wǎng)絡(luò)能耗問(wèn)題，也沒(méi)有分析同構(gòu)網(wǎng)絡(luò)與異構(gòu)網(wǎng)絡(luò)的能耗差異。這將是后期的工作方向。此外，傳感節(jié)點(diǎn)的部署問(wèn)題是一個(gè)NP 問(wèn)題，屬系統(tǒng)優(yōu)化問(wèn)題。而自動(dòng)學(xué)習(xí)機(jī)算法能夠有效地處理優(yōu)化問(wèn)題。自動(dòng)學(xué)習(xí)機(jī)在節(jié)點(diǎn)部署方面的應(yīng)用將是今后分析研究的重點(diǎn)。