% -------------------------------------------------------------------------
% All-Annex.tex : Annexures for WiFiRe document
% -------------------------------------------------------------------------
\documentclass[12pt,a4paper]{article}
\usepackage{psfig}
\usepackage{epsf}
\usepackage{times}
\usepackage{latexsym}
\usepackage{fancyheadings}
%\usepackage[pagewise]{lineno}

\textheight 9in
\textwidth 6.5in
\evensidemargin=0in
\oddsidemargin=0in
\topmargin= -.5in
\parindent 0in
\parskip 1.5ex

%This command reserves a whole page for a figure
%Its only argument is the caption
\newcommand{\fullpagefigspace}[2]{
\begin{figure}
\vspace{5.0in}
\caption{#1}
\label{#2}
\end{figure}
}
%            
%
\newcommand{\abs}[1]{$|{#1}|$}
\newcommand{\absq}[1]{$|{#1} |^{2}$}
\newcommand{\tabs}[1]{|{#1}|}
\newcommand{\tabsq}[1]{|{#1}|^2}
\newcommand{\half}{$\frac{1}{2}$}
\newcommand{\nth}{^{\mathrm{th}}}
\newcommand{\prob}[1]{\mathsf{Pr}\left(#1\right)}
\newcommand{\EXP}[1]{\mathsf{E}\!\left(#1\right)}
\newcommand{\D}{\displaystyle}

\newcommand{\erf}[1]{
{\mbox{\mathsf{erf}}}\left( {#1} \right)
}

\newcommand{\erfc}[1]{
{\mbox{\mathsf{erfc}}}\left( {#1} \right)
}

\newcommand{\binomial}[2]{
\left(\! {{#1}\atop{#2}}\!\right)}

%\newcommand{\argmax}[1]{\mathrm{arg}\max_{#1} }

%Numbered environments
\newtheorem{remarks}{Remarks}[section] %\label{rmk:}
\newtheorem{example}{Example}[section] %\label{exp:}
\newtheorem{algorithm}{Algorithm}[section] %\label{alg:}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{discussion}{Discussion}[section] %\label{dis:}
\newcommand{\remove}[1]{}

\newcommand{\notes}[1]{}
\newcommand{\argument}[1]{\noindent{\bf Argument: }#1 \hfill $\Box$}
\newcommand{\VAR}[1]{\mathsf{Var}\!\left(#1\right)} 
\newcommand{\bmath}[1]{\mbox{\boldmath$#1$}}
\newcommand{\first}[1]{$1^{\mathrm{st}}$}
\newcommand{\second}[1]{$2^{\mathrm{nd}}$}
\newcommand{\qed}{\hfill \rule{2.5mm}{2.5mm}}

\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}

\pagestyle{fancy}
\chead{}
\rhead{\small WiFiRe Specifications, Aug 2006 draft}
\lhead{}
\headrulewidth 0pt
%\footrulewidth 0.5pt
\lfoot{}
\cfoot{\thepage}
\rfoot{\small Copyright \copyright 2006 CEWiT, Some rights reserved}

%\pagestyle{myheadings}
%\markboth{}{WiFiRe Specifications, Aug 2006 draft}

%\pagewiselinenumbers
% -------------------------------------------------------------------------
\begin{document}

\addtocounter{page}{74}
\addtocounter{figure}{25}

\section*{ANNEX A : Design Drivers}

\section{The Indian Rural Scenario}
About 70\% of India's population, or 750 million, live in its 600,000 villages. More than 85\% of these villages are in the plains or on the Deccan plateau.
The average village has 200-250 households, and occupies an area of 5 sq. km. Most of this is farmland, and it is typical to find all the houses in one or 
two clusters. Villages are thus spaced 2-3 km apart, and spread out in all directions from the market towns. The market centers are typically spaced 30-40 km apart. Each such centre serves a catchment of around 250-300 villages in a radius of about 20 km. As the population and the economy grow, several large villages are continually morphing into towns and market centres.

The telecommunication backbone network, mostly optical-fiber based, which passes through these towns and market centers, is new and of high quality. The state-owned telecom company has networked exchanges in all these towns and several large villages with optical fiber that is rarely more than 10-15 years old. The mobile revolution of the last four years has seen base stations sprouting in all these towns, with three or more operators, including the state-owned company. These base stations are also networked using mostly optical fiber laid in the last 5 years. There is a lot of dark fiber, and seemingly unlimited scope for bandwidth expansion.

The solid telecom backbone that knits the country together ends abruptly when it reaches the towns and larger villages. Beyond that, cellular coverage extends mobile telephone connectivity up to a radius of 5 km, and then telecommunications simply peters out. Cellular telephony will expand further as it becomes affordable to the rural populace. It is a highly sought after service, and the only reason for the service not spreading as rapidly in rural areas as in urban areas is the lack of purchasing power in the the rural areas. Fixed wireless telephones have been provided in tens of thousands of villages as a service obligation; however, the wireless technologies currently being deployed can barely support dial-up speeds as far as Internet access is concerned.

The rural per capita income is distinctly lower than the national average, and rural income distribution is also more skewed. About 70\% of the rural households earn less than Rs 3000 per month, and only 4\% have incomes in excess of Rs 25000 per month. Only the latter can be expected to even aspire to have a personal computer and Internet connection. For the rest, the key to Internet access is a public kiosk providing a basket of services. Provision of basic telecommunications as well as broadband Internet services is imperative, since ICT is known to be an enabler for wealth creation

\section{Affordability}
When considering any technology for rural India, it is clear that the question of affordability must be addressed first. Given the income levels, one must work backwards to determine the cost of any economically sustainable solution. It is reasonable to expect an expenditure on telecommunication services of only around Rs 60 per month on the average (2\% of household income) from about 70\% of the 200-250 households in a typical village. Thus, the revenue of a public kiosk can only be of the order of Rs 4500 per month (assuming two kiosks per village on the average). Apart from this, a few wealthy households in each village can afford private connections. Taking into account the cost of the personal computer, power back-up, peripherals, etc, it is estimated that a cost of at most Rs 15000 per broadband connection is sustainable for the kiosk. This includes the User Equipment, as well the per-subscriber cost of the Network Equipment connecting the user to the optical fiber PoP. 

A typical wireless system for servicing such a rural area will have a BTS at the fiber PoP. A BTS can be expected to serve about 250-300 connections initially, going upto a 1000 connections as the service becomes stable and popular and the wealthy households decide to invest in a computer. Growth to full potential will take several years. Given the cost target mentioned above, it is found that a wireless technology becomes economically viable in the rural areas only when it has reached maturity and volumes worldwide are high enough to bring the cost down. New technologies at the early induction stage are too costly, particularly since the slow growth in the subscriber base keeps the per-subscriber cost of the BTS and associated equipment high.

\section{Coverage, Towers and System Cost}
We have already mentioned that we need to cover a radius of 15-25 km from the PoP using wireless technology.  The system gain is a measure of the link budget available for overcoming propagation and penetration losses (through foliage and buildings) while still guaranteeing system performance. Mobile cellular telephone systems have a system gain typically of around 150-160 dB, and achieve indoor penetration within a radius of about 3-5 km. They do this with Base Station towers of 40 m height, which cost about Rs 5 lakhs each. If a roof-top antenna is mounted at the subscriber end at a height of 6m from the ground, coverage can be extend upto 15-20 km with this system gain. When the system gain is lower at around 135 dB, as with many low-power systems such as those based on the WiFi standard or the DECT standard~\cite{dect}, coverage is limited to around 10 km and antenna-height at the subscriber-end has to be at least 10m. This increases the cost of the installation by about Rs 1000.

In any case, we see that fixed terminals with roof-top antennas are a must if one is to obtain the required coverage from the fiber PoP. A broadband wireless system will  need a system gain of around 140 - 150 dB at bit-rates in excess of 256 kbps, if it is to be easily deployable. This system gain may be difficult to provide for the higher bit-rates supported by the technology, and one may have to employ taller poles in order to minimize foliage loss.

There is an important relationship between coverage and the heights of the towers and poles, and indirectly their cost. The Base Station tower must usually be at least 40 m high for line-of-sight deployment, as trees have a height of 10-12m and one can expect a terrain variation of around 20-25m even in the plains over a 15-20 km radius. Taller Base Station towers will help, but the cost goes up exponentially with height. A shorter tower will mean that the subscriber-end will need a 20 m mast. At Rs 15000 or more, this is substantially costlier than a pole, even if the mast is a guyed one and not self-standing. The cost of 250-300 such masts is very high compared to the additional cost of a 40 m tower vis-à-vis a 30 m one.  With the 40m towers, simple poles can be deployed at the subscriber-end, and these need be only than 12m high.

In summary, one can conclude that for a cost-effective solution the system gain should be of the order of 145 dB, (at least for the reasonable bit-rates, if not the highest ones supported), a 40 m tower should be deployed at the fiber PoP, and roof-top antennas with 6-12m poles  at the subscriber-end. The system gain can be lower at around 130 dB, provided repeaters are used to cover areas beyond 10 km radial distance, and assuming antenna poles that are 10-12m high are deployed in the villages. The cost per subscriber of the tower and pole (assuming a modest 300 subscribers per tower) is Rs 2500. This leaves about Rs 12500 per subscriber for the wireless system itself. 

\section{Definition of Broadband}
The Telecom Regulatory Authority of India has defined broadband services as those provided with a minimum downstream (towards subscriber) data rate of 256 kbps. This data-rate must be available unshared to the user when he/she needs it. At this bit-rate, browsing is fast, video-conferencing can be supported, and applications such as telemedicine and distance education using multi-media are feasible. There is no doubt that a village kiosk could easily utilise a much higher bit-rate, and as technology evolves, this will become available too. However, it is important to note that even at 256 kbps, since kiosks can be expected to have a sustained rate not much lower, 300 kiosks will generate of the order of 75 Mbps traffic to evacuate over the air per Base Station. This is non-trivial today even with a spectrum allocation of 20 MHz.

The broadband wireless access system employed to provide Internet service to kiosks must also provide telephony using VoIP technology. Telephony earns far higher revenue per bit than any other service, and is an important service. The level of teletraffic is limited by the income levels of the populace. Assuming that most of the calls will be local, charged at around Rs 0.25 per minute,  even if only one call is being made continuously from each kiosk during the busy hours (8 hours per day), this amounts to an expenditure of Rs 120 per day at each kiosk. This is a significant fraction of the earnings of the kiosk, and a significant fraction of the total communications expenditure of the village. 

Thus, depending on the teledensity in the district, one can expect around 0.5-1 Erlang traffic per kiosk. This works out to a total of around  100-200 Erlangs traffic per BTS. Assuming one voice call needs about 2x16 kbps with VoIP technology, this traffic level requires 2x1.5 Mbps to 2x3.0 Mbps of capacity. If broadband services are not to be significantly affected, the system capacity must be several times this number. It is to be noted here that if the voice service either requires a higher bit-rate (say, 64 kbps) per call, or wastes system capacity due to MAC inefficiency when handling short but periodic VoIP packets, we will have significant degradation of other broadband services. Thus, an efficient VoIP capability is needed, with QoS guaranteed, that eats away from system capacity only as much as is unavoidably needed to support the voice traffic. Such a capability must be built into the wireless system by design. It is also important not to discourage use of the system for telephony since it is the major revenue earner as well as most popular service.

\section{Broadband Wireless Technologies circa 2006}
One of the pre-requisites for any technology for it to cost under Rs 12500 per connection is that it must be a mass-market solution. This will ensure that the cost of the electronics is driven down by volumes and competition to the lowest possible levels. As an example, both GSM and CDMA mobile telephone technologies can today meet easily meetthe above cost target, except that they do not provide broadband access.

The third-generation evolution of cellular telephone technologies may, in due course,   meet the cost target while offering higher bit-rate data services. However, they are ain the early induction stage at present, and it is also not clear whether they will right away provide the requires system capacity. However, the third-generation standards are constantly evolving, and the required system capacity is likely to be reached at some time. The only question is regarding when the required performance level will be reached and when the cost will drop to the required levels.  

If we turn our attention next to some proprietary broadband technologies such as iBurst~\cite{iburst}, and Flash-OFDM~\cite{flash}, or a standard technology such as WiMAX-d (IEEE 802.16d)~\cite{dot16}, we find that volumes are low and costs high. Of these, WiMAX-d has a lower system gain. All of them will give a spectral efficiency of around 4 bps/Hz/cell (after taking spectrum re-use into account), and thus can potentially evacuate 80 Mbps with a 20 MHz allocation. High cost is the inhibitory factor.

It is likely that one or more OFDMA-based broadband technologies will become widely accepted standards in the near future. WiMAX-e (IEEE 802.16e)~\cite{dot16} is one such that is emerging rapidly. The standards emerging as the Long-Term Evolution (LTE) of the 3G standards are other candidates. These will certainly have a higher spectral efficiency, and more importantly, when they become popular and successful, they will become mass-market technologies, and the cost will be low. Going by the time-to-maturity of mass-market wireless technologies till date, none of these technologies are likely to provide an economically viable solution for India's rural requirements for several years yet.  

\section{Alternative Broadband Wireless Technologies in the Near Term}
While wide-area broadband wireless technologies will be unavailable at the desired price-performance point for some time, local-area broadband technologies have become very inexpensive. A well-known example is WiFi (IEEE 802l.11) technology. These technologies can provide 256 kbps or more to tens of subscribers simultaneously, but can normally do so only over a short distance, less than 50m in a built-up environment. Several groups have worked with the low-cost electronics of these technologies in new system designs that provide workable solutions for rural broadband connectivity.
 
One of the earliest and most widely deployed examples of such re-engineering is the corDECT Wireless Access System~\cite{cordect} developed in India. A next--generation broadband corDECT system has also been launched recently, capable of evacuating upto 70 Mbps per cell in 5 MHz bandwidth (supporting 144 full-duplex 256 kbps connections simultaneously). These systems are built around the electronics of the European DECT standard, which was designed for local area telephony and data services. Proprietary extensions to the DECT standard have been added in a manner that the low-cost mass-market ICs can continue to be used. These increase the bit-rate by three times, while being backward compatible to the DECT standard. 

The system gain in Broadband corDECT for 256 kbps service is 125-130 dB, depending on the antenna gain at the subscriber-end. This is sufficient for 10 km coverage under line-sight conditions (40 m tower for BS and 10-12 m pole at subscriber side). A repeater is used for extending the coverage to 25 km. The system meets the price-performance requirement, but with the additional encumbrance of taller poles and one level of repeaters.

The WiFiRe standard proposed by CEWiT is an alternative near-term solution, with many similarities. It, too, is a re-engineered system based on low-cost low-power mass-market technology. Cost structures are similar, and deployment issues too are alike. There is one key aspect in which WiFiRe differs from Broadband corDECT. The spectrum used for WiFiRe is unlicensed without fees, whereas the spectrum used by Broadband corDECT is licensed with a fee. The spectral efficiency of the WiFiRe system is poorer, and the cell capacity per MHz of bandwidth is lower. However, this is offset by the fact that the spectrum used by it is in the unlicensed WiFi band of 2.4-2.485 MHz. This unlicensed use is subject to certain conditions, and some modifications to these conditions will be needed to support WiFiRe in rural areas (see section on Conditional Licensing below).  WiFiRe technology is best suited for local niche operators who can manage well the conditionalities associated with unlicensed use. It does not afford the blanket protection from interference that a system operating with licensed spectrum enjoys.

\section{Motivation for WiFiRe}
In recent years, there have been some sustained efforts to build a rural broadband technology using the low-cost, mass-marketWiFi chipset. WiFi bit rates go all the way up to 54  Mbps  Various experiments with off-the-shelf equipment have demonstrated the feasibility of using WiFi for long-distance rural point-to-point links~\cite{insideout}. One can calculate that the link margin for this standard is quite adequate for line-of-sight outdoor communication in flat terrain for about 15 kms of range.  The system gain is about 132 dB for 11 Mbps service, and as in corDECT, one requires a 40 m tower at the fiber PoP and 10-12 m poles at the subscriber-end.

The attraction of WiFi technology is the de-licensing of spectrum for it in many countries, including India. In rural areas, where the spectrum is hardly used, WiFi is an attractive option. The issues related to spectrum de-licensing for WiFiRe are discussed separately in the next section. Before that, we turn our attention to the suitability of the WiFi  standard as it exists for use over a wide rural area. We have already seen that the limitations of the Physical Layer of WiFi can be demonstrably overcome. We turn our focus noe to the MAC in WIFi.

The basic principle in the design of MAC in Wi-Fi is fairness and equal allocation to all sources of demand for transmission.  This leads to the DCF mode which operates as a CSMA/CA with random backoff upon sensing competing source of tx.  On the other hand there is also a PCF mode, which assumes mediation by access points.  This gives rise to the possibility of enterprise-owned and managed networks with potential for enhanced features like security and quality of service guarantees.

The CSMA/CA DCF MAC has been analysed and turns out to be inefficient for a distribution service that needs to maximize capacity for subscribers and maintain quality of service~\cite{perf11}.  The delays across a link are not bounded and packet drops shoot up rapidly in such a system while approaching throughputs of the order of 60\% of rated link bandwidth. The PCF MAC will perform better than the DCF MAC. However, both the MACs in the WiFi standard become very inefficient when the spectrum is re-used in multiple sectors of a BTS site. 

Fundamentally, in a TDD system, wherein uplink and downlink transmissions take place in the same band in a time-multiplexed manner, the down-link (and similarly uplink) transmissions of all the sectors at a BTS site must be synchronized. Otherwise the receivers in one sector will be saturated by the emissions in another. This can be avoided only by physical isolation of the antennas, which is very expensive if all the antennas must also be at a minimum height of 40 m. Further, this synchronization must be achieved with minimal wastage of system capacity due to the turnaround from uplink to downlink and vice versa, as well as due to varying traffic characteristics (packet sizes, packet arrival rates) in different sectors at different times. 

It is thus clear that a new MAC is needed which is designed to maximize the efficiency in a wide-area rural deployment supporting both voice and data services with modest use of spectrum (see next section for the need for limiting the use of spectrum). Fortunately, most Wi-Fi chipsets are designed so that the Physical and MAC layers are separate.  Thus one can change the MAC in ways that enable high- efficiency outdoor systems that can be used for rural internet service provisioning or voice applications, while retaining the same PHY.  Thus without significantly changing radio costs, one can arrive at entirely different network level properties by changing the MAC, sectorization and antenna design choices and tower/site planning.
Taking a cue for this approach, we design a new wireless system, WiFiRe, which shares the same PHY as WiFi, but with a new MAC.  The principle of Access Points, or special nodes which control the channel and allocate bandwidth to individual nodes, and tight synchronization based on the time-slotting principle used in cellular voice systems such as GSM or upcoming data systems like WiMax, can be combined to guarantee efficiency and quality of service.  

\section{Conditional Licensing of Spectrum}
The spectrum allotted for WiFi, in the 2.4-2.485 MHz band, can be employed by anyone for indoor or outdoor emissions, without a prior license provided certain emission limits are met [www.dotindia.com/wpc]. The 5 GHz band, also universally allotted to WIFi, can be used in India only for indoor emissions. In the 2.4 Ghz band, the maximum emiited power can be 1W in a 10 MHz (or higher) bandwidth, and the maximum EIRP can be 4W. The outdoor antenna can be no higher than 5 m above the rooftop. For antenna  height higher than the permissible level, special permission has to be obtained. Further, if the emissions interfere with any licensed user of spectrum in the vicinity, the unlicensed user may have to discontinue operations.

It is clear that some modifications of the rules are needed for WiFiRe. A higher EIRP will need to be permitted in rural areas, and further, antenna deployment at 40 m must be permitted at the PoP, and possibly for repeaters (in due course). Antenna deployments at 10-15 m will have to be permitted at the villages.

The relaxations may be restricted to WiFiRe- compliant technology. It may be given only for one specified carrier per operator, and a maximum of two operators may be permitted in an area. The BTS and repeaters of the second operator (in chronological order of deployment)  may be restricted to be at least one kilometer from those of the first operator in an area. This will prevent mutual adjacent-channel interference, as well as permit maximum use of the two conditionally licensed carriers by others in the vicinity of the BTSs. If an unlicensed WiFi user in the vicinity of the BTS or village kiosk/private subscriber interferes with the WiFiRe system, the unlicensed user will have to switch over to a non-interfering carrier in the same band or in the 5 GHz band. This last condition is not very restrictive, as only around 15 MHz of the available 85 MHz in the 2.4 GHz band is blocked in the vicinity of any one BTS or village kiosk/subscriber. Further, if the unlicensed user is an indoor user, the area where there is noticeable interference to/from the WifiRe system is likely to be fairly small.

\newpage
\addtocounter{section}{-8}
% -------------------------------------------------------------------------
\section*{ANNEX B: Capacity Analysis and Optimisation}

\section{Spatial Reuse Model}
\label{section:spatial reuse}

Maximising the cardinality of independent sets used in a schedule need
not necessarily increase the throughput, since as the cardinality of
the set increases, the prevailing SINR drops, thereby resulting in an
increase in the probability of error, decreasing the throughput. Hence
it is necessary to limit the cardinality of the independent set used
so as to satify the SINR requirements. i.e., there is a limit to the
number of simultaneous transmissions possible.

In this section the problem of finding the maximum number of
simultaneous transmissions possible in different sectors in the uplink
and the downlink is being considered. There is no power control in the
downlink. The BTS transmits to all the STs at the same power. There is
static power control in the uplink. Each ST transmits to the BTS at a
fixed power, such that the average power received from different STs
at the BTS is the same.  The STs near the BTS transmit at a lower
power and the ones farther away transmit at a higher power.

A typical antenna pattern used in the deployment is as shown in
Figure~\ref{fig:antennacordect}. Based on the antenna pattern, one can
divide the region into an \emph{association region}, a \emph{taboo
  region} and a \emph{limited interference region} with respect to
each BTS.

The radial zone over which the directional gain of the antenna is
above -3dB is called the association region. In the analysis, the
directional gain is assumed to be constant over this region. Any ST
which falls in this region of a BTS antenna $j$ is associated to the
BTS~$j$.

The region on either side of the association region where the
directional gain is between -3dB and -15dB is called the taboo region.
Any ST in this region of BTS~$j$ causes significant interference to
the transmissions occuring in Sector~$j$. When a transmission is
occuring in Sector $j$, no transmission is allowed in this region.

In the limited interference region the directional gain of the BTS
antenna is below -15dB. A single transmission in this region of
BTS~$j$ may not cause sufficient interference to the transmission in
Sector~$j$. But a number of such transmissions may add up causing the
SINR of a transmission in Sector~$j$ to fall below the threshold
required for error free transmission. This is taken care of by
limiting the total number of simultaneous transmissions in the system
as explained in Sections~\ref{section:spatialreuse:uplink} and
\ref{section:spatialreuse:downlink}.

As an example, for the antenna pattern  shown in
Figure~\ref{fig:antennacordect}, the association region is a
$60^{\circ}$ sector centered at the $0^{\circ}$ mark, the taboo region
is $30^{\circ}$ on either side of this association region, and the
limited interference region covers the remaining $240^{\circ}$.


\begin{figure}[htb]
  \centering \
  \psfig{figure=./figures/antenna_cordect.eps,width=150mm,height=145 mm}
  \caption{ Radiation pattern for a typical antenna that could be used
    in the deployment.}
  \label{fig:antennacordect}
\end{figure}

\subsection{Uplink}
\label{section:spatialreuse:uplink}
In the uplink, there is static power control. All STs transmit at a
power such that the power received at the BTS is $P$ times noise
power.  Let the maximum power that can be transmitted by an ST be
$P_t$ times noise power. Let $R_0$ be the distance such that when
$P_t$ is transmitted by an ST at distance $R_0$, the average power
received at the BTS is $P_0$ times noise power, where $P_0$ is the
minimum SNR required to decode a frame with a desired probability of
error.  Also, let $R$ be such that when $P_t$ is transmitted from an
ST at distance $R$, the power received at the BTS is $P$ times noise
power, i.e.,

\[\frac{P}{P_0}=\bigg(\frac{R}{R_0}\bigg)^{-\eta}\]

In the presence of interferers, the power required at the receiver
will be greater than $P_0$ times noise. Let $P$ be the power required,
so that the receiver decodes the frame with a desired probability of
error, in the presence of interferers.  The directional gain of the
BTS antenna is -15dB in the other non taboo directions. Hence, the
interference power from a transmission in any other sector would be
$10^{-\frac{3}{2}}P$.  If there are $n_0-1$ simultaneous
transmissions, the path loss factor being $\eta$, the signal to
interference ratio at the BTS receiver is
\begin{eqnarray*}
\Psi_{rcv} &=& \frac{P}{1+\sum_{i=1}^{n_0-1} 10^{-\frac{3}{2}}P}\\
&=& \frac{P_0(\frac{R}{R_0})^{-\eta}}{1+(n_0-1) 10^{-\frac{3}{2}}P_0(\frac{R}{R_0})^{-\eta}}\\
\end{eqnarray*}

For decoding a frame with less than a given probability of error, we
need an SINR of $P_0$ at the receiver.  So, $R$ should be such that
\begin{eqnarray*}
\Psi_{rcv} &\geq& P_0\\
 \frac{P_0(\frac{R}{R_0})^{-\eta}}{1+(n_0-1)10^{-\frac{3}{2}}P_0(\frac{R}{R_0})^{-\eta}} &\geq& P_0\\
n_0&\leq&1+\frac{(\frac{R}{R_0})^{-\eta}-1}{10^{-\frac{3}{2}}P_0(\frac{R}{R_0})^{-\eta}}
\end{eqnarray*}

To provide a margin for fading, consider a reduced range $R'$ such
that
\[10\log{\bigg(\frac{R'}{R}\bigg)^{-\eta}} \geq 2.3\sigma\] 
where $\sigma$ is the fade variance. In this case, 99\% of the STs in
a circle of radius $R'$ around the BTS can have their transmit power
set so that the average power $P$ is received at the BTS in the
uplink.

 \begin{figure}[htb]
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/no_of_txn_new0.eps,width=50mm,height=50mm}
   \end{minipage}
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/no_of_txn_new4.eps,width=50mm,height=50mm}
   \end{minipage}
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/no_of_txn_new8.eps,width=50mm,height=50mm}
   \end{minipage}
   % \label{figure:coverage}
   % \caption{The plot showing the variation of number of simultaneous
   %   transmissions possible with coverage for $\eta = 2.3, 3,4$ for
   %   $\sigma = 8$.}
   % \end{figure}
   % \begin{figure}[!]
   \\
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/cap0.eps,width=50mm,height=50mm}
   \end{minipage}
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/cap4.eps,width=50mm,height=50mm}
   \end{minipage}
   \begin{minipage}{5cm}
     \centering \
     \psfig{figure=./plots/cap8.eps,width=50mm,height=50mm}
   \end{minipage}
   \caption{Variation of the number of simultaneous transmissions
     possible ($n_0$) and system capacity(C) with coverage relative to
     a reference distance $R_0$ for $\eta = 2.3, 3,4$ and $\sigma =
     0,4,8$. Plots for $\sigma = 0,4,8$ are shown left to right. }
   \label{figure:coverage_cap}
 \end{figure}

 Evidently, $n_0$ can be increased by reducing $R'$. But then, spatial
 reuse increases at the expense of coverage. This tradeoff can be
 captured by the spatial capacity measure $C = nR'^2$, which has units
 slots.km${^2}$ (or packets.km${^2}$)

 The variation of the maximum number of transmissions, $n_0$ and
 system capacity, $C$, with coverage is as shown in
 Figure~\ref{figure:coverage_cap}. One can see that for each $\eta$,
 there is an optimal $n_0$ and $R'$ such that $C$ is maximum.  The
 coverage for which capacity is maximum can be obtained by equating
 the derivative of $C$, with respect to $(R'/R_0)$ to be zero. Take
 $r' = \frac{R'}{R_0}$ and set

\[\frac{\mathsf{d}C}{\mathsf{d}r'} = 0\]
Then we get the optimum value of $r'$ and $n_0$ as
\[r' =  \bigg(10^{-\frac{2.3\sigma}{10}} \frac{1+10^{-\frac{3}{2}}P_0}{1+\frac{\eta}{2}}\bigg)^{\frac{1}{\eta}}\] 
\[n_0 = \frac{(1+10^{-\frac{3}{2}}P_0)\eta}{10^{-\frac{3}{2}}P_0(\eta+2)}\]


\begin{table}
  \centering   \
  \begin{tabular}{|c|c|c|c|}
    \hline
    {\begin{tabular}{c}{~~$\sigma$}\\{$\eta$~~}\end{tabular}} &0 & 4 & 8  \\   
                              
    \hline
    2.3    &0.77 & 0.31 & 0.12\\
    \hline
    3      &0.78 & 0.39 & 0.20\\
    \hline 
    4      &0.80 & 0.47 & 0.28\\
    \hline
  \end{tabular}
  \hspace{1cm} 
  \begin{tabular}{|c|c|c|c|}
    \hline 
    {$\eta$}&2.3&3&4\\
    \hline
    {$n_0$}&3&3&4\\  
    \hline
  \end{tabular}
  \caption{The optimum values of $C$ and $n_0$ for different values of $\eta$ and $\sigma$.}  
\label{table:Cn}
\end{table}

Table~\ref{table:Cn} gives the optimum coverage $C$ and maximum number
of simultaneous transmissions possible for different values of
$\eta$and $\sigma$. $P_0$ is taken to be $8dB$. Directional gain of
the antenna is taken to be 1 in the associated sector and $-15dB$ in
non-taboo directions. For path loss factor $\eta=4$, the number of
simultaneous transmissions is seen to be 4. For a given value of
$\eta$, the maximum nunber of simultaneous transmissions is found to
be independent of the fade variance $\sigma$.

\subsection{Downlink}
\label{section:spatialreuse:downlink}

In the downlink, the transmit power is kept constant. The BTS
antennas transmit at a power $P_t$ times noise.  Let $R_0$ be the
distance at which the average power received is $P_0$ times noise. $R$
be the distance such that the average power received is $P$.  Then,
\begin{eqnarray*}
  P_0&=&P_t\bigg(\frac{R_0}{d_0}\bigg)^{-\eta}\\
  P&=&P_t\bigg(\frac{R}{d_0}\bigg)^{-\eta}\\
  \frac{P}{P_0}&=&\bigg(\frac{R}{R_0}\bigg)^{-\eta}
\end{eqnarray*}

Allowing $n_0-1$ interferers,
\begin{eqnarray*}
  \Psi_{rcv} &=& \frac{P}{1+(n_0-1) 10^{-\frac{3}{2}}P}\\
  &=& \frac{P_0(\frac{R}{R_0})^{-\eta}}{1+(n_0-1) 10^{-\frac{3}{2}}P_0(\frac{R}{R_0})^{-\eta}}\\
\end{eqnarray*}
which is the same as in uplink. So, the optimum number of
transmissions and optimum coverage in uplink and downlink are the
same.  The plots and tables for uplink apply for downlink also.


\subsection{Number of Sectors}
Once the maximum number of simultaneous transmissions possible, $n_0$
is obtained, one gets some idea about the number of sectors required
in the system. In an $n_0$ sector system, when a transmission occur in
the taboo region between Sector~$j$ and Sector~$j+1$, no more
transmissions can occur in Sectors $j$ and $j+1$. So, the number of
simultaneous transmissions can be at most $n_0-1$, one in Sector $j$
and $j+1$ and at most one each in each of the other sectors. Thus the
maximum system capacity cannot be attained with $n_0-1$ sectors. With
$n_0+1$ sectors, one can choose maximal independent sets such that the
sets are of cardinality $n_0$.  So, at least $n_0+1$ sectors are
needed in the system. From the spatial reuse model it can be seen that
there can be up to 4 simultaneous transmissions in the system, for
path loss $\eta=4$. So, the system should have at least 5 sectors.

\section{Characterising the Average Rate region}
\label{section:Capacity_bnd}
There are $m$ STs. Suppose a scheduling policy assigns $k_j(t)$ slots,
out of $t$ slots, to ST $j$, such that $\lim_{t \to \infty}
\frac{k_j(t)}{t}$ exists and is denoted by $r_j$. Let $\mathbf{r} =
(r_1,r_2, \dots r_m)$ be the rate vector so obtained. Denote by
${\cal{R}}(n)$ the set of acheivable rates when the maximum number of
simultaneous transmission permitted is $n$. Notice that for $n_1>n_2$,
${\cal{R}}_1 \supset {\cal{R}}_2 $. This is evident because any
sequence of scheduled slots with $n=n_2$ is also schedulabale with
$n=n_1$.In the previous section, we have determined the maximum value
of $n$, i.e., $n_0$. Denote ${\cal{R}}_0 = {\cal{R}}(n_0)$. A
scheduling policy will aceive an $r \in {\cal{R}}_0$. In this section,
we provide some understanding of ${\cal{R}}_0$ via bounds.



\subsection{An Upper Bound on Capacity}
\label{section:upperbound} 
Suppopse each ST has to be assigned the same rate $r$. In this
subsection an upperbound on $r$ is dertermined. In general, the rate
vector $(r,r,\dots r)\notin {\cal{R}}_0$. The upper bound is obtained
via simple linear inequalities.  Consider the case $n \geq 3$.
Suppose one wishes to assign an equal number of slots $k$ to each ST
in the uplink.  There are $N_U$ uplink slots in a frame.  Consider
Sector $j$, which contains $m_j$ STs.  Thus $k\cdot m_j$ slots need to
be allocated to uplink transmission in Sector $j$. When STs in the
interference region $j-$ or $j+$ transmit, then no ST in Sector $j$
can transmit.  Suppose $k_{j\pm}$ slots are occupied by such
interference transmission.  Now it is clear that
\[k\cdot m_{j}+k_{j\pm}=N_U\]
because whenever there is no transmission from the interference region
for sector $j$ there can be a transmission from sector $j$.  Let $m_{j-}$
and $m_{j+}$ denote the number of STs in the interference regions
adjacent to Sector $j$.  Since the nodes in $j-$ and $j+$ can transmit
together, we observe that
\[k_{j\pm}\geq \max(k\cdot m_{j-}, k\cdot m_{j+})\]
with equality if transmission in $j-$ and $j+$ overlap wherever
 possible.  Hence one can conclude that for any feasible scheduler that
 assigns $k$ slots to each ST in the uplink

\[k\cdot m_j + \max(k\cdot m_{j-}, k\cdot m_{j+}) \leq N_U\]

For large frame time $N$, divide the above inequality by $N$
and denote the rate of allocation of slots by $r$. Thus if out of $t$
slots, each ST is allocated $k$ slots, then $r = \lim_{t \to
  \infty}\frac{k}{t}\leq 1$

\[r\cdot m_j +r\cdot \max(m_{j-}, m_{j+}) \leq \phi_u\]
where $\phi_u$ is the fraction of frame time allocated to the uplink
or 
\[r \leq \frac{\phi_u}{m_j+\max(m_{j-}, m_{j+})}\]
This is true for each $j$. So,

\[r \leq \frac{\phi_u}{\max_{1 \leq j \leq n}(m_j + \max(m_{j-}, m_{j+}))}\]

For the case $n=2$ for $j \in \{1, 2 \}$ denote the interfering nodes
 in the other sector by $m_j$.  One easily sees that
\[r \leq \frac{\phi_u}{\max(m_1+m'_1, m_2+m'_2)}\]



\subsection{An Inner Bound for the Rate Region}
\label{section:lowerbound}
In this section a rate set ${\cal{R}}_L$ is obtained such that
${\cal{R}_L}\subset{\cal{R}_0}$. i.e., ${\cal{R}}_L$ is an inner bound
to the aceivable rate set.

  The following development needs some graph definitions.
\begin{description}
 \item{\emph{Reuse constraint graph}:} Vertices represents links. In any slot
  all links are viewed as uplinks or all are downlinks. Two vertices
  in the graph are connected, if a transmission in one link can cause
  interference to a transmission in the other link.  The reuse
  constraint graph is represented as $(\mathbf{\cal{V,E}})$, where
  $\mathbf{\cal{V}}$ is the set of vertices and $\mathbf{\cal{E}}$ is
  the set of edges.
\item{\emph{Clique}:} A fully connected subgraph of the reuse constraint
  graph.  A transmission occuring from an ST in a clique can
  interfere with all other STs in the clique. At most one
  transmission can occur in a clique at a time.
\item{\emph{Maximal clique}:} A maximal clique is a clique which is not a proper 
subgraph of another clique.
\item{\emph{Clique incidence matrix}:}
Let ${\kappa}$ be the number of maximal cliques in  $(\mathbf{\cal{V,E}})$. Consider
 the $\kappa \times m$ matrix $\mathbf{\cal{Q}}$ with
\[\mathbf{\cal{Q}}_{i,j} = \left\{\begin{array}{cc} 1 & \mathrm{if~link}~j~\mathrm{is~in~clique}~i\\
 0 & \mathrm{o.w.}\end{array}\right.\]
\end{description}

By the definition of $\mathbf{r}$ and ${\cal{Q}}$, a necessary
condition for $\mathbf{r}$ to be feasible is (denoting by
$\mathbf{1}$, the column vector of all $1$s.)
\[\mathbf{\cal{Q}}\cdot \mathbf{r} \leq 1\] since at most one link
from a clique can be activated. In general, $\mathbf{\cal{Q}}\cdot
\mathbf{r} \leq 1$ is not sufficient to guarantee the feasibility of
$\mathbf{r}$. It is sufficient if the graph is linear.  A linear
graph is one in which links in each clique is contigous. A
linear clique will have a clique incidence matrix of the form
\[{\cal{Q}} =\left[ \begin{array}{cccccccccccc} 
1&1&1&1&\dots&\dots&0&0&0\\
0&0&1&1&1&1&\dots&0&0\\
0&0&0&0&1&1&1&1&\dots\\
\vdots&&&&&&&&\vdots\\
0&0&0&0&0&\dots&1&1&1\end{array}\right]\]


The reuse constraint graph in the multisector scheduling problem being
considered has a ring structure.  $\mathbf{\cal{Q}}\cdot \mathbf{r}
\leq 1$ gives an upper bound on the rate vector. The reuse constraint
graph is linear except for the wrapping around at the end.  If the
nodes in one sector are deleted, the graph becomes linear. Let
$\mathbf{m}_i$ be the set of STs in Sector~$i$. There is a  feasible
$\mathbf{r}_i$ such that $\mathbf{\cal{Q}}\cdot \mathbf{r}_i \leq 1$
and all STs in $\mathbf{m}_i$ are given rate 0.  Linear combination of
feasible vectors is also feasible.  Thus, defining
\begin{eqnarray*}
  {\cal{R}}_L := \{\mathbf{x}:\mathbf{x} =
  \sum_{i=1}^{m}\alpha_i r_{ij}; ~~~\mathbf{\cal{Q}}\cdot [\mathbf{r_1
    r_2 \dots r_m}]\leq \mathbf{1};~~~\sum_{i=1}^{m}\alpha_i=1;~~~
  \mathbf{r_1(m_1)}=\dots= \mathbf{r_m(m_m)}=0\}
\end{eqnarray*}

We see that ${\cal{R}}_L \in {\cal{R}}$

\subsection{Optimum Angular positioning of the Antennas}

As can be seen from the previous section, feasible rates set,
${\cal{R}}_0$, of the system depends on the spatial distribution of
the STs around the BTS. Thus the ${\cal{R}}_0$ varies as the sector
orientation is changed. A system where the antennas are oriented in
such a way that most STs fall in the association region of BTSs rather
than in the taboo region will have more capacity than one in which
more STs are in the taboo regions.

One sector boundary is viewed as a reference. Let
${\cal{R}}_0(\theta)$ denote the feasible rate set, when this boundary
is at an angle $\theta$ with respect to a reference direction. Then,
for each $0 \leq \theta \leq \frac{360 ^ {\circ}}{n}$, we have
${\cal{R}}_0(\theta)$, where $n$ is the number of sectors. Since
${\cal{R}}_0(\theta)$ is not known, the inner bound
${\cal{R}}_L(\theta)$ is used in the following analysis. If each
vector $\mathbf{r}$ is assigned a utility function $U(\mathbf{r})$,
then one could seek to solve the problem
\[\max_{0 \leq \theta \leq \frac{360 ^ {\circ}}{n}} \max_{ \mathbf{r} \in {\cal{R}}_L(\theta)} U(\mathbf{r})\]
 and then position the antenna at this value of $\theta$.

The optimization can be done so as to maximise the average rate
allocated to each ST, with the constraint that each ST gets the same
average rate. The bound evaluated with average rate to each ST, for
antenna positions differing by $5^\circ$ is given below.  $ub(i)$ gives
the upperbound on capacity of the system with antenna placed at
$((i-1)*5)^\circ$ from the reference line. Similarly $lb(i)$ is the
lower bound for each position.  

Upper bound, $\mathbf{ub} =
\begin{array}{cccccccc}
  [0.0714&0.0769&0.0714&0.0714&0.0667&0.0769&0.0714\\0.0667&0.0667&0.0625&0.0625&0.0667&0.0667&0.0769]
\end{array}$

Lower bound, $\mathbf{lb} = \begin{array}{ccccccc}
[0.0714&0.0769&0.0714&0.0714&0.0667&0.0769&0.0714\\0.0667&0.0667&0.0625&0.0625&0.0667&0.0667&0.0769]
\end{array}$

The bounds are seen to be very tight, and the maximum rate is obtained
when antennas are at $5^\circ$, $25^\circ$ or $-5^\circ$ from the
reference line. The maximum rate so obtained is 0.0769, giving a sum
capacity of 3.076. Only 14 different positions of the antenna are
considered for a 5 sector system, since the pattern would repeat
itself after that.


Trying to optimize tha rates such that the rate to each ST is
maximized will adversely affect the sum capacity of the system. So,
take $U(\mathbf{r})=\sum_{j=1}^{m}(r_j)$.

For example, the sum capacity evaluated for antenna
postition varied in steps of $5^\circ$ is as follows. It can be seen
that the system capacity does not vary much with the position of the
antenna. But, there seems to be some positions which are worse than
the others.

Upper bound,$\mathbf{ub} =\begin{array}{cccccccccccccccc}
[4&4&4&4&4&4&4&4&4&4&4&4&4&4]
\end{array}$\\
Lower bound, $\mathbf{lb} = \begin{array}{cccccccccccccccc}
[4&4&3.8046&4&4&4&4&4&4&4&3.8883&3.8699&4&3.9916]
\end{array}$

\begin{figure}[htb]
  \begin{minipage}{75mm}
    \centering \
    \psfig{figure=./plots/sumrate.eps,width=75mm,height=75mm}
  \end{minipage}
  \begin{minipage}{75mm}
    \centering \
    \psfig{figure=./plots//fairnessind.eps,width=75mm,height=75mm}
  \end{minipage}
  \caption{Variation of sum rate and fairness index with antenna
    orientation for different utility functions.}
  \label{figure:sumrate_fairnessind}
\end{figure}


Maximising $\sum_{i=1}^{m}\log(r(i))$ under the given constraints for
upper bound and lower bound gives the utility
functions for different positions of the antenna as\\
$U_{lb}$ = $\begin{array}{cccccccc}
  [-96.2916&-95.7459&-97.0998&-95.112&-95.9083&-98.0191&-96.1752\\-99.1991&-101.1465&-102.5186&-102.0872&-99.52350&-98.37440&-96.58240]
\end{array}$\\
$U_{ub}$ = $\begin{array}{cccccccc}
  [-96.2916&-95.5485&-97.0998&-95.1122&-95.9083&-98.0191&-96.1752\\-99.1991&-101.1465&-102.5186&-102.0872&-99.5235&-97.3909&-96.4809]
\end{array}$\\

The sum capacities for each of the rates above are bounded by \\
Sum of rates for upperbound = $\begin{array}{cccccccccccccccc}
  [3.9102&3.8463&3.7333&3.8611&3.8535&3.6159&3.7896\\3.6663&3.3637&3.30270&3.3513&3.6291&3.7565&3.7844]
\end{array}$\\
Sum of rates for lower bound = $\begin{array}{cccccccccccccccc}
  [3.9102&3.8350&3.7333&3.8612&3.8535&3.6157&3.7896\\3.6663&3.3636&3.3027&3.3512&3.6291&3.704&3.7734]
\end{array}$\\

The utility function is maximum when the antenna is positioned at
$15^\circ$ from the reference line.  The sum of rates at this position
is 3.86.  This gives a trade-off between maximising the system
capacity and providing fairness.

The sum of the rate given to STs and the fairness index vs antenna
orientation is plotted in Figure~\ref{figure:sumrate_fairnessind}. 
for different utility functions (the lower bounds are plotted here).
Fairness index varies from 0 to 1. For a rate vector $\mathbf{r}$, the
fairness index is given by
\[\gamma =\frac{(\sum_{1=1}^{m}x_i)^2}{m \sum_{1=1}^{m}x_i^2}\]
If the rates to different STs are equal, then fairness index would be 1,
 and it decreases as the rates are made unfair.
The plots for maximum $\sum_{i=1}^{m}{r_i}$, maximum $\sum_{i=1}^{m}\log{r_i}$ 
%and by maximising the average rate to each ST 
are shown. It can be seen that maximising the sum rate gives high
overall capacity, but poor fairness. On the other hand, maximising the
average rate to each ST gives good fairness, but low sum capacity.
Maximising $\sum_{i=1}^{m}\log{r_i}$ gives a good tradeoff between
maximising the system capacity and providing fairness.  It is
interesting to note that in maximum $\sum_{i=1}^{m}\log{r_i}$ case,
the sum capacity is higher when fairness is lower and viceversa.
For example, at $\theta=10$, we can see that the sum rate is close to
4. The fairness index is also close to 1. So, we may choose this
orientation as optimum.

\newpage
\addtocounter{section}{-2}
% -------------------------------------------------------------------------
\section*{ANNEX C: Scheduler Design}
\section{Slot Scheduling}

\label{section:problem}
The scheduling problem  is the following.

First partition the frame of size $N$ slots into a contiguous part
with $N_D$ downlink slots and an uplink part with $N_U$ uplink slots, such
that $N_D + N_U = N - N_B$, where $N_B$ is the number of slots
required for the periodic beacon. Typically, $N_D \gg N_U$
as TCP data traffic is highly asymmetric since users download a lot
more than they upload, and during downloads, long TCP packets (upto
1500 bytes) are received in the downlink and one 40 byte TCP ACK is
sent in the uplink for alternate recieved packets.

Now, when $m_{v,i}, 1\leq i\leq m$, VOIP calls are admitted for ST $i$,
one needs to determine the number of slots $C_i$ to be reserved in the
uplink and downlink subframes for ST $i$, such that the QoS targets
are met for all the voice calls. For doing this, evidently the set of
vectors $\textbf{C} = (C_1,\dots,C_m)$ that are feasible (i.e., can be
scheduled) needs to be known. For each deployment,
there will be an optimal set of such vectors
${\cal{C}}_{opt}$, and for any practical
scheduler, there will be an achievable set of admissible vectors
${\cal{C}} \in {\cal{C}}_{opt}$.

Once the required vector of voice payload slots has been scheduled, one
has to schedule as many additional payload slots, so as to maximize
the traffic carrying capacity for TCP while ensuring some fairness
between the flows.



\subsection{Representation of a Schedule}
A feasible schedule for the deployment in Figure~\ref{fig:sch_dep} is
given in the table below, where each row stands for a sector and each
colomn stands for a slots.  There are 15 slots in the example. The
entry in the table denotes the index of the ST that is transmitting in
each sector in each slot.  ST 1 in sector 2 and ST 2 in sector 1
transmit for the first 4 slots. At the end of 4th slot, ST 1 stops
transmitting and ST 4 starts transmitting. The matrix representation
of the schedule is also shown.  The first 3 columns stands for the 3
sectors. Each entry shows the index of the ST that is transmitting.
The last column indicates the number of slots for which that row is
operative.  Here, the sum of elements in column 4 is 15, indicating
that there are 15 slots. This notation is followed throughout the
examples.

\begin{figure}[htb]
 \centering \
 \psfig{figure=./figures/int_association_matrices.eps,width=60mm,height=60mm} 
 \caption{A system example showing the distribution of 6 stations in 3 sectors}
 \label{fig:sch_dep}
\end{figure}
slots $\to$\\
\begin{minipage}{10cm}
 % \begin{table}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
  \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
    \hline
    2&2&2&2&2&2&2&2&0&0&0&0&0&0&0\\
    \hline
    1&1&1&1&4&4&4&4&4&4&4&4&4&4&4\\ 
    \hline
    0&0&0&0&0&0&0&0&6&6&6&6&6&6&6\\ 
    \hline    
  \end{tabular}
  % \end{table}
\end{minipage}
\vspace{1.5cm}
\begin{minipage}{4cm}
$\left[ \begin{array}{cccc}2&1&0&4 \\2&4&0&4 \\0&4&6&7 
\end{array}\right]$
\end{minipage}

\subsection{A Greedy Heuristic Scheduler for the Uplink}
\label{greedy_alg}
The STs are scheduled such that the one with the longest queue is
scheduled first. Find an activation vector which includes the ST with
the largest voice queue. Next include a non interfering ST with the
longest queue and so on until the number of STs in the activation set
is equal to the number of simultaneous transmissions possible or till
the activation set is maximal. A maximal activation set is one to
which one cannot add any more links such that there is no interference
between the links in the set. Use this maximal activation vector until
one of the STs in the set completes transmission. Once one of the STs
complete transmission, we remove that ST from the set and schedule
another ST, that does not interfere with the STs in the set. Repeat
the procedure until all the STs completes transmitting their voice
packets. When all the STs complete their voice transmission, the
remaining slots are used for TCP transmission. If at any stage during
voice transmission, a situation occurs where there are no more
noninterfering STs in a sector which can transmit voice, but there is
one that can transmit data, schedule data for that interval.

In the beginning of each frame, for each slot $k$, heuristically build
an activation vector $\mathbf{u}_k \in \mathbf{\cal{U}}$ starting from
an ST in $\{i: q_{k,i}=\max_j q_{k,j}\}$, i.e., the non interfering
station with the maximum voice queue. Here, $q_{kj}$ denotes the queue
length of the $j$th ST at the beginning of the $k$th slot.  $k$ varies
from 1 to $N$ over a frame. Build a maximal activation vector
beginning with that link, and augmenting the vector every time with a
non interfering link.

$\cal{I}(\mathbf{u})$ denote the interference set of activation set
$\mathbf{u}$, the set of links that can interfere with the STs in
$\mathbf{u})$.

\noindent
\begin{algorithm}
  \label{alg:greedy_alg}
\end{algorithm}
\begin{enumerate}
\item{} Modify the voice queue lengths to include the overhead slots
  required. i.e., If an ST has a voice queue of 2 packets, add 3 slots
  of PHY overhead to make the queue length 5.
\item{}Initially, slot index $k=0$. Let ST $i$ be such that
  \[q_{ki} = \max_{l = 1\dots m}\{q_{kl}\}\] i.e., The ST with longest
  voice queue at the beginning of slot $k$ is $i$. Form activation
  vector $\mathbf{u}$ with link $i$ activated. i.e., $\mathbf{u} =
  \{i\}$
\item{}Let ST $j$ be such that 
  \[q_{kj} = \max_l\{{q_{kl}: l\notin{\cal{I}}(\mathbf{u})}\}\] $j$ is
  such that it is the non interfering ST with maximum queue length.
  Augment s with link $j$. Now, find ${\cal{I}}(\mathbf{u})$
  corresponding to the new $\mathbf{u}$.
\item{}Repeat step 3 until activation vector that we get is a maximal
  activation vector.
\item{}Let \[n = \{ q_{kl}:\min_{l=1,\dots,m}(q_{kl},l\in
  \mathbf{u})\}\] i.e., $n$ is the minumum number of slots required
  for the first ST in $\mathbf{u}$ to complete its transmission.  Use
  $\mathbf{u}$ in the schedule from $k$th to $(k+n)$th slot.
  \[q_{k+n,i}=\left\{\begin{array}{ccc} q_{k,i}-n &~~~~ \textrm{for}~~~~ &i \in \mathbf{u'}\\
      q_{k,i} &~~~~\textrm{for} ~~~~& i \notin \mathbf{u'}
   \end{array}\right.\]
 and $k = k+n$ i.e., slot index advances by $n$, and the queue length
 for the STs at the beginning of $k+n$th slot is $n$ less
\item{}At the end of $k+n$th slot,
  \[\mathbf{u} = \mathbf{u} - \{l: q_{kl} = min(q_{kl}, l \in
  \mathbf{u})\}\] i.e., remove from the activation vector, those STs
  that have completed their voice slot requirement.
\item{} Go back to Step 3 and form maximal activation vector including
  $\mathbf{u}$. Continue the above procedure until $\mathbf{q} =
  \mathbf{0}$ or $n = N_U$ In this step, we form a new activation
  vector with the remaining STs in the activation vector (which need
  more slots to complete their requirement).
\item{} Once the voice packets are transmitted, we serve the TCP
  packets in the same way, except that if in forming a maximal
  activation set, it is found that the only schedulable ST has only
  TCP packets to send, then TCP packets are scheduled.
\end{enumerate}
If $\mathbf{q}>\mathbf{0}$ when $n =N_U$ , the allocation is
infeasible.  \hfill

\subsection{A Greedy Heuristic Scheduler for the Downlink}
The difference of the downlink scheduling problem from the uplink
scheduling problem is that in downlink, a transport block can contain
packets to multiple STs. By combining the voice packets to different
STs to a single TB, we save considerable PHY overhead. For
transmitting a single voice packet needs 4 slots, where 3 slots are
for the PHY header. Transmitting 2 voice packets need only 5 slots. So,
it is always advantageous to have transmissions in longer blocks.
This can be done by grouping together the STs to those which are
heard only by $i$th BTS, those heard by $i$th and $(i-1)$th BTS, but
associated to the $i$th BTS and those heard by $i$th and $(i-1)$th
BTS, but associated to the $(i-1)$th BTS, for all values of $i$. 

For example in Figure~\ref{fig:dep} STs 3 and 4 are associated with
BTS 1 and hears only form BTS 1. So, any ST in the interference set of
3 will also be in the interference set of 4. Any transmission to ST 3
can equivalently be replaced by a transmission to 4. So, they form a
group for the down likn schedule. Similarly, STs 8 and 9 are
associated to BTS 2 and interfere with BTS 3. They are associated to
the same BTS and cause interference to the same STs. So, ST 8 and 9
also form a group.

\begin{figure}[htb]
  \centering \
  \psfig{figure=./figures/deploymenteg.eps,width=40mm,height=40mm}
  \caption{Typical deployment of a system with 3 sectors and 15 STs}
  \label{fig:dep}
\end{figure}

The STs are grouped together based on the above criterion. The queue
length of each group would be the sum of queue lengths of the STs
forming the group. The greedy heuristic scheduler for the uplink
scheduling problem can then be used over these groups.  This is made
clearer in Example~\ref{example:downlink}

\subsection{Round Robin Scheduling}
A scheduler with least complexity can be designed as follows. The
uplink and downlink parts of the frame may further be divided into two
contigous parts. Alternate sectors are served in these two parts. For
example, Sectors 1, 3, 5 are served in the first part, and Sectors 2,
4, 6 can be served in the second part of the frame. Interference
between adjacent sectors can be eliminated in this way. With the
number of sectors close to $2n_0$, performance of this scheduler would
be equivalent to that of the scheduler discussed in
Section~\ref{greedy_alg}, since we can have $n_0$ transmissions going
on in each slot, with this scheduler. But, with $n_0=4$, this would
require 8 sectors in the system. With number of sectors less than
$2n_0$, the number of simultaneous transmissions would be less than
$n_0$ with the round robin algorithm, where as we can have upto $n_0$
transmissions with the greedy algorithm.

\subsection{Fair Scheduling}
\label{section:fairscheduling}
Having all voice transmission in the beginning and data afterwards is
wasteful in terms of overhead. Following the principle of having
longer TBs, it is advantageous to have the voice and data tranfer to
an ST in a block. To provide fairness to users, keep track of the
average rates allocated to STs over time.  The STs with low average
rate over frames are given a chance to transmit first. Maximal
independent sets are formed starting from the ST with the lowest
average rate. Once the slots for voice transmission are scheduled, the
attempt should be to have TCP transmission in blocks of size
$T_{max}$, so that PHY overhead per slot is minimised.

Let $\mathbf{R}_k$ be the vector of average rates allocated to STs
till the $k$th frame and $\mathbf{r}_k$ be the vector of rates
allocated to the STs in the $k$th slot, i.e, the fraction of slots
allocated to STs in the $k$th frame.  The avrage rate acheived by the
STs is obtained by computing the following geometrically weighted
average.A large value of $\alpha$ places lees weight on the previous
frames.
\[\mathbf{R}_{k+1} =\alpha\mathbf{R}_k + (1-\alpha)\mathbf{r}_k\]



\begin{enumerate}
\item Given a rate vector $\mathbf{R}$, obtain a maximal independent
  set as follows
  \begin{enumerate}
  \item
    $\mathbf{u}_1=\{i_1\}$\\
    $i_1 =\mathrm{arg}\min_{1\leq j \leq n} \mathbf{R}_j$\\
    ${\cal{I}}(\mathbf{u}_1)$ is the set
    of links interfering with the links in $\mathbf{u}_1$. In this
    step, we select the ST with the smallest average rate $R_k$ for
    transmission.
  \item Choose $i_2 \in \mathrm{arg}\min_{1\leq j \leq n,i_2 \notin {\cal{I}}(\mathbf{u_1}) } \mathbf{R}_j $\\
    $\mathbf{u}_1=\{i_1,i_2\}$.  In this step, we select one of the
    non interfering STs with minimum average rate for transmission.
  \item Repeat the above until a maximal independent set is obtained.
    Now, we have a set with STs which have received low average rates
    in the previous slots. So, once all STs transmit their voice
    packets, we schedule these STs for data packets.
  \end{enumerate}
\item Let $l_1$ denote the number of nodes in $\mathbf{u_1}$ at the
  end of step 1.  Repeat the above for the remaining $n-l_1$ nodes.
  Now we have a maximal independent set from the remaining $N_u-l_1$
  nodes. If any one of the $l_1$ nodes can be activated along with the
  maximal independent set formed from the $N_u-l_1$ nodes, add that
  till one get a maximal independent set. This yields
  $\mathbf{u}_1,\mathbf{u}_2 \ldots \mathbf{u}_k$ such that each node
  is included atleast once. Each node is included atleast once
  since a given number of slots is to be reserved for each ST in
  every frame.
\item Now, we need to schedule $\mathbf{u}_1$ for $t_1$,
  $\mathbf{u}_2$ for $t_2$, etc. To maximize throughput, we take $t_j
  = T_{max}$ or number of voice slots required. The vectors in the
  initial part of the schedule had low average rate over frames. So,
  they get priority to send data packets. So, starting from $j$=1,
  i.e., from the first activation vector, if the sum of number of
  slots allocated to STs in the frame is less than $N_u$, $t_j =
  T_{max}$. Else, $t_j =$ number of voice slots required.Therefore
  transmission takes place in blocks of length equal to $T_{max}$ as
  long as it is possible.
\item Update the rate vector as
\[\mathbf{R}_{k+1}=\alpha\mathbf{R}_k+(1-\alpha)\mathbf{r}_k\] 
\end{enumerate}


\section{Design Methodology: Examples}
\label{section:designmethodology}

The deployment considered in the examples are described by the
$\mathbf{A}$ and $\mathbf{I}$ matrices given in Table~\ref{table:deployment}. The
$\mathbf{A}$ matrix shows the BTS to which each ST is associated.
Columns in both matrices correspond to sectors and rows correspond to
STS. $\mathbf{A}_{ij}=1$ indicates that the $i$th ST is associated to
the $j$th BTS. Each ST is associeted to one and only one BTS.
$\mathbf{I}_{ij}=1$ indicates that the $i$th ST can hear from the
$j$th BTS. An ST might hear from more than one BTS.


\begin{example}
\label{example:equalvoiceload}
\end{example}
\textbf{Equal Voice Load}

In this example there are 40 stations in 5 sectors. Any station within
$72\,^{\circ}$ is associated with the BTS and any station within
$32\,^{\circ}$ of the center of a mainlobe can cause interference at
that BTS.  We take the maximum burst length, $T_{max}$ to be 15 and
$N_U = 112$. Voice packet ( including MAC header) is 44 bytes long.
So, each voice packet requires one slot time for transmission. In this
example, we take $n_0=4$.

Consider all stations to have the same voice slot requirement of 4
packets.  The uplink transmission from each station could be done in a
single block , which requires a total of 3 slots of overhead. So, the
schedule should give at least 7 slots for each station. One schedule
that attains this, (as obtained Algorithm~\ref{alg:greedy_alg}) is given
by $\mathbf{S}_2$.



\begin{table}
  \label{table:deployment}
  \begin{tabular}{llll}
    \scriptsize{$\mathbf{A} =\left[\begin{array}{ccccc}
          1&0&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\\1&0&0&0&0\\1&0&0&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0
          \\0&0&1&0&0\\0&0&0&1&0\\0&0&1&0&0\\0&0&1&0&0\\1&0&0&0&0\\1&0&0&0&0\\0&1&0&0&0\\0&1&0&0&0\\0&0&0&1&0\\0&1&0&0&0\\0&0&0&1&0
          \\0&0&0&0&1\\0&0&1&0&0\\0&0&0&0&1\\0&0&0&0&1\\0&0&0&0&1\\1&0&0&0&0\\0&0&0&0&1\\0&0&0&0&1\\1&0&0&0&0\\1&0&0&0&0\\0&0&0&1&0
          \\0&0&0&1&0\\0&0&0&1&0\\0&0&0&1&0\\0&0&0&1&0\\0&0&0&0&1\\0&1&0&0&0\\0&0&1&0&0\end{array}\right]$}

    \scriptsize{$\mathbf{I} =\left[\begin{array}{cccccc}
          \\1&0&0&0&1\\0&1&0&0&0\\0&0&0&1&1\\0&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\\1&0&0&0&0\\1&0&0&0&0\\1&0&0&0&1\\1&1&0&0&0\\0&0&1&0&0
          \\0&0&1&0&0\\0&0&0&1&0\\0&0&1&1&0\\0&0&1&0&0\\1&0&0&0&0\\1&1&0&0&0\\0&1&1&0&0\\0&1&0&0&0\\0&0&0&1&1\\0&1&0&0&0\\0&0&1&1&0
          \\1&0&0&0&1\\0&0&1&0&0\\0&0&0&0&1\\0&0&0&1&1\\0&0&0&0&1\\1&0&0&0&0\\0&0&0&1&1\\0&0&0&0&1\\1&0&0&0&0\\1&0&0&0&0\\0&0&0&1&1
          \\0&0&0&1&0\\0&0&0&1&0\\0&0&0&1&0\\0&0&0&1&0\\0&0&0&0&1\\0&1&0&0&0\\0&1&1&0&0;
        \end{array}\right]$}

    \scriptsize{${\mathbf{Q}}_1 =\left[\begin{array}{ccccc}
          3\\2\\3\\4\\5\\5\\2\\4\\4\\5\\3\\2\\5\\2\\4\\5\\5\\4\\4\\5\\3
          \\2\\4\\4\\3\\5\\5\\3\\4\\5\\2\\5\\4\\5\\5\\3\\3\\2\\5\\4
        \end{array}\right]$}

    \scriptsize{$\mathbf{\cal{S}}_1 =\left[\begin{array}{ccccccccc}
          \\0&10&15&6&5&7&28&0\\0&10&24&6&5&1&4&0\\16&0&24&13&27&6&24&0\\16&39&0&13&27&2&8&0\\32&39&11&20&0&6&24&0
          \\32&4&12&20&0&2&8&0\\8&4&12&0&26&3&12&0\\8&4&11&0&26&2&6&2\\8&19&11&0&26&2&6&2\\28&19&11&0&26&1&3&1\\
          28&19&0&34&30&4&16&0\\28&18&0&34&30&1&4&0\\7&18&0&34&30&3&12&0\\7&18&0&35&25&2&8&0\\31&18&0&35&25&1&4&0
          \\31&0&40&35&25&3&12&0\\31&0&40&35&38&1&4&0\\7&0&40&35&38&1&3&1\\7&0&40&36&38&2&6&2\\17&0&11&36&38&1&3&1
          \\17&0&11&36&38&3&6&6\\17&0&11&37&38&4&8&8\\9&21&11&37&0&2&6&2\\9&21&11&37&0&4&8&8\\9&2&11&37&0&1&2&2\\
          0&2&11&37&23&4&8&8\\0&2&11&37&23&3&21&7\\7&2&11&0&29&7&21&7\\7&2&11&33&0&7&21&7\\1&2&11&33&0&6&18&6\\
          1&2&11&3&0&6&18&6\\1&2&14&0&0&5&15&5\\1&2&0&22&0&5&15&5
        \end{array}\right]$}   \\
    \scriptsize{${\mathbf{Q}}_2 =\left[\begin{array}{ccccc}
          4\\4\\4\\\vdots\\4
        \end{array}\right]$}

    \scriptsize{$\mathbf{\cal{S}}_2 =\left[\begin{array}{ccccccccc}
          \\1&2&11&6&0&7&28&0\\7&4&12&3&0&7&28&0\\8&0&15&13&5&7&28&0\\9&19&24&34&0&7&28&0\\
          0&10&11&35&25&7&28&0\\16&21&14&0&27&7&28&0\\17&0&11&36&30&7&21&7\\28&18&0&37&38&7&28&0
          \\31&39&11&20&0&7&21&7\\32&39&0&22&5&7&21&7\\0&39&0&22&23&7&7&14\\7&39&11&0&26&7&7&21
          \\7&39&11&0&29&7&21&7\\7&39&11&33&0&7&21&7\\7&0&40&33&0&7&14&7
        \end{array}\right]$}
  \end{tabular}
  \caption{Data and results for the Example~\ref{example:equalvoiceload} and~\ref{example:unequalvoiceload}.
    $\mathbf{\cal{S}}_i$ is the schedule for voice slot requirements given
    by $\mathbf{Q}_i, i \in \{1,2\}$. Note that the last two columns of 
    $\mathbf{\cal{S}}_i$ are the total number of slots in all sectors for
    voice and TCP packets respectively scheduled in each row.}
\end{table}

The first 5 columns of the matrix $\mathbf{S}_2$ gives the links that
can transmit in each sector. A $0$ indicates that there cannot be a
transmission by any of the stations in this sector without causing
interference to at least one of the ongoing transmissions. The entries
in the 6th column indicates the number of consecutive slots for which
these vector is used in the schedule. The 7th column is the number of
slots (over all the sectors) used for transmitting voice packets. The
last column shows the number of slots, over all the sectors used for
transmitting TCP packets.

For example, consider the first row of $\mathbf{S}_2$. This indicates
that the ST 1 from Sector 1, 2  from Sector 2, 11 from Sector 3, 6
from Sector 4 and none from Sector 5 are scheduled for the first 7
slots. At the end of 7 slots, the voice queues of these stations are
exhausted, so we schedule other stations.

From $\mathbf{S}_2$, one sees that ST 40 gets a chance for transmission
only in the last row, i.e., by the 98th slot. It transmits till the
105th slot to complete transmitting its voice queue. This indicates
that the scheduling of voice queues requires 105 slots.


In the 1st row, ST 11 has been scheduled for 7 slots. So the voice
queue of ST 11 is exhausted by the end of that row. But, since there
are no other STs in Sector 3, that can use the slot for voice
transmission, we schedule ST 11 for TCP transmission further in the
schedule. In this algorithm, priority is to STs that had been
transmitting in the previous slot, and next priority to stations with
lower index. But,  better fairness can be ensured by round robining
between the STs in a sector.

Since the voice queue of ST 11 is exhausted by the end of 1st row in
$\mathbf{\cal{S}}_2$ the ST 11 scheduled after 1st row, i.e., from
29th slot is for TCP transmission. Similarly, ST 7 scheduled after
the 11th row, ST 39 scheduled after 9th row etc.  are  for TCP transmission.

In this example, 4 STs transmit in each slot ( i.e.,
$3\times26$ slots of transmission.). Thereby,
of the $112\times5$ slots available ( since in each slot, at most one
ST from a sector can transmit.),$112\times4$  slots are used for
transmission, giving a throughput of 78\% and a goodput efficiency
of 46\%. In this schedule, transmission of TCP packets occur in 105
slots.

\begin{example}
\label{example:unequalvoiceload}
\end{example}
\textbf{Unequal Voice Load}

Also given is the schedule obtained by the Algorithm~\ref{alg:greedy_alg},
when the voice slot requirements are different for different stations.
Given is one such vector ($\mathbf{Q}_1$) and the corresponding
schedule ($\mathbf{S}_1$).
 

In the example, in the first row, i.e., links 10,15,6,5 are
scheduled for the first 7 slots. At the end of the 7th slot, ST 15
exhausts its voice queue.  So, remove ST 15 from
the vector, and add ST 24 which can take its place. This continues
till one of the other queues become empty. Then, remove the one
whose queue is empty, and schedule some other ST which does not
interfere with the ongoing transmissions, and so on till all STs are
served.


All the STs get a chance to transmit by the last row of the given
schedule. But, the last row finishes transmission by the 108th slot
(as seen by summing up the last column of $\mathbf{S}_1$). The slots
from 108 to 112 may be used for transmitting TCP packets for the STs
in the last row. Here, the  throughput  78\% and a goodput efficiency of
46\%. In this schedule, transmission of TCP packets occurs in 147
slots.

\begin{example}
\label{example:downlink}
\end{example}
\textbf{Downlink} \\
In downlink, transmission to multiple STs can be done in a block.  In
the deployment in this example, STs 2, 4, 19, 21, 39 all hear only
from BTS~2. This can be seen from the $\mathbf{A}$ and $\mathbf{I}$
matrices. All these STs have 1 in the second column, indicating that
they are associated to BTS 2. The $\mathbf{I}$ matrix has 1s only in the
seccond column, indicationg that they hear only from BTS 2. These are
grouped in to $b$. The transmissions to these STs can take place in a
TB, since an ST which interferes with any ST in $h$ will interfere
with every other ST in $h$, and vice versa. So every ST in $h$ is
equivalent with respect to interference constraints. An $h$ occuring
in the schedule in Table~\ref{table:downlink} indicates a transmission
to this group of STs. The STs which are in the same group are
associated to the same BTS and are in the exclusion region of same
sectors. The groups so formed for the example are given in
Table~\ref{table:downlink}.  Similarly, the STs 3,20 and 33 hear from
BTSs 4 and 5; all of them are associated to BTS~4. They are grouped to
$c$. All STs in $c$ are equivalent with respect to the interference
constraints. The transmissions to these STs can occur in a TB. Now,
the voice slot requirement of a group is the sum of the voice slot
requirements of individual STs constituting the group. The same
algorithm as for the uplink is then used over the groups
$a,b,c,d,\dots$ with their respective queue lengths to obtain the
schedule in downlink.  Aggregating STs in the association and
exclusion regions of each BTS like this has the advantage of
increasing the overall system throughput, since transmissions occur in
longer TBs. The goodput efficiency in downlink is about 64\%.

\begin{table}[htb]
  \begin{tabular}{ccc}
    \scriptsize{${\mathbf{Q}_{2d}} =\left[\begin{array}{cc}2\\2\\ \vdots \\2   \end{array}\right]$}
    &
    \scriptsize{$\mathbf{\cal{S}}_{2d} =\left[\begin{array}{ccccccc}
          f&b&0&e&d&31\\f&b&h&e&0&5\\f&b&h&c&0&18\\a&b&h&c&0&13\\f&b&h&0&n&13\\0&g&h&0&n&8
          \\0&g&i&0&n&8\\j&0&i&0&n&8\\f&k&0&0&n&8\\f&k&0&l&d&8\\0&k&0&l&m&8\\0&0&o&e&m&8
        \end{array}\right]$}
    &
    \scriptsize{$\begin{array}{lll}a = \{1,9\} & b=\{2,4,19,21,39\} & c=\{3,20,33\}\\
        d=\{5,25,27,30,38\}& e=\{6,13,34,35,36,37\}& f=\{7,8,16,28.31.32\}\\ g=\{10\}& h=\{11,12,15,24\}&  i=\{14\}\\ 
        j=\{17\}& k=\{18\}& l=\{22\}\\ m=\{23\}& n=\{26,29\}& o=\{40\}\end{array}$}

  \end{tabular}
  \caption{The part of the downlink schedule for completing the voice slot 
    requirement when 2 slots are reserved for voice transmission from each ST. }
  \label{table:downlink}
\end{table}

\vspace*{2in}
\newpage
\addtocounter{section}{-2}
% -------------------------------------------------------------------------
\section*{ANNEX D: Simulation Analysis}
\label{section:throughput}

The fair scheduling algorithm and the round robin algorithm discussed
in ANNEX C were implemented in MATLAB.
The voice and data capacity of the system using these algorithms is provided in
this section.

\section{Simulation Scenario}
We consider the distribution of $n$ STs in $m$ sectors. Results for
different values of $m$ and $n$ are given. All STs are assumed to be
carrying the same number of voice calls. One VOIP call requires one
slot every alternate frame. A voice packet that arrives in the system
is scheduled within the next two frames. If the system capacity and
scheduling constraints do not allow the voice packet to be transmitted
within two frame times of its arrival, the packet is dropped. In this
simulation, we assume synchronous arrival of voice packets. i.e., if
two voice calls are going on from an ST, packets for both calls arrive
synchronously, in the same frame. The data throughput considered is
the saturation throughput, i.e., the STs have packets to be
transmitted throughout. All STs have infinite queues and the schedule
is driven by the average rates obtained over time. The STs which
received low service rates in the previous frames are scheduled
first.(See ANNEX C, Section~\ref{section:fairscheduling})

\begin{table}[!hp]
\centering \	
\begin{tabular}{|c|c|c|c|c|c|}
  % \centering \
\hline
& &  \multicolumn{4}{c|}{ \scriptsize{Number of voice calls per station}} \\
\hline
{\scriptsize{$\begin{array}{c}\mathrm{number~ of~ sectors},\\ \mathrm{number~ of ~sSTs},\\ n_0 \\\mathrm{width~ of~ taboo~ region},\theta \end{array}$}}
 &  &  {\scriptsize{1}} &  \scriptsize{2} & \scriptsize{3} & \scriptsize{4} \\
 \hline
%%%%%%%%%%%%%%%%%%%%%
  % 6,40,3 %
%%%%%%%%%%%%%%%%%%%%%
\scriptsize{6, 40, $n_0$=3, $\theta=10^\circ$}&
  \scriptsize{$\begin{array}{c}\mathrm{ min~ d/l~ rate}\\\mathrm{ max~ d/l~ rate} \\\mathrm{ sum ~d/l~ rates}\\ \end{array}$} &  
  \scriptsize{$\begin{array}{c} 0.0507\\ 0.0557 \\2.1379   \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0504\\ 0.0545 \\2.0909    \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0486 \\0.0538  \\2.0342    \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0453 \\ 0.0524 \\ 1.9766   \end{array}$}\\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0337\\ 0.0733 \\ 2.0641\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c}  0.0288 \\ 0.0636\\ 1.8120 \\ 0\end{array}$}&
\scriptsize{$\begin{array}{c}  0.0277 \\ 0.0578\\ 1.6330\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c}  0.0203 \\ 0.0511\\ 1.4013\\ 0 \end{array}$}\\
 \hline
\scriptsize{6, 40, $n_0$=3, $\theta=20^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0507\\ 0.0547 \\2.1086    \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0487 \\0.0552\\2.0574     \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0472\\0.0535  \\2.0171    \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0452 \\ 0.0528 \\1.9272   \end{array}$} 
 \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0347\\ 0.0712 \\ 2.0544\\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0299\\ 0.0664 \\ 1.8157\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0238\\ 0.0596\\ 1.6002\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0190\\ 0.0547 \\ 1.3898\\ 0 \end{array}$}\\
 \hline
 \scriptsize{6, 40, $n_0$=3, $\theta=30^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0526 \\0.0633  \\ 2.0865  \end{array}$}&  
 \scriptsize{$\begin{array}{c}0.0479 \\ 0.0613 \\2.0023  \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0472 \\0.0570  \\ 1.9881  \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0437 \\ 0.0598 \\  1.9740  \end{array}$} \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0298\\  0.0843 \\ 2.0484\\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0276\\ 0.0759 \\ 1.8204\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0208\\ 0.0749 \\ 1.5909\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0172\\ 0.0624 \\ 1.3926\\ 0 \end{array}$}\\
 \hline 

%%%%%%%%%%%%%%%%%%
  % 6,60,3 %
%%%%%%%%%%%%%%%%%%
 \scriptsize{6, 60, $n_0$=3, $\theta=10^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0326 \\ 0.0380 \\ 2.0792   \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0312 \\ 0.0359 \\2.0034   \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0297 \\ 0.0339 \\ 1.8873 \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0270 \\ 0.0322  \\1.7249  \end{array}$}
 \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0137\\ 0.0448 \\ 1.4863\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0094\\ 0.0357 \\1.2020 \\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0050\\ 0.0274 \\ 0.8714\\ 0.0022 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0026\\  0.0197\\ 0.6368\\ 0.0156 \end{array}$}\\

 \hline
 \scriptsize{6, 60, $n_0$=3, $\theta=20^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0325 \\0.0363  \\ 2.0472  \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0317 \\ 0.0368 \\1.9924  \end{array}$}&
 \scriptsize{$\begin{array}{c} 0.0293\\0.0340  \\1.8861  \end{array}$}&
 \scriptsize{$\begin{array}{c} 0.0267\\ 0.0321 \\1.7338  \end{array}$}
 \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0130\\ 0.0444 \\1.5189 \\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0091\\   0.0398\\ 1.2006\\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0055\\  0.0291\\ 0.9036\\0.0029  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0018\\  0.0198\\ 0.6327\\ 0.0167 \end{array}$}\\

 \hline
 \scriptsize{6, 60, $n_0$=3, $\theta=30^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
 \scriptsize{$\begin{array}{c} 0.0338\\ 0.0375 \\2.1148   \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0326 \\ 0.0358 \\ 2.0344   \end{array}$}&
 \scriptsize{$\begin{array}{c} 0.0293 \\0.0337  \\1.8997  \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0260 \\0.0318  \\1.7368   \end{array}$}
 \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0139\\ 0.0452 \\  1.4985\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c}  0.0087\\ 0.0360 \\1.1587 \\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0049\\ 0.0326 \\0.9299 \\ 0.0033 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0257 \\0.6301 \\0.0179  \end{array}$}\\

%%%%%%%%%%%%%%%%%%%%%
  % 6,80 ST n0=3 %
%%%%%%%%%%%%%%%%%%%%
\hline

 \scriptsize{ 6,80,$n_0$=3,$\theta=10^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \end{array}$} &
 \scriptsize{$\begin{array}{c} 0.0244\\ 0.0265 \\  2.0453  \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0220 \\ 0.0271 \\ 1.9118 \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0200 \\ 0.0248 \\1.7390  \end{array}$}&
 \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
  \\

\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c}0.0056 \\0.0245  \\ 1.0388\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0025\\ 0.0160 \\0.6563 \\ 0.0029 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\  0.0091\\ 0.3505\\ 0.0229 \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
 \hline

 \scriptsize{ 6,80,$n_0$=3,$\theta=20^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}   \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0242 \\0.0267  \\2.0150   \end{array}$}&                
  \scriptsize{$\begin{array}{c}0.0224 \\ 0.0257 \\ 1.9039  \end{array}$}&                
  \scriptsize{$\begin{array}{c}0.0203 \\0.0263  \\1.7552  \end{array}$}&
  \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
  \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0048\\  0.0252 \\1.0604 \\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\0.0185 \\ 0.6305\\ 0.0033 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0097 \\0.3352 \\ 0.0312 \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
  \hline

 \scriptsize{ 6,80,$n_0$=3,$\theta=30^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}   \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0249 \\ 0.0268 \\ 2.0653   \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0228 \\ 0.0258 \\1.9339 \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0204 \\ 0.0240 \\1.7480  \end{array}$}&
  \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0045\\ 0.0249 \\ 1.0319\\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0022\\ 0.0174 \\ 0.6797\\ 0.0042 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\  0.0114\\ 0.3399\\0.0346  \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\

  \hline
\end{tabular}
\label{table:gs1throughput1}
\caption{The average throughput per ST averaged over 30 random deployments. The data throughputs are tabulated for different number of sectors, number of STs, width of taboo region and $n_0=3,4$. Throughputs are in terms of fraction of uplink or downlink bandwidth respectively }
\end{table}

%\begin{table}[!hp]
%\centering \
%  \begin{tabular}{|c|c|c|c|c|c|}
%    %\centering \
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  \\

%%%%%%%%%%%%%%%%%%%%%
  % 6,100ST,n0=3 %
%%%%%%%%%%%%%%%%%%%%%

%\end{tabular} 
%\label{table:gs1throughput2}
%\caption{The average throughput per ST averaged over 30 random deployments. The data throughputs are tabulated for different number of sectors, number of STs, width of taboo region and $n_0=3,4$(Contd) }
%\end{table}

\begin{table}[!hp]
\centering \
  \begin{tabular}{|c|c|c|c|}
    %\centering \
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hline
& &  \multicolumn{2}{c|}{ \scriptsize{Number of voice calls per station}} \\
\hline
{\scriptsize{$\begin{array}{c}\mathrm{number~ of~ sectors},\\ \mathrm{number~ of ~sSTs},\\ n_0 \\\mathrm{width~ of~ taboo~ region},\theta \end{array}$}}
 &  &  {\scriptsize{1}} &  \scriptsize{2}  \\
\hline
 \scriptsize{6, 100, $n_0$=3, $\theta=10^\circ$}&
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \\ \end{array}$} &
 \scriptsize{$\begin{array}{c}0.0187 \\ 0.0219 \\ 2.0074 \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0168 \\ 0.0202 \\ 1.8184 \end{array}$}
 \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0011\\ 0.0146 \\ 0.6103\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0068 \\0.2755 \\0.0250  \end{array}$}
\\
\hline
  \scriptsize{6, 100, $n_0$=3, $\theta=20^\circ$}&
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \\ \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0192 \\ 0.0217 \\2.0010  \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0174 \\ 0.0202 \\1.8327  \end{array}$}
  \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0010\\0.0129 \\ 0.5927\\0.0017  \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0063 \\ 0.2576\\0.0237  \end{array}$}\\
  \hline
  \scriptsize{6, 100, $n_0$=3, $\theta=30^\circ$}&
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0194\\0.0211  \\ 2.0005  \end{array}$}&
 \scriptsize{$\begin{array}{c}0.0173 \\ 0.0205 \\1.8133  \end{array}$}
  \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c}0\\ 0.0142 \\ 0.5860\\ 0.0037 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0098 \\0.3040 \\0.0233  \end{array}$}\\

%%%%%%%%%%%%%%%%%
 % 6,120ST,n0=3 %
%%%%%%%%%%%%%%%%%


\hline
\scriptsize{6, 120, $n_0$=3, $\theta=10^\circ$}&
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \end{array}$} &
\scriptsize{$\begin{array}{c}0.0155\\0.0184\\1.9903\end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
\\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0057 \\0.2305 \\0.0231  \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
\hline
\scriptsize{6, 120, $n_0$=3, $\theta=20^\circ$}&
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}   \\ \end{array}$} &
\scriptsize {$\begin{array}{c}0.0157 \\0.0174  \\1.9538  \end{array}$}&
\scriptsize {$\begin{array}{c} \\  \\ \\ \end{array}$}  
\\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate}\\ \mathrm{packet~drop~u/l} \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0052 \\0.2177 \\0.0230  \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\

\hline
\scriptsize{6, 120, $n_0$=3, $\theta=30^\circ$}&
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \\ \end{array}$} &
\scriptsize{$\begin{array}{c}0.0139 \\ 0.0153 \\ 1.7393 \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\

\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0052 \\0.2117  \\0.0394  \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
\hline
\end{tabular}
\label{table:gs1throughput3}
\caption{The average throughput per ST averaged over 30 random deployments. The data throughputs are tabulated for different number of sectors, number of STs, width of taboo region and $n_0=3,4$(Contd) }
\end{table}

\begin{table}[!hp]
\centering \
\begin{tabular}{|c|c|c|c|c|c|}
  % \centering \
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \hline
  & &  \multicolumn{4}{c|}{ \scriptsize{Number of voice calls per station}} \\
  \hline
  {\scriptsize{$\begin{array}{c}\mathrm{number~ of~ sectors},\\ \mathrm{number~ of ~sSTs},\\ n_0 \\\mathrm{width~ of~ taboo~ region},\theta \end{array}$}}
  &  &  {\scriptsize{1}} &  \scriptsize{2} & \scriptsize{3} & \scriptsize{4} \\
%%%%%%%%%%%%%%%%%%%%%
  % 6,40,3 %
%%%%%%%%%%%%%%%%%%%%%
  \hline     
  \scriptsize{6, 40, $n_0$=4, $\theta=10^\circ$} &
  \scriptsize{$\begin{array}{c} \mathrm{min~ d/l~ rate}\\\mathrm{ max ~d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0658 \\0.0808 \\2.9443   \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0658 \\  0.0782\\2.8665   \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0661 \\0.0772  \\ 2.8532 \end{array}$}&
  \scriptsize{$\begin{array}{c}  0.0632\\0.0777 \\2.7495   \end{array}$}
  \\
  \cline{2-6}
  &\scriptsize{$\begin{array}{c} \mathrm{min ~u/l ~rate}\\ \mathrm{ max~ u/l~ rate}  \\ \mathrm{sum~u/l~rate} \\ \mathrm{packet~ drop~ u/l}\end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0452\\ 0.1214 \\ 2.9113\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0371\\  0.1125\\ 2.6910\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0333\\ 0.1027 \\ 2.4730\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0256\\  0.1029\\2.3426 \\ 0 \end{array}$}\\
  \hline
  \scriptsize{ 6, 40, $n_0$=4, $\theta=20^\circ$} &
  \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}   \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0616\\ 0.0866 \\ 2.9434   \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0607\\ 0.0756 \\ 2.7094  \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0606\\0.0758  \\2.6901   \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0587\\ 0.0708 \\ 2.5764  \end{array}$}\\
  \cline{2-6}
  &\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
  \scriptsize{$\begin{array}{c}0.0405 \\ 0.1462 \\ 2.7302\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0338\\ 0.1526 \\ 2.4593\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0267\\ 0.1491 \\ 2.3504\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0219\\ 0.1513 \\ 2.1716\\ 0 \end{array}$}\\
  \hline
    
  \scriptsize{ 6, 40, $n_0$=4, $\theta=30^\circ$} &
  \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0550\\ 0.0681 \\ 2.4473   \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0536 \\0.0666  \\2.3727   \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0530\\ 0.0653 \\2.3198   \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0480\\  0.0690\\  2.1754  \end{array}$}\\
    
  \cline{2-6}
  &\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0326\\0.1110  \\ 2.1184\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0277\\ 0.0923 \\ 1.8977\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0227\\ 0.0972 \\ 1.7520\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0173\\ 0.0866 \\ 1.5281\\ 0 \end{array}$}\\
  \hline
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 5%%%%%%%%%%5
  \scriptsize{6, 60, $n_0$=4, $\theta=10^\circ$} &
  \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0469 \\ 0.0556 \\3.0059    \end{array}$} &
  \scriptsize{$\begin{array}{c} 0.0436\\  0.0552 \\ 2.8453   \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0404\\ 0.0497\\ 2.6891 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0382\\ 0.0473 \\2.5362  \end{array}$}\\
  \cline{2-6}
  &\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0233\\0.0624  \\ 2.2345\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0144\\ 0.0602 \\ 1.8461\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c}0.0088 \\ 0.0513 \\ 1.5598\\ 0.0004 \end{array}$}&
  \scriptsize{$\begin{array}{c}  0.0022\\ 0.0484 \\ 1.3567\\0.0062  \end{array}$}\\
  \hline

  % \centering \
  \scriptsize{6, 60, $n_0$=4, $\theta=20^\circ$} &
  \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0465 \\ 0.0567 \\ 3.0010   \end{array}$} &
  \scriptsize{$\begin{array}{c}0.0429 \\ 0.0547 \\ 2.8456  \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0401\\ 0.0506 \\ 2.6901  \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0379\\0.0500  \\ 2.5312 \end{array}$}\\
  \cline{2-6}
  &\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0192\\ 0.0944 \\2.1408 \\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0126\\ 0.0870 \\ 1.7864\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0069\\ 0.0795 \\ 1.4975\\ 0 \end{array}$}&
  \scriptsize{$\begin{array}{c} 0.0039\\  0.0695\\ 1.2942\\ 0.0083 \end{array}$}\\
  \hline
   \hline
   \scriptsize{ 6, 60, $n_0$=4, $\theta=30^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}\\ \end{array}$} &
    \scriptsize{$\begin{array}{c} 0.0352\\0.0469  \\ 2.3692   \end{array}$} &
    \scriptsize{$\begin{array}{c} 0.0334\\ 0.0439 \\2.2139   \end{array}$}&
    \scriptsize{$\begin{array}{c}0.0305 \\ 0.0419 \\ 2.0396  \end{array}$}&
    \scriptsize{$\begin{array}{c} 0.0283\\0.0343  \\1.8635  \end{array}$}
    \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0139\\ 0.0521 \\ 1.5640\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0078\\  0.0490\\ 1.2581\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0033\\ 0.0417 \\ 0.9693\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0018\\ 0.0350 \\ 0.7319\\ 0.0083 \end{array}$}\\

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
    \hline
    \scriptsize{6, 80, $n_0$=4, $\theta=10^\circ$ }&
     \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates} \\ \end{array}$} &
     \scriptsize{$\begin{array}{c}0.0333 \\0.0438  \\2.9465    \end{array}$} &
     \scriptsize{$\begin{array}{c}0.0304 \\0.0413  \\2.7337 \end{array}$}&
     \scriptsize{$\begin{array}{c}0.0282 \\0.0384  \\ 2.5300 \end{array}$}&
     \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
    \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0105\\0.0292 \\ 1.4752\\0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0069\\ 0.0255\\1.1493 \\ 0.0029 \end{array}$}&
\scriptsize{$\begin{array}{c}0 \\ 0.0236\\ 0.9122\\0.0283 \end{array}$}&
\scriptsize{$\begin{array}{c} \\ \\ \\ \end{array}$}\\
    \hline
    \scriptsize{6, 80, $n_0$=4, $\theta=20^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0304\\ 0.0421 \\2.8728   \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0288 \\0.0380  \\2.6641   \end{array}$}&
     \scriptsize{$\begin{array}{c}0.0.0264 \\0.0408  \\2.4441  \end{array}$}&
     \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
    \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0069\\ 0.0399 \\1.4386 \\0  \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0022\\ 0.0389 \\ 1.1273\\ 0.0025 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0477 \\ 0.8810\\0.0304  \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\

 \hline
   \scriptsize{6, 80, $n_0$=4, $\theta=30^\circ$} &
\scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}   \\ \end{array}$} &
    \scriptsize{$\begin{array}{c}0.0256 \\ 0.0316 \\2.3167  \end{array}$} &
    \scriptsize{$\begin{array}{c} 0.0246\\ 0.0309 \\ 2.0943 \end{array}$}&
    \scriptsize{$\begin{array}{c} 0.0209\\  0.0282\\ 1.85944\end{array}$}&
    \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
    \\
\cline{2-6}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0040\\ 0.0263 \\ 1.0279\\ 0 \end{array}$}&
\scriptsize{$\begin{array}{c} 0.0016\\ 0.0205 \\ 0.6997\\ 0.0029 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0155 \\ 0.4316\\ 0.0254 \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\

\hline
\end{tabular}
\label{table:gs1throughput4}
\caption{The average throughput per ST averaged over 30 random deployments. The data throughputs are tabulated for different number of sectors, number of STs, width of taboo region and $n_0=3,4$ (Contd)}
\end{table}


\begin{table}[htb]
\centering \
  \begin{tabular}{|c|c|c|c|}
\hline
& &  \multicolumn{2}{c|}{ \scriptsize{Number of voice calls per station}} \\
\hline
{\scriptsize{$\begin{array}{c}\mathrm{number~ of~ sectors},\\ \mathrm{number~ of ~sSTs},\\ n_0 \\\mathrm{width~ of~ taboo~ region},\theta \end{array}$}}
 &  &  {\scriptsize{1}} &  \scriptsize{2}  \\
%%%%%%%%%%%%%%%%%%%%%
  % 6,40,3 %
%%%%%%%%%%%%%%%%%%%%%

  \hline
    \scriptsize{ 6, 100, $n_0$=4, $\theta=10^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0260\\  0.0324\\ 2.8934  \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0239\\ 0.0301 \\2.6314  \end{array}$}
   \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0035\\ 0.0176 \\ 0.9422\\0.0030  \end{array}$}&
\scriptsize{$\begin{array}{c}0\\ 0.0105 \\ 0.6522\\ 0.0250 \end{array}$}\\
 \hline
    \scriptsize{ 6,100,$n_0$=4,$\theta=20^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0257\\ 0.0332 \\  2.8303\end{array}$} &
     \scriptsize{$\begin{array}{c}0.0226 \\0.0315  \\2.5684 \end{array}$}\\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0.0017\\ 0.0318 \\0.9711 \\ 0.0023 \end{array}$}&
\scriptsize{$\begin{array}{c}0 \\ 0.0270 \\0.6803 \\ 0.0215 \end{array}$}\\
 \hline
    \scriptsize{ 6, 100, $n_0$=4, $\theta=30^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0210\\ 0.0250 \\2.2563 \end{array}$} &
     \scriptsize{$\begin{array}{c} 0.0181\\ 0.0240 \\1.9626 \end{array}$}
    \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0159 \\ 0.6055 \\ 0.0010 \end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0107 \\ 0.3280\\0.0280  \end{array}$}\\
\hline
    \scriptsize{6, 120, $n_0$=4, $\theta=10^\circ$} &
 \scriptsize{$\begin{array}{c} \mathrm{min ~d/l ~rate}\\\mathrm{ max~ d/l~ rate} \\ \mathrm{sum~ d/l~ rates}  \\ \end{array}$} &
     \scriptsize{$\begin{array}{c}0.0184 \\ 0.0269 \\2.5225  \end{array}$} &
     \scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}
    \\
\cline{2-4}
&\scriptsize{$\begin{array}{c} \mathrm{min~ u/l ~rate}\\ \mathrm{max~ u/l ~rate}  \\\mathrm{sum~ u/l~ rate} \\\mathrm{packet~drop~u/l}\end{array}$}&
\scriptsize{$\begin{array}{c} 0\\ 0.0099 \\ 0.5529\\ 0.0750 \end{array}$}&
\scriptsize{$\begin{array}{c} \\  \\ \\  \end{array}$}\\
\hline
\end{tabular}
\label{table:gs2throughput}
\caption{The average throughput per ST averaged over 30 random deployments. The data throughputs are tabulated for different number of sectors, number of STs, width of taboo region and $n_0=3,4$ (Contd)}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% ROUND ROBIN              %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{table}[htb]
\centering \	
\begin{tabular}{|c|c|c|c|c|c|}
  % \centering \
  \hline
  % & \multicolumn{3}{c|} {1} & \multicolumn{3}{c|} {2} & \multicolumn{3}{c|} {3} & \multicolumn{3}{c|} {4} \\
  && \multicolumn{4}{c|} {\scriptsize{Number of voice calls per station} }\\
  \hline
 \scriptsize{ no. of STs} && \scriptsize{1}&\scriptsize{2}&\scriptsize{3}&\scriptsize{4}\\
  \hline
  &\scriptsize{min d/l rate}&\scriptsize{0.0531}&\scriptsize{0.0508}&\scriptsize{0.0479}&\scriptsize{0.0457} \\
 \scriptsize{40} &\scriptsize{max d/l rate}&\scriptsize{0.0683}&\scriptsize{0.0657}&\scriptsize{0.0629}&\scriptsize{0.0604}\\
  &\scriptsize{sum d/l rates}&\scriptsize{2.2938}&\scriptsize{2.1899}&\scriptsize{2.0859}  &\scriptsize{1.9813}\\
  % \cline{2-5}
  % 40, 6, $n_0=3$, $\theta=10^\circ$&&&&\\
  % &&&&\\
  % &&&&\\
  % \cline{2-5}
  % &&&&\\
   \hline
  &\scriptsize{min d/l rate}&\scriptsize{0.0344}&\scriptsize{0.0319}&\scriptsize{0.0295} & \scriptsize{0.0267} \\
  \scriptsize{60} & \scriptsize{max d/l rate}&\scriptsize{ 0.0421}&\scriptsize{0.0390} & \scriptsize{0.0364} &\scriptsize{0.0341}\\
  &\scriptsize{sum d/l rates}& \scriptsize{2.2438}&\scriptsize{2.0875}&\scriptsize{1.9313} &\scriptsize{1.7750}\\
  % \cline{2-5}
  % 40, 6, $n_0=3$, $\theta=10^\circ$&&&&\\
  % &&&&\\
  % &&&&\\
  % \cline{2-5}
  % &&&&\\
  \hline
  &\scriptsize{min d/l rate}&\scriptsize{0.0255}&\scriptsize{0.0229}&\scriptsize{0.0202}& \\
 \scriptsize{ 80} &\scriptsize{ max d/l rate}&\scriptsize{ 0.0296}& \scriptsize{0.0271}&\scriptsize{0.0245}&\\
  &\scriptsize{sum d/l rates}&\scriptsize{2.1917}& \scriptsize{1.9833} &\scriptsize{1.7750}&\\
  % \cline{2-5}
  % 40, 6, $n_0=3$, $\theta=10^\circ$&&&&\\
  % &&&&\\
  % &&&&\\
  % \cline{2-5}
  % &&&&\\
  \hline
&  \scriptsize{min d/l rate}&\scriptsize{0.0199}&\scriptsize{0.0172}&\scriptsize{0.0147}& \\
 \scriptsize{ 100} &\scriptsize{ max d/l rate}&\scriptsize{ 0.0227} & \scriptsize{0.0202}& \scriptsize{0.0175}&\\
  &\scriptsize{sum d/l rates}&\scriptsize{ 2.1396}&\scriptsize{1.8792}&\scriptsize{1.6188}&\\
  % \cline{2-5}
  % 40, 6, $n_0=3$, $\theta=10^\circ$&&&&\\
  % &&&&\\
  % &&&&\\
  % \cline{2-5}
  % &&&&\\
  \hline
  & \scriptsize{min d/l rate}& \scriptsize{ 0.0110}&&& \\
  \scriptsize{ 120}& \scriptsize{ max d/l rate}& \scriptsize{0.0132}&&&\\
  &\scriptsize{sum d/l rates}& \scriptsize{1.4625}&&&\\
  % \cline{2-5}
  % 40, 6, $n_0=3$, $\theta=10^\circ$&&&&\\
  % &&&&\\
  % &&&&\\
  % \cline{2-5}
  % &&&&\\
  \hline
\end{tabular}
\label{table:rrthroughput}
\caption{The average data throughput per ST with round robin scheduler for number of sectors=6, number of STs 40, 60, 80, 100 and 120}
\end{table}
\normalsize

\section{Numeric Results}
Following the fair scheduling algorithm described earlier, the data throughputs attainable for
$n$ STs in $m$ sectors are calculated for different number of voice
calls, widths of taboo regions, $n$ and $m$. For each value of $n$,
$m$, width of taboo region ($\theta^\circ$), and voice call
requirement, the attainable data throughput is calculated in terms of
fraction of downlink bandwidth, for 30 different deployments and the
averages are tabulated. The minimum average throughput (in slots per
slot time) attained among the STs, the maximum average throughput
among STs, the sum of the average throughputs to STs and also the
probability of a voice packet being dropped are tabulated.
 
The first column of Tables 4 to 8 gives the number of sectors, number
of STs, width of taboo region and the maximum number of simultaneous
transmissions possible, $n_0$.  $minrate$ is the minimum average rate
over STs, averaged over random deployments, $maxrate$ is the maximum
average rate over STs, $sumrate$ is the sum of average rates to STs,
and the average fraction of voice packets dropped.

For example, one can see from Table 4 that for 40 STs in 6 sectors,
with a taboo region of width $10^{\circ}$ and $n_0=3$, the minimum
average downlink throughput provided to an ST is 0.0507 of the
downlink bandwidth. If one slot is reserved every two frames for voice
calls, the downlink bandwidth being 66\% of the total bandwidth of 11
Mbps, the ST gets 370 Kbps.  Similarly, if two slots are reserved per
ST every two frames, each ST receives an average of at least 369
Kbps. The average fraction of voice packets dropped is zero when the
number of STs is as small as 40.

As the number of STs goes up to 80, $n_0$ remaining as 3, one can
reserve at most 2 slot per ST in alternate frames, with acceptable
probability of dropping voice packets. With 80 STs, the probability of
dropping a voice packet is more than 2 percent when we reserve slots
for 2 calls per ST. With 80 STs, and slots reserved for one call per
ST, each ST gets at least 123kbps of downlink bandwidth. But the uplink
bandwidth is as small as 17 kbps. But, since the internet traffic in
predominantly downlink, the capacity required in the uplink is
small. 

The rates given in Tables 4 to 8 are in terms of fraction of uplink
of downlink bandwidth available for data transfer. Total uplink
bandwidth is one third of 11 Mbps and downlink bandwidth is two thirds
of 11 Mbps. So, a downlink rate of 0.0507 should be read as an uplink
downlink bandwidth of a fraction of 0.0507 of $11\times\frac{2}{3}$
Mbps. Similarly an uplink bandwidth of 0.0307 should be read as a
fraction 0.0307 of $11\times\frac{1}{3}$ Mbps. i.e.,11 kbps.

As seen from the tables, with 6 sectors, and $n_0=3$, the capacity
remains almost the same irrespective of the width of taboo region.
This happens because even if the taboo region of a sector covers half
of the adjacent sector, we can form maximal sets with 3 links. But,
with $n_0=4$, the capacity decreases with an increase in the width of
taboo region. With a taboo region of width $30^\circ$, in a 6 sector
system, we can have at most 3 links scheduled at a time. 
 
Depending upon the antenna pattern and the terrain, $n_0$ may go up to
4. With $n_0=4$, we can schedule slots for 2 calls per ST with a
probability of voice packet dropping as small as 0.29\%.
 
The minimum, maximum and sum of average data throughput over STs over
different deployments are tabulated in Table 8 
for the round robin scheduler, for different values of voice slot
requirement. The average behavior of the round robin scheduler is
almost the same as the greedy heuristics scheduler. But, in a given
deployment, the greedy heuristic scheduler is found to be more fair.
For example consider a deployment, where the adjacent sectors have 3
and 10 STs respectively. With a scheduler that round robins among the
sectors, all STs in the sector with 3 STs will get 1/3 of the downlink
bandwidth, whereas all those in a sector with 10 STs get only 1/10 of
the downlink bandwidth. But, if we were allowed to select the STs in
the activation set based on queue lengths, or on average rates, with
the condition that no two interfering transmissions are allowed
simultaneously, it is possible to vary the fraction of time each
sector is allowed to transmit, based on the number of STs in each
sector (which will be reflected in queue lengths or average rates),
and thereby provide better fairness.

\newpage
%----------------------------------------------------------------------------------------------------------------
\section{OPNET model and Simulation}
Development of an OPNET model for the WiFiRe protocol, including the fair scheduling algorithm, is ongoing.
Such a development will not only be useful to further understand the behaviour of the WiFiRe System under various conditions, 
but also may serve as a building block for the actual implementation of the protocol.

A description of the preliminary work completed so far is given in this section. This makes the following assumptions:
(i) The ST(s) and BS are initialized at the same time. No ranging is performed. 
(ii) BS after becoming ready, starts transmitting MAPs. Each ST receives MAPs and gets associated with the BS antenna from which it receives maximum power. 
(iii) {\em Dynamic Service Addition} messages are exchanged and the simulation starts; {\em Dynamic Service Change} messages are not supported at present.

\begin{figure}[htb]
\centering \
\psfig{figure=./figures/st_basic.eps,width=140 mm,height=100 mm}
\caption{OPNET Model: WiFiRe MAC State Diagram}
\label{fig:sys_st_basic}
\end{figure}

\subsection{MAC State Diagrams}
Figure~\ref{fig:sys_st_basic} shows the generic state diagram of the MAC. It shows states common to both BS and ST. 
Different actions are taken in each state based on whether the node is the BS or an ST.

In the {\em Init State} all variables are initialised. MAC and IP addresses are obtained. 
The {\em Invoke Corresponding Process State} invokes a {\tt bs\_control()} module, in case the node is the BS. 
This state initializes the directional antennas (six in current implementation) and then enters the {\em Ready State} to wait for events.
In case the node is an ST, a {\tt st\_control()} module is invoked. This orients the ST antenna towards the BS and 
then enters the {\em Ready State} to wait for events.

When the MAC (in the {\em Ready State}) receives a packet from the higher layer, it makes transition to {\em Enqueue State}. 
Here, a {\tt classify\_packet()} module maps each incoming higher layer packet to one of the outgoing connections, identified by a CID. 
A CID has a queue associated with it. A {\tt get\_queue()} module is invoked to determine the appropriate queue and the packet is then inserted into it.
A packet which does not match any condition specified in classifier is inserted in a default best-effort (BE) connection queue. 

When the MAC receives a data packet PDU from the PHY, it makes a transition to the {\em Process Data Packet State}.
Here the PDU is de-multiplexed into appropriate higher layer packets, based on the CID(s).
These packets are passed to the higher layer for further processing. 

When the MAC receives a control packet PDU from the PHY, it makes a transition to the {\em Process Control Packet State}.
In case of the BS, this corresponds to {\em Dynamic Service Addition Request} and {\em Bandwidth Request} messages.
In case of the ST, this corresponds to {\em Dynamic Service Addition Response} messages.
When the BS receives a {\em Bandwidth Request} message, the CID of the flow and the bandwidth requested are noted and 
the MAC returns to the {\em Ready State}.
When the BS receives a {\em Dynamic Service Addition} message, it determines the service flow type, assigns a CID and a queue. For UGS flows, 
an {\tt admission\_control()} module is invoked. This takes into account the UGS flow requirements and the number of free slots per frame, 
to determine whether the flow can be admitted or not. An appropriate {\em Dynamic Service Response} message is created.
This is given to a {\tt schedule\_pk()} module and the MAC returns to the {\em Ready State}.
When the ST receives a {\em Dynamic Service Response} message, it creates a queue for the CID and returns to the {\em Ready State}.
Note: One limitation of the simulation model implemented so far is that an ST needs to send all its {\em Dynamic Service Addition Request}
messages at the start of the simulation itself.

At a ST node, when a Beacon is received from the lower layer (PHY), it enters the {\em Process MAP State}.
A child {\tt st\_control} process is invoked and the packet is passed to it.
The process checks each element in the UL-MAP. The each element in the UL-MAP contains: 
(i) CID, (ii) Start Slot (Slot number at which transmission should start) and
(iii) Number of Slots (Number of slots alloted for transmission). 
If the CID in UL-MAP element belongs to that ST node, the number of slots allocated for transmission is checked and
an appropriate number of packets are extracted from the queue associated with that CID. A MAC PDU (protocol data unit) is
constructed, taking into account the PHY overhead and the PDU is given to a {\tt schedule\_pk()} module.
The control then returns from the child to the parent {\tt st\_control} process which is returns to the {\em Ready State}.
This {\tt schedule\_pk()} module independently transmits the PDU in the appropriate slot.

The BS enters the {\em Process MAP State} periodically, at the end of each frame (time interval). 
Here it invokes the scheduler, which takes into account the admitted UGS flows and pending bandwidth requests, 
to construct the DL-MAP and UL-MAP for the next frame.
It then constructs data PDU(s) for downlink transmission in the next frame, based on the DL-MAP. This is similar to the mechanism followed by the ST.

\section{Simulation Setup}
A preliminary validation of the WiFiRe OPNET model was carried out using the scenario shown in Figure~\ref{fig:simulation_setup}. 
The scenario consists of one BS, surrounded by 16 ST(s), which are placed randomly around the BS. 
Each ST has 4 flows registered at the BS: one UGS downlink flow, one UGS uplink flow, one BE downlink flow and one BE uplink flow. 
The following parameters can be specified while setting up the simulation: 
(i) Classifier Definition, (ii) Service Class Definition,
(iii) Packet inter-arrival time (exponential distribution) and (iii) Packet size (Uniform Distribution).

\begin{figure}[!h]
   \begin{minipage}{8cm}
\centering \
\psfig{figure=./plots/simulation_setup.eps,width=72 mm,height=72 mm}
\caption{Simulation scenario; unit 5 km.}
\label{fig:simulation_setup}
\end{minipage}
%\end{figure}
%\begin{figure}[htb]
   \begin{minipage}{8cm}
\centering \
\psfig{figure=./plots/load_throughput.eps,width=72 mm,height=72 mm}
\caption{Throughput (on Y-axis in bps) v/s Load (on X-axis in 10 Mbps)}
\label{fig:load_throughput}
\end{minipage}
%\end{figure}
%\begin{figure}[htb]
   \begin{minipage}{8cm}
\centering \
\psfig{figure=./plots/throughput_ugs_delay.eps,width=72 mm,height=72 mm}
\caption{Delay of UGS flows (on Y-axis in seconds) v/s Throughput (on X-axis in 10 Mbps)}
\label{fig:throughput_ugs_delay}
\end{minipage}
%\end{figure}
%\begin{figure}[htb]
   \begin{minipage}{8cm}
\centering \
\psfig{figure=./plots/throughput_be_delay.eps,width=72 mm,height=72 mm}
\caption{Delay of BE flows (on Y-axis in seconds) v/s Throughput (on X-axis in 10 Mbps)}
\label{fig:throughput_be_delay}
\end{minipage}
\end{figure}

Figure~\ref{fig:load_throughput} shows how throughput of system varies with increasing load, while Figure~\ref{fig:throughput_ugs_delay} and
Figure~\ref{fig:throughput_be_delay} show the delay v/s throughput for UGS and BE flows, respectively.
The behaviour observed in graphs is close to that expected by simple theoretical analysis, thereby validating the WiFiRe OPNET model developed so far.
Further development of the model as well as detailed experimentation is underway.

%\newpage
% -------------------------------------------------------------------------
\begin{thebibliography}{10}\setlength{\itemsep}{-1ex}
%\small
% DO NOT CHANGE THE ORDER of the bibitems.
% The first eighteen references are hardcoded into the WiFiRe Word Doc.
%
% -------------------------------------------------------------------------
\bibitem{jkr}
Ashok Jhunjhunwala, Anand Kannan and Bhaskar Ramamurthi. 
\newblock {Interim Broadband Wireless System for India}.
\newblock {CEWiT Technical Report, CEWiT-2005-02}, March 2005, available from http://www.cewit.org.in/

\bibitem{policy} 
\newblock {Broadband Policy 2004}. 
\newblock{Govt. Of India, Ministry of Communications and Information Technology, Department of Telecommunications}, 
available from http://www.dotindia.com/ntp/broadbandpolicy2004.htm

\bibitem{kr} 
J. Klutto Milleth and Bhaskar Ramamurthi. 
\newblock {Study of Imminent and Emerging Broadband Wireless Technologies}.
\newblock {CEWiT Technical Report, CEWiT-2005-01}, March 2005, available from http://www.cewit.org.in/

\bibitem{gsm} 
\newblock {Digital cellular telecommunications system (Phase 2+) (GSM);GSM Release 1999 Specifications}.
available from http://www.etsi.org/

\bibitem{gprs} 
\newblock {Digital cellular telecommunications system (Phase 2+) (GSM);General Packet Radio Service (GPRS) Release 1999 Specifications}.
available from http://www.etsi.org/

\bibitem{cdma} 
\newblock {cdma2000 Specifications}.
available from http://www.3gpp2.org/

\bibitem{iburst} 
\newblock {iBurst Specifications}.
available from http://www.arraycomm.com/docs/iBurst.pdf

\bibitem{flash} 
\newblock {Flash-OFDM Specifications}.
available from http://www.flarion.com/products/flash\_ofdm.asp

\bibitem{cordect} 
\newblock {corDECT, "Wireless access system"}.
\newblock {Technical report of Midas Communication Technologies Private Ltd}.
December 2000.

\bibitem{dot16} 
\newblock {IEEE Std 802.16-2004}.
\newblock {IEEE Standard for Local and metropolitan area networks "Part 16: Air Interface for Fixed Broadband Wireless Access Systems"}. 
(Revision of IEEE Std 802.16-2001), 2004.

\bibitem{dot11} 
\newblock {IEEE Std 802.11-1999}.
\newblock {IEEE Standard for Local area networks "Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications"}.
1999.

\bibitem{insideout}
Pravin Bhagwat, Bhaskar Raman and Dheeraj Sanghi.
\newblock {Turning 802.11 Inside-Out}.
\newblock {\em ACM SIGCOMM Computer Communication Review}, 34(1):33--38, Jan 2004.

\bibitem{perf11} 
Leena Chandran-Wadia, Shruti Mahajan and Sridhar Iyer. 
\newblock {Performance of 802.11 Wireless LANs}. 
\newblock {IEEE Conference on Computer Communications}, Mumbai, 2002.

\bibitem{sbr} 
http://www.smartbridges.com/products/ap2np.asp

\bibitem{brovis} 
http://www.brovis.com/files/product\_as1000.htm

\bibitem{cisco} 
http://www.cisco.com/en/US/products/hw/wireless/ps5279/

\bibitem{winncom} 
http://www.winncom.com/moreinfo/item/ETHERANT-3-20/index.html

\bibitem{dot1F} 
\newblock {IEEE Std 802.1F-1993}. 
\newblock {IEEE Standards for Local and Metropolitan Area Networks: Common Definitions and Procedures for IEEE 802 Management Information}, 1993.

% -------------------------------------------------------------------------
%
% DO NOT CHANGE THE ORDER of the above 18 bibitems.
% They are referenced in the WiFiRe Word Doc. - Numbers are HARD-CODED.
%
% -------------------------------------------------------------------------

\bibitem{dect} 
\newblock {Digital enhanced cordless telecommunications (DECT)}. 
\newblock {ETSI EN 300 175}, 1988.
available from http://www.etsi.org/

\bibitem{bran} 
\newblock {Broadband Radio Access Networks (BRAN); Requirements and architectures for broadband fixed radio access networks (HIPERACCESS)}.
\newblock {ETSI Technical Report TR 101 177 V1.1.1}, May 1998.

\bibitem{statmux}
Anurag Kumar, D.Manjunath and Joy Kuri.
\newblock {\em {Communication Networking, An Analytical Approach}}.
\newblock {Morgan Kaufman Networking Services, Elsevier}, {2004}.

\bibitem{stable_scheduling}
Atilla Eryilmaz, R.Srikant and R.Perkins.
\newblock {Stable Scheduling Policies for Wireless Fading Channels}.
\newblock {IEEE/ACM Transactions on Networking}, 2005.

\bibitem{graphbased}
Arash Behzad and Izhak Rubin.
\newblock {On the Performance of Graph Based Scheduling Algorithms for Packet Radio Networks}.
\newblock {GLOBECOM}, 2003.

\bibitem{DP}
Dimitri~P. Bertsekas.
\newblock {\em {Dynamic Programming and Optimal Control}}, volume~1.
\newblock Athena Scientific, 2001.

\bibitem{evdo}
Sem Borst, Ken Clarkson, John Graybeal, Harish Viswanathan, and Phil Whiting.
\newblock {User-Level QoS and Traffic Engineering for 3G Wireless 1xEV-DO systems}.
\newblock {Bell Labs Technical Journal}, 8(2):33--47, 2003.

\bibitem{rep}
Harish V. Shetiya.
\newblock {Efficient Routing and Scheduling for IEEE 802.16 Mesh network}.
\newblock Master's thesis, {Electrical Communication Enigineering, IISc}, 2005.

\bibitem{stability}
Leandros Tassuilas and Anthony Ephremides.
\newblock {Stability properties of constrained queuing systems and scheduling policies for maximum throughput in multihop radio networks}.
\newblock {IEEE Transactions on Automatic Control}, 1992.

\bibitem{mac}
Bhaskar Raman and Kameswari Chebrolu.
\newblock {Revisiting MAC Design for an 802.11-based Mesh Network}.
\newblock {Third Workshop on Hot Topics in Networks}, San Diego, Nov 2004.

\bibitem{brewer}
E. Brewer, M. Demmer, et. al. 
\newblock {The case for Technology in Developing Regions}.
\newblock {IEEE Computer}, June 2005, pp. 25-38.

\bibitem{lee}
M.J. Lee, J.L. Zheng, Y-B. Ko and D.M. Shreshta.
\newblock {Emerging standards for wireless mesh technologies}.
\newblock {IEEE Wireless Communications}, April 2006, pp. 56-63.

\end{thebibliography}
\end{document} 
% -------------------------------------------------------------------------
