k重覆蓋設(shè)置算法的百分比覆蓋研究*

費 娟,劉桂英,劉 瑤

(嶺南師范學(xué)院信息工程學(xué)院,廣東 湛江 524048)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)由大量的傳感器節(jié)點自組織網(wǎng)絡(luò)而構(gòu)成,已廣泛應(yīng)用于軍事應(yīng)用,環(huán)境科學(xué),醫(yī)療健康,空間探索,家庭安保等領(lǐng)域[1]。由于節(jié)點的電源能量受限,在網(wǎng)絡(luò)覆蓋質(zhì)量得到保障的前提下,如何高效地利用有限的能量資源,最大化地延長網(wǎng)絡(luò)的生命期一直是無線傳感器網(wǎng)絡(luò)的一個重要研究方向。延長無線傳感器網(wǎng)絡(luò)的生命期主要有以下幾種辦法:①優(yōu)化網(wǎng)絡(luò)工作方式[2];②對通信數(shù)據(jù)進(jìn)行壓縮聚合等處理[3];③優(yōu)化拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)路由[4];④優(yōu)化匯聚節(jié)點(Sink node)部署[5];⑤移動充電等新技術(shù)[6]。k重覆蓋設(shè)置(SETk-cover)通過優(yōu)化網(wǎng)絡(luò)工作方式,對無線傳感器網(wǎng)絡(luò)的覆蓋集進(jìn)行睡眠調(diào)度,來達(dá)到降低網(wǎng)絡(luò)干擾,提升網(wǎng)絡(luò)生命期的目的。

針對無線傳感器網(wǎng)絡(luò)高密度隨機節(jié)點部署所帶來的冗余性問題,研究人員提出以節(jié)點覆蓋集輪流工作休眠的方式來實現(xiàn)節(jié)能、抗干擾的目的。SETk-cover 算法從部署節(jié)點集合中找出k組互不相關(guān)的節(jié)點子集,每個子集均可獨立完成對網(wǎng)絡(luò)的通信覆蓋,子集間輪流工作,其他子集處于低功耗的睡眠狀態(tài),通過這樣的方式可將網(wǎng)絡(luò)的生命期延長至大約k倍。當(dāng)前SETk-cover問題的研究大多基于子集對網(wǎng)絡(luò)的區(qū)域覆蓋,要求目標(biāo)區(qū)域中的每一點要被節(jié)點完全覆蓋,而完全覆蓋在實際應(yīng)用中有時是不可實現(xiàn)或者不必要的:一方面,SETk-cover適用于隨機高密度節(jié)點部署場景,而隨機部署很難保證投擲出去的節(jié)點能夠覆蓋到目標(biāo)區(qū)域的每一寸角落,同時網(wǎng)絡(luò)工作過程中會不斷的出現(xiàn)故障節(jié)點以及能量耗盡的節(jié)點,這進(jìn)一步增加了完全覆蓋的難度;另一方面,某些應(yīng)用場景并不需要完全覆蓋,如環(huán)境監(jiān)測、天氣預(yù)報、智慧農(nóng)業(yè)等。有學(xué)者提出部分覆蓋[7](partial coverage)和百分比覆蓋[8](percentage coverage)的概念,其目的是在滿足監(jiān)測百分比精度要求的情況下,令更多的節(jié)點進(jìn)入休眠狀態(tài),從而保存能量,延長網(wǎng)絡(luò)的生命期。

針對SETk-cover的研究始于本世紀(jì)初,文獻(xiàn)[9]提出了一種基于貪婪算法的啟發(fā)式算法MCMCC,用于解決高密度隨機部署中冗余節(jié)點的覆蓋集輪流調(diào)度問題,SETk-cover的概念首次被提出。此后,學(xué)者們陸續(xù)提出用不同的算法來解決SETk-cover問題,如整數(shù)規(guī)劃算法[10]、Memetic算法[11]、遺傳算法[12]、蟻群算法[13]、N人紙牌游戲算法[14]、時變對數(shù)線性學(xué)習(xí)算法[15]等,研究者們在SETk-cover問題上給予了持續(xù)的關(guān)注,但是研究成果多針對算法本身,對于實際應(yīng)用中可能會遇到的一些實際問題缺少后續(xù)跟蹤研究。部分覆蓋、百分比覆蓋的概念提出后,有不少研究者致力于通過研究部分覆蓋來進(jìn)一步提升網(wǎng)絡(luò)的生命期,但是這種研究一般只是針對一個子集覆蓋的研究,鮮有將部分覆蓋應(yīng)用于SETk-cover中的研究。SETk-cover的研究文獻(xiàn)[9-15]均基于區(qū)域覆蓋的全覆蓋,覆蓋的判定通常采用傳感區(qū)域劃分法和網(wǎng)格法,若采用傳感區(qū)域劃分法進(jìn)行百分比覆蓋研究,將會給網(wǎng)絡(luò)建模帶來很大的困難,而對于網(wǎng)格法,對目標(biāo)區(qū)域的百分比覆蓋可以轉(zhuǎn)化為網(wǎng)格頂點被覆蓋的百分比,覆蓋的分析建模將比較方便。文獻(xiàn)[12]采用了網(wǎng)格法進(jìn)行網(wǎng)絡(luò)的覆蓋,本文對文獻(xiàn)[12]的算法進(jìn)行改進(jìn),提出一種以覆蓋和生命期為目標(biāo)的SETk-cover算法,以網(wǎng)絡(luò)子集的連通度作為約束條件,要求節(jié)點子集在保證連通度的前提下,滿足給定的百分比覆蓋目標(biāo)。

1 系統(tǒng)模型及問題描述

1.1 感知模型

節(jié)點的感知模型是研究無線傳感器網(wǎng)絡(luò)覆蓋性問題的基礎(chǔ),通常分為確定型和概率型兩類,最常見的布爾模型(Boolean sensing model)屬于確定型感知模型,概率型感知模型則包含了考慮障礙物等地理面貌的Shadow-fading模型,以及考慮目標(biāo)探測點和節(jié)點傳感器間距離長度影響的Elfes sensing模型[16]。

不同的感知模型決定了覆蓋度的不同算法,式(1)是布爾模型感知能力的計算公式:

(1)

式(1)表明:布爾模型中,若探測點落在節(jié)點感知半徑范圍內(nèi),則感知能力為1;若探測點落在節(jié)點感知半徑范圍外,則感知能力為0。布爾模型定義簡潔、易于建模且應(yīng)用廣泛,本文算法的感知模型采用了布爾模型。

1.2 覆蓋模型

SETk-cover問題中,覆蓋判斷常通過子區(qū)域判斷的方式進(jìn)行,目前常見的子區(qū)域劃分方式有傳感區(qū)域劃分和網(wǎng)格劃分兩種,本算法采用了網(wǎng)格法來進(jìn)行覆蓋情況的判斷。

如圖1所示,目標(biāo)區(qū)域是一個L×W的矩形區(qū)域,網(wǎng)格法將目標(biāo)區(qū)域用平行于x軸和平行于y軸的一系列等間距直線劃分成一個個的網(wǎng)格,網(wǎng)格間的距離稱為粒度d,由期望的覆蓋判斷精度所決定。

圖1 粒度為d的網(wǎng)格判斷網(wǎng)絡(luò)覆蓋的實例

網(wǎng)格法的覆蓋判定規(guī)則是:以網(wǎng)格為單位對覆蓋進(jìn)行判斷,當(dāng)一個網(wǎng)格的4個頂點均處于被覆蓋范圍時,判定該網(wǎng)格屬于被覆蓋區(qū)域。當(dāng)目標(biāo)區(qū)域以及網(wǎng)格的粒度d確定后,可以求得網(wǎng)格的各個頂點坐標(biāo),通過計算網(wǎng)格頂點和各傳感器之間的距離可以判斷出各頂點被覆蓋的情況,進(jìn)而計算出被覆蓋的網(wǎng)格數(shù)。SETk-cover的百分比覆蓋模型中,節(jié)點子集所覆蓋的網(wǎng)格數(shù)量與總網(wǎng)格數(shù)之比即覆蓋的百分比。以圖1為例,被覆蓋的網(wǎng)格數(shù)為陰影區(qū)域的網(wǎng)格數(shù)目141,總的網(wǎng)格數(shù)為25×16=400,則覆蓋的百分比為p=141/400=35.25%。顯然計算出的p值和實際的覆蓋情況之間存在誤差,可通過減小網(wǎng)格粒度d來達(dá)到誤差要求,代價是算法運行時間的增加。

覆蓋和連通度是無線傳感器網(wǎng)絡(luò)最基本的兩個問題。如圖2(a)所示,當(dāng)滿足全覆蓋時,任意節(jié)點和相鄰節(jié)點之間的最短距離一定小于等于2Rs,只要節(jié)點的通信半徑Rc大于每個節(jié)點的最短通信距離,即滿足Rc≥2Rs,就可以構(gòu)成連通的網(wǎng)絡(luò),不需單獨考慮連通度的問題[17]。圖2(b)所示的百分比覆蓋場景中,節(jié)點間的距離不再受限于2Rs,因此必須單獨考慮網(wǎng)絡(luò)的連通度問題。

圖2 全覆蓋和百分比覆蓋的節(jié)點連通性實例

根據(jù)無線傳感器網(wǎng)絡(luò)自組網(wǎng)絡(luò)的特性可知,對于覆蓋集Ci中的任意一個節(jié)點Si,若網(wǎng)絡(luò)連通,則需滿足Si和其他節(jié)點的最短距離min(Di,j)應(yīng)小于等于節(jié)點的通信半徑Rc,即滿足式(2)。

min(Di,j)≤Rc,

(2)

SETk-cover問題中研究百分百覆蓋,要將式(2)所對應(yīng)的連通度條件作為一個約束條件在算法中實現(xiàn),從而保證網(wǎng)絡(luò)的連通度。

1.3 問題描述

N個感知半徑為Rs的傳感器節(jié)點S1,S2,…,SN隨機部署在長為L,寬為W的矩形區(qū)域內(nèi),假設(shè)該無線傳感器網(wǎng)絡(luò)具有以下性質(zhì):①所有傳感器節(jié)點隨機部署后為靜止?fàn)顟B(tài);②可以通過定位技術(shù)確定每個節(jié)點的位置;③相對于節(jié)點的感知覆蓋范圍,目標(biāo)區(qū)域的面積足夠大,邊界效應(yīng)可以忽略;④節(jié)點采用布爾感知模型,網(wǎng)絡(luò)采用網(wǎng)格覆蓋模型;⑤無線傳感器網(wǎng)絡(luò)為同構(gòu)網(wǎng)絡(luò),所有節(jié)點(不包括Sink節(jié)點)具有相同的參數(shù)和初始條件,節(jié)點的最大通信半徑Rc和感知半徑Rs無特定關(guān)系;⑥網(wǎng)絡(luò)無時鐘同步的要求。

無線傳感器網(wǎng)絡(luò)滿足上述條件時,本文研究的問題表述如下:目標(biāo)區(qū)域中,給定覆蓋百分比的目標(biāo)概率p,要求將N個節(jié)點安排在k個互不相交的子集內(nèi)(k值要盡可能大),使得每個子集都能夠?qū)δ繕?biāo)區(qū)域進(jìn)行p百分比覆蓋并保證網(wǎng)絡(luò)連通可用。

2 算法實現(xiàn)

2.1 算法思想

XM HU和J Zhang等人提出的STHGA算法[12]是一種基于全覆蓋的SETk-cover算法,在簡單遺傳算法的基礎(chǔ)上引入了前向編碼和冗余調(diào)度,實驗結(jié)果表明該算法是目前串行算法中求解成功率和求解效率都非常高的一種算法,且算法在不同網(wǎng)絡(luò)規(guī)模下的表現(xiàn)穩(wěn)定。本文對文獻(xiàn)[12]的算法進(jìn)行改進(jìn),將全覆蓋模型改為百分比覆蓋,同時將網(wǎng)絡(luò)的連通度作為約束條件在算法中實現(xiàn)。

2.2 算法步驟

為了更好地說明算法的實現(xiàn)過程,將算法的步驟做如下說明:

Step 1 群體初始化

算法的染色體長度對應(yīng)節(jié)點的個數(shù),基因取值對應(yīng)于覆蓋子集編號,染色體的初始化過程使用了前向編碼方案,對于染色體ci=(gi1,gi2,…,giN),gimax=max(gi1,gi2,…,giN),前向編碼方案要求互不相交的子集C1,C2,…,Cgimax-1中每個子集都能夠?qū)W(wǎng)絡(luò)實現(xiàn)給定指標(biāo)p的百分比覆蓋,而Cgimax對網(wǎng)絡(luò)的覆蓋要求滿足與否是不確定的。舉例來說,染色體ci=(1,2,1,1,3,2,1,2,2,3)表示當(dāng)前有10個節(jié)點,節(jié)點子集C1={S1,S3,S4,S7},C2={S2,S6,S8,S9}可分別對網(wǎng)絡(luò)進(jìn)行百分比覆蓋,C3={S5,S10}對網(wǎng)絡(luò)的覆蓋情況僅從染色體ci無法判斷。初始化時,染色體c1=(1,1,1,…,1),基因取值全部置1。染色體c1的基因取值全部置1表示所有節(jié)點全部激活,此時若網(wǎng)絡(luò)不能滿足覆蓋要求,算法結(jié)束;若此時網(wǎng)絡(luò)可以滿足覆蓋要求,則在染色體c1中隨機選取K1個基因,若對應(yīng)的節(jié)點是冗余節(jié)點,則基因取值自增1構(gòu)成其他染色體,進(jìn)而形成初始化群體。

Step 2 適應(yīng)值評價,保存最優(yōu)染色體

文獻(xiàn)[12]的適應(yīng)度函數(shù)定義為:

fi=ω1(gimax-1)+ω2Pgimax

(3)

式中:ω1,ω2是定義的權(quán)重參數(shù),gimax-1表示滿足覆蓋條件的子集數(shù)目,Pgimax表示不能滿足覆蓋條件的子集的網(wǎng)絡(luò)覆蓋率。顯然,算法尋找最大適應(yīng)度函數(shù)的過程就是不斷增加覆蓋子集的過程。

在百分比覆蓋環(huán)境下,為了在算法中提供連通度的保障,本算法提出可變參的適應(yīng)值函數(shù),當(dāng)染色體所對應(yīng)的節(jié)點子集C1,C2,…,Cgimax-1滿足連通條件式(2)時,則ω1=1,ω2=1否則ω1=0,ω2=1,即本算法的適應(yīng)值函數(shù)定義為式(4)

(4)

將連通條件加入到適應(yīng)值函數(shù)中,所保存的最優(yōu)染色體不僅能滿足最大覆蓋集個數(shù)下的覆蓋條件,而且還可以保證網(wǎng)絡(luò)的連通度。

Step 3 重組/選擇

重組實際上就是適應(yīng)前向編碼方案的交配過程,它和選擇過程組合在一起期望通過染色體的互動產(chǎn)生更好的種群。

Step 4 變異

變異操作僅對未能滿足覆蓋條件的子集所對應(yīng)的基因進(jìn)行,由于可能會降低適應(yīng)度函數(shù),因此每隔Gm代才執(zhí)行一次。

Step 5 冗余調(diào)度

為了加速收斂,文獻(xiàn)[12]提供了混合調(diào)度、前向調(diào)度和關(guān)鍵區(qū)調(diào)度3個冗余調(diào)度模塊。百分比覆蓋模型下覆蓋子集的上限已經(jīng)不受關(guān)鍵區(qū)的約束,因此本算法僅保留了混合調(diào)度和前向調(diào)度模塊。其中,混合調(diào)度將節(jié)點子集中的冗余節(jié)點調(diào)往其他子集;前向調(diào)度將節(jié)點子集中的冗余節(jié)點調(diào)往不滿足覆蓋條件的子集,以提高其覆蓋率。

Step 6 算法迭代運行,直至結(jié)束

算法此后的流程步驟都要遵照前向編碼方案的要求,隨著算法流程的不斷迭代,染色體逼近最優(yōu)解。通過最佳染色體可以看到求解的各個覆蓋子集的情況。

百分比覆蓋中,k值的上限不再受限于關(guān)鍵區(qū)所覆蓋的節(jié)點數(shù),因此算法的結(jié)束條件也不再受限于關(guān)鍵區(qū)覆蓋的節(jié)點數(shù),本算法的結(jié)束條件為最佳染色體400代內(nèi)沒有變化。

4 實驗分析

為了評估算法,在Intel(R)Core(TM)i7-7700 CPU @ 3.60GHz,8GB內(nèi)存,Ubuntu 16.04 LTS 64位操作系統(tǒng)的環(huán)境下進(jìn)行了實驗測試。測試的目標(biāo)區(qū)域是50×50的正方形區(qū)域,算法的參數(shù)設(shè)置為popsize=3,pm=0.5,Gm=100,K1=5,K2=5。對節(jié)點數(shù)量N,節(jié)點感知半徑Rs,節(jié)點通信半徑Rc,網(wǎng)絡(luò)的覆蓋百分比p在不同取值情況下進(jìn)行了多次實驗,每一個實驗用例測試30次,測試結(jié)果取平均值。

測試關(guān)注網(wǎng)絡(luò)參數(shù)N,節(jié)點參數(shù)Rs,Rc,以及覆蓋百分比p對無線傳感器生命期的影響,即關(guān)注在上述參數(shù)取值不同的情況下,節(jié)點所求得的覆蓋集情況以及算法的性能表現(xiàn)。

圖3 覆蓋子集數(shù)量k隨節(jié)點數(shù)目N的變化

當(dāng)Rs=5,Rc=8以及Rs=5,Rc=20時,算法在滿足不同的覆蓋百分比的情況下,覆蓋子集的數(shù)量隨節(jié)點數(shù)N的變化情況如圖3所示。從圖3(a)、圖3(b)可以看出:在同樣的覆蓋百分比情況下,覆蓋集的數(shù)量k隨網(wǎng)絡(luò)節(jié)點N的增加而增加,這意味著隨著網(wǎng)絡(luò)中節(jié)點數(shù)目的不斷增多,冗余節(jié)點增多,構(gòu)成更多的覆蓋子集,網(wǎng)絡(luò)的生命期增加。圖3(a)中,在同樣的節(jié)點數(shù)量下,當(dāng)0.7≤p≤1.0時,覆蓋集的數(shù)量隨百分比p的降低而增加,但是當(dāng)p取值小于0.5時,隨著覆蓋百分比的降低,出現(xiàn)了覆蓋集數(shù)量減少的情況,這主要是因為受限于連通度的約束條件;同時,覆蓋百分比p=0.8時,k值相比于全覆蓋的k值增加了近5倍。圖3(b)中,在同樣的節(jié)點數(shù)量下,當(dāng)0.4≤p≤1.0時,覆蓋集的數(shù)量隨百分比p的降低而增加,但是當(dāng)p取值小于0.3時,隨著覆蓋百分比的降低,出現(xiàn)了覆蓋集數(shù)量減少的情況,這主要是因為受限于連通度的約束條件;同時,覆蓋百分比p=0.4時候的k值相比于全覆蓋的k值增加了十余倍。綜上表明,Rc和Rs比值不同的情況下,約束度的影響不同,比值越大,能帶來生命期最大化的百分比的最佳值越低,不同場景下根據(jù)實際的覆蓋要求設(shè)定理想的覆蓋百分比值,可以顯著地延長網(wǎng)絡(luò)的生命期。

當(dāng)Rs=5,N=1 000時,算法在滿足不同的覆蓋百分比的情況下,覆蓋子集的數(shù)量隨節(jié)點的通信半徑Rc的變化情況如圖4所示。從圖4可以看出:在通信半徑確定不變的情況下,覆蓋集的數(shù)量隨百分比p的降低而增加,受限于連通度的約束條件,當(dāng)p取值較小時,覆蓋集的增速變緩甚至出現(xiàn)下降;同樣的測試條件下,k值會伴隨Rc的增大而增大,這意味著隨著Rc取值的增大,連通性所帶來的約束效應(yīng)減小。

圖4 覆蓋子集數(shù)量k隨節(jié)點通信半徑Rc的變化

當(dāng)Rc=15,N=1 000時,算法在滿足不同的覆蓋百分比的情況下,覆蓋子集的數(shù)量隨節(jié)點的通信半徑Rs的變化情況如圖5所示。從圖5可以看出:當(dāng)0.8≤p時,k值會伴隨Rs的增大而增大,這是由于Rs的增大使得節(jié)點的覆蓋面積增大,冗余節(jié)點增多,從而可以構(gòu)成更多的覆蓋集;當(dāng)p≤0.8時,k值和Rs的取值關(guān)系不明顯,這是由于受約束性條件影響,傳感器感知半徑增大所造成的覆蓋面積增大所帶來的覆蓋集增加的效應(yīng)降低。

圖5 覆蓋子集數(shù)量k隨節(jié)點感知半徑Rs的變化

從圖6可以看出,算法的FEs曲線雖然在局部會有一些小的震蕩,但是總體上FEs的取值隨N,Rc,Rs的取值增大而增大。同時,由于算法是概率型算法,因此雖然總體上算法的FEs會隨著N值的增加而提升,但是并沒有嚴(yán)格遵守這一規(guī)律。結(jié)合圖3～圖6來看,當(dāng)網(wǎng)絡(luò)的覆蓋集數(shù)量k增大時,算法的FEs也會隨之增大,但是增幅并不成倍。以圖6(a)為例,可以看到當(dāng)覆蓋百分比p為0.8時的FEs值相比于全覆蓋的FEs值增加了僅約1%,但是覆蓋集數(shù)量k卻增加了近5倍,這說明生命期延長需要的計算資源多,但是生命期延長的效應(yīng)更明顯。同時,受限于連通度的約束條件,當(dāng)覆蓋百分比值非常低的時候,生命期的延長效應(yīng)會降低,因此在進(jìn)行覆蓋比率選擇的時候并非越低越好。

圖6 適應(yīng)值評估度隨各參數(shù)的變化

5 結(jié)束語

通過SETk-cover算法找出多個對網(wǎng)絡(luò)獨立覆蓋的集合并進(jìn)行睡眠調(diào)度,可以有效地提升網(wǎng)絡(luò)的生命期,當(dāng)前的SETk-cover算法多針對完全覆蓋展開研究,本文提出了一種針對百分比覆蓋的SETk-cover算法,將連通度作為約束條件,以覆蓋和生命期為目標(biāo),百分比覆蓋下可以讓更多的節(jié)點進(jìn)入休眠狀態(tài),從而達(dá)到節(jié)能、抗干擾的目的。實驗結(jié)果表明,算法在保證網(wǎng)絡(luò)覆蓋質(zhì)量時能夠有效地減少活躍節(jié)點的數(shù)量,使得覆蓋集數(shù)量增大,延長了網(wǎng)絡(luò)的生存時間。受限于連通度的約束,覆蓋百分比的生命期延長效應(yīng)在覆蓋比率較低的情況下有抑制現(xiàn)象,算法可為需要進(jìn)行覆蓋比選擇的應(yīng)用場景提供理論最佳數(shù)值的參考依據(jù)。