云平臺行車跟隨系統的設計

王田，李洋，曾建電，王文華，蘇耕民，許迪文，賴永炫（.華僑大學計算機科學與技術學院，福建廈門360；.廈門大學軟件學院，福建廈門36005）

云平臺行車跟隨系統的設計

王田1，李洋1，曾建電1，王文華1，蘇耕民1，許迪文1，賴永炫2
（1.華僑大學計算機科學與技術學院，福建廈門361021；2.廈門大學軟件學院，福建廈門361005）

基于安卓手機系統，提出一種基于云平臺的行車跟隨方案.導向車客戶端根據跟隨算法判斷自身行駛狀態(tài)，在轉彎時，發(fā)送轉向信息至云服務器端，跟隨車則下載該信息，并繪制出行車路徑.實驗結果表明：該行車跟隨系統不僅精確性高，而且大大降低數據傳輸量，給用戶帶來極大的便利，是現有的全球定位導航系統（GPS）的有力補充.

行車跟隨；全球定位導航系統；導向車；跟隨車；跟隨算法

全球定位系統（global position system，GPS）為導航帶來了革命性的變化［1－2］，車輛導航是全球衛(wèi)星定位系統的一個重要應用，隨著GPS技術迅猛發(fā)展，相關的技術支持平臺越來越多［3］.Qi等［4］介紹一種新型、高效的云計算計算模式，為用戶提供良好的上網體驗［5］.文獻［6－8］在Android手機上安裝GPS導航模塊，提供車載導航服務，但未考慮一車識路，多車跟隨的情況.王敏等［9］提出適合于交通網絡拓撲結構變化的動態(tài)平行四邊形匹配算法.譚寶成等［10］建立公共點分布密度和轉換精度之間的關系以減少定位誤差.馬紅皎［11］介紹一種嵌入式航位推算車載組合導航，提高導航的穩(wěn)定性、可靠性和實時性.王田等［12］在無線傳感網中，對移動的目標定位跟蹤，為車輛跟隨提供一種新的思路.以上研究提高了車載導航的精確度，但一車帶路，多車跟隨的問題仍未得到關注.Indhumathi等［13］通過實時上傳導向車的地理位置到服務器為跟隨車提供路，但是實時的上傳和下載數據對網絡穩(wěn)定性要求苛刻，設備內存要求高，通用性不強［14］.文獻［15－16］中均采用無線技術實現目標跟蹤，但是藍牙的通信距離是一個致命的瓶頸.基于此，本文提出基于云平臺的行車跟隨系統.

2 系統設計

2.1 系統模型

系統模型，如圖1所示.圖1中：Xi為經度；Yi為緯度.通過坐標點的線性求解，可得到車輛行駛斜率a，即為方向，行駛距離S.將所有的坐標點連通繪制，得到車輛的行駛路徑L，路徑的方向斜率變化率Δa，其正負表示車輛轉彎的方向，大小表示車輛轉彎的角度.

2.2 車輛狀態(tài)的判定

根據坐標點的變化規(guī)律（圖1），可求解出導向車的運動規(guī)律.導向車的行駛距離為

式中：初始狀態(tài)T0的位置信息為（X0，Y0）；下一時刻T1的位置信息為（X1，Y1）.

本系統中，分別設置斜率變化率上限閥值Kmax、下限閥值Kmin和抖動次數，以降低系統誤判率和漏判率.

2.3 車輛行為數據化

車輛行為有兩種：直線狀態(tài)到轉向狀態(tài)；轉向狀態(tài)到直線狀態(tài).在直線狀態(tài)中，導向車發(fā)出“go straight！”消息給跟隨車.同時，導向車按等距離將自身位置信息（X，Y）存入隊列Q1.若在第i個Δt時間間隔中，行駛的距離Si小于初始額定值S，則此時刻的位置信息不入列.將此距離Si與下一時刻的行駛距離Si＋1進行疊加，直到疊加值大于等于S，則入列.每間隔Δt時間，導向車根據隊列Q1中的數據，計算當前時刻車輛行駛方向斜率，存入隊列Q2.由隊列Q2的數據，計算相鄰時刻導向車行駛方向的斜率的變化率Δa.

3 車輛跟隨算法

3.1 車輛位置取點

結合車輛行駛的實際情況，在行駛過程中，車輛的速度并不固定，為保證跟隨算法中判斷轉向的穩(wěn)定性，應使車輛在行駛過程中所上傳的位置信息點距離相等；否則，個別特異位置信息點會影響跟隨算法對于轉向的判斷.具體有如下3個分析.

1）若Si≥S，則將此刻位置信息存入隊列Q1中；否則，將此次Si累積到Si＋1中.

2）根據隊列Q1的數據，計算行駛方向斜率，并存入隊列Q2中，根據Q2計算斜率差Δa，若連續(xù)兩次Kmin＜Δa＜Kmax，則判斷導向車為轉向狀態(tài)，上傳位置信息到云服務器，并發(fā)送轉向消息給跟隨車.

3）當跟隨車收到走直線消息時，則無需下載位置信息，可直接走直線，直到收到轉向消息，則下載位置信息，并通過客戶端繪制成地圖進行顯示.

3.2 車輛跟隨算法

車輛跟隨算法的核心是將導向車的行駛區(qū)域模擬成一個直角坐標系，根據直角坐標系中的線性關系，可計算出一系列數據代表車輛行車過程中的特性.然后，根據這些計算結果，判定導向車的運行狀態(tài).當導向車在直線狀態(tài)運行時，則只記錄每一時刻的位置信息而不上傳，直到被判定為轉向時，則上傳此刻位置信息到云服務器，并向跟隨車發(fā)送轉向消息.跟隨車收到轉向消息后，則下載位置信息，并將其同步到自身行駛路徑中.

Vehicles Tracking Algorithm

1：Set the fixed distance as S

2：for Every two adjacent points in Map do

3：if the distance＞S then push Queue1

4：end if

5：end for

6：for Every upload point do

7：compute and save the change of position

8：calculate the slope and get the slope changing rate asΔa

9：end for

10：for EveryΔado

11：ifΔa＜10%then judge as′Go Straight′

12：else

13：if two adjacentΔa＞＝10%＆＆Δa＜＝90%

then judge as′Turning′and upload point data.

14：end if

15：end if

16：end for

首先，對每一時刻導向車的行駛距離進行判斷，如果大于S，則將此時刻位置信息入隊Q1；然后，對隊列中的位置信息計算行車斜率.如果行車斜率的改變值Δa＜10%，則判斷為直線行駛；如果10%≤Δa≤90%，則判斷為正在轉彎.

4 跟隨算法模擬測試

將導向車位置信息模擬成直角坐標系中的坐標，并展示跟隨算法的核心計算點.不同時刻經緯度，如表1所示.表1中：i為每隔Δt時間段的時刻；Xi為經度；Yi為緯度.由表1的位置信息，可求出經緯變化差，如表2所示.表2中：ΔX為等時間段經度變化值；ΔY為等時間段緯度變化值.

表1 不同時刻經緯度Tab.1 Latitude and longitude in different time

表2 經緯變化差Tab.2 D－value of latitude and longitude

由經緯度變化差求出每一時刻導向車行駛方向斜率，如表3所示.表3中：ai為每一時間段導向車行駛方向斜率.由方向斜率求出方向斜率變化率Δa，如表4所示.

表3 方向斜率Tab.3 Slope of direction

表4 方向斜率變化Tab.4 Change percentage of direction slope

由表1～4可知：當時刻為1～7時，方向斜率未發(fā)生變化，導向車按直線行駛；當時刻為8～9時，斜率變化較大，則判斷導向車發(fā)生轉向；當時刻為10時，斜率未發(fā)生變化，導向車恢復直線行駛.

5 實驗結果

5.1 算法的對比

1）實時上傳方案算法.導向車在行駛過程中實時上傳自身的位置信息到云平臺［13］，跟隨車則實時從云平臺下載，并將位置信息快速的加入到自身行車導航中.該方案設計簡單，容易實現，且誤差小，但是位置的信息上傳下載次數多，對網絡穩(wěn)定性要求高，數據冗余大，浪費設備內存，不利于長期使用.

2）時間間隔算法.時間間隔是指在行駛的過程當中，導向車按照一定的時間間隔，將位置信息上傳到云平臺，再由跟隨車下載.該算法設計簡單易實現，相對于實時上傳位置信息的方案，該算法的上傳次數會減少，但是導航精確度和上傳次數、時間間隔的大小有決定性關系.因此，最優(yōu)時間間隔很難確定.

3）行車跟隨算法.將導向車的行駛路徑模擬成直角坐標系中的一條曲線，通過對曲線的幾何分析，判斷導向車的行駛狀態(tài).只有在導向車為轉彎狀態(tài)時才上傳此時位置信息，否則只將部分位置信息存儲在本地，進行相關的計算判斷.該算法設計相對之前兩個要復雜許多，但是上傳次數降低到最少，網絡穩(wěn)定性要求不高，且精確度有保障.

5.2 實驗對比法析

對理想狀態(tài)算法、時間間隔算法及行車跟隨算法3種不同算法進行模擬行車實驗，得到不同算法下導向車的跟隨車地圖上轉向口的個數（n1），如圖2所示；上傳位置信息的次數（n2）對比，如圖3所示.

圖2 轉彎路口數有效性對比圖Fig.2 Comparison of valid turnings

圖3 上傳次數對比Fig.3 Comparison of upload times

1）跟隨車地圖上的轉向路口的個數對比（圖2）.由圖2可知：在理想狀態(tài)下，能判斷出每一個轉向路口都為有效轉向路口；行車跟隨算法對于轉向路口的判斷出現一些誤判，但能夠覆蓋所有有效轉向路口.由于位置信息的抖動，造成行車跟隨算法對于轉向發(fā)生誤判，其所判斷導向車的轉向路口數略微多于理想狀態(tài)下所判斷出的轉向路口數，但其中有效路口數與理想狀態(tài)持平，證明行車跟隨算法能夠有效地實現車輛間的跟隨.

2）導向車位置信息上傳次數比較（圖3）.由圖3可知：不同時間間隔算法需要連續(xù)上傳自身的位置信息；行車跟隨算法先分析導向車的行駛狀態(tài)，在直線行駛時只監(jiān)控而不上傳位置信息.當判斷出導向車轉向時，才上傳此刻的位置信息，大大減少上傳次數，降低通信代價.

5.3 實際場景實驗

通過MockLocation軟件仿真模擬行進的車輛，模擬行車的地址位于福建廈門集美區(qū)，導向車以平均40km·h－1的速度在固定的路徑上行駛，分別以2種方式上傳數據：間隔2.5s直接上傳；間隔2.5s跟隨算法.導向車行駛路徑圖，如圖4所示.圖4中：圓點為實際上傳點.

圖4 導向車行駛路徑圖Fig.4 Preceding car′s route

6 結束語

研究車輛在行駛過程中一車帶路，多車跟隨情況下的解決方案.將車輛跟隨系統進行直角坐標模擬，對車輛的轉向判斷進行研究分析，針對轉向時車輛斜率變化特點，提出對車輛行駛轉向判斷的跟隨算法.根據車輛跟隨算法與理想狀態(tài)下車輛轉向路口數量和有效轉向路口的覆蓋率的對比，證明車輛跟隨算法的準確性.再將車輛跟隨算法與時間間隔算法過程中所產生的位置信息上傳次數作對比，證明在該算法下，能夠大量減少位置信息上傳次數，體現了車輛跟隨算法的有效性.

［1］ HUANG J Y，TSAI C H，HUANG S T.The next generation of GPS navigation systems［J］.Communications of the ACM，2012，55（3）：84－93.

［2］ LANDY J，LOPEZ T，NDEE N，et al.Finding directions to a good GPS system［M］.Heraklion：Springer International Publishing，2014：454－465.

［3］ VARLEY M C，FAIRWEATHER I H，AUGHEY R J.Validity and reliability of GPS for measuring instantaneous velocity during acceleration，deceleration，and constant motion［J］.Journal of Sports Sciences，2012，30（2）：121－127.

［4］ QI Han，GANI A.Research on mobile cloud computing：Review，trend and perspectives［C］∥Digital Information and Communication Technology and It′s Applications.Harrisburg：IEEE Press，2012：195－202.

［5］ 李德毅，張?zhí)炖祝S立威.位置服務：接地氣的云計算［J］.電子學報，2014，42（4）：786－790.

［6］ 曾薪夷.基于Android平臺的GPS導航系統的設計與實現［J］.計算機與現代化，2012（9）：225－228.

［7］ 任克強，李曉亮，謝斌.基于Android的手機導航系統設計與實驗［J］.實驗技術與管理，2014，31（5）：131－135.

［8］ HUANG Yi，HE Qian，WANG Yubin，et al.Research on global positioning system in mobile communication equipment based on android platform［C］∥International Conference on e－Education，e－Business and Information Management.Atlantis：Atlantis Press，2014：218－220.

［9］ 王敏，魏衡華，鮑遠律.GPS導航系統中的地圖匹配算法［J］.計算機工程，2012，38（14）：259－261.

［10］ 譚寶成，鄧子豪.GPS導航系統下坐標轉換及應用［J］.西安工業(yè)大學學報，2014，34（6）：504－510.

［11］ 馬紅皎，胡永輝，武建鋒，等.嵌入式GPS／DR車載組合導航系統EKF算法軟件設計［J］.時間頻率學報，2015 （2）：64－70.

［12］ 王田，彭臻，陳永紅，等.異構無線傳感器網絡對移動目標的連續(xù)跟蹤［J］.小型微型計算機系統，2015，36（3）：503－507.

［13］ INDHUMATHI R，MURUGESAN K S.Advanced vehicle tracking and display system［J］.Automation and Autonomous System，2015，7（2）：40－43.

［14］ IVANOV R.Real－time GPS track simplification algorithm for outdoor navigation of visually impaired［J］.Journal of Network and Computer Applications，2012，35（5）：1559－1567.

［15］ TAHAT A，SAID A，JAOUNI F，et al.Android－based universal vehicle diagnostic and tracking system［C］∥Consumer Electronics.Harrisburg：IEEE Press，2012：137－143.

［16］ PENG Zhen，WANG Tian，BHUIYAN M Z A，et al.Dependable cascading target tracking in heterogeneous mobile amera sensor networks［C］∥Algorithms and Architectures for Parallel Processing.Heraklion：Springer International Publishing，2015：531－540.

（責任編輯：陳志賢 英文審校：吳逢鐵）

Design on Cloud－Based Vehicle Tracking System
WANG Tian1，LI Yang1，ZENG Jiandian1，WANG Wenhua1，

SU Gengmin1，XU Diwen1，LAI Yongxuan2
（1.College of Computer Science and Technology，Huaqiao University，Xiamen 361021，China；2.College of Software，Xiamen University，Xiamen 361005，China）

Based on Android system，a driving following strategy is proposed on Cloud platform.The client of leading car judges the driving direction based on the designed following algorithm.When the leading car swerves，it would send the location information to a Cloud server.Then the client of following car downloads this information to draw the vehicle routing path.The experimental results show that this driving system has the advantages of high accuracy，low data transmission and convenience for users，which is good supplement for traditional GPS system.

vehicle tracking system；global position system；preceding car；following car；tracking algorithm

TP 393

A

1000－5013（2016）04－0481－05

10.11830／ISSN.1000－5013.201604018

2015－11－09

王田（1982－），男，副教授，博士，主要從事物聯網技術、移動監(jiān)控的研究.E－mail：wangtian＠hqu.edu.cn.

國家科技支撐計劃（2015BAH16F00／F01／F02）；國家自然科學基金資助項目（61572206，61202468）；福建省自然科學基金計劃資助項目（2014J01240）；華僑大學研究生科研創(chuàng)新能力培育計劃資助項目（2014，2015年度）