15-02-2013, 04:27 PM
The Boomerang Protocol: Tying Data to Geographic Locations in Mobile Disconnected Networks
1The Boomerang Protocol.pdf (Size: 1.55 MB / Downloads: 41)
Abstract
We present the boomerang protocol to efficiently retain information at a particular geographic location in a sparse
network of highly mobile nodes without using infrastructure networks. To retain information around certain physical location, each
mobile device passing that location will carry the information for a short while. This approach can become challenging for remote
locations around which only few nodes pass by. To address this challenge, the boomerang protocol, similar to delay-tolerant
communication, first allows a mobile node to carry packets away from their location of origin and periodically returns them to the anchor
location. A unique feature of this protocol is that it records the geographical trajectory while moving away from the origin and exploits
the recorded trajectory to optimize the return path. Simulations using automotive traffic traces for a southern New Jersey region show
that the boomerang protocol improves packet return rate by 70 percent compared to a baseline shortest path routing protocol. This
performance gain can become even more significant when the road map is less connected. Finally, we look at adaptive protocols that
can return information within specified time limits.
INTRODUCTION
AS daily mobile devices such as smart phones, PDAs,
and digital cameras start to be used as sensing devices
[1], [2], [3], mobile sensing is becoming a social event
instead of a high-tech phenomenon. Compared to today’s
special-purpose sensing applications such as automotive
traffic congestion monitoring [4] and pothole detection [5],
mobile sensing takes place anytime, anywhere, and will
have far more diverse meanings. A direct consequence of
this trend is the production of a vast amount of data, in
terms of both type and volume. Example data types include
pictures, videos, audios, and plain text-based sensor readings.
These data can potentially bring great convenience to
the society as they can serve as traces of our lives and logs
of the physical world.
SYSTEM MODEL AND APPLICATIONS
We consider a scenario where nodes move along constrained
two-way paths. Nodes can communicate intermittently
via high-bandwidth short-range radios (e.g., 802.11)
with other nearby nodes or through a continuous lowbandwidth
wide-area network (e.g., cellular network). We
assume that nodes have high-storage capacity and are
aware of their geographic positions (e.g., via GPS), but the
communication and localization systems do not rely on
proprietary road maps.
Mobile data management through Geocache. As mobile
devices start to produce large volumes of data, efficient
management of such data can bring great convenience to
our daily life. Let us look at the motivating scenario
illustrated in Fig. 1.
Alice took a picture of a car accident using her cell phone
when she drove by the accident scene. Bob, the victim in the
accident, was eagerly seeking such pictures as evidence to
support his claims in front of the judge or his insurance
company. A traditional solution for exchanging the information
would likely involve Alice uploading her picture
to a server where Bob can download from (after consulting
popular search engines such as Google). However, as
mentioned earlier, this solution does not scale well with
the data volume we may expect from anytime-anywhere
mobile sensing. Instead, we propose a highly distributed
approach in which mobile devices keep the data locally, but
leave a log around the geographic location where the data
were generated.
GEOCACHE ANCHORING PROTOCOLS
The goal of the Geocache anchoring protocols is to retain
Geocache data around the corresponding anchor location
while minimizing communication overhead.
Intuitively, we envision the following anchoring process:
the mobile node that currently carries the Geocache
(referred to as the carrier) is moving away from the anchor
location. To avoid taking the Geocache away, it hands off
the data to other nodes, preferably those traveling toward
the anchor location. After receiving the data, the new carrier
node will periodically examine whether another handoff is
needed. This process repeats until the data returns to the
anchor location, and we call this protocol a boomerang
protocol because the data eventually return to its origin like
a boomerang.
To motivate how this boomerang approach can reduce
communication overhead, let us consider a brief thought
experiment. One could retain information at the anchor
location by simply handing off the Geocache whenever the
anchor location moves out of the radio range. In an
idealized model with constant radio range r, vehicular
velocity v and high vehicle density, retaining the Geocache
for a duration t would require m ¼ tv
r handoffs. However,
under ideal settings, the boomerang approach can reduce
the number of transmissions to m ¼ 2 (one to the new
carrier heading back and one to the anchor location). Thus,
the boomerang approach has the potential to significantly
reduce transmission overhead when the Geocache content
is only needed periodically.
TRAJECTORY CONSTRUCTION IN REVTRAJ
The primary challenge in implementing the trajectory-based
boomerang protocol lies in the construction of the Geocache
trajectory, and the detection of divergence from a given
trajectory. To illustrate these challenges, let’s consider the
example in Fig. 5, where the Geocache was handed off to Q
who was traveling in the opposite direction of P’s
trajectory. After traversing the path until B0, Q diverges
from P’s trajectory and heads for A0. In this case, Q must be
able to detect the divergence and start extending the path
history from B0, so that at its next handoff, a modified path
A ! BðB0Þ ! A0 will be passed to the new carrier node O.
The challenge in this implementation lies in developing
robust trajectory update and divergence detection algorithms
that are feasible across a variety of road networks.
Divergence Detection
When on the return path to the anchor location, a node
shrinks the saved trajectory by removing segments it has
passed. Meanwhile, it also needs to continuously check if it
has diverged from the remaining trajectory.
Intuitively, a divergence from the trajectory will result in
a noticeable change in the heading direction, as well as a
distance increase from the trajectory. However, using one
factor alone to determine divergence could be erroneous.
Lane shift, the individual’s driving behavior and many
other factors may all lead to a sudden direction change
without actual divergence. Further, the variance in road
widths (e.g., 15 to 60 ft for city roads2) makes the selection
of a single distance threshold difficult.
ADAPTIVE HANDOFF FOR In-time ANCHORING
After studying how to return Geocache to the anchor
location in the general setting, we next look at a specific
anchoring requirement, in-time anchoring. Here, the Geocache
is required to return to the anchor location within a
specific time interval. A wide range of mobile applications
have such requirements. For example, a mobile user may
have a query “what is the average car speed around my
location for the next 5 minutes?” He only accepts real-time
responses within the next few minutes, and after that, he
will lose interest and leave.
The challenge here is twofold. First, we would like to
have in-time returns. Second, we would like the return time
to be as close to the expected return time as possible. If the
Geocache is returned too early, we need to either keep the
Geocache exactly at the anchor location until the deadline,
which incurs high communication overhead, or continue to
boomerang the Geocache, with the risk of late returns.