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

online Throughput Maximization for Energy Harvesting Communication Systems with Battery Overflow

IEEE TRANSACTIONS ON MOBILE COMPUTING 2017年第1期16卷 185-197页

作者： Wu, Weiwei Wang, Jianping Wang, Xiumin Shan, Feng Luo, Junzhou Southeast Univ Sch Comp Sci & Engn Nanjing Jiangsu Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China HeFei Univ Technol Sch Comp & Engn Hefei Anhui Peoples R China

Energy harvesting communication system enables energy to be dynamically harvested from natural resources and stored in capacitated batteries to be used for future data transmission. In such a system, the amount of future energy to harvest is uncertain and the battery capacity is limited. As a consequence, battery overflow and energy dropping may happen, causing energy underutilization. To maximize the data throughput by using the energy efficiently, a rate-adaptive transmission schedule must address the trade-off between a high- rate transmission which avoids energy overflow and a low-rate transmission which avoids energy shortage. In this paper, we study an online throughput maximization problem without knowing future information. To the best of our knowledge, this is the first work studying the fully-online transmission rate scheduling problem for battery-capacitated energy harvesting communication systems. We consider the problem under two models of the communication channel, a static channel model that assumes the channel status is stable, and a fading channel model that assumes the channel status varies. For the former, we develop an online algorithm that approximates the offline optimal solution within a constant factor for all possible inputs. For the latter, that the channel gains vary in range [h(min), h(max)], we propose an online algorithm with a proven Theta(log(h(max)/h(min)))-competitive ratio. Our simulation results further validate the efficiency of the proposed online algorithms.

关键词： Energy harvesting battery capacity energy overflow energy-efficient rate scheduling throughput maximization online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

The Steiner Traveling Salesman Problem with online edge blockages

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第1期243卷 30-40页

作者： Zhang, Huili Tong, Weitian Xu, Yinfeng Lin, Guohui Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

We consider the online Steiner Traveling Salesman Problem. In this problem, we are given an edge-weighted graph G = (V, E) and a subset D subset of V of destination vertices, with the optimization goal to find a minimum weight closed tour that traverses every destination vertex of D at least once. During the traversal, the salesman could encounter at most k non-recoverable blocked edges. The edge blockages are real-time, meaning that the salesman knows about a blocked edge whenever it occurs. We first show a lower bound on the competitive ratio and present an online optimal algorithm for the problem. While this optimal algorithm has non-polynomial running time, we present another online polynomial-time near optimal algorithm for the problem. Experimental results show that our online polynomial-time algorithm produces solutions very close to the offline optimal solutions. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Traveling Salesman Problem Steiner TSP online edge blockage online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

online LPT algorithms for parallel machines scheduling with a single server

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第3期26卷 480-488页

作者： Su, Chunjie E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

We consider two parallel machines scheduling problems with a single server. For the general case we present an online LPT algorithm with competitive ratio 2, and give a lower bound . We also apply the online LPT algorithm to the special case where all the setup times are equal to 1. We show that the competitive ratio is 1.5, and no online algorithm can has a competitive ratio less than root 2.

关键词： Parallel machines Server online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Collaborative online Edge Caching With Bayesian Clustering in Wireless Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2020年第2期7卷 1548-1560页

作者： Liu, Junyan Li, Dapeng Xu, Youyun Nanjing Univ Posts & Telecommun Key Lab Broadband Wireless Commun & Sensor Networ Nanjing 210003 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China

In this article, we study the edge caching problem by considering the heterogeneous context with unknown users' preferences. The cache provider (CP) can personalize the users' storage based on available data to maximize the overall cache hit rate, accounting for the dynamic natures of both mobile edge cache scenarios and the users' preferences. Toward this end, we introduce an online Bayesian clustering caching algorithm for the CP to autonomously learn the users' interactive cache hit data in a collaborative way while maintaining sustainable scalability. Specifically, a Bayesian generative framework called the Dirichlet multinomial mixture (DMM) model is used to describe the uncertainty about the latent number of users' clusters, each of which consists of the users with the same preference. Then, a dynamic clustering policy is proposed to obtain both the underlying mapping of users to clusters and the preferences of each cluster by using a collapsed Gibbs sampling algorithm. Subsequently, cache decisions are made according to the generated mappings by extending the traditional cache bandit algorithm to a new bandit mechanism with clusters of arms, capable of expediting the learning process between the exploitation and exploration. We theoretically characterize the value of dynamic Bayesian clustering for the long-term edge caching scenario with respect to the regret incurred by the noncluster schemes. Finally, using a real-world data set, our numerical results show that the proposed scheme outperforms the caching algorithms without clustering in the uncertain network scenario.

关键词： Heuristic algorithms Clustering algorithms Bayes methods Wireless communication Internet of Things Collaboration Hypercubes Bayesian clustering content cache edge computing online algorithm reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

online bin packing problem with buffer and bounded size revisited

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第2期33卷 530-542页

作者： Zhang, Minghui Han, Xin Lan, Yan Ting, Hing-Fung Dalian Univ Technol Sch Software Technol Dalian 116620 Peoples R China Dalian Neusoft Univ Informat Software Engn Dept Dalian 116023 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within where , and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360-369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.

关键词： Bin packing online algorithm Asymptotic competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal deterministic algorithms for some variants of online Quota Traveling Salesman Problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第3期238卷 735-740页

作者： Yu, Wei Liu, Zhaohui Bao, Xiaoguang E China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

This paper is concerned with the online Quota Traveling Salesman Problem. Depending on the symmetry of the metric and the requirement for the salesman to return to the origin, four variants are analyzed. We present optimal deterministic algorithms for each variant defined on a general space, a real line, or a half-line. As a byproduct, an improved lower bound for a variant of online TSP on a half-line is also obtained. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Traveling salesman Quota TSP online algorithm Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Optimal semi-online preemptive algorithms for machine covering on two uniform machines

引用

THEORETICAL COMPUTER SCIENCE 2005年第2-3期339卷 293-314页

作者： He, Y Jiang, YW Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Zhejiang Univ State Key Lab CAD & CG Hangzhou 310027 Peoples R China

In this paper, we consider the semi-online preemptive scheduling problem with decreasing job sizes on two uniform machines. Our goal is to maximize the continuous period of time (starting from time zero) when both machines are busy, which is equivalent to maximizing the minimum machine completion time if idle time is not introduced before all the jobs are completed. We design optimal deterministic semi-online algorithms for every machine speed ratio s is an element of [1, infinity), and show that idle time is required during the assignment procedure of algorithms for any s > root 6/2. The competitive ratios of the algorithms match the randomized lower bound for every 1 <= s <= 3. The problem of whether randomization still does not help for the discussed preemptive scheduling problem remains open. (c) 2005 Elsevier B.V. All rights reserved.

关键词： online algorithm preemptive scheduling machine covering competitive ratio

来源：评论

学校读者我要写书评

暂无评论

To store or not: online cost optimization for running big data jobs on the cloud

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2024年 156卷 42-52页

作者： Fu, Xiankun Pan, Li Liu, Shijun Shandong Univ Sch Software Jinan Peoples R China

As businesses increasingly rely on cloud-based big data analytics services to drive insights, reducing the cost of storing and analyzing large volumes of data in the cloud has become a major concern. During the execution of big data analysis jobs, some of the generated data can be reused by subsequent jobs. By storing such intermediate data, the cost of running big data jobs can be greatly reduced for businesses using cloud services. An important challenge is how to determine which data should be stored in order to save costs. Existing storing strategies do not differentiate between data with different usage frequencies, resulting in significant storage costs in practical applications. To address the aforementioned challenges, in this paper we propose two online algorithms, one deterministic and the other randomized, which dynamically determine whether to store the data with the aim of saving cost. We show that our proposed deterministic algorithm (resp., randomized) incurs costs within a factor of 2 - alpha' (resp., 2/1+alpha') times the minimum cost obtained by an optimal offline algorithm which is assumed to know the exact future a priori. Finally, through extensive experiments with real-world workload of big data jobs in Alibaba Cloud environment, we demonstrate that our proposed online algorithms can achieve significant cost savings under common cloud pricing schemes.

关键词： Cloud computing Cost optimization online algorithm Big data analysis Competitive analysis algorithm design

来源：评论

学校读者我要写书评

暂无评论

Hybrid online protocols for source location privacy in wireless sensor networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2018年 115卷 67-81页

作者： Bradbury, Matthew Jhumka, Arshad Leeke, Matthew Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

Wireless sensor networks (WSNs) will form the building blocks of many novel applications such as asset monitoring. These applications will have to guarantee that the location of the occurrence of specific events is kept private from attackers, in what is called the source location privacy (SLP) problem. Fake sources have been used in numerous techniques, however, the solution's efficiency is typically achieved by fine-tuning parameters at compile time. This is undesirable as WSN conditions may change. In this paper, we first present an SLP algorithm - Dynamic - that estimates the relevant parameters at runtime and show that it provides a high level of SLP, albeit at the expense of a high number of messages. To address this, we provide a hybrid online algorithm - DynamicSPR - that uses directed random walks for the fake sources allocation strategy to reduce energy usage. We perform simulations of the various protocols we present and our results show that DynamicSPR provides a similar level of SLP as when parameters are optimised at compile-time, with a lower number of messages sent. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Wireless sensor networks Source location privacy Fake sources Random walks online algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal algorithms for solving green online reheat furnace scheduling problems with deterioration effect

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2024年 194卷

作者： Xu, Juannian Ma, Ran Zhang, Houkun Qingdao Univ Technol Sch Management Engn Qingdao Peoples R China Southwestern Univ Finance & Econ Sch Business Adm Chengdu Peoples R China

Optimizing reheating furnace scheduling in terms of energy saving and reheating time reduction is a vital component in improving competitive advantage of the steel enterprises. However, current reheating furnace scheduling models are still limited since (1) most of the scheduling problems involving reheating furnace suppose that the steel orders and their information are known in advance and (2) the reheating time of a slab in reheating operation is a constant in the majority of current reheating furnace scheduling models. To address these issues, three online reheat furnace scheduling models with deterioration effect are proposed in order to minimize the maximum residence time, the maximum energy consumption as well as total energy consumption of all slabs in reheating operation, respectively. Furthermore, for these online scheduling problems, deterministic online algorithms are presented and shown to be optimal, respectively. In addition, the computational experiments confirm that the three online algorithms developed in this paper are particularly efficient and effective in practice.

关键词： Scheduling online algorithm Energy consumption Maximum residence time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：