Research Of Real-Time Map Matching Algorithm Based On Storm

When a GPS point was projected into road network directly without any processing,its projection location will probably depart from user's true road very far,which does not satisfy the requirement of many LBS applications for location accuracy.Map matching technique is used to fix this kind of error.Under some circumstances,accuracy and real-time of location information should be guaranteed simultaneously,such as vehicle navigation,traffic condition monitoring,bus arriving time prediction and so on,so real-time map matching technique is widely used in these field.Existing real-time algorithms can be categorized into three groups: simple map matching algorithms,weight based map matching algorithms and advanced map matching algorithms,in which weight based map matching algorithms has the potential of high real-time and high accuracy due to its uncomplicated model,while simple map matching algorithms' simple logic lead to low accuracy in complicated road network and advanced map matching algorithms' complicated mathematical model cannot meet the high real-time demand.However,existing weight based algorithms have two major limitations: weight coefficient is constant,which cannot adjust to the changing matching situations;the history information of trajectory is not considered very well in model,which leads to the mismatch of parallel roads.Weight based algorithms' accuracy probably suffered from these limitations.This dissertation has two research purposes: improve weight based algorithm based on its shortcomings;explore its parallel performance in dealing with massive GPS points.The main achievements are obtained as followings.(1)Focusing on the issues that current weighted real-time map matching algorithms are difficult to keep high accuracy,an improved weighted real-time map matching algorithm named ST-DWMM(Spatio-Temporal Dynamic Weighted Map Matching algorithm)was proposed.Firstly,analysing the error sources of map matching,ST-DWMM algorithm made full use of GPS point's attributes and road network's topology properties and other information to reduce error.And then based on the relation among previous GPS point,previous match road,unmatched GPS point and its candidate roads to make spatio-temporal analysis,ST-DWMM algorithm's weight model was constructed consisting of distance weight,heading weight,direction weight and connectivity weight.Secondly,based on the factors having bad effect on the reliability of weight model,ST-DWMM algorithm created its dynamic weight coefficient model.Lastly,the best matching road segment was selected according to the confidence level of current GPS point to minimize probability of matching failure.The experiments were conducted on three city bus trajectories with total length of 36 km in Chongqing.The average matching accuracy of ST-DWMM algorithm is 97.31%.The experimental results show that compared with the comparison algorithms,ST-DWMM algorithm has better performance in matching Y-junctions and parallel road.(2)Concerning that the efficiency challenge when serial algorithm running in single server copes with a large amount of GPS points' real-time map matching,a parallel algorithm of ST-DWMM algorithm based on Storm platform was proposed in the dissertation.Firstly,considering the correlation among all the steps of the serial algorithm and principles of Storm,a parallel algorithm was presented.Then the parallel algorithm's matching efficiency was evaluated based on ten real trajectories with total length of 269 km,consisting of 16477 GPS points.The efficiency of ST-DWMM algorithm running in single server was regarded as benchmark.The experimental results show that the efficiency of the parallel algorithm can improved more than three times compared with the serial one and its single GPS point's matching delay was as low as 4 ms.