The Energy Complexity of Broadcast
The Energy Complexity of Broadcast
复制标题
DOI：
10.1145/3212734.3212774
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Yi-Jun Chang;Varsha Dani;Thomas P. Hayes;Qizheng He;Wenzheng Li;Seth Pettie
中科院分区：
文献类型：
--
作者：
Yi-Jun Chang;Varsha Dani;Thomas P. Hayes;Qizheng He;Wenzheng Li;Seth Pettie
能量通常是电池供电的网络中最受限制的资源，随着设备的较小，他们将能量的较大部分用于通信（收发器使用）而不是计算，而不是为真实的能源使用。为了使设备的传输/listers liste;无线电网络在多跳网络中广播的能量复杂性连接到单跳（集团）网络中的Leadelection的时间复杂性。例如，在CD和无CD模型中，广播需要ω（logn）和ω（log2 n）能量，分别是W.H.P。允许无限的能量预算，其中D是网络的直径。仅在任何常数ε> 0的情况下，就可以在时间复杂上实现接近最佳性。 n）能量。
Energy is often the most constrained resource in networks of batterypowered 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 are as follows. Time lower bounds imply energy lower bounds. The energy complexity of Broadcast in a multi-hop network is connected to the time complexity of LeaderElection 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, Broadcast requires Ω(logn) and Ω(log2 n) energy, respectively, w.h.p. Energy- and time-efficient broadcasting. It requires Ω(D) time to solve Broadcast even allowing unlimited energy budget, where D is the diameter of the network. The complexity measures of energy and time are in conflict, and it is an open problem whether both can be minimized simultaneously. We show that it is possible to achieve near optimality in time complexity with only poly logn energy cost. For any constant ε > 0, Broadcast can be solved in O(D1+ε logO(1/ε) n) time with O(logO(1/ε) n) energy.