An efficient heuristic algorithm for 2D h-hops range assignment problem

Given a set S of n radio-stations on a 2D plane and an integer h, the range assignment problem is to assign ranges to the members in S such that each member of S can communicate with all other members in S using at most h hops, and the sum of powers required for all the members in S is minimized. The general 2D h-hop range assignment problem is known to be NP-hard (A.E.F. Clementi et al, Proc. Symp. on Theor. Aspects of Comp. Sci. (STACS-00), pp. 651-660, 2000). We first consider some simplified variations of the problem and propose an efficient polynomial time algorithm for obtaining optimal solution. In the homogeneous version, where the range assigned to each radio-station is same (ρ), we can obtain the minimum value of ρ in O(n³logn) time in the worst case. In addition, if we consider the unbounded version of the homogeneous range assignment problem (i.e. h=n-1), then the optimal value of ρ can be obtained in O(n²logn) time. Finally, we propose an efficient heuristic algorithm for the general h-hop range assignment problem in 2D, where the range of the radio stations may not be equal. Experimental results demonstrate that our heuristic algorithm runs fast and produces near-optimal solutions on randomly generated instances.