一种基于车载自组网的停车位协作发现算法

李 鹏，李德敏，张晓露

（东华大学 信息科技与技术学院，上海 201620）

在停车位发现服务中，由于车载自组网的拓扑结构具有快速频繁变化的特点，使得原有的C/S构架网络缺乏灵活性和适用性，而车载自组织网络(Vehicular Ad Hoc Network，VANET)提供了一种分布式停车位发现解决方案[1]。在分布式的VANET系统中，车辆节点通过与通信范围内的节点组成临时的ad hoc网络来进行多跳通信、交换信息（包括实时的驾驶者信息、路况信息以及非实时的交通模式信息）[2]，这为分布式停车位发现提供了数据通信基础。

2006 年Caliskan等人[3]在提出了一种基于车载自组网的分布式停车位发现模型，通过阶段性信息采集来进行停车位计算。Mathur等人[4]在2009年提出了一种集中式和一种分布式方案来解决寻找停车位问题。在集中式方案中车辆节点安装超声波传感器，沿道路行进过程中收集停车位数据信息，然后向中央服务器提出申请来得到停车位分配服务。同时阐述了分布式停车系统的重要性。2010年Mathur等人[5]对集中式停车位发现思想予以实现和评估。2011年, Kokolaki等人[6]提出了一种分布式的机会停车位发现算法（OAPS -Opportunistically Assisted Parking Search），其基本思想是车

辆节点在停车位搜寻过程中与网络中的邻居节点进行分布式机会通信，交换路况信息和停车位信息，基于这些储存在缓存中的信息按照抢占式原则计算出最近且最可达的停车位。

在具有代表性的OAPS算法中，机会通信可以让车辆灵活的掌握网内邻居节点的信息从而使停车位决策具有很大的智能性，但由于抢占式的原则，不能很好的体现整体的系统性能。因此本文基于OAPS提出了一种协作式停车位发现算法（简称COAPS- Collaborative OAPS）。该算法使用机会通信方式，利用车辆和停车位的数据信息来实现一种车辆与停车位协作交互，具有较好系统利用率的停车位分配机制，从而在性能上获得两方面的优势：1)在分布式系统的灵活、成本低的特点下，克服车辆节点的“自私竞争”，做出最大限度满足自身和全局的停车位选择；2)车辆节点通过与停车位的报文交互来扩展通信范围，获得比车辆通信范围内更大的信息量，从而做出具有协作特点的决策。

1 COAPS策略描述

1.1 问题描述

典型的停车位发现服务的问题描述在[6]已有叙述，其场景主要由地理信息、车辆节点及停车位节点组成，如图1所示，（方块代表车辆节点，实心点代表停车位，圆圈Mij代表路径的交叉口节点）。

图1 停车位发现服务场景示意图Fig. 1 Typical scene of parking lot discovery service

基于图1场景信息停车位发现算法可描述为：车辆节点如何在与邻居节点竞争与协作的情况下从可用的停车位节点中找出最有可能占用且尽可能兼顾邻居节点利益的最优停车位。

OAPS基于抢占式原则总是选择个体指标最好也即最近的停车位，在典型的节点竞争场景下其停车位选择如图2所示。

图2 OAPS车辆节点竞争Fig. 2 Competition of vehicles in COAPS

由图2可知，车辆节点 具有两个距离相近的停车位P0和 P1，但是占用P1后对节点N1造成了很大的额外路径开销，缺乏协作性。这种不良竞争会造成邻居节点的利益损失，也是COAPS主要解决的问题，图3是COAPS的理想竞争示意图。对比图2、图3可知，如果要兼顾邻居节点的利益就需要对邻居节点的路径开销予以考虑，使得每个车辆节点的决策能够体现局部的整体效益。因此COAPS在选择停车位时会计算邻居节点的开销，以VANET网络内各节点的综合开销作为衡量标准。但考虑每个节点选择合作的倾向性不同，因此需要在个体开销和邻居节点开销的权重及优先级上予以体现（详见第2节）。

1.2 策略描述

图3 COAPS车辆节点竞争Fig. 3 Competition of vehicles in COAPS

停车位发现服务的核心是如何在拓扑结构频繁变换的网络场景中为车辆节点及时找到“最优”的停车位。“最优”的评价通常是通过两个层次的指标来予以衡量[1]：一是个体指标，即如何让车辆节点以最短时间找到停车位；二是系统指标，如何让停车位区域的停车位利用率达到最高。OAPS基于抢占式原则主要面向个体指标，COAPS则是综合考虑两种指标，在尊重个体指标情况下最大限度兼顾系统指标。

为了获得节点的协作性，COAPS中的车辆节点以自己和邻居节点的均衡开销作为总开销，通过调节邻居节点开销的权重来改变节点的协作倾向，但当邻居节点和停车位节点数量较多时，最优解的求解变得非常缓慢低效，因此引入具有全局性能优化的模拟退火算法可以显著提高求解效率，同时针对停车位组合优化问题的非凸型，避免陷入局部最优。

在模拟退火的算法框架下，COAPS中的车辆节点与其邻居节点首先在可选停车位中任意分配产生初始解（同时作为当前解），在随后从高温到低温的模拟退火过程中不断的由当前解产生新解，同时以各节点的整体路径开销作为性能评价指标来确定其优劣性，以大概率接受更优解，以小概率接受次优解（跳出局部最优），当温度达到最低（算法的终止条件）时即得出最终的最优停车位。每个节点依次进行运算即可得到其相应的停车位，至此在单一节点间完成了协作。但在不同节点间仍会出现停车位冲突也即竞争的情况，此时通过节点与其最优停车位之间的报文交换，由相应停车位来从冲突的节点中选择最优节点，拒绝其他次优节点，由此来完成多节点之间的协作。

以下是COAPS算法的总体描述，下一节将给出具体的算法实现细节：

Step1：车辆节点从可用停车位中随机选择一个停车位以及参与竞争的邻居节点集合，生成初始解，同时作为当前解（详见2.1）；

Step2：由当前解产生新解，对当前解进行更新（详见2.2）；

Step3：计算节点开销作为评价解的性能指标，对当前解进行筛选（详见2.3）；

Step4：由初始解依次从高温向低温收敛，以Step3的性能指更新最优解（详见2.4）；

Step5：与解得的最优停车位进行报文交互，确定是否可占用。（详见2.5）；

2 COAPS算法

基于1.2节的COAPS算法策略描述，本节将阐述算法的具体实现细节。

下面首先对COAPS所用到的基本参量进行定义说明：

-V={V1,…V2…VN},1≤i≤x, 为车辆节点集合，x为车辆节点数目；

-Ni={,……},1≤j≤y,1≤i≤x为车辆节点在VANET网络范围内的邻居节点， 为邻居节点数目；

-Pi={,……},1≤j≤z,1≤j≤x为Vi传感感知到的和邻居节点告知的停车位；

-C={V1,…V2…Vi}，V ∈ V，∈Pi为节点Vi到停车位的开销。

-α:为节点的协作参数。

2.1 停车位的初始解

COAPS算法首先为节点Vi从可用停车位Pi中随机选取停车位。由于邻居节点和停车位数量不确定，因此参与竞争的邻居节点Ji的数量为邻居节点数量和停车位数量的最小值：

Ji为邻居节点集合的一个随机子序列，其数量为min(|Pi|,|Ni|) 。同理Ki对应的可选的停车位集合Ki为：

2.2 停车位的新解

对于节点Vi，其新解是在当前解的基础上产生的，目的是在当前状态下产生新的更优解，来达到进化演算的目标。由于解是一个行向量序列，因此可以采取二交换的形式产生新解。

由于Ji是邻居节点Ni的一个不完全子集，因此其补集的信息同样需要考虑，这里我们设Ji的补集为Ji。在进行交换前，首先从Ji集合选出两个待交换元素和，再从Ji集合选出一个待交换元素，于是满足：

为了让Ji和Ji'同时参与选择，利用0～1的概率随机数 α对进行交换，即：

交换的结果便是更新Ji和Ji'。Ki的更新与Ji类似，不同之处在于与的关联，因此需在、、与四者之间进行概率交换，即：

为了加速解的更新还需引入三交换，即在Ji和Ki中选出3个变量进行交换，原理与二交换一样，需要再引入一个随机数 在二交换和三交换之间进行概率均衡，即：

2.3 停车位的开销计算

在节点Vi选取停车位情况下，首先计算Vi到的开销为 Dijkstra（Vi，），其中Dijkstra是以道路节点为无向图计算出的两个节点间最短路径。然后计算邻居节点开销，并用节点的合作倾向参数α进行均衡，于是Vi对于停车位Picur的最终路径总开销C（Vi，）为：

考虑到不同节点的邻居节点和可用停车位数量不同，且存在节点不可达的情况，因此用VANET网内各节点的平均路径开销来统一表示。α表征节点与邻居节点的协作程度，α=0时协作程度最低，退化为OAPS，α=1时协作程度最高，不考虑自身利益（通常α=0.5 ）。

2.4 停车位的最优解

对于节点Vi，其最优停车位即是以C（Vi，）为目标函数的最优解。在模拟退火中，以作为初始解和当前解，以 C（Vi，）作为内能依次从高温向低温靠近，同时保持对当前最低内能及对应当前解的记录，以大概率接受新的最优解，小概率接受次优解作为当前解，从而最终算出达到最低温度时的最优停车位（最优解），即：

2.5 车辆节点—停车位的报文交互

以上得到的关于节点Vi的最优停车位反映的是VANET网内信息，限于通信半径的影响，节点的决策不能很好的体现以停车位为中心的区域信息。作为V-V(Vehicle-to-Vehicle)通信的一种重要途径，以报文为载体的信息传递交互使得车辆节点不仅能获取如停车位等相关场所信息，同时避免一些有害的场景[7]。因此与停车位的报文交互一方面可以扩大节点对停车位的感知范围，另一方面可以扩大停车位对车辆节点的控制范围，使节点的停车位决策超出局部VANET网络，扩大到环绕停车位的VANET网络群，表现系统指标。

因此每个节点Vi在算得最优停车位后，将计算出的总路径开销C（Vi，）发送申请报文给，从接收到的申请报文中选出开销最小的节点向其发送确认报文，确认其被分配成功，并向其他节点发送拒绝报文。收到拒绝报文的节点开始新一轮的停车位搜索。

3 仿真与分析

车载自组网算法仿真主要分为交通仿真(Traffic Simulation)和网络仿真(Network Simulation)[8]，停车位发现算法侧重于应用层的交通仿真（不考虑网络层的丢包率等），因此在VanetMobisim(VANET运动模型及交通仿真平台)的框架基础上用Java语言扩展算法模型，对COAPS与OAPS进行对比仿真，仿真环境描述如下：

仿真场景范围：1 200 m×1 200 m

车辆平均行驶速度：40 km/h

车辆通信范围：200 m

车辆数目：5～80

停车位通信范围：100 m

停车位数目：30

道路网格参数（水平/垂直方向道路的数量）：20×20

为了表现典型的实际情况，地图采用网格道路模型，随机生成20×20的道路，车辆节点和停车位的起始位置随机均匀分布于区域中，按照节点数量的不同分别进行多次仿真，取统计均值来消除节点分布不同所造成的影响。仿真结果如图4所示。

图4 车辆节点搜寻停车位的平均行驶时间仿真对比Fig. 4 Comparative simulation of vehicles’ average parking lot discovery time

图4为车辆节点搜寻停车位的平均行驶时间，停车位数量为30，车辆节点数目为5～80。分析图4可知，在车辆数目少于停车位数量的情况下，由于所有节点最终都可以分配到停车位，COAPS与OAPS的平均搜寻时间相比差别不是很大，COAPS仅仅是在路径规划上略优于OAPS。当车辆数目接近于停车位数目时便出现了竞争，于是OAPS所造成的资源浪费开始显现出来，因为节点对最近停车位的盲目抢占极有可能造成邻居节点更大的路径开销，而这种情况下最能体现出COAPS的协作性优势。当车辆数目远多于停车位数量时不是所有车辆节点都可以分配到停车位，同时车辆的高密度增加了路径分配的难度，这种环境最为恶劣的情况对OAPS影响最大，而COAPS按照分层局部最优的原则保护邻居节点的利益，因而受车辆密度的影响不大。

停车位的空闲时间是指车辆节点从开始寻找到预定到停车位的时间（不包括节点行驶到停车位的时间），体现了车辆节点对停车位的竞争情况，也是表征车辆协作性的一个重要指标。停车位空闲时间及其均方差的仿真结果图如图5～6所示。

图5 停车位的平均空闲时间Fig. 5 Average idle time of the parking lots

图6 停车位搜寻时间的均方差Fig. 6 Average variance of parking lot discovery time

图5显示COAPS与OAPS的停车位平均空闲时间相差不大，但图6显示的停车位搜寻时间均方差要远小于OAPS。OAPS中的车辆节点基于抢占式原则总是选择尽可能近的停车位，导致邻居节点很有可能去选择更远的停车位，因而车辆节点间不均衡的停车位选择导致停车位空闲时间的均方差很大。由此可以看出COAPS算法由于兼顾邻居节点的利益，均化了节点的停车位搜寻时间，体现出协作性特征。虽然在停车位平均空闲时间上没有明显优势，但可以换来停车位发现效率的显著提升。

4 结 论

文中通过对停车位发现算法的研究，基于OAPS和模拟退火算法提出了一种协作式停车位发现算法（COAPS），通过车辆节点间的协作来避免不良竞争。通过COAPS与OAPS的对比仿真，验证COAPS算法具有更好的全局效益，可以减少车辆节点的不良竞争和停车位发现时间。

[1] Caliskan M,Barthels A,Scheuermann B,et al.Predicting parking lot occupancy in vehicular ad hoc networks[C].Vehicular Technology Conference, 2007. VTC2007-Spring. IEEE 65th.IEEE, 2007: 277-281.

[2] Mousannif H,Khalil I,Al Moatassime H.Cooperation as a Service in VANETs[J].Journal of Universal Computer Science,2011,17(8):1202-1218.

[3] 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.

[4] 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.

[5] Mathur S, Jin T, Kasturirangan N, et al. Parknet: drive-by sensing of road-side parking statistics[C].Proceedings of the 8th international conference on Mobile systems, applications, and services.ACM,2010:123-136.

[6] 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.

[7] Lee U, Gerla M. A survey of urban vehicular sensing platforms[J].Computer Networks, 2010, 54(4): 527-544.

[8] Stanica R, Chaput E, Beylot A L. Simulation of vehicular ad-hoc networks: Challenges, review of tools and recommendations[J].Computer Networks, 2011, 55(14): 3179-318