移動(dòng)傳感器對(duì)關(guān)鍵點(diǎn)的監(jiān)測(cè)問題研究

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

(哈爾濱工程大學(xué) 自動(dòng)化學(xué)院，黑龍江 哈爾濱 150001)

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

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

文獻(xiàn)［9-12］研究了靜態(tài)傳感器的覆蓋問題.文獻(xiàn)［13］和文獻(xiàn)［14］研究了動(dòng)態(tài)傳感器的運(yùn)動(dòng)規(guī)劃問題，但是沒有研究動(dòng)態(tài)傳感器的覆蓋效率與動(dòng)態(tài)傳感器的速度之間的關(guān)系.文獻(xiàn)［10］是最早的一篇研究無線傳感器網(wǎng)絡(luò)的覆蓋問題的論文，用圖論的方法研究了無線傳感器網(wǎng)絡(luò)的覆蓋問題.文獻(xiàn)［15］采用柵格法研究了無線傳感器網(wǎng)絡(luò)完成對(duì)工作區(qū)域覆蓋和保持通訊的充分必要條件.文獻(xiàn)［16-18］研究了無線傳感器網(wǎng)絡(luò)的能源效率問題.

針對(duì)靜態(tài)傳感器無法覆蓋整個(gè)工作空間，易被對(duì)手利用和無法適應(yīng)新情況等缺點(diǎn)，提出用移動(dòng)傳感器對(duì)事件進(jìn)行監(jiān)測(cè)，彌補(bǔ)了靜態(tài)傳感器的不足;為了提高監(jiān)測(cè)效率，提出了移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃方法.

1 移動(dòng)傳感器對(duì)關(guān)鍵點(diǎn)的監(jiān)測(cè)問題研究

1.1 問題描述

隨機(jī)事件在工作空間的某一固定點(diǎn)出現(xiàn)和消失，這一固定點(diǎn)稱為關(guān)鍵點(diǎn).如果移動(dòng)傳感器在事件消失之前發(fā)現(xiàn)事件，稱隨機(jī)事件被監(jiān)測(cè)到，如果隨機(jī)事件在移動(dòng)傳感器到達(dá)之前消失，那么稱隨機(jī)事件丟失.在關(guān)鍵點(diǎn)處事件的出現(xiàn)和消失的時(shí)間分布是已知的.本文的目的是給出移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃，用于滿足事件監(jiān)測(cè)的指標(biāo).在本文中，假設(shè)關(guān)鍵點(diǎn)的集合是有限離散集.

本文提出的方法應(yīng)用范圍極為廣泛，如監(jiān)視、檢測(cè)、水下網(wǎng)絡(luò)傳感器和供應(yīng)鏈管理.

本文假設(shè)以下3點(diǎn):

1)每個(gè)關(guān)鍵點(diǎn)只被一個(gè)移動(dòng)傳感器監(jiān)測(cè)，如果每個(gè)關(guān)鍵點(diǎn)可以被多個(gè)傳感器監(jiān)測(cè)，會(huì)使問題的復(fù)雜度大大增加.

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

3)移動(dòng)傳感器的速度是相同的.

1.2 關(guān)鍵點(diǎn)事件監(jiān)測(cè)問題的性能分析

本節(jié)對(duì)移動(dòng)傳感器網(wǎng)絡(luò)覆蓋效率的性能進(jìn)行了分析.假設(shè)有a個(gè)關(guān)鍵點(diǎn)，分布在長(zhǎng)度為D的閉合曲線C上.傳感器沿著C運(yùn)動(dòng)，傳感器的探測(cè)半徑為r，相鄰關(guān)鍵點(diǎn)之間的距離大于2r，當(dāng)傳感器與關(guān)鍵點(diǎn)的距離小于r時(shí)才能對(duì)此處的事件進(jìn)行監(jiān)測(cè).

關(guān)鍵點(diǎn)的狀態(tài)在0和1之間變化.狀態(tài)0代表事件出現(xiàn)，狀態(tài)0代表事件消失.狀態(tài)0和狀態(tài)1的持續(xù)時(shí)間服從指數(shù)分布，它們的均值分別為和本文設(shè)λ=μ?i.

假設(shè)傳感器以速度v沿著C運(yùn)動(dòng)，事件完成一個(gè)0→1→0或1→0→1變化稱為一個(gè)循環(huán).L代表一個(gè)狀態(tài)循環(huán)的均值:

移動(dòng)傳感器沿著C運(yùn)行一周，經(jīng)過各關(guān)鍵點(diǎn)一次.每個(gè)關(guān)鍵點(diǎn)能被傳感器監(jiān)測(cè)的時(shí)間為如果在t時(shí)刻，傳感器發(fā)現(xiàn)一個(gè)關(guān)鍵點(diǎn).那么傳感器將在這段時(shí)間內(nèi)對(duì)該關(guān)鍵點(diǎn)進(jìn)行監(jiān)測(cè).傳感器監(jiān)測(cè)到的事件的數(shù)量取決于關(guān)鍵點(diǎn)在t時(shí)刻的狀態(tài)，和在時(shí)間段的循環(huán)次數(shù).定理1 用C(τ)表示在時(shí)間段(t，t+τ)關(guān)鍵點(diǎn)的狀態(tài)循環(huán)次數(shù)，那么在這段時(shí)間內(nèi)狀態(tài)循環(huán)次數(shù)的數(shù)學(xué)期望為

證明:事件的狀態(tài)循環(huán)是一個(gè)更新過程，消失和出現(xiàn)的時(shí)間是2個(gè)服從指數(shù)分布的隨機(jī)變量，在時(shí)間τ內(nèi)更新次數(shù)的數(shù)學(xué)期望的拉普拉斯變換為［19］

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

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

因此，T的概率密度為

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

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

那么，

因此在時(shí)間τ內(nèi)的更新次數(shù)的數(shù)學(xué)期望為

證畢.

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

證明:當(dāng)t時(shí)刻Si(t)=1時(shí)，移動(dòng)傳感器監(jiān)測(cè)到的隨機(jī)事件的數(shù)量為表示移動(dòng)傳感器經(jīng)過一個(gè)關(guān)鍵點(diǎn)2次捕獲到同一事件的概率，則當(dāng)Si(t)=1時(shí)，移動(dòng)傳感器監(jiān)測(cè)到的隨機(jī)事件數(shù)量的數(shù)學(xué)期望為

當(dāng)t時(shí)刻Si(t)=0時(shí)，t'表示關(guān)鍵點(diǎn)的狀態(tài)由0變?yōu)?所需要的時(shí)間，當(dāng)t時(shí)刻Si(t)=0時(shí)，移動(dòng)傳感器監(jiān)測(cè)到的隨機(jī)事件數(shù)量的數(shù)學(xué)期望為

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

證畢.

定理3 移動(dòng)傳感器監(jiān)測(cè)到的事件的比例為

證明:移動(dòng)傳感器沿著C運(yùn)行一圈，捕獲到的事件的數(shù)學(xué)期望記為Nr，Nr的數(shù)學(xué)期望是移動(dòng)傳感器在每個(gè)關(guān)鍵點(diǎn)處捕獲的事件的數(shù)學(xué)期望之和，即

NT'表示在時(shí)間［0，T］隨機(jī)事件出現(xiàn)的總數(shù):

當(dāng)T→∞時(shí)，移動(dòng)傳感器捕獲到的事件的比例為

證畢.

1.3 移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃

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

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

u插入到子路徑Ri中時(shí)，總是把u插入到Ri中的相鄰節(jié)點(diǎn)之間，并且使得路徑的總代價(jià)最小，記為Ri←(u).總路徑R的代價(jià)函數(shù)為:c(R)=Fk(v)，F(xiàn)k(v)為在總路徑R上移動(dòng)傳感器捕獲到的事件的效率:

算法如下:

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

2)對(duì)于每一個(gè)不在(R1，R2，R3，…，Rk)中的關(guān)鍵點(diǎn)vj，1≤j≤a，計(jì)算出vj插入到Ri中的代價(jià)函數(shù)Fk(v)，存在一個(gè)vj和Ri，使得當(dāng)vj被加進(jìn)Ri時(shí)，F(xiàn)k(v)增加最大.

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

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

2 仿真實(shí)驗(yàn)與分析

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

圖1 1個(gè)移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃Fig.1 The motion planning of one mobile sensor

圖2 2個(gè)移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃Fig.2 The motion planning of two mobile sensors

圖3 3個(gè)移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃Fig.3 The motion planning of three mobile sensors

圖4 移動(dòng)傳感器時(shí)監(jiān)測(cè)到的隨機(jī)事件與移動(dòng)傳感器速度的關(guān)系Fig.4 The relationship between Stochastic event capture and the speed of mobile sensors

圖4中的“+”線代表只有一個(gè)移動(dòng)傳感器時(shí)監(jiān)測(cè)到的隨機(jī)事件與移動(dòng)傳感器的速度的關(guān)系，“*”線代表有兩個(gè)移動(dòng)傳感器時(shí)監(jiān)測(cè)到的隨機(jī)事件與移動(dòng)傳感器的速度的關(guān)系，實(shí)線代表有3個(gè)移動(dòng)傳感器時(shí)監(jiān)測(cè)到的隨機(jī)事件與移動(dòng)傳感器的速度的關(guān)系，其他虛線代表固定傳感器的監(jiān)測(cè)效率.從圖形可以看出，隨著速度的增加，移動(dòng)傳感器監(jiān)測(cè)到的隨機(jī)事件的效率也在增加;當(dāng)速度超過某一值時(shí)，移動(dòng)傳感器的監(jiān)測(cè)效率就會(huì)大于固定傳感器的監(jiān)測(cè)效率，隨著移動(dòng)傳感器數(shù)量的增加捕獲效率隨之增加.

3 結(jié)束語(yǔ)

本文對(duì)移動(dòng)傳感器的捕獲效率進(jìn)行了分析，并且提出了一種移動(dòng)傳感器的運(yùn)動(dòng)規(guī)劃方法.通過仿真實(shí)驗(yàn)驗(yàn)證了路徑規(guī)劃方法的可行性，并且分析了監(jiān)測(cè)效率與移動(dòng)傳感器的數(shù)量和速度的關(guān)系，也比較了移動(dòng)傳感器和固定傳感器監(jiān)測(cè)性能.結(jié)果表明隨著速度的增加移動(dòng)傳感器監(jiān)測(cè)到的隨機(jī)事件的效率也在增加，當(dāng)速度超過某一值時(shí)，移動(dòng)傳感器的監(jiān)測(cè)效率就會(huì)大于固定傳感器的監(jiān)測(cè)效率，隨著移動(dòng)傳感器數(shù)量的增加捕獲效率隨之增加，但是增速越來越緩慢.

［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.