车载自组织网络路由算法研究

岳志鹏，周永，黄弘（西华大学计算机与软件工程学院，成都 610039）

车载自组织网络路由算法研究

岳志鹏，周永，黄弘
（西华大学计算机与软件工程学院，成都 610039）

0　引言

随着各国城市化和计算机化的发展，极大地推动了通信技术在道路交通领域的发展，一些发达国家开始研究以提高安全性和效率为目标的交通系统，即智能交通系统（Intelligent Transport System，简称ITS）。交通管理系统中嵌入了ITS，ITS是由信号控制系统、监控系统、交通流动态系统和车辆收费系统等联网组成，而ITS服务则包括广播、电台、路边终端、路边情报等发布渠道，由动态导航信息服务系统、综合枢纽换乘信息服务系统、停车信息服务系统等联网组成的，由此车载自组织网络（Vehicle Ad hoc Networks，简称VANET）应运而生。本文研究的是城市交通环境下的车载自组织网络路由协议，而主要研究其中基于地理位置的路由问题。传统的基于地理位置的路由协议存在着不足，本文提出一种城市环境下基于地理位置的车载自组织网络路由协议GCRR（Geography-based and Network Connectivity Reliable Routing）。GCRR有如下特点：算法不仅考虑了道路的物理长度，而且考虑了道路的连通性；在道路的十字路口部署了RSU基站，来辅助路由发现；在数据传输过程中，用公式推导出了使链路稳定的方案；使得数据包投递率增加，吞吐量增加。

1　一种基于地理位置的路由协议

1.1物理长度产生的影响

传统的基于位置的路由协议主要是考虑了道路的物理长度，而并没有考虑道路的车辆数目和道路连通性等因素，因此在应用中会影响网络中端到端的平均时延和数据包投递率。

依据物理距离作为判断路由选择的机制，是传统的基于位置路由协议的局限。所以，在结合了道路物理距离的同时，需要考虑道路的其他因素和网络的连通性。

1.2平面图产生的影响

由于城市交通道路周围存在大量的建筑物，而车辆无法对它的存在做出判断，无论使用Gabriel图还是相关邻近图都会隔断网络拓扑结构。为了解决上述问题，可以在每个十字路口部署RSU基站，数据包可沿着城市中的道路进行转发，来提高网络的连通性。

综合以上因素，本文给出了一种基于地理位置的路由算法GCRR，该算法的路径选择部分是基于路道中车辆数目和道路的物理长度，数据转发部分则考虑了链路的持续时间，即算法由路径选择和数据转发两部分组成。

2　算法描述

2.1车载网络城市结构图

城市主干道路上部署了车流量采集系统，并在十字路口和三岔路口部署了路边单元（RSU），（见图1，其中，路边单元包括计算处理模块、无线接口、以太网接口等，车载单元由车路通信模块、车间通信模块、电子地图和GPS定位模块等组成（见图2，RSU通过无线接口与车辆互换信息，并且收集车辆的具体位置信息，同时RSU通过以太网接口与交通信息服务中心进行通信。

图1　车载网络城市结构图

图2　车载单元结构图

当有车辆驶出当前街道，并进入十字路口时，RSU能够将此信息采集到，并且车流量采集系统统计道路密度。交通信息服务中心TISC（Traffic Information Service Center）依据RSU和车流量采集系统，统计城市中所有车辆的位置信息和道路密度，且记录着每条道路的交通状况，并可以实时更新道路中的车辆信息，使交通信息服务中心可以获得实时准确的道路交通信息。如图3所示，当车辆1从街道Road1驶进Road2时，RSU就会采集到此信息，TISC更改车辆位置更新数据内容。位置更新数据的内容包括：（IDi，Roadi，Roadj，Xi，Yi，Vx，Vy），其中IDi代表车辆I的编号，Roadi指之前所在的路段编号，Roadj指刚驶入的路段编号，Vx，Vy表示车辆的移动速度和移动方向，Xi，Yi表示车辆所处的地理位置。

图3　车辆更换道路

在路径选择方面，交通信息服务中心依据车流量采集系统和电子地图提供指定路段的车流量数据，并根据源节点和目的节点的位置信息、相关路段的车辆数目以及物理长度计算源节点到目的节点的数据传输的路径。

2.2条件假设及基本概念

在该算法中，假设所有车辆都安装GPS导航系统，车辆可以获取他们的位置信息和其他车辆的位置，导航系统能为车辆提供城市街道的电子地图等。本文中提到的节点是指车辆模型，假设处于十字路口的节点可以跟无线传输范围内的非十字路口节点进行通信，而不在同一条道路上的非十字路口节点间不可通信。因此，数据的转发过程，主要是从非十字路口节点向十字路口节点逼近，十字路口节点再转发给另一个非十字路口节点，直到数据转发到目的节点为止。文中提到的车辆为源节点，车辆为目的节点。

2.3路由选择

路由选择的过程如下：

（1）车辆周期性地广播信标消息，即车辆的位置信息，消息中包括（IDi，Roadi，Xi，Yi，Vx，Vy），Roadi表示车辆所在的路段编号，同时，每辆车和路边单元都维护并周期性更新一个邻居表。车辆之间通过交换信标消息，将直接邻居的ID和位置信息添加到自己的邻居列表中，由此获得对自身周围网络拓扑情况的认知。

（2）城区主干道启用车流量采集系统，实时采集各路段的车流量。

（3）车辆S由电子地图获知本路段两端的RSU基站地理位置，并由多跳转发的方式向RSU发送路径请求包，数据包内容包括（IDs，IDd，Xs，Ys，Xd，Yd，Vsx，Vsy），其中，IDs指代源节点的编号，IDd指代目的节点编号，Xs，Ys指代当前源节点的地理位置，Xd，Yd表示目的节点的地理位置，Vsx，Vsy表示源节点的行驶速度和行驶方向。

若交通信息服务中心发现车辆S与车辆D处在同一路段，则不用进行如下计算，直接将数据通过多跳方式转发至车辆D。否则，交通信息服务中心通过车流量采集系统得到第i条路段的车辆数目，建立一个每条路段的权值公式并计算每条路段的权值，权值公式定义如下:

其中，Li为本路段道路的物理长度，Ni为本路段的车辆数目，Wi为本路段的道路权重，此参量为Ni和Li的综合度量，此值表示本路段的物理长度越小，车辆数目越多，此路段就越可能被选为路由路径。使用道路权重因子是为了充分利用车辆数量多的路段，也为了选择能尽快将数据包传递至路口RSU的路段。图4为TISC收集消息及工作流程图。

最先收到路径请求包的RSU基站，将此消息发送给交通信息服务中心，而后来接受到数据的RSU将此信息删除。交通信息服务中心将依据路径请求包的内容，通过Dijkstra算法计算出路由路径，再将传输路径数据包回复给刚才的RSU基站，传输路径数据包内容包括（Ri，…，Rj，Xd，Yd），其中，Ri，…，Rj为路由转发经过的RSU基站编号，Xd，Yd为车辆D的地理位置。Dijkstra算法如下：

图4　 TISC收集消息及工作流程图

①设Rs'为源RSU基站（路口），令A为已经寻找到的最短路径路口的集合，A＝{Rs'}，把所有不在集合A的节点放入集合B中，B={R1，R2，…，Ri}。若路口Rs'与路口R1直接相连，有：

其中，W（Rs',1）代表从源路口Rs'到路口1的权值，即D（R1）代表从源路口Rs'到路口R1的权值。

若路口Rs'与路口R1不直接相连，有：

②寻找一个不在中的节点Ri，其D（Ri）值最小，把它加入到中，再对所有不在中的节点Rj，

●Rj节点之前与Rs'不相邻,即D（Rs'）=∞，则D（Rs'）更新为：

●D（Rs'）!=∞

则用[D（Rs'），D（Ri）+W（Ri，Rj）]中较小的值去替换之前的D（Rs'）值，即:

③重复步骤2，直至A中包含网络中所有的节点（循环次数=节点数）。

车辆S将返回的消息放入数据包分组的头部，并根据（Ri，Rj，…，Rd）转发基站路由的次序，依次向这些RSU基站转发消息，当RSU基站收到消息后，就在数据分组的头部做好“签到”标记，直至将数据传输到最后的基站Rd，该基站再将数据转发至车辆D。图5给出了路由选择流程图。

通常认为道路的连通性与该道路上的车辆数量有关，车辆数量越多，则此道路的连通性越好。

2.4数据转发

当车辆S获知路由路径后，将传输路径数据包的内容添加到车辆S的分组头部，包括传输需要经过的RSU基站（Ri…Rj），和目的车辆的具体位置（Xd，Yd）。车辆S将按照路径S-RSUi…RSUj-D进行转发，而这之间的每一条路段，将采用多跳的方式。

图5　路由选择流程图

在介绍本算法的转发方案前，先强调一点，在路由的转发时，并不是道路中的所有车辆都参与数据包的转发，而是选择符合条件的车辆节点参加数据包的转发。

经典的GPSR协议在选取下一跳节点时，考虑在无线可传输范围内，选取离目的节点最近的节点作为下一跳，这样的方式只考虑了尽量远距离的传输，而忽略了行驶中车辆的运动状态而导致传输链路不稳定。数据的转发是采取多跳的方式，若其中的一条链路断裂，就会导致数据包丢失和数据重传，从而增加了端到端的平均时延，降低了数据包的投递率。因此，每跳链路的稳定是数据转发中需要重点考虑的，本算法在数据转发部分，下一跳节点的选取是，将数据包转发给同向行驶的速度尽量相近的车辆。此方案是通过下面的公式推导出来的。

Su W和Lee S J给出了预测每条链路连接时间的公式：

其中：

公式（9）中，vi，vj代表移动节点i，j的速度，（xi，yi），（xj，yj）代表移动节点i，j的坐标，θi，θj代表节点i，j的移动方向，r是节点的有效通信距离。两个节点之间的链路持续时间就是预测时间，Su W和Lee S J只给出了链路持续时间的公式，而没有再简洁的结果。这里本文结合城市车载网络的特点，将此公式继续化简。

在一条道路中，车辆的下一跳选择，在方向上分为传递给同向行驶的车辆和逆向行驶的车辆，如图6所示，当车辆i选择同向行驶的车辆j作为下一跳时，θi= 0，θj=0，代入到公式（9）中，此时：

图6　车辆i和j同向行驶

将式（10）代入到式（8）中有：

如图7所示，当车辆i选择逆向行驶的车辆j作为下一跳节点时，θi=0，θj=180°，代入到公式（9）中，此时有：

图7　此图车辆i，j逆向行驶

将（12）代入到（8）中有：

由公式（11）和（13）可看出，两公式中只有分母不同，因为（vi-vj）<（vi+vj），所以T1>T2，即选择同向行驶车辆为下一跳的链路持续时间要长于选择逆向行驶的。另外，由公式（11），可得出，当vi，vj的大小越接近，则T1越大，即当节点i和节点j的行驶速度越相近，链路的持续时间越长。因此，本文在数据转发时，选取在可传输范围内，同向行驶的速度相近的节点作为下一跳节点，以保证链路的稳定性。即车辆通过查找自己的邻居列表，选择与自身行驶方向一致和速度相近的车辆作为下一跳节点并发送数据包，以此类推，直到数据包到达传输路径的第一跳路边单元，此路边单元根据传输路径数据包的内容地址，继续转发，直到到达节点D位置。

3　结语

本文主要研究的是城市交通环境下的车载自组织网络的路由协议，而主要研究其中基于地理位置的路由问题。

通过对经典路由协议的特点和原理进行了研究后，本文根据它们存在的不足和城市道路的特点，给出了基于地理位置的路由协议。本算法在路由选择部分，利用了交通信息服务中心和交叉口的基站，从而减少了路由查找的时间和路由开销，另外，借用车流量采集系统，并综合考虑了道路的物理长度和车辆密度因素。在路由节点的转发部分，采用使链路稳定的方案，通过对比同向和逆向选取下一跳节点的情况，可推出本算法的转发方案，即选择同向行驶的速度相差较近的车辆作为下一跳节点。同时，像经典协议那样，只考虑道路的物理长度而进行贪婪转发的机制是有缺陷的，所以，在算法中考虑道路的连通性对于提高网络的吞吐量是有必要的。

[1]Su W,Lee S J,Gerla M.Mobility Prediction and Routing in Ad Hoc Wireless Networks[J].International Journal of Network Management,2001,11(1):3-30.

[2]毕然,党梅.智能交通系统标准化现状及发展趋势[J].电信网技术,2011(4):44-47.

[3]Dijkstra E W.A Note on Two Problems In Connexion With Graphs[J].Numerische Mathematik,1959,1(1):269-271.

[4]Tee C,Lee A C R.Survey of Position Based Routing For Inter Vehicle Communication System[C].Distributed Framework and Applications,2008.Dfma 2008.First International Conference on.IEEE,2008:174-182.

[5]Tian J,Stepanov I,Rothermel K.Spatial Aware Geographic Forwarding For Mobile Ad Hoc Networks[J]，2002.

[6]Karp B,Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks[C].Proceedings of The 6th Annual InternationalConference on Mobile Computing and Networking.ACM,2000:243-254.

[7]Sherali Zeadally,Ray Hunt,Yuh-Shyan Chen,Et Al.Vehicular Ad Hoc Networks(VANETS):Status,Results,and Challenges[J]. Telecommunication Systems,2012,50(4):217-241.

[8]Karnadi F K,Mo Z H,Lan K.Rapid Generation of Realistic Mobility Models for VANET[C].Wireless Communications and Networking Conference,2007.WCNC 2007.IEEE.IEEE,2007:2506-2511.

VANET;Routing Protocols;Connectivity

Research on VANET Routing Algorithm

YUE Zhi-peng，ZHOU Yong，HUANG Hong

（College of Computer and Software Engineering,Xihua University,Chengdu610039）

1007-1423（2016）05-0012-06

10.3969/j.issn.1007-1423.2016.05.003

岳志鹏（1990-），男，四川江油人，硕士，研究方向为计算机网络

黄弘（1987-），女，山东烟台人，硕士，研究方向为软件工程师、Android开发2015-12-30

2016-02-13

车载自组织网络是专为实现车辆间通信而设计的无线自组织网络。然而，车载自组织网络的拓扑变化快等特点使它面临着挑战，其中需要解决的关键技术之一是路由选择问题。传统的自组织网络路由协议存在缺陷，不适用于车载自组织网络。经过对经典的路由协议的研究，给出一种适用于城市交通场景下的、基于地理位置的路由算法，主要包括路由的选择和数据包的转发两个部分。

车载自组织网络；路由协议；连通性

周永（1989-），男，四川广安人，硕士，研究方向为计算机网络

VANET is designed for the realization of communication between vehicle wireless self-organized networks.However,VANET topology changes fast and make it faces challenges,which need to be solved,is one of the key technologies of routing problem.Traditional self-organizing network routing protocol is flawed,it does not apply to VANET.After the classical studies of routing protocols,gives a suitable city traffic scene location-based routing algorithms,including the choice of the routing and packet forwarding two parts.