LBS中基于GIS的二次定位和位置预测算法的研究与实现
摘要
本文首先针对位置服务中的移动定位技术进行了深入的研究。目前,由于定位技术和电子地图存在定位精度不同,导致无线定位或GPS的一次定位数据在直接匹配到电子地图上时的不准确,在一定程度上给我们造成不便,所以当前部分基于位置服务的业务需要进行二次地图匹配定位,来纠正一次定位存在的误差。
本文对目前LBS中地图匹配算法进行了研究和比较,引进了基于GIS缓冲区的自适应模糊决策地图匹配算法,并在此基础之上对其进行改进和实现;地图匹配算法将待匹配道路信息存储在GIS缓冲区中,对当前候选匹配路段进行判定时,引入了前序待匹配道路的判定信息,使得算法在道路交叉、分布密集的区域仍能够达到很高的精确性。
同时,考虑到当受到外界条件(比如天气,隧道,涵洞等)干扰的情况下,服务器接受不到定位数据信息,从而无法提供给用户定位服务;鉴于此种情况,我们引进位置预测算法作为辅助定位模块,位置预测算法借助BP神经网络和时间序列来估算车辆行驶轨迹,因为车辆GPS信号失效的时间很短,所以本文所介绍的预测算法在一定程度上能根据历史的信息较准确的估计出物体行使的位置。
最后,本文给出了定位服务模块中地图匹配算法和位置预测算法的设计和实现,并验证了算法的有效性。
LBS(Location-based services)are based on the geographical location of data in services.With the development of society,the scope of activities of the people is increasingly becoming more and more uncertain.The mobile and uncertainty brought market and challenges for the mobile communications,as well as,brought unlimited business opportunities for Location Based Service.Thus,the value-added business based on LBS will be the great development.However,some of the business needed the positioning accuracy are bound to have more precise requirements to bottom positioning data,such as navigation and positioning based the mobile location,vehicle tracking and location enquiries and so on.At present, however,the positioning technology we generally used can not solve the problem fundamentally,this requires us to a second development,the map matching is the realization of the function,and also is the focus of the study. At the same time,taking into account the sustained positioning for GPS signal due to obstructions can not be achieved,the location prediction algorithm also is conducted in-depth research.
The paper,firstly,did a more comprehensive study to the mobile location technology in LBS.At present,due to different positioning accuracy between positioning technology and electronic map,wireless location or GPS positioning data is not accurate in direct matching the electronic map.It,to a certain extent,cause inconvenience to us,so part of the current location-based services business needs the second matching location to correct the error.The paper,considering the advantage of all existing map-matching algorithm,is given the algorithm.
The paper is based on the platform of the mobile positioning system,and do in-depth research and comparison to map-matching algorithm in LBS. Based on the consideration of continuity,real-time,accuracy in map matching,the paper introduced the self-adaptive fuzzy decision algorithm based on GIS buffer,and improved and implemented it on its original basis for the algorithm.The self-adaptive fuzzy decision algorithm based on GIS buffer is based on the following assumptions,firstly,high-precision digital map and location information;secondly,location information updated one times every second and retain it on the server;thirdly,vehicles always moving on the road.In the self-adaptive fuzzy decision algorithm based on GIS buffer,candidate matching roads information is stored in GIS buffer. When judging the matched road of the current matching point,previous candidate matching information is used to enrich the current judging information.Though the moving object in the area of road crossing point or intensive highway,the algorithm can reach high accurate still.Through self-adaptive adjusting and fuzzy decision,the algorithm advances the differentiation degree between the right road and the wrong one.We can judge the matched road immediately,so it is a real-time algorithm.The processes of selecting candidate matching roads and matching computation are almost in GIS Buffer,so the computing complexity of this algorithm is reduced.However,the algorithm did not consider the road network topology,and so can not be more accurate positioning.By using the criteria of the road topology on the basis of the original algorithm,the algorithm able to meet the matching of high precision on the complex environment of the close parallel roads and cross roads.
On the other hand,in the process of wireless location and GPS positioning,due to external conditions(such as weather,tunnels,culverts, etc.)interference,the server could accept less than GPS positioning data, which could not be provided the user with location-based services;In view of the situation,we introduced a prediction algorithm as a complementary location positioning module.This paper made lots of research for automotive navigation and positioning technology currently,such as GPS+ DR navigation system,and so on.However,the model can not be divorced from on-board equipment,and needs install some equipment in the car,such as gyroscopes which measure current speed and direction.It also can not be achieved in the mobile client and the PC client for the forecast and track.In this paper,we have analyzed the principle of the location prediction algorithm in detail,and proposed the location prediction model based on the mobile system by using for reference of their thoughts and using the model of kinematic principles benefit from the ideas and principles of using kinematic model is proposed based on the location of the system model.BP neural network is a network structure of the most widely and most mature in applications.This paper estimates the direction of the vehicle by BP network.It also is based on the error back-propagation learning algorithm, BP algorithm adjust the network weights to more accurately predict direction of the traffic movement.As the change of the speed of vehicles is not great on the road in a short period,and there is an inherent law,In order to improve the efficiency we predict the speed of vehicles using time series, and received very good results similarly.When known the speed V and the variation△θof the direction angle,we also need the location coordinates of points(X_0,Y_0)before the failure of GPS signal,so that we can estimate the vehicle location next time under the object Kinematic model.
Location prediction algorithm estimate traffic path using BP neural network and time series.It reached the requirements of the auxiliary positioning in the system,and,to a certain extent,estimated more accurately the location coordinates of objects according to its history of the information. However,due to the cumulative of the prediction process,the accumulation of calculation error,and the error of the forecast itself,the prediction System is a divergence process with the passage of time.But,in the cities,the interruption of GPS positioning signal is usually short,about a few seconds to 1 minute.Therefore,generally speaking,the error of the system is in the control.
Finally,the paper presents the design and implementation of map-matching algorithm and location prediction algorithm.We read the map information in actual environment,and simulate GPS positioning.We have analyzed the matching effect of the positioning module and auxiliary positioning module through the algorithm in this paper.Its effect is satisfactory.Of course,there are also some inadequacies in the algorithm model.We give the improvements of the algorithm model in the final.
本文对目前LBS中地图匹配算法进行了研究和比较,引进了基于GIS缓冲区的自适应模糊决策地图匹配算法,并在此基础之上对其进行改进和实现;地图匹配算法将待匹配道路信息存储在GIS缓冲区中,对当前候选匹配路段进行判定时,引入了前序待匹配道路的判定信息,使得算法在道路交叉、分布密集的区域仍能够达到很高的精确性。
同时,考虑到当受到外界条件(比如天气,隧道,涵洞等)干扰的情况下,服务器接受不到定位数据信息,从而无法提供给用户定位服务;鉴于此种情况,我们引进位置预测算法作为辅助定位模块,位置预测算法借助BP神经网络和时间序列来估算车辆行驶轨迹,因为车辆GPS信号失效的时间很短,所以本文所介绍的预测算法在一定程度上能根据历史的信息较准确的估计出物体行使的位置。
最后,本文给出了定位服务模块中地图匹配算法和位置预测算法的设计和实现,并验证了算法的有效性。
LBS(Location-based services)are based on the geographical location of data in services.With the development of society,the scope of activities of the people is increasingly becoming more and more uncertain.The mobile and uncertainty brought market and challenges for the mobile communications,as well as,brought unlimited business opportunities for Location Based Service.Thus,the value-added business based on LBS will be the great development.However,some of the business needed the positioning accuracy are bound to have more precise requirements to bottom positioning data,such as navigation and positioning based the mobile location,vehicle tracking and location enquiries and so on.At present, however,the positioning technology we generally used can not solve the problem fundamentally,this requires us to a second development,the map matching is the realization of the function,and also is the focus of the study. At the same time,taking into account the sustained positioning for GPS signal due to obstructions can not be achieved,the location prediction algorithm also is conducted in-depth research.
The paper,firstly,did a more comprehensive study to the mobile location technology in LBS.At present,due to different positioning accuracy between positioning technology and electronic map,wireless location or GPS positioning data is not accurate in direct matching the electronic map.It,to a certain extent,cause inconvenience to us,so part of the current location-based services business needs the second matching location to correct the error.The paper,considering the advantage of all existing map-matching algorithm,is given the algorithm.
The paper is based on the platform of the mobile positioning system,and do in-depth research and comparison to map-matching algorithm in LBS. Based on the consideration of continuity,real-time,accuracy in map matching,the paper introduced the self-adaptive fuzzy decision algorithm based on GIS buffer,and improved and implemented it on its original basis for the algorithm.The self-adaptive fuzzy decision algorithm based on GIS buffer is based on the following assumptions,firstly,high-precision digital map and location information;secondly,location information updated one times every second and retain it on the server;thirdly,vehicles always moving on the road.In the self-adaptive fuzzy decision algorithm based on GIS buffer,candidate matching roads information is stored in GIS buffer. When judging the matched road of the current matching point,previous candidate matching information is used to enrich the current judging information.Though the moving object in the area of road crossing point or intensive highway,the algorithm can reach high accurate still.Through self-adaptive adjusting and fuzzy decision,the algorithm advances the differentiation degree between the right road and the wrong one.We can judge the matched road immediately,so it is a real-time algorithm.The processes of selecting candidate matching roads and matching computation are almost in GIS Buffer,so the computing complexity of this algorithm is reduced.However,the algorithm did not consider the road network topology,and so can not be more accurate positioning.By using the criteria of the road topology on the basis of the original algorithm,the algorithm able to meet the matching of high precision on the complex environment of the close parallel roads and cross roads.
On the other hand,in the process of wireless location and GPS positioning,due to external conditions(such as weather,tunnels,culverts, etc.)interference,the server could accept less than GPS positioning data, which could not be provided the user with location-based services;In view of the situation,we introduced a prediction algorithm as a complementary location positioning module.This paper made lots of research for automotive navigation and positioning technology currently,such as GPS+ DR navigation system,and so on.However,the model can not be divorced from on-board equipment,and needs install some equipment in the car,such as gyroscopes which measure current speed and direction.It also can not be achieved in the mobile client and the PC client for the forecast and track.In this paper,we have analyzed the principle of the location prediction algorithm in detail,and proposed the location prediction model based on the mobile system by using for reference of their thoughts and using the model of kinematic principles benefit from the ideas and principles of using kinematic model is proposed based on the location of the system model.BP neural network is a network structure of the most widely and most mature in applications.This paper estimates the direction of the vehicle by BP network.It also is based on the error back-propagation learning algorithm, BP algorithm adjust the network weights to more accurately predict direction of the traffic movement.As the change of the speed of vehicles is not great on the road in a short period,and there is an inherent law,In order to improve the efficiency we predict the speed of vehicles using time series, and received very good results similarly.When known the speed V and the variation△θof the direction angle,we also need the location coordinates of points(X_0,Y_0)before the failure of GPS signal,so that we can estimate the vehicle location next time under the object Kinematic model.
Location prediction algorithm estimate traffic path using BP neural network and time series.It reached the requirements of the auxiliary positioning in the system,and,to a certain extent,estimated more accurately the location coordinates of objects according to its history of the information. However,due to the cumulative of the prediction process,the accumulation of calculation error,and the error of the forecast itself,the prediction System is a divergence process with the passage of time.But,in the cities,the interruption of GPS positioning signal is usually short,about a few seconds to 1 minute.Therefore,generally speaking,the error of the system is in the control.
Finally,the paper presents the design and implementation of map-matching algorithm and location prediction algorithm.We read the map information in actual environment,and simulate GPS positioning.We have analyzed the matching effect of the positioning module and auxiliary positioning module through the algorithm in this paper.Its effect is satisfactory.Of course,there are also some inadequacies in the algorithm model.We give the improvements of the algorithm model in the final.
引文
[1]童恩,位置服务实现技术及展望[J],江苏通信技术,2004.2:33-35.
[2]黄永芳,杨新勇,一种基于自适应模糊决策的车辆导航系统地图匹配算法[J],淮阴工学院学报,2004.13(1):21-23.
[3]ESRI Inc[EB/OL].http://www.esri.com/industries/locationservices/.
[4]MapInfo Corporation,MapInfo wlutepaper:Business Issues and Opportunities in Location-based Services,2002.
[5]Sun Microsystems,Inc.,Carriers Realize the Potential of Location-Based Services,2005.
[6]Openwave Systems Inc.,Openwave Location Studio WhitePaper,2002
[7]3GPP TS 22.071 V7.4.0,Location Services(LCS),Service description,Stage 1(Release 7),2005.
[8]Open Geospatial Consortium Inc,Location Services(OpenLS):Core Services version 1.1 OGC OS-016,2005.
[9]李伟章,移动数据通信技术与业务,北京:人民邮电出版社,2006.
[10]方舟咨询,移动通信市场新的增长点,通信市场,2005.
[11]孙世博,基于GPRS的GPS车辆定位系统及其证据推理地图匹配算法[J],哈尔滨工业大学上学硕士学位论文,2006.6:52-53.
[12]钟海丽,童瑞华,李军,陈宏盛,GPS定位与地图匹配方法研究[J],小型微型计算机系统,2003.24(1):109-112.
[13]高晖,常青,基于当前统计模型的地图匹配车辆跟踪研究[J],中国公路学报,2006.19(2):95-98.
[14]彭飞,柳重堪,张其善,基于代价函数的组合导航系统地图匹配算法[J],北京航空航天大学学报,2002.2A.(3):261-264.
[15]周培德,付梦印,地图匹配的新算法[J],北京理工大学学报,2004.24.(3):238-241.
[16]张文修,梁怡,小确定性推理原理[M],西安交通大学出版社,1996:20-32.
[17]Mengyin Fu,Jie Li,Meiling Wang,A hybrid map matching algorithm based on fuzzy comprehensive,Proceedings of The 7th International IEEE Conference on Intelligent Transportation Systems,2004:613-617.
[18]于兴旺,张小红等,GPS/GLONASS组合单点定位在导航中的应用[J],测绘信息与工程,2007:1-3.
[19]卫育新,GPS/INS组合导航定位定向系统研究[J],西北工业大学硕士学位论文,2004.2:56-75.
[20]杨晓云,何恒,施浒立,车辆GPS/DR组合导航系统研究[J],测绘通报,2007年第9期:1-4.
[21]Vu Thi Hong Nhan,Keun Ho Ryu,Future Location Prediction of Moving Objects Based on Movement Rules[M],Springer Berlin/Heidelberg,2006.
[22]Tong Liu,Paramvir Bahl,ImrichChlamtac,Mobility Modeling,Location Tracking and Trajectory Prediction in Wireless ATM Networks,IEEE Journal on Selected Areas in Communications,10(1998):922-936.
[23]安凯,马佳光,傅承毓,运动目标位置预测模型[J],系统工程与电子技术,2001.23(12):4-7.
[24]岑明,傅承毓,钟代均等,卫星跟踪中位置预测的序列匹配算法[J],光电工程,2006.33(1):24-26.
[25]齐治昌,谭庆平,宁洪著,软件工程(第二版)[M],高等教育出版社,2007.6.
[26]田朋轩,朱仲英,基于J2EE的LBS服务器平台设计[J],微型电脑应用,2005.21(2):1-16.
[27]Bennett,Simon/Skelton,John著,Schaum's Outline Of UML[M],Baker & Tayl,2005.2.
[28]刘莉华,神经网络方法在股市预测中的应用研究[J],电子科技大学硕士学位论文,2005.5:17-35.
[29]周靖,随机时间序列模型在商品国际价格预测中的适用性研究[J],西南财经大学硕士学位论文,2007.4:23-27.
[30]王博,LCS中基于GIS的二次定位算法研究[J],吉林大学硕士学位论文,2006.6:16-27.
[31]李胜乐等,MapInfo地理信息系统二次开发实例,电子工业出版社,2003.
[32]袁博,邵进达,地理信息系统基础与实践(21世纪高等学校规划教材)[M],国防工业出版社,2003.
[33]陈则工,袁信,GIS在车辆定位导航系统中的应用[J],微型电脑应用,2002.18(9):28-29.
[34]王文川,面向车载导航的嵌入式GIS研究与实现[J],南京航空航天大学硕士学位论文,2005.1:6-29.
[35]Sinn Kim,Jong-Hwan Kim,Adaptive Fuzzy-network-based C-measure Map-matching Algorithm for Car Navigation System [J],IEEE Transactions on Industrial Electronics,2001,(4).
[36]Sinn Kim,et al,Q-facter Map Matching Method Using Adaptive Fuzzy Network[C],IEEE International Fuzzy Systems Conference Proceedings,1999.
[37]Tomohiro Takagi,M.Sugeno,Fuzzy Identification of System and Its Application to Modeling and Control,IEEE Trans.Syst,Man and Cybern,1985,15(1).
[38]ManSheng Zhang,et al,A new self-adaptive Kalman filtering method for GPS kinematic positioning,Journal of Central South University of Technology 2003,34(5).
[39]Daglic,Schierholt K.,Stock Market Prediction Using Different Neural Network Classification Architectures.IEEE/IAFE 1996 Conference on Computatinal Intelligence for Financial Engineering,1996,8(3):72-78.
[40]师智斌,陈立潮,靳雁霞,基于神经网络的股票交易数据的预测研究[J],华北土学院学报,2003.34(6):12-16.
[41]Apostolos Nicholas Refenes,Achileas Zapranis,Gavin Francis,Stock Performance Modeling Using Neural Networks:A Comparative Study with Regression Models.Neural Networks,1994:7(2):375-388.
[2]黄永芳,杨新勇,一种基于自适应模糊决策的车辆导航系统地图匹配算法[J],淮阴工学院学报,2004.13(1):21-23.
[3]ESRI Inc[EB/OL].http://www.esri.com/industries/locationservices/.
[4]MapInfo Corporation,MapInfo wlutepaper:Business Issues and Opportunities in Location-based Services,2002.
[5]Sun Microsystems,Inc.,Carriers Realize the Potential of Location-Based Services,2005.
[6]Openwave Systems Inc.,Openwave Location Studio WhitePaper,2002
[7]3GPP TS 22.071 V7.4.0,Location Services(LCS),Service description,Stage 1(Release 7),2005.
[8]Open Geospatial Consortium Inc,Location Services(OpenLS):Core Services version 1.1 OGC OS-016,2005.
[9]李伟章,移动数据通信技术与业务,北京:人民邮电出版社,2006.
[10]方舟咨询,移动通信市场新的增长点,通信市场,2005.
[11]孙世博,基于GPRS的GPS车辆定位系统及其证据推理地图匹配算法[J],哈尔滨工业大学上学硕士学位论文,2006.6:52-53.
[12]钟海丽,童瑞华,李军,陈宏盛,GPS定位与地图匹配方法研究[J],小型微型计算机系统,2003.24(1):109-112.
[13]高晖,常青,基于当前统计模型的地图匹配车辆跟踪研究[J],中国公路学报,2006.19(2):95-98.
[14]彭飞,柳重堪,张其善,基于代价函数的组合导航系统地图匹配算法[J],北京航空航天大学学报,2002.2A.(3):261-264.
[15]周培德,付梦印,地图匹配的新算法[J],北京理工大学学报,2004.24.(3):238-241.
[16]张文修,梁怡,小确定性推理原理[M],西安交通大学出版社,1996:20-32.
[17]Mengyin Fu,Jie Li,Meiling Wang,A hybrid map matching algorithm based on fuzzy comprehensive,Proceedings of The 7th International IEEE Conference on Intelligent Transportation Systems,2004:613-617.
[18]于兴旺,张小红等,GPS/GLONASS组合单点定位在导航中的应用[J],测绘信息与工程,2007:1-3.
[19]卫育新,GPS/INS组合导航定位定向系统研究[J],西北工业大学硕士学位论文,2004.2:56-75.
[20]杨晓云,何恒,施浒立,车辆GPS/DR组合导航系统研究[J],测绘通报,2007年第9期:1-4.
[21]Vu Thi Hong Nhan,Keun Ho Ryu,Future Location Prediction of Moving Objects Based on Movement Rules[M],Springer Berlin/Heidelberg,2006.
[22]Tong Liu,Paramvir Bahl,ImrichChlamtac,Mobility Modeling,Location Tracking and Trajectory Prediction in Wireless ATM Networks,IEEE Journal on Selected Areas in Communications,10(1998):922-936.
[23]安凯,马佳光,傅承毓,运动目标位置预测模型[J],系统工程与电子技术,2001.23(12):4-7.
[24]岑明,傅承毓,钟代均等,卫星跟踪中位置预测的序列匹配算法[J],光电工程,2006.33(1):24-26.
[25]齐治昌,谭庆平,宁洪著,软件工程(第二版)[M],高等教育出版社,2007.6.
[26]田朋轩,朱仲英,基于J2EE的LBS服务器平台设计[J],微型电脑应用,2005.21(2):1-16.
[27]Bennett,Simon/Skelton,John著,Schaum's Outline Of UML[M],Baker & Tayl,2005.2.
[28]刘莉华,神经网络方法在股市预测中的应用研究[J],电子科技大学硕士学位论文,2005.5:17-35.
[29]周靖,随机时间序列模型在商品国际价格预测中的适用性研究[J],西南财经大学硕士学位论文,2007.4:23-27.
[30]王博,LCS中基于GIS的二次定位算法研究[J],吉林大学硕士学位论文,2006.6:16-27.
[31]李胜乐等,MapInfo地理信息系统二次开发实例,电子工业出版社,2003.
[32]袁博,邵进达,地理信息系统基础与实践(21世纪高等学校规划教材)[M],国防工业出版社,2003.
[33]陈则工,袁信,GIS在车辆定位导航系统中的应用[J],微型电脑应用,2002.18(9):28-29.
[34]王文川,面向车载导航的嵌入式GIS研究与实现[J],南京航空航天大学硕士学位论文,2005.1:6-29.
[35]Sinn Kim,Jong-Hwan Kim,Adaptive Fuzzy-network-based C-measure Map-matching Algorithm for Car Navigation System [J],IEEE Transactions on Industrial Electronics,2001,(4).
[36]Sinn Kim,et al,Q-facter Map Matching Method Using Adaptive Fuzzy Network[C],IEEE International Fuzzy Systems Conference Proceedings,1999.
[37]Tomohiro Takagi,M.Sugeno,Fuzzy Identification of System and Its Application to Modeling and Control,IEEE Trans.Syst,Man and Cybern,1985,15(1).
[38]ManSheng Zhang,et al,A new self-adaptive Kalman filtering method for GPS kinematic positioning,Journal of Central South University of Technology 2003,34(5).
[39]Daglic,Schierholt K.,Stock Market Prediction Using Different Neural Network Classification Architectures.IEEE/IAFE 1996 Conference on Computatinal Intelligence for Financial Engineering,1996,8(3):72-78.
[40]师智斌,陈立潮,靳雁霞,基于神经网络的股票交易数据的预测研究[J],华北土学院学报,2003.34(6):12-16.
[41]Apostolos Nicholas Refenes,Achileas Zapranis,Gavin Francis,Stock Performance Modeling Using Neural Networks:A Comparative Study with Regression Models.Neural Networks,1994:7(2):375-388.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |