移動傳感器對關鍵點的監測問題研究

朱齊丹，吳葉斌，姚姍姍，陸軍

(哈爾濱工程大學 自動化學院，黑龍江 哈爾濱 150001)

無線傳感器網絡具有廣泛的應用范圍，其中包括偵查，環境監測，生態系統監測，森林火災的響應，醫療監護，等等［1-8］.在傳統的無線傳感器網絡模型中，靜態傳感器節點以極高的密度隨機分布在工作空間中，使該傳感器網絡覆蓋整個工作空間并且使傳感器網絡保持連接.但是，這種方法有幾個缺點: 1)由于傳感器的位置是固定的，所以沒有被覆蓋的區域永遠無法被監測;2)在監測網絡中，如果對手獲得傳感器的位置信息，它可以利用這些信息避開傳感器;3)在傳感器密度較低的區域，一旦有傳感器發生故障可能導致整個傳感器網絡無法連接.最后，靜態傳感器網絡無法適應動態環境下可能出現的新的情況，因而妨礙正常的感知和通訊任務.

移動傳感器能夠解決靜態傳感器所面臨的大多數問題，并且已經成功應用于大型工作空間［5］.由于這種機動性的存在，從而可以用少量的傳感器覆蓋所有敏感區域.隨機運動的策略可以使對手難以確保不被傳感器發現.由于可以運動，當他們來到對方的傳輸范圍時，傳感器之間可以相互交換數據，也可以給中央節點(接收器)發送信息.這就保持了網絡的連接.雖然移動傳感器在一段時間內能夠覆蓋更多的區域，但是可能出現多個機器人同時探測同一區域的情況.因此，沒有適當的運動規劃，移動傳感器網絡不能有效完成對整個工作空間的覆蓋，使得該傳感器網絡錯過了發現未被覆蓋區域的事件，從而使探測效率大大降低.

文獻［9-12］研究了靜態傳感器的覆蓋問題.文獻［13］和文獻［14］研究了動態傳感器的運動規劃問題，但是沒有研究動態傳感器的覆蓋效率與動態傳感器的速度之間的關系.文獻［10］是最早的一篇研究無線傳感器網絡的覆蓋問題的論文，用圖論的方法研究了無線傳感器網絡的覆蓋問題.文獻［15］采用柵格法研究了無線傳感器網絡完成對工作區域覆蓋和保持通訊的充分必要條件.文獻［16-18］研究了無線傳感器網絡的能源效率問題.

針對靜態傳感器無法覆蓋整個工作空間，易被對手利用和無法適應新情況等缺點，提出用移動傳感器對事件進行監測，彌補了靜態傳感器的不足;為了提高監測效率，提出了移動傳感器的運動規劃方法.

1 移動傳感器對關鍵點的監測問題研究

1.1 問題描述

隨機事件在工作空間的某一固定點出現和消失，這一固定點稱為關鍵點.如果移動傳感器在事件消失之前發現事件，稱隨機事件被監測到，如果隨機事件在移動傳感器到達之前消失，那么稱隨機事件丟失.在關鍵點處事件的出現和消失的時間分布是已知的.本文的目的是給出移動傳感器的運動規劃，用于滿足事件監測的指標.在本文中，假設關鍵點的集合是有限離散集.

本文提出的方法應用范圍極為廣泛，如監視、檢測、水下網絡傳感器和供應鏈管理.

本文假設以下3點:

1)每個關鍵點只被一個移動傳感器監測，如果每個關鍵點可以被多個傳感器監測，會使問題的復雜度大大增加.

2)為了使每個傳感器需要與中央控制器能夠通信，傳感器的路徑從中央控制器所在地開始，最后還要回到起點，把收集到的數據發送給中央控制器.

3)移動傳感器的速度是相同的.

1.2 關鍵點事件監測問題的性能分析

本節對移動傳感器網絡覆蓋效率的性能進行了分析.假設有a個關鍵點，分布在長度為D的閉合曲線C上.傳感器沿著C運動，傳感器的探測半徑為r，相鄰關鍵點之間的距離大于2r，當傳感器與關鍵點的距離小于r時才能對此處的事件進行監測.

關鍵點的狀態在0和1之間變化.狀態0代表事件出現，狀態0代表事件消失.狀態0和狀態1的持續時間服從指數分布，它們的均值分別為和本文設λ=μ?i.

假設傳感器以速度v沿著C運動，事件完成一個0→1→0或1→0→1變化稱為一個循環.L代表一個狀態循環的均值:

移動傳感器沿著C運行一周，經過各關鍵點一次.每個關鍵點能被傳感器監測的時間為如果在t時刻，傳感器發現一個關鍵點.那么傳感器將在這段時間內對該關鍵點進行監測.傳感器監測到的事件的數量取決于關鍵點在t時刻的狀態，和在時間段的循環次數.定理1 用C(τ)表示在時間段(t，t+τ)關鍵點的狀態循環次數，那么在這段時間內狀態循環次數的數學期望為

證明:事件的狀態循環是一個更新過程，消失和出現的時間是2個服從指數分布的隨機變量，在時間τ內更新次數的數學期望的拉普拉斯變換為［19］

其中，LF(r)是完成一個更新過程所需時間的拉普拉斯變換.

用T表示完成一次更新過程所需要的時間，則T=T1+T2，T1和 T2服從均值為和的指數分布，則T的概率分布為

因此，T的概率密度為

fT(t)的拉普拉斯變換為

由文獻［3］得E［C(τ)］的拉普拉斯變換為

那么，

因此在時間τ內的更新次數的數學期望為

證畢.

用Si(t)表示在t時刻的狀態，P0和P1分別表示在t時刻Si(t)=0和Si(t)=1的概率，因此

證明:當t時刻Si(t)=1時，移動傳感器監測到的隨機事件的數量為表示移動傳感器經過一個關鍵點2次捕獲到同一事件的概率，則當Si(t)=1時，移動傳感器監測到的隨機事件數量的數學期望為

當t時刻Si(t)=0時，t'表示關鍵點的狀態由0變為1所需要的時間，當t時刻Si(t)=0時，移動傳感器監測到的隨機事件數量的數學期望為

合并(1)、(2)得證.

證畢.

定理3 移動傳感器監測到的事件的比例為

證明:移動傳感器沿著C運行一圈，捕獲到的事件的數學期望記為Nr，Nr的數學期望是移動傳感器在每個關鍵點處捕獲的事件的數學期望之和，即

NT'表示在時間［0，T］隨機事件出現的總數:

當T→∞時，移動傳感器捕獲到的事件的比例為

證畢.

1.3 移動傳感器的運動規劃

假設有k個移動傳感器，本節提出一種運動規劃方法，使得每個關鍵點只被一個移動傳感器監測，并且至少被一個移動傳感器監測，同時使監測效率盡可能大.每個移動傳感器都是從中央控制器所在位置出發，最后回到出發點.這是旅行商問題的一種變形，屬于k-TSP問題為:k個人從城市1出發分頭去訪問n－1個城市，每個城市有且僅有一個人到達，最后都回到城市1.問怎樣安排使得k個人的總訪問路線最短.k-TSP是TSP的一種變形，同樣是NP困難的，因此從理論的角度看，是不可能設計出理想的(多項式時間)能求出最優解的精確算法.本節通過一種啟發式的方法同時建立k條路徑.

令Ri=(vi1，…，vim)為其中的一條子路徑，其中vi1=vim.存在一節點u?Ri，則把u插入到vi和vi+1之間的代價函數為

u插入到子路徑Ri中時，總是把u插入到Ri中的相鄰節點之間，并且使得路徑的總代價最小，記為Ri←(u).總路徑R的代價函數為:c(R)=Fk(v)，Fk(v)為在總路徑R上移動傳感器捕獲到的事件的效率:

算法如下:

1)初始化k個路徑，Rj=(v0，v0)?1≤j≤k.其中v0代表中央控制器的位置，工作空間中的關鍵點所在位置分別用序號(v1，…，vm)表示.

2)對于每一個不在(R1，R2，R3，…，Rk)中的關鍵點vj，1≤j≤a，計算出vj插入到Ri中的代價函數Fk(v)，存在一個vj和Ri，使得當vj被加進Ri時，Fk(v)增加最大.

3)如果由2)得到的結果是Ri和vj，則把vj插入到Ri中，即Ri←(vj).

4)如果(R1，R2，R3，…，Rk)中包含了所有的關鍵點，則算法終止，否則轉到2).

2 仿真實驗與分析

根據以上對移動傳感器的分析和設計，在Visual C++和Matlab下進行仿真實驗，比較了移動傳感器與固定傳感器的監測效率，分析了移動傳感器的數量和速度對捕獲效率的影響.如果有m個固定傳感器分布在工作空間中，a個關鍵點分布在工作空間中，并且m≤a每個傳感器監測一個關鍵點，則監測效率為m/a.如果相同數量的移動傳感器的捕獲效率Fm(v)＞m/a，則使用移動傳感器更加有效.本節在500 m×500 m的環境中進行仿真，取參數r=10 m，a=9，λ=μ=0.01，k分別取1、2、3.如圖1～3所示.圖中的黑點代表中央控制器的位置，圈的圓心代表關鍵點，圓代表隨機事件能被感知的范圍.圖1～3分別為有1個、2個、3個傳感器的運動規劃情況.

圖1 1個移動傳感器的運動規劃Fig.1 The motion planning of one mobile sensor

圖2 2個移動傳感器的運動規劃Fig.2 The motion planning of two mobile sensors

圖3 3個移動傳感器的運動規劃Fig.3 The motion planning of three mobile sensors

圖4 移動傳感器時監測到的隨機事件與移動傳感器速度的關系Fig.4 The relationship between Stochastic event capture and the speed of mobile sensors

圖4中的“+”線代表只有一個移動傳感器時監測到的隨機事件與移動傳感器的速度的關系，“*”線代表有兩個移動傳感器時監測到的隨機事件與移動傳感器的速度的關系，實線代表有3個移動傳感器時監測到的隨機事件與移動傳感器的速度的關系，其他虛線代表固定傳感器的監測效率.從圖形可以看出，隨著速度的增加，移動傳感器監測到的隨機事件的效率也在增加;當速度超過某一值時，移動傳感器的監測效率就會大于固定傳感器的監測效率，隨著移動傳感器數量的增加捕獲效率隨之增加.

3 結束語

本文對移動傳感器的捕獲效率進行了分析，并且提出了一種移動傳感器的運動規劃方法.通過仿真實驗驗證了路徑規劃方法的可行性，并且分析了監測效率與移動傳感器的數量和速度的關系，也比較了移動傳感器和固定傳感器監測性能.結果表明隨著速度的增加移動傳感器監測到的隨機事件的效率也在增加，當速度超過某一值時，移動傳感器的監測效率就會大于固定傳感器的監測效率，隨著移動傳感器數量的增加捕獲效率隨之增加，但是增速越來越緩慢.

［1］KAHN J M，KATZ R H，PISTER K S.Next century challenges:mobile networking for smart dust［C］//Proceedings of 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York，USA，1999: 271-278.

［2］POTTIE G J，KAISER W J.Wireless integrated network sensors［J］.Communications of the ACM，2000，43(5): 51-58.

［3］LEONCINI M，RESTA G，SANTI P.Analysis of a wireless sensor dropping problem in wide-area environmental monitoring［C］//Proceedings of 4th International Symposium on Information Processing in Sensor Networks.Los Angeles，USA，2005:239-245.

［4］STEERE D C，BAPTISTA A，MCNAMEE D.Research challenges in environmental observation and forecasting systems［C］//Proceedings of 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York，USA，2000:292-299.

［5］MAINWARING A，CULLER D，POLASTRE J.Wireless sensor networks for habitat monitoring［C］//Proceedings of 1st ACM International Conference on Wireless Sensor Networks and Applications.New York，USA，2002:88-97.

［6］MEGUERDICHIAN S，KOUSHANFAR F，QU G.Exposure in wireless ad-hoc sensor networks［C］//Proceedings of 7th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York，USA，2001:139-150.

［7］CHEN M X，WANG Y D.An efficient location tracking structure for wireless sensor networks［J］.Computer Communications，2009，32(13):1495-1504.

［8］YANG H，SIKDAR B.A protocol for tracking mobile targets using sensor network［C］//Proceedings of IEEE International Workshop on Sensor Network Protocols and Applications，2003:71-81.

［9］HUANG C F，TSENG Y C.The coverage problem in a wireless sensor network［C］//Proceedings of 2nd ACM International Conference on Wireless Sensor Networks and Applications.New York，USA，2003:115-121.

［10］MEGUERDICHIAN S，KOUSHANFAR F，SRIVASTAVA P M.Coverage problems in wireless ad-hoc sensor networks［C］//Proceedings of 20th Annual IEEE Conference on Computer Communications.New York，USA，2001: 1380-1387.

［11］WANG X，XING G，ZHANG Y.Integrated coverage and connectivity configuration in wirelesssensornetworks［C］//Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York，USA，2003:28-39.

［12］XING G，LU C，PLESS R.Cogrid:an efficient coverage maintenance protocol for distributed sensor networks［C］// Proceedings of 3th International Symposium on Information Processing in Sensor Networks.New York，USA，2004: 414-423.

［13］LATOMBE J C.Robot motion planning［M］.Norwell: Kluwer Academic Publishers，1991:95-97.

［14］LAVALLE S M.Planning algorithms［M］.Cambridge: Cambridge University Press，2006.

［15］SHAKKOTTAI S，SRIKANT R，SHROFF N B.Unreliable sensor grids:Coverage，connectivity and diameter［J］.Ad Hoc Networks，2006，3(6):702-716.

［16］HSIN C F，LIU M.Network coverage using low duty-cycled sensors:random ＆ coordinated sleep algorithms［C］//Proceedings of 4th International Symposium on Information Processing in Sensor Networks.New York，USA，2004:433-442.

［17］KUMAR S，LAI T H，BALOGH J.On k-coverage in a mostly sleeping sensor network［C］//Proceedings of 10th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York，USA，2004:144-158.

［18］TIAN D，GEORGANAS N D.A coverage-preserving node scheduling scheme for large wireless sensor networks［C］// Proceedings of 2nd ACM International Conference on Wireless Sensor Networks and Applications.New York，USA，2002:32-41.

［19］GALLAGER R G.Discrete stochastic processes［M］.Norwell:Kluwer Academic Publishers，1995:251-254.