基于二进制树算法的路侧微站不停车收费系统

糜江

摘要：本文介绍一种智能节点式路侧微站不停车收费系统的模型以及基于改进的二进制树算法在其中通讯防碰撞的应用。通过matlab对算法进行了数据的图像化处理，结果显示：改进后的算法在搜索效率、数据吞吐率两项重要指标上较之之前使用的方法都有较大提高，尤其是新的防碰撞算法的吞吐率比AHLOHA算法提高了近50%。另外，传输负担的减小还使数据传输的安全性有了更高的保障。

【关键词】路侧微站; 不停车收费; 碰撞算法

当前，我国的高速公路收费方式主要采用半自动收费方式MTC和全自动收费方式ETC，这两种收费方式均在应用过程存在一定的缺陷。

本文所提出的侧微式不停车收费模型从布置方式上解决了车辆入站及出站过程中的“停车”收费现象，可以直接对正在行驶的车辆进行实时定位，并同时覆盖多车道，完成多车辆的数据传输。

为在短时间内尽可能多的识别读写区域内的所有电子标签，该套系统对传统防碰撞算法提出了改进方式，通过模拟得出改进后的算法改进后的算法在搜索次数、吞吐率等重要指标都明显优于传统算法。

1.路侧微站不停车收费平台

与传统的自由流系统相比，路侧微站不停车收费系统最大的特点就在于设备被安装于公路一侧，且无需固定距离，即避免了传统自由流系统存在的多义性路径和费用拆分问题，又能够把现有两种收费方式下的收费出口的收费工作量集中，再分散到行驶过程中來完成，进而提高收费口的工作效率。具体模型及收费方式如图1所示：

智能微型收费结算基站可以覆盖一定半径的圆形区域，形成通信区域，当车辆D从高速入口驶入基站11的通信区域6内后，通过车辆D上安装的车载设备单元与第一高速运营公司第一个智能微型收费结算分界站，即基站11进行互联，车载设备单元向基站11传输车辆D的基本信息，包含车辆唯一标识码、车辆历经的上一个位置和车辆类别等信息。由于车辆D是在邻近智能微型收费结算基站11的高速入口驶入，因此，初始位置信息为0，车辆D从进入高速至基站11的距离为P11，获取车辆行驶距离后可根据车辆类型及货车重量计算该车辆所需缴纳的通行费用，并生成结算所需的费用账单，此时收缴的通行费划给基站11所属的第一高速运营公司3。同时基站11将当前车辆的位置信息上传至车辆D上的车载设备单元，将当前车辆位置信息更新为P11，用于基站12进行费用结算时使用。以此类推，当车辆D行驶至第二高速运营公司第一个智能微型收费结算分界站，即基站21的通信区域8内，通过车辆D上安装的车载设备单元与基站21进行互联通信，车载设备单元2向基站21发送车辆D的基本信息，包含车辆唯一标识码、车辆历经上一个基站的位置和车辆类别等信息。此时车辆D已经驶离第一高速运营公司第n个智能微型收费结算基站1n进入基站21的通信区域内，用当前位置信息P21减去上一个基站的位置信息P1n，此时，基站21使用P21-P1n的里程来进行通行费用计算，并生成结算所需的费用账单，此时收缴的通行费应归基站21所属的第二高速运营公司4，同时将车辆上安装的车载设备单元位置信息更新为P21。

2 改进的二进制树算法

为达到真正的“不停车，多车道”实时监测收费，就必须解决数据间的相互碰撞现象，如何解决通信冲突，是不停车收费系统中的关键。

信号读写的过程如下：首先读写器按照写入频率发出协议信号，使得进入该区域范围内携带电子标签的车辆接受信号并应答。当读写器选择子应答信号载体后，如果当前标签第一位与之前标签第一位不相同，即没有产生通讯冲突，此时便开始发送到最后一位。当接收到的通讯位与周围其他的对应位相同即发生了碰撞，则进行记录并再次传送。如果没有发生通讯碰撞，车载识别装置则可以识别出对应车载设备。一旦碰撞位发生在最后一位，由于协议标签的唯一性，则发射端会判定存在两辆携带车载设备的车辆进入通讯区域。

通过上述工作流程的描述，我们对通讯过程做出如下改进：

（1）一旦发送端监测到有携带设备的车辆驶入，端口即发出既定的通讯协议进行通讯请求指令，等待区域范围内的所有车载设备的应答，直到完成接收所有有效特征码;

（2）发送端收到车载设备的响应码后后开始回复自身的既定协议特征码，在过程中如果没有产生碰撞，那么发送端会对车载设备执行读写指令，晚上读写指令后再发送“挂起”指令，使该车载设备进入到“挂起”的状态，进而离开发射端的通讯范围，如果发射端检测到数据发生协议碰撞，则执行防碰撞指令进行防碰撞操作。

（3）发送端会根据车载设备的协议特征代码来定位具体的位位置，通过对比每一协议位数据是否相同来进行防碰撞处理，当某一协议位不同，则读取下一位数，如果某一协议位数据相同，则表示发生了碰撞，产生数据冲突。此时定位产生冲突的协议位位置，并将低于该位的其他位置上的位进行丢弃操作，在发生碰撞的车载设备中再次发送请求指令，如果仍然发生碰撞，则继续重复上一方案，将所选车载设备的特征码判断并读取出来，在此过程中优先将各车载设备协议码上相同位是 0 的特征码读取出来，当读取的特征码只有最后一个协议位时，选定该 车载设备，完整读取出所有信息，并在识别后进行屏蔽操作。

3.改进对比分析

3.1搜索次数分析

4.结束语

本文从自由流不停车收费系统入手，引入了一种路侧微站不停车收费系统，并着重介绍了其中的数据防碰撞算法，本系统应用一种改进的二进制树算法，通过减少总应答次数、降低查询次数和减少传输数据字节的方式，实现缩短查询时间从而达到提高系统实时性与稳定性的目的。

【参考文献】

[1]罗涛.高速公路机电系统安全维护方式[J].中国设备工程，2019（04）：61-62.

[2]陈振，韩江洪，刘征宇，陆阳.VANET中利用未分配TDMA时隙协助重发数据的方法[J].计算机研究与发展，2017，54（01）：202-211.

[3]张静.并发处理技术在多车道自由流系统中的应用[D].北京交通大学，2011.