一種基于投票的VANET位置驗證方法

陳佳威

（同濟大學 電子與信息工程學院，上海 201804）

0 引言

VANET中很多與安全相關的應用都依賴于正確的車輛位置信息。但 VANET中的攻擊者通過位置欺騙，達到利己的目的。位置欺騙嚴重威脅到車輛的行駛安全，為有效地解決位置欺騙問題，研究人員提出了利用位置驗證來解決位置欺騙。

位置驗證時通常利用安全定位來確定位置驗證目標節點的位置，再與所聲稱的位置進行比較。位置驗證的一般方法包括[3]：多點定位驗證，三角測量法，自主位置驗證等。

VANET中車輛間有較高的相對速度，網絡拓撲結構變化快，路徑壽命短。這使得傳感器網絡的定位方式（如抗攻擊的位置估計、信標套件技術等[2]）不適合VANET，為驗證車輛的位置帶來了一定的挑戰。但 VANET不受電源和計算能力的限制，具有相當的計算和儲存能力。這些有利條件為設計出新的VANET位置驗證方法提供了基礎。

基于MMSE的位置驗證方法[4]是通過最小均方誤差推得一個良性鄰居集，此良性鄰居集的大小應大于目標車輛的直接鄰居數量的一半。若推不出這樣的良性鄰居集，則說明目標車輛實施了位置欺騙。

為更高效準確地檢測出位置欺騙，本文引入投票機制，通過協作式的投票，來更好解決 VANET中位置驗證，進一步提高位置檢測的正確性。其基本思想是將連續時間轉化成一個個靜態幀，在每個靜態幀上，主檢測者啟動多輪投票過程。該過程為主檢測者審核投票者的投票資格、劃分目標區域為網格，接著與審核通過的從檢測者對網格進行投票，最后選出票數最多的網格（組）。在此基礎上，用閾值判定驗證被檢測者是否實施了位置欺騙。

1 基于投票的VANET位置驗證

1.1 系統模型及假設

本文定義了VANET中的3種車輛類別：主檢測者(MT, Major Tester)、被檢測者(PT, Passive Tester)和從檢測者(FT, Followed Tester)，如圖1所示。假設數據包在通信過程中，均須安全認證，確保惡意車輛在一定時間內無法偽裝成多個車輛來進行位置欺騙。

MT：收到一跳鄰居的數據包并對該數據包的源節點發起位置驗證過程的車輛。

PT：每輛行駛的車輛周期性的廣播一個數據包。通常車輛發出一個數據包后，被檢測者的位置受到鄰居車輛的位置驗證。

FT：被檢測者一跳通信范圍內的所有鄰居為從檢測者，為主檢測者提供關于被檢測者的位置信息的真實性。

圖1給出了這3種車輛類別的關系圖。由圖1知，MT和PT是鄰居關系，是MT和PT的共同鄰居。

圖1 主檢測者、被檢測者及從檢測者關系圖

VANET中車輛間的通信是通過數據包的發送和接收來完成的。數據包的格式如圖2所示。其中，記錄表是發送上一個數據包到發下一個數據包這段時間間隔內收到的所有直接鄰居數據包的記錄，每條記錄包含所收到的數據包的身份標識碼，該身份標識碼車輛的位置、速率、時戳，收到該身份標識碼時自己的位置、速率、所測得的該數據包所附信號的功率（RSS值）。

圖2 數據包的格式

為實現投票，本文定義了投票的三個主要要素：目標區域、網格和投票圓環。目標區域：PT的實際位置的所有可能范圍。網格：PT的實際位置的可能范圍的一小部分。投票圓環：投票者認為PT的實際位置的可能范圍。圖3給出了目標區域、網格及投票圓環的關系圖。由圖可知，目標區域劃分為網格，投票圓環是目標區域的一部分，它與多個網格有重疊部分。

為驗證車輛位置，本文進一步假設：

1）每輛車都裝有以下設備：全球定位系統(GPS)接收器，可為位置信息提供二維平面的坐標；無線收發設備，發射數據包時使用相同的全向發射功率。

2）大多數的車輛是位置可信的，僅有部分會實施位置欺騙，即：若一個車輛周圍有n輛車，良性車輛的數目至少為( 2)/2n+[5]。

圖3 目標區域、網格及投票圓環關系

1.2 問題描述與設計目標

假設在高速公路場景下，通過對車輛進行位置驗證，檢測出位置欺騙的車輛。給定一個區域，該區域中車輛集合為。顯然，是VI的子集，即FT?VI。FT可為空集，可以是一個元素的集合也可以是多個元素的集合。

本位置驗證方案擬實現以下目標：

1）假設PT的聲稱位置為 P T(x,y)，實際位置為 P T′(x′,y′)，若不滿足PT? P T′，MT能檢測出PT實施了位置欺騙。

2）位置驗證方法的正確率為 acR，漏警率為 fnR ，虛警率為 fpR 。在車輛總數和惡意車輛數目相同的高速公路場景下，達到

1.3 位置驗證方案

1.3.1 位置驗證流程

本位置驗證方案采用兩步驟來檢測車輛是否實施了位置欺騙：

1）MT單獨對 PT進行一個初步的真實性檢測[7]：若PT所聲稱的位置不在MT的投票圓環內，則可直接確定PT存在位置欺騙，位置驗證結束，否則進入下一個步驟。

2）MT聯合從檢測者FT對PT進行一個深入的位置驗證：MT收集來自從檢測者的數據包，從中提取出PT觸發的靜態幀，再用基于投票的位置驗證算法判斷PT的位置是否屬實。

圖4 位置驗證流程

1.3.2 投票圓環

投票圓環是投票者通過接收到被檢測者的數據包，接著利用 RSS測距技術計算得出。本文采用Rappaport的大尺度無線信號傳播模型[6]來計算 T-R距離，忽略VANET中的小尺度衰落[1]。

將車輛A和車輛B之間的距離表示為 (,)DAB，其中A為數據包發送者，B為數據包接收者。因為測量誤差的存在，使得 (,)DAB的值落在一個最小值和最大值的范圍內。如圖3所示，即B能將 A的位置限定在以自己為圓心，(A,B)和A ,B )為內外半徑的圓環內，將此圓環稱為 B的投票圓環。

1.3.3 基于投票的位置驗證算法

為解決動態變化網絡中，車輛在運動時仍能完成投票的問題，本文采用了文獻[5]提出的時間切片的概念，把連續時間轉化為一系列時間間隔極小的靜態幀。當某個PT在 1t時刻發送數據包給其鄰居節點時，觸發了 1t時刻的一個靜態幀。當在t′時刻MT收集到 1t時刻的所有FT的信息后，就啟動對PT的投票位置驗證算法。如圖5所示，假設這些車輛發送數據包的先后順序為MT。MT等1到2個周期（數據包發送周期為0.3～1 s），直到收集到一定數量的關于PT在時刻 1t靜態幀中的信息（如圖中的t′或t′），然后再利用基于投票的位置驗證方法做后續處理。

圖5 通信過程

每個PT觸發的靜態幀上，MT首先識別出一個包含所有車輛（MT、PT和所有FT）聲稱位置的最小矩形，之后基于每個聲稱位置用bR來擴展這個矩形， bR為數據包的最大傳播范圍（根據專用短程通信技術標準， bR為 300米）。這個被擴展的矩形與實際道路的重疊部分就構成 MT的目標區域。MT把目標區域分割成M個網格，網格的邊長為L，如圖6所示。每個網格有一個票數狀態變量，初始值為零。

藥物、飲食、各種疾病狀態均可改變華法林的藥代動力學。藥化表明，S-華法林異構體比R-華法林異構體的抗凝效率高5倍，因此干擾S-華法林異構體代謝的因素更為重要。維生素K攝入量是影響華法林抗凝治療效果的關鍵要素。很多日常飲食及營養保健品也會影響華法林的抗凝作用。當患者口服華法林進行抗凝治療時，應盡量保持飲食結構的均衡，不要盲目服用過多的營養保健品，并定期監測PT和INR。

首輪投票開始前，MT須對每個FT的投票資格進行審核。MT收集到PT觸發的靜態幀上所有FT的數據包后，提取時刻 t2FT的位置 ( x 2 ,y 2 )、速率 v 2及記錄表中FT上一時刻 t1的位置 ( x1,y1 ) 、速率 v1。按式（1）和式（2）可求出 t1 - t 2時間內該車輛的平均速率。若v或v′超過了公路上的限制車速，則該FT不具有投票權。若滿足(v- v ′)/v≤ λ ，λ取5%以內，該FT才具有投票權。

MT和審核通過的FT組成投票委員會。為判斷PT的實際位置落于哪個網格，投票委員會對所有網格進行投票。投票規則[8]是：網格與 n個投票者的投票圓環有重疊部分，即有n個投票者認為PT的實際位置落于該網格內，該網格的票數狀態變量加n。網格的票數越多，表示PT的實際位置落于該網格的概率越高。如圖6所示，若PT的聲稱位置在 P T1處，PT得到的票數為3，其聲稱位置具有很高的可信度；若PT的聲稱位置在或處，PT得到的票數為2或1，因網格的最高票數為3，所以PT的聲稱位置是虛假的。

圖6 基于投票的位置驗證

首輪投票結束后，MT可能會發現一個或多個票數最高的網格。MT識別出一個包含所有票數最高網格的最小矩形作為下一輪投票的目標區域，把目標區域以更小的量化間隔劃分為網格，然后再執行新一輪的投票。

新一輪投票開始前，MT須對剩余投票者進行投票資格審核。若投票者沒有把票投給票數最高的網格，該投票者不能參加新一輪投票，同時更新投票委員會。新一輪的投票過程中，由于目標區域的縮小，網格面積減小，這樣位置估計的精確度更高。當達到設置的精度（L小于預設臨界值2Me[9]）時，多輪投票就終止，MT選出最后一輪中產生的票數最高的網格（組），并把它的幾何中心當作PT的估計位置。其中Me為平均測量誤差。

通過投票法得到PT的估計位置后，接著執行閾值判定。閾值判定的過程如下：假設PT的投票法估計位置為()，PT的聲稱位置為(x,y)。若，PT的聲稱位置是正確的，否則PT實施了位置欺騙。τ為預設臨界值，一般設為5以內。

閾值判定后，MT得出PT是否實施了位置欺騙。一個靜態幀的多輪投票過程結束，MT等待下一個靜態幀的到來，啟動新一次多輪投票過程。

2 安全性分析

VANET中，位置驗證方法的安全性是一個關鍵問題。分析一個位置驗證算法的安全性主要是考察其檢測鄰居車輛是否發起位置欺騙攻擊的能力。這里分析了VANET中幾種位置欺騙的情形。

情況1 PT聲稱的位置未落在MT的投票圓環內。這種情況下，基于投票的位置驗證算法能直接通過真實性檢測將這種位置欺騙檢測出來。

情況 2 PT屬于一種狡猾的攻擊者，它能逃脫MT的真實性檢測，但沒有與其他車輛合伙。

情況3 PT屬于一種狡猾的攻擊者，它能逃脫MT的真實性檢測，且勾結其他車輛合伙進行位置欺騙。

在這兩種情況下，假設對于PT來說，有N個鄰居車輛，這些鄰居車輛中有n個良性車輛和m個惡意車輛。可知：

假設1P表示惡意車輛可通過投票資格審核的概率，2P表示良性車輛沒有通過投票資格審核的概率。當且僅當參與投票的良性車輛數小于等于參與投票的惡意車輛數時，即：

無法檢測出PT實施了位置欺騙。由方案假設知：

將式（3）和式（5）代入式（4）得到：

由投票資格審核的規則可推斷出2P的值非常小，接近于0。因此忽略式（6）中的2P，可得：

因為 0 ＜P1＜1，式（7）右邊的值為負，N要小于等于一個負數，這與實際不相符。

通過上述分析，本節主要針對三種基本情況進行了討論，無論哪種情況出現，本算法都可以較高的準確率來驗證位置。

3 實驗仿真

位置驗證方法有效性的評價參數包括：

1）正確率（Rac，Accuracy），Nsv表示正確的位置驗證次數，Ntv表示總的位置驗證次數，則公式為：

2）漏警率（Rfn，False Negative Rate）：指惡意位置被識別為良性位置的比率；Nfm表示通過位置驗證的惡意節點數，Ntm表示總的惡意節點數。公式為：

（3）虛警率（Rfp，False Positive Rate）：是指良性位置被識別為惡意位置的比率；Nfb表示未通過位置驗證的良性節點數，Ntb表示總的良性節點數。公式為：

本次仿真選取的場景為：一個雙向4車道，每車道寬2.5 m，長500 m的高速公路。在這10 m×500 m的目標區域內隨機部署1個主檢測者MT和N-1個鄰居節點，N是車輛總數考慮到不同時刻車流量的不同，道路上會出現密集車輛網絡和稀疏車輛網絡，所以在一天24小時中設置峰頂值1tN和3tN，峰谷值2tN和4tN，峰頂和峰谷間的時間區域內，N是單調的。

車輛在行駛中為勻速運動，速度為（20～42 m/s）間的一個隨機值。車輛分為良性車輛和惡意車輛。良性車輛：以周期T廣播自己的數據包。惡意車輛分為單獨攻擊的車輛和共謀攻擊的車輛。單獨攻擊的車輛：上報的數據包中位置和RSS信息都是隨機的。共謀攻擊的車輛：上報的位置是隨機的，但RSS信息是計算出來的。良性車輛數目與惡意車輛數目也是隨機分布的，但滿足N =+和＞這兩個條件。

仿真結果如圖7和圖8所示。

圖7 兩種位置驗證方法的正確率

圖8 兩種位置驗證方法的漏警率與虛警率

由圖可知，基于投票的位置驗證算法的正確率比基于MMSE的位置驗證算法高，漏警率和虛警率比基于MMSE的位置驗證算法低。

4 結語

檢測位置欺騙，減少位置欺騙相關的攻擊對于VANET的安全性而言是最為關鍵的因素之一。本文的工作主要針對該領域，設計了一種基于投票的位置驗證方法，來有效且安全的實現 VANET中的位置驗證。

本文僅研究了 VANET中的位置驗證，如何將位置驗證同 VANET中較為成熟的安全和隱私保護機制結合起來使用，使之和諧的共同確保 VANET的安全性，還需設計一種安全架構，這也是本文需要進一步研究的內容。

[1] 熊飚,張小橋.VANET網絡中小尺度衰落信道仿真[J].通信技術,2010,43(12):56-57.

[2] 楊躍,王福豹,段渭軍.無線傳感器網絡安全定位研究[J].信息安全與通信保密,2008(09):56-60.

[3] SONG Joo-Han, WONG V W S, LEUNG V C M. Secure Location Verification for Vehicular Ad-Hoc Networks[C].USA:IEEE,2008:1-5.

[4] XUE Xiaoping,LIU Mingyang,LIN Nizhong, et al. TSLV:Time － Slice － Based Location Verification for VANET[J]. China Communications,2011(05):130-143.

[5] ZHONG S, JADLIWALA M, UPADHYAYA S,et al. Towards a Theory of Robust Localization Against Malicious Beacon Nodes[C].USA:IEEE,2008:1391-1399.

[6] LAURENDEAU C, BARBEAU M. Probabilistic Localization and Tracsking of Malicious Insiders Using Hyperbolic Position Bounding in Vehicular Networks[M].USA:ACM,2009:1-13.

[7] WHITEHOUSE K, KARLOF C, CULLER D. A Practical Evaluation of Radio Signal Strength for Ranging-based Localization[J].Mobile Computing and Communications Review,2006,11(01):41-52.

[8] LIU D, NING P, DU W K. Attack-resistant Location Estimation in Sensor Networks[C]. USA:IEEE,2005:99-106.

[9] Yan Gongjun, Chen Xingwang, Olariu. Providing VANET Position Integrity through Filtering[C]. USA:IEEE,2009:1-6.