[ Introduction | Analysis of DAG | Research Plan | Reference | Survey on Routing Protocols ]
A Mobile Ad Hoc Network, also called a MANET, is an autonomous collection of mobile nodes forming a dynamic wireless network. The administration of such a network is decentralized, i.e.each node acts both as host and router and forwards packets for nodes that are not within transmission range of each other. A MANET provides a practical way to rapidly build a decentralized communication network in areas where there is no existing infrastructure or where temporary connectivity is needed, e.g. emergency situations, disaster relief scenarios, and military applications.
The challenge to realize a mesh-like ad-hoc radio network to support
multi-hop end-to-end flows motivates new innovations both in MAC and
Routing. A preferable cross-layer approach is to integrate all medium
access, link quality and topology information to provide better
support for both best-effort traffic and real-time flows. As a wireless
node usually broadcasts information to the neighborhood instead of
using a point-to-point link. Thus, the MAC layer actually could hear
more information about the network connectivity, link quality status
and even sniff other transmissions. With the storage and analyze those
information, the MAC could provide assistance to the routing choice in
higher layer.
For optimizing the network performance, I contrived a new multi-path
packet forwarding approach for multi-hop flows in wireless ad-hoc
network based on a neighborhood cooperation scheme. This novel method
will benefit the performance of on-demand routing protocols. Basically,
the node will try a cached route whenever a packet transmission failure
happens in MAC instead of waiting for a complete link failure. This
could reduce the packet delivery failure rate. Also, the switching from
one path to another would be smooth and does not request a new
route-find process. The healthy of cached route is also improved by
these frequent usage.
The on-demand routing algorithm always perform a "route-discovery" process, and to prevent the broadcasting overhead and prevent loops, intermediate nodes will only broadcast the message once. The other reason is that, otherwise, the algorithm would not converge. So, if each node adds there own id to the "route-discovery" message. What kind of information the sink knows?
A figure example after route discovery.
(a) is the DAG rootted at the source
formed after a "route-request" broadcast process. The sink will
receive multiple route-request messages, but it does not know all the
directed links. Actually, in the figure (b) above, sink received three
Route Request messags and have a knowledge of network topology like
(b). Similarly, (c) is for the intermediate nodes in the shortest
path. The sink only know a graph with is made up of multiple
"(non-crossing)" directed paths that end in the sink, but begins
either at the source or intermediate nodes in the shortest path from
source to sink. We are only sure that the sink knows one or more
(equal-hop) shortest path. But it can not guarantee that all the
disjoint path to the source or intermediate nodes can be found by the
sink.
So, algorithms are proposed in Das's paper
actually does not guarantee to find those desirable disjoint paths even
though those paths do exist! The other shortcoming of this DAG
operation is that the sink fails to know the local multi-path around
the intermediate nodes in the shortest path. Some local multipath is
known by the intermediate nodes (see (c)). So, after the first
"route-reply", the intermediate nodes will build a network topology
like in (d), and the sink only knows the shortest (primary) path.
However, after three route-reply messages, the intermediate nodes will
have the network topology information like in (e) (the directional
arrows might be ignored for this connectivity indications). And the
source has same knowledge as the sink (see (b)).
In CHAMP, another algorithm to found
several equal-hop multi-paths to the sink is proposed. The innovation
is that as each node has a DAG rooted from source itself, it can
select same-hop-counts shortest paths as a set, and the route-reply
messages, instead of sending back to the upstream node in the path
specified in the DSR header, it sends to all the nodes in that set.
This could help upstream nodes discover more equal-hop paths to the
destination. However, this definitely increase overhead. And finally,
the source perhaps knows more information than the sink about multiple
paths to the same destination.
|
Active
protection with end-to-end disjoint path
|
Active
protection with locally disjoint path
|
Dynamic
protection with end-to-end disjoint path
|
Dynamic
protection with locally disjoint path
|
Standby
protection with end-to-end disjoint path
|
Standby
protection with locally disjoint path
|
|
|
Efficiency of
network utilization
|
low
|
Low
|
High (no/small
overhead)
|
High (no/small
overhead)
|
moderate
|
moderate
|
|
Recovery delay
|
No delay
|
No delay (may
have resource contention for shared medium)
|
nDetect
failure
nSend
error back to source
nSet up
new path
|
nDetect
failure
nSet up
new path
|
nDetect
failure
nSend
error back to source
|
nDetect
failure
¡¡
|
|
Applications
|
Real-time
video/sound
|
Real-time
video/sound
|
Data
|
Data
|
Data,
video/sound
|
Data,
video/sound
|
¡¡
Alvin Valera,Winston
Seah, S.V. Rao
Cooperative Packet Caching and Shortest
Multipath Routing in Mobile Ad hoc Networks
Infocom.03 [ My Comments ]
P. Papadimitratos, Z. J.
Haas, and E. G. Sirer,
¡°Path set selection in mobile ad hoc networks,¡±
in Proc. ACM MobiHOC 2002, Lausanne, Switzerland, June 9¨C11, 2002, pp.
160¨C170. [ My Comments ]
Performance analysis of reactive shortest path and multi-path routing
mechanism with load balance
Pham, P.P.; Perreau, S.
Infocom 03, page(s):251-259 [ My
Comments ]
Implicit source routes for on-demand ad hoc network routing
Yih-Chun Hu and David B. Johnson
Mobihoc'01
¡¡