基于Markov鏈的車載自組網MAC層建模及分析

孫 偉，張和生，2，潘 成，楊 軍，白 喆

（1.北京交通大學 電氣工程學院，北京100044；2.北京交通大學 軌道交通控制與安全國家重點實驗室，北京100044）

0 引 言

車 載 自 組 網（Vehicular ad－hoc networks，VANETs）依靠先進的信息技術和通信技術為日益嚴重的交通問題，如道路擁堵和事故頻發，提供了解決方案［1］。

在車輛間和車輛與基礎設施間的通信中，VANETs采用2010年批準的IEEE 802.11p［2］作為底層協議以解決車輛環境下的無線接入問題，如車輛高速移動導致的通信拓撲頻繁變換及不同應用類型通信性能的不同需求等。而MAC（Media access control）層在上述通信問題解決中起著重要作用。

IEEE 802.11p MAC采用IEEE 802.11e［3］的增強型分布信道訪問（Enhanced distributed channel access，EDCA）機制以提供多種應用類型的服務，然而不同類型的服務質量（Quality of service，QoS）要求不同，如安全類應用實時性要求較高［4］。IEEE 802.11p MAC 層對其參數進行了修改以適用于車路環境。為滿足不同類型應用的QoS，需要對IEEE 802.11p的網絡性能進行分析，并對性能指標進行求解，如吞吐量、時延、丟包率等。

很多文獻采用分析模型對IEEE 802.11e EDCA 機制進行了研究。其中大部分是對Bianchi模 型［5］的 改 進，如 文 獻［6］對DCF（Distributed coordination function）的非飽和吞吐量進行了計算。文獻［7］提出了基于Markov鏈的分析模型，但未考慮消息內部碰撞。文獻［8］建立了IEEE 802.11e的綜合分析模型對其性能進行分析。文獻［9，10］使用三維Markov 鏈對IEEE 802.11e EDCA 機制的不同接入類（Access categories，ACs）性能進行了分析。文獻［11］采用Markov鏈模型研究了IEEE 802.11p協議在安全方面的應用。文獻［12］采用二維Markov鏈對IEEE 802.11p EDCA 機制進行了分析，該模型分析時并未考慮信道忙時退避計數器的掛起機制。

本文采用二維Markov鏈建立了IEEE 802.11p EDCA 機制的飽和模型，通過該模型對吞吐量、丟包率和時延進行了求解。同時還研究了退避掛起機制對丟包率的影響。結果表明，隨著通信范圍內車輛數的增加，歸一化吞吐量逐漸減小，丟包率和時延逐漸增加。高優先級隊列始終有較大歸一化吞吐量和較小傳輸時延。同樣驗證了IEEE 802.11p采用的EDCA 機制能夠保證不同應用類型的服務質量。

1 IEEE 802.11p MAC的特點

MAC層采用的EDCA 機制是由DCF 擴展而來，因此其信道訪問方式與DCF 一致，均為CSMA／CA（Carrier sense multiple access with collision avoidance）。EDCA 定義了四類AC 以保證不同優先級消息的QoS，用AC［i］（i＝0，1，2，3）表示。

EDCA 機制中，不同優先級的AC 在其信道訪問時采用不同的仲裁幀間間隔（Arbitration inter frame spacing，AIFS）和 競 爭 窗 口（Contention window，CW）值，如表1所示。

表1 IEEE 802.11p EDCA參數值［2］Table 1 EDCA parameters of IEEE 802.11p［2］

AC［i］（i＝0，1，2，3）的TAIFS［AC［i］］計 算 公 式如下［2］：

式中：TSIFS是短幀間間隔的持續時間（Short inter frame spacing，SIFS）；TaSlotTime是一個時隙所持續的時間；NAIFSN［AC［i］］是AIFSN［AC［i］］的值。

信道訪問過程為：當AC［i］隊列有消息發送時，首先監聽信道，如果信道空閑持續時間超過AIFS［AC［i］］，且AC［i］的退避計數器的值為0，則該消息直接被發送，如圖1站點A 所示。如果不為0，AC［i］的退避計數器在每個空閑時隙減1，若此時檢測到信道忙，退避計數器被掛起，停止遞減，如圖1站點C所示。此后，站點重新監聽信道，如果信道持續空閑時間為AIFS［AC［i］］，退避計數器解掛開始遞減。若退避計數器值遞減為0，站點向信道發送該消息。當同一站點內多個AC隊列的退避計數器同時遞減為0，消息的同時發送導致內部碰撞。此時，內部碰撞由站點內的虛擬調度器采用沖突避免方式選擇高優先級AC消息的發送，從而造成低優先級AC 消息的重傳。不同站點間消息產生碰撞時，不論優先級高低，消息都需重傳。由表1和式（1）知，高優先級AC 具有較小的AIFS和CW 值，因此可優先獲得信道訪問權。

圖1 IEEE 802.11p EDCA信道訪問Fig.1 EDCA basic access mechanism of IEEE 802.11p

2 模型的建立與分析

2.1 EDCA機制的Markov鏈模型

MAC層在保證不同AC 的QoS上起著重要作用。為了分析不同AC 的QoS，需對IEEE 802.11p MAC層所采用的EDCA 機制進行建模分析。

采用EDCA 機制進行信道訪問時，AC 的退避過程實際為退避計數器狀態轉移的過程，狀態間的轉移符合Markov性，即下一狀態只與當前狀態有關而與過去狀態無關。因此可采用二維Markov鏈描述單個AC 的退避機理，如圖2 所示，該模型分析時考慮了不同AC 的不同競爭窗口值、消息的內部碰撞以及信道忙時的退避掛起機制。模型分析采用文獻［10］的類似方法。在分析時，假定信道為理想狀態，即數據包不存在由于誤碼導致的重傳。同時假定AC 隊列飽和，即每個隊列始終有消息發送。

圖2Markov鏈中二元組｛s（t），b（t）｝表示信道訪問的退避過程，s（t）為t時刻消息的重傳次數或稱退避階段（Backoff stage）的值，b（t）為t時刻退避計數器的值。狀態Di，j表示退避計數器掛起時所處的狀態，即此時的退避階段和退避計數器的值。pb表示檢測到信道忙時退避計數器的掛起概率。當退避計數器值減為0時，站點將向信道發送該消息，若此時同一站點內高優先級隊列或其他站點同時發送消息，則消息間發生碰撞，其概率為pc。碰撞使競爭窗口值加倍，重傳次數加1，進入下次退避過程，當超過最大重傳次數m時，消息將被丟棄。

圖2 IEEE 802.11p單個AC的Markov鏈模型Fig.2 Signal AC Markov model of IEEE 802.11p

由圖2Markov鏈模型知，消息在第j次退避階段，退避計數器的取值為［0，Wj－1］中的隨機整數。Wj的計算式如下：

Markov鏈的一步轉移概率如下：

（1）第j退避階段，退避計數器值從（j，k＋1）狀態轉移到（j，k）狀態，即時隙內檢測到信道空閑的概率為1－pb，其轉移表達式為：

（2）第j退避階段，退避計數器從（j，k＋1）狀態轉移到Di，k狀態，即時隙內檢測到信道忙導致退避計數器掛起的概率為pb，其轉移表達式為：

（3）第j－1退避階段，消息發送時，如果發生碰撞，使得消息重傳，則重傳次數加1，并轉至第j退避階段，其轉移表達式為：

（4）第j退避階段，若消息成功發送，則返回到初始階段，發送下一條消息，其表達式為：

（5）當達到最大退避階段m 時，若消息發送成功，則返回初始階段發送下一消息；反之，則丟棄該消息，同樣返回初始階段發送下一消息。因此在最大退避階段以概率1返回到初始階段。表達式為：

2.2 系統穩態概率分析

相鄰兩個退避階段的關系式為：

通過式（8）和式（9）可得出任意狀態與初始狀態的關系式為：

在平穩分布中，根據歸一化條件，可得初始狀態b0，0如式（11）所示：

任意退避階段只有退避計數器值減為0時，消息才能被發送。因此消息能被發送的概率τ的表達式為式（12）：

用τi表示站點內AC［i］（i＝0，1，2，3）隊列消息能被發送的概率，其表達式如式（13）所示：

由式（13）知，AC［i］隊列中消息能被發送的概率與AC［i］的最小競爭窗口值、碰撞概率和信道忙概率有關。需再找出τi、pci、pbi之間的其他關系式，聯立求解消息能被發送的概率和碰撞概率等。

若本站點內其他AC隊列或其他站點同時有消息發送時，消息間會產生碰撞。消息的內部碰撞依據消息優先級決定消息發送權，高優先級消息繼續發送，低優先級消息則重傳。與外部站點消息發生碰撞時，無論優先級高低消息都需重傳。用PIi表示AC［i］的內部碰撞概率，則其表達式為［13］：

AC［i］隊列消息發送概率σi的表達式為［16］：

式中：N 為站點總數量。

AC［i］消息發送時產生碰撞的概率為pci：

執行退避過程時，退避計數器的值在時隙內減少，即信道空閑概率為1－pbi，其表達式為：

將式（13）（17）（18）聯立組成一個非線性方程組，可求解出AC［i］的發送概率σi和碰撞概率pci。

2.3 歸一化吞吐量

歸一化吞吐量為時間段內數據幀成功發送的量。設Pidle為信道空閑即時隙內無消息發送的概率；PTr為時隙內至少有一個站點發送消息的概率；PSi為AC［i］消息成功發送即時隙內只有一個站點發送AC［i］消息的概率；PFail為由于碰撞導致消息發送失敗即時隙內有兩個或兩個以上的站點同時發送消息的概率。則其表達式為：

設Si為站點內AC［i］的歸一化吞吐量，則：

式中：TE［Li］為傳輸AC［i］數據包所需時間。分母第一部分為信道空閑時間的均值；第二部分為數據包成功發送的時間均值；第三部分為數據包發送失敗的時間均值。式（20）中TSi為消息成功發送的傳輸時延，TCi為消息間發生碰撞所持續的時間。其表達式為：

式中：THead為消息幀幀頭的傳輸時間；TLi為數據包的傳輸時間；δ為傳播時延；TSIFS為SIFS的持續時間；TACK為ACK 的傳輸時間；為碰撞時數據包最大傳輸時間。

2.4 丟包率

設PDropi為站點內AC［i］隊列的丟包率。若數據包第m 次重傳失敗，則該數據包將被丟棄造成丟包，丟包率表達式為：

2.5 時延分析

MAC層時延定義為：消息從成為AC隊列的隊首開始到接收站點成功接收到該幀為止的時間段，由接入時延和傳輸時延組成。用TD表示消息的時延，E［TDi］為AC［i］消息時延的均值，表達式如下［5］：

式中：E［Ni］為AC［i］消息退避重傳次數的均值，其表達式為：

式（23）中：E［BDi］為AC［i］消息的退避時間，該時間由兩部分組成，分別為：不掛起情況下，退避計數器連續減少到0所持續的時間，用Xi表示，其期望表達式如式（25）所示；檢測到信道忙導致退避計數器掛起所等待的時間，用FRi表示，表達式如式（26）所示。

式中：E［Nbacki］為AC［i］的退避計數器在遞減過程中被掛起的次數，其表達式為［5］：

AC［i］隊列消息的退避時間為：

T0為消息發生碰撞時，重新監聽信道前所等待的時間，在基本接入模式下其表達式為：

3 結果分析

3.1 性能指標分析

建立如圖3所示的通信場景。聯立求解得到歸一化吞吐量、丟包率和時延性能指標，并通過NS－2［14］仿真驗證了分析模型的準確性。計算中所需要參數的列表如下：數據包長度為512 bytes；位傳輸速率為6 Mbit／s；通信范圍為500 m；數據包產生量為10packet／s；短幀間間隔SIFS為32μs；時隙時間slottime為13μs；幀頭傳輸時間Thead為57μs；ACK 傳輸時間TACK為39μs；傳播時延δ為2μs。

圖4為不同AC隊列的歸一化吞吐量隨通信范圍內車輛數的變化情況。可見，隨著通信范圍內車輛數的增加，AC 隊列的歸一化吞吐量值逐漸減小。AC［3］隊列的吞吐量最大，而AC［0］最小。原因為發生內部沖突時，虛擬調度器會選擇高優先級消息發送，造成低優先級消息重傳。

圖3 通信場景Fig.3 Communication scenario

圖4 歸一化吞吐量隨車輛數變化圖Fig.4 Normalized throughput variation with number of vehicles

圖5 為不同AC隊列的丟包率隨通信范圍內車輛數的變化情況。通過求解公式知，丟包率只與碰撞概率有關。由圖5可知，不同AC 隊列的丟包率隨車輛數的增加而上升。當通信范圍內僅有一輛車時，AC［3］的丟包率為0，AC［0］的丟包率為1.3%，該丟包是由于消息的內部碰撞造成的。隨著通信范圍內車輛數的增加，消息碰撞加劇，導致消息重傳次數增加，丟包現象加劇。當通信范圍內有35輛車時，4個AC 的丟包率均超過了20%。為滿足丟包率不超過10%［3］的要求，由圖5知，在飽和情況下通信范圍內最大車輛數為19輛。

隨著通信范圍內車輛數的增加，不同AC 隊列消息的時延也增加，如圖6所示。其中，高優先級隊列AC［3］和AC［2］隊列的時延增加不明顯，而較低優先級隊列AC［1］和AC［0］的時延急劇增加，原因為高優先級消息發送的增加，阻塞了低優先級發送，從而導致時延增大。通信范圍內車輛數為35時，AC［3］和AC［2］的時延均小于100 ms，滿足安全應用數據交互的時限要求［12］。AC［1］和AC［0］可應用于非時間苛求類型的場合，如娛樂等。

圖5 丟包率隨車輛數變化圖Fig.5 Drop rate variation with number of vehicles

圖6 時延隨車輛數變化圖Fig.6 Time delay variation with number of vehicles

3.2 退避掛起機制對性能的影響

IEEE 802.11p協議規定退避時存在掛起機制。而很多文獻采用Markov鏈分析時沒予以考慮，退避計數器的值以概率1 遞減，即圖2 中pb＝0，不存在Di，j狀態。所以研究退避掛起機制對網絡性能（特別是對丟包率）的影響是必要的。

圖7 退避掛起機制對丟包率的影響Fig.7 Effect of backoff mechanism on drop rate

圖7 為退避掛起機制對丟包率的影響。當通信范圍內車輛數較少時，退避掛起機制對改善丟包率無明顯作用。但隨著通信范圍內車輛數的增加，無退避掛起機制會導致丟包率的急劇上升。若無退避機制，當通信范圍內有19輛車時，丟包率會達到90%以上，而存在退避掛起機制時，丟包率僅為10%。從而說明退避過程中采用掛起機制能有效地減少數據包碰撞概率，從而降低丟包率。

4 結束語

本文考慮了不同類型消息間的影響，在消息內部碰撞和信道忙時的退避掛起機制情況下，采用二維Markov鏈對IEEE 802.11p的EDCA 機制進行了建模。研究了歸一化吞吐量、丟包率和時延性能指標，并分析了退避掛起機制對丟包率的影響。結果表明：當通信范圍內車輛數固定時，單個站點的歸一化吞吐量和時延與不同優先級AC隊列有關；丟包率只與AC 隊列和碰撞概率有關。而高優先級隊列始終有較大吞吐量、較低時延和較小丟包率。通過分析得出為滿足安全類應用丟包率的要求，通信范圍內的車輛數最多為19輛。同樣也驗證了IEEE 802.11p 的EDCA機制能滿足不同類型消息的服務質量。

［1］Dar K，Bajhouya M，Gaber J，et al.Wireless communication technologies for ITS applications［J］.IEEE Communications Magazine，2010，48（5）：156－162.

［2］IEEE Std.IEEE 802.11p：Wireless LAN medium access control（MAC）and physical layer（PHY）specifications－amendment 7：wireless access in vehicular environment［S］.2010.

［3］IEEE 802.11e／D6.0.Draft supplement to part 11：Wireless medium access control（MAC）and physical layer specifications：medium access control（MAC）enhancement for quality of service（QoS）［S］.2003.

［4］Cheng H T，Shan H，Zhuang W.Infotainment and road safety service support in vehicular networking：From a communication perspective［C］∥Mech Syst Signal Process，2011，25（6）：2020－2038.

［5］Bianchi G.Performance analysis of the IEEE 802.11 distributed coordination function［J］.IEEE Journal on Selected Areas in Communications，2000，18（3）：535－547.

［6］楊衛東，李亞輝，馬建峰.衰落信道中802.11DCF的非飽和吞吐量分析［J］.吉林大學學報：工學版，2008，38（3）：695－699.Yang Wei－dong，Li Ya－Hui，Ma Jian－feng.Non－saturation throughput analysis of 802.11DCF in fading channel［J］.Journal of Jilin University（Engineering and Technology Edition），2008，38（3）：695－699.

［7］Robinson J，Randhawa T.Saturation throughput analysis of IEEE 802.11eenhanced distributed coordination function［J］.IEEE Journal Selected Areas Communication，2004，22（5）：917－928.

［8］Tursunova S，Kim Young－tak.Realistic IEEE 802.11eEDCA model for QoS－aware mobile cloud service provisioning［J］.IEEE Transactions on Consumer Electronics，2012，58（1）：60－68.

［9］Gas M，Kosek－saott K，Natkaniec M，et al.3D Markov chain－based saturation throughput model of IEEE 802.11EDCA［J］.Electronics Letters，2011，47（14）：826－827.

［10］Inan I，Keceli F，Ayanoglu E.Analysis of the 802.11eenhanced distributed channel access function［J］.IEEE Transactions on Communications，2009，57（6）：1753－1764.

［11］Yao Yuan，Rao Lei，Liu Xue.Performance and reliability analysis of IEEE 802.11p safety communication in a highway environment［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4198－4212.

［12］Han C，Dianati M，Tafazollir E，et al.Analytical study of the IEEE 802.11p MAC sublayer in vehicular networks［J］.IEEE Transactions on Intelligent Transportation Systems，2012，99：1－14.

［13］Huang C L，Liao W.Throughput and delay performance of IEEE 802.11e enhanced distributed channel access（EDCA）under saturation condition［J］.IEEE Transactions on Wireless Communications，2007，6（1）：136－145.

［14］The Network Simulator－ns－2.［DB／OL］［2014－06－21］.http：／／www.isi.edu／nsnam／ns／.