Figure 7.5. (u, v) is not in the RNG graph because of a witness w.
224 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS
Figure 7.6. RNG graph.
node neighbor, it suffices that only internal nodes retransmit the message. Messages are
only sent on edges connecting two internal nodes (one message per edge). The number of
short messages is then equal to the number of edges in the subgraph of internal nodes.
Each noninternal node, knowing all its internal node neighbors, will choose one of them
and inform that one to send all broadcast messages to it. The number of noninternal nodes
is therefore added to the number of edges connecting internal nodes. Experiments in 
show that less than 10% more messages are needed in that approach compared to RNG-
7.10 BROADCASTING WITH ADJUSTED TRANSMISSION RADII
In the minimum-energy broadcasting problem, each node can adjust its transmission pow-
er in order to minimize total energy consumption but still enable a message to be originat-
ed from a source node to reach all the other nodes in an ad hoc wireless network. The
problem is known to be NP-complete . There exist a number of approximate solutions
in the literature (cited in ) in which each node requires global network information
(including distances between any two neighboring nodes in the network) in order to de-
cide its own transmission radius. Cartigny, Simplot, and Stojmenovic  described a lo-
calized protocol whereby each node requires only the knowledge of its distance to all
neighboring nodes and distances between its neighboring nodes (or, alternatively, geo-
graphic position of itself and its neighboring nodes). In addition to using only local infor-
mation, the protocol is shown experimentally to be competitive even with the best-known
globalized BIP solution , which is a variation of Dijkstraâ€™s shortest-path algorithm.
The solution  is based on the use of a RNG that preserves connectivity and is defined
in a localized manner. The transmission range for each node is equal to the distance to its
furthest RNG neighbor, excluding the neighbor from which the message came. Localized
energy efficient broadcast for wireless networks with directional antennas is described in
, and is also based on RNG. Messages are sent only along RNG edges, requiring
about 50% more energy than the BIP-based  globalized solution. However, when the
communication overhead for maintenance is added, the localized solution becomes supe-
Lipman, Boustead, and Judge  described the following broadcasting protocol.
7.10 BROADCASTING WITH ADJUSTED TRANSMISSION RADII
Table 7.1. Taxonomy of Broadcast Schemes for One-to-All Model with Fixed Transmission Range
Network â€śHelloâ€ť Broadcast
Method Determinism information Reliability message message
Cluster tree  deterministic quazi-global Yes global message only
Clustering [1,17, 22] deterministic quazi-local Yes ID/degree message only
Passive clustering  deterministic local Yes none message + two bits
Probabilistic  probabilistic local No ID/degree message only
Counter/distance, probabilistic local No ID/position message only
Border retransmit  probabilistic local No ID one-hop
Forwarding neighbors deterministic local Yes one-hop forwarding neighbors
[14, 15, 36]
Curved convex hull deterministic local Yes position forwarding neighbors
Curved convex hull deterministic local Yes position + message only
[34, 35] one-hop
Forwarding-node deterministic local Yes ID forwarding neighbors
Partial dominant deterministic local Yes one-hop forwarding neighbors
Lightweight  deterministic local Yes one-hop message only
MPR-dominating  deterministic local Yes one-hop message only
Screening angle / deterministic local No position message only
further neighbor 
Intermediate, Rules 1 deterministic local Yes position or message only
& 2  one-hop
Intermediate, deterministic local Yes  + message only
inter(gateway)  degree
Rule k/connected deterministic local Yes ID message only
component cover 
k-hop dominating deterministic local Yes (k â€“ 1)-hop message only
Announced gateway deterministic local Yes ID/degree message only
 + one bit
k-hop gateway + deterministic local Yes (k â€“ 1)-hop message + last hops
Neighbor elimination deterministic local Yes position/ message only
[14, 22, 39, 45] one-hop
Gateway + neighbor deterministic local Yes position/ message only
elimination  one-hop
RNG relay subset + deterministic local Yes position/ message only
neighbor elim.  one-hop
226 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS
Upon receiving a broadcast message(s) from a node h, each node i (which was determined
by h as a forwarding node) determines which of its one-hop neighbors also received the
same message. For each of its remaining neighbors j (which did not receive a message yet,
based on iâ€™s knowledge), node i determines whether j is closer to i than any one-hop
neighbors of i (that are also forwarding nodes of h) that received the message already. If
so, i is responsible for message transmission to j, otherwise it is not. Node i then deter-
mines a transmission range equal to that of the farthest neighbor it is responsible for.
Table 7.1 presents a taxonomy of broadcast protocols for the omnidirectional antenna
(one-to-all) model with fixed transmission range, following our discussion. Only net-
work-layer methods are included, that is, MAC layer methods discussed in Section 7.7 are
not included. Also not included are a variety of global solutions, which were not within
the scope of this chapter.
Despite the rapidly growing number of publications on the broadcasting problem, no
comprehensive performance evaluation exists. Williams and Camp  compared some se-
lected protocols using the contention-based 802.11 MAC scheme under various network
and mobility scenarios. However, they did not include internal-node-based dominating sets
[24, 22] in their experiments. The articles that did compare their methods with the internal
node-based dominating sets [65, 34] used an inefficient version  of it instead of the im-
proved one in  (the neighbor-elimination scheme is the main improvement) and have
even misunderstood the method, claiming communication overhead for its construction. (In
their defense, the description in  used â€śmarking processâ€ť which is misleading.)
There are some issues not discussed in this survey. For example, Mosko and Garcia-
Luna-Aceves  considered a series of broadcasting tasks and the impact of such flow
on the performance and reliability. Our discussion was restricted to the performance of
one broadcast task at a time. They obtained some initial results, and this and other relevant
issues will be studied further in literature. Thus, we expect increased research activity on
the transport layer of the broadcasting problem.
1. G. Lauer, â€śAddress Servers in Hierarchical Networks,â€ť in Proceedings of ICC, pp. 443â€“451,
2. P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, â€śRouting with Guaranteed Delivery in Ad Hoc
Wireless Networks,â€ť in Proceedings of 3rd International Workshop DIAL M, Seattle, August 20,
1999, pp. 48â€“55; ACM/Kluwer Wireless Networks, 7, 6, 609â€“616, 2001.
3. C. Ho, K. Obraczka, G. Tsudik, and K. Viswanath, â€śFlooding for Reliable Multicast in Multi-
hop Ad Hoc Networks,â€ť in Proceedings of 3rd International Workshop on Discrete Algorithms
and Methods for Mobile Computing and Communication DIALâ€™M, August 1999.
4. G. J. Pottie and W. J. Kaiser, â€śWireless Integrated Network Sensors,â€ť Communications of ACM,
43, 5, 51â€“58, 2000.
5. I. Stojmenovic, â€śVoronoi Diagram and Convex Hull Based Geocasting and Routing in Ad Hoc
Wireless Networks,â€ť in Proceedings of IEEE International Symposium on Computers and Com-
munications ISCC, Turkey, July 2003.
6. X. Jiang and T. Camp, â€śA Review of Geocasting Protocols for a Mobile Ad Hoc Network,â€ť Col-
orado School of Mines, 2002.
7. B. Williams and T. Camp, â€śComparison of Broadcasting Techniques for Mobile Ad Hoc Net-
works,â€ť Proceedings of MobiHoc, Lausanne, Switzerland, June 2002.
8. J. Wu and W. Lou, â€śForward-Node-Set-Based Broadcast in Clustered Mobile Ad Hoc Net-
works,â€ť Wireless Communications and Mobile Computing, 3, 2, 155â€“173.
9. A. Pelc, â€śBroadcasting in Wireless Networks,â€ť in Handbook of Wireless Networks and Mobile
Computing, Wiley, pp. 509â€“528, 2002.
10. S. Guha and S. Khuller, â€śApproximation Algorithms for Connected Dominating Sets,â€ť Algo-
rithmica, 20, 4, 374â€“387, 1998.
11. K. M. Alzoubi, P. J. Wan and O. Frieder, â€śNew distributed Algorithm for Connected Dominat-
ing set in Wireless Ad Hoc Networks,â€ť in Proceedings of Hawaii International Conf. System
12. Y. P. Chen and L. Liestman, â€śApproximating Minimum Size Weakly-Connected Dominating
Sets for Clustering Mobile Ad Hoc Networks,â€ť in Proceedings of MobiHoc, 2002.
13. N. F. Huang and T. H. Huang, â€śOn the Complexity of Some Arborescences Finding Problems
on a Multi-hop Radio Network,â€ť BIT, 29, 212â€“216, 1989.
14. H. Lim and C. Kim, â€śFlooding in Wireless Ad Hoc Networks,â€ť in Proceedings of ACM MSWiM
Workshop at MobiCom, Aug. 2000; Computer Communication Journal, 24, 3â€“4, 353â€“363,
15. A. Qayyum, L. Viennot, and A. Laouiti, â€śMultipoint Relaying: An Efficient Technique for
Flooding in Mobile Wireless Networks,â€ť in Proceedings of Hawaii International Conf. System
Sciences, January 2002.
16. A. Ephremides, J. E. Wieselthier and D. J. Baker, â€śA Design Concept for Reliable Mobile Radio
Networks with Frequency Hoping Signaling,â€ť Proceedings of IEEE, 75, 56â€“73, 1987.
17. C. R. Lin and M. Gerla, â€śAdaptive Clustering for Mobile Wireless Networks,â€ť IEEE Journal on
Selected Areas in Communications, 15, 7, 1265â€“1275, 1997.
18. G. Chen, F. Garcia, J. Solano, and I. Stojmenovic, â€śConnectivity Cased k-hop Clustering in
Wireless Networks,â€ť in CD Proceedings of Hawaii International Conf. System Science, January
19. K. M. Alzoubi, P. J. Wan, and O. Frieder, â€śMessage-optimal Connected Dominating set in Mo-
bile Ad Hoc Networks,â€ť in Proceedings of MobiHoc, 2002.
20. C. C. Chiang, H. K. Wu, W. Liu, and M. Gerla, â€śRouting in Clustered Multihop, Mobile Wire-
less Networks with Fading Ahannel,â€ť in Proceedings of IEEE Singapore International Conf. on
Networks, pp. 197â€“211, 1996.
21. E. Pagani and G. P. Rossi, â€śProviding Reliable and Fault Tolerant Broadcast Delivery in Mobile
Ad-Hoc Networks,â€ť Mobile Networks and Applications, 4, 175â€“192, 1999.
22. I. Stojmenovic, M. Seddigh, and J. Zunic, â€śDominating Sets and Neighbor Elimination Based
Broadcasting Algorithms in Wireless Networks,â€ť IEEE Transactions on Parallel and Distributed
Systems, 13, 1, 14â€“25, 2002.
23. M. Gerla, T. J. Kwon, and G. Pei, â€śOn Demand Routing in Large Ad Hoc Wireless Networks
with Passive Clustering,â€ť in Proceedings of IEEE WCNC, September 2000.
24. J. Wu and H. Li, â€śA Dominating Set Based Routing Scheme in Ad Hoc Wireless Networks,â€ť in
Proceedings of DIAL M, Seattle, August 1999, pp. 7â€“14; Telecommunication Systems, 18, 1â€“2,
25. S.Y. Ni, Y. C. Tseng, Y. S. Chen, and J. P. Sheu, â€śThe Broadcast Storm Problem in a Mobile Ad
Hoc Network,â€ť in Proceedings of MobiCom, Seattle, August 1999, pp. 151â€“162.
26. Y. Sasson, D. Cavin, and A. Schiper, â€śProbabilistic Broadcast for Flooding in Wireless Mobile
Ad Hoc Networks,â€ť Technical Report IC/2002/54, EPFL, July 2002, www.epfl.ch.
228 BROADCASTING AND ACTIVITIY SCHEDULING IN AD HOC NETWORKS
27. J. Cartigny, and D. Simplot, â€śBorder Node Retransmission Based Probabilistic Broadcast Pro-
tocols in Ad Hoc Networks,â€ť Telecommunication Systems, 22, 1â€“4, 189â€“204.
28. G. Calinescu, I. Mandoiu, P. J. Wan, and A. Zelikovsky, â€śSelecting Forwarding Neighbors in
Wireless Ad Hoc Networks,â€ť in Proceedings of DIAL M, 2001.
29. M. T. Sun and T. H. Lai, â€śLocation Aided Broadcast in Wireless Ad Hoc Network Systems,â€ť
in Proceedings of IEEE Symposium on Ad Hoc Wireless Networks, at GLOBECOM,
30. L. Lovasz, â€śOn the Ratio of Optimal Integral and Fractional Covers,â€ť Discrete Mathematics, 13,
31. W. Lou and J. Wu, â€śOn Reducing Broadcast Redundancy in Ad Hoc Wireless Networks,â€ť IEEE
Transactions on Mobile Computing, 1, 2, 111â€“122, 2002.
32. W. Peng and X. Lu, â€śAHBP: An Efficient Broadcast Protocol for Mobile Ad Hoc Networks,â€ť
Journal of Science and Technology, Bejing, China, 2002.
33. W. Peng and X. Lu, â€śEfficient Broadcast in Mobile Ad Hoc Networks Using Connected Domi-
nating Sets,â€ť in Proceedings of ICPADS, Iwate, Japan, July 2000.
34. M. T. Sun and T. H. Lai, â€śComputing Optimal Local Cover Set for Broadcasting in Ad Hoc Net-
works,â€ť in Proceedings of IEEE ICC, pp. 3291â€“3295, 2002.
35. M. T. Sun and T. H. Lai, â€śLocation Aided Broadcast in Wireless Ad Hoc Network Systems,â€ť in
Proceedings of IEEE WCMC, 2002.
36. R. Sisodia, B. Manoj, and C. Murthy, â€śA preferred Link Based Routing Protocol for Wireless
Ad Hoc Networks,â€ť IEEE/KICS Journal of Communication Networks, 4, 1, 14â€“21, 2002.
37. J. Sucec and I. Marsic, â€śAn Efficient Distributed Network-wide Broadcast Algorithm for Mo-
bile Ad Hoc Networks,â€ť CAIP Technical Report 248, Rutgers University, September 2000.
38. S. Rogers, â€śGPS Query Optimization in Ad Hoc Mobile Network Routing,â€ť 2001.
39. I. Stojmenovic and M. Seddigh, â€śBroadcasting Algorithms in Wireless Networks,â€ť in Proceed-
ings of International Conf. on Advances in Infrastructure for Electronic Business, Science, and
Education on the Internet SSGRR, Lâ€™Aquila, Italy, July 31â€“Aug. 6, 2000.
40. A. Boukerche, â€śA Performance Evaluation of a Dynamic Source Routing discovery Optimiza-
tion Using GPS System,â€ť Telecommunication Systems, 22, 1â€“4, 337â€“354.
41. F. Dai and J. Wu, â€śDistributed Dominant Pruning in Ad Hoc Wireless Networks,â€ť in IEEE
42. J. Carle, D. Simplot, and I. Stojmenovic, â€śSensor Area Coverage and Activity Scheduling with
Reduced Dominating Set Size,â€ť in preparation.
43. I. Stojmenovic, â€śClustering with Localized Maintenance via 2-hop Dominating Sets,â€ť in prepa-
44. C. Adjih, P. Jacquet, and L. Viennot, â€śComputing Connected Dominating sets with Multipoint
relays,â€ť Rapport #4597, INRIA, October 2002.
45. W. Peng, X -C. Lu, â€śOn the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks,â€ť
in Proceedings of First Annual Workshop on Mobile and Ad Hoc Networking and Computing,
Boston, August 11, 2000, pp. 129â€“130.
46. J. Wu and F. Dai, â€śBroadcasting in Ad Hoc Networks Based on Self-pruning,â€ť in Proceedings of
IEEE INFOCOM 2003; International Journal of Foundations of Computer Science, to appear.
47. J. Cartigny, F. Ingelrest, and D. Simplot, â€śRNG Relay Subset Flooding Protocols in Mobile Ad
Hoc Networks,â€ť International Journal of Foundations of Computer Science, 14, 2, April 2003,
48. D. G. Petitt, â€śReliable Multicast Protocol Design Choices,â€ť in Proceedings of MILCOM 97,
Vol. 1, November 1997, pp. 242â€“246.
49. C. S. Hsu, Y. C. Tseng, and J. P. Sheu, â€śAn Efficient Reliable Broadcasting Protocol for Wire-
less Mobile Ad Hoc Networks,â€ť 2002.
50. K. Viswanath and K. Obraczka, â€śAn Adaptive Approach to Group Communications in Multi-
hop Ad Hoc Networks,â€ť in Proceedings of IEEE International Symposium on Computers and
Communications ISCC, Taormina, Italy, July 2002, pp. 559â€“566.
51. C. Rohl, H. Woesner, and A. Wolisz, â€śA Short Look on Power Saving Mechanisms in the Wire-
less LAN Standard Draft IEEE 802.11,â€ť in Proceedings of 6th WINLAB Workshop on Third
Generation Wireless Systems, 1997.
52. J. Wu, B. Wu, and I. Stojmenovic, â€śPower-aware Broadcasting and Activity Scheduling in Ad