. 40
( 87 .)


47. G. Calinescu, “Computing 2-Hop Neighborhoods in Ad Hoc Wireless Networks,” submitted for
48. J. Gao, L. J. Guibas, J. Hershburger, L. Zhang, and A. Zhu, “Geometric Spanner for Routing in
Mobile Networks,” in Proceedings of the 2nd ACM Symposium on Mobile Ad Hoc Networking
and Computing (MobiHoc 01), 2001.
49. X.-Y. Li and Y. Wang, “Localized Construction of Bounded Degree Planar Spanner for Wireless
Ad Hoc Networks,” submitted for publication.
50. J. Monks, V. Bharghavan, and W.-M Hwu, “Transmission Power Control for Aultiple Ac-
cess Wireless Packet Networks,” in IEEE Conference on Local Computer Networks (LCN),
51. M. Sanchez, P. Manzoni, and Z. Haas, “Determination of Critical Transmission Range in Ad-
Hoc Networks,” in Multiaccess, Mobility and Teletraffic for Wireless Communications
(MMT™99), 1999.
52. M. Faloutsos and M. Molle, “Creating Otimal Distributed Algorithms for Minimum Spanning
Trees,” Tech. Rep. Technical Report CSRI-327 (also submitted in WDAG ™95), 1995.
53. R. Gallager, P. Humblet, and P. Spira, “A Distributed Algorithm for Minimumweight Spanning
Trees,” ACM Transactions on Programming Languages and Systems, 5, 1, 66“77, 1983.
54. J. A. Garay, S. Kutten, and D. Peleg, “A Sub-Linear Time Distributed Algorithm for Minimum-
Weight Spanning Trees,” in Symposium on Theory of Computing, 1993, pp. 659“668.
55. L. Kirousis, E. Kranakis, D. Krizanc, and A. Pelc, “Power Consumption in Packet Radio Net-
works,” in Symposium on Theoretical Aspects of Computer Science (STACS) ™97, 1997.
56. A. E. F. Clementi, P. Penna, and R. Silvestri, “On the Power Assignment Problem in Radio Net-
works,” 2000.
57. A. Clementi, P. Penna, and R. Silvestri, “The Power Range Assignment Problem in Radio Net-
works on the Plane,” in XVII Symposium on Theoretical Aspects of Computer Science
(STACS™00), LNCS(1770), pp. 651“660, 2000.
58. A. Clementi, P. Penna, and R. Silvestri, “Hardness Results for the Power Range Assignment
Problem in Packet Radio Networks,” in II International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (RANDOM/APPROX™99), LNCS(1671), pp.
197“208, 1999.
59. G. Calinescu, I. Mandoiu, and A. Zelikovsky, “Symmetric Connectivity with Minimum Power
Consumption in Radio Networks,” in IFIP-TCS, 2002, To appear.
60. P. Bose, A. Brodnik, S Carlsson, E. D. Demaine, R. Fleischer, A. Lopez-Ortiz, P. Morin, and J. I.
Munro, “Online Routing in Convex Subdivisions,” in International Symposium on Algorithms
and Computation, pp. 47“59, 2002.
61. P. Bose and P. Morin, “Online Routing in Triangulations,” in Proc. of the 10th Annual Interna-
tional Symposium on Algorithms and Computation ISAAC, 1999.

62. I. Stojmenovic and X. Lin, “Loop-Free Hybrid Single-Path/Flooding Routing aAgorithms with
guaranteed delivery for Wireless Networks,” IEEE Transactions on Parallel and Distributed
Systems, 12, 10, 2001.
63. S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A. Woodward, “A Distance Routing Effect Algo-
rithm for Mobility (DREAM),” in Proceedings of ACM/IEEE MobiCom™98, 1998.
64. Z. Haas and B. Liang, “Ad-hoc Mobility Management with Uniform Quorum Systems,”
IEEE/ACM Transactions on Networking, 7, 2, pp. 228“240, 1999.
65. I. Stojmenovic, “A Routing Strategy and Quorum Based Location Update Scheme for Ad Hoc
Wireless Networks,” Tech. Rep. TR-99-09, Computer Science, SITE, University of Ottawa,
66. K. N. Amouris, S. Papavassiliou, and M. Li, “A Position Based Multi-Zone Routing Protocol
for Wide Area Mobile Ad-Hoc Networks,” in Proceedings of 49th IEEE Vehicular Technology
Conference, pp. 1365“1369, 1999.
67. E. Kranakis, H. Singh, and J. Urrutia, “Compass Routing on Geometric Networks,” in Proceed-
ings of 11 th Canadian Conference on Computational Geometry, pp. 51“54, 1999.
68. P. Morin, Online Routing in Geometric Graphs, Ph.D. thesis, Carleton University School of
Computer Science, 2001.
69. P. Bose and P. Morin, “Competitive Online Routing in Geometric Graphs,” in Proceedings of
the VIII International Colloquium on Structural Information and Communication Complexity
(SIROCCO 2001), pp. 35“44, 1999.
70. X.-Y. Li, Y. Wang and O. Frieder, “Localized Routing for Wireless Ad Hoc Networks,” 2003,
IEEE ICC 2003, to appear.
71. M. Penrose, “The Longest Edge of the Random Minimal Spanning Tree,” Annals of Applied
Probability, 7, 340“361, 1997.
72. P. Gupta and P. R. Kumar, “Critical Power for Asymptotic Connectivity in Wireless Networks,”
in Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H.
Fleming, W. M. McEneaney, G. Yin, and Q. Zhang (eds.), 1998.
73. X.-Y. Li, Y. Wang, P.-J. Wan and C.-W. Yi, “Fault Tolerant Deployment and Topology Control in
Wireless Networks,” in 2003 ACM MobiHoc, 2003.
74. M. Penrose, “On k-Connectivity for a Geometric Random Graph,” Random Structures and Al-
gorithms, 15, 145“164, 1999.
75. B. Bollobás, Random Graphs, Cambridge University Press, 2001.
76. H. Dette and N. Henze, “Some Peculiar Boundary Phenomena for Extremes of rth Nearest
Neighbor Links,” Statistics & Probability Letters, 10, 381“390, 1990.
77. M. Penrose, “Extremes for the Minimal Spanning Tree on Normally Distributed Points,” Ad-
vances in Applied Probability, 30, 628“639, 1998.
78. M. Penrose, “A Strong Law for the Longest Edge of the Minimal Spanning Tree,” Annals of
Probability, 27, 246“260, 1999.
79. C. Bettstetter, “On the Minimum Node Degree and Connectivity of a Wireless Multihop Net-
work,” in 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing
(MobiHoc™02), June 2002.
80. D. M. Blough, M. Leoncini, G. Resta, and P. Santi, “On the Symmetric Range Assignment
Problem in Wireless Ad Hoc Networks,” in Proceedings of 2nd IFIP International Conference
on Theoretical Computer Science, 2002.
81. C. Cooper and A. Frieze, “On the Connectivity of Random k-th Nearest Neighbour Graphs,”
Combinatorics, Probability and Computing, 4, 343“362, 1995.
82. M. Grossglauser and D. Tse, “Mobility Increases the Capacity of Ad-Hoc Wireless Networks,”
in INFOCOMM, 2001, vol. 3, pp. 1360“1369.

83. P. Gupta and P. Kumar, “Capacity of Wireless Networks,” Techincal Report, University of Illi-
nois, Urbana“Champaign, 1999.
84. O. D. Patrick, “Connectivity in Ad-Hoc and Hybrid Networks,” in IEEE INFOCOM, 2002.
85. P. Santi and D. M. Blough, “An Evaluation of Connectivity in Mobile Wireless Ad Hoc Net-
works,” in Proceedings of IEEE DSN, pp. 89“98, 2002.
86. F. Xue and P. R. Kumar, “The Number of Neighbors Needed for Connectivity of Wireless Net-
works,” submitted to Wireless Networks.
87. P. Hall, “Distribution of Size, Structure and Number of Vacant Regions in a High-Intensity Mo-
saic,” Z. Warsch. verw, Gebiete 70, 237“261, 1985.
88. T. Lukovszki, “New Results of Fault Tolerant Geometric Spanners,” in Workshop on Algorithms
and Data Structures, pp. 193“204, 1999.
89. F. Kuhn, R. Wattenhofer, and A. Zollinger, “Asymptotically Optimal Geometric Mobile Ad-Hoc
Routing,” in Proceedings of the 6th International Workshop on Discrete Algorithms and Meth-
ods for Mobile Computing and Communications (DIALM), 2002.




Wireless networks consist of static or mobile hosts (or nodes) that can communicate with
each other over wireless links without any static network interaction. Each mobile host
has the capability to communicate directly with other mobile hosts in its vicinity. They
can also forward packets destined for other nodes. Examples of such networks are ad hoc,
local area, packet radio, and sensor networks. They are used in disaster rescues and wire-
less conferences, on battlefields, in possibly remote or dangerous environments where
monitoring objects is required, for wireless Internet access, and so on.
In a broadcasting task, a source node sends the same message to all the nodes in the
network. In the one-to-all model, transmission by each node can reach all nodes that are
within radius distance from it, whereas in the one-to-one model, each transmission is di-
rected toward only one neighbor (using narrow-beam directional antennas or separate fre-
quencies for each node). In the literature, broadcasting has been studied mainly for the
one-to-all model, and most of this chapter is devoted to that model. The one-to-many
model can also be considered, in which fixed or variable angular-beam antennas can be
used to reach several neighbors at once.
Broadcasting is also frequently referred to in literature as flooding. Broadcasting appli-
cations include paging a particular host or sending an alarm signal. The broadcasting task
was sometimes studied in the context of address serving [1] in hierarchically clustered
packet radio networks. Flooding/broadcasting is also used for route discovery in source-
initiated, on-demand routing. Broadcasting can similarly be used in the context of an effi-
cient location-aware routing algorithm as follows. The source S may initiate a destination

Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.

search process by broadcasting a short message that contains the location of S, identity
(ID) of destination D, and some control bits. When the destination search message suc-
cessfully reaches D, D applies any location-based routing algorithm (e.g., [2] which guar-
antees delivery if the location of the destination, in this case S, is accurate) and reports
back to S with a short message containing its location. The source S can then again apply
the same routing algorithm [2] (or use the path created in the previous step by D if that
path was recorded in the process) to send the full message to D. Ho et al. [3] argued that
flooding can be a viable candidate for multicast and routing protocols in very dynamic ad
hoc networks.
Another application of broadcasting is in the sensor network. Recent advances in tech-
nology have made it possible to integrate microsensor, low-power signal processing, com-
putation, and low-cost wireless communication into a sensing device, such as one devel-
oped by the WINS project at UCLA [4]. Data broadcasting and gathering are important
functions supported in a sensor network to collect and disseminate critical information,
such as temperature, pressure, and noise level.
Geocasting is a form of broadcasting in which nodes that shall receive messages are re-
stricted to be inside a region. A simple solution to this problem is to route from the source
to a node inside the geo-casting region, and then apply broadcasting inside the region [5].
Solutions proposed in literature do not appear to be more efficient than this one, and we
will not survey them here. A survey is given in [6].
The traditional solution to the broadcasting problem is blind flooding, whereby each
node receiving the message will retransmit it to all its neighbors. The only “optimization”
applied to this solution is that nodes remember messages received for flooding, and do not
act when receiving repeated copies of the same message. However, blind flooding causes
unnecessary collisions and bandwidth waste, with many nodes not receiving the message
as a consequence.
Williams and Camp [7] classified the broadcast protocols into simple (blind) flooding,
probability-based, area-based, and neighbor-knowledge methods. In this chapter, area-
based methods are reclassified within other groups, whereas neighbor-knowledge methods
are divided into clustering-based, selecting forwarding neighbors, and internal-node-based
methods. We shall present here a comprehensive taxonomy of broadcasting schemes with
the one-to-all model in mind (the other models can similarly be considered). All schemes
can be classified following the taxonomy consisting of five categories: determinism, net-
work information, reliability, “hello” message content, and broadcast message content. The
boldfaced terms are used in the summary table given in the conclusion section.

7.1.1 Determinism
A broadcast scheme may use probabilistic or deterministic protocols, based on whether
or not a random number selection was used to make decisions. The random-number usage
here is limited to the network layer decision; the underlying medium-access control
(MAC) protocol may still use random backoff counters, for example, in a network layer
deterministic scheme.

7.1.2 Network Information
The second classification is based on the type of state information used in the algorithm:
global or local. Note that the distinction between global and local is not clear-cut. Central-

ized algorithms can be also applied in the distributed setting if a deciding node has full
global information for the network. Through several rounds of sequential information ex-
changes, global or partial global information can be assembled based on local information
only. However, sequential information propagation (also called chain reaction) could be
costly, and this can be measured in terms of rounds. Mobility adds another dimension of
complexity in measuring state information. The locality of maintenance can be used to
measure the adaptiveness of a protocol in the mobile environment. Wu and Lou [8] further
classified protocols based on neighbor-knowledge information: global, quasiglobal, qua-
silocal, and local. The global broadcast protocol, centralized or distributed, is based on
global state information. A survey of centralized broadcasting algorithms (using global
information) is given in [9], and they will not be covered in this chapter. The classical ap-
proximation algorithm by Guha and Khuller [10] for connected dominating sets is based
on global information. In quasiglobal broadcasting, a broadcast protocol is based on par-
tial global state information. For example, the approximation algorithm in [11] is based on
building a global spanning tree (a form of partial global state information) that is con-
structed in a sequence of sequential propagations. Recently, Chen and Liestman [12] pro-
posed a distributed formation of a weakly connected dominating set by iteratively expand-
ing and connecting fragments, similar to the distributed Kruskal™s algorithm. In quasilocal
broadcasting, a distributed broadcast protocol is based on mainly local state information
and occasional partial global state information. Cluster networks are examples of this: al-
though clusters can be constructed locally most of the time, the chain reaction does occur
occasionally. In local broadcasting, a distributed broadcast protocol is based solely on lo-
cal state information. All protocols that select forward nodes locally (based on one-hop or
two-hop neighbor sets) belong to this category. It has been recognized that scalability in
wireless networks cannot be achieved by relying on solutions in which each node requires
global knowledge about the network. To achieve scalability, the concept of localized algo-
rithms was proposed. These algorithms, based on local knowledge, achieve a desired
global objective.

7.1.3 Reliability
Reliability is the ability of a broadcast protocol to reach all the nodes in the network. It
can be considered at the network layer or at the medium-access layer. We will classify pro-
tocols according to their network layer performance. That is, assuming that the MAC lay-
er is ideal (every message sent by a node reaches all its neighbors), a location update pro-
tocol provides accurate desired neighborhood information to all nodes, and the network is
connected, broadcast protocols can be reliable or unreliable. In a reliable protocol, every
node in the network is reached. The set of nodes that rebroadcast a message in a reliable
broadcasting scheme define a connected dominating set. A dominating set D(S) of a set S
is a set of nodes such that each node from S either belongs to D(S) or has a neighboring
node that belongs to D(S). It is easy to observe that all nodes will receive the message if it
is retransmitted only by nodes that belong to a connected dominating set. Connectivity
provides propagation through the whole network, whereas domination assures reachabili-
ty by all nodes. The broadcasting task can therefore be solved optimally by finding a con-
nected dominating set of minimal size. Optimality here is measured by the percentage of
saved retransmissions in a reliable broadcasting scheme. Unfortunately, the problem of
finding a connected dominating set of minimal size is NP-complete, even if a node has
global knowledge about the network [13“15]. Therefore one must apply heuristics to

flood intelligently. Note also that a protocol, such as blind flooding, that is reliable on the
network layer may be very unreliable at the MAC layer. Excess messages in any protocol
affect the node power and bandwidth available; thus, the main goal is to describe a reliable
broadcast protocol with minimal number of retransmissions, that is, to construct a con-
nected dominating set of minimal size. Note also that the MAC layer cannot guarantee
100% reliability due to the hidden-terminal problem (a node simultaneously receiving
messages from two other nodes that are not aware of each other™s transmission) and the
probabilistic nature of protocols used.

7.1.4 “Hello” Message Content
The broadcast schemes may require different neighborhood information, which is reflect-
ed in the contents of messages sent by nodes when they move, react to topological
changes, change activity status, or simply periodically send update messages. A common-
ly seen “hello” message may contain, in addition to its own ID, its position, one bit for
dominating set status (one bit telling neighbors whether or not the node considers itself to
be in a dominating set), a list of one-hop neighbors, and its degree (number of its neigh-
bors). Other content is also possible, such as a list of one-hop neighbors with their posi-
tions, a list of two-hop neighbors, or even global network information. The Global Posi-
tion System (GPS) provides geographic location information (if required) to hosts in a


. 40
( 87 .)