Research And Implementation Of Continuous State Query Algorithms Between Moving Objects In Road Networks

With the development of location-based services (LBS), users’ new demands for LBS become more and more diversified. For example, in the field of intelligent transportation, the automatic driving technology not only needs to solve ordinary position location technology, but also, and very importantly, needs to continuously monitor the relationship of distance change between the car and other vehicles on the road, to ensure the safely driving. The existing mobile object query technology, such as range queries, nearest neighbor queries, continuous range queries, just focuses on position relationship between the query point and the queried points one moment, but can not satisfy the users’ demands for continuous state queries between two moving objects. State queries between moving objects are that the moving objects query position relationship between themselves and other moving objects, such as more and more far or more and more close. The existing state queries between moving objects, including naive state query and state query based on ELM, are based on euclidean space, and can not to be applied to road networks. So in this thesis presents continuous query between moving objects in road networks. There are two technology problems in the LBS applications:how to rapidly process large volume of moving objects’ position to determine the object belonging to segment, and how to rapidly calculate the distance between two moving objects. Aiming at the above problems, this thesis consists of the following two aspects:For the problem about rapidly positioning moving objects belonging to segment, this thesis presents three kinds of algorithm on moving objects positioning. Moving objects positioning based on dividing segment algorithm effectively reduce the MBRs’ overlap region and MBRs’ invalid area coverage by dividing the long road. Moving objects Positioning Based on Grid and R-tree algorithm, PBGR, combines high efficiency grid positioning with R-tree searching efficiency. Moving objects positioning based on Network Topology and Grid and R-tree algorithm, combine network topology with PBGR. Experimental results show that three kinds of algorithm about moving objects positioning outperform the algorithm of moving objects positioning based on R-tree.For the problems about rapidly calculating distances between massive moving objects data, this thesis presents calculating distance sequence based on Distance Query Table (DQT) algorithm, in view of engineering. This algorithm satisfies the real-time requirement of the continuous state queries between moving objects. The distance query table needs large memory space but user needs limited qury range. This thesis presents an algorithm for calculating distance sequence based on Limited Space Distance Query Table, LSDQT, in order to save memory space. Experimental results show that two kinds of algorithm presented by this thesis outperform the algorithm of calculating distance sequence based on shortest path. Although LSDQT takes longer the time of calculating distance than DQT, the distance query table of LSDQT needs 1% memory space of DQT’s. The accuracy of state between moving objects calculated by LSDQT is similar to DQT’s, nearly 100%.