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,
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Cross-layer optimization in wireless local area networks
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Cross-layer optimization in wireless local area networks Lin, Yuxia 2008
pdf
Page Metadata
Item Metadata
Title | Cross-layer optimization in wireless local area networks |
Creator |
Lin, Yuxia |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | This thesis studies several research problems in the area of wireless local area networks (WLANs) with an objective of improving network efficiency, quality-of-service and user satisfactions. The I E E E 802.11 Working Group has been under rapid development and expansion in 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 in these developments and propose effective schemes to improve network performance. The original 802.11 standard presents a simple and robust design, but has relatively low data rate and lacks QoS support. The recent 802.11e standard and the 8 0 2 . l ln proposals aim to significantly improve the network performance in terms of QoS and throughput. In this thesis, an analytical model of I E E E 802.11e WLANs is first presented. With 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 (MAC Protocol Data Unit Aggregation) and A - M S D U (MAC Service Data Unit Aggregation) are considered. Furthermore, a comprehensive network setup is studied where the QoS requirements of the 802.11e M A C and the MIMO physical layer of 8 0 2 . l ln are both considered. Cross-layer design schemes are proposed for WLANs under two different M A C protocols: the carrier sense multiple access with collision avoidance (CSMA/CA)-based 802.11e M A C , and the slotted Aloha M A C . Lastly, the thesis studies the problem of cooperative transmission in a wireless ad-hoc network with extensions to the 802.11 M A C protocols. A complete system framework is proposed for wireless adhoc 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 path and the relaying topology. Improvements in network performance for the proposed schemes are validated with numerical and simulation tests. |
Extent | 7508229 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-04-27 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0067193 |
URI | http://hdl.handle.net/2429/7571 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2009-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
Aggregated Source Repository | DSpace |
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
Cite
Citation Scheme:
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>
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