一種優(yōu)化無線傳感網(wǎng)絡(luò)的覆蓋算法

許道強(qiáng)，吳 波，龔 賀，范照健，陳志國

(1.國家電網(wǎng)江蘇省電力有限公司，江蘇 南京 210000; 2.福建億榕信息技術(shù)有限公司， 福建 福州 350003; 3.河北農(nóng)業(yè)大學(xué)，河北 保定 071000)

0 引 言

無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)內(nèi)的節(jié)點(diǎn)具有感知、通信和計(jì)算能力，已廣泛應(yīng)用于災(zāi)害搜救、環(huán)境監(jiān)測(cè)等其他工業(yè)應(yīng)用。這些應(yīng)用通過節(jié)點(diǎn)感測(cè)環(huán)境，并將感測(cè)數(shù)據(jù)傳輸至后臺(tái)，進(jìn)而監(jiān)測(cè)環(huán)境的目的[2]。

在WSNs內(nèi)運(yùn)用最少的傳感節(jié)點(diǎn)數(shù)覆蓋最大的監(jiān)測(cè)區(qū)域一直是WSNs的研究目標(biāo)。文獻(xiàn)[3]分析了三維隨機(jī)覆蓋連通問題，旨在以最少的節(jié)點(diǎn)數(shù)實(shí)現(xiàn)對(duì)監(jiān)測(cè)區(qū)域100%的覆蓋。而文獻(xiàn)[4]研究了基于三維晶格模型的局部覆蓋問題。

不同的應(yīng)用對(duì)覆蓋要求并不相同。有些應(yīng)用要求對(duì)監(jiān)測(cè)區(qū)域?qū)崿F(xiàn)100%覆蓋。而多數(shù)應(yīng)用，并不需要對(duì)監(jiān)測(cè)區(qū)域有100%的覆蓋，只需要局部覆蓋[4]，如圖1所示。A區(qū)、B區(qū)、C區(qū)、D區(qū)對(duì)覆蓋率的要求并不相同, 如D區(qū)對(duì)覆蓋要求最高,達(dá)到90%。相比于D區(qū), A區(qū)、B區(qū)、C區(qū)對(duì)覆蓋要求較低, 分別為80%、60%和50%。

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

此外，WSNs一般由海量傳感節(jié)點(diǎn)構(gòu)成。這些節(jié)點(diǎn)可能存在一些特性差異。即使是同類型的傳感節(jié)點(diǎn), 也可能因故障原因呈現(xiàn)不同特性。因此, 多數(shù)WSNs表現(xiàn)出異構(gòu)特性。為此, 本文以異構(gòu)WSNs為研究對(duì)象, 分析異構(gòu)WSNs的局部覆蓋問題[5-7]。

文獻(xiàn)[8]提出分布式的局部覆蓋(Distributed Algorithm for Partial Coverage, DAPC)算法。在DAPC算法中，每個(gè)傳感節(jié)點(diǎn)無需任何地理位置信息尋找冗余節(jié)點(diǎn)，并將這些冗余節(jié)點(diǎn)進(jìn)入休眠狀態(tài)。而文獻(xiàn)[9]引用連通支配集(Connected Dominating Set, CDS)概念。利用構(gòu)建CDS實(shí)現(xiàn)區(qū)域覆蓋。文獻(xiàn)[10]引用學(xué)習(xí)自動(dòng)機(jī)分配活動(dòng)節(jié)點(diǎn)和休眠節(jié)點(diǎn)，進(jìn)而滿足部分覆蓋要求。然而，這些算法從局部覆蓋角度討論網(wǎng)絡(luò)覆蓋問題，同時(shí)，它們是以同構(gòu)網(wǎng)絡(luò)為研究對(duì)象。

為此，針對(duì)異構(gòu)網(wǎng)絡(luò)，提出概率模型的局部覆蓋算法(Probability-based Partial Coverage, PPC)。PPC算法先計(jì)算傳感節(jié)點(diǎn)的覆蓋冗余度，再依據(jù)節(jié)點(diǎn)覆蓋冗余度和對(duì)監(jiān)測(cè)區(qū)域的覆蓋面積，選擇節(jié)點(diǎn)加入覆蓋集。然后，覆蓋集內(nèi)的節(jié)點(diǎn)滿足局部覆蓋。仿真數(shù)據(jù)表明，提出的PPC算法能夠以最少的節(jié)點(diǎn)數(shù)，滿足覆蓋要求。

1 約束條件及問題描述

將WSNs覆蓋區(qū)域進(jìn)行二維平面處理。令Ci和Ri分別表示第i個(gè)傳感節(jié)點(diǎn)Si的通信半徑、感測(cè)半徑。一般感測(cè)半徑大于通信半徑。假定傳感節(jié)點(diǎn)的通信區(qū)域和感測(cè)區(qū)域呈圓形[11]。

依據(jù)傳感節(jié)點(diǎn)的通信半徑和感測(cè)半徑的不同, 將網(wǎng)絡(luò)內(nèi)N個(gè)節(jié)點(diǎn)劃分t個(gè)類型。第i類傳感節(jié)點(diǎn)表示為Si, 它的通信半徑、感測(cè)半徑分別表示為ri和Ri, 且1≤i≤t。

節(jié)點(diǎn)Si的感測(cè)區(qū)域表示為A(si,Ri)。A(si,Ri)表示以節(jié)點(diǎn)Si的位置si為圓心以Ri為半徑的圓。節(jié)點(diǎn)Si不能感測(cè)A(si,Ri)區(qū)域的事件。類似地, 節(jié)點(diǎn)Si的通信區(qū)域也可表示為A(si,Ci)。

定義1: 在異構(gòu)WSN內(nèi), 任意兩個(gè)傳感節(jié)點(diǎn)Si和Sj, 且1≤i,j≤t,?{i≠j}, 則Ci≠Cj,Ri≠Rj。

dij≤min(Ci,Cj)

(1)

其中(xi,yi)、(xj,yj)分別表示節(jié)點(diǎn)Si、Sj的二維坐標(biāo)。

定義3: 如果節(jié)點(diǎn)感測(cè)區(qū)域內(nèi)的局部區(qū)域的某點(diǎn)被不止一個(gè)節(jié)點(diǎn)覆蓋, 則說該節(jié)點(diǎn)存在局部覆蓋冗余。令ξi表示節(jié)點(diǎn)Si的覆蓋冗余率, 其等于它鄰居節(jié)點(diǎn)覆蓋的區(qū)域面積與它自己覆蓋區(qū)域面積之比。

2 PPC算法

為了選擇合適的節(jié)點(diǎn)加入覆蓋集, 利用概率模型估計(jì)節(jié)點(diǎn)Si的覆蓋冗余度。并選擇覆蓋冗余度最低的節(jié)點(diǎn)加入覆蓋集, 其他沒選擇的節(jié)點(diǎn)進(jìn)行休眠, 進(jìn)而以最少的節(jié)點(diǎn)實(shí)現(xiàn)目標(biāo)的局部覆蓋。

2.1 點(diǎn)的冗余覆蓋

考慮節(jié)點(diǎn)Si的感測(cè)區(qū)域A(si,Ri), 如圖2所示。令Y為一個(gè)隨機(jī)變量, 其表示區(qū)域位置X離si的位置變量[12]。其中位置X離si的距離為x, 且0≤x≤Ri。因此, 變量Y概率密度函數(shù)可表示為:

fY(x)=2x/(Ri)2

(2)

圖2 節(jié)點(diǎn)Si及Sj的感測(cè)和通信區(qū)域示意圖

令pij(x)表示位置X被鄰居節(jié)點(diǎn)Sj覆蓋的概率。若X∈A(si,Ri)能被鄰居節(jié)點(diǎn)Sj覆蓋, 則節(jié)點(diǎn)Sj離位置X的距離大于Rj。

結(jié)合圖1, 可推導(dǎo)pij值, 如式(3)所示:

(3)

依據(jù)式(3)可知,pij(x)值取決于位置X、si和min(Ci,Cj)。對(duì)于特定的一對(duì)鄰居節(jié)點(diǎn)Si和Sj, 它們的有效通信區(qū)域A(si,min(Ci,Cj))是常數(shù)。

2.2 覆蓋冗余度

(4)

其中nij表示節(jié)點(diǎn)Si具有j類型的鄰居節(jié)點(diǎn)數(shù)。

P(Di(X))=1-(1-pi1(x))ni1…(1-pit(x))nit=

(5)

利用積分, 計(jì)算P(Di(X))的期望值:

(6)

而節(jié)點(diǎn)Si的覆蓋冗余度ξi的期望值E[ξi]可表示為:

(7)

將式(5)代入式(8)可得:

酒店使用社交媒體營銷的目的。調(diào)查結(jié)果顯示：社交媒體營銷人員使用社交媒體營銷時(shí)，最關(guān)注的是提高品牌知名度、提供產(chǎn)品信息和了解消費(fèi)者需求。超過一半的酒店媒體高管認(rèn)為社交媒體不應(yīng)成為酒店創(chuàng)收的工具，而應(yīng)成為酒店產(chǎn)品信息的宣傳窗口。此外，有4家酒店提到招聘員工是他們使用社交媒體的另一目的。

(8)

2.3 覆蓋集

提出PPC算法旨在: 以最少的節(jié)點(diǎn)數(shù)滿足局部覆蓋要求。為此,PPC算法從覆蓋冗余度擇優(yōu)選擇傳感節(jié)點(diǎn)加入覆蓋集。

首先, 隨機(jī)選擇一個(gè)傳感節(jié)點(diǎn)加入覆蓋集，然后再從該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇覆蓋冗余度最低的節(jié)點(diǎn)加入覆蓋集[13], 重復(fù)執(zhí)行, 直到滿足局部覆蓋要求。

先隨機(jī)選擇一個(gè)傳感節(jié)點(diǎn)Sk加入覆蓋集Φ。令Nk表示節(jié)點(diǎn)Sk的一跳鄰居節(jié)點(diǎn)集; 再計(jì)算Nk內(nèi)節(jié)點(diǎn)的覆蓋冗余度，并選擇覆蓋冗余度低的節(jié)點(diǎn)加入Φ, 如式(9)所示:

Φ=Φ∪Si

(9)

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

再檢測(cè)Φ內(nèi)節(jié)點(diǎn)的覆蓋區(qū)域是否滿足局部覆蓋要求? 。如果滿足要求, 就停止向覆蓋集內(nèi)添加節(jié)點(diǎn)。否則, 就從Φ內(nèi)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇覆蓋冗余度和對(duì)監(jiān)測(cè)區(qū)域覆蓋面積大的節(jié)點(diǎn)加入覆蓋集。從Φ內(nèi)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中選擇節(jié)點(diǎn)加入覆蓋集, 能夠保持網(wǎng)絡(luò)的連通性。

以圖3為例闡述構(gòu)建局部覆蓋集的過程。圖3(a)為網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。假定選擇節(jié)點(diǎn)5加入覆蓋集。而節(jié)點(diǎn)2,4,8,9,6是節(jié)點(diǎn)5的鄰居節(jié)點(diǎn)。而節(jié)點(diǎn)4覆蓋區(qū)域的面積最大。因此, 選擇節(jié)點(diǎn)4加入Φ。

圖3 PPC算法構(gòu)建覆蓋集示例

Φ={4,5}內(nèi)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)為{1,2,8,9,6}。再從{1,2,8,9,6}中選擇覆蓋冗余度低和覆蓋面積大的節(jié)點(diǎn)加入Φ。而節(jié)點(diǎn)8的覆蓋面積大,且覆蓋冗余度低。因此, 節(jié)點(diǎn)8加入覆蓋集。如圖3(c)所示。再將節(jié)點(diǎn)1加入覆蓋集。最后, 將節(jié)點(diǎn)6加入覆蓋集。選擇節(jié)點(diǎn)6的原因在于:盡管節(jié)點(diǎn)2, 6, 9的覆蓋面積相同, 但是節(jié)點(diǎn)2和節(jié)點(diǎn)9的覆蓋冗余度高于節(jié)點(diǎn)6。

3 性能仿真

表1 兩類傳感器節(jié)點(diǎn)參數(shù)

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

本次實(shí)驗(yàn)分析不同類型的節(jié)點(diǎn)數(shù)對(duì)覆蓋集內(nèi)節(jié)點(diǎn)數(shù)的影響。為了簡(jiǎn)化描述，將覆蓋集內(nèi)的節(jié)點(diǎn)稱為覆蓋節(jié)點(diǎn)。在滿足局部覆蓋要求u條件下，覆蓋節(jié)點(diǎn)數(shù)越少，性能越好。

圖4顯示了m1∶m2=0∶1和m1∶m2=1∶3兩種情況下的覆蓋節(jié)點(diǎn)數(shù)。從圖4可知，覆蓋要求u越高，所需的覆蓋節(jié)點(diǎn)數(shù)越多。例如，在u=0.6時(shí)所需的覆蓋節(jié)點(diǎn)數(shù)低于u=0.95。

圖4 活動(dòng)節(jié)點(diǎn)數(shù)

此外，對(duì)比圖4(a)和4(b)可知，在m1∶m2=1∶3網(wǎng)絡(luò)環(huán)境下所需的覆蓋節(jié)點(diǎn)數(shù)大于m1∶m2=0∶1網(wǎng)絡(luò)環(huán)境下的覆蓋節(jié)點(diǎn)數(shù)。原因在于：第二類傳感節(jié)點(diǎn)的感測(cè)半徑大于第一類傳感節(jié)點(diǎn)的感測(cè)半徑。相比于m1∶m2=0∶1,m1∶m2=1∶3網(wǎng)絡(luò)環(huán)境下的第二類傳感節(jié)點(diǎn)更少。因此，它需要更多的傳感節(jié)點(diǎn)加入覆蓋集，進(jìn)而滿足覆蓋要求。

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

本次實(shí)驗(yàn)進(jìn)行對(duì)比分析，選擇DAPC、CDS和PCLA算法作為參照。實(shí)驗(yàn)參數(shù)：100個(gè)節(jié)點(diǎn)分布于100 m×100 m。并考慮m1∶m2=1∶0和m1∶m2=0∶1這兩種情況。m1∶m2=1∶0意味著100個(gè)節(jié)點(diǎn)全是第一類節(jié)點(diǎn)；而m1∶m2=0∶1意味著100個(gè)節(jié)點(diǎn)全是第二類節(jié)點(diǎn)。由于這兩類節(jié)點(diǎn)的通信半徑和感測(cè)半徑不同，通過對(duì)比分析這兩種情況下的覆蓋性能，可獲取通信半徑和感測(cè)半徑對(duì)覆蓋性能的影響。

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

從圖5可知，提出的PPC算法所需的覆蓋節(jié)點(diǎn)數(shù)優(yōu)于DAPC、CDS和PCLA算法。原因在于：PPC算法通過覆蓋冗余度和對(duì)監(jiān)測(cè)區(qū)域的覆蓋面積選擇節(jié)點(diǎn)加入覆蓋集，進(jìn)而能夠以最少的節(jié)點(diǎn)數(shù)覆蓋監(jiān)測(cè)區(qū)域。

此外，對(duì)比圖5(a)和5(b)不難發(fā)現(xiàn)，m1∶m2=0∶1情況下所需的覆蓋節(jié)點(diǎn)數(shù)少于m1∶m2=1∶0情況。原因在于：第二類傳感節(jié)點(diǎn)的感測(cè)半徑大于第一類傳感節(jié)點(diǎn)。

4 結(jié) 語

針對(duì)異構(gòu)WSNs網(wǎng)絡(luò)的局部覆蓋問題，提出基于概率模型的局部覆蓋算法PPC。PPC算法先利用概率模型估計(jì)傳感節(jié)點(diǎn)覆蓋冗余度，再通過覆蓋冗余度擇優(yōu)選擇節(jié)點(diǎn)，將這些節(jié)點(diǎn)加入覆蓋集。并由覆蓋集內(nèi)節(jié)點(diǎn)覆蓋監(jiān)測(cè)區(qū)域。實(shí)現(xiàn)數(shù)據(jù)表明，提出的PPC算法降低了覆蓋集內(nèi)節(jié)點(diǎn)數(shù)。

本文只研究WSNs的局部覆蓋問題，旨在以最少的傳感節(jié)點(diǎn)覆蓋監(jiān)測(cè)區(qū)域。但是，并沒有分析PPC算法的復(fù)雜度以及節(jié)點(diǎn)能耗問題。這將是后期的工作方向。