A Method For Trajectory Prediction Based On Data Mining

With the development of wireless technology and kinds of wireless applications, especially those need QoS support, mobility prediction techniques become more and more important.Mobility prediction impacts greatly on different aspects of wireless networks including reducing handoff delay of mobile hosts, improving admission control and flow control in wireless networks, reducing energy consumption of wireless network, improving the multicast routing protocols, and so on. Now the research on mobility prediction includes two different directions:one uses real time coordinates to make prediction with the assistance of GPS, while the other only uses user mobile history, which contains the sequence of APs the mobile host has associated with. The latter is the focus of this research paper. The main contents and conclusions in this dissertation can be summarized as follows:Among mobility prediction models in WLAN, Markov models are important for mobility prediction because of their simplicity and quite good prediction accuracy. But high_orders have the problem of high state space complexity.In fact, the mobility patterns are key factors in the mobility prediction problem. Therefore, the paper brings forward a new mobility prediction scheme based on data mining, especially on time sequence mining. At first, regular mobility patterns are picked out by using data mining techniques. Then by pattern matching, mobility prediction is made. In order to trace the newer mobility patterns, an incremental data mining technique is used to enhance the whole scheme, especially to improve its online prediction ability. Simulation experiments proved that the incremental data mining technique really promoted the prediction accuracy of the scheme.This paper puts forward a new method for predicting the mobile path based on pattern mining and matching, called MPP. Firstly Divide the historical record of user information into several transactions, and thus form the visiting transaction database. Having been given the minimum supportive degree threshold, we designed the algorithm Mm to mine the mobile patterns. Secondly we designed the algorithm named Mmp for the prediction of mobile user's future path.Advantages of method MPP:a) This method can get a better prediction result than that of method Markov, if only we do the measurement of the matching of current path and the pattern accurately, this is because in the method Mmp, we take consideration of all kinds of cases with different orders for the current path by means of repeated unreeling, not like the Markov, which just does the prediction with single order, here ,order stands for the number of nodes in current user path when doing the prediction;b) The method MPP occupied a smaller status space than Markov, because the pattern database includes only a few patterns. while the order₂ or order_k (k>2) Markov predictor possesses the disadvantage of space inflation, which means the status space increases exponentially as the AP number goes up.As the time goes by, new mobile record is added to historical database, so, some of the old user mobile patterns may no longer satisfy the minimum degree threshold and there will be new patterns come up ,therefore, the mined results must be updated at the same time, to reflect the dynamic updating of the mobile record database. How to make full use of the original mined results is very important to the improvement of efficiency of mining. Here we use the algorithm named PDIU to implement the incremental updating of pattern database, and only the frequent sequences, their supportive degrees and | D B .k| have to be stored, while there are not too many frequent sequences, so it takes a much smaller space. Better predicting precision is got after an incremental mining is implemented in pattern mining, and from the figure we can see it is equal with that of the order₂ Markov predictor. If we make the parameters more reasonable the predicting precision can be further improved. By implementing the incremental updating of the pattern database we improve the efficiency of calculation greatly avoiding mining the whole updated historical records database again.For improving the efficiency of MPP, this paper puts forward the design that using the technique of projection in the arithmetic of Mm and PDIU. General idea is: Given a visiting transaction database D, through the first scan, we will get all the frequent 1_sequences, assume them to be a,b,c,d,e,f, then the complete set of frequent sequences can be partitioned into the following six disjoint subsets according to the six prefixes: the ones having prefix a;the ones having prefix b;……the ones having prefix f.To mine the ones with prefix a, we just have to scan part of D but not the whole D, and this part that needs to be scanned is got by projecting D with prefix a, we call it a_projected database. It is the same when we mine other frequent sequences.With the development of Pervasive Computing and applications supporting wireless QoS, mobility prediction will become more and more important and contribute more to the future wireless networks. The results of the dissertation will contribute to the study on mobility prediction algorithms and its applications.