The characteristics of wireless communication channels may vary with time due to fading, environmental changes and movement of mobile wireless devices. Tracking and estimating channel gains of wireless channels is therefore a fundamentally important element of many wireless communication systems. In particular, the receivers in many wireless networks need to estimate the channel gains by means of a training sequence. This paper studies the scaling law (on the network size) of the overhead for channel gain monitoring in wireless networks. We first investigate the scenario in which a receiver needs to track the channel gains with respect to multiple transmitters. To be concrete, suppose that there are n transmitters, and that in the current round of channel-gain estimation, k<n+1 channels suffer significant variations since the last round. We prove that Theta(klog((n+1)/k)) time slots is the minimum overhead needed to catch up with the k varied channels. Here a time slot equals one symbol duration. At the same time, we propose a novel channel-gain monitoring scheme named ADMOT to achieve the overhead lower-bound. ADMOT leverages recent advances in compressive sensing in signal processing and interference processing in wireless communication, to enable the receiver to estimate all n channels in a reliable and computationally efficient manner within O(klog((n+1)/k)) time slots. To our best knowledge, all previous channel-tracking schemes require Theta(n) time slots regardless of k. Note that based on above results for single receiver scenario, the scaling law of general setting is achieved in which there are multiple transmitters, relay nodes and receivers.
In July of 2007, Hongyi Yao received his bachelor degree from Electronic Engineering Department of Tsinghua University. In Sept of 2010, he received the PHD degree from Institute for Theoretical Computer Science (ITCS) of Tsinghua University, and in the mean time won the ITCS achievement award 2010. His thesis adviser is Prof. Andrew Yao. He is going to be a postdoc of Prof. Tracey Ho, in the Electronic Engineering Department of California Institute of Technolog.
