یک روش داده کاوی برای پیش بینی مکان در محیط های تلفن همراه

Mobility prediction is one of the most essential issues that need to be explored for mobility management in mobile computing systems. In this paper, we propose a new algorithm for predicting the next inter-cell movement of a mobile user in a Personal Communication Systems network. In the first phase of our three-phase algorithm, user mobility patterns are mined from the history of mobile user trajectories. In the second phase, mobility rules are extracted from these patterns, and in the last phase, mobility predictions are accomplished by using these rules. The performance of the proposed algorithm is evaluated through simulation as compared to two other prediction methods. The performance results obtained in terms of Precision and Recall indicate that our method can make more accurate predictions than the other methods.

Personal Communication Systems (PCSs) are becoming more popular by the help of the recent developments in the computer and communication technologies. In the near future, PCSs will support a huge user population and offer services that will allow the users to access various types of data such as video, voice and images. A PCS allows dynamic relocation of mobile users since these systems are based on the notion of wireless access. Mobility of the users in PCSs gives rise to the problem of mobility management. Mobility management in mobile computing environments covers the methods for storing and updating the location information of mobile users who are served by the system. A hot topic in mobility management research field is mobility prediction. Mobility prediction can be defined as the prediction of a mobile user’s next movement where the mobile user is traveling between the cells of a PCS or GSM network. The predicted movement can then be used to increase the efficiency of PCSs. By using the predicted movement, the system can effectively allocate resources to the most probable-to-move cells instead of blindly allocating excessive resources in the cell-neighborhood of a mobile user. Effective allocation of resources to mobile users would improve resource utilization and reduce the latency in accessing the resources. Broadcast program generation can also benefit from predicted mobility patterns, since the data items can be broadcast to the cell where the users are moving [16]. Accurate prediction of location information is also crucial in processing location-dependent queries of mobile users. When a user submits a location-dependent query, the answer to the query will depend on the current location of the user [17]. Many application areas including health care, bioscience, hotel management, and the military benefit from efficient processing of location-dependent queries. With effective prediction of location, it may also be possible to answer the queries that refer to the future positions of users. Up until now, there has been a considerable amount of research on mobility management. Most of the research has focused on the problem of location update, which is concerned with the reporting of the up-to-date cell locations by the mobile users to the PCS network [4]. Location update should be performed whenever a mobile user moves to another cell in the network to be able to track the exact location of each mobile user. When an incoming call arrives, the network simply routes the call to the last reported location of the mobile user. Compared to the amount of work performed on location update, little has been done in the area of mobility prediction [1], [6], [7], [8], [10] and [11]. These works have some deficiencies, which are explained in the following: • Some of these works do not attempt to find mobility patterns. Instead, the patterns are assumed to be already available. These patterns are then used for mobility prediction. • In some of these works, prediction is based on the probability distribution of the speed and direction of the mobile user. For collecting such information, highly sophisticated and expensive tools such as GPS (Global Positioning System) are needed. • Most of the methods studied in these works are highly sensitive to a change in a mobile user’s path. For this reason, the prediction accuracy drops in case of noisy data. These methods do not consider the difference between the randomness and the regularity in users’ paths (i.e., they do not distinguish a random movement and a regular movement of a user). In general, users follow some path patterns when traveling in network and their random movements are relatively few when compared to regular movements. Therefore random and regular movements should not be treated equally. Aiming to overcome the above deficiencies, we have developed an effective mobility prediction algorithm. In the first phase of this three-phase algorithm, movement data of mobile users is mined for discovering regularities in inter-cell movements. These regularities are called mobility patterns. Mobility rules are then extracted from the mobility patterns in the second phase of our algorithm. In the third phase, the mobility rules, which match the current trajectory of a mobile user, are used for the prediction of the user’s next movement. The first two phases of our prediction algorithm, which are user mobility pattern mining and mobility rule generation, are accomplished offline by the system. However, the last phase, i.e., the mobility prediction, is accomplished online. It means that whenever a user intends to make an inter-cell movement, a prediction request is sent to the system and the prediction is made by the system using our mobility rule based prediction algorithm. The rest of this paper is organized as follows. In Section 2, we present the network model we have used in this work, formulate the problem that we deal with, and present the related work. Our method for the solution of the problem is proposed in Section 3. We present the experimental results in Section 4, and conclude our paper in Section 5.

In this paper, we present a data mining algorithm for the prediction of user movements in a mobile computing system. The algorithm proposed is based on mining the mobility patterns of users, forming mobility rules from these patterns, and finally predicting a mobile user’s next movements by using the mobility rules. Through accurate prediction of mobile user movements, our algorithm will enable the system to allocate resources to users in an efficient manner, thus leading to an improvement in resource utilization and a reduction in the latency in accessing the resources. Another benefit of our algorithm will be to enable the system to produce more accurate answers to location-dependent queries that refer to future positions of mobile users. We have evaluated the performance of our algorithm using simulation and compared the obtained results with the performance of two other prediction methods, Mobility Prediction based on Transition Matrix (TM) and Ignorant Prediction. In TM, mobility prediction is based on the cell-to-cell transition probability matrix. The Ignorant method does not take any historical information into account when making prediction. In this method, randomly selected neighbors of the current cell are used as the predicted cells. This method can be considered as a baseline algorithm for comparison. Our method has performed well with a variety of corruption factor and outlier percentage values. We have observed that although an increase in the corruption in the data decreases the recall and precision, an increase in the outlier percentage has no significant effect on the recall and precision. When compared to the performance of the baseline method, which is Ignorant Prediction, our method provides a very good performance in terms of precision and recall. When we compare its performance with the performance of TM, it can be seen that the precision obtained with our method is better than that observed with TM. This result indicates that our method makes more accurate predictions. Most of its predictions made at each request are correct. On the other hand, the recall values obtained with TM are higher than those obtained with our method for most of the experiments. This is due to the nature of our method, which may not make prediction in response to some of the requests. The reason is that there may not be any matching rule for the current trajectory of the user when a prediction request is made. Thus, our method does not make any prediction in that case. On the other hand, TM makes prediction at most of the requests because it only keeps the transition probabilities of the cells. Therefore, even if there has been only one transition from a cell, say A, then it will use this information to make a prediction when the user is in cell A. It will have a higher potential to make predictions at every request, resulting in higher probability to make a correct prediction. Since the number of requests in the test set is the same for both methods and the number of correct predictions is higher for TM, TM produces higher recall values.