陳志國，滕桂法

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

0 引言

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

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

圖1 部分覆蓋等級

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

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

1 約束條件及問題描述

1.1 約束條件

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

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

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

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

1.2 問題描述

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

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

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

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

2 GHPC 算法

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

GHPC 算法先從位于監(jiān)測區(qū)域中心位置的節(jié)點中隨機選擇一個節(jié)點加入CS 集。然后，再從它的一跳鄰居節(jié)點中選擇覆蓋貢獻(xiàn)率最大的節(jié)點加入，重復(fù)執(zhí)行，直到滿足覆蓋要求σ。

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

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

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

圖3 GHPC 算法偽代碼

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

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

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

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

3 性能仿真

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

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

3.1 實驗1

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

圖5 活動節(jié)點數(shù)（實驗1）

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

3.2 實驗2

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

圖6 活動節(jié)點數(shù)（實驗2）

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

4 結(jié)論

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

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