Minimum local disk cover sets for broadcasting in heterogeneous multihop wireless networks

Guaning Chen, Chih Wei Yi, Min Te Sun, Fang Chu Liu, Wei Chi Lan

Research output: Contribution to journalArticlepeer-review

Abstract

The concept of forwarding sets is widely adopted in many broadcast protocols for wireless multihop networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its 1-hop neighbors, a.k.a. the forwarding set, to further relay it. In this paper, we propose to use the Minimum Local Disk Cover Set (MLDCS) as the forwarding set in heterogeneous multihop wireless networks, where nodes may have different transmission ranges.We show that the minimum local disk cover set of a node in heterogeneous networks is equivalent to its skyline set, and then we propose a divide-and-conquer algorithm with the optimal time complexity to compute the skyline set locally and statelessly. Moreover, unlike other forwarding heuristics, the proposed algorithm requires only 1-hop neighbor information. This helps to reduce the forwarding set formation latency and thus will be more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.

Original languageEnglish
Pages (from-to)1147-1172
Number of pages26
JournalInternational Journal of Foundations of Computer Science
Volume23
Issue number5
DOIs
StatePublished - Aug 2012

Keywords

  • applications in multihop networks
  • Minimum disc cover
  • optimal algorithms

Fingerprint

Dive into the research topics of 'Minimum local disk cover sets for broadcasting in heterogeneous multihop wireless networks'. Together they form a unique fingerprint.

Cite this