車載自組網中基于分簇的多優先級異步MAC協議

任秀麗，陳梓航

(遼寧大學 信息學院，沈陽 110036) E-mail：892529546@qq.com

1 引 言

車載自組網(Vehicular Ad-hoc NETwork，VANET)是傳統移動自組織網在交通領域的重要應用，其通過車載單元(On-Board Unit，OBU)和路側單元(Road Side Unit，RSU)實現車與車、車與道路間的雙向通信.美國IEEE 1609工作組在IEEE 802.11p標準[1]基礎上，根據VANET的特殊需求為其制定了IEEE 1609.4標準[2].該標準將75MHz的專用帶寬劃分成1條控制信道(Control CHannel，CCH)和6條服務信道(Service CHannel，SCH)，并規定了信道接入的同步周期為100ms.由于固定的同步周期劃分不適合高移動性的車載網絡環境，因此，研究一種適合VANET環境的高效、可靠的MAC協議具有重要意義.

目前，車載自組織網絡MAC協議按節點切換信道的工作方式分為時間同步切換和時間異步切換.在時間同步MAC協議中，文獻[3-5]提出了一種可變CCH周期的方法，有效地提高了信道吞吐量，但在數據周期內會造成CCH資源的浪費.文獻[6]采用自排序過程形成隊列，按照隊列順序訪問信道，減少時延但時間同步所導致的信道空閑問題仍然存在.文獻[7]提出一種基于分簇的移動感知分布式多信道MAC協議(Distribute Multichannel and Mobility-Aware Cluster-based，DMMAC)，雖基于簇的分配機制在信道空間利用率上占有很大優勢[8]，但為保證簇內成員間的可靠通信，簇頭傳輸范圍減小，從而影響到安全應用的性能.在時間異步MAC協議中，分布式多信道異步MAC方案(Asynchronous Multi-channel MAC，AMMAC)[9]將50ms首尾相接的控制周期分成100個等長的時間槽，按照優先級的高低分配不同數量的時間槽，每個節點隨機選擇時間槽接入信道，安全消息不受這種約束.但這種時間槽分配與選擇機制略顯復雜進而影響協議的運行穩定性.為了解決這個問題，文獻[10]中提出基于時分復用的異步多信道MAC協議(Asynchronous TDMA-based Multi-channel MAC，ATMP)采用簡單的時分復用機制將周期分成5個時隙，節點等概率隨機選擇接入時隙，攜帶服務信息的節點只有在自己時隙內才能競爭信道，這減少了控制信道上的碰撞概率，但不適用于稀疏網絡環境，不具備一般性.文獻[11]提出一種高效可靠的MAC協議允許節點在控制周期和數據周期內各廣播一次安全信息，提高了安全信息的可靠性，但傳輸安全信息時，較高的計算復雜度會增大網絡時延.

因此，本文針對上述問題，提出一種基于分簇的多優先級MAC協議.該協議采用時間異步和多優先級接入機制，在保證安全信息實時可靠傳輸前提下，使消息按優先級別訪問控制信道；基于移動感知位置分簇算法完成簇頭選舉及分簇過程，并提出服務信道預約選擇方法，提高信道的吞吐量.

2 網絡模型

車載自組網拓撲結構的頻繁動態變化和車輛的高速移動為MAC協議的設計帶來極大挑戰.為使安全信息以最小時延并在可容忍范圍內訪問信道，以適用于不同交通流量.VANET情景模型，如圖1所示.圖中橢圓部分成簇，各簇由一個簇頭和若干簇成員組成.考慮到由N輛車形成的車載自組網，網絡中存在m個簇及t個其他節點(稱為孤兒節點)，si代表第i個簇的節點個數.因此，簇內節點數目集合為S={s1，s2，…，sm}，N滿足公式(1).

(1)

圖1 VANET情景分簇示意圖Fig.1 VANET scenario with clustering of vehicles

現對該網絡場景作以下假設：

1)每個節點均配有GPS車載設備.

2)每個節點都有兩種發射功率，分簇完成后，簇內節點使用低發射功率進行簇內通信，簇頭節點使用高發射功率進行簇外通信.

3)新節點的通信及簇內通信皆在1條服務信道上完成，該條服務信道是隨機選擇的；其余5條服務信道仍用于傳輸服務消息.

4)每隔一個傳輸半徑都有一個RSU，用于與簇頭進行簇外通信；每個RSU可以互相傳輸信息.

3 ACMP協議

ACMP協議主要包括以下四個方面：時間異步、多優先級訪問信道機制、基于移動位置感知的分簇算法、服務信道預約與選擇方法.ACMP協議中所用符號，如表1所示.

3.1 時間異步

為解決大多數時間同步協議信道利用率低的問題，ACMP協議采用如下改進的時間異步切換方式[9，10]：不進行服務信息收發的節點，繼續監聽控制信道；節點按照3.4節所提出的預約信道方法對服務信道進行無競爭的訪問.當節點預約信道完成時，就會立刻轉到已預約的信道上，進行有關服務信息的傳輸.服務信息全部傳輸完成后，節點轉到控制信道繼續監聽.為使當前網絡中的新節點監聽到緊急消息，所有簇頭節點將會在同步周期的空閑時隙進行廣播，如圖2所示.與時間同步的協議不同，ACMP協議沒有嚴格的控制周期和服務周期的界限，不需要所有節點同步地在控制信道和服務信道之間切換，最終使信道的資源得到充分利用.信道利用率提高的同時，也帶來了控制信道和服務信道吞吐量的提高.

表1 符號定義Table 1 Notations definition

圖2 ACMP協議的同步周期框架Fig.2 Synchronization interval framework of the ACMP protocol

3.2 多優先級訪問信道機制

在非飽和的車載自組網中，為保證安全信息可靠、實時傳輸，ACMP協議將在CCH上傳遞的信息分為三種類型：緊急的事件驅動型信息，一般的信標信息和非緊急的控制信息，優先級依次降低，網絡中的節點都應采用IEEE 802.11e增強型分布式協調接入機制.在該機制中，不同優先級接入類型(Access Category，AC)使用可變的仲裁幀間間隔(Arbitration Inter Frame Space，AIFS)和競爭窗口(Contention Windows，CW)來獲得不同的訪問信道機會.當信道空閑時，對于競爭信道的節點，本文將改變AIFS和競爭窗口的大小執行延時退避，仲裁幀間間隔為：

AIFSACi=AIFSNACi×SlotTime+SIFS

(2)

其中：AIFSN為仲裁幀間間隔數，SlotTime為一個時隙的長度，SIFS為常量短幀幀間間隔.設置AC1，AC2，AC3的AIFSN值分別為2，2，3；競爭窗口分別為7，15，15.相較于AC2和AC3的分組，AC1的分組具有較小的AIFS和CW值，故其在傳輸前將獲得較高的傳輸概率和較少的退避時間.根據多優先級訪問機制，ACMP協議控制周期包括三個階段，如圖2所示.緊急階段，用來傳輸緊急的安全信息SA(safety)；信標階段，用來廣播擴展的Beacon；服務階段，用來傳輸新增節點的擴展Beacon和WSA(Wave Service Advertisement，WSA)服務、發送請求幀(Request To Send，RTS)以及確認幀(Clear To Send，CTS).

3.3 基于移動位置感知的分簇算法

3.3.1 簇頭的選舉

簇頭的選擇是分簇算法中至關重要的環節之一，直接關系著簇的有效運行時間和穩定程度.ACMP協議提出了簇頭選擇參數：簇頭系數CCP，并將此參數寫入信標幀中.具體實現如下：

在信標階段，每個節點在信標幀中擴展以下三個部分來完成簇頭的選舉過程：(1)自身ID，占8byte；(2)所屬簇簇頭ID，占8byte；(3)簇頭參數，占4byte.信標幀結構，如圖3所示.與DMMAC協議不同，不需要傳遞額外的狀態信息占用控制信道.

圖3 信標幀結構Fig.3 Framework of beacon frame

本文采取如下三種信息作為簇頭系數的量化標準：

1)位置信息.網絡中每輛車計算其最佳簇頭位置及距最佳簇頭的距離，例如：第i個節點以自身的位置為原點，自身的行駛方向為x軸正半軸建立直角坐標系.假設第i個節點的傳輸范圍內有ni個鄰居節點，每個鄰居節點的位置通過坐標(X,Y)={(x1,xy),(x2,y2),L,(xni,yni)}表示出來.最佳簇頭的坐標，如公式(3)所示；并計算第i個節點到最佳簇頭的距離di，如公式(4)所示.

(3)

(4)

(5)

vmax=max{|vi-v1|，|vi-v2|，…，|vi-vni|}

(6)

3)行駛方向信息.每輛車計算其傳輸范圍內與之同向的車輛個數，例如：第i個節點的傳輸范圍內有ni個鄰居節點，速度同2)，那么其同向車個數Nsd，如公式(7)所示.

(7)

為在未來時刻使簇頭和簇內成員仍處于彼此通信范圍內，避免頻繁變換簇結構，此刻應選擇簇頭系數較大的節點，簇頭系數越大代表其成為簇頭的可能性越大，如公式(8)所示；Ps為位置量化標準；Po為速度量化標準；Pc為方向量化標準.

(8)

其中α，β，λ為感知位置量化標準的三個權值，且

(9)

設置α=0.4，β=λ=0.3，將在4.4節給出參數取值的實驗分析.

3.3.2 分簇算法的實現

簇頭選舉完成后，簇頭將在其傳輸范圍內廣播簇頭消息，監聽到該消息的節點將CHID設置為簇頭的ID，節點向CH發送ACK幀，CH收到其ACK幀更新簇成員信息表，節點成功加入簇；新節點加入網絡時入簇流程如圖4所示.具體實現如下：

圖4 新節點入簇流程圖Fig.4 Process of new nodes join in cluster

步驟 1.新節點進入該網絡時，將會發送請求加入簇數據包CFR.

步驟 2.在一定時間內，節點是否收到允許加入簇數據包CFA.若收到，節點立即在CCH上廣播其信標信息，CH監聽到其信標信息會自動更新簇成員信息表CMT，節點成為該簇的成員，新節點成功加入簇.如該節點的CCP符合簇頭選舉標準，節點將會被選舉為新的簇頭.注意：如果節點收到不止一個CFA包，選擇簇頭ID號較小的簇加入.否則，執行步驟3.

步驟 3.新節點將暫時成為一個“孤兒”節點，不屬于任何簇也不屬于此網絡.判斷節點是否收到CFR，若收到，該節點將會與發送CFR的源節點組成一個新簇，簇頭可隨機選取.否則，轉回步驟1.

3.4 服務信道的預約與選擇

3.4.1 服務階段的協商

與IEEE 1609.4不同，本協議采用預約信道方式完成對服務信道的無競爭訪問，每個簇頭節點存儲見表2.簇成員信息表MIL、簇活動成員預約表ARL和信道可用表CUL，表結構分別如表2(a)、(b)和(c)所示.

服務信道的具體預約過程如下：

步驟 1.WSA分組的廣播.在服務階段，服務提供者向網絡中所有節點廣播WSA分組，分組包括將要使用的SCH編號以及該服務傳輸時間長度、服務提供者ID等其它信息.

表2 ACMP協議中的三種表結構Table 2 Three lists structure in ACMP protocol

(b)簇活動成員預約表ARL活動成員ID預約信道編號預約信道時隙數據傳輸開始時間ID12O_t1S_t1…………(c)信道可用表CUL可用信道編號信道可用時隙1U_t1……

步驟 2.活動節點(感興趣的節點)的預約.其它節點監聽到該WSA分組，若對該服務感興趣，就會向CH發送一個預約聲明，表明自己有信息要在SCH上傳輸，執行步驟3；否則，節點將會繼續監聽CCH.

步驟 3.CH完善簇活動成員預約表.CH將會收集簇內所有活動節點聲明，首先為活動節點分配可用信道：對照MIL中活動節點傳輸所用信道編號與WSA分組的信道編號，取其編號相同的信道來完成預約過程.如有多個，可隨機選取一個.CH就會為該節點預約此信道進行服務消息的傳輸；之后CH將為活動節點分配可用時隙：基于CUL的信道可用時隙，按照3.4.2節所排順序為節點預約信道.在預約信息寫入ARL之前，CH會檢查預約信道號是否與預約表中已有預約信道號有沖突.如有沖突，就會在其開始傳輸時間上加一個等待時隙，等待時隙為信道釋放時間加上保護間隔GI.

步驟 4.CH向服務提供商發送RTS.簇內所有活動節點的預約信息全部寫入ARL后，CH將從[0，We]中隨機選擇一個時隙向服務提供商發送包括活動成員預約表及服務提供商ID的RTS并在簇內廣播ARL.其它CH監聽到RTS根據幀內信息更新自己的CUL.

步驟 5.服務提供商向CH回復CTS.幀中包括自身ID和簇頭ID.若CTS成功接收，表明信道預留成功.相應節點立即切換到已預約SCH進行服務信息的傳輸.傳輸完成后，立即釋放信道，繼續監聽控制信道.

3.4.2 信道內活動節點的排序

在一個同步周期內，當簇內節點競爭信道時，速度對簇頭到簇成員間的距離影響不大，因此在排序過程中只考慮相對位置和行駛方向對簇成員的影響.將簇頭指定為參照物，簇頭前方節點到簇頭的距離為正，反之為負.與簇頭同向的方向系數為1，反之為-1.本文定義a_dis為實際位移，其意義為簇成員離開本簇的可能性，如公式(10)所示.

a_dis=μ·s

(10)

公式(10)中μ代表方向系數，s代表簇頭到簇成員真正距離.a_dis值越大的節點離開簇的可能性越大，因此要先為a_dis值大的節點預約信道.當a_dis值相同時將會看μ的取值，將μ值為負的節點順序排到前面，這樣就完成信道內活動節點的排序過程.按圖5所示的環境況下，以節點A為簇頭，簇內的活動節點分別為B、C、D和E，則其排列順序為D、B、E和C.

圖5 網絡中簇內活動節點排序示意圖Fig.5 Schematic diagram of active nodes in a cluster

4 仿真及結果分析

為了驗證協議的有效性，在NS-2的仿真環境下，結合交通仿真軟件SUMO[12]生成的雙向四車道交通場景，進行仿真實驗.仿真中每個節點的業務量都相同，主要考察節點個數對各性能的影響.在大規模的車載自組網中，ACMP協議主要解決控制信道碰撞率較高所造成的安全信息延遲及信道吞吐量較低等問題，因此仿真實驗分析安全消息時延、服務信道的有效吞吐量及簇穩定程度的性能指標，結果與IEEE1609.4、ATMP和DMMAC進行比較.仿真參數設置如表3所示.

表3 仿真參數Table 3 Simulation parameters

4.1 安全消息平均時延

首先，比較隨著節點密度的變化，消息平均時延的變化情況.根據文獻[6]建立馬爾可夫模型并結合泊松過程模擬攜帶不同優先級信息的節點競爭控制信道的過程，計算網絡消息平均時延，如公式(11)所示.

(11)

圖6 安全消息時延隨節點密度變化Fig.6 Time delay of safety informationversus vehicle density

4.2 服務信道吞吐量

服務信道吞吐量是指單位時間內服務信道成功接收的比特數，本文中主要受成功預約服務信道的節點數及在一個同步周期中簇頭首次收到CTS的時間的影響.圖7是節點密度對服務信道吞吐量的影響情況.隨著節點密度增加，這四種協議的吞吐量都有一個先增加后減少的趨勢.當節點密度為0.3米/輛時，ACMP的服務吞吐量比IEEE 1609.4標準提高近52.6%，比DMMAC提高36.1%，比ATMP提高21.9%.這是由于IEEE 1609.4和DMMAC的控制周期為固定的50ms，在節點稀疏時，服務信道吞吐量會隨著節點密度增大而增加；當服務信道達到飽和后，節點密度的增加會使服務信道的競爭加劇，進而使分組投遞率下降，造成服務信道吞吐量降低.ATMP協議和ACMP協議都采用無競爭訪問服務信道方式，因此吞吐量會高于前兩種協議.另外， ACMP協議隨著節點密度增大，簇內活動成員增加致使預約信道數增加，會有更小的時延，更早完成服務信道的數據傳輸，比其它協議較晚進入飽和狀態.

圖7 SCH吞吐量隨節點密度變化Fig.7 Throughput of SCH with respect to vehicle density

4.3 簇頭平均時間

本協議采用分簇算法來完成對服務信道的預約，因此在考慮簇的穩定程度上定義簇頭平均時間CHT參數，計算網絡中簇的有效運行時間如下：

(12)

其中E[CHT]為簇頭平均時間，n為整個網絡的CH數量，TCH為簇頭運行的有效時間.圖8顯示的是在服務分組大小固定的情況下，兩種協議隨節點密度的增加，簇頭平均時間也會增加.當節點密度為0.25輛/米時，ACMP的CHT比DMMAC提高近14.3%，因為ACMP采用移動感知位置的簇頭選舉算法，簇頭壽命明顯提高，因此簇的有效運行時間更長.隨著節點密度升高，兩種協議的CHT差距逐漸減小.這是由于位置對CHT的影響不大，簇的穩定性得到提升.

圖8 簇頭平均時間隨節點密度變化Fig.8 Average CH time versus vehicle density

4.4 相關參數討論

為獲得權值α、β和λ的最佳取值，圖9為四種量化標準與簇結構重組次數的關系.從圖上可知：速度和方向對簇結構重組次數的影響大致相同，因此設置權值β=λ.為得出權值間的關系，用公式(13)進行采樣計算：

圖9 不同權值簇結構重組次數隨時間變化Fig.9 Recombination times of cluster structure changed with different weights over time

(13)

sk表示Ps的樣本，ok表示Po的樣本.公式(13)的計算結果為0.1.即α-β=0.1，根據公式(9)，可求得α=0.4，β=λ=0.3.

5 結 論

本文從提高信道利用率角度出發，提出一種保證安全信息實時且可靠的MAC協議.該協議將控制信道傳輸的信息劃分成不同類別，以確保高優先級信息的實時可靠的傳輸.并通過基于移動位置感知的分簇算法，增強簇的穩定性，在分簇的基礎上實現服務信道預約，有效地降低碰撞概率，從而增大信道的吞吐量.在交通稀疏時，ACMP協議會為節點預約更多的服務信息；在交通密集時，在保證與安全有關的信息可靠傳輸的基礎上，使服務信道得到充分利用，達到控制信道和服務信道較為均衡的狀態.在后續的研究工作中，將會完善該協議，使其適用于多種道路環境并且在簇的維護上會有進一步的研究.