Minimizing the maximum Interference in k-connected wireless networks
| dc.contributor.author | Mehrpour, Sahar | |
| dc.contributor.examiningcommittee | Li, Ben (Computer Science) Arino, Julien (Mathematics) | en_US |
| dc.contributor.supervisor | Durocher, Stephane (Computer Science) | en_US |
| dc.date.accessioned | 2016-09-21T14:48:10Z | |
| dc.date.available | 2016-09-21T14:48:10Z | |
| dc.date.issued | 2016 | |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| dc.description.abstract | Given a set P of n points in R^d, we consider the k-connected interference minimization problem, in which the objective is to assign a transmission radius to each node in P such that the resulting network is k-connected and the maximum interference is minimized. We show for any n and any 1 <= k < n, Omega(sqrt(kn)) and Omega(k log n) are lower bounds on the worst-case minimum maximum interference in the symmetric and asymmetric models, respectively. In the symmetric case, we present polynomial-time algorithms that build a k-connected network on any given set of n nodes with interference O(sqrt(kn)) in one dimension and O(min{k sqrt(n), k log lambda}) in two dimensions, where lambda denotes the ratio of the longest to shortest distances between any pair of nodes. In the asymmetric case, we present a polynomial-time algorithm that builds a strongly k-connected network with maximum interference O(k log lambda) in two dimensions. | en_US |
| dc.description.note | October 2016 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/31845 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| dc.subject | Wireless networks | en_US |
| dc.subject | K-connectivity | en_US |
| dc.subject | Topology control | en_US |
| dc.subject | Interference minimization | en_US |
| dc.title | Minimizing the maximum Interference in k-connected wireless networks | en_US |
| dc.type | master thesis | en_US |