Location Identification and Vehicle Tracking using VANET(VETRAC) Adviser: Ho-Ting Wu Speaker: Yi-Wei Sun Date: 2008/4/1

Outline Automotive Navigation 定位法 VETRAC(Vehicle Tracking) Conclusion Reference

Mobile Vehicle Tracking System Navigation Server Vehicle Tracking System Vehicle Tracking System Access Point – 1 … Access Point - n Wireless communication Wireless communication Client 1 Client 1 Client 1

Automotive Navigation 以wirless – mobile導航系統為基礎的radio frequency 使用digital map根據車輛位置，給與指南 並運用道路資訊的Database，給予使用者多條到達目的地的路徑指引。 最早實踐的Automotive Navigation Dead reckoning Digital map-matching +

Dead reckoning the process of estimating a global position 速度 方向 現在位置 時間 Wheel sensors Magnetic compass Digital map-matching

Dead reckoning 10:00 方向 09:30 Speed :60 km/h 車 09:00

GPS Dead reckoning問題 ! Wheel sensors Magnetic compass depend depend Wheel sensors Magnetic compass Digital map-matching ! 不規則的磁場!! GPS

GPS(Global Positioning System) 美國國防部與海空軍共同進行之計畫，供美軍所使用。 目前免費提供給民間使用其定位訊號 所有權屬於美國交通部 加入S/A(Selective Availability)效應干擾訊號﹐ 降低民用GPS接收機定位精確度。 95%的接收狀況精確度在直徑100公尺內。 5%的接收狀況在直徑300公尺內。 三點定位法

定位-三點定位法 A B C

定位-三點定位法 A B C

定位-三點定位法 Maximum likelihood method 取最小的一個 (x，y) rＡ rB A=(xＡ，yＡ) B=(xB，yB) C=(xC，yC) rC

定位-多點定位法 GPS GPS GPS B GPS GPS D C A GPS GPS GPS

定位-多點定位法 GPS GPS GPS B GPS GPS D C A GPS GPS GPS

定位-合作多點定位法 E A D D’ B B’ F C

802.11的定位技術 常用的有兩種 Radio Propagation Model Static Scene Analysis 不論是哪種，皆有兩個階段 Training phase Location Estimation phase

Training Phase 收集所有參考點所發出的訊號到各個training locations的訊號特徵。 3. 根據資料庫內容，建立定位模組。 4. 透過定位模組可以快速比對出一個未知位置的訊號樣本的最可能的位置 。

Location Estimation Phase 比對待定位的目標物體所接到的訊號樣本最可能出現在哪一個training locations上。 這需要大量的計算 因此就有各種定位演算法在其中 藉著計算來推出這未知位置可能的實際位置

表示此training locations的座標 流程圖 第二階段： Location Estimation phase (x1,y1 <ss1, ss2,……, ssn>1) 第一階段： Training phase <ss1, ss2,……, ssn> (x2,y2<ss1, ss2,……, ssn>2) 定位資料庫 定位模型 (xm,ym<ss1, ss2,……, ssn>m) (x,y) 表在此training locations上接收到的第i個參考點的訊號強度 表示此training locations的座標

Radio Propagation Model Training phase 建立訊號特徵 建立參考點與AP之間距離的對應函數 Location Estimation phase 根據Training phase所建立的對應函數 計算出參考點與AP之間的距離 利用定位演算法估計參考點可能的位置 演算法：三點定位法

Static Scene Analysis Training phase Location Estimation phase 建立Training set，存放在training locations上 建立參考點對AP的訊號特徵 Location Estimation phase 根據Training phase的訊號特徵 運用定位演算法估出可能位置 定位演算法： K-Nearest Neighbors algorithm Conditional Probability algorithm Simple Point Matching algorithm Bayesian Inference algorithm

Nearest Neighbor algorithm 在Training phase時會對每一個training locations在定位模組中建立一個Characteristic vector(特徵向量) Ci = <ci1, ci2,....,cin> Cij 代表在訓練位置i從參考點j收到的所有訊號強度的平均值 在Location Estimation phase時對於一個未知位置的目標物，會根據其接收到的訊號樣本S = <s1 ,s2 ,…,sn>，計算這個樣本到各個定位模組中的Characteristic vector的幾何距離 再根據幾何距離，找出具有最小幾何距離的 training locations作為定位的結果。

K-Nearest Neighbor algorithm 先根據Nearest Neighbor的Training phase中所計算的各個training locations與訊號樣本的幾何距離 從中挑出k個最小的training locations 接著平均這些位置的x座標與y座標 平均的結果，就作為估測的定位結果 而Nearest Neighbor只是k-Nearest Neighbor 在k=1時的特例

Conditional Probability algorithm 是以機率分佈表示每個training locations的特徵向量 訊號樣本S = <s1 ,s2 ,…,sn> 特徵向量Ci = <ci1, ci2,...,cin> 機率演算法則會去計算在各個training locations觀察到這個訊號樣本的機率，即 最後根據每一個training locations所計算出來的機率，找出擁有最大機率的training locations作為最後的定位。

Conditional Probability algorithm Example: 當環境中有三個參考點，而我們收到的訊號強度樣本為 S = <-66,-71,-74>如下圖 p2 p3 p1 因此訓練位置i收到的樣本S的機率為 p1 p2 p3 最後根據每一個training locations所計算出來的機率，找出擁有最大機率的training locations作為最後的定位。

Location Identification and Vehicle Tracking using VANET(VETRAC)

Introduction Vehicles tracking systems 是一種電子設備，安裝於車輛之上，供使用者自己會第三方track車輛的位置。 GPS就是現代既簡單又精確的Vehicles tracking系統。 GPS缺點: 無法偵測大型室內的地方 如：大學裡、機場、隧道 等 而WiFi就可以對這些地方給予tracking的服務。

Goal 事故 道路封閉 估計道路重開的時間 詢問或建議去繞道 AP 車

預設環境 - VETRAC 使用WiFi 預期移動的路徑上已佈滿AP Carriers收集資訊 當前的位置 目的地的位置或地標 也可以透過streaming traffic video知道道路的狀況

Motivation - VETRAC 在matching車輛資訊的訊息傳輸，要減小和避免congestion的發生。 提供給駕駛者一個安全又聰明的最佳路徑。 提供traffic video information讓駕駛知道詳細的道路狀況。 給予駕駛者會新進這城市的人，指定明確的地標。 藉由WiFi能不受限制的不間斷的提供通訊連結。

現實面的挑戰 High-speed mobility 車輛的移動只限制在車行道上 駕駛者出乎意料的行為 交通狀況中存在的變數

Interoperability 是指不同的計算機系統、網路、操作系統和應用程式一起工作並共享信息的能力。

VETRAC Interoperability Framework SINGLE HOP ACCESS Carrier GATEWAY MULTI HOP ACCESS A Mobile Nodes (WiFi/PDA) Base Station B Consumer WiFi Access Point

Some issues MANET raises several interesting issues in regard to data forwarding。 EX1: 當封閉的道路再度開啟時，carriers就不應該再傳送有關道路封閉的資訊出去。 EX2: 當交通停擺時， carriers可能會浪費過多的廣播，給所有會遇到交通停擺的車子。 VETRAC解法: 在carriers傳送事件訊息時，先過濾資訊。 當接收到訊息時， carriers會去看事件的Location與expiration time(e.g. 道路重開的時間) 假如超過規定的距離與時間，就discard此訊息

Some issues 網路congestion問題 VETRAC解法: 假設所有的carriers都傳送相同的訊息，連相鄰的carriers也都傳送同一份訊息時。 VETRAC解法: 在carriers中實做一個”redundant message”的過濾機制 當聽到一個跟自己正要送的訊息相同的訊息時，會移除自己的，並將他加到自己的訊息queue中的最後面。

Vehicle Tracking Setup Human Machine Interface Adaptive Front Lighting Application Curve Speed Lighting Application Route Planning Guidance Sensor Data Processing WiFi Reckoning MAP DATABASE Map Matching Address Match

VETRAC Functionality Frame-Work Client control Panel Database system Map Display System Client registration database Navigation Server Establish Connection Establish connection data Connection Establish Server Registration New client registration Landmark database Client current location Landmark data Location data Location Server Destination client’s location Traffic Server Client Location data Client location database Landmark Identification Traffic data Traffic information Positioning Server Update data Traffic video streaming Vehicle location information Traffic video information Vehicle Tracking System

Vehicle Traffic Navigate Lane 9 Lane 7 WiFi 車 車 WiFi WiFi Navigation Server WiFi WiFi WiFi 車 WiFi WiFi 車 WiFi WiFi B 車 A Communicate

VETRAC–Implementation and Result Map Display Current Location Destination Client Location Landmark Identification Get Traffic Information Get Traffic Video

Conclusion and Future Work VETRAC advantage: 提供使用者在任何時間任何地點，都能運用WiFi連結，來提供資訊。 補足GPS不能偵測到的環境 如: 機場裡,隧道。 VETRAC disadvantage: VETRAC並沒有支援安全機制(未來發展) 關於技術理論方面，沒有太深入的介紹 以WiFi在台灣目前的佈點率來說，此系統可能無法運作 相對的，這是一項很有參考價值成果，對將來有意發展類似研究的，應該能給予很大的幫助。

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 Position Location and Navigation Symposium , page 415-421 ,April 1996 【3】Terry Costlow , “WiFi Could Augment GPS” , IEEE Distributed system online , Vol. 5 , Issue no. 9, Page 1-2 , Sep 2004 【4】WHEEL SENSOR http://autorepair.about.com/library/glossary/bldef-883.htm 【5】Dead reckoning http://en.wikipedia.org/wiki/Dead_reckoning 【6】無線區域及個人網路(隨意及感測器網路之技術與應用) 曾煜棋 潘孟鉉 林志宇 編著 【7】 802.11 Rogue Devices的偵測與定位,趙守彬,林華君,2005

Thank you and Happy April Fool’s Day 完 End おわり Thank you and Happy April Fool’s Day