徐 萍，何加銘，謝志軍，曾興斌

(寧波大學信息科學與工程學院，浙江寧波315211)

0 引言

在構(gòu)建無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)時，覆蓋問題是衡量網(wǎng)絡(luò)的QoS指標之一，可以看作是傳感網(wǎng)絡(luò)在節(jié)點能量、計算處理能力等資源受限的情況下，通過放置節(jié)點和喚醒/休眠節(jié)點等手段，從而獲得更好的QoS。傳感器節(jié)點構(gòu)成的WSNs在無人監(jiān)管的情況下，通過傳感器節(jié)點之間的協(xié)同工作實現(xiàn)監(jiān)測和采集各種環(huán)境或監(jiān)測對象的相關(guān)信息，并將處理后的數(shù)據(jù)傳送給基站。除此之外，WSNs中通常節(jié)點布設(shè)密集，如果讓所有節(jié)點都工作，則會在數(shù)據(jù)收集時存在高度相關(guān)和冗余，甚至在傳送數(shù)據(jù)時發(fā)生沖突。移動目標監(jiān)測是WSNs的重要應用之一［1］。

一種典型的移動目標監(jiān)測的調(diào)度策略是基于分簇策略的跟蹤算法［2，3］。假設(shè)WSNs是由特定或者隨機部署在監(jiān)測區(qū)域內(nèi)的簇首和普通節(jié)點組成，簇首負責接收處理節(jié)點發(fā)來的數(shù)據(jù)，然后轉(zhuǎn)發(fā)給基站;普通節(jié)點負責感知數(shù)據(jù)。然而活躍節(jié)點數(shù)直接影響網(wǎng)絡(luò)能量的消耗。文獻［4］提出基于自適應目標跟蹤算法，利用最優(yōu)選擇機制和動態(tài)分簇方式確定活躍節(jié)點。文獻［5］最大熵原理，先把部署在網(wǎng)絡(luò)中的靜態(tài)節(jié)點分簇，然后根據(jù)監(jiān)測環(huán)境的需要加入移動節(jié)點，從而降低網(wǎng)絡(luò)的不確定性，增加節(jié)點的可選擇性。文獻［6］利用節(jié)點的聯(lián)合概率探測模型，選擇探測概率大的節(jié)點作為任務(wù)節(jié)點。然而當目標在局部做重復運動，或者更為復雜的運動時，目標在局部區(qū)域內(nèi)逗留的時間很長，這樣局部能量就會迅速消耗，最終導致對目標漏檢。

本文根據(jù)以往節(jié)點的調(diào)度記錄和剩余能量、目標軌跡以及回退機制來提高網(wǎng)絡(luò)覆蓋度和監(jiān)測概率，借助貪心算法優(yōu)化網(wǎng)絡(luò)資源分配，使之更好地完成對移動目標的監(jiān)測任務(wù)。在WSNs中，大量節(jié)點隨機分布在目標區(qū)域內(nèi)，受節(jié)點自身條件限制，若所有節(jié)點同時工作，不僅能量消耗過快，而且降低了網(wǎng)絡(luò)的使用壽命。本文研究如何通過模糊移動軌跡［7］策略解決喚醒調(diào)度算法中某些節(jié)點過早死亡和移動物體監(jiān)測過程中盲點問題。主要研究包括:構(gòu)建基于隨機均勻分布節(jié)點模型，提出模糊移動軌跡建立方案，提出一種基于模糊移動軌跡策略的節(jié)點調(diào)度(move trajectory PEAS，M-PEAS)算法。實驗證明:該算法提高了節(jié)點的監(jiān)測概率，降低了能耗。

1 M-PEAS理論基礎(chǔ)

采用輪換“活躍”和“休眠”節(jié)點的覆蓋控制協(xié)議可以有效延長網(wǎng)絡(luò)生存時間，每個周期由一個自調(diào)度階段和一個工作階段組成。在自調(diào)度階段:各節(jié)點首先向傳感半徑內(nèi)鄰居節(jié)點廣播通告消息，其中包括節(jié)點ID和位置。節(jié)點檢查自身傳感任務(wù)是否可由鄰居節(jié)點完成，可替代的節(jié)點返回一條狀態(tài)通告消息，之后進入“休眠狀態(tài)”，需要繼續(xù)工作的節(jié)點執(zhí)行傳感任務(wù)，在判斷節(jié)點是否可以休眠時，如果相鄰節(jié)點同時檢查到自身的傳感任務(wù)可由對方完成并同時進入“休眠狀態(tài)”，就會出現(xiàn)監(jiān)測的“盲點”［8］。

1)監(jiān)測概率

一般由于傳感器節(jié)點的理論或物理特性不同，應用場景對監(jiān)測要求不同，對監(jiān)測性能要求不同。根據(jù)傳感模型得到監(jiān)測概率的分布，不同傳感器的傳感模型有所差異，但感知能力隨距離的增長而降低的這一基本特點是保持不變的。PEAS算法節(jié)點密度公式

其中，λ為節(jié)點的監(jiān)測概率，ts為節(jié)點睡眠周期。傳感器節(jié)點s在q點的感知模型定義如下［9］

其中，dis(s，q)為節(jié)點s與q在二維空間上的歐氏距離，α＞0為感知系數(shù)，k=1，2為距離影響系數(shù)。根據(jù)感應模型，可以得出節(jié)點s對q點的發(fā)現(xiàn)概率p(d)

其中，d=dis(s，q)，r為感知半徑，R 為通信半徑，為保證節(jié)點間正常通信，設(shè)定R＞2r。

2)模糊軌跡

設(shè)移動目標物體從節(jié)點A移動到節(jié)點B的坐標分別為A(x1，y1)，B(x2，y2)，根據(jù)兩節(jié)點之間的歐氏距離和監(jiān)測時間，得出移動目標的速度函數(shù)

方位角函數(shù)

其中，φab為A至B直線方向參考方向。當運動物體從節(jié)點A移至節(jié)點B時，節(jié)點B計算速度估計函數(shù)f(vB)和方位角估計函數(shù)f(Bφ)定義如下

其中，Δv，Δθ為速度和方位角的偏差量。

3)回退機制

節(jié)點在自調(diào)度階段檢查之前執(zhí)行一個回退機制:每個節(jié)點在一個隨機產(chǎn)生的Td時間之后再開始檢查工作。在本文中Td時間根據(jù)物體移動軌跡、速度、節(jié)點間距離決定。此外，回退時間還可以根據(jù)周圍節(jié)點密度而計算，這樣就可以有效地控制網(wǎng)絡(luò)“活躍”節(jié)點的密度，為了進一步避免“盲點”的出現(xiàn)，每個節(jié)點在進入“休眠狀態(tài)”之前還將等待3 s時間來監(jiān)聽鄰居節(jié)點的狀態(tài)更新。

4)模糊移動軌跡的優(yōu)劣評價標準

模糊移動軌跡的優(yōu)劣評價標準:移動目標在運動的情況下，在傳感區(qū)域內(nèi)的時間越長，被監(jiān)測到的概率越大，對于目標在監(jiān)測區(qū)域內(nèi)監(jiān)測量的計算，移動目標在監(jiān)測區(qū)域內(nèi)的責任感知節(jié)點有影響，第一，移動目標在區(qū)間［t1，t2］在二維軌跡上監(jiān)測量［10］為

式(7)表示目標移動過程中責任節(jié)點對其感知數(shù)量，即監(jiān)測量越大越好。模糊軌跡監(jiān)測的長度與節(jié)點監(jiān)測狀態(tài)有關(guān);第二，目標在移動過程中被監(jiān)測的概率越大，漏檢的可能性減少。同時喚醒機制綜合考慮剩余能量，當節(jié)點剩余能量為初始能量的1/3時，節(jié)點自動轉(zhuǎn)換成中繼節(jié)點，只負責節(jié)點信息的傳遞工作，減少因節(jié)點失效而產(chǎn)生的盲點問題。

2 M-PEAS節(jié)點調(diào)度策略

M-PEAS節(jié)點調(diào)度策略是一種基于探測的節(jié)點密度控制協(xié)議PEAS的分布式控制算法，其中，運動物體模糊移動軌跡、速度和方位角函數(shù)推算是此算法的關(guān)鍵。節(jié)點調(diào)度休眠規(guī)則包括2個方面:首先，檢查節(jié)點在各自責任區(qū)是否滿足保證區(qū)域覆蓋;其次，根據(jù)估計值設(shè)定節(jié)點喚醒函數(shù)。

1)模型的分解

運動物體從節(jié)點A運動至節(jié)點C，而B，D，E，F(xiàn)是其鄰居節(jié)點，如圖1所示，各節(jié)點具有相同的屬性，節(jié)點C根據(jù)節(jié)點A獲取物體移動的速度、方位角、距離等信息推算運動物體本輪的軌跡，計算到達自身監(jiān)測區(qū)域概率和時間。由于各節(jié)點具有相同的時鐘，同時物體的運動具有很強的關(guān)聯(lián)性，在短時間內(nèi)其速度和方向不會發(fā)生太大的變化。節(jié)點C根據(jù)節(jié)點A的信息和兩點間的距離，確定速度估計函數(shù)F(v)，方位角函數(shù)φ(θ)，如圖2所示，定義與參考方向x軸方向的夾角為方位角。通過這2個函數(shù)推算物體的運動軌跡y，休眠節(jié)點根據(jù)信息確定到達本區(qū)域的概率，將此信息發(fā)送給鄰居節(jié)點，通過比對接收到的信息分析數(shù)據(jù)。關(guān)聯(lián)度最小的節(jié)點采用休眠方式;若有幾個節(jié)點同時處于方位角之內(nèi)，且監(jiān)測區(qū)域有重疊，根據(jù)節(jié)點的覆蓋范圍和節(jié)點的剩余能量綜合考慮節(jié)點的工作狀態(tài)。通常，設(shè)物體從節(jié)點A運動到節(jié)點B，根據(jù)RSSI技術(shù)獲得兩點的距離，估計速度函數(shù)計算物體到達上限時間令T為PEAS休眠節(jié)點喚醒周期，則，當節(jié)點C收到節(jié)點A的感知信號，經(jīng)過mT時間，節(jié)點C進入節(jié)點監(jiān)聽狀態(tài)，并持續(xù)(m-n)T時間。

圖1 目標物體移動原理圖Fig 1 Mobile principle diagram of the target object

圖2 移動目標方位角示意圖Fig 2 Azimuth diagram of moving target

若多個目標同時進入節(jié)點監(jiān)測區(qū)域，建立分時隙偵聽，避免過多節(jié)點數(shù)據(jù)冗余，減少節(jié)點能量消耗。

2)模糊移動軌跡分析

在傳感區(qū)域S內(nèi)，起始節(jié)點Pt的坐標為(0，0)，已知終點S，節(jié)點A首先監(jiān)測到移動目標O，記錄其到達時間t1，根據(jù)式(5)、式(6)得出速度和方位角函數(shù)。已知鄰居節(jié)點位置信息，鄰居節(jié)點收到B發(fā)送的監(jiān)測信息，計算物體到達本監(jiān)測區(qū)域的時間和概率P(b)=P(d)×(1+p)，其中，p是根據(jù)模糊移動軌跡估算的預測概率［11］。同時將處理后的信息反饋給周邊鄰居節(jié)點，鄰居節(jié)點接收到處理信息后通過比對自身監(jiān)測區(qū)域的概率、剩余能量、目前狀態(tài)，決定自身的狀態(tài)(休眠狀態(tài)、監(jiān)聽狀態(tài)、加強監(jiān)聽狀態(tài))。為防止出現(xiàn)節(jié)點同時進入休眠狀態(tài)而出現(xiàn)的盲點問題，本策略采用節(jié)點回退機制，回退時間0～t，根據(jù)移動目標與節(jié)點本身距離而定，設(shè)定t等于距離，B，C，F(xiàn) 節(jié)點進入覆蓋探測狀態(tài)的時間不同，避免了監(jiān)測重疊區(qū)域出現(xiàn)覆蓋漏洞的現(xiàn)象。

3)算法描述

輸入傳感器節(jié)點集 S={s1，s2，s3，…，sn}，目標監(jiān)測區(qū)域 A，移動物體目標集 L={l1，l2，l3…，lm}，監(jiān)聽節(jié)點集 Q={q1，q2，q3…，ql}，休眠節(jié)點集 W={w1，w2，w3…，wn-l}，輸出實現(xiàn)節(jié)點之間覆蓋監(jiān)測區(qū)域責任節(jié)點集G。

3 節(jié)點監(jiān)測覆蓋性能分析

設(shè)WSNs的節(jié)點隨機均勻分布，節(jié)點密度服從式(1)分布，節(jié)點的感知半徑為r，物體在網(wǎng)絡(luò)內(nèi)的運動路徑長度為L，責任節(jié)點的感知概率為Ps(i)，物體經(jīng)過的責任節(jié)點數(shù)為N=(2rL+πr2)f(ts)，被責任節(jié)點感知的節(jié)點數(shù)目，則漏檢概率為，采用模糊移動軌跡策略，責任節(jié)點i對目標的監(jiān)測感知數(shù):

1)當物體恰好在監(jiān)聽加強狀態(tài)時進入感知區(qū)域，節(jié)點對物體采用加強監(jiān)聽(此時的感知概率記為Pes)。

2)采用軌跡分析進行檢測，設(shè)節(jié)點對物體加強監(jiān)聽的概率為Pe，物體被節(jié)點感知的數(shù)量滿足

由式(8)可知，若Nes＞Ns，即采用模糊移動軌跡策略失真率小于PEAS算法。

4 仿真實驗

為了驗證本算法的正確性和有效性，初始仿真場景和，下限 t2=相關(guān)參數(shù)設(shè)定如下:選用Matlab作為實驗仿真平臺，初始仿真場景與相關(guān)參數(shù)設(shè)定如下:平面100 m×100 m，1 000個節(jié)點隨機分布，r=5 m，R=15 m，λ =1，k=1，節(jié)點初始能量0.5 J，移動目標速度 v=1 m/s。

仿真1:比較同一場景下，M-PEAS，PEAS算法在網(wǎng)絡(luò)運行期間剩余能量變化。

由于M-PEAS算法通過軌跡、節(jié)點剩余能量設(shè)計調(diào)度函數(shù)，節(jié)點能耗更加均衡。從圖3中可以看出:M-PEAS和PEAS算法在網(wǎng)絡(luò)正常運行的不同時間段的剩余能量百分比。節(jié)點能量隨著時間不斷地消耗，當時間為130 s時，PEAS算法能量由于某些節(jié)點持續(xù)工作導致節(jié)點失效，整體能量消耗過大，已經(jīng)小于整體能量的1/3，沒有很好地考慮能耗的均衡性，導致整個網(wǎng)絡(luò)過早處于癱瘓狀態(tài)，造成很大的能量浪費。

仿真2:選取同上的仿真平臺，分別選取節(jié)點數(shù)100，200，300，400，500，600，700，800，900，1 000 等 10 組數(shù)據(jù)進行100次仿真分析比對，其他參數(shù)保持一致。結(jié)果如圖4所示。從中可以看出:在不同節(jié)點數(shù)覆蓋情況下，M-PEAS算法監(jiān)測概率高于PEAS算法，其原因是，WSNs節(jié)點在工作期間會出現(xiàn)一部分失效節(jié)點，隨著節(jié)點工作變化，PEAS算法中的失效節(jié)點遠大于M-PEAS算法，同時，采用軌跡分析策略，責任節(jié)點對物體的監(jiān)測概率加強。所以，在具有相同的節(jié)點數(shù)時，M-PEAS的監(jiān)測概率大于PEAS。

圖4 監(jiān)測概率對比圖Fig 4 Comparison diagram of monitoring probability

5 結(jié)束語

在WSNs中，節(jié)點覆蓋已成為WSNs研究的一個重要分支?？紤]到節(jié)點自身能量有限，目標運動的復雜性和隨機部署的不確定性，在本文中提出一種基于PEAS模糊移動軌跡算法。首先，提出了模糊移動軌跡策略，構(gòu)建軌跡算法，將節(jié)點調(diào)度問題轉(zhuǎn)化成軌跡生成問題;然后，基于模糊移動軌跡建立節(jié)點調(diào)度函數(shù)，仿真實驗表明:此調(diào)度算法能很好解決節(jié)點能耗均衡問題;最后，利用貪婪算法關(guān)聯(lián)其自身剩余能量對策略進行優(yōu)化，證明該算法優(yōu)于PEAS算法，提高了網(wǎng)絡(luò)的監(jiān)測概率，降低了節(jié)點漏檢問題，延長了網(wǎng)絡(luò)生命周期。

［1］Gezici S，Tian Z，Giannakis G，et al.Localization via ultra-wideband radios:A look at positioning aspects for future sensor networks［J］.IEEE Signal Processing Magazine，2005，22(4):70-84.

［2］Chen W P，Hou JC，Liu S.Dynamic clustering for acoustic target tracking in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(3):258-271.

［3］Chuang SC.Survey on target tracking in wireless sensor networks［R］.Beijing:Tsinghua University，2005.

［4］Phuong P，Sesh C.Stability and performance of wireless sensor networks during the tracking of dynamic targets［J］.Lecture Notes in Electrical Engineering，2011，89:349-362.

［5］Kuang X H，F(xiàn)eng R，Shao H H.A lightweight target tracking scheme using wireless sensor networks［J］.Measurement Science and Technology，2008，19:1-7.

［6］Wang X，Ma JJ，Wang S，et al.Distributed energy optimization for target tracking in wireless sensor networks［J］.IEEE Transactions on Mobile Computing，2009，9(1):73-86.

［7］Chen A，Kumar S，Lai TH.Local barrier coverage in wireless sensor networks［J］.IEEE Trans on Mobile Computing，2010，9(4):491-504.

［8］Adlakha S，Srivastava M.Critical density thresholds for coverage in wireless sensor networks［C］∥Proc of IEEE WCNC’2003，New Orleans，La，USA，2003:1615-1620.

［9］Zhang W Z，Li M L，Wu M Y.An algorithm for target traversing based on local voronoi diagram［J］.Journal of Software，2007，18(5):1246-1253.

［10］Saipulla A，Westphal C，Liu B，et al.Barrier caverage of linebased deployed wireless sensor networks［C］∥Proc of the 28th IEEE Conf on Computer Communications，INFOCON 2009，Rio de Janeiro，2009:19-25.

［11］Wang B，Chua K C，Wang W，et al.Worst and best information exposure paths in wireless sensor networks［C］∥International Conference on Mobile Ad Hoc and Sensor Networks，MSN’05，2005:52-62.