On selection problem in radio networks

Research output: Contribution to conferencePaperpeer-review

93 Scopus citations

Abstract

22ndA selection problem is among the basic communication primitives in networks. In this problem at most k participating stations have to broadcast successfully their messages. This problem is especially important in packet radio networks, where simultaneous transmissions of many neighbors result in interference among delivered messages. This work focuses on a single-hop radio networks with n-stations, also called a multiple access channel, and considers both static and dynamic versions of the selection problem. We construct a family of efficient oblivious deterministic protocols based on selectors, one of them with selection time Ο(k log(n/k)), and the second explicit construction with selection time O(k polylog n). The first construction matches the lower bound Ω(k log(n/k)) on deterministic oblivious selection, while the second one is the first known explicit construction better than ⊖(k 2). In the dynamic case we introduce the model of dynamic requests, called k-streams, which generalizes the static model and the dynamic requests with at most k participants. We prove that each oblivious deterministic protocol has latency Ω(k 2/log k), and on the other hand we prove the existence of the oblivious deterministic protocol with latency Ο(k 2log n). In view of the existence of the randomized oblivious protocol with expected latency O(k log(n/k)), this shows that randomization is substantially better than determinism for dynamic setting. Selection problem can be applied to implement other communication primitives - we demonstrate it in the example of broadcast problem in multi-hop ad-hoc radio networks. In particular, we design an adaptive deterministic protocol broadcasting in time Ο (n log D) in every D-hop radio network of n-stations.

Original languageEnglish (US)
Pages158-166
Number of pages9
DOIs
StatePublished - 2005
Externally publishedYes
Event24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005 - Las Vegas, NV, United States
Duration: Jul 17 2005Jul 20 2005

Conference

Conference24th Annual ACM Symposium on Principles of Distributed Computing, PODC 2005
Country/TerritoryUnited States
CityLas Vegas, NV
Period7/17/057/20/05

Keywords

  • Broadcast problem
  • Multiple Access Channel
  • Radio networks
  • Selection problem

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'On selection problem in radio networks'. Together they form a unique fingerprint.

Cite this