Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Deterministic communication in radio networks

Tools
- Tools
+ Tools

Czumaj, Artur and Davies, Peter (2018) Deterministic communication in radio networks. SIAM Journal on Computing, 47 (1). pp. 218-240. doi:10.1137/17M1111322 ISSN 0097-5397.

[img]
Preview
PDF
WRAP-deterministic-communication-radio-networks-Czumaj-2017.pdf - Accepted Version - Requires a PDF viewer.

Download (880Kb) | Preview
Official URL: https://doi.org/10.1137/17M1111322

Request Changes to record.

Abstract

In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad hoc radio networks with unknown topology: broadcasting and wake-up. We consider an unknown radio network, in which all nodes have no prior knowledge about network topology, and know only the size of the network $n$, the maximum in-degree of any node $\Delta$, and the eccentricity of the network $D$. For such networks, we first give an algorithm for wake-up, based on the existence of small universal synchronizers. This algorithm runs in $O(\frac{\min\{n, D\Delta\} \log n \log \Delta}{\log\log \Delta})$ time, the fastest known in both directed and undirected networks, improving over the previous best $O(n \log^2n)$-time result across all ranges of parameters, but particularly when maximum in-degree is small. Next, we introduce a new combinatorial framework of block synchronizers and prove the existence of such objects of low size. Using this framework, we design a new deterministic algorithm for the fundamental problem of broadcasting, running in $O(n \log D \log\log\frac{D\Delta}{n})$ time. This is the fastest known algorithm for the problem in directed networks, improving upon the $O(n \log n \log \log n)$-time algorithm of Marco [SIAM J. Comput., 39 (2010), pp. 2162--2175] and the $O(n \log^{2}D)$-time algorithm due to Czumaj and Rytter [in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), 2003]. It is also the first to come within a log-logarithmic factor of the $\Omega(n \log D)$ lower bound due to Clementi et al. [Theoret. Comput. Sci., 302 (2003), pp. 337--364]. Our results also have direct implications on the fastest deterministic leader election and clock synchronization algorithms in both directed and undirected radio networks, tasks which are commonly used as building blocks for more complex procedures.

Item Type: Journal Article
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Cognitive radio networks, Electric network topology
Journal or Publication Title: SIAM Journal on Computing
Publisher: Society for Industrial and Applied Mathematics
ISSN: 0097-5397
Official Date: 15 February 2018
Dates:
DateEvent
15 February 2018Available
7 November 2017Accepted
Volume: 47
Number: 1
Page Range: pp. 218-240
DOI: 10.1137/17M1111322
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 19 January 2018
Date of first compliant Open Access: 21 February 2019
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
UNSPECIFIEDUniversity of Warwickhttp://dx.doi.org/10.13039/501100000741
Version or Related Resource: A preliminary version appeared under the title "Faster deterministic communication in radio networks". in Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Rome, Italy, July 12 - 15, 2016
Related URLs:
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us