Event-Triggered Differentially Private Average Consensus for Multi-agent Network

Ⅰ. INTRODUCTION

Mnetwork systems (MANSs) have been one of the focal points from many researchers due to its extensively real applications in a variety of scopes, such as biological systems, robotic teams, sensor networks, unmanned air vehicles formations, just to name a few [1]-[7]. Particularly, consensus problem, as a basic building block of MANSs' collective behaviors, has been widely investigated [8]-[14]. Moreover, a survey about theory and applications of consensus problems for MANSs is presented in [15]. The consensus of MANSs is that the states of all agents reach a common value by exchanging information among agents [16]-[22].

Recently, there is an increasing interest that is to apply the notion of privacy preserving into the consensus behaviors of the dynamical network systems (DNSs) [23]. It means that the network agents may not want to expose their initial states in the process of consensus computation. For example, in social networks (SNs), a group of individuals execute a prescribed procedure to obtain the common opinion on a subject [24] in which individual, however, may not want to divulgate its own true views on the subject. Subsequently, a few literatures have successfully studied the preserving-privacy problem in the context of consensus of MANSs [25]-[27]. It means that the algorithm not only achieves the agents' consensus, but also preserves the privacy of each agent' initial state against the other all agents. For example, privacy-preserving average consensus algorithms for MANSs are developed in [25] and [26]. The former just gives the condition that the initial state of one agent can be exactly recognized by the other agents. This motivates the latter to provide a quantitative condition that the initial state can be estimated perfectly. To extend the research of this filed, Duan et al. [27] propose a new privacy-preserving scheme and apply it to the maximum consensus algorithm for MANSs. The probability that the maximum state owner's identity is recognized by its neighbors is calculated. Later, differentially private, as an existing preserving-privacy approach, has gained remarkable attention due to its rigorous formulation and proven security properties, including resilience to post-processing and side information, and independence from the model of the adversary. Recently, there are a large number of results concerning the differentially private consensus problem for MANSs [28]-[31]. Huang et al. [28] firstly investigate the differentially private problem in the context of consensus of MANSs. Differentially private maximum consensus algorithm which achieves $\epsilon$-differentially private for initial states of all agents and makes all agents converge to the maximum initial state value is developed [29]. For the common average consensus of MANSs, Nozari et al. [30] show that any differentially private algorithm cannot achieve exact average consensus. Following it, the authors in [30] systematically analyze the differentially private average consensus problem of MANSs in expectation [31]. This observation motivates us to develop different types of differentially private consensus algorithms (DPCAs) to preserve the initial states of the MANSs as well as achieve consensus for all agents' states.

It is worth noting that, on the other hand, the privacy-preserving consensus algorithms in [28]-[31] are continuous communication between agents and their neighbors. Continuous communication results in the waste of network resources and possibility blocks channels due to the mass of transmission data, which drives us to employ the intermittent communication techniques (ICTs). The event-triggered control (ETC) strategy, as a classical ICT, has successfully been applied to consensus control problem of the different kinds of MANSs for dramatically reducing communication among agents [32]-[43]. Model-based ETC is used for MANSs with quantization and time-varying delays [32]. Moreover, the ETC is proved to be an effective approach for the cooperative control problem of the nonlinear MANSs with unknown external disturbance [36], [37]. Based on the point, the latest article [44] firstly adopts the event-triggered scheme to the algorithm in [31]. To the best of authors' knowledge, there are few work to employ the ETC strategy in DPCA except for [44]. This observation inspires us to develop the corresponding ETC in some new DPCAs for reducing the communication among agents.

Motivated by the existing research in the above literature, in this paper, we develop a new event-triggered update law for all agents in MANSs as our differentially private consensus algorithm. The primary advantage of our proposed algorithm is that the mean square consensus of all agents in MANSs and the preservation of the privacy of each agent can be guaranteed simultaneously. In detail, the main contributions of our work are threefold: 1) A new distributed event-triggered DPCA is established for MANSs by introducing ETC strategy, which dramatically reduces the mutual communications among the agents. 2) Based on our algorithm, we carry out the detailed theoretical analysis, including its consensus, accuracy and differential privacy. Meanwhile, the sufficient condition of consensus, and its accuracy are derived, respectively. 3) An optimization problem is established to minimize the variance of the agents' convergence point according to the tradeoff between privacy level and algorithm's performance. It is found that the optimal value of the variance can be derived for the given privacy level.

The remainder of this paper is structured as follows. Section Ⅱ introduces the preliminaries for graph theory and probability theory, present the DPCA. The main results are established in Section Ⅲ, including three parts. First, the convergence analysis of the DPCA is presented. Second, the accuracy and differential privacy of the DPCA are guaranteed. Third, the optimization problem to minimize the variance of the agents' convergence point is established. Section Ⅳ provides some numerical examples to testify the validity of our results. Section Ⅴ contains some main conclusions and further research.

Ⅱ. PROBLEM FORMULATION

A Communication Network Topology

We consider a network of $N$ agents interacting over a network topology modeled as an undirected and connected communication graph $g = (V, \;\varepsilon , \;A)$. $V = \{ 1, \;2, \;\ldots, \;N\}$ is a set of vertices and $\varepsilon \subseteq V \times V$ is a set of communication edge. $\left( {i, j} \right) \in \varepsilon$ means that there is an edge between $j$ and $i$. The neighbor set of agent $i$ is defined as ${N_i} = \left\{ {j \in V|\left( {i, j} \right) \in \varepsilon } \right\}$. Note that $i \in {N_i}$, which means that there exists a self-loop for agent $i$. The cardinality of $N_i$ for agent $i$ is $| {{N_i}} |$. $A = {({a_{ij}})_{N \times N}}$ is the connection weighted matrix of the graph $g$. The degree of agent $i$ is defined as ${d_i} = \sum\nolimits_{j \in {N_i}} {{a_{ij}}}$ and the Laplacian of the weighted digraph $g$ is defined as $L=D-A$ with $D = {\text{diag}}\left\{ {{d_1}, {d_2}, \ldots, {d_N}} \right\}$. The graph $g$ is connected if and only if for any two distinct agents $i, j\in V$, there is a path between $j$ and $i$. Here, we order the eigenvalues of the matrix $A$ in the decreasing order as ${\lambda _1}\left( A \right) \ge {\lambda _2}\left( A \right) \ge \cdots \ge {\lambda _N}\left( A \right)$ and the eigenvalues of the Laplacian matrix $L$ in the decreasing order as ${\lambda _1}\left( L \right) \ge {\lambda _2}\left( L \right) \ge \cdots \ge {\lambda _N}\left( L \right) = 0$.

B Probability Theory

Consider the probability space $\left( {\Omega , \Sigma , \Pr } \right)$, where, as usual, $\Omega$ is the sample space, $\Sigma$ is the collection of all events, and $\Pr$ is the probability measure. A random variable is a measurable function $X:\omega \in \Omega \to R$, and we denote its expected value by $E[X]$. The variance of $X$ is represented by ${\mathop{\rm var}} \left( X \right)$ with ${\mathop{\rm var}} \left( X \right) = E\left[ {{X^2}} \right] - E\left[ X \right]E\left[ X \right]$. $X \sim Lap\left( b \right)$ means that a zero mean random variable $X$ obeys the Laplace distribution with its variance $2b^2$. Its PDF is that $f\left( {x;b} \right) = \frac{1}{{2b}}{e^{ - \frac{{\left| x \right|}}{b}}}$ for any $x\in \mathbb{R}$.

C Algorithm Description

In this section, we develop a new update law of the discrete-time DPCA for each agent in MANSs as follows:

where $0 < {\alpha _i}, {\beta _i} < 1$ are the algorithm parameters, $x_i(t)$ is the state of the agent $i$, $\theta_i(t)$ is the state sending to its neighbors, and $\eta_i(t)$ is the random noise, which obeys the Laplace distribution $Lap\left( {{c_i}q_i^t} \right)$ with $q_i\in (0, 1)$ and the positive constant $c_i$.

It is clearly seen that the communication among agents is continuous in the algorithm (1), which results in the waste of network resources. Motivated by this observation, the event-triggered DPCA is established as follows:

where $t_k^j$ is the event-triggered time instant for the agent $j$, and the next trigged time instant $t_{k + 1}^i$ is determined by

where ${e_i}\left( t \right)$ is measure error with ${e_i}\left( t \right) = {\theta _i}\left( {t_k^j} \right) - {\theta _i}\left( t \right)$, and $0 < {\sigma _i} < 1$. The execution process of the algorithm (2) can be described as Fig. 1, where the control input $u_i(t)$ is denoted by $u_i(t)=\sum\nolimits_{j \in {N_i}} {{a_{ij}}{\theta _j}\left( {t_k^j} \right)}$, $i$ is a neighbor of agent $j$, and $f_i(t)$ represents the event function with ${f_i}\left( t \right) = \left| {{e_i}\left( t \right)} \right| - {\sigma _i}\left| {\sum\nolimits_{j \in {N_i}} {{\theta _j}\left( {t_k^j} \right) - {\theta _i}\left( {t_k^i} \right)} } \right|$.

Figure  1.  The event-triggered DPCA schematic architecture.

DownLoad: Full-Size Img PowerPoint

Remark 1: Our triggered condition (3) is more conservative. Admittedly, the triggered condition (3) is really not easy to satisfy due to the "=". But it is possible to satisfy if the size step is small enough. And, this similar form for event-triggered condition can be found in [45].

Remark 2: The proposed algorithm (1) is derived from the distributed algorithms (6)-(7) in [30], which is as follows:

However, the algorithm (4) can be viewed as a special case of our algorithm (1). It can be clearly seen that the parameters $0 < {\alpha _i}, {\beta _i} < 1$ in our algorithm is more general than ones in [30]. On the other hand, the algorithm in [31] can be expressed as:

As the extension of the algorithm in [31], the latest article [44] adopts the event-triggered scheme to the algorithm (5), which forms the following:

Note that without the term $s_i\eta_i(t)$, the differentially privacy cannot be guaranteed, as is described in [31], [44]. Generally, for the general DPCA, the term $s_i\eta_i(t)$ need not be included in the second equation. Actually, the term $s_i\eta_i(t)$ have to be added to the algorithm (5) due to using the relative agents' information, which increases the computation load. Hence, the observation motivates us to use the absolute information such that the term $s_i\eta_i(t)$ can be abandoned, which yields our algorithm (1).

Based on the above discussion, our algorithm (2) dramatically reduces the communication among agents by employing the ETC strategy, which is the main difference compared with algorithms in [30], [31]. And, the main differences from the [44] have three points: 1) Our algorithm uses the absolute information, which reduces the computation load between neighbors. 2) Our algorithm guarantees that every agent converges to the weighted average of initial states for all agents instead of the average of initial states in mean square. 3) In this paper, based on our algorithm, we further analyze the best achievable accuracy of our algorithm under the free parameters and the fixed privacy level.

In the following, some basic definitions and assumption are given.

Definition 1 (Convergence) [28]: The agents of MANSs are said to reach consensus in mean square if for any agents $i, j = 1, 2, \ldots, N$, $\mathop {\lim }\limits_{t \to \infty } E{\left( {{x_i}\left( t \right) - {x_j}\left( t \right)} \right)^2} = 0$ holds, where the expectation is over the coin-flips of the algorithm.

Definition 2 (Adjacency) [28]: Given $\delta>0$, the initial states of the two groups of network agents $x_i^{\left( 2 \right)}\left( 0 \right), x_i^{\left( 1 \right)}\left( 0 \right)$ are $\delta$-adjacent, if there exists some $i_0$ such that

Definition 3 (Differential Privacy) [28]: The algorithm (2) is $\epsilon$-differential privacy for any pair $x_i^{\left( 2 \right)}\left( 0 \right)$ and $x_i^{\left( 1 \right)}\left( 0 \right)$ of $\delta$-adjacent initial states, if

holds, where ${\rm{Alg}}\left( \cdot \right)$ represents the execution of the algorithm (2), and $\Xi$ denotes the state domain of global execution.

Definition 4 (Accuracy) [28]: For any initial state ${x_i}\left( 0 \right)$ and $p \in \left[ {0, 1} \right]$, the algorithm (2) is $(p, r)$-accuracy, if the network state $x_i(t)$ converges to $x_\infty$ as $t \to \infty$ with $E\left[ {{x_\infty }} \right] < \infty$ and $\Pr \left[ {\left| {{x_\infty } - E\left[ {{x_\infty }} \right]} \right| \le r} \right] \ge 1 - p$ holds.

Assumption 1: We assume that the communication topology considered in this paper is undirected and connected. And, the connection matrix $A$ satisfies $A \cdot 1 = 1$.

Remark 3: Assumption 1 guarantees that $A$ is symmetric matrix with ${\lambda _1}\left( A \right) = 1$ and $L$ is a positive semi-definite matrix with ${\lambda _N}\left( L \right) = 0$.

Ⅲ. MAIN RESULTS

In this section, we establish some main results based on our proposed DPCA, including the convergence analysis, the accuracy, differential privacy and the optimal solution for the optimization problem to minimize the variance of the agents' convergence point.

A Convergence Analysis

Lemma 1: For any $\varepsilon , \delta$, our proposed DPCA cannot guarantee the any type of convergence to the exact average of the initial states of the network agents.

Remark 4: Our algorithm (2) is the special case of the algorithm in [31], which is as follows:

where $f\left( \cdot \right)$ and $h\left( \cdot \right)$ are continuous function.

The similar proof has been given in Proposition 4.1 of [31]. Here, we omit it.

Substituting ${e_i}\left( t \right) = {\theta _i}\left( {t_k^j} \right) - {\theta _i}\left( t \right)$ into the second equation of (2), we rewrite (2) in the vector form as follows:

where $\alpha = {\text{diag}}\left\{ {{\alpha _1}, {\alpha _2}, \ldots, {\alpha _N}} \right\}$, $\beta = {\text{diag}}\left\{ {{\beta _1}, {\beta _2}, \ldots, {\beta _N}} \right\}$ and $e\left( t \right) = {\left[ {{e_1}\left( t \right), {e_2}\left( t \right), \ldots, {e_N}\left( t \right)} \right]^T}$.

According to the triggered condition (3), we have:

where $\sigma = {\text{diag}}\left\{ {{{\hat \sigma }_1}, {{\hat \sigma }_2}, \ldots, {{\hat \sigma }_N}} \right\}$ with ${\hat \sigma _i} = - {\sigma _i}$ or $\sigma _i$. Then, (10) can be rewritten as:

Substituting (11) into the second equation of (10) yields:

Theorem 1: Under Assumption 1, algorithm (2) achieves the mean square asymptotic convergence for all agents if $\mathop {\max }\limits_i \left( {{\alpha _i} + {\kappa _i}} \right) < 1$ holds with ${\kappa _i} = {\beta _i}{\left( {1 - {\sigma _i}} \right)^{ - 1}}$.

Proof: Define a function as

The matrix form of (13) is $P\left( t \right) = \frac{1}{2}{x^T}\left( t \right)Lx\left( t \right)$. Following by (12), we have:

where $\Gamma = {\left( {I - \sigma } \right)^{ - 1}}A\beta$. Taking expectation of both sides of (13) and applying the inequality technology to every term yields:

where ${\kappa _i} = {\beta _i}{\left( {1 - {\sigma _i}} \right)^{ - 1}}$, $\lambda_1(L)$ is defined in theory graph section. If $\mathop {\max }\limits_i \left( {{\alpha _i} + {\kappa _i}} \right) < 1$, the first term of (12) converges to 0 as $t \to \infty$. For the second term $E\left[ {{\eta ^T}\left( t \right)\eta \left( t \right)} \right]$, $\eta_i(t)$ obeys the Laplace distribution $Lap\left( {c{q^t}} \right)$, $E\left[ {\eta _i^2\left( t \right)} \right] = {\rm{var}}\left[ {{\eta _i}\left( t \right)} \right] = 2c_i^2q_i^{2t}$. Hence, we have $E\left[ {P\left( t \right)} \right] \to 0, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} t \to \infty$. The algorithm (2) achieves the mean square asymptotic convergence.

Remark 5: It is worth noting that zeno-behaviors of our event-triggered communication scheme can be rule out. This is because our algorithm considered in this paper is a discrete-time system with a constant sampling interval (one step size). In other words, the event detection only occurs at each constant sampling time instant so that the number of event-triggered is finite in a certain interval (the worst-case is number of the time intervals). Hence, the zeno-behaviors won't happen.

B Accuracy Analysis

In the subsection, the average of the network agents' states is proved to converge to the weighted average of their initial states in the mean square. The accuracy of algorithm (2) is given in the following Theorem.

Theorem 2: Under the event-triggered condition (3), if the parameters satisfy ${\gamma _i} = \frac{{\left| {{N_i}} \right|}}{{1 - {\alpha _i}}}$, ${\beta _i} = \frac{{\left( {1 - {\sigma _i}} \right)\left( {1 - {\alpha _i}} \right)}}{{\left| {{N_i}} \right|}}$ and $0 < {\alpha _i} < 1$, algorithm (2) achieves $(p, r)$-accuracy, where $r = \sqrt {\sum\nolimits_{i = 1}^N {\frac{{2c_i^2d}}{{1 - q_i^2}}} } /\sqrt p$, $d = \frac{{{{\left( {\mathop {\max }\limits_i \left( {\left| {{N_i}} \right|} \right)} \right)}^2}}}{{{{\left( {\sum\nolimits_{i = 1}^N {{\gamma _i}} } \right)}^2}}}$, $0<p<1$ and $\gamma_i$ is the weight.

Proof: We can rewrite (12) in the distributed form as:

We define the weighted average $\bar x\left( t \right) = \frac{{\sum\nolimits_{i = 1}^N {{\gamma _i}{x_i}\left( t \right)} }}{{\sum\nolimits_{i = 1}^N {{\gamma _i}} }}$. Then, we have

Let ${\gamma _i} = \frac{{{N_i}}}{{1 - {\alpha _i}}}, 0 < {\alpha _i} < 1$ and ${\gamma _i} = \frac{1}{{{\beta _i}{{\left( {1 - {\sigma _i}} \right)}^{ - 1}}}}$, (14) is rewritten as:

It follows from (18) that

where $\tilde w\left( t \right) = \frac{{\sum\nolimits_{i = 1}^N {{w_i}\left( t \right)} }}{{\sum\nolimits_{i = 1}^N {{\gamma _i}} }}$ with ${w_i}\left( t \right) = \sum\nolimits_{j \in {N_i}} {{a_{ij}}{\eta _j}\left( t \right)}$. By the iteration, (19) is rewritten as:

According to (20) and ${\eta _i}\left( t \right), \forall i, t$ is independent, we have

By (20), the variance of $\tilde w\left( t \right)$ is

where $d = \frac{{{{\left( {\mathop {\max }\limits_i \left( {\left| {{N_i}} \right|} \right)} \right)}^2}}}{{{{\left( {\sum\nolimits_{i = 1}^N {{\gamma _i}} } \right)}^2}}}$ and ${q_i}\forall i \in \left( {0, 1} \right)$. Following (22), we have

According to Chebyshev's inequality for any, we have

Choosing $r = \frac{{\sqrt {{\mathop{\rm var}} \left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)} }}{{\sqrt p }} = \frac{{\sqrt {\sum\nolimits_{i = 1}^N {\frac{{2c_i^2d}}{{1 - q_i^2}}} } }}{{\sqrt p }}$, we have $1 - \Pr \left( {\left| {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right| > r} \right) \ge 1 - p$, which implies that the algorithm (2) achieves $\left( {p, r = \sqrt {\sum\nolimits_{i = 1}^N {\frac{{2c_i^2d}}{{1 - q_i^2}}} } /\sqrt p } \right)$-accuracy.

Remark 6: Theorem 1 means that algorithm (2) achieves the mean square asymptotic convergence. Then Theorem 2 implies that the average of the network agents' states converges to the weighted average of their initial states in the mean square with its variance as $\sum\nolimits_{i = 1}^N {\frac{{2c_i^2d}}{{1 - q_i^2}}}$. Hence, it follows from the results of Theorem 1 and Theorem 2 that the network agents converge to the weighted average of their initial states in the mean square.

C Differential Privacy Analysis

In the section, we aim to investigate the differential privacy property of the algorithm (2). Here, without loss of generality, a pair of $\delta$-adjacent initial states $x_i^{\left( 2 \right)}\left( 0 \right), x_i^{\left( 1 \right)}\left( 0 \right)$ is considered as follows:

In this paper, two groups of random noise $\eta _i^{(1)}\left( t \right)$ and $\eta _i^{(2)}\left( t \right)$ in our algorithm (2) are designed as follows:

where $t \in \left\{ {0, 1, \ldots} \right\}$. According to (25)-(26), we obtain the relationship between $x _i^{(2)}\left( t \right)$ and $x_i^{(1)}\left( t \right)$.

Proposition 1: According to the update (26), for $t \in \left\{ {0, 1, ...} \right\}$, we have $\theta _i^{\left( 2 \right)}\left( t \right) = \theta _i^{\left( 1 \right)}\left( t \right), \forall i$ and

Proof: Next, we will prove (27) by mathematical induction. Let us start with $t=0$, note that for $i= i_0$, $\theta _{{i_0}}^{\left( 2 \right)}\left( 0 \right) = x_{{i_0}}^{\left( 2 \right)}\left( 0 \right) + \eta _{{i_0}}^{\left( 2 \right)}\left( 0 \right) = x_{{i_0}}^{\left( 1 \right)}\left( 0 \right) + \delta + \eta _{{i_0}}^{(1)}\left( 0 \right) - \delta = \theta _{{i_0}}^{\left( 1 \right)}\left( 0 \right)$. For $i\neq i_0$, we have $\theta _i^{\left( 2 \right)}\left( 0 \right) = x_i^{\left( 2 \right)}\left( 0 \right) + \eta _i^{\left( 2 \right)}\left( 0 \right) = x_i^{\left( 1 \right)}\left( 0 \right) + \eta _{{i_0}}^{(1)}\left( 0 \right) = \theta _i^{\left( 1 \right)}\left( 0 \right)$. (23) implies that $\theta _i^{\left( 2 \right)}\left( 0 \right) = \theta _i^{\left( 1 \right)}\left( 0 \right), \forall i$.

Now, we assume that $\theta _i^{\left( 2 \right)}\left( {t'} \right) = \theta _i^{\left( 1 \right)}\left( {t'} \right), \forall i$, $x_{{i_0}}^{(2)}\left( {t'} \right) = x_{{i_0}}^{(1)}\left( {t'} \right) + \alpha _{{i_0}}^{t'}\delta \,$ and $x_i^{(2)}\left( {t'} \right) = x_i^{(1)}\left( {t'} \right), i \ne {i_0}$ hold for $t = t'$. Then, when $t = t' + 1$, for $i \ne {i_0}$, we have

For $i= {i_0}$, we have

Based on (27) and (28), for $t = t' + 1$, equation (25) holds and $\theta _i^{\left( 2 \right)}\left( t \right) = \theta _i^{\left( 1 \right)}\left( t \right), \forall i$. Therefore, by above analysis, we get the equation (26).

Theorem 3: Algorithm (2) guarantees $\epsilon _i$-differential privacy for the initial state of agent with ${\epsilon _i} = \frac{{\delta {q_i}}}{{{c_i}\left( {{q_i} - {\alpha _i}} \right)}}$, if the noise are design as (25). Continually, we can call that algorithm (2) is $\epsilon$-differentially private with $\epsilon=\mathop {\max }\limits_i {\epsilon _i}$.

Proof: According to Proposition 1, the privacy calculation of state $x_i^{\left( 1 \right)}\left( t \right)$ and $x_i^{\left( 2 \right)}\left( t \right)$ can be converted into the privacy calculation of noise $\eta _i^{(1)}\left( t \right)$ and $\eta _i^{(2)}\left( t \right)$, which obey the Laplace distribution $Lap\left( {{c_i}q_i^t} \right)$. Hence, by the continuity of probability [46], we have

where ${\rm{Alg}}\left( \cdot \right)$ represents the execution of the algorithm (2), ${R^{\left( 1 \right)}}\left( t \right) = \left\{ {\eta |{\rm{Alg}}\left( {{\eta ^{\left( 1 \right)}}} \right) \in \Omega } \right\}$, $\Omega$ denotes the state domain of global execution, and ${f_{N\left( {t + 1} \right)}}\left( \cdot \right)$ is the $N(t+1)$-dimensional joint probability distribution, which is given as

Based on (30) and (31), we have

It follows from (32) that

Therefore, by integration of both sides of (31) over all the set ${R^{\left( 1 \right)}}\left( t \right)$ yields:

which implies that the algorithm (2) achieves $\frac{{\delta {q_{{i_0}}}}}{{{c_{{i_0}}}\left( {{q_{{i_0}}} - {\alpha _{{i_0}}}} \right)}}$-differential privacy for agent $i_0$. The fact is that agent $i_0$ can be any agent, so, we have the result of Theorem 3.

Theorems 1 and 2 imply that the network agents converge to the weighted average of their initial states in the mean square with its variance $\sum\nolimits_{i = 1}^N {\frac{{2c_i^2d}}{{1 - q_i^2}}}$. And, Theorem 3 implies that the algorithm (2) achieves ${\epsilon _i} = \frac{{\delta {q_i}}}{{{c_i}\left( {{q_i} - {\alpha _i}} \right)}}$-differential privacy for the initial state of agent. Based on the above discussion, it can be found that there exists an explicit trade-off between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$. It means that the variance decreases as $\epsilon_i$ increases, which can be clearly seen from the following relation expression between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$:

D Optimal Variance Discussion

In the following, we will minimize the variance ${\rm{var}}\left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)$ in (33) of the agents' convergence point for the fixed $\epsilon_i$. We establish the optimization problem as follows:

Theorem 4: For the adjacency $\delta >0$ and the given privacy level $\epsilon_i$, the optimal solution for the variance (34) of the agents' convergence point is

Proof: For convenience, we introduce a parameter ${\vartheta _i} = \frac{{{q_i} - {\alpha _i}}}{{1 - {\alpha _i}}} \in \left( {0, 1} \right)$. Note that ${q_i} = {\vartheta _i} + \left( {1 - {\vartheta _i}} \right){\alpha _i}$, which we substitute into (36), we have:

Here, we define a function as follows:

where the local parameters $\left( {{\vartheta _i}, {\alpha _i}} \right) \in \left( {0, 1} \right) \times \left( {0, 1} \right)$. Figure 1 shows the graph of the function $\psi \left( {{\vartheta _i}, {\alpha _i}} \right)$. From Fig. 1, we learn that the infimum of $\psi ({{\vartheta _i}, {\alpha _i}})$ is 1. Next, we prove it by the theoretical analysis.

Note that $1 - {\left( {{\vartheta _i} + \left( {1 - {\vartheta _i}} \right){\alpha _i}} \right)^2} < 1$, then we have

In the following, for the value $\alpha_i$, we divide three cases to consider.

For the first case ${\alpha _i} \in \left( {0, 1} \right)$, we have

For the second case ${\alpha _i} \to 1$, it yields:

For the third case ${\alpha _i} \to 0$, we have

Besides, note that $\mathop {\lim }\limits_{{\vartheta _i} \to 0, {\kern 1pt} {\kern 1pt} {\alpha _i} \to 0} \psi \left( {{\vartheta _i}, {\alpha _i}} \right) = 1.$

From (40)-(42), we obtain that the infimum of $\psi ({{\vartheta _i}, {\alpha _i}})$ is 1. Hence, by (37), the optimal variance as follows:

which implies that the results of Theorem 4 hold.

Figure  2.  The graph of the function $\psi \left( {{\vartheta _i}, {\alpha _i}} \right)$ over the parameters $\left( {{\vartheta _i}, {\alpha _i}} \right) \in \left( {0, 1} \right) \times \left( {0, 1} \right)$. It shows that the function approaches its infimum 1 as ${\vartheta _i} \to 0, \, \, \, {\alpha _i} \to 0$, which is consistent with our theoretical result.

DownLoad: Full-Size Img PowerPoint

Ⅳ. SIMULATION EXAMPLE

In this subsection, we aim to confirm the theoretical results we have obtained based on the proposed algorithm (2). For the sake of convenience, we consider a undirected and connected ring network [47] with 20 agents. In all the simulations, we set $\delta=0.7$.

Fig. 3 shows that all network agents eventually reach certain values under algorithm (2) with parameters $\alpha_i=0.8$ and $\beta_i=0.07$. It can be found that all network agents do not converge to the same value, which implies that the network agents cannot converge to the exact average initial value. The result is in accordance with Proposition 4.1 in [31]. Fig. 4 depicts that all network agents eventually converge to the weighted average initial value in the mean square. The ETC algorithm parameters are set $\alpha_i=0.8$, $\beta_i=0.07$, $\sigma_i=0.3$ and the weighted value $\gamma_i=10$ for $\forall i$. The simulation testifies the results of Theorems 1 and 2.

Figure  3.  State trajectory $x_i(t)$ all network agents under the algorithm (2).

DownLoad: Full-Size Img PowerPoint

Figure  4.  State trajectory $x_i(t)$ of each agent under algorithm (2), and the algorithm parameters are set $\alpha_i=0.8$, $\beta_i=0.07$ and $\sigma_i=0.3$. From the results, it can be found that the sates of all agents converge to the weighted average initial value in the mean square.

DownLoad: Full-Size Img PowerPoint

In order to illustrate the effectiveness of our event-triggered scheme, we present the ETC trajectory $u_i(t)$ of all network agents in Fig. 5 with $u_i(t)=\sum\nolimits_{j \in {N_i}} {{a_{ij}}{\theta _j}\left( {t_k^j} \right)}$. The ETC algorithm parameters are set $\alpha_i=0.8$, $\beta_i=0.07$, $\sigma_i=0.3$ and the weighted value $\gamma_i=10$ for $\forall i$. It can be found that $u_i(t)$ is the piecewise constant communication control function, which means that the communication among agents is discontinuous. Besides, Fig. 6 shows the event-triggered time instant of all network agents 1-20. Following Fig. 4, the event-triggered time instant further verify that the communication among agents is intermittent and just occurs at event-triggered time instant.

Figure  5.  The ETC trajectory $u_i(t)$ of all network agents with $u_i(t)=\sum\nolimits_{j \in {N_i}} {{a_{ij}}{\theta _j}\left( {t_k^j} \right)}$. It can be found that $u_i(t)$ is the piecewise constant communication control function, which means that the communication among agents is discontinuous.

DownLoad: Full-Size Img PowerPoint

From the D section of Main results, it is found that there exists a trade-off between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^\infty {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$ with Laplace noise parameters $c_i=0.7$ and $q_i=0.9$. Fig. 7 shows the relationship between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^\infty {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$, as is shown in (33). The result of Fig. 7 are in accordance with our conclusion.

Figure  7.  Event-triggered time instant of the network agents 1-20. It can be found that events are not triggered at every step, and the communication among agents is discontinuous.

DownLoad: Full-Size Img PowerPoint

Fig. 8 depicts the histogram of convergence points for $10^4$ times simulations under algorithm (2) with $x_\infty=\bar x\left( 0 \right)+{\rm{var}}\left( {\sum\nolimits_{s = 0}^\infty {\tilde w\left( s \right)} } \right)$. The most of the convergence point are near the weighted average initial value. The distribution of the convergence point is similar to the Gaussian distribution. As we increase the simulation times, the distribution of the convergence point will approach closer to a Gaussian distribution function.

Figure  8.  The relationship between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$ is shown. It is clearly seen that there exists an explicit trade-off between ${\rm{var}}\left( {\sum\nolimits_{s = 0}^t {\tilde w\left( s \right)} } \right)$ and $\epsilon_i$, as is shown in (33).

DownLoad: Full-Size Img PowerPoint

Ⅴ. CONCLUSIONS AND FUTURE WORK

This paper aims to develop a new event-triggered update law for all agents in MANSs as our differentially private consensus algorithm. The results show that our proposed algorithm not only guarantees to achieve the consensus of all agents in MANSs, but also preserves the privacy of each agent' initial state against the other all agents. By the theoretical analysis, the sufficient condition of convergence and its accuracy are derived, respectively. Meanwhile, the differential privacy of the algorithm is guaranteed. Besides, the optimal solution to minimize the variance of the agents' convergence point according to the tradeoff between privacy and performance of our proposed algorithm is derived for the given privacy level. Finally, a numerical simulation example is used to testify the of the validity of our algorithm.

From the above conclusion, the convergence rate is not provided, which is due to the generality of the algorithm parameters. It is as described in Remark 4. This motivates us to improve our algorithm (2) such that we can derive the convergence rate. Besides, some interesting open questions left by this paper include expanding main results to switching topology directed graphs, the time-delay case and proposing the more effective privacy-preserving scheme for more general systems under the event-triggered communication strategy.