Power-Aware Population Protocols

Chuan Xu (1) , Janna Burman (1) , Joffroy Beauquier (1)

1 ParSys - LRI - Systèmes parallèles (LRI)

The contribution of the paper is twofold. First, it introduces a model for analyzing energy consumption in networks of mobile sensors. Second, it uses this model for studying energy complexity of distributed protocols for the task of data collection. The proposed model is quite general and can be used for other tasks. It can be considered as the first extension of this kind, taking into account energy consumption, of the classical model of population protocols. In population protocols, anonymous and bounded memory agents (sensors) move unpredictably and communicate in pairs when two of them are in proximity. The interest of the extended model is to allow a purely analytical analysis of the energy complexity of a protocol, in the same spirit as for time and space complexity, without appealing to simulations. This approach allows to exhibit energy functions and to draw their curves, from which the optimal values of various parameters can be deduced. In order to illustrate the power and the usefulness of this model, we consider the issue of determining and adjusting the amount of agents' initial energy necessary and sufficient for being able to perform a given task. This issue is crucial for choosing, in practice, a category of sensors (in respect with their power capacities) adapted both to the task and to the number of times it should be repeated (before the sensors are replaced or recharged). In this context, the natural chosen metric is the maximum energy spent by an agent (for accomplishing the overall collaborative task). This metric is directly related to the minimum necessary initial energy (and also to the lifetime of the network). Contrary to most of the energy studies in networks of mobile agents, our approach is completely deterministic. The reason is that due to the nature of the considered problem, the analysis has to be done in the worst case (in particular, such analysis is impossible when the interactions between agents are supposed to be probabilistic). The specific task we consider in this work is data collection, which is known to be fundamental in sensor networks. In this problem, initially, each sensor has an input (a sensed) value, and eventually, every input should be delivered exactly once, to a base station. Transfers of inputs between sensors are possible in order to optimize time and energy metrics. In this context, our first contribution is the energy complexity analysis of an already known time optimal protocol. The second contribution is a new power-aware protocol, which improves the previous one in terms of the maximum energy spent by an agent. Finally, we present a lower bound concerning energy consumption of any possible data collection protocol and we show the cases where this lower bound is reached by the presented protocols.

Domaines: Complexité [cs.CC]; Informatique [cs]

Chuan Xu, Janna Burman, Joffroy Beauquier. Power-Aware Population Protocols. 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS), Jun 2017, ATLANTA, United States. ⟨10.1109/ICDCS.2017.238⟩. ⟨hal-01458930v3⟩