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

Efficient event handling in Wireless Sensor and Actor Networks: An on-line computation approach

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS 2016年第0期75卷 181-199页

作者： Konstantopoulos, Charalampos Pantziou, Grammati Venetis, Ioannis E. Gavalas, Damianos Univ Piraeus Dept Informat Piraeus Greece Technol Educ Inst Athens Dept Informat Athens Greece Univ Aegean Dept Cultural Technol & Commun Mitilini Greece

The real time response of actors to events occurring in a network area is of critical importance in Wireless Sensor and Actor Networks (WSANs). This in turn requires fast notification of actors from Sensor Nodes (SNs) about events as well as effective coordination of actors for prompt event handling. In this paper, we introduce an on-line distributed protocol for event handling in a WSAN. Existing techniques usually select actors nearby the current event for handling it. However, this greedy approach may eventually lead to a slow response to events because it does not consider the spatial distribution that future events might have. In contrast, in order to cater for future events, the proposed solution probabilistically selects actors for event handling, allowing distant actors to be selected as well. This randomized approach guarantees fast average responsiveness to events, a balanced energy consumption among actors and low energy consumption for SNs. These merits have also been confirmed in the experimental results where the performance of the proposed approach has also been evaluated. In addition, the event-handling scheme presented in this work features efficient distributed algorithms for sensor to actor and actor to actor coordination which are of independent interest. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Wireless sensor and actor networks on-line algorithms k-Server problem Routing

来源：评论

学校读者我要写书评

暂无评论

LRU is better than FIFO

引用

ALGORITHMICA 1999年第2期23卷 180-185页

作者： Chrobak, M Noga, J Univ Calif Riverside Dept Comp Sci Riverside CA 92521 USA Univ Calif Riverside Dept Math Riverside CA 92521 USA

In the paging problem we have to manage a two-level memory system, in which the first level has short access time but can hold only up to k pages, while the second level is very large but slow. We use competitive analysis to study the relative performance of the two best known algorithms for paging, LRU and FIFO. Sleator and Tarjan proved that the competitive ratio of LRU and FIFO is k. In practice, however, LRU is known to perform much better than FIFO. It is believed that the superiority of LRU can be attributed to locality of reference exhibited in request sequences. In order to study this phenomenon, Borodin et al. [2] refined the competitive approach by introducing the concept of access graphs. They conjectured that the competitive ratio of LRU on each access graph is less than or equal to the competitive ratio of FIFO. We prove this conjecture in this paper.

关键词： paging caching on-line algorithms competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line edge-coloring with a fixed number of colors

引用

ALGORITHMICA 2003年第2期35卷 176-191页

作者： Favrholdt, LM Nielsen, MN Department of Mathematics and Computer Science University of Southern Denmark Campusvej 55 DK-5230 Odense M Denmark. lenem@imada.sdu.dk nyhave@imada.sdu.dk. DK

We investigate a variant of on-line edge-coloring in which there is a fixed number of colors available and the aim is to color as many edges as possible. We prove upper and lower bounds on the performance of different. classes of algorithms for the problem. Moreover, we determine the performance of two specific algorithms, First-Fit and Next-Fit. Specifically, algorithms that never reject edges that they are able to color are called fair algorithms. We consider the four combinations of fair/not fair and deterministic/randomized. We show that the competitive ratio of deterministic fair algorithms can vary only between approximately 0.4641 and (1)/(2), and that Next-Fit is worst possible among fair algorithms. Moreover, we show that no algorithm is better than (4)/(7)-competitive. If the graphs are all k-colorable, any fair algorithm is at least (1)/(2)-competitive. Again, this performance is matched by Next-Fit while the competitive ratio for First-Fit is shown to be k/(2k - 1), which is significantly better, as long as k is not too large.

关键词： edge-coloring on-line algorithms competitive analysis fixed number of colors maximization problem fair algorithms k-colorable graphs accommodating sequences restricted adversary randomization

来源：评论

学校读者我要写书评

暂无评论

Fair versus unrestricted bin packing

引用

ALGORITHMICA 2002年第2期34卷 181-196页

作者： Azar, Y Boyar, J Epstein, L Favrholdt, LM Larsen, KS Nielsen, MN Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ So Denmark Dept Math & Comp Sci Odense Denmark Interdisciplinary Ctr Sch Comp & Media Sci Herzliyya Israel

We consider the on-line Dual Bin Packing problem where we have n unit size bins and a sequence of items. The goal is to maximize the number of items that are packed in the bins by an on-line algorithm. We investigate unrestricted algorithms that have the power of performing admission control on the items, i.e., rejecting items while there is enough space to pack them, versus fair algorithms that reject an item only when there is not enough space to pack it. We show that by performing admission control on the items, we get better performance compared with the performance achieved on the fair version of the problem. Our main result shows that with an unfair variant of First-Fit, we can pack approximately two-thirds of the items for sequences for which an optimal off-line algorithm can pack all the items. This is in contrast to standard First-Fit where we show an asymptotically tight hardness result: if the number of bins can be chosen arbitrarily large, the fraction of the items packed by First-Fit comes arbitrarily close to five-eighths.

关键词： on-line algorithms competitive analysis bin packing dual bin packing restricted adversaries randomization admission control

来源：评论

学校读者我要写书评

暂无评论

On an on-line scheduling problem for parallel jobs

引用

INFORMATION PROCESSING LETTERS 2002年第6期81卷 297-304页

作者： Naroska, E Schwiegelshohn, U Univ Dortmund Comp Engn Inst D-44221 Dortmund Germany

This paper addresses the non-preemptive on-line scheduling of parallel jobs. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2 - 1/m for the makespan if m identical machines are available and if each job requires only a single machine for processing. Here, we show that the same factor also holds in the case of parallel jobs. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms analysis of algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

Online scheduling of weighted equal-length jobs with hard deadlines on parallel machines

引用

COMPUTERS & OPERATIONS RESEARCH 2011年第8期38卷 1103-1108页

作者： Krumke, Sven O. Taudes, Alfred Westphal, Stephan Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany Vienna Univ Econ & Business Adm Inst Prod Management Vienna Austria

We consider the problem of scheduling a maximum profit selection of equal length jobs on m identical machines. Jobs arrive online over time and the goal is to determine a non-preemptive schedule which maximizes the total profit of the scheduled jobs. Let the common processing requirement of the jobs be p > 0. For each job j(i), i = 1,...,n we are given a release time r(i) (at which the job becomes known) and a deadline r(i)+p+delta(i). If the job is scheduled and completed before the deadline, a profit of w(i) is earned. Upon arrival of a new job, an online algorithm must decide whether to accept the job or not. In case of acceptance, the online algorithms must provide a feasible starting date for the job. Competitive analysis has become a standard way of measuring the quality of online algorithms. For a maximization problem, an online algorithm is called c-competitive, if on every input instance it achieves at least a 1/c-fraction of the optimal ("offline") profit. We give lower bounds for the competitivity of online algorithms and propose algorithms which match this lower bound up to a constant factor. (C) 2010 Published by Elsevier Ltd.

关键词： Revenue management Scheduling on-line algorithms Competitiveness

来源：评论

学校读者我要写书评

暂无评论

Scheduling uniform machines on-line requires nondecreasing speed ratios

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 225-234页

作者： Vestjens, APA Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands

We consider the following on-line scheduling problem. We have to schedule n independent jobs, where n is unknown, on m uniform parallel machines so as to minimize the makespan;preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand;its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, there exists an algorithm that solves the problem if and only if s(i-1)/s(i) less than or equal to s(i)/s(i+1) for all i = 2,..., m - 1, where s(i) denotes the ith largest machine speed. We also show that if this condition is satisfied, then Ci(mn) preemptions are necessary, and we provide an example to show that this bound is tight. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： on-line algorithms preemptive scheduling uniform machines

来源：评论

学校读者我要写书评

暂无评论

Dynamic trees and dynamic point location

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 612-636页

作者： Goodrich, MT Tamassia, R Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Brown Univ Dept Comp Sci Providence RI 02912 USA

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision. The main approach is based on the maintenance of two interlaced spanning trees, one for and one S for the graph-theoretic planar dual of. Queries are answered by using a centroid decomposition S of the dual tree to drive searches in the S primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 26 (1983), pp. 362-381], leading to a scheme that achieves vertex insertion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n+k) time, and answers queries in O(log(2) n) time, with O(n) space, where n is the current size of subdivision S. The techniques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addition, the interlaced-tree approach is applied to on-line point location (where one builds incrementally), improving the query bound to O(log n log log n) time and the update bounds to O(1) S amortized time in this case. This appears to be the first on-line method to achieve a polylogarithmic query time and constant update time.

关键词： computational geometry point location centroid decomposition dynamic data structures on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Visibility-based pursuit-evasion in an unknown planar environment

引用

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH 2004年第1期23卷 3-26页

作者： Sachs, S LaValle, SM Rajko, S Univ Illinois Dept Comp Sci Urbana IL 61801 USA Iowa State Univ Dept Comp Sci Ames IA 50011 USA

We address an on-line version of the visibility-based pursuit-evasion problem. We take a minimalist approach in modeling the capabilities of a pursuer robot. A point pursuer moves in an unknown, simply-connected, piecewise-smooth planar environment, and is given the task of locating any unpredictable, moving evaders that have unbounded speed. The evaders are assumed to be points that move continuously. To solve the problem, the pursuer must for each target have an unobstructed view of it at some time during execution. The pursuer is equipped with a range sensor that measures the direction of depth discontinuities, but cannot provide precise depth measurements. All pursuer control is specified either in terms of this sensor or wall-following movements. The pursuer does not have localization capability or perfect control. We present a complete algorithm that enables the limited pursuer to clear the same environments that a pursuer with a complete map, perfect localization, and perfect control can clear (under certain general position assumptions). Theoretical guarantees that the evaders will be found are provided. The resulting algorithm to compute this strategy has been implemented in simulation. Results arc shown for several examples. The approach is efficient and simple enough to be useful towards the development of real robot systems that perform visual searching.

关键词： sensor-based planning visibility pursuit-evasion on-line algorithms surveillance bug algorithms sensing uncertainty

来源：评论

学校读者我要写书评

暂无评论

Parallel scheduling problems in next generation wireless networks

引用

NETWORKS 2005年第1期45卷 9-22页

作者： Becchetti, L Leonardi, S Marchetti-Spaccamela, A Vitaletti, A Diggavi, S Muthukrishnan, S Nandagopal, T Univ Roma La Sapienza Rome Italy Lab Syst Informat & Commun Lausanne Switzerland Rutgers State Univ Piscataway NJ 08855 USA Bell Labs Holmdel NJ 07733 USA

Next-generation 3G/4G wireless data networks allow multiple codes (or channels) to be allocated to a single user, where each code can support multiple data rates. Providing fine-grained QoS to users in such networks poses the two-dimensional challenge of assigning both power (rate) and codes to every user. This gives rise to a new class of parallel scheduling problems. We abstract general downlink scheduling problems suitable for proposed next-generation wireless data systems. Our contribution includes a communication-theoretic model for multirate wireless channels. In addition, while conventional focus has been on throughput maximization, we attempt to optimize the maximum response time of jobs, which is more suitable for streams of user requests. We present provable results on the algorithmic complexity of these scheduling problems. In particular, we are able to provide very simple, on-line algorithms for approximating the optimal maximum response time. We also perform an experimental study with realistic data of channel conditions and user requests that strengthens our theoretical results. (C) 2004 Wiley Periodicals, Inc.

关键词： scheduling on-line algorithms wireless networks convex programming resource augmentation CDMA

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：