Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On Complexity of Wireless Gathering Problems on Unit-Disk Graphs
verfasst von : Nikola Milosavljević
Erschienen in: Ad-hoc, Mobile, and Wireless Networks
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We address the problem of efficient gathering of data from a wireless network to a single sink node. Network’s communication and interference pattern are assumed to be captured by the unit-disk model. We consider the objective of minimizing the maximum latency (the time between release and delivery of a packet). We prove that the problem is NP-complete even when all packets are released from the same source node, or at the same time. To our knowledge, these are the first results about the wireless gathering problem in the plane. They can be seen as an extension of recent inapproximability results of Bonifaci et al., which hold in three dimensions.