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

費(fèi) 娟,劉桂英,劉 瑤

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

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

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

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

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

1.1 感知模型

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

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

(1)

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

1.2 覆蓋模型

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

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

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

網(wǎng)格法的覆蓋判定規(guī)則是:以網(wǎng)格為單位對(duì)覆蓋進(jìn)行判斷,當(dāng)一個(gè)網(wǎng)格的4個(gè)頂點(diǎn)均處于被覆蓋范圍時(shí),判定該網(wǎng)格屬于被覆蓋區(qū)域。當(dāng)目標(biāo)區(qū)域以及網(wǎng)格的粒度d確定后,可以求得網(wǎng)格的各個(gè)頂點(diǎn)坐標(biāo),通過(guò)計(jì)算網(wǎng)格頂點(diǎn)和各傳感器之間的距離可以判斷出各頂點(diǎn)被覆蓋的情況,進(jìn)而計(jì)算出被覆蓋的網(wǎng)格數(shù)。SETk-cover的百分比覆蓋模型中,節(jié)點(diǎn)子集所覆蓋的網(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%。顯然計(jì)算出的p值和實(shí)際的覆蓋情況之間存在誤差,可通過(guò)減小網(wǎng)格粒度d來(lái)達(dá)到誤差要求,代價(jià)是算法運(yùn)行時(shí)間的增加。

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

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

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

min(Di,j)≤Rc,

(2)

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

1.3 問(wèn)題描述

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

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

2 算法實(shí)現(xiàn)

2.1 算法思想

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

2.2 算法步驟

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

Step 1 群體初始化

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

Step 2 適應(yīng)值評(píng)價(jià),保存最優(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ù)的過(guò)程就是不斷增加覆蓋子集的過(guò)程。

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

(4)

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

Step 3 重組/選擇

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

Step 4 變異

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

Step 5 冗余調(diào)度

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

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

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

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

4 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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