<<

. 7
( 87 .)



>>

Besides collision avoidance, other optimization studies have been done in the MAC
layer to improve MANET performance, including MAC improvement and algorithms
used to reduce mobile node energy consumption [26, 38] as well as MAC optimizations
for improving TCP layer performance.

1.4.2. Ad Hoc Routing
The highly dynamic nature of mobile ad hoc networks results in frequent changes and un-
predictability in network topologies, adding difficulty and complexity to routing among
the mobile nodes within the network. These added challenges, coupled with the critical
importance of routing protocols in establishing communications among mobile nodes,
make the routing area perhaps the most active research area within the MANET domain.
Especially over the last few years, numerous routing protocols and algorithms have been
proposed and their performance under various network environments and traffic condi-
tions closely studied and compared. The ultimate goal of the MANET community is to
provide a set of standardized protocols that can be both robust and scalable to tens of
thousands of network nodes to enable fast commercialization of mobile ad hoc networks
in increasing network applications suites.
The primary objective of an ad-hoc network routing protocol is the correct and effi-
cient route establishment between a pair of nodes so that messages may be delivered reli-
ably and in a timely manner. Route construction should be done with minimum overhead
and bandwidth consumption [57]. Existing distance-vector and link-state-based routing
protocols are designed for static environment, and are, therefore, unable to catch up with
frequent topology changes of ad hoc environments, resulting in degradation in perfor-
mance, including slow route convergence, low communication throughput [23], possible
route loops during node failure, and network partition or congestion. In addition, proto-
cols that use flooding techniques, such as link-state algorithms, tend to create excessive
traffic and control overhead during route establishment. New routing protocols need to be
designed to suit the specific needs of mobile ad hoc network environments and character-
istics, particularly mobility and bandwidth/energy limitations.
Important criteria and considerations used in designing and comparing the new routing
protocols include:

Simplicity and ease of implementation
Rapid route convergence”routes should be loop-free and optimal, and, possibly,
multiple routes should be available between each pair of nodes to increase robust-
ness
Distributed but lightweight in nature”can quickly adapt to changes in topology and
traffic pattern resulting from mobility and failure conditions; protocol reaction
should result in minimal control overhead
Bandwidth, power, and computing efficient with minimum overhead
Scalable
Secure and reliable
Supporting Quality of Service requirements

In general, ad hoc network routing protocols may be divided into two broad categories:
proactive routing protocols and reactive on-demand routing protocols [57]. Proactive
22 MOBILE AD HOC NETWORKING WITH A VIEW OF 4G WIRELESS: IMPERATIVES AND CHALLENGES


routing protocols attempt to maintain consistent, up-to-date routing information between
every pair of nodes in the network by propagating, proactively, route updates at fixed time
intervals. As the resulting routing information is usually maintained in tables, the proto-
cols are sometimes refered to as table-driven protocols. Reactive on-demand routing pro-
tocols, on the other hand, establish a route to a destination only when there is a demand
for it, usually initiated by the source node through route discovery process within the net-
work. Once a route has been established, it is maintained by the node until either the desti-
nation becomes inaccessible along every path from the source or until the route is no
longer used or has expired [57].
Representative proactive protocols include Destination-Sequenced Distance-Vector
(DSDV) protocol, Clusterhead Gateway Switch Routing (CGSR) protocol, Wireless Rout-
ing Protocol (WRP), Global State Routing (GSR) [79], Optimized Link State Routing
Protocol (OLSR), Fisheye State Routing (FSR) [75] Protocol, Landmark Routing (LAN-
MAR) Protocol, and Hierarchical State Routing (HSR).
The Destination-Sequenced Distance-Vector (DSDV) protocol (PB94) is a distance
vector protocol with extensions to make it suitable for MANET. Every node maintains a
routing table with one route entry for each destination in which the shortest path route
(based on number of hops) is recorded. To avoid routing loops, a destination sequence
number is used. A node increments its sequence number whenever a change occurs in its
neighborhood. This number is used to select among alternative routes for the same desti-
nation. Nodes always select the route with the greatest sequence number.
CGSR extends DSDV with a cluster framework concept that increases protocol scala-
bility [63]; also, heuristic methods like priority token scheduling, gateway code schedul-
ing, and path reservation [63] are used to improve the protocol™s performance. On the oth-
er hand, setting up structure in a highly dynamic environment can adversely affect
protocol performance since the structure might not persist for a very long time.
WRP is another loop-free proactive protocol whereby four tables are used to maintain
distance, link cost, routes, and message retransmission information [64]. General route
updates are sent among neighboring nodes with distance and second-to-last hop informa-
tion for each destination, resulting in faster convergence.
Despite the variance in number of routing tables used and the difference in routing in-
formation maintained in these tables, proactive routing protocols like DSDV CGSR, and
,
WRP are all distance vector shortest-path-based and have the same degree of complexity
during link failures and additions.
The OLSR protocol [74] is an optimization from the pure Link State protocol. In
OLSR, instead of flooding a node™s complete link state information to all nodes in the net-
work, only link information from a subset of links to the neighboring Multipoint Relay
Selectors (MRS) are flooded to other MRSs, which then relay the control information to
their neighbor nodes. Upon receiving the updates, each node calculates the routes to all
known nodes, which are a sequence of hops through multipoint relay nodes to each desti-
nation node. All nodes select their set of multipoint relays such that the set covers all the
nodes that are two hops away. The FSR protocol [75, 76] is also an optimization over Link
State algorithm using the fisheye technique. In essence, FSR will propagate link state in-
formation to other nodes in the network based on how far away (defined by scopes, which
are determined by number of hops) the nodes are. The protocol will propagate link state
information more frequently with nodes that are in a closer scope as opposed to ones that
are further away. This means that a route will be less accurate the further away the node is,
but once the message gets closer to the destination, the accuracy increases. LANMAR
23
1.4. TECHNICAL CHALLENGES AND RESEARCH OVERVIEW


[77, 78] builds on top of FSR and achieves hierarchical routing by partitioning the net-
work nodes into different mobility groups. A landmark node is elected within each group
to keep track of which logical subnet a node belongs to and facilitate intergroup routing,
whereas FSR is used for intragroup routing. OLSR and FSR are similar in that they are
both Link-State-algorithm-based, and both optimizations provide the same benefit of re-
ducing routing overhead and, consequently, improve bandwidth efficiency.
Representative reactive routing protocols include Dynamic Source Routing (DSR),
Ad-hoc on-Demand Distance Vector (AODV), Temporally Ordered Routing Algorithm
(TORA), Associativity-Based Routing (ABR), and Signal Stability Routing (SSR). DSR
is a loop-free source based on the demand routing protocol [65], in which each node
maintains route caches that contain the source routes learned by the node, and the route
discovery process is only initiated when a source node does not already have a valid
route to the destination in its route cache. Entries in the route cache are continually up-
dated as new routes are learned. AODV is an improvement on the DSDV protocol.
AODV minimizes the number of route broadcasts by creating routes on an on-demand
basis [61], as opposed to maintaining a complete list of routes as in the DSDV algo-
rithm. Just like DSR, route discovery is initiated on an on-demand basis, the route re-
quest is then forward to the neighbors, and so on, until either the destination or an in-
termediate node with a fresh route to the destination are located. DSR has potentially
larger control overhead and memory requirements than AODV since each DSR packet
must carry full routing path information, whereas in AODV packets only contain the
destination address. On the other hand, DSR can utilize both asymmetric and symmetric
links during routing, whereas AODV only works with symmetric links, a condition that
is more difficult to satisfy in mobile wireless environments. In addition, nodes in DSR
maintain multiple routes to a destination in the cache, which is helpful during link fail-
ure. In general, both AODV and DSR work well in small-to-medium-sized networks
with moderate mobility.
TORA is another source-initiated on-demand routing protocol, built on the concept of
link reversal [58] of Directed Acyclic Graph (ACG). In addition to being loop-free and
bandwidth-efficient, TORA has the property of being highly adaptive and quick in route
repair during link failure, while providing multiple routes for any desired source/destina-
tion pair. These features make it especially suitable for large highly dynamic mobile ad
hoc environments with dense populations of nodes. The limitation in TORA™s applicability
comes from its reliance on synchronized clocks. If a node does not have a GPS position-
ing system or some other external time source, or if the time source fails, the algorithm
cannot be used.
The ABR protocol is also a loop-free protocol using a new routing metric termed “de-
gree of association stability” in selecting routes [66] so that routes discovered can be
longer-lived routes and thus be more stable and require less updating in the future. The
limitation of ABR mainly comes from the periodic beaconing requirement used to estab-
lish the association stability metrics, which may result in additional energy consumption.
The Signal Stability Algorithm (SSA) [84] is basically an ABR with the additional proper-
ty of selecting routes based on signal strength of the link.
In general, on-demand reactive protocols are more efficient than proactive routing pro-
tocols in terms of control overhead and power consumption since routes are only estab-
lished when required. By contrast, proactive protocols require periodic route updates to
keep information current and consistent. In addition, many routes maintained might never
be needed, which significantly adds to routing overhead in the bandwidth-constrained net-
24 MOBILE AD HOC NETWORKING WITH A VIEW OF 4G WIRELESS: IMPERATIVES AND CHALLENGES


work. As routing overhead grows exponentially with network size, it prevents the applica-
tion of these protocols in large-scaled networks.
Proactive routing protocols generally provide better quality of service than on-demand
protocols. As in proactive protocols, routing information is constantly updated, routes to
every destination are always available and up-to-date, and, hence, end-to-end delay can be
minimized. For on-demand protocols, the source node has to wait for the route to be dis-
covered before communication can happen. This latency in route discovery might be in-
tolerable for real-time communications. In [57], the authors present a set of tables that
summarize the main differences between these protocols in terms of their complexity,
route update patterns, and capabilities.
The above categorization is very broad, and other taxonomies exist to categorize routing
protocols in ad hoc domains based on different selection criteria, including those based on
structure, type of cast, cost functions (metrics) [86], and so on. For example, some proto-
cols rely on setting up an internal structure, hierarchy, or partitions to help improve routing
efficiency and achieve scalability. CGSR and HSR use a cluster/cluster-head-based hierar-
chical architecture, OLSR protocol relies on the selection of multipoint relays, FSR parti-
tions nodes based on scope, the LANMAR method depends on landmark node and hierar-
chical partitions of the network nodes, CEDAR relies on core nodes to negotiate routes and
maintain and disseminate QoS information, and the Zone-Based Hierarchical Link State
Routing Protocol (ZRP) [80] divides the network into nonoverlapping zones based on
nodes™ geolocation, with neighboring zone connectivity information propagated by dedi-
cated gateway nodes. In general, structure-based protocols are more bandwidth-efficient
and scalable, but the cost to maintain the structure can be prohibitive, especially in mobile
ad hoc environments where constant topology changes might result in unstable structures.
Yet another category of routing protocols base their routing decisions on the nodes™ ge-
ographical position, such as the one provided by GPS [55] or other mechanisms [184,
185]. These are typically referred as location-aware routing or position-based routing al-
gorithms. Location-aware routing does not require the routes™ establishment and mainte-
nance. No routing information is stored. Typically, a node selects the next hop for packets™
forwarding by using the physical position of its one-hop neighbors and the physical posi-
tion of the destination node; positioning information of the networks™ nodes are usually
obtained via queries offered through some location service. The packets are then forward-
ed to a neighbor in the receiver™s direction. The use of geolocation information avoids net-
work-wide searches, as both control and data packets are sent toward the known geo-
graphical coordinates of the destination node. These features make location-aware routing
protocols quickly adaptive to route changes, and more scalable than unicast protocols
such as AODV DSDV or DSR. DREAM, the first location-based routing protocol, uti-
, ,
lized the idea of the “distance factor,” allowing optimized performance to be obtained
based on the observation that the further the nodes are from each other, the slower they
appear to be moving [87]. Hence, less routing information has to be transferred between
remote nodes. As demonstrated in [87], location-based protocols can yield an order of
magnitude improvement in performance and bandwidth/energy usage by utilizing loca-
tion information in routing.
A large number of location-aware algorithms have been proposed in the literature since
then. As represented by [186“189], these protocols typically fall into three main strate-
gies: greedy forwarding, directed flooding, and hierarchical routing. Greedy forwarding
and directed flooding algorithms forward the packet to one or more neighbors, respective-
ly. Hierarchical routing algorithms are a combination of position-based, and non-position-
25
1.4. TECHNICAL CHALLENGES AND RESEARCH OVERVIEW


based routing algorithms. Proposed greedy forwarding algorithms include The Most For-
ward within Radius policy (MFR) [190], the Nearest with Forward Progress scheme
(NFP) [191] and the compass routing scheme [192]; representative directed flooding al-
gorithms include DREAM [87] and LAR [193]; and representative hierarchical routing
algorithms include the Grid Routing [194] and the Terminode Routing protocols [195].
In [86], the authors present a detailed discussion of applications of different routing
protocols in various types of networks. In general, they show that the proactive protocols
are sufficient for a small-scale static network, whereas reactive protocols such as DSR
and AODV normally work well for medium-size networks with moderate mobility. For
large-scale networks with hundreds or thousands of nodes, in which layering and parti-
tioning are essential in ensuring network performance, structure-based or hybrid protocols
are more appropriate. Overall, a good approach in routing protocol design might come
from hybrid routing protocols; for example, by using proactive protocols in local zones,
while using reactive protocols between zones (ZRP), by using location-aware routing for
nodes over long distances when the forwarding node and the receiver are far away, or by
incorporating a hierarchical clustering algorithm to AODV to increase scalability. Loca-
tion-based algorithms may also become key contenders for solving efficient routing in
MANET networks as location based services become generally available.

1.4.3. Multicasting and Broadcasting
As mentioned in Section 1.4.2, routing protocols can also be classified by the type of cast
property, that is, whether they use Unicast, Geocast, Multicast, or Broadcast [86]. The
first works on broadcasting in multihop and mobile multihop wireless ad hoc networks fo-
cused on slotted channels [90, 92]. Broadcast is a basic mode of operation in the wireless
medium whereby messages are sent to all source nodes™ neighbors. In a unicast operation,
a single source transmits messages or data packets to one destination. Unicast protocols
serve as the basis for other types of protocols. Multicast routing protocols come into play
when a node needs to send the same message or stream of data to multiple destinations,
whereas Geocast protocols are used to deliver data packets to groups of nodes situated in
a specified geographical area. Geocast is a special type of Multicast. In a multicast situa-
tion, nodes may join or leave a multicast group as desired, and in Geocast, nodes can only
join or leave the group by entering or leaving the defined geographical region [88]. To op-
erate properly, Geocast typically requires additional node location information from posi-
tioning systems, such as GPS.
Multicasting is an efficient communication service for supporting multipoint applica-
tions (e.g., software distributions, audio/video conferencing) in the Internet. In MANET,
the role of multicast services is potentially even more important due the bandwidth and
energy savings that can be achieved through multicast packets™ delivery [CW87]. Conven-
tional static multicast routing protocols work well under static configurations. Supporting
multicast routes under highly dynamic network situation is a major challenge for mobile
ad hoc multicasting routing protocols [92].
In general, two mechanisms are used to establish routing information among multicast
members within a group: routing tree or mesh. Establishing a routing tree among a group
of routers works well in static networks. Multicast meshes are more suitable for dynamic
environments as they support higher connectivity than trees. Multicast meshes are estab-
lished first by flooding control packets within the network. Although multicast meshes
perform better than multicast trees in dynamic networks, the mesh mechanism is more in-
26 MOBILE AD HOC NETWORKING WITH A VIEW OF 4G WIRELESS: IMPERATIVES AND CHALLENGES


clined to form routing loops. In addition, approaches to mesh building based on flooding
incur excessive overhead in large networks [88].
Representative route-tree-based multicast protocols include the Distance Vector Multi-
cast Routing Protocol (DVMRP), AMROUTE, and AODV DVMRP proactively builds a
,
source-based tree by first flooding the whole network with the multicast traffic and then
conducting pruning operations. AODV uses a multicast group leader to establish a core-
based tree structure based on demand.
Representative mesh-based multicast routing protocols include the Core-Assisted
Mesh Protocol (CAMP), the Forwarding Group Multicast Protocol (FGMP), and the
On-Demand Multicast Routing Protocol (ODMRP). These protocols build routing meshes
rather than routing trees to disseminate multicast packets within groups. Both FGMP and
ODMRP use flooding to build the mesh, whereas CAMP uses one or more core nodes to
assist in building the mesh instead of using flooding. In FGMP, the receivers initiate the

<<

. 7
( 87 .)



>>