1、Location Identification and Vehicle Tracking using VANET(VETRAC)Adviser: Ho-Ting WuSpeaker: Yi-Wei SunDate: 2008/4/1 1第一頁(yè)，共四十二頁(yè)。OutlineAutomotive Navigation 定位法VETRAC(Vehicle Tracking)ConclusionReference2第二頁(yè)，共四十二頁(yè)。Mobile Vehicle Tracking System3NavigationServerVehicleTrackingSystemVehicleTrackingSys

2、temAccess Point 1 Access Point - nClient 1Client 1Client 1Wireless communicationWireless communication第三頁(yè)，共四十二頁(yè)。Automotive Navigation以wirless mobile導(dǎo)航系統(tǒng)為基礎(chǔ)的radio frequency使用digital map根據(jù)車(chē)輛位置，給與指南並運(yùn)用道路資訊的Database，給予使用者多條到達(dá)目的地的路徑指引。最早實(shí)踐的Automotive Navigation4+Digital map-matchingDead reckoning第四頁(yè)，共四十二

3、頁(yè)。Dead reckoning the process of estimating a global position速度方向現(xiàn)在位置時(shí)間5Wheel sensorsMagnetic compassDigital map-matching第五頁(yè)，共四十二頁(yè)。Dead reckoning609:00方向09:30車(chē)Speed :60 km/h 10:00第六頁(yè)，共四十二頁(yè)。Dead reckoning問(wèn)題7Wheel sensorsMagnetic compassDigital map-matchingdependdependGPS不規(guī)則的磁場(chǎng)!第七頁(yè)，共四十二頁(yè)。GPS(Global Pos

4、itioning System)美國(guó)國(guó)防部與?？哲姽餐M(jìn)行之計(jì)畫(huà)，供美軍所使用。目前免費(fèi)提供給民間使用其定位訊號(hào)所有權(quán)屬於美國(guó)交通部加入S/A(Selective Availability)效應(yīng)干擾訊號(hào) 降低民用GPS接收機(jī)定位精確度。95%的接收狀況精確度在直徑100公尺內(nèi)。5%的接收狀況在直徑300公尺內(nèi)。8三點(diǎn)定位法第八頁(yè)，共四十二頁(yè)。定位-三點(diǎn)定位法9ACB第九頁(yè)，共四十二頁(yè)。定位-三點(diǎn)定位法10ACB第十頁(yè)，共四十二頁(yè)。定位-三點(diǎn)定位法11A=(x，y)C=(xC，yC)B=(xB，yB)rrBrCMaximum likelihood method(x，y)取最小的一個(gè)第十一頁(yè)，共四

5、十二頁(yè)。定位-多點(diǎn)定位法12BADCGPSGPSGPSGPSGPSGPSGPSGPS第十二頁(yè)，共四十二頁(yè)。CAB定位-多點(diǎn)定位法13DGPSGPSGPSGPSGPSGPSGPSGPS第十三頁(yè)，共四十二頁(yè)。定位-合作多點(diǎn)定位法14ACEFDDBB第十四頁(yè)，共四十二頁(yè)。802.11的定位技術(shù)常用的有兩種Radio Propagation ModelStatic Scene AnalysisRadio Propagation Model 平均誤差大約 45公尺Static Scene Analysis 平均誤差大約 23公尺不論是哪種，皆有兩個(gè)階段Training phaseLocation Est

6、imation phase15第十五頁(yè)，共四十二頁(yè)。Training Phase收集所有參考點(diǎn)所發(fā)出的訊號(hào)到各個(gè)training locations的訊號(hào)特徵。training locations: 是在欲建立部署的定位系統(tǒng)的802.11訊號(hào)空間中，已知的實(shí)際位置。1. 先決定一群training locations的座標(biāo)。2. 接著在這些training locations上收集附近參考點(diǎn)的訊號(hào)強(qiáng)度並輸入進(jìn)定位資料庫(kù)中。3. 根據(jù)資料庫(kù)內(nèi)容，建立定位模組。4. 透過(guò)定位模組可以快速比對(duì)出一個(gè)未知位置的訊號(hào)樣本的最可能的位置 。16第十六頁(yè)，共四十二頁(yè)。Location Estimation

7、Phase比對(duì)待定位的目標(biāo)物體所接到的訊號(hào)樣本最可能出現(xiàn)在哪一個(gè)training locations上。這需要大量的計(jì)算因此就有各種定位演算法在其中藉著計(jì)算來(lái)推出這未知位置可能的實(shí)際位置17第十七頁(yè)，共四十二頁(yè)。流程圖18(x1,y1 1)(x2,y22)(xm,ymm)定位資料庫(kù)第一階段：Training phase定位模型(x,y)第二階段：Location Estimation phase表在此training locations上接收到的第i個(gè)參考點(diǎn)的訊號(hào)強(qiáng)度表示此training locations的座標(biāo)第十八頁(yè)，共四十二頁(yè)。Radio Propagation ModelTraini

8、ng phase建立訊號(hào)特徵建立參考點(diǎn)與AP之間距離的對(duì)應(yīng)函數(shù)Location Estimation phase根據(jù)Training phase所建立的對(duì)應(yīng)函數(shù)計(jì)算出參考點(diǎn)與AP之間的距離利用定位演算法估計(jì)參考點(diǎn)可能的位置演算法：三點(diǎn)定位法19第十九頁(yè)，共四十二頁(yè)。Static Scene AnalysisTraining phase建立Training set，存放在training locations上建立參考點(diǎn)對(duì)AP的訊號(hào)特徵Location Estimation phase根據(jù)Training phase的訊號(hào)特徵運(yùn)用定位演算法估出可能位置定位演算法：K-Nearest Neighbo

9、rs algorithmConditional Probability algorithmSimple Point Matching algorithmBayesian Inference algorithm 20第二十頁(yè)，共四十二頁(yè)。Nearest Neighbor algorithm在Training phase時(shí)會(huì)對(duì)每一個(gè)training locations在定位模組中建立一個(gè)Characteristic vector(特徵向量)21Ci = Cij 代表在訓(xùn)練位置i從參考點(diǎn)j收到的所有訊號(hào)強(qiáng)度的平均值 在Location Estimation phase時(shí)對(duì)於一個(gè)未知位置的目標(biāo)物，會(huì)根

10、據(jù)其接收到的訊號(hào)樣本S = ，計(jì)算這個(gè)樣本到各個(gè)定位模組中的Characteristic vector的幾何距離再根據(jù)幾何距離，找出具有最小幾何距離的training locations作為定位的結(jié)果。第二十一頁(yè)，共四十二頁(yè)。K-Nearest Neighbor algorithm為Nearest Neighbor algorithm的變形先根據(jù)Nearest Neighbor的Training phase中所計(jì)算的各個(gè)training locations與訊號(hào)樣本的幾何距離從中挑出k個(gè)最小的training locations接著平均這些位置的x座標(biāo)與y座標(biāo)平均的結(jié)果，就作為估測(cè)的定位結(jié)果而

11、Nearest Neighbor只是k-Nearest Neighbor在k=1時(shí)的特例22第二十二頁(yè)，共四十二頁(yè)。Conditional Probability algorithm 是以機(jī)率分佈表示每個(gè)training locations的特徵向量23特徵向量Ci = 訊號(hào)樣本S = 機(jī)率演算法則會(huì)去計(jì)算在各個(gè)training locations觀察到這個(gè)訊號(hào)樣本的機(jī)率，即最後根據(jù)每一個(gè)training locations所計(jì)算出來(lái)的機(jī)率，找出擁有最大機(jī)率的training locations作為最後的定位。第二十三頁(yè)，共四十二頁(yè)。Conditional Probability algori

12、thm Example:當(dāng)環(huán)境中有三個(gè)參考點(diǎn)，而我們收到的訊號(hào)強(qiáng)度樣本為 S = 如下圖24p1p2p3因此訓(xùn)練位置i收到的樣本S的機(jī)率為 p1 p2 p3最後根據(jù)每一個(gè)training locations所計(jì)算出來(lái)的機(jī)率，找出擁有最大機(jī)率的training locations作為最後的定位。第二十四頁(yè)，共四十二頁(yè)。Location Identification and Vehicle Tracking using VANET(VETRAC)25第二十五頁(yè)，共四十二頁(yè)。IntroductionVehicles tracking systems 是一種電子設(shè)備，安裝於車(chē)輛之上，供使用者自己會(huì)第三

13、方track車(chē)輛的位置。GPS就是現(xiàn)代既簡(jiǎn)單又精確的Vehicles tracking系統(tǒng)。GPS缺點(diǎn):無(wú)法偵測(cè)大型室內(nèi)的地方如：大學(xué)裡、機(jī)場(chǎng)、隧道 等而WiFi就可以對(duì)這些地方給予tracking的服務(wù)。26第二十六頁(yè)，共四十二頁(yè)。Goal27事故車(chē)AP道路封閉估計(jì)道路重開(kāi)的時(shí)間詢(xún)問(wèn)或建議去繞道第二十七頁(yè)，共四十二頁(yè)。預(yù)設(shè)環(huán)境 - VETRAC使用WiFi預(yù)期移動(dòng)的路徑上已佈滿(mǎn)APCarriers收集資訊當(dāng)前的位置目的地的位置或地標(biāo)也可以透過(guò)streaming traffic video知道道路的狀況28第二十八頁(yè)，共四十二頁(yè)。Motivation - VETRAC在matching車(chē)輛資訊

14、的訊息傳輸，要減小和避免congestion的發(fā)生。提供給駕駛者一個(gè)安全又聰明的最佳路徑。提供traffic video information讓駕駛知道詳細(xì)的道路狀況。給予駕駛者會(huì)新進(jìn)這城市的人，指定明確的地標(biāo)。藉由WiFi能不受限制的不間斷的提供通訊連結(jié)。29第二十九頁(yè)，共四十二頁(yè)?，F(xiàn)實(shí)面的挑戰(zhàn)High-speed mobility車(chē)輛的移動(dòng)只限制在車(chē)行道上駕駛者出乎意料的行為交通狀況中存在的變數(shù)30第三十頁(yè)，共四十二頁(yè)。Interoperability是指不同的計(jì)算機(jī)系統(tǒng)、網(wǎng)路、操作系統(tǒng)和應(yīng)用程式一起工作並共享信息的能力。31第三十一頁(yè)，共四十二頁(yè)。VETRAC Interoperabi

15、lity Framework32SINGLE HOP ACCESSCarrierMULTI HOP ACCESSConsumerABMobile Nodes (WiFi/PDA)Base StationWiFi Access PointGATEWAY第三十二頁(yè)，共四十二頁(yè)。Some issuesMANET raises several interesting issues in regard to data forwarding。EX1: 當(dāng)封閉的道路再度開(kāi)啟時(shí)，carriers就不應(yīng)該再傳送有關(guān)道路封閉的資訊出去。EX2: 當(dāng)交通停擺時(shí)， carriers可能會(huì)浪費(fèi)過(guò)多的廣播，給所有會(huì)遇到交

16、通停擺的車(chē)子。VETRAC解法:在carriers傳送事件訊息時(shí)，先過(guò)濾資訊。當(dāng)接收到訊息時(shí)， carriers會(huì)去看事件的Location與expiration time(e.g. 道路重開(kāi)的時(shí)間)假如超過(guò)規(guī)定的距離與時(shí)間，就discard此訊息33第三十三頁(yè)，共四十二頁(yè)。Some issues網(wǎng)路congestion問(wèn)題假設(shè)所有的carriers都傳送相同的訊息，連相鄰的carriers也都傳送同一份訊息時(shí)。VETRAC解法:在carriers中實(shí)做一個(gè)”redundant message”的過(guò)濾機(jī)制當(dāng)聽(tīng)到一個(gè)跟自己正要送的訊息相同的訊息時(shí)，會(huì)移除自己的，並將他加到自己的訊息queue中的

17、最後面。34第三十四頁(yè)，共四十二頁(yè)。Vehicle Tracking Setup35Adaptive FrontLighting ApplicationCurve SpeedLighting ApplicationSensor DataProcessingWiFi ReckoningMap MatchingAddress MatchMAPDATABASEHumanMachineInterfaceRoutePlanningGuidance第三十五頁(yè)，共四十二頁(yè)。VETRAC Functionality Frame-Work36Map Display SystemEstablish Connect

18、ionNew client registrationClient current locationDestination clients locationLandmark IdentificationTraffic informationTraffic video informationClient control PanelConnection Establish ServerLocation ServerTrafficServerPositioningServerVehicle Tracking SystemLandmark databaseClient registration data

19、baseClient location databaseLocation dataTraffic dataTraffic video streamingVehicle location informationDatabase systemNavigation ServerRegistrationLandmark dataClient Location dataEstablish connectiondataUpdate data第三十六頁(yè)，共四十二頁(yè)。Vehicle Traffic Navigate37車(chē)車(chē)車(chē)車(chē)Navigation ServerWiFiWiFiWiFiWiFiWiFiWiFiW

20、iFiWiFiWiFiWiFi車(chē)ABCommunicateLane 7Lane 9第三十七頁(yè)，共四十二頁(yè)。VETRACImplementation and Result38Map DisplayCurrent LocationDestination Client LocationLandmark IdentificationGet Traffic InformationGet Traffic Video第三十八頁(yè)，共四十二頁(yè)。Conclusion and Future WorkVETRAC advantage:提供使用者在任何時(shí)間任何地點(diǎn)，都能運(yùn)用WiFi連結(jié)，來(lái)提供資訊。補(bǔ)足GPS不能偵測(cè)到

21、的環(huán)境 如: 機(jī)場(chǎng)裡,隧道。VETRAC disadvantage:VETRAC並沒(méi)有支援安全機(jī)制(未來(lái)發(fā)展)關(guān)於技術(shù)理論方面，沒(méi)有太深入的介紹以WiFi在臺(tái)灣目前的佈點(diǎn)率來(lái)說(shuō)，此系統(tǒng)可能無(wú)法運(yùn)作相對(duì)的，這是一項(xiàng)很有參考價(jià)值成果，對(duì)將來(lái)有意發(fā)展類(lèi)似研究的，應(yīng)該能給予很大的幫助。39第三十九頁(yè)，共四十二頁(yè)。References【1】A Thangavelu , K Bhuvaneswari, K Kumar, K, Location Identification and Vehicle Tracking using VANET (VETRAC), IEEE ICSCN, 2007【2】Sweeney, L.E., “Comparative benefits of various automotive navigation and routing technologies ”, IEEE