基于以太網負載的改進CSMA協議

齊少楠, 趙 航, 林金花

(1.長春工業大學 應用技術學院, 吉林 長春 130102;2.長春工業大學 數學與統計學院, 吉林 長春 130012)

0 引 言

載波偵聽多路訪問(Carrier Sense Multiple Access, CSMA)是一種MAC層協議,是解決以太網擁塞問題的關鍵技術之一。以太網技術具有價格低廉、通信速率高、兼容性好、帶寬大等諸多優點[1-2],廣泛應用于通信、航天、國防等對通信實時性具有嚴格要求的領域。

由于以太網采用帶沖突檢測的載波偵聽多路訪問(Carrier Sense Multiple Access/Collision Detection, CSMA/CD)的介質訪問機制,采用1-堅持CSMA協議及二進制指數退避BEB算法來處理報文沖突存在通信延遲不定等缺點。文獻[3]根據ACK字符發送成功的數據包個數,提出一種自適應反沖AAB算法,通過ACK計數器來調整反沖時隙,并給出算法的具體實現過程。之后更多學者對CSMA協議展開研究。美國加州大學開發的CSMA/DCR協議是走樹搜索協議的改進,每個終端具有唯一的時隙分配,如果終端沒有數據發送,則其時隙將被沒收[4]。文獻[5]針對信道沖突/空閑比設置4種優先級,提出基于P-堅持CSMA協議的自適應調整發送概率的RLBSA算法。文獻[6]基于現場可編程門陣列設計通信電路,首先利用平均周期法建模,計算得出雙優先級P-堅持CSMA協議的吞吐量與節點平均功率理論值。文獻[7]針對面向低壓電力線通信人工蛛網的網絡,提出一種根據參與信道競爭節點數調整接入概率的改進型自適應P-堅持CSMA協議優化方法,從而控制節點發送數據分組行為。文獻[8]提出一種根據鏈路占用率和優先級動態調整隊列傳輸窗口,從而提高傳輸效率的CSMA調度算法。文獻[9]根據網絡吞吐量和終端發包概率以及數據包碰撞率之間的關系,提出基于CSMA/CA提升網絡吞吐量的方法。文獻[10]提出一種自適應碰撞時長的三時隙P-CSMA協議,其中包括信息分組發送成功時長、發生碰撞時長以及空閑時長。文中提出一種基于以太網負載的改進CSMA協議。當網絡負載較輕時,采用1-Persistent CSMA協議和P-Persistent CSMA協議(P值較大)來減小終端接入信道的時延;當網絡重載時,采用非堅持CSMA協議和P值較小的P-堅持CSMA協議來減少數據沖突。

1 協議評價性能指標

負載、吞吐量及平均傳輸時延這三個指標是評價協議性能的最基本指標。吞吐量定義為每幀時內通過信道成功傳輸的數據,記為S;負載定義為每幀時內終端新產生的數據與遭受沖突而重傳數據的數據之和,記為G。對于一個理想協議,負載與吞吐量之間的關系為

(1)

吞吐量與業務量之間的關系如圖1所示。

圖1 吞吐量與業務量之間的關系

從圖1可以看出,在理想情況下,如果沒有數據包產生,或者所有傳輸的數據包由于碰撞被丟棄,此時,吞吐量為0,如果所有數據都成功傳輸,則吞吐量為1。然而,在實際情況下,吞吐量在負載較小時,隨著負載的增加而增加,而當負載大于一定門限后,吞吐量隨著負載的增加而下降。

設任意標準幀長度為lp,數據在信道上的傳輸速率為br,則標準幀長度的數據傳輸時間T0為

(2)

當負載大于某一閾值時,平均傳輸時延將大幅度增加。當成功發送的數據包數量達到total=5 000時,成功發送的數據包和失敗發送的數據包總延遲時間為Tw,則平均傳輸延遲Tdelay為

(3)

2 CSMA協議通信模型

在分析CSMA協議的性能時,使用下列假設:

1)仿真系統模型是一個分組通信系統,也是一個無線呼叫源模型,若每個終端獨立隨機生成分組,所有終端到達幀服從Possion分布。

2)假設每個終端的傳播延遲τ相同,即信道上任意兩個終端的單向傳播時延相同;數據傳輸時間T0相同,即傳輸固定長度的幀需要的時間相同,歸一化傳播延遲為α=τ/T0,且α<1。

3)在任何時刻,每個終端只有一個數據包準備發送,載波偵聽過程是瞬間完成的。

4)信道為理想有線信道,是時不變系統,假設各終端的信號功率相同,并且無捕獲效應,所有在信道內碰撞的數據包都必須重發。

基于負載的CSMA改進協議設計,CSMA協議一般分為1-堅持CSMA協議、P-堅持CSMA協議和非堅持CSMA協議[11]。在不同的負載下,三種協議不同負載時表現不一,以下分別就這三種協議作一剖析。

在低負載時,使用1-堅持CSMA協議可獲得更好的性能。原因是1-堅持CSMA協議的規則為:若終端有數據要發送,首先監聽所在的信道(即載波監聽),如果信道在idle狀態下,數據可被即時發送;如果信道是busy,數據將不被發送,直到發現信道處于空閑狀態。雖然1-堅持CSMA協議避免了介質利用率的損失,在低負載下,延遲較低且吞吐量較高,但是一旦負載增加,多個終端發送數據時,沖突將不可避免。

設λ為數據包平均到達率,每幀時負載G與幀時T0的關系為

G=λT0。

(4)

設PS為數據成功發送的概率,則吞吐量S與負載G的關系為

S=PSG。

(5)

由于終端產生的數據與經歷沖突重傳的數據包傳輸到達在概率分布上滿足泊松分布,則T0秒內到達k個數據包的概率為

(6)

一個數據發送成功要求在T0+τ內有且僅有一個數據到達,在T0+τ內有一個數據到達的概率為

P[在T0+τ時間內有一個數據到達]=

λ(T0+τ)e-λ(T0+τ)=

G(1+α)e-G(1+α)。

(7)

在T0+τ內有數據到達的概率為

P[在T0+τ時間內有數據到達]=

1-e-λ(T0+λ)=

1-e-G(1+α)。

(8)

在τ內有一個數據到達的概率為

P[在τ內有一個數據到達]=λτe-λτ=

αGe-αG。

(9)

在τ內有數據到達的概率為

P[在τ內有數據到達]=1-e-Gτ/T0=

1-e-αG。

(10)

可以求得1-堅持CSMA協議吞吐量與負載的關系為

(11)

當忽略歸一化傳播延遲時,吞吐量與負載的關系式收斂于

(12)

在負載較高時,非堅持CSMA協議性能較高。主要原因是非堅持CSMA協議的規則為:若終端存在要發送數據的情況,先偵聽信道后再發送數據,如果信道是idle,信息可馬上發送出去;當信道處于busy狀態時,不再監聽信道,而是隨機延遲一段時間后再監聽。盡管非堅持CSMA協議在高負載時使用隨機重傳次數來降低碰撞概率,但是低負載情況下,非堅持CSMA協議極有可能下一次偵聽前信道已處于idle狀態,因此會使信道資源浪費,導致利用率低。

數據包產生間隔表示為

(13)

式中:n----終端數目。

當信道忙時,數據包等待一個隨機時間重發,該隨機時間為

Tcol=-Tintlog(1-m), 0≤m≤1,

(14)

式中:m----0～1之間的隨機值。

用同樣方法可求得非堅持CSMA協議吞吐量S與負載G之間的關系為

(15)

P-堅持CSMA協議作為折中方案不僅能在非堅持CSMA協議等重負載時降低碰撞,而且在1-堅持CSMA等低負載時降低信道空閑時間。P-堅持CSMA應用在時隙信道上,它的協議規則是節點在準備傳輸數據時先監聽信道,如果信道在idle狀態下,則按概率P進行信息傳輸,按概率1-P延遲傳輸直至數據傳輸成功。若監聽到信道在busy狀態下,則等待下個時隙時重復以上過程。

對于P-堅持CSMA協議,可以得到吞吐量S與負載G的關系為

(16)

其中x值定義為

(17)

由于P-堅持CSMA協議的負載G與吞吐量S之間的關系與P值相關,所以P-堅持CSMA協議的仿真結果在下文闡述。

P-堅持CSMA協議適用于分時隙的信道,假定共有k個終端競爭信道的使用權,終端在各自時隙傳輸概率為P,信道處于空閑狀態且沒有正在傳輸的數據,則可以得到負載G的表達式為

(18)

一般情況下,傳輸時間T0遠大于傳播延遲τ,所以在該狀態下的負載G約等于競爭信道的終端數k。

終端競爭得到信道的概率是任意一個終端以概率P發送,而其他(k-1)個終端以(1-P)的概率延遲到下個時隙,則該終端成功發送概率為

A=kP(1-P)k-1。

(19)

由式(19)可以求得,當P=1/k時,最大終端成功發送概率A與競爭信道的終端數量k之間的關系為

(20)

終端競爭信道成功概率與競爭終端數目關系如圖2所示。

圖2 終端競爭信道成功概率與競爭終端數目關系

從圖2可以看出,競爭終端數量少的情況下,成功的可能性大,但競爭終端數量一旦達到5個后,其可能性就會逐漸接近1/e。當P=1/k時,A最大,但是,隨著競爭終端數目的增加,P的取值會越來越小,造成大量數據包延時重發。

為了解決上述問題,終端在發送數據前,先預測k值,然后根據k的閾值判斷以某種介質訪問控制方法發送數據。隨著網絡負載增加,競爭信道終端數也隨之增加,而相應的協議會隨之調整,從而減小發生碰撞的概率。

假設k的取值為(1,+∞),當k=1時,網絡負載較低,則采用1-堅持CSMA協議;當k在2～5時,選擇發送概率P為1/k的P-堅持CSMA協議,根據競爭終端數目確定P的取值分別為1/2、1/3、1/4、1/5,引入自適應機制,使系統的吞吐量能夠維持相對穩定高效;當k>5時,最大終端成功發送概率趨近于1/e,并且P值過小,使得網絡阻塞,所以此時選擇非堅持CSMA協議作為以太網介質訪問控制層協議。

3 仿真分析

IEEE802.3協議定義最小幀長為512 bit,在實際以太網中,為驗證文中提出的算法性能,利用Matlab R2014a仿真工具,假設所需發送的數據服從參數為λ的泊松分布,數據包長度為512 bit,仿真條件設為比特速率為6×106bit/s,符號速率為0.25×106符號/s,歸一化傳輸延遲為0.08,并將100個終端隨機布置在半徑為100 m的服務區域內。

在不同負載情況下,對吞吐量與負載關系進行分析,結果如圖3所示。

圖3 CSMA協議的吞吐量與負載的關系

隨著負載的增加,網絡吞吐量起初呈上升趨勢,1-堅持CSMA協議吞吐量與負載的增長曲線最陡,在G=1附近時,吞吐量達到最高值53.79%,非堅持CSMA協議增長曲線最緩,在G=3附近時,吞吐量最高值為55.31%,P-堅持CSAM協議吞吐量介于1-堅持CSMA協議與非堅持CSMA協議之間;當吞吐量達到最高后,隨著負載的增加,網絡吞吐量呈下降趨勢,非堅持CSMA協議吞吐量與負載的下降曲線最緩,在G=36附近時,網絡吞吐量小于5%,1-堅持CSMA協議下降趨勢最陡,在G=5附近時,網絡吞吐量小于5%。

由圖3可見,基于負載的改進CSMA協議可以隨著負載的變化對協議進行相應調整,與1-堅持CSMA協議、P-堅持CSMA協議,以及非堅持CSMA協議相比,吞吐量明顯更高。

對不同負載下的傳輸延遲進行分析,結果如圖4所示。

圖4 CSMA協議的傳輸延時與負載的關系

當網絡負載較小時,1-堅持CSMA協議傳輸延遲顯著低于非堅持CSMA協議傳輸延遲,由于1-堅持CSMA協議使用連續監聽信道方式,當檢測到信道空閑時會立即進行數據傳輸,而非堅持CSMA協議偵聽到沖突后會等待一段隨機時間,從而造成很大的傳輸延遲;在網絡負載較大時,1-堅持CSMA協議傳輸延遲會急劇增加,由于1-堅持CSMA協議采用持續偵聽信道的方式,所以隨著網絡負載的增加,數據沖突數就會急劇增大,而非堅持CSMA協議在信道忙時,發送數據會隨機等待一段時間,避免了沖突的發生,所以傳輸延遲會較低。P-堅持CSMA協議在發現信道空閑后,按P概率發送該數據,并且按(1-P)概率將該數據推遲傳送至下一通道。P-堅持CSMA協議的延遲性能介于1-堅持CSMA協議和非堅持CSMA協議之間。

從圖4可以看出,改進后基于負載的CSMA協議可以根據負載的變化對協議進行相應調整,低負載時采用1-堅持CSMA協議,高負載時采用非堅持CSMA協議,而負載不處于兩個極端狀態時,則采用P-堅持CSMA協議,從整體上看,基于負載改進的CSMA協議傳輸延遲明顯比其他協議傳輸時延更低。

4 結 語

根據以太網的網絡負載變化情況提出一種改進的CSMA協議,基于在1-堅持CSMA協議、P-堅持CSMA協議,以及非堅持CSMA協議,提出一種通過預估競爭信道沖突數而自適應切換MAC層介質訪問機制的方法,從而在不同負載情況下,保證最大吞吐量及滿足實時性要求,實驗仿真和模型分析結果驗證了該方法的有效性。