Repositório Institucional da Universidade de Aveiro > Departamento de Electrónica, Telecomunicações e Informática > DETI - Comunicações >
 Spanning trees with generalized degree constraints arising in the design of wireless networks
Please use this identifier to cite or link to this item http://hdl.handle.net/10773/5192

title: Spanning trees with generalized degree constraints arising in the design of wireless networks
authors: Gouveia, Luís
Moura, Pedro
Sousa, Amaro de
issue date: Jun-2011
publisher: Springer
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.
URI: http://hdl.handle.net/10773/5192
ISBN: 978-3-642-21526-1
ISSN: 0302-9743
source: International Network Optimization Conference
appears in collectionsDETI - Comunicações

files in this item

file description sizeformat
GouveiaMouraSousa_final.pdfVersão post-print38.16 kBAdobe PDFview/open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! RCAAP OpenAIRE DeGóis
ria-repositorio@ua.pt - Copyright ©   Universidade de Aveiro - RIA Statistics - Powered by MIT's DSpace software, Version 1.6.2