电信行业mobile导航系统为基础的radio

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

2、temAccess Point 1 Access Point - nClient 1Client 1Client 1Wireless communicationWireless communication第三页，共四十二页。Automotive Navigation以wirless mobile導航系統為基礎的radio frequency使用digital map根據車輛位置，給與指南並運用道路資訊的Database，給予使用者多條到達目的地的路徑指引。最早實踐的Automotive Navigation4+Digital map-matchingDead reckoning第四页，共四十二

3、页。Dead reckoning the process of estimating a global position速度方向現在位置時間5Wheel sensorsMagnetic compassDigital map-matching第五页，共四十二页。Dead reckoning609:00方向09:30車Speed :60 km/h 10:00第六页，共四十二页。Dead reckoning問題7Wheel sensorsMagnetic compassDigital map-matchingdependdependGPS不規則的磁場!第七页，共四十二页。GPS(Global Pos

4、itioning System)美國國防部與海空軍共同進行之計畫，供美軍所使用。目前免費提供給民間使用其定位訊號所有權屬於美國交通部加入S/A(Selective Availability)效應干擾訊號 降低民用GPS接收機定位精確度。95%的接收狀況精確度在直徑100公尺內。5%的接收狀況在直徑300公尺內。8三點定位法第八页，共四十二页。定位-三點定位法9ACB第九页，共四十二页。定位-三點定位法10ACB第十页，共四十二页。定位-三點定位法11A=(x，y)C=(xC，yC)B=(xB，yB)rrBrCMaximum likelihood method(x，y)取最小的一個第十一页，共四

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

6、imation phase15第十五页，共四十二页。Training Phase收集所有參考點所發出的訊號到各個training locations的訊號特徵。training locations: 是在欲建立部署的定位系統的802.11訊號空間中，已知的實際位置。1. 先決定一群training locations的座標。2. 接著在這些training locations上收集附近參考點的訊號強度並輸入進定位資料庫中。3. 根據資料庫內容，建立定位模組。4. 透過定位模組可以快速比對出一個未知位置的訊號樣本的最可能的位置 。16第十六页，共四十二页。Location Estimation

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

8、ng phase建立訊號特徵建立參考點與AP之間距離的對應函數Location Estimation phase根據Training phase所建立的對應函數計算出參考點與AP之間的距離利用定位演算法估計參考點可能的位置演算法：三點定位法19第十九页，共四十二页。Static Scene AnalysisTraining phase建立Training set，存放在training locations上建立參考點對AP的訊號特徵Location Estimation phase根據Training phase的訊號特徵運用定位演算法估出可能位置定位演算法：K-Nearest Neighbo

9、rs algorithmConditional Probability algorithmSimple Point Matching algorithmBayesian Inference algorithm 20第二十页，共四十二页。Nearest Neighbor algorithm在Training phase時會對每一個training locations在定位模組中建立一個Characteristic vector(特徵向量)21Ci = Cij 代表在訓練位置i從參考點j收到的所有訊號強度的平均值 在Location Estimation phase時對於一個未知位置的目標物，會根

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

11、Nearest Neighbor只是k-Nearest Neighbor在k=1時的特例22第二十二页，共四十二页。Conditional Probability algorithm 是以機率分佈表示每個training locations的特徵向量23特徵向量Ci = 訊號樣本S = 機率演算法則會去計算在各個training locations觀察到這個訊號樣本的機率，即最後根據每一個training locations所計算出來的機率，找出擁有最大機率的training locations作為最後的定位。第二十三页，共四十二页。Conditional Probability algori

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

13、方track車輛的位置。GPS就是現代既簡單又精確的Vehicles tracking系統。GPS缺點:無法偵測大型室內的地方如：大學裡、機場、隧道 等而WiFi就可以對這些地方給予tracking的服務。26第二十六页，共四十二页。Goal27事故車AP道路封閉估計道路重開的時間詢問或建議去繞道第二十七页，共四十二页。預設環境 - VETRAC使用WiFi預期移動的路徑上已佈滿APCarriers收集資訊當前的位置目的地的位置或地標也可以透過streaming traffic video知道道路的狀況28第二十八页，共四十二页。Motivation - VETRAC在matching車輛資訊

14、的訊息傳輸，要減小和避免congestion的發生。提供給駕駛者一個安全又聰明的最佳路徑。提供traffic video information讓駕駛知道詳細的道路狀況。給予駕駛者會新進這城市的人，指定明確的地標。藉由WiFi能不受限制的不間斷的提供通訊連結。29第二十九页，共四十二页。現實面的挑戰High-speed mobility車輛的移動只限制在車行道上駕駛者出乎意料的行為交通狀況中存在的變數30第三十页，共四十二页。Interoperability是指不同的計算機系統、網路、操作系統和應用程式一起工作並共享信息的能力。31第三十一页，共四十二页。VETRAC Interoperabi

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

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

17、最後面。34第三十四页，共四十二页。Vehicle Tracking Setup35Adaptive FrontLighting ApplicationCurve SpeedLighting ApplicationSensor DataProcessingWiFi ReckoningMap MatchingAddress MatchMAPDATABASEHumanMachineInterfaceRoutePlanningGuidance第三十五页，共四十二页。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第三十六页，共四十二页。Vehicle Traffic Navigate37車車車車Navigation ServerWiFiWiFiWiFiWiFiWiFiWiFiW

20、iFiWiFiWiFiWiFi車ABCommunicateLane 7Lane 9第三十七页，共四十二页。VETRACImplementation and Result38Map DisplayCurrent LocationDestination Client LocationLandmark IdentificationGet Traffic InformationGet Traffic Video第三十八页，共四十二页。Conclusion and Future WorkVETRAC advantage:提供使用者在任何時間任何地點，都能運用WiFi連結，來提供資訊。補足GPS不能偵測到

21、的環境 如: 機場裡,隧道。VETRAC disadvantage:VETRAC並沒有支援安全機制(未來發展)關於技術理論方面，沒有太深入的介紹以WiFi在台灣目前的佈點率來說，此系統可能無法運作相對的，這是一項很有參考價值成果，對將來有意發展類似研究的，應該能給予很大的幫助。39第三十九页，共四十二页。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