劉 忠，羅 浩，任雄偉，彭鵬菲

（海軍工程大學電子工程學院，湖北 武漢 430033）

無線傳感器網(wǎng)絡[1]（WSN）是當前國際上備受關注、由多學科高度交叉的新興前沿研究熱點領域。目標定位與跟蹤是WSN的一項重要應用。二進制臨近傳感器[2,3]因其價格低廉、能提供最基本的感知能力（只能提供關于目標是否在其感知范圍內(nèi)的1比特信息），可以大量部署在監(jiān)測區(qū)域?qū)δ繕藢嵤┒ㄎ桓櫋?/p>

在分布式二進制傳感器網(wǎng)絡中，由于沒有嚴格的控制中心，所有節(jié)點地位平等，是一個對等式網(wǎng)絡。由于單個節(jié)點單獨對目標進行定位會帶來很大的誤差，需要多個節(jié)點協(xié)同對目標進行定位，因此跟蹤系統(tǒng)中，節(jié)點的協(xié)作和目標定位算法成為兩個關鍵環(huán)節(jié)?，F(xiàn)有的基于動態(tài)簇的節(jié)點協(xié)作方法[4,5]，因為簇的組建、簇頭對簇結構的管理、簇的重組等需要耗費節(jié)點大量的能量，且常存在丟失目標和簇頭電量耗盡的風險。文獻[4]和[5]的分簇方法并不是專門針對二進制傳感器網(wǎng)絡的，不能直接使用。文獻[6]所采用的“鄰居節(jié)點狀態(tài)表”與本文所用到的鄰居節(jié)點狀態(tài)表相似，但其所指鄰居的概念不同。本文所指的鄰居是指某節(jié)點通信距離范圍內(nèi)所有節(jié)點的集合，文獻[6]中所指的鄰居是指探測區(qū)域與該節(jié)點探測區(qū)域相交的所有節(jié)點的集合（實際應用中，較難獲取）。因此，本文提出了一種簡單的協(xié)作方法，通過傳感器檢測到的特定事件（目標進入或目標離開）觸發(fā)節(jié)點發(fā)送協(xié)作消息和完成對目標的定位，節(jié)點收到消息后對鄰居節(jié)點狀態(tài)表進行更新。

文獻[7]和[8]提出的粒子濾波算法之所以不適用于分布式二進制傳感器網(wǎng)絡，是因為粒子濾波計算復雜度高、實時性差，不適用傳感器節(jié)點級別的處理；文獻[2]和[3]提出的改進質(zhì)心算法，需要節(jié)點時間同步，因而對節(jié)點硬件和能量要求較高；而常用的質(zhì)心定位算法定位精度又太低，滿足不了某些場合的應用需求；文獻[6]提出的求弧中點的定位方法計算復雜、不易實現(xiàn)。因此，本文提出了一種基于m-網(wǎng)格的定位算法，主要研究了分布式二進制傳感器網(wǎng)絡對單目標進行定位的情況，其定位原理簡單、易于實現(xiàn)，計算復雜度可調(diào)節(jié)（通過控制m的大?。?，定位精度優(yōu)于質(zhì)心定位法。

1 網(wǎng)絡模型

分布式二進制傳感器網(wǎng)絡由N個二進制臨近傳感器節(jié)點組成，以隨機的方式均勻部署在監(jiān)視區(qū)域內(nèi)，節(jié)點部署后不移動，如圖1所示。節(jié)點通過全球定位系統(tǒng)（GPS）、有向天線或定位算法等輔助設施和算法?？梢垣@知其位置信息，二進制臨近傳感器只有兩種探測狀態(tài)，即它只能判斷目標處于節(jié)點探測區(qū)域之內(nèi)或者之外。為了使問題簡單化，文中假設所有的傳感器節(jié)點具有相同的探測半徑。特別地，本文傳感器節(jié)點能夠檢測出前后兩個時刻的探測狀態(tài)是否相同，即傳感器節(jié)點能夠檢測到目標進入或離開傳感器的探測區(qū)域。

圖1 用于目標跟蹤的二進制傳感器網(wǎng)絡

2 簡單協(xié)作方法

簡單協(xié)作方法描述如下：每個節(jié)點負責維護一張鄰居節(jié)點狀態(tài)表，表的每條記錄包括鄰居節(jié)點編號、位置、狀態(tài)（表明是否探測到目標）。傳感器節(jié)點部署后，節(jié)點通過相互發(fā)送“Hello消息”，可以獲取鄰居節(jié)點編號、位置；狀態(tài)初始統(tǒng)一設置為“0”（表明沒有探測到目標）。當節(jié)點檢測到目標進入或離開傳感器節(jié)點的探測區(qū)域時，本地廣播（單跳）一個目標進入消息或目標離開消息。收到“目標進入消息”或“目標離開消息”的節(jié)點對其鄰居節(jié)點狀態(tài)表進行更新。更新的規(guī)則如下：如果收到的是“目標進入消息”，從該消息中可以提取發(fā)送該消息的節(jié)點編號，在鄰居節(jié)點表中查找到該節(jié)點編號的記錄，將記錄中的狀態(tài)屬性更新為“1”；如果收到的是“目標離開消息”，從該消息中可以提取發(fā)送該消息的節(jié)點編號，在鄰居節(jié)點表中查找到該節(jié)點編號的記錄，將記錄中的狀態(tài)屬性更新為“0”。各協(xié)作消息的定義見表1。并規(guī)定：節(jié)點僅當探測到目標進入或目標離開傳感器探測區(qū)域時，利用鄰居節(jié)點狀態(tài)表提供的信息對目標進行定位，并將定位結果發(fā)送給遠方基站，由基站采用跟蹤算法對定位點序列進行處理。

表1 協(xié)作消息定義

從以上描述可以看出，當目標在傳感器網(wǎng)絡監(jiān)視區(qū)域運動時，只有節(jié)點檢測到目標進入或離開它的探測區(qū)域時，它才會單跳廣播“目標進入消息”或“目標離開消息”，因此通信量很小。

3 基于m-網(wǎng)格的定位算法

當節(jié)點檢測到目標進入或離開其傳感器探測區(qū)域時，它利用鄰居節(jié)點狀態(tài)表提供的信息對目標進行定位。通過鄰居節(jié)點狀態(tài)表，節(jié)點可以知道當前自己的鄰居節(jié)點是否探測到目標。最簡單的定位方法是常用的質(zhì)心定位法，它是取所有探測到目標的節(jié)點位置的均值作為對目標位置的估計。

與該方法不同，我們提出了一種基于m-網(wǎng)格的定位方法，該方法考慮到了未探測到目標的鄰居節(jié)點對定位所作的貢獻。其主要思想是：先確定一個包括目標可能存在位置的矩形區(qū)域，然后將該區(qū)域劃分m個網(wǎng)格（m=n2，n為自然數(shù)），確定這些網(wǎng)格中心點（網(wǎng)格點）的坐標，選出滿足一定條件的網(wǎng)格點，以這些網(wǎng)格點坐標的均值作為對目標位置的估計。如圖2所示，節(jié)點3檢測到目標進入，搜索鄰居節(jié)點表發(fā)現(xiàn)節(jié)點1和節(jié)點2也探測到目標，而節(jié)點4未探測到目標，先通過節(jié)點1、節(jié)點2和節(jié)點3的位置確定圖中的矩形區(qū)域，然后對矩形區(qū)域進行網(wǎng)格化，找到陰影區(qū)域內(nèi)的網(wǎng)格對應的網(wǎng)格點，以這些網(wǎng)格點位置的均值作為對目標位置的估計。

圖2 定位算法原理示意圖

基于m-網(wǎng)格的定位算法描述如下。

1）先通過鄰居節(jié)點表中探測到目標的節(jié)點的位置信息，得到目標位置可能存在的矩形區(qū)域。假設鄰居節(jié)點表中有假設有N個節(jié)點探測到目標，第i個節(jié)點的坐標為(xi,yi)，節(jié)點的探測半徑為R，通過

可計算出目標存在的矩形區(qū)域的左下角坐標(xz,yz)和右上角坐標(xy,yy)。

2）將矩形區(qū)域劃分成m個網(wǎng)格，得到每個網(wǎng)格中心點（網(wǎng)格點）的位置坐標。網(wǎng)格的劃分方法是將矩形區(qū)域在橫坐標方向上平均分成n等分（打n-1條縱線），在縱坐標方向上平均分成n等分（打n-1條橫線），這樣就得到了n×n個網(wǎng)格。由

可以計算出目標可能存在區(qū)域中第i行、第j列的網(wǎng)格對應的網(wǎng)格點坐標(xij,yij)。

3）計算每個網(wǎng)格點與鄰居節(jié)點表內(nèi)沒有探測到目標的節(jié)點的距離，若該距離小于探測半徑，則刪掉該網(wǎng)格點。

4）若剩余的網(wǎng)格點集合為空，取矩形區(qū)域的中心位置作為對目標位置的估計；否則，取剩余網(wǎng)格點位置的平均值作為對目標位置的估計。

通過以上描述，可以看出基于m-網(wǎng)格的定位算法的計算復雜度與m的大小以及節(jié)點鄰居中未探測到目標的節(jié)點的個數(shù)（設為l）相關。該算法的主要運算是求定位點與未探測到目標的鄰居節(jié)點的距離，根據(jù)算法的描述，該算法最多要做lm×次距離計算。在實際運用中，可以通過控制m的大小來調(diào)節(jié)計算復雜度，節(jié)約節(jié)點處理器運算時耗費的能量。

4 仿真分析

為驗證本文算法的有效性，進行了仿真分析，并與質(zhì)心定位方法進行了比較。假設監(jiān)測區(qū)域為 100 m×100 m的方形區(qū)域，坐標原點設在傳感器網(wǎng)絡覆蓋區(qū)域的左下角；100個二進制臨近傳感器節(jié)點以均勻分布的方式隨機散布在該區(qū)域，節(jié)點探測半徑為 10 m，節(jié)點采樣周期為1 s；目標從傳感器網(wǎng)絡覆蓋區(qū)域的左下角向右上角勻速運動，即目標的初始位置為(0 m,0 m)，速度為(1 m/s,1 m/s)。在仿真中，記錄每個定位時刻的定位距離誤差，然后取該次仿真中各個定位時刻定位距離誤差的均值，作為不同定位方法定位精度的比較標準。

圖3為節(jié)點通信半徑取2倍節(jié)點探測半徑，m取不同值時，本文定位方法的平均定位誤差桿圖。從該圖可以看出，并不是m值越大，定位精度就越高，當m值增加到一定大小時，定位精度反而會下降。在該圖中，當m=64時，平均定位距離誤差最小為3.05 m，當m=4時，平均定位距離誤差最大為3.81 m。對于質(zhì)心法而言，平均定位距離誤差為4.05 m，這說明本文定位算法精度高于質(zhì)心算法。

圖4為m=36時，不同通信半徑下（節(jié)點探測半徑的1倍～3倍），本文算法和質(zhì)心定位算法的平均定位距離誤差的比較。從圖中可以看出，通過增加節(jié)點通信半徑的方式提高定位算法的平均定位距離誤差有一定的極限，對于質(zhì)心定位方法，當節(jié)點通信半徑提高到2倍節(jié)點探測半徑時，極限達到；而對于本文方法，當節(jié)點通信半徑提高到 2.6倍節(jié)點探測半徑時，極限達到。同時，在不同的通信半徑下，本文算法的定位精度要高于質(zhì)心算法。

圖3 m的取值對本文算法定位精度的影響

圖4 節(jié)點通信距離對定位算法估計精度的影響

圖5給出了不同m取值下，不同通信半徑對本文定位算法精度的影響。從圖中可以看出，不同m取值下，通過增加節(jié)點通信半徑來提高算法的定位精度均存在一定的極限，對于本態(tài)勢而言，節(jié)點通信半徑大于26 m時，平均定位距離誤差將不再降低；而且，對本態(tài)勢而言，m取81，節(jié)點通信半徑取26 m，平均定位距離誤差將降到最低為2.35 m，較質(zhì)心定位法定位精度提高 42%（質(zhì)心定位法的平均定位距離誤差為 4.02 m）；從降低算法計算復雜度的角度看，也存在著次優(yōu)選擇，如m取25，節(jié)點通信半徑取26 m，此時平均定位距離誤差為2.40 m，較質(zhì)心定位法定位精度提高40%（質(zhì)心定位法的平均定位距離誤差為4.02 m）。

圖5 節(jié)點通信距離對不同m值的本文算法的影響

上述仿真表明，在本文所給協(xié)作方式下，本文算法的定位精度高于質(zhì)心定位法，而且適當調(diào)整節(jié)點的通信半徑（在已知節(jié)點探測半徑的情況下）和m的取值，本文算法能夠提供較質(zhì)心定位法更高的精度。

5 結束語

分布式二進制傳感器網(wǎng)絡中的目標協(xié)作定位問題涉及到節(jié)點的協(xié)作和目標定位算法兩個重要方面，本文從簡單協(xié)作的角度出發(fā)，提出的簡單的協(xié)作方法使得每個節(jié)點通過簡單的廣播通信，就可以知道自己鄰居節(jié)點探測目標的情況，通信量很小。對于單個節(jié)點而言，僅當目標進入或離開其探測區(qū)域時，才對目標進行定位。所提出的基于m-網(wǎng)格的定位方法，原理簡單、易于實現(xiàn)、計算復雜度可調(diào)節(jié)，可以提供比質(zhì)心法更高的定位精度。本文考慮的節(jié)點探測模型比較理想，在應用本文方法時，需要將實際傳感器探測模型進行分析，從軟件上改進其判決目標是否存在的方式，使其與理想的探測模型較為一致。如對于測量聲音能量的傳感器，可以滿足較小恒虛警需求的硬判決閾值，然后設置節(jié)點聲音能量多次超過閾值才判斷發(fā)現(xiàn)目標（這對于節(jié)點探測半徑較大，探測的目標速度很慢的應用場合是可以的），這樣虛警概率將降到很低。在下一步研究中，我們將重點考慮節(jié)點探測的不確定性對本文算法的影響，對算法進一步改進，提高其魯棒性。

[1]Chong C Y,Kumar S P.Sensor Networks: Evolution,Opportunities,and Challenges[C].Proceedings of the IEEE,USA,August 2003: 1247-1256.

[2]Kim W,Mechitov K,Choi J Y,et al.On Target Tracking with Binary Proximity Sensors[C].Proceedings of the 4th International Conference on Information Processing in Sensor Networks,Piscataway,NJ,USA,2005: 301-308.

[3]Mechitov K,Sundresh S,Kwon Y,et al.Cooperative Tracking with Binary-Detection Sensor Networks[R].Technical Report UIUCDCS-R-2003-2379,University of Illinois at Urbana-Champaign,September 2003.

[4]鄧克波，劉中.基于無線傳感器網(wǎng)絡動態(tài)簇的目標跟蹤[J].兵工學報，2008，29(10)：1197-1202.

[5]申興發(fā)，李鴻斌，趙軍，等.面向目標跟蹤的傳感器網(wǎng)絡分布式組管理機制[J].儀器儀表學報，2007，28(6)：966-972.

[6]Zijian W,Eyuphan B,Boleslaw K.S.A Distributed Cooperative Target Tracking with Binary Sensor Networks[C].IEEE International Conference on Communication Workshops,May 2008: 306-310.

[7]Djuric P M,Vemula M,Bugallo M F.SIGNAL PROCESSING BY PARTICLE FILTERING FOR BINARY SENSOR NETWORKS[C].2004 IEEE 11th Digital Signal Processing Workshop & IEEE Signal Processing Education Workshop,Taos,NM,USA,August 2004: 263-267.

[8]Djuric P M,Vemula M,Bugallo M F.Target Tracking by Particle Filtering in Binary Sensor Networks[J].IEEE Transactions on Signal Processing,2008,56(6):2229-2238.