17-01-2013, 03:57 PM
Adaptive Routing in Dynamic Ad Hoc Networks
Adaptive Routing in Dynamic Ad Hoc.pdf (Size: 141.15 KB / Downloads: 37)
Abstract—
Dynamic ad hoc networks are mobile ad hoc networks
(MANETs) where network characteristics, such as network
density and node mobility, change significantly over time and
space. Sometimes, dynamic ad hoc networks resemble a dense
ad hoc network. At other times, they resemble a delay tolerant
network. Many real networks follow the paradigm of dynamic
ad hoc networks. Military networks, wildlife tracking sensor
networks, and vehicle networks are some of these examples.
In dynamic ad hoc networks, conventional routing schemes
fail when the network characteristics do not fall into their
applicable scenarios. Previous research has proposed a variety of
routing schemes for each specific network scenario. For instance,
distributed routing tables are built for efficient multi-hop, singlecopy
routing in static and dense networks. Mobility assisted,
multi-copy routings are proposed in sparse networks where
contemporary paths might not exist. With the advantages of the
existing schemes in mind, we introduce a new routing scheme,
Adaptive ROuting in Dynamic ad hoc networks (AROD), which
is a seamless integration of several existing schemes. Simulation
results show that AROD is highly scalable and is adaptive to
different network scenarios.
Keywords: Adaptive routing protocol, dynamic ad hoc networks,
delay tolerant networks (DTNs).
I. INTRODUCTION
In mobile ad hoc networks (MANETs), two nodes can
exchange data when they are located within one another’s
communication range. A node can deliver data to another node
directly or via intermediate nodes without relying on basestations.
Traditional ad hoc routing uses a single-copy, multihop
delivery scheme under the assumption of the existence of
contemporary source-destination paths and unlimited network
capacity.
Interest has grown over the past few years in delay tolerant
networks (DTNs). DTNs are usually sparse, such that
a contemporary path between a source and a destination
might not exist, and delivery of messages must utilize node
mobility. A path existing between a source and a destination
in a DTN means that the source and the destination are
connected in the overlapped evolving network graphs. The
primary focus of existing DTN routing protocols is to increase
the likelihood of finding such a path, in extremely sparse
networks with extremely limited information. To this end, a
variety of mechanisms are used, including estimating meeting
probabilities, message replication, network coding, placement
of stationary storage devices, and using prior knowledge of
mobility.
a sparse sub-network, and white static nodes form a dense one.
Our interests lie in developing an algorithm that is as
general as possible. We model dynamic ad hoc networks as
MANETs which are connected most of the time but are not
always disconnected due to mobility. In a dynamic ad hoc
network, network characteristics can change significantly over
time and space. At certain times the mobile nodes might
gather, enabling the instant communication between the nodes
using direct or multi-hop delivery. At other times, nodes might
spread and roam around a large geographical region, and it is
appropriate to deliver messages in a store-and-forward, multicopy
scheme to increase delivery probability and decrease
delivery time. Many real networks follow the paradigm of
dynamic ad hoc networks. Military networks [1], wildlife
tracking sensor networks [8], and vehicle networks [3] [12]
are some of these examples. An example of a dynamic ad
hoc network is shown in Figure 1, where some nodes that are
sparsely deployed with randomized trajectories form a DTN
sub-network, while other nodes stay close to each other and
form a dense sub-network.
Different existing routing protocols would work well for the
different scenarios exhibited by a dynamic ad hoc network.
However, it is inconvenient to require the users to switch
between multiple routing protocols. Moreover, if different
scenarios are exhibited by different parts of a network, the
routing protocols used must be able to communicate and
cooperate with each other, which is another difficult task. Thus,
a routing protocol that is adaptive in an effor to maintain good
performance and that also operates seamlessly in different
network scenarios is desired. In this preliminary work, we
investigate an adaptive routing algorithm in dynamic ad hoc
networks, aiming to show that such a protocol is possible
rather than proposing a routing protocol to optimize the routing
performance in different scenarios.
The goal of our algorithm is to be adaptive to different
network densities and different mobility models. We broadly
discriminate two kinds of mobility models: local mobility and
random mobility. In local mobility, each node has a home
region which it visits more often than other regions. As a
result, it meets some nodes more frequently than others. Local
mobility also includes the situations where the nodes do not
have preferred regions, but the dissemination of the meeting
information is fast enough to form gradients of delivery
probabilities among the nodes. Random mobility refers to
the opposite situation where the motion of the nodes is fast
and random, which leads to difficulties when attempting to
estimate delivery probability in the network.
The design principle of our proposed Adaptive ROuting in
Dynamic ad hoc networks (AROD) is exemplified as follows.
In a network that has an adequate communication capacity
(i.e., the total transfer opportunities in the network) and a
clear gradient of decreasing estimated delivery latency or
increasing delivery probability to each destination, such as a
dense network with a local mobility pattern, it is suffice to use
a single-copy and multi-hop delivery. However, in a sparse
mobile network with random mobility and limited transfer
opportunities, mobility-assisted and multi-copy delivery is
used to shorten the delivery time and increase the delivery
ratio. AROD adaptively trades off delivery latency/probability
to bandwidth consumption. It is a seamless integration of the
different routing schemes used for different network scenarios.
The remainder of this paper is presented as follows. In
Section II, we go over some related work and summarize
our contributions. Section III presents our proposed solution,
AROD, and its implementation details. Section IV shows the
adaptive performance of AROD in different network scenarios.
Finally, Section V concludes the paper and discusses ideas for
future work.
II. RELATED WORKS AND CONTRIBUTIONS
This paper focus on routing protocols in mobile ad hoc
networks that do not rely on particular hardware support or
prior knowledge, such as a GPS that provides a node with its
position, a powerful global channel to disseminate the status
information of the nodes, or a bounded network area. Previous
work on MANETs has been based on various assumptions
regarding node density and mobility models. Conventional
ad hoc network routing schemes such as DSR [7], AODV
[5], and DSDV [13] are proposed in dense networks where
contemporary source-destination paths exist.
In delay tolerant networks [6], especially the extremely
sparse networks where the average node degree is smaller
than 1, messages can still be delivered if paths exist in the
evolving graph of the network. Existing routing schemes such
as Epidemic [15], Prophet [10], Spray and Wait [14], Spray
and Focus [14], MaxProp [3], and RAPID [2], use a storecarry-
forward scheme.
Previous proposed adaptive routing protocol includes CAR
[11], where routing methods are selected depending on
whether the recipient presents in the same connected component
(cloud) in the network. If it does, the message is
delivered by DSDV [13]. Otherwise, the message is sent to the
node in the cloud which has the highest delivery probability.
This protocol, however, uses pure single-copy forwarding and
works well only for local mobility.
Routing information is exchanged by peers in the control
channel of AROD. Our approach is built on several important
insights from previous works. Chen and Nahrstedt [4] and
Spyropoulos et al. [14] use replicas to decrease average delay
and increase delivery rates. Leguay et al. [9], Burgess et al. [3],
Levine et al. [2], and Leguay et al. [14] suggest using historical
connectivity information and predictions of future connectivity
information in order to improve routing performance. Burgess
et al. [3] shows that flooding acknowledgements effectively
reduce delays and increase delivery rates by freeing up resources
used by delivered packages. Mirco et al. [11] uses
proactive routing to send messages to destinations within the
same cloud, and to predict forwarding nodes for destinations
in other clouds.
Our main contribution in this work is demonstrating the
feasibility of an adaptive routing approach in dynamic ad hoc
networks. To this end, we:
• present a routing protocol, AROD, which is the first
routing scheme that is adaptive to network density as well
as to mobility patterns,
• show that AROD behaves appropriately and maintains
desired properties in different network scenarios, and
• implement AROD and show its efficacy in different
network scenarios.
III. ADAPTIVE ROUTING IN DYNAMIC AD HOC
NETWORKS
Two nodes transfer data messages to each other when
they are within one another’s communication range. During
a transfer, the sender replicates messages while retaining a
copy. Messages may not be fragmented. We assume unlimited
storage capacity, and that a node never deletes messages until
it receives an acknowledgement or timeout.
Each message is given a Time-To-Live (TTL) which specifies
a timeout of the message after which a message is no
longer meaningful and can thusly be dropped. Two nodes
are in the same cloud if there is a contemporary multi-hop
contemporary path.
Similar to [14], we give each message a logical floatingpoint
ticket which is initialized 1.0. Whenever a message is
delivered, both the sender and the receivers hold a complete
copy of the message while the new tickets associated with their
copies in the sender and the receivers add up to the ticket of
the original message in the sender.