Synopsis
MAC Enhancements for Wireless Networks to Support QoS

TABLE OF CONTENTS (ONLY FOR REVIEW, TO BE DELETED LATER)
1	Overview	1
2	Mobile Ad Hoc Networks	1
2.1	Overview	2
2.1.1	DCF Mode of IEEE 802.11 MAC	2
2.1.2	EDCF Mode of IEEE 802.11e MAC	2
2.2	Previous Work	3
2.3	Contribution in this Thesis	3
2.4	Performance Study	6
2.5	Results and Discussion	6
3	Wireless Local Area Networks	7
3.1	Overview of Existing Technology and Literature Survey	7
3.1.1	PCF Mode of IEEE 802.11 MAC	7
3.1.2	HCF Mode of IEEE 802.11e MAC	8
3.2	Contribution in this Thesis	9
3.2.1	MAC Scheduler Enhancements	9
3.2.2	Design of Scheduler	10
3.3	Performance Study	11
3.4	Results and Discussion	12
4	Conclusion	15
References	15

1	Overview
In this thesis, we propose medium access control (MAC) layer enhancements to improve the performance of wireless networks. In specific, we address the MAC issues in wireless ad hoc networks and wireless local area networks (WLAN) to support traffic with quality-of-service (QoS) requirements.
The wireless access channel is a shared medium, which is to be shared by all users in the system. Hence, it is necessary to have an efficient MAC. In wireless ad hoc networks, the MAC is usually distributed, whereas, in WLAN, the MAC could be distributed or centralized. We first consider wireless ad hoc networks with directional nodes and propose a MAC protocol that exploits the directionality of the nodes. We then consider WLANs with centralized MAC and propose an enhanced MAC to improve the delay performance of the system and the system throughput.
2	Mobile Ad Hoc Networks
Typically, ad hoc networks are classified by their topology-free, infrastructure-independent nature. All nodes in the network contribute to the network functionality, but, at the same time, there is no dependence on any single node for existence of the network. The basic MAC considered for ad hoc networks is the carrier sense multiple access with collision avoidance (CSMA/CA) with four way handshake namely request to send (RTS), clear to send (CTS), data, and acknowledgement (ACK). Binary exponential backoff (BEB) with contention window (CW) is deployed to minimize collision. 
QoS enhanced MAC has the requirement that the protocol data units (PDUs) that reach the MAC layer, from the higher layers, be associated with certain traffic categories (TC), which is typically eight. Each TC is mapped to one of four access categories (ACs) and the available resource is distributed to these ACs based on the preset priorities for the ACs. Prioritizing is achieved by assigning different values for various parameters like the backoff window size and the inter-frame spacing in the basic CSMA/CA based MAC.
2.1	Overview 
2.1.1	DCF Mode of IEEE 802.11 MAC
The distributed coordination function (DCF) is based on CSMA/CA. The standard defines the common duration for carrier sensing by the clear channel assessment (CCA) function or DCF inter frame space (DIFS) at every node and also the contention window ranges (CWmin, CWmax). The time gap between two packets in the handshake sequence or an atomic operation, defined as short inter frame space (SIFS), is less than DIFS. This prevents other nodes from capturing the channel when one transmission (in the same area) is already going on. 
2.1.2	EDCF Mode of IEEE 802.11e MAC
Though to support traffic streams with guaranteed service in ad hoc networks is not a possibility, the available bandwidth can be distributed based on the Traffic Category (TC). The IEEE 802.11e standard provides enhanced mechanism to handle TCs that are mapped to one of the 4 Access Categories (AC). Each AC has different priority of channel access. Multiple instances of the DCF (i.e., one for each AC) exist in every node. Once a node captures the channel, it can transmit for a duration termed as Transmission Opportunity (TXOP). Prioritization amongst ACs is achieved by having different: values for 
•	CCA duration or arbitration inter frame spacing (AIFS) per AC,
•	contention window ranges or CWmin and CWmax per AC and
•	Transmission Opportunity (TXOP) per AC.
2.2	Previous Work
The CSMA/CA based MAC scheme was proposed for mobile ad hoc network (MANET) [1] by the IEEE 802.11 standard [2]. The performance of ad hoc networks with distributed coordination function (DCF) mode specified in this standard was studied in [3]. Most MAC protocols proposed for ad hoc networks assumed omni directional antennas at all the nodes. In [8], Sanchez et al studied the performance of the IEEE 802.11 DCF in a network of nodes with directional antennas. However the MAC protocol and the scheduling mechanism did not exploit the directional nature of the nodes in the network. In [8], Tse et al showed that in the absence of delay constraints, mobility of the nodes enhances the throughput ad hoc networks. However, in ad hoc networks with QoS support, it is necessary to satisfy the delay requirements of users. Thansis et al consider MAC protocol specifically designed for directional ad hoc networks in [10] but this too does not deal with inherent QoS issues. Some of the handshake techniques in papers [11][12] are reused here but with a difference in scheduling.
2.3	Contribution in this Thesis
In this thesis, we propose a MAC for ad hoc networks that take into account, the directionality of the antennas at the nodes. We also study the effect of having stationary or immobile nodes placed at strategic locations. We consider a network in which the transmission ranges of the nodes are comparable to the geographical area of the network.
Nodes with directional antennas can be used in ad hoc networks to increase concurrent transmissions due to decreased interference. We also consider power back off at the antennas. Power back off is defined as the reduction in the transmission power in any specified direction. We consider the usage of both fixed beam-width antenna arrays as well as variable beam-width antenna arrays.
Mobility in ad hoc networks was shown to have resulted in an enhanced throughput in the absence of delay constraints [8]. However, in ad hoc networks with QoS support, it is necessary to satisfy the delay requirements of users. Therefore, it is of interest to selectively immobilize nodes in an ad hoc network and study the delay performance. The immobile nodes in are fixed taking the following into considerations:
•	The transmission ranges of all the immobile nodes are proper subsets of the geographical area of the network.
•	For networks with a given probability distribution of node positions in a given area, the immobile nodes must be placed following the same distribution.
•	As a corollary, when nodes are distributed uniformly in the network area, the immobile nodes must also be placed in a uniformly distributed manner.

We show that an improvement of 50% in the delay performance and 5% in the throughput performance can be achieved by combining the above techniques, i.e., selectively immobilizing nodes in an ad hoc network and exploiting the directionality of the antennas at the nodes. We also show that the proposed enhancements to the MAC result in improved network connectivity.
2.3.1.1	System Model
We consider a flat geographical network area of circular shape with radius 'R'. 
Let fd(x,y) be the probability density function (pdf) of the position of the nodes. The objective is to propose a MAC scheme and scheduling mechanism 
1.	that takes into account the directionality of the antennas at the nodes, and
2.	by immobilizing a selected subset of nodes.
We make the following assumptions to carry out the required study.
•	There are N nodes in the network
•	Each node can transmit only to nodes which are at a distance lesser than a specified distance limit, d0.
•	The contention mechanism is same as DCF for traffic without QoS requirements, and the EDCF for traffic with QoS requirements.
•	As in [reference], the nodes are assumed to know their individual positions.
•	The RTS frames contain the MSDU expiry time i.e., the time relative from the recent most Beacon frame, when the corresponding MSDU would be dropped from the MAC queue if it does not receive service. This is calculated considering the current time and the IEEE 802.11 parameter, MSDU lifetime.
2.3.1.2	MAC Enhancements with Directional Nodes
We propose the following enhancements in the MAC for a network with directional antennas at the nodes:
•	Before the basic atomic sequence, (RTS/CTS/Data/ACK), every source node with at least one MSDU in its queue contends to send an omni directional RTS (ORTS) at maximum power. The ORTS contains the position of the source node.
•	The destination node responds with a omni directional CTS (OCTS) at maximum power. The OCTS also contains the position of the destination node.
•	If the source does not receive an OCTS after ORTS, 
o	it may send another ORTS to the same node after a time period corresponding to an extended inter frame space (EIFS), or
o	the can send an ORTS corresponding to a different destination node as indicated by another MSDU in its queue.
•	On successful reception of the OCTS, the source node uses the information on the position of the destination and computes the direction of the destination node. Similarly, the destination node computes the direction of the source node from the ORTS.
•	Depending on the residual life time of the MSDU (i.e., the difference between the maximum MSDU lifetime and the delay already experienced by the MSDU), the source node chooses either to continue sending ORTS to other nodes or initiate transmission of directional DATA (DDATA) to the destination
•	The scheduler at the directional nodes can decide to switch to directional mode in any particular direction and initiate reception using Directional Request To Receive (DRTR) after which directional atomic sequence (DRTS/DCTS/DData/DACK) can go on. It shall select to orient to the direction from where maximum traffic is coming in terms of sum of requests.
The following figure illustrates the protocol through a state diagram. 

Fig 1: State diagram of the protocol.
When in state 3, the scheduler decides whether to send another ORTS or a DRTS based on the queue status and residual lifetime of the packets for which DCTS has been received. Without moving to a state greater than or equal to state 5, the node can not hold the channel for more than a MSDU transmission time.
2.3.1.3	QoS Enhanced MAC with Directional Nodes
In a network with QoS parameter specifications for the traffic, we consider 8 traffic categories (TCs), which, in turn, are mapped to 4 access categories (ACs). Weights are assigned to the ACs depending on the QoS requirements. The only additional change in the protocol is that, the scheduler selects to orient to the direction in which maximum weighted traffic is expected to be transmitted. The maximum weighted traffic is computed from the weights assigned to the ACs. 
2.4	Performance Study
We study the throughput and delay performance of the proposed MAC in ad hoc networks for the following scenarios:
•	Directional nodes with basic CSMA/CA based MAC
•	Directional nodes with enhanced scheduler based MAC
•	Directional nodes with EDCF for QoS traffic handling
•	Directional nodes with enhanced scheduler based MAC for QoS traffic handling
The performance of the network with omni directional antennas at the nodes are provided for comparison.
2.5	Results and Discussion
Simulations were carried out with the specified parameters for an ad hoc network with increasing number of nodes within a 1000m* 1000m area. We define goodput as the total number of bits of data transmitted successfully by the MAC layer. Maximum goodput of a particular topology corresponds to the traffic condition that results in maximum bits transfer in MAC. As shown in the graph, we observer that as we increase the density of the network, the delay performance improves. The curve corresponding to all mobile nodes indicates the base performance when all nodes are mobile and omni-directional (using basic IEEE 802.11 protocol). We observer up to 50% drop in delay when the network has all directional nodes with 10% of them immobilized. This directly gives better support for traffic with delay based QoS requirements.

3	Wireless Local Area Networks
Wireless local area networks (WLANs) are network of computers or other devices that can communicate with other nodes either using a central coordinator or distributed coordinator. The distributed coordination is the same as ad hoc mode detailed in the previous sections. In central coordination, there is a special node termed as access point (AP)
3.1	Overview of Existing Technology and Literature Survey
In WLANs the MAC deployed is typically based on the IEEE 802.11 standard [2]. Nodes can operate in a distributed manner using the DCF or in a centralized manner using the point coordination function (PCF). In the PCF mode, the point coordinator that resides in the AP does the central coordination.
3.1.1	PCF Mode of IEEE 802.11 MAC
In PCF mode, the access point AP is given preferential access to the medium. This is achieved by sensing the carrier to be free for duration of PCF inter-frame space (PIFS), which is shorter than DIFS but longer than SIFS.

Fig.  1. CFP, CP and super frame

The AP may hold the channel in the contention free mode for a contention free period (CFP) maximum duration [2] after which contention based transmission takes place. It can gain access again at the end of target beacon transmission time (TBTT) or contention free repetition interval. Thus a contention free period (CFP) and contention period (CP) alternate. In the CFP, the point coordinator (PC) in the AP forwards any multi-cast packet and polls the associated wireless stations for transmission and reception in a round-robin fashion.
3.1.2	HCF Mode of IEEE 802.11e MAC 
The QoS mechanisms in IEEE 802.11e [4] specified for the centralized mode of operation is called as the hybrid co-ordination function (HCF), which provides a mechanism  for QoS enhanced STAs (QSTAs) associated with a QoS enhanced AP (QAP). 
A QSTA obtains transmission opportunities (TXOPs) for any of these mechanisms. Within one TXOP duration, a wireless station (WSTA) may transmit as many MPDUs as might fit in.
3.1.2.1	HCF Controlled Channel Access
This mechanism involves a point coordinator called the hybrid coordinator (HC). It gains channel access with better preference using PIFS sense duration because SIFS < PIFS < DIFS or AIFS of any AC. Traffic streams (TSs) may be created on the wireless link. QSTA may negotiate regarding the traffic specifications (TSPECs) the QAP must try to provide for the TS with the HC.
The HC schedules traffic during CFP and CP to meet the requirements of TCs and all accepted TSs.
3.1.2.2	Admission Control
Resource allocation requests for new TS for which proper schedule can not be created due to lack of resources as computed from the link conditions and TXOP budget by the scheduler are rejected. 
3.1.2.3	Buffer Management
Random Early Detect (RED) [6] algorithm can be used for EDCF based traffic. This maintains small queue size and is suitable for low latency applications. 
3.1.2.4	Traffic Shaping and Policing
Since the input traffic is highly bursty in nature, it must be shaped and policed before scheduling. Traffic not belonging to any TS may be rate-limited by using a simple leaky bucket. However for TSs the aggregate throughput and delay characteristics of all the admitted TSs should be used as a for traffic shaping. This can be achieved by the twin-token bucket implementation. The decision of token-bucket parameters is based on scheduler explained in next section.
3.2	Contribution in this Thesis
In this section, we describe the implementation of a system conforming to the IEEE 802.11e draft [4]. The scheduler must be able to adapt to the channel variations and provide optimal performance. It must interact properly with the other parts of the system in establishing queues of shaped and policed stream of packets to be scheduled.
3.2.1	MAC Scheduler Enhancements
Fig.2. shows the interaction between different blocks in the system at the QAP. It shows the flow of packets as it enters the QAP. Only the downlink (QAP to WSTAs) situation has been depicted. A similar set of blocks exists for uplink (WSTAs to QAP) Packets entering the down link buffer are first of all classified based on whether or not TS has been created. The ones for which, TS has been created are sent to the Twin-token bucket based traffic shaper, the others are sent to a Random Early Drop (RED) [6] based queue. The shaped up traffic is fed to the TS buffers while the other is classified based on AC and is fed to the 4 AC buffers. The HCF, common to uplink, downlink and crosslink (WSTA to WSTA direct link in contention free mode) has two schedulers.

Fig.  2. System - Block Diagram

The TS scheduler generates polled TXOPs for the admitted TSs. Under EDCF, scheduling within every AC is First In First Out (FIFO, except for timeout based packet drops). At any given time instance, only one of the TSs or ACs (of/for any WSTA) that has obtained a TXOP either by contention or by poll, occupies the channel. The function of the individual blocks, related to the TS scheduler is explained, wherever required. The scheduler closely interacts with the admission controller and, traffic policer and shaper to optimize the performance.
 
3.2.2	Design of Scheduler 
The scheduler must allocate resources such that under controlled operating conditions, all WSTAs with admitted TS are offered TXOPs that satisfy the service schedule. 
The input for the scheduler to generate a service schedule is the TSPEC [4] (mentioning Mean Data Rate, Peak Data Rate, Delay Bound, etc.) of each TS to be admitted. 
The scheduler must try to generate TXOPs at definite intervals for finite duration computed from the requirements mentioned and generate corresponding polls. The remaining resource can be shared by the WSTAs through EDCF mechanism.
Scheduler was designed such that QAP generates schedules and admits Traffic Streams based on effective bandwidth (Effective Mean Data Rate or EMDR) estimation calculated from Packet Error information. For ease of design and analysis, it is assumed that transmission is always at the same data rate (54Mbps) and that only one QBSS is present. 

Set rate of token filling in Twin Token bucket is varied accordingly.

Fig.  3. Twin Token Bucket Implementation

Any 802.11 implementation offers more than one data rate. The mechanism for rate adaptation based on channel characteristics is not mentioned. Many use schemes based on Received Signal Strength measurement [15]. If the scheduler mentioned in the section above is used, it will only get a rough estimate of EMDR. To accommodate rate adaptation information, obtained from Station Management Entity, (SME), we modify the algorithm mentioned in previous section. 
3.3	Performance Study
Only the BSS (Basic Service Set) type of simulation topology has been taken into consideration. The IBSS (Independent Basic Service Set) or pure ad hoc mode is independent of the inherent QoS facilities and for all practical purposes it essentially operates as a plain IEEE 802.11 WLAN using DCF. Since we consider the enhancements provided by IEEE 802.11e, we have a QBSS (QoS enabled BSS). A single QAP connecting to many WSTAs has been taken up. The QAP is connected to the Ethernet interface too.
The table D.1 in IEEE 802.11e [4] gives us the details of the parameters taken for AC specific parameters.
Simulation of this with parameters for Best-Effort, Video Probe, Video and Voice as the 4 Access Categories was considered. The weights taken were 1:2:3:4. This is the performance without explicit traffic stream creation by the management layer.
We simulated a QBSS with one QAP and 8 WSTAs. For EDCF traffic generation belonging to the 4 different ACs, the parameters shown in Fig. 4. were used. 

Fig.  4. Parameters for generation of traffic of 4 ACs.

For ease of simulations, accumulated bursty traffic of 512Kbps of AC=3 and 512Kbps of AC=1 requiring a combined Mean Data Rate of 1Mbps has been used per TS.
To alter the QoS parameters, (CWmin[AC], CWmax[AC], TXOP[AC]), EDCF parameters chosen are the same as specified in the standards [4] as default.
Physical layer assumed is as mentioned in the IEEE 802.11a standard. Simulations were carried out for two different channel conditions viz., ideal and high bit error rate (BER=10-4) resulting in varying Packet Error Rate (PER).
3.4	Results and Discussion
In this section we discuss the results as found from the study.

The following graph illustrates the effective goodput of the higher AC increasing linearly with incoming traffic at the cost of lower ACs.

In this graph, we study the effective goodput of the two protocol schemes namely, HCF contention free access and EDCF deploying the scheduler discussed earlier. We observe that the performance is better when HCF contention free access is used over EDCF by about 5% at maximum goodput.

Fig. 7 illustrates the number of 1Mbps streams or roughly the throughput in terms of Mbps achievable when a channel with high bit error rate (10-4) is used.

Fig.  5. Traffic Streams supported for different peak data rate deviation on a non-ideal channel.

We observe that the adaptive scheme is able to provide service schedule of TXOPs for Traffic Streams and is able to support equivalent number of Traffic Streams (TSs) even in bad channel condition. From Fig. 6 and Fig. 7 it can be seen that throughput performance improves when rate adaptation information is used for EMDR estimation by the scheduler in HCF. The performance improvement is significant particularly when BER of the channel is high. 
In both the cases trials to admit more TSs than indicated in the graphs resulted in rejection by the Admission Control procedure.
Fig. 6  shows the average throughput performance of the adaptive scheduler in generating service schedules for both 
•	Traffic Streams in Contention Free Period (CFP) and 
•	the four Access Categories in Contention Period (CP)
We observe that the overall throughput is a bit better for contention free traffic (TSs) due to less contention overheads.

Fig.  6. Traffic Streams supported and EDCF Throughput for a network when scheduler in HCF handles TXOPs of both contention free and contention based traffic.

We observe from Fig. 6 that presence of EDCF does not degrade the performance of the scheduler for Traffic Streams as the HCF allocates only the bandwidth remaining after TS allocation for EDCF. Such a centralized scheduling scheme performs well when bandwidth is shared for EDCF operation due to the higher access priority of HC in QAP (using PIFS). Thus it can support applications with QoS guarantee requirements on the wireless link. Optimization of scheduler for polling in CFP when reserved Traffic Streams are not established has not been considered.
4	Conclusion
From the study, we conclude that usage of directional antennas with appropriate MAC protocol can help enhance performance of ad hoc networks and can help offer better QoS guarantees. We also conclude that when a scheduler with rate estimation coupled with incoming traffic stream shaping and admission control (adaptive scheduler) is used, performance can be improved in the centralized wireless networks. This when combined with IEEE 802.11e protocol is deployed can help handle both traffic with differentiated QoS requirements (multiple Access Categories) and integrated requirements (reserved Traffic Streams).
References
[1]	J.Macker and S. Corson, "Mobile Ad Hoc Networks (MANET)," IETF WG Charter, http://www.ietf.org/html.charters/manet-charter.html, 2001.
[2]	"IEEE 802.11, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification on 2.4GHz band," 1999.
[3]	A. Kamerman and G. Aben, "Throughput performance of wireless LANs operating at 2.4 and 5 GHz," in Proc of The 11th IEEE International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), vol. 1, pp. 190--195, September 2000.
[4]	IEEE Draft Supplement "IEEE 802.11e, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification: Medium Access Control (MAC) enhancements for Quality of Service (QoS)", D3.3, Oct 2002.
[5]	IEEE Standard 802.1Q-1998, IEEE Standards for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networks.
[6]	IETF RFC 2306, B. Braden, D. Clark, J. Crowcroft, B. Davie, S. Deering, D. Estrin, S. Floyd, V. Jacobson, G. Minshall, C. Partridge, L. Peterson, K. Ramakrishnan, S. Shenker, J. Wroclawski, L. Zhang, "Recommendations on Queue Management and Congestion Avoidance in the Internet", April 1998.
[7]	IETF RFC 2215, 2215 General Characterization Parameters for Integrated Service Network Elements. S.Shenker, J.Wroclawski. September 1997.
[8]	M. Sanchez, T. Giles and J. Zander, “CSMA/CA with Beam Forming Antennas in Multi-hop Packet Radio,” Proc. Swedish Workshop on Wireless Ad hoc Networks, March 2001.
[9]	Matthias Grossglauser and David Tse, "Mobility Increases the Capacity of ad hoc Wireless Networks,” Proc. IEEE Infocom, April 2001.
[10]	Thanasis.K, Gentian.J and Leandros.T, "A MAC protocol for full exploitation of directional antennas in ad-hoc wireless networks," International Conference on Mobile Computing and Networking, 2003, Pg - 98-107.
[11]	A.Nasipuri, S.Ye, J.You, R.E.Hiromoto, "A MAC protocol for mobile ad-hoc netowrks using directional antenna," Proc. IEEE Wireless Communications and Networking Conference, Chicago, IL, Sep. 23-28, 2000.
[12]	Y.B.Ko, V.Shankarkumar and N.H.Vidya, "Medium access protocols using directional antennas in ad hoc networks." Proc. IEEE Conference on Computer Communications, Vol 1(3), Pg 13-21, 2000.
[13]	Swetha Narayanaswamy, Vikas Kawadia, R. S. Sreenivas and P. R. Kumar, "Power Control in Ad-Hoc Networks: Theory, Architecture, Algorithm and Implementation of the COMPOWProtocol," European Wireless Conference, 2002.
[14]	 Rahul Jain, Anuj Puri, and Raja Sengupta, “Geographical routing using partial information for wireless ad hoc networks,” Technical Report M99/69, University of California, Berkeley, December 20, 1999. 34, 36, 42
[15]	Javier del Prado and Sunghyun Choi, "Link Adaptation Strategy for IEEE 802.11 WLAN via Received Signal Strength Measurement", Infocom TR 2002-013, 2002.