# Distributed adaptive transmit beamforming

The advancing miniaturisation of electronics and its integration into everyday objects fosters smart spaces as an antecedent to an Internet of Things (IoT).
In such environments, arbitrarily distributed, sharply resource restricted devices share data acquired by their sensors and cooperate in their data processing in order to establish an intelligent and responsive smart space.
Instead of being equally distributed among an environment, the processing and communicating devices are likely clustered in distant physical spaces.
Consequently, for the sharply resource restricted devices it might be difficult to establish a connection among the spread clusters of devices.
Natural clusters are given, for instance, by the set of devices worn or carried by a person or also by a working place constituted of a high density of electronically enhanced tools.
In a smart space, clusters should be connected to share information and provide additional value to an individual in this space.

Since IoT devices (possibly featuring RFID or Organic Electronics) will have a sharply restricted transmission range for their low energy budget available, these clusters, however, might be frequently disconnected.
From a communication perspective, the signal strength of such resource restricted devices in one cluster might be too weak to reach a remote cluster at sufficient Signal-to-Noise Ratio (SNR).
Therefore, although nodes in a remote cluster might sense some activity on the channel, the signal strength is too weak for them to decode information.

One solution to increase the transmission range of nodes in a cluster and thereby to establish a connection is to combine their transmit signals during simultaneous, phase-aligned transmission on the wireless channel.

By superimposing signals on the wireless channel in-phase, they are accumulated and therefore strengthened so that the transmission range can be extended.

In the literature, several approaches for such beamforming among distributed nodes are proposed.
The most common ones require either code divisioning techniques or for the receiving node to conduct significant computation.
Such process, however, is exhaustive for sharply resource restricted IoT nodes in a smart space.
A simpler, less resource consuming, method was proposed by Mudumbai and others.
The authors employ an iterative random search mechanism in which nodes in each iteration may randomly change the phase of their carrier signal conditioned on a binary feedback from the receiver.
This approach is better suited for IoT nodes for its low computational complexity to randomly draw alternative signal phases at nodes.
Since the binary feedback can be encoded as an energy efficient on/off (burst transmission=1, no transmission=0) scheme, the required SNR can be low.
This carrier synchronisation scheme is applicable also with inexpensive crystal oscillators with high frequency derivations such as we can expect for IoT devices.

For this scheme we derived a sharp asymptotic bound on the expected optimisation time for n transmit devices and k possible transmit carrier phases each of Θ(nk log(n)).
This performance is the main drawback of the beamforming scheme for smart spaces.
Significant count of iterations and therefore a high number of transmissions are required which slows down the synchronisation.

In an alternative asymptotically optimal, iterative optimisation approach was presented.
Although its optimisation performance was as low as O(n), this improved performance was achieved at the cost of a more descriptive receiver feedback so that it can not be implemented as a simple on/off scheme and is therefore less well suited for resource restricted IoT nodes.

Another possibility to improve the synchronisation performance is to modify the random search for synchronised transmit phases at nodes.
The original approach employed an evolutionary random search.
However, the search space of the problem is rather simple and does not contain any local optima.

Therefore, we propose to utilise a fast local random search to establish carrier synchronisation among nodes.
In particular, we derive an asymptotic upper and lower bound for the expected optimisation time and compare the approach to the one presented before in simulations and a case study.

## Contributions

- Sharp asymptotic bound on the synchronisation performance of a global random search approach
- Simulations and case studies in realistic environments
- Upper and lower bounds on various local random search approaches
- Considerations of various modifications to speed up the synchronisation process
- Asymptotically optimal algorithm

## Results

### Sharp asymptotic bounds on the synchronisation time

We have considered randomised search approaches to solve the problem of distributed adaptive transmit beamforming.
In an analytic consideration an asymptotically tight bound on the expected optimisation time of Θ(nk log(n)) was derived.

Additionally, a protocol to further reduce the optimisation time and energy consumption of distributed adaptive beamforming was introduced.
In this protocol, the problem was divided into sub-problems that were solved iteratively.
Since the decrease in the synchronisation time is greater than the increase in transmission power in smaller clusters, this approach can improve the optimisation time and reduce energy consumption.

Furthermore, an asymptotically optimal algorithm was derived.
For this approach we considered the possibility to estimate the unknown feedback function by an individual node so that an optimisation approach is possible that scales linearly with the network size n.
This approach is asymptotically optimal since each carrier signal has to be considered at least once individually in order to find its optimum phase offset.

In mathematical simulations we demonstrated the effect of several configurations for distributed adaptive transmit beamforming with uniform and normal distributed phase alteration methods.
Generally, a low mutation probability translates to a better performance in the phase synchronisation process.
An adaptive probability over the course of the optimisation might further improve the optimisation speed.
While a moderate mutation probability is beneficial at the beginning of the simulation, a smaller mutation probability shows an improved optimisation speed later in the process.
Also, our implementation of the asymptotically optimal method greatly outperforms the global random search approach in the synchronisation achieved and the optimisation speed.

Finally, in an instrumentation with USRP software radios we demonstrated the feasibility of distributed adaptive transmit beamforming in a concrete implementation with up to four transmitters.

### Synchronisation performance of improved algorithms

In order to speed up the synchronisation process we considered several changes in the algorithm utilised.

For instance, we employed a local random search approach that was able to speed up the synchronisation method.
We observed that minimum mutation probabilities together with a suitable variance are well suited to achieve optimum synchronisation performance.
Furthermore, by considering smaller clusters of nodes to synchronise in a hierarchical fashion, we were able to improve the synchronisation speed.

We derived an upper bound on the synchronisation time of a local random search implementation.
Furthermore, we proposed three modifications of the global search approaches that improve the synchronisation performance of distributed adaptive beamforming in wireless sensor networks.
For these approaches we achieved quantitative results in mathematical simulations for a network of 100 nodes.

In mathematical simulations we could show that the synchronisation of phases of RF transmit signal components is possible even when the signal strength of individual RF signal components is below the thermal noise level.
In particular, the noise level does not impact the speed of the synchronisation process.
However, the spread of relative phase offsets increases with increasing relative noise level.
Furthermore, we presented an $\Theta(n)$ optimisation algorithm for distributed adaptive beamforming in wireless sensor networks and compared its performance in mathematical simulations to a standard random search heuristic.

In a near realistic instrumentation with USRP software radios we successfully demonstrated the general feasibility of distributed adaptive beamforming in realistic settings.
To the best of our knowledge it is the first such instrumentation that utilises up to four independent transmit nodes and also the first that also uses a wireless channel for the receiver feedback.

### Asymptotically optimal algorithm

We have introduced a numeric approach to distributed adaptive beamforming in wireless sensor networks.
The algorithm achieves an asymptotic simulation time of O(n), which means that it is an asymptotically optimal solution.
In mathematical simulations, we could show that the standard global random search approach is in fact outperformed.
Moreover, we have studied the impact of mobility on the synchronization performance of both approaches.
For a random walk model and a linear movement model, both approaches have been compared in mathematical simulations.

The numeric synchronization method allows movement speeds of more than 200 km/h at a distance of about 30 meters.

For obtaining experimental results in near realistic settings, we are currently working on the implementation of both approaches with USRP software radios.

## Publications

- Stephan Sigg, Rayan Merched El Masri and Michael Beigl: Feedback based closed-loop carrier synchronisation: A sharp asymptotic bound, an asymptotically optimal approach, simulations and experiments, in IEEE Transactions on Mobile Computing (TMC), 2011 (DOI)
- Stephan Sigg, Michael Beigl and Behnam Banitalebi: Efficient adaptive communication from resource restricted transmitters, In Organic Computing - A Paradigm Shift for Complex Systems, Christian Mueller-Schloer and Hartmut Schmeck and and Theo Ungerer, Springer, 2011 (Online)
- Stephan Sigg and Michael Beigl: An adaptive protocol for distributed beamforming, in 17. Fachtagung 'Kommunikation in Verteilten Systemen 2011' (KiVS11), 2011 (PDF)
- Behnam Banitalebi, Dawud Gordon, Stephan Sigg, Takashi Miyaki and Michael Beigl: Collaborative Channel Equalization: Analysis and Performance Evaluation of Distributed Aggregation Algorithms in WSNs, in Proceedings of the 8th IEEE International Conference on Mobile Ad-hoc and Sensor Systems (IEEE MASS 2011), 2011 (DOI)
- Behnam Banitalebi, Stephan Sigg and Michael Beigl: Performance analysis of receive collaboration in TDMA-based Wireless Sensor Networks, in Proceedings of the fourth International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (Ubicomm), October 2010 (PDF)
- Behnam Banitalebi, Stephan Sigg and Michael Beigl: On the Feasibility of Receive Collaboration in Wireless Sensor Networks, in Proceedings of the 21st annual IEEE Symposium on Personal, Indoor and Mobile Radio Communications, March 2010 (DOI)
- Rayan Merched El Masri, Stephan Sigg and Michael Beigl: An asymptotically optimal approach to the distributed adaptive transmit beamforming in wireless sensor networks, in Proceedings of the 16th European Wireless Conference, April 2010 (DOI)
- Stephan Sigg, Rayan Merched El Masri and Julian Ristau Michael Beigl: Limitations, performance and instrumentation of closed-loop feedback based distributed adaptive transmit beamforming in WSNs, in Fifth International Conference on Intelligent Sensors, Sensor Networks and Information Processing - Symposium on Adaptive Sensing, Control, and Optimization in Sensor Networks, 2009 (DOI)
- Stephan Sigg and Michael Beigl: Algorithmic approaches to distributed adaptive transmit beamforming, in Fifth International Conference on Intelligent Sensors, Sensor Networks and Information Processing - Symposium on Theoretical and Practical Aspects of Large-scale Wireless Sensor Networks, 2009 (DOI, slides)
- Stephan Sigg and Michael Beigl: Algrithms for closed-loop feedback based distributed adaptive beamforming in wireless sensor networks, in Fifth International Conference on Intelligent Sensors, Sensor Networks and Information Processing - Symposium on Adaptive Sensing, Control, and Optimization in Sensor Networks, 2009 (DOI)
- Stephan Sigg and Michael Beigl: Randomised Collaborative Transmission of Smart Objects, in 2nd International Workshop on Design and Integration Principles for Smart Objects (DIPSO2008) in conjunction with Ubicomp 2008, September 2008 (PDF)