Transmitting Range Assignments Using Steiner Tree in Ad Hoc Wireless Networks

In this paper, we discuss the problem of assigning transmitting ranges and establishing connectivity in ad hoc wireless networks from the practical perspective. That is, setup a communication links by introducing extraneous nodes to the network in the emergencies. Furthermore, transmitting ranges of nodes must be assigned in such a way that the energy cost is minimum. The main contribution of this work is the O(N log N) algorithm to add relay nodes to the network and 2-approximation to assign transmitting ranges of nodes (original and relay). The output of the algorithm is the minimal Steiner tree on the graph consists of terminal (original) nodes and relay (additional) nodes. The output of approximation is the range assignments to the nodes. The paper also analyzed the complexity and established the correctness of the proposed algorithm.