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

Energy-Efficient Flight Scheduling and Trajectory Optimization in UAV-Aided Edge Computing Networks

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第5期11卷 4591-4602页

作者： Ye, Weidu Zhao, Lu Zhou, Jian Xu, Sheng Xiao, Fu Nanjing Univ Posts & Telecommun Sch Comp Sci Nanjing 210023 Peoples R China Nanjing Forestry Univ Coll Comp Sci & Technol & Artificial Intelligence Nanjing 210037 Peoples R China

Energy saving is a critical issue in UAV-aided edge computing for their limited battery storage. Most recent studies in UAV-aided edge computing have focused on reducing the energy consumption of UAVs during a single flight, but this approach may not be appropriate for scenarios with a large number of ground clients (GCs) that need to be served. In this study, a UAV-mounted edge node is deployed as a mobile edge computing platform to collect and process tasks generated from GCs. The goal of this work is to minimize the energy consumption of the UAV by optimizing the number of flights and the flight trajectories, while adhering to the deadline constraints of the GCs. In this work, we first formulate the problem in a simple scenario where the UAV has sufficient energy for the entire flight. We then propose an offline optimal trajectory-design algorithm with theoretical analysis, while considering the deadline constraints. Next, we propose an online approximation algorithm that is suitable for a multi-flight scenario, where UAVs need to perform multiple flights to complete all tasks for the GCs. We prove that the approximation ratio of our algorithm is 2, and the simulation results demonstrate that our algorithms outperform the compared algorithms.

关键词： approximation algorithm energy saving flight scheduling UAV-aided edge computing approximation algorithm energy saving flight scheduling UAV-aided edge computing

来源：评论

学校读者我要写书评

暂无评论

Digital Twin-Assisted, SFC-Enabled Service Provisioning in Mobile Edge Computing

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2024年第1期23卷 393-408页

作者： Li, Jing Guo, Song Liang, Weifa Chen, Quan Xu, Zichuan Xu, Wenzheng Zomaya, Albert Y. Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Guangdong Univ Technol Sch Comp Guangzhou 510006 Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China Sichuan Univ Coll Comp Sci Chengdu 610017 Peoples R China Univ Sydney Sch Comp Sci Camperdown NSW 2006 Australia

Mobile Edge Computing (MEC) has been identified as a desirable computing paradigm that provides efficient and effective services for various applications, while meeting stringent service delay requirements. Orthogonal to the MEC computing paradigm, Network Function Virtualization (NFV) technology is another enabling technology that provides the network resource management with great flexibility and scalability, where the instances of Virtual Network Functions (VNFs) are deployed in edge servers as Service Function Chains (SFCs) for SFC-enabled services. Although reliable service provisioning in MEC environments is fundamentally important, the deployed VNF instances usually are not reliable, which can be affected by their software implementation, their execution duration, the workload among edge servers, and so on. Empowered by digital twin techniques, the states of VNF instances can be maintained by their digital twins in a real-time manner and their reliability can be accurately predicted through their digital twins. In this paper, we study digital twin-assisted, SFC-enabled reliable service provisioning in MEC networks by exploiting the dynamics of VNF instance reliability. We concentrate on two novel optimization problems of reliable service provisioning: the service cost minimization problem, and the dynamic service admission maximization problem. We first show their NP-hardness. We then formulate an Integer Linear Program (ILP) solution, and devise an approximation algorithm with a constant approximation ratio for the service cost minimization problem. We third provide an ILP solution to the offline version of the dynamic service admission maximization problem. Built upon this offline ILP solution, we also develop an online algorithm with a provable competitive ratio for the problem, by adopting the primal-dual dynamic updating technique. We finally evaluate the performance of the proposed algorithms via simulations. Simulation results demonstrate that the prop

关键词： Mobile edge computing service function chain digital twin reliable service provisioning approximation algorithm online algorithm resource allocation and optimization

来源：评论

学校读者我要写书评

暂无评论

Federated Submodular Maximization With Differential Privacy

引用

IEEE INTERNET OF THINGS JOURNAL 2024年第2期11卷 1827-1839页

作者： Wang, Yanhao Zhou, Tianchen Chen, Cen Wang, Yinggui East China Normal Univ Sch Data Sci & Engn Shanghai 200062 Peoples R China Ant Grp Hangzhou 310000 Peoples R China

Submodular maximization is a fundamental problem in many Internet of Things applications, such as sensor placement, resource allocation, and mobile crowdsourcing. Despite being intensively studied over the last two decades, the problem of submodular maximization has not yet been considered in an emerging federated computation setting. In this article, we first comprehensively study federated submodular maximization, where a set of clients aims to cooperate in finding a set of items to maximize a monotone submodular function under the orchestration of a central server while providing strong privacy guarantees for their sensitive data. We consider the problem in a client-level differential privacy (DP) setting: the server is not necessarily trusted and the clients should perturb their results locally before sending them to the server. Specifically, we propose a novel approximation algorithm for federated submodular maximization by incorporating client-level DP mechanisms and decomposed function evaluations into the greedy algorithm, along with two heuristics to further reduce the privacy budget, computational cost, and communication overhead. Finally, we perform extensive experiments to demonstrate the effectiveness and efficiency of our proposed algorithms.

关键词： approximation algorithm differential privacy (DP) federated computation submodular maximization

来源：评论

学校读者我要写书评

暂无评论

Robust IRS-Element Activation for Energy Efficiency Optimization in IRS-Assisted Communication Systems With Imperfect CSI

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2024年第10期23卷 14380-14393页

作者： Efrem, Christos N. Krikidis, Ioannis Univ Cyprus Dept Elect & Comp Engn CY-1678 Nicosia Cyprus

In this paper, we study an intelligent reflecting surface (IRS)-aided communication system with single-antenna transmitter and receiver, under imperfect channel state information (CSI). More specifically, we deal with the robust selection of binary (on/off) states of the IRS elements in order to maximize the worst-case energy efficiency (EE), given a bounded CSI uncertainty, while satisfying a minimum signal-to-noise ratio (SNR). In addition, we consider not only continuous but also discrete IRS phase shifts. First, we derive closed-form expressions of the worst-case SNRs, and then formulate the robust (discrete) optimization problems for each case. In the case of continuous phase shifts, we design a dynamic programming (DP) algorithm that is theoretically guaranteed to achieve the global maximum with polynomial complexity O (L log L), where L is the number of IRS elements. In the case of discrete phase shifts, we develop a convex-relaxation-based method (CRBM) to obtain a feasible (sub-optimal) solution in polynomial time O(L-3.5), with a posteriori performance guarantee. Furthermore, numerical simulations provide useful insights and confirm the theoretical results. In particular, the proposed algorithms are several orders of magnitude faster than the exhaustive search when L is large, thus being highly scalable and suitable for practical applications. Moreover, both algorithms outperform a baseline scheme, namely, the activation of all IRS elements.

关键词： Intelligent reflecting surface continuous/discrete phase shifts IRS-element activation energy efficiency imperfect CSI robust discrete optimization dynamic programming global optimization convex relaxation approximation algorithm energy efficiency imperfect CSI robust discrete optimization dynamic programming global optimization convex relaxation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Conflict-Aware Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks

引用

IEEE ACCESS 2024年 12卷 14751-14763页

作者： Shin, Donghoon Lee, Changreol Choi, Sunghee DGIST Dept Elect Engn & Comp Sci Daegu 42988 South Korea Inzent Res & Dev Ctr Seoul 04516 South Korea Korea Adv Inst Sci & Technol KAIST Sch Comp Daejeon 34141 South Korea

This paper proposes a theoretical model-driven channel assignment scheme designed to enhance network performance in multi-radio multi-channel wireless mesh networks. Unlike previous conflict graph-based channel assignments that addressed co-channel interference and hidden terminal problems while overlooking an exposed terminal problem, our proposed approach integrates these problems comprehensively to mitigate network performance degradation. Given a communication graph, we establish a conflict graph based on hop distance for practical implementation. The weighted conflict graph is constructed by analyzing packet collision conditions under the IEEE 802.11 standard with the CSMA/CA protocol, considering not only the transmission range and interference range but also the carrier sensing range simultaneously. Given a weighted conflict graph and available channel lists on each router, we devise a Weighted Soft List Coloring problem to address the channel assignment challenge. We prove the NP-hardness of this problem by establishing its dual problem, Max list-Cut. We present an approximation algorithm with worst-case performance at most twice the optimal solution while preserving network topology. We substantiate the performance of the proposed channel assignment algorithm through simulations in various topologies. The proposed algorithm, on average, demonstrates a network throughput increase of 162% and 174% compared to the greedy heuristic algorithm with 3 channels and 12 channels, respectively.

关键词： Channel allocation Wireless sensor networks IEEE 802.11 Standard Interchannel interference Sensors Ad hoc networks Wireless mesh networks Channel assignment in IEEE 802.11 networks multi-radio and multi-channel weighted soft list coloring problem max list-cut problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Sequential Competitive Facility Location: Exact and Approximate algorithms

引用

OPERATIONS RESEARCH 2024年第1期72卷 300页

作者： Qi, Mingyao Jiang, Ruiwei Shen, Siqian Tsinghua Univ Shenzhen Int Grad Sch Logist & Transportat Div Shenzhen 518071 Peoples R China Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA

We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation and exploit the problem structures to derive two valid inequalities based on submodularity and concave overestimation, respectively. We use the two valid inequalities in a branch-and-cut algorithm to find globally optimal solutions. Then, we propose an approximation algorithm to find good-quality solutions with a constant approximation guarantee. We develop several extensions by considering general facility-opening costs and outside competitors as well as diverse facility-planning decisions, and we discuss solution approaches for each extension. We conduct numerical studies to demonstrate that the exact algorithm significantly accelerates the computation of CFLP on large-sized instances that have not been solved optimally or even heuristically by existing methods, and the approximation algorithm can quickly find high-quality solutions. We derive managerial insights based on sensitivity analysis of different settings that affect customers' probabilistic choices and the ensuing demand.

关键词： competitive facility location mixed-integer nonlinear programming branch-and-cut submodularity concave overestimation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for finding maximum outerplanar subgraphs

引用

DISCRETE APPLIED MATHEMATICS 2024年 342卷 207-217页

作者： Calinescu, Gruia Kaul, Hemanshu Kudarzi, Bahareh IIT Dept Comp Sci Chicago IL 60616 USA IIT Dept Appl Math Chicago IL 60616 USA

We study the NP-complete MAXIMUM OUTERPLANAR SUBGRAPH problem. The previous best known approximation ratio for this problem is 2/3. We propose a new approximation algorithm which improves the ratio to 7/10.(c) 2023 El... 详细信息

关键词： Outerplanar graph Maximum subgraph approximation algorithm Matroid parity

来源：评论

学校读者我要写书评

暂无评论

algorithms for the bin packing problem with scenarios

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第4期48卷 1-28页

作者： Borges, Yulle G. F. de Lima, Vinicius L. Miyazawa, Flavio K. Pedrosa, Lehilton L. C. de Queiroz, Thiago A. Schouery, Rafael C. S. Univ Estadual Campinas Inst Comp Campinas SP Brazil Fed Univ Catalao Inst Math & Technol Catalao GO Brazil

This paper presents theoretical and practical results for the bin packing problem with scenarios, a generalization of the classical bin packing problem which considers the presence of uncertain scenarios, of which only one is realized. For this problem, we propose approximation algorithms whose ratios are bounded by the square root of the number of scenarios times the approximation ratio for an algorithm for the vector bin packing problem. We also show how an asymptotic polynomial-time approximation scheme is derived when the number of scenarios is constant, that is, not a part of the input. As a practical study of the problem, we present a branch-and-price algorithm to solve an exponential set-cover model and a variable neighborhood search heuristic. Experiments show the competence of the branch-and-price in obtaining optimal solutions for about 59% of the instances considered, while the combined heuristic and branch-and-price optimally solved 62% of the instances considered.

关键词： Bin packing problem Scenarios approximation algorithm Variable neighborhood search Branch-and-price algorithm

来源：评论

学校读者我要写书评

暂无评论

The maximum 3-star packing problem in claw-free cubic graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第5期47卷 73-73页

作者： Xi, Wenying Lin, Wensong Southeast Univ Sch Math Nanjing 210096 Peoples R China

A 3-star is a complete bipartite graph K1,3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{1,3}$$\end{document}. A 3-star packing of a graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is a 3-star. The maximum 3-star packing problem is to find a 3-star packing of a given graph with the maximum number of 3-stars. A 2-independent set of a graph G is a subset S of V(G) such that for each pair of vertices u,v is an element of S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u,v\in S$$\end{document}, paths between u and v are all of length at least 3. In cubic graphs, the maximum 3-star packing problem is equivalent to the maximum 2-independent set problem. The maximum 2-independent set problem was proved to be NP-hard on cubic graphs (Kong and Zhao in Congressus Numerantium 143:65-80, 2000), and the best approximation algorithm of maximum 2-independent set problem for cubic graphs has approximation ratio 815\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{8}{15}$$\end{document} (Miyano et al. in WALCOM 2017, Proceedings, pp 228-240). In this paper, we first prove that the maximum 3-star packing problem is NP-hard in claw-free cubic graphs and then design a linear-time algorithm which can find a 3-star packing of a connected claw-free cubic graph G covering at least 3v(G)-84\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackag

关键词： Cubic graphs Claw-free graphs 3-Star packing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Reconstruction of a Quality Virtual Backbone in a Wireless Sensor Network With Faulty Links

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2024年第1期11卷 1277-1292页

作者： Liang, Jiarong He, Feng Wang, Dajin Li, Qingnian Guangxi Univ Sch Comp Elect & Informat Guangxi Key Lab Multimedia Commun & Network Techno Nanning 530004 Peoples R China Nanning Univ Nanning 530200 Guangxi Peoples R China Guangxi Univ Sch Comp Elect & Informat Nanning 530004 Peoples R China Montclair State Univ Dept Comp Sci Montclair NJ 07043 USA Nanning Univ Coll Informat Engn Nanning 530200 Guangxi Peoples R China

The work of routing and topological control for a wireless sensor network (WSN) is often undertaken by means of its virtual backbone (VB). Usually, a WSN and its VB can be modeled as a unit disk graph (UDG) and a corresponding connected dominating set (CDS), respectively. A smaller CDS in a UDG is preferred because it will lead to less overhead. In practical applications, sensor nodes or their links in a WSN may fail due to obstacles or accidental damage. Thus, it is desirable to either construct a robust VB or be able to reconstruct a new VB. In this article, the problem of reconstructing CDSs for UDGs with faulty links is considered. First, we propose a centralized approximation algorithm for the problem. We theoretically show that for a given UDG, the size of the CDS constructed by our algorithm does not exceed xi & sdot;opt+gamma+2m , where xi & sdot;opt+gamma is the upper bound on the original CDS size, opt is the minimum CDS size in the UDG, xi and gamma are two positive constants, and m is the number of faulty links. Next, we design a distributed approximation algorithm on the basis of our centralized approximation algorithm and analyze its time and message complexity. Related simulation experiments are presented to compare our algorithm with other state-of-the-art algorithms for solving this problem, and the results show that our algorithm outperforms its competitors.

关键词： Wireless sensor networks approximation algorithms Routing Storms Fault tolerant systems Fault tolerance Task analysis Wireless sensor network approximation algorithm reconstruction faulty links distributed algorithm connected dominating set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：