一類離散時延多智能體系統(tǒng)的安全一致性研究

高炎秋，紀(jì)良浩，高 婷，于南翔

（1.重慶郵電大學(xué) 圖像認(rèn)知重慶市重點實驗室，重慶 400065；2.重慶郵電大學(xué) 計算智能重慶市重點實驗室，重慶 400065；3.重慶郵電大學(xué) 理學(xué)院，重慶 400065）

0 引言

近年來，一致性作為復(fù)雜系統(tǒng)協(xié)調(diào)控制中的基本問題，逐漸受到各領(lǐng)域?qū)W者的關(guān)注。多智能體系統(tǒng)的一致性是指在分布式控制協(xié)議(算法)下，智能體通過局部信息交互，使得系統(tǒng)中各個智能體的狀態(tài)信息(如位置、速度和加速度等)在一定時間內(nèi)趨于一致。隨著多智能體系統(tǒng)在工程領(lǐng)域的廣泛應(yīng)用[1-3]以及多智能體系統(tǒng)一致性問題研究的逐步開展[4-8]，多智能體系統(tǒng)的安全問題逐漸引起了國內(nèi)外眾多學(xué)者的關(guān)注[9-11]。

安全一致性問題的解決思路是對各正常智能體施加一種安全一致性算法，使其能夠抵御惡意攻擊，確保自身狀態(tài)始終處于一定安全范圍(安全區(qū)間)內(nèi)，最終收斂一致[12]。為了實現(xiàn)安全一致性，學(xué)者們從各個方面進行了相關(guān)研究。文獻(xiàn)[13]針對系統(tǒng)存在Dos 攻擊，提出了一條分布式事件觸發(fā)控制法則，研究結(jié)果表明，采用該控制法則后，系統(tǒng)能夠以指數(shù)形式實現(xiàn)安全一致。文獻(xiàn)[14]針對系統(tǒng)在遭受連接維持或連接破壞等拓?fù)涔舻那樾?，提出了一類多步分布式的算法，并給出了系統(tǒng)收斂的充分條件。相較以上攻擊類型，文獻(xiàn)[15]研究了系統(tǒng)在拜占庭攻擊下的一致性問題，并給出了惡意節(jié)點數(shù)與網(wǎng)絡(luò)拓?fù)溥B通度的關(guān)系。文獻(xiàn)[16]針對系統(tǒng)存在通信時延問題，設(shè)計了一類使用局部信息的控制協(xié)議，并分析得出當(dāng)正常節(jié)點的拓?fù)錆M足健壯圖時實現(xiàn)安全一致的條件。在文獻(xiàn)[16]的基礎(chǔ)上，文獻(xiàn)[12]將拓?fù)鋽U展為時變通信拓?fù)?，即惡意?jié)點能夠改變攻擊對象。除上述研究工作之外，一些學(xué)者采用迭代思想來設(shè)計安全一致性算法。文獻(xiàn)[17]提出了有限時間內(nèi)的分布式迭代學(xué)習(xí)算法。文獻(xiàn)[18]基于上述研究，控制算法僅選取正常節(jié)點鄰居信息序列的中間值作為最優(yōu)信息，并以該值進行狀態(tài)更新，最后給出了系統(tǒng)實現(xiàn)有限時間安全一致性的相關(guān)條件。

對于惡意節(jié)點的安全研究，有一類工作是通過算法移除極大值和極小值來降低其對狀態(tài)的影響，但其還存在需進一步研究的內(nèi)容，如針對較強的拓?fù)溥B通度需求，正常節(jié)點的拓?fù)湫铦M足r-健壯圖；算法的抗攻擊能力較弱，能抵御的惡意節(jié)點數(shù)目單一；算法未進行判斷而是直接選取序列中間值，增大了狀態(tài)更新偏差[12, 16, 18]等。

基于上述相關(guān)研究工作，本文首先討論了一類時延多智能體系統(tǒng)的安全一致性問題，并以正態(tài)曲線下距離期望值一個標(biāo)準(zhǔn)差為約束條件，設(shè)計了一種攻擊容忍類安全一致性算法。該算法在處理單一惡意節(jié)點攻擊時，可降低正常節(jié)點的拓?fù)溥B通度需求；拓?fù)溥B通度相同時，增強了系統(tǒng)抗攻擊能力，即任一正常節(jié)點能抵御3 個惡意節(jié)點的攻擊；對鄰居時延信息進行判斷，保留了若干信息值，減小了狀態(tài)更新偏差和惡意節(jié)點的影響。此外，該算法還能夠同時適用于固定通信拓?fù)浜蜁r變通信拓?fù)洹?/p>

1 預(yù)備知識及問題描述

用G={V,ε,A}表示一個有向加權(quán)圖，其中V={v1,v2, …,vn}表示圖中n個節(jié)點的集合；表示圖的邊集合；節(jié)點的下標(biāo)集合為N={1, 2, …,n}；圖的鄰接矩陣A={aij}∈Rn×n，其中aij為節(jié)點vi與vj的連接權(quán)重。當(dāng)vi可以得到vj的信息時，aij＞0；否則，aij=0。定義節(jié)點vi的鄰居集合為。

考慮一個由n個多智能體組成的多智能體系統(tǒng)，其拓?fù)浣Y(jié)構(gòu)可用G={V,ε,A}描述，其中每個智能體可看作圖G的一個節(jié)點，智能體間的信息流可被視為圖中的一條有向路徑（有向邊）。假設(shè)在此系統(tǒng)中包含no個正常節(jié)點和nm個惡意節(jié)點，Vo表示正常節(jié)點集，Vm表示惡意節(jié)點集，則有。正常節(jié)點的序號集為Wo={1, 2, …,no}，惡意節(jié)點的序號集為Wm={no+1,no+2, …,n}。定義節(jié)點的正常鄰居節(jié)點集合為。

如果有向圖中至少存在一個節(jié)點可以沿著有向路徑抵達(dá)其他任一節(jié)點，則稱此圖包含一有向生成樹。在任意有向圖中，對于圖中的每個節(jié)點，若滿足節(jié)點的出度等于入度，則稱該圖為有向平衡圖。令S表示節(jié)點集為V的有向圖的集合，ε(G)為圖G的邊集合，A(G)為圖G的權(quán)重鄰接矩陣，則記為S的并圖。若S的并圖包含生成樹，則稱該圖集合聯(lián)合包含生成樹。

為了方便論述，下面先給出一些相關(guān)的定義與引理。

定義1K正則有向圖[19]

對于有向圖G，記

式中：Δ(G)——圖G的最大頂點度；δ(G)——圖G的最小頂點度。

在有向圖G中，若存在關(guān)系Δ+(G)=Δ-(G)=δ+(G)=δ-(G)=K，則稱G為K正則有向圖。

引理1正則有向圖及其生成子圖至少有一棵生成樹[19]。

引理2對于有向圖G的Laplacian 矩陣L，0 是該矩陣一個單一特征值且1n為其對應(yīng)的特征向量，當(dāng)且僅當(dāng)該有向圖G含有一棵生成樹[20]。

引理3如果存在一個列向量c∈Rn，其使得隨機矩陣Q滿足，則稱D為SIA（系統(tǒng)影響評估）矩陣[21]。

引理4如果一系列有向圖含有一棵生成樹，則對任意序列矩陣的乘積都是SIA 矩陣，且對于每一個無限序列矩陣，存在一個列向量c∈Rn，使得[21]。

2 安全一致性算法

假設(shè)多智能體系統(tǒng)中正常節(jié)點滿足如下動態(tài)方程：

式中：xi(t)——狀態(tài)輸入，xi(t)∈Rz；ui(t)——控制輸入，ui(t)∈Rz。

為了論述的方便且又不失一般性，文中假設(shè)z=1。

由文獻(xiàn)[22-23]可知，攻擊類型中拜占庭攻擊的破壞力最強，該類攻擊節(jié)點不受約束，向鄰居節(jié)點發(fā)送干擾值影響其狀態(tài)更新，使系統(tǒng)狀態(tài)偏離安全域且無法達(dá)成一致。下面先給出相關(guān)的定義。

定義2惡意節(jié)點[23]

節(jié)點va,a∈Vm為惡意節(jié)點，其具有下列屬性：

（1）狀態(tài)更新方程為

其中，fa(·)可以是任意函數(shù)。

（2）同一時刻發(fā)送不同的狀態(tài)值。

（3）任意時刻可以隨意改變攻擊對象或者放棄攻擊。

本文所考慮的惡意節(jié)點除了具有拜占庭攻擊能力外，還考慮了網(wǎng)絡(luò)中任一惡意節(jié)點之間相互共謀的能力，即在t時刻至少有兩個惡意節(jié)點同時攻擊某一正常節(jié)點，以及惡意節(jié)點之間相互可達(dá)。

定義3f-局部攻擊模型[24]

多智能體系統(tǒng)中，若任一正常節(jié)點的鄰居中有至多不超過f個惡意節(jié)點，則該拓?fù)浔环Q為f-局部攻擊模型。

定義4安全域[12]

在t=0 時刻，正常節(jié)點的狀態(tài)最小值和最大值構(gòu)成的區(qū)間被稱為安全域，即[m(0),M(0)]。其中：

定義5安全一致性[12]

若多智能體系統(tǒng)能滿足式（5）所示條件，則稱式（1）所示系統(tǒng)能漸近實現(xiàn)安全一致。

本文考慮了一種情況，即某一時刻正常節(jié)點狀態(tài)值不利于狀態(tài)更新而惡意節(jié)點狀態(tài)值有利于狀態(tài)更新，則需要判斷狀態(tài)值是否利于狀態(tài)更新。

與文獻(xiàn)[12]類似，本文對系統(tǒng)中惡意節(jié)點數(shù)目進行了限定，即系統(tǒng)滿足f-局部攻擊模型，并假設(shè)信息序列服從近似正態(tài)分布，以對狀態(tài)值進行判斷：x∈(μ-σ,μ+σ)，符合，則保留；否則，剔除。在此前提下，所設(shè)計的安全一致性算法的具體步驟如下：

（1）對于節(jié)點vi,i∈Vo，與文獻(xiàn)[12,18]類似，將t時刻所包含的鄰居時延信息和自身信息的序列作升序排序；用安全域?qū)ζ溥M行預(yù)處理，移除不在安全域內(nèi)的惡意狀態(tài)值，進而得到預(yù)處理后的新序列。

（3）記Mi(t)為步驟（2）中經(jīng)約束條件處理后保留的節(jié)點集，正常節(jié)點vi所采用一致性控制協(xié)議如下：

式中：Tij——節(jié)點vj到節(jié)點vi的通信時延；aij——權(quán)值，aij≥0；ηij(t)——節(jié)點通信狀態(tài)值。

節(jié)點vi自身不具有輸入時延。當(dāng)節(jié)點vi采用節(jié)點vj的信息時，ηij(t)=1；否則，ηij(t)=0，。

3 主要結(jié)果

假設(shè)1系統(tǒng)中任一正常節(jié)點任意時刻被K個惡意節(jié)點攻擊。

假設(shè)2系統(tǒng)中任一正常節(jié)點任意時刻被至多K+1個惡意節(jié)點攻擊。

定理1對于時延（有界）多智能體系統(tǒng)式（1），其拓?fù)錆M足假設(shè)1，則在式（6）所示協(xié)議作用下，當(dāng)且僅當(dāng)正常節(jié)點的拓?fù)錇? 正則有向圖時，系統(tǒng)能夠漸近實現(xiàn)安全一致。

證明：

（1）必要性

采用反證法。系統(tǒng)中正常節(jié)點構(gòu)成的拓?fù)錇? 正則有向圖，則任一正常節(jié)點的鄰居節(jié)點中有且僅有一個正常節(jié)點。假設(shè)系統(tǒng)已經(jīng)收斂至一致狀態(tài)z，此時惡意節(jié)點的狀態(tài)值為且a≠z；對系統(tǒng)中某時刻入度不為1 的正常節(jié)點發(fā)送該值，此時安全算法未能將該惡意值剔除，則該值將被用于狀態(tài)更新，從而打破了一致性，使系統(tǒng)狀態(tài)無法保持一致。

（2）充分性

經(jīng)第2 節(jié)中算法步驟（1）處理后，記t時刻序列的第一個數(shù)值為m′(t)，最后一個數(shù)值為M′(t)，顯然。記約束條件保留的狀態(tài)值為xj(t),j∈Mi(t)，則該值始終在安全域內(nèi)，即，這保證了系統(tǒng)的安全性。

根據(jù)式（1）和式（6），系統(tǒng)的閉環(huán)形式為

圓圈圖適用于描述物質(zhì)、化學(xué)現(xiàn)象和概念 初中化學(xué)教師講解某種物質(zhì)、化學(xué)現(xiàn)象、概念的時候，需要對其相關(guān)細(xì)節(jié)或特征進行介紹，這些細(xì)節(jié)或特征并不都是物質(zhì)固有的屬性，或經(jīng)過反應(yīng)所得，或需要在某些條件下才成立，涉及的知識比較零散。如果學(xué)生對其僅進行機械記憶學(xué)習(xí)，很容易遺忘，這時教師可用上圓圈圖配合講解。圓圈圖有兩個圈，小圈里可填寫主題，大圈里可填寫與這個主題相關(guān)的細(xì)節(jié)特征。如描述金屬鐵在氧氣中燃燒的化學(xué)現(xiàn)象，小圈內(nèi)寫鐵在氧氣中燃燒作為主題，大圈內(nèi)可寫在空氣中很難燃燒、在氧氣中劇烈燃燒且火星四射、放出大量熱、生成黑色固體。

將式（7）寫成矩陣形式：

用G′表示G，通過算法移除相應(yīng)邊后的時延圖，矩陣Q(t)為時延圖的鄰接矩陣，矩陣為時延圖的拉普拉斯矩陣。對于1 正則有向圖，任一正常節(jié)點入度為1，即度矩陣D=I，可得是一個非負(fù)矩陣，因而Q(t)也為非負(fù)矩陣。惡意節(jié)點之間相互可達(dá)，再根據(jù)引理1，則系統(tǒng)有向圖G包含一棵生成樹；經(jīng)過安全算法移除相應(yīng)邊后，其生成子圖G也包含一棵生成樹。根據(jù)引理2 可得，，。因此，Q(t)是一個隨機矩陣且其特征值λ=1 是一個單根。根據(jù)引理3，有一個列向量c∈Rn，其使得隨機矩陣Q(t)滿足，可以得到Q(t)為SIA 矩陣；再根據(jù)引理4，可以得到矩陣Q(t)的乘積：

將式（9）代入式（8），系統(tǒng)一致性狀態(tài)值為xc=cx0，其中x0為系統(tǒng)中正常節(jié)點初始狀態(tài)，滿足了系統(tǒng)的一致性條件。

至此，證明完畢。

推論1對于式（1）所示時延（有界）多智能體系統(tǒng)，其拓?fù)淙魸M足假設(shè)2，則在式（6）所示協(xié)議作用下，當(dāng)且僅當(dāng)正常節(jié)點的拓?fù)錇? 正則有向圖時，系統(tǒng)能夠漸近實現(xiàn)安全一致。

由于推論1 的證明過程與定理1 的類似，故在此處省略。

需要說明的是，對于1—局部攻擊模型，采用本文算法會降低拓?fù)溥B通度要求。對于3—局部攻擊模型，文獻(xiàn)[12]算法失效，而本文算法能夠?qū)崿F(xiàn)安全一致性，增強了系統(tǒng)抗攻擊的能力。相較文獻(xiàn)[18]，本文算法對節(jié)點的各鄰居時延信息都進行了判斷，減小了狀態(tài)更新偏差。

4 仿真

為了驗證所設(shè)計的算法是否能降低正常節(jié)點拓路連通度的需求并增強系統(tǒng)的抗攻擊能力，分別采用滿足1—局部攻擊模型的系統(tǒng)拓?fù)浜蜐M足3—局部攻擊模型的系統(tǒng)拓?fù)溥M行仿真實驗。

4.1 實驗1

圖1 多智能體系統(tǒng)拓?fù)?Fig.1 Topological structure 1 for multi-agent-system

取通信步長為0.1 s，時延上界為0.5 s。為了方便分析，此處假設(shè)系統(tǒng)奇數(shù)時刻和偶數(shù)時刻的鄰接矩陣分別為

不失一般性，假設(shè)系統(tǒng)中正常節(jié)點初始狀態(tài)值為x1(0)=1,x2(0)=2,x4(0)=4,x6(0)=6，惡意節(jié)點初始狀態(tài)值為x3(0)=3,x5(0)=5,x7(0)=7，則惡意節(jié)點v3,v5,v7的動態(tài)方程分別為x3(t+1)=0.8x3(t)+1.4,x5(t+1)=1.5sin(0.3t)+4,x7(t+1)=1.5cos(0.3t)+3。

圖1 所示通信拓?fù)渲?，任一正常?jié)點在任意時刻會被至多1 個惡意節(jié)點攻擊。根據(jù)定理1 可知，多智能體系統(tǒng)能夠?qū)崿F(xiàn)安全一致。各節(jié)點狀態(tài)演化曲線如圖2所示。

圖2 1 正則有向圖下的狀態(tài)演化軌跡Fig.2 State trajectories under 1 regular digraph

針對圖1 所示通信拓?fù)?，采用文獻(xiàn)[12]中的安全算法，算法容忍性較弱，無法移除部分惡意節(jié)點狀態(tài)值，保留的惡意狀態(tài)值成功地干擾了正常節(jié)點的狀態(tài)更新，使多智能體系統(tǒng)狀態(tài)無法收斂一致，各節(jié)點狀態(tài)演化曲線如圖3 所示。

圖3 文獻(xiàn)[12]算法下的狀態(tài)演化軌跡Fig.3 State trajectories under the algorithm of literature [12]

4.2 實驗2

本實驗將驗證推論2 的正確性。假設(shè)多智能體系統(tǒng)包含12 個節(jié)點（4 個正常節(jié)點和8 個惡意節(jié)點），紅色連接虛線為奇數(shù)時刻節(jié)點間輸入邊，綠色連接虛線為偶數(shù)時刻節(jié)點間輸入邊，實線為恒定輸入邊。通信步長設(shè)為0.1 s，時延上界取0.5 s，其連接拓?fù)淙鐖D4 所示。

圖4 多智能體系統(tǒng)拓?fù)?Fig.4 Topological structure 2 for multi-agent system

圖4 中，任一正常節(jié)點在任意時刻被至少1 個且至多3 個惡意節(jié)點攻擊。假設(shè)正常節(jié)點的初始狀態(tài)值分別為x1(0)=1,x2(0)=2,x4(0)=4,x6(0)=6，惡意節(jié)點的初始狀態(tài)值分別為x3(0)=3,x5(0)=5,x7(0)=7,x8(0)=8，x9(0)=9，x10(0)=2.5,x11(0)=4.4,x12(0)=6.6，可以驗證正常節(jié)點v1,v2,v4,v6構(gòu)成的拓?fù)錇? 正則有向圖。為了檢驗安全算法的容忍性，增強惡意節(jié)點的隱藏力和破壞力，現(xiàn)將惡意節(jié)點v3,v5,v7,v8,v9,v10,v11,v12的動態(tài)方程定義為安全域內(nèi)變化的動態(tài)函數(shù)，分別為x3(t+1)=1.2sin(0.4t)+4，x5(t+1)=1.2cos(0.3t)+3，x7(t+1)=1.5sin(0.3t)+3，x8(k+1)=1.5cos(0.4t)+3，x9(k+1)=2cos(0.3t)+4，x10(t+1)=2.5cos(0.3t)+3，x11(k+1)=sin(0.3t)+4，x12(t+1)=cos(0.3t)+4。

各節(jié)點狀態(tài)演化曲線如圖5 所示。從結(jié)果可知，多智能體系統(tǒng)中各正常節(jié)點在安全一致性算法的作用下，其狀態(tài)值始終在安全域內(nèi)變化，系統(tǒng)一致性不受惡意節(jié)點攻擊行為的干擾，最終多智能體系統(tǒng)能夠?qū)崿F(xiàn)安全一致。

圖5 2 正則有向圖下的狀態(tài)演化軌跡Fig.5 State trajectories under 2 regular digraph

移除圖4 中節(jié)點v1到節(jié)點v2和節(jié)點v2到節(jié)點v4的輸入邊，這種情形不滿足推論1 中的充分條件，使得系統(tǒng)無法實現(xiàn)安全一致。該條件下各節(jié)點狀態(tài)演化曲線如圖6 所示，此時惡意節(jié)點成功干擾了正常節(jié)點的狀態(tài)更新，破壞了多智能體系統(tǒng)的一致性。

圖6 非2 正則有向圖下的狀態(tài)演化軌跡Fig.6 State trajectories under non 2 regular digraph

綜上，在實驗1 中，正常節(jié)點拓?fù)錇? 正則有向圖，對比文獻(xiàn)[12]中正常節(jié)點拓?fù)鋱D，拓?fù)溥B通度降低；在實驗2 中，正常節(jié)點拓?fù)錇? 正則有向圖，與文獻(xiàn)[12]中正常節(jié)點拓?fù)鋱D具有相同連通度，但每個正常節(jié)點能被3 個惡意節(jié)點攻擊，增強了抗攻擊能力，實驗結(jié)果證明了所設(shè)計算法的有效性。

5 結(jié)語

本文研究了通信時延影響下多智能體系統(tǒng)的安全一致性問題，主要以拜占庭節(jié)點為惡意節(jié)點，考慮了多智能體系統(tǒng)的拓?fù)鋸?fù)雜度和抗攻擊能力，提出了一種容忍性強的安全一致性算法。本文算法對正常節(jié)點的所有鄰居信息都進行了惡意值的判斷，并保留了其最優(yōu)鄰居節(jié)點狀態(tài)集。當(dāng)多智能體系統(tǒng)拓?fù)浣Y(jié)構(gòu)為時變通信拓?fù)?、攻擊模型為局部攻擊模型，且正常?jié)點的拓?fù)錆M足K正則有向圖時，在安全一致性協(xié)議作用下，得出了多智能體系統(tǒng)實現(xiàn)安全一致的充要條件。仿真結(jié)果驗證了該安全一致性算法的有效性和結(jié)論的正確性，該算法不僅能降低正常節(jié)點拓?fù)溥B通度需求，而且增強了多智能體系統(tǒng)的抗攻擊能力。但是，本文研究的系統(tǒng)為同構(gòu)系統(tǒng)，且節(jié)點間為合作關(guān)系，下一步我們將考慮合作-競爭關(guān)系以及異構(gòu)系統(tǒng)。