孫友偉，王辰寰，張 晶

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

?

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

孫友偉，王辰寰，張 晶

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

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

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

0 引言

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

1 提出問題

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

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

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

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

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

(1)

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

(2)

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

3 TS-MCL算法描述

3.1 位置初始化

3.1.1 初始化

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

圖1 移動(dòng)節(jié)點(diǎn)估測(cè)范圍

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

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

3.1.2 循環(huán)計(jì)算

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

初始位置確定后，每間隔一定時(shí)間通過移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)情況和新的觀測(cè)信息對(duì)移動(dòng)節(jié)點(diǎn)的位置序列進(jìn)行位置更新。

3.2 位置預(yù)測(cè)

(3)

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

3.3 TS尋優(yōu)濾波

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

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

(4)

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

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

終止條件:

(5)

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

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

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

算法流程如圖2所示。

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

3.4 重要性采樣及定位

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

(6)

(7)

(8)

(9)

(10)

4 仿真性能分析

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

(11)

式(11)中，x、y代表被測(cè)量點(diǎn)的橫、縱坐標(biāo)的真實(shí)值，x′、y′代表被測(cè)量點(diǎn)的橫、縱坐標(biāo)的測(cè)量值。

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

圖3 算法收斂性證明

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

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

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

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

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

圖5 TS-MCL算法與MCL算法定位時(shí)間對(duì)比

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

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

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

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

5 總結(jié)

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

[1] 孫友偉,溫雙濤．基于電力線通信的新型物聯(lián)網(wǎng)架構(gòu)[J]．西安郵電大學(xué)學(xué)報(bào),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ò)無需測(cè)距的高效定位算法的研究[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2010:23-26.

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

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

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

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

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

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

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

[11] 王 龍,夏厚培.禁忌搜索粒子濾波算法在目標(biāo)跟蹤中的應(yīng)用[J].科學(xué)技術(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-)，男，陜西西安人，教授，碩士研究生導(dǎo)師，主要從事下一代通信網(wǎng)方向的研究。

1671-4598(2016)06-0240-04

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

TN913.6

A