Cooperative Positioning and Tracking in Disruption Tolerant Networks

No Comments

Cooperative Positioning and Tracking in Disruption Tolerant Networks


With the increasing number of location-dependent applications, positioning and tracking a mobile device becomes more and more important to enable pervasive and context-aware service. While extensive research has been performed in physical localization and logical localization for satellite, GSM and WiFi communication networks where fixed reference points are densely-deployed, positioning and tracking techniques in a sparse disruption tolerant network (DTN) have not been well addressed. In this paper, we propose a decentralized cooperative method called PulseCounting for DTN localization and a probabilistic tracking method called ProbTracking to confront this challenge. PulseCounting evaluates the user walking steps and movement orientations using accelerometer and electronic compass equipped in cellphones. It estimates user location by accumulating the walking segments, and improves the estimation accuracy by exploiting the encounters of mobile nodes. Several methods to refine the location estimation are discussed, which include the adjustment of trajectory based on reference points and the mutual refinement of location estimation for encountering nodes based on maximum-likelihood. To track user movement, the proposed ProbTracking method uses Markov chain to describe movement patterns and determines the most possible user walking trajectories without full record of user locations. We implemented the positioning and tracking system in Android phones and deployed a testbed in the campus of Nanjing University. Extensive experiments are conducted to evaluate the effectiveness and accuracy of the proposed methods, which show an average deviation of 9m in our system compared to GPS.


  • Several recent research focuses on GPS-free localization in wireless networks by incorporating fixed landmarks and surrounding characteristics.
  • Surround Sense identifies logical location using the surrounding information like sounds, lights and colors.
  • CompAcc adopts a distance estimation method using accelerometer and compass and determines location by matching to possible path signatures generated from an electronic map.
  • Escort provides a logical navigation system to help a person navigate to another person in a public place with the aid of context features.


  • Escort provides a logical navigation system for social localization. Its goal is not to identify the physical location, but to help a person navigate to another person in a public place such as a hotel. By periodically learning the walking trails of different individuals, as well as how they encounter each other in space-time, a route is computed between any pair of persons. However, it needs global information of users’ movements and their encounters to construct the navigation graph, which does not apply for DTNs.
  • These methods need continuous communication with a centralized server to process a large amount of surrounding data, which are not suitable for the decentralized structure and the opportunistic communication nature of DTNs.


  • In this paper, we propose a decentralized cooperative method called PulseCounting for DTN localization and a probabilistic method called ProbTracking to track the movement of mobile nodes.
  • PulseCounting evaluates the number of user walking steps using the accelerometer data, and decides the orientation of each step using the electronic compass measurements. By accumulating the segments of walking steps, it is able to form an estimation of current location.
  • PulseCounting further takes advantage of the opportunity of encounters in DTNs to refine the location estimation: on the one hand, the encountering APs and phones equipped with GPS could be regarded as reference points; on the other hand, the encounters of two mobile nodes enable the possibility of mutual adjustment to reduce estimation error.
  • ProbTracking detects the movement trajectory based on the partial location information reported by the other mobile nodes. It constructs a Markov chain using the movement his tory data and uses it to determine the most probable user walking route without the need for global location information in DTNs


  • It constructs a Markov chain using the movement history data and uses it to determine the most probable user walking route without the need for global location information in DTNs.
  • Accuracy of direction mapping




  1. Bootstrapping
  2. Step counting
  3. Direction mapping
  4. Trajectory generation
  5. Location estimation



As the first step, each node needs to know its position initially. Without the initial position, there is no reference point for location estimation. In DTNs, we assume a small number of fixed landmarks (e.g., wireless APs) are deployed in the environment with known locations. We also assume that there are a few GPS-nodes willing to report their locations to other nodes. Thus the common-nodes can obtain a rough initial location when they firstly encounter the land-marks or GPS-nodes. It is unlikely for all common-nodes to obtain their initial locations at the same time, so the initialization process is asynchronous. With the initial location information, a map in this area will be downloaded to the user’s cellphone. We use the Google Map in our implementation since it provides open access to its data and APIs. The map is downloaded opportunistically when the device has a chance to access the Internet (i.e., entering the communication range of an AP).

Step counting:

We introduce the method of using the accelerometer to measure walking steps. The accelerometer records user movement in three dimensions: X (the direction of front and back), Y (the direction of left and right), and Z (the direction of up and down). As we plot the accelerometer data of users with the cellphone putting in three different positions: holding horizontally in hand, sticking vertically in front pocket, and sticking vertically in back pocket. Observation reveals several characteristics: (1) The acceleration is non-uniform. It shows a pattern of “increase-decrease” and fluctuates around some value. (2) The data is noisy. It is influenced by the way people walks and the position of their cellphones. (3) It has obvious periodicity and its shape looks like a wave. The periodical phenomenon is most clear in the direction of Z axis (up and down) of all cellphone positions. During movement, the human’s center of gravity goes up and down, which causes the increasing and decreasing of his accelerations. Thus a period in the accelerometer reading corresponds to two walking steps in reality.

Direction mapping:

The other important aspect of movement is direction, which can be measured by electronic compass. The cellphone compass records the users orientation in the form of an angle with respect to magnetic north. Similar to the accelerometer data, the compass data is densely sampled (about 22 data per seconds) and appears fluctuating and noisy, thus it cannot be used directly. We proposed the direction mapping method to make the compass data discrete. For a rough estimation, we project the compass data to eight discrete directions: North, Northeast, East, Southeast, South, Southwest, West, and Northwest, which are numbered by 0-7 accordingly.

Trajectory generation:

With the results from step counting and direction mapping, we are able to describe user movement trajectories. A movement trajectory is defined as a series of segments with distance and direction. Each tuple < Si, θi >(i = 1, 2,… ,M ) indicates a segment of the movement. Si is the moving distance of two consecutive walking steps (one period of the acceleration); θi is the movement direction (measured by the angle to the north) in the steps, which is obtained by the direction mapping method. M is the total number of segments.

Location estimation:

Given a trajectory T (P0 P1), if the location of departure point P0 is known, we can roughly estimate the location of P1 by accumulating the trajectory segments. However, due to the inaccuracy of step size and orientation measurement, errors may be introduced during the estimation of each segment. With the number of segments increase, the errors are accumulated, thus the estimated location will be far away from the actual location. To overcome this drawback, we use the encounter opportunity of nodes to improve the estimation accuracy, which is introduced in the following subsection.




  • System :         Pentium IV 2.4 GHz.
  • Hard Disk :         40 GB.
  • Floppy Drive : 44 Mb.
  • Monitor : 15 VGA Colour.
  • Mouse :
  • Ram : 512 Mb.


  • Operating system : Windows XP/7.
  • Coding Language : Java 1.7
  • Tool Kit : Android 2.3 ABOVE
  • IDE : Eclipse


Wenzhong Li, Member, IEEE, Yuefei Hu, Student Member, IEEE, Xiaoming Fu, Senior Member, IEEE, Sanglu Lu, Member, IEEE, and Daoxu Chen, Member, IEEE, “Cooperative Positioning and Tracking in Disruption Tolerant Networks,”. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 26, NO. 2, FEBRUARY 2015

Contact Form

Fields marked with an * are required