石 拓,李建中,高 宏

(哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

無線傳感器網(wǎng)絡(luò)(wireless senor network)是物聯(lián)網(wǎng)(IoT)中的重要組成部分,一個(gè)無線傳感器網(wǎng)絡(luò)由若干無線傳感器節(jié)點(diǎn)和Sink 節(jié)點(diǎn)構(gòu)成.無線傳感器節(jié)點(diǎn)通過自身配置的電池獲能,并通過傳感器來獲取周圍環(huán)境中的物理信息,再通過通信模塊與其他傳感器節(jié)點(diǎn)或Sink 節(jié)點(diǎn)進(jìn)行通信[1].這樣,一個(gè)無線傳感器網(wǎng)絡(luò)可以被部署到一個(gè)區(qū)域當(dāng)中,從而達(dá)到收集、分析該區(qū)域中的物理信息的目的.由于無線傳感器節(jié)點(diǎn)的體積很小,這樣,無線傳感器網(wǎng)絡(luò)可以被部署到人類很難到達(dá)的環(huán)境,比如森林、河流、山丘等.這樣,通過無線傳感器網(wǎng)絡(luò),我們幾乎可以對任意環(huán)境進(jìn)行監(jiān)控.然而,以下兩個(gè)缺點(diǎn)阻礙了無線傳感器網(wǎng)絡(luò)的大規(guī)模部署.

(1) 無線傳感器網(wǎng)絡(luò)的壽命受限.由于無線傳感器節(jié)點(diǎn)的能量有限,這導(dǎo)致了無線傳感器網(wǎng)絡(luò)的壽命是受限的.對于一個(gè)部署在復(fù)雜環(huán)境中的大型無線傳感器網(wǎng)絡(luò)而言,短暫的網(wǎng)絡(luò)壽命不但影響了網(wǎng)絡(luò)的性能,也造成了不必要的經(jīng)濟(jì)損失.

(2) 無線傳感器節(jié)點(diǎn)是環(huán)境不友好的.由于無線傳感器節(jié)點(diǎn)一般采用鋰電池作為能量源,當(dāng)無線傳感器節(jié)點(diǎn)能量耗盡后,遺留在環(huán)境中的廢棄電池會對環(huán)境造成極大的污染.

為了解決無線傳感器網(wǎng)絡(luò)的這兩個(gè)問題,Shi 等人[2?5]提出了一種新型的傳感器網(wǎng)絡(luò)結(jié)構(gòu)——無源傳感器網(wǎng)絡(luò).在無源傳感器網(wǎng)絡(luò)中,每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)配備有可從周圍環(huán)境中獲取能量的能量獲取模塊,并通過超級電容來存儲能量.

?一方面,由于周圍環(huán)境中的能量是無限的,比如太陽能、風(fēng)能、射頻能量等,這樣,從能量上講,無源傳感器網(wǎng)絡(luò)的壽命是無限長的,從而解決了無線傳感器網(wǎng)絡(luò)的壽命受限的問題.比如在斜拉橋的拉索狀態(tài)檢測應(yīng)用中,傳統(tǒng)的方法是在拉索上部署不同類型的無線傳感器節(jié)點(diǎn),但是由于無線傳感器節(jié)點(diǎn)的壽命有限,需要不斷地更換傳感器節(jié)點(diǎn)中的電池,這就造成了不必要的危險(xiǎn)和人工消耗.通過部署無源傳感器網(wǎng)絡(luò)節(jié)點(diǎn),則可以改善這一問題.

?另一方面,由于超級電容從理論上講是可以無限次充放電的,這樣,無源節(jié)點(diǎn)的能量存儲模塊的壽命也是無限長的,從而解決了無線傳感器節(jié)點(diǎn)環(huán)境不友好的缺點(diǎn).比如在森林火災(zāi)監(jiān)控當(dāng)中,需要在野外森林中部署大量的無線傳感器節(jié)點(diǎn),但是無線傳感器節(jié)點(diǎn)所配備的鋰電池在能量耗盡后,會對自然環(huán)境造成嚴(yán)重的污染.如果使用無源傳感器網(wǎng)絡(luò)進(jìn)行監(jiān)控,則可以實(shí)現(xiàn)環(huán)境友好型監(jiān)控.

綜上所述,無源傳感器網(wǎng)絡(luò)可以替代無線傳感器網(wǎng)絡(luò)對環(huán)境進(jìn)行理論上無限長時(shí)間的監(jiān)控.圖1 中展示了兩種無源節(jié)點(diǎn),其中,圖1(a)中的無源節(jié)點(diǎn)主要從射頻能量源中獲取能量,圖1(b)中的節(jié)點(diǎn)可以從太陽能中獲取能量.

Fig.1 Two kinds of battery-free nodes圖1 兩種無源節(jié)點(diǎn)

覆蓋問題是傳統(tǒng)無線傳感器網(wǎng)絡(luò)中的一個(gè)重要問題.覆蓋問題的解決,直接關(guān)系到了無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)獲取質(zhì)量.文獻(xiàn)[6?15]中均對無線傳感器網(wǎng)絡(luò)中的覆蓋問題進(jìn)行了研究.然而,由于無源傳感器網(wǎng)絡(luò)自身的特點(diǎn),導(dǎo)致了覆蓋問題在無源傳感器網(wǎng)絡(luò)是一個(gè)全新的問題.Shi 等人[2,4,5]著重討論了覆蓋問題在無源傳感器網(wǎng)絡(luò)中的特點(diǎn).相比于無線傳感器網(wǎng)絡(luò)中的覆蓋問題,無源傳感器網(wǎng)絡(luò)的覆蓋問題具有以下特點(diǎn).

(1) 優(yōu)化目標(biāo)不同.無源傳感器網(wǎng)絡(luò)中的覆蓋問題與無線傳感器網(wǎng)絡(luò)中的覆蓋問題的優(yōu)化目標(biāo)是不同的:在無線傳感器網(wǎng)絡(luò)中,由于傳感器節(jié)點(diǎn)的能量有限,所以在無線傳感器網(wǎng)絡(luò)當(dāng)中的覆蓋問題的主要目的在于合理化地調(diào)度節(jié)點(diǎn)工作,從而減少節(jié)點(diǎn)的能量消耗,進(jìn)而最大化網(wǎng)絡(luò)壽命;然而在無源傳感器網(wǎng)絡(luò)當(dāng)中,由于無源節(jié)點(diǎn)的壽命在能量角度來講是無限的,這就使得最大化網(wǎng)絡(luò)壽命成為了一個(gè)偽命題.在無源傳感器網(wǎng)絡(luò)當(dāng)中,我們需要考慮的是如何通過更加合理地使用環(huán)境中的能量,來最大化網(wǎng)絡(luò)的覆蓋質(zhì)量.

(2) 節(jié)點(diǎn)調(diào)度方式不同:在無線傳感器網(wǎng)絡(luò)當(dāng)中,在網(wǎng)絡(luò)生命周期內(nèi),傳感器節(jié)點(diǎn)可以在任意時(shí)間工作;然而在無源傳感器網(wǎng)絡(luò)當(dāng)中,無源節(jié)點(diǎn)只有在獲取足夠能量后才能開始工作.但是由于周圍環(huán)境能量源具有能量低、能量分布不均勻等特點(diǎn),導(dǎo)致一個(gè)無源節(jié)點(diǎn)往往需要很長時(shí)間才能獲取足夠能量,這就使得無源節(jié)點(diǎn)無法在任意時(shí)刻進(jìn)行工作.這種特點(diǎn)使得無源傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)調(diào)度更加困難,使得無源傳感器網(wǎng)絡(luò)中的覆蓋問題成為了一個(gè)新的問題.

(3) 節(jié)點(diǎn)能量獲取不穩(wěn)定.能量可獲取網(wǎng)絡(luò)(energy harvesting network)是無線傳感器網(wǎng)絡(luò)中的一種,在能量可獲取網(wǎng)絡(luò)中[16?18],每個(gè)傳感器節(jié)點(diǎn)可獲取固定的能量輸入.然而在無源傳感器網(wǎng)絡(luò)中,由于周圍環(huán)境能量源的不可預(yù)測性,導(dǎo)致節(jié)點(diǎn)的能量獲取速率十分不穩(wěn)定.這也為無源傳輸節(jié)點(diǎn)的調(diào)度造成了極大的困難.

根據(jù)以上3 點(diǎn),我們發(fā)現(xiàn),無源傳感器網(wǎng)絡(luò)中的覆蓋問題是一個(gè)全新的問題,且現(xiàn)有的在無線傳感器網(wǎng)絡(luò)中的覆蓋算法均無法用來解決無源傳感器網(wǎng)絡(luò)中的覆蓋問題.Shi[2]在文章中給出了一種解決無源傳感器網(wǎng)絡(luò)中的覆蓋問題的方案.然而在這篇文章中[2],作者并沒有考慮具有多等級通信半徑的無源節(jié)點(diǎn).一個(gè)具有多等級通信半徑的無源節(jié)點(diǎn)可以自主地調(diào)整自己的通信半徑,而不同的通信半徑具有不同的能量消耗.這樣,無源節(jié)點(diǎn)具有更多地自主性,并可以更合理地利用所獲得的環(huán)境能量.比如,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度比較高,或者環(huán)境中能量源比較弱時(shí),無源節(jié)點(diǎn)可以將自己的通信半徑調(diào)為較低的等級,從而減少不必要的能量消耗;而當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度比較低,或者環(huán)境中能量源比較強(qiáng)時(shí),無源節(jié)點(diǎn)則可以采用較高等級的通信半徑,通過提高通信半徑來增強(qiáng)網(wǎng)絡(luò)的連通性.然而,由于上述提到的3 個(gè)無源網(wǎng)絡(luò)的特點(diǎn),如何合理地調(diào)度無源節(jié)點(diǎn)工作、調(diào)整無源節(jié)點(diǎn)的通信半徑等級,成為了一個(gè)更加困難的問題.在本文中,我們提出了通信半徑可調(diào)整的無源傳感器網(wǎng)絡(luò)覆蓋最大化問題(CR-MC-BFN).

本文的貢獻(xiàn)簡介如下:

(1) 我們定義了通信半徑可調(diào)整的無源傳感器網(wǎng)絡(luò)覆蓋最大化問題(CR-MC-BFN),證明了CR-MC-BFN問題是NP-Hard 問題.

(2) 我們提出了一個(gè)兩階段近似算法(two-phase approximation algorithm,簡稱TPA)來解決CR-MC-BFN問題.我們分析了TPA算法的時(shí)間復(fù)雜度,并證明了TPA算法的近似比.

(3) 我們通過模擬實(shí)驗(yàn)來驗(yàn)證算法的性能.我們首先提出了一個(gè)基于貪心策略的樸素算法,并將TPA算法與其進(jìn)行比較.根據(jù)實(shí)驗(yàn)結(jié)果,TPA算法是有效的、可靠的.

本文第1 節(jié)總結(jié)相關(guān)的工作.第2 節(jié)給出問題的明確定義.第3 節(jié)給出該問題的近似算法,并分析算法的時(shí)間復(fù)雜度和近似比.第4 節(jié)研究如何在無源傳感器網(wǎng)絡(luò)中解決k-覆蓋的問題.第5 節(jié)通過模擬實(shí)驗(yàn)驗(yàn)證算法的性能.第6 節(jié)總結(jié)全文.

1 相關(guān)工作

1.1 網(wǎng)絡(luò)覆蓋

覆蓋問題是傳感器網(wǎng)絡(luò)中的一個(gè)重要問題.覆蓋問題的目的,是要保障傳感器網(wǎng)絡(luò)中傳感器對監(jiān)控目標(biāo)的有效覆蓋.在無線傳感器網(wǎng)絡(luò)的研究中,存在著大量的關(guān)于覆蓋問題的研究[7?15].這些研究中,覆蓋問題的主要目標(biāo)就是合理地節(jié)省傳感器節(jié)點(diǎn)的電量消耗,進(jìn)而最大化網(wǎng)絡(luò)的壽命.在文獻(xiàn)[13,15]中,作者考慮了一種邊界覆蓋問題,在這種問題中,覆蓋區(qū)域?yàn)橐粭l給定的路.而在文獻(xiàn)[10?12]中,作者希望通過構(gòu)造連通支配集(connected dominating set)來保障無線傳感器網(wǎng)絡(luò)的覆蓋與連通.但是由于這些工作均沒有考慮如何合理地利用能量,且其研究問題的優(yōu)化目標(biāo)與無源傳感器網(wǎng)絡(luò)中的覆蓋問題不同,導(dǎo)致這些工作無法直接應(yīng)用到無源傳感器網(wǎng)絡(luò)中來.

1.2 無源節(jié)點(diǎn)與無源傳感器網(wǎng)絡(luò)

無源節(jié)點(diǎn)是一種新型的物聯(lián)網(wǎng)節(jié)點(diǎn).Sample 等人[19?21]通過改進(jìn)RFID 的標(biāo)簽節(jié)點(diǎn),使其成為了一種可以從射頻能量中獲取能量的無源節(jié)點(diǎn).文獻(xiàn)[22,23]中分別提出了一種基于太陽能和風(fēng)能的無源節(jié)點(diǎn).Dai 等人[24,25]提出了一個(gè)基于特定充電樁的無源傳感器網(wǎng)絡(luò),在這種網(wǎng)絡(luò)中,無源節(jié)點(diǎn)需要從特定的充電樁來獲取能量.然而,這些文章或者沒有考慮到無源節(jié)點(diǎn)的組網(wǎng)問題,或者沒有考慮無源傳感器網(wǎng)絡(luò)中的覆蓋問題.

1.3 無源傳感器網(wǎng)絡(luò)中的覆蓋問題

Shi 等人[2,4,5,26]研究了無源傳感器網(wǎng)絡(luò)中的覆蓋問題.在這些文章中,主要考慮了在不同網(wǎng)絡(luò)結(jié)構(gòu)、不同能量獲取方式下的無源傳感器網(wǎng)絡(luò)中的覆蓋問題.然而在這些問題中,均沒有考慮無源傳感器網(wǎng)絡(luò)中的無源節(jié)點(diǎn)的通信半徑選擇問題.

2 問題定義

2.1 網(wǎng)絡(luò)模型

一個(gè)無源傳感器網(wǎng)絡(luò)(battery-free wireless sensor network,簡稱BF-WSN)包含了一個(gè)Sink 節(jié)點(diǎn)集合S={s1,s2,…,sn}和一個(gè)無源節(jié)點(diǎn)集合V={1,2,…,m}.無源節(jié)點(diǎn)均勻地分布在監(jiān)控區(qū)域R.無源網(wǎng)絡(luò)的監(jiān)控周期為T,T可被分為若干時(shí)間槽:{t1,t2,…,tK}.不失一般性地,我們將每一個(gè)時(shí)間槽當(dāng)作網(wǎng)絡(luò)的采樣周期.

每個(gè)無源節(jié)點(diǎn)可以從周圍能源環(huán)境中獲取能量.我們設(shè)每個(gè)節(jié)點(diǎn)i在時(shí)間槽tj可獲取的能量為μi(tj),同時(shí)設(shè)所有無源節(jié)點(diǎn)都具有相同的能量存儲空間B.令Bi(tj)為無源節(jié)點(diǎn)i在tj時(shí)間槽開始時(shí)刻所存儲的電量,顯然,Bi(tj)≤B.根據(jù)Zhang 等人[27]的研究工作,對于任意一個(gè)無源節(jié)點(diǎn)i,它可以在時(shí)間槽tj工作,當(dāng)且僅當(dāng)Bi(tj)≥Bf.其中,Bf是保障節(jié)點(diǎn)可以工作的最低能量值.一個(gè)無源節(jié)點(diǎn)在一個(gè)時(shí)間槽(或采樣周期)內(nèi)可以進(jìn)行感知、計(jì)算、傳輸?shù)裙ぷ?而在進(jìn)行這些工作的過程中,無源節(jié)點(diǎn)同樣需要消耗能量.我們假設(shè):在每一個(gè)時(shí)間槽,每一個(gè)無源節(jié)點(diǎn)的最大能量消耗為Δ[28],顯然,Δ≤Bf.這樣,節(jié)點(diǎn)i在時(shí)間槽tj+1的電量可以表示為

不失一般性,我們假設(shè)所有Sink 節(jié)點(diǎn)所導(dǎo)出的圖為連通圖,且所有無源節(jié)點(diǎn)具有相同的感知半徑rs.根據(jù)無源節(jié)點(diǎn)的特性,我們假設(shè)節(jié)點(diǎn)可以自主地調(diào)整其通信半徑的大小[29].設(shè)每個(gè)無源節(jié)點(diǎn)的通信半徑rc具有L個(gè)等級,當(dāng)節(jié)點(diǎn)的通信半徑處于l級時(shí),節(jié)點(diǎn)的通信半徑為節(jié)點(diǎn)單位時(shí)間槽的最大能量消耗為Δl,且對于任意兩個(gè)等級1≤l

給定一個(gè)監(jiān)控區(qū)域R,R可以表示為所有無源節(jié)點(diǎn)監(jiān)控區(qū)域的集合Ri,其中,Ri是無源節(jié)點(diǎn)i的監(jiān)控區(qū)域.一般地,我們認(rèn)為Ri是一個(gè)以i的位置為圓心、rs為半徑的圓形區(qū)域.為了更好地評估對監(jiān)控區(qū)域的覆蓋效果,我們再根據(jù)節(jié)點(diǎn)的感知半徑將監(jiān)控區(qū)域R離散化為若干不同的區(qū)塊,并為每一個(gè)區(qū)塊分配一個(gè)0 到1 之間的權(quán)值.區(qū)塊的權(quán)值表示了區(qū)塊的重要程度,比如,對于一個(gè)部署在森林當(dāng)中、監(jiān)控森林火災(zāi)的網(wǎng)絡(luò)而言,更加干燥的區(qū)域就需要分配給較高的權(quán)重.一個(gè)區(qū)塊的具體定義如下.

定義1(監(jiān)控區(qū)塊).給定一個(gè)監(jiān)控區(qū)域R,R可以被劃分為若干不同的監(jiān)控區(qū)域,R={φ1,φ2,…,φk}.對于任意一個(gè)監(jiān)控區(qū)塊φi∈R,φi需滿足以下條件:

(1)φi具有一個(gè)在0～1 之間的權(quán)重wi;

(2) 對于φi中的任意兩點(diǎn)p,p′,{j|dis(j,p)≤rs∧j∈V}={j|dis(j,p′)≤rs∧j∈V}.

定義1 中的第2 個(gè)條件表明,處于同一個(gè)監(jiān)控區(qū)塊中的所有點(diǎn),均可被相同的無源節(jié)點(diǎn)集合所監(jiān)控.圖2 中給出了一個(gè)監(jiān)控區(qū)塊的例子.圖2 中具有4 個(gè)無源節(jié)點(diǎn),根據(jù)無源節(jié)點(diǎn)的感知半徑,監(jiān)控區(qū)域可以被分為11 個(gè)監(jiān)控區(qū)塊.對于任意的監(jiān)控區(qū)塊φi∈R,我們用ai來表示φi的面積.

Fig.2 An example of the monitor block圖2 監(jiān)控區(qū)塊的例子

2.2 問題定義

為了有效地監(jiān)控區(qū)域,無源網(wǎng)絡(luò)需要調(diào)度節(jié)點(diǎn),使得在任意時(shí)間槽內(nèi)有無源節(jié)點(diǎn)進(jìn)行工作,并對監(jiān)控區(qū)域進(jìn)行監(jiān)控.因此,我們給出如下局部覆蓋的定義.

定義2(局部覆蓋).給定一個(gè)無源傳感器網(wǎng)絡(luò)N(V∪S,E),在時(shí)間槽t的覆蓋Ct∈V是一個(gè)無源節(jié)點(diǎn)集合,且滿足以下條件.

(1) 對于任意一個(gè)無源節(jié)點(diǎn)i∈Ct,Bi(t)≥Bf;

(2) 由Ct∪S導(dǎo)出的圖Gt(Ct∪S,Et)是一個(gè)連通圖,且Et={(i,j)|(dis(i,j)≤min{rc(i,t),rc(j,t)})∧(i,j∈Ct)}.

定義2 中的條件(1)表明,在時(shí)間槽t的局部覆蓋中的所有無源節(jié)點(diǎn)均可工作.而第2 個(gè)條件表明,由這些節(jié)點(diǎn)和Sink 節(jié)點(diǎn)所構(gòu)成的圖是連通圖,這也保障了在時(shí)間槽t內(nèi)局部覆蓋的連通性.顯然,對于一個(gè)局部覆蓋Ct,其所能監(jiān)控的區(qū)域?yàn)?根據(jù)局部覆蓋的定義,我們給出如下全局覆蓋(或簡稱覆蓋)的定義:

定義3(全局覆蓋(覆蓋)).給定一個(gè)無源傳感器網(wǎng)絡(luò)N(V∪S,E)、一個(gè)監(jiān)控周期T,一個(gè)全局覆蓋C={Ct|t∈T}是在監(jiān)控周期T內(nèi)的所有局部覆蓋的集合.

我們定義如下的覆蓋質(zhì)量來度量一個(gè)(局部/全局)覆蓋:

定義4(覆蓋質(zhì)量).給定一個(gè)全局覆蓋C={Ct|t∈T},對于任意局部覆蓋Ct∈C,其覆蓋質(zhì)量為

顯然,當(dāng)Q(C)=1 時(shí),監(jiān)控區(qū)域在監(jiān)控周期內(nèi)可以被全覆蓋.然而,由于無源節(jié)點(diǎn)的特點(diǎn),一個(gè)無源節(jié)點(diǎn)很難保障在任意時(shí)刻都可以工作.這樣,如何合理地調(diào)度無源節(jié)點(diǎn)工作,選取節(jié)點(diǎn)的通信半徑,從而最大化全局覆蓋質(zhì)量,成為了一個(gè)問題.為此,我們定義了通信半徑可調(diào)整的無源傳感器網(wǎng)絡(luò)覆蓋最大化問題(簡稱CR-MC-BFN).該問題的輸入輸出如下.

輸入:

1.無源節(jié)點(diǎn)集合V和Sink 節(jié)點(diǎn)集合S;

2.無源節(jié)點(diǎn)的能量存儲空間B和無源節(jié)點(diǎn)可以工作的最小電量Bf;

3.無源節(jié)點(diǎn)的感知半徑rs;

4.無源節(jié)點(diǎn)通信半徑的L個(gè)等級以及無源節(jié)點(diǎn)在不同通信半徑下的單位時(shí)間槽能量消耗{Δ1,Δ2,…,ΔL};

5.無源傳感器網(wǎng)絡(luò)的監(jiān)控周期T={t1,t2,…,tK}以及任意無源節(jié)點(diǎn)i在不同時(shí)間槽tj∈T 獲取的能量μi(tj);

6.無源網(wǎng)絡(luò)所監(jiān)控的監(jiān)控區(qū)域R={φ1,φ2,…,φm}以及每個(gè)監(jiān)控區(qū)塊φj∈R的權(quán)值wj和面積aj;

輸出:一個(gè)具有最大覆蓋質(zhì)量的全局覆蓋C={Ct|t∈T}.

以下定理證明了CR-MC-BFN 問題是NP-Hard 的.

定理1.CR-MC-BFN 問題是NP-Hard 的.

證明:顯然,Shi 等人[2]所研究的問題MC-BFN 是CR-MC-BFN 問題在L=1 時(shí)的特例.因?yàn)镸C-BFN 問題是NP-Hard 問題,所以CR-MC-BFN 問題也是NP-Hard 問題.□

3 CR-MC-BFN 問題的近似算法

因?yàn)镃R-MC-BFN 問題是NP-Hard 的,我們在這一章提出了一個(gè)兩階段近似算法(two-phase approximation algorithm,簡稱TPA)對其進(jìn)行求解.該近似算法分為兩個(gè)階段,這兩個(gè)階段簡述如下.

?階段1:節(jié)點(diǎn)工作預(yù)調(diào)度.在給定區(qū)域內(nèi)基本能量分布(定義5)的情況下,為每個(gè)無源節(jié)點(diǎn)預(yù)分配傳輸半徑,并給出每個(gè)無源節(jié)點(diǎn)的調(diào)度,從而最大化網(wǎng)絡(luò)的覆蓋質(zhì)量;

?階段2:節(jié)點(diǎn)工作自適應(yīng)調(diào)度.根據(jù)節(jié)點(diǎn)的實(shí)際獲能,對階段1 中為節(jié)點(diǎn)預(yù)分配的傳輸半徑和工作調(diào)度進(jìn)行自適應(yīng)式的微調(diào),從而進(jìn)一步最大化網(wǎng)絡(luò)的覆蓋質(zhì)量.

在以下兩節(jié)中,我們將詳細(xì)地介紹這兩個(gè)階段.

3.1 階段1:節(jié)點(diǎn)工作預(yù)調(diào)度

由于周圍能源環(huán)境的變化十分復(fù)雜,對于一個(gè)無源節(jié)點(diǎn),預(yù)測該節(jié)點(diǎn)在特定時(shí)間槽內(nèi)的能量獲取是十分困難的.但是根據(jù)能源環(huán)境的歷史數(shù)據(jù),我們可以很容易地預(yù)測每個(gè)節(jié)點(diǎn)可獲取能量的最小值.因此,我們可以定義基本能量分布.

定義5(基本能量分布).給定無源節(jié)點(diǎn)集合V,監(jiān)控周期T,一個(gè)基本能量分布E={μi|i∈V}滿足對于任意μi∈E,μi≤min{μi(t)|t∈T}.

對于一個(gè)無源網(wǎng)絡(luò),基本能量分布可以從歷史數(shù)據(jù)中很容易地得到.基于基本能量分布,我們可以對網(wǎng)絡(luò)中節(jié)點(diǎn)的工作狀態(tài)進(jìn)行提前調(diào)度,從而減少節(jié)點(diǎn)分布式調(diào)度時(shí)的能量消耗.我們的節(jié)點(diǎn)工作預(yù)調(diào)度算法大致分為以下兩個(gè)步驟.

?步驟1(節(jié)點(diǎn)集合劃分算法):將無源傳輸節(jié)點(diǎn)分為k個(gè)不相交的集合D={D1,D2,…,Dk},為每個(gè)集合中的無源節(jié)點(diǎn)分配通信半徑,使得對于任意Dj∈D,Dj∪S的導(dǎo)出圖是連通的,并且最大化目標(biāo)函數(shù):

?步驟2(節(jié)點(diǎn)集合調(diào)度算法):調(diào)度步驟1 中的k個(gè)集合,從而最大化網(wǎng)絡(luò)的覆蓋質(zhì)量.我們在以下兩個(gè)章節(jié)中介紹這兩個(gè)步驟中的具體操作.

3.1.1 步驟1:節(jié)點(diǎn)集合劃分算法

步驟1 中主要存在兩個(gè)問題:1) 如何確定k的具體值;和2) 如何分割節(jié)點(diǎn)并分配節(jié)點(diǎn)的通信半徑,從而最大化目標(biāo)函數(shù).為了解決這兩個(gè)問題,步驟1(見算法1)中按照如下子步驟進(jìn)行.

Step 1(Line 1～Line 2):設(shè)k的最大值為kmax=max{(Δl/μj)|1≤l≤L∧μj∈E},最小值為

Step 2(Line 3～Line 18):對于任意k,且kmin≤k≤kmax,重復(fù)以下步驟.

(1) (Line 4～Line 5):對于每個(gè)無源節(jié)點(diǎn)i∈V,為其分配通信半徑,其中,

需要指出的是:對于無源節(jié)點(diǎn)i而言,若不存在滿足條件的通信半徑等級時(shí),則不考慮該節(jié)點(diǎn).

(2) (Line 6～Line 17):設(shè)D1=D2=…=Dk=?,并運(yùn)行以下步驟.

3.1.2 步驟2:節(jié)點(diǎn)集合調(diào)度算法

設(shè)D={D1,D2,…,Dk}為步驟1 中的返回結(jié)果,則步驟2 按照如下構(gòu)造全局覆蓋:

對于任意時(shí)間槽(采樣周期)tj∈T,如果jmod (k+1)=m,則Ctj=Dm,即

3.2 階段2:節(jié)點(diǎn)工作自適應(yīng)調(diào)度

在階段1 當(dāng)中,我們根據(jù)網(wǎng)絡(luò)中的基本能量分布,對無源節(jié)點(diǎn)進(jìn)行了預(yù)調(diào)度,并得到了一個(gè)全局覆蓋C.然而,在階段1 中所取得的全局覆蓋的主要依據(jù)是每個(gè)無源節(jié)點(diǎn)的靜態(tài)的基本能量分布.如果單獨(dú)依賴階段1 中的全局覆蓋,則會造成節(jié)點(diǎn)存儲能量無法充分利用的后果.因此在這一階段,我們將根據(jù)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的實(shí)時(shí)能量獲取以及節(jié)點(diǎn)自身所存儲的能量,自適應(yīng)地調(diào)度節(jié)點(diǎn)進(jìn)行工作,從而最大化全局覆蓋質(zhì)量.

階段2 包含以下兩個(gè)步驟.

?Step 1:對于任意一個(gè)無源節(jié)點(diǎn)i∈V和任意的時(shí)間槽t∈T,如果i∈Ct,則i在時(shí)間槽內(nèi)工作.

?Step 2:對于任意一個(gè)無源節(jié)點(diǎn)i∈V和任意的時(shí)間槽t∈T,如果i?Ct,則i按照如下情況判斷在時(shí)間槽t

內(nèi)的工作狀態(tài):

(a) 如果?1≤l≤L,都有Bi(t)?Δl+kμi

(b) 如果?1≤l≤L,并滿足以下兩個(gè)條件:

則對于每一個(gè)滿足該條件的l,為其分配權(quán)值wl=λ/Δl,其中,

這里,λ值表示如果將節(jié)點(diǎn)i加入Ct之后,可能繼續(xù)加入Ct中的無源節(jié)點(diǎn)的個(gè)數(shù).令滿足條件(1)、條件(2)},并且調(diào)度節(jié)點(diǎn)i在時(shí)間槽t工作(即Ct=Ct∪{i}),通信半徑為

這樣,根據(jù)階段1 和階段2,TPA算法即可完成對無源節(jié)點(diǎn)的調(diào)度.該算法的時(shí)間復(fù)雜度、近似比將在下一章節(jié)給出.

3.3 TPA算法的性能分析

3.3.1 時(shí)間復(fù)雜度

在階段1 中,共有kmax?kmin次迭代.在每一次迭代中,需要構(gòu)造k個(gè)不相交的無源節(jié)點(diǎn)集合.構(gòu)造無源節(jié)點(diǎn)集合的過程也需要進(jìn)行迭代,并且并在每一次迭代中選取一個(gè)無源節(jié)點(diǎn).因此,為了構(gòu)造這些無源節(jié)點(diǎn)集合,需要進(jìn)行最多|V|次迭代.同時(shí),在每次迭代中需要計(jì)算每一個(gè)無源節(jié)點(diǎn)對應(yīng)于不同的不相交節(jié)點(diǎn)集合的權(quán)值.這樣,構(gòu)造不相交無源節(jié)點(diǎn)集合的時(shí)間復(fù)雜度為O(k|V|2),其中,kmin≤k≤kmax.因此,階段1 的時(shí)間復(fù)雜度為

在階段2 中,在每一個(gè)時(shí)間槽內(nèi)需要確定每一個(gè)無源節(jié)點(diǎn)的狀態(tài),判斷該節(jié)點(diǎn)是否滿足可以工作的條件.這樣,至多有|V|個(gè)節(jié)點(diǎn)滿足工作條件.對于每一個(gè)滿足條件的無源節(jié)點(diǎn),需要計(jì)算其權(quán)值,計(jì)算權(quán)值的過程的時(shí)間復(fù)雜度為O(L).這樣,在階段2 的時(shí)間復(fù)雜度為O(L|T||V|).

3.3.2 算法近似比

引理1.設(shè)為階段1 的輸出結(jié)果,且D為階段1 中步驟1的輸出結(jié)果,則有Q(C)=U(D).

證明:首先,根據(jù)階段1 中Step 2 的通信半徑構(gòu)造方法,即對于任意無源節(jié)點(diǎn)i,其通信半徑為,且li=max{l|,我們可知:若節(jié)點(diǎn)i可以在時(shí)間槽tj工作,則其工作后的能量滿足.這樣,無源節(jié)點(diǎn)i在tj+k時(shí)間槽的能量滿足.這樣,無源節(jié)點(diǎn)在tj+k時(shí)間槽一定可以工作.因此,根據(jù)覆蓋C的構(gòu)造,在集合Dm中的無源節(jié)點(diǎn)可以在時(shí)間槽tm,tm+k,tm+2k,…工作.

一般而言,|T|>>k,因此我們可以認(rèn)為|T|>>nk,其中,n為正整數(shù).這樣,根據(jù)覆蓋C的構(gòu)造,覆蓋C可被認(rèn)為是集合D中的無源節(jié)點(diǎn)集合的循環(huán)工作.顯然,在每一個(gè)循環(huán)中,其覆蓋質(zhì)量為U(D).這樣,在n個(gè)循環(huán)后的覆蓋質(zhì)量為

定理2.設(shè)C,C′分別為階段1 和階段2 的輸出結(jié)果,則有Q(C′)≥Q(C)=U(D).

證明:顯然,在階段2 中的節(jié)點(diǎn)調(diào)度并沒有減少不相交無源節(jié)點(diǎn)集合D1,D2,…,Dk中的節(jié)點(diǎn),因此我們有Q(C′)≥Q(C).又根據(jù)引理1,我們有Q(C′)≥Q(C)=U(D).□

引理3.給定一個(gè)k′值,我們定義問題P為:構(gòu)造k′個(gè)不相交的無源節(jié)點(diǎn)集合D={D1,D2,…,Dk′},滿足每個(gè)無源節(jié)點(diǎn)的通信半徑,其中且每個(gè)集合中的無源節(jié)點(diǎn)與Sink 節(jié)點(diǎn)的導(dǎo)出圖為連通圖,并最大化U(D).設(shè)Do為該問題的最優(yōu)解,D′為階段1 返回的結(jié)果,則有

證明:在階段1 中,會按照k值從kmin到kmax的順序,根據(jù)貪心思想,迭代地構(gòu)造不相交的無源節(jié)點(diǎn)集合,并選取目標(biāo)函數(shù)值最大的k值.這樣,對于階段1 不同k取值所得到的目標(biāo)函數(shù)值,我們有U(D′)=max{Uk|kmin≤k≤kmax},其中,Uk=U({D1,D2,…,Dk}),且D1,D2,…,Dk為階段1 中當(dāng)k值為k時(shí)的輸出結(jié)果.

這樣,當(dāng)k=|Do|=k′時(shí),我們有U(D′)≥Uk′.又因?yàn)槟繕?biāo)函數(shù)U(?)對于任意k值都是次模的(引理2),這樣,我們有從而有

根據(jù)Shi[2]中的定理4 和定理5,我們給出以下兩個(gè)定理.在這兩個(gè)定理中,我們將給出TPA算法的近似比.設(shè)Co為本問題的最優(yōu)解,CA為TPA算法輸出的解.

定理3.給定一個(gè)無源傳感器網(wǎng)絡(luò)的無源節(jié)點(diǎn)集合V和監(jiān)控周期T,令:

證明:同樣地,構(gòu)造與定理3 中同樣的全局覆蓋,該定理可證.□

值得注意的是:與Shi 等人[4,5,26]的工作不同,我們的問題定義與TPA算法中并沒有對網(wǎng)絡(luò)拓?fù)浜铜h(huán)境中能量源做出假設(shè)和特殊規(guī)定,所以TPA算法在理論上可適用于具有不同的拓?fù)浣Y(jié)構(gòu)和不同能量源的無源傳感器網(wǎng)絡(luò),TPA算法在無源傳感器網(wǎng)絡(luò)中是一個(gè)普適的算法.

4 k-覆蓋擴(kuò)展

在以上章節(jié)中,我們認(rèn)為:若一個(gè)監(jiān)控區(qū)塊被至少一個(gè)無源節(jié)點(diǎn)所監(jiān)控,則該區(qū)塊就被該無源節(jié)點(diǎn)所覆蓋.然而在另一些場景中,由于環(huán)境更加惡劣,導(dǎo)致無源節(jié)點(diǎn)的可靠性降低.因此,對于任意一個(gè)監(jiān)控區(qū)塊而言,需要多個(gè)無源節(jié)點(diǎn)共同對其進(jìn)行監(jiān)控才可以實(shí)現(xiàn)完全覆蓋,這種覆蓋方式被稱為k-覆蓋[30].為了解決這一問題,在本節(jié)中,我們主要討論如何擴(kuò)展CR-MC-BFN 問題和TPA算法,使其可以解決在無源傳感器網(wǎng)絡(luò)中的k-覆蓋問題.

在k-覆蓋中,我們認(rèn)為:在一個(gè)采樣周期(時(shí)間槽)內(nèi),一個(gè)監(jiān)控區(qū)塊可以被覆蓋當(dāng)且僅當(dāng)其被至少k個(gè)無源節(jié)點(diǎn)監(jiān)控.顯然,在k-覆蓋中局部覆蓋與全局覆蓋的定義保持不變.然而,無源節(jié)點(diǎn)能量的不穩(wěn)定性使得無源節(jié)點(diǎn)無法持續(xù)工作,k-覆蓋的要求使得覆蓋的難度加大,因此我們需要重新定義覆蓋質(zhì)量.

定義5(k-覆蓋質(zhì)量).給定一個(gè)全局覆蓋C={Ct|t∈T},對于任意局部覆蓋Ct∈C,其覆蓋質(zhì)量為

這樣,通信半徑可調(diào)整的無源傳感器網(wǎng)絡(luò)k-覆蓋最大化問題(簡稱k-CR-MC-BFN)可描述如下:給定一個(gè)無源傳感器網(wǎng)絡(luò),一個(gè)常數(shù)k,一片監(jiān)控區(qū)域和一個(gè)監(jiān)控周期,輸出一個(gè)全局覆蓋,最大化k-覆蓋質(zhì)量.

顯然,CR-MC-BFN 問題是k-CR-MC-BFN 問題在k=1 時(shí)的子問題.因此,k-CR-MC-BFN 問題也是NP-難問題.為了解決k-CR-MC-BFN 問題,我們提出了k-TPA算法.k-TPA算法基于TPA算法,根據(jù)k-覆蓋質(zhì)量的定義,我們只需將TPA算法中的目標(biāo)函數(shù)改為如下形式,而其他步驟則保持不變:

綜上,我們就解決了在無源傳感器網(wǎng)絡(luò)當(dāng)中的k-覆蓋問題.

5 實(shí)驗(yàn)結(jié)果

5.1 樸素算法

在介紹實(shí)驗(yàn)結(jié)果之前,我們首先提出了如下基于貪心策略的樸素算法(na?ve algorithm),用來與TPA算法進(jìn)行對比.

該算法在任意時(shí)間槽t內(nèi)構(gòu)造局部覆蓋Ct.在任意時(shí)間槽t,該算法將局部覆蓋Ct初始化為空集(Line 3),并執(zhí)行以下步驟.

Step 1(Line 4～Line 12):當(dāng)Ct≠V,或存在V?Ct中的節(jié)點(diǎn)i,且Bi(t)≥Bf時(shí),重復(fù)以下子步驟.

(1) 對于任意i∈V?Ct且Bi(t)≥Bf,設(shè)置節(jié)點(diǎn)i在時(shí)間槽t的通信半徑為.這一步的目的是盡量減少無源節(jié)點(diǎn)的能量消耗;

(2) 對于滿足步驟(1)中條件的無源節(jié)點(diǎn)i,如果集合Ct∪{i}∪S的導(dǎo)出圖是連通圖,則說明將無源節(jié)點(diǎn)i加入局部覆蓋Ct后,覆蓋的連通性可以得到滿足,這樣,為無源節(jié)點(diǎn)i分配權(quán)值:ui=Q(Ct∪{i})?Q(Ct);否則,為無源節(jié)點(diǎn)i分配權(quán)值ui=?1;

(3) 對于所有i∈V?Ct且Bi(t)≥Bf,選取權(quán)值最大的無源節(jié)點(diǎn),并加入局部覆蓋Ct當(dāng)中.

Step 2(Line 13):將Step 1 中所得到的局部覆蓋Ct加入全局覆蓋C中.

Step 3(Line 14):根據(jù)基本能量分布更新無源節(jié)點(diǎn)的能量,即:對于i∈Ct,Bi(t+1)=min{Bi(t)+μi?Δ1,B};對于i≠Ct,Bi(t+1)=min{Bi(t)+μi,B}.在更新無源節(jié)點(diǎn)的能量之后,進(jìn)行下一時(shí)間槽的局部覆蓋的構(gòu)造.

5.2 實(shí)驗(yàn)設(shè)置

我們采用模擬實(shí)驗(yàn)的方式來驗(yàn)證我們的算法.我們假設(shè)監(jiān)控區(qū)域?yàn)橐粋€(gè)50m×50m 的方形區(qū)域,監(jiān)控周期最長為225 分鐘,并被分為45 個(gè)時(shí)間槽,即每個(gè)時(shí)間槽為5 分鐘.我們采用不同的無源節(jié)點(diǎn)來構(gòu)成不同的無源傳感器網(wǎng)絡(luò)來驗(yàn)證算法.我們假設(shè)無源節(jié)點(diǎn)的能量存儲空間B的大小在3mJ 到9mJ 之間,感知半徑在3m 到7m 之間.此外,對于每一個(gè)無源節(jié)點(diǎn),我們假設(shè)其通信半徑具有5 個(gè)等級,分別為,且對于不同的通信半徑等級,無源節(jié)點(diǎn)在一個(gè)時(shí)間槽的能量消耗滿足:

同時(shí),對于每一個(gè)無源節(jié)點(diǎn),我們假設(shè)無源節(jié)點(diǎn)可以工作的最小的能量為3mJ,即Bf=3mJ.此外,我們假設(shè)每個(gè)無源傳輸節(jié)點(diǎn)在每個(gè)時(shí)間槽內(nèi)可以從周圍能源環(huán)境中獲取0.1mJ～0.6mJ 的能量.這樣,我們隨機(jī)地部署200～1 000 個(gè)無源節(jié)點(diǎn)到監(jiān)控區(qū)域當(dāng)中,并構(gòu)成若干個(gè)同構(gòu)的無源傳感器網(wǎng)絡(luò),并在這些網(wǎng)絡(luò)中運(yùn)行TPA算法來驗(yàn)證該算法的性能.

在下面的實(shí)驗(yàn)當(dāng)中,我們將研究無源傳感器網(wǎng)絡(luò)中不同的系統(tǒng)參數(shù)值對于覆蓋質(zhì)量的影響.這些系統(tǒng)參數(shù)包括網(wǎng)絡(luò)中節(jié)點(diǎn)的密度、周圍能源環(huán)境的優(yōu)劣、無源節(jié)點(diǎn)的感知半徑、無源節(jié)點(diǎn)的能量存儲空間、監(jiān)控周期的長度以及能量獲取速率不均衡程度.同時(shí),為了保證實(shí)驗(yàn)的客觀性,我們將TPA算法的實(shí)驗(yàn)結(jié)果與算法2 中的樸素算法以及Shi[2]提出的DSC算法在同樣的實(shí)驗(yàn)環(huán)境下進(jìn)行對比.DSC算法中,無源節(jié)點(diǎn)具有相同的通信半徑,且無法自適應(yīng)地調(diào)節(jié)自身的通信半徑大小.DSC算法具有以下兩個(gè)步驟.

?步驟1:將無源傳感器網(wǎng)絡(luò)中的無源節(jié)點(diǎn)根據(jù)節(jié)點(diǎn)的通信半徑與感知半徑分為k=Δ/μmin個(gè)不相交集合,并最大化無源節(jié)點(diǎn)對監(jiān)控區(qū)域的覆蓋率.其中,μmin為所有節(jié)點(diǎn)在單位時(shí)間槽內(nèi)獲取的最小能量.

?步驟2:無源節(jié)點(diǎn)根據(jù)實(shí)際的能量獲取速率和被分配到的節(jié)點(diǎn)集合進(jìn)行自適應(yīng)地調(diào)度,從而進(jìn)一步最大化節(jié)點(diǎn)對監(jiān)控區(qū)域的覆蓋率,提高覆蓋質(zhì)量.

5.3 不同系統(tǒng)參數(shù)對覆蓋質(zhì)量的影響

5.3.1 網(wǎng)絡(luò)密度的影響

在這個(gè)系列的實(shí)驗(yàn)中,為了研究網(wǎng)絡(luò)密度對覆蓋質(zhì)量的影響,我們模擬了6 種無源傳感器網(wǎng)絡(luò),這6 個(gè)無源傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量分別為100,200,300,500,700,1000.同時(shí),我們假設(shè)在這6 種無源傳感器網(wǎng)絡(luò)中,無源節(jié)點(diǎn)的電量存儲空間為6mJ,監(jiān)控周期長度為40 個(gè)時(shí)間槽(200 分鐘),每個(gè)無源節(jié)點(diǎn)在一個(gè)時(shí)間槽內(nèi)最少獲能為0.2mJ,感知半徑為5m.在這6 種無源傳感器網(wǎng)絡(luò)中,我們分別運(yùn)行樸素算法、TPA算法和DSC算法,并計(jì)算每個(gè)算法所得到的覆蓋質(zhì)量.實(shí)驗(yàn)結(jié)果如圖3 所示.圖3 展示了3 種不同算法在不同無源網(wǎng)絡(luò)下所得覆蓋質(zhì)量的平均值、最大值和最小值.

Fig.3 Impact of number of nodes圖3 節(jié)點(diǎn)數(shù)量的影響

根據(jù)圖3,隨著節(jié)點(diǎn)數(shù)量的不斷增加,網(wǎng)絡(luò)的節(jié)點(diǎn)密度不斷增大,3 種算法所得到的覆蓋質(zhì)量都在不斷上升.這是因?yàn)樵跓o源節(jié)點(diǎn)的感知半徑不變的情況下,增加網(wǎng)絡(luò)節(jié)點(diǎn)的密度,會增加無源節(jié)點(diǎn)對監(jiān)控區(qū)域的覆蓋冗余,即同一塊監(jiān)控區(qū)域可以被更多的無源節(jié)點(diǎn)所覆蓋.同時(shí)我們發(fā)現(xiàn),TPA算法得到的覆蓋質(zhì)量遠(yuǎn)好于樸素算法和DSC算法.在大部分情況下,TPA算法所得到的覆蓋質(zhì)量的最小值均大于樸素算法與DSC算法在相同網(wǎng)絡(luò)參數(shù)下的最大值.平均而言,TPA算法所得到的覆蓋質(zhì)量比DSC算法得到的覆蓋質(zhì)量高23.8%,比樸素算法得到的覆蓋質(zhì)量平均高98.7%.這是因?yàn)樵赥PA算法中,節(jié)點(diǎn)可以自適應(yīng)地調(diào)整自己的通信半徑,從而達(dá)到了更合理利用能量的效果,進(jìn)而增加了節(jié)點(diǎn)工作的可能性,增加了網(wǎng)絡(luò)的覆蓋質(zhì)量.

5.3.2 能量獲取速率的影響

為了研究能量獲取速率對全局覆蓋質(zhì)量的影響,在這一組實(shí)驗(yàn)當(dāng)中,我們控制網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量不變,將網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量設(shè)置為200 個(gè),將無源節(jié)點(diǎn)的感知半徑設(shè)置為5m,設(shè)置Bf=3mJ,B=6mJ.根據(jù)這些系統(tǒng)參數(shù),我們生成6 種無源傳感器網(wǎng)絡(luò),在這6 組無源傳感器網(wǎng)絡(luò)中,我們讓每個(gè)節(jié)點(diǎn)在單位時(shí)間槽內(nèi)的最小能量獲取從0.1mJ 不斷增加至0.6mJ,從而來驗(yàn)證最小能量獲取速率對覆蓋質(zhì)量的影響.同樣地,我們在這6 組無源傳感器網(wǎng)絡(luò)中分別運(yùn)行TPA、樸素算法以及DSC算法.圖4 給出了這3 種算法在不同網(wǎng)絡(luò)中覆蓋質(zhì)量的最大值、平均值和最小值.

Fig.4 Impact of the energy recharging rate圖4 能量獲取速率的影響

顯然,當(dāng)能量獲取速率不斷增加時(shí),3 個(gè)算法所得到的覆蓋質(zhì)量都不斷增加;且在不同的網(wǎng)絡(luò)參數(shù)下,TPA算法所得到的覆蓋質(zhì)量的最小值均大于相同參數(shù)下的DSC 與樸素算法的最大值.當(dāng)能量獲取速率從0.1mJ 增加到0.6mJ 時(shí),TPA算法所得到的覆蓋質(zhì)量增加了2.72 倍.另一方面,TPA算法所得到的覆蓋質(zhì)量在每種能量獲取速率下均優(yōu)于樸素算法和DSC算法所得到的覆蓋質(zhì)量.根據(jù)圖4 中的實(shí)驗(yàn)結(jié)果,TPA算法的性能比DSC算法的性能高26.4%,比樸素算法高39.5%.

5.3.3 感知半徑的影響

節(jié)點(diǎn)的感知半徑是影響網(wǎng)絡(luò)覆蓋質(zhì)量的重要因素.在這組實(shí)驗(yàn)中,我們構(gòu)造5 組不同的無源傳感器網(wǎng)絡(luò),在這5 組不同網(wǎng)絡(luò)中的無源節(jié)點(diǎn)具有不同的感知半徑,分別為3m,4m,5m,6m 和7m.同樣的,我們設(shè)置網(wǎng)絡(luò)中的其他參數(shù)分別為B=6mJ,Bf=3mJ,|V|=200,且每個(gè)節(jié)點(diǎn)在每個(gè)時(shí)間槽的最小獲能為0.2mJ.在圖5 中,我們展示了將3種算法在這5 組網(wǎng)絡(luò)中分別運(yùn)行后的統(tǒng)計(jì)結(jié)果,并記錄了在不同網(wǎng)絡(luò)下,3 種算法所取得的覆蓋質(zhì)量的最大值、最小值和平均值.

Fig.5 Impact of sensing radius圖5 感知半徑的影響

顯然,當(dāng)無源節(jié)點(diǎn)的感知半徑逐漸增大時(shí),3 種算法所取得的覆蓋質(zhì)量也不斷增加.然而,我們同樣發(fā)現(xiàn),當(dāng)節(jié)點(diǎn)的感知半徑非常小,即為3m 時(shí),3 種算法所得到的覆蓋質(zhì)量基本相同.但是,隨著無源節(jié)點(diǎn)的感知半徑逐漸增加,TPA算法所獲取的覆蓋質(zhì)量迅速增加.當(dāng)感知半徑從3m 增加到7m 時(shí),TPA算法所得到的覆蓋質(zhì)量增加了約4.3 倍.然而對于樸素算法,隨著感知半徑的增加,覆蓋質(zhì)量的增加速度并不高.根據(jù)實(shí)驗(yàn)數(shù)據(jù)的統(tǒng)計(jì)結(jié)果,TPA算法所獲取的覆蓋質(zhì)量比樸素算法所獲得的覆蓋質(zhì)量平均高45%,比DSC算法所得到的覆蓋質(zhì)量平局高30.4%.

5.3.4 能量存儲空間的影響

顯然,當(dāng)無源節(jié)點(diǎn)配備較大的能量存儲器件(一般為超級電容)時(shí),節(jié)點(diǎn)可以工作更長的時(shí)間.為了研究不同大小的能量存儲空間對全局覆蓋質(zhì)量的影響,我們考慮了7 種不同的無源節(jié)點(diǎn),并根據(jù)這7 種無源節(jié)點(diǎn)構(gòu)造了7組同構(gòu)的無源傳感器網(wǎng)絡(luò).這7 種不同的無源節(jié)點(diǎn)分別配備不同大小的能量存儲器件,能量存儲空間大小分布從3mJ 到9mJ.在構(gòu)造的7 組同構(gòu)的無源傳感器網(wǎng)絡(luò)中,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目均為200,無源節(jié)點(diǎn)在每個(gè)時(shí)間槽內(nèi)的最小能量獲取為0.2mJ,感知半徑為5m,節(jié)點(diǎn)可工作的最小能量為Bf=3mJ.同樣地,我在這7 組網(wǎng)絡(luò)中分別運(yùn)行TPA、DSC 和樸素算法,并記錄3 個(gè)算法在不同網(wǎng)絡(luò)下的覆蓋質(zhì)量的最大值、平均值和最小值.圖6 中表示了這3 種算法的運(yùn)行結(jié)果.

Fig.6 Impact of the size of B圖6 B 值大小的影響

根據(jù)圖6 中的實(shí)驗(yàn)結(jié)果,當(dāng)能量存儲空間不斷增加時(shí),樸素算法所取得的覆蓋質(zhì)量不斷增加,而DSC,TPA算法所取得的覆蓋質(zhì)量隨能量存儲空間的變化并不明顯.這是因?yàn)樵贒SC 和TPA算法構(gòu)造覆蓋時(shí),并沒有考慮能量存儲空間;而樸素算法由于采用貪心算法,在監(jiān)控周期的初始,十分依賴能量的存儲空間.當(dāng)能量存儲空間從3mJ 增長到9mJ 時(shí),TPA算法所取得的覆蓋質(zhì)量僅增加了約1.11 倍.因此,我們可以說TPA算法是不受能量存儲空間所影響的.因此,對于不同的能量存儲空間,TPA算法均可以保障穩(wěn)定的覆蓋質(zhì)量.根據(jù)圖6 中的實(shí)驗(yàn)結(jié)果,TPA算法的性能比DSC算法平均高31.9%,比樸素算法的性能平均高80.38%.

5.3.5 監(jiān)控周期長度的影響

在無源傳感器網(wǎng)絡(luò)中,由于網(wǎng)絡(luò)壽命在能量上來講是無限的,因此,研究監(jiān)控周期對網(wǎng)絡(luò)覆蓋質(zhì)量的影響是必要的.在這組實(shí)驗(yàn)中,我們固定無源節(jié)點(diǎn)的參數(shù),將無源節(jié)點(diǎn)的感知半徑設(shè)為5m,能量存儲空間設(shè)為6mJ,節(jié)點(diǎn)工作的最低電量為Bf=3mJ,在每個(gè)時(shí)間槽內(nèi)的能量獲取量為0.2mJ.同時(shí),我們設(shè)置網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)量為200.為了研究監(jiān)控周期的影響,我們將網(wǎng)絡(luò)的監(jiān)控周期從20 個(gè)時(shí)間槽不斷增加到45 個(gè)時(shí)間槽,并在不同的監(jiān)控周期下分別運(yùn)行TPA,DSC 和樸素算法.圖7 中記錄了3 種算法在不同監(jiān)控周期長度下的全局覆蓋質(zhì)量的最大值、最小值和平均值.

我們發(fā)現(xiàn),TPA算法和DSC算法在任意長度監(jiān)控周期下所取得的覆蓋質(zhì)量的最大值、平均值以及最小值的變化并不明顯.這是因?yàn)門PA算法和DSC算法首先計(jì)算了k個(gè)節(jié)點(diǎn)集合,并在整個(gè)監(jiān)控周期中不斷調(diào)度同樣的k個(gè)節(jié)點(diǎn)集合,這樣,兩種算法所取得的覆蓋質(zhì)量主要取決于這k個(gè)節(jié)點(diǎn)集合所獲得的覆蓋質(zhì)量.相反地,由于樸素算法僅根據(jù)每個(gè)時(shí)間槽內(nèi)的節(jié)點(diǎn)能量來調(diào)度節(jié)點(diǎn)工作,這就導(dǎo)致了當(dāng)監(jiān)控周期變長,節(jié)點(diǎn)初始能量被消耗殆盡后,所取得的覆蓋質(zhì)量不斷降低.總體而言,TPA算法所取得的覆蓋質(zhì)量平均是樸素算法的覆蓋質(zhì)量的1.73倍,是DSC算法所取得的覆蓋質(zhì)量的1.36 倍.

Fig.7 Impact of the length of monitoring duration圖7 監(jiān)控周期長度的影響

5.3.6 能量獲取速率不均衡程度的影響

能量獲取速率的不均衡程度,是影響無源網(wǎng)絡(luò)覆蓋質(zhì)量的重要因素.為了探究能量獲取不均衡程度的影響,我們利用μmax?μmin的值來衡量能量分布的不均衡程度.其中,μmax,μmin分別為節(jié)點(diǎn)在一個(gè)時(shí)間槽內(nèi)所獲能量的最大值與最小值.在這組實(shí)驗(yàn)中,我們假設(shè)每個(gè)無源節(jié)點(diǎn)在單位時(shí)間槽內(nèi)所獲得的能量在[μmin,μmax]中隨機(jī)變化.我們固定μmax=0.6mJ,并將μmin的值從0.6mJ逐漸減小到0.1mJ.顯然,當(dāng)μmax?μmin的值越大,節(jié)點(diǎn)的能量獲取速率的不均衡程度就越嚴(yán)重.在這組實(shí)驗(yàn)中,我們固定網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目為200,將無源節(jié)點(diǎn)的感知半徑設(shè)為5m.

為了研究能量獲取速率不均衡程度的影響,我們將μmax?μmin的值從0mJ 逐漸增大到0.5mJ,在不同的網(wǎng)絡(luò)參數(shù)下運(yùn)行TPA,DSC 和樸素算法,并記錄3 種算法所取得的覆蓋質(zhì)量的最大值、最小值和平均值.實(shí)驗(yàn)結(jié)果記錄在圖8 中.

Fig.8 Impact of the energy deviation圖8 能量偏移的影響

顯然,根據(jù)圖8 中的實(shí)驗(yàn)結(jié)果,我們發(fā)現(xiàn),隨著能量獲取不均衡程度的逐漸加深,3 種算法說獲得的覆蓋質(zhì)量不斷降低,并且每種算法所取得的覆蓋質(zhì)量的最大值與最小值之間的差距也逐漸加大.當(dāng)μmax?μmin的值從0 增加到0.5 時(shí),TPA算法所取得的覆蓋質(zhì)量降低了越31%.這說明隨著能量獲取不均衡程度的加大,網(wǎng)絡(luò)中節(jié)點(diǎn)工作狀態(tài)更加不穩(wěn)定.然而,我們也可以發(fā)現(xiàn),TPA算法在不同的不均衡程度下所取得的覆蓋質(zhì)量均優(yōu)于DSC算法與樸素算法.總體而言,TPA算法的性能比DSC算法的性能高20%,比樸素算法高30%.這是因?yàn)門PA算法在第二階段中充分考慮了網(wǎng)絡(luò)中能量獲取不均衡時(shí)的情況,并自適應(yīng)地調(diào)整了在階段一中所得到的節(jié)點(diǎn)的調(diào)度,從而使得TPA算法在節(jié)點(diǎn)獲能不均衡時(shí),也能保障一定的覆蓋質(zhì)量.

6 總結(jié)

在本文中,我們提出了一個(gè)基于多等級通信半徑的無源傳感器網(wǎng)絡(luò)中的覆蓋問題.在這個(gè)問題中,無源傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)可以自適應(yīng)地調(diào)整自己的通信半徑,從而進(jìn)一步合理地使用獲取的能量.我們證明了該問題是NP-Hard 問題,并提出了基于貪心策略的TPA算法來解決這個(gè)問題.我們分析了該算法的時(shí)間復(fù)雜度,并證明了該算法具有一個(gè)合適的近似比.此外,我們還通過模擬實(shí)驗(yàn)來對算法的性能進(jìn)行評估.為此,我們還提出了一個(gè)與TPA算法進(jìn)行對比的樸素算法.基于我們的實(shí)驗(yàn)結(jié)果,我們驗(yàn)證了TPA算法的有效性和可靠性.在本文中,監(jiān)控區(qū)域中環(huán)境能量源的基本能量分布主要基于歷史數(shù)據(jù).這一數(shù)據(jù)的準(zhǔn)確與否,對于本文所提出的算法具有關(guān)鍵的影響.若該數(shù)據(jù)誤差較大,則會影響無源節(jié)點(diǎn)的調(diào)度.在未來的工作中,我們將研究如何減少對周圍環(huán)境能量源歷史數(shù)據(jù)的依賴,從而進(jìn)一步提高算法的性能與效率.