Abstract
In this thesis we look at various problems in wireless networking. First we consider two problems in physicalmodel networks. We introduce a new model for localisation. The model is based on a rangefree model of radio transmissions. The first scheme is randomised and we analyse its expected performance. Then we introduce the concept of a splitline schedule. We conjecture that a certain class of schedules (the regular schedules) is optimal. We prove this for some restricted cases, but the general case remains open. Then we introduce the reversebinary schedule and prove that it is within a constant factor of optimal.
Next we consider the scheduling of wireless transmissions. We give an exact exponentialtime algorithm for the Link Independent Set problem. Its branching rules are valid for arbitrary gain matrices, but designed to take advantage of the structure available in geometric instances. We prove a worstcase bound of O*(1.888^n) on the runtime of the algorithm, but only under an assumption on the input. Next we experimentally demonstrate that this assumption is reasonable for random geometric instances and that, in fact, the effective branching factor of the algorithm is expected to be much better than 1.888 on such instances. Finally we show that density is a meaningful structural parameter: experiments as well as theory tell us that the size of the optimal link independent set is closely tied the density of the instance.
After these results for physicalmodel networks, we turn our attention to graphs. We introduce a model of recoverable routing in the presence of node failures. The model is based on the concept of backup nodes: for every node in the network, we assign a backup node that will take over in case the original node fails. These backup nodes are used to fix a route easily and locally. We resolve the basic algorithmic and complexityrelated questions about this problem: some variants are polynomialtime solvable and others are NPcomplete. For the former we give an O(n^4)time algorithm. We give nontrivial exponentialtime algorithms for the hard cases of the problem. Then we look at a variant of the problem where the basic path is given and we are merely asked to pick which node is backed up by which other node. Again we see that the problem has variants that are polynomialtime solvable and variants that are NPcomplete. We give algorithms for all variants.
Lastly, we look at a problem of energyefficient data gathering in wireless sensor networks. We formalise a version of this problem and call it energyconstrained flow. We study, in particular, the integer version of the problem. We prove NPhardness and hardness of approximation in various settings. Among other results, we show that the problem is strongly NPcomplete on geometric configurations on a line. After these mostlynegative results, we present a column generation algorithm for the fractional relaxation of energyconstrained flow. It performs well and we demonstrate experimentally that this approach also leads to an effective heuristic for the integer problem. We finish the thesis with two algorithms with advantage, improving the best known approximation factor when restricted to stplanar networks.
Next we consider the scheduling of wireless transmissions. We give an exact exponentialtime algorithm for the Link Independent Set problem. Its branching rules are valid for arbitrary gain matrices, but designed to take advantage of the structure available in geometric instances. We prove a worstcase bound of O*(1.888^n) on the runtime of the algorithm, but only under an assumption on the input. Next we experimentally demonstrate that this assumption is reasonable for random geometric instances and that, in fact, the effective branching factor of the algorithm is expected to be much better than 1.888 on such instances. Finally we show that density is a meaningful structural parameter: experiments as well as theory tell us that the size of the optimal link independent set is closely tied the density of the instance.
After these results for physicalmodel networks, we turn our attention to graphs. We introduce a model of recoverable routing in the presence of node failures. The model is based on the concept of backup nodes: for every node in the network, we assign a backup node that will take over in case the original node fails. These backup nodes are used to fix a route easily and locally. We resolve the basic algorithmic and complexityrelated questions about this problem: some variants are polynomialtime solvable and others are NPcomplete. For the former we give an O(n^4)time algorithm. We give nontrivial exponentialtime algorithms for the hard cases of the problem. Then we look at a variant of the problem where the basic path is given and we are merely asked to pick which node is backed up by which other node. Again we see that the problem has variants that are polynomialtime solvable and variants that are NPcomplete. We give algorithms for all variants.
Lastly, we look at a problem of energyefficient data gathering in wireless sensor networks. We formalise a version of this problem and call it energyconstrained flow. We study, in particular, the integer version of the problem. We prove NPhardness and hardness of approximation in various settings. Among other results, we show that the problem is strongly NPcomplete on geometric configurations on a line. After these mostlynegative results, we present a column generation algorithm for the fractional relaxation of energyconstrained flow. It performs well and we demonstrate experimentally that this approach also leads to an effective heuristic for the integer problem. We finish the thesis with two algorithms with advantage, improving the best known approximation factor when restricted to stplanar networks.
Original language  English 

Awarding Institution 

Supervisors/Advisors 

Award date  3 Dec 2014 
Publisher  
Print ISBNs  9789090286846 
Publication status  Published  3 Dec 2014 
Keywords
 nonverbal predication
 copular clauses
 raising
 agreement
 casemarking
 BE and HAVE