On minimizing the total power of <Emphasis Type="Italic">k</Emphasis>-strongly connected wireless networks |
| |
Authors: | Hanan Shpungin Michael Segal |
| |
Affiliation: | (1) Computer Sciences Department, Ben Gurion University of the Negev, Beer-Sheva, Israel;(2) Communication Systems Engineering Department, Ben Gurion University of the Negev, Beer-Sheva, Israel |
| |
Abstract: | Given a wireless network, we want to assign each node a transmission power, which will enable transmission between any two
nodes (via other nodes). Moreover, due to possible faults, we want to have at least k vertex-disjoint paths from any node to any other, where k is some fixed integer, depending on the reliability of the nodes. The goal is to achieve this directed
k-strong connectivity with a minimal overall power assignment. The problem is NP-Hard for any k ≥ 1 already for planar networks. Here we first present an optimal power assignment for uniformly spaced nodes on a line for
any k ≥ 1. We also prove a number of useful properties of power assignment which are also of independent interest. Based on it,
we design an approximation algorithm for linear radio networks with factor
min{2,(\frac \Updelta d)a },\hbox{min}\left\{2,\left(\frac {\Updelta} {\delta}\right)^\alpha \right\}, where Δ and δ are the maximal and minimal distances between adjacent nodes respectively and parameter α ≥ 1 being the distance-power
gradient. We then extend it to the weighted version. Finally, we develop an approximation algorithm with factor O(k
2), for planar case, which is, to the best of our knowledge, the first non-trivial result for this problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|