Research And Implementation Of Range Departure Monitoring Algorithms For Groups Of Moving Objects Based On Covered Area

With the rapid development of wireless communications and geo-positioning, much more attention has been paid to LBS (Location Based Service) which can be widely used in many fields such as civil and military. Because of the popularity of LBS equipments, people need more and more new types of LBS and monitoring range departure of grouped moving objects is one of the popular services. Users can use the service at any time to get to know whether the monitored non-center objects in each group have deviated from the center object beyond the specified distance, that is to say, whether beyond the circular range which with the center object as center and the specified distance as the radius. For example, a large number of tourist tours in a scenic can use the service to monitor if there is any tourist deviated the tourist tour guide too far and when the kindergarden teachers guide the students to go outing, the service can determine whether there is any student too far away from the teachers.Although there have been many achievements in the research on LBS, most researches have focused on that neither the querying point nor the queried point is static, in addition, the researches which is directly related to the monitoring of mass of moving objects is rare. In the process of range departure monitoring, both of the querying point and the queried point are in different motions. The existing achievements can’t be used directly,and a new index structure and algorithm are needed. This thesis conducts a thorough study on these issues.Firstly, according to the distribution and movement characteristics of mobile objects, this thesis proposes a grouped mobile objects index based on covered area virtual grid quadtree (GVGQ) to manage the movement of objects with group information. GVGQ index is built on the area of mobile objects rather than mobile objects themselves to reduce the frequent updates of the index structure caused by the position changes of moving objects. Furthermore, the corresponding group information of mobile objects is stored in the GVGQ index structure in order to much easily support query operations of the mobile objects in a specified group. Secondly, based on GVGQ index structure, this thesis presents two algorithms to monitor the range departure of grouped mobile objects. The RQMonitor algorithm employs GVGQ index structure to execute range queries to find the departure objects in the outside area of the approximate security area of each group. It can significantly increase range departure monitoring speed by making full use of the group information in the index structure and the inclusion relations between the nodes and the query ranges. While, the DPMonitor algorithm also find the departure objects in the outside area of the security area of each group with the same mechanism as the RQMonitor algorithm. The main difference is that the DPMonitor algorithm prunes the nodes in which there are no departure mobile objects through the maximum distance and minimum distance between the nodes and the central object in the corresponding group. Besides improving monitoring accuracy, the monitoring algorithm response time can be improved also.To analyze the performance of GVGQ index structure and monitoring algorithms proposed, this thesis does many simulation experiments. The evaluation results show that the designed index structure and two monitoring algorithms have good flexibility and scalability and more suitable for dealing with large data. Under the environment of100thousands to300thousands of moving objects, the proposed two monitoring algorithms can be improved one order of magnitude in the response time compared to the naive algorithm.