黃業(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é)議具有更突出的信道利用率。
在常見的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
為了檢驗(yàn)?zāi)P偷男诺览寐剩肕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)越性能。
圖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ì)算。