基于本地化差分隐私的电动汽车接入充电点位置隐私保护

李科寰 李红娇 田秀霞

(上海电力大学计算机科学与技术学院 上海 200090)

0 引 言

电动汽车接入电网(Vehicle-to-grid,V2G)借助电动汽车(Electric Vehicle，EV)充放电的特点，实现了电网与车辆的双向互动，能够帮助电网对负荷进行“削峰填谷”，提高电网的稳定性，降低能耗以及发电成本[1]，是智能电网技术的重要组成部分。随着V2G网络的发展和推广，EV用户数量快速增加，在未来EV大量使用的情况下，可以通过分析充电点的状态数据进行新充电点的选址和规划，服务提供商也将尽可能通过分析V2G发布的数据从用户身上获取利益，例如，应用程序通过利用EV所处的位置和电池状态规划下一个充电点这类功能来吸引用户，或是对用户进行周边服务信息推送等。然而，某EV经常访问的充电点位置可与其用户的住所、工作地点、兴趣点等相联系，容易暴露具体用户的家庭住址、健康状况、个人偏好、社交关系和其他私人信息[2]，一旦被不怀好意的攻击者利用，用户将承担个人隐私泄露的巨大风险[3]。

一方面，V2G的管理和服务提供需要数据中心收集EV接入充电点的位置信息并发布；另一方面，用户对提供他们的身份和位置数据存在顾虑。因此，如何在隐私保护考虑下处理这些位置数据对于V2G发展、EV用户的安全和EV的普及至关重要。近年来，研究人员提出的EV位置隐私保护方法可分为两种：一种是利用匿名、假名技术对用户的真实ID进行隐藏，将准确的位置提供给电网控制中心获得服务，使非授权者无法确定用户的真实身份[4]；另一种是对用户的位置数据进行扰动等模糊化处理，隐藏部分位置信息。

目前，第一种隐藏身份的方式在V2G网络中提出较多。文献[5]使用部分受限盲签名技术，EV和充电点通信时使用假名，只有智能电网服务器(第三方可信实体)可以将假名映射到真实车辆身份，当EV从一个站移动到另一个站时假名改变；文献[6]提出一种基于计算复杂性理论的同态公钥加密隐私保护认证方案，通过可信第三方在EV、聚合器、充电站和电网控制中心之间建立通信连接，仅仅提供虚拟身份的提交注册，只传输共享密钥，令攻击者无法通过攻破控制中心威胁用户信息安全。

然而，上述基于身份匿名的保护机制存在两个主要问题：(1) 由于大多需要可信第三方存在，数据在多个实体之间共享以供分析时灵活性较差，存在密钥托管问题；(2) 隐私保护强度不足，可信第三方易受攻击，且不能抵御背景知识攻击。

第二种隐藏位置的方式在V2G网络中应用较少，但在众包位置数据采集隐私保护方面已逐渐引起关注，其主要利用本地化差分隐私技术(Local Differential Privacy,LDP)将数据隐私化处理过程转移到客户端上，摒弃可信第三方的假设，使数据收集服务器无法得知具体个人的位置数据，仅能在扰动后的数据上作分析统计，从而实现位置隐私保护。文献[7]首先研究了LDP在室内定位数据采集中的应用，将室内区域用大小相同的网格划分，令B={b1,b2,…,bn}表示n个信标ID，用户访问的信标点对应位为1，其余位为0，对B进行随机响应，使结果满足本地化差分隐私，可通过结果期望最大化估算出室内区域的人口密度。该文给出了一种空间划分编码的启示，但其映射方式可表达的空间范围较小。文献[8]针对用户不同的隐私保护需求提出了一种个性化的LDP隐私保护方法，每个用户要求的位置隐私保护空间范围称为安全区域，采用LDP对安全区域内的位置进行扰动，使得攻击者识别出任一个具体用户安全区域的概率不超过某阈值。文献[9]先利用维诺格进行路网分割编号，设计出一种针对路网空间较合理的位置数据字符串映射方法，给出一种可查询的满足本地化差分隐私的众包位置数据采集方式。本文针对传统身份匿名方式中存在的可信第三方依赖、未考虑基于背景知识攻击的问题，结合上述维诺格分割和安全区域的概念，提出一种基于LDP的EV接入充电点位置隐私保护方法。

对于充电点的位置分布空间范围，采用基于距离变换的方法利用聚合器作为维诺格生成元生成维诺图，一个维诺格作为一个安全区域，维诺格编号作为用户所处充电点位置数据向量的一部分；对EV用户端上传的充电点位置数据进行K-RR随机响应处理，通过隐私理论分析证明其满足ε-LDP；聚合器将收集的充电点状态数据发送给V2G数据中心，结果可用于估计EV接入充电点的位置分布。通过真实数据集上的实验证明本文方法与传统k-匿名位置保护算法相比较在数据可用性相当的前提下，算法安全性和算法效率具有优势。

1 本地化差分隐私保护模型

1.1 差分隐私

差分隐私[10-11]模型中，攻击者的计算能力和所具有的背景知识无法影响模型对用户数据的隐私保护程度。

定义1ε-差分隐私：若随机算法A对任意一对至多只相差一条记录的邻近数据集D和D′及任意输出O⊆Range(A)均满足下列等式：

(1)

则称算法A满足ε-差分隐私，其中Pr表示概率。

差分隐私严格的数学定义保证了无论数据集D中是否存在单条数据记录r，算法A的输出都将保持几乎一致的概率分布。实现差分隐私的常用机制是向真实数据添加Laplace噪声，差分隐私参数ε越小，所提供的隐私保护强度越大，但同时也会给真实结果带来更大的噪声。

1.2 本地化差分隐私

随着众包数据采集的流行，LDP提出了在数据收集之前就进行隐私保护扰动的概念，这已经成为继传统差分隐私技术之后一种强健的隐私保护模型。

定义2ε-本地化差分隐私[12-13]：若随机算法A对任意两个数值l和l′及任意输出O⊆Range(A)均满足下列等式：

(2)

则称算法A满足ε-LDP。

1.1节介绍的传统的差分隐私技术将原始数据集中到一个第三方数据库，然后在收集到的数据表上进行差分隐私保护，也被称为中心化差分隐私(Centralized Differential Privacy)技术。传统差分隐私被证明可以应用于有多用户位置的信息发布，但并不适用单个用户位置[14]。中心化差分隐私保护模型里的一个重要假设：第三方数据收集者是可信的，不会泄露用户个人的敏感信息，数据扰动处理发生在数据收集方。中心化差分隐私处理模型如图1(a)所示，LDP处理模型如图1(b)所示，它们的主要区别：LDP中不存在第三方数据收集者可信的假设，数据扰动处理在客户端直接进行，每个用户按照隐私算法对原始数据进行扰动，数据收集者收集到的是扰动后的数据，并对数据分析者的查询请求做出响应。

(a) 5%空间范围查询(b) 10%空间范围查询

(a) 中心化差分隐私处理模型

(b) 本地化差分隐私处理模型图1 差分隐私处理模型

LDP技术在客户端直接保护敏感信息的特点使隐私化处理过程更加简洁明了，此外，由于每个用户能够掌握个人的敏感信息处理过程，也使得用户可以根据自身需求，进行更加个性化的隐私设置。

1.3 随机响应

随机响应是目前最常用的实现LDP的扰动机制，其作为一种调查技术，用于减少在敏感问题的情况下由被调查者的错误答案引起的误差[15]。例如，给出的敏感问题(如：你的年龄是否超过30岁)的可选择答案X有“是”或“否”两种，要求总共n个被调查者根据一枚非均匀硬币的正反面给出答案，假设其正面朝上的概率为p，反面朝上的概率为1-p，被调查者秘密查看硬币抛掷的结果，然后回答真实答案(如果硬币正面朝上)或虚假答案(如果硬币反面朝上)。若真实情况为超过30岁的人占的比例为π，而调查结果中有n′人的答案为“是”，n-n′人的答案为“否”，则回答“是”或“否”的被调查者比例为：

Pr(X=“是”)=πp+(1-π)(1-p)

(3)

Pr(X=“否”)=(1-π)p+π(1-p)

(4)

对真实比例π的极大似然估计为：

(5)

(6)

(7)

因此，已知调查总人数n、回答“是”的人数n′、作出真实回答的概率p，可估计出超过30岁的人数的统计值，根据LDP的定义，要满足：

隐私预算设定为：

(8)

(9)

1.4 维诺图

定义3维诺图(Voronoi Diagram)[17]。设点集P={p1,p2,…,pn}(2≤n≤∞)中的任意点pi(i∈{1,2,…,n})所对应的维诺多边形V(pi)为：

(10)

式中：H为维诺多边形的边的集合。则称Vor(P)={V(p1),V(p2),…,V(pn)}为由点集P生成的维诺图，如图2所示。

图2 维诺图局部

维诺图将目标空间进行无重叠的区域划分，使对象与各个元素距离最小，pi称为维诺多边形V(pi)的生成元，维诺多边形V(pi)的边界被连接两个邻点的直线垂直平分，V(pi)内的任意点q到该生成元pi的距离小于到其他生成元的距离，处于边界的点到包含这条边界的维诺格生成元的距离相等。

本文算法将V2G网络中的EV聚合器作为维诺图生成元进行划分编号，原因为：

1) 符合V2G网络结构中一个聚合器管理多个充电点的结构特性，每个维诺格内都有EV访问的充电点，每个EV访问的充电点都处于维诺格中，维诺格编号作为用户所处充电点位置数据字符串的一部分，不需扰动，使聚合器直接得知一个维诺格内接入的真实EV总数。

2) 一个维诺格作为用户的一个安全区域，访问每个聚合器管理区域中的EV用户分布较为均匀，聚合器可以将维诺格变动快速告知充电点，便于数据管理。

2 位置数据隐私保护算法

EV接入充电点进行充放电时，需要用户提供ID，一个聚合器管理多个充电点，聚合器处收集的充电点状态数据包括接入的EV用户ID和充电点位置ID。本节根据充电点状态数据的特点，介绍EV接入充电点位置数据的LDP保护算法。

2.1 充电点位置空间的维诺格划分

文献[11]针对路网空间进行维诺格划分时使用了逐点加入法，通过对维诺图进行局部修改来生成新的维诺图。逐点加入法构造简单但存储复杂，在对充电点进行维诺格划分的问题上，充电点的分布不规律，生成的计算较复杂，因此，本文在维诺格划分上采用基于距离变换的维诺图栅格算法。

将n个聚合器位置坐标集表示为P={p1,p2,…,pn}，作为维诺图的生成元，要保证划分后每个充电站的位置到所属维诺格内聚合器的位置距离比到其他聚合器内的距离都小。首先定义两个聚合器栅格p1(x1,y1)与p2(x2,y2)之间的欧氏距离为：

(11)

计算出每个聚合器pi(1≤i≤n)与和自身相邻的聚合器之间的欧氏距离，某聚合器栅格Pk(1≤k≤n)的隶属编码定义为距其最近的栅格的编码，重复上述步骤直到所有的聚合器栅格皆被检索完毕，一个聚合器坐标生成一个维诺格，得到充电站位置所在空间分布的维诺图。利用上述维诺图栅格算法在本文所用实验数据集上得到的空间区域划分结果(以15个聚合器为例)如图3所示。

图3 充电站分布的维诺图分割空间

V2G数据中心存储维诺图信息并给每个聚合器发放分组信息G={Vi,m,〈loc0,loc2,…,locm-1〉}，其中：Vi为聚合器管理的维诺格编码；m为该聚合器内充电点的个数；〈loc0,loc2,…,locm-1〉为充电点的位置ID。

2.2 基于LDP的EV接入充电点位置数据隐私保护

基于LDP的EV接入充电点位置隐私保护模型如图4所示。模型包括两个主要部分：客户端和服务器端。客户端为EV用户移动设备，完成满足LDP的充电站位置ID数据随机响应；服务器端为V2G数据中心，完成维诺格划分和编号以及查询结果的估计与发布。两者之间进行通信的聚合器除了作为维诺格生成元，还对一个维诺格的所有充电点状态数据进行聚合以及保存维诺格划分信息。下面介绍客户端的随机响应过程和服务器端的接收过程，结果可用于估计EV通过充电点接入V2G的分布。

图4 基于LDP的EV接入充电点位置隐私保护模型示意图

(1) 客户端。EV接入充电点充放电时，其所处的维诺格作为一个基本的安全区域，充电点为其提供该安全区域内所有充电点的位置ID数据〈loc0,loc1,…,locm-1〉，其中lock(0≤k≤m-1)为此充电点位置，根据K-RR随机响应，给定隐私参数ε，每辆接入的EV以如下概率上传自己位置数据loci(0≤i≤m-1)：

(12)

则安全区域内某一EV的真实ID应与其真实接入充电点ID在一定概率下无法对应。

(2) 服务器端。在接收一定时间段内EV接入充电点的位置数据后，服务器将其存储在数据库中以供将来分析。令R(〈Vi,lock〉,ts)表示数据库中的表，其中：〈Vi,lock〉是某一聚合器管理的安全区域内的充电点接入状态，lock为有EV接入的充电点，ts表示收集该状态信息的时间戳。服务器收集到该状态信息时按照时间戳ts将记录〈Vi,lock〉插入表R(〈Vi,lock〉,ts)中。

综上，本文设计的满足LDP的EV接入充电点位置数据隐私保护算法如算法1所示。

算法1满足LDP的EV接入充电点位置数据隐私保护算法

输入：聚合器位置坐标集P={P1,P2,…,Pn}，隐私参数ε，空间计数查询范围Range。

输出：空间计数查询结果Q(Range)。

1.控制中心将P用维诺图划分，对每个聚合器Vi发放G={Vi,m,〈loc0,loc2,…,locm-1〉}；

2.充电点告知EV所处安全区域内所有充电点位置〈loc0,loc1,…,locm-1〉；

3.for each用户ui：

4.获得自身所处充电点位置lock；

5.生成位置向量L={loc0,loc1,…,lock,…,locm-1}；

6.以概率Pr(loci|lock)上传lock或loci(i≠k)到聚合器；

7.for each聚合器Vi：

8.将一定时间段内有EV接入的充电点lock加上编号Vi和时间戳ts发送给服务器端；

9.end for

10.服务器端估算Q(Range)

11.end

2.3 隐私性和可用性分析

2.3.1隐私性分析

定理1算法1满足ε-LDP。

证明设一个维诺格区域内充电点总数为m，接入的EV总数为n，在给定隐私参数ε下，接入该维诺格内充电点的EV发送真实充电点位置lock的概率为:

(13)

式中：LP表示概率的最大似然估计。

同理，发送其余m-1个虚假位置中任意一个的概率为:

(14)

则有:

(15)

2.3.2 可用性分析

本节分析收集到的位置数据可用性，即能否得出EV空间计数值的无偏估计。V2G数据中心服务器估算Q(Range)时，查询范围存在完全覆盖k个维诺格区域的部分和仅覆盖内部一部分区域的部分，考虑查询中涉及的两种类型的空间范围：

1)Q(Range)的空间范围完全覆盖k个维诺格的区域：控制中心直接根据k个聚合器发送的数据表记录总数确定Q(Range)的EV计数值k|R|，其中R表示范围。

2)Q(Range)的空间范围只覆盖一个维诺格部分的区域：控制中心处根据收集到的位置应答分布以及预设的真实应答概率Pr[LP(loci,n,ε)=lock]估计查询结果的具体流程如下。

(1) 假设某维诺格内部区域Range中接入的电动汽车用户数占所处聚合器管理区域内用户总数的比例为π，则发送真实位置的用户比例及发送假位置的用户比例分别为：

(16)

(2) 根据极大似然估计法构建似然函数如下：

L=[πP+(1-π)(1-P)ni][(1-π)P+

π(1-P)](n-ni)

(17)

式中：ni表示响应在某维诺格内部空间范围Range中的用户个数；n为某时间段内该聚合器管理区域内用户的总数。

(3) 对两边分别取对数后求导，令导数为零，可得到关于π的极大似然估计为：

(18)

(19)

当Q(Range)涉及的空间范围同时包含k1个完整维诺格区域和k2个维诺格内部区域时，空间计数值可表示为：

(20)

3 实 验

在真实充电站数据集上利用本文所提出的基于LDP的EV接入充电点位置数据隐私保护算法处理数据后，进行空间范围查询，并与基于泛化的k-匿名算法[19]对比，根据查询结果范围的相对误差以及查询的运行时间来验证算法的可用性和算法效率。

3.1 充电站数据集

实验采用爱尔兰充电站状态数据集，该数据集记录了从2017年至2019年的爱尔兰电动汽车充电站的接入访问状态，可反映出一定时间段内电动汽车接入充电站的位置分布，该数据每五分钟收集一次，内容包括爱尔兰163个充电站的ID、类型、访问状态、经纬度坐标，充电站的总体位置分布如图5所示。

图5 爱尔兰电动汽车分布地理位置

3.2 实验环境

实验采用的计算机为Intel i5 处理器，8 GB内存，Windows 10(64位)操作系统，所有算法由Python语言实现。本文在实验数据集上对算法的范围查询相对误差及算法运行时间分别进行了测试。

3.3 实验数据预处理

实验主要提取数据集中的充电站ID、经纬度坐标和访问状态，对只停放而未接入充电点的状态数据进行剔除，预处理之后的实验数据集属性如表1所示。原始数据集中并未给出聚合器的位置与数量，故采用K-means[18]方法对充电点位置聚类，产生的聚类簇中心为聚合器位置，通过调整聚类簇数量来测试一个安全区域内充电点状态数据的稀疏程度对实验结果的影响。

表1 实验数据集属性

3.4 实验结果分析

算法的隐私保护强度已在定理1中证明，实验主要验证算法的相对误差及运行时间，并与传统的基于k-匿名的方法进行了对比。

3.4.1空间范围相对误差

使用相对误差[20]来衡量空间范围查询的精确度，相对误差表示为：

图6显示了EV接入充电点位置的查询结果相对误差。可以看出，随着查询范围的增大，算法的查询精度得到提高，这是因为随着查询选择范围的增大，用户应答范围选择性减小，ε增大，给真实结果注入的噪声变小，造成查询相对误差逐渐减小。当查询范围固定时，算法的查询精度随着聚合器数量的增加而提高，这是因为聚合器数量越多，EV对充电点的接入位置数据越密集，响应的位置距离真实位置越接近。

(c) 15%空间范围查询(d) 20%空间范围查询

(e) 25%空间范围查询图6 EV接入充电点位置查询结果相对误差

表2对比了k-匿名算法泛化模糊充电点位置数据与本文提出的ε-LDP算法的空间范围查询误差率结果，其中ε-LDP算法空间范围大小为实验数据集所在空间面积的25%，聚合器数量为15个。根据充电点的总数163个，当k-匿名的参数k为10时，匿名区域泛化为至少拥有10个充电点的空间范围，与ε-LDP算法的15个维诺格内充电点数量相当。可以看出，两种算法在对比结果中查询相对误差率相当，而本文算法所基于的LDP技术的优势在于不需要第三方先收集原始数据集，也无须考虑攻击者拥有的背景知识，能对用户接入位置提供更加彻底的隐私保护。

表2 查询误差率对比

3.4.2运行时间

根据V2G网络中控制中心定期发布汇聚数据的特点，分别提取了1、3、5、7天的数据作为新的4个数据集，在这四个数据集上分别进行500次20%空间范围查询后取平均值。由图7可以看出运行时间基本随数据量的增大而线性增长；7天内控制中心处接收到的状态数据有328 608条，运行时间在11 s内。

图7 不同数据量的查询运行时间对比

表3在真实数据集上将本文算法与k-匿名算法运行时间作了对比，本文算法使用20%空间范围查询，其中：ε是LDP算法中的隐私预算参数，ε越小隐私保护度越大；k是k-匿名算法中与隐私保护程度相关的参数，k越大隐私保护度越大。可以看出ε-LDP算法在实际数据集上的运行时间不受设置的隐私预算参数ε影响，原因是参数ε只影响算法效用性，而不影响算法的运行时间；而k-匿名算法则随着隐私保护程度提高运行时间也增加。可以说明在实际数据集上ε-LDP算法的运行效率更高。

表3 算法运行时间对比

4 结 语

本地化差分隐私(LDP)技术是目前众包数据采集中最先进的隐私保护技术。随着V2G网络的发展，数据隐私保护要求提升，本文首次提出将LDP技术应用于EV通过充电点接入V2G时的位置隐私保护，以聚合器位置为生成元对充电站分布空间进行了维诺图划分，使用户的位置数据向量在客户端处就进行K-RR随机响应处理。通过隐私的理论分析和真实数据集上的实验结果验证了LDP方法在充电位置数据隐私保护问题方面与k-匿名算法比较，在可用性相当的情况下，算法安全性和效率更佳。下一步将考虑利用LDP直接在客户端处进行隐私保护的特点，为EV用户对数据不同的隐私需求程度个性化地设置隐私参数ε，以提供更好的需求服务。