Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Joint admission control and routing in IEEE 802.16-based mesh networks Zhang, Shiying 2008

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


ubc_2008_fall_zhang_shiying.pdf [ 445.71kB ]
JSON: 1.0066653.json
JSON-LD: 1.0066653+ld.json
RDF/XML (Pretty): 1.0066653.xml
RDF/JSON: 1.0066653+rdf.json
Turtle: 1.0066653+rdf-turtle.txt
N-Triples: 1.0066653+rdf-ntriples.txt
Original Record: 1.0066653 +original-record.json
Full Text

Full Text

Joint Admission Control and Routing in IEEE802.16-Based Mesh NetworksbyShiying ZhangM.E.,Tianjin University, P.R.China, 1999B.E.,Tianjin University, P.R.China, 1996A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIES(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)September 2008c Shiying Zhang, 2008AbstractIn recent years, wireless mesh networking has attracted a growing interestdue 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 wirelessmesh networks.This thesis focuses on the quality of service (QoS) provisioning techniquesin WiMAX-based metropolitan area mesh networks. We study the connection ad-mission control (CAC) and routing issues in the design and operation of wirelessmultihop mesh networks. We propose a joint CAC and routing scheme for multipleservice classes with the objective to maximize the overall revenue from all carriedconnections. Connection-level QoS constraints such as handoff connection drop-ping probability can be guaranteed within a threshold. Multiple service classes canbe prioritized by imposing different reward rates. We apply optimization techniquesto obtain the optimal CAC policies. The optimality criterion is the long-run aver-age reward. We demonstrate that the proposed scheme can the maximum revenueiiobtainable by the system under QoS constraints. We show that the optimal jointpolicy is a randomized policy, i.e., connections are admitted to the system withsome probabilities when the system is in certain states.Simulation results illustrate that the proposed scheme meets our design goalsand outperforms the existing scheme.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . 62 Background and Related Works . . . . . . . . . . . . . . . . . . . . . 82.1 Overview of WiMAX Physical and MAC Layers . . . . . . . . . . 8iv2.1.1 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . 82.1.2 MAC Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 QoS Framework and Service Types . . . . . . . . . . . . . . . . . . 132.2.1 Service Flows . . . . . . . . . . . . . . . . . . . . . . . . . 132.2.2 Scheduling Services . . . . . . . . . . . . . . . . . . . . . 142.3 Mesh Topology Support . . . . . . . . . . . . . . . . . . . . . . . . 172.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.4.1 CAC in Wireless Cellular Networks . . . . . . . . . . . . . 192.4.2 QoS Provisioning in WiMAX Networks . . . . . . . . . . . 202.4.3 CAC in Wireless Multihop Networks . . . . . . . . . . . . 222.4.4 Optimal CAC Schemes . . . . . . . . . . . . . . . . . . . . 253 Joint CAC and Routing . . . . . . . . . . . . . . . . . . . . . . . . . 273.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 273.1.1 WiMAX-based Mesh Network Infrastructure . . . . . . . . 273.1.2 The Joint CAC and Routing Problem . . . . . . . . . . . . 283.1.3 Resource Reservation and CAC Process . . . . . . . . . . . 303.1.4 Wireless Channel Model . . . . . . . . . . . . . . . . . . . 333.2 Formulation of the Joint CAC and Routing Problem as an SMDP . . 343.2.1 State Space . . . . . . . . . . . . . . . . . . . . . . . . . . 373.2.2 Decision Epochs and Actions . . . . . . . . . . . . . . . . 393.2.3 State Dynamics . . . . . . . . . . . . . . . . . . . . . . . . 413.2.4 Policy and Reward Function . . . . . . . . . . . . . . . . . 433.2.5 Network Layer Blocking Probability Constraints . . . . . . 45v3.3 Optimal Solution to the Joint CAC and Routing Problem . . . . . . 463.4 Computational Complexity and Implementation Issues . . . . . . . 474 Simulation Results and Discussions . . . . . . . . . . . . . . . . . . . 504.1 Simulation Method and Parameter Settings . . . . . . . . . . . . . 504.1.1 Simulation Method . . . . . . . . . . . . . . . . . . . . . . 504.1.2 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . 524.2 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . 544.2.1 Single Service Class . . . . . . . . . . . . . . . . . . . . . 544.2.2 Multiple Service Classes . . . . . . . . . . . . . . . . . . . 604.2.3 Optimal Policy Obtained from the Proposed Scheme . . . . 645 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . 675.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70viList of Tables2.1 Modulation and coding schemes for WiMAX. . . . . . . . . . . . . 102.2 WiMAX applications and QoS. . . . . . . . . . . . . . . . . . . . . 164.1 Simulation models and parameters. . . . . . . . . . . . . . . . . . . 53viiList of Figures2.1 WiMAX-based backhaul mesh network. . . . . . . . . . . . . . . . 183.1 Multi-radio multi-channel deployment. . . . . . . . . . . . . . . . . 323.2 The admission control process. . . . . . . . . . . . . . . . . . . . . 374.1 Simulation time vs. number of ongoing connections. . . . . . . . . 554.2 Traffic load vs. number of ongoing connections, blocking probabil-ity, and average reward. . . . . . . . . . . . . . . . . . . . . . . . . 564.3 Simulation time vs. number of ongoing new and handoff connections. 574.4 Handoff connection arrival rate vs. blocking probability. . . . . . . 584.5 New connection arrival rate vs. average number of connections. . . 594.6 Handoff connection arrival rate vs. dropping probability. . . . . . . 594.7 Average reward under different traffic loads. . . . . . . . . . . . . . 614.8 Blocking probability comparisons under different traffic loads. . . . 624.9 Blocking probabilities comparisons of two service classes. . . . . . 624.10 Blocking probabilities of two service classes with threshold settings. 634.11 Average reward when the reward ratio between two classes of ser-vice changes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64viii4.12 Illustration of the obtained optimal policy. . . . . . . . . . . . . . . 654.13 Optimal policy for new connections. . . . . . . . . . . . . . . . . . 664.14 Optimal policy for handoff connections. . . . . . . . . . . . . . . . 66ixList of AbbreviationsAMC Adaptive Modulation and CodingBE Best EffortCAC Connection Admission ControlCID Connection IDCAC Connection Admission ControlDiffServ Differentiated ServicesDSL Digital Subscriber LineertPS extended-real-time Polling ServiceFDD Frequency-Division DuplexGPC Grant Per ConnectionGPSS Grant Per Subscriber StationLOS Line-Of-SightMAC Medium Access ControlMANET Mobile Ad hoc NetworkMMR Mobile Multihop RelayMPEG Moving Picture Experts GroupNLOS Non-Line-Of-SightxnrtPS non-real-time Polling ServiceOFDM Orthogonal Frequency-Division MultiplexingOFDMA Orthogonal Frequency-Division Multiple AccessPDU Protocol Data UnitPMP Point-to-MultipointQoS Quality of ServiceRSVP Resource Reservation ProtocolrtPS real-time Polling ServiceSFID Service Flow IdentifierSLA Service Level AgreementSMDP Semi-Markov Decision ProcessSNR Signal to Noise ratioTDM Time-Division MultiplexingTDD Time-Division DuplexTDMA Time Division Multiple AccessUGS Unsolicited Grant ServiceVBR Variable Bit RateVoIP Voice Over IPWiMAX Worldwide Interpretability for Microwave AccessWLAN Wireless Local Area NetworkxiAcknowledgmentsFirst, 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 writtenwithout 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. Iam 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 Sciencesand Engineering Council of Canada under grant CRDPJ 341254-06.xiiChapter 1IntroductionThis introductory chapter gives a brief description of the motivations andobjectives on the research of connection admission control (CAC) and routing prob-lems in worldwide interoperability for microwave access (WiMAX)-based wirelessmetropolitan area mesh networks. The outline of the thesis is stated in Section MotivationsIn 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 multihopwireless 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 anddigital subscriber line (DSL). WiMAX makes it possible for low-cost deployments1of broadband access for areas that are technically or economically infeasible to in-stall wired cable infrastructure. Initially the WiMAX air interfaces are created tosupport fixed users. The new standard, i.e., IEEE 802.16e-2005 [2] [3], adds fullmobility support for mobile users. Infrastructure meshing creates wireless backhaulmesh among wireless routers/base stations. It reduces system backhaul costs whileincreasing network coverage and reliability. WiMAX, which offers great bandwidthof up to 70 Mbps and long transmission range up to 50 km, is an ideal candidate toserve 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 meshrouters 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 wiredInternet through direct or multihop communications over wireless backbone. Theintermediate nodes serve as relay stations, which help forward the data packets fromthe source node to the destination node. They make the packets forwarding deci-sions based on their knowledge of the network. Mesh architecture offers improvedefficiency, flexibility, as well as high and predictable performance. Most applica-tions in WiMAX-based mesh networks are broadband services with various qualityof service (QoS) requirements. It is essential to provide wireline like QoS guaranteein 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 in2wireless networks. The role of CAC is to restrict the access to the network inorder to prevent network congestion or service degradation for already acceptedusers. A new connection request can be accepted if there are enough free resourcesto meet the QoS requirements of the new connection without violating the QoSconstraints for existing connections. Supporting multiple classes of traffic withdifferent QoS requirements is one of the fundamental requirements for WiMAX-based wireless mesh networks [4]. It has become a desirable feature in wirelesssystems 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. Oncethe charging rates for different service classes are fixed, one way to optimize thesystem revenue is through CAC, i.e., more profitable connections are given higherpriorities for channel access. The CAC scheme for a WiMAX-based mesh networkmust be able to prioritize different types of connections according to their quality ofservice (QoS) requirements. However, most existing CAC schemes are for a singleservice class, and the extension of these schemes to the case of multiple serviceclasses may not be an easy task. Therefore, there is a need to develop a CAC androuting scheme for multiple classes of service with different QoS expectations.When a mobile station moves from the coverage area of a base station to thatof 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 provideseamless mobility support to mobile clients. In multihop wireless mesh networks,the CAC scheme has to handle two types of connections: new connections that3are initiated from its own cell and handoff connections from other base stations ormesh routers. The QoS performance related to these two types of connections aregenerally measured by the new connection blocking probability and handoff con-nection dropping probability. In general, dropping a handoff connection has a morenegative impact than blocking a new connection request. Therefore, channel accesspriority should be given to handoff connections by the CAC module so that theyexperience a lower connection blocking probability than new connections. On thisbasis, the long-run system utilization is maximized while guaranteeing QoS for allconnections.A wireless mesh network consists of a mixture of fixed and mobile nodesthat are interconnected together via wireless links to form a multihop wireless net-work. It has fundamental differences compared with traditional cellular networksor infrastructureless mobile ad hoc networks [4]. Wireless mesh networks supportad 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 minimalmobility and can perform dedicated routing and configuration. In wireless meshnetworks, CAC decisions are closely coupled with route selections. When a newconnection request arrives, the network has to look for a feasible route from thesource 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 existingconnections. Therefore, practical and effective joint optimize CAC and traffic rout-ing schemes are desired in a wireless mesh network in order to achieve optimal4revenues.1.2 ObjectivesThe main objective of this thesis is to study the problems of CAC and routingin WiMAX-based wireless metropolitan area mesh networks. We intend to developa 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 todesign a mechanism that: (1) Optimally decides whether or not to admit as well asto 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. toguarantee the dropping probability of the handoff connections; (3) Prioritizes thetraffic according to the application’s service types and maximizes the total systemrevenue.1.3 ContributionsOur research mainly focuses on studying the CAC and routing problemsin WiMAX-based backhaul mesh networks. Most existing works on the resourcemanagement and QoS provisioning in WiMAX networks are based on single-hoppoint-to-multipoint (PMP) network topology. In this thesis, we intend to develop anoptimal scheme that takes into account the new characteristics introduced throughinfrastructure meshing. The main contributions of this thesis are as follows [5] [6]:5† We propose a semi-Markov decision process (SMDP) based approach whichcombines 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 functionis 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 resultsshow that the proposed scheme meets our design goals and outperforms theexisting scheme.1.4 Organization of the ThesisThe 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 androuting in multihop wireless mesh networks are discussed.6† In Chapter 3, we investigate the key design issues related to the resourcemanagement for QoS support in WiMAX-based backhaul mesh networks.We describe the formulation of the optimal joint CAC and routing schemeand provide a linear programming based approach to get the optimal CACpolicy.† 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 workand some suggestions for future work.7Chapter 2Background and Related WorksIn this chapter, Section 2.1 gives a brief description of the WiMAX physicallayer, medium access control (MAC) layer, and QoS characteristics. Section 2.2gives an overview of related works on CAC and routing schemes in wireless meshnetworks.2.1 Overview of WiMAX Physical and MAC Layers2.1.1 Physical LayerThe original WiMAX standard, IEEE 802.16a, specifics the physical layerof 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-11GHz range and supports non-line-of-sight (NLOS) transmissions. An amendmentto IEEE 802.16-2004, IEEE 802.16e-2005, incorporates a number of enhancements8including better QoS support and the use of scalable orthogonal frequency-divisionmultiple 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 supportmobile users at higher layers and provide more efficient management of networkresource, mobility, and spectrum.WiMAX specifies different air interfaces for different frequency bands. Inthe 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 inconjunction with the MAC layer to provide a reliable end-to-end connection. Thethree 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 anygiven time. Time-division or frequency-division multiple access is employedto support multiple users.† WirelessMAN-OFDMA: also referred to as multiuser-OFDM, is an exten-sion of OFDM. OFDMA allows multiple users to transmit simultaneously onthe different subcarriers per OFDM symbol. Multiple access is provided byaddressing 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 Mbps9Table 2.1: Modulation and coding schemes for WiMAX.Rate ID Modulation Level Coding rate Information Requiredbits/symbol SNR (dB)0 BPSK 1/2 0.5 6.41 QPSK 1/2 1 9.42 QPSK 3/4 1.5 11.23 16QAM 1/2 2 16.44 16QAM 3/4 3 18.25 64QAM 2/3 4 22.76 64QAM 3/4 4.5 24.4depending on the channel bandwidth as well as the modulation and coding schemesused. 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 signalmodulation scheme in each frame depending on the channel conditions on the airlink. Using the channel quality feedback indicator, the mobile stations can providethe base station with feedback on the downlink channel quality. For the uplink, thebase 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’suplink and downlink and assign a modulation and coding scheme that maximizesthe throughput for the available signal-to-noise ratio (SNR). WiMAX standards de-fine seven combinations of modulation and coding rates that can be used dependingon the channel and interference conditions. These possible combinations are shownin Table MAC LayerWiMAX uses a connection-oriented MAC protocol which provides a mech-anism for bandwidth requests and grants. All data transmissions between a basestation and subscriber stations take place in the context of connections. The MAClayer schedules the usage of the network resources, provides QoS differentiation tomultiple users on the shared medium, and guarantees a specified service level foreach 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 stationand subscriber stations.WiMAX supports both frequency-division duplex (FDD) and time-divisionduplex (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 andbroadcasted to the subscriber stations through downlink and uplink map messagesat the beginning of each frame. Therefore, each subscriber station knows when andhow long to receive and transmit data to the base station.In WiMAX, subscriber stations use bandwidth request mechanism to specifyuplink bandwidth requirements to the base station. The MAC protocol supportsdynamic bandwidth allocation. Each subscriber station can request bandwidth fromthe base station by using a bandwidth request message (BW-request) PDU. Twomodes can be used to transmit BW-request PDUs: contention mode and contention-free mode. In the contention mode, a subscriber station sends BW-request PDUs11during the contention period during a frame and a backoff mechanism is used toresolve the the contentions among multiple BW-request PDUs. In the contention-free mode, the base station polls each subscriber station and the subscriber stationresponses by sending back BW-request PDUs. Due to the predictable signalingdelay of the polling scheme, contention-free mode is suitable for QoS-sensitiveapplications.WiMAX supports two modes of bandwidth allocation: grant per connec-tion (GPC) and grant per subscriber station (GPSS). In GPC mode, bandwidth isgranted explicitly to a connection, and the subscriber station uses the granted band-width only for that connection. In GPSS mode, subscriber stations are grantedbandwidth aggregated into a single grant to the subscriber station itself. The sub-scriber station then holds the responsibility for reassigning the bandwidth among itsconnections, 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. ThereforeGPC is suitable for substation stations with fewer users. GPSS has a low overheadbut requires intelligent subscriber stations. It supports hierarchical and distributedscheduling, allowing more complicated reaction to QoS needs. Thus GPSS is moreefficient 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 requestbandwidth, but the base station grants it unsolicited. Bandwidth requirements12are negotiated at connection setup.† Bandwidth request messages. Bandwidth is allocated to subscriber stationsin response to a BW-request sent from subscriber stations to the base station.GPSS subscriber stations can send this message in any bandwidth allocationthey receive. GPC subscriber stations can send it in either a request intervalor 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 BSknow it needs to be polled for bandwidth needs on another connection.2.2 QoS Framework and Service TypesWiMAX standards define a QoS framework and various types of serviceflows. The MAC layer provides differentiated QoS to support different classes ofservices. WiMAX standards accommodate data, voice, video, and other types oftraffic by using appropriate features in the MAC layer.2.2.1 Service FlowsOne 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 layertransport service which provides unidirectional transportation of packets in bothuplink and downlink directions. In WiMAX, all service flows have a 32-bit service13flow identifier (SFID) and active service flows also have a unique 16-bit connectionID (CID) assigned by the base station. QoS is provided according to a set of QoSparameters defined for the service flow. The QoS parameter set defines the neces-sary QoS metrics such as delay, jitter, bandwidth guarantee, and traffic priority forthe applications being delivered.A service flow can be either dynamic or static. Dynamic service flows maybe created, changed, or deleted, which is carried out through a series of MAC man-agement messages: dynamic service addition (DSA) for creating a new serviceflow; dynamic service change (DSC) for changing an existing service flow; anddynamic service deletion (DSD) for deleting an existing service flow. The basestation 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 ormulti-protocol label switching (MPLS) flow labels to enable end-to-end IP-basedQoS.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 flowQoS parameters, such as DSA, DSC, or DSD message, must be approved by an au-thorization module. These changes include requesting a CAC decision, activationof a service flow, or service reduction requests.2.2.2 Scheduling ServicesScheduling services are the data handling mechanisms supported by theMAC scheduler for data transmissions on a connection. WiMAX standards de-fine four scheduling services for uplink flows, each scheduling service has different14QoS requirements:† Unsolicited grant service (UGS). UGS supports real-time service flows thatgenerate fixed size data packets on a periodic basis such as voice over IP(VoIP) without silence suppression. In this case, a fixed amount of bandwidthis allocated to each connection in a static manner, which minimizes delay andjitter. UGS service is suitable for the traffic with very strict QoS constraints.† Real-time polling service (rtPS). rtPS supports real-time service flows thatgenerate variable size data packets on a periodic basis, e.g. moving pictureexperts group (MPEG) video. The service offers real-time, periodic, unicastrequest opportunities, which meet the flows’ real-time needs and allow thesubscriber stations to specify the size of the desired grant. This service re-quires more request overhead than UGS, but supports variable grant sizes foroptimum data transport efficiency.† Extended real-time polling service (ertPS): ertPS is a scheduling mechanismthat builds on the efficiency of both UGS and rtPS. ertPS is designed forreal time traffic with variable data rate, such as VoIP service with silencesuppression, over WiMAX networks. This service is defined only in IEEE802.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 aregular basis, which assures that the flow receives request opportunities even15Table 2.2: WiMAX applications and QoS.QoS Category Applications QoS SpecificationsUGS VoIP * Maximum Sustained RateUnsolicited Guaranteed * Maximum Latency ToleranceService * Jitter TolerancertPS Streaming Audio * Minimum Reserved Ratereal-time Polling Service or Video * Maximum Sustained Rate* Maximum Latency Tolerance* Traffic PriorityertPS Voice with Activity * Minimum Reserved Rateextended-real-time Detection * Maximum Sustained RatePolling Service * Maximum Latency Tolerance* Jitter Tolerance* Traffic PrioritynrtPS File Transfer Protocol * Minimum Reserved Ratenon-real-time (FTP) * Maximum Sustained RatePolling Service * Traffic PriorityBE Data Transfer, Web * Maximum Sustained RateBest Effort Browsing etc. * Traffic Priorityduring 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 toBE service depends on the bandwidth allocation policies for other types ofservice. In general, neither throughput nor delay guarantees are provided forBE service.The data services and applications that WiMAX currently supports are sum-marized in Table Mesh Topology SupportWiMAX standards specify an air interface for broadband wireless accesssystems which support fixed, nomadic, and mobile users. A typical deployment ofWiMAX is in the areas where wired broadband access is too expensive, especiallywhen a low density of users is expected. In order to extend the coverage of a basestation, WiMAX standards define a multihop mesh mode extension to the singlehop PMP network architecture.Mesh networking can be implemented in two basic modes: client meshingand infrastructure meshing. The mesh mode extension, which enables multihoppeer-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. Althoughinfrastructure meshing has not been standardized in WiMAX, the mobile multi-hop relay (MMR) task group [7] [8] is making effort to standardize the multihoprelay-based network infrastructure. It is expected that the infrastructure meshingfunctionality 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 wirelessaccess points to a wired gateway.A WiMAX-based infrastructure mesh network consists of mesh routers/basestations 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 fromone or multiple mesh clients is transmitted through several base stations along amultihop route in the backhaul network to the destination mesh client or an Internet17Mesh 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. InFigure 2.1, the base stations/mesh routers form a backbone mesh network for themesh clients to connect to the Internet.In contrast to traditional mobile ad hoc networks (MANETs) or wirelessclient 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 usuallystationary. The network topology is relatively static. Changes in the topology18are mainly caused by switching on/off the mesh routers.† The mesh routers perform dedicated routing and configuration functionalitiesinstead of the end users. The route selection is less dynamic than MANETswhere the routing protocols are mainly intended for use by mobile nodes.† Wireless backhaul mesh networks are expected to be always connected to theInternet backbone. Usually multiple gateways are deployed to provide theInternet connectivity.† The network traffic in the backhaul mesh network is primarily aggregatedtraffic from many end users. The estimated traffic volume is very high andthe 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 intelligentchannel assignment can be accomplished.† The mesh routers usually have no strong constraints on power consumptions.2.4 Related Work2.4.1 CAC in Wireless Cellular NetworksCAC 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 thanblocking 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 handoff19connections 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 handoffconnections in order to achieve low dropping probabilities. For multiple serviceclasses, an extension of the basic guard channel policy can be achieved by settingdifferent reservation thresholds for each service class [12].Handoff dropping probability can also be controlled by taking into accountthe loading information in the neighbor cells in the admission process. The numberof users in the target cell and neighbor cells are used together to determine themaximum 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 itschannels to its adjacent cells in order to accommodate more handoff connections.The schemes discussed above are mainly designed for the cellular networksin which all mobile stations communicate with the base station directly. Differ-ent from a cellular network, a WiMAX-based wireless mesh network is made upof multiple base stations and mobile stations organized in a mesh topology. QoSprovisioning is more challenging in wireless multihop mesh networks due to theirdecentralized architecture. In wireless multihop mesh networks, routing, CAC,bandwidth reservation, and signaling are tightly coupled together which requiresthe joint design scheme between MAC layer and network layer.2.4.2 QoS Provisioning in WiMAX NetworksCAC plays an important role in the provisioning of guaranteed QoS in WiMAX-based broadband wireless networks. Although much work has been done on the20resource management and CAC in WiMAX networks, most of them are based on asingle hop PMP network topology.In [14], a downlink CAC scheme for multiple classes of services with anobjective to maximize the system revenue is proposed for WiMAX networks. Autility 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 subscriberstations. The CAC scheme uses a cost-based function as the admission criteria andchecks 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. Anew 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 queuelength for each service flow at regular intervals and estimate the specific bandwidthrequirements the service flows.Niyato et al. [17] present a joint adaptive bandwidth allocation and CACscheme 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 costfunctions and decision criteria for bandwidth allocation and CAC. An optimiza-tion problem is formulated and the solution is given by using linear programmingtechniques.21IEEE 802.16e adds the capability to provide full mobility support in WiMAXnetworks. The CAC scheme designed for mobile WiMAX should consider the newfeatures introduced by the full mobility of mobile stations. In [18], a dynamicbandwidth reservation and CAC scheme (DBRAC) for 802.16e broadband systemis proposed. A fraction of the bandwidth, i.e., guard bandwidth, is reserved forhandoff traffic. The total reserved guard bandwidth is dynamically adjusted basedon the bandwidth requirements of both potential handoff traffic and current ongoingreal-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 networktopology, the network operations and radio resource allocation problems are muchmore complicated for multihop mesh networks compared with the single hop ar-chitecture [4]. Therefore, QoS schemes that are designed for a single hop WiMAXnetworks may not work well in a multihop situation in which QoS guarantee isrequired not only over a single hop, but also over an entire wireless multihop path.2.4.3 CAC in Wireless Multihop NetworksQoS routing and CAC schemes have been extensively studied in mobile mul-tihop networks, which are characterized by the lack of infrastructures. In mobilemultihop networks, the mobile stations are free to move randomly and the net-work topology changes frequently. In [19], a CAC scheme over an on-demandrouting protocol is proposed to guarantee bandwidth for real-time applications intime-slotted multihop mobile networks. The times slots for a connection are re-served at each node along the route. On-demand routing and bandwidth reservation22are used to explore all paths between the source node and the destination node, andthe available bandwidth is calculated in a hop-by-hop fashion. The connection isrejected if no routes could be found. All nodes along that path are allocated therequired bandwidth in terms of time slots once a connection is accepted.Zhu et al. [20] propose a CAC and bandwidth reservation framework whichis 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 schemefor mobile ad hoc networks is proposed. A sequence of probing packets is used todetermine a service curve which reflects the network loading status. The measuredservice 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 theuniversal service curve. Otherwise, the connection will be rejected. Georgiadisd etal. [22] also address the problems of CAC and bandwidth reservation in mobile adhoc networks. The proposed method is based on a proactive routing scheme wherenodes obtain routing information through periodic exchange knowledge of networktopologies and states.Wireless backhaul mesh networks have different characteristics comparedwith mobile ad hoc networks. Wireless mesh networks have a relatively stabletopology except for the occasional failure of nodes or addition of new nodes, whilein 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, whileend user devices usually do not have such functionalities in mobile ad hoc net-23works. The traffic being carried on mesh networks is usually aggregated from alarge number of end users. Therefore, it changes infrequently. Particularly, in aninfrastructure 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 arbitrarypair of nodes. Therefore, the QoS provisioning algorithms developed in mobile adhoc networks may not be applied directly in wireless mesh networks.There are some research efforts in the literature studying CAC, bandwidthreservation, and routing techniques in mesh networks. Niyato et al. [23] proposea 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 proposedapproach considers only a single class of service type. In [24], a CAC scheme isproposed for multihop wireless backhaul networks with QoS support. The proposedscheme 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 delayguarantees in multihop wireless mesh networks.Tsai et al. [26] propose a routing and CAC algorithm for WiMAX-basedmesh networks. The route selection process uses the shortest widest effective band-width (SWEB) as the routing metrics. The bandwidth requested of a service flow iscalculated using a token bucket-based model which is based on the delay require-24ments of the new connections. CAC is performed based on the estimation of newbandwidth requirements and current available system capacity. A two-step end-to-end bandwidth reservation scheme in WiMAX-based mesh networks is proposedby Cicconetti et al. [27]. First, the node that initiates the traffic flows conveys thebandwidth requests to the destination node through a PATH message which speci-fies the traffic flow information. Then a RESV message is sent backward from thedestination node to the source node along the path. CAC is performed at each nodeto check whether there is sufficient resource to admit the traffic.In [28], a cross-layer approach to coordinate routing, MAC scheduling, andphysical layer resource allocation in multihop wireless backhaul networks is pro-posed. The gateway base stations perform CAC as well as scheduling. A newtraffic 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 servicesmay not be an easy task. Meanwhile, in wireless mesh networks, handoff of on-going connections between base stations is necessary in order to provide seamlessmobility 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 ofview, handoff connections should be given higher priorities.2.4.4 Optimal CAC SchemesOne of the objectives of a service provider is to differentiate prices amongthe users and maximize the system revenue. CAC plays an important role in op-25timizing the revenue for wireless networks. WiMAX MAC layer is designed todifferentiate services among traffic categories. Therefore, one of the design goalsof CAC schemes in WiMAX-based mesh networks is to find an optimal admis-sion policy which maximizes the network revenue based on the potential rewardsof admitting or rejecting new connections.An admission policy is basically a set of decisions that indicate whether anew connection will be accepted and whether an existing connection will be denieda handoff from one cell to another. Decision theoretic approaches that are basedon Markov decision process have been used to construct the optimal CAC schemesusing standard optimization techniques. In [29] and [30], an SMDP is used tofind the optimal policies in a cellular network. The resulting optimal policy canalso guarantee blocking probability for new or handoff connections. In [31], anSMDP based joint session CAC scheme is proposed in integrated wireless local areanetwork (WLAN) and cellular networks. It can optimally control the admission ofnew 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 CACschemes for WiMAX-based wireless mesh networks.26Chapter 3Joint CAC and RoutingThis 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 jointoptimal CAC and routing scheme using a Markov decision process. The CACmechanism 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 thesystem is maximized. A linear programming based solution for the optimizationproblem in the proposed joint CAC and routing scheme is given in Section System Architecture3.1.1 WiMAX-based Mesh Network InfrastructureWiMAX aims to provide wireless broadband access for both fixed and mo-bile users. It can be deployed in either last mile broadband access scenario orbackhaul wireless network scenario. In the first scenario, the operation is based onPMP single hop transmissions between a base station and multiple subscriber sta-tions. In the second scenario, WiMAX operates as the wireless mesh backhaul in27which 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 networkis shown in Figure 2.1. The network architecture of Figure 2.1 basically consists oftwo parts: WiMAX base stations/mesh routers and subscriber stations/mesh clients.The mesh routers form the multihop infrastructure to support both backhaul accessto the Internet and peer-to-peer communications among them. Each of the meshrouters in the mesh infrastructure also serves as a base station for one or multiplemesh clients within its coverage area. Such an infrastructure mesh would be suitableas a wireless backhaul to integrate existing wireless networks such as IEEE 802.16or IEEE 802.11 based WLAN hotspots. Mesh clients can be fixed, portable, ormobile. Mobile clients roam among base stations and access the wired network viathe gateways.3.1.2 The Joint CAC and Routing ProblemWiMAX defines a connection-oriented MAC layer which effectively enablesend-to-end QoS control. A connection must be established before the transmissionof 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 metricsfor the applications being delivered. In WiMAX-based mesh networks, the mo-bile clients request bandwidth on a per connection basis. When a new or handoff28connection 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 theserequests 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 towhich 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 multimediaapplications. If it is possible to find one or multiple routes that satisfy the bandwidthrequirements, the mesh router will admit the connection and pick one route to ac-commodate the new connection. Resources are also reserved by each mesh routeralong 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 resourcesfor the new connection at the mesh routers. A routing algorithm is needed to findthe best set of mesh routers to support the requested connection. A new connectionis accepted only if all the mesh routers along the route from the source node tothe destination node have enough resources for reservation by that connection. Thesetup process involves a reservation of network resources at the mesh routers alongthe chosen route for the connection. If these resources are not available, the setupprocess fails and the connection is blocked.We have two objectives in designing our CAC scheme in WiMAX-basemesh networks. The first objective is to guarantee connection-level QoS such asdropping probabilities for handoff connections, and the second objective is to max-imize the system revenue. The routing decisions can influence both objectives.29Some 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 achievemaximized network revenue. Therefore, joint consideration of the CAC mechanismand route selection scheme is necessary in order to maximize the system revenueand 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 handoffconnection.The admission of data traffic into a network has both rewards and potentialrisks to the service providers. The rewards come from the utilization of networkresources to earn a certain amount of revenue. However, too much network loadmay cause the degradation of the QoS experience by the already admitted usersand even dropping of existing users, which leads to a potential penalty. A well-designed CAC mechanism can increase the network revenue based on the potentialrewards 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 designof the joint CAC and routing scheme in WiMAX backhaul mesh networks.3.1.3 Resource Reservation and CAC ProcessCAC and resource reservation are two common mechanisms for providingQoS guarantee in wireless networks. When a new connection is to be setup betweena 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 these30resources can be found, they are reserved for the connection and the transmissioncan 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 pathhave sufficient remaining capacity to satisfy the new connection’s bandwidth re-quirement. The remaining capacity means the link capacity minus the bandwidthalready reserved for admitted flows. An optimization problem can be formulatedfor 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 theCAC module selects one route to accept the new connection, resources are reservedby each router along the chosen route. The reservation of network resources canbe performed using a signaling protocol such as the resource reservation protocol(RSVP).Wireless backhaul mesh networks have a relatively stable topology, the meshrouters are relatively fixed and may not have power constraints. The network trafficthat is aggregated from many end users also changes infrequently. Generally all thetraffic is either forwarded to or from a gateway node, while in ad hoc networks thetraffic flows can happen between any pairs of nodes. The behavior of this kind ofnetwork is similar to wired networks since it has infrequent topology changes andlimited 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, weassume each mesh router is equipped with multiple radios, each operating on dif-31Internet 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 networkswhere multiple channels and multiple radios are used in each mesh router. Tworadios are employed for serving the backhaul links, and one more radio is usedfor serving the local mesh clients. Efficient and intelligent channel assignmentschemes are required since the number of total channels is not infinite and may notbe enough in high density nodes scenarios [32]. Ideally, the uplink and downlinkbackhaul radios and the service radio can operate at non-overlapping channels andtherefore eliminates the potential co-channel interferences. Fixed channel assign-ments to these radios are viable as each mesh router can be equipped with multipleradios. Therefore, considering the stationary nature of backhaul mesh networks and32in order to make sure that the admission decisions for new and handoff connectionscan be taken promptly, we use pre-computed paths for each source-destination pairin the backhaul mesh network. This can be achieved during the phase of networkdeployment.3.1.4 Wireless Channel ModelWiMAX 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 toone connection at a time. Assume adaptive modulation and coding scheme is usedin the physical layer to enhance the transmission rate by adjusting modulation levelsaccording to the channel quality. We use the general Nakagami-m channel modelto describe the received SNR. Nakagami-m channel model covers a large class offading channels including Rayleigh channel as a special case when m = 1. Thereceived SNR  per frame is a random variable with a Gamma probability densityfunction [34]:P ( ) = mm m¡1„ m¡(m)exp(¡m „ ); (3.1)where m is the Nakagami fading parameter (m ‚ 0:5), „ := Ef g is the averagereceived SNR, and ¡(m) := R10 tm¡1exp(¡t)dt is the Gamma function.Let N denote the total number of transmission modes available (N = 7 inIEEE 802.16). The SNR range at the receiver can be partitioned into N + 1 non-overlapping intervals with boundary points denoted by ff ngN+1n=0 g. Mode n will bechosen when 2 [ n; n+1); (3.2)33where 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 moden = 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 Table2.1, i.e.,  1 = 6:4dB; 2 = 9:4dB;:::; N = 24:4dB. Based on (3.1) and (3.2), theprobability of choosing mode n is given by [35]Pr(n) =Z  n+1 np ( )d = ¡(m;m n=„ )¡¡(m;m n+1=„ )¡(m) ; (3.3)where ¡(m;x) := R1x tm¡1exp(¡t)dt is the complementary incomplete Gammafunction.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 linkin the wireless mesh network. The capacity can be calculated as followsCavg =NXn=0Pr(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 SMDPIn this section, the joint CAC and routing problem in wireless mesh networksis 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 timeuntil the next decision epoch, and the state at the next decision epoch dependsonly 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 itgeneralize a MDP by (1) allowing decision maker to choose actions whenever thesystem state changes; (2) modeling the system evolution in continuous time; and(3) allowing the time spent in a particular state to follow an arbitrary probabilitydistribution [36]. Therefore, SMDPs are appropriate for modeling continuous-timesystems in which the time between transitions is not constant. We model the systemas an SMDP, instead of a MDP due to the fact that, in a wireless mesh network, thetime 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 touse the linear programming techniques because a nice feature of the linear program-ming formulation (which is not available with policy iteration or value iteration) forsolving an SMDP problem is that it allows optimization over extra constraints suchas maximum allowed blocking probabilities. The optimal policy will in general berandomized when an additional constraint is imposed [39].The SMDP formulation for the problem mainly includes the following threesteps:† First, we define a finite state space for all the active user connections in thenetwork. The link capacity constraint is specified in the construction of the35state 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 homogeneousPoisson 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, adecision must be made as to whether or not to admit and to which route to admit theincoming connection based on the available resources in the mesh network. Thesetime instances are called decision epochs, and decisions are called actions in theSMDP 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 oneach route in the mesh network.The process of the SMDP-based optimal CAC scheme is illustrated in Figure3.2. When an event, e.g., a new connection arrival, occurs, a state is identified bygetting the number of sessions in each of the possible routes from the source nodeto the destination node. Then, an action is found according to the state. The CACcontroller in the base station/mesh router executes the action (reject or admit). Theprocess is repeated when next event occurs.36Figure 3.2: The admission control process.In order to obtain the optimal solution, it is necessary to identify the statespace, decision epochs, actions, state dynamics, rewards, and constraints in themultihop mesh network.3.2.1 State SpaceWe describe a WiMAX-based wireless backhaul mesh network as a set ofnodesN = f1;:::;Ngthat includes all the mobile clients and mesh routers/gatewaysand a set of wireless links L = f1;:::;Lg that includes all the backhaul links as wellas the links between base stations and subscriber stations. Each link l has a totalcapacity of B(l) units of bandwidth. The mesh network offers J different classesof services. Assume the connections arrive according to independent Poisson pro-cesses. The intensity of arrival and the average duration of data connections foreach service class is ‚j and 1=„j, respectively. When a new or handoff connectionof class j, with origination node O and destination node D arrives, it can be eitherrejected (with zero reward) or accepted (with reward r(j), which can be interpretedas the average reward for carrying the jth class connection). In order to accept theconnection, we need to choose a route k from the set of all feasible routes from O37to D, k 2 f1;:::;Kg. Assume the bandwidth requirement for the new arrival isb(j). Each node and each link along the chosen route must have at least b(j) unitsof bandwidth available for the new connection. Although WiMAX-based backhaulmesh networks can support heterogeneous wireless networks, for simplicity, weassume the peer-to-peer transmissions among base stations/mesh routers and thelocal transmissions between base stations and subscriber stations are all based onWiMAX technology.Let X denote the state space and x(t) 2 X denote the state of the meshnetworks at time t, where t 2 R+. The state matrix of the considered system canbe described byx(t) =266666664n11(t) n21(t) ¢¢¢ nK1 (t)n12(t) n22(t) ¢¢¢ nK2 (t)¢¢¢n1J(t) n1J(t) ¢¢¢ nKJ (t)377777775J£K2ZJ£K+ ; (3.5)where nkj(t) denotes the number of class j connections that are currently active andcarried on route k.The SMDP state of the system could also be represented by including thenumber of connections of each class using a particular route and other informationabout the current request such as whether it is a new or handoff connection requestand the traffic type information etc. However, as in [31] [29] and [37], we chooseto use a simplified state descriptor in (3.5) in order to reduce the cardinality of thestate space. We mainly adopt the SMDP approach introduced in [38]. The ideais to use the same decision epochs, but the decisions are made before, rather than38after, 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 2 L, a path may or may notpass link l. All the traffic passing link l should not exceed its capacity. We definefl(k) asfl(k) =8><>: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 satisfiesKXk=1JXj=1fl(k)nkjb(j) • B(l);8l 2 L; (3.6)where B(l) denotes the link capacity and b(j) is the effective bandwidth requiredby 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 trafficcharacteristics, the desired packet-level QoS guarantees, and the scheduling can to-gether be represented by this effective bandwidth. Techniques for computing theeffective bandwidth for different traffic characteristics and QoS requirements canbe found in [40].Therefore, the state space of the SMDP can be defined asX =(x 2ZJ£K+ :KXk=1JXj=1fl(k)nkjb(j) • B(l);8l 2 L): (3.7)3.2.2 Decision Epochs and ActionsWhen an incoming connection to be admitted into the system, the meshrouter or base station will make a decision whether or not to accept the connection39over a specific route. The natural decision epochs are the arrival instances of the newor handoff connections [36]. However, each time a connection departure occurs, thestate of the system also changes. Therefore, similar to [38] [29] [37], we choosethe 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 decisionepoch tn, the network makes a decision for each possible type of connection arrivalsthat may occur during the time interval (tn;tn+1]. These decisions are collectivelyreferred to as an action.Action a(tn) at decision epoch tn can be defined asa(tn) =266666664a11(tn) a21(tn) ¢¢¢ aK1 (tn)a12(tn) a22(tn) ¢¢¢ aK2 (tn)¢¢¢a1J(tn) a1J(tn) ¢¢¢ aKJ (tn)377777775J£K; (3.8)where akj(t) denotes the action for class j connections carried on route k. If akj(t) =1, a class j user connection that arrives in the interval (tn;tn+1] is admitted to routek as an active user. If akj(t) = 0, the user is rejected. We assume a connection canonly be admitted to one route.The set of all possible actions (action space) A can be defined asA = fa : a 2f0;1gJ£K;j = 1;2;:::;J;k = 1;2;:::;K;ak1j 6= 1;ifak2j = 1andk1 6= k2;k1;k2 = 1;2;:::;Kg: (3.9)Note that a state transition occurs when a new user connection is admitted or40an existing active user departs the system. A user connection that is rejected doesnot cause a state transition in the process fx(t)gt2R+.For a given state x 2 X, a selected action should not result in a transition toa state that is not in X. In addition, action f0gJ£K should not be the only possibleaction in state f0gJ£K. Otherwise, new connections are never admitted into thenetwork and the system cannot evolve. Therefore, for a given state x 2 X, theadmissible action space of Ax ‰ A is defined as follows:Ax = fa 2 A : akj = 0if(x+eujk) =2 X;j = 1;:::;J;k = 1;:::;K;a 6= f0gJ£K;ifx = f0gJ£Kg; (3.10)where eujk 2 f0;1gJ£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 jconnections carried on route k by 1.Assuming x(tn) = x, the action at decision epoch tn, which is denoted bya(tn), must be selected from the state-dependent subset of A, i.e.,a(tn) 2 Ax  A;ifx(tn) = x: (3.11)3.2.3 State DynamicsThe state dynamics of the mesh networks can be characterized by the statetransition 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 thatat the next decision epoch the system will be in state y if action a is selected at thecurrent state x, while ¿x(a) is the expected time until the next decision epoch afteraction a is chosen at the present state x. The definitions of Pxy(a) and ¿x(a) are:41pxy(a) ,P(x(tn+1) = yjx(tn) = x;a(tn) = a); (3.12)¿x(a) ,Eftn+1 ¡tnjx(tn) = x;a(tn) = ag (3.13)Since connection arrivals and departures are mutually independent Poissonprocesses, the cumulative process is also Poisson. Therefore, the cumulative eventrate is the sum of the rates for all constitution processes. i.e., the resulting processconsists of a session arrival process with rate PJj=1 ‚j, if class j connection canbe admitted into all the possible routes from the source node to the destinationnode (akj = 1 if action a admits a class j connection to route k), and a connectiondeparture process with rate PKk=1PJj=1 „jnkj. Note that arrivals that are blocked donot constitute an event such that the cumulative process includes only the unblockedarrivals which are also Poisson distributed. The cumulative event rate is the sum ofthe rates of all constituent processes and the expected sojourn time is the inverse ofthe event rate.¿x(a) =" KXk=1JXj=1‚jakj +KXk=1JXj=1„jnkj#¡1: (3.14)We can use the decomposition property of a Poisson process to derive thetransition probabilities: An event of certain type occurs (e.g. class j connectionarrival) with a probability equal to the ratio between the rate of that particular typeof event and the total cumulative event rate 1=¿x(a). Therefore, the state transition42probabilities of the embedded chain, Pxy(a) , arePxy(a) =8>>>><>>>>:‚jakj¿x(a); if y = x+eujk;j = 1;:::;J;k = 1;:::;K;„jnkj¿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 jconnection who is going to be admitted on route k, and y = x¡eujk corresponds toa 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 statex(tn+1) and sojourn time in the current state, i.e., tn+1 ¡ tn, are determined by acomposition of independent Poisson processes. The resulting process consists ofone departure process with rate „j for each active class j connection and an arrivalprocess with rate ‚j if action a admits a class j user.3.2.4 Policy and Reward FunctionFor each given state x 2 X, an action a 2 Ax is chosen according to apolicy ux 2 U, where U is a set of admissible policies defined asU = fu : X ! A j ux 2 Ax;8x 2 Xg: (3.16)Note that given any u 2 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 policyu 2 U and an initial state x0 2 X, the average reward is defined asJu(x0) = limT!11T E‰Z T0r(x(t);a(t))dt ; (3.17)43where T is the time over which the SMDP has evolved and r(x(t);a(t)) is theexpected 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 initialstates, i.e., it satisfiesJu⁄(x0) = maxu2UJu(x0)for allx0 2 X (3.18)We assume the embedded chain considered here is a unichain, which is acommon 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 programassociated with the SMDP.Singh et al. [29] use the blocking probability as the average cost criterionin the CAC settings. They prove that minimizing the average cost performancecriterion is equivalent to minimizing the blocking probability. Similarly, it is shownin [31] that the admitting probability (1 ¡ blocking probability) can be expressedas the average reward criterion. Here, we also use the admitting probability asthe average reward criteria. Based on the action a taken in a state x, a rewardr(x;a) occurs to the network. As in [31] [37], we use wkjakj to represent the rewardrelated to akj, where wkj is the weight associated with class j connection that isadmitted on route k. In practice, the value of weight wkj is determined by the averagerevenue generated by accepting a class j connection to route k. The objective isto construct a prioritized admission control policy which maximizes the long-runsystem 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) can44be expressed as followsr(x;a) =JXj=1KXk=1wkjakj: (3.19)3.2.5 Network Layer Blocking Probability ConstraintsIn the current problem formulation, the SNR constraints of all connectionsin the system can be guaranteed by restricting the state space in (3.6). In addition, itis necessary to put constraints on blocking probabilities of certain classes of trafficor handoff traffic arrivals. For example, in case of network congestion, the networkoperators may want to have a small blocking probability for premium users anda relatively large blocking probability for economic users. Therefore, we need toformulate 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 Pbj for class j can be defined as the fraction oftime the system is in a set of states Xbj ‰ X and the chosen action is in a set ofactions Abxj ‰ A, where xbj 2 Xbj and Abxj = fa 2 A : akj = 0;k = 1;:::;Kg,Pbj = limT!11T E(ZT0KXk=1(1¡akj(t))¿x(t)(a(t))dt)=Px2XbjPa2Axbj¿x(a)Px2XPa2A ¿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 blockingprobability can be expressed asPbj • flj;j = 1;2;:::;J; (3.21)45where flj is the maximum allowed connection blocking probability for class jtraffic. The blocking probability constraints can be easily addressed in the linearprogramming 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 stationincurs administrative costs when it chooses action a while in state x.Cbj(x;a) =KYk=1(1¡akj);j = 1;2;:::;J: (3.22)3.3 Optimal Solution to the Joint CAC and RoutingProblemNext, we use linear programming to solve the above SMDP. The optimalpolicy u⁄ can be obtained by solving the following linear program [43]:maxzxa‚0;x2X;a2AxXx2XXa2Axr(x;a)¿x(a)zxaSubject toXa2Ayzya ¡Xx2XXa2AxPxy(a)zxa = 0; y 2 XXx2XXa2Axzxa¿x(a) = 1Xx2XXa2AxKYk=1(1¡akj)zxa¿x(a) • flj; j = 1;2;:::;J (3.23)The decision variables are zxa, x 2 X, a 2 Ax. The term zxa¿x(a) can beinterpreted as the steady-state probability of the system being in state x and actiona is chosen. The first constraint is a balance equation and the second constraintcan guarantee that the sum of the steady-state probabilities equals to one. The net-work layer new connection blocking probability and handoff connection blocking46probability constraints are expressed in the third one. Let z⁄xa denote the optimalsolution to (3.23). When sample path constraints are included, the optimal policyobtained will be a randomized policy: the optimal action a⁄ 2 Ax for state x ischosen probabilistically according to the probabilities ¿x(a)zxa=Pa2Ax ¿x(a)zxa.3.4 Computational Complexity and ImplementationIssuesIn this section, we discuss the computational complexity of the proposedmodel and some issues about the implementation of the SMDP-based joint CACand routing scheme.In wireless backhaul mesh networks, the mesh routers/base stations are rela-tively stationary and route changes are infrequent. Our proposed scheme maintainsmultiple routes and activates one route at a given time. To obtain the optimal CACand routing policy u⁄, we need to first construct the state space X in (3.7) andthen 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 anew 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 bevery large. As a consequence, linear programming may not be a feasible method tosolve the SMDP. In this case, recent advances in reinforcement learning [44] can beused to break the curse of dimensionality. The formulations in this thesis are still47applicable in the reinforcement learning method.In order to minimize the dropping probability for handoff connections, wecan construct the optimal CAC policy that minimizes the probability of droppingconnections or includes handoff connections dropping probability as a constraint.The basic idea is as follows: Assume the handoff connections from adjacent cellsarrive 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 requirementsare 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 tore-define the actions in (3.8) and action space in (3.9).Action a(tn) at decision epoch tn can be re-defined asa(tn) =26666666666666666666664a11(tn) a21(tn) ¢¢¢ aK1 (tn)a12(tn) a22(tn) ¢¢¢ aK2 (tn)¢¢¢a1J(tn) a1J(tn) ¢¢¢ aKJ (tn)a11;hf(tn) a21;hf(tn) ¢¢¢ aK1;hf(tn)a12;hf(tn) a22;hf(tn) ¢¢¢ aK2;hf(tn)¢¢¢a1J;hf(tn) a1J;hf(tn) ¢¢¢ aKJ;hf(tn)377777777777777777777752J£K: (3.24)48The set of all possible actions A can be re-defined asA = fa : a 2f0;1g2J£K;j = 1;2;:::;2J;k = 1;2;:::;K;ak1j 6= 1;ifak2j = 1andk1 6= k2;k1;k2 = 1;2;:::;Kg: (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.49Chapter 4Simulation Results and DiscussionsIn this chapter, we evaluate the performance of the proposed joint optimalCAC and routing scheme by simulations. Section 4.1 explains the simulation en-vironments and parameter settings. Section 4.2 presents the simulation results todemonstrate the system performance under the proposed algorithms.4.1 Simulation Method and Parameter Settings4.1.1 Simulation MethodIn order to evaluate the performance of our proposed joint CAC and routingalgorithm, we develop a custom simulator using C++ and MATLAB. In this sec-tion, we describe our simulation method and the performance metrics used in oursimulations.Our simulation process mainly consists of four steps. First, we define thenetwork topology and setup the simulation configurations. Second, we define theperformance metrics that are used to evaluate the simulation results. Third, weexecute the simulation programs. Finally, we analyze and verify the simulationresults by comparing different scenarios and using different parameter settings.50The 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 estimationof 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 aregenerated according to a Poisson process. We change the routes of ongoing con-nections to generate handoff traffic. We vary the connection arrival and departurerates to observe the network performance under different load scenarios. The jointCAC and routing algorithm is invoked when a new or handoff connection arrives ordeparts. We run the simulations for at least 10000 connections for each data entry.We have specified two metrics to evaluate the performance of our proposedscheme. The first metric is the average network revenue. The average revenue isoptimized by prioritizing different service classes using different reward parametersand maximizing a reward function defined in 3.19. The second metric is the newconnection blocking probability (Pb) and handoff connection dropping probability(Phf). Handoff connections receive less stringent admission conditions comparedwith a new connection, a decrease in handoff dropping probability might lead to aslight increase in the new connection blocking rate.We evaluate the network performance under different scenarios and verifyanalytical results (i.e., the optimal solution to (3.23)) with simulation results. Weshow that the proposed scheme can achieve significant performance improvementsover the existing CAC scheme in terms of network revenue [23]. In the existingscheme, when a new connection arrives, the CAC module in the base station will51estimate the available resources in the mesh network, and the route with the leastend-to-end delay is selected to accommodate the new connection. If no such routeexists, the connection is rejected. Simulation results also indicate that the handoffdropping probability can be effectively guaranteed by giving priority to handoffusers in the proposed scheme. We also give some examples to illustrate optimalpolicies obtained from the proposed scheme.4.1.2 Parameter SettingsWe evaluate the performance of the proposed joint CAC and routing schemefor a WiMAX-based mesh network topology shown in Figure 2.1. We consider thefollowing scenario in our simulations: the wireless backhaul mesh network con-sists of 3 base stations/mesh routers and 3 pairs of unidirectional wireless backhaullinks. Assume the wireless communications between mobile stations and base sta-tions/mesh routers and the backhaul transmissions among the mesh routers are allbased 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 amountof states in each state space, the number of feasible actions corresponding to thestate, 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 issueand it will not affect the simulation results.We assume the considered WiMAX-based mesh network operates with the52Table 4.1: Simulation models and parameters.Parameter ValueSystem bandwidth 7,10 MHzCarriers NFFT 256Data carriers 192Sampling factor n 8/7Guard period ratio (G = Tg=Tb) 1/4Nakagami fading parameter m 1Average SNR 15 dB256-carrier WirelessMAN-OFDM air interface. Of these 256 subcarriers, 192 aremodulated for user data, 56 are nulled for a guard band, and 8 are used as permanentpilot signals. The simulation parameters and values are illustrated in Table 4.1. Thephysical layer adaptive modulation and coding schemes for WiMAX networks areshown 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). Forfading channels, we assume a Nakagami-m channel with parameter m = 1. Theaverage SNR „ at each mesh router/base station including the gateway base stationis 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 thetwo video traffic classes are 1 Mbps and 2 Mbps. The reward weights for the twoservice 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 transmission53link in the mesh network. First we need to get the probability of choosing eachmode n, i.e., Pr(n), which can be obtained from (3.3). Then, we can get the usefulchannel capacity C(n) for using each mode n given the simulation parameters inTable 4.1. Finally, we obtain the calculated the average channel capacity for bothbackhaul links and direct access links from the base station to mobile stations (3.4).4.2 Results and DiscussionsIn this section, we study the proposed joint CAC and routing algorithm undervarious traffic scenarios and describe our simulation results in detail.4.2.1 Single Service ClassWe first study a relatively simple scenario when there is only one class ofvideo traffic in the system. We assume the connections arrive according to a Poissonprocess, the connection interarrival time and the connection holding time are bothexponential distributed. Assume the arrival rate is ‚ = 0:08 and the service rateis „ = 0:03. Figure 4.1 illustrates how the number of ongoing connections in thesystem 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 ) alsoincreases, which indicates the system is heavily loaded. Although the total revenueof the system increases as the traffic intensity increases, the new connection block-ing probability also increases due to less available bandwidth in the system. Figure4.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 that541000 2000 3000 4000 5000 6000 7000 8000 9000 1000002468101214161820Simulation timeNumber of ongoing connectionsFigure 4.1: Simulation time vs. number of ongoing the traffic arrival rate increases from 0.05 to 0.12 and other parameters remainunchanged, the number of average connections in the system, the total revenue, andthe new connection blocking rate all increase.The mesh network can accommodate both new traffic arrivals and handofftraffic arrivals. Figure 4.3 shows the number of ongoing connections for both newand handoff arrivals in the network during a period of time. Assume the arrival ratesfor 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, weset 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 rate550.05 0.06 0.07 0.08 0.09 0.1 0.11 0.12051015Arrival rate λ (connections/second)Number of connections(a)0.05 0.06 0.07 0.08 0.09 0.1 0.11 0.1200.050.1Arrival rate λ (connections/second)Blocking probability(b)0.05 0.06 0.07 0.08 0.09 0.1 0.11 rate λ (connections/second)Average reward(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 arrivalrate for handoff connections ‚hf varies from 0.001 to 0.018. Simulation results areshown in Figure 4.4, where the dashed line represents the threshold that is set forthe handoff connections. We can see from Figure 4.4 that when the arrival rates forhandoff connections increase, both the blocking probability for new connections Pband the dropping probability for handoff connections Phf will increase. However,561 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8x 104−202468101214Simulation timeNumber of connections in the networkNew connectionsHandoff connectionsFigure 4.3: Simulation time vs. number of ongoing new and handoff connections.when the dropping probability for handoff connections reaches the threshold, it willnot go up any more. We also notice that after the dropping probability for handoffconnections reaches the threshold, there is a change in the trend of new connectionblocking probabilities. This is because the guarantee of handoff connection drop-ping probabilities is accomplished at the expense of a slight increase in the newconnection blocking probabilities.Figure 4.5 illustrates the variations of the average number of connectionsfor new and handoff connections in the network. The average number of handoffconnections increases as the new connection arrivals ‚new increase from 0.001 to0.018. The average number of new connections in the network decreases slowlybefore dropping probability of handoff connections reach the threshold. However,it will decrease faster after the dropping probability of handoff connections reaches572 4 6 8 10 12 14 16 18x 10−310−310−210−1Handoff connection arrival rate (connections/second)Connection blocking and dropping probabilities Handoff connectionsNew connectionsTarget dropping probabilityFigure 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 thescheme 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 handoffconnections. From Figure 4.6, we observe that when the traffic load increases from0:003 to 0:014, the dropping probability Phf of handoff connection will increasefor 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 goingup any more. However, the dropping probability in the scheme without consideringhandoff connections will keep going up.The above examples demonstrate that our proposed optimal CAC schemecan guarantee the handoff blocking probability in different traffic load conditions.582 4 6 8 10 12 14 16 18x 10−311.522.533.544.55New connection arrival rate (connections/second) (λ)Average number of connectionsNew connectionsHandoff connectionsFigure 4.5: New connection arrival rate vs. average number of connections.4 6 8 10 12 14x 10−310−410−310−210−1Handoff connection arrival rate (connections/second)Dropping probability Proposed SchemeNo handoffTarget dropping probabilityFigure 4.6: Handoff connection arrival rate vs. dropping probability.594.2.2 Multiple Service ClassesThe proposed joint CAC and routing scheme supports multiple service classes,which is more flexible in terms of bandwidth allocation. Given limited amount ofresources in wireless mesh networks, bandwidth of service flows with low prioritycan 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 thenetwork revenue.In the simulations, there are two classes of video traffic in the system witharrival rate ‚1, ‚2 and service rates „1, „2. We prioritize these two service classesby assigning different weight values to them. We evaluate the performance of ourproposed scheme under various traffic load scenarios. Figure 4.7 shows the averagereward in different traffic loads scenarios. In this example, 40 percent of the totalnew connection arrivals in the systems are the first class traffic and 60 percent arethe second class traffic. The service rates are „1 = „2 = 0:03. The bandwidthrequirements for the two classes of traffic are 1 Mbps and 2 Mbps. The rewardweight are w1 = 1 and w2 = 2. We perform the simulations under different trafficloads ‚ = 0:2;:::;0:8. The results are shown in Figure 4.7, we can see that thereward gained in our proposed joint CAC and routing scheme is always better thanthe existing scheme, where the route with the least end-to-end delay is selected toaccommodate the new arrivals. In addition to the reward gain, the network layerconnection blocking probability in our proposed scheme is also lower than whichfrom the existing scheme as demonstrated in Figure 4.8. The comparisons of ana-600.02 0.03 0.04 0.05 0.06 0.07 0.0810−1New connection arrival rate (connections/second)Average rewardTheoretical valueProposed optimal schemeExisting schemeFigure 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 percentof the traffic is the first class traffic and 60 percent is the second class traffic. Thebandwidth 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 Figure4.9, that the blocking probability for the first class of service with low priority ishigher than the second class of service.In addition to the reward gain, the proposed joint CAC and routing schemeis also capable of guaranteeing blocking probability for connections with higherpriorities. We demonstrate this in the next example. Assume the second serviceclass has higher priority than the first service class, we set the reward weight pa-610.02 0.03 0.04 0.05 0.06 0.0710−410−310−210−1100New connection arrival rate (connections/second)Blocking probabilities 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.0710−410−310−210−1New connection arrival rate (connections/second) (λ)Blocking probabilityClass 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.620 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04 0.04510−410−310−210−1New connection arrival rate (connections/second) (λ)Blocking probability Class II connectionClass I connectionTarget dropping probabilityFigure 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 toguarantee the blocking probability for connections of the second service class, weset the threshold blocking probability to one percent. Figure 4.10 shows that theblocking probability for connections of the second service class can be guaranteedwithin certain threshold.The reward ratios between different classes may vary with different networkoperators. Figure 4.11 shows average reward increases when the fraction of trafficwith 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.631 1.5 2 2.5 3 3.5 4 4.5 50.0340.0360.0380.040.0420.0440.0460.048Reward rate ratio between two classes of trafficAverage rewardTheoretical valueProposed optimal schemeExisting schemeFigure 4.11: Average reward when the reward ratio between two classes of servicechanges.4.2.3 Optimal Policy Obtained from the Proposed SchemeIn order to make it clear what the proposed optimal joint CAC and routingscheme 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 routesfrom the source node to the destination node to choose from. It can be observedthat the optimal policy is a randomized policy, which means that a connection willbe 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 oradmitted to only one route with probability one.Figures 4.13 and 4.14 illustrate the obtained policy for a single service class64−1 0 1 2 3 4 5 6 7 8−10123456Number of existing connections on the first routeNumber of existing connections on the second routeAdmit to the first routeAdmit to the second routeRejectFigure 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 canobserve that the number of states where a handoff connection can be admitted ismore than the number of states where a new connection can be admitted. Thisis because the QoS constrains of handoff connections are tighter than that of newconnections, and some bandwidth is reserved for handoff connections to guaranteethe tighter QoS.65−1 0 1 2 3 4 5 6 7 8−1012345Number of existing connections on the first routeNumber of existing connections on the second routeAdmit to the first routeAdmit to the second routeRejectFigure 4.13: Optimal policy for new connections.−1 0 1 2 3 4 5 6 7 8−1012345Number of existing connections on the first routeNumber of existing connections on the second routeAdmit to the first routeAdmit to the second routeRejectFigure 4.14: Optimal policy for handoff connections.66Chapter 5Conclusion and Future WorkIn this chapter, we conclude this thesis with a summary of our contributionsand give some suggestions for future work.5.1 SummaryIn this thesis, we have mainly studied the key issues in the design of QoSguarantee schemes in WiMAX-based multihop wireless backhaul mesh networks.We have presented an optimal joint CAC and routing scheme in order to provideconnection-level QoS guarantees while maximizing the long term network revenue.Computer simulations have been carried out to evaluate the performance of theproposed scheme.In Chapter 2, the research issues related to the resource management for QoSsupport in WiMAX-based wireless mesh networks have been outlined and some ofthe solution methods proposed in the literature have been reviewed.In Chapter 3, we have formulated the problem of joint CAC and routing asan SMDP, and used linear programming based algorithm to compute the optimalpolicy. We have used the long term average reward as the target optimization cri-67terion and add blocking probability constraint to the linear programming. Basedon the problem formulation, the obtained optimal policy can produce the maximumexpected reward for every initial state. QoS constraints such as handoff droppingprobabilities can be kept below a target value in the proposed joint CAC and routingscheme. Multiple service classes can be prioritized by imposing different rewardrate to each service class. We have demonstrated that the obtained optimal jointCAC and routing policy is a randomized policy. New or handoff connections willbe admitted to the system with some probabilities when the system is in certainstates.In Chapter 4, we have evaluated the performance of our proposed joint CACand routing scheme under various traffic loads. Simulation results confirm that theproposed scheme outperforms the existing CAC scheme.5.2 Future WorkFuture work can be done in the following areas:† Taking into account packet-level QoS such as packet delay, packet droppingprobability. The CAC scheme will evaluate the available network resourcesby considering the packet-level performance statistics. A joint optimizationof 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. Further68research may consider designing a more complicated resource managementand CAC scheme which requires cross-layer optimization due to the presentof heterogeneous wireless access environment [45].† Taking into consideration user mobility information. User mobility statisticscould be exploited in order to intelligently set the threshold value for handoffconnections and reserve resources accordingly. It would be interesting to ex-tend the work of this thesis to study and design a mobility model for wirelessmesh networks.69References[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 accesssystems,” February 2005.[3] B. Li, Y. Qin, C. Low, and C. L. Gwee, “A survey on mobile WiMAX,” IEEECommunications 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 controland 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 androuting in WiMAX-based mesh networks,” submittd to IEEE Trans. WirelessCommunications, August 2008.70[7] IEEE 802.16’s Mobile Multihop Relay (MMR) Study Group,[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 forcellular mobile radio telephone systems with prioritized and nonprioritizedhandoff procedures,” IEEE Trans. Vehicular Technology, vol. 35, pp. 77–92,August 1986.[11] R. Ramjee, D. Towsley, and R. Nagarajan, “On optimal call admission controlin 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 schemefor 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 multiserviceWiMAX 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.16networks,” 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,” IEEEJournal on Select Areas in Communications, vol. 19, pp. 1974–1983, October2001.[20] H. Zhu and I. Chlamtac, “Admission control and bandwidth reservation inmultihop ad hoc networks,” The International Journal of Computer andTelecommunications 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 multihopwireless networks: Complexity and mechanisms,” in Proc. IEEE ICDCS’04,Tokyo, Japan.[23] D. Niyato and E. Hossain, “A radio resource management framework for IEEE802.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 controlfor multihop wireless backhaul networks with QoS support,” in Proc. IEEEWCNC’06, Las Vegas, USA, pp. 92–97, April 2006.[25] Y. Hu, X. Li, H. Chen, and X. Jia, “Distributed call admission protocol formulti-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 Wirelessand Optical Communications Networks (WOCN), Singapore, pp. 1–5, July2007.[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 backhaulnetworks: A cross-layer design paradigm,” IEEE Journal on Select Areas inCommunications, 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 inpacket 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,” IEEETrans. Mobile Computing, vol. 6, pp. 126–139, January 2007.[32] M. Alicherry, R. Bhatia, and L. Li, “Joint channel assignment and routingfor 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 modulationand 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 controlfor delay sensitive traffic in CDMA networks with LMMSE receivers,” IEEETrans. 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 trafficsources 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


Citation Scheme:


Usage Statistics

Country Views Downloads
China 13 0
Japan 3 0
United States 2 0
India 2 1
Russia 2 0
Germany 1 0
Italy 1 0
City Views Downloads
Beijing 13 0
Unknown 4 1
Tokyo 3 0
Ashburn 2 0
Pisa 1 0
Mumbai 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items