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

Computation-Efficient distributed algorithm for Convex Optimization Over Time-Varying Networks With Limited Bandwidth Communication

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2020年 6卷 140-151页

作者： Li, Huaqing Huang, Chicheng Wang, Zheng Chen, Guo Umar, Hafiz Gulfam Ahmad Southwest Univ Coll Elect & Informat Engn Chongqing Key Lab Nonlinear Circuits & Intelligen Chongqing 400715 Peoples R China Univ New South Wales Sch Elect Engn & Telecommun Sydney NSW 2052 Australia Ghazi Univ Dept Comp Sci & IT Dg Khan 32260 Pakistan

A novel computation-efficient quantized distributed optimization algorithm is presented in this article for solving a class of convex optimization problems over time-varying undirected networks with limited communication capacity. These convex optimization problems are usually relevant to the minimization of a sum of local convex objective functions using only local communication and local computation. In most of the existing distributed optimization algorithms, each agent needs to calculate the subgradient of its local convex objective function at each time step, which leads to extremely heavy computation. The proposed algorithm incorporates random sleep scheme into procedures of agents' updates in a probabilistic form to reduce the computation load, and further allows for uncoordinated step-sizes of all agents. The quantized strategy is also applied, which overcomes the limitation of communication capacity. Theoretical analysis indicates that the convex optimization problems can be solved and numerical analysis shows that the computation load of subgradient can be significantly reduced by the proposed algorithm. The boundedness of the quantization levels at each time step has been explicitly characterized. Simulation examples are presented to demonstrate the effectiveness of the algorithm and the correctness of the theoretical results.

关键词： Convex optimization distributed algorithm computation-efficient quantization limited communication capacity

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for Min-Max Tree and Max-Min Cut Problems in Communication Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2010年第4期18卷 1067-1076页

作者： Guo, Song Leung, Victor C. M. Univ Aizu Sch Comp Sci & Engn Aizu Wakamatsu Fukushima 9658580 Japan Univ British Columbia Dept Elect & Comp Engn Vancouver BC V6T 1Z4 Canada

We consider the problem of finding a multicast tree rooted at the source node and including all the destination nodes such that the maximum weight of the tree arcs is minimized. It is of paramount importance for many optimization problems, e.g., the maximum-lifetime multicast problem in multihop wireless networks, in the data networking community. We explore some important properties of this problem from a graph theory perspective and obtain a min-max-tree max-min-cut theorem, which provides a unified explanation for some important while separated results in the recent literature. We also apply the theorem to derive an algorithm that can construct a global optimal min-max multicast tree in a distributed fashion. In random networks with it nodes and m arcs, our theoretical analysis shows that the expected communication complexity of our distributed algorithm is in the order of 0(m). Specifically, the average number of messages is 2(n - 1 - gamma) - 2ln(n - 1) + m, at most, in which gamma is the Euler constant. To our best knowledge, this is the first contribution that possesses the distributed and scalable properties for the min-max multicast problem and is especially desirable to the large-scale resource-limited multihop wireless networks, like sensor networks.

关键词： Communication complexity distributed algorithm min-max tree Steiner tree

来源：评论

学校读者我要写书评

暂无评论

A Novel distributed algorithm for constructing virtual backbones in wireless sensor networks

引用

COMPUTER NETWORKS 2018年 146卷 104-114页

作者： Luo, Chuanwen Yu, Jiguo Li, Deying Chen, Honglong Hong, Yi Ni, Lina Renmin Univ China Sch Informat Beijing 100872 Peoples R China Qilu Univ Technol Shandong Acad Sci Shandong Comp Sci Ctr Natl Supercomp Ctr Jinan Jinan 250014 Shandong Peoples R China Qufu Normal Univ Sch Informat Sci & Engn Rizhao 276826 Shandong Peoples R China China Univ Petr Coll Informat & Control Engn Qingdao 266580 Shandong Peoples R China Beijing Inst Petrochem Technol Informat Engn Coll Beijing 102617 Peoples R China Shandong Univ Sci & Technol Coll Comp Sci & Engn Qingdao 266590 Peoples R China SUST Shandong Prov Key Lab Wisdom Mine Informat Techno Qingdao 266590 Peoples R China

In Wireless Sensor Networks (WSNs), energy saving techniques are critical for efficient routing. The Connected Dominating Set (CDS) used as a virtual backbone for saving energy in WSN has been extensively studied in the past two decades. Since the time complexity and performance ratio are two important metrics to evaluate algorithms, reducing the time expenditure of algorithm and the total number of sensors in CDS are two key problems for CDS construction. In this paper, we propose a novel distributed algorithm, Dominating Set based on Link and Degree and Connecting Tree (LDDS-CT), to find a Minimum CDS (MCDS). LDDS-CT is divided into two phases. In the first phase, a Dominating Set (DS) is constructed using LDDS. In the second phase, a CT algorithm for connecting all sensors in DS is proposed, which can guarantee the number of connectors added to DS is minimized. This paper proves that the time cost of LDDS-CT is at most 2.25n and the performance ratio of LDDS-CT is at most 14.798opt + 9.748, where n is the number of sensors and opt is the size of any MCDS. To the best of our knowledge, LDDS-CT is the fastest two-phased distributed algorithm for MCDS construction with unknown network topology. And the performance ratio of the proposed algorithm is close to the sate-of-the-art algorithms in theory. The simulation results show that LDDS-CT outperforms the existing distributed algorithms. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Wireless sensor network distributed algorithm Connected dominating set Unit disk graph Virtual backbone Energy efficiency

来源：评论

学校读者我要写书评

暂无评论

distributed algorithm for Area Monitoring in Directional Sensor Networks 12th

Distributed Algorithm for Area Monitoring in Directional Sen...

引用

12th International Conference on Information Systems and Advanced Technologies, ICISAT 2022

作者： Bendimerad, Nawel Boumedjout, Amal Bot, Bena Department of Systems Engineering National Polytechnic School of Oran Maurice Audin El M’Naouer PO. Box 1523 Oran31000 Algeria

ISBN: (纸本)9783031253430

Directional sensor networks (DSNs) are still receiving consideration in different fields of high-level monitoring applications. However, unlike traditional omni-directional sensors, directional sensors are characterized by a limited sensing angle, which causes various problems for satisfying the coverage quality requirements of a critical region. In this paper, a novel distributed algorithm is proposed to significantly improve the area coverage ratio using a DSN. Based on a directional sensor node model combined with geometry concepts, we provide each directional sensor with the ability to calculate the most appropriate working direction. This solution allows us to maximize coverage, in such a way to obtain a better surveillance quality in monitoring and control applications. To extend the network lifetime, redundant sensors are exploited to keep just a set of directional sensors in active mode. Simulation results demonstrate that the proposed approach effectively improves the area coverage ratio compared to the existing algorithms. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Area coverage Directional sensor network distributed algorithm Simulation

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for high-dimension convex quadratically constrained quadratic programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2021年第3期80卷 781-830页

作者： Chen, Run Liu, Andrew L. Purdue Univ Sch Ind Engn W Lafayette IN 47906 USA

We propose a Jacobi-style distributed algorithm to solve convex, quadratically constrained quadratic programs (QCQPs), which arise from a broad range of applications. While small to medium-sized convex QCQPs can be solved efficiently by interior-point algorithms, high-dimension problems pose significant challenges to traditional algorithms that are mainly designed to be implemented on a single computing unit. The exploding volume of data (and hence, the problem size), however, may overwhelm any such units. In this paper, we propose a distributed algorithm for general, non-separable, high-dimension convex QCQPs, using a novel idea of predictor-corrector primal-dual update with an adaptive step size. The algorithm enables distributed storage of data as well as parallel, distributed computing. We establish the conditions for the proposed algorithm to converge to a global optimum, and implement our algorithm on a computer cluster with multiple nodes using message passing interface. The numerical experiments are conducted on data sets of various scales from different applications, and the results show that our algorithm exhibits favorable scalability for solving high-dimension problems.

关键词： Convex QCQP distributed algorithm Proximal method Parallel computing

来源：评论

学校读者我要写书评

暂无评论

A learning-based distributed algorithm for scheduling in multi-hop wireless networks

引用

JOURNAL OF COMMUNICATIONS AND NETWORKS 2022年第1期24卷 99-110页

作者： Park, Daehyun Kang, Sunjung Joo, Changhee UNIST ECE Ulsan South Korea OSU ECE Columbus OH USA Korea Univ CSE Seoul South Korea

We address the joint problem of learning and scheduling in multi-hop wireless network without a prior knowledge on link rates. Previous scheduling algorithms need the link rate information, and learning algorithms often require a centralized entity and polynomial complexity. These become a major obstacle to develop an efficient learning-based distributed scheme for resource allocation in large-scale multi-hop networks. In this work, by incorporating with learning algorithm, we develop provably efficient scheduling scheme under packet arrival dynamics without a priori link rate information. We extend the results to distributed implementation and evaluation their performance through simulations.

关键词： Wireless communication Spread spectrum communication Complexity theory Interference Wireless networks Heuristic algorithms Dynamic scheduling distributed algorithm learning multi-hop networks provable efficiency wireless scheduling

来源：评论

学校读者我要写书评

暂无评论

An efficient distributed algorithm for target-coverage preservation in wireless sensor networks

引用

PEER-TO-PEER NETWORKING AND APPLICATIONS 2021年第2期14卷 453-466页

作者： Nguyen, Tri Gia Phan, Trung V. Nguyen, Hai Hoang Aimtongkham, Phet So-In, Chakchai Duy Tan Univ Fac Informat Technol Danang 50206 Vietnam Duy Tan Univ Inst Res & Dev Danang 50206 Vietnam Tech Univ Chemnitz Chair Commun Networks D-09126 Chemnitz Germany Univ Danang Vietnam Korea Univ Informat & Commun Technol Fac Comp Sci Danang Vietnam Khon Kaen Univ Fac Sci Dept Comp Sci Appl Network Technol Lab Khon Kaen 40002 Thailand

Maximizing the full coverage lifetime over a predefined set of target points (TPs) is one of the most fundamental functions in wireless sensor networks. However, coverage performance is challenging to maintain due to the energy consumption of self-contained sensor nodes (SNs). Therefore, in this paper, we propose an energy-efficient distributed algorithm for target-coverage preservation (DATCP) that can rotate a group of SNs for the monitoring task in each time slot based on cover sets and the remaining energy to ensure preservation of coverage. Specifically, we first propose a novel SN clustering algorithm based on the location of the TPs to reduce the number of control messages. Next, we introduce a cover set construction algorithm to group SNs that can cover all TPs in a cluster. In addition, our approach considers the capability of multihop communication to improve the energy efficiency in the network. The results of extensive experiments show that substantial improvements in full coverage lifetime and energy efficiency compared to existing algorithms are obtained by our proposed algorithm: the full coverage lifetime can be enhanced more than 30 % compared to that of other approaches.

关键词： Target coverage distributed algorithm Clustering Energy-efficient Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Provably-Good distributed algorithm for Constrained Multi-Robot Task Assignment for Grouped Tasks

引用

IEEE TRANSACTIONS ON ROBOTICS 2015年第1期31卷 19-30页

作者： Luo, Lingzhi Chakraborty, Nilanjan Sycara, Katia Carnegie Mellon Univ Inst Robot Pittsburgh PA 15213 USA SUNY Stony Brook Dept Mech Engn Stony Brook NY 11794 USA

In this paper, we present provably-good distributed task assignment algorithms for a heterogeneous multi-robot system, in which the tasks form disjoint groups and there are constraints on the number of tasks a robot can do (both within the overall mission and within each task group). Each robot obtains a payoff (or incurs a cost) for each task and the overall objective for task allocation is to maximize (minimize) the total payoff (cost) of the robots. In general, existing algorithms for task allocation either assume that tasks are independent or do not provide performance guarantee for the situation, in which task constraints exist. We present a distributed algorithm to provide an almost optimal solution for our problem. The key aspect of our distributed algorithm is that the overall objective is (almost) maximized by each robot maximizing its own objective iteratively (using a modified payoff function based on an auxiliary variable, called price of a task). Our distributed algorithm is polynomial in the number of tasks, as well as the number of robots.

关键词： Auction algorithm distributed algorithm multirobot task assignment task allocation

来源：评论

学校读者我要写书评

暂无评论

A distributed algorithm for Reconstructing Time-Varying Graph Signals

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2022年第6期41卷 3624-3641页

作者： Chi, Yuan Jiang, Junzheng Zhou, Fang Xu, Shuwen Guilin Univ Elect Technol Guangxi Key Lab Wireless Wideband Commun & Signal Guilin 541004 Peoples R China Guilin Univ Elect Technol Sch Life & Environm Sci Guilin 541004 Peoples R China Xidian Univ Natl Lab Radar Signal Proc Xian 710071 Peoples R China

The reconstruction of time-varying signals on graphs is a prominent problem in graph signal processing community. By imposing the smoothness regularization over the time-vertex domain, the reconstruction problem can be formulated into an unconstrained optimization problem that minimizes the weighted sum of the data fidelity term and regularization term. In this paper, we propose an approximate Newton method to solve the problem in a distributed manner, which is applicable for spatially distributed systems consisting of agents with limited computation and communication capacity. The algorithm has low computational complexity while nearly maintains the fast convergence of the second-order methods, which is evidently better than the existing reconstruction algorithm based on the gradient descent method. The convergence of the proposed algorithm is explicitly proved. Numerical results verify the validity and fast convergence of the proposed algorithm.

关键词： Time-varying graph signal reconstruction distributed algorithm Matrix inverse approximation

来源：评论

学校读者我要写书评

暂无评论

A NEW OPTIMAL distributed algorithm FOR THE SET INTERSECTION PROBLEM

引用

INFORMATION PROCESSING LETTERS 1991年第3期38卷 143-148页

作者： RAJANARAYANAN, S IYENGAR, SS Department of Computer Science Louisiana State University Baton Rouge LA 70803 USA

A simple decentralized distributed algorithm for the set intersection problem is presented. This algorithm is an improvement of the previous bound for the problem and uses only 3m(n - 1) + 3(n - 1) messages, where m is the cardinality of the smallest-sized subset and n is the number of processors, compared to 5mn + 2n - 4m messages as proposed in a previous solution for the same problem. Our algorithm has a time complexity of O(mn).

关键词： distributed COMPUTING ASYNCHRONOUS SYSTEM CENTRALIZED PROTOCOL DECENTRALIZED PROTOCOL distributed algorithm LOWER BOUND SET INTERSECTION

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：