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

Data Caching Optimization With Fairness in Mobile Edge Computing

IEEE TRANSACTIONS ON SERVICES COMPUTING 2023年第3期16卷 1750-1762页

作者： Zhou, Jingwen Chen, Feifei He, Qiang Xia, Xiaoyu Wang, Rui Xiang, Yong Deakin Univ Sch Informat Technol Geelong Vic 3125 Australia Swinburne Univ Technol Dept Comp Technol Melbourne Vic 3122 Australia Univ Southern Queensland Sch Math Phys & Comp Toowoomba Qld 4350 Australia CSIRO Data61 Canberra ACT 2601 Australia

Mobile edge computing (MEC) provides a new computing paradigm that can overcome the inability of the traditional cloud computing paradigm to ensure low service latency by pushing computing power and resources to the network edge. Many studies have attempted to formulate edge data caching strategies for app vendors to optimize caching performance by caching the right data on the right edge servers. However, existing edge data caching approaches have unfortunately ignored fairness, which is an important issue from the app vendor's perspective. In general, an app vendor needs to cache data on edge servers to serve its users with insignificant latency differences at a minimum caching cost. In this paper, we make the first attempt to tackle the fair edge data caching (FEDC) problem. Specifically, we formulate the FEDC problem as a constraint optimization problem (COP) and prove its $\mathcal {NP}$NP-hardness. An optimal approach named FEDC-OPT is proposed to find optimal solutions to small-scale FEDC problems with integer programming technique. In addition, an approximate algorithm named FEDC-APX is proposed to find approximate solutions in large-scale FEDC problems. The performance of the proposed approaches is analyzed theoretically, and evaluated experimentally on a widely-used real-world data set against four representative approaches. The experimental results show that the proposed approaches can solve the FEDC problem efficiently and effectively.

关键词： approximation algorithm edge data caching fairness integer programming mobile edge computing optimization

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for parallel machine scheduling under additional resource constraints

引用

OPTIMIZATION LETTERS 2023年第3期17卷 753-769页

作者： Zhang, An Zhen, Tan Chen, Yong Chen, Guangting Hangzhou Dianzi Univ Dept Math Hangzhou 310018 Peoples R China Zhejiang Univ Water Resources & Elect Power Hangzhou 310018 Peoples R China

We consider a classic machine scheduling problem under resource constraints. Given m parallel identical machines and a collection of additional but renewable resources, each task requires both a machine and one particular resource at any time of its processing. The goal is to allocate the machines and resources to the tasks so as to minimize the makespan, that is, the maximum completion time of all tasks. Because of NP-hardness of the problem, we design a three-stage combinatorial algorithm with performance ratio 2m+2/m+3 that improves the best prior ratio for m >= 3 machines and ties with that for m = 2 machines.

关键词： Resource constraints Parallel machines approximation algorithm Performance analysis

来源：评论

学校读者我要写书评

暂无评论

AN ADAPTIVE algorithm FOR MAXIMIZATION OF NON-SUBMODULAR FUNCTION WITH A MATROID CONSTRAINT

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2023年第3期19卷 2050-2070页

作者： Sun, Xin Xu, Dachuan Zhang, Dongmei Zhou, Yang Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio gamma. The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio (1 - e(-gamma 2) - O(epsilon)) in O(log n log(k/gamma epsilon)/epsilon(-2) log n log(1/gamma) - epsilon(-1) log(1-epsilon)) then use the contention resolution schemes to convert the fractional solution to a discrete one with gamma (1 - e(-1))(1 - e(-gamma 2) - O(epsilon))-approximation.

关键词： approximation algorithm non-submodular generic submodularity ratio matroid constraints adaptivity

来源：评论

学校读者我要写书评

暂无评论

Doing their best: How to provide service by limited number of drones?

引用

WIRELESS NETWORKS 2023年第1期29卷 209-220页

作者： Danilchenko, Kiril Nutov, Zeev Segal, Michael Ben Gurion Univ Negev Sch Elect & Comp Engn Beer Sheva Israel Open Univ Israel Raanana Israel

Exploiting drones as flying base stations to assist the terrestrial cellular networks or replace them is promising in 5G and beyond. One of the challenging problems is optimally deploying multiple drones to achieve coverage for the ground users. Usually, the goal is to find the minimum number of drones and their placement when all users are served. In this work, we consider a more realistic scenario. We focus on the situation where the number of drones is given in advance, and this number is significantly smaller than the number required to cover all ground users. This assumption is reasonable in emergency cases or battlefields where the number of ground users (for example, soldiers or firefighters) is much larger than the number of drones. Additionally, we consider the case when the ground users have a rank, interpreted as weight, and we aim to deploy drones' swarm such that the sum of the weights of the ground users covered by the swarm is maximized while the drones in the swarm are connected (without involving a third party entity that provides connectivity in the swarm). Our solution significantly improves currently best known approximation ratio for the problem from 1/144 to 1/28.

关键词： Budgeted covering approximation algorithm Tree partition

来源：评论

学校读者我要写书评

暂无评论

Benefit-oriented task offloading in UAV-aided mobile edge computing: An approximate solution

引用

PEER-TO-PEER NETWORKING AND APPLICATIONS 2023年第5期16卷 2058-2072页

作者： Gao, Yu Tao, Jun Wang, Haotian Wang, Zuyan Zou, Dikai Xu, Yifan Southeast Univ Sch Cyber Sci & Engn Nanjing 211189 Jiangsu Peoples R China Southeast Univ Key Lab CNII MOE Nanjing 211189 Jiangsu Peoples R China Purple Mt Labs Network & Commun Secur Nanjing 211111 Jiangsu Peoples R China

Recently, adopting UAVs equipped with the edge computing platform to provide computing service has been considered as a promising approach for resource-limited devices in mobile edge computing (MEC). Unfortunately, the limited resources (e.g., energy, computing and communication) of the UAV may significantly restrict its service capability, which means it has to selectively provide task offloading service to achieve the maximal benefit. In this article, aiming at optimizing the overall benefit of the UAV in a single dispatch, we propose an approximate Benefit Maximizing Task Offloading (BMTO) algorithm, which jointly considers the trajectory scheduling of the UAV and the offloading strategy of tasks. Specially, the flight path of the UAV is decomposed into several hover sites, which are selected by a benefit-cost approach. And the offloading sequence of tasks is arranged to maximize the benefit of the UAV through a surrogate function, which is proved to be a nonnegative monotone submodular function. Thus we transform the original problem into a submodular maximization problem and theoretically prove that BMTO owns an approximation ratio of 1/2 (1 - 1/e) . Simulation results show that our proposed algorithm outperforms the benchmark algorithms in terms of total benefit as well as energy efficiency ratio.

关键词： UAV-Aided MEC Task offloading Trajectory scheduling Benefit maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Design and Optimization of Solar-Powered Shared Electric Autonomous Vehicle System for Smart Cities

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第4期22卷 2053-2068页

作者： Zhou, Pengzhan Wang, Cong Yang, Yuanyuan SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA George Mason Univ Dept Cybersecur Fairfax VA 22030 USA

Smart transportation shall address utility waste, traffic congestion, and air pollution problems with least human intervention in future smart cities. To realize the sustainable operation of smart transportation, we leverage solar-harvesting charging stations and rooftops to power electric autonomous vehicles(AVs) solely via design. With a fixed budget, our framework first optimizes the locations of charging stations based on historical spatial-temporal solar energy distribution and usage patterns, achieving (2+e) factor to the optimal. Then a stochastic algorithm is proposed to update the locations online to adapt to any shift in the distribution. Based on the deployment, a strategy is developed to assign energy requests in order to minimize their traveling distance to stations while not depleting their energy storage. Equipped with extra harvesting capability, we also optimize route planning to achieve a reasonable balance between energy consumed and harvested en-route. As a promising application, utility optimization of shared electric AVs is discussed, and (2k+1)-approx algorithm is proposed to manage $k$k vehicles simultaneously. Our extensive simulations demonstrate the algorithm can approach the optimal solution within 10-15% approximation error, improve the operating range of vehicles by up to 2-3 times, and improve the utility by more than 50% compared to other competitive strategies.

关键词： Optimal scheduling energy harvesting vehicle charging shared autonomous vehicles approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

New semidefinite relaxations for a class of complex quadratic programming problems

引用

JOURNAL OF GLOBAL OPTIMIZATION 2023年第1期87卷 255-275页

作者： Xu, Yingzhe Lu, Cheng Deng, Zhibin Liu, Ya-Feng North China Elect Power Univ Sch Econ & Management Beijing 102206 Peoples R China Univ Chinese Acad Sci Sch Econ & Management Beijing 100190 Peoples R China UCAS MOE Social Sci Lab Digital Econ Forecasts & Policy Beijing 100190 Peoples R China Chinese Acad Sci Inst Computat Math & Sci Engn Comp Acad Math & Syst Sci State Key Lab Sci & Engn Comp Beijing 100190 Peoples R China

In this paper, we propose some new semidefinite relaxations for a class of nonconvex complex quadratic programming problems, which widely appear in the areas of signal processing and power system. By deriving new valid constraints to the matrix variables in the lifted space, we derive some enhanced semidefinite relaxations of the complex quadratic programming problems. Then, we compare the proposed semidefinite relaxations with existing ones, and show that the newly proposed semidefinite relaxations could be strictly tighter than the previous ones. Moreover, the proposed semidefinite relaxations can be applied to more general cases of complex quadratic programming problems, whereas the previous ones are only designed for special cases. Numerical results indicate that the proposed semidefinite relaxations not only provide tighter relaxation bounds, but also improve some existing approximation algorithms by finding better sub-optimal solutions.

关键词： Quadratic optimization Semidefinite relaxation approximation algorithm Phase quantized waveform design Discrete transmit beamforming

来源：评论

学校读者我要写书评

暂无评论

TWO-AGENT VEHICLE SCHEDULING PROBLEM ON A LINE-SHAPED NETWORK

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2023年第7期19卷 4874-4892页

作者： Yan, Hao Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

This paper studies single vehicle scheduling problems with two agents on a line-shaped network. Each of two agents has some customers that are situated at some vertices on the network. A vehicle has to start from upsilon(0) to serve all customers. The objective is to schedule the customers to minimize C-max(A) + theta C-max(B), where C-max(X) is the latest completion time of the customers for agent X and X is an element of{A,B}. We first propose a polynomial time algorithm for the problem without release time. Next, the problem with release time is proved to be NP-hard despite of a network with only two vertices. Then, we present a 3+root 5/2 -approximation algorithm. Finally, numerical experiments are carried out to verify the approximation algorithm is effective.

关键词： Agent scheduling network scheduling complexity polynomial time algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Joint Server Deployment and Task Scheduling for the Maximal Profit in Mobile-Edge Computing

引用

IEEE INTERNET OF THINGS JOURNAL 2023年第24期10卷 22501-22513页

作者： Gao, Yu Tao, Jun Wang, Haotian Wang, Zuyan Sun, Weice Song, Changping Southeast Univ Sch Cyber Sci & Engn Nanjing 210000 Peoples R China Southeast Univ Key Lab CNII MOE Nanjing 210000 Peoples R China Purple Mt Labs Network & Commun Secur Nanjing 210000 Peoples R China

Recently, adopting mobile-edge computing (MEC) to accommodate the compute-intensive and delay-sensitive tasks from mobile devices has gained increasing attention from the research community. In contrast to a cloud-centric scheme, deploying servers at the network edge offers the advantage of delivering faster and more efficient services. However, pioneering works primarily focus on a homogeneous server deployment strategy, which distributes the same quantity of servers among a specific number of selected locations. In this work, we aim to lay the theoretical foundation for budget-constrained profits maximization (BCPM) problem, which is a coupled problem of server deployment and task scheduling. Subsequently, a two-step optimization method is proposed. Through seeking the maximum matches in the constructed bipartite graph, a task scheduling algorithm is first designed to maximize the profits under the server deployment. Then, two approximation algorithms with provable approximation ratios are exploited to perform nearly optimal deployment of servers in a homogeneous and heterogeneous manner, respectively. Extensive simulations with real-world data set and system settings are conducted. The results show that the proposed algorithms can achieve at least a 10.54% increase in total profits and the average processing delay of tasks can be shortened by about 17%.

关键词： approximation algorithm mobile-edge computing (MEC) profit maximization server deployment

来源：评论

学校读者我要写书评

暂无评论

Computing densest k-subgraph with structural parameters

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-17页

作者： Hanaka, Tesshu Kyushu Univ Fac Informat Sci & Elect Engn Dept Informat Fukuoka Japan

DENSEST k-SUBGRAPH is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that DENSEST k-SUBGRAPH is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2-approximation 2(tc(G)/2)n(O(1))-time algorithm where tc(G) is the twin cover number of an input graph G.

关键词： Densest subgraphs Sparsest subgraphs Fixed parameter tractability Structural parameters approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：