Method For Selecting State Of A Reconfigurable Antenna In A Communication System Via Machine Learning

[0001] The present application is a continuation application of U.S. patent application Ser. No. 14/565,665, filed Dec. 10, 2014, which is, in turn, a continuation application of U.S. patent application Ser. No. 13/606,843, filed Sep. 7, 2012, now U.S. Pat. No. 8,942,659, which claims priority under 35 U.S.C. §119(e) to U.S. Provisional Patent Application No. 61/532,131 filed Sep. 8, 2011. The contents of these patent applications are hereby incorporated by reference in their entireties.

[0002] This invention was made with government support under Grant No. 0916480 awarded by the National Science Foundation. The government has certain rights in the invention.

[0003] The present invention relates generally to the field of multi-element antenna systems. Specifically, the present invention relates to methods for efficiently using multi-element reconfigurable antennas in MIMO systems.

[0004] In recent years, studies have shown that reconfigurable antennas can offer additional performance gains in Multiple Input Multiple Output (MIMO) systems by increasing the channel capacity, diversity order and even have been shown to perform well in the low SNR regimes. These reconfigurable antennas are capable of generating multiple uncorrelated channel realizations by changing their electrical and radiation properties and are gradually making their way into commercial wireless systems. The key to effectively utilizing the reconfigurability offered by these antennas is to select a state that provides improvement in received SNR, throughput or channel capacity (referred to as “optimal state” herein) among all the states for a given wireless environment.

[0005] Reconfigurable antennas can be employed either at the transmitter or the receiver, or at both ends of the RF chain. This flexibility can create a large search space in order to find an optimal state for communication. The key bottleneck to exploit the full potential of reconfigurable antennas is the requirement of additional training to obtain the channel state information corresponding to each beam pattern and/or the combination thereof at the receiver and transmitter. Moreover, the effect of node mobility to a different location, changes in physical antenna orientation, and the dynamic nature of the wireless channel can render previously found “optimal” states suboptimal over time. This makes it important for a wireless system to employ a learning algorithm to find the new optimal states and to maintain the highest possible SNR.

[0006] In order to be effective, an online learning algorithm for antenna state selection (also referred to herein interchangeably as “selection technique”) must overcome certain challenges, including:

[0007] 1) Optimal antenna state for each wireless link (between a single transmitter and a receiver location) is unknown a priori. Moreover, each wireless link may have a different optimal state. A selection technique should be able to learn and find the optimal state for a given link.

[0008] 2) For a given wireless link, there might be several states which are near optimal over time, based on channel conditions and multi-path propagation. A selection technique should provide a policy to balance between exploiting a known successful state and exploring other available states to account for dynamic behavior of the channel.

[0009] 3) For the purpose of real-time implementation in a practical wireless system, a selection technique must employ simple metrics that can be extracted from the channel without large overhead or requiring extensive feedback data.

[0010] 4) The selection technique should require reduced training or reduced channel state information to keep the overhead low in a practical wireless system.

[0011] Previous work related to state selection is based on estimating channel response of each antenna state which required changing the standard OFDM frame format. However, as the number of states increases, the scheme becomes impractical. See, e.g., A. Grau, H. Jafarkhani, and F. De Flavis, “A reconfigurable multiple-input multiple-output communication system,” IEEE Transactions on Wireless Communications, vol. 7, no. 5, pp. 1719-1733, 2008. Selection techniques using second order channel statistics and average SNR information have also been proposed by D. Piazza, M. D'Amico, and K. Dandekar in “Performance improvement of a wideband MIMO system by using two-port RLWA,” Antennas and Wireless Propagation Letters, IEEE, vol. 8, pp. 830-834, 2009. Further H. Eslami, C. Sukumar, D. Rodrigo, S. Mopidevi, A. Eltawil, L. Jofre, and B. Cetiner, proposed training schemes with reduced overhead and compared these to exhaustive search techniques in “Reduced overhead training for multi reconfigurable antennas with beam-tilting capability,” IEEE Transactions on Wireless Communications, vol. 9, pp. 3810-3821, 2010. Though some of these techniques were successful in showing the benefits of multi-state selection and motivated the need for a selection algorithm, none solved the challenges mentioned above and were not truly adaptive in operation and required additional parameter tuning to perform optimally. Previous work in learning for cognitive radios has primarily been focused on link adaptation. See, e.g., R. Daniels, C. Caramanis, and R. Heath, “Adaptation in convolutionally coded MIMO-OFDM wireless systems through supervised learning and SNR ordering,” IEEE Transaction on Vehicular Technology, vol. 59, no. 1, pp. 114-126, 2010, and S. Yun and C. Caramanis, “Reinforcement learning for link adaptation in MIMO-OFDM wireless systems,” in GLOBECOM 2010, 2010 IEEE Global Telecommunications Conference, December 2010, pp. 1-5 and channel allocation for dynamic spectrum access in Y. Gai, B. Krishnamachari, and R. Jain, “Learning multi-user channel allocations in cognitive radio networks: a combinatorial multi-armed bandit formulation,” in 2010 IEEE Symposium on New Frontiers in Dynamic Spectrum, IEEE, 2010, pp. 1-9.

[0012] It is desired to develop learning algorithms for antenna state selection to address the above challenges to improve the performance of wireless systems and to investigate the feasibility of implementing such algorithms in a practical wireless system. The present invention addresses these needs in the art.

[0013] The present invention addresses the above-mentioned challenges in the art by formulating the antenna state selection as a multi-armed bandit problem. The multi-armed bandit problem described by T. L. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” Advances in Applied Mathematics, vol. 6, no. 1, pp. 4-22, 1985; V. Anantharam, P. Varaiya, and J. Walrand, “Asymptotically efficient allocation rules for the multi-armed bandit problem with multiple plays-part I: I.I.D rewards,” IEEE Transactions on Automatic Control, vol. 32, no. 11, pp. 968-976, 1987; and P. Auer, N. Cesa-Bianchi, and P. Fischer, “Finite-time analysis of the multi-armed bandit problem,” Machine learning, vol. 47, no. 2, pp. 235-256, 2002, is a fundamental mathematical framework for learning unknown variables. In its classic form, there are N independent arms with a single player playing arm i (i=1, . . . N). Each play of a single arm yields random rewards which are i.i.d with a distribution of unknown mean. The goal is to design a policy to play one arm at each time sequentially to maximize the total expected reward in the long run. T. L. Lai and H. Robbins in “Asymptotically efficient adaptive allocation rules,” Advances in Applied Mathematics, vol. 6, no. 1, pp. 4-22, 1985, studied the non-Bayesian formulation and provided a performance measure of an arm selection policy referred to as regret or cost of learning. Regret is defined as the difference in the expected reward gained by always selecting the optimal choice and the reward obtained by a given policy. Since the best arm cannot always be identified in most cases using a finite number of prior observations, the player will always have to keep learning and the regret will grow over time. Then, the regret of a policy after n selections is given by:

${\mu }^{*}n-{\mu }_i\sum _{i=1}^NE\left[T_i\left(n\right)\right]$

where:

μ*=max_1≦i≦Nμ_i

[0014] μ* is the average reward for the optimal arm, μ_i is the average reward for arm i, n is number of total trials, E[•] is the expectation operator and T_i is the number of times arm i has been sampled. It has been shown by Lai and Robbins that the minimum rate at which regret grows is of logarithmic order under certain regularity conditions. The algorithm of the invention processes the received data to select the antenna state that minimizes the regret over time.

[0015] In accordance with an exemplary embodiment, the method of selecting an antenna state for a multi-element reconfigurable transmitter and/or receiver antenna (e.g., a type of reconfigurable leaky wave antenna) in accordance with the invention includes the steps of providing a learning algorithm that optimizes a wireless link between at least one reconfigurable transmitter antenna and at least one reconfigurable receiver antenna over time over different antenna array states and setting the antenna state for the transmitter and/or a receiver antenna based at least in part on the antenna states determined by the learning algorithm to lead to an optimized wireless link between the at least one reconfigurable transmitter antenna and the at least one reconfigurable receiver antenna over time. In an illustrated embodiment, the learning algorithm formulates selection of an antenna as a multi-armed bandit problem for learning the wireless channel conditions of the wireless link so as to maximize the wireless link between the at least one reconfigurable transmitter antenna and the at least one reconfigurable receiver antenna over time. In this exemplary embodiment, the learning algorithm implements an arm selection policy referred to as regret defined as the difference in an expected reward gained by always selecting a path with an optimal wireless link and a path that leads to an optimized wireless link over time. The learning algorithm processes the received data to select the antenna array configuration that minimizes the regret over time. Thus, the transmission data is first collected and then later processed through the learning algorithm to benchmark performance. When the data is replayed on the computer implementing the learning algorithm, the learning algorithm is used to continuously make decisions until all of the data is processed. When this selection technique is deployed on a live wireless device and live transmission data is transmitted, the learning algorithm is active at every transmission and selects the state of the antenna system per transmission or per data packet. Whether the live data transmission is emulated or actual live data is sent through the wireless device, the techniques of the invention will always be active and will make sequential decisions. The wireless link is optimized by optimizing signal to noise ratio, channel capacity, or link throughput.

[0016] The proposed method is adaptive in nature and can adapt to changes in wireless channel conditions, wireless node mobility and antenna orientation. The proposed method also is less computationally intensive and has low feedback requirements for practical implementation.

[0023] A detailed description of illustrative embodiments of the present invention will now follow with reference to FIGS. 1-6. Although this description provides a detailed example of possible implementations of the present invention, it should be noted that these details are intended to be exemplary and in no way delimit the scope of the invention.

[0024] The methods described herein are influenced by the work done by P. Auer, N. Cesa-Bianchi, and P. Fischer as reported in “Finite-time analysis of the multi-armed bandit problem,” Machine learning, vol. 47, no. 2, pp. 235-256, 2002, where arms have non-negative rewards that are i.i.d over time with an arbitrary unparameterized distribution. The setup is considered where there is a single transmitter and M wireless receiver nodes and both the transmitter and the receivers employ the reconfigurable antennas. The transmitter has a fixed antenna state and the receivers can select from N available antenna states. This reduces the problem to selecting an antenna state only at the receiver end where each receiver can select state i independently. The decision is made at every packet reception n to select the state to be used for the next reception. If a receiver node selects a state i and it is assumed that the transmission is successful, a random reward is achieved which can be denoted as R_i (n). Without loss of generality, R_i (n) is normalized as R_i (n) ε[0, 1]. When a receiver selects a state i, the value of R_i (n) is only observed by that receiver and the decision is made only based on locally observed history.

[0025] The selection technique described herein is based on the deterministic policy UCB1 given by Auer, Cesa-Bianchi, and Fischer. To implement this policy, the average of all the reward values observed for state i up to the current packet n denoted as R_i (n) and the number of times state i has been played, n_i (n) are stored. The UCB1 policy is shown below as Algorithm I.

Algorithm 1 UCB1 Policy (P. Auer, N. Cesa-Bianchi, and P. Fischer,
“Finite-time analysis of the multi-armed bandit problem,” Machine learning,
vol. 47, no. 2, pp. 235-256, 2002)
	// Initialization
	ni, Ri ← 0
	Play each arm at least once and update ni, Ri accordingly.
	// Main Loop
	while 1 do
	Play arm i that maximizes
	R _ i + 2  ln  ( n ) n i	(1)
	Update ni, Ri for arm i
	end while

[0026] The ε-GREEDY policy is also implemented, which is a randomized policy, and the UCB1-Tuned policy of Auer, Cesa-Bianchi, and Fischer is implemented, which has been shown to work better for practical purposes. In the ε-GREEDY policy, the arm with current highest average is selected with probability 1−ε and a random arm is selected with probability ε. UCB1-Tuned is a fine tuned version of UCB1 policy which accounts for the variance measured independently across arms. In this policy, the upper confidence bound of UCB1 policy is replaced by:

$\begin{array}{cc}\sqrt{\frac{\ln \left(n\right)}{n_t}\min \left\{\frac{1}{4},V_i\left(n_t\right)\right\}}& \left(2\right)\end{array}$

where V_i is defined as:

$\begin{array}{cc}{V}_i\left(s\right)\equiv \left(\frac{1}{s}\sum R_{\mathrm{is}}^2\right)-R_{\mathrm{is}}^2+\sqrt{\frac{2\ln \left(t\right)}{s}}& \left(3\right)\end{array}$

when arm i has been played s times during the first t plays. Another variant of UCB1 policy known as UCB1-Normal is also implemented where it is assumed that the rewards are drawn from a normal distribution. The UCB1-Normal policy proposed in Auer, Cesa-Bianchi, and Fischer is given as Algorithm 2 below.

Algorithm 2 UCB1-Normal Policy (P. Auer, N. Cesa-Bianchi, and P. Fischer,
“Finite-time analysis of the multi-armed bandit problem,” Machine learning,
vol. 47, no. 2, pp. 235-256, 2002)
	// Initialization
	ni, Ri ← 0
	// Main Loop
	while 1 do
	Play the machine which has been played less than 8logn times
	Otherwise, play arm i that maximizes
	R _ i + 16  q i - n i  R i 2 n i - 1  ln  ( n - 1 ) n i	(4)
	Update ni, Ri for arm i
	end while

where q_i is the sum of squared rewards for arm i.

[0027] We compare the proposed multi-armed bandit algorithms with periodic training scheme which requires exhaustive search to acquire channel state information corresponding to each antenna state. In the periodic training scheme of an exemplary embodiment, each receiver goes through a training phase where each antenna state is activated in sequence by a processor implementing the ESPT scheme and the reward from each transmission is stored in an associated memory. The amount of training is defined by the training period T. Once, the training phase is over, the receiver selects the state with maximum average during the training phase and continues receiving on that state. The training is repeated every F packets, which is defined as the frequency of the training This can be viewed as the process of consecutive exploration and exploitation, except that the duration of the exploration and exploitation is fixed and exploration occurs across all the states.

[0028] The Reconfigurable Leaky Wave Antenna (RLWA) is a two port antenna array designed to electronically steer two highly directional independent beams over a wide angular range. Initially proposed by the authors in D. Piazza, D. Michele, and K. Dandekar, “Two port reconfigurable CRLH leaky wave antenna with improved impedance matching and beam tuning,” in 3^rd European Conference on Antennas and Propagation, 2009, EuCAP 2009, IEEE, 2009, pp. 2046-2049, the embodiment shown in FIG. 1 is a composite right/left-handed leaky wave antenna composed of 25 cascaded metamaterial unit cells. See also, D. Piazza, M. D'Amico, and K. Dandekar, “Performance improvement of a wideband MIMO system by using two-port RLWA,” Antennas and Wireless Propagation Letters, IEEE, vol. 8, pp. 830-834, 2009. Moreover, the application of various combinations of bias voltages “S” and “SH” controls the beam direction allowing for symmetrical steering of the two radiation beams at the two ports over a 140° range.

[0029] In order to characterize the effect of beam direction on the efficacy of a wireless system with RLWAs deployed at both ends of a link, a subset of states was selected to allow the beam to steer over a range of 140° in the elevation plane. FIG. 2 shows the measured radiation patterns for the selected states for port 1 and their corresponding bias voltages (Gain ˜−3 dB).

[0030] In their experiments, the inventors used the Wireless Open Access Research Platform (WARP), an FPGA-based software defined radio testbed, and WARPLab, the software development environment used to control WARP nodes from MATLAB Rice University WARP project. http://warp.rice.edu. Four WARP nodes were distributed throughout the fifth floor of the Drexel University Bossone Research Center as shown in FIG. 4. By using WARPLab, each of the nodes were centrally controlled to allow for the synchronization of the transmission and reception process and to provide control over the antenna state selected at each of the nodes. Although the nodes were controlled centrally for data collection purposes, the learning algorithm was decentralized. Specifically, no information during the learning process was shared with the transmitter. Those skilled in the art will appreciate that the WARPLab software development environment may be replaced in exemplary practical embodiments by a central processor (not shown) or a processor connected to each antenna at each transmitter/receiver (not shown) programmed to control the system nodes and to control the antenna state selected at each of the nodes in accordance with one or more of the machine learning algorithms described above. Also, a memory (not shown) associated with the central processor or with each processor associated with an antenna may be used to store the received transmission and reception data for processing by the selected machine learning algorithm.

[0031] The performance of the RLWA was evaluated in a 2×2 MIMO system with spatial multiplexing as the transmission technique. For baseline measurements, each designated WARP node transmitter broadcasted packets modulated using BPSK. For each packet transmission, the receiver nodes stored channel estimates in memory and measured the post-processing signal-to-noise ratio (PPSNR) by evaluating the error vector magnitude (EVM) of the received symbol constellations. EVM is defined as the inverse of the squared symbol estimation error. Furthermore, the antenna states for each node were switched after each packet until all 5 possible antenna states between the transmitter and receivers were tested. This process was repeated until 200 realizations were achieved for all state combinations and for each node acting as a transmitter. The beam directions in FIG. 4 correspond to the optimal state selected most often at each of the receivers when node 4 was transmitting. The algorithm described above is an online algorithm but the collected channel realizations were used corresponding to each state and the algorithm was evaluated in post-processing. This is important in order to benchmark the performance of different policies under the same channel conditions and to make sure that channel conditions do not bias the performance results.

[0032] The results for three multi-armed bandit policies (UCB1, UCB1-Tuned, ε-GREEDY) are presented in FIG. 3 verifying the empirical performance of the selection technique. Each sub-figure represents the average reward achieved by all three policies for a given wireless link over 200 packets. The upper bound is defined as the reward obtained by a genie which always selected the optimal state with perfect channel knowledge of all antenna states. For most of the links in FIG. 3, it was found that both UCB1-Normal and UCB1-Tuned outperformed the other policies. UCB1-Tuned has been found to work better for practical purposes since it is not sensitive to the variance of the states. Also, ε-GREEDY did not perform well because ε-GREEDY explores uniformly over all states and can select sub-optimal states more often, thereby reducing the average reward. It is evident from the figure that among three instances of ε-GREEDY policy, the instance with highest ε performed the worst. However, were mobile users considered in this experiment, it is possible that ε-GREEDY policy will adapt better to substantial variations in channel condition. As, mentioned in above, one of the major drawbacks of the periodic training with exhaustive search is that the optimal training period (T) and training frequency (F) is not known a priori for each link and it is challenging to vary those parameters in the case of node mobility and high channel variability. It is observed that in the case of static receivers, by varying the T and F, performance of the exhaustive scheme is significantly affected. As the training period is reduced and training frequency is increased, sub-optimal states are used more often which reduces the average reward in the long run. It can also be seen that the exhaustive scheme with higher training period and higher frequency converges faster, but has overall reduced performance in the beginning These results show that the ability of MAB policies to work as hands-off, semi-blind techniques without requiring parameter tuning

[0033] It is desired to find the optimal policy which can minimize the regret over time and provide logarithmic rate of growth of regret over time. In FIG. 5, the normalized regret is shown for all multi-armed bandit policies and also the exhaustive and random scheme. P. Auer, N. Cesa-Bianchi, and P. Fischer proved that the regret for UCB1, UCB1-Tuned, UCB1-Normal grows logarithmically in time. The ε-GREEDY policy yields regret that is linear in time. Since, there are random policies, the regret is averaged over 200 runs, each run with 200 sequential trials for the random policies. It can be seen that the regret of all multi-armed bandit policies have very low regret as compared to the ESPT and Random selection policies. UCB1-Tuned has the least regret among the multi-armed bandit policies. FIG. 6 further shows the empirical CDF of Post-Processing SNR averaged across all links for both multi-armed bandit and heuristic policies.

[0034] The above techniques were applied to methods of selecting an antenna array state for a multi-element reconfigurable transmitter and/or receiver antenna by providing a learning algorithm such as that described above that optimizes wireless channel conditions of possible signal paths between at least one reconfigurable transmitter antenna and at least one reconfigurable receiver antenna over time over different antenna array states of the at least one reconfigurable transmitter antenna and the at least one reconfigurable receiver antenna. The antenna array states for the transmitter and/or a receiver antenna is then set based at least in part on the antenna array states determined by the learning algorithm to lead to optimized wireless channel conditions between the at least one reconfigurable transmitter antenna and the at least one reconfigurable receiver antenna over time. For example, the learning algorithm may formulate selection of an antenna array state as a multi-armed bandit problem for learning the wireless channel conditions of the possible signal paths so as to maximize wireless channel conditions between the at least one reconfigurable transmitter antenna and the at least one reconfigurable receiver antenna over time. The learning algorithm may further implement an arm selection policy to minimize regret (defined as the difference in an expected reward gained by always selecting a path with an optimal wireless channel condition and a path that leads to an optimized wireless channel condition over time). The learning algorithm processes the received data to select the antenna array state that minimizes the regret.

[0035] The methods of the invention thus incorporate a learning algorithm for antenna state selection that it is practical for use in wireless systems employing reconfigurable antennas. It has been shown empirically that the multi-armed bandit problem is a useful online learning framework for antenna state selection in a practical wireless system. For a network of four nodes employing reconfigurable antennas equipped with five states, the learning algorithm improves the received PPSNR and thereby improves the achievable throughput of the system.

[0036] While the invention has been described with reference to specific embodiments, the description is illustrative of the invention and is not to be construed as limiting the invention. Various modifications and applications may occur to those skilled in the art without departing from the spirit and scope of the invention as defined by the appended claims. For example, the methods described herein may be used in a training mode for a wireless transmission system or during an operational mode where live data is transmitted to select antenna states and configurations in real-time or near real-time.

[0037] Therefore, it must be understood that the illustrated embodiment has been set forth only for the purposes of example and that it should not be taken as limiting the invention as defined by the following claims. For example, notwithstanding the fact that the elements of a claim are set forth below in a certain combination, it must be expressly understood that the invention includes other combinations of fewer, more, or different elements, which are disclosed above even when not initially claimed in such combinations. A teaching that two elements are combined in a claimed combination is further to be understood as also allowing for a claimed combination in which the two elements are not combined with each other, but may be used alone or combined in other combinations. The excision of any disclosed element of the invention is explicitly contemplated as within the scope of the invention.

[0038] The words used in this specification to describe the invention and its various embodiments are to be understood not only in the sense of their commonly defined meanings, but to include by special definition in this specification structure, material or acts beyond the scope of the commonly defined meanings. Thus, if an element can be understood in the context of this specification as including more than one meaning, then its use in a claim must be understood as being generic to all possible meanings supported by the specification and by the word itself.

[0039] The definitions of the words or elements of the following claims are, therefore, defined in this specification to include not only the combination of elements which are literally set forth, but all equivalent structure, material or acts for performing substantially the same function in substantially the same way to obtain substantially the same result. In this sense, it is therefore contemplated that an equivalent substitution of two or more elements may be made for any one of the elements in the claims below or that a single element may be substituted for two or more elements in a claim. Although elements may be described above as acting in certain combinations and even initially claimed as such, it is to be expressly understood that one or more elements from a claimed combination can in some cases be excised from the combination and that the claimed combination may be directed to a subcombination or variation of a subcombination.

[0040] Insubstantial changes from the claimed subject matter as viewed by a person with ordinary skill in the art, now known or later devised, are expressly contemplated as being equivalently within the scope of the claims. For example, while the method of the invention is described for use with reconfigurable leaky wave antennas (RLWAs), those skilled in the art will appreciate that the claimed methods may be used with other types of reconfigurable antennas as well. Therefore, obvious substitutions now or later known to one with ordinary skill in the art are defined to be within the scope of the defined elements.