基于智能交通的隱私保護(hù)道路狀態(tài)實(shí)時(shí)監(jiān)測(cè)方案

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

（1.福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108；2.福州大學(xué)網(wǎng)絡(luò)安全福建省高校重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108；3.福州大學(xué)福建省網(wǎng)絡(luò)計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室，福建 福州 350108）

1 引言

隨著經(jīng)濟(jì)的飛速發(fā)展、社會(huì)城市化進(jìn)程的加快，全球各大城市均面臨交通擁堵帶來的壓力。近些年，我國(guó)機(jī)動(dòng)車保有量持續(xù)快速增長(zhǎng)，城市交通擁堵已成為大眾出行討論的焦點(diǎn)。交通的擁堵不但延長(zhǎng)了人們出行的時(shí)間，增大了機(jī)動(dòng)車的油耗，而且加劇了環(huán)境的污染[1-2]。更甚者，交通擁堵導(dǎo)致交通事故頻發(fā)，給人們的生命和財(cái)產(chǎn)帶來極大威脅。為緩解城市交通壓力，構(gòu)建智慧城市，建立完善的智能交通系統(tǒng)成為城市建設(shè)的關(guān)鍵。智能交通系統(tǒng)（ITS,intelligent traffic system）指對(duì)道路交通狀況實(shí)施監(jiān)測(cè)的系統(tǒng)，該系統(tǒng)借助數(shù)據(jù)挖掘方法獲取道路的擁堵狀態(tài)，然后根據(jù)系統(tǒng)分析的結(jié)果對(duì)機(jī)動(dòng)車實(shí)施有效的調(diào)度[3-4]。事實(shí)上，許多監(jiān)測(cè)手段已經(jīng)應(yīng)用到了智能交通系統(tǒng)，并實(shí)現(xiàn)了對(duì)交通擁堵狀況的判斷。例如，通過道路兩側(cè)安裝靜態(tài)傳感器獲取道路的實(shí)時(shí)數(shù)據(jù)，并將其傳輸?shù)綌?shù)據(jù)中心加以處理與分析，得到反映道路擁堵狀態(tài)的數(shù)值。另外，借助高清攝像頭采集交通圖像數(shù)據(jù)，根據(jù)對(duì)圖像的處理分析結(jié)果做出對(duì)道路擁堵情況的準(zhǔn)確判定[5-7]。然而，靜態(tài)傳感器、高清攝像頭的安裝成本和維護(hù)成本十分高昂，盡管可以有效地實(shí)現(xiàn)交通狀況的監(jiān)控，但不適合大規(guī)模地部署[8]。此外，固定的靜態(tài)傳感器的感知區(qū)域有很大局限性，所獲取的數(shù)據(jù)也過于稀疏，不利于數(shù)據(jù)的處理與分析。隨著傳感器功能的增加，越來越多的機(jī)動(dòng)車安裝了智能車載傳感器設(shè)備[9]。研究學(xué)者利用車載傳感器不斷地收集機(jī)動(dòng)車交通數(shù)據(jù)（如實(shí)時(shí)位置、行駛速度、方向、數(shù)據(jù)上報(bào)時(shí)間等信息），實(shí)現(xiàn)低成本、高精度的交通監(jiān)測(cè)。此外，機(jī)動(dòng)車數(shù)量龐大且行駛具有隨機(jī)性，能夠有效解決交通數(shù)據(jù)過于稀疏的問題[10]。然而，利用機(jī)動(dòng)車交通數(shù)據(jù)實(shí)現(xiàn)道路狀態(tài)監(jiān)測(cè)，忽略了因數(shù)據(jù)泄露引發(fā)的一系列危害。由于交通數(shù)據(jù)包含諸多敏感信息，攻擊者很容易通過數(shù)據(jù)提供者的歷史數(shù)據(jù)推斷出未來某個(gè)時(shí)間段數(shù)據(jù)提供者所處的位置，甚至還可以通過頻繁出入的地方推測(cè)出數(shù)據(jù)提供者的個(gè)人信息，諸如興趣愛好、健康狀況、收入等敏感信息[11-12]。研究學(xué)者提出利用傳統(tǒng)的加密算法對(duì)交通數(shù)據(jù)進(jìn)行加密，以確保數(shù)據(jù)傳輸及存儲(chǔ)過程中的安全性。處理中心在密態(tài)數(shù)據(jù)的基礎(chǔ)上實(shí)現(xiàn)交通狀態(tài)的監(jiān)測(cè)。借助傳統(tǒng)的加密算法盡管能夠滿足數(shù)據(jù)提供者對(duì)數(shù)據(jù)安全性的要求（如高級(jí)加密標(biāo)準(zhǔn)（AES,advanced encryption standard）[13-14]等），但傳統(tǒng)的加密算法存在明顯的弊端，即無法對(duì)密態(tài)數(shù)據(jù)直接進(jìn)行處理與分析。為達(dá)到監(jiān)測(cè)的目的，需要先對(duì)密文進(jìn)行解密，這不但將明文數(shù)據(jù)暴露給了數(shù)據(jù)處理中心，而且還延長(zhǎng)了交通監(jiān)測(cè)所需的時(shí)間。Paillier 算法盡管可以避免加密數(shù)據(jù)的解密過程，但其完成數(shù)據(jù)處理與分析的過程非常耗時(shí)，違背了交通監(jiān)測(cè)對(duì)時(shí)延的要求。更重要的是，借助加密算法能夠保證在交通數(shù)據(jù)中的敏感信息不被泄露的同時(shí)，更需要實(shí)現(xiàn)機(jī)動(dòng)車駕駛員對(duì)交通狀態(tài)的安全查詢，因此，實(shí)現(xiàn)對(duì)加密數(shù)據(jù)的查詢功能是完成智能交通隱私保護(hù)的關(guān)鍵[15]。其不僅需要滿足任意時(shí)刻機(jī)動(dòng)車駕駛員對(duì)智能交通系統(tǒng)分析出的某一具體道路交通擁堵狀態(tài)結(jié)果的查詢，而且能夠保證查詢值的正確性及反饋結(jié)果的唯一性。通過對(duì)加密數(shù)據(jù)的查詢，能夠保證在整個(gè)智能交通系統(tǒng)的實(shí)現(xiàn)過程，機(jī)動(dòng)車所產(chǎn)生的交通數(shù)據(jù)始終受到保護(hù)而不被泄露。因此，在保證交通數(shù)據(jù)隱私安全的前提下，既能快速地挖掘出數(shù)據(jù)的內(nèi)在信息、又能安全且準(zhǔn)確地實(shí)現(xiàn)駕駛員對(duì)交通道路擁堵狀態(tài)結(jié)果的查詢是研究隱私保護(hù)智能交通系統(tǒng)的核心難題。

安全多方計(jì)算（MPC,secure multiparty computation）為隱私保護(hù)智能交通道路監(jiān)測(cè)的實(shí)現(xiàn)提供了可行的方案[16-18]，該方案在確保數(shù)據(jù)安全的前提下，完成對(duì)明文數(shù)據(jù)的處理、分析與查詢。但是，如何設(shè)計(jì)適用于處理與分析機(jī)動(dòng)車交通數(shù)據(jù)的安全計(jì)算協(xié)議，降低處理數(shù)據(jù)耗費(fèi)的時(shí)間仍是實(shí)現(xiàn)交通監(jiān)測(cè)所面臨的難題。

針對(duì)上述問題，本文對(duì)傳統(tǒng)K 最近鄰（KNN,K-nearest neighbor）距離算法進(jìn)行改進(jìn)，提出了一種基于智能交通的隱私保護(hù)道路狀態(tài)實(shí)時(shí)監(jiān)測(cè)（PPIM,privacy preserving intelligent monitoring）算法。借助基礎(chǔ)安全計(jì)算協(xié)議，并設(shè)計(jì)了一系列的安全計(jì)算協(xié)議，在保證數(shù)據(jù)隱私安全的前提下，完成了交通數(shù)據(jù)的處理與分析，通過部分已知道路的擁堵狀態(tài)，達(dá)到對(duì)整個(gè)路網(wǎng)中其余未知道路擁堵狀態(tài)的監(jiān)測(cè)。此外，還提出一種改進(jìn)型KNN 算法，通過引入皮爾遜相關(guān)系數(shù)，得到已知道路與未知道路之間擁堵狀態(tài)的權(quán)重系數(shù)，提高了對(duì)道路擁堵狀況監(jiān)測(cè)的準(zhǔn)確度。

2 預(yù)備知識(shí)

2.1 路網(wǎng)的拓?fù)浣Y(jié)構(gòu)與擁堵狀態(tài)

交通路網(wǎng)（簡(jiǎn)稱“路網(wǎng)”）指供機(jī)動(dòng)車行駛的龐大道路，其最基礎(chǔ)的結(jié)構(gòu)是路段與路口，如圖1所示。通常，路網(wǎng)的拓?fù)浣Y(jié)構(gòu)用圖G(L,C,V)表示，其中，L表示路網(wǎng)中的道路；C表示道路L的中間位置；V表示道路L某一時(shí)間間隔內(nèi)道路的平均速度，即此時(shí)道路允許的機(jī)動(dòng)車通行能力。假設(shè)圖G(L,C,V)包含n條道路，定義i∈[1,n]（i表示路網(wǎng)中道路的編號(hào)）。倘若道路i在時(shí)間間隔T內(nèi)采集了m輛機(jī)動(dòng)車的數(shù)據(jù)，并且上報(bào)k條的數(shù)據(jù)，vτ（τ∈[1,k]）表示每條數(shù)據(jù)中車輛的瞬時(shí)速度，單位為km/h?；谏鲜龆x，可以計(jì)算出道路i在時(shí)間間隔T內(nèi)的平均速度。結(jié)合真實(shí)的駕車體驗(yàn)，道路的擁堵狀態(tài)可分為4 種不同程度。1) 當(dāng)?shù)缆返钠骄俣仍?＜vi≤ 10范圍時(shí)，表示該道路處于十分擁堵的狀態(tài)；2) 當(dāng)10＜vi≤ 30時(shí)，表示該道路處于較擁堵的狀態(tài)；3) 當(dāng)30＜vi≤ 45時(shí)，表示明機(jī)動(dòng)車可以在該道路上暢通地行駛；4) 當(dāng)vi＞ 45時(shí)，表示該道路此時(shí)的通行狀態(tài)十分暢通。

圖1 路網(wǎng)的拓?fù)浣Y(jié)構(gòu)

2.2 傳統(tǒng)的KNN 算法監(jiān)測(cè)框架

KNN 算法常被用于監(jiān)測(cè)道路交通的擁堵狀態(tài)。若vτ(T)表示時(shí)間間隔T內(nèi)道路τ待求解的預(yù)測(cè)值，v(T)表示時(shí)間間隔T預(yù)測(cè)vτ(T)所對(duì)應(yīng)的特征向量。對(duì)于特征向量v(T)，KNN 算法在歷史數(shù)據(jù)集中搜索與其距離最近的K個(gè)歷史特征xi,xi+1,…,xi+K，利用式(1)將K個(gè)特征向量通過加權(quán)估計(jì)的方法，求解vτ(T)的值。

由式(1)可知，KNN 算法中的唯一參數(shù)是確定K，其值直接關(guān)系到判斷未知道路擁堵情況的準(zhǔn)確性。通常采用交叉驗(yàn)證法確定最優(yōu)K值，具體步驟如下。

步驟1定義選取K的最大值Kmax和最小值Kmin。根據(jù)路網(wǎng)中道路總數(shù)可知Kmax=n,Kmin=1。

步驟2將n條道路的歷史數(shù)據(jù)以時(shí)間間隔T為單位計(jì)算n條道路的n個(gè)特征值，得到道路歷史數(shù)據(jù)集的集合{v1,v2,…,vn}，然后依次將數(shù)據(jù)集{v1,v2,…,vn}作為測(cè)試數(shù)據(jù)集，其他n-1個(gè)數(shù)據(jù)集作為歷史數(shù)據(jù)集。

步驟3將K從Kmin以步長(zhǎng)為1 進(jìn)行取值，直至取到Kmax后結(jié)束。

步驟4優(yōu)化二范式，使待求解道路τ的預(yù)測(cè)值vτ(T)與真實(shí)值相差最小。

步驟5計(jì)算n個(gè)數(shù)據(jù)集對(duì)應(yīng)選取K值的平均誤差百分比，并對(duì)n個(gè)值求均值，即其中，num(i,K)表示計(jì)算道路i時(shí)K的具體數(shù)值。

本文基于KNN 算法實(shí)現(xiàn)交通狀態(tài)的實(shí)時(shí)監(jiān)測(cè)，主要是因?yàn)槠涓軡M足交通監(jiān)測(cè)對(duì)時(shí)延的要求。首先，相比于其他數(shù)據(jù)預(yù)測(cè)算法，KNN 算法不僅具有簡(jiǎn)單易用的特點(diǎn)，而且能達(dá)到較好的預(yù)測(cè)效果；其次，KNN 算法模型的訓(xùn)練時(shí)間快，其模型訓(xùn)練主要是確定K的取值，對(duì)于特定的某個(gè)區(qū)域，一旦K值被確定，在相當(dāng)長(zhǎng)的時(shí)間內(nèi)可以對(duì)未知數(shù)據(jù)進(jìn)行預(yù)測(cè)；最后，KNN 算法對(duì)異常值不敏感，換而言之，交通數(shù)據(jù)內(nèi)經(jīng)常出現(xiàn)的異常值對(duì)KNN 算法的預(yù)測(cè)精度不會(huì)造成很大的影響。

2.3 安全兩方計(jì)算

安全兩方計(jì)算是指雙方在互不泄露各自數(shù)據(jù)的前提下完成數(shù)據(jù)的處理與分析。假設(shè)2 個(gè)獨(dú)立的參與實(shí)體Alice 和Bob，兩者分別存儲(chǔ)各自的私有數(shù)據(jù)，Alice 的私有數(shù)據(jù)是隨機(jī)數(shù)a，Bob 的私有數(shù)據(jù)是隨機(jī)數(shù)b。安全兩方計(jì)算的目的是獲取a×b的結(jié)果，但是Alice 和Bob 都不想泄露其私有信息的數(shù)值。安全兩方計(jì)算過程如下。首先定義函數(shù)Γ是期望實(shí)現(xiàn)的乘法計(jì)算，經(jīng)過執(zhí)行z-1 次函數(shù)Γ得到最終結(jié)果Sz，即存在。然后Sz被隨機(jī)分成az和bz，并滿足Sz=az+bz的關(guān)系。最后Alice 獲取az的值，Bob 接收bz的值。具體過程如圖2 所示。

圖2 安全兩方計(jì)算過程

通過安全兩方計(jì)算來維護(hù)交通數(shù)據(jù)的隱私安全，在不泄露數(shù)據(jù)敏感信息的前提下，實(shí)現(xiàn)對(duì)數(shù)據(jù)的安全處理。安全兩方計(jì)算能夠加快處理數(shù)據(jù)的速度，降低獲取城市路網(wǎng)道路交通狀態(tài)的時(shí)延，達(dá)到道路實(shí)時(shí)監(jiān)測(cè)的目的。

2.4 基礎(chǔ)安全計(jì)算協(xié)議

本文根據(jù)已有研究成果及基礎(chǔ)安全計(jì)算協(xié)議，來實(shí)現(xiàn)所提PPIM 算法?；A(chǔ)安全計(jì)算協(xié)議基于2 個(gè)云服務(wù)器SP1和SP2，通過兩者之間的安全交互數(shù)據(jù)來完成計(jì)算，具體如下。

基礎(chǔ)安全乘法協(xié)議（BSMP,basic secure multiplication protocol）。假設(shè)云服務(wù)器SP1和SP2分別存儲(chǔ)私有數(shù)據(jù)a和b，將滿足ka+kb=ra rb條件所生成的4 個(gè)隨機(jī)數(shù)ka、kb、ra和rb作為密鑰。SP1計(jì)算a′=a+ra，SP2計(jì)算b′=b+rb，并將a′和b′進(jìn)行互換。然后，SP2產(chǎn)生隨機(jī)數(shù)vb并計(jì)算t=a′b+kb-vb，SP1計(jì)算va=t+ka-ra b′。經(jīng)上述過程即可實(shí)現(xiàn)va+vb=ab的計(jì)算，并將va和vb替代SP1和SP2原有的數(shù)據(jù)a和b。因此，基礎(chǔ)安全乘法協(xié)議可表示為映射va+vb←BSMP(a：b)。

基礎(chǔ)安全除法協(xié)議（BSDP,basic secure division protocol）。SP1和SP2分別存儲(chǔ)私有數(shù)據(jù)a和b，將滿足ka+kb=ra rb條件所生成的4 個(gè)隨機(jī)數(shù)ka、kb、ra和rb作為密鑰。SP1計(jì)算a′=a+ra，SP2計(jì)算，并將a′和b′進(jìn)行互換。然后，SP2產(chǎn)生隨機(jī)數(shù)vb并計(jì)算，SP1計(jì)算。經(jīng)上述過程即可實(shí)現(xiàn)的計(jì)算，并將va和vb替代SP1和SP2原有的數(shù)據(jù)a和b。因此，基礎(chǔ)安全除法協(xié)議可表示為映射，其中，va和vb分別表示原始數(shù)據(jù)a和b的密文值。

3 交通監(jiān)測(cè)方案

為實(shí)現(xiàn)智能交通隱私保護(hù)道路狀態(tài)的監(jiān)測(cè)，本節(jié)給出了系統(tǒng)監(jiān)測(cè)的模型，并對(duì)模型內(nèi)實(shí)體的功能逐一介紹；結(jié)合系統(tǒng)模型，闡明系統(tǒng)存在的安全威脅；為防止數(shù)據(jù)泄露帶來的危險(xiǎn)，設(shè)計(jì)了適于隱私保護(hù)改進(jìn)型 KNN（IKNN,improved KNN）算法的高效安全計(jì)算協(xié)議。

3.1 系統(tǒng)模型

道路狀態(tài)監(jiān)測(cè)的系統(tǒng)模型如圖3 所示，該模型包含4 個(gè)實(shí)體的參與，具體如下。

可信任實(shí)體（TA,trusted authority）。一個(gè)獨(dú)立可信任的第三方，它的主要任務(wù)是生成隨機(jī)數(shù)并將隨機(jī)數(shù)通過安全信道發(fā)送給其他參與方。

數(shù)據(jù)提供車輛（VD,vehicle data）。負(fù)責(zé)機(jī)動(dòng)車交通數(shù)據(jù)的收集，并將收集的數(shù)據(jù)實(shí)時(shí)地傳輸?shù)皆品?wù)器，即云服務(wù)提供商。

云服務(wù)提供商（SP,server provider）。接收來自數(shù)據(jù)提供車輛發(fā)送的數(shù)據(jù)并對(duì)其存儲(chǔ)和處理與分析。

導(dǎo)航提供商（NAV,navigation）。負(fù)責(zé)接收2 個(gè)云服務(wù)提供商計(jì)算出的結(jié)果，并將其發(fā)布給行駛在道路上的機(jī)動(dòng)車，用于提升司機(jī)的駕駛體驗(yàn)。

圖3 系統(tǒng)模型

3.2 安全威脅

安全威脅主要來自惡意攻擊者對(duì)提供數(shù)據(jù)存儲(chǔ)服務(wù)的第三方云服務(wù)提供商進(jìn)行的惡意攻擊，該攻擊容易造成數(shù)據(jù)提供者信息的泄露。假設(shè)存在一個(gè)模擬器?，其任意地產(chǎn)生隨機(jī)值并獲取安全計(jì)算協(xié)議真實(shí)的視圖H1。基于H1，模擬器?試圖在多項(xiàng)式的時(shí)間內(nèi)生成一個(gè)模擬的視圖H2。假設(shè)存在2 個(gè)不共謀的惡意攻擊者 A1和A2。攻擊者 A1可以成功地攻擊并獲取存儲(chǔ)在服務(wù)器SP1內(nèi)的交通數(shù)據(jù)，一次成功的攻擊意味著A1可以找到一個(gè)概率二項(xiàng)式算法成功地區(qū)分H1和H2，并結(jié)合獲取的數(shù)據(jù)推測(cè)出真實(shí)的數(shù)據(jù)值。攻擊者A2也可以成功地攻擊并獲取存儲(chǔ)在服務(wù)器SP2中數(shù)據(jù)，A2完成一次成功的攻擊同樣意味著其可以找到一個(gè)概率二項(xiàng)式算法對(duì)H1和H2進(jìn)行區(qū)分，結(jié)合獲取的數(shù)據(jù)推測(cè)出其真實(shí)值。此外，云服務(wù)提供商是好奇并誠(chéng)實(shí)的實(shí)體，在執(zhí)行數(shù)據(jù)處理時(shí)會(huì)利用已知的部分?jǐn)?shù)據(jù)來猜測(cè)真實(shí)的數(shù)據(jù)值。

3.3 設(shè)計(jì)目標(biāo)

本文主要目的是實(shí)現(xiàn)對(duì)智能交通隱私保護(hù)道路交通狀態(tài)的監(jiān)測(cè)，因此，系統(tǒng)既要滿足實(shí)現(xiàn)交通監(jiān)測(cè)的目標(biāo)，又要符合數(shù)據(jù)隱私保護(hù)的要求，具體要求如下。

數(shù)據(jù)的安全性。任何收集的機(jī)動(dòng)車行駛數(shù)據(jù)都應(yīng)該受到保護(hù)，比如車輛ID、車輛行駛的速度、車輛的經(jīng)緯度等信息。

數(shù)據(jù)計(jì)算的低復(fù)雜性。用于數(shù)據(jù)加密的加密算法應(yīng)當(dāng)是輕量級(jí)的、快速的。

數(shù)據(jù)的輕量化傳輸。為了降低交通監(jiān)測(cè)的時(shí)延，應(yīng)盡可能地減少交通數(shù)據(jù)的傳輸量。

預(yù)測(cè)的實(shí)時(shí)性。為滿足道路交通監(jiān)測(cè)的實(shí)時(shí)性，利用少量的數(shù)據(jù)實(shí)現(xiàn)對(duì)整個(gè)路網(wǎng)道路狀況的快速監(jiān)測(cè)。

3.4 IKNN 監(jiān)測(cè)算法

為提高傳統(tǒng)KNN 算法的監(jiān)測(cè)精度，本文提出了IKNN 算法，其主要思想是利用已知道路的部分平均速度對(duì)未知道路的平均速度進(jìn)行預(yù)測(cè)。通過增加權(quán)重調(diào)節(jié)因子ω，借助機(jī)動(dòng)車的歷史數(shù)據(jù)，整合距離預(yù)測(cè)道路最近的K條道路與其之間的相似度值，調(diào)節(jié)不同道路在預(yù)測(cè)未知道路時(shí)的影響程度。對(duì)于權(quán)重調(diào)節(jié)因子ω的計(jì)算，本文首先采用歸一化的歐幾里得公式將獲取的路段速度值歸一化到0～1。然后利用式(2)所示的皮爾遜相關(guān)系數(shù)進(jìn)行計(jì)算，獲取所需的權(quán)重值。

其中，x表示待求解道路的歷史平均速度的向量，y表示距離其最近的K條道路中某一條路段的歷史平均速度向量。由皮爾遜相關(guān)系數(shù)的性質(zhì)可知，ω值越大，說明向量x和y兩者之間的相似度越大，反之亦然。基于ω給出IKNN 交通監(jiān)測(cè)計(jì)算式，如式(3)所示。

ω的引入更加凸顯出已知道路中每一條道路對(duì)未知路段具有不同程度的影響。根據(jù)選取的已知道路與待求解道路歷史數(shù)據(jù)之間的皮爾遜相關(guān)系數(shù)，降低預(yù)測(cè)值與真實(shí)值之間的誤差。

由式(3)可知，IKNN 算法的前提是確定K值及計(jì)算ω，具體如下。

步驟1利用收集的整個(gè)路網(wǎng)的歷史數(shù)據(jù)，根據(jù)式(1)計(jì)算出時(shí)間間隔T內(nèi)每一條道路的平均速度及經(jīng)緯度信息。采用道路中間位置的經(jīng)緯度Ci(x,y)表示道路i的空間地理信息。Ci(x,y)利用兩點(diǎn)之間的中點(diǎn)求解公式進(jìn)行求解，其中(x1,y1)表示道路i最靠近路口一端的經(jīng)緯度信息，(x2,y2)表示道路i最遠(yuǎn)離該路口另一端的經(jīng)緯度位置信息。

步驟2通過訓(xùn)練歷史的交通數(shù)據(jù)，確定用于估計(jì)未知道路平均速度時(shí)的K值。

步驟3依次計(jì)算選取的K條道路與其余n-K條道路之間的權(quán)重向量Θ=(ω1,ω2,…,ωn-K)。

步驟4根據(jù)步驟3 得到的K值和式(3)計(jì)算出未知道路時(shí)間間隔T內(nèi)待求解道路的平均速度vτ(T)。

4 隱私保護(hù)道路監(jiān)測(cè)

本節(jié)闡述了智能交通隱私保護(hù)道路監(jiān)測(cè)的實(shí)現(xiàn)過程。為說明算法執(zhí)行的具體步驟，首先定義了機(jī)動(dòng)車交通數(shù)據(jù)的數(shù)據(jù)格式及數(shù)據(jù)到云服務(wù)提供商的上傳格式。然后闡述云服務(wù)提供商在保護(hù)數(shù)據(jù)隱私安全的基礎(chǔ)上，采用IKNN 算法，實(shí)現(xiàn)道路交通狀態(tài)的監(jiān)測(cè)。

4.1 數(shù)據(jù)格式和數(shù)據(jù)傳輸

實(shí)現(xiàn)監(jiān)測(cè)的關(guān)鍵是收集必要的數(shù)據(jù)。定義R(lat,lon,v,t)表示數(shù)據(jù)的上傳格式，時(shí)間間隔T內(nèi)道路i上行駛的車輛共上報(bào)k條數(shù)據(jù)，Dτ={(latτ,lonτ,vτ,tτ)|τ∈[1,k]}表示數(shù)據(jù)的集合。然后，將每一條數(shù)據(jù)內(nèi)的每一個(gè)元素隨機(jī)地分為兩部分，即其中，。最后，每個(gè)元素被隨機(jī)地分為2 個(gè)分量分別傳輸給云服務(wù)提供商SP1和SP2，即作為一個(gè)整體發(fā)送給SP1，傳輸給SP2。

4.2 經(jīng)緯度距離安全計(jì)算協(xié)議

將數(shù)據(jù)安全地外包給云服務(wù)提供商后，云服務(wù)提供商利用存儲(chǔ)的數(shù)據(jù)計(jì)算相應(yīng)道路的平均速度。對(duì)于道路i，SP1根據(jù)存儲(chǔ)的速度數(shù)據(jù)分量，對(duì)集合計(jì)算SP2計(jì)算。根據(jù)機(jī)動(dòng)車的歷史經(jīng)緯度計(jì)算能夠體現(xiàn)道路空間位置的信息。路段i的GPS 緯度信息的集合lati={lat(i,τ)|τ∈[1,k]}存儲(chǔ)在SP1，經(jīng)度信息集合loni={lon(i,τ)|τ∈[1,k]}存儲(chǔ)在SP2。根據(jù)3.4 節(jié)中步驟1 所述，近似地計(jì)算出道路i的空間經(jīng)緯度位置信息Ci(latC,lonC)。為計(jì)算空間兩點(diǎn)經(jīng)緯度之間的距離，本文將兩點(diǎn)間距離計(jì)算方法推廣到求解空間兩點(diǎn)間經(jīng)緯度的歐氏距離，如式(4)所示。

其中，R表示地球的半徑，p表示兩點(diǎn)之間經(jīng)度差的余弦值，li=cos(lati)，lτ=cos(latτ)，bi=sin(lati)，bτ=sin(latτ)，p(i,τ)=cos(loni-lonτ)。根據(jù)式(4)計(jì)算基于密文狀態(tài)下2 個(gè)不同經(jīng)緯度之間距離，具體如下。

步驟1SP1執(zhí)行l(wèi)=lilτ=cos(lati)cos(latτ)和b=bibτ=sin(lati)sin(latτ)的計(jì)算。

步驟2SP2對(duì)兩點(diǎn)之間經(jīng)度進(jìn)行差值運(yùn)算，即p(i,τ)=cos(loni-lonτ)。

步驟3根據(jù)泰勒公式的展開近似等式，即以及二項(xiàng)式展開，計(jì)算對(duì)應(yīng)數(shù)值反余弦的近似值。當(dāng)f∈[9,7,5,3]、（f和ρ每次選取的元素位置相同）時(shí)，根據(jù)每次選取的f和ρ值，執(zhí)行BSMP，結(jié)合f和ρ的取值范圍，協(xié)議執(zhí)行可以表示為，其中，g∈[1,f]。然后，將計(jì)算得到的va(f,g)發(fā)送給SP1，將獲得的vb(f,g)發(fā)送給SP2。

步驟4SP1計(jì)算，SP2計(jì)算

步驟5SP1執(zhí)行va=+b的計(jì)算，SP2執(zhí)行的計(jì)算。

經(jīng)上述步驟，得到路網(wǎng)中任意2 條道路之間的空間距離d。并且滿足d=va+vb的映射關(guān)系。其中，va存儲(chǔ)在SP1，vb存儲(chǔ)在SP2。

假設(shè)時(shí)間間隔T內(nèi)，智能交通系統(tǒng)共收集到來自h條道路上的機(jī)動(dòng)車的交通數(shù)據(jù)，根據(jù)前文所述的平均速度計(jì)算方法，系統(tǒng)計(jì)算出h條道路的平均速度，組成向量V=[v1,v2,…,vh]。另外，向量V隨機(jī)地被分為兩部分V′和V′，然后分別存儲(chǔ)在SP1和SP2。結(jié)合存儲(chǔ)在云服務(wù)器中n條道路的歷史數(shù)據(jù)，提取出任意2 條道路之間的空間相關(guān)性，得到n條道路的空間相關(guān)性矩陣?，如式(5)所示。

同樣地，空間相關(guān)性矩陣?被隨機(jī)地分為?′和兩部分分量，被依次存儲(chǔ)在SP1和SP2，并且滿足的等式關(guān)系。其中，分別如式(16)和式(17)所示。

4.3 權(quán)重系數(shù)安全計(jì)算協(xié)議

為獲取已知h條道路與未知的n-h條道路之間的權(quán)重系數(shù)，通過已知h條道路的歷史平均速度向量Vi={vi|i∈[1,h]}，完成對(duì)未知道路的歷史平均速度向量Vτ={vτ|τ∈ [h+1,n]}的求解。具體步驟如下。

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

步驟2SP1求解SP2計(jì)算

經(jīng)上述計(jì)算，最終未知道路τ在時(shí)間間隔T內(nèi)道路的平均速度vτ被隨機(jī)地分為，并分別存儲(chǔ)在SP1和SP2中。

通過執(zhí)行設(shè)計(jì)的經(jīng)緯度距離安全計(jì)算（SLD,secure length distance）協(xié)議、權(quán)重系數(shù)安全計(jì)算（SWF,secure weight factor）協(xié)議和道路監(jiān)測(cè)安全計(jì)算（SMS,secure monitoring scheme）協(xié)議這3 個(gè)安全計(jì)算協(xié)議，可以完成智能交通系統(tǒng)隱私保護(hù)道路狀態(tài)實(shí)時(shí)監(jiān)測(cè)的任務(wù)。在IKNN 算法的基礎(chǔ)上，本文首先利用SLD 協(xié)議獲取體現(xiàn)道路之間空間位置的空間相關(guān)性矩陣?；然后根據(jù)SWF 協(xié)議計(jì)算出路網(wǎng)中任意2 條道路之間的ω，并得到權(quán)重向量Θ；最后在獲取的空間相關(guān)性矩陣?和權(quán)重向量Θ的基礎(chǔ)上，依據(jù)式(3)并按照SMS 協(xié)議的執(zhí)行過程即可實(shí)現(xiàn)隱私保護(hù)交通狀態(tài)的實(shí)時(shí)監(jiān)測(cè)?？偠灾?，依次執(zhí)行SLD、SWF 和SMS 這3 個(gè)安全計(jì)算協(xié)議，借助存儲(chǔ)在云服務(wù)器中的交通數(shù)據(jù)即可實(shí)現(xiàn)整個(gè)智能交通監(jiān)測(cè)的算法。因此，基于上述過程，可根據(jù)已知h條路段的平均速度，在保證數(shù)據(jù)隱私安全的前提下，實(shí)現(xiàn)對(duì)其余n-h條未知道路的平均速度的預(yù)測(cè)。然后，將系統(tǒng)最終的處理分析結(jié)果提供給導(dǎo)航提供商。導(dǎo)航提供商將獲取的數(shù)據(jù)直接進(jìn)行相加，獲取時(shí)間間隔T內(nèi)整個(gè)路網(wǎng)所有道路的平均速度，并根據(jù)速度的相加結(jié)果，判斷出道路交通真實(shí)的擁堵情況。最后，將分析出的真實(shí)擁堵狀況實(shí)時(shí)地發(fā)布給機(jī)動(dòng)車駕駛員。

5 安全性分析

5.1 數(shù)據(jù)存儲(chǔ)安全性分析

根據(jù)本文的數(shù)據(jù)傳輸策略，SP1存儲(chǔ)數(shù)據(jù)分量x1，SP2存儲(chǔ)數(shù)據(jù)分量x2。假設(shè)2 個(gè)攻擊者 A1和A2，A1對(duì)SP1發(fā)起攻擊并獲取SP1的內(nèi)部數(shù)據(jù)，A2對(duì)SP2發(fā)起攻擊并獲取SP2的內(nèi)部數(shù)據(jù)。由于云服務(wù)提供商SP1和SP2存儲(chǔ)的數(shù)據(jù)僅僅是原始數(shù)據(jù)的分量，當(dāng)成功攻擊SP1獲取存儲(chǔ)在其中的數(shù)據(jù)x1后，由于x1本身的隨機(jī)性，A1并不能通過數(shù)據(jù)分量x1對(duì)原始數(shù)據(jù)x做出正確的推斷；同樣地，當(dāng)成功攻擊SP2獲取存儲(chǔ)在其中的數(shù)據(jù)x2后，由于x2同樣具備很大的隨機(jī)性，A2也不能由數(shù)據(jù)分量x2對(duì)原始數(shù)據(jù)x做出正確的推斷。

5.2 數(shù)據(jù)計(jì)算安全性分析

假設(shè) A1對(duì)SP1實(shí)施攻擊并能夠獲取其內(nèi)部存儲(chǔ)的數(shù)據(jù)，并攔截云服務(wù)提供商SP1和SP2之間交互運(yùn)算時(shí)所產(chǎn)生的中間值；A2同樣對(duì)SP2進(jìn)行攻擊，并攔截兩服務(wù)器之間數(shù)據(jù)交互計(jì)算所生成的中間值。當(dāng)SP1安全地接收可以作為密鑰的隨機(jī)數(shù)ra時(shí)，在ra的基礎(chǔ)上將獲取的原始數(shù)據(jù)分量x1與之相加，即計(jì)算x3=x1+ra。當(dāng)x3被獲取后，攻擊者 A1很難根據(jù)x3的值推算出x1的值，因此 A1更無法對(duì)完整的原始數(shù)據(jù)x實(shí)現(xiàn)正確地推斷。同理，A2也無法對(duì)執(zhí)行上述操作的數(shù)據(jù)進(jìn)行正確的推斷。當(dāng)云服務(wù)提供商SP1和SP2執(zhí)行安全計(jì)算協(xié)議后得到最終的路段平均速度，該速度又被隨機(jī)地分成了兩部分并分別存儲(chǔ)在SP1和SP2。對(duì)于發(fā)送給導(dǎo)航提供商的最終數(shù)據(jù)也僅僅只是體現(xiàn)道路的擁堵情況，并不能推測(cè)出機(jī)動(dòng)車的原始數(shù)據(jù)。本文所設(shè)計(jì)的SLD 協(xié)議、SWF 協(xié)議和SMS 協(xié)議均依照上述分析的安全交互過程進(jìn)行計(jì)算，因此，本文所提PPIM 算法可以保證數(shù)據(jù)的隱私安全不被泄露，進(jìn)而完成對(duì)數(shù)據(jù)的一系列操作。

6 性能分析及實(shí)驗(yàn)驗(yàn)證

6.1 性能分析

計(jì)算復(fù)雜度。為評(píng)估本文所提PPIM 算法的計(jì)算復(fù)雜度，先對(duì)算法中每個(gè)安全的子協(xié)議進(jìn)行計(jì)算復(fù)雜度分析。假設(shè)TBSMP、TBSDP和TPaillier分別表示BSMP、BSDP 及Paillier 算法執(zhí)行一次所需的時(shí)間，具體數(shù)值通過仿真實(shí)驗(yàn)獲得，如表1 所示。由表1 可知，TBSMP≈TBSDP?TPaillier。對(duì)于SLD協(xié)議，因其需要借助泰勒公式對(duì)反余弦函數(shù)近似求解，完成一次迭代的計(jì)算需要執(zhí)行9 次BSMP，因此，執(zhí)行輸入數(shù)據(jù)大小為n，計(jì)算復(fù)雜度為9O(n)TBSMP。對(duì)于SWF 協(xié)議，系統(tǒng)完成一次完整協(xié)議計(jì)算需要進(jìn)行3 次BSMP 計(jì)算及一次BSDP計(jì)算，執(zhí)行輸入數(shù)據(jù)大小為n，SWF 協(xié)議所需時(shí)間為3O(n)TBSMP+O(n)TBSDP。同樣，對(duì)于完成道路監(jiān)測(cè)協(xié)議SMS 協(xié)議，其執(zhí)行BSMP 的次數(shù)與K的取值有關(guān)，并且完成一次SMS 協(xié)議也需執(zhí)行一次BSDP。對(duì)于執(zhí)行輸入數(shù)據(jù)大小為n，SMS 共需的時(shí)間為3KO(n)TBSMP+O(n)TBSDP。因此，將3 個(gè)過程的計(jì)算復(fù)雜度進(jìn)行相加即可得到PPIM 算法的計(jì)算復(fù)雜度，即(11 +3K)O(n)TBSMP。假設(shè)數(shù)據(jù)的大小仍然為n，采用Paillier 算法完成對(duì)道路狀態(tài)的監(jiān)測(cè)，則需要的時(shí)間復(fù)雜度是nO(n2)TPaillier。通過表2，可以更加清晰地比較SLD 協(xié)議、SWF 協(xié)議、SMS 協(xié)議、PPIM 算法及Paillier 算法之間的計(jì)算復(fù)雜度。

表1 協(xié)議執(zhí)行一次所需時(shí)間

表2 協(xié)議/算法計(jì)算復(fù)雜度

通信開銷。借助對(duì)每個(gè)子協(xié)議的分析，獲取整個(gè)算法執(zhí)行過程中的通信開銷。表3 給出了SLD 協(xié)議、SWF 協(xié)議、SMS 協(xié)議及PPIM 算法各自完成一次計(jì)算所需的數(shù)據(jù)通信輪數(shù)。通過分析基礎(chǔ)協(xié)議BSMP 和BSDP，完成BSMP 或者BSDP 都需要2輪的通信開銷。根據(jù)計(jì)算復(fù)雜度分析，完成一次SLD 協(xié)議需要運(yùn)行6 次BSMP，因此其需要進(jìn)行數(shù)據(jù)交互的輪數(shù)是12；對(duì)于SWF 協(xié)議，其需要運(yùn)行3 次BSMP 和1 次BSDP，所以共需8 輪的數(shù)據(jù)交互；然而，執(zhí)行SMS 協(xié)議同樣與K的取值有關(guān)，需要數(shù)據(jù)交互的輪數(shù)是6K+2。因此，根據(jù)3 個(gè)協(xié)議計(jì)算時(shí)交互的輪數(shù)，得出PPIM 算法需要的通信開銷，即交互22+6K輪。

表3 執(zhí)行協(xié)議/算法通信輪數(shù)

6.2 實(shí)驗(yàn)驗(yàn)證

基于真實(shí)的交通數(shù)據(jù)，本節(jié)通過實(shí)驗(yàn)對(duì)PPIM算法的性能進(jìn)行驗(yàn)證。首先，通過未知數(shù)據(jù)預(yù)測(cè)誤差衡量IKNN 算法的有效性；然后，給出每一個(gè)安全計(jì)算協(xié)議及實(shí)現(xiàn)PPIM 算法運(yùn)行時(shí)間結(jié)果；最后，給出完成PPIM 算法各階段所需通信成本的仿真。為驗(yàn)證隱私保護(hù)下IKNN 算法的有效性，本文用e表示對(duì)道路平均速度預(yù)測(cè)的誤差率[19]，其計(jì)算如式(8)所示。

實(shí)驗(yàn)的仿真數(shù)據(jù)為福州市200輛出租車的相關(guān)數(shù)據(jù)，包含出租車行駛的瞬時(shí)速度、GPS 經(jīng)緯度位置信息、數(shù)據(jù)上報(bào)的時(shí)間及機(jī)動(dòng)車的ID 信息。仿真實(shí)驗(yàn)平臺(tái)是在RAM 為16 GB，CPU 為1.80 GHz 的Intel Core(TM) i7-8550U 的筆記本電腦。本文將K的值設(shè)為4，時(shí)間間隔T設(shè)為5 min[20]。

在保證數(shù)據(jù)隱私安全的前提下，分別采用KNN與IKNN 這2 種算法估計(jì)未知數(shù)據(jù)的誤差，曲線如圖4 所示。從1 000 個(gè)數(shù)據(jù)中，依次隨機(jī)在集合M=[200,300,…,800]選取不同數(shù)量的數(shù)據(jù)Ml（l表示集合M中元素位置的編號(hào)）作為已知數(shù)據(jù)。利用Ml個(gè)已知數(shù)據(jù)，估算其余沒有被選取的1000-Ml個(gè)數(shù)據(jù)。由圖4 可以得出，隨著已知數(shù)據(jù)與數(shù)據(jù)總量比值的增大，無論是KNN 算法還是IKNN 算法，對(duì)未知數(shù)據(jù)估計(jì)的準(zhǔn)確度降低了6%～8%的誤差。更重要的是，本文所提IKNN 算法的曲線一直處于KNN 算法曲線的下方，說明IKNN 算法在實(shí)現(xiàn)道路狀態(tài)監(jiān)測(cè)上具有更好的準(zhǔn)確度。

圖4 2 種算法估計(jì)未知數(shù)據(jù)估計(jì)曲線

本文所提IKNN 算法與貝葉斯（Bayes）算法和支持向量機(jī)（SVM,support vector machine）算法這2 種算法進(jìn)行的交通監(jiān)測(cè)預(yù)測(cè)準(zhǔn)確度比較如圖5 所示。數(shù)據(jù)總量同樣為1 000，選擇200～800 范圍，數(shù)據(jù)步長(zhǎng)為100。需要說明的是，SVM 算法采用的核函數(shù)是高斯核函數(shù)（RBF,radial basis function），正則化參數(shù)δ=5，核函數(shù)參數(shù)ε=0.01。由圖5 可知，IKNN、Bayes 和SVM 這3 種算法的未知數(shù)據(jù)預(yù)測(cè)誤差都隨已知數(shù)據(jù)量的增加出現(xiàn)了不同程度的下降。從曲線變化過程可知，IKNN 算法和SVM 算法的預(yù)測(cè)精度均優(yōu)于Bayes 算法，IKNN 算法與SVM算法曲線盡管有部分相交，但隨著數(shù)據(jù)量的增加，IKNN 算法的準(zhǔn)確性更高。

圖5 3 種算法交通監(jiān)測(cè)預(yù)測(cè)準(zhǔn)確度曲線

SWF、SLD 和SMS 這3 個(gè)協(xié)議在不同的數(shù)據(jù)量下的運(yùn)行時(shí)間如圖6 所示。從圖6 可以看出，每個(gè)協(xié)議在加密不同量的數(shù)據(jù)量時(shí)，其效率都達(dá)到了毫秒級(jí)，并且3 個(gè)協(xié)議之間運(yùn)行時(shí)間存在的差異與6.1 節(jié)的理論分析結(jié)果一致。

圖6 3 個(gè)協(xié)議的運(yùn)行時(shí)間

為說明本文所提PPIM 算法不僅完成了對(duì)道路狀態(tài)的監(jiān)測(cè)，而且具備安全、高效處理數(shù)據(jù)的優(yōu)點(diǎn)，本文所提PPIM 算法與Paillier 算法進(jìn)行了對(duì)比。Paillier 算法是加法同態(tài)加密算法，可以在不泄露數(shù)據(jù)隱私安全的前提下，實(shí)現(xiàn)對(duì)數(shù)據(jù)的安全處理。通過設(shè)置變量N及2 個(gè)大素?cái)?shù)p和q，產(chǎn)生用于保護(hù)數(shù)據(jù)隱私的密鑰，其整個(gè)過程通常分為密鑰生成、加密和解密3 個(gè)階段。

1) 密鑰生成

首先，選取2 個(gè)大素?cái)?shù)p和q，并使其滿足gcd(pq,(p-1)(q-1))=1的要求。

其次，計(jì)算N=pq，λ=lcm(p-1,q-1)，并定義函數(shù)

最后，隨機(jī)選取g且滿足g＜N2，計(jì)算u=((L(gλmodN2))-1mod)N，可生成所需的公鑰(n,g)和私鑰(λ,u)。

2) 加密

對(duì)需要加密的數(shù)據(jù)m（0＜m＜N），并計(jì)算其密文

3) 解密

基于密鑰生成階段的私鑰(λ,u)，計(jì)算出明文m=(L(cλmodN2)u)modN。

需要說明的是，Paillier 算法滿足系統(tǒng)加密的2個(gè)消息相乘的結(jié)果解密后恰好是2 個(gè)消息明文狀態(tài)相加的結(jié)果，這種方式與本文數(shù)據(jù)傳輸與處理策略相同。因此，將本文所提PPIM 算法與Paillier 算法進(jìn)行對(duì)比，得到圖7 所示的仿真結(jié)果。需要說明的是，采用Paillier 算法時(shí)，設(shè)置變量N=2 048，并且生成2 個(gè)1 024 位的大素?cái)?shù)p和q。由圖7 可知，本文所提PPIM 算法比Paillier 算法具備更加快速地實(shí)現(xiàn)對(duì)道路狀態(tài)監(jiān)測(cè)的功能，更好地滿足智能交通系統(tǒng)對(duì)低時(shí)延的要求。

圖7 2 種算法的交通監(jiān)測(cè)實(shí)現(xiàn)效率對(duì)比

本文用于衡量通信開銷的單位是bit，其測(cè)量依據(jù)是基于IEEE 754 標(biāo)準(zhǔn)[21]。由該標(biāo)準(zhǔn)可知，任何以單精度浮點(diǎn)形式存儲(chǔ)的值都需要32 bit，雙精度浮點(diǎn)則需要64 bit，而真實(shí)的交通數(shù)據(jù)屬于單精度浮點(diǎn)。各協(xié)議和算法所對(duì)應(yīng)的通信量如圖8 所示。由圖8 可知，實(shí)現(xiàn)整個(gè)PPIM 算法，即使數(shù)據(jù)大小為1 000 時(shí)，其數(shù)據(jù)的通信量還不足0.2 MB，現(xiàn)有的網(wǎng)絡(luò)帶寬很容易滿足其要求。

圖8 協(xié)議/算法的數(shù)據(jù)通信量

7 結(jié)束語

本文實(shí)現(xiàn)了機(jī)動(dòng)車交通數(shù)據(jù)隱私保護(hù)的道路交通監(jiān)測(cè)。為了優(yōu)化KNN 算法，提出了IKNN 算法，通過引入道路之間的相似程度，對(duì)預(yù)測(cè)值進(jìn)行有目的的調(diào)整，提高了交通監(jiān)測(cè)的精度。為了提升數(shù)據(jù)處理的效率，還設(shè)計(jì)了適用于IKNN 算法的安全計(jì)算協(xié)議。最后，通過真實(shí)數(shù)據(jù)的仿真實(shí)驗(yàn)證明，所提算法不但有效地實(shí)現(xiàn)了隱私保護(hù)下的智能交通道路監(jiān)測(cè)，而且滿足交通監(jiān)測(cè)對(duì)實(shí)時(shí)性的需求。