Abstract
In the thesis, we consider the Directed Weighted Degree Constrained Network Design (DWDCN) problem and its applications to Maximum Network Lifetime (MNL) problems in wireless ad-hoc networks.The goal of the DWDCN problem is to find a minimum-cost subgraph satisfying the specified connectivity requirements and the specified degree bounds. This problem has many variants, depending on the type of the connectivity requirements and on the type of the degree bounds. We consider a general case when the connectivity requirements are defined by an intersecting or crossing supermodular set function and the degree bounds are defined for the out-degrees of nodes or for the in-degrees or both. Since most of the DWDCN problems are known to be NP-hard, we consider approximation algorithms. While requiring that all connectivity constraints are (strictly) satisfied, we allow approximation of both the total cost and the degree bounds. More specifically, an (α,β) bi-criteria approximation algorithm for an DWDCN problem computes in polynomial time a subgraph which satisfies the connectivity requirements but may violate the optimality of the cost by a factor α and degree bounds by a factor β. We improve a number of previous (α,β)-approximation bounds, for example, we show a (2,5)-approximation bound for the DWDCN problem with out-degree constraints and connectivity requirements defined by an intersecting supermodular function. The previous best bounds were (2,7) and (3,6)-approximations.
One application of the DWDCN algorithm is to solve the MNL problem. In an MNL problem, we are given a wireless ad-hoc network with an edge-weight function representing the energy costs of individual transmissions, and a node function representing the initial energy of nodes. The communication tasks we consider are unicast, broadcast, convergecast and mixedcast. The goal is to compute a schedule of individual transmissions to perform a specified communication task as many times as possible before the energy of the nodes is depleted. Using our approximation bounds for DWDCN problems, we improve the previous approximation algorithms for MNL problems. For example, we show a polynomial time algorithm which computes a schedule allowing ⌊kopt/5⌋ rounds of broadcasting, where kopt is the optimal number of rounds. This improves the previous best approximation bound of ⌊kopt/36⌋.
We also conduct experimental evaluation of the considered MNL approximation algorithms, comparing the quality of the computed solutions with upper bounds and with solutions obtained by heuristics.
| Date of Award | 2016 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Tomasz Radzik (Supervisor) & Colin Cooper (Supervisor) |