<<

. 44
( 87 .)



>>





w

u v



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 [59]
show that less than 10% more messages are needed in that approach compared to RNG-
based one.


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 [13]. There exist a number of approximate solutions
in the literature (cited in [61]) 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 [61] 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 [62], which is a variation of Dijkstra™s shortest-path algorithm.
The solution [61] 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
[63], and is also based on RNG. Messages are sent only along RNG edges, requiring
about 50% more energy than the BIP-based [62] globalized solution. However, when the
communication overhead for maintenance is added, the localized solution becomes supe-
rior.
Lipman, Boustead, and Judge [64] described the following broadcasting protocol.
225
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 [11] deterministic quazi-global Yes global message only
Clustering [1,17, 22] deterministic quazi-local Yes ID/degree message only
Passive clustering [23] deterministic local Yes none message + two bits
Probabilistic [25] probabilistic local No ID/degree message only
Counter/distance, probabilistic local No ID/position message only
location [25]
Border retransmit [27] 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
[29, 28]
Curved convex hull deterministic local Yes position + message only
[34, 35] one-hop
Forwarding-node deterministic local Yes ID forwarding neighbors
cluster [8]
Partial dominant deterministic local Yes one-hop forwarding neighbors
prunning [31]
Lightweight [37] deterministic local Yes one-hop message only
MPR-dominating [44] deterministic local Yes one-hop message only
Screening angle [38]/ deterministic local No position message only
further neighbor [39]
Intermediate, Rules 1 deterministic local Yes position or message only
& 2 [24] one-hop
Intermediate, deterministic local Yes [24] + message only
inter(gateway) [22] degree
Rule k/connected deterministic local Yes ID message only
component cover [41]
k-hop dominating deterministic local Yes (k “ 1)-hop message only
set [43]
Announced gateway deterministic local Yes ID/degree message only
[42] + one bit
k-hop gateway + deterministic local Yes (k “ 1)-hop message + last hops
neighbor elimination
[46]
Neighbor elimination deterministic local Yes position/ message only
[14, 22, 39, 45] one-hop
Gateway + neighbor deterministic local Yes position/ message only
elimination [22] one-hop
+ degree
RNG relay subset + deterministic local Yes position/ message only
neighbor elim. [47] one-hop
+ degree
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.


7.11 CONCLUSION

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 [7] 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 [24] of it instead of the im-
proved one in [22] (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 [24] used “marking process” which is misleading.)
There are some issues not discussed in this survey. For example, Mosko and Garcia-
Luna-Aceves [66] 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.



REFERENCES

1. G. Lauer, “Address Servers in Hierarchical Networks,” in Proceedings of ICC, pp. 443“451,
1988.
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.
227
REFERENCES


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
Sciences, 2002.
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,
2001.
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
2002, INIB03.
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,
13“36, 2001.
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,
November 2001.
30. L. Lovasz, “On the Ratio of Optimal Integral and Fractional Covers,” Discrete Mathematics, 13,
383“390, 1975.
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
Globecom, 2002.
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-
ration.
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,
253“266.
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-
229
REFERENCES


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

<<

. 44
( 87 .)



>>