傳感器網中基于角度的移動目標跟測方法

李蘭英，蔣維成，周 玲，黃 靜

(成都理工大學工程技術學院 電子信息與計算機工程系，四川 樂山 614000)

0 引 言

無線傳感器網絡中，測定目標所在位置或范圍比較復雜。常用的方法是測定目標與無線傳感器之間的距離，利用目標與多個無線傳感器之間的距離，通過計算得出目標的位置。這種方法投入監測的無線傳感器數量較多，代價也高。目標在移動過程中距離發生改變，又須重新測量。如果目標是圓周上的移動，位于圓心位置的無線傳感器，測得的距離卻是不變的，這就導致測量無法反映目標的變化情況。然而采用角度的測量方式，很容易測得目標角度的變化。對移動軌跡呈圓周狀、扇形，或不規則曲線的這類目標，采用角度的監測方法就具有一定優勢。目標的移動往往是不規則的和復雜的，如野生動物的活動、罪犯或可疑目標在某區域的活動、獨立作業機器的活動，對這類目標的監測，需要掌握目標的活動軌跡，不同時段的位移變化情況，以便對目標進行深入的分析研究。對于復雜的運動，若直接測定移動目標比較困難，可以測定水平和豎直兩個方向的分運動，再通過對運動的合成而得到結果，就能把復雜的問題分解成兩個相對簡單的子問題來解決。采用位于不同方位且相距一定距離的多個無線傳感器對目標進行角度測量，可以很容易得到目標在水平和豎直方向的移動，互相彌補，提高測量的準確度，完成復雜的監測任務。

1 相關研究

無線傳感器網絡在工農業生產和軍事領域具有廣泛的應用，吸引國內外眾多的學者研究。文獻[1]對傳感器分布和布置進行研究，根據短期和長期的不同監控應用優化網絡中的能量利用。文獻[2]在考慮簇中結點分布和距離的基礎上，對leach算法中成簇階段簇頭進行優化。文獻[3]通過設定閾值，采用分層型拓撲控制算法，對網絡能耗進行優化。文獻[4]采用雙簇頭協作方案，減少故障，提高系統的可靠性。文獻[5]根據能量和距離，對Dijkstra算法進行改進，實現能耗均衡。文獻[6]利用綜合鏈路質量指標，對路由協議進行優化，降低網絡能耗。文獻[7]根據實際和理論延時差值對排隊延時進行估算，根據最大和最小排隊延時閾值，對路由進行優化。文獻[8]在短距離傳輸中采用光通信，在長距離傳輸中采用聲通信，基于混合接收信號強度估計結點的位置。文獻[9]把三維空間定位運算降為二維平面運算來對結點進行定位。文獻[10]利用隨機矩陣理論的譜分布定理和協方差矩陣奇異值分解性質實現對異常結點進行定位，提高準確性。文獻[11]運用調度預處理，對鏈路比例沖突空余時間值分配時隙和信道資源，提高網絡調度成功率。文獻[12]采用跨層方法對網絡進行優化，選擇占空比大的結點來提高數據傳輸的可靠性，降低重傳，提高能源效率。

這些算法對無線傳感器網絡資源的使用進行了優化，提高了效率。但缺少對網絡中移動目標的研究。隨著目標的移動，引起監測環境的改變和監測數據的有效性等問題，對移動目標的監測進行研究也是十分必要的。本文提出了基于角度的目標跟測方法(target tracking method based on angle，TTMBA)，采用所圍區域中的關鍵結點對目標進行角度監測，相互彌補，并隨目標的移動動態生成所圍區域對目標進行有效監測。

2 算法框架

2.1 網絡模型

無線傳感器在監測區域內隨機勻速地布置，各結點通過北斗定位系統或GPS獲取其所在的位置。在無線傳感器網絡中為了保持對目標的有效監測，更好地研究目標在網絡中的移動情況，本文討論的模型抽象如下：

(1)假設目標是隨機移動的，目標移動方向和移動速率具有不規則性。

(2)目標在無線傳感器網絡中所在的位置可以抽象為一個點。

(3)每個無線傳感器均能實現0～360°角度的測量，并能對目標進行角度測量。

(4)無線傳感器網絡中的傳感器密度符合要求，對目標進行有效監測，區域內無線傳感器能有效通信。

2.2 區域內測定

以目標所在的位置為中心，其外圍構成一個田字框，田字框的中心與目標重合或者附近。在平面內規定4個方向，x軸的正方向為東，負方向為西；y軸的正方向為北，負方向為南。并且假設田字框的所圍區域是正方形。為討論的方便假設正方形邊長為1。位于4個角上的結點按方向稱為東北角點、東南角點、西南角點、西北角點。位于北方水平線位置的邊稱為北方水平邊，位于北方水平邊中點位置的結點稱為北方水平邊中點。位于南方水平線位置的邊稱為南方水平邊，位于南方水平邊中點位置的結點稱為南方水平邊中點。位于東方豎直線位置的邊稱為東方豎直邊，位于東方豎直邊中點位置的結點稱為東方豎直邊中點。位于西方豎直線位置的邊稱為西方豎直邊，位于西方豎直邊中點位置的結點稱為西方豎直邊中點。田字框所圍成的正方形區域稱為所圍區域，所圍區域的中點位置稱為所圍區域中心。北方水平邊中點和南方水平邊中點的連線與東方豎直邊中點和西方豎直邊中點的連線將所圍區域劃分為4個子正方形區域。這4個子區域稱為：所圍區域東北子區、所圍區域東南子區、所圍區域西北子區、所圍區域西南子區。

位于所圍區域邊界上角點位置和各邊中點位置處的結點是關鍵結點。所圍區域4個角點處的無線傳感器確定位置后，就可以得知所圍區域的位置。由于目標位于所圍區域內，在確定所圍區域的位置后，也就可以知道目標的大概位置。

設目標位置用L表示，無線傳感器結點Sx監測目標具有的關系用ψ(Sx)表示，監測網可以描述如下

L=ψ(Si)∧ψ(Sj)∧ψ(Sk)

(1)

N(Si,Sj)=1,N(Si,Sk)=1

(2)

J(Si)=1

(3)

J(Sj)=0,J(Sk)=0

(4)

Si∝Min{dis(Si,c),dis(Sx,c)} (J(Sx)=1,x=u,v,w)

(5)

其中，N(Sx,Sy)表示無線傳感器結點Sx與Sy是否為相鄰結點，若相鄰則為1，不相鄰為0。J(Sx)表示無線傳感器結點Sx是否位于角點，如果是位于所圍區域的角點位置則為1，否則為0。式(2)、式(3)和式(4)表示結點Si與Sj和Sk相鄰，Si位于角點，結點Sj和Sk不是角點。dis(Sx,c)表示無線傳感器結點Sx與目標c之間的距離。

目標位置由所圍區域關鍵結點中不同方位的3個無線傳感器結點進行測量，一個位于角點位置，另兩個與其相鄰，但不是角點。目標同時滿足這3個無線傳感器監測到的結果，因而有式(1)。該角點在4個角點中距離目標的距離最近，因而有式(5)。

如果要進一步取得目標的位置，可以再對所圍區域進行劃分。南北水平邊中點與東西豎直邊中點的連線把所圍區域劃分成4個子正方形區域。在每個子正方形區域中，對角線之間的連線又將其劃分成4個等腰直角三角形，所圍區域中共有16個面積大小相同的等腰直角三角形。根據位置將所圍區域內的等腰直角三角形劃分為內圈等腰直角三角形和外圈等腰直角三形。內圈等腰直角三角形有一個頂點與所圍區域的中心重合，位于所圍區域的內部。外圈等腰直角三角形位于所圍區域的外部。每個內圈等腰直角三角形外側有一個外圈等腰直角三角形，內圈等腰直角三角形和外圈等腰直角三角形都是8個。

對所圍區域內的等腰直角三角形進行編號，先對內圈等腰直角三角形進行編號，以所圍區域的中心水平向東順時針方向開始，每45°所對應的等腰直角三角形為一個編號，依次為0,1,2,3,4,5,6,7。外圈等腰直角三角形也按順時針方向進行編號，與編號0相鄰的外圈等腰直角三角形編號為8，與編號1相鄰的外圈等腰直角三角形編號為9，以此類推。外圈等腰直角三角形的編號依次為8,9,10,11,12,13,14,15。這樣所圍區域中的16個等腰直角三角形按照一定規律編號成0～15。如圖1所示，圖中帶圈的數字是等腰直角三角形的編號。

圖1 所圍區域

所圍區域中的等腰直角三角形編號后，就可以方便地通過編號找到其所在的區域位置，或者通過區域位置找到相應編號。區域位置和編號之間的關系是一一對應的。

定義1 方向數：方向數是以無線傳感器結點為中心，水平向東開始，逆時針方向旋轉，每45°為一個方向數。其中：0～45°方向數為0，45°～90°方向數為1，90°～135°方向數為2，……，315°～360°方向數為7。整個平面劃分為8個方向數，分別是0，1，2，3，4，5，6，7。

圖1中所圍區域中的東北子區由位于B0處的結點S0測得的方向數是2和3，位于B6處的結點S6測得的方向數是6和7，位于B7處的結點S7測得的方向數是4和5。

位于子區域中關鍵結點位置處的3個無線傳感器監測到目標的方向數分別為θ1，θ2，θ3。子區域內的等腰直角三角形的編號可以由這3個結點測得的方向數來確定，通過適當變換轉換成相應的區域編號。用L(d)表示目標所在位置的等腰直角三角形的編號。若目標處于內圈等腰直角三角形，則有式(6)

L(d)=(θ1+θ2+θ3)-7

(6)

若目標處于外圈等腰直角等腰三角形，則有式(7)

L(d)=(θ1+θ2+θ3)+1

(7)

當目標位于編號為6的等腰直角三角形區域時，位于B0，B6，B7處的無線傳感器S0，S6，S7監測到的方向數分別是3，6，4。根據式(6)可得：L(d)=(3+6+4)-7=6，與該區域的等腰直角三角形編號6相同。目標位于編號為7的等腰直角三角形區域中時，無線傳感器S0，S6，S7監測到的方向數分別是3，6，5。根據式(6)可得：L(d)=(3+6+5)-7=7，與該區域的等腰直角三角形編號7相同。當目標位于編號為15的等腰直角三角形區域時，無線傳感器S0，S6，S7監測到的方向數分別是2，7，5。根據式(7)可得：L(d)=(2+7+5)+1=15，與該區域的等腰直角三角形編號15相同，其余等腰直角三角形的編號驗證略。

原僅知道目標位于所圍區域內，然而在對等腰直角三角形進行編號后，對目標進行方向數的測定，就可以進一步確定目標所在的區域，并將范圍縮小到原來的1/16。

2.3 所圍區域更新與運動合成

目標在區域內移動，在目標移出所圍區域之前，需要對所圍區域進行更新。新的所圍區域根據目標所在的位置不同而分兩種情況生成。這里以所圍區域東南子區進行討論。如圖2所示，B’是東方豎直邊中點B0和東南角點B1之間的中點，B’’是西方豎直邊中點B4和西南角點B3之間的中點。B’B’’之間的連線將所圍區域東南子區劃分為兩部分。第一種情況，目標即將移出時位于所圍區域東南子區B’B’’連線以北。第二種情況，目標即將移出時位于所圍區域東南子區B’B’’連線以南。第一種情況中，目標的移動位置位于所圍區域東方豎直邊附近的中部，新生成的所圍區域應盡可能以目標為中心，新的所圍區域是把原所圍區域水平向東平移邊長的1/2距離。原所圍區域中B0位置處將成為新的所圍區域中心。第二種情況中，目標移動位置位于所圍區域的東南方向，新的所圍區域是把原所圍區域水平向東平移邊長的1/2，然后再豎直向南平移邊長的1/2距離。原所圍區域中結點B1位置處將成為新的所圍區域中心，這樣生成的所圍區域也盡可能以目標為中心。

圖2 更新所圍區域

新生成的所圍區域充分考慮了目標的移動方向和運動趨勢的需要。目標在第一種情況中向東、東北、東南方向移動，生成的所圍區域中有1/2面積可以為目標提供活動范圍。目標在第二種情況中向東、東北、東南或轉變為向南方向移動，生成的所圍區域中有3/4面積可以為目標提供活動范圍。

上述兩種情況生成的所圍區域與原所圍區域存在重疊部分，也就是原所圍區域中有部分區域保留在新生成的所圍區域中。目標當前停留在這部分區域中，由于移動的不確定性，目標可能返回到以前的位置或者附近。保留這部分區域是為了在目標出現這種情況時也能很好地進行監測。

第一種情況生成的所圍區域中，原所圍區域中東南角點B1和南方水平邊中點B2這兩個點成為新生成的所圍區域的關鍵點。第二種情況生成的所圍區域中，原所圍區域中東方豎直邊中點B0和南方水平邊中點B2這兩個點成為新生成的所圍區域的關鍵點。在這兩種情況中，原所圍區域中的8個關鍵結點有且僅有2個關鍵結點在新的所圍區域中，有利于將上一階段的有關信息保留傳遞到下一階段的監測任務中去。另有6個關鍵結點不再是新的所圍區域中的關鍵結點，可以避免結點能量消耗過多而提前死亡。

這里是以所圍區域東南子區為例進行討論的，由于正方形區域具有對稱性，其它子區的情況類似，不再敘述。

要確定目標所在的具體位置，還需要測定目標所在位置角度的大小。這里以所圍區域東南子區進行討論。如圖3所示，若目標位于R處，R與南方水平邊中點B2之間的連線同南方水平邊之間的夾角為α，R與東南角點B1之間的連線同南方水平邊之間的夾角為β，R與東方豎直邊中點B0之間的連線同東方豎直邊之間的夾角為γ。R’為R在南方水平邊上的垂足。R’’為R在東方豎直邊上的垂足。由于所圍區域的邊長為1，B1，B2之間的距離為1/2。那么可得

|RR′|=|B2R′|·tanα

|RR′|=(1/2-|B2R′|)·tanβ

因此，可以進一步得到R與南方水平邊的距離Dv和與東方豎直邊的距離Dh

(8)

(9)

R與所圍區域中點B0,B1,B2之間的距離分別為

圖3 角度

若t0時刻，R與南方水平邊中點B2之間連線與南方水平邊之間的角為α0，t1時刻為α1。若t0時刻，R與東南角點B1之間連線與南方水平邊之間的角為β0，t1時刻為β1。若t0時刻，R與東方豎直邊中點B0與東方豎直邊之間的角為γ0，t1時刻為γ1。

根據式(8)和式(9)可得目標在(t0,t1)時間里在豎直方向的位移增量ΔMv和水平方向的位移增量ΔMh分別為

當ΔMv>0時，t1時刻距離南方水平邊的距離比t0時刻要大，目標向北方向移動。當ΔMv<0時，目標向南方向移動。

當ΔMh>0時，t1時刻距離東方豎直邊的距離比t0時刻要大，目標向西方向移動，當ΔMh<0時，目標向東方向移動。

由水平位移增量和豎直位移增量可以合成目標的位移增量ΔM′，從而有

(10)

位移改變量的角度為φ，并且有

(11)

若知道t0時刻目標的位移，根據式(10)和式(11)可以得到t1時刻的位移。如果對目標進行多次監測，就可以得到這段時間的運動軌跡，以及不同時刻的水平位移增量和豎直位移增量的變化情況，在這兩個分量的基礎上，合成目標的位移，從而對目標移動過程的不同時刻運動改變情況進行深入的分析，掌握目標的詳細移動情況。

這里是以所圍區域東南子區為例進行討論，由于正方形具有對稱性，其它子區的情況類似，也不再敘述。

若知道目標在(tn-1，tn)時間和(tn，tn+1)時間里目標的位移改變情況。根據這兩段時間的位移增量，預測(tn+1，tn+2)時間的位移增量。

如果(tn，tn+1)時間的位移增量和(tn-1，tn)時間的位移增量相同。預測下一段時間(tn+1，tn+2)位移增量也相同。

如果(tn，tn+1)時間的位移增量比(tn-1，tn)時間的位移增量大，預測下一段時間(tn+1，tn+2)位移增量也將增大，增大量與時間成正比。

如果(tn，tn+1)時間的位移增量比(tn-1，tn)時間的位移增量小，預測下一段時間(tn+1，tn+2)位移增量也將減小，減小量與時間成正比。

設置兩個閾值h1和h2，對于不同的應用系統，可以根據環境設置不同。當目標距離所圍區域的邊界距離小于或等于h1時，對目標的位移方向和位移改變大小進行預測。

若目標的位移改變有利于增加目標移出所圍區域的概率，預測目標下一個時段的位置。如果預測位置距離邊界的值小于閾值h2，根據對目標的預測位置，符合第一種情況，按第一種情況生成所圍區域；符合第二種情況，按第二種情況生成所圍區域。

若目標的位移方向發生改變或移動速率減小，導致目標在下一時段移出所圍區域概率減小，過一段時間再檢查目標的移動情況，進行決策。如果目標在下一時段的位置小于閾值h2，則根據目標的位置生成所圍區域。

3 仿真結果

采用Matlab軟件構建算法模型，對本文算法和leach算法進行比較實驗。為了模擬現實環境中不同情況下的執行效果。實驗過程中采用不同的參數進行了多次實驗，對無線傳感器網絡生存期中的有關參數進行了詳細實驗。圖中的TTMBA是本文所提出算法。

(1)網絡中無線傳感器結點死亡數比較

無線傳感器在執行監測任務的過程中不斷地消耗能量，無線傳感器死亡數增多，網絡中擔任監測任務的無線傳感器就越少，導致無效數據增加，重復監測增多，加重網絡通信的負擔，對任務監測和網絡通信都不利。

兩算法中無線傳感器死亡數隨時間的變化情況如圖4所示。從圖4可以看出，在相同的時刻leach算法中死亡數比本文算法要多，本文算法在目標的移動過程中不斷生成新的所圍區域，更換監測的無線傳感器，考慮了能量的均衡利用。避免部分結點能耗過度提前死亡。因而網絡中的無線傳感器死亡數要少。

圖4 死亡數比較

(2)網絡中無線傳感器結點存活數比較

無線傳感器網絡中監測需要存活的無線傳感器來完成，無線傳感器存活數越多，網絡中剩余能量也越多，目標的監測也就能持續有效進行，獲得更多的有效數據，網絡中能量的利用率也就越高。

在執行相同的監測任務情況下，兩算法中無線傳感器結點存活數隨時間的變化情況如圖5所示。從圖5可以看出，在相同的時間里，本文算法要比leach算法存活數要多。本文算法在目標附近生成所圍區域，僅由目標附近的無線傳感器進行監測，提高了監測的準確性和監測的效率，減小了不必要的能量損耗，因而網絡中的存活數要多。

圖5 存活數比較

(3)網絡中無線傳感器死亡百分數的比較

無線傳感器網絡有效期跟網絡中結點死亡百分比有很大關系。監測任務的完成需要網絡中具有一定數量的無線傳感器。隨著網絡中無線傳感器死亡數的增加，將出現某個時刻對移動目標無法監測，監測數據無法及時回傳給Sink結點，網絡中結點通信間斷或中斷，導致網絡有效期縮短。兩算法中無線傳感器死亡4%、9%、14%時的比較如圖6所示。從圖6可以看出，本文算法在這3種死亡百分比情況下均比leach算法時間要晚，表明本文算法的網絡有效生存期更長。本文算法中所圍區域是根據地理位置生成的。而leach算法中簇頭選舉和輪換及相關通信都需要消耗能量，此外本文算法考慮能量的均衡利用。因而在結點死亡4%、9%、14%這3種情況下均比leach算法要晚。

圖6 死亡百分比

4 結束語

獲取目標的位置具有重要意義，可以對目標進行有效的監測。本文采用所圍區域上的關鍵結點基于角度測量方法進行監測，通過對所圍區域中的等腰直角三角形進行編號，運用方向數和編號之間的映射關系，實現目標的快速區域定位。采用角度的測量方法，獲取目標水平位移增量和豎直位移增量，合成目標的位移，詳細掌握目標的移動情況。根據目標的移動，動態生成所圍區域。新生成的所圍區域有較大范圍滿足目標的移動趨勢的需要，同時與原所圍區域存在一定的重疊部分，可滿足目標返回上一狀態位置監測的需要。不同方位的無線傳感器基于角度的測量方法對目標進行監測，相互彌補，使得對目標的監測更加準確。