Spanning trees with generalized degree constraints arising in the design of wireless networks

Abstract

In this paper we describe a minimum spanning tree problem with generalized degree constraints which arises in the design of wireless networks. The signal strength on the receiver side of a wireless link decreases with the distance between transmitter and receiver. In order to work properly, the interference on the receiving part of the link must be under a given threshold. In order to guarantee this constraint, for each node we impose a degree constraint that depends on the ”length” of the links adjacent to the corresponding node, more precisely, nodes adjacent to long links must have a smaller degree and vice-versa. The problem is complicated by considering different signal strengths for each link. Increasing the strength in a link increases the cost of the link. However, it also reduces the maximum allowed degree on its end nodes. We create two models using adequate sets of variables, one may be considered an extended version of the other, and relate, from a theoretical perspective, the corresponding linear programming relaxations.