车载自组织网络中一种同时更改伪码算法

车载自组织网络中一种同时更改伪码算法 ComputerEngineeringandApplications计算机工程与应用 车载自组织网络中一种同时更改伪码算法 李建庆,潘媛媛,冯丽 LIJianqing.PANYuanyuan,FENGLi 澳门科技大学资讯科技学院,澳门999078 FacultyofInformationTechnology,MacauUniversityofScienceandTechnology,Macau999078,China LIJianqing,PANYuanyuan,FENGLi.Algorithmofchan~ngpseudonymssimultaneouslyinVANETs.ComputerEngineering andAppHcafions,2012,48(2):18-21. Abstract:FrequentlychangingpseudonymiscommonlyacceptedasasolutiontoprotectprivacyinVehicularAdhocNETworks (VANETs).Toagainsttheloweffectivenessofmostchangingpseudonymalgorithms,aneffectivealgorithmofchangingpseudonyms simultaneouslyisproposed.Inthealgorithm,abit”waitflag”isinsertedintotheinformationthatvehiclesperiodicallybroadcast, whichisusedtoimprovetheprobabilityofchangingpseudonymssimultaneously,therebytoimprovethesuccessfulrateofchanging pseudonyms.Simulationresultsshowthatthealgorithmcaneffectivelyimpr ovethesuccessfulrateofchangingpseudonyms,thusiten— hancestheeffectivenessofchangingpseudonymstostrengthenprivacyprote ctionofvehicles. Keywords:VehicularAdhocNETworks(VANET);changingpseudonyms;p rivacyprotection 摘要:在车载自组织网络中,频繁更改伪码是一种被广泛接受的保护隐私.针对目前大部分更改伪码算法的有效性较低 的问题,提出了一种有效的同时更改伪码算法.该算法通过在车辆周期性广播的信息中插入一个等待标识比特来提高车辆同时 更改伪码的概率,从而提高更改伪码的成功率.模拟结果表明,该算法能够显着提高更改伪码的成功率,从而提高更改伪码的有 效性,增强车辆的隐私保护. 关键词:车载自组织网络;更改伪码;隐私保护 DOI:10.3778~.issn.1002.8331.2012.02.006文章编号:1002.8331(2012)02.0018-04文献标识码:A中图分类号:TP309 1引言 车载白组织网络作为一种提高交通系统安全,效率和方 便性的技术,这些年来已经受到越来越多研究团体的关注n. 在车载自组织网络中,车辆周期性广播自己的位置和状态信 息,利用这些信息可以实现一系列提高交通系统安全和效率 的应用.不幸的是,不法分子也比较容易监听到这些信息, 并利用这些信息来追踪车辆,威胁车主的隐私.和传统的利 用摄像机或者人工来追踪车辆相比,通过监听信息来追踪车 辆的成本较低,因此车辆被追踪的可能性较高.在车载自组 织网络中,研究和探讨车辆的隐私保护策略变得非常重要. 保护车辆的隐私有多种策略,一种简单,有效且被广泛接 受的方法是通过频繁更改车辆伪码来保护隐私.但是,现 有的大部分更改伪码算法的有效性比较低,其原因是它们更 改伪码的触发条件没有全面考虑相关因素.有的触发条件既 没有考虑车辆的位置和状态信息,也没有考虑车辆更改伪码 的时间信息n,有的触发条件只考虑了车辆的位置和状态信 息,但没有考虑车辆更改伪码的时间信息嘲.虽然最近有人讨 论触发条件时考虑到车辆更改伪码的时间信息,但他们只考 虑到车辆自己更改伪码的时间信息,没有考虑相邻车辆间更 改伪码的同时性.如果更改伪码的触发条件不考虑同时性因 素,车辆更改伪码后隐私攻击者仍可能利用更改伪码的时间 不同来关联车辆相继使用的两个伪码,从而追踪车辆的行踪, 这样更改伪码起不到保护车辆隐私的作用,造成伪码浪费. 伪码浪费使每个车辆所需要的伪码数量增多,从而增加管理 伪码的工作负担. 为了提高更改伪码的有效性,减少伪码的使用量,本文提 出了一种有效的更改伪码算法,该算法在车辆广播的信息中 插入一个等待标识比特,利用这个比特,更改伪码的触发条件 除了考虑车辆的位置和状态信息外,还可以考虑车辆间更改 伪码的同时性.触发条件考虑到相邻车辆间更改伪码的同时 性,可以提高相邻车辆同时更改伪码的概率,从而提高更改伪 码的有效性,增强车辆的隐私保护. 2相关研究工作 车载自组织网络中利用更改伪码来对隐私进行保护的研 究工作主要集中在讨论更改伪码的空间,时间和触发条件等 三方面的问题. 第一方面的工作讨论更改伪码的空间问题.其中一个想 法是将混淆区域(mix.zone)作为更改伪码的空间区域,混淆区 域指隐私攻击者不能获得信息内容的区域.在混淆区域内更 改伪码可以混淆车辆进入混淆区域事件与离开混淆区域事件 的关联性,从而降低车辆被追踪的概率.Beresford首先讨论 了如何利用混淆区域保护位置隐私,随后Freudiger等人提 出利用对称密钥在交通十字路口对车辆广播的信息进行加 密n”,使交通十字路口成为混淆区域,并将多个混淆区域组成 一 个混淆网络(mix.network)来进一步增强隐私保护[12]0 第二方面的工作讨论车辆更改伪码的时间问题.Sampi. gethaya等人提出车辆在通信过程中随机沉默一段时间,并在 基金项目:澳门特别行政区科学技术发展基金(No.016/2010/A). 作者简介:李建庆(1969一),男,博士,副教授,主要研究领域为计算机网络,车载网络,光网络以及光通信等;潘嫒媛(1979一),女,博士研究生 冯丽(1976一),女,博士研究生,讲师.E—mail:jqli@must.edu.mo 收稿日期:2011-07.15;修回日期:2011.09.23 李建庆,潘媛媛,冯丽:车载自组织网络中一种同时更改伪码算法 沉默期内更改伪码.这种方法的缺点是,在沉默期内车辆不 广播信息很可能带来交通安全隐患. 第三方面的工作设定车辆更改伪码的触发条件,当触发 条件满足时则更改伪码.这种方法的好处是,车辆通过设定 不同的触发条件可以方便地选取更改伪码的空间和时间.本 文的工作属于此方面的研究.Song等人以车辆密度作为触发 条件fl4l,实际上是考虑了车辆的位置信息来选取更改伪码的 地点.Freudiger等人根据伪码的年龄,邻车数目以及隐私需 求来设定触发条件,他们设定的触发条件考虑了车辆的位置 信息和车辆自己更改伪码的时间信息.Gerlach等人提出以 混淆信息(mixcontext)作为触发条件嗍,混淆信息指能提供匿 名性的任何信息,但他们所讨论的混淆信息指车辆的位置和 状态信息,并且在模拟时只考虑了位置信息. 本文认为现有的更改伪码的触发条件都没有考虑相邻车 辆更改伪码的同时性,使其有效性较低.为了提高更改伪码 的有效性,必须提高车辆间同时更改伪码的概率,这触发 条件必须考虑相邻车辆更改伪码的同时性.为了更好地理解 后面提出的更改伪码算法,下面首先讨论更改伪码的有效性 和其触发条件间的关系. 3更改伪码的有效性 攻击者主要利用车辆广播信息中不能改变的数据,协议 信息,车辆的位置和状态信息以及伪码更改的时间信息来追 踪车辆.本文仅考虑利用车辆的位置信息,状态信息以及更 改伪码的时间信息来追踪车辆的问题. 车辆广播信息的周期,称之为时隙,假定所有车辆的时隙长 短—样,都装有GPs接收器,利用GPs接收到的时间信号可以实现 时隙同步.车辆在t时隙广播的信息定义为{尸,vt,Dt,,t}, 其中,P表示车辆在t时隙的位置,v:表示车辆在t时隙 的速度,表示车辆在f时隙的行驶方向,{P,1,t,Df}表示 车辆在t时隙的状态(状态一般包括车辆的位置,速度,加 速度和行驶方向,为简单起见,本文不考虑加速度,根据车辆 前后相邻时隙的速度可以算出其加速度),表示车辆在t 时隙使用的伪码.如果两辆车位于相同的路段,相距距离小 于r米,称之为位置相近,两辆车的位置相近意味着攻击者不 能根据位置信息来区分它们.两辆位置相近的车辆,速度相 差小于d米/j眇,行驶方向一样,则称之为状态相似,两辆车的 状态相似意味着攻击者不能根据状态信息来区分它们.,和 d的大小一般固定,具体数值根据实际情况决定,,和车辆定 位系统的精度有关,d和车辆广播信息的周期有关.两辆车 在同—个时隙更改伪码称之为同时更改伪码,两辆车同时更改 伪码意味着攻击者不能根据更改伪码的时间信息来区分它们. 对使用更改伪码来保护隐私的某车辆进行追踪分为三 个阶段.假设车辆在时隙t更改伪码,第一阶段,必须知道 时隙t一1车辆使用的伪码为,,称之为”鉴别”.第二阶 段,车辆在时隙t更改伪码为,根据获得的其他信息,推 理得知这两个伪码和是指同一辆车,称之为”关联”. 第三阶段,车辆每次更改伪码后,都可以将其更改前后的两 个伪码关联,经过多次关联,将车辆使用的所有伪码都关联 起来,根据这些伪码对应的时隙和位置,即可追踪车辆的行 踪,威胁其隐私,这个阶段的工作称之为”追踪”. 本文主要考虑更改伪码问题,更改伪码的目的是当某辆 车更改伪码时,攻击者不能推断出哪辆车更改了伪码,从而难 以完成关联工作,保护车辆的隐私.攻击模型定义如下:某时 隙如果位置相近或状态相似的车辆中只有一辆车更改伪码, 攻击者很容易判断出哪辆车更改了伪码;某时隙如果位置相 近的车辆中至少有两辆以上车辆同时更改伪码,攻击者不能根 据该时隙车辆的位置信息或更改伪码的时间信息判断出哪辆车 更改了伪码,但如果更改伪码车辆的状态不同,攻击者可以根据 前后时隙车辆的位置信息完成关联工作,因为状态不同的车辆 在前后相邻两个时隙的位置不同的可能性较大.某时隙如果状 态相似的车辆中至少两辆车同时更改伪码,关联工作较难以 完成,则认为更改伪码成功,否则更改伪码失败.在本文中, 更改伪码成功,意味着更改伪码有效,反之,更改伪码无效. 4同时更改伪码算法 这一部分详细讨论更改伪码算法.为了描述方便,先给 出这些算法的共同假定,每个伪码的使用时间有最短使用时 间和最长使用时间的限制.最短使用时间是为了满足车载自 组织网络地理路由的需求n.最长使用时间是为了提供最低 程度隐私保护的需要,因为某个伪码使用时间越长,攻击者就 有更多的时间来关联伪码.通过对伪码设定最长使用时间, 可以对车辆的隐私进行一定的保护. 车辆更改伪码后的时间小于伪码最短使用时间,不能更 改伪码,称车辆处于”伪码稳定”状态.当超过伪码最短使用 时间后,车辆根据更改伪码的触发条件更改伪码.从伪码的 最短使用时间至下次更改伪码的时间称之为”等待时间”,在 这段时间内,车辆处于”等待更改伪码”状态.在伪码最短使 用时问和最长使用时间之间,车辆发现自己满足触发条件则 在下一个时隙更改伪码,这种满足触发条件的伪码更改称之 为”主动更改”.等待时间的最大值为伪码最长使用时间与最 短使用时间之差,当等待时间达到最大值时,车辆还没有满足 触发条件,系统则强制更改伪码,这种强制的伪码更改称之为 “被动更改”. 如果更改伪码的触发条件只考虑车辆的位置和状态信 息,当某辆车发现自己达到了触发条件决定下一个时隙更改 伪码时,其他与之相似状态的车辆下一个时隙可能还处于”伪 码稳定”状态,不能更改伪码,则下一个时隙两辆或以上车辆 同时更改伪码的概率非常低,这将导致更改伪码的成功率非 常低.为了提高车辆更改伪码的成功率,必须提高同时更改 伪码的概率.为此,更改伪码的触发条件必须考虑车辆问更 改伪码的同时性.考虑到车辆问更改伪码的同时性,下面提 出一种有效的更改伪码算法.该算法的核心思想是,在车辆 广播的信息中插入一个等待标识比特,该比特的不同数值表 示车辆是否处于等待更改伪码状态.这种算法可以使两两互 为相似状态的车辆同时决定下一个时隙主动更改伪码,称之 为同时更改伪码算法.由于时隙的量级一般为几百毫秒至一 秒,车辆决定更改伪码时的状态和更改伪码时的状态相差一 般不会太大,决定更改伪码时互为相似状态的车辆下一个时 隙仍互为相似状态的概率非常高,且同时更改伪码,则更改伪 码的成功率非常高. 同时更改伪码算法流程图如图1所示.某车辆伪码系统 启动时,首先选取一个伪码作为改伪码算法的性能随时间的变化情况,然后比较不同交通流 量密度对三种更改伪码算法性能的影响.主要考虑的性能指 标包括所有车辆使用的伪码总数,成功更改的伪码总数,更改 伪码的成功率和平均每辆车使用的伪码数. 在模拟过程中,发现数分钟后系统进入稳定状态.为了 保证结果的稳定性,每次模拟以第10分钟为记录时间起点,每 分钟记录一次使用的伪码总数以及成功更改的伪码总数,连 续记录10分钟,更改伪码的成功率为记录时刻的成功更改的 伪码总数与使用的伪码总数之比,代表从记录时间起至该时 刻的平均更改伪码的成功率. 图4给出了中等交通流量(2o辆/公里)情况下,三种更改 伪码算法使用的伪码总数,成功更改的伪码总数以及更改伪 码的成功率随时间的变化情况.从图4中可以明显看出,三种 算法使用的伪码总数和成功更改的伪码总数基本上随时间都 呈线性增长,成功率基本上不随时间变化.时间从10分钟变 化至15分钟时,和相似状态更改伪码算法相比,同时伪码更改 算法使用的伪码总数减小了大约23%,成功更改的伪码总数 却多了大约1.8倍,更改伪码的成功率从约l1%升至约41%;同 样和相似状态更改伪码算法相比,相近位置更改伪码算法使 用的伪码总数多了大约11%,成功更改的伪码总数少了大约 32%,伪码更改的成功率从约11%降至约7%.这些结果表明, 触发条件中考虑位置因素的基础上再考虑状态因素对更改伪 码算法的性能影响较小,同时性因素比状态因素对更改伪码 算法的性能影响大,说明了触发条件中考虑同时性的重要性. 交通流量密度影响车辆间的距离,车辆间的距离影响车 辆的行驶速度.车辆间的距离和车辆的行驶速度对车辆处于 互为相似状态的时间长短和频率有重要影响,从而影响使用 的伪码数和更改伪码的成功率.由于不同的交通流量密度对 应的车辆总数不_样,使用的伪码总数和成功更改的伪码总 数两个性能参数不能够准确反映不同交通流量情况下每种更 改伪码算法的性能,为此,将讨论的性能参数改为平均每辆车 使用的伪码数和更改伪码的成功率.模拟时,平均每辆车使 用的伪码数为从记录时间起至第20分钟的伪码使用总数与车 辆总数之比. 图5描述了三种更改伪码算法的平均每辆车使用的伪码 数和更改伪码的成功率随交通流量密度的变化情况.从图5 (a)中可以看出,随着交通流量密度的增加,这三种更改伪码 算法的平均每辆车使用的伪码数都相应增加,这是由于随着 交通流量密度的增加,车辆拥有更多机会达到触发条件主动 更改伪码,从而使平均每辆车使用的伪码数增加.从图5(b) 中可以发现,随着交通流量密度的增加,对于相似状态更改伪 码算法和相近位置更改伪码算法,它们更改伪码的成功率基 本不变.对于同时更改伪码算法,当交通流密度从15辆/公里 增至40辆里时,其成功率显着增加,从41%上升至63%,这 说明了在高交通流密度的情况下,触发条件中的同时性因素 对更改伪码算法的性能影响更大. 6总结 隐私保护是车载自组织网络重要的研究内容,通过更改 伪码来保护车辆隐私是一种广泛被接受的方法.更改伪码的 触发条件对更改伪码的有效性有重要影响.为了提高更改伪 码的有效性,本文提出了同时更改伪码算法.模拟结果表明, 该算法能够有效提高车辆同时更改伪码的概率,从而提高伪 码更改的有效性,增强车辆的隐私保护.触发条件中的同时 性因素对更改伪码算法的性能影响较大. (下转38页) O5O5O5O5O 655443322巅露g旺塔卅驿蜡E汗 382012,48(2)ComputerEngineeringandApplications计算机工程与应用 d(曰,c)=0.2733. 从上述计算结果可以看出:,之间的距离测度很小,而 ,c之间的距离测度和,c之间的距离测度则相对较大,据 此可以推测P.,尸:两个模式相同,而属于与前两者不同的 模式. 7结论 本文针对以往学者研究模糊熵,距离测度和相似性测度 三者关系时所采用定义存在的缺陷,在更为严格的定义下,利 用模糊集之间的运算研究了三者之间的关系,给出了一些新 的诱导公式,为进一步研究这三种度量开拓了新的思路. 参考文献: [1]ShangXG,JiangWS.Anoteonfuzzyinformationmeasures[J]. PatternsRecognitionLetters,1997,18:425—432. [2]GhoshA.Useoffuzzinessmeasuresinlayerednetworksforobject extraction:ageneralization[J].FuzzySetsandSystems,1995,72: 331—348. [3】PalSK.Anoteonthequantitativemeasuresofimageenhance- mentthoughfuzziness[J].IEEETransonPatternAnalMachine Intell,1982,14:204-208. 【4】PalNR,PalSK.Object—backgroundsegmentationusingnew definitionsofentropy[J].IEEEProc,1989,36:284?295. [5】LeeHM,WangWT.Aneuralnetworkarchitectureforclassifica— tionoffuzzyinputs[J].FuzzySetsandSystems,1994,63:159—173. 【6】SinhaD,DoughertyER.Fuzzificationofsetinclusion:theory andapplications[J].FuzzySetsandSystem,1993,55:15—42. [7]DeLucaA,TerminiS.Adefinitionofanonprobabilitiesentropy inthesettingoffuzzysettheory[J].InformandControl,1972, 20:301—312. [8】LiuXuecheng.Entropy,distancemeasureandsimilaritymeasure offuzzysetsandtheirrelations[J].FuzzySetsandSystems, 1992,52:305-318. [9】MeiXiao—feng,XinXiao—long.Entropy,distancemeasureanddi— vergencemeasure[J].FuzzySystemsandMathematics.2006,20: 57—61. [10]FanJiulun,XieWeixin.Distancemeasureandinducedfuzzyen— tropy[J].FuzzySetsandSystems,1999,104:305—3l4. [11]孙义阳,辛小龙.模糊熵与距离测度的相互诱导及其应用[J】.纯粹 数学与应用数学,2009,25:396.401. [12】YagerRR.OnmeasuresoffuzzinessandnegationPartI:mem— 229 bershipintheunitinterval[J].IntJGenSyst,1979,5:221— [13]范九伦.相似性测度与模糊熵诱导关系的注记[J]_模糊系统与数 学,2008,22(2):117.125. [14]FanJL,XieWX.Subsethoodmeasure:newdefinitons[J].Fuzzy SetsandSystems,1999,106:201—209. (上接21页) 参考文献: [1】PapadimitratosP,FortelleAL,EvenssenK,eta1.Vehicularcorn- municationsystems:enablingtechnologies,applications,andfu— tureoutlookonintelligenttransportation[J].IEEECommunica— tionsMagazine.2009,47(11):84—95. 【2]QuF,WangF-Y,YangL.Intelligenttransportationspaces:vehicles, traffic,communications,andbeyond[J].IEEECommunicationsMag— azine,2010,48(11):136.142. [3】PapadimitratosP,ButtyanL,HolczerT,eta1.Securevehicular communicationsystems:designandarchitecture[J].IEEECommu- nicationsMagazine,2008,46(11):100—109. [4]RayaM,HubauxJ-EThesecurityofvehicularadhocnetworks[C]// TheThirdACMWorkshoponSecurityofAdHocandSensor Networks,AlexandriaVA,USA,November7-10,2005:11-21. [5】RayaM,PapadimitratosP,HubauxJ-ESecuringvehicularnet- works[J].IEEEWirelessCommunications,2006,13(5):8-15. 【6]ArmknechtF,FestagA,WesthoffD,eta1.Cross-layerprivacyen— hancementandnon-repudiationinvehicularcommunication[C]// The4thWorkshoponMobileAd—HocNetworks,Bern,Switzer- 1and,MarchI一2.2007:l-12. [7]FreudigerJ,ManshaeiM,BoudecJ-YL,eta1.Ontheageof pseudonymsinmobileadhocnetworks[C]//The29thIEEEIn— ternationalConferenceonComputerCommunications,SanDi? ego,CA,USA,Mar15-19,2010:1-9. [8】GerlachM,GuttlerF.PrivacyinVANETsusingchangingpseud— onyms-idealandreal[C]//The65thIEEEVehicularTechnology Conference,Dublin,Ireland,April22—25,2007:2521-2525. [9】BeresfordAR,StajanoF.Locationprivacyinpervasivecomput— ing[J].IEEEPervasiveComputing,2003,2(1):46?55. [10】BeresfordAR.Locationprivacyinubiquitouscomputing[D]. UniversityofCarnbridge,2005. [11]FreudigerJ,RayaM,FeleghhaziM.Mix—zonesforlocationpri— vacyinvehicularnetworks[C]//TheFirstInternationalWork- shoponWirelessNetworkingforIntelligentTransportation Systems,Vancouver,BritishColumbia,Canada,August14,2007: 1.7. [12]FreudigerJ,ShokriR,HubauxJ-EOntheoptimalplacementof MixZones[C]//The9thInternationalSymposiumonPrivacy EnhancingTechnologies,Seattle,WA,USA,August5-7,2009: 216.234. [13】SampigethayaK,LiM,HuangL,eta1.AMOEBA:robustloca— tionprivacyschemeforVANET[J].IEEESelectedAreasin 1589. Communications,2007,25(8):1569— [14】SongJ-H,WongV,LeungV.Wirelesslocationprivacyprotec— tioninvehicularad—hocnetworks[J].MobileNetworksandAp— plications,2010,15(1):l60—171. [15】StojmenovicI.Position—basedroutinginadhocnetworks[J]. IEEECommunicationMagazine.2002,40(7):128—134. 【16]ChoffnesD,BustamanteF.Anintegratedmobilityandtraffic modelforvehicularwirelessnetworks[C]//TheSecondACM IntemationalWorkshoponVehicularAdHocNetworks,Co— logne,Germany,Sept2,2005:69—78.