有向傳感網分塊區域p-覆蓋節點調度算法研究*

陳常超,孫力娟,韓 崇,郭 劍

(1.南京郵電大學計算機學院,南京 210003;2.江蘇省無線傳感網高技術研究重點實驗室,南京 210003)

?

有向傳感網分塊區域p-覆蓋節點調度算法研究*

陳常超,孫力娟*,韓 崇,郭 劍

(1.南京郵電大學計算機學院,南京 210003;2.江蘇省無線傳感網高技術研究重點實驗室,南京 210003)

本文研究了分塊區域p-覆蓋的有向傳感網節點調度問題,并提出了一種有效延長網絡生存時間的節點調度方案。將區域劃分為擁有不同監測需求的子區域,從有向傳感器節點感知模型出發,設計了基于網格劃分的節點感知范圍度量方法,并在此基礎上提出了分布式分區域節點調度算法DSSA(Distributed Subarea Sensor-schedule Algorithm),該算法是一個選取最少數量的節點去對每一個子區域進行p-覆蓋的分布式貪心算法。算法同時還考慮了整體網絡的連通。通過仿真深入評估了DSSA算法的性能。對比實驗結果表明,DSSA算法可以顯著延長網絡生存時間。

有向傳感網絡;節點調度;區域劃分;p-覆蓋

無線傳感網絡WSNs(Wireless Sensor Networks)作為一種將邏輯上的信息世界與客觀上的物理世界融合在一起的方式,參與到了許多實際應用中,例如實時流量監控、空氣質量監控、污染監控等等[1]。無線傳感網絡感知節點有多種,過去大部分工作基于全方位角度感知的全向傳感器假設,但在實際應用中存在多種有向傳感器,例如相機傳感器、超聲傳感器和紅外傳感器等[2-4]。節點調度作為提高WSN節點利用效率的一個方式,引起了很多學者的極大關注[5-7]。本文研究就是基于有向傳感網絡的節點調度問題。

針對于許多監測需求不嚴格的場景,部分的觀測失誤或者數據丟失也是可接受的,因此此類場景通常進行部分覆蓋。例如,雨季對森林進行火災監測時,由于雨季火險等級明顯低于旱季,此時通常采用部分覆蓋監測。同時森林的不同區域監測需求存在差異:在樹木密度大或較為干燥區域,監測需求較高;而在樹木密度小或有池塘沼澤等區域,監測需求相應較低。由此,針對不同的監測區域,采取不同的覆蓋度是更加合理的一種方案。本文研究充分考慮區域覆蓋時存在不同子區域監測需求不同的情況,提出了根據監測需求進行區域分塊并單獨調度的算法設計。

1 相關研究

WSNs覆蓋調度問題已經取得廣泛研究。Cheng等[8]針對有向傳感網絡,研究了“最大有向區域覆蓋”MDAC(Maximum Directional Area Coverage)問題,即最大化覆蓋區域面積。文中提出一種分布式貪心算法DGreedy(Distributed Greedy Algorithm)解決MDAC問題。Han等[9]針對有向傳感器節點組成的有向傳感網絡中時空覆蓋調度問題進行研究,設計了基于網格劃分的基本區域生成方法,并在此基礎上提出了節點最大覆蓋調度迭代選擇MaxGreedy算法。Chen等[10]同樣通過網格劃分的方法研究了無線傳感網中的節點調度問題,其節點感知模型為圓形,最終提出了一個簡單的近似算法來選取滿足工作需求的最少節點來進行檢測工作。以上研究成果都是將整個待覆蓋區域作為一個整體,擁有相同的覆蓋需求,來進行節點調度研究。然而在大面積部署傳感器節點時,通常不同區域擁有不同監測需求。Li等[11]提出覆蓋區域分塊劃分的概念,針對節點感知模型為圓形的情況下進行了節點調度算法的研究,提出了集中式覆蓋調度算法(CPCA)和分布式覆蓋調度協議(DPCP)。Zhou等[12]針對有向傳感網進行了節點的覆蓋調度研究,其研究成果同樣考慮到目標重要性不同,然而其覆蓋目標為關鍵點而非區域。最終提出了一個基于貪心算法的近似算法來對節點進行部署與調度。Zhang等[13]針對WSN多重覆蓋問題進行了研究,提出了節點輪換喚醒與休眠的調度思路。

本文在以上研究基礎上,考慮不同子區域監測需求不同的情況,基于網格劃分方法,對基于有向感知模型的節點進行了調度算法的研究。對比已有算法增加了算法的普適性和精確性,對節點感知范圍異構、子區域異構等都進行了考慮。

圖1 有向傳感節點感知范圍模型

2 問題定義

2.1 節點感知模型

本文主要研究有向傳感節點的調度問題,為便于抽象,將有向傳感節點的感知模型定義在二維空間中[14]。如圖1所示。

本文研究區域覆蓋問題,節點或網絡覆蓋率的計算基于網絡中節點的感知區域。

2.2 網絡覆蓋模型

本文考慮一個部署有N個有向傳感節點的二維區域M,并且假設不存在兩個節點部署位置相同。區域覆蓋模式為冗余覆蓋,即充分考慮節點衰亡情況,高密度部署了N個節點以提供調度保障,不同節點的監測區域可能存在重疊。下面給出本文中的p-覆蓋定義。

定義1(P-覆蓋) 給定二維區域M,根據不同監測需求將大區域M劃分為不同的小區域Mj,并根據每個子區域的實際監測需求分別為其指定一覆蓋比例pj。通過節點調度使任意子區域Mj滿足:

(1)

則稱該區域滿足p-覆蓋,該無線傳感網絡是滿足p-覆蓋的網絡。

其中Sj表示子區域Mj的面積,Nj表示子區域Mj中部署的節點個數,seti表示子區域Mj中節點si感知范圍內的網格集合,Ei表示節點si的存活狀態,a表示網格劃分步長。

如圖2所示,整個二維區域M根據實際需求劃分為了9個子區域M1～M9,每個子區域擁有不同的大小和形狀。根據不同子區域的重要性,為每個子區域Mj設定一個需求覆蓋比例pj。每個子區域中部署有異構的有向傳感節點。子區域M7是一個比較重要的區域,因此需要90%覆蓋。然而,針對子區域M2和M9,可能其非重要區域,因此僅50%覆蓋就足夠。通過這種策略,用戶可以在部署階段獲得更大的自由度。同樣是N個節點,在部署時可以根據不同子區域的權重,在關鍵子區域部署更多的傳感器節點而對非關鍵區域則部署較少的節點,由此可以在相同的成本下有效地提高節點利用率。

圖2 網絡覆蓋模型

圖2中畫出的節點數量并不代表實際部署數量,節點部署是一次性工作,因此在實際部署中通常進行更高密度的節點部署。

在針對全覆蓋問題的研究中,網絡終結的標志是節點不能對覆蓋區域提供完全無死角覆蓋。而本文研究覆蓋問題為非全覆蓋情況,同時還對覆蓋區域根據重要性不同進行了劃分,因此以往研究中的網絡終結標志在此處并不適用。考慮到不同子區域擁有不同的覆蓋需求和面積,本文將網絡終結時間定義如下:

定義2(網絡終結時間) 給定二維區域M,將其劃分為J個子區域,對每一個子區域Mj設置覆蓋需求pj,隨著節點因為能量減少而衰亡,當滿足:

(2)

時,表明網絡終結。

其中,

(3)

(4)

Sj表示子區域Mj的面積,f為網絡覆蓋度,由用戶根據覆蓋需求給定。Bj表示子區域Mj的狀態,Nj表示子區域Mj中部署的節點個數,seti表示子區域Mj中節點si感知范圍內的網格集合,Ei表示節點si的存活狀態,a表示網格劃分步長,ei表示節點si的能量剩余。

綜上,定義分塊區域p-覆蓋節點調度問題如下:

定義3(分塊區域p-覆蓋節點調度問題) 給定滿足p-覆蓋的區域M,通過設計節點調度算法使之在滿足p-覆蓋的前提下盡可能延長網絡生存時間。

3 本文算法

根據上節對節點及網絡覆蓋模型的定義,由于有向傳感節點感知區域為扇形,并且節點感知模型異構且扇形的相交區域多為非凸多邊形,通常在判斷感知區域時,可以將連續的節點監測區域看作是由均勻離散的點組成,因此本文采用網格劃分的方法來刻畫節點覆蓋區域,在網格化完成后,節點的監測區域通過網格點集合來表示。根據上文問題描述及定義,本文設計了如下調度算法。

3.1 分區域節點調度算法

假設有充足的節點被部署在二維區域M,區域M根據實際覆蓋需求分為J子區域,并且節點部署滿足p-覆蓋,即

針對任意子區域Mj,有

(5)

圖3 網絡工作模式

本節提出一個分布式分區域節點調度算法DSSA來完成對區域的覆蓋,算法在每一個子區域中分布式執行來進行節點調度工作,最終算法能夠在保證每個子區域覆蓋比例pj的同時最大化網絡生存時間。定義網絡工作模式為:決策期+運行期。決策期即算法執行階段,通過執行DSSA算法在每一個子區域Mj選取一個工作節點集worksetj;運行期激活worksetj中的節點進行工作。當運行期結束后,重新進入決策期選取下一運行期需要激活的節點,如此往復循環執行。雖決策期網絡并不能提供監測,但是與運行期相比,決策期的時間非常短,因此本文假設決策期帶來的覆蓋損失和能耗損失忽略不計。由于算法是循環執行的,在此定義1個決策期與1個執行期合稱為網絡工作模式中的一個網絡周期,如圖3所示。下面重點敘述決策期所執行的DSSA算法。

DSSA算法包含兩部分,分別工作于如下兩個階段:選取階段和連通階段。每一階段都有一固定的時間長度,該時間長度可保證算法在該階段能夠執行完畢,從而不會影響下一階段算法的執行,如圖3所示。

上圖中選取階段和連通階段的短虛線表示該階段的實際結束時間,其一定是在下一階段開始之前,也就是說網絡工作模式中每一網絡周期都是相等的,從而保證選取階段算法結束后不同子區域的連通階段算法可以同步執行,進行連通不同子區域的操作。選取和連通階段的具體任務為:①選取階段:所有子區域Mj獨立執行選取算法來構建一個能保證該子區域監控需求pj的節點集合worksetj;②連通階段:將所有子區域的節點集合連通起來。

在每一個網絡周期的開始,下面的算法都會在所有子區域中執行,來構建能夠對子區域提供pj比例覆蓋的worksetj。在描述算法之前,先做如下定義:

網格點狀態(有效、無效) 針對任一節點si的感知網格點集seti,若seti中某一網格點已經被worksetj中的節點覆蓋,則稱在seti中該網格點狀態為無效,否則稱該網格點狀態為有效。

有效網格點集Useti節點si感知網格點集seti中未被標記為無效的網格點集合,初始狀態下Useti與seti相等。

重復網格點集Rseti節點si感知網格點集中被標記為無效的網格點集合,初始狀態下Rseti為空。

子區域j當前覆蓋網格點集Allnumj當前周期的決策期結束后,所有工作標志位q為1的節點所覆蓋的網格點數目(集合中無重復網格點)。

3.1.1 選取階段算法

算法1 選取階段算法(執行于每一個節點si)

輸入:子區域Mj的覆蓋需求pj,Mj的面積Sj,網格步長a

輸出:工作節點集worksetj(部分)

執行:

1:初始化:

2: Allnumj=0qi=0

3: 隨機選擇一節點,向其發送消息包msg(beRoot)

4: (算法執行于任一子區域Mj中的任一節點si中)

5:節點自動喚醒

6:if 接收到消息包msg(beRoot)

7:qi=1sroot=si

8: worksetj=worksetj∪sroot

9: Allnumj=Allnumj+numof(Usetroot)

11: goto算法2:連通階段算法

12: else

13: 向所有鄰居廣播消息包msg(IamRoot)

//消息包中包含Usetroot字段

14: end if

15:end if

16:if接收到消息包msg(IamRoot)

17: ifq=1

18: throw msg

19: else

20: Rseti=Rseti+(Useti∩ Usetroot)

21: Useti=Useti-(Useti∩ Usetroot)

22: 計算worthi的值,并封裝為消息包msg(worthi),回傳至其鄰居根節點sroot

23: end if

24:end if

25:if接收到消息包msg(worthi)

26: ifq=0

27: throw msg

28: else

29: 選擇最大的兩個worth值記為Firworth,Secworth

30:snextroot=node(Firworth>Refworth? Firworth:Refworth)

//消息包msg(beRoot)中包含Allnumj、Refworth字段

31: ifsnextroot=sFirworth

32: msg(beRoot).Refworth=Secworth

33: else

34: msg(beRoot).Refworth=0

35: end if

36: 向snextroot發送消息包msg(beRoot)

37: end if

38:end if

39:ifq=1且未接收到消息包msg(worthi)

40: if Refworth!=0

41:snextroot=sRefworth

42: 向snextroot發送消息包msg(beRoot)

43: else

44: ifspreviousroot==NULL

45: 宣告子區域死亡,算法在該子區域Mj中停止執行

46: else

47: 向節點spreviousroot發送消息包msg(reCall)

48: end if

49: end if

50:end if

51:if接收到消息包msg(reCall)

52: ifq=0

53: throw msg

54: else

55:sroot=spreviousroot

56: goto 13

57: end if

58:end if

初次部署或上一周期運行階段結束時,所有節點自動喚醒。算法隨機選取一個節點s并將其設置為初始根節點sfirstroot(3行)。在決策期所有節點都將保持喚醒狀態。當節點收到msg(beRoot)信息,其將自己q置1,加入worksetj。此時該節點稱為根節點sroot。sroot執行:Allnumj=Allnumj+numof(Usetroot),然后考察Allnumj,如果滿足:

(6)

子區域Mj選取階段完成,算法轉至連通階段(6行～11行)。否則,sroot向鄰居節點廣播msg(IamRoot)消息包,消息中包含Usetroot(13行)。當節點si收到鄰居根節點sroot發來的當選消息包,如果qi為1,忽略此消息包。如果qi為0,節點考察Useti與當選消息包中攜帶的Usetroot是否有重復網格點,如果有重復,將重復網格點從Useti中刪除,加入Rseti。節點完成Useti和Rseti的更新后,計算自身worthi值并回傳給sroot(16行～24行)(worth值的計算見3.2節)。

sroot接收到鄰居節點回傳的worth值,從中選取最大的兩個worth值(記為Firworth和Secworth)和其對應的節點信息進行存儲。然后sroot比較Firworth和msg(beRoot)包中的Refworth值的大小,選取較大者對應的節點記為snextroot,向snextroot發送msg(beRoot)信息。beRoot信息:如果snextroot為Firworth對應的節點,beRoot信息中的Refworth寫為Secworth,否則,beRoot信息中的Refworth值置0.beRoot信息中還包含Allnumj(25行～38行)。

如果sroot未接收到鄰居節點回傳的worth值(說明sroot沒有鄰居節點或鄰居節點已死亡),并且beRoot中的Refworth為0,sroot向其上一級根節點spreviousroot發送msg(reCall)回溯消息包。spreviousroot收到msg(reCall)回溯消息包后,算法轉至13行。如果向上回溯至sfirstroot仍然不能找到snextroot,Bj置0,宣告子區域Mj死亡,Mj中的算法結束執行(39行～58行)

3.1.2 連通階段算法

算法執行至此說明選取階段已經結束,下面將進入連通階段,將各個子區域中選取出來的工作節點集連通起來。算法等待連通階段的起始時間點,當起始時間點到達,每一個worksetj中節點都將廣播一個msg(connect)連通消息包,定義連通信息包的最大轉發次數為Maxstep。連通信息包中包含變量distancej,初始為1,指代距離worksetj集合中節點的跳數,連通消息包每被轉發一次,distancej加1。信息包中還包含轉發過該消息包的路徑節點信息。在接下來的算法中,Mk將會被用來代表子區域Mj的任何一個鄰居子區域。對于任意節點si,其針對所在子區域Mj和其任意鄰居子區域Mk維護有對應的變量Mindistancej和Mindistancek,初始為最大值,指代節點si距離worksetj和worksetk最短距離。算法偽代碼如下:

算法2 連通階段算法(執行于每一個節點si)

輸入:節點工作集worksetj(部分)(即算法2的輸出)

輸出:節點工作集worksetj

執行:

1:(算法執行于任一子區域Mj中的任一節點si中)

2:if接收到消息包msg(connect)

3:ifqi=1

4:throwmsg

5:else

6:distancez++//z的取值可能為j或k

7:ifdistancez≥Maxstep

8:throwmsg

9:else

10:ifdistancez≤Mindistancez

11: 用distancez更新節點自身維護的Mindistancez

12:else

13: 用節點自身維護的Mindistancez更新distancez

14: 向鄰居節點廣播消息包msg(connect)

15:endif

16endif

17:endif

18:endif

19:ifMindistancej+Mindistancek≤Maxstep

20: q=1

21: 向每一個子區域Mj和Mk中的節點廣播消息包msg(RouteSuccess) //消息包msg(RouteSuccess)告訴這些節點停止z為j或者k的msg(connect)消息包

22: 向所有處于連通路徑上的節點發送消息包msg(turnOn),將這些節點的q置1,即這些節點也加入節點工作集worksetj

23:endif

24:ifq=0

25: 轉至休眠狀態直至下周期開始時喚醒

26:endif

當節點si接收到連通消息包,如果節點的qi為1,表明節點屬于某一workset,不轉發消息包(2行～4行)。否則對消息包中的distanceq(q可能為j或k)執行加1操作,并判斷distanceq≥Maxstep是否成立。如果成立,不轉發消息包(6行～8行)。否則,判斷distanceq≤Mindistanceq是否成立,如果成立,用distanceq更新自己維護的Mindistanceq并轉發消息包(10行～14行)。如果存在節點si,其維護的Mindistancej和Mindistancek滿足:Mindistancej+Mindistancek≤Maxstep,廣播路徑建立消息包,告知子區域Mj和其任意鄰居子區域Mk已經連通,停止轉發任何Mk子區域相關的連通信息包,并發送msg(turnOn)激活消息包至該連通路徑上的所有節點,將這些節點的q置1,即這些節點運行期也將激活運行來保證連通。如果節點的工作標志位q未被置1,表示其最終未被加入worksetj,其將會在決策期結束后自動恢復休眠狀態(24行～26行)。

3.1.3 算法復雜度分析

選取階段算法整體采用的是類貪心算法,由于貪心算法是“一條鏈”式的處理算法,每次處理皆發生在臨近的幾個節點之間,所以從算法整體來看其時間復雜度是較低的。經典貪心算法時間復雜度為O(N),然而考慮算法存在尋找失敗的回溯過程,因此復雜度會比經典貪心算法復雜度略高,約為O(2N)左右。

由于算法獨立執行于每一個節點,因此我們選任一節點si為例,分析其計算復雜度。針對任一節點si,算法執行過程中復雜度最高的是更新自身所維護的有效網格點集Useti和重復網格點集Rseti以及worth值的計算。更新操作僅僅需要兩個集合的對比,而worth值計算也較為簡單,因此算法整體計算復雜度不高。

由于涉及集合更新操作,因此不可避免會帶來大量的信息傳遞。為降低消息復雜度,本文設計了集合增量更新策略。每次根節點通告有效節點時不需要廣播所有已覆蓋節點集合,而僅需要通告新增加節點集合,其他節點可以增量更新自己維護的Useti和Rseti。在采用網格法為基礎的算法中,本文的設計大幅降低了消息復雜度。

連通階段算法中不涉及太多計算操作,故計算復雜度在此忽略不計。算法為每個連通消息包設計有最大轉發次數Maxstep以保證消息不會重復無限次轉播,同時只要算法判斷出連通路徑算法及廣播終止消息停止算法,因此算法時間復雜度低于O(Maxstep·N)。

3.2 worth值的計算

DSSA使用worth來衡量每一個節點能夠提供的覆蓋貢獻,這種機制為選取最佳節點來對區域進行監控提供了保障。本文將seti分為兩個部分,分別為:有效網格集Useti和重復網格集Rseti。有效網格集中的節點越多,相應的節點能夠提供的覆蓋貢獻就越大,故而Useti與worthi正相關;而重復網格集中的網格點數越多,代表冗余覆蓋越多,因此Rseti與worthi負相關。另外,節點的剩余能量e也將作為參考變量。最終,我們用這3個參數來對候選節點進行評估,worth值可以用如式(7)表示:

(7)

其中e代表節點剩余能量。當numof(Useti)=0時,代表節點si的Useti中沒有網格點,即其不能提供任何覆蓋貢獻,此時將worthi值置0。λ、η、γ 3個變量根據不同應用場景或部署情況來取值調整3個參數的權重。

4 仿真實驗

仿真實驗采用C++語言,基于MicrosoftVisualStudio2013平臺實現。本文研究節點調度算法比較準則是網絡生存時間,其中包括各子區域網絡生存時間和整體網絡生存時間。本節將DSSA算法與如下3種算法進行對比:1、LongRange算法:根據文獻[10]中最遠距離選取思想,根節點每次選取通信距離內最遠的鄰居節點作為下一根節點。2、RandSchedule算法:根節點每次在鄰居節點中隨機選取一個節點作為下一根節點。3、NonSchedule算法:該算法不進行節點選擇與調度,每次將子區域中所有節點全部打開運行,直到子區域中存活節點不能提供p比例覆蓋,宣告子區域死亡。仿真基于二維區域M,隨機劃分為9個子區域,各子區域參數如表1所示。

表1 子區域劃分情況

其他參數設置如表2所示。其中為方便比較,將節點剩余能量e的單位規格化為節點能夠工作的網絡周期數,如e=5,表示節點剩余能量能夠保證其正常工作5個網絡周期。

表2 算法仿真參數設置

不考慮整體網絡覆蓋度f,考察在4個調度算法調度下的各子區域最大生存時長,結果如圖4所示。

圖4 不同算法調度下的各子區域生存時長對比

由圖4可以看出,在9個子區域中,DSSA算法均能夠提供比其他3個算法更多的子區域生存時長。

下面抽取其中兩個子區域M6和M9對比4種算法在選取節點工作集worksetj時的效率。

圖5 節點工作集合選取效率對比

從圖5(a)和圖5(b)中可以看出,本文提出的DSSA算法在節點工作集worksetj選取時始終保持領先于其他3種算法的優勢,即用更少的節點數就可滿足預定的覆蓋需求。在后期隨著節點衰亡等因素,雖然worksetj中所需節點數有所上升,但仍低于其他3種算法。也正因為選取的合理與高效,使得DSSA算法能夠提供的工作網絡周期最多。

圖6中將網絡覆蓋度f考慮進來,針對不同網絡覆蓋度f,對4種算法調度下的網絡整體生存時間進行對比。其中NonSchelule表示的是不進行節點調度的網絡生存時長,通過數據可以發現,如果不進行任何節點調度,即使在網絡覆蓋度f=0.1的情況下,網絡最大生存時長(周期)也不會大于節點最大初始剩余能量5(網絡周期)。而借助于節點調度算法,如本文提出的DSSA算法,在網絡覆蓋度f=0.7時,算法還能夠保證18個周期的網絡生存時長,足以說明DSSA算法的必要性和有效性。同時通過圖6可以發現,文獻[10]中提出的針對全向感知節點的LongRange節點調度算法完全不適用與有向傳感網絡中的節點調度問題,其性能表現甚至不如隨機調度算法。而本文提出的DSSA算法在不同網絡覆蓋度下始終保持良好的性能表現。

圖6 不同網絡覆蓋度下的算法性能表現對比

為對比不同節點部署密度下的算法性能表現,在上文仿真實驗的基礎上,對每一個子區域中節點部署個數減半和翻倍,分別重新進行仿真實驗,如圖7和圖8所示。

圖7 子區域節點部署數量減半時4種算法性能對比

圖8 子區域節點部署數量翻倍時4種算法性能對比

其中圖7和圖8分別表示每個子區域的節點部署數量減半和翻倍時,4種算法調度下的網絡生存時間對比。結合圖6初始節點部署個數的對比圖表,可以看出DSSA算法不論節點部署密度大小,性能表現始終明顯領先于其他3種算法。同時隨著節點部署密度的增加,DSSA算法相比其他3種算法的優勢逐步拉大。

5 結語

為延長分塊區域p-覆蓋有向傳感網絡的生存時間,本文提出一種基于網格劃分的分區域節點調度算法DSSA。首先對節點感知范圍網格化劃分,然后在每一個子區域的執行算法貪心式的進行節點工作集的選取調度。DSSA算法還對整體網絡的連通進行了考慮。仿真實驗表明,該算法對比已有算法表現出了良好的性能和穩定性。

[1]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005:59-61.

[2]Chen P,Hong K,Naikal N,et al.A Low-Bandwidth Camera Sensor Platform with Applications in Smart Camera Networks[J].ACM Transactions on Sensor Networks,2013,9(2):21.

[3]Sung T W,Yang C S.Voronoi-Based Coverage Improvement Approach for Wireless Directional Sensor Networks[J].Journal of Network and Computer Applications,2014,39:202-213.

[4]Singh A,Rossi A.A Genetic Algorithm Based Exact Approach for Lifetime Maximization of Directional Sensor Networks[J].Ad Hoc Networks,2013,11(3):1006-1021.

[5]Liu C,Cao G.Distributed Critical Location Coverage in Wireless Sensor Networks with Lifetime Constraint[C]//INFOCOM,2012 Proceedings IEEE.IEEE,2012:1314-1322.

[6]Ren Y,Zhang S,Zhang H.Theories and Algorithms of Coverage Control for Wireless Sensor Networks[J].Journal of Software,2006,17(3):422-433.

[7]劉端陽,暴占兵,程珍.一種可分負載WSN的能耗均衡負載調度算法[J].傳感技術學報,2014,27(2):225-232.

[8]Cheng W F,Liao X K,Shen C X.Maximal Coverage Scheduling in Wireless Directional Sensor Networks[J].Journal of Software,2009,20(4):975-984.

[9]韓崇,孫力娟,郭劍.一種基于網格劃分的有向傳感網時空覆蓋調度算法[J].南京郵電大學學報(自然科學版),2013,33(5):82-87.

[10]Chen H,Wu H,Tzeng N F.Grid-Based Approach for Working Node Selection in Wireless Sensor Networks[C]//Communi-cations,2004 IEEE International Conference on.IEEE,2004,6:3673-3678.

[11]Li Y,Ai C,Cai Z,et al.Sensor Scheduling for p-Percent Coverage in Wireless Sensor Networks[J].Cluster Computing,2011,14(1):27-40.

[12]Zhou P,Wu J,Long C.Probability-Based Optimal Coverage of PTZ Camera Networks[C]//Communications(ICC),2012 IEEE International Conference on.IEEE,2012:218-222.

[13]張蕾.無線傳感器網絡中多重覆蓋算法的研究[J].傳感技術學報,2014,27(6):802-806.

[14]Ma H,Liu Y.Correlation Based Video Processing in Video Sensor Networks[C]//Wireless Networks,Communications and Mobile Computing,2005 International Conference on.IEEE,2005,2:987-992.

A Scheduling Algorithm for Area-Dividingp-Persent Coverage in Directional Sensor Networks*

CHENChangchao,SUNLijuan*,HANChong,GUOJian

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China;2.Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

In this paper,we study sensor scheduling problems for p-percent coverage area which is divided into different subareas.We propose a schedule to prolong the network lifetime.Based on different coverage requirement,we divide the initial whole area into different small subareas.Each subarea has its’ own coverage requirement p.Starting from the sensor model of directional sensor nodes,we propose an algorithm to describe node’s sensor area based on grid partition.Then we propose the Distributed Greed Subarea Scheduling Algorithm DSSA(Distributed Subarea Sensor-schedule Algorithm),which promises p-precent coverage for every subarea and use least number of nodes.This algorithm also consider network connectivity.The simulation results show that DSSA can prolong network lifetime significantly.

directional sensor networks;sensor schedule algorithm;area divided;p-percent coverage

陳常超(1991-),男,碩士,南京郵電大學計算機學院碩士研究生,主要研究方向為無線傳感器網絡及應用;

孫力娟(1963-),女,教授,博士生導師,研究方向為演化計算、無線傳感器網絡和數據處理等;

韓 崇(1985-),男,博士,講師,研究生方向為多媒體信息處理、數據挖掘;

郭 劍(1978-),男,副教授,碩士生導師,研究方向為無線傳感器網絡、無線多媒體傳感器網絡。

項目來源:國家自然科學基金項目(61171053,61300239);教育部博士點基金項目(20113223110002);中國博士后科學基金項目(2014M551635);江蘇省博士后科研資助計劃項目(1302085B)

2014-08-21 修改日期:2014-10-30

C:7230

10.3969/j.issn.1004-1699.2015.01.019

TP393

A

1004-1699(2015)01-0107-08