【Paper】2020_Resilient Self/Event-Triggered Consensus Based on Ternary Control

Matsume H, Wang Y, Ishii H. Resilient self/event-triggered consensus based on ternary control[J]. Nonlinear Analysis: Hybrid Systems, 2021, 42: 101091.

本文考虑了在存在对抗性代理的情况下的多代理共识问题，这些代理可能试图阻止和引入对正常代理之间协调的不希望的影响。在我们的环境中，我们扩展了所谓的平均子序列减少算法，目的是通过两种措施减少通信量。代理商在每次传输时以三元数据的形式交换信息，此外，通过采用自我和事件触发的通信，保持低的数据交换频率。我们将观察到，在有对手的敌对环境中，自触发的方法可以比事件触发的对应方法带来某些优势。

I. Introduction

II. PROBLEM FORMULATION

A. Preliminaries on graphs

B. Self-triggered consensus protocol

我们引入了基于三元控制器的自触发共识协议，供代理实现共识[15]。在这个协议中，每个代理 $i$ 都有状态变量 $x_i$，控制 $u_i$（被量化为三元值），以及本地时钟变量 ${\theta }_i$。所有这些变量都是在时间 $t\ge 0$ 时定义的。每个代理都会根据自己的时钟触发更新事件和传输事件。

1）混合系统格式的动力学：我们将每个代理人 $i\in V$ 的自触发动态表达为一个混合系统，由三个变量 $x_i,u_i$ 和 ${\theta }_i$ 组成。在时间 $t$，这些状态满足以下连续演化：

x ˙ i = u i u ˙ i = 0 θ ˙ i = − 1 (1)

\tag{1} x˙i​u˙i​θ˙i​​=ui​=0=−1​(1)

除了每一个 $t$，使定时器变量 ${\theta }_i(t)$ 成为零。这样的时间段被称为自触发时间，用 { t m i } m ∈ Z + \{ t_m^i \}_{m∈ \mathbb{Z}+} {tmi​}m∈Z+​ 表示，其中 $t_0^i=0，t_m^i<t_{m+1}^i$。所有自触发时间的集合由以下公式给出

{ t l } l ∈ Z + = ⋃ i ∈ V { t m i } m ∈ Z +

{tl​}l∈Z+​=i∈V⋃​{tmi​}m∈Z+​​
此外，让 $\mathcal{U}(t)$ 为自触发时间等于 $t$ 的节点的集合，即 U ( t ) = { i ∈ V : θ i ( t ) = 0 } \mathcal{U}(t)= \{ i∈V : θ_i (t) = 0 \} U(t)={i∈V:θi​(t)=0}。

在这样的时间时刻 { t l } \{ t_l \} {tl​}，代理 $i$ 的状态遵循离散演化，由以下公式给出

{ x i ( t + ) = x i ( t ) u i ( t + ) = { sign ( f ϵ ( ave i ( t ) ) ) if  i ∈ U ( t ) u i ( t ) otherwise θ i ( t + ) = { max { ∣ ave i ( t ) ∣ , ϵ } if  i ∈ U ( t ) θ i ( t ) otherwise (2) \left\{

\right. \\ \theta_i(t^+) &= \left\{\right. \end{aligned}\right. \tag{2} ⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​xi​(t+)ui​(t+)θi​(t+)​=xi​(t)={​sign(fϵ​(avei​(t)))if i∈U(t)ui​(t)otherwise​={​max{∣avei​(t)∣,ϵ}if i∈U(t)θi​(t)otherwise​​(2)

其中映射 $f_{\epsilon }(z):\mathbb{R}\to \mathbb{R}$，敏感参数为 $\epsilon >0$，被定义为

f ε ( z ) = { z if  ∣ z ∣ ≥ ε 0 otherwise f_\varepsilon (z) = \left\{

\right. fε​(z)={z0​if ∣z∣≥εotherwise​

另外，让 ${\text{ave}}_i(t)$ 为邻居的相对状态的加权平均数，由以下公式给出

ave i ( t ) = ∑ a i j ( t ) ( x ^ j ( t − τ j i ( t ) ) − x i ( t ) ) (3)

\tag{3} avei​(t)=∑aij​(t)(x^j​(t−τji​(t))−xi​(t))​(3)

其中，$a_{ij}(t)$ 是与 $\mathcal{G}$ 对应的（可能是时变的）邻接矩阵 $A(t)\in {\mathbb{R}}^{n\times n}$ 的第（$i,j$）个条目，当 $a_{ij}\ne 0$ 时，满足 $\alpha \le a_{ij}(t)<1$，$\alpha$ 是 $0<\alpha \le 1/2$ 的下限。此外，${\tau }_j^i(t)$ 表示在时间 $t$ 从代理 $j$ 到代理 $i$ 的通信延迟。变量 $\hat{x}j(t)$ 是代理 $i$ 最近收到和存储的代理 $j$ 的状态值。更具体地说，它是由 ${\hat{x}}_j(t)=x_j(t_k^j)$，对于 $t_k^j<t\le t_{k+1}^j$。

此外，对于 $t_m^i<t\le t_{m+1}^i$，我们定义了代理人 $i$ 上次更新后的时间间隔长度 $e_i(t)=t-t_m^i$。关于通信的延迟时间，我们假设它对任何 $i,j,t$ 都有 ${\tau }^{\prime }$ 的上限，即

e i ( t ) + τ j i ( t ) ≤ τ ′ (4)

\tag{4} ei​(t)+τji​(t)≤τ′​(4)

基于算法（1），（2）的每个代理 $i$ 的算法可以描述如下。代理人 $i$ 有本地时钟 ${\theta }_i(t)$，它随着时间的推移而减少。当它的时钟在时间 $t$ 达到 $0$ 时，它根据迄今为止从邻居那里收到的状态 ${\hat{x}}_j(t)$ 计算出加权平均 ${\text{ave}}_i(t)$。然后，它将其更新的状态值 $x_i(t)={\hat{x}}_i(t)$ 发送给其邻居。这个协议与[15]中提出的协议不同，它不使用 $x_j(t)$，而是使用 ${\hat{x}}_j(t)$ 来更新。这意味着代理人不需要向邻居发送请求来接收邻居在时间 $t$ 的值。因此，我们可以将该协议应用于有向图。

---

2）离散系统表述中的动力学：在上面讨论的混合协议的动力学中，对于每个代理 $i$ 来说，离散演化时间的间隔时间长度至少是$\epsilon$。同样，在时间 $t_l<t\le t_{l+1}$ 的变量 $x(t)$ 遵循 $x(t_l)\le x(t)\le x(t_{l+1})$ 或 $x(t_l)\ge x(t)\ge x(t_{l+1})$。我们可以通过关注时间 { t l } \{t_l\} {tl​} 的演变，将动力学解释为一个离散时间系统。

为了简化符号，我们把具有离散时间 $k\in \mathbb{Z}+$ 的变量表示为 $x[k]=x(t_k)$，$u[k]=u(t_k)$，并让序列 { k m i } m ∈ Z + \{k_m^i\}_{m∈\mathbb{Z}+} {kmi​}m∈Z+​ 是

{ k m i } m ∈ Z + = { k : i ∈ U [ k ] , k 0 i = 0 } \{k_m^i\}_{m∈\mathbb{Z}+} = \{k: i\in \mathcal{U}[k], k_0^i = 0 \} {kmi​}m∈Z+​={k:i∈U[k],k0i​=0}

那么代理人 $i$ 的自触发算法可以用离散时间表示为

x i [ k + 1 ] = { x ^ i [ k ] + f ε ( dave i [ k ] ) if  i ∈ U [ k ] x i [ k ] + u i [ k ] ( t k + 1 − t k ) otherwise (5) x_i[k+1] = \left\{

\right. \tag{5} xi​[k+1]={​x^i​[k]+fε​(davei​[k])xi​[k]+ui​[k](tk+1​−tk​)​if i∈U[k]otherwise​(5)

进一步，${\hat{x}}_i[k]$ 的更新规则为
x ^ i [ k + 1 ] = { x ^ i [ k ] + f ε ( dave i [ k ] ) if  i ∈ U [ k ] x ^ i [ k ] otherwise (6) \hat{x}_i[k+1] = \left\{

\right. \tag{6} x^i​[k+1]={​x^i​[k]+fε​(davei​[k])x^i​[k]​if i∈U[k]otherwise​(6)

其中 ${\text{dave}}_i[k]$ 定义为
$${\text{dave}}_i[k]=\sum _{j\in N_i}{a}_{ij}[k-e_i[k]]({\hat{x}}_j[k-e_i[k]-{\tau }_j^i[k]]-{\hat{x}}_i[k])$$

对于(4)中给定的 ${\tau }^{\prime }$ 和任何 $i,j,k$，假定通信的延迟时间以 $\tau$ 为上限。
$$e_i[k]+{\tau }_j^i[k]\le \tau <\frac{n{\tau }^{\prime }}{\epsilon }\text{\hspace{1em}(7)}$$

C. Adversarial model and resilient consensus

现在，我们考虑的情况是，网络中的一些节点是有问题的，甚至是有敌意的。这里的目标是使非故障的、正常的节点不受这种对抗性节点的影响。这里，我们介绍一下本文所考虑的对抗性节点的类别。

$\mathcal{V}$ 中的节点被划分为两组。$\mathcal{R}$ 表示常规节点的集合，$\mathcal{A}=\mathcal{V}/\mathcal{R}$ 表示对抗性节点的集合。正规节点将完全按照设计的算法来更新它们的控制 $u_i$，而对抗性节点则可以任意地更新 $u_i$。这里，让 $n_R=|\mathcal{R}|$，$n_A=|\mathcal{A}|$。攻击者被允许知道常规节点的状态和图的拓扑结构，并在一些约束条件下选择任何节点作为 $\mathcal{A}$ 的成员。

对于对抗性节点的类别，我们采用恶意模型，其定义如下[6]。

定义2.（恶意节点）

我们说，如果一个对抗性节点在每次传输时向其所有邻居发送相同的值，那么它就是恶意的。

更难对付的对抗性节点是那些能以任意方式向不同邻居发送不同数值的节点。这样的节点被称为拜占庭节点[7]。

在我们的问题设置中，恶意节点的身份是未知的，但我们假设事先知道网络中恶意节点的最大数量。这是在分布式容错算法的文献中采用的一个常见假设[4]。更具体地说，我们引入以下模型。

定义3（F-总数和F-局部模型）

对于 $F\in \mathbb{N}$，如果 $|\mathcal{A}|\le F$，则对抗集 $\mathcal{A}$ 遵循 $F$-总模型；如果 $|{\mathcal{N}}_i\cap A|\le F$，则每个节点 $i\in \mathcal{R}$ 的对抗集遵循 $F$-本地模型。

本文讨论的是 $F$-总模型的网络。

在此背景下，现在已经给出了多代理系统的弹性共识的概念[26]。

定义4：（弹性共识）

给定 $c\ge 0$，如果对于恶意代理的任何可能的集合和行为以及常规节点的任何初始状态值，都满足以下条件，则称多代理系统在误差水平 $c$ 达到弹性共识。

1. 安全条件：存在一个由常规代理的初始状态决定的区间 $\mathcal{S}\subset \mathbb{R}$，这样，对于所有 $i\in \mathcal{R}，k\in \mathbb{Z}+$，满足 $x_i[k]\in \mathcal{S}$。
2. 共识条件：对于所有的 $i,j\in \mathcal{R}$，持有 $\lim {\sup }_{k\to \infty }|x_i[k]-x_j[k]|\le c$。

本文的多代理问题可以表述如下。给定 $c\ge 0$，为常规代理设计基于事件的更新规则，使其在 $F$-total模型下的误差水平 $c$ 达到弹性的共识。

III. SELF-TRIGGERED CONSENSUS PROTOCOL

A. E-MSR algorithm

如上所述，每个代理在每个时间通过三元输入更新其状态值，但只有当更新事件发生时，辅助值才会使用其邻居的值来更新。为了达成有弹性的共识，我们采用一种算法，即每个普通代理忽略一些被怀疑有恶意行为的邻居。

我们继[26]之后提出了一种算法，称为基于事件的平均子序列减少（E-MSR）算法。

1. （收集邻居的值）在时间 $t$，每个常规节点 $i\in \mathcal{R}$ 拥有最近从邻居那里发送的值 ${\hat{x}}_i(t)$（或 ${\tilde{x}}_i(t)$）以及它自己的值 $x_i(t)$，并按升序排序。
2. （删除可疑值）与 $x_i(t)$ 比较，节点 $i$ 从步骤 1 收集的值中删除 $F$ 个最大和 $F$ 个最小的值。如果大于或小于 $x_i(t)$ 的值的数量少于 $F$，那么所有的值都被删除。被删除的数据被认为是可疑的，将不会被用于当前时间步骤的更新。剩余数值的节点索引集被写成 $M_i(t)\subset N_i$。
3. （本地更新）节点 $i$ 用从 $M_i(t)$ 发送的数值更新其辅助数值。被忽略的邻居 $j$ 的权重 $a_{ij}(t)$ 被暂时设置为0。

B. Self-triggered resilient consensus protocol

在基于三元控制器的自触发共识协议中，为了达成弹性共识，可以通过引入E-MSR算法来取代离散演化（2），其算法如下：

{ x i ( t + ) = x i ( t ) u i ( t + ) = { sign ( f ϵ ( ave i ( t ) ) ) if  i ∈ U ( t ) u i ( t ) otherwise θ i ( t + ) = { max { ∣ ave i ( t ) ∣ , ϵ } if  i ∈ U ( t ) θ i ( t ) otherwise (8) \left\{

\right. \\ \theta_i(t^+) &= \left\{\right. \end{aligned}\right. \tag{8} ⎩⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎧​xi​(t+)ui​(t+)θi​(t+)​=xi​(t)={​sign(fϵ​(avei​(t)))if i∈U(t)ui​(t)otherwise​={​max{∣avei​(t)∣,ϵ}if i∈U(t)θi​(t)otherwise​​(8)

算法 1 $P_{\text{slf}}^M$: 智能体 $i\in \mathcal{R}$ 的连续演化

1. 初始化： u i ( 0 ) ∈ { − 1 , 0 , 1 } u_i(0) \in \{-1, 0, 1\} ui​(0)∈{−1,0,1}，${\theta }_i(0)=0$
2. 如果智能体 $i$ 收到了来自 $j$ 的状态 $x_j(t)$，那么智能体 $i$ 存储 $x_j(t)$
3. 如果 ${\theta }_i(0)=0$，
   1. 如果 $u_i(t)\ne 0$，针对所有的邻居 $j\in N_i$，智能体 $i$ 都把自己的状态 $x_i(t)$ 发送给邻居 $j$
   2. 使用 E-MSR 的第 2 步并设 $M_i(t)$，${\theta }_i(t^{+})$，$u_i(t^{+})$
4. 结束 ${\theta }_i(0)=0$ 的判断

然后，我们就可以介绍每个代理为达成弹性共识所遵循的算法。算法1中给出的协议代表了基于三元控制器的自我触发的弹性共识协议。

V. NUMERICAL EXAMPLE

在这一节中，我们说明了两个提议的弹性共识协议的有效性，并将其性能与传统的非弹性对应协议进行比较。

A. Small network with 3-robust property

首先，我们考虑图2中所示的有8个节点的网络。我们可以检查一下，它是3-robust。对于这三个协议，我们使用共同的初始状态 $x(0)=[0,1/6,3/1,2/1,2/3,5/6,1,2/1]$。对时间延迟的约束被设定为 $\tau =0.1$。对手被认为是代理8，它将持续振荡其状态。我们还取敏感性参数 $\epsilon =0.1$。这里，恶意代理每隔 $\epsilon$ 的时间长度发送一次其数值。

[15]的传统自触发协议对对抗者来说是没有弹性的。我们证实了代理人的状态会随着时间的推移而变化，并且传输不会停止。图3和图4分别显示了拟议的自触发和事件触发弹性协议的仿真结果。另外，在图中，点表示代理的传输时间段，其颜色与状态的颜色一致。我们观察到，这些协议设法在共识中达到了所需的误差水平。此外，普通代理在达成共识后会停止传输。因此，与基于抽样的时间触发协议相比，这些协议在通信量上更有效率。