基于智能交通的隐私保护道路状态实时监测方案

李家印，郭文忠，李小燕，刘西蒙

（1.福州大学数学与计算机科学学院，福建 福州 350108；2.福州大学网络安全福建省高校重点实验室，福建 福州 350108；3.福州大学福建省网络计算与智能信息处理重点实验室，福建 福州 350108）

1 引言

随着经济的飞速发展、社会城市化进程的加快，全球各大城市均面临交通拥堵带来的压力。近些年，我国机动车保有量持续快速增长，城市交通拥堵已成为大众出行讨论的焦点。交通的拥堵不但延长了人们出行的时间，增大了机动车的油耗，而且加剧了环境的污染[1-2]。更甚者，交通拥堵导致交通事故频发，给人们的生命和财产带来极大威胁。为缓解城市交通压力，构建智慧城市，建立完善的智能交通系统成为城市建设的关键。智能交通系统（ITS,intelligent traffic system）指对道路交通状况实施监测的系统，该系统借助数据挖掘方法获取道路的拥堵状态，然后根据系统分析的结果对机动车实施有效的调度[3-4]。事实上，许多监测手段已经应用到了智能交通系统，并实现了对交通拥堵状况的判断。例如，通过道路两侧安装静态传感器获取道路的实时数据，并将其传输到数据中心加以处理与分析，得到反映道路拥堵状态的数值。另外，借助高清摄像头采集交通图像数据，根据对图像的处理分析结果做出对道路拥堵情况的准确判定[5-7]。然而，静态传感器、高清摄像头的安装成本和维护成本十分高昂，尽管可以有效地实现交通状况的监控，但不适合大规模地部署[8]。此外，固定的静态传感器的感知区域有很大局限性，所获取的数据也过于稀疏，不利于数据的处理与分析。随着传感器功能的增加，越来越多的机动车安装了智能车载传感器设备[9]。研究学者利用车载传感器不断地收集机动车交通数据（如实时位置、行驶速度、方向、数据上报时间等信息），实现低成本、高精度的交通监测。此外，机动车数量庞大且行驶具有随机性，能够有效解决交通数据过于稀疏的问题[10]。然而，利用机动车交通数据实现道路状态监测，忽略了因数据泄露引发的一系列危害。由于交通数据包含诸多敏感信息，攻击者很容易通过数据提供者的历史数据推断出未来某个时间段数据提供者所处的位置，甚至还可以通过频繁出入的地方推测出数据提供者的个人信息，诸如兴趣爱好、健康状况、收入等敏感信息[11-12]。研究学者提出利用传统的加密算法对交通数据进行加密，以确保数据传输及存储过程中的安全性。处理中心在密态数据的基础上实现交通状态的监测。借助传统的加密算法尽管能够满足数据提供者对数据安全性的要求（如高级加密标准（AES,advanced encryption standard）[13-14]等），但传统的加密算法存在明显的弊端，即无法对密态数据直接进行处理与分析。为达到监测的目的，需要先对密文进行解密，这不但将明文数据暴露给了数据处理中心，而且还延长了交通监测所需的时间。Paillier 算法尽管可以避免加密数据的解密过程，但其完成数据处理与分析的过程非常耗时，违背了交通监测对时延的要求。更重要的是，借助加密算法能够保证在交通数据中的敏感信息不被泄露的同时，更需要实现机动车驾驶员对交通状态的安全查询，因此，实现对加密数据的查询功能是完成智能交通隐私保护的关键[15]。其不仅需要满足任意时刻机动车驾驶员对智能交通系统分析出的某一具体道路交通拥堵状态结果的查询，而且能够保证查询值的正确性及反馈结果的唯一性。通过对加密数据的查询，能够保证在整个智能交通系统的实现过程，机动车所产生的交通数据始终受到保护而不被泄露。因此，在保证交通数据隐私安全的前提下，既能快速地挖掘出数据的内在信息、又能安全且准确地实现驾驶员对交通道路拥堵状态结果的查询是研究隐私保护智能交通系统的核心难题。

安全多方计算（MPC,secure multiparty computation）为隐私保护智能交通道路监测的实现提供了可行的方案[16-18]，该方案在确保数据安全的前提下，完成对明文数据的处理、分析与查询。但是，如何设计适用于处理与分析机动车交通数据的安全计算协议，降低处理数据耗费的时间仍是实现交通监测所面临的难题。

针对上述问题，本文对传统K 最近邻（KNN,K-nearest neighbor）距离算法进行改进，提出了一种基于智能交通的隐私保护道路状态实时监测（PPIM,privacy preserving intelligent monitoring）算法。借助基础安全计算协议，并设计了一系列的安全计算协议，在保证数据隐私安全的前提下，完成了交通数据的处理与分析，通过部分已知道路的拥堵状态，达到对整个路网中其余未知道路拥堵状态的监测。此外，还提出一种改进型KNN 算法，通过引入皮尔逊相关系数，得到已知道路与未知道路之间拥堵状态的权重系数，提高了对道路拥堵状况监测的准确度。

2 预备知识

2.1 路网的拓扑结构与拥堵状态

交通路网（简称“路网”）指供机动车行驶的庞大道路，其最基础的结构是路段与路口，如图1所示。通常，路网的拓扑结构用图G(L,C,V)表示，其中，L表示路网中的道路；C表示道路L的中间位置；V表示道路L某一时间间隔内道路的平均速度，即此时道路允许的机动车通行能力。假设图G(L,C,V)包含n条道路，定义i∈[1,n]（i表示路网中道路的编号）。倘若道路i在时间间隔T内采集了m辆机动车的数据，并且上报k条的数据，vτ（τ∈[1,k]）表示每条数据中车辆的瞬时速度，单位为km/h。基于上述定义，可以计算出道路i在时间间隔T内的平均速度。结合真实的驾车体验，道路的拥堵状态可分为4 种不同程度。1) 当道路的平均速度在0＜vi≤ 10范围时，表示该道路处于十分拥堵的状态；2) 当10＜vi≤ 30时，表示该道路处于较拥堵的状态；3) 当30＜vi≤ 45时，表示明机动车可以在该道路上畅通地行驶；4) 当vi＞ 45时，表示该道路此时的通行状态十分畅通。

图1 路网的拓扑结构

2.2 传统的KNN 算法监测框架

KNN 算法常被用于监测道路交通的拥堵状态。若vτ(T)表示时间间隔T内道路τ待求解的预测值，v(T)表示时间间隔T预测vτ(T)所对应的特征向量。对于特征向量v(T)，KNN 算法在历史数据集中搜索与其距离最近的K个历史特征xi,xi+1,…,xi+K，利用式(1)将K个特征向量通过加权估计的方法，求解vτ(T)的值。

由式(1)可知，KNN 算法中的唯一参数是确定K，其值直接关系到判断未知道路拥堵情况的准确性。通常采用交叉验证法确定最优K值，具体步骤如下。

步骤1定义选取K的最大值Kmax和最小值Kmin。根据路网中道路总数可知Kmax=n,Kmin=1。

步骤2将n条道路的历史数据以时间间隔T为单位计算n条道路的n个特征值，得到道路历史数据集的集合{v1,v2,…,vn}，然后依次将数据集{v1,v2,…,vn}作为测试数据集，其他n-1个数据集作为历史数据集。

步骤3将K从Kmin以步长为1 进行取值，直至取到Kmax后结束。

步骤4优化二范式，使待求解道路τ的预测值vτ(T)与真实值相差最小。

步骤5计算n个数据集对应选取K值的平均误差百分比，并对n个值求均值，即其中，num(i,K)表示计算道路i时K的具体数值。

本文基于KNN 算法实现交通状态的实时监测，主要是因为其更能满足交通监测对时延的要求。首先，相比于其他数据预测算法，KNN 算法不仅具有简单易用的特点，而且能达到较好的预测效果；其次，KNN 算法模型的训练时间快，其模型训练主要是确定K的取值，对于特定的某个区域，一旦K值被确定，在相当长的时间内可以对未知数据进行预测；最后，KNN 算法对异常值不敏感，换而言之，交通数据内经常出现的异常值对KNN 算法的预测精度不会造成很大的影响。

2.3 安全两方计算

安全两方计算是指双方在互不泄露各自数据的前提下完成数据的处理与分析。假设2 个独立的参与实体Alice 和Bob，两者分别存储各自的私有数据，Alice 的私有数据是随机数a，Bob 的私有数据是随机数b。安全两方计算的目的是获取a×b的结果，但是Alice 和Bob 都不想泄露其私有信息的数值。安全两方计算过程如下。首先定义函数Γ是期望实现的乘法计算，经过执行z-1 次函数Γ得到最终结果Sz，即存在。然后Sz被随机分成az和bz，并满足Sz=az+bz的关系。最后Alice 获取az的值，Bob 接收bz的值。具体过程如图2 所示。

图2 安全两方计算过程

通过安全两方计算来维护交通数据的隐私安全，在不泄露数据敏感信息的前提下，实现对数据的安全处理。安全两方计算能够加快处理数据的速度，降低获取城市路网道路交通状态的时延，达到道路实时监测的目的。

2.4 基础安全计算协议

本文根据已有研究成果及基础安全计算协议，来实现所提PPIM 算法。基础安全计算协议基于2 个云服务器SP1和SP2，通过两者之间的安全交互数据来完成计算，具体如下。

基础安全乘法协议（BSMP,basic secure multiplication protocol）。假设云服务器SP1和SP2分别存储私有数据a和b，将满足ka+kb=ra rb条件所生成的4 个随机数ka、kb、ra和rb作为密钥。SP1计算a′=a+ra，SP2计算b′=b+rb，并将a′和b′进行互换。然后，SP2产生随机数vb并计算t=a′b+kb-vb，SP1计算va=t+ka-ra b′。经上述过程即可实现va+vb=ab的计算，并将va和vb替代SP1和SP2原有的数据a和b。因此，基础安全乘法协议可表示为映射va+vb←BSMP(a：b)。

基础安全除法协议（BSDP,basic secure division protocol）。SP1和SP2分别存储私有数据a和b，将满足ka+kb=ra rb条件所生成的4 个随机数ka、kb、ra和rb作为密钥。SP1计算a′=a+ra，SP2计算，并将a′和b′进行互换。然后，SP2产生随机数vb并计算，SP1计算。经上述过程即可实现的计算，并将va和vb替代SP1和SP2原有的数据a和b。因此，基础安全除法协议可表示为映射，其中，va和vb分别表示原始数据a和b的密文值。

3 交通监测方案

为实现智能交通隐私保护道路状态的监测，本节给出了系统监测的模型，并对模型内实体的功能逐一介绍；结合系统模型，阐明系统存在的安全威胁；为防止数据泄露带来的危险，设计了适于隐私保护改进型 KNN（IKNN,improved KNN）算法的高效安全计算协议。

3.1 系统模型

道路状态监测的系统模型如图3 所示，该模型包含4 个实体的参与，具体如下。

可信任实体（TA,trusted authority）。一个独立可信任的第三方，它的主要任务是生成随机数并将随机数通过安全信道发送给其他参与方。

数据提供车辆（VD,vehicle data）。负责机动车交通数据的收集，并将收集的数据实时地传输到云服务器，即云服务提供商。

云服务提供商（SP,server provider）。接收来自数据提供车辆发送的数据并对其存储和处理与分析。

导航提供商（NAV,navigation）。负责接收2 个云服务提供商计算出的结果，并将其发布给行驶在道路上的机动车，用于提升司机的驾驶体验。

图3 系统模型

3.2 安全威胁

安全威胁主要来自恶意攻击者对提供数据存储服务的第三方云服务提供商进行的恶意攻击，该攻击容易造成数据提供者信息的泄露。假设存在一个模拟器ϒ，其任意地产生随机值并获取安全计算协议真实的视图H1。基于H1，模拟器ϒ试图在多项式的时间内生成一个模拟的视图H2。假设存在2 个不共谋的恶意攻击者 A1和A2。攻击者 A1可以成功地攻击并获取存储在服务器SP1内的交通数据，一次成功的攻击意味着A1可以找到一个概率二项式算法成功地区分H1和H2，并结合获取的数据推测出真实的数据值。攻击者A2也可以成功地攻击并获取存储在服务器SP2中数据，A2完成一次成功的攻击同样意味着其可以找到一个概率二项式算法对H1和H2进行区分，结合获取的数据推测出其真实值。此外，云服务提供商是好奇并诚实的实体，在执行数据处理时会利用已知的部分数据来猜测真实的数据值。

3.3 设计目标

本文主要目的是实现对智能交通隐私保护道路交通状态的监测，因此，系统既要满足实现交通监测的目标，又要符合数据隐私保护的要求，具体要求如下。

数据的安全性。任何收集的机动车行驶数据都应该受到保护，比如车辆ID、车辆行驶的速度、车辆的经纬度等信息。

数据计算的低复杂性。用于数据加密的加密算法应当是轻量级的、快速的。

数据的轻量化传输。为了降低交通监测的时延，应尽可能地减少交通数据的传输量。

预测的实时性。为满足道路交通监测的实时性，利用少量的数据实现对整个路网道路状况的快速监测。

3.4 IKNN 监测算法

为提高传统KNN 算法的监测精度，本文提出了IKNN 算法，其主要思想是利用已知道路的部分平均速度对未知道路的平均速度进行预测。通过增加权重调节因子ω，借助机动车的历史数据，整合距离预测道路最近的K条道路与其之间的相似度值，调节不同道路在预测未知道路时的影响程度。对于权重调节因子ω的计算，本文首先采用归一化的欧几里得公式将获取的路段速度值归一化到0～1。然后利用式(2)所示的皮尔逊相关系数进行计算，获取所需的权重值。

其中，x表示待求解道路的历史平均速度的向量，y表示距离其最近的K条道路中某一条路段的历史平均速度向量。由皮尔逊相关系数的性质可知，ω值越大，说明向量x和y两者之间的相似度越大，反之亦然。基于ω给出IKNN 交通监测计算式，如式(3)所示。

ω的引入更加凸显出已知道路中每一条道路对未知路段具有不同程度的影响。根据选取的已知道路与待求解道路历史数据之间的皮尔逊相关系数，降低预测值与真实值之间的误差。

由式(3)可知，IKNN 算法的前提是确定K值及计算ω，具体如下。

步骤1利用收集的整个路网的历史数据，根据式(1)计算出时间间隔T内每一条道路的平均速度及经纬度信息。采用道路中间位置的经纬度Ci(x,y)表示道路i的空间地理信息。Ci(x,y)利用两点之间的中点求解公式进行求解，其中(x1,y1)表示道路i最靠近路口一端的经纬度信息，(x2,y2)表示道路i最远离该路口另一端的经纬度位置信息。

步骤2通过训练历史的交通数据，确定用于估计未知道路平均速度时的K值。

步骤3依次计算选取的K条道路与其余n-K条道路之间的权重向量Θ=(ω1,ω2,…,ωn-K)。

步骤4根据步骤3 得到的K值和式(3)计算出未知道路时间间隔T内待求解道路的平均速度vτ(T)。

4 隐私保护道路监测

本节阐述了智能交通隐私保护道路监测的实现过程。为说明算法执行的具体步骤，首先定义了机动车交通数据的数据格式及数据到云服务提供商的上传格式。然后阐述云服务提供商在保护数据隐私安全的基础上，采用IKNN 算法，实现道路交通状态的监测。

4.1 数据格式和数据传输

实现监测的关键是收集必要的数据。定义R(lat,lon,v,t)表示数据的上传格式，时间间隔T内道路i上行驶的车辆共上报k条数据，Dτ={(latτ,lonτ,vτ,tτ)|τ∈[1,k]}表示数据的集合。然后，将每一条数据内的每一个元素随机地分为两部分，即其中，。最后，每个元素被随机地分为2 个分量分别传输给云服务提供商SP1和SP2，即作为一个整体发送给SP1，传输给SP2。

4.2 经纬度距离安全计算协议

将数据安全地外包给云服务提供商后，云服务提供商利用存储的数据计算相应道路的平均速度。对于道路i，SP1根据存储的速度数据分量，对集合计算SP2计算。根据机动车的历史经纬度计算能够体现道路空间位置的信息。路段i的GPS 纬度信息的集合lati={lat(i,τ)|τ∈[1,k]}存储在SP1，经度信息集合loni={lon(i,τ)|τ∈[1,k]}存储在SP2。根据3.4 节中步骤1 所述，近似地计算出道路i的空间经纬度位置信息Ci(latC,lonC)。为计算空间两点经纬度之间的距离，本文将两点间距离计算方法推广到求解空间两点间经纬度的欧氏距离，如式(4)所示。

其中，R表示地球的半径，p表示两点之间经度差的余弦值，li=cos(lati)，lτ=cos(latτ)，bi=sin(lati)，bτ=sin(latτ)，p(i,τ)=cos(loni-lonτ)。根据式(4)计算基于密文状态下2 个不同经纬度之间距离，具体如下。

步骤1SP1执行l=lilτ=cos(lati)cos(latτ)和b=bibτ=sin(lati)sin(latτ)的计算。

步骤2SP2对两点之间经度进行差值运算，即p(i,τ)=cos(loni-lonτ)。

步骤3根据泰勒公式的展开近似等式，即以及二项式展开，计算对应数值反余弦的近似值。当f∈[9,7,5,3]、（f和ρ每次选取的元素位置相同）时，根据每次选取的f和ρ值，执行BSMP，结合f和ρ的取值范围，协议执行可以表示为，其中，g∈[1,f]。然后，将计算得到的va(f,g)发送给SP1，将获得的vb(f,g)发送给SP2。

步骤4SP1计算，SP2计算

步骤5SP1执行va=+b的计算，SP2执行的计算。

经上述步骤，得到路网中任意2 条道路之间的空间距离d。并且满足d=va+vb的映射关系。其中，va存储在SP1，vb存储在SP2。

假设时间间隔T内，智能交通系统共收集到来自h条道路上的机动车的交通数据，根据前文所述的平均速度计算方法，系统计算出h条道路的平均速度，组成向量V=[v1,v2,…,vh]。另外，向量V随机地被分为两部分V′和V′，然后分别存储在SP1和SP2。结合存储在云服务器中n条道路的历史数据，提取出任意2 条道路之间的空间相关性，得到n条道路的空间相关性矩阵Ω，如式(5)所示。

同样地，空间相关性矩阵Ω被随机地分为Ω′和两部分分量，被依次存储在SP1和SP2，并且满足的等式关系。其中，分别如式(16)和式(17)所示。

4.3 权重系数安全计算协议

为获取已知h条道路与未知的n-h条道路之间的权重系数，通过已知h条道路的历史平均速度向量Vi={vi|i∈[1,h]}，完成对未知道路的历史平均速度向量Vτ={vτ|τ∈ [h+1,n]}的求解。具体步骤如下。

步骤1SP1计算向量Vi的期望E(Vi)、和E2(Vi)，同理，SP2计算得到Vτ的期望E(Vτ)、

步骤2SP1求解SP2计算

经上述计算，最终未知道路τ在时间间隔T内道路的平均速度vτ被随机地分为，并分别存储在SP1和SP2中。

通过执行设计的经纬度距离安全计算（SLD,secure length distance）协议、权重系数安全计算（SWF,secure weight factor）协议和道路监测安全计算（SMS,secure monitoring scheme）协议这3 个安全计算协议，可以完成智能交通系统隐私保护道路状态实时监测的任务。在IKNN 算法的基础上，本文首先利用SLD 协议获取体现道路之间空间位置的空间相关性矩阵Ω；然后根据SWF 协议计算出路网中任意2 条道路之间的ω，并得到权重向量Θ；最后在获取的空间相关性矩阵Ω和权重向量Θ的基础上，依据式(3)并按照SMS 协议的执行过程即可实现隐私保护交通状态的实时监测。总而言之，依次执行SLD、SWF 和SMS 这3 个安全计算协议，借助存储在云服务器中的交通数据即可实现整个智能交通监测的算法。因此，基于上述过程，可根据已知h条路段的平均速度，在保证数据隐私安全的前提下，实现对其余n-h条未知道路的平均速度的预测。然后，将系统最终的处理分析结果提供给导航提供商。导航提供商将获取的数据直接进行相加，获取时间间隔T内整个路网所有道路的平均速度，并根据速度的相加结果，判断出道路交通真实的拥堵情况。最后，将分析出的真实拥堵状况实时地发布给机动车驾驶员。

5 安全性分析

5.1 数据存储安全性分析

根据本文的数据传输策略，SP1存储数据分量x1，SP2存储数据分量x2。假设2 个攻击者 A1和A2，A1对SP1发起攻击并获取SP1的内部数据，A2对SP2发起攻击并获取SP2的内部数据。由于云服务提供商SP1和SP2存储的数据仅仅是原始数据的分量，当成功攻击SP1获取存储在其中的数据x1后，由于x1本身的随机性，A1并不能通过数据分量x1对原始数据x做出正确的推断；同样地，当成功攻击SP2获取存储在其中的数据x2后，由于x2同样具备很大的随机性，A2也不能由数据分量x2对原始数据x做出正确的推断。

5.2 数据计算安全性分析

假设 A1对SP1实施攻击并能够获取其内部存储的数据，并拦截云服务提供商SP1和SP2之间交互运算时所产生的中间值；A2同样对SP2进行攻击，并拦截两服务器之间数据交互计算所生成的中间值。当SP1安全地接收可以作为密钥的随机数ra时，在ra的基础上将获取的原始数据分量x1与之相加，即计算x3=x1+ra。当x3被获取后，攻击者 A1很难根据x3的值推算出x1的值，因此 A1更无法对完整的原始数据x实现正确地推断。同理，A2也无法对执行上述操作的数据进行正确的推断。当云服务提供商SP1和SP2执行安全计算协议后得到最终的路段平均速度，该速度又被随机地分成了两部分并分别存储在SP1和SP2。对于发送给导航提供商的最终数据也仅仅只是体现道路的拥堵情况，并不能推测出机动车的原始数据。本文所设计的SLD 协议、SWF 协议和SMS 协议均依照上述分析的安全交互过程进行计算，因此，本文所提PPIM 算法可以保证数据的隐私安全不被泄露，进而完成对数据的一系列操作。

6 性能分析及实验验证

6.1 性能分析

计算复杂度。为评估本文所提PPIM 算法的计算复杂度，先对算法中每个安全的子协议进行计算复杂度分析。假设TBSMP、TBSDP和TPaillier分别表示BSMP、BSDP 及Paillier 算法执行一次所需的时间，具体数值通过仿真实验获得，如表1 所示。由表1 可知，TBSMP≈TBSDP≪TPaillier。对于SLD协议，因其需要借助泰勒公式对反余弦函数近似求解，完成一次迭代的计算需要执行9 次BSMP，因此，执行输入数据大小为n，计算复杂度为9O(n)TBSMP。对于SWF 协议，系统完成一次完整协议计算需要进行3 次BSMP 计算及一次BSDP计算，执行输入数据大小为n，SWF 协议所需时间为3O(n)TBSMP+O(n)TBSDP。同样，对于完成道路监测协议SMS 协议，其执行BSMP 的次数与K的取值有关，并且完成一次SMS 协议也需执行一次BSDP。对于执行输入数据大小为n，SMS 共需的时间为3KO(n)TBSMP+O(n)TBSDP。因此，将3 个过程的计算复杂度进行相加即可得到PPIM 算法的计算复杂度，即(11 +3K)O(n)TBSMP。假设数据的大小仍然为n，采用Paillier 算法完成对道路状态的监测，则需要的时间复杂度是nO(n2)TPaillier。通过表2，可以更加清晰地比较SLD 协议、SWF 协议、SMS 协议、PPIM 算法及Paillier 算法之间的计算复杂度。

表1 协议执行一次所需时间

表2 协议/算法计算复杂度

通信开销。借助对每个子协议的分析，获取整个算法执行过程中的通信开销。表3 给出了SLD 协议、SWF 协议、SMS 协议及PPIM 算法各自完成一次计算所需的数据通信轮数。通过分析基础协议BSMP 和BSDP，完成BSMP 或者BSDP 都需要2轮的通信开销。根据计算复杂度分析，完成一次SLD 协议需要运行6 次BSMP，因此其需要进行数据交互的轮数是12；对于SWF 协议，其需要运行3 次BSMP 和1 次BSDP，所以共需8 轮的数据交互；然而，执行SMS 协议同样与K的取值有关，需要数据交互的轮数是6K+2。因此，根据3 个协议计算时交互的轮数，得出PPIM 算法需要的通信开销，即交互22+6K轮。

表3 执行协议/算法通信轮数

6.2 实验验证

基于真实的交通数据，本节通过实验对PPIM算法的性能进行验证。首先，通过未知数据预测误差衡量IKNN 算法的有效性；然后，给出每一个安全计算协议及实现PPIM 算法运行时间结果；最后，给出完成PPIM 算法各阶段所需通信成本的仿真。为验证隐私保护下IKNN 算法的有效性，本文用e表示对道路平均速度预测的误差率[19]，其计算如式(8)所示。

实验的仿真数据为福州市200辆出租车的相关数据，包含出租车行驶的瞬时速度、GPS 经纬度位置信息、数据上报的时间及机动车的ID 信息。仿真实验平台是在RAM 为16 GB，CPU 为1.80 GHz 的Intel Core(TM) i7-8550U 的笔记本电脑。本文将K的值设为4，时间间隔T设为5 min[20]。

在保证数据隐私安全的前提下，分别采用KNN与IKNN 这2 种算法估计未知数据的误差，曲线如图4 所示。从1 000 个数据中，依次随机在集合M=[200,300,…,800]选取不同数量的数据Ml（l表示集合M中元素位置的编号）作为已知数据。利用Ml个已知数据，估算其余没有被选取的1000-Ml个数据。由图4 可以得出，随着已知数据与数据总量比值的增大，无论是KNN 算法还是IKNN 算法，对未知数据估计的准确度降低了6%～8%的误差。更重要的是，本文所提IKNN 算法的曲线一直处于KNN 算法曲线的下方，说明IKNN 算法在实现道路状态监测上具有更好的准确度。

图4 2 种算法估计未知数据估计曲线

本文所提IKNN 算法与贝叶斯（Bayes）算法和支持向量机（SVM,support vector machine）算法这2 种算法进行的交通监测预测准确度比较如图5 所示。数据总量同样为1 000，选择200～800 范围，数据步长为100。需要说明的是，SVM 算法采用的核函数是高斯核函数（RBF,radial basis function），正则化参数δ=5，核函数参数ε=0.01。由图5 可知，IKNN、Bayes 和SVM 这3 种算法的未知数据预测误差都随已知数据量的增加出现了不同程度的下降。从曲线变化过程可知，IKNN 算法和SVM 算法的预测精度均优于Bayes 算法，IKNN 算法与SVM算法曲线尽管有部分相交，但随着数据量的增加，IKNN 算法的准确性更高。

图5 3 种算法交通监测预测准确度曲线

SWF、SLD 和SMS 这3 个协议在不同的数据量下的运行时间如图6 所示。从图6 可以看出，每个协议在加密不同量的数据量时，其效率都达到了毫秒级，并且3 个协议之间运行时间存在的差异与6.1 节的理论分析结果一致。

图6 3 个协议的运行时间

为说明本文所提PPIM 算法不仅完成了对道路状态的监测，而且具备安全、高效处理数据的优点，本文所提PPIM 算法与Paillier 算法进行了对比。Paillier 算法是加法同态加密算法，可以在不泄露数据隐私安全的前提下，实现对数据的安全处理。通过设置变量N及2 个大素数p和q，产生用于保护数据隐私的密钥，其整个过程通常分为密钥生成、加密和解密3 个阶段。

1) 密钥生成

首先，选取2 个大素数p和q，并使其满足gcd(pq,(p-1)(q-1))=1的要求。

其次，计算N=pq，λ=lcm(p-1,q-1)，并定义函数

最后，随机选取g且满足g＜N2，计算u=((L(gλmodN2))-1mod)N，可生成所需的公钥(n,g)和私钥(λ,u)。

2) 加密

对需要加密的数据m（0＜m＜N），并计算其密文

3) 解密

基于密钥生成阶段的私钥(λ,u)，计算出明文m=(L(cλmodN2)u)modN。

需要说明的是，Paillier 算法满足系统加密的2个消息相乘的结果解密后恰好是2 个消息明文状态相加的结果，这种方式与本文数据传输与处理策略相同。因此，将本文所提PPIM 算法与Paillier 算法进行对比，得到图7 所示的仿真结果。需要说明的是，采用Paillier 算法时，设置变量N=2 048，并且生成2 个1 024 位的大素数p和q。由图7 可知，本文所提PPIM 算法比Paillier 算法具备更加快速地实现对道路状态监测的功能，更好地满足智能交通系统对低时延的要求。

图7 2 种算法的交通监测实现效率对比

本文用于衡量通信开销的单位是bit，其测量依据是基于IEEE 754 标准[21]。由该标准可知，任何以单精度浮点形式存储的值都需要32 bit，双精度浮点则需要64 bit，而真实的交通数据属于单精度浮点。各协议和算法所对应的通信量如图8 所示。由图8 可知，实现整个PPIM 算法，即使数据大小为1 000 时，其数据的通信量还不足0.2 MB，现有的网络带宽很容易满足其要求。

图8 协议/算法的数据通信量

7 结束语

本文实现了机动车交通数据隐私保护的道路交通监测。为了优化KNN 算法，提出了IKNN 算法，通过引入道路之间的相似程度，对预测值进行有目的的调整，提高了交通监测的精度。为了提升数据处理的效率，还设计了适用于IKNN 算法的安全计算协议。最后，通过真实数据的仿真实验证明，所提算法不但有效地实现了隐私保护下的智能交通道路监测，而且满足交通监测对实时性的需求。