一種感知概率模型下的有向傳感器柵欄覆蓋增強算法

任勇默,牛玉剛

(華東理工大學 化工過程先進控制和優(yōu)化技術(shù)教育部重點實驗室,上海 200237)

1 引 言

有向傳感器,如紅外傳感器、聲吶傳感器,在諸多領(lǐng)域被廣泛應(yīng)用,如可將傳感器節(jié)點部署在森林區(qū)域及時感知并告知是否有人員經(jīng)過附近,以及在水下布設(shè)聲吶傳感器節(jié)點來監(jiān)視敵方的潛艇運動狀態(tài)等.在上述應(yīng)用中,有向傳感器節(jié)點在部署完畢后,能夠?qū)ΡO(jiān)控區(qū)域的移動目標進行檢測,這種感知目標的模式被稱為柵欄覆蓋.如何利用有向傳感器節(jié)點的移動、轉(zhuǎn)動能力實現(xiàn)k-柵欄覆蓋是有向傳感網(wǎng)絡(luò)一個研究熱點[1].

2 相關(guān)工作

Kumar[2]定義了感知效果與穿越路徑無關(guān)的柵欄為強柵欄,而僅能確保感知垂直柵欄方向穿越目標的柵欄為弱柵欄.文獻[3]指出傳感器節(jié)點在探測目標時,若距離較近,理想狀態(tài)下可確保感知目標,距離稍遠時感知目標的能力(幾率)與距離的高次方呈反比;文獻[4]則給出了傳感器節(jié)點部署的臨界密度,在部署密度大于臨界密度時,確保能感知目標,但臨界密度的要求過高,超出了大多數(shù)實際情況下的密度上限;文獻[5]通過相鄰節(jié)點間組合構(gòu)造虛擬節(jié)點,以虛擬節(jié)點的組合組成柵欄;文獻[6]研究了狹窄區(qū)域內(nèi),節(jié)點密度足夠大的情況下,僅通過轉(zhuǎn)動有向節(jié)點調(diào)整其感知范圍,完成強柵欄構(gòu)建;文獻[7]提出了一種在高密度投撒條件下,僅靠旋轉(zhuǎn)有向傳感器節(jié)點完成小區(qū)域柵欄覆蓋的方法,但柵欄在小區(qū)域間拼接時會多消耗一部分節(jié)點;文獻[8]研究了混合有向網(wǎng)絡(luò)的柵欄覆蓋,根據(jù)網(wǎng)絡(luò)拓撲構(gòu)建權(quán)重柵欄圖WBG,再運用頂點不相交的路徑算法構(gòu)造K-柵欄,但密度偏低時節(jié)點有可能不夠形成柵欄;文獻[9]研究了在全向傳感器節(jié)點間感知能力有所差異的情況下,配置相應(yīng)的權(quán)重,完成對特定目標的覆蓋以及對障礙物的規(guī)避;Guvensan基于移動能耗和轉(zhuǎn)動能耗,研究了有向網(wǎng)絡(luò)的覆蓋增強[10].文獻[11]提出了在鏈路可靠前提下,能夠節(jié)省節(jié)點通信開銷及增強網(wǎng)絡(luò)壽命的策略.文獻[12]提出了如何在二維和三維環(huán)境下用最少節(jié)點構(gòu)建k條不相交的柵欄,但不能保證節(jié)點最低的能耗與通信開銷.文獻[13]研究了雷達傳感器以總移動距離最小為目標實施區(qū)域覆蓋,但該方法不適用于需要轉(zhuǎn)動的有向傳感器模型.

本文研究如何在低密度的節(jié)點部署環(huán)境下,完成符合最低感知概率要求的概率柵欄覆蓋,提出了一種基于相鄰節(jié)點選取的有向概率柵欄構(gòu)建算法(Fence coverage of directional sensor based on probability-aware distributed,FDS-AD).在形成柵欄的過程中,先完成邊界覆蓋,再依次完成區(qū)域覆蓋,最終再完成另一側(cè)邊界覆蓋.

3 相關(guān)模型與定義

有向傳感器模型,與全向傳感器模型不同,它的感知方向不是360°全方位的,而是有一個特點的夾角視野范圍,超過了這個夾角的視野范圍,即使目標在感知距離之內(nèi),也無法被其感知到,例如攝像機、野外作業(yè)的紅外掃描器等.為了簡化對象,文中所使用的有向傳感器模型用五元組表示(如圖1).

其中,α為有向傳感器節(jié)點的感知角度;β為節(jié)點感知范圍的對稱軸與正方向的夾角,代表節(jié)點的感知方向;rs表示節(jié)點能100%感知目標的最大極限距離;ru表示節(jié)點能以一定概率感知目標的最大極限距離,P(x,y)表示該節(jié)點的坐標位置.當感知距離超過rs時,節(jié)點能感知目標的概率隨距離的a次方成反比[3]:

(1)

(一般情況下,指數(shù)a=2～5,在這里取a=2,rs=10,ru=20)

圖1 有向傳感器感知模型Fig.1 Model of directional sensor

本文對所研究的柵欄覆蓋問題做如下假設(shè):

①在監(jiān)控區(qū)域內(nèi),所有傳感器節(jié)點的感知角度、感知目標能力均相同,節(jié)點的初始橫、縱坐標以及感知角度均服從隨機分布.

②所有節(jié)點的單位轉(zhuǎn)動能耗與單位移動能耗均相同.

③所有節(jié)點在監(jiān)控區(qū)域內(nèi),輸出的信號強度均相同.

④所有節(jié)點均是無故障的.

定義1.節(jié)點的調(diào)度能耗:節(jié)點的移動能耗與轉(zhuǎn)動能耗之和,其中移動能耗由它所移動至預(yù)備位置的距離直接決定,轉(zhuǎn)動能耗由它轉(zhuǎn)動的角度直接決定.

定義2.柵欄概率閾值:指柵欄準確感知目標概率的最大下限P0.

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

本文研究的問題:在給定投撒密度ρ與概率閾值P0的前提下,如何調(diào)度節(jié)點,使之能以較低的能耗完成柵欄覆蓋,并盡可能地減少節(jié)點的使用數(shù)量,兼顧每個節(jié)點之間能耗的均衡.

4 基于感知概率的有向概率柵欄覆蓋算法(FDS-AD)

在文獻[8]中,Wang提出了strong-optimal算法和strong-greedy算法,在監(jiān)控區(qū)域內(nèi)的節(jié)點拓撲結(jié)構(gòu)得到完全確定時,采用頂點不重復(fù)的K條路徑的圖論算法找到節(jié)點感知范圍已連通的子區(qū)域,然后移動其余節(jié)點沿最優(yōu)路徑填補子區(qū)域之間的空檔,從而拼接成柵欄.需要指出的是,文獻[8]中兩種算法的實施均需要全局拓撲信息,通信開銷較大.文獻[9]提出了EX-VFA算法,在全向節(jié)點感知能力不同的情況下進行權(quán)重匹配,從而完成對特定目標的覆蓋.但EX-VFA算法不適用于有向傳感器模型,因為在有向傳感器模型中,還受到感知角度的制約,僅靠節(jié)點自身的坐標和感知半徑不能完全決定其性能參數(shù).

針對上述問題,本文提出了一種基于感知概率的有向傳感器柵欄覆蓋增強算法(FDS-AD),該算法的主要思想是:在確定概率閾值之后,通過柵欄預(yù)選區(qū)域與基準線的確定,將較密集區(qū)段的節(jié)點沿基準線進行部署,組成概率柵欄.在現(xiàn)實應(yīng)用中,使用多個節(jié)點同時感知同一感知區(qū)間的策略,雖然能夠提高該區(qū)域的感知概率,并降低了對單個節(jié)點的感知半徑要求,但會導(dǎo)致以下問題:

1)形成的概率柵欄對節(jié)點需求數(shù)增加,當先前使用的節(jié)點剩余能量不足時,后備的補充節(jié)點數(shù)目減少;

2)當目標穿越這一局部區(qū)域時,需要多個節(jié)點同時工作才可以滿足概率閾值要求,而多個節(jié)點同時產(chǎn)生信號傳遞,會增加通信開銷與能量消耗;

3)若采取多個節(jié)點同時調(diào)度至某一范圍進行共同感知的策略,會增加算法復(fù)雜度.綜合上述因素,為了提高算法的實用性,FDS-AD算法中,不采取調(diào)度多個節(jié)點聯(lián)合感知同一區(qū)域的調(diào)度策略.在后續(xù)仿真實驗中能夠驗證,當投撒密度較大時,節(jié)點間感知區(qū)域重合的情況增多,概率柵欄中會實際出現(xiàn)一部分聯(lián)合感知的情況,間接提高了局部區(qū)域的實際感知能力.

4.1 算法實現(xiàn)步驟

FDS-AD算法實現(xiàn)步驟如下:

步驟1.確定節(jié)點的臨界感知距離d0.

當給定概率閾值P0時,依照公式(1),可以解出節(jié)點至多能達到的感知距離d0.顯然,當節(jié)點感知距離超過d0時,不能完全確保整條柵欄中所有位置的感知概率都不小于P0.與P0對應(yīng)的感知距離d0即為此時節(jié)點的臨界感知距離.

步驟2.確定柵欄形成區(qū)域.

當節(jié)點投撒完畢后,從縱坐標最大的節(jié)點開始,若對其縱坐標記作yi,則統(tǒng)計以直線y=yi、y=yi-2d0與監(jiān)控區(qū)域圍成的公共部分內(nèi)的節(jié)點數(shù)量,挑選出節(jié)點數(shù)最多的監(jiān)控區(qū)域作為柵欄形成區(qū)域.若出現(xiàn)數(shù)個并列最多的區(qū)域,則挑選出其中節(jié)點縱坐標方差最小的區(qū)間作為柵欄形成區(qū)域.這是因為在同等節(jié)點數(shù)量下,節(jié)點縱坐標方差小意味著形成的柵欄更密集,期望上實際感知能力更強;且可以在最大程度上減少形成下一條柵欄時,區(qū)域與之發(fā)生重疊的部分.

步驟3.確定柵欄基準線.

步驟4.確定柵欄首節(jié)點.

圖2 首節(jié)點調(diào)度方式Fig.2 Movement of the first node

步驟5.確定第二個節(jié)點.

當首節(jié)點調(diào)動完成后,以其為圓心,臨界感知距離d0為半徑開展搜索,搜索距首節(jié)點最近的節(jié)點作為柵欄第二個節(jié)點;如果未搜索到,則之后的每一次搜索將搜索半徑再擴大d0,直至搜索到合適的節(jié)點.在密度不至于過低的情況下,采用上述搜索方式,一般一至兩輪即可結(jié)束搜索,明顯降低了搜索過程中的通信開銷.第二個節(jié)點的預(yù)備位置即為首節(jié)點的位置.然后按最少的轉(zhuǎn)動角度轉(zhuǎn)動第二個節(jié)點,使其感知范圍恰能覆蓋住其正右方d0處的點(如果已經(jīng)覆蓋住則不轉(zhuǎn)動),即確保其完成在基準線上d0長度的覆蓋.具體調(diào)度方式如圖3所示.

步驟6.后續(xù)節(jié)點的調(diào)度.

在第i(i≥2)個節(jié)點調(diào)度完畢后,繼續(xù)以其為圓心,感知半徑逐次增加d0的方式搜索其周圍的節(jié)點,并判斷其右側(cè)是否存在與之橫坐標差值不大于d0,且位于柵欄形成區(qū)域內(nèi)的節(jié)點.如有,在符合條件的節(jié)點中,挑選出橫坐標最大的節(jié)點作為第i+1個節(jié)點,將其沿垂直基準線方向移動至基準線上,轉(zhuǎn)動方向角方式同步驟5,如圖4(c)圖所示;如沒有,則選出與第i(i≥2)個節(jié)點距離最近的節(jié)點作為第i+1個節(jié)點,按最短距離移動至第i(i≥2)個節(jié)點正右方d0處,轉(zhuǎn)動方向角方式同步驟5,如圖4(d)圖所示.

圖3 第二個節(jié)點調(diào)度方式Fig.3 Movement of the second node

步驟7.形成第一條柵欄.

在第i+1個節(jié)點調(diào)度完畢后,判斷其與監(jiān)控區(qū)域右邊界是否存在交點:若是,則第一條柵欄形成完畢;若否,則重復(fù)步驟6的操作.

圖4 后續(xù)節(jié)點調(diào)度方式Fig.4 Movement of the subsequent nodes

步驟8.形成剩余K-1條柵欄.

若柵欄數(shù)K>1,則已參與形成柵欄的節(jié)點不再次參與新的調(diào)度,剩余節(jié)點依照步驟2至步驟7的操作,形成第2條柵欄.同理,繼續(xù)形成第3條,第4條…直至第K條柵欄形成完畢.當?shù)贙條柵欄形成完畢后,算法結(jié)束.

FDS-AD算法所涉及參數(shù)見表1,算法偽代碼見下頁表2.

表1 參數(shù)說明
Table 1 Parameter description

參 數(shù)參數(shù)說明L區(qū)域長度W區(qū)域?qū)挾圈羵鞲衅鞴?jié)點感知角度J1傳感器節(jié)點移動單位能耗(J/m)J2傳感器節(jié)點轉(zhuǎn)動角度能耗(J/π)ρ節(jié)點部署密度P0概率閾值d0節(jié)點的臨界感知距離K柵欄數(shù)

4.2 算法的理論分析

定理1.柵欄預(yù)選區(qū)域得到確定后,采取步驟3中基準線的選擇方式,可以使預(yù)選區(qū)域內(nèi)的每個節(jié)點,在垂直方向上期望的運動距離最小.

證明:要使節(jié)點在垂直方向上期望運動距離最小,在每個節(jié)點權(quán)重相同的情況下,等價于預(yù)選區(qū)域內(nèi)的每個節(jié)點,與基準線之間垂直距離的殘差平方和最小.

對y求偏導(dǎo)后得:

(2)

表2 FDS-AD算法偽代碼
Table 2 FDS-AD algorithm pseudocode

01：DividingwholeareaintoW/2d0subareainverticaldirection；02：For i=1：n03：Thesubareawithmaximumnodesetsisselectingas1?barriersubarea；04：If therearemorethanonesubarea05：Selecttheonewiththesmallestvarienceinordinate；06：Determinethebaseliney= y，thenN1isleastxcoordinateinthisnodesets；07：If x1≤d008：x1=x1，y1= y09：Elsex1=d0，y1= y10：RotatingN1withminimumenergyconsumptionaboutmoveandrotate；11：End12：(x1，y1)isalsothefinallocationofthesecondnode，thenpressatleasttheangleofrotation；13：Whiletherightboundaryofbarrierislessthanofarea14：Ifnocrosspointbelongto(xn，xn+d0)，( y-d0， y+d0)15：RotatingN1withminimumenergycomsumptionuntilthereisapointat(xn+d0， y)16：Elseif existingthepointbelongto(xn，xn+d0)，( y-d0， y+d0)17：Findthelargestabscissanode，moveitto(xn+1， y)，withmini?mumenergyconsumptionaboutmoveandrotate；18：End19：Deletetheusednodes；20：End

證明:

∵單個節(jié)點對柵欄所增加長度的范圍為(0,d0),且節(jié)點的橫坐標在x軸上服從隨機分布

∴設(shè)m個節(jié)點中,挑選出的節(jié)點對柵欄所增加的長度為隨機變量X

則X不大于t的概率等價于這m個節(jié)點中,挑選任意一個節(jié)點,對柵欄所增加的長度都不能大于t的概率:

(3)

因為,概率密度函數(shù)為:

社會經(jīng)濟的蓬勃發(fā)展和分工的不斷細化，對專業(yè)技術(shù)人才的需求越來越大，部分中職學校為了提高就業(yè)率，提升學校影響力，偏重于學生專業(yè)技能培訓，對德育重視程度不夠。同時，在中職德育中，對傳統(tǒng)文化教育重視不夠，主要表現(xiàn)在：中職學校對傳統(tǒng)文化教育投入不足，傳統(tǒng)文化教育骨干教師嚴重匱乏，極少有中職學校開設(shè)專門的傳統(tǒng)文化教育課程。

(4)

在柵欄的形成過程中,由于有部分節(jié)點在調(diào)度完畢后,落在了前一節(jié)點的感知區(qū)域內(nèi)部,例如圖4(c)圖所示的情況.依照公式(1)所示的概率感知模型,可以發(fā)現(xiàn),這導(dǎo)致在柵欄中,有相當一部分感知能力相對薄弱的區(qū)域,實際感知能力超過了概率閾值的臨界要求,使得柵欄整體實際的目標捕獲能力,在給定的概率閾值P0下有所提升.

在時間復(fù)雜度方面,依照時間復(fù)雜度定義,考量其運算時間的上界:在最壞情況下,每一次的節(jié)點搜索均是全局搜索,監(jiān)控區(qū)域內(nèi)的全部n個節(jié)點都參與形成K條柵欄.那么在這種情況下,算法的整體運算次數(shù)為:先在全部n個節(jié)點中挑出首個節(jié)點,再全局搜索,從剩余n-1個節(jié)點中挑選出第2個節(jié)點,從剩余n-2個節(jié)點中挑選出第3個節(jié)點…以此類推,根據(jù)數(shù)學歸納法可得,時間復(fù)雜度為:O(n2).

5 仿真實驗

下面通過實驗檢驗本文所提出的FDS-AD算法的性能,并與文獻[8]提出的strong-greedy算法和strong-optimal算法進行對比分析.

在實驗中,為了盡可能抵消隨機誤差的干擾,每組實驗數(shù)據(jù)采用重復(fù)500次獨立實驗取平均值的方法獲得.參考文獻[10]中的實驗數(shù)據(jù),每個傳感器節(jié)點,每移動1個單位長度消耗3.6J的能量,每轉(zhuǎn)動180°消耗1.8J的能量.在后續(xù)的仿真實驗中,如果沒有特別指明特定參數(shù)的數(shù)值,默認的參數(shù)值如表3所示.

表3 默認參數(shù)值
Table 3 Default parameters for the experiment

參 數(shù)取 值L300mW200mαπ/3J13．6J/mJ21．8J/πρ0．006P080%d011．18mK2

在默認參數(shù)下,令初始投撒結(jié)果相同,初始情況的節(jié)點投撒狀態(tài)如下頁圖5所示.在圖5初始狀態(tài)下,分別使用FDS-AD算法和strong-greedy算法構(gòu)建柵欄,如下頁圖6、圖7所示,能將矩形監(jiān)控區(qū)域進行橫向分割的連通節(jié)點的集合即為生成的兩條柵欄.

圖5 節(jié)點初始狀態(tài)Fig.5 Initial form of the node

圖6 FDS-AD算法Fig.6 FDS-AD algorithm

圖7 Strong-greedy算法Fig.7 Strong-greedy algorithm

5.1 投撒密度的影響

由于strong-greedy算法、strong-optimal算法需要在較高投撒密度下,其內(nèi)部的連通區(qū)域才能更好地發(fā)揮作用.因此,為了兼顧strong-greedy算法、strong-optimal算法的應(yīng)用要求,使對比結(jié)果更有意義,實驗中以0.004的投撒密度起始,逐次將投撒密度遞增0.001,直至0.008截止,其余實驗參數(shù)值均與表2所示的默認參數(shù)值一致.仿真實驗結(jié)果如圖8-圖10所示.

圖8 投撒密度 VS 平均能耗Fig.8 Distribution density VS average energy consumption

圖9 投撒密度 VS 柵欄使用節(jié)點數(shù)Fig.9 Distribution density VS the number of nodes used by the fence

圖10 投撒密度 VS 能耗標準差Fig.10 Distribution density VS standard deviation of energy consumption

從圖8中可以看到,當投撒密度增加時,三種算法的平均能耗均明顯下降.當投撒密度為0.004時,FDS-AD算法的平均能耗約為strong-greedy算法和strong-optimal算法的50%;隨著密度增至0.008,FDS-AD算法的平均能耗相對于另兩種算法的平均能耗,約降至strong-greedy算法和strong-optimal算法的30%.這說明在FDS-AD算法中投撒區(qū)域的確定和基準線的選取,比strong-greedy算法和strong-optimal算法更有效地利用了節(jié)點連通的區(qū)域.而對于strong-greedy算法和strong-optimal算法來說,雖然事先尋找到了若干個節(jié)點連通區(qū)域,但連通區(qū)域間的空隙通常較大,使得其余節(jié)點需要移動更多的距離來填補空隙,且連通區(qū)域?qū)艡诓糠止?jié)點的優(yōu)化程度極大程度上受到隨機性干擾,導(dǎo)致其平均能耗始終高于FDS-AD算法.

從圖9中可以發(fā)現(xiàn),當投撒密度增大時,FDS-AD算法需要的節(jié)點數(shù)始終明顯少于strong-greedy算法和strong-optimal算法.對于strong-greedy算法和strong-optimal算法來說,投撒密度處于0.004-0.007時,柵欄通常需要更多的連通塊進行拼接,導(dǎo)致柵欄使用的節(jié)點數(shù)越來越多;而當密度處于0.007-0.008時,連通區(qū)域已接近飽和,使得柵欄使用的節(jié)點數(shù)增長受到了抑制.相應(yīng)地,對于FDS-AD算法來說,當密度處于0.004-0.006時,預(yù)選區(qū)域內(nèi)節(jié)點增多,但稠密程度有限,使得柵欄使用的節(jié)點數(shù)增長較為穩(wěn)定;當密度處于0.006-0.008時,由于預(yù)選區(qū)域內(nèi)節(jié)點增多的同時,其分布變得更稠密,進一步地導(dǎo)致更多節(jié)點采取垂直移動至基準線的方式完成調(diào)度.因此在密度處于0.006-0.008時,FDS-AD算法使用的節(jié)點數(shù)目開始受到放大作用的影響,導(dǎo)致其增長率發(fā)生了明顯的突變,不難推測:當密度從0.008繼續(xù)增長時,會導(dǎo)致柵欄使用節(jié)點數(shù)增多的同時,其斜率仍會明顯增大.

從圖10中可以看出,FDS-AD算法的能耗標準差始終低于strong-greedy算法和strong-optimal算法,且最大時也僅為strong-greedy算法和strong-optimal算法的33%.在strong-greedy算法和strong-optimal算法中,當密度為0.004-0.006時,隨著密度的增大,期望的連通區(qū)域段個數(shù)也隨之增多,但這也導(dǎo)致更多的節(jié)點參與填補區(qū)域間的空檔,拉大了節(jié)點間能耗的差距,最終使能耗標準差隨之增大;當密度為0.006-0.008時,連通區(qū)域段個數(shù)仍在增多,但同時地,需要填補區(qū)域間空檔的節(jié)點明顯減少,這使得節(jié)點間能耗的差距得到明顯縮小,最終使能耗標準差在此時隨密度增大而減少.在FDS-AD算法中,密度為0.004-0.006時,柵欄基準線周圍節(jié)點數(shù)量增多,每個節(jié)點期望移動的距離較為接近,幾乎沒有能耗過低或過高的節(jié)點,而轉(zhuǎn)動角度在期望上又相同,導(dǎo)致能耗標準差一定程度上減少;當密度為0.006-0.008時,由于柵欄基準線周圍節(jié)點分布變得更稠密,每個節(jié)點期望上移動距離的減少已接近極限,能耗標準差在此時幾乎完全由系統(tǒng)誤差決定,幾乎不再降低.

5.2 柵欄實際的感知能力

從圖5-圖7中可以明顯看出,有相當部分的節(jié)點感知區(qū)域存在重合.在節(jié)點實際的通信過程中,如果有若干個節(jié)點感知區(qū)域之間有公共部分,則這若干個節(jié)點之間在該公共部分的感知能力存在一定的相關(guān)性,并非完全獨立.因此,為了相對準確地評估重疊區(qū)域下節(jié)點的感知能力,進行如下規(guī)定:當一個點位于n個傳感器節(jié)點感知區(qū)域的公共部分時,那么這n個節(jié)點在該點處的聯(lián)合感知概率表示為:

P=max{P1,P2,…,Pn}

(5)

由于當概率閾值P0變化時,根據(jù)公式(1),臨界感知距離d0也隨之發(fā)生變化.因此,為了盡可能提高對柵欄實際感知能力的測量精度,采取如下仿真實驗方式:在表2參數(shù)條件下生成1條柵欄,均勻地在柵欄中感知概率小于1的區(qū)域內(nèi)投撒106個坐標點,而后依照公式(1)與公式(5)計算柵欄中對這106個坐標點的感知概率,再取平均值作為柵欄實際感知概率.同時,為了規(guī)避隨機誤差的干擾,這樣的獨立實驗要重復(fù)500次,取其平均值作為最后的測量值.仿真實驗結(jié)果如圖11所示.

圖11 概率閾值 VS 柵欄實際感知概率Fig.11 Probability threshold VS fence actual detection probability

顯然地,從圖11中可以看出,當概率閾值相同時,FDS-AD算法相比strong-greedy算法和strong-optimal算法,有效提高了柵欄實際感知目標的能力.

6 結(jié)束語

本文基于概率感知模型,提出了FDS-AD算法.該算法在概率閾值給定時,按照從左邊界至右邊界的順序,將節(jié)點依次調(diào)度至基準線上.仿真結(jié)果證明在同等條件下,FDS-AD算法能在節(jié)省能耗的同時,降低了節(jié)點的使用量,大幅提高了柵欄的實際感知能力(概率),并兼顧節(jié)點間能耗的均衡,提高了柵欄的工作壽命.在三維環(huán)境下,如何進行基于感知概率的空間覆蓋,是下一步要研究的內(nèi)容.

[1] Ren Yan,Zhang Si-dong,Zhang Hong-ke.Theories and algorithms of coverage control for wireless sensor networks [J].Journal of Software,2006,17(3):422-433.

[2] Santosh Kumar,Ten-Hwang Lai,Anish Arora.Barrier coverage with wireless sensors [C].In 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].In Proc.of the 6th International Conference on Information Processing in Sensor Networks,Boston:ACM Press,2007:313-322.

[4] Liu Ben-yuan,Don Towsley.A study of the coverage of large-scale sensor networks [C].In Proc.of the 1st IEEE International Conference on Mobile Ad-Hoc and Sensor Systems,2004:475-483.

[5] Yang Guan-qun,Qiao Da-ji.Barrier information coverage with wireless sensors [C].In Proc.of the 28th IEEE International Conference on Computer Communications,Rio de Janeiro,2009:918-926.

[6] Zhang Li,Tang Jian,Zhang Wei-yi.Strong barrier coverage with directional sensors [C].In Proc IEEE GlobeCom,Honolulu,HI,USA,2009:1-6.

[7] Wang Lin,Liu Wen-yuan,Wang Lin,et al.Optimal strategies towards strong barrier coverage based on directional sensor networks[J].Journal of Chinese Computer Systems,2014,35(4):740-745.

[8] Wang Zhi-bo,Liao Ji-long,Cao Qing,et al.Achieving k-barrier coverage in hybrid directional sensor networks [J].IEEE Transactions on Mobile Computing,2014,13(7):1443-1455.

[9] Chen Jie,Du Qing-wei,Li Xiao-yu,et al.Research on the deployment algorithm of heterogeneous sensor networks based on probability model [J].Journal of Chinese Computer Systems,2012,33(1):49-53.

[10] Amac Guvensan,Gokhan Yavuz.Hybrid movement strategy in self-orienting directional sensor networks [J].Ad Hoc Networks,2013,11(3):1075-1090.

[11] Nowsheen Nusrat,Karmakar Gour,Kamruzzaman Joarder.A path reliability-aware data delivery protocol for underwater acoustic sensor networks[J].Journal of Network and Computer Applications,2016,75(11):385-397.

[12] Guo Ling,Li De-ying,Zhu Yu-qing,et al.Enhancing barrier coverage with beta quality of monitoringin wireless camera sensor networks[J].Ad Hoc Networks,2016,51(11):62-79.

[13] Chen Jiao-yan,Wang Bang,Liu Wen-yu.Constructing perimeter barrier coverage with bistatic radar sensors [J].Journal of Network and Computer Applications,2015,57(11):129-141.

附中文參考文獻：

[1] 任 彥,張思東,張宏科.無線傳感器網(wǎng)絡(luò)中覆蓋控制理論與算法[J].軟件學報,2006,17(3):422-433.

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

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