Network Lifetime and Power Assignment in ad hoc Wireless Networks
Network Lifetime and Power Assignment in ad hoc Wireless Networks
复制标题
自组织无线网络中的网络生命周期和功率分配
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
A. Zelikovsky
中科院分区：
文献类型：
--
作者：
G. Călinescu;S. Kapoor;Alexander Olshevsky;A. Zelikovsky
用于自组织无线网络拓扑控制的功率分配是一类问题，每个问题由一定的连通性约束（如强连通性）定义，输入由一个有向完全加权图G=(V,c)组成。有向生成子图H中顶点u的幂由PH (u) = max uv∈E(H) c（uv）给出。H的幂由(p（H) = sum_{u in v}p{sc H}(u)）给出，幂分配寻求在H满足给定连通性约束的情况下最小化p(H)。我们提出了三个幂分配问题的渐近最优O（log n）逼近算法：最小幂强连通性，最小幂对称连通性（具有边uv的无向图，如果H同时具有uv和vu，则必须连通）和最小幂广播（输入也有r∈V，并且H必须是r根的外向生成树形）。
Used for topology control in ad-hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity) The input consists of a directed complete weighted graph G=(V,c). The power of a vertex u in a directed spanning subgraph H is given by PH (u) = max uv ∈ E(H) c(uv). The power of H is given by (p(H) = sum_{u in v}p{sc H}(u)), Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint. We present asymptotically optimal O(log n)-approximation algorithms for three Power Assignment problems: Min-Power Strong Connectivity, Min-Power Symmetric Connectivity (the undirected graph having an edge uv iff H has both uv and vu must be connected) and Min-Power Broadcast (the input also has r ∈ V , and H must be a r-rooted outgoing spanning arborescence).