Variations of base-station placement problem on the boundary of a convex region
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 + epsilon)-factor approximation result in O((n + k)log(n + k) + nlog([1/epsilon])) 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.
complexity base station placement wireless network covering problem approximation algorithm