Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Stochastic control of inter-switch handoff and location update in wireless cellular networks Wong, Wai-Shuen Vincent 2000

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

Item Metadata

Download

Media
831-ubc_2000-487393.pdf [ 5.65MB ]
Metadata
JSON: 831-1.0065351.json
JSON-LD: 831-1.0065351-ld.json
RDF/XML (Pretty): 831-1.0065351-rdf.xml
RDF/JSON: 831-1.0065351-rdf.json
Turtle: 831-1.0065351-turtle.txt
N-Triples: 831-1.0065351-rdf-ntriples.txt
Original Record: 831-1.0065351-source.json
Full Text
831-1.0065351-fulltext.txt
Citation
831-1.0065351.ris

Full Text

Stochastic Control of Inter-Switch Handoff and Location Update in Wireless Cellular Networks by WAI-SHUEN VINCENT WONG M.A.Sc, University of Waterloo, 1996 B.Sc, University of Manitoba, 1994 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA April 2000 © W. S. Vincent Wong, 2000 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of £iee7&tcBL & C o ^ w r P f t The University of British Columbia Vancouver, Canada r.J-Date ^ / MPlRClA . £ 0 0 0 DE-6 (2788) Abstract One of the issues in mobility management is to support handoff. When the mobile user moves from one location to another, the network should ensure that all ongoing connections are rerouted to another access point in a seamless manner. Part of our work focuses on connection rerouting due to inter-switch handoff in wireless A T M networks. Although fast local connection rerouting minimizes handoff delay, the end-to-end path after rerouting may become "suboptimal", which implies an inefficient use of network resources. Path optimization may be necessary afterwards. Our research begins with the following question: "How often should path optimization be performed?" To this end, we propose three path optimization schemes (namely: exponential, periodic, and Bernoulli) , which are simple to implement. Closed-form solutions of the optimal operating point are derived for each scheme. We further investigate this problem and propose a stochastic model to determine the optimal time to initiate path optimization. L in k cost and signaling cost functions are introduced to capture the trade-off between the network resources utilized by a connection and the signaling and processing load incurred on the network. Results indicate that the optimal policy derived from our model has a better performance compared to other heuris-tics. Another issue in mobility management is to track the location of the users between call arrivals. Although it has been shown that the distance-based location update algorithm has a better performance than the movement and timer based schemes, the determination of the optimal distance threshold is often based on certain unrealistic assumptions. We propose a stochastic model to study the distance-based update algorithm. Our model is applicable to arbitrary cell topologies and the cell residence time can follow general distri-butions. We consider Markovian movement patterns in which the probability that the i i mobile user moves to a particular neighboring cel l can depend on the location of the current cell or a list of cells recently visited. Results indicate that the distance thresholds determined from our model have a better performance than those derived from a hexago-nal cell configuration with random walk movement pattern. iii Tab le o f C o n t e n t s Abstract ii List of Figures viii List of Tables xi Acknowledgements xii Chapter 1 Introduction 1 1.1 Related Work on Inter-Switch Handoff 3 1.1.1 Virtual Connection Tree 4 1.1.2 Multicast-Based Rerouting 4 1.1.3 Path Extension 4 1.1.4 Path Rerouting 5 1.1.5 Two-Phase Handoff Scheme : 6 1.2 Related Work on Location Update 8 1.2.1 Location Area (LA)-based 9 1.2.2 Selective L A Update 9 1.2.3 Profile-based 10 1.2.4 Movement-based 10 1.2.5 Timer-based 11 1.2.6 Distance-based 11 1.2.7 Predictive Distance-based 12 1.2.8 State-based 13 1.2.9 L e Z i Update 13 iv 1.3 Related Work on Terminal Paging 14 1.3.1 Blanket Polling 14 1.3.2 Shortest-Distance-First ...15 1.3.3 Sequential Paging based on User's Location Probability 16 1.3.4 Velocity Paging. 17 1.4 Motivations and Objectives.: 17 1.5 Contributions of the Thesis • 20 1.6 Organization of the Thesis 21 Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 23 2.1 Introduction 23 2.2 Path Optimization Schemes 24 2.2.1 QoS-based 24 2.2.2 Network-based 24 2.2.3 Timer-based 25 2.2.4 Handoff-based 25 2.3 Analytical Model 26 2.3.1 Exponential Path Optimization Scheme 28 2.3.2 Periodic Path Optimization Scheme 29 2.3.3 Bernoulli Path Optimization Scheme 30 2.4 Simulation Model 31 2.5 Results and Discussions 34 2.6 Summary 39 Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 46 vi 3.1 Introduction 46 3.2 Model Formulation 47 3.2.1 Semi-Markov Decision Process Model 47 3.2.2 State Transition Probability Function 52 3.2.3 Cost Functions 54 3.3 Optimality Equations 56 3.3.1 Value Iteration Algorithm 57 3.3.2 Structure of the Optimal Policy 59 3.4 Implementation Aspects 59 3.5 Model Extensions 60 3.5.1 Extension to Mobile-to-Mobile Connection 61 3.5.2 Extension to QoS Constraints 62 3.6 Numerical Results and Discussions 63 3.6.1 Simulation Model 64 3.6.2 Results ; 65 3.7 Summary • 68 Chapter 4 Distance-based Locat ion Update 75 4.1 Introduction 75 4.2 Model Formulation 76 4.3 Distance-based Location Update Algorithm 80 4.3.1 Linear Cel l Configuration , 80 4.3.2 Hexagonal Cel l Configuration 85 4.3.3 Arbitrary Ce l l Topology 88 4.4 Numerical Results and Discussions 91 4.4.1 Paging Delay Constraints 91 4.4.2 Cel l Residence Time Distributions 93 4.4.3 Cel l Topologies 95 4.4.4 Performance Comparisons ..96 4.4.5 Sensitivity Analysis 98 4.5 Summary • 98 Chapter 5 Conclusions 108 5.1 Summary 108 5.2 Further work 1 11 Bibliography H3 Appendix A. Expected Cost for the Exponential Path Optimization Scheme 122 Appendix B. Expected Cost for the Periodic Path Optimization Scheme 126 Appendix C. Expected Cost for the Bernoulli Path Optimization Scheme 129 Appendix D. Semi-Markov Decision Processes 132 Glossary of Acronyms 141 List of Figures Figure 1.1 (a) Path extension scheme, (b) Path rerouting scheme 5 Figure 1.2 Two-phase handoff protocol 7 Figure 1.3 Classification of different paging schemes 15 Figure 1.4 Hexagonal cell configuration 16 Figure 1.5 Structure of the thesis 21 Figure 2.1 A 20-node random graph with node degree of 3; minimum distance between any two nodes is 15 33 Figure 2.2 Exponential path optimization scheme 41 Figure 2.3 Periodic path optimization scheme 41 Figure 2.4 Bernoulli path optimization scheme 42 Figure 2.5 Analytical and simulation results of the periodic path optimization scheme 42 Figure 2.6 Analytical and simulation results of the exponential path optimization scheme 43 Figure 2.7 Analytical and simulation results of the Bernoulli path optimization scheme 43 Figure 2.8 Comparisons between different path optimization schemes 44 Figure 2.9 Variation of the average call termination time 44 Figure 2.10 Variation of the time between inter-switch handoff 45 Figure 3.1 Timing diagram 48 Figure 3.2 Expected total cost versus link cost rate 70 Figure 3.3 Expected number of path optimizations versus link cost rate 70 Figure 3.4 Expected total cost versus inter-switch handoff rate 71 viii Figure 3.5 Expected number of path optimizations versus inter-switch handoff rate . 71 Figure 3.6 Expected total cost versus call termination rate 72 Figure 3.7 Expected number of path optimizations versus call termination rate . . 72 Figure 3.8 Min imum expected total cost of the optimal policy versus inter-switch handoff rate for various distributions. 73 Figure 3.9 Min imum expected total cost versus link cost rate for various inter-switch handoff rate distributions 73 Figure 3.10 Variation of the average call termination time 74 Figure 3.11 Variation of the average time between inter-switch handoffs.. . 74 Figure 4.1 Timing diagram -76 Figure 4.2 One-dimensional linear model 80 Figure 4.3 Hexagonal cell configuration 85 Figure 4.4 Update boundary derived from an arbitrary cell configuration. Location update is performed whenever the mobile terminal moves to any cells labeled with " B " 90 Figure 4.5 Expected total cost versus call arrival rate under various delay constraints 100 Figure 4.6 Optimal distance threshold versus call arrival rate under various delay constraints 100 Figure 4.7 Expected total cost versus cell crossing fate under various delay constraints 101 Figure 4.8 Optimal distance threshold versus cell crossing rate under various delay constraints... '. 101 Figure 4.9 Expected total cost versus location update cost under various delay constraints 102 Figure 4.10 Optimal distance threshold versus location update cost under various delay constraints 102 ix Figure 4.11 Optimal distance threshold versus cell crossing rate under various cell residence time distributions and delay constraints: (a) maximum paging delay constraint = 1, (b) maximum paging delay constraint = 2, (c) no paging delay constraint 103 Figure 4.12 Expected total cost versus cell crossing rate under various cell residence time distributions and paging delay constraints: (a) maximum paging delay = 1, (b) maximum paging delay = 2, (c) no paging delay constraint 104 Figure 4.13 Representation of a cellular network topology by a graph model. . . . 105 Figure 4.14 Graph model with an average node degree of 4. The nodes represent the location of the base stations. A n edge between two nodes represents those two base stations are neighbors to each other 105 Figure 4.15 Optimal distance threshold distribution 106 Figure 4.16 Cost ratio versus call arrival rate and location update cost under different cell crossing rate 106 Figure 4.17 (a) Cost ratio versus percentage change in average time between call arrivals under different call arrival rate; (b) Cost ratio versus percentage change in average cell residence time under different cell crossing rate. . 107 Figure A . l Timing diagram 122 x List of Tables Table 2.1 Summary of parameters used in simulation and analytical models xi Acknowledgements First of al l , I would like to thank my supervisor, Professor Victor Leung, for his guidance, advice, and support throughout my graduate studies. I am also grateful to him for allowing me to attend and present our work at various conferences. During different stages on my research, I have the privilege to work with two other people. The first one is Dr. Henry Chan who is now teaching at the Hong Kong Polytech-nic University. The second one is Dr. Mark Lewis who is now teaching at the University of Mich igan , A n n Arbor. I thank them sincerely for their comments on my work on path optimization in wireless A T M networks. Mark 's guidance on Markov decision processes also gave me another perspective on location update problems. A major part of this thesis is based on the results in Markov decision processes. I learned this branch of mathematics through a graduate course taught by Professor Mart in Puterman. A n d I thank him for offering such an interesting course. I would like to thank Professor Cyr i l Leung and Professor Son Vuong for serving on my dissertation committee. The area of wireless/mobile A T M was first introduced to me by my former supervisor, Professor Jon M a r k , at the Univers i ty of Water loo. He also wrote the recommendation letters for me so that I could have the opportunity to pursue my Ph .D. studies. For that, I thank him wholeheartedly. I would also like to thank all the former and present members in the Communica-tions group for their help and support, especially Hansen Wang and Peter Chong. I wish to express my sincere thanks to my parents, Denise F. C. Chan and Stanley C . M . Wong, for their constant love and support throughout all these years. • Many thanks to my wife, Joyce Lee, for her love, understanding, and encourage-ment which helped me go through this difficult yet rewarding process. This work was supported in part by the (1) Natural Sciences and Engineering xii X l l l Research Counc i l of Canada ( N S E R C ) under a Postgraduate Scholarship and Grant N o . OGP0044286; (2) Communications Research Centre, Industry Canada, under the Fessenden Postgraduate Scholarship; and (3) the University of Bri t ish Columbia under the University Graduate Fellowship. Chapter 1 Introduction In recent years, there has been tremendous growth in the use of wireless cellular telephony for communications. Mobi le subscribers are increasing at an exponential rate and wi l l continue to increase in the near future. There are various wireless networks currently in use or proposed in the literature. Examples include Personal Communication Services (PCS), paging [78], wireless Asynchronous Transfer Mode (ATM) [28] [29], mobile Inter-net Protocol (IP) [44], and mobile satellite. The next generation wireless broadband net-works, such as the International Mobi le Telecommunications 2000 (IMT-2000) [30] defined by the International Telecommunication Union (ITU) and the Universal Mobi le Telecommunications System ( U M T S ) defined by the European Telecommunications Stan-dards Institute (ETSI), aim to unify many of these diverse systems existing today into a seamless radio infrastructure capable of offering a wide range of services. In order to utilize the radio spectrum efficiently, a cellular architecture is used in wireless networks. The geographical coverage area is partitioned into cells, each served by a base station. Mobi le users and their terminals are connected to the network via the base stations. Cells can have different sizes: picocells are commonly used in indoor environ-ments; microcells are used within cities; macrocells are used in highway and rural areas. Smaller cells use less power for transmissions and allow a greater frequency re-use. One of the issues in mobility management is to track the location of the users and their terminals between call arrivals. Since mobile users are free to move within the coverage area, the network only maintains the approximate location of each user. When a connection needs to be established to a particular user, the network has to determine the user's exact location. The operation of informing the network about the current location of the mobile user is known as location update, and the operation of determining the exact location of the mobile user is called terminal paging or searching. 1 Chapter 1 Introduction 2 It is well-known that there is a trade-off between location update and paging. If the mobile terminal updates its location whenever it crosses a cell boundary, then the network can maintain its precise location. However, i f the cal l arrival rate is low, the network wastes its resources by processing frequent update information and the mobile terminal wastes its power by transmitting the update signal. O n the other hand, i f the mobile terminal does not perform location update frequently, a large coverage area has to be paged when a call arrives, which wastes the radio bandwidth. Thus, the central problem of location management is to devise algorithms which minimize the overall cost for location update and paging. Another issue in mobility management is to maintain the connections when the mobile user moves from one access point to another. The operation of transferring a mobile connection from one access point to another is known as handoff or handover. Handoffs for multimedia traffic differ from conventional voice handoffs in that a mobile user may have several active connections with different bandwidth requirements and quality-of-service (QoS) constraints. The handoff function should ensure that all ongoing connections are rerouted to another access point in a seamless manner. In other words, the design goal is to minimize any service disruption and degradation during and after the handoff process. Since handoff may involve operations such as rerouting, resource allocation, and packet forwarding, the handoff protocols are network dependent. For example, the handoff operations for Mobi le IP are different than those for Wireless A T M . On the other hand, the same location update and paging mechanism can be deployed in different networks with minor modifications. The only difference is how the update information is stored, dissem-inated, and retrieved within the network. In our work, we focus on (1) handoff management in wireless ATM networks, and Chapter 1 Introduction 3 (2) location update in wireless cellular networks. A m o n g different kinds of wireless network technologies, wireless A T M is chosen because of its potential to support different kind of services with QoS guarantee. A number of prototypes reported in the literature such as the M A G I C W A N D from Advanced Communications Technologies & Services (ACTS) [39] and the WATMnet from N E C [51] have demonstrated the feasibility of using A T M to support high speed services in the wireless domain. There are two types of handoffs in wireless A T M networks, namely intra-switch handoffs and inter-switch handoffs. A n intra-switch handoff occurs when the mobile terminal moves from one base station to another,, and both base stations are connected to the same switch. A n inter-switch handoff occurs when the mobile terminal moves to a new base station that is connected to another switch. In both cases, channel al location is performed at the new base station. However, connection rerouting is also required for inter-switch handoffs. Several local connection rerouting protocols have been proposed in the literature. Although most of these protocols incur a low handoff delay, the end-to-end path after rerouting may become "suboptimal", which implies an inefficient use of network resources. Part of our work focuses on optimizing the path after an inter-switch handoff. The rest o f this chapter is organized as follows: Sections 1.1-1.3 describe the related work on inter-switch handoff, location update, and terminal paging, respectively. Section 1.4 discusses the motivations and objectives of our work. Section 1.5 presents an overview of our contributions. Section 1.6 describes the scope of this thesis. 1.1 Related Work on Inter-Switch Handoff Several connection rerouting protocols to facilitate inter-switch handoffs for wireless A T M networks have been proposed in the literature. In this section, we summarize these protocols and point out the strengths and weaknesses of each method. Chapter 1 Introduction 4 1.1.1 Virtual Connection Tree Cal l and handoff control for wireless A T M networks based on hierarchical grouping of backbone and wireless network resources is proposed in [1]. A virtual connection tree is a collection of base stations and A T M switching nodes and links. The root of the tree is an A T M switching node and the leaves of the tree are the base stations. The advantage of the proposed scheme is that as long as the mobile terminals stay within the virtual connection tree, they can move to any base stations without involving the network call processor. However, the proposed solution minimized the handoff processing delay at the expense of allocating more resources that may not be used. Over allocation of network resources is contrary to the original idea of flexibility and efficiency inherent in A T M networks. In addition, packet loss may occur and out-of-sequence packets may be received at the mobile terminal or the end station. 1.1.2 Multicast-Based Rerouting In this method [25], the controlling switch establishes a multicast connection to the cur-rent serving base station and its neighboring base stations. When A T M packets arrive for the mobile terminal, the controlling switch wi l l multicast those A T M packets to this multi-cast connection group. Thus when the mobile terminal moves to one of the neighboring base stations, A T M packets are. already available. After each handoff, the controlling switch has to add the new neighboring base stations to the multicast connection group as well as delete the previous neighboring base stations from the group. The major drawback of this scheme is that extra buffer space has to be allocated to the neighboring base sta-tions. In addition, with a large number of mobile terminals, frequent handoff increases the processing load of the controlling switch. 1.1.3 Path Extension The rationale behind path extension is to extend the original connection to the switch to Chapter 1 Introduction 5 Remote terminal Remote terminal Crossover Switch Anchor Switch Anchor Switch I M 'M Target Switch c (a) (b) Mobile terminal bj, Switch A Base Station Original Connection Extended Connection Partial Connection Figure 1.1 (a) Path extension scheme, (b) Path rerouting scheme. which the new base station is connected. A s shown in Figure 1.1 (a), the switches to which the original and new base stations are connected are usually referred, respectively, as the anchor switch and the target switch [6]. The path extension method extends the connection from the anchor switch to the target switch during handoff. The minimum hop path between these two switches is usually chosen as the extended path. The path extension scheme is fast and simple to implement. QoS degradations such as packet loss, duplicate packets, and mis-sequence packets do not occur. However, since the extended path is longer than the original one, certain QoS requirements, such as packet transfer delay and packet delay variation, may not be guaranteed after a handoff. In addition, data looping may occur when the mobile terminal moves back to the previous anchor switch later. This leads to an inefficient utilization of network resources. 1.1.4 Path Rerouting Path rerouting can be considered as a generalization of the path extension scheme. In path Chapter 1 Introduction 6 extension, the anchor switch extends the original connection to the target switch, while in path rerouting, any switch along the original connection can be selected to set up a branch connection to the target switch. As shown in Figure 1.1 (b), the switch chosen to perform this function is usually referred to as the crossover switch [61]. Depending on the perfor-mance criteria of the crossover switch discovery algorithms [61][14], the end-to-end path after rerouting may not be optimal. The optimal path is defined as the best path among a set of feasible paths that can satisfy the prescribed end-to-end QoS constraints. The performance comparisons between various connection schemes including the virtual connection tree, path extension, path rerouting, and multicast-based rerouting are reported in [11]. Results indicate that the virtual connection tree incurs the lowest handoff delay at the expense of the highest bandwidth requirements. The multicast-based rerouting has the shortest disruption time but a relatively high buffer requirements. The performance of path extension and path rerouting lie in between the virtual connection tree and the multicast-based rerouting schemes. However, these analytical results are only true for a hierarchical symmetric tree network configuration. Performance comparisons between these rerouting schemes in another network topology may be different. 1.1.5 Two-Phase Handoff Scheme The two-phase handoff protocol proposed in [65] combines the advantages of path exten-sion and path rerouting. The two-phase handoff protocol consists of two stages: path extension and possible path optimization. Referring to Figure 1.2, path extension is per-formed for each inter-switch handoff, and path optimization is performed whenever it is necessary. During path optimization, the network determines the optimal path between the source and the destination (i.e., the path between the remote terminal and the current target switch in Figure 1.2) and transfers the user information from the old path to the new path. The major steps during path optimization execution generally involve [20]: Chapter! Introduction 7 Remote Terminal Mobile's movements Original Connection Extended Connection _ . . _ Optimal Connection Figure 1.2 Two-phase handoff protocol. 1. Determining the location of the crossover switch; 2. Setting up a new branch connection; 3. Transferring the user information from the old branch connection to the new one; 4. Terminating the old branch connection. Since the mobile terminal is still communicating over the extended path v ia the current base station while path optimization takes place, this gives enough time for the network to perform the necessary functions while minimizing any service disruptions. Notice that the path optimization process described above is not restricted to the two-phase handoff protocol. It can also be applied to other connection rerouting protocols where the location of the crossover switch is not the optimal one. In addition, when the mobile terminal moves to another switch during the execution of path optimization, path extension can still be used to extend the connection to the target switch. In [47], an experimental testbed is used to compare the performance between Chapter I Introduction ) 8 different rerouting schemes. Results indicate that for the two-phase handoff scheme, path extension from the old base station to the new base station in the first phase incurs a small handoff delay (6.5 ms). For CD-quali ty audio (128 kb/s), there is no packet loss during path extension and that only 1% of the subsequent path optimizations suffer a loss of a single packet. To ensure a seamless path opt imiza t ion , some important issues need to be addressed: 1. How to determine the location of the crossover switch? 2. How can the service disruptions be minimized during path optimization? 3. When and how often should path optimization be performed? For the first issue, a crossover switch determination algorithm based on P N N I (Private Network-to-Network Interface) standard [10] was proposed in [20]. Five different crossover switch algorithms for wireless A T M local area networks are proposed in [61]. For the second issue, packet loss and packet mis-sequencing can be prevented by using appropriate signaling and buffering at the anchor and crossover switches during path optimization, see [20][70][71]. However, little work has been reported on the third issue. 1.2 Related Work on Location Update In order to reduce its location uncertainty, each mobile terminal has to report its location from time to time. The location update procedure begins with an update message sent by the mobile over the uplink control channel, which is followed by some signaling proce-dures which update the database. Location update algorithms can be divided into two main groups: static and dynamic. In a static algorithm, location update is triggered based on the topology of the network. In a dynamic algorithm, location update is based on the user's call and mobility patterns. In this section, we summarize various location update schemes currently in use or proposed in the literature. Chapter 1 Introduction 9 1.2.1 Location Area (LA)-based In this update algorithm, the coverage area is partitioned into a number of location areas (LAs) . Each L A contains a group of cells. A l l base stations within the same L A broadcast the identifier (ID) of its L A periodically. Each mobile terminal compares its registered L A ID with the current broadcast L A ID. Location update is triggered i f the two IDs are differ-ent. Upon a call arrival for a particular mobile terminal, all the cells within its current L A are polled simultaneously, ensuring a success within a single step. The LA-based update scheme is widely adopted by the current cellular systems, including the E I A / T I A IS-41 [22] and the G S M (Global System for Mobi le Communication) networks [41]. The main drawback of this scheme is that for an L A with a large number of cells, significant amount of radio bandwidth is consumed in paging for each call arrival. In addition, mobile termi-nals located close to an L A boundary may perform excessive location updates as they move back and forth between two L A s . 1.2.2 Selective LA Update The rationale behind the selective LA update scheme [58] is that a daily commuter may cross a number of L A s on his way to and from work. However, he may only stay in some L A s for a very short period of time. Rather than performing location update whenever he crosses a new L A , the update process at certain L A s can be skipped. In [58], an analytical model is introduced in which the interconnections of the L A s are characterized by a graph model. The movement model is Markovian. The residence time in each L A follows a geo-metric distribution. A genetic algorithm is used to obtain the near-optimal solutions. For low residing probability in certain L A s and high update cost, results show that this scheme incurs a lower location management cost than the conventional LA-based scheme. For implementat ion, information regarding the transition probabi l i t ies and residence time is required. To estimate the transition probabilities between L A s for a Chapter 1 Introduction 10 particular user, his movements throughout the day can be observed over long periods of time. Since the LA-based update scheme is used in the current P C S networks, information about the frequency of his transition from one L A to another can be retrieved from the database. 1.2.3 Profile-based The goal of the profile-based location update scheme [45] (also known as the alternative location strategy [60]) is to reduce the update cost by taking advantage of the user's mobility pattern. The network maintains a profile for each user, which includes a sequen-tial list of the most likely L A s that the user is located at different time periods. This list is sorted from the most to the least likely L A where a user can be found. When a call arrives, the L A is being paged sequentially. A s long as the mobile terminal moves between L A s within the list, no update is necessary. Location update is performed only when the mobile terminal moves to a new L A which is not on the list. The list may be derived from the user's movement history. 1.2.4 Movement-based In the movement-based update scheme [4] [12], each mobile terminal counts the number of boundary crossings between cells incurred by its movements. Location update is per-formed when this number exceeds a predefined movement threshold M (e.g., M = 6) . This scheme allows the dynamic selection of the movement threshold on a per-user basis. For implementation, the mobile terminal only needs a counter to count the number of cell boundary crossings. The counter is reset whenever it reaches the movement thresh-old. The cell identification code proposed in [43] can also be used to identify the boundary crossing. In [4], an analytical model is introduced to determine the optimal movement threshold. The model is applicable for mesh and hexagonal cell configurations under the Chapter 1 Introduction 11 assumptions of a general cel l residence time distribution and symmetric random walk movement pattern. The maximum paging delay constraint is considered and a shortest-distance-first order paging scheme is used. 1.2.5 Timer-based In the timer-based update scheme [12][53], each mobile terminal updates its location every T time units (e.g., T = 1 hour). This scheme does not require the mobile terminal to record or process location information during the time between updates. For implemen-tation, the timer threshold can be programmed into the mobile terminal by a hardware or software timer. A n analytical model is introduced in [53] to study the timer-based scheme. Assuming the Gaussian distribution on user location probability and Poisson call arrivals, the update period which minimizes the cost of location update and paging is derived. Results show that the timer-based scheme performs substantially better than the LA-based scheme. A variation of the timer-based scheme, called the adaptive threshold scheme, is proposed in [42]. The mobile terminal transmits an update message every T time units, where the parameter T (referred as the location registration threshold) is not a constant, but varies with the current signaling load on the uplink control channel of the base station. Numerical results, under the assumptions of a linear cell configuration and random walk movement pattern, show that the adaptive threshold scheme has a better performance than the static timer-based scheme. 1.2.6 Distance-based In the distance-based update scheme [12][27][38], each mobile terminal tracks the dis-tance it has moved (in number of cells) since the last update, and transmits an update sig-nal whenever the distance exceeds a certain threshold. For implementation, the mobile terminal requires some knowledge about the cell topology. In order to identify the cells Chapter! Introduction 12 within the distance threshold or the cells along the distance threshold boundary, the mobile terminal needs to download a set of these cell IDs after each location update. The distance-based scheme has been studied extensively. In [12], the authors compared the movement, timer, and distance-based schemes, under the assumptions of random walk mobility movements and a ring topology of cells. Analyt ical results show that the distance-based scheme gives the lowest location management cost. In [38], the distance-based update scheme is formulated as an optimization problem. The goal is to minimize the expected total cost for update and paging between cal l arrivals. Under a linear cel l configuration and symmetric random walk movement pattern, the optimal distance threshold is determined by dynamic programming. In [27], an iterative approach is used to compute the optimal distance threshold in a hexagonal cell configuration under the assumption of symmetric random walk mobility pattern. 1.2.7 Predictive Distance-based In the predictive distance-based update scheme [35], the mobile terminal reports both its location and velocity during the update process. Based on the above information, the net-work determines the probability density function of the mobile's location, which is used to predict the mobile's location in future time. This prediction information is made available to both the network and the mobile terminal. The mobile terminal checks its position peri-odically and performs location update whenever its distance exceeds the threshold dis-tance measured from the predicted location. Upon a call arrival, the network pages the mobile terminal starting from the predicted location (which may be the one that performed the last update) and outward, in a shortest-distance-first order, until the mobile terminal is found. For performance analysis, a Gauss-Markovian process is used to model the user's mobi l i ty pattern. The Gauss-Markov model captures the correlation of the mobile 's Chapter 1 Introduction 13 velocity in time, and can represent different user mobility patterns, including the random walk and the constant velocity fluid-flow model. Numerical results, under the assumptions of an infinite one-dimensional linear model and Poisson call arrivals, show that the predic-tive distance-based scheme has a better performance than the non-predictive one. 1.2.8 State-based In the state-based update scheme [55], the mobile terminal determines whether to perform location update based on its current state. The state information can include the time elapsed or the number of cell crossings since the last update, the cell-distance between the current and last registered locations, or some other criteria. Thus, maintaining different state information corresponds to different location update schemes. In [55], a state-based update scheme is analyzed where the system state includes the current location and the time elapsed since the last update. A time-varying Gaussian process [54] is used to model the user's movement. The sub-optimal solution for the average cost of location update and paging under no paging delay constraint is obtained by a greedy method. Results show that the state-based update scheme achieves a 10% improvement in average cost compared to the timer-based scheme. 1.2.9 LeZi Update The idea of the LeZi update (pronounced as "lazy update") algorithm [16] is based on a compression algorithm proposed by Z iv and Lempel. The L e Z i update algorithm can be considered to be a path-based update scheme in which the movement history rather than the current location is sent in an update message. The movement history consists of a list of zone (i.e., L A or cell) IDs where the mobile terminal has crossed after the last update. The network database maintains the movement history in a compact form by a trie or dig-ital search tree. This trie can be considered to be a part of the user's profile. Upon a call arrival, selective paging based on the trie information is used to locate the mobile terminal. Chapter 1 Introduction 14 1.3 Related Work on Terminal Paging Terminal paging is the process in which the network determines the exact location of a particular mobile terminal. In each polling cycle [27] or search iteration, polling signals are sent over the downlink control channel to all cells where the mobile terminal is likely to be present. A l l the mobile terminals listen to the page message and only the target mobile terminal sends a response message back over the uplink control channel. In each polling cycle, there is a timeout period. If the target mobile terminal replies before the tim-eout, then the paging process is terminated. Otherwise, another group of cells are chosen in the next polling cycle. To avoid call dropping, the mobile terminal must be located within an allowable time constraint. The maximum paging delay corresponds to the maxi-mum number of polling cycles allowed to locate the mobile terminal. For example, i f the maximum paging delay is equal to 1, the mobile terminal has to be located within a single search iteration. Since radio bandwidth is consumed during the paging process, the paging cost is proportional to the number of polling cycles, as well as the number of cells being polled in each cycle. The paging area depends on the information provided by the location update function. The paging cost can be reduced by predicting the current location of the mobile terminal. In this section, we summarize different paging strategies proposed in the litera-ture. A classification of various paging strategies is shown in Figure 1.3. 1.3.1 Blanket Polling In blanket polling, all the cells within the L A in which the mobile terminal is located are being polled simultaneously when a call arrives. Since the mobile terminal is located within the L A , its location can be determined within a single polling cycle. This paging strategy is currently deployed on top of the LA-based update scheme in the existing P C S networks. The major drawback of blanket polling is that since the number of cells within a Chapter 1 Introduction 15 Figure 1.3 Classification of different paging schemes. typical L A is large, the paging cost is very high. 1.3.2 Shortest-Distance-First In this paging strategy, the network pages the mobile terminal starting from the cell where the mobile terminal last updated its location and moving outward, in a shortest-distance-first order. The distance is measured in terms of the number of cells away from the last update location. If a threshold-based update scheme (e.g., distance or movement) is used, the paging area or the residing area of the mobile terminal is bounded [27]. The mobile terminal can be located within a fixed number of polling cycles. The paging delay con-straint can be incorporated by grouping cells with different distances for each polling cycle. Various location update algorithms such as the distance and movement-based schemes have used this paging strategy to determine the location management cost for performance comparisons (e.g., [27][35][38][43]). To illustrate the mechanism of this paging strategy, consider Figure 1.4 in which the cell topology is hexagonal. Suppose the cell labeled 0 is the location where the mobile terminal performed the last update. Assume the distance-based update scheme is used with a distance threshold equal to 4. That is, location update is performed whenever the mobile Chapter 1 Introduction 16 Figure 1.4 Hexagonal cell configuration. terminal moves to any ce l l labeled 4. Wi th no paging delay constraint, the po l l i ng sequence is {0, 1, 2, 3} . That is, cell 0 is polled first. If no response is received from the mobile terminal after a timeout, all the cells labeled 1 are polled in the next polling cycle. This continues until either the mobile terminal sends a response message to the base station or all the cells within the sequence list have been polled. Wi th delay constraints, cells with different labels or distances may be polled as a group in a poll ing cycle. For example, i f the maximum paging delay is equal to 3, the paging sequence list can be {{0 , 1}, {2}, {3}} . That is, cells with label 0 or 1 are polled in the first poll ing cycle. Cells labeled 2 and 3 are polled in the second and third polling cycles, respectively. 1.3.3 Sequential Paging based on User's Location Probability In this paging strategy, the current location of the mobile terminal is predicted based on its location probability distribution. Polling signals are sent only to those cells where the user is likely to be present. A n intuitive result derived in [52] states that: "Given the probability Chapter! Introduction 17 distribution on user location, under no paging delay constraint, the paging cost is mini-mized by sequentially polling the cells in decreasing order of probability". Clearly, the uniform location distribution gives the highest paging cost and delay. When there is a maximum paging delay constraint, a group of cells can be polled together in each polling cycle. Dynamic programming [46] can be used to determine the optimal group size which minimizes the paging cost. In [52], the authors obtained the optimal paging sequence that results in the minimum paging cost with average paging delay constraint. The sequential paging strategy has been used in [53][55] for performance analysis of the timer and state-based update schemes. 1.3.4 Velocity Paging The velocity paging scheme [68] aims to reduce the paging cost by decreasing the size of the paging area. The goal is achieved by grouping the users into different velocity classes, based on their velocity at the location update instant. When a call arrives, the paging area is dynamically generated based on the user's last registration time and the velocity class index. The velocity paging scheme can be deployed on top of other location update algo-rithms. To implement this paging strategy, information such as the mobile's last known location, velocity class index, and the last registration time is required at the user's data-base profile. When the velocity paging scheme is combined with the movement-based update algorithm, numerical results [68] indicate that this combined scheme may not always result in a reduction in cost as compared to the LA-based update scheme with blan-ket polling. The authors determine the range of cell radius under which this combined scheme should be used based on system parameters. 1.4 Motivations and Objectives To facilitate inter-switch handoff in wireless A T M networks, several connection rerouting Chapter 1 Introduction 18 protocols have been reported in the literature. Although most of these protocols incur a low handoff delay, the path after rerouting may become suboptimal, which implies an inefficient use of network resources. Path optimization is required to reroute the connec-tion to a more efficient route. However, the question of when path optimization should be performed has not been addressed in the literature, and is investigated in the first part of the thesis. Our work is motivated by the fact that path optimization does not have to be performed after each inter-switch handoff. Although path optimization can increase the network utilization by rerouting the connection to a more efficient route, transient QoS degradations such as packet loss and an increase in packet delay variation may occur. In addit ion, i f there are a large number of mobile users with high movement patterns, performing path optimization after each path extension w i l l increase the processing load of certain switches and the signaling load of the network. We believe the decision of performing path optimization should be based on several factors including: (1) the amount of network resources (e.g., bandwidth) utilized by the connection, (2) the QoS require-ments of the connection, (3) the remaining time of the connection, or (4) signaling load of the network. Another part of our work focuses on the determination of the optimal update boundary for the distance-based location update algorithm. Although it has been shown that the distance-based update algorithm has a better performance than the L A , movement, and timer based update schemes, the models used to determine the optimal distance threshold are often under certain unrealistic assumptions. First of a l l , structured cel l configurations are commonly used. For example, mesh or hexagonal cell configurations are used in two-dimensional models (e.g., [27]), and a linear model is used in the one-dimensional case (e.g., [12][38]). Although these cell topologies simplify the analytical Chapter 1 Introduction 19 computation, they do not give an accurate representation of a realistic cellular network topology, where the size of each cell depends on the transmit power, receiver sensitivity, antenna radiation pattern, and propagation environment, and the number of neighboring cells varies from ce l l to ce l l . We believe a graph model such as the one proposed in [16][58] is more appropriate to characterize the topology of a cellular network. ^ Another commonly used assumption is related to the cell residence time distribu-tion. The cell residence time denotes the amount of time that the mobile terminal stays in a particular cell before moving to another one. Most of the work assumed the cell residence time follows a geometric (or exponential) distribution. A n d the distribution is assumed to be independent and identically distributed (i.i.d.) for all cells. The major limitation of the i.i .d. geometric residence time assumption is that it does not capture an accurate represen-tation of individual user mobility patterns, where a user may stay at certain locations (e.g., his home or office) for a relatively long period of time. The last assumption is related to the movement models. The symmetric random walk is commonly used to characterize individual movement behavior. When the mobile user leaves a cell , there is an equal probability that the user w i l l move to any neighboring cells. Although the random walk model simplifies the analysis, its main drawback is that the direction of the mobile user is not taken into account. In general, a mobile user usually travels with a destination in mind. Thus, the mobile's location in the future is likely to be correlated with its movement history. Another goal of our work is to develop an analytical model which can eliminate some of the unrealistic assumptions commonly used and w i l l allow us to determine the optimal distance threshold (or update boundary) for the distance-based location update algorithm. Chapter 1 • Introduction 20 1.5 Contributions of the Thesis The main contributions of this dissertation are as follows: • Exponential, periodic, and Bernoulli path optimization schemes: To address the issue of when and how often path optimization should be performed, we propose three heuristics for the initiation of path optimization. These heuristics may not be optimal but they are simple to implement. Given the cost and mobility parameters, closed-form solutions of the expected cost per call and the optimal operating point are derived for each scheme. • Optimal policy to initiate path optimization: We further investigate the path optimization problem and propose a stochastic model to determine the optimal time to perform path optimization. L ink cost and signaling cost functions are introduced to capture the trade-off between the network resources utilized by a connection and the signaling and processing load incurred on the network. Different link cost functions can be assigned to different service classes with different bandwidth requirements. Different signaling cost functions can be used based on the complexity of the path optimization procedures and the signaling load of the network. The time between inter-switch handoffs can follow any arbitrary general distributions. A stationary deterministic optimal policy is obtained. Results indicate that the optimal policy derived from our model has a better performance compared to some other heuristics. • Distance-based location update algorithm: We propose a novel stochastic model to analyze the distance-based location update algorithm. The model is formulated as a semi-Markov decision process. There is a cost function associated with location update and another cost function associated with terminal paging. Unl ike other models, our model is applicable to arbitrary cell topologies and the cell Chapter 1 Introduction 21 Chapter 1 Path Optimization: Heuristics Chapter 2 Appendices A - C Interest Path Optimization: Optimal Policy Chapter 3 Appendix D Distance-Based Location Update Chapter 4 Appendix D Chapter 5 4 1— w Figure 1.5 Structure of the thesis. residence time can follow general distributions. We consider Markovian movement patterns in which the probability that the mobile user moves to a particular neighboring cell can depend on the location of the current cell or a list of cells recently visited. Results indicate that the distance thresholds determined from our model have a better performance than those derived from a hexagonal cell configuration with random walk movement pattern. 1.6 Organization of the Thesis Depending on the specific interest the reader may choose one of the following chapter routes (see Figure 1.5). The thesis is organized as follows: In Chapter 2, we propose and analyze three path optimization schemes to facilitate the two-phase handoff protocol. A Chapter 1 Introduction 22 discrete time analytical model and a discrete event simulation model are proposed to eval-uate the performance of different path optimization schemes. We present performance comparisons between these schemes. In Chapter 3, we propose a stochastic model to determine the optimal time to perform path optimization. We describe the optimality equa-tions, the value iteration algorithm, and the structure of the optimal policy. We present numerical results and compare the optimal policy with four heuristics. In Chapter 4, we propose a stochastic model to determine the optimal update boundary for the distance-based location update algorithm. We present numerical results for the hexagonal cell con-figuration and random graph topology. Finally, Chapter 5 concludes the thesis with a sum-mary of the presented work and some suggestions for future work. "lake a methodandtry it. If it fails, admit itfrankfy and try another. 'But above all, try something." frankfin 'Delano Roosevelt, 1881-1945. Chapter 2 Path Optimization for Inter-Switch Hand-off: Heuristics 2.1 Introduction In this chapter, we address the issue of when to perform path optimization for the two-phase handoff protocol by proposing and analyzing three path optimization schemes, namely: exponential, periodic, and Bernoulli [72]-[75]. These schemes may not be optimal but they are simple to implement. A n analytical model and a simulation model are used to analyze the performance of these path optimization schemes. For the discrete time analytical model, closed-form solution of the expected cost per call and the optimal operating point are derived for each path optimization scheme. The analytical results are corroborated by simulations based on non-hierarchical random graphs. The rest of this chapter is organized as follows. The proposed path optimization schemes are described in Section 2.2. The discrete time analytical model and the discrete event simulation model proposed for evaluating the performance of different path optimi-zation schemes are explained in Sections 2.3 and 2.4, respectively. Section 2.5 discusses the analytical and simulation results. A summary is given in Section 2.6. The proofs of the expected cost per ca l l for the proposed path optimization schemes are shown in the Appendices A - C . 23 Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 24 2.2 Path Optimization Schemes A s mentioned in Chapter 1, the end-to-end path after connection rerouting may not be optimal. For a large number of mobile connections within the fixed network, these sub-optimal paths can lead to an inefficient use of network resources. In this section, we discuss different methods to initiate path optimization. Path optimization schemes are grouped into four types, namely, QoS-based, network-based, timer-based, and handoff-based. These path optimization initiation schemes are described below. 2.2.1 QoS-based A s the name implies, QoS-based path optimization schemes trigger path optimization of each mobile connection based on its current QoS measures. For example, path optimiza-tion can be initiated .if the number of hops of the path is greater than a certain number, or i f the average end-to-end packet transfer delay bound is violated. To implement those QoS-based path optimization schemes, information about the quality of the current path in terms of the defined QoS measures (e.g., hop count, current average delay, delay variation) must be maintained by the network. 2.2.2 Network-based Network-based path optimization schemes trigger path optimizations for a group of connections based on the existing traffic load of a switch or the utilization of the network. For example, a network switch can initiate path optimization for a group of mobile connections whenever the new call dropping probability of a certain traffic class exceeds a particular threshold. During path optimization, a number of connections wi l l be rerouted to some other switches, thereby reducing the traffic load of that switch. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 25 2.2.3 Timer-based For the timer-based schemes, path optimizations are triggered at time instants which are independent of the current QoS of the connection or the utilization of the network. The time instants can be deterministic or random. For example, the time between path optimi-zation can be based on some random processes. In addition, it can also be a function of the velocity of the mobile terminal, the dwell time, and the residual service time of the mobile connection. In this chapter, we analyze two of these timer-based schemes which are simple to implement. 1. Periodic path optimization scheme: path optimization is performed every T time units. 2. Exponential path optimization scheme: The time between path optimizations is modeled as an exponentially distributed random variable with mean 1 / v . The periodic scheme has been proposed within the A T M Forum wireless A T M working group [8] to facilitate inter-switch handoff. Notice that both periodic and the exponential schemes trigger path optimization regardless of whether or not there is an inter-switch handoff. Thus, unnecessary path optimizations may be performed for station-ary mobile connections. 2.2.4 Handoff-based The handoff-based path optimization schemes trigger path optimization for each mobile connection based on some criteria after each inter-switch handoff. For example, it can be a function of the number of previous handoffs, the velocity of the mobile terminal, or the residual service time of the connection. In this chapter, we also analyze the following scheme: 1. Bernoulli path optimization scheme: After each path extension, there is a probability p, 0 < p < \ , such that path optimization is performed. For the Bernoul l i scheme, path optimization may only occur on condition that Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 26 there is an inter-switch handoff. Thus, path optimization is never triggered after each handoff i f p = 0 . On the other hand, path optimization is always performed after each path extension i f p = 1. Path opt imizat ion can also be invoked based on a combinat ion of the above schemes. In the remainder of this chapter, we w i l l compare the performance of the periodic, exponential, and the Bernoulli path optimization schemes, and determine how to assign the optimal values for v, T and p given a set of call and mobility parameters. 2.3 Analytical Model In this section, we present a discrete time analytical model proposed to evaluate the performance of different path optimization schemes [73]. Our proposed model is a generalization of the model in [48]. Events occur at each fixed time interval. The time interval can be minutes or seconds. When the time interval is sufficiently small (e.g., fraction of a second), this model is approximately the same as a continuous time model. For each mobile connection, the following events can occur at each time interval: (1) path extension due to inter-switch handoff; (2) path optimization; and (3) call termination. A t each time interval, we let: • \ r denote the probability that there is an inter-switch handoff (and thus a path extension); • p, denote the probability that the call terminates. Thus, the time between inter-switch handoff and the call duration follow geometric distribution with mean l / ? i and 1 /p , respectively. For each mobile connection, we let: • L denote the number of links between the source and the destination during call setup; Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 27 • H denote the number of links between the anchor switch and the target switch during path extension. The random variables L and H are assumed to be independent, each having a general distribution with mean L and H, respectively. During path optimization, the path between the current anchor switch and the source is recomputed. We assume the number of links of this optimal path is a random variable also with mean L. The performance metric is the expected cost per call, which captures the amount of network resources used and the processing and signaling load of the network. The total cost per call is the sum of the link cost and the signaling cost due to inter-switch handoff. More precisely, we let: • C l i n k denote the link cost per unit time interval per link; • CPE denote the signaling cost for each path extension event; • CP0 denote the signaling cost for each path optimization event. The term C l i n k captures the amount of resources (e.g., bandwidth) used by the connection. Different traffic classes can be assigned different values for C l i n k . The total link cost of the call is a function of time and the number of links. The term CPE captures the cost for setting up the extended path between the anchor switch and the target switch. The term Cp0 includes the cost for (1) locating the crossover switch; (2) setting up the new branch connection; (3) terminating the old branch connection; and (4) updating the connection server about the status of the existing route. Since path optimization is more complex than path extension, the cost of performing path optimization is higher than the cost of performing path extension. Thus, it is reasonable to assume that CP0 » CPE . A s we are only interested in the relative performance between different path optimization schemes, other signaling costs including the costs for call setup and termination as well as Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 28 the costs for location update and intra-switch handoff are not considered. In the fo l lowing subsections, we describe the closed-form expressions of the expected cost for the exponential, periodic, and Bernoulli path optimization schemes. The derivation of these expressions are presented in the Appendices A - C . 2.3.1 Exponential Path Optimization Scheme In the exponential scheme, the time between path optimization is modeled as an exponen-tially distributed random variable with mean 1 /v . In the discrete time model, the time between path optimization is modeled as a geometrically distributed random variable. A t each time interval, we let v denote the probability that path optimization is invoked. The expected cost per call, denoted as E[Cexponentia[], is: m r , L M\-\i)(\-v)H ^exponential! ^ H I * ^ ^ 1 _ ( 1 _ _ V ) ] + il^l(xcPE + vCP0). The proof of equation (2.1) is shown in Appendix A . In (2.1), the first term is the link cost of the call i f the mobile terminal remains connected to the same switch during its connection lifetime. The second term is the increase in link cost due to the path extension associated with each inter-switch handoff. The third term is the signaling cost due to path extension. A n d the last term is the signaling cost due to path optimization. When v = 0, Fir 11 - k r . Ml-[i)H r HI - H ) r ' n i . exponentiali\v _ Q ~ ^ link ^ p,[ 1 - ( 1 - p,)] ' ' " ^ \i P E ' The exponential path optimization scheme reduces to pure path extension. That is, only path extension is performed for each inter-switch handoff and there is no path optimiza-tion. On the other hand, i f v = 1, Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 29 E[C i i - k r 4. H L z ^ l r + LLzJilr exponentiali\v _ l ~ y^Hnk "*" ,, U P £ "*" ,, ^ P O ' (2.3) In this case, path optimization is invoked at each time interval. B y taking the derivative of (2.1) with respect to v and setting the expression to zero, we obtain the optimal v , denoted as vopt, such that the expected cost is minimized. The expression is: 1 v = °P' 1 - p JXH^ - p C PO (2.4) Since v is a probability, it has to be within the range 0 < v < 1. Thus, based on (2.4), the sub-optimal value of v is: ^sub - opt ^ opt 1, if 0 < v o p l < \ i f v ^ > l . (2.5) 2.3.2 Periodic Path Optimization Scheme The periodic scheme invokes path optimization periodically. In the discrete time model, we let positive integer k denote the time period, measured in number of discrete time intervals, between successive path optimizations. The expected cost per call, denoted as E[Cperiodic^ » i S : E[Cperiodic) = \cUnk + ^ 1 i [ 1 - *( 1 - 1 + (* - 1 ) ( 1 - tfVlink V* [i [1 - (1 - jx) ] (2.6) X(i-yi) ( l - p ) " r + L - p E + - — l^PO-l - ( l - l l ) The proof for equation (2.6) is shown in Appendix B . Similar to (2.1), the first term in (2.6) is the link cost of the call i f no inter-switch handoff is generated. The second Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 30 term is the increase in link cost due to path extension at each inter-switch handoff. The last two terms are the signaling cost due to path extension and path optimization, respectively. When = 1 in (2.6), E[Cperiodic1\k = i = ^Clink + ^ ^ ^CPE + ^ ^ CPO • (2-7) Equations (2.3) and (2.7) are the same. That is, path optimization is performed at each time interval. B y taking the derivative of (2.6) with respect to k and setting the expression to zero, the optimal k, denoted as kopt, such that the expected cost is minimized, is given by the solution of: XHClink[l+(\-[i)k-kln(\-[i)] = j i C P 0 l n ( l - f i ) . (2.8) Although the value of k that satisfies (2.8) is always positive, it may not be an integer. Thus this value needs to be rounded to the closest integer. 2.3.3 Bernoulli Path Optimization Scheme For the Bernoulli scheme, path optimization is performed with probability p after each path extension. A s derived in Appendix C , the expected cost of the call , denoted as E[CBernoulli ' *S: F r r i-lr + Ml-p)(i-m r ^ B e r n o u l l i i ~ \ilink + \i[\-(\-XP){\-\i)]link In (2.9), the first term is the link cost of the call i f the mobile terminal moves under the coverage of the same edge switch during its connection lifetime. The second term is the additional link cost due to path extension at each inter-switch handoff. The last term is Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 31 the signaling cost due to path extension and path optimization. When p = 0 , equation (2.9) reduces to the same expression as (2.2), as follows: F\C II - lC . A , ( l - n ) 5 c . k ( i - n ) c f 2 1 0 ) ^Bernoulli\\p = Q " + p [ l _ ( l _ p ) ] C ^ + p ^ 1 U ' The Bernoulli scheme reduces to pure path extension. On the other hand, when p = 1, EiCBernoulli]\p=i = ±Clink + Mizii) ( C / 3 £ + C P 0 ) . (2.11) Path optimization is performed after every path extension. B y taking the derivative of (2.9) with respect to p and setting the expression to zero, we obtain the optimal p, denoted as p t , such that the expected cost is minimized, as follows: ^•'xihu^-m"^f0-A (2-i2) Since p is a probability, it has to be within the range 0 < p < 1 . Thus, based on (2.12), the sub-optimal value of p is: Psub opt 0, X popt<0 PoPt ifO<popt<l (2.13) 1. i f Popt>l-2.4 Simulation Model In the simulation model, a wireless A T M network is modeled as a non-hierarchical random graph. Random graphs have been used to model A T M networks [24]. Different variations of random graph models have also been proposed to model the topology of the Internet [19] [80]. The generation of a non-hierarchical random graph consists of the following steps [19]: Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 32 1. /V nodes are randomly distributed over a rectangular coordinate grid. Each node is placed at a location with integer coordinates. A minimum distance is specified so that a node is rejected i f it is too close to another node. The Euclidean metric is then used to calculate the distance a(i, j) between each pair of nodes (i, j). 2. A fully connected graph is constructed with the link weight equal to the Euclidean distance. 3. Based on the fully connected graph, a minimum weight spanning tree is constructed. 4. To achieve a specified average node degree1 of the graph, edges are added one at a time with increasing distance. If node i and j are connected, then the link weight, denoted as ca^, is assumed to be equal to: co0. = a(i,j) + p (2.14) where P is a uniformly distributed random variable in the range 0 < P < $ m a x - In (2.14), the first term can be interpreted as the propagation delay of the link, and the second term approximately models the queueing delay of the link. A 20-node random graph generated from the above model is shown in Figure 2.1. The size of the rectangular coordinate grid is 100 x 100. The minimum distance between any two nodes is 15. The average node degree of the graph is 3. For (2.14), $max is set to be equal to 100. Each node represents an A T M switch and each edge represents a physical link connecting the two switches. Since we are only concerned about inter-switch handoff, base stations are not included in the model. For our simulations, ten different 20-node random graphs, similar to the example shown above, were generated. Each random graph is employed in 10,000 simulation runs. The average node degree is defined as the average number of links connected to a node. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 33 100 Horizontal Distance Figure 2.1 A 20-node random graph with node degree of 3; minimum distance between any two nodes is 15. For each simulation run, a call is generated with two nodes chosen randomly as the source and destination nodes. Dijskstra's algorithm [13] is used to compute the shortest delay path between these two nodes. The source node is assumed to be stationary. The destina-tion node becomes the anchor switch of the mobile connection. The call duration and the time between inter-switch handoff are modeled as exponentially distributed random variables with mean 1/p, and 1/A,, respectively. During each inter-switch handoff, the target switch is restricted to be one of the neighboring switches of the current anchor switch. Path extension is used to extend the connection from the anchor switch to the target switch. Subsequent path optimizations may be triggered based on different initiation schemes as described in Section 2.2. Similar to the performance metric used in our analytical model, the performance metric in our simulation model is the average cost per call, which is defined as the sum of the link cost and the signaling cost due to inter-switch handoff, and is given by: m Cost = npECPE + npoCPO + £ %. /• Clink (2.15) Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 34 Table 2.1 Summary of parameters used in simulation and analytical models item symbol value number of nodes in the network - 20 size of the rectangular coordinate grid - 100 x 100 average node degree - 3 maximum queueing delay (ms) Qmax 100 time between inter-switch handoff (minutes) 5 average call duration (minutes) 1/p, 20 signaling cost per path extension CpE 1 signaling cost per path optimization Cpo 5 link cost per link per minute Clink variable time interval in analytical model (minutes) - 1 x 10~3 average number of links during call setup (from simulation) L 3.44 average increase in number of links during path extension H 1 where nPE and npo denote the number of path extension and path optimization, respec-tively, during a call; Clink, CPE and Cpo are as defined in the previous section; m is the number of events per call; x • denotes the time elapsed between event i - 1 and i; and / • denotes the number of links between two end nodes during xi. The average cost per call is calculated by averaging the total cost per call over all (100,000) simulation runs. The simulation model described above can be extended to handle other network topologies (e.g., star, ring, and hierarchical), as well as other statistical distributions for the call duration and the time between inter-switch handoff. 2.5 Results and Discussions The baseline parameters for the analytical and simulation models are summarized in Table 1. Since the analytical model is a discrete time model and the simulation model is a continuous time model, for a fair comparison, the time interval in the analytical model has Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 35 to be sufficiently small in order to approximate it as a continuous time model. We have chosen a time interval of 1 x 10 minutes. Thus, i f Cunk = 0.5/link/minute in the simula-_3 tion model, the corresponding value is Cunk = 0.5 x 10 /link/time interval in the analyt-ical model. The inter-switch handoff rate X, the call termination rate [i, the path optimization rate v for the exponential scheme, and the path optimization period k for the periodic scheme also have to be scaled accordingly (e.g., X = 0.2/minute in the simula-_3 tion model is expressed as 0.2 x 10 /time interval in the analytical model). We first present the analytical results for the three proposed path optimization schemes. The expressions of the expected cost per call as shown in equations (2.1), (2.6), and (2.9) are normalized with respect to the signaling cost per path optimization, Cpo • Figures 2.2 - 2.4 show the analytical results for the exponential, periodic, and Bernoul l i path optimizat ion schemes, respectively. Given the l ink cost to s ignal ing cost ratio, Clink/Cp0 , and the mobility parameters X and \l, there exists an optimal operating point for each scheme such that the expected cost per call is minimized. This optimal value can be determined directly from equations (2.4), (2.8), and (2.12). For the exponential path optimization scheme, as shown in Figure 2.2, the optimal path optimization probability \ t increases as Clink/Cp0 increases. F rom equations (2.4) and (2.5), vsub o p ( is always equal to 1 when §^ > -L. (2.16) C P 0 XH For the periodic path optimization scheme, as shown in Figure 2.3, the optimal path optimization period kopt decreases as Clink/CP0 increases. When CUnk/CP0 exceeds a certain threshold, kopt is always equal to 1. This threshold can be determined from equation (2.8). For the Bernoull i path optimization scheme, as shown in Figure 2.4, the optimal Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 36 path optimization probability popt increases as Clink/CPO increases. From equations (2.12) and (2.13), when Clink > \(l-\L)+]L ^ CP0 H Psub-opt is always equal to 1. Figures 2.5 - 2.7 compare the analytical and simulation results for the periodic, exponential, and the Bernoulli path optimization schemes, respectively. A s shown in the figures, the results of the expected cost per call from the analytical model and the average cost per call from the simulation model are closely in agreement. The simulation results corroborate the closed-form solutions derived from the analytical model. Although the analytical and simulation models give the same results, there are subtle differences between these two models. In the simulation model, a fixed network topology is required; while in the analytical model, only the parameters L and H are fixed. Thus, even though the average cost per cal l from the simulation model and the expected cost per call from the analytical model are the same, their second moments (i.e., cost variance) are different. Figure 2.8 shows the performance comparisons between different path optimiza-tion schemes. For each path optimization scheme, its optimal value (i.e., respectively, kopt, vopt, and popt) is first calculated and then used to determine the minimum expected cost per call . On the whole, the exponential scheme gives the highest expected cost per connection. The performance of the periodic scheme lies between the exponential and the Bernoull i schemes. The Bernoulli scheme outperforms the other two schemes by giving the lowest expected cost per call. This is due to the fact that in the Bernoulli scheme, path optimization may be invoked only after each inter-switch handoff, while in the exponential and periodic cases, multiple path optimizations may occur unnecessarily between succes-Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 37 sive inter-switch handoff. Other results for different values of X and u. also indicate that the Bernoulli scheme has a better performance over the other two schemes. Another obser-vation from Figure 2.8 is that the minimum expected cost per call increases linearly in Clink/CP0 . Th i s is due to the fact that as Clink/CP0 increases, the first term in equations (2.1), (2.6), (2.9), (i.e., LClink/\i) becomes the dominant term of the respective expression. Note that in our simulation, 10 different 20-node random graphs are used. If the number of nodes of the random graph remains unchanged, the average total cost of using either 10, 25, or 50 random graphs is equal. However, i f the number of nodes of the random graph increases, the average number of l inks between two end-points w i l l increase. Thus, the expected total costs, averaged over al l source and destination pairs, w i l l also increase. In spite of that, results show that the Bernoulli scheme still has a better performance than the other two heuristics. In order to determine the minimum expected cost for each scheme, its optimal operating point needs to be calculated. The operating point for each scheme is a function of X, p , H, and CUnk/CP0. Although the parameters H and Clink/Cpo can be deter-mined by the network, the values of X and p. may not always be estimated correctly by the mobile terminal during call setup. If that is the case, the path optimization operating point may not indeed be the optimal one. We are interested in determining the percentage change of the expected cost per call to the variation of the average call duration 1 /u \ and the average time between inter-switch handoffs 1 /X. First of all, we assume the actual call termination rate p. = 0.03 per minute. Thus, the average call duration of the mobile connection is approximately 33 minutes. The opti-mal expected total cost, denoted as £ [ C o s t (optimal)], is determined. The average cal l duration is then varied within the range of (-90, 100) %, (i.e., between 3 and 66 minutes). Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 38 Let p, denote the estimated call termination rate. The values of p. and ft. are related by the following equation: A " ' = ( l + A ^ u - 1 (2.18) where A u , ( -90% < A ^ < 100%), is the percentage change of the average call duration. Based on the estimated call duration rate p. and other network parameters (i.e., L, H, Clink/ Cpo, etc), the sub-optimal operating point for each path optimization scheme is determined. From this sub-optimal operating point and other cost and mobility parameters (i.e., X, \i, etc), the sub-optimal expected total cost, denoted as £ [ C o s t (sub-optimal)], is computed. The change in the expected total cost is determined by the following equation: E[Cost (sub-optimal)] ^ 19) ZstCost (optimal)] For the mobi l i ty and cost parameters, we assume that A, = 0 .1 , Clink = 0.5, CPE = 1, CP0 = 5 , L = 3.5 , and H = 1. The result is shown in Figure 2.9. When the average ca l l duration is over-estimated by more than - 4 0 % , the cost ratio of a l l three schemes is equal to one, which implies that the operating point is insensitive to the change of average call duration. However, within the (-90, -40) percentage range, there is an increase in the cost ratio for both exponential and Bernoulli schemes. The periodic scheme has the smallest change in expected cost (less than 1%) within the variation range. These results imply that i f there is uncertainty in estimating the average call duration, it may be better to over-estimate the value. For the variation of the time between inter-switch handoff, we assume that the actual inter-switch handoff rate X. = 0.1 per minute. Thus, the average time between inter-switch handoffs is 10 minutes. The time between inter-switch handoffs is then varied within the range of (-90, 100)%, (i.e., between 1 and 20 minutes). Let X denote the Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 39 estimate inter-switch handoff rate. The values of X and X are related by the fol lowing equation: I " ' = (l+Ax)X~] (2.20) where A ^ , ( - 9 0 % < A ^ < 100%), is the percentage change of the time between inter-switch handoffs. Based on the estimated inter-switch handoff rate X and other network parameters, the operating point for each path optimization scheme is calculated. The percentage change in expected cost is determined from eqn. (2.19). The result is shown in Figure 2.10. When the average time between inter-switch handoffs is over-estimated by more than - 6 0 %, the change in expected total cost is less than 5% for all three schemes. Among these three schemes, the Bernoulli scheme has the smallest change in expected cost. These results imply that i f there is uncertainty in estimating the time between inter-switch handoffs, it may be better to over-estimate the value. Although both the analytical and simulation models provide us with some useful insights on the network resources used and the processing and signaling load per connec-tion, these models are not without drawbacks. First of all, path extension and path optimi-zation are assumed to be point processes, i.e., the time to perform these operations has not been taken into account. In addition, the signaling overhead for path optimization is assumed to be constant. In practice, this signaling overhead may also depend on the location of the crossover switch. To simplify the analysis, we assume the average number of links of the optimal path is the same as the average number of links of the path during call setup. In real networks, that assumption may not be true. 2.6 Summary Path optimization may be necessary i f the end-to-end path after connection rerouting is not optimal. In this chapter, we proposed and analyzed three different path optimization Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 40 schemes which are simple to implement. For the exponential path optimization scheme, the time between path optimizations is modeled as an exponentially distributed random variable. The periodic path optimization scheme invokes path optimization at periodic time intervals. For the Bernoulli path optimization scheme, path optimization is performed with a fixed probability after each path extension. A discrete time analytical model and a discrete event simulation model were proposed to compare the performance of these schemes by evaluating the expected cost during a call. The analytical model enables a closed-form expression and optimal operating point to be obtained for each path optimiza-tion scheme. The analytical and simulation results agree with each other, corroborating the two models. The Bernoulli scheme outperforms the other two schemes by providing a lower expected cost per call and a lower percentage change of expected cost relative to the variation of the average time between inter-switch handoffs. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 41 65 1 1 1 1 60 C,. „ / C„„ = 0.5 • • • • ink . _ P O C,. , / CD„ = 0.4 • — • „ l i n k , _ P O C / C =0.3 „ l i n k ' „ P O C / C =0.2 C,. , /C„=0 .1 • • • ' link P O 55 \ \ 50 • \ \ \ to 45 o ^ 4 0 o 8 35 Q . X W 30 25 20 . \ \ — " 15 10 -. 0 0.2 0.4 0.6 0.8 1 Path Optimization Rate v Figure 2.2 Exponential path optimization scheme. 15 10 ' 1 , , , 0 5 10 15 20 25 30 Path Optimization Period k Figure 2.3 Periodic path optimization scheme. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 42 70 60 - 50 co o O -o 02 40 o a> a. x LU 30 20 10 C,. , / C =0.5 „link , PO C / C =0.4 C / C =0.3 C,. , / C m = 0.2 link , PO „ . C,. U / C „ „ = 0.1 link PO 0.2 0.4 0.6 0.8 Path Optimization Probability p Figure 2.4 Bernoulli path optimization scheme. -o Simulation Result - * Analytical Result o 15 20 25 Path Optimization Period k Figure 2.5 Analytical and simulation results of the periodic path optimization scheme. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 43 851 1 1 1 1 r ,1 i • i i • ' 1 1 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 Path Optimization Rate v Figure 2.6 Analytical and simulation results of the exponential path optimization scheme. 851 1 1 1 1 r ,l i i i i i i i i i I 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Path Optimization Probability p Figure 2.7 Analytical and simulation results of the Bernoulli path optimization scheme. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 44 Figure 2.8 Comparisons between different path optimization schemes. — Bernoulli P.O. Exponential P.O. - Periodic P.O. 60 -40 -20 0 20 40 60 Percentage Change in Average Call Duration (%) 80 100 Figure 2.9 Variation of the average call termination time. Chapter 2 Path Optimization for Inter-Switch Handoff: Heuristics 45 1.3r o o \ \ a 1.15r E «. 1.1 "55 o O 1.05 Exponential P.O. Periodic P.O. Bernoulli P.O. -80 -60 -40 -20 0 20 40 60 80 100 Percentage Change in Average Time between Inter-Switch Handoff (%) Figure 2.10 Variation of the time between inter-switch handoff. "Two roads diverged in ayeftozv woods... I took^the one (ess traveled by. And that has made aft the difference." fRpBert frost, The !RpadC^pt Taken. Chapter 3 Path Optimization for Inter-Switch Hand-off: Optimal Policy 3.1 Introduction In this chapter, we propose a stochastic model to determine the optimal time to perform path optimization [76]. The path optimization problem is formulated as a semi-Markov decision process. Link cost and signaling cost functions are introduced to capture the trade-off between the network resources utilized by a connection and the signaling and processing load incurred on the network. The objective is to determine the optimal policy which minimizes the expected total cost per call. The major contribution lies in the formu-lation of a general model that is applicable to a wide range of conditions. Distinct features of our model include: 1. Different link cost functions can be assigned to different service classes with different bandwidth requirements. 2. Different signaling cost functions can be used based on the complexity of the path optimization procedures and the signaling load of the network. 3. The time between inter-switch handoffs can follow an arbitrary general distribution. The rest of this chapter is organized as follows. The model formulation of the path optimization problem is described in Section 3.2. In Section 3.3, we describe the optimal -ity equations, the value iteration algorithm, and the structure of the optimal policy. The 46 Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 47 implementation issues are described in Section 3.4. Extension of the above model to mobile-to-mobile connection and other QoS constraints are described in Section 3.5. In Section 3.6, we present numerical results and compare the optimal policy with four other heuristics. A summary is given in Section 3.7. The proofs of the propositions stated in this chapter are shown in the Appendix D . For general background on M a r k o v decision processes, please refer to [46] or [56]. 3.2 Model Formulation Each mobile connection may experience a number of inter-switch handoffs during its con-nection lifetime. During each inter-switch handoff, path extension can be used to extend the connection from the current anchor switch to the target switch. Although path exten-sion is simple to implement, the connection utilizes more network resources than neces-sary. Occasional path optimization is required to reroute the connection to an optimal path. Path optimization is a complex process. It increases the processing and signaling load of the network. Thus, there is a trade-off between the network resources utilized by the call and the processing and signaling load incurred on the network. We formulate the above problem as a semi-Markov decision process. After each path extension, the network must decide whether to perform subsequent path optimization. The decision is based on the cur-rent number of links of the path and the locations of the anchor and target switches. The model is described below. 3.2.1 Semi-Markov Decision Process Model When an inter-switch handoff occurs, a path extension is performed. After that, a decision must be made whether to perform subsequent path optimization. Those time instants are called decision epochs. Referring to Figure 3.1, the sequence a 0 , Oj , . . . represents the time of successive decision epochs. Since inter-switch handoff only occurs during the call Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 48 XX,YX X2,Y2 XHT)'YHT) time - i 1 1 1 x 1 — * <70 = 0 a i a 2 . . . aHT) T Figure 3.1 Timing diagram. lifetime, the time interval requiring mobility monitoring is between a call arrival and its termination. The term o 0 = 0 represents the arrival time of a new call and the random variable T denotes the call termination time. The random variable ty(T) denotes the total number of inter-switch handoffs that has occurred before the termination time T. A t each decision epoch, the network must decide whether to perform subsequent path optimization. Let A = {NPO, PO} denote the action set, where PO corresponds to performing path optimization after path extension, and NPO corresponds to performing path extension only. The random variable Yn is used to denote the action chosen at decision epoch n. The action chosen is based on the current state of the connection. The state space is denoted by S. For each state s e S, the state information includes the locations of the target and anchor switches, and the number of links of the current path. Al though the decision is only based on the state at the current decision epoch, state change may occur between decision epochs. Consequently, we distinguish the natural process and the semi-Markov decision process. The natural process models the state evolution of the system as if it were observed continually throughout time, while the semi-Markov decision process represents the evolution of the system state at decision epochs only. These two processes coincide at decision epochs. The random variable Xn is used to denote the state at decision epoch n, and W T is used to denote the state of the natural process at time T. Two cost functions are introduced to account for the network resources utilized Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 49 and the signaling load incurred due to inter-switch handoff. The link cost function reflects the amount of network resources used during the connection lifetime, while the signaling cost function captures the processing and signaling load incurred on the network due to path extension and path optimization. The signaling costs are incurred only at the decision epochs, while the link cost is accrued continuously during the call lifetime. The function f(s, s, a) denotes the l ink cost rate as long as the natural process occupies state s and action a was chosen in state s at the preceding decision epoch. If the natural process occupies state s during the time interval (x, x + di), then the l ink cost accrued during this period is f(s, s, a) • dl. The function b(s,a) denotes the signaling cost incurred when the decision maker chooses action a in state s. Thus, b{s, NPO) represents the signaling cost of performing path extension, and b(s, PO) represents the signaling cost of performing path extension and subsequent path optimization. A l l cost functions are assumed to be bounded and nondecreasing with respect to the number of links of the current path. A decision rule prescribes a procedure for action selection in each state at a specif ied dec i s ion epoch. De te rmin i s t i c M a r k o v i a n dec i s ion rules are functions ot: S —> As, which specify the action choice when the system occupies state s at decision epoch t < T; i.e., for each s e S, 5t(s) e As. This decision rule is said to be Markovian (memoryless) because it depends on previous system states and actions only through the current state of the system, and deterministic because it chooses an action with certainty. A policy 71 specifies the decision rule to be used at all decision epochs. That is, a policy is a sequence of decision rules, 7t = (5j , 8 2 , . . . ) . The set of all policies is denoted by IT. Let v (s) denote the expected total cost per call given policy n is used with initial state s. Thus, Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 50 (s) = En\jjb{Xn,Yn) + X \\yf(WvXn,Yn)dx Jt V U = 0 n = 0 (3.1) + f f(WvXHT),YHT))dx where Es denotes the expectation with respect to policy K and initial state s. In the above expression, the first summation corresponds to the lump sum portion of the signaling cost. In the second summation, each term corresponds to the continuous portion of the link cost that is incurred at rate f(Wv Xn, Yn) between decision epochs n and n + 1. The last term corresponds to the link cost that is incurred at rate / ( W v X^Ty Y^T^) between decision epoch (J)(T) and termination time T. We assume the termination time is exponentially dis-tributed with rate p . In that case, equation (3.1) can be written as: For a proof of this fact, see Proposition D . l in Appendix D . The expression in (3.2) is the expected total cost of an infinite-horizon semi-Markov decision process with discount rate p . The function c(s, a) in (3.3) is the expected total cost between two decision epochs, given the system occupies state s and the decision maker chooses action a in state s. This cost function is further discussed in Section 3.2.3. Since the optimization problem that we consider is to minimize the expected total cost, we define a policy iz* is optimal in IT if (3.2) where (3.3) Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 51 vK*(s) < v*(s) (3.4) for all 7t e n . Let G(t\Xn, Yn) denote the cumulative distribution function of the time between decision epochs n and n + 1, given that current state is Xn and action Yn is chosen. The time between decision epochs corresponds to the time between inter-switch handoffs. In this formulation, the time between inter-switch handoffs follows a general distribution and can depend on the location of a particular anchor switch that the mobile terminal is connected to. We use G(dt\Xn, Yn) to represent the time-differential. That is, G{dt\Xn,Yn) = dG(t\Xn,Yn). A policy is said to be stationary i f 8, = 8 for all t. A stationary policy has the form 7t = (8, 8, . . . ) ; for convenience we denote it by 8. For a stationary po l icy 8, equation (3.2) can be written as: v\s) = c[s, 8(s)] + X If VV> pls'\s> 5 ^ G[dt\s, d(s)] (3.5) where d(s)] denotes the transition probability that the next state is s', given the current state is s and action b(s) is chosen. For a proof of this fact, see Proposition D . l in * Appendix D . Our objective is to determine an optimal stationary deterministic policy 8 which minimizes (3.5). To simplify the analysis, two assumptions are made. We assume the time between inter-switch handoffs is independent of the state and action chosen, i.e., the cumulative distribution function G(t\Xn, Yn) = G(t). We assume the mobile terminal is communi-cating with a remote terminal which is stationary; i.e., we consider a mobile-to-fixed connection. The model formulation for mobile-to-mobile connection is described in Section 3.5.1. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 52 3.2.2 State Transition Probability Function A state change occurs when there is an inter-switch handoff. The state space S is three dimensional. For each state (/, j, k) e S, i denotes the location of the target switch; j denotes the location of the current anchor switch; and k denotes the number of links of the current path. Thus, where N denotes the total number of nodes in the network and L represents the maximum number of links allowed in a path. The number of links of any path is always finite. We assume the number of links increased during path extension is bounded by M which is much smaller than L (i.e., M « L). Since the end-to-end delay is proportional to the number of links of the path, a sub-optimal path with a high number of links not only increases the delay but also increases the ca l l dropping probability and the congestion level of the network. We impose the condition that whenever the number of links is greater than or equal to L - M and there is an inter-switch handoff, path extension is performed followed by path optimization with certainty. For convenience, we let K = L-M. Later we show that path optimization is always performed when the number of links exceeds a certain threshold, and this threshold is much smaller than K. Given the current state s = (i, j, k), the available action set is: S = {1 ,2 , . . . , / V } x { l , 2 , . . . , / Y } x { l , 2 , . . . , L } (3.6) {NPO,PO}, {PO}, K< k < L. 1 < k <K (3.7) Thus, after each path extension, path optimization may be performed i f the number of links is less than K, while path optimization is performed with certainty whenever the number of links is greater than or equal to K. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 53 Two probability distribution functions are introduced to govern the state changes. Let • p(m\ i, j) denote the probability that the number of links of the optimal path is m, given the locations of the two end-points are i and j, respectively. • q(l\i) denote the probability that the location of the target switch in the next decision epoch is / , given the location of the target switch at the current decision In A T M networks, source routing is used for all connection setup requests. That is, the source switch selects a path based on topology, loading, and reachability information in its database. A s networks grow in size and complexity, full knowledge of network parameters is typically unavailable. Each single entity in the network cannot be expected to have detailed and instantaneous access to all nodes and links. Routing must rely on partial or approximate information, and still meet the QoS demands [26] [37]. The A T M Forum P N N I standard [10] introduces a hierarchical process that aggregates information as the network gets more and more remote. However, the aggregation process inherently reduces the accuracy of the information and introduces uncertainty. Thus, in large networks it is more appropriate to model the number of links of a path between two endpoints in a prob-abilistic manner. On the other hand, for small networks- with periodic routing information update, the number of links of a path between the two endpoints can be modeled in a deterministic manner. Let Y ( i , j) denote the number of l inks of the optimal path between the two endpoints i and j . The functions p(m\i, j) and T(i, j) are related by epoch is i. i f = m if Y ( i , j) * m. (3.8) Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 54 Let D denote the location of the destination (i.e., the remote terminal), which is assumed to be fixed. The transition probability that the next state s' = (/', /, k') given the current state s = (/, j, k) and action a chosen, is given by: P(i', f, k' | i , j, k, a) = q(i'\i) • p(m\i, j), x" * i , f = i, k' = k + m, a = NPO q(i'\i)- p(n\i,D), f = i, k' = n, a = PO (3.9) 0, otherwise. Equation (3.9) states that i f action NPO is chosen, the number of links is increased by m with probability p(m\i, j) after path extension. On the other hand, i f action PO is chosen, the number of links is equal to n with probability p(n\i, D) after path optimization. In both cases, the location of the target switch at the next decision epoch is equal to /' with probability q(i'\i). 3.2.3 Cost Functions For each path extension event, the network incurs a fixed signaling cost CPE> 0 and a variable signaling cost hPE(m) where m represents the number of links increased during path extension. The terms CPE and hpE(m) capture the cost of setting up the extended path between the anchor and target switches. For each path optimization performed, the network incurs a fixed signaling cost CP0 > 0 and a variable signaling cost hp0(l) where / represents the number of links reduced during path optimization. These two terms capture the cost of (1) locating the crossover switch; (2) setting up the new branch connection; (3) terminating the old branch connection; and (4) updating the connection server about the status of the existing route. We assume the link cost rate only depends on the number of links of the current path. That i s , f(~s,s,a) = f(k) for a l l S,SG S. R e c a l l f rom equat ion (3.2) that c(i, j, k, a) denotes the expected total cost between two decision epochs, given the system Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 55 occupies state (/, j, k) and action a is chosen. Since the first inter-switch handoff occurs at time O j , the locations of the anchor and target switches are the same at the call setup time a 0 . Thus, during the time interval ( G 0 , Gx ], we have i = j and the cost function c(j,j,k,NPO) = rxf(k) (3.10) r 0 0 r' - U T where / j = J J e dx G(dt). The function 7j/(fe) is the expected discounted link cost between two decision epochs, given the current number of links is k. For other decision epochs not equal to CT0, the locations of the anchor and target switches are always different (i.e., i * j i f o * a 0 ) . In that case, i f action NPO is chosen, then the cost function M c{i,j,k,NPO) = CPE + £ {hPE(m) + IJ{k + m)}p{m\i,j). (3.11) m = 1 The function CPE + ^hPE(m)p(m\i, j) is the expected signaling cost for path extension, given the locations of the anchor and target switches are i and j, respectively. For path optimization, we assume the number of links of the optimal path is always less than or equal to the number of links of the current path, and less than K. For decision epoch CT not equal to CT0, i f action PO is chosen, then the cost function M c(i,j,k,PO) = CPE + X hPE(m)p(m\i, j) + CP0 m = 1 (3.12) M (k + m)A(K-\) v 7 + X X {hp0(k + m-n) + Ilf(n)}p(n\i,D)p(m\i, j) in = 1 n = 1 where JC A y = min (x, y). The expression CPO + ^ h p o ( k - n)p(n\i, D) is the expected signaling cost for path optimization, given the current number of links is k, and the locations of the source and destination are i and D, respectively. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 56 3.3 Optimality Equations In this section, we introduce the optimality equations (sometimes referred to as the B e l l -man equations or functional equations) and investigate their properties. We show that solutions of these equations correspond to optimal value functions and that they also pro-vide a basis for determining optimal policies. Let v(s) denote the minimum expected total cost per call given state s. That is, v(s) = min vn(s). (3.13) TIE n The optimality equations are given by v(s) = )  min \c(s,a) + Y IT v(s') P(s'\s, a) G(dt)] I. (3.14) aeA { fts L J ° J J Let 12 = J e G(dt). Equation (3.14) can be expanded as follows: 'o For i = j and 1 <k< K, v(jJ,k) = c(jJ,k,NPO) + J^I2v(l,j,k)q(l\j). (3.15) /= 1 For i * j and 1 < k < K, r N M v(i,j,k) = min \ c{i, j, k, NPO) + X 2 I2v(l, i, k + m)p(m\i, j)q(l\i), 1 1 = 1 m - ] (3.16) N M {k + m)A(K-\) < c(i,j,k,PO)+^ £ £ I2v(l,i,n)p(n\i,D)p(m\i,j)q(l\i)[ 1= 1 m = 1 n = 1 J For i * j and K<k<L, N K-1 v(i,j,k) = c(i,j,k,PO) + £ ^I2v(l,i,n)p(n\i,D)q(l\i). (3.17) /= 1 n= 1 Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 57 A t call setup time G 0 , the locations of the anchor and target switches are the same. Thus in (3.15), no path extension or path optimization is performed. For other decision epochs not equal to a 0 , the locations of the anchor and target switches are different. If the number of links of the path is less than K, then after each path extension, the network w i l l decide whether to perform subsequent path optimization. This fact is stated in (3.16). Since path optimization is always performed i f the number of links is greater than K, in (3.17), the action PO is chosen when there is an inter-switch handoff. If the signaling cost function for path optimization is zero (i.e., CP0 = 0 and hpo{l) = 0 ) , the problem of finding an optimal policy is trivial. It is optimal to perform path optimization after each inter-switch handoff. This is because the link cost function is nondecreasing with respect to the number of links of the current path. After each path optimization, there is a reduction in the number of links. However, i f the signaling cost function for path optimization is nonzero, it is not obvious as to what constitutes the optimal policy. Note that i f p. > 0 , the state space is finite, and the cost functions are bounded, then the solutions for equations (3.15)-(3.17) exist. B y solving these equations, a stationary deterministic optimal policy can be obtained. 3.3.1 Value Iteration Algorithm There are a number of iteration algorithms available to solve the above optimality equa-tions. Examples include the value iteration, policy iteration, and linear programming algo-rithms [46]. Value iteration is the most widely used and best understood algorithm for solving discounted Markov decision problems. Value iteration is also known by other names including successive approximations, over-relaxation, and pre-Jacobi iteration. The following value iteration algorithm finds a stationary deterministic optimal policy and the corresponding expected total cost. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 58 A l g o r i t h m : 1. Set v°(5') = 0 for each state s e S. Specify e > 0 and set n = 0 . 2. For each s e S, compute v" + 1 (s) by: v 0 ) = min ae A \c(s,a) + X [T ^ V ( s ' ) P ( y | s , a ) G ( < f r ) ] 3. If | v " + 1 — v"! < e, go to step 4. Otherwise increment n by 1 and return to Step 2. 4. For each s e S, the stationary optimal policy g min I c O . a ) + Y I T v V ) W l * . « ) [ 5 (s) = ar£and stop. There are a number of definitions for the function norm || • ||. In this thesis, the function norm is defined as: ||v|| = max v(s). se s Convergence of the value iteration algorithm is ensured since the operation in Step 2 cor-responds to a contraction mapping. Thus, the function v"(^) converges in norm to v(s ) . In small networks, i f each node maintains perfect information of al l nodes and links, then the function v[i, i, T(i, D)] is the minimum expected total cost per call given source i and destination D. On the other hand, in large networks, the number of links of a path determined by the source is modeled in a probabilistic manner. In that case, the expression J^v(i,i,k)p(k\i,D) (3.18) k is the minimum expected total cost per call given source i and destination D, averaged Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 59 over the number of links of the optimal path. 3.3.2 Structure of the Optimal Policy We now provide a condition under which the optimal policy has a control limit (or thresh-old) structure. The control limit structure states that path optimization is performed with certainty whenever the number of links of the current path exceeds a certain threshold. For convenience, we let Ay(k) = y(lc + 1) - y(k) for some function y . Proposi t ion 3.1: Given state (/, j, k)e S, the optimal policy 8 has a control limit struc-ture: and k* <k<K. The proof of the above proposition is shown in Proposition D.2 in Appendix D . The value k* is the control limit or threshold. Consider the special case where the cost functions are linear. That is, f(k) = Clink • k and hpo(l) = wp0 • I where C l i n k and w p 0 are positive constant. In this case, i f l\CUnk - wP0 > 0 , then path optimization is always performed when the number of links is greater than or equal to k* . A n optimal policy with threshold structure facilitates its implementation. For each mobile connection, the network only has to maintain the information of the minimum number of links to initiate path optimization for all anchor and target switch pairs. The decision of performing path optimization can be made by a table lookup. 1 <k<k*, k*<k<L (3.19) when IlAf(k + m)-^iAhPO(k + m-n)p(n\i,D)>0 for all m such that p(m\i,j)*0 n 3.4 Implementation Aspects Having identified the different parameters involved in the model, we are now in a position Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 60 to explain the steps that need to be taken in order to implement the model. For each mobile connection, during its connection setup phase, the network controller assigns the cost functions based on the service class and the signaling load of the network. Different ser-vice classes (e.g., C B R , V B R , A B R ) with different bandwidth requirements are assigned different link cost functions to reflect the network resources consumed. The assigned sig-naling cost function reflects the complexity of the path optimization procedures and the current signaling load of the network. B y keeping the mobility profile of each user (i.e., the movement history and call history), the average time between inter-switch handoffs as well as the average duration of the connection can be estimated [81]. Given the input parameters (i.e., cost functions and various distributions), the value iteration algorithm can be used to determine the optimal policy. The optimal policy is then stored in a table format. Each entry of the table specifies the minimum number of links to initiate path optimization for a specific pair of anchor and target switches. Whenever there is an inter-switch handoff, the network performs a table lookup at the corresponding anchor and target switch entry. Path optimization is performed i f the number of links is greater than the threshold. The optimal policy table needs to be updated when there are changes in network topology or signaling load of the network. The update can be performed off-line; i.e., whenever spare processing capacity is available at the network controller. 3.5 Model Extensions In the previous sections, we have considered the connection between a mobile terminal and a fixed endpoint. In this section we extend the above model to the connection between two mobile terminals and to take into the consideration of other QoS constraints. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 61 3.5.1 Extension to Mobile-to-Mobile Connection The problem formulation for mobile-to-mobile connection is similar to that of mobile-to-fixed connection. Consider mobile terminals 1 and 2 communicating with each other via a wireless A T M network. Each mobile terminal has its own movement pattern. Path exten-sion is performed when there is an inter-switch handoff, (initiated from either side), fol-lowed by path optimization i f necessary. In this formulation, the state space needs to include the locations of the two endpoints, as well as the information of which mobile ter-minal initiates the path extension. For each state (i, j, k, I, m) e S, i and j denote the locations of the anchor switch connected to mobile terminals 1 and 2, respectively; k denotes the number of links of the current path; / denotes the identifier of the mobile ter-minal which initiates the inter-switch handoff; and m denotes the location of the target switch. Since the movement pattern of each mobile user is different, the time between inter-switch handoffs for each mobile user is also different. Suppose the time between inter-switch handoffs for mobile terminal r , ( r e { 1 , 2 } ) , is exponentially distributed with rate Xr, then the time between decision epochs is also exponentially distributed with rate X-l+X2. Since the state space has changed, the cost functions and the state transition probability function have to be modified accordingly. A s the modification is conceptually similar to the functions derived in Section 3.3, the details are omitted. The optimality equations are v(s) = min aeA (3.20) The value iteration algorithm described in Section 3.3.1 can be used to evaluate the expected total cost and the optimal policy. The conditions for the optimal policy with a Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 62 threshold structure can also be derived. 3.5.2 Extension to QoS Constraints In Sections 3.2 and 3.3, path optimization is triggered based on the number of links of the current path. In general, a mobile connection can have multiple QoS constraints such as bandwidth, delay, delay jitter, etc. Suppose the connection has to maintain a delay con-straint. In this case path optimization is performed with certainty i f the end-to-end delay after path extension exceeds the delay constraint, while path optimization may be per-formed i f the delay after path extension is still below the constraint. To incorporate the delay constraint into the model, the state space needs to be extended to include the end-to-end delay of the current path. We assume the endTto-end delay of a path is the sum of the delay on each link of the path. The delay information on each link can be obtained from the network by measurement. Let £ denote the end-to-end delay of the current path and *F be the delay constraint. Let <£>(/, j) denote the delay of the path between the two endpoints / and j. The optimality equations described in Section 3.3 have to include the following constraint £ + O ( U ) < *F (3.21) where i and j denote the locations of target and anchor switches respectively. Note that the value iteration algorithm described in Section 3.3.1 cannot be used to solve the opti-mality equations with constraints. However, the optimality equations can be transformed into primal or dual linear programs, which can then be solved by the simplex algorithm. Interested readers are referred to [46] for details of the transformation. In summary, multiple QoS constraints can be incorporated into the model by extending the state space and including the constraint equations into the set of optimality equations. The expected total cost and the optimal policy can be obtained by transforming Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 63 the model into a linear programming model. 3.6 Numerical Results and Discussions In this section, we compare the performance of the optimal policy with four heuristics. For the first heuristic, path optimization is performed after each path extension. We denote this policy as "always perform path optimization" or 8 . For the second heuristic, no path optimization is performed during the connection lifetime. We denote this policy as "never perform PO" or bNP°. For the third heuristic, periodic path optimization is considered. The use of periodic path optimization has been proposed within the A T M Forum [8]. For periodic path optimization, after every T time units, the network determines i f the connec-tion requires path optimization. Suppose the current time is r, path optimization is per-formed i f an inter-switch handoff has occurred during the time interval (t- Y, t). In this section, we assume that T is equal to the average time between inter-switch handoffs. For the last heuristic, we consider the Bernoulli path optimization scheme which is proposed and analyzed in the previous chapter. The performance metrics are the expected total cost per call and the expected number of path optimizations per call. The expected total cost per ca l l is defined in Section 3.1. The expected number of path optimizations per cal l given pol icy 71 with initial state s is: ^n = 0 J where 1 [ ] denotes the indicator function. That is, l[a = 1] is equal to one i f a = 1 and zero otherwise. (3.22) Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 64 3.6.1 Simulation Model In the simulation model, a wireless A T M network is modeled as a non-hierarchical ran-dom graph, similar to the one proposed in Chapter 2. Based on network model, we obtain the adjacency matrix of the network as well as the number of links of the shortest path between any two nodes. We assume the number of links of the shortest path estimated by the source is deterministic. The call duration is assumed to be exponential. The time between inter-switch handoffs follows a Gamma distribution. For each source and destination pair, the value iteration algorithm described in Section 3.3.1 is used to determine the minimum expected total cost and the optimal policy. F r o m the optimal policy, the value iteration algorithm is used again to calculate the expected number of path optimizations. The m i n i m u m expected total cost and the expected number of path optimizations are then averaged over all possible source and destination pairs. We repeat this for 100 random graphs and determine the averages. For the two heuristics bP° and b N P O , the expected total cost and the expected number of path optimizations for each source and destination pair are also determined by the value iteration algorithm. These values are then averaged over all possible source and destination pairs. A g a i n , we repeat this for 100 random graphs and determine the averages. For the periodic and Bernoulli path optimization policies, simulation must be used. Given the network topology, a call is generated with two nodes chosen as the source and destination. Dijskstra's algorithm is used to compute the shortest path between these two nodes. The destination node is assumed to be stationary. The source node becomes the anchor switch of the mobile connection. During each inter-switch handoff, the target switch is restricted to be one of the neighboring switches of the current anchor switch. Path extension is used to extend the connection from the anchor switch to the target Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 65 switch. Path optimization is performed periodically for the periodic scheme. For the Bernoul l i scheme, its operating point, denoted as p , is determined from equations (2.12) and (2.13). After each path extension, path opt imizat ion is performed wi th p robabi l i ty popt. For each source and destination pair, 1000 s imula t ion runs are performed. The average total cost and the average number of path optimizations per call are determined. We repeat this for 100 random graphs and determine the averages. A l l the cost funct ions are assumed to be l inear . The l i n k cost func t ion f(k) = Clink • k where Clink > 0 . The term Clink captures the amount of resources (e.g., bandwidth) used by the connection. Different traffic classes can be assigned different values for C l i n k . The variable cost function for path extension hPE(m) = wPE • m where wpE > 0 and m denotes the number of links increased during path extension. The variable cost function for path optimization hpo(l) = wP0 • I where wp0 > 0 and / denotes the number of links reduced during path optimization. For the cost and mobility parameters, we assume that Clink = 0.1, CPE = 1, CP0 = 5 , wPE = 0.5, wP0 = 0.5, X = 0.1 , and p, = 0.03. 3.6.2 Results Figure 3.2 shows the expected total cost versus the link cost rate C l i n k . The optimal policy gives the lowest expected total cost compared to the other four heuristics. When the link cost rate is small, there is no incentive to perform path optimization. The operating point, p t , for the Bernoulli policy is close to zero. The optimal policy is to perform path exten-sion only. Thus, results of the Bernoulli, 8NP0, and optimal policies are the same. When the link cost rate increases, the optimal policy for some source and destination pairs is to perform path optimization. Results of the optimal, Bernoulli, and bNP° policies diverge, PO while the results of the Bernoulli and 5 policies begin to converge. Figure 3.3 shows the expected number of path optimizations versus the l ink cost Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 66 rate Clink. Since no path optimization is performed for the S"ru policy, the expected number of path optimizations is always equal to zero. Note that since both the call termi-nation rate and the inter-switch handoff rate are constant, in this case the expected number PO of inter-switch handoffs is also a constant. Thus, results for the periodic and 8 policies are independent of the link cost rate. For the Bernoulli and optimal policies, when the link cost rate is small, there is no incentive to perform path optimization. The expected number of path optimizations is small. A s the link cost rate increases, some source and destination pairs perform path optimization after inter-switch handoff. Thus, there is an increase in the number of path optimizations performed. Figure 3.4 shows the expected total cost versus the inter-switch handoff rate A,. The expected total cost increases as the inter-switch handoff rate increases. When X is small (i.e., the average time between inter-switch handoffs is larger than the average call duration), an inter-switch handoff is unlikely to occur during the connection lifetime. Thus, the results between the five policies are close. A s the inter-switch handoff rate PO increases, these five curves begin to diverge. The 8 policy gives the highest expected total cost, which is followed by the periodic, dNP0, and Bernoulli policies. Results of the & N P 0 and Bernoulli policies are very close. Although we can conclude that the expected total cost increases in X and the optimal policy always gives the minimum expected total cost, the performance comparisons between the other four heuristics differ when another PO set of parameters are chosen. That is, the 8 policy can sometimes have a better perfor-mance than the periodic and b N P 0 policies Figure 3.5 shows the expected number of path optimizations versus the inter-switch handoff rate X. The expected number of path optimizations increases as X increases. Results of the Bernoulli and optimal policies are quite close. Due to the thresh-old structure of the optimal policy, path optimization is performed only after a certain Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 67 number of inter-switch handoffs. Thus, the expected number of path optimizations for the PO optimal policy is smaller than the periodic and 6 policies. Figure 3.6 shows the expected total cost versus the call termination rate \i. The expected total cost decreases as the call termination rate increases, which is intuitive since the link cost is accrued continuously during the call lifetime. When p. is large (i.e., the call duration is short), all the connections experience a small number of inter-switch handoffs. Thus, the results of all these policies are close. When the cal l duration increases, the results begin to diverge. We can see a significant cost difference between the optimal policy and the other heuristics when the call duration is long (i.e., p. is small). Figure 3.7 shows the expected number of path optimizations versus the ca l l termination rate p.. The expected number of path optimizations decreases as \i increases. Due to the threshold structure of the optimal policy, path optimization is performed only after a certain number of path extensions. Thus, the expected number of path optimiza-po tions performed for the optimal policy is much smaller than the periodic and 8 policies. In the previous results, we assume the time between inter-switch handoffs follows a Gamma distribution. We also consider exponential and hyper-exponential distributions for the time between inter-switch handoff. For a fair comparison, the average time between inter-switch handoffs is the same for various distributions. Figure 3.8 and Figure 3.9 show the min imum expected total cost of the optimal pol icy versus X and CUnk, respectively. These results indicate that the expected total cost is relatively insensitive to the distributions of the time between inter-switch handoffs. We also perform the sensitivity analysis for the optimal policy with respect to the variation of the average call duration and the average time between inter-switch handoffs. The procedures for the sensitivity analysis are similar to those described in Section 2.5 in Chapter 2. The results for different \l are shown in Figure 3.10. When the average call Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 68 duration is over-estimated by more than -40 %, the cost ratio is almost equal to one, which implies that the optimal policy is insensitive to the change of the average ca l l duration. However, within the (-90, -50) percentage range, there is an increase in the cost ratio. The cost ratio can be as high as 1.53 for p. = 0.02. These results imply that i f there is uncertainty in estimating the average call duration, it may be better to over-estimate the value in order to reduce the cost ratio difference. Figure 3.11 shows the cost ratio versus the percentage change in average time between inter-switch handoffs for different X. Within the percentage range of interest, the cost ratio is always less than 1.07 (i.e., 7%). Within the (-50, 100) percentage range, the cost ratio is less than 1.01 (i.e., 1%). These results imply that the optimal pol icy is relatively insensitive to the change of the average time between inter-switch handoffs. In this chapter, the wireless A T M network is modeled as a non-hierarchical random graph. One question that arises is whether the results w i l l differ i f some other network topologies are used. The answer is affirmative. The relative performance between the four heuristics w i l l change i f another network topology is used. This is essentially the same as changing the values in the functions p(m\i, j) or T(i, j). However, the optimal policy wi l l always give the lowest expected total cost compared to the other heuristics. One issue may arise as to the mapping of the network resources ut i l ized by a connection into appropriate cost functions. That issue is beyond the scope of our work. Interested readers can refer to [7] or [17] for details. 3.7 Summary In this chapter, we addressed the issue of when to initiate path optimization for the two-phase handoff protocol. The path optimization problem is formulated as a semi-Markov decision process. Based on current state information, the network decides whether to per-form path optimization after path extension. The time between inter-switch handoff fol-Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 69 lows a general distribution and can depend on the location of the anchor switch. Although in this chapter, the network architecture is assumed to be ATM-based, the proposed model is also applicable for any connection-oriented mobile network archiectures. In addition in the future IP network infrastructure which provides QoS, our model may also be used to ensure a continuous flow of the multimedia applications in the wireless domain. We presented the value iteration algorithm which solves the optimality equations. A stationary deterministic optimal pol icy is obtained. Under certain conditions, the optimal policy has a threshold structure. That is, path optimization is always performed when the number of links of the path is greater than a certain threshold. The threshold structure of the optimal policy facilitates the implementation. When inter-switch handoff occurs, the decision of performing path optimization can be made by a table lookup. The performance of the optimal policy is compared with four heuristics, namely, "always perform path optimization", "never perform path optimization", "periodic" and "Bernoull i" path optimizations. Simulation results indicate that the optimal policy gives a lower expected cost per call than the other four heuristics. These results imply that by using the optimal policy, the mobile connection maintains a good balance between the network resources ut i l ized and the signaling load incurred on the network during its connection lifetime. We studied the effect of various distributions for the time between inter-switch handoffs on the expected total cost. Results indicate that the relative change in the expected total cost is not significant. We also performed the sensitivity analysis for the optimal policy with respect to the variation of the average call duration and the average time between inter-switch handoffs. Results indicate that the optimal policy is relatively insensitive to the change of the average time between inter-switch handoffs. If there is uncertainty in estimating the average call duration, it may be better to over-estimate the value in order to reduce the cost ratio difference. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 200 Link Cost Rate Figure 3.2 Expected total cost versus link cost rate Clink. . _ - A - Always Perform Path Optimization •a • Periodic Path Optimization - O - Bernoulli Path Optimization —*— Optimal Policy 3.5 - Never Perform Path Optimization Link Cost Rate Figure 3.3 Expected number of path optimizations versus link cost rate Cx Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 101 1 1 1 ' — — — ' ' 1 • 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Inter-Switch Handoff Rate (per minute) Figure 3.4 Expected total cost versus inter-switch handoff rate X. Figure 3.5 Expected number of path optimizations versus inter-switch handoff rate A, Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy Call Termination Rate (per minute) Figure 3.6 Expected total cost versus call termination rate p . 10 t U.UU u.uu u.u* Termination Rate (per minute) Figure 3.7 Expected number of path optimizations versus call termination rate Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 73 221 1 1 1 1 1 1 r 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Inter-Switch Handoff Rate (per minute) Figure 3.8 Min imum expected total cost of the optimal policy versus inter-switch handoff rate X for various distributions. 22 Link Cost Rate Figure 3.9 Min imum expected total cost versus link cost rate Clink for various inter-switch handoff rate distributions. Chapter 3 Path Optimization for Inter-Switch Handoff: Optimal Policy 74 - O - a = 0.02 - * - p. = 0.03 A n = Q.l ~A A & 1 ' ~&—fa ~$ * -60 -40 -20 0 20 40 60 Percentage Change in Average Call Duration (%) 80 100 Figure 3.10 Variation of the average call termination time. Percentage Change in Average Time Between Inter-Switch Handoff (%) Figure 3.11 Variation of the average time between inter-switch handoffs. "There, is always another way to look\at the same problem." %ichardcP. Jeynman, 1918-1988. Chapter 4 Distance-based Location Update 4.1 Introduction In this chapter, we propose a stochastic model to analyze the distance-based location update algorithm [77]. The location tracking problem is formulated as a semi-Markov decision process [46]. There is a cost function associated with location update and another cost function associated with terminal paging. The objective is to determine the optimal policy so as to minimize the expected total cost between call arrivals. Unlike other models proposed in the literature, our model eliminates some of the unrealistic assumptions com-monly used. Distinct features of our model include: 1. Cell residence time can follow general distributions: This captures the fact that the mobile user may spend more time at certain cell locations (e.g., home or office) than some other locations. In addition, various distributions can be used to model different cell sizes (e.g., macrocell, microcell, or picocell). The average residence time in each cell can be different. The i.i.d. exponential or geometric cell residence time assump-tion can be relaxed. 2. Applicable to arbitrary cell topologies: This feature captures the fact that the num-ber of neighboring base stations at different locations may vary in real life. Some base stations may only have two neighboring base stations while others can have as many as six. Thus, our model is not restricted to structured cell configuration such as mesh or hexagonal. 3. Markovian movement patterns: The probability that the mobile user moves to a par-75 Chapter 4 Distance-based Location Update 76 X0> Y0 Xl> Y \ X2' Y2 Xl(T)> Yl(T) time 1 : 1 \ X • c 0 = 0 a , a 2 . . . al(T) T • j ^ x2 Figure 4.1 Timing diagram. ticular neighboring cell can depend on the location of the current cell or a list of cells recently visited. The assumption of symmetric random walk movement pattern can be relaxed. The structure of this chapter is as follows: In Section 4.2, we describe the model formulation. In Section 4.3, we derive some analytical results for the distance-based algorithm under a given cell residence time distribution. Numerical results are presented in Section 4.4. A summary is given in Section 4.5. The derivation of the optimality equations is shown in Appendix D . In the remainder of this chapter, we use the terms "mobile user" and "mobile terminal" interchangeably. 4.2 Model Formulation The mobile terminal has to make a decision whenever it crosses a cell boundary or a cer-tain time has elapsed. Those time instants are called decision epochs. Referring to Figure 4.1, the sequence G 0 , o t , . . . represents the times of successive decision epochs. Since the network must track the user's location perfectly during a call, the user's location is known to the network when a call terminates. Thus, the time interval requiring mobility tracking is between the termination of the last call and the arrival of the next one. In Figure 4.1, c 0 = 0 denotes the last call termination time and the random variable T represents the arrival time of the next call. A t each decision epoch, the mobile terminal has to decide whether to update its Chapter 4 Distance-based Location Update 77 location or not. The action set A = {0, 1} , where " 1 " represents the action of performing location update and "0" represents the null action of no intervention. The random variable Yn is used to denote the action chosen at decision epoch n. The mobile terminal chooses an action based on its current state information. The state informat ion can include: the number of cel ls crossings since the last update (movement-based), the cell-distance between the current location and where the previous update was performed (distance-based), the velocity of the mobile terminal, or some other criteria. The random variable Xn is used to denote the state at decision epoch n. Two cost functions are introduced to account for the network resources used for location update and terminal paging. The location update cost reflects the consumption of radio bandwidth and battery power, as wel l as the update processing incurred on the database. The paging cost reflects the number of cells being paged and the number of search iterations performed. The function f(Xn, Yn) denotes the update cost at decision epoch n, given current state Xn and action Yn chosen. Thus, f(Xn, 1) represents the cost incurred, given location update is performed at decision epoch n with state Xn. On the other hand, we assume the cost is zero for no updating, i.e., f(Xn, 0) = 0 . For the paging cost function, referring to Figure 4.1, let l(T) denote the last decision epoch before the next call arrival. The cost function hiX^) represents the cost incurred on terminal paging. We assume that the paging strategy follows the shortest-distance-first order. That is, when a paging event occurs, the search is conducted first at the user's last reported cell . If the mobile is not found there, then the search is conducted in increasing distance order from the last reported ce l l , unt i l the user is located. The maximum paging delay corresponds to the maximum number of search iterations allowed. A t each search iteration, a set of cells is paged simultaneously. In this model, different Chapter 4 Distance-based Location Update 78 paging delay constraints are modeled by using different paging cost functions. A decision rule prescribes a procedure for action selection in each state at a specif ied dec i s ion epoch. De te rmin i s t i c M a r k o v i a n dec i s ion rules are functions 8,: S —> A, which specify the action choice when the system occupies state s at decision epoch t < T. A policy n = (8, , 8 2 , ...) is a sequence of decision rule to be used at al l decision epochs. Let vK(s) denote the expected total cost between call arrivals given policy n is used with initial state 5 . It is the sum of the location update and paging cost. Based on the above notations, As) = Ensl X /(*„ , Yn) + h(Xl(T)) (4.1) U = o J where denotes the expectation with respect to policy n and initial state s . In the above expression, the first term corresponds to the lump sum portion of the location update cost. The second term corresponds to the paging cost incurred upon a call arrival. Let G{t\Xn, Yn) denote the cumulative distribution function of the time between decision epochs n and n + 1, given current state Xn and action Yn chosen. The time between decision epochs corresponds to the cell residence time (also known as the cell dwell time). In our formulation, the cell residence time follows a general distribution that can depend on the location of the cell. This captures the fact that a mobile user may spend more time at certain cell locations than the others. In addition, different cell sizes (e.g., macrocell, microcell, picocell) can have different cell residence time distributions. Thus, the usual i . i .d. exponential cell residence time assumption can be relaxed. If the time between call arrivals at each mobile terminal is exponentially distrib-uted with mean l/X, then as shown in Appendix D , equation (4.1) can be written as: Chapter 4 Distance-based Location Update 79 v\s) = A £ e-X%(Xn, Yn) (4.2) where c(Xn, Yn) = f(Xt Yn) + h(Xn)f(\-e-Xx)G(dx\Xn,Yn). (4.3) The cost function c(Xn, Yn) can be interpreted as the effective cost incurred at decision epoch n, given the current state Xn and that action Yn is chosen. A policy is said to be stationary i f 5, = 8 for all t. A stationary policy has the form 7t = (8, 8, . . . ) ; for convenience we denote it by 8. For a stationary po l i cy 8, equation (4.2) can be written as where P[j\s, 8(s)] denotes the transition probability that the next state is ;', given the cur-rent state is s and action 8(s) is chosen. For a proof of this fact, see Proposition D . l in Appendix D . Our objective is to determine an optimal stationary deterministic policy 8 which minimizes (4.4). Note that for Markovian movement pattern, correlations between the directions of successive moves of the mobile user can also be incorporated i f the state includes a history of the cells visited. Since different location update algorithms correspond to maintaining different states, in the remainder of this chapter, we focus on the analysis of the distance-based location update algorithm subject to various paging delay constraints, cell residence time distributions, and network topologies. (4.4) * Chapter 4 Distance-based Location Update 80 -2 -1 0 1 2 Figure 4.2 One-dimensional linear model. 4.3 Distance-based Location Update Algorithm In this section, we begin by analyzing the distance-based algorithm with a given cell resi-dence time distribution G{t) for all cells and a simple linear cell configuration. The value iteration algorithm is presented to evaluate the expected total cost and the optimal policy. The conditions under which the optimal policy has a threshold structure are given. These results are then extended to the hexagonal cell configuration. After that, we analyze the distance-based algorithm under arbitrary cell topology and Markovian movement patterns, and describe the implementation based on a simple table lookup. 4.3.1 Linear Cell Configuration We assume that the mobile user moves according to a symmetric one-dimensional random walk (see Figure 4.2). That is, when the mobile user moves to a neighboring cell , the prob-ability that the user moves to the left (or right) is equal to 0.5. The state X(t) e {0, ± 1 , ±2 , ...} of the mobile terminal at time t refers to the coordinates of the current position of the user relative to the position of the last update. For / > 0 , X(t) = i denotes the user being i units to the right at time t, and vice versa. The state X(t) = 0 denotes the user staying within the cell in which the mobile terminal performed the last update. Whenever the mobile terminal crosses a cell boundary, it makes a decision whether or not to perform location update. Let S(X(r) ) denote the action chosen at state X(t). If 8(X(f)) = 0 , then X(t+) = X(t). I f 8(X(0) = 1, then X(t+) = 0 , where X(t+) denotes the user's location immediately after the decision. Chapter 4 Distance-based Location Update 81 The cost for location update is assumed to be constant. That is, f(X(t),a) = a = 1. a = 0 (4.5) The update cost represents the expenditure of radio bandwidth and processing at the data-base. If a call arrives at time t, the paging cost incurred is given by h(X(t)). The form of the paging cost function is based on the assumption that the network starts its search for the user from the cell in which the mobile terminal last updated its location (i.e., shortest-distance-first). Since the network must track the user's location precisely during a call, we assume the user's locat ion is known to the network when a ca l l ends. Start ing from state X(0) = 0 , we devise a distance-based location update pol icy which minimizes the expected sum of the location update costs and the paging cost of the next call. We now introduce the optimality equations and investigate their properties. For simplicity, we denote the position X(t) by i. Let v(i) denote the minimum expected total cost between call arrivals given state / . The optimality equations are given by: The first term in (4.6) denotes the expected total cost i f no update is performed at state i, whi le the second term denotes the expected total cost i f locat ion update is performed at state / . For state i = 0 , the minimum is achieved by the first term so that (4.6) where i = 0, ± 1 , ± 2 , . . . , and K = e G(dx). o Chapter 4 Distance-based Location Update 82 8 (0) = 0 and v(0) = (\-K)h(0) + | [ v ( l ) + v ( - l ) ] . (4.7) For ( V O , the optimal policy 8 (i) is given by: r o , v(i) < cLU + v(0) 8 (i) = ^ ( 4 - 8 ) [1 , v(i) = CLU + v(0). There are a number of iteration algorithms available to solve the opt imali ty equations. The following value iteration algorithm finds a stationary deterministic optimal policy and the corresponding minimum expected total cost. Value Iteration Algorithm: 1. Select v°(i), specify e > 0 and set n = 0 . 2. For each i, compute v" + 1 (i) by v " + 1 ( 0 ) = (l-K)h(O) + | [ v " ( l ) + v " ( - l ) ] (4-9) vn + \i) = min Ul-K)h(i) + | [ v " ( / + l ) + v " ( / - l ) ] , CLU + vB(0)} (4.10) where i = +1, ±2 , . . . . 3. If || v" + 1 — v"|| < e, go to step 4. Otherwise increase n by 1 and return to Step 2. 4. For each i, choose 8 (/) = 0 i f Chapter 4 Distance-based Location Update 83 ( l - ^ ( 0 + | [ v B ( i + l ) + v " ( / - l ) ] < CLU + vn(0). (4.11) Otherwise, choose 8 ( 0 = 1. 5. Stop. We now provide a condition under which the optimal policy has a control limit (or threshold) structure. The control l imi t structure simply states that location update is performed with certainty whenever the distance exceeds a certain threshold. Proposi t ion 4.1: If the paging cost function h(i) is nondecreasing in i for i < 0 , then the optimal policy has the control limit structure = | 0 ' u<i<'» [ 1, otherwise where IL<Q<IJJ. We allow the values IL = - ° ° and 1^ = ° ° , which correspond to the policy that location update is never performed. If h(i) is symmetric, that is h(i) = h(-i) for all i > 0 , then IL = - I V . Proof: Let v°(j) = 0 for all i in the value iteration algorithm. B y using induction in n, it is clear that for each n, v" is nondecreasing in i for / > 0 and nonincreasing in i for i < 0 . Since v" —»v, the optimal expected total cost v is also nondecreasing in i for i > 0 and nonincreasing in i for i < 0 . From (4.8), the optimal policy must have a control limit structure. • Let Cp denote the paging cost per cell. We now consider the scenario where h(i) is symmetric and unbounded, such as h(i) = CP-[2\i\ + 1] . (4.13) for i > 0 and in -i (4.12) Chapter 4 Distance-based Location Update 84 In this case, the paging cost is proportional to the distance from the user's last known loca-tion. Since the paging cost function and the random walk model are both symmetric, we can deduce that v must also be symmetric in i. Thus, the value iteration algorithm only needs to consider non-negative values of i. It is necessary to limit the range of i in order to obtain a practical value iteration algorithm. We assume the existence of an upper bound v(0) for v (0 ) , and let Imax be the minimal value of i such that (l-K)h(i) > CLU + v(0) > CLU + v(0) for all | i | > Imax. The existence of a finite Imax is guaranteed for h such as (4.13), since (1 - K)h(i) - » o o as i ' - » o o . From (4.6)-(4.8), we obtain v(i') = CLU + v(Q) and 5(z) = 1 for \i\>Imax. Therefore in the value iteration algorithm, we only consider vn(i) for \i\ < Imaxmd set vn + \-Imax) = v" + \ l m a x ) = CLU + vn(0) for all n. To obtain an upper bound v (0 ) , we consider the following policy: 5 ( 0 = i . , 1421 in which the mobile terminal updates its position whenever it moves to another cell . We take the expected cost at state 0 of this policy as our upper bound of v (0 ) . Thus, v(0) = (\-K)h{Q) + | [ 2 C L f / + 2v(0)] Chapter 4 Distance-based Location Update 85 Figure 4.3 Hexagonal cell configuration. In summary, given a general ce l l residence time distr ibut ion, the m i n i m u m expected total cost of updating and paging as well as the optimal policy can be determined by the value iteration algorithm. If the paging cost function is nondecreasing, the optimal policy has a threshold structure. Results in this section can be considered as an extension of [38] in which the cel l residence time is restricted to be geometric, while our model allows a general cell residence time distribution. 4.3.2 Hexagonal Cell Configuration We now extend the results in the previous section to the symmetric two-dimensional ran-dom walk model. A n infinite two-dimensional hexagonal cell configuration is considered (see Figure 4.3). The probability that a user moves to each neighboring cell is equal to 1 /6 . The cell residence time is assumed to be i.i .d. with a given cumulative distribution G(t). The state X(t) e {0, 1, 2, ...} of the mobi le terminal at time f refers to the Chapter 4 Distance-based Location Update 86 coordinates of the current position of the user relative to the most recent update position. The state X(t) = 0 denotes the user staying within the cel l where the last update was performed. The state X(t) = i denotes the user being located in one of those cells which is i units away from the last update location. The cost for each location update is C L U . If a call arrives at time t, the paging cost incurred is given by h(X(t)). For simplicity, we denote the two-dimensional position X(t) by i. The optimality equations for the minimum expected total cost between call arrivals are given by: v(0) = (l-K)h(O) + Kv(l). (4.14) v(i) = mm^(\-K)h(i) + ^ Q - l j v ( i - l ) + ^v(i) + Q + I)v(i+1) CLU + (l-K)h(O) + Kv(l)} (4.15) where / = 1 ,2 ,3 , . . . and K = \ e G(dx). Jo The first term in (4.15) denotes the expected total cost i f no update is performed at state i, whi le the second term denotes the expected total cost i f location update is performed at state i. * If state i = 0 , the optimal policy 8 (0) = 0 . For state i > 1, the optimal policy * 8 (0 is given by r o , v(o < cLU + V(0) 8 ( 0 = \ (4.16) 1 1, v(i) = CLU + v(0). The value iteration algorithm in the previous section can be used to determine the optimal policy and the minimum expected total cost. We only need to replace equations (4.9) and (4.10) by Chapter 4 Distance-based Location Update 87 n + 1 (0) = (l-K)h(O) + Kv"(\). (4.17) v (4.18) where i = 1, 2, 3, A n d replace equation (4.11) by: (4.19) Simi lar to the linear cel l configuration, the optimal pol icy in a hexagonal cel l configuration also has a threshold structure i f h(i) is a non-decreasing function. In that case, where / denotes the distance threshold. Interested readers can refer to [59] for a proof of this fact. In summary, for a hexagonal cell configuration, under the assumption of a given general cell residence time distribution and random walk movement pattern, the minimum expected total cost of updating and paging as well as the optimal policy can be determined by the value iteration algorithm. Results in this section can be considered as an extension of [27]. The key difference between our results and those in [27] is that we consider mobility tracking between calls and do not make the assumption that the user's location evolves to a steady-state by the time the next cal l arrives. In addition, our model can i < I i > I. (4.20) Chapter 4 Distance-based Location Update 88 analyze any given cell residence time distribution where the model in [27] is restricted to the exponential distribution. 4.3.3 Arbitrary Cell Topology Although the model formulations of the distance-based algorithm in the previous sections give us some insight on the structure of the optimal policy and allow us to extend the work reported in [38] and [27], they are not practical for implementation simply because (1) it is difficult to keep track of the distance between two cells, and (2) the analysis are still under certain unrealistic assumptions (e.g., random walk movement pattern). To implement the distance-based algorithm efficiently, we propose that: "the mobile terminal maintains the information of the identifiers of the current cell and the cell that performed the last update. Whenever the mobile terminal crosses a cell boundary, the decision of location update is made by a simple table lookup." This model is formally described below. Let (i, j) denote the state, where i represents the identifier of the current cell that the mobile terminal is residing, and j represents the identifier of the cell in which the mobile terminal performed its last update. For a particular mobile user, different cel l residence time distributions can be assigned to different cell locations. The average residence time in each cell can be differ-ent. This is achieved by letting G(t\i) denote the cumulative distribution function of the cell residence time, given the identifier of the current cell is i. For the Markovian movement pattern in an arbitrary cell topology, we let P(k\i) denote the probabil i ty that the mobile user moves to neighboring ce l l k in the next decision epoch, given the current cell identifier is / . This captures the correlations of the user movement between two neighboring cells. If the state information includes the identi-fiers of the recently visited cells, then a history-based mobility model for a particular user can be obtained. Chapter 4 Distance-based Location Update 89 The location update cost is CLU and the paging cost function is given by h(i, j). Let v(/, j) denote the minimum expected total cost between call arrivals given state (/, j). The optimality equations are given by: v(i,j) = min ^fQ(l-e-Xt)h(i,j)G(dt\i) + ^[f^e^' v(k, j)P(k\i)G(dt\i)^, (4.21) CLU + fQ(l-e~lt)h(i,i)G(dt\i) + ^ ^ e ~ X t v(kJ)P(k\i)G(dt\i)^ where 1 < i, j < N and N denotes the number of base stations within the coverage area. The first term in (4.21) denotes the expected total cost i f no update is performed at state (i, j), while the second term denotes the expected total cost i f location update is per-formed at state (i, j). Equation (4.21) can be solved by the value iteration algorithm to * obtain the minimum expected total cost and the optimal policy 5 (/, j). Since the mobile terminals usually have limited processing power, the computations can be performed either at the base stations or the switches. Note that there are some differences between the distance thresholds computed in an arbitrary cell topology to those derived from a structured cell topology. In a structured cel l topology (e.g., hexagonal), the number of neighboring cells is the same for all cel l locations. Since the derivation of the optimal distance threshold in a structured cell config-uration is under the assumptions of symmetric random walk and i. i .d. cell residence time distribution, the optimal distance threshold is the same for all cell locations. A s an example, refer to Figure 4.3. Suppose cell "0" is the last update location and the distance threshold is equal to 3. Whenever the mobile terminal moves to a cel l location with distance threshold greater than or equal to 3, location update is performed. One the other hand, in an arbitrary cell topology, the number of neighboring cells Chapter 4 Distance-based Location Update 90 • Mobile's movement Cell " B " : Boundary cell Figure 4.4 Update boundary derived from an arbitrary cell configuration. Location update is performed whenever the mobile terminal moves to any cells labeled with " B " . is different at different cell locations. Since our proposed model allows Markovian move-ment pattern and general cell residence time distributions at different cell locations: 1. For any cells located on the update boundary, their cell-distance measured from the last updated cell location may be different. 2. Different cell locations may have different update boundary. A s an example, refer to Figure 4.4. The cell labeled with "0" is the cel l location where update was last performed. The update boundary consists of the set of cells labeled with " B " . Whenever the mobile terminal moves to those boundary cells, location update is performed. Note that some boundary cells have cell-distance equals to 2 while some have cell-distance equal to 3. After an update is performed in a boundary cell, that cell w i l l be labeled as "0" and a new set of boundary cells w i l l be chosen. For implementation, after each location update or a cal l termination, the mobile terminal needs to download the list of the update boundary cell identifiers. Whenever the mobile terminal moves to another cell , it compares the new cell identifier with the list of the update boundary cell identifiers. Location update is performed i f the new cell is one of Chapter 4 Distance-based Location Update 91 those update boundary cells. 4.4 Numerical Results and Discussions We now present some numerical results for the distance-based location update algorithm. The performance metrics are the expected total cost and the optimal distance threshold. We are interested in understanding how the (1) paging delay constraints, (2) cell residence time distributions, (3) cell topologies, and (4) movement patterns affect the expected total cost and the optimal distance threshold. 4.4.1 Paging Delay Constraints We consider a hexagonal cell configuration with random walk movement pattern. The cell residence time is assumed to be Gamma distributed with the following cumulative distri-bution function: K — 1 N G(t) = 1 - Y f K = 1 ,2 ,3 , . . . (4.22) n = 0 If 1 / f t represents the mean cell residence time, then j l = p,/K. The factor K controls the variance of the distribution. A higher value of K gives a lower variance. In this section, we assume K = 2 . The max imum paging delay corresponds to the max imum number of search iterations al lowed. When there is no paging delay constraint, we assume the paging strategy follows the shortest-distance-first order. Let state i denote the user being located in one of those cells which is i units away from the last update location. The paging cost function is: h(i) = CP[3i(i+\) + l]. (4.23) When the maximum paging delay is equal to one, all cells within the distance Chapter 4 Distance-based Location Update 92 threshold are paged simultaneously. Let / denote the distance threshold. The paging cost function is: h(i) = CP[3I(I- 1)+ 1], 0 < / < 7 o o , i>I. (4.24) When the maximum paging delay is equal to two, we assume all the cells within half the distance of the threshold are paged first. If the mobile terminal is not located, then the remaining cells within the distance threshold are paged simultaneously. For the paging cost function with distance threshold 1=1, h(i) = C p, i = 0 i > 0. (4.25) For the paging cost function with distance threshold I > 1, + 1 j , 0<i< Hi) = CP 3 I -0 I . 2 . J _2_ CP[3(I- 1 )7+1] , - 1 / _2 |i| >/ <i<I (4.26) We assume that the call arrival rate A, is 0.01 per minute, the cell crossing rate j l is 0.1 per minute, the location update cost CLU is 10, and the paging cost per cell CP is 1. Figure 4.5 shows the expected total cost versus the call arrival rate A of each user under various delay constraints. When the call arrival rate is high, the average inter-arrival time is much smaller than the average cel l residence time, in which case the network tracks the user's location perfectly. The expected total cost decreases when the call arrival rate increases. The cases of "paging delay = 1" and "no paging delay constraint" provide the upper and lower bounds for the expected total cost, respectively. A s the maximum Chapter 4 Distance-based Location Update 93 paging delay increases, there is a reduction in the expected total cost. Figure 4.6 shows the optimal distance threshold versus the call arrival rate X under various delay constraints. The optimal distance threshold decreases as the call arrival rate increases. The cases of "no delay constraint" and "paging delay = 1" provide the upper and lower bounds for the optimal distance threshold, respectively. A s the maximum paging delay increases, there is an increase in the optimal distance threshold. Figure 4.7 shows the expected total cost versus cell crossing rate j l under various delay constraints. The expected total cost increases when the outgoing rate increases. When the cell crossing rate is high, the average cell residence time is small. In that case, the mobile user moves frequently which increases the need to perform location update. Figure 4.8 shows the optimal distance threshold versus cell crossing rate p, under various delay constraints. The optimal distance threshold increases when the cell crossing rate increases. When the cell residence time is large (i.e., cell crossing rate is small), the mobile terminal has a high chance to be within the last update location. A small distance threshold reduces the paging cost. On the other hand, when the cell residence time is small (i.e., cell crossing rate is large), the mobile terminal may have crossed a large number of cells before a call arrives. A high distance threshold reduces the update cost. Figure 4.9 shows the expected total cost versus the location update cost CLU under various delay constraints. The behavior for low and high values of location update costs is in accordance with intui t ion. When the update cost is low, more updates are being performed in order to reduce the paging cost. When the update cost increases, there is no incentive to perform location update. Figure 4.10 confirms the above reasoning. The optimal distance threshold increases as the update cost increases. 4.4.2 Cell Residence Time Distributions In this section, we study the effect of the cell residence time distributions on the expected Chapter 4 Distance-based Location Update 94 total cost and the distance threshold. We assume a hexagonal cell configuration with ran-dom walk movement pattern. Three cell residence time distributions are chosen: exponen-tial, hyper-exponential, and Gamma. The Gamma distribution is stated in equation (4.22). For the hyper-exponential distribution, it has the following cumulative distribution func-tion: G(t) = 1 - [pe'^' + (1 - p)e~^\. (4.27) We assume p,j = 2 j l , p, 2 = ( 2 / 3 ) j l , and p = 0.5 . We also assume that the call arrival rate X is 0.01 per minute, the location update cost CLU is 10, and the paging cost per cell CP is 1. Figure 4.11 shows the optimal distance threshold versus the cel l crossing rate fx under different cel l residence time distributions and paging delay constraints. Results indicate that for a given cell crossing rate fx, the values of the optimal distance threshold are in general the same for these cell residence time distributions. Their values only differ for 0.007 < fx < 0.01 with paging delay constraint equals to 1 and for 0.08 < j l < 0.09 with no paging delay constraint. Figure 4.12 shows the expected total cost versus the cell crossing rate fx under three different cell residence time distributions and paging delay constraints. Results show that the expected total costs between various cell residence time distributions are quite close. One way to explain this is by observing equations (4.14)-(4.15). Different cel l residence time distributions correspond to different values of K. For example, when X = 0.01 a n d fx = 0.1: K e x p o n e n t i a l = 0.909, ^ h y p e , e x p o n e n t i a l = 0.911, a n d ^ G a m m a = 0-907 . For the range of parameters that we have chosen to investigate, the values of K under those three cell residence time distributions are quite close. Thus, the expected total costs between these distributions are also quite close. These results indicate Chapter 4 Distance-based Location Update 95 that for a hexagonal cell configuration with random walk movement pattern, the effect of changing the cell residence time distributions is not significant. 4.4.3 Cell Topologies In the previous sections, we assume a hexagonal cell configuration for the analysis. Rather than using a structured cell topology, in this section, we use a graph model to model the cellular network. In general, the interconnection of the cells can be modeled as a con-nected graph G = (N, E), where the node set N represents the set of cell or base station identifiers and the edge set E represents the connectivity between two neighboring cells. For example, referring to Figure 4.13, the node set N = {a, b, c, d, e, f, g] and the edge set E = {(a, b), (a, c), (b, c), (f, g)} . Since we are unable to obtain an actual cell topology from the public domain, we use a random graph model to represent the topology of a cellular network. The advantages of using a random graph model are: (1) the number of neighboring base stations for each base station can be different; and (2) only the nodes that are close together are connected. This models the connectivities of the neighboring base stations. The generation of a random graph is described in Section 2.4. In our model, we consider a coverage area that consists of 100 base stations with an average node degree of 4. A n example of a random graph model is shown in Figure 4.14. The cell residence time is assumed to be Gamma distributed. A symmetric random walk movement model is assumed. We also assume that the call arrival rate X is 0.01 per minute, the cell crossing rate p is 0.1 per minute, the location update cost CLU is 10, and the paging cost per cell Cp is 1. Figure 4.15 shows the relative frequency distribution of the average optimal distance threshold. For each last updated location, its average optimal distance threshold is defined as the average of all the cell-distance of the update boundary cells relative to the Chapter 4 Distance-based Location Update 96 last updated ce l l location. For illustration purpose, the optimal distance threshold is rounded to the closest integer. Figure 4.15 shows that for a random graph topology, approximately 62% of the cells have a distance threshold of 4, 25% of the cells have a distance threshold of 5, 10% of the cells have a distance threshold of 3, and 3% of the cells have a distance threshold of 6. Note that, for the same set of cost and mobility parameters, the optimal distance threshold derived from a hexagonal cell configuration is equal to 4. 4.4.4 Performance Comparisons One question arises as to the performance gain of using (1) a random graph model with Markovian movement pattern as compared to (2) a hexagonal cell configuration with sym-metric random walk movement pattern. We now compare the performance between these two models. Since the mobile user usually has a destination in mind, we model this behavior by choosing one particular node (or cell) in the random graph as the destination. Whenever the mobile user leaves the current cell , it moves to a neighboring cell which is closest to the destination. This captures the behavior of moving towards the destination. If the mobile user is staying within the destination cell, after a certain period of time it w i l l move to one of the neighboring cells. This continues until the next call arrives. We now describe the procedures of comparing the distance thresholds determined from our model to those derived from a hexagonal cell configuration. 1. Given the cost and mobility parameters, we first use a hexagonal cell configuration with symmetric random walk movement pattern to obtain the optimal distance thresh-old. This optimal distance threshold is then applied to the random graph model with Markovian movement pattern. 2. The expected total cost of location update and paging between call arrivals is then determined. This cost is denoted as "Cost (hexagonal)". The term "hexagonal" is used Chapter 4 Distance-based Location Update 97 to remind us that the optimal distance threshold is derived from the hexagonal cell configuration. 3. We also use the random graph model with the above movement pattern to determine the minimum expected total cost by solving the optimality equations. This cost is denoted as "Cost (optimal)". The term "optimal" is used to remind us that the update boundary corresponds to the optimal policy. 4. The performance gain is the cost ratio which is defined as Cost (hexagonal) / Cost (optimal). The parameters used include: call arrival rate X = 0.01 per minute, the location update cost CLU = 10, and the paging cost per cel l Cp = 1. We assume that the cel l residence time follows an i.i .d. Gamma distribution with rate p . Figure 4.16 shows the cost ratio versus the cal l arrival rate X and the location update cost CLU under different cell crossing rate p . From these figures, we observe that the cost ratio increases when p increases or X decreases. A n d it approaches unity when X or C L ( / . a r e large. In Figure 4.16 (a), when the average time between call arrivals is large (i.e., X is small), the optimal update boundary obtained from our model gives a lower cost than the distance threshold derived from the hexagonal model. However, when the average time between call arrivals is small (i.e., X is large), the mobile user does not travel much before a call arrives. Thus, the distance thresholds derive from both methods give the same performance. In Figure 4.16 (b), the variation of the cost ratio with respect to CLU is due to the changes of the optimal update boundary or distance threshold for different update cost values. When CLU is large, there is no incentive to perform location update. The expected total cost only consists of the paging cost. Thus, the cost ratio approaches unity. These results imply that in real wireless cellular networks environments in which the cell topology is not structured and the user movement pattern is not random, our model Chapter 4 Distance-based Location Update 98 can provide a more accurate update boundary than that derived from a hexagonal cell configuration with random walk movement pattern. A n d by using a more accurate location update boundary, the network can maintain a better balance between the processing incurred due to location update and the radio bandwidth utilized for paging between call arrivals. 4.4.5 Sensitivity Analysis We also perform sensitivity analysis for the optimal policy with respect to the variation of the average time between call arrivals and average cell residence time. The procedures for the sensitivity analysis are similar to those described in Section 2.5 in Chapter 2. Figure 4.17 (a) shows the cost ratio versus A ^ under different call arrival rate X and Figure 4.17 (b) shows the cost ratio versus A ^ under different cell crossing rate p.. From these figures, we observe that the cost ratio is more sensitive to the under-estimation of both X and \i. If the target cost ratio has to be less than 1.05 (i.e., 5% difference between the optimal and sub-optimal cost), then A ^ has to be greater than - 5 0 % and A ^ has to be greater than - 6 0 % . These results imply that if there is uncertainty in estimating X or p,, it may be better to over-estimate the values in order to reduce the cost ratio differ-ence. 4.5 Summary In this chapter, we proposed a stochastic model to analyze the distance-based location update algorithms. The location tracking problem is formulated as a semi-Markov deci-sion process. Based on the current state information, the mobile terminal decides whether to update its location whenever it crosses a cell boundary. The Markovian movement pattern allows the study of a variety of mobility models. For example, i f the state information includes the identifiers of the recently visited cells, Chapter 4 Distance-based Location Update 99 then a history-based mobility model for a particular user can be obtained. The cell resi-dence time follows a general distribution and can depend on the location of the cel l . The usual i . i .d. assumption for the cell residence time distribution can be relaxed. For the distance-based algorithm, we showed that the optimal policy has a thresh-old structure for nondecreasing paging cost functions. We proposed an efficient scheme to implement the distance-based algorithm in an arbitrary cell topology. After each location update or a call termination, the mobile terminal needs to download the list of the update boundary cell identifiers corresponds to its current location. Whenever the mobile terminal moves to another cell , it compares the new cell identifier with the list of the update bound-ary cel l identifiers. Location update is performed i f the new cel l is one of those update boundary cells. We presented numerical results for the distance-based update algorithm in both hexagonal and random graph models. Results indicate that the distance threshold (or update boundary) computed from our proposed model has a better performance (in terms of a lower cost) than the distance threshold derived from a hexagonal cell configuration with random walk movement pattern. These results imply that by using the optimal policy, the network maintains a good balance between the processing incurred on location update and the radio bandwidth utilized for paging between call arrivals. Chapter 4 Distance-based Location Update 100 Figure 4.6 Optimal distance threshold versus call arrival rate under various delay constraints. Chapter 4 Distance-based Location Update 101 —*— No Paging Delay Constraint •e Maximum Paging Delay = 2 A Maximum Paging Delay = 1 2 o -* * — * — • CL O &—a a -6 A A 10 Cell Crossing Rate (per minute) Figure 4.8 Optimal distance threshold versus cell crossing rate under various delay constraints. Chapter 4 Distance-based Location Update 102 250 200 •A Maximum Paging Delay = 1 •© Maximum Paging Delay = 2 - * - No Paging Delay Constraint 10' 10' Location Update Cost 10 Figure 4.9 Expected total cost versus location update cost under various delay constraints. 20 18 16 g !4 10 - * - No Paging Delay Constraint •€> Maximum Paging Delay = 2 A Maximum Paging Delay = 1 2 * -10° © • — Q- 6- <S A AAA A A' 10' 10 Location Update Cost 10° Figure 4.10 Optimal distance threshold versus location update cost under various delay constraints. Chapter 4 Distance-based Location Update 103 2 o CO cu CD o c 2 Q ; "co E •*—' Q. o 1«H 1(T (a) A Hyper-Exponential -e Exponential -*— Gamma -A 10 (b) 2 1 4 | h-CU O c 2 w b "5 E Q. O A Hyper-Exponential -© Exponential —*— Gamma 2#-10 -3 10" 10 (c) 2 o . c I— CD O c 2 b 2 A -Q. O A Hyper-Exponential •e- Exponential -#— Gamma 10 -3 1 0 ' Cell Crossing Rate (per minute) 10 Figure 4.11 Optimal distance threshold versus cell crossing rate under various cell residence time distributions and delay constraints: (a) maximum paging delay constraint = 1, (b) maximum paging delay constraint = 2, (c) no paging delay constraint. Chapter 4 Distance-based Location Update 104 (a) 50 to 40 o O | 30 H % 20 <a a. x m 10 A Hyper-Exponential •© Exponential -*— Gamma 10" 10 (b) 40 UI O O « o 30 T3 £ o (U CL X LU 20 10 A Hyper-Exponential •O Exponential Gamma 10 10 (c) (0 o O o T3 Ti (1) CL X LU 30 25 20 15 10 5 A Hyper-Exponential •© Exponential - * - Gamma 0 10" 10 10" Cell Crossing Rate (per minute) Figure 4.12 Expected total cost versus cell crossing rate under various cell residence time distributions and paging delay constraints: (a) maximum paging delay = 1, (b) maximum paging delay = 2, (c) no paging delay constraint. Chapter 4 Distance-based Location Update 105 a b c Cells (a) The cell topology. (b) Graph model showing the interconnections of the cells. Figure 4.13 Representation of a cellular network topology by a graph model. Horizontal Distance Figure 4.14 Graph model with an average node degree of 4. The nodes represent the location of the base stations. A n edge between two nodes represents those two base stations are neighbors to each other. Chapter 4 Distance-based Location Update 106 100 90 h 80 h 70 60 co 50 40 30 20 r 3 4 5 Distance Threshold Figure 4.15 Optimal distance threshold distribution. Figure 4.16 Cost ratio versus call arrival rate and location update cost under different cell crossing rate. Chapter 4 Distance-based Location Update 107 (b) 1.25 a. o_ to o O (0 E 1.2 1.15 1.1 O 1 - o - u = 0.2 u. = 0.1 . A- H = 0.05 • O u = 0.03 100 -50 0 50 100 Percentage change in average cell residence time (%) -100 -50 0 50 100 Percentage change in average time between call arrivals (%) Figure 4.17 (a) Cost ratio versus percentage change in average time between call arrivals under different call arrival rate; (b) Cost ratio versus percentage change in average cell residence time under different cell crossing rate. "Ifall, I stand stiff... I trudge on, Igain a little... Iget more eager and climb higher and begin to see the. xvidening horizon. "Every struggle is a victory." Helen "Keller, 1880-1968. Chapter 5 Conclusions We conclude this dissertation with a summary of our contributions and directions for future work. 5.1 Summary This research begins with a study of inter-switch handoff in wireless A T M networks. Path optimization may be necessary i f the end-to-end path after connection rerouting is not optimal. • In Chapter 2, we proposed and analyzed three different path optimization schemes which are simple to implement. In the exponential path optimization scheme, the time between path optimizations is modeled as an exponentially distributed random variable. The periodic path optimization scheme invokes path optimization at periodic time intervals. In the Bernoulli scheme, path optimization is performed with a fixed probability after each path extension. A discrete time analytical model and a discrete event simulation model were proposed to compare the performance of these schemes by evaluating the expected total cost during a call . The analytical model enables a closed-form expression and optimal operating point to be obtained for each path optimization scheme. The analytical and simulation results agree with each other, corroborating the two models. Results indicate that the 108 \er 5 Conclusions 109 Bernoulli scheme outperforms the other two schemes by providing a lower expected cost per call and a lower percentage change of expected cost relative to the variation of the average time between inter-switch handoffs. • In Chapter 3, we addressed the issue of when to initiate path optimization by proposing a stochastic model. The path optimization problem is formulated as a semi-Markov decision process. Based on current state information, the network decides whether to perform path optimization after path extension. The time between inter-switch handoff follows a general distribution and can depend on the location of the anchor switch. We presented the value iteration algorithm which solves the optimality equations. A stationary deterministic optimal policy is obtained. Under certain conditions, the optimal policy has a threshold structure. That is, path optimization is always performed when the number of links of the path is greater than a certain threshold. The threshold structure of the optimal policy facilitates the implementation. When inter-switch handoff occurs, the decision of performing path optimization can be made by a simple table lookup. The performance of the optimal policy was compared with four heuristics, namely, "always perform path optimization", "never perform path optimization", "periodic", and "Bernoull i" path optimization. Simulation results indicate the optimal policy gives a lower expected cost per call than the other four heuristics. These results imply that by using the optimal policy, the mobile connection maintains a good balance between the network resources utilized and the signaling load incurred on the network during its connection lifetime. We also performed the sensitivity analysis for the optimal policy with respect to the variation of the average call duration and the average time between inter-switch handoffs. Results indicate that the optimal policy is relatively insensitive to the change of the average Chapter 5 Conclusions 110 time between inter-switch handoffs. If there is uncertainty in estimating the average call duration, it may be better to over-estimate the value in order to reduce the cost ratio difference. Another part of this thesis focused on location update in wireless cellular networks. Although it has been shown that the distance-based update algorithm has a better performance than the L A , movement, and timer based update schemes, the determination of the optimal distance threshold is often under certain unrealistic assumptions. • In Chapter 4, we proposed a stochastic model to analyze the distance-based location update algorithm. The location tracking problem is formulated as a semi-Markov decision process. Based on the current state information, the mobile terminal decides whether to update its location whenever it crosses a cell boundary. The Markovian movement pattern allows the study of a variety of mobility models. For example, i f the state information includes the identifiers of the recently visited cells, then a history-based mobility model for a particular user can be obtained. The cell residence time follows a general distribution and can depend on the location of the cell. The usual i.i .d. assumption for the cell residence time distribution can be relaxed. For the distance-based algorithm, we showed that the optimal policy has a threshold structure for nondecreasing paging cost functions. We proposed an efficient scheme to implement the distance-based algorithm in an arbitrary cell topology. Each mobile terminal only has to maintain the information of the identifiers of the current cell and the cell that performed the last update. Whenever the mobile terminal crosses a cell boundary, the decision of location update is made by a simple table lookup. We presented numerical results for the distance-based update algorithm in both hexagonal and random graph topologies. Results indicate that the distance threshold (or update boundary) Chapter 5 Conclusions 111 computed from our proposed model has a better performance (in terms of a lower cost) than the distance threshold determined from the hexagonal cell configuration with random walk movement pattern. These results imply that by using the optimal policy, the network can maintain a good balance between the processing incurred on location update and the radio bandwidth utilized for paging between call arrivals. 5.2 Further work In the course of the investigations reported in this thesis, a number of interesting problems have been discovered which merit further research. • Multicast Handoff: The support of multicast handoff is similar to the support of dynamic multicasting in which users can leave or join the multicast tree. If the target switch is part of the multicast tree, the handoff function can be invoked similar to the dynamic joint function in multicasting. If the target switch is not part of the multicast tree, path rerouting or path extension schemes can be still used. If path extension scheme is used [62], the crossover switch algorithm requires modification. Termination of the old subpath is required only i f there is no group users connected to the old subpath within the multicast tree. Although path extension scheme seems to be easier to implement, issues like the increase of the path length and the formation of loops still need to be addressed. Path optimization within a multicast tree may not be a simple procedure. Further work is required in this area. • State-based models: The proposed model in Chapter 4 can be used to analyze the movement-based and timer-based location update algorithms, and to study the effects of correlations between the cell residence times of adjacent cells. Our Chapter 5 Conclusions 112 proposed model can also be extended to study the location tracking algorithms in a wireless two-way messaging system [78], in which there is an additional holding cost to account for delaying the delivery of a message. Most of the models proposed in the literature (including the one we proposed in Chapter 4) assume the call arrival rate for a particular mobile user follows a Poisson distribution. Results in [31 ] show that it may not be the case. This points to the need for new analytical models for location tracking under general call arrival distributions. • User Profile: Several location update and paging strategies improve the network performance by predicting the user's location based on his velocity, probability distribution, etc. This information has to be stored in the user profile. A n efficient way to collect, store, update, and disseminate the user profile information is crucial. • Heterogeneous Networks: As part of the IMT-2000 system, the mobile terminal wi l l be able to communicate with several networks at the same time. Rather than performing location update with different networks, it is desirable i f the mobile terminal only needs to report its location to a single network. This network wi l l then disseminate the location information to other networks. A n efficient way to disseminate and retrieve the information remains an open issue. Bibliography [1] A . S. Acampora and M . Naghshineh, " A n Architecture and Methodology for Mobile-Executed Hand-off in Cellular A T M Networks," IEEE I. Select. Areas Commun. vol. 12, no. 8, pp. 1365-1375, Oct. 1994. [2] A . Acharya, J. L i , and D . Raychaudhuri, "Primitives for Location Management and Handoff in Mobi le A T M Networks," ATM Forum Contribution 96-1121, Aug . 1996. [3] A . Acharya, J. L i , B . Rajagopalan, and D . Raychaudhuri, "Mobi l i ty Management in Wireless A T M Networks," IEEE Commun. Mag., vol. 35, no. 11, pp. 100-109, Nov. 1997. [4] I. F. Akyi ld iz , J. Ho, and Y . - B . L i n , "Movement-based Location Update and Selective Paging for PCS networks," IEEE/ACM Trans. Networking, vol. 4, no. 4, pp. 629-638, Aug . 1996. [5] I. F. Akyi ld iz , J. McNair , J. Ho, H . Uzunalioglu, and W. Wang, "Mobi l i ty Management in Next-Generation Wireless Systems," Proc. of the IEEE, vol . 87, no. 8, pp. 1347-1384, Aug . 1999. [6] B . A . A k y o l and D . C . Cox, "Signaling Alternatives in a Wireless A T M Network," IEEE J. Select. Areas in Commun., vol. 15, no. 1, pp. 35-49, Jan. 1997. [7] M . Asawa and W. E . Stark, "Optimal Scheduling of Handoffs in Cellular Networks," IEEE/ACM Trans, on Networking, vol. 4, no. 3, pp. 428-441, June 1996. [8] The A T M Forum Wireless A T M Working Group, "Wireless A T M Capability Set 1 Specification - Draft," BTD-WATM-01.13, Jan. 2000. 113 Bibliography 114 [9] The A T M Forum Technical Committee, " A T M User-Networks Interface (UNI) Specification Version 3.1, Sept. 1994. [10] The A T M Forum Technical Committee, "Private Network-to-Network Interface Specification Version 1.0 (PNNI 1.0)," af-pnni-0055.000, March 1996. [11] B . A . J. Banh, G . J. Anido, and E . Dutkiewicz, "Handover Re-routing Schemes for Connection Oriented Services in Mobi le A T M Networks," in Proc. IEEE INFOCOM'98, San Francisco, C A , pp. 1139-1146, March/Apri l 1998. [12] A . Bar-Noy, I. Kessler, and M . Sidi , "Mobi le Users: To Update or Not to Update?" ACM/Baltzer I. Wireless Networks, vol. 1, no. 2, pp. 175-195, July 1995. [13] D . Bertsekas and R. Gallager, Data Networks, 2nd edition, Prentice Hal l , 1992. [14] R. R. Bhat and R. Gupta, "Framework for Dynamic C O S Discovery in Wireless A T M , " ATM Forum Contribution 98-0005, Feb. 1998. [15] R. R. Bhat, "Extension to Backward C O S Discovery ( B C D ) Approach," ATM Forum Contribution 98-0231, Apr i l 1998. [16] A . Bhattacharya and S. K . Das, "LeZi-Update: A n Information-Theoretic Approach to Track Mobile Users in PCS networks," in Proc. of ACM/IEEE MobiCom'99, Seattle, W A , pp. 1-12, Aug . 1999. [17] G . Bianchi, A . T. Campbell, and R. Liao, "On Utility-Fair Adaptive Services in Wireless Networks," in Proc. IEEE/IFIP TWQoS'98, Napa Valley, C A , M a y 1998. [18] Common E T S I - A T M Forum reference model for Wireless A T M Access Systems (WACS) , B R A N - D T R - B R A N - 0 4 0 0 0 1 VO.3.2, July 1998. [19] M . B . Doar, "Better Model for Generating Test Networks," in Proc. IEEE GLOBECOM'96, London, U K , pp. 86-93, 1996. Bibliography 115 [20] G . Dommety, M . Veeraraghavan, and M . Singhal, "Route Optimization in Mobi le A T M Networks," ACM/Baltzer Mobile Networks and Applications, vol . 3, no. 2, pp. 203-220, Aug . 1998. [21] G . Dommety, M . Veeraraghavan, and M . Singhal, " A Route Optimization Algorithm and Its Application to Mobile Location Management in A T M Networks," IEEE J. Select. Areas Commun., vol. 16, no. 6, pp. 890-908, Aug . 1998. [22] E I A / T I A IS-41.3 (Revision B) , Cellular Radio-Telecommunications Intersystem Operations, July 1991. [23] Y. Fang, I. Chlamtac, and Y . - B . L i n , "Modeling PCS Networks Under General Cal l Holding Time and Cel l Residence Time Distributions," IEEE/ACM Trans. Networking, vol. 5, no. 6, pp. 893-906, Dec. 1997. [24] A . Farago and I. Chlamtac, "Virtual Path Network Topology Optimization Using Random Graphs," in Proc. IEEE INFOCOM'99, New York, N . Y . , March 1999. [25] R. Ghai and S. Singh, " A n Architecture and Communication Protocol for Picocellular Networks," IEEE Personal Communications, 3rd quarter, pp. 36-46, 1994. [26] R. Guerin and A . Orda, "QoS Routing in Networks with Inaccurate Information: Theory and Algorithms," IEEE/ACM Trans. Networking, vol . 7, no. 3, pp. 350-364, June 1999. [27] J. Ho and I. F. Akyi ld iz , "Mobi le User Location Update and Paging under Delay Constraints," ACM/Baltzer I. Wireless Networks, vol. 1, no. 4, pp. 413-425, Dec. 1995. [28] IEEE J. Select. Areas Commun., special issue on Wireless A T M , vol. 15, no. 1, Jan. 1997. [29] IEEE Communications Magazine, special issue on Introduction to Mobi le and Wireless A T M , vol . 35, no. 11, Nov. 1997. Bibliography 116 [30] IEEE Personal Communications, special issue on IMT-2000: Standards Efforts of the I T U , vol . 4, no. 4, Aug . 1997. [31] J. Jannink, D . Lam, N . Shivakumar, J. Widom, A n d D . Cox, "Efficient and Flexible Location Management Techniques for Wireless Communication Systems," ACM/ BaltzerJ. Wireless Networks, vol. 3, pp. 361-374, Oct. 1997. [32] D . Lam, D . Cox, and J. Widom, "Teletraffic Modeling for Personal Communications Services," IEEE Commun. Mag., vol. 35, no. 2, pp. 79-87, Feb. 1997. [33] J. L i and A . Acharya, "Handoff Control for Point to Multipoint Connections in Mobi le A T M Networks," in Proc. IEEE Globecom'98, Sydney, Australia, November 1998. [34] J. L i , R. Yates, and D . Raychaudhuri, "Performance Analysis on Path Rerouting Algorithms for Handoff Control in Mobile A T M Networks," in Proc. IEEE INFOCOM'99, New York, N Y , March 1999. [35] B . Liang and Z . Haas, "Predictive Distance-based Mobil i ty Management for PCS Networks," in Proc. IEEE INFOCOM'99, New York, N Y , March 1999. [36] T L i u , P. Bahl , and I. Chlamtac, "Mobil i ty Modeling, Location Tracking, and Trajectory Prediction in Wireless A T M Networks," IEEE J. Select. Areas Commun., vol. 16, no, 6, pp. 922-936, August 1998. [37] D . H . Lorenz and A . Orda, "QoS Routing in Networks with Uncertain Parameters," IEEE/ACM Trans. Networking, vol. 6, no. 6, pp. 768-778, Dec. 1998. [38] U . Madhow, M . Honig, and K . Steiglitz, "Optimization of Wireless Resources for Personal Communications Mobil i ty Tracking," IEEE/ACM Trans. Networking, vol . 3, no. 4, pp. 698-707, Dec. 1995. [39] The M A G I C W A N D homepage: http://www.tik.ee.ethz.ch/~wand Bibliography 117 [40] H . Mitts, H . Hansen, J. Immonen, and S. Veikkolainen, "Lossless Handover for Wireless A T M , " ACM/Baltzer Mobile Networks and Applications, vol. 1, no. 3, pp. 299-312, Dec. 1996. [41] M . Mouly and M . - B . Pautet, The GSM System for Mobile Communications, Palaiseau, France, 1992. [42] Z . Naor and H . Levy, "Minimiz ing the Wireless Cost of Tracking Mobi le Users: A n Adaptive Threshold Scheme," in Proc. IEEE INFOCOM^S, San Francisco, C A , pp. 720-727, March/Apri l 1998. [43] Z . Naor and H . Levy, "Ce l l Identification Codes for Tracking Mobi le Users," in Proc. IEEE INFOCOM'99, New York, N Y , March 1999. [44] C . E . Perkins and D . B . Johnson, "Mobil i ty Support in IPv6," draft-ietf-mobileip-ipv6-09.txt, work in progress, Oct. 1999. [45] G . P. Poll ini and C . - L . I, " A Profile-Based Location Strategy and Its Performance," IEEEJ. Select. Areas Commun., vol. 15, no, 8, pp. 1415-1424, Oct. 1997. [46] M . L . Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1994. [47] R. Ramjee, T. F. L a Porta, J. Kurose, and D . Towsley, "Performance Evaluation of Connection Rerouting Schemes for ATM-Based Wireless Networks," IEEE/ACM Trans. Networking, vol. 6, no. 3, pp. 249-261, June 1998. [48] S. Rao, B . Gopinath, and D . Kurshan, "Optimizing Ca l l Management of Mobi le Units," in Proc. IEEE PIMRC'92, Boston, M A , pp. 225-229, 1992. [49] K . Rauhala, "Requirements for Mobi le A T M Handover," ATM Forum Contribution 96-989, August 1996. Bibliography 118 [50] D . Raychaudhuri and N . D . Wilson, "ATM-Based Transport Architecture for Multiservices Wireless Personal Communication Networks," IEEE J. Select. Areas Commun., vol. 12, no. 8, pp. 1401-1414, Oct. 1994. [51] D . Raychaudhuri, L . J. French, R. J. Siracusa, S. K . Biswas, R. Yuan, P. Narasimhan, and C . A . Johnson, "WATMnet: A Prototype Wireless A T M System for Mult imedia Personal Communication," IEEE J. Select. Areas Commun., vol. 15, no. 1, pp. 83-95, Jan. 1997. [52] C . Rose and R. Yates, "Minimiz ing the Average Cost of Paging under Delay Constraints," ACM/Baltzer J. Wireless Networks, vol. 1, no. 2, pp. 211-219, July 1995. [53] C . Rose, "Minimiz ing the Average Cost of Paging and Registration: A Timer-based Method," ACM/Baltzer I. Wireless Networks, vol. 2, no. 2, pp. 109-116, June 1996. [54] C . Rose and R. Yates, "Location Uncertainty in Mobi le Networks: A Theoretical Framework," IEEE Commun. Mag., vol. 35, no. 2, pp. 94-101, Feb. 1997. [55] C. Rose, "State-based Paging/Registration: A Greedy Technique," IEEE Trans. Vehicular Technology, vol. 48, no. 1, pp. 166-173, Jan. 1999. [56] S. M . Ross, Introduction to Stochastic Dynamic Programming. Academic Press, New York, 1983. [57] R . Sanchez, J. Evans, G . Minden, V. Frost, and K . Shanmugan, " R D R N : A Prototype for a Rapidly Deployable Radio Network," ACM Computing and Commun. Review, vol. 2, no. 2, pp. 15- 22. [58] S. K . Sen, A . Bhattacharya, and S. K . Das, " A Selective Location Update Strategy for P C S Users," ACM/Baltzer J. Wireless Networks, vol. 5, no. 5, pp. 313-326, Sept. 1999. [59] S. S. Stidham, Jr., "Socially and Individually Optimal Control of Arrivals to a G I / M / 1 Queue," Man . Sci. vol. 24, pp. 1598-1610, 1978. Bibliography 119 [60] S: Tabbane, " A n Alternative Strategy for Location Tracking," IEEE J. Select. Areas Commun., vol. 13, no. 5, pp. 880-892, June 1995. [61] C . - K . Toh, "Crossover Switch Discovery for Wireless A T M L A N s , " ACM/Baltzer Mobile Networks and Applications, vol. 1, no. 2 pp. 141-165, Oct. 1996. [62] C . - K . Toh, " A Unifying Methodology for Handover of Heterogeneous Connections in Wireless A T M Networks," ACM SIGCOMM Computer Communications Review, vol. 27, no. 1, pp. 12-30, Jan. 1997. [63] C . - K . Toh, Wireless ATM and Ad-Hoc Networks, Kluwer Academic Publishers, Boston 1997. [64] L . Van Hauwermeiren, L . Vercauteren, A . Saidi, and T. Van Landegem, "Requirements for Mobil i ty Support in A T M , " in Proc. IEEE GLOBECOM'94, San Francisco, C A , pp. 1691-1695, 1994. [65] M . Veeraraghavan, M . Karol , and K . Eng, " A Combined Handoff Scheme for Mobi le A T M Networks," ATM Forum Contribution 96-1700, Dec. 1996. [66] M . Veeraraghavan, M . Karol , and K . Eng, "Mobil i ty and Connection Management in a Wireless A T M L A N , " IEEE J. Select. Areas Commun., vol. 15, no. 1, pp. 50-68, Jan. 1997 [67] M . Veeraraghavan and G . Dommety, "Mobi le Location Management in A T M Networks," IEEE J. Select. Areas Commun., vol. 15, no. 8, pp. 1437-1454, Oct. 1997. [68] G . Wan and E . L i n , " A Dynamic Paging Scheme for Wireless Communication Systems," in Proc. ACM/IEEEMobiCom'97, Budapest, Hungary, pp. 195-203, 1997. [69] Z . Wang and J. Crowcroft, "Quality-of Service Routing for Supporting Multimedia Applications," IEEE J. Select. Areas Commun., vol. 14, no. 7, pp. 1228-1234, Sept. 1996. Bibliography 120 [70] W. S. V. Wong and V. Leung, " A Path Optimization Signaling Protocol for Inter-Switch Handoff in Wireless A T M Networks," in Proc. of the 1st International Workshop on Wireless Mobile ATM Implementation (wmATM), Hangzhou, China, pp. 92-98, Apr i l 1998. [71] W. S. V. Wong and V. C. M . Leung, " A Path Optimization Signaling Protocol for Inter-Switch Handoff in Wireless A T M Networks," Computer Networks, vol . 31, no. 9-10, pp. 975-984, May 1999. [72] W. S. V. Wong, H . Chan, and V. C. M . Leung, "Path Optimization for Inter-Switch Handoff in Wireless A T M Networks," in Proc. IEEE International Conf. on Universal Personal Communications (ICUPC), Florence, Italy, pp. 615-619, Oct. 1998. [73] W. S. V. Wong, H . Chan, and V. C. M . Leung, "Performance Evaluations of Path Optimization Schemes for Inter-Switch Handoffs in Wireless A T M Networks," in Proc. ACM/IEEEMobiCom'98, Dallas, Texas, pp. 242-251, Oct. 1998. [74] W. S. V. Wong, H . Chan, and V. C. M . Leung, " A Framework for Analyzing Path Optimization Schemes for Inter-Switch Handoff in Wireless A T M Networks," in Proc. IEEE ICC'99, Vancouver, Canada, June 1999. [75] W. S. V. Wong, H . Chan, and V. C. M . Leung, "Performance Evaluations of Path Optimization Schemes for Inter-Switch Handoffs in Wireless A T M Networks," accepted for publication in ACM/Baltzer Wireless Networks. [76] W. S. V. Wong, M . E . Lewis, and V. C. M . Leung, "Stochastic Control of Path Optimization for Inter-Switch Handoffs in Wireless A T M Networks," submitted to IEEE/ACM Trans, on Networking. [77] W. S. V. Wong and V. C. M . Leung, " A Framework for Analyzing Location Update Algorithms in Wireless Cellular Networks," submitted. Bibliography 121 [78] T. Woo, T. L a Porta, J. Golestani, and A . Agarwal, "Update and Search Algorithms for Wireless Two-Way Messaging: Design and Performance," in Proc. IEEE INFOCOM, San Francisco, C A , March/Apri l 1998. [79] R. Yuan, S. K . Biswas, and D . Raychaudhuri, " A Signaling and Control Architecture for Mobi l i ty Support in Wireless A T M Networks," in Proc. IEEE ICC96, Dallas, Texas, pp. 478-484, 1996. [80] E . W. Zegura, K . L . Calvert, and M . J. Donahoo, " A Quantitative Comparison of Graph-Based Models for Internet Topology," IEEE/ACM Trans. Networking, vol . 5, no. 6, pp. 770-783, Dec. 1997. [81] M . M . Zonoozi and P. Dassanayake, "User Mobil i ty Modeling and Characterization of Mobi l i ty Patterns," IEEE J. Select. Areas Commun., vol. 15, no. 7, pp. 1239-1252, Sept. 1997. Appendix A. Expected Cost for the Exponential Path Optimization Scheme In this appendix, we derive the expected cost per call for the exponential path optimization scheme. The notations used follow the analytical model described in Chapter 2. Referring to Figure A . l , the following notations are defined to facilitate the derivation: ct = c\ + c/ i-1 i+1 1 r n-l n Figure A . 1 Timing diagram • n denote the call termination time. • Ci denote the total cost during time interval [i, • c/ denote the link cost during time interval [/, i+1). • C / denote the signaling cost at time i . The cost functions C , , C- , and C- are related by the following equation: time Ci = c/+c/ (A.1) Two indicator functions are defined: j 1, i f path extension occurs at time i , 1 10, otherwise. (A.2) [a, b) denote the interval between a and b that includes a but not b. 122' Appendix A. Expected Cost for the Exponential Path Optimization Scheme 123 [ 1, i f path optimization occurs at time i , I i = \ ~ . (A.3) 0, otherwise. Since at each time interval, path extension and path optimization are modeled as Bernoulli processes with probabilities A and v , respectively, we have: £ [ / • ] = A and £ [ / , ] = v . (A.4) For the initial conditions, i.e., at i = 0 , we assume: C0S = 0 • and CQl = LClink. (A.5) Their expected values are: E[CQS] = 0 and E[C0l] = LClink . (A.6) For the signaling cost due to mobility at time i: C- = IfpE + IiCpo i>\ . (A.7) Taking the expectation: E[Cts] = 7iCPE + vCP0 i>\ . (A.8) For the link cost between time interval [i, i+1): Cli = +IiHClink)(l-Ii) + LCnJi i*l • (A.9) Taking the expectation, we have: Appendix A. Expected Cost for the Exponential Path Optimization Scheme 124 £ [ C / ] = (l-v)E[Cil_l] + [(i-v)XH + vL]Clink. (A.10) For i > 1, it can be proved by mathematical induction that: £ [ C / ] = ( l - v ) I L C / . n f c + [ l + ( l - v ) + ... + ( l - v ) i _ 1 ] M ( A . l l ) where M = (1 - v)\HClink + vLClink . Equation ( A . l 1) can also be written as: E[C!] = ( l - v ) i L C l i n k + l {l V ) M / > 0 (A.12) The expected cost of the call when using the exponential path optimization scheme is: E[Cexponential ~ E<E n = 1 rn- 1 -n -i = 0 -(A. 13) • M - l 1E n = 1 7V = n = 0 1 Z ( c / + c/) P(N = n) N = n \P(N = n) •i = 0 The expected signaling cost of the call: Appendix A. Expected Cost for the Exponential Path Optimization Scheme 125 oo p i - 1 X ( C , ' | / V = n) P(N = n) n = 1 U = 0 oo n - 1 n = 2 i = 1 (A.14) = aCP£ + v C P O ) X ( » - ! ) ( ! - H ) " V n = 2 ( i - n ) I1 ( A C P £ + v C P 0 ) . The expected link cost of the call: 71-1 X (c/ ^ = ») n = 1 U = 0 rn-l F(7V = n) = X X ^ 1 - ^ 1 ^ + l - ( l - v ) ' n = 1 = 0 - X I ^T< ~LClink + w = 1 h V W l - ( l - V ) V , 2 M ^P(7V = n) l i n k p [ l - ( l - p ) ( l - v ) ] l i n k ' (A.15) Substituting equations (A.14) and (A.15) into equation (A. 13), we have: E[C exponential ] = r + Ml-M-)( l -v)# r " n * p [ l - ( l - p ) ( l - v ) ] 0 - ^ ( A C P £ + v C P O ) . P (A. 16) Appendix B. Expected Cost for the Periodic Path Optimization Scheme In this appendix, we derive the expected cost per call for the periodic path optimization scheme. The notations and definitions used follow those defined in Chapter 2 and Appen-dix A . In addition, we let k denote the period to invoke path optimization. The value of k is a positive integer and is measured in time interval as defined in Chapter 2. A n indicator function, which models the time to perform periodic path optimization, is defined as: _ | 1, i f i mod k = 0, ' [ 0, otherwise. Thus, / • is equal to 1 whenever time / is a multiple of k. For the signaling cost due to mobility at time i: C- = ItCpE+IiCpo i>l. (B.2) Taking the expectation: E[Cts] = XCpE+TiCpo i>\. (B.3) For the link cost between time interval [i, C\ = (c/_ j + liHCUnk){\ -Tt) + TtLClink. (B.4) Taking the expectation: E[C!] = (l-T^EiC^^ + Kl-T^XH + T^Cn^. (B.5) Since E[CQl] = LC[ink , equation (B.5) can also be written as: 126 Appendix B. Expected Cost for the Periodic Path Optimization Scheme 127 £ [ C / ] = LClink + XHClink(i mod k) i>0. (B.6) The expected cost of the^all is: E\-C periodic^ = X E n = \ U=0 N = n P(N = n) (B.7) The expected signaling cost of the call: n = 1 P(N = n) m-l I X (C / | /V = n) U = o oo n - 1 n = 2 ( = 0 n - 1 = ^ c P £ x i n p ( N =")] + c ™ X X Tipw = ") n = 2 « = 2 i = 0 oo oo k = ^ ^ W l - l i f V ] + C P 0 X X JP(N = jk + m) n = 2 j = 1 m = 1 O O = ^ } C / J £ + C , 0 X I ; ( l - H ) i i + B-V y = 1 m = 1 _ X ( l - f i ) ^ I - ( I - M - ) (B.8) The expected link cost of the call: Appendix B. Expected Cost for the Periodic Path Optimization Scheme 128 r n - l X (C / N = n) \P(N = n) n = 1 U = 0 oo n - 1 X X llCUnk + ^HClink(i mod = n) n=\ i=0 k-\ LCUnk X [nP(N = « ) ] + A t f C ^ X n = 1. An = 1 ifc-1 n = 1 m = 1 /t- 1 ™X X p(N = j) L ,= 1 j = ki-(k-\-m) OO oo mX X L (=1 j = ki-(k-\-m) (B.9) £ m ( l - i x ) l - ( l - u T m = i r 1 U. [ 1 - ( 1 - M-) 1 Substituting equations (B.8) and (B.9) into equation (B.7), we have: E[C periociic] M i - n ) H C , „ f e [ i ^ ( i _ ^ _ 1 + ( ^ _ i ) ( i _ ^ ] (B.10) A ( l - | i ) r (1 -u) r + ~ ^PE + k PO' V l - ( l - J i ) Appendix C. Expected Cost for the Bernoulli Path Optimization Scheme In this appendix, we derive the expected cost per call for the Bernoulli path optimization scheme. Following the notations and definitions used in Chapter 2 and Appendix A , we also define an indicator random variable: j j l , perform path optimization after path extension at time i , 1 [O, otherwise. Since path optimization is invoked with probability p after each path extension, we have: E[Ii\ = p. ( C 2 ) Note that in our analytical model, path extension and path optimization are modeled as point processes. Thus, the time required to perform these operations is not taken into account. For the signaling cost due to mobility at time i: C- = IiiCpE + IiCpo) i>\. (C.3) Taking the expectation: E[C-} = MCPE + PCP0) i>l. (CA) For the link cost between time interval [i, i+1): Cl = < _ , ( ! - / , . ) + ( C / . , + HClink)I:(!-/,)+ LCuM . (C.5) Taking the expectation: 5 [ C / ] = (l-Xp)E[Cil_l] + [X(l-p)H + lpL]ClM. (C.6) 129 Appendix C. Expected Cost for the Bernoulli Path Optimization Scheme 130 Since E[C0 ] = LClink , it can be proved by mathematical induction that for i > 1: £ [ C / ] = (l-Xp)'LClink + [i + (i-M + ... + (i-M'' -1]* = {\-Xp)lLClink + Xp (C.7) K where/? = [X( \ -p)H + XpL]C link ' The expected cost of the call when using the Bernoulli path optimization scheme is: \P(N = n ) . (C.8) E[CBernoulli] ~ X E n = 1 m -1 I(c/ + c/) 4 = 0 /V = n The expected signaling cost of the call: P(7Y = n) r n - l X ( C / | i V = n) oo n — 1 . = X X ^ C P £ + PCPO)P(N =N) n = 2 i = 1 = M C P £ + pcPO)X(«-1)(1-i-o,I"V n = 2 = M i ^ ) ( C p £ + pcP0) (C9) The expected link cost of the call: r n - l 4 = 0 n = 1 oo r n - \ rc=1W=0 X ( C / / V = «) P(N = n) fP(/V = n) L A , ( l - p ) ( l - n ) / f P ^ p [ l - ( l - A . / ? ) ( l - p ) ] / , n * ' (CIO) Appendix C. Expected Cost for the Bernoulli Path Optimization Scheme Substituting equations (C.9) and (CIO) into equation (C.8), we have: mr ^ = LC + M l - p ) ( l - H ) g C < f a j b ^Bernoulli* ^link ^[1 - (l - Xp)(l -"Another roof, another proof." TauPEraas, 1913-1996. Appendix D. Semi-Markov Decision Processes Proposit ion D . l : Assume the cost, transition probabilities, and sojourn times are time homogeneous. If the termination time of a finite-horizon semi-Markov decision process is exponentially distributed with mean 1/u., then it is equivalent to an infinite-horizon semi-Markov decision process with discount rate p,. That is, r4»(T) 4>(r)-l A * ) = En\ X b{Xn, Yn) + X [j; + 1 / ( W t , X „ , T „ ) J t U = 0 n = 0 + f f(WvXl{T),Yl{T))ax + h(XHT))\ is equivalent to where ( D . l ) ^S) = E:\^e-"\(Xn,Yn)\ (D.2) c(s,a) = b(s,a) + Eas\j\ wf{Ws, a)dt + (l -e (D.3) Proof: For clarity, we wi l l analyze the four terms in (D. l ) separately. Let vn(s) = ul(s) + u\(s) + 1*3(5) + ^ 4 ( 5 ) (D-4) 132 Appendix D. Semi-Markov Decision Processes 133 where "fr) = E*\ X b(Xn, Yn) (D.5) U = o J '4>(T)-1 fr) = *J X [£+7(wrx„yB)*r (D.6) n = 0 = EnsUT^Tf(WvXl{T), Yl{T))dx (D.7) IIJ(J) = Ens{h(X,(T))} (D.8) For (D.5), u*{s) = E*\ X b(Xn, Yn) U = o 4K0 X ^) U = 0 If m represents the last decision epoch before termination, then -To = 4 x C ^ m = 0 Ln = 0 X Yn) \le ^'dt B y interchanging the order of summation, we have o o o o •To-*? X xC"''(X»•,'"¥e"," L n = 0 m = n Since Y f°" + 1(-)^ = f CO*. Jo J (T „ Appendix D. Semi-Markov Decision Processes 134 = I fa HXn, F M )p<f ^ j = X e-^b(Xn, Yn) L n = 0 For (D.6), we have u2(s) Es\ x [j ; ;7 (w r x„ ,y„)jT rm - 1 '-m = 1 <-n = 0 B y interchanging the order of summation, we obtain, TC, . u2(s) ( o o o o n = 0 m = n + l " L " J j • £*f ix.,Kr,/(,v"x-y»)AK'"*} = 0 = 0 For (D.7), = {^r / ( W t , ^ ( r ) , y ^ ( r ) ) J x l pe (D.9) (D.10) If n represents the last decision epoch before termination, then Appendix D.v Semi-Markov Decision Processes 135 ( oo n = 0 " " B y interchanging the order of integration, we have, 3 w = ^{xC;*'[C*,/(H'"x»'i'»)t"!"1"* = 0 " dx = E*s\ ^fa" + i[e^-e-^]f(WvXn,Yn)dx '-n = 0 ( D . l l ) For (D.8) ul(s) = E*{h(XHT))} = 0 (D.12) U = 0 Substitute (D.9)-(D.12) into (D.4), we obtain: v-(.) = E:\ 2 r^°"MX„,y„) + f"+ie^f(WvXn,Yn)dx •*n = 0 = d I ^ " [ ^ , F„) + f^e-^nW,, Xn, Yn)dx_ ( D . l 3) ^n = 0 Appendix D. Semi-Markov Decision Processes 136 { oo I [e~^HXn, Yn) + foye^f(Wv Xn, Y n)dx n = 0 " + (e -e )h(Xn)] \ U = 0 (D.14) •0-n+l - U . ( T - O j + ( l - ^ " + > ( X „ ) ] . Recall c(s, a) denotes the expected total cost between two decision epochs, given that the system occupies state s at the first decision epoch and that the decision maker choose action a in state s. Since the cost, transition probabilities, and sojourn times are assumed to be time homogeneous, c(s,a) = b(s,a) + Eas^j\~iitf(Wt,s,a)dt + (1 - <f^ ' ) /z(s) j . (D.15) Substitute (D.15) into (D.13), we have v\s) = E:\ie-^c(Xn,Yn)\ The discrete-time version of this result can be found in Chapter 5 of [46]. For stationary deterministic policy 5 : v\s) = c[s,8(s)] + E ^ W X ^ = c[s, b(s)] + X i f y 5 ( y ) P [ S ' \ S' 5 ( 5 ) 1 G [ d t \ S' 5 ( 5 ) ] f D Appendix D. Semi-Markov Decision Processes 137 L e m m a D . l : For each state (/, j, Jc) e S, the expected total cost v(i, j, k) is a nondecreas-ing function in the number of links k. Proof: The proof of this lemma is by induction. We must show v ( , ; ^ ) - v ( , - , ; , « : + 1 ) < 0 . R e c a 1 1 / 2 = J j V 1 " G[dt) .For K <k< L: N K-l v(i,j,k) = c(i,j,k,PO) + £ y£l2Hl,i,n)p(n\i,D)q(l\i). 1=1 n=l From (3.10) and (3.11), it is clear that c(i, j, k, a) < c(i, j,k+l,a) for all k. Hence, N K-1 v(i,j,k) < c(i,j,k+l,PO) + ' £ JjI2v(l,i,n)p(n\i,D)q(l\i) 1=1 n=\ = v(i,j,k+ 1). Thus, v( i , j, k) < v( i , j, k + 1) for K < k < L. Since (K - 1 + m) A (K - 1) = K- 1, for state (i,j,K): v{i,j,K-\) r N M = min \c{i,j,K-\,NPO) + X X *2v(l> h K- 1 + m)p(m\i, j)q(l\i), [ 1= 1 m= 1 N M K-l c(i,j,K-\,PO) + £ £ JjI2v{l,i,n)p(n\i,D)p(m\i,j)q(l\i) 1=1 m = l n = l N K-l <c{i,j,K-\,PO) + £ ^I2v(l,i,n)p(n\i,D)q(l\i) 1=1 n=l N K-l <c(i,j,K,PO) + J JJI2v(l,i,n)p(n\i,D)q(l\i) 1= 1 n= 1 <v(i,j,K). F o r j and 1 < k < K , assume v(i, j, k + 1) < v(i, j, k + 2) < ... < v(i, j, L). We need Appendix D. Semi-Markov Decision Processes 138 to show v(/, j, k) - v(i, j, k + 1) < 0 . From (3.16), r N M v(i,j,k) = min \c(i,j,k,NPO) + X X / 2 V ( / ' ^ ^ + m)/?(m|/, <- l = l m = l c{i,j,k,PO)+YJ X X I2v(l,i,n)p(n\i,D)p(m\i,j)q(l\i)l I = 1 ;n = 1 n = 1 J Let a* denote the optimal action of state (i, j, k + 1) . If a* = PO, v(i, j, k) N M {k + m) A ( # - 1 ) < c(i,j,k,PO)+ X X / 2 v ( / , i , » ) p ( n | i , P ) p ( m | i , j ) g ( i | 0 / = 1 m = 1 n = 1 JV M (fc+1+m) A ( A T - 1 ) < c ( « , y , t + l , P O ) + X X X I2v(l,i,n)p(n\i,D)p(m\i,j)q(l\i) 1= 1 m = 1 n = 1 = v(i,j,k+ 1). On the other hand, i f a* = NPO, A/ v(i,j,k) < c(i,j,k,NPO) + X X 7 2 V ( Z > ' » * + m)P(m\i> J)<l(lV) 1= 1 m = 1 N M . < c(i,j,k+l,NPO) + X X 7 2 v ( * ' '"'^ + 1 + m)p(m|/, 7)^ r(/|0 /= 1 m= 1 = v(i,j,k+ 1). To complete the proof, we need to show v(j, j, k) - v(j, j, k + 1) < 0 for 1 < k < K. From (3.15), N v(j,j,k) = c(j,j,k,NPO) + ^I2v(l,j,k)q(l\j) 1=1 N < c(j,j,k+\,NPO) + J^I2v(l,j,k+\)q(l\j) /= l < v(j,j,k+l). Appendix D. Semi-Markov Decision Processes 139 Thus, by the principle of induction, for each state (/, j, k) e S, the expected total cost v(i, j, k) is a nondecreasing function in k. • The following proposition states the conditions under which the optimal policy has a threshold structure. * Proposit ion D.2: Given state (/, j, k) e S, the optimal policy 5 has a control limit (or threshold) structure: [NPO, \<k<k*, 8 (i,j,k) = \ (D.16) [ PO, k*<k<L when IlAf(k + m)-^iAhPO(k + m-n)p(n\i,D)>0 for all m such that p(m\i,j)*Q n and k*<k<K. Proof: Let M N M r(i,j,k) = X Iif(k + m)p(m\i,j)+ X ]T I2v(l,i,k + m)p{m\i, j)q(l\i) m = 1 / = 1 m = 1 M (jfc + m) A ( # - 1) - CPO ~ X X {r t P 0 (fc + m - n ) + / I / ( n ) } / 7 ( n | / , D ) p ( m | i , ;') m = 1 n = 1 M (fc + /n) A ( J T - 1 ) " X X X / 2 v ( / , /, n)p(n\i, D)p(m\i, j)q{l\i). /= 1 m = 1 „ = 1 Thus, the action PO is chosen i f r(i,j,k)>0 and the action NPO is chosen i f r(i, j, k)<0. Let £ be the smallest k such r(i, j,k)>0. For convenience, let A r ( / , 7, k) = r(i, j,k+ 1) - r(«', 7, A:). Appendix D. Semi-Markov Decision Processes 140 M N M Ar(i,j,k) = X l\&f(k + m)p(m\i, j) + X X 7 2 A v ( ' ' *» ^ + w ) p ( m | i , y ' )?( / |0 m = 1 / = i « = i ( D 1 7 ) M (ik + m ) A ( ^ - l ) ~X X Ahp0(k + m-n)p(n\i,D)p(m\i, j). m = 1 n = 1 Since v(i,j,k) is a nondecreasing function in Av(7, /, + m) > 0 . Thus, Ar(i, j, k)>0 when (£ + m) A ( A : - 1) IxAf{k->i-m) - X Ahp0(k + m-n) p(n\i, D) > 0 n = l for all m such that p(m| / , /) ^ 0 . Now for some assume Ar(i, j, k), Ar(i, j,k+ 1), ..., Ar(i,j,k-l)>O.Then N M M Ar(i,j,k)= X X hAv(l> i, k + m)p(m\i, j)q(l\i) + X 7 l Af(k + m)p{m\i, j) l= \ m=\ m=\ M (k + m)A(K-\) - X X Afcp0(fc + m-n)p(rt|i, D)p(m\i, j). m = 1 n = 1 Since v(i,j,k) is a nondecreasing function in £ , A v ( / , /, k + m) > 0 . Thus, Ar(i, j, k)>0 when (k + m)A(K-\) IxAf{k + m) - X Ahpo(k + m-n)p(n\i,D) > 0 n = 1 for all m such that p(ra|z, j)^0. Thus, by induction, the optimal policy has the control limit structure when /,Af(k + m) - ^Ahpo(k + m-n)p(n\i, D)>0 for all m such that n p(m\i, j)*0 and k* <k<K. • Glossary of Acronyms A B R Available Bi t Rate A C T S Advanced Communications Technologies & Services A T M Asynchronous Transfer Mode C B R Constant Bi t Rate G S M Global System for Mobi le Communication E T S I European Telecommunications Standards Institute ID Identifier IMT-2000 International Mobile Telecommunications 2000 IP Internet Protocol I T U International Telecommunication Union L A Location Area P C S Personal Communication Services P N N I Private Network-to-Network Interface QoS Quality of Service U M T S Universal Mobi le Telecommunications System V B R Variable Bi t Rate 141 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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

Comment

Related Items