OVERVIEW

While mobility has been addressed in several domains, including wireless sensor networks and software processes, the emergence of GPS technology and sensors that can measure distance, speed, and acceleration have enabled much more accurate navigation through an instrumented field and tracking of subjects and objects of interest. At the same time, knowledge about the sensors location and trajectories can greatly improve both data aggregation and sensor fusion. From a technical point of view, mobility can be studied in two components: mobility modeling, and the application of the mobility model on a selected subset of networking and sensing tasks in wireless multi-hop ad-hoc networks.

APPROACHes

In this project, we propose the development of a layered mobility model. The proposed mobility model has five layers: measurements to points, points to trajectories, intentions to trajectories, intention-based Markov Chain, and Markov Chain-based inter-environment. We currently address the two lowest levels of the model: (i) how to combine measurements from different types of sensors in order to obtain maximum likelihood positions of the object, and (ii) how to calculate a compact representation of a particular sequence of positions into compact object trajectories for building a precise and compressed model of the user’s movement. We formulate the first problem as an instance of nonlinear function minimization and use Powell’s method to iteratively find a solution. Sequences of points in 2-dimensional or 3-dimensional space are the basis of our second problem. The objective of our second problem is to find a small subset of points in space that characterize the trajectory well, in the sense that each point of the piecewise linear approximation trajectory formed using the initial point is within a small distance of piecewise linear approximation formed using the new points. Note that, therefore, there are continuously many alternatives to select the points which represent our particular trajectory. The second problem is first abstracted to a graph theoretical formulation and consequently solved using Dijkstra shortest path algorithm optimally in polynomial time.

With various stages of the mobility model in place, the goals of this project transfers to addressing the benefits and effects the mobility model has on existing networking tasks and on the development of new networking approaches which consider mobility components. We target a set of networking tasks: routing, multicast, broadcast, aggregation, and resource and power management.

Algorithmic Development
The goals for the mobility model are three-fold:  prediction, compression and simulation. Predication can be defined as the task of deducing the location, direction, speed and acceleration of a subject in the presence of information from the limited past history about the same entities. Compression calls for compact representation of large volumes of data about location, direction, speed, and acceleration of one or more subjects. Finally, simulation is required to enable a number of network management and network design tasks.

In order to address these three goals, we are developing algorithmic approaches at each level of the mobility model which will enable accurate, compact representation of the object’s movement. At the lowest level of abstraction, our goal is to use sensor measurements (distance from beacons, speed, acceleration, and angle) collected from an instrumented environment of an object’s movement at a particular point in time. The goal is not only to find maximum likelihood position, speed, and acceleration of the object at a given period of time, but also to provide density distribution functions for any combination of these four parameters.  We accomplish this task by using a combination of maximum likelihood non-linear function minimization algorithms and software and a suite of non-parametric modeling and evaluation techniques. We have developed a series of algorithms that provide a flexible trade-off between accuracy and computation runtime and communication costs.

Once, when we have information about the speed, acceleration, angle, and position of an object at k time points, the second layer of our mobility model aims to combine this information in most likely compact trajectory and series of mobility parameters. For this task, we have developed two generic techniques. The first one is a based on the combination of statistical parametric techniques and graph theoretic optimization mechanisms. The second one utilizes non-linear program formulation.

The two bottom levels of the model are dedicated to efficient and accurate translation of sensor readings into mobility parameters.  The two top layers of our model are dedicated to efficient and effective mapping of human behavior into mobility actions.  The middle layer aims to provide an interface between these two conceptual diverse domains. Specifically, the goal is that once that we have deduced information about the intention of a subject to move from a point A to a targeted point B, this layer tries to answer the question: what is the most likely trajectory which a particular user will follow to accomplish this goal. It is important to emphasize that this trajectory can be updated as additional information about the subject’s past movement becomes available.

FUTURE DIRECTIONS

In the next phase, the goal of this project is to continue development of algorithms for the mobility model layers. Additionally, the goal is to establish data sources for actual mobile trajectories or to build hardware/environment for collecting data from a mobile object.

PEOPLE

FACULTY

Prof. Miodrag Potkonjak

GRADUATE STUDENTS

Jennifer Wong