Mobility Enhanced Smart Antenna Adaptive Sectoring for Uplink Capacity Maximization in C D M A Cellular Network by Alex Wang B. A . Sc., University of British Columbia, 2003 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L M E N T OF T H E R E Q U I R E M E N T S F O R T H E D E G R E E OF M A S T E R OF A P P L I E D SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES (Electrical and Computer Engineering) T H E U N I V E R S I T Y OF BRITISH C O L U M B I A August ^2005 © Alex Wang, 2005 11 Abstract In this thesis, adaptive sectoring of a C D M A cellular network is investigated, and the aim is to maximize the uplink capacity by utilizing the mobiles' spatial information. One important feature of the algorithm developed is that it does not depend on tracking in-dividual mobile, but rather on the statistics of mobiles. The distribution of mobiles is modeled as a spatial Poisson process, whose rate function quantizes the mobile concen-tration and is inferred with a Bayesian estimator based on the statistics of network traffic. In addition, the time dynamics of the rate function is assumed to evolve according to the mobiles' mobility pattern and it is formulated using the Influence model. With the knowl-edge of the mobiles' spatial distribution, the interference and thus the outage probability of different sector partitions of a cell can be computed. The adaptive sectoring problem is formulated as a shortest path problem, where each path corresponds to a particular sector partition, and the partition is weighted by its outage probability. In simulation examples, a hot spot scenario is simulated with the adaptive sectoring mechanism, and it is observed that load balancing between sectors is achieved and which greatly reduces the effect of hot spot. iii Contents A b s t r a c t • • • n T a b l e o f C o n t e n t s i i i L i s t o f F i g u r e s vi C h a p t e r 1 I n t r o d u c t i o n 1 1.1 Main Contributions 2 1.2 Outline of the Thesis 4 C h a p t e r 2 B a c k g r o u n d a n d L i t e r a t u r e S u r v e y 5 2.1 Sectorization 5 2.1.1 Fixed Sectorization 6 2.1.2 Smart Antenna System 8 2.1.3 Adaptive Sectorization 11 2.2 The Influence Model 14 2.3 Spatial Poisson Process and Mobility 16 2.3.1 Spatial Poisson Process 18 Contents iv 2.3.2 Mobility Pattern 20 Chapter 3 Adaptive Sectoring 23 3.1 Model Definitions and Formulation of Adaptive Sectoring Problem . . . . 23 3.1.1 Formulation of Adaptive Sectoring Problem .27 3.1.2 Mobility-Enhanced Traffic Model 31 3.1.3 C D M A Network Assumptions and Outage Probability Calculation 35 3.2 Adaptive Sectoring Algorithm 39 3.2.1 Overview of the Adaptive Sectoring Algorithm in Pseudocode . . 40 3.2.2 M A P Estimator of Spatial Poisson's Rate Function 40 3.2.3 Outage Probability Evaluation for Adaptive Sectoring 42 3.2.4 Dijkstra's Algorithm 46 3.3 Simulation Results 47 3.3.1 Simulation of Spatial Poisson Estimation 47 3.3.2 Simulation of Adaptive Sectorization 51 Chapter 4 Conclusion and Future Work 54 4.1 Conclusion 54 4.2 Limitations 55 4.3 Future Work 55 Bibliography 57 Contents v Appendix A Derivation of MAP Estimator 64 vi List of Figures 2.1 Conceptual scheme of a smart antenna system. Each beam i is shaped by its weight vector, w1 9 2.2 The two classifications of smart antenna system 10 2.3 The antenna radiation pattern of a possible adaptive sectoring implemen-tation 13 2.4 Graphical representation of the Influence model. Each node is a finite state Markov chain, and the interactions between the nodes are represented by the edges connecting them. Each node may have different state space. . 15 2.5 The graphical representation of the Influence model, (a) assumes all states are observed, and (b) models the case where the states are indirectly ob-served through Nlk 17 3.1 Four major components of the adaptive sectoring algorithm 26 3.2 Graph-theoretic representation of a cell 27 List of Figures vii 3.3 Acyclic network generated from the string illustrated in Fig. 3.2(b). The network nodes that lie in between the origin (0, 0) and the destination (3,6) follow the rule {(g, i) : 1 < g < N - l,g < i < M - N + g} where N = 3 and M — 6. Edge is placed from the node (g, i) to (h,j) if h — g +1 and j > i, and no edges otherwise 30 3.4 Computation of the outage probability for a particular sector configura-tion. The diamonds shown in the figure is the soft handoff set, where the mobile located in the diamond is in soft handoff with the 2 base stations at the diamond's vertices, and power controlled by the, one with smaller pathloss. In this thesis, soft handoff of two base stations is assumed. . . . 37 3.5 The real time output of the M A P estimators of the traffic in two subareas of a hypothetical network are plotted for four 60-minute periods. The realizations of the intensity functions in subareas are generated using the Influence model, and (3.11) is applied to follow. The solid line is the simulated realization, and the dotted line is the M A P estimator value. . 49 3.6 The two plots illustrate the real time tracking of the a posteriori proba-bility mass function of the two subareas in Fig. 3.5 for the first 60-minute period. (3.9) is applied to update the a posteriori probability mass func-tion as traffic data is accumulated. It is evident from the figure that the convergence speed in tracking is directly proportional to the magnitude of the rate function 50 List of Figures 1 viii 3.7 Outage probability of sector configuration consisting of 1 to 4 subareas under constant spatial Poisson rate 52 3.8 Comparison of system performance with fixed and dynamic sectoring un-der hot spot condition. It can be observed that dynamic sectoring balances the traffic and keep the outage probabilities of the three sectors under 1%, where the loaded sector in fixed sectoring has approximately 9% outage probability 53 A.1 The figure illustrates the network model relevant to the development of the M A P estimator, and the corresponding graphical representation. The subarea of interest is labeled as Xl, and its dependency on its neighboring subareas are represented as a Bayes net in (a) and as a factor graph in (b). 65 1 Chapter 1 Introduction In wireless cellular networks, C D M A is a promising technology to offer high quality and robust voice/data services. Its R A K E receiver design and soft handoff greatly increase the robustness against multipath and fast fading environment. However, the ever increasing demand for the wireless services is continuously challenging the capacity limit of C D M A networks. In this thesis, the application of adaptive sectorization to increase the network capacity is studied. It is well known that C D M A systems are interference limited, and sectoring has been an effective mean of increasing the network capacity by introducing spatial domain orthogonalization to the system. The conventional method applied in, for example, G S M and IS-95 employs 120° or 60° sectoring to achieve better reuse of network resources. However, one major drawback of this scheme is its inflexibility when dealing with non-stationary and non-uniform mobile distribution. For example, hot spots can cause outage in a sector while other sectors have light traffic. In this thesis, we extend the conventional sectorization by allowing base stations to observe the network traffic and adaptively sectorize the cell accordingly. The dynamic sectorization is achieved by the deployment of smart antenna system at the base station. Chapter 1. Introduction 2 While smart antenna is often associated with adaptive beam forming, our approach is fundamentally different. Even though both approaches utilize the spatial domain, while beam forming directs dedicated beam to each mobile, sectorization spans the cell with few main beams with each beam corresponds to a sector. The major difference between adaptive and conventional sectoring is the system's responsiveness to changes in mobile distribution. In [41], movement of people are observed to follow certain patterns. However, mobility is not observable, and it can only be indirectly observed through the network traffic. In this thesis, a mobility-enhanced traffic model is developed to capture the fluctuation of the mobile distribution over period of a day from the network traffic observed, and based on which, the sectoring problem is solved to maximize the uplink capacity. 1.1 M a i n Contributions The main scheme of this thesis is to enable the C D M A networks to re-configure its sectorization in response to fluctuations in mobiles' spatial distribution. The two basic problems are: 1. The formulation of the adaptive sectorization as an optimization problem. 2. The real time estimation of mobiles' spatial distribution. In this thesis, the first problem is solved by mapping the adaptive sectoring problem to a shortest path problem, and which can then be readily optimized by the application of Chapter 1. Introduction 3 Dijkstra's algorithm. In order to estimate the mobile distribution, a statistical model is developed relating the mobile concentration and the network traffic such as the new call requests; the establishment of the statistical relation provides an important feedback link on evaluating the sectoring decision. Based on the statistical model, a Bayesian estimator is derived to track the mobiles' spatial distribution in real time. The main contributions of the thesis are summarized below: 1. A mobility-enhanced traffic model is developed. Mobile's distribution is modeled as a spatial Poisson process with time-varying rate function. The rate functions of different locations are assumed to evolve according to the mobiles' aggregate mobil-ity pattern and which is formulated with the Influence model [3]. If the dynamics is formulated in ordinary Markov chain, the curse of dimensionality greatly limits the applicability of the model. 2 . Recursive M A P estimator of the spatial Poisson's rate function given the network traffic. It provides real time tracking of the mobile distribution. 3. Formulation of the adaptive sectoring problem as a shortest path problem for chang-ing mobile distribution. The method was first applied in [34] to sectorize cells in wireless local loop, and it is adapted to work with the developed model. 4. Numerical studies of the adaptive sectoring algorithm. Chapter 1. Introduction 4 1.2 Outline of the Thesis In Chapter 2, the background information is provided. Sec. 2.1 discusses reasons for the inefficient use of network resources in systems with fixed sectorization, and few possible remedies. The status of these remedies are described, and which provides the motivation for the development of the adaptive sectorization. Sec. 2.2 provides an overview of a statistical model, called the Influence model, used in the thesis to model the mobiles' mobility pattern; the model is introduced in the Chalee Asavathiratham's PhD thesis [3] and it is a generative model describing the interactions of many Markov chains. Sec. 2.3 surveys the application of the spatial Poisson process in modeling the mobile distribution and also some common approaches in which the mobility pattern is modeled. Chapter 3 is the main body of the thesis where the adaptive sectoring algorithm is developed. Sec. 3.1 provides the mathematical formulation of the problem, and the basic assumptions; the optimization problem of the adaptive sectoring problem is illustrated and the related models such as the channel model and the signal model are discussed in this section. Based on the optimization problem, the adaptive sectoring algorithm is developed in Sec. 3.2, and the simulation results are presented in Sec. 3.3. Chapter 4 concludes the thesis, and also lists some limitations of the work and possible directions for future work. Appendix A derives a M A P estimator essential to the adaptive sectoring algorithm developed in Chapter 3. 5 Chapter 2 Background and Literature Survey 2.1 Sectorization In C D M A systems, because mobiles share frequency spectrum and time slots, interference reduction has direct impact on the system capacity and quality of service. In recent years, the area that has received a great attention in this aspect is the exploitation of spatial dimension. The idea is to spatially separate mobiles and allow the network resources to be reused on individual basis; by contrast, the conventional method reuses resources on cell or sector basis. Among the spatial selective techniques, smart antenna is a promising technology and it is envisioned to be a core component in future generation of mobile networks [42, 32]. However, even though intensive research has gone into this field, many challenges such as cost and system complexity still make the adoption of smart antenna technology in mobile cellular networks difficult. In this thesis, instead of focusing on individual adaptation with smart antenna directly, smart antenna is applied to enhance the conventional networks. The main topic of the thesis is to make fixed cell sectorization adaptive with the power of smart antenna, and keeps the system complexity to the minimum. In this section, the background material on sectorization and smart Chapter 2. Background and Literature Survey 6 antenna is provided to motivate the need for an adaptive sectorization system. 2.1.1 Fixed Sectorization In cellular radio system, the classical approach in utilizing spatial dimension is cell sector-ization with, directional antennas. [9] illustrates how signal-to-inference ratio and cluster size can be improved with sectorization to handle higher traffic densities. The sectoriza-tion gain is even more visible with C D M A technology because of two points: 1) Handoff mechanism between sectors is greatly facilitated with soft handoff. (Assuming sharp an-tenna cut off and small overlapping soft handoff area.) 2) The frequency reuse factor in C D M A is 1 and thus there is no loss in trunking efficiency. In principle, assuming ideal sector antenna pattern, the sectorized system's capacity is the number of sectors multiplies the original system's capacity. In practice, the typical sectorization gain is often assumed to be 2.5 (4 dB) for a 3 sector cell to take unideal antenna pattern and other channel effects into account [31]. In most cases, unfortunately, the sectorization gain is not fully utilized; the mobiles are not uniformly distributed in the network to take full advantage of the sectorized system. The problem is aggravated when the cell dimension is in micro-cell or pico-cell range. [40] describes six factors contributing to the traffic nonuniformity, and which are listed in Table 2.1. Factor 1 is the variation of the number of active mobiles in a short time scale due to activation/termination of calls and hand-off; it is often modeled as a Poisson process with constant average traffic. Factor 2 represents the long term variation Chapter 2. Background and Literature Survey 7 Time variation: 1) Short term (Poisson with constant mean) 2) Long term (Traffic variation over the course of a day) Geographical variation: 3) Steady and predictable (Traffic in shopping malls or railway stations) 4) Transient (Burst of data during a local traffic congestion) Cell shape variation: 5) Nonuniform placement of base stations 6) Nonuniform propagation loss Table 2.1: Six factors contributing to the nonuniformity of traffic in a cellular network. of the average traffic, and an example is the day-night variation of traffic in downtown business districts. Factor 3 refers to geographical traffic variation with predictable pattern (Peak data rates in train stations) and factor 4 considers the transient geographical traffic (Sudden burst of service requests during a local traffic congestion). Factor 5 and 6 are related to nonuniformity in system capacity supplied by the network due to irregular placement of base stations and random propagation environment respectively. (Hexagonal cellular network model and log-normal shadowing propagation losses are assumed in this thesis, and thus factor 5 and 6 are not modeled.) Because of the nonuniformity, full system capacity is not utilized [30, 47]; system needs to estimate and adapt to the nonuniformity in order to achieve more efficient use of the system resources. In recent years, smart antenna technology has received great Chapter 2. Background and Literature Survey 8 attention in its ability to track and exploit this spatial information. A brief overview of the smart antenna technology is given in the next subsection. 2.1.2 Smart Antenna System In general, smart antenna systems contain two main components: an antenna array and a digital signal processing unit. The conceptual scheme of a smart antenna system is illustrated in Fig. 2.1. The antenna array consists of many antenna elements, which usually are omnidirectional antenna, and the elements are arranged in certain geometry patterns. The common arrays place the elements along a straight line (linear array) or on a circle (circular array). The digital signal processing unit, according to certain control strategies, could alter each antenna element's gain and phase, and as a result changes the radiation pattern of the antenna. References on smart antenna may be found in [28, 22, 21]. The vector of gains and phases applied to produce a beam i is often called a weight vector and denoted as w% = [wl0,..., wlM_^\, where M is the number of antenna elements and each component wlm is a complex number called weighting element. The smart antenna systems can be classified into two types according to its weight vector: adaptive array system and switched beam system. Adaptive Array System A n adaptive array system is a smart antenna system that adaptively adjust its weight vector according to mobile movement. The radiation pattern of the antenna array can be adjusted in real time adapting to the R F signal environment. The signal of interest (SOI) and the signal not of interest (SNOI) are estimated based on Chapter 2. Background and Literature Survey 9 Antenna Array Input parameters Figure 2.1: Conceptual scheme of a smart antenna system. Each beam i is shaped by its weight vector, wl. the signals' time delays among the antenna elements, and antenna pattern is dynamically adjusted to follow the direction of SOIs. Fig. 2.2(a) illustrates a possible radiation pattern where two desired users are followed and an interferer is rejected. Swi tched-Beam System A switched-beam system is a smart antenna system with a set of pre-calculated and fixed weight vector, and thus only a set of fixed antenna patterns can be generated; [29] uses a Butler matrix to generate the switch beams to cover a cell. As the mobile moves through the cell, the system detects the signal strength, and chooses, from the predefined antenna patterns, the one with the best signal. The potential of the smart antenna system seems enormous. However, there are certain practical challenges that are still not yet addressed. [25] details many concerns regarding the deployment of the adaptive array system. 1. The requirement on channel link parameters in forward beam-forming. (In T D D , parameters may be obtained from the reverse link. In F D D , autocalibration tech-Chapter 2. Background and Literature Survey 10 SOI SOI SNOI (a) Adaptive Array System (b) Switched-Beam System Figure 2.2: The two classifications of smart antenna system, niques is needed to adjust the parameters from the reverse link.) 2. The degradation of forward link due to the multipath radio environment. 3. The numerical complexity of signal processing in beam-forming and spatial filtering. 4. Standardization still incomplete. 5. High deployment cost and difficulties in integrating with existing networks. Furthermore, the switched-beam system also has several limitations [28]. 1. The system is not able to provide protection from multipath components which arrive in the angle near that of the desired mobile; especially when the mobile is not located at the main lobe of the beam pattern but slightly off. 2. The system typically cannot take advantage of path diversity by combining coherent multipath components. Chapter 2. Background and Literature Survey 11 Considering the limitations listed above, the application of smart antenna to indi-vidual mobiles in mobile cellular network still seems several years away. However, the adaptive power of the smart antenna may be applied to a less complex environment -adaptive sectorization. Using the adaptive beam pattern, the sector coverage may be altered according to the traffic nonuniformity, and fully utilize the network resources supplied by the sectorized system. 2.1.3 Adaptive Sectorization In this thesis, the adaptive sectoring algorithm developed is independent of the underlying smart antenna technology. However, in order to demonstrate the practicality of the system, the application of the switched-beam system is discussed because of its superiority in mobile cellular networks. Comparison of the two smart antenna technologies are discussed in [10, 36], and it is observed that in high density areas where both angle of arrival spread and SINR are relatively small, as compared to L A N and indoor systems, the adaptive array system performs less satisfactory. The switched beam system provides equal or better performance with a fraction of the complexity and the expense. In addition, there are certain advantages in implementing the adaptive sectoring with the switched beam system: 1) The system integrates easily with the existing fixed sector-ized system and it is upgradable to full switch beam system as needs arise or technologies mature. The adaptive sectoring can be implemented by dynamic combination of switch beams and which is described in [29, 18]. In particular, [29] details the use of Butler Chapter 2. Background and Literature Survey 12 matrix and circular antenna array to equip a fixed sectorized system with the adaptive sectoring ability. 2) The system conforms to 3G standards. For example, [12] describes the support of auxiliary pilot with switched beam in CDMA2000, [28] details its appli-cation in IS-95 and [1] describes how dedicated pilot symbols in W C D M A systems can render future deployment of the system easier. As a result, the antenna architecture that support the adaptive sectoring algorithm can be considered as a migration from a fixed sectorized system to a full switched-beam smart antenna system. A possible implementation which build on top of existing fixed sectoring system is to deploy circular antenna array and a beam forming network per sector, and with each beam forming network outputs signal to the sector receiver [29]. Fig. 2.3 illustrates the antenna radiation pattern of a possible adaptive sectoring implementation; each sector is identified by its pilot signal and soft handoff is used when mobiles travel between sectors. In addition, since the location of mobiles can be identified by the beam with the strongest signal strength, the statistics of the mobiles' distribution can be collected by summing up the connection requests in the beams making up the sector. The details of the mobile distribution will be discussed in Chapter 3. The adaptive sectorization problem have been researched in many papers. This para-graph provides a literature survey of papers which looked into this problem [34, 15, 20, 2]. [34, 15] deals with the problem when mobiles' locations within the network are known and stationary, such as the case in wireless local loop. The adaptive sectoring is solved for two cases: minimizing the total transmit power of the mobiles and minimizing the Chapter 2. Background and Literature Survey 13 (Sector Pilot Tone) Figure 2.3: The antenna radiation pattern of a possible adaptive sectoring implementa-tion. total received power at the base station. [2] assumes a spatial Poisson process with the intensity function A, which is assumed known, and the probability of having k mobiles in an area A is given by the Poisson distribution P(k, A) = ^) e~XA. By fixing k and P = J2%k P(j> A), and replace A by ^ where r is the cell radius and 8 is the sector's angle span, P is the probability of having more than k users in 6. Adaptive sectoring is computed by an iterative method which reduces 9 when k is above a certain threshold. [20] continuously monitors the SINR (signal to interference and noise ratio) of all the users, and sectorize the cell to equalize the SINR in all sectors. However, in each of the above solutions, there are certain limitations. While the work in [34, 15] is designed to work for wireless local loop, it is difficult to extend it for constantly moving mobiles. In [2], the success of the algorithm depends on the knowledge of the mobile concentration. Moreover, the SINR-based sectoring in [20] may be unstable because of the shadowing Chapter 2. Background and Literature Survey 14 and fast fading in the measurement of SINR [13]. 2.2 The Influence M o d e l In this thesis, the statistical model applied to track the traffic nonuniformity is formulated as an the Influence model, which is introduced in the PhD thesis by Chalee Asavathi-ratham [3]. Briefly, the Influence model is a generative model describing the interactions between many Markov chains. In the formulation to be developed in Chapter 3, the network is divided into discrete areas, and the traffic in each discrete area is modeled as a finite state Markov chain and the traffic nonuniformity is the result of the Markov chains' interactions. In this section, the Influence model is introduced and some of its important properties emphasized. The Influence model comprises a network of interacting nodes; each node assumes a finite number of possible states at each discrete time instant, and the interactions between the nodes are represented by the edges connecting them. The graphical representation of the model is illustrated in Fig. 2.4. The state of a node at time k, Xk, is represented by an indicator vector containing a single 1 in the position corresponding to the present state, and 0 everywhere else. For example, suppose the state space of a node is {High, Low}, the indicator vector denoting the state High is s[k] = [1 0]', where the prime denotes matrix transposition. Furthermore, suppose the network contains M nodes, the next state probability of node i, given the current state of all M nodes, can be calculated Chapter 2. Background and Literature Survey 15 Figure 2.4: Graphical representation of the Influence model. Each node is a finite state Markov chain, and the interactions between the nodes are represented by the edges connecting them. Each node may have different state space. using P{Xik+i\Xl...,X?)= £ dyPiXi+M), where dij and P(Xlk+1\Xf. = Sj[k]) = Sj[fc]A,j are model parameters whose significance will be explained below, and D(i) is the set of nodes which share an edge with node i, including i itself. The simulation procedures of the Influence Model for an arbitrary node i is listed here: • Stage 1: The node i randomly selects one of its neighboring nodes or itself, i.e., selects one from the set D(i), to determine its state at the next time instant. The probability at which its neighboring nodes or itself is chosen is , and "T\ = 1. • Stage 2: Suppose the node chosen from stage 1 is node j, the present state of node j, Sj[k], fixes the probability vector of node i for time k + 1, i.e., P(Xlk+x\X3k — Sj[k]) = Sj-'A^Afi, where A,-; is a fixed row-stochastic rrij x m» matrix whose values dictate the probability distribution of Xk+1, and rrij and w i j are the number of Chapter 2. Background and Literature Survey 16 states for Xk and Xlk respectively. Note that since s'j[k] is a indicator vector, a particular row of Aji is picked for P(Xlk+1\Xk = Sj[fc]). • Stage 3: Node i's state at time k + 1, s'^k + 1], is sampled from the distribution vector P(Xk+1\Xk = Sj[k]) computed at Stage 2. Applying the simulation procedures, complex phenomena involving interactions between large number of chains could be simulated. The model parameter is a constant factor that indicates how often the node i is influenced by the node j, and P(Xlk+1\Xk) specifies how node i is influenced by j depends on j ' s current state. The time dynamics of Xlk for i = 1,2,... , M can be depicted graphically in Fig. 2.5(a), where the dependency is assumed known a priori and it is specified by D{i) defined above. Furthermore, for the adaptive sectorization to be modeled, the state of nodes can not be observed, and hidden states need to be incorporated into the Influence model. The dynamics of the Influence model with hidden states is illustrated in Fig. 2.5(b). In this thesis, parameters of the Influence model are assumed known (Some parameter estimation techniques can be found in [5, 11]), and the estimator of the state's a posteriori probability distribution given observations will be derived. 2.3 Spatial Poisson Process and Mobi l i ty In this thesis, the mobiles' spatial distribution is modeled as a doubly stochastic Poisson process. The literature survey of papers applying the spatial Poisson process is provided Chapter 2. Background and Literature Survey 17 (a) The states of the Influence model's dynamics (b) The states of the Influence model are hidden, are fully observed. Figure 2.5: The graphical representation of the Influence model, (a) assumes all states are observed, and (b) models the case where the states are indirectly observed through Nxk. Chapter 2. Background and Literature Survey 18 in Sec. 2.3.1. In addition, the stochastic process that drives the doubly stochastic Poisson process is modeled after the mobiles' mobility pattern, whose overview is given in Sec. 2.3.2 2.3.1 Spatial Poisson Process In this subsection, a literature survey of the spatial Poisson process in the context of cellular networks is provided. The most often encountered version of the spatial Poisson in the literature is the homogeneous spatial Poisson process. It has been used to characterize the other-cell interference, determine the optimal soft handoff area and to dimension the communication networks. More detail is given in the next paragraph. However, homogeneous spatial Poisson is not adequate in our case because it cannot reflect the fluctuation of the mobile concentration. In order to adapt the sectorization to maximize the uplink capacity, the model needs to be flexible enough such that it can follow mobiles' mobility pattern. The most obvious extension of the homogeneous spatial Poisson process is the doubly stochastic Poisson process, and it will also be discussed in the following paragraphs. The homogeneous spatial Poisson process is defined as follows: Suppose mobiles are randomly located over a plane according to a homogeneous spatial Poisson process of rate A, the probability of having a certain number of users in some area A, N(A), is P(N(A) = k)=eXp(-X\A\)^^-. Many papers have used the homogeneous spatial Poisson to model the mobiles' spatial Chapter 2. Background and Literature Survey 19 distribution. Earlier works [39, 23] characterize the interference at the receiver from a Poisson field of interferers, and which is applied to demodulate a signal in the presence of such interference. [43] divides the network area into a grid, and represents the traffic intensity in each grid block as a spatial Poisson process with certain rate function; the rate function is estimated based on the geographical and demographical data. Furthermore, [33] relates the targeted traffic, represented by the spatial Poisson's rate function, to the soft handoff threshold, and the optimal threshold is determined as a trade off between capacity and coverage. As demonstrated in [8] and further elaborated in Chapter 3, the spatial Poisson distribution is seen to follow in a simple way from some basic assumptions. One of the limitations of the homogeneous Poisson distribution is that the mean number of mobiles in the area is fixed. However, in terms of adaptive sectoring, it is the change of mobile concentration that is of primary interest. As a result, a more sophisti-cated model is needed. Doubly stochastic Poisson process, a generalization of the homo-geneous Poisson process, is defined as follows [37]: Let {xt\t > to} be a left-continuous, vector valued stochastic process that influences the evolution of a point process whose associated counting process is {Nt]t > to}. {Nt;t > to} is a doubly stochastic Pois-son process with intensity process {Xt(xt);t > t0} if for almost every given path of the process {xt;t > to}, N is a Poisson process with intensity function Xt(xt). In other words, {Nt;t > to} is conditionally a Poisson process with intensity function Xt(xt) given {xt\t > to}. The intuitive approach in characterizing the mobile concentration is to model it as a doubly stochastic Poisson process, and has the rate function, xt in the Chapter 2. Background and Literature Survey 20 above definition, models after mobiles' mobility pattern. 2.3.2 Mobility Pattern Much research effort that has been spent in the analysis of mobility patterns is to char-acterize mobiles' movement behavior. The mobility characterization has implications on issues related to location management, radio resource allocation and handoff manage-ment; [48] studies the effect of mobility on the performance of multimedia traffic and [49] evaluates its impact on C D M A ' s capacity. As a broad classification, individual user-behavior and aggregate movement are the two major types of mobility patterns. In this subsection, a brief survey of the common approaches in modeling the mobile movement is presented. Much of the work related to individual user-behavior characterization is based on the Markovian assumption. The most common model is the random walk model, where mobiles either remain within a region or move to an adjacent region according to a transi-tion probability distribution. Under the Markovian movement assumption, [4] evaluates the cost of location update and [46] formulates the location update algorithm as a semi-Markov decision process. A commonly applied mobility model in ad-hoc networks is the random waypoint model [24]. The model breaks the entire movement of the mobile into repeating pause and motion periods. The mobile first stays at a location for a certain period of time then it moves to a new randomly chosen destination at a speed uniformly distributed between [Kna^V^^]. Many other variations exist to model the individual Chapter 2. Background and Literature Survey 21 user-behavior, however, the mobility pattern of interest in this thesis is on the aggregate movement. For interested readers, a more complete survey of mobility models can be found in [7] and references therein. In this thesis, it is the statistics of mobiles that is of interest, and as a result, the aggregate movement model better suit our needs. In general, the aggregate population movement has been well characterized using the fluid model [19] and the gravity model [6, 27]. In fluid model, traffic flow is conceptualized as the flow of fluid. One of the simplest fluid models describes the amount of traffic flowing out of a region to be proportional to the population density within the region, the average velocity, and the length of the region boundary. However, one of the limitations of this model is that it is hard to apply to situations where individual movement patterns are desired. In the gravity model, on the other hand, the mobility pattern is characterized by the concept of origin and destination trips. The portion of all trips started in a given area that will destine in another is proportional to the relative attraction and inversely proportional to the spatial separation between the two points. In its simplest form, the probability T -^ of movement between the origin i and destination j is KijPiPj, where Pi is the attraction parameter of the region i, and Kij is the parameter specific to the region pair i and j. In this thesis, the gravity model is favored in describing the aggregate movement pat-tern. As will be explained in more detail, the collection of mobiles' statistics requires the network to be divided into discrete regions, where each region is a fraction of a cell (The network model is defined in Chapter 3). Since average population density and average Chapter 2. Background and Literature Survey 22 velocity are used in the fluid model, the setup of the network model with small regions has made the fluid model inappropriate because the model is accurate only for regions containing large population. As a result, it is natural to adopt a mobility model similar to the gravity model. As will be shown in the model definition, the aggregate mobility pattern is specified in terms of conditional probability between each pair of regions in the network; the conditional probability characterizes the dependence of a region's future mobile concentration on its neighboring region's previous mobile concentration. 23 Chapter 3 Adaptive Sectoring 3.1 M o d e l Definitions and Formulation of Adaptive Sectoring Problem The adaptive sectoring of C D M A systems is formulated as a maximization problem of its uplink capacity; uplink is chosen because it is the limiting link [44, 16]. In C D M A networks, because mobiles occupy the same frequency spectrum and time allocation, interference is the major factor limiting the capacity. A widely used capacity measure is the outage probability, which is defined as the probability of interference at a base station exceeding a certain threshold value [44, 17]. As a result, the optimization problem to be developed is the minimization of outage probability in C D M A uplink with adaptive sectorization. In order to compute the outage probability at a sector, the knowledge of mobiles' whereabouts is necessary. Yet, as the density of mobiles increases, tracking the location of individual mobile is too computationally intensive, and may lead to frequent sectoring because of various individual movement patterns. As a result, the network is modeled Chapter 3. Adaptive Sectoring 24 as a hexagonal cellular network, with each cell consists of six equally spaced areas called subarea (See Fig. 3.1(a)), and with respect to which statistics of mobiles is collected. Fig. 3.1(b) illustrates the process where each base station collects statistics in its subareas and shares it among its neighboring base stations; the arrows in the figure indicate the transfer of information. The sharing of mobiles' spatial information allows, as demonstrated in later sections, the computation of the outage probability. In this thesis, discrete sectoring in terms of subareas is considered. Specifically, each sector in a cell is defined by the beam pattern of its sector-beam, whose beamwidth is multiples of a subarea's angular span (See Fig. 3.1(d)). In addition, perfect beam pattern is assumed; there is no overlap between beams and thus mutual interference is ignored and mobiles in a particular sector only see one sector-beam. As a result, the outage probability of a sector is computed according to mobile statistics in subareas covered within the range of the sector-beam's angular span (See Fig. 3.1(c)). Note that the dimension of the subarea defines the granularity of the model; the smaller the subarea, the finer the tracking of the mobile distribution and also the sectoring, but the higher the computational load on the system to perform estimation. From the above discussions, the adaptive sectoring problem consists of three compo-nents: the optimization of the sectoring problem, the estimation of mobile distribution and the computation of outage probability. In this section, the model components are established in turn. Chapter 3. Adaptive Sectoring 25 (a) The network is modeled as a hexagonal cellular network, and each cell is divided into six equally-spaced areas call subarea. The base station is located at the center of the cell and it is equipped with the smart antenna technology such that sectoring is achieved by adapting the antenna's radiation pattern to mobile's mobility. (b) Each base station is responsible for traffic estimation in each of its subareas, and also the distri-bution of the estimated values to its adjacent base stations. The value is necessary for the calculation of other-cell interference. The black dots represent the mobiles. Chapter 3. Adaptive Sectoring 26 (c) Computation of the outage probability for a particular sector configuration. The information of mobile distribution in other cells is fed to the central cell in the previous step. (d) Adaptive sectoring which minimize the total outage probability in the sectors. The sector beams are assumed to be perfect, and no mutual interference is considered. Figure 3.1: Four major components of the adaptive sectoring algorithm. Chapter 3. Adaptive Sectoring 27 vl v2 v3 v4 el e2 e3 e4 v5 • e5 v6 (a) Ring representation of a cell. In this representation, subareas are nodes, and se-tors are disjoint subsets of nodes. (b) One of the six reduced string represen-tation of a cell. The edge ee is arbitrarily chosen and removed. Figure 3.2: Graph-theoretic representation of a cell. 3.1.1 Formulation of Adaptive Sectoring Problem A natural mathematical representation of the adaptive sectoring problem is with graph partitioning; a discrete sectoring of a cell with no overlapping sector-beams is modeled as a particular partitioning of subareas. The key advantage of representing the problem as a graph partitioning problem is that, under certain conditions, the partitioning problem has a one-to-one correspondence to a shortest path problem, and which is readily solvable using Dijkstra's algorithm. (The method was first applied in [34] to sectorize wireless local loops with stationary mobiles.) In this subsection, the graph partitioning formulation of the adaptive sectoring problem, and the mapping to a shortest path problem are demonstrated. Fig. 3.2(a) illustrates the graph theoretical representation of the cellular network. A cell is modeled as a ring of nodes where each node represents a subarea. Let the Chapter 3. Adaptive Sectoring 28 graph G = (V, E) denotes the ring and the vector V = {v\, v2, • • • ,v$} denotes the nodes, the sectoring problem is equivalent to the partitioning of nodes (subareas) into subsets (sectors). Let IT — {Si,..., SN} be a partition of the set of nodes V into N subsets. 7r is considered feasible in G if for every g € {1,... ,N}, the subgraph G(Sg) induced by Sg is connected, and the weight W(Sg), which is the outage probability experienced in sector Sg, is greater than or equal to zero. For example, 3.1(d) illustrates a feasible partition with Si = [vi], S2 = [v2 v3] and 5 3 = [i>4 v5 v6], and W(S2) is the outage probability caused by mobiles in the area shaded in Fig. 3.1(c). The set of all such feasible partitions is denoted by Q,(G,N). The cost function C : Q(G,N) —> K assigns a value to each feasible partition and the cost of a particular partition ir is given by C(7r) = J2iLi W(Si). The graph partitioning problem is to find a feasible partition with the minimum cost, i.e., In general, the problem of optimally partitioning an arbitrary graph with an arbitrary cost function is a NP-hard optimization problem. However, it has been shown that the partitioning problem can be solved in polynomial time if the graph is a string and the cost function is separable. Defini t ion A function of M variables, f { x i , x 2 , i s separable if it can be expressed as a sum of M functions of a single variable; i.e., f{xi,x2,..., %) = Yliii fi{xi). Theorem 1 If the cost function is separable, the problem of optimally partitioning a string can be reduced to a shortest path problem. N C(n) = £ W(St) i=l (3.1) Chapter 3. Adaptive Sectoring 29 Proof The proof can be found in [14]. | The important observation of a ring is that it can be broken into a string if an edge is removed. In addition, with perfect sector-beam assumption, the computation of a sector's outage probability is independent of other sectors. In other words, the hypothesis of the above theorem holds and the graph partitioning formulation of the adaptive sectoring problem is equivalent to a shortest path problem. Fig. 3.2(b) illustrates the string representation where the edge e§ is arbitrarily chosen and removed. It should be noted that the removal of an edge traded problem complexity with computational complexity since six strings are generated from one ring. Suppose H is a string whose M nodes are labeled as VI,...,VM such that adjacent nodes have consecutive indices. The problem is to partition M nodes into N subsets with the minimum cost function. The graph partitioning problem is mapped to a shortest path problem by the construction of an acyclic network. Let (0,0) be the origin and (N, M) be the destination node of the acyclic network. The set of network nodes that lie in between the origin and the destination node is P = {(g,i) : I < g < N — l,g < i < M — N + g}. Edge is placed from the network node (g,i) to the network node (h,j) if h = g + 1 and j > i, and no edges otherwise. Note that a network node is different from a string node. There is a one-to-one correspondence between the feasible partitions of the string and the paths in the acyclic network. Each network node (g, i) is in P iff i is the last string node of the subset Sg in n. In other words, suppose an edge is ((h,j), (g,i)), the subset Sg contains the string nodes {fj+i,. . . ,t>i} because the last string node of S^ is j and Chapter 3. Adaptive Sectoring 30 Figure 3.3: Acyclic network generated from the string illustrated in Fig. 3.2(b). The network nodes that lie in between the origin (0,0) and the destination (3, 6) follow the rule {(g,i) : 1 < g < N -l,g <i < M - N + g} where N = 3 and M = 6. Edge is placed from the node (g,i) to (h,j) if h — g + 1 and j > i, and no edges otherwise. the last string node of Sg is i. Furthermore, the weight of each network node is zero, and the weight of each edge is the weight W of the corresponding subset. For example, let M — 6 and N = 3, which is the case of partitioning 6 subareas into 3 sectors, and choose the string representation as shown in Fig. 3.2(b), the acyclic network constructed is illustrated in Fig. 3.3. Suppose a path through the network is (0,0) —> (1,1) —> (2,3) -> (3,6), the corresponding sectors of the three edges ((0,0), (1,1)), ((1,1), (2,3)) and ((2, 3), (3,6)) are {vi},{v2,v3} and {uj, v 5 , ve} respectively. The weight assigned to each edge is the weight of the corresponding subset and it is the outage probability of the corresponding sector. As a result, according to the above formulation, the adaptive sectoring problem can be Chapter 3. Adaptive Sectoring 31 viewed as a shortest path problem with a changing weight matrix; the weight of each edge depends on the evolving statistics of mobile distribution in each subarea. In Sec. 3.1.2, a model is developed to track the statistics in each subarea, and Sec. 3.2.3 computes of the outage probability. In this subsection, the aim is to develop a model of mobile distribution which enables the base stations to track the mobile distribution by collecting its statistics. The first major problem that has to be addressed is the observability of mobility. In general, mobility is not observable, and it can only be indirectly observed through the network traffic processed at the base station. The approach taken is inspired by [8] where the mobile distribution is modeled as a spatial Poisson process and its relation to the network traffic is demonstrated with the following theorem. Theorem 2 Let n t be a Poisson process of arriving calls at a base station with constant rate of Xk from mobiles in an arbitrary subarea. Once the mobiles placed the call, they move at random around the subarea with independent trajectories. Let E be a spatial subset of the subarea such that the probability of the mobile who called at time s being in E at a subsequent time t is p(s,t). Then the number of mobiles in E at time t has a Poisson distribution with mean 3.1.2 Mobility-Enhanced Traffic Model Chapter 3. Adaptive Sectoring 32 Assuming uniform distribution for p(s, t) over the subarea, the distribution of the mobiles in the subarea is a spatial Poisson process with rate equals to that of the arriving calls. P r o o f The proof can be found in [26], (pg 49 Bartlett's Theorem). | In Theorem 2, a number of assumptions are made, and it is worthwhile going into the details. Assumpt ion 1 The arrival process at the base station is a Poisson process with constant . rate. The arrival process referred to in the Theorem is the connection requests made by mobiles in the subarea. For example, the number of times Access Channel is requested in IS-95 or CDMA2000. From the study of broadband network traffic [35], the connection request is generally modeled as an inhomogeneous Poisson process. The additional assumption is that the rate function, Xk, in a subarea is a jump process with finite states, and jumps occur on a hourly basis; during each hour, the rate function is taken as a simple random variable and takes on a single value. Assumpt ion 2 The uniform probability distribution over the subarea. The assumption is made to simplify the discussion, and it seems reasonable if the subarea is small enough such that highly attractive locations such as shopping malls does not appear like a clustered point in the subarea. However, other distributions may be applied but they are not studied in this thesis. The advantages of relating the network traffic to a spatial Poisson process are 1) The time dynamics of the connection requests in each subarea can be described by the Chapter 3. Adaptive Sectoring 33 mobiles' mobility pattern. 2) The rate function of the spatial Poisson process can be estimated in real time from the statistics of connection requests. M o d e l Def ini t ion Let i = 1,2, ...,M denotes subareas, where M is the number of subareas in the network, and k = 0 , 1 , . . . , 23 denotes hours of a day, Uk is the spatial Poisson process with constant rate Xk in subarea i during the time interval [k,k + 1). Xk = [Xk, X%,..., Xjf \ is a discrete time discrete state stochastic process, and, with Theorem 2, its state controls the rate of connection arrivals observed in each subarea. The evolution of Xk is pictorially represented as a dynamic Bayes nets (DBN) in Fig. 2.5(b). If there is only one subarea, Xk is a hidden Markov chain observed through a Poisson process. For M subareas, the state of Xlk for all subarea i is modeled with the Influence model [3]. Suppose the subarea of interest is i, let D(i) denotes the dependency of i, the transition probability for Xk is P(Xl+1\Xl... ,XJf) = £ d^PiXl^Xl), (3.2) jeD(i) where D(i) refers to i itself and its adjacent subareas, and and P(Xk+1\Xk) are model parameters which are assumed known. (Some parameter estimation techniques can be found in [5, 11].) Furthermore, the initial probability distribution P(Xk_0) is also assumed known for all i. Justification of the model is presented next. Aggregate M o b i l i t y M o d e l i n g w i t h Influence M o d e l The basic assumption un-derlying the model is that daily pattern of a subarea's traffic is the result of mobiles traveling in and out of the subarea. The aggregate movement of the mobiles is ex-pressed as a conditional probability of Xk on Xk-i- The most straightforward model is Chapter 3. Adaptive Sectoring 34 P(Xk+1,..., Xjf+l\Xk,..., Xjf), however, such complete specification is not desirable be-cause not only does the model dimension grow exponentially as the number of subareas, the interpretation of the model parameters is difficult. In Asavathiratham's PhD thesis [3], the Influence Model is introduced to describe in-teractions between many Markov chains. The model simplifies P(Xk+1,..., XJf+l\Xk,..., Xf) to M P(Xlk+1\Xl..., Xjf), and for each i, P{X{+1\Xlk,Xjf) is a convex com-binations of P(Xk+1\Xk) as shown in (3.2). (Note that (3.2) degenerates to a standard Markov chain if dij = 1 for i = j, and 0 otherwise.) The parameter d^ is referred to as "influences" by Asavathiratham, and they are constant factors indicating how often subarea i is influenced by subarea j, and the effect of the influence is in the specification of the conditional probability P(Xk+1\Xk). In terms of aggregate mobility, the implicit assumption of (3.2) is that during [k, k+1), the time interval is short enough such that mobiles in one subarea can only stay in the same subarea or travel to the adjacent ones. In addition, may be interpreted as relative attraction between subarea i and j such that high traffic flux between i and j can be expressed by high d^. An example of P(Xk+1\Xk) is that the probability of a food court i having high traffic at time k + 1 = 12 given the neighboring business district j had high traffic at time k = 11 might be 0.8. In other words, given there was high concentration of people working nearby, the probability of them coming to the food court subarea for lunch and induce high traffic is 80%. In addition to the mobility interpretation, the model complexity of the Influence model is another advantage. Suppose there are M subareas Chapter 3. Adaptive Sectoring 35 and each subarea has Q states, the total number of model parameters are MQ2 + M2, which is greatly reduced from Q2M as in the case of complete specification. 3.1.3 C D M A Network Assumptions and Outage Probability Calculation In this subsection, the C D M A network model and the propagation model are introduced, and the expression of the outage probability is derived. For adaptive sectoring, because it is the performance analysis of the network over long time scales that is of primary interest, many important physical layer effects, such as the signature sequence structure of the C D M A system and the fast fading losses, are not included. The performance of the adaptive sectoring is studied with perfect power control, soft handoff and log-normal shadowing. P r o p a g a t i o n M o d e l a n d Interference C a l c u l a t i o n The propagation loss in general is modeled as the product of 7th power of distance and a log-normal shadowing component [44]. Let Bn denotes the location of base station n and suppose an arbitrary mobile at location z, the following propagation loss model is assumed: rz[Bn] = d[z, 5„]no«/10 = d[z, s„]no a f e / 1 0 )io 6^- B"/ 1 0), (3.3) where d[z, Bn] is the distance between z and Bn, and 7 is the path loss exponent. The shadowing £ = a£ 2 + 6£z,s n is the superposition of two components: £ z is the shadowing in the near field of the mobile at point z, and £z,Bn is the shadowing in the wireless link Chapter 3. Adaptive Sectoring 36 between the mobile at z and the base station Bn. £ 2 and £ 2 ,a n are independent Gaus-sian random variables with the following properties: E(£ 2 ) = E(£ 2 ,B N ) = 0, Var(£ 2) = V a r ( 6 , B „ ) = cr2 and E(£ 2 £ 2 ,B„) = 0 for all n, and E(£ 2 ,B N£ 2 , .BM) = 0 for all n ^ m. In ad-dition, £ 2 and £ 2 j s n are assumed to have equal standard deviation, and thus a 2 = b2 = 1/2 is assumed. With the propagation model in place, the base station that does the power control and the set of base stations that participate in soft handoff can be defined. Let B = [B\ B2 • • • BN] denotes the TV base stations in the network, the path loss of a mobile at location z to each of the base station is then TZ[B] — [Tz[Bi] FJ.B2] • • • TZ[BN]]. The base station that power controls the mobile at z is defined as Cz = arg min^ Tz [Bi]. As regard to soft handoff, assume Ns base stations are involved, the soft handoff set, £ z , is defined with respect to location z as the set of A^s base stations with the least path loss values in T 2 [B]. Ns is taken to be 2 in the rest of the thesis. Furthermore, the received power from the mobile at z is power controlled to have magnitude of 1 at the base station Cz. As a result, a mobile at z and power controlled by Cz has to transmit with power T 2 [Cz], and the interference it induces on base station Bn is equal to Interference C a l c u l a t i o n R e v i s i t e d w i t h S p a t i a l P o i s s o n In Sec. 3.1.2, Theorem 2 establishes that the mobile distribution in the network is spatial Poisson. The problem to be addressed is to revisit the. interference calculation and take spatial Poisson into (3.4) Chapter 3. Adaptive Sectoring 37 Figure 3.4: Computation of the outage probability for a particular sector configuration. The diamonds shown in the figure is the soft handoff set, where the mobile located in the diamond is in soft handoff with the 2 base stations at the diamond's vertices, and power controlled by the one with smaller pathloss. In this thesis, soft handoff of two base stations is assumed. account. Fig. 3.4 shows the network model conceptually. Each point z € is assigned a soft handoff set £ 2 ) which is represented as a diamond-shaped area; for any mobile within the diamond, the mobile is in soft handoff with the two base stations at the vertices, and power controlled by the one with smaller pathloss. Suppose the interference at B\ is of interest, which is the central base station in Fig. 3.4. Let S be the set of all subareas in the shaded area A, and II". the subarea i's spatial Poisson process with rate Xlk, the entire set of mobiles that is loading the sector is denoted Chapter 3. Adaptive Sectoring 38 as n f c = Uiesrife- With (3.4), the total interference at the sector of B\ is i[Bi] = £ r . p j / r . t B j . (3.5) According to [8], (3.5) can be classified into two components by identifying the two point patterns in life; any point in TLk can either belong to a point pattern corresponding to Cz — B\ (Jik[Bi\) or the one corresponding to Cz ^ B\ (ITfc[-Bi]). The classification is achieved by the Poisson Marking theorem. According to the network definitions given above, the probability that a mobile at z is power controlled by Bi is P(CZ = Bi) = P(r z[5x] < r2[/i„]) and the probability of not power controlled by Bx is P(CZ ^ Bx) = P(Tz[Bi] > Tz[Bn\) for all n e (z and n ^ 1. Furthermore, let z g and define the mean measure of life by the two points patterns of mobiles in IT/, are then classified as: In-cell mobile is the point pattern IIfc[5i] with mean measure m[B\[(dz) defined by d(m[B!])(z) = P(CZ = Bl)dm(z). Other-cell mobile is the point pattern IIA;[5I] = I L ; — IL;[5i] with mean measure mlB^dz) defined by d(m[Bi])(z) = P[CZ ^ Bx)dm{z) = (1 - P(CZ = Bx))dm(z). As a result, let and I°[Bi] denote the in-cell and other-cell interference at B\ respectively. The total interference at B\ expressed in (3.5) is the summation of /'[.Bi] 0; otherwise. 1, if dz is in subarea i (3.6) Chapter 3. Adaptive Sectoring 39 and J°[Bi]: I[B1] = P[B1] + I°[B1}= E !+ E ^[C^/T^]. (3.7) The outage probability of the sector is then (3.8) \z€nfc[Bi] zenfc[Bi] where a is the threshold value for the total interference. The evaluation of (3.8) is presented in Sec. 3.2.3. In this subsection, the outage probability expression is for a particular sector partition. However, it should be clear that the expression is the same for different partitions except the spatial Poisson process Hfc. 3.2 Adaptive Sectoring Algor i thm From the previous section, the adaptive sectoring problem is shown to be equivalent to finding the shortest path in an acyclic network whose weight matrix is constantly changing; the weight is a function of a spatial Poisson process which evolves on a hourly basis. As a result, the rate function estimation of the spatial Poisson process and the construction of the acyclic network's weight matrix with (3.8) are integral parts of the adaptive sectoring algorithm. Once the weight matrix is constructed, Dijkstra's algorithm can be used to determine the optimal sector partition. In this section, the components of the adaptive sectoring algorithm is described. Sec. 3.2.1 provides an overview of the algorithm, Sec. 3.2.2 describes the M A P estimation of the spatial Poisson's rate function, Chapter 3. Adaptive Sectoring 40 Sec. 3.2.3 computes the outage probability and Sec. 3.2.4 brief discusses the Dijkstra's algorithm. 3.2.1 Overview of the Adaptive Sectoring Algorithm in Pseudocode Recall in Sec. 3.1.2, the time t of a day is divided into hourly intervals k = { 0 , 1 , . . . , 23}. Let M be the number of subareas and N the number of sectors in a cell, the pseudocode of the adaptive sectoring algorithm is provided in Algorithm 1 (See page 41). 3.2.2 M A P Estimator of Spatial Poisson's Rate Function In this subsection, the M A P (maximum a posteriori) estimator of Xk given the connection requests statistics is introduced, where the derivation is presented in Appendix A. Since the estimators for all subareas are equivalent, and for notational convenience, the subarea to be estimated is labeled as Xl, and the neighbors of Xl, labeled as Xk, Xk and Xk, are shown in Fig. A . 1(a). M A P Es t imator A l g o r i t h m Let TTk be a spatial Poisson process with rate Xlk at the subarea i, and let {Nk(o)\k < o <i] denotes the observed path of Wk in the time interval [k, t), i.e., the connection requests processed at the base station. The a posteriori probability mass function of Xl is iteratively calculated by the following algorithm. For t e [k,k + 1), define AN} = Nlk(t + At) - Nlk(t), where At is an arbitrary time interval, the a posteriori probability mass function P(Xk\Nk(o); k < o < t), for Chapter 3. Adaptive Sectoring 41 A l g o r i t h m 1 Adaptive Sectoring Algorithm 1: Initialize P(Xlk=0) for all subarea i and the Influence model parameters {See Sec. 3.1.2.} 2: for (jfe = 0; k < 23; k + +) do 3: t *- k 4: repeat 5: t = t + AT 6: M A P estimation of each subarea's rate function. Complexity O(M). {See Sec. 3.2.2} 7: un t i l ( M A P estimator stabilizes) 8: Construct the shortest path's weight matrix. Complexity O(M). {See Sec. 3.1.1 for the shortest path formulation and Sec. 3.2.3 for the outage probability compu-tation} 9: Dijkstra's Algorithm to find the shortest path. Complexity 0(M2N).{See Sec. 3.2.4} 10: Cell sectorization. 11: Update the rate function estimator for k + 1. {See Sec. 3.2.2} 12: end for Chapter . 3. Adaptive Sectoring 42 i = 1,2,3,4 is P(Xt\Nt(o);k<o<t + At) (3.9) = P(Xi\Nl(o); k<o<t)[l + {Xi-Xl)Xf\ANl - X< At )} + o(At), where X\ = E[Xlk\Ni(c); k < o < t] = X j P ( X j | J V ^a ) ; k < o <t), and for A i small enough, AiV t* is either 0 or 1 depending on occurrence or nonoccurrence of events and o(At) is negligible. At the end of the time interval [k, k + 1), label nx = {Nk(o);k < o < k + 1}, n 2 = {Nl{o)\k < o < k + 1 } , . . . , and n 4 = {A^(cr); k < o < k + 1}, the probability mass function of the subarea 1 at the beginning of the next time interval [fc + l,fc + 2) is P(Xlk+l = x\m,n2,n3,n4) = £ d u £ P(Xl+1 = x\Xi)P(Xi\nj), (3.10) where dXj and P(Xk+1\Xl) are Influence model parameters. For t € [k + l,k + 2), (3.9) again continuously update the a posteriori probability upon receiving connection requests. As a result, assuming the initial probability P(Xlk=0) is known for all i, the a posteriori probability of Xk can be tracked for any time t, and thus the M A P estimator at time t is a r g m a x P ^ 1 = x\N£(o),..., N£(o); k<o<t) (3.11) 3.2.3 Outage Probability Evaluation for Adaptive Sectoring In this subsection, the aim is to evaluate the outage probability (3.8) of an arbitrary sector configuration. The spatial Poisson distribution is assumed known, and its resulting Chapter 3. Adaptive Sectoring 43 outage probability is computed. Let Uk be the union of spatial Poisson processes loading a sector, the total interference received at the sector of base station B\ is computed with (3.7) and the outage probability is P(F[B1] + I°[B1]>a) = p( 2~2 1+ E rz[Cz}/rz{B1}>a). \zenk[Bi] zenfc[Bi] / Recall is the mobile point pattern power controlled by Bi and n^Bi] is the point pattern not power controlled by B\. It is obvious that the first term, P[Bi], is a Poisson random variable. In addition, in order for the base station Bi to be well defined, a condition that /*[5i] > 0 should be imposed. Combining the two observations, the outage probability becomes P(P[B1} + I°[BX\ > a|r[Bx] > 0) = — — £ ^-P(r[Bi] >a-(j- 1)) where u = E(/ l[jS 1]). The exact expression for P(I°[Bi]) is difficult, however, from [8,17], it is shown that Gaussian approximation can be applied; the approximation is motivated by the central limit theorem and it is treated rigorously in [17]. In order to compute the mean and the variance of the Gaussian approximation, the characteristics function of /°[Bi] is derived, and the mean and the variance are the first and second cumulants of I°[Bi] respectively. Theorem 3 below establishes the existence of the characteristics function and Theorem 4 shows the expression to compute the cumulants based on the model assumptions. Let IIfc[5i] be a Poisson point pattern on the network area A with mean measure Chapter 3. Adaptive Sectoring 44 m[Bx). Recall 7°[7^] = Y.z&tkm V^C^/V^}, define ( 0 if Cz = Bx, 4>z[Bi] = Theorem 3 If JA Jm+ min(|<^2[Bi]|, \)m[Bx](dz) < oo holds, then for any complex number s, the characteristics function of 7°[5i] can be calculated with E(exp(s/°[Si])) = exp ^ [ e x p ^ ^ ] ) - l]m[5i](<fe)) . (3.12) P r o o f The proof can be found in [8]. | The hypothesis holds since the area A is finite (only the first layer of interference is considered in this thesis), and the mean measure of the spatial Poisson process has finite states. As a result, the characteristics function of 7°[Bi] exists, and its cumulants can be computed. L e m m a If the characteristics function of I°[Bi) exists, let KC denotes the cth cumulant o f / ° [5 i ] , K c = ^ ( l n E ( e x p ( s / 0 [ 5 i ] ) ) L = o > then Kc= f E(^[5!]) cm(rfz). J A P r o o f From (3:12), l n E ' s / " ^ ] ] is given by Thus KC = / / #[Bi]cm[B,](ifa) JA J9t+ Chapter 3. Adaptive Sectoring 45 = / n{UBx])c]m{dz) | JA Theorem 4 Divide the network area A into Ain-ceu and Aother-ceii, where in-cell (other-cell) is defined by the inclusion (exclusion) of Bi in the soft handoff set ( z at the location z, i.e., for z G Ain_cell, Bx c Cz and for z £ Aother_ceU, £ Cz- If soft handoff set contains only 2 base stations, label the soft handoff base stations in Ain_ceu as Cz and Bi, and the base stations in Aother-ceii as Bm and Bn, the cth cumulant is where m(dz) is defined in (3.6), f3 = lnlO/10 and Ms , = \Q^\oglQd[z, B{\. P r o o f From the lemma above, and recall (3.3) for Tz, KC = jTE(^[fi 1]) cm(dz) = j T E ^ ^ j ^ j •Tz{Cz}<rz[B1}^m(dz) r ((d[z,Cz}nOb^c*W\c (d[z,Cz] ' I Q H ^ / i o ) ^ hm_cM \\d\z1Bl}n^B1mj ^d[z,B1]} < io"(^/ 1 0 ) ) m [ a z ) r ((d[z,Bm\riW.*~M\c fd[z,Bm]„ „ 1 0 ^ / i o ) ^ y / / ^ , B K p i O b f e . B n / i Q ) \ c d[z,B n ] 1 0 X ^ / 1 0 ) \ A o t_ c e i i ^{{d^B^lQf^/io)) ^d{z,Bm]} lO b(^.Bn/io) j m { - d z ) JAin_cM a[z,&i\ V 6 / A*> Bm] ,C1T? / , t „ M B m - M B , /• ( f e ^ ) - E (exp ( c & f l ^ - 6 , B J ) ; < & i B n - &>Bm) m(dz) J A o t h e r - c c U d[Z, BX\ \ 0 / JAotHcr-cM d[z,Bl\ V 0 ' Chapter 3. Adaptive Sectoring 46 The last equality is arrived at by taking the mean of the Gaussian variable £ 2 | s ; — MB -MB ^ _ under the constraint — ^ < tZiB. — tZtB.. | With (3.13), 7°[5i]'s mean and variance, K I and K2 respectively, are calculated, and the outage probability becomes: -m oo j P ( r [ B 1 ] + Z ^ ] > alPlBr] > 0) = — — £ — Q f e ) (3.14) 1 e j= i J -where = (a — j + 1 — KI)/T/K2, m is the mean of IlfcfBi] and Q is the Q-function for the standard normal distribution. From the above equations, it can be seen that if the rate function of the spatial Poisson process is known, the cost function for each sectoring configuration can be com-puted. However, the computation requires two numerical integration: one for the in-cell mobiles and the other for the other-cell mobiles. The numerical integration process is computationally intensive and time consuming. Fortunately, because the rate function of the spatial Poisson process is assumed to be constant over each subarea, the integration can be precomputed, and real time operation has computational complexity linear to the number of subareas in n/~. 3.2.4 Dijkstra's Algorithm For reader's convenience, the Dijkstra's algorithm [45] is presented in Algorithm 2, page 47. The instance of the shortest-path problem is given in Fig. 3.3, and which is the acyclic network constructed from the graph partitioning problem. Denote E as the set of edges in the graph, W : E —> 3?1 as the weight function of the edge (The outage probability Chapter 3. Adaptive Sectoring 47 computed in the previous subsection), and let g(i) be the weight of a minimum-weight 1-i path, the Dijkstra's algorithm is as follows: A l g o r i t h m 2 Dijkstra's Algorithm 1: Initialize: g(l) = 0, U = {1}, h(j) = WXi if (1, j ) G E, h(j) = oo otherwise. 2: Let i = argmin^gry h(j). If the minimum is not unique, select any i that achieves the minimum. Set U <— U U {i} and g(i) = h(i). If U — V, stop. 3: For all j # U with G E, h(j) <— min(^(z) + W y , Return to step 2. 3.3 Simulation Results In this section, the focus is on the numerical analysis of the adaptive sectoring algorithm. The analysis consists of two parts: Sec. 3.3.1 simulates the traffic tracking with the mobility-enhanced traffic model as described in Sec. 3.2.2, and Sec. 3.3.2 simulates a hot-spot scenario where a comparison in performance of adaptive and fixed sectoring is made. 3.3.1 Simulation of Spatial Poisson Estimation As described in Sec. 3.1.2, the network traffic is determined by a spatial Poisson process whose rate function is described in terms of the Influence Model. Ideally, the param-eters of the Influence model can be learned from the actual traffic statistics using the expectation-maximization method or the constrained gradient descent method [11, 5]. Chapter 3. Adaptive Sectoring 48 However, in this thesis, the model parameters are assumed known, and a hypothetical network is used to simulate the tracking of the rate functions. The hypothetical network consists of 10 adjacent subareas, and the Influence model parameters are arbitrarily chosen. The rate function X\ in each subarea is assumed to have three states {High, Medium, Low}. Fig. 3.5 illustrates the traffic tracking for four time slices of 2 subareas in the network. The blue line is the true state of the subarea, and the green dotted line is the output of the M A P estimator (3.11). It can be seen that the estimator follows the true state nicely except for the first few minutes after each time the rate function changes value (on a hourly basis). The reason is that the estimation equation is formulated in a finite difference form, and update is done only upon new arrival of connection requests. As a result, a certain convergence time is needed for the M A P estimator to reach the true value. Fig. 3.6 illustrates the real time tracking with the finite difference equation (3.9) of the two subareas during the first time interval. As the connection requests arrive, the real time update of the subareas' probability mass function is plotted. The top (bottom) plot shows that the system is getting more certain that the subarea is in state High (Low) as connection requests are accumulated. It can be observed that the convergence speed is directly proportional to the magnitude of the rate function. The tracking converges within 4 minutes when the subarea is in state High, while the tracking of the state Low takes approximately 40 minutes. However, since the M A P estimator depends only on the absolute difference between the state probabilities, the estimation yields accurate result Chapter 3. Adaptive Sectoring 49 20r 15 £ 1 0 5h 20 15 £ 1 0 Spatial Poisson rate tracking of two subareas 50 50 100 150 100 150 Time (minutes) 200 200 250 250 Estimated intensity -True intensity Figure 3.5: The real time output of the M A P estimators of the traffic in two subareas of a hypothetical network are plotted for four 60-minute periods. The realizations of the intensity functions in subareas are generated using the Influence model, and (3.11) is applied to follow. The solid line is the simulated realization, and the dotted line is the M A P estimator value. Chapter 3. Adaptive Sectoring 50 1 0.8 0.6 0.4 0.2 0 Probability tracking of a subarea in state High 10 J > h 20 30 40 Probability tracking of a subarea in state Low 50 30* Time (minutes) 60 Figure 3.6: The two plots illustrate the real time tracking of the a posteriori probability mass function of the two subareas in Fig. 3.5 for the first 60-minute period. (3.9) is applied to update the a posteriori probability mass function as traffic data is accumulated. It is evident from the figure that the convergence speed in tracking is directly proportional to the magnitude of the rate function. Chapter 3. Adaptive Sectoring 51 as long as the true state has the highest probability. 3.3.2 Simulation of Adaptive Sectorization The typical problem of nonuniform traffic is manifested in the generation of hot spots. In this subsection, the response of the adaptive sectoring algorithm is studied against a hot spot scenario, where a comparison in network capacity of the adaptive and the fixed sectoring is made. Fig. 3.4 illustrates the network model. The network consists of 19 cells and each cell has radius of one. The value of the path-loss exponent, 7 , is assumed to be 4, and the required SIR is set to 7 dB/128, which corresponds to a despread SIR of 7 dB when the spreading factor is 128. Furthermore, the shadowing component in the propagation uncertainty is taken to have standard deviation of 8 dB. Under the network assumptions made, the outage probability of different sector configurations under uniform traffic is illustrated in Fig. 3.7. It is obvious that the sector with angular span of 4 subareas has the steepest slope, and the sector with one subarea is the smoothest. Suppose the cell of interest is the central cell, the hot spot scenario considered is to increase the rate function of its two neighboring cells, and determine how adaptive sectoring can mitigate the effect. Fig. 3.8 illustrates the difference in outage probabilities between the fixed and the adaptive sectoring. In the fixed sectoring case, when the rate function is gradually increased, as illustrated in Fig. 3.8(a), the sector closest to the hot spot experiences high outage probability while the other two sectors have all the unutilized resources. On the other hand, the adaptive sectoring case is illustrated in Fig. Chapter 3. Adaptive Sectoring 52 10 10 ' .10 . 10 ° IQ" 2 0 10-h 10 ' Outage probability of different sectoring configurations (constant intensity value in all cells) 0'' : . A / . ; . . . . X ' .; V ••••x~-» -0~1 subarea —x— 2 subareas - O 3 subareas - * - 4 subareas 0 2 4 6 8 10 12 14 16 18 20 Mean number of users per subarea Figure 3.7: Outage probability of sector configuration consisting of 1 to 4 subareas under constant spatial Poisson rate. 3.8(b), and it can be observed that the adaptive sectoring algorithm narrows the loaded sector when its outage probability starts to rise, and share the load among the three sectors. It is observed that even though the outage probabilities have risen in the other two sectors, they are well below 1%; the outage probability in the fixed sectoring case has soared to approximately 9%. Chapter 3. Adaptive Sectoring 53 10" 10" Outage probability with fixed sectoring under hot spot 10" —Sector Two ™ b ~ Sector One Sector Three 10 15 20 Intensity (a) Outage probability with fixed sectoring. 10" Outage probability with dynamic sectoring under hot spot 10' i-~e~ Sector One Sector Two -0-Sector Three (b) Outage probability with dynamic sectoring. Figure 3.8: Comparison of system performance with fixed and dynamic sectoring under hot spot condition. It can be observed that dynamic sectoring balances the traffic and keep the outage probabilities of the three sectors under 1%, where the loaded sector in fixed sectoring has approximately 9% outage probability. 54 Chapter 4 Conclusion and Future Work 4.1 Conclusion In this thesis, a solution to the adaptive sectoring problem is developed. A mobility-enhanced traffic model is built to capture the mobile distribution from the network traffic statistics, and the dimension of the model is significantly reduced using the Influence model. For a network of M subareas and each subarea has Q possible states, the number of model parameters is MQ2 + M2. Furthermore, the real time tracking of the mobile distribution enables the computation of each sector's outage probability, and the adaptive sectoring algorithm is formulated as a shortest path problem, which is easily solvable with standard Dijkstra's algorithm. The simulation on the tracking of the spatial Poisson process' rate functions has shown rapid convergence when the rate function is high. On the other hand, even though the convergence is slow when the rate is low, accurate estimation is made as long as the true state has the highest probability. Furthermore, the simulation of hot spot scenario has demonstrated the adaptive sectoring's ability to cope with nonuniform traffic distribution. The adaptive sectoring balances the load between sectors such that no sector Chapter 4. Conclusion and Future Work 5 5 has outage probability exceeding 1%, while the fixed sectoring scheme experiences outage of approximately 9%. 4.2 Limitations • While the application of the Influence model greatly reduces the model parameters, the joint effects of the neighbors is sacrificed and only the first order effects is modeled. Furthermore, the Influence model's parameters are assumed known, and the probabilistic structure of individual Markov chains is assumed to be identical across the network. • The evaluation of the outage probability in Sec. 3.2.3 is based on the estimated value instead of the entire probability density function of the spatial Poisson's rate function. In other words, hard decision is made and the sectorization is not optimal. • The possible capacity improvement with increasing the soft handoff area of the smart antenna radiation pattern is not studied; increasing the sector overlap may help reducing the interference and improving the system performance because of the diversity gain of the soft handoff. 4.3 Future Work • Application of the mobility-enhanced traffic model to other resource management problems such as channel allocation. Chapter 4. Conclusion and Future Work 56 • Currently, the model parameters are assumed known, and each subarea (individual Markov chain) is assumed to have the same state space. However, the Influence Model is very flexible, and it is possible to have different state space for different subareas, and have the model parameters estimated based on the real time traffic data. • Improve the algorithm that evaluates the outage probability; instead of using the estimated value of the spatial Poisson's rate functions, use its probability density function. • Study the possibilities of incorporating the soft handoff diversity gain into the cost function of the optimization problem, and determine its effects on the sectorization decision. • Study the steady state behaviour of the mobiles' mobility pattern using the esti-mated Influence model matrix. The study may provide information essential to cell planning and cell dimensioning, and lead to efficient investment on telecommuni-cation infrastructure. 57 Bibliography [1] 3GPP. Technical specification group radio access network, physical channels and mapping of transport channels onto physical channels (FDD), TS 25.221 V3.2.0 (2000-03). [2] A . Ahmad. A C D M A network architecture using optimized sectoring. IEEE Trans-actions on Vehicular Technology, 51:404-410, May 2002. [3] C. Asavathiratham. The Influence Model: A Tractable Representation for the Dy-namics of Networked Markov Chains. PhD thesis, Massachusetts Institute of Tech-nology, 2000. [4] A . Bar-Noy, I. Kessler, and M . Sidi. Mobile users: To update or not to update? Wireless Networks, 1:175-185, 1995. [5] S. Basu, T. Choudhury, B . Clarkson, and A. Pentland. Learning human interactions with the influence model. Technical report, MIT Media Laboratory, June 2001. [6] J. Bouchard and E. Pyers. Use of gravity model for describing urban travel. Highway Research Record, 88:1-43, 1965. Bibliography 58 [7] T. Camp, J . Boleng, and V . Davies. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing, 2:483-502, September 2002. [8] C. Chan and V . Hanly. Calculating the outage probability in a C D M A network with spatial poisson traffic. IEEE Transactions on Vehicular Technology, 50:183-203, January 2001. [9] K . Chan. Effects of sectorization on the spectrum efficiency of cellular radio systems. IEEE Transactions on Vehicular Technology, 41:217-225, August 1992. [10] S. Choi, D. Shim, and K . Sarkar. A comparison of tracking-beam arrays and switching-beam arrays operating in a C D M A mobile communication channel. IEEE Antenna and Propagation Magazine, 41:10-22, December 1999. [11] T. Choudhury, B. Clarkson, S. Basu, and A. Pentland. Learning communities: Connectivity and dynamics of interacting agents. Technical report, MIT Media Laboratory, July 2003. [12] S. Dennett. The CDMA2000 ITU-R R T T candidate submission (0.18). Technical report, TIA, July 1998. [13] C. Yun et al. Traffic balancing performance of adaptive sectorized systems. Vehicular Technology Conference, 3:1878-1881, September 2002. Bibliography 59 [14] D. Simone et al. Fair dissections of spiders, worms, and caterpillars. Networks, 20:323-344, 1990. [15] J. Zhang et al. An efficient algorithm for adaptive cell sectoring in C D M A systems. IEEE International Conference on Communications, 2:1238-1242, May 2003. [16] L. Korowajczuk et al. Designing CDMA2000 Systems. John Wiley and Sons, Ltd, 2004. [17] S. Evans and D. Everitt. On the teletraffic of C D M A cellular networks. IEEE Transactions on Vehicular Technology, 48:153-165, January 1999. [18] J. Feuerstein. Controlling R F coverage - smart antennas know how to optimize cdma networks. America's Network, 102:69-71, February 1998. [19] S. Frost and B. Melamed. Traffic modeling for telecommunications networks. IEEE Communications Magazine, 32:70-81, March 1994. [20] R. Giuliano, F. Mazzenga, and F. Vatalaro. Smart cell sectorization for third gener-ation C D M A systems. Wireless Communications and Mobile Computing, 2:253-267, May 2002. [21] C. Godara. Applications of antenna arrays to mobile communications, part i i : Beam-forming and direction-of-arrival considerations. Proceedings of the IEEE, 85:1195-1245, August 1997. Bibliography 60 [22] C. Godara. Applications of antenna arrays to mobile communications, part kperformance improvement, feasibility, and system considerations. Proceedings of the IEEE, 85:1031-1060, July 1997. [23] J. How, D. Hatzinakos, and N . Venetsanopoulos. Performance of F H SS radio net-works with interference modeled as a mixture of Gaussian and alpha-stable noise. / IEEE Transactions on Communications, 46:509-520, April 1998. [24] T. Imielinski and F. Korth. Mobile Computing. Kluwer Academic Publishers, 1996. [25] T. Kaiser. When will smart antennas be ready for the market? part 1. IEEE Signal Processing Magazine, 22:87-92, March 2005. [26] C. Kingman. Poisson Processes. Clarendon Press, Oxford, 1993. [27] D. Lam, D. Cox, and J. Widom. Teletraffic modeling for personal communications services. IEEE Communications Magazine, 35:79-87, Feburary 1997. [28] C. Liberti and S. Rappaport. Smart Antennas for Wireless Communications: IS-95 and Third Generation CDMA Applications. Prentice Hall P T R , 1999. [29] M . Mahmoudi, S. Sousa, and H. Alavi. Adaptive sector size control in a C D M A system using Butler matrix. IEEE Transactions on Vehicular Technology, 2:1355-1359, May 1999. Bibliography 61 [30] T. Nguyen, P. Dassanayake, and M . Faulkner. Capacity of C D M A cellular systems with adaptive sectorisation and non-uniform traffic. Vehicular Technology Confer-ence, 2:1163-1167, October 2001. [31] K . Pahlavan and P. Krishnamurthy. Principles of Wireless Networks: A Unified Approach. Prentice Hall P T R , 2002. [32] S. Rappaport, A . Annamalai, M . Buehrer, and H. Tranter. Wireless communications: Past events and a future perspective. IEEE Communications Magazine, 40:148-161, May 2002. [33] M . Remiche and K . Leibnitz. Adaptive soft-handoff thresholds for cdma systems with spatial traffic. Technical report, University of Wiirzburg, October 1998. [34] U . Saraydar and A . Yener. Adaptive cell sectorization for C D M A systems. IEEE Journal on Selected Areas in Communications, 19:1041-1051, June 2001. [35] M . Sexton and A . Reid. Broadband Networking. Artech House, Inc., 1997. [36] D. Shim and S. Choi. Should the smart antenna be a tracking beam array or switching beam array?, May 1998. [37] L. Snyder. Random Point Processes. John Wiley & Sons, Ltd, 1975. [38] L. Snyder and I. Miller. Random Point Processes in Time and Space. Springer-Verlag, 1991. Bibliography 62 [39] S. Sousa. Performance of a spread spectrum packet radio network link in a Pois-son field of interfererers. IEEE Transactions on Information Theory, 38:1743-1754, November 1992. [40] K . Takeo and S. Sato. Dynamic cell configuration for C D M A microcell mobile radio communications systems considering nonuniform traffic distribution. Electronics and Communications in Japan, 83:75-89, 2000. [41] D. Tang and M . Baker. Analysis of a metropolitan-area wireless network. Wireless Networks, 8:107-120, March 2002. [42] G. Tsoulos, M . Beach, and J. McGeehan. Wireless personal communications for the 21st century: European technological advances in adaptive antennas. IEEE Communications Magazine, 35:102-109, September 1997. [43] K . Tutschku and P. Tran-Gia. Spatial traffic estimation and characterization for mobile communication network design. IEEE Journal on Selected Areas in Commu-nications, 16:804-811, June 1998. [44] J. Viterbi. CDMA: Principles of Spread Spectrum Communication. Addison-Wesley Publishing Company, 1995. [45] A. Wolsey and L. Nemhauser. Integer and Combinatorial Optimization. John Wiley & Sons, Ltd, 1999. Bibliography 63 [46] V . W. S. Wong and V . C. M . Leung. An adaptive distance-based location update algorithm for next-generation pes networks. IEEE Journal on Selected Areas in Communications, 19:1942-1952, October 2001. [47] W. Wong and K . Prabhu. Optimum sectorization for CDMA1900 base stations. Vehicular Technology Conference, 2:1177-1181, May 1997. [48] F. Yu and V . C. M . Leung. Effects of mobility on packet level performance of connection-oriented multimedia traffic over packet-switched cellular networks. Wire-less Communications and Networking Conference, 4:2171-2176, March 2004. [49] M . Zhang and C. Lea. The impact of mobility on C D M A ' s capacity and call admis-sion control. Wireless Communications and Networking Conference, 4:2371-2376, March 2004. 64 Appendix A Derivation of M A P Estimator In this Appendix, the M A P estimator introduced in Sec. 3.2.2 is derived. Because of the symmetric property of hexagonal cellular network, the estimators of all the subareas are equivalent. Fig A . 1(a) illustrates the network model, and the subarea to be estimated is labelled as Xk whose evolution is shown in Fig. A. 1(a) as a dynamic bayes net (DBN). The solid lines in D B N show the dependency of Xk at k+l on itself and its neighbors' pre-vious state. (The dotted lines refer to other subareas' dependency, but they are irrelevant in estimating Xk.) Note that for each k, Xlk is not observable; it is indirectly observed through the connection requests processed in each subarea i, and which is labeled as Nk in the figure. As a result, the estimation problem is the recursive propagation of the realizations Nk for i = 1,2,3,4 to determine the a posteriori probability distribution of Denote the a posteriori probability distribution for Xk given the network traffic Nk up to time k as the marginal function P^k = P(Xl\NQ.k, A^.*., A ^ , A ^ ) , and the prediction as Pk+1]k = P(X£+1\NZ:k, N2k, N*k, N*k), where TV* fc = (N> N{ .., N*). The recursive computation of two marginal functions produces the a posteriori probability tracking of the subarea. Fig. A. 1(b) illustrates the dynamics as a factor graph with the marginal Appendix A. Derivation of MAP Estimator 65 (a) The mapping of the network model to its corresponding Bayes net representation. The solid lines in the Bayes net indicate the dependency structure of Xl on itself and its neighbors' previous states, and the dotted lines indicate the dependency structure of other subareas. (b) Factor graph representation of the Bayesian network. The X\ is isolated and the conditional probabilities relevant to the estimation of Xl are explicitly illustrated. Figure A . 1 : The figure illustrates the network model relevant to the development of the M A P estimator, and the corresponding graphical representation. The sub-area of interest is labeled as Xl, and its dependency on its neighboring subareas are represented as a Bayes net in (a) and as a factor graph in (b). Appendix A. Derivation of MAP Estimator 66 functions explicitly stated. Given P^k for all i, th prediction part can be computed easily. Let Zxk = E x i E x * ' • • E x £ > p i _ V ^ p f y l I y l y 2 y 3 Y ^ P 1 P 2 P 3 P 4 = EQI dlJ-P(^fc+ll^D)-PfeV^fc|fe^>fc|fc'':fc|fc where the second step uses the Influence model representation discussed earlier in Sec. 3.1.2. Both dXj and P(Xk+1\Xk) are defined model parameters. The computation of P^k from the previous prediction is illustrated in the following Theorem. Theorem Suppose Nk(t) is doubly stochastic Poisson with rate Xk, and Xk is a random variable. If we let Pt(Xk\Nk(o); k < o < t) denote the conditional probability density function for Xk given the connection request statistics {Nk(o);k < o < t}, then we obtain dp(Xl\Ni(o);k<o<t) (A.1) p(Xi\Ni(o); k<o< t)(Xl - Xl)Xl\dNt - X{dt), with P(Xt\Ni(o);o = k) = Pi{k_v and XI = E[Xi\Ni(o); fc < a < t] = £ X « Pt(Xi\Nl(o); k<o<t) Proof The proof can be found in [38]. | Eq. (A.1) can also be viewed as defining an updating algorithm according to which the prior density Pkt^k_1 is propagated forward in time to form the a posterior density Pk\k as data are accumulated. For this interpretation, it is convenient to rewrite (A.1) in Appendix A. Derivation of MAP Estimator 6 7 the finite difference form P(Xt\Nt(o);k<o<t + At) r 1 ( A - 2 ) = P(Xi\Nt(o); k < o < t) | l + (Xi - Xl)Xl\ANi - X« At )} + o(At), For A i sufficiently small, the term o(At) can be disregarded and A i V t l = Nk(t + At) — Nf.(t) will be either zero or one according to the nonoccurrence or occurrence of a point in [t,t + At). As CT reaches time k + 1, P(Xk\Nk(o)) = P^k, which completes the cycle.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Mobility enhanced smart antenna adaptive sectoring...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Mobility enhanced smart antenna adaptive sectoring for uplink capacity maximization in CDMA cellular… Wang, Alex 2005
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Mobility enhanced smart antenna adaptive sectoring for uplink capacity maximization in CDMA cellular network |
Creator |
Wang, Alex |
Publisher | University of British Columbia |
Date Issued | 2005 |
Description | In this thesis, adaptive sectoring of a CDMA cellular network is investigated, and the aim is to maximize the uplink capacity by utilizing the mobiles' spatial information. One important feature of the algorithm developed is that it does not depend on tracking individual mobile, but rather on the statistics of mobiles. The distribution of mobiles is modeled as a spatial Poisson process, whose rate function quantizes the mobile concentration and is inferred with a Bayesian estimator based on the statistics of network traffic. In addition, the time dynamics of the rate function is assumed to evolve according to the mobiles' mobility pattern and it is formulated using the Influence model. With the knowledge of the mobiles' spatial distribution, the interference and thus the outage probability of different sector partitions of a cell can be computed. The adaptive sectoring problem is formulated as a shortest path problem, where each path corresponds to a particular sector partition, and the partition is weighted by its outage probability. In simulation examples, a hot spot scenario is simulated with the adaptive sectoring mechanism, and it is observed that load balancing between sectors is achieved and which greatly reduces the effect of hot spot. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2009-12-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065870 |
URI | http://hdl.handle.net/2429/16798 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2005-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-ubc_2005-0685.pdf [ 2.68MB ]
- Metadata
- JSON: 831-1.0065870.json
- JSON-LD: 831-1.0065870-ld.json
- RDF/XML (Pretty): 831-1.0065870-rdf.xml
- RDF/JSON: 831-1.0065870-rdf.json
- Turtle: 831-1.0065870-turtle.txt
- N-Triples: 831-1.0065870-rdf-ntriples.txt
- Original Record: 831-1.0065870-source.json
- Full Text
- 831-1.0065870-fulltext.txt
- Citation
- 831-1.0065870.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0065870/manifest