VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION

Abstract

This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by at least one base station. We name this problem as region-cover(k) problem. A simplified form of this problem is the vertex-cover(k) problem, where the objective is to communicate with only the vertices of P instead of covering the entire polygon. We first present efficient algorithms for vertex-cover(2) and region-cover(2) problems, where the base stations are to be installed on a pair of specified edges. The time complexity of these algorithms are O(n log n) and O(n 2 ) respectively, where n is the number of vertices in the polygon P. Next, we consider the case where k ≥ 3. We first concentrate on a restricted version of the vertex-cover(k) and region-cover(k) problems, where all the k base stations are to be installed on the same edge of P. Our proposed algorithm for the restricted vertex-cover(k) problem produces optimum result in O(min(n 2 ,nk log n)) time, whereas the algorithm for the restricted region-cover(k) problem produces an (1 + ∊)-factor approximation result in [Formula: see text] time. Finally, we propose efficient heuristic algorithm for the unrestricted version of the region-cover(k) problem for k ≥ 3. Experimental results demonstrate that our proposed algorithm runs fast and produces near optimum solutions.