检索结果-内蒙古大学图书馆

Energy Efficient Monitoring in Sensor Networks

algorithmICA 2011年第1期59卷 94-114页

作者： Deshpande, Amol Khuller, Samir Malekian, Azarakhsh Toossi, Mohammed Univ Maryland Dept Comp Sci College Pk MD 20742 USA Google Mountain View CA USA

We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice. We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in alpha different sets (time-slots). This means that the battery life is extended by a factor of k/alpha, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation

关键词： algorithms Complexity approximation algorithm Sensor networks Energy efficiency Target monitoring

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant routing: k-inconnected many-to-one routing in wireless networks

引用

THEORETICAL COMPUTER SCIENCE 2011年第3期412卷 209-216页

作者： Li, Deying Wang, Yuexuan Zhu, Qinghua Yang, Huiqiang Renmin Univ China Key Lab Data Engn & Knowledge Engn MOE Beijing Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

This paper addresses the problem of fault-tolerant many-to-one routing in static wireless networks with asymmetric links, which is important in both theoretical and practical aspects. The problem is to find a minimum energy subgraph for a given subset and a destination node such that there are k node-disjoint paths from each node in the subset to the destination node in the subgraph. Firstly, we prove that the problem is NP-hard, and then propose two approximation algorithms: the minimum weight k node-disjoint paths based (MWkNDPB) algorithm and the minimum energy k node-disjoint paths based (MEkNDPB) algorithm. Extensive simulations have been conducted to show that proposed algorithms are efficient. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Wireless networks Fault-tolerant k-inconnected many-to-one routing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第3期412卷 198-208页

作者： Zou, Feng Wang, Yuexuan Xu, Xiao-Hua Li, Xianyue Du, Hongwei Wan, Pengjun Wu, Weili Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +epsilon)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +epsilon)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +epsilon)-approximation algorithm for an MWCDS. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum-weighted dominating set Minimum-weighted connected dominating set Minimum-weighted chromatic disk cover Node-weighted Steiner tree Polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT

引用

SIAM JOURNAL ON COMPUTING 2011年第6期40卷 1740-1766页

作者： Calinescu, Gruia Chekuri, Chandra Pal, Martin Vondrak, Jan IIT Dept Comp Sci Chicago IL 60616 USA Univ Illinois Dept Comp Sci Urbana IL 61801 USA Google Inc New York NY 10018 USA IBM Almaden Res Ctr San Jose CA 95120 USA

Let f : 2(X) -> R+ be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem max(S is an element of I)f(S). It is known that the greedy algorithm yields a 1/2-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8 (1978), pp. 73-87] for this problem. For certain special cases, e. g., max(|S|<= k)f(S), the greedy algorithm yields a (1 - 1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f(S) for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3 (1978), pp. 177-188] and for explicitly posed instances assuming P not equal NP [U. Feige, J. ACM, 45 (1998), pp. 634-652]. In this paper, we provide a randomized (1 - 1/e)-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8 (2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrak, Proceedings of the 38th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case;although the reduction requires |X| to be exponential in the original problem size, we are able to achieve a (1 - 1/e - o(1))-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints.

关键词： monotone submodular set function matroid social welfare generalized assignment problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Estimation of parameters of motion of a moving sound source by digital processing of a set of Doppler-shifted underwater acoustic signals

引用

ACOUSTICAL PHYSICS 2011年第4期57卷 490-495页

作者： Getmanov, V. G. Firsov, A. A. Natl Res Nucl Univ MEPhI Moscow 115409 Russia

A method is proposed for estimating the parameters of motion of a moving sound source on the basis of digital processing of Doppler-shifted underwater acoustic signals received by a set of hydrophones. A two-step approximation algorithm is used. An example of implementing the method of estimating the parameters of motion is presented for a two-hydrophone receiving system. Errors in estimating the parameters by means of the proposed method are considered.

关键词： Doppler underwater acoustic signals digital processing approximation algorithm estimating the parameters of motions

来源：评论

学校读者我要写书评

暂无评论

Size-constrained tree partitioning: Approximating the multicast k-tree routing problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第3期412卷 240-245页

作者： Cai, Zhipeng Goebel, Randy Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In the multicast k-tree routing problem, a data copy is sent from the source node to at most k destination nodes in every transmission. The goal is to minimize the total cost of sending data to all destination nodes, which is measured as the sum of the costs of all routing trees. This problem was formulated out of optical networking and has applications in general multicasting. Several approximation algorithms, with increasing performance, have been proposed in the last several years;the most recent ones rely heavily on a tree partitioning technique. In this paper, we present a further improved approximation algorithm along the line. The algorithm has a worst-case performance ratio of 5/4 rho + 3/2, where rho denotes the best approximation ratio for the Steiner minimum tree problem. The proofs of the technical routing lemmas also provide some insights into why such a performance ratio could be the best possible that one can get using this tree partitioning technique. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Capacitated multicast tree routing approximation algorithm Tree partitioning

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2007年第3期18卷 565-591页

作者： Soper, Alan J. Strusevich, Vitaly A. Univ Greenwich Sch Comp & Math Sci London SE10 9LS England

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a 3/2-approximation algorithm that outputs a two-shipment schedule. We design a 4/3-approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

关键词： flow shop scheduling scheduling with transportation approximation algorithm linear relaxation

来源：评论

学校读者我要写书评

暂无评论

Conflict-free Many-to-One Data Aggregation Scheduling in Multi-channel Multi-hop Wireless Sensor Networks

Conflict-free Many-to-One Data Aggregation Scheduling in Mul...

引用

IEEE International Conference on Communications (ICC)

作者： Li, Deying Zhu, Qinghua Du, Hongwei Wu, Weili Chen, Hong Chen, Wenping Renmin Univ China Sch Informat Beijing 100872 Peoples R China Shenzhen Grad Sch Harbin Inst Technol Dept Comp Sci Technol Harbin Peoples R China Univ Texas Dallas Dept Comp Sci Dallas TX USA

ISBN: (纸本)9781612842332

In this paper, we studied the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: Given locations of all sensors and a base station, some sensors which are called as sources, find a schedule such that data from all sources can be transmitted to the base station without any conflict and the latency is minimized. In this model, each sensor has three parameters which are transmission range r, interference range alpha r and carrier sensing range beta r where alpha, and beta are constant. There are lambda >= 1 available channels for communications. We designed an approximation algorithm with ratio (inverted right perpendicular a/lambda inverted left perpendicular + 11 inverted right perpendicular b/lambda inverted left perpendicular). This work improves our previous work [9] when lambda = 1. Extensive simulations evaluate the performance of the algorithm.

关键词： conflict-free data aggregation latency multi-channel approximation algorithm sensor networks

来源：评论

学校读者我要写书评

暂无评论

Size-constrained tree partitioning: Approximating the multicast k-tree routing problem

Size-constrained tree partitioning: Approximating the multic...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Cai, Zhipeng Goebel, Randy Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

关键词： Capacitated multicast tree routing approximation algorithm Tree partitioning

来源：评论

学校读者我要写书评

暂无评论

Maximising Lifetime for Fault-Tolerant Target Coverage in Sensor Networks 11

Maximising Lifetime for Fault-Tolerant Target Coverage in Se...

引用

23rd Annual Symposium on Parallelism in algorithms and Architectures

作者： Erlebach, Thomas Grant, Tom Kammer, Frank Univ Leicester Dept Comp Sci Leicester LE1 7RH Leics England

ISBN: (纸本)9781450307437

We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events. Here, a composite event is the simultaneous occurrence of a combination of atomic events, such as the detection of smoke and high temperature. We are given sensor nodes that have an initial battery level and can monitor certain event types, and a set of points at which composite events need to be detected. The points and sensor nodes are located in the Euclidean plane, and all nodes have the same sensing radius. The goal is to compute a longest activity schedule with the property that at any point in time, each event point is monitored by at least two active sensor nodes. We present a (6 + epsilon)-approximation algorithm for this problem by devising an approximation algorithm with the same ratio for the dual problem of minimising the weight of a fault-tolerant sensor cover and applying the Garg-Konemann algorithm. Our algorithm for the minimum-weight fault-tolerant sensor cover problem generalises previous approximation algorithms for geometric set cover with weighted unit disks and is obtained by enumerating properties of the optimal solution that guide a dynamic programming approach.

关键词： approximation algorithm unit disk graph set multi-cover dynamic programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：