摘  要： 利用车载自组网方便、灵活、成本低的特点，使用机会通信扩展车辆通信范围，提出一种基于停车位可用概率的停车位发现算法来解决分布式网络中信息不完全下的停车位发现问题。通过估算附近可用停车位在车辆到达时刻的可占用概率，为车辆分配成功率最大的停车位。仿真结果表明，该算法适用于车载自组网的分布式停车位算法，平均停车时间较短。

　　关键词： VANET；停车；机会通信；概率

0 引言

　　私人汽车的激增使城市道路交通量日益增加，引发了一系列亟待解决的交通问题。其中，停车问题给大城市带来了沉重的道路通行负担，并成为交通拥堵的重要因素。如何采用先进的科学技术方法来解决“停车难”问题[1]，是当前城市交通发展急需解决的问题。

　　在停车位发现服务中，拓扑网络结构变化快速，集中式的架构缺乏灵活性和适应性，车载自组织网络（Vehicular Ad Hoc Network，VANET）提供了一种分布式停车位发现解决方案[2]。在分布式的VANET系统中，车辆节点通过与通信范围内的节点组成临时的Ad hoc网络进行多跳通信、交换信息[3]，VANET在智能交通系统中起着重要作用，为系统提供统一的无线通信网络及多种通信方式。

1 相关工作

　　2006年Caliskan等[2]提出了一种基于车载自组网的分布式停车位发现模型，通过阶段性信息采集进行停车位计算。2007年，Sherisha等[4]提出使用停车场历史数据计算车辆目的地附近的停车位可用概率的方法为车辆提供停车引导。Murat[5]对停车位发现问题建立了概率预测模型，从统计角度对区域停车概率进行了预测。2009年Mathur等[6]提出了一种集中式和一种分布式方案来解决寻找停车位问题，并对停车位发现思想予以评估。2011年，Kokolak等[7]提出了一种分布式的机会停车位发现算法，可以扩展个体车辆的通信范围。2012年，Andreas[8]对Murat数据收集方法和模型进行了改进，优化了转移矩阵。

　　现有停车位概率预测算法主要是从统计角度预测停车位空闲的概率，但是不能具体为停车位发现提供明确的决策目标。本文提出一种基于停车位可用概率的停车位发现算法（An Available Probability based Parking Algorithm，APPA），在分布式系统中使用机会通信扩展车辆通信范围，估算车辆到达停车位时的车位可用概率，为车辆分配最佳的可用停车位，规划有效的行驶路径。

2 前期假设与模型分析

　　2.1 停车位信息获取

　　限于通信半径的影响，车辆节点能感知的停车位有限，使用报文交互扩大节点的感知范围，使节点的停车位决策超出局部VANET网络，扩大到环绕车辆的VANET网络群，做出更加符合整体利益的决策。

　　在车辆行驶过程中，不断侦测可用的停车位信息，当侦测到可用停车位时，记录该停车位的位置信息，同时记录该停车位的时间戳。并在路边设置少量的RSU，维护一个标准的时间和一张可用停车位信息表。当车辆进入RSU通信范围时，交换可用停车位的信息，更新可用停车位信息，使得车辆能得到超出自身通信范围的可用停车位信息。

　　2.2 距离计算标准

　　从地理位置信息角度考虑，将道路网络转化为有向图。以道路作为拓扑网络中的线，并以停车位和车辆作为拓扑网络中的节点，赋予停车位和车辆地理二维坐标。转化道路平面图的同时做如下约定：

　　（1）对道路和道路交叉口赋予不同的量化值；

　　（2）对每个道路交叉口赋予一个额外的平均等待时间；

　　（3）由于算法的依据是有效距离，因此把等待时间结合预定的车辆速度转化为距离，这个距离也是有效距离的组成部分；

　　（4）使用Dijkstra算法计算节点间距离。

　　2.3 模型分析

　　在车辆位置信息不完全的模型中存在两种对停车位有需求的车辆，一种是加入车载自组网并实时共享信息的车辆，其他车辆能通过车载网得到这些车辆的位置信息，位置信息由GPS设备提供；另一种车辆是没有加入车载自组网的车辆，它们自发且随机地搜索停车位，网络中的车辆无法得知这些车辆的数量和位置等信息。在这种情况下，停车问题变得非常复杂，如果通过分配预约等方式为车载自组网中的车辆分配停车位，则在车辆向预定车位行驶的过程中，既定停车位很可能已经被不在网络中的车辆所占据，显然固定分配的停车位发现方式不适用于此模型。

3 主要工作

　　3.1 车辆到达时间计算

　　在信息交互过程中，车辆互相传播停车位信息，在获取的报文中，如果存在本地链表没有的车位，则记录该车位位置信息及时间戳；如果已经存在，则更新时间戳，时间的记录以最早发现该停车位为准。

　　当车辆占用某停车位后，则时间戳设为0，并向其他车辆转发一次该停车位信息，同时将本地的停车位节点删除。当其他车辆接收到时间戳为0的停车位信息时，进行相同操作。

　　假设当前时刻为t，车辆行驶速度为v，根据Dijkstra算法计算得到的车辆与停车位之间的最短路径为D。在得到可用停车位的位置信息后，可以根据Dijkstra算法和车辆的行驶速度估计得到车辆相对每个停车位的到达时间：

　　3.2 可用车位获取概率计算

　　假设车辆vi对一个车位sj的可用概率为P（vi，sj）：

　　式中，P（vi，sj）为T时刻停车位sj被其他车辆占用的概率。要计算车辆到达时刻的停车位可用概率，只需计算P（vi，sj）即可。

　　P（vi，sj）主要受两个因素的影响：一个是停车位的空闲时长，即从停车位空闲时刻开始至车辆发起停车请求，这段时间的车位没有被占用，但车位被选择的概率会随着时间的延长而累积，下一时刻被占用的概率随之增大；另一个是当前时刻至车辆到达停车位，此时车辆与其他所有可能驶向此车位的车辆进行竞争，车辆距离停车位越近，胜出的可能性越高。

　　在参考文献[9]中，针对计算实时可用停车位的变化进行了大量实验，得到了关于停车场各个时刻停车位占用情况的实验数据。本文引用这些实验数据，并通过分析，将历史数据抽象为函数，该函数表示车位被占用概率随时间的变化关系，简化了算法的复杂度，提高了算法效率。函数如式（3）所示：

　　其中c=86 400-a+b。

　　令概率Ph（sj）表示在t时刻可用停车位sj被任意一辆车占用的概率，其中包括没有加入车载自组网的车辆。那么，从停车位sj空闲时刻开始至当前时刻t，认为其在t时刻后被任意车辆占用的概率为：

　　Ph（sj）=Pr（t）（4）

　　其中t为当前时刻。

　　设从停车位sj空闲时刻t开始，停车位的空闲时间和停车时间服从指数分布，则车辆节点流量可以看作一个泊松过程（λ）。那么，Pn（vi，sj）可以由式（5）计算得到：

　　Pn（vi，sj）=1-P（K=1）（5）

　　其中，T为记录的车辆到达时刻，P（K=1）可看作到T时刻停车位被占用的概率。

　　那么，最终的停车位可用概率可由式（6）得到：

　　P（vi，sj）=（1-Ph（sj））·Pn（vi，sj）（6）

　　即P（vi，sj）可以由式（7）表示：

　　P（vi，sj）=1-P（vi，sj）=（1-Ph（sj））·Pn（vi，sj）（7）

　　P（vi，sj）越大，则到达时刻的停车位可用概率越高。

　　3.3 算法描述

　　车辆在行驶过程中，不断侦听感知范围内的可用停车位，同时进行车间报文交互。当发起停车请求时，计算车辆与每个可用停车位之间的有效距离，并通过APPA算法计算每个可用停车位的概率，选择概率最高的停车位并向其行驶，在行驶过程中，不断重复进行侦听和概率更新，始终驶向最大可用概率的停车位；当与某停车位距离D小于阈值Z（Z=v）时，占用停车位并将此停车位的时间戳置0。算法伪代码如下：

　　FUNCTION APPA（S）{

　　for所有的停车位节点S

　　{  计算车辆与停车位之间距离D

　　IF D<Z

　　{

　　占用停车位，时间戳置0

　　END

　　}

　　}

　　for所有的停车位节点S

　　{

　　Ph（sj）=Pr（t）

　　Pn（vi，sj）=1-P（K=1）

　　P（vi，sj）=（1-Ph（sj））·Pn（vi，sj）

　　}

　　Pmax（vi）=max（1-P（vi，sj））

　　向Pmax（vi）车位方向行驶1 s，同时更新S

　　RETURN FUNCTION APPA（S）

　　}

4 仿真分析

　　4.1 场景描述

　　本文在VanetMobiSim框架下进行仿真，仿真过程中，每当一辆车占用一个停车位时，保存记录这辆车找寻停车位所花费的时间，并在整个道路上随机位置重新生成一个车辆，在另一随机位置重新生成一个可用停车位。这可看作道路交通中的实时变化因素，更加符合实际情况。具体参数见表1。

　　4.2 仿真分析

　　仿真场景中停车位节点数为30，车辆节点数为5~80，且设定隐藏车辆与非隐藏车辆数量比约为1∶1。

　　图1表示停车位节点数和车辆平均行驶时间的关系曲线。当车辆数少于停车位时，每个车辆都能分配到停车位，APPA算法根据有限的信息找到最优的车位，产生的额外行车开销较小，且在行驶过程中，实时地更新数据，使车辆更大概率获取位置更优的可用停车位；当车辆数目多于停车位时，APPA算法能根据已知信息做出更加合理的决策，使车辆能在车位很少时更快地找到可用停车位。

　　图2表示停车位平均空闲时间的关系曲线。由图2可知，APPA算法的停车位平均空闲时间与就近原则方法接近，略优于就近原则。当可用停车位数目较多时，车辆有更多的停车选择，APPA算法的决策拥有最大的成功概率；在车辆数目大于停车位数目时，车辆之间存在激烈的竞争，由于APPA算法计算了停车位从空闲时刻开始至发起停车请求这段时间对停车占用概率的影响，因此能提高车辆寻找车位的有效性。

5 结束语

　　本文对分布式系统中车辆和停车位位置信息不完全的模型进行研究，提出了一种基于停车位可用概率的停车位发现算法来解决分布式网络中信息不完全情况下的停车位发现问题。通过仿真分析得知，在系统模型中，APPA算法有较大的优越性，其能更好地应对信息不完全的情形，缩短车辆的平均停车位发现时间。

参考文献

　　[1] DELOT T， ILARRI S， LECOMTE S， et al. Sharing with caution： Managing parking spaces in vehicular networks[J]. Mobile Information Systems， 2013，9（1）：69-98.

　　[2] CALISKAN M， GRAUPNER D， MAUVE M. Decentralized discovery of free parking places[C]. Proceedings of the 3rd International Workshop on Vehicular ad hoc Networks. ACM， 2006： 30-39.

　　[3] YOUSEFI S， MOUSAVI M S， FATHY M. Vehicular ad hoc networks（VANETs）： challenges and perspectives[C]. ITS Telecommunications Proceedings， 2006 6th International Conference on. IEEE， 2006： 761-766.

　　[4] PULLOLA S， ATREY P K， EL SADDIK A. Towards an intelligent GPS-based vehicle navigation system for finding street parking lots[C]. Signal Processing and Communications， 2007. ICSPC 2007：1251-1254.

　　[5] CALISKAN M， BARTHELS A， SCHEUERMANN B， et al. Predicting parking lot occupancy in vehicular ad hoc networks[C]. Vehicular Technology Conference， 2007. IEEE 65th. IEEE， 2007： 277-281.

　　[6] MATHUR S， KAUL S， GRUTESER M， et al. ParkNet： a mobile sensor network for harvesting real time vehicular parking information[C]. Proceedings of the 2009 MobiHoc S 3 workshop on MobiHoc S 3. ACM， 2009： 25-28.

　　[7] KOKOLAKI E， KARALIOPOULOS M， STAVRAKAKIS I. Opportunistically assisted parking service discovery： now it helps， now it does not[J]. Pervasive and Mobile Computing， 2012， 8（2）： 210-227.

　　[8] KLAPPENECKER A， LEE H， WELCH J L. Finding available parking spaces made Easy[C]. Proceedings of the 6th International Workshop on Foundations of Mobile Computing. ACM， 2010： 49-52.

　　[9] 鲁忠辉.基于VanetMobiSim/NS-2的车载自组网的研究与仿真[D].武汉：武汉理工大学，2010.