In wireless networks, consisting of battery-powered devices, energy is a costly resource and most of it is spent on transmitting and receiving messages. Broadcast is a problem where a message needs to be transmitted from one node to all other nodes of the network. We study algorithms that can work under limited energy measured as the maximum number of transmissions by a single station. The goal of the paper is to study tradeoffs between time and energy complexity of broadcast problem in multi-hop radio networks. We consider a model where the topology of the network is unknown and if two neighbors of a station are transmitting in the same discrete time slot, then the signals collide and the receiver cannot distinguish the collided signals from silence. We observe that existing, time efficient, algorithms are not optimized with respect to energy expenditure. We then propose and analyse two new randomized energy-efficient algorithms. Our first algorithm works in time @math with high probability and uses @math energy per station for any @math for any graph with @math nodes and diameter @math . Our second algorithm works in time @math with high probability and uses @math energy. We prove that our algorithms are almost time-optimal for given energy limits for graphs with constant diameters by constructing lower bound on time of @math . The lower bound shows also that any algorithm working in polylogaritmic time in @math for all graphs needs energy @math .
Recently Chang al @cite_18 presented various results about energy-efficient broadcast. Their assumptions differs however from ours in two aspects. @cite_18 the authors assume that the stations which have not received the message are allowed to make transmissions. Secondly the energy complexity in @cite_18 includes the number of times a station listens to the channel. Because of that the minimal energy complexity can be shown to be @math for graphs with maximum degree @math . In contrast, in our setting, where only the number of transmissions. The authors in @cite_18 showed an algorithm with time complexity @math and energy @math for the model without collision detection.
@cite_18
2763569140
Energy is often the most constrained resource in networks of battery-powered devices, and as devices become smaller, they spend a larger fraction of their energy on communication (transceiver usage) not computation. As an imperfect proxy for true energy usage, we define energy complexity to be the number of time slots a device transmits listens; idle time and computation are free. In this paper we investigate the energy complexity of fundamental communication primitives such as broadcast in multi-hop radio networks. We consider models with collision detection (CD) and without (No-CD), as well as both randomized and deterministic algorithms. Some take-away messages from this work include: 1. The energy complexity of broadcast in a multi-hop network is intimately connected to the time complexity of leader election in a single-hop (clique) network. Many existing lower bounds on time complexity immediately transfer to energy complexity. For example, in the CD and No-CD models, we need @math and @math energy, respectively. 2. The energy lower bounds above can almost be achieved, given sufficient ( @math ) time. In the CD and No-CD models we can solve broadcast using @math energy and @math energy, respectively. 3. The complexity measures of Energy and Time are in conflict, and it is an open problem whether both can be minimized simultaneously. We give a tradeoff showing it is possible to be nearly optimal in both measures simultaneously. For any constant @math , broadcast can be solved in @math time with @math energy, where @math is the diameter of the network.