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

The complexity of leader election in diameter-two networks

distributed COMPUTING 2020年第2期33卷 189-205页

作者： Chatterjee, Soumyottam Pandurangan, Gopal Robinson, Peter Univ Houston Houston TX 77204 USA McMaster Univ Hamilton ON Canada

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1-7:27, 2015) showed a fundamental lower bound of Omega(m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability;this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134-143, 2015) established a tight bound of (Theta) over tilde(root n) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of (Theta) over tilde (n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n(-c), for some fixed positive constant c) succeeds and uses O(n log(3) n) messages and runs in O(1) rounds;this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs O(n) messages (even when n is known), regardless of the number of rounds. We also present an O(n log n) message deterministic algorithm that takes O(log n) rounds (but needs knowledge of n);we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-a-vis the graph diameter.

关键词： distributed algorithm Leader election Randomized algorithm Message complexity Time complexity Lower bound

来源：评论

学校读者我要写书评

暂无评论

Energy Efficient Scheduling algorithms for Sweep Coverage in Mobile Sensor Networks

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2020年第6期19卷 1332-1345页

作者： Gao, Xiaofeng Chen, Zhiyin Pan, Jianping Wu, Fan Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Key Lab Scalable Comp & Syst Shanghai 200240 Peoples R China Univ Victoria Victoria BC V8P 5C2 Canada

Nowadays, with the development of micro-electro-mechanical technologies, sweep coverage with mobile sensors is more and more popular in wireless sensor networks, which is also applied widely in other scenarios, such as message ferrying and data routing in ad-hoc networks. In order to reduce the sweep cycle and the number of mobile sensors, we propose the Distance-Sensitive-Route-Scheduling (DSRS) problem, which is to consider the effect of sensing range. We prove that DSRS is NP-hard, and consider three different scenarios: the single sensing-point case, the general case, and the extended case. In the single sensing-point case, we propose an approximation algorithm ROSE to schedule the routes of the mobile sensors efficiently. For the general case and the extended case, we present two other approximation algorithms G-ROSE and E-ROSE based on ROSE. We further characterize the non-locality property and design a distributed algorithm D-ROSE, coordinating sensors to meet the sweep requirements with best effort. Our algorithms are scalable to different sweep coverage problems, and according to the simulation results, they greatly outperform other existing algorithms up to 45 percent especially with a large sensing range.

关键词： Robot sensing systems Approximation algorithms Scheduling distributed algorithms Surveillance Mobile computing Mobile sensor networks sweep coverage approximation distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Arbitrary pattern formation on infinite grid by asynchronous oblivious robots

引用

THEORETICAL COMPUTER SCIENCE 2020年 815卷 213-227页

作者： Bose, Kaustav Adhikary, Ranendu Kundu, Manash Kumar Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India

The ARBITRARY PATTERN FORMATION problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in the literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not have access to any common global coordinate system. However, the grid allows the robots to have a partial agreement on coordinate system as they can align the axes of their local coordinate systems along the grid lines. In this setting, we have shown that a set of robots can form any pattern, if their starting configuration is asymmetric. (C) 2020 Elsevier B.V. All rights reserved.

关键词： distributed algorithm Autonomous robot Arbitrary pattern formation Grid Asynchronous Look-compute-move cycle

来源：评论

学校读者我要写书评

暂无评论

Adaptive Routing algorithm for Information Management in distributed Microgrids in Smart Grid

引用

IFAC-PapersOnLine 2019年第4期52卷 336-341页

作者： Olamide Jogunola Bamidele Adebisi Kelvin Anoh Augustine Ikpehai Mohammad Hammoudeh Faculty of Science and Engineering Manchester Metropolitan University Manchester M1 5GD UK Department of Engineering and Mathematics Sheffield Hallam University Sheffield. S1 1WB UK

The increasing affordability of renewable energy resources is inspiring new interest in smart management techniques for the power grid. This paper presents an adaptive routing algorithm technique based on distributed dual-gradient update for facilitating communication among distributed energy resources (DER) units in smart grid. In particular, we consider the optimal message routing as a minimum cost flow problem among DER units in the network. The proposed technique employs a multi-commodity flow optimization, with the aim of minimizing the communication cost against network performances indicators such as throughput and delay. The results show that the proposed technique is able to route messages across the network in fewer processing steps than minimum spanning tree algorithm without any message drop. The algorithm is investigated for mesh, partial mesh and ring networks, with the result consistently showing potential cost savings and reduced complexity which can save significant amount of time when applied to a larger system.

关键词： distributed energy resources prosumer distributed algorithm communication network information flow management optimal power flow

来源：评论

学校读者我要写书评

暂无评论

Simple and local independent set approximation

引用

THEORETICAL COMPUTER SCIENCE 2020年 846卷 27-37页

作者： Boppana, Ravi B. Halldorsson, Magnus M. Rawitz, Dror MIT Dept Math Cambridge MA 02139 USA Reykjavik Univ Sch Comp Sci Reykjavik Iceland Bar Ilan Univ Fac Engn Ramat Gan Israel

We study the worst-case behavior of Turan-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, we revisit a randomized approach of Boppana that forms a simple 1-round distributed algorithm, as well as a streaming algorithm and a preemptive online algorithm. We show that it gives a tight (Delta + 1)/2-approximation in unweighted graphs of maximum degree Delta, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a (Delta + 1)-approximation, but a simple modification results in an asymptotic expected 0.529(Delta + 1)-approximation. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Independent set Turan bound Approximation algorithm distributed algorithm

来源：评论

学校读者我要写书评

暂无评论

Predefined-Time Generalized Nash Equilibrium Seeking for Noncooperative Games of Hybrid Heterogeneous Multi-Agent Systems

Predefined-Time Generalized Nash Equilibrium Seeking for Non...

引用

第34届中国控制与决策会议

作者： Yu Yang Xiaohong Nian Fuxi Niu School of Automation Central South University

This paper investigates the generalized Nash equilibrium(GNE) seeking problem of the noncooperative *** consider the problem that the participants in the noncooperative game have two different dynamics(the second-order linear dynamics and Euler-Lagrange nonlinear dynamics),and the feasible decision set is subject to the coupling equality constraints,the participant only can access the necessary information of its *** on the time base generator(TBG),we propose a distributed GNE seeking algorithms,it can converge to GNE with the predefined time,and the time can be designed in advance by the user without relying on the initial value and any design ***,the effectiveness of the algorithm is verified by a practical example.

关键词： distributed algorithm non-cooperative games generalized Nash equilibrium predefined time convergence hybrid heterogeneous multi-agent system

来源：评论

学校读者我要写书评

暂无评论

distributed deep learning inference in fog networks

Distributed deep learning inference in fog networks

引用

作者： Chowdhury, Arnab Aalto University

学位级别：硕士

Today’s smart devices are equipped with powerful integrated chips and built-in heterogeneous sensors that can leverage their potential to execute heavy computation and produce a large amount of sensor data. For instance, modern smart cameras integrate artificial intelligence to capture images that detect any objects in the scene and change parameters, such as contrast and color based on environmental conditions. The accuracy of the object recognition and classification achieved by intelligent applications has improved due to recent advancements in artificial intelligence (AI) and machine learning (ML), particularly, deep neural networks (DNNs). Despite the capability to carry out some AI/ML computation, smart devices have limited battery power and computing resources. Therefore, DNN computation is generally offloaded to powerful computing nodes such as cloud servers. However, it is challenging to satisfy latency, reliability, and bandwidth constraints in cloud-based AI. Thus, in recent years, AI services and tasks have been pushed closer to the end-users by taking advantage of the fog computing paradigm to meet these requirements. Generally, the trained DNN models are offloaded to the fog devices for DNN inference. This is accomplished by partitioning the DNN and distributing the computation in fog networks. This thesis addresses offloading DNN inference by dividing and distributing a pre-trained network onto heterogeneous embedded devices. Specifically, it implements the adaptive partitioning and offloading algorithm based on matching theory proposed in an article, titled "distributed inference acceleration with adaptive dnn partitioning and offloading". The implementation was evaluated in a fog testbed, including Nvidia Jetson nano devices. The obtained results show that the adaptive solution outperforms other schemes (Random and Greedy) with respect to computation time and communication latency.

关键词： DNN inference task partitioning task offloading distributed algorithm DNN framework and architectures

来源：评论

学校读者我要写书评

暂无评论

distributed multi-vehicle task assignment in a time-invariant drift field with obstacles

引用

IET CONTROL THEORY AND APPLICATIONS 2019年第17期13卷 2886-2893页

作者： Bai, Xiaoshan Yan, Weisheng Cao, Ming Xue, Dong Univ Groningen Fac Sci & Engn NL-9747 AG Groningen Netherlands Northwestern Polytech Univ Sch Marine Sci & Technol 127 West Youyi Rd Xian 710072 Shaanxi Peoples R China Tech Univ Munich Dept Elect & Comp Engn Arcisstr 21 D-80209 Munich Germany

This study investigates the task assignment problem where a fleet of dispersed vehicles needs to visit multiple target locations in a time-invariant drift field with obstacles while trying to minimise the vehicles' total travel time. The vehicles have different capabilities, and each kind of vehicles can visit a certain type of the target locations;each target location might require to be visited more than once by different kinds of vehicles. The task assignment problem has been proven to be NP-hard. A path planning algorithm is first designed to minimise the time for a vehicle to travel between two given locations through the drift field while avoiding any obstacle. The path planning algorithm provides the travel cost matrix for the target assignment, and generates routes once the target locations are assigned to the vehicles. Then, a distributed algorithm is proposed to assign the target locations to the vehicles using only local communication. The algorithm guarantees that all the visiting demands of every target will be satisfied within a total travel time that is at worst twice of the optimal when the travel cost matrix is symmetric. Numerical simulations show that the algorithm can lead to solutions close to the optimal.

关键词： remotely operated vehicles mobile robots distributed algorithms computational complexity minimisation total travel time travel cost matrix multivehicle task assignment time-invariant drift field task assignment problem dispersed vehicles multiple target locations path planning algorithm target assignment distributed algorithm numerical simulation

来源：评论

学校读者我要写书评

暂无评论

A consensus-based distributed trajectory control in a signal-free intersection

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2019年第Mar.期100卷 161-176页

作者： Mirheli, Amir Tajalli, Mehrdad Hajibabai, Leila Hajbabaie, Ali SUNY Stony Brook Dept Civil Engn Stony Brook NY 11794 USA Washington State Univ Dept Civil & Environm Engn 405 Spokane St Pullman WA 99164 USA

This paper develops a distributed cooperative control logic to determine conflict-free trajectories for connected and automated vehicles (CAVs) in signal-free intersections. The cooperative trajectory planning problem is formulated as vehicle-level mixed-integer non-linear programs (MINLPs) that aim to minimize travel time of each vehicle and their speed variations, while avoiding near-crash conditions. To push vehicle-level solutions towards global optimality, we develop a coordination scheme between CAVs on conflicting movements. The coordination scheme shares vehicle states (i.e., location) over a prediction horizon and incorporates such information in CAVs' respective MINLPs. Therefore, the CAVs will reach consensus through an iterative process and select conflict-free trajectories that minimize their travel time. The numerical experiments quantify the effects of the proposed methodology on traffic safety and performance measures in an intersection. The results show that the proposed distributed coordinated framework converges to near-optimal CAV trajectories with no conflicts in the intersection neighborhood. While the solutions are found in real-time, the comparison to a central intersection control logic for CAVs indicates a maximum marginal objective value of 2.30%. Furthermore, the maximum marginal travel time, throughput, and average speed do not exceed 0.5%, 0.1%, and 0.5%, respectively. The proposed control logic reduced travel time by 43.0-70.5%, and increased throughput and average speed respectively by 0.8-115.6% and 59.1-400.0% compared to an optimized actuated signal control, while eliminating all near-crash conditions.

关键词： distributed algorithm Coordination Signal-free Cooperative Control logic Connected and autonomous vehicles

来源：评论

学校读者我要写书评

暂无评论

Diffusion Kalman Filter With Quantized Information Exchange in distributed Mobile Crowdsensing

引用

IEEE INTERNET OF THINGS JOURNAL 2019年第3期6卷 4423-4435页

作者： Yang, Shujie Xu, Changqiao Qiu, Xuesong Wu, Dapeng Oliver Beijing Univ Posts & Telecommun State Key Lab Networking & Switching Technol Beijing 100876 Peoples R China Univ Florida Dept Elect & Comp Engn Gainesville FL 32611 USA

With the explosion of smart devices and the gradual maturation of mobile systems, mobile crowdsensing (MCS) is playing more and more important roles in our daily life. In traditional MCS with a centralized framework, participants directly send perceived information to the task provider alone. This framework greatly increases the burden of cloud-based servers and cannot make full use of the increasing computation and storage capabilities of Internet of Things devices. To offload the computing and storage burden from traditional MCS architecture, a distributed MCS architecture was proposed in this paper, in which participants exchange sensing information with each other rather than forward it to central servers to complete a task together. Then, a diffusion Kalman filtering algorithm with quantized information exchange (QDKF) was proposed to solve the dynamic real-time estimate problem and limited communication resources in distributed MCS, where nodes exchange their quantized observations with neighbors to reduce the consumption of computing and storage resources. To prove the convergence and stability of the QDKF algorithm, an in-depth analysis of the algorithm uncertainty was reported to completely characterize the proposed solution. Moreover, the proposed algorithm achieves a superior performance by simulation.

关键词： distributed algorithm Kalman filter meansquare-deviation (MSD) quantized information

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：