23-01-2013, 10:53 AM
Towards Reliable Mobile Ad Hoc Networks
1Towards Reliable Mobile.pdf (Size: 378.95 KB / Downloads: 57)
Introduction
It is expected that future networks will interconnect an even larger number of devices then
today, ranging from servers to micro-devices embedded in objects. These devices will
provide useful services thanks to the possibility of a networked operation, for example,
localization services to support a variety of situation-aware applications. A very significant
number of these devices will be carried by users-on-the-move. While a wireless
infrastructure could serve to provide a near permanent network access to these devices,
structural network dynamics and service demand patterns could impact the main features
of the solutions relying on this network.
Mobile ad hoc networks (MANETs) may serve to bridge these devices to the network in
situations where a connection to a wireless infrastructure may not be feasible or desirable
because of coverage limitations, network failures, congestion, policies, or cost. MANETs can
be quickly created for a wide variety of applications and whenever needed to operate on
virtually any environment. A main feature of a MANET is its self-organizing ability over a
network that is assumed by temporarily linking each mobile with other nodes within
wireless coverage. In this situation, nodes can serve as routers, at least temporarily, to
forward packets for other nodes. One of the main technical drawbacks of these type of
networks is that the network tends to change quite often. Nodes may arrive at or depart
from the network without notice and direct node-to-node communication may or may not
be possible at any given time due to node mobility and changes on the surrounding
environment. These characteristics determine a highly dynamic network that makes difficult
a reliable forwarding of packets on multi-hop routes over long periods of time.
Communications tend to be very unreliable and inefficient, because a route break not only
disrupts immediately a communication, but also can introduce additional overhead into the
network because of the potential need for retransmissions and re-routing operations.
Related work
MANETs are subject of intensive research and many works have been devoted to research
their properties and operation (1). Some of the principal works that have explicitly
addressed MANET reliability, or are in close relation to this discussion, are mentioned
below. The list is not intended to be exhaustive, but representative of the related work
previously done.
A possibility that have been explored by various authors is on the selection of the longestlived
links to create stable paths. These works are based on the observation that most
randomly moving nodes are likely to drift apart from one another over time (2), so that their
main assumption is that a link between two nodes that had survived for a significant long
time would be unlikely to change any time soon and so, the link could be classified as stable.
In fact, even in static networks wireless links may fail (3; 4; 5). In the Associativity Based
Routing (ABR) (6), a link lifetime is measured by counting the number of beacons received
from neighboring nodes and the links associated with the highest beacon counts are
preferred. In the Signal Stability Adaptive Routing (SSA) (7), routes are created by giving
preference to the selection of strong connected nodes. Nodes are classified as strongly or
weakly connected on the basis of their signal strength as measured from beacons, which are
exchanged periodically between neighboring nodes. McDonald and Zanti (8) investigated a
clustering approach for MANETs and the probability of two nodes remaining within a
distance threshold of one another over time.
Model
We assume a mobile ad hoc network (MANET) where wireless nodes communicate using a
common broadcast channel by omni-directional antennas. A MANET can be represented by
an undirected graph G = (V, E), where V expresses the set of vertices (nodes) and E ⊆ V ×V
the set of edges (wireless links).
In this model, we assume that nodes have the same transmission range and so, the graph is
undirected: (u, v) ∈ E ⇒ (v, u) ∈ E, i.e., nodes are neighbors and it is possible a
communication in either way although not at the same time. In more detail, the radio signal
encoding a packet sent from a node u with a power level Pt may be received and decoded
(with a certain probability)
Localization
The basic assumption is that nodes can learn their own location in a three-dimensional space
precisely through an external mechanism. Various alternatives exist to let mobile nodes
acquire their location. The Global Positioning System (GPS) is a navigation satellite system
that provides physical location information free-of-charge to any GPS receiver, but requires
line of sight to at least four of the 24–32 GPS satellites. The information accuracy depends on
various factors and could range from 5 m to 100 m in civilian receivers. Another possibility
is through trilateration, which allows a node to determine its location from measurements of
the transmission time from at least three known references. In contrast, an external system
could be deployed to implement hyperbolic positioning (multilateration), which can
determine the location of a node by using three or more receivers and computing the time
difference of arrival of signals emitted by the node of interest. Multilateration is used by
GSM systems and so it is of particular interest for implementing ad hoc network of smart
mobile phones. Another alternative is to use a system with antenna diversity, where nodes’
location can be determined by triangulation. These localization techniques could be
implemented by the mobiles themselves of by an external system, such as the sensor
network that we consider in this study.
Regardless of the method used, the localization system that is used would provide periodic
updates to each mobile informing them of their relative or absolute coordinates. The mobiles
will then estimate their location whenever needed from the data available, for example,
from their calculated velocity vector and the previous location update. Note that the length
of time between location updates can determine the accuracy of the location estimations.
The impact of using imprecise information to MANET routing will be addressed in the
simulation study discussed in a later section.
Evaluation under ideal conditions
To support the idea, we conducted a simulation study to find out the average route lifetime
on a mobile ad hoc network to determine whether there would be any reliability
improvement over flooding (calculated as the shortest path) with the use of either the oldest
links or the links with the longest residual lifetime metrics. The simulation was done at the
topology level and assuming ideal conditions, which imply that links are determined solely
based on the distance between nodes and that route calculation can be done with full
knowledge of the location of nodes and their mobility patterns. Although these assumptions
do not hold in practice, the results would suggest the best metric from a route reliability
standpoint. We defer to a later section the use of more realistic assumptions.
Nodes move according to the random waypoint point (RWP) model without pause times
and at a given speed that is randomly selected in the range [1, S]. Nodes move on a
rectangular field of 400 × 100 units, all with equal wireless coverage of 50 units. For each
simulation instance and after a suitable time (2.5 simulated hours) to let the statistical
properties of the RWP model emerge, a route is established between two randomly selected
nodes. Routes are established with either a hop count, link age, or link residual lifetime
criterium. The results are depicted in Figure 1 for all three cases as a function of the
maximum moving speed of the nodes. The plots also indicate the 95% confidence interval
resulting from the Monte Carlo simulations.
Route setup
As mentioned above, LDR relies on a modified flooding algorithm to discover routes. The
standard flooding algorithm is of common use by many on demand ad hoc routing
protocols and works as follows. Whenever a new route to a destination is needed, the source
broadcasts a route request message. The message indicates the desired destination and a
message identifier, in addition to other pieces of information that could be relevant to each
particular algorithm. The identifier and origin addresses of the message allows intermediate
nodes to discern new from replicated requests, so that they can select to process only the
first arrival of each request. If the node receiving the request if not the destination, the node
will append its own address to the packet (and possibly other pieces of information
depending on the actual protocol being used) and broadcast again the message without
delay.