無線傳感器網(wǎng)絡中一種延長壽命的覆蓋算法*

崔彥新,劉三陽,馮海林

(西安電子科技大學理學院,西安 710071)

無線傳感器網(wǎng)絡由大量的傳感器節(jié)點組成,這些節(jié)點隨機部署或者固定安置在監(jiān)測區(qū)域,以感知、采集和處理監(jiān)測區(qū)域中被測對象的信息,它們使用自身攜帶的電池供電,因此,有效且合理地利用有限的能量是無線傳感器網(wǎng)絡設計的核心[1-2],最小化能量消耗并最大化網(wǎng)絡壽命成為無線傳感器網(wǎng)絡研究的熱點之一。

現(xiàn)有的延長網(wǎng)絡壽命的方法通常是在已知節(jié)點地理位置信息的條件下進行的,但是獲取地理位置信息需要的開銷很大,并且精度難以保證。若所獲得的地理位置信息有誤差,則許多延長壽命的算法就達不到預期的效果。Gaurav S.Kasbekar等人在文獻[3]中第一次提出了一種分布式無坐標的調(diào)度機制,在保證完全覆蓋的條件下,延長了網(wǎng)絡壽命。算法需要精確的節(jié)點間的距離信息,可以通過文獻[4-5]中提到的方法來確定。

但是文獻[3]中的 DLM算法有一個明顯的不足,就是 DLM算法一旦探測到覆蓋空洞即告終止,即使網(wǎng)絡中大量的節(jié)點還有很多的能量儲備。這樣不利于能量的有效利用[6]。如果可以將有能量儲備的節(jié)點的能量利用起來,必然會很好的延長網(wǎng)絡的壽命。因此,為了提高節(jié)點能量的利用率,本文在DLM算法基礎上進行了改進,將傳統(tǒng)的節(jié)點“休眠或激活”調(diào)度機制一般化,提出一種調(diào)整感知半徑的節(jié)點調(diào)度算法 ASR-DLM(Ad justable Sensing Range-Distributed Lifetime Maximization)。這種方法有以下優(yōu)點：①因為能量的消耗與感知半徑的大小有直接的關系,感知半徑越大,消耗的能量就越多,本文算法通過調(diào)整感知半徑的大小,可以省去由于多余的覆蓋而產(chǎn)生的能量浪費,提高能量的利用率。②ASR-DLM還可以完成對覆蓋空洞的探測與填補?，F(xiàn)有的覆蓋空洞探測與填補的方法都是基于精確的地理位置信息的,而本文的算法不需要地理位置信息,節(jié)省了使用 GPS及信標節(jié)點的成本。另外,與需要地理位置信息的算法相比,可以避免由于定位誤差的存在而影響網(wǎng)絡服務質(zhì)量。③與 DLM算法相比,DLM算法在探測到覆蓋空洞時終止,壽命結(jié)束,本文的算法可以對探測到的覆蓋空洞進行填補,大大延長了網(wǎng)絡壽命。

1 網(wǎng)絡模型

1.1 網(wǎng)絡描述

考慮由n個傳感器節(jié)點集合 S組成的無線傳感器網(wǎng)絡,傳感器節(jié)點隨機地分布在矩形區(qū)域。本文假設傳感器節(jié)點的監(jiān)測范圍和通信區(qū)域滿足單位圓性質(zhì)[7]。傳感器節(jié)點的感知半徑可以調(diào)整,節(jié)點 u的感知半徑集合用 Rs(u)表示,Rs(u)={r(1),r(2),…,r(p)},其中,r(1)表示傳感器節(jié)點感知半徑最小值;r(p)表示感知半徑最大值。傳感器節(jié)點的通信半徑固定,用Rc表示。如果傳感器網(wǎng)絡中節(jié)點的通信半徑大于兩倍的感知半徑,且無線傳感器網(wǎng)絡滿足覆蓋,則此網(wǎng)絡為連通網(wǎng)絡[7]。本文假設傳感器節(jié)點的通信半徑大于兩倍的感知半徑,則有 Rc＞2 r(p)。

另外,根據(jù)文獻[3]中的要求,因為傳感器節(jié)點不知道全局位置信息,所以,選擇的節(jié)點部署區(qū)域比監(jiān)測區(qū)域稍大一點。位于監(jiān)測區(qū)域邊界上的節(jié)點稱為外圍節(jié)點;位于監(jiān)測區(qū)域內(nèi)部的節(jié)點稱為內(nèi)部節(jié)點。每個節(jié)點可以根據(jù)文獻[8-9]中提出的方法判斷自己是外圍節(jié)點還是內(nèi)部節(jié)點。

1.2 模型假設

假設以下條件可以滿足：

(1)假設可以得到兩個節(jié)點相互之間的精確距離。

(2)傳感器節(jié)點有著同步的時鐘。

(3)每個傳感器節(jié)點初始能量 B。

(4)處于休眠模式的傳感器節(jié)點幾乎不消耗能量,我們假定為 0。

(5)用 ek表示節(jié)點感知半徑為 k時,單位時間消耗的能量,其中 eu(k)=cs?r2(k),其中 cs為感知系數(shù)[6]。

(6)用 tk表示節(jié)點通信時消耗的能量,則 tk=ρ?ct?Tr4(u),19≤cs：ct≤35,其中,Tr(u)表示通信距離,ρ表示通信密度,例如 ρ=0.1表示 10個單位時間通信一次[6]。

2 預備知識

定義 1覆蓋集：對于一個傳感器節(jié)點組成的集合 C?S,若 C中的傳感器節(jié)點的感知區(qū)域可以把監(jiān)測區(qū)域完全覆蓋,則稱 C為一個傳感器覆蓋集,這里簡稱為覆蓋集[3]。

定義 2覆蓋空洞：傳感器網(wǎng)絡中如果存在一片連續(xù)的區(qū)域不被任何傳感器節(jié)點的感知范圍所覆蓋,那么這片未被監(jiān)測的連續(xù)區(qū)域稱為一個覆蓋空洞[7]。

定義 3如果兩個傳感器節(jié)點 u,v∈S的感知圓盤相交,則稱這兩個節(jié)點交叉。感知圓盤邊界相交的兩個交點稱為交叉點[3]。

性質(zhì) 1節(jié)點 u,v∈S的感知半徑分別為 ru和rv,節(jié)點 u,v之間的距離記為 du,v,則它們是相交的當且僅當du,v＜ru+rv,du,v+ru＞rv,du,v+rv＞ru[3]。

性質(zhì) 2考慮一個覆蓋 C?S,設 u∈C與任何其他傳感器節(jié)點都不交叉,則 C-{u}也是一個覆蓋[3]。

定理 1考慮一個集合 C?S,C是一個覆蓋集當且僅當 C中節(jié)點的感知區(qū)域可以覆蓋 P中所有點[3]。設 P是監(jiān)測區(qū)域內(nèi)部所有交叉點組成的集合,簡稱為交叉點集。

推論 1在無線傳感器網(wǎng)絡工作時,設激活的傳感器節(jié)點組成的集合為 A,P是交叉點集,若 A中節(jié)點的感知范圍不能將 P中所有點覆蓋,則覆蓋空洞產(chǎn)生。

證明因為A中節(jié)點的感知范圍不能將 P中所有點覆蓋,根據(jù)定理 1,A不是一個傳感器覆蓋集,不能將監(jiān)測區(qū)域完全覆蓋,因此覆蓋空洞產(chǎn)生。證畢。

根據(jù)推論 1,可以進行覆蓋空洞的探測,本文的ASR-DLM算法就是根據(jù)推論 1進行覆蓋空洞的探測。

用到的術(shù)語：

空洞邊緣節(jié)點 傳感器網(wǎng)絡中如果存在一個傳感器節(jié)點,其感知范圍邊緣某段圓弧未被其它傳感器節(jié)點的感知區(qū)域所覆蓋,則稱節(jié)點為空洞邊緣節(jié)點[7]。

圖1 覆蓋空洞

空洞邊緣交叉點 傳感器網(wǎng)絡中如果存在兩個空洞邊緣節(jié)點互為感知鄰居,且這兩個傳感器節(jié)點中存在一個交叉點,不被這兩個節(jié)點之外的第 3個節(jié)點的感知范圍所覆蓋,則稱該交叉點為空洞邊緣交叉點[7]。簡稱邊緣交叉點。

空洞邊緣鄰居 傳感器網(wǎng)絡中如果兩個節(jié)點互為感知鄰居并且這兩個節(jié)點之間的交叉點至少有一個為空洞邊緣交叉點,則這兩個節(jié)點互為空洞邊緣鄰居[7]。

空洞環(huán) 傳感器網(wǎng)絡中相鄰的空洞邊緣節(jié)點組成的集合,與集合中節(jié)點的鄰居組成的并集。如圖2所示。

圖2 空洞環(huán)

如圖 2所示,{A,B,C,D,E,F,G}形成一個空洞環(huán),{a,b,c,d,e,f,g}是空洞邊緣交叉點。

3 問題與算法設計

3.1 問題陳述

最大化網(wǎng)絡壽命問題是指在滿足服務質(zhì)量(如覆蓋、連通等)條件下,采用節(jié)點輪換調(diào)度模式,輪換激活/休眠模式,每一輪中僅將部分節(jié)點投入活躍工作狀態(tài),而將冗余節(jié)點投入低功耗的睡眠狀態(tài),這樣可以達到減少能量消耗和延長網(wǎng)絡壽命的目的[3]。

文獻[3]中DLM算法有初始化和激活兩個階段。首先初始化整個網(wǎng)絡,使每個節(jié)點獲知網(wǎng)絡參數(shù),這個步驟在網(wǎng)絡開始運行時執(zhí)行一次。然后,在每個子時間段開始時,即每一輪開始時,進入激活階段。每個激活階段選取一個最優(yōu)的覆蓋集,將最優(yōu)覆蓋集中的節(jié)點投入激活狀態(tài),開始工作,直到子時間段的結(jié)束。但是文獻[3]中的 DLM算法有一個明顯的不足,就是 DLM算法一旦探測到覆蓋空洞即告終止,即使網(wǎng)絡中大量的節(jié)點還有很多的能量儲備。這樣不利于能量的有效利用。為了提高節(jié)點能量的利用率,本文在 DLM算法基礎上進行了改進,將傳統(tǒng)的節(jié)點“休眠或激活”調(diào)度機制一般化,提出一種調(diào)整感知半徑的節(jié)點調(diào)度算法ASR-DLM(Adjustable Sensing Range-Distributed Lifetime Maximization)。

3.2 算法設計

ASR-DLM算法由初始化、感知半徑選擇和激活三個階段組成。初始化階段使每個節(jié)點獲知網(wǎng)絡參數(shù),在網(wǎng)絡開始工作時執(zhí)行一次。在每個子時間段,即每一輪,開始時首先選擇感知半徑的大小,然后執(zhí)行激活階段,選取最優(yōu)覆蓋集。

網(wǎng)絡壽命隨傳感器節(jié)點的感知半徑的增加而減小[11-12],因此,本文的算法盡可能設置小的感知半徑。對節(jié)點的感知半徑進行選擇,需要先對每個節(jié)點賦權(quán),對任意節(jié)點 u∈S,計算選取權(quán)值最大的感知半徑為最優(yōu)感知半徑大小。其中 Pu是指節(jié)點 u感知范圍內(nèi)的交叉點組成的集合。|Pu|表示節(jié)點 u感知范圍內(nèi)的交叉點數(shù)目。因為感知半徑越大,消耗能量就越多,所以,這里利用選擇權(quán)值最大的感知半徑,達到最小感知消耗和覆蓋最多交叉點的雙重目標,其中 Pu可以在沒有地理位置信息的條件下獲得[3]。

確定最優(yōu)感知半徑大小之后,選取最優(yōu)覆蓋集,方法根據(jù)文獻[3]中的 DSC算法進行。

如果存在最優(yōu)覆蓋集,選取最優(yōu)覆蓋集中節(jié)點為激活節(jié)點,傳感器網(wǎng)絡開始正常工作;若不存在最優(yōu)覆蓋集,即探測到覆蓋空洞,這時進行覆蓋空洞的填補。

根據(jù)推論 1探測是否有覆蓋空洞,若探測到覆蓋空洞,則增加傳感器節(jié)點的感知半徑,遵循空洞填補準則將覆蓋空洞填補,達到完全覆蓋后,網(wǎng)絡開始正常工作。

空洞填補準則 空洞邊緣節(jié)點在增加其感知半徑過程中,應遵循：(1)感知半徑增加的長度為一個單位長度,也就是說,若節(jié)點 u∈S的感知半徑是r(k)時,將感知半徑增加到 r(k+1)。若增加一個單位長度的感知半徑未能填補覆蓋空洞,再增加一個單位長度的感知半徑,依次類推。(2)增加感知半徑后,必須使得空洞邊緣交叉點的數(shù)目減少。通過空洞邊緣交叉點的數(shù)目不斷減少至零,則覆蓋空洞被填補完全。(3)給每個空洞邊緣節(jié)點賦權(quán),權(quán)值根據(jù)每增加一個單位長度的感知半徑所能覆蓋空洞邊緣交叉點的數(shù)目來確定,擁有較大權(quán)值的節(jié)點優(yōu)先增加其感知半徑。這樣就可以保證消耗最少的能量以覆蓋較多的空洞邊緣交叉點。(4)在空洞填補的過程中,需要保證覆蓋空洞不會由于增加感知半徑而造成當前空洞數(shù)量的變化,即填補節(jié)點不應該將覆蓋空洞分裂[7]。如圖 3所示,增加節(jié)點 C的感知半徑造成了本來的覆蓋空洞分裂成了兩個覆蓋空洞,這樣就形成了兩個空洞環(huán)。如果每次填補空洞都被分裂,最終會由于分裂的空洞個數(shù)過多而造成空洞填補工作的大大增加。

圖3 空洞的分裂

3.3 尋找空洞環(huán)的方法

步驟①：空洞邊緣節(jié)點的確定

有推論可知,當感知范圍不能覆蓋交叉點集 P中某些點時,覆蓋空洞產(chǎn)生,因為 P中的點都有唯一的ID作為標識,因此,網(wǎng)絡中傳感器節(jié)點可以根據(jù)這個標志來確定是否為空洞邊緣節(jié)點。若是空洞邊緣節(jié)點,則通知鄰居節(jié)點。這樣,每個空洞邊緣節(jié)點都有一個集合存儲著它的空洞邊緣鄰居集。如圖 3(a)中節(jié)點 A的空洞邊緣鄰居集就是 Nh(A)={C,G}。

步驟②：確定空洞環(huán)上的節(jié)點

當探測到覆蓋空洞時,空洞邊緣節(jié)點發(fā)起空洞環(huán)探測過程,對于如圖 3(a)中所示的覆蓋空洞而言,節(jié)點 A是空洞邊緣節(jié)點,它發(fā)送 “空洞環(huán)”報文給空洞邊緣鄰居 Nh(A)={C,G},報文是由 A及 A的空洞邊緣鄰居 Nh(A)={C,G}組成的集合 H。然后 C和 G同時將“空洞環(huán)”報文進行修改,H=H∪Nh(C)-H∩Nh(C),然后發(fā)送給自己的空洞邊緣鄰居,包括節(jié)點 A。若“空洞環(huán)”報文不再有更新,則說明已經(jīng)找到與節(jié)點 A相關的空洞環(huán)。

步驟③：計算空洞環(huán)上節(jié)點的填補權(quán)值

圖4 增加感知半徑

3.4 ASR-DLM算法

ASR-DLM算法的詳細步驟,對于時段 j,進行以下算法：

Step 0 在時段 j開始時,計算節(jié)點的感知半徑的最優(yōu)值,將感知半徑設置為最優(yōu)值。

Step 1 在時段 j開始時,對任意節(jié)點 u∈S,計算 μ=4?n?B,c(u)=μl(u)和 W(u)=cu(j)/Bu。其中l(wèi)(u)表示節(jié)點 u在時段 j開始時已消耗能量與初始能量的比值。Bu表示節(jié)點 u的初始能量,B表示所有節(jié)點初始能量的最大值。[3]

Step 2 對任意節(jié)點 u∈S,使用 DSC算法[3]確定節(jié)點的狀態(tài)(工作 or休眠),并且確定最優(yōu)的感知半徑大小。

Step 3 根據(jù)推論 1探測覆蓋空洞。若在上一步驟中激活節(jié)點的感知范圍不能將交叉點集 P中所有點覆蓋,說明有覆蓋空洞產(chǎn)生,進入 Step4;激活節(jié)點的感知范圍能將 P中所有點覆蓋,則說明沒有覆蓋空洞,無線傳感器網(wǎng)絡可以正常工作,直到時段j結(jié)束。

Step 4 尋找空洞環(huán)。一個網(wǎng)絡中可能會有若干個空洞環(huán)。對每個空洞環(huán)計算 Step 5。

Step 5 計算空洞環(huán)上的節(jié)點的填補權(quán)值Wh(u)。

Step 6 選擇最大填補權(quán)值的節(jié)點,增加此節(jié)點的感知半徑,并且向空洞鄰居節(jié)點廣播“增加”消息,消息包括節(jié)點的新感知半徑,并更新空洞邊緣節(jié)點集及空洞邊緣交叉點集,形成新的空洞環(huán),并向空洞邊緣節(jié)點廣播“新空洞環(huán)”消息,若“新空洞環(huán)”為空集,轉(zhuǎn) Step 7;否則轉(zhuǎn) Step 5。

Step 7 若已經(jīng)不存在空洞環(huán),轉(zhuǎn) Step 8;否則轉(zhuǎn)Step 5。

Step 8 進入正常工作階段,直到時段 j結(jié)束。

3.5 算法分析

從 ASR-DLM算法的步驟中可以看到,DLM算法在探測到覆蓋空洞時即終止,而 ASR-DLM在此基礎上,對覆蓋空洞進行填補,從而延長了網(wǎng)絡壽命。從能量角度來說,ASR-DLM算法從一開始就選擇最優(yōu)的感知半徑,提高節(jié)點的能量利用率;然后再選擇覆蓋集,經(jīng)過若干輪后,DLM算法探測到覆蓋空洞并且宣告終止,但是 ASR-DLM算法還可以利用某些節(jié)點的剩余能量對覆蓋空洞進行填補,無疑會延長網(wǎng)絡壽命,填補覆蓋空洞過程中消耗的能量,比如,確定空洞環(huán)消耗的能量,只有在探測到覆蓋空洞時才發(fā)生,由此產(chǎn)生的額外的通信能量消耗只占節(jié)點總能量的一小部分,因此,不會對網(wǎng)絡的壽命產(chǎn)生影響。

4 仿真

仿真實驗在一個 50×50的方形區(qū)域中隨機均勻部署節(jié)點,節(jié)點的初始能量是 B,DLM算法中感知半徑與通信半徑分別為 10和 22;ASR-DLM算法的感知半徑為 Rs={8,9,10,11}和 22;對于每一個激活節(jié)點,每個時段消耗能量采用 eu(k)=cs?r2(k),模型,其中 cs為感知系數(shù),這里取 cs=0.01,則 DLM算法中激活節(jié)點每時段消耗的能量為 1,而 ASRDLM算法中激活節(jié)點每時段消耗的能量為 Es={0.64,0.81,1,1.21}。下面比較 DLM算法[3]和ASR-DLM算法。

首先檢驗 ASR-DLM算法和 DLM算法[3]獲得的網(wǎng)絡壽命隨節(jié)點數(shù)目 n的變化情況,如圖 5所示。仿真結(jié)果表明,ASR-DLM算法確實優(yōu)于 DLM算法,并且隨著節(jié)點數(shù)目的增多,優(yōu)越性越突出。然后檢驗 ASR-DLM算法和 DLM算法[3]獲得的網(wǎng)絡壽命隨節(jié)點初始能量大小 B的變化情況,如圖 6所示。結(jié)果表明,兩種算法獲得的網(wǎng)絡壽命都隨著初始能量的增加,近似呈現(xiàn)線性關系,說明了兩種算法中能量均能有效利用,但是,擁有較高初始能量時,使用ASR-DLM算法比 DLM算法獲得了更長的網(wǎng)絡壽命,總體來說,ASR-DLM算法是優(yōu)于 DLM算法的。

圖5 初始能量為 15,網(wǎng)絡壽命隨節(jié)點總數(shù)的變化情況

圖6 節(jié)點總數(shù)為 150時,網(wǎng)絡壽命隨初始能量的變化情況

5 結(jié)論

本文設計了一種分布式無需地理位置信息的延長網(wǎng)絡壽命算法,采用調(diào)整傳感器節(jié)點感知半徑的方法,在保證完全覆蓋的基礎上延長了網(wǎng)絡壽命,可以將它擴展到 k-覆蓋。本文的算法也可以用于覆蓋空洞的探測與填補,在無需地理位置信息的條件下很有意義。

[1]Wang J,Medidi S,Medidi M.Energy-Efficient K-Coverage for Wireless Sensor Networks with Variable Sensing Radii[C]//Global Telecommunications Conference,Honolulu,2009：4518-4523.

[2]張曉麗,韓芳希,王瑞.基于 Voronoi圖的無線傳感器網(wǎng)絡的節(jié)點調(diào)度機制[J].計算機應用,2006,26(6)：199-200.

[3]Kasbekar G,Bejerano Y,Sarkar S.Lifetime and Coverage Guarantees Through Distributed Coordinate-Free Sensor Activation[C]//Proceeding of the 15thAnnual International Conference on Mobile Computing and Networking Mobi Com 09.Beijing：ACM Press,2009：169-180.

[4]AlaviB,Pahlavan K.Modeling of the TOA-Based Distance Meas-urement Error Using UWB Indoor Radio Measurements[J].IEEE Communications Letters,2006,10(4)：275-277.

[5]Wen C,Morris R,Sethares W.Distance Estimation Using Bidirectional Communications Without Synchronous Clocking[J].IEEE Transactions on Signal Processing,2007,55(5)：1927-1939.

[6]Lu Mingming,Wu Jie,Cardei M,et al.Energy-Efficient Connected Coverage of Discrete Targets in Wireless Sensor Networks[J].International Journal ofAd Hoc and Ubiquitous Computing,2009,4(3/4)：137-147.

[7]蘇瀚,汪蕓.傳感器網(wǎng)絡中無需地理信息的空洞填補算法[J].計算機學報,2009,32(10)：158-170.

[8]Zhang C,Zhang Y,Fang Y.Detecting Coverage Boundary Nodes in Wireless Sensor Networks[C]//Proceeding of ICNSC,2006,6(4)：868-873.

[9]Wang Y,Gao J,Mitchell J.Boundary Recognition in Sensor Networks by Topological Methods[C]//Proceeding of the 12thAnnual International Conference on Mobile Computing and Networking.Los Angeles：ACM Press,2006：122-133.

[10]Guo LX,Wang X.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Transactions on Sensor Network,2005,1(1)：36-72.

[11]楊文國,郭田德,趙彤.異構(gòu)監(jiān)測傳感器網(wǎng)絡壽命最大化模型及其求解[J].計算機學報,2007,30(4)：532-538.

[12]孫瑞華,馬春光,張國印,等.異構(gòu)傳感器網(wǎng)絡代價最小模型[J].計算機應用,2008,28(5)：1280-1286.