IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 1, JANUARY 2009
355
Distributed Connsus Algorithms in Sensor Networks With Imperfect Communication: Link Failures and Channel Noi
Soummya Kar and José M. F. Moura, Fellow, IEEE
Abstract—The paper studies average connsus with random topologies (intermittent links) and noisy channels. Connsus with noi in the network links leads to the bias-variance dilemma—running connsus for long reduces the bias of the final average estimate but increas its variance. We prent two algorithm different compromis to this tradeoff: the modifies conventional connsus by forcing the weights to satisfy a persistence condition (slowly decaying to zero;) and the algorithm where the weights are constant but connsus is run for a fixed number of iterations , then it is restarted and rerun for a total of runs, and at the end averages the final states of the runs (Monte Carlo averaging). We u controlled Markov process and stochastic approximation arguments to prove almost sure convergence of to a finite connsus limit and compute explicitly the mean square error (m) (variance) of the connsus limit. We show that reprents the best of both worlds—zero bias an
d low variance—at the cost of a slow convergence rate; rescaling the weights balances the variance versus the rate of bias reduction (convergence rate). In contrast, , becau of its constant weights, converges fast but prents a different bias-variance tradeoff. For the same number of iterations , shorter runs (smaller ) lead to high bias but smaller variance (larger number of runs to average over.) For a static nonrandom network with Gaussian noi, we compute the optimal gain for to reach in the shortest number of iterations , with high probability (1 ), ( )-connsus ( residual bias). Our results hold under fairly general assumptions on the random link failures and communication noi. Index Terms—Additive noi, connsus, nsor networks, stochastic approximation, random topology.
I. INTRODUCTION
D
ISTRIBUTED computation in nsor networks is a wellstudied field with an extensive body of literature (e, for example, [1] for early work.) Average connsus computes iteratively the global average of distributed data using local communications, e [2]–[5] that consider versions and extensions of basic connsus. A review of the connsus literature is in [6].
Manuscript received November 25, 2007; revid August 31, 2008. First published October 31, 2008; current version published January 06, 2009. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Shahram Shahbazpanahi. This work was supported in part by the DARPA DSO Advanced Computing and Mathematics Program Integrated Sensing and Processing (ISP) Initiative under ARO grant DAAD19-02-1-0180, by the NSF by Grants ECS-0225449 and CNS-0428404, by an IBM Faculty Award, and by the Office of Naval Rearch under MURI N000140710747. The authors are with the Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213 USA (e-mail: u.edu; u.edu). Color versions of one or more of the figures in this paper are available online at ieeexplore.ieee. Digital Object Identifier 10.1109/TSP.2008.2007111
Reference [7] designs the optimal link weights that optimize the convergence rate of the connsus algorithm when the connectivity graph of the network is fixed (not random). Our previous work, [8]–[11], extends [7] by designing the topology, i.e., both the weights and the connectivity graph, under a variety of conditions, including random links and link communication costs, under a network communication budget constraint. We consider distributed average connsus when simultaneously
the network topology is random (link failures, like when packets are lost in data networks) and the communications among nsors is commonly noisy. A typical example is time division multiplexing, where in a particular ur’s time slot the channel may not be available, and, if available, we assume the communication is analog and noisy. Our approach can handle spatially correlated link failures and certain types of temporally Markovian quences of Laplacians and Markovian noi, which go beyond independently, identically distributed (i.i.d.) Laplacian matrices and i.i.d. communication noi quences. Noisy connsus leads to a tradeoff between bias and variance. Running connsus longer reduces bias, i.e., the mean of the error between the desired average and the connsus reached. But, due to noi, the variance of the limiting connsus grows with longer runs. To address this dilemma, we consider two versions of connsus with link failures and noi that reprent and the two different bias-variance tradeoffs: the algorithms. updates each nsor state with a weighted fusion of its current neighbors’ states (received distorted by noi). The satisfy a persistence condition, decreasing fusion weights to zero, but not too fast. falls under the purview of controlled Markov process, and we u stochastic approximation techniques to prove its almost sure (a.s.) connsus when the network is connected on the average: the nsor state vector quence converges a.s. to the connsus subspace. A simple con, for connectedness is dition on the mean Laplacian, . We establish that the nsor on its cond eigenvalue states converge asymp
totically a.s. to a finite random variable and, in particular, the expected nsor states converge to the desired average (asymptotic unbiadness.) We determine the variance of , which is the mean square error (m) between and the desired average. By properly tuning the weights quence , the variance of can be made arbitrarily small, s convergence rate, i.e., the though at a cost of slowing rate at which the bias goes to zero. is a repeated averaging algorithm that performs in-network Monte Carlo simulations: it runs connsus times
1053-587X/$25.00 © 2008 IEEE
Authorized licend u limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:51 from IEEE Xplore. Restrictions apply.
356
检场IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 1, JANUARY 2009
with constant weight , for a fixed number of iterations each time, and then each nsor averages its values of the state s constant weight at the final iteration of each run. speeds its convergence rate relative to s, who decrea to zero. We determine the number of weights iterations required to rea
ch -connsus, i.e., for the bias , of the connsus limit at each nsor to be smaller than . For nonrandom networks, we with high probability establish a tight upper bound on the minimizing and compute the corresponding optimal constant weight . We quantify the tradeoff between the number of iterations per Monte Carlo run and the number of runs . Finally, we compare the bias-variance tradeoffs between the two algorithms and the network parameters that determine their convergence rate and noi resilience. The fixed weight algorithm can converge faster but requires greater internsor coordination than the algorithm. A. Comparison With Existing Literature Random link failures and additive channel noi have been considered parately. Random link failures, but noiless connsus, is in [11]–[16]. References [11]–[13] assume an erasure model: the network links fail independently in space (independently of each other) and in time (link failure events are temporally independent.) Papers [14] and [16] study directed topologies with only time i.i.d. link failures, but impo distributional assumptions on the link formation process. In [15], the link failures are i.i.d. Laplacian matrices, the graph is directed, and no distributional assumptions are made on the Laplacian matrices. The paper prents necessary and sufficient conditions for connsus using the ergodicity of products of stochastic matrices. Similarly, [17]–[19] consider connsus with additive noi, but fixed or static, nonrandom topologies (no link failures.) They u a decreasing weight quence to guarantee connsus. The references do not characterize the m. For exam
ple, [18] and [19] rely on the existence of a unique solution to an algebraic Lyapunov equation. The more general problem of distributed estimation (of which average connsus is a special ca) in the prence of additive noi is in [20], again with a fixed topology. Both [17] and [20] assume a temporally white noi quence, while our approach can accommodate a more general Markovian noi quence, in addition to white noi process. In summary, with respect to [11]–[20], our approach considers: i) random topologies and noisy communication links simultaneously; ii) spatially correlated (Markovian) dependent random link failures; iii) time Markovian noi quences; iv) undirected topologies; v) no distributional assumptions; vi) connsus (estimation being considered elwhere); and vii) two versions of connsus reprenting different compromis of bias versus variance. Briefly, the paper is as follows. Sections II and III summarize relevant spectral graph and average connsus results. Sections IV and V treat the additive noi with random link failure communication analyzing the and algorithms, respectively. Finally, Section VI concludes the paper.
II. ELEMENTARY SPECTRAL GRAPH THEORY We summarize briefly facts from spectral graph theory. For , is the t of an undirected graph , and is the t of edges . nodes or vertices The unordered pair if there exists an edge between nodes and . We only consider simple graphs, i.e., graphs devoid of lf-loops and multiple edges. A path between nodes and of length is a quence o
f . A graph vertices, such that, is connected if there exists a path, between each pair of nodes. The neighborhood of node is (1) Node has degree (number of edges with as one end point.) The structure of the graph can be described adjacency matrix, , by the symmetric , if , 0 otherwi. Let the degree matrix . The graph be the diagonal matrix is Laplacian matrix (2) The Laplacian is a positive midefinite matrix; hence, its eigenvalues can be ordered as (3) The multiplicity of the zero eigenvalue equals the number of connected components of the network; for a connected graph . This cond eigenvalue is the algebraic connectivity or the Fiedler value of the network; e [21]–[23] for detailed treatment of graphs and their spectral theory. III. DISTRIBUTED AVERAGE CONSENSUS WITH IMPERFECT COMMUNICATION In a simple form, distributed average connsus computes the average of the initial node data (4) by local data exchanges among neighbors. For noiless and unquantized data exchanges across the network links, the state of each node is updated iteratively by
goldberg
(5)
s, may be constant or time varying. where the link weights, Similarly, the topology of a time-varying network is captured s, to be a function of time. by making the neighborhoods Becau noi caus connsus to diverge, [10], [24], we let
Authorized licend u limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:51 from IEEE Xplore. Restrictions apply.
KAR AND MOURA: LINK FAILURES AND CHANNEL NOISE
恒星英语学习网
357我爱你的英语
小学生英语the link weights to be the same across different network links, but vary with time. Equation (5) becomes
1.1) Temporally i.i.d. Laplacian Matrices: The graph Laplacians are (11)
(6) We address connsus with imperfect internsor communication, where each nsor receives noi corrupted versions of its neighbors’ states. We modify the state update (6) to
(7) where is a quence of functions (possibly random) modeling the channel imperfections. In the following ctions, we analyze the connsus problem given by (7), when the channel communication is corrupted by additive noi. In [25], we consider the effects of quantization (e also [26] for a treatment of connsus algorithms with quantized communication.) Here, we study two different algorithms. The first, , considers a decreasing weight quence ( ) , us reand is analy
zed in Section IV. The cond, peated averaging with a constant link weight and is detailed in Section V. IV. : CONSENSUS IN ADDITIVE NOISE AND RANDOM LINK FAILURES
We consider distributed connsus when the network links fail or become alive at random times, and data exchanges are corrupted by additive noi. The network topology varies randomly across iterations. We analyze the convergence properties algorithm under this generic scenario. We start of the in the next by formalizing the assumptions underlying Subction. A. Problem Formulation and Assumptions We compute the average of the initial state with the distributed connsus algorithm with communication channel imperfections given be a quence of independent in (7). Let zero mean random variables. For additive noi, (8) Recall the Laplacian defined in (2). Collecting the states in the vector , (7) is (9) (10) We now state the assumptions of the algorithm.1 1) Random Network Failure: We propo two models; the cond is more general than the first.
1See
is a quence of i.i.d. Laplacian mawhere , such that . trices with mean We do not make any distributional assumptions on the link failure model, and, in fact, as long as the is independent with constant quence , the i.i.d. assumption mean , satisfying can be dropped. During the same iteratio
n, the link failures can be spatially dependent, i.e., correlated across different edges of the network. This model subsumes the erasure network model, where the link failures are independent both over space and time. Wireless nsor networks motivate this model since interference among the nsors communication correlates the link failures over space, while over time, it is still reasonable to assume that the channels are memoryless or independent. Connectedness of the graph is an important issue. We of do not require that the random instantiations the graph be connected; in fact, it is possible to have all the instantiations to be disconnected. We only require that the graph stays connected on average. This , enabling us is captured by requiring that to capture a broad class of asynchronous communication models; for example, the random asynchronous gossip protocol analyzed in [28] satisfies and hence falls under this framework. 1.2) Temporally Markovian Laplacian Matrices: Our results hold when the Laplacian matrix quence is state-dependent. More precily, we assume that there exists a two-parameter random of Laplacian matrices such field, that (12) and . We also require that, for a fixed , the random matrices, , are independent of the sigma algebra, .2 It is clear then that the Laplacian matrix quence, , is Markov. We will show that our convergence analysis holds also for this general link failure model. Such a model may be appropriate in stochastic formation control scenarios, e [29]–[31], where the network topology is state-dependent. 2) Communication Noi Model: We propo two models; the cond is more general than the first. 2.1) Independent Noi Sequence : The additive noi is an independent quence
(13)
i miss you 是什么意思2This guarantees that the Laplacian L(i; x(i)) may depend on the past state history fx(j ); j ig, only through the prent state x(i).
also [27], where parts of the results are prented.
Authorized licend u limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:51 from IEEE Xplore. Restrictions apply.
358
IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 57, NO. 1, JANUARY 2009
The quences, and are mutually independent. Hence, , , , are independent of , . Then, from (10)
(14) No distributional assumptions are required on the noi quence. 2.2) Markovian Noi Sequence: Our approach allows the noi quence to be Markovian through state-dependence. Let the two-parameter random field, of random vectors (15) are For fixed , the random vectors independent of the -algebra, and the random families and are independent. It is clear then is that the
noi vector quence Markov. Note, however, in this ca the resulting and Laplacian and noi quences are no longer independent; they are . In addition to (15), we coupled through the state require the variance of the noi component orthogonal to the connsus subspace [e (31)] to satisfy, for constants (16) We do not restrict the variance growth rate of the noi component in the connsus subspace. This clearly subsumes the bounded noi variance model. An example of such noi is (17) and are zero mean finite where variance mutually i.i.d. quences of scalars and vectors, respectively. It is then clear that the condition in (16) is satisfied, and the noi model 2.2) applies. The model in (17) aris, for example, in multipath effects in MIMO systems, when the channel adds multiplicative noi who amplitude is proportional to the transmitted data. 3) Persistence Condition: The weights decay to zero, but not too fast (18)
For clarity, in the main body of the paper, we prove the results algorithm under Assumptions 1.1), 2.1), and for the 3). In the Appendix, we point out how to modify the proofs when the more general assumptions 1.2) and 2.2) hold. We now prove the almost sure (a.s.) convergence of the algorithm in (9) by using results from the theory of stochastic approximation algorithms [32]. B. A Result on Convergence of Markov Process A systematic and thorough treatment of stochastic approximation procedures has been given in [32]. In this ction, we modify slightly a result from [32] and restate it
as a theorem in a form relevant to our application. We follow the notation of [32], which we now introduce. be a Markov process on . The genLet erating operator of is (20) , provided the condifor functions tional expectation exists. We say that in a domain , if is finite for all . . For , the Denote the Euclidean metric by -neighborhood of and its complement is (21) (22) We now state the desired theorem, who proof we sketch in the Appendix. Theorem 1: Let be a Markov process with generating operator . Let there exist a nonnegative function in the domain , and with the following properties: 1) (23) (24) (25) 2) (26) where such that is a nonnegative functionjedward
(27) 3) This condition is commonly assumed in adaptive control and signal processing. Examples include (19) (28) (29)
Authorized licend u limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:51 from IEEE Xplore. Restrictions apply.
KAR AND MOURA: LINK FAILURES AND CHANNEL NOISE
359
Then, the Markov process distribution converges a.s. to
as
with arbitrary initial . In other words, (30)
Now consider
in (20). Using (9) in (20), we obtain初一英语
Proof of Convergence of the
英语四级成绩什么时候出来Algorithm (38) and with respect to , Using the independence of and are zero-mean, and that the subspace lies that in the null space of and (the latter becau this is true for both and ), (38) leads successively to
The distributed connsus algorithm is given by (9) in Section IV-A. To establish its a.s. convergence using Theorem 1, define the connsus subspace, , aligned with , the vector of 1s, (31) to be ud in We recall a result on distance properties in the quel. We omit the proof. . For , Lemma 2: Let be a subspace of consider the orthogonal decomposition . Then . a.s. convergence) Let assumptions Theorem 3: ( connsus al1.1), 2.1) , and 3) hold. Consider the gorithm in (9) in Section IV-A with initial state . Then, (32) Proof: Under the assumptions, the process is Markov. Define (33) is nonnega
tive. Since The potential function an eigenvector of with zero eigenvalue is
(39) are less The last step follows becau all the eigenvalues of in absolute value, by the Gershgorin circle theorem. than Now, by the fact and , we have
(34) . The cond condition follows from the continuity of By Lemma 2 and the definition in (22) of the complement of the -neighborhood of a t (35) Hence, for ,
(40) where
(36) (note that the asThen, since by assumption 1.1) comes into play here), we get sumption It is easy to e that and conditions for Theorem 2. Hence,
(41) defined above satisfy the
(42) (37)
Authorized licend u limited to: Carnegie Mellon Libraries. Downloaded on January 16, 2010 at 17:51 from IEEE Xplore. Restrictions apply.hostage
