Deterministic recurrent communication in restricted sensor networks (Q764337)

The paper considers distributed computing in sensor networks where \(n\) nodes are placed in a plane (\(\mathbb{R}^2\)) and every node can (potentially) communicate with any node within radius \(1\). The computation is structured into timeslots and each node can choose to either transmit or receive during a particular timeslot. Communication between nodes is implemented by wireless broadcast. Therefore, if multiple adjacent nodes attempt to transmit a message in the same timeslot, a collision occurs and the message is lost. Moreover, nodes cannot distinguish between the case where a collision occurs and the case where no message has been sent. If there are no other simultaneous transmission within a 2-neighborhood of a transmitting node, the transmission is said to be clear. Clear receptions are defined analogously with respect to a receiving node. Nodes themselves are powered up at an arbitrary point in time, which is chosen by the adversary. In this setting, the authors study several variants of the important selection problem (cf. Definition 1) where \(k\leq n\) nodes are active. Each active node holds a distinct message that needs to be delivered to all other active nodes. For single-hop network, the authors consider the recurring selection problem where every active node needs to achieve infinitely many clear transmissions. In multi-hop networks, this problem generalizes to recurring reception (cf. Definition 2) where each active node has infinitely many clear reception from all of its active neighbors, and recurring transmission (cf. Definition 3), where each active node must have infinitely many clear transmissions. The authors provide several (deterministic) protocols for these problems that are formally analysed with respect to their message complexity and the induced delay. A protocol is either oblivious (cf. Section 2), if the future transmissions that a node performs are independent of the messages received so far, or adaptive (cf. Section 3) otherwise. The authors present an oblivious protocol (called Primed Selection) that turns out to be optimal with respect to message complexity and induces a delay of \(k(n+k)(\ln(n+k)+\ln\ln(n+k))\) where \(k\) is the number of active nodes. For adaptive protocols, the authors consider a variant of the Primed Selection protocol (Reduced Primed Selection) that improves the worst case delay of Primed Selection. The delay bound is further improved by the Prime-Compression Selection protocol which is delay-optimal with respect to the lower bounds that we describe below. Several lower bounds for the recurring selection problem are presented, which imply analogous results for recurring transmission and recurring reception: First, the authors show that any oblivious (deterministic) protocol has a message complexity of at least \(k\), i.e., the number of active nodes. By establishing a mapping between the Recurring Selection problem and the combinatoric concept of \((m,k,n)\)-selectors, the authors obtain a lower bound of \(\Omega(k^2 \log n / \log k)\) for the delay of any Recurring Selection protocol.