云平台行车跟随系统的设计

王田，李洋，曾建电，王文华，苏耕民，许迪文，赖永炫（.华侨大学计算机科学与技术学院，福建厦门360；.厦门大学软件学院，福建厦门36005）

云平台行车跟随系统的设计

王田1，李洋1，曾建电1，王文华1，苏耕民1，许迪文1，赖永炫2
（1.华侨大学计算机科学与技术学院，福建厦门361021；2.厦门大学软件学院，福建厦门361005）

基于安卓手机系统，提出一种基于云平台的行车跟随方案.导向车客户端根据跟随算法判断自身行驶状态，在转弯时，发送转向信息至云服务器端，跟随车则下载该信息，并绘制出行车路径.实验结果表明：该行车跟随系统不仅精确性高，而且大大降低数据传输量，给用户带来极大的便利，是现有的全球定位导航系统（GPS）的有力补充.

行车跟随；全球定位导航系统；导向车；跟随车；跟随算法

全球定位系统（global position system，GPS）为导航带来了革命性的变化［1－2］，车辆导航是全球卫星定位系统的一个重要应用，随着GPS技术迅猛发展，相关的技术支持平台越来越多［3］.Qi等［4］介绍一种新型、高效的云计算计算模式，为用户提供良好的上网体验［5］.文献［6－8］在Android手机上安装GPS导航模块，提供车载导航服务，但未考虑一车识路，多车跟随的情况.王敏等［9］提出适合于交通网络拓扑结构变化的动态平行四边形匹配算法.谭宝成等［10］建立公共点分布密度和转换精度之间的关系以减少定位误差.马红皎［11］介绍一种嵌入式航位推算车载组合导航，提高导航的稳定性、可靠性和实时性.王田等［12］在无线传感网中，对移动的目标定位跟踪，为车辆跟随提供一种新的思路.以上研究提高了车载导航的精确度，但一车带路，多车跟随的问题仍未得到关注.Indhumathi等［13］通过实时上传导向车的地理位置到服务器为跟随车提供路，但是实时的上传和下载数据对网络稳定性要求苛刻，设备内存要求高，通用性不强［14］.文献［15－16］中均采用无线技术实现目标跟踪，但是蓝牙的通信距离是一个致命的瓶颈.基于此，本文提出基于云平台的行车跟随系统.

2 系统设计

2.1 系统模型

系统模型，如图1所示.图1中：Xi为经度；Yi为纬度.通过坐标点的线性求解，可得到车辆行驶斜率a，即为方向，行驶距离S.将所有的坐标点连通绘制，得到车辆的行驶路径L，路径的方向斜率变化率Δa，其正负表示车辆转弯的方向，大小表示车辆转弯的角度.

2.2 车辆状态的判定

根据坐标点的变化规律（图1），可求解出导向车的运动规律.导向车的行驶距离为

式中：初始状态T0的位置信息为（X0，Y0）；下一时刻T1的位置信息为（X1，Y1）.

本系统中，分别设置斜率变化率上限阀值Kmax、下限阀值Kmin和抖动次数，以降低系统误判率和漏判率.

2.3 车辆行为数据化

车辆行为有两种：直线状态到转向状态；转向状态到直线状态.在直线状态中，导向车发出“go straight！”消息给跟随车.同时，导向车按等距离将自身位置信息（X，Y）存入队列Q1.若在第i个Δt时间间隔中，行驶的距离Si小于初始额定值S，则此时刻的位置信息不入列.将此距离Si与下一时刻的行驶距离Si＋1进行叠加，直到叠加值大于等于S，则入列.每间隔Δt时间，导向车根据队列Q1中的数据，计算当前时刻车辆行驶方向斜率，存入队列Q2.由队列Q2的数据，计算相邻时刻导向车行驶方向的斜率的变化率Δa.

3 车辆跟随算法

3.1 车辆位置取点

结合车辆行驶的实际情况，在行驶过程中，车辆的速度并不固定，为保证跟随算法中判断转向的稳定性，应使车辆在行驶过程中所上传的位置信息点距离相等；否则，个别特异位置信息点会影响跟随算法对于转向的判断.具体有如下3个分析.

1）若Si≥S，则将此刻位置信息存入队列Q1中；否则，将此次Si累积到Si＋1中.

2）根据队列Q1的数据，计算行驶方向斜率，并存入队列Q2中，根据Q2计算斜率差Δa，若连续两次Kmin＜Δa＜Kmax，则判断导向车为转向状态，上传位置信息到云服务器，并发送转向消息给跟随车.

3）当跟随车收到走直线消息时，则无需下载位置信息，可直接走直线，直到收到转向消息，则下载位置信息，并通过客户端绘制成地图进行显示.

3.2 车辆跟随算法

车辆跟随算法的核心是将导向车的行驶区域模拟成一个直角坐标系，根据直角坐标系中的线性关系，可计算出一系列数据代表车辆行车过程中的特性.然后，根据这些计算结果，判定导向车的运行状态.当导向车在直线状态运行时，则只记录每一时刻的位置信息而不上传，直到被判定为转向时，则上传此刻位置信息到云服务器，并向跟随车发送转向消息.跟随车收到转向消息后，则下载位置信息，并将其同步到自身行驶路径中.

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时，方向斜率未发生变化，导向车按直线行驶；当时刻为8～9时，斜率变化较大，则判断导向车发生转向；当时刻为10时，斜率未发生变化，导向车恢复直线行驶.

5 实验结果

5.1 算法的对比

1）实时上传方案算法.导向车在行驶过程中实时上传自身的位置信息到云平台［13］，跟随车则实时从云平台下载，并将位置信息快速的加入到自身行车导航中.该方案设计简单，容易实现，且误差小，但是位置的信息上传下载次数多，对网络稳定性要求高，数据冗余大，浪费设备内存，不利于长期使用.

2）时间间隔算法.时间间隔是指在行驶的过程当中，导向车按照一定的时间间隔，将位置信息上传到云平台，再由跟随车下载.该算法设计简单易实现，相对于实时上传位置信息的方案，该算法的上传次数会减少，但是导航精确度和上传次数、时间间隔的大小有决定性关系.因此，最优时间间隔很难确定.

3）行车跟随算法.将导向车的行驶路径模拟成直角坐标系中的一条曲线，通过对曲线的几何分析，判断导向车的行驶状态.只有在导向车为转弯状态时才上传此时位置信息，否则只将部分位置信息存储在本地，进行相关的计算判断.该算法设计相对之前两个要复杂许多，但是上传次数降低到最少，网络稳定性要求不高，且精确度有保障.

5.2 实验对比法析

对理想状态算法、时间间隔算法及行车跟随算法3种不同算法进行模拟行车实验，得到不同算法下导向车的跟随车地图上转向口的个数（n1），如图2所示；上传位置信息的次数（n2）对比，如图3所示.

图2 转弯路口数有效性对比图Fig.2 Comparison of valid turnings

图3 上传次数对比Fig.3 Comparison of upload times

1）跟随车地图上的转向路口的个数对比（图2）.由图2可知：在理想状态下，能判断出每一个转向路口都为有效转向路口；行车跟随算法对于转向路口的判断出现一些误判，但能够覆盖所有有效转向路口.由于位置信息的抖动，造成行车跟随算法对于转向发生误判，其所判断导向车的转向路口数略微多于理想状态下所判断出的转向路口数，但其中有效路口数与理想状态持平，证明行车跟随算法能够有效地实现车辆间的跟随.

2）导向车位置信息上传次数比较（图3）.由图3可知：不同时间间隔算法需要连续上传自身的位置信息；行车跟随算法先分析导向车的行驶状态，在直线行驶时只监控而不上传位置信息.当判断出导向车转向时，才上传此刻的位置信息，大大减少上传次数，降低通信代价.

5.3 实际场景实验

通过MockLocation软件仿真模拟行进的车辆，模拟行车的地址位于福建厦门集美区，导向车以平均40km·h－1的速度在固定的路径上行驶，分别以2种方式上传数据：间隔2.5s直接上传；间隔2.5s跟随算法.导向车行驶路径图，如图4所示.图4中：圆点为实际上传点.

图4 导向车行驶路径图Fig.4 Preceding car′s route

6 结束语

研究车辆在行驶过程中一车带路，多车跟随情况下的解决方案.将车辆跟随系统进行直角坐标模拟，对车辆的转向判断进行研究分析，针对转向时车辆斜率变化特点，提出对车辆行驶转向判断的跟随算法.根据车辆跟随算法与理想状态下车辆转向路口数量和有效转向路口的覆盖率的对比，证明车辆跟随算法的准确性.再将车辆跟随算法与时间间隔算法过程中所产生的位置信息上传次数作对比，证明在该算法下，能够大量减少位置信息上传次数，体现了车辆跟随算法的有效性.

［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］ 李德毅，张天雷，黄立威.位置服务：接地气的云计算［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］.西安工业大学学报，2014，34（6）：504－510.

［11］ 马红皎，胡永辉，武建锋，等.嵌入式GPS／DR车载组合导航系统EKF算法软件设计［J］.时间频率学报，2015 （2）：64－70.

［12］ 王田，彭臻，陈永红，等.异构无线传感器网络对移动目标的连续跟踪［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－），男，副教授，博士，主要从事物联网技术、移动监控的研究.E－mail：wangtian＠hqu.edu.cn.

国家科技支撑计划（2015BAH16F00／F01／F02）；国家自然科学基金资助项目（61572206，61202468）；福建省自然科学基金计划资助项目（2014J01240）；华侨大学研究生科研创新能力培育计划资助项目（2014，2015年度）