一种车辆自组织网络中基于RSU的分布式实时导航方法

摘要

本发明公开了一种车辆自组织网络中基于RSU的分布式实时导航方法，包括：路由请求信息和车辆位置报告的收集和处理；RSU间的区域穿越时延信息的交互和目的地区域时延的请求及应答；区域路径选择和域内路由设计；导航实施。本发明将整个网络划分为不同的区域，每个区域除了收集本区域的路由请求信息和车辆位置报告，仅和其他区域的RSU交互区域穿越时延信息和目的地区域时延信息，即可独立地为本区域内的车流进行路由决策，这种分布式信息采集和路由决策方式显著降低了导航算法的计算复杂度，提升了导航系统的实时性；本发明以域内平均时延最小为目标设计域内路由，通过分流的方式避免道路堵塞状况发生，保证了本方法具有很强的抗堵塞能力。

权利要求

1.一种车辆自组织网络中基于RSU的分布式实时导航方法，包括如下步骤：

(1)将整个车辆自组织网络划分成多个面积相近的区域，并在每个区域近中心位置的十字路口布置一个RSU；利用RSU周期性地收集每个区域内的道路状况信息；

(2)对于任一周期，RSU根据道路状况信息将本区域内的所有车辆按源地址和目的地址相近的原则归并为多条车流，并根据以下公式计算每条车流的到达速率：其中：λ(f)为本区域内车流f的到达速率，m(f)为一个周期内进入本区域的车流f的车辆数目，T为一个周期的时长，为本区域内的车流集合；

(3)RSU根据本区域内各条路段上的车流量计算出车流从不同方向穿越本区域到达其他相邻区域的区域穿越时延以及车流的目的地区域时延；进而以车流所穿越区域的区域穿越时延之和加上目的地区域时延作为最小化求解目标，为车流规划出一条区域行驶路径；

(4)根据车流的到达速率，由RSU为其管辖区域内开启导航服务的车辆设计区域内路由。

2.根据权利要求1所述的分布式实时导航方法，其特征在于：所述的道路状况信息包括开启导航服务的车辆在本区域内首次报告的源地址、目的地址以及车辆实时报告的当前地址。

3.根据权利要求1所述的分布式实时导航方法，其特征在于：所述的步骤(3)中RSU根据以下公式计算车流从不同方向穿越本区域的区域穿越时延：其中： 表示车流f从第j区域穿越本区域到达第k区域的区域穿越时延，第j区域和第k区域均与本区域相邻，j和k均为区域序号；Cr为本区域内路段r的容量，λr为本区域内路段r的车流量，vlimit,r为本区域内路段r的限速，Dr为本区域内路段r上平均每辆车的行驶时延，lr为本区域内路段r的长度； 为从第j区域与本区域相邻边界的第h入口穿越本区域到达第k区域行驶时延最小的路径，ej为第j区域与本区域相邻边界的入口总数；

为本区域内的车流集合。

4.根据权利要求1所述的分布式实时导航方法，其特征在于：所述的步骤(3)中RSU根据以下公式计算车流的目的地区域时延：其中： 表示车流f从第j区域至本区域目的地的目的地区域时延，第j区域与本区域相邻且本区域为车流目的地所在区域，j为区域序号；Cr为本区域内路段r的容量，λr为本区域内路段r的车流量，vlimit,r为本区域内路段r的限速，Dr为本区域内路段r上平均每辆车的行驶时延，lr为本区域内路段r的长度； 为从第j区域与本区域相邻边界的第h入口至本区域目的地行驶时延最小的路径，ej为第j区域与本区域相邻边界的入口总数；

为本区域内的车流集合。

5.根据权利要求1所述的分布式实时导航方法，其特征在于：所述的步骤(3)中RSU以车流所穿越区域的区域穿越时延之和加上目的地区域时延作为最小化求解目标，通过以下优化模型为车流规划出一条区域行驶路径，以特定区域Ak为例；

式中，Af＝{Af(1),Af(2),...,Af(mf)}表示车流f的区域路径；mf为车流f离开Ak区域后所经过的区域数目；Af(mf)为目的地所在区域；车流源地址所在区域Ak等同为Af(0)； 为Ak区域内的车流集合； 表示车流f沿着区域路径“第(j-1)个区域→第j个区域→第(j+

1)个区域”穿越第j个区域的平均时延； 表示车流f从区域Af(mf-1)与区域Af(mf)相邻的边界到达目的地的目的地区域时延。

6.根据权利要求1所述的分布式实时导航方法，其特征在于：所述的步骤(4)中RSU为其管辖区域内开启导航服务的车辆设计区域内路由的具体方法如下：RSU通过以下优化数学模型求解出本区域内每个路段的车流量：

其中：为本区域内所有车流总的行驶时延，N为本区域内所有车流到达速率之和， 为本区域内所有路段集合，λr为本区域内路段r的车流量，Dr为本区域内路段r上平均每辆车的行驶时延，Cr为本区域内路段r的容量，lr为本区域内路段r的长度，vlimit,r为本区域内路段r的限速；

T为一个周期的时长，q1和q2均表示本区域内任一与十字路口ig连接的十

字路口， 为本区域内所有与十字路口ig连接的十字路口集合，sf为车流f的源地址，df为车流f的目的地址， 为本区域内的车流集合，λ(f)为本区域内车流f的到达速率；

由于 通过FD分流方法确定出 进而对于本区域内的任一

十字路口，由RSU根据 的车辆比例关系为车流f中的车辆选择路段实施导航。

说明书

一种车辆自组织网络中基于RSU的分布式实时导航方法

技术领域

[0001] 本发明属于移动通信导航技术领域，具体涉及一种车辆自组织网络中基于RSU的分布式实时导航方法。

背景技术

[0002] 随着城市道路上的车辆个数越来越多，交通拥塞已经成为许多大城市面临的问题。它不仅浪费了人们的时间和资源，同时也产生大量的污染气体，影响人们的健康。根据实时道路状况信息进行导航，能够引导车辆避开拥塞区域，以最小的代价(如行驶时间或耗油量等)到达目的地。

[0003] 随着无线通信技术的发展，车辆自组织网络VANET(Vehicular Ad Hoc Network)成为一种实时收集道路状况信息的有效手段。它由装有车载单元OBU(Onboard Unit)的车辆和固定部署在路边的通信设施RSU(Roadside Unit)组成，能够支持车辆之间的V2V(Vehicle-to-Vehicle)通信和车辆与RSU之间的V2R(Vehicle-to-RSU)通信。装有OBU的车辆能感知自身的地理位置和移动速度等道路状况信息，这些信息能通过V2V和V2R通信传给相邻的车辆或者一个与各RSU相连的服务器，这些收集到的信息可以用来做实时的路由决策，为车辆提供代价最小的路径。

[0004] 现有的基于VANET的导航系统可以分为无网络设施和有网络设施两大类。无网络设施的系统为分布式系统，只由车辆组成；每个车辆通过信息交互自主地完成局部区域的道路状况信息收集，然后根据这些信息计算通过每段路的代价并为自己选择从当前位置到目的地的代价最小的路径，如文献“SoTIS-A self-organizing traffic information system”(作者L.Wischoff，发表于IEEE Vehicular Technology Conference，2003Spring)中所介绍。有网络设施的导航系统通常是通过网络设施(如RSU、固定传感器或基站等)辅助把全网道路状况信息聚集到服务器，再由该服务器对信息进行处理并为所有的车辆做路由决策，如文献“A vehicle route management solution enabled by wireless vehicular networks”(作者K.Collins，发表于IEEE INFOCOM，2008)中所介绍。

[0005] 无网络设施的导航系统的路由决策计算复杂度较低，但是由于各车辆独立计算，不同目的地的车辆可能会选择经过同一条路段，导致该路段拥塞，即造成新的拥塞。有网络设施的导航系统以全网所有车辆代价最小为目标，能在一定程度上避免出现新拥塞。例如，文献“NAVOPT:NavigatorAssisted Vehicular route optimizer”(作者W.Kim，发表于IEEE Conference on Innovative Mobile and Internet Services in Ubiquitous Computing，2011)中通过控制每个十字路口的单位时间内到达的车辆个数，使全网所有车辆到达目的地的平均行驶时延最小。但是，这种集中式的道路状况信息收集和路由决策限制了系统的扩展性。完整收集一个城市几百万车辆的信息需要时间较长(根据ISO中的文献“Traffic Message Channel using ALERT-C”介绍，已经商业化的导航系统Traffic Message Channel完成一次完整信息收集的时间为2～30分钟)，因此这种集中式信息收集方式并不适用于高速动态变化的车辆网络；而为所有车辆同时做路由决策的集中式导航算法的复杂度会随着车辆数量增多而显著增大，也不适用于大规模的网络场景。

发明内容

[0006] 针对现有技术所存在的上述技术问题，本发明提供了一种车辆自组织网络中基于RSU的分布式实时导航方法，能够显著降低导航算法的计算复杂度，提升导航系统的实时性。

[0007] 一种车辆自组织网络中基于RSU的分布式实时导航方法，包括如下步骤：

[0008] (1)将整个车辆自组织网络划分成多个面积相近的区域，并在每个区域近中心位置的十字路口布置一个RSU；利用RSU周期性地收集每个区域内的道路状况信息；

[0009] (2)对于任一周期，RSU根据道路状况信息将本区域内的所有车辆按源地址和目的地址相近的原则归并为多条车流，并计算每条车流的到达速率；

[0010] (3)RSU根据本区域内各条路段上的车流量计算出车流从不同方向穿越本区域到达其他相邻区域的区域穿越时延以及车流的目的地区域时延；进而以车流所穿越区域的区域穿越时延之和加上目的地区域时延作为最小化求解目标，为车流规划出一条区域行驶路径；

[0011] (4)根据车流的到达速率，由RSU为其管辖区域内开启导航服务的车辆设计区域内路由。

[0012] 所述的道路状况信息包括开启导航服务的车辆在本区域内首次报告的源地址、目的地址以及车辆实时报告的当前地址。

[0013] 所述的步骤(2)中RSU根据以下公式计算本区域内每条车流的到达速率：

[0014]

[0015] 其中：λ(f)为本区域内车流f的到达速率，m(f)为一个周期内进入本区域的车流f的车辆数目，T为一个周期的时长， 为本区域内的车流集合。

[0016] 所述的步骤(3)中RSU根据以下公式计算车流从不同方向穿越本区域的区域穿越时延：

[0017]

[0018] 其中： 表示车流f从第j区域穿越本区域到达第k区域的区域穿越时延，第j区域和第k区域均与本区域相邻，j和k均为区域序号；Cr为本区域内路段r的容量，λr为本区域内路段r的车流量，vlimit,r为本区域内路段r的限速，Dr为本区域内路段r上平均每辆车的行驶时延，lr为本区域内路段r的长度； 为从第j区域与本区域相邻边界的第h入口穿越本区域到达第k区域行驶时延最小的路径，ej为第j区域与本区域相邻边界的入口总数；为本区域内的车流集合。

[0019] 所述的步骤(3)中RSU根据以下公式计算车流的目的地区域时延：

[0020]

[0021] 其中： 表示车流f从第j区域至本区域目的地的目的地区域时延，第j区域与本区域相邻且本区域为车流目的地所在区域，j为区域序号；Cr为本区域内路段r的容量，λr为本区域内路段r的车流量，vlimit,r为本区域内路段r的限速，Dr为本区域内路段r上平均每辆车的行驶时延，lr为本区域内路段r的长度； 为从第j区域与本区域相邻边界的第h入口至本区域目的地行驶时延最小的路径，ej为第j区域与本区域相邻边界的入口总数；为本区域内的车流集合。

[0022] 所述的步骤(3)中RSU以车流所穿越区域的区域穿越时延之和加上目的地区域时延作为最小化求解目标，通过以下优化模型为车流规划出一条区域行驶路径，以特定区域Ak为例；

[0023]

[0024] 式中，Af＝{Af(1),Af(2),...,Af(mf)}表示车流f的区域路径；mf为车流f离开Ak区域后所经过的区域数目；Af(mf)为目的地所在区域；车流源地址所在区域Ak等同为Af(0)；为Ak区域内的车流集合； 表示车流f沿着区域路径“第(j-1)个区域→第j个区域→第(j+1)个区域”穿越第j个区域的平均时延； 表示车流f从区域Af(mf-1)与区域Af(mf)相邻的边界到达目的地的目的地区域时延。

[0025] 所述的步骤(4)中RSU为其管辖区域内开启导航服务的车辆设计区域内路由的具体方法如下：

[0026] RSU通过以下优化数学模型求解出本区域内每个路段的车流量：

[0027]

[0028]

[0029]

[0030]

[0031] 其中： 为本区域内所有车流总的行驶时延，N为本区域内所有车流到达速率之和，为本区域内所有路段集合，λr为本区域内路段r的车流量，Dr为本区域内路段r上平均每辆车的行驶时延，Cr为本区域内路段r的容量，lr为本区域内路段r的长度，vlimit,r为本区域内路段r的限速；T为一个周期的时长，q1和q2均表示本区域内任一与十字路口ig连接的十
字路口， 为本区域内所有与十字路口ig连接的十字路口集合，sf为车流f的源地址，df为车流f的目的地址， 为本区域内的车流集合，
λ(f)为本区域内车流f的到达速率；

[0032] 由于 通过FD(Flow Deviation)分流方法确定出进而对于本区域内的任一十字路口，由RSU根据 的车辆比例关系为车流f中的车辆选择路段实施导航。

[0033] 本发明的有益效果在于：

[0034] (1)本发明设计的导航系统将整个网络划分为多个面积相近的互不重叠的区域，每个区域的RSU只需收集本区域内的道路状况信息，并和其他区域的RSU交换区域穿越时延信息和目的地区域时延信息，即可独立地为本区域内的车流进行区域间路径选择和区域内路由设计；这种分布式的信息收集和路由决策方式，显著降低了导航算法的计算复杂度，提升了导航系统的实时性。

[0035] (2)本发明以时延最小为目标进行区域间路径选择，有效避开了拥塞区域；同时以域内平均时延最小为目标设计区域内路由，把车流分散到域内的道路上，从而避免或减轻道路堵塞，保证本发明提出的导航算法具有很强的抗堵塞能力。

附图说明

[0036] 图1(a)为本发明城市交通网络的区域层模型示意图。

[0037] 图1(b)为本发明特定区域的道路层模型示意图。

[0038] 图2为本发明的车流归并示意图。

[0039] 图3为本发明域内路由设计的流程示意图。

[0040] 图4为本发明导航方法的流程示意图。

[0041] 图5为本发明实际城市道路网络的仿真场景图。

[0042] 图6为本发明常规道路条件下的行驶时延仿真结果曲线图。

[0043] 图7为本发明拥堵道路条件下的行驶时延仿真结果曲线图。

具体实施方式

[0044] 为了更为具体地描述本发明，下面结合附图及具体实施方式对本发明的技术方案进行详细说明。

[0045] 本实施方式的道路网络由车辆、RSU和基站组成，如图1所示。图1(a)为一个城市交通网络的区域层模型，整个城市被划分为K个面积相近的互不重叠区域(图1(a)中K＝7)，记Ak为网络中的第k个区域， 为网络中所有区域的集合。图1(b)给出了一个特定区域的道路层模型，图中实线表示道路。每个区域中心位置的十字路口上布置一个RSU，这个RSU管辖着该区域内的所有车辆，即提供路由决策。每个RSU的通信范围(图中圆形虚线内区域)通常小于其管辖的区域范围。当车辆处于RSU的通信范围内时，它以V2R的方式直接与RSU进行信息传递；否则，以V2V和V2R结合的方式进行信息的多跳传递。

[0046] 车辆一旦进入一个新的区域，就会向当前所在区域的RSU发送一个路由请求，告知自己当前位置(源地址)和目的地。另外，车辆还周期地向当前所在区域的RSU报告自己的位置。这些实时道路状况信息的收集，是RSU给管辖区域内的车辆提供路由决策的必要前提。

[0047] 根据收集到的路由请求信息，RSU将管辖范围内的每个需要导航服务的车辆归并到若干车流中。具体的车流归并规则为：归并后车流的起始点为离该路由请求信息中的源地址最近的十字路口；归并后车流的终点为离该路由请求信息中的目的地址最近的十字路口。图2给出了车流归并的示意图，图中实线表示道路，车辆v请求从其起始点sv到达目的地dv，则其被归并到车流 (因为离sv和dv最近的十字路口分别为i1和i4)。由于每个车辆的源地址和目的地址都可能出现在网络中的任意位置，因此归并后将得到多个车流，即整个城市交通被建模为一个多车流模型。任一车流f的到达速率λ(f)则是根据上一个周期内归并到该车流的车辆数统计得到。值得注意的是，如果在上一周期内无车辆到达，则不更新车流的到达速率。

[0048] 根据收集到的车辆位置报告，RSU统计出管辖区域内的任意路段上的车流量(以路段r为例，车流量记为λr)，进而计算出从任意相邻区域穿越自身所在的区域到达另一个相邻区域的区域穿越时延，最后周期地把这个时延信息广播给其他区域的RSU。考虑到车辆密度的不断变化和车辆的快速移动可能导致V2V和V2R链路的时断时续，所以区域间信息传输是通过蜂窝网或其他有线网络完成的。图1(a)中以蜂窝网络为例描述RSU间的信息传输。这样，每个RSU就获得了车流从各个方向穿越其他区域的时延。

[0049] 本实施方式采用分层的模式进行路由决策。上层为区域层，要进行区域路径选择。下层为道路层，要进行域内路由设计。在区域层以时延最小为目标，RSU为源地址在其管辖区域而目的地在其他区域的车流选择区域路径，即依次穿越哪些区域。以特定区域Ak为例，具体的优化问题表示为：

[0050]

[0051] 式中，Af＝{Af(1),Af(2),...,Af(mf)}表示车流f的区域路径；mf为车流f离开Ak区域后所经过的区域数目；Af(mf)为目的地所在区域；为了表示方便，将车流源地址所在区域Ak等同为Af(0)； 为Ak区域内的车流集合； 表示车流f沿着区域路径“第(j-1)个区域→第j个区域→第(j+1)个区域”穿越第j个区域的平均时延； 表示车流f从区域Af(mf-1)与区域Af(mf)相邻的边界到达目的地的目的地区域时延。

[0052] 令从区域Af(j-1)进入区域Af(j)的入口数为ej-1；用Pj-1,j+1表示分别从Af(j-1)和Af(j)两个区域间的ej-1个入口进入并穿越Af(j)区域再到达Af(j+1)区域的所有代价最小的路径构成的集合；令从其中第h个入口进入并穿越Af(j)区域的代价最小的路径为 则车流f沿着区域路径“第(j-1)个区域→第j个区域→第(j+1)个区域”穿越第j个区域的平均时延 可由下式计算：

[0053]

[0054] 其中： 表示车辆在路径 的行驶时延，由该路径上所有路段的行驶时延之和计算得到：

[0055]

[0056] 这里的Dr为车辆在路段r的平均时延。通常情况下考虑路段r上的车流服从速率为λr的泊松分布，服务速率服从参数为Cr的指数分布，其中Cr为路段r的容量(由路段车道数和路段允许行驶速度等因素决定)。根据排队理论可知Dr为：

[0057]

[0058] 这里的lr和vlimit,r分别为路段r的长度和最大行驶速度。将公式(4)和(3)代入公式(2)即得到车流f沿区域路径“第(j-1)个区域→第j个区域→第(j+1)个区域”穿越第j个区域的时延计算式：

[0059]

[0060] 穿越每个区域的时延都可根据公式(5)计算得到的。目的地区域时延 也可按以下类似计算得到：

[0061]

[0062] 这里的 为从区域Af(mf-1)与目的区域Af(mf)相邻边界的第h入口至目的地行驶时延最小的路径， 为区域Af(mf-1)与目的区域Af(mf)相邻边界的入口总数。

[0063] RSU除了通过周期性交互收集从不同方向穿越其他区域的时延之外，当为特定车流进行路由决策时，也通过向目的地所在区域的RSU请求，来获得目的地区域时延。基于这些收集到的时延信息，RSU通过最短路由算法，如Dijkstra算法求解优化问题(1)，从而可为管辖范围内的每个目的地在其他区域的车流选择一条时延最小的区域路径。

[0064] 为每个车流选择完区域路径后，在道路层以所有车流的域内平均时延最小为目标，RSU为其管辖范围内的每个车流设计合适的域内路由方案。域内平均时延定义为区域内部总时延与车流到达速率总和之比，而区域内部总时延为区域内部所有路段上时延的车流量加权和。用 表示Ak区域内所有车流的平均时延；用 表示Ak区域所有路段集合。由于区域内任意路段上的时延都采用公式(4)描述，则Ak的域内平均时延为：

[0065]

[0066] 其中， 为区域Ak内所有车流到达速率之和，在路由设计时刻数值已知。

[0067] 区域Ak内路由设计优化问题的数学模型为：

[0068]

[0069]

[0070]

[0071]

[0072] 式(8a)以Ak区域内所有车流的平均时延最小为目标求域内最优的车流总量分布。式(8b)是十字路口车流量守恒约束，保证每个十字路口的车流流入量等于车流流出量。其中， 为区域Ak中的第g个十字路口， 为区域Ak内所有十字路口的集合； 是Ak区域内与ig相邻的十字路口构成的集合； 表示流入十字路口ig的车流f分量； 表
示流出十字路口ig的车流f分量；sf和df分别为车流f的源十字路口和在区域Ak内的目的十字路口。约束式(8c)是保证每条路段的车流量非负，其中 为车流f在路段r上的分量。约束式(8d)是保证Ak区域内各路段的车流量始终小于该路段容量。

[0073] 在区域内的具体道路层(图1(b)给出一例)求解优化问题(8)，RSU将获得所管辖区域内所有路段上的最优总车流量分布。为此，以Ak区域内为例，任一车流f的在域内所有路段上的车流量分布向量为 车流量分布矩阵和路段车流总量分布向量 这里的 和 分别为Ak区域内
的路段总数和车流总数。由于路段r上的行驶时延 是该路段的车流到达速率
λr的严格凸函数， 所以域内平均时延 关于λ构成一个严格凸球面。同时，由于区域Ak内各个路段上车流总量为该路段上所有车流分量的线性相加(即
)， 相对于路段车流量分布矩阵Λ也构成一个严格凸球面。由此可知，该目标函数存在稳定点，且为全局最优解。

[0074] 基于上述分析，域内路由设计问题(8)是一个凸优化问题，本实施方式采用现有的凸优化方法求解，如文献“NAVOPT:NavigatorAssisted Vehicular route optimizer”(作者W.Kim，发表于IEEE Conference on Innovative Mobile and Internet Services inUbiquitous Computing，2011)中提出的FD(Flow Deviation)分流方法。该方法具体的解法流程在图3中给出，其步骤如下：

[0075] (1)令n＝0，通过现有的最短路由算法之一(如Dijkstra算法)找到一个初始的路段车流量分布矩阵Λ(0)；

[0076] (2)令n＝n+1，更新路段车流量分布矩阵Λ(n+1)＝(1-α)Λ(n)+αS。其中0＜α＜1，S是以 为每条路段的代价时，所有的车流都经过代价最小的路径时的车流量分布矩阵；

[0077] (3)如果条件(8d)成立且满足 (其中λ(n)为Λ(n)各行的线性相加)，则输出Λ(n)作为最优的路段车流量分布矩阵Λopt并进入步骤(4)；否则返回步骤(2)；

[0078] (4)由Λopt构建任意车流的行驶路径，以车流f为例，记其在Ak区域内所有可能经过的路径组合以及每条路径上的车流量比例为 和其中pw和ηw分别为第w条路径和车流f在第w条路径上的比例分量。

[0079] 步骤(4)中Wf为车流f在Ak区域内所有可能经过的路径的总数。为了计算车流f在任一路径pw上所占的比例，令路径pw上十字路口的集合为{i1,i2,...,iz}，则车流f在该路径上的车流比例 上述表达式中 为车流f从十字路口iu流向iu+1的车流量与车流f从十字路口iu流出的车流总量之比。

[0080] 综上所述，经过步骤(1)到(4)，本地RSU为区域Ak内的所有车流设计得到具体的域内路由方案。

[0081] 下面我们将上述RHD(RSU-based Hierarchical and Distributed)导航方法应用于城市道路网络场景下的路由决策，此时的路由决策是周期性进行的，其中任一个周期内的流程图如图4所示，包括如下步骤：

[0082] (1)S101，路由请求信息和车辆位置报告的收集和处理；

[0083] 当网络中的任意车辆进入一个新的区域，立即向当前所在区域的RSU发送一个路由请求信息，告知自身的当前位置和目的地位置。另外，车辆还周期地向所在区域的RSU报告自己的位置。

[0084] 本地RSU在该周期内收集管辖区域内所有的路由请求信息和车辆位置报告。根据收集到的路由请求信息以及车流归并规则，本地RSU将每个车辆归并到特定车流中，进而统计每个车流在该周期内的到达速率。根据收集到的车辆位置报告，本地RSU统计出管辖区域内的每条路段的车流量。

[0085] (2)S102，区域路径选择；

[0086] 每个RSU根据该周期内统计的路段车流量，计算从各个方向穿越本区域的时延，并在下一周期开始时，将该区域穿越时延广播给其他区域的RSU。

[0087] 本地RSU通过蜂窝网络为每个目的地在其他区域的车流向其目的区域的RSU发送一个目的地区域时延请求。收到请求后，目的区域RSU根据该周期内统计的路段车流量计算该车流的目的地区域时延，并通过例如蜂窝网进行反馈。

[0088] 利用现有的最短路由算法之一(如Dijkstra算法)求解优化问题(1)，每个区域的RSU为源地址在其管辖区域而目的地在其他区域的每个车流选择区域路径。

[0089] (3)S103，域内路由设计；

[0090] 通过FD分流方法求解优化问题(8)，每个RSU为其管辖区域内的所有车流设计具体的域内路由方案。

[0091] (4)S104，导航实施；

[0092] 根据步骤(2)中下一个周期开始时得到的区域路径选择方案和域内路由方案，每个区域的RSU为下一个周期内到达其管辖区域的车辆提供实时导航服务。

[0093] 本发明技术方案的有益效果可以通过计算复杂度分析得到验证。

[0094] 若RHD导航算法中的域内路由设计采用FD分流方法，且各个区域的FD分流方法中的迭代次数都为N1。参照FD分流方法的迭代过程，该方法的复杂度主要取决于最短路由的计算。如果最短路由的计算采用Dijkstra算法，则RHD导航算法的复杂度为：

[0095]

[0096] 式中第一项 为区域路径选择的计算复杂度，取决于区域个数K。式中第二项中的 为区域Ak的域内路由设计的计算复杂度，它主要取决于域内十字路口个数 因为各个区域分布式进行路由决策，故域内路由设计的复杂度取决于取各个区域的最大值。

[0097] 假设集中式导航算法也采用FD分流方法。记该方法的迭代次数为N2(由于整个网络中的道路数目远大于一个区域的道路数目，因此N2通常远大于N1)，则集中式导航算法的复杂度取决于网络中所有十字路口个数 为：

[0098]

[0099] 对比公式(9)和公式(10)可知，RHD导航算法的计算复杂度显著低于集中式导航算法。

[0100] 本发明技术方案的有益效果还可以通过行驶时延性能的仿真进行验证。

[0101] 图5所示仿真场景为杭州市西湖区的部分道路网络，网络的覆盖范围为6000m×4000m，包含218条双车道路段，每条路段的长度已在图中标注。整个网络中被划分为面积相近的6个区域，每个区域的近中心十字路口上布置着管辖该区域的RSU。在仿真中，每条车道的容量都设置为2000车辆/小时，则所有路段的容量都为4000车辆/小时。设置3个车流(即图中的车流1、车流2和车流3)，并控制每个车流都具有相同的泊松到达速率，且速率不超过
5000车辆/小时。

[0102] 为了通过对比验证本发明提出的RHD导航算法的有效性，本发明选择了现有的集中式导航算法和最短路径导航算法进行性能对比。集中式导航算法是针对整个网络建立优化模型实现时延最小化，并用FD分流方法进行求解。其优点为得到的解为全局最优，因而性能最佳，其缺点为当网络覆盖范围较大或者车辆较多时，计算复杂度过高。最短路径导航算法则是通过Dijkstra算法为每个车流独立地找到一条最短路径，随后让整个车流上的车辆都通过该最短路径到达目的地。最短路径导航算法与集中式导航算法的区别在于少了分流迭代过程，降低了复杂度的同时也损失了算法性能。

[0103] 图6给出了常规路况条件下RHD导航算法及其对比导航算法的性能仿真结果。所谓常规路况条件指的是除了给定的3个车流外每条路段上没有其他车辆通过。由图可见，在各种到达速率下，集中式导航算法的平均车辆行驶时延总是略小于RHD导航算法。这是因为集中式导航算法是在整个范围中进行优化求解，得到的路由方案是全局最优的；而本发明提出的RHD导航算法则是通过区域路径选择和域内路由设计进行路由决策，得到的路由方案是次优的。由图还可见，另一种比较算法最短路径导航算法在到达速率达到2000车辆/小时/车道时，行驶时延曲线呈垂直型，即进入拥堵状态。虽然RHD导航算法的性能不如集中式导航算法，但当到达速率增大到5000车辆/小时后并未出现道路堵塞状态。这是因为RHD导航算法在区域内部通过分流的方式尽量防止道路堵塞，这表明本发明提出的RHD导航算法在大大降低计算复杂度的前提下仍有较强的防堵塞能力。

[0104] 图7给出了拥塞路况条件下性能仿真结果。所谓拥塞路况条件是除了给定的3个车流外，区域2中每条道路上还存在着其他车流，并且到达速率为3000车辆/小时。从图中可以发现，随着车流到达速率的增加，最短路径导航算法、RHD导航算法和集中式导航算法先后进入拥塞状态。RHD导航算法的抗堵塞能力虽弱于集中式导航算法，但明显强于最短路径导航算法。

[0105] 综合图6和图7可知，本发明提出的RHD导航算法在遇到车流到达速率增加和部分道路拥塞时，能够以比较小的计算复杂度实现有效的车辆分流，避免堵塞状况的发生。

[0106] 显然，本领域的技术人员可以对本发明进行各种改动和变形而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变形属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变形在内。