computing. 4. Computer algorithms. I. Boukerche, Azzedine.
This book is dedicated to my parents and my family who have always been there with me.
communicating through wireless channels, without any ﬁxed backbone support.
with mobile communication and computation capabilities.
under different network densities, loss rates, and routing and mobility characteristics.
efﬁcient data distribution in multihop ad hoc networks.
in intermittently connected mobile ad hoc networks and delay-tolerant networks.
as a cost-effective way of deploying outdoor coverage in metro-area Wi-Fi hot zones.
and cons for each of the proposed approaches.
design and analysis accessible to all levels of readers.
their patience in ﬁnalizing this book.
security systems on mobile phone operations.
IEEE WMAN 04-05, and ACM MSWiM 98-99.
and Real-Time Applications Symposium (DS-RT).
was basically a visual communication system, other people could see the same message (broadcast) and the people responsible for relaying messages could be mobile.
Copyright © 2009 by John Wiley & Sons Inc.
military personnel relaying tactical and other types of information in a battleﬁeld.
is ﬁnding and maintaining routes since host mobility can cause topology changes.
they differ in the way new routes are found and existing ones are modiﬁed.
personal area network to wide area network), and wireless sensor network (WSN).
various challenges in the design of algorithms for them as discussed in the following.
must be posed from the user and application.
transmission range of a transmitting device can receive a message.
extemporaneous service customized to applications for a limited period of time.
terms of computational, communication, and storage resources.
routing paths. Figure 1.1 depicts a snapshot of a MANET topology.
complex than their wired counterpart.
in its interfering range, which can cause collisions at the other nodes.
topology knowledge range, so it leads to a faster convergence of its neighboring nodes.
parameters such as the amount of energy available at each node.
nodes’ geographical location to choose the one that is closest to the destination node D.
Figure 1.2. Strategies used by some forwarding algorithms.
name suggests, chooses a random node that is in direct communication range from S.
algorithms can be either centralized, distributed, or localized.
components of G. It means that if G is a connected graph, so is the resulting subgraph.
signal among them to select the cluster head .
based on a spanning tree algorithm .
the maximum power used is minimized while keeping the network biconnected.
of control messages during route establishment.
proposed in the literature .
a mobile environment—in particular, bandwidth and energy limitations and mobility.
such as hidden stations and exposed stations.
Reverse Path Forwarding (TBRPF) Protocols .
number. This ensures utilization of the route with the most recent information.
set of its neighbors such that the set covers those nodes that are distant two hops away.
its MPR set are responsible for broadcasting the message.
source trees maintained at neighboring nodes, it can update its own shortest path tree.
fewer control packets are transmitted.
given destination only when a node requests it by initiating a route discovery process.
Routing (DSR)  and Ad Hoc On-Demand Distance Vector (AODV) .
routes to a destination in the cache, which is helpful in case of a link failure.
known route to the destination. Otherwise, it retransmits the RREQ message.
many available routes might never be needed, which increases the routing overhead.
Proactive protocols tend to provide better quality of service than reactive protocols.
route update patterns, and capabilities.
there are protocols that use the node’s geographical location to route messages.
Source Routing (DSR)  and Ad Hoc On-Demand Distance Vector (AODV) .
split. Finally, broadcast is the delivery of a message to all nodes in the network.
same message or stream of data to a group of nodes that share a common interest.
in a mobile ad hoc network distinguishes the different multicasting routing protocols.
the sense that no protocol state is maintained at any node except for the source node.
in the ODMRP the senders initiates it.
quite low and the TCP’s congestion avoidance mechanism works very well.
TCP’s dynamic congestion window mechanism. In summary, standard TCP ﬂow control and congestion control mechanisms do not work well in mobile ad hoc networks.
The error control mechanisms of MAC protocols can affect the TCP performance.
a prediction was not successfully predicted.
A third strategy is to design a new transport protocol for the mobile ad hoc network.
feedback to the ATP sender for reliability, rate, and ﬂow control.
important system design criteria for optimization may be energy conservation .
among participating nodes to deliver messages.
the network increase the vulnerabilities of a mobile ad hoc network.
inefﬁcient; and stolen device attacks.
authority function to manage the private–public keys and to distribute keys via certiﬁcates, which needs to be distributed over multiple nodes in the MANET .
that each node must receive a certiﬁcate and a secret share in a distributed manner.
certiﬁcates, and it is possible to create new secret shares in a distributed manner .
mobile ad hoc environment makes the detection of these problems more difﬁcult .
Routing) technique  to add security attributes to the route discovery .
deploying commercial ad hoc applications to ordinary people.
a connection “opportunity” arises, such as an appropriate network contact happens.
the case of a wired networking.
used, for instance, in a taxi dispatch system based on MANET.
and frequent network partitioning .
equipment. The main goal of a VANET is to provide safety and comfort for passengers.
danger warning, intersection collision avoidance, and work zone safety warning. Comfort applications aim to improve the driving comfort and the efﬁciency of the transportation system and, hence, are more bandwidth-sensitive instead of delay-sensitive.
download (electronic map download/update), and driving through payment .
wireless networking and tends to become increasingly present in our daily life .
broadband wireless solutions, and is simple to understand.
radio terminals. IEEE Transactions on Communications, 32(3):246–257, 1984.
4. T. C. Hou and V. O. K. Li. Transmission range control in multihop packet radio terminals.
IEEE Transactions on Communications, 34(1):38–44, 1986.
5. G. G. Finn. Routing and addressing problems in large metropolitan scale internetworks.
Technical Report RR–87–180, ISI Research Report, 1987.
network with capture. IEEE Transactions on Communications, 32(6):684–694, 1984.
and Computing (MobiHoc ’03), Annapolis, MD, ACM, New York 2003, pp. 40–48.
Networked Sensing Technical Report 6, UCLA, 2003.
9. S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998.
dominating sets. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODS ’01), Newport, RI, 2001.
Mobile Computing (WNMC ’01), Scottsdale, AZ, 2001, pp. 72–80.
’01), Rome, Italy, 2001, pp. 62–70.
wireless networks. IEEE Personal Communications, April 1999, pp. 40–45.
17. J. M. McQuillan, I. Richer, and E. C. Rosen. The new routing algorithm for the ARPANet.
IEEE Transactions on Communications, 28(5):711–719, 1980.
18. C. Hedrick. Routing Information Protocol. Request for Comments 1058, June 1988. Available at http://www.ietf.org/rfc/rfc1058.txt.
Comments 3626, October 2003. Available at http://www.ietf.org/rfc/rfc3626.txt.
hoc networks. Ad Hoc Networks, 2(1):1–22, 2004. Mobile Ad-hoc Networks (MANET).
Internet drafts available at http://www.ietf. org/ids.by.wg/manet.html.
Protocol. Mobile Networks and Applications, 7(6):429–439, 2002.
on Mobile Computing and Networking (MobiCom’99), Seattle, WA, August 1999, pp.
CA, June 2002, pp. 270–271.
mesh protocol. Mobile Networks and Applications, 6(2):151–165, 2001.
Orleans, LA, September 1999, pp. 1298–1302.
Communications Surveys & Tutorials, 7(3):22–36, 2005.
Conference (WCNC ’99), pages 1323–1327, New Orleans, LA, September 1999.
networks. Wireless Communications, 9(4):8–27, 2002.
37. J. R. Lorch and A. J. Smith. Software strategies for portable computer energy management.
IEEE Personal Comunications, 5(3):60–73, 1998.
wireless networks: A survey. Ad Hoc Networks, 4(3):326–358, 2006.
(WCNC ’07), Hong Kong, China, March 2007, pp. 4313–4317.
42. R. Kravets and P. Krishnan. Application-driven power management for mobile communication. Wireless Networks, 6(4):263–277, 2000.
44. M. Rulnick and N. Bambos. Mobile power management for wireless communication networks. Wireless Networks, 3(1):3–14, 1997.
for dense multi-hop wireless networks. Wireless Networks, 6:50–58, 2007.
48. P. Papadimitratos and Z. J. Haas. Secure data communication in mobile ad hoc networks.
IEEE Journal on Selected Areas in Communications, 24(2):343–356, 2006.
and solutions. Wireless Communications, 11(1):38–47, 2004.
50. L. Zhou and Z. J. Haas. Securing ad hoc networks. IEEE Network, 13(6):24–30, 1999.
Protocols (ICNP ’01), Riverside, CA, November 2001, pp. 251–260.
Protocols (ICNP ’03), Atlanta, GA, November 2003, pp. 336–345.
Canada, November 1987, pp. 427–437.
(ICNP’03), Boston, MA, November 2003, pp. 269–278.
ad hoc networks. Computer, 37(2):61–65, 2004.
58. K. Sanzgiri, D. LaFlamme, B. Dahill, B. N. Levine, C. Shields, and E. M. Belding-Royer.
Authenticated routing for ad hoc networks. IEEE Journal on Selected Areas in Communications, 23(3):598–610, 2005.
2001, Reading, MA, pp. 221–253.
Computing (MobiHoc ’01), Long Beach, CA, October 2001, pp. 299–302.
’07), Toronto, Canada, June 2007, p. 7.
IL, May 2005, pp. 355–365.
Hoc Networking and Computing (MobiHoc ’05), Urbana-Champaign, IL, May 2005, pp.
(MILCOM ’06), Washington, D.C., October 2006, p. 7.
67. M. Caliskan, D. Graupner, and M. Mauve. Decentralized disovery of free parking places.
(VANET ’06), Los Angeles, CA, October 2006, pp. 30–36.
DSRC, March 2005. Available at http://ntlsearch.bts.gov/tris/record/tris/01002103.html.
69. I. Chlamtac, M. Conti, and J. J.-N. Liu. Mobile ad hoc networking: Imperatives and Challenges. Ad Hoc Networks, 1(1):13–64, 2003.
dynamic faults, and devices with limited resources.
and require the minimum possible knowledge of the immediate surroundings.
and Mathematics of Information Technology and Complex Systems (MITACS).
hoc network communication and discusses applications.
masters, beacons, or even base stations (see Figure 2.2).
and provide more control over access to transmission.
Figure 2.1. Flat routing infrastructure.
and abbreviated CH) and the master hosts can communicate directly with themselves.
and become members of that cluster.
aspects of mobile ad hoc networking. A clustering algorithm is basically a multileader election problem, and a cluster is similar to a group in distributed systems.
Figure 2.3. Partitioning of nodes in hierarchical routing.
virtual distance from a beacon.
consists of a set of, say, r nodes B1 , B2 , . . . , Br , which are speciﬁed to be the beacons.
their virtual coordinates using broadcast messages.
failing the attempt using ﬂooding.
from any source (this is also known as the routing problem).
between source and destination is a shortest path.
two anchors, in suitably chosen positions, can solve the naming problem on a grid.
problem in unit disk graphs.
their construction for each of the three cases.
an analogy borrowed from the theory of graph embeddings (see Linial et al. ).