Joint Admission Control and Routing in IEEE 802.16-Based Mesh Networks by Shiying Zhang M.E.,Tianjin University, P.R.China, 1999 B.E.,Tianjin University, P.R.China, 1996 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) September 2008 c© Shiying Zhang, 2008 Abstract In recent years, wireless mesh networking has attracted a growing interest due to its inherent flexibility, scalability, and reliability. The IEEE 802.16 standard, commonly known as worldwide interoperability for microwave access (WiMAX), is the latest technology that enables broadband wireless access over long distances. WiMAX, which emerges as a wireless alternative to cable and digital subscriber line (DSL), is an ideal candidate to serve as the infrastructure for large scale wireless mesh networks. This thesis focuses on the quality of service (QoS) provisioning techniques in WiMAX-based metropolitan area mesh networks. We study the connection ad- mission control (CAC) and routing issues in the design and operation of wireless multihop mesh networks. We propose a joint CAC and routing scheme for multiple service classes with the objective to maximize the overall revenue from all carried connections. Connection-level QoS constraints such as handoff connection drop- ping probability can be guaranteed within a threshold. Multiple service classes can be prioritized by imposing different reward rates. We apply optimization techniques to obtain the optimal CAC policies. The optimality criterion is the long-run aver- age reward. We demonstrate that the proposed scheme can the maximum revenue ii obtainable by the system under QoS constraints. We show that the optimal joint policy is a randomized policy, i.e., connections are admitted to the system with some probabilities when the system is in certain states. Simulation results illustrate that the proposed scheme meets our design goals and outperforms the existing scheme. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . 6 2 Background and Related Works . . . . . . . . . . . . . . . . . . . . . 8 2.1 Overview of WiMAX Physical and MAC Layers . . . . . . . . . . 8 iv 2.1.1 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2 MAC Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 QoS Framework and Service Types . . . . . . . . . . . . . . . . . . 13 2.2.1 Service Flows . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Scheduling Services . . . . . . . . . . . . . . . . . . . . . 14 2.3 Mesh Topology Support . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.1 CAC in Wireless Cellular Networks . . . . . . . . . . . . . 19 2.4.2 QoS Provisioning in WiMAX Networks . . . . . . . . . . . 20 2.4.3 CAC in Wireless Multihop Networks . . . . . . . . . . . . 22 2.4.4 Optimal CAC Schemes . . . . . . . . . . . . . . . . . . . . 25 3 Joint CAC and Routing . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 WiMAX-based Mesh Network Infrastructure . . . . . . . . 27 3.1.2 The Joint CAC and Routing Problem . . . . . . . . . . . . 28 3.1.3 Resource Reservation and CAC Process . . . . . . . . . . . 30 3.1.4 Wireless Channel Model . . . . . . . . . . . . . . . . . . . 33 3.2 Formulation of the Joint CAC and Routing Problem as an SMDP . . 34 3.2.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2.2 Decision Epochs and Actions . . . . . . . . . . . . . . . . 39 3.2.3 State Dynamics . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2.4 Policy and Reward Function . . . . . . . . . . . . . . . . . 43 3.2.5 Network Layer Blocking Probability Constraints . . . . . . 45 v 3.3 Optimal Solution to the Joint CAC and Routing Problem . . . . . . 46 3.4 Computational Complexity and Implementation Issues . . . . . . . 47 4 Simulation Results and Discussions . . . . . . . . . . . . . . . . . . . 50 4.1 Simulation Method and Parameter Settings . . . . . . . . . . . . . 50 4.1.1 Simulation Method . . . . . . . . . . . . . . . . . . . . . . 50 4.1.2 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . 52 4.2 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . 54 4.2.1 Single Service Class . . . . . . . . . . . . . . . . . . . . . 54 4.2.2 Multiple Service Classes . . . . . . . . . . . . . . . . . . . 60 4.2.3 Optimal Policy Obtained from the Proposed Scheme . . . . 64 5 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . 67 5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 vi List of Tables 2.1 Modulation and coding schemes for WiMAX. . . . . . . . . . . . . 10 2.2 WiMAX applications and QoS. . . . . . . . . . . . . . . . . . . . . 16 4.1 Simulation models and parameters. . . . . . . . . . . . . . . . . . . 53 vii List of Figures 2.1 WiMAX-based backhaul mesh network. . . . . . . . . . . . . . . . 18 3.1 Multi-radio multi-channel deployment. . . . . . . . . . . . . . . . . 32 3.2 The admission control process. . . . . . . . . . . . . . . . . . . . . 37 4.1 Simulation time vs. number of ongoing connections. . . . . . . . . 55 4.2 Traffic load vs. number of ongoing connections, blocking probabil- ity, and average reward. . . . . . . . . . . . . . . . . . . . . . . . . 56 4.3 Simulation time vs. number of ongoing new and handoff connections. 57 4.4 Handoff connection arrival rate vs. blocking probability. . . . . . . 58 4.5 New connection arrival rate vs. average number of connections. . . 59 4.6 Handoff connection arrival rate vs. dropping probability. . . . . . . 59 4.7 Average reward under different traffic loads. . . . . . . . . . . . . . 61 4.8 Blocking probability comparisons under different traffic loads. . . . 62 4.9 Blocking probabilities comparisons of two service classes. . . . . . 62 4.10 Blocking probabilities of two service classes with threshold settings. 63 4.11 Average reward when the reward ratio between two classes of ser- vice changes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 viii 4.12 Illustration of the obtained optimal policy. . . . . . . . . . . . . . . 65 4.13 Optimal policy for new connections. . . . . . . . . . . . . . . . . . 66 4.14 Optimal policy for handoff connections. . . . . . . . . . . . . . . . 66 ix List of Abbreviations AMC Adaptive Modulation and Coding BE Best Effort CAC Connection Admission Control CID Connection ID CAC Connection Admission Control DiffServ Differentiated Services DSL Digital Subscriber Line ertPS extended-real-time Polling Service FDD Frequency-Division Duplex GPC Grant Per Connection GPSS Grant Per Subscriber Station LOS Line-Of-Sight MAC Medium Access Control MANET Mobile Ad hoc Network MMR Mobile Multihop Relay MPEG Moving Picture Experts Group NLOS Non-Line-Of-Sight x nrtPS non-real-time Polling Service OFDM Orthogonal Frequency-Division Multiplexing OFDMA Orthogonal Frequency-Division Multiple Access PDU Protocol Data Unit PMP Point-to-Multipoint QoS Quality of Service RSVP Resource Reservation Protocol rtPS real-time Polling Service SFID Service Flow Identifier SLA Service Level Agreement SMDP Semi-Markov Decision Process SNR Signal to Noise ratio TDM Time-Division Multiplexing TDD Time-Division Duplex TDMA Time Division Multiple Access UGS Unsolicited Grant Service VBR Variable Bit Rate VoIP Voice Over IP WiMAX Worldwide Interpretability for Microwave Access WLAN Wireless Local Area Network xi Acknowledgments First, I would like to express my deep and sincere gratitude to my supervisor, Dr. Victor C.M. Leung, for his constant support, encouragement, understanding, and guidance throughout this work. This thesis would never have been written without his assistance. I also want to express my sincere thanks to Dr. Richard Yu for his valu- able suggestions, constructive comments, and precious time spent on this thesis. I am very grateful to all my friends and colleagues in Data Communications Group, especially Mr. Hui Chen, Ms. Joy Zhang, Ms. Jie Zhang, Ms. Dana Wang, Dr. Zhanping Yin, and Dr. Qixiang Pang for their friendship, help, and support. Special thanks to my husband Henry for his love, support, understanding, and encouragement during my studies at UBC. This work was supported by a grant from TELUS and the Natural Sciences and Engineering Council of Canada under grant CRDPJ 341254-06. xii Chapter 1 Introduction This introductory chapter gives a brief description of the motivations and objectives on the research of connection admission control (CAC) and routing prob- lems in worldwide interoperability for microwave access (WiMAX)-based wireless metropolitan area mesh networks. The outline of the thesis is stated in Section 1.3. 1.1 Motivations In recent years, WiMAX networks, which are based on IEEE 802.16 stan- dards, have emerged as alternatives for delivering last mile broadband wireless ac- cess to end users [1]. WiMAX promises to deliver high data rates over long dis- tances to a large number of users. Wireless mesh networks are basically multihop wireless networks that maintain signal strength by breaking long distances into a se- ries of shorter hops. The WiMAX air interfaces are specifically designed as broad- band wireless access systems to replace wired broadband access, such as cable and digital subscriber line (DSL). WiMAX makes it possible for low-cost deployments 1 of broadband access for areas that are technically or economically infeasible to in- stall wired cable infrastructure. Initially the WiMAX air interfaces are created to support fixed users. The new standard, i.e., IEEE 802.16e-2005 [2] [3], adds full mobility support for mobile users. Infrastructure meshing creates wireless backhaul mesh among wireless routers/base stations. It reduces system backhaul costs while increasing network coverage and reliability. WiMAX, which offers great bandwidth of up to 70 Mbps and long transmission range up to 50 km, is an ideal candidate to serve as the infrastructure for large scale wireless backhaul mesh networks. Wireless mesh networks are composed of mesh routers and mesh clients [4]. The mesh routers form the backhaul of the wireless mesh networks. Some mesh routers that are called gateway nodes connect to the Internet backbone via high- bandwidth wired connections. End user’s traffic is routed to and from the wired Internet through direct or multihop communications over wireless backbone. The intermediate nodes serve as relay stations, which help forward the data packets from the source node to the destination node. They make the packets forwarding deci- sions based on their knowledge of the network. Mesh architecture offers improved efficiency, flexibility, as well as high and predictable performance. Most applica- tions in WiMAX-based mesh networks are broadband services with various quality of service (QoS) requirements. It is essential to provide wireline like QoS guarantee in WiMAX-based mesh networks. The design of a QoS scheme is especially chal- lenging given the new characteristics introduced through wireless multiple hops, such as network connectivity, traffic routing, and decentralized implementation. CAC is one of the key mechanisms in the provision of guaranteed QoS in 2 wireless networks. The role of CAC is to restrict the access to the network in order to prevent network congestion or service degradation for already accepted users. A new connection request can be accepted if there are enough free resources to meet the QoS requirements of the new connection without violating the QoS constraints for existing connections. Supporting multiple classes of traffic with different QoS requirements is one of the fundamental requirements for WiMAX- based wireless mesh networks [4]. It has become a desirable feature in wireless systems to differentiate service classes by prioritizing and pricing them accordingly. For example, an end user may want to put voice traffic on a gold class of service, backup traffic on a silver class, and non-critical data traffic on a bronze class. Once the charging rates for different service classes are fixed, one way to optimize the system revenue is through CAC, i.e., more profitable connections are given higher priorities for channel access. The CAC scheme for a WiMAX-based mesh network must be able to prioritize different types of connections according to their quality of service (QoS) requirements. However, most existing CAC schemes are for a single service class, and the extension of these schemes to the case of multiple service classes may not be an easy task. Therefore, there is a need to develop a CAC and routing scheme for multiple classes of service with different QoS expectations. When a mobile station moves from the coverage area of a base station to that of another, it switches its connectivity to the closest base station. Handoff of ongo- ing connections among base stations/mesh routers is necessary in order to provide seamless mobility support to mobile clients. In multihop wireless mesh networks, the CAC scheme has to handle two types of connections: new connections that 3 are initiated from its own cell and handoff connections from other base stations or mesh routers. The QoS performance related to these two types of connections are generally measured by the new connection blocking probability and handoff con- nection dropping probability. In general, dropping a handoff connection has a more negative impact than blocking a new connection request. Therefore, channel access priority should be given to handoff connections by the CAC module so that they experience a lower connection blocking probability than new connections. On this basis, the long-run system utilization is maximized while guaranteeing QoS for all connections. A wireless mesh network consists of a mixture of fixed and mobile nodes that are interconnected together via wireless links to form a multihop wireless net- work. It has fundamental differences compared with traditional cellular networks or infrastructureless mobile ad hoc networks [4]. Wireless mesh networks support ad hoc networking and have the capability of self-forming, self-healing, and self- organization. Their wireless backbone/infrastructure provides large coverage, con- nectivity, and robustness in the wireless domain. The mesh routers have minimal mobility and can perform dedicated routing and configuration. In wireless mesh networks, CAC decisions are closely coupled with route selections. When a new connection request arrives, the network has to look for a feasible route from the source node to the destination node and ensure that it has enough residual capac- ity to admit the new connection without violating the QoS constraints of existing connections. Therefore, practical and effective joint optimize CAC and traffic rout- ing schemes are desired in a wireless mesh network in order to achieve optimal 4 revenues. 1.2 Objectives The main objective of this thesis is to study the problems of CAC and routing in WiMAX-based wireless metropolitan area mesh networks. We intend to develop a CAC scheme which maximizes the total system revenue from all carried connec- tions while guaranteeing the QoS for each class of service. Specially, we aim to design a mechanism that: (1) Optimally decides whether or not to admit as well as to which route to admit an incoming connection, and if the connection is admitted, reserves the necessary bandwidth along the chosen route; (2) Simultaneously sat- isfies QoS constraints of all the admitted connections at connection level, e.g. to guarantee the dropping probability of the handoff connections; (3) Prioritizes the traffic according to the application’s service types and maximizes the total system revenue. 1.3 Contributions Our research mainly focuses on studying the CAC and routing problems in WiMAX-based backhaul mesh networks. Most existing works on the resource management and QoS provisioning in WiMAX networks are based on single-hop point-to-multipoint (PMP) network topology. In this thesis, we intend to develop an optimal scheme that takes into account the new characteristics introduced through infrastructure meshing. The main contributions of this thesis are as follows [5] [6]: 5 • We propose a semi-Markov decision process (SMDP) based approach which combines CAC and routing together to provide connection-level QoS guaran- tees while maximizing the long-run system revenue in WiMAX-based wire- less backhaul mesh networks. Our proposed scheme takes into account mul- tiple classes of services with various QoS requirements. It can prioritize dif- ferent service classes by imposing different reward rates. A reward function is used to determine the set of optimal admission control policies. • We use a linear programming based approach to obtain the optimal policies. We define a cost function which is related to the blocking probability con- straints and add those constraints to the linear programming formulation. Handoff dropping probability can be guaranteed below a specified threshold. • We provide extensive simulations to evaluate the performance of our pro- posed joint CAC and routing scheme under various traffic load conditions. We validate the simulation results with analytical results. Simulation results show that the proposed scheme meets our design goals and outperforms the existing scheme. 1.4 Organization of the Thesis The organization of this thesis is as follows: • In Chapter 2, we provide a background and survey on existing CAC algo- rithms in the literature. The issues and design approaches for joint CAC and routing in multihop wireless mesh networks are discussed. 6 • In Chapter 3, we investigate the key design issues related to the resource management for QoS support in WiMAX-based backhaul mesh networks. We describe the formulation of the optimal joint CAC and routing scheme and provide a linear programming based approach to get the optimal CAC policy. • In Chapter 4, we present the simulation results which demonstrate the effec- tiveness of the proposed scheme. • In Chapter 5, we conclude the thesis with a summary of the presented work and some suggestions for future work. 7 Chapter 2 Background and Related Works In this chapter, Section 2.1 gives a brief description of the WiMAX physical layer, medium access control (MAC) layer, and QoS characteristics. Section 2.2 gives an overview of related works on CAC and routing schemes in wireless mesh networks. 2.1 Overview of WiMAX Physical and MAC Layers 2.1.1 Physical Layer The original WiMAX standard, IEEE 802.16a, specifics the physical layer of WiMAX operating in the 10-66 GHz frequency band for line-of-sight (LOS) transmissions between a base station and a subscriber station. Subsequent amend- ments, IEEE 802.16-2004, extends the 802.16 air interface to operate in the 2-11 GHz range and supports non-line-of-sight (NLOS) transmissions. An amendment to IEEE 802.16-2004, IEEE 802.16e-2005, incorporates a number of enhancements 8 including better QoS support and the use of scalable orthogonal frequency-division multiple access (OFDMA). It is specially designed to support user mobility. The lat- est 802.16 standard (IEEE 802.16g) that is still under development, aims to support mobile users at higher layers and provide more efficient management of network resource, mobility, and spectrum. WiMAX specifies different air interfaces for different frequency bands. In the 10-66 GHz band, the signal transmissions between a base station and a sub- scriber station should be LOS and the air interface for this band is Wireless-SC (single carrier). In the 2-11 GHz band, three different air interfaces can be used in conjunction with the MAC layer to provide a reliable end-to-end connection. The three air interfaces are: • WirelessMAN-SCa: a single-carrier modulated air interface. • WirelessMAN-OFDM: a 256-carrier orthogonal frequency-division multiplex- ing (OFDM) scheme, a single user can transmit on all of the subcarriers at any given time. Time-division or frequency-division multiple access is employed to support multiple users. • WirelessMAN-OFDMA: also referred to as multiuser-OFDM, is an exten- sion of OFDM. OFDMA allows multiple users to transmit simultaneously on the different subcarriers per OFDM symbol. Multiple access is provided by addressing a subset of the carriers to individual receivers. WiMAX supports adaptive modulation and coding (AMC) technique in or- der to enhance the data transmission rate. It can achieve data rates up to 70 Mbps 9 Table 2.1: Modulation and coding schemes for WiMAX. Rate ID Modulation Level Coding rate Information Required bits/symbol SNR (dB) 0 BPSK 1/2 0.5 6.4 1 QPSK 1/2 1 9.4 2 QPSK 3/4 1.5 11.2 3 16QAM 1/2 2 16.4 4 16QAM 3/4 3 18.2 5 64QAM 2/3 4 22.7 6 64QAM 3/4 4.5 24.4 depending on the channel bandwidth as well as the modulation and coding schemes used. Multiple modulation levels are supported in WiMAX. The allowed modula- tion schemes in the downlink and uplink are: binary phase shift keying (BPSK), quadrate phase shift keying (QPSK), 16-quadrature amplitude modulation (QAM), and 64-QAM. Adaptive modulation allows the WiMAX system to adjust the signal modulation scheme in each frame depending on the channel conditions on the air link. Using the channel quality feedback indicator, the mobile stations can provide the base station with feedback on the downlink channel quality. For the uplink, the base station can estimate the channel quality based on the received signal quality. The base station scheduler can take into account the channel quality of each user’s uplink and downlink and assign a modulation and coding scheme that maximizes the throughput for the available signal-to-noise ratio (SNR). WiMAX standards de- fine seven combinations of modulation and coding rates that can be used depending on the channel and interference conditions. These possible combinations are shown in Table 2.1. 10 2.1.2 MAC Layer WiMAX uses a connection-oriented MAC protocol which provides a mech- anism for bandwidth requests and grants. All data transmissions between a base station and subscriber stations take place in the context of connections. The MAC layer schedules the usage of the network resources, provides QoS differentiation to multiple users on the shared medium, and guarantees a specified service level for each connection. The MAC layer also performs standard protocol data unit (PDU) creation tasks and handles network entry and initialization of a subscriber station. The MAC PDU is the data unit exchanged between the MAC layers of a base station and subscriber stations. WiMAX supports both frequency-division duplex (FDD) and time-division duplex (TDD) transmission modes. For TDD, the MAC frame is divided into up- link and downlink subframes. Each subframe consists of a number of time slots. The lengths of these subframes are determined dynamically by the base station and broadcasted to the subscriber stations through downlink and uplink map messages at the beginning of each frame. Therefore, each subscriber station knows when and how long to receive and transmit data to the base station. In WiMAX, subscriber stations use bandwidth request mechanism to specify uplink bandwidth requirements to the base station. The MAC protocol supports dynamic bandwidth allocation. Each subscriber station can request bandwidth from the base station by using a bandwidth request message (BW-request) PDU. Two modes can be used to transmit BW-request PDUs: contention mode and contention- free mode. In the contention mode, a subscriber station sends BW-request PDUs 11 during the contention period during a frame and a backoff mechanism is used to resolve the the contentions among multiple BW-request PDUs. In the contention- free mode, the base station polls each subscriber station and the subscriber station responses by sending back BW-request PDUs. Due to the predictable signaling delay of the polling scheme, contention-free mode is suitable for QoS-sensitive applications. WiMAX supports two modes of bandwidth allocation: grant per connec- tion (GPC) and grant per subscriber station (GPSS). In GPC mode, bandwidth is granted explicitly to a connection, and the subscriber station uses the granted band- width only for that connection. In GPSS mode, subscriber stations are granted bandwidth aggregated into a single grant to the subscriber station itself. The sub- scriber station then holds the responsibility for reassigning the bandwidth among its connections, maintaining QoS and service level agreements (SLA). The two mech- anisms of bandwidth allocation allow a tradeoff between simplicity and efficiency. GPC allows a simpler subscriber stations but it incurs a high overhead. Therefore GPC is suitable for substation stations with fewer users. GPSS has a low overhead but requires intelligent subscriber stations. It supports hierarchical and distributed scheduling, allowing more complicated reaction to QoS needs. Thus GPSS is more efficient and scalable than GPC. It is suitable for stations with many connections. A subscriber station may request bandwidth in the following ways: • Implicit requests (for unsolicited grant service (UGS)). For continuous band- width demand such as CBR data, the subscriber stations need not request bandwidth, but the base station grants it unsolicited. Bandwidth requirements 12 are negotiated at connection setup. • Bandwidth request messages. Bandwidth is allocated to subscriber stations in response to a BW-request sent from subscriber stations to the base station. GPSS subscriber stations can send this message in any bandwidth allocation they receive. GPC subscriber stations can send it in either a request interval or a data grant interval allocated to their basic connections. • Piggybacked request (for non-UGS services). Piggyback a request for addi- tional bandwidth on a normal data packet. • Poll-me bit (for UGS service). To bypass the normal polling process, a sub- scriber station with a UGS connection can set the poll-me bit to let the BS know it needs to be polled for bandwidth needs on another connection. 2.2 QoS Framework and Service Types WiMAX standards define a QoS framework and various types of service flows. The MAC layer provides differentiated QoS to support different classes of services. WiMAX standards accommodate data, voice, video, and other types of traffic by using appropriate features in the MAC layer. 2.2.1 Service Flows One of the primary mechanisms for providing QoS in WiMAX is to asso- ciate application data packets with a service flow. A service flow is a MAC layer transport service which provides unidirectional transportation of packets in both uplink and downlink directions. In WiMAX, all service flows have a 32-bit service 13 flow identifier (SFID) and active service flows also have a unique 16-bit connection ID (CID) assigned by the base station. QoS is provided according to a set of QoS parameters defined for the service flow. The QoS parameter set defines the neces- sary QoS metrics such as delay, jitter, bandwidth guarantee, and traffic priority for the applications being delivered. A service flow can be either dynamic or static. Dynamic service flows may be created, changed, or deleted, which is carried out through a series of MAC man- agement messages: dynamic service addition (DSA) for creating a new service flow; dynamic service change (DSC) for changing an existing service flow; and dynamic service deletion (DSD) for deleting an existing service flow. The base station is responsible for issuing the SFIDs and mapping it to unique CIDs. Ser- vice flows can also be mapped to differentiated services (DiffServ) code points or multi-protocol label switching (MPLS) flow labels to enable end-to-end IP-based QoS. The standard also specifics the authorization process by which the base sta- tion and the subscriber station identify each other. Every change to the service flow QoS parameters, such as DSA, DSC, or DSD message, must be approved by an au- thorization module. These changes include requesting a CAC decision, activation of a service flow, or service reduction requests. 2.2.2 Scheduling Services Scheduling services are the data handling mechanisms supported by the MAC scheduler for data transmissions on a connection. WiMAX standards de- fine four scheduling services for uplink flows, each scheduling service has different 14 QoS requirements: • Unsolicited grant service (UGS). UGS supports real-time service flows that generate fixed size data packets on a periodic basis such as voice over IP (VoIP) without silence suppression. In this case, a fixed amount of bandwidth is allocated to each connection in a static manner, which minimizes delay and jitter. UGS service is suitable for the traffic with very strict QoS constraints. • Real-time polling service (rtPS). rtPS supports real-time service flows that generate variable size data packets on a periodic basis, e.g. moving picture experts group (MPEG) video. The service offers real-time, periodic, unicast request opportunities, which meet the flows’ real-time needs and allow the subscriber stations to specify the size of the desired grant. This service re- quires more request overhead than UGS, but supports variable grant sizes for optimum data transport efficiency. • Extended real-time polling service (ertPS): ertPS is a scheduling mechanism that builds on the efficiency of both UGS and rtPS. ertPS is designed for real time traffic with variable data rate, such as VoIP service with silence suppression, over WiMAX networks. This service is defined only in IEEE 802.16e-2005, not in IEEE 802.16-2004. • Non-real-time polling service (nrtPS). nrtPS is designed to support non-real- time service flows that require variable size data grants on a regular basis, such as high bandwidth file transfer. The service offers unicast polls on a regular basis, which assures that the flow receives request opportunities even 15 Table 2.2: WiMAX applications and QoS. QoS Category Applications QoS Specifications UGS VoIP * Maximum Sustained Rate Unsolicited Guaranteed * Maximum Latency Tolerance Service * Jitter Tolerance rtPS Streaming Audio * Minimum Reserved Rate real-time Polling Service or Video * Maximum Sustained Rate * Maximum Latency Tolerance * Traffic Priority ertPS Voice with Activity * Minimum Reserved Rate extended-real-time Detection * Maximum Sustained Rate Polling Service * Maximum Latency Tolerance * Jitter Tolerance * Traffic Priority nrtPS File Transfer Protocol * Minimum Reserved Rate non-real-time (FTP) * Maximum Sustained Rate Polling Service * Traffic Priority BE Data Transfer, Web * Maximum Sustained Rate Best Effort Browsing etc. * Traffic Priority during network congestions. • Best effort service (BE): This service is designed to support best effort traffic, such as web surfing and email traffic. The amount of bandwidth allocated to BE service depends on the bandwidth allocation policies for other types of service. In general, neither throughput nor delay guarantees are provided for BE service. The data services and applications that WiMAX currently supports are sum- marized in Table 2.2. 16 2.3 Mesh Topology Support WiMAX standards specify an air interface for broadband wireless access systems which support fixed, nomadic, and mobile users. A typical deployment of WiMAX is in the areas where wired broadband access is too expensive, especially when a low density of users is expected. In order to extend the coverage of a base station, WiMAX standards define a multihop mesh mode extension to the single hop PMP network architecture. Mesh networking can be implemented in two basic modes: client meshing and infrastructure meshing. The mesh mode extension, which enables multihop peer-to-peer communications among subscriber stations, is a type of client mesh- ing. Infrastructure meshing creates wireless backhaul mesh among base stations. It further increases network coverage and reduces system backhaul cost. Although infrastructure meshing has not been standardized in WiMAX, the mobile multi- hop relay (MMR) task group [7] [8] is making effort to standardize the multihop relay-based network infrastructure. It is expected that the infrastructure meshing functionality will be supported in the standard in the near future. Such an infras- tructure mesh would be suitable as a wireless backhaul to connect multiple wireless access points to a wired gateway. A WiMAX-based infrastructure mesh network consists of mesh routers/base stations that form a wireless mesh backhaul, and mesh clients that access the wire- less mesh backhaul through the mesh routers. User traffic that is aggregated from one or multiple mesh clients is transmitted through several base stations along a multihop route in the backhaul network to the destination mesh client or an Internet 17 Mesh router (WiMAX base station) Internet Backbone Mesh user access Mesh infrastructure Figure 2.1: WiMAX-based backhaul mesh network. gateway. Figure 2.1 illustrates a WiMAX-based infrastructure mesh network. In Figure 2.1, the base stations/mesh routers form a backbone mesh network for the mesh clients to connect to the Internet. In contrast to traditional mobile ad hoc networks (MANETs) or wireless client mesh networks which are formed among stationary or mobile clients, WiMAX- based backhaul mesh networks have relatively stable topologies. The main charac- teristics of a WiMAX-based backhaul mesh networks are: • The mesh routers are also base stations or relay stations and they are usually stationary. The network topology is relatively static. Changes in the topology 18 are mainly caused by switching on/off the mesh routers. • The mesh routers perform dedicated routing and configuration functionalities instead of the end users. The route selection is less dynamic than MANETs where the routing protocols are mainly intended for use by mobile nodes. • Wireless backhaul mesh networks are expected to be always connected to the Internet backbone. Usually multiple gateways are deployed to provide the Internet connectivity. • The network traffic in the backhaul mesh network is primarily aggregated traffic from many end users. The estimated traffic volume is very high and the number of users is very large. • Each mesh router is equipped with multiple radios each operating on differ- ent channels. Simultaneous transmissions and receptions through intelligent channel assignment can be accomplished. • The mesh routers usually have no strong constraints on power consumptions. 2.4 Related Work 2.4.1 CAC in Wireless Cellular Networks CAC has been extensively studied in wireless cellular networks as an impor- tant tool for QoS provisioning in terms of connection blocking and dropping proba- bilities [9]. Since connection dropping is generally considered more annoying than blocking a new connection, CAC is employed to control the handoff failure proba- bility. This can be implemented by reserving a part of system capacity for handoff 19 connections exclusively. The CAC criterion can be either the total number of con- nections that can be admitted or an estimation of handoff dropping probabilities. In [10] and [11], a subset of channels called guard channels are reserved for handoff connections in order to achieve low dropping probabilities. For multiple service classes, an extension of the basic guard channel policy can be achieved by setting different reservation thresholds for each service class [12]. Handoff dropping probability can also be controlled by taking into account the loading information in the neighbor cells in the admission process. The number of users in the target cell and neighbor cells are used together to determine the maximum number of new connections that can be admitted in the target cell. In [13], a channel borrowing scheme is proposed, which allows each cell to lend its channels to its adjacent cells in order to accommodate more handoff connections. The schemes discussed above are mainly designed for the cellular networks in which all mobile stations communicate with the base station directly. Differ- ent from a cellular network, a WiMAX-based wireless mesh network is made up of multiple base stations and mobile stations organized in a mesh topology. QoS provisioning is more challenging in wireless multihop mesh networks due to their decentralized architecture. In wireless multihop mesh networks, routing, CAC, bandwidth reservation, and signaling are tightly coupled together which requires the joint design scheme between MAC layer and network layer. 2.4.2 QoS Provisioning in WiMAX Networks CAC plays an important role in the provisioning of guaranteed QoS in WiMAX- based broadband wireless networks. Although much work has been done on the 20 resource management and CAC in WiMAX networks, most of them are based on a single hop PMP network topology. In [14], a downlink CAC scheme for multiple classes of services with an objective to maximize the system revenue is proposed for WiMAX networks. A utility and fairness constrained greedy algorithm is also developed as a computa- tional efficient method for the optimal policy. Chang et al. [15] present an adaptive CAC method to increase network re- wards and channel utilization. A two-level scheduling mechanism (e.g., node pri- ority level and service flow level) is used to schedule a polling list for subscriber stations. The CAC scheme uses a cost-based function as the admission criteria and checks the residual bandwidth to decide whether or not to admit the new connec- tion. In [16], a CAC scheme for different types of service flows is proposed. A new connection request is classified into a particular queue depending on the asso- ciated service class type. A bandwidth estimator agent is used to monitor the queue length for each service flow at regular intervals and estimate the specific bandwidth requirements the service flows. Niyato et al. [17] present a joint adaptive bandwidth allocation and CAC scheme for real-time and non-real-time polling services in the WiMAX-based broad- band wireless networks. The delay and transmission rate are used as the cost functions and decision criteria for bandwidth allocation and CAC. An optimiza- tion problem is formulated and the solution is given by using linear programming techniques. 21 IEEE 802.16e adds the capability to provide full mobility support in WiMAX networks. The CAC scheme designed for mobile WiMAX should consider the new features introduced by the full mobility of mobile stations. In [18], a dynamic bandwidth reservation and CAC scheme (DBRAC) for 802.16e broadband system is proposed. A fraction of the bandwidth, i.e., guard bandwidth, is reserved for handoff traffic. The total reserved guard bandwidth is dynamically adjusted based on the bandwidth requirements of both potential handoff traffic and current ongoing real-time variable bit rate (VBR) traffic. Although there have been a lot of works on the problems of bandwidth allo- cation and CAC in WiMAX-based wireless broadband networks with PMP network topology, the network operations and radio resource allocation problems are much more complicated for multihop mesh networks compared with the single hop ar- chitecture [4]. Therefore, QoS schemes that are designed for a single hop WiMAX networks may not work well in a multihop situation in which QoS guarantee is required not only over a single hop, but also over an entire wireless multihop path. 2.4.3 CAC in Wireless Multihop Networks QoS routing and CAC schemes have been extensively studied in mobile mul- tihop networks, which are characterized by the lack of infrastructures. In mobile multihop networks, the mobile stations are free to move randomly and the net- work topology changes frequently. In [19], a CAC scheme over an on-demand routing protocol is proposed to guarantee bandwidth for real-time applications in time-slotted multihop mobile networks. The times slots for a connection are re- served at each node along the route. On-demand routing and bandwidth reservation 22 are used to explore all paths between the source node and the destination node, and the available bandwidth is calculated in a hop-by-hop fashion. The connection is rejected if no routes could be found. All nodes along that path are allocated the required bandwidth in terms of time slots once a connection is accepted. Zhu et al. [20] propose a CAC and bandwidth reservation framework which is also based on an on-demand QoS routing protocol in multihop ad hoc networks. The available bandwidth on each node along the path is estimated based on calcu- lated saturation throughput. In [21], a measurement-based distributed CAC scheme for mobile ad hoc networks is proposed. A sequence of probing packets is used to determine a service curve which reflects the network loading status. The measured service curve is compared by a pre-specified service corresponding to the QoS re- quirements. A connection request is accepted if the measured service is above the universal service curve. Otherwise, the connection will be rejected. Georgiadisd et al. [22] also address the problems of CAC and bandwidth reservation in mobile ad hoc networks. The proposed method is based on a proactive routing scheme where nodes obtain routing information through periodic exchange knowledge of network topologies and states. Wireless backhaul mesh networks have different characteristics compared with mobile ad hoc networks. Wireless mesh networks have a relatively stable topology except for the occasional failure of nodes or addition of new nodes, while in mobile ad hoc networks, the mobile stations are free to move randomly. In addi- tion, mesh routers can carry out the routing and configuration functionalities, while end user devices usually do not have such functionalities in mobile ad hoc net- 23 works. The traffic being carried on mesh networks is usually aggregated from a large number of end users. Therefore, it changes infrequently. Particularly, in an infrastructure mesh network, all the traffic is either forwarded from or to a gateway, while in mobile ad hoc networks, the traffic flows can happen between arbitrary pair of nodes. Therefore, the QoS provisioning algorithms developed in mobile ad hoc networks may not be applied directly in wireless mesh networks. There are some research efforts in the literature studying CAC, bandwidth reservation, and routing techniques in mesh networks. Niyato et al. [23] propose a radio resource management framework for WiMAX-based wireless mesh net- works. The framework combines subchannel allocation, CAC, and route selection. A tandem queueing model is developed to obtain the end-to-end delay, throughout, and packet dropping probabilities. A route will be selected for an arrived connec- tion based on the estimated end-to-end transmission delay. However, the proposed approach considers only a single class of service type. In [24], a CAC scheme is proposed for multihop wireless backhaul networks with QoS support. The proposed scheme first constructs a tree-based topology rooted at the gateway in the backhaul, and then admits a subset of connections based on their rate and delay requirements. In [25], a distributed CAC protocol is presented to provide bandwidth and delay guarantees in multihop wireless mesh networks. Tsai et al. [26] propose a routing and CAC algorithm for WiMAX-based mesh networks. The route selection process uses the shortest widest effective band- width (SWEB) as the routing metrics. The bandwidth requested of a service flow is calculated using a token bucket-based model which is based on the delay require- 24 ments of the new connections. CAC is performed based on the estimation of new bandwidth requirements and current available system capacity. A two-step end-to- end bandwidth reservation scheme in WiMAX-based mesh networks is proposed by Cicconetti et al. [27]. First, the node that initiates the traffic flows conveys the bandwidth requests to the destination node through a PATH message which speci- fies the traffic flow information. Then a RESV message is sent backward from the destination node to the source node along the path. CAC is performed at each node to check whether there is sufficient resource to admit the traffic. In [28], a cross-layer approach to coordinate routing, MAC scheduling, and physical layer resource allocation in multihop wireless backhaul networks is pro- posed. The gateway base stations perform CAC as well as scheduling. A new traffic flow is accepted only if the traffic demand can be supported by the scheduler, otherwise, it is not scheduable or admissible. All the above mentioned CAC schemes only consider a single class of ser- vices, the extension of these schemes to the case of multiple classes of services may not be an easy task. Meanwhile, in wireless mesh networks, handoff of on- going connections between base stations is necessary in order to provide seamless mobility support to mobile clients. Since forced termination of an ongoing connec- tion is more annoying than blocking a new connection attempt from user’s point of view, handoff connections should be given higher priorities. 2.4.4 Optimal CAC Schemes One of the objectives of a service provider is to differentiate prices among the users and maximize the system revenue. CAC plays an important role in op- 25 timizing the revenue for wireless networks. WiMAX MAC layer is designed to differentiate services among traffic categories. Therefore, one of the design goals of CAC schemes in WiMAX-based mesh networks is to find an optimal admis- sion policy which maximizes the network revenue based on the potential rewards of admitting or rejecting new connections. An admission policy is basically a set of decisions that indicate whether a new connection will be accepted and whether an existing connection will be denied a handoff from one cell to another. Decision theoretic approaches that are based on Markov decision process have been used to construct the optimal CAC schemes using standard optimization techniques. In [29] and [30], an SMDP is used to find the optimal policies in a cellular network. The resulting optimal policy can also guarantee blocking probability for new or handoff connections. In [31], an SMDP based joint session CAC scheme is proposed in integrated wireless local area network (WLAN) and cellular networks. It can optimally control the admission of new session arrivals to each network as well as vertical handoffs between them. Although the general optimization techniques have been widely used in or- der to obtain the optimal CAC policies in wireless networks such as mobile cellu- lar networks, little work has been carried out so far on developing optimal CAC schemes for WiMAX-based wireless mesh networks. 26 Chapter 3 Joint CAC and Routing This chapter explains the key design issues related to the resource manage- ment for QoS support in WiMAX-based multihop mesh networks. In Section 3.1, we describe the system architecture. In Section 3.2, we present the proposed joint optimal CAC and routing scheme using a Markov decision process. The CAC mechanism is used to limit the number of ongoing connections at the base sta- tions/mesh routers so that the total revenue for the ongoing connections in the system is maximized. A linear programming based solution for the optimization problem in the proposed joint CAC and routing scheme is given in Section 3.3. 3.1 System Architecture 3.1.1 WiMAX-based Mesh Network Infrastructure WiMAX aims to provide wireless broadband access for both fixed and mo- bile users. It can be deployed in either last mile broadband access scenario or backhaul wireless network scenario. In the first scenario, the operation is based on PMP single hop transmissions between a base station and multiple subscriber sta- tions. In the second scenario, WiMAX operates as the wireless mesh backhaul in 27 which the base stations are connected to each other in a multihop fashion to trans- mit integrated multimedia and data traffic between end users and the core network. A WiMAX backhaul mesh network can integrate multiple types of network access, such as cellular networks, WLANs, and provide services to end users of these net- works. An example of a WiMAX-based wireless metropolitan area mesh network is shown in Figure 2.1. The network architecture of Figure 2.1 basically consists of two parts: WiMAX base stations/mesh routers and subscriber stations/mesh clients. The mesh routers form the multihop infrastructure to support both backhaul access to the Internet and peer-to-peer communications among them. Each of the mesh routers in the mesh infrastructure also serves as a base station for one or multiple mesh clients within its coverage area. Such an infrastructure mesh would be suitable as a wireless backhaul to integrate existing wireless networks such as IEEE 802.16 or IEEE 802.11 based WLAN hotspots. Mesh clients can be fixed, portable, or mobile. Mobile clients roam among base stations and access the wired network via the gateways. 3.1.2 The Joint CAC and Routing Problem WiMAX defines a connection-oriented MAC layer which effectively enables end-to-end QoS control. A connection must be established before the transmission of data packets. Each connection is associated with a service flow and each ser- vice flow is associated with a QoS parameter set which defines the key QoS metrics for the applications being delivered. In WiMAX-based mesh networks, the mo- bile clients request bandwidth on a per connection basis. When a new or handoff 28 connection arrives, a connection request message is sent to the nearest base sta- tion/mesh router. Upon receiving the message, the mesh router will collect all these requests and estimate the available bandwidth based on its knowledge of the net- work. Then CAC is performed to decide whether to admit the connection and to which route to admit it. We use ”bandwidth” as the QoS parameter because band- width guarantee is one of the most significant requirements for real-time multimedia applications. If it is possible to find one or multiple routes that satisfy the bandwidth requirements, the mesh router will admit the connection and pick one route to ac- commodate the new connection. Resources are also reserved by each mesh router along the chosen route to create a multihop end-to-end route. In order to support end-to-end QoS in a WiMAX-based backhaul mesh net- work, an efficient CAC scheme is required to ensure that there are enough resources for the new connection at the mesh routers. A routing algorithm is needed to find the best set of mesh routers to support the requested connection. A new connection is accepted only if all the mesh routers along the route from the source node to the destination node have enough resources for reservation by that connection. The setup process involves a reservation of network resources at the mesh routers along the chosen route for the connection. If these resources are not available, the setup process fails and the connection is blocked. We have two objectives in designing our CAC scheme in WiMAX-base mesh networks. The first objective is to guarantee connection-level QoS such as dropping probabilities for handoff connections, and the second objective is to max- imize the system revenue. The routing decisions can influence both objectives. 29 Some routing algorithms may achieve better performance in some aspects, e.g., routing with minimum hops, routing with the shortest end-to-end delay. However, these routing algorithms alone usually can not give an optimal solution to achieve maximized network revenue. Therefore, joint consideration of the CAC mechanism and route selection scheme is necessary in order to maximize the system revenue and guarantee QoS for QoS-sensitive connections. The problem is how to opti- mally decide whether or not to admit and to which route to admit a new or handoff connection. The admission of data traffic into a network has both rewards and potential risks to the service providers. The rewards come from the utilization of network resources to earn a certain amount of revenue. However, too much network load may cause the degradation of the QoS experience by the already admitted users and even dropping of existing users, which leads to a potential penalty. A well- designed CAC mechanism can increase the network revenue based on the potential rewards and risks of admitting new connections. In order to maximize the revenue, we assign different revenue rates for different types of service flows in the design of the joint CAC and routing scheme in WiMAX backhaul mesh networks. 3.1.3 Resource Reservation and CAC Process CAC and resource reservation are two common mechanisms for providing QoS guarantee in wireless networks. When a new connection is to be setup between a source node and a destination node, the source node (i.e., base station/mesh router) examines whether there are enough resources in the mesh networks so that the con- nection can be admitted without affecting the already existed connections. If these 30 resources can be found, they are reserved for the connection and the transmission can start. The CAC process for an incoming connection consists of finding a path be- tween the source node to the destination node such that all the links on that path have sufficient remaining capacity to satisfy the new connection’s bandwidth re- quirement. The remaining capacity means the link capacity minus the bandwidth already reserved for admitted flows. An optimization problem can be formulated for the base stations/mesh routers to maximize the system revenue. The CAC de- cisions are made based on the results of the optimization formulation. After the CAC module selects one route to accept the new connection, resources are reserved by each router along the chosen route. The reservation of network resources can be performed using a signaling protocol such as the resource reservation protocol (RSVP). Wireless backhaul mesh networks have a relatively stable topology, the mesh routers are relatively fixed and may not have power constraints. The network traffic that is aggregated from many end users also changes infrequently. Generally all the traffic is either forwarded to or from a gateway node, while in ad hoc networks the traffic flows can happen between any pairs of nodes. The behavior of this kind of network is similar to wired networks since it has infrequent topology changes and limited node failures. Node additions and maintenance are also rare [4]. Multiple channels can be used in wireless mesh networks in order to in- crease the network capacity [32] [33]. In the system considered in this thesis, we assume each mesh router is equipped with multiple radios, each operating on dif- 31 Internet Internet Gateway BS1 BS2 BS3 Figure 3.1: Multi-radio multi-channel deployment. ferent channels. For example, Figure 3.1 shows a wireless backhaul mesh networks where multiple channels and multiple radios are used in each mesh router. Two radios are employed for serving the backhaul links, and one more radio is used for serving the local mesh clients. Efficient and intelligent channel assignment schemes are required since the number of total channels is not infinite and may not be enough in high density nodes scenarios [32]. Ideally, the uplink and downlink backhaul radios and the service radio can operate at non-overlapping channels and therefore eliminates the potential co-channel interferences. Fixed channel assign- ments to these radios are viable as each mesh router can be equipped with multiple radios. Therefore, considering the stationary nature of backhaul mesh networks and 32 in order to make sure that the admission decisions for new and handoff connections can be taken promptly, we use pre-computed paths for each source-destination pair in the backhaul mesh network. This can be achieved during the phase of network deployment. 3.1.4 Wireless Channel Model WiMAX supports both TDD and FDD operations. We assume that the back- haul transmissions in the mesh networks use TDD scheme based on OFDM/TDMA (i.e., WirelesMAN-OFDM). With OFDM/TDMA, all subchannels are allocated to one connection at a time. Assume adaptive modulation and coding scheme is used in the physical layer to enhance the transmission rate by adjusting modulation levels according to the channel quality. We use the general Nakagami-m channel model to describe the received SNR. Nakagami-m channel model covers a large class of fading channels including Rayleigh channel as a special case when m = 1. The received SNR γ per frame is a random variable with a Gamma probability density function [34]: Pγ(γ) = mmγm−1 γ̄mΓ(m) exp(−mγ γ̄ ), (3.1) where m is the Nakagami fading parameter (m ≥ 0.5), γ̄ := E{γ} is the average received SNR, and Γ(m) := ∫∞ 0 tm−1exp(−t)dt is the Gamma function. Let N denote the total number of transmission modes available (N = 7 in IEEE 802.16). The SNR range at the receiver can be partitioned into N + 1 non- overlapping intervals with boundary points denoted by {{γn}N+1n=0 }. Mode n will be chosen when γ ∈ [γn, γn+1), (3.2) 33 where n is the mode index and γ is the received SNR. To avoid possible transmis- sion errors, no data are transmitted when γ0 ≤ γ < γ1, which corresponds to mode n = 0 with rate R0 = 0 (bits/symbol). Note that these boundary points correspond to the required SNR at the re- ceiver side, and their values are specified in WiMAX standards as shown in Table 2.1, i.e., γ1 = 6.4dB, γ2 = 9.4dB, ..., γN = 24.4dB. Based on (3.1) and (3.2), the probability of choosing mode n is given by [35] Pr(n) = ∫ γn+1 γn pγ(γ)dγ = Γ(m,mγn/γ̄)− Γ(m,mγn+1/γ̄) Γ(m) , (3.3) where Γ(m,x) := ∫∞ x tm−1exp(−t)dt is the complementary incomplete Gamma function. In our model, we focus on the long term performance of the network, there- fore we use the average transmission rate over the link as the capacity for each link in the wireless mesh network. The capacity can be calculated as follows Cavg = N∑ n=0 Pr(n)C(n), (3.4) where Pr(n) is the probability of choosing transmission mode n defined in (3.3) and C(n) is the channel capacity when using mode n. 3.2 Formulation of the Joint CAC and Routing Prob- lem as an SMDP In this section, the joint CAC and routing problem in wireless mesh networks is formulated as an SMDP. We can model the considered system as an SMDP be- cause the following Markovian properties are satisfied [36]: 34 • Given the current decision time, if action a is chosen in state x, then the time until the next decision epoch, and the state at the next decision epoch depends only on the present state and on the current chosen action. • The time interval between two successive decision epochs is non-deterministic. An SMDP is a generalization of a Markov Decision Process (MDP) and it generalize a MDP by (1) allowing decision maker to choose actions whenever the system state changes; (2) modeling the system evolution in continuous time; and (3) allowing the time spent in a particular state to follow an arbitrary probability distribution [36]. Therefore, SMDPs are appropriate for modeling continuous-time systems in which the time between transitions is not constant. We model the system as an SMDP, instead of a MDP due to the fact that, in a wireless mesh network, the time interval between two successive decision periods is non-deterministic. An SMDP can be solved using algorithms such as policy iteration, value iter- ation, and linear programming [29]. Similar to [31] [29] [37] and [38], we choose to use the linear programming techniques because a nice feature of the linear program- ming formulation (which is not available with policy iteration or value iteration) for solving an SMDP problem is that it allows optimization over extra constraints such as maximum allowed blocking probabilities. The optimal policy will in general be randomized when an additional constraint is imposed [39]. The SMDP formulation for the problem mainly includes the following three steps: • First, we define a finite state space for all the active user connections in the network. The link capacity constraint is specified in the construction of the 35 state space. • Second, we specify the actions and the state dynamics of the SMDP. We as- sume the arrival process for each user to be a continuous-time homogeneous Poisson process. The durations of data connections are exponentially dis- tributed. The reward function and the set of admissible policies are defined. • Third, we specify the performance criterion of maximizing the long-run aver- age reward. We use a linear programming based approach to solve the SMDP. Blocking probability constraints for multiple service classes can be accom- modated by adding additional linear constraints to this linear programming. When a new or handoff connection arrives at a base station or mesh router, a decision must be made as to whether or not to admit and to which route to admit the incoming connection based on the available resources in the mesh network. These time instances are called decision epochs, and decisions are called actions in the SMDP framework. The action chosen is based on the current state of the network. The state information includes the number of sessions of each class of traffic on each route in the mesh network. The process of the SMDP-based optimal CAC scheme is illustrated in Figure 3.2. When an event, e.g., a new connection arrival, occurs, a state is identified by getting the number of sessions in each of the possible routes from the source node to the destination node. Then, an action is found according to the state. The CAC controller in the base station/mesh router executes the action (reject or admit). The process is repeated when next event occurs. 36 Figure 3.2: The admission control process. In order to obtain the optimal solution, it is necessary to identify the state space, decision epochs, actions, state dynamics, rewards, and constraints in the multihop mesh network. 3.2.1 State Space We describe a WiMAX-based wireless backhaul mesh network as a set of nodesN = {1, ..., N} that includes all the mobile clients and mesh routers/gateways and a set of wireless links L = {1, ..., L} that includes all the backhaul links as well as the links between base stations and subscriber stations. Each link l has a total capacity of B(l) units of bandwidth. The mesh network offers J different classes of services. Assume the connections arrive according to independent Poisson pro- cesses. The intensity of arrival and the average duration of data connections for each service class is λj and 1/µj , respectively. When a new or handoff connection of class j, with origination node O and destination node D arrives, it can be either rejected (with zero reward) or accepted (with reward r(j), which can be interpreted as the average reward for carrying the jth class connection). In order to accept the connection, we need to choose a route k from the set of all feasible routes from O 37 to D, k ∈ {1, ..., K}. Assume the bandwidth requirement for the new arrival is b(j). Each node and each link along the chosen route must have at least b(j) units of bandwidth available for the new connection. Although WiMAX-based backhaul mesh networks can support heterogeneous wireless networks, for simplicity, we assume the peer-to-peer transmissions among base stations/mesh routers and the local transmissions between base stations and subscriber stations are all based on WiMAX technology. Let X denote the state space and x(t) ∈ X denote the state of the mesh networks at time t, where t ∈ R+. The state matrix of the considered system can be described by x(t) =  n11(t) n 2 1(t) · · · nK1 (t) n12(t) n 2 2(t) · · · nK2 (t) · · · n1J(t) n 1 J(t) · · · nKJ (t)  J×K ∈ ZJ×K+ , (3.5) where nkj (t) denotes the number of class j connections that are currently active and carried on route k. The SMDP state of the system could also be represented by including the number of connections of each class using a particular route and other information about the current request such as whether it is a new or handoff connection request and the traffic type information etc. However, as in [31] [29] and [37], we choose to use a simplified state descriptor in (3.5) in order to reduce the cardinality of the state space. We mainly adopt the SMDP approach introduced in [38]. The idea is to use the same decision epochs, but the decisions are made before, rather than 38 after, the occurrence of an event. In this case, when the system is in certain state, reject/accept decisions must be made for each type of possible arrivals. In the considered mesh networks, given a link l ∈ L, a path may or may not pass link l. All the traffic passing link l should not exceed its capacity. We define f l(k) as f l(k) =  0, if path k does not pass link l;1, if path k passes link l. The state space X of the system consists of any state matrices that satisfies K∑ k=1 J∑ j=1 f l(k)nkj b(j) ≤ B(l),∀l ∈ L, (3.6) where B(l) denotes the link capacity and b(j) is the effective bandwidth required by jth class traffic. In WiMAX-based wireless mesh networks, the bandwidth cor- responds to a set of time slots and frequencies. In this paper, we assume the traffic characteristics, the desired packet-level QoS guarantees, and the scheduling can to- gether be represented by this effective bandwidth. Techniques for computing the effective bandwidth for different traffic characteristics and QoS requirements can be found in [40]. Therefore, the state space of the SMDP can be defined as X = { x ∈ ZJ×K+ : K∑ k=1 J∑ j=1 f l(k)nkj b(j) ≤ B(l),∀l ∈ L } . (3.7) 3.2.2 Decision Epochs and Actions When an incoming connection to be admitted into the system, the mesh router or base station will make a decision whether or not to accept the connection 39 over a specific route. The natural decision epochs are the arrival instances of the new or handoff connections [36]. However, each time a connection departure occurs, the state of the system also changes. Therefore, similar to [38] [29] [37], we choose the decision epochs as the set of all arrival and departure instances. Let t0 = 0, the decision epochs are taken to be the instances tn, n = 1, 2, .... At each decision epoch tn, the network makes a decision for each possible type of connection arrivals that may occur during the time interval (tn, tn+1]. These decisions are collectively referred to as an action. Action a(tn) at decision epoch tn can be defined as a(tn) =  a11(tn) a 2 1(tn) · · · aK1 (tn) a12(tn) a 2 2(tn) · · · aK2 (tn) · · · a1J(tn) a 1 J(tn) · · · aKJ (tn)  J×K , (3.8) where akj (t) denotes the action for class j connections carried on route k. If a k j (t) = 1, a class j user connection that arrives in the interval (tn, tn+1] is admitted to route k as an active user. If akj (t) = 0, the user is rejected. We assume a connection can only be admitted to one route. The set of all possible actions (action space) A can be defined as A = {a : a ∈ {0, 1}J×K , j = 1, 2, ..., J, k = 1, 2, ..., K, ak1j 6= 1, if ak2j = 1 and k1 6= k2, k1, k2 = 1, 2, ..., K}. (3.9) Note that a state transition occurs when a new user connection is admitted or 40 an existing active user departs the system. A user connection that is rejected does not cause a state transition in the process {x(t)}t∈R+ . For a given state x ∈ X, a selected action should not result in a transition to a state that is not in X. In addition, action {0}J×K should not be the only possible action in state {0}J×K . Otherwise, new connections are never admitted into the network and the system cannot evolve. Therefore, for a given state x ∈ X, the admissible action space of Ax ⊂ A is defined as follows: Ax = {a ∈ A : akj = 0 if (x+ eujk) /∈ X, j = 1, ..., J, k = 1, ..., K, a 6= {0}J×K , if x = {0}J×K}, (3.10) where eujk ∈ {0, 1}J×K denotes a matrix containing all zeros except for the (j, k) component, which is 1. (x + eujk) corresponds to an increase of number of class j connections carried on route k by 1. Assuming x(tn) = x, the action at decision epoch tn, which is denoted by a(tn), must be selected from the state-dependent subset of A, i.e., a(tn) ∈ Ax ⊆ A, if x(tn) = x. (3.11) 3.2.3 State Dynamics The state dynamics of the mesh networks can be characterized by the state transition probabilities of the embedded chain Pxy(a) and the expected sojourn time τx(a) for each state-action pair [41]: Pxy(a) can be defined as the probability that at the next decision epoch the system will be in state y if action a is selected at the current state x, while τx(a) is the expected time until the next decision epoch after action a is chosen at the present state x. The definitions of Pxy(a) and τx(a) are: 41 pxy(a) , P(x(tn+1) = y|x(tn) = x, a(tn) = a), (3.12) τx(a) , E{tn+1 − tn|x(tn) = x, a(tn) = a} (3.13) Since connection arrivals and departures are mutually independent Poisson processes, the cumulative process is also Poisson. Therefore, the cumulative event rate is the sum of the rates for all constitution processes. i.e., the resulting process consists of a session arrival process with rate ∑J j=1 λj , if class j connection can be admitted into all the possible routes from the source node to the destination node (akj = 1 if action a admits a class j connection to route k), and a connection departure process with rate ∑K k=1 ∑J j=1 µjn k j . Note that arrivals that are blocked do not constitute an event such that the cumulative process includes only the unblocked arrivals which are also Poisson distributed. The cumulative event rate is the sum of the rates of all constituent processes and the expected sojourn time is the inverse of the event rate. τx(a) = [ K∑ k=1 J∑ j=1 λja k j + K∑ k=1 J∑ j=1 µjn k j ]−1 . (3.14) We can use the decomposition property of a Poisson process to derive the transition probabilities: An event of certain type occurs (e.g. class j connection arrival) with a probability equal to the ratio between the rate of that particular type of event and the total cumulative event rate 1/τx(a). Therefore, the state transition 42 probabilities of the embedded chain, Pxy(a) , are Pxy(a) =  λja k j τx(a), if y = x+ e u jk, j = 1, ..., J, k = 1, ..., K; µjn k j τx(a), if y = x− eujk, j = 1, ..., J, k = 1, ..., K; 0, otherwise. (3.15) Note that in (3.15), y = x + eujk corresponds to an arrival of a new class j connection who is going to be admitted on route k, and y = x− eujk corresponds to a departure of an existing class j connection on route k. The expressions in (3.14) and (3.15) can be explained as follows: if x(tn) = x and a(tn) = a, the new state x(tn+1) and sojourn time in the current state, i.e., tn+1 − tn, are determined by a composition of independent Poisson processes. The resulting process consists of one departure process with rate µj for each active class j connection and an arrival process with rate λj if action a admits a class j user. 3.2.4 Policy and Reward Function For each given state x ∈ X, an action a ∈ Ax is chosen according to a policy ux ∈ U , where U is a set of admissible policies defined as U = {u : X→ A | ux ∈ Ax, ∀x ∈ X}. (3.16) Note that given any u ∈ U , CAC is performed as follows: For the interval (tn, tn+1], the action in (3.11) to be chosen is a(tn), where a(tn) = u(x(tn)). We consider the average reward as the performance criterion. For any policy u ∈ U and an initial state x0 ∈ X, the average reward is defined as Ju(x0) = lim T→∞ 1 T E {∫ T 0 r(x(t), a(t))dt } , (3.17) 43 where T is the time over which the SMDP has evolved and r(x(t), a(t)) is the expected reward until the next decision epoch when a(t) is selected in state x(t). The aim is to find an optimal policy u∗ that has the maximum reward for all initial states, i.e., it satisfies Ju∗(x0) = max u∈U Ju(x0) for all x0 ∈ X (3.18) We assume the embedded chain considered here is a unichain, which is a common assumption in CAC context [29] [31] [37]. With the unichain assumption, there exists an optimal policy and it can be obtained by solving the linear program associated with the SMDP. Singh et al. [29] use the blocking probability as the average cost criterion in the CAC settings. They prove that minimizing the average cost performance criterion is equivalent to minimizing the blocking probability. Similarly, it is shown in [31] that the admitting probability (1 − blocking probability) can be expressed as the average reward criterion. Here, we also use the admitting probability as the average reward criteria. Based on the action a taken in a state x, a reward r(x, a) occurs to the network. As in [31] [37], we use wkj a k j to represent the reward related to akj , where w k j is the weight associated with class j connection that is admitted on route k. In practice, the value of weightwkj is determined by the average revenue generated by accepting a class j connection to route k. The objective is to construct a prioritized admission control policy which maximizes the long-run system revenue by providing different traffic classes with different priorities [42], as will be seen in Section 3.3. Therefore, the reward for state-action pair (x, a) can 44 be expressed as follows r(x, a) = J∑ j=1 K∑ k=1 wkj a k j . (3.19) 3.2.5 Network Layer Blocking Probability Constraints In the current problem formulation, the SNR constraints of all connections in the system can be guaranteed by restricting the state space in (3.6). In addition, it is necessary to put constraints on blocking probabilities of certain classes of traffic or handoff traffic arrivals. For example, in case of network congestion, the network operators may want to have a small blocking probability for premium users and a relatively large blocking probability for economic users. Therefore, we need to formulate connection blocking probability constraints in our model. Since we have derived the expected sojourn time τx(a) for a given state- action pair, the blocking probability P bj for class j can be defined as the fraction of time the system is in a set of states Xbj ⊂ X and the chosen action is in a set of actions Abxj ⊂ A, where xbj ∈ Xbj and Abxj = {a ∈ A : akj = 0, k = 1, ..., K}, P bj = lim T→∞ 1 T E {∫ T 0 K∑ k=1 (1− akj (t))τx(t)(a(t))dt } = ∑ x∈Xbj ∑ a∈A xb j τx(a)∑ x∈X ∑ a∈A τx(a) . (3.20) Expression (3.20) represents the cumulative average blocking probability. The proof of (3.20) can be found in [29]. The constraints related to the blocking probability can be expressed as P bj ≤ βj, j = 1, 2, ..., J, (3.21) 45 where βj is the maximum allowed connection blocking probability for class j traffic. The blocking probability constraints can be easily addressed in the linear programming formulation (3.23) by defining a cost function related to these con- straints. The cost function reflects the rate at which the mesh router/base station incurs administrative costs when it chooses action a while in state x. Cbj (x, a) = K∏ k=1 (1− akj ), j = 1, 2, ..., J. (3.22) 3.3 Optimal Solution to the Joint CAC and Routing Problem Next, we use linear programming to solve the above SMDP. The optimal policy u∗ can be obtained by solving the following linear program [43]: max zxa≥0,x∈X,a∈Ax ∑ x∈X ∑ a∈Ax r(x, a)τx(a)zxa Subject to ∑ a∈Ay zya − ∑ x∈X ∑ a∈Ax Pxy(a)zxa = 0, y ∈ X ∑ x∈X ∑ a∈Ax zxaτx(a) = 1 ∑ x∈X ∑ a∈Ax K∏ k=1 (1− akj )zxaτx(a) ≤ βj, j = 1, 2, ..., J (3.23) The decision variables are zxa, x ∈ X, a ∈ Ax. The term zxaτx(a) can be interpreted as the steady-state probability of the system being in state x and action a is chosen. The first constraint is a balance equation and the second constraint can guarantee that the sum of the steady-state probabilities equals to one. The net- work layer new connection blocking probability and handoff connection blocking 46 probability constraints are expressed in the third one. Let z∗xa denote the optimal solution to (3.23). When sample path constraints are included, the optimal policy obtained will be a randomized policy: the optimal action a∗ ∈ Ax for state x is chosen probabilistically according to the probabilities τx(a)zxa/ ∑ a∈Ax τx(a)zxa. 3.4 Computational Complexity and Implementation Issues In this section, we discuss the computational complexity of the proposed model and some issues about the implementation of the SMDP-based joint CAC and routing scheme. In wireless backhaul mesh networks, the mesh routers/base stations are rela- tively stationary and route changes are infrequent. Our proposed scheme maintains multiple routes and activates one route at a given time. To obtain the optimal CAC and routing policy u∗, we need to first construct the state space X in (3.7) and then solve the liner programming in (3.23). Both procedures can be done offline. Once we have the optimal policy, the network just checks the current system state (the number of connections of each service class on each route) whether there is a new or handoff connection arrival and executes the policy (to which route to admit, reject, or admit with a probability). For some networks, the state space and computational complexity will be very large. As a consequence, linear programming may not be a feasible method to solve the SMDP. In this case, recent advances in reinforcement learning [44] can be used to break the curse of dimensionality. The formulations in this thesis are still 47 applicable in the reinforcement learning method. In order to minimize the dropping probability for handoff connections, we can construct the optimal CAC policy that minimizes the probability of dropping connections or includes handoff connections dropping probability as a constraint. The basic idea is as follows: Assume the handoff connections from adjacent cells arrive according to Poisson processes with rate λj,hf . The total arrival rate of in- coming class j connections is the sum of the rates of new and handoff connections, i.e., λj + λj,hf . Since we do not distinguish between an active new class j con- nections and an active handoff class j connections as their bandwidth requirements are the same, the definition of the state space remains the same as in (3.7). In or- der to explicitly minimize the handoff connection blocking probability, we need to re-define the actions in (3.8) and action space in (3.9). Action a(tn) at decision epoch tn can be re-defined as a(tn) =  a11(tn) a 2 1(tn) · · · aK1 (tn) a12(tn) a 2 2(tn) · · · aK2 (tn) · · · a1J(tn) a 1 J(tn) · · · aKJ (tn) a11,hf (tn) a 2 1,hf (tn) · · · aK1,hf (tn) a12,hf (tn) a 2 2,hf (tn) · · · aK2,hf (tn) · · · a1J,hf (tn) a 1 J,hf (tn) · · · aKJ,hf (tn)  2J×K . (3.24) 48 The set of all possible actions A can be re-defined as A = {a : a ∈ {0, 1}2J×K , j = 1, 2, ..., 2J, k = 1, 2, ..., K, ak1j 6= 1, ifak2j = 1 and k1 6= k2, k1, k2 = 1, 2, ..., K}. (3.25) Since the action space has been re-defined, the admissible action space in (3.10), the mean sojourn time in (3.14), the state transition probabilities in (3.15), and the average reward function in (3.19) will have to be changed accordingly. 49 Chapter 4 Simulation Results and Discussions In this chapter, we evaluate the performance of the proposed joint optimal CAC and routing scheme by simulations. Section 4.1 explains the simulation en- vironments and parameter settings. Section 4.2 presents the simulation results to demonstrate the system performance under the proposed algorithms. 4.1 Simulation Method and Parameter Settings 4.1.1 Simulation Method In order to evaluate the performance of our proposed joint CAC and routing algorithm, we develop a custom simulator using C++ and MATLAB. In this sec- tion, we describe our simulation method and the performance metrics used in our simulations. Our simulation process mainly consists of four steps. First, we define the network topology and setup the simulation configurations. Second, we define the performance metrics that are used to evaluate the simulation results. Third, we execute the simulation programs. Finally, we analyze and verify the simulation results by comparing different scenarios and using different parameter settings. 50 The simulations run on two threads: the flow generator and admission con- troller. The flow generator generates traffic flows from the source node to the des- tination node. The admission controller performs the CAC based on the estimation of the current available bandwidth in the system. We use a uniform random gener- ator to generate the source and the destination for each flow. The traffic flows are generated according to a Poisson process. We change the routes of ongoing con- nections to generate handoff traffic. We vary the connection arrival and departure rates to observe the network performance under different load scenarios. The joint CAC and routing algorithm is invoked when a new or handoff connection arrives or departs. We run the simulations for at least 10000 connections for each data entry. We have specified two metrics to evaluate the performance of our proposed scheme. The first metric is the average network revenue. The average revenue is optimized by prioritizing different service classes using different reward parameters and maximizing a reward function defined in 3.19. The second metric is the new connection blocking probability (Pb) and handoff connection dropping probability (Phf ). Handoff connections receive less stringent admission conditions compared with a new connection, a decrease in handoff dropping probability might lead to a slight increase in the new connection blocking rate. We evaluate the network performance under different scenarios and verify analytical results (i.e., the optimal solution to (3.23)) with simulation results. We show that the proposed scheme can achieve significant performance improvements over the existing CAC scheme in terms of network revenue [23]. In the existing scheme, when a new connection arrives, the CAC module in the base station will 51 estimate the available resources in the mesh network, and the route with the least end-to-end delay is selected to accommodate the new connection. If no such route exists, the connection is rejected. Simulation results also indicate that the handoff dropping probability can be effectively guaranteed by giving priority to handoff users in the proposed scheme. We also give some examples to illustrate optimal policies obtained from the proposed scheme. 4.1.2 Parameter Settings We evaluate the performance of the proposed joint CAC and routing scheme for a WiMAX-based mesh network topology shown in Figure 2.1. We consider the following scenario in our simulations: the wireless backhaul mesh network con- sists of 3 base stations/mesh routers and 3 pairs of unidirectional wireless backhaul links. Assume the wireless communications between mobile stations and base sta- tions/mesh routers and the backhaul transmissions among the mesh routers are all based on IEEE 802.16 TDMA/TDD techniques. For simplicity without losing generality, we simulate a wireless mesh net- work with simplified topology in order to save simulation time and memory spaces. The only differences between the simplified and general topologies are the amount of states in each state space, the number of feasible actions corresponding to the state, and the number of routes between the source node and the destination node. These scale factors do not significantly impact the accuracy of our simulations. Hence, the selection of network topologies in our simulations is not a critical issue and it will not affect the simulation results. We assume the considered WiMAX-based mesh network operates with the 52 Table 4.1: Simulation models and parameters. Parameter Value System bandwidth 7,10 MHz Carriers NFFT 256 Data carriers 192 Sampling factor n 8/7 Guard period ratio (G = Tg/Tb) 1/4 Nakagami fading parameter m 1 Average SNR 15 dB 256-carrier WirelessMAN-OFDM air interface. Of these 256 subcarriers, 192 are modulated for user data, 56 are nulled for a guard band, and 8 are used as permanent pilot signals. The simulation parameters and values are illustrated in Table 4.1. The physical layer adaptive modulation and coding schemes for WiMAX networks are shown in Table 2.1. We assume the bandwidth for each backhaul link is 10 MHz and the band- width between the base station and corresponding subscriber stations is 7 MHz. We consider adaptive modulation with seven transmission rates (i.e., N = 7). For fading channels, we assume a Nakagami-m channel with parameter m = 1. The average SNR γ̄ at each mesh router/base station including the gateway base station is assumed to be 15 dB. We generate two classes of video traffic with arrival rate λ1 and λ2 respec- tively. The service rates are µ1 and µ2. Assume the bandwidth requirements for the two video traffic classes are 1 Mbps and 2 Mbps. The reward weights for the two service classes are w1 = 1 and w2 = 2. We may vary some of these parameters ac- cording to different evaluation scenarios while the rest of them remain unchanged. We use (3.4) to compute the average channel capacity for each transmission 53 link in the mesh network. First we need to get the probability of choosing each mode n, i.e., Pr(n), which can be obtained from (3.3). Then, we can get the useful channel capacity C(n) for using each mode n given the simulation parameters in Table 4.1. Finally, we obtain the calculated the average channel capacity for both backhaul links and direct access links from the base station to mobile stations (3.4). 4.2 Results and Discussions In this section, we study the proposed joint CAC and routing algorithm under various traffic scenarios and describe our simulation results in detail. 4.2.1 Single Service Class We first study a relatively simple scenario when there is only one class of video traffic in the system. We assume the connections arrive according to a Poisson process, the connection interarrival time and the connection holding time are both exponential distributed. Assume the arrival rate is λ = 0.08 and the service rate is µ = 0.03. Figure 4.1 illustrates how the number of ongoing connections in the system evolves with the simulation time. In our considered mesh networks, if we increase the traffic intensity, the av- erage number of connections that are served in the network ( i.e., traffic load ) also increases, which indicates the system is heavily loaded. Although the total revenue of the system increases as the traffic intensity increases, the new connection block- ing probability also increases due to less available bandwidth in the system. Figure 4.2 illustrates the relationship of average number of connections, blocking proba- bility, and average reward as the traffic loads increase in the system. It shows that 54 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 2 4 6 8 10 12 14 16 18 20 Simulation time N um be r o f o ng oi ng c on ne ct io ns Figure 4.1: Simulation time vs. number of ongoing connections. as the traffic arrival rate increases from 0.05 to 0.12 and other parameters remain unchanged, the number of average connections in the system, the total revenue, and the new connection blocking rate all increase. The mesh network can accommodate both new traffic arrivals and handoff traffic arrivals. Figure 4.3 shows the number of ongoing connections for both new and handoff arrivals in the network during a period of time. Assume the arrival rates for new connections and handoff connections are λnew = 0.024 and λhf = 0.008, respectively. The service rate is µ = 0.008. Next, we show in our simulation that our proposed scheme is able to guar- antee dropping probability for handoff connections. In the following examples, we set up a target dropping probability threshold, e.g. two percent, for handoff connec- tions in the mesh network. Assume there is a single class of traffic, the arrival rate 55 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0 5 10 15 Arrival rate λ (connections/second)N um be r o f c on ne ct io ns (a) 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0 0.05 0.1 Arrival rate λ (connections/second) Bl oc ki ng p ro ba bi lity (b) 0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.02 0.04 0.06 0.08 0.1 Arrival rate λ (connections/second) Av er ag e re wa rd (c) Figure 4.2: Traffic load vs. number of ongoing connections, blocking probability, and average reward. for new connections is λnew = 0.015 and the service rate is µ = 0.08. The arrival rate for handoff connections λhf varies from 0.001 to 0.018. Simulation results are shown in Figure 4.4, where the dashed line represents the threshold that is set for the handoff connections. We can see from Figure 4.4 that when the arrival rates for handoff connections increase, both the blocking probability for new connections Pb and the dropping probability for handoff connections Phf will increase. However, 56 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 x 104 −2 0 2 4 6 8 10 12 14 Simulation time N um be r o f c on ne ct io ns in th e ne tw or k New connections Handoff connections Figure 4.3: Simulation time vs. number of ongoing new and handoff connections. when the dropping probability for handoff connections reaches the threshold, it will not go up any more. We also notice that after the dropping probability for handoff connections reaches the threshold, there is a change in the trend of new connection blocking probabilities. This is because the guarantee of handoff connection drop- ping probabilities is accomplished at the expense of a slight increase in the new connection blocking probabilities. Figure 4.5 illustrates the variations of the average number of connections for new and handoff connections in the network. The average number of handoff connections increases as the new connection arrivals λnew increase from 0.001 to 0.018. The average number of new connections in the network decreases slowly before dropping probability of handoff connections reach the threshold. However, it will decrease faster after the dropping probability of handoff connections reaches 57 2 4 6 8 10 12 14 16 18 x 10−3 10−3 10−2 10−1 Handoff connection arrival rate (connections/second) Co nn ec tio n bl oc kin g an d dr op pi ng p ro ba bi liti es Handoff connections New connections Target dropping probability Figure 4.4: Handoff connection arrival rate vs. blocking probability. the threshold, which is consistent with results of Figure 4.4. We also compare our proposed joint CAC and routing scheme with the scheme that does not support handoff connections, i.e., new connections and hand- off connections are treated the same way, and there is no guarantee for handoff connections. From Figure 4.6, we observe that when the traffic load increases from 0.003 to 0.014, the dropping probability Phf of handoff connection will increase for both schemes. Since we have set a threshold (one percent) for the handoff con- nections in our proposed scheme, when Phf reaches the threshold, it will not going up any more. However, the dropping probability in the scheme without considering handoff connections will keep going up. The above examples demonstrate that our proposed optimal CAC scheme can guarantee the handoff blocking probability in different traffic load conditions. 58 2 4 6 8 10 12 14 16 18 x 10−3 1 1.5 2 2.5 3 3.5 4 4.5 5 New connection arrival rate (connections/second) (λ) Av er ag e nu m be r o f c on ne ct io ns New connections Handoff connections Figure 4.5: New connection arrival rate vs. average number of connections. 4 6 8 10 12 14 x 10−3 10−4 10−3 10−2 10−1 Handoff connection arrival rate (connections/second) D ro pp in g pr ob ab ilit y Proposed Scheme No handoff Target dropping probability Figure 4.6: Handoff connection arrival rate vs. dropping probability. 59 4.2.2 Multiple Service Classes The proposed joint CAC and routing scheme supports multiple service classes, which is more flexible in terms of bandwidth allocation. Given limited amount of resources in wireless mesh networks, bandwidth of service flows with low priority can be released and reallocated to service flows with high priority upon requests. We show that the proposed scheme can provide connection-level QoS for differ- ent service classes in backhaul mesh networks and at the same time maximize the network revenue. In the simulations, there are two classes of video traffic in the system with arrival rate λ1, λ2 and service rates µ1, µ2. We prioritize these two service classes by assigning different weight values to them. We evaluate the performance of our proposed scheme under various traffic load scenarios. Figure 4.7 shows the average reward in different traffic loads scenarios. In this example, 40 percent of the total new connection arrivals in the systems are the first class traffic and 60 percent are the second class traffic. The service rates are µ1 = µ2 = 0.03. The bandwidth requirements for the two classes of traffic are 1 Mbps and 2 Mbps. The reward weight are w1 = 1 and w2 = 2. We perform the simulations under different traffic loads λ = 0.2, ..., 0.8. The results are shown in Figure 4.7, we can see that the reward gained in our proposed joint CAC and routing scheme is always better than the existing scheme, where the route with the least end-to-end delay is selected to accommodate the new arrivals. In addition to the reward gain, the network layer connection blocking probability in our proposed scheme is also lower than which from the existing scheme as demonstrated in Figure 4.8. The comparisons of ana- 60 0.02 0.03 0.04 0.05 0.06 0.07 0.08 10−1 New connection arrival rate (connections/second) Av er ag e re wa rd Theoretical value Proposed optimal scheme Existing scheme Figure 4.7: Average reward under different traffic loads. lytical results and simulation result are also shown in Figures 4.7 and 4.8. Figure 4.9 shows the blocking probabilities for two different classes of ser- vices in the condition of various traffic loads and service rates. Assume 40 percent of the traffic is the first class traffic and 60 percent is the second class traffic. The bandwidth requirements for the two classes of traffic are 1 Mbps and 2 Mbps, re- spectively. The reward weights are w1 = 1 and w2 = 2. We can see from Figure 4.9, that the blocking probability for the first class of service with low priority is higher than the second class of service. In addition to the reward gain, the proposed joint CAC and routing scheme is also capable of guaranteeing blocking probability for connections with higher priorities. We demonstrate this in the next example. Assume the second service class has higher priority than the first service class, we set the reward weight pa- 61 0.02 0.03 0.04 0.05 0.06 0.07 10−4 10−3 10−2 10−1 100 New connection arrival rate (connections/second) Bl oc ki ng p ro ba bi liti es Theoretical value (class I) Theoretical value (class II) Proposed optimal scheme (class I) Proposed optimal scheme (class II) Existing scheme (class I) Existing scheme (class II) Figure 4.8: Blocking probability comparisons under different traffic loads. 0.01 0.02 0.03 0.04 0.05 0.06 0.07 10−4 10−3 10−2 10−1 New connection arrival rate (connections/second) (λ) Bl oc ki ng p ro ba bi lity Class I (µ=0.08,w=1) Class II (µ=0.08,w=2) Class I (µ=0.1,w=1) Class II (µ=0.1,w=2) Figure 4.9: Blocking probabilities comparisons of two service classes. 62 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.045 10−4 10−3 10−2 10−1 New connection arrival rate (connections/second) (λ) Bl oc ki ng p ro ba bi lity Class II connection Class I connection Target dropping probability Figure 4.10: Blocking probabilities of two service classes with threshold settings. rameters for the two classes of confections to w1 = 1 and w2 = 2. In order to guarantee the blocking probability for connections of the second service class, we set the threshold blocking probability to one percent. Figure 4.10 shows that the blocking probability for connections of the second service class can be guaranteed within certain threshold. The reward ratios between different classes may vary with different network operators. Figure 4.11 shows average reward increases when the fraction of traffic with larger reward weight increases. The traffic arrival rates are λ1 = 0.016 and λ2 = 0.024. The service rate are µ1 = µ2 = 0.03. We can see from Figure 4.11, the proposed scheme has bigger reward gains than the existing scheme. 63 1 1.5 2 2.5 3 3.5 4 4.5 5 0.034 0.036 0.038 0.04 0.042 0.044 0.046 0.048 Reward rate ratio between two classes of traffic Av er ag e re wa rd Theoretical value Proposed optimal scheme Existing scheme Figure 4.11: Average reward when the reward ratio between two classes of service changes. 4.2.3 Optimal Policy Obtained from the Proposed Scheme In order to make it clear what the proposed optimal joint CAC and routing scheme looks like, next we will give two examples to illustrate the obtained policies. Figure 4.12 illustrates the obtained policy for a single service class scenario. Assume that the network only has new connection arrivals and there are two routes from the source node to the destination node to choose from. It can be observed that the optimal policy is a randomized policy, which means that a connection will be admitted with a probability in some states to each route in a lightly loaded net- work. However, in a heavily loaded network, a new connection may be rejected or admitted to only one route with probability one. Figures 4.13 and 4.14 illustrate the obtained policy for a single service class 64 −1 0 1 2 3 4 5 6 7 8 −1 0 1 2 3 4 5 6 Number of existing connections on the first route N um be r o f e xis tin g co nn ec tio ns o n th e se co nd ro ut e Admit to the first route Admit to the second route Reject Figure 4.12: Illustration of the obtained optimal policy. with handoff connections scenario. The network has set certain QoS constraints (the threshold for handoff dropping probabilities) for handoff connections. We can observe that the number of states where a handoff connection can be admitted is more than the number of states where a new connection can be admitted. This is because the QoS constrains of handoff connections are tighter than that of new connections, and some bandwidth is reserved for handoff connections to guarantee the tighter QoS. 65 −1 0 1 2 3 4 5 6 7 8 −1 0 1 2 3 4 5 Number of existing connections on the first route N um be r o f e xis tin g co nn ec tio ns o n th e se co nd ro ut e Admit to the first route Admit to the second route Reject Figure 4.13: Optimal policy for new connections. −1 0 1 2 3 4 5 6 7 8 −1 0 1 2 3 4 5 Number of existing connections on the first route N um be r o f e xis tin g co nn ec tio ns o n th e se co nd ro ut e Admit to the first route Admit to the second route Reject Figure 4.14: Optimal policy for handoff connections. 66 Chapter 5 Conclusion and Future Work In this chapter, we conclude this thesis with a summary of our contributions and give some suggestions for future work. 5.1 Summary In this thesis, we have mainly studied the key issues in the design of QoS guarantee schemes in WiMAX-based multihop wireless backhaul mesh networks. We have presented an optimal joint CAC and routing scheme in order to provide connection-level QoS guarantees while maximizing the long term network revenue. Computer simulations have been carried out to evaluate the performance of the proposed scheme. In Chapter 2, the research issues related to the resource management for QoS support in WiMAX-based wireless mesh networks have been outlined and some of the solution methods proposed in the literature have been reviewed. In Chapter 3, we have formulated the problem of joint CAC and routing as an SMDP, and used linear programming based algorithm to compute the optimal policy. We have used the long term average reward as the target optimization cri- 67 terion and add blocking probability constraint to the linear programming. Based on the problem formulation, the obtained optimal policy can produce the maximum expected reward for every initial state. QoS constraints such as handoff dropping probabilities can be kept below a target value in the proposed joint CAC and routing scheme. Multiple service classes can be prioritized by imposing different reward rate to each service class. We have demonstrated that the obtained optimal joint CAC and routing policy is a randomized policy. New or handoff connections will be admitted to the system with some probabilities when the system is in certain states. In Chapter 4, we have evaluated the performance of our proposed joint CAC and routing scheme under various traffic loads. Simulation results confirm that the proposed scheme outperforms the existing CAC scheme. 5.2 Future Work Future work can be done in the following areas: • Taking into account packet-level QoS such as packet delay, packet dropping probability. The CAC scheme will evaluate the available network resources by considering the packet-level performance statistics. A joint optimization of connection-level and packet-level QoS control scheme would be an inter- esting extension of the work of this thesis. • Handling the handoff connections between heterogeneous networks (i.e., ver- tical handoff). Wireless mesh networks are expected to support the integra- tion of heterogeneous networks with different QoS requirements. Further 68 research may consider designing a more complicated resource management and CAC scheme which requires cross-layer optimization due to the present of heterogeneous wireless access environment [45]. • Taking into consideration user mobility information. User mobility statistics could be exploited in order to intelligently set the threshold value for handoff connections and reserve resources accordingly. It would be interesting to ex- tend the work of this thesis to study and design a mobility model for wireless mesh networks. 69 References [1] IEEE Std. 802.16-2004, “IEEE standard for local and metropolitan area net- works, part 16: Air interface for fixed broadband wireless access systems,” October 2004. [2] IEEE Std. 802.16e-2005, “IEEE standard for local and metropolitan area net- works, part 16: Air interface for fixed and mobile broadband wireless access systems,” February 2005. [3] B. Li, Y. Qin, C. Low, and C. L. Gwee, “A survey on mobile WiMAX,” IEEE Communications Magazine, vol. 45, pp. 70–75, December 2007. [4] I. Akyidiz and X. Wang, “A survey on wireless mesh networks,” IEEE Com- munications Magazine, vol. 43, pp. S23–S30, September 2005. [5] S. Zhang, F. R. Yu, and V. C. Leung, “Joint connection admission control and routing in IEEE 802.16-based mesh networks,” in Proc. IEEE ICC’08, Beijing, China, pp. 4938–4942, May 2008. [6] S. Zhang, F. R. Yu, and V. C. Leung, “Joint connection admission control and routing in WiMAX-based mesh networks,” submittd to IEEE Trans. Wireless Communications, August 2008. 70 [7] IEEE 802.16’s Mobile Multihop Relay (MMR) Study Group, http://wirelessman.org/sg/mmr/index.html [8] C. Hoymann, K. Klagges, and M. Schinnenburg, “Multihop communica- tions in relay enhanced IEEE 802.16 networks,” in Proc. IEEE PIMRC’06, Helsinki, Finland, pp. 1–4, September 2006. [9] M. Ghaderi and R. Boutaba, “Call admission control in mobile cellular net- works: A comprehensive survey,” Wireless Communications and Mobile Com- puting, vol. 6, pp. 69–93, February 2006. [10] D. Hong and S. S. Rappaport, “Traffic model and performance analysis for cellular mobile radio telephone systems with prioritized and nonprioritized handoff procedures,” IEEE Trans. Vehicular Technology, vol. 35, pp. 77–92, August 1986. [11] R. Ramjee, D. Towsley, and R. Nagarajan, “On optimal call admission control in cellular networks,” Wireless Networks, vol. 3, pp. 29–41, March 1997. [12] B. Li, S. Chanson, and C. Lin, “Analysis of a hybrid cutoff priority scheme for multiple classes of traffic in multimedia wireless networks,” Wireless Net- works, vol. 4, pp. 279–290, July 1998. [13] X. Wu and K. L. Yeung, “Efficient channel borrowing strategy for multime- dia wireless networks,” in Proc. IEEE GLOBECOM’98, Sydney, Australia, pp. 126–131, November 1998. 71 [14] B. Rong, Y. Qian, and K. Lu, “Downlink call admission control in multiservice WiMAX networks,” in Proc. IEEE ICC’07, Glasgow, UK, pp. 5082–5087, June 2007. [15] B. Chang, Y. Chen, and C. Chou, “Adaptive hierarchical polling and cost- based call admission control in IEEE 802.16 WiMAX networks,” in Proc. IEEE WCNC’07, Hong Kong, pp. 1954–1958, March 2007. [16] S. Chandra and A. Sahoo, “An efficient call admission control for IEEE 802.16 networks,” in Proc. IEEE Workshop on Local and Metropolitan Area Networks (LANMAN), New Jersey, USA, pp. 188–193, June 2007. [17] D. Niyato and E. Hossain, “Joint bandwidth allocation and connection ad- mission control for polling services in IEEE 802.16 broadband wireless net- works,” in Proc. IEEE ICC’06, Istanbul, Turkey, pp. 5540–5545, June 2006. [18] X. Guo, W. Ma, Z. Guo, and Z. Hou, “Dynamic bandwidth reservation ad- mission control scheme for the IEEE 802.16e broadband wireless access sys- tems,” in Proc. IEEE WCNC’07, Hongkong, pp. 3418–3423, March 2007. [19] C. Lin, “Admission control in time-slotted multihop mobile networks,” IEEE Journal on Select Areas in Communications, vol. 19, pp. 1974–1983, October 2001. [20] H. Zhu and I. Chlamtac, “Admission control and bandwidth reservation in multihop ad hoc networks,” The International Journal of Computer and Telecommunications Networking, vol. 50, pp. 1653–1674, August 2006. 72 [21] S. Valaee and B. Li, “Distributed call admission control for ad hoc networks,” in Proc. IEEE VTC’02-Fall, Vancouver, pp. 1244–1248, October 2002. [22] L. Georgiadis, P. Jacquet, and B. Mans, “Bandwidth reservation in multihop wireless networks: Complexity and mechanisms,” in Proc. IEEE ICDCS’04, Tokyo, Japan. [23] D. Niyato and E. Hossain, “A radio resource management framework for IEEE 802.16-based OFDM/TDD wireless mesh networks,” in Proc. IEEE ICC’06, Istanbul, Turkey, pp. 3911–3916, June 2006. [24] S. Lee, G. Narlikar, M. Pal, G. Wilfong, and L. Zhang, “Admission control for multihop wireless backhaul networks with QoS support,” in Proc. IEEE WCNC’06, Las Vegas, USA, pp. 92–97, April 2006. [25] Y. Hu, X. Li, H. Chen, and X. Jia, “Distributed call admission protocol for multi-channel multi-radio wireless networks,” in Proc.IEEE GLOBECOM’07, New Orleans, USA, pp. 2509–2513, November 2007. [26] T. Tsai and C. Wang, “Routing and admission control in IEEE 802.16 dis- tributed mesh networks,” in Proc. IFIP International Conference on Wireless and Optical Communications Networks (WOCN), Singapore, pp. 1–5, July 2007. [27] C. Cicconetti, V. Gardellin, L. Lenzini, and E. Mingozzi, “End-to-end band- width reservation in IEEE 802.16 mesh networks,” in Proc. IEEE Interna- tional Conference on Mobile Ad-hoc and Sensor Systems (MASS), Pisa, Italy, pp. 1–6, October 2007. 73 [28] M. Cao, X. Wang, S. Kim, and M. Madihian, “Multihop wireless backhaul networks: A cross-layer design paradigm,” IEEE Journal on Select Areas in Communications, vol. 25, pp. 738–748, May 2007. [29] S. Singh, V. Krishnamurthy, and H. V. Poor, “Integrated voice/data call admis- sion control for wireless DS-CDMA systems,” IEEE Trans. Signal Processing, vol. 50, pp. 1483–1495, June 2002. [30] F. Yu and V. Krishnamurthy, “Effective bandwidth of multimedia traffic in packet wireless CDMA networks with LMMSE receivers: A cross-layer per- spective,” IEEE Trans. Mobile Computing, vol. 5, pp. 525–530, March 2006. [31] F. Yu and V. Krishnamurthy, “Optimal joint session admission control in in- tegrated WLAN and CDMA cellular networks with vertical handoff,” IEEE Trans. Mobile Computing, vol. 6, pp. 126–139, January 2007. [32] M. Alicherry, R. Bhatia, and L. Li, “Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks,” in Proc. ACM MobiCom’05, New York, USA, pp. 58–72, August 2005. [33] N. Nandiraju, D. Nandiraju, L. Santhanam, B. He, J. Wang, and D. Agrawal, “Wireless mesh networks: Current challenges and future directions of web-in- sky,” IEEE Wireless Communications, vol. 14, pp. 1536–1284, August 2007. [34] G. L. Stuber, Principles of Mobile Communications, 2nd ed. Kluwer, 2000. 74 [35] Q. Liu, S. Zhou, and G. B. Giannakis, “Queuing with adaptive modulation and coding over wireless links: Cross-layer analysis and design,” IEEE Trans. Wireless Communications, vol. 4, pp. 1142–1153, May 2005. [36] M. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Pro- gramming. John Wiley, 1994. [37] C. Comaniciu and H. V. Poor, “Jointly optimal power and admission control for delay sensitive traffic in CDMA networks with LMMSE receivers,” IEEE Trans. Signal Processing, vol. 51, pp. 2031–2042, August 2003. [38] K. Ross and D. Tsang, “Optimal circuit access policies in an ISDN environ- ment: A Markov decision approach,” IEEE Trans. Communications, vol. 37, pp. 934–939, September 1989. [39] K. Ross, “Randomized and past-dependent policies for Markov decision pro- cesses with multiple constraints,” Operations Research, vol. 37, pp. 474–477, June 1986. [40] A. Elwalid and D. Mitra, “Effective bandwidth of general Markovian traffic sources and admission control of high speed networks,” IEEE/ACM Trans. Networking, vol. 1, pp. 329–343, June 1993. [41] C. Cassandras and S. Lafortune, Introduction to Distrete Event Systems. Kluwer, 1999. [42] K. Ross and D. Tsang, “The stochastic knapsack problem,” IEEE Trans. Com- munications, vol. 37, pp. 740–747, July 1989. 75 [43] H. Tijms, Stochastic Modelling and Analysis: A Computational Approach. New York: Wiley, 1986. [44] T. K. Das, A. Gosavi, S. Mahadevan, and N. Marchalleck, “Solving semi- Markov decision problems using average reward reinforcement learning,” Management Science, vol. 45, pp. 560–574, April 1999. [45] I. Akyidiz and X. Wang, “Cross-layer design in wireless mesh networks,” IEEE Trans. Vehicular Technology, vol. 57, pp. 1061–1076, March 2008. 76