石向亭，秦 俊，陈思国，牟贺铭，余雪岗，曲良东

（吉林大学计算机科学与技术学院 符号计算与知识工程教育部重点实验室，吉林 长春130012）

0 引 言

导航系统目前正经历着由传统自主导航到中心导航［1－3］转变的过程。在单车自主导航中，为驾驶员提供引路服务时，是依据静态存储在本地的地理信息进行的路径规划；而中心导航系统的优势在于车载终端可以通过网络实时地获得导航中心所提供的相关信息服务［4］和地图单元数据，其中包括基于实时交通路况的导航［5－6］。从而达到对于驾驶员来说，他们都可以使用实时路况导航服务，这将使导航系统的使用方式达到彻底的改变。更重要的是，从交通系统的整体来看，中心导航存在着传统单车自主导航所不可比拟的优势，即其具有引导车辆避开拥堵路段的交通疏导功效。

地图数据单元不必全部存储在车载导航终端。只要系统定义好导航中心与车载终端之间进行数据交换的协议，即可通过网络对终端所需地图数据进行在线下载，从而降低了车载终端设计和实现的复杂度，使其成为一个人机接口 （human machine interface，HMI）而存在；同时，目前中国快速发展的路网和路边POI（point of interest）与此种设计理念也达到极大的契合，中心导航的基本系统框架如图1所示。然而如何解决地图数据网络传输延时问题，保证终端系统能够实时的使用地图数据和实时显示地图是中心导航系统亟待解决的问题。

图1 中心导航的基本系统框架

地图的分块存储［7］、分层加载［8］、分区索引［9］和基于二级缓存的地图显示［10］等方法被很多研究这提出，这些方案使地图数据的存储、传输和显示效率达到了一定的提高。通过对以方案的分析，选择使用地图分块存储和地图显示二级缓存的方法以达到满足嵌入式系统内存小、运算慢得特点，同时还可以提高地图传输和显示效率，另外对地图数据进行的预取和更新策略也是在电子地图分块存储的基础上提出来的，结合基于双缓存的局部地图刷新机制保证车载终端电子地图显示的实时性。

1 车载终端与系统服务器之间的通信

按照地图分块策略，服务器将矢量地图数据按横向和纵向分块存储，每一个分块地图包含所有的图层。每一个分块为 “地图单元”，每一个地图单元将分配一个编号，为“地图单元号”。为了方便终端使用地图单元，每个地图单元数据在经过投影变换转为平面坐标 （其中原点在左上角）后存储到数据库中，同时存储该地图单元经纬度范围以及地图单元号。服务器建立了经纬度坐标和地图单元号之间的对应关系，并利用地图单元号索引机制提高地图块查找效率。服务器有个模块专门处理实时的交通信息［11］，并集成到分块地图数据库中。

车载终端系统分为数据管理模块、地图绘制模块和显示模块：①数据管理模块，负责地图数据请求、存储和删除；②地图绘制模块，负责绘制地图数据和备用缓存的更新；③显示模块，负责地图画面刷新。车载终端系统启动时，首先由数据管理模块与服务器建立连接，传输地图数据。

1.1 地图传输协议

协议的设计保障了服务器和车载终端之间地图数据的实时和有效传输，同时传输层的TCP协议是可靠的传输协议，因此终端和服务器间建立的TCP连接，一方面可以使数据传输认为是可靠的，另一方面也避免了在设计应用层协议时再次考虑可靠传输的问题。两者之间协议包括数据请求协议和数据发送协议。

1.1.1 地图单元请求协议

请求报文主要包括地图数据初始化报文和地图数据更新报文，其结构见图2。其中 “类型标识”用来区分两类报文，传输地图数表示终端向服务器请求的数据单元数量，经纬度坐标表示终端的位置。下面进行详细介绍。

图2 地图数据请求报文

类型标识为1时，表示终端系统请求进行地图数据初始化，这时所需地图单元数为25。为什么需要传输25个地图单元，将在第2部分详解。终端通过GPS（global positioning system）接收机获得自身经纬度坐标［12］，发送给服务器。服务器首先查找包含这一坐标的地图单元，然后查找以该地图单元为中心的5行5列的25个地图单元，服务器将按照上北下南的方向，从左到右从上到下，依次传1－25张地图单元数据到终端。类型标识为2时，表示终端向中心系统请求进行地图数据更新。主要包括需要更新的地图单元数及相应的地图数据。

1.1.2 地图单元发送协议

响应车载终端的地图数据请求报文之后，服务器端向其传输所请求的地图数据，发送数据报文的协议主要由地图头部和地图元素两个部分组成。

（1）地图头部

每块地图所表示的范围由边界经纬度定义，此范围主要用来判断车辆是否在此块地图单元中。每块地图数据单元的分层数用地图层数记录，便于车载终端控制地图数据的接收。其结构如图3所示。

图3 地图数据单元头部

（2）地图数据元素

各种地图数据元素的在网络中的传输格式见图4。

地图单元当前层数据传输结束用标识0表示。

传送数据元素为点时，用标识1表示；此时不发送点的个数这一选项；接下来的两个短整型，表示了该点相对此块地图边界的偏移量；标注的字节数由标注长度n来表示，为0时表示当前点元素没有标注；该点元素的颜色和样式用属性字段表示。

图4 地图元素数据格式

传送数据元素为线时，用标识2表示；若点的个数为2，则表示该地图元素为线段；若大于2，则表示该元素为折线，并且该项记录了此折线所包含的点的数目；接下来的字段是该元素中点的坐标以及此元素的标注；当前的路况信息则由其属性指示出来。

传送数据元素是一个区域时，用标识3时；点的个数表明了该区域的边界线所包含点的数量；接下来的字段是该元素中点的坐标以及此区域的相关标注；所绘制区域的样式和颜色用属性字段表示。

1.2 地图数据的组织

车载终端系统定义了地图数据单元结构体，对从服务器端接收到的每块地图数据都作为独立的单元进行存储，方便了车载终端的管理。每个结构体都存储该块地图的头部和图层数据，每个图层数据又包含多种地图数据元素，为了提高空间的使用率，采用链表的存储方式来保存数量不固定的图层及其中数据元素信息。

本系统参照了MIF［13］中地图的格式对点、线段、折线和区域4种图形对象进行了定义，具体结构如：

（1）坐标点结构体。定义了指示其平面位置的x和y；以及指向下一个坐标点的指针，以便存储不同数据元素中点的坐标信息。

struct GP｛

int px；

int py；

struct GP＊pnext；｝

（2）点结构体。定义了表示该点具体位置信息的坐标点结构体，以及存储标注的字符串指针，以及指向下一个点结构体的指针。

struct Point｛

struct GP pgp；

char＊plabel；

struct Point＊pnext；｝

（3）线段结构体。定义了表示该线段起止位置的起止点坐标结构体，存储标注的指针，和指向下一线条段的指针。

struct Line｛

struct GP lstart；

struct GP lend；

char＊llabel；

struct Line＊lnext；｝

struct Pline｛

int pointnum；

struct GP＊pgp；

char＊plable；

struct Pline＊pnext；｝

（5）区域结构体。定义了该区域所包含节点数，坐标点结构体链表，中心坐标，存储标注的指针，以及指向下一个区域的指针。

struct Region｛

那是我最后一次看到万姐，背着一个比她身体还要大的包袱。老公要下楼帮她拦辆出租车，却被她拦住了，一个人摇摇欲坠地向楼下走去。我这才发现，原来她住在我家时，竟然做了那么多的衣服。

int pointnum；

struct GP＊rgp；

struct GP rcenter；

char＊rlable；

struct Region＊rnext；｝

1.3 建立地图单元

车载终端系统根据协议依次接收多个地图数据单元，终端将接收的地图单元存储到地图数据单元结构体。图5指示了终端接收地图数据单元的具体流程。

2 地图数据的预取和更新

空间相关性是地图数据单元所具有的特点，因此当某一块地图数据单元被车辆使用时，在其周围的其它地图单元数据也有很大机率被使用。车载终端系统的接收、存储、绘制、预取，以及更新都是以地图数据单元为基本单位进行的，这样做不仅提高了预取和更新的效率，而且使已下载地图的使用效率有所提高。在进行了测算，并经过实际的上车实验后，确定终端系统任意时刻都存储25块地图数据单元。具体的逻辑存储结构如图6所示，其中每个地图数据单元均为正方形，当车辆在13号地图数据单元的中央行驶时，在终端上可能显示的地图范围由灰色区域指出，占整个地图数据的36%；当车辆在其内漫游时，可能使用到的区域如黑色和灰色区域所示，占整个地图数据的64%；预取的地图数据由剩余白色区域所示，占地图数据的36%。当车辆行驶出13号地图单元时，则需进行地图数据的更新操作。考虑终端系统地图数据更新的时间为t，T是车辆从13号单元行驶到周围任一单元中心线上时间，当T＞t时，即可保证地图的实时显示。

2.1 地图数据单元初始化

如图6所示，初始化时终端系统存储25块地图数据单元。为了在车载终端显示地图时使车辆的移动方向始终向上，就需要更大的空间对地图数据进行存储。本系统中所使用的触摸屏分辨率是640＊480，其对角线为800，根据以上分析，当车辆在中间行驶时，其可能用到的地图单元数为9，即每块地图单元绘制后的像素宽度至少为屏幕对角线长度的1／3，最后系统采取绘制后地图数据像素的宽度为300以便于计算，为了降低地图数据绘制的难度，采取实际长度一米用一个像素表示，因此，300m＊300m为本系统所使用的地图数据单元的大小；中心服务器也采用这一标准进行地图数据划分，以达到简化的目的。终端将接收的25块地图数据单元存储到一个由5＊5的二维数组指针链接起来的地图数据单元结构体中，并且根据各自所在二维数组中行和列的位置，计算出该地图单元由平面坐标转为屏幕坐标的X偏移量和Y偏移量。车载终端对其所接收的每个地图数据单元都进行遍历，将其中的各地图元素的坐标与其所在地图单元的偏移量相加，之后以 （750，750）为旋转中心，以车辆行驶的角度为旋转角度进行旋转变换，并将得到的结果绘制大小为1500＊1500的备用缓冲区HDC中。

图5 建立地图单元流程

图6 地图数据逻辑存储结构

2.2 动态刷新地图和更新地图数据

为了在导航过程中显示好的车辆移动效果需要对画面不断进行刷新，同时为了降低地图数据绘制时间，保证显示的实时性，本系统最后采用的局部刷新机制是基于双缓存的［10］，这样可以使得终端在任意时刻使用地图都不需要重新绘制，而仅仅是将所需要的地图拷贝到正确位置即可，提高了地图刷新的速度。地图数据和备用缓存的更新只有在车辆形式出13号地图单元才会发生。

2.2.1 动态刷新地图数据

终端系统采取地图向着车辆行驶的反向移动，而保持车辆不动的显示在屏幕的中间位置。系统所使用的备用缓冲区横纵坐标范围均为0到1500。刷新地图操作如下：

（1）初始运行时，利用函数BitBlt以 （750，750）为中心将大小为640＊480的画面从备用HDC拷贝到当前主窗口HDC。

（2）每隔1s获得车辆GPS坐标，首先同过道路匹配［14］对GPS坐标进行校正，从而判断出车辆当前所处地图数据单元的编号，即可根据相应公式对当前坐标进行投影变换，所得的平面坐标再加上该地图单元的X偏移量和Y偏移量得出坐标，并依据车辆行驶角度计算出其旋转之后的坐标，即可得进行显示地图的操作。如果坐标为 （650，705），则利用BitBlt函数以 （650－320，705－240）、（650＋320，705＋240）为矩形边界点拷贝640＊480的画面到主窗口HDC。

（3）当车辆的行驶角度变化小于5o时，不必进行地图重绘，否则利用新的行驶角度对缓冲区进行重绘；这样极大的降低了地图绘制次数。

（4）如果车辆在13号地图单元内行驶时，重复 （2）操作，否则触发 （5）操作。

（5）更新地图数据单元，并且重绘备用HDC。

2.2.2 地图数据和备用HDC的更新

由于系统是以单元为单位对地图数据进行存储，为了提高地图利用率，当需要更新地图数据和重绘备用HDC时也都是按单元进行的。如果车辆驶出13号地图单元，将定义一个以当前所处单元为中心的5＊5矩阵，对此矩阵内没有数据的单元进行请求更新操作。下面以车辆驶入18号地图单元为例对更新过程进行介绍：

（1）车辆行驶到18号地图单元，将对25个地图单元以此为中心进行更新操作，并丢弃原有的1、2、3、4、5共5张地图。

（2）将原来地图编号为6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25的地图向上方移动一个单元的距离，变为1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20。

（3）之后向服务器请求21、22、23、24、25号地图单元。如果当前车辆行驶方向变化小于5°，则将备用HDC中对应的图像利用BitBlt函数整体向上移动，同时将21、22、23、24、25地图单元旋转之后的位置用空白矩形进行填充，并在此绘制更新之后的地图数据；当行驶方向变化大于5度时，则根据当前的25块地图数据和车辆行驶方向对备用HDC重新进行旋转绘制。

其它情况下更新过程类似，当车辆驶入19、17、9、7号地图单元，会更新9块地图数据，即重用原有64%的数据；当驶入18、14、12、8号地图单元时，会对5块地图数据进行更新操作，而重用原有数据的80%。如果车辆不在当前地图内，系统将重新初始化。

3 实验和分析

采用仿真测试和上车测试两种实验方法进行测试，以验证本系统所采取预取策略的有效性。上车测试时，车辆的当前坐标利用GPS接收机实时获取，并对其进行存储；仿真测试则是利用软件以某一特定速度模拟产生存储的GPS坐标，以获得车辆在不受路况环境影响而匀速行驶时的数据，其它环境两者相同，并使用CDMA进行网络通信。

实验所使用的环境配置如下：①CPU是以ARM920T为核心的32位RISC微处理器S3C2410；②64Mbytes 32位SDRAM以及16Mbytes16位FLASH；③10M／100M自适应以太网接口；④一个GPS接收机。一个分辨率为640＊480的10.1英寸触摸屏及其接口和RS232接口；一个CDMA模块；一个TFT LCD接口和标准20针JTAG调试接口；以及实时时钟 （RTC）单元。车载终端的操作系统是内核版本号为2.4.18－rmk7的 ARM－Linux，同时选取嵌入式图形软件［15］MiniGUI绘制地图。使用某市地图，其覆盖面积约为20.43km＊19.83km，数据分为五层，总量为93.3M。实验环境如图7所示。

图7 实验环境

测试数据如下：①更新地图单元中使用的数目占更新总数的比例，即为命中率HR （hit ratio）；②系统初始化后预取次数与从初始化完成到当前预取完成时间的商，即地图单元预取频率 MPR （map prefetch ratio）；③系统接收总数据量与更新时间的商，即单位时间更新数据量UTDM（unit time update amount）；④更新地图时间与地图单元总数的商，即更新地图单元的平均时间MUAT （map update average time）。其中，更新时间即为接收、绘制和删除地图数据的时间之和。表1给出了一些测试数据。

表1 测试数据

上车主要测试了当车速介于 （15～36km／h和36～66 km／h）两个不同的区间时系统的性能，分别在市区和靠近郊区的区域进行实验；为了使仿真实验的行驶轨迹与上车实验大体相同，根据上车实验两种情况下的GPS坐标进行仿真实验，并将速度分别设置为28.8km／h和46.8km／h。

在所得实验数据中，地图数据单元的命中率基本上处于0.6235～0.7333之间。测试使用地图数据单元的平均数据量约等于UTDM与MUAT的乘积，由此可以得出当车速V较慢时，其经过的区域数据量较大，反之数据量则较小；这与上车测试中市区测试时车速较慢且数据量较大，以及靠近郊区测试时车速较大且数据量较小相对应。地图单元数据量的大小与单位时间内传输的数据量也相互影响；若地图单元数据量传输较大，则在一定程度上可以提高网络带宽的利用率，从而使UTDM也相对较高；同时对比测试数据中的UTDM列发现，仿真测试时单位时间更新数据量比上车测试时大，可知车速的大小在某种程度上会影响到CDMA的传输。同时，速度V越快，则相应MPR就越高，由此可知速度与更新频率成正比关系，且两者的商在数值上接近1100。

实验分析：T＝S／V为本系统的预取时间，其中S是预取距离，V为车辆的行驶速度。由公式可知：当S固定时，车速越大则时间越小。当网络传输速率固定时，更新地图单元数和其数据量与地图更新时间t成正比。更新地图单元数有9和5两种情况，假设其为9，以800＊800为使用范围进行分析得到S＞＝200m；选择表1中最大的MUAT作为参考值，则可得出当车速V＜＝ （S／（n×MUAT））时，即可得到满足。根据此公式及相关实验数据可知，若要保证T＞t成立，速度V最大为158km／h，这一速度远大于车辆在市区内行驶时的速度。如果某个地图单元数据量较大，就说明其包含道路的路况信息较为复杂，此时车速必然比正常情况小，从而使T更大，亦可实时地显示地图信息。通过以上分析可得结论：本文的策略可以保障终端系统地图显示实时性。

4 结束语

本文提出通过网络下载电子地图时，使用对地图进行分块传输和存储的方法提高传输效率和使用效率，以此为基础，提出了预取和更新地图数据的策略。当需要对地图数据进行更新时，为了保障实时地显示地图，采用在继续使用原有数据的同时对地图数据进行预取的方法。经过实验证明此方法可以保证地图实时显示。这种方法为中心导航的方式提供了基础，但在如何根据现有地图和车辆位置相结合进行地图数据的预取、预取数据大小设置、以及提高地图单元命中率方面，还存在更多的研究，以更好地保障地图实时显示。

［1］HU Jiyong.Design and development of vehicular wireless terminal in network－based central navigation［D］.Xiamen：Xiamen University，2009：13－19 （in Chinese）.［胡继勇.车辆联网式中心导航系统车载无线终端的研发 ［D］.厦门：厦门大学，2009：13－19.］

［2］YANG Xuejun.Research on algorithms and implement software about the central－type navigation system ［D］.Changchun：Jilin University，2006：4－14 （in Chinese）.［杨学军.中心式导航算法的研究和应用软件的实现 ［D］.长春：吉林大学，2006：4－14.］

［3］SHAO Yuning.Research on several key technologies of vehicle electronic map for real－time car navigation ［D］.Guangzhou：Guangdong University of Technology，2008：9－26 （in Chinese）.［邵于宁.实时车载导航系统中的电子地图若干关键技术研究 ［D］.广州：广东工业大学，2008：9－26.］

［4］WANG Wenchuan，XIA Hongshan.Study on the embedded－GIS for VNS and its implementation ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2005：12－35 （in Chinese）.［王文川，夏洪山.面向车载导航的嵌入式GIS研究与实现 ［D］.南京：南京航空航天大学，2005：12－35.］

［5］LI Xu.Research on the key techniques of vehicular sensor networks and applications ［D］.Shanghai：Shanghai Jiaotong University，2009：44－50 （in Chinese）.［李旭.车载传感器网络的应用及关键技术研究 ［D］.上海：上海交通大学，2009：44－50.］

［6］XU Li.Performance evaluation of vehicle－based mobile sensor networks for traffic monitoring［J］.IEEE Transactions on Vehicular Technology，2009，58 （4）：1647－1653.

［7］WU Xueling，LI qingquan，REN Fu.Bidirectional A＊algorithm based on hierarchical and block data or organization ［J］.Journal of Geomatics，2006，31 （8）：1－3 （in Chinese）. ［武雪玲，李清泉，任福.基于分层分块数据组织的双向A＊算法［J］.测绘信息工程，2006，31 （8）：1－3.］

［8］LI Jianyuan.Study of hierarchical path guidance algorithm and strategies ［D］Xi’an：Shanxi Normal University，2007：16－20（in Chinese）.［李建元.分层路径诱导算法与策略研究 ［D］西安：陕西师范大学，2007：16－20.］

［9］XU Jinghai，LI Qingquan，SONG Ying，et al.Research on map displayment based on Kiwi data format ［J］.Geomatics and Information Science of Wuhan University，2005，30 （10）：867－869（in Chinese）.［徐敬海，李清泉，宋莺，等.基于Kiwi数据格式的地图显示研究 ［J］.武汉大学学报信息科学版，2005，30 （10）：867－869.］

［10］MA Yaming，ZHANG Yajun，ZHANG Ruisheng.Study on fast displaying strategies of vector map based on VxWorks［J］.Journal of Geomatics Science and Technology，2009，26（4）：300－304 （in Chinese）. ［马亚明，张亚军，张瑞生.嵌入式GIS中矢量地图快速显示策略研究 ［J］.测绘科学技术学报，2009，26 （4）：300－304.］

［11］XIA Kai，WEI Chao.Study on real－time navigation data model based on ESRI shapefile ［C］.International Conference on Embedded Software and Systems Symposia，2008：174－178.

［12］GUO Baoqing，TANG Tao，YU Zujun.Train position with map matching based on GPS and track information ［J］.Journal of Electronic Measurement and Instrument，2007，21（1）：49－52 （in Chinese）. ［郭保青，唐涛，余祖俊.基于GPS与轨道信息的地图匹配列车定位算法 ［J］.电子测量与仪器学报，2007，21 （1）：49－52.］

［13］LIU Yang.The design and implementation of vehicle navigation system GIS based on QTE ［D］.Chongqing：Chongqing University，2009：15－19 （in Chinese）.［刘洋.基于 QTE的GIS车载导航系统的设计与实现 ［D］.重庆：重庆大学，2009：15－19.］

［14］DING Lu，CHEN Jiabin，SONG Chunlei.New map－matching algorithm and real－time parameter correction for land vehicle navigation system ［J］.Chinese Journal of Scientific Instrument，2008，29 （3）：658－661 （in Chinese）. ［丁露，陈家斌，宋春雷.车辆导航系统地图匹配算法及实时参数修正［J］.仪器仪表学报，2008，29 （3）：658－661.］

［15］LI Xusheng，LI Bing，QU Shangyong，et al.Application and research of the MiniGUI based on the ARM－Linux ［J］.Journal of Xihua University，2008，27 （3）：64－68 （in Chinese）. ［李旭升，李兵，曲尚勇，等.ARM－Linux的 MiniGUI的应用研究［J］.西华大学学报，2008，27 （3）：64－68.］