Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Cross-layer optimization in wireless local area networks Lin, Yuxia 2008

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2009_spring_lin_yuxia.pdf [ 7.16MB ]
Metadata
JSON: 24-1.0067193.json
JSON-LD: 24-1.0067193-ld.json
RDF/XML (Pretty): 24-1.0067193-rdf.xml
RDF/JSON: 24-1.0067193-rdf.json
Turtle: 24-1.0067193-turtle.txt
N-Triples: 24-1.0067193-rdf-ntriples.txt
Original Record: 24-1.0067193-source.json
Full Text
24-1.0067193-fulltext.txt
Citation
24-1.0067193.ris

Full Text

Cross-layer Optimization in Wireless Local Area Networks by Yuxia Lin B . S c , Tsinghua University, Beijing, China, 2000 M . S c , Tsinghua University, Beijing, C h i n a , 2003  A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF DOCTOR OF PHILOSOPHY  in  T H E F A C U L T Y OF G R A D U A T E STUDIES  (Electrical and Computer Engineering)  T H E UNIVERSITY OF BRITISH COLUMBIA (Vancouver)  December 2008  © Y u x i a L i n , 2008  Abstract This thesis studies several research problems i n the area of wireless local area networks ( W L A N s ) w i t h an objective of improving network efficiency, quality-of-service and user satisfactions. The I E E E 802.11 W o r k i n g Group has been under rapid development and expansion i n recent years following the successful deployment of the 802.11 network around the globe. The thesis work has been striving to study several key problems i n these developments and propose effective schemes to improve network performance. T h e original 802.11 standard presents a simple and robust design, but has relatively low data rate and lacks QoS support. T h e recent 802.11e standard and the 8 0 2 . l l n proposals aim to significantly improve the network performance i n terms of QoS and throughput. In this thesis, an analytical model of I E E E 802.11e W L A N s is first presented. W i t h the help of this throughput model, an admission control scheme for a multi-hop 802.11e W L A N is proposed. To fully utilize the high data rate provided by 802.11n, the performance improvement of the M A C protocol by frame aggregation is studied.  Two  frame aggregation techniques, namely A - M P D U ( M A C Protocol D a t a U n i t Aggregation) and A - M S D U ( M A C Service D a t a U n i t Aggregation) are considered. Furthermore, a comprehensive network setup is studied where the QoS requirements of the 802.11e M A C and the M I M O physical layer of 8 0 2 . l l n are both considered.  Cross-layer design schemes are proposed for  W L A N s under two different M A C protocols: the carrier sense multiple access with collision  Abstract  iii  avoidance ( C S M A / C A ) - b a s e d 802.11e M A C , and the slotted A l o h a M A C . Lastly, the thesis studies the problem of cooperative transmission i n a wireless ad-hoc network w i t h extensions to the 802.11 M A C protocols.  A complete system framework is proposed for wireless ad-  hoc networks utilizing two different cooperative relaying techniques at the physical layer: the repetition coding and the space-time coding. In the data link layer, two medium access control protocols are proposed to accommodate the corresponding physical layer cooperative diversity schemes. In the network layer, diversity-aware routing protocols are proposed to determine the routing p a t h and the relaying topology. Improvements in network performance for the proposed schemes are validated w i t h numerical and simulation tests.  Contents Abstract  t . •  "  Contents  iv  List of Tables  ix  List of Figures  x  List of Acronyms  xiii  Acknowledgements  xvi  C o - A u t h o r s h i p Statement  xvii  1  Introduction  1  LI  I E E E 802.11 W L A N s  2  1.2  Adaptive Control i n Wireless L A N s  4  1.3  Network U t i l i t y M a x i m i z a t i o n  6  1.4  Cooperative Communication i n Ad-hoc Wireless Networks  1.5  Summary of Results and Contributions  12  1.6  Thesis Organization  15  ;  9  Bibliography  2  16  Saturation Throughput of I E E E 802,11e E D C A Based on M e a n Value A n a l 27  ysis 2.1  2.2  2.3  2.4  Background and Related Work  29  2.1.1  I E E E 802.11e  29  2.1.2  Previous Work i n Performance Analysis of D C F and E D C A  31  The Analytical Model  33  2.2.1  Differentiation by Contention Window  34  2.2.2  Differentiation b y A I F S  37  M o d e l Validation by Simulation  40  2.3.1  Effect of Contention W i n d o w Size Differentiation  40  2.3.2  Effect of A I F S Differentiation  41  Summary  42  Bibliography  3  46  A n admission control algorithm for multihop 802.11e based W L A N s 3.1  3.2  . . . .  49  Related Work  52  3.1.1  I E E E 802.11e  52  3.1.2  Related Work i n Admission Control i n W L A N s  53  Admission Control System M o d e l  56  3.2.1  Network M o d e l and Assumptions  56  3.2.2  Contention G r a p h  57  3.2.3  Contention Analysis of 802.11e W L A N  58  3.3  3.4  4  3.2.4  Available Capacity Estimation  60  3.2.5  Admission Control A l g o r i t h m  62  3.2.6  Extension for Best-effort Traffic  62  3.2.7  Extension for Mobile User Terminals  64  Performance Evaluation  67  3.3.1  Linear Topology  67  3.3.2  R a n d o m Topology  68  3.3.3  Real-time and Best-effort Traffic Flows  69  3.3.4  Admission Control i n a Mobile Network  70  Summary  71  Bibliography  86  Frame Size Adaptation for I E E E 802.11n W L A N s  91  4.1  Related Work and Background on I E E E 802. U n  93  4.2  The Analytical Model  94  4.2.1  Uni-directional M A C  98  4.2.2  Bi-directional M A C  99  Simulation and M o d e l Validation  100  4.3.1  Uni-directional D a t a Transfer  100  4.3.2  Bi-directional D a t a Transfer  101  4.3  4.4  O p t i m a l Frame Size Adaptation for A - M S D U  102  4.5  Summary  104  Bibliography  112  5  Cross-layer Design of M I M O - e n a b l e d W L A N s with Network U t i l i t y M a x i mization  114  5.1  Related Work  118  5.1.1  Related work on M I M O systems  118  5.1.2  Related work on network utility maximization  119  5.2  5.3  5.4  System M o d e l for 802.11e E D C A M A C  121  5.2.1  Satiuration Throughput Analysis of the U - M A C Scheme  125  5.2.2  Saturation Throughput Analysis of the D - M A C Scheme  126  5.2.3  Network U t i l i t y Formulation  128  5.2.4  N U M Framework for Cross-layer Design  128  System M o d e l for Slotted A l o h a M A C  131  5.3.1  Network U t i l i t y Formulation  132  5.3.2  U t i l i t y - O p t i m a l P H Y / M A C Cross-layer Design  133  5.3.3  N U M - S : U t i l i t y - M a x i m i z a t i o n with Separated P H Y / M A C Layers  140  Performance Evaluation  142  5.4.1  Results for 802.11e E D C A  142  5.4.2  Results for Slotted A l o h a M A C  145  5.5  Summary  147  5.6  Proof of the convexity for problem (5.28)  148  5.6.1  Proof of the concavity of the utility function  148  5.6.2  Proof of convexity of the constraints  149  Bibliography  162  6  Cooperative M A C and R o u t i n g Protocols Design for Wireless A d - h o c N e t works  167  6.1  Related Work  169  6.2  System M o d e l for a Cooperative Ad-hoc Network  172  6.2.1  Physical Layer M o d e l  172  6.2.2  M A C Protocol Design  176  6.2.3  Cooperative R o u t i n g Protocol Design  178  6.2.4  Enhanced C R P  179  6.3  6.4  7  A  Performance Evaluation  181  6.3.1  Linear Topology Test  181  6.3.2  R a n d o m Topology Test  182  Summary  184  Bibliography  195  Conclusions and Future W o r k  199  7.1  Summary of Work Accomplished  199  7.2  Relationship A m o n g Chapters  202  7.3  Future W o r k  203  Bibliography  205  List of Publications  206  List of Tables 2.1  I E E E 802.11e Throughput Simulation Parameters  43  3.1  I E E E 802.11e Admission Control Simulation Parameters  73  4.1  I E E E 802.11n Simulation Parameters  5.1  List of Nomenclature - P a r t I  5.2  List of Nomenclature - P a r t II  151  5.3  CompEirison between Proposed Schemes  152  5.4  I E E E 802.11n Simulation Parameters  153  5.5  N U M Solution for the U - M A C Scheme  154  5.6  N U M Solution for the D - M A C Scheme  155  5.7  Solution for the N U M - D Scheme  156  6.1  Simulation Parameters  185  105  ".  150  List of Figures 2.1  Throughput performance for symmetrically increasing load  43  2.2  Throughput performance for asymmetrically increasing load  44  2.3  Differentiation effect of C W m i n  44  2.4  Differentiation effect of A I F S  45  2.5  Differentiation effect of A I F S and C W m i n  45  3.1  A multi-hop W L A N . E a d i Unk is identified by an integer  73  3.2  Contention graph and maximal chques  74  3.3  Network throughput with increasing traffic load  75  3.4  Simulation topologies: (a) Linear topology, (b) R a n d o m topology.  76  3.5  Performance of voice flows under linear topology.  77  3.6  Performance of video flows under linear topology.  78  3.7  Performance of voice flows under random topology.  79  3.8  Performance of video flows under random topology.  80  3.9  Performance of voice flows w i t h F T P flows under random topology.  81  3.10 Performajice of F T P flows under random topology.  82  3.11 C a l l dropping probabiUty w i t h different handoff parameter 7^  83  3.12 Average number of received calls per second w i t h different handoff parameter 7^.  83  3.13 Packet loss ratio w i t h increasing admission parameter 7  84  3.14 Average number of received calls per second w i t h increasing admission parameter 7 3.15 Packet loss ratio w i t h increasing pause time  84 85  4.1  Frame format for A - M S D U  106  4.2  Frame format for A - M P D U  106  4.3  Uni-directional R T S / C T S access scheme  107  4.4  Bi-directional R T S / C T S access scheme  107  4.5  Saturation throughput for A - M S D U  108  4.6  Access delay for A - M S D U  108  4.7  Saturation throughput for A - M P D U  109  4.8  Access delay for A - M P D U  109  4.9  Saturation throughput under bi-directional data transfer  110  4.10 A - M S D U throughput under different number of stations  110  4.11 Throughput under different frame aggregation schemes  Ill  5.1  Performance of U - M A C and D - M A C versus P  157  5.2  Network utility of U - M A C and D - M A C versus P  158  5.3  T h e tradeoff between throughput and reliability for slotted A l o h a  158  5.4  Slotted A l o h a - Network utility versus the number of wireless stations  159  5.5  Slotted A l o h a - Average throughput for best-effort trafSc w i t h different number of wireless stations  159  5.6  Slotted A l o h a - Average reliability for real-time traffic w i t h different number of wireless stations  160  5.7  Slotted A l o h a - Network utility versus the average S N R  160  5.8  Slotted A l o h a - Average throughput for best-effort traffic w i t h different S N R . . . 161  5.9  Slotted A l o h a - Average rehability for real-time traffic w i t h different S N R  161  6.1  Two different cooperative diversity scenarios  186  6.2  M R C - M A C timing sequence  187  6.3  S T C - M A C timing sequence  187  6.4  Linear topology.  188  6.5  Linear topology tests  189  6.6  T C P throughput with linear topology.  190  6.7  R a n d o m topology tests for C B R traffic with C R P (no gray zone reduction). . . .  191  6.8  R a n d o m topology tests for C B R traffic w i t h E - C R P  192  6.9  Relationship between the delivery ratio and channel B E R  193  6.10 T C P throughput under random topology w i t h C R P (no gray zone reduction). . . 193 6.11 T C P throughput under random topology w i t h E - C R P  194  List of Acronyms AC  Access Category  AIFS  A r b i t r a t i o n inter-frame spacing  AF  A m p l i f y and forward  AP  Access point  AWGN  Additive white Gaussian noise  BS  Base station  CBR  Constant bit rate  CCA  Clear channel assessment  CRP  Cooperative routing protocol  GTS  Clear to send  DGF  Distributed coordination function  DF  Decode and forward  EDGA  Enhanced distributed channel access  FCC  Federal communications commission  FCS  Frame check sequence  HCCA  H C F controlled channel access  HCF  H y b r i d coordination function  IEEE  Institute of electrical and electronics engineers  IP  Internet protocol  ISM  Industrial, scientific and medical band  MAC  M e d i u m access control  MIMO  Multiple-input multiple-output  MSDU  M A C Service D a t a U n i t  MPDU  M A C Protocol D a t a U n i t  NUM  Network utiUty maximization  PCF  Point coordination function  PLCP  Physical layer convergence procedure  RTS  Request to send  TCP  Transmission control protocol  TXOP  Transmission opportunity  UDP  User datagram protocol  WLAN  Wireless local area network  Acknowledgements I would like to express my deep gratitude to my research supervisor D r . Vincent Wong for all these years of guidance and help throughout my P h D research work. His great efforts i n teaching and research provided me w i t h valuable support and good ideas. W i t h o u t his guidance, this thesis would not be possible. I also want to thank all the members of my supervisory committee for their comments and time. D r . V i c t o r Leung, D r . V i k r a m Krishnamurthy, D r . Robert Schober, D r . Lutz Lampe and D r . Steve W i l t o n . T h a n k s to D r . Fei (Richard) Y u , D r . Enrique Stevens-Navarro, D r . A m i r - H a m e d MohsenianR a d , D r . J o o - H a n Song, D r . M i n Chen, D r . Zhanping (Walter) Y i n , D r . Qixiang (Kevin) Pang, H u i C h e n , Jie Zhang, Zhibing (Harry) Chen, C h i Sun, M a n H o n (Michael) Cheung, Y i n g W a i (Ray) L a m , Yangwen Liang, Simon Y i u , V i j a y Vivekanandan, V a h i d Shah-Mansouri, and N a s i m Arianpoo, w i t h whom I have the great opportunity to collaborate during the past years. Special thanks to my parents Zhaoyuan and Zhaoming, and my brother D a n x i a for all their support during these j^ars. T h i s work has been supported by the research grants from N a t u r a l Sciences and Engineering Research C o u n c i l ( N S E R C ) of Canada, the N S E R C Canada Graduate Scholarship and the University of B C Graduate Fellowship.  Co-Authorship Statement I am the first author and principal contributor of all manuscript chapters. A l l chapters are co-authored with D r . Vincent W . S . Wong, who supervises the present thesis research. Chapter 3 is also co-authored w i t h Michael Cheung, who helped to review the conference paper draft and provided positive feedback on the proposed admission control algorithm. Chapter 6 is also co-authored with D r . Joo-Han Song, who contributed to the routing protocol simulator development.  Chapter 1  Introduction I E E E 802.11 wireless local area networks ( W L A N s ) or so called W i - F i networks originate from the decision i n 1985 by the U n i t e d States Federal Communications Commission ( F C C ) to open several wireless spectrum bands for use without a government license, which is later known as the unlicensed Industrial, Scientific and Medical (ISM) spectrum. I n 1990, the Institute of Electrical and Electronics Engineers ( I E E E ) formed the 802.11 committee and began its work on standardizing the W L A N protocol for the I S M band. T h e first I E E E 802.11 W L A N standard didn't come out until 1997. B u t soon afterwards, the standard's popularity took off w i t h the rapid growth of high-speed Internet access around the globe. U n t i l now, it remains the easiest and the most widely used access technology for sharing a broadband data connection within a home or office building. Its main advantages are its low cost, robustness and ease of deployment. After its successful application i n W L A N s , the I E E E 802.11 protocol suite is being adapted i n many other wireless networking scenarios, such as sensor networks, ad-hoc networks, and mesh networks. T h i s thesis work focuses on studying several recent advances i n the 802.11-based wireless communication systems. T h i s work is based on recent developments i n the I E E E 802.11 Working Group. T h e I E E E 802.11e standard added QoS supports to the network. T h e 802.11n proposals aim to install multiple antennas i n wireless terminals and greatly boost the data throughput.  T h e 802.11s further extends the network topology to multiple hops and form a mesh network. T h e rest of this chapter is organized as follows. Section 1.1 to 1.4 provide some background information i n this research area. Section 1.5 summarizes the contributions of the thesis work. Section 1.6 gives an outline of the organization of this thesis.  1.1  I E E E 802.11 W L A N s  T h e 802.11a/b/g standards [1^] defined a physical layer ( P H Y ) supporting data rate up to 54 M b / s , and the corresponding medium access control ( M A C ) layer functionahties. W i t h the continued effort i n the 802.11 standard groups, the 802.11-based W L A N has been evolving from a simple and inexpensive wireless data access scheme to a more sophisticated last-mile wireless broadband access technology, which provides high throughput data access for a wide range of multimedia applications.  E n d users would be able to access high-speed Internet,  play online gaming, and use various voice over I P (VoIP) and video streaming applications. However, the original 802.11 M A C is designed w i t h a relatively simple C S M A / C A (carriersense-multiple-access/coUision-avoidance) protocol. T h e major advantage of this M A C protocol is its robustness and fully distributed control. B u t one inherent drawback is that its efficiency is low and can not provide hard quality-of-service (QoS) guarantees. W i t h the increasing demand from real-time multimedia applications on W L A N s , the 802.11e standard [5] was approved i n 2005 to provide quality-of-service (QoS) support by differentiating different classes of traffic. W i t h the success of building the 802.11 D C F i n millions of commercial products, there is great expectation that the Enhanced Distributed Channel Access ( E D C A ) function, which is D C F ' s QoS extension i n 802.11e, will dominate the next generation of QoS-  enabled W L A N equipments. Experimental testbeds [6] and numerous simulation tests [7-10] have been carried out which show that E D C A is effective i n QoS differentiation. A n a l y t i c a l models for 802.11 M A C protocol are important for in-depth understanding and improvement of the protocol.  Most of the existing analytical models for 802.11e E D C A are  extensions of the D C F models. Several models [11-13] extend the D C F Markov chain model proposed by Bianchi [14].  These multi-dimensional Markov chain analysis is highly compu-  tational intensive as they involve solving complex sets of non-linear equations. Some simpler models involve extending Call's p-persistent D C F model [15, 16], or extending Tay and Chua's mean value analysis [17]. We present a new E D C A throughput model i n this thesis, which is based on the mean value analysis approach. It has the benefits of low computational complexity and can be readily utilized for admission control algorithms. A p a r t from QoS improvement, the 802. U n working group [18] is i n the process of  finalizing  a new P H Y / M A C extension to increase the physical layer bit rate up to 600 M b p s . To achieve the ultimate goal of providing high-throughput multimedia services w i t h QoS support, different adaptive techniques need to be utilized in the system design i n order to improve the network performance.  For example, the auto-rate selection function at the M A C layer can adapt the  fink data rate according to the received signal strength such that more rehable transmission may be achieved. Adaptive frame aggregation at the M A C layer can significantly reduce the protocol overhead and improve the M A C efiiciency. Chapter 3 will look at the frame aggregation problem for an 802. U n W L A N . T h e significant data rate improvement at the physical layer of the 802. U n W L A N is from utilizing multiple antennas to form a multiple-input-multiple-output ( M I M O ) system. Chapter 4 will look at cross-layer optimization of the M I M O physical and M A C layer protocol.  Another recent development i n the 802.11 protocol suite is the addition of the 802.11s draft standard which extends the limited coverage area of W L A N w i t h multi-hop relaying. This thesis will study two problems arising from this multi-hop extension of W L A N s : the admission control problem i n a multi-hop W L A N , and the cooperative transmission schemes i n an ad-hoc wireless network.  1.2  Adaptive Control in Wireless L A N s  In I E E E 802.11 W L A N s , the M A C layer protocol is the main element which determines the efficiency of the wireless communications system. T h e C S M A / C A - b a s e d D C F function has been shown to be inefficient i n several communication scenarios [14, 19, 20]. T h i s is partly due to the simple design of the standard which fixes many operation parameters i n the system. Adaptive control of the communication system is one major way to improve the network performance. This thesis studies a few adaptive schemes i n a W L A N . Some related development i n this research area is introduced i n this section. T h e main functionality provided by the D C F function is the binary exponential backoff algorithm, which is a fully distributed mechanism for contention control. T h e key component in the backoff algorithm is the design of the contention window size.  A s evident from the  analysis in several studies [21, 22], the C W size has a major impact on the contention level in the network. T h e 802.11 standard uses a pre-defined m i n i m u m and m a x i m u m window size. Dynamically adjusting the backoff process can improve the M A C efficiency and maintain the network i n an appropriate level of contention [23-25]. For higher layers, cross-layer design has shown great performance gains [26-28]. For ex-  ample, at the application layer, adaptive video streaming over 802.11 D C F or P C F has shown good performance gain [29-32]. T h e video quality benefits from adapting the coding rate to the quality of the wireless channel. A t the transport layer, wireless-aware congestion control is especially important because the high packet error rate on a wireless link undermines a T C P transport protocol's basic assumption that packet losses are mainly due to link congestions. M a n y adaptive protocols for T C P enhancement [33, 34] are proposed to adapt to the 802.11 W L A N channel. T h e QoS enhanced E D C A utilizes more system parameters than D C F such as the A r b i tration Inter-Frame Space ( A I F S ) and Transmission Opportunity ( T X O P ) . A I F S is shown to have more significant impact on the traffic differentiation than C W [35, 36]. Large differences in different A G ' s A I F S values may tend to starve the lower priority traffic [17]. T h e T X O P is introduced i n E D C A so that a station may transmit multiple frames separated by SIFS once it has gained access to the wireless medium. T h i s improves system performance when wireless stations have many small packets for transmission, because each packet will not need to go through the time-consuming access contention.  T h i s operating mode is optional  in 802.11e and the standard does not specify the algorithm for obtaining the proper T X O P s . Several adaptive T X O P schemes have been proposed recently [37-39]. In this thesis, the crosslayer design techniques w i l l be utilized to jointly optimize the M A C layer parameters, such as the contention window size, w i t h the physical layer parameters. Other than the above cross-layer adaptive designs, proper admission control mechanisms are important for voice and video real-time flows [40-45]. In this thesis, an extension of the admission control to an 802.11e multi-hop W L A N is proposed based on constructing contention cliques i n the multi-hop topology.  1.3  Network Utility Maximization  Network utility maximization ( N U M ) is a recently developed mathematical framework to study network resource and functionality allocation of networking problems. N U M originates from the monotropic programming problem, which was studied since the 1960s [46]. K e l l y et. al. [47] applied monotropic programming to communication networks, which is later known as the N U M problem. T h e recognition of N U M as an important tool to study the performance of a packet data networking system came from the successful reverse-engineering of the T C P transport protocol's rate/congestion control algorithm. Different T C P variants have been shown that they are implicitly solving a N U M problem [48-52]. Since then, N U M has been applied widely in studying network protocol stacks. T h e N U M methodology is especially useful for the cross-layer design problems [26] i n wireless communication networks. Traditional wireline networks, such as today's Internet, has largely followed the layered design methodology [53]. According to the Open Systems Interconnection (OSI) reference model, communication networks are broken down into seven layers, which assume relative independence from each other. Each layer communicates with its upper or lower layers by exchanging m i n i m u m information required. In this way, the very complex communication network design problem is broken down into manageable modules. People work i n one particular layer and design that layer independently of each other. However, it has been found that this rigid layered design architecture can no longer meet many performance requirements in a wireless network. T h e characteristics of wireless communication channels are very different from those of the wirehne channels. T h e y are more dynamic, w i t h a higher error rate and varying transmission bandwidths [54]. These characteristics couple the higher layers performance  w i t h the physical layer [55]. W i t h the N U M framework, network protocols can be analyzed and systematically designed as distributed solutions to some global optimization problems [56]. T h e generic formulation of a N U M problem usually has the following form [57]:  subject to  /t(x) < 0, I <i hi{x)  <m,  = 0, 1 < i < p  (1.1)  where x G is the optimization variable, /o is the cost or objective function, / i , . . . , / m are the m inequality constraint functions, and hi, ...,hp are the p equaUty constraint functions. If the objective and inequality constraint functions are convex and the equality constraint functions are af&ne, the problem is a convex optimization  problem. A point x i n the domain of the problem  is feasible i f it satisfies a l l the constraint functions. T h e problem (1.1) is said to be feasible if at least one feasible point exists. Otherwise, the problem is infeasible. T h e optimal value of the objective function is denoted by / * , and is achieved at an optimal solution x*, i.e., / * = /o(x*). For example, the T C P congestion control problem can be formulated as [47]:  max  rr / ^ s  subject to  R x < c,  (1.2)  where x is the source rate vector, R and c are the routing matrix and link capacity vector, respectively.  T h e convexity of the N U M problem formulation is one major aspect to inspect when formulating a N U M problem [58]. A convex problem is much easier to investigate than a general nonlinear optimization problem. T h e local optimum of a convex problem is also globally optimal. For a convex problem, the widely used Lagrange duality theory can convert the original minimization problem (1.1), termed the primal problem, to a dual maximization problem. T h e optimal objective values of the primal and dual problems may not be equal. T h e difference between the two optimal solutions is called the duality gap. W h e n certain constraint qualifications are met, such as Slater's condition [59], the duality gap reduces to zero and the primal and dual problems are equivalent to each other. T h e attractiveness of the dual problem conversion is that a difficult primal problem may be easier to solve i n the dual formulation. If the problem is well defined, the dual problem may also present opprortunies of decomposition where the original N U M problem can be decomposed into multiple smaller scale optimization problems.  For a  non-convex N U M formulation, certain techniques can be applied to transform the problem into a convex problem, such as log transformation of variables [60]. There are two major approaches of utilizing the N U M  framework.  T h e first one is to  view the network as an optimization solver, and reverse-engineer the exact shape of the utility function from the given protocol.  T h i s technique has been successfully apphed i n studying  several existing network protocols, such as the transmission control protocol ( T C P ) [61-63] and the border gateway protocol ( B G P ) [64] protocols' T h e second one is to study a layered protocol stack as a decomposition of the N U M formulation. W h e n a network design problem is formulated into a N U M problem, the network performance and requirements are built into the utility functions. T h e n , the network protocol and system parameters can be designed according to the solution of the N U M formulation. This is one major advantage of the N U M framework  where the network protocol stacks can be holistically analyzed and systematically designed as distributed solutions to a global optimization problem. There are two main ways to obtain an optimal solution to a generalized N U M : vertical decomposition and horizontal decomposition. The vertical decomposition method decomposes the N U M problem across functional modules which can corresponds to different layers i n the protocol stack. T h i s naturally leads to cross-layer design and optimization. Some typical studies utilizing the vertical decomposition include: 1) joint congestion control, routing and scheduling [65-67], 2) joint congestion control and adaptive coding [68], 3) joint routing and power control [69-71], 4) joint routing, scheduling, and power control [72], etc. There are usually multiple ways to decompose a given problem, which correspond to different layering architecture and protocol stack designs. T h e horizontal decomposition method decomposes the N U M problem across geographically disparate network elements, such that a distributed network solution can be achieved.  Examples of utilizing the horizontal decomposition method include the T C P  congestion control, B G P and scheduling based M A C protocols [73]. T h e N U M framework w i l l be utihzed i n studying the M A C / P H Y cross-layer design of a M I M O - e n a b l e d wireless network i n Chapter 4 of this thesis.  1.4  Cooperative Communication in Ad-hoc Wireless Networks  Cooperative communication is a recently developed class of methods i n wireless communications which enables single-antenna wireless stations i n a multi-user environment to cooperate with each other i n data transmissions to exploit the spatial diversity gain. Spatial diversity has been widely utilized i n multi-antenna wireless transmissions, where one wireless station is equipped  w i t h more than one antenna. T h e multiple antennas form a multiple-input-multiple-output ( M I M O ) system, which can effectively combat the wireless fading by transmitting correlated information across the multiple antennas. Spatial diversity is generated by transmitting signals from different locations (via different antennas), thus providing independently faded versions of the signal to the receiver. However, to effectively exploit the spatial diversity gain, there is a m i n i m u m spacing requirement between two adjacent antenna elements, which is on the order of the wavelength. M a n y modern wireless devices do not have enough physical dimensions to meet the requirements to install multiple antennas. However, the cooperative communication scheme allows single-antenna wireless devices to share their antennas i n a manner that creates a virtual MIMO system [74]. A cooperative wireless communication network aims to increase the wireless users' qualityof-service (QoS) v i a cooperation.  There are many measures for the QoS of a wireless user.  O n the physical layer, bit error rate ( B E R ) , block error rate, and outage probability are the common performance metrics. O n the higher layers, throughput, packet dropping probability and delay performances are usually considered. T h e first work of cooperative communications started from an information theoretical perspective. Cover and G a m a l [75] studied the capacity of a relay channel where the simplest three-node network under an additive white Gaussian noise ( A W G N ) channel is considered. T h e source node transmit to the destination node with the help of a relay node. Recent work expanded the simple relaying i n a A W G N channel into a fading channel w i t h diversity gain. T h e role of the relay node has also been expanded. T h e relay node may also be a traffic source or destination node rather than solely relaying other nodes' data traffic. P r o m the physical layer's perspective, there are three main categories of cooperative schemes:  amplify-and-forwaxd, decode-and-forward, (AF)  and coded cooperation.  T h e amphfy-and-forward  scheme [76] allows the relays to amplify the received signal and retransmit the noisy  signal version. T h e destination node combines the signals from the sender a n d relays, and make a final decision on the bits transmitted. Although noise is also eimplified by the relay node, the destination node receives multiple copies of independently faded version of the signal and the diversity gain can still be achieved. In the decode-and-forward (DF) scheme [77, 78], the relay node attempts to decode the received information before retransmit it to the destination node. W h e n multiple relays are used, a certain relaying method can be used, such as repetition coding or space-time coding.  T h e coded cooperation [79] integrates channel coding.  Users  divide their coded message into différent segments, and send these segments v i a cooperation w i t h each other i n different time slots. In this way, each user's code word is transmitted v i a multiple fading paths. T h e physical layer techniques defined the foundations of the cooperative transmission schemes.  However, successful coordination of the diflFerent wireless users i n a  network to form a cooperative network depends on functionalities of higher layers. Cooperative medium access control ( M A C ) protocols coordinates the transmission of the source and relay nodes. Coordination is needed because the antennas are not located at a single terminal as i n a M I M O system. Some basic M A C functionalities include relay selection, distributed channel access control, and opportunistic scheduling of relaying nodes to exploit multi-user diversity, etc. W h e n the source to destination transmission involves multiple paths, the network layer's routing protocol shall find a suitable end-to-end path taking into consideration the opportunity of cooperation relaying along the path. T h i s thesis will propose a system framework for cooperative transmission i n an ad-hoc network based on the 802.11 protocol suites.  1.5  Summary of Results and Contributions  T h i s thesis studies several state-of-the-art research problems i n the area of wireless local area networks w i t h an objective of improving network efficiency, quaUty-of-service and user satisfactions. T h e main contributions of the thesis are divided into four chapters. Each chapter's contributions are summarized below.  • Chapter 2 presents an analytical model for I E E E 802.11e W L A N s . T h i s model studies the satiuration throughput of the E D C A function of the 802.11e protocol. It extends the mean value analysis model of D C F proposed by Tay and C h u a [80], thus avoids utilizing the Markovian chain model which involves compUcated non-linear system of equations. T h e work has been pubUshed i n a conference paper [81].  • Chapter 3 proposed an admission control scheme for a multi-hop 802.11e W L A N with the help of the throughput model from Chapter 2. T h e coverage area of W L A N s can be extended by allowing the neighboring mobile devices to relay data to the access points. T h i s concept is known as multi-hop W L A N s or wireless mesh networks.  Due to the  limited network capacity and the contention-based channel access mechanism, admission control is required to regulate the number of simultaneous flows to maintain QoS. The multi-hop extension of W L A N s present fiurther challenges for admission control design due to the location-dependent contention i n the network.  In the proposed admission  control algorithm, a contention graph is used to model the contention situation i n the multi-hop W L A N . It is followed by an estimation of the capacity for each m a x i m a l clique i n the contention graph. A new flow is admitted if the aggregated traffic load is less than the estimated network capacity. The proposed algorithm supports both stationary and  mobile nodes, as well as handoff and new connections. T h e work has been published i n a conference paper [82] and has been accepted for publication as a journal paper [83].  • Chapter 4 studies the recent 8 0 2 . l l n proposals which aim to significantly improve the physical layer transmission rate. To fully utiUze this high data rate, the current I E E E 802.11 medium access control ( M A C ) fieeds to be enhanced. T h e performance improvement of the M A C protocol by frame aggregation is studied i n this chapter. T w o frame aggregation techniques, namely A - M P D U ( M A C Protocol D a t a U n i t Aggregation) and A - M S D U ( M A C Service D a t a U n i t Aggregation) are considered. A n analytical model is proposed to study the performance imder uni-directional and bi-directional data transfer. T h e proposed model incorporates packet loss either from collisions or channel errors. Furthermore, an optimal frame size adaptation algorithm with A - M S D U under error-prone channels is proposed, which shows significant throughput improvements. T h e work has been published i n a conference paper [84].  • Chapter 5 studies a more complicated network setup where the QoS requirements of the 802.11e standard and the M I M O physical layer of the 802. U n are b o t h considered. M u l t i ple antennas can be used to improve the performance gain by either increasing the transmission reliabiUty through spatial diversity or increasing the transmission rate through spatial multiplexing. T h i s new characteristic at the wireless physical layer requires the corresponding adaptation at the medium access control ( M A C ) layer to reach the best performance gain. In this chapter, cross-layer design schemes for W L A N s rnider two difi'erent M A C protocols: the carrier sense multiple access w i t h collision avoidance ( C S M A / C A ) based 802.11e M A C , and the slotted A l o h a M A C are studied. For the 802.11e M A C , two  different contention window size adaptation schemes, namely U-MAC  and D-MAC,  are  proposed, which faciUtate the M A C protocol to adapt its contention window size jointly w i t h the physical layer's M I M O operating parameters. For the slotted A l o h a M A C , a cross-layer optimization framework NUM-0  is proposed for jointly optimizing the M I M O  configuration at the physical layer and the persistent probabifities for different classes of multimedia traffic at the M A C layer. A distributed algorithm NUM-D decomposition and a simpUfied version NUM-S  are also proposed.  based on dual  T h e work has been  published i n two conference papers [85, 86], and is under review for pubUcation as a journal paper [87].  • Chapter 6 studies the problem of cooperation i n a wireless ad-hoc network based on 802.11 M A C protocols. Wireless ad-hoc networks can experience significant performance degradation under fading channels. Spatial diversity has been shown to be an effective way of combating wireless fading w i t h the M E M O technique by transmitting correlated information through multiple antennas. T h e virtual M I M O technique, which allows multiple wireless stations with single antenna to form a virtual transmission array, is shown to be a viable solution from several recent studies. In this chapter, a complete system framework is proposed for wireless ad-hoc networks utilizing two different cooperative relaying techniques at the physical layer: the repetition coding and the space-time coding. In the data fink layer, two medium access control protocols are proposed to accommodate the corresponding physical layer cooperative diversity schemes. In the network layer, diversity-aware routing protocols are proposed to determine the routing path and the relaying topology. T h i s work has been pubUshed as a conference paper [88], and has been  submitted as an invited paper for journal publication [89].  1.6  Thesis Organization  T h e remainder of the thesis is organized as follows. Chapter 2 introduces the satmration throughput analytical model for 802.11e. T h e novel admission control scheme for an 802.11e multi-hop W L A N is proposed i n Chapter 3 w i t h cross-layer information sharing between QoS apphcations and admission control at M A C layer. Chapter 4 presents frame aggregation design at the M A C layer of an 8 0 2 . l l n W L A N where the physical layer error probabihties are jointly considered w i t h M A C frame aggregation. Chapter 5 studies the problem of jointly optimizing the physical and M A C parameters by utilizing new featmres provided w i t h the M I M O wireless channel. In Chapter 6, the recently developed cooperative communication schemes are studied and a complete system design for cooperative M A C and routing protocols are proposed. Chapter 7 summarizes the findings of the thesis work and discusses possible future research directions.  Bibliography [1] I E E E 802.11 W G , " I E E E Std 802.11: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications," 1999.  [2]  , " I E E E S t d 802.11a: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications: high-speed physical layer i n the 5 G H z band," 1999.  [3]  , " I E E E S t d 802.11b: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications: Higher-speed physical layer extension i n the 2.4 G H z band," 1999.  [4]  , " I E E E S t d 802.11g: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications: Further higher data rate extension i n the 2.4 G H z band," 2003.  [5] I E E E 802.11e W G , "Wireless L A N M A C and P H Y specifications amendment 8: M A C quality of service enhancements," Sept. 2005.  [6] A . Banchs, A . Azcorra, C. Garcia, and R. Cuevas, "Applications and challenges of the 802.11e E D C A mechanism: A n experimental study," IEEE  Network, vol. 19, no. 4, pp.  52-58, J u l y / A u g . 2005.  [7] A . Lindgren, A . Almquist, and O. Schelen, "Quality of service schemes for I E E E 802.11 wireless L A N s : an evaluation," ACM Mobile Networks and Applications,  vol. 8, no. 3, pp.  223-235, June 2003.  [8] S. C h o i , J . D . Prado, S. Shankar, and S. Mangold, " I E E E 802.11e contention-based channel access ( E D C F ) performance evaluation," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [9] D . He and C. Q. Shen, "Simulation study of I E E E 802.11e E D C F , " i n Proc. of IEEE  VTC,  Jeju, Korea, A p r . 2003.  [10] Q. N i , "Performance analysis and enhancements for I E E E 802.11e wireless networks," IEEE Network, vol. 19, no. 4, pp. 21-27, J u l y / A u g . 2005.  [11] Y . X i a o , "Performance analysis of I E E E 802.11e E D C F under saturation condition," i n Proc. of IEEE ICC, Paris, France, June 2004.  [12] Z. K o n g , D . H . K . Tsang, and B . Bensaou, "Performance analysis of I E E E contention-based channel access," IEEE  J. Select. Areas Commun.,  802.11e  vol. 22, no. 10, pp.  2095-2106, Dec. 2004.  [13] J . W . Robinson and T . S. Randhawa, "Saturation throughput analysis of I E E E 802.11e enhanced distributed coordination function," IEEE  J. Select. Areas Commun.,  vol. 22,  no. 5, pp. 917-928, June 2004.  [14] G . Bianchi, "Performance analysis of the I E E E 802.11 distributed coordination function," IEEE  J. Select. Areas Commun., vol. 18, no. 3, pp. 535-547, M a r . 2000.  [15] Y . Ge and J . H o u , " A n analytical model for service differentiation i n I E E E 802.11," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [16] J . H u i and M . Devetsikiotis, "Performance analysis of I E E E 802.11e E D C A by a unified model," i n Proc. of IEEE  Globecom, Dallas, Texas, Nov. 2004.  [17] Y . L i n and V . W . Wong, "Saturation throughput of I E E E 802.11e E D C A based on mean value analysis," i n Proc. of IEEE  WCNC, Las Vegas, N V , A p r . 2006.  [18] " I E E E  802.11n  Working  Group,"  http://grouper.ieee.org/groups/802/ll/Reports  /tgn_update.htm.  [19] A . K a m e r m a n and G . A b e n , "Throughput performance of wireless L A N s operating at 2.4 and 5 G H z , " i n Proc. of IEEE PIMRC, London, U K , Sept. 2000.  [20] M . H o , J . W a n g , K . Shelby, and H . Haisch, " I E E E 802.11g O F D M W L A N throughput performance," i n Proc. of IEEE  VTC-Fall,  Orlando, Florida, Oct. 2003.  [21] C . C h o u , K . G . Shin, and S. Shankar, "Contention-based airtime usage control i n multirate I E E E 802.11 wireless L A N s , " IEEE/ACM  Trans. Networking, vol. 14, no. 6, pp. 1179-1192,  Dec. 2006.  [22] B . L i , R . B a t t i t i , and Y . Fang, "Achie-ving optimal performance by using the I E E E 802.11 M A C protocol with service differentiation enhancements," IEEE  Trans. Veh. Technol.,  vol. 56, no. 3, pp. 1374-1387, M a y 2007.  [23] F . C a l l , M . C o n t i , and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput limit," IEEE/ACM  Trans. Networking, vol. 8, no. 6, pp. 785-799,  Dec. 2000.  [24] G . Bianchi and I. Tinnirello, " K a l m a n filter estimation of the number of competing terminals i n an I E E E 802.11 network," i n Proc. of IEEE INFOCOM,  San Francisco, C A , A p r .  2003.  [25] L . B o n o n i , M . C o n t i , and E . Gregori, "Runtime optimization of I E E E 802.11 wireless L A N s performance," IEEE  Trans. Parallel Distrib. Syst, vol. 15, no. 1, pp. 66-80, J a n . 2004.  [26] X . L i n , N . Shroff, and R . Srikant, " A tutorial on cross-layer optimization i n wireless networks," IEEE  J. Select. Areas Commun., vol. 24, no. 8, p p . 1452-1463, A u g . 2006.  [27] M . van Der Schaar and S. S. N , "Cross-layer wireless multimedia transmission: challenges, principles, and new paradigms," IEEE  Wireless Commun. Mag., vol. 12, no. 4, pp. 50-58,  A u g . 2005.  [28] V . Srivastava and M . M o t a n i , "Cross-layer design: a siurvey and the road ahead," Commun.  IEEE  Mag., vol. 43, no. 12, pp. 112-119, Dec. 2005.  [29] L . Haratcherev, J . Taal, K . Langendoen, R . Lagendijk, and H . Sips, "Optimized video streaming over 802.11 by cross-layer signaling," IEEE  Commun.  Mag., vol. 44, no. 1, pp.  115-121, J a n . 2006.  [30] Y . Andreopoulos, N . Mastronarde, and M . V . D . Schaar, "Cross-layer optimized video streaming over wireless multihop mesh networks," IEEE J. Select. Areas Commun., vol. 24, no. 11, pp. 2104-2115, Nov. 2006.  [31] M . I. Kazantzidis, " M A C intelligence for adaptive multimedia in 802.11 networks,"  IEEE  J. Select. Areas Commun., vol. 23, no. 2, pp. 357-368, Feb. 2005.  [32] M . van der Schaar, S. Krishnamachari, S. C h o i , and X . X u , "Adaptive cross-layer protection strategies for robust scalable video transmission over 802.11 W L A N s , " IEEE Areas Commun.,  J. Select.  vol. 21, no. 10, pp. 1752-1763, Dec. 2003.  [33] R . de Oliveira and T . B r a u n , " A smart T C P acknowledgment approach for multihop wireless networks," IEEE  Trans. Mobile Comput, vol. 6, no. 2, pp. 192-205, Feb. 2007.  [34] J . Lee, S. K w o n , and D . C h o , "Adaptive beacon listening protocol for a T C P connection i n slow-start phase i n W L A N , " IEEE Commun.  Lett, vol. 9, no. 9, pp. 853-855, Sept. 2005.  [35] Z. X u and L . Meng, " A novel fair scheduling scheme based on dynamic A I F S i n 802.11 wireless L A N s , " i n Proc. of Intl. Conf. on Communications,  Circuits and Systems, Guilin,  C h i n a , June 2006.  [36] C. Wang, P. L i n , and T . L i n , " A cross-layer adaptation scheme for improving I E E E 802.11e QoS by learning," IEEE Trans. Neural Networks, vol. 17, no. 6, pp. 1661-1665, Nov. 2006.  [37] J . M a j k o w s k i and F . C. Palacio, "Dynamic T X O P configuration for QoS enhancement i n I E E E 802.11e wireless L A N , " i n Proc. of IEEE SoftCOM,  [38]  Montreal, Canada, Sept. 2006.  , "Enhanced T X O P scheme for efficiency improvement of W L A N I E E E 802.11e," i n Proc. of IEEE  VTC-Fall,  Montreal, Canada, Sept. 2006.  [39] E . K i m and Y . Suh, " A T X O P : an adaptive T X O P based on the data rate to guarantee fairness for I E E E 802.11e wireless L A N s , " i n Proc. of IEEE  VTC-Fall,  Los Angeles, C A ,  Sept. 2004.  [40] D . G u and J . Zhang, " A new measurement-based  admission control method for I E E E  802.11 wireless local area networks," i n Proc. of IEEE PIMRC,  Beijing, C h i n a , Sept. 2003.  [41] D . Pong and T . Moors, " C a l l admission control for I E E E 802.11 contention access mecha^ nism," i n Proc. of IEEE Globecom, San Francisco, C A , Dec. 2003.  [42] Y . K u o , C . L u , E . H . W u , and G . Chen, " A n admission control strategy for differentiated service i n I E E E 802.11," i n Proc. of IEEE Globecom, San Francisco, C A , Dec. 2003.  [43] Z. K o n g , D . H . Tsang, and B . Bensaou, "Measurement-assisted model-based call admission control for I E E E 802.11e W L A N contention-based channel access," i n Proc. of IEEE Workshop on Local and Metropolitan  Area Networks, San Francisco, C A , A p r . 2004.  [44] Y . Xiao and H . L i , " L o c a l data control and admission control for QoS support i n wireless ad hoc networks," IEEE Trans. Veh. Technol, vol. 53, no. 5, pp. 1558-1572, Sept. 2004.  [45] Y . X i a o , H . L i , and S. C h o i , "Protection and guarantee for voice and video traffic i n I E E E 8 0 2 . l i e wireless L A N s , " i n Proc. of IEEE INFOCOM,  [46] R. T . Rockafellar, Network Flows and Monotropic  Hong K o n g , C h i n a , M a r . 2004.  Programming.  Athena Scientific, 1998.  [47] F . P. Kelly, A . K . Maulloo, and D . K . H . Tan, "Rate control for communication networks: Shadow prices, proportional fairness and stability," Journal of the Operational  Research  Society, vol. 49, no. 3, pp. 237-252, M a r . 1998.  [48] R. J . L a and V . A n a n t h a r a m , "Utility-based rate control i n the internet for elastic traffic," IEEE/ACM  Trans. Networking,  vol. 10, no. 2, pp. 272-286, A p r . 2002.  [49] S. H . Low, " A duality model of T C P and queue management algorithms," Trans. Networking,  IEEE/ACM  vol. 11, no. 4, pp. 525-536, A u g . 2003.  [50] S. H . L o w and D . E . Lapsley, "Optimization flow control, I: basic algorithm and convergence," IEEE/ACM  Trans. Networking,  vol. 7, no. 6, pp. 861-874, Dec. 1999.  [51] L . Massoulie and J . Roberts, " B a n d w i d t h sharing: objectives and algorithms," Trans. Networking,  vol. 10, no. 3, pp. 320-328, June 2002.  IEEE/ACM  [52] J . M o and J . Walrand, "Fair end-to-end window-based congestion control," Trans. Networking,  IEEE/ACM  vol. 8, no. 5, pp. 556-567, Oct. 2000.  [53] J . F . Kurose and K . W . Ross, Computer Networking: the Internet, 4th ed.  A Top-Down  Approach  Featuring  1st ed.  Prentice  Addison Wesley, 2007.  [54] T . S. Rappaport, Wireless Communications:  Principles  and Practice,  H a l l , 1996.  [55] S. Shakkottai, T . Rappaport, and P. Karlsson, "Cross-layer design.for wireless networks," IEEE  Commun.  Mag., vol. 41, no. 10, pp. 74-80, Oct. 2003.  [56] M . Chiang, S. Low, A . Calderbank, and J . Doyle, "Layering as optimization decomposition: A mathematical theory of network architectures," Proc. IEEE, vol. 95, no. 1, pp. 255-312, Jan. 2007.  [57] D . P. Palomar and M . Chiang, " A tutorial on decomposition methods for network utility maximization," IEEE J. Select. Areas Commun., vol. 24, no. 8, pp. 1439-1451, A u g . 2006.  [58] D . P. Bertsekas, Nonlinear Programming, 2nd ed.  A t h e n a Scientific, 2004.  [59] S. B o y d and L . Vandenberghe, Convex Optimization.  Cambridge University Press, 2004.  [60] M . Chiang, "Balancing transport and physical layers i n wireless multihop networks: jointly optimal congestion control and power control," IEEE no. 1, pp. 104-116, J a n . 2005.  J. Select. Areas Commun., vol. 23,  [61] D . X . Wei, C . J i n , S. H . Low, and S. Hegde, " F A S T T C P : Motivation, architecture, algorithms, performance," IEEE/ACM  Trans. Networking,  vol. 14, no. 6, pp. 1246-1259,  Dec. 2006.  [62] S. K u n n i y u r and R . Srikant, "End-to-end congestion control schemes: utility functions, random losses and E C N marks," IEEE/ACM  Trans. Networking,  vol. 11, no. 5, pp. 689-  702, Oct. 2003.  [63] R . J . L a and V . Anantharam, "Utility-based rate control i n the internet for elastic traffic," IEEE/ACM  Trans. Networking, vol. 10, no. 2, pp. 272-286, A p r . 2002.  [64] T . G . Griffin, F . B . Shepherd, and G . Wilfong, "The stable paths problem and interdomain routing," IEEE/ACM  Trans. Networking, vol. 10, no. 2, pp. 232-243, A p r . 2002.  [65] L . Chen, S. H . L o w , M . Chiang, and J . C . Doyle, "Joint optimal congestion control, routing, and scheduhng i n wirelss ad. hoc networks," i n Proc. of IEEE  INFOCOM,  Barcelona,  Spain, A p r . 2006.  [66] A . E r y i l m a z and R . Srikant, "Joint congestion control, routing, and mac for stability and fairness in wireless networks," IEEE  J. Select. Areas Commun., vol. 24, no. 8, pp. 1514-  1524, A u g . 2006.  [67] X . L i n and N . B . Shroff, "The impact of imperfect scheduling on cross-layer congestion control i n wireless networks," IEEE/ACM A p r . 2006.  Trans. Networking, vol. 14, no. 2, pp. 302-315,  [68] J . Lee, M . C h i a n g , and A . R. Calderbank, "Price-based distributed algorithms for raterehability tradeoff i n network utility maximization," IEEE  J. Select. Areas  Commun.,  vol. 24, no. 5, pp. 962-976, M a y 2006.  [69] B . Johansson, P. Soldati, and M . Johansson, "Mathematical decomposition techniques for distributed cross-layer optimization of data networks," IEEE J. Select. Areas  Commun.,  vol. 24, no. 8, pp. 1535-1547, A u g . 2006.  [70] M . Neely, E . Modiano, and C. Rohrs, "Dynamic power allocation and routing for timevarying wireless networks," IEEE J. Select. Areas Commun.,  vol. 23, no. 1, pp. 89-103,  Jan. 2005.  [71] L . X i a o , M . Johansson, and S. P. B o y d , "Simultaneous routing and resource allocation v i a dual decomposition," IEEE Trans. Commun.,  vol. 52, no. 7, pp. 1136-1144, July 2004.  [72] R. C r u z and A . Santhanam, " O p t i m a l routing, link scheduling and power control i n multihop wireless networks," i n Proc. of IEEE INFOCOM,  San Francisco, C A , M a r . 2003.  [73] J . - W . Lee, M . Chiang, and A . R. Calderbank, "Utility-optimal medium access control: Reverse and forward engineering," i n Proc. of IEEE INFOCOM,  Barcelona, Spain, A p r .  2006.  [74] A . Nosratinia, T . Hunter, and A . Hedayat, "Cooperative communication i n wireless networks," IEEE Commun.  Mag., vol. 42, no. 10, pp. 74-80, Oct. 2004.  [75] T . Cover and A . G a m a l , "Capacity theorems for the relay channel," IEEE Trans. Theory, vol. 25, no. 5, pp. 572-584, Sept. 1979.  Inform.  [76] J . N . Laneman, D . N . C. Tse, and G . W . Wornell, "Cooperative diversity i n wireless networks: Efficient protocols and outage behavior," IEEE  Trans. Inform.  Theory, vol. 50,  no. 12, pp. 3062-3080, Dec. 2004.  [77] A . Sendonaxis, E . E r k i p , and B . Aazhang, "User cooperation diversity - Part I: System description," IEEE  [78]  Trans. Commun., vol. 51, no. 11, pp. 1927-1938, Nov. 2003.  , "User cooperation diversity - Part II: Implementation aspects and performance analysis," IEEE  Trans. Commun., vol. 51, no. 11, pp. 1939-1948, Nov. 2003.  [79] T . riunter and A . Nosratinia, "Diversity through coded cooperation," IEEE less Commun.,  Trans.  Wire-  vol. 5, no. 2, pp. 283-289, Feb. 2006.  [80] Y . Tay and K . Chua, " A capacity analysis for the I E E E 802.11 M A C protocol,"  Wireless  Networks, vol. 7, no. 2, pp. 159-171, M a r . 2001.  [81] Y . L i n and V . W . Wong, "Saturation throughput of I E E E 802.11e E D C A based on mean value analysis," i n Proc. of IEEE  WCNC, Las Vegas, Nevada, A p r . 2006.  [82] Y . L i n , V . W . Wong, and M . Cheung, " A n admission control algorithm for multi-hop 802.11e based W L A N s , " i n Proc. of QShine, Waterloo, Canada, A u g . 2006.  [83] Y . L i n and V . W . Wong, " A n admission control algorithm for multi-hop 802.lie-based W L A N s , " Elsevier  Computer  Communications  Journal, vol. 31, no. 14, pp. 3510-3520,  Sept. 2008.  [84]  , "Frame aggregation and optimal frame size adaptation for I E E E 8 0 2 . l l n W L A N s , " in Proc. of IEEE  Globecom, San Francisco, C A , Nov. 2006.  [85]  , "Adaptive tuning of M I M O - e n a b l e d 802.11e W L A N s w i t h network utihty maximization," i n Proc. of IEEE  [86]  WCNC, Las Vegas, Nevada, M a r . 2008.  , "Utility-optimal cross-layer design for W L A N w i t h M I M O channels," in Proc. of IEEE ICC, Beijing, C h i n a , M a y 2008.  [87]  , "Cross-layer design of M I M O - e n a b l e d W L A N s w i t h network utility maximization," IEEE  Trans. Veh. Technol, accepted for publication, 2008.  [88] Y . L i n , J . - H . Song, and V . W . Wong, "Cooperative protocols design for wireless ad-hoc networks w i t h multi-hop routing," in Proc. of International  ICST Conference on Heteroge-  neous Networking for Quality, Reliability, Security and Robustness (QShine), Hong K o n g , C h i n a , J u l y 2008.  [89]  , "Cooperative protocols design for wireless ad-hoc networks w i t h multi-hop routing," ACM/Springer  Mobile Networks and Applications  Journal, invited, 2008.  Chapter 2  Saturation Throughput of I E E E 802.11e E D C A Based on Mean Value Analysis ^ Due to the simpUcity i n deployment and low cost, the I E E E 802.11-based wireless L A N s [1] have become the de facto standard for providing high-speed wireless Internet access to end users. I E E E 802.11 M e d i u m Access Control ( M A C ) specifies two main functions for random access: the contention-based mechanism of Distributed Coordination Function ( D C F ) and the centralized mechanism of Point Coordination Function ( P C F ) . D C F is simple and robust, and thus has been used i n most commercial products. However, it provides no traffic differentiation, delay or throughput guarantees. Real-time flows may experience arbitrary delays when the network load is high due to the C S M A / C A mechanism. O n the other hand, the P C F mechanism can provide a level of service guarantee by a central scheduling scheme, but it introduces additional complexity and protocol overhead.  It also has some problems that may lead to poor QoS  ' A version of this chapter has been published. Y . L i n and V . W . S . Wong, "Saturation Throughput of I E E E 802.11e E D C A Based on Mean Value Analysis," in Proc. of IEEE Conference (WCNC),  Las Vegas, Nevada, April 2006.  Wireless Communications  and Networking  performance [2]. A s a result, P C F is not widely deployed i n the existing W L A N s . Driven by the demand of supporting multimedia services on W L A N s (such as voice, video and interactive games), the Task Group E i n the I E E E 802.11 conmiittee has defined an extension to the I E E E 802.11 standard which provides QoS featiures and multimedia support to the existing 802.11a/b/g standards while maintaining backward compatibility. The I E E E 802.11e standard [3] defines a new coordination function called the H y b r i d Coordination Function ( H C F ) which includes a contention-based Enhanced Distributed Channel Access ( E D C A ) mode and a centralized H C F Controlled Channel Access ( H C C A ) mode. Due to the rapid deployment of W L A N s based on I E E E 802.11 D C F , throughput analysis of the contention-based D C F media access function has been extensively studied by using analytical or simulation methods. One widely used analytical model is proposed by Bianchi [4], which models the binary exponential backoff scheme of D C F w i t h a two-dimensional Markov chain. W i t h the popularity of the D C F i n I E E E 802.11 networks, E D C A is expected to be the dominating access scheme for I E E E 802.11e networks. A s a result, performance evaluations of E D C A function have been conducted by using either simulation or analytical methods. Most of the proposed analytical models extend the Bianchi's Markov chain model to take into account the different A r b i t r a t i o n Inter-Frame Space (AIFS) and the different Contention Window ( C W ) sizes. However, these extensions are not trivial. T h e use of multi-dimensional Markov chains and other non-linear equations lead to higher computational complexity. It may not be possible to obtain real-time solutions for these equations. Thus, although some of these models provide good accuracy, the high computational complexity may prevent them from implementing i n real-time control functions such as on-line call admission control algorithms i n I E E E 802.11e  networks. In this chapter, we propose a simple and accurate analytical model to evaluate the saturation throughput for 802.11e E D C A access scheme. We extend the work by Tay and C h u a [5] and use the mean value analysis. T h e proposed analytical model is simpler, and yet it maintains good accuracy. O u r proposed analytical model is validated by simulations. Results show that our model is accurate under a wide range of conditions (i.e., different number of stations, different contention window sizes and different A I F S values). O u r model is applicable to the design of fast on-line algorithms such as system parameter tuning and call admission control i n 802.11e networks. This chapter is organized as follows. In Section 2.1, we provide an overview of the new QoS access schemes i n I E E E 802.11e, and describe the related work on saturation throughput analysis for 802.11 D C F and 802.11e E D C A . In Section 2.2, we describe our proposed analytical model. Section 2.3 presents the results of the model validation by simulation. Section 2.4 summarizes this work.  2.1 2.1.1  Background and Related Work I E E E 802.11e  I E E E 802.11e is a direct extension to the existing 802.11 networks that provides QoS features and multimedia support, and at the same time, maintains full backward compatibility. It defines a H y b r i d Coordination Function, which includes two access modes: a distributed E D C A mode and a centralized H C C A mode. E D C A provides a prioritized QoS service by enhancing the contention-based D C F function.  Higher layer packets are classified into one of the four Access Categories (ACs) at the M A C layer. E a c h A C has its own queue and channel access parameters, which include the Arbitration Inter-frame Space ( A I F S ) , m i n i m u m and maximum contention window sizes and Transmission Opportunity ( T X O P ) limits. T h e A C s gain different priority for channel access by differentiating these parameters. However, due to its probabilistic nature of channel access, E D C A cannot provide hard QoS guarantees such as strict delay bound. In order to provide parameterized QoS service, H C C A has been proposed as a centralized polling scheme to allocate guaranteed channel access to Traffic Streams based on their QoS requirements.  D u r i n g a beacon interval, a H y b r i d Coordinator which is collocated w i t h the  QoS Access Point can access the wireless medium w i t h its higher priority to initiate frame exchange sequences and to allocate T X O P s to itself and other stations, so as to provide limitedduration controlled access phase ( C A P ) for contention-free transfer of QoS data. The durations of T X O P s are calculated from the traffic specification ( T S P E C ) , such as the mean/peak data rate and delay requirement announced at the beginning of the traffic flow. H C C A can be initiated during the Contention-free Period as well as the Contention Period. It is more flexible than P C F . W i t h a good admission control and scheduhng scheme, H C C A is able to provide guaranteed QoS services to network flows. However, compared w i t h E D C A , H C C A still presents much challenge for its actual implementation due to its higher complexity and cost concerns. W i t h D C F based 802.11a/b/g products dominating the market, E D C A is expected to be widely adopted as the multimedia solution to the 802.11-based networks. E D C A i n this chapter.  A s a result, we focus on  2.1.2  P r e v i o u s W o r k i n P e r f o r m a n c e A n a l y s i s of D C F a n d  EDCA  W i t h the rapid deployment of the I E E E 802.11 W L A N s , there have been many studies of contention-based D C F medium access function. D C F uses the carrier sense multiple access/collision avoidance ( C S M A / C A ) scheme w i t h binary exponential backoff. Most of the research work focused on the saturation throughput analysis, which is the maximum load that the system can carry i n a saturation condition (i.e., the transmission queue of every station is assumed to be always nonempty).  T h i s is a fundamental performance figure as it indicates the limit of the  network throughput when the offered traffic load increases. In addition to many simulation studies [6-8], analytical models have been constructed for performance analysis. A m o n g these works, Bianchi's model [4] has attracted lots of attention. It models a single station's back-off process w i t h a two-dimensional Markov chain. Assuming that each transmission experiences identical and independent collision probability, it obtains the stationary probability for a station to transmit in a generic time slot. T h e saturation throughput is obtained by dividing the expected payload information transmitted i n a time slot by the expected length of a time slot. T h i s method provides a relatively accurate representation of D C F ' s binary exponential bîickoff process, and achieves good performance prediction. O n the other hand, some parallel works derive the saturation throughput without fully describing the detailed behavior of the binary exponential backoff.  C a l l et al. [9] model the  backoff process w i t h a p-persistent model. T h e backoff interval is sampled from a geometric distribution w i t h parameter p. They show that the p-persistent I E E E 802.11 model closely approximates the standard protocol performance as long as the average backoff interval is the same. T h e y also derive the optimal p value for maximizing the system capacity.  Tay and C h u a [5] fiurther simphfy the 802.11 M A C modeUing by using a mean value ap- ' proach. Instead of studying the details of the stochastic process using M a r k o v chain, their model tries to approximate the average value for a system variable wherever possible. T h i s technique provides closed-form expressions for the collision probability and the saturation throughput, thus facilitating the analysis of the dependence of system performance on various parameters. T h e model vahdation shows that even though this model omits many system details, it still achieves good accuracy warranting its usefulness. There has been work reported i n the literatmre for the performance of the E D C A function. Experimental testbeds [10] and numerous simulation tests [2, 11-13] have been carried out which show that E D C A is effective i n traffic differentiation. Several analytical models have also been proposed for 802.11e E D C A . T h e y extend the above D C F models to include the traffic differentiation features of E D C A . Most of the work extends the D C F Markov chain model proposed by Bianchi. X i a o [14] enlarges the original two-dimensional Markov chain to threedimensional, and analyzes the effects of the different contention window sizes on throughput, but the A I F S - b a s e d priority scheme is not included. K o n g et al. [15] use a three-dimensional Markov chain to fully describe the backoff behavior of each A C i n each station so that both A I F S and C W are considered. Robinson et al. [16] keep the two-dimensional Markov chain, but divide the contention periods into different zones to account for the different collision probabilities during different contention periods. H u i et al. [17] also divide backoff into several sub-periods and constructs a p-consistent C S M A / C A model. Ge and H o u [18] extend Call's p-persistent D C F model to include multiple priority classes, but the mathematical model does not incorporate the A I F S differentiation proposed i n I E E E 802.11e standard. One major obstacle for utilizing the analytical models based on multi-dimensional Markov  chain analysis is the high computation complexity of these models. Solving a set of non-linear equations by approximation may not be feasible i n real-time. To better facilitate system design, such as deriving optimal call admission control or adaptive schemes, we need a mathematical model which is accurate and simple to implement (i.e., solutions can be obtained i n real-time). T h e motivation of our work is to propose a simple and yet acciurate analytical model. We achieve this by extending Tay and Chua's mean value D C F model to E D C A . B y following the principle of average value approximation, we construct a model based on evaluating the average collision and transmission probability for each access category w i t h different contention window size and A I F S .  2.2  The Analytical Model  In our proposed model, we assume that there is a fixed number of stations in the network. Each station has saturated traffic w i t h one access category.  Though the following work can  be generalized to four A G s as defined i n the 802.11e standard, we focus our initial analysis on only two A C s . T h i s avoids excessive formulation and makes the model easier to understand. We assume that there are Ni stations w i t h access category ACi traffic, and N2 stations with access category AC2 traffic. ACi is assumed to be the higher priority traffic. We also assume an ideal channel condition which does not have transmission errors or capture effect.  TXOP  limit is assumed to be 0, which allows only one frame exchange each time. T h e system time is considered to be slotted, and only basic access scheme is considered. For stochastic process analysis, people usually need to adopt assumptions, such as Markov memory and exponential distribution, to make the problem tractable. Network queueing and  multi-access systems are especially complex to analyze; only very simplified and ideal protocols can be well analyzed [19]. I n our problem, we formulate several simplifying assumptions i n the model development to achieve a good trade-off between simpUcity and accuracy. T h e simulation validation later w i l l show that these approximations are good enough to give meaningful system predictions.  2.2.1  Differentiation by Contention  Window  We first study the case when aU ACs have the same A I F S value. T h e traffic priority differentiation is thus only realized through diflFerentiating the contention window size. We assume that a packet for ACi (i = 1,2) transmitted i n a time slot has a constant collision probabifity of Pi. Each unsuccessful transmission will be re-tried until an acknowledgment is received. T h e number of transmissions experienced by each packet is then a geometric distribution with the probability of success I - Pi. T h e backoff timer starts w i t h a value uniformly selected from 0 to Wi, where Wj is the m i n i m u m contention window size for AC^. T h e average backoff timer i n the first stage is thus  Wi/2.  Each time a collision occurs, the contention window size w i l l double until it reaches the maximum stage rrii. T h e average number of backoff time slots experienced by a packet i n ACi can be calculated as:  2 i-Pi-Pi{2pir^Wi l-2pi  2 '  i = 1,2  (2.1)  If we assume that ACi s packet has a constant probability of transmission i n each idle slot.  then the probabihty for ACi's packet to transmit i n an idle time slot can be approximated as:  i =  Ti = l/Wbi,  l,2  (2.2)  T h e probability that one transmitted packet by ACi will collide is the probability that any of the other {Ni — 1) AC\ stations or N2 AC2 stations also transmits:  Pi = l - ( l - r i ) ( ^ i - l ) ( l - T 2 ) ^ ^  T h e same is true for the collision probability of  AC2S  (2.3)  packet:  P2 = 1 - (1 - r i ) ^ n i - T2)(^'"'^  (2.4)  We can solve for pi and Wbi from the above system of equations (2.1)-(2.4). To derive the saturation throughput for each ACi, we observe the system i n a unit time period. T h e rate of transmission  rxi is defined as the number of transmission attempts by ACi  stations during this unit time period. The rate of successful transmission  rgi is defined as the  number of successful transmissions by ACi stations. Due to the geometrical distribution of the number of transmission attempts per packet, the average number of transmissions per packet is 1/(1 - Pi), which equals rxi/rgi'.  r ^ I-Pi  = ?^'  ^ = i'2  (2-5)  Tai  Each collision may involve multiple stations. To a first degree approximation, we assume that each collision involves only two stations. Thus, the rate of collision rd, which is the number of collisions observed i n the system i n a unit time period, is given by:  For ACi, we define Tj as tfie time needed to finisfi a transmission cycle, which is the renewal period between two successive transmissions. Tj includes the frame transmission time, an SIFS, the A C K transmission time, an A I F S and an average number of backoff time slots. We make an approximation to estimate the average number of backoff time slots experienced by each packet transmission. A t satiuration, all transmissions will be preceded w i t h a mandatory backoff selected from the minimum contention window Wi. If we omit the dependence between two and only look at ACi stations, when Ni stations uniformly choose a backoff counter from  ACs  0 to W j , the separation between any two stations has an average of  Wi/{Ni  w i t h the smallest backoff coimter may make the first transmission after  +  1). T h e station  Wi/{Ni  +  1) slots of  waiting. A s an approximation, we have:  Ti = Tframe  + TsiFS  + TACK  + TAIFS  +  Wi jy. ^ -^"^slot  (2-7)  T h e time taken by the successful and collision transmissions should sum up to one time unit: 2 Y.[rsi+r^)Ti  (2.8)  = l  1=1  It is reasonable to assume that the rate of transmission by each ACi is proportional to the number of stations i n each ACi and the transmission probability by each ACi:  iVm  NiT2  ^  '  Equations (2.5)-(2.9) give a system of linear equations about Txi and Vsi which can be solved  i n closed form:  r^i =  K  =  + {l  -P2/2)r2]-i  (2.10)  r.2 = [(1 -pj2)KT,  +  il - P 2 / 2 ) r 2 ] - i  (2.11)  r , i = i f ( l - p i ) [ ( l -pj2)KT,  +  il - P 2 / 2 ) r 2 ] - i  (2.12)  -P2/2)r2]-i  (2.13)  r.2 =  where  K[il -p,/2)KT,  ( l - P 2 ) [ ( l -p^/2)KT^  + {l  N\T\/N2T2.  T h e saturation throughput for ACi can be calculated as:  Si = rsirp,i,  (2.14)  i = l,2  where Tp^i is the time used to transmit the frame pay load information for an ACi packet.  2.2.2  Differentiation by A I F S  T h e model i n the previous section only considers the effects of the contention window size on the throughput differentiation. I E E E 802.11e standard also defines traffic differentiation by utilizing different A I F S . W h e n we further take into account the different A I F S values for each access category, it is more challenging to design an effective mean value-based mathematical model. Since we assume that ACi is the higher priority access category, it is reasonable to assume that  AI F Si  < AIFS2.  B y the I E E E 802.11e standard [3], A I F S is calculated as  AI F Si = SIFS  where  Tsiot  is the slot time and  AIFSNi  + AIFSNiTsiot,  i = l,2  is an integer w i t h a typical value from 1 to 7.  (2.15)  For simplicity, i n the subsequent equations, we assume that  AIFSN2  = AIFSNi  + M  (2.16)  where M is a non-negative integer. The problem w i t h introducing different A I F S values is that it may violate some of the assumptions we used before. During the  {AIFS2  - AI F Si) time period, there is less contention  for ACi traffic. T h e collision probabihty during this period may become lower. T h i s violates the basic assumption that a packet belonging to one AC experiences identical collision probabihty i n any time slot. Robinson et al. [16] solve the problem by dividing the transmission periods into two contention zones and calculating the different collision probabilities i n each zone. K o n g et al. [15] expand the M a r k o v chain to three-dimensional to give a detailed representation of the priority access scheme. In order to follow the average value methodology, we assume that the collision probabihty for each access category is still identical i n each slot time. This assumption is reasonable if M is small compared to CWmin- In this case, the M time slots during which ACi has a smaller collision probability has less significance when we calculate the average probability. W i t h this approximation, we can calculate the new average collision probability for each access category. Each time the wireless medium becomes idle, AC2 will wait M more time slots before counting down its backoff timer. To incorporate the effects of the difference i n AIFS  into the  framework i n the previous subsection, we consider these M extra time slots as some equivalent extra backoff time slots experienced by  W i t h this consideration, we re-examine equation  2.1 to find the new average backoff time slots experienced by each access category's packet. The higher priority (ACi)  packet's average backoff slots (Wbi) remains the same as expressed  i n equation 2.1. T h e effect of longer AIFS2  for AC2 is converted into A C 2 ' s equivalently longer  bac;koff time slots W^QTo calculate the total number of time slots which an AC2 packet w i l l experience due to its larger A I F S , we first estimate how many times an AC2 packet's backoff timer w i l l be interrupted before counting down to zero. A n extra M slots' backoff time occurs every time the backoff timer is frozen due to sensing the busy medium. T h e probability that A C 2 ' s backoff will be interrupted due to busy medium can be approximated w i t h A C 2 ' s conditional collision probability p2. W i t h an average backoff timer of W2/2 i n the first stage, i t experiences an average of P2l^2/2 interruptions. For each of these backoff timer interruptions, it incurs an extra backoff time slot of MP2W2/2 Iteratively, these extra MP2W2/2  compared to AC\.  backoff slots may introduce another P2{Mp2W2/2)  terruptions, which lead to another extra Mp2{Mp2W2/2)  timer i n -  = M ^ P 2 ^ 2 / 2 time slots. A s a result,  the effect of an extra M A I F S time slots for AC2 is approximately equivalent to increasing the average first stage backoff slots of AC2 from W2/2 to:  T h e adjusted average backoff time slots for AC2 becomes _ i-P2-P2{2P2r^w2 ^"2-  1-2P2  (  1  \  2\l-Mp2)  ^^-'^^  Note that the above equation is deduced from our assumption that M (the difference between AI  F Si and AIFS2)  is relatively small compared to CWmin-  Too large an M may well lead to  1 - Mp2 < 0, which w i l l invalidate this equation. B y substituting WI2 as ^^62 into the system of equations presented i n Section 2.2, we can obtain the solution for the saturation throughput prediction from equation (2.14).  2.3  Model Validation by Simulation  In order to verify the validity of the proposed analytical model, we carry out simulations using the ns-2 simulator [20]. T h e parameters used i n the simulation are summarized i n Table 2.1. T h e network has one access point, Ni stations w i t h ACi traffic and N2 stations with AC2 traffic. A U the stations are within transmission range of each other. O n l y basic access scheme is used. Each A C is backlogged with constant bit rate traffic. T h e packets have a fixed payload size of 1020 bytes.  2.3.1  Effect o f C o n t e n t i o n W i n d o w Size D i f f e r e n t i a t i o n  We first examine the effects of different contention window size on the saturation throughput. We  set  AIFSNi  =  AIFSN2  =  2,  CWmvaX  =  15, m i  =  2,  and  CW„in2 =  31,m2  =  2  for  simulations i n Figure 2.1 according to recommended default parameter settings i n the 802.11e standard [3]. Figure 2.1 shows the aggregated satiuration throughput when we symmetrically increase the number of stations i n each A C from 2 to 20. T h e aggregated throughput for each A C and the total network throughput from simulation and the analytical model are compared. A s we can see that there is good agreement between the analytical and simulation results. Also, the aggregated saturation throughput decreases w i t h increasing number of stations due to increased coUision and backoff i n the network. Figure 2.2 shows the saturation throughput performance when the number of stations for each A C is asymmetrical i n the network. T h e number of stations i n AC\ is fixed at i V i = 5, but the number of stations i n AC2  increases from 2 to 20. CWmini  =  7 and CWmin2  = 15 are  used. Due to the asymmetry i n the number of stations, we draw the figure using the throughput per station  which is a more meaningful metric. G o o d prediction by the analytical model is  also observed.  We can also see that the per station throughput by the higher priority ACi  significantly decreases due to the increased competition from the lower priority traffic, even though its own number of stations remains the same. Thus, some admission control mechanism is needed to protect the higher priority traffic's QoS performance from the lower priority traffic. F i g i u e 2.3 shows the differentiation effect of contention window size on the saturation throughput by varying the for  ACi  In this test,  CWmin-  is fixed at 7, but the  CWmin  for  AC2  Ni  =  N2  =  10, m i =  7712  = 2,  CWmin  increases from 7 to 63. Prom the aggregated  saturation throughput for each AC, we can clearly see the effectiveness of traffic differentiation by the m i n i m u m contention window size.  2.3.2  Effect of A I F S D i f f e r e n t i a t i o n  We study the sole effect of A I F S for traffic differentiation by setting the contention window size parameters to be the same for the two access categories and only varying the A I F S value. In this simulation, AIFSN2  Ni  ^  N2  ^  5,  CWminX  =  CWmini  =  31, m i = m2 = 2,  AIFSNi  =  2.  changes from 2 to 5. T h e results are shown in Figure 2.4. Comparing Figure 2.3 and  2.4, we can see that A I F S has a more dramatic effect on traffic differentiation. Increasing A C 2 ' s A I F S by one has almost the equivalent effect of doubling its  CWmin  value. B u t setting A I F S  difference to too large a value may lead to traffic starvation for low priority traffic. Figure 2.5 shows the combined differentiation effects of this simulation, AIFSN2  Ni  = N2  =  5,  CWmini  = 31,  CWmini  CWmin  and A I F S on the traffic. In  = 63, m i = m2 = 2,  AIFSNi  = 2 and  increases from 2 to 5. T h e results also show good prediction by the analytical model.  2.4  Summary  In this chapter, we proposed a novel analytical model for saturation throughput evaluation of the I E E E 802.11e E D C A access mechanism. The proposed model is based on the use of mean value analysis. T h e distinct advantage of this model is a lower computational overhead when compared to other multi-dimensional Markov chain approaches.  A l t h o u g h there is tradeoff  between the model complexity and its accuracy, simulation results show that our model has good accuracy. T h e proposed analytical model is apphcable to real-time system tuning and on-hne admission control algorithms which require a low computation complexity.  Table 2.1: I E E E 802.11e Throughput Simulation Parameters  0  -I  Basic Rate  1 Mbps  D a t a Rate  11 M b p s  P L C P Preamble and Header  192 bits  M A C Header  192 bits  F C S (Frame Check Sequence)  32 bits  A C K Frame Size (excluding P L C P )  112 bits  T i m e Slot  20 p,s  SIFS  10  2  ,  ,  ,  5 10 16 Number of Stations in Each AC  ,  /Its  20  Figure 2.1: Throughput performance for symmetrically increasing load.  0.8  -1  I 0.6 -  I 0-5 I 0.4-  •  ACI (AnalydcaO AC1 (Simulation)  A  AC2(Analyacal) AC2 (Simulation)  a.  I 0.3 I 0.2 ^ 0.1 0 -5  10  15  20  Number ofStatlons In AC2  Figure 2.2: Throughput performance for asymmetrically increasing load.  45 -| 4 «• a- 3.5 •  S  i  a.  3  H  2.5 -  4  I-  2 -  g  • A  H 0.5  Total (Analytical) Total (Simulation) AC1 (Analytical) AC1 (Simulation) AC2(AnalytlcaD AC2 (Simulation)  •••"•••A.  H 15  CWmin for AC2  31  63  Figure 2.3: Differentiation effect of C W m i n .  8  1  7-  Total (Analytical) Total (Simulation) ACI (Analytical)  • •  ACI (Simulation) AC2 (Analytical) AC2 (Simulation)  A M  3  I"  'A-  !.. <  3 1 • 0  AIFSN2 for AC2  4  -  Figure 2.4: Differentiation effect of A I F S .  8n  t6H 5 -  • • A  Total (Analytical) Total (Simulation) ACI (Analytical) AC1 (Simulation) AC2 (Analytical) AC2 (Simulation)  1^ *1 0 3  4 AlFSNZ for AC2  Figure 2.5: Differentiation effect of A I F S and C W m i n .  Bibliography [1] I E E E 802.11 W G , "Part 11: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications," 1999.  [2] Q. N i , "Performance analysis and enhancements for I E E E 802.11e wireless networks," IEEE Network, vol. 19, no. 4, pp. 21-27, J u l y / A u g . 2005.  [3] I E E E 802.11 W G , " I E E E Std 802.11e-2005 (Amendment to I E E E Std 802.11, 1999 E d i t i o n (Reaff 2003)," Sept. 2005.  [4] G . Bianchi, "Performance analysis of the I E E E 802.11 distributed coordination function," IEEE  J. Select. Areas Commun., vol. 18, no. 3, pp. 535-547, M a r . 2000.  [5] Y . Tay and K . Chua, " A capacity analysis for the I E E E 802.11 M A C protocol,"  Wireless  Networks, vol. 7, no. 2, pp. 159-171, M a r . 2001.  [6] G . Bianchi, L . Pratta, and M . Oliveri, "Performance evaluation and enhancement of the C S M A / C A M A C protocol for 802.11 wireless L A N s , " i n Proc. of IEEE  PIMRC,  Taipei,  Taiwan, Oct. 1996.  [7] B . P. Crow, I. W i d j a j a , J . G.. K i m , and P. T . Sakai, " I E E E 802.11 wireless local area networks," IEEE  Commun. Mag., vol. 35, no. 9, pp. 116-126, Sept. 1997.  [8] J . Weinmiller, M . Schlager, A . Festag, and A . Wohsz, "Performance study of access control i n wireless L A N s - I E E E 802.11 D F W M A C and E T S I R E S 10 H I P E R L A N , " Networks and Applications,  vol. 2, no. 1, pp. 55-67, M a r . 1997.  Mobile  [9] F . C a l l , M . Conti, and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput Umit," IEEE/ACM  Trans. Networking, vol. 8, no. 6, pp. 785-799,  Dec. 2000.  [10] A . Banchs, A . Azcorra, G. Garcia, and R . Guevas, "Apphcations and challenges of the 802.11e E D C A mechanism: A n experimental study," IEEE  Network, vol. 19, no. 4, pp.  52-58, J u l y / A u g . 2005.  [11] A . Lindgren, A . Almquist, and O. Schelen, "Quality of service schemes for I E E E 802.11 wireless L A N s : an evaluation," ACM Mobile Networks and Applications,  vol. 8, no. 3, pp.  223-235, June 2003.  [12] S. C h o i , J . D . Prado, S. Shankar, and S. Mangold, " I E E E 802.11e contention-based channel access ( E D C F ) performance evaluation," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [13] D . He and G. Q. Shen, "Simulation study of I E E E 802.11e E D C F , " i n Proc. of IEEE  VTC,  Jeju, Korea, A p r . 2003.  [14] Y . X i a o , "Performance analysis of I E E E 802.11e E D C F under saturation condition," in Proc. of IEEE ICC, Paris, France, June 2004. '  [15] Z. K o n g , D . Tsang, and B . Bensaou, "Performance analysis of I E E E 802.11e contentionbased channel access," IEEE Dec. 2004.  J. Select. Areas Commun.,  vol. 22, no. 10, pp. 2095-2106,  [16] J . W . Robinson and T . S. Randhawa, "Saturation throughput analysis of I E E E 802.11e enhanced distributed coordination function," IEEE  J. Select. Areas Commun.,  vol. 22,  no. 5, pp. 917-928, June 2004.  [17] J . H u i and M . Devetsikiotis, "Performance analysis of I E E E 802.11e E D C A by a unified model," i n Proc. of IEEE Globecom, Dallas, Texas, Nov. 2004.  [18] Y . Ge and J . H o u , " A n analytical model for service differentiation i n I E E E 802.11," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [19] D . Bertsekas and R. GaUager, Data networks, 2nd ed.  Prentice H a l l , 1992.  [20] h t t p : / / w w w . i s i . e d u / n s n a m / n s / i n d e x . h t m l . ns-2 simulator.  Chapter 3  A n admission control algorithm for multihop 802.11e based W L A N s ^ W i t h the increasing demand for multimedia services (e.g., voice calls, video streaming) over wireless, the newly approved I E E E 802.11e standard [1] provides a QoS extension to the current 802.11a/b/g W L A N s . T h e Enhanced Distributed Channel Access ( E D C A ) mechanism i n 802.11e, which is a direct extension to the Distributed Coordination Function ( D C F ) , provides a contention-based QoS support. In E D C A , each traffic flow is assigned to one of four possible access categories (ACs). Each A C has a different medium access priority. It has been shown that this differentiation scheme works well when the network is moderately loaded [2]. However, due to the contention-based channel access, no strict QoS guarantee (e.g., throughput, delay) can be provided when the network becomes overloaded . For -better QoS provisioning, resoiurce management schemes such as admission  œntrol are essential to provide QoS guarantee. T h e QoS access point ( Q A P ) can  police the amount of traffic allowed into the network and maintain the network load so that it ^ A version of this chapter has been published. Y . L i n and V . W . S . Wong, " A n Admission Control Algorithm for Multi-hop 802.11e-based W L A N s , " in Elsevier Computer Communications 3510-3520, September 2008.  Journal, vol. 31, issue 14, pp.  is below a certain threshold. W i t h the increasing popularity of the 802.11-based W L A N s , there has been an interest i n providing wireless Internet access v i a multi-hop  WLANs or mesh W L A N networks [3, 4]. In  a multi-hop W L A N , one or more Q A P s are connected to the Internet backbone. T h e mobile stations form an ad-hoc multi-hop network and relay the traffic to the Q A P v i a each other (see Figure 3.1). I n densely populated areas, network access can be easily extended w i t h this multi-hop structure without the cost of deploying more infrastructure devices [5]. T h i s wireless mesh topology combines the advantages of W L A N ' s infrastructure working mode and the pure ad-hoc working mode. T h e network is both self-organizing and self-configuring. T h i s leads to minimal upfront investment and ease of incremental installation. Admission control for multi-hop W L A N s is a challenging issue. For the single-hop W L A N case, all the Q A P s and mobile stations experience similar medium access contention. The admission decisions are then based on the assumption that all the nodes can monitor the network conditions by some local measurements. However, for the multi-hop W L A N case, due to the location-dependent contention, the local medium usage information becomes ineffective to capture the traffic contention situation i n the whole network. Thus, admission control algorithms proposed for the single-hop case cannot be directly extended to the multi-hop scenarios. In this chapter, we propose an effective admission control algorithm for multi-hop W L A N s based on the I E E E 802.11e E D C A QoS extension. In our proposed admission control algorithm, we first use a contention graph (or conflict graph) to model the contention situation i n the multi-hop W L A N . It is followed by an estimation of the capacity for each maximal clique i n the contention graph v i a the use of the 802.11e saturation throughput analysis. A new flow is admitted if the aggregated traffic load is less than the estimated network capacity.  Node mobility is further considered i n the system model. Handoff connections are given a higher priority i n order to reduce the probability of dropping an on-going connection. Simular tions are conducted under both linear and random topologies. Results show that the proposed algorithm is effective i n providing QoS guarantee to the existing voice and video flows while maintaining a good performance for best effort traffic. In order for effective admission control, performance evaluations of E D C A function are required. Throughput analysis has been conducted by using either simulation or analytical methods. Most of the proposed analytical models extend the Bianchi's Markov chain model to take into account the different Arbitration Inter-Frame Space ( A I F S ) and the different Contention W i n d o w ( C W ) sizes. However, these extensions are not trivial. T h e use of multi-dimensional Markov chains and other non-linear equations lead to higher computational complexity. It may not be possible to obtain real-time solutions for these equations. Thus, although some of these models provide good accuracy, the high computational complexity may prevent them from i m plementing i n real-time control functions such as on-line call admission control algorithms i n I E E E 802.11e networks. I n this chapter, we utilize the saturation throughput model for 802.11e E D C A access scheme from the previous chapter. T h e rest of this chapter is organized as follows. In Section 3.1, we provide an overview of the related new features i n I E E E 802.11e and the related work i n this area. In Section 3.2, we present the contention analysis for multi-hop W L A N s and describe our proposed admission control algorithm for both stationary and mobile networks. Simulation results and discussions are presented i n Section 3.3. Conclusions are given i n Section 3.4.  3.1  Related Work  In this section, we first describe the extension of the M A C protocol i n the I E E E 802.11e standard. It is followed by a summary of various admission control algorithms.  3.1.1  I E E E 802.11e  T h e I E E E 802.11e standard [1] defines a H y b r i d Coordination Function ( H C F ) to provide QoS guarantee.  T h e H C F can use either a contention-based channel access method E D C A  or a controlled channel access method H C C A ( H C F Controlled Channel Access).  E D C A is  distributed and is compatible w i t h the legacy D C F mechanism. For E D C A , diflFerent traffic types are assigned to one of the four A C s . E D C A diflFerentiates traffic priorities by assigning different sets of parameters to each A C . T h e parameters include the arbitration interframe space ( A I F S ) , m i n i m u m and m a x i m u m contention window sizes and  CWmax),  {CWmin  and transmission opportunity ( T X O P ) .  This traffic diflFerentiation works well i n light to medium network load conditions. W h e n the network load is high, increasing contention introduces excess colHsions and retransmissions, which leads to a decrease i n network throughput and an increase of delay [2]. To protect the existing traffic flows and provide QoS guarantee to the new flows, the I E E E 802.11e network can use admission control for resource management. T h e I E E E 802.11e standard [1] defines the basic procedures for contention-based admission control for E D C A . A mobile station which needs to initiate a new real-time flow w i l l first send an ADDTS.request  (Add-Traffic-Stream Request) frame to the Q A P . T h e station specifies  the traffic parameters such as the nominal M S D U ( M A C Service D a t a Unit) size, mean data  rate, and surplus bandwidth allowance in the ADDTS.request  frame.  Based on the requested  traffic parameters and the network state, the Q A P makes an admission decision, and sends back the results i n the ADDTS.response frame. Note that the 802.11e standard only defines the signaling frame format for admission control. T h e network operators are free to implement their own admission decision algorithms. T h i s chapter proposes an admission control algorithm for E D C A - b a s e d multi-hop W L A N s .  3.1.2  Related W o r k in Admission Control in W L A N s  Due to the scarcity of wireless spectrum, radio resource management ( R R M ) is essential i n QoS provisioning for wireless communication systems. R R M includes strategies and algorithms for wireless channel allocation, power control, modulation and coding schemes. Admission control is an important part of R R M , which grants or denies access of an arriving call to the network. The admission control decision is usually based on some predefined criteria, which depends on the network traffic condition, and the characteristics of the arriving call, such as its required network resources and whether it is a new or handoff call. Admission control has been extensively studied for the wireless cellular networks i n the past two decades [6]. For example, admission control for C D M A wireless networks has attracted particular interest due to its soft capacity limit. C a l l admission control is carried out to achieve a m i n i m u m signal-to-interference ratio (SIR). Another design criterion i n wireless cellular networks is to control the handoff dropping probability i n order to reduce the incidents of dropping an active call. Admission control for W L A N s has attracted more interest i n recent years. Due to the probabilistic nature of the 802.11 medium access control, admission control for W L A N s has many  new challenging problems to solve. In [7], a distributed measurement-based admission control method is proposed for an 802.11 W L A N working i n ad-hoc mode. E a c h mobile node measures the occupied bandwidth or the average collision ratio, and makes the admission decisions with a simple threshold rule. In [8-10], the expected network throughput or delay performance is estimated based on extensions to the Markov-chain model i n [11] by applying the analytical model w i t h measured parameters. A n admission control decision is made at the Q A P based on the new flow's request and the analytical prediction. However, it requires that admission control be applied to all four access categories, which may not be practical for bursty elastic data traffic such as H T T P (Hyper Text Transfer Protocol) sessions. The work i n [12] further extended the analytical modeling to 802.11e networks and proposed an admission control scheme by considering both bandwidth and delay performances.  When  a new call arrives, the expected collision probabihty is derived. The expected throughput and virtual time slot length are then calculated i n order to compare them w i t h the bandwidth and delay requirements of the incoming call. T h e new call is accepted when both throughput and delay requirements are met. A measurement-based admission control and dynamic bandwidth allocation scheme for the 802.11e H C C A function is proposed i n [13] where the admission control is based on a threshold policy. In [14], a distributed admission control scheme is proposed, which can be used i n both infrastructure and ad-hoc modes. The Q A P measures the medium utihzation, and announces the transmission opportunity budget ( T X O P B u d g e t ) via periodic beacon signals for each A C (except A C 0 for best-effort traffic).  W h e n the T X O P B u d g e t for one A C is depleted, new  flows cannot gain transmission time and the existing flows cannot increase the transmission time either. In this case, the existing flows are protected.  Several enhancements are further  proposed i n [2] by adjusting the contention level for data traffic. T h e above admission control schemes are designed for the traditional single hop W L A N s working under either infrastructure or ad-hoc mode. A reinforcement learning based admission control algorithm is introduced for a multi-hop mesh network i n [15] where the admission objective is to maximize the network utiUty. T h i s admission control scheme works well for a network w i t h only best-effort traffic where the network operator's revenue can be maximized. B u t the admission control algorithm cannot provide QoS support for real-time fiows because the throughput and delay performance is not guaranteed. T h e work i n [16] proposed a contention aware admission control protocol ( C A C P ) to support QoS i n multi-hop ad-hoc networks.  Each node calculates the local available bandwidth by  sensing the portion of the wireless medium time being idle. T h e available bandwidth i n the carrier-sensing range neighborhood (c-neighborhood) is attained by either actively exchanging control frames or passively monitoring the channel. A n admission control decision is made based on the bandwidth demand of the incoming flow and the available bandwidth at both the node and its c-neighbors. In [17], an admission control scheme for V o I P calls i n a 802.11based wireless mesh network is proposed. However, the network capacity arising from multihop interference is estimated firom simulation tests. T h e above schemes only work w i t h one class of traffic for the 802.11-based ad-hoc networks. In our work, we aim to design an admission control algorithm that can support multiple classes of traffic with different QoS requirements i n a multi-hop W L A N environment.  3.2  Admission Control System Model  In this section, we first describe the network model and the assumptions for the 802.11e admission control scheme. It is followed by a discussion of the contention graph and maximal chques. We then introduce our proposed admission control framework and describe how to estimate the capacity of each m a x i m a l clique by the saturation throughput analysis. We also describe the requirements to implement our proposed admission control algorithm i n a Q A P .  3.2.1  Network M o d e l and  Assumptions  Consider a multi-hop W L A N which is comprised of a set of N nodes and a set of L logical links. There is an access point which connects to the Internet and acts as the gateway for a l l the other mobile nodes i n the network. W i t h o u t loss of generality, we consider two A C s for E D C A . A l l the nodes use the same modulation scheme and transmission power, and are assumed to have the same receiver sensitivity performances. Thus, under similar propagation conditions, we can assume that every node has an identical transmission range rtx. T h e assumption of identical transmission range is widely adopted i n the study of 802.11-based wireless networks [18-21]. One advantage of this simphfied physical model is that the algorithms and protocols i n the M A C and network layers can be more succinctly and clearly presented. We follow this simphfied physical layer model to present the proposed admission control algorithm. Furthermore, a traffic flow subject to admission control usually keeps active from a few seconds to a few minutes, which is much longer than the time scale under which the wireless fading takes effect. A s a result, it is suitable to consider the average link condition over a period of time for admission control purposes instead of the instantaneous transmission range imder fading.  If a device utilizes  adaptive transmission power control, its transmission range will change over time due to power control.  T h e proposed admission control framework can handle this situation as well.  We  simply need to update the varying transmission range to the access point periodically, which w i l l introduce extra protocol overhead. B u t , if each node's propagation environment is different, the problem of accurately estimating each node's transmission range is beyond the scope of this chapter. A logical link exists between two nodes if the distance between them is less than or equal to rtx- T h e transmission from node i to j is successful if [22]:  1. There is a logical link between nodes i and j.  2. N o other nodes which are w i t h i n the interference range  Tint  of node  j  transmit simulta-  neously.  3.2.2  Contention G r a p h  In general, the interference range  Tint  is larger than  rtx-  T h e packets transmitted within the  interference range may experience location-dependent contention for channel access. To captiure the contention relations between different neighboring links i n the network, we can construct a flow contention graph G = {V,E}  based on the above network model. In a contention graph,  vertices correspond to the logical links.  Each vertex v G V represents a logical link i n the  corresponding network graph. Given two logical links u and v e V, there is an edge e^^ G J5 if those two links are within the interference range of each other and they cannot be active simultaneously. A s an example. Figure 3.2(a) is a representation of the network topology for the scenario i n Figure 3.1. T h e resulting contention graph is shown i n Figure 3.2(b).  In a contention grapii, an induced subgraph which is complete is called a clique. In a clique, every vertex is adjacent to every other. A maximal clique is a clique which does not belong to any other larger cUques. For example, i n Figure 3.2(b), there are three maximal cliques: links {1, 2, 3}, links {1, 2, 4, 5}, and Unks {1, 4, 5, 6}. A l l the Unks i n each maximal clique share the same channel resources and thus only one of them can be active at any given time. However, links which belong to different maximal chques can be active simultaneously.  3.2.3  C o n t e n t i o n A n a l y s i s of 802.11e W L A N  Consider a contention graph which has M maximal chques. We define the contention matrix F as:  f  1,  if hnk I e chque m ,  0,  otherwise.  (3.1)  T h e dimension of matrix F is M x L . Suppose there are i n total S traffic flows between mobile nodes and the Q A P . We deflne the routing matrix R as follows: f 1,  if flow s uses link Z,  0,  otherwise.  (3.2)  T h e dimension of matrix R is L x 5. For the S flows i n the network, we assume that they belong to one of the two access categories (i.e., AC\ or AC2).  We define the source rate vector for Ad  Xi  =  \xii,Xi2,...,Xis^,  where Xij is the source rate of flow j i n ACi.  as:  i =  l,2  (3.3)  T h e traffic load from ACi on each hnk can be calculated as:  Vi = R x i  =  [yii,yi2,yiif  where yu is the total traffic load on hnk I from Ad T h e traffic load from Ad  1,2  (3.4)  1,2  (3.5)  traffic.  on each maximal chque is:  Zi = Fyi  =  [zii,Zi2,... ,ZiM  A new flow can be accepted only when the total traffic load on each maximal clique does not exceed the available capacity Cj i n that cUque. T h a t is,  Zi  :< 7i C i ,  i=  1,2  (3.6)  where 0 < 7i < 1 and is a tunable parameter. T h e challenge presented by the above admission decision framework is how to obtain an accurate estimation of the capacity Cj i n each maximal clique. O n a wirehne communication link, the channel capacity is usually well defined because the communication channel is a dedicated link between one transmitter and one receiver. O n the other hand, for wireless networks, the channel capacity can be interpreted i n different ways. Some may view it as the physical layer transmission rate which is a fixed value given the transmission power, coding and modulation schemes. However, i n a C S M A / C A based W L A N , the throughput achieved by each node usually falls short of the physical transmission rate due to the protocol overhead and the contention to the shared transmission medium. Thus, it is appropriate to define the wireless channel capacity as the attainable throughput above the M A C layer, which is simflar to the definition used i n [23]. For example, i n an I E E E 802.11 network, the achievable system throughput is usually less than 80% of the physical  transmission rate [11]. A n d this value varies with the number of stations i n the network and the selected M A C parameters. T h u s , i n this chapter, we use the achievable throughput as the channel capacity instead of the nominal physical transmission rate.  3.2.4  Available Capacity Estimation  T h e determination of the capacity of multi-hop W L A N s is a non-trivial task. Information theory may provide a general bound of the achievable capacity [23-25]. However, the assumptions used in those models restrict their applicability to ï)rovide an accurate capacity estimation i n 802.11based multi-hop W L A N s . To this end, we use the concept of saturation  throughput i n a single  hop W L A N and extend it to the multi-hop case. In a single-hop W L A N , the saturation throughput is defined as the throughput hmit reached by the network i n an overload condition (i.e., each node always has data packets to send) [11].  To study the effectiveness of using the saturation throughput as a capacity measure,  a simple ns-2 simulation experiment is r u n for an 802.11b W L A N with ten mobile stations. E a c h station generates constant bit rate ( C B R ) traffic flow and the data packet size is 1500 bytes. Figure 3.3 shows the measured network throughput as a function of the offered traffic load.  We can observe that the network throughput increases hnearly w i t h the offered load  until it reaches the maximum  throughput.  Afterwards, the network enters the overload state  and the throughput remains at the saturation throughput level, which is slightly lower than the maximum throughput. A s a result, the saturation throughput is a good performance figure of the system. It represents the m a x i m u m load that the system can carry i n stable condition. Recall that Ci = [cji, Ci2, • • • , CIM]^  denotes the capacity vector of A C i. T h e element Cim  denotes the capacity (i.e., saturation throughput) of maximal clique m for ACi.  Given the  set of ax;tive nodes i n each maximal chque m e M, the saturation throughput is used as the achievable throughput estimate for Cim. There are several analytical models for saturation throughput determination i n the literature (e.g., [26-29]). We use the one proposed i n [30]. Let Nim (i = l i 2) denote the number of nodes w i t h active Ad  traffic i n maximal chque m. Prom  [30], we have Cim = rsi,mTp,i,  i = l,2,  m = 1,2,...,M  (3.7)  where Tp,» is the time used to transmit the frame payload information for an ACi packet, and  rsi,m  =  Kmil-pim-^)KmTi  rs2,m  =  (l-p2)[(l-f)ifmri+ (l-Ç)T2]-\  Km  =  + {l-^)T2]-\  (3.8)  (3.9) (3.10)  JV2m T-2  where t j denotes the probabihty for an ACi packet to transmit i n an idle time slot, Nim denotes the number of nodes i n m a x i m a l chque m that have A C i traffic to send, Pi denotes the packet colhsion probability of an ACi packet, and Tj is the time required to finish a transmission cycle for ACi traffic. T h e equations required to obtain the numerical solutions for the above variables can be found i n Chapter 2 and [30]. T h e saturation throughput is the throughput achieved when all Nim nodes i n the maximal chque m always have A C i traffic to send. T h i s can be a good estimation of the capacity of a chque. Since the saturation throughput is slightly lower than the m a x i m u m throughput which the network may achieve, this can also be viewed as a conservative estimation of the capacity of a chque. However, for admission control decisions, a conservation approach can always ensure better QoS guarantee.  3.2.5  Admission Control Algorithm  We now describe how to implement our proposed admission control algorithm at the Q A P . We assume that all wireless stations are stationary and each station has access to some location service which can provide the geographical coordinates.  For outdoor apphcations, G P S is  nowadays readily available. In addition, different localization techniques can be used i n our work, as presented i n recent research papers [31, 32]. T h e position information is sent to the access point i n the initial association process. W h e n a wireless station initializes a new flow, it sends an ADDTS.request  frame to the Q A P . W h e n the Q A P receives the request frame,  it updates the contention matrix F , the routing matrix R and the soiurce rate vector Xi (by assuming that the new flow is accepted). It then computes the expected traffic load Zi. T h e Q A P then calculates the expected saturation throughput i n each maximal clique and uses it to construct the m a x i m a l cHques' capacity vector c». T h e new flow will be accepted only if equation (3.6) is satisfied. Otherwise, the new flow w i l l be rejected. Finally, the Q A P will notify the mobile station its decision v i a the ADDTS.response  frame. T h e admission control algorithm  is summarized i n A l g o r i t h m 1. T h i s algorithm works w i t h stationary stations. Extension to mobile nodes w i l l be discussed i n Section 3.2.7.  3.2.6  E x t e n s i o n for Best-effort  Traffic  T h e algorithm described i n the previous section assumes that both ACi and AC2 traffic flows are subject to admission control. However, data traffic are usually bursty i n natiure and may not be suitable for admission control. Instead, one needs to protect those best effort flows so that the event of bandwidth starvation wiU not occur. O u r proposed algorithm can be extended to handle the case of best-effort traffic.  A l g o r i t h m 1 Admission Control A l g o r i t h m 1: Initialization: Q A P gathers all mobile stations' location information. 2: for an ADDTS.request  arrives at the Q A P , do  3:  O b t a i n the updated F , R and Xi (by assuming that the new flow is accepted).  4:  Calculate Zi based on equation (3.5).  5:  Calculate the clique capacity Ci  6:  if equation (3.6) is satisfied, then  7: 8: 9:  accept the new flow. else reject the new flow.  10:  end if  11:  Send admission decision to mobile station v i a ADDTS.response  12:  end for  frame.  W i t h o u t loss of generality, we assume that ACi is subject to admission control and AC2 is for best-eflfort traffic. T h e active links used by the best-effort traffic flows will still be utilized for constructing the contention graph. In addition, the number of active AC2 nodes i n each chque will also be used for chque capacity estimation. T h i s usually leads to a conservative estimation of the channel capacity for the real-time flows, because not a l l AC2 nodes may be active simultaneously. Furthermore, the best-effort traffic such as T C P flows have congestion control mechanisms and usually will not cause the network to be operated i n a saturated condition.  A s a result, the admission control A l g o r i t h m 1 can be used with the following  changes:  1. T h e source rate vector i n Step 3 will only include ACi.  2. For the decision making i n Step 6, the constraint will only be checked for  ACi.  In this case, the value of 71 can be adjusted according to the amount of network capacity allocated for best traffic traffic. For example, a small 71 i n equation (3.6) will provide more bandwidth for best-effort traffic.  3.2.7  E x t e n s i o n for M o b i l e U s e r T e r m i n a l s  T h e above analysis was based on the assumption that the network topology is stationary. However, it is not difficult to extend it to account for mobile users i n the multi-hop network. T h i s section describes the extensions needed to accommodate node mobility. T h e particular concern to investigate with mobihty is the handoff process where a mobile node may change its route to the Q A P due to its own movement or movement of any of the intermediate relaying nodes. We assume that the location information of each mobile node is periodically updated  to the Q A P , such that the Q A P may have relatively accurate location information for the admission control decision. W h e n user terminals move around, the change i n distances between nodes may alter the contention relationships between them, which i n t u r n changes the contention matrix F . Moreover, when two nodes move beyond the transmission range of each other, the wireless Hnk between them may break. A n y existing route utilizing this link will become invalid and a route discovery process will be initiated to find a new route by an ad-hoc routing protocol. T h i s will lead to a change i n the the routing matrix R. B o t h F and R are important parameters for making the correct routing decision i n the admission control algorithm. W h e n F and R change, the QoS requirement of some of the accepted calls may no longer be satisfied, and those calls may have to be dropped. Since the interference range is generally much larger than the transmission range, route changes i n R occur more often than changes in the contention graph F , and has a greater impact on system performance. A s a result, we may only consider the route change events. W h e n a mobile node switches from an old routing path to a new one, we may consider this to be equivalent to the horizontal handoff process i n a wireless cellular network where the user terminal switches from one base station to another. For new calls from a mobile station, the admission process can be carried out the same as specified i n A l g o r i t h m 1.  However, when the route between a mobile terminal and the  Q A P is changed due to node mobility and a new route is established at the mobile node, a ADDTS.renew  frame  will be sent to the Q A P requesting that the existing QoS flow be handed  over to the newly estabHshed path. U p o n receiving the A D D T S . r e n e w frame, the Q A P wUl update the F and R matrices using the updated information, and will decide whether to accept  the handoff call based on: Zi  ^  -y'iCi,  i =  (3.11)  l,2  where 0 < 7- < 1 is a tunable parameter generally greater t h a n 7 i n (3.6), such that the handoff call has a higher priority than the new calls i n order to reduce the probability of dropping an on-going call. T h e algorithm is summarized in A l g o r i t h m 2. A l g o r i t h m 2 Admission Control A l g o r i t h m - M o b i l i t y Extension 1: Hsindoff occurred: when a new route to Q A P is established, the mobile node sends ADDTS.renew  frame to Q A P  2: for an ADDTS.renew  arrives at the Q A P , do  3:  O b t a i n the updated F , R and Xi (by assuming that the handoff flow is accepted).  4:  Calculate Zi based on equation (3.5).  5:  Calculate the chque capacity Ci  6:  if equation (3.11) is satisfied, then  7:  accept the handoff fiow request.  8: i9:  else drop the handoff flow request.  10:  end if  11:  Send admission decision to mobile station v i a ADDTS.response  12: end for  frame.  3.3  Performance Evaluation  To verify the effectiveness of our proposed admission control algorithm, we perform simulation experiments by using ns-2 [33]. The I E E E 802.11 M A C parameters used are shown i n Table 3.1. T h e transmission range of each wireless station, rtx, is 100 m. T h e interference range, r-jnt is twice the transmission range.  O n l y basic access scheme is used, and no channel error is  considered. We first consider the cases when only real-time traffic is present i n Sections 3.3.1 and 3.3.2. Section 3.3.3 investigates the cases when both real-time and best-effort traffic are present. Section 3.3.4 studies the performance under node mobility.  3.3.1  Linear Topology  We first examine the performance of the proposed admission control scheme under a Unear topology w i t h 10 mobile stations, as shown i n Figure 3.4(a). T h e distance between any two neighboring stations is 100 m. Real-time traffic flows (either voice or video) arrive at each mobile station periodically. These flows are subject to the admission control algorithm proposed i n the previous section. Each voice flow is a C B R source with a fixed payload size of 208 bytes (i.e., 160 bytes G.711 payload + R T P / U D P / I P / L L C / S N A P Headers) and an inter-arrival time of 20 ms. It corresponds to an 83.2 kbps traffic stream. E a c h video traffic source is a C B R data source, using U D P w i t h a constant payload of 1500 bytes and an average inter-arrival time of 40 ms. It corresponds to a 300 kbps traffic stream. T h e A I F S N and CWmin/max  for  CWmin/CWmax  values are set according to the I E E E 802.11e standard [1].  A C _ V O (Voice flow) is 7/15, and for A C . V I (Video flow) is 15/31. A I F S N for  A C _ V O and A C . V I are both equal to 2. T h e Destination-Sequenced Distance-Vector R o u t i n g  ( D S D V ) [34] is used as tiie routing protocol. A t time 10 x i second, mobile station number i initiated a flow towards the Q A P by sending an A D D T S . r e q u e s t frame to the Q A P . It is either a video flow when i is a multiple of 3, or a voice flow otherwise. Thus, the video and voice flows arrive alternatively. T h e Q A P either accepts or rejects the flow request based on the decision rule i n equation (3.6). A value of 0.85 is used for both 71 and 72. Results for the throughput and delay performance of voice flows are shown i n Figure 3.5. The results for video flows are shown i n Figure 3.6. We compare w i t h the case when no admission control mechanism is enforced. F r o m these figures, we can observe that the admission control algorithm begins to reject the video flows at time 60s, and to reject the voice flows at time 80s. In this way, the network protects the existing voice and video flows that have been admitted to the network. A l l the admitted real-time flows have an end-to-end delay to be below 10 ms. W i t h o u t admission control, the delay begins to increase signiflcantly from time 60s onwards, and the throughput begins to decrease due to packet loss.  3.3.2  R a n d o m Topology  In the second simulation, 30 mobile stations are randomly distributed i n a 500 m x 500 m coverage area, w i t h the Q A P located at the center as shown i n Figure 3.4(b). T h e mobile stations are numbered from 1 to 30 consecutively.  A t time 10 x i second, station number i  initiates a flow to the Q A P . It is either a video flow if i is a multiple of 3, or a voice flow otherwise. A l l other parameters are the same as i n the hnear topology test. T h e throughput and delay performance for voice and video flows are shown i n Figures 3.7 and 3.8. T h e results show that the admission control algorithm rejects voice flows from time  80s, and video flows from time 90s onwards. It accepts one more video flow than the linear topology.  T h i s is expected, as the two dimensional space provides better spatial separation  between flows than the one dimensional linear topology, which leads to less contention and higher capacity i n the network.  3.3.3  R e a l - t i m e a n d Best-effort  Traffic F l o w s  In this test, we examine the efltectiveness of the admission control algorithm when both realtime and best-efltort traffic co-exist. T h e test uses the same random topology as i n the previous simulation. F T P and voice flows use the A C - V I and A C - V O E D C A parameters as specified in Section 3.3.1 respectively. T h e stations numbered 3, 6, 9 initiate three F T P flows to the Q A P v i a T C P connections at time 10s. Afterwards, voice flows arrive every 10s from station numbered 1, 2, 4, 5, 7, 8, 10, 11, and 12. We do not perform admission control on the F T P flows. For the voice flows, we set 71 = 0.6. T h e throughput and delay performance for voice flows are shown i n Figure 3.9. T h e performance of F T P flows is shown i n Figure 3.10. We can observe that w i t h a reduced 71 value, only 4 voice flows are admitted. W h e n no admission control is used, the throughput of F T P flows goes to zero. T h i s is the well-known starvation problem i n 802.11e E D C A [35]. W h e n admission control is used, F T P flows avoid starvation from excessive competition from higher priority flows. The value of the R T T (round trip time) for T C P packets value fluctuates greatly imder no admission control, but is maintained at a stable level by the admission control algorithm. Thus, our algorithm can protect the performance of the existing best effort traffic flows. We can further observe that the fourth voice flow at time 50s is rejected, but the fifth voice flow at time 60s is accepted. T h i s is due to the location-dependent contention i n the multi-hop  W A N . T h e fourth flow originates from node 5 which is farther away from Q A P than the source of the fifth flow which is node 7. A s a result, it causes more contention than the fifth flow and is rejected. T h i s shows the capability of our proposed admission control algorithm to accurately predict the location-dependent contention and maintain QoS while maximizing the spatial reuse of the network.  3.3.4  Admission Control in a Mobile  Network  We first investigate the differentiation effects of using 7^ > 7i for the handoff calls. There are 30 mobile nodes randomly located within a 500 m x 300 m coverage area. T h e Q A P is located i n the center of the coverage area. A l l the mobile nodes move according to the random waypoint mobility model. T h e maximum and m i n i m u m speeds are 10 m/s and 0 m / s , respectively. T h e pause time is 5 s. One third of the mobile nodes are sending 300 kbps video traffic, and the other two third of the mobile nodes have 83.2 kbps voice traffic streams as specified i n Section 3.3.1.  T h e A d hoc O n Demand Distance Vector ( A O D V ) routing protocol is used.  T h e call inter-arrival time is exponentially distributed w i t h a mean of 10 s. C a l l duration is also exponentially distributed w i t h a mean of 15 s. E a c h simulation runs for 500 s. We fix 71 = 72 = 0.5, and vary 7^ = j'2 from 0.5 to 1. T h e resulting call dropping probabihty, which is the ratio of the number of dropped calls divided by the total number of A D D T S . r e n e w requests, is shown i n Figure 3.11. Results show that the call dropping probability is greatly reduced by increasing the difference between 7^ and 7^. Figure 3.12 shows the average number of new ceills accepted per second. We can see that the number of accepted new calls decrease when increased priority is given to handoff calls. In Figures 3.13 and 3.14, we show the results of packet loss ratio and average number of  accepted calls per second when we increase 7^ = 72 = 7^ = 73 from 0.5 to 1. Each simulation result is the average of three simulation runs when the number of mobile nodes i n the network is 20, 30, and 40, respectively. T h e other simulation parameters remain the same. T h e results show that there is a trade-off when selecting the 7 value. A larger 7 allows more calls to be accepted, but leads to larger packet losses. Figure 3.15 shows the impact of pause time of the mobility model on the packet loss ratio. 30 nodes are used and 71 = 72 = 0.5, 7i = 72 = 0.7. It can be observed that as pause time increases, the network packet loss decreases. T h e random waypoint mobility model is the default mobility model used by ns-2, and has several shortcomings [36]. A l t h o u g h the proposed admission control algorithm is independent of specific mobihty models, its effectiveness may be influenced by the mobility scefiarios. A s a result, we perform additional simulations under the more advanced random trip mobility model [37]. Results show that there is a slightly higher packet loss ratio under the random trip mobility model. However, the loss rate is still under acceptable levels w i t h the proposed admission control mechanism. T h e decreased packet loss ratio under the random waypoint mobility model tests may be due to the fact that this model tends to put nodes slightly more concentrated into the central area of the simulation topology which can possibly decrease the routing hops and thus increase the delivery rehability.  3.4  Summary  In this chapter, an effective admission control algorithm for multi-hop W L A N s was proposed, which is based on the use of contention graph and the saturation throughput analysis for each maximal chque's capacity estimation. Simulation tests under different topologies have shown  that our proposed admission control algorithm is effective i n evaluating the contention status in a multi-hop W L A N , and makes accurate admission control decisions to prevent the network from congestion. In addition, it can provide QoS guarantee to the existing voice and video flows while maintaining a good performance for best effort traffic. Node mobihty is also considered i n the model. Simulation results show that the admission control algorithm performs well under a multi-hop W L A N w i t h mobility, and provides a mechanism to differentiate between handoff and new calls.  T a b l e 3 . 1 : I E E E 802.11e Admission Control Simulation Parameters Basic Rate  1 Mbps  D a t a Rate  11 M b p s  P L C P Preamble and Header  192 bits  M A C Header  192 bits  F C S (Frame Check Sequence)  32 bits  A C K Frame Size (excluding P L C P )  112 bits  T i m e Slot  20 fis  SIFS  10 fis  F i g u r e 3.1: A multi-hop W L A N . E a c h link is identified by an integer.  Clique {1.2,4,5}  Clique {1,|4, 5,6} (a) A n example of multi-hop W L A N topology with 6 links.  i ? l i q u e { 1 . 2 , 3}  C l i q u e {1, 2, 4;.  — - - ^ C l i q u e {1,4,  5,6}  (b) The corresponding contention graph and maximal cliques.  F i g u r e 3.2: Contention graph and maximal cliques.  Maximum Throughput  a. i3  ^  4.8  1 I 1f  i I \1  Q.  1  Saturation T h r o u g h p u t  / /  J. A  4.6  Optimal Operation R a n g e for A d m i s s i o n C o n t r o l 4.4  I-  2  4.2  •  1  4.5  --r-  5  -  -1  5.5  1  6  1  6.5  Traffic Load (Mbps)  F i g u r e 3.3: Network throughput with increasing traffic load.  1  (b) Random Topology.  F i g u r e 3.4: Simulation topologies: (a) Linear topology, (b) R a n d o m topology.  600  1 ' r Throughput (with Admission Control) Throughput (no Admission Control)  500 400h ^  300  S  200  I  i Voice Flows Rejected •by Admission Controlle •  100 0  0  20  40  80  60  100  120  Time (s) (a) Throughput.  • Delay (with Admission Contit)!)^ , j • Delay (no Admission Controlj) / I' \j  I"u  0.1  r  if'  Q  1 B  A  0.01  r  lE-3  7  ^  >  i ^/xl.jiVoice Flows Rejected . i! :by Admission ControllQ '  20  40  60 Time (s)  80  100  120  700 600 "•" _  500 -  è  400 -  - Throughput (with Adiiission Control) • Throughput (no Admifssion Control) i •* / Video Flows Rejected (1; ' ! by Admission Controller  r  r  0  1  200 -  ! Video Flow's Starvatioi ! jnthout Admission Cofirol  100 0  0  20  40  60  4L 80  100120  Time (s) (a) Throughput.  • Delay (with Admisçion Control) • Delay (no Admission Control)  S  W  0.1  ; Video Flovip Rejected ; by Admissi{>n Controller  r  Î  0.01  20  40  60 Time (s)  80  100  120  600 - Throughput (with Admission Control) - Throughput (no Admission Cdntrol) f\ ;\ . j  500  I I "3 §  400  300 jVoice Flows Rejected jby Admission Controlle  200 100 -  0  40  20  60  80  100  120  Time (s) (a) Throughput.  -1  1  r  •  1  <  r  • Delay (with Admission Control) • Delay (no Admission Control) a/  0.1  : i  r  j i  iVoice Flows' Rejected jby Admissiqn Controlle  I  -I i  i  0.01  20  40  60 Time (s)  80  1000  1  ,  1  ,  1  1  ,  ,  j  800  I  f  p  Throughput (with Admission Contiol) Throughput (no Admission Control^\^y. I  600  400 -  Video Flows Rejectê 1 byjAdmission Contrqller  200  0  20  40  60  _i  L.  80  100  120  Time (s) (a) Throughput.  1r  - Delay (with Admission Control) • Delay (no Admission Control) I I video FJOWS Rejected b;^ Admission Contipller -j-- — >  Q 0.1 r  I 0.01 r 0  20  (a) Throughput.  0.14 0.121^  0.10 h  Q  0.08 -  I  0.06 ^  ^  0.04 h  I  • èelay (wiài Admission Control) • Delay (without Admission Control) r i i  -  i !  11  ii! ii! ii! ii!  0.02 20  40  60 Time (s)  80  100  120  1500 1250 -  • Throughput (with Admission Control) • Throughput (no Admission Control)  1 IÏ  FTP Flows Bxpenence Starvation wi&out Admission Cooèol I  Ï 0 0 1 2 0  Time (s) (a) Throughput.  0.20 -  RTT (with Admission Control) RTT (no Admiss^op Cotjtrol)  0.15 -  0.10 -  IF  I  iVoice Flows Rejected \; •by Admission Controller '  1st Voice Flow Rejected by Admission Controller  0.00  20  40  60 Time (s)  80  100  120  0.1 -  Z 0.0  I  1 0.5  '  1 0.6  '  1 0.7  '  1 0.8  '  1 0.9  •  L1.0  Handoff Parameter /  F i g u r e 3.12: Average number of received calls per second w i t h different handoff parameter 7^.  1  •  I  I  1  •  I  I  r  1.5 :  0.5  I  I  0.6  I  0.7  0.8  I  0.9  I  :  1.0  Admission Panuneter y  F i g u r e 3.13: Packet loss ratio w i t h increasing admission parameter 7.  0.60  Admission Parameter y F i g u r e 3.14: Average number of received calls per second w i t h increasing admission parameter  F i g u r e 3.15: Packet loss ratio w i t h increasing pause time.  Bibliography [1] I E E E 802.11 W G , " I E E E Std 802.11e-2005 (Amendment to I E E E S t d 802.11, 1999 E d i t i o n (ReaiF 2003)," Sept. 2005.  [2] Y . X i a o , H . L i , and S. C h o i , "Protection and guarantee for voice and video traffic i n I E E E 802.11e wireless L A N s , " i n Proc. of IEEE INFOCOM,  Hong K o n g , C h i n a , M a r . 2004.  [3] S. M . Faccin, C . W i j i n g , J . Kneckt, and A . Damle, "Mesh W L A N networks: concept and system design," IEEE  Wireless Commun.  Mag., vol. 13, no. 2, pp. 10-17, A p r . 2006.  [4] O. O y m a n , J . N . Laneman, and S. Sandhu, " M u l t i h o p relaying for broadband wireless mesh networks: Prom theory to practice," IEEE Commun.  Mag., vol. 45, no. 11, pp. 116-122,  Nov. 2007.  [5] R .  Pabst,  B . Walke,  D.  Schultz,  P. Herhold, H . Yanikomeroglu,  S.  Mukherjee,  H . Viswanathan, M . L o t t , W . Zirwas, M . Dohler, H . Aghvami, D . Falconer, and G . Fettweis, "Relay-based deployment concepts for wireless and mobile broadband radio," Commun.  Mag., vol. 42, no. 9, pp. 80-89, Sept. 2004.  [6] M . H . A h m e d , " C a l l admission control i n wireless networks: a comprehensive IEEE  IEEE  survey,"  Comm. Surveys and Tutorials, vol. 7, no. 1, pp. 50-69, A p r . 2005.  [7] D . G u and J . Zhang, " A new measurement-based admission control method for I E E E 802.11 wireless local area networks," i n Proc. of IEEE PIMRC,  Beijing, C h i n a , Sept. 2003.,  [8] D . P o n g and T . Moors, " C a l l admission control for I E E E 802.11 contention access mechanism," i n Proc. of IEEE Globecom, San Francisco, C A , Dec. 2003.  [9] Y . - L . K u o , C. L u , E . W u , and G . Chen, " A n admission control strategy for differentiated service i n I E E E 802.11," i n Proc. of IEEE  Globecom, San Francisco, C A , Dec. 2003.  [10] Z. K o n g , D . Tsang, and B . Bensaou, "Measurement-assisted model-based call admission control for I E E E 802.11e W L A N contention-based channel access," i n Proc. of IEEE shop on Local and Metropolitan  Work-  Area Networks, San Francisco, C A , A p r . 2004.  [11] G . Bianchi, "Performance analysis of the I E E E 802.11 distributed coordination function," IEEE  J. Select. Areas Commun., vol. 18, no. 3, pp. 535-547, M a r . 2000.  [12] J . Zhu and A . O. Fapojuwo, " A new call admission control method for providing desired throughput and delay performance i n IEEE802.11e wireless L A N s , " IEEE Commun.,  Trans. Wireless  vol. 6, no. 2, pp. 701 - 709, Feb. 2007.  [13] Y . - J . C h o i and S. Bahk, "Feedback-based bandwidth allocation with call admission control for providing delay guarantees i n I E E E 802.11e networks," Computer  Communications,  vol. 28, no. 3, pp. 325-337, Feb. 2005.  [14] Y . X i a o and H . L i , " L o c a l data control and admission control for QoS support i n whreless ad hoc networks," IEEE  Trans. Veh. Technol, vol. 53, no. 5, pp. 1558-1572, Sept. 2004.  [15] D . Niyato and E . Hossain, "Radio resource management i n M I M O - O F D M - b a s e d wireless infrastructure mesh networks: Issues and approaches,"  IEEE  Commun.  Mag., vol. 45,  no. 11, pp. 100-107, Nov. 2007.  [16] Y . Y a n g and R . Kravets, "Contention-aware admission control for ad hoc networks," Trans, on Mobile Computing, vol. 4, no. 4, pp. 363-377, J u l y 2005.  IEEE  [17] H . Wei, K . K i m , A . Kashyap, and S. Ganguly, " O n admission of V o I P calls over wireless mesh network," in Proc. of IEEE ICC, Istanbul, Turkey, June 2006. [18] K . N a h m , A . Helmy, and C . - C . J . K u o , " T C P over multihop 802.11 networks: issues and performance enhancement," i n Proc. of ACM MobiHoc, Urbana-Champaign, I L , M a y 2005. [19] A . Acharya, A . M i s r a , and S. Bansal, "High-performance architectures for IP-based multihop 802.11 networks," IEEE  Wireless Commun.  Mag., vol. 10, no. 5, pp. 22-28, Oct.  2003. [20] P. C. N g and S. C. Liew, "Throughput analysis of I E E E 802.11 multi-hop ad hoc networks," IEEE/ACM  Trans. Networking,  vol. 15, no. 2, pp. 309-322, A p r . 2007.  [21] K . Wang, F . Yang, Q. Zhang, and Y . X u , "ModeUng path capacity in multi-hop I E E E 802.11 networks for QoS services," IEEE  Trans. Wireless Commun.,  vol. 6, no. 2, pp.  738-749, Feb. 2007. [22] G . Mergen and L . Tong, "Stability and capacity of regular wireless networks," IEEE Inform.  Trans.  Theory, vol. 51, no. 6, pp. 1938-1953, June 2005.  [23] P. G u p t a and P. K u m a r , "The capacity of wireless networks," IEEE Trans. Inform.  Theory,  vol. 46, no. 2, pp. 288-404, M a r . 2000. [24] A . Zemlianov and G . de Veciana, "Capacity of ad hoc wireless networks w i t h infrastructure support," IEEE  J. Select. Areas Commun., vol. 23, no. 3, pp. 657-667, M a r . 2005.  [25] M . K o d i a l a m and T . Nandagopal, "Characterizing achievable rates i n multi-hop wireless mesh networks with orthogonal channels," IEEE/ACM pp. 868-880, A u g . 2005.  Trans. Networking,  vol. 13, no. 4,  [26] J . H u i and M . Devetsikiotis, "Performance analysis of I E E E 802.11e E D C A by a unified model," i n Proc. of IEEE  Globecom, Dallas, Texas, Nov. 2004.  [27] J . W . Robinson and T . S. Randhawa, "Saturation throughput analysis of I E E E 802.11e enhanced distributed coordination function," IEEE  J. Select. Areas Commun.,  vol. 22,  no. 5, pp. 917-928, June 2004.  [28] Z. K o n g , D . Tsang, and B . Bensaou, "Performance analysis of I E E E 802.11e contentionbased channel access," IEEE  J. Select. Areas Commun.,  vol. 22, no. 10, pp. 2095-2106,  Dec. 2004.  [29] Y . X i a o , "Performance analysis of I E E E 802.11e E D C F under saturation condition," i n Proc. of IEEE  ICC, Paris, France, June 2004.  [30] Y . L i n and V . W . S. Wong, "Saturation throughput of I E E E 802.11e E D C A based on mean value analysis," i n Proc. of IEEE  WCNC, Las Vegas, Nevada, A p r . 2006.  [31] Y . Chen, J . - A . Francisco, W . Trappe, and R . M a r t i n , " A practical approach to landmark . deployment for indoor locaUzation," i n Proc. of IEEE SECON, Reston, V A , Sept. 2006.  [32] J . Y i n , Q. Y a n g , and L . M . N i , "Learning adaptive temporal radio maps for signal-strengthbased location estimation," IEEE  Trans. Mobile Comput, vol. 7, no. 7, pp. 869-883, J u l y  2008.  [33] h t t p : / / w w w . i s i . e d u / n s n a m / n s / i n d e x . h t m l . ns-2 simulator.  [34] C. Perkins and P. Bhagwat, "Highly dynamic Destination-Sequenced Distance-Vector routing ( D S D V ) for mobile computer," i n Proc. of ACM SIGCOMM,  London, U K , Sept. 1994.  [35] N . Ramos, D . Panigralii, and S. Dey, "Quality of service provisioning i n 802.11e networlcs: Challenges, approaches, and future directions," IEEE Network, vol. 19, no. 4, pp. 14-20, J u l y / A u g . 2005.  [36] C . Bettstetter, G . Resta, and P. Santi, "The node distribution of the random waypoint mobility model for wireless ad hoc networks," IEEE  Trans. Mobile Comput,  vol. 2, no. 3,  pp. 257-269, July-Sept. 2003.  [37] J . - Y . L e Boudec and M . Vojnovic, "The random trip model: StabiUty, stationary regime, and perfect simulation," IEEE/ACM Dec. 2006.  Trans. Networking,  vol. 14, no. 6, pp. 1153-1166,  Chapter 4  Frame Size Adaptation for I E E E 802.11n W L A N s ^ W i t h the successful deployment of I E E E 802.11a/b/g wireless local area networks ( W L A N s ) and the increasing demand for real-time applications over wireless, the I E E E 8 0 2 . l l n Working Group is standardizing a new M e d i u m Access Control ( M A C ) and Physical Layer ( P H Y ) specification [1-3]. A t the P H Y layer, 802.11n will use M I M O (multiple-input multiple-output) and O F D M (orthogonal frequency division multiplexing) to increase the bit rate to be up to 600 M b p s . T h e throughput performance at the M A C layer can be improved by aggregating several frames before transmission. Frame aggregation not only reduces the transmission time for preamble and frame headers, but also reduces the waiting time during C S M A / C A (Carrier Sense M u l t i p l e Access - Collision Avoidance) random backoff period for successive frame transmissions.  T h e frame aggregation can be performed within different sub-layers.  In 802.11n  [1-3], frame aggregation can be performed either by M A C Protocol D a t a U n i t Aggregation ( A - M P D U ) or M A C Service D a t a U n i t Aggregation ( A - M S D U ) . ^ A version of this chapter has been published. Y . L i n and V . W . S . Wong, "Frame Aggregation and Optimal Frame Size Adaptation for I E E E 802.11n W L A N s , " in Proc. of IEEE (Globecom), San Francisco, C A , November 2006.  Global Teleœmmunications  Conference  Although frame aggregation can increase the throughput at the M A C layer under ideal channel conditions, a larger aggregated frame will cause each station to wait longer before its next chance for channel access. Thus, there is a tradeoff between throughput and delay for frame aggregation at the M A C layer. Furthermore, under error-prone channels, corrupting a large aggregated frame may waste a long period of channel time and lead to a lower M A C efficiency. A s a result, there is a need to study the effects of channel conditions on the chosen frame aggregation schemes. Several papers [4-8] extend the error-free 802.11 network models [9-12] to study the throughput performance under different channel error conditions. Y i n et al. [13] study the effects of packet size i n an error-prone channel for I E E E 802.11 D C F and conclude that there is an optimal packet size under a certain bit error rate ( B E R ) to achieve the m a x i m u m throughput. C i and Sharif [14] propose an optimal frame size predictor based on K a l m a n filter to maintain a committed goodput. Most of these studies assume that a single bit error can corrupt the whole frame. T h i s assumption may not be true for the 8 0 2 . l l n M A C layer w i t h frame aggregation. In this chapter, we provide a unified approach to study the satiuration throughput and delay performance of the proposed frame aggregation schemes i n the new 8 0 2 . l l n proposals under error-prone channels. B o t h uni-directional and bi-directional transfer are being considered. T h e analytical model provides an accurate prediction for system performance which is vaUdated by simulation experiments. Based on the analysis, we propose an adaptive frame size adaptation algorithm. Simulation results show that there are significant throughput improvements when compared w i t h the randomized and fixed frame aggregation algorithms. These studies serve as the basis for further optimization of the system parameters i n the 8 0 2 . l l n W L A N s . T h e rest of this chapter is organized as follows. Section 4.1 provides an overview of 8 0 2 . l l n  frame aggregation techniques. In Section 4.2, we present an analytical model to determine the throughput and delay performance for different frame aggregation schemes under error-prone channel conditions. Simulations are presented i n Section 4.3 to validate the accuracy of the analytical model. A n adaptive frame size adaptation algorithm is proposed i n Section 4.4. A summary is given i n Section 4.5.  4.1  Related Work and Background on I E E E 802.11n  In this section, we provide an overview of several new M A C mechanisms i n 802.11n, including the frame aggregation, block acknowledgement, and bi-directional data transmission. There are two ways to perform frame aggregation at the M A C layer. T h e first technique is by concatenating several M A C Service D a t a Units ( M S D U s ) to form the data payload of a large M A C Protocol D a t a U n i t ( M P D U ) . T h e P H Y header and M A C header, along w i t h the frame check sequence ( P C S ) , are then appended to form the Physical Service D a t a U n i t ( P S D U ) . T h i s technique is known as MSDU  Aggregation ( A - M S D U ) . Figure 4.1 shows the frame format for  A-MSDU. T h e second technique is called MPDU-aggregation  ( A - M P D U ) . It begins w i t h each M S D U  appending w i t h its own M A C header and P C S to form a s u b - M P D U . A n M P D U delimiter is then inserted before each s u b - M P D U . P a d d i n g bits are also inserted so that each s u b - M P D U is a multiple of 4 bytes i n length, which can facihtate subframe delineation at the receiver. T h e n , all the s u b - M P D U s are concatenated to form a large P S D U . Figure 4.2 shows the frame format for A - M P D U . T h e 802.11n also specifies a bi-directional data transfer method. If R T S / C T S is used, the  current transmission sequence of R T S (Request To Send) - C T S (Clear To Send) - D A T A (Data frame) - A C K (Acknowledgement)  only allows the sender to transmit a single data frame. In  the bi-directional data transfer method, the receiver may request a reverse data transmission in the C T S control frame. The sender can then grant a certain medium time for the receiver on the reverse hnk. T h e transmission sequence will then become R T S - C T S - D A T A f - D A T A r A C K . T h i s facihtates the transmission of some small feedback packets from the receiver and may also enhance the performance of T C P (Transmission Control Protocol) which requires the transmission of T C P A C K segments. In a l l of the above cases. Block Acknowledgement  ( B A C K ) can be used to replace the  previous A C K frame. The B A C K can use a bit map to efficiently acknowledge each individual sub-frame w i t h i n the aggregated frame. For the bi-dfrectional data transfer, the reverse D A T A r frame can contain a B A C K to acknowledge the previous D A T A f frame. In the rest of this chapter, we w i l l focus on the study of frame aggregation and bi-directional data transfer schemes.  4.2  The Analytical Model  We extend Bianchi's model [9] to study the A - M P D U , A - M S D U frame aggregation under errorprone channels. In the analytical model, we assume that there are N mobile stations i n the W L A N . E a c h mobile station has saturated traffic. The wireless channel has a bit-error-rate ( B E R ) of Pi,. T h e m i n i m u m contention window size is W and the maximum backoff stage is m. Since the size of an aggregated frame is large, the R T S / C T S access scheme is generally more efficient than the basic access scheme. A s a result, this chapter only discusses the access scheme  w i t h R T S / C T S . In 802.11 W L A N s , the control frames ( R T S , C T S , B A C K ) are transmitted at the basic rate which is much lower than the data rate. Thus, the control frames are more robust i n combating errors. Since the sizes of these control frames are much smaller than an aggregated data frame, they have a much lower frame error rate. In addition, the P L C P (Physical Layer Convergence Procedure) preamble and header are also transmitted at a lower rate. To simplify the analysis, we do not consider the frame error probabilities for control frames and preambles. T h e possible t i m i n g sequences for A - M P D U and A - M S D U i n the uni-directional transfer case are shown i n Figure 4.3. The timing sequences for bi-directional data transfer are shown in Figure 4.4. In both figures, the D A T A frame represents either an A - M P D U or an A - M S D U frame. T h e system time can be broken down into virtual time slots where each slot is the time interval between two consecutive countdown of backoflF timers by non-transmitting stations. Prom [9], the transmission probability r in a virtual slot is:  (1 - 2p){W  + l)+pW{l  - (2p)'")'  (41) ^ • '  where p is the unsuccessful transmission probability conditioned on that there is a transmission i n a time slot. W h e n considering both collisions and transmission errors, p can be expressed as: p = l-(l-Pe)(l-Pe), where pc = I - {I - T)^^~^^  (4.2)  is the conditional collision probability and pe is the error prob-  ability on condition that there is a successful R T S / C T S transmission i n the time slot.  For  uni-directional transfer, Pe is the error probability corresponding to the error case i n Figmre 4.3(b). For bi-directional transfer, we define pe as a2 x 1 vector Pe = \pe,i,Pe,2]^ (where T is  the transpose) corresponding to the two error cases i n Figure 4.3(b) and (c). In the following, we w i l l use the vector form for generality, and equation (4.2) for the bi-directional case is:  p=l-(l-pc)(l-Pe,l)  (4.3)  Note that only pe,i for Figure 4.3(b) contributes to p. T h i s is because i n the case of Figure 4.3(c), we follow our previous assumption that the BACKf BACKf  control frame is error-free. Thus,  for the forward frame is always successful and the DATAfs  sending station w i l l not  double its contention window i n this case. T h e probability of an idle slot is:  Pi<«e = ( l - r ) ^  (4.4)  T h e probabihty for a transmission i n a time slot is:  Ptr^l-  Pidie = ! - ( ! -  r)^.  (4.5)  T h e probability of a non-colhded transmission is that only one station transmits, which equals NT{1 - T)^~^.  So, the probabihty for a transmission to be not collided with another  station is:  Ptr T h e transmission failure probabihty due to error (no collisions but having transmission errors) is: Perr = Ptr Ps Pe = [Perr.l.Perr.a]^ where Perr.i and  Perr,2  (4.7)  correspond to the two different error timing sequences for the b i -  directional transfer i n Figure 4.4. Perr reduces to a scalar for the uni-directional case.  T h e probability for a successful transmission (without collisions and transmission errors) is:  Psucc = PtrPsil  (4.8)  - Pe,l - Pefi)-  T h e network's saturation throughput can be calculated as:  5 = | ,  (4.9)  where Ep is the number of payload information bits successfully transmitted i n a virtual time slot, and Et is the expected length of a virtual time slot. We have:  Et = TidlePidle + TcPtril  - Ps) + T e ^ P e r r + Ts^œPsucc,  (4.10)  where TicUe, Tc and Tsucc are the idle, collision and successful virtual time slot's length. T e is the virtual time slot length for an error transmission sequence. Similar to Pe, it corresponds to a scalar for the uni-directional case, and a 2 x 1 vector for the bi-directional transfer timing sequence. A p a r t from throughput, we study the average access delay experienced by each station i n the uni-directional case. T h e access delay is defined as the delay between the time when an aggregated frame reaches the head of the M A C queue and the time that the frame is successfully received by the receiver's M A C . W i t h the saturation throughput 5, each frame takes an average of Lp/S  to transmit [Lp is the aggregated frame's payload length).  There are N stations  competing for transmission. O n average, the access delay is:  d = iV^,  (4.11)  To calculate S and d from equations (4.9) and (4.11), the parameters of Ep, Tidie, Tc, Tgucc,  T e and Pe need to be determined. Tjd/e is equal to the system's empty slot time a. (4.12)  Tc = RTS + EIFS,  where R T S is the transmission time for an R T S frame. T h e other parameters are case-dependent and will be discussed separately i n the following subsections.  4.2.1  Uni-directional M A C  In the uni-directional case, the equations for Tsucc, 2e and Ep are as follows: Tsucc =  RTS + CTS+  DATA  Te  =  RTS + CTS + DATA+  Ep  =  LpP,ucc = LpPtrPsil-Pe),  +BACK+ EIFS  3SIFS + 2SIFS,  +DIES,  (4.13) (4.14) (4.15)  where C T S , B A C K and D A T A are the transmission time for C T S , B A C K and the aggregated data frame, respectively. For A - M S D U , the equations for pe and Ep are: Pe  =  l-(l-Pt)^,  (4.16)  Ep  =  {L-LHdr)PtrPs{l-Pe),  (4.17)  where L is the aggregated M A C frame's size, and Lhdr is the total length of M A C header and FCS. For A - M P D U , error occurs when all the sub-frames become corrupted. T h e variables pe and Ep can be expressed as: Pe  =  Ep  =  Hil-il-Ptf^), i  53(Li -  L«„6Mr)i'trP.(l - n ) ^ %  (4.18) (4.19)  where i is from 1 to the total number of aggregated s u b - M P D U s , and Li is the size for the i * ' ' s u b - M P D U . Lsubhdr is the total size of each s u b - M P D U ' s delimiter, header, and P C S .  4.2.2  Bi-directional M A C  For the bi-directional M A C transfer function, there are also the two aggregation methods: A M P D U and A - M S D U . Due to the space limitation, we only present the results for A - M S D U aggregation i n this chapter. T h e A - M P D U case can be derived i n a similar way based on the following discussions. For error i n the forward frame (see Figmre 4.4(b)), we have:  Te,i  =  RTS + CTS  Pe,i  =  1 - (1 -  + DATAf  + 2SIFS  + EIFS,  P6)^^^^A  (4.20) (4.21)  For error i n the reverse frame (see Figure 4.4(c)), we have:  Te,2  =  RTS  + CTS  + ZSIFS  DATAr Pe,2 =  + DATAf  + BACK  f + (4.22)  + EIFS,  (1-P6)^^^^^[1-(1-P6)^^^^'-].  (4.23)  For a successful bi-directional frame transmission:  Tsucc =  RTS + CTS +BACKr  Since we assume that the BACK  + DATAf  + 4SIFS  + BACK  f  +DATAr  + DIPS.  control frame is transmitted at the basic rate,  (4.24)  DATAf  will be successfully received i n the case of Figure 4.4(c). Thus, the expected successful payload  information transmitted Ep can be expressed as:  4.3  —  i^f +I^r-  2Lhdr)Psucc + (Lf - Lhdr)Perr,2  =  {Lf + Lr-  2LMr)PtrPs(1  - Pe.l - Pefl) + {Lf - Lhdr)PtrPsPe,2  (4.25)  Simulation and Model Validation  To verify the accuracy of the analytical model proposed in Section 4.2, simulations are carried out i n the ns-2 simulator [15] for throughput and delay performance comparison w i t h the analytical model. T h e parameters used i n the simulation are from [16]. T h e y are also shown in Table 4.1.  4.3.1  U n i - d i r e c t i o n a l D a t a Transfer  In this simulation, there are 10 wireless nodes and one access point i n the network. A l l the wireless nodes have saturated C B R (constant bit rate) traffic directed to the access point. The B E R varies from 0 to 10~^. A l l the data packets passed down to the M A C layer are 100 Bytes i n length. T h e number of packets aggregated i n one M A C frame varies from 1 to 80, which leads to an aggregated payload size from 100 Bytes to 8 K B y t e s . Figures 4.5 and 4.6 show the saturation throughput and access delay for the A - M S D U aggregation. Figures 4.7 and 4.8 show the saturation throughput and access delay for the A M P D U aggregation.  A l l the lines i n the figures are the results obtained from the analytical  model. T h e simulation results are shown i n discrete marks. Comparison w i t h the simulation results show that the analytical model is accurate i n predicting the network performance. From these figures, we can observe that the saturation throughput decreases and the de-  lay increases w i t h increasing B E R for both aggregation schemes. A - M S D U achieves a higher throughput t h a n A - M P D U under ideal channel conditions (i.e., B E R = 0). T h i s is due to the fact that A - M S D U includes a lower overhead i n the aggregation process than A - M P D U . However, under error-prone channels, the advantage of A - M S D U quickly diminishes. T h e curves in Figure 4.5 show that the throughput under A - M S D U first increases, and then decreases with increasing aggregated frame size i n error-prone channels. T h i s is because without the protection of P C S i n individual sub-frames, a single bit error may corrupt the whole frame which wiU waste lots of mediiun time usage and counteract the efficiency produced by an increased frame size. For A - M P D U , the throughput monotonically increases w i t h increasing aggregated frame size. A s a result, it is more beneficial to use A - M S D U under good channel conditions and A - M P D U under bad channel conditions. Although the throughput increases by increasing the aggregated frame size for A - M P D U , the frame size cannot be increased indefinitely due to the delay constraint by many applications. A s a result, we need to choose the proper aggregation scheme and adapt their parameters according to the different channel conditions and appUcation requirements i n order to achieve an optimal performance. T h i s chapter provides the performance analysis model. In Section 4.4, we will investigate the performance of a simple adaptive frame size adaptation algorithm for A - M S D U under error-prone conditions.  4.3.2  B i - d i r e c t i o n a l D a t a Treinsfer  T h e satiuration throughput performance for A - M S D U with bi-directional data transfer under different B E R is shown i n Figure 4.9. T h e numbers of aggregated M S D U s i n the forward and reverse data aggregation are set to 20 and 1, respectively. T h e number of stations is varied  from 5 to 30. T h e simulation results validate the accuracy of the analytical model i n predicting the network performance. Comparing with Figure 4.5, the bi-directional transfer provides not much gain from the aspect of saturation throughput performance. Its major contribution to the system improvement is the interaction to the higher layer protocols (e.g., T C P ) for the transfer of acknowledgement segments i n a timely manner.  4.4  Optimal Frame Size Adaptation for A - M S D U  From Figure 4.5, we can observe that A - M S D U may reach a m a x i m u m throughput imder different B E R conditions.  T h e optimal aggregated frame size L* to achieve this maximum  throughput varies w i t h the channel's B E R condition. To further determine the relationship between L* and the number of contending stations, we conduct an experiment i n which the number of stations changes from 10 to 30. T h e other parameters are the same as i n Section 4.3. T h e analytical and simulation results are shown i n Figiure 4.10. From Figure 4.10, we can observe that the optimal aggregated frame size L* is very sensitive to B E R , but rather insensitive to the number of contending stations i n the network. To this end, we propose a simple and efffective frame aggregation adaptation algorithm to be as foUows: First, we determine the L * - B E R curve from the analytical model i n Section 4.2 by using an average number of stations N i n the network. T h e L * - B E R curve gives the optimal aggregated frame size L* under different channel bit-error-rate. Before transmitting an aggregated A M S D U frame, the sending station will obtain an estimation of the channel B E R , consult the L * - B E R curve for an optimal L*, and then construct the aggregated frame w i t h a size that is close to the optimal frame size.  T h e channel B E R is a function of the modulation scheme and the S N R (Signal-to-noise ratio).  In general, for a given modulation and coding scheme, the B E R can be determined  either from a theoretical or an empirical B E R - S N R curve. T h e S N R is measured at the receiver for each received frame.  W i t h the help a closed-loop feedback mechanism, this S N R may  be efficiently updated to the sender.  For example, i n the 8 0 2 . l l n proposals, there is a new  M A C feature for channel management which is called the receiver-assisted link adaptation  [1].  Channel conditions are fed back to the sender by control frames i n a closed-loop fashion. In this chapter, we assume that such a feedback mechanism is available i n 8 0 2 . l l n to provide the sending station w i t h the channel S N R information. To determine the effectiveness of our proposed frame adaptation algorithm, we conduct an ns-2 simulation. We use the Channel B error model from [16], which models a typical large open space and office environments which have non-line-of-sight conditions, and 100 ns rms delay spread.  T h e 144.44 M b p s data rate is used which leads to an effective transmission  range of 25 m. T h e network topology consists of an open space of 50 m x 50 m. T h e access point is fixed at the center of the area. There are N wireless nodes i n the network, and they move according to a random waypoint mobility model.  T h e m a x i m u m speed is 5 m / s and  the pause time is 5 s. A l l the wireless terminals are saturated w i t h C B R traffic. T h e number of stations  is varied from 5 to 20. T h e throughput performance of the optimal frame size  adaptation algorithm is compared with a fixed frame aggregation model and a randomized frame aggregation model, where the aggregated frame sizes are randomly distributed between the m i n i m u m (100 B ) and maximum (20 K B ) frame size allowed. F r o m the simulation results shown i n Figure 4.11, we can observe that the adaptive frame aggregation algorithm achieves better throughput performance than the other two algorithms.  4.5  Summary  In this chapter, we conducted a thorough study of the newly proposed A - M S D U and A - M P D U frame aggregation schemes i n 8 0 2 . l l n W L A N s under error-prone channels. T h e effects on system throughput and delay performance with the uni-directional and bi-directional data transfer methods are analyzed by both analytical and simulation methods. Comparison w i t h the simulation results show that the analytical model is accurate i n predicting the network performance. We also proposed a simple and effective adaptive frame size adaptation algorithm for A - M S D U under error-prone channels. Simulation results show that it achieves a higher throughput performance t h a n two other heuristics.  T a b l e 4 . 1 : I E E E 802.11n Simulation Parameters Basic Rate  54 M b p s  D a t a Rate  144.44 M b p s  P L C P Preamble  16 fis  P L C P Header  48 bits  P L C P Rate  6 Mbps  M A C Header  192 bits  P C S (Fra,me Check Sequence)  32 bits  T i m e Slot  9 us  SIFS  16 fis  Sub-frame Header for A - M S D U  14 bytes  Delimiter for A - M P D U  4 bytes  PSDU PHY HDR  MAC HDR  FCS  Subframe 1  Subframe2  Subframe HDR  Subframe N  *••  Padding  MSDU  F i g u r e 4 . 1 : Frame format for A - M S D U .  PSDU PHY HDR  A-MPDU  \ Subframel  Delimiter  Subframe 2  MPDU Header  Subframe N  • * *  MSDU  FCS  Sub-MPDU  F i g u r e 4 . 2 : Frame format for A - M P D U .  Padding  RTS ' ^ EIFS (a) RTS CoKision RTS :>IFS  DATA  EIFS  CTS (b) DATA Frame Corruption BIFS DATA RTS  SIFS  CTS  BACK  (c) Success F i g u r e 4.3: Uni-directional R T S / C T S access scheme.  RTS (a) R T S Collision DATAf  RTS  M  EIFS  •  CTS (b) Forward DATAf Frame Corruption RTS  m  àlFS  DATAf  SIFS  CTS  BACKf  DATAr  (c) Reverse D A T A r Frame Corruption RTS  m  JIFS CTS  DATAf  s|5g  SIFS BACKf  BACKr  DATAr  (d) S u c c e s s  F i g u r e 4.4: Bi-directional R T S / C T S access scheme.  • A O Xi  0  3  V  Q.  BER=0 (Analytical) BER=0 (Simulation) BER=1E-05 (Analytical) BER=1E-05 (Simulation) BER=2E-05 (Analytical) BER=2E-05 (Simulation) BER=5E-05 (Analytical) BER»5E-05 (Simulation) BER»1E-04 (Analytical) BER=1E-04 (Simulation) ^  TÛr  -A-  -A- A -  Oi O  A . A- u  o. o. < .  10  20  y 30  V  V 40  V  V 50  $  $ 4 60  Number of Aggregated MSDUs  ^ 70  o ; ^  i 80  V  •  Figure 4.5: Saturation throughput for A - M S D U .  10^ • 10^  r  A O  10° V  0 V  BER=0 (Analytical) BER=0 (Simulation) BER=1E-05 (Analytical) BER=1E-05 (Simulation) BER=2E-05 (Analytical) BER=2E-05 (Simulation) BER=5E-05 (Analytical) BER=5E-05 (Simulation) BER=1E-04 (Analytical) BER=1E-04 (Simulation)  Q 10"^  10-2  10"  o  o  10  20  30  40  50  60  Number of Aggregated MSDUs  Figure 4.6: Access delay for A - M S D U ,  70  80  F i g u r e 4.7: Saturation througiiput for A - M P D U .  10"  • BER=0 (Analytical) BER=0 (Simulation) •BER=1E-04(AnalyUcal) BER=1E-04 (Simulation) BER=1E-03 (Analytical) BER=1E-03 (Simulation)  o  .o o  .,o.-0"'  510-^ Q  10  10  20  30  40  50  60  Number of Aggregated MPDUs  F i g u r e 4.8: Access delay for A - M P D U .  45 401»-  -n-  -o—  35,  S-30 =J Q.  25  • 0  •&20  2  O  15 10  BER=0 (Analytical) BER=0 (Simulât" on) BER=1E-5 (Analytical) BER=1E-5 (Simulation) BER=1E-4 (Analytical) BER=1E-4 (Simulation)  ^  0  10  15  20  25  30  Number of Stations  F i g u r e 4 . 9 : Saturation throughput under bi-directional data transfer.  Number of Aggregated IVISDUs  F i g u r e 4 . 1 0 : A - M S D U throughput under different number of stations.  O) 3 5 Z3 O ^  302520-  —•— Adaptive Frame Aggregation - o - • Fixed Frame Aggregation (10 KB) • • A - . Fixed Frame Aggregation (20 KB) —V— Randomized Frame Aggregation - o - Fixed Frame Aggregation (1 KB)  -O—T— 10  —r15  20  Number of Stations  F i g u r e 4 . 1 1 : Throughput under different frame aggregation schemes.  Bibliography [1] I E E E 802.11n T G n Sync, " T G n Sync proposal technical specification," M a y 2005.  [2] I E E E 802.11n W W i S E , " W W i S E proposal: High throughput extension to the 802.11 standard," J a n . 2005.  [3] Enhanced Wireless Consortium, " H T M A C specification," J a n . 2006. [4] J . Yeo and A . Agrawala, "Packet error model for the I E E E 802.11 M A C protocol," i n Proc. of IEEE PIMRC,  Beijing, C h i n a , Sept. 2003.  [5] X . J . Dong and P. Varaiya, "Saturation throughput analysis of I E E E 802.11 wireless L A N s for a lossy channel," IEEE  Communications  Letters, vol. 9, no. 2, pp. 100-102, Feb. 2005.  [6] Z. Hadzi-Velkov and B . Spasenovski, "Saturation throughput - delay analysis of I E E E 802.11 D C F i n fading channel," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003. [7] P. Chatzimisios, A . C. Boucouvalas, and V . Vitsas, "Performance analysis of I E E E 802.11 D C F i n presence of transmission errors," i n Proc. of IEEE ICC, Paris, France, June 2004. [8] T . Nadeem and A . Agrawala, " I E E E 802.11 D C F enhancements for noisy environments," in Proc. of IEEE PIMRC,  Barcelona, Spain, Sept. 2004.  [9] G . Bianchi, "Performance analysis of the I E E E 802.11 distributed coordination function," IEEE J. Select. Areas Commun.,  vol. 18, no. 3, pp. 535-547, M a r . 2000.  [10] F . C a l l , M . Conti, and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput hmit," IEEE/ACM Dec. 2000.  Trans. Networking,  vol. 8, no. 6, pp. 785-799,  [U] Y . Tay and K . Chua, " A capacity analysis for the I E E E 802.11 M A C protocol,"  Wireless  Networks, vol. 7, no. 2, pp. 159-171, M a r . 2001.  [12] C. L i u and A . P. Stephens, " A n analytic model for infrastructure W L A N capacity with bidirectional frame aggregation," in Proc. of IEEE  WCNC, New Orleans, L A , M a r . 2005.  [13] J . Y i n , X . Wang, and D . P. Agrawal, " O p t i m a l packet size i n error-prone channel for I E E E 802.11 distributed coordination function," i n Proc. of IEEE  WCNC,  Atlanta, Georgia,  M a r . 2004.  [14] S. C i and H . Sharif, "Improving goodput i n I E E E 802.11 wireless L A N s by using variable size and variable rate ( V S V R ) schemes," Wireless Communications  and Mobile  vol. 5, no. 3, pp. 329-342, M a y 2005.  [15] Ns-2 simulator. [Online]. Available: h t t p : / / w w w . i s i . e d u / n s n a m / n s /  [16] I E E E 802.11n T G n Sync, ' T G n Sync proposal M A C simulation methodology."  Computing,  Chapter 5  Cross-layer Design of MIMO-enabled W L A N s with Network Utility Maximization In recent years, there has been a tremendous growth i n adopting the I E E E 802.11 standards for high-speed wireless local area networks ( W L A N s ) . T h e original 802.11a/b/g standards provide a raw data rate of up to 54 M b p s . T h e recent 802.11e medium access control ( M A C ) protocol [1] provides quality-of-service (QoS) support v i a the H y b r i d Coordination Function ( H C F ) . W i t h i n H C F , it defines the Enhanced Distributed Channel Access ( E D C A ) function and the H C F Controlled Channel Access ( H C C A ) function. E D C A is a contention-based access control scheme by extending the original Distributed Coordination Function ( D C F ) . Due to its simplicity, robustness, and distributed channel access control, E D C A is expected to be widely deployed i n 802.lie-based W L A N s . In E D C A , the traffic is classified into four access categories ( A C s ) , where each A C has different priority for channel access based on its own "^A version of this chapter has been siccepted for publication. Y . L i n and V . W . S . Wong, "Cross-layer Design of MIMO-enabled W L A N s with Network Utility Maximization," in IEEE 2008.  Transactions on Vehicviar Technology,  Arbitration Inter-Prame Space ( A I F S ) , transmission opportunity values, and minimum and maximum contention window ( C W ) sizes. A m o n g these parameters, the minimum contention window size has been shown to have a major impact on the network performance [2]. Various schemes have been proposed to tune the contention window size i n order to improve the M A C efficiency [3]. B y using the multiple-input-multiple-output ( M I M O ) technology at the physical layer [4], the recent 8 0 2 . l l n proposal [5] aims to increase the physical hnk data rate up to 600 Mbps. In a wireless fading channel, two major performance gains can be realized i n a wireless M I M O system: the diversity gain and the spatial multiplexing  gain [6]. T h e spatial diversity gain is  realized when the same information symbols are transmitted across different fading paths, i n which case the transmission rehability can be increased.  O n the other hand, if independent  data symbols are transmitted over each transmit antenna, the spatial multiplexing gain can be achieved, which significantly increases the spectral efficiency. Let 7 denote the average signal-to-noise ratio (SNR) of a wireless link. A wireless M I M O system achieves spatial multiplexing gain r and diversity gain d if the data rate R{'y) and the average error probability Pe(7) have the following asymptotic characteristics in the high S N R regime [7]: l i m ^  = r,  (5.1)  7-»oolog7 and hm 7-»oo  = -d. log  (5.2)  7  For a point-to-point wireless link w i t h MT transmit antennas and MR receive antennas, the maximal diversity gain is MTMR.  The maximal spatial multiplexing gain is m i n { M T , M i î } .  However, it is not possible to realize both maximal diversity gain and maximal spatial multiplexing gain simultaneously. There is a fundamental tradeoff between these two performance gains. For each spatial multiplexing gain r, the best diversity gain d*{r) is the supremum of the diversity gain achieved over all schemes. In a Rayleigh-fading channel w i t h long enough block lengths, the optimal multiplexing-diversity tradeoff d*{r) is given by the piecewise-linear function connecting the points (r, d*(r)), for r = 0 , 1 , . . . , m i n { M x , MR} [7]:  d*{r)  = {MT-r){MR-r).  (5.3)  In this chapter, we assume that a family of carefully designed codes can achieve the above optimal tradeoff performance. A s shown in (5.4), apart from the two working modes where we can obtain a maximal multiplexing gain r while the diversity gain d is zero (or vice versa), there are intermediate working modes where we can achieve part of the diversity gain and multiplexing gain simultaneously.  It is intuitive to consider whether adaptively tuning the M I M O system  gains along the optimal trade-off curve provided by (5.4) is more beneficial than only choosing the points on the two ends of this curve. In this work, we consider how to best utilize this multiplexing-diversity tradeoff i n W L A N s w i t h M I M O channels.  We formulate the cross-layer design as network utility maximization  ( N U M ) problems, where the M A C layer parameters and the multiplexing-diversity tradeoff at the physical layer are jointly optimized.  Two types of M A C protocols are studied i n this  chapter, the carrier sense multiple access w i t h collision avoidance ( C S M A / C A ) M A C , which is used by the 802.11e E D C A , and the slotted A l o h a M A C . For 802.11's C S M A / C A M A C , a centralized scheme is proposed w i t h the access point being the centralized controller. For the slotted A l o h a M A C , distributed algorithms are proposed. The contributions of this chapter are  as follows: 1. For 802.11e W L A N s w i t h M I M O channels, we propose two cross-layer schemes, neimely U-MAC  and D-MAC,  which jointly select the M I M O coding scheme at the physical layer  and the m i n i m u m contention window size at the M A C layer to achieve the maximal network utihty.  2. For the slotted A l o h a based W L A N , we propose a cross-layer design framework  NUM-0  which jointly selects the M I M O coding scheme at the physical layer and the transmission persistent probability at the M A C layer to achieve the m a x i m a l network utility. B y using the dual decomposition method, we then propose a distributed algorithm NUM-D. further propose another algorithm called NUM-S,  We  which is also practical for implementa-  tion.  3. Simulation results are presented to study the effectiveness of the proposed schemes. T h e U-MAC  and D-MAC  schemes are compared with the original 802.11e E D C A protocol  under M I M O channels. B o t h system throughput and delay performance are shown to improve significantly. For the slotted-Aloha M A C , network throughput and rehability performance of the distributed NUM-D  scheme is compared to the NUM-S  scheme.  Table 5.1 and 5.2 hsts the nomenclature used i n this chapter. T h e comparison between our proposed algorithms is shown i n Table 5.3. T h e rest of this chapter is organized as follows. Related work is summarized i n Section 5.1. System models and the cross-layer optimization schemes U-MAC  and D-MAC  for the 802.11e W L A N are presented i n Section 5.2.  5.3 proposes the system model NUM-0 solution NUM-D.  Section  for the slotted A l o h a based W L A N , and its distributed  Simulation results are presented i n Section 5.4. A summary is given i n Section  5.5.  5.1  Related Work  5.1.1  R e l a t e d w o r k o n M I M O systems  T h e traditional network protocol design has been following the layered architecture under the Internet five-layer reference model. Recent development i n wireless networking has found that cross-layer design [8] can be used for performance optimization i n a wireless communication paradigm due to the close coupUng of the characteristics i n the physical layer with the performance i n the higher layers. Some recent work has studied the multiplexing and diversity gains of wireless M I M O systems under different cross-layer frameworks. A M I M O - e n a b l e d M A C protocol was proposed i n [9], where the protocol mitigates interferences by utilizing the multiplexing capability of the M E M O system. Another M I M O - e n a b l e d M A C protocol based on C S M A / C A i n an ad-hoc network was proposed i n [10], where the M A C layer schedules the transmission of different spatial streams by utilizing the spatial multiplexing capability of the M I M O system. T h e impact of the spatial diversity of a M I M O system on the routing hop distance i n an ad-hoc network was investigated i n [11]. T h e M I M O antenna's spatial beamforming capability is utilized i n [12] by the proposed S P A C E - M A C protocol. Some other schemes allow the system to adaptively switch between the two M I M O working modes. T h e adaptive routing protocol i n [13] directs a link to operate under full spatial diversity gain when the distance is long and the signal is weak.  It operates under maximal spatial  multiplexing gain when the distance is short and the signal is strong so as to increase the  throughput. T h e transmission control protocol ( T C P ) over wireless M I M O channel is shown to perform better w i t h a more reliable link provided by the diversity gain of a space-time block coding system at low S N R regions, while a spatial multiplexing scheme outperforms i n the high S N R regions [14]. A U the cross-layer designs summarized above only focus on utilizing one of the two M I M O resources at a time: either fuU diversity or full spatial multiplexing. Some recent schemes investigated the possibihty of achieving a diversity-multiplexing tradeoff.  R e z k i et d. proposed a threshold-based adaptive encoding scheme which achieves the  optimal diversity-multiplexing tradeoff [15]. T h e adaptive encoding scheme switches between several suboptimal encoding schemes with the help of limited channel feedback to the transmitter. L u and K u m a r constructed a space-time block code to achieve any integer point on the multiplexing-diversity tradeoff curve [16]. In [17], Lee et al. studied the optimal tradeoff i n a M I M O ad-hoc network by formulating the rate-rehability tradeoff problem as a network utility maximization problem. However, only one class of traffic is considered, and the M A C uses a reservation-based scheduhng scheme, where the transmission time by each node has to be allocated i n advance.  5.1.2  Related work on network utility maximization  T h e method of network utility maximization ( N U M ) has been shown to be an effective way of tackhng cross-layer optimization problems i n wureless networks [18]. The utihty function for each source node i n a N U M framework is usually chosen such that it reflects the satisfaction attained by the user for the services that it receives. It can also be interpreted as the revenue that the network operator would be able to accrue by providing a certain level of QoS service to the end users.  Solving the optimization problem for maximizing the total network utility can give us optim a l network performance parameters. W h e n the N U M formulation satisfies certain conditions, such as being a separable convex optimization problem, fully distributed algorithms can be obtained, which are highly desirable i n today's distributed networking environment. To formulate the 802.lie-based W L A N w i t h M I M O channels as a N U M problem, we first need to find an appropriate system model. Most of the research work i n this area has focused on the saturation throughput analysis of the 802.11 W L A N , which is the maximum load that the system can carry i n the saturated condition (i.e., the transmission queue of every station is assumed to be always nonempty). T h i s is a fundamental performance figure which indicates the stable limit of the network throughput when the oflFered traffic load increases. Simulation studies [19-22] and experimental testbeds [23] have been constructed to analyze the throughput performance of E D C A . Several analytical models are further proposed. Most of the work extended the D C F Markov chain model proposed by Bianchi [2]. For example, X i a o [24] considered a three-dimensional Markov chain and analyzed the effects of the difi'erent contention window sizes on throughput. K o n g et al. [25] considered the A I F S effects i n a three-dimensional Markov chain model. Robinson et al. [26] used a two-dimensional Markov chain and divided the contention periods into different contention zones to account for the different coUision probabilities during different contention periods.  H u i et al. [27] and Ge et al. [28] extended the  p-persistent D C F models to E D C A . One major obstacle to utilize the above models for N U M formulation is their computa^ tional complexity, which usually involves solving a set of non-linear equations.  To facilitate  practical implementation, it is preferable to use a closed-form expression for the throughput i n the utility optimization problem. A s a result, i n this chapter, we propose two 802.11e E D C A  throughput models based on several simplifying assumptions. These assumptions provide us an E D C A model where the saturation throughput can easily be derived with a closed-form solution. T h i s greatly facilitates the N U M formulation, and improves the convergence speed of the optimization problem. Although the simplifying assumptions may reduce the accuracy of the model, simulation results show the effectiveness of the proposed schemes, and verify that the simplifying assumptions provide a good trade-off to reach manageable optimization solutions. In the next section, we begin by formulating an 802.lie-based W L A N with M E M O channels as a N U M problem and deriving its solutions. T h e following section then studies the slotted Aloha-based M A C , which can be solved by distributed algorithms.  5.2  System Model for 802.11e E D C A M A C  Consider a W L A N w i t h an access point ( A P ) . Let  denote the set of wireless stations. A c -  cording to the E D C A specifications i n the 802.11e standard, there can be up to four different classes of traffic w i t h different QoS requirements. For simplicity, we study the case of two access categories {ACi  and AC2) with AC2 being the higher priority traffic in the network. We use  A / i and A/2 to denote the set of wireless stations i n ACi  and AC2, respectively. E a c h wheless  station transmits one class of traffic, so the set of a l l stations and N to denote the number of stations i n the set. T h u s , Ni =  is N'i\JAf2.  We use Ni, N2,  N2 = \J^2\, and N = \J^\,  where |.| denotes the cardinality of a set. Ni, N2 and N are assumed to be known constants i n the system model. E s t i m a t i o n of the number of competing nodes i n the network has been studied i n [29, 30], and is beyond the scope of this chapter. Extension to four access categories is fairly straightforward based on the optimization framework proposed below.  We study the performance of wireless stations competing for channel access and sending data to the A P . E a c h wireless station has Mr transmit antennas, and the A P has MR receive antennas. There is a fundamental tradeoff between a M I M O system's multiplexing and diversity gains. For each spatiîil multiplexing gain r, the best diversity gain d*{r) is the supremmn of the diversity gain achieved over all schemes. In a Rayleigh-fading channel w i t h long enough block lengths, the optimal multiplexing-diversity tradeoff d*{r) is given b y the piecewise-linear function connecting the points (r, d*{r)), for r = 0 , 1 , . . . , m i n ( M r , MR) [7]:  (5.4)  d*{r) = {MT-r){MR-r), where MT a n d MR are the number of transmit and receive antennas, respectively.  I n this  chapter, we assume that a family of carefully designed codes can achieve the above optimal tradeoff performance. However, this curve is non-differentiable, which may cause difficulties to solve the N U M problem. We use the differentiable approximation as i n [17]:  d{r) = {MT - r){MR -r),  0<r<  m i n ( M T , MR).  (5.5)  T h i s differentiable approximation is a lower boimd of (5.4), which gives a subset of the feasible diversity-multiplexing tradeoff region. A l t h o u g h this can potentially lead to a sub-optimal solution of the problem due to the reduced tradeoff region, as analyzed i n [17], this approximation is close to the exact tradeoff relationship and the reduction of the feasible tradeoff region is small. Thus, the impact on the results should not be signfficant. If a wireless link from the wireless station s G A/" to the A P has the average signal-to-noise ratio 7s, multiplexing gain  and diversity gain dg, then the hnk data rate Cs(7s) (bps) and  error probability pf^ijs)  can be approximated as [31]: Csils) =  (5.6)  kcrslogjt  and (5.7) where kc and kp are positive constants for different coding schemes.  T h e log function uses  base 2 throughout this chapter. T h e multiplexing gain TS and diversity gain ds conform to the optimal tradeoff i n (5.5). T h e n , the link transmission rehabihty ys is: y, = l-fcp77'^('-»)  s e AT.  (5.8)  W i t h Cs being the data rate of wireless station s, the achievable throughput of each station is usually significantly lower than Cg due to the random access and the protocol overhead [2]. To formulate the N U M problem, we need an analytical model for the throughput of each station w i t h respect to Cg and other network parameters, which is a difficult task due to the C S M A / C A based access scheme.  However, the saturation throughput is more tractable and  has been successfully derived from various mathematical niodels. For a single cell 802.11 W L A N , its saturation throughput is a good indicator of network performance because it is the sustainable throughput under heavy traffic load, and is also very close to the m a x i m u m network capacity. In this work, we base om: analysis on the saturation performance of the network. There are two causes of packet loss i n an 802.11 W L A N . One is the packet collision where two nodes transmit simultaneously. T h e other one is channel error, where a packet is received without packet collisions, but is corrupted due to low S N R . In this chapter, we denote the saturation throughput under an ideal channel (i.e., no channel errors) as Xg. T h e n , XsVs can approximately represent the effective throughput after further  discarding the corrupted packets due to channel errors. T h i s approximation separates the effects of packet collision and channel error on the throughput calculation, and greatly faciUtates the problem formulation. The throughput Xs is primarily a function of the physical layer parameters, such as the network basic and data rates, and the M A C layer parameters such as contention window sizes, the D I F S / S I F S / A I F S values, and the frame header overhead. O f all the elements listed above, we focus on studying the effects of the data rate Cs and the m i n i m u m contention window size Ws for station s i n this chapter. T h e data rate w i t h a M I M O channel is given by (5.6), and it is a function of the S N R 7s and the M I M O operation mode Tg. We consider two cases of the assignment of Wg. In the first case, there is a uniform C W value for each A C , where all wireless stations belonging to the same A C use the same minimum contention window value. T h i s is the normal behavior i n 802.11e. We call this M A C as the U n i f o r m - C W M A C or U-MAC.  In the second case, we allow each wireless station to freely  choose its own m i n i m u m contention window size without conforming to the same C W i n its A C . We call this M A C as the Differentiated-CW M A C or  D-MAC.  T i m e is partitioned into virtual time slots where each slot can be either a backoff time slot, a colhsion-free transmission slot, or a collided transmission slot. T h e probability for station s to transmit i n a v i r t u a l time slot can be approximated as follows [32]:  ^^=w~^' where Wg is the m i n i m u m contention window size for station s.  ^^-^^ T h e probability that one  transmitted packet by station s w i l l collide is the probability that any of the other stations also  transmit:  qs = l-  n k€Af, k^s  (5.10)  SEAT.  In tlie following subsections, we describe how to determine the throughput Xs for the two M A C schemes.  5.2.1  S a t u r a t i o n T h r o u g h p u t A n a l y s i s of the U - M A C S c h e m e  For the U-MAC,  TS and QS i n (5.9) and (5.10) are reduced to the same values for each A C , as  we requhre that each A C has a uniform m i n i m u m contention window size, which is Ws = W Q , for wireless station s transmitting ACa traffic. Thus from (5.9), we can use T Q to represent any Ts, s e Ma, for a = 1, 2. To calculate Xs, we extend the mean value based saturation throughput analysis i n [33]. T h e main difference here is that the wireless stations may use different data rates other than the uniform data rate assumed in [33]. T h e average length of one virtual time slot Ta for ACa (where a = 1,2) can be approximated as follows:  To =  :^=r—^  where Thdr, TACK,  — + Thir + TsiFS  + TACK + TAIFS + ,  . Taiot,  a = 1,2,  (5.11)  Tgiot, TSIFS and TAIFS denote the length of the frame header, the A C K  frame, the backoff time slot length, the SIFS and A I F S length, respectively. W Q (for a =  1,2)  represents the m i n i m u m contention window size of ACa- T h i s chapter focuses on studying the effects of contention window size adaptation, and thus the same A I F S is used for each A C . A n identical payload length L is assumed for the network. L/ca is the time to transmit the frame payload of station s. T h e average payload transmission time is the weighted sum of aU ACa stations, using each station's transmission probabihty as the weight.  From [33], we can calculate the rate of success for ACa, which is the average number of collision-free transmissions by ACa per second, as follows:  „  -  ^" -  (1 - qi/2)Ninn  ,0  9a)  rs 12^  + (1 - q2/2)N2T2T2'  T h e aggregated saturation throughput of all stations belonging to ACa is equal to VaL. T h e saturation throughput for station s i n each A C can be calculated as follows:  Xs = VaL  VSGA/;,  a = 1,2.  (5.13)  T h e above equation shows that the individual saturation throughput of each station s i n ACa is the weighted portion of VaL i n proportion to its data rate c^.  5.2.2  S a t u r a t i o n T h r o u g h p u t Ansdysis o f the D - M A C Scheme  For the D-MAC,  we allow each station s to choose its own Ws value individually based on  its link state and class of traffic. In this case, we have an 802.11e W L A N with multiple data rates, and multiple C W values. To model this system accurately is a challenging task. Even for the basic 802.11e M A C w i t h a single data rate, complicated multi-dimensional Markov chain and queueing models have to be used, which result i n complex systems of non-linear equations to solve for the throughput Xs [25]. Although these models give accurate results, they usually require some stringent assumptions, and none can handle a versatile system where each wireless station has a distinct data rate and a distinct C W . However, we may not need a highly accurate throughput model for the N U M framework to work properly. Other factors, such as the convergence speed of the optimization problem and the computation efficiency, are important for a N U M problem. It is preferable to obtain an  approximate closed form expression of a;^ instead of a system of nonlinear equations on a;^ with higher accuracy. W i t h this goal, we propose that the throughput of station s be modeled as:  Xs = TTs{l-qs)^,  a =1,2,  se Ma,  (5.14)  where F is a positive scaling factor. Here, we assume that the two A C s have the same scaling factor. I n Section 5.2.4, we can see that the exact value of F need not be known for solving our N U M problem. B y extending the model from [33] with approximating the uniform contention window size w i t h X^sg/Za ^sl^a,  the average virtual slot length Ta (for a = 1,2) is defined as  follows:  Ta=  v^~^  ~ + Thdr + TSIFS + TACK + TAIFS + ^ / t r ^ " .  l^keMa '^kCs  ^\Tsiot, a = 1.2, (5.15)  -Na{Na + l)  where we use the average contention window size X^seA/k ^s/Ma as an approximation of the identical contention window size modeled i n [33]. Equation (5.14) states that the throughput of wireless station s is i n proportion to its transmission probability T ^ , collision-free probabihty (1 - QS), rate of one payload by each ACa {L/Ta).  and the average transmission  This is a reasonable throughput approximation  as the transmission and coUision probabilities of a station are the major factors influencing its throughput.  T h e linear proportional relationship is a bold assumption.  From our later  simulation results, we can verify that our N U M formulation based on this simple assumption can efficiently achieve the desired traffic differentiation and utihty optimization effects.  5.2,3  Network Utility Formulation  A commonly used family of utility functions is as follows [34]:  Uix)  (1-a)-ia;(i-°),  i f a G (0,1) U ( l , o o ) ,  logx,  i f a = 1,  (5.16)  =<  where a is the fairness parameter. For example, i f x is the throughput of the source node, then Q! —> 0 leads to throughput maximization. Proportional and harmonic mean fairness are achieved when a = 1 and o; = 2, respectively. W h e n o; —> oo, max-min fairness can be achieved. In our N U M framework, we choose the utihty function for each wireless station s w i t h a> 1:  Ua{xs,ys)  = {l-ar\xsysy-'',  a>l,  a = 1,2  (5.17)  where Xgys is the effective throughput of station s after accounting for both packet collisions and channel errors. Ua represents the utility function of ACa for a = 1 and 2. T h e network utihty function is defined as:  U{K,y)  = Yl  + E  i^-P)U2ixj,yj),  a > 1,  (5.18)  where ^ is an adjustable parameter between 0 and 0.5 to tune the weight of ACi and AC2 on the network utility. It can be proven that i7(x,y) is a concave function of x,y.  5.2.4  N U M F r a m e w o r k for C r o s s - l a y e r D e s i g n  W i t h the above system model and definition of the network utihty, we propose our N U M formulation for cross-layer design of a M I M O - e n a b l e d 802.11e W L A N , where each station's M I M O multiplexing gain at the physical layer and the contention window sizes at the M A C layer are jointly optimized.  U-MAC Wireless stations use the m i n i m u m contention window size of Wa i n ACa- The N U M problem can be formulated as follows:  subject to  Q<xs<  VaL^  ya < 2/3 < 1 - A v T r ^ ^ ' ' " ' ' ' ^ ^ ^ ' ' " ' ' ' ^ 0<rs<  min(AfT, MR),  Wa<Wa<Wa,  V s e A/k, a = 1,2 VsGAfa,  a = 1,2  VS€ a = 1,2,  where Va is given by (5.12), and is a function of Wa, rs and other system parameters.  (5.19)  The  parameters ya, Wa and Wa are constant bounds on the variables, and should be selected within reasonable ranges. T h e above problem is a N U M problem w i t h variables x, y , r and Wa-  The  saturation throughput from (5.13) is used as the upperbound for XgAlthough the objective function i n (5.19) is concave, the constraint sets make this problem non-convex and challenging to solve. However, our tests w i t h M a t l a b ' s nonlinear optimization toolbox, using the sequential quadratic programming (SQP) method [35], show that this problem formulation, under reasonable ranges of network parameters and initial variable values, has no difficulty i n converging to a unique solution. Results from Section 5.4 show that the number of iterations needed is i n the range of 20 to 200. Note that due to non-convexity of the problem, the solution can be sub-optimal i n the sense that a local instead of the global optimal solution is determined. W h e n the hnk S N R values drop below certain levels, the problem may no longer have a feasible solution. Analytically deriving the feasible region of the N U M problem is diffi-  cult. However, from an engineering point of view, whenever a feasible solution is unavailable, it means that one or more of the stations w i t h the lowest S N R s wiU not satisfy the m i n i m u m QoS requirements. T w o possible actions can be taken: reducing the QoS demand or disassociating those stations from the network.  D-MAC  W i t h each station s choosing its m i n i m u m contention window size W3 individually, the N U M problem can be formulated as follows:  subject to  0<Xs<  TTS{1 - Qs)^,  V s e A/^,  a =  1,2  -to  VseA/a,  ya<ys<i-kp^7^^^""^^^''"''\ 0<rs<  min(MT,  Ws<Ws<Ws,  MR),  V  S  a =  1,2  e A/"  V s e M,  (5.20)  where Wa and Ws are the lower and upper bounds of the contention window for station s, respectively. T h e variables T ^ , QS, and Ta are given i n (5.9), (5.10) and (5.15). Note that for the constant parameter F , it ends up being a scahng factor r ^ ~ " i n the objective function as defined by (5.18), and has no effect on the optimal solutions, which are the system's m i n i m u m contention window size Wg and the M E M O multiplexing gain r-^. T h e above problem is a N U M problem w i t h variables x, y, r, and Wa- It can also be solved using standard algorithms for constrained nonlinear optimization problems as discussed i n Section 5.2.4. W i t h the above U-MAC  and D-MAC  formulation, the A P i n an 802.11e W L A N can coUect  each wireless station's hnk S N R , select a P w i t h appropriate network revenue models, and  solve either (5.19) or (5.20) to obtain the M I M O multiplexing gain TS and m i n i m u m contention window size Wg for each station. T h e resulting Vg and Wg values can be sent out i n the E D C A parameter set elements of the 802.11e beacon frame for each station to adjust its physical and M A C layer operation parameters.  5.3  System Model for Slotted Aloha M A C  In this section, we consider the slotted A l o h a M A C . T h e N U M formulation can be transformed to a separable convex optimization problem, and a distributed algorithm can be derived accordingly. For the slotted A l o h a , we can obtain the throughput formulation without assuming the saturated conditions. W h e n source node s transmits w i t h persistent probability ps i n slotted A l o h a , its throughput is:  T h e transmission reliability yg is the same as in (5.8). Instead of only differentiating the priority of ACi and AC2 traffic, we now further assume that the higher priority traffic {AC2) is realtime traffic w i t h constant-bit-rate ( C B R ) flows, which has a hard throughput requirement R and reliabiUty demand Q:  R<Xj<x Q < Vj < 1,  = kcrlog'j,  j e A/2, J e ATa,  (5.22)  where x is the constant upper bound on throughput, with r and 7 being the network's maximum multiplexing gain and maximum S N R value, respectively. T h e maximum S N R value can either be deduced from the network channel condition under study or be assigned a high enough value  to put a reasonable upper bound i n the problem formulation. T h e ACi traffic is best-effort traffic, and also has the bounding constraints:  xi <Xi<x,  i G A/i,  yi<2/i<l,  i e M ,  (5.23)  where xi and yi are the constant lower bound on throughput and rehability for best-effort traffic, respectively.  5.3.1  Network Utility Formulation  To differentiate the different QoS requirement of ACi and AC2, we use the utihty function of (5.16) w i t h a > 1, and extend it to include a normalizing denominator.  Thus, the utihty  function for the wireless stations w i t h ACi traffic is as follows:  where the product x^i/i can be interpreted as the effective throughput for the best-effort station i GMFor the C B R traffic i n AC2, the utility function is chosen to be a function of the rehability only, because we expect that the throughput x w i l l satisfy the C B R traffic's throughput demand i î as i n (5.22); however, further increasing a C B R traffic's throughput provisioning usually does not provide additional performance gains:  T h e utihty functions i n (5.24) and (5.25) are normalized such that Ui{xi,yi) = U2{Q) = 0 and Ui{x,l) = f/2(l) = 1- T h i s avoids the apparent problem of combining two utility functions.  which would otherwise have a few magnitude of difference i n value. T h e network utility is the sum of the utihties of all the source nodes:  t / ( x , y ) = J2 ^^ii^i^Vi)  + E  (1 - 0Wyj)'  « > 1  (5-26)  where x, y are vectors for each source's throughput and rehability, /3 is an adjustable parameter between 0 and 1 to tune the weight of ACi and A C a ' s utihties on the network utility function. It can be shown that U{x, y ) is a concave function.  5.3.2  U t i l i t y - O p t i m a l P H Y / M A C Cross-layer  Centralized Scheme:  Design  NUM-O  We now present the centralized N U M formulation for the slotted A l o h a M A C , which is called NUM-O.  Assuming that each wireless station s can adaptively adjust its persistent probability  Ps at the M A C layer w i t h cross-layer information from the M I M O - e n a b l e d physical layer, we  propose the foUowing utihty maximization formulation:  0Ui{xi,yi)  E subject to  + 5]  Xs < kcrs log(7s)Ps  (1 -  J][  0)U2{yj) (1 - Pk),  \/s e Af  k€^J\{s}  < 1-  fcp7r^^''~'''^^^''~'''\  ^1 < a;i < X ,  VsG Vi G M  R<Xj<X,  y i < 2/i < 1,  Vi G M  Q<yj<l,  VjGAAa  0 < r-a < m i n ( M r , M f l ) , 0 <  < 1,  V s G A/" V s G AA.  (5.27)  Problem (5.27) is a non-linear optimization problem w i t h respect to the variables {x, y , r , p } . We can use a change of variables to make the problem separable into sub-problems, and prove that the resulting problem is convex. l o g X s , p ^ = logps and  We perform a log transformation of variables: x's =  = l o g ( l - ps) for s G A/" by taking log on b o t h sides of the first  constraint. T h e N U M problem becomes:  subject to :  x'^ - log kc - log  ys - 1 +  - log(log 7^) - p'^ E Pfc ^ 0fc6Ar\{s}  fcp77(^^-^»)(^«-'-»)  < 0,  V s € A/"  V sG  eP'»+eP"<l,  VseAA  l o g x i < X- < l o g X ,  V Î e A/i  l o g i î < Xj- < l o g x ,  V j e ATa  y i < 2/i <  1,  V i e A/i  Q<2/j<l, 0<rs<A„  VjeA/-2 p;,p';<0,  VseAA  (5.28)  where A , = m i n { m i n { M r , M n } , Ml+M^  _ ^y^}  ,  (5.29)  and  T h e above problem is a convex optimization problem. T h e detailed proof of convexity is included in the A p p e n d i x . Appendices A and B show the proofs for the convexity of the objective function and the constraints, respectively. In order to obtain a convex problem, we introduced an extra constraint on  as shown in (5.29). T h i s constraint can reduce r^'s range of values i n low S N R  conditions. However, this reduction in the range of  is not significant. For example, when  MT = 2, MR = 3, and 7s = 7 d B , the range of TS is reduced from [0,2] i n (5.27) to [0,1.993] i n (5.29). W h e n 7s is higher than 8 d B , there is no longer any difference between the formulations  i n (5.27) and (5.28). A s a result, we can expect that the transformed convex formulation (5.28) would obtain the same optimal solution as before the variable transformation i n most cases. T h e possibihty of obtaining sub-optimal solutions i n some low S N R cases is a trade-off i n order to formulate the problem as a convex optimization problem. In a W L A N where aU the wireless stations communicate w i t h the A P directly, the A P can measure the S N R (7^) of each link and use this information to solve the persistent probabihty Ps at the M A C layer, and the multiplexing gain  at the M I M O physical layer. The resulting  rs and Ps values can be sent to each wireless station v i a piggyback on the control frames. Each station will then tune its operating parameters accordingly.  Furthermore, the A P can  adjust the parameter /3 i n the network utility function to adaptively tune the tradeoff between enhancing the throughput of best-effort traffic and the rehability of real-time flows. The N U M formulation also faces the problem of non-feasibility when some hnk S N R s are too low.  We  may either reduce the QoS demand or disassociating weak stations from the network to reach a feasible solution.  Distributed Scheme T h e NUM-0  NUM-D  problem proposed i n (5.27) is a centrahzed scheme, where the A P acts as the  central controller and distributes the control information to each wireless station. T h i s may suffer from a single-point failure. A n alternative would be a fully distributed algorithm, where each wireless station can decide its own operation parameters based on the locally available information and hmited message exchanges.  Since problem (5.28) is convex, the dual decom-  position approach can be used to obtain the distributed solution. B y relaxing the first two  constraints, the Lagrangian function for problem (5.28) is:  L(x',y,r,p',p",A,Ax)  =  ^(a^Ui) + E  "'^)^2(yj)  I  \  A,  + 5]^ seM  logfcc + logrs + l o g ( l o g 7 s ) + p ; + \  + Yf^s(}-ys-  Pk-^'s kçM\{s}  A:p77(^^-'--)(^«-'-»))  J (5.31)  T h e Lagrange dual function is:  $(A, /x) =  max L (x', y, r , p', p". A, / i ) x',y,r,p',p"  (5.32)  where x', y, r, p', p " axe subject to the third to the ninth constraints of (5.28). T h e dual optimization problem can be formulated as follows:  min$(A,/x),  subject to A ^ 0,  and /x >: 0,  (5.33)  which is optimized over A and / i . Due to the separabihty of variables in (5.31), the problem can be decomposed into two subproblems. T h e maximization of the Lagrangian over x', y, r , p', p " can be conducted i n parallel at the application layer for the target throughput x' and reliabihty y:  max  subject to  2/») + E (1 - /5)^2(yi) - E (>'^< + ^^2/^) jeUi aeAf  Yl ieMi logxi <  < logx,  V i E A/i  logx,  V j G A/i?  log R<x'j< y i < yi < 1,  V i G A/i  Q<yj<l,  VjGATa  which is optimized over x' and y.  (5.34)  A n d , on the M A C / P H Y layers for the transmission probability p and M I M O diversity gain r: max subject to  ^ + eP" < 1,  V s G A/" V S G A T  Vs  0 < r, < A,  G  AT,  (5.35)  which is optimized over p and r . T h e above problem can be separately solved at each wireless station locally. For i G A / i w i t h ACi traffic, it solves the following problem to obtain its target x[ and yi values:  max subject to  PUiix'i,yi)  - (AjX- + /Xij/i)  log x i < X • < log x. Î/1 < yi < 1,  (5.36)  which is optimized over x^ and yi. For station j G A/2 w i t h AC2 traffic, its target Xj and yj values can be calculated from:  max subject to  (1 - P)U2iyj) - (Xjx'j + p.jyj) logR < x'j < l o g x , Q < y i < 1,  which is optimized over x'j and yj.  (5.37)  For station s G A/", the M I M O diversity gain r at the P H Y layer can be calculated from:  max  A , log r , -  subject to  fMskp-y;^^^'^'^'-^''-^'')  0 < rs < A .  (5.38)  FVom (5.35), since EseAf >^s {p's + EksA/\{s} P'k) =  E.eAT (a.P^  +  Efc6Ar\W ^feP^') '  transmission probability p can be solved at each wireless station s by:  max subject to  Xsp's-\- J2  ^kPs  e^'" + ^ ' < 1, Ps,p': < 0.  (5.39)  W i t h the subgradient projection algorithm, Ag and Hs can be updated at each station as follows: / A,(t + 1)  =  fis{t + l)  =  Xsit) - Sit)  \1 + log rs +p's+  Y  Pk +  kc + log log js - x's  [^is{t)-5{t)(l-ys-kp^:^''^-''^^''''-''^)Y,  ,(5.40)  (5.41)  where [a;]"'" = m a x ( x , 0 ) , and ô{t) is the diminishing step size [36] (e.g., ô{t) = 1/(1 + <)). There are many results on convergence of the subgradient method w i t h difference choices of step-sizes [36-39]. For example, for the diminishing step-size rule, the algorithm is guaranteed to converge to the optimal value (assuming bounded subgradients) [39]. B y taking the advantage of the broadcast nature of the wireless transmission, the values of A and p which are required i n each iteration can be piggybacked over a broadcast frame by each station. T h u s , i t introduces limited overhead i n the network.  Another advantage of the distributed solution is that the  computation complexity is reduced compared w i t h the centralized scheme.  T h i s wiU benefit  a mobile node which would save its C P U utilization and battery consumption.  Furthermore,  when the framework is extended into multiple hops, the distributed solution would introduce more substantial performance gains than the central computation. Extension of the single-hop W L A N to multiple hops is under our further study. T h e distributed algorithm (5.36) to (5.41) runs at each wireless station s by calculating its target throughput Xs, reliability requirement ys, M I M O diversity gain r^, and transmission probability pg. The Vg and pg results can then be used to adjust the P H Y / M A C operation parameters.  5.3.3  N U M - S : Utility-Maximization  with Separated P H Y / M A C  Layers  For performance analysis, we propose a simpUfied scheme i n which the persistent probabiUties at the M A C layer and the multiplexing-diversity tradeoff scheme at the physical layer are determined separately.  We call this scheme NUM-S,  and use it as a baseline for performance  comparison i n Section 5.4. A t the M A C layer, it is shown that imder identical traffic and data rate, the network throughput is maximized w i t h each node transmitting w i t h persistent probability [40]:  Ps =  where N =  l/N,  (5.42)  seJ\f,  \Af\. If we choose the persistent probabiUty based on (5.42), then the M I M O  multiplexing-diversity tradeoff at the physical layer for each station becomes independent of each other and can be computed as foUows:  A t the physical layer, the AC2 station j can  calculate its required level of M I M O multiplexing gain for providing the C B R data rate R from (5.21): RN^ fee l o g 7 i ( A r - 1 ) ^ - 1 '  3  e  J^2-  (5.43)  T h e value rj is the m i n i m u m multiplexing gain required for sustaining the data rate R, which leads to the corresponding maximum diversity gain from (5.5) because dj is a strictly decreasing function of rj.  T h i s maximum diversity gain dj i n t u r n provides the maximum reliability yj  available for station j as from (5.8). Because the utility function (5.25) is strictly increasing w i t h yj, this multiplexing-diversity tradeoff maximizes the utility for AC2 stations. For the ACi  stations, maximizing Ui (xy) i n (5.30) is equivalent to maximizing xy because  it is strictly increasing w i t h xy.  We can solve the optimal multiplexing gain  for each AC-y  station i E M\ w i t h the following simple constrained maximization problem: max  subject to  ,  ,  ,  , (TV-1)^-1  fccrilog(7i)^^  x i < A;crtlog(7i)  (N  (l-K^-'^'-'^), 1)^-1  -  < x,  y i < 1 - fcp7r'^^''*^ < 1. din)  = (MT  - ri){MR  -  n),  0 < Ti < m i n ( M T , MR).  (5.44)  T h e solution of problem (5.44) provides each AC\ station w i t h its M I M O multiplexing gain ri, and the transmission reliabihty j/j can be subsequently calculated from (5.8). W i t h the reliability results from AC2 stations, we can obtain the network utility from (5.28) to compare w i t h the NUM-D  scheme.  This scheme divides the network utility maximization problem into two steps. T h e persistent probabihties are first determined at the M A C layer, and the best M I M O scheme at the physical layer is solved using a simple constrained maximization problem.  However, this scheme may  not achieve the best possible network utility because it does not consider adapting the M A C layer parameters to the physical layer schemes.  5.4 5.4.1  Performance Evaluation R e s u l t s for 802.11e E D C A  We carry out network simulations by using the ns-2 [41] simulator to study the effectiveness of the cross-layer optimization framework proposed i n this chapter. T h e simulation parameters are shown i n Table 5.4. We consider a W L A N w i t h 10 wireless stations. Five of them have ACi trafSc, and five of them have AC2 traffic. To effectively study the traffic differentiation effects on our proposed schemes, we use the same S N R values for each pair of ACi and AC2 stations. T h a t is 7t = 71+5 (for i = 1,... ,5). E a c h 7i is a Gaussian distributed random variable with a mean value of 7^ = 10 d B , and a variance of 7t, = 5. To avoid obtaining a too low S N R from the Gaussian random number generator, which will likely lead to no feasible solution for the optimization problem, we set a lower S N R bound of 3 d B . T h i s setup tries to simulate a W L A N w i t h wireless stations randomly located within certain distances from the A P . Other assumptions such as uniformly distributed S N R s have also been tested, and do not seem to have a major impact on the performance comparisons. In fact, the U-MAC  and D-MAC  models do  not make any assumptions on the S N R ' s distributions. A n d our tests also show that similar performance trends are observed under differently simulated S N R s . Thus, only results from the Gaussian distributed S N R s are presented. For U-MAC M r = 2,  MR  and D-MAC, =  3, Ws =Wa  the following parameters are used: kc = 20 M H z , kp = 0.15, = 7, Ws = Wa = 1023, a = 1.1, yi = 0.7,  y2 =  0.85, and  r = 1. W i t h a m a x i m u m of five retransmissions, the m a x i m u m contention window size is set to be 2^ = 32 times the m i n i m u m contention window size. T h e resulting M I M O multiplexing gain r and contention window size CW  from the solution of (5.19) or (5.20) are used in the  ns-2 simulator to assign the proper physical and M A C operating parameters.  We vary the  utility parameter 0 from 0.1 to 0.5 to study the effectiveness of the traffic diflFerentiation effect of our proposed schemes. Smaller /3 improves the higher priority A C a ' s performance, but at a price of decreasing performance of ACi.  A desired tradeoff may be obtained by assigning the  appropriate /? by the network administrator. We compare the proposed adaptive cross-layer schemes U-MAC  and D-MAC  with the  original 802.11e M A C . We look at the following three main performance metrics: the traffic's throughput, delay and the network's utihty. T h e throughput is calculated as the end-to-end network throughput above the M A C layer, which is the number of bits transmitted i n the transport layer protocol data unit ( P D U ) divided by time.  For the original 802.11e M A C ,  the Wi and W2 are chosen as 7 and 31, respectively, according to the standard specifications. In order to have a meaningful performance comparison, we also use M I M O links with the 802.11e M A C . T h e multiplexing gain Vs of wireless station s is chosen without the cross-layer optimization as done i n the U-MAC  and D-MAC  schemes. Its rg is chosen by (5.8) such that  wireless station s would achieve a Hnk rehability of 0.9 w i t h its channel S N R 7^. We will study the effectiveness of the tuning 0 on the traffic QoS differentiation. T h e network total utihty is used to evaluate the effectiveness of the schemes i n achieving better utility values, which corresponds to a higher network revenue and better user QoS satisfactions. Figure 5.1(a) shows the aggregated throughput of each A C . Because of the static nature of the 802.11e M A C scheme, its performance values do not change w i t h /3, and are drawn as a horizontal line i n the figure to be used as a performance comparison basehne. T h e medium access delay is shown i n Figiure 5.1(b). A s we would expect, an increase i n P decreases the priority differentiation between the two A C s . W h e n /? reaches 0.5, ACi  and AC2 reach equal  priority and liave comparable performances. T h e network utility is shown i n Figure 5.2. Although the 8 0 2 . l i e M A C does not consider /?, its Xg, ys values are also substituted into (5.18) to calculate the network utility under different p. Figure 5.2 shows that the U-MAC  and D-MAC  maintain a relatively high network utihty,  while the 802.11e is not adaptive to different P adjustments and its network utility decreases sharply when the utihty function demands less traffic differentiation by increasing the P value. F r o m the simulation results, we can observe that the adaptive U-MAC and D-MAC  schemes  have good flexibility i n adapting to the network's different assignment of weights to the two access categories.  They also consistently outperform the original 802.11e M A C i n every per-  formance measure because they jointly adapt the m i n i m u m contention window size values and the M I M O coding schemes.  These results verify that those simplifying assumptions that we  made to formulate the computationally efficient N U M problem i n Section 5.2 are reasonable and sound. We can also observe that the U-MAC MAC  slightly outperforms the D-MAC,  even though D-  allows the extra flexibility of letting each station have its own Ws parameter.  The  cause for this is from the coarse approximation we made i n the throughput model for DMAC, while the U-MAC  model is more accurate. However, an insight that we can gain from  these simulation experiments is that restricting each access category to have uniform m i n i m u m contention window sizes may be suflBicient to provide good performance gain i n the M I M O enabled cross layer design framework. We may be able to improve the performance of  D-MAC  by further reflning its throughput model. To have a better understanding of the system behavior near the optimal values, we present a set of results of the system variables from the N U M framework i n Tables 5.5 and 5.6. Ten  wireless stations axe also used i n the tests. T h e Unk S N R values 7 i = 7^+5 (for i = 1 , . . . ,5) axe set at increasing values (from 6 d B to 10 d B ) instead of random numbers so that it is easier to observe the behavior of the system variables. f3 is increased from 0.1 to 0.5. Prom the tables, we can see that the difference of the diversity gain and contention window size of the two AC'S stations diminishes when 0 approaches 0.5. In previous simulation tests, the slightly under-performs U-MAC. Prom these two tables, we can see that the D-MAC  D-MAC tends to  use a smaller contention window size t h a n the U-MAC model, which is likely the cause for the performance loss. A more accurate throughput model for D-MAC  w i l l be needed for improving  this performance gap.  5.4.2  R e s u l t s for S l o t t e d A l o h a M A C  T h e slotted A l o h a schemes NUM-D  and NUM-S  axe studied w i t h numerical tests i n M a t l a b .  T h e following parameters are used: x = 0.01 Mbps,  7 = 30 dB, Q = 0.85, and the other  parameters use the same values as i n Section 5.4.1. T h e stopping criteria for NUM-D  is that  \\s{t + 1) - Aa(f)| and \fj.s{t + 1) - Ms(<)| are less than 10"^ for aU s.  EflFect of /? on the Network U t i l i t y Function First, we examine the effectiveness of the network utUity function (5.26) i n determining the tradeoff between the throughput of ACi and the reliabiUty of AC2. We vary the parameter P from 0.6 to 1 w i t h a step size of 0.05, and solve problem (5.28). We also use the Gaussian distributed random variable w i t h a mean value of 7^ and a variance of 7^ to generate the S N R values i n simulations. T h e results for ATi = ATa = 5, 7m = 8 dB,  = 0.57m, and  varying R axe shown i n Figure 5.3. T h e throughput is calculated from (5.21) which is the  throughput for transmitting the M A C layer protocol data unit ( P D U ) (including M A C frame headers). We can see that for a smaller P, the throughput i n ACi is given lower priority, but the network achieves higher rehability for the AC2 traffic. A s P increases, the throughput i n ACi significantly increases at the price of decreasing reliability on AC2 traffic. T h e Eirea below each curve is effectively the achievable throughput-rehabihty region for a specified R. W h e n R increases, this region shrinks because more resources have to be allocated to guarantee the higher throughput requhrement from the AC2 traific. Figure 5.3 shows that the utihty function (5.26) has great fiexibihty i n adapting different user QoS requirements by adjusting the parameter p. If the network operators can generate higher revenues by providing high rehabihty for AC2 traffic, they may tend to choose a smaller P value. In the following tests, we choose P = 0.85.  Performance under Different N u m b e r of Stations In this experiment, 7^ is fixed at 8 d B , and 7^ = 0.57,„. We vary the number of stations i n each A C from 1 to 5. R is set at 1.5 M b p s . T h e resulting network utihty, the throughput ACi  and rehabihty performance i n AC2 are shown i n Figures 5.4 to 5.6. W h e n the number  of stations is small, the NUM-D  scheme achieves much higher ACi throughput than  NUM-S.  W h e n the number of stations increases, the performance gain on ACi's throughput by  NUM-D  diminishes.  B u t NUM-D  is able to maintain the AC2's  rehabihty above 95%, while NUM-  iS"s rehabihty performance significantly deteriorates. Overall, the network utihty achieved by NUM-D  is consistently higher than  NUM-S.  Performance under Different S N R s In this experiment, Ni and N2 axe set to 5. T h e networit average 7^ varies from 6 d B to 16 d B , 7u = 0.57m. R is equal to 1.0 M b p s . Figures 5.7 to 5.9 show the network utility,  ACis  throughput and A C a ' s reliability achieved w i t h these two schemes. Results show that i n the lower S N R region, NUM-D  sacrifices a portion of A C i ' s throughput to achieve consistently  high reliabihty for AC2, while at the higher S N R region, NUM-D throughput than NUM-S  achieves significantly higher  and also maintains A C a ' s rehability greater than 99%. A s a result,  it successfully achieves a good balance between throughput for best-effort traffic and rehabiHty for real-time traffic and attains higher network utihty than the NUM-S  scheme.  To study the detailed system variable behavior at the optimal solution, we also present a set of results w i t h pre-determined S N R values i n Table 5.7. We can see that the solutions provide the required 1 M b p s throughput for the AC2 traffic w i t h good reliability. T h e best-effort  ACi  traffic tends to use higher a multiplexing gain rs to achieve a higher data rate. T h e stations w i t h higher S N R links can use a higher multiplexing gain and lower transmission probabihty to achieve the required Hnk rehability and throughput. T h e above results show that the cross-layer network utihty maximization formulation of (5.27) successfully balances between the QoS requirements of the two access categories by jointly adapting M A C and M I M O physical layer parameters.  5.5  Summary  T h i s chapter proposed a M A C / P H Y cross-layer design w i t h network utility maximization i n a W L A N w i t h multiple classes of traffic. T w o types of M A C protocol are considered.  For  the C S M A / C A - b a s e d 802.11e E D C A M A C , the m i n i m u m contention window size at the M A C layer is jointly optimized w i t h the multiplexing-diversity gain tradeoff at the physical layer w i t h M I M O antennas. T h e utility-based cross-layer design is shown to be flexible i n adjusting the system performance i n regard to QoS tradeoff for different access categories of traffic. We further analyzed the slotted A l o h a M A C using the N U M approach as weU, and were able to derive distributed solutions w i t h variable transformation and dual decomposition of the original N U M problem. Simulation results are presented for both M A C designs, which show the effectiveness i n system performance improvement.  5.6  Proof of the convexity for problem (5.28)  5.6.1  P r o o f of the concavity of the utility function  For a > 1, we define the constants C i and C2 as foUows:  1  C2 =  1 -  It is easy to see that C i < 0 and C2 < 0, because  is a strictly decreasing function of t  for a > 1. A s a result, C22/^~" is a concave function of y for a > 1. Thus, 1/2(2/) is a concave function. For U{{x',y), the Hessian m a t r i x of C\{e'''y)^ " is:  H  =  =  V^Ciie-'yf  Cie  ( l - a ) V - "  (1 - a)2y-"  ( 1 - « ) V "  -a{\ -  a)y-°'-'^  (5.45)  For any non-zero vector z = [zi Z2] and a > 1, we have: zHz^  =  C i ( l - a)e(i-")^'y-"-i  <  0  [(1 - a){yzi + z^f  - zl] (5.46)  which shows that H is negative definite. A s a result, the utility function U{{x',y) is a concave function of {x', y}.  5.6.2  Please note that we require a > 1 for the above concavity proof.  •  P r o o f of convexity of the constraints  For a convex optimization problem, its equahty constraints should be affine, and the function / ( x ) i n the inequality constraint f{x)  < 0 should be convex.  It is easy to see that the first constraint i n (5.28) is affine. For the second constraint, i n order for the function w{rs) = -y~(^r~''')(^«~'"") to be convex, it is required that: w{rs)  =  ^-(^r-r,)iMR-rs)  >  0.  ^(^^  + MR  -  2rsf  hi7,  -  2]  In7,  (5.47)  T h i s gives an upper bound of r^, which is refiected i n (5.29). T h e t h i r d constraint is relaxed from the equality constraint (e^» -|- e^' = 1) to an inequality constraint. T h e main concern is that a non-linear equahty constraint makes the problem nonconvex. W i t h this relaxation to inequality constraint, the problem becomes convex. Intuitively, this relaxation is reasonable. Suppose that e^''+e^'' is strictly less than 1, we can increase p'^ or p " to reach the upper limit 1. A n increase i n p'g or p " w i l l lead to relaxing the first constraint, which i n t u r n may lead to higher x'^, resulting i n better network utility. A s a result, we may expect that this upper bound of 1 is always tight. Thus, problem (5.28) is a convex optimization problem over variables { x ' , y , r , p ' , p " } .  •  T a b l e 5.1: List of Nomenclature - P a r t I Notation  Parameter Definition  a  U t i l i t y function parameter  P  Weight trade-off between two access categories  Is  Average signal-to-noise ratio of station s  Xs  Lagrange multiphers for the rate constraints Lagrange multiphers for the delay constraints  Ts  Transmission probabihty of station s i n C S M A / C A  Cs  L i n k data rate of station s  ds  M I M O diversity gain for station s  K  M I M O spatial multiplexing throughput parameter M I M O error probability parameter  L  Packet payload length of 802.11e  MT  Number of transmit antennas at wireless stations  MR  Number of receive antennas at A P Set of all mobile stations  M M ,  M  N Ni,N2  Set of mobile stations i n ACi and AC2, respectively Total number of mobile stations Total number of mobile stations i n ACi and AC2, respectively  Ps  Transmission probabihty i n slotted A l o h a for station s  Qs  Collision probability of a transmitted frame by station s i n C S M A / C A  T a b l e 5.2: List of Nomenclature - Part II Notation  Parameter Definition  Q  Reliability requirement for AC2 C B R traffic  R  Throughput requirement for AC2 C B R traffic M I M O spatial multiplexing gain  S  Wireless station number firom 1 to iV  Ta  Average length of a virtual time slot i n ACa (0 = 1,2)  Va  Average number of collision-free transmissions from ACa per second  Wa Wa,Wa Ws Ws,Ws Xs  X  M i n i m u m contention window size for ACa Lower and upper bounds of Wa, respectively M i n i m u m contention window size of station s Lower and upper bounds of Ws for station s, respectively Throughput of station s Throughput upper bound i n slotted A l o h a  Xl  Lower bound of A C i ' s throughput i n slotted A l o h a  Vs  L i n k reliabihty of station s  Va  L i n k reliabihty lower bound of ACa (û = 1> 2)  T a b l e 5.3: Comparison between Proposed Schemes Scheme  Operation  MAC  Input Parameters  Variables  Output  Comments  Solutions U-MAC  Centralized  CSMA/CA  MT,  MR, a, /3, N, L  y , r, Wa  X ,  kc, kp, 7, Thdr, TACK Tsiot, TSIFS, D-MAC  Centralized  CSMA/CA  MT,  y , r, Ws  X ,  Centralized  Slotted A l o h a  MT,  Distributed  Slotted A l o h a  MT,  MR, a, P, M  MR, a, P, M  kc, kp, 7) P NUM-S  Distributed  Slotted A l o h a  MT,  for each AC.  PHY: r  DiJHferentiated C W for each station.  TAIFS  PHY: r  Centrahzed N U M  MAC: p  formulation.  x', y, r  PHY: r  Distributed solution  P', P " , A, n  MAC: p  for  PHY: r  Simplified scheme as  MAC: p  performance baseline.  X ,  y , r, p  kc, kp, 7) P NUM-D  M A C : Wa  M A C : Ws  kc, kp, 7 , Thdr, TACK  NUM-0  Uniform C W  TAIFS  MR, a, p, M, L  Tsiot, TSIFS,  PHY: r  MR, a, P, M  kc, kp, 7 , R  X ,  y , r, p  NUM-0.  T a b l e 5.4: I E E E 802.11n Simulation Parameters Basic Rate  10 M b p s  M a x i m u m D a t a Rate  80 M b p s  DSSS P L C P Preamble and Header  192 bits  M A C Header  192 bits  P C S (Frame Check Sequence)  32 bits  A C K Frame Size (include Headers)  304 bits  D a t a Packet Size  1000 bytes  T i m e Slot  9 fj.s  SIFS  10 fj,s  AIFS  28 (XS  M a x i m u m Number of Retransmissions  5  T a b l e 5.5:  N U M Solution for the U - M A C Scheme.  ACi Station s  AC2  1  2  3  4  5  6  7  8  9  10  6 dB  7dB  8dB  9dB  10 d B  6 dB  7dB  8 dB  9dB  10 d B  P  7s  0.1  Ws  220  29  0.2  Ws  120  33  0.3  Ws  84  38  0.4  Ws  65  45  0.5  Ws  53  53  0.1  rs  1.552  1.522  1.496  1.470  1.442  1.549  1.528  1.502  1.476  1.449  0.2  rs  1.554  1.524  1.497  1.471  1.444  1.549  1.528  1.501  1.475  1.449  0.3  rs  1.555  1.525  1.498  1.472  1.445  1.549  1.528  1.501  1.475  1.448  0.4  Ts  1.556  1.526  1.499  1.473  1.446  1.549  1.527  1.500  1.474  1.447  0.5  rs  1.557  1.527  1.500  1.474  1.447  1.549  1.526  1.500  1.474  1.447  T a b l e 5.6:  N U M Solution for the D - M A C Scheme.  ACi Station s  AC2  1  2  3  4  5  6  7  8  9  10  Is  6dB  7dB  8dB  9dB  10 d B  6dB  7dB  8dB  9dB  10 d B  0.1  Ws  36  33  31  29  27  7  7  7  7  7  0.2  Ws  23  22  20  19  18  7  7  7  7  7  0.3  Ws  17  16  15  14  13  8  8  7  7  7  0.4  Ws  14  13  12  11  10  10  9  8  8  7  0.5  Ws  11  10  10  9  9  11  10  10  9  9  0.1  rs  1.632  1.631  1.632  1.636  1.640  1.539  1.528  1.523  1.521  1.522  0.2  Ts  1.562  1.569  1.576  1.583  1.591  1.538  1.540  1.533  1.531  1.531  0.3  Ta  1.538  1.546  1.554  1.563  1.571  1.528  1.536  1.545  1.547  1.546  0.4  rs  1.530  1.539  1.548  1.557  1.565  1.526  1.535  1.544  1.553  1.561  0.5  Ta  1.528  1.537  1.546  1.554  1.563  1.528  1.537  1.546  1.554  1.563  T a b l e 5.7: Solution for the N U M - D Scheme. ACx Station s  1  2  3  4  5  6  7  8  9  10  Is  6dB  7dB  8 dB  9 dB  10 d B  6 dB  7dB  8dB  9 dB  10 d B  Ps  0.090  0.089  0.089  0.088  0.087  0.138  0.122  0.109  0.099  0.090  Ts  1.562  1.575  1.587  1.599  1.610  1.124  1.149  1.173  1.195  1.216  Xs (Mbps)  0.864  0.969  1.074  1.179  1.283  1.000  1.000  1.000  1.000  1.000  Vs  0.843  0.857  0.869  0.879  0.888  0.973  0.980  0.982  0.986  0.989  Xs  0.085  0.085  0.084  0.083  0.082  0.130  0.115  0.103  0.093  0.085  IJ-s  0.102  0.099  0.097  0.094  0.092  0.943  0.937  0.934  0.930  0.927  P (a) Average throughput performance between U - M A C , D - M A C , and 802.11e.  2.0-  (b) Average delay performance between U - M A C , D - M A C , and 802.11e.  F i g u r e 5.1: Performance of U - M A C and D - M A C versus /3.  -I  I-  -46-  11  p  1  -47^  1  11  • •  -48-  -  1 0  -50-  - • - U-MAC  Z  --A--D-MAC  •  ••-802.11  -51-52-  '  1  0.1  1  •  0.2  1  0.4  0.3  0.5  p  F i g u r e 5.2: Network utility of U - M A C and D - M A C versus 0.  0.84-J  1 1.0  .  1 1.5  ,  1 2.0  ,  1 2.5  Average Throughput for A C , (Mbps)  F i g u r e 5.3: T h e tradeoff between throughput and rehabihty for slotted A l o h a .  3.0  Number of Wireless Stations in Each AC  F i g u r e 5.4: Slotted A l o h a - Network utility versus the number of wireless stations.  Number of Wireless Stations in Each AC F i g u r e 5.5: Slotted A l o h a - Average throughput for best-effort traffic w i t h different number of wireless stations.  in  —r-  1.0-1  1 CO < 0.8-1 0.7a> 0.6-  -•-NUM-D - ••- NUM-S  2 ^  0.5-T  1  •  1  2  V •  1  3  "  1  -  '  4  !  Number of Wireless Stations in Each AC F i g u r e 5.6: Slotted A l o h a - Average rehability for real-time traffic w i t h different number of wireless stations.  7. (dB)  F i g u r e 5.8: Slotted A l o h a - Average throughput for best-effort traiBc w i t h different S N R .  6  '  T  1  1  1  1  1  1  '  T  8  '  10  '  12  '  14  '  ?6  7. (dB)  F i g u r e 5.9: Slotted A l o h a - Average rehability for real-time traffic w i t h different S N R .  Bibliography [1] I E E E 802.11e W G , "Wireless L A N M A C and P H Y specifications amendment 8: M A C quality of service enhancements," Sept. 2005.  [2] G . Bianchi, "Performance analysis of the I E E E 802.11 distributed coordination function," IEEE  J. Select. Areas Commun.,  vol. 18, no. 3, pp. 535-547, M a r . 2000.  [3] F . C a h , M . C o n t i , and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput limit," IEEE/ACM  Trans. Networking,  vol. 8, no. 6, pp. 785-799,  Dec. 2000.  [4] A . J . P a u l r a j , D . A . Gore, R . U . Nabar, and H . Bolcskei, " A n overview of M I M O communications - a key to Gigabit wireless," Proc. of the IEEE, vol. 92, no. 2, pp. 198-218, Feb. 2004.  [5] I E E E 8 0 2 . l l n W G , " I E E E 8 0 2 . l l n Draft 4.0," M a y 2008.  [6] D . Tse and P. Viswanath, Fundamentals  of Wireless Communication.  Cambridge Univer-  sity Press, 2005.  [7] L . Zheng and D . N . C . Tse, "Diversity and multiplexing: A fundamental tradeoff i n multiple-antenna channels," IEEE  Trans. Inform.  Theory, vol. 49, no. 5, pp. 1073-1096,  M a y 2003.  [8] X . L i n , N . Shroff, and R . Srikant, " A tutorial on cross-layer optimization i n whreless networks," IEEE  J. Select. Areas Commun., vol. 24, no. 8, pp. 1452-1463, A u g . 2006.  [9] M . Paxk, S. C h o i , and S. M . Nettles, "Cross-layer M A C design for wireless networks using M E M O , " i n Proc. of IEEE  Globecom, St. Louis, M O , Nov. 2005.  [10] K . Sundaresan, R . Sivakumar, M . A . Ingram, and T . Chang, " M e d i u m access control i n ad hoc networks w i t h M I M O links: optimization considerations and algorithms," Trans. Mobile  IEEE  Comput, vol. 3, no. 4, pp. 350-365, Oct.-Dec. 2004.  [11] M . H u and J . Zhang, " M I M O medium access control and routing i n ad hoc networks: a holistic perspective," i n Proc. of IEEE  Workshop on High Performance  Switching  and  Routing, Hong K o n g , C h i n a , M a y 2005.  .  [12] J . - S . P a r k , A . N a n d a n , M . Gerla, and H . Lee, " S P A C E - M A C : E n a b l i n g spatial reuse using M I M O channel-aware M A C , " i n Proc. of IEEE ICC, Seoul, Korea, M a y 2005.  [13] K . Sundaresan and R . Sivakumar, "Routing i n ad-hoc networks w i t h M I M O links," i n Proc. of IEEE Int'l Conf on Network Protocols, Boston, M A , Nov. 2005.  [14] A . L . Toledo and X . Wang, " T C P performance over wireless M I M O channels w i t h A R Q and packet combining," IEEE  Trans. Mobile  Comput,  vol. 5, no. 3, pp. 208-223, M a r .  2006.  [15] Z. Rezki, D . Haccoun, and P . Gagnon, " A threshold-based adaptive encoding for achieving the diversity-multiplexing tradeoff," i n Proc. of IEEE Communication  Intl Symposium  on  Wireless  Systems, Siena, Italy, Sept. 2005.  [16] H . - F . L u and P. K u m a r , " A unified construction of space-time codes w i t h optimal ratediversity tradeoff," IEEE  Trans. Inform.  Theory, vol. 51, no. 5, pp. 1709-1730, M a y 2005.  [17] J . Lee, M . Chiang, and A . R. Calderbank, "Price-based distributed algorithms for raterehability tradeoff i n network utihty maximization," IEEE  J. Select. Areas  Commun.,  vol. 24, no. 5, pp. 962-976, M a y 2006.  [18] M . Chiang, S. H . Low, A . R . Calderbank, and J . C. Doyle, "Layering as optimization decomposition: A mathematical theory of network architectures," Proc. of the IEEE, vol. 95, no. 1, pp. 255-312, J a n . 2007.  [19] A . Lindgren, A . Almquist, and O. Schelen, "Quahty of service schemes for I E E E 802.11 wireless L A N s : an evaluation," Mobile Networks and Applications,  vol. 8, no. 3, pp. 2 2 3 -  235, June 2003.  [20] S. C h o i , J . D . Prado, S. Shankar, and S. Mangold, " I E E E 802.11e contention-based channel access ( E D C F ) performance evaluation," in Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [21] D . He and C. Q. Shen, "Simulation study of I E E E 802.11e E D C F , " i n Proc. of IEEE  VTC,  Jeju, K or ea , A p r . 2003. [22] Q. N i , "Performance analysis and enhancements for I E E E 802.11e whreless networks,"  IEEE  Network, vol. 19, no. 4, pp. 21-27, J u l y / A u g . 2005. [23] A . Banchs, A . Azcorra, C. Garcia, and R. Cuevas, "Apphcations and challenges of the 802.11e E D C A mechanism:  A n experimental study," IEEE Network, vol. 19, no. 4, pp.  52-58, J u l y / A u g . 2005. [24] Y . X i a o , "Performance analysis of I E E E 802.11e E D C F under saturation condition," i n Proc. of IEEE ICC, Paris, France, June 2004.  [25] Z. K o n g , D . H . K . Tsang, and B . Bensaou, "Performance analysis of I E E E contention-based channel access," IEEE  J. Select. Areas Commun.,  802.11e  vol. 22, no. 10, pp.  2095-2106, Dec. 2004.  [26] J . W . Robinson and T . S. Randhawa, "Saturation throughput analysis of I E E E 802.11e enhanced distributed coordination function," IEEE  J. Select. Areas Commun.,  vol. 22,  no. 5, pp. 917-928, June 2004.  [27] J . H u i and M . Devetsikiotis, "Performance analysis of I E E E 802.11e E D C A by a unified model," i n Proc. of IEEE  Globecom, Dallas, Texas, Nov. 2004.  [28] Y . Ge and J . H o u , " A n analytical model for service differentiation i n I E E E 802.11," i n Proc. of IEEE ICC, Anchorage, Alaska, M a y 2003.  [29] A . L . Toledo, T . Vercauteren, and X . Wang, "Adaptive optimization of I E E E 802.11 D C F based on Bayesian estimation of the number of competing terminals," IEEE Comput,  Trans. Mobile  vol. 5, no. 9, pp. 1283-1296, Sept. 2006.  [30] G . Bianchi and I. Tinnirello, " K a l m a n filter estimation of the number of competing terminals i n an I E E E 802.11 network," i n Proc. of IEEE INFOCOM,  San Francisco, C A , M a r .  • 2003.  [31] D . Gesbert, M . Shafi, D . Shiu, P. J . Smith, and A . Naguib, "From theory to practice: an overview of M I M O space-time coded wireless systems," IEEE vol. 21, no. 3, pp. 281-302, A p r . 2003.  J. Select Areas  Commun.,  [32] G . Bianchi, L . Pratta, and M . Oliveri, "Performance evaluation and enhancement of the C S M A / C A M A C protocol for 802.11 wireless L A N s , " i n Proc. of IEEE PIMRC,  Taipei,  Taiwan, Oct. 1996.  [33] Y . L i n and V . Wong, "Saturation throughput of I E E E 802.11e E D C A based on mean value analysis," i n Proc. of IEEE  WCNC, Las Vegas, Nevada, A p r . 2006.  [34] J . M o and J . Walrand, "Fair end-to-end window-based congestion control,"  IEEE/ACM  Trans. Networking, vol. 8, no. 5, Oct. 2000.  [35] A . R . C o n n , N . I. M . G o u l d , and P. L . Toint, Trust-region Methods.  Society for Industrial  Mathematics, 2000.  [36] D . P. Bertsekas, Nonlinear Programming, 2nd ed.  A t h e n a Scientific, 2004.  [37] D . P. Palomar and M . Chiang, " A tutorial on decomposition methods for network utihty maximization," IEEE J. Select. Areas Commun., vol. 24, no. 8, pp. 1439-1451, A u g . 2006.  [38] N . Z. Shor, Minimization  methods for non-differentiable  [39] D . P. Bertsekas, Convex Analysis and Optimization.  [40] D . Bertsekas and R . Gallager, Data networks, 2nd ed.  functions.  Springer, 1985.  A t h e n a Scientific, 2003.  Prentice H a l l , 1992.  [41] Ns-2 simulator. [Online]. Available: h t t p : / / w w w . i s i . e d u / n s n a m / n s /  .  Chapter 6  Cooperative M A C and Routing Protocols Design for Wireless Ad-hoc Networks ^ Due to the impairments i n the wireless channels, signal transmission through the wireless propagation medium presents various challenging problems. One of them is channel fading, which comes from the constructive and destructive interference of the multiple signal copies between the transmitter and receiver. It can cause a wide variation i n received signal's amplitude and phase over a small spatial or time interval, which degrades the signal detection performance significantly.  One main cause for the poor performance of some traditional modulation and  coding schemes over a fading channel is that the traditional radio transmission technique only utilizes the single transmitter-to-receiver signal path. Once this signal path goes into a deep fade, any strong communication scheme may suffer from a transmission failure. A n effective way to improve the wireless communication performance over a fading channel is version of this chapter has been accepted for publication. Y . L i n , J . Song, and V . W . S . Wong, "Cooperative M A C and Routing Protocols Design for Wireless Ad-hoc Networks," Applications  Journal, 2008  in ACM/Springer  Mobile Networks and  the diversity technique. Instead of obtaining a single copy of the signal, the information symbols pass through multiple independent fading paths. Reliable communication is possible when at least one of these paths does not encounter a deep fade.  T h e probability of a transmission  failure, which occurs when aU the independent signal paths fade simultaneously, is thus greatly reduced. W i t h an increasing demand on the wireless communication systems, multiple antennas are becoming more prevalent i n wireless terminals. M u l t i p l e antennas can form a multiple-input multiple-output ( M I M O ) system, which can provide spatial diversity gains to effectively combat fading by transmitting correlated information across the multiple antennas.  To achieve the  desired diversity gain, the spacing between two adjacent antenna elements should be at least on the order of the wavelength. However, many wireless devices may not meet such physical dimension requirements. In some wireless networking scenarios, such as an ad-hoc network, it is possible to coordinate neighboring wireless nodes such that they form a virtual MIMO  system  and cooperatively relay each other's trafBc to combat fading. In this study, a complete cooperative relay framework for wireless ad-hoc networks is proposed. T h e main contributions of this chapter are as follows:  1. In the data hnk layer, two M A C protocols are proposed for the different physical models, which have the advantages of robustness, good diversity gain, and fully distributed control.  2. In the network layer, a cooperative routing protocol ( C R P ) is proposed for route establishment and distributed relay selection based on hnk quality estimation.  3. We further propose an Enhanced C R P protocol using hnk S N R threshold to combat the gray zone problem which originates from the different transmission rates used by control  and data frames i n an ad-hoc network.  4. Simulation results show signifiicant performance gains on delay and throughput by the proposed cooperative relay design.  T h e rest of this chapter is organized as follows. Section 6.1 presents related research work in this field. Section 6.2 presents the system model as weU as our proposed cooperative M A C and routing protocols. Section 6.3 presents the simulation results for performance evaluation. A summary is presented i n Section 6.4.  6.1  Related Work  In recent years, several cooperative diversity schemes for the virtual M I M O system i n wireless ad-hoc networks have been studied from the information theory and physical layer design's perspective [1-6]. T h e basic cooperative diversity scheme works on a single-relay channel as shown i n Figure 6.1(a). A source node transmits information to the destination, and a relay node first receives and then relays the information to enhance the communication between the source and destination. Some recent schemes consider two or more available relays as shown in Figure 6.1(b). T h e performance benefits of utihzing the cooperative relaying has been weU studied i n the physical layer models which generally focus on the performance of the outage probability and average error probabihty [1-5]. T h e mode of relay operation can be classified into two main categories:  amphfy-and-forward, and decode-and-forward  [7]. In this chapter,  we focuses on studying the decode-and-forward relaying. W i t h the advances i n physical relay models, the medium access control ( M A C ) and routing protocols need to be modified i n order to fully utihze the diversity gain provided by the coop-  erative relaying. A slotted A l o h a based cooperative M A C protocol is proposed i n [8] w i t h the decode-and-forward relay. Mini-slots are used i n each transmission time slot to accommodate the need for selection and utilization of relays. Higher throughput and lower delay performance is observed compared w i t h the original slotted A l o h a M A C protocol. A cooperative diversity M A C based on the 802.11 carrier sense multiple access w i t h colhsion avoidance ( C S M A / C A ) protocol is proposed i n [9]. T h e sender activates the cooperative relay transmission when the original 802.11 request-to-send (RTS) transmission fails. However, due to the higher rehability of the R T S transmission compared w i t h the D A T A frame transmission, this scheme neglects the case when an R T S can be successfully transmitted but the D A T A frame may fail due to poor link condition. Another cooperative M A C based on 802.11 is proposed i n [10] to improve the energy-saving performance of the network. The source adaptively selects the relays and assigns the transmission power to them. However, several strong assumptions were used i n the system model, such as the acciurate estimation of the angle of arriving signal and availabihty of separate channels for control and data packets. Also, the impact on network throughput and delay were not analyzed. Several routing schemes w i t h cooperative considerations are also proposed recently. In [11] and [12], cooperative transmission is incorporated i n route selection i n wireless ad-hoc networks to improve the power consumption performance. T h e Co-Operative Diversity Enhanced A d hoc Network ( C O D E A N ) protocol is proposed i n [13] by letting each intermediate node form logical clusters of relay nodes. However, these schemes mainly focus on the route selection process and assume a working M A C layer providing the services that are needed at the network layer. Some of those assumptions on the M A C layer may either be unrealistic or over-simplified. In this study, we propose and design a complete cooperative relay framework for wireless  ad-hoc networks. For the two physical relay models considered, efficient and robust cooperative M A C protocols are proposed. T h e y are based on the distributed carrier-sensing M A C protocols used i n 802.11. T h i s design is more robust and practical for deployment than the commonly assumed time division multiple access ( T D M A ) or other orthogonal M A C relaying schemes i n the literature.  A system framework with similar design structure as ours is proposed i n  [14], where a comprehensive scheme across the physical, M A C and network layers is proposed for cooperative transmission i n ad-hoc networks.  In their work, only space-time coding is  considered at the physical layer. A primary route p a t h is constructed using the dynamic source routing ( D S R ) , and the relay nodes are selected at the M A C layer w i t h an extensively modified 802.11 D C F protocol where pilot tones are inserted after R T S frame transmission for channel estimation. Compared w i t h [14], the proposed scheme i n this chapter is apphcable to either repetition or space-time coding physical modules.  More importantly, our relay selection is  primarily carried out by the network layer with hmited assistance from the M A C protocol and is based on average hnk signal-to-noise (SNR) estimation, so that no pilot tone is needed. Rehance on pilot tones is a major concern for protocol performance i n the proposed scheme in [14], because pilot tones are assumed to be transmitted orthogonally i n time where a node decides when to transmit based on its assigned globally unique I D . T h i s introduces extra system management cost and the risk of pilot tone colhsion i n case of mis-configuration. In our proposed scheme, the route discovery and relay selection are handled by the cooperative routing protocol ( C R P ) . C R P is a distributed protocol and selects the relays based on the average hnk S N R and the two-hop neighborhood information. It considers the diflterent bit error performance of the control and d a t a frames when constructing the relay topology. C R P is simple to implement i n the existing wireless ad-hoc networks. This design also breaks the tight couphng between M A C  and network layers i n [14], and can increase the rehabihty of the system.  6.2  System IVLodel for a Cooperative Ad-hoc Network  We consider a wireless ad-hoc network w i t h N wireless stations. E a c h station has one single antenna. T h e physical layer model is presented i n Section 6.2.1. T w o cooperative  techniques  are considered at the physical layer: repetition coding with maximal ratio combining ( M R C ) , and space-time coding ( S T C ) . The cooperative M A C protocols proposed i n Section 6.2.2 utihze relay nodes to assist the transmission of data traffic between source and destination nodes w i t h cooperative relaying. For end-to-end transfer of data packets, a multi-hop routing path is determined w i t h the cooperative routing protocol ( C R P ) proposed i n Section 6.2.3. C R P establishes a routing path and pre-selects the relay nodes. The C R P is based on the widely used ad-hoc on-demand distance vector ( A O D V ) routing protocol [15], and may suffer from the gray zone problem [16, 17], which arises from the different transmission rates for control and data frames i n 802.11-based networks. A n enhanced routing protocol is further proposed i n Section 6.2.4, which uses S N R threshold to effectively combat the gray zone effect.  6.2.1  Physical Layer M o d e l  We study a wireless ad-hoc network under a slow Rayleigh fading channel. T h e received i n stantaneous S N R 7 w i t h fading is a random variable with the probabiUty density function [18]:  p(7) = ^ e - ^ / ^  (6.1)  where 7 is the average S N R at distance d from the transmitter. It is a function of received  power Pr and noise power En-  (6.2)  7 = lOlogioTT. T h e received power Pr can be estimated by the log-distance path loss model as [19]:  Pr = Pt  A2  (6.3)  (47r)2d"'  where Pt is the transmission power, A is the wavelength i n meters, and n is the path loss exponent, respectively. T h e value of n typicaUy ranges from 2 in a free space environment to 6 i n a densely populated urban environment. In the rest of this chapter, we choose n = 3. We consider a single wireless channel and assume half-duplex transmission mode for cooperative relaying, where no node can receive and transmit at the same time. T h i s is a realistic assumption because a vast majority of current radio transceivers do not have the capabiUty of full-duplex operations on the same frequency channel. In an 802.11-based wireless network [20], there exist at least two transmission rates with different modulation and coding schemes (MCSs):  the basic rate for transmitting the physical layer convergence procedure ( P L C P )  preamble and header, the control and broadcast frames; and the data rate for transmitting unicast data frame payloads, which is defined as the M P D U ( M A C Protocol D a t a U n i t ) . In this chapter, we choose the basic rate to be 1 M b p s , and assume an M C S with a binary phase shift keying ( B P S K ) modulation w i t h a convolutional code and V i t e r b i decoding.  Using the  rate 1/2 convolutional code w i t h the octal generators 133/171, the bit error rate ( B E R ) performance of this M C S w i t h an instantaneous S N R 7 can be approximated using its lower bound performance [21]: (6.4)  where  dfree  = 10 is the the m i n i m u m free distance of the code. T h e  Q{.)  function is defined as:  (6.5) We choose the data rate to be 11 M b p s , and assume an M C S which uses a 16-ary quadrature ampHtude modulation ( Q A M ) without coding. B y assuming a Gray-coded symbol assignment, the B E R performance of the 16-ary Q A M modulation can be approximated as [18, 22]:  (6.6)  Note that the assumption of using the above two M C S s does not exclude any other M C S s from being used i n our proposed cooperative M A C and routing protocols.  A s most M C S s used i n  commercial products utilize more comphcated physical transmission techniques, their accurate bit error performance is generally difficult to derive analytically, and sometimes may only be obtained w i t h empirical tests and summarized i n look-up tables. O u r approach of using the closed-form expressions of the bit error performance i n (6.4) and (6.6) can reduce the simulation computation overhead, and facilitate the performance analysis for the cooperative M A C and routing schemes. We utilize cooperative relaying only for the data transmissions at the rate of 11 M b p s . A l l control and broadcast frames are transmitted i n a basic rate of 1 M b p s without cooperative relaying. One main reason for this choice is that we need the control frames to bootstrap the system by selecting the relays and establish the relaying relationship for data frame communication.  Also, the basic transmission rate provides a much more robust error  performance compared w i t h the data rate. For data transmission between source S and destination D, two relays are selected for cooperative transmission. We denote the two chosen relays as Ri and R2, as shown i n Figure  6.1(b) where n = 2. T h e mechanisms to select the relays are incorporated into the M A C and routing protocols, and will be discussed i n detail i n Sections 6.2.2 and 6.2.3. Here, we focus on the physical layer model of the cooperative relaying scheme.  T w o cooperative diversity  techniques are studied: 1) Repetition  coding with maximal ratio combining  (MRC):  After receiving the original  frame from the source, the relay nodes first attempt to decode the received frame. T h e received frame's successful decoding depends on two factors: the preamble at the basic rate and M P D U at the data rate. T h e i r B E R can be calculated from (6.4) and (6.6), respectively. If the decoded frame is corrupted (with an incorrect cychc redundancy check ( C R C ) for either the preamble or the M P D U ) , the relay wiU discard the frame. If the frame decoding is successful, the relay w i l l transmit the frame to the destination i n its assigned relay time slot. T h e relay transmission time for Ri and i?2 is decided i n advance with the help of the cooperative M A C protocol. It assures that two relays will not transmit the frame simultaneously to avoid a collision. After receiving the three frames from the source and the two relays, the destination D w i l l utilize M R C to combine multiple copies of the received frame, and then decode it. T h e B E R s of the preamble header and the M P D U can be approximated as foUows [18, 23]:  Ppl,^  = Q (\/20(7S + 7Hi + 7fl.) ) ,  Pd^tT = 1 - ( l - 0.75Q (V0.8(7s + 7 H i + 7 H . ) ) ) ' ,  (6.7)  (6-8)  where 75, 7^1 and •yR^ are the instantaneous S N R s of the received frames at the destination from source S, and relays Ri, R2, respectively. T h i s is the B E R with the particular fading realization to be used i n our simulations.  2) Space-time coding (STC):  T h e two relays follow similar decode-and-forward process as i n  M R C . T h e m a i n difference is that they w i l l relay the frame to the destination simultaneously using a certain distributed space-time coding scheme. S T C is more efficient than the repetition coding by using one less time slot to relay, but it involves more complicated signal processing at the physical layer. T h e receiver may successfully decode the frame from the direct transmission from the source. Faihng that, the destination node can wait for the relayed S T C signal in the second time slot and decode it w i t h space-time coding. We utilize the widely used A l a m o u t i scheme [24] on the 2 by 1 multiple-input-single-output (MISO) relay channel from the relays Ri and R2 to D. T h e S N R for the effective S T C channel is the sum of the two relay frames' S N R s [25]. T h i s signal can be combined w i t h the signal from the direct source to destination transmission. A s a result, the P L C P and M P D U ' s B E R performances for S T C can be derived as: Pplïp^ = Q ( \ / 2 0 ( 7 . + 7^1+7^2)) ,  (6.9)  and  Pd^ta - 1 - (1 - 0.75Q ( v / 0 . 8 ( 7 . + 7 R x + 7 R . ) ) ) ' •  6.2.2  M A C Protocol  Design  We extend the C S M A / C A M A C protocol for 802.11-based W L A N s to support relaying.  (6-10)  cooperative  T h e C S M A / C A M A C is fully distributed, and has been shown to be robust and  stable. 1) MRC-MAC:  M R C - M A C is the M A C protocol to support repetition coding w i t h M R C  at the physical layer.  T h e t i m i n g sequence of the M R C - M A C is shown i n Figiure 6.2.  control frames R T S , clear-to-send ( C T S ) , and acknowledgement  The  ( A C K ) are transmitted at the  basic rate between a reachable pair of source and destination nodes. It is the routing layer's responsibihty to maintain this reachable neighboring cormection between S and D and selects the two relays Ri, R2, which will be discussed i n the next subsection. A successful R T S and C T S exchange between S and D leads to transmission of the D A T A frame by S. T h e M A C header of the D A T A frame contains four M A C addresses: the source node M A C , the destination node M A C , and two additional address fields MACMi  and MACJRa,  which contain the M A C  address of the two relays R\ and R2, respectively. W h e n a node receives a data frame with its M A C address contained i n the relay address field MAC-Ri  or MAC-R2,  it apphes the decode-and-forward cooperative relaying scheme.  If the  relay node can successfully decode the received frame, it relays the frame to D i n its allocated relay time slot. For the relay node with its M A C address contained i n the data or MAC-R2  frame's  MAC-R\  address field, it wiU defer for short inter-frame space (SIFS) and D A T A - h 2 x S I F S  duration, respectively, as shown i n Figure 6.2. If the relay node's decoding of the data frame fails, it will remain silent during its allocated transmission time slot. T h e destination node waits to receive three independent copies of the D A T A frame. After the duration of 3 x D A T A -|-4xSIFS, the destination w i l l decode received frames w i t h M R C . If the decoded frame successfully passes the C R C check, an A C K is sent back to the source. Otherwise, it will defer for extended inter-frame space ( E I F S ) and resume normal operation. 2) STC-MAC:  S T C - M A C is the M A C extension to support space-time coding. T h e timing  sequence is shown i n Figure 6.3. Its operation is similar to the M R C - M A C , except that the two relays wiU b o t h defer SIFS and transmit the relayed frame simultaneously using S T C . It also employs decode-and-forward, which means that if a relay cannot decode the frame from S correctly, it wiU remaiin silent during the relay time slot. T h e destination node wiU receive  the data frame i n two consecutive time slots: first, the direct transmission from the source, and then the space-time coded transmission from the two relays. If either transmission is successful, then the destination will reply w i t h an A C K frame to the sender.  6.2.3  Cooperative Routing Protocol Design  In the M R C - M A C and S T C - M A C protocols, we assume that each hop's source, destination and two relay nodes are known to the M A C layer. It is the network's responsibihty to estabhsh the end-to-end route, which selects each hop's source/destinations pairs and also the two relay nodes. We propose a cooperative routing protocol ( C R P ) for the cooperative relay network. C R P is based on the widely used A O D V routing protocol i n wireless ad-hoc networks. One important new feature i n C R P is the discovery and maintenance of relaying nodes. To incorporate this routing feature, C R P includes two new components i n the original A O D V protocol: two-hop neighborhood maintenance,  and relay selection.  1) Two-hop Neighborhood Maintenance:  Each wireless station needs to mjiintain a two-hop  neighborhood table which contains the M A C address of all of its immediate neighbors and those neighbors' immediate neighbors (the two-hop neighborhood).  Furthermore, the average link  S N R between each pair of neighboring nodes need to be recorded i n the two-hop neighborhood table. T h e H E L L O message i n A O D V is extended to include the M A C addresses of the node's immediate neighbors and each neighbor's average link S N R information. U p o n receiving a H E L L O message, each node updates its two-hop neighborhood table. T h e receiving node adds the H E L L O message's source node to its hst of immediate neighbors, and the neighbor list contained in the H E L L O message to the hst of two-hop neighbors. T h e H E L L O message is broadcast by each node every second.  2) Relay Selection:  T h e end-to-end routing path is established using the route discovery  mechanisms of A O D V w i t h the route request and route reply ( R R E Q / R R E P ) control frames. We expand the routing table w i t h two fields Ri and R2, which contain the M A C addresses of the two selected relay nodes for the next hop transmission. Whenever a new route entry is inserted into the routing table which provides a route entry from node i to destination D with the next hop j, the two relay nodes Ri and R2 are selected based on i's two-hop neighborhood table and inserted into the route entry. T h e algorithm to select the two relay nodes is as follows:  1. For every direct neighbor x of node i, look up x's list of dhrect neighbors Lx, which is contained i n i's two-hop neighborhood table. 2. If the next hop node j Ç. Lx, then determine the minimum S N R between the two logical links (i, x) and {x,j): T]x = m i n [SNR{i, x), SNR{x,j)].  (6.11)  3. Sort r]x for a l l x. T h e two nodes associated w i t h the two highest rjx values are selected as Ri and R2, respectively.  This algorithm eflFectively chooses two nodes which are common immediate neighbors of b o t h i and j, and having the two highest of the m i n i m u m S N R of the relay channels (from i to relay, and relay to j).  T h i s effectively avoids selecting relays which have a weak link with  either the sender i or the receiver j.  6.2.4  Enhanced C R P  T h e C R P protocol proposed i n the previous section can enhance the wireless conununcation compared w i t h the original A O D V . However, the C R P protocol still suffers from the well-  known gray zone problem of A O D V i n an 802.11 network [16, 17]. T h i s phenomenon stems from the large difference i n B E R performance between M C S s used by the basic rate and data rate transmission. T h e A O D V H E L L O and R R E Q packets are broadcast at the basic rate which has a much more robust B E R performance than the higher rate of data transmissions. The difference i n control frame and data frame's length (a few hundred bits versus thousands of bits) further exaggerates the frame error rate of the control and data frames. This creates long but umeliable routing hops i n the gray zone for transmitting large data frames. Various methods can be utilized to combat the effects of gray zone [26]. In this chapter, we propose an enhanced C R P protocol ( E - C R P ) by using a threshold-based approach to mitigate the gray zone effect.  W h e n a node maintains its two-hop neighborhood table, the received  H E L L O packet's average S N R is recorded w i t h a moving average. T h e H E L L O packet's sovuce node w i l l be added as an immediate neighbor i n the two-hop neighborhood table only when the average S N R of the link is above a threshold value 70. A l l received A O D V control broadcast packets will be subject to the filtering by the neighborhood table. A broadcast packet will be dropped if its source is not recorded as the receiving node's immediate neighbor despite a possible successful reception. T h e appropriate 70 threshold should be set such that it provides a well connected network topology and also maintains the average S N R of the hnk to be above reasonable levels. In this chapter, a practical 70 value is selected based on simulation experiments.  6.3  Performance Evaluation  Simulation experiments are carried out by using the ns-2 simulator. T h e following new modules are implemented i n the ns-2 simulator: the fading channel and the physical error model, the cooperative M A C and routing protocols proposed i n Section 6.2. T h e system parameters used i n the simulation are hsted i n Table 6.1.  6.3.1  Linear Topology Test  A hnear topology w i t h 10 nodes forming a 3-hop route between the source S and destination D is shown i n Figure 6.4.  In this test, the route and relay nodes are known. A s a result,  it only tests the performance of cooperative M A C protocols. ( C B R ) traffic flow is transmitted from S to D.  A 100 kbps constant bit rate  T h e distance between two adjacent nodes is  d, and d varies from 50 m to 160 m. Under our proposed cooperative relaying scheme, two relays are used i n each hop w i t h the M R C - M A C or the S T C - M A C . T h e packet delivery ratio of the network under cooperative relaying is compared w i t h the original 802.11 M A C where no relays are utihzed. T h e results for the C B R packet dehvery ratio and the end-to-end delay are shown i n Figure 6.5(a) and 6.5(b), respectively. We can see that M R C - M A C and S T C M A C consistently achieve better performance than the 802.11 M A C . T h e cooperative M A C s maintains the delivery ratio above 99% while the hop distance increases to 140 m. However, w i t h d increasing further, the delivery ratio begins to drop significantly, which means that the hnk is becoming too unrehable even for cooperative schemes to maintain a low B E R on the hnk. T h i s indicates the start of the gray zone area where a low rate control frames may still have high enough success rate, but the data frame's error rate has significantly increased.  Simulations tests w i t h one T C P flow from S to D is carried out, and the throughput performance under the three different M A C schemes is shown i n Figure 6.6. T h e 802.11 M A C has better performance when the distance is shorter than 80 m. T h i s is because within such a short distance, the link is robust enough that the frame error rate is already small without cooperation. W i t h i n this short range, cooperative M A C simply consumes more transmission time slots and lead to poorer performance. However, when d increases further, the cooperative relaying's eflfectiveness begins to show up. These results can help us decide what range of hop distance is optimal for cooperative routing protocols. In aU the tests, the S T C - M A C has both a delay performance gain for C B R traffic and a throughput gain for T C P traffic compared with M R C - M A C because it utilizes one less time slot for cooperative transmission. B u t S T C - M A C requires more enhanced signal processing capabilities i n wireless stations.  6.3.2  R a n d o m T o p o l o g y Test  T o f u l l y test the C R P protocol, we carry out a random topology test i n a 500m x 500m square area. 50 wireless nodes are randomly located within the area. One to five 50 kbps C B R flows exist i n the network with each flow's source and destination randomly selected. We compare the C B R traffic's performance under the C R P or E - C R P / c o o p e r a t i v e M A C w i t h the A O D V / 8 0 2 . 1 1 M A C . T h e results for C R P without the enhancement for gray zone reduction are shown i n Figure 6.7. T h e results for E - C R P are shown i n Figure 6.8. To have a fair comparison, we also applies the S N R threshold policy to the original A O D V to obtain an enhanced A O D V protocol w i t h gray zone reduction for the tests w i t h E - C R P i n Figure 6.8. 70 is chosen to be 10 d B which corresponds to hmiting the per-hop distance to approximately 140 m from (6.3). T h i s  is the distance where the gray zone effects begin to show up from Figs. 6.5 and 6.6 i n the hnear topology tests. E - C R P showed a performance gain of ajound 20% to 30% compared w i t h C R P without gray zone reduction. T h e delivery ratio and delay performance slightly dechnes w i t h increasing traffic load, but the cooperative M A C / r o u t i n g schemes consistently maintain a much better performance than 802.11 M A C w i t h A O D V . S T C - M A C also out-performs M R C - M A C w i t h the gains from its reduced channel access time, which i n t u r n reduces channel contention and probability of packet colHsions.. For the original 802.11 M A C without gray zone reduction, the dehvery ratio for C B R traffic can be as low as around 40% as shown in Figure 6.7(a). To explain such a low dehvery rate under the non-cooperative scheme, we carry out a simple estimation test. Consider transmitting a 1000-byte packet over a two-hop path w i t h the number of retransmissions to be equal to 4. T h e average B E R of the link varies from 10~^ to 10~^. T h e resulting packet delivery ratio versus the B E R is shown i n Figure 6.9. We can see that the packet delivery ratio drops below 40% when the B E R increases to 10~^. In the fading channel used i n the simulation model, there is a high probabihty for the link B E R to reach this level over a long hop distance without the diversity schemes. T h i s simple example shows that the dehvery ratio of a large frame can be significantly improved by the cooperative S T C - M A C and M R C - M A C which provides the significant B E R enhancements as shown i n equations (6.7) to (6.10). Simulation tests are also carried out for T C P flows. T h e number of T C P flows i n the network increases from 1 to 5. T h e total throughput under the different M A C and routing schemes w i t h or without the gray zone reduction enhancement are shown i n Figs. 6.10 and 6.11, respectively. T h e throughput under the cooperative M A C s w i t h E - C R P shows the highest performance gain. T h e S T C - M A C also outperforms the M R C - M A C because of its reduced medium transmission  time from the space-time coding. W h e n the number of flows increases, S T C - M A C ' s performance gain over M R C - M A C increases. T h i s is mainly due to increased medium access contention i n the network w i t h increasing number of traffic flows. S T C - M A C ' s reduced medium time shows its advantage i n reducing packet contentions.  6.4  Summary  In this chapter, we proposed a complete system design for utihzing cooperative relaying in wireless ad-hoc networks to improve the network performance.  In the data hnk layer, we  proposed the M R C - M A C and S T C - M A C protocols when the underlying physical layer uses the repetition coding with m a x i m a l ratio combining and space-time coding, respectively. In the network layer, we proposed the C R P and EÎ-CRP protocols for routing and relay selection. Simulation results from the linear and random topologies show significant performance gains for both C B R and T C P traffic from the EI-CRP scheme w i t h the two cooperative M A C protocols.  T a b l e 6.1: Simulation Parameters Basic Rate  1 Mbps  D a t a Rate  11 M b p s  Transmission Power  100 m W  M i n i m u m Contention Window Size  31  M a x i m u m Contention Window Size  1023  DSSS P L C P Preamble and Header  192 bits  M A C Header  192 bits  F C S (Frame Check Sequence)  32 bits  A C K Frame Size (include Headers)  304 bits  C B R D a t a Packet Size  1000 bytes  T i m e Slot  20 /is  SIFS  10 (j,s  DIPS  50 us  M a x Number of Retransmissions  4  T C P Source Protocol Version  T C P Reno  T C P Sink Protocol Version  TCP  SACK  (b) Multiple relays scenario.  F i g u r e 6 . 1 : T w o different cooperative diversity scenarios.  Busy  "TTO DIPS ^airo • - • - ^ RTS ^  ow o  SEFS  air 0 DATA  CTS  ACK  iSIFS DATA_Rl  DATA_R2  F i g u r e 6.2: M R C - M A C timing sequence.  Busy  r»TFQ  -4—^  SIFS  QTFP  RTS  -i-^  DATA  ^  ACK  CTS  DATA_Ri  DATA_R2  F i g u r e 6.3: S T C - M A C timing sequence.  F i g u r e 6.4:  Linear topology.  —T  1  1  •  1' s  0  1 I  X \  0.8  S  ; \  m \  -  \ \  0 0.6  \  1  STC-MAC MRC-MAC -•-802.11  TO 0.4  QL  CQ  \ \ \  •  \ \  ^ 0.2  y J  1  60  80  100 120 d (meters)  140  ' 160  (a) Packet delivery ratio for C B R traffic.  0.1  0.08  - • -802.11 ^ MRC-MAC -•-STC-MAC  0) (0  « 0.06 C  <û 0 0.04 1 •a c LU  0.02  60  80  100 120 d (meters)  140  (b) End-to-end delay for C B R traffic.  F i g u r e 6.5: Linear topology tests.  160  F i g u r e 6.6: T C P throughput w i t h linear topology.  •B  I I  o.s0.6  O  •STC-MAC MRC-MAC •802.11  0.4i ^  CO  Q.  m o 0.2  2  3 4 Number of CBR Flows  (a) Packet delivery ratio for C B R traffic.  _0.2 >.  o T3  c  S  0.1  • -802.11 MRC-MAC STC-MAC  T3 C  LU  2  3 4 Number of CBR Flows  (b) End-to-end delay for C B R traffic.  F i g u r e 6.7: R a n d o m topology tests for C B R traffic w i t h C R P (no gray zone reduction).  •2 0.9 CO  a:  .1 0.8  io.7r CÛ  O 0.6  0.5  •STC-MAC MRC-MAC - - -802.11  2  3 4 Number of CBR Flows  (a) Packet delivery ratio for C B R treJEc.  0.05  0.04  • -802.11 * MRC-MAC -•-STC-MAC  Q  "i 0.03 I  I  ?  •D  iS 0.02 = 0.01  1  2  3 4 Number of CBR Flows  (b) Bnd-to-end delay for C B R traffic.  F i g u r e 6.8: R a n d o m topology tests for C B R traffic w i t h E - C R R  10'=  10-"  10''  Channel BER  F i g u r e 6.9: Relationship between the delivery ratio and channel B E R  1000  Number of TCP Flows  F i g u r e 6.10: T C P throughput under random topology w i t h C R P (no gray zone reduction).  1000  STC-MAC MRC-MAC - • -802.11  0 1 •  2  3 4 Number of T C P Flows  F i g u r e 6.11: T C P throughput under random topology with E - C R P .  Bibliography [1] A . Sendonaris, E . E r k i p , and B . Aazhang, "User cooperation diversity - Part I: System description," IEEE  [2]  Trans. Commun., vol. 51, no. 11, pp. 1927-1938, Nov. 2003.  , "User cooperation diversity - P a r t II: Implementation aspects and performance analysis," IEEE  Trans. Commun., vol. 51, no. 11, pp. 1939-1948, Nov. 2003.  [3] P . A . A n g h e l and M . K a v e h , "Exact symbol error probabihty of a cooperative network i n a Rayleigh-fading environment," IEEE  Trans. Wireless Commun.,  vol. 3, no. 5, pp.  1416-1421, Sept. 2004.  [4] J . H u and N . C . Beaulieu, "Closed-form expressions for the outage and error probabihties of decode-and-forward relaying i n dissimilar Rayleigh fading channels," i n Proc. of  IEEE  ICC, Glasgow, Scotland, June 2007.  [5] G . Scutari and S. Barbarossa, "Distributed space-time coding for regenerative relay networks," IEEE  Trans. Wireless Commun., vol. 4, no. 5, pp. 2387-2399, Sept. 2005.  [6] S. V a k i l ajid B . Liang, "Effect of joint cooperation and multi-hopping on the capacity of wireless networks," i n Proc. of IEEE SECON,  San Francisco, C A , June 2008.  [7] J . N . Laneman, D . N . C . Tse, and G . W . Wornell, "Cooperative diversity i n wireless networks: Efficient protocols and outage behavior," IEEE  Trans. Inform.  Theory, vol. 50,  no. 12, pp. 3062-3080, Dec. 2004.  [8] J . M . Shea, T . F . Wong, and W . - H . Wong, "Cooperative-diversity slotted A L O H A , " less networks, vol. 13, no. 3, pp. 361-369, J u l y 2006.  Wire-  [9] S. M o h , C . Y u , S . - M . Park, H . - N . K i m , and J . P a r k , " C D - M A C : Cooperative diversity M A C for robust commimication in wireless ad hoc networks," i n Proc. of IEEE  ICC,  Glasgow, Scotland, June 2007.  [10] A . A z g i n , Y . Altunbasak, and G . A l R e g i b , "Cooperative M A C and routing protocols for wireless ad hoc networks," i n Proc. of IEEE  Globecom, St. Louis, Missouri, Nov. 2005.  [11] X . Fang, T . H u i , Z. P i n g , and Y . Ning, "Cooperative routing strategies i n ad hoc networks," i n Proc. of IEEE  VTC-Spring,  Stockholm, Sweden, M a y 2005.  [12] N . K i m , B . A n , D . K i m , and Y . Lee, "Whreless ad-hoc networks using cooperative diversitybased routing i n fading channel," i n Proc. of IEEE PACRIM,  Victoria, Canada, A u g . 2007.  [13] M . A . Tope, J . C. M c E a c h e n , and A . C . Kinney, " R o u t i n g performance of cooperative diversity i n ad-hoc networks," i n Proc. of IEEE ISCC, Pula-Cagliari, Italy, June 2006.  [14] G . Jakllari, S. V . Krishnamurthy, M . Faloutsos, P. V . Krishnamurthy, and O. Ercetin, " A cross-layer framework for exploiting virtual M I S O links i n mobile ad hoc networks," Trans. Mobile Comput,  IEEE  vol. 6, no. 6, pp. 579-594, June 2007.  [15] C . Perkins, E . Belding-Royer, and S. Das, " A d hoc on-demand distance vector ( A O D V ) routing," lETF-RFC  S561, 2003.  [16] H . Lundgren, E . Nordstrom, and C . Tschudin, " T h e gray zone problem i n I E E E 802.11b based ad hoc networks," ACM Mobile Computing no. 1, pp. 104-105, J u l y 2002.  and Communications  Review, vol. 6,  [17] W . K i m , J . Lee, T . K w o n , S . - J . Lee, and Y . Choi, "Quantifying the interference gray zone in wireless networks: A measurement study," in Proc. of IEEE  ICC, Glasgow, Scotland,  June 2007.  [18] J . G . Proakis, Digital Communications,  4th ed.  [19] T . S. Rappaport, Wireless Communications:  M c G r a w HiU Higher Education, 2000.  Principles  and Practice,  1st ed.  Prentice  HaU, 1996.  [20] I E E E 802.11 W G , " I E E E standard: Wkeless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications," 2003.  [21] S. B . Wicker, Error Control Systems for Digital Communication  and Storage, 1st ed.  Pren-  tice HaU, 1995.  [22] S. Maghrebi, M . Lotfizad, and M . Ghanbari, "The better performance of the new nonrectangular Q A M with F H T i n A D S L system based on D M T without cychc prefix," in Proc. of the 15th Intl Conference on Digital Signal Processing,  Cardiff, Wales, U K , July  2007.  [23] A . Ribeiro, X . C a i , and G . B . Giannakis, "Symbol error probabihties for general cooperative links," IEEE  Trans. Wireless Commun.,  vol. 4, no. 3, pp. 1264-1273, M a y 2005.  [24] S. A l a m o u t i , " A simple transmit diversity technique for wireless communications," J. Select. Areas Commun.,  vol. 16, no. 8, pp. 1451-1458, Oct. 1998.  [25] R . N . A . Paulraj and D . Gore, Introduction Cambridge, 2003.  IEEE  to Space-time Wireless Communications,  1st ed.  [26] B . Awerbuch, D . Holmer, and H . Rubens, "The medium time metric: high throughput route selection i n multi-rate ad hoc whreless networks," ACM/Springer and Applications,  vol. 11, no. 2, pp. 253-266, A p r . 2006.  J  Mobile  Networks  Chapter 7  Conclusions and Future Work 7.1  Summary of Work Accomplished  This thesis investigated several performance enhancement problems i n wireless local area networks. Adaptive techniques and cross-layer optimization are utilized to provide better qualityof-service i n the network. Specifically, we have studied the following five main research problems and have archived the following contributions to the field: • T h r o u g h p u t a n a l y s i s o f I E E E 802.11e W L A N s :  In Chapter 2 of the thesis, we  proposed a saturation throughput analytical model for the E D C A function of the newly introduced 802.11e W L A N [1].  T h e throughput model avoids utihzing the traditional  Markovian analysis approach, which leads to solve a complex system of nonhnear equations. A l t h o u g h accurate, the Markovian approach is difficult to utihze for many real-time algorithms, such as admission control and dynamic system parameter tuning, due to its high computation cost.  T h e new throughput model is based on mean value analysis,  and has the benefits of low computation complexity and good accuracy. T h i s throughput model was designed to provide an efficient computation tool for an admission control algorithm proposed i n this thesis. • A d m i s s i o n c o n t r o l for I E E E 802.11e W L A N s : Based on the saturation throughput  model, a novel admission control algorithm is proposed in Chapter 3 for a multi-hop 802.11e wireless network [2].  T h e use of contention graph enables us to describe the  contention situations i n the network and handle the admission control problem with the consideration of location dependent contentions.  T h e admission control algorithm can  handle multiple classes of traific as required by the 802.11e standard. A p a r t from providing QoS support to the existing voice and video flows, it also maintains a good performance for best efi'ort traiiic. Node mobility is also incorporated i n this model. Simulation results show that the admission control algorithm performs weU under a multi-hop W L A N with mobility, and provides a mechanism to differentiate between handoff and new calls.  • F r a m e s i z e a d a p t a t i o n for I E E E 8 0 2 . 1 1 n W L A N s :  In Chapter 4 of the thesis,  we investigated the M A C efiiciency enhancement of the 8 0 2 . l l n high-throughput W L A N [3].  W i t h the much higher physical layer transmission rate, the M A C layer efficiency  must be improved to gain enough benefits of the faster physical layer. Frame aggregation is one main technique to gain significant efficiency on the M A C layer. T h e two firame aggregation techniques: A - M P D U ( M A C Protocol D a t a U n i t Aggregation) and A - M S D U ( M A C Service D a t a U n i t Aggregation) are studied.  A n analytical model is proposed  to describe the throughput behavior under frame aggregations. T h e model incorporates packet loss either from collisions or channel errors. Comparison w i t h simulation results show that the model is accurate i n predicting the network throughput. We also propose an optimal frame size adaptation algorithm with A - M S D U under error-prone channels. Simulation results show that the network throughput performance is significant improved when compared w i t h both randomized and fixed frame aggregation algorithms.  • Cross-layer design of M I M O - e n a b l e d W L A N s with network utility maximization: In Chapter 5, the QoS demand of the 802.11e standard, and the proposed M I M O transmission w i t h multiple antennas i n the 802.11n proposals are studied from a crosslayer perspective [4]. We studied two M A C protocols: the carrier sense multiple access with collision avoidance ( C S M A / C A ) - b a s e d 802.11e M A C , and the slotted A l o h a M A C . For the 802.11e M A C , two different contention window size adaptation schemes, namely U-MAC  and D-MAC,  are proposed, which facilitate the M A C protocol to adapt its con-  tention window size jointly with the physical layer's M I M O operating parameters. For the slotted A l o h a M A C , a cross-layer optimization framework NUM-O  is proposed for jointly  optimizing the M I M O configuration at the physical layer and the persistent probabilities for different classes of multimedia traffic at the M A C layer. A distributed algorithm NUM-D  based on dual decomposition and a simplified version NUM-S  are also proposed.  Simulation results are presented to show the effectiveness of the proposed methods.  • Cooperative M A C and routing design for wireless ad-hoc networks: In Chapter 6, the wireless fading channel is considered. Cooperative transmission is studied to combat fading through the spatial and multi-user diversity gains [5]. M u l t i p l e wireless stations w i t h single antennas can form a virtual M I M O system, and cooperatively relay traffic for each other. A complete system framework for Wireless ad-hoc networks under cooperative relaying is proposed.  T w o different cooperative relaying techniques are considered  at the physical layer: the repetition coding and the space-time coding. In the data link layer, two medium access control protocols are proposed to accommodate the corresponding physical layer cooperative diversity schemes.  In the network layer, diversity-aware  routing protocols are proposed to determine the routing path and the relaying topology. Simulations w i t h both constant bit rate and T C P (transmission control protocol) traific show significant performance gains of the proposed cooperative relaying schemes.  7.2  Relationship Among Chapters  A l l the research topics covered i n this thesis are surrounding the network protocol design related to the 802.11 wireless local area network protocol suite. The I E E E 802.11 Working Group is under rapid development and expansion i n recent years. T h e thesis work has been striving to study several key problems i n these developments and propose effective schemes to improve network performance. T h e throughput modeling i n Chapter 2 is the basis for the admission control algorithm i n Chapter 3. T h e frame aggregation analytical model i n Chapter 4 also utihzes some of the analytical modeling concepts i n Chapter 2. Chapter 4 is mainly studying the M A C performance improvement of the 8 0 2 . l l n proposal. Further i n Chapter 5, more in-depth study of the 802.11e and 802.11n protocols is carried out.  T h e main new characteristic of the 8 0 2 . l l n standard,  which is the M I M O - e n a b l e d physical layer, is combined with the QoS-enabled 802.11e M A C , and studied from a cross-layer perspective. In Chapter 6, the network under study is expanded to the more general ad-hoc scenario, where the 802.11 protocol suite has also been widely used. T h e more realistic wireless fading channel is studied. A n d we proposed a complete system design for cooperative relaying in an ad-hoc wireless network. analyzed w i t h simulations.  T h e protocol performance is  7.3  Future Work  There are several aspects of the thesis which has potential for further studies. We present an overview of some of the possible directions for future work.  • Saturation throughput analysis of 802.11e: In Chapter 2, the proposed system model tries to describe the 802.11e W L A N ' s saturation throughput w i t h low computational complexity. For future work, the accuracy of the model can be further improved. M e d i u m access delay is another important system performance indicator which can be incorporated into this throughput model. Apphcation of this throughput model for other system dynamic tuning algorithms can be explored as well.  • Distributed admission control: In Chapter 3, our proposed admission control a l gorithm requires the complete network topology information at the access point, which makes it a centralized scheme. For future work, design of a distributed algorithm based on hmited local information sharing should be an attractive extension to work on.  • Cross-layer consideration for frame aggregation: In Chapter 4, the frame aggregation scheme is aimed to improve the M A C layer throughput. B u t aggregation can have an impact on the packet's delay performance as weU. Some delay-sensitive apphcations may have additional performance requirements on the frame aggregation algorithm. A n enhanced frame aggregation design is required to take into account the different throughput and delay requirements for QoS flows. T h e interaction between M A C layers frame aggregation and higher layer protocols, such T C P , also needs fmrther investigation.  • Distributed design of the M I M O - e n a b l e d  C S M A / C A M A C : In Chapter 5, a  distributed algorithm has been successfully proposed for the A l o h a M A C . B u t for the C S M A / C A M A C , the design is still centralized, which relies on the access point to allocate the proper operating parameters. A n extension to distributed design is difficult due to the complexity of the C S M A / C A M A C modeling. Future work shall try to design a better M A C modeling scheme which can be readily used i n the network utihty maximization formulation. Other possible research directions i n this area include extending the design framework  to a multi-hop scenario.  • A d a p t i v e d e s i g n o f t h e c o o p e r a t i v e s c h e m e : In Chapter 6, the cooperative scheme is being utihzed all the time during the operation of the network. For future work, the design can be improved by adaptively deciding when to invoke cooperative relaying on each hop. To achieve this, a proper analytical model for the cooperative relaying system is required. W i t h a good analytical model, algorithms for optimizing system operation parameters such as the S N R threshold for E - C R P can also be considered.  Bibliography [1] Y . L i n and V . W . Wong, "Saturation throughput of I E E E 802.11e E D C A based on mean value analysis," i n Proc. of IEEE  [2]  WCNC, Las Vegas, Nevada, A p r . 2006.  , " A n admission control algorithm for multi-hop 802.lie-based W L A N s , " Elsevier puter Communications  [3]  Com-  Journal, vol. 31, no. 14, pp. 3510-3520, Sept. 2008.  , "Frame aggregation and optimal frame size adaptation for I E E E 8 0 2 . l l n W L A N s , " i n Proc. of IEEE  [4]  Globecom, San Francisco, C A , Nov. 2006.  , "Cross-layer design of M I M O - e n a b l e d W L A N s w i t h network utihty maximization," IEEE  Trans. Veh. Technol, i n press, 2008.  [5] Y . L i n , J . - H . Song, and V . W . Wong, "Cooperative M A C and routing protocols design for wireless ad-hoc networks," ACM/Springer press, 2008.  Mobile Networks and Applications  Journal, i n  Appendix A  List of Publications Journal Papers  • Y u x i a L i n , J o o - H a n Song, and Vincent W . S . Wong, "Cooperative M A C and R o u t i n g P r o tocols Design for Wireless Ad-hoc Networks," accepted for pubhcation i n Mobile Networks' and Applications  ACM/Springer  Journal, 2008.  • Y u x i a L i n and Vincent W . S . Wong, "Cross-layer Design of M I M O - e n a b l e d W L A N s with Network U t i l i t y Maximization," accepted for publication i n IEEE  Transactions  on Vehic-  ular Technology, 2008.  • Y u x i a L i n and Vincent W . S . Wong, " A n Admission Control A l g o r i t h m for M u l t i - h o p 802.lie-based W L A N s , " i n Elsevier  Computer Communications  Journal, vol. 31, issue  14, pp. 3510-3520, September 2008.  Conference Papers  • Y u x i a L i n , J o o - H a n Song, and Vincent W . S . Wong, "Cooperative Protocols Design for Wireless A d - H o c Networks w i t h M u l t i - h o p Routing," i n Proc. of International ference on Heterogeneous Networking (QShine),  for Quality, Reliability,  Hong K o n g , C h i n a , J u l y 2008.  Security  ICST  Con-  and Robustness  • Y u x i a L i n and Vincent W . S . Wong, "Utility-optimal Cross-layer Design for W L A N with M I M O Channels," i n Proc. of IEEE International  Conference on Communications  (ICC),  Beijing, C h i n a , M a y 2008.  • Y u x i a L i n and Vincent W . S . Wong, "Adaptive T u n i n g of M I M O - e n a b l e d 802.11e W L A N s w i t h Network Utility M a x i m i z a t i o n , " i n Proc. of IEEE Networking  Conference (WCNC),  Wireless Communications  and  Las Vegas, Nevada, M a r c h / A p r i l 2008.  • Y u x i a L i n and Vincent W . S . Wong, "Frame Aggregation and O p t i m a l Frame Size A d a p t a tion for I E E E 802.11n W L A N s , " i n Proc. of IEEE Global Telecommunications  Conference  (Globecom), San Francisco, C A , November 2006.  • Y u x i a L i n , Vincent W . S . Wong, and Michael Cheung, " A n Admission Control A l g o r i t h m for M u l t i - h o p 802.11e based W L A N s , " i n Proc. of Third International  Conference  Quality of Service in Heterogeneous Wired/Wireless  Waterloo, O n -  Networks  (QShine),  on  tario, Canada, August 2006.  • Y u x i a L i n and Vincent W . S . Wong, "Saturation Throughput of I E E E 802.11e E D C A Based on M e a n Value Analysis," i n Proc. of IEEE working Conference (WCNC),  Wireless Communications  and Net-  Las Vegas, Nevada, A p r i l 2006.  • Y u x i a L i n , A m i r Hamed Mohsenian H a d , Vincent W . S . Wong, and Joo-Han Song, " E x perhnental Comparisons between S A O D V and A O D V R o u t i n g Protocols," i n Proc. of 1st ACM  Workshop on Wireless Multimedia Networking and Performance  Montreal, Quebec, October 2005.  Modeling  (WMuNeP),  Book Chapters  • Y u x i a L i n and Vincent W . S . Wong, "Adaptive Techniques i n 802.11-based W L A N s , " to appear i n Adaptive Networking edited by M . Ibnkahla, C R C Press.  and Cross-layer  Design in Wireless  Communications,  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0067193/manifest

Comment

Related Items