Assign ranges in general ad-hoc networks

In this paper we theoretically study the MINIMUM RANGE ASSIGNMENT problem in static ad-hoc networks with arbitrary structure, wherethe transmission distances can violate triangle inequality. We consider two versions of the MINIMUM RANGE ASSIGNMENT problem, wherethe communication graph has to fulfill either the h-strong connectivity condition (MIN-RANGE(h-SC)) or the h-broadcast condition (MINRANGE(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, wepresent probabilistic O(log n)-approximation algorithms for MIN-RANGE(h-SC) and MIN-RANGE(h-B), which improves the previous bestratios O(log n log log n) and O(n² log n log log n), respectively [D. Ye, H. Zhang, The range assignment problem in static ad-hoc networkson metric spaces, Proceedings of the 11th Colloquium on Structural Information and Communication Complexity, Sirocco 2004, Lecture Notesin Computer Science, vol. 3104, pp. 291–302]. The result for MIN-RANGE(h-B) matches the lower bound [G. Rossi, The range assignmentproblem in static ad-hoc wireless networks. Ph.D. Thesis, 2003] for the case that triangle inequality for transmission distance holds (which isa special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient is sufficientlysmall, the approximation ratio is improved to O((log log n)^α). Finally we discuss the applications of our algorithms in mobile ad-hoc networks.