DAWN: Directional Antenna Based Wi-Fi Networks

Project Overview

Wireless networks employing directional antennas are expected to proliferate. In this project, we are studying a variety of resource provisioning issues that arise in such networks. Given a set of subscribers and one or more access points possessing directional antennas, we formalize the problem of orienting these antennas in two fundamental settings: (i) subscriber-centric, where the objective is to fairly allocate bandwidth among the subscribers and (ii) provider-centric, where the objective is to maximize the revenue generated by satisfying the bandwidth requirements of subscribers.

For both the problems, we first design algorithms for the case of single access point working under the assumption that the number of antennas does not exceed the number of non-interfering channels. Using the well-regarded lexicographic maxmin fair allocation as the objective for a subscriber-centric network, we present an optimum dynamic programming algorithm. For a provider-centric network, the allocation problem turns out to be NP-hard. We present a greedy heuristic-based algorithm that guarantees almost half of the optimum revenue. We enhance both these algorithms to operate in more general networks with multiple access points and no restrictions on the relative numbers of antennas and channels. A simulation-based evaluation using OPNET demonstrates the efficacy of our approaches and provides us further insights into these problems.

The figures below demonstrate the efficacy of our algorithms. In these figures, “A” means the antenna; “C” means the channel. So “A 2, C 6” means 2nd antenna using the 6th channel. Subscribers are distributed around the AP which has multiple antennas to cover them. We simulate an 802.11b network (three non-interfering channels.) Three different colors have been used in the figures below for these three channels. For details, please read our technical report below.

 
 

Subscriber-centric provisioning

We use 12 directional antennas on the AP, each with a span of 30 degree. we compare the antenna orientations derived by the baseline (left figure above) with our heuristic SUB-HEUR (right figure above) for a subscriber distribution in which 80 subscribers are uniformly distributed within a small region (12% of the total area) and 20 subscribers are uniformly distributed in the remaining area. Baseline algorithm operates as follows: each AP orients its antennas so that they cover the entire area and the sectors covered by any two antennas do not intersect. The baseline algorithm represents a simple strategy that is oblivious of subscriber locations and provides an useful point of comparison. Our heuristic SUB-HEUR is based on the optimum dynamic programming algorithm for subscriber-centric network. SUB-HEUR derives antenna orientations and assignments of subscribers to antennas given by the dynamic programming based algorithm presented in Section III-A of our technical report below. It then associates a channel to each antenna in a round-robin fashion (antennas A 1 gets C 1; A 2 gets C 2, etc.). We observe that the solution provided by SUB-HEUR exhibits the intuitively desirable feature of orienting more antennas where more subscribers reside. The two figures below show that SUB-HEUR improves fairness significantly.

 
 
 
   
We present a comparison of the performance of the baseline algorithm (left figure) with our heuristic SUB-HEUR (right figure.). It shows the data rates available to the subscribers. Since there are 3 channels and subscribers using a channel share its bandwidth equally, there are 3 groups of subscriber throughputs.The baseline algorithm provides poor fairness – subscribers in the densely populated region receive much lower data rates than others. SUB-HEUR improves fairness significantly by ensuring that each channel was shared by an almost equal number of subscribers.
   

Provider-centric provisioning

We present results for an AP with 3 directional antennas each with a default span of 120. We chose a smaller number of antennas (3 as opposed to 12 as in the Subscriber-centric provisioning) to enable the evaluation of optimal revenue via an exhaustive search of all feasible antenna orientations. It compares the antenna orientations provided by baseline (left figure) and our PROV-HEUR (right figure) for the Non-Uniform subscriber distribution. The baseline algorithm represents the same strategy as that described for subscriber-centric.Our PROV-HEUR derives antenna orientations and assignments of subscribers to antennas given by the approximation algorithm GREEDY presented in Section IV of our techinical report. It then associates channels with the antennas using the round-robin scheme. We observe that the solution provided by our PROV-HEUR exhibits the intuitively desirable feature of orienting more antennas where more subscribers reside in order to maximize the revenue. The figure below shows that our PROV-HEUR achieve much more revenue than the baseline.

 

We compare the revenues generated by the baseline algorithm, PROV-HEUR, and the optimal solution for a variety of subscriber throughput demands for provider-centric provisioning. We see that the PROV-HEUR greatly improves upon the revenue obtained using the baseline algorithm. We see that the performance of our PROV-HEUR is very close to that of the optimal solution.

We also enhance both these algorithms to operate in more general networks with multiple access points. For detail, please see our technical report, “Bandwidth Provisioning in Infrastructure-based Wireless Networks Employing Directional Antennas”, in the publications section.

 

People

  • Shiva Kasiviswanathan
  • Bhuvan Urgaonkar
  • Sudarshan Vasudevan, Adverplex Inc.
  • Bo Zhao

    Publications

    Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.

    Packing to Angles and Sectors
    Piotr Berman , Jieun Jeong, Shiva Kasiviswanathan, and Bhuvan Urgaonkar
    Proceedings of the Nineteenth ACM Symposium on Parallel Algorithms and Architectures (SPAA), San Diego, CA, June 2007.
    [37 accepted out of 130 submissions = 28%]
    Also, Electronic Colloquium on Computational Complexity Report TR06-030, 2006.
    Abstract    Paper     Tech. Report    

    Bandwidth Provisioning in Infrastructure-based Wireless Networks Employing Directional Antennas
    Bo Zhao, Shiva Kasiviswanathan, Sudarshan Vasudevan, and Bhuvan Urgaonkar
    Technical Report CSE-07-008, Department of Computer Science and Engineering, The Pennsylvania State University, July 2007.
    Abstract     Tech. Report   

    Software

    dirOPNET: Enhanced OPNET for “Provisioning in Infrastructure-based Wireless Networks Employing Directional Antennas”. We have modified the code of OPNET to allow one MAC layer component to have multiple transmitter components, each of which connects to a directional antenna. Each MAC layer has one receiver component. For notes on how to use this code, please see here.
     
    The OPNET experiment projects of “Bandwidth Provisioning in Infrastructure-based Wireless Networks Employing Directional Antennas”. This is a collection of the inputs to our experiments presented in the technical report CSE-TR 07-008. You can use these inputs to verify and reproduce the experiments used by our technical report. For help on using this file, please see here.