An energy-efficient initialization algorithm for random radio networks

摘要

A radio network is a distributed system consisting of a large number of tiny sensors with low-power transceivers and no central controller. One of the most important problems in such networks is to minimize the energy consumption, and maximize the network lifetime. In the initialization problem (also known as naming) each of the $n$ indistinguishable (anonymous) nodes in a given network is assigned a unique identifier, ranging from $1$ to $n$. We consider a network where $n$ nodes (processors) are randomly deployed in a square (resp. a cube) $X$. The network is assumed to be synchronous and the time to be slotted. Two nodes can communicate only if they are at a distance of at most $r$ from each other ($r$ is the transmitting/receiving range). Moreover, if two or more neighbors of a processor $u$ are transmitting concurrently at the same time slot, $u$ cannot receive either of their messages (collision). We suppose also $n$ and $|X|$ represent the only topological knowledge in each node. To solve the initialization problem, we propose an energy-efficient randomized algorithm running in at most $\mathcal{O}\l(n^{3/4}\,\log{(n)}^{1/4}\r)$ time slots, with no station being awake for more than $\mathcal{O}\l(n^{1/4}\,\log{(n)}^{3/4}\r)$ time slots.