14-02-2013, 10:05 AM
Geographical Routing with Location Service in Intermittently Connected MANETs
Geographical Routing.pdf (Size: 390.07 KB / Downloads: 32)
Abstract
Combining mobile platforms such as manned or
unmanned vehicles and peer assisted wireless communication is
an enabler for a vast number of applications. A key enabler for
the applications is the routing protocol that directs the packets in
the network. Routing packets in fully connected mobile ad hoc
networks (MANETs) has been studied to a great extent, but the
assumption on full connectivity is generally not valid in a real
system. This means that a practical routing protocol must handle
intermittent connectivity and the absence of end-to-end
connections. In this paper we propose a geographical routing
algorithm LAROD enhanced with a location service LoDiS,
together shown to suit an intermittently connected MANET (ICMANET).
Since location dissemination takes time in ICMANETs
LAROD is designed to be able to route packets with
only partial knowledge of geographic position. To achieve a low
overhead LAROD uses a beacon-less strategy combined with
position-based resolution of bids when forwarding packets.
LoDiS maintains a local database of node locations which is
updated using broadcast gossip combined with routing
overhearing.
INTRODUCTION
OUTING in systems of mobile nodes with no infrastructure
support has received a lot of attention in the last decade.
This began in the field of mobile ad hoc networks (MANETs)
and then carried over to the field of delay-tolerant networks
(DTNs). Despite the solid body of work on routing schemes
there is a lack of momentum in applying them in real-world
systems. Lindgren and Hui [1] suggest some applications
where DTN routing is more attractive than conventional
infrastructure-based solutions. Two areas that can be added to
their review are disaster scenarios and military operations,
areas we believe can spearhead the application of DTN
technology. Works on disaster area networks are emerging
[2][3] and the Unmanned Aircraft Systems Flight Plan 2009-
2047 for the US Air Force [4] envisions swarming unmanned
aerial vehicles (UAVs) communicating with MANET
technology.
BACKGROUND AND RELATED WORK
Proposals on how to route packets in MANETs comprise a
massive body of research in ad hoc networks. In the last decade
this interest has broadened into networks with intermittent
connectivity. In this section we give an overview of relevant
research in the MANET and DTN area regarding geographical
routing and location services. We also present the military
reconnaissance mobility model used in the evaluations.
A. IC-MANET Routing
In a wireless ad hoc network where a contemporaneous path
can never be assumed to exist between any two nodes, mobility
can be used to bridge the partitions. When no suitable
forwarding opportunity exists a routing node can choose to
temporarily store a packet until node mobility presents a
suitable forwarding node. This routing paradigm is called
store-carry-forward.
Cerf et al. have described an architecture for DTNs [13]
where a large and heterogeneous system transports data
bundles between custodians that temporarily store the bundles
until they can be forwarded again. The main difference
between their view of a DTN and our view of an IC-MANET
is in the size and diversity of the systems. We see an ICMANET
as a relatively homogeneous system with a relatively
modest spatial distribution. This difference in system
properties leads to the proposal that the routing should be done
on the network (i.e. IP) layer instead of on top of the transport
layer. This choice is in line with how routing is done in
MANETs.
Mobility Models
The choice of mobility model when evaluating IC-MANET
routing protocols is important since the performance of a
routing protocol will change depending on how the nodes
move [21][22]. We have chosen a military reconnaissance
operation mobility model as the main model used in the
evaluations [5]. For comparative reasons we have also used the
random waypoint mobility model [23]. Extensive surveys on
mobility models can be found in articles by Camp et al. [24]
and Aschenbruck et al. [25].
The goal of a reconnaissance operation is to monitor an area
and to detect defined types of activities. Due to high costs it is
generally not possible to monitor the entire area continuously
and instead all parts of the area need to be regularly scanned. In
a military setting it is also a requirement that the scanning shall
not exhibit any apparent pattern (to make it harder to avoid
detection), and the system must be robust upon loss of some of
the scanning nodes. The mobility model we use utilizes
distributed pheromones to guide the scanning nodes, the
UAVs, to areas not recently scanned.
EVALUATION
In this section we present the results from our evaluations of
LAROD-LoDiS. The routing protocols have been evaluated in
the network simulator ns-2 using both the pheromone
reconnaissance mobility model and the random waypoint
mobility model (for comparative purposes). The setup of the
simulator for the evaluations is detailed in Section IV.A. The
configuration parameters for LAROD and LoDiS are studied
in Sections IV.B and IV.C and this is followed in Section IV.D
by an evaluation of how the choice of mobility model impacts
LAROD-LoDiS. Finally, in Section IV.E we compare the
performance of LAROD-LoDiS to Spray and Wait.
FUTURE WORK
LoDiS is a very good base to use for further studies of
location services in IC-MANETs and DTNs. Depending on
what one considers a reasonable scenario for an IC-MANET
further studies and improvements of the LAROD-LoDiS
routing algorithm should be done for very sparse systems
(nodes normally lacking a neighbor) or a mixed scenario with
both dense and sparse areas. Current work includes evaluation
of a manycast algorithm in disaster area networks where
pockets of intense activity and large sparse areas can be
simultaneously present [3]. Also, the location service
performance should be studied for very large systems
(thousands of nodes). For the very sparse systems information
dissemination will probably be very slow and it is not certain
that geographical routing is the best choice in such a scenario.
For very large systems the challenge will be how to distribute
the location information for all the nodes in the system. To do
this one probably has to employ some kind of data
compression or approximation methods for nodes located far
away.
CONCLUSION
The availability of node location information enables the use
of efficient geographical routing protocols in MANETs and
IC-MANETs. A major component for a geographical routing
protocol is a well performing location service. The location
service will provide information on where a destination is
located in order to have a point to route a packet towards.
In this paper we have shown that by using a MANET
broadcast gossiping technique and continuous modification of
packet location information, geographical routing in ICMANETs
is feasible.