有向傳感網(wǎng)分塊區(qū)域p-覆蓋節(jié)點(diǎn)調(diào)度算法研究*

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

(1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院,南京 210003;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,南京 210003)

?

有向傳感網(wǎng)分塊區(qū)域p-覆蓋節(jié)點(diǎn)調(diào)度算法研究*

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

(1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院,南京 210003;2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室,南京 210003)

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

有向傳感網(wǎng)絡(luò);節(jié)點(diǎn)調(diào)度;區(qū)域劃分;p-覆蓋

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

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

1 相關(guān)研究

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

本文在以上研究基礎(chǔ)上,考慮不同子區(qū)域監(jiān)測需求不同的情況,基于網(wǎng)格劃分方法,對(duì)基于有向感知模型的節(jié)點(diǎn)進(jìn)行了調(diào)度算法的研究。對(duì)比已有算法增加了算法的普適性和精確性,對(duì)節(jié)點(diǎn)感知范圍異構(gòu)、子區(qū)域異構(gòu)等都進(jìn)行了考慮。

圖1 有向傳感節(jié)點(diǎn)感知范圍模型

2 問題定義

2.1 節(jié)點(diǎn)感知模型

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

本文研究區(qū)域覆蓋問題,節(jié)點(diǎn)或網(wǎng)絡(luò)覆蓋率的計(jì)算基于網(wǎng)絡(luò)中節(jié)點(diǎn)的感知區(qū)域。

2.2 網(wǎng)絡(luò)覆蓋模型

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

定義1(P-覆蓋) 給定二維區(qū)域M,根據(jù)不同監(jiān)測需求將大區(qū)域M劃分為不同的小區(qū)域Mj,并根據(jù)每個(gè)子區(qū)域的實(shí)際監(jiān)測需求分別為其指定一覆蓋比例pj。通過節(jié)點(diǎn)調(diào)度使任意子區(qū)域Mj滿足:

(1)

則稱該區(qū)域滿足p-覆蓋,該無線傳感網(wǎng)絡(luò)是滿足p-覆蓋的網(wǎng)絡(luò)。

其中Sj表示子區(qū)域Mj的面積,Nj表示子區(qū)域Mj中部署的節(jié)點(diǎn)個(gè)數(shù),seti表示子區(qū)域Mj中節(jié)點(diǎn)si感知范圍內(nèi)的網(wǎng)格集合,Ei表示節(jié)點(diǎn)si的存活狀態(tài),a表示網(wǎng)格劃分步長。

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

圖2 網(wǎng)絡(luò)覆蓋模型

圖2中畫出的節(jié)點(diǎn)數(shù)量并不代表實(shí)際部署數(shù)量,節(jié)點(diǎn)部署是一次性工作,因此在實(shí)際部署中通常進(jìn)行更高密度的節(jié)點(diǎn)部署。

在針對(duì)全覆蓋問題的研究中,網(wǎng)絡(luò)終結(jié)的標(biāo)志是節(jié)點(diǎn)不能對(duì)覆蓋區(qū)域提供完全無死角覆蓋。而本文研究覆蓋問題為非全覆蓋情況,同時(shí)還對(duì)覆蓋區(qū)域根據(jù)重要性不同進(jìn)行了劃分,因此以往研究中的網(wǎng)絡(luò)終結(jié)標(biāo)志在此處并不適用?？紤]到不同子區(qū)域擁有不同的覆蓋需求和面積,本文將網(wǎng)絡(luò)終結(jié)時(shí)間定義如下:

定義2(網(wǎng)絡(luò)終結(jié)時(shí)間) 給定二維區(qū)域M,將其劃分為J個(gè)子區(qū)域,對(duì)每一個(gè)子區(qū)域Mj設(shè)置覆蓋需求pj,隨著節(jié)點(diǎn)因?yàn)槟芰繙p少而衰亡,當(dāng)滿足:

(2)

時(shí),表明網(wǎng)絡(luò)終結(jié)。

其中,

(3)

(4)

Sj表示子區(qū)域Mj的面積,f為網(wǎng)絡(luò)覆蓋度,由用戶根據(jù)覆蓋需求給定。Bj表示子區(qū)域Mj的狀態(tài),Nj表示子區(qū)域Mj中部署的節(jié)點(diǎn)個(gè)數(shù),seti表示子區(qū)域Mj中節(jié)點(diǎn)si感知范圍內(nèi)的網(wǎng)格集合,Ei表示節(jié)點(diǎn)si的存活狀態(tài),a表示網(wǎng)格劃分步長,ei表示節(jié)點(diǎn)si的能量剩余。

綜上,定義分塊區(qū)域p-覆蓋節(jié)點(diǎn)調(diào)度問題如下:

定義3(分塊區(qū)域p-覆蓋節(jié)點(diǎn)調(diào)度問題) 給定滿足p-覆蓋的區(qū)域M,通過設(shè)計(jì)節(jié)點(diǎn)調(diào)度算法使之在滿足p-覆蓋的前提下盡可能延長網(wǎng)絡(luò)生存時(shí)間。

3 本文算法

根據(jù)上節(jié)對(duì)節(jié)點(diǎn)及網(wǎng)絡(luò)覆蓋模型的定義,由于有向傳感節(jié)點(diǎn)感知區(qū)域?yàn)樯刃?并且節(jié)點(diǎn)感知模型異構(gòu)且扇形的相交區(qū)域多為非凸多邊形,通常在判斷感知區(qū)域時(shí),可以將連續(xù)的節(jié)點(diǎn)監(jiān)測區(qū)域看作是由均勻離散的點(diǎn)組成,因此本文采用網(wǎng)格劃分的方法來刻畫節(jié)點(diǎn)覆蓋區(qū)域,在網(wǎng)格化完成后,節(jié)點(diǎn)的監(jiān)測區(qū)域通過網(wǎng)格點(diǎn)集合來表示。根據(jù)上文問題描述及定義,本文設(shè)計(jì)了如下調(diào)度算法。

3.1 分區(qū)域節(jié)點(diǎn)調(diào)度算法

假設(shè)有充足的節(jié)點(diǎn)被部署在二維區(qū)域M,區(qū)域M根據(jù)實(shí)際覆蓋需求分為J子區(qū)域,并且節(jié)點(diǎn)部署滿足p-覆蓋,即

針對(duì)任意子區(qū)域Mj,有

(5)

圖3 網(wǎng)絡(luò)工作模式

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

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

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

在每一個(gè)網(wǎng)絡(luò)周期的開始,下面的算法都會(huì)在所有子區(qū)域中執(zhí)行,來構(gòu)建能夠?qū)ψ訁^(qū)域提供pj比例覆蓋的worksetj。在描述算法之前,先做如下定義:

網(wǎng)格點(diǎn)狀態(tài)(有效、無效) 針對(duì)任一節(jié)點(diǎn)si的感知網(wǎng)格點(diǎn)集seti,若seti中某一網(wǎng)格點(diǎn)已經(jīng)被worksetj中的節(jié)點(diǎn)覆蓋,則稱在seti中該網(wǎng)格點(diǎn)狀態(tài)為無效,否則稱該網(wǎng)格點(diǎn)狀態(tài)為有效。

有效網(wǎng)格點(diǎn)集Useti節(jié)點(diǎn)si感知網(wǎng)格點(diǎn)集seti中未被標(biāo)記為無效的網(wǎng)格點(diǎn)集合,初始狀態(tài)下Useti與seti相等。

重復(fù)網(wǎng)格點(diǎn)集Rseti節(jié)點(diǎn)si感知網(wǎng)格點(diǎn)集中被標(biāo)記為無效的網(wǎng)格點(diǎn)集合,初始狀態(tài)下Rseti為空。

子區(qū)域j當(dāng)前覆蓋網(wǎng)格點(diǎn)集Allnumj當(dāng)前周期的決策期結(jié)束后,所有工作標(biāo)志位q為1的節(jié)點(diǎn)所覆蓋的網(wǎng)格點(diǎn)數(shù)目(集合中無重復(fù)網(wǎng)格點(diǎn))。

3.1.1 選取階段算法

算法1 選取階段算法(執(zhí)行于每一個(gè)節(jié)點(diǎn)si)

輸入:子區(qū)域Mj的覆蓋需求pj,Mj的面積Sj,網(wǎng)格步長a

輸出:工作節(jié)點(diǎn)集worksetj(部分)

執(zhí)行:

1:初始化:

2: Allnumj=0qi=0

3: 隨機(jī)選擇一節(jié)點(diǎn),向其發(fā)送消息包msg(beRoot)

4: (算法執(zhí)行于任一子區(qū)域Mj中的任一節(jié)點(diǎn)si中)

5:節(jié)點(diǎn)自動(dòng)喚醒

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: 計(jì)算worthi的值,并封裝為消息包msg(worthi),回傳至其鄰居根節(jié)點(diǎn)sroot

23: end if

24:end if

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

26: ifq=0

27: throw msg

28: else

29: 選擇最大的兩個(gè)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發(fā)送消息包msg(beRoot)

37: end if

38:end if

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

40: if Refworth!=0

41:snextroot=sRefworth

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

43: else

44: ifspreviousroot==NULL

45: 宣告子區(qū)域死亡,算法在該子區(qū)域Mj中停止執(zhí)行

46: else

47: 向節(jié)點(diǎn)spreviousroot發(fā)送消息包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

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

(6)

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

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

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

3.1.2 連通階段算法

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

算法2 連通階段算法(執(zhí)行于每一個(gè)節(jié)點(diǎn)si)

輸入:節(jié)點(diǎn)工作集worksetj(部分)(即算法2的輸出)

輸出:節(jié)點(diǎn)工作集worksetj

執(zhí)行:

1:(算法執(zhí)行于任一子區(qū)域Mj中的任一節(jié)點(diǎn)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更新節(jié)點(diǎn)自身維護(hù)的Mindistancez

12:else

13: 用節(jié)點(diǎn)自身維護(hù)的Mindistancez更新distancez

14: 向鄰居節(jié)點(diǎn)廣播消息包msg(connect)

15:endif

16endif

17:endif

18:endif

19:ifMindistancej+Mindistancek≤Maxstep

20: q=1

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

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

23:endif

24:ifq=0

25: 轉(zhuǎn)至休眠狀態(tài)直至下周期開始時(shí)喚醒

26:endif

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

3.1.3 算法復(fù)雜度分析

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

由于算法獨(dú)立執(zhí)行于每一個(gè)節(jié)點(diǎn),因此我們選任一節(jié)點(diǎn)si為例,分析其計(jì)算復(fù)雜度。針對(duì)任一節(jié)點(diǎn)si,算法執(zhí)行過程中復(fù)雜度最高的是更新自身所維護(hù)的有效網(wǎng)格點(diǎn)集Useti和重復(fù)網(wǎng)格點(diǎn)集Rseti以及worth值的計(jì)算。更新操作僅僅需要兩個(gè)集合的對(duì)比,而worth值計(jì)算也較為簡單,因此算法整體計(jì)算復(fù)雜度不高。

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

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

3.2 worth值的計(jì)算

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

(7)

其中e代表節(jié)點(diǎn)剩余能量。當(dāng)numof(Useti)=0時(shí),代表節(jié)點(diǎn)si的Useti中沒有網(wǎng)格點(diǎn),即其不能提供任何覆蓋貢獻(xiàn),此時(shí)將worthi值置0。λ、η、γ 3個(gè)變量根據(jù)不同應(yīng)用場景或部署情況來取值調(diào)整3個(gè)參數(shù)的權(quán)重。

4 仿真實(shí)驗(yàn)

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

表1 子區(qū)域劃分情況

其他參數(shù)設(shè)置如表2所示。其中為方便比較,將節(jié)點(diǎn)剩余能量e的單位規(guī)格化為節(jié)點(diǎn)能夠工作的網(wǎng)絡(luò)周期數(shù),如e=5,表示節(jié)點(diǎn)剩余能量能夠保證其正常工作5個(gè)網(wǎng)絡(luò)周期。

表2 算法仿真參數(shù)設(shè)置

不考慮整體網(wǎng)絡(luò)覆蓋度f,考察在4個(gè)調(diào)度算法調(diào)度下的各子區(qū)域最大生存時(shí)長,結(jié)果如圖4所示。

圖4 不同算法調(diào)度下的各子區(qū)域生存時(shí)長對(duì)比

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

下面抽取其中兩個(gè)子區(qū)域M6和M9對(duì)比4種算法在選取節(jié)點(diǎn)工作集worksetj時(shí)的效率。

圖5 節(jié)點(diǎn)工作集合選取效率對(duì)比

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

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

圖6 不同網(wǎng)絡(luò)覆蓋度下的算法性能表現(xiàn)對(duì)比

為對(duì)比不同節(jié)點(diǎn)部署密度下的算法性能表現(xiàn),在上文仿真實(shí)驗(yàn)的基礎(chǔ)上,對(duì)每一個(gè)子區(qū)域中節(jié)點(diǎn)部署個(gè)數(shù)減半和翻倍,分別重新進(jìn)行仿真實(shí)驗(yàn),如圖7和圖8所示。

圖7 子區(qū)域節(jié)點(diǎn)部署數(shù)量減半時(shí)4種算法性能對(duì)比

圖8 子區(qū)域節(jié)點(diǎn)部署數(shù)量翻倍時(shí)4種算法性能對(duì)比

其中圖7和圖8分別表示每個(gè)子區(qū)域的節(jié)點(diǎn)部署數(shù)量減半和翻倍時(shí),4種算法調(diào)度下的網(wǎng)絡(luò)生存時(shí)間對(duì)比。結(jié)合圖6初始節(jié)點(diǎn)部署個(gè)數(shù)的對(duì)比圖表,可以看出DSSA算法不論節(jié)點(diǎn)部署密度大小,性能表現(xiàn)始終明顯領(lǐng)先于其他3種算法。同時(shí)隨著節(jié)點(diǎn)部署密度的增加,DSSA算法相比其他3種算法的優(yōu)勢逐步拉大。

5 結(jié)語

為延長分塊區(qū)域p-覆蓋有向傳感網(wǎng)絡(luò)的生存時(shí)間,本文提出一種基于網(wǎng)格劃分的分區(qū)域節(jié)點(diǎn)調(diào)度算法DSSA。首先對(duì)節(jié)點(diǎn)感知范圍網(wǎng)格化劃分,然后在每一個(gè)子區(qū)域的執(zhí)行算法貪心式的進(jìn)行節(jié)點(diǎn)工作集的選取調(diào)度。DSSA算法還對(duì)整體網(wǎng)絡(luò)的連通進(jìn)行了考慮。仿真實(shí)驗(yàn)表明,該算法對(duì)比已有算法表現(xiàn)出了良好的性能和穩(wěn)定性。

[1]孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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]劉端陽,暴占兵,程珍.一種可分負(fù)載WSN的能耗均衡負(fù)載調(diào)度算法[J].傳感技術(shù)學(xué)報(bào),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]韓崇,孫力娟,郭劍.一種基于網(wǎng)格劃分的有向傳感網(wǎng)時(shí)空覆蓋調(diào)度算法[J].南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),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]張蕾.無線傳感器網(wǎng)絡(luò)中多重覆蓋算法的研究[J].傳感技術(shù)學(xué)報(bào),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-),男,碩士,南京郵電大學(xué)計(jì)算機(jī)學(xué)院碩士研究生,主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)及應(yīng)用;

孫力娟(1963-),女,教授,博士生導(dǎo)師,研究方向?yàn)檠莼?jì)算、無線傳感器網(wǎng)絡(luò)和數(shù)據(jù)處理等;

韓 崇(1985-),男,博士,講師,研究生方向?yàn)槎嗝襟w信息處理、數(shù)據(jù)挖掘;

郭 劍(1978-),男,副教授,碩士生導(dǎo)師,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、無線多媒體傳感器網(wǎng)絡(luò)。

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61171053,61300239);教育部博士點(diǎn)基金項(xiàng)目(20113223110002);中國博士后科學(xué)基金項(xiàng)目(2014M551635);江蘇省博士后科研資助計(jì)劃項(xiàng)目(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