一種改進WCA分簇廣播路由在高速公路環境的應用研究

袁學松，　張　靜，　袁　濤

(1.安徽機電職業技術學院信息工程系,安徽 蕪湖　241000；2.合肥工業大學計算機與信息學院，安徽 合肥　230009)

?

一種改進WCA分簇廣播路由在高速公路環境的應用研究

袁學松1,2，張靜1，袁濤1

(1.安徽機電職業技術學院信息工程系,安徽 蕪湖241000；2.合肥工業大學計算機與信息學院，安徽 合肥230009)

摘要：針對高速公路上車輛節點運動速度快，拓撲結構變化頻繁，傳統車載廣播算法廣播覆蓋率低、簇結構不穩定，造成網絡負載高等缺點.本文在充分研究高速公路的車載自組網絡(vehicle ad hoc networks,VANETs)環境的基礎上，提出了一種基于權值的HWCA(Highway Weighted Clustering Algorithm)分簇廣播算法.該算法通過增加HRSU(Highway Road Side Unit)節點，有效控制了成簇規模，并通過車輛的行駛模型實時確定簇首節點和首尾網關節點，提高網絡廣播的可靠性.仿真結果表明，在高速公路環境下，HWCA較現有的車載廣播算法有更好的廣播覆蓋率，更低的簇首變化頻率，更穩定的簇結構，并有效地降低了網絡負載，減小了系統開銷.

關鍵詞:分簇算法；HWCA；VANETS；HRSU；成簇規模；高速公路

在高速公路場景下，安裝在汽車中的Vanet節點運動速度快 ，密度分布不均勻，但運動模型相對于普通公路更有規律，基本符合跟駛交通流形態.在該場景中，由于節點速度快，前車若發生意外，后車跟駛較近很可能發生連環追尾事故.相關研究表明，如果可以使用信息手段將前端突發事件及時廣播給后車，則會大大減少事故發生概率.Vanet經典廣播協議有洪泛法、UMB協議、ABM協議等.這些算法大多在高速公路行車模型中會產生冗余、競爭和沖突等問題，這些問題嚴重時會產生“廣播風暴”.

1VANET分簇廣播算法與問題描述

在各類車載自組網絡的廣播算法中最原始的為“洪泛法”,該算法為簡單的MAC層多跳廣播協議.協議會導致廣播數據冗余、數據碰撞、“廣播風暴”等問題.近年來UMB[1](Urban Multihop Broadcast)協議被廣泛應用到車載自組網中，該協議使用請求和確認的廣播方式避免的“隱藏終端”問題.隨著節點密度增大，該協議在廣播數據包時會產生高延時.AMB(Active Magnetic Bearing)協議常被應用在有眾多路口的城市交通中.WCA[2]分簇廣播協議經常被用在MANET中，網絡利用幾個影響因素對節點進行分簇.因素的權重隨實際需要進行更改，簇內通過簇首節點進行廣播，簇間通過網關節點進行數據交互.文獻[3]提出的一種加權的分簇協議，很好解決了Vanet跟駛狀態下的分簇問題.但其應用到高速公路上仍存在簇首變換頻繁、網絡負載較高等不足.本文通過分析Vanet中經典廣播協議的優缺點，選擇較適合高速場景的基于權重的分簇算法(WCA，Weighted Clustering Algorithm)，并加以改進.

2一種可靠的分簇路由算法

2.1HWCA簇首節點的推舉算法

簇首節點是簇的中心節點，是根據各成員的權值比較推選出來的.當簇首節點形成后會主動地向成員廣播信息，同時可以通過網關節點將成員發起的廣播擴散到全網，并能在生命周期內維護簇內成員的穩定.

文獻[2]中提出的經典WCA算法大多應用在MANET環境中，該環境下節點運動速度較低，網絡拓撲變換不頻繁，需要考慮到MENAT中各節點的能耗問題.所以算法推舉簇首節點考慮了各節點之間的連通度ΔV、移動速度MV、能耗PV和節點與鄰居節點的距離DV這四個因素.當自組網數據通信時，每個節點會根據公式(1)計算自己的WV，簇會推舉一個WV最小且穩定的節點作為簇首節點，式中W1～W4為權重.

WV=MVW1+ΔVW2+DVW3+PVW4

(1)

HWCA簇首節點推舉算法借鑒了經典算法基于權的設計.針對高速公路節點運動規律的相關問題，增加了節點的位置、節點運動規律、節點連通度等權重信息.在高速公路的場景中，HWCA算法借助車內的GPS定位系統獲取車輛信息，在經過HRSU節點覆蓋范圍時計算前若干時間的平均速度、駕駛習慣(是否頻繁變道、是否有急剎車、是否經常行駛在超車道或應急車道)等信息.節點對駕駛習慣信息進行初步評分得到一個值，其越大表明駕駛習慣越不穩定，不適合做簇首節點.在經典算法中簇首節點負責管理簇規模，HWCA算法把控制簇規模大小交給了HRSU節點.綜上所述，在HWCA協議中簇首節點推選權計算公式如下：

Wh=ChW1+DhW2+VhW3+HhW4+KhW5

(2)

2.2HWCA網關節點的設計

圖1　網關節點覆蓋范圍示意圖Fig.1　Schematic diagram of the gateway node coverage

在經典的WCA算法中，簇首節點不僅需要完成簇內的通信工作，同時需要通過不同的發射功率與鄰居簇進行信息交流.考慮到DSRC[4]要求，不同發射功率的簇首節點已不能滿足Vanet的要求.所以在Vanet的分簇算法中大多使用標準的發射功率，這樣就需要一個網關節點來完成簇間通信問題.高速公路場景中，可能出現如圖1的情景.

雖然簇a和簇c還在通信范圍內，a和c則不能通過處于前端的網關節點進行數據通信.導致廣播不能覆蓋后簇，可能會發起不必要的簇維護過程，增大了網絡的負擔.在HWCA網關節點設計中，為了解決上述問題，根據高速公路行車特點，為每個簇設置了前置網關節點和后置網關節點.

2.3HRSU節點的設計

在Vanet中，傳統RSU通常部署在城市交通道路的兩旁，汽車節點可以和RSU間進行高帶寬數據傳輸.當沒有合適的RSU和汽車節點進行通信時，汽車節點可以將要傳輸的信息預存在車內設備的本地緩存中，有合適機會繼續進行數據傳輸[5].在HWCA協議中，設計了HRSU節點.它不僅能夠完成普通RSU的功能，而且讓它具有了簇規?？刂?、簇首節點、網關節點推選等特定功能.

當前RSU使用的802.11p協議支持的最大傳輸距離是1Km.在高速場景下，汽車節點平均速度約為100Km/h(27.7m/s)，經過HRSU的覆蓋范圍約為72s.在該段時間內HRSU工作過程如下：當第一輛汽車進入信號覆蓋范圍的時候，RSU開啟計數器，每經過一輛汽車計數器加一.當簇規模達到設定的上限時會發出通知消息，讓再進入覆蓋范圍的車輛進入下一簇.同時，HRSU強制簇內注冊的汽車節點離開原簇準備建立新簇，在建立新簇之前所有的廣播通信均由HRSU完成.HRSU收集覆蓋范圍內汽車節點自身速度、位置、駕駛習慣等信息并將其記錄在內存中.當在覆蓋范圍內的車輛都將信息傳輸給HRSU時，通過HWCA的推舉算法推舉出簇首節點、前向網關節點、后向網關節點和成員節點并通知各節點所對應的身份信息.在高速公路環境中，安排10-20Km建立一個站點.在HRSU覆蓋的兩公里范圍內各成員接收HRSU廣播信息.當各節點離開覆蓋范圍則根據相關算法簇首負責對信息進行廣播和對簇進行維護.

2.4各類數據包設計

為了完成簇網絡中各種信息、控制和廣播包的傳遞，協議定義了8種數據包，具體如下：

(1)廣播包和緊急廣播包(Broadcast Data Packet, BDP / Emergency Broadcast Data Packet, EBDP )

廣播包是有簇首節點傳送給成員節點，HRSU節點傳給各成員節點的內容數據包.包頭區中存放控制信息，數據區存放著內容信息，主要定義了包ID號、發送包的源ID、包生成時間、包中簇首節點ID、優先級等字段信息.在緊急廣播包中優先級設置為最高.

(2)節點信息狀態包(Node Status Packet，NSP)

用在向RSU提供節點的狀態信息，同時在協議后期簇維護過程中用以節點間信息交換來推薦簇首.該包信息主要由節點的當前速度、節點的位置信息、節點的駕駛習慣評分以及節點承擔簇首的次數等組成.

(3)HRSU信息傳遞包(HRSU Information Transfer Packet，HITP)

當RSU經過評估確定簇首、網關、成員節點后發給每個節點的身份認證包.該包定義了RSU ID號、目的節點ID號、目的節點身份信息和經過加權后的權值等信息.

(4)HRSU信息中斷包(HRSU Break Packet，HBP)

該數據包是控制包.將在HRSU覆蓋區域的汽車節點進行簇分離，讓其強制進入組網模式.

(5)簇首聲明維持包(Head Announce and Maintenance Packet，HAMP)

節點在離開RSU覆蓋范圍后，為了維持簇的穩定性要進行簇維護和簇重建的過程.在這個過程中簇首定期發送相關自身信息給各成員節點來聲明自己身份.如果根據簇首推選方案有更小的權值的節點，則提出異議，該簇進行相關維護和重建工作.

(6)網關維持包(Gateway Maintenance Packet，GMP)

網關節點需要能夠與本簇中的簇首進行通信，同時需要和鄰居簇的簇首進行數據交換，所以不論是HRSU還是簇建立過程中創建的網關節點都需要告知周圍的簇首自己的網關身份.在HWCA算法中，由于設置了前向網關和后向網關，所以每個網關節點最少能和兩個簇首建立通信.

(7)網關退出包(Gateway Quit Packet，GQP)

在簇維護過程中，不論是前向還是后向網關發現自己不能和兩個或者以上的簇首進行聯系時，主動發起GQP通知簇首.簇首可以讓各成員節點競爭網關節點.

(8)網關競爭通告包(Gateway Compete Packet，GCP)

只要網關發出GQP，簇首節點就會向群內廣播GCP.符合條件的會獲得簇首授予的網關身份，同時向周圍簇首發送GMP告知其網關身份.

2.5HWCA協議原理

2.5.1HWCA簇建立過程和簇維護過程簇建立是由高速路邊的HRSU裝置發起.其信號覆蓋范圍為以其為中心的1Km的圓形區域，成簇時間為第一輛車駛入信號覆蓋范圍到第一輛收到HBP包車離開覆蓋范圍的時間差，簇規模為S，成簇過程如圖2.

圖2　HRSU成簇流程圖　　　　　　　　　　　　　　　　　　圖3　節點自發成簇流程圖Fig.2　HRSU clustering flowchart　　　　　　　　　　　　　　Fig.3　Clustering chart with nodes

(1)第一輛汽車經過HRSU覆蓋范圍時，發送HBP包，汽車節點收到HBP包后強制脫離原簇，進入組網模式.在該模式下所有的廣播信息不在由簇頭發布，而是由HRSU節點接管，同時HRSU自身計數器加一.

(2)若超時，信號覆蓋的節點是否達到成簇的最低要求，若達不到則轉到(6)，否則轉至(3).

(3)查看HRSU計數器是否超過S，若不超過轉至(1)，若超過轉至(4).

(4)各個汽車節點向HRSU發送NSP包，經過計算得到該簇的簇首、前向網關、后向網關、成員節點，同時向每個簇內節點發送HITP包.

(5)發送成功組組網結束，否則轉至(6).

(6)成簇失敗的節點將在后續行駛過程中向周圍廣播NSP包，通過簇維護的方式加入前簇或后簇.

在行駛過程中，始終向周圍節點周期性的廣播HAMP包，向周邊節點告知自己的簇首身份.當周邊節點認為自己有更小的權值或由于意外情況，簇首節點丟失，會進入簇重建過程.簇重建過程如圖3.

圖4　高速公路中網關節點的維護模型Fig.4　Gateway node maintenance model in highway

ⅰ當成員節點找不到自己的簇首或者簇首節點的權值受到質疑時，任意節點發起簇首推選.任意節點向周邊鄰居節點發送NSP包，用來交換各自節點的綜合權值信息.

ⅱ節點通過計算認為自己的綜合權值較小則向周圍廣播HAMP包，若無異議則成為新的簇首節點周期性的發送HAMP包，若存在異議則進入過程ⅰ.

ⅲ當各成員收到HAMP包后將各自的身份調整至成員節點或網關節點.

當成簇失敗的節點經過一段時間的行駛，接受到新簇首節點的HAMP包，會向其發出自己的NSP包，若權值較大則加入簇成員，若權值較小則質疑簇首節點并發起簇重建過程.

圖5　網關節點維護流程圖Fig.5　Gateway node maintenance flow chart

2.5.2網關節點的維護過程在HWCA協議中，在HRSU成簇過程中通常會選擇最先離開信號覆蓋范圍的節點作為前向網關節點(簇最前端)，最后進入信號覆蓋范圍的為后向網關節點(簇最后端).在簇運動過程中，網關節點位置會在簇內位置發生變化.圖4中可以看出簇A后向網關節點GWA此時已不在簇C簇首節點HC的信號覆蓋范圍內.這就意味著簇C將不能和簇A通過GWA交互廣播信息.此時，簇A就需要重新推舉后向網關節點，具體過程見圖5.

當A簇網關節點GWA不能收到至少2個簇首發布的周期信號HAMP包，則進入網關重選過程.GWA向HA發送GQP包，HA收到后將向簇成員廣播GCP包.當收到2個或更多HAMP的節點向簇首申請網關節點后，簇首通過周期數據包HAMP授權該節點為網關節點.授權后的節點向鄰居簇首周期發送GMP包.

簇首節點、網關節點和成員節點均可以發起廣播包，EBDP包優先發送.簇首節點將自己的ID存入廣播包的源ID中，通過網關節點對其他簇進行轉發.

3仿真實驗分析

3.1汽車節點運動模型與高速公路模型的構建

由于汽車在高速公路上同向高速行駛，無需考慮交通信號燈和建筑物的限制.高速運動汽車節點模型不再適合使用普通的Vanet運動模型.Bai[6-7]等人提出的基于高速公路和曼哈頓流動模型較適合本文場景.在高速公路模型的選擇上，本文使用MOVE[8](Mobility Model Generator for Vehicular Networks)軟件將地圖數據庫直接導入到軟件中實現了真實場景的仿真，通過該軟件搭建了某段長約10Km的高速公路.

本次實驗以真實的高速公路為依據，同時使用節點運動模擬器SUMO[9]仿真運動高速運動的汽車節點.實驗的目標廣播區域是長約10Km寬為36m的5車道場景.為反映真實數據，節點的運動速率為80-120Km/h，且只考慮車輛單向從標記1運動至標記2，當場景中的車輛節點到100輛且保持該車流密度，對各指標進行提取.實驗分別對車流密度區間為100-700每間隔50輛車做一次數據收集并分析.

在實驗中，運動模型考慮了車輛變道等情況，但未考慮車輛車身長度信息.從簇結構穩定性考慮，設置協議中的權值分別為W1=0.26,W2=0.2，W3=0.21,W4=0.29，W5=0.04.仿真場景的各類參數入表1所示：

在仿真過程中，對整個網絡性能主要關注廣播覆蓋率和端到端延時兩個指標.而從簇穩定性的角度需關注分簇數目，簇首改變次數，簇生存時間等性能指標.

表1　高速公路場景參數表

3.2仿真結果與分析

本次仿真實驗在真實模型下，把HWCA算法、WCA算法和針對跟駛模型設計的VWCP算法從網絡性能和簇穩定性兩個方面進行對比實驗[10].

圖6為仿真場景中分簇數目，可以看出隨著節點的增加HWCA算法和VWCP算法的分簇數保持穩定，表示簇很少進行重建和分離.在整個600秒仿真時間內，由于HRSU使用計數器有效地限制了簇規模.所以HWCA中分簇個數雖比VWCP多，但成簇后簇數較兩種算法更加穩定.圖7-8為簇首改變次數和簇生存時間，簇首改變次數越小、簇生存時間越長表示簇首更替越少，簇生存時間越長，簇更穩定，網絡負擔越小.從圖中可以看出，當車輛節點增多時，HWCA算法由于權重因素設計合理，簇首幾乎沒有改變，較其他兩種算法有很好的穩定性.

圖6　簇規模　　　　　　　　　　　　　　　　　　　　　　　　　　　圖7　簇平均生存時間Fig.6　Cluster scale　　　　　　　　　　　　　　　　　　　　　Fig.7　Average survival time of the cluster

圖8　簇首改變次數　　　　　　　　　　　　　　　　　　　　　　　圖9　廣播覆蓋率Fig.8　Change times of cluster head　　　　　　　　　　　　　　　　　Fig.9　Coverage rate of broadcast

圖10　平均端到端延時Fig.10　Average end-to-end delay of data packets

圖9展示的是三個協議的廣播覆蓋率，廣播覆蓋率越高說明節點發送廣播能可靠的傳播給全網.從圖中可以看出WCA和VWCP兩種算法在車輛節點較少時廣播率可達98%左右，而由于HWCA算法在節點較少時使用了HRSU對網絡進行廣播，所以廣播覆蓋率接近100%.圖10顯示了三種算法的端到端延時指標，該指標能反映出廣播包是否能及時到達各節點.當車輛較少時，在HWCA算法中節點由于大多是由HRSU進行廣播傳輸延時較低.隨著車輛節點的增多，大多數廣播發生在HRSU覆蓋范圍之外，和其他兩種協議一樣是由簇首節點負責廣播，由于協議的簇較穩定，網絡負載較小，所以較其他兩種協議端到端的延時也更小.

4結束語

本文深入研究WCA和VWCP兩種廣播協議的基礎上，提出了一種應用于高速公路的HWCA協議.通過仿真結果表明，新協議和經典協議在高速公路環境下均有很好的廣播覆蓋率，但在車輛節點較多，路況較為復雜的情況下，HWCA協議比經典協議具有有更好的網絡性能，其形的成簇具有更好的穩定性，相關協議算法在真實高速公路情景下具有更好的實用價值.

參考文獻:

[1]JAGRUTI sahoo, ERIC Hsiao-Kuang Wu, Pratap Kumar Sahu. Binary-Partion-Assisted MAC-Laryer Broadcast for Emergency Message Dissemination in VANETs[J]. IEEE Transactions on Intelligent Transportation System,2011,12(3):757-770.

[2]CHATTERJEE M, DAS S K, TURGUT D. WCA: a weighted clustering algorithm for mobile ad hoc networks[J]. Cluster Computing. 2002,5:193-204.

[3]周連科.基于交通流密度的VANET廣播技術研究[D].哈爾濱:哈爾濱工業大學,2011:50-70.

[4]CSEH C. Architecture of the dedicated short-range communications (DSRC) protocol[C]. 48th IEEE Vehicular Technology Conference. Ottawa,Canada,1998:2095-2099.

[5]LIN Xiaodong, LU Rongxing, LIANG Xiaohui, et al.Stap:a social-tier-assisted packet forwarding prot-ocol for achieving receiver-location privacy preservation in vanets[C]∥Proceedings of IEEE INFOCOM 2011, IEEE INFOCOM．Shanghai: IEEE Press,2011:2147-2155．

[6]F Bai, SADAGOPAN N, HELMY A. The important framework for analyzing the impact of mobility on performance of routing for ad hoc networks[J]. Ad Hoc Networks, 2003,1(4):383-403.

[7]F Bai, SADAGOPAN N, HELMY A. Important:a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks[C].INFOCOM 2003,the 22th Annual Joint Conference of the IEEE Computer Communications,IEEE Societies,2003,2:825-835.

[8]KARNADI F K, MO Z H, LAN K.Rapid generation of realistic mo-bility models for VANET[C]. Proc of IEEE Wireless Communications and Networking Conference 2007. Hong Kong, 2007:2506-2511.

[9]BEHRISCH M, BIEKER L, ERDMANN J, et al. SUMO-Simulation of Urban Mobility: An Overview[C]// Simul. 2011:63-68.

[10]ZHANG H, XIA J， SHEN Y. A graph clustering algorithm based on weighted shared neighbors and links[C]. Software Engineering and Service Science (ICSESS), 2015 6th IEEE International Conference on, Beijing, 2015, 828-831.

DOI：10.14182/J.cnki.1001-2443.2016.04.004

收稿日期：2016-4-14

基金項目：安徽省教育廳2016年度高校領軍人才引進與培育計劃項目(gxfxZD2016324)；安徽省教育廳省級教學團隊(2014jxtd99)資助.

作者簡介：袁學松，男，1982，碩士，研究生，副教授，研究方向為主要研究方向為網絡仿真技術、無線傳感網、數據挖掘.

中圖分類號:TPT393

文獻標志碼:A

文章編號：1001-2443(2016)04-0324-07

Application of an Improved WCA Clustering Broadcast Routing in Highway Scenarios

YUAN Xue-song1,2,ZHANG Jing1，YUAN Tao1

(1.Department of Information Engineering, Anhui Technical College of Mechanical and Electrical Engineering, Wuhu 241000， China；2.School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Abstract:Due to the fast vehicle node speed and rapid topological structure change of the highway vehicle network, the traditional vehicle broadcasting algorithms have many drawbacks, e.g. low coverage, unstable cluster structure and high network load. In this paper we study the Vehicle Ad Hoc Networks (VANETs) and propose a novel Highway Weighted Clustering Algorithm (HWCA). First, the amount of Highway Road Side Unit (HRSU) is increased and the cluster scale is controlled. Second, the first node and the gateway nodes of the network cluster are located based on the real-time vehicle driving model. The broadcasting reliability is improved. Finally, the simulation is carried out and the results show that HWCA has better coverage, lower cluster change rate, and more stable cluster structure in highway environment. The proposed algorithm may decrease the network load and cost in highway vehicle broadcasting.

Key words:clustering algorithm; HWCA；VANETS；HRSU；scale of clustering; highway

引用格式：袁學松，張靜，袁濤.一種改進WCA分簇廣播路由在高速公路環境的應用研究[J].安徽師范大學學報：自然科學版，2016，39(4)：324-330.