Predict user mobility in enterprise networks

Introducing a design pattern for predicting user movement

With the advent of high-speed, high-bandwidth mobile radio technologies and low-power, high-computing mobile devices, enterprise-application users are becoming increasingly mobile, rather than remaining fixed or nomadic. To migrate existing real-time applications of such users to these high-mobility networks, knowledge of user movement is essential. In the absence of this knowledge, reestablishing the network-side application context of users can be costly and lead to performance bottlenecks. In this article, learn about a behavioral design pattern for mobility prediction in a nomadic, mobile, or an ad-hoc network.

Share:

Deep Shikha (deep.shikha@in.ibm.com), Advisory Software Engineer, IBM

Deep Shikha photoDeep Shikha is an advisory software engineer at IBM. She is part of the team working on the FileNet suite of products in the Information Management group. When not busy at work, Deep tries to catch up on her interests in mountaineering, running, and karate.



10 June 2008

Introduction

Today's enterprise-application users are still relatively fixed but are becoming increasingly mobile with burgeoning high-speed, high-bandwidth mobile radio technologies such as IEEE 802.16e and 3G, and with the availability of low-power, high-computing mobile devices.

The technological challenges for real-time applications in a mobile environment are complicated. All such applications will need to be able to predict user movement in high-speed mobile networks driven by third- and fourth-generation mobile radio technologies. Without predictive mechanisms, trying to reestablish the network context of users will likely downgrade the performance of real-time applications.

In this article, learn about a novel design pattern for mobility prediction in a nomadic, mobile, or an ad-hoc network. With this design pattern, application architects can design the mobility predictor for various types of networks, independent of the structure of the transport networks. This article includes a complete design of the mobility predictor for a cellular network.

Data communication revisited

Data communication between digital machines is based on a hierarchical layer of very loosely coupled layers, which have a distinct and well-defined function to ensure reliable and efficient data transportation among applications. The Internet uses the TCP/IP protocol stack to communicate reliably between applications on different machines or devices. Figure 1 shows the typical IP protocol stack and the applications that rely on the IP stack to transfer data between them.

Figure 1. The TCP/IP stack
The TCP/IP stack

The TCP/IP protocol stack has two broad parts: the IP layer and above, and below the IP layer. The IP layer and above operate without regard to the physical media and its underlying characteristics, which are the link layer, media access and control, and the physical layers.

As a user moves within a network, the layers under the IP layer are responsible for maintaining connectivity to the network infrastructure. However, all layers in the TCP/IP stack must communicate with their peer layers in the end nodes to provide end-to-end (or "seamless") connectivity. Mobile IP technologies such as Proxy Mobile Internet Protocol (MIP), Client MIP, and IPv6-based MIP provide seamless connectivity for mobile IP-based devices. In order to ensure uninterrupted behavior on an application level, however, you must use optimization techniques such as buffering and context sharing.

Mobility predictions form an important aspect of application-level decisions. For example, the IP header compression scheme (see Resources) for voice over IP relies on recent history to reduce the size of overhead in the IP packets that contain voice packets by over 95 percent. The reduction is possible only with header compression receiving regular or event-based feedback from its peer entity. If this information is lost when a point of user attachment changes from a serving node to a destination node, a serious drop in voice quality can be perceived. If the user movement can be predicted, and the historical voice compression context can be shared between the serving and target compression entities, then the voice compression can resume from the last point at the serving node before the user was handed to the destination node.


Modeling user movement

When a user moves from one place to another, it is usually for some reason that will typically be the same the next time the user starts from the same position. Moving from one geographical position to another is not an independent event in statistical terms. The short-range behavior of user mobility is quite predictable, due to practical considerations such as movement on highways, business processes, and so on.

User movement in a mobile network can be modeled as a Markov stationary process (See Resources). The user mobility is predicted by using the previous long history of the user movement, a mobility model, and algorithms that use the “long history” along with the user’s current position. A predictor is an entity that can predict the user movement in a network based on the history of the user movement in such a network. The history of user mobility is the series of cells (in cellular networks) or any geography identifier that the user has moved across in the past.

Put simply, the Markov predictor relies on the probability of transition to a destination cell based on the current position being stationary, which means the probability of transition based on the current position is same everywhere in the long history of user mobility.

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

Consider a user whose location history is L = a1a2 . . . an. Let substring L(i,j) = aiai+1. . .aj for any 1≤ i ≤ j ≤ n .

We think of the user's location as a random variable X. Let X(i,j) be a string XiXi+1. . .Xj representing the sequence of random variates Xi,Xi+1, . . .Xj 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 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 Markov model is useful for describing user mobility in a mobile network. It allows for reasonably accurate predictions as the user mobility history accumulates over time. Studies have shown (see Resources) that a Markov predictor of order 2 yields better than most predictors of the same execution complexity and memory requirements.


Mobility Predictor design pattern

A design pattern is a structure for communicating objects and classes that are customized to solve a general design problem in a particular context.

In any mobile network employing mobility prediction, you can use the mobility predictor design pattern as a base template to develop components to execute the incumbent mobility prediction subsystem. A design pattern is typically made up of the aspects discussed in this section.

Intent

The mobility predictor design pattern provides a way to implement mobility prediction without exposing the underlying network architecture, application context, or mechanism of storing mobility history.

Motivation

Mobility prediction is a framework for predicting user mobility in a network that is an aggregate of geographical regions called cells. You can use any of the algorithms (such as Knuth Morris Pratt, with or without optimizations) for pattern searches in the list of symbols describing the accumulated history of movement within such a network. Based on the searches, statistical methods are used to produce the output showing a matrix of transition to target cells and associated probability of the transition from the current cell.

The mobility predictor also provides interfaces for defining the following:

  • Network layout
  • User characteristics
  • Triggers to the application contexts
  • Mechanism for measuring the efficacy of its own prediction

A typical pitfall in designing a mobility predictor is to fold the user information and network-related information into the predictor object itself. Doing so severely limits the ability to reuse the predictor for a new network or a new set of users with different characteristics.

Figure 2 shows the classes in the mobility prediction framework.

NetworkUser class
For encapsulating the network user data, user identification, and the network traversal history.
NetworkPlan class
An aggregate class of cells that represents the network structure. The operation NeighborList provides a list of neighbor cells for a given cell. You might want to predict the mobility of a network user in different ways.

Beware of bloating the NetworkUser interface with operations of different mobility predictors.

MobilityPredictor class
Needs to interface with NetworkUser and NetworkPlan to derive information used by the predictor algorithm to create the cell transition matrix. MobilityPredictor also has a unique mechanism to build reporting information on its own prediction efficiency. It is a secret hidden in the class and is not exposed to the outside.

The mobility predictor pattern arises from the ideas just discussed. The pivotal point of this pattern is to take the responsibility for accessing the user mobility history in the NetworkUser class and put it into the MobilityPredictor object. The MobilityPredictor class defines an interface for accessing the network user’s traversal history, and it defines an interface for deriving the neighbor list for a cell from the NetworkPlan class, thereby predicting user movement in the NetworkPlan generated cell list.

For example, a NetworkUser and a NetworkPlan would call for a MobilityPredictor with the relationship shown in Figure 2.

Figure 2. Class diagram for a mobility prediction module
Class diagram for a mobility predictor module

Before you can instantiate the MobilityPredictor class, you must supply the NetworkUser and the NetworkPlan to predict the user mobility. Once you have the MobilityPredictor instance, you can predict user movement within the network based on the user’s current position. Separating the prediction mechanism from the NetworkUser objects lets you define predictors using different searching algorithms without enumerating them in the NetworkUser interface.

For example, a MarkovMobilityPredictor would predict mobility based on the order-k Markov model. An LZ-based predictor LZMobilityPredictor would predict mobility based on a popular incremental parsing algorithm by Ziv and Lempel. Similarly, you can have PPMMobilityPredictor and SPMMobilityPredictor based on a Prediction by Partial Matching and Sampled Pattern Matching, respectively (see Resources for more information).

The MobilityPredictor and the NetworkUser are coupled classes. Changes in the NetworkUser structure will result in changes in the code of the MobilityPredictor. The MobilityPredictor class should not be committed to a particular structure of the NetworkUser. Therefore, only the generic interfaces will be encapsulated to an abstract class of the NetworkUser. Figure 3 shows a polymorphic MobilityPredictor.

Figure 3. Subtyping polymorphism
Subtyping polymorphism

You can define an abstract MobilityPredictor class that provides a common interface for handling mobility prediction implementations. Then you define concrete MobilityPredictor subclasses for the different implementations that are based on different mobility prediction algorithms. As a result, the mobility prediction mechanism becomes independent of the concrete subclasses.

The NetworkUser should be able to create a MobilityPredictor object based on the mobility prediction algorithm you are going to use. The CreateMobilityPredictor function in the NetworkUser class implements the interfaces defined for usage of the MobilityPredictor.

Applicability

Use the mobility predictor pattern to:

  • Access a network user’s movement history, extract the current context, and predict the next location.
  • Provide a uniform interface for making mobility predictions for different mobility prediction algorithms.

Structure

Figure 4 shows a design pattern for mobility prediction.

Figure 4. Design pattern for mobility predictor
Design pattern for mobility predictor
Participants
ParticipantDescription
MobilityPredictorDefines an interface for making mobility prediction
ConcreteMobilityPredictorImplements the MobilityPredictor interface
NetworkUserDefines and implements the MobilityPrediction creation interface to return an instance of the proper ConcreteMobilityPredictor
NetworkPlanDefines and implements the neighbor listing interface based on the current cell

Collaborations

A ConcreteMobilityPredictor reads the user movement history in the network, extracts the current context, and can predict the movement of the network user based on the mobility prediction algorithm.

Consequences

The mobility predictor pattern has two important consequences:

  • It supports variations in the mobility prediction of the network user.

    You can do mobility prediction in multiple ways based on different prediction algorithms, such as using the Prediction by Partial Matching or Sampled Pattern Matching. This pattern makes it easy to change the mobility prediction algorithm by just replacing the MobilityPredictor instance with a different one. You can also define MobilityPredictor subclasses to support new predictors.

  • It simplifies the NetworkUser interface.

    MobilityPredictor's prediction interface eliminates the need for a similar interface in the NetworkUser, thus simplifying the NetworkUser class.


Summary

In this article, you learned about the increasing need to model mobility prediction. The mobility predictor design pattern explains how to implement a mobility predictor in your application environment.

Resources

Learn

Get products and technologies

Discuss

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Rational software on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Rational, Mobile development
ArticleID=312852
ArticleTitle=Predict user mobility in enterprise networks
publish-date=06102008