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.
TopIntroduction
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).