Publication authored by Amnir Hadachi, Oleg Batrashev, Artjom Lind,George Singer,Eero Vainikko.
You can find our publication here link.

Highlights

• Enhanced Markov Chain Algorithm
• Real Data Validation
• Improved User Mobility Prediction

1. Introduction

The surge in cell phone users and the widespread deployment of cellular networks over recent decades, driven by technological advancements, has led to various applications utilizing mobile devices. Smartphones, with their diverse communication capabilities, serve as valuable tools for understanding and predicting human mobility patterns. Mobility prediction models^[1] leverage cellular networks, employing two primary techniques. One approach focuses on analyzing users’ historical trajectory patterns^[2], delving into multidimensional contextual variables or geographical features to predict human movement^[3]. Another method involves probabilistic techniques, emphasizing historical mobility data alongside radio strength measurements. Common models in this category include prediction filters like the particle filter, Kalman filter, and linear predictors^[4]. These techniques collectively aim to forecast human mobility based on past behaviors and contextual knowledge extracted from mobile device data. In the rapidly evolving domain of mobile networks, predicting user mobility is a critical aspect of network management and service delivery. Our work titled “Cell Phone Subscribers Mobility Prediction Using Enhanced Markov Chain Algorithm” presents a significant stride in this area. It introduces an improved Markov Chain method, validated with real-world data, to more accurately predict cell phone users’ locations.

2. Methodology

The system architecture, depicted in Fig. 1, serves as a framework for processing collected data and training models based on user trajectories before predicting the user’s next cell location. The process begins by gathering data into the users’ database. Subsequently, the system processes this data to extract all user trajectories, defining them as a series of consecutive events, which may sometimes include redundant events of the same cell, subsequently combined into a single cell visit within a specific timeframe (65 minutes in this case due to hourly service events).

Fig. 1: Overview of the system architecture.

The system includes three trajectory filters, which potentially split the trajectory into multiple sub-trajectories (chains). These chains encapsulate the user’s trajectory Fig. 2, maintaining independence between subsequent chains.

Fig. 2: Visualization of users trajectories, Estonia.

The filters encompass the following criteria:

• Time filter: Defines the period and weekdays for a user trajectory.
• Ping pong handover filter: Mitigates errors in prediction by addressing ping-pong handover phenomena, where users switch between neighboring cells due to signal propagation variations. The filtering identifies and splits the trajectory when three sequential cells are not unique, ultimately reducing errors.
• Gap filter: Splits the trajectory when the time delay between subsequent visits exceeds 2 hours.

Post-filtering, the enhanced Markov algorithm is executed for mobility prediction. This algorithm incorporates two association rules—the temporal rule and the universal behavior rule—run separately during tests to evaluate their efficacy in prediction.

Human behavior’s repetitive nature suggests predictability in user mobility. However, irregular movements due to changes in habits challenge predictability. Hence, the introduction of two association rules aims to account for this unpredictability. The classic Markov approach forms the basis, followed by enhancements—namely, the universal behavior rule and the temporal rule—to address irregularities.

The Markov model comprises two key components: discrete states or events as contexts and transitions representing possible locations following these contexts. This model predicts the next location using the current context, typically derived from the most recent locations in the trajectory history.

The Markov process involves two elements: the General Prediction Algorithm (GPA) and the Local Prediction Algorithm (LPA). The GPA operates on a second-order Markov process, considering transitions between cells based on the current and previous cell. Meanwhile, the LPA acts as a first-order Markov process, focusing solely on transitions between the current and subsequent cell.

Further enhancements are introduced to the GPA and LPA algorithms: the Global Universal Prediction Algorithm (GUPA) and Local Universal Prediction Algorithm (LUPA), and the Global Temporal Prediction Algorithm (GTPA) and Local Temporal Prediction Algorithm (LTPA), each accounting for different aspects of user behavior and temporal factors.

For testing and comparison, two test sets—Test 1 and Test 2—are employed, each comprising 100,000 users. Test 1 includes users from the training database, evaluating the training algorithm’s performance, while Test 2 comprises users not in the training database, assessing the algorithm’s predictive ability for new users. Different combinations of these algorithms and enhancements are systematically tested to evaluate their performance and predictive accuracy.

3. Experimentation and Testing

The initial phase of testing involved individual assessments of various algorithms using two distinct datasets: Test 1 and Test 2. Table. 2 presents the outcomes of Test 1, showcasing the performance metrics for each algorithm. Notably, GTPA emerged as the most successful, achieving 95.67% correct predictions with the lowest rate of wrong predictions among the methods. Additionally, GTPA exhibited the highest localization ratio, signifying its ability to converge quickly to accurate predictions.

Test 1	%Correct Predictions (%)	%Wrong Predictions (%)	%Failure (%)	Localization Ratio (%).
GPA	81.46	6.25	12.29	52.82
LPA	53.98	23.76	22.26	18.63
GUPA	34.44	61.34	4.22	0.61
LUPA	17.58	82.4	0.02	0.07
GTPA	95.67	0.36	3.97	90.57
LTPA	66.6	10.02	23.39	38.41

Table 1: Unitary Test Results for dataset “Test 1”.

Moving to Table. 2, representing the results for Test 2, LPA stands out with 53.87% correct predictions, displaying a considerably lower rate of wrong predictions compared to other methods. However, LPA’s drawback lies in its relatively slower convergence to the correct prediction.

Test 2	%Correct Predictions (%)	%Wrong Predictions (%)	%Failure (%)	Localization Ratio (%).
GPA	9.57	2.25	88.18	17.9
LPA	53.87	23.8	22.33	18.43
GUPA	28.75	52.19	19.06	0.5
LUPA	18.18	81.81	0.01	0.07
GTPA	2.7	0.05	97.25	36.48
LTPA	6.6	2.85	95.55	12.61

Table 2: Unitary Test Results for dataset “Test 2”.

Further analyses involved combining various algorithms, as depicted in Fig. 2 the average performance across both datasets, illustrating that combinations incorporating GTPA, particularly GTPA+LPA, excelled when dealing with users known to the system, showcasing high accuracy in predicting movements and benefiting from the historical database during the training process.

Fig. 3: Performance of the combined methods using dataset “Test 1” plus Test2"."

The results indicated that the Global Temporal Prediction Algorithm (GTPA) combined with LPA yielded the most reliable predictions, especially for known users in the system. The GTPA outperformed other methods with a correct prediction rate of 95.67% in Test 1. However, for new users in Test 2, the Local Prediction Algorithm (LPA) demonstrated superior performance with a 53.87% correct prediction rate. These findings highlight the effectiveness of the enhanced Markov Chain algorithm in predicting user mobility with higher accuracy, especially when incorporating both global and local predictive components (GTPA+LPA).

4. Conclusion

This paper’s contribution to the field of mobile network management is noteworthy, presenting a robust and effective solution for predicting user mobility. The enhanced Markov Chain algorithm, validated with real-world data, offers promising implications for optimizing network resources and improving user experience. Future research could explore integrating other predictive algorithms to further refine the model’s accuracy, particularly for unknown users.

---

1. W.-S. Soh and H. S. Kim, “QoS provisioning in cellular networks based on mobility prediction techniques,” IEEE Communications Magazine, vol. 41, no. 1, pp. 86-92, 2003. ↩︎

2. T. M. T. Do and D. Gatica-Perez, “Contextual Conditional Models for Smartphone-based Human Mobility Prediction,” in Proceedings of the 2012 ACM Conference on Ubiquitous Computing, New York, NY, USA, 2012, pp. 163-172. ↩︎

3. Bellahsene, S., Kloul, L., Barth, D.:" A hierarchical prediction model for two nodesbased IP mobile networks" MSWiM 2009. In: Proceed- ings of the 12th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems MSWiM, Tenerife, Canary Islands, Spain, pp. 173-180 (2009) ↩︎

4. S. Bellahsene and L. Kloul, “A New Markov-Based Mobility Pre- diction Algorithm for Mobile Networks,” in Computer Performance Engineering, A. Aldini, M. Bernardo, L. Bononi, and V. Cortellessa, Eds. Springer Berlin Heidelberg, 2010, pp. 37-50. ↩︎