Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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

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

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

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

Full Text

Cross-layer Optimization in Wireless Local Area Networks by Yux ia L i n B . S c , Tsinghua University, Beijing, China, 2000 M . S c , Tsinghua University, Beijing, China, 2003 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F D O C T O R O F P H I L O S O P H Y in T H E F A C U L T Y O F G R A D U A T E S T U D I E S (Electrical and Computer Engineering) T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A (Vancouver) December 2008 © Yux ia L i n , 2008 Abstract This thesis studies several research problems in the area of wireless local area networks ( W L A N s ) wi th 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 l n 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 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 Data Uni t Aggregation) and A - M S D U ( M A C 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 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 i i i avoidance ( C S M A / C A ) - b a s e d 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 ad- hoc networks uti l izing 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. Contents Abstract t . • " Contents iv List of Tables ix List of Figures x List of Acronyms x i i i Acknowledgements xv i Co-Authorship Statement xv i i 1 Introduction 1 L I I E E E 802.11 W L A N s 2 1.2 Adaptive Control in Wireless L A N s 4 1.3 Network Ut i l i ty Maximization 6 1.4 Cooperative Communication in Ad-hoc Wireless Networks ; 9 1.5 Summary of Results and Contributions 12 1.6 Thesis Organization 15 Bibliography 16 2 Saturation Throughput of I E E E 802,11e E D C A Based on Mean Value Anal - ysis 27 2.1 Background and Related Work 29 2.1.1 I E E E 802.11e 29 2.1.2 Previous Work in Performance Analysis of D C F and E D C A 31 2.2 The Analyt ical Model 33 2.2.1 Differentiation by Contention Window 34 2.2.2 Differentiation by A I F S 37 2.3 Model Validation by Simulation 40 2.3.1 Effect of Contention Window Size Differentiation 40 2.3.2 Effect of A I F S Differentiation 41 2.4 Summary 42 Bibliography 46 3 A n admission control algorithm for multihop 802.11e based W L A N s . . . . 49 3.1 Related Work 52 3.1.1 I E E E 802.11e 52 3.1.2 Related Work in Admission Control in W L A N s 53 3.2 Admission Control System Model 56 3.2.1 Network Model and Assumptions 56 3.2.2 Contention Graph 57 3.2.3 Contention Analysis of 802.11e W L A N 58 3.2.4 Available Capacity Estimation 60 3.2.5 Admission Control Algor i thm 62 3.2.6 Extension for Best-effort Traffic 62 3.2.7 Extension for Mobile User Terminals 64 3.3 Performance Evaluation 67 3.3.1 Linear Topology 67 3.3.2 Random Topology 68 3.3.3 Real-time and Best-effort Traffic Flows 69 3.3.4 Admission Control in a Mobile Network 70 3.4 Summary 71 Bibliography 86 4 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 Analyt ical Model 94 4.2.1 Uni-directional M A C 98 4.2.2 Bi-directional M A C 99 4.3 Simulation and Model Validation 100 4.3.1 Uni-directional Data Transfer 100 4.3.2 Bi-directional Data Transfer 101 4.4 Opt imal Frame Size Adaptation for A - M S D U 102 4.5 Summary 104 Bibliography 112 5 Cross-layer Design of MIMO-enabled W L A N s with Network Utility 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 System Model 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 Ut i l i ty Formulation 128 5.2.4 N U M Framework for Cross-layer Design 128 5.3 System Model for Slotted A loha M A C 131 5.3.1 Network Ut i l i ty Formulation 132 5.3.2 Ut i l i ty -Opt imal P H Y / M A C Cross-layer Design 133 5.3.3 N U M - S : Uti l i ty-Maximizat ion with Separated P H Y / M A C Layers 140 5.4 Performance Evaluation 142 5.4.1 Results for 802.11e E D C A 142 5.4.2 Results for Slotted Aloha 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 Routing Protocols Design for Wireless Ad-hoc Net- works 167 6.1 Related Work 169 6.2 System Model for a Cooperative Ad-hoc Network 172 6.2.1 Physical Layer Model 172 6.2.2 M A C Protocol Design 176 6.2.3 Cooperative Routing Protocol Design 178 6.2.4 Enhanced C R P 179 6.3 Performance Evaluation 181 6.3.1 Linear Topology Test 181 6.3.2 Random Topology Test 182 6.4 Summary 184 Bibliography 195 7 Conclusions and Future Work 199 7.1 Summary of Work Accomplished 199 7.2 Relationship Among Chapters 202 7.3 Future Work 203 Bibliography 205 A 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 105 5.1 List of Nomenclature - Part I ". 150 5.2 List of Nomenclature - Part 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 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) Random 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 with F T P flows under random topology. 81 3.10 Performajice of F T P flows under random topology. 82 3.11 Ca l l dropping probabiUty with different handoff parameter 7̂  83 3.12 Average number of received calls per second with different handoff parameter 7̂ . 83 3.13 Packet loss ratio with increasing admission parameter 7 84 3.14 Average number of received calls per second with increasing admission parameter 7 84 3.15 Packet loss ratio with increasing pause time 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 I l l 5.1 Performance of U - M A C and D - M A C versus P 157 5.2 Network uti l ity of U - M A C and D - M A C versus P 158 5.3 The tradeoff between throughput and reliability for slotted Aloha 158 5.4 Slotted A loha - Network util ity versus the number of wireless stations 159 5.5 Slotted A loha - Average throughput for best-effort trafSc with different number of wireless stations 159 5.6 Slotted Aloha - Average reliability for real-time traffic wi th different number of wireless stations 160 5.7 Slotted A loha - Network util ity versus the average S N R 160 5.8 Slotted A loha - Average throughput for best-effort traffic wi th different SNR. . . 161 5.9 Slotted A loha - Average rehability for real-time traffic with 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 Random topology tests for C B R traffic with C R P (no gray zone reduction). . . . 191 6.8 Random topology tests for C B R traffic with 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 with C R P (no gray zone reduction). . . 193 6.11 T C P throughput under random topology with E - C R P 194 List of Acronyms A C Access Category A I F S Arbitrat ion inter-frame spacing A F Ampli fy and forward A P Access point A W G N Additive white Gaussian noise B S Base station C B R Constant bit rate C C A Clear channel assessment C R P Cooperative routing protocol G T S Clear to send D G F Distributed coordination function D F Decode and forward E D G A Enhanced distributed channel access F C C Federal communications commission F C S Frame check sequence H C C A H C F controlled channel access H C F Hybr id coordination function I E E E Institute of electrical and electronics engineers I P Internet protocol I S M Industrial, scientific and medical band M A C Medium access control M I M O Multiple-input multiple-output M S D U M A C Service Data Unit M P D U M A C Protocol Data Unit N U M Network utiUty maximization P C F Point coordination function P L C P Physical layer convergence procedure R T S Request to send T C P Transmission control protocol T X O P Transmission opportunity U D P User datagram protocol W L A N Wireless local area network Acknowledgements I would like to express my deep gratitude to my research supervisor Dr . Vincent Wong for all these years of guidance and help throughout my P h D research work. His great efforts in teaching and research provided me with valuable support and good ideas. Without 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. Dr . Victor Leung, Dr . V i k r a m Krishnamurthy, Dr . Robert Schober, Dr . Lutz Lampe and Dr . Steve Wi l ton . Thanks to Dr . Fei (Richard) Y u , Dr . Enrique Stevens-Navarro, Dr . Amir-Hamed Mohsenian- Rad , Dr . Joo-Han Song, Dr . M i n Chen, Dr . Zhanping (Walter) Y i n , Dr . Qixiang (Kevin) Pang, H u i Chen, Jie Zhang, Zhibing (Harry) Chen, C h i Sun, M a n Hon (Michael) Cheung, Y i n g Wai (Ray) L a m , Yangwen Liang, Simon Y i u , Vi jay Vivekanandan, Vahid Shah-Mansouri, and Nasim Arianpoo, with whom I have the great opportunity to collaborate during the past years. Special thanks to my parents Zhaoyuan and Zhaoming, and my brother Danxia for all their support during these j^ars. This work has been supported by the research grants from Natural Sciences and Engineering Research Council ( 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 Dr . Vincent W.S . Wong, who supervises the present thesis research. Chapter 3 is also co-authored with 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 Dr . 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 in 1985 by the United 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. In 1990, the Institute of Electrical and Electronics Engineers ( IEEE) formed the 802.11 committee and began its work on standardizing the W L A N protocol for the I S M band. The first I E E E 802.11 W L A N standard didn't come out unti l 1997. B u t soon afterwards, the standard's popularity took off with 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 in W L A N s , the I E E E 802.11 protocol suite is being adapted in many other wireless networking scenarios, such as sensor networks, ad-hoc networks, and mesh networks. This thesis work focuses on studying several recent advances in the 802.11-based wireless communication systems. This work is based on recent developments in the I E E E 802.11 Working Group. The I E E E 802.11e standard added QoS supports to the network. The 802.11n proposals aim to install multiple antennas in wireless terminals and greatly boost the data throughput. The 802.11s further extends the network topology to multiple hops and form a mesh network. The rest of this chapter is organized as follows. Section 1.1 to 1.4 provide some background information in 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 IEEE 802.11 WLANs The 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 in 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 IP (VoIP) and video streaming applications. However, the original 802.11 M A C is designed with a relatively simple C S M A / C A (carrier- sense-multiple-access/coUision-avoidance) protocol. The major advantage of this M A C protocol is its robustness and fully distributed control. But 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 in 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 in 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 in 802.11e, wi l l 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 in QoS differentiation. Analyt ical 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 in 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. Apart from QoS improvement, the 802. U n working group [18] is in the process of finalizing a new P H Y / M A C extension to increase the physical layer bit rate up to 600 Mbps. To achieve the ultimate goal of providing high-throughput multimedia services with QoS support, different adaptive techniques need to be utilized in the system design in 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 wi l l look at the frame aggregation problem for an 802. U n W L A N . The 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 wi l l look at cross-layer optimization of the M I M O physical and M A C layer protocol. Another recent development in 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 with multi-hop relaying. This thesis wi l l study two problems arising from this multi-hop extension of W L A N s : the admission control problem in a multi-hop W L A N , and the cooperative transmission schemes in an ad-hoc wireless network. 1.2 Adaptive Control in Wireless LANs 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. The C S M A / C A - b a s e d D C F function has been shown to be inefficient in several communication scenarios [14, 19, 20]. This is partly due to the simple design of the standard which fixes many operation parameters in the system. Adaptive control of the communication system is one major way to improve the network performance. This thesis studies a few adaptive schemes in a W L A N . Some related development in this research area is introduced in this section. The main functionality provided by the D C F function is the binary exponential backoff algorithm, which is a fully distributed mechanism for contention control. The 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. The 802.11 standard uses a pre-defined minimum and maximum window size. Dynamically adjusting the backoff process can improve the M A C efficiency and maintain the network in 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]. The 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. Many adaptive protocols for T C P enhancement [33, 34] are proposed to adapt to the 802.11 W L A N channel. The 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 (AIFS) 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]. The T X O P is introduced in E D C A so that a station may transmit multiple frames separated by SIFS once it has gained access to the wireless medium. This improves system performance when wireless stations have many small packets for transmission, because each packet wi l l not need to go through the time-consuming access contention. This 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 cross- layer design techniques wi l l be utilized to jointly optimize the M A C layer parameters, such as the contention window size, with 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 in the multi-hop topology. 1.3 Network Utility Maximization Network uti l ity 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]. Kel ly et. al. [47] applied monotropic programming to communication networks, which is later known as the N U M problem. The 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 implicit ly solving a N U M problem [48-52]. Since then, N U M has been applied widely in studying network protocol stacks. The N U M methodology is especially useful for the cross-layer design problems [26] in 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 as- sume relative independence from each other. Each layer communicates with its upper or lower layers by exchanging minimum information required. In this way, the very complex communi- cation network design problem is broken down into manageable modules. People work in 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. The characteristics of wireless communication channels are very different from those of the wirehne channels. They are more dynamic, with a higher error rate and vary- ing transmission bandwidths [54]. These characteristics couple the higher layers performance with 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]. The generic formulation of a N U M problem usually has the following form [57]: subject to /t(x) < 0, I <i <m, hi{x) = 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 in the domain of the problem is feasible i f it satisfies al l the constraint functions. The problem (1.1) is said to be feasible if at least one feasible point exists. Otherwise, the problem is infeasible. The 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. The convexity of the N U M problem formulation is one major aspect to inspect when for- mulating a N U M problem [58]. A convex problem is much easier to investigate than a general nonlinear optimization problem. The local optimum of a convex problem is also globally opti- mal. 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. The optimal objective values of the primal and dual problems may not be equal. The difference be- tween the two optimal solutions is called the duality gap. When 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. The 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 util izing the N U M framework. The 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. This technique has been successfully apphed in 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' The second one is to study a layered protocol stack as a decomposition of the N U M formulation. When a network design problem is formulated into a N U M problem, the network performance and requirements are built into the util ity functions. Then, 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. This 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. The 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 util izing the horizontal decomposition method include the T C P congestion control, B G P and scheduling based M A C protocols [73]. The N U M framework wi l l be utihzed in studying the M A C / P H Y cross-layer design of a MIMO-enabled wireless network in Chapter 4 of this thesis. 1.4 Cooperative Communication in Ad-hoc Wireless Networks Cooperative communication is a recently developed class of methods in wireless communications which enables single-antenna wireless stations in a multi-user environment to cooperate with each other in data transmissions to exploit the spatial diversity gain. Spatial diversity has been widely utilized in multi-antenna wireless transmissions, where one wireless station is equipped with more than one antenna. The 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 minimum spacing requirement between two adjacent antenna elements, which is on the order of the wavelength. Many 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 in a manner that creates a virtual MIMO system [74]. A cooperative wireless communication network aims to increase the wireless users' quality- of-service (QoS) v ia 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. The first work of cooperative communications started from an information theoretical perspective. Cover and Gamal [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. The source node transmit to the destination node with the help of a relay node. Recent work expanded the simple relaying in a A W G N channel into a fading channel w i th diversity gain. The role of the relay node has also been expanded. The relay node may also be a traffic source or destination node rather than solely relaying other nodes' data traffic. Prom the physical layer's perspective, there are three main categories of cooperative schemes: amplify-and-forwaxd, decode-and-forward, and coded cooperation. The amphfy-and-forward (AF) scheme [76] allows the relays to amplify the received signal and retransmit the noisy signal version. The destination node combines the signals from the sender and 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 st i l l 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. When multiple relays are used, a certain relaying method can be used, such as repetition coding or space-time coding. The coded cooperation [79] integrates channel coding. Users divide their coded message into différent segments, and send these segments v ia cooperation with each other in different time slots. In this way, each user's code word is transmitted via multiple fading paths. The physical layer techniques defined the foundations of the cooperative transmission schemes. However, successful coordination of the diflFerent wireless users in 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 in 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. When 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. This thesis wi l l propose a system framework for cooperative transmission in an ad-hoc network based on the 802.11 protocol suites. 1.5 Summary of Results and Contributions This thesis studies several state-of-the-art research problems in the area of wireless local area networks with an objective of improving network efficiency, quaUty-of-service and user satis- factions. The 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 . This 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 Chua [80], thus avoids utilizing the Markovian chain model which involves compUcated non-linear system of equations. The work has been pubUshed in 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. The coverage area of W L A N s can be extended by allowing the neighboring mobile devices to relay data to the access points. This 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 in the network. In the proposed admission control algorithm, a contention graph is used to model the contention situation in the multi-hop W L A N . It is followed by an estimation of the capacity for each maximal clique in 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. The work has been published in a conference paper [82] and has been accepted for publication as a journal paper [83]. • Chapter 4 studies the recent 802 . l ln 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. The performance improve- ment of the M A C protocol by frame aggregation is studied in this chapter. Two frame aggregation techniques, namely A - M P D U ( M A C Protocol Data Uni t Aggregation) and A - M S D U ( M A C Service Data Unit Aggregation) are considered. A n analytical model is proposed to study the performance imder uni-directional and bi-directional data transfer. The proposed model incorporates packet loss either from collisions or channel errors. Fur- thermore, an optimal frame size adaptation algorithm with A - M S D U under error-prone channels is proposed, which shows significant throughput improvements. The work has been published in 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 both considered. M u l t i - ple antennas can be used to improve the performance gain by either increasing the trans- mission reliabiUty through spatial diversity or increasing the transmission rate through spatial multiplexing. This new characteristic at the wireless physical layer requires the corresponding adaptation at the medium access control ( M A C ) layer to reach the best per- formance 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 with collision avoidance ( C S M A / C A ) - based 802.11e M A C , and the slotted Aloha 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 with the physical layer's M I M O operating parameters. For the slotted Aloha 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 based on dual decomposition and a simpUfied version NUM-S are also proposed. The work has been published in two conference papers [85, 86], and is under review for pubUcation as a journal paper [87]. • Chapter 6 studies the problem of cooperation in 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 with the M E M O technique by transmitting correlated information through multiple antennas. The virtual M I M O technique, which allows mul- tiple 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 re- laying 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 accommo- date the corresponding physical layer cooperative diversity schemes. In the network layer, diversity-aware routing protocols are proposed to determine the routing path and the re- laying topology. This 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 The remainder of the thesis is organized as follows. Chapter 2 introduces the satmration through- put analytical model for 802.11e. The novel admission control scheme for an 802.11e multi-hop W L A N is proposed in Chapter 3 with 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 with M A C frame aggregation. Chapter 5 studies the problem of jointly optimizing the physi- cal and M A C parameters by util izing new featmres provided with 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 Std 802.11a: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications: high-speed physical layer in the 5 G H z band," 1999. [3] , " I E E E Std 802.11b: Wireless L A N medium access control ( M A C ) and physical layer ( P H Y ) specifications: Higher-speed physical layer extension in the 2.4 G H z band," 1999. [4] , " I E E E Std 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. Choi , 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. [9] D . He and C. Q. Shen, "Simulation study of I E E E 802.11e E D C F , " in Proc. of IEEE VTC, Jeju, Korea, Apr . 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 . Xiao , "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. [12] Z. Kong , D . H . K . Tsang, and B. Bensaou, "Performance analysis of I E E E 802.11e contention-based channel access," IEEE J. Select. Areas Commun., 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, Mar . 2000. [15] Y . Ge and J . Hou, " A n analytical model for service differentiation in I E E E 802.11," in Proc. of IEEE ICC, Anchorage, Alaska, May 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," in 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," in 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/l l /Reports /tgn_update.htm. [19] A . Kamerman and G . Aben, "Throughput performance of wireless L A N s operating at 2.4 and 5 G H z , " in Proc. of IEEE PIMRC, London, U K , Sept. 2000. [20] M . Ho, J . Wang, K . Shelby, and H . Haisch, " I E E E 802.11g O F D M W L A N throughput performance," in Proc. of IEEE VTC-Fall, Orlando, Flor ida, Oct. 2003. [21] C. Chou, K . G . Shin, and S. Shankar, "Contention-based airtime usage control in 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 . Conti , and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput l imit , " IEEE/ACM Trans. Networking, vol. 8, no. 6, pp. 785-799, Dec. 2000. [24] G . Bianchi and I. Tinnirello, "Ka lman filter estimation of the number of competing termi- nals i n an I E E E 802.11 network," in Proc. of IEEE INFOCOM, San Francisco, C A , Apr . 2003. [25] L . Bononi, M . Conti , 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, Jan. 2004. [26] X . L i n , N . Shroff, and R. Srikant, " A tutorial on cross-layer optimization in wireless net- works," IEEE J. Select. Areas Commun., vol. 24, no. 8, pp. 1452-1463, Aug . 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, Aug . 2005. [28] V . Srivastava and M . Motani , "Cross-layer design: a siurvey and the road ahead," IEEE Commun. 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, Jan. 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. Choi , and X . X u , "Adaptive cross-layer protection strategies for robust scalable video transmission over 802.11 W L A N s , " IEEE J. Select. Areas Commun., vol. 21, no. 10, pp. 1752-1763, Dec. 2003. [33] R. de Oliveira and T . Braun, " 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. Cho, "Adaptive beacon listening protocol for a T C P connection in slow-start phase in 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 in 802.11 wireless L A N s , " in Proc. of Intl. Conf. on Communications, Circuits and Systems, Gui l in , China , 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 . Majkowski and F . C. Palacio, "Dynamic T X O P configuration for QoS enhancement in I E E E 802.11e wireless L A N , " in Proc. of IEEE SoftCOM, Montreal, Canada, Sept. 2006. [38] , "Enhanced T X O P scheme for efficiency improvement of W L A N I E E E 802.11e," in 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 , " in 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," in Proc. of IEEE PIMRC, Beijing, China, 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," in 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 in I E E E 802.11," in Proc. of IEEE Globecom, San Francisco, C A , Dec. 2003. [43] Z. Kong, D . H . Tsang, and B . Bensaou, "Measurement-assisted model-based call admis- sion control for I E E E 802.11e W L A N contention-based channel access," in Proc. of IEEE Workshop on Local and Metropolitan Area Networks, San Francisco, C A , Apr . 2004. [44] Y . Xiao and H . L i , "Local data control and admission control for QoS support in wireless ad hoc networks," IEEE Trans. Veh. Technol, vol. 53, no. 5, pp. 1558-1572, Sept. 2004. [45] Y . Xiao, H . L i , and S. Choi , "Protection and guarantee for voice and video traffic in I E E E 802. l ie wireless L A N s , " in Proc. of IEEE INFOCOM, Hong Kong, China , M a r . 2004. [46] R. T . Rockafellar, Network Flows and Monotropic 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, Mar . 1998. [48] R. J . L a and V . Anantharam, "Utility-based rate control in the internet for elastic traffic," IEEE/ACM Trans. Networking, vol. 10, no. 2, pp. 272-286, Apr . 2002. [49] S. H . Low, " A duality model of T C P and queue management algorithms," IEEE/ACM Trans. Networking, vol. 11, no. 4, pp. 525-536, Aug . 2003. [50] S. H . Low and D. E . Lapsley, "Optimization flow control, I: basic algorithm and conver- gence," IEEE/ACM Trans. Networking, vol. 7, no. 6, pp. 861-874, Dec. 1999. [51] L . Massoulie and J . Roberts, "Bandwidth sharing: objectives and algorithms," IEEE/ACM Trans. Networking, vol. 10, no. 3, pp. 320-328, June 2002. [52] J . M o and J . Walrand, "Fair end-to-end window-based congestion control," IEEE/ACM Trans. Networking, vol. 8, no. 5, pp. 556-567, Oct. 2000. [53] J . F . Kurose and K . W . Ross, Computer Networking: A Top-Down Approach Featuring the Internet, 4th ed. Addison Wesley, 2007. [54] T . S. Rappaport, Wireless Communications: Principles and Practice, 1st ed. Prentice Ha 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, Aug . 2006. [58] D . P. Bertsekas, Nonlinear Programming, 2nd ed. Athena Scientific, 2004. [59] S. Boyd and L . Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [60] M . Chiang, "Balancing transport and physical layers in wireless multihop networks: jointly optimal congestion control and power control," IEEE J. Select. Areas Commun., vol. 23, no. 1, pp. 104-116, Jan. 2005. [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. Kunniyur and R. Srikant, "End-to-end congestion control schemes: util ity 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 in the internet for elastic traffic," IEEE/ACM Trans. Networking, vol. 10, no. 2, pp. 272-286, Apr . 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, Apr . 2002. [65] L . Chen, S. H . Low, M . Chiang, and J . C . Doyle, "Joint optimal congestion control, routing, and scheduhng in wirelss ad. hoc networks," in Proc. of IEEE INFOCOM, Barcelona, Spain, Apr . 2006. [66] A . Eryi lmaz 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, Aug . 2006. [67] X . L i n and N . B . Shroff, "The impact of imperfect scheduling on cross-layer congestion control in wireless networks," IEEE/ACM Trans. Networking, vol. 14, no. 2, pp. 302-315, Apr . 2006. [68] J . Lee, M . Chiang, and A . R. Calderbank, "Price-based distributed algorithms for rate- rehability tradeoff in network uti l ity maximization," IEEE J. Select. Areas Commun., vol. 24, no. 5, pp. 962-976, May 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, Aug . 2006. [70] M . Neely, E . Modiano, and C. Rohrs, "Dynamic power allocation and routing for time- varying wireless networks," IEEE J. Select. Areas Commun., vol. 23, no. 1, pp. 89-103, Jan. 2005. [71] L . Xiao , M . Johansson, and S. P. Boyd, "Simultaneous routing and resource allocation v ia dual decomposition," IEEE Trans. Commun., vol. 52, no. 7, pp. 1136-1144, July 2004. [72] R. Cruz and A . Santhanam, "Opt imal routing, link scheduling and power control in mul- tihop wireless networks," in Proc. of IEEE INFOCOM, San Francisco, C A , Mar . 2003. [73] J . - W . Lee, M . Chiang, and A . R. Calderbank, "Uti l i ty-optimal medium access control: Reverse and forward engineering," in Proc. of IEEE INFOCOM, Barcelona, Spain, Apr . 2006. [74] A . Nosratinia, T . Hunter, and A . Hedayat, "Cooperative communication in wireless net- works," IEEE Commun. Mag., vol. 42, no. 10, pp. 74-80, Oct. 2004. [75] T . Cover and A . Gamal , "Capacity theorems for the relay channel," IEEE Trans. Inform. Theory, vol. 25, no. 5, pp. 572-584, Sept. 1979. [76] J . N . Laneman, D. N . C. Tse, and G . W . Wornell, "Cooperative diversity in 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 Trans. Commun., vol. 51, no. 11, pp. 1927-1938, Nov. 2003. [78] , "User cooperation diversity - Part II: Implementation aspects and performance anal- ysis," IEEE Trans. Commun., vol. 51, no. 11, pp. 1939-1948, Nov. 2003. [79] T . riunter and A . Nosratinia, "Diversity through coded cooperation," IEEE Trans. Wire- less Commun., 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, Mar . 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," in 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 , " in Proc. of QShine, Waterloo, Canada, Aug . 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 MIMO-enabled 802.11e W L A N s with network utihty maximiza- tion," in Proc. of IEEE WCNC, Las Vegas, Nevada, M a r . 2008. [86] , "Uti l i ty-optimal cross-layer design for W L A N with M I M O channels," in Proc. of IEEE ICC, Beijing, China, M a y 2008. [87] , "Cross-layer design of MIMO-enabled W L A N s with network uti l ity 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 with multi-hop routing," in Proc. of International ICST Conference on Heteroge- neous Networking for Quality, Reliability, Security and Robustness (QShine), Hong Kong, China , July 2008. [89] , "Cooperative protocols design for wireless ad-hoc networks with 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 in 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 Medium Access Control ( M A C ) specifies two main functions for random access: the contention-based mechanism of Distributed Coordination Function (DCF) and the centralized mechanism of Point Coordination Function ( P C F ) . D C F is simple and robust, and thus has been used in 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 . Lin 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 Wireless Communications and Networking Conference (WCNC), Las Vegas, Nevada, April 2006. performance [2]. A s a result, P C F is not widely deployed in 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 in the I E E E 802.11 conmiittee has defined an ex- tension 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 Hybr id Coordination Func- tion (HCF) 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 an- alytical or simulation methods. One widely used analytical model is proposed by Bianchi [4], which models the binary exponential backoff scheme of D C F with a two-dimensional Markov chain. W i t h the popularity of the D C F in 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. As 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 Arbitrat ion Inter-Frame Space (AIFS) and the different Contention Window (CW) sizes. However, these extensions are not tr ivial . The 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 in real-time control functions such as on-line call admission control algorithms in 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 Chua [5] and use the mean value analysis. The proposed analytical model is simpler, and yet it maintains good accuracy. Our 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). Our model is applicable to the design of fast on-line algorithms such as system parameter tuning and call admission control in 802.11e networks. This chapter is organized as follows. In Section 2.1, we provide an overview of the new QoS access schemes in 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 Background and Related Work 2.1.1 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 Hybr id 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. Each A C has its own queue and channel access parameters, which include the Arbitration Inter-frame Space (AIFS) , minimum and maximum contention window sizes and Transmission Opportunity ( T X O P ) limits. The A C s gain different priority for channel access by differentiat- ing 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. During a beacon interval, a Hybr id Coordinator which is collocated with the QoS Access Point can access the wireless medium with 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 limited- duration 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 with E D C A , H C C A sti l l 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. A s a result, we focus on E D C A in this chapter. 2.1.2 Previous W o r k in Performance Analysis of D C F a n d E D C A 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 with binary exponential backoff. Most of the research work fo- cused on the saturation throughput analysis, which is the maximum load that the system can carry in a saturation condition (i.e., the transmission queue of every station is assumed to be always nonempty). This 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. Among these works, Bianchi's model [4] has attracted lots of attention. It models a single station's back-off process with a two-dimensional Markov chain. Assuming that each transmission experiences identical and independent collision probability, it obtains the stationary probability for a sta- tion to transmit in a generic time slot. The saturation throughput is obtained by dividing the expected payload information transmitted in a time slot by the expected length of a time slot. This 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. Ca l l et al. [9] model the backoff process wi th a p-persistent model. The backoff interval is sampled from a geometric distribution with 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. They also derive the optimal p value for maximizing the system capacity. Tay and Chua [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 Markov chain, their model tries to approximate the average value for a system variable wherever possible. This 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. The model vahdation shows that even though this model omits many system details, it stil l achieves good accuracy warranting its usefulness. There has been work reported in 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 in traffic differentiation. Several analytical models have also been proposed for 802.11e E D C A . They 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 . Xiao [14] enlarges the original two-dimensional Markov chain to three- dimensional, and analyzes the effects of the different contention window sizes on throughput, but the AIFS-based priority scheme is not included. Kong et al. [15] use a three-dimensional Markov chain to fully describe the backoff behavior of each A C in 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 Hou [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 in 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 in 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 in real-time). The 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 with 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 with one access category. Though the following work can be generalized to four AGs as defined i n the 802.11e standard, we focus our initial analysis on only two A C s . This avoids excessive formulation and makes the model easier to understand. We assume that there are Ni stations with 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. T X O P limit is assumed to be 0, which allows only one frame exchange each time. The 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]. In our problem, we formulate several simplifying assumptions in the model development to achieve a good trade-off between simpUcity and accuracy. The simulation validation later wi l l show that these approximations are good enough to give meaningful system predictions. 2.2.1 Differentiation by Content ion W i n d o w We first study the case when aU ACs have the same A I F S value. The traffic priority differ- entiation is thus only realized through diflFerentiating the contention window size. We assume that a packet for ACi (i = 1,2) transmitted in a time slot has a constant collision probabifity of Pi. Each unsuccessful transmission wi l l be re-tried unti l an acknowledgment is received. The number of transmissions experienced by each packet is then a geometric distribution with the probability of success I - Pi. The backoff timer starts wi th a value uniformly selected from 0 to Wi, where Wj is the minimum contention window size for AC^. The average backoff timer in the first stage is thus Wi/2. Each time a collision occurs, the contention window size wi l l double unti l it reaches the maximum stage rrii. The average number of backoff time slots experienced by a packet in ACi can be calculated as: If we assume that ACi s packet has a constant probability of transmission in each idle slot. 2 i-Pi-Pi{2pir^Wi l-2pi 2 ' i = 1,2 (2.1) then the probabihty for ACi's packet to transmit in an idle time slot can be approximated as: Ti = l/Wbi, i = l , 2 (2.2) The probability that one transmitted packet by ACi wi l l collide is the probability that any of the other {Ni — 1) AC\ stations or N2 AC2 stations also transmits: P i = l - ( l - r i ) ( ^ i - l ) ( l - T 2 ) ^ ^ (2.3) The same is true for the collision probability of AC2S 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 in a unit time period. The 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'2 (2-5) I-Pi 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 in the system in 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 wi l l be preceded with a mandatory backoff selected from the minimum contention window Wi. If we omit the dependence between two ACs and only look at ACi stations, when Ni stations uniformly choose a backoff counter from 0 to Wj , the separation between any two stations has an average of Wi/{Ni + 1). The station wi th the smallest backoff coimter may make the first transmission after Wi/{Ni + 1) slots of waiting. A s an approximation, we have: Wi Ti = Tframe + TsiFS + TACK + TAIFS + jy. ^ -^"^slot (2-7) The time taken by the successful and collision transmissions should sum up to one time unit: 2 Y.[rsi+r^)Ti = l (2.8) 1=1 It is reasonable to assume that the rate of transmission by each ACi is proportional to the number of stations in each ACi and the transmission probability by each ACi: i V m NiT2 ^ ' Equations (2.5)-(2.9) give a system of linear equations about Txi and Vsi which can be solved in closed form: r ^ i = K[il -p,/2)KT, + {l -P2/2)r2 ] - i (2.10) r.2 = [(1 -pj2)KT, + il -P2/2)r2 ] - i (2.11) r , i = i f ( l - p i ) [ ( l -pj2)KT, + il -P2/2)r2 ] - i (2.12) r.2 = ( l - P 2 ) [ ( l -p^/2)KT^ + {l -P2/2)r2 ] - i (2.13) where K = N\T\/N2T2. The saturation throughput for ACi can be calculated as: Si = rsirp,i, i = l,2 (2.14) 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 The model in 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 . When 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 + AIFSNiTsiot, i = l,2 (2.15) where Tsiot is the slot time and AIFSNi is an integer with a typical value from 1 to 7. For simplicity, in the subsequent equations, we assume that AIFSN2 = AIFSNi + M (2.16) where M is a non-negative integer. The problem with 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. The collision probabihty during this period may become lower. This violates the basic assumption that a packet belonging to one AC experiences identical collision probabihty in 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 in each zone. Kong et al. [15] expand the Markov 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 sti l l identical in 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 wi l l wait M more time slots before counting down its backoff timer. To incorporate the effects of the difference in AIFS into the framework in 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 in equation 2.1. The effect of longer AIFS2 for AC2 is converted into AC2 's equivalently longer bac;koff time slots W^Q- To calculate the total number of time slots which an AC2 packet wi l l experience due to its larger A I F S , we first estimate how many times an AC2 packet's backoff timer wi 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. The probability that AC2 's backoff wi l l be interrupted due to busy medium can be ap- proximated with AC2 's conditional collision probability p2. W i t h an average backoff timer of W2/2 in the first stage, it 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 compared to AC\. Iteratively, these extra MP2W2/2 backoff slots may introduce another P2{Mp2W2/2) timer in - terruptions, which lead to another extra Mp2{Mp2W2/2) = M ^ P 2 ^ 2 / 2 time slots. As 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: The adjusted average backoff time slots for AC2 becomes _ i-P2-P2{2P2r^w2 ( 1 \ ^ " 2 - 1-2P2 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 wi l l invalidate this equation. B y substituting WI2 as ^̂ 62 into the system of equations presented in 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]. The parameters used in the simulation are summarized in Table 2.1. The network has one access point, Ni stations with ACi traffic and N2 stations with AC2 traffic. A U the stations are within transmission range of each other. Only basic access scheme is used. Each A C is backlogged with constant bit rate traffic. The packets have a fixed payload size of 1020 bytes. 2.3.1 Effect of Content ion W i n d o w Size Differentiation 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 C W „ i n 2 = 31,m2 = 2 for simulations in Figure 2.1 according to recommended default parameter settings in the 802.11e standard [3]. Figure 2.1 shows the aggregated satiuration throughput when we symmetrically increase the number of stations in each A C from 2 to 20. The aggregated throughput for each A C and the total network throughput from simulation and the analytical model are compared. As we can see that there is good agreement between the analytical and simulation results. Also, the aggregated saturation throughput decreases with 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 in the network. The number of stations in AC\ is fixed at iV i = 5, but the number of stations in AC2 increases from 2 to 20. CWmini = 7 and CWmin2 = 15 are used. Due to the asymmetry in the number of stations, we draw the figure using the throughput per station which is a more meaningful metric. Good 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. Fig iue 2.3 shows the differentiation effect of contention window size on the saturation throughput by varying the CWmin- In this test, Ni = N2 = 10, m i = 7712 = 2, CWmin for ACi is fixed at 7, but the CWmin for AC2 increases from 7 to 63. Prom the aggregated saturation throughput for each AC, we can clearly see the effectiveness of traffic differentiation by the minimum contention window size. 2.3.2 Effect of A I F S Differentiation 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, Ni ^ N2 ^ 5, CWminX = CWmini = 31, m i = m2 = 2, AIFSNi = 2. AIFSN2 changes from 2 to 5. The 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 AC2's A I F S by one has almost the equivalent effect of doubling its CWmin value. But 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 CWmin and A I F S on the traffic. In this simulation, Ni = N2 = 5, CWmini = 31, CWmini = 63, m i = m2 = 2, AIFSNi = 2 and AIFSN2 increases from 2 to 5. The 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. The distinct advantage of this model is a lower computational overhead when compared to other multi-dimensional Markov chain approaches. Although there is tradeoff between the model complexity and its accuracy, simulation results show that our model has good accuracy. The 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 Basic Rate 1 Mbps Data Rate 11 Mbps 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 ime Slot 20 p,s SIFS 10 /Its 0 -I , , , , 2 5 10 16 20 Number of Stations in Each AC Figure 2.1: Throughput performance for symmetrically increasing load. 0.8 -1 I 0.6 - I 0-5 -I 0 .4 - a. I 0.3 - I 0.2 - ^ 0.1 - 0 - - ACI (AnalydcaO • AC1 (Simulation) AC2(Analyacal) A AC2 (Simulation) 5 10 15 Number ofStatlons In AC2 20 Figure 2.2: Throughput performance for asymmetrically increasing load. 45 -| 4 - «• a- 3.5 • S i 3 H a. 2.5 - 2 - I- g H 0.5 H Total (Analytical) 4 Total (Simulation) AC1 (Analytical) • AC1 (Simulation) AC2(AnalytlcaD A AC2 (Simulation) •••"•••A. 15 31 CWmin for AC2 63 Figure 2.3: Differentiation effect of C W m i n . 8 1 7 - M 3 I " !.. < 1 • 0 - Total (Analytical) • Total (Simulation) ACI (Analytical) • ACI (Simulation) AC2 (Analytical) A AC2 (Simulation) 'A- 3 4 AIFSN2 for AC2 Figure 2.4: Differentiation effect of A I F S . 8 n t6H 5 - 1^ * 1 0 Total (Analytical) • Total (Simulation) ACI (Analytical) • AC1 (Simulation) AC2 (Analytical) A AC2 (Simulation) 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 Edit ion (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, Mar . 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, Mar . 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 , " in Proc. of IEEE PIMRC, Taipei, Taiwan, Oct. 1996. [7] B . P. Crow, I. Widja ja , 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 con- trol in 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 , " Mobile Networks and Applications, vol. 2, no. 1, pp. 55-67, M a r . 1997. [9] F . Ca 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. Choi , 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. [13] D . He and G. Q. Shen, "Simulation study of I E E E 802.11e E D C F , " in Proc. of IEEE VTC, Jeju, Korea, A p r . 2003. [14] Y . Xiao, "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. Kong, D . Tsang, and B . Bensaou, "Performance analysis of I E E E 802.11e contention- based channel access," IEEE J. Select. Areas Commun., vol. 22, no. 10, pp. 2095-2106, Dec. 2004. [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," in Proc. of IEEE Globecom, Dallas, Texas, Nov. 2004. [18] Y . Ge and J . Hou, " A n analytical model for service differentiation in I E E E 802.11," in Proc. of IEEE ICC, Anchorage, Alaska, May 2003. [19] D . Bertsekas and R. GaUager, Data networks, 2nd ed. Prentice Hal l , 1992. [20] http: / /www.is i .edu/nsnam/ns/ index.html. 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 cur- rent 802.11a/b/g W L A N s . The Enhanced Distributed Channel Access ( E D C A ) mechanism in 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. The 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 . Lin 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 Journal, vol. 31, issue 14, pp. 3510-3520, September 2008. 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 in providing wireless Internet access v ia 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. The mobile stations form an ad-hoc multi-hop network and relay the traffic to the Q A P via each other (see Figure 3.1). In densely populated areas, network access can be easily extended with this multi-hop structure without the cost of deploying more infrastructure devices [5]. This wireless mesh topology combines the advantages of W L A N ' s infrastructure working mode and the pure ad-hoc working mode. The network is both self-organizing and self-configuring. This 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 ad- mission 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 cap- ture the traffic contention situation in 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 in the multi-hop W L A N . It is followed by an estimation of the capacity for each maximal clique in the contention graph via 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 in the system model. Handoff connections are given a higher priority in 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 in 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 re- quired. Throughput analysis has been conducted by using either simulation or analytical meth- ods. Most of the proposed analytical models extend the Bianchi's Markov chain model to take into account the different Arbitrat ion Inter-Frame Space (AIFS) and the different Contention Window (CW) sizes. However, these extensions are not tr ivial . The 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 im- plementing in real-time control functions such as on-line call admission control algorithms in I E E E 802.11e networks. In this chapter, we utilize the saturation throughput model for 802.11e E D C A access scheme from the previous chapter. The rest of this chapter is organized as follows. In Section 3.1, we provide an overview of the related new features in I E E E 802.11e and the related work in 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 in Section 3.3. Conclusions are given in Section 3.4. 3.1 Related Work In this section, we first describe the extension of the M A C protocol in the I E E E 802.11e stan- dard. It is followed by a summary of various admission control algorithms. 3.1.1 I E E E 802.11e The I E E E 802.11e standard [1] defines a Hybr id Coordination Function (HCF) to provide QoS guarantee. The 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 with 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 . The parameters include the arbitration interframe space (AIFS) , minimum and maximum contention window sizes {CWmin and CWmax), and transmission opportunity ( T X O P ) . This traffic diflFerentiation works well in light to medium network load conditions. When the network load is high, increasing contention introduces excess colHsions and retransmissions, which leads to a decrease in 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. The 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 wi l l first send an ADDTS.request (Add-Traffic-Stream Request) frame to the Q A P . The station specifies the traffic parameters such as the nominal M S D U ( M A C Service Data 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 in the ADDTS.response frame. Note that the 802.11e standard only defines the signaling frame format for admission control. The network operators are free to implement their own admission decision algorithms. This 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 A d m i s s i o n C o n t r o l in W L A N s Due to the scarcity of wireless spectrum, radio resource management ( R R M ) is essential in 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 in 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 l imit . Ca l l admission control is carried out to achieve a minimum signal-to-interference ratio (SIR). Another design criterion in wireless cellular net- works is to control the handoff dropping probability in order to reduce the incidents of dropping an active call. Admission control for W L A N s has attracted more interest in recent years. Due to the prob- abilistic 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 in ad-hoc mode. Each 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 in [11] by applying the analytical model with 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 in [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 with the bandwidth and delay requirements of the incoming call. The 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 in [13] where the admission control is based on a threshold policy. In [14], a distributed admission control scheme is proposed, which can be used in both infrastructure and ad-hoc modes. The Q A P measures the medium utihzation, and announces the transmission opportunity budget (TXOPBudget ) via periodic beacon signals for each A C (except A C 0 for best-effort traffic). When 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 in [2] by adjusting the contention level for data traffic. The 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 in [15] where the admission objective is to maximize the network utiUty. This admission control scheme works well for a network with only best-effort traffic where the network operator's revenue can be maximized. But the admission control algorithm cannot provide QoS support for real-time fiows because the throughput and delay performance is not guaranteed. The work in [16] proposed a contention aware admission control protocol ( C A C P ) to support QoS in multi-hop ad-hoc networks. Each node calculates the local available bandwidth by sensing the portion of the wireless medium time being idle. The available bandwidth in 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 VoIP calls in a 802.11- based wireless mesh network is proposed. However, the network capacity arising from multihop interference is estimated firom simulation tests. The above schemes only work with 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 in 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 admis- sion 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 maximal clique by the saturation throughput analysis. We also describe the requirements to implement our proposed admission control algorithm in a Q A P . 3.2.1 N e t w o r k 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 in the network. Without 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. The assumption of identical transmission range is widely adopted in the study of 802.11-based wireless networks [18-21]. One advantage of this simphfied physical model is that the algorithms and protocols in 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. As 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 wi l l change over time due to power control. The 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 wi l l introduce extra protocol overhead. But , 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- The transmission from node i to j is successful if [22]: 1. There is a logical link between nodes i and j. 2. No other nodes which are within the interference range Tint of node j transmit simulta- neously. 3.2.2 Content ion G r a p h In general, the interference range Tint is larger than rtx- The packets transmitted within the interference range may experience location-dependent contention for channel access. To captiure the contention relations between different neighboring links in 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 in the corresponding network graph. Given two logical links u and v e V, there is an edge ê ^ 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 in Figure 3.1. The resulting contention graph is shown in 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, in 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 in 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 Content ion Analysis 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, (3.1) 0, otherwise. The dimension of matrix F is M x L . Suppose there are in 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 l ink Z, (3.2) 0, otherwise. The dimension of matrix R is L x 5. For the S flows in 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 as: Xi = \xii,Xi2,...,Xis^, i = l , 2 (3.3) where Xij is the source rate of flow j in ACi. The traffic load from ACi on each hnk can be calculated as: Vi = R x i = [yii,yi2,yiif 1,2 (3.4) where yu is the total traffic load on hnk I from Ad traffic. The traffic load from Ad on each maximal chque is: Zi = Fyi = [zii,Zi2,... ,ZiM 1,2 (3.5) A new flow can be accepted only when the total traffic load on each maximal clique does not exceed the available capacity Cj in that cUque. That is, where 0 < 7i < 1 and is a tunable parameter. The challenge presented by the above admission decision framework is how to obtain an ac- curate estimation of the capacity Cj in 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 in 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, in a C S M A / C A based W L A N , the throughput achieved by each node usu- ally 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 in [23]. For example, in an I E E E 802.11 network, the achievable system throughput is usually less than 80% of the physical Zi :< 7i C i , i = 1,2 (3.6) transmission rate [11]. A n d this value varies with the number of stations in the network and the selected M A C parameters. Thus, in this chapter, we use the achievable throughput as the channel capacity instead of the nominal physical transmission rate. 3.2.4 Avai lable Capaci ty E s t i m a t i o n The 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 in 802.11- based multi-hop W L A N s . To this end, we use the concept of saturation throughput in 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 in 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 run for an 802.11b W L A N with ten mobile stations. Each 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 with the offered load unti l 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. As a result, the saturation throughput is a good performance figure of the system. It represents the maximum load that the system can carry in stable condition. Recall that Ci = [cji, Ci2, • • • , CIM]^ denotes the capacity vector of A C i. The element Cim denotes the capacity (i.e., saturation throughput) of maximal clique m for ACi. Given the set of ax;tive nodes in 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 in the literature (e.g., [26-29]). We use the one proposed in [30]. Let Nim (i = l i 2) denote the number of nodes with active Ad traffic in 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 + {l-^)T2]-\ (3.8) rs2,m = ( l - p 2 ) [ ( l - f ) i f m r i + ( l - Ç ) T 2 ] - \ (3.9) Km = (3.10) JV2m T-2 where t j denotes the probabihty for an ACi packet to transmit in an idle time slot, Nim denotes the number of nodes in maximal 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. The equations required to obtain the numerical solutions for the above variables can be found in Chapter 2 and [30]. The saturation throughput is the throughput achieved when all Nim nodes in the maximal chque m always have A C i traffic to send. This can be a good estimation of the capacity of a chque. Since the saturation throughput is slightly lower than the maximum 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 A d m i s s i o n C o n t r o l A l g o r i t h m 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 in our work, as presented in recent research papers [31, 32]. The position information is sent to the access point in the init ial association process. When a wireless station initializes a new flow, it sends an ADDTS.request frame to the Q A P . When 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. The Q A P then calculates the expected saturation throughput in each maximal clique and uses it to construct the maximal cHques' capacity vector c». The new flow wi l l be accepted only if equation (3.6) is satisfied. Otherwise, the new flow wi l l be rejected. Finally, the Q A P wi l l notify the mobile station its decision v ia the ADDTS.response frame. The admission control algorithm is summarized in Algorithm 1. This algorithm works with stationary stations. Extension to mobile nodes wi l l be discussed in Section 3.2.7. 3.2.6 E x t e n s i o n for Best-effort Traffic The algorithm described in the previous section assumes that both ACi and AC2 traffic flows are subject to admission control. However, data traffic are usually bursty in 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. Our proposed algorithm can be extended to handle the case of best-effort traffic. Algorithm 1 Admission Control Algorithm 1: Initialization: Q A P gathers all mobile stations' location information. 2: for an ADDTS.request arrives at the Q A P , do 3: Obtain 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: accept the new flow. 8: else 9: reject the new flow. 10: end if 11: Send admission decision to mobile station v ia ADDTS.response frame. 12: end for Without loss of generality, we assume that ACi is subject to admission control and AC2 is for best-eflfort traffic. The active links used by the best-effort traffic flows wi l l sti l l be utilized for constructing the contention graph. In addition, the number of active AC2 nodes in each chque wi l l also be used for chque capacity estimation. This usually leads to a conservative estimation of the channel capacity for the real-time flows, because not al l AC2 nodes may be active simultaneously. Furthermore, the best-effort traffic such as T C P flows have congestion control mechanisms and usually wi l l not cause the network to be operated in a saturated condition. As a result, the admission control Algorithm 1 can be used with the following changes: 1. The source rate vector in Step 3 wi l l only include ACi. 2. For the decision making in Step 6, the constraint wi l l 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 in equation (3.6) wi l l 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 User Terminals The 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 in the multi-hop network. This section describes the extensions needed to accommodate node mobility. The 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. When user terminals move around, the change in distances between nodes may alter the con- tention relationships between them, which in turn 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 util izing this link wi l l become invalid and a route discovery process wi l l be initiated to find a new route by an ad-hoc routing protocol. This wi l l lead to a change in the the routing matrix R. Both F and R are important parameters for making the correct routing decision in the admission control algorithm. When 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 in R occur more often than changes in the contention graph F , and has a greater impact on system performance. As a result, we may only consider the route change events. When 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 in 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 in Algorithm 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 wi l l be sent to the Q A P requesting that the existing QoS flow be handed over to the newly estabHshed path. Upon receiving the ADDTS.renew frame, the Q A P wUl update the F and R matrices using the updated information, and wi l l decide whether to accept the handoff call based on: Zi ^ -y'iCi, i = l,2 (3.11) where 0 < 7- < 1 is a tunable parameter generally greater than 7 i n (3.6), such that the handoff call has a higher priority than the new calls in order to reduce the probability of dropping an on-going call. The algorithm is summarized in Algorithm 2. Algorithm 2 Admission Control Algorithm - Mobi l i ty 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: Obtain 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: else i9: drop the handoff flow request. 10: end if 11: Send admission decision to mobile station via ADDTS.response frame. 12: end for 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 in Table 3.1. The transmission range of each wireless station, rtx, is 100 m. The interference range, r-jnt is twice the transmission range. Only 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 with 10 mobile stations, as shown in Figure 3.4(a). The 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 in 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. Each video traffic source is a C B R data source, using U D P with a constant payload of 1500 bytes and an average inter-arrival time of 40 ms. It corresponds to a 300 kbps traffic stream. The A I F S N and CWmin/CWmax values are set according to the I E E E 802.11e standard [1]. CWmin/max for 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. The Destination-Sequenced Distance-Vector Routing (DSDV) [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 ADDTS.request 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. The Q A P either accepts or rejects the flow request based on the decision rule in 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 in Figure 3.5. The results for video flows are shown in Figure 3.6. We compare with the case when no admission control mechanism is enforced. From 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. Without 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 in a 500 m x 500 m coverage area, with the Q A P located at the center as shown in Figure 3.4(b). The 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 in the hnear topology test. The throughput and delay performance for voice and video flows are shown in Figures 3.7 and 3.8. The 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. This 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 in the network. 3.3.3 Real - t ime a n d Best-effort Traffic Flows In this test, we examine the efltectiveness of the admission control algorithm when both real- time and best-efltort traffic co-exist. The test uses the same random topology as in 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. The stations numbered 3, 6, 9 initiate three F T P flows to the Q A P via 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. The throughput and delay performance for voice flows are shown in Figure 3.9. The performance of F T P flows is shown in Figure 3.10. We can observe that with a reduced 71 value, only 4 voice flows are admitted. When no admission control is used, the throughput of F T P flows goes to zero. This is the well-known starvation problem in 802.11e E D C A [35]. When 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. This is due to the location-dependent contention in the multi-hop W A N . The 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. As a result, it causes more contention than the fifth flow and is rejected. This 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 A d m i s s i o n C o n t r o l in a M o b i l e 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. The Q A P is located in the center of the coverage area. A l l the mobile nodes move according to the random way- point mobility model. The maximum and minimum speeds are 10 m/s and 0 m/s , respectively. The 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 in Section 3.3.1. The A d hoc O n Demand Distance Vector ( A O D V ) routing protocol is used. The call inter-arrival time is exponentially distributed with a mean of 10 s. C a l l duration is also exponentially distributed with a mean of 15 s. Each simulation runs for 500 s. We fix 71 = 72 = 0.5, and vary 7̂  = j'2 from 0.5 to 1. The resulting call dropping probabihty, which is the ratio of the number of dropped calls divided by the total number of ADDTS.renew requests, is shown in 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 in the network is 20, 30, and 40, respectively. The other simulation parameters remain the same. The 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. The random waypoint mobility model is the default mobility model used by ns-2, and has several shortcomings [36]. Although the proposed admission control algorithm is independent of specific mobihty models, its effectiveness may be influenced by the mobility scefiarios. As 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 sti l l under acceptable levels with the proposed admission control mechanism. The 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 in 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 in the model. Simulation results show that the admission control algorithm performs well under a multi-hop W L A N with 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 Data Rate 11 Mbps 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 Time Slot 20 fis SIFS 10 fis F i g u r e 3.1: A multi-hop W L A N . Each 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. Clique {1, 2, 4;. i? l ique{1.2 , 3} — - - ^ 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. 4.8 4.6 a. i 3 Q. 1 4.4 I- 2 4.2 M a x i m u m Throughput ^ Saturation Throughput 1 I 1 f i I \ 1 J. A / / Optimal Operat ion R a n g e for A d m i s s i o n C o n t r o l • 1 - - r - - -1 1 1 1 4.5 5 5.5 6 Traffic Load (Mbps) 6.5 F i g u r e 3.3: Network throughput with increasing traffic load. (b) Random Topology. F i g u r e 3.4: Simulation topologies: (a) Linear topology, (b) Random topology. 600 500 - 400h ^ 300 I S 200 100 0 1 ' r Throughput (with Admission Control) Throughput (no Admission Control) i Voice Flows Rejected •by Admission Controlle • 0 20 40 60 Time (s) 80 100 120 (a) Throughput. I" u Q 1 B 0.1 r 0.01 r lE-3 7 • Delay (with Admission Contit)!)^ , j • Delay (no Admission Controlj) / I' \j if' A ^ > i ^/xl.jiVoice Flows Rejected . :by Admission ControllQ ' i! 20 40 60 Time (s) 80 100 120 700 600 "•" _ 500 - è 400 - 0 1 200 - 100 - 0 0 - Throughput (with Adiiission Control) • Throughput (no Admifssion Control) i •* / Video Flows Rejected (1; ' ! by Admission Controller r r 20 ! Video Flow's Starvatioi ! jnthout Admission Cofirol 4 L 40 60 Time (s) 80 1 0 0 1 2 0 (a) Throughput. 0.1 r S W 0.01 • Delay (with Admisçion Control) • Delay (no Admission Control) ; Video Flovip Rejected ; by Admissi{>n Controller Î 20 40 60 80 Time (s) 100 120 600 500 400 I "3 300 I § 200 100 - - Throughput (with Admission Control) - Throughput (no Admission Cdntrol) f\ ;\ . j 0 20 jVoice Flows Rejected jby Admission Controlle 40 60 Time (s) 80 100 120 (a) Throughput. 1 r 0.1 r I i 0.01 -1 • 1 < r • Delay (with Admission Control) • Delay (no Admission Control) a / : j i i iVoice Flows' Rejected jby Admissiqn Controlle -I i 20 40 60 80 Time (s) 1000 800 f 600 1 , 1 , 1 1 , , j p Throughput (with Admission Contiol) Throughput (no Admission Control̂ \^y. I I 400 - 200 Video Flows Rejectê 1 byjAdmission Contrqller _i L. 0 20 40 60 80 Time (s) 100 120 (a) Throughput. Q I 1 r - Delay (with Admission Control) • Delay (no Admission Control) I I 0.1 r video FJOWS Rejected b;̂  Admission Contipller - j - - — > 0.01 r 0 20 (a) Throughput. 0.14 0.121- ^ 0.10 h Q 0.08 - I 0.06 ^ I ^ 0.04 h 0.02 - • èelay (wiài Admission Control) • Delay (without Admission Control) r i i - 20 40 i ! 11 i i ! i i ! i i ! i i ! 60 80 100 120 Time (s) 1500 1250 - • Throughput (with Admission Control) • Throughput (no Admission Control) FTP Flows Bxpenence Starvation wi&out Admission Cooèol 1 I Ï I Ï 0 0 1 2 0 Time (s) (a) Throughput. I 0.20 - 0.15 - 0.10 - RTT (with Admission Control) RTT (no Admiss^op Cotjtrol) 1st Voice Flow Rejected by Admission Controller IF iVoice Flows Rejected \; •by Admission Controller ' 0.00 20 40 60 80 Time (s) 100 120 0.1 - Z 0.0 I 1 ' 1 ' 1 ' 1 ' 1 • L- 0.5 0.6 0.7 0.8 0.9 1.0 Handoff Parameter / F i g u r e 3.12: Average number of received calls per second wi th different handoff parameter 7̂ . 1 • 1 • r 1.5 - : I I I I I I I I I : 0.5 0.6 0.7 0.8 0.9 1.0 Admission Panuneter y F i g u r e 3.13: Packet loss ratio wi th increasing admission parameter 7. 0.60 Admission Parameter y F i g u r e 3.14: Average number of received calls per second wi th increasing admission parameter F i g u r e 3.15: Packet loss ratio with 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 Std 802.11, 1999 Edit ion (ReaiF 2003)," Sept. 2005. [2] Y . Xiao , H . L i , and S. Choi , "Protection and guarantee for voice and video traffic i n I E E E 802.11e wireless L A N s , " in Proc. of IEEE INFOCOM, Hong Kong, China, M a r . 2004. [3] S. M . Faccin, C . Wi j ing , 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, Apr . 2006. [4] O. Oyman, J . N . Laneman, and S. Sandhu, "Multihop 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 . Lott , W . Zirwas, M . Dohler, H . Aghvami, D . Falconer, and G . Fet- tweis, "Relay-based deployment concepts for wireless and mobile broadband radio," IEEE Commun. Mag., vol. 42, no. 9, pp. 80-89, Sept. 2004. [6] M . H . Ahmed, " C a l l admission control in wireless networks: a comprehensive survey," IEEE Comm. Surveys and Tutorials, vol. 7, no. 1, pp. 50-69, Apr . 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," in Proc. of IEEE PIMRC, Beijing, China, Sept. 2003., [8] D . Pong and T . Moors, " C a l l admission control for I E E E 802.11 contention access mecha- nism," in 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 in I E E E 802.11," in Proc. of IEEE Globecom, San Francisco, C A , Dec. 2003. [10] Z. Kong , 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," in Proc. of IEEE Work- shop on Local and Metropolitan Area Networks, San Francisco, C A , Apr . 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, Mar . 2000. [12] J . Zhu and A . O. Fapojuwo, " A new call admission control method for providing desired throughput and delay performance in IEEE802.11e wireless L A N s , " IEEE Trans. Wireless Commun., vol. 6, no. 2, pp. 701 - 709, Feb. 2007. [13] Y . - J . Cho i and S. Bahk, "Feedback-based bandwidth allocation with call admission control for providing delay guarantees in I E E E 802.11e networks," Computer Communications, vol. 28, no. 3, pp. 325-337, Feb. 2005. [14] Y . Xiao and H . L i , "Local data control and admission control for QoS support in 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 in 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 . Yang and R. Kravets, "Contention-aware admission control for ad hoc networks," IEEE Trans, on Mobile Computing, vol. 4, no. 4, pp. 363-377, Ju ly 2005. [17] H . Wei, K . K i m , A . Kashyap, and S. Ganguly, " O n admission of VoIP calls over wireless mesh network," in Proc. of IEEE ICC, Istanbul, Turkey, June 2006. [18] K . Nahm, A . Helmy, and C . - C . J . Kuo , " T C P over multihop 802.11 networks: issues and performance enhancement," in Proc. of ACM MobiHoc, Urbana-Champaign, I L , M a y 2005. [19] A . Acharya, A . Misra , and S. Bansal, "High-performance architectures for IP-based mul- tihop 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, Apr . 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 Trans. Inform. Theory, vol. 51, no. 6, pp. 1938-1953, June 2005. [23] P. Gupta and P. Kumar , "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 with infrastructure support," IEEE J. Select. Areas Commun., vol. 23, no. 3, pp. 657-667, M a r . 2005. [25] M . Kodia lam and T . Nandagopal, "Characterizing achievable rates in multi-hop wireless mesh networks with orthogonal channels," IEEE/ACM Trans. Networking, vol. 13, no. 4, pp. 868-880, Aug . 2005. [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," in 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. Kong , D . Tsang, and B . Bensaou, "Performance analysis of I E E E 802.11e contention- based channel access," IEEE J. Select. Areas Commun., vol. 22, no. 10, pp. 2095-2106, Dec. 2004. [29] Y . Xiao , "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. [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," in Proc. of IEEE WCNC, Las Vegas, Nevada, Apr . 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," in Proc. of IEEE SECON, Reston, V A , Sept. 2006. [32] J . Y i n , Q. Yang, and L . M . N i , "Learning adaptive temporal radio maps for signal-strength- based location estimation," IEEE Trans. Mobile Comput, vol. 7, no. 7, pp. 869-883, Ju ly 2008. [33] http: / /www.is i .edu/nsnam/ns/ index.html. ns-2 simulator. [34] C. Perkins and P. Bhagwat, "Highly dynamic Destination-Sequenced Distance-Vector rout- ing (DSDV) for mobile computer," in Proc. of ACM SIGCOMM, London, U K , Sept. 1994. [35] N . Ramos, D . Panigrali i , and S. Dey, "Quality of service provisioning in 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 . Le Boudec and M . Vojnovic, "The random trip model: StabiUty, stationary regime, and perfect simulation," IEEE/ACM Trans. Networking, vol. 14, no. 6, pp. 1153-1166, Dec. 2006. 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 Medium Access Control ( M A C ) and Physical Layer ( P H Y ) specification [1-3]. A t the P H Y layer, 802.11n wi l l 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 Mbps. The 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 Mult iple Access - Collision Avoidance) random backoff period for successive frame trans- missions. The 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 Data Uni t Aggregation ( A - M P D U ) or M A C Service Data Uni t Aggregation ( A - M S D U ) . ^ A version of this chapter has been published. Y . Lin 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 Global Teleœmmunications Conference (Globecom), San Francisco, C A , November 2006. Although frame aggregation can increase the throughput at the M A C layer under ideal channel conditions, a larger aggregated frame wil l 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 through- put performance under different channel error conditions. Y i n et al. [13] study the effects of packet size in an error-prone channel for I E E E 802.11 D C F and conclude that there is an opti- mal packet size under a certain bit error rate ( B E R ) to achieve the maximum throughput. C i and Sharif [14] propose an optimal frame size predictor based on Ka lman filter to maintain a committed goodput. Most of these studies assume that a single bit error can corrupt the whole frame. This assumption may not be true for the 8 0 2 . l l n M A C layer wi th frame aggregation. In this chapter, we provide a unified approach to study the satiuration throughput and delay performance of the proposed frame aggregation schemes in the new 8 0 2 . l l n proposals under error-prone channels. Both uni-directional and bi-directional transfer are being considered. The 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 with the randomized and fixed frame aggregation algorithms. These studies serve as the basis for further optimization of the system parameters in the 8 0 2 . l l n W L A N s . The 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 in Section 4.3 to validate the accuracy of the analytical model. A n adaptive frame size adaptation algorithm is proposed in Section 4.4. A summary is given in Section 4.5. 4.1 Related Work and Background on IEEE 802.11n In this section, we provide an overview of several new M A C mechanisms in 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. The first technique is by concatenating several M A C Service Data Units (MSDUs) to form the data payload of a large M A C Protocol Data Unit ( M P D U ) . The P H Y header and M A C header, along with the frame check sequence (PCS) , are then appended to form the Physical Service Data Unit (PSDU) . This technique is known as MSDU Aggregation ( A - M S D U ) . Figure 4.1 shows the frame format for A - M S D U . The second technique is called MPDU-aggregation ( A - M P D U ) . It begins with each M S D U appending with 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 . Padding bits are also inserted so that each s u b - M P D U is a multiple of 4 bytes in length, which can facihtate subframe delineation at the receiver. Then, 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 . The 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. The transmission sequence wil l then become R T S - C T S - D A T A f - D A T A r - A C K . This 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 al 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 within 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 wi 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 error- prone channels. In the analytical model, we assume that there are N mobile stations in the W L A N . Each mobile station has saturated traffic. The wireless channel has a bit-error-rate ( B E R ) of Pi,. The minimum 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. As a result, this chapter only discusses the access scheme with R T S / C T S . In 802.11 W L A N s , the control frames (RTS, 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 in 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. The possible t iming sequences for A - M P D U and A - M S D U in the uni-directional transfer case are shown in 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. The 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: - (41) (1 - 2p){W + l)+pW{l - (2p)'") ' ^ • ' where p is the unsuccessful transmission probability conditioned on that there is a transmission in a time slot. When considering both collisions and transmission errors, p can be expressed as: p = l - ( l - P e ) ( l - P e ) , (4.2) where pc = I - {I - T)^^~^^ 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 in the time slot. For uni-directional transfer, Pe is the error probability corresponding to the error case in 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 in Figure 4.3(b) and (c). In the following, we wi l l use the vector form for generality, and equation (4.2) for the bi-directional case is: p = l - ( l - p c ) ( l - P e , l ) (4.3) Note that only pe,i for Figure 4.3(b) contributes to p. This is because in the case of Figure 4.3(c), we follow our previous assumption that the BACKf control frame is error-free. Thus, BACKf for the forward frame is always successful and the DATAfs sending station wi l l not double its contention window in this case. The probability of an idle slot is: Pi<«e = ( l - r ) ^ (4.4) T h e probabihty for a transmission in a time slot is: Ptr^l- Pidie = ! - ( ! - r ) ^ . (4.5) The 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 The transmission failure probabihty due to error (no collisions but having transmission errors) is: Perr = Ptr Ps Pe = [Perr.l.Perr.a]^ (4.7) where Perr.i and Perr,2 correspond to the two different error timing sequences for the b i - directional transfer in Figure 4.4. Perr reduces to a scalar for the uni-directional case. The probability for a successful transmission (without collisions and transmission errors) is: Psucc = PtrPsil - Pe,l - Pefi)- (4.8) The network's saturation throughput can be calculated as: 5 = | , (4.9) where Ep is the number of payload information bits successfully transmitted in a virtual time slot, and Et is the expected length of a virtual time slot. We have: Et = TidlePidle + TcPtril - Ps) + Te^Perr + Ts^œPsucc, (4.10) where TicUe, Tc and Tsucc are the idle, collision and successful virtual time slot's length. Te 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. Apart from throughput, we study the average access delay experienced by each station in the uni-directional case. The 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 = i V ^ , (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. Tc = RTS + EIFS, (4.12) where R T S is the transmission time for an R T S frame. The other parameters are case-dependent and wi l l be discussed separately in the following subsections. 4.2.1 Uni -d irect ional M A C In the uni-directional case, the equations for Tsucc, 2e and Ep are as follows: Tsucc = RTS + CTS+ DATA +BACK+ 3SIFS +DIES, (4.13) Te = RTS + CTS + DATA+ EIFS + 2SIFS, (4.14) Ep = LpP,ucc = LpPtrPsil-Pe), (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 - P t ) ^ , (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 F C S . For A - M P D U , error occurs when all the sub-frames become corrupted. The variables pe and Ep can be expressed as: Pe = Hil-il-Ptf^), (4.18) i Ep = 53(Li - L«„6Mr)i ' trP .(l - n)^% (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 -d irect ional 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 in this chapter. The A - M P D U case can be derived in a similar way based on the following discussions. For error in the forward frame (see Figmre 4.4(b)), we have: Te,i = RTS + CTS + DATAf + 2SIFS + EIFS, (4.20) Pe,i = 1 - (1 - P6 )^^^^A (4.21) For error in the reverse frame (see Figure 4.4(c)), we have: Te,2 = RTS + CTS + DATAf + BACK f + DATAr + ZSIFS + EIFS, (4.22) Pe,2 = ( 1 - P 6 ) ^ ^ ^ ^ ^ [ 1 - ( 1 - P 6 ) ^ ^ ^ ^ ' - ] . (4.23) For a successful bi-directional frame transmission: Tsucc = RTS + CTS + DATAf + BACK f +DATAr +BACKr + 4SIFS + DIPS. (4.24) Since we assume that the BACK control frame is transmitted at the basic rate, DATAf wil l be successfully received in the case of Figure 4.4(c). Thus, the expected successful payload information transmitted Ep can be expressed as: — i^f +I^r- 2Lhdr)Psucc + (Lf - Lhdr)Perr,2 = {Lf + Lr- 2LMr)PtrPs(1 - Pe.l - Pefl) + {Lf - Lhdr)PtrPsPe,2 (4.25) 4.3 Simulation and Model Validation To verify the accuracy of the analytical model proposed in Section 4.2, simulations are carried out in the ns-2 simulator [15] for throughput and delay performance comparison with the analytical model. The parameters used in the simulation are from [16]. They are also shown in Table 4.1. 4.3.1 Uni -d irect ional D a t a Transfer In this simulation, there are 10 wireless nodes and one access point in 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 in length. The number of packets aggregated in one M A C frame varies from 1 to 80, which leads to an aggregated payload size from 100 Bytes to 8 KBytes . 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 in the figures are the results obtained from the analytical model. The simulation results are shown in discrete marks. Comparison with the simulation results show that the analytical model is accurate in predicting the network performance. From these figures, we can observe that the saturation throughput decreases and the de- lay increases wi th increasing B E R for both aggregation schemes. A - M S D U achieves a higher throughput than A - M P D U under ideal channel conditions (i.e., B E R = 0). This is due to the fact that A - M S D U includes a lower overhead in the aggregation process than A - M P D U . How- ever, under error-prone channels, the advantage of A - M S D U quickly diminishes. The 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 in error-prone channels. This is because without the protection of P C S in 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 with increasing aggregated frame size. As 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. As a result, we need to choose the proper aggregation scheme and adapt their parameters according to the different channel conditions and appUcation requirements in order to achieve an optimal performance. This chapter provides the performance analysis model. In Section 4.4, we wil l 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 irect ional D a t a Treinsfer The satiuration throughput performance for A - M S D U with bi-directional data transfer under different B E R is shown in Figure 4.9. The numbers of aggregated M S D U s in the forward and reverse data aggregation are set to 20 and 1, respectively. The number of stations is varied from 5 to 30. The simulation results validate the accuracy of the analytical model in 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 in 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 maximum throughput imder different B E R conditions. The optimal aggregated frame size L* to achieve this maximum throughput varies with the channel's B E R condition. To further determine the relationship between L* and the number of contending stations, we conduct an experiment in which the number of stations changes from 10 to 30. The other parameters are the same as in Section 4.3. The analytical and simulation results are shown in 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 in 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 in Section 4.2 by using an average number of stations N in the network. The 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 wil l 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 with a size that is close to the optimal frame size. The 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, in 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 in a closed-loop fashion. In this chapter, we assume that such a feedback mechanism is available in 8 0 2 . l l n to provide the sending station with 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. The 144.44 Mbps data rate is used which leads to an effective transmission range of 25 m. The network topology consists of an open space of 50 m x 50 m. The access point is fixed at the center of the area. There are N wireless nodes in the network, and they move according to a random waypoint mobility model. The maximum speed is 5 m/s and the pause time is 5 s. A l l the wireless terminals are saturated with C B R traffic. The number of stations is varied from 5 to 20. The 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 minimum (100 B ) and maximum (20 K B ) frame size allowed. From the simulation results shown in 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 in 8 0 2 . l l n W L A N s under error-prone channels. The effects on sys- tem throughput and delay performance with the uni-directional and bi-directional data transfer methods are analyzed by both analytical and simulation methods. Comparison with the simu- lation results show that the analytical model is accurate in 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 per- formance than two other heuristics. T a b l e 4 .1 : I E E E 802.11n Simulation Parameters Basic Rate 54 Mbps Data Rate 144.44 Mbps 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 Time 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 N Subframe HDR MSDU Padding F i g u r e 4 .1 : Frame format for A - M S D U . PSDU PHY HDR A-MPDU \ Subframel Subframe 2 • * * Subframe N Delimiter MPDU Header MSDU FCS Padding Sub-MPDU F i g u r e 4.2: Frame format for A - M P D U . RTS ' ^ EIFS (a) RTS CoKision RTS :>IFS DATA EIFS CTS (b) DATA Frame Corruption BIFS RTS DATA SIFS CTS BACK (c) Success F i g u r e 4.3: Uni-directional R T S / C T S access scheme. R T S (a) R T S Collision R T S DATAf EIFS M • C T S (b) Forward DATAf Frame Corruption R T S àlFS m DATAf S I F S C T S BACKf DATAr (c) Reverse DATAr Frame Corruption R T S JIFS m DATAf s|5g S I F S BACKr C T S BACKf DATAr (d) Success F i g u r e 4.4: Bi-directional R T S / C T S access scheme. Xi 3 Q. Oi O BER=0 (Analytical) • BER=0 (Simulation) BER=1E-05 (Analytical) A BER=1E-05 (Simulation) BER=2E-05 (Analytical) O BER=2E-05 (Simulation) BER=5E-05 (Analytical) 0 BER»5E-05 (Simulation) BER»1E-04 (Analytical) V BER=1E-04 (Simulation) ̂  TÛr -A- - A - A - A . A - u o. o. .< o ; y V V V V $ $ 4 ^ ^ i 30 40 50 60 70 80 10 20 Number of Aggregated MSDUs Figure 4.5: Saturation throughput for A - M S D U . 10̂ 10̂  r 10° V Q 10"̂ -2 10 10" BER=0 (Analytical) • BER=0 (Simulation) BER=1E-05 (Analytical) A BER=1E-05 (Simulation) BER=2E-05 (Analytical) O BER=2E-05 (Simulation) BER=5E-05 (Analytical) 0 BER=5E-05 (Simulation) BER=1E-04 (Analytical) V BER=1E-04 (Simulation) V • o o 10 20 30 40 50 60 Number of Aggregated MSDUs 70 80 Figure 4.6: Access delay for A - M S D U , 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) 510-̂ Q . , o . - 0 " ' .o o o 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»- 35, S-30 25 =J Q. •&20 2 15 10 ^ 0 - n - -o— BER=0 (Analytical) • BER=0 (Simulât" on) BER=1E-5 (Analytical) 0 BER=1E-5 (Simulation) BER=1E-4 (Analytical) O BER=1E-4 (Simulation) 10 15 20 Number of Stations 25 30 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.10: A - M S D U throughput under different number of stations. O) 35 - Z3 O ^ 3 0 - 2 5 - —•— 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) 2 0 - - O - —T— 10 — r - 15 20 Number of Stations F i g u r e 4 .11 : 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 stan- dard," Jan . 2005. [3] Enhanced Wireless Consortium, " H T M A C specification," Jan. 2006. [4] J . Yeo and A . Agrawala, "Packet error model for the I E E E 802.11 M A C protocol," in Proc. of IEEE PIMRC, Beijing, China, 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 in fading channel," in 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 in presence of transmission errors," in 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, Mar . 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 Trans. Networking, vol. 8, no. 6, pp. 785-799, Dec. 2000. [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, Mar . 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 , Mar . 2005. [13] J . Y i n , X . Wang, and D. P. Agrawal, "Opt imal packet size in error-prone channel for I E E E 802.11 distributed coordination function," in Proc. of IEEE WCNC, At lanta, Georgia, M a r . 2004. [14] S. C i and H . Sharif, "Improving goodput in 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 Computing, vol. 5, no. 3, pp. 329-342, M a y 2005. [15] Ns-2 simulator. [Online]. Available: http : / /www.is i .edu/nsnam/ns/ [16] I E E E 802.11n T G n Sync, ' T G n Sync proposal M A C simulation methodology." 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 in adopting the I E E E 802.11 standards for high-speed wireless local area networks ( W L A N s ) . The original 802.11a/b/g standards provide a raw data rate of up to 54 Mbps. The recent 802.11e medium access control ( M A C ) protocol [1] provides quality-of-service (QoS) support v ia the Hybrid 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 in 802.lie-based W L A N s . In E D C A , the traffic is classified into four access categories (ACs) , 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 . Lin and V . W.S . Wong, "Cross-layer Design of MIMO-enabled W L A N s with Network Utility Maximization," in IEEE Transactions on Vehicviar Technology, 2008. Arbitrat ion Inter-Prame Space (AIFS) , transmission opportunity values, and minimum and maximum contention window (CW) sizes. Among 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 in order to improve the M A C efficiency [3]. B y using the multiple-input-multiple-output (MIMO) 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]. The spatial diversity gain is realized when the same information symbols are transmitted across different fading paths, in 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 i f 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 = -d. (5.2) 7-»oo log 7 For a point-to-point wireless link with MT transmit antennas and MR receive antennas, the maximal diversity gain is MTMR. The maximal spatial multiplexing gain is min{MT,Miî} . However, it is not possible to realize both maximal diversity gain and maximal spatial mult i - plexing 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 with 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. As 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 in W L A N s with M I M O channels. We formulate the cross-layer design as network util ity 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 in this chapter, the carrier sense multiple access with 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 Aloha M A C . For 802.11's C S M A / C A M A C , a centralized scheme is proposed with the access point being the centralized controller. For the slotted Aloha M A C , distributed algorithms are proposed. The contributions of this chapter are as follows: 1. For 802.11e W L A N s with 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 minimum contention window size at the M A C layer to achieve the maximal network utihty. 2. For the slotted Aloha 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 maximal network utility. B y using the dual decomposition method, we then propose a distributed algorithm NUM-D. We further propose another algorithm called NUM-S, which is also practical for implementa- tion. 3. Simulation results are presented to study the effectiveness of the proposed schemes. The U-MAC and D-MAC schemes are compared with the original 802.11e E D C A protocol under M I M O channels. Bo th 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 in this chapter. The comparison between our proposed algorithms is shown in Table 5.3. The rest of this chapter is organized as follows. Related work is summarized in 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 in Section 5.2. Section 5.3 proposes the system model NUM-0 for the slotted Aloha based W L A N , and its distributed solution NUM-D. Simulation results are presented in Section 5.4. A summary is given in Section 5.5. 5.1 Related Work 5.1.1 Related work on M I M O systems The traditional network protocol design has been following the layered architecture under the Internet five-layer reference model. Recent development in wireless networking has found that cross-layer design [8] can be used for performance optimization in a wireless communication paradigm due to the close coupUng of the characteristics in the physical layer with the perfor- mance in 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 MIMO-enabled M A C protocol was proposed in [9], where the protocol mitigates interferences by utilizing the multiplexing capability of the M E M O system. Another MIMO-enabled M A C protocol based on C S M A / C A in an ad-hoc network was proposed in [10], where the M A C layer schedules the transmission of different spatial streams by util izing the spatial multiplexing capability of the M I M O system. The impact of the spatial diversity of a M I M O system on the routing hop distance in an ad-hoc network was investigated in [11]. The M I M O antenna's spatial beamforming capability is utilized in [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. The adaptive routing protocol in [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. The transmission control protocol ( T C P ) over wireless M I M O channel is shown to perform better with 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 in the high S N R regions [14]. A U the cross-layer designs summarized above only focus on util izing 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 trade- off. Rezki et d. proposed a threshold-based adaptive encoding scheme which achieves the optimal diversity-multiplexing tradeoff [15]. The adaptive encoding scheme switches between several suboptimal encoding schemes with the help of limited channel feedback to the trans- mitter. 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 in a M I M O ad-hoc network by formulating the rate-rehability tradeoff problem as a network uti l ity 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 in advance. 5.1.2 Related work on network util ity maximizat ion The method of network uti l i ty maximization ( N U M ) has been shown to be an effective way of tackhng cross-layer optimization problems in wureless networks [18]. The utihty function for each source node in 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 util ity can give us opti- mal network performance parameters. When 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 in today's distributed networking environment. To formulate the 802.lie-based W L A N with 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 in 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 in the saturated condition (i.e., the transmission queue of every station is assumed to be always nonempty). This is a fundamental performance figure which indicates the stable l imit of the network throughput when the oflFered traffic load increases. Simulation studies [19-22] and experimental testbeds [23] have been constructed to analyze the through- put 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, Xiao [24] con- sidered 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 in 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 prob- abilities 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 in the util ity optimization problem. As a result, in 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 solu- tion. This 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. The 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 with an access point (AP) . Let denote the set of wireless stations. A c - cording to the E D C A specifications in the 802.11e standard, there can be up to four different classes of traffic wi th 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 in ACi and AC2, respectively. Each wheless station transmits one class of traffic, so the set of al l stations is N'i\JAf2. We use Ni, N2, and N to denote the number of stations in the set. Thus, Ni = 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. Estimation of the number of competing nodes in the network has been studied in [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 . Each 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 wi th 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 r , MR) [7]: d*{r) = {MT-r){MR-r), (5.4) where MT and MR are the number of transmit and receive antennas, respectively. In 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 in [17]: d{r) = {MT - r){MR -r), 0<r< m in (MT, MR). (5.5) This differentiable approximation is a lower boimd of (5.4), which gives a subset of the feasible diversity-multiplexing tradeoff region. Although this can potentially lead to a sub-optimal solu- tion of the problem due to the reduced tradeoff region, as analyzed in [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 l ink 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) = kcrslogjt (5.6) and (5.7) where kc and kp are positive constants for different coding schemes. The log function uses base 2 throughout this chapter. The multiplexing gain T S and diversity gain ds conform to the optimal tradeoff in (5.5). Then, the link transmission rehabihty ys is: 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 with 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 maximum network capacity. In this work, we base om: analysis on the saturation performance of the network. There are two causes of packet loss in an 802.11 W L A N . One is the packet collision where two nodes transmit simultaneously. The 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. Then, XsVs can approximately represent the effective throughput after further y, = l-fcp77'^('-») s e AT. (5.8) discarding the corrupted packets due to channel errors. This 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. Of all the elements listed above, we focus on studying the effects of the data rate Cs and the minimum contention window size Ws for station s in this chapter. The data rate with 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. This is the normal behavior in 802.11e. We call this M A C as the Uni f o rm-CW M A C or U-MAC. In the second case, we allow each wireless station to freely choose its own minimum contention window size without conforming to the same C W in its A C . We call this M A C as the Differentiated-CW M A C or D-MAC. Time 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. The probability for station s to transmit in a v ir tual time slot can be approximated as follows [32]: ^^=w~^' ^^-^^ where Wg is the minimum contention window size for station s. The 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 SEAT. (5.10) k€Af, k^s In tlie following subsections, we describe how to determine the throughput Xs for the two M A C schemes. 5.2.1 Saturat ion T h r o u g h p u t Analys is of the U - M A C Scheme For the U-MAC, TS and QS in (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 minimum 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 in [33]. The main difference here is that the wireless stations may use different data rates other than the uniform data rate assumed in [33]. The average length of one virtual time slot Ta for ACa (where a = 1,2) can be approximated as follows: To = :̂ =r—^ — + Thir + TsiFS + TACK + TAIFS + , . Taiot, a = 1,2, (5.11) where Thdr, TACK, 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 minimum contention window size of ACa- This 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. The 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: „ - 9a) , 0 rs 12^ ^" - (1 - qi/2)Ninn + (1 - q2/2)N2T2T2' The aggregated saturation throughput of all stations belonging to ACa is equal to VaL. The saturation throughput for station s in each A C can be calculated as follows: Xs = VaL V S G A / ; , a = 1,2. (5.13) The above equation shows that the individual saturation throughput of each station s in ACa is the weighted portion of VaL in proportion to its data rate c .̂ 5.2.2 Saturat ion T h r o u g h p u t Ansdysis of 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 with a single data rate, complicated multi-dimensional Markov chain and queueing models have to be used, which result in 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)^, se Ma, a = 1 , 2 , (5.14) where F is a positive scaling factor. Here, we assume that the two A C s have the same scaling factor. In 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 with X ŝg/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 ^ " . ^\Tsiot, a = 1.2, (5.15) l^keMa '^kCs -Na{Na + l) where we use the average contention window size X ŝeA/k ^s/Ma as an approximation of the identical contention window size modeled in [33]. Equation (5.14) states that the throughput of wireless station s is in proportion to its transmission probability T ^ , collision-free probabihty (1 - QS), and the average transmission rate of one payload by each ACa {L/Ta). This is a reasonable throughput approximation as the transmission and coUision probabilities of a station are the major factors influencing its throughput. The 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 U t i l i t y Formulat ion A commonly used family of uti l ity functions is as follows [34]: ( 1 - a ) - i a ; ( i - ° ) , if a G (0,1) U (l ,oo), Uix) = < (5.16) logx, if a = 1, where a is the fairness parameter. For example, if 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. When o; —> oo, max-min fairness can be achieved. In our N U M framework, we choose the utihty function for each wireless station s with 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 util ity function of ACa for a = 1 and 2. The 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 Framework for Cross-layer Design 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 MIMO-enabled 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 - M A C Wireless stations use the minimum contention window size of Wa in ACa- The N U M problem can be formulated as follows: subject to Q<xs< VaL^ V s e A/k, a = 1,2 ya < 2/3 < 1 - AvTr^^ ' ' " ' ' ' ^^^ ' ' " ' ' ' ^ VsGAfa, a = 1,2 0<rs< min(AfT, MR), V S € Wa<Wa<Wa, a = 1,2, (5.19) where Va is given by (5.12), and is a function of Wa, rs and other system parameters. The parameters ya, Wa and Wa are constant bounds on the variables, and should be selected within reasonable ranges. The above problem is a N U M problem with variables x, y , r and Wa- The saturation throughput from (5.13) is used as the upperbound for Xg- Although the objective function in (5.19) is concave, the constraint sets make this problem non-convex and challenging to solve. However, our tests wi th Matlab 's nonlinear optimization toolbox, using the sequential quadratic programming (SQP) method [35], show that this prob- lem formulation, under reasonable ranges of network parameters and init ial variable values, has no difficulty in converging to a unique solution. Results from Section 5.4 show that the number of iterations needed is in the range of 20 to 200. Note that due to non-convexity of the problem, the solution can be sub-optimal in the sense that a local instead of the global optimal solution is determined. When the hnk S N R values drop below certain levels, the problem may no longer have a feasible solution. Analytical ly 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 with the lowest SNRs wiU not satisfy the minimum QoS requirements. Two possible actions can be taken: reducing the QoS demand or disassociating those stations from the network. D - M A C W i t h each station s choosing its minimum 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 ya<ys<i-kp^7^^^""^^^''"''\ V s e A / a , a = 1,2 0<rs< min(MT, MR), V S e A/" Ws<Ws<Ws, V s e M, (5.20) where Wa and Ws are the lower and upper bounds of the contention window for station s, respectively. The variables T ^ , QS, and Ta are given in (5.9), (5.10) and (5.15). Note that for the constant parameter F , it ends up being a scahng factor r ^ ~ " in the objective function as defined by (5.18), and has no effect on the optimal solutions, which are the system's minimum contention window size Wg and the M E M O multiplexing gain r- .̂ The above problem is a N U M problem with variables x, y, r, and Wa- It can also be solved using standard algorithms for constrained nonlinear optimization problems as discussed in Section 5.2.4. W i t h the above U-MAC and D-MAC formulation, the A P in an 802.11e W L A N can coUect each wireless station's hnk S N R , select a P with appropriate network revenue models, and solve either (5.19) or (5.20) to obtain the M I M O multiplexing gain TS and minimum contention window size Wg for each station. The resulting Vg and Wg values can be sent out in 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 Aloha M A C . The N U M formulation can be transformed to a separable convex optimization problem, and a distributed algorithm can be derived accord- ingly. For the slotted Aloha, we can obtain the throughput formulation without assuming the saturated conditions. When source node s transmits with persistent probability ps in slotted Aloha, its throughput is: The 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 real- time traffic with constant-bit-rate ( C B R ) flows, which has a hard throughput requirement R and reliabiUty demand Q: R<Xj<x = kcrlog'j, j e A/2, Q < Vj < 1, 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. The 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 in the problem formulation. The ACi traffic is best-effort traffic, and also has the bounding constraints: xi <Xi<x, i G A/i, y i < 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 U t i l i t y Formulat ion To differentiate the different QoS requirement of ACi and AC2, we use the utihty function of (5.16) wi th a > 1, and extend it to include a normalizing denominator. Thus, the utihty function for the wireless stations with ACi traffic is as follows: where the product x^i/i can be interpreted as the effective throughput for the best-effort station i G M - For the C B R traffic in AC2, the util ity function is chosen to be a function of the rehability only, because we expect that the throughput x wi l l satisfy the C B R traffic's throughput demand i î as in (5.22); however, further increasing a C B R traffic's throughput provisioning usually does not provide additional performance gains: The utihty functions in (5.24) and (5.25) are normalized such that Ui{xi,yi) = U2{Q) = 0 and Ui{x,l) = f /2(l) = 1- This avoids the apparent problem of combining two util ity functions. which would otherwise have a few magnitude of difference in value. The network util ity 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 ACa ' s utihties on the network util ity 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 Design Centralized Scheme: NUM-O We now present the centralized N U M formulation for the slotted Aloha 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 with cross-layer information from the MIMO-enabled physical layer, we propose the foUowing utihty maximization formulation: E 0Ui{xi,yi) + 5] (1 - 0)U2{yj) subject to Xs < kcrs log(7s)Ps J][ (1 - Pk), \/s e Af k€^J\{s} < 1 - fcp7r^^''~'''^^^''~'''\ V s G ^1 < a;i < X, V i G M R<Xj<X, y i < 2/i < 1, V i G M Q < y j < l , V j G A A a 0 < r-a < m i n ( M r , M f l ) , V s G A/" 0 < < 1, V s G AA. (5.27) Problem (5.27) is a non-linear optimization problem with 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. We perform a log transformation of variables: x's = l o g X s , p ^ = logps and = log( l - ps) for s G A/" by taking log on both sides of the first constraint. The N U M problem becomes: subject to : x'^ - log kc - log - log(log 7 )̂ - p'^ - E Pfc ^ 0- V s € A/" fc6Ar\{s} ys - 1 + fcp77(^^-^»)(^«-'-») < 0, V s G e P ' » + e P " < l , V s e A A l o g x i < X- < logX, V Î e A / i log i î < Xj- < logx, V j e ATa y i < 2/i < 1, V i e A / i Q < 2 / j < l , V j e A / - 2 0 < r s < A „ p ; , p ' ; < 0 , V s e A A (5.28) A , = min { m i n { M r , M n } , Ml+M^ _ ^ y ^ } , (5.29) where and The above problem is a convex optimization problem. The detailed proof of convexity is included in the Appendix. 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). This constraint can reduce r^'s range of values in 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 T S is reduced from [0,2] in (5.27) to [0,1.993] in (5.29). When 7s is higher than 8 d B , there is no longer any difference between the formulations in (5.27) and (5.28). As a result, we can expect that the transformed convex formulation (5.28) would obtain the same optimal solution as before the variable transformation in most cases. The possibihty of obtaining sub-optimal solutions in some low S N R cases is a trade-off in order to formulate the problem as a convex optimization problem. In a W L A N where aU the wireless stations communicate with the A P directly, the A P can measure the S N R (7^) of each l ink 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 ia piggyback on the control frames. Each station wi l l then tune its operating parameters accordingly. Furthermore, the A P can adjust the parameter /3 in the network util ity 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 SNRs are too low. We may either reduce the QoS demand or disassociating weak stations from the network to reach a feasible solution. Distributed Scheme NUM-D The NUM-0 problem proposed in (5.27) is a centrahzed scheme, where the A P acts as the central controller and distributes the control information to each wireless station. This 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 ^ U i ) + E " ' ^ ) ^ 2 (y j ) I \ + 5]̂  A , logfcc + logrs + l o g ( l o g 7 s ) + p ; + Pk-^'s seM \ kçM\{s} J + Yf^s(}-ys- A:p77(^^-'--)(^«-'-»)) (5.31) The Lagrange dual function is: $(A, /x) = max L (x', y, r , p', p". A, / i ) (5.32) x',y,r,p',p" where x', y, r, p', p" axe subject to the third to the ninth constraints of (5.28). The 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 sub- problems. The maximization of the Lagrangian over x', y, r , p', p" can be conducted in parallel at the application layer for the target throughput x' and reliabihty y: max Yl 2/») + E (1 - /5)^2(yi) - E (>'^< + ^ 2̂/̂ ) ieMi jeUi aeAf subject to l o g x i < < logx, V i E A / i log R<x'j< logx, V j G A/i? y i < yi < 1, V i G A / i Q<yj<l, V j G A T a (5.34) which is optimized over x' and y. 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/" 0 < r , < A , V S G A T V s G AT, (5.35) which is optimized over p and r . The above problem can be separately solved at each wireless station locally. For i G A / i wi th ACi traffic, it solves the following problem to obtain its target x[ and yi values: max PUiix'i,yi) - (AjX- + /Xij/i) subject to log x i < X • < log x. Î/1 < yi < 1, (5.36) which is optimized over x^ and yi. For station j G A/2 with AC2 traffic, its target Xj and yj values can be calculated from: max (1 - P)U2iyj) - (Xjx'j + p.jyj) subject to logR < x'j < logx, Q < yi < 1, (5.37) which is optimized over x'j and yj. 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 , - fMskp-y;^^^'^'^'-^''-^'') subject to 0 < rs < A . (5.38) FVom (5.35), since EseAf >^s {p's + EksA/\{s} P'k) = E.eAT (a.P^ + Efc6Ar\W f̂eP '̂) ' transmission probability p can be solved at each wireless station s by: max Xsp's-\- J2 ^kPs subject to ê '" + ^ ' < 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) = / \ 1 + Xsit) - Sit) ,(5.40) log rs +p's+ Y Pk + kc + log log js - x's fis{t + l) = [^is{t)-5{t)(l-ys-kp^:^''^-''^^''''-''^)Y, (5.41) where [a;]"'" = max(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 with 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 in each iteration can be piggybacked over a broadcast frame by each station. Thus, it introduces limited overhead in the network. Another advantage of the distributed solution is that the computation complexity is reduced compared with the centralized scheme. This 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. The 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 : U t i l i t y - M a x i m i z a t i o n wi th Separated P H Y / M A C Layers For performance analysis, we propose a simpUfied scheme in 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 in 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 with each node transmitting with persistent probability [40]: where N = \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 Ps = l/N, seJ\f, (5.42) (5.21): RN^ 3 e J^2- (5.43) fee l o g 7 i ( A r - 1 ) ^ - 1 ' The value rj is the minimum 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. This maximum diversity gain dj in turn provides the maximum reliability yj available for station j as from (5.8). Because the util ity function (5.25) is strictly increasing with yj, this multiplexing-diversity tradeoff maximizes the util ity for AC2 stations. For the ACi stations, maximizing Ui (xy) in (5.30) is equivalent to maximizing xy because it is strictly increasing wi th xy. We can solve the optimal multiplexing gain for each AC-y station i E M\ w i th the following simple constrained maximization problem: max , , , , ( T V - 1 ) ^ - 1 fccrilog(7i)^^ (l-K^-'^'-'^), (N - 1 ) ^ - 1 subject to x i < A;crtlog(7i) < x, y i < 1 - fcp7r'^^''*^ < 1. din) = (MT - ri){MR - n), 0 < Ti < min (MT, MR). (5.44) The solution of problem (5.44) provides each AC\ station with 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 util ity from (5.28) to compare with the NUM-D scheme. This scheme divides the network util ity maximization problem into two steps. The 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 util ity because it does not consider adapting the M A C layer parameters to the physical layer schemes. 5.4 Performance Evaluation 5.4.1 Results 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 in this chapter. The simulation parameters are shown in Table 5.4. We consider a W L A N with 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. That is 7t = 71+5 (for i = 1 , . . . ,5). Each 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 wil l likely lead to no feasible solution for the optimization problem, we set a lower S N R bound of 3 d B . This setup tries to simulate a W L A N with wireless stations randomly located within certain distances from the A P . Other assumptions such as uniformly distributed SNRs 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 SNR's distributions. A n d our tests also show that similar performance trends are observed under differently simulated SNRs. Thus, only results from the Gaussian distributed SNRs are presented. For U-MAC and D-MAC, the following parameters are used: kc = 20 M H z , kp = 0.15, M r = 2, MR = 3, Ws =Wa = 7, Ws = Wa = 1023, a = 1.1, yi = 0.7, y2 = 0.85, and r = 1. W i t h a maximum of five retransmissions, the maximum contention window size is set to be 2^ = 32 times the minimum contention window size. The 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 util ity 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 ACa ' 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. The throughput is calculated as the end-to-end network throughput above the M A C layer, which is the number of bits transmitted in the transport layer protocol data unit (PDU) 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 . The multiplexing gain Vs of wireless station s is chosen without the cross-layer optimization as done in 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 with its channel S N R 7 .̂ We wi l l study the effectiveness of the tuning 0 on the traffic QoS differentiation. The network total utihty is used to evaluate the effectiveness of the schemes in achieving better uti l ity 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 with /3, and are drawn as a horizontal line i n the figure to be used as a performance comparison basehne. The medium access delay is shown in Figiure 5.1(b). As we would expect, an increase in P decreases the priority differentiation between the two A C s . When /? reaches 0.5, ACi and AC2 reach equal priority and liave comparable performances. The network uti l ity is shown in Figure 5.2. Although the 802. l ie 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 util ity decreases sharply when the utihty function demands less traffic differentiation by increasing the P value. From the simulation results, we can observe that the adaptive U-MAC and D-MAC schemes have good flexibility in 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 in every per- formance measure because they jointly adapt the minimum 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 in Section 5.2 are reasonable and sound. We can also observe that the U-MAC slightly outperforms the D-MAC, even though D- MAC allows the extra flexibility of letting each station have its own Ws parameter. The cause for this is from the coarse approximation we made in the throughput model for D- MAC, 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 minimum contention window sizes may be suflBicient to provide good performance gain in 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 in Tables 5.5 and 5.6. Ten wireless stations axe also used in the tests. The Unk S N R values 7i = 7̂ +5 (for i = 1 , . . . ,5) axe set at increasing values (from 6 d B to 10 dB) 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 D-MAC slightly under-performs U-MAC. Prom these two tables, we can see that the D-MAC tends to use a smaller contention window size than the U-MAC model, which is likely the cause for the performance loss. A more accurate throughput model for D-MAC wi l l be needed for improving this performance gap. 5.4.2 Results for Slotted A l o h a M A C The slotted A loha schemes NUM-D and NUM-S axe studied with numerical tests in Matlab. The following parameters are used: x = 0.01 Mbps, 7 = 30 dB, Q = 0.85, and the other parameters use the same values as in Section 5.4.1. The 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 Utility Function First , we examine the effectiveness of the network utUity function (5.26) in determining the tradeoff between the throughput of ACi and the reliabiUty of AC2. We vary the parameter P from 0.6 to 1 wi th a step size of 0.05, and solve problem (5.28). We also use the Gaussian distributed random variable with a mean value of 7^ and a variance of 7^ to generate the S N R values in simulations. The results for ATi = ATa = 5, 7m = 8 dB, = 0.57m, and varying R axe shown in Figure 5.3. The throughput is calculated from (5.21) which is the throughput for transmitting the M A C layer protocol data unit (PDU) (including M A C frame headers). We can see that for a smaller P, the throughput in ACi is given lower priority, but the network achieves higher rehability for the AC2 traffic. As P increases, the throughput in ACi significantly increases at the price of decreasing reliability on AC2 traffic. The Eirea below each curve is effectively the achievable throughput-rehabihty region for a specified R. When 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 in 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 Number of Stations In this experiment, 7^ is fixed at 8 dB , and 7^ = 0.57,„. We vary the number of stations in each A C from 1 to 5. R is set at 1.5 Mbps. The resulting network utihty, the throughput ACi and rehabihty performance in AC2 are shown in Figures 5.4 to 5.6. When the number of stations is small, the NUM-D scheme achieves much higher ACi throughput than NUM-S. When the number of stations increases, the performance gain on ACi's throughput by NUM-D diminishes. But 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. The networit average 7^ varies from 6 dB to 16 d B , 7u = 0.57m. R is equal to 1.0 Mbps. Figures 5.7 to 5.9 show the network utility, ACis throughput and ACa 's reliability achieved with these two schemes. Results show that in 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 achieves significantly higher throughput than NUM-S and also maintains ACa 's rehability greater than 99%. As 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 with pre-determined S N R values in Table 5.7. We can see that the solutions provide the required 1 Mbps throughput for the AC2 traffic with good reliability. The best-effort ACi traffic tends to use higher a multiplexing gain rs to achieve a higher data rate. The stations with higher S N R links can use a higher multiplexing gain and lower transmission probabihty to achieve the required Hnk rehability and throughput. The 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 This chapter proposed a M A C / P H Y cross-layer design with network uti l ity maximization in a W L A N with multiple classes of traffic. Two 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 minimum contention window size at the M A C layer is jointly optimized with the multiplexing-diversity gain tradeoff at the physical layer wi th M I M O antennas. The utility-based cross-layer design is shown to be flexible in adjusting the system performance in regard to QoS tradeoff for different access categories of traffic. We further analyzed the slotted Aloha M A C using the N U M approach as weU, and were able to derive distributed solutions with 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 in 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 matrix of C\{e'''y)^ " is: H = V^Ciie-'yf ( l - a ) V - " ( 1 - « ) V " (1 - a)2y-" -a{\ - a)y-°'-'^ = Cie (5.45) For any non-zero vector z = [zi Z2] and a > 1, we have: z H z ^ = C i ( l - a ) e ( i - " ) ^ ' y - " - i [(1 - a){yzi + z^f - zl] < 0 (5.46) which shows that H is negative definite. As a result, the uti l ity function U{{x',y) is a concave function of {x', y}. Please note that we require a > 1 for the above concavity proof. • 5 .6 .2 P r o o f o f c o n v e x i t y o f t h e c o n s t r a i n t s For a convex optimization problem, its equahty constraints should be affine, and the function / ( x ) in the inequality constraint f{x) < 0 should be convex. It is easy to see that the first constraint in (5.28) is affine. For the second constraint, in order for the function w{rs) = -y~(^r~''')(^«~'"") to be convex, it is required that: w{rs) = ^-(^r-r,)iMR-rs) ^(^^ + MR - 2rsf h i 7 , - 2] In7 , > 0. (5.47) This gives an upper bound of r^, which is refiected in (5.29). The third constraint is relaxed from the equality constraint (e^» -|- e^' = 1) to an inequality constraint. The main concern is that a non-linear equahty constraint makes the problem non- convex. 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 l imit 1. A n increase in p'g or p" wi l l lead to relaxing the first constraint, which in turn may lead to higher x'^, resulting in 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 - Part I Notation Parameter Definition a Uti l i ty 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 in 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 M Set of all mobile stations M , M Set of mobile stations in ACi and AC2, respectively N Total number of mobile stations Ni,N2 Total number of mobile stations in ACi and AC2, respectively Ps Transmission probabihty in slotted Aloha for station s Qs Collision probability of a transmitted frame by station s in 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 in ACa (0 = 1,2) Va Average number of collision-free transmissions from ACa per second Wa M i n i m u m contention window size for ACa Wa,Wa Lower and upper bounds of Wa, respectively Ws M i n i m u m contention window size of station s Ws,Ws Lower and upper bounds of Ws for station s, respectively Xs Throughput of station s X Throughput upper bound in slotted Aloha Xl Lower bound of A C i ' s throughput in slotted Aloha 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 M A C Input Parameters Variables Output Solutions Comments U-MAC Centralized C S M A / C A MT, MR, a, /3, N, L kc, kp, 7, Thdr, TACK Tsiot, TSIFS, TAIFS X , y , r, Wa P H Y : r M A C : Wa Uniform C W for each AC. D-MAC Centralized C S M A / C A MT, MR, a, p, M, L kc, kp, 7 , Thdr, TACK Tsiot, TSIFS, TAIFS X , y , r, Ws P H Y : r M A C : Ws DiJHferentiated C W for each station. NUM-0 Centralized Slotted Aloha MT, MR, a, P, M kc, kp, 7) P X , y , r, p P H Y : r M A C : p Centrahzed N U M formulation. NUM-D Distributed Slotted Aloha MT, MR, a, P, M kc, kp, 7) P x ' , y , r P', P", A, n P H Y : r M A C : p Distributed solution for NUM-0. NUM-S Distributed Slotted Aloha MT, MR, a, P, M kc, kp, 7, R X , y , r, p P H Y : r M A C : p Simplified scheme as performance baseline. T a b l e 5.4: I E E E 802.11n Simulation Parameters Basic Rate 10 Mbps Maximum Data Rate 80 Mbps 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 Data Packet Size 1000 bytes Time Slot 9 fj.s SIFS 10 fj,s A I F S 28 (XS Maximum Number of Retransmissions 5 T a b l e 5.5: N U M Solution for the U - M A C Scheme. ACi AC2 Station s 1 2 3 4 5 6 7 8 9 10 P 7s 6 d B 7 d B 8 d B 9 d B 10 dB 6 d B 7 d B 8 d B 9 d B 10 dB 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 AC2 Station s 1 2 3 4 5 6 7 8 9 10 Is 6 d B 7 d B 8 d B 9 d B 10 d B 6 d B 7 d B 8 d B 9 d B 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 6 d B 7 d B 8 d B 9 d B 10 dB 6 d B 7 d B 8 d B 9 dB 10 dB 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. -46- 1 I- -I 1 1 p 1 1 1 -47- • • ^ -48- 0 1 -50- Z -51- - - • - U-MAC - - A - - D - M A C ••-802.11 • -52- 1 0.1 ' 1 0.2 • 1 0.3 0.4 0.5 p F i g u r e 5.2: Network util ity of U - M A C and D - M A C versus 0. 0.84-J 1 . 1 , 1 , 1 1.0 1.5 2.0 2.5 Average Throughput for A C , (Mbps) F i g u r e 5.3: The tradeoff between throughput and rehabihty for slotted Aloha. 3.0 Number of Wireless Stations in Each AC F i g u r e 5.4: Slotted Aloha - Network util ity versus the number of wireless stations. Number of Wireless Stations in Each AC F i g u r e 5.5: Slotted Aloha - Average throughput for best-effort traffic with different number of wireless stations. 1.0-1 in 1 CO < 0.8-1 — r - 0.7- a> 0.6- 2 ^ 0.5- -•-NUM-D - ••- NUM-S V - -T • 1 • 1 " 1 ' 1 2 3 4 ! Number of Wireless Stations in Each AC F i g u r e 5.6: Slotted Aloha - Average rehability for real-time traffic with different number of wireless stations. 7. (dB) F i g u r e 5.8: Slotted Aloha - Average throughput for best-effort traiBc with different SNR. T 1 1 1 1 1 1 ' T 6 ' 8 ' 10 ' 12 ' 14 ' ?6 7. (dB) F i g u r e 5.9: Slotted Aloha - Average rehability for real-time traffic with different SNR. 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 . Cah, M . Conti , and E . Gregori, "Dynamic tuning of the I E E E 802.11 protocol to achieve a theoretical throughput l imit , " IEEE/ACM Trans. Networking, vol. 8, no. 6, pp. 785-799, Dec. 2000. [4] A . J . Paulra j , D . A . Gore, R. U . Nabar, and H . Bolcskei, " A n overview of M I M O commu- nications - 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," May 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 in multiple-antenna channels," IEEE Trans. Inform. Theory, vol. 49, no. 5, pp. 1073-1096, May 2003. [8] X . L i n , N . Shroff, and R. Srikant, " A tutorial on cross-layer optimization in whreless net- works," IEEE J. Select. Areas Commun., vol. 24, no. 8, pp. 1452-1463, Aug . 2006. [9] M . Paxk, S. Choi , and S. M . Nettles, "Cross-layer M A C design for wireless networks using M E M O , " in Proc. of IEEE Globecom, St. Louis, M O , Nov. 2005. [10] K . Sundaresan, R. Sivakumar, M . A . Ingram, and T . Chang, "Medium access control in ad hoc networks with M I M O links: optimization considerations and algorithms," IEEE Trans. Mobile 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 in ad hoc networks: a holistic perspective," in Proc. of IEEE Workshop on High Performance Switching and Routing, Hong Kong, China, May 2005. . [12] J . -S . Park, A . Nandan, M . Gerla, and H . Lee, " S P A C E - M A C : Enabling spatial reuse using M I M O channel-aware M A C , " in Proc. of IEEE ICC, Seoul, Korea, M a y 2005. [13] K . Sundaresan and R. Sivakumar, "Routing in ad-hoc networks with M I M O links," in 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 with A R Q and packet combining," IEEE Trans. Mobile Comput, vol. 5, no. 3, pp. 208-223, Mar . 2006. [15] Z. Rezki , D . Haccoun, and P. Gagnon, " A threshold-based adaptive encoding for achiev- ing the diversity-multiplexing tradeoff," in Proc. of IEEE Intl Symposium on Wireless Communication Systems, Siena, Italy, Sept. 2005. [16] H . - F . L u and P. Kumar , " A unified construction of space-time codes with optimal rate- diversity 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 rate- rehability tradeoff in 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 de- composition: A mathematical theory of network architectures," Proc. of the IEEE, vol. 95, no. 1, pp. 255-312, Jan. 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. 223- 235, June 2003. [20] S. Choi , 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 , " in Proc. of IEEE VTC, Jeju, Korea, Apr . 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 . Xiao , "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. [25] Z. Kong , D . H . K . Tsang, and B . Bensaou, "Performance analysis of I E E E 802.11e contention-based channel access," IEEE J. Select. Areas Commun., 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," in Proc. of IEEE Globecom, Dallas, Texas, Nov. 2004. [28] Y . Ge and J . Hou, " A n analytical model for service differentiation in I E E E 802.11," in 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 Trans. Mobile Comput, vol. 5, no. 9, pp. 1283-1296, Sept. 2006. [30] G . Bianchi and I. Tinnirello, "Ka lman filter estimation of the number of competing termi- nals in an I E E E 802.11 network," in Proc. of IEEE INFOCOM, San Francisco, C A , Mar . • 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 J. Select Areas Commun., vol. 21, no. 3, pp. 281-302, Apr . 2003. [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 , " in 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," in Proc. of IEEE WCNC, Las Vegas, Nevada, Apr . 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. Conn, N . I. M . Gould, and P. L . Toint, Trust-region Methods. Society for Industrial . Mathematics, 2000. [36] D . P. Bertsekas, Nonlinear Programming, 2nd ed. Athena 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, Aug . 2006. [38] N . Z. Shor, Minimization methods for non-differentiable functions. Springer, 1985. [39] D . P. Bertsekas, Convex Analysis and Optimization. Athena Scientific, 2003. [40] D . Bertsekas and R. Gallager, Data networks, 2nd ed. Prentice Hal l , 1992. [41] Ns-2 simulator. [Online]. Available: http : / /www.is i .edu/nsnam/ns / Chapter 6 Cooperative M A C and Routing Protocols Design for Wireless Ad-hoc Networks ^ Due to the impairments in the wireless channels, signal transmission through the wireless prop- agation 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 in 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 . Lin, J . Song, and V . W.S. Wong, "Cooperative M A C and Routing Protocols Design for Wireless Ad-hoc Networks," in ACM/Springer Mobile Networks and Applications Journal, 2008 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. The 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 in wireless terminals. Mult ip le 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 pro- posed. The 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 estab- lishment 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 in an ad-hoc network. 4. Simulation results show signifiicant performance gains on delay and throughput by the proposed cooperative relay design. The 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 in Section 6.4. 6.1 Related Work In recent years, several cooperative diversity schemes for the virtual M I M O system in wireless ad-hoc networks have been studied from the information theory and physical layer design's perspective [1-6]. The basic cooperative diversity scheme works on a single-relay channel as shown in 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). The performance benefits of utihzing the cooperative relaying has been weU studied in the physical layer models which generally focus on the performance of the outage probability and average error probabihty [1-5]. The 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 in physical relay models, the medium access control ( M A C ) and routing protocols need to be modified in order to fully utihze the diversity gain provided by the coop- erative relaying. A slotted Aloha based cooperative M A C protocol is proposed in [8] with the decode-and-forward relay. Mini-slots are used in each transmission time slot to accommodate the need for selection and utilization of relays. Higher throughput and lower delay performance is observed compared with the original slotted Aloha M A C protocol. A cooperative diversity M A C based on the 802.11 carrier sense multiple access with colhsion avoidance ( C S M A / C A ) protocol is proposed in [9]. The 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 with 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 in [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 in 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 with cooperative considerations are also proposed recently. In [11] and [12], cooperative transmission is incorporated in route selection in wireless ad-hoc networks to improve the power consumption performance. The Co-Operative Diversity Enhanced A d hoc Network ( C O D E A N ) protocol is proposed in [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. They are based on the distributed carrier-sensing M A C protocols used in 802.11. This 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 in the literature. A system framework with similar design structure as ours is proposed in [14], where a comprehensive scheme across the physical, M A C and network layers is proposed for cooperative transmission in ad-hoc networks. In their work, only space-time coding is considered at the physical layer. A primary route path is constructed using the dynamic source routing (DSR), and the relay nodes are selected at the M A C layer with an extensively modified 802.11 D C F protocol where pilot tones are inserted after R T S frame transmission for channel estimation. Compared with [14], the proposed scheme in 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 in the proposed scheme in [14], because pilot tones are assumed to be transmitted orthogonally in time where a node decides when to transmit based on its assigned globally unique ID. This introduces extra system management cost and the risk of pilot tone colhsion in 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 data frames when constructing the relay topology. C R P is simple to implement in the existing wireless ad-hoc networks. This design also breaks the tight couphng between M A C and network layers in [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 with N wireless stations. Each station has one single antenna. The physical layer model is presented in Section 6.2.1. Two cooperative techniques are considered at the physical layer: repetition coding with maximal ratio combining ( M R C ) , and space-time coding (STC) . The cooperative M A C protocols proposed in Section 6.2.2 utihze relay nodes to assist the transmission of data traffic between source and destination nodes with cooperative relaying. For end-to-end transfer of data packets, a multi-hop routing path is determined with the cooperative routing protocol (CRP) proposed in 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 in 802.11-based networks. A n enhanced routing protocol is further proposed in Section 6.2.4, which uses S N R threshold to effectively combat the gray zone effect. 6.2.1 P h y s i c a l Layer M o d e l We study a wireless ad-hoc network under a slow Rayleigh fading channel. The received in - stantaneous S N R 7 with 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- 7 = l O l o g i o T T . (6.2) The 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 in meters, and n is the path loss exponent, respectively. The value of n typicaUy ranges from 2 in a free space environment to 6 in 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 coop- erative relaying, where no node can receive and transmit at the same time. This 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 Data Unit ) . In this chapter, we choose the basic rate to be 1 Mbps, and assume an M C S with a binary phase shift keying ( B P S K ) modulation with a convolutional code and Viterb i decoding. Using the rate 1/2 convolutional code with the octal generators 133/171, the bit error rate ( B E R ) perfor- mance of this M C S with an instantaneous S N R 7 can be approximated using its lower bound performance [21]: (6.4) where dfree = 10 is the the minimum free distance of the code. The Q{.) function is defined as: We choose the data rate to be 11 Mbps, 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]: 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 in our proposed cooperative M A C and routing protocols. A s most M C S s used in 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 with empirical tests and summarized in look-up tables. Our approach of using the closed-form expressions of the bit error performance in (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 Mbps. A l l control and broadcast frames are transmitted in a basic rate of 1 Mbps 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 with 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 in Figure (6.5) (6.6) 6.1(b) where n = 2. The mechanisms to select the relays are incorporated into the M A C and routing protocols, and wi l l be discussed in detail in Sections 6.2.2 and 6.2.3. Here, we focus on the physical layer model of the cooperative relaying scheme. Two 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. The received frame's successful decoding depends on two factors: the preamble at the basic rate and M P D U at the data rate. Their 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 (CRC) for either the preamble or the M P D U ) , the relay wiU discard the frame. If the frame decoding is successful, the relay wi l l transmit the frame to the destination in its assigned relay time slot. The relay transmission time for Ri and i?2 is decided in advance with the help of the cooperative M A C protocol. It assures that two relays wi l l 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 . The 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.) ) , (6.7) Pd^tT = 1 - ( l - 0.75Q (V0.8(7s + 7 H i + 7 H . ) ) ) ' , (6-8) where 75, 7̂ 1 and •yR^ are the instantaneous SNRs of the received frames at the destination from source S, and relays Ri, R2, respectively. This is the B E R with the particular fading realization to be used in our simulations. 2) Space-time coding (STC): The two relays follow similar decode-and-forward process as in M R C . The main difference is that they wi 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. The 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 wi th space-time coding. We utilize the widely used Alamouti scheme [24] on the 2 by 1 multiple-input-single-output (MISO) relay channel from the relays Ri and R2 to D. The S N R for the effective S T C channel is the sum of the two relay frames' SNRs [25]. This signal can be combined with 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 (\/20(7.+ 7^1+7^2)) , (6.9) and Pd^ta - 1 - (1 - 0.75Q ( v / 0 . 8 ( 7 . + 7 R x + 7 R . ) ) ) ' • (6-10) 6 .2 .2 M A C P r o t o c o l D e s i g n We extend the C S M A / C A M A C protocol for 802.11-based W L A N s to support cooperative relaying. The 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 with M R C at the physical layer. The t iming sequence of the M R C - M A C is shown in Figiure 6.2. The control frames R T S , clear-to-send (CTS) , and acknowledgement ( 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 wi l l be discussed in 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. The 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. When a node receives a data frame with its M A C address contained in 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 in its allocated relay time slot. For the relay node with its M A C address contained in the data frame's MAC-R\ or MAC-R2 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 in Figure 6.2. If the relay node's decoding of the data frame fails, it wi l l remain silent during its allocated transmission time slot. The 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 wi l l decode received frames with 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 wi l l defer for extended inter-frame space (EIFS) and resume normal operation. 2) STC-MAC: S T C - M A C is the M A C extension to support space-time coding. The timing sequence is shown in Figure 6.3. Its operation is similar to the M R C - M A C , except that the two relays wiU both 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. The destination node wiU receive the data frame in 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 wil l reply wi th an A C K frame to the sender. 6.2.3 Cooperat ive R o u t i n g P r o t o c o l 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 in wireless ad-hoc networks. One important new feature in C R P is the discovery and maintenance of relaying nodes. To incor- porate this routing feature, C R P includes two new components in 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 in the two-hop neighborhood table. The H E L L O message in 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. Upon receiving a H E L L O message, each node updates its two-hop neighborhood table. The 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. The H E L L O message is broadcast by each node every second. 2) Relay Selection: The end-to-end routing path is established using the route discovery mechanisms of A O D V with the route request and route reply ( R R E Q / R R E P ) control frames. We expand the routing table with 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. The 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 in 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 = min [SNR{i, x) , SNR{x,j)]. (6.11) 3. Sort r]x for al l x. The two nodes associated with the two highest rjx values are selected as Ri and R2, respectively. This algorithm eflFectively chooses two nodes which are common immediate neighbors of both i and j, and having the two highest of the minimum S N R of the relay channels (from i to relay, and relay to j). This effectively avoids selecting relays which have a weak link with either the sender i or the receiver j. 6.2.4 E n h a n c e d C R P The C R P protocol proposed in the previous section can enhance the wireless conununcation compared with the original A O D V . However, the C R P protocol stil l suffers from the well- known gray zone problem of A O D V in an 802.11 network [16, 17]. This phenomenon stems from the large difference in B E R performance between M C S s used by the basic rate and data rate transmission. The 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 in 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 in 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. When a node maintains its two-hop neighborhood table, the received H E L L O packet's average S N R is recorded with a moving average. The H E L L O packet's sovuce node wi l l be added as an immediate neighbor in 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 wi l l be subject to the filtering by the neighborhood table. A broadcast packet wi l l be dropped if its source is not recorded as the receiving node's immediate neighbor despite a possible successful reception. The appropriate 70 threshold should be set such that it pro- vides 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. The following new modules are implemented in the ns-2 simulator: the fading channel and the physical error model, the cooperative M A C and routing protocols proposed in Section 6.2. The system parameters used in the simulation are hsted in Table 6.1. 6.3.1 Linear Topology Test A hnear topology with 10 nodes forming a 3-hop route between the source S and destination D is shown in 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. A 100 kbps constant bit rate ( C B R ) traffic flow is transmitted from S to D. The 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 in each hop with the M R C - M A C or the S T C - M A C . The packet delivery ratio of the network under cooperative relaying is compared with the original 802.11 M A C where no relays are utihzed. The results for the C B R packet dehvery ratio and the end-to-end delay are shown in 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 . The cooperative M A C s maintains the delivery ratio above 99% while the hop distance increases to 140 m. However, wi th 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. This 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 wi th 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 in Figure 6.6. The 802.11 M A C has better performance when the distance is shorter than 80 m. This is because within such a short distance, the l ink 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. But S T C - M A C requires more enhanced signal processing capabilities in wireless stations. 6.3.2 R a n d o m Topology Test To fu l ly test the C R P protocol, we carry out a random topology test in 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 in 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-CRP/cooperat ive M A C with the AODV/802 .11 M A C . The results for C R P without the enhancement for gray zone reduction are shown in Figure 6.7. The results for E - C R P are shown in 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 with gray zone reduction for the tests with E - C R P in 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). This is the distance where the gray zone effects begin to show up from Figs. 6.5 and 6.6 in the hnear topology tests. E - C R P showed a performance gain of ajound 20% to 30% compared with C R P without gray zone reduction. The delivery ratio and delay performance slightly dechnes with 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 with A O D V . S T C - M A C also out-performs M R C - M A C with the gains from its reduced channel access time, which in turn 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 with the number of retransmissions to be equal to 4. The average B E R of the link varies from 10~^ to 10~^. The resulting packet delivery ratio versus the B E R is shown in 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 in 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. This 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 in equations (6.7) to (6.10). Simulation tests are also carried out for T C P flows. The number of T C P flows in the network increases from 1 to 5. The total throughput under the different M A C and routing schemes with or without the gray zone reduction enhancement are shown in Figs. 6.10 and 6.11, respectively. The throughput under the cooperative M A C s with E - C R P shows the highest performance gain. The 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. When the number of flows increases, S T C - M A C ' s performance gain over M R C - M A C increases. This is mainly due to increased medium access contention in the network with increasing number of traffic flows. S T C - M A C ' s reduced medium time shows its advantage in 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 maximal 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 with the two cooperative M A C protocols. T a b l e 6.1: Simulation Parameters Basic Rate 1 Mbps Data Rate 11 Mbps Transmission Power 100 m W M i n i m u m Contention Window Size 31 Max imum 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 Data Packet Size 1000 bytes Time 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 T C P S A C K (b) Multiple relays scenario. F i g u r e 6.1: Two different cooperative diversity scenarios. Busy DIPS • - • - ^ "TTO SEFS ^airo RTS ^ ow o air 0 D A T A CTS A C K iSIFS D A T A _ R l DATA_R2 F i g u r e 6.2: M R C - M A C timing sequence. Busy r»TFQ QTFP SIFS -4—^ RTS -i-^ D A T A ^ CTS A C K D A T A _ R i 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. 1' 0 1 0.8 I 0 0.6 1 TO 0.4 Q L CQ ^ 0.2 —T 1 1 • s X \ ; - S \ m \ \ \ \ STC-MAC \ \ MRC-MAC \ • -•-802.11 \ \ J 1 y 60 80 100 120 140 ' 160 d (meters) (a) Packet delivery ratio for C B R traffic. 0.1 0.08 0) (0 « 0.06 C <û 0 0.04 1 •a c LU 0.02 - • -802.11 ^ MRC-MAC - • - S T C - M A C 60 80 100 120 140 160 d (meters) (b) End-to-end delay for C B R traffic. F i g u r e 6.5: Linear topology tests. F i g u r e 6.6: T C P throughput with linear topology. •B o.s- I 0.6 O I CO Q. m o •STC-MAC MRC-MAC •802.11 0.4i ^ 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 T3 C LU • -802.11 MRC-MAC STC-MAC 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: Random topology tests for C B R traffic with 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 Q "i 0.03 I I ? •D iS 0.02 = 0.01 1 • -802.11 * MRC-MAC - • - S T C - M A C 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: Random topology tests for C B R traffic with E - C R R 10'= 10-" 1 0 ' ' 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 with C R P (no gray zone reduction). 1000 0 S T C - M A C MRC-MAC - • -802.11 1 • 2 3 4 Number of TCP 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 Trans. Commun., vol. 51, no. 11, pp. 1927-1938, Nov. 2003. [2] , "User cooperation diversity - Part II: Implementation aspects and performance anal- ysis," IEEE Trans. Commun., vol. 51, no. 11, pp. 1939-1948, Nov. 2003. [3] P . A . Anghel and M . Kaveh, "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 in dissimilar Rayleigh fading channels," in Proc. of IEEE ICC, Glasgow, Scotland, June 2007. [5] G . Scutari and S. Barbarossa, "Distributed space-time coding for regenerative relay net- works," IEEE Trans. Wireless Commun., vol. 4, no. 5, pp. 2387-2399, Sept. 2005. [6] S. Vaki l ajid B . Liang, "Effect of joint cooperation and multi-hopping on the capacity of wireless networks," in Proc. of IEEE SECON, San Francisco, C A , June 2008. [7] J . N . Laneman, D. N . C. Tse, and G . W . Wornell, "Cooperative diversity in 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 , " Wire- less networks, vol. 13, no. 3, pp. 361-369, July 2006. [9] S. M o h , C. Y u , S . - M . Park, H . - N . K i m , and J . Park, " C D - M A C : Cooperative diversity M A C for robust commimication in wireless ad hoc networks," in Proc. of IEEE ICC, Glasgow, Scotland, June 2007. [10] A . Azgin , Y . Altunbasak, and G . AlRegib, "Cooperative M A C and routing protocols for wireless ad hoc networks," in Proc. of IEEE Globecom, St. Louis, Missouri, Nov. 2005. [11] X . Fang, T . H u i , Z. P ing , and Y . Ning, "Cooperative routing strategies in ad hoc networks," in 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 diversity- based routing in fading channel," in Proc. of IEEE PACRIM, Victoria, Canada, Aug . 2007. [13] M . A . Tope, J . C. McEachen, and A . C. Kinney, "Routing performance of cooperative diversity in ad-hoc networks," in Proc. of IEEE ISCC, Pula-Cagliari , Italy, June 2006. [14] G . Jakl lar i , S. V . Krishnamurthy, M . Faloutsos, P. V . Krishnamurthy, and O. Ercetin, " A cross-layer framework for exploiting virtual M I S O links in mobile ad hoc networks," IEEE Trans. Mobile Comput, 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, "The gray zone problem in I E E E 802.11b based ad hoc networks," ACM Mobile Computing and Communications Review, vol. 6, no. 1, pp. 104-105, Ju ly 2002. [17] W . K i m , J . Lee, T . Kwon, 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. M c G r a w HiU Higher Education, 2000. [19] T . S. Rappaport, Wireless Communications: 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 non- rectangular Q A M with F H T in 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. Alamouti , " A simple transmit diversity technique for wireless communications," IEEE J. Select. Areas Commun., vol. 16, no. 8, pp. 1451-1458, Oct. 1998. [25] R. N . A . Paulraj and D. Gore, Introduction to Space-time Wireless Communications, 1st ed. Cambridge, 2003. [26] B . Awerbuch, D . Holmer, and H . Rubens, "The medium time metric: high throughput route selection in multi-rate ad hoc whreless networks," ACM/Springer Mobile Networks and Applications, vol. 11, no. 2, pp. 253-266, A p r . 2006. J Chapter 7 Conclusions and Future Work 7.1 Summary of Work Accomplished This thesis investigated several performance enhancement problems in wireless local area net- works. Adaptive techniques and cross-layer optimization are utilized to provide better quality- of-service in 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]. The throughput model avoids utihzing the traditional Markovian analysis approach, which leads to solve a complex system of nonhnear equa- tions. Although 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. The new throughput model is based on mean value analysis, and has the benefits of low computation complexity and good accuracy. This through- put model was designed to provide an efficient computation tool for an admission control algorithm proposed in 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]. The use of contention graph enables us to describe the contention situations in the network and handle the admission control problem with the consideration of location dependent contentions. The admission control algorithm can handle multiple classes of traific as required by the 802.11e standard. Apart 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 in 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 size a d a p t a t i o n for I E E E 802 .11n 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. The two firame aggregation techniques: A - M P D U ( M A C Protocol Data Uni t Aggregation) and A - M S D U ( M A C Service Data Uni t Aggregation) are studied. A n analytical model is proposed to describe the throughput behavior under frame aggregations. The model incorporates packet loss either from collisions or channel errors. Comparison with simulation results show that the model is accurate in 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 with both randomized and fixed frame aggregation algorithms. • Cross-layer design of MIMO-enabled W L A N s with network utility maximiza- tion: In Chapter 5, the QoS demand of the 802.11e standard, and the proposed M I M O transmission with multiple antennas in the 802.11n proposals are studied from a cross- layer 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 Aloha 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 loha 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 probabili- ties 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]. Mult iple wireless stations with 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 coopera- tive relaying is proposed. Two 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 correspond- ing 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 with 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 in 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 in recent years. The thesis work has been striving to study several key problems in these developments and propose effective schemes to improve network performance. The throughput modeling in Chapter 2 is the basis for the admission control algorithm in Chapter 3. The frame aggregation analytical model in Chapter 4 also utihzes some of the analytical modeling concepts in Chapter 2. Chapter 4 is mainly studying the M A C performance improvement of the 8 0 2 . l l n proposal. Further in Chapter 5, more in-depth study of the 802.11e and 802.11n protocols is carried out. The main new characteristic of the 8 0 2 . l l n standard, which is the MIMO-enabled 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. The 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. The protocol performance is analyzed with simulations. 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 with low computa- tional complexity. For future work, the accuracy of the model can be further improved. Medium 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 aggrega- tion scheme is aimed to improve the M A C layer throughput. But 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 through- put and delay requirements for QoS flows. The interaction between M A C layers frame aggregation and higher layer protocols, such T C P , also needs fmrther investigation. • Distributed design of the MIMO-enabled C S M A / C A M A C : In Chapter 5, a distributed algorithm has been successfully proposed for the Aloha M A C . But for the C S M A / C A M A C , the design is st i l l 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 in the network utihty maximization formulation. Other possible research directions in this area include extending the design framework to a multi-hop scenario. • A d a p t i v e des ign o f t h e c o o p e r a t i v e scheme: 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," in Proc. of IEEE WCNC, Las Vegas, Nevada, Apr . 2006. [2] , " A n admission control algorithm for multi-hop 802.lie-based W L A N s , " Elsevier Com- puter Communications Journal, vol. 31, no. 14, pp. 3510-3520, Sept. 2008. [3] , "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. [4] , "Cross-layer design of MIMO-enabled W L A N s with network utihty maximization," IEEE Trans. Veh. Technol, in 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 Mobile Networks and Applications Journal, in press, 2008. Appendix A List of Publications Journal Papers • Y u x i a L i n , Joo-Han Song, and Vincent W.S . Wong, "Cooperative M A C and Routing Pro - tocols Design for Wireless Ad-hoc Networks," accepted for pubhcation in ACM/Springer Mobile Networks' and Applications Journal, 2008. • Y u x i a L i n and Vincent W.S . Wong, "Cross-layer Design of MIMO-enabled W L A N s with Network Ut i l i ty 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 Algorithm for Multi -hop 802.lie-based W L A N s , " in Elsevier Computer Communications Journal, vol. 31, issue 14, pp. 3510-3520, September 2008. Conference Papers • Y u x i a L i n , Joo-Han Song, and Vincent W.S . Wong, "Cooperative Protocols Design for Wireless Ad-Hoc Networks with Mult i -hop Routing," in Proc. of International ICST Con- ference on Heterogeneous Networking for Quality, Reliability, Security and Robustness (QShine), Hong Kong, China , July 2008. • Y u x i a L i n and Vincent W.S . Wong, "Uti l i ty-optimal Cross-layer Design for W L A N with M I M O Channels," in Proc. of IEEE International Conference on Communications (ICC), Beijing, China , M a y 2008. • Y u x i a L i n and Vincent W . S . Wong, "Adaptive Tuning of MIMO-enabled 802.11e W L A N s with Network Uti l i ty Maximization," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), 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 Optimal Frame Size Adapta- tion for I E E E 802.11n W L A N s , " in 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 Algorithm for Mult i -hop 802.11e based W L A N s , " in Proc. of Third International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine), Waterloo, O n - tario, Canada, August 2006. • Yux ia L i n and Vincent 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 Wireless Communications and Net- working Conference (WCNC), Las Vegas, Nevada, A p r i l 2006. • Y u x i a L i n , A m i r Hamed Mohsenian Had, Vincent W.S . Wong, and Joo-Han Song, " E x - perhnental Comparisons between S A O D V and A O D V Routing Protocols," in Proc. of 1st ACM Workshop on Wireless Multimedia Networking and Performance Modeling (WMuNeP), Montreal, Quebec, October 2005. B o o k C h a p t e r s • Y u x i a L i n and Vincent W.S . Wong, "Adaptive Techniques in 802.11-based W L A N s , " to appear in Adaptive Networking and Cross-layer Design in Wireless Communications, edited by M . Ibnkahla, C R C Press.

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items