{'fraction_non_alphanumeric': 0.036897590361445784, 'fraction_numerical': 0.009370816599732263, 'mean_word_length': 4.350268576544315, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Transmit Beamforming using Feedback Control

A simple feedback control algorithm is presented for distributed beamforming in a wireless network. A network of wireless sensors that seek to cooperatively transmit a common message signal to a Base Station (BS) is considered. In this case, it is well-known that substantial energy efficiencies are possible by using distributed beamforming. The feedback algorithm is shown to achieve the carrier phase coherence required for beamforming in a scalable and distributed manner. In the proposed algorithm, each sensor independently makes a random adjustment to its carrier phase. Assuming that the BS is able to broadcast one bit of feedback each timeslot about the change in received signal to noise ratio (SNR), the sensors are able to keep the favorable phase adjustments and discard the unfavorable ones, asymptotically achieving perfect phase coherence. A novel analytical model is derived that accurately predicts the convergence rate. The analytical model is used to optimize the algorithm for fast convergence and to establish the scalability of the algorithm.


I. INTRODUCTION
Energy efficient communication is important for wireless ad-hoc and sensor networks. We consider the problem of cooperative communication in a sensor network, where there are multiple transmitters (e.g., sensor nodes) seeking to transmit a common message signal to a distant Base Station receiver (BS). In particular, we investigate distributed beamforming, where multiple transmitters coordinate their transmissions to combine coherently at the intended receiver. With beamforming, the signals transmitted from each antenna undergo constructive interference at the receiver, the multiple transmitters acting as a virtual antenna array. Thus, the received signal magnitude increases in proportion to number of transmitters N , and the SNR increases proportional to N 2 , whereas the total transmit power only increases proportional to N . This N -fold increase in energy efficiency, however, requires precise control of the carrier phases at each transmitter in order that the transmitted signals arrive in phase at the receiver. In this paper, we propose a feedback control protocol for achieving such phase coherence. The protocol is based on a fully distributed iterative algorithm, in which each transmitter independently adjusts its phase by a small amount in a manner depending on a single bit of feedback from the BS. The algorithm is scalable, in that convergence to phase coherence occurs in a time that is linear in the number of cooperating transmitters.
Prior work on cooperative communication mainly focuses on exploiting spatial diversity for several wireless relaying and networking problems [1], [2]. Such distributed diversity methods require different transmitters to transmit information on orthogonal channels, which are then combined at the receiver. The resulting diversity gains could be substantial in terms of smoothing out statistical fluctuations in received power due to fading and shadowing environments. However, unlike distributed beamforming, distributed diversity does not provide a gain in energy efficiency in terms of average received power, which simply scales with the transmitted power. On the other hand, the coherent combining of signals at the receiver due to distributed beamforming also provides diversity gains.
Recent papers discussing potential gains from distributed beamforming include [3], which investigates the use of beamforming for relay under ideal coherence at the receiver, and [4], which shows that even partial phase synchronization leads to significant increase in power efficiency in wireless ad hoc networks. The beam patterns resulting from distributed beamforming using randomly placed nodes are investigated in [5]. However, the technical feasibility of distributed beamforming is not investigated in the preceding papers. In our prior work [6], [7], we recognized that the key technical bottleneck in distributed beamforming is carrier phase synchronization across cooperating nodes. We presented a protocol in which the nodes first establish a common carrier phase reference using a master-slave architecture, thus providing a direct emulation of a centralized multi-antenna system. This is a challenging problem, because even small timing errors lead to large phase errors at the carrier frequencies of interest. Once phase synchronization is achieved, reciprocity was proposed as a means of measuring the channel phase response to the BS. In this paper, we present an alternative method of achieving coherent transmission iteratively using a simple feedback control algorithm, which removes the need for explicit estimation of the channel to the BS, and greatly reduces the level of coordination required among the sensors.
Other related work on synchronization in sensor networks is based on pulse-coupled oscillator networks [8] and biologically inspired (firefly synchronization) [9] methods. These methods are elegant, robust and suitable for distributed implementation, however they are limited by assumptions of zero propagation delay and the requirement of mesh-connectivity, and are not suitable for carrier phase synchronization.
We consider the following model to illustrate our ideas. The protocol is initialized by each sensor transmitting a common message signal modulated by a carrier with an arbitary phase offset. (This phase offset is a result of unknown timing synchronization errors, and is therefore unknown.) When the sensors' wireless channel is linear and time-invariant, the received signal is the message signal modulated by an effective carrier signal that is the phasor sum of the channel-attenuated carrier signals of the individual sensors. At periodic intervals, the BS broadcasts a single bit of feedback to the sensors indicating whether or not the received SNR level increased in the preceding interval. Each sensor introduces an independent random perturbation of their transmitted phase offset. When this results in increased total SNR compared to the previous time intervals (as indicated by feedback from the BS), the new phase offset is set equal to the perturbed phase by each sensor; otherwise, the new phase offset is set equal to the phase prior to the perturbation. Each sensor then introduces a new random perturbation, and the process continues. We show that this procedure asymptotically converges to perfect coherence of the received signals, and provide a novel analysis that accurately predicts the rate of convergence. We verify the analytical model using Monte-Carlo simulations, and use it to optimize the convergence rate of the algorithm.
The rest of this paper is organized as follows. Section II describes our communication model for the sensor network. A feedback control protocol for distributed beamforming is described in Section III-A and its asymptotic convergence is shown in Section III-B.
Section IV describes an analytical model to characterize the convergence behavior of the protocol. Some analytical and simulation results are presented in Section V. Section V-A presents an optimized version of the feedback control protocol. Sections V-B and V-C present some results on scalability, and the effect of time-varying channels respectively. Section VI concludes the paper with a short discussion of open issues.

II. COMMUNICATION MODEL FOR A SENSOR
NETWORK We consider a system of N sensors transmitting a common message signal m(t) to a receiver. Each sensor is power constrained to a maximum transmit power of P . The message m(t) could represent raw measurement data, or it could be a waveform encoded with digital data. We now list the assumptions in this model.
1) The sensors communicate with the receiver over a narrowband wireless channel at some carrier frequency, f c . In particular, the message bandwidth B < W c , where B is the bandwidth of m(t) and W c is the coherence bandwidth of each sensor's channel. This means that each sensor has a flatfading channel to the receiver. Therefore the sensor i's channel can be represented by a complex scalar gain h i .
2) Each sensor has a local oscillator synchronized to the carrier frequency f c i.e. carrier drift is small.
One way to ensure this is to use Phase-Locked Loops (PLLs) to synchronize to a reference tone transmitted by a designated master sensor as in [6]. In this paper, we use complex-baseband notation for all the transmitted signals referred to the common carrier frequency f c .
3) The local carrier of each sensor i has an unknown phase offset, γ i relative to the receiver's phase reference. Note that synchronization using PLLs still results in independent random phase offsets In the frequency domain, this becomes: where n(t) is the additive noise at the receiver and N (f ) is its Fourier transform over the frequency range f ≤ which is proportional to the square-root of received SNR.
Note that b i ≤ 1, in order to satisfy the power constraint on sensor i. From the Cauchy-Schwartz In-equality, we can see that to maximize G, it is necessary that the received carrier phases Φ i . = γ i + θ i + ψ i , are all equal: However sensor i is unable to estimate either γ i or ψ i because of the lack of a common carrier phase reference.
In the rest of this paper, we propose and analyze a feedback control technique for sensor i to dynamically compute the optimal value of θ i so as to achieve the condition for equality in (6).

A. Description of Algorithm
The protocol for distributed beamforming works as follows: each sensor starts with an arbitrary (unsynchronized) phase offset γ i . In each time-slot, the sensor applies a random perturbation to θ i and observes the resulting received signal strength y[n] through feedback.
The objective is to adjust its phase to maximize y[n] through coherent combining at the receiver. Each phase perturbation is a guess by each sensor about the correct phase adjustment required to increase the overall received signal strength. If the received SNR is found to increase as a result of this perturbation, the sensor adds the appropriate phase offset, and repeats the process.
This works like a distributed, randomized gradient search procedure, and eventually converges to the correct phase offsets for each sensor to achieve distributed beamform- ing. Fig. 2 shows the convergence to beamforming with N = 10 sensors.
is the received signal phase corresponding to sensor i. We set the proportionality constant to unity for simplicity of analysis.
At each time instant n, let θ i [n] be the best known carrier phase at sensor i for maximum received SNR.
Each sensor uses the distributed feedback algorithm to dynamically adjust θ i [n] to satisfy (6) asymptotically.
The algorithm works as follows.
Initially the phases are set to zero: θ i [1] = 0. At each time-slot n, each sensor i applies a random phase perturbation δ i [n] to θ i [n] for its transmission. As a result, the received phase is given by: The BS measures Y[n] and keeps a record of the highest all previous timeslots. At the end of each timeslot, the BS broadcasts a one-bit feedback message that indicates whether the received signal strength of the preceding timeslot was higher than the previous highest signal strength. Depending on the feedback message, each sensor i updates its phase according to: Simultaneously, The BS also updates its highest received signal strength: This has the effect of retaining the phase perturbations that increase SNR and discarding the unfavorable ones that do not increase SNR. The sensors and the BS repeat the same procedure in the next timeslot.
The random perturbation δ i [n] is chosen independently across sensors from a probability distribution parameter of the protocol. In this paper, we consider We allow for the possibility that the distribution f δ (δ i ) dynamically changes in time.
It follows from (7) that if the algorithm were to be terminated at timeslot n, the best achievable signal strength using the feedback information received so far, is equal to Y best [n], which correspond to sensor i

B. Asymptotic Coherence
We now show that the feedback control protocol outlined in Section III-A asymptotically achieves phase coherence for any initial values of the phases Φ i . LetΦ denote the vector of the received phase angles Φ i . We define the function Mag(Φ) to be the received signal strength corresponding to received phaseΦ: Phase Φ const is an arbitrary phase constant. In order to remove this ambiguity, it is convenient to work with the rotated chosen such that the phase of the total received signal is zero. This is just a convenient shift of the receiver's phase reference and as (10) shows, such a shift has no impact on the received signal strength: We interpret the feedback control algorithm as a discrete-time random process Y best [n] in the state-space ofφ, the state-space being the N -dimensional space of the phases φ i constrained by the condition that the phase of the received signal is zero. We observe that the sequence {Y best [n]} is monotonically non-decreasing, and is upperbounded by G opt as shown in (5). Therefore each realization of {Y best [n]} is always guaranteed to i.e. the limit G 0 of the sequence {Y best [n]} is the same as its Least Upper Bound [10]. In general the limit G 0 would depend on the starting phase anglesφ. We now provide an argument that shows (under mild conditions on the probability den- the constant G opt with probability 1 for arbitrary starting phasesφ. The following proposition will be needed to establish the convergence. Proof. For the class of distributions f δ (δ i ) that we consider, the probability of choosing δ i in any finite Recall that the phase reference is chosen such that the total received signal i a i e jφi has zero phase. First we sort all the phases φ i in the vectorφ in the descending order of |φ i | to get the sorted phases φ * i satisfying |φ * 1 | > |φ * 2 | > ... > |φ * N |, and the corresponding sorted channel gains a * i . We use the condition Mag(φ) < G opt − ǫ to get: Now we choose a phase perturbation δ 1 that decreases |φ * 1 |. This makes the most mis-aligned phase inφ closer to the received signal phase, and thus increases the magnitude of the received signal. If φ * 1 > 0, then we need to choose a δ 1 < 0, whereas if φ * 1 < 0, we need δ 1 > 0. In the following, we assume that φ * 1 > 0 and φ ǫ > δ 0 . The argument below does not depend on these assumptions, and can be easily modified for the other . This is an interval in which f δ (δ 1 ) is non-zero , therefore there is a non-zero probability ρ 1 > 0 of choosing such a δ 1 . We have: We observe that ǫ 1 and ρ 1 do not dependent onφ.
The perturbation δ 1 by itself will achieve a non-zero increase in total received signal, provided that the other phases φ * i do not get too mis-aligned by their respective δ i : We note that since Mag(φ) is continuous in each of the phases φ * i , we can always find a ǫ i > 0 to satisfy: In particular the choice ǫ i . = ǫ1 a * i (N −1) , satisfies (15), and this choice of ǫ i is independent ofφ. With the δ i 's chosen to satisfy (15), we have: Since f δ (δ i ) has non-zero support in each of the nonzero intervals (−ǫ i , ǫ i ), the probability ρ i of choosing δ i to satisfy (15) is non-zero, i.e. ρ i > 0, which is independent ofφ. Finally, we recall that each of the δ i are chosen independently, and therefore with probability ρ = i ρ i > 0, it is possible to find δ 1 to satisfy (13) and δ i , i > 1 to satisfy (15). Forδ chosen as above, Mag(φ +δ) − Mag(φ) > ǫ 1 , and therefore Proposition 1 follows. Consider an arbitrarily small ǫ > 0 and define T ǫ (φ) as the first timeslot when the received signal exceeds By definition if n < T ǫ (φ), then Y best [n] = Mag(φ[n]) < G opt − ǫ, and by Proposition 1, constants ǫ 1 > 0 and ρ > 0. We have: Using (17) we have: Taking expectation we have: where we obtained (19) by using (17). Therefore we have P rob(T ǫ (φ) > n) < 1 n G opt ǫ1ρ → 0, as n → ∞. Since this is true for an arbitrarily small ǫ, we have shown that Y best [n] → G opt andφ[n] →0 almost surely.

IV. ANALYTICAL MODEL FOR CONVERGENCE
The analysis in Section III-B shows that the feedback control algorithm of Section III-A asymptotically converges for a large class of distributions f δ (δ i ); however it provides no insight into the rates of convergence.
We now derive an analytical model based on simple, intuitive ideas that predicts the convergence behavior of the protocol accurately. We then use this analytical model, to optimize f δ (δ i ) for fast convergence.

A. Derivation of Analytical Model
The basic idea behind our analytical model is that the convergence rate of typical realizations of Y best [n] is well-modeled by computing the expected increase in signal strength at each time-interval given a distribution f δ (δ i ). This is illustrated in Fig. 3 Consider: In most cases, the function F (y) is concave, and therefore (by Jensen's Inequality) the approximation in (23) represents an overestimate of the unconditional aver- where The random variables x 1 , x 2 are illustrated in Fig. 4. Therefore as the number of sensors N increases, these random variables can be well-modeled as Gaussian, as per the CLT [11]. Futhermore, x 1 , x 2 are zero-mean random variables, and their respective variances σ 2 1 , σ 2 2 are related by: With these simplifications, the statistics of y[n + 1] only depends on the density function f δ (δ i ) through C δ and C 2δ . We have the following proposition.

Proposition 2:
Assuming that the CLT applies for random variable x 1 , the expected value of the received signal strength is given by: Proof. First we observe that the small imaginary component x 2 of the perturbation mostly rotates the received signal, with most of the increase in y[n + 1] coming from x 1 (see Fig. 4).
Defining p as the probability that Y best [n + 1] > y[n], where f (y)  We find that the Laplacian probability distribution gives the best results 2 in terms of accurately predicting the convergence behavior of the algorithm of Section III-A. Fig. 5 shows an empirically derived histogram 1 It is important to note that the φ i are not random variables, however we statistically parametrize them using a probability distribution for the sake of compactness. 2 The Laplacian distribution for φ i is empirically found to work well, when compared with other families of distributions like the uniform and triangular distributions. from a Monte-Carlo simulation of the feedback control algorithm. A Laplacian approximation is also plotted alongside the histogram. We now explain the details of the approximation.
The Laplacian density function is given by [11]: For φ i distributed according to (37), we also have: Therefore given that at iteration n of the feedback algorithm, the phase angles areφ[n] = [φ 1 φ 2 ...φ N ], we have: where we used a i = 1 in (10). Now if we parametrize all the φ i using a Laplacian distribution, we can set φ 0 such that i cos φ i ≡ N E φ cos φ . Thus we use (38) to rewrite (40) as: We are now able to determine σ 1 given y[n].

C. Summary of Analytical Model
We now summarize the analytical model derived in We observe from Fig. 6, that the received signal grows rapidly in the beginning, but after y[n] gets to within about 25% of G opt , the rate of convergence becomes slower. Also while the simple two-valued probability distribution appears to give good results, it does not satisfy the condition for asymptotic coherence derived in Section III-B. Using the identity cos(2δ) = 2 cos 2 (δ) − 1 and Jensen's Inequality, we can show that C 2δ is constrained by the value of C δ : We are interested in δ i corresponding to small random perturbations i.e. δ i ≪ π 2 . For such small values of δ i , (43) allows only a small range of possible values of C 2δ .
Indeed we observe that cos(δ i ) and cos(2δ i ) are very well approximated by the first two terms of the Taylor series: Equation (44) indicates that both C δ and C 2δ are essentially determined by the second moment of δ i , and therefore even a one-parameter family of distributions f δ (δ i ) is sufficient to achieve optimality of the convergence rate. Fig. 7 shows plots of the optimal choices of the the optimal parameters in each case were determined numerically using a simple search procedure. The two curves in Fig. 7 were obtained by plotting (C δ , C 2δ ) pair corresponding to the optimal parameters for cases (i) and (ii) at each timeslot. The 3-point distribution is flexible enough to permit any (C δ , C 2δ ) in the feasible region of (43). For the example of Fig. 7, it is clear that the uniform distribution achieves values of (C δ , C 2δ ) that is close to optimal, thereby confirming the intuition of (44).  We now use the family of distributions f δ (δ i ) ∼ uniform[−δ 0 , δ 0 ] to obtain insight into the optimal convergence rate. Fig. 8 shows y[n] as a function of n for fixed values of δ 0 as well as for the optimized algorithm. We observe that the convergence rate decreases with time in all cases, and the optimized algorithm converges significantly faster than any fixed instance. and Proof. We offer a proof by induction. From Section IV-C, we know that y 2 [1] > y 1 [1] where F 1 (y) and F 2 (y) are defined as in (36). Note that F 1 (y 1 [n]) (and F 2 (y 2 [n])) depends on the time index n not only through y 1 [n] (y 2 [n]), but also through the distribution f δ (δ i ). We have suppressed this additional time-dependence to keep the notation simple. The functions F 1 (y) and F 2 (y) satisfy the following properties: To see this we observe from (42) that for the same value of y, σ 1 is larger for larger N , and since f (y) in (36) We are now ready to complete the proof of (45) by induction. Given that y 2 [n] > y 1 [n], we have: where we used (47) and (48) for the two inequalities.
This completes the proof of (45). The proof of (46) by induction is similar and is omitted.
Proof. First we use (43) to get a lower-bound for the variance σ 2 1 . With y[n] = f · G opt = f · N we have: Using the upper bound from (52) in (42), we have: We now use a bound for the Gaussian Q-Function: Using (54), we rewrite (33) to get: The bound in (55) has a maximum at x 0 ≈ 3.6; choosing a C δ such that x is close to x 0 , does not necessarily optimize the RHS in (55), because σ 1 also depends on C δ . However such a choice for C δ does provide a meaningful lower bound on the optimal ∆y * [n].
Let us denote the RHS of (58) by K(f ).
We observe that the lower bound in (58) Since T f is just a sum of terms like T f,∆f , (51) immediately follows.
Theorem 3 is illustrated by the results in Fig. 9, where the number of timeslots required to get within a certain fraction of convergence is plotted against number of transmitters N for a fixed distribution ( Fig. 9(a)) as well as optimized distributions ( Fig. 9(b)). These results show that the feedback algorithm is highly scalable with number of transmitters.

C. Tracking Time-varying channels
So far we have focused on the simple case of timeinvariant wireless channels from each sensor to the BS.
In practice, the channel phase response varies because of Doppler effects arising from the motion of the sensors or scattering elements relative to the BS. In the dis-

VI. CONCLUSION
In this paper, we presented a simple algorithm for distributed beamforming in sensor networks, that is based on the idea of using SNR feedback from the receiver to perform phase synchronization in an iterative manner. This algorithm can be easily implemented in a decentralized manner and is guaranteed to achieve asymptotic coherence under mild assumptions. We also derived an analytical model that predicts the performance of the algorithm accurately, and offers insight into the convergence behavior.
This paper represents an initial study into a new ap-