HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.

Introduction

Mobile cellular Telecom Service Providers (TSP) allocate radio resources (frequency, timeslots. codes etc.) to various Base Stations (BS) that cover certain geographic areas called cells. The allocation of the radio resources is called Radio Planning and is an involved skill employing the use of traffic estimation, nature of traffic analysis, nature of dynamics of traffic, terrain and business needs among others. Invariably, the TSPs start with a radio allocation configuration and then monitor the key parameters of the network such as dropped calls, resource utilization, revenue etc. to monitor the effectiveness of their current radio plan. The feedback acquired over a time is fed back into a system typically called a Offline Traffic Analyzer (OTA) and the Analyzer produces an updated radio plan which is again tried out in the live network.

A mobility predictor (MobPred), on the other hand uses user mobility history to predict user movement across radio cells and consequently this information can be a critical input to the Traffic Analyzer to optimize radio resource utilization.

The Motivation for mobility prediction

Some of the motivations for the ability to predict user movement are

• Preventing handover failures owing to resource constraints
• Flow oriented route prediction
• Distance vector routing with mobility prediction
• On-Demand Multicast Routing Protocol
• Long term radio planning
• Predictive header compression (and other context data sharing) during handoffs

Benefits of MobPred? for network layer specially routing are discussed in [sungmar] and [sohkim] discusses the resource optimization based on MobPred? in a network effected by nodes moving in a road network. However, in this article we intend to discuss a simple statistical solution for the MobPred? problem.

The simplified Mobility problem

A Mobile network infrastructure system receives reports of change of user cell updates as and when they change their position to a new cell (or even recover from loss of radio coverage in the same cell). The problem for a Mobility predictor is to find the probability of user moving to each neighbouring cell based on its previous mobility pattern.

A simple solution - A Markov Predictor [songkotz]

The order-k or O(k) Markov Predictor assumes that the location of a user can be predicted from the current context, that is the sequence of k most current locations in the location history of (a_n-k+1_....,a_n_). The underlying Markov model represents each state as a context, the transitions represent the possible locations that follow the context.

 Consider a user whose location history is L =
 a_1_,a_2_...an. Let substring L(i,j) = a_i_,a_i+1_....a_j_
 for any 1 ≤ i ≤ j ≤ n. The users location can be
 thought of as a random variable X. Let X(i,j) be a string
 X_i_,X_i+1_....X_j_ representing the sequence of random
 variates X _i_, X_i+1_...X_j_ for any 1 ≤ i ≤ j ≤
 n. 

Define the context c = L(n-k+1,n). Let A be the set of all possible locations. The Markov assumption is that the X behaves as follows for all a A and i {1,2,....n}:

 P(Xn+1 = a|X(1,n) = L) = P(Xn+1 = a|X(n-k+1,n) = c)
 = P(Xi+k+1 = a|X(i+1, i+k) = c).  
 Where the notation P(Xi = ai|..) denotes the probability
 that Xi takes the value ai.

The equation above indicates that the probability of transition depends only on k most recent locations. The above also indicates the assumption of a stationary distribution that is the probability is same anywhere the context is the same.

Sample Architecture for a mobile cellular network

We implemented and analyzed a Markov predictor for a mobile cellular network with the input as the cell update information as the users cross form one cell to another and the output of the predictor as the list of cells and associated transition probability for each cell. The implementation architecture comprises of an in memeory database to remember cell update history of each user and the moment a cell update trigger is recieved by the MobPred? system, it looks up the network design/layout and finds the potential destinations of the user. For each cell in the potential transition cell list, it looks up the long history of the cell updates of the particular user and computes the conditional probability of the used to transit to the destination cell based on its last few(order) cell transitions. It assumes that this movement process is a stationary process.

We tested an implementation based on the above architecture and would report it in a separate paper.

Conclusions

There a variety of Mobility predictors such as LZ (Ziv and Lempel), PPM (Prediction by Partial Matching) or others (Sampled PPM etc.) and [songkotz]] has analyzed the efficacy of these in a campus wide WiFi? network. Our results in a simple simulated cellular network match the ones reported in the same paper. We observed an accuracy of about 65-70% for median users in our implementation of order 2 Markov predictor.

Overall the best Mobility predictors as reported in [songkotz] have an accuracy of about 65-72 percent for median users, but the accuracy varies widely around that median. In our view, currently the mobility prediction for individual user, the cost is quite high (computationally) and the benefit is quite questionable, however, for an aggregation of users, the mobility prediction information can be quite useful to the Telecom Service Providers.

Consider the case of movement of users on a highway, it is not really critical for a TSP to know if individual users would be moving from one cell to another, the crucial information is how many users may move (with a large probability) to a destination cell at some time of the day. Given this information about aggregates of users, the service provider can optimize the radio resource allocation. However it currently rules out benefits such as user application/network layer or even MAC layer context transfer.

References

[sungmar] Mobility Prediction in Wireless Networks MILCOM 2000

[sohkim] Dynamic Bandwidth Reservation in cellular networks using road topology based mobility prediction INFOCOM 2004, On page(s): 2766- 2777 vol.4

[songkotz] Evaluating Next-Cell Predictors with Extensive Wi-Fi Mobility Data Libo Song, David Kotz, IEEE transaction on mobile computing, dec 2006.

Appendix, a sample source for the predictor of order bigO.

int pred(predList* curList, int curCell) { /* accepts userId in the curList, current cell and constructs transition matrix for the user based on the histDb and returns the list of cells in the curList with associated probability of movement. The order of predictor is the global bigO iterate thru mobDb to find the last bigO cells for this userId find all potential neighbours of this (userId,cell) in the nw build the transition matrix for each cell copy into curList and return.

• /

int i,j,k,l = 0,m,n; int curRec, c; int shortPath[bigO+1], tmpShortPath[bigO+2];

//make room for "transition to" cell

for (curRec = 0; histDb[curRec].userId && !(histDb[curRec].userId == curList -> userId); curRec++); if (histDb[curRec].userId != curList -> userId) { printf ("error finding user \n"); return (0); }

//init shortPath for (i = 0; i < bigO+1; i++) shortPath[i] = 0;

for (i = 0; i < bigO+2; i++) tmpShortPath[i] = 0;

//find the end of path and copy last bigO items to shortPath for (i = 0; histDb[curRec].path[i] && i < MAX_PATH_LEN; i++); i = ( (c = (i - bigO)) < 0) ? 0 : c; for (c = 0; c < bigO; shortPath[c++] = histDb[curRec].path[i++]); // short path may have only one cell, need to take care...

//printf("the short path items are d %d \n", shortPath[0], shortPath[1], shortPath[2]);

// given the short path, what are the probabilities for transitioning to the neighbouring cells /// count the number of times the shortPath occures i.e. last bigO transitions happened.

n = instanceIn(histDb[curRec].path, shortPath); if (n > 1) n--; //ignoring latest traverse //printf (" n is %d\n", n); for (j = 0; curList -> cellList[j].cellId && j <MAX_NEIGHBOUR_CELL;j++) { // building subpath to current cell from last two cells. for ( i = 0; i < bigO; i++) tmpShortPath[i] = shortPath[i]; tmpShortPath[i] = curList -> cellList[j].cellId;

m = instanceIn(histDb[curRec].path, tmpShortPath);

//printf("m is %d and m/n is %f",m, (float) m/n); curList -> cellList[j].Pt = (float) m/n;

// printf("the tmpshortPath d d times \n",tmpShortPath[0],tmpShortPath[1], // tmpShortPath[2],instanceIn(histDb[curRec].path, tmpShortPath));

}

// Not efficient for large data Bases, but sufficient for current mobile networks // can implement knuth Morris Prat algorithm based substring matching // of the strcat(shortPath, curList -> cellList) in the histDb[user] -> path for large data base size.

return(1);

}

Maintainer: rakesh.mawa@hsc.com Views: ###

Categories: Wireless

Comments