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