基于WSN节点定位与道路方位信息的地图匹配改进算法

杨绍恭,伍彩琴,董国芳

(1.云南文化艺术职业学院学生处,云南昆明 650111;2.云南民族大学电气信息工程学院无线传感器网络重点实验室,云南昆明 650500)

基于WSN节点定位与道路方位信息的地图匹配改进算法

杨绍恭1,伍彩琴2,董国芳2

(1.云南文化艺术职业学院学生处,云南昆明 650111;2.云南民族大学电气信息工程学院无线传感器网络重点实验室,云南昆明 650500)

全球定位系统具有高精度、低成本、实时性好等优点,但由于市区卫星信号容易受遮挡,GPS无法有效发挥作用,因此结合无线传感网络节点定位技术,可以提高地图匹配算法的匹配精度.根据航向角、道路倾角以及定位点到候选路段的距离等信息,对车辆导航系统中的地图匹配算法进行分析研究,在已有权重算法的基础上,提出一种基于方位信息度地图匹配的改进算法,并利用MATLAB环境下进行仿真实现.

WSN节点;定位;GPS;方位信息度;地图匹配

与 GPS定位相比,基于无线定位的技术可以给用户提供很多方便.地图匹配算法中,当车辆经过隧道、桥洞等较隐蔽地段时,可在车辆上安装无线传感器节点,利用无线传感器网络成熟的节点定位技术进行定位,弥补 GPS定位中的不足,也可提高定位精度,进而提高地图匹配算法中的匹配精度.

作为一种基于软件技术的定位修正方法,地图匹配 (Map-Matching,MM)算法的基本思想是将车辆定位轨迹与数字地图中的道路网络信息联系起来,并由此相对于地图确定车辆的位置.就权重法算法而言,仍然可以利用定位点距候选路段的投影距离、定位点行驶方向与候选路段方向的夹角等信息,讨论权重分配,从而对地图匹配算法作一些改进.

1 算法的设计

1.1 基于无线传感器的车载定位

将无线定位技术应用与车载定位,可以实现城市交通系统的智能化,也可以弥补 GPS定位的一些缺点.可利用部署在汽车上的移动节点,和部署在高楼、广告牌、路灯等固定设施上的固定节点充当锚节点 (信标节点)[1].锚节点每个固定周期发送包含自身位置信息的广播信号,用于车辆上的移动节点定位,然后将定位信息传回给锚节点,锚节点再将位置信息送给信息管理中心进行集中管理,再将此位置信息用于地图匹配算法中.

文献[2]中将无线传感器、里程仪和 GPS定位系统整合,利用三者信息融合,解决了 GPS无法定位时的车辆定位问题,能有效降低系统营运成本、改善交通路况信息服务效果.

当 GPS定位信息可用时,无线传感器可处于休眠节能状态.将两种定位方式结合,可有效提高定位覆盖率,进而提升地图匹配算法的匹配度.

1.2 确定误差区域

通常采用文献[3]中根据概率准则定义误差椭圆的办法确定误差区域.对采用伪距定位测量方式的 GPS接收机,由于在定位求解的过程中,包含了统计误差参数,因此,实际应用中这些参数可以方便地从接收机输出电文中获得.见图 1.

假设系统的方差、协方差矩阵模型为

式中,σx和σy是 GPS测量误差的标准差;σ2x和σ2y是方差,σxy和σyx是协方差,则

式中,a、b是误差椭圆的长、短轴;δ^0是单位权值的后验方差 (扩展因子).误差区域通常乘上扩展因子,因为除了 GPS误差外,可能还存在其他不确定的误差,如测量误差、处理误差、数字地图误差等,所以扩大误差区域是必要的.可以调整椭圆的大小以表示不同的可信度:在二维情况下,δ^0=2.15时,可得 95%的可信度,此时 GPS接收机的水平误差约为 100m,满足车辆定位时对 GPS接收机可信度的最低要求 90%.

1.3 确定匹配路段的信息

1.3.1 利用定位点到候选路段的投影距离信息

定位点 P到路段 Li的距离为 di(见图2).计算投影距离,比较后知 dimin,如此可认为此投影点是目前车辆所在位置点[4].在数字地图中弧线是用折线段代替表示的,所以对于地图上任意形状的路线,都可以进行投影.

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

航向角φ应该和道路倾斜角β不应有过大偏差,因此,比较航向角φ和道路倾斜角β,令见图3.当θ=θmin时,认定轨迹同该路段有最大相似性,可以进行投影匹配.

1.4 匹配路段确定方法的改进

式中,Fi(d,θ)为候选路段的匹配度量函数,α和(1-α)分别为 d和θ在匹配度函数中的权重,可最新约定:直线路段 (α =2/3);非直线路段 (α =1/3).而分别为第 i条候选路段所对应的投影距离和方向夹角的权重均值.

式中,n为匹配候选路段数;di和θi分别为第 i条匹配候选路段所对应的 d和θ.

2 地图匹配算法的实现过程及流程

2.1 算法的实现过程

1)获取 GPS定位数据;

2)确定误差区域;

3)判断误差区域内是否有节点,若没有,认为其轨迹是 1条直线,α =2/3,即表达式然后可以转向 7);

4)判断定位点是否进入判断域,若否,认为轨迹是 1条直线,α =2/3,即表达式然后可以转向 7);

5)根据拓扑结构,与该节点相连的路段为待匹配路段;

7)比较 Fi的大小,取其中的 Fimin进行匹配;

8)垂直投影并将匹配结果显示于电子地图.

2.2 算法流程图

算法流程见图4.

3 算法的仿真实现

基于前面的讨论,使用仿真工具对地图匹配算法进行仿真分析,用虚拟的方式实现地图匹配算法,从而验证算法在的有效性.输入假设的路段和定位点信息,并利用Matlab R2007a进行仿真[6],采用 50m ×50 m的网格来近似地图上的这部分道路 (见图5).

其中,交叉直线为候选道路,“＊”为虚拟的定位轨迹,“o”为基于地图匹配算法仿真后车辆轨迹.在节点处,如果出现匹配点不连续的情形,则可采用数学方法加以修正,使前后不同路段上的匹配点形成连续的轨迹.

4 结语

本文结合无线传感器节点定位技术,充分利用方位信息,并在不同的路段给予不同的权重;在设计算法流程时,尽量简洁明了,尽量考虑地图匹配算法的实时性和鲁棒性.同时,对定位点投影时,节点处可能没有匹配点,出现不连续的情况,根据拓扑结构用数学的方法加以修正,补充匹配点,使匹配轨迹连续.总之,该算法详细介绍了如何利用道路倾角和航向角的差的绝对值进行比较,为候选路段的选择奠定基础.在地图匹配过程中,只有匹配路段选择正确,才能实现匹配精度的提高.

此思想也可应用于无线传感器网络特定监测环境下的节点定位算法中,如节点进行环境监测、医疗护理时,由于环境因素,节点处于不规则运动状态,可事先将地理环境根据一定的规律划分,标号,再利用地理匹配算法对传感器节点进行定位.结合本文提出的方位信息也可用于传感器网络中路由限制洪泛机制,利用方位、距离等地理信息来指导和限制路由洪泛,界定洪泛路由搜索区域,能够大大提高搜索的方向性和有效性.

目前,对无线传感器网络定位机制研究成果已经比较成熟,在某些环境下,也可与导航系统中所用的GPS定位相辅相成,为现有的导航方法提供一些补充.

[1]梁甲金,邓平.一种基于移动锚节点的多坐标系定位算法[J].云南民族大学学报:自然科学版,2010,19(4):248-252.

[2]曾庆化,刘建业,赵飞,等.基于 GPS和无线传感器的智能交通系统[J].全球定位系统,2009(05):34-38.

[3]赵亦林,谭国真.车辆定位与导航系统 [M].北京:电子工业出版社,1999.

[4]张宏,温永宁.地理信息系统算法基础 [M].北京:科学出版社,2006.

[5]张振辉.车辆导航中地图匹配算法与应用研究[D].郑州:解放军信息工程大学,2006.

[6]周品,赵新芬.MATLAB数学建模与仿真 [M].北京:国防工业出版社,2009.

(责任编辑庄红林)

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.

云南省教育厅科学研究基金 (09Y0256).

杨绍恭 (1973-),男,硕士,讲师.主要研究方向:车辆导航.