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

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

（1.華南理工大學(xué)廣州學(xué)院 廣東 廣州　510800；2.韶關(guān)學(xué)院 廣東 韶關(guān)　512005）

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

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

（1.華南理工大學(xué)廣州學(xué)院 廣東 廣州510800；2.韶關(guān)學(xué)院 廣東 韶關(guān)512005）

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

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

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

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

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

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

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

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

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

4）信道實(shí)時(shí)監(jiān)測(cè)接收信號(hào)；

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

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

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

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

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

10）數(shù)據(jù)幀沖突時(shí)，終端發(fā)送沖突信號(hào)的時(shí)間J對(duì)各個(gè)終端一樣；

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

12）沖突的檢測(cè)時(shí)間忽略不計(jì)；

13）信道是理想信道。

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

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

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

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

由式（1）～（7）可計(jì)算出：

將k逐一取值，計(jì)算之后得當(dāng)p=p0時(shí)，P（a=k|C）、P（a=k|的最大值，記為

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

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

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

2　模型仿真

為了檢驗(yàn)?zāi)Ｐ偷男诺览寐剩肕atlab2010a進(jìn)行仿真實(shí)驗(yàn)，設(shè)信道利用率為S，每幀時(shí)平均發(fā)送幀數(shù)為G，初始發(fā)送概率設(shè)為p0=1，發(fā)送延時(shí)τ=512 bytes，數(shù)據(jù)幀傳送幀時(shí)F =16τ，沖突反饋時(shí)長(zhǎng)J=τ。仿真得到的信道利用率S和平均發(fā)送幀數(shù)G的關(guān)系如圖2所示。

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

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

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

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

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

3　結(jié)　論

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

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

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

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

[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]毛秀偉，吳鐵軍.自適應(yīng)p-持續(xù)CSMA/CD介質(zhì)訪問控制策略[J].通信學(xué)報(bào)，2003，24（8）:161-167.

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

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

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

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

[10]Andrew S.Tanenbaum.計(jì)算機(jī)網(wǎng)絡(luò)[M].潘愛民，譯.4版.北京：清華大學(xué)出版社，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稿件編號(hào)：201510030

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

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