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

On-line algorithm for optimizing throughput performance of wireless LANs

JOURNAL OF HIGH SPEED NETWORKS 2016年第2期22卷 125-151页

作者： Krishnan, Sundaresan Chaporkar, Prasanna Google Mountain View CA 94043 USA Indian Inst Technol Bombay 400076 Maharashtra India

Throughput improvement of the wireless LANs has been a constant area of research. Most of the work in this area focuses on designing throughput optimal schemes for fully connected networks (no hidden nodes). The schemes are optimal in a sense that they maximize the sum throughput subject to giving equal channel access opportunity to each user. But, we demonstrate that the optimal schemes proposed in the literature, though perform optimally in fully connected network, achieve significantly lesser throughput even than that of standard IEEE 802.11 in a network with hidden nodes. This motivates designing schemes that provide near optimal performance even when hidden nodes are present. This problem is particularly challenging as mathematical models for networks with hidden nodes do not exist. Here, we consider the weighted fair throughput allocation policy that maximizes system throughput while guaranteeing that every user achieves a throughput that is proportional to their weights. We prove the optimality of the proposed scheme in a fully connected network. However, the specialty of the algorithm, as observed in the simulation study, is that it can provide the optimal throughput even in networks with hidden terminals. Unlike existing techniques, which use the mathematical model to derive invariant features, we attempt to maximize the throughput directly using stochastic approximation techniques, and hence does not require the estimation of any system parameters which can result in inaccurate predictions. Simulations show that our proposed policies perform better than the standard IEEE 802.11 protocol without or with hidden nodes present. Moreover, our proposed schemes outperform existing schemes when the network is not fully connected.

关键词： Stochastic approximation optimization wireless LANs resource allocation on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

引用

THEORY OF COMPUTING SYSTEMS 2015年第1期56卷 22-40页

作者： Brodal, Gerth Stolting Moruz, Gabriel Negoescu, Andrei Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8200 Aarhus N Denmark Goethe Univ Frankfurt Inst Informat D-60325 Frankfurt Germany

In the field of online algorithms paging is one of the most studied problems. For randomized paging algorithms a tight bound of H (k) on the competitive ratio has been known for decades, yet existing algorithms matching this bound have high running times. We present a new randomized paging algorithm OnlineMin that has optimal competitiveness and allows fast implementations. In fact, if k pages fit in internal memory the best previous solution required O(k (2)) time per request and O(k) space. We present two implementations of OnlineMin which use O(k) space, but only O(logk) worst case time and O(logk/loglogk) worst case time per page request respectively.

关键词： on-line algorithms Competitive analysis Paging Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Greedily computing associative aggregations on sliding windows

引用

INFORMATION PROCESSING LETTERS 2015年第2期115卷 186-192页

作者： Basin, David Klaedtke, Felix Zalinescu, Eugen Swiss Fed Inst Technol Inst Informat Secur Zurich Switzerland NEC Europe Ltd Heidelberg Germany

We present an algorithm for combining the elements of subsequences of a sequence with an associative operator. The subsequences are given by a sliding window of varying size. Our algorithm is greedy and computes the r... 详细信息

关键词： Sliding window Associative aggregation operator on-line algorithms Complexity Optimality

来源：评论

学校读者我要写书评

暂无评论

The optimal structure of algorithms for α-paging

引用

INFORMATION PROCESSING LETTERS 2015年第12期115卷 932-938页

作者： Kovacs, Annamaria Meyer, Ulrich Moruz, Gabriel Negoescu, Andrei Goethe Univ Frankfurt D-60325 Frankfurt Germany

Paging is an important part of data management between two memory hierarchies, a fast cache and a slow disk. Its main application areas are modern operating systems and databases. Paging algorithms need to take decisions without precisely knowing the future behavior of the system, therefore paging is one of the most studied problems in the field of online-algorithms. In this paper we consider a-paging [13], a variation of the classical paging problem. It models the asymmetry between reading and writing data when the slow disk is implemented by means of flash memory. We develop an online structure that keeps track of the cache contents of the optimal offline algorithm. Based on this structure we design the algorithm class OPTMark which has the best possible competitive ratio and performs well on real-world traces. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Paging on-line algorithms Empirical competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Weighted sampling without replacement from data streams

引用

INFORMATION PROCESSING LETTERS 2015年第12期115卷 923-926页

作者： Braverman, Vladimir Ostroysky, Rafail Vorsanger, Gregory Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90024 USA

Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis [5] presented an algorithm for weighted sampling without replacement from data streams. Their algorithm works under the assumption of precise computations over the interval [0,1]. Cohen and Kaplan [3] used similar methods for their bottom-k sketches. Efraimidis and Spirakis ask as an open question whether using finite precision arithmetic impacts the accuracy of their algorithm. In this paper we show a method to avoid this problem by providing a precise reduction from k-sampling without replacement to k-sampling with replacement. We call the resulting method Cascade Sampling. (C) 2015 Published by Elsevier B.V.

关键词： algorithms on-line algorithms Sampling Streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on one-space bounded square packing

引用

INFORMATION PROCESSING LETTERS 2015年第11期115卷 872-876页

作者： Grzegorek, Paulina Januszewski, Janusz Univ Technol & Life Sci Inst Math & Phys PL-85789 Bydgoszcz Poland

关键词： on-line algorithms Two-dimensional bin packing

来源：评论

学校读者我要写书评

暂无评论

OnlineMin: A Fast Strongly Competitive Randomized Paging Algorithm

OnlineMin: A Fast Strongly Competitive Randomized Paging Alg...

引用

9th International Workshop on Approximation and Online algorithms (WAOA 2011)

ISBN: (纸本)9783642291159

关键词： on-line algorithms Competitive analysis Paging Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Work-Competitive Scheduling on Task Dependency Graphs

引用

PARALLEL PROCESSING LETTERS 2015年第2期25卷 1550001-1550001页

作者： Kari, Chadi Russell, Alexander Shashidhar, Narasimha Univ Pacific Sch Engn & Comp Sci 3601 Pacific Ave Stockton CA 95211 USA Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA Sam Houston State Univ Dept Comp Sci Huntsville TX 77341 USA

A fundamental problem in distributed computing is the task of cooperatively executing a given set of t tasks by p asynchronous processors where the communication medium is dynamic and subject to failures. Also known as do-all, this problem been studied extensively in various distributed settings. In [2], the authors consider a partitionable network scenario and analyze the competitive performance of a randomized scheduling algorithm for the case where the tasks to be completed are independent of each other. In this paper, we study a natural extension of this problem where the tasks have dependencies among them. We present a simple randomized algorithm for p processors cooperating to perform t known tasks where the dependencies between them are defined by a k-partite task dependency graph and additionally these processors are subject to a dynamic communication medium. By virtue of the problem setting, we pursue competitive analysis where the performance of our algorithm is measured against that of the omniscient offline algorithm which has complete knowledge of the dynamics of the communication medium. We show that the competitive ratio of our algorithm is tight and depends on the dynamics of the communication medium viz. the computational width defined in [2] and also on the number of partitions of the task dependency graph.

关键词： on-line algorithms distributed computing randomized algorithms competitive analysis partitionable networks

来源：评论

学校读者我要写书评

暂无评论

On the advice complexity of online bipartite matching and online stable marriage

引用

INFORMATION PROCESSING LETTERS 2014年第12期114卷 714-717页

作者： Miyazaki, Shuichi Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Kyoto 6068501 Japan

In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, inverted right perpendicular log(2)(n!) inverted left perpendicular bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter. (C) 2014 Elsevier B.V. All rights reserved.

关键词： on-line algorithms Advice complexity Bipartite matching Stable marriage

来源：评论

学校读者我要写书评

暂无评论

DISTRIBUTED ON-line MULTIDIMENSIONAL SCALING FOR SELF-LOCALIZATION IN WIRELESS SENSOR NETWORKS

DISTRIBUTED ON-LINE MULTIDIMENSIONAL SCALING FOR SELF-LOCALI...

引用

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Morral, Gemma Dieng, Ndeye Amy Bianchi, Pascal Telecom ParisTech Inst Mines Telecom CNRS LTCI F-75634 Paris France

ISBN: (纸本)9781479928934

Consider a wireless network formed by fixed or mobile nodes. Each node seeks to estimate its own position based on noisy measurements of the relative distance with other nodes. In a centralized batch mode, positions can be retrieved (up to a rigid transformation) by applying Principal Component Analysis (PCA) on a so-called similarity matrix built from the relative distances. In this paper, we propose a distributed on-line algorithm allowing each node to estimate its own position based limited exchange of information in the network. Our framework encompasses the case of sporadic measurements and random link failures. We prove the consistency of our algorithm in the case of fixed sensors. Our numerical results also demonstrate the attractive performance of the algorithm for tracking the positions of mobile sensors. Simulations are conducted on a wireless sensor network testbed.

关键词： Distributed algorithms on-line algorithms Localization Principal Component Analysis Wireless Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：