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) subscribercentric, where the objective is to fairly allocate bandwidth among the subscribers and (ii) providercentric, 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 noninterfering channels. Using the wellregarded lexicographic maxmin fair allocation as the objective for a subscribercentric network, we present an optimum dynamic programming algorithm. For a providercentric network, the allocation problem turns out to be NPhard. We present a greedy heuristicbased 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 simulationbased 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 noninterfering channels.) Three different colors have been used in the figures below for these three channels. For details, please read our technical report below.




Subscribercentric 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 SUBHEUR (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 SUBHEUR is based on the optimum dynamic programming algorithm for subscribercentric network. SUBHEUR derives antenna orientations and assignments of subscribers to antennas given by the dynamic programming based algorithm presented in Section IIIA of our technical report below. It then associates a channel to each antenna in a roundrobin fashion (antennas A 1 gets C 1; A 2 gets C 2, etc.). We observe that the solution provided by SUBHEUR exhibits the intuitively desirable feature of orienting more antennas where more subscribers reside. The two figures below show that SUBHEUR improves fairness significantly.








We present a comparison of the performance of the baseline algorithm (left figure) with our heuristic SUBHEUR (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. SUBHEUR improves fairness significantly by ensuring that each channel was shared by an almost equal number of subscribers. 




Providercentric 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 Subscribercentric 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 PROVHEUR (right figure) for the NonUniform subscriber distribution. The baseline algorithm represents the same strategy as that described for subscribercentric.Our PROVHEUR 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 roundrobin scheme. We observe that the solution provided by our PROVHEUR 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 PROVHEUR achieve much more revenue than the baseline. 


We compare the revenues generated by the baseline algorithm, PROVHEUR, and the optimal solution for a variety of subscriber throughput demands for providercentric provisioning. We see that the PROVHEUR greatly improves upon the revenue obtained using the baseline algorithm. We see that the performance of our PROVHEUR 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 Infrastructurebased 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 TR06030, 2006. Abstract Paper Tech. Report
Bandwidth Provisioning in Infrastructurebased Wireless Networks Employing Directional Antennas Bo Zhao, Shiva Kasiviswanathan, Sudarshan Vasudevan, and Bhuvan Urgaonkar Technical Report CSE07008, Department of Computer Science and Engineering, The Pennsylvania State University, July 2007. Abstract Tech. Report
Software
dirOPNET: Enhanced OPNET for “Provisioning in Infrastructurebased 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 Infrastructurebased Wireless Networks Employing Directional Antennas”. This is a collection of the inputs to our experiments presented in the technical report CSETR 07008. 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. 
