周 佳，王 然

(杭州電子科技大學(xué) 計算機學(xué)院,浙江 杭州 310018)

覆蓋問題是無線傳感網(wǎng)絡(luò)中的常見問題。根據(jù)所監(jiān)測實體的不同，覆蓋問題被分為區(qū)域覆蓋[1-3]、目標覆蓋[4-6]和柵欄覆蓋[7-8]等問題。傳感器監(jiān)測模型分為0-1圓盤模型和概率模型。傳感器類型分為全向傳感器和定向傳感器。

與傳統(tǒng)0-1監(jiān)測模型不同，概率監(jiān)測模型是一種更加接近實際的監(jiān)測模型[9]。傳感器對目標的監(jiān)測結(jié)果并不是確定的0或者1，而是一個與傳感器材質(zhì)和距離相關(guān)的概率。文獻[10]研究了在概率目標覆蓋中的最少節(jié)點選擇問題，通過每次選擇增益最多使傳感器形成覆蓋集合。文獻[11]提出了在柵欄覆蓋中的一種概率模型，通過網(wǎng)絡(luò)流的方法得到最小權(quán)重的柵欄。文獻[12]研究了在可移動傳感器網(wǎng)絡(luò)中使用概率模型的方法，通過將傳感器節(jié)點分類，每一輪重新規(guī)劃傳感器位置使各個目標周圍傳感器更加均衡，以此來延長網(wǎng)絡(luò)壽命。

定向傳感器已被應(yīng)用到越來越多的領(lǐng)域中，例如攝像傳感器、紅外傳感器[13]。文獻[14]中使用了一種非重疊定向監(jiān)測模型。該模型中，傳感器的監(jiān)測角固定，偏轉(zhuǎn)角可以是預(yù)設(shè)的幾個方向之一。該研究使用遺傳算法來確定每一輪應(yīng)該開啟的方向，通過多輪迭代得到最大網(wǎng)絡(luò)壽命。文獻[15]提出了一種非重疊定向模型，給定傳感器的監(jiān)測角后，可以根據(jù)實際情況偏轉(zhuǎn)任意角度。文獻[16]提出了在柵欄覆蓋中使用定向傳感器，并以此構(gòu)造強柵欄覆蓋。該研究考慮了在一維直線和二維平面情況下使傳感器的偏轉(zhuǎn)角度總和最小。

上述文獻在求解網(wǎng)絡(luò)壽命時，都沒有考慮到目標權(quán)重的影響。本文研究了概率感知模型下的定向目標覆蓋的最大網(wǎng)絡(luò)壽命問題，考慮了目標的權(quán)重對網(wǎng)絡(luò)壽命的影響。每一輪得到新的定向覆蓋集合，通過多輪睡眠喚醒調(diào)度使總的網(wǎng)絡(luò)壽命最大。

1 問題定義

1.1 監(jiān)測模型

非重疊的概率定向感知模型對應(yīng)的數(shù)學(xué)表達式如式(1)所示。其中，α為與傳感器材質(zhì)和功率相關(guān)的強度系數(shù)；di,j表示傳感器和目標的距離；φs和φa分別表示傳感器和目標與水平方向的夾角；θ表示傳感器監(jiān)測的張角。

(1)

對于任意一個傳感器，可以用對應(yīng)的四元組表示，即γi=(Li,Rs,θ,k)，分別對應(yīng)了位置、監(jiān)測半徑、監(jiān)測角和選擇的方向。一旦確定這幾個元素就能夠知道目標是否被監(jiān)測，以及對應(yīng)的監(jiān)測概率。對于偏轉(zhuǎn)角和方向選擇的關(guān)系如式(2)所示，傳感器的監(jiān)測范圍為φs～φs+θ。

φs=(k-1)·θ

(2)

如圖1所示，此時傳感器有3個可選擇的方向，對應(yīng)的監(jiān)測張角為120°。此時傳感器偏轉(zhuǎn)到了方向2，可以監(jiān)測到目標a1,對應(yīng)的偏轉(zhuǎn)角為120°。目標a2雖然在監(jiān)測半徑的范圍內(nèi)，但是不在對應(yīng)的方向內(nèi)，所以無法被監(jiān)測到。a3在對應(yīng)的方向，但是其與傳感器的距離已經(jīng)超出了監(jiān)測半徑，所以也無法被監(jiān)測。

圖1 概率定向模型

如果目標aj在距離Rs之內(nèi)的所有傳感器集合為Ω，要使a至少滿足的監(jiān)測概率為ε，那么必然會有式(3)對應(yīng)的關(guān)系。

1-∏si∈Ω(1-pi,j)≥ε

(3)

對式(3)進行對數(shù)轉(zhuǎn)換可以得到如式(4)所示的對應(yīng)計算式。

1-ε≥∏si∈Ω(1-pi,j)?
ln(1-ε)≥∑si∈Ωln(1-pi,j)?
-ln(1-ε)≤∑si∈Ω-ln(1-pi,j)

(4)

通過數(shù)學(xué)變化可以將概率轉(zhuǎn)化為對數(shù)形式的累加。-ln(1-ε)表示增益閾值，對應(yīng)每個目標的最低概率要求，使用Ψ來表示。傳感器si對目標aj的概率則可以用-ln(1-pi,j)形式的增益等價代替，被定義為傳感器si對目標aj的監(jiān)測增益，用gi,j來表示。

1.2 形式化定義

定義1閾值半徑。傳感器si對目標aj必然存在距離d使得pi,j=ε，那么只要傳感器和目標的距離小于d，必然能夠直接滿足監(jiān)測概率要求。這個距離被定義為閾值半徑，用Rm表示。閾值半徑的計算式為

(5)

在圖2中，s1和s2對目標的增益分別為3.4和2.4。如果先開啟s1監(jiān)測目標，目標a的積累增益為3.4。再開啟s2，a的積累增益變成5.8，超出了給定的閾值5.0。因此，s2對目標的有效增益為1.6，溢出增益為0.8。

圖2 各種類型增益

定義5ε-定向覆蓋。給定長為L、寬為H的區(qū)域，在這片區(qū)域里有給定的待監(jiān)測目標集合A={a1,…,aN}和隨機拋灑的傳感器集合S={s1,…，sM}。S中的傳感器都是定向傳感器，需要從S中選擇部分傳感器開啟某個方向，使所有目標達到最低的概率要求ε；

1.3 NP-hard證明

定理1ε-定向覆蓋最大網(wǎng)絡(luò)壽命問題是NP-hard問題。

文獻[17]已經(jīng)證明了在0-1模型下定向傳感器大網(wǎng)絡(luò)壽命問題是一個NP-hard問題，接下來通過概率模型到0-1模型的轉(zhuǎn)化來說明ε-定向覆蓋最大網(wǎng)絡(luò)壽命問題也是NP-hard。如圖3所示，假設(shè)s1、s2和s3是半徑為Rs的定向傳感器，采用的是概率感知模型。此時傳感器對應(yīng)的閾值半徑為Rm，那么顯然無論開啟s1、s2和s3中的任意一個都能夠使目標a直接滿足概率要求。如果將s1、s2和s3替換成監(jiān)測半徑為Rm的定向0-1模型傳感器，也是只需要開啟任何一個都能夠達到監(jiān)測目標的效果，由此可見這兩種形式是等價的。即任意半徑為Rm的定向0-1覆蓋問題都會有對應(yīng)半徑為Rs的定向ε-定向覆蓋問題。

圖3 NP-hard證明

綜上，以感知半徑為Rm的確定0-1定向傳感器只是半徑為Rs的概率定向傳感器的一種特殊情況。所以本文提出的最小ε-定向覆蓋最大網(wǎng)絡(luò)壽命問題也是一個NP-hard問題。

1.4 目標和約束條件

式(6)～式(8)通過精確的數(shù)學(xué)表達式來描述ε-定向覆蓋最大網(wǎng)絡(luò)壽命問題，包括了最終的優(yōu)化目標和所需滿足的約束條件。

(6)

(7)

(8)

(9)

xi,w,k∈{0,1},τk>0

(10)

2 算法設(shè)計

本文已經(jīng)證明了ε-定向覆蓋最大網(wǎng)絡(luò)壽命問題是一個NP-hard問題，無法在多項式的時間內(nèi)找出最優(yōu)解，因此需要提出與之對應(yīng)的啟發(fā)式算法。這個問題的關(guān)鍵就在于ε-定向覆蓋集合的選擇。如果每次迭代都能夠選擇出優(yōu)秀的傳感器集合，必定能夠提高能效，延長整體的網(wǎng)絡(luò)壽命。因此，本文提出了基于目標權(quán)重的優(yōu)先選擇算法(Target Weight Preference Algorithm，TWP)。

2.1 基于目標權(quán)重的優(yōu)先選擇算法

圖4 潛在積累增益的差距

通過潛在可行增益來確定權(quán)重，權(quán)重越大說明應(yīng)該優(yōu)先考慮。權(quán)重的計算如式(11)所示，其中v表示所有節(jié)點的平均增益。首先按照目標為基準，逐個計算出權(quán)重，將目標按照權(quán)重進行排序。按照排序的順序得出目標周圍距離小于Rs的傳感器集合，從集合中選擇一個傳感器開啟對應(yīng)的方向。節(jié)點的選擇需要綜合考慮剩余能量和有效增益，因此使用式(12)來計算優(yōu)先系數(shù)。對于傳感器si，其優(yōu)先系數(shù)會綜合考慮到剩余能量和總增益大小，使用hi來表示。

(11)

(12)

圖5給出了為選擇傳感器的實例。目標a能夠被兩個傳感器監(jiān)測，假設(shè)a對應(yīng)的集合就是{s1,s2}，g(s1,a)=2，g(s2,a)=3.2，總能量為10且s1和s2剩余能量分別為8和2，那么相應(yīng)的ρ1=1.6，ρ2=0.64，最終所選擇的傳感器應(yīng)該是s1。由此可見單純的增益和能量都無法代表傳感器的優(yōu)先級，只有綜合兩類因素最優(yōu)的才會被選擇。

圖5 傳感器選擇的舉例

TWP算法首先需要得到每個目標周圍的傳感器集合，然后計算出目標的潛在積累增益，并使用潛在積累增益計算權(quán)重，按照權(quán)重為目標排序。對于某個目標周圍的傳感器集合，要優(yōu)先開啟優(yōu)先級最高的傳感器。而優(yōu)先級的計算方式已經(jīng)在式(12)中定義，開啟一個傳感器對應(yīng)方向后就可以更新一個或多個目標的積累增益。為了使當前目標達到增益閾值，要按照優(yōu)先級選擇多個傳感器。當完成一個目標后，就可以按照順序為下一個目標尋找傳感器集合，并通過同樣的方式得到開啟的傳感器。當所有目標都迭代完成以后，就會得到每個目標的監(jiān)測集合，合并之后即為完整的覆蓋集合。當一輪完成后，需要更新傳感器剩余能量，如果有傳感器能量耗盡，就需要重新更新權(quán)重。

假設(shè)給定給的時間片為t，如果傳感器剩余能量充足，那么當前這一輪就可以直接運行時間t。對于第i輪調(diào)度運行的時間τi如式(13)所示，其中min (RE(si))表示當前這輪選擇的傳感器集合中剩余能量最小的，es表示單位運行時間t需要的能量。

(13)

TWP算法的具體步驟如下：

輸入傳感器集合S；目標集合A；時間片t；最低監(jiān)測ε；增益閾值Ψ；單位時間能耗es；監(jiān)測半徑Rs；初始能量Es。

輸出運行的總時間T。

初始化變量：T←0

1.while each target can be covered do

3.Ω←?

4.計算每個目標的潛在積累增益

5.通過公式11得到目標權(quán)重

6.將A中目標按照權(quán)重排序

7.fora∈Ado

8.計算a周圍距離小于Rs的集合φa

9.計算a對應(yīng)于傳感器的方向

10.從φa中重復(fù)選擇hi最大的傳感器s

11.開啟s對應(yīng)的方向

12.更新s能監(jiān)測的所有目標增益

13.Ω←Ω∪s

14.end for

15. end while

16.計算Ω中剩余能量能否滿足t

17.if satisfyτi=t

19.更新Ω中傳感器運行τi后的能量

20.T←T+τi

21.end while

2.2 算法分析

定理3TWP算法的時間復(fù)雜度為O(M×N+MlogM)。

在為目標計算潛在積累增益時，需要為M個目標計算周圍的傳感器集合。由于無法確定目標周圍傳感器數(shù)量，那么最多可能會有N個傳感器，需要計算的次數(shù)為M×N。在根據(jù)潛在積累增益進行排序，時間復(fù)雜度為MlogM。最后按照順序為每個目標先擇傳感器，需要計算優(yōu)先系數(shù)。每個目標最多需要計算N次，那么M個最多目標需要計算M×N次。而調(diào)度的輪次假設(shè)為K，綜合總的需要時間為K(M×N+MlogM+M×N)。由于K必定是一個常數(shù)，所以時間復(fù)雜度為M×N+MlogM。

3 模擬實驗

實驗中所有傳感器都是隨機拋灑到100 m×100 m的區(qū)域中，監(jiān)測半徑為15 m，默認設(shè)置的監(jiān)測角為2π/3。與傳感器物理特性相關(guān)的系數(shù)α為0.05，默認最低監(jiān)測概率為ε=0.85。默認放置的傳感器數(shù)量為200，目標數(shù)量為50，傳感器初始能量為15 kJ，在時間片t全向開啟(這里的單位時間指的是比較長的一段時間)時監(jiān)測能耗為6 kJ。能耗與監(jiān)測角度相關(guān)，例如監(jiān)測角為π時的能耗是監(jiān)測角為2π時的一半。為了保證準確性，所有實驗都是在50次隨機結(jié)果下的平均值。

圖6表示在不同監(jiān)測角下網(wǎng)絡(luò)壽命隨著傳感器數(shù)量的變化，設(shè)置的監(jiān)測角分別為2π、π、2π/3、和π/2?？梢钥吹诫S著節(jié)點數(shù)量增加，網(wǎng)絡(luò)壽命都會延長。監(jiān)測角越小，對應(yīng)的網(wǎng)絡(luò)壽命也更長。這是由于監(jiān)測角越小對應(yīng)的能耗越小，減少了能量的浪費。

圖6 不同監(jiān)測角的比較

圖7為不同目標數(shù)量下，網(wǎng)絡(luò)壽命隨著傳感器數(shù)量的變化。監(jiān)測角設(shè)定為2π/3，最小監(jiān)測概率為ε=0.85?？梢钥闯鲂枰O(jiān)測的目標數(shù)量越多，對應(yīng)的網(wǎng)絡(luò)壽命就越小。這是由于目標增多后，每一輪選擇的覆蓋集合對應(yīng)的傳感器數(shù)量會增加，對應(yīng)的總能耗會增大。

圖7 不同目標數(shù)量的比較

圖8中將TWP算法與文獻[15]中的HMCS算法和文獻[10]中的PSCM算法進行了比較。監(jiān)測角為2π/3時，在不同的最小監(jiān)測概率下最大的網(wǎng)絡(luò)壽命如圖8所示。隨著目標監(jiān)測概率的提高，網(wǎng)絡(luò)壽命會逐漸變小，這是因為隨著增益閾值變大單個目標周圍需要開啟的傳感器數(shù)量增加了。從結(jié)果可以看出，TWP算法比另外兩種算法表現(xiàn)更加優(yōu)異。

圖8 不同算法網(wǎng)絡(luò)壽命的比較

圖9顯示出了3種算法在不同初始傳感器數(shù)量下調(diào)度結(jié)束之后剩余能量的方差。可以看出，TWP算法由于考慮到權(quán)重更小的瓶頸節(jié)點，所以能量使用更加均衡，這也是其能夠延長網(wǎng)絡(luò)壽命的重要原因之一。

圖9 不同算法剩余能量方差

4 結(jié)束語

本文研究了概率定向傳感器的目標覆蓋問題，并提出了最大網(wǎng)絡(luò)壽命的優(yōu)化目標。為了解決這個問題，本文將概率轉(zhuǎn)化為增益，提出了積累增益、有效增益等概念，并證明了這是一個NP-hard問題。本文提出了基于權(quán)重的優(yōu)先選擇算法，將潛在積累增益轉(zhuǎn)化為權(quán)重，并將權(quán)重應(yīng)用到目標排序和節(jié)點選擇的過程中。最后，通過對比實驗證明了本文所提出算法的有效性。