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

崔彥新,劉三陽,馮海林

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

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

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

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

1 網絡模型

1.1 網絡描述

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

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

1.2 模型假設

假設以下條件可以滿足：

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

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

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

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

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

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

2 預備知識

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

定義 2覆蓋空洞：傳感器網絡中如果存在一片連續的區域不被任何傳感器節點的感知范圍所覆蓋,那么這片未被監測的連續區域稱為一個覆蓋空洞[7]。

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

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

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

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

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

證明因為A中節點的感知范圍不能將 P中所有點覆蓋,根據定理 1,A不是一個傳感器覆蓋集,不能將監測區域完全覆蓋,因此覆蓋空洞產生。證畢。

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

用到的術語：

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

圖1 覆蓋空洞

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

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

空洞環 傳感器網絡中相鄰的空洞邊緣節點組成的集合,與集合中節點的鄰居組成的并集。如圖2所示。

圖2 空洞環

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

3 問題與算法設計

3.1 問題陳述

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

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

3.2 算法設計

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

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

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

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

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

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

圖3 空洞的分裂

3.3 尋找空洞環的方法

步驟①：空洞邊緣節點的確定

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

步驟②：確定空洞環上的節點

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

步驟③：計算空洞環上節點的填補權值

圖4 增加感知半徑

3.4 ASR-DLM算法

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

Step 0 在時段 j開始時,計算節點的感知半徑的最優值,將感知半徑設置為最優值。

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

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

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

Step 4 尋找空洞環。一個網絡中可能會有若干個空洞環。對每個空洞環計算 Step 5。

Step 5 計算空洞環上的節點的填補權值Wh(u)。

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

Step 7 若已經不存在空洞環,轉 Step 8;否則轉Step 5。

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

3.5 算法分析

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

4 仿真

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

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

圖5 初始能量為 15,網絡壽命隨節點總數的變化情況

圖6 節點總數為 150時,網絡壽命隨初始能量的變化情況

5 結論

本文設計了一種分布式無需地理位置信息的延長網絡壽命算法,采用調整傳感器節點感知半徑的方法,在保證完全覆蓋的基礎上延長了網絡壽命,可以將它擴展到 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圖的無線傳感器網絡的節點調度機制[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]蘇瀚,汪蕓.傳感器網絡中無需地理信息的空洞填補算法[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]楊文國,郭田德,趙彤.異構監測傳感器網絡壽命最大化模型及其求解[J].計算機學報,2007,30(4)：532-538.

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