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

楊紹恭,伍彩琴,董國(guó)芳

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

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

楊紹恭1,伍彩琴2,董國(guó)芳2

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

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

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

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

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

1 算法的設(shè)計(jì)

1.1 基于無(wú)線傳感器的車載定位

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

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

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

1.2 確定誤差區(qū)域

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

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

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

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

1.3 確定匹配路段的信息

1.3.1 利用定位點(diǎn)到候選路段的投影距離信息

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

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

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

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

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

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

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

2.1 算法的實(shí)現(xiàn)過(guò)程

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

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

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

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

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

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

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

2.2 算法流程圖

算法流程見(jiàn)圖4.

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

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

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

4 結(jié)語(yǔ)

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

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

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

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

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

[3]趙亦林,譚國(guó)真.車輛定位與導(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].北京:國(guó)防工業(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)航.