（模式识别与智能系统专业论文）大规模浮动车数据处理的研究与实现.pdf

摘要 摘要 随着我国经济的快速发展，汽车数量急剧增加，交通拥堵、事故和尾气污染 等交通问题日益严重。智能交通系统( i t s ) 是解决交通问题的有效途径，其各 功能都围绕着对基础交通信息的应用展开。因此，提供准确、实时的交通信息是 i t s 成功实施的重要前提和基本保证。浮动车数据( f c d ) 采集技术是一种近年 来发展起来的交通信息采集技术，具有部署成本低、覆盖范围广和实时性强等优 势。f c d 处理的过程就是把大量浮动车数据转换成道路交通信息，如旅行时间 和路段速度。本文对大规模f c d 处理的并行框架和关键算法进行了研究，并对 f c d 并行处理系统及f c d 实验平台进行了实现。论文的主要工作包括： 1 在k d 5 0 高性能计算机平台上，设计了大规模f c d 并行处理框架，对任务 分解与调度方法进行了研究，给出了改进的任务分解算法及动态调度方法， 并采用m a p r e d u c e 并行编程模型进行f c d 并行系统设计。 2 对增量匹配和全局匹配方法进行了比较，在分析f c d 误差影响因素的基础 上，提出了一种基于s v m 多分类器的f c d 地图匹配方法，给出了参数优化 选择的过程和f c d 地图匹配实验结果。 3 给出了基于区间平均速度的路段速度估算方法，通过实际跑车实验对该方法 的准确性进行了分析。针对路段速度信息缺失的情况，给出了简单滑动平均 的补偿方法。 4 以k d 5 0 高性能计算机为平台，实现了f c d 并行处理系统( 第2 版) 。通过 改进任务分配调度功能，实现了同时处理多个城市f c d 的交通数据处理中 心。为方便f c d 处理的算法研究，设计了基于可视化g i s 的f c d 实验平台。 关键词：浮动车数据，大规模数据，并行处理，地图匹配，速度推测 a b s t r a c t a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to fe c o n o m ya n du r b a n i z a t i o n ，t h en u m b e ro f v e h i c l e so nt h er o a d si n c r e a s e ss h a r p l y , w h i c hc a u s e st h et r a f f i cj a m s ，a c c i d e n t sa n d e n v i r o m e n tp o l l u t i o n i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ( i t s ) i sr e g a r d e da st h em o s t e f f e c t i v ew a yt os o l v et h i sp r o b l e m h o w e v e r , t h es u c c e s s f u l d e p l o y m e n t sa n d a p p l i c a t i o n so fi t sr e l yo nt h er e a l t i m ea n da c c u r a t et r a f f i ci n f o r m a t i o n f l o a t i n gc a r d a t a ( f c d ) t e c h n o l o g yi san e wa p p r o a c ho ft r a f f i ci n f o r m a t i o na c q u i r e m e n t i tc a n p r o v i d er e a l t i m et r a f f i ci n f o r m a t i o ns u c ha st r a v e lt i m ea n dr o a ds e c t i o ns p e e df o ra l a r g et r a f f i cr o a dn e t w o r kw i mal o wc o s t i nt h i sd i s s e r t a t i o n t h el a r g e r - s c a l ef c d p r o c e s s i n g ，i n c l u d i n g t a s kd e c o m p o s i t i o na n d d i s p a t c h , p a r a l l e lp r o g r a m m i n g f r a m e w o r k ，a n ds o m ek e ya l g o r i t h m s ，i ss t u d i e d t h em a i nw o r ko ft h i sd i s s e r t a t i o n i n c l u d e s ： 1 al a r g e - s c a l ef c d p a r a l l e lp r o c e s s i n gf r a m e w o r ki sd e s i g n e do nk d 5 0h p c ，a n d t h ed e f i n i t i o no fe a c hm o d u l ei sg i v e n a ni m p r o v e dm u l t i - t a s kd e c o m p o s i t i o na n d d y n a m i cd i s p a t c ha l g o r i t h mi sp r o p o s e d a n daf c ds y s t e md e s i g nb a s e do n m a p r e d u c ep r o g r a m m i n gm o d e li sa l s od e v e l o p e d 2 t h ei n c r e m e n t a la n dg l o b a lm a pm a t c h i n ga l g o r i t h m sa r ei n v e s t i g a t e d t h ef c d m a pm a t c h i n ge r r o r sa r ea n a l y z e d ，a n dt h e nan o v e lf c dm a pm a t c h i n ga l g o r i t h m i sp r o p o s e db a s e do ns v mm u l t i - c l a s s i f i e r s t h et r a i n i n gp r o c e s so fp a r a m e t e r s s e l e c t i o na n dc o m p a r i s o n so fr e s u l ta r eg i v e n 3 t h ee d g es p e e de s t i m a t i o nm e t h o db a s e do nt h ei n t e r v a l a v e r a g es p e e di s i n t r o d u c e d ，w h i c hi sa n a l y z e db yr e a lt e s t i n gc a rd a t a as i m p l em o v i n ga v e r a g e m e t h o do fp r e d i c t i o ni sg i v e nf o rr e s t o r i n gt h em i s s i n gs p e e dd a t ao fs o m ee d g e s at r a v e lt i m ec o m p u t i n gm e t h o di sa l s og i v e n 4 af c d p a r a l l e lp r o c e s s i n gs y s t e mi si m p l e m e n t e db a s e do nk d - 5 0h p c at r a f f i c d a t ap r o c e s s i n gc e n t e ri sd e v e l o p e di nw h i c hm u l t i c i t yf c dc a nb ep r o c e s s e d s i m u l t a n e o u s l y t h ef c de x p e r i m e n tp l a t f o r mu s i n gv i s u a lg i st e c h n o l o g yi s i m p l e m e n t e di no r d e rt or e s e a r c ha n dd e v e l o pt h ef c dp r o c e s s i n ga l g o r i t h mi na m o r ec o n v i n i e n tw a y k e yw o r d s ：f l o a t i n gc a rd a t a ，l a r g e - s c a l ed a t a ，p a r a l l e lp r o c e s s i n g ，m 印m a t c h i n g ， s p e e de s t i m a t i o n i i i 中国科学技术大学学位论文相关声明 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：避 签字日期：驯。l f 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名：导师签名： 签字日期：) 咿f 讲签字日期： 。( 。 镅少 ， 。 第1 章绪论 第1 章绪论 1 1 研究背景和意义 随着经济的发展与城市化进程的不断加速，道路汽车数量急剧增加，交通拥 堵日益严重，已经成为制约经济高速发展的瓶颈。 在国外，每年因交通拥堵造成的经济损失巨大。美国德州运输研究所最近的 一项调查显示，美国每年因交通拥堵与事故造成的经济损失在5 0 0 亿美元左右。 其中，十几个主要城市每年分别损失了1 0 亿美元以上，并且这个数字正呈现逐 年上升趋势。还有研究显示，美国每年因交通拥堵浪费多达1 4 3 5 亿升燃料和2 7 亿工作小时，由此造成的环境污染也十分严重。据估计，欧洲每年交通拥挤造成 的经济损失约5 0 0 0 亿欧元，日本东京市交通拥挤造成的经济损失在1 2 3 ，0 0 0 亿 日元以上( 王媛，2 0 0 9 ) 。 我国的经济正处于高速发展阶段，城市化进程日益加快，包括拥堵、事故和 污染等在内的交通问题将非常严重( 许彦等，2 0 0 7 ) 。据统计，在首都北京，2 0 0 8 年汽车保有量达到3 5 0 万辆，并以每天1 0 0 0 辆的速度增加；在上海，2 0 0 6 年的 汽车保有量突破了2 4 3 万辆，并且以每天5 0 0 辆的速度增加：广州、深圳等大城 市的汽车保有量也早以超过1 0 0 万辆。在道路交通工具高速发展的同时，交通堵 塞和大气污染变得日益严重。据测算，仅2 0 0 3 年一年全国因交通拥堵造成的经 济损失已达到约2 3 0 0 亿人民币，占全年g d p 的2 。 随着交通拥堵、尾气污染和交通事故等交通问题逐渐被人们所认识，各个国 家逐步开展了相关研究工作。经过长期对交通问题的思考与研究，发达国家已从 修建交通基础设施、扩大路网规模来缓解日益增长的交通需求，过渡到了通过使 用技术手段改造现有交通运输系统与管理体系，提高路网整体通行效率和服务水 平。 随着研究逐步深入，智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，i t s ) 应运而生，它是将先进的计算机控制技术、信息技术、人工智能与系统工程技术 结合，应用于交通运输系统的管理体系中，从而建立起大范围实时、准确、高效 的交通运输管理系统。i t s 为解决交通问题提供了全新的方法，是目前世界交通 运输领域研究的前沿课题。i t s 是科学技术发展的必然产物，是信息化社会发展 与世界经济发展的必然要求，是目前国际公认的解决交通拥挤、改善行车安全、 提高交通运输效率、减少空气污染等的最佳途径( 杨兆升，2 0 0 4 ) 。美国研究机 构将i t s 分为以下几部分：先进的交通管理系统( a t m s ) 、先进的旅行者信息 系统( a t i s ) 、先进的公共交通运输系统( a p t s ) 、商用车辆运营系统( c v o s ) 、 第1 章绪论 先进的车辆控制系统( a v c s ) 、自动公路系统( a h s ) 、先进的乡村运输系统 ( a l 玎s ) 。a t m s 和a t i s 属于整个i t s 体系的核心部分，真正反映了城市整体 智能交通的发展水平。 i t s 的各部分功能都是围绕交通信息的应用而展开，交通信息的采集质量对 i t s 系统可靠、有效的运作起着重要作用。因此，获取实时、准确、全面、有效 的城市道路交通信息是i t s 成功实施的重要前提和基本保障( 郭磷，2 0 0 7 ) 。并 且，这也是影响i t s 进一步发展的瓶颈问题。目前，常用的交通数据采集方法大 致分为人工采集技术和自动采集技术两种。人工采集是通过人的参与进行实地交 通调查，对采集的数据进行人工统计，获取交通流参数。因此，人工采集并不适 合实时、大范围的应用。感应线圈、红外、射频和视频交通检测技术属于自动采 集技术，虽然能够自动获得路段的车辆通行信息，但是存在着覆盖范围小、投资 昂贵、信息局部性、对路面产生破坏等缺点。浮动车数据( f l o a t i n gc a rd a t a ， 下文简称f c d ) 采集技术是近几年发展起来的具有广阔前景的交通信息采集技 术，它具有覆盖范围大、部署成本低、信息实时性强等优点，能够实时、准确地 得到整个城市范围的动态交通信息。 合肥作为安徽省省会，在国家“中部崛起”的战略环境下，通过国家创新性 试点城市建设，正在逐步加强包括智能交通系统在内的交通基础设施建设。从 2 0 0 5 年开始，通过与德国宇航局等国外机构及国内科研单位、高校的合作，在 “中国百万人口城市交通系统”项目背景下，引进了城市f c d 浮动车交通信息 采集系统，进行了全城试点。经过近两年的规划与实施，目前在全城运营的浮动 车数量约为6 0 0 辆，并且会在几年内逐步增加至1 2 0 0 0 辆左右。本文在此背景下 进行研究，依托于安徽“十一五”科技攻关重点项目：城市交通一体化集成管控 平台( 0 7 0 1 0 2 0 2 0 4 9 ) 。 1 2f c d 交通信息采集系统 交通信息采集系统是构建智能交通应用的基础平台，f c d 采集技术作为一 种移动检测器技术，是目前交通信息采集的研究热点。它综合了g p s 定位、无 线通信、数据存储和地理信息系统等先进技术，利用行驶在道路上的装有定位和 无线通信设备的浮动车，实时采集交通数据，通过对采集到的数据进行处理来提 取交通信息，建立基于实时交通信息的调度管理、动态诱导和出行服务等应用， 达到缓解交通拥堵、改善道路服务水平的目的( l iq i n g q u a n ，2 0 0 6 ) 。 f c d 采集系统采集浮动车的g p s 定位数据，行驶方向角，时间，车辆编号 信息。它可以获得路段速度、行程时间等交通流参数，并且具有很好的扩展性和 经济性。城市范围内部署大量浮动车，通过它们不断向交通中心定时发送车辆经 2 第1 章绪论 纬度和时间信息，估算车流速度，就可以得到城市实时交通速度信息( s c h a e f e re t a l ，2 0 0 2 ) 。相对于感应线圈、视频检测等固定采集系统来说，f c d 采集系统有 如下优点： 1 ) 部署成本低。相对感应线圈等采集设备来说，f c d 采集系统不用对路面 进行施工和后期保养、维护，因为是装置在移动的车辆中，也不用进行基础设施 的建设，并且f c d 采集设备共享了出租车调度系统的设施，这样大大减少了系 统部署投入的成本。 2 ) 覆盖范围广。由于固定式检测器只能检测一个点的信息，加上成本的考 虑，很难做到全城覆盖。f c d 采集一般用出租车作为采集源，这类交通工具数 量多，每年行驶里程数很大，基本能够覆盖整个城市路网。 3 ) 采集数据的信息量丰富，数据精度高。根据采集到的车辆行驶数据，能 够估算出路段的行驶时间，交通速度信息。 4 ) 实时性高。可以对交通信息进行实时自动采集，受时段等限制少。 5 ) 系统鲁棒性强。浮动车不停的在路网中穿梭，系统采集的交通信息是所 有样本共同的贡献，因此一个检测器发生故障对系统总体的准确度产生的影响不 大，系统能够稳定运行。 6 ) 可扩展性强。由于采集到的交通信息的质量和浮动车数有关。可以通过 增加浮动车的方式，来提高城市交通信息采集的准确性和及时性。 1 3 国内外研究进展 交通信息是智能交通系统的数据基础，它分为静态交通信息和动态交通信息 两种。静态交通信息包括路网结构、交通设施部署等，这些信息随时间变化小。 动态交通信息是指实时采集到的交通信息，比如道路交通流速度，车辆实时位置 等随时间变化的信息。f c d 所采集的就是动态交通信息，国内外对f c d 技术的 理论进行了研究，并致力于在此基础上开发出有效可用的f c d 采集系统。下面 介绍国内外f c d 系统的研究现状及f c d 相关技术理论的发展趋势。 1 3 1f c d 系统的研发现状 目前，日本、欧洲、美国在智能交通领域的研究水平最高。他们对于交通信 息平台的研究起步较早，由国家层面推进，联合各部门、工商团体和科研机构共 同完成研究项目，因而他们的研究、开发、系统实施的技术水平都处于世界领先 地位( 杨兆升，2 0 0 4 ) 。 日本早在7 0 年代中就开始了智能交通信息平台的开发，最初正式投入使用 第1 章绪论 的有汽车综合控制系统c a c s ( c o m p r e h e n s i v ea u t o m o b i l ec o n t r o ls y s t e m s ) ，该 系统为后面发展的各项成果提供了基础。8 0 年代中期，通产省的汽车行驶电子 技术协会( j s k ) 设立，更深入的研究交通信息导航和路车之间的无线通信。日 本在1 9 9 0 年建立了世界上第一个道路车辆信息通信系统( v e h i c l ei n f o r m a t i o n & c o m m u n i c a t i o ns y s t e m ，v i c s ) ，成为日本出行者信息系统的核心。v i c s 由道路 上的交通流检测器和车里的发射天线将动态交通信息传输给信息中心，经过处理 后通过调频等手段将诱导信息传送给车辆，结合车载g p s 设备的定位功能，达 到引导车辆更好完成出行的目标( n a g a o k a ，1 9 9 9 ) 。在1 9 9 9 至2 0 0 2 年间，j s k 调研了浮动车收集交通数据的可行性，并在横滨设立了实验项目，将g p s 和无 线通信结合应用到交通信息采集系统中。由于当时的g p s 设备成本和通信代价 都较大，又不太被民众广泛使用，如何降低投入成本和保护隐私成为研究的主要 问题。互联网i t s 联盟( i n t e m e ti t sc o n s o r t i u m ) 也从2 0 0 2 年1 0 月开始进行相 关研究，由丰田及其他合作伙伴共同参与。其中j s k 的角色是支持f c d 标准化 的发展( i v s o u r c e ，2 0 0 3 ) 。 欧洲从1 9 8 6 年开始投入对智能交通的研究，在f c d 采集系统的开发和实施 上走在了世界前列。1 9 8 8 年开始，英国的t r a f f i cm a s t e r 系统由私人公司运营， 收集和处理交通数据，以提供交通信息服务，该系统中f c d 主要作为交通信息 的补充，此外，英国的r o a d t r a f f i c a d v i s o r 项目也对基于车辆通信的信息采集进 行了研究。瑞士的o p t i s ( o p t i m i z e d t r a f f i ci ns w e d e n ) 工程由政府和汽车制造 商共同投资，建立成本合理的出行信息的数据采集方法，从2 0 0 0 年开始的六年 间共投资2 亿多美元，主要达成三个目标：建立处理f c d 的服务器、通过实地 试验校正仿真实验和为未来的应用确定计划。德国宇航中心交通研究所开发了基 于出租车的f c d 采集系统，在全国进行的实验涵盖了2 3 0 0 辆出租车，因为使用 的是出租车管理系统的数据源，所以没有额外的通信费用产生，每辆车的采集间 隔为1 5 1 2 0 秒一次数据发送，一年大约有1 2 亿条数据。这一系统不受雨雪天 气影响，采集效果相当好。同时，d d g 公司使用了4 0 0 0 个路面交通传感器和 2 5 0 0 0 辆采集车( 来自宝马和大众) ，系统设计为每天每辆车发送三条记录，信 息中心每天总共处理3 0 m 数据( f a s t e n r a t h ，1 9 9 7 ) 。m a n n e s m a n 公司使用1 0 0 0 辆车对f c d 技术进行了实验，计算出需要使用8 0 0 0 1 0 0 0 0 辆探测车来检测出 9 0 的交通状况。g e d a s 与大众集团合作g e d a sw a y f l o w 计划，采集行程时间和 中心城区的交通状况，该计划在莱茵河地区进行了采集试验。此外，荷兰、法国 等国家都先后做了f c d 系统的研究和试验( i v s o u r c e ，2 0 0 3 ) 。 美国的起步也比较早，从6 0 年代末就开始了智能交通系统方面的研究，当 时研究的是电子路线引导系统( e l e c t r o n i cr o u t eg u i d a n c es y s t e m ，e r g s ) 。但随 4 第1 章绪论 后很长一段时间在交通信息化和智能化方面没有进展，直到8 0 年代末，由于受 到欧日i t s 进展的触动，加上冷战结束军转民的需求，由i t sa m e r i c a 组织确定 了运输系统开发与实施框架计划。到2 l 世纪，已经建立起了车队管理、公交出 行、电子收费和交通需求管理等系统。比较有代表性的有：美国t r a v t e k 导航 动态交通信息平台；明尼苏达州与福特研究机构业合作开发了一套f c d 系统， 用以减少行程时间，提高事件检测精度和道路服务水平；佛罗里达州在政府部门 的支持下也建立了f c d 系统的实验，联邦公路局( f h w a ) 设想该计划能够作 为私人浮动车技术发展的温床；v e h i c l ei n f r a s t r u c t u r ei n i t i a t i v e ( v i i ) 联盟也对 f c d 进行了研究，建立了一系列基于i n t e l l i d r i v e 踟( i n t e l l i d r i v e u s a o r g ) 的应用 ( i v s o u r c e ，2 0 0 3 ) 。 国内目前只有少数城市实现了大规模车载g p s 设备用于交通信息采集，f c d 数据采集系统尚处在研发和小范围试用阶段。宁波市部署了我国第一个f c d 应 用的商业项目( w a n gj i a - j i e ，2 0 0 5 ) 。北京于2 0 0 8 年浮动车超过2 0 0 0 0 辆，构建 的f c d 系统在北京奥运会期间为城市道路实时交通监测起到了重要作用( w a n g z u y u n ，2 0 0 8 ) 。另外，上海、广东、厦门、杭州等均开展了对f c d 系统的研究 和试用。 1 3 2f c d 技术理论的研究趋势 目前f c d 相关技术的理论研究主要集中在系统架构、实现步骤以及数据的 扩展应用等方面( 王嫒，2 0 0 9 ) 。一些学者对f c d 系统架构实现、系统开发进行 过研究( 叶杨，2 0 0 9 ；张周强，2 0 0 8 ；张存保，2 0 0 6 ；张永强，2 0 0 5 ；s c h a e f e re t a l ，2 0 0 2 ) 。郭磷( 2 0 0 7 ) 对基于信息融合的交通信息采集进行了研究，并给出 了f c d 采集系统的准确度实验。z h a n ge ta l ( 2 0 0 9 ) 与刘彦廷( 2 0 0 6 ) 对长间隔 数据的地图匹配分别进行研究，开发出了有效的匹配算法。庞昊( 2 0 0 9 ) 对交通 动态诱导进行了研究，并对f c d 处理的关键算法进行了研究。王嫒( 2 0 0 9 ) 对 大范围战略交通协调控制系统的关键技术进行了研究，给出了对于手机浮动车的 地图匹配、行程时间估计的方法。g u og e n g q ie ta l ( 2 0 0 9 ) 使用f c d 作为输入 数据构建概率神经网络分类器，将它用于识别城市道路交通状态，该研究成果已 经成功集成入广州i t s 公共信息服务平台中。 关于f c d 大规模处理的研究不是很多。l uw e ie ta l ( 2 0 0 6 ) 以北京f c d 处 理为背景，研究了如何使用分布式处理系统来降低f c d 处理的时间延误。陈锋 ( 2 0 0 9 ) 对f c d 并行处理进行了研究，并给出了在高性能计算机上的系统实现 和性能比较。随着f c d 技术的发展、g p s 设备的普及，数据量会越来越多，如 何实时处理f c d 需要进行深入研究与开发。另一方面，f c d 数据处理中的关键 第1 章绪论 技术，如地图匹配和行驶时间、路段速度推测的方法，准确度如何提高，算法能 否实时处理、低采样率的f c d 地图匹配( z h a n ge ta l ，2 0 0 9 ) 等方面，也需要进 行更多研究。 1 4 研究目的与研究内容 f c d 处理的一般流程是串行化，这一流程难以满足大规模f c d 的处理需求。 以目前合肥的f c d 系统来估算，处理系统的吞吐量为3 6 0 0 条记录分钟，而北 京的f c d 数据量比合肥大一个数量级，以一般的串行流程来处理这些f c d 难以 满足实时性的要求。因此，需要对f c d 处理流程进行优化设计，对相关的处理 算法进行进一步的深入研究。 本文研究内容包括：为了实时处理大规模f c d ，基于k d 5 0 高性能计算机 体系结构，研究f c d 并行处理的框架和流程，并对并行处理的关键算法任务 分解与调度展开研究；针对f c d 的数据与个人导航设备数据有较大的差别，一 般经典的g p s 导航地图匹配算法可能得不到好的匹配效果，本文研究适合于 f c d 的地图匹配算法；为了得到整合后的大范围实时交通信息，论文对路段行 程与速度估计进行研究。 1 5 论文组织结构 本文以智能交通系统中的实时交通信息采集为研究背景，对基于浮动车采集 的数据处理进行研究，使用并行处理流程来解决大规模数据处理的实时性问题， 并且对处理算法中的地图匹配和交通流参数估测进行了深入研究，分别提出了改 进的方法，并且将提出的方法与并行处理框架结合，成功运用于k d 5 0 高性能 计算机上。同时开发了f c d 处理算法的实验平台，为算法的验证提供支持。论 文其余各章组织结构如下： 第二章f c d 并行处理及任务分分配。本章首先阐述了并行处理f c d 的必 要性，介绍了k d 5 0 高性能计算机。设计了k d 5 0 平台下的f c d 并行处理框架， 该框架包含数据预处理、任务分解与调度、地图匹配和旅行时间估计等。并对实 现并行处理的关键技术任务分配进行了研究，给出了实验与结果分析。最后， 给出了一种基于m a p r e d u c e 并行编程框架的系统设计方案。 第三章f c d 地图匹配。本章是论文的重点内容之一，地图匹配是f c d 数 据处理的重要过程，对交通信息的处理结果有很大影响。首先给出了问题定义， 并对相关研究进行了深入研究与分析，针对f c d 地图匹配的特点，提出了基于 s v m 多分类器的f c d 地图匹配算法，描述了训练过程，并通过实验论证了该方 6 第1 章绪论 法的有效性。 第四章路段速度与旅行时间推测。本章通过地图匹配得到的匹配结果，给 出了基于区间平均速度的路段速度与旅行时间估算方法，并给出了实验结果与分 析。针对f c d 在计算时段内某些道路上的缺失问题，给出了一种基于回归预测 的交通信息补偿策略。 第五章f c d 并行处理系统与f c d 实验平台的实现。本章实现了基于k d 一5 0 高性能计算机的并行f c d 处理系统( 第2 版) ，较第一版运行更加稳定，且 功能更加完善。基于改进的任务分配方法，实现了多城市f c d 同时处理的f c d 数据处理中心。针对f c d 处理核心算法的难于调试的问题，开发了f c d 实验平 厶 口。 第六章总结与展望。对全文内容进行总结并指出了今后研究方向。 7 第2 章f c d 并行处理与任务分配 第2 章f c d 并行处理及任务分配 随着f c d 数据规模越来越大，将f c d 处理过程并行化是提高f c d 处理实 时性的有效途径。关于f c d 并行处理的研究尚处于起步阶段，文献( l uw e ie ta l ， 2 0 0 6 ) 为了减少f c d 处理的延误提出了一种使用网格划分任务数据进行分布式 处理的方案，由若干台p c 平衡f c d 处理负载，但此种任务分配方法没有考虑 跨网格的问题。目前，对于并行处理的关键技术：任务分配和调度的研究较少( 陈 锋，2 0 0 9 ；庞吴，2 0 0 9 ) 。本章将基于k d 5 0 高性能计算平台，对f c d 并行处 理框架及其关键技术进行研究和设计。 本章首先对一般f c d 系统结构及处理流程进行介绍，然后就大规模f c d 实 时处理的需求，基于k d 5 0 高性能计算机平台，设计一种任务并行处理的框架。 并行处理的主要思想是将要处理的f c d 任务分解成若干任务块，然后通过调度 程序将任务块分配到各个空闲计算单元，以达到任务块间并行处理、加快总任务 处理速度的目标。为了实现并行流程，任务分解和调度是重要的步骤，因此本章 也对相关算法作了研究，并给出实验结果和分析。最后，本章针对f c d 并行处 理的任务需求，基于m a p r e d u c e 分布式计算模型给出了一种切实可行的系统设 计方案。 2 1f c d 系统结构与处理流程 浮动车数据( f l o a t i n gc a rd a t a ，f c d ) 采集技术是一种移动型交通检测器的 应用技术，它是现代无线通信技术、地理定位技术( 如全球定位系统，g p s ) 和 计算机与数据库系统技术等的结合。通过探测浮动车的运行产生的数据，可以获 得行驶速度和行驶时间等路段的交通流参数，具有很好的扩展性和经济性。本节 将介绍f c d 系统结构和处理流程。 2 1 1f c d 采集系统的结构 装有g p s 终端设备的出租车分布在整个城市路网上，组成了一个大规模的 移动检测器网络，这些移动交通检测器定时向交通处理中心发送基础数据( 包含 g p s 定位信息、速度时间信息、车辆编号等) 。处理中心按照先进先出原则实时 处理这些数据，通过地图匹配、速度估计等算法对采集的基础数据进行计算处理， 从而实现大规模城市道路交通速度信息的采集。关于f c d 采集系统更多硬件技 术细节可以参考文献( s c h a e f e r e ta l ，2 0 0 2 ；殷伟等，2 0 0 8 ) 等。 9 第2 章f c d 井行处理与任务分配 图2 1f c d 交通数据采集与处理架构 f c d 交通数据采集系统主要由车载定位设备、无线通信网络和交通信息处 理中心等组成( 如图21 所示) 。车载设备主要包括g p s 全球定位模块、无线通 信模块等，g p s 模块接收定位卫星信号根掘定位算法得出车辆的经纬度坐标和瞬 时速度，然后车辆坐杯、速度、记录时暗】、设各状态等信息由无线通信模块负责 传送至交通处理中心，同时可以接收交通信息中心发送的指令。无线通信网络由 通信运营商提供，包括通信基站与数据交换设备等，目前在中国普遍使用的是通 用分组无线服务技术( g p r s ) 或者增强型数据速率g s m 演进技术( e d g e ) ， 同时第三代移动通信技术( 3 g ) 也逐渐在中国铺开应用。交通信息处理中心主 要由f c d 采集服务器、数据处理服务器和交通信息应用服务器等组成。f c d 采 集和数据处理服务器负责将原始的f c d 处理成易丁_ _ 理解的交通流参数，是交通 数据平台的关键部分。交通信息应用服务器负责将处理的结果发布给用户同时 可以进一步提供基于这些实时交通信息的应用。 车载设备向交通信息处理中心传输的f c d 包含：车辆i d 号、经纬度坐标， 瞬时速度、方向、已录时间、设备状态等字段。交通信息处理巾心对这些信息进 行采集存储、预处理结合电子地图利用相应的处理算法对交通参数如速度、行 程时间等进行估计，以得到整个路网实时的交通状态信息。 2i2f c d 处理基本流程 f c d 数据记录了车辆当前的位置、速度等信息。本文的研究数据基于在台 肥和北京的城市f c d 数据采集系统的数据源，该系统单条f c d 数据记录的格式 如表2 1 所示。 第2 章f c d 并行处理与任务分百己 表2 1 单条f c d 记录的字段格式 r e cl o n g i t u d ed o u b l eg p s 记录的经度 r e co i r e c t i o n i n t e g e r ! f = 辆当前方向 电子地图数据是地图匹配需要用到的重要数据它是车辆所在区域的道路与 交叉口的空l 训位置信息。电子地图数据包括了道路、道路方向、交叉口连接等信 息其g i s 基础数掘结构由点和弧线组成，为1 ：2 5 0 0 比例的地图数据。平面拓 扑展示如图22 。 图2 2 电子地图数据的展现 f c d 处理的基本流程( 图2 3 ) 包括电子地图数据预处理、f c d ( o p s 数据) 预处理、f c d 地图匹配、行车路线推测、路段旅行时叫平均速度推测、交通信 息整台发布等模块组成( 陈锋，2 0 0 9 ) 。 围2 3 一股f c d 处理流程 第2 章f c d 并行处理与任务分配 f c d 处理流程中，首先是预处理。包括地图数据和f c d 预处理两部分。地 图数据预处理就是将地图数据读入内存并且可以根据后续算法需求得到一些预 处理信息，比如路网的拓扑结构、连通性、前后路段，作为地图匹配或路径搜索 算法的准备数据，也有将路网进行网格化划分，预先保存好每个网格中的路段编 号，这样以后的算法中对路段可以进行局部查找，加快算法速度。此预处理是离 线完成，只需要做一次。而f c d 的预处理是在线进行的，并且每个数据都会运 行一次，它主要是把不符合条件的、明显数据的、设备出错导致的无效数据剔除。 地图匹配是f c d 处理的核心步骤，对最后产生的交通信息结果的准确度影响最 大。它是将f c d 记录匹配到电子地图路网上的过程，并且得出每一辆探测车的 行车轨迹。得到了地图匹配的结果后，通过行车路线推测和行程时间与速度推测 过程，得到需要的交通流参数。将推测结果进行储存，加入一部分历史数据，整 合后进行交通信息发布。 2 2 大规模f c d 并行处理的必要性 为了得到城市范围的实时交通信息，需要对大范围大规模采集数据进行实时 处理和分析，以保证交通信息及时发布。北京市区交通路网包括2 万多个交叉1 ：3 ， 9 万多路段节点，共有约1 4 万条路段，目前装有车载g p s 的出租车已经达到了 2 万多辆，而合肥不久前部署f c d 系统，目前约为6 0 0 辆车，但其定位信息发 送间隔比较短，目前为每辆车l o 秒一次，数据量也较大。据估算，目前合肥的 f c d 系统需要处理的数据量约在3 6 0 0 条记录分钟，而北京的f c d 系统的数据 量就比合肥大一个数量级，特别在高峰时间，能够达到约2 0 0 0 0 条记录分钟。 使用一般的串行流程来处理这些f c d 难以满足实时性要求。因此，必须优化f c d 处理流程的设计，将其并行化。 我们采用k d 5 0 高性能计算机作为f c d 处理平台，实现f c d 的并行处理。 下文将介绍k d 5 0 i 计算机的系统结构。 2 3k d 5 0 i e 高性能计算机 k d 5 0 i 是由中国科学技术大学、国家高性能计算中心和中科院计算所合作 研发的高性能计算机系统，是我国首台采用自主知识产权处理器的高性能计算 机，集成了3 3 6 个主频为7 5 0 m h z 的龙芯2 f 处理器，理论峰值计算能力为1 0 0 8 万亿次。k d 5 0 i 在板上机群、高密度计算结点、轻量操作系统等关键技术上取 得突破，具有低占地、低功耗、低成本、高计算密度等特点( 张俊霞等，2 0 0 8 ) 。 1 2 第2 章f c d 并行处理0 任井分配 照 圈2 4 k d 5 0 i 帆柜 整套系统集成在一个机柜中( 图24 ) ，菇2 8 个计算节点，每个节点使用l u 空i h j 每个计算节点包含1 2 个处理单元，通过千兆以太网卡日连。主控服务器为 曙光服务嚣，机柜里节点问采用华为4 8 端口千兆交换机，主控服务器与机柜交 换机之f n j 万兆互联，系统结构如图25 所示。 * - 。t * n 口童目目目 i l 口 ip h * _ 匹三三三j i i ：卫 n t n 一 _ _ _ 崮“崮由毒索由 l 、| 1 、 一| _ ：l ： 、 l 盟| | 品l 、 j fi i = l 1 i = _ 1 = l 、= l ，。；二、；l 、 n - 】、i ：c = | 、未、 l 品j 二i r 向m阿r 钾f l = 一l 刖l 型l * j l _ l 生 图2 5k d 5 0 一i 系统结构 k d 一5 0 一i e ( 后文均简称k d 一5 0 ) 是k d - 5 0 i 的增强版本，主要改进了i f 算 甘点的设汁，使用了纠错能力更强的存储芯片和速度更快的交换芯片，整体性能 有较大提升，运行更加稳定可靠，面向行业应州领域( 鹿吴，2 0 0 9 ) 。与k d 5 0 1 相比，它增加到7 台曙光服务器，共有1 2 个计算节点，每个节点1 2 个处理单元 ( 简称p e ) ，一共1 4 4 颗龙芯2 f 处理器。 k d 5 0 主控服务器使用其中一台曙光服务器采用主频为22 g h z 的o p t e r o n 八核处理器，内存8 g b ，硬盘容量为8 7 6 g b 。主控服务器土要为k d 5 0 提供用 户管理、磁盘共享、任务分解、作业调度等功能。k d 一5 0 的一个计算节点包含两 块交换底板、共享电源和散热肛【扇。每6 个处理单元集成在一块交换底板上，由 内置的阿个华为4 端口干兆交换芯片组成，每个芯片连接3 个处理单元，另外一 个千兆接口作为对外输出，连入机柜交换机。k d 5 0 的处理单元中有一个龙芯 第2 章f c d 井行址理与任务分配 2 f 处理器，内存为d d r 2 1 g b ，千兆以太网芯片采用r t l s l l 0 s c ，其他还有b i o s 闪存，半口芯片，实时时钟芯片以及各种电源变换电路。由于龙芯2 f 是4 发射 超标量6 4 位处理器( 中国科学院计算技术研究所，2 0 0 7 ) ，当c p u 工作在7 5 0 m h z 时，相当于3 g f l o p s 的取精度浮点计算能力。 k d 5 0 的操作系统环境与应用配置以丌源软件为主，具有兼容性强、成本低、 易维护、易升级等优点。操作系统为d e b i a ng n ul i n u x4 0 无盘工作站，l i n u x 内核2 61 8 ，编译环境为g c c4 2 ，还部署了m p i c h 2 并行环境、t o r q u e 、 m a u l 资源管理和作业调度，以及g a n g l i a 系统运行监控。系统所有节点全部干兆 互联全局通信采用简化的l b p 模型。经过测试，使用t c p 协议进行点对点通 信的最大带宽可达到4 0 0 m b p s 。 综上所述，k d - 5 0 的特点概括为：c p u 浮点运算能力强，数量多，整体功 耗低，适合节点间无需频繁通信的并行浮点运算任务。k d 5 0 为大规模f c d 并 行处理提供了有力的高性能计算平台。下文将针对k d 5 0 系统结构，设计f c d 并行处理的框架。 24 k d 一5 0 下的f c d 并行处理框架 本节以k d 一5 0 高性能计算机为平台，介绍了f c d 并行处理框架 2 4 l 框架概述 虿孓目蚌 国l 霪急 国一d 忑 ”! - 图2 6f c d ，f _ 行处理系统结构