基于錨節點－邊框的非測距車輛跟蹤算法

楊秀萍，崔 強，廖朝輝

（廣東工業大學 計算機學院，廣東 廣州510003）

0 引 言

車輛跟蹤技術關鍵在于如何實施目標定位［1－3］。目前，主要有基于測距 （range－based）和非測距 （range－free）的兩大類定位算法［4］。基于測距定位算法是通過測量錨節點（已知位置的傳感節點）與未知節點的角度、距離值，從而估計未知節點的位置。經典的基于測距定位算法有：到達角度測量 法AOA （angel of arrival）［5］、到 達 時 間 測 量 法TOA （time of arrival）［6］、到達時間差測量法TDOA （time difference of arrival）［7］和 基 于 接 收 信 號 強 度 測 量 法RSSI（received signal strength indicator）［8］。非測距的定位算法是通過網絡拓撲結構等信息估計未知節點的位。盡管非測距方案無需測距設備，成本低，但是其定位精度低于基于測距方案。為此，本文僅考慮基于測距定位方案。在基于測距定位方案中，利用含有噪聲的位置數據去估計目標節點位置。為了實現這個目標，節點間需進行節點通信。依據節點通信范圍的不同，又可將定位方案分為合作式和非合作式。所謂非合作式是指源節點僅能與錨節點通信，而合作式是指源節點能與網絡內所有節點 （源節點、錨節點）通信，這兩種方式均可通過分布式或集中式模式實現。盡管分布式方案具有低復雜度、高可擴展性，但是其對傳播模型錯誤很敏感，并且處理時延長。因此，本文僅考慮集中式的非合作式定位算法。

測距方面的研究，可采取多種方式測距，如接收信號強度RSS （received signal strength）、到達時間差TDOA、到達時間TOA、往返路徑時間RTT （round－trip－time）以及到達角度AOA。在應用這些測距方案，必須權衡該方案的定位精度和復雜度間的關系。例如，基于TOA 或TDOA的測距定位方案，具有高的定位精度，但是要求收／發兩端具有嚴格的時間同步，需添加額外的設備，提高定位成本［9，10］。盡 管 基 于RSS 測 距 定 位 的 定 位 精 度 低 于TOA、TDOA，但是其不需要特殊的硬件設備，降低了系統成本［10］。基于RSS測距定位技術受到廣泛關注，且常采用最大似然估計ML （maximum likelihood），然而，由于基于RSS測距定位問題是非線性和凸性，求解的ML 估計是一項挑戰工作，其存在多個局部最優解。

為此，面對不同的VANET 環境，提出基于分布式的非測距車輛跟蹤算法。分布式的策略提高了算法的可擴展性，同時采用非測距定位，降低了成本。該算法在實施過程中，節點觀察鄰居節點的信息，并將錨節點進行歸類，隨后建立Anchor box，再利用車輛的行駛速度對Anchor box進行抽樣［12］，進一步縮小目標區域位置，最后再基于離散－抑制技術的濾波策略，跟蹤車輛的位置［13］。

1 系統模型

網絡區域的大小由（xmin，ymin）和（xmax，ymax）表示。車輛的行駛最大速度為υmax，且為已知參數。錨節點和車輛行駛的最大通信范圍分別為Ra、Rv。在每個瞬時t，車輛觀察錨節點，從而產生N 個可能狀態。每個狀態關聯車輛所在的可能位置。依據文獻 ［5］，可將其稱為樣本Samples，如式 （1）所示

其中，N 為樣本Samples集的大小。

通過對錨節點的觀察，可產生兩個集合：一跳集 、二跳集 ，其定義如下［10］：

（1） ：能直接與車輛通信的車輛。即錨節點與車輛的歐式距離dav≤Ra。

（2） ：通過鄰居節點間接地與車輛通信的錨節點，即錨節點與車輛的歐式距離Ra＜dav≤Ra＋Rv。

2 基于非測距的車輛跟蹤

本節，將分析提出非測距的車輛跟蹤算法。提出的算法可分為觀察 （observation）、預測 （prediction）和濾波（filter）階段。每個車輛可能被一個或多個錨節點覆蓋，并估計自己所在的可能區域 （region），再利用Monte－Carlo算法進一步縮小自己 （車輛）所在位置點 （points）。最后通過離群－抑制技術 （outlier rejection technique）進行濾波，剩余的Points就是車輛最終的位置估計值。

（1）Observation

首先，錨節點周期地廣播ID 以及位置信息。同時，每個車輛將自己的一跳錨節點的位置信息傳遞給鄰居車輛。在最初時刻，車輛監聽所有錨節點以及鄰居車輛，并存儲所監聽到的錨節點位置信息，存儲格式如式 （2）所示

式中：AP——鄰居列表，Ij——錨節點j的ID 號。（xj，yj）為節點j的位置。

給定車輛υ，列表中的錨節點j可分為兩類：一類屬于一跳集 、一類屬于二跳集 ，如式 （3）、式 （4）所示

（2）建立錨節點邊框Anchor box

所謂錨節點邊框Anchor box就是一個區域，即一跳和二跳錨節點覆蓋的重疊區域。因此，box所在位置很大可能就是車輛所在的區域位置。在時刻t，Anchor box區域如式 （5）所示

若錨節點j的位置為（xj，yj），j＝1，2，…，N ，則一跳錨節點的Anchor box的參數如式 （6）所示

對于二跳錨節點

式 （6）、式 （7）中的min、max 表示求最小、最大運算。

圖1顯示了由3個錨節點構成的Anchor box，黑實點表示錨節點，圓圈表示錨節點通信范圍，陰影矩形表示Anchor box。若只有一個錨節點，那整個錨節點通信范圍就為Anchor box。

圖1 Anchor box

（3）Box抽樣

一旦建立了Anchor box，需對其進行抽樣。前一時刻t的樣本集如式 （8）所示

考慮節點行駛速度vmax，則抽樣后的Anchor box的邊緣長度為2 vmax。經第ith抽樣后，Anchor box表示為Si

其中，式 （9）的4個參數如式 （10）所示

抽樣后的Anchor box如圖2所示。經抽樣后，縮小了區域范圍，降低計算復雜度，也節省了車輛能量。

圖2 抽樣后的Anchor box

（4）位置估計

在建立了由車輛所在的可能位置所構成的抽樣集后，估計車輛的位置（xest，yest），利用式 （8）可得

提出的整個算法的流程如圖3所示。

圖3 算法流程

3 性能分析

本節，分析提出非測距的跟蹤算法。

3.1 仿真環境

考慮面積為500m×500 m 網絡區域，共425個節點，其中錨節點數85個。車輛行駛的最大速度、最小速度分別為10m／s、0m／s。節點間依據IEEE 802.15.4協議進行通信。為了顯示提出算法的有效性，與文獻 ［10］提出MCL方案進行對比仿真。

3.2 仿真數據及仿真

在仿真過程中，考慮由通信范圍歸一化的平均跟蹤誤差 （normalized by radio range average tracking error）評估性能。同時考慮離群－抑制技術。在每一時刻，計算所有跟蹤誤差E 的均值M 和標準方差S。若滿足

就丟棄跟蹤誤差E，不進入計算跟蹤誤差的平均值，其中E、M 、S 分別表示跟蹤誤差、跟蹤誤差的均值和方差。

為了分析采用Outlier rejection 技術的有效性，圖4、圖5顯示了有、無采用Outlier rejection技術的平均跟蹤誤差曲線。若采用了，在圖中標識為with outlier rejection；否則標識為without outlier rejection。

圖4 提出算法的歸一化的平均跟蹤誤差

圖4顯示所提出算法的平均跟蹤誤差。從圖4 可知，隨著仿真時間的增長，平均跟蹤誤差呈穩定的趨勢。當時間大于15s后，without outlier rejection的歸一化的平均跟蹤誤差為0.09，而with outlier rejection的歸一化的平均跟蹤誤差僅為0.07，下降了20%。這說明outlier rejection技術的有效性。

圖5顯示MCL 的平均跟蹤誤差。與圖4 相似，通過Outlier rejection降低了平均跟蹤誤差約20%。將圖4與圖5進行比較可知，提出的算法極大降低平均跟蹤誤差。例如，在時間大于15s，MCL 方案在有、無采用Outlier re－jection技術的歸一化的平均跟蹤誤差分別為0.2、0.3，而提出算法的僅為0.07、0.09，提出的算法有效地降低了平均跟蹤誤差。

圖5 MCL歸一化的平均跟蹤誤差

圖6顯示了比較了MCL和提出的算法的歸一化平均跟蹤誤差隨車輛速度的變化情況，且車輛速度從10m／s變化至60m／s。

圖6 歸一化平均跟蹤誤差隨車輛速度的變化情況

從圖6可知，隨著車輛速度的提升，跟蹤誤差呈增加的趨勢。圖6的數據再次驗證了Outlier rejection技術能夠有效地降低跟蹤誤差。此外，與MCL方案相比，提出算法在整個車輛速度變化范圍內的平均跟蹤誤差得到有效的下降，并且車速越大，下降地越明顯。當車速為50 m／s時，下降了約50%。

圖7顯示了兩個方案的平均跟蹤誤差的偏差 （average tracking error deviation）情況。從圖7可知，Outlier rejection技術使誤差更穩定。而提出的算法的偏差都集中于－0.05至0.05范圍內，這也說明提出的算法能夠有效地降低平均跟蹤誤差。

4 結束語

圖7 平均跟蹤誤差的偏差

針對智能城市的車輛跟蹤問題，提出基于非測距的分布式目標跟蹤算法。分布式的策略提高了算法的可擴展性，同時采用非測距定位，降低了成本。該算法在實施過程中，節點觀察鄰居節點的信息，并將錨節點進行歸類，隨后建立Anchor box，再利用車輛的行駛速度對Anchor box進行抽樣，進一步縮小目標區域位置，再基于離散－抑制技術的濾波策略，跟蹤車輛的位置。與MCL方案相比，提出的基于非測距的分布式目標跟蹤算法能夠有效地跟蹤車輛，歸一化的平均跟蹤誤差約為0.09。

［1］Sahinoglu Z，Gezic S I，Guvenc I.Ultra－wideband positioning sytems：Theoretical limits，ranging algorithms and protocols［M］.English：Cambridge University Press，2008.

［2］Patwari N，Hero A，Perkins M，et al.Relative location estimation in wireless sensor networks［J］.IEEE Transactions on Signal Processing，2013，51 （8）：2137－2148.

［3］Cheung KW，So HC，Ma WK，et al.A constrained least squares approach to mobile positioning：Algorithms and optimality ［J］.EURASIP Journal on Applied Signal Processing，2006：1－6.

［4］Lazos L，Poovendran R.Serloc：Secure range in dependent localization for wireless sensor networks ［C］／／Proceedings of the 3rd ACM Workshop on Wireless Security.ACM，2004：21－30.

［5］Hu L，Evans D.Localization for mobile sensor networks［C］／／Proceedings of the 10th Annual International Conference on Mobile Computing and Networking.ACM，2004：45－57.

［6］Zhang Y，Liu S，Jia Z.Localization using joint distance and angle information for 3d wireless sensor networks ［J］.Communications Letters.IEEE，2012，16 （6）：809－811.

［7］Zhou Y，Li J，Lamont L.Multilateration localization in the presence of anchor location uncertainties［C］／／Global Communications Conference.IEEE，2012：309－314.

［8］Kumar S，Sharan V，Hegde R M.Energy e＿cient optimal node－source localization using mobile beacon in Ad－Hoc sensor networks［C］／／Globecom Ad Hoc and Sensor Networking Symposium，2013：509－514.

［9］Ekim P O，Gomes J，Xavier J，et al.Robust localization of nodes and time－recursive tracking in sensor networks using noisy range measurements ［J］.IEEE Transactions on Signal Processing，2011，59 （8）：3930－3942

［10］Baggio A，Langendoen K.Monte carlo localization for mobile wireless sensor networks ［J］.Ad Hoc Networks，2008，6（5）：718－733.

［11］Saleet H N，Langar R，Naik K.Intersection－based geogra－phical routing protocol for VANETs：A proposal and analysis［J］.IEEE Transactions on Vehicular Technology，2011，60（9）：4560－4575.

［13］Vaghefi R M，Gholami M R，Buehrer R M.Cooperative received signal strength－based sensor localization with unknown transmit powers［J］.IEEE Trans Signal Process，2013，61（6）：1389－1403.