基于WSN節(jié)點定位與道路方位信息的地圖匹配改進(jìn)算法

楊紹恭,伍彩琴,董國芳

(1.云南文化藝術(shù)職業(yè)學(xué)院學(xué)生處,云南昆明 650111;2.云南民族大學(xué)電氣信息工程學(xué)院無線傳感器網(wǎng)絡(luò)重點實驗室,云南昆明 650500)

基于WSN節(jié)點定位與道路方位信息的地圖匹配改進(jìn)算法

楊紹恭1,伍彩琴2,董國芳2

(1.云南文化藝術(shù)職業(yè)學(xué)院學(xué)生處,云南昆明 650111;2.云南民族大學(xué)電氣信息工程學(xué)院無線傳感器網(wǎng)絡(luò)重點實驗室,云南昆明 650500)

全球定位系統(tǒng)具有高精度、低成本、實時性好等優(yōu)點,但由于市區(qū)衛(wèi)星信號容易受遮擋,GPS無法有效發(fā)揮作用,因此結(jié)合無線傳感網(wǎng)絡(luò)節(jié)點定位技術(shù),可以提高地圖匹配算法的匹配精度.根據(jù)航向角、道路傾角以及定位點到候選路段的距離等信息,對車輛導(dǎo)航系統(tǒng)中的地圖匹配算法進(jìn)行分析研究,在已有權(quán)重算法的基礎(chǔ)上,提出一種基于方位信息度地圖匹配的改進(jìn)算法,并利用MATLAB環(huán)境下進(jìn)行仿真實現(xiàn).

WSN節(jié)點;定位;GPS;方位信息度;地圖匹配

與 GPS定位相比,基于無線定位的技術(shù)可以給用戶提供很多方便.地圖匹配算法中,當(dāng)車輛經(jīng)過隧道、橋洞等較隱蔽地段時,可在車輛上安裝無線傳感器節(jié)點,利用無線傳感器網(wǎng)絡(luò)成熟的節(jié)點定位技術(shù)進(jìn)行定位,彌補(bǔ) GPS定位中的不足,也可提高定位精度,進(jìn)而提高地圖匹配算法中的匹配精度.

作為一種基于軟件技術(shù)的定位修正方法,地圖匹配 (Map-Matching,MM)算法的基本思想是將車輛定位軌跡與數(shù)字地圖中的道路網(wǎng)絡(luò)信息聯(lián)系起來,并由此相對于地圖確定車輛的位置.就權(quán)重法算法而言,仍然可以利用定位點距候選路段的投影距離、定位點行駛方向與候選路段方向的夾角等信息,討論權(quán)重分配,從而對地圖匹配算法作一些改進(jìn).

1 算法的設(shè)計

1.1 基于無線傳感器的車載定位

將無線定位技術(shù)應(yīng)用與車載定位,可以實現(xiàn)城市交通系統(tǒng)的智能化,也可以彌補(bǔ) GPS定位的一些缺點.可利用部署在汽車上的移動節(jié)點,和部署在高樓、廣告牌、路燈等固定設(shè)施上的固定節(jié)點充當(dāng)錨節(jié)點 (信標(biāo)節(jié)點)[1].錨節(jié)點每個固定周期發(fā)送包含自身位置信息的廣播信號,用于車輛上的移動節(jié)點定位,然后將定位信息傳回給錨節(jié)點,錨節(jié)點再將位置信息送給信息管理中心進(jìn)行集中管理,再將此位置信息用于地圖匹配算法中.

文獻(xiàn)[2]中將無線傳感器、里程儀和 GPS定位系統(tǒng)整合,利用三者信息融合,解決了 GPS無法定位時的車輛定位問題,能有效降低系統(tǒng)營運成本、改善交通路況信息服務(wù)效果.

當(dāng) GPS定位信息可用時,無線傳感器可處于休眠節(jié)能狀態(tài).將兩種定位方式結(jié)合,可有效提高定位覆蓋率,進(jìn)而提升地圖匹配算法的匹配度.

1.2 確定誤差區(qū)域

通常采用文獻(xiàn)[3]中根據(jù)概率準(zhǔn)則定義誤差橢圓的辦法確定誤差區(qū)域.對采用偽距定位測量方式的 GPS接收機(jī),由于在定位求解的過程中,包含了統(tǒng)計誤差參數(shù),因此,實際應(yīng)用中這些參數(shù)可以方便地從接收機(jī)輸出電文中獲得.見圖 1.

假設(shè)系統(tǒng)的方差、協(xié)方差矩陣模型為

式中,σx和σy是 GPS測量誤差的標(biāo)準(zhǔn)差;σ2x和σ2y是方差,σxy和σyx是協(xié)方差,則

式中,a、b是誤差橢圓的長、短軸;δ^0是單位權(quán)值的后驗方差 (擴(kuò)展因子).誤差區(qū)域通常乘上擴(kuò)展因子,因為除了 GPS誤差外,可能還存在其他不確定的誤差,如測量誤差、處理誤差、數(shù)字地圖誤差等,所以擴(kuò)大誤差區(qū)域是必要的.可以調(diào)整橢圓的大小以表示不同的可信度:在二維情況下,δ^0=2.15時,可得 95%的可信度,此時 GPS接收機(jī)的水平誤差約為 100m,滿足車輛定位時對 GPS接收機(jī)可信度的最低要求 90%.

1.3 確定匹配路段的信息

1.3.1 利用定位點到候選路段的投影距離信息

定位點 P到路段 Li的距離為 di(見圖2).計算投影距離,比較后知 dimin,如此可認(rèn)為此投影點是目前車輛所在位置點[4].在數(shù)字地圖中弧線是用折線段代替表示的,所以對于地圖上任意形狀的路線,都可以進(jìn)行投影.

1.3.2 利用航向角和道路傾斜角信息

航向角φ應(yīng)該和道路傾斜角β不應(yīng)有過大偏差,因此,比較航向角φ和道路傾斜角β,令見圖3.當(dāng)θ=θmin時,認(rèn)定軌跡同該路段有最大相似性,可以進(jìn)行投影匹配.

1.4 匹配路段確定方法的改進(jìn)

式中,Fi(d,θ)為候選路段的匹配度量函數(shù),α和(1-α)分別為 d和θ在匹配度函數(shù)中的權(quán)重,可最新約定:直線路段 (α =2/3);非直線路段 (α =1/3).而分別為第 i條候選路段所對應(yīng)的投影距離和方向夾角的權(quán)重均值.

式中,n為匹配候選路段數(shù);di和θi分別為第 i條匹配候選路段所對應(yīng)的 d和θ.

2 地圖匹配算法的實現(xiàn)過程及流程

2.1 算法的實現(xiàn)過程

1)獲取 GPS定位數(shù)據(jù);

2)確定誤差區(qū)域;

3)判斷誤差區(qū)域內(nèi)是否有節(jié)點,若沒有,認(rèn)為其軌跡是 1條直線,α =2/3,即表達(dá)式然后可以轉(zhuǎn)向 7);

4)判斷定位點是否進(jìn)入判斷域,若否,認(rèn)為軌跡是 1條直線,α =2/3,即表達(dá)式然后可以轉(zhuǎn)向 7);

5)根據(jù)拓?fù)浣Y(jié)構(gòu),與該節(jié)點相連的路段為待匹配路段;

7)比較 Fi的大小,取其中的 Fimin進(jìn)行匹配;

8)垂直投影并將匹配結(jié)果顯示于電子地圖.

2.2 算法流程圖

算法流程見圖4.

3 算法的仿真實現(xiàn)

基于前面的討論,使用仿真工具對地圖匹配算法進(jìn)行仿真分析,用虛擬的方式實現(xiàn)地圖匹配算法,從而驗證算法在的有效性.輸入假設(shè)的路段和定位點信息,并利用Matlab R2007a進(jìn)行仿真[6],采用 50m ×50 m的網(wǎng)格來近似地圖上的這部分道路 (見圖5).

其中,交叉直線為候選道路,“＊”為虛擬的定位軌跡,“o”為基于地圖匹配算法仿真后車輛軌跡.在節(jié)點處,如果出現(xiàn)匹配點不連續(xù)的情形,則可采用數(shù)學(xué)方法加以修正,使前后不同路段上的匹配點形成連續(xù)的軌跡.

4 結(jié)語

本文結(jié)合無線傳感器節(jié)點定位技術(shù),充分利用方位信息,并在不同的路段給予不同的權(quán)重;在設(shè)計算法流程時,盡量簡潔明了,盡量考慮地圖匹配算法的實時性和魯棒性.同時,對定位點投影時,節(jié)點處可能沒有匹配點,出現(xiàn)不連續(xù)的情況,根據(jù)拓?fù)浣Y(jié)構(gòu)用數(shù)學(xué)的方法加以修正,補(bǔ)充匹配點,使匹配軌跡連續(xù).總之,該算法詳細(xì)介紹了如何利用道路傾角和航向角的差的絕對值進(jìn)行比較,為候選路段的選擇奠定基礎(chǔ).在地圖匹配過程中,只有匹配路段選擇正確,才能實現(xiàn)匹配精度的提高.

此思想也可應(yīng)用于無線傳感器網(wǎng)絡(luò)特定監(jiān)測環(huán)境下的節(jié)點定位算法中,如節(jié)點進(jìn)行環(huán)境監(jiān)測、醫(yī)療護(hù)理時,由于環(huán)境因素,節(jié)點處于不規(guī)則運動狀態(tài),可事先將地理環(huán)境根據(jù)一定的規(guī)律劃分,標(biāo)號,再利用地理匹配算法對傳感器節(jié)點進(jìn)行定位.結(jié)合本文提出的方位信息也可用于傳感器網(wǎng)絡(luò)中路由限制洪泛機(jī)制,利用方位、距離等地理信息來指導(dǎo)和限制路由洪泛,界定洪泛路由搜索區(qū)域,能夠大大提高搜索的方向性和有效性.

目前,對無線傳感器網(wǎng)絡(luò)定位機(jī)制研究成果已經(jīng)比較成熟,在某些環(huán)境下,也可與導(dǎo)航系統(tǒng)中所用的GPS定位相輔相成,為現(xiàn)有的導(dǎo)航方法提供一些補(bǔ)充.

[1]梁甲金,鄧平.一種基于移動錨節(jié)點的多坐標(biāo)系定位算法[J].云南民族大學(xué)學(xué)報:自然科學(xué)版,2010,19(4):248-252.

[2]曾慶化,劉建業(yè),趙飛,等.基于 GPS和無線傳感器的智能交通系統(tǒng)[J].全球定位系統(tǒng),2009(05):34-38.

[3]趙亦林,譚國真.車輛定位與導(dǎo)航系統(tǒng) [M].北京:電子工業(yè)出版社,1999.

[4]張宏,溫永寧.地理信息系統(tǒng)算法基礎(chǔ) [M].北京:科學(xué)出版社,2006.

[5]張振輝.車輛導(dǎo)航中地圖匹配算法與應(yīng)用研究[D].鄭州:解放軍信息工程大學(xué),2006.

[6]周品,趙新芬.MATLAB數(shù)學(xué)建模與仿真 [M].北京:國防工業(yè)出版社,2009.

(責(zé)任編輯莊紅林)

Improvement of the Map-Matching Algorithm Based on WSN Localization Algorithm and Bearing Information

YANG Shao-gong1,WU Cai-qin2,DONG Guo-fang2
(1.StudentsAffairsDivision,Yunnan Vocational College for Culture&Arts,Kunming 650111,China;2.KeyLab onW ireless SensorNetwork Technology,School of Electrical and Information Technology,Yunnan University ofNationalities,Kunming 650500,China)

The global positioning system GPS has many merits such as high precision,real-time,low-cost,etc.,but it is hard for GPS signal to work in the urban environment where satellite signal is blocked.This paper analyzes the map-matching algorithm in the system of VNS and concludes that the technique of the wireless networks node of localization algorithm can help perfect the GPS by improving the matching accuracy of the mapmatching algorithm according to the information for the angle course,the dip angle of the road and the distance from the present position to the target road.Based on the previous studies on the weight degree of bearing infor mation,the paper presents an improvementof themap-matching algorithm on bearing infor mation and carriesout the s imulation studies in the condition ofMatlab.

WSN node;localization;GPS;degree of bearing infor mation;map-matching

TP 393.03

A

1672-8513(2011)01-0050-03

10.3969/j.issn.1672-8513.2011.01.012

2010-10-27.

云南省教育廳科學(xué)研究基金 (09Y0256).

楊紹恭 (1973-),男,碩士,講師.主要研究方向:車輛導(dǎo)航.