Algorithms for Reducing Cell Sites while Maintaining Coverage During a Network Overlay of a Technology Upgrade

The development of newer generations of technology has created the opportunity and need for wireless providers to upgrade their networks (e.g. 2G to 3G), while market forces require them to maximize the use of their capital and preexisting investments. Upgrades in technology not only offer additional services but also performance enhancements which give the operator the opportunity to achieve comparable network wide coverage with fewer cells. We propose a simple yet novel algorithm for choosing those cells that can be deleted during such an upgrade, and compare its performance and speed to other algorithms used to address related combinatorial optimization problems. We present an intuitive example to demonstrate the role of inhomogeneity in network performance, and show how the opportunities for cell deletion increase with the amount of network inhomogeneity; in addition we apply these algorithms to a realistic network and compare their performance.