【论文理解】FedSky: An Efficient and Privacy-Preserving Scheme for Federated Mobile Crowdsensing
这篇论文同样由陆老师组完成，并发布在IEEE INTERNET OF THINGS JOURNAL上的一篇文章中。该文章聚焦于联邦学习与同态加密技术的研究。
目录
-
-
* 论文背景 -
- 群智感知（Crowd Sensing）
- F-MCS
-
本文的主要贡献
-
模型与设计目标
-
- 系统模型
- 安全模型
- 设计目标
-
-
PRELIMINARIES
-
-
A. fed_avg算法
-
B. 不同版本的skyline查询
-
C.双线性配对
-
D.帕尔雷密码系统
-
提出的方案
-
- A.KeyDist Phase
- B. WorkSel Phase
- C.DataAgg Phase
-
总结
-
参考
-
-
论文背景
在过去的几年里, 移动通信与物联网的快速扩张开创了全新的传感模式, 这种模式被命名为 移动群智感知 (MCS) 。从本质上讲, 由工人组成的移动人群被MCS平台招募, 将他们的传感数据转包给若干具体任务, 包括环境监测、交通密度评估、城市规划、位置导航以及医疗保健供应等。然而, 在执行传感任务的过程中, 工人不可避免地会将个人传感信息（如日常轨迹、实时位置及周边环境）分享给平台 。信息泄露可能导致严重的隐私问题 。例如, 攻击者可以通过对工人的传感数据进行分析来推断其日常活动轨迹及行为模式 。因此, 保护工人敏感信息不被泄露成为MCS应用面临的主要技术挑战之一
群智感知（Crowd Sensing）
群智感知（Crowd Sensing）一开始来源于众包 的概念，科技公司将项目工作以自由意愿的形式分配给非特定的社会大众，一种分布式协作。而群智感知（Crowd Sensing） 指大规模的普通用户通过其自身携带的智能移动设备来采集感知数据并上传到服务器，服务提供商对感知数据进行记录处理，最终完成感知任务并利用收集的数据给用户提供日常所需服务的过程。近些年随着各种移动设备和可穿戴设备的普及利用这些传感设备收集的数据可以分析提取许多有用信息。移动的可穿戴的传感器可以有效的收集数据而没有维护成本高覆盖范围有限等问题。如今群智感知在环境污染监测、环境噪声地图、城市交通路况、社交网络与医疗保健等方面都已经得到了应用，在可预见的未来它将会应用到更多的业务场景中。
移动群智感知系统 一般会由多个移动用户，任务发起者，云端感知平台组成，任务发起者向云端提交任务需求，感知平台向用户发布任务，移动用户携带智能设备执行任务并上传数据获得相应报酬，感知平台处理数据提供计算服务。整个过程主要设计如下几个研究方向：收集、用户招募、任务分配、隐私保护 、数据质量和激励机制
F-MCS
到目前为止为止，在已有大量持续增长的文献中用于解决MCS中的隐私问题。现有研究普遍认为，在这些研究中联合学习（FL）可被视为一种潜在且实用的技术方案。
由于其分布式特性，在这些研究中 FL 可以被看作是一种技术方案。它不仅能够通过本地存储训练数据来进行模型优化（即参与优化），而且能够在不泄露个人数据的前提下完成模型训练。
具体而言 FL 可主要可分为两种类型：跨主机 FL 和跨设备 FL 两种类型的主要区别在于参与者的主要角色和应用场景的不同
训练有素的模型会被定向发布给这些组织而不会包含 FL 聚合平台.另一方面，在跨设备 FL 中, 计算能力受限的异质移动用户提供方充当了参与者角色.最后, FL 平台将会获取训练完成后的模型.
本文在多感知器协同架构框架下成功引入了跨设备联邦学习技术后，在这项研究工作中我们提出了一种新的传感场景——联合MCS（F-MCS）。通过这种创新方案设计，在这种创新方案下让每位工人都能轻松构建高效且安全的机器学习模型。
由此可见，F-MCS能够克服传统MCS系统中工人信息外泄的核心问题，并不仅能够成为移动传感服务的一个重要领域，而且可能发展成这一领域的新热点。
然而，在仅将FL技术与MCS服务简单结合时仍面临两大关键问题。（1）在F-MCS环境中选择稳定的工作者存在挑战性。这里的工作者凭借便携式设备进行数据采集与上传工作面临着高度不稳定性的问题。这些设备所具有的硬件性能（3G/4G/5G/Wi-Fi）、网络连接质量以及供电状况（续航时间），由于分布式训练要求所有workers在完成当前轮次训练前必须正确同步数据传输这一前提下，在受设备限制的情况下会导致workers之间出现时间上的不一致步调进而影响后续的数据融合环节。（2）针对跨设备的F-MCS平台现有隐私保护方案尚显不足。作为一项跨设备的FL系统最终模型将在该平台应用于特定实时服务功能因此现有方案无法满足需求亟需为F-MCS平台设计一套切实可行且注重隐私保护的实际解决方案
本文的主要贡献
在本文中, 为了解决上述挑战, 我们提出了一种新型安全的F-MCS应用的数据聚合方案FedSky。该方案是基于经典FedAvg算法的一种扩展, 其核心特点在于采用群体天际线（G-skyline）来选择合格的workers并结合同态加密技术确保数据的安全性。具体而言,本文的主要贡献如下:
(1)我们在FedSky方案中引入了一种新颖且高效的工人选择机制。具体来说,在每一轮通信中,并非随机选择一组workers而是依据每个worker本地数据量及移动设备计算能力来确定一个适合参与的数据集。这种做法相较于传统FedAvg算法的优势在于显著降低了参与者的计算负担以及平台等待时间,从而大幅提升了联邦学习的整体效率。
(2)我们为F-MCS平台设计了一种基于HE技术的新颖隐私保护数据聚合方案,该方案旨在适用于跨设备联邦学习场景。通过这种设计,最终训练好的全球模型可被F-MCS平台访问使用。同时,整个训练过程无需参与方之间的交互交流,仅需记录相邻节点ID信息即可完成数据共享与模型更新。
(3)为了全面评估解决方案的效果与效率,在实验部分我们构建了一个专门的设计用于性能测试。
经过大量实验验证表明,所提出的解决方案能够在不牺牲准确性的情况下显著提升联邦学习过程中的效率水平
模型与设计目标
系统模型
场景考虑一个比较典型的F-MCS场景，包括三个实体：一个可信的密钥生成生成器\mathcal{TKG}，一个F-MCS平台和一组异质工人\mathcal{W}=\{w_1,w_2,w_3....\}.
(1)\mathcal{TKG}:一个受信任的权威机构，它生成并向相应的实体分发适当的密钥，从而使某项F-MCS任务能够合作完成。
(2)F-MCS平台P:P是提供F-MCS服务的可信平台，负责执行F-MCS任务，包括注册工人、初始化任务模型、选择工人和训练模型。更具体地说，在注册时，P给每个注册的工人W_i分配一个唯一的标识ID_{wi}。然后将工人的识别码广播给\mathcal{TKG}。在训练的过程中，P首先会初始化全局模型，然后从\mathcal{W}=\{w_1,w_2,w_3....\}选择一部分合格的员工（具体怎么选参考后文），P将模型分发给选定的工人，并在每轮训练中通过汇总工人提供的模型参数来训练模型。为了实现最终的全局模型，需要P和选定的工人之间进行多轮互动。
(3) 参与的工作者 ： \mathcal{W}=\{w_1,w_2,w_3....\}，\mathcal{W}是希望进行某项F-MCS任务的参与工作者。如果\mathcal{W}中的工人被P选中，首先，他/她需要用他/她的移动设备收集原始感应数据。在收到全局模型后，每个被选中的工人需要通过用他/她的本地数据训练模型来更新模型参数，加密模型参数，并与P交换密文。为了在每轮训练中被选中，工作者需要定期向P发送他们当前的训练能力和计算状态，例如，本地数据集的大小，他们的移动设备的当前CPU份额/电池/内存。
安全模型
首先，在我们的研究中认为系统参数（即参数空间）与任务知识图谱（即知识图谱）之间存在高度相关性。值得注意的是，在某些情况下恶意软件可能会被植入系统参数（即参数空间）而不被发现。因此，在这种情况下潜在威胁者（即对手）能够监控系统参数（即参数空间）的数据库，并窃取系统参数（即参数空间）与工作台之间的通信信息。主要关注点在于潜在威胁者对于每个工人的模型更新行为表现出的兴趣。通过这些更新操作潜在威胁者能够推断出工人的实时时空位置信息。
设计目标
（1）效率：该方案在训练模型以及加密传输模型参数方面具有较高的效率。相比之下，在传统的FedAvg算法中P的等待时间可能较长，在我们的方案中P的工作流程得到优化从而缩短等待时间以提高整体FL训练效率的可能性更大。
（2）隐私保护：为了确保数据安全起见 我们计划开发一个F-MCS框架 该框架能够有效防止工人敏感信息的数据泄露风险。具体而言 对于∀w_i \mathcal{D}_i表示w_i的本地数据 而x_i表示w_i在每轮训练后更新的模型参数 \mathcal{D}_i与xi均需保密以防止其他工人的未经授权访问 即使窃听者获取了\mathcal{P}的数据库以及相关的通信数据 也无法识别每个工作者的具体模型参数更新信息。
PRELIMINARIES
A. FedAvg Algorithm
该联邦平均算法在深度学习与机器学习领域被应用于联邦学习框架中以实现模型的一致化训练目标。
传统联邦学习架构包含两个基本实体：
- 数据聚合器
- K个参与者的集合\{w_{1},w_{2},...,w_{k}\}
其中，
- N_{i}代表了参与者W_{i}所拥有的本地数据集的数量
- 算法执行过程如下：
- 在第t轮开始时系统会从包含所有参与者的集合中随机选择k个参与者来进行通信交互
- 每位参与者接收到当前迭代周期的模型参数后将对该参数进行本地数据集上的梯度计算并获得该周期的平均梯度向量
- 每位参与者按照固定的学习率\eta对自身模型参数进行更新操作即x_{i}\leftarrow x^{t}-\eta·g_{i}
- 更新后的参数会被发送至数据聚合器进行汇总处理
- 数据聚合器根据公式x^{t+1}\leftarrow\sum_{i=1}^{k}(N_{i}/N)x_{i}（其中总样本数为 N=N_1+N_2+...+N_k）来更新全局模型参数
具体优化流程可通过下图进行直观展示。
B. Different Variants of Skyline Queries
多种多样化的天际线查询方案可以通过MCS的方法进行展示。 skylinemethods包括典型的G_skylinemethods以及严格定义的C_skylinemethods（C_skylinemethods）这些基本概念构成了复杂多维空间中数据处理的重要基础。此外我们还提出了一种特殊的skylinetemplate即CG_skylinetemplate它能够有效地检索出满足特定尺寸限制的数据集合
Definition 1: skyline : K个参与者\mathcal{W}=\{w_{1},w_{2},...,w_{k}\}每位参与者都可以表示为d维的数据点,
记作wi=(w_{i}[1],w_{i}[2],...,w_{i}[d]),其中i∈[1,K];假设每位参与者在所有维度上都追求最大值.
定义一种支配(dominated)关系（w_a \prec w_b）如下:对于\mathcal{W}中的任意两个不同的参与者w_a,w_b(a≠b),若对于所有维度j∈[1,d]都有w_{a[j]}≥w_{b[j]},且至少存在一个维度使得w_{a[j)}>w_{b[j]},则称v_a支配v_b.
相等关系定义为:对于所有维度j∈[1,d],都有w_{a[j]}=w_{b[j]}.
例如:考虑两个参与者v_1=(3,4,5)和v_2=(3,4,5),显然v_1=v_2.再如:v_3=(6,7,8)与v_4=(6,7,8)满足相等关系.
我们可以认为位于坐标右上方的点是最优的选择。
这些变量w_1,w_3,w_4,w_5以及w_6均属于skyline领域。
定义二 k-Point\ G-Skyline: 给定一个由工作者组成的集合\mathcal{W}，
存在两组数量为k的工作者集合G=\{w_{1},w_{2},...,w_{k}\} 和 G'=\{w_{1}',w_{2}',...,w_{k}'\} ，其中k \leq K且均为\mathcal{W}中的元素。
在此基础上，
我们定义了一种支配关系（g-domaintes）(w_{a} \prec_g w_{b})：
在两个工人组之间建立一种排列关系，
即从第一个集合中选取k个代表\{w_{u1}, w_{u2},..., w_{uk}\}，
与第二个集合中的代表\{w_{v1}', w_{v2}',..., w_{vk}'\}对应，
满足所有维度上都有d(w_{ui}, w_{vi}') \preceq 0
并至少存在一维使得d(w_{ui}, w_{vi}') < 0
从而确定了这种k-point\ G-skyline
这种情况下，
任何相同大小的工作者组都无法完全主导另一方。
举例如下：
注意 ：这里定义的符号\prec 是一种主导关系 ，具体到数值上其实是大于的关系，图像上显示实在右上角位置
定义三 ：（C-skyline）: 给定一系列d-维度的工作者\mathcal{W}
令\mathcal{C}=\{Con_1,Con_2,...Con_d,\} 表示d维度的一些限制。Con_i 表示的是一个属于一个维度的限制范围[min_i,max_i]，或者是空集\emptyset ,这样所有的限制\mathcal{C}会在d维度的空闲内形成一个约束空间 可以理解是普通的skyline上加上约束之后的点
定义四 (k-Point CG-Skyline，本文提出的新的skyline) 给定一系列d-维的工作者\mathcal{W},和一系列限制\mathcal{C} , k-point CG-skyline 的点是由约束空间中的所有的拥有k个工作者且不会被别的组 g-dominated的所有组。
举个例子： 还是在上图中 令\mathcal{C}=\{Con1,Con2\} 其中Con_1=[1,5],Con_2=[1,7] 那么图上的蓝色区域就是约束空间，那么对于定义三种C-skyline就是\{w_3,w_4，w_5\} 其中组G=\{w_1,w_4，w_5\} 是一个 3-point G-skyline 而不是一个 3-point CG-skyline 。
C.Bilinear Pairing
这部分内容就是双线性配对，就不展开讲述 可以参考 网络上的一些博文：
D.Paillier Cryptosystem
Paillier 同态加密也不做详述
需要注意在Paillier密码体系中，在某些特定情况下两份密文相乘的结果能够解码得到它们各自对应的明文字母之和。即：
D(sk,E（pk,m_1）·E(pk,m_2) mod \ n^{2})=m_1+m_2 \ mod \ n
提出的方案
本节将介绍一种创新性的基于F-MCS-联合移动群智感知的数据融合方案FedSky,该方案主要包含三个关键模块:密钥分发机制（KeyDist）、工作节点选择策略（WorkSel）以及数据融合模块（DataAgg）。
A.KeyDist Phase
首先\mathcal{TKG}运行KeyGen(k)算法生成一组参数(p,q,n,\lambda,\mu),其中包含公钥信息pk_p=(n,g)以及私钥信息sk_p=(\lambda,\mu)。随后\mathcal{TKG}会选定一个标准的双线性配对方案，并选取一个适合整数域\mathbb{Z}_{n^2}运算的统一哈希函数H_1。接着\mathcal{TKG}会将生成的所有公开参数以及选定的双线性配对方案e:\mathbb{G}×\mathbb{G}\rightarrow\mathbb{G}_T广播至参与者P及其所在的整个系统中所有成员，并安全地将私钥sk_p分配给参与者P（F-MCS平台）。在此基础上\mathcal{TKG}会依次选择多个加密方案并为每个参与者分配独特的密钥信息：首先再选择一个基于Zn域上的哈希函数H2；其次为每位参与者w_i分配一个独特的标识ID_{w_i}=H_0(w_i)，其中H_0是一个从二进制字符串到群\mathbb{G}元素映射的标准哈希函数；最后将每位参与者w_i的安全密钥ID_{w_i}^S传递给他们
B. WorkSel Phase
在本文的模型中。所有的工作者wi都具备两种属性
(1)本地的数据集大小N_i
(2)移动设备的计算能力大小P_i ，P_i表示在F-MCS任务中每分钟可以处理多少任务， wi需要定期的将N_i和P_i 发送给平台 P 在选择工作者之前，平台P 会根据F-MCS 任务的要求定义一些二维的限制 \mathcal{C}=\{Con_1，Con_2\} 对于更高的要求 限制应该也是更加严格一点。Con_1=[min_1,max_1],Con_2=[min_2,max_2], 我们认为如果min_1>min_2且max_1>max_2那么 Con_1 是比Con_2更加严格的。 接着平台P 会选择一系列符合这些限制的工作者\mathcal{W}' ,在每轮训练前P都会从\mathcal{W}'种 由N_i和P_i 两个属性的CG-skyline 选择最佳的k个工作者，具体的方法如下：
首先对于每个工作者wi,P 会计算Sum(w_i)=N_i+P_i，根据这个Sum(i) 所有的工作者都会被添加进一个最大值优先队列 Q_W ,即降序排列，值越大的越先从队列种删去。这里注意P_i和N_i 应该在同一水平(即数值上是在相近的范围内，不会出现某个属性主导的情况) ，由上述章节的描述有以下两个定理:
Theorem 1: 如果w_i是第一个被Q_W移除的工作者那么w_i就是一个符合skyline 的工作者
Theorem 2: 对于所有的w_j ∈\mathcal{W}' 能主导w_j的一定是比w_j先移出Q_W的
算法执行如下：
首先P 会初始化另一个空的最大优先队列Q_{non},和一个空的列表Q_{sky} P 会遍历Q_W队列，根据上述的定理，第一个工作者w_i 会被直接加入Q_{sky}，然后接下来的Q_W中的第一个工作者，去跟Q_{sky}中的所有工作者比较，如果都没被Q_{sky}中的工作者所主导那么就加入到Q_{sky}中，否则就添加入Q_{non}。 P重复执行上述步骤直到Q_{sky}中的数量为k或者Q_W队列为空。最后还会进行一个判断，如果最终Q_{sky}中的数量少于k个，那么会从Q_{non}选出少的个数的工作者加入到Q_{sky}，这一部分的理解是即使是某些工作者的计算能力或者数据集不够，还是需要保证有k个参与者。
举例如下
值得注意的是，在本研究中所提出的CG-skyline技术仅能指定一组G-skyline工人。一旦选定该组工人群体后,MCS平台中的进程P负责向选中的该组工人群体推送全局模型的超参数（如学习速率）。随后,选中的每个工人都能够利用接收到的超参数来进行模型训练及优化过程.
C.DataAgg Phase
\mathcal{W}_s 被定义为从k个候选工作者中选出的一组人。例如，在集合符号下表示为 \mathcal{W}_s=\{w_1,w_2,...,w_k\}。在每一轮循环开始时，系统都会执行以下操作：计算每个工作者i的权重值为 y_i = \frac{N_i}{\sum_{j=1}^{k} N_j}；其中，在计算结果后会保留三位小数位；随后将每个权重值乘以1000进行放大处理。具体的DataAgg操作步骤如下：
P将从\mathcal{W}_s中选取k个工人并将其安排成一个循环结构。注意其中每个节点w_i的相邻节点及其左侧为节点w_k。
- P 产生一个随机数 \alpha_i ∈\mathbb{Z}^{*}_n P将如下信息发送给每个工作者w_i:
这里的i\rightarrow l 和i\rightarrow r 具体来说表示的是节点w_i的左邻居和右邻居关系，在当前第t个训练周期中这些值会随着每一轮的更新而发生变化
- 当接收到信息后, w_i基于本地训练数据集计算出本地梯度g_i. 按照预设的学习率, 计算并更新模型参数x_{i}\leftarrow x^{t}-\eta·g_{i}, 并将对x_i进行归一化处理, 使其保留至第八位小数. 在每次模型更新后, w_i会重新计算\bar{x_i}=10^{8}·x_i
随后将进行操作：该算法将用来计算相关的参数（包括三个相关的关键字：左侧的 session key S_{(i,i\rightarrow l)}, 右侧的 session key S_{(i,i\rightarrow r)}, 以及处理过程中的关键参数 S_ip.）
接着w_i会计算一个\pi_i 发送给P:
系统P首先会检查是否所有参与方的参数w_i都已提交其对应的\pi_i. 如果发现有任何一个参与方的参数\pi_i尚未提交, 则协议将终止并启动新的训练轮次. 当所有参与方均已完成并提交了各自的参数$\pi_i后, 系统P将计算θ值为各π_i的乘积并对n²取模. 具体计算过程如下:
令\bar{m}=\sum_{i = 1}^{k}{\bar{x}_{i}·y_i} P 可以通过D(sk,c) 进行过解密获得\bar{m}:
正确性验证：
针对给定的所有k位员工（workers），处理密钥的形式为：
\prod_{i=1}^{k}\text{Sip}= S_{1p} + S_{2p} + S_{3p} + \dots + S_{kp}
这等于：
S_{(1,k)} - S_{(2,1)} - S{(2,3)} + \dots + S{(k,k-1)} - S{(k,1)}
根据双线性映射性质，
\sum\limits _{i= 1}^{k}\text{Sip}=0
因此可以得出结论：
对于所有k>0, 我们有：
\prod\limits _{i= 1,\text{i}\neq j }^{k}\text{rip}=0
在这一部分中可以将其视为一个随机数值的情况下，在这里可以把H_1(t)^{\sum_{i = 1}^{k}{\bar{x_i}·y_i+\gamma}} 视为一个随机数值的情况下，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式视为一个随机数值变量，在这里可以把这个表达式作为一个关键的中间结果使用起来的情况下
这里对原文中说： \bar{m} 可以是正的（
在恢复m之后，在轮t+1中进行更新：x^{t+1}\leftarrow\sum_{i=1}^{k}\left(\frac{N_i}{N}\right)x_i=m$系统随后将进入下一轮训练，并循环执行前述步骤直至全局模型达到预期性能目标
总结
在本文中,本研究提出了一种新型隐私保护方案命名为FedSky,它基于经典联邦学习算法框架进行优化,并采用CG-skyline技术筛选出合适的参与者,通过安全地汇总各参与者的模型更新来构建全局模型,特别值得注意的是与传统联邦学习算法（如FedAvg）相比,我们的方案能够更好地考虑到参与者的动态变化性和异质性特征,从而显著提高了F-MCS模型训练过程的效率,在此基础上我们还设计了一种新型隐私保护数据集成协议,该协议针对异构设备联邦学习场景,在不涉及客户端交互的情况下实现了数据的安全整合,通过安全性评估表明该方案能够有效地保障参与者数据的安全性,同时我们在一系列真实图像分类任务中进行了大量实验验证比较结果表明 FedSky 在提升参与者选择效率方面表现出色 并且还计划将其扩展至实际物体检测场景以进一步验证其适用性