基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議

黃業(yè)文，楊榮領，鄺神芬

（1.華南理工大學廣州學院 廣東 廣州　510800；2.韶關學院 廣東 韶關　512005）

基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議

黃業(yè)文1，楊榮領1，鄺神芬2

（1.華南理工大學廣州學院 廣東 廣州510800；2.韶關學院 廣東 韶關512005）

針對計算機終端中p-持續(xù)CSMA協(xié)議的信道利用率的問題進行研究，為了能更好的利用信道發(fā)送數(shù)據(jù)，提高信道利用率，采用了基于貝葉斯決策統(tǒng)計理論，通過全概率公式拆分，對p-持續(xù)CSMA協(xié)議中的參數(shù)p進行動態(tài)自適應擬合的一種CSMA協(xié)議改進方法。用Matlab2010a進行模擬仿真實驗，得出改進后的自適應p-持續(xù)CSMA協(xié)議比靜態(tài)的p-持續(xù)CSMA協(xié)議對信道有高20%左右的利用率。

貝葉斯決策；p-持續(xù)CSMA；吞吐率；自適應

網(wǎng)絡終端信道的分配從上世紀70年代就成為了計算機網(wǎng)絡研究的熱點，最開始是 Norman Abramson研究的ALOHA系統(tǒng)，經(jīng)歷了純ALOHA系統(tǒng)，分槽ALOHA系統(tǒng)。之后Kleinrock和Tobagi推廣到載波檢測協(xié)議，研究了持續(xù)的和非持續(xù)的CSMA協(xié)議，又分為1-持續(xù)的CSMA協(xié)議和p-持續(xù)的CSMA協(xié)議。后來進一步改進成帶沖突檢測的CSMA協(xié)議。之后更多的工作者研究了p-持續(xù)CSMA協(xié)議在計算機終端隨機競爭接入信道中的應用[1-6]。CSMA協(xié)議主要是發(fā)送從MAC子層交過來的數(shù)據(jù)幀，對于怎么樣有效地發(fā)送數(shù)據(jù)幀，使得信道能夠有較好的利用率，并且盡可能大的提高信道利用率成為了CSMA協(xié)議研究的最主要的問題。直至當代，CSMA協(xié)議仍然是計算機網(wǎng)絡研究的熱點，各類文獻已經(jīng)在研究各種實際出現(xiàn)的繁雜情況下的數(shù)據(jù)幀發(fā)送，并且已有了一定的研究結果。本文在一些文獻研究的基礎上，提出基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議，該協(xié)議是通過全概率公式拆分，對p-持續(xù)CSMA協(xié)議中的數(shù)據(jù)幀發(fā)送概率p利用貝葉斯公式進行擬合的改進[7-8]協(xié)議。通過理論分析之后，用Matlab2010a進行模型仿真，仿真結果表明本文基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議比常見的的靜態(tài)p-持續(xù)CSMA協(xié)議具有更突出的信道利用率。

1　自適應p-持續(xù)CSMA協(xié)議模型

在常見的p-持續(xù)CSMA協(xié)議中[9]，信道以數(shù)值p發(fā)送上層下交的數(shù)據(jù)時，p值是靜態(tài)不變的。這樣的系統(tǒng)運行起來比較簡單，不用關注系統(tǒng)的擁塞情況，只能按照既定的協(xié)議單調地發(fā)送數(shù)據(jù)幀。從而對信道的利用率也不會很高，使得系統(tǒng)一直在忙卻處于信道利用率效率較為低下的狀態(tài)中。相對于一般的靜態(tài)p-持續(xù)CSMA協(xié)議[10]，為了提高系統(tǒng)信道利用率，本文利用全概率公式拆分提出基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議模型，該模型的主要特點是：只要發(fā)生數(shù)據(jù)幀傳輸，數(shù)值p隨著系統(tǒng)擁塞情況進行動態(tài)調整，不管終端是否發(fā)生沖突重傳。其中數(shù)值p由基于貝葉斯決策統(tǒng)計理論的全概率公式拆分計算來確定。這樣的模型因為關注到系統(tǒng)的擁塞狀況，對擁塞狀況來調整終端數(shù)據(jù)幀的發(fā)送頻率來避免數(shù)據(jù)幀發(fā)送發(fā)生沖突，因此能夠使得系統(tǒng)信道能夠得到較高的利用率。但是也存在一定的缺陷，為了調整p的取值，需要用到一小部分系統(tǒng)的資源。該模型實質就是損失一部分系統(tǒng)資源來調整p值提高系統(tǒng)信道利用率的模型研究，這也是動態(tài)p-持續(xù)CSMA協(xié)議模型繞不過去的彎。在模型中，發(fā)生數(shù)據(jù)幀傳送時，如果信道不空閑，終端繼續(xù)監(jiān)測信道直到信道重新處于競爭時隙，此時，終端才開始發(fā)送上層移交的數(shù)據(jù)，終端以概率p發(fā)送數(shù)據(jù)，以概率1-p將數(shù)據(jù)調整到下一個時隙繼續(xù)發(fā)送，時隙寬度記為δ。如果系統(tǒng)終端順利發(fā)送數(shù)據(jù)幀，立即調整p值大小，如果終端發(fā)送數(shù)據(jù)幀過程中遭遇沖突，系統(tǒng)同樣調整p值大小，將數(shù)據(jù)幀發(fā)送往后延遲隨機時間t，t∈（0，T），再次進行監(jiān)測，競爭信道以等待發(fā)送，如此循環(huán)。

基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議的隨機接入流程如圖1所示，發(fā)送數(shù)據(jù)幀是引入隨機數(shù)j，j與p比較后，j

1）系統(tǒng)信道只有一個，有無窮終端，；

2）數(shù)據(jù)幀平均到達率λ～N（μ，σ2），其密度函數(shù)為φμ，σ（x）；

3）終端在由數(shù)據(jù)幀發(fā)送轉為數(shù)據(jù)幀接收是瞬時的；

4）信道實時監(jiān)測接收信號；

5）在每個時隙（間隔足夠小）內，每一終端有不超過一個數(shù)據(jù)幀等待競爭信道；

6）系統(tǒng)內站點間的數(shù)據(jù)傳輸存在延時，延時假設為τ；

7）系統(tǒng)內包括新到達的數(shù)據(jù)幀和需要重發(fā)的數(shù)據(jù)幀，各個終端數(shù)據(jù)幀等待發(fā)送的數(shù)目服從參數(shù)為λ的泊松分布，λ為平均到達率，密度函數(shù)為p（k，λ），k∈N；

8）數(shù)據(jù)幀長度相等，記每幀時為F，F(xiàn)是τ的整數(shù)倍；

9）若發(fā)送過程中檢測到發(fā)生沖突，立即停止數(shù)據(jù)幀傳送；

10）數(shù)據(jù)幀沖突時，終端發(fā)送沖突信號的時間J對各個終端一樣；

11）只要信道發(fā)送數(shù)據(jù)時數(shù)據(jù)幀重疊，就需要重新發(fā)送數(shù)據(jù)幀；

12）沖突的檢測時間忽略不計；

13）信道是理想信道。

設模型中有上層移送數(shù)據(jù)待發(fā)的終端數(shù)記為a，即整個系統(tǒng)要發(fā)的幀數(shù)為a。a由假設（1）、（2）確定，a為正數(shù)。系統(tǒng)終端發(fā)送數(shù)據(jù)幀時，當p最接近時信道利用率達到最大，所以對p進行調整取值時，最優(yōu)的選擇應該是，但是這只是客觀存在的一個數(shù)值，不可能精確的尋找出來，只能通過模型研究，擬合，尋求盡量接近其理想值的方法。設p0是終端系統(tǒng)即時p值，由假設（2），通過全概率公式計算，對即時p值進行最大概率的估計，得a的初始估計為這個數(shù)值作

為貝葉斯公式的先驗概率，該a值認為是瞬時λ的最優(yōu)概率估計，再由假設（2），因為λ>0，λ～N（k，σ2），由3σ原則，可得λ∈（0，2k）取值范圍是，從而

圖1　基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議流程圖Fig.1　Flowchart of dynamic p-persistent CSMA protocol based on Bayesian decision theory

根據(jù)模型假設（1）、（2）可得以下計算式子：

由式（1）～（7）可計算出：

將k逐一取值，計算之后得當p=p0時，P（a=k|C）、P（a=k|的最大值，記為

在信道利用率概率最大的意義下，p=p0時進行一次信道競爭后，若系統(tǒng)遭遇傳送數(shù)據(jù)幀重復，p自適應調整為；若系統(tǒng)不發(fā)生數(shù)據(jù)幀重復，p自適應調整為至此完成一個數(shù)據(jù)幀發(fā)送，繼續(xù)循環(huán)下去即為信道吞吐率最大的基于貝葉斯決策的自適應p-堅持CSMA協(xié)議模型，該模型較好的解決了關鍵參數(shù)p的選取的問題。參數(shù)p的選取基于貝葉斯公式，是由系統(tǒng)擁塞情況調整的，這是本文基于貝葉斯決策的自適應p-堅持CSMA協(xié)議算法的改進之處。

對函數(shù)f（p0，C），和f（p0，C）的部分計算結果可見表1。在實際應用時，只要對照表1就可以查詢到相應的p值。

表1　基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議p值選取表Tab.1　p-value selection table of dynamic p-persistent CSMA protocol based on Bayesian decision theory

2　模型仿真

為了檢驗模型的信道利用率，利用Matlab2010a進行仿真實驗，設信道利用率為S，每幀時平均發(fā)送幀數(shù)為G，初始發(fā)送概率設為p0=1，發(fā)送延時τ=512 bytes，數(shù)據(jù)幀傳送幀時F =16τ，沖突反饋時長J=τ。仿真得到的信道利用率S和平均發(fā)送幀數(shù)G的關系如圖2所示。

圖2每幀時平均發(fā)送幀數(shù)G∈（0，1 000），可以看到G值很大時信道利用率仍然在85%左右，這表明模型的吞吐率是較好的。

在p-持續(xù)CSMA協(xié)議中，分別對p=1，0.5，0.1，0.01，進行了F=16τ，J=τ，τ=512 bytes的模型仿真，其S和G的變化關系如圖3所示。

圖3可以看到不同的p值發(fā)生擁塞的情況不同，p= 1，0.5，0.1，0.01時發(fā)生擁塞分別發(fā)生在G=10，20，100，1 000，并且在沒有發(fā)生擁塞時信道的利用率也是比較低效的。在G∈（0，10）的一般取值范圍內信道利用率在45%～65%之間。

圖2　自適應p-持續(xù)CSMA協(xié)議S和G變化關系圖Fig.2　S and G function diagram of dynamic p-persistent CSMA protocol based on Bayesian decision theory

為了更清楚地對比文中的動態(tài)p值協(xié)議和一般的靜態(tài)p值協(xié)議的信道利用率吞吐性能，取0≤G≤10，以步長0.1進行仿真，得到p分別為1，0.5，0.1，0.01情形下平均發(fā)送幀數(shù)G和信道利用率S的函數(shù)關系，如圖4所示。圖4充分體現(xiàn)了本文模型的優(yōu)越性能。

3　結　論

圖2、圖3和圖4的Matlab2010a仿真實驗表明，相對于常見的p-持續(xù)CSMA協(xié)議，本文基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議使得終端數(shù)據(jù)發(fā)送在整體上有較好的數(shù)據(jù)幀吞吐性，信道得到較高的利用率。改良后的基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議整體信道利用率高達85%以上，而其他的協(xié)議信道利用率或者開始較高但后來隨著數(shù)據(jù)發(fā)送量增大立刻急劇降低，例如p=1，p=0.5時，或者開始較低而隨著數(shù)據(jù)發(fā)送量增大才會緩慢改善慢慢增大，例如p= 0.1，p=0.01時，這些情況對信道的平均利用率在45～65%之間。本文基于貝葉斯決策的自適應p-持續(xù)CSMA協(xié)議很好的避免了常見的p-持續(xù)CSMA協(xié)議中信道利用率較低的缺陷，實際應用時，可將p值先計算出來，存于一個存貯棧中，方便讀取，模型的實際應用性較好。

圖3　p-持續(xù)CSMA協(xié)議S和G變化關系圖Fig.3　S and G function diagram of p-persistent CSMA protocol

圖4　自適應p和固定p的協(xié)議S和G變化關系圖Fig.4　S and G function diagram about dynamic p-persistent and p-persistent's CSMA protocol

協(xié)議模型提出了一種能大幅度提高信道利用率的動態(tài)改變p值的新方法，該模型的研究是初步的，下一步將對模型進行完善。模型中的一部分假設是比較理想的，實際情況會復雜的多，例如，信道監(jiān)測可能受到系統(tǒng)電壓變化產(chǎn)生的一些信號影響，信道不是理想信道等等，所以要對協(xié)議模型進行進一步的完善，能夠讓模型越來越適用于復雜的實際。

[1]Gallager R G.A perspective on multiaccess Channels[J]. IEEE Trans.on Information Theory，1985，31（2）:124-142.

[2]Cali F，Conti M，Gregori E.IEEE 802.11 protocol:design and performance evaluation of an adapative backoff mechanism[J]. IEEEJournalonSelectedAreasinCommunications，2000，18（9）:1774-1786.

[3]Breno R，Conti M，Gregori E.Optimal capacity of p-persistent CSMA protocols[J].IEEE Communications Lettes，2003，7 （3）:139-141.

[4]Cali F，Conti M，Gregori E.Dynamic tuning of the IEEE 802.11 protocol to achieve a theoretical throughput limit[J]. IEEE/ACM Trans.on Networking，2000，8（6）:785-799.

[5]毛秀偉，吳鐵軍.自適應p-持續(xù)CSMA/CD介質訪問控制策略[J].通信學報，2003，24（8）:161-167.

[6]何偉，南敬唱，潘峰.改進的動態(tài)p-持續(xù)CSMA協(xié)議[J].計算機工程，2010，36（21）:118-120.

[7]朱金玲.貝葉斯決策分析及改進 [J].江蘇統(tǒng)計，2006（6）: 27-28.

[8]翟軍昌，車偉偉，劉艷麗，等.基于改進信息增益的垃圾郵件過濾研究[J].電子設計工程，2012（13）:9-11.

[9]吳汶泰，扈維，林勝潔.頒布式單片機網(wǎng)絡中CSMA的軟件設計與性能分析[J].電子科技，2009（7）:93-95.

[10]Andrew S.Tanenbaum.計算機網(wǎng)絡[M].潘愛民，譯.4版.北京：清華大學出版社，2004.

Adaptive p-persistent CSMA protocol based on Bayesian decision theory

HUANG Ye-wen1，YANG Rong-ling1，KUANG Shen-fen2
（1.Guangzhou College of South China University of Technology，Guangzhou 510800，China；2.Shaoguan University，Shaoguan 512005，China）

Research on the problem about the channel utilization of p-persistent CSMA protocol in computer terminal.In order to improve the channel utilization，this paper proposes an adaptive p-persistent CSMA protocol based on Bayesian decision theory by calculation of full probability formula.Using Matlab2010a to carry on the simulation experiment，the improved adaptive p-persistent CSMA protocol has a higher utilization ratio than the others of fixed p-CSMA protocol which it rase about 20%.

Bayesian decision theory；p-persistent CSMA；throughput；adaptive

TN911.1

A

1674－6236（2016）01-0073-04

2015-10-08稿件編號：201510030

國家自然科學基金（61305036）；華南理工大學廣州學院青年教師科研基金（XQ114004）

黃業(yè)文（1979—），男，廣西北流人，碩士，講師。研究方向：數(shù)理統(tǒng)計，計算機網(wǎng)絡與分布計算。