The scheduling and energy complexity of strong connectivity in ultra-wideband networks

Abstract

Recently Moscibroda and Wattenhofer came up with the notion of scheduling complexity to capture the minimum amount of time to successfully schedule all the transmission requests under the physical SINR model. Their algorithm featuring a non-linear power assignment can schedule strongly connected transmissions in narrowband networks with O(log4 n) timeslots. In this paper, we first generalize this result to ultra-wideband networks. We show the strong connectivity scheduling complexity in UWB networks to be O(log(n/w) · log3 n), where m is the processing gain. Secondly, we show that both of these polylogarithmic scheduling complexity results are gained at the expense of exponential energy complexity with lower bound ω(n · 2n). We also prove the upper bound of the energy complexity in narrowband networks to be O(n2 · 2na), and for UWB networks, this upper bound can be reduced by a processing gain factor. On the other hand, we show that improving the scheduling complexity through arbitrary power control has its limitations, and that different power assignment strategies have different impacts on the protocol interference models, which was often neglected in the design of wireless scheduling algorithms. Compared with narrowband networks, although the effect of aggregate interferences in UWB networks is greatly reduced, we demonstrate that the constant and linear power assignments in UWB networks are still inefficient in the worst case with respect to the scheduling complexity (Ω(n/m)), which suggests there is a need for a better arbitrary power assignment. Our analyses shed new light on the design of the power assignment scheme and the performance analysis of the wireless scheduling algorithms. In energy-constrained wireless networks, a tradeoff between the scheduling complexity and energy complexity is a practical consideration. Our results in this paper can be directly applied to other spread-spectrum networks including DS-CDMA and FH-CDMA. Copyright 2006 ACM.