孫友偉，王辰寰，張 晶

(西安郵電大學 通信與信息工程學院，西安 710121)

?

基于禁忌搜索的車聯(lián)網(wǎng)蒙特卡洛定位算法

孫友偉，王辰寰，張 晶

(西安郵電大學 通信與信息工程學院，西安 710121)

在蒙特卡洛定位算法中引入禁忌搜索算法以提高車聯(lián)網(wǎng)中快速定位的性能；自組織車聯(lián)網(wǎng)高速移動的車輛和快速變化的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，使用傳統(tǒng)的蒙特卡洛定位算法，不能迅速地收斂位置信息；在濾波階段引入禁忌搜索算法對傳統(tǒng)蒙特卡洛定位算法進行改進, 優(yōu)化濾波排除可能性較小的位置點，獲得近似最優(yōu)估計位置采樣集；仿真結(jié)果表明，改進后的算法在樣本采集數(shù)、計算時間、定位精度等方面有了顯著提升，改進后的算法能更好地解決車聯(lián)網(wǎng)的定位問題。

蒙特卡洛定位；禁忌搜索算法；車聯(lián)網(wǎng)；距離無關(guān)；定位

0 引言

物聯(lián)網(wǎng)現(xiàn)今得到了長足的發(fā)展，諸如電力線通信、車聯(lián)網(wǎng)等新興領(lǐng)域成為物聯(lián)網(wǎng)研究的熱點[1]，基于車聯(lián)網(wǎng)的定位也成為業(yè)內(nèi)急需解決的問題。傳統(tǒng)的移動節(jié)點定位算法基本歸納為兩類，一類是基于距離的定位算法，比如利用信號強度、到達時間、方位角度等確切物理值進行定位；另一類是與距離無關(guān)定位算法，通過連通網(wǎng)絡(luò)間傳送的消息進行定位[2]。一般而言基于距離的定位算法精確度較高，但其缺點也很顯著，比如對硬件要求高、易受周圍環(huán)境影響等；與距離無關(guān)定位算法通常來講其定位精度不高。但其優(yōu)點也很顯著，比如不需時間同步、對硬件要求不高、節(jié)省能耗等[3]。傳統(tǒng)的定位算法大多面向靜態(tài)網(wǎng)絡(luò)，不能有效解決車聯(lián)網(wǎng)中汽車節(jié)點隨時動態(tài)變化的問題，這成為近來車聯(lián)網(wǎng)定位面臨的一個主要難點。

1 提出問題

我們設(shè)計的車聯(lián)網(wǎng)是基于自組織網(wǎng)絡(luò)并且網(wǎng)絡(luò)中移動節(jié)點高速運動，網(wǎng)絡(luò)拓撲結(jié)構(gòu)高度動態(tài)變化[4]，傳統(tǒng)定位方法已經(jīng)不適用。根據(jù)車聯(lián)網(wǎng)這一結(jié)構(gòu)特點，本文提出一種改進型的蒙特卡洛(MCL)定位算法。Monte Carlo方法由美國科學家馮.諾依曼等人首先提出，后來廣泛應用于經(jīng)濟、物理、生物醫(yī)學領(lǐng)域，主要用于統(tǒng)計模型的建立。Monte Carlo方法首次用于定位領(lǐng)域是Sebastin Thrun等人通過蒙特卡洛采樣確定移動機器人所處位置的概率[5]。MCL定位算法根據(jù)節(jié)點移動性構(gòu)建數(shù)學模型[6]，在貝葉斯濾波位置估計的基礎(chǔ)上，利用若干個帶有權(quán)重的采樣點來計算移動節(jié)點在某一位置出現(xiàn)的概率，最終實現(xiàn)節(jié)點定位[7]。但是我們在仿真MCL定位算法的過程中發(fā)現(xiàn)，傳統(tǒng)的MCL算法計算量大，位置估測樣本較大，濾波過程耗時較長，且定位精度不高。因此我們在傳統(tǒng)MCL算法濾波階段引入禁忌搜索算法，經(jīng)過一系列實驗證明，改進后的算法與傳統(tǒng)MCL算法相比，改進后的算法能夠很好地適應車聯(lián)網(wǎng)節(jié)點動態(tài)變化，并在樣本集數(shù)量、計算時間、定位精度等幾項參數(shù)指標方面均有顯著提升。禁忌搜索算法(Tabu Search,TS)是一種全局優(yōu)化算法。禁忌搜索算法廣泛應用于路由優(yōu)化、函數(shù)優(yōu)化等方面[8]。禁忌搜索算法在濾波優(yōu)化定位方面能夠很好地契合車聯(lián)網(wǎng)中高速移動節(jié)點快速定位的需求。

本文提出的TS-MCL算法屬于與距離無關(guān)定位算法，該算法不僅能夠滿足與距離無關(guān)定位算法的各項優(yōu)點，而且通過對傳統(tǒng)MCL定位算法的改進，TS-MCL能達到較高的定位精度。

2 網(wǎng)絡(luò)模型描述

在城市智能交通的車聯(lián)網(wǎng)模型中，城市按照一定面積劃定一個區(qū)域，區(qū)域內(nèi)設(shè)若干固定路基信息點，這些信息點與其覆蓋范圍內(nèi)的車輛進行雙向通信，用于采集車輛實時信息以及向車輛傳送交通控制中心的實時播報。設(shè)每一個信息點為錨節(jié)點，錨節(jié)點為靜止狀態(tài)，錨節(jié)點每隔一定時間發(fā)出包含錨節(jié)點自身位置信息的輪詢信號，則以錨節(jié)點為圓心、錨節(jié)點所發(fā)送信號的最大傳輸距離為半徑的圓內(nèi)的所有移動節(jié)點均能接收到輪詢信號。模型不考慮環(huán)境對信號的干擾等問題，并確保錨節(jié)點發(fā)出的輪詢信號可以被不大于νmax速度運動的移動節(jié)點隨時接收。

車聯(lián)網(wǎng)中移動節(jié)點定位的相關(guān)空間變量定義如表1所示。

(1)

狀態(tài)更新方程為：

(2)

將式(1)代入式(2)，因為p(ot|o1:t-1)是歸一化常量，所以看作已知數(shù)，故對于p(ot|lt)、p(lt|o1:t-1)、p(lt|o1:t)三者來說，只需要得任意兩個，即可得第3個[9]。

3 TS-MCL算法描述

3.1 位置初始化

3.1.1 初始化

移動節(jié)點在定位以前并不知曉關(guān)于其自身所在N個位置的先驗位置信息，故需要對其進行初始化操作(N表示算法執(zhí)行過程中所要維持的采樣數(shù))。

圖1 移動節(jié)點估測范圍

估測范圍的確定如圖1所示，當移動節(jié)點接收到一個錨節(jié)點的位置信息時，其估測范圍為Ⅰ(圖1(a))，錨節(jié)點為中心的信號傳輸最大距離為半徑的圓形區(qū)域。當移動節(jié)點接收到兩個錨節(jié)點的位置信息時，其估測范圍為Ⅱ(圖1(b))，即兩個錨節(jié)點交叉覆蓋范圍。當移動節(jié)點接收到3個錨節(jié)點的位置信息時，其估測范圍為Ⅲ(圖1(c))，即3個錨節(jié)點交叉覆蓋范圍。同理，可得移動節(jié)點接收到更多錨節(jié)點位置信息時的估測范圍。

L0=[移動節(jié)點所在區(qū)域內(nèi)隨機確立的 N個可能位置]

3.1.2 循環(huán)計算

根據(jù)Lt-1以及Ot計算Lt，三者分別代表上一時間段內(nèi)移動節(jié)點的可能位置序列、新的觀測值、移動節(jié)點新的可能位置。

初始位置確定后，每間隔一定時間通過移動節(jié)點的運動情況和新的觀測信息對移動節(jié)點的位置序列進行位置更新。

3.2 位置預測

(3)

將式(3)的計算結(jié)果代入式(1)中，可計算出預測方程中的p(lt|o1:t-1)值。

3.3 TS尋優(yōu)濾波

在濾波過程中采用禁忌搜索策略(TS)通過優(yōu)化濾波排除可能性較小的位置點，獲得近似最優(yōu)估計位置采樣集[11]。與傳統(tǒng)MCL算法濾波過程相比較，禁忌搜索算法通過較少的迭代次數(shù)和暫時鎖定局部極值引導搜索向其他路徑延伸，在節(jié)約時間和提高準確度上有著明顯的優(yōu)勢[12]。位置采樣集中的元素依靠領(lǐng)域函數(shù)產(chǎn)生領(lǐng)域元素集，通過建立禁忌表避免陷入局部最優(yōu)，使得采樣集中的元素向更多路勁搜索，并利用特赦準側(cè)釋放性能良好的被禁元素，最終實現(xiàn)全局優(yōu)化。

在t時刻采樣集Lt利用TS尋優(yōu)濾波方法優(yōu)化濾波過程如下：

(4)

式(4)中，N(0,1)是均值為0，方差為1的正態(tài)隨機數(shù)。若新產(chǎn)生的領(lǐng)域元素集中的元素與禁忌表中有重復，則重新產(chǎn)生領(lǐng)域元素集，避免迂回搜索。上式表明，權(quán)值較大的元素領(lǐng)域范圍小，權(quán)值較小的元素領(lǐng)域范圍大，產(chǎn)生的元素集更合理有效；

5)判斷該元素是否滿足終止條件，若滿足，進行下一步,否則返回步驟2)。

終止條件:

(5)

式(5)中，U(0,1)表示[0,1]均勻分布的隨機數(shù)；

算法最后得出最優(yōu)或近似最優(yōu)值即為要計算的當前t時刻的p(lt|ot)值。

綜上所述，TS濾波算法通過建立禁忌表實現(xiàn)對局部極值一定時間的鎖定，不會陷入局部極值，從而實現(xiàn)向其他路徑搜索，最終依靠特赦準則釋放優(yōu)良元素，通過迭代實現(xiàn)步步接近最優(yōu)值，從而實現(xiàn)全局最優(yōu)化。這樣的搜索過程既不會遺漏優(yōu)化值，又能提高搜索效率。

算法流程如圖2所示。

圖2 禁忌搜索尋優(yōu)濾波流程圖

3.4 重要性采樣及定位

重要性采樣是將節(jié)點位置采樣值通過標準化重要性采樣函數(shù)π獲得，并調(diào)整這些相互獨立的節(jié)點采樣值的權(quán)重值，利用權(quán)重值對節(jié)點可能位置作出后驗概率分布估計。具體運用了如下遞歸式的重要性函數(shù)。

(6)

(7)

(8)

(9)

(10)

4 仿真性能分析

為了評估TS-MCL算法性能，我們對算法收斂性、樣本集數(shù)量、計算時間、定位精度進行仿真測評。這里我們采用均方根誤差(RMSE)來衡量定位算法的誤差。

(11)

式(11)中，x、y代表被測量點的橫、縱坐標的真實值，x′、y′代表被測量點的橫、縱坐標的測量值。

仿真環(huán)境設(shè)置錨節(jié)點通信半徑為1 000 m，區(qū)域內(nèi)有40個移動節(jié)點，移動節(jié)點移動速度不大于50 m/s，移動節(jié)點能接收到兩個錨節(jié)點的位置信息。則TS-MCL算法的收斂狀況如圖3所示。

圖3 算法收斂性證明

其中縱坐標代表TS-MCL算法定位誤差，橫坐標代表TS-MCL算法的迭代次數(shù)，由仿真圖可知，在0～50步迭代過程中算法誤差下降較快，100步之后，算法誤差下降趨于平穩(wěn)，誤差測量值約為5 m，算法整體趨于收斂。

仿真環(huán)境參數(shù)設(shè)置仍如上所述，圖4描述了TS-MCL算法在不同樣本數(shù)量情況下，定位誤差的變化情況。

圖4 定位誤差受樣本數(shù)量的影響

圖中橫坐標代表樣本數(shù)量，縱坐標代表均方根誤差。由圖可知，TS-MCL算法在1～8個樣本數(shù)時定位誤差急劇下降，之后誤差趨于平穩(wěn)，得出采樣樣本數(shù)量占總體樣本數(shù)的20%時，算法即可達到一定誤差范圍內(nèi)的定位，與傳統(tǒng)MCL算法比較，采樣樣本數(shù)量大幅減少。

圖5描述了傳統(tǒng)MCL算法與TS-MCL算法在不同迭代次數(shù)的情況下定位時間的對比。

圖5 TS-MCL算法與MCL算法定位時間對比

其中橫坐標為迭代次數(shù)，縱坐標代表定位時間。由圖可知，TS-MCL算法在相同迭代次數(shù)下，相較于傳統(tǒng)MCL算法定位時間減少30%以上，這是因為TS-MCL算法在尋優(yōu)濾波和重采樣定位階段計算量大大減小，導致算法整體計算時間縮短。

圖6描述了在錨節(jié)點通信半徑不同的情形下傳統(tǒng)MCL算法與TS-MCL算法兩種定位算法定位誤差的對比。仿真條件設(shè)定移動節(jié)點能夠接受到兩個錨節(jié)點的位置信息。

圖6 TS-MCL算法與MCL算法定位誤差比較

圖6中橫坐標代表錨節(jié)點的通信半徑，縱坐標代表均方根誤差。從圖中可以看出，由于錨節(jié)點通信半徑增大，定位精度都會下降，但同等通信半徑條件下TS-MCL算法定位精度較傳統(tǒng)MCL算法提高了10%以上。

5 總結(jié)

本文通過在濾波階段引入禁忌搜索算法對傳統(tǒng)MCL算法進行改進，仿真結(jié)果表明改進后的算法與傳統(tǒng)MCL算法相比較在樣本采集數(shù)、計算時間、定位精度等方面有了顯著提升，改進后的算法能更好地解決車聯(lián)網(wǎng)的定位問題。

[1] 孫友偉,溫雙濤．基于電力線通信的新型物聯(lián)網(wǎng)架構(gòu)[J]．西安郵電大學學報,2014,19(3):43-48.

[2] Sheu J P,Hu W K,Lin J C.Distributed localization scheme for mobile sensor networks[J].IEEE Transactions on Mobile Computing,2010,9(4):510-512.

[3] 董振中.無線傳感器網(wǎng)絡(luò)無需測距的高效定位算法的研究[D].合肥:中國科學技術(shù)大學,2010:23-26.

[4] 孫友偉.現(xiàn)代通信新技術(shù)新業(yè)務[M].北京：北京郵電大學出版社,2004.

[5] 梅 舉,陳 滌,辛 玲.基于蒙特卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法[J].傳感技術(shù)學報,2013,26(05):689-694.

[6] 孔凡天.無線傳感器網(wǎng)絡(luò)節(jié)點定位與數(shù)據(jù)融合技術(shù)研究及實現(xiàn)[D].武漢:華中科技大學, 2006 .

[7] 朱海平,于紅丞,鐘小勇,等.動態(tài)無線傳感器網(wǎng)絡(luò)的改進蒙特卡洛定位算法[J].傳感技術(shù)學報,2012,25(9):1284-1288.

[8] 張玉芳,薛青松,熊忠陽.基于禁忌搜索的動態(tài)粒子群算法[J].計算機工程與應用,2008,44(24):56-58.

[9] 劉文文,宋國治,孫學梅,等.基于捕食搜索策略MCL算法的蜂窩網(wǎng)移動終端定位問題的研究[J].小型微型計算機系統(tǒng),2015,36(1):54-59.

[10] 喬 峰,王思民.基于MCL算法的無線傳感網(wǎng)絡(luò)節(jié)點定位技術(shù)[J].山西電子技術(shù),2009(03):63-64.

[11] 王 龍,夏厚培.禁忌搜索粒子濾波算法在目標跟蹤中的應用[J].科學技術(shù)與工程,2013,13(06):1630-1634.

[12] Boer S Y,Driessen J N. Interacting multiple model particle filter[J].IEE Proc. of RadarSonar Navigation,2003,150(5):334-349.

A Monte Carlo Localization Algorithm Based on Tabu Search in Car Networking

Sun Youwei, Wang Chenghuan,Zhang Jing

(School of Communication and Information Engineering, Xi′an University of Posts and Telecommunications, Xi′an 710121, China)

Tabu search algorithm is introduced in Monte Carlo localization algorithm to improve the car networking quickly locate performance.Ad-hoc car networking vehicles moving at high speed and network topology rapidly changing,the use of traditional Monte Carlo localization algorithm,can not quickly converge location information.Tabu search algorithm is introduced in the filtering stage of the traditional Monte Carlo localization algorithm to filter optimization and exclude the small possibility points, to obtain approximate optimal sample set of the estimated position.Simulation results show that the improved algorithm in the number of sample collection,computation time,positioning precision,has been significantly improved,the improved algorithm can better solve the positioning of car networking.

MCL;tabu search algorithm;car networking;independent of distance;positioning

2016-01-05；

2016-01-20。

孫友偉(1956-)，男，陜西西安人，教授，碩士研究生導師，主要從事下一代通信網(wǎng)方向的研究。

1671-4598(2016)06-0240-04

10.16526/j.cnki.11-4762/tp.2016.06.066

TN913.6

A