Deploying Wireless Networks with Beeps

Alejandro Cornejo; Fabian Kuhn

paper

Deploying Wireless Networks with Beeps

arXiv:1005.2567

Abstract

We present the \emph{discrete beeping} communication model, which assumes nodes have minimal knowledge about their environment and severely limited communication capabilities. Specifically, nodes have no information regarding the local or global structure of the network, don't have access to synchronized clocks and are woken up by an adversary. Moreover, instead on communicating through messages they rely solely on carrier sensing to exchange information. We study the problem of \emph{interval coloring}, a variant of vertex coloring specially suited for the studied beeping model. Given a set of resources, the goal of interval coloring is to assign every node a large contiguous fraction of the resources, such that neighboring nodes share no resources. To highlight the importance of the discreteness of the model, we contrast it against a continuous variant described in [17]. We present an O(1 $t im e a l g or i t hm t ha tt er mina t es w i t h p r o babi l i t y 1 an d a ss i g n s anin t er v a l o f s i z e$ Ω(T/Δ) $t ha t r e p e a t se v er y$ T $t im e u ni t s t oe v er y n o d eo f t h e n e tw or k . T hi s im p r o v es an$ O(\log n)$ time algorithm with the same guarantees presented in \cite{infocom09}, and accentuates the unrealistic assumptions of the continuous model. Under the more realistic discrete model, we present a Las Vegas algorithm that solves $Ω(T/Δ) $- in t er v a l co l or in g in$ O(\log n) $t im e w i t hhi g h p r o babi l i t y an dd escr ib e h o w t o a d a ptt h e a l g or i t hm f or d y nami c n e tw or k s w h er e n o d es ma y j o in or l e a v e . F or co n s t an t d e g r ee g r a p h s w e p r o v e a l o w er b o u n d o f$ Ω(\log n)$ on the time required to solve interval coloring for this model against randomized algorithms. This lower bound implies that our algorithm is asymptotically optimal for constant degree graphs.

References in corpus (1)

Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time

Deploying Wireless Networks with Beeps

Abstract

References in corpus (1)

Cited by in corpus (14)