Distributed Beamforming with Binary Signaling

Mark Christopher Johnson and Kannan Ramchandran

National Science Foundation 0729237 and National Science Foundation 0635114

We consider a distributed beamforming problem, where nodes are restricted to using binary signaling. The receiver has access to a one-bit noiseless feedback channel, as shown in Figure 1. The objective is for the distributed transmitters to choose a set of signals such that the received signal magnitude is a linear fraction of the maximum possible value. We demonstrate both upper and lower bounds on the convergence time that are linear in the number of nodes in the system. The information-theoretic lower bound is found by modifying the system and then applying point-to-point rate distortion theory. The upper bound is given by analyzing a simple randomized algorithm. Each node toggles its transmitted signal with a fixed probability in every iteration, and the receiver uses the feedback channel to inform the transmitters whether the received signal magnitude increased or decreased. We also discuss mean field methods for accurately approximating the convergence time numerically that apply to this constructive algorithm, as well as more general algorithms. Finally, we investigate a modification of the basic algorithm which improves the constant factor in the running time by dynamically adjusting the probability that each node toggles its signal.

Figure 1
Figure 1: Model of the communication system

M. Johnson, M. Mitzenmacher, and K. Ramchandran, "Distributed Beamforming with Binary Signaling," IEEE International Symposium on Information Theory (ISIT), Toronto, July 2008.

More information: https://www.eecs.berkeley.edu/~mjohnson/