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

Enforcing consensus while monitoring the environment in Wireless Sensor Networks

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第7期56卷 3375-3380页

作者： Braca, Paolo Marano, Stefano Matta, Vincenzo Univ Salerno Elect & Informat Engn Dept I-84084 Fisciano SA Italy

In many environmental monitoring applications of Wireless Sensor Networks (WSNs), safe information retrieval from any subset of sensors, at an arbitrary instant of time, should be guaranteed. Accordingly, we study the behavior of a WSN that continuously senses the surrounding environment, while consensus among its nodes is simultaneously enforced. For this running consensus scheme, analytical bounds in terms of consensus degree and compsarison with an ideal centralized system are provided, and example of applications are presented.

关键词： gossip algorithms pairwise averaging running consensus Wireless Sensor Networks

来源：评论

学校读者我要写书评

暂无评论

Order-Optimal Consensus Through Randomized Path Averaging

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第10期56卷 5150-5167页

作者： Benezit, Florence Dimakis, Alexandros G. Thiran, Patrick Vetterli, Martin Ecole Polytech Fed Lausanne Sch IC CH-1015 Lausanne Switzerland Univ So Calif Dept Elect Engn Syst Los Angeles CA 90089 USA Ecole Polytech Fed Lausanne Swiss Fed Inst Technol DSC LCAV CH-1015 Lausanne Switzerland Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

gossip algorithms have recently received significant attention, mainly because they constitute simple and robust message-passing schemes for distributed information processing over networks. However, for many topologies that are realistic for wireless ad-hoc and sensor networks (like grids and random geometric graphs), the standard nearest-neighbor gossip converges as slowly as flooding (O(n(2)) messages). A recently proposed algorithm called geographic gossip improves gossip efficiency by a root n factor, by exploiting geographic information to enable multihop long-distance communications. This paper proves that a variation of geographic gossip that averages along routed paths, improves efficiency by an additional root n factor, and is order optimal (O(n) messages) for grids and random geometric graphs with high probability. We develop a general technique (travel agency method) based on Markov chain mixing time inequalities which can give bounds on the performance of randomized message-passing algorithms operating over various graph topologies.

关键词： Average consensus distributed algorithms gossip algorithms sensor networks

来源：评论

学校读者我要写书评

暂无评论

Improved Bounds for Max Consensus in Wireless Networks

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2019年第2期5卷 305-319页

作者： Nowzari, Aida Rabbat, Michael G. McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 0E9 Canada

In consensus problems, the goal is for the nodes of a network to converge to a certain quantity or a function of their values using local communications. In the maximum value consensus problem, the objective of these communications is for all the nodes to converge to the maximum of their initial values. There are two existing algorithms for the maximum value consensus problem in asynchronous networks: RANDOM-PAIRWISE-MAX and RANDOM-BROADCAST-MAX for which the bounds on the mean convergence time have been derived in the literature. In this paper, we derive tighter bounds on the expected convergence time of these two algorithms when run on grid networks and random geometric graphs, respectively-two models commonly used to capture salient properties of wireless networks. We show that RANDOM-PAIRWISE-MAX run on a 2-D grid graph with n nodes converges in expectation after O(n(3/2)) iterations, and RANDOM-BROADCAST-mAx run on a random geometric graph with n nodes converges in expectation after O((n/ log n)(3/2)) iterations. These bounds improve over the previous best-known upper bounds by factors of root n log n and log n + log(2) n, respectively. Experiments illustrate that the proposed bounds can be up to 95% tighter than the previous state-of-the-art bounds. Furthermore, we enhance the proposed bounds by introducing probabilistic network link failures, e.g., to model packet drops in wireless networks.

关键词： gossip algorithms agreement random geometric graphs grid topology

来源：评论

学校读者我要写书评

暂无评论

Non-Asymptotic Analysis of an Optimal Algorithm for Network-Constrained Averaging With Noisy Links

引用

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2011年第4期5卷 833-844页

作者： Noorshams, Nima Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

The problem of network-constrained averaging is to compute the average of a set of values distributed throughout a graph G using an algorithm that can pass messages only along graph edges. We study this problem in the noisy setting, in which the communication along each link is modeled by an additive white Gaussian noise channel. We propose a two-phase decentralized algorithm, and we use stochastic approximation methods in conjunction with the spectral graph theory to provide concrete (non-asymptotic) bounds on the mean-squared error. Having found such bounds, we analyze how the number of iterations T-G(n;delta) required to achieve mean-squared error delta scales as a function of the graph topology and the number of nodes n. Previous work provided guarantees with the number of iterations scaling inversely with the second smallest eigenvalue of the Laplacian. This paper gives an algorithm that reduces this graph dependence to the graph diameter, which is the best scaling possible.

关键词： Consensus averaging gossip algorithms non-asymptotic bounds optimal network scaling stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

Broadcast-Based Consensus With Non-Zero-Mean Stochastic Perturbations

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第6期59卷 3971-3989页

作者： Yang, Yang Blum, Rick S. Lehigh Univ Dept Elect & Comp Engn Bethlehem PA 18015 USA

Bolstered by the growing interest in building wireless sensor and ad hoc networks with applications ranging across different engineering disciplines, distributed consensus algorithms have recently seen a new revival since their inception in the early 1980s. Of particular interest is the recently developed broadcast-based consensus algorithm, which is one special type of randomized consensus algorithms and is amenable to practical implementation in wireless networks. This paper focuses on the performance analysis of this broadcast-based consensus algorithm in the presence of non-zero-mean stochastic perturbations. It is demonstrated that as the algorithm proceeds, the deviation of the node states from their average will converge, in expectation, to a fixed value, which is determined by the Laplacian matrix of the network, the mixing parameter, and the mean of the stochastic perturbations. Asymptotic upper and lower bounds on the total mean-square deviation are derived, which describe the range of distances over which the node states deviate from consensus. These bounds can facilitate evaluation of the applicability of this algorithm in practice. Results are also provided on the algorithm's epsilon-converging time, i.e., the earliest time at which the deviation is close to its steady value, and on the mean and mean-square behaviors of the displacement of node states from their initial states at large iteration number. As a special case study, performance of the broadcast-based consensus algorithm under zero-mean stochastic disturbances is analyzed, and results regarding its convergence, mean-square deviation, and mean-square displacement are given. The theoretical results presented in this study hold true regardless of the statistics of the stochastic disturbances, and are valid for arbitrary network topology as long as the topology is connected.

关键词： Broadcasting distributed consensus algorithms gossip algorithms network synchronization randomized consensus algorithms wireless ad hoc networks wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Performance of a Distributed Stochastic Approximation Algorithm

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2013年第11期59卷 7405-7418页

作者： Bianchi, Pascal Fort, Gersende Hachem, Walid Telecom ParisTech CNRS LTCI F-75634 Paris 13 France

In this paper, a distributed stochastic approximation algorithm is studied. Applications of such algorithms include decentralized estimation, optimization, control or computing. The algorithm consists in two steps: a local step, where each node in a network updates a local estimate using a stochastic approximation algorithm with decreasing step size, and a gossip step, where a node computes a local weighted average between its estimates and those of its neighbors. Convergence of the estimates toward a consensus is established under weak assumptions. The approach relies on two main ingredients: the existence of a Lyapunov function for the mean field in the agreement subspace, and a contraction property of the random matrices of weights in the subspace orthogonal to the agreement subspace. A second-order analysis of the algorithm is also performed under the form of a central limit Theorem. The Polyak-averaged version of the algorithm is also considered.

关键词： Convergence decentralized estimation decentralized optimization gossip algorithms stochastic approximation

来源：评论

学校读者我要写书评

暂无评论

Breaking the log n barrier on rumor spreading

引用

DISTRIBUTED COMPUTING 2018年第6期31卷 503-513页

作者： Avin, Chen Elsaesser, Robert Ben Gurion Univ Negev Commun Syst Engn Beer Sheva Israel Univ Salzburg Dept Comp Sci Salzburg Austria

O(log n) rounds has been a well known upper bound for rumor spreading using push& pull in the random phone call model (i. e., uniform gossip in the complete graph). A matching lower bound of O(log n) is also known for this special case. Under the assumption of this model and with a natural addition that nodes can call a partner once they learn its address (e. g., its IP address) we present a new distributed, address- oblivious and robust algorithm that uses push& pull with pointer jumping to spread a rumor to all nodes in only O(v log n) rounds, w. h. p. This algorithm can also cope with F = O(n/2 v log n) node failures, in which case all but O(F) nodes become informed within O(v log n) rounds, w. h. p.

关键词： Rumor spreading gossip algorithms Random phone call Push & pull

来源：评论

学校读者我要写书评

暂无评论

Distributed primal-dual stochastic subgradient algorithms for multi-agent optimization under inequality constraints

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2013年第16期23卷 1846-1868页

作者： Yuan, Deming Xu, Shengyuan Zhang, Baoyong Rong, Lina Nanjing Univ Sci & Technol Sch Automat Nanjing 210094 Jiangsu Peoples R China

We consider the multi-agent optimization problem where multiple agents try to cooperatively optimize the sum of their local convex objective functions, subject to global inequality constraints and a convex constraint set over a network. Through characterizing the primal and dual optimal solutions as the saddle points of the associated Lagrangian function, which can be evaluated with stochastic errors, we propose the distributed primal-dual stochastic subgradient algorithms for two cases: (i) the time model is synchronous and (ii) the time model is asynchronous. In the first case, we obtain bounds on the convergence properties of the algorithm for a diminishing step size. In the second case, for a constant step size, we establish some error bounds on the algorithm's performance. In particular, we prove that the error bounds scale as n root n in the number of n agents. Copyright (c) 2012 John Wiley & Sons, Ltd.

关键词： multi-agent systems convex optimization subgradient methods distributed average consensus gossip algorithms

来源：评论

学校读者我要写书评

暂无评论

A Distributed Particle Filter for Bearings-Only Tracking on Spherical Surfaces

引用

IEEE SIGNAL PROCESSING LETTERS 2016年第3期23卷 326-330页

作者： Yu, Jun Ye Coates, Mark J. Rabbat, Michael G. Blouin, Stephane McGill Univ ECE Dept Montreal PQ H3A 0E9 Canada Def Res & Dev Canada Atlantic Res Ctr Dartmouth NS B2Y 3Z7 Canada

We present a distributed particle filter for bearings-only tracking of a target moving on the surface of a sphere, such as Earth. The proposed filter accounts for the curvature of the surface in the measurement model for more robust performance. In addition, a linearization of the likelihood function significantly reduces the communication overhead. Simulations demonstrate that the proposed distributed approach maintains accuracy comparable to that of a centralized filter with access to all measurements even when the sensors and target are spread over a large region, where a planar approximation would fail.

关键词： Bearings-only tracking distributed particle filter gossip algorithms likelihood approximation

来源：评论

学校读者我要写书评

暂无评论

Distributed Voting/Ranking With Optimal Number of States per Node

引用

IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 2015年第4期1卷 259-267页

作者： Salehkaleybar, Saber Sharif-Nassab, Arsalan Golestani, S. Jamaloddin Sharif Univ Technol Dept Elect Engn Tehran Iran

Considering a network with n nodes, where each node initially votes for one (or more) choices out of K possible choices, we present a distributed multichoice voting/ranking (DMVR) algorithm to determine either the choice with maximum vote (the voting problem) or to rank all the choices in terms of their acquired votes (the ranking problem). The algorithm consolidates node votes across the network by updating the states of interacting nodes using two key operations: the union and the intersection. The proposed algorithm is simple, independent from network size, and easily scalable in terms of the number of choicesK, using only K x 2(K-1) nodal states for voting, and K x K! nodal states for ranking. We prove the number of states to be optimal in the ranking case;this optimality is conjectured to also apply to the voting case. The time complexity of the algorithm is analyzed in complete graphs. We show that the time complexity for both ranking and voting is O(log(n)) for given vote percentages, and is inversely proportional to the minimum of the vote percentage differences among various choices.

关键词： Majority voting problem ranking problem gossip algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：