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.

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.

Back to top

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 (a_n-k+1, . . . , a_n). 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 = a₁a₂ . . . a_n. Let substring L(i,j) = a_ia_i+1. . .a_j 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 X_iX_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 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(X_i = a_i|…) denotes the probability that X_i takes the value a_i.

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.

Back to top

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.

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.

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.

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.

Back to top

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

• Design Patterns Elements of Reusable Object-Oriented Software by Gamma, Helm, Johnson, and Vlissides (1994) is a good resource on design patterns.
  
  
• The IBM Design Patterns project discovers and documents common solutions to problems in object-oriented software design.
  
  
• The Patterns Library is a source of information on books, articles, conferences, mailing lists, and more.
  
  
• Wiki on 802.16e: IEEE Standard for Local and Metropolitan Area Networks.
  
  
• "Mobility prediction in wireless networks" (MILCOM 2000) presents various enhancements to unicast and multicast routing protocols using mobility prediction.
  
  
• Stay current with developerWorks Technical events and webcasts.
  
  
• Read about the Markov chain on Wikipedia.
  
  
• "RFC 3095" describes IP packet header compression scheme which is used to reduce the size of overheads in IP packets communicating voice or other data over bandwidth constrained links.
  
  
• Browse the technology bookstore for books on these and other technical topics.
  
  

Get products and technologies

• Download IBM product evaluation versions and get your hands on a variety of tools and products from DB2®, Lotus®, Rational®, Tivoli®, and WebSphere®.
  
  

Discuss

• The Design Patterns Study Group of New York City is a center for the study and mastery of software patterns and pattern languages.
  
  

About the author

Deep 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.

Rate this article

Comments

Back to top

Table of contents

• Introduction
• Data communication revisited
• Modeling user movement
• Mobility Predictor design pattern
• Summary
• Resources
• About the author
• Comments

IBM SmartCloud trial. No charge.

Unleash the power of hybrid cloud computing today!

---

Public and private solutions in one trial.

Special offers