802.11 AD Search and Track
1.0 Technical Problem
The large amount of wireless devices that connect to the Internet has caused congestion on the 802.11 a/b/g/n/ac standard 2.4Ghz and 5Ghz spectrums. In order to help alleviate this, the next generation 802.11 ad standards use the 60Ghz spectrum. While there is available bandwidth at these higher frequencies, these signals suffer from greater attenuation which limits the usable transmit range. One way to address this range limit is to use directional antennas, or beamforming, to create a high power, focused signal that has an increased range. This scheme works fine so long as you can locate and track connecting devices. Our final project aims to address this problem and implement a search, locate, and tracking protocol for 802.11 ad.
2.0 Related Work
2.1 802.11 AD Protocol
In this section, we introduce the procedure in IEEE 802.11ad standard for beamforming. The protocol suggests a three step beamforming training procedure. These steps can be summarized in figure 1.
In the first step one Antenna transmits in different directions with the other set up as an omnidirectional antenna. In the next step, the roles are reversed. Once these two steps are complete each antenna has an idea of the environment it is in. Each antenna will determine n number of best directions to point. In step 3, the system tests all n^2 pairs of directions. Once step 3 is complete the antennas will lock on their optimal direction. The protocol suggests that the antennas should stay locked into this direction until the signal strength drops. Once the signal has degraded the protocol restarts the three step Search.
2.2 Efficient Codebook-Based MIMO Beamforming for Millimeter-Wave WLANs [2]
This paper published by Fujitsu Laboratories outlines a protocol used to find the optimal beam direction for a 60 Ghz wave. They mention that the large number of tests run by the 802.11 ad protocol results in large overhead and a large amount of training data. They propose a solution that balances complexity and high-performance.
It works using a matrix referred to as the codebook. A codebook is a matrix where each column specifies the antenna weight vector (AWV) with a beam direction. The 802.15.3c are given as:
w(m,n) = jfix[(m*mod(n+N/2,N)) / (N/4)], m=0,...,M-1; n=0,.....,N-1.
This works well when testing 90 degree intervals. But, once M or N become greater than 4 the output leads to high gain loss in the signal. This paper suggests a new codebook matrix with the formula:
w(m,n) = 1/M e-2(m-1)(n-1)/N, m=1,....,M; n=1,....,N.
This new solution is a more efficient (less overhead) solution for determining the optimal angle to point the beam.
3.0 Solution
The final implementation used can be divided into two categories: Search and Tracking. Search is used to describe the transition from knowing nothing about the environment to finding the current optimal direction. Tracking describes the process of maintaining the best direction for sending data. To understand the final solution we will first describe the hardware used in the system, follow that with a description of the Search algorithm. Lastly, we will describe the Tracking solution we used.
3.1 Hardware
In order to completely understand the project some knowledge of the available hardware is needed. The setup consists of two horn antennas, an RX and a TX antenna. Each antenna is connected to a 24 Ghz signal chain. The transmitted 24 Ghz signal that is sent through the air is created by mixing a 27Ghz signal, created by a PLL, and a 3 Ghz signal created in software on a USRP. Once the 24Ghz signal is received by the RX chain, it is down converted to 3 Ghz and sampled by the USRP into Matlab. In matlab we are able to analyze the data we received. Each horn antenna sits on a rotating motor that is driven by an Arduino. This will allow us to rotate the horn antennas 360 degrees so that they can find each other.
3.2 Search
The term Search is used in this report to describe the initial discovery of the first optimal directions to point the antennas. This state begins with no information about the environment. The goal is to find the optimal direction to point the TX and RX antennas for data transfer. SNR is used as a heuristic to determine the quality of the channel at the current direction. Several different approaches were tested to determine the initial optimal direction. The approaches were evaluated based on SNR and the speed to complete the process.
The final implementation used to Search for the best current directions involves partitioning the range of TX degrees into 30 degrees slices. During each step, we cycle the TX antenna into the next 30 degree slice and then sweep the RX antenna over the full range. After a measurement is made in each of the 30 degree slices, the antennas rotate back to the location that had the highest SNR. This approach is advantageous because the horn antennas used have high gain over a 30 degree range. (About -4dB difference between 0 degrees and +/- 15 degrees.) This means that the SNR generally does not drop greatly in the range of 30 degrees. There are some obvious flaws with this logic such as the instance when your antenna is completely out of phase with your measurement locations. This can mask the largest peak. The tests found that this was a fairly good approximation for a starting position. The Tracking algorithm, that begins to run when the Search is over, is designed to handle the smaller changes in angle.
Once the antennas have found a direction to point, we move into the Tracking State. The goal of the Tracking state is to maintain the antennas in the best direction. The way the Tracking works is that the TX and RX antennas alternate sweeping 60 degrees looking for better channels. To describe that more concretely, the first step is to sweep RX from 30 degrees less than its current position to 30 degrees greater than that current position. RX then back tracks to the location with the highest SNR. Once RX has locked in, then TX begins the same process by rotating 60 degrees and locking into the direction with the highest SNR. The benefits of this constant small rotation is that we can update quickly to environmental changes while only give us minor reductions in throughput. This seemed to work well for several reasons. The first is because of the bell-shaped curve of the horn antennas gain we can see when we are approaching the optimal direction because of the rise in SNR and amplitude. Also the width of the Gain curve gives us some room for error when deciding the best direction.
3.3 Modifications to Tracking for Final Implementation
The final implementation of the system has two modifications to the simple “Search then Track” solution described above. The first modification is that during the Tracking stage if the system notices that the channel has suddenly dropped significantly then it will rerun the Search code. This case covers the instance where your channel isn’t shifting but instead suddenly greatly degrades. This could happen if something suddenly blocks the two antennas. In our demo we use this state change to display the multipath capabilities of this system. Our Search locks into a position where the antennas face each other. When I obstruct the direct path of the antennas, it restarts the Search algorithm.
The second modification we made is adding a five minute timer to the Tracking code. Every 5 minutes we restart the Searching code. This timer accounts for the instances where a new better channel has become available but it is outside the 60 degree range seen by the Tracking algorithm.
4.0 Evaluation Method and Results
The overall goal of the project is to locate and track a device efficiently. With this in mind, we based the effectiveness of the Search and Track a little differently from each other. An effective Search algorithm is one that quickly finds the best direction but also covers the largest percentage of combinations in directions. For the Tracking algorithm speed and accuracy were the largest factors in determining effectiveness.
4.1 Search
As mentioned above, the Search algorithm’s effectiveness was based partly on speed but more heavily on its ability to scan the entire space and find the true optimal position. An effective Search algorithm for this purpose is one that excludes the minimum number of options from the sample space it measures. We implemented and analyzed three Searching Techniques before settling on the one we believed was most precise. This section will provide an overview of the three techniques with a brief analysis of the results we discovered.
4.1.1 Initial Search- Exhaustive Search
Our initial implementation for Searching was an exhaustive search. It sampled every combination of points, with resolution of 1 degree, between TX and RX. This as you can imagine was a very slow process but it was a good starting point for building up our project and becoming familiar with the hardware and the cycle of information.
One of our main issues was that we had antenna movement and data collection as two separate actions. This was causing us a large amount of delay in between each step. To be more concrete our first search algorithm took
t = n2 *tu
n = number of steps, tu=USRP reset time
to collect all the necessary data, where n is the number of steps and t_u is the 5 second setup time for the USRPs. The USRP setup time is not something we have the ability to reduce. This means that for measuring only 6 positions with each antenna (36 pairs of directions) it would take:
62*5 = 180 seconds
Using the same equation we see that a 180 degree sweep with 10 degree resolution would take:
182*5 = 1620 seconds
Although theoretically this method of Searching could ensure that every option is sampled, it is way too time intensive for our application. The following two algorithms we tested sacrifice small amounts of resolution for large speed boosts.
4.1.2 Synchronizing the Motor Controller and the USRP
Upon analyzing the initial implementation it was clear that the largest crutch was the 5 second delay that the USRP needed to begin resampling data. With that in mind, the goal for the updated Search was to reduce the number of times the USRP restarted collecting data. The way that number was reduced in this implementation was by synchronizing the motor controller and the USRP’s data collecting process. This can be accomplished by running the motor control and USRP control from the same terminal in Matlab. With this synchronization we can simply sweep the antenna over a range while collecting data. From there we can map the sample numbers to the angles and find which angle has the best signal. Once we have the optimal angle we can sweep backwards to that point. This dramatically reduces the time we need to Search before the antennas find each other.
Upon analyzing the first trials using the synchronized system, we discovered that the motor’s speed was our limiting factor as far as speed of completing any kind of Searching method. The motor’s initial code ran a 180 degree sweep in 10 seconds. In an effort to reduce that time we edited the Arduino code and reduced the 180 degree sweep time to 3.1 seconds. This 69% reduction in time gave us the speed we needed to begin developing solutions for Searching.
4.1.3 Updated Search- Alternating TX and RX sweeps
The first implementation idea with this synchronized setup was one that involved alternating between moving the TX and RX antennas. It worked as follows: The first step was to sweep the RX antenna over the whole range of degrees and then have it rotate back to the location it saw the best SNR. Then the TX antenna would rotate over the full range and move back to its optimal direction. That two step process would continue repeating until the change in degrees between the previous state and the new state became less than 5 degrees. This was a huge improvement over the previous solution because each step only took about 4 seconds to complete.
This solution seemed to work effectively in our controlled environment. The gain of the horn antenna was large in directions that a large enough range of degrees that most trial runs converged in about 6 iterations. To compare the speed of 6 iterations of the solution to the previous solution, the time it took to converge is:
t = 2*(ts+tc+tu)*n
ts = sweep time, tc = computation time, n = number of iterations, tu=USRP start time
For a 180 degree sweep that takes 6 iterations to converge the time becomes approximately:
t = 2*(3.1+1.5+5)*6= 116.2 seconds
This is a great improvement from the previous solution. The main issue with this solution is that the number of iterations the system takes to converge is heavily dependent on the starting positions of the antennas. If one antenna was within 15 degrees of its optimal direction then the process can converge in one step. But if at the start one antenna is facing completely away from the other antenna it will take the algorithm much more than 6 iterations to converge because the sweeping antenna would not even see other antenna. Without any walls for multipath there is a possibility that this solution never converges. In our environment we were able to use the multipath to our advantage because we could see effects of the antenna without being directly pointed at the other antenna.
4.1.4 Final Search- Divide and Search
The final search algorithm we explored is one that reduced this dependence on the starting position while preserving the degree of magnitude in time of completion. The way it works is that in every step the TX antenna is rotated by 30 degrees while the RX antenna is being rotated 180 degrees. Thirty degree was chosen because of the width of the horn antennas gain. This process iterates until the TX antenna has covered the sample space you require. For our tests and demos we positioned the antennas such that it was only necessary to sweep the antennas 180 degrees. But the same ideas can be extended to a 360 degree space.
With 180 degree space this algorithm needs 6 iterations to discover the optimal direction. This means our new algorithm is only limited by the amount of time it takes the motor to rotate.
t = 6*(ts + tc+ tu)
ts = sweep time, tc=computation time, tu=USRP start time
With our optimized motor speed we are able to complete this Search in:
t = 6*(3.1+1.5+5) = 48 seconds
With this increase in speed and range we decided this would be a good solution for Searching.
4.2 Tracking
Tracking starts when the Search has found an optimal direction. In terms of the demo, the Tracking begins with the antennas almost perfectly facing each other. The Tracking algorithm was evaluated in a manner that is a little different from the Search. For the Tracking algorithm speed and accuracy were the largest factors in determining effectiveness. An effective Tracking solution is able to sense any changes in the environment and quickly respond to them. Our ideal solution would not lose much throughput while it is searching for new directions. We implemented two algorithms for tracking. This section will describe the two methods and analyze their advantages and disadvantages.
4.2.1 Initial Tracking- Constant Update
We began by implementing a rudimentary tracking algorithm. Our initial thought was to have a system that is always updating its initial position. It does this in three steps. We refer to the starting position of the antenna as the “0 degree” position. The algorithm we implemented measured 9 different positions. It first rotates the TX antenna to -10 degrees and measures the SNR with the RX antenna at -10, 0 and 10 degrees. It then repeats that two more times with the TX antenna at 0 and 10 degrees. The idea was the using these 9 measurement points, the antenna could update itself to reflect small changes in the channel. The hope was that if the antenna moved away slow enough, the antenna could update itself fast enough to follow it.
The implementation suffered from because of several factors. Most importantly the change in gain in the region covered was not big enough to accurately predict the optimal direction. Measuring only 3 points in a 20 degree span left room for a lot of miscalculation. When left to run multiple iterations, the Tracking algorithm never truly converged to a value. It was very susceptible to the noise in the system because, with only 3 measurements per TX position, if one was unusually big the Tracking was greatly thrown off. Another reason it did not work as well as we had hoped was the amount of time it took. The expectation was the be able to update faster than any movement in the environment. But, the cycle took a lot longer to complete than any reasonable change in the channel. To put it in perspective the duration of this Tracking algorithm can be expressed as:
t = 9*(ts+tc+tu)
ts = sweep time, tc=computation time, tu=USRP start time
For our implementation that evaluates to:
t = 9*(1/6 + 1/12 + 5) = approx. 48 seconds
This update time is way too slow for any reasonable change in the environment.
4.2.2 Updated Tracking- Alternating TX and RX 60 degree sweeps
The tracking algorithm we settled on using as our final solution is one that integrates ideas we had for Search algorithms with optimizations that come from the properties of the devices used in our system.
Tracking begins as the Search algorithm ends. In this state the antennas are nearly directly pointed at each other. The way the Tracking is implemented can be described in two steps. In the first step the RX antenna rotates from -30 degrees to 30 degrees with the TX antenna static. It then rotates back to the position where it saw the highest SNR. In the second step the TX antenna rotates from -30 to 30 degrees with the RX antenna static and then rotates back to the best position. This process repeats so that the system can respond to any environmental changes. This system is effective and determining changes that are within the +/- 30 degree range because, due to the Search, we can guarantee that the initial state of the antennas is somewhere where we can see the signal. It is also a fast iteration cycle, only one cycle needs to occur to begin responding to a change. The duration per iteration can be evaluated as:
t <= (ts+tc+tu)
ts = sweep time, tc=computation time, tu=USRP start time
For this solution:
t <= (1.03+0.5+5) = 6.5 seconds
This 6.5 seconds represents an upper bound to the reaction time because the environment can certainly be changing during the 5 second time it takes to start up the USRP. Which means it can react as fast as 1.53 seconds after the change in the environment.
5.0 Conclusion
In this project we implemented part of the 802.11 AD protocol for next generation wireless networks. 802.11 AD uses 60 GHz signals in an uncongested spectrum. While these high frequency waveforms provide higher data rates relative to 2.4 GHz and 5 GHz, they attenuate more quickly. Directional antennas or beamforming antenna arrays are used to address the impact on signal strength and range. However, these directional systems require the ability to search and track connecting devices. We used a directional horn antennas on stepper motors to mimic beamforming from an antenna array. We tested different search algorithms and tracking strategies on this platform. Ultimately we have implemented a quick coarse search followed by a finer tracking step before locking on for data transmission. While in this locked on state, the protocol constantly monitors the signal strength. If it senses a decrease in signal strength to below 80%, a local search or tracking strategy is employed to lock on to the device. If it senses a decrease in signal strength to below 55%, the coarse search algorithm is run followed by the finer tracking step to re localize. This implementation is modular to allow for the mechanical system to be replaced by alternatives such as beamforming patch antenna arrays. This project has developed a platform to further develop and test implementations of 802.11 AD.