05-07-2012, 12:03 PM
An Improved Geocast for Mobile Ad Hoc Networks
[attachment=26809]
Abstract
Geographic addressing of packets within mobile ad hoc networks enables novel applications, including hard real-time
engagement simulation in military training systems, geographic command and control functions in training and emergency
communications, and commercial messaging applications as well. The most scalable implementation of geoaddressing is via a
geocast protocol, where nodes selectively retransmit packets based on local decision rules. Well-designed retransmission heuristics
yield scalable geographic flooding that outperforms alternative geoaddressing approaches. However, previous geocast
implementations, while effective, fall into two categories.
INTRODUCTION
GEOGRAPHIC addressing within mobile ad hoc networks
(MANETs [1]) enables interesting new applications.
These include hard real-time engagement simulation in
military training and testing systems, geographic command
and control in areas lacking network infrastructure, emergency
communications for disaster response, and commercial
geographic messaging applications, such as gaming,
advertising, and traffic services [2]. In engagement simulation
by geometric pairing, as is done by the US Army’s
One Tactical Engagement Simulation System (OneTESS),
www.peostri.army.mil/PRODUCTS/ONETESS, an instrumentation
system mounts sensors and a wearable, locationaware
computational device on each human trainee and
weapon.
THE GEOCAST FRAMEWORK
Throughout this paper, we assume that each mobile node is
location aware, meaning it knows its location at all times, such
as via an onboard GPS unit. Geocast is a network protocol for
sending a packet to all nodes within a defined geographic
region termed as the geocast region. Hall and Auzins [4]
describe a multitiered framework for geocast in MANETs.
The framework comprises a heuristic-based limited flooding
technique, termed a flat geocast, that operates within each
single tier, a tier being a distinct wireless channel. Typically,
distinct tiers will operate at different transmission ranges; for
example, in a military scenario, it may be that vehicles have
two-tier radios capable both of operating on a short-range
channel shared with equipment carried by dismounted
soldiers and also of operating on a longer range channel to
communicate at distance to other vehicles or buildings.
THE CD-P HEURISTIC
As discussed in [4], Classic Geocast is effective in a wide
variety of situations, more scalable than simple flooding,
and more reliable than simple broadcast. However, recent
experience has exposed a weakness in urban terrain. The
latter is characterized by restricted, maze-like radio lines of
sight (due to buildings, etc.) and multipath effects.
Fig. 3 shows an example urban scenario. In it, nodes are
located in streets and avenues of a Manhattan-style
geometry; the dark squares represent buildings that completely
block radio signals from penetrating through them.
(Thus, connectivity is purely line-of-sight.) The transmission
range of each radio is assumed to be three blocks; so,
for example, node 1 can hear node 3 and vice versa. We
attempt to send a geocast from the node at third and A to
the dark circle centered at first and B. A typical Classic
Geocast transmission sequence is shown.
Scenario Selection
We have selected 14 scenarios covering a range of complexity
measures in numbers of nodes, terrain complexity, and
traffic load. These scenarios represent realistic battlefield
training scenarios envisioned for the OneTESS system, as
well as more abstract random node placements and traffic.
The geocasts in the training-like scenarios are used to
implement engagement simulation of long-range shots, as
well as geographic command and control messaging. Rather
than describing each scenario in detail, we summarize them
in Fig. 9. In the figure, each scenario (numbered 1 . . . 14) is a
numbered box, with number of mobile nodes in the scenario
in parentheses. The position of the box semiquantitatively
represents its position in two other complexity dimensions.
The horizontal position indicates its terrain complexity.
RELATED WORK
Geographic routing protocols fall into two broad classes:
those that do not require current neighbor-topology information
and those that do. Generally, topology-based
approaches suffer from three drawbacks in the high-scale
scenarios of interest in this paper. First, we seek scaling to
high geographic density; since topology-packet traffic grows
in proportion to density, this overhead can become
prohibitive. Second, we seek scaling to medium and high
levels of node mobility. This leads to topology information
rapidly becoming stale, which tends to mislead the
algorithms relying on it. Finally, topology-based approaches
depend on link symmetry: if a node hears a packet from a
neighbor, the assumption is that it can be heard by the
neighbor as well.
CONCLUSIONS
CD-P is a novel heuristic designed to support geocast in
high-scale MANET applications and integrated into the
Classic Geocast framework, allowing it to complement
other heuristics. It is based upon three key ideas. First, a
node retransmits if it is closer to the center of the geocast
region than all other copies it has heard transmitted.
Second, it listens to other retransmissions continuously
prior to its own retransmission and cancels its own if it
hears another node transmit closer to the center first. And
third, scalability relies on each node prioritizing its send
queue to send soonest those packets that make the most
progress toward the center of their geocast regions.
[attachment=26809]
Abstract
Geographic addressing of packets within mobile ad hoc networks enables novel applications, including hard real-time
engagement simulation in military training systems, geographic command and control functions in training and emergency
communications, and commercial messaging applications as well. The most scalable implementation of geoaddressing is via a
geocast protocol, where nodes selectively retransmit packets based on local decision rules. Well-designed retransmission heuristics
yield scalable geographic flooding that outperforms alternative geoaddressing approaches. However, previous geocast
implementations, while effective, fall into two categories.
INTRODUCTION
GEOGRAPHIC addressing within mobile ad hoc networks
(MANETs [1]) enables interesting new applications.
These include hard real-time engagement simulation in
military training and testing systems, geographic command
and control in areas lacking network infrastructure, emergency
communications for disaster response, and commercial
geographic messaging applications, such as gaming,
advertising, and traffic services [2]. In engagement simulation
by geometric pairing, as is done by the US Army’s
One Tactical Engagement Simulation System (OneTESS),
www.peostri.army.mil/PRODUCTS/ONETESS, an instrumentation
system mounts sensors and a wearable, locationaware
computational device on each human trainee and
weapon.
THE GEOCAST FRAMEWORK
Throughout this paper, we assume that each mobile node is
location aware, meaning it knows its location at all times, such
as via an onboard GPS unit. Geocast is a network protocol for
sending a packet to all nodes within a defined geographic
region termed as the geocast region. Hall and Auzins [4]
describe a multitiered framework for geocast in MANETs.
The framework comprises a heuristic-based limited flooding
technique, termed a flat geocast, that operates within each
single tier, a tier being a distinct wireless channel. Typically,
distinct tiers will operate at different transmission ranges; for
example, in a military scenario, it may be that vehicles have
two-tier radios capable both of operating on a short-range
channel shared with equipment carried by dismounted
soldiers and also of operating on a longer range channel to
communicate at distance to other vehicles or buildings.
THE CD-P HEURISTIC
As discussed in [4], Classic Geocast is effective in a wide
variety of situations, more scalable than simple flooding,
and more reliable than simple broadcast. However, recent
experience has exposed a weakness in urban terrain. The
latter is characterized by restricted, maze-like radio lines of
sight (due to buildings, etc.) and multipath effects.
Fig. 3 shows an example urban scenario. In it, nodes are
located in streets and avenues of a Manhattan-style
geometry; the dark squares represent buildings that completely
block radio signals from penetrating through them.
(Thus, connectivity is purely line-of-sight.) The transmission
range of each radio is assumed to be three blocks; so,
for example, node 1 can hear node 3 and vice versa. We
attempt to send a geocast from the node at third and A to
the dark circle centered at first and B. A typical Classic
Geocast transmission sequence is shown.
Scenario Selection
We have selected 14 scenarios covering a range of complexity
measures in numbers of nodes, terrain complexity, and
traffic load. These scenarios represent realistic battlefield
training scenarios envisioned for the OneTESS system, as
well as more abstract random node placements and traffic.
The geocasts in the training-like scenarios are used to
implement engagement simulation of long-range shots, as
well as geographic command and control messaging. Rather
than describing each scenario in detail, we summarize them
in Fig. 9. In the figure, each scenario (numbered 1 . . . 14) is a
numbered box, with number of mobile nodes in the scenario
in parentheses. The position of the box semiquantitatively
represents its position in two other complexity dimensions.
The horizontal position indicates its terrain complexity.
RELATED WORK
Geographic routing protocols fall into two broad classes:
those that do not require current neighbor-topology information
and those that do. Generally, topology-based
approaches suffer from three drawbacks in the high-scale
scenarios of interest in this paper. First, we seek scaling to
high geographic density; since topology-packet traffic grows
in proportion to density, this overhead can become
prohibitive. Second, we seek scaling to medium and high
levels of node mobility. This leads to topology information
rapidly becoming stale, which tends to mislead the
algorithms relying on it. Finally, topology-based approaches
depend on link symmetry: if a node hears a packet from a
neighbor, the assumption is that it can be heard by the
neighbor as well.
CONCLUSIONS
CD-P is a novel heuristic designed to support geocast in
high-scale MANET applications and integrated into the
Classic Geocast framework, allowing it to complement
other heuristics. It is based upon three key ideas. First, a
node retransmits if it is closer to the center of the geocast
region than all other copies it has heard transmitted.
Second, it listens to other retransmissions continuously
prior to its own retransmission and cancels its own if it
hears another node transmit closer to the center first. And
third, scalability relies on each node prioritizing its send
queue to send soonest those packets that make the most
progress toward the center of their geocast regions.