一種分區(qū)的全向傳感器柵欄覆蓋構(gòu)建算法*

任勇默,牛玉剛*,賈廷綱

(1.華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237;2.上海電氣自動化集團(tuán),上海 200070)

一種分區(qū)的全向傳感器柵欄覆蓋構(gòu)建算法*

任勇默1,牛玉剛1*,賈廷綱2

(1.華東理工大學(xué)化工過程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237;2.上海電氣自動化集團(tuán),上海 200070)

柵欄覆蓋是傳感器網(wǎng)絡(luò)覆蓋控制的研究熱點(diǎn)之一。提出一種全向傳感器柵欄分區(qū)構(gòu)建算法(FCOIS)。算法中節(jié)點(diǎn)采取全向傳感器感知模型,依照節(jié)點(diǎn)初始分布狀態(tài)劃分子區(qū)域,使每個子區(qū)域內(nèi)節(jié)點(diǎn)個數(shù)盡量相等,并根據(jù)每個子區(qū)域內(nèi)節(jié)點(diǎn)的分布情況確定柵欄的形成區(qū)間。在每個子區(qū)域內(nèi),依照從左至右的順序構(gòu)建柵欄,當(dāng)各子區(qū)域的柵欄構(gòu)建完畢后,采用貪婪算法對相鄰子區(qū)域間柵欄的空隙進(jìn)行填充。仿真結(jié)果證明該算法能夠以較低的總能耗、平均能耗構(gòu)建柵欄,顯著節(jié)省了節(jié)點(diǎn)的使用數(shù)量與通信開銷。

全向傳感器;柵欄覆蓋;FCOIS;子區(qū)域;通信開銷

全向傳感器相較于有向傳感器,有著更廣闊的感知視角,適用于在死角較多的地域集中監(jiān)控,或用于復(fù)雜地理環(huán)境下的險(xiǎn)情檢測。若干個傳感器節(jié)點(diǎn)所構(gòu)成的集合,能夠?qū)⒈O(jiān)控區(qū)域進(jìn)行分隔,用于感知進(jìn)行跨區(qū)域穿越的目標(biāo),這種技術(shù)被稱為柵欄覆蓋。在柵欄覆蓋問題中,由全向傳感器組成的柵欄稱為全向柵欄,由有向傳感器組成的柵欄稱為有向柵欄。在全向柵欄研究方面,如何提高柵欄的相關(guān)性能,并降低形成柵欄的難度,是無線傳感器網(wǎng)絡(luò)領(lǐng)域的一個研究熱點(diǎn)[1]。

1 相關(guān)工作

目前已有許多與柵欄覆蓋相關(guān)的研究工作[2-15],其中,文獻(xiàn)[2]中定義了強(qiáng)柵欄、弱柵欄;文獻(xiàn)[3]中提出了節(jié)點(diǎn)部署密度與感知目標(biāo)概率之間的關(guān)系式;文獻(xiàn)[4]研究了在有向傳感器節(jié)點(diǎn)部署密度較大時(shí),僅采取轉(zhuǎn)動節(jié)點(diǎn)方式完成柵欄部署,但此方式不適用于全向柵欄的構(gòu)建;文獻(xiàn)[5]中提出了在柵欄系統(tǒng)中移動傳感器的方式,以用于提前捕獲目標(biāo);文獻(xiàn)[6]提出了strong-greedy算法與strong-optimal算法,能夠在節(jié)點(diǎn)密度較高時(shí),利用原有的連通部分,再用貪婪算法與最優(yōu)匹配算法完成對空隙部分的拼接,從而構(gòu)建柵欄;文獻(xiàn)[7]提出了異構(gòu)傳感器模型下的覆蓋部署策略,但異構(gòu)模型下的每個節(jié)點(diǎn)權(quán)重不一致,部署策略不完全適用于同構(gòu)模型;文獻(xiàn)[8]研究了矩形分區(qū)狀態(tài)下柵欄最少節(jié)點(diǎn)數(shù)目與節(jié)點(diǎn)間距的計(jì)算方法,但最少的節(jié)點(diǎn)數(shù)與節(jié)點(diǎn)間距并不代表節(jié)點(diǎn)的能耗與通信開銷最小;文獻(xiàn)[10]提出PMNSB算法,采用以總移動距離最小為目標(biāo)的匹配方式分區(qū)構(gòu)建柵欄,但PMNSB算法下總移動距離最小有著較嚴(yán)格的約束條件,且分區(qū)方法為等分監(jiān)控區(qū)域,并未考慮節(jié)點(diǎn)在區(qū)域內(nèi)的分布權(quán)重;文獻(xiàn)[11]提出了一種在柵欄出現(xiàn)空洞時(shí),分階段修補(bǔ)柵欄的策略;文獻(xiàn)[12]提出了一種分布式自學(xué)習(xí)算法,能夠提高柵欄系統(tǒng)的生存周期,但未對柵欄本身的構(gòu)建方式進(jìn)行優(yōu)化;文獻(xiàn)[13]提出了在鏈路可靠前提下,能夠增強(qiáng)網(wǎng)絡(luò)壽命的策略;文獻(xiàn)[14]提出了最少節(jié)點(diǎn)構(gòu)建k條不相交的柵欄,但使用最少節(jié)點(diǎn)不能保證單個節(jié)點(diǎn)最低的能耗;文獻(xiàn)[15]研究了雷達(dá)傳感器以總移動距離最小為目標(biāo)實(shí)施區(qū)域覆蓋,但該方法在柵欄工作時(shí),需要激活柵欄中所有的節(jié)點(diǎn)同時(shí)工作,需要較高的通信開銷。

本文將通過優(yōu)化劃分子區(qū)域的方式,對全向柵欄構(gòu)建算法的性能進(jìn)行改進(jìn)。后續(xù)內(nèi)容安排如下:第3節(jié)描述網(wǎng)絡(luò)模型。第4節(jié)給出基于分區(qū)的全向同構(gòu)傳感器強(qiáng)柵欄構(gòu)建方法(FCOIS)。第5節(jié)通過仿真實(shí)驗(yàn)對提出的算法進(jìn)行性能評估。第6節(jié)總結(jié)全文并指出下一步工作。

2 相關(guān)模型和定義

全向傳感器節(jié)點(diǎn)感知模型如圖1所示。

圖1 全向傳感器的傳感模型

圖1中,r表示節(jié)點(diǎn)的感知半徑,O點(diǎn)的位置即為節(jié)點(diǎn)位于坐標(biāo)軸中的相對位置(坐標(biāo)),P點(diǎn)為一個需要被感知的目標(biāo),則當(dāng)|OP|≤r時(shí),目標(biāo)才能夠被節(jié)點(diǎn)感知,同時(shí)節(jié)點(diǎn)發(fā)出感知到目標(biāo)的通信信號。

本文對所研究的全向傳感器柵欄問題,作如下假設(shè):①在監(jiān)控區(qū)域內(nèi),所有傳感器節(jié)點(diǎn)均是同構(gòu)的,節(jié)點(diǎn)以隨機(jī)投撒形式分布在區(qū)域內(nèi)。投撒完畢后,每個節(jié)點(diǎn)在區(qū)域內(nèi)的相對橫、縱坐標(biāo)均已知;②監(jiān)控區(qū)域內(nèi)的地理環(huán)境無差別,所有節(jié)點(diǎn)在區(qū)域內(nèi)的單位移動能耗均相同;③在監(jiān)控區(qū)域內(nèi),所有節(jié)點(diǎn)在感知到目標(biāo),輸出通信信號時(shí),相應(yīng)的通信輸出功率均相同;④所有節(jié)點(diǎn)均是無故障的。

定義1節(jié)點(diǎn)的運(yùn)動能耗:節(jié)點(diǎn)的移動距離與單位移動能耗的乘積。

定義2節(jié)點(diǎn)通信開銷:節(jié)點(diǎn)感知到穿越目標(biāo)后,輸出信號所消耗的能量。

定義3節(jié)點(diǎn)的投撒密度:傳感器節(jié)點(diǎn)總數(shù)與監(jiān)控區(qū)域面積的比值ρ。投撒密度對柵欄形成過程中的能耗與通信開銷有著顯著影響,后面在仿真實(shí)驗(yàn)中會進(jìn)行詳細(xì)分析。

本文研究的問題:在監(jiān)控區(qū)域中以密度ρ隨機(jī)部署節(jié)點(diǎn)之后,如何移動節(jié)點(diǎn),節(jié)省每個節(jié)點(diǎn)的運(yùn)動能耗,減少每條柵欄構(gòu)建時(shí)所需要的節(jié)點(diǎn)數(shù)量,并盡量降低柵欄后續(xù)工作時(shí)的通信開銷。

3 基于分區(qū)的全向同構(gòu)傳感器柵欄構(gòu)建算法(FCOIS)

文獻(xiàn)[6]中提出的strong-greedy算法通過先搜索初始狀態(tài)下連通的節(jié)點(diǎn),再通過對比各個連通區(qū)域之間的距離,進(jìn)一步地選定柵欄所需的連通區(qū)域,而后采取貪婪算法將連通區(qū)域之間的空隙用其余的節(jié)點(diǎn)進(jìn)行填補(bǔ),這需要耗費(fèi)大量的節(jié)點(diǎn)。文獻(xiàn)[10]中提出的PMNSB算法將監(jiān)控區(qū)域分成若干個子區(qū)域之后,同時(shí)在各個子區(qū)域內(nèi)形成柵欄,而后再將各個子區(qū)域之間的柵欄用豎直柵欄進(jìn)行連接,從而形成整個監(jiān)控區(qū)域的柵欄。但豎直柵欄的使用增加了區(qū)域內(nèi)節(jié)點(diǎn)的使用數(shù)量,同時(shí)也增大了子區(qū)域內(nèi)柵欄工作狀態(tài)下的通信開銷。

針對上述問題,本文研究如何更合理地劃分子區(qū)域,并在子區(qū)域內(nèi)更充分地應(yīng)用各節(jié)點(diǎn)之間的位置關(guān)系構(gòu)建柵欄,提出了一種分區(qū)的全向傳感器柵欄構(gòu)建算法FCOIS(Fence Construction for Omnidirectional Isomorphism Sensor based on subarea)。整體監(jiān)測區(qū)域的柵欄主體由各個子區(qū)域內(nèi)柵欄的并集組成,若相鄰子區(qū)域內(nèi)柵欄之間有空隙,則需要沿豎直方向進(jìn)行填補(bǔ)。

3.1 算法實(shí)現(xiàn)步驟

FCOIS算法具體步驟如下:

步驟1 設(shè)定子區(qū)域個數(shù),并確定各子區(qū)域邊界 將需劃分的子區(qū)域個數(shù)記作V,投撒的傳感器節(jié)點(diǎn)總數(shù)記作n,并將每個節(jié)點(diǎn)的橫坐標(biāo)按照從小到大的順序進(jìn)行排列,將從小到大順序下排位為|n/V|的節(jié)點(diǎn)計(jì)入第1個子區(qū)域,并將其橫坐標(biāo)記為l1,則直線x=l1與監(jiān)控區(qū)域的公共交線為第1個子區(qū)域的右邊界,同時(shí)也為第2個子區(qū)域的左邊界。同理,將排位為2|n/V|的節(jié)點(diǎn)計(jì)入第2個子區(qū)域,并將其橫坐標(biāo)記為l2,直線x=l2與監(jiān)控區(qū)域的公共交線作為第2個子區(qū)域的右邊界…直至第V個子區(qū)域的左右邊界分別為x=lV-1與x=L(x=L即為整個監(jiān)控區(qū)域的右邊界)。如圖2所示,即為節(jié)點(diǎn)數(shù)n=7,子區(qū)域數(shù)V=3下的子區(qū)域劃分方式。顯然,為了盡量使每個子區(qū)域內(nèi)的節(jié)點(diǎn)個數(shù)盡可能均等(即第V個子區(qū)域內(nèi)節(jié)點(diǎn)個數(shù)不能明顯多于前V-1個子區(qū)域),在實(shí)際應(yīng)用中,子區(qū)域的劃分個數(shù)V應(yīng)遵循n?V的選取原則。

圖2 子區(qū)域的劃分

步驟2 確定柵欄的預(yù)設(shè)區(qū)域 在每個子區(qū)域內(nèi),統(tǒng)計(jì)節(jié)點(diǎn)縱坐標(biāo)范圍分別在0≤y≤2r、2r

步驟3 確定各子區(qū)域內(nèi)柵欄的首節(jié)點(diǎn) 在預(yù)設(shè)區(qū)域內(nèi),選出每個子區(qū)域中橫坐標(biāo)最小的節(jié)點(diǎn)作為各子區(qū)域柵欄的首節(jié)點(diǎn),若首節(jié)點(diǎn)橫坐標(biāo)與左邊界之差大于半徑r,則令其向左平行移動至恰與左邊界相切,如圖3(a)所示,首節(jié)點(diǎn)從A點(diǎn)運(yùn)動至B點(diǎn);若其橫坐標(biāo)與左邊界之差小于等于半徑r,則該節(jié)點(diǎn)不移動,如圖3(b)所示。

圖3 首節(jié)點(diǎn)運(yùn)動方式

步驟4 在各子區(qū)域內(nèi)形成柵欄 在各子區(qū)域內(nèi),判斷剩余的所有節(jié)點(diǎn)中,是否有節(jié)點(diǎn)的感知區(qū)域與首節(jié)點(diǎn)感知區(qū)域相交。若有,選出其中橫坐標(biāo)最大的節(jié)點(diǎn)作為第2個節(jié)點(diǎn),不進(jìn)行移動,如圖4(a)所示,選取C點(diǎn)作為第2個節(jié)點(diǎn);若沒有節(jié)點(diǎn)的感知區(qū)域與首節(jié)點(diǎn)感知區(qū)域相交(或相切),則以首節(jié)點(diǎn)正右方向+2r處作為第2個節(jié)點(diǎn)的目標(biāo)位置,選取距離此目標(biāo)位置最近的節(jié)點(diǎn)移動至該目標(biāo)位置,如圖4(b)所示,由于|BC|≤|AC|,選取B處節(jié)點(diǎn)移動至C點(diǎn)作為第2個節(jié)點(diǎn)。

圖4 節(jié)點(diǎn)的選擇

在第i(i≥2)個節(jié)點(diǎn)移動完畢后,依照同樣的節(jié)點(diǎn)選取方式選取第i+1個節(jié)點(diǎn)。隨著i的逐一增加,直至第i+1個節(jié)點(diǎn)能夠與子區(qū)域右邊界產(chǎn)生交點(diǎn),子區(qū)域內(nèi)的柵欄構(gòu)建完畢。子區(qū)域內(nèi)所剩余的節(jié)點(diǎn)不移動。

步驟5 在監(jiān)控區(qū)域整體上形成首條柵欄 當(dāng)各子區(qū)域內(nèi)柵欄構(gòu)建完畢,判斷相鄰子區(qū)域間的柵欄是否有相交部分。若是,則不需填充節(jié)點(diǎn);否則,則從周圍挑選節(jié)點(diǎn),按豎直方向?qū)ο噜徸訁^(qū)域間的柵欄空隙進(jìn)行填充,節(jié)點(diǎn)依照貪婪算法選取,使填充段內(nèi)各節(jié)點(diǎn)運(yùn)動能耗最小。

步驟6 構(gòu)建其余K-1條柵欄 若K>1,從剩余的區(qū)域段中找出節(jié)點(diǎn)個數(shù)最多的區(qū)域段(之前已參與構(gòu)建柵欄的節(jié)點(diǎn)不重復(fù)計(jì)入),重復(fù)步驟2至步驟5的操作,形成第2條至第K條柵欄,算法結(jié)束。

FCOIS算法偽代碼如下:

01:Divide the subareas in the area

02:In each subarea,the interval section with the largest number of nodes is selected

03:The interval in which the node is the most is the final preset area

04:Determine the first node in each subarea

05:If the first node intersects the left border

06:The first node remains in place

07:Else move parallel to the left until tangent to the left border

08:If the next node perceived range intersects the perceived range of the node

09:The next node remains in place

10:Else select the nearest distance node to move to the target position on the right side of the node,and the distance from the node is equal to the diameter of the sensing range

11:Repeat the above operation until the fence in the subarea is formed

12:If there is a gap between the fence of the subarea

13:The nodes fill the voids according to the greedy algorithm

14:End

15:Delete the used nodes

16:If the number of fencesK>1

17:Build the remainingK-1 fences

18:End

3.2 算法的性能分析

如果監(jiān)控區(qū)域未分區(qū),那么為了避免目標(biāo)穿越柵欄時(shí)出現(xiàn)遺漏目標(biāo)的情況,整條柵欄上的節(jié)點(diǎn)均需被激活至工作狀態(tài)。然而,在監(jiān)控區(qū)域內(nèi)采取劃分子區(qū)域的方式,當(dāng)目標(biāo)穿越時(shí),僅需激活子區(qū)域內(nèi)柵欄的節(jié)點(diǎn),有效地減少了激活節(jié)點(diǎn)的數(shù)量,降低通信開銷。如圖5所示。

圖5 目標(biāo)穿越子區(qū)域內(nèi)的柵欄

當(dāng)節(jié)點(diǎn)投撒完畢之后,選出各子區(qū)域中節(jié)點(diǎn)個數(shù)最多,且節(jié)點(diǎn)縱坐標(biāo)分布最集中的區(qū)域段作為每個子區(qū)域內(nèi)柵欄的預(yù)設(shè)區(qū)域,能夠盡可能地減少各子區(qū)域間柵欄豎直方向的偏差,并降低節(jié)點(diǎn)豎直分量上的移動距離,從而節(jié)省單個節(jié)點(diǎn)的運(yùn)動能耗。

在各子區(qū)域內(nèi),若采取從中間至兩側(cè)邊界的構(gòu)建方式構(gòu)建柵欄,可能會導(dǎo)致柵欄兩端朝向兩個相反的方向偏離,這將加大柵欄豎直方向上的偏差程度,使各子區(qū)域間柵欄的拼接需要更多的節(jié)點(diǎn)。同時(shí),柵欄耗費(fèi)更多的節(jié)點(diǎn)將導(dǎo)致總能耗與通信開銷增大。因此,為了盡量降低各相鄰子區(qū)域間柵欄豎直方向上的偏移程度,降低子區(qū)域邊界上柵欄拼接所使用的節(jié)點(diǎn)數(shù),不失一般性,規(guī)定各子區(qū)域內(nèi)柵欄的構(gòu)建順序?yàn)閺淖笾劣摇?/p>

在時(shí)間復(fù)雜度方面,由于計(jì)算每個節(jié)點(diǎn)的運(yùn)動狀態(tài)所花費(fèi)的時(shí)間相同,依照時(shí)間復(fù)雜度定義,考慮在最壞情況下,每個子區(qū)域內(nèi)的節(jié)點(diǎn)恰好全部參與形成柵欄。設(shè)節(jié)點(diǎn)總數(shù)為n,劃分了V個子區(qū)域。由于每個子區(qū)域內(nèi)的節(jié)點(diǎn)不多于|n/V|個,且各子區(qū)域內(nèi)柵欄的構(gòu)建同時(shí)進(jìn)行。因此在不多于|n/V|個節(jié)點(diǎn)中選出第1個節(jié)點(diǎn),然后從|n/V|-1個節(jié)點(diǎn)中選出第2個節(jié)點(diǎn),以此類推,直至柵欄形成完畢,時(shí)間復(fù)雜度為:O(|n/V|)2。若不劃分子區(qū)域,即V=1,則時(shí)間復(fù)雜度為O(n)2。采取劃分子區(qū)域的方式,有效地降低了算法的時(shí)間復(fù)雜度。

4 仿真結(jié)果

本文運(yùn)用MATLAB7.0對此算法進(jìn)行仿真,每組實(shí)驗(yàn)數(shù)據(jù)采用重復(fù)100次獨(dú)立實(shí)驗(yàn)取平均值的方式獲得。實(shí)驗(yàn)所涉及的參數(shù)指標(biāo)如表1所示。

表1 參數(shù)說明

如果沒有特別指明特定參數(shù)的數(shù)值,參數(shù)的默認(rèn)值如表2所示。我們選取了文獻(xiàn)[6]中的strong-greedy算法與文獻(xiàn)[10]中的PMNSB算法與本文中的FCOIS算法進(jìn)行了仿真比較。參考文獻(xiàn)[6]和文獻(xiàn)[10]中的實(shí)驗(yàn)數(shù)據(jù),規(guī)定每個傳感器節(jié)點(diǎn)的感知半徑為5 m,每移動1個單位長度消耗3.6 J的能量。目標(biāo)每穿越1次柵欄,單個節(jié)點(diǎn)激活通信信號消耗1.5 J的能量。

圖6 FCOIS算法

參數(shù)取值L300mW200mJ13.6J/mJ21.5J/次P00.006個/m2K2V3

在默認(rèn)參數(shù)下,給定同一初始節(jié)點(diǎn)投撒條件,FCOIS算法、strong-greedy算法、PMNSB算法形成的柵欄分別如圖6～圖8所示,可以看出,在同一初始投撒條件下,FCOIS算法構(gòu)建2條柵欄所使用的節(jié)點(diǎn)數(shù)量明顯少于strong-greedy算法與PMNSB算法。

圖7 strong-greedy算法

圖8 PMNSB算法

4.1 節(jié)點(diǎn)密度的影響

由于strong-greedy算法需要依賴監(jiān)控區(qū)域內(nèi)大量的連通區(qū)域,當(dāng)投撒密度較低時(shí)可能會出現(xiàn)節(jié)點(diǎn)數(shù)量不足的情況,在較高投撒密度下才能發(fā)揮較好的性能。因此為了兼顧strong-greedy算法的應(yīng)用要求,使對比結(jié)果更有意義,實(shí)驗(yàn)中以0.004的投撒密度起始,逐次將投撒密度遞增0.001,直至0.008截止,其余實(shí)驗(yàn)參數(shù)值與表2所示參數(shù)一致。仿真實(shí)驗(yàn)結(jié)果如圖9～圖12所示。

圖9 節(jié)點(diǎn)密度VS總能耗

圖10 節(jié)點(diǎn)密度VS平均能耗

從圖9中可以看到,當(dāng)投撒密度增加時(shí),3種算法的總能耗均明顯下降,FCOIS算法的總能耗始終低于strong-greedy算法與PMNSB算法。雖然PMNSB算法在各子區(qū)域生成柵欄時(shí),采取以總能耗最小為優(yōu)化目標(biāo)的部署策略,但其豎直柵欄的選取位置并非最優(yōu),對約束條件造成了影響,間接提高了PMNSB算法的總能耗。從圖10中可以看到,隨著密度從0.004增至0.008,節(jié)點(diǎn)的分布更密集,在3種算法下,每個節(jié)點(diǎn)平均移動的距離都減小。但隨著密度的增大,在FCOIS算法中,節(jié)點(diǎn)感知區(qū)域之間出現(xiàn)相交的情況會增多,使得平均能耗得到了進(jìn)一步的降低,相較strong-greedy算法和PMNSB算法,平均能耗下降的速率更快。這說明FCOIS算法中比strong-greedy算法和PMNSB算法更有效地利用了初始狀態(tài)下連通的節(jié)點(diǎn)。

圖11 節(jié)點(diǎn)密度VS能耗標(biāo)準(zhǔn)差

圖12 節(jié)點(diǎn)密度VS柵欄使用節(jié)點(diǎn)數(shù)

對比圖11、圖12可以看到,對strong-greedy算法來說,雖然事先尋找到了若干個節(jié)點(diǎn)連通區(qū)域,但在節(jié)點(diǎn)密度較低時(shí),其余節(jié)點(diǎn)需要移動更多的距離來填補(bǔ)空隙,導(dǎo)致了節(jié)點(diǎn)的能耗分布不均勻,能耗標(biāo)準(zhǔn)差較大,柵欄使用的節(jié)點(diǎn)數(shù)也較多,隨著節(jié)點(diǎn)密度增大,使用的節(jié)點(diǎn)數(shù)大幅增加,能耗標(biāo)準(zhǔn)差也相應(yīng)地減少。對PMNSB算法來說,以總能耗最小為最優(yōu)目標(biāo),在約束條件下使用的節(jié)點(diǎn)個數(shù)較為穩(wěn)定,幾乎不隨節(jié)點(diǎn)密度變化而變化,但總能耗最小的優(yōu)化目標(biāo)會部分犧牲節(jié)點(diǎn)能耗分布的均勻性,且各子區(qū)域間柵欄的預(yù)設(shè)區(qū)域不統(tǒng)一,導(dǎo)致豎直柵欄上使用了較多節(jié)點(diǎn),進(jìn)一步增大了能耗標(biāo)準(zhǔn)差。在FCOIS算法中,隨著節(jié)點(diǎn)密度增大,感知區(qū)域連通的節(jié)點(diǎn)更多的參與構(gòu)建柵欄,導(dǎo)致柵欄使用的節(jié)點(diǎn)數(shù)相應(yīng)增多。又因?yàn)樵贔COIS算法中,各子區(qū)域內(nèi)柵欄的預(yù)設(shè)區(qū)域得到統(tǒng)一,豎直方向上用于填充空隙的節(jié)點(diǎn)較少,且豎直方向節(jié)點(diǎn)采取貪婪算法部署柵欄。在這些因素的綜合作用下,FCOIS算法的能耗標(biāo)準(zhǔn)差始終明顯低于strong-greedy算法與PMNSB算法。

4.2 柵欄的通信開銷

當(dāng)目標(biāo)穿越柵欄時(shí),目標(biāo)所屬子區(qū)域內(nèi),柵欄上的節(jié)點(diǎn)都會被激活,并發(fā)出通信信號。為了更準(zhǔn)確地反映各算法下,目標(biāo)穿越柵欄時(shí)的通信開銷,并對比各算法在實(shí)際環(huán)境下的性能,仿真實(shí)驗(yàn)中采取逐一增大柵欄條數(shù)K,進(jìn)行100次目標(biāo)隨機(jī)穿越柵欄實(shí)驗(yàn)求平均值的方式,對各算法下柵欄的通信開銷進(jìn)行對比。同時(shí),為控制變量,避免實(shí)驗(yàn)數(shù)據(jù)受到其他因素的干擾,除柵欄數(shù)K之外的其余實(shí)驗(yàn)參數(shù)均與表2中一致,仿真結(jié)果如圖13所示。

圖13 柵欄數(shù)K VS 通信開銷

從圖13可以看出,隨著柵欄數(shù)K的增加,由于預(yù)設(shè)區(qū)域的設(shè)定,FCOIS算法與PMNSB算法的子區(qū)域內(nèi)節(jié)點(diǎn)數(shù)增加幅度較穩(wěn)定,使FCOIS算法與PMNSB算法的通信開銷呈近似線性增長。又因?yàn)镻MNSB算法使用更多的節(jié)點(diǎn)構(gòu)建豎直柵欄,因此FCOIS算法的通信開銷始終明顯低于PMNSB算法。而strong-greedy算法在構(gòu)建前3條柵欄時(shí)的節(jié)點(diǎn)較充裕,導(dǎo)致strong-greedy算法的通信開銷在K=1～3時(shí)增長速度較大,而在構(gòu)建第4、第5條柵欄時(shí),由于連通區(qū)域減少,可供參與構(gòu)建柵欄的節(jié)點(diǎn)減少,使第4、第5條柵欄工作狀態(tài)下整體的通信開銷降低,通信開銷隨柵欄數(shù)K的增長速度變小,但整體通信開銷明顯大于FCOIS算法與PMNSB算法。不難推測:若節(jié)點(diǎn)數(shù)量足夠充裕,隨著柵欄數(shù)K的增大,FCOIS算法構(gòu)建的柵欄,在工作狀態(tài)下,相較strong-greedy算法與PMNSB算法構(gòu)建的柵欄,能夠明顯降低通信開銷,具備穩(wěn)定的性能。

5 結(jié)論

本文主要研究基于分區(qū)的柵欄構(gòu)建問題,提出FCOIS算法,按節(jié)點(diǎn)的分布情況較為平均地劃分子區(qū)域,同時(shí)在每個子區(qū)域中按照從左到右的節(jié)點(diǎn)順序構(gòu)建子區(qū)域內(nèi)的柵欄,并依照貪婪算法沿豎直方向完成各子區(qū)域間柵欄的拼接。仿真結(jié)果證明同等條件下,FCOIS算法可以用更少的節(jié)點(diǎn),更低的平均能耗、總能耗與通信開銷構(gòu)建柵欄,且一定程度上兼顧了各節(jié)點(diǎn)之間能耗的均衡,降低了節(jié)點(diǎn)個體出現(xiàn)較大能耗的可能性,間接提高了柵欄的工作壽命。相較PMNSB算法與strong-greedy算法而言,FCOIS算法更好地兼顧了各項(xiàng)指標(biāo)的優(yōu)化,同時(shí)也為全向柵欄的優(yōu)化問題提供了進(jìn)一步的選擇方向與可能性。

三維柵欄模型是更應(yīng)用廣泛的感知模型,如何高效地構(gòu)建三維柵欄是下一步要研究的內(nèi)容。

[1] 羅卿,林亞平,王雷,等. 傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的柵欄覆蓋控制研究[J]. 電子與信息學(xué)報(bào),2012,34(4):825-831.

[2] Santosh Kumar,Ten-Hwang Lai,Anish Arora. Barrier Coverage with Wireless Sensors[C]//Proc of the 11th Annual International Conference on Mobile Computing and Networking,2005:284-298.

[3] Wang Wei,Vikram Srinivasan,Kee-Chaing Chua,et al. Energy-Efficient Coverage for Target Detection in Wireless Sensor Networks[C]//Proc of the 6th International Conference on Information Processing in Sensor Networks. Boston:ACM Press,2007:313-322.

[4] 王林,劉文遠(yuǎn),王琳,等. 基于有向傳感器網(wǎng)絡(luò)的強(qiáng)柵欄覆蓋優(yōu)化策略[J]. 小型微型計(jì)算機(jī)系統(tǒng),2014,35(4):740-745.

[5] 舒堅(jiān),余坤,劉琳嵐,等. 無線傳感器網(wǎng)絡(luò)中基于移動模型的柵欄覆蓋研究[J]. 計(jì)算機(jī)研究與發(fā)展,2011,48(9):141-144.

[6] Wang Zhibo,Liao Jilong,Cao Qing,et al. Achievingk-Barrier Coverage in Hybrid Directional Sensor Networks[J]. IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[7] 陳杰,杜慶偉,李曉禹,等. 概率模型下異構(gòu)傳感器網(wǎng)絡(luò)部署算法的研究[J]. 小型微型計(jì)算機(jī)系統(tǒng),2012,33(1):049-053.

[8] 胡照鵬,張長森. 基于矩形分區(qū)覆蓋的節(jié)點(diǎn)確定部署策略[J]. 傳感技術(shù)學(xué)報(bào),2013,26(3):411-413.

[9] Xu Biaofei,Zhu Yuqing,Donghyun Kim,et al. Strengthening Barrier-Coverage of Static Sensor Network with Mobile Sensor Nodes[J]. Wireless Networks,2015,8491:368-377.

[10] 王超,范興剛,王恒,等. 一種高效強(qiáng)K—柵欄覆蓋構(gòu)建算法[J]. 傳感技術(shù)學(xué)報(bào),2015,28(2):1-8.

[11] Anwar Saipulla,Cedric Westphal,Liu Benyuan,et al. Barrier Coverage with Line-Based Deployed Mobile Sensors[J]. Ad Hoc Networks,2013,11(4):1381-1391.

[12] Habib Mostafaei,Mohammad Reza Meybodi. An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2014. 77(3):2099-2115.

[13] Nowsheen Nusrat,Karmakar Gour,Kamruzzaman Joarder. A Path Reliability-Aware Data Delivery Protocolfor Underwater Acoustic Sensor Networks[J]. Journal of Network and Computer Applications,2016,75:385-397.

[14] Guo Ling,Li Deying,Zhu Yuqing,et al. Enhancing Barrier Coverage with Beta Quality of Monitoringin Wireless Camera Sensor Networks[J]. Ad Hoc Networks,2016,51:62-79.

[15] Chen Jiaoyan,Wang Bang,Liu Wenyu. Constructing Perimeter Barrier Coverage with Bistatic Radar Sensors[J]. Journal of Network and Computer Applications,2015,57:129-141.

任勇默(1994-),男,碩士研究生,主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò),renyongmo@126.com;

牛玉剛(1964-),男,教授,博士生導(dǎo)師,主要研究領(lǐng)域?yàn)殡S機(jī)系統(tǒng)、智能電網(wǎng)、無線傳感器網(wǎng)絡(luò),acniuyg@ecust.edu.cn;

賈廷綱(1973-),男,博士,教授級高工,主要研究領(lǐng)域?yàn)楣I(yè)自動化。

APartitionedAlgorithmforConstructingOmnidirectionalSensorFenceCover*

RENYongmo1,NIUYugang1*,JIATinggang2

(1.Key Lab of Advanced Control and Optimization for Chemical Process of Ministry of Education,East China University of Science and Technology,Shanghai 200237,China;2.Automation Group of Shanghai Electric,Shanghai 200070,China)

Sensor coverage is one of the hot topics in sensor network coverage control. We propose a partitioned omnidirectional sensor fence construction algorithm(FCOIS). In the algorithm,the nodes adopt the omnidirectional sensor-aware model,and the sub-regions are divided according to the initial distribution state of the nodes so that the number of nodes in each sub-region is equal. The fence formation interval is determined by the distribution of nodes in each sub-region. In each sub-region,the fence is constructed according to the order from left to right. When the fence of each sub-area is built,the greedy algorithm is used to fill the gap of the fence between adjacent sub-regions. The simulation results show that the algorithm can build the fence with lower total energy consumption and average energy consumption,which can save the number of nodes and the communication cost.

omnidirectional sensor;fence coverage;FCOIS;sub-region;communication cost

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61273073)

2017-03-07修改日期:2017-05-02

TP273

:A

:1004-1699(2017)09-1381-07

10.3969/j.issn.1004-1699.2017.09.014