Minimum local disk cover sets for broadcasting in heterogeneous wireless ad hoc networks

Chih Wei Yi, Fang Chun Liu, Min Te Sun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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.

Original languageEnglish
Title of host publication2007 International Conference on Parallel Processing Workshops, ICPPW
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages47-52
Number of pages6
ISBN (Print)0769529348, 9780769529349
DOIs
StatePublished - 2007
Event2007 International Conference on Parallel Processing Workshops, ICPPW 2007 - Xian, China
Duration: 10 Sep 200714 Sep 2007

Publication series

NameProceedings of the International Conference on Parallel Processing Workshops
ISSN (Print)1530-2016

Conference

Conference2007 International Conference on Parallel Processing Workshops, ICPPW 2007
Country/TerritoryChina
CityXian
Period10/09/0714/09/07

Fingerprint

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

Cite this