查看文章

In this paper we consider a constrained version of the range assignment problem for wireless ad hoc networks, where the value the node transmitting ranges must be assigned in such a way that the resulting communication graph is strongly connected and the energy cost is minimum. We impose the further requirement of symmetry on the resulting communication graph. We also consider a weaker notion of symmetry, in which only the existence of a set of symmetric edges that renders the communication graph connected is required. Our interest in these problems is motivated by the fact that a (weakly) symmetric range assignment can be more easily integrated with existing higher and lower-level protocols for ad hoc networks, which assume that all the nodes have the same transmitting range. We show that imposing symmetry does not change the complexity of the problem, which remains NP-hard in two …