We present the \emph{discrete beeping} communication model, which assumesnodes have minimal knowledge about their environment and severely limitedcommunication capabilities. Specifically, nodes have no information regardingthe local or global structure of the network, don't have access to synchronizedclocks and are woken up by an adversary. Moreover, instead on communicatingthrough messages they rely solely on carrier sensing to exchange information.We study the problem of \emph{interval coloring}, a variant of vertex coloringspecially suited for the studied beeping model. Given a set of resources, thegoal of interval coloring is to assign every node a large contiguous fractionof the resources, such that neighboring nodes share no resources. To highlightthe importance of the discreteness of the model, we contrast it against acontinuous variant described in [17]. We present an O(1$ time algorithm thatterminates with probability 1 and assigns an interval of size$\Omega(T/\Delta)$ that repeats every $T$ time units to every node of thenetwork. This improves an $O(\log n)$ time algorithm with the same guaranteespresented in \cite{infocom09}, and accentuates the unrealistic assumptions ofthe continuous model. Under the more realistic discrete model, we present a LasVegas algorithm that solves $\Omega(T/\Delta)$-interval coloring in $O(\log n)$time with high probability and describe how to adapt the algorithm for dynamicnetworks where nodes may join or leave. For constant degree graphs we prove alower bound of $\Omega(\log n)$ on the time required to solve interval coloringfor this model against randomized algorithms. This lower bound implies that ouralgorithm is asymptotically optimal for constant degree graphs.
展开▼
