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

楊秀萍，崔 強，廖朝輝

（廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州510003）

0 引 言

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

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

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

1 系統(tǒng)模型

網(wǎng)絡(luò)區(qū)域的大小由（xmin，ymin）和（xmax，ymax）表示。車輛的行駛最大速度為υmax，且為已知參數(shù)。錨節(jié)點和車輛行駛的最大通信范圍分別為Ra、Rv。在每個瞬時t，車輛觀察錨節(jié)點，從而產(chǎn)生N 個可能狀態(tài)。每個狀態(tài)關(guān)聯(lián)車輛所在的可能位置。依據(jù)文獻(xiàn) ［5］，可將其稱為樣本Samples，如式 （1）所示

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

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

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

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

2 基于非測距的車輛跟蹤

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

（1）Observation

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

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

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

（2）建立錨節(jié)點邊框Anchor box

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

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

對于二跳錨節(jié)點

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

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

圖1 Anchor box

（3）Box抽樣

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

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

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

抽樣后的Anchor box如圖2所示。經(jīng)抽樣后，縮小了區(qū)域范圍，降低計算復(fù)雜度，也節(jié)省了車輛能量。

圖2 抽樣后的Anchor box

（4）位置估計

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

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

圖3 算法流程

3 性能分析

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

3.1 仿真環(huán)境

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

3.2 仿真數(shù)據(jù)及仿真

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

圖7 平均跟蹤誤差的偏差

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