Tuesday, 13:45 - 14:10 h, Room: H 3002


Pedro Moura
Generalized degree constraints arising in wireless networks problems

Coauthors: Luís Gouveia, Amaro de Sousa


We describe a minimum spanning tree problem with generalized degree constraints which arises in the design of wireless networks. In these networks, each link is implemented through a point-to-point wireless transmission system composed by a transmitter/receiver antenna and a signal processing unit at each side of the link. Each system works on different frequency channels chosen from a limited set of available channels. Possible overlapping may occur in a node, i.e., part of the transmitted signal on one channel is added as interference on the received signal on another channel. Due to propagation effects, the signal strength on the receiver side decreases as the distance to the transmitter side increases. Therefore, the maximum distance between antennas that allow the link to work properly, depends on the amount of interference introduced by all the frequency channels used on its end nodes
We consider different types of links that may be installed between two nodes depending on the distance between them and their degrees. We propose three models and compare the linear programming relaxations. We also test these models against a set of instances with up to 100 nodes.


Talk 2 of the invited session Tue.2.H 3002
"Tree problems" [...]
Cluster 23
"Telecommunications & networks" [...]


  The system of instant Virginia Payday Loans allows any adult U.S. citizen. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.