Project Topics
Get Complete Project Material File(s) Now! »
Chapter 3 CDMA System Deployment
Introduction
In Chapter 2, the fundamentals of wireless communication systems were discussed. In a cellular wireless communication system, each cell has a fixed base station which connects to multiple mobile users simultaneously. The users share the available resources in the cell using multiple access schemes like Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA) and Code Division Multiple Access (CDMA).
The multiple access in a (cellular) wireless system is like a cocktail party in which people want to talk to each other simultaneously [5, p14] [18, p668]. This can be done in several ways, without creating confusion. They can either speak at different pitches (analogous to FDMA) or take turns to speak (analogous to TDMA) or speak in different languages (analogous to CDMA). In FDMA, the bandwidth (i.e the band of frequencies) is divided into frequency slots and each user is assigned a different frequency slot for transmission [12, p3]. In TDMA, each user uses the entire bandwidth but is assigned a different timeslot for transmission [1, p365] [21, p13]. Thus, in both TDMA and FDMA, there is a fixed limit on the capacity i.e. a fixed number of users can connect to a base station [1, p401]. However, in CDMA, each user is assigned a unique code for transmission and the capacity is not fixed1 [1, p365] [21, p15]. The concepts of the three multiple access schemes are shown in Fig. 3.1.
One of the most important advantage of CDMA systems is that there is universal frequency reuse i.e. the same frequency is used in each cell [21, p18]. In contrast, in FDMA and TDMA systems, the frequency is reused in cells which are (sufficiently) spatially separated. Also, as all the cells use the same frequency in CDMA, a user can simultaneously connect to two or more base stations. Another multiple access scheme which can have universal frequency reuse is the Orthogonal Frequency Division Multiple Access (OFDMA), in which each user is assigned a subset of the subcarriers as shown in Fig. 3.1 [16, p105] [21, p19]. However, CDMA systems are considered in this thesis because the interference models for CDMA systems are well developed2 and widely used for system planning.
In this chapter, the fundamentals of CDMA are discussed and the deployment strategies developed (in the literature) for Base Station Placement (BSP) are reviewed. In Section 3.2, the details of CDMA (in particular the operation, handover and power control) are discussed. A literature review of the strategies developed for solving the BSP problem is presented in Section 3.3 and the contributions of this thesis are outlined in Section 3.4. The chapter is summarised in Section 3.5.
CDMA Fundamentals
CDMA is a multiple access scheme in which each user is assigned a unique codeword and thus, all the users can transmit simultaneously and share the same bandwidth [1, p365] [21, p15]. In Section 3.2.1, the operation of CDMA is discussed focusing on how the transmitter codes and receiver decodes the message. As discussed in Section 2.4, the received message signal is affected by interference and noise. Thus, handover is performed to maintain connectivity of users (while they are moving) and the transmission powers need to be managed to minimise the effect of interference and noise. The handover process and the implementation of power control for CDMA systems are discussed in Sections 3.2.2 and 3.2.3, respectively.
Operation of CDMA
In CDMA, the narrowband message signal is multiplied by a wideband signal called the spread-ing code before it is transmitted3 on the carrier channel4 [5, p15] [17, p458]. As shown in Fig. 3.1, all the users use the same (carrier) frequency and can transmit simultaneously. How-ever, each user is assigned a unique pseudo random codeword which is approximately orthogo-nal to other codewords and distinguishes it from the other users in the system.
When a user receives a signal (from a base station), it uses its unique codeword to perform a time correlation operation and decode its desired message. In addition to the desired message, the received signal also contains messages for other users which appear as interference (as the codewords of the users are not exactly orthogonal) [21, p16]. The interference increases as the number of users increases and the capacity of the system depends on the total interference
generated by the users. Thus, CDMA systems are known as ‘user-limited’ or ‘interference-limited’ systems [12, p3].
Handover
As discussed in Section 2.4, a user connects to a base station only if the Signal-to-Interference Ratios (SIRs) are above the thresholds, in both the forward and reverse links. As a (connected) mobile user moves away from a base station, the SIR can go below the threshold and handover is performed.
There are two main types of handovers — hard and soft handovers [17, p67]. In hard handover, the mobile user disconnects from the current base station before connecting to a new base station and thus, it is also referred to as break-before-make handover. Soft handover is referred to as make-before-break handover as the mobile user connects to the new base station and then disconnects from the current base station [1, p404]. In soft handover, if a base station has multiple sectors, a user can also connect to a different sector of the same base station instead of connecting to a new base station. This is referred to as softer handover [5, p17].
Hard handover is performed in FDMA and TDMA systems [5, p17]. The advantage of hard handover is that only one frequency channel is used by the mobile user at any time. On the other hand, CDMA systems perform soft or softer handover and the advantage is that there are no chances of losing a call due to handover failure [1, p404] [17, p67].
Power Control
Power control is necessary for CDMA systems but it is optional for FDMA and TDMA systems [1, p404]. As discussed in Section 2.4, the transmission power is managed using power control schemes in both forward and reverse links.
Forward Link Power Control
The aim of power control on the forward link is to minimise the power of the signal transmitted by the base station ensuring that the received signal power at each user can achieve the required SIR threshold and overcome noise [1, p404] [5, p17] . Power control is implemented by the user, which requests the base station to adjust the forward link signal power to combat interference and noise.
Reverse Link Power Control
If there is no power control on the reverse link and all the users transmit signals with the same power, the near–far problem can occur at a base station i.e. the strongest received signal will interference by the other (or undesired) base stations [1, p404]. Though this interference cannot be controlled by the base stations, it can be minimised by careful placement of base stations.
Deployment Strategies — A Literature Review
The main design criteria for the placement of base stations in FDMA and TDMA systems was coverage maximisation [1,7,28–38] and/or path loss minimisation [37,39]. However, in CDMA systems, the signal power levels and the Signal-to-Interference Ratios (SIRs) are considered as performance measures and included in the recent mathematical models developed for Base Sta-tion Placement (BSP) [5, 8, 10, 40–50]. Also, some models developed in the literature include several factors (like traffic variability and multiple classes of services) affecting BSP optimisa-tion and are classified into one (or more) of the following four categories6:
-
- The optimisation includes call traffic variability models i.e. the variability of voice traffic, generally measured in Erlangs.
- The optimisation includes user mobility models i.e. the movement of users and handover.
- The optimisation includes models for multiple classes of services with constant bit rates i.e. the voice traffic and the data traffic with constant bit rates.
- The optimisation includes models for packet switched traffic with variable bit rates i.e. the different traffic distributions to model the variable bit rates (for packet switched systems)
The BSP problem is considered to be an NP-hard optimisation7 problem [10, 40–43, 51]. Thus, several standard and novel algorithms have been proposed (and compared using case studies) in the literature to solve the BSP problem. The investigations in the literature (i.e. models and algorithms) for solving the BSP problem are discussed in this section and summarised in Table 3.1.
Anderson and McGeehan [52] showed that an optimisation algorithm, Simulated An-nealing (SA) can be used for finding the optimal base station locations in an urban micro-cellular environment. The objective of their model is to minimise the difference between the received and the targeted signal strength on a grid of virtual user locations. The study demonstrates that BSP is a combinatorial optimisation problem which can be solved using (optimisation) algo-rithms like SA. Although SA is shown to be computationally demanding, it may prove to be useful with the continuing advances in computing resources
Wright et. al. [28,29] developed a software package called Wireless System Engineering (WISE) for designing indoor and campus-sized (“microcell”) wireless systems. The objective of WISE is to maximise the coverage i.e. the percentage of the building within which the received signal strength is above the defined threshold. The package was written at AT&T Bell Laboratories and uses CAD and optimisation for BSP. The optimisation is performed using a variant of the Nelder-Mead method to find the optimal coordinates for placement of base stations.
Sherali et. al. [39] analysed and modelled the problem of placing (a single or multi-ple) base stations for serving a specified distribution of users. The objective of the study is to minimise the path loss using a nonlinear programming model. Three nonlinear optimisa-tion algorithms, namely, Hooke and Jeeve’s methods, Quasi-Newton, and conjugate gradient search procedures are investigated to solve the BSP problem. It is shown that BSP optimisation improves the performance of the system.
Tutschku et. al. [53–56] developed an integrated cellular network planning tool (ICEPT) which is one of the earliest tools to include the spatial distribution of the expected teletraffic within the service area of the cellular system. The objective of the tool is to maximise the average Carrier-to-Interference Ratio (CIR) while optimising the covered traffic. The traffic is estimated (considering the geographical and demographical factors) at discrete points, known as demand nodes. The Demand Node Concept (DNC) enabled the formulation of the BSP problem as a Maximal Coverage Location Problem (MCLP), which is well known in economics for solving facility location problems. The earlier version of ICEPT uses Adaptive Base Station Positioning Algorithm (ABPA). However, in [56], a greedy heuristic known as the Set Cover Base Station Positioning Algorithm (SCBPA) is proposed for optimisation.
Neve and Sowerby [57] investigated the suitability of a number of optimisation algo-rithms including Genetic Algorithms (GA) for solving the complex indoor BSP problem. The objective of their study is to minimise the fraction of a building volume that fails to achieve a defined threshold value of the CIR. It is shown that quantisation effect of an optimisation algo-rithm can have a significant impact on its performance and thus, the algorithm must be selected (and set up) carefully. It is also shown that SA and GA are suitable for BSP optimisation.
Krishnamachari and Wicker [30, 31] analysed the performance of four optimisation al-gorithms, namely Random Walk (RW), Simulated Annealing (SA), Tabu Search (TS) and Ge-netic Algorithms (GA), for solving the BSP problem. The objective of the study is to maximise
the coverage while selecting the minimum number of base stations (from an initial list of po-tential locations). It is shown that GA and TS are suitable for solving the BSP problem and GA is particularly scalable to large systems.
Molina et. al. [7, 32–36] developed a new algorithm, known as the Combinatorial Algo-rithm for Total optimisation (CAT) for solving the BSP problem. The objective of the algorithm is to select the minimum number of base stations (out of potential base station locations) re-quired to provide coverage and capacity to a set of users. It is not practical to evaluate all possible combinations of base stations if there are a large number of potential base station lo-cations. Hence, the CAT is implemented by splitting the potential base station locations into smaller groups and evaluating the possible combinations within each group. The best combina-tions from the groups are merged together in a unique group and the process is repeated until the number of solutions cannot be further reduced. The performance of the CAT is compared to the Greedy Algorithm (GR) and the Genetic Algorithm (GA) and it is shown that the CAT provides better solutions.
The study laid a foundation for optimisation of BSP and was extended to include the factors like traffic variability and multiple classes of services (i.e. voice and data) for BSP optimisation. In [33–35], the optimisation is extended by including non-uniform traffic distribution, priority for admission, delay spread and power control. In [36], optimisation is performed for WCDMA systems with multiple classes of services, using GA and Situation Awareness algorithms, in addition to the CAT.
Ji et. al. [37] developed a model to compare the performance of several optimisation algo-rithms, namely Steepest Descent, BFGS (Quasi-Newton), Simplex, Hooke and Jeeve’s method, Rosenbrock, Simulated Annealing (SA) and Genetic Algorithms (GA), to solve the indoor BSP problem. The objective of the model is to maximise the coverage by ensuring that the path loss is less than a defined threshold level. It is shown that Steepest Descent, Simplex, BFGS and Rosenbrock algorithms are unable to achieve ‘reasonable’ deployments. However, Hook and Jeeve’s method, SA and GA provide almost the same ‘reasonable’ results. It is also shown that a ‘suitable’ initial guess can significantly reduce the computational time for SA and GA.
Fruhwirth and Brisset [38] developed the POPULAR (planning for pico-cellular radio) package to find the optimal BSP, given the information about the potential base station and user locations and the propagation environment. The objective of the package is to compute the minimal number and locations of base stations (required to provide coverage to all the users) using a unique optimisation model. The attenuation level around each user is estimated using ray-tracing and a polygon is defined around the user. The polygon represents the region in which a base station can be placed to provide service to the user. The intersection of multiple polygons represents the location of a base station to provide service to the multiple users. Similarly, the minimum number and locations of base stations to provide service to all the users are computed.
Lee and Kang [58] formulated the BSP problem using a Binary Integer Programming (BIP) model and solved the problem of serving the user traffic using Tabu Search algorithm. The study considers two types of scenarios — the first is to deploy new base stations in an existing system and the second is to deploy a totally new system (with new base stations). The objective of the study is to minimise the cost (of deploying new base stations) ensuring that the base stations have enough capacity to serve the users and the signal power received at each user is above the defined threshold. Though the study does not consider interference, it emphasises the importance of including the traffic demands and the capacity of base stations. The traffic at the user locations is handled using a similar approach to ICEPT’s demand node concept [56]. Depending on the multiple access scheme (i.e. FDMA, TDMA or CDMA), the capacity of a base station is estimated for 2% blocking probability. It is shown that the performance of the proposed Tabu Search is superior to that of the Genetic Algorithm and the CPLEX solver for solving the BSP problem.
Amaldi et. al. [41–46] proposed discrete models and algorithms to find the optimal loca-tions and configurations (such as antenna height, tilt and sector orientation) of base stations for UMTS with voice and data traffic. The objective is to find a trade-off between maximising the coverage and minimising the costs. The proposed BIP models consider power control mecha-nisms and the signal strength levels as well as the SIRs on the forward and reverse links. The optimisation is implemented using customised Tabu Search, which uses the solutions provided by a randomized greedy algorithm. It is shown that the proposed models and algorithms are capable of delivering good solutions for different traffic scenarios.
The study creates realistic optimisation models which consider power levels as well as in-terference constraints and includes variable voice and data traffic. Though the mobility of users and handover is not included in the model, it is suggested as an extension to the study.
Wong et. al. [5,10,47,48] developed a unique framework8 (with mathematical models and optimisation algorithms) for solving the BSP problem of CDMA systems. The objective of the study is to minimise the number of base stations required to serve the users while satisfying the requirements for coverage, (transmitted and received) powers and (forward and reverse link) SIRs. The optimisation model is formulated using BIP and implemented using a customised Genetic Algorithm (GA). The performance of the GA is compared to the Branch-and-Bound (B&B) algorithm and it is shown that although the B&B guarantees to find the optimal solution, its computational time increases significantly as the problem size increases. On the other hand, the GA is shown to be generally effective for solving the BSP problem in ‘reasonable’ time even when the problem size increases.
Apart from developing comprehensive mathematical models to meet all the (power and in-terference) constraints for CDMA systems, this study also includes unique BIP models for mul-tirate traffic and diversity reception. The options considered for multirate traffic are Multi-Code (MC) and Varying Spreading Factor (VSF) and diversity reception are Equal Gain Combining (EGC) and Maximal Ratio Combining (MRC). It is shown that multirate traffic and diversity reception influence the signal quality and the BSP required to serve the users. Again, although the influence of user mobility on BSP is not investigated, it is suggested to include mobility profiles and handover strategies as an extension to the study.
Ngadiman et. al. [8] proposed a novel optimisation algorithm9 to solve the BSP problem for CDMA systems with traffic variations. The traffic variability is assumed by considering ‘snapshots’ of different numbers of fixed users. The objective of the study is to select the minimum number of base station locations (out of the potential locations) required to serve the users, ensuring the SIRs are above the defined thresholds in both forward and reverse links. The proposed optimisation algorithm begins by assuming that all the potential base station locations are active and assigns users to the base stations depending on the path loss. It then deactivates the base stations one by one (reassigning the users every time) as long as the SIR constraints can be met for all the users. The optimal BSP to serve the (variable number of) users is obtained by averaging the results for many iterations. It is suggested that multiple classes of services and user mobility can be included as an extension to the study.
Whitaker et. al. [49] investigated the sensitivity of coverage associated with considering ‘snapshots’ of user traffic for BSP in WCDMA systems. This study focuses on the importance of including the factors (like traffic variability) that can significantly influence BSP and must be analysed for network planning. The objective of the investigation is to demonstrate the effect of including priorities for user admission and multiple classes of services. However, models for user mobility and packet switched traffic (with variable bit rates) are not considered in this study. The algorithm connects the user to the best (i.e. least path loss) base station ensuring the downlink SIR is above the defined threshold. It is shown that admitting the users with greatest-path-loss first is useful and a ‘higher data rate user’ is satisfied at the expense of multiple ‘low data rate users’.
1 Introduction
2 Wireless Communication Systems — An Overview
2.1 Introduction
2.2 The Cellular Concept
2.3 Radio Propagation in Cellular Systems
2.4 Interference in Cellular Systems
2.5 Summary
3 CDMA System Deployment
3.1 Introductio
3.2 CDMA Fundamentals
3.3 Deployment Strategies — A Literature Review
3.4 Contributions of This Thesis
3.5 Summary
4 Optimisation and Wireless System Modelling
4.1 Introduction
4.2 Optimisation — An Overview
4.3 Optimisation for Base Station Placement (BSP)
4.4 Summary
5 Existing Algorithms for Base Station Placement — A Comparison
5.1 Introduction
5.2 Existing Algorithms for Base Station Placement (BSP)
5.3 Comparison of Existing Algorithms for Base Station Placement
5.4 Summary
6 Development of a Hybrid Algorithm — RCR
6.1 Introduction
6.2 The Hybrid Algorithm
6.3 Comparison of Hybrid and Existing Algorithms for Base Station Placement
6.4 Summary
7 Comparison of Algorithms and Outline of Investigation
7.1 Introduction
7.2 Comparison of Algorithms
7.3 Outline of Investigation
7.4 Summary
8 Effect of Call Traffic Variability on Base Station Placement
8.1 Introduction
8.2 System Models for Call Traffic Variability
8.3 Effect of Call Traffic Variability on Base Station Placement
8.4 Summary
9 Effect of User Mobility on Base Station Placement
9.1 Introduction
9.2 System Models for User Mobility
9.3 Effect of User Mobility on Base Station Placement
9.4 Summary
10 Effect of Call Switching Technologies on Base Station Placement
10.1 Introduction
10.2 System Models for Call Switching Technologies
10.3 Effect of Call Switching Technology on Base Station Placement
10.4 Summary
11 Optimisation of Multi-Floored Buildings and Future Work
12 Conclusions
GET THE COMPLETE PROJECT
Optimisation of Base Station Placement for Indoor Wireless Communications
