Title :
Minimum Local Disk Cover Sets for Broadcasting in Heterogeneous Wireless Ad Hoc Networks
Author :
Yi, Chih-Wei ; Liu, Fang-Chun ; Sun, Min-Te
Author_Institution :
Nat. Chiao Tung Univ., Hsinchu
Abstract :
The concept of the forwarding set has been used extensively by many broadcast protocols in wireless ad hoc networks to alleviate the broadcast storm problem. In these protocols, when a node receives a broadcast, it only instructs a subset of its neighbors, a.k.a. the forwarding set, to relay the message. In this paper, we propose to use the local minimum disk cover set as the forwarding set in heterogeneous wireless ad hoc networks, where nodes may have different transmission radius. We show that the minimum local disk cover set of a node is equivalent to its skyline set, and propose a divide-and-conquer algorithm with the optimal time complexity O (n log n) to compute the skyline set locally and statelessly.
Keywords :
ad hoc networks; communication complexity; divide and conquer methods; protocols; set theory; broadcast protocols; broadcast storm problem; divide-and-conquer algorithm; forwarding set; heterogeneous wireless ad hoc networks; minimum local disk cover sets; optimal time complexity; Broadcasting; Computer science; Military computing; Mobile ad hoc networks; Monitoring; Network topology; Relays; Storms; Sun; Wireless application protocol;
Conference_Titel :
Parallel Processing Workshops, 2007. ICPPW 2007. International Conference on
Conference_Location :
Xian
Print_ISBN :
0-7695-2934-8
Electronic_ISBN :
1530-2016
DOI :
10.1109/ICPPW.2007.55