基于层次网格索引的大批监控车辆显示模型*

胡继华，唐 巍，詹承志

(中山大学工学院智能交通研究中心，广东 广州 510275)

显示(Representation)是GIS主要功能之一，二维电子地图、三维城市地图[1]、海量遥感影像的发布等都表明GIS显示取得了巨大进步[2]，在深度和广度上大大推进了GIS的发展和应用，车辆监控就是GIS深层次应用的领域之一。

随着GPS、GIS和无线通信技术的广泛应用，利用安装了GPS和无线通信设备的浮动车采集交通信息，已成为一种主流的交通信息采集方式[3]。车辆规模从最初的几百辆车，到现在的几万辆车，甚至百万辆车，车辆监控规模快速增长。这种大批车辆在电子地图上的位置状态显示，和静态的电子地图、遥感影像显示相比，有鲜明的特点：第一，显示的车辆位置状态是实时的，一般是分钟级的，最高可以达到秒级的；第二，刷新显示车辆位置状态时，数据流量很大，常常是几千、几万辆的车辆信息，给网络传输带来巨大冲击，导致网络拥塞。也给客户端显示带来很大的计算量，导致车辆显示时间过长，满足不了实时监控的要求，而且其他的计算和分析也难以进行。因此，大批车辆位置状态的显示是车辆监控迫切需要解决的问题。

从GIS的发展历程看，人们越来越多地需要在不同分辨率、不同空间尺度下对地理现象进行观察、理解和描述，即越来越多地需要对多尺度的海量空间数据进行分析、处理和表达[4]。而空间索引是管理海量空间数据的关键，它决定着整个空间数据管理的质量。空间索引主要用于从大量空间对象中快速存取满足一定空间范围条件的空间对象，从而实现空间对象的快速检索。建立适合不同场景的索引机制，对实现空间数据的管理和操作有着重要的意义。近年来，针对空间数据索引的研究日益成熟。比较有代表性的几种方式包括：网格索引、BSP树、R树、R+树、R*树、Cell树等等[5-12]。其中网格索引由于实现简单，能够直接映射到地理区域，被海量地图发布广泛使用，如Google Map地图和影像发布，ArcGIS和Supermap的地图发布管理软件都广泛采用网格索引或网格索引与其它索引组成的混合索引。

在监控中，车辆是地图对象的一种。车辆显示除了有实时性、动态性特点外，与传统的地图对象显示有很多相同之处，如大比例尺下显示全部对象，小比例尺下抽象显示地图对象，有选择地显示重要对象等[13]。此外，车辆位置状态也有区域化特征，因此，可以参考网格索引技术来设计车辆显示模型和算法。

本研究主要针对大批监控车辆的显示和管理，基于网格建立自适应层次网格索引机制，以解决监控车辆数据庞大造成的显示缓慢问题。

1 车辆显示模型

海量地图发布通过将各级比例尺的电子地图按照设计的网格尺寸切成图片(Tiled map)保存，响应请求时根据请求比例尺和显示区域返回对应网格图片给客户端，使网络传输的地图数据量大大降低，保证用户可以顺畅地浏览任意比例尺，任意区域的地图[14]。因此，大批车辆显示也必须满足比例尺、网格索引和网络传输数据量3个要素：在比例尺上，监控区域的各级比例尺地图都可以显示车辆；在网格索引上，建立和比例尺对应的网格索引，来管理车辆位置状态信息；在网络数据传输量上，必须将网络传输量压缩至kb级，才能保证车辆在各种网络条件下流畅地显示和更新。由此定义模型的3个性质：

1)全面性/全覆盖：所有车辆都可以在地图上显示出来，每一个车辆都可以在地图上实时显示和监控。即从总体上，所有车辆都被监控起来；从个体上，可以详细监控跟踪车辆位置和状态。

2)区域网格化：电子地图被划分成规则的网格，每个网格有对应的地理区域。只显示当前地图范围内的车辆，当车辆显示存在重叠时，一个网格区域只显示一个车辆对象，代表区域内的所有车辆，这些车辆可以通过放大地图或列表方式进行进一步监控跟踪。

3)动态性：按照车辆监控范围和地图比例尺级别设置对应的网格体系，根据比例尺使用相应尺寸的网格，在地图范围显示对应网格内的车辆，形成动态网格。

综上所述，所谓车辆显示模型，是指通过建立与比例尺对应的网格索引机制，管理车辆位置状态信息，最终实现监控车辆信息在电子地图上流畅显示与更新。模型具有全面覆盖性，区域网格化，动态性3个基本特征。

1.1 模型结构

模型主要定义了基准网格，网格体系，动态网格，车辆网格管理等几个基本概念。

基准网格：在全图显示下，根据显示空间范围和车辆图标大小确定网格大小，作为基准网格，一般为正方形，显示在地图上时大于车辆图标范围，避免相邻网格的车辆图标重叠。

网格体系：基准网格确定后，下面各级网格按照下式来确定：

(1)

其中，n为网格层级，Nn代表第n层划分的网格数量，N0代表基准网格数量，a代表网格划分粒度。

网格层级可以参考Google Map的网格层级，一般取3～5级即可。

动态网格：将各级网格和显示比例尺联系起来，在地图上显示车辆对象，根据显示出来的网格总数对比例尺和网格体系的关系进行微调，控制同时显示的网格数在1 000左右。

车辆网格管理：车辆显示时，先计算每个网格内车辆的数量，并选择其中一个车辆作为代表显示车辆位置和个数，点击该车辆，进入下一级比例尺的网格显示或列表显示本网格内的所有车辆。另外，在最大比例尺附近，地图显示的空间范围比较小，此时不再使用网格体系，当前地图视窗内的车辆全部显示。

1.2 模型评价指标

根据车辆监控系统的实际需要，模型应具有以下3个评价指标。

监控覆盖率/全面性：基准网格是在车辆监控区域全图显示时确定的，其他网格是在基准网格的基础上派生的，所以基准网格区域之和就覆盖了全部监控区域，即覆盖率为100%，对于在监控区域外活动的车辆，如果需要可以将车辆活动区域并入监控区域，这样就实现了对所有车辆的监控。

数据量：无论网格层级如何，车辆的显示总数保持在千量级。当地图按照2倍等比放大显示时，当前地图区域的显示范围就成为原来的1/4，同时子网格显示数量则随着网格划分方式而变化，此时如果a=2，n=2，则网格显示大小和数量不变。按照规则，每个网格只显示一个车辆，车辆显示总数仍处于103辆级水平。

响应时间：车辆显示的相应时间包括地图显示时间、数据库请求查询时间、数据库传输时间和地图上车辆对象更新绘制时间。前三者的时间一般是秒级，第四个时间和图标的复杂度有关，如果图标简单，则绘制时间可以控制在秒级，如果复杂，则时间会比较长。总体而言，在简单图标情况下，总的相应时间能控制在秒级。另外，响应时间可以通过改进显示策略和更新策略进一步优化。

2 模型实现

模型的实现有两种方式，服务器端实现和客户端实现，下面以广东省重点车辆监控系统为例阐述模型的实现。广东省重点车辆监控系统的目标是将广东省境内的长途客运、货运、出租车、校车、建筑用车等八种车辆监控管理起来，这些车辆共50万辆。监控的前端设备是GPS汽车行驶记录仪，后台是大型的服务器和工作站，前端设备通过无线网络将车辆位置状态信息实时传送给车辆所属公司，公司每隔一定时间(当前是15 s)将车辆位置状态信息上传给省监控中心，省监控中心在监控客户端显示这些车辆，根据车辆信息对车辆实施监控管理。

2.1 服务器端实现

2.1.1 基准网格和网格体系设计 车辆上传的经纬度数据是以弧度为单位的，如某车辆的位置是113.332 34，23.875 755，另外，广东省的经纬度范围介于北纬20.2°～25.5°、东经109.75°～117.33°之间。为方便起见，基础网格可以0.3弧度来划分，子网格采用a=10，n=3进行划分，共3层网格，分别是0.3*0.3 rad、0.03*0.03 rad、0.003*0.003 rad。网格id采用hash表的方式直接用经纬度生成，如第一层第一个网格id为20.3～109.8，子网格id依次类推。和比例尺对应方面，指定基础网格对应全图显示的比例尺，以及第2、3级比例尺，2级网格对应之下4、5、6级比例尺，3级网格对应7、8级比例尺，9级以下不再使用网格。

2.1.2 网格体系实现 网格体系在车辆实时数据保存的时候自动实现，首先在车辆实时位置表里增加三个字段，CODE_1、CODE_2、CODE_3，分别用于保存一级网格、二级网格、三级网格。车辆位置数据保存时，截取对应精度的经纬度(如1级网格精确到0.1°)，拼成网格id保存起来，这样就构建了hash表式的网格，如图1所示。

图1 网格层级划分结构图

2.1.3 车辆查询和客户端显示 查询车辆时，根据地图请求的比例尺确定要查询的网格级别，对相应的网格id进行查询，如一级网格就对CODE_1进行查询，再结合地图请求的空间范围，就可以获取目标空间范围内各网格车辆数量和代表车辆的详细信息了，核心代码如下：

select

CODE_1, NUM, ID, LONGITUDE,

LATITUDE, CARPLATE, CARTYPE,

DATEDMYTIME, SPEED, HEADING,

ALTITUDE, DRIVERID, POSITIONCITY,

POSITIONROAD, AREACODE, ISONLINE,

LIMITEDSPEED, CARMEMBERNAME

from (

select CODE_1,NUM=count(*)

from Table_2

group by CODE_1

)t

cross apply(

select top 1 * from Table_2

where t.CODE_1=CODE_1

order by newid()

)b

where

LONGITUDE between 112.65 and 113.85

and LATITUDE between 22.05 and 23.15

order by CODE_1

数据到达客户端后，客户可以选用合适的图标将车辆在地图上显示出来。

2.1.4 效率评价 从以上过程可以看出，基准网格约60*80共480个，这样极端情况下子网格显示数量为2.5*480=1 200个，则全部地图浏览过程中显示的网格量控制在千级水平，意味着车辆数据传输量控制在千级规模。

从时间上看，网格创建在数据存储时同步进行，基本上不耗费时间；查询所用时间也很少，可以在1秒内完成。主要的时间用在车辆图标绘制上，这可以通过选择合适的图标将时间控制在秒级。总体上，一次车辆更新显示可以控制在秒级。

2.2 客户端实现

2.2.1 设计思路 客户端实现方式与服务器端不同点在于网格的划分规则上。服务端采用3层网格架构，当比例尺超过限度范围变化层级和网格数量的方式，以表达不同的粒度。在较少车辆区域范围内，客户端实现方式表现为固定划分的网格数量，如设定为33*33=1 089个网格，但网格所表示的范围可以随尺度进行变化。通过计算车辆的经纬度与各网格的隶属关系，对车辆进行分组，如网格的Extent范围为(113.6,22.0,114.0,22.1)，相应网格编号为(18,10)，有一辆被监控车辆某时刻所处位置为(22.028,113.725)，那么该车按照分组规则落入该网格内。最后按照分组结果在地图上加载车辆位置代表(每个网格用1个车辆图标表示)。当比例尺变化时，重新计算网格Extent范围和落入其中的车辆，通过这种方式实现了随比例尺变化的动态显示粒度变化。也即小比例尺对应粗粒度，大比例尺对应细粒度。

2.2.2 网格划分过程 首先从数据库实时提取所有车辆定位数据，为提高效率，采用服务器数据压缩，客户端数据解压的方式提高传输速度。网格数量划分则以可接受的显示效果为依据，本例选取33*33=1 089个网格，然后计算车辆与不同尺度下网格在空间范围上的隶属关系，并记录车辆的隶属网格编号信息。这样初步建立了一套网格索引，通过网格查询落在其中的车辆，与此同时，也可以通过车牌等信息查询车辆所处的网格。

2.2.3 车辆查询和客户端显示 查询车辆时，直接根据索引查询到车辆的网格编号，进一步通过网格查询可获取到所有位于该网格内的车辆的详细信息。主要的算法流程如图2和图3所示。

图2 网格划分算法流程图

图3 车辆信息查询流程图

2.2.4 效率评价 从上述过程可知，网格数量划分在系统初始化时可以按照不同的需求进行设定，多比例尺的变化的并不影响车辆位置表示效果，主要表现在加载和更新方面。

在时间方面，通过数据压缩和解压的方式传输可以有效避免网络拥塞，通过算法设计后的车辆与网格的隶属关系确定计算时间也非常短。通过进一步改进图标绘制，可有效解决车辆数据更新和比例尺变化情况下的地图表现问题。

3 结果验证

实验中均在Intel 双核CPU 2.00 GHz，2.0 GB内存普通PC上进行。程序运行平台为VS2008，采用的开发语言为ArcGIS+ Silverlight +C#。

1)没有经过网格索引优化的车辆监控。

图4中所采用的车辆显示图标为ArcGIS内置简单图标(SimpleMarkerSymbol)，也可以采用车辆型小图片的形式(本实验采用的图片大小为783字节，占用空间4KB)，但加载图片的速度较慢，不能满足实时监控需要。

图 4 无网格索引下的车辆监控效果图

两种方案耗费的时间比较见表1。

表1 加载图标与加载图片初始化时间对比

由上述可知，当采用图片作为车辆展示图标时，为满足速度和网格满载率的需要，1 000辆是一个可以接受的监控参考值。在展示效果方面，不经过任何优化的车辆密集区域，车辆图标重叠严重，展示效果不好。

2)经过自适应网格优化的车辆监控和查询。

为达到明确监控对象的需求，本实验采用车辆图片作为车辆点对象在地图上的代表，效果如图5所示。

图5 网格索引下的车辆监控效果图

在实验中将地图区域划分为33*33=1 089个虚拟网格，实验中的车辆数据为8 405辆。通过算法进行聚合优化，减少展示展示在地图上的车辆图标数，提高展示效果和速度。另通过算法步骤对车辆属性分组，同时满足车辆单点和区域监控需要。

实验同时对自适应网格优化后的结果和未经任何优化的结果进行了对比，结果见表2。

表2 网格索引与未索引结果对比

4 结论和展望

本文针对车辆监控中的大批量车辆显示速度慢、车辆覆盖率低等问题，提出了基于层次网格索引的大批监控车辆显示模型，为车辆建立多层网格索引，结合地图显示比例尺动态聚合重叠显示的车辆，实现了车辆监控的全面性，降低了数据传输量，提高了车辆显示速度。

1)提出车辆监控中大批车辆显示模型，必须满足覆盖率、数据传输量、响应速度等指标。

2)提出了将网格索引应用于车辆显示，将层次网格和比例尺关联起来，动态聚合重叠显示的车辆，降低了数据传输量，提高了响应时间。

3)以广东省重点车辆监控系统为例，分别在服务器端和客户端实现了模型并验证其有效性。

参考文献：

[1]谭仁春.三维城市模型的研究现状综述[J].城市勘测, 2007(5):42-46.

[2]陈锐祥,何兆成,黄敏等.Google Earth在交通信息服务系统中的应用研究[J].中山大学学报：自然科学版, 2007,46(2):195-198.

[3]张存保,杨晓光,严新平.浮动车采样周期优化方法研究[J].交通运输系统工程与信息,2007,7(3):100-104.

[4]张新长,黄秋华,杨剑.土地利用数据在不同尺度下的精度损失模型研究[J].中山大学学报：自然科学版, 2007,46(3):103-106.

[5]李德仁,崔巍.地理本体与空间信息多级网格[J].测绘学报,2006,35(2):143-148.

[6]周勇,何建农,涂平.一种改进的自适应层次网格空间索引查询算法[J].计算机工程与应用,2006:159-161.

[7]李德仁,肖志峰,朱欣焰.空间信息多级网格的划分方法及编码研究[J].测绘学报,2006,35(1): 52-56.

[8]吴长彬,闾国年,刘昱君.基于规则库和网格算法的土地利用现状图自动数字注记[J].测绘学报, 2008,37(2):250-255.

[9]王映辉.一种GIS自适应层次网格空间索引算法[J].计算机工程与应用,2003,9:58-60.

[10]胡久乡,何松,钟瑜.空间数据库网格索引机制的最优划分[J].计算机学报,2002,25(11):1227-1230.

[11]邵振峰,李德仁.基于网格计算环境下的空间信息多级格网研究[J].地理信息世界,2005,3(2):31-35.

[12]LI Wei, ZHANG Rong, LIU Zhengkai.An approach of laser-based vehicle monitor[J].Applied Mathematics and Computation,2007,185: 953-962.

[13]LI Qingquan,ZHANG Tong, WANG Handong.Dynamic accessibility mapping using floating oating car data: a network-constrained density estimation approach[J].Journal of Transport Geography,2011,19(3):379-393.

[14]LOUKAS G A, BALAJI R, DANIEL P B.Multiresource inventories in corporating GIS, GPS and database management systems: a conceptual model[J].Computers and Electronics in Agriculture,2000, 28: 89-100.