A Heuristic Solution to the Large Scale Cellular Telecommunication Network Expansion Problem

A Heuristic Solution to the Large Scale Cellular Telecommunication Network Expansion Problem

Joon-Yeoul Oh (Texas A&M University-Kingsville, USA) and John P. Mullen (New Mexico State University, USA)
DOI: 10.4018/978-1-60566-148-3.ch010
OnDemand PDF Download:


This chapter proposes a very effective heuristic algorithm to address a variation of the cellular network expansion problem and discusses each algorithm step in detail. Although the input to the algorithm appears to be a binary integer programming problem, the proposed algorithm deals with several nonlinear aspects. The solution specifies the connections of each component, cell sites, hubs, and mobile telephone switching office and satisfies the redundancy requirements for each cell site to ensure continued traffic flow in the event of a local overload or equipment failure. The algorithm reports the best feasible solution it finds, as well as lower and upper bounds on the cost of an exact solution. Preliminary testing indicates that it generates very good results, in spite of its very short execution time. The authors hope that in presenting such an algorithm, designers of very large cellular network expansions will have a tool to obtain significantly good solutions in a reasonable time. In addition, because the expansion problem presented here is a knapsack problem, the authors anticipate that this heuristic might have other applications in solving similar large-scale problems.
Chapter Preview


Over the years, significant technology improvements have been achieved in the field of cellular telecommunications. However, existing cellular network systems often cannot satisfy the sharply increasing demand due to the growing number of subscribers. For instance, some calls may not be connected during a peak time or frequent drop-calls may occur due to the limited coverage areas. Even if a system would normally be adequate, heavy phone call activity due to the evacuation from a natural disaster can cause a connection difficulty.

The cellular network expansion problem (CNEP) deals with the way to increase the capacity of existing cellular telecommunication network systems. There are two general ways to solve this problem. One is cell site splitting and the other is cell site addition.

The main idea behind cell site splitting is to split a large cell into a number of smaller cells to maximize the theoretical and practical capacity of the cell sites (Goodman, 1997). Depending on the density and distribution of traffic throughout the network, such systems can employ various sizes of cell sites. Generally, large cell sites are used to provide services to areas with low subscriber density. For high subscriber density locations, multiple smaller cell sites are used to provide services. In lightly populated areas, the diameter of a cell site can be up to 30km, whereas in the most densely populated areas, smaller diameters, 2km and 1km, are in use (Gardiner, 1995; Rappaport, 1996; William, 2001). This expansion method is the most commonly used.

In the case of cell site addition, new cell sites are created in areas that were originally not covered. The main concerns are the determination of the optimal number of cell sites and the location of the new cell sites. In 1992, AT&T Network Systems had a contract with the Pilipino Telephone Corporation (Piltel) to expand Piltel’s cellular network. For the $82 million contract, AT&T provided 1000 equipments including switching offices and cell sites (Bona, 1992). Cellular South in Mississippi also installed more than 100 cell sites to provide better coverage and clarity with $38 million investments for two years (Rankin, 2004). DIGITAL Telecommunications Philippines Inc. is planning to increase its cell sites to 4,000 in 2008 and they anticipate an increase of customers from the present five million to ten million with the cellular network expansion plan (Sanchez-Lacson, 2008).

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Indranil Bose
Chapter 1
Varadharajan Sridhar
Telecom operators have a wide variety of functions to perform including marketing of telecom products and services, managing their networks... Sample PDF
Strategic Outsourcing: Opportunities and Challenges for Telecom Operators
Chapter 2
Sami J. Habib
This article presents a computer-aided integration tool, iCAD, that can predict a network evolution. We have used the term a network evolution to... Sample PDF
Empirical Prediction of Computer-Network Evolution
Chapter 3
Hak Ju Kim
This article seeks to develop a richer understanding of the suitability of IP telephony in the Public Switched Telephony Network (PSTN) with an... Sample PDF
Suitability of IP Telephony in the Public Switched Telephone Network (PSTN): A Case Study
Chapter 4
Abid Al Ajeeli
This chapter describes a detailed framework configuration infrastructure design for a high performance network. The configuration is described based... Sample PDF
A Framework for High-Speed Networking
Chapter 5
Nurul I. Sarkar, Catherine Byrne, Nabeel A.Y. Al-Qirim
Ethernet network technology is still one of the most popular LAN technologies in use today by many organizations and educational institutions... Sample PDF
Updating on Gigabit Ethernet Implementation: The Case of a Large New Zealand Organization
Chapter 6
M. Chandrasekaran, R. S.D. Wahida Banu
This chapter introduces and analyses a class of non-linear congestion control algorithms called polynomial congestion control algorithms. These... Sample PDF
Interaction Between MIMD-Poly & PIPD-Poly Algorithms and other TCP Variants in Multiple Bottleneck TCP Networks
Chapter 7
Xabiel G. Pañeda
This chapter presents a method for performance analysis and configuration of audio/video-on-demand services. These kind of services makes use of an... Sample PDF
A Systematic Approach to the Analysis and Configuration of Audio/Video-on-Demand Services
Chapter 8
Say Ying Lim
As more and more servers appearing in the wireless environment provide accesses to mobile users, more and more demand and expectation is required by... Sample PDF
Mobile Information Processing Involving Multiple Non-Collaborative Sources
Chapter 9
Vilmos Simon
In the next generation IP-based mobile networks, one of the most important QoS parameters are the delay and the delay variation. The cell handover... Sample PDF
Network Planning Algorithms for Optimizing Signalling Load in Mobile Networks
Chapter 10
Joon-Yeoul Oh, John P. Mullen
This chapter proposes a very effective heuristic algorithm to address a variation of the cellular network expansion problem and discusses each... Sample PDF
A Heuristic Solution to the Large Scale Cellular Telecommunication Network Expansion Problem
Chapter 11
Manuel Vilas
This article introduces a distributed system, called wireless proxy, to mitigate the effects of user mobility over streaming services on IEEE 802.11... Sample PDF
Wireless Proxy: Distributed System to Mitigate the Effects of User Mobility Over Streaming Services on IEEE 802.11 Wireless LANs
Chapter 12
R. Radhakrishnan, K. R. Shankarkumar, A. Ebenezer Jeyakumar
In this chapter, we propose a new scheme for Multi User Detection (MUD) using Parallel Interference Cancellation (PIC) technique. This technique... Sample PDF
Soft Decision Parallel Interference Cancellation for Multi-Carrier DS-CDMA
Chapter 13
Ghassan Kbar
This chapter introduces a new radio resource management technique based on distributed dynamic channel assignment, and sharing load among Access... Sample PDF
Distributed Resources Management in Wireless LANs that Support Fault Tolerance
Chapter 14
Mieso K. Denko
This article proposes a cooperative data caching and prefetching scheme for Mobile Ad Hoc Networks (MANETs). In this scheme, multiple hosts... Sample PDF
Cooperative Data Caching and Prefetching in Wireless Ad Hoc Networks
Chapter 15
Essam Natsheh
The challenge in creating a routing protocol for ad-hoc networks is to design a single protocol that can adapt to the wide variety of conditions... Sample PDF
A Survey on Fuzzy Reasoning Applications for Routing Protocols in Wireless Ad-Hoc Networks
Chapter 16
Essam Natsheh
Mobile ad-hoc network is a network without infrastructure, where every node has its own protocols and services for powerful cooperation in the... Sample PDF
Fuzzy Linguistic Knowledge for Active Queue Management in Wireless Ad-Hoc Networks
Chapter 17
Yun Wang, Lee Seidman
The use of network traffic audit data for retrieving anomaly intrusion information and profiling user behavior has been studied previously, but the... Sample PDF
Risk Factors to Retrieve Anomaly Intrusion Information and Profile User Behavior
Chapter 18
Rania Wehbi
In Inter-Vehicle Communication (IVC) networks, the high mobility and lack of infrastructure pose major challenges in designing secure routing... Sample PDF
Network Setup for Secure Routing in Inter-Vehicle Communication Networks
Chapter 19
Antonios Alexiou, Christos Bouras, John Papagiannopoulos, Dimitrios Primpas
This chapter presents the design principles that cover the implementation of broadband infrastructure in the region of Western Greece, by examining... Sample PDF
Metropolitan Broadband Networks: Design and Implementation Aspects, and Business Models
About the Contributors