Minimum Energy Broadcast on Rectangular Grid Wireless Networks

摘要

The minimum energy broadcast problem is to assign a transmission range to each node in an ad hoc wireless network to construct a spanning tree rooted at a given source node such that any non-root node resides within the transmission range of its parent. The objective is to minimize the total energy consumption, i.e., the sum of the δth powers of a transmission range (δ ≧ 1). In this paper, we consider the case that δ = 2, and that nodes are located on a 2-dimensional rectangular grid. We prove that the minimum energy consumption for an n-node k × l-grid with n = kl and k ≦ I is at most n/π + O(n/(k~(0.88))) and at least n/π + Ω(n/k) - O(k). Our bounds close the previously known gap of upper and lower bounds for square grids. Moreover, our lower bound is n/3 - O(1) for 3 ≦ k ≦ 18, which matches a naive upper bound within a constant term for k ≡ 0 (mod 3).