Solving a minimum-power covering problem with overlap constraint for cellular network design
2010 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 203, no 3, 714-723 p.Article in journal (Refereed) Published
We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.
Place, publisher, year, edition, pages
2010. Vol. 203, no 3, 714-723 p.
OR in telecommunications; Cellular networks; Covering; Integer programming; Tabu search
National CategoryEngineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-52895DOI: 10.1016/j.ejor.2009.09.018OAI: oai:DiVA.org:liu-52895DiVA: diva2:285763
Original Publication: Lei Chen and Di Yuan, Solving a minimum-power covering problem with overlap constraint for cellular network design, 2010, European Journal of Operational Research, (203), 3, 714-723. http://dx.doi.org/10.1016/j.ejor.2009.09.018 Copyright: Elsevier Science B.V., Amsterdam. http://www.elsevier.com/2010-01-132010-01-122013-03-04