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

Services Management and Distributed Multihop Requests Routing in Mobile Edge Networks

IEEE-ACM TRANSACTIONS ON NETWORKING 2023年第2期31卷 497-510页

作者： Shi, Tuo Cai, Zhipeng Li, Jianzhong Gao, Hong Chen, Jiancheng Yang, Ming Tianjin Univ Coll Intelligence & Comp Tianjin 300354 Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Xiamen Intretech Inc Fujian Prov Key Lab Ind Internet & IoT Xiamen 361027 Fujian Peoples R China Xiamen Intretech Inc Xiamen 361027 Fujian Peoples R China

Multi-access Edge Computing (MEC) is an emerging computing architecture to release the resource burden of the centralized cloud and reduce the mobile application latency. Services management and MEC requests routing is a major problem in MEC systems. Existing works mainly focus on the one-hop centralized request routing strategies. However, the centralized one-hop routing method is not suitable enough since the MEC network is a distributed system, and the number of MEC requests increases dramatically. In this paper, we have proposed an online problem. In such problem, we jointly consider the mobile edge service management and the distributed multi-hop requests routing in an MEC network in which the MEC requests randomly generate. We prove that such problem is NP-Hard even in the off-line scenario. Furthermore, we propose an approximation algorithm to manage the MEC services and two distributed online algorithms to route MEC requests. The approximation ratio and competitive ratio of these algorithms have been analyzed. Experiments are carried out to evaluate the performance of the algorithms and simulation results imply that these algorithms are effective and efficient.

关键词： Servers Routing Task analysis approximation algorithms Spread spectrum communication Mobile handsets Bandwidth Edge computing service management routing

来源：评论

学校读者我要写书评

暂无评论

Randomized Admission Policy for Efficient Top-k, Frequency, and Volume Estimation

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2019年第4期27卷 1432-1445页

作者： Ben Basat, Ran Chen, Xiaoqi Einziger, Gil Friedman, Roy Kassner, Yaron Harvard Univ Dept Comp Sci Cambridge MA 02138 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Network management protocols often require timely and meaningful insight about per flow network traffic. This paper introduces Randomized Admission Policy (RAP) -a novel algorithm for the frequency, top-k, and byte volume estimation problems, which are fundamental in network monitoring. We demonstrate space reductions compared to the alternatives, for the frequency estimation problem, by a factor of up to 32 on real packet traces and up to 128 on heavy-tailed workloads. For top-k identification, RAP exhibits memory savings by a factor of between 4 and 64 depending on the workloads' skewness. These empirical results are backed by formal analysis, indicating the asymptotic space improvement of our probabilistic admission approach. In Addition, we present d-way RAP, a hardware friendly variant of RAP that empirically maintains its space and accuracy benefits.

关键词： Algorithm design and analysis approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Path multicoloring with fewer colors in spiders and caterpillars

引用

COMPUTING 2007年第3期80卷 255-274页

作者： Pagourtzis, A. Potika, K. Zachos, S. Natl Tech Univ Athens Sch Elect & Comp Engn Dept Comp Sci Athens 15780 Greece CUNY Brooklyn Coll Brooklyn NY 11210 USA

We study a recently introduced path coloring problem with applications to wavelength assignment in all-optical networks with multiple fibers. In contrast to classical path coloring, it is, in this setting, possible to assign a color more than once to paths that pass through the same edge;the number of allowed repetitions per edge is given and the goal is to minimize the number of colors used. We present algorithms and hardness results for tree topologies of special interest. Our algorithms achieve approximation ratio of 2 in spiders and 3 in caterpillars, whereas the best algorithm for trees so far, achieves an approximation ratio of 4. We also study the directed version of the problem and show that it admits a 3-approximation algorithm in caterpillars, while it can be solved exactly in spiders.

关键词： path coloring multifiber all-optical networks approximation algorithms spiders caterpillars

来源：评论

学校读者我要写书评

暂无评论

METAHEURISTICS FOR THE DEPLOYMENT OF 5G

引用

IEEE WIRELESS COMMUNICATIONS 2015年第6期22卷 40-46页

作者： Tsai, Chun-Wei Cho, Hsin-Hung Shih, Timothy K. Pan, Jeng-Shyang Rodrigues, Joel J. P. C. Natl Ilan Univ Dept Comp Sci & Informat Engn Yilan 260 Taiwan Natl Cent Univ Dept Comp Sci & Informat Engn Zhongli Taiwan Natl Cent Univ Zhongli Taiwan Fujian Univ Technol Fujian Peoples R China Univ Beira Interior Inst Telecomunicacoes Dept Informat Covilha Portugal Univ Fortaleza Fortaleza Ceara Brazil

It is not difficult to anticipate that the system capacity and spectral efficiency of 5G will be greater than those of 4G, and so will the number of network-connected wireless devices. Moreover, the infrastructure of wireless communications today will not meet the requirements of a 5G environment because a large number of traffic flows will be generated between a large number of heterogeneous devices. The deployment strategy is one of the promising solutions to meet the expected demands of 5G. This article begins with a brief review of the deployment problem of wireless communication and a hyper-dense deployment problem (HDDP) definition for the requirements of 5G. A simple example for illustrating how a metaheuristic algorithm can be used to solve the HDDP is then given. Finally, some open and possible research issues are discussed to suggest future research trends on this problem.

关键词： 5G mobile communication Wireless communication Macrocell networks Genetic algorithms Software defined radio approximation algorithms Base stations

来源：评论

学校读者我要写书评

暂无评论

Resource-Constrained Federated Edge Learning With Heterogeneous Data: Formulation and Analysis

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第5期9卷 3166-3178页

作者： Liu, Yi Zhu, Yuanshao Yu, James J. Q. Southern Univ Sci & Technol Dept Comp Sci & Engn Guangdong Prov Key Lab Brain Inspired Intelligent Shenzhen 518055 Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong 518057 Peoples R China

Efficient collaboration between collaborative machine learning and wireless communication technology, forming a Federated Edge Learning (FEEL), has spawned a series of next-generation intelligent applications. However, due to the openness of network connections, the FEEL framework generally involves hundreds of remote devices (or clients), resulting in expensive communication costs, which is not friendly to resource-constrained FEEL. To address this issue, we propose a distributed approximate Newton-type algorithm with fast convergence speed to alleviate the problem of FEEL resource (in terms of communication resources) constraints. Specifically, the proposed algorithm is improved based on distributed L-BFGS algorithm and allows each client to approximate the high-cost Hessian matrix by computing the low-cost Fisher matrix in a distributed manner to find a "better" descent direction, thereby speeding up convergence. Second, we prove that the proposed algorithm has linear convergence in strongly convex and non-convex cases and analyze its computational and communication complexity. Similarly, due to the heterogeneity of the connected remote devices, FEEL faces the challenge of heterogeneous data and non-IID (Independent and Identically Distributed) data. To this end, we design a simple but elegant training scheme, namely FedOVA (Federated One-vs-All), to solve the heterogeneous statistical challenge brought by heterogeneous data. In this way, FedOVA first decomposes a multi-class classification problem into more straightforward binary classification problems and then combines their respective outputs using ensemble learning. In particular, the scheme can be well integrated with our communication efficient algorithm to serve FEEL. Numerical results verify the effectiveness and superiority of the proposed algorithm.

关键词： Convergence Optimization Distributed databases approximation algorithms Training Computational modeling Task analysis Resource-constrained Federated Edge Learning Non-IID Data Newton-type Methods One-vs-All Methods

来源：评论

学校读者我要写书评

暂无评论

Survivable Task Allocation in Cloud Radio Access Networks With Mobile-Edge Computing

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第2期8卷 1095-1108页

作者： Yang, Song He, Nan Li, Fan Trajanovski, Stojan Chen, Xu Wang, Yu Fu, Xiaoming Beijing Inst Technol Sch Comp Sci & Technol Beijing 100081 Peoples R China Microsoft Microsoft Search Assistant & Intelligence Grp London W2 6BD England Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510006 Peoples R China Temple Univ Dept Comp & Informat Sci Philadelphia PA 19122 USA Univ Gottingen Inst Comp Sci D-37077 Gottingen Germany

Cloud radio access network (C-RAN) is a promising 5G network architecture by establishing baseband units (BBU) pools to perform baseband processing functionalities and deploying remote radio heads (RRHs) for wireless signal transmission and reception. Mobile-edge computing (MEC) offers a way to shorten the service delay by building small-scale cloud infrastructures at the network edge. By co-locating the BBU pool with edge cloud at the so-called BBU node, we can take full advantages of C-RAN and MEC for better spectrum utilization and delay-guaranteed services. In this article, we first study how to allocate each users task to the BBU node and find the path from his/her accessing RRH node to the BBU node such that the maximum service delay among all the requests is minimized. We then consider this problem with survivability concerns, which is to use both primary and backup BBU nodes to issue the request such that the primary path and backup path are link disjoint. We analyze the complexities of these two problems and prove they are NP-hard in general. Subsequently, we devise a randomized approximation algorithm and an efficient heuristic to solve the considered problems, respectively. The simulation results show that the proposed algorithms outperform two benchmark heuristics in terms of acceptance ratio and maximum service delay.

关键词： Task analysis Delays Cloud computing Resource management Baseband approximation algorithms Edge computing Cloud radio access network (C-RAN) delay mobile-edge computing (MEC) survivability task allocation

来源：评论

学校读者我要写书评

暂无评论

Region-restricted clustering for geographic data mining

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2009年第3期42卷 231-240页

作者： Gudmundsson, Joachim van Kreveld, Marc Narasimhan, Giri NICTA Sydney NSW Australia Univ Utrecht Dept Informat & Comp Sci NL-3508 TC Utrecht Netherlands Florida Int Univ Sch Comp & Informat Sci Miami FL 33199 USA

Clustering problems in a complex geographical setting are often required to incorporate the type and extent of land cover within a region. Given a set P of n points in a geographical setting. with the constraint that the points of P can only occur in one type of land cover, an interesting problem is the detection Of Clusters. First, we extend the definition of clusters and define the concept of a region-restricted cluster that satisfies the following properties: (i) the cluster has sufficient number of points, (ii) the cluster points are confined to a small geographical area, and (iii) the amount of land cover of the specific type in which the points lie is also small. Next, we give efficient exact and approximation algorithms for computing such clusters. The exact algorithm determines all axis-parallel squares with exactly m out of n points inside, size at most some prespecified value, and area of a given land cover type at most another prespecified value, and runs in O(nm log(2) n + (nm + nn(f)) log(2) n(f)) time, where nf is the number of edges that bound the regions with the given land cover type. The approximation algorithm allows the square to be a factor 1 + epsilon too large, and runs in O (n log n + n/epsilon(2) + n(f) log(2) n(f) + (n log(2) n(f))/(m epsilon(2))) time. We also show how to compute largest clusters and outliers. Crown Copyright (c) 2008 Published by Elsevier B.V. All rights reserved.

关键词： Computational geometry Data structures Clustering approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension

引用

MATHEMATICAL PROGRAMMING 2008年第2期115卷 273-290页

作者： De Loera, Jesus A. Hemmecke, Raymond Koeppe, Matthias Weismantel, Robert Otto VonGuericke Univ Magdegurg FMA IMO D-39106 Magdeburg Germany Univ Calif Davis Dept Math Davis CA 95616 USA

We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.

关键词： mixed-integer nonlinear programming integer programming in fixed dimension computational complexity approximation algorithms FPTAS

来源：评论

学校读者我要写书评

暂无评论

FITTING TREE METRICS: HIERARCHICAL CLUSTERING AND PHYLOGENY

引用

SIAM JOURNAL ON COMPUTING 2011年第5期40卷 1275-1291页

作者： Ailon, Nir Charikar, Moses Technion Israel Inst Technol Fac Comp Sci IL-32000 Haifa Israel Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

Given dissimilarity data on pairs of objects in a set, we study the problem of fitting a tree metric to this data so as to minimize additive error (i.e., some measure of the difference between the tree metric and the given data). This problem arises in constructing an M-level hierarchical clustering of objects (or an ultrametric on objects) so as to match the given dissimilarity data-a basic problem in statistics. Viewed in this way, the problem is a generalization of the correlation clustering problem (which corresponds to M - 1). We give a very simple randomized combinatorial algorithm for the M-level hierarchical clustering problem that achieves an approximation ratio of M+2. This is a generalization of a previous factor 3 algorithm for correlation clustering on complete graphs. The problem of fitting tree metrics also arises in phylogeny where the objective is to learn the evolution tree by fitting a tree to dissimilarity data on taxa. The quality of the fit is measured by taking the l(p) norm of the difference between the tree metric constructed and the given data. Previous results obtained a factor 3 approximation for finding the closest tree metric under the l(infinity) norm. No nontrivial approximation for general l(p) norms was known before. We present a novel linear program formulation for this problem and obtain an O((log n log log n)(1/p))-approximation to the closest ultrametric under the l(p) norm using this. Our techniques are based on representing and viewing an ultrametric as a hierarchy of clusterings and may be useful in other contexts.

关键词： approximation algorithms phylogenic reconstructions hierarchical clustering

来源：评论

学校读者我要写书评

暂无评论

Approximating the Generalized Minimum Manhattan Network Problem

引用

ALGORITHMICA 2018年第4期80卷 1170-1190页

作者： Das, Aparna Fleszar, Krzysztof Kobourov, Stephen Spoerhase, Joachim Veeramoni, Sankar Wolff, Alexander Le Moyne Coll Dept Math & Comp Sci Syracuse NY USA Univ Arizona Dept Comp Sci Tucson AZ 85721 USA Univ Wurzburg Inst Informat Lehrstuhl 1 Wurzburg Germany

We consider the generalized minimum Manhattan network problem (GMMN). The input to this problem is a set R of n pairs of terminals, which are points in . The goal is to find a minimum-length rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axis-parallel line segments whose total length equals the pair's Manhattan distance. This problem is a natural generalization of the extensively studied minimum Manhattan network problem (MMN) in which R consists of all possible pairs of terminals. Another important special case is the well-known rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an -approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple -approximation algorithm for the problem in arbitrary fixed dimension d. As a corollary, we obtain an exponential improvement upon the previously best -ratio for MMN in d dimensions (ESA 2011). En route, we show that an existing -approximation algorithm for 2D-RSA generalizes to higher dimensions.

关键词： approximation algorithms Computational geometry Minimum Manhattan Network

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：