具有切换拓扑的多智能体系统协同控制的差分隐私保护

孙玉娇，杨洪勇，于美妍

(鲁东大学信息与电气工程学院，山东烟台 264025)

1 引言

在大数据的时代，许多信息化平台通过用户数据可以为用户提供越来越方便的服务，如:定位服务、网上购物和健康服务等，提高了服务质量和精度.然而，由于用户在享受便利服务的同时需要向平台提供自己的隐私信息，如:位置信息、兴趣爱好和身体状况等，使得用户的信息被不可信任的第三方获取，导致用户的隐私数据遭到严重的侵害.因此，隐私保护问题成为许多领域的研究者共同关注的问题.

近年来，隐私保护被涉及到越来越多的问题当中，如数据聚合问题.文献[1]研究了自组织网络中的隐私保护数据聚合问题，提出了具有隐私保护的基于一致性的数据聚合算法，该算法在保护敏感数据隐私的同时保证了精确的聚合.为了缓解数据收集和隐私保护的紧张，差分隐私算法被认为是一个有效的解决方案.差分隐私由Cynthia Dwork[2]提出，差分隐私的定义要求协议或者机制保证一定范围内相邻的数据集通过该协议或机制输出在某一集合的概率的相差程度很小.随着差分隐私的发展，差分隐私已经被应用到许多不同的领域中，如:机器学习、多智能体一致性等等.在考虑到隐私的情况下，传统平均一致性算法中的智能体状态不可用，使得传统平均一致性算法失效.为了解决多智能体系统差分隐私平均一致性问题，许多控制学者致力于设计出控制协议或机制使其不仅满足平均一致性，而且满足差分隐私的定义，以确保攻击者无法通过窃取通道信息获得智能体真实的位置信息.文献[3]研究了差分隐私平均一致性问题，提出了隐私算法，保证了智能体状态的隐私性和平均一致性.但这种算法不能让状态收敛到精确平均值，只是平均值附近的一个随机值.因此文献[4]研究了具有隐私保护的平均一致性问题，提出了新的隐私保护平均一致性算法，保证初始状态的隐私性和初始值精确平均值的渐近一致性.文献[5]研究了考虑隐私保护的多智能体平均一致性问题，提出了差分隐私一致性算法，保证了智能体状态收敛到初始状态平均值的无偏估计，并保护了智能体状态的隐私.除此之外，差分隐私被逐渐的拓展到越来越多不同多智能体系统中，如事件触发系统、分布式优化系统等等.文献[6]研究了基于事件触发机制的差分隐私平均一致性问题，提出了分布式事件触发机制差分隐私算法，最终不仅保证了智能体初始状态隐私性，而且可以提高整个系统的执行效率.文献[7]研究了多智能体差分隐私分布式优化问题，提出了基于拉格朗日的差分隐私分布式算法，该算法不仅保证了智能体状态的隐私性，而且系统具有更快的收敛速度.文献[8]研究了轨迹隐私保护问题，提出了基于差分隐私的轨迹保护算法，该算法不仅保护了真实轨迹数据，而且获得最后轨迹位置提高了数据发布的可用性.文献[9]研究了差分隐私下多重一致性约束的最优发布问题，提出了差分隐私一致性并行发布算法，该算法不仅保证了数据的最优一致性发布，而且提高了计算效率.文献[10]研究了具有差分隐私保护的多智能体系统最大一致性问题，提出了差分隐私最大一致性算法，最终保证初始状态隐私性和初始状态最大值的渐进一致性.

随着智能机器人、传感器等设备的发展，以及更复杂的实际应用的需求，固定拓扑下的系统很难满足自动控制研究的现状.在实际情况中，固定拓扑系统可能会发生因通信能力、传感范围等限制因素导致的故障，使得系统的通讯网络变得不连通，因此研究切换拓扑对系统的影响具有很大的实际意义.由于切换拓扑中拉普拉斯矩阵及其特征值也会随之发生变化，使得理论分析过程变得相对复杂.目前与切换拓扑的多智能体系统的相关研究已有不少.文献[11]研究了非线性多智能体系统在切换拓扑下的基于事件触发的一致性控制问题，提出了分布式事件触发一致性算法，该算法得到了多智能体达到一致有界的充分条件，并且降低了网络通信负载.文献[12]研究了切换拓扑下离散和连续多智能体系统的一致性问题，提出了一致性控制协议，最终得到了智能体达到一致的充分条件.文献[13]研究了时变拓扑下二阶多智能体系统有限时间一致性，提出了有限时间一致性控制算法，得到了多智能体在切换拓扑下达到有限时间一致的条件.文献[14]研究了具有联合连通的时延的二阶多智能体系统一致性问题，提出了时延控制算法，得到了系统达到平均一致性的充分条件.文献[15]研究了有向动态拓扑多智能体系统一致性控制问题，提出了一致性控制算法，得到了智能体达到指数一致的条件.文献[16]研究了二阶动态拓扑系统跟踪虚拟领导者的问题，提出了跟踪控制协议，得到了联合连通条件下智能体协调跟踪控制的条件.文献[17]研究了具有联合连通拓扑结构的做智能体系统领导跟随一致性问题，提出了自适应一致性控制算法，得到了领导者和跟随者渐近一致的条件.文献[18]研究了具有不确定拓扑得多智能体系统的包容控制问题，提出了具有时变的包容控制算法，得到了多智能体系统分布式包容控制的约束条件.

从以上文献的研究发现，对于切换拓扑的相关研究考虑了联合连通拓扑的情况，联合连通拓扑是拓扑在某个时间段内进行若干次切换，且不需要切换后的拓扑时刻连通，这对降低通信成本、排除一定程度的通信链路故障具有很好的效果.然而据作者所知，对具有联合连通拓扑的多智能体系统隐私保护问题的相关研究很少.

受到已有研究成果的启发，本文拟对具有切换拓扑多智能体系统的一致性的隐私保护进行研究.本文的创新点主要是:

1) 本文提出了具有隐私保护的多智能体均方一致性控制算法，该算法成功结合了传统平均一致算法和差分隐私算法，可以保护智能个体的数据隐私，同时可以使得系统运动实现均方一致.

2) 当多智能体系统的连接拓扑是动态变化不连通的情况下，本文研究了具有切换拓扑的多智能体系统协同控制的隐私保护问题，对该算法的收敛性和隐私性进行理论分析，并讨论了切换拓扑对隐私保护的影响.

2 问题描述

2.1 代数图论与概率理论

用无向图G{V，E}描述n个智能体的通信拓扑图，V(v1，v2，···，vn)表示节点集合，E ⊆V ×V表示边集合.记智能体i的邻域为Ni{j|(j，i)∈E，∀j ∈V}.图G对应的邻接矩阵为A[aij]，其中aij表示智能体i和智能体j之间的连接权重，当且仅当智能体i与它邻域中的任一智能体之间有通信时，aij ＞0，否则aij0.Laplacian矩阵为LD-A，其中度矩阵D是一个对角矩阵，表示为Ddiag{d1，d2，···，dn}，di在一个无向图G中，若从顶点i到顶点j有路径相连(当然从j到i也一定有路径)，则称i和j是连通的.如果图中任意两点都是连通的，那么图被称作连通图.

假设x表示一个服从均值为0，方差为2b2的拉普拉斯分布的随机变量，记作x～Lap(μ，b)，它的概率密度函数表示为f其中b ＞0.

2.2 相关引理和定义

引理1[12]如果一组无向图的并集G1-n是连通，那么称这组图是联合连通的，矩阵的积

为SIA(不可约非周期矩阵)，其中矩阵C(ti)是无向图对应的矩阵.

成立.

引理3[12]设正整数m＞2，如果P1，P2，···，Pm是具有正对角元素的非负n×n矩阵，那么

其中γ ＞0可以由矩阵Pi指定.

定义1对于任意智能体i，j，多智能体系统能够实现均方一致性，如果以下等式成立:

其中xi表示智能体状态.

定义2对于两组数据x ∈Rn，x′ ∈Rn，隐私保护的敏感度定义如下:

其中d1.

定义3向量x ∈Rn，x′ ∈Rn被称为是Δf-邻接的，如果以下不等式成立:

其中Δf表示敏感度.

定义4已知一对Δf邻接的状态向量x，x′，多智能体系统满足ε-差分隐私，如果以下不等式成立:

其中:Pr[·]表示算法执行后的观测序列构成的集合的概率，M(·)表示算法的执行，O表示观测序列，ε ＞0表示隐私保护预算.

3 具有固定拓扑的多智能体系统的隐私保护

3.1 均方一致性

考虑n个智能体的协同运动问题，假设第i个智能体的运动方程为

其中:xi ∈R表示智能体i的位置，ui ∈R表示智能体i的控制输入.

其中wi是服从均值为0，方差为2b2拉普拉斯分布的噪声，记作x～Lap(μ，b).

假设1对任意智能体i，j ∈{1，2，···，n}，，xi，wi相互独立，wi，wj相互独立.

注1隐私算法保证了智能体i与它的邻域中的任一智能体通信的状态不是真实状态，而是加密状态.

通过以上的分析，该系统的动态方程可以表示为

引理4若非负矩阵C[cij]∈Rn×n是一个随机矩阵，则矩阵有以下性质:

1) 特征值满足λ11，|λi|＜1，i2，3，···，n.

2)C11，其中1(1 1···1)T是特征值1对应的特征向量.

将系统写成矩阵形式

其中:矩阵LE-C，E表示单位矩阵，w(w1w2··· wn)T表示隐私保护噪声向量.

注3通过构造的隐私一致性算法(9)可以看到，网络传输的信息是经过加密的隐私数据，在网络传递时隐藏了智能体的真实信息，即使攻击者窃取通道传输信息，也不会获得智能体真实数据信息，这样就保护了智能体的隐私.这是本文算法与传统平均一致性算法的区别.协同控制采用隐私保护的意义在于保护智能体的敏感数据同时使得多智能体系统实现均方一致.

注4如果不给网络传输信息加密，那么攻击者获取智能体真实数据后，可能会对多智能体系统的运行造成负面影响.例如，当智能体i的初始状态信息泄露后，攻击者使用相同的初始状态进行冒充，并且切掉智能体i与邻居智能体的连接，最终使得多智能体系统的运行受到破坏.

定理1考虑一个具有n个智能体的系统，它的运动方程为式(6)，智能体的加密算法为式(7)，在隐私保护一致性控制算法(9)的作用下，智能体位置会渐近收敛到均方一致，并且智能体位置的隐私得到了保护.

证由无向图的性质可知，矩阵Laplacian有一个0特征值，其余特征值均大于0.假设λ1≤λ2≤···≤λn，∀i，λi≥0，λ10，λ1对应的特征向量v1(1 1···1)T.已知线性定常系统状态方程(8)的零解为

分析方程(8)的零解.由于矩阵L有一个特征值为0，因此存在正交矩阵P使得矩阵L相似对角化，即PTLPΛdiag{0，λ2，···，λn}，其 中λi是矩阵L的n-1个不为0的特征值.由于特征值0对应的特征向量为(1 1···1)T，则正交矩阵P(p1，p2，···，pn)的第1列表示为

PT的第1行表示为

因此式(11)的第1项表示为

由于w(t)服从期望为0的Laplace分布，因此对式(11)两边求期望可得

根据定义1，该分布式系统是渐近稳定的，智能体的状态渐近收敛到均方一致，收敛点为所有智能体初始值的平均值，即证毕.

3.2 隐私保护算法分析

为了保护任意智能体的位置状态的隐私，给智能体真实位置加上一个服从拉普拉斯分布的噪声得到发送位置，使得后续状态更新过程中不会再出现与真实状态相关的信息.

定理2给定一对Δf-邻接的状态向量x和x′，则隐私保护一致性控制算法(9)提供ε-隐私保护，其中ε ＞0.

根据假设1，噪声变量wi，wj相互独立，因此添加到n个智能体的噪声变量的概率密度函数可以表示为

假设添加到Δf-邻接的状态向量x，x′的噪声变量的概率密度函数用ρ1，ρ2表示，那么可以得到以下不等式:

对式(16)两边求积分后可以得到Pr[M(x)∈O]≤eεPr[M(x′)∈O].也就是说，对于Δf邻接的状态向量x，x′，使用隐私保护协同控制算法得到相同的观测向量的概率是非常大的.换句话说，攻击者试图从观测序列中估计噪声进而推断出准确的真实状态的概率是非常小的.这说明了隐私保护一致性控制算法保证了相似的输入有大致相同的输出，使得攻击者无法从截取的观测信息中区分x，x′，因此智能体系统的真实状态向量x受到隐私保护.

下面分析隐私保护强度.取ε在噪声方差一定的条件下，Δf越小，ε就越小，隐私保护算法提供的隐私保护强度就越高，这说明两个向量之间的差值越小，噪声对真实数据的保护就越好. 证毕.

4 具有切换拓扑的多智能体系统的隐私保护

4.1 均方一致性

定理3考虑具有n个智能体的系统，智能体的运动方程为式(6)，智能体加密算法为式(7)，在算法(9)的作用下，如果智能体系统在无穷时间序列t0，t1，t2，···的每个时间间隔[tk，tk+1)都是联合连通的，那么任意智能体的位置将会渐近收敛到均方一致，并且任意智能体的真实状态受到保护.

以此类推，迭代后得到时间间隔[tk，tk+1)的子系统的解，表示为

经过类似的分析，通过迭代可以得到系统在无穷时间序列的解表示为

其中k0，1，2，···.

已知时间间隔[tk，tk+1)内系统的拓扑图的并集Gk，1-s是连通的，根据引理1，矩阵的积

是SIA的，也就是存在向量使得以下等式成立:

由于w(t)服从期望为0的Laplace分布，因此对系统的解两边求期望可得

这意味着多智能体系统在联合连通条件下能够渐近收敛到均方一致性，且最终收敛值是智能体初始值的平均值. 证毕.

4.2 隐私保护算法分析

假设分别用ρ1，1和ρ2，2表示，那么可以得到

5 仿真示例

5.1 具有固定拓扑的多智能体系统的隐私保护

为了验证本文算法的效果，本文考虑由6个智能体组成的多智能体系统，每个智能体的初始状态取值为x(0)[-6.5，5.4，-9.6，10.3，6.9，4.2]，假设多智能体系统的无向通信拓扑图如图1所示.

图1 多智能体系统的通信拓扑图Fig.1 The communication topology of multi-agent systems

图2表示在隐保护私协同控制算法作用下所有智能体的位置状态，从图中可以看出多智能体状态最终都渐近收敛到初始状态的平均值，这说明了隐私保护协同控制算法不会影响多智能体系统的收敛性.图3表示在传统平均一致性控制算法作用下和在隐私保护协同控制算法作用下所有智能体位置状态的误差，从图中可以看出这两个状态之间一直存在一个很小的偏差，产生这种偏差的原因是在隐私保护协同控制算法中的智能体真实状态被加密状态代替;偏差很小的原因是隐私保护协同控制算法能够保证相似的输入有大致相同的输出，这也说明了攻击者无法准确的区分智能体真实状态，使得智能体的真实状态受到保护.图4表示智能体的控制器随时间变化图，从图中可以看出随着智能体的状态收敛到初始状态的平均值，智能体的控制器状态逐渐趋于0.

图2 具有隐私保护的智能体位置状态Fig.2 The position states of agents with privacy protection

图3 智能体真实状态与加密状态的误差Fig.3 The errors of agents between actual value and encrypted value

图4 智能体的控制器状态Fig.4 The controller states of agents

通过仿真可以发现，本文的提出的差分隐私协同控制算法是在传统平均一致性算法的基础上提出的，结合差分隐私算法后，使得智能体状态逐渐收敛到均方意义下的平均一致性.相比传统平均一致性算法，本文算法能够保护智能体真实状态，而传统平均一致性算法不能保护智能体状态.

5.2 具有切换拓扑的多智能体系统的隐私保护

假设6个智能体在时间间隔[ti-1，ti)内按照图5所示拓扑图依次进行切换，那么多智能体系统在隐私保护协同控制算法的作用下的仿真结果如下图所示.

图5 智能体切换通信拓扑图Fig.5 The switching communication topologies of multi-agent systems

图6表示在隐私保护协同控制算法作用下所有智能体位置状态，从图中可以看出所有智能体的位置状态随着时间的变化最终都趋向于初始状态的平均值，这说明了隐私保护协同控制算法不会影响多智能体系统的收敛性.而且从图6可以看出智能体的状态曲线图是不光滑的，产生不光滑曲线的原因是在时间间隔内有的智能体没有与别的智能体产生连接，进而没有位置更新.图7表示在传统平均一致性协同控制算法和本文提出的隐私保护协同控制算法作用下所有智能体状态的误差，从图中可以看出所有智能体的真实状态与加密状态的误差一直在一个很小的范围内，产生这种偏差的原因是在隐私保护协同控制算法中的智能体真实状态被加密状态代替;偏差很小的原因是隐私保护协同控制算法能够保证相似的输入有大致相同的观测序列，这保证了攻击者无法准确的区分智能体真实状态，也就使得智能体的真实状态受到保护.

图6 具有隐私保护的智能体位置状态Fig.6 The position states of agents with privacy protection

图7 智能体真实状态与加密状态的误差Fig.7 The errors of agents between actual value and encrypted value

对比图3和图7可以看出，隐私保护算法在固定拓扑和切换拓扑的情况下都可以保护个体数据隐私，真实数据与加密数据之间都会有一个很小的偏差，也就是切换拓扑不会影响个体数据的隐私保护.但通过对比还可以发现，切换拓扑对施加保护的系统的收敛性来说，会使得系统收敛性分析更加复杂，也会影响系统的收敛速度.

5.3 隐私泄露

在本节中，将对隐私泄露后的系统进行仿真分析.假设1号智能体的被攻击，攻击者冒充1号智能体，并切断1号智能体与邻居智能体的连接.

图8表示隐私泄露后智能体状态随着时间变化的曲线图，从图中可以看出，1号智能体表示隐私泄露的智能体，该智能体状态保持不变，2号和3号智能体状态最终都保持-2.1不变，4号，5号和6号智能体状态最终都保持7.1不变.这说明了隐私泄露对系统造成无法收敛的影响，使得系统的稳定性受到破坏.

图8 具有隐私泄露的智能体位置状态Fig.8 The position states of agents with privacy leak

图9表示隐私保护强度随着尺度参数变化的曲线图，红色曲线表示在Δf0.3 时，隐私保护强度随着尺度参数的变化情况，蓝色曲线表示在Δf0.6时，隐私保护强度随着尺度参数的变化情况.从图中可以看出，在Δf一定时，随着尺度参数b越来越大，ε会越来越小，也就是隐私保护算法的隐私保护强度会越来越高，算法对数据的保护性越好.

图9 隐私保护强度Fig.9 The comparison of privacy protection strength

6 结论

本文研究了具有固定拓扑和切换拓扑结构的连续多智能体系统的隐私保护问题，提出了具有隐私保护的多智能体系统协同控制算法，应用矩阵论和概率统计对隐私保护协同控制算法的收敛性和隐私性进行理论分析，得出了隐私泄漏对分布式协同控制闭环系统稳定性的影响，最终该算法可以保护智能个体的数据隐私，同时可以使得系统运动实现均方一致.