高速公路場景中車用自組織網絡的節點度

熊 煒 李清泉

①(武漢大學電子信息學院 武漢 430079)②(武漢大學交通研究中心 武漢 430079)

③(武漢大學測繪遙感信息工程國家重點實驗室 武漢 430079)

1 引言

隨著交通禍害的日益嚴重，交通治理觀念的轉變，政府交通政策的改變以及運用智能交通(ITS)改善道路運輸狀況的成效等諸多方面的因素，使得研究與發展ITS已經成為當前科技競爭的前沿熱點領域之一。車用自組織網絡(VANET)作為ITS的一個重要組成部分，近年來也一直備受交通發達國家的廣泛關注，它是移動自組織網絡(MANET)與無線傳感器網絡(WSN)在ITS中的具體應用。借助車輛與車輛(V2V)、車輛與路旁基礎設施(V2I)以及車輛與行人(V2P)之間的直接或多跳通信，從而在現有道路網上動態、快速構建一個自組織、分布式控制的專用短程通信(DSRC)網絡成為現實。通過運用新興的車-X通信技術，可以實現諸如道路安全告警、交通擁塞監測以及基于位置的流媒體服務等方面的應用[1]。由于VANET獨具的特點(例如車輛運動的高速性、頻繁的網絡分裂、網絡易受駕駛員行為等因素的影響[2])，針對MANET/WSN所做的研究成果并不能夠直接應用于新興的VANET系統。

目前，VANET研究人員在車用媒介訪問控制(MAC)、數據分發、通信安全以及運動建模等方面取得了較好的研究進展[3,4]，但對于車輛網絡能夠提供可靠服務的先決條件，即VANET拓撲連通性方面的研究還相對較少。文獻[5]探討了影響車輛間通信網絡連通性的諸多關鍵因素，例如車流密度、相對速度、車道數等。文獻[6]利用元胞自動機模擬信息的傳播過程，給出了相距為d的兩車之間在不同交通環境以及不同通信距離下通過IVC建立連接的概率。文獻[7]分析得出了無線通信范圍r內至少存在一個VANET節點的概率。文獻[8]通過研究緊急告警信息在雙向多車道高速公路場景中的傳播機制，得出了在被影響區域L內可將緊急告警消息轉發給至少一個其它有效車輛的概率。文獻[9]運用復雜網絡的傳播機理，研究了VANET市場普及率(即具有車載無線通信設備的車輛占道路中所有行駛車輛的比率)對交通信息的傳播效率及傳播速度的影響，并從消息縱向傳播的動力學分析中得出轉發概率有賴于節點最大通信距離的結論。文獻[10]提出了一個分析模型用以計算沿交通流方向覆蓋每一輛車的概率，該遞歸模型為瞬時傳輸距離的建模提供了一種數值計算的方法；隨后文獻[11]在此基礎上，分析了VANET節點密度、節點通信距離以及信息傳播距離之間的關系，并給出了計算信息傳播距離的數學期望、方差及其概率分布的閉合解析式。文獻[12]基于公認的交通流分布，通過引入攝動機制模擬駕駛員行為，研究了單向有限長度高速公路場景中VANET連通性問題，并給出了網絡高概率連通所需的節點鄰居數下限。文獻[13]則推導得出了雙向4車道場景中無孤立節點的存在概率。

縱觀國內外的研究現狀，研究重點主要集中在非孤立節點方面，即節點通信范圍內至少存在一個鄰居車輛的概率，但對車輛節點之間存在冗余鏈路方面的研究還尚未引起足夠重視。為此，本文在已有研究的基礎上，重點考查車輛網絡的k-鄰居問題，并推導得出一種用于高速公路場景中車用自組織網絡節點度的概率計算方法。文獻[14]與本文的研究較為接近，然而前者在分析得出MANET的最小節點度時，并未考慮車輛網絡的約束性。本文屬于網絡k-連通性范疇，在文獻[13]提出的算法基礎上，對VANET的冗余節點度(即k=1,2,3,…)做了進一步深入研究，因此從某種意義上而言，文獻[13]是本文在k=1時的特例。本文在以下幾個方面取得了較好的研究進展：(1)高速公路場景中車輛運動建模；(2)高速公路場景中無線信道建模；(3)VANET隨節點通信距離的變化表現出的特殊性；(4)VANET中節點度至少為k的概率計算公式。

2 VANET系統建模

2.1 車輛運動模型

對自組織網絡的研究表明，協議性能的優劣在很大程度上取決于所選擇的節點運動模型，并且MANET研究中經常采用的隨機路點(RWP)和隨機方向(RD)運動模型不適合模擬車輛的運動，另外，通過大規模現場實驗以期獲得一定數量、真實的車輛軌跡數據代價太大，因此，微觀交通仿真系統可用于生成研究所需的車輛運動。本文使用的車輛運動軌跡數據來源于HWGui項目[15]，原始車輛運動數據由DaimlerChrysler內部的駕駛員行為模擬器產生，并同高速公路上采集到的真實車輛運動數據進行了比較。它對交通流的描述是以單個車輛為基本單元，車輛在道路上的跟車、超車以及車道變換等微觀行為都能夠得到真實的反映。

運動數據的格式為每個車輛節點(NodeID)在采樣時刻(Timestep)具有的瞬時位置(PositionX)、速度(Speed)、加速度(Acceleration)及車道(Lane)信息，轉換成NS-2兼容的TCL運動格式后，相當于車輛在如圖1所示的雙向4車道高速公路模型中連續運動。不同密度的車流可沿著被中間帶分隔且與車道平行的兩個方向(如圖中箭頭所示)高速運動，每個方向再具體劃分為行車道(行進方向右手側)和超車道(行進方向左手側)。本文規定：行/超車道寬度LaneWidth=3.75 m，中央分隔帶寬度MedianWidth=2.00 m。

由于每個車輛節點在高速公路上的坐標位置均由2元組(PositionX, Lane)表示，因此在模擬實驗中，車輛的車道變換過程總是在相鄰兩次采樣間隔(0.5 s)內完成。為了簡化數據處理，我們用車輛所在車道的中線表示其在Y方向上的投影(PositionY)，若采用圖1中所示的坐標系統，則映射關系式為

圖1 高速公路場景模型

2.2 無線傳播模型

信號通過無線信道時，會遭受各種衰落的影響，可以分為[16]：大尺度衰落和小尺度衰落。其中大尺度衰落是由于傳播距離的路徑損耗或傳播環境(例如地形起伏、高大建筑等障礙物)的遮擋所致，它通常與射頻頻率無關。小尺度衰落則是由于無線電波在空間傳播時存在反射、繞射和衍射等機制，從而造成信號經由多條路徑到達接收端疊加形成，與所選信號頻率有關。

復雜的統計模型(例如瑞利、萊斯、Nakagami等分布)可以用來描述無線傳播的多徑衰落，但對無線鏈路性能及無線通信方式的研究表明[17,18]：基于幾何光學的雙線模型(同時考慮視距直接傳播與地面反射路徑)在預測高速公路場景中的專用短距離通信時也具有良好的效果。本文采用式(2)所示的廣義對數距離路徑損耗模型為無線信道建模：

其中Prx/Ptx分別為收/發信號功率，d為收發之間的距離，d0為近地參考距離(由測試決定)，β為路徑損耗指數，它表明路徑損耗隨距離增長的速率，在視距以及非視距車輛通信場景中分別為1.4～3.5和2.8～5.9[19]。因此，在給定接收靈敏度Prx,th時，每個節點的無線通信距離可以由其等效發送功率來計算。當Prx(d)＜Prx,th時，我們就認為兩節點之間不存在無線通信鏈路。本文假定場景中所有車輛節點都相同，即具有相同的射頻功率和接收靈敏度，并采用全方向天線。

3 k-近鄰節點概率

基于前述的VANET系統模型，本文將高速公路場景中每個采樣時刻t所對應的車輛網絡表示為一個簡單無向圖Gp(r)(V, t)，其中，V表示實驗場景中的所有活動車輛，其網絡規模為N=|V|，p(r)則表示當節點通信距離為r時，場景中任意兩個節點之間邊(即無線通信鏈路)的存在概率。如果記符號||?||為實d-維向量空間?d上的范數，對于給定分布的有限點集V??d，當且僅當||vj-vi||≤r時，兩節點{vi,vj}互為鄰居。不防設離散型隨機變量D為圖中任意節點v∈V的可能頂點度。以下將從交通工程學的角度出發，推導網絡或圖中節點度至少為k的概率Pr{D≥k}。

在交通流理論中，車頭間距(hs)與車頭時距(ht)是兩個非常重要的微觀交通特征參數，它們是表征同一概念的兩種不同量度單位，分別用來描述在同向行駛的車流中，前后相鄰兩車之間的空間距離以及駛過道路某一斷面的時間間隔，其取值與駕駛員行為特征、車輛性能、道路具體情況密切相關，同時也受到交通流量、交通控制方式以及道路幾何特征等因素的影響。實際工程應用中，由于車頭間距的實時測量非常困難，一般僅使用車頭時距這個指標。在自由流(例如高速公路上的交通流)條件下，其車頭時距服從指數分布[7,9,12]，并且可以證明，車輛到達數在任意計時周期內一定是泊松分布。如果車流速度vs同時滿足均勻分布，則車頭間距與車頭時距具有完全相同的指數分布形式[7,12](hs=vsht)。由于車流密度被定義為κ=N/(Lm)，其中，N為車輛數，m為車道數，L為觀測路段的長度。于是，在車輛節點通信范圍A內至少存在k個鄰居的概率為

其中λ=1/(vs?ht?m?LaneWidth)是一個與高速公路模型、車頭時距、車輛運動速度有關的物理量。由于車輛網絡固有的技術特點，對組網真正產生貢獻的有效作用面積為帶狀行車區域和無線覆蓋范圍的交集。關于有效組網面積的詳細討論，讀者可以參見文獻[13]，考慮到篇幅限制，本文僅對節點通信距離足夠大(即r＞3.5×LaneWidth+MedianWidth)的情況進行分析。

若記A1，A2為帶狀行車區域分別與行車道(i=1)、超車道(i=2)上車輛節點的無線覆蓋范圍所形成的公共面積(如圖1所示)，于是有

式(4)中的兩個二重積分非常相似，差異主要在于積分變量y的上/下限不同，因此只需要計算以下二重積分即可。

令y?yi=rsin(t)，則有=rcos(t)，dy=rcos(t)dt ，t=arcsin(y?yi)/r ，將它們代入式(5)得

(2)在嵌入的雙對數坐標系中，當節點通信距離較大時，其與車道平均系數之間具有冪律特征(對應為一條直線)，即c～r?γ，本文僅對100～1000 m處的車道平均系數做最小二乘擬合得γ=0.9988，此時對應的殘差平方和僅為1.0575×10?6。

圖2 行車道與超車道系數

4 實驗與分析

本文使用的車輛運動軌跡數據來源于HWGui項目，采用地面反射雙線模型為無線信道建模(通信頻率設為5.9 GHz DSRC專用頻段，無線模型的其它參數采用NS-2中的默認值)。為了驗證推導得出的理論分析結果與實際的車輛網絡模型之間的匹配效果，作者選取5組不同車流密度下的車輛運動軌跡數據進行實驗，表1列出了實驗場景中車輛網絡的部分運動數字特征。

圖3為場景1中節點度至少為1的實驗概率曲線分別與相同參數的3條理論概率曲線之間的比較，其中，虛線是將高速公路視為1維(線性)場景時的理論概率，點劃線是將高速公路視為2維(帶狀)場景且有效組網區域視為圓時的理論概率，實線則是將高速公路視為2維(帶狀)場景且有效組網區域為本文提出的弧邊矩形時的理論概率。從圖中可以看出，可以將高速公路場景中的車用自組織網絡視為1維線性或2維帶狀，但是在2維帶狀條件下，節點間的有效組網區域必須限制為弧邊矩形，即理論分析中須除去節點不可達的部分。此外，相對于虛線而言，實線更逼近于實際實驗曲線，并且當節點通信距離較小時，實線以點劃線作為其漸近線；當節點通信距離較大時，實線又以虛線作為其漸近線。換言之，在節點通信距離較小時，高速公路場景中的車用自組織網絡具有較為明顯的2維特性；但在節點通信距離較大時，其又轉而具有明顯的1維特性，這也進一步說明了VANET的特殊性。對于其它實驗場景在不同節點度時也都有類似的結論。

表1 實驗場景中車輛網絡的運動數字特征

圖3 理論概率與實驗概率對比

圖4，圖5和圖6分別為VANET場景中節點近鄰數至少為1，2和3的概率。其中，圖4(a)，5(a)，6(a)的3維網格圖是在給定場景(其長度L=12000 m)中的理論概率及其對應的等高線投影，網格圖中任意兩曲線的交點即為在給定(N, r)條件下，節點度至少為k的概率；圖4(b)，5(b)，6(b)分別為5組不同車流密度下的節點度實驗概率與本文推導得出的k-近鄰節點概率(相同參數下的理論概率)之間的比較，可以看出，在所有這5組實驗場景中，節點度的理論概率與實驗概率吻合得較好，并且當場景中節點數N以及節點通信距離r一定時，隨著節點鄰居數k的增加，其存在概率越小。例如若N=50，r=250 m，網絡中所需節點度至少等于1，2和3的理論概率分別為0.8754，0.6158和0.3456。此外，若給定網絡所需的最小節點度，則：(1)在相同通信距離的條件下，隨著車流密度的增加，Pr{D≥k}越大；(2)在相同Pr{D≥k}的條件下，場景中車流密度越大，所需的節點通信距離越小。這與有關文獻所得的結論完全一致。

5 結束語

本文基于地面反射雙線模型將車輛網絡建模為(路徑損耗)幾何隨機圖，并在已有研究的基礎上向前邁進了一步，重點研究了高速公路場景中車用自組織網絡的k-鄰居問題，推導得出了計算VANET節點度至少為k的概率分析算法，并借助真實的車輛運動軌跡數據做了大量模擬實驗。本文的主要貢獻在于：(1)將VANET建模為幾何隨機圖，并提出了弧邊矩形有效組網面積的概念，即高速公路帶狀行車區域與無線信號覆蓋范圍的交集，并將其由2維場景中的πr2緊縮為cr2，其中c＜π；(2)分析說明了車輛間通信網絡所具有的特殊性，即隨著節點通信距離的增加，其網絡屬性將逐漸由2維模式過渡到1維模式，并最終以1維模型對應的概率曲線作為其漸近線(相對于1維模型而言，本文推導得出的理論概率更逼近實驗概率)；(3)推導得出了無線通信范圍內至少存在k≥1個VANET鄰居的概率，根據式(8)可以解算出，場景中所需的網絡規模N、節點通信距離r以及網絡中節點度至少為k的概率Pr{D≥k}三者之間的數值關系。

圖4 場景中節點度至少為1的概率

圖5 場景中節點度至少為2的概率

圖6 場景中節點度至少為3的概率

對于車用自組織網絡連通性方面還存在一些問題有待于作者做進一步的分析與研究，例如：VANET在高速公路場景中節點度與網絡連通性之間的關系以及VANET在市區內的連通性分析等。

[1] Hartenstein H and Laberteaux K P. A tutorial survey on vehicular Ad hoc networks. IEEE Communications Magazine,2008, 46(6): 164-171.

[2] Toor Y, Muhlethaler P, and Laouiti A, et al.. Vehicle Ad hoc networks: applications and related technical issues. IEEE Communications Surveys & Tutorials, 2008, 10(3): 74-88.

[3] Moustafa H and Zhang Y. Vehicular networks: techniques,standards, and applications. NW: Auerbach Publishers, CRC Press, Taylor & Francis Group, 2009.

[4] Olariu S and Weigle M C. Vehicular networks: from theory to practice. NW: Chapman & Hall, CRC Press, Taylor &Francis Group, 2009.

[5] Artimy M M, Robertson W, and Phillips W J. Connectivity in inter-vehicle ad hoc networks. Proceedings of Canadian Conference on Electrical and Computer Engineering, Niagara Falls, Canada, 2004, Vol. 1: 293-298.

[6] Hartenstein H, Bochow B, and Ebner A, et al.. Position-aware ad hoc wireless networks for inter-vehicle communications:the fleetnet project. Proceedings of the 2nd ACM International Symposium on Mobile Ad hoc Networking &Computing, Long Beach, CA, USA, 2001: 259-262.

[7] Tsugawa S and Kato S. Evaluation of incident information transmission on highways over inter-vehicle communications.Proceedings of the IEEE Intelligent Vehicles Symposium(IV-2003), Columbus, Ohio, USA, 2003: 12-16.

[8] Tondl P and Pérez Guirao M D. Forwarding of emergency notifications in one-dimensional networks. Inter-vehiclecommunications based on Ad hoc Networking Principles - the FleetNet Project. Karlsruhe, Germany, Universit?tsverlag Karlsruhe, 2005: 83-116.

[9] Sch?nhof M, Kesting A, and Treiber M, et al.. Coupled vehicle and information flows: message transport on a dynamic vehicle network. Physica A: Statistical Mechanics and its Applications, 2006, 363(1): 73-81.

[10] Jin W-L and Recker W W. Instantaneous information propagation in a traffic stream through inter-vehicle communication. Transportation Research Part B:Methodological, 2006, 40(3): 230-250.

[11] Wang X. Modeling the process of information relay through inter-vehicle communication. Transportation Research Part B:Methodological, 2007, 41(6): 684-700.

[12] Ukkusuri S and Du L. Geometric connectivity of vehicular Ad hoc networks: analytical characterization. Transportations on Research Part C: Emerging Technologies, 2008, 16(5):615-634.

[13] 熊煒, 李清泉. 高速公路場景中車用自組織網絡1-連通的必要條件. 軟件學報, 2009. Available: http://www.jos.org.cn/1000-9825/3681.htm.Xiong W and Li Q Q. Prerequisite to 1-connected vehicular Ad hoc networks in highway scenarios. Journal of Software,2009. Available: http://www.jos.org.cn/ 1000-9825/3681.htm.

[14] Bettstetter C. On the minimum node degree and connectivity of a wireless multihop network. Proceedings of the 3rd ACM International Symposium on Mobile Ad hoc Networking &Computing, Lausanne, Switzerland, 2002: 80-91.

[15] Fü?ler H, Torrent-Moreno M, and Transier M, et al..Studying vehicle movements on highways and their impact on ad-hoc connectivity. ACM SIGMOBILE Mobile Computing and Communications Review, 2006, 10(4): 26-27.

[16] Rappaport T S. Wireless Communications: Principles and Practice. 2nd ed. New Jersey: Prentice Hall PTR, 2002, Chap.4-5.

[17] Zang Y, Stibor L, and Orfanos G, et al.. An error model for inter-vehicle communications in highway scenarios at 5.9GHz.Proceedings of the 2nd ACM International Workshop on Performance Evaluation of Wireless Ad hoc, Sensor, and Ubiquitous Networks, Montreal, Quebec, Canada, 2005:49-56.

[18] Gallagher B, Akatsuka H, and Suzuki H. Wireless communications for vehicle safety: radio link performance and wireless connectivity methods. IEEE Vehicular Technology Magazine, 2006, 1(4): 4-24.

[19] Yin J, ElBatt T, and Yeung G, et al.. Performance evaluation of safety applications over DSRC vehicular ad hoc networks.Proceedings of the 1st ACM International Workshop on Vehicular Ad hoc Networks, Philadelphia, PA, USA, 2004:1-9.