基于二進制樹算法的路側微站不停車收費系統

糜江

摘要：本文介紹一種智能節點式路側微站不停車收費系統的模型以及基于改進的二進制樹算法在其中通訊防碰撞的應用。通過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.