Mobility Modeling, Prediction and Resource Allocation
in Wireless Networks
by
Pratap Simha Prasad
A dissertation submitted to the Graduate Faculty of
Auburn University
in partial fulflllment of the
requirements for the Degree of
Doctor of Philosophy
Auburn, Alabama
May 9, 2011
Keywords: Mobility Modeling, Mobility Prediction, Resource Allocation
Copyright 2010 by Pratap Simha Prasad
Approved by
Prathima Agrawal, Chair, Sam Ginn Distinguished Professor of Electrical and Computer
Engineering
Thaddeus Roppel, Associate Professor of Electrical and Computer Engineering
Shiwen Mao, Assistant Professor of Electrical and Computer Engineering
Abstract
Rapid increase in the number of mobile and wireless users has created greater loads on
legacy networks. Also, increased miniaturization of computing devices has led to an in ux
of handheld gadgets. Mobile users now wish to have seamless roaming across networks and
not experience  uctuations in the quality of service. These wireless devices can overwhelm
existing networks since these were traditionally not built to handle heavy user mobility across
networks.
User mobility in uences the performance seen by a mobile device in a wireless network.
Prior knowledge of mobility patterns can be exploited to properly allocate network resources
and enhance the performance and quality of service experienced by a mobile device for ap-
plications and services. Hence, mobility prediction plays an important role in the e?cient
operation of wireless networks such as WANs and WLANs. In this work we propose a prob-
abilistic model to efiectively predict user mobility using wireless trace sets using a Hidden
Markov Model (HMM). Access to mobility related information such as user movement pro-
vides an opportunity for networks to e?ciently manage resources to satisfy user needs. Also,
mobility models for simulation and their performance analysis are investigated rigorously.
Adaptive network resource management based on user mobility can reduce network
loads. Towards this goal, we propose a generic methodology based on a control theoretic
framework. The feedback based controller efiectively uses the predicted mobility to allocate
resources efiectively for mobile users. Incorporation of this engine in a control theoretic
framework with feedback from an adaptive controller permits the e?cient allocation of net-
work resources to various applications. The efiectiveness of the approach using a prediction
engine based on HMM is evaluated through simulation experiments. All simulations use
real-world wireless traces. The proposed framework is quite general and the HMM based
ii
engine can be replaced by other suitable models such as neural networks and results for these
show that the framework is indeed modular as proposed.
Mobility also in uences the interference seen by a mobile user. We study the efiect of
mobility on interference dynamics and the outage perceived by users in a cellular system.
Due to the mobility of interfering nodes, the aggregate interference and its statistics are
time-varying. Analytical results are obtained for interference statistics by using a Gaussian
model and considering the efiect of difierent mobility models. For this purpose, the cross-
over probabilities of difierent edges of a cell and for difierent mobility models are obtained
through simulation and used in the derivation of analytical results.
The main contribution of this dissertation is a generic framework for mobility prediction
and resource management. A  exible and generic framework for mobility prediction and
resource allocation allows for use of other techniques such as ARMA and machine learning
in place of HMM and Neural Networks. The generic model can be used in various network
applications such as QoS, seamless handover and jitter-free streaming applications.
iii
Acknowledgments
I acknowledge with great pleasure the help received from several persons and extend
thanks to all of them who helped me during my graduate studies at Auburn University. First
and foremost, it is my humble duty to convey my hearty thanks to my advisor Professor
Prathima Agrawal. She has provided me with full freedom to identify research problems,
given sound advice and ideas to solve them and motivation to lead this project to fruition.
Moreover, she has inculcated objective and original thinking in me and the drive to pursue
research problems. She has turned me from a raw engineer to a research scientist. For these
and a lot more, I am forever indebted to her.
I also wish to thank Professors Shiwen Mao and Thaddeus Roppel for graciously accept-
ing to be on my advisory committee. Special thanks area also due to Prof. Shiwen Mao for
initially introducing me to mobility models in his course. I also wish to thank Dr. Alvin Lim
for his consent to be an external reader for the dissertation at a very short notice. Special
thanks to Ms. Shelia Collis who has been a great help in taking care of tedious paperwork
and red tape to make our lives easier.
My thanks also go out to my colleagues and friends in the Wireless Research Laboratory
in 405 Broun Hall. I wish to thank the former ?residents? Santosh Pandey, Ravi Paruchuri,
Sowmia Devi, Priyanka Sinha and Dr. Shaoqiang Dong for valuable suggestions and dis-
cussions that we have had during my stay here. Also the present group of Dr. Alireza
Babaei, Santosh Kulkarni, Yogesh Kondareddy, Nida Bano, Indraneil Gokhale and Gopal
Iyer have provided a great environment for discussion and occasional welcome distractions.
Many friends at Auburn and elsewhere have contributed to shaping my thoughts and pro-
vided moral support when I needed it most. I could not have asked for better and more
understanding roommates than Anilkumar and Santosh Kulkarni to spend my student days.
iv
Also, several other friends and relatives have ensured that I never felt homesick - espe-
cially my heartfelt thanks to Raju, Rajesh and Sreekantamurthy and family. I gratefully
thank them all for their time and caring thoughts. I particularly wish to thank Mr. A. L.
Vishweshwaraiah for his kind help in the initial stages.
Finally, thanks to Lord Lakshmi Narasimha Swamy for helping me in all my endeavors
and perseverance and have faith in human values. My dearest brother Pradeep has been
very supportive and loving and I am very thankful for his afiection. My wife Deepika has
helped a lot with the love and support in flnishing up this dissertation and I am grateful
for her patience. Lastly, I am eternally grateful for the tremendous sacriflces that Amma,
Anna, Ajji and Thatha have made to ensure that I had an excellent education. They have
always inspired me, instilled values, supported me in all my ventures and made me what I
am today. For this and much more, I am in their eternal debt. It is to them that I humbly
dedicate this thesis.
v
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Organization of this dissertation . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Simulation Study of Mobility Models . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Motivation for using Mobility Models . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Existing Mobility Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3.1 Random Way Point Mobility Model . . . . . . . . . . . . . . . . . . . 8
2.3.2 Random Walk Mobility Model . . . . . . . . . . . . . . . . . . . . . . 12
2.3.3 Random Direction Mobility Model . . . . . . . . . . . . . . . . . . . 14
2.3.4 Other Mobility Models . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.5 Shortcomings of Mobility Models . . . . . . . . . . . . . . . . . . . . 16
2.4 Performance Analysis of Mobility Models . . . . . . . . . . . . . . . . . . . . 18
2.5 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Mobility Models vs other methods . . . . . . . . . . . . . . . . . . . . . . . . 26
2.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Mobility Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Existing Methods of Mobility Prediction . . . . . . . . . . . . . . . . . . . . 29
vi
3.3.1 Challenges in Mobility Prediction . . . . . . . . . . . . . . . . . . . . 31
3.4 Mathematical Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.1 Markov Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.2 First Order Markov Model . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5 Hidden Markov Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5.1 Prediction Model using HMM . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.1 Wireless Mobility Traces . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.2 Mining Wireless Traces for Information . . . . . . . . . . . . . . . . . 46
3.6.3 Trace Sets as HMMs . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.7 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.8 Other prediction methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.8.1 Neural Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.8.2 MultiLayer Perceptron Neural Network Model . . . . . . . . . . . . . 53
3.8.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.9 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.9.1 Comparison of Neural Networks and HMM Models . . . . . . . . . . 60
4 Resource Allocation in Wireless Networks . . . . . . . . . . . . . . . . . . . . . 61
4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Network Management using Mobility Prediction . . . . . . . . . . . . . . . . 62
4.3 Control Theory in Resource Allocation . . . . . . . . . . . . . . . . . . . . . 62
4.4 Proposed model and Mathematical analysis . . . . . . . . . . . . . . . . . . 63
4.5 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.1 MATLAB Simulink Modeling . . . . . . . . . . . . . . . . . . . . . . 69
4.5.2 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4.6 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
vii
5 Efiect of Mobility on Interference . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.1 Proposed Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3 Interference Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.4 Relations for ntij . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7 Future Work and Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
viii
List of Figures
2.1 A classiflcation of mobility models in literature . . . . . . . . . . . . . . . . . . 8
2.2 Sample movement of nodes in a Random Way Point mobility model . . . . . . . 9
2.3 Average instantaneous velocity in meters/second as simulation progresses . . . . 12
2.4 Characteristic movement of nodes in a Random Walk mobility model . . . . . . 13
2.5 Characteristic movement of nodes in Manhattan mobility model . . . . . . . . . 17
2.6 Network architecture comprising of mobile nodes, clusters and cluster heads . . 19
2.7 Performance of DSR protocol for various mobility models; RWP gives best hop
count in simulation results for DSR . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.8 End to end delay packet transport for Dynamic Source Routing protocol . . . . 22
2.9 Packet delivery ratio for Random Way Point mobility model . . . . . . . . . . . 22
2.10 Efiect of node density on network delay . . . . . . . . . . . . . . . . . . . . . . 23
2.11 Packet delivery ratio for Random Way Point mobility model . . . . . . . . . . . 24
2.12 Packet delivery ratio for various mobility models using Dynamic Source Routing
protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.13 Efiect of tra?c  ows on throughput for Random Walk mobility model . . . . . 25
3.1 A Markov Chain showing states, state transitions and transition probabilities . 34
ix
3.2 Initial Prediction success rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Prediction Success rate after training . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Transition probabilities of 3 states during the initial and steady states . . . . . 40
3.5 A Schematic of a Hidden Markov Model showing the hidden and observable
states, state transitions and probabilities. . . . . . . . . . . . . . . . . . . . . . 41
3.6 APs and the connected mobile users. User AP12 can be connected to either AP1 or
AP2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7 Percentage of time connected to difierent APs . . . . . . . . . . . . . . . . . . . . . 49
3.8 Prediction accuracy for various users using HMM . . . . . . . . . . . . . . . . . . . 49
3.9 Efiect of sequence length on prediction accuracy . . . . . . . . . . . . . . . . . . . 50
3.10 Efiect of iterative improvement of HMM on prediction accuracy . . . . . . . . . 50
3.11 A scatter plot showing the distribution of users? average prediction accuracies . . . . 51
3.12 A representation of a Multi Layer Perceptron . . . . . . . . . . . . . . . . . . . 53
3.13 Efiect of iterative improvement of Neural Networks on prediction accuracy . . . 56
3.14 A comparison of prediction accuracies between Neural Network and Hidden
Markov Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.15 AcomparisonofpredictionaccuracybetweenNeuralNetworksandHiddenMarkov
Models over long movement sequences . . . . . . . . . . . . . . . . . . . . . . . 58
3.16 Optimal weight coe?cients convergence in a MLP Neural Network model . . . . 59
4.1 The proposed network model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
x
4.2 Details of the network controller . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Simulated resource utilization ^ythr with and without controller . . . . . . . . . . 70
4.4 Resource utilization ^ythr as a function of number of users . . . . . . . . . . . . . 71
4.5 Percentage of dropped users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.6 Simulation convergence time for model coe?cients a(i)n . . . . . . . . . . . . . . 72
4.7 Mean errors in estimated network load at various instants . . . . . . . . . . . . . . 72
5.1 Representation of the mth nearest node from the BS in a cell . . . . . . . . . . . 76
5.2 Cellular geometry and cell numbering . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3 Cell cross-over probability from difierent edges of a cell . . . . . . . . . . . . . . 78
5.4 Distances between the interfering nodes and the victim BS . . . . . . . . . . . . 79
5.5 The geometry used to flnd Hij . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.6 Efrfimg versus m for fi = 3;R = 100 and N = 10;20;30 . . . . . . . . . . . . . . 81
xi
Chapter 1
Introduction
Recent trends in the development of microchip technologies and their miniaturization
has caused an explosive spurt in the growth of the hand held device market. Examples
of such devices are laptops, PDAs, WiFi enabled cellphones, etc. With ubiquitous wireless
connectivity in today?s workplaces, social and home environments, these devices are naturally
wireless enabled and lead to increased usage at all places. The presence of cellular handsets
embedded with WiFi and bluetooth devices, PDAs enabled with multiple kinds of radios,
etc can also enable other kinds of networks such as ad hoc networking [1]. These devices
support several applications including voice, video, data, etc which are bandwidth intensive.
Even though devices and networking capabilities are ever increasing, there still exist
several challenges that can constrict the growth of the hand held wireless market. Some such
factors include network connectivity, bandwidth  uctuations and high network costs. Also,
available network resources are subject to abrupt changes due to factors such as mobility,
environmental variations, etc.
Most access points or home wireless routers are single node networks that are not prop-
erly planned before installation. They may be interfering with several other neighboring
device channels or may not be installed at the right locations. The increasing availabil-
ity of public wireless access points with internet connectivity has also increased. Most of
these wireless networks are connected to backbone wired legacy systems and wired-wireless
networks are still prevalent in several places.
The sudden arrival of a large number of wireless users can lead to a bandwidth crunch
and result in network failure. Hence there is a necessity to explore proactive methods to
provide guaranteed services to the wireless applications. The huge popularity of wireless
1
hand held devices have necessitated provisioning distributed resources to a variety of mobile
client terminals.
1.1 Motivation
With the availability of contiguous coverage, mobile users now expect to have uninter-
rupted service. Since most users are highly mobile, there is a need to include mobility as
an inherent part of the system [2] [3]. Mobility introduces dynamism in the network. The
network, if modeled as a graph with users as vertices and links between the users/network
as edges, is ever changing due to the continuous motion of the users. A single network
graph snapshot would be stale within a short time and would be worthless to determine
the current positions of users. Also, difierent classes of networks exhibit difierent  avors
of mobility. User mobility in a cellular environment is very difierent from the mobility of
WLAN users. Mobile users on an educational campus move very difierently as compared
to users on the streets in a city or users in a dense city environment. There may be some
level of predictability depending on the topology of the network graph. One way of studying
mobility is through designing mathematical models that can model human mobility [4] [5]
and these are usually used in simulations. Also, extensive experimental studies have been
performed to collect mobility traces of users. However, this requires a lot of resources and
becomes mostly speciflc to the scenario in which the experiments were conducted.
Similar to cellular handofis, wireless networks also need to hand over the users to an
adjacent networks access point (AP) [6]. This is necessary in order to continue active sessions
such as voice-over-IP (VoIP) calls, video and audio streaming sessions, flle transfers, etc
without any disruption of service. This means that their connections are constantly being
switched from one wireless access point (AP) to another. A handofi is possible only if
resources are made available at the next location and the current AP can inform the next
AP before hand. A failure in this process leads to session termination due to any of the
reasons such as latency, lack of resources, etc.
2
In order to ensure timely handofis, we need to allocate resources at neighboring APs
to facilitate the mobile user to join an adjacent AP without interruption to the connection.
Reserving resources at several or all neighboring APs causes a deflnite wastage of resources
leading to under-utilization of the network. Moreover, it may not be possible to allocate
resources at all neighboring APs to all the current users in the present AP. Hence, some kind
of prior knowledge of a mobile user?s next destination is helpful in allocating resources. This
process is called mobility management.
Cellular providers have performed tracking of user locations to facilitate channel as-
signment, paging, etc. This kind of continuous real time tracking is necessary in a cellular
system since the users are moving at very high speeds. Such continuous tracking is resource
intensive and not necessary in a WLAN network since most users move at pedestrian speeds.
Slow moving users in a wireless network ofier better localization techniques, alternate han-
dover schemes to endure seamless handofis, etc but ofier other challenges such as disjoint
WLAN networks and random mobility. In this dissertation, towards this goal of efiective
resource allocation, we propose a method of predictive mobility management based on a
control theoretic approach. We propose a method of mobility prediction, i.e., predicting
a mobile user?s next location. We make use of a prediction algorithm that can accurately
estimate the next location visited by a mobile user, given current and historical movement
information. Further, a feedback control system provides information regarding network re-
source and utilization for better overall resource management. A brief overview of this thesis
is presented in the subsequent section.
1.2 Organization of this dissertation
This dissertation is organized as follows.
Mathematical mobility models are an e?cient and simple means to validate network
protocols and algorithms. In Chapter 2, we lay the groundwork for studying mobility in
3
networks. We shall discuss the methods of mobility simulation in network models, advan-
tages and disadvantages of existing mobility models and a thorough performance analysis of
mobility models under difierent routing protocols.
Chapter 3 deals with methods of predicting mobility in wireless local area networks
(WLAN). In spite of the advantages of using mobility models, we shall use real-world wire-
less trace data to perform simulations. This chapter provides several methods to perform
mobility prediction such as Markovian, Neural Learning methods, etc. We have analyzed
the performance of Markovian methods with regard to mobility prediction. A flrst order and
a kth order Markov model are studied. Hidden Markov Model and Neural Network models
are proposed to perform mobility prediction.
Modeling and prediction of user mobility is studied in Chapter 3. To use the prediction
model efiectively to dynamically allocate resources in the network, we propose a control
theoretic approach to resource allocation in Chapter 4. A feedback based control system is
designed to operate with the network prediction scheme. The proposed scheme is studied
both mathematically and experimentally using Monte Carlo simulations. The scheme has
the advantage of being incorporated into existing WLAN architectures. To our knowledge,
this is the flrst time control theory is used for studying the efiect of mobility on mobile
network performance.
Chapter 5 provides a discussion on interference caused due to mobile users in the net-
work. Expressions for aggregate interference on a wireless user from other cells are obtained.
Also, efiects of mobility average instantaneous number of mobile users in a cell and proba-
bility of crossing over to adjacent cells are taken into consideration. Analytical results are
obtained for interference statistics under various mobility models.
4
Chapter 2
Simulation Study of Mobility Models
2.1 Overview
Modeling Mobile wireless networks poses certain challenges that make real prototype
implementations very di?cult. Some of these are rapidly fading channel characteristics, dy-
namic topologies, fast user movements, etc. However, these challenges can be addressed by
performing a simulation study of such characteristics. Hence a practical method for eval-
uating the characteristics of networks is through the use of computer simulation methods.
Simulation provides researchers with a number of signiflcant beneflts, such as parameter
abstraction, multi-level views for difierent tests, etc. A strong simulation based on realistic
scenarios provides better insight into understanding the performance of these networks. It
is vital for robust network design to understand network performance under difierent net-
work protocols, varied physical conditions, repeatability in experimental setups and mobility.
Also, a large variety of realistic scenarios and network conflgurations/deployments can be
evaluated through simulation. Characterizing these parameters are extremely hard in real
network setups. Hence, simulation is the most popular tool for studying and analyzing the
performance of networks.
Simulation also has other key advantages such as providing a deeper insight into how
parameter changes such as mobility, speed or mobile users, etc impact end user performance.
Simulation facilitates parameter isolation which helps study the efiects of a single parameter,
such as mobility, transmission range, etc. while other metrics may remain unchanged.
A network simulator provides the advantage of simulating network mobility which is the
central idea proposed in this dissertation. After the initial placement of nodes, the ?mobility
model? governs how the nodes move during the course of the simulation. It is this feature
5
that is useful for our purposes. In this chapter, we discuss the details of several mobility
models and their efiects on simulation.
2.2 Motivation for using Mobility Models
As discussed in the previous section, mobility models provide beneflts in simulating node
mobility. They are mathematical algorithms that try to model the behavior of real movement
patterns. The mobility model has to be designed to describe the actual movement pattern
of mobile users, their geographic location, speed, etc. Since mobility patterns may play
a signiflcant role in determining the protocol performance, it is imperative that network
protocols [7] [8] [9] be tested for mobile conditions too. Otherwise, the observations made
and the conclusions drawn from the studies may be misleading. Hence, when evaluating
Mobile Ad hoc Network (MANET) protocols, it becomes necessary to choose the appropriate
mobility model for a particular scenario [10].
The mobility model is designed to describe the movement pattern of mobile users, and
how their location, velocity and acceleration change over time. Since mobility patterns may
play a signiflcant role in determining routing protocol performance, it is desirable for mobility
models to emulate the movement pattern of targeted real life applications in a reasonable
way. Otherwise, the observations made and the conclusions drawn from the simulation
studies may be misleading or erroneous. Hence, while evaluating network protocols, it is of
great importance to choose the correct mobility model that suits the real world scenario [11]
[12] [13].
2.3 Existing Mobility Models
Mobility models for simulations are implemented as discrete movements of nodes that
adhere to certain mathematical rules such as node densities, initial statistical distributions,
etc. The initial statistical distribution of nodes may follow uniform, Gaussian or any other
distribution. Once the nodes have been initially distributed, the mobility model dictates
6
the movement of the nodes within the network. Because the mobility of the nodes directly
impacts the performance of routing protocols, simulation results obtained with unrealistic
movement models may not correctly re ect the true performance of the protocols.
The topology and movement of the nodes in simulation are key factors in the perfor-
mance of the protocols under study. Initial distributions, node velocities and successive node
positions relative to previous locations need to realistically model real-world movements to
obtain a true performance metric from the simulation study.
Several mobility models are used in network simulations. Some are very generic and
are usually applied to a wide variety of scenarios. Others however may be tailor made
for a very speciflc case and node movements modeled as the case may be. Hence, it is
important to understand that there is no one-model-flts-all mobility model. Also, there
are other properties of mobility models such as the stationary distribution (i.e., where the
nodes spend most of the time) and average velocity that help decide the right model for the
simulation.
Mobility models can be broadly divided as random models and dependent models. Ran-
dom models are those whose parameters such as velocity, direction, etc are based on random
processes. On the other hand, dependent mobility models have parameters dependent on
geography, location, direction, clustering, etc. A classiflcation of mobility models is shown
in Figure 2.1.
To model random mobility in simulations and experiments, random mobility models [14]
are extensively used in mobile networks. Other random parameters such as speed, direction,
etc [15] [16] [9] have also been considered. Some of the commonly used mobility models in
simulation are Random Way Point Model (RWP), Random Walk model (Brownian motion),
Random Direction and Random Trip mobility models. However, there is still no way to use
these directly on a single users movement to predict a users next position.
In the subsequent sections, we shall discuss the performance of some of the popular
mobility models, their mathematical properties, strengths and limitations.
7
Mathematical 
Mobility Models
Random 
Mobility Models
Models with
Dependencies
Random
Way Point Random Direction Random Walk
Geographic
Dependency
(Manhattan)
Spatial
Dependency
(RPGM)
Temporal
Dependency
(Gauss-Markov)
Figure 2.1: A classiflcation of mobility models in literature
2.3.1 Random Way Point Mobility Model
Random Way Point (RWP) mobility model is a simple synthetic mobility model not
based on any actual traces. It is very easy to implement, easy to derive analytical results
and can be described using very few parameters. The key features of RWP mobility model
are random velocity of node movements and pause times between changes in direction and/or
speed. A mobile node moves from one location to another for a certain period of time with
a random velocity given by a uniformly distributed interval [0;vmax]. Then, it pauses for a
period of time Tp. After this, it once again chooses a random destination in the simulation
fleld and moves towards it at a new velocity. The process repeats again indeflnitely to
simulate node movement.
The RWP is a random mobility model where the node moves randomly without restric-
tions. In essence, the destination, velocity, pause time and direction are all chosen randomly
8
X0
X1
Xn+1
Xn
Figure 2.2: Sample movement of nodes in a Random Way Point mobility model
and independently of other nodes. A flgure showing an example of random movement of a
using following RWP mobility model is depicted in Figure 2.2.
Properties of Random Way Point Model
RWP mobility model is one of the most widely used mobility models in simulation.
Since it is extensively used, a thorough analysis of the mathematical properties of the model
is presented in this section.
The two main parameters in RWP are Vmax and Tp. A very low Vmax coupled with a
high Tp results in a reasonably static topology. However, if Vmax is large and Tp is small,
9
then the topology is dynamic. This results in frequent changes in routing paths and neighbor
node information tables.
RWP Model has some inherent deflciencies, most important of which is non-stationarity
as has been recently shown [5] [17] [18] in some research efiorts. A key property desired
in a mobility model is stationarity. Stationarity means that statistical properties such as
mean, variance and the probability distributions remain constant at all times during simu-
lation. However, in RWP model, the average speed of the nodes is consistently decreasing.
A common problem with simulation studies using RWP is a misleading choice of velocity
distribution, i.e., U(0;Vmax). Often, the model is described as having an average speed of
Vmax=2. This model is expected to maintain this average speed as the simulation progresses,
and simulation results are almost always in the form of an average over a period of time.
Such averages only make sense if the simulation reaches a steady state. Unfortunately, this
is not the case. In fact, over a large interval of time, speed decay will cause node veloc-
ity to become zero. With increasing simulation time, the speed of the nodes will have an
exponential distribution [19] [15]. Hence what started ofi as a uniform distribution will
change with time to an exponential distribution and hence does not satisfy the condition of
stationarity [18] [20].
Also, it sufiers from border efiect which means that nodes pass through the center of
the simulation area with a greater probability than any other area. However, it is sometimes
still widely used since the decaying efiects are only observed during long simulations.
Consider the average speed of a node as Vav.
Vav = lim
T!1
1
T
Z T
0
v(t)dt
= lim
T!1
PN(T)
n=1 dnP
N(T)
n=1 sn
10
= E[D]E[S]
= Vmax ?Vminln(Vmax
Vmin)
Here N(T) is the total number of trips a node takes in time T and dn and rn are the
distance and travel time in the nth trip. We notice that E[S] ! 1 as Vmin ! 0 and hence
Vav ! 0 as Vmin ! 0.
Let us consider the initial average speed as Vin. Vin may be given by the relation
Vmax+Vmin
2 . Now comparing Vav and Vin, we have
Vav
Vin =
Vmax?Vmin
ln(VmaxVmin )
Vmax+Vmin
2
Let
? = VmaxV
min
> 1
Vav
Vin =
2(??1)
(?+1)ln?
This relation shows that Vav < Vin which means that the average node speed over time
is less than that of the initial average node speed, which proves the non-stationarity property
of the speed distribution.
We have performed a long simulation using RWP model under the above described
conditions. The model is initialized with a velocity distribution [0;vmax]. The average speed
of the nodes at the end of the simulation is shown in Figure 2.3.
A simple workaround to this problem is to set a non-zero minimum speed. Hence, the
velocity distribution may be considered to be [Vmin;Vmax] where Vmin > 0. Another common
problem with the RWP model is zig-zag trajectories. This usually does not correspond to
any kind of mobility path in the real world.
11
0 500 1000 15000
1
2
3
4
5
6
7
8
Simulation time in seconds
Average instantaneous velocity (m/s)
Figure 2.3: Average instantaneous velocity in meters/second as simulation progresses
2.3.2 Random Walk Mobility Model
Random Walk mobility model is a derivative of Brownian motion as formulated by
Albert Einstein [21]. Brownian motion [22] describes the movement of particles in a liquid
(in 3 Dimensions). For most simulations, the 2-D model is used to represent the motion of
mobile nodes in a fleld.
The Random Walk model is similar to the RWP model in certain ways. The node
movement has randomness in both the models. However, the Random Walk model is the
RWP model with zero pause time. According to the Random Walk model, a mobile node
chooses a random direction and a random speed to travel and moves to a new location.
However, the speed and angular direction of motion are dictated by the limits [vmin;vmax]
and  (t) from [0;2?] respectively. The speed distribution may be Uniform or Gaussian. Each
discrete movement in the Random Walk Mobility Model occurs in a constant time interval
12
?50 ?40 ?30 ?20 ?10 0 10 20
?120
?100
?80
?60
?40
?20
0
20
40
Figure 2.4: Characteristic movement of nodes in a Random Walk mobility model
t or a constant distance traveled d. During the time interval t, the node moves with the
velocity vector given by [v(t)cos (t);v(t)sin (t)].
For the next movement, a new angle and speed are chosen. On encountering the simu-
lation boundary, the node moves away from the boundary depending on the incident angle,
i.e. with an angle ? ? (t) called boundary efiect. Since the Random Walk Mobility Model
is memoryless, it has no information of its previous locations and speeds. Hence, this can
lead to some impractical mobility patterns.
Figure 2.4 shows a representation of a random walk mobility model.
13
2.3.3 Random Direction Mobility Model
The random direction mobility is perhaps the most widely used mobility model other
than the RWP model. This is because it also considers user movement along straight line
paths, constant velocities and pauses in between motion segments. We discussed in the
previous section the RWP model, the spatial distribution of mobile nodes changes from a
uniform distribution to that of a non-uniform distribution during the simulation. At the end
of the simulation, the density of nodes is much higher at the center of the simulation area
and almost non-existent at the boundaries.
TheRandomDirectionmobilitymodelhasbeendesignedtoovercomethenon-stationarity
problem in the RWP Mobility Model. In this model, instead of a random destination as in
RWP model, nodes only choose a random direction in which to travel. After choosing a
random direction, a node travels to the border of the simulation area in that direction.
When the boundary is reached, the node pauses for a certain period of time, chooses another
angular direction in the interval [0;?].
For a movement area of size A, the sojourn density by one node using this model
is ?(x) = 1A for the whole movement area and the mean user movement is zero since all
movement directions are equal and hence cancel each other. Hence the mobility model
possesses the desired property of stationarity. This model is used for simulation studies
of mobile cellular networks since the design of cells and mobile hot spots within the node
movement area does not afiect the simulation results. However, one of the drawbacks of
the random direction is its behavior at the boundary of the simulation area. Realistically
characterizing the movement at a boundary is a complicated process. Analysis of the model
is di?cult due to the non-linear factors introduced by such movements.
There also exist several other variations of the random direction mobility model. The
waytheseversionsvaryfromoneanotheristhemethodinwhichtheygeneratethesubsequent
movement segment. One version proposes [23] a method that models a cell structure with
users passing the cell in straight lines. They choose new directions at cell borders. Other
14
versions model direction changes happening anywhere in the movement area with minor
difierences to suit other scenarios [24]. Some approaches characterize the direction change
with absolute angles while some others determine relative angular changes with respect to
the current direction [25].
2.3.4 Other Mobility Models
There are several other mobility models that have been proposed to suit certain speciflc
scenarios. In this section, we shall discuss some of the dependent mobility models as shown
in Figure 2.1 and their beneflts in simulation.
Group Mobility Models
Real world scenarios usually involve cases where groups of users move together. There
is a high correlation in the relative spacing of the nodes which can determine that it is group
common. This is called group mobility. An example is a group of soldiers on the battlefleld
where they move together on the same mission. Other simple examples include a group of
students taking the same classes or a family on a outing, etc where they usually move in
groups.
In a group mobility model, the node movement is relative to a reference point amongst
the group of nodes it belongs to. An example of a group mobility model is the Reference
Point Group Mobility model (RPGM).
However, there are certain di?culties in realistically using group models for simulation.
Most group mobility models such as RPGM implicitly assume permanent group a?liation.
In most cases, it is also understood that each node only belongs to a single group. But in
reality, to model more complex scenarios, a more comprehensive model is required. Some
nodes move in groups while others move independently. Some nodes may even be stationary.
Moreover, the group a?liation is not permanent. A good realistic mobility model must
capture all these mobility dynamics in order to yield realistic performance evaluation results.
15
Manhattan Mobility Model
Manhattan mobility model is a grid-based mobility model that attempts to mimic the
movement of users in a city section. This mobility model was mainly proposed for modeling
node movement in urban areas where the streets are organized as a grid. This are used
widely for vehicular movement modeling in city scenarios.
In this mobility model, the mobile nodes move in horizontal or vertical direction on an
urban map. The Manhattan model employs a probabilistic approach in the selection of node
movements. At each intersection, a node continues to keep moving in the same direction or
takes a turn based on some probability distribution. However, the model may be altered
to suit difierent scenarios where probabilities to choose certain streets over others may be
higher.
The Manhattan mobility model is an example of a geographic mobility model. It can
be overlaid over a city map and made to accurately model the movements of mobile users
in a city. Figure 2.5 shows an example of a layout of movements according to Manhattan
mobility model.
2.3.5 Shortcomings of Mobility Models
Mobility Models have been designed primarily using mathematical properties such as
stationarity. Some of these models may not re ect any realistic scenarios. RWP model and
other random based models model provide perfectly random movements. However, users
in the real world may not move so randomly at all. Also, most research has focused on
designing protocols and network designs based on synthetic mobility models. Hence, results
and designs emanating from these efiorts may also be misleading or erroneous.
There are also other parameters in the real world that are di?cult to create in a mobility
model. Obstacles are a di?cult deterrent for user movement. However, realistic obstacle
creation and modeling user movement when they encounter obstacles is not as easy in a
16
Figure 2.5: Characteristic movement of nodes in Manhattan mobility model
17
mathematical mobility model. However, Geographic Information Systems (GIS) may provide
real terrain data that may be overlaid onto a simulation scenario.
Perhaps the most important problem with synthetic mobility models are incorporating
temporal and spatial correlation amongst users. As we discussed, not all user movement is
random. The way users move may be dependent on other nearby nodes, the time of the day
and the location they are in. Hence memoryless mobility models defeat the purpose when
simulating such scenarios.
Inspiteofalltheseshortcomings, mobilitymodelsdoprovideaneasywaytotestnetwork
protocols. Also, other issues such as scalability and tra?c  ow characteristics which cannot
be realistically tested in a real-world deployment may be tested in a simulation setup.
2.4 Performance Analysis of Mobility Models
The mobility models discussed in the preceding sections have been used extensively in
simulations. In this section, we discuss some of the network models used to test the protocols
and mobility models and the performance issues involved in using the models.
We use ns2 (version 2.28) [26] to simulate the efiects of node mobility. The network
architecture for simulation is described below.
Several mobile nodes are randomly distributed in a square geographical area. These
nodes are equipped with radios that can communicate with other nodes using one of several
protocols such as Ad Hoc On Demand Distance Vector routing(AODV) [27] or Dynamic
Source Routing (DSR) [9].
To better connect the nodes in the network, a backbone comprising of better equipped
nodes to perform back end operations is assumed to exist. We assume sparsely distributed
powerful radios in the same region to provide a backbone network to the mobile nodes. These
are stationary and are better powered, long lasting and more robust. Nodes are categorized
into groups called clusters. They act as cluster heads, coordinating local node activities,
inter-cluster communications, etc thereby providing some scalability to the network.
18
Cluster Head
Mobile Node
Figure 2.6: Network architecture comprising of mobile nodes, clusters and cluster heads
When the network is initialized, the mobile nodes identify the nearest cluster heads as
shown in Figure 2.6 and are associated with that cluster. Hence all mobile nodes belonging
to a particular cluster only transmit to the cluster head. In turn, the cluster head transmits
to neighboring cluster heads and hence propagates information to the sink.
NodemobilitymodelssuchasRWP,randomwalkandrandomdirectionareimplemented
in the simulator. All node movement is characterized by the mobility model. Due to mobility,
the nodes move out of range of the nearest cluster head node and hence move into a new
cluster. The overhead in joining the cluster and conflguring new routes to the cluster head
19
node lead to more delays and dropped packets. To simulate the overhead of joining a
new cluster, the mobile nodes have a flxed latency which is used to conflgure to the new
cluster head. This includes the time required for local broadcasts, route requests, route
conflguration, etc. High mobility involves frequent joining and leaving several clusters.
2.5 Results
The algorithm performance is evaluated through a simulation study using some of the
mobility models. We test various routing protocols and their performance under difierent
mobility conditions.
Mobility models are studied under the in uence of the overlying network routing pro-
tocols. The flrst study involves using the Dynamic Source Routing (DSR) protocol [9] and
testing various mobility models. In this experiment, the efiects of Random Direction, Ran-
dom Way Point and Random walk on DSR are studied. The nodes move anywhere from 5
to 25 meters per second. As we can see from Figure 2.7, Random Direction performs the
best while Random Way Point performs the worst. However, the delay associated with the
Random Way Point model is low and it provides almost 90% packet delivery rate at lower
speeds. In Figure 2.8, we see that the delay is normalized and RWP performs very well.
Also, it still performs better than the other random models at higher speeds. Random di-
rection model performs the worst with the highest number of packets dropped even at very
low speeds. However, the DSR protocol is ideal in cases where the node remains in a cluster
for su?cient amount of time to determine the routing paths.
Since RWP is widely used in many simulation studies, we analyze the efiects of RWP
on multiple routing protocols. DSR and AODV routing protocols are implemented to re-
lay information to the sink. The node mobility model used is the RWP mobility model.
Simulation is performed for 1000 seconds of simulation time and results are averaged over
several runs. As we see in Figure 2.9, in spite of the cluster identiflcation overhead and
delay, DSR performs best with RWP model. However, the throughput drops noticeably if
20
Figure 2.7: Performance of DSR protocol for various mobility models; RWP gives best hop
count in simulation results for DSR
the number of hops increases. This is because of the increase in packet size since the whole
path has to be preflxed to the data payload. These results are in slight variation compared
to the non-hierarchical network architecture. Due to constant association and disassocia-
tion with clusters and routing overhead, these protocols perform only slightly worse than in
non-hierarchical networks.
Next, we compare RWP and Random Walk mobility models using DSR and AODV
protocols. DSR performs well for both mobility models achieving a throughput of about 90%
in both cases. However, AODV performs the same as DSR for Random Walk model. The
performance of these routing protocols in a cluster also depends on the cluster size. A higher
node density in a cluster leads to more latency for DSR. This is due to the proactive nature
of DSR which requires every node to broadcast periodically and store routes in cache. With
fast mobility, the cache routes become stale leading to frequent broadcasts. Hence AODV
performs better if there are more nodes.
21
Figure 2.8: End to end delay packet transport for Dynamic Source Routing protocol
Figure 2.9: Packet delivery ratio for Random Way Point mobility model
22
Figure 2.10: Efiect of node density on network delay
To compare the efiect of high mobility on packet delivery rate for difierent mobility
models, we simulate Constant Bit Rate (CBR) tra?c in the network. As we see in Figure
2.12, DSR performs best at lower speeds and its performance degrades drastically at higher
speeds. At much higher speeds, the packet delivery ratio is almost the same for many pro-
tocols and is very bad at about 50%. However, DSR performance sufiers from simultaneous
tra?c  ows. With multiple CBR tra?c  ows, each  ow being 32Kbps, in the same cluster
with a high density of nodes, DSR performance drops below that of AODV.
Compared to a static network, we observe a signiflcant drop in network throughput
when adopting DSR and AODV protocols with the speed of the mobile nodes. If the speed
is low, then DSR works better due to valid routes in the cache. Higher mobility leads to
obsolete route caches very often. Hence as we see in Figure 2.10, AODV performs better in
cases of higher mobility.
23
Figure 2.11: Packet delivery ratio for Random Way Point mobility model
Figure 2.11 shows the packet delivery ratios for difierent protocols using RWP Model.
Also, tra?c overhead as a percentage of goodput is much higher for AODV since high
mobility leads to frequent broad- casts and route discoveries for DSR. Also, periodic message
exchanges and mobility leads to worse performance of DSR in higher mobility scenarios.
DSR packets have to carry considerably more routing information which leads to drop in
throughput at higher tra?c  ows.
Choosing the right mobility model
Having discussed various mobility models and their suitability to various scenarios, it is
of utmost importance to choose the right mobility model for the desired simulation scenario.
RWPmodelsandRandomWalkmodelsmayprovideaflrststeptotestmostadhocnetworks.
More complex settings and parameters can be included in the simulation setup. However,
care must be taken to maintain stationarity and randomness in the simulation.
24
Figure 2.12: Packet delivery ratio for various mobility models using Dynamic Source Routing
protocol
Figure 2.13: Efiect of tra?c  ows on throughput for Random Walk mobility model
25
For instance, DSR is a source routing protocol. The distinguishing feature of this routing
protocol is that it routes routes packets on demand. A source routing protocol is one where
every packet contains the complete route information, i.e., a list of nodes in the order that
the data packet should traverse through in its header. In an On Demand routing protocol, a
routing path to a destination node is obtained only when there is data to be sent. We chose
DSR and AODV since they perform well in many of the experimental evaluations of routing
protocols.
From the results however, we flnd that in spite of their best features, the routing pro-
tocols can fail to provide the desired results under the wrong mobility conditions. Hence
mobility models and real world mobility conditions decide which protocol should be used
under various scenarios.
2.6 Mobility Models vs other methods
In spite of the specialized mobility models used in simulation studies, it may sometimes
not be suited for certain applications. This may be due to the fact that certain real world
scenarios cannot be replicated in a simulation setting. Also, scalability issues, unforseen
circumstances such as outages, network disruptions may not be reproducible in a controlled
computer simulation.
Hence, in such cases, it may be better to choose a simulation study using data from
an existing real-world system. Such data are called data traces. Data traces and their
characteristics are dealt with in greater detail in the next chapter.
2.7 Discussion
We have evaluated the performances of various mobility models using a couple of routing
protocols. These results provide an insight into the understanding of protocol performance
under mobile conditions. Most clustering algorithms deal with static or slowly-changing
topologies. Hence this study of routing protocols with mobility helps in understanding the
26
behavior of mobility. We have determined that DSR performs better under lower mobility
while AODV performs in high mobility and higher tra?c  ows. In a dense network with
several simultaneous  ows, AODV achieves lower delay and higher throughput. Also, this
study demonstrates the scalability of a routing protocol with respect to mobility.
27
Chapter 3
Mobility Prediction
3.1 Introduction
Predicting a mobile user?s next location before the actual movement is termed as mo-
bility prediction. Accurate and fast mobility prediction methods are an important topic
of research due to the emergence of ubiquitous wireless networks and increasing number
of users. The ability to track and predict a mobile user?s location is important from the
perspective of network management for today?s mobile systems and applications. Mobility
prediction becomes all the more important since its efiect can be seen at multiple levels of
the network.
At the network level, mobility can in uence handofi management, bufier and  ow
control, adaptive resource allocation [28] and congestion control, call admission control,
and quality of service (QoS) provisioning [29] [30]. In the application level, better mo-
bility prediction techniques can greatly in uence the efiectiveness of location aware ser-
vices [30] [31] [32] [33]. Prediction can be helpful in keeping track of the proflle and location
of users.
In order to ensure timely handofis, we need to allocate resources at neighboring APs to
facilitate the mobile user to join an adjacent AP without terminating the connection (i.e.,
minimize call dropping probability). Reserving resources at several or all neighboring APs
causes a deflnite wastage of resources leading to under-utilization of the network. Moreover,
it may not be possible to allocate resources at all neighboring APs to all current users in
the present AP. Hence, prior knowledge of a mobile user?s next destination is helpful in
allocating resources. This process is called mobility management. Slow moving users in a
wireless network ofier better localization techniques, alternate handover schemes to endure
28
seamless handofis, etc but ofier other challenges such as disjoint WLAN networks and random
mobility.
3.2 Motivation
Mobile users exhibit regularity in their movements. Human beings are habitual in many
ways and there is a regularity even in the randomness of movement. For instance, a mobile
user moving along a straight path is highly likely to follow the same path until he encounters
some intersection. Also, users tend to move in a non-random path and follow other landmarks
such as straight roads, better paths, etc. To predict the mobility of a user, we can exploit
the user?s movement patterns, past habits, historic mobility proflles, etc.
Mobility prediction can also help develop a snapshot of the future network topology and
allow for smooth transition into topology changes. Also, in ad hoc networks, new routing
paths can be formulated ahead of time and routing overhead reduced.
Mobility prediction techniques are commonly based on historical movement patterns of
the user populations. Predictions can be for the next step of mobile user movement or for
a whole sequence of movements. There are also separate advantages of performing mobility
predictions from the client?s or the AP?s perspectives.
3.3 Existing Methods of Mobility Prediction
Several mobility prediction schemes have been proposed in the literature to tackle the
problems of handover management in wireless management. Mobility prediction algorithms
make the assumption that there is a certain regularity in the mobility patterns which allows
for prediction using certain metrics such as velocity, current location, direction, etc. Almost
all prediction algorithms rely on the fact that user movements are based on some pattern
and are not completely random [34] [35] [36] [37]. Prediction schemes are beneflcial to many
applications and several such predictors that have been proposed are discussed in this section.
29
Predictive mobility management algorithms for supporting mobile communications [38]
employs detection algorithms to decompose the complicated daily movement into two parts:
regular pattern part and random movement part. The Movement Circle and the Movement
Track model [38] have been proposed and used to predict the regular movement while the
random parts of the movement are modeled and predicted by the Markov chain model.
Proflle-based prediction [39] is a mobility prediction method to address indoor move-
ments in places such as corridors, rooms, etc. It classifles motion into several categories
such as deterministic, random, purely random, etc. Since it is an indoor prediction, it can
guarantee QoS by reserving resources even in highly random scenarios.
Mobility Prediction methods modeled on historic movement proflles [1] [15] based on
the compression algorithm by Lempel-Ziv [40] have also been studied. The LZ (Lempel Ziv)
algorithm considers movement patterns to be generated by a flnite-state Markov source. In
this model, the subsequent symbol is dependent only on the current state of the system.
Then a LZ tree is constructed with nodes comprised of the most recent locations visited by
the user [41]. To predict a user?s next location, the tree is traversed and the most frequently
seen path is chosen.
Blough. et al [42] propose a class of domain independent location predictors that do
not require any semantic knowledge of their locations. Only past movements are studied to
perform predictions. The principal conjecture is that there exists a temporal regularity in
the node movements. These movements are modeled to predict user movements.
A more simplistic form of Lempel Ziv prediction is using a Kth order Markov predictor
[43]. In this method, the flnite state Markov source is limited to a speciflc K. The authors
here have used a Markovian prediction model on a data trace set collected at Dartmouth
College. The model?s performance was reported to be as good as that of the LZ predictor
without the complexity of building a LZ tree. Also, the O(2) model provides an excellent
accuracy compared to even higher order Markov models.
30
Most of the discussed methods of mobility prediction use only historic mobility data to
perform prediction. Also, almost all of them are stand alone prediction models that have
not been analyzed as part of a complete network management system.
Only few mobility prediction algorithms exist that address network resource issues in
conjunction with mobility prediction. One such algorithm proposed for resource manage-
ment assumes a cooperation architecture and mobility management functionality. In this
policy based mobility management technique [44], problems such as difierentiating highest
and lowest priority tra?c, guaranteeing delivery to priority tra?c (based on QoS metrics),
guaranteeing resources such as bandwidth, etc. Location determination can also be factored
into the algorithm by using difierent positioning methods. Further, this work describes
other actions executed by the implemented policy-based mobility management scheme like
radio access technology association, user and  ow context transfer, handover decision, and
deployment priority. The framework also shows how the difierent deflnitions of the mobil-
ity management relate to each other. Also, several other prediction schemes such as those
in [45] [46] try to tackle certain issues such policy based user movements. Other studies
include speciflc scenarios such as studying the nature of campus networks and the efiect of
mobility on such networks [47] [48] [49].
3.3.1 Challenges in Mobility Prediction
Having studied the mobility models, we can see that there exist several key challenges
that constrict fast and accurate mobility prediction. Some of the challenges are summarized
below.
1. Accurate mobility prediction depends on several factors such as complete knowledge
of the network topology, mobility habits of users, etc.
2. Most prediction models depend on building a mobility proflle of the user. A complete
proflle development of a mobile user is not feasible and hence a 100% accuracy is
impossible.
31
3. Better prediction is possible for more regular users. Also, users who show regularity
in movement can be predicted with better accuracy.
4. Data collection and system learning takes time and resources. For a completely new
scenario with no dataset, it takes time to build the models and train the mobility
management system.
5. User movement also depends on the spatio-temporal correlations of other variables; in
a campus setting, these may be the schedule of classes or the locations of users. having
complete knowledge of all these extraneous variables is usually very di?cult.
6. Even with all the techniques, regular users can sometimes behave unpredictably.
3.4 Mathematical Preliminaries
Inthissection, weshalldeflnesomemathematicaltermsandnotationswewillrepeatedly
use in this chapter.
A random process is the counterpart to a deterministic process [50]. Instead of dealing
with only one possible reality of how the process might evolve under time, in a stochastic
or random process there is some uncertainty in its future evolution described by probabil-
ity distributions. This means that even if the initial condition is known, there are many
possibilities the process might lead to, but some paths may be more probable than others.
A random variable x is a rule for assigning the output of a chance outcome fi to a
number x(fi). A stochastic process is a function of time of the random variable, i.e., x(t). It
is a rule that assigns the chance outcome fi to a function x(t;fi) [50] [51]. The domain of t
is the set R of all real numbers. If R is the real axis R, the stochastic process is said to be
a continuous time process and is discrete if R is the set of integers.
Common examples of processes modeled as stochastic time series include stock market
and exchange rate  uctuations, signals such as speech, audio and video signals, medical data
32
like a patient?s EKG, EEG, blood pressure or temperature, and random movement such as
Brownian motion or random walks.
3.4.1 Markov Chains
A Markov chain is a discrete random process with Markovian property [50]. Markov
chain is a term used to denote a Markov process that has a discrete state space. In other
words, it has a flnite number of states. A discrete-time Markov Chain is deflned for discrete
times. A discrete time Markov process signifles a system in which the system is in a random
state at each time slot and the state changes randomly between time slots. The Markov
property states that the conditional probability distribution for the system at the next time
slot given its current state depends only on the current state of the system. It does not
depend on any of the previous states of the system.
The system changes from one slot to another randomly. Hence, it is not possible to
predict the exact future state of the system. The statistical properties of the system help
predict the future steps which is what is used in several applications.
The changes of state of the system are called state transitions. Probabilities associated
with various state changes are called state transition probabilities. The set of all states
and transition probabilities completely characterizes a Markov chain. A completely deflned
Markov Chain has all states, state transitions deflned. Hence, the transition process could
go on forever since there is always a current state and a next state.
A Markov chain can be deflned mathematically using two components { a transition
matrix and an initial state distribution. A transition matrix is deflned as follows.
Assume a flnite set S = f1;:::;ng of states in a probabilistic system.
33
BA
C
a
d f
c b
e
Figure 3.1: A Markov Chain showing states, state transitions and transition probabilities
pij is the probability of transition from state i to state j in the system. Assign to each
pair (i;j) 2 S2 of states a real number pij such that the properties
pij ? 0 8(i;j) 2 S2 (3.1)
X
j2S
pij = 1 8i 2 S (3.2)
are satisfled. The Figure 3.1 shows a Markov chain with 3 states namely A, B and C
and the transition probabilities between them denoted by a;b;:::f.
We deflne the transition matrix A by
0
BB
BB
BB
B@
a11 a12 ::: a1n
a21 a22 ::: a2n
... ... ... ...
an1 0 ::: ann
1
CC
CC
CC
CA
Let (Xn)n2N0 be a sequence of random variables whose values lie in S. Here, n indicates
the time at which the system is in state Xn.
34
The sequence (Xn)n2N0 is called a homogeneous Markov chain with discrete time, state
space S, and transition matrix A,
if and only if 8n 2 N0 the condition
P
h
Xn+1 = j
flfl
flX0 = i0;:::;Xn = in
i
= P
h
Xn+1 = j
flfl
flXn = in
i
= pinj (3.3)
is satisfled for all (i0;:::;in;j) 2 Sn+2, for which
P[X0 = i0;:::;Xn = in] > 0 (3.4)
Equation (3.3) deflnes the memory or Markov property of a Markov Chain. In the
above example, the order of the Markov Chain is 1 since the transition probabilities are
only dependent on the preceding state. Also, the homogeneity condition ensures that the
transition probabilities are constant with time.
First order Markov chains can be extended to higher order Markov Processes. Higher
order processes with flnite memory s can be extended as being in the space Ss.
We also need to deflne the initial distribution of a Markov Chain to completely describe
it. The discrete set of initial distributions on the space S is deflned by
RS = fP = (Pi)i2S : Pi ? 0;
X
i2S
Pi = 1g (3.5)
P0 = (P0i)i2S 2 RS (3.6)
The relation (3.6) is known as the initial distribution of the Markov Chain (Xn)n2N0
if A[X0 = i] = A0i for all states i 2 S.
35
The ijth entry a(n)ij of the matrix An gives the probability that the Markov chain, starting
in state si will be in after n steps. The nth order transition probabilities are given by
p(n)ij = P[Xm+n = jjXm = i];n 2 N (3.7)
These are obtained by summing over all possible intermediate states. Paths of length
n+1 with initial state i and flnal state j are considered. Hence,
pnin =
X
(i1;:::;in?1)2Sn?1
P [Xm+n = jjXm = i;Xm+1 = i1 :::Xm+n?1 = in?1] (3.8)
=
X
(i1;:::;in?1)2Sn?1
pii1
n?2Y
j=1
pijij+1pin?1j (3.9)
(a(n)ij )(i;j)2S2 is the same as the n?th power An of the transition matrix A.
Also, a(0)ij := ?ij which leads to A0 equals the identity matrix Im. Hence, given A0 of
X0, the distribution of Xn leads to A0An, n 2 N0.
For A = (A1;:::;Am) 2 RS, we can deflne a Markov chain with state space S, transition
matrix A = (aij)(i;j)2S2 given by pij = Aj, i 2 S.
Let us also consider a random initial distribution A0 2 RS.
Also, 8n 2 N0,
A
h
Xn+1 = j
flfl
flX0 = i0;:::;Xn = in
i
= A
h
Xn+1 = j
flfl
flXn = in
i
= Aj (3.10)
This is called an \independent chain" with respect to the transition matrix A.
We have described the basics of random processes and Markov chains in this section. In
the following section, we propose some methods to model the mobility patterns as random
processes.
36
3.4.2 First Order Markov Model
In this section, we model the mobility patterns as a First Order Markov Process.
Consider a scenario where a mobile user is connected to an AP. Here we are assuming
a wireless local area network (WLAN) such as a network based on 802.11a, b, and g. The
network consists of access points (APs) and mobile hosts. The APs are connected to a
backbone network which may be connected o a wired data network such as the Internet.
The network serves both mobile and stationary users who may be equipped with laptops,
PDAs, internet-enabled phones, etc. The user may move away from this AP (say Aj) and
connect to an adjacent AP (Ak) after some time. The model proposed here attempts to
predict this transition from Aj to Ak ahead of the user?s movement by analyzing the history
and transition paths.
A Markov Chain model [50] towards this objective was studied in detail in [52] using
a campus wireless trace dataset. In this case, only the user?s previous movement is known.
For example, if the user moved to Aj from Ai, only this information is known to the system.
The system also has a knowledge of the probability of transition from Ai to Aj and Aj to Ak.
Using this information, the system predicts the transition of the user from Aj to some other
adjacent AP. There are several deflciencies in this model. For instance, the user?s path to the
current AP Aj may be from several paths but the last immediate AP could have been Ai.
These path transitions may be difierent for various users based on user movement histories
and the paths taken. Hence a more complex model is necessary to make more accurate
predictions.
In this context, a k-th Order Markov model where k > 1 is a logical extension to this
model. The system understands user movements for the past k transitions. For instance,
the user?s current location is modeled as a random variable Y and YiYi+1 :::Yk denoted by
Yik be the sequence of random variables. For example, a second order model is written as
P = P[APnextjAPcurrent;APprevious]
37
5 10 15 20 25 3010
20
30
40
50
60
70
80
90
Number Users
Percentage
Success RateFailure Rate
Figure 3.2: Initial Prediction success rate
Results
To validate the claims, we have mobile user-association data collected at an access point.
This dataset consists of 8 APs and a set of users who frequent these APs on a regular basis.
This data has been parsed to extract the AP and unique user information and the frequency
of connections between the users and the APs. The transition probabilities and the matrix
is built using this information. We now have the user history over a period of time and this
gives the probability of transition between any adjacent APs.
A random users information is used to test the accuracy of the system. The users
current AP connection is used and the system predicts the next AP connection that the user
moves to. This is validated against the actual movement from the data set. Accuracy and
false predictions are also noted. This experiment is repeated for various users several times.
Also, every time an accurate prediction is made, the transition probabilities are updated
to better re ect the user movement history. Some of the results from the experiments are
38
5 10 15 20 25 300
10
20
30
40
50
60
70
80
90
100
Number of Users
Percentage
SuccessFailure
Figure 3.3: Prediction Success rate after training
discussed here. Figure 3.2 shows the prediction success of the system modeled. In Figure
3.2, we see that with a smaller number of users and under initial conditions, the system
performs prediction with moderate success. By initial conditions, we mean that the users
data is barely enough to build a transition matrix and use the prediction algorithm. Hence,
there is a higher failure rate which indicates that the system is still learning from the users
movement data.
We perform a thousand iterations and feed the data into the prediction system; the
system learns from the inaccurate estimates and corrects the transition matrix accordingly.
After these iterations we can see the success rate in Figure 3.3. We can clearly see that the
Markov chain model is best suited to work under steady state conditions. The Figure 3.3
shows that the success rate is higher by about 15% and is consistently over 90%. Figure
3.4 shows the variation of transition probability stabilization. The three curves show the
probability variation for three difierent users. We can see that the three states shown in the
39
5 10 15 20 25 30 35 400
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Iterations
Probability of transition at state Xi
Figure 3.4: Transition probabilities of 3 states during the initial and steady states
flgure reach steady state conditions after a few iterations and the system accuracy improves
only after the steady state is reached.
3.5 Hidden Markov Model
Mobility patterns were modeled as a First Order Markov Model were seen in the preced-
ing section. We propose to model the same problem using a Hidden Markov Model (HMM).
A HMM is deflned by a flnite set of states (some hidden and some observable), a set of
state transition probabilities, an alphabet of output symbols (also referred to as emissions)
and a set of emission probabilities. The emission probabilities denote the distribution of
output symbols that are emitted from each state. There are several advantages to modeling
the solution to incorporate hidden states as opposed to a simple Markov Chain. In order
to understand the necessity to model a HMM, we flrst demonstrate the drawbacks of the
simple Markov chain model.
40
In the Markov Chain discussed previously, an observer (or another AP) may not be
able to observe all the transitions in a network. In other words, the observer may sometimes
only see the transition from APi to APj; however, some transitions could be hidden from
the observer by the system or by the user. For example, in places where a user may connect
to any one of multiple APs, the observer can only see the movement of the user from one
place to another but cannot determine which AP the user is connected to. In this case, the
APs are the hidden states and the locations are the observable states. Hence the problem is
to identify the APs corresponding to the location of the user.
In this section, the HMM and the method of using it to solve the problem of mobility
prediction are explained. There are several classical papers in the area of statistical source
modeling and speech recognition theory that have used the concept of HMM to model various
hidden parameters [53] [54] [55]. As explained earlier, it may be noted that only the outcome
and not the state is visible to an external observer. Hence the states are hidden from the
observer and the name Hidden Markov Model.
Figure 3.5: A Schematic of a Hidden Markov Model showing the hidden and observable
states, state transitions and probabilities.
41
A HMM is deflned by a flnite set of states, a set of state transition probabilities, an
alphabet of output symbols (also referred to as emissions) and a set of emission probabili-
ties. The emission probabilities denote the distribution of output symbols that are emitted
from each state. Figure 3.5 shows some of the probabilistic parameters of a HMM. HMM
is a stochastic process of moving between states and the process of emitting an output se-
quence. However, the sequences of state transitions are hidden and observed only through
the sequence of emitted symbols.
A HMM is formally deflned as follows.
1. S : fs1s2 :::sNg are the N hidden states in the system. Even though the states are
hidden, they have practical signiflcance as we shall see later in our discussion.
2. O : fo1o2:::oNg are the values of the observed sequences. They symbolize the discrete
alphabet size and represent the physical output of the system being modeled.
3. ? = f?g is the initial state probabilities. Here ?i indicates the probability of starting
in state i.
4. A = faijg are the state transition probabilities where aij denotes the probability of
moving from state i to j. In a system where a state can reach any other state in a
single transition, aij > 08i;j.
aij = P(tk = sjjtk?1 = si)
5. B = fbikgare the observation state probabilities where bik is the probability of emitting
symbol k at state i.
bik = P(okjtk = sj)
42
6. For ease of use, this entire model as shown in Figure 3.5 is denoted as ? = (?;A;B).
From the HMM, it is easily seen that there is no one-to-one correspondence between
the states and the symbols.
3.5.1 Prediction Model using HMM
The HMM is applied to the problem of mobility prediction in the following way. For
an external observer (such as another network or AP) to predict the movement of a user,
the APs are hidden and the user locations are the only visible observations. On the other
hand, suppose the network AP controller wishes to perform mobility prediction. From that
perspective, it can only see the APs and their associations with the mobile users. The actual
geographic locations of the users are ?hidden?. Hence this is a generic model that aims to
provide a framework for mobility prediction.
We approach this problem from the perspective of the centralized AP controller that
aims to collect information about mobile users and make mobility predictions to better
allocate network resources. All APs can all send user information to the controller which
stores the user histories, movement behavior and is capable of computations to make the
prediction.
A HMM ? as described earlier is built for each user by the AP controller. The data
for state transitions and probability transition matrices is ?learned? from the trace data as
explained in the subsequently. This HMM model can provide solutions to three problems as
explained in [53].
1. Observing the movement sequences over time, the HMM ? can give the probability
that a certain observed sequence O = o1;o2;:::oK came from this model.
This is given by probability that the observed sequence O was generated by the model
?
Let s = fs1s2 :::sKg be a state sequence. Also, let us assume that the observations
are independent. Hence,
43
P(Ojs;?) =
kY
i=1
P(okjsK;?) (3.11)
= bs1o1:bs2o2 :::bsKoK (3.12)
Probability of any state sequence is
P(sj?) = ?s1as1s2as2s3 :::as(K?1)sK (3.13)
Hence we have
P(Oj?) =
X
s
P(Ojs;?)?P(sj?) (3.14)
This metric is especially useful for our proposed model since such a probability would
help estimating the users movement over a longer run. Hence network resource alloca-
tion can be performed throughout the user?s movement in that network.
2. Suppose the observed sequence of movements is denoted by
o = o1;o2;:::ok
The most likely sequence of hidden states corresponding to these observed sequences
can help in determining the part of the user.
A solution to this problem helps in locating the hidden parameter in the model. In
a model with hidden user locations, the model can give the probability if a user is
located in a particular geographical area. Alternately, the external observer can also
determine which AP the user is most likely connected to, given that the user is within
44
range of certain APs. This is a maximum likelihood problem and can be solved using
the Viterbi algorithm [56] [57].
3. The last exercise is to determine the value of ? to maximize P(Oj?) i.e., to train the
model given a set of observations.
This is an important phase in the model since the model should be able to learn from
the user movement histories over time and make better predictions. Also, this is a
hard problem with no easy solution. It can however be computed iteratively using
the Baum-Welch algorithm [58] and computing new ? based on ?0 and given O. The
iteration stops when
logP(Oj?)?logP(Oj?0) < ? (3.15)
3.6 Experiments
We have established a mathematical model for mobility prediction. To test the validity
of the claims made, we perform simulation experiments. In this section, we describe the
simulation settings, mobility patterns and analysis.
3.6.1 Wireless Mobility Traces
We have earlier discussed methods of simulating mobility in computer experiments. Us-
ing mathematical mobility models does provide a flrst method of validating results. However,
using real-world wireless traces from the fleld ofier a more realistic environment for testing
protocols and mobility prediction models.
We have used a campus wireless trace dataset available online [59]. The CRAWDAD
wireless trace sets have been collecting wireless device association and disassociation mes-
sages in WLAN networks since early 2001. All connections to its wireless network have been
45
stored as trace flles which is a valuable mine of information. The trace flles contain the wire-
less Network Interface Card (NIC), MAC addresses and the time of connection/disconnection
for each access point. Since MAC addresses are unique, we can safely assume that each con-
nection/disconnection associated with a MAC ID belongs to a unique user and can be treated
as a mobile node.
The advantage of using this trace set is that it is being used by several other researchers
for experiments to study various aspects of social mobility, campus mobility, resource alloca-
tion, etc. The ubiquitous WiFi coverage on the university campus afiords a great opportunity
to study handofis and contiguous user mobility.
3.6.2 Mining Wireless Traces for Information
The wireless trace dataset contains user histories for thousands of wireless users. The
logged data, as described in the earlier section, consists of AP associations to multiple users,
MAC addresses of users, time stamps of associations and disassociations.
We have mined information such as the number of unique wireless network users, their
association with the number of APs in the networks, the probability of transitions from one
AP to another, etc from this trace dataset. We have used this data to perform simulation to
verify the accuracy of the model versus actual movement, study user movement, prediction
beneflts, etc.
3.6.3 Trace Sets as HMMs
Wireless trace sets have provided a unique opportunity to study mobility patterns across
a campus. Parsing information from a trace dataset is non-trivial. However, an even harder
task is to import the data into the models that we have proposed.
The proposed HMM is a doubly stochastic process that consists of hidden and observable
states. The trace sets can be used to model the observable or the hidden states depending on
the scenario. Suppose we visualize the network data from the perspective of the access point,
46
Enterprise WLAN Network
AP1 AP2 APn
AP12
Figure 3.6: APs and the connected mobile users. User AP12 can be connected to either AP1 or
AP2
we can only see the users connected to difierent access points. We have no way of knowing
where the users are geographically located on a map. This is because several users at the
exact same location may connect to one of several access points. Hence, we can conclude
that all users connected to an AP are not at the same place. Here, the access points are the
observable states and the location of the users are the hidden states.
On the other hand, suppose we can determine the exact location of the users, we can
model the problem to be determining the most likely access point the user will connect to.
Now, the users are the observable nodes and the access points are hidden.
Hence, modeling the problem as a HMM lets us conveniently redeflne the problem based
on the available data.
47
In Figure 3.6, we see the coverage of the APs and the wireless users connected to the
APs. There is an overlap in the coverage areas of AP1 and AP2. Hence, a user location in
the overlap area such as AP12 could be connected to either AP1 or AP2.
3.7 Results
The model proposed in the previous section has been simulated extensively to verify the
claims. The data from the trace sets is imported into the model for the purpose of building
the HMM. Aspects such as wireless user transitions from one access point to another are
considered as mobility. Thus, the transition probabilities for the user with respect to those
access points are reinforced. The developed prediction engine based on HMM is tested for
accuracy in predicting the future mobility of users. Some of the results are brie y discussed
below.
We have used a campus wireless trace dataset available online [59]. This dataset contains
wireless user histories such as user associations with APs, duration of association, etc. From
this dataset, we have mined a lot of information such as the number of unique users, their
association with difierent APs, the probability of transitions from one AP to another, etc.
Using this data, we have performed some analysis to verify the accuracy of the model versus
actual movement, study user movement, prediction beneflts, etc.
One main observation that we make from the dataset is shown in Figure 3.7. We see
that most users always connect to only one or two APs regularly. These kind of behavioral
issues in uence the prediction and make it harder to predict users? next location.
The prediction accuracy is one of the most important metrics for the veriflcation of this
model. Figure 3.8 shows the prediction accuracy for several users across various APs. There
is large variance across the users and APs. This is because of the ?preferred? tendency of the
users to connect to a certain AP.
As mentioned earlier, Figure 3.9 shows how sequence length afiects prediction accuracy.
The accuracy decreases as sequence length increases due to the nature of the dataset as
48
0 2 4 6 8 10 12 140
10
20
30
40
50
60
70
80
90
Access Point Index
Percentage of Time Connected to AP
User 1User 2
Figure 3.7: Percentage of time connected to difierent APs
0 2 4 6 8 10 1230
40
50
60
70
80
90
100
Access Point Index
Prediction Accuracy (%) User 1
User 2User 3
User 4User 5
Figure 3.8: Prediction accuracy for various users using HMM
49
4 5 6 7 8 9 100.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Sequence Length
Prediction Accuracy
User 1User 2
User 3User 4
Figure 3.9: Efiect of sequence length on prediction accuracy
1 2 3 4 50.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
Number of Iterations
Prediction Accuracy
User 1User 2
User 3User 4
Figure 3.10: Efiect of iterative improvement of HMM on prediction accuracy
50
0 20 40 60 80 1000.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Index of Mobile Users
Prediction Accuracy
Figure 3.11: A scatter plot showing the distribution of users? average prediction accuracies
shown in flgure 3.7 which biases the users towards a small percentage of APs. However,
repeated training of the HMM can help in making better predictions as shown in Figure
3.10.
Figure 3.11 shows the average predictability of users in a network. There are a good
percentage of users (approximately 41%) who are quite predictable since they move around
a lot. Most other users in a network are random and connect only occasionally to APs other
than their regular one. This is also validated by Figure 3.7.
From the simulation experiments using the HMM, we observe that highly accurate
prediction of a user?s mobility can be performed. The HMM model is easy to train with past
data, the learning is fast and since the model is a learning model, the HMM can continue
to learn with time. Also, the HMM can perform better predictions for users with regular
habits.
51
3.8 Other prediction methods
HMM is a generic method of performing mobility prediction. In a system, depending
on the scenario, difierent models may provide difierent prediction accuracies. In some cases
it may be more important to generate prediction faster due to paucity of time rather than
train the models for a long time. In other cases, the back end system may have the luxury of
analyzing the historic movement data for a lengthy period of time to provide more accurate
predictions.
Hence, we have attempted to show that the same data may be used to feed other
prediction models and get comparable results.
3.8.1 Neural Networks
An artiflcial neural network is a mathematical model based on the operation of a neural
network. It emulates the functioning of a of biological neural system. A neural network
is an elegant data analysis and learning tool that can capture and represent multi variable
functions. The idea for using an artiflcial neural system is based on the desire to model
a system that can work like the human brain [60]. The artiflcial neural network can be
characterized by the following capabilities.
1. Input variables feed into a neural network and it can acquire knowledge through learn-
ing models.
2. The knowledge gained by a neural network is represented as connection strengths
known as synaptic weights.
3. A neural network needs no reprogramming and can work in parallel.
The main advantage of using a neural network lies in the fact that it can be used to
model both linear and non-linear relationships in functions [61].
52
InputLayer HiddenLayer OutputLayer
Figure 3.12: A representation of a Multi Layer Perceptron
3.8.2 MultiLayer Perceptron Neural Network Model
One of the most common and versatile neural network models is the multilayer percep-
tron (MLP) model [60] [62] [63]. This model belongs to a class supervised learning models
since it requires a desired output to acquire knowledge and learn. This is an example of a
mathematical model that can accurately map an input to an output using only historical
data. Through this method, the model acquires knowledge and can generate the output for
future inputs when the desired output is unknown. A graphical representation of an MLP
is shown in Figure 3.12.
The MLP consists of an input layer, hidden layers and an output layer [64] [65] [66]. The
number of hidden layers can be one or more. Every node, except the input nodes, computes
a weighted sum of its inputs and applies a sigmoid function [60] to its output, which then is
transmitted to the next layer.
53
The output of the MLP can be written as shown in Equation 3.17.
y = `
NX
n=1
(wixi +b) (3.16)
= `(wx +b) (3.17)
where
` is the activation function
w denotes the vector of weights,
x is a vector of inputs,
b is the system bias.
The MLP model generates a single output value taking inputs from multiple real-valued
variables. The output is a linear/non-linear function of inputs and the weights and then
weights. A nonlinear activation function may also be used.
The MLP uses a learning algorithm called backpropagation algorithm. Through back-
propagation, the input data is repeatedly presented to the neural network and the output of
the neural network is compared to the desired output known apriori. The computed error
is then fed back i.e., backpropagated to make adjustments to the weights so that the error
decreases with each iteration. Hence the neural network weights converge to the optimal
value to produce the desired output. This phase is called the learning phase.
The learning phase consists of pairs of inputs and outputs that are obtained from historic
data. In our case, we have mobility traces that show the initial access point and the actual
next access point the user connects to. This information is fed to the network to train the
network. The training process continues until the weights and bias functions are converged
to a stable value. The criterion to be optimized is typically the squared reconstruction error
P
tjjf(s(t))?x(t)jj
2.
54
The error in an output node is given by
ek(n) = dk(n)yk(n) (3.18)
where we are observing the error at the kth output node for the nth data tuple. d is the
desired output value and y is the erroneous value generated by the model.
The weights and biases are corrected accordingly to minimize the output error using
e(n) =
X
k
e2k(n)
2 (3.19)
The change in each weight can be computed as
?wkj(n) = ?? @e(n)@v
k(n)
yj(n) (3.20)
where yj is the output of the previous neuron and ? is the learning rate. The constant ?
decides the speed of convergence of the weights in the network.
If the weights of all the nodes are expressed as a matrix, then
Wih = Wih +?Wih (3.21)
where Wihj = ?ie+fl?Wihj?1
Who = Who +?Who (3.22)
where Whoj = ?hd+fl?Whoj?1,
Wihpxn denotes the weight matrix for links from input layer i to hidden layer h,
? is the learning rate and
fl is the weight change momentum factor.
55
1 2 3 4 50.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
Number of Iterations
Prediction Accuracy
User 1User 2
User 3User 4
Figure 3.13: Efiect of iterative improvement of Neural Networks on prediction accuracy
One hidden layer is usually enough for most models. More than one hidden layers are
necessary for modeling discontinuous data with higher complexity. If two hidden layers are
used, the model may be improved but it also adds the risk of the output converging to a
local minima. Also, care must be taken in designing the number of neurons in the hidden
layer. A lower number of neurons may produce erroneous or poor results and an excessive
number of neurons will result in a very large learning phase. It may also introduce noise in
the data and cause wrong outputs.
3.8.3 Results
A simulation experiment is conducted using the same wireless data traces is used to
perform mobility prediction using MLP Neural Network. Simulation is performed using
MATLAB software. All experimental settings from the HMM prediction experiment are
maintained the same. Some of the results of the experiment are discussed in this section.
56
0 2 4 6 8 10 12 140
10
20
30
40
50
60
70
80
90
100
Access Point Index
Prediction Accuracy
 
 
NN
HMM
Figure 3.14: A comparison of prediction accuracies between Neural Network and Hidden
Markov Model
Figure 3.14 shows a comparison of the prediction accuracies for the MLP Neural Network
model to the HMM. The same users and access point settings are used for the experiment.
It can be seen from Figure 3.14 that the prediction accuracies are almost the same. Hence
MLP Neural Network provides an excellent model to produce highly accurate predictions.
In Figure 3.15, a comparison of prediction accuracies for the Neural Network and Hidden
Markov Model can be seen. It is easily seen that the HMM outperforms the MLP model for
longer sequence lengths. For movement sequences over 4 states, the Neural Network model
is incapable of performing predictions
One of the obvious disadvantages of using the MLP model is the time it takes for the
synaptic weights to converge. Figure 3.16 shows the number of iterations the model takes
to converge to produce a stable and accurate output. While MLP model is quite accurate,
it can take a very long time to get out of the ?learning phase?. Moreover, we have simulated
57
4 5 6 7 8 9 1010
20
30
40
50
60
70
80
90
Sequence Lengths
Prediction Accuracy
 
 
HMM
NN
Figure 3.15: A comparison of prediction accuracy between Neural Networks and Hidden
Markov Models over long movement sequences
the model using only one hidden layer. Increasing the number of hidden layers can greatly
increase the convergence time.
3.9 Discussion
In this chapter, we have studied the mobility prediction schemes in literature and exper-
imented with two prediction methods. We have proposed performing prediction using the
HMM and the MLP Neural Network models. Accurate mobility prediction is essential for
providing location based services and network management. It is shown that with a trace
data set, we can achieve a very high accuracy in mobility prediction. Also, there are several
similarities, advantages and disadvantages in using HMMs and Neural Networks as we have
shown in [47] [67] [68] .
58
1 2 3 4 50.5
0.55
0.6
0.65
0.7
0.75
0.8
0.85
0.9
0.95
1
Number of Iterations
Prediction Accuracy
User 1
User 2
User 3
User 4
Figure 3.16: Optimal weight coe?cients convergence in a MLP Neural Network model
59
3.9.1 Comparison of Neural Networks and HMM Models
Neural Networks and Hidden Markov Models have several advantages over each other.
HMMs can be trained rapidly since their learning phase can be quite short. Also, the Markov
models can be made into kth order models to capture recent path changes. On the other
hand, MLPs can predict the next state of the system based only on the previous state.
Also, training HMMs required a lot less historic data before producing accurate predic-
tions. In contrast, Neural Networks take a long time to learn, require more historic data
information and can be more complex. However, Neural Networks can be used when no
data is available at all; but since it is a supervised learning model, the network can start ofi
with arbitrary synaptic weights and eventually adapt its coe?cients correctly if it is fed the
correct feedback. The feedback loop error can be minimized with successive iterations and
the model made to converge over time.
60
Chapter 4
Resource Allocation in Wireless Networks
4.1 Overview
In a large network, keeping track of devices, servers and active connections is a challenge.
The problem is tougher in the case of wireless networks involving hundreds or thousands of
users. The process of managing all these devices, providing a constant supply of resources
and administering and maintaining them is called network management.
Wireless networks pose signiflcant management challenges in several ways. One of the
main challenges in network management is to provision the available resources optimally.
Resources may mean bandwidth, time slots, QoS requirements, etc. However, providing
real-time services is challenging due to the binding delay/jitter requirements and also due
to complex network dynamics.
Enterprise wireless networks are very complex systems with several inter-dependent
components that afiect their performance. These components, besides radio interference,
may include various network protocols, tra?c  ows, dynamic network topologies, device
hardware and software. Moreover, it is very di?cult to characterize and analyze how these
devices interact with each other.
Resources are always scarce in wireless networks with radio spectrum being the most
important. With increasing number of users, over-provisioning bandwidth as done in wireline
networks is not feasible. Hence, the importance of e?ciently allocating bandwidth resources
cannot be overemphasized.
61
Figure 4.1: The proposed network model
4.2 Network Management using Mobility Prediction
In Chapter 3, we have performed mobility prediction using historic movement data. The
objective of performing mobility prediction was to provide better localization and location
aware services. It is possible to utilize the same data and results of mobility prediction for
network management.
The framework consists of two parts - the prediction model shown in Figure 4.1 and the
control theoretic feedback model for resource utilization in Figure 4.2.
4.3 Control Theory in Resource Allocation
Control systems [69] [70] have been applied [71] [72] to solve problems in communica-
tion networks. Several problems in the domain of computing and communication systems
have been modeled using control theoretic approaches [71] [72] [73] [74]. Some of these
include network  ow-control problem, CPU resource allocation problems, etc. One com-
mon characteristic of such problems is that they involve time variant inputs that cannot
62
be characterized by closed form solutions. Hence a control system is ideal in such mod-
els since it can be made adaptive to the changing input-output parameters and resource
conditions [75] [76] [77] [78] [79].
There are no models that also solve the problem of prediction and management as a
single issue in mobile wireless networks. We propose to address the resource allocation issue
as an integral part of the mobility prediction framework.
4.4 Proposed model and Mathematical analysis
The model in Figure 4.1 shows a block diagram of the network mobility prediction. The
prediction engine is driven by a HMM or a Neural Network Model. The current mobility
information and a history of the users? past movements is used to make predictions. The
data for the predictions is stored in a mobility database which updates mobility of users
moving to adjacent network APs.
The predictive controller module in Figure 4.1 is a control system shown in more detail in
Figure 4.2. The controller consists of a network manager which decides the current resource
utilization and helps makes an estimate of the network usage. This information is fed to the
estimator after a delay to denote that it uses stale historic data, i.e., only events that have
already transpired. This generates the estimated threshold function xest or ^x which is used
to output function for the resource allocation. The resource allocation engine only produces
a fractional value denoting the network resource usage. A value greater than 1 would mean
an overloaded network.
Inmobilityprediction, usermobilitycanberandom, bursty, stochasticandnon-stationary.
These parameters result in uncertainty in reserving resources, thereby demanding adaptive
models that can regulate the tra?c and allocate resources optimally.
The proposed predictive control model determines the threshold for input to regulate
the incoming users depending on parameters such as number of users and efiective resource
utilization. Efiective resource utilization is deflned as the fraction of network resources being
63
Figure 4.2: Details of the network controller
used at any given time. The solution proposed is a predictive controller that is driven by
the HMM. Other proactive tasks such as capacity planning and intelligent learning can also
be performed.
To describe Figure 4.2, a few terminologies and notations are needed. Let d[n] be the
average network demand due to all existing users at the time instant n and z[n] the regulating
value. The actual quantity of network resources being utilized at any moment is a function
of d and z and is denoted by x. Relative utilization of the network is denoted by y[n]. This
is deflned as the ratio of the measured network resource usage to the total available network
resource.
y[n] = f(x[n];z[n]) (4.1)
y[n] = x[n]z[n] (4.2)
64
The controller has to maintain the efiective network utilization at a specifled threshold
level, say ythr. Hence,
z[n] = z[n?1]?Ga[n]
 
ythr ? x[n?1]z[n?1]
?
(4.3)
Ga is the adaptive loop feedback gain and is negative to indicate negative feedback.
Ga[n] = ?
 x[n?1]
ythr
?
(4.4)
where ? is the loop control constant that ?regulates? the level of control in the feedback loop.
The adaptive loop feedback gain as
Ga[n] = z[n?1]y
thr
(4.5)
Hence, z[n] becomes
z[n] = x[n?1]y
thr
(4.6)
Since the predictability of x[n] is straightforward as established by f(?), z[n] is obtained by
z[n] = xest[n]y
thr
(4.7)
Since this is a model for a system with memory using historic data to estimate the resource
utilization at any instant, the control system depends on the current and the average loads.
Hence,
x[n] = min(z[n];d[n]) (4.8)
65
In an ideal scenario, the network is always able to meet the demands of the users. The
network demand should always be less than the total available resources. and hence, we
have d[n] ? z[n]. However, due to the unpredictability of mobile users, there are bursty
arrivals and demand exceeds supply. The arrivals are bound by the resources available and
x[n] = z[n]. The goal of the controller is to regulate the number of users in the network
depending on the resource availability where d[n] is observable.
To analyze the estimator shown in Figure 4.2, the state space model [71] is given by
x(i)n = ?(i)x(i)n?1 +?(i)zn?1 (4.9)
y(i)n = C(i)x(i)n +?n (4.10)
This is a generalized model equation with the superscript (i) denoting model index. Estimat-
ing these coe?cients results in errors that are also represented by ?n, the error coe?cient.
The output y(i)n predicted by the model is also iteratively corrected using repeated estima-
tion. A separate correction index ?n that accounts for all other inherent model errors is also
introduced.
x(i)n is a state estimation performed by the model and can be expressed as a single state
vector in the form
x(in)n =
2
64 x(i)n
?(i)n
3
75 (4.11)
The generalized state vector can be written as
x(in)n = ?(in)x(in)n?1 +?(in)zn?1 +?(in)?n?1 (4.12)
y(i)n = C(in)x(in)n +?n (4.13)
66
However, we know that the information at the estimator above is old and is denoted by a
time lag. Hence, the estimated information is denoted as
^x(in)njn?1 = ?(in)^x(in)n?1jn?1 +?(in)zn?1 +?(in)?n?1 (4.14)
^y(i)njn?1 = C(in)^x(in)njn?1 +?n (4.15)
^x notation explicitly denotes the predicted value of x. The prediction is made from the
state variables in the previous time slot. These equations can be solved using the standard
linear algebraic methods described in [69].
The uniqueness of this solution is that at each time slot, an optimization problem
formulationissolved. Thedesignofthecontrollerissuchthattheformulationoftheobjective
function is to minimize the controller function over a horizon of m time slots.
At the beginning, only the initial control conditions are applied to the system. The
state space models are updated and then the system iteratively updates the conditions from
the controller. The desired efiective resource utilization is 83:3% as used in most networks.
The initial mode for the estimation is deflned by
y0n+jjn =
lX
i=1
a(i)n ^y(i)n+jjn (4.16)
where a(i)n are the coe?cients of the model weight vectors and ^y(i)n+jjn are the predicted
individual model outputs. These have been calculated using the state estimation results
explained earlier.
For the predictive control solution, we need to derive a solution from the linear model de-
scribed above. The objective function is formulated as follows. The error over the prediction
range of m time slots is give as
?err = (Y ?Y 0)TAy(Y ?Y 0) (4.17)
67
where Y is the vector, ^Y is the vector deflning the predicted output values over the range
^yn+1jn through ^yn+mjn, i.e.,
Y 0 =
2
66
66
66
64
y0n+1jn
y0n+2jn
...
y0n+mjn
3
77
77
77
75
(4.18)
The correction of the controller in the loop is given by
? = ?ZTAz?Z (4.19)
where
?Z =
2
66
66
66
64
?zn
?zn+1
...
?zn+m?1
3
77
77
77
75
(4.20)
Z0 is a column vector of elements zn?1 of size m?1
The optimization problem is formulated as follows and solved numerically.
min? = ?err +? (4.21)
4.5 Simulation
The model proposed in the previous section has been simulated to verify the proposed
ideas. The prediction engine based on HMM is separately tested for accuracy in predicting
the future mobility of users. Also, the control system is tested for stability and integrated
with the prediction model as a whole to regulate network resource utilization. Some of the
results are brie y discussed in the subsequent sections.
68
Using mobility data, we have performed analysis using MATLAB simulations to verify
the accuracy of the model versus actual movement, study user mobility, prediction beneflts,
etc. The control system has been simulated using the Control System toolbox and Simulink
from MATLAB.
4.5.1 MATLAB Simulink Modeling
Simulation of the feedback based control system is performed in MATLAB using the
Simulink toolbox. MATLAB Simulink is a specialized control system toolbox that provides
advanced features of control theoretic principles. Simulink is an environmentfor multidomain
simulation and Model-Based Design for dynamic control and embedded systems. Simulink
models are hierarchical and allow for using both top-down and bottom-up approaches.
We have used MATLAB extensively to simulate some of the models described in the
earlier chapters. Mobility prediction models using HMM were implemented in MATLAB
since it provides extensive features for data mining and analysis. Since Simulink is an
integrated component of the MATLAB environment, it is relatively easy to perform analysis
of control systems and also derive full advantage of features ofiered in both environments.
4.5.2 Simulation Parameters
A MATLAB simulink scenario is used to perform simulation for the complete system
involving the prediction engine and the controller. The threshold value for the network
is decided based on the efiective resource utilization rate. The resource utilization rate is
deflned as the ratio of the total resource being used to the total available network resource
which is always less than unity.
The desired optimum efiective utilization rate has been set at 0:833 and the feedback
loop coe?cients converge accordingly. Various model characteristics such as resource utiliza-
tion, time required for stability, percentage of mobile users dropped and errors in estimation
are observed via simulation. The simulation results are discussed below.
69
0 5 10 15 200
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Simulation time instant (in seconds)
Effective Network Resource Utilization  
 
Without Controller
With Controller
Figure 4.3: Simulated resource utilization ^ythr with and without controller
4.6 Results
The efiectiveness of the controller is shown in Figure 4.3. With the feedback control
system, the network resource is managed more efiectively than when it operates without a
controller. A HMM without a controller can still achieve high utilization but only at certain
times; a controller helps regulate the number of users to optimize resource utilization. In
the same flgure, it is also seen that the efiective resource utilization using a controller is
approximately 83%, which was the threshold set by the network.
Figure 4.4 proves the same as a function of resource utilization with plain HMM pre-
diction, without prediction and with prediction-based controller. Figure 4.5 shows the per-
centage of users ?dropped? (i.e., denied admission to prevent overloading of the network).
Figure 4.6 shows that the model is stable and the coe?cients indeed converge in flnite
time. Network load is an important parameter in predicting network utilization. Network
load estimation errors also decrease with time. Comparing Figures 4.6 and 4.7, we can see
that the errors reduce signiflcantly as shown in Fig 4.7 after the model coe?cients converge.
70
10 20 30 40 50 60 70 80 90 1000
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Number of Nodes
Effective Resource Utilization
ControllerMarkov Model
No Prediction
Figure 4.4: Resource utilization ^ythr as a function of number of users
10 20 30 40 50 60 70 80 90 1000
10
20
30
40
50
60
Number of Mobile Users
Percentage of users dropped
 
 Without Controller
Controller
Figure 4.5: Percentage of dropped users
71
0 2 4 6 8 10 12 14 16 18 200
0.05
0.1
0.15
0.2
0.25
Simulation time (for convergence)
Model co?efficients
Figure 4.6: Simulation convergence time for model coe?cients a(i)n
0 2 4 6 8 10 12 14 16 18 200
0.2
0.4
0.6
0.8
1
1.2
1.4
Simulation time instants
Errors in estimated network load
Figure 4.7: Mean errors in estimated network load at various instants
72
4.7 Discussion
The prediction scheme uses an HMM which delivers mobility information to a predictive
control system. We have shown increased utilization, reduced blocking scalability and rapid
convergence [67] [68] through extensive simulation experiments. The proposed scheme can
be efiectively incorporated into existing wireless network architectures. To our knowledge,
this is the flrst time control theory is used for studying the efiect of mobility on mobile
network performance.
73
Chapter 5
Efiect of Mobility on Interference
5.1 Overview
We have studied various aspects of mobility. We have characterized the general move-
ment of users, studied the efiects of mobility on wireless network parameters such as through-
put, data rates, etc and we have proposed solutions to deal with some of its detrimental
efiects.
With increasing number of users, cells are being split into nano and femtocells; wireless
networks are being made smaller to prevent interference amongst various networks. However,
the cells and networks cannot be split indeflnitely. Mobility and interference together have
been extensively studied for cellular networks for a long time [80] [81] [82]. Interference
efiects arising out of mobility have also been studied in the context of routing, network
modeling, etc [83] [84].
One other important aspect is the efiect of mobility on interference dynamics and outage
perceived by users. Outage can be deflned as the probability that the quality of service (e.g.,
measured by Signal to Interference Ratio (SIR)) is less than a predeflned threshold. Due to
movement of mobile users, the location of interfering nodes change by time. As a result, the
statistics of interference dynamics needs to be considered in our analysis. In this chapter,
we aim to obtain analytical models for outage which consider mobility as a parameter.
There are few studies which take into account the efiect of mobility on quality of service
and outage. One study [85] uses a  uid model for mobility and deflnes f as the ratio of outer
cell received power to the inner cell received power. Using this factor, analytical results are
found for outage probability. However, the considered mobility model is not very practical
and is limited in scope.
74
Another research study [80] focuses on the impact of mobility of low-speed users. It
aims to model how interference evolves with respect to the mobility of users who move in
a random fashion. WienerL?evy process is used as a stochastic tool for characterizing the
impact of mobility on the future behavior of interference. The considered is simplifled and
only distance-based path loss model is considered while neglecting the efiect of fading in
analysis.
In this chapter, we consider a power-controlled cellular system and obtain cell cross-over
probability for difierent edges of a cell and for difierent mobility models using simulation.
First, assuming that users are uniformly distributed at the beginning, we obtain time de-
pendent equations for the number of users in a cell considering difierent models. Second,
we obtain analytical results for distances between an arbitrary node and a particular victim
BS. These distances are then used to flnd the amount of interference to the victim BS us-
ing distance-dependent as well as log-normal shadowing. The aggregate interference is then
modeled as a Gaussian random variable assuming central limit theorem holds. We obtain
analytical results for mean variance of aggregate interference which are enough to charac-
terize the Gaussian random process. The outage probability therefore can be easily found
using this statistical model.
5.2 System Model
The cellular system is modeled as a tessellation of hexagonal cells. The nodes inside
each cell employ power control so that the received power of each node at its associated base
station (BS) is a constant Pf. The channel model is a combination of distance-dependent
path loss as well as shadow fading.
Now let us consider Figure 5.1. Focusing on a single cell in the cellular system, the
received power, Pr, from the mth nearest node in the cell to the BS is given by [86]:
Pr = ?mPt;mr?fim (5.1)
75
rm
mth nearest node
Figure 5.1: Representation of the mth nearest node from the BS in a cell
where ?m is the shadow fading factor, fi is the path loss exponent, rm is the distance between
BS and mth nearest node and Pt;m is the transmit power level of mth nearest node. We assume
that perfect power control is employed by the nodes and Pt;m is
Pt;m = 1?
m
Pfrfim; (5.2)
so that the received power is flxed (i.e., Pf).
5.2.1 Proposed Approach
In Figure 5.2, the tessellation of cells is shown. The cells are numbered starting from the
bottom outer perimeter cell as shown. The numbering is continued in an counter-clockwise
manner and the perimeter hierarchy is determined as illustrated in the flgure. The number
of nodes in a cell (i;j) at time t is deflned by nti;j. Given that nodes are distributed uniformly
with density ? at time t = 0, several mobility models are used to determine nti;j.
For this purpose, we flnd the probabilities pi(i = 1;2;??? ;6) of nodes crossing the edges
of a cell in a time interval ?t as seen in Figure 5.3. These probabilities depend on the
mobility model, cell size, ?t and speed among other factors.
76
Cell (2,6)
Victim BS
Figure 5.2: Cellular geometry and cell numbering
Using these probabilities, we can flnd the evolution of nti;j. For example, for cell (2;6),
it can be seen that
nt2;6 = nt?12;6 (1?q)+nt?12;5 (p5)+nt?12;7 (p2)+nt?11;3 (p4)
+nt?11;4 (p3)+nt?13;8 (p6)+nt?13;9 (p1) (5.3)
where
q =
6X
i=1
pi
5.3 Interference Analysis
Consider Figure 5.4 in which the distance between mth nearest node to the BS in cell
(i;j) and the BS in the victim cell, denoted by di;j;m is found using the law of cosines.
d2i;j;m = H2ij +r2m ?2Hijrm cos(3?2 ?fim)
= H2ij +r2m +2Hijrm sinfim (5.4)
77
p1
p2
p3
p4
p5
p6
Figure 5.3: Cell cross-over probability from difierent edges of a cell
Lemma 1 By assigning k = (j ?1)mod i, Hij can be found as:
Hij =
p
3R2(i2 +k2 ?ik) (5.5)
Proof: By assigning k = (j ? 1)mod i, we can see from Figure 5.4 that Hij equals xk in
Figure 5.5. By using the law of cosines sequentially, equation ?? can be obtained.
Interference originated from nodes in cell(i,j) on the victim BS at time t will be
Itij =
nti;jX
m=1
?mPt;md?fii;j;m
=
nti;jX
m=1
?m
?mPf(
rm
di;j;m)
fi =
nti;jX
m=1
?mPf( rmd
i;j;m
)fi (5.6)
where ?m is the shadow fading component for the link between mth nearest node in cell(i,j)
to its BS and the victim BS and the relation for Pt;m is obtained from Equation 5.2. We
78
Hi,jdi,j,m
rm
Cell (i,j)
am
Figure 5.4: Distances between the interfering nodes and the victim BS
also have ?m = ?m?m. It is easily seen that if ?m and ?m both correspond to  dB Log-normal
shadowing, ?m corresponds to p2 dB Log-normal shadowing.
By deflning  0 ,p2 ln1010 , the flrst two moments of ?m can be found as
Ef?g = e 02=2 (5.7)
Ef?2g = e2 02 (5.8)
While it is possible to obtain the statistics of rm with certain assumptions (see next
section) and fim can be assumed uniformly distributed in [0;2?] and independent from rm,
the statistics of di;j;m is not easy to obtain. Now,
Efd2ijmg = H2ij +Efr2mg+2HijEfrmgEfsinfimg
= H2ij +Efr2mg (5.9)
79
X0= i v3 R
X1
Xk= H
iji
 v3 
R
v3 R
p/(3i)
i v3 
R
v3 R
Xi
Figure 5.5: The geometry used to flnd Hij
We estimate Itij by ~Itij as
~Itij =
nti;jX
m=1
?mPf r
fi
m
[H2ij +Efr2mg]fi=2:
Total interference at the victim BS at time t can therefore be estimated as
~It = X
i;j
~Itij (5.10)
Statistics of ~It
~It is the sum of a large number of random variables and we assume that Central Limit
Theorem (CLT) holds and it follows a Gaussian distribution. Therefore, mean and variance
80
1 2 3 4 5 6 7 8 9 101
2
3
4
5
6
7 x 10
5
m
E{r
m? }
 
 
N=10
N=20
N=30
Figure 5.6: Efrfimg versus m for fi = 3;R = 100 and N = 10;20;30
of ~It are required to completely characterize it. They can be found as follows:
Ef~Itg = Ef?gPf
X
i;j
nti;jX
m=1
Efrfimg
[H2ij +Efr2mg]fi=2 (5.11)
varf~Itg =
X
i;j
nti;jX
m=1
P2fvarf?mrfimg?
H2ij +Efr2mg?fi (5.12)
From Equation 5.11 and Equation 5.12, Ef?g = e 02=2 and varf?mrfimg = e2 02Efr2fim g ?
e 02E2frfimg.
Statistics of rm
We make the assumption that at time t, the nti;j nodes inside cell (i;j) are uniformly
distributed. Once we have nti;j = N, we can approximate the hexagonal cell of radius R to
a circular cell of radius R0 for for more clarity in analysis.
81
?R20 = 3
p3
2 R
2
R0 =
s
3p3
2? R
The pdf of rm is shown in [87] to be
frm = N
 N
m
?
Fr(r)m?1(1?Fr(r))N?mfr(r) (5.13)
where
Fr(r) = ( rR
0
)2
fr(r) = 2rR2
0
Using the pdf of rm, we can flnd
Efrfimg =
Z R0
0
rfifrm(r) dr: (5.14)
After simpliflcation, and using Equation 5.13 in Equation 5.14, we flnd
Efrfimg = Rfi0N
 N
m
?
2F1(fi=2+m;m?N;fi=2+m+1;1)
fi=2+m (5.15)
where 2F1 is the hypergeometric function [88]. In Figure 5.6, Efrfimg is plotted for fi = 3,
R = 100 and for three values of N = 10;20 and 30. As the number of nodes increases, the
nodes will be more densely distributed and Efrfimg decreases for a given m.
82
5.4 Relations for ntij
Generally, one can flnd the following equation for nti;j.
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p3)+nt?1i;j+1 (p6)+nt?1i?1;j?1 (p2)
+nt?1i?1;j (p1)+nt?1i+1;j (p4)+nt?1i+1;j+1 (p5) 2 ? j ? i
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p4)+nt?1i;j+1 (p1)+nt?1i?1;j?2 (p3)
+nt?1i?1;j?1 (p2)+nt?1i+1;j+1 (p5)+nt?1i+1;j+2 (p6) i+2 ? j ? 2i
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p5)+nt?1i;j+1 (p2)+nt?1i?1;j?3 (p4)
+nt?1i?1;j?2 (p3)+nt?1i+1;j+2 (p6)+nt?1i+1;j+3 (p1) 2i+2 ? j ? 3i
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p6)+nt?1i;j+1 (p3)+nt?1i?1;j?4 (p5)
+nt?1i?1;j?3 (p4)+nt?1i+1;j+3 (p1)+nt?1i+1;j+4 (p2) 3i+2 ? j ? 4i
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p1)+nt?1i;j+1 (p4)+nt?1i?1;j?5 (p6)
+nt?1i?1;j?4 (p5)+nt?1i+1;j+4 (p2)+nt?1i+1;j+5 (p3) 4i+2 ? j ? 5i
nti;j = nt?1i;j (1?q)+nt?1i;j?1 (p2)+nt?1i;j+1 (p5)+nt?1i?1;j?6 (p1)
+nt?1i?1;j?5 (p6)+nt?1i+1;j+5 (p3)+nt?1i+1;j+6 (p4) 5i+2 ? j ? 6i
83
nti;1 = nt?1i;1 (1?q)+nt?1i;2 (p6)+nt?1i;6i (p2)+nt?1i?1;1 (p1)
+nt?1i+1;6(i+1) (p3)+nt?1i+1;1 (p4)+nt?1i+1;2 (p5) j = 1
nti;i+1 = nt?1i;i+1 (1?q)+nt?1i;i (p3)+nt?1i;i+2 (p1)+nt?1i?1;i (p2)
+nt?1i+1;i+1 (p4)+nt?1i+1;i+2 (p5)+nt?1i+1;i+3 (p6) j = i+1
nti;2i+1 = nt?1i;2i+1 (1?q)+nt?1i;2i (p4)+nt?1i;2i+2 (p2)+nt?1i?1;2i?1 (p3)
+nt?1i+1;2i+3 (p6)+nt?1i+1;2i+2 (p5)+nt?1i+1;2i+4 (p1) j = 2i+1
nti;3i+1 = nt?1i;3i+1 (1?q)+nt?1i;3i (p5)+nt?1i;3i+2 (p3)+nt?1i?1;3i?2 (p4)
+nt?1i+1;3i+3 (p6)+nt?1i+1;3i+4 (p1)+nt?1i+1;3i+5 (p2) j = 3i+1
nti;4i+1 = nt?1i;4i+1 (1?q)+nt?1i;4i (p6)+nt?1i;4i+2 (p4)+nt?1i?1;4i?3 (p5)
+nt?1i+1;4i+4 (p1)+nt?1i+1;4i+5 (p2)+nt?1i+1;4i+6 (p3) j = 4i+1
nti;5i+1 = nt?1i;5i+1 (1?q)+nt?1i;5i (p1)+nt?1i;5i+2 (p5)+nt?1i?1;5i?4 (p6)
+nt?1i+1;5i+5 (p2)+nt?1i+1;5i+6 (p3)+nt?1i+1;5i+7 (p4) j = 5i+1
For nt1;j, the above relations are valid if we substitute for nt0;k, the average number of
nodes in the victim cell at time t for any k.
5.5 Discussion
In this chapter, we have studied the efiect of mobility on interference dynamics. Cross-
over probabilities of difierent edges of a cell are characterized by the mobility model. Aggre-
gate interference and its statistics are stochastic in nature due to the random movement of
mobile users. The aggregate interference is considered to be Gaussian in nature. However,
84
the Gaussian approximation holds only for larger distances. We have also analyzed the av-
erage instantaneous number of mobile users in a cell and the outage perceived by users in
the cellular system.
85
Chapter 6
Conclusion
In this dissertation, we have studied mobility models, mobility prediction, control the-
oretic resource allocation and addressing interference problems related to mobility.
In Chapter 2, we discussed mobility models, problems of existing mobility models and a
thorough performance analysis of mobility models under difierent routing protocols. It was
noted that while mobility models are an easy way to validate network protocols and algo-
rithms, they sometimes lack the necessary features to perfectly emulate real-world scenarios.
Chapter 3 proposed novel methods of mobility prediction. Firstly, instead of using
mobility models, we used real-world wireless trace data in our simulations. We have analyzed
the performance of Markovian methods with regard to mobility prediction. A flrst order
Markov model was studied and observed some shortcomings. A Hidden Markov model was
proposed to perform mobility prediction. The HMM provided desired abstraction models to
suit the data and the scenarios. A high degree of accuracy in predicting user movement was
achieved using the HMM prediction model.
We have proposed a generic frame work for modeling and predicting user movement in
wireless networks. We used a HMM for mobility prediction in a wireless network in conjunc-
tion with a closed loop feedback control system. The proposed scheme is computationally
simple and can be incorporated into existing wireless network architectures as seen in Chap-
ter 4. The mobility prediction is based on a resource management method using control
theoretic framework. The prediction scheme uses an HMM which delivers mobility infor-
mation to a predictive control system. The model is verifled by simulations and the results
show increased network utilization for WLAN networks with low-speed mobility, reduced call
blocking and rapid convergence of the prediction model coe?cients. The model is also shown
86
to be scalable in the number of users. The proposed scheme can be efiectively incorporated
into existing wireless network architectures. To our knowledge, this is the flrst time control
theory is used for studying the efiect of mobility on mobile network performance.
Chapter 5 provided a discussion on the efiect of interference on wireless users due to
mobility. Interference to a wireless user from adjacent base stations was also analyzed. Due
to the mobility of interfering nodes, the aggregate interference and its statistics are time-
varying. Analytical results are obtained for interference statistics by using a Gaussian model
and considering the efiect of difierent mobility models.
Mobility is a key challenge in today?s wireless and mobile networks. Hence, it is nec-
essary to consider the efiects of mobility on network architectures and protocols. The main
contribution of this dissertation is a generic framework for mobility prediction and resource
management. The  exible framework for prediction and resource allocation allows for use of
other techniques such as ARMA, Neural Networks and machine learning in place of HMM.
The same model can be used in various network applications such as QoS, seamless handover
and jitter-free streaming applications.
87
Chapter 7
Future Work and Extensions
In this dissertation, we have dealt with mobility models, mobility prediction and re-
source allocation. These solutions are proposed to solve problems in network management.
However, there is still a lot of scope for solving problems such as . This chapter discusses
some of the proposed work in future as possible extensions of our existing work.
In future, we propose to investigate performance issues of time-series prediction models
and compare with neural networks and ARMA models. Time series forecasting has been used
for predicting data with high temporal correlation (e.g., stock market data). Exploiting the
spatio-temporal characteristics of the data hold a vast potential for future research work. For
instance, the campus WiFi data has a high correlation to the schedule of classes. Knowledge
of student class schedules can improve the accuracies of user predictions by a high degree. We
also propose to extend the probabilistic models to include user behavior such as clustering,
group modeling, etc.
Mobile network management can be performed better if more of the variables involved
are understood better. Hence, it is necessary to study issues such as mobile tra?c-aware
channel assignments and intelligent power control in WLANs, integrated wired-wireless in-
frastructure management, security issues involved in user mobility, etc. Problems in radio
resource management can be investigated by harnessing multi-radio systems to collect net-
work and channel statistics while the device is transmitting/receiving. Other possible solu-
tions also include automatically shifting mobile clients to difierent channels to provide better
service and reduce co-channel interference among access points.
Also, most large scale WLAN installations are not planned extensively before deploy-
ment. One of the biggest problems caused by mobility on users is mutual interference. This
88
has not been studied extensively in the context of mobile WLAN networks. Users moving
around in a WLAN hotspot can reduce the data rates of all the other users connected to the
same access point. Hence, a more rigorous study of interference is necessary to understand
the underlying issues. Also, the expressions obtained for interference using Gaussian distri-
bution is true only for interferers at larger distances. Hence a better flt can be investigated
to cover all interferers.
89
Bibliography
[1] V. Rodoplu and T. Meng, \Growth of wireless ad hoc networks," in IEEE Global
Telecommunications Conference, (GLOBECOM), 2003.
[2] D. Perkins, H. Hughes, and C. Owen, \Factors afiecting the performance of ad hoc
networks," IEEE International Conference on Communications (ICC), vol. 4, pp. 2048{
2052, 2002.
[3] P. S. Prasad, P. Agrawal, and K. M. Sivalingam, \Efiects of mobility in hierarchical
mobile ad hoc networks," in 6th IEEE Consumer Communications and Networking
Conference, January 2009, pp. 1{5.
[4] M. Gonzlez, C. Hidalgo, and A.-L. Barabsi, \Understanding individual human mobility
patterns," Nature, no. 453, pp. 479{482, 2008.
[5] W. Navidi and T. Camp, \Stationary distributions for the random waypoint mobility
model," IEEE Transactions on Mobile Computing, vol. 3, no. 1, pp. 99{108, Jan-Feb
2004.
[6] A. Acampora and M. Naghshineh, \An architecture and methodology for mobile-
executed handover in cellular atm," IEEE Journal on Selected Areas in Communi-
cations, vol. 12, no. 8, pp. 1365{1374, October 1994.
[7] C. E. Perkins, E. Royer, S. R. Das, and M. K. Marina, \Performance comparison of two
on-demand routing protocols for ad hoc networks," IEEE Personal Communications,
vol. 8, pp. 16{28, February 2001.
[8] A. Jardosh, E. M. Belding-Royer, K. C. Almeroth, and S. Suri, \Towards realistic
mobility models for mobile ad hoc networks," in ACM Mobicom 2003, 2003.
[9] D. B. Johnson and D. A. Maltz, \Dynamic source routing in ad hoc wireless networks,"
Mobile Computing, vol. 353, 1996.
[10] F.Bai, N.Sadagopan, andA.Helmy, \Important: aframeworktosystematicallyanalyze
the impact of mobility on performance of routing protocols for ad hoc networks," in
Proceedings of IEEE Information Communications Conference (INFOCOM 2003), 2003.
[11] J. Markoulidakis, G. Lyberopoulos, D. Tsirkas, and E. Sykas, \Mobility modeling
in third-generation mobile telecommunications systems," Personal Communications,
IEEE, vol. 4, no. 4, pp. 41 {56, aug. 1997.
90
[12] M. Feeley, N. Hutchinson, and S. Ray, \Realistic mobility for mobile ad hoc network
simulation," in Ad-Hoc, Mobile, and Wireless Networks, ser. Lecture Notes in Computer
Science, I. Nikolaidis, M. Barbeau, and E. Kranakis, Eds. Springer Berlin / Heidelberg,
2004, vol. 3158.
[13] I. Stepanov, P. Marron, and K. Rothermel, \Mobility modeling of outdoor scenarios for
manets," apr. 2005, pp. 312 { 322.
[14] T. Camp, J. Boleng, and V. Davies, \A survey of mobility models for ad hoc network
research," Wireless Communications and Mobile Computing, volume 2, number 5, 2002.
[15] C. Bettstetter and C. Wagner, \The spatial node distribution of the random waypoint
mobility model," in Proc. German Workshop on Mobile Ad-Hoc Networks (WMAN),
no. P-11, 2002, pp. 41{58.
[16] C. Bettstetter, \Mobility modeling in wireless networks: Categorization, smooth move-
ment, and border efiects," in ACM Mobile Computing and Communications Review,
vol. 5, no. 3, 2001, pp. 55{67.
[17] C. Bettstetter, H. Hartenstein, and X. Perez-Costa, \Stochastic properties of the ran-
dom waypoint mobility model," ACM/Kluwer Wireless Networks, Special Issue on Mod-
eling and Analysis of Mobile Networks, vol. 10, no. 5, pp. 181{190, Jan-Feb 2004.
[18] J. Yoon, M. Liu, and B. Noble, \Random waypoint considered harmful," in Proceedings
of INFOCOM, 2003.
[19] T. Chu and I. Nikolaidis, \On the artifacts of random waypoint simulations," in Pro-
ceedings of the 1st International Workshop on Wired/Wireless Internet Communications
(WWIC2002), 2002.
[20] S. J. Doyle, T. K. Forde, and L. E. Doyle, \Spatial stationarity of link statistics in
mobile ad hoc network modelling," in MASCOTS ?06: Proceedings of the 14th IEEE
International Symposium on Modeling, Analysis, and Simulation. Washington, DC,
USA: IEEE Computer Society, 2006, pp. 43{50.
[21] A. Einstein, Investigations on the Theory of Brownian Movement. Dover, New York,
1956.
[22] R. Brown, \A brief account of microscopical observations made in the months of june,
july and august, 1827, on the particles contained in the pollen of plants; and on the
general existence of active molecules in organic and inorganic bodies," Phil. Mag, vol. 4,
pp. 161{173, 1828.
[23] D. Hong and S. Rappaport, \Tra?c model and performance analysis for cellular mo-
bile radio telephone systems with prioritized and nonprioritized handofi procedures,"
Vehicular Technology, IEEE Transactions on, vol. 35, no. 3, pp. 77 { 92, Aug. 1986.
[24] R. Guerin, \Channel occupancy time distribution in a cellular radio system," Vehicular
Technology, IEEE Transactions on, vol. 36, no. 3, pp. 89 { 99, aug. 1987.
91
[25] M. Zonoozi, P. Dassanayake, and M. Faulkner, \Mobility modelling and channel holding
time distribution in cellular mobile communication systems," vol. 1, nov. 1995, pp. 12
{16 vol.1.
[26] ns2 Network Simulator.
[27] E. M. Royer and C. E. Perkins, \An implementation study of the aodv routing protocol,"
Wireless Communications and Networking Conference, IEEE WCNC 2000, vol. 3, 2000.
[28] J. Chan and A. Seneviratne, \A practical user mobility prediction algorithm for sup-
porting adaptive qos in wireless networks," sep. 1999, pp. 104 { 111.
[29] W.-S. Soh and H. Kim, \Qos provisioning in cellular networks based on mobility pre-
diction techniques," Communications Magazine, IEEE, vol. 41, no. 1, pp. 86 { 92, jan.
2003.
[30] A. Aljadhai and T. Znati, \Predictive mobility support for qos provisioning in mobile
wireless environments," Selected Areas in Communications, IEEE Journal on, vol. 19,
no. 10, pp. 1915 {1930, oct. 2001.
[31] D. Ashbrook and T. Starner, \Learning signiflcant locations and predicting user move-
ment with gps," 2002, pp. 101 { 108.
[32] S. Tabbane, \An alternative strategy for location tracking," Selected Areas in Commu-
nications, IEEE Journal on, vol. 13, no. 5, pp. 880{892, jun. 1995.
[33] J. Chan, S. Zhou, and A. Seneviratne, \A qos adaptive mobility prediction scheme for
wireless networks," vol. 3, 1998, pp. 1414 {1419.
[34] E. Clayirci and I. Akyildiz, \User mobility pattern scheme for location update and
paging in wireless systems," Mobile Computing, IEEE Transactions on, vol. 1, no. 3,
pp. 236 { 247, jul. 2002.
[35] B. Liang and Z. Haas, \Predictive distance-based mobility management for multidimen-
sional pcs networks," Networking, IEEE/ACM Transactions on, vol. 11, no. 5, pp. 718
{ 732, oct. 2003.
[36] T. Liu, P. Bahl, and I. Chlamtac, \Mobility modeling, location tracking, and trajectory
prediction in wireless atm networks," Selected Areas in Communications, IEEE Journal
on, vol. 16, no. 6, pp. 922 {936, aug. 1998.
[37] K. Wang, J.-M. Liao, and J.-M. Chen, \Intelligent location tracking strategy in pcs,"
Communications, IEE Proceedings-, vol. 147, no. 1, pp. 63 {68, feb. 2000.
[38] G. Liu and G. Maguire, \A class of mobile motion prediction algorithms for wireless
mobile computing and communication," in Mob. Netw. Appl, 1996, pp. 113{121.
[39] V. Bharghavan and M. P. Jayanth, \Proflle-based nextcell prediction in indoor wireless
lans," in Proceedings of IEEE Singapore International Conference on Networking, 1997.
92
[40] J. Ziv and A. Lempel, \Compression of individual sequences via variable-rate coding,"
Information Theory, IEEE Transactions on, vol. 24, no. 5, pp. 530 { 536, sep. 1978.
[41] A. Bhattacharya and S. K. Das, \Lezi-update: an information-theoretic approach to
track mobile users in pcs networks," in MobiCom ?99: Proceedings of the 5th annual
ACM/IEEE international conference on Mobile computing and networking. New York,
NY, USA: ACM, 1999, pp. 1{12.
[42] M. H. Sun and D. M. Blough, \Mobility prediction using future knowledge," in MSWiM
?07: Proceedings of the 10th ACM Symposium on Modeling, analysis, and simulation of
wireless and mobile systems. New York, NY, USA: ACM, 2007, pp. 235{239.
[43] F. Lassabe, P. Canalda, P. Chatonnay, and F. Spies, \Predictivemobility models based
on kth markov models," jun. 2006, pp. 303 {306.
[44] A. Mihovska, J. Luo, E. Mino, E. Tragos, C. Mensing, G. Vivier, , and R. Fracchia,
\Policy-based mobility management for heterogeneous networks," in Proceedings of the
IST Mobile and Wireless Communications Summit, Budapest, 2007.
[45] J.-M. Franois and G. Leduc, \Ap and mn-centric mobility prediction: A comparative
study based on wireless traces," in In Proceedings of Networking 2007, 2007, pp. 322{
332.
[46] B. Landfeldt, \Integrating mobility prediction and resource pre-allocation into a home-
proxy based wireless internet framework," in In Proceedings of the 8th IEEE Interna-
tional Conference on Networks (ICON), Washington DC, 2000.
[47] P. S. Prasad and P. Agrawal, \Movement prediction in wireless networks using mobility
traces," in 7th IEEE Consumer Communications and Networking Conference, January
2010.
[48] T. Henderson, D. Kotz, and I. Abyzov, \The changing usage of a mature campus-wide
wireless network," in In Proceedings of ACM MOBICOM,ACM Press, 2004, pp. 187{
201.
[49] L. Song and D. Kotz, \Evaluating location predictors with extensive wi-fl mobility
data," in In Proceedings of INFOCOM, 2004, pp. 1414{1424.
[50] A. Papoulis, Probability, random variables, and stochastic processes, 4th ed. McGraw
Hill, 2001.
[51] S. Ross, Stochastic Processes, 2nd ed. Wiley, 1995.
[52] P. S. Prasad and P. Agrawal, \Mobility prediction for wireless network resource man-
agement," in In Proceedings of 41st IEEE SSST 2009, March 2009, pp. 98{102.
[53] L. Rabiner, \A tutorial on hidden markov models and selected applications in speech
recognition," Proceedings of the IEEE, vol. 77, no. 2, pp. 257{286, Feb 1989.
93
[54] L. Rabiner and B. Juang, \An introduction to hidden markov models," IEEE ASSP
Magazine, vol. 3, no. 1, pp. 4{16, Jan 1986.
[55] Y. Bengio and P. Frasconi, \Input-output hmms for sequence processing," IEEE Trans-
actions on Neural Networks, vol. 7, no. 5, pp. 1231{1249, Sep 1996.
[56] A. Viterbi, \Error bounds for convolutional codes and an asymptotically optimum de-
coding algorithm," Information Theory, IEEE Transactions on, vol. 13, no. 2, pp. 260
{ 269, apr. 1967.
[57] J. Forney, G.D., \The viterbi algorithm," Proceedings of the IEEE, vol. 61, no. 3, pp.
268 { 278, mar. 1973.
[58] L. E. Baum, T. Petrie, G. Soules, and N. Weiss, \A maximization technique occurring
in the statistical analysis of probabilistic functions of markov chains," The Annals of
Mathematical Statistics, vol. 41, no. 1, pp. 164{171, 1970.
[59] \Crawdad: Wireless traces from dartmouth," in http://crawdad.cs.dartmouth.edu/.
[60] S. Haykin, Neural Networks: A Comprehensive Foundation. Prentice Hall, 1998.
[61] J. Biesterfeld, E. Ennigrou, and K. Jobmann, \Location prediction in mobile networks
with neural networks," in Proc. IWANNT, 1997, pp. 207{214.
[62] F. Rosenblatt, \The perceptron: A probabilistic model for information storage and
organization in the brain." Psychological Review, vol. 65(6), pp. 386{408, 1958.
[63] M. L. Minsky and S. A. Papert, Perceptrons. MIT Press, 1969.
[64] C. M. Bishop, Neural Networks for Pattern Recognition, 1st ed. Oxford University
Press, USA, January 1996.
[65] S. Kartalopoulos, Understanding Neural Networks and Fuzzy Logic(Basic Concepts and
Applications). Wiley-IEEE Press, 1995.
[66] C. Looney, Pattern Recognition Using Neural Networks: Theory and Algorithms for
Engineers and Scientists. Oxford University Press, USA.
[67] P. S. Prasad and P. Agrawal, \A generic framework for mobility prediction and resource
allocation in wireless networks," in Proceedings of 2nd IEEE COMSNETS Conference,
Bangalore, India, January 2010.
[68] ||, \A control-theoretic framework for mobility prediction in wireless networks," in
IEEE Wireless Networking and Communications Conference, Sydney, Australia, April
2010.
[69] B. W. Bequette, Process Control: Modeling, Design and Simulation. Prentice Hall,
Upper Saddle River, NJ, 2003.
94
[70] J. B. Rawlings, \Tutorial overview of model predictive control," IEEE Control Systems
Magazine, vol. 20, no. 3, pp. 38{52, Jun 2000.
[71] J. L. Hellerstein, Y. Diao, S. Parekh, and D. M. Tilbury, Feedback Control of Computing
Systems. Wiley-IEEE Press, 2004.
[72] Y. Diao, J. Hellerstein, A. Storm, M. Surendra, S. Lightstone, S. Parekh, and C. Garcia-
Arellano, \Using mimo linear control for load balancing in computing systems," in
Proceedings of the American Control Conference, 2004, vol. 3, July 2004, pp. 2045{
2050.
[73] D. Kusic, J. Kephart, J. Hanson, N. Kandasamy, and G. Jiang, \Power and performance
management of virtualized computing environments via lookahead control," in Proc.
IEEE Intl. Conf. on Autonomic Computing (ICAC), 2008.
[74] C. Hollot, V. Misra, D. Towsley, and W. bo Gong, \On designing improved controllers
for aqm routers supporting tcp  ows," in Proceedings of INFOCOM, 2000.
[75] Y. Lu, T. Abdelzaher, C. Lu, and G. Tao, \An adaptive control framework for qos
guarantees and its application to difierentiated caching," in Tenth IEEE International
Workshop on Quality of Service, 2002, pp. 23{32.
[76] S. Parekh, N. Gandhi, J. Hellerstein, D. Tilbury, T. Jayram, and J. Bigus, \Using
control theory to achieve service level objectives in performance management," Real-
Time Syst., vol. 23, no. 1/2, pp. 127{141, 2002.
[77] Z. Wang, X. Zhu, and S. Singhal, \Utilization and slo-based control for dynamic siz-
ing of resource partitions," in Proceedings of the 16th IFIP/IEEE Distributed Systems:
Operations and Management, Barcelona, Spain, October 2005.
[78] S. Keshav, \A control-theoretic approach to  ow control," in Proc. ACM SigComm
1991, September 1991.
[79] B. Li and K. Nahrstedt, \A control-based middleware framework for quality-of-service
adaptations," IEEE Journal on Selected Areas in Communications, vol. 17, no. 9, pp.
1632{1650, Sep 1999.
[80] S. Yarkan, A. Maaref, K. H. Teo, and H. Arslan, \Impact of mobility on the behavior
of interference in cellular wireless networks." in GLOBECOM. IEEE, 2008, pp. 2378{
2382.
[81] B. C. Jones and D. J. Skellern, \An integrated propagation-mobility interference model
for microcell network coverage prediction," Wirel. Pers. Commun., vol. 5, no. 3, pp.
223{256, 1997.
[82] T. Karagiannis, J.-Y. Le Boudec, and M. Vojnovi?c, \Power law and exponential decay
of inter contact times between mobile devices," in MobiCom ?07: Proceedings of the
13th annual ACM international conference on Mobile computing and networking. New
York, NY, USA: ACM, 2007, pp. 183{194.
95
[83] L. Qiu, Y. Zhang, F. Wang, M. K. Han, and R. Mahajan, \A general model of wireless
interference," in MobiCom ?07: Proceedings of the 13th annual ACM international con-
ference on Mobile computing and networking. New York, NY, USA: ACM, 2007, pp.
171{182.
[84] X. Zhang, J. Kurose, B. N. Levine, D. Towsley, and H. Zhang, \Study of a bus-based
disruption-tolerant network: mobility modeling and impact on routing," in MobiCom
?07: Proceedings of the 13th annual ACM international conference on Mobile computing
and networking. New York, NY, USA: ACM, 2007, pp. 195{206.
[85] J.-M. Kelif and M. Coupechoux, \On the impact of mobility on outage probability in
cellular networks," in Proceedings of IEEE WCNC, April 2009.
[86] T. Rappaport, Wireless Communications: Principles and Practice. Upper Saddle
River, NJ, USA: Prentice Hall PTR, 2001.
[87] A. Mawira, \Estimate of mean c/i and capacity of interference limited mobile ad-hoc
networks," in International Zurich Seminar on Broadband Communications, 2002. Ac-
cess, Transmission, Networking, 2002, pp. 51{1 { 51{6.
[88] M. Abramowitz and I. A. Stegun, Eds., Handbook of Mathematical Functions:
with Formulas, Graphs, and Mathematical Tables, 1st ed., ser. Dover books on
mathematics. Dover Publications, 1965. [Online]. Available: http://www.worldcat.
org/isbn/0486612724
96