Affiliations: Department of Computer Science, Kent State University,
Kent, OH, USA. Tel.: +1 330 6722074; Fax: +1 330 672 0737; E-mail:
rmuhamma@cs.kent.edu
Abstract: This paper describes an efficient method for introducing relay nodes
in the given communication graph. Our algorithm assigns transmitting ranges to
the nodes such that the cost of range assignment function is minimal over all
connecting range assignments in the graph. The main contribution of this paper
is the O(N log N) algorithm to add relay nodes to the
wireless communication network and 2-approximation to assign transmitting
ranges to nodes (original and relay). It does not assume that communication
graph to be a unit disk graph. 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.
Keywords: Connectivity, range assignment, steiner tree, and approximation