方　飛，余文春

(1. 內(nèi)江師范學(xué)院 工程技術(shù)學(xué)院，四川 內(nèi)江 641110；2.電子科技大學(xué) 通信學(xué)院，成都 611731)

?

分級(jí)自適應(yīng)偽貝葉斯時(shí)隙ALOHA控制算法

方飛1,2，余文春1

(1. 內(nèi)江師范學(xué)院 工程技術(shù)學(xué)院，四川 內(nèi)江 641110；2.電子科技大學(xué) 通信學(xué)院，成都 611731)

摘要：時(shí)隙ALOHA需要使用控制算法以保證系統(tǒng)獲得穩(wěn)定吞吐量，而控制算法的關(guān)鍵是精確估計(jì)系統(tǒng)中的節(jié)點(diǎn)數(shù)。針對(duì)系統(tǒng)中的節(jié)點(diǎn)數(shù)在某時(shí)刻發(fā)生劇變時(shí)，傳統(tǒng)的偽貝葉斯控制算法(pseudo Bayesian control algorithms,PBCA)存在調(diào)節(jié)時(shí)間較長(zhǎng)的問(wèn)題，提出分階快速自適應(yīng)偽貝葉斯控制算法(ranked fast adaptive PBCA,RFA-PBCA)，首先設(shè)置一個(gè)門(mén)限值nth把信道的競(jìng)爭(zhēng)情況分成高強(qiáng)度和低強(qiáng)度2種類(lèi)型，再利用游程技術(shù)將信道分成空閑(沖突)和非空閑(非沖突)2種狀態(tài)。當(dāng)信道檢測(cè)到c(c=6)個(gè)空閑時(shí)隙時(shí)，若估計(jì)節(jié)點(diǎn)數(shù)n大于nth，則節(jié)點(diǎn)將其傳輸數(shù)據(jù)概率增大為原先的2倍；同理，當(dāng)信道檢測(cè)c(c=6)個(gè)沖突時(shí)隙后，將其傳輸數(shù)據(jù)概率設(shè)為原先的1/2，其他情況下則采用PBCA進(jìn)行調(diào)整。仿真結(jié)果表明，RFA-PBCA能夠很好適應(yīng)系統(tǒng)節(jié)點(diǎn)急劇變化的應(yīng)用場(chǎng)景，其性能明顯優(yōu)于傳統(tǒng)的PBCA。

關(guān)鍵詞：時(shí)隙ALOHA;游程; 分階快速自適應(yīng); 偽貝斯控制算法

0引言

時(shí)隙ALOHA及其改進(jìn)協(xié)議[1]由于其簡(jiǎn)單性已經(jīng)廣泛應(yīng)用于衛(wèi)星通信，GSM數(shù)字蜂窩網(wǎng)絡(luò)及標(biāo)簽識(shí)別[2]、認(rèn)知無(wú)線網(wǎng)絡(luò)[3-4]、車(chē)載網(wǎng)絡(luò)[5]及水下傳感網(wǎng)絡(luò)等延時(shí)較長(zhǎng)的環(huán)境下[6]。然而，時(shí)隙ALOHA本質(zhì)上是不穩(wěn)定的，文獻(xiàn)[7]研究了有限用戶時(shí)隙ALOHA系統(tǒng)的穩(wěn)定范圍。為解決時(shí)隙ALOHA的不穩(wěn)定性，Rivest[8]提出的偽貝葉斯控制算法(pseudo Bayesian control algorithms,PBCA)依據(jù)信道的前一狀態(tài)來(lái)修正系統(tǒng)的估計(jì)節(jié)點(diǎn)，更新節(jié)點(diǎn)的傳輸概率來(lái)實(shí)現(xiàn)系統(tǒng)的穩(wěn)定性控制。文獻(xiàn)[9]提出了在不同總體輸入負(fù)載情況下采用不同的重傳概率Pr的方式來(lái)獲得系統(tǒng)的穩(wěn)定性。Sarker研究了在控制新包生成率、允許某種程度的拒絕率及傳輸信道存在錯(cuò)誤概率等多種環(huán)境下，有限次重傳機(jī)制對(duì)系統(tǒng)穩(wěn)定性的影響[10-12]。文獻(xiàn)[13-16]依據(jù)系統(tǒng)的連續(xù)狀態(tài)和節(jié)點(diǎn)間協(xié)作分析了系統(tǒng)性能，并將博弈理論引入到信道競(jìng)爭(zhēng)中，并以此研究了時(shí)隙ALOHA系統(tǒng)的信道利用率和吞吐量。然而，這些穩(wěn)定控制算法均是通過(guò)對(duì)系統(tǒng)中實(shí)際通信節(jié)點(diǎn)的準(zhǔn)確估計(jì)，并調(diào)整各節(jié)點(diǎn)的數(shù)據(jù)發(fā)送概率從而實(shí)現(xiàn)系統(tǒng)穩(wěn)定性的目的。

當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)發(fā)生急劇變化時(shí)，信道將出現(xiàn)大量空閑或沖突時(shí)隙，造成信道利用率非常低。研究表明，當(dāng)估計(jì)節(jié)點(diǎn)數(shù)與實(shí)際節(jié)點(diǎn)數(shù)之比大于2或小于0.5時(shí)，系統(tǒng)吞吐量低于最大理論吞吐量的50%。因此，若能采用某種控制算法將估計(jì)節(jié)點(diǎn)數(shù)同系統(tǒng)實(shí)際節(jié)點(diǎn)數(shù)之比調(diào)整到0.5—2，然后再采用精細(xì)調(diào)整算法，必能提高系統(tǒng)的整體吞吐量。本文基于通用的時(shí)隙ALOHA系統(tǒng)，借鑒Wang等在文獻(xiàn)[17-18]中提出的檢測(cè)固定大小的空閑時(shí)隙進(jìn)行指數(shù)方式調(diào)節(jié)回退時(shí)間的原理，引入信道狀態(tài)游程，采用“二分法”模型[19]得出信道狀態(tài)的游程長(zhǎng)度k的差分方程，并估計(jì)出信道狀態(tài)的發(fā)生概率，從而估計(jì)出系統(tǒng)中的節(jié)點(diǎn)與估計(jì)節(jié)點(diǎn)數(shù)的差異。本文首先依據(jù)系統(tǒng)當(dāng)前的估計(jì)節(jié)點(diǎn)數(shù)將信道競(jìng)爭(zhēng)情況分成高負(fù)載和低負(fù)載2個(gè)等級(jí)，再依據(jù)信道狀態(tài)的游程信息進(jìn)行快速自適應(yīng)調(diào)整，并將該算法與PBCA相結(jié)合，提出了分級(jí)快速自適應(yīng)偽貝葉斯控制算法(ranked fast adaptive pseudo-bayesian control algorithm, RFA-PBCA)。最后利用MATLAB對(duì)該算法進(jìn)行了仿真測(cè)試。

1偽貝葉斯控制算法

有限網(wǎng)絡(luò)節(jié)點(diǎn)的系統(tǒng)，采用時(shí)隙ALOHA方式共享無(wú)線信道。時(shí)間軸被分成大小相同的時(shí)隙，時(shí)隙長(zhǎng)度為發(fā)送一個(gè)數(shù)據(jù)幀所需的時(shí)間，每個(gè)節(jié)點(diǎn)只能在時(shí)隙開(kāi)始時(shí)才允許發(fā)送數(shù)據(jù)。當(dāng)2個(gè)及以上節(jié)點(diǎn)同時(shí)發(fā)送數(shù)據(jù)時(shí)，將產(chǎn)生沖突。發(fā)生沖突的節(jié)點(diǎn)在后續(xù)時(shí)隙重傳產(chǎn)生沖突的數(shù)據(jù)包。因此，信道在任意時(shí)隙包含3種狀態(tài):空閑、成功及沖突，分別用{0,1,c}來(lái)表示。我們假定接收者在一個(gè)時(shí)隙成功接收一個(gè)數(shù)據(jù)包后，并在時(shí)隙結(jié)束時(shí)立即向所有用戶反饋數(shù)據(jù)包傳輸結(jié)果。時(shí)隙ALOHA的基本原理如圖1所示。

圖1　時(shí)隙ALOHA系統(tǒng)原理圖Fig.1　System principle diagram of slotted Aloha

采用時(shí)隙ALOHA作為MAC協(xié)議系統(tǒng)，有數(shù)據(jù)到達(dá)的節(jié)點(diǎn)是均值為m的泊松分布隨機(jī)變量。假定在第i個(gè)時(shí)隙，信道有k個(gè)節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，其概率為

(1)

當(dāng)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)以概率p=1/m進(jìn)行發(fā)送時(shí)，則該時(shí)隙空閑的概率為

(2)

在第i個(gè)時(shí)隙空閑情況時(shí)，系統(tǒng)中還有k個(gè)終端等待發(fā)送的概率為

(3)

其概率是一個(gè)均值為m-1的泊松分布。

同理，當(dāng)前有k個(gè)終端需要發(fā)送數(shù)據(jù)，成功傳輸?shù)母怕蕿?/p>

(4)

當(dāng)在時(shí)隙i中成功傳輸一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)時(shí)，系統(tǒng)中有k+1個(gè)分組的概率為

P(mi=k+1|succ)=

(5)

可見(jiàn)系統(tǒng)中等待傳輸?shù)姆纸M數(shù)k是一個(gè)均值為m-1的泊松分布隨機(jī)變量?？紤]到系統(tǒng)在一個(gè)時(shí)隙內(nèi)新到達(dá)的請(qǐng)求數(shù)為λ(≤0.368)，給定一個(gè)與mi(mi≥1)相關(guān)的先驗(yàn)概率p=1/mi，當(dāng)時(shí)隙空閑或成功后，mi+1是一個(gè)均值為mi+λ-1的泊松分布隨機(jī)變量。若發(fā)生沖突，mi+1可近似為一個(gè)均值為mi+λ+1/(e-2)的泊松分布隨機(jī)變量。因此，可根據(jù)當(dāng)前時(shí)隙的狀態(tài)進(jìn)行下一時(shí)隙發(fā)送概率的調(diào)整，該算法稱(chēng)為偽貝葉斯算法(pseudo-bayesian control algorithm, PBCA)，其算法實(shí)現(xiàn)步驟如下：

1)假定在時(shí)隙i，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)以概率P(mi)=min{1,1/mi}發(fā)送數(shù)據(jù)分組；

2)在i+1時(shí)隙的需要發(fā)送數(shù)據(jù)分組的終端數(shù)可以用(6)式進(jìn)行估計(jì)。

(6)

3)下一時(shí)隙各終端以1/mi+1的概率發(fā)送請(qǐng)求分組。

在MATLAB平臺(tái)下對(duì)PBCA進(jìn)行仿真，假定系統(tǒng)在第30個(gè)時(shí)隙時(shí)刻系統(tǒng)處于穩(wěn)定狀態(tài)，在第30個(gè)時(shí)隙時(shí)刻節(jié)點(diǎn)數(shù)發(fā)生突變，PBCA調(diào)整過(guò)程中的系統(tǒng)吞吐量如圖2所示。其中圖2a為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)(N=10,20,50)突變?yōu)?00時(shí)PBCA的調(diào)整過(guò)程的系統(tǒng)吞吐量。圖2b為系統(tǒng)節(jié)點(diǎn)數(shù)(N為50, 100, 200)突變?yōu)?時(shí)，PBCA調(diào)整過(guò)程中的系統(tǒng)吞吐量。圖2中的吞吐量是指在500個(gè)時(shí)隙時(shí)間內(nèi)，成功完成數(shù)據(jù)傳輸?shù)臅r(shí)隙數(shù)所占的比例，是一個(gè)歸一化值。從圖2中可以看出，經(jīng)過(guò)一段時(shí)間的調(diào)整，PBCA能夠保證系統(tǒng)獲得接近理論最大值的穩(wěn)定吞吐量。但是，當(dāng)節(jié)點(diǎn)數(shù)變化很大時(shí)，需要較長(zhǎng)的時(shí)間才能獲得理論最大值穩(wěn)定吞吐量。

圖2　PBCA調(diào)整過(guò)程中的平均吞吐量Fig.2　Throughput of PBCA in the adjusting

2S-ALOHA的信道狀態(tài)游程分布

定義1N節(jié)點(diǎn)的S-ALOHA系統(tǒng)中，信道連續(xù)出現(xiàn)某種狀態(tài)的長(zhǎng)度稱(chēng)為信道的狀態(tài)游程，連長(zhǎng)為x個(gè)某種信道狀態(tài)序列稱(chēng)信道狀態(tài)游程為x。

使用二分法模型將信道狀態(tài)分成空閑(或沖突)狀態(tài)E和非空閑(非沖突)狀態(tài)E′，并設(shè)E發(fā)生的概率為p。用t(t=1,2,…)表示時(shí)隙數(shù)，用s(t)表示在一個(gè)更新窗口內(nèi)從t時(shí)隙開(kāi)始的信道游程狀態(tài)，假定各時(shí)隙信道狀態(tài)獨(dú)立，則s(t)為一維Markov鏈。依據(jù)游程的定義，游程k≥1，為了描述信道狀態(tài)的轉(zhuǎn)移過(guò)程，增加狀態(tài)0，得到時(shí)隙ALOHA系統(tǒng)的信道狀態(tài)E的游程狀態(tài)轉(zhuǎn)移如圖3所示。

圖3　時(shí)隙ALOHA信道狀態(tài)E的游程Markov模型Fig.3　Markov model of run of channel state E of S-ALOHA

s(t)的狀態(tài)轉(zhuǎn)移概率為

(7)

2.1信道狀態(tài)游程的差分方程

為研究S-ALOHA系統(tǒng)在不同節(jié)點(diǎn)和傳輸概率下信道狀態(tài)的游程分布，先以樣本取值元素個(gè)數(shù)為H(H≥2)，各樣本值依均勻分布(P=1/H)的隨機(jī)試驗(yàn)X為參考模型，分析某一狀態(tài)E(假定為X=1)的游程分布情況。

用k表示X=1游程的長(zhǎng)度；用z(n)表示進(jìn)行n次投幣試驗(yàn)可能得到的互不重復(fù)的樣本總個(gè)數(shù)；用x(n)表示樣本中全部元素的個(gè)數(shù)；用G(n,k)表示連續(xù)進(jìn)行n次試驗(yàn)形成的全部樣本中游程恰好為k的游程總數(shù)。在MATLAB平臺(tái)下編程實(shí)現(xiàn)n次投幣試驗(yàn)的完備樣本空間，并統(tǒng)計(jì)出不同n情況下G(n,k)的值。表1為H=2時(shí)，G(n,k)的統(tǒng)計(jì)值。令ξ=n-k，用G(ξ)表示所有樣本空間中游程為k樣本個(gè)數(shù)。

表1　H=2時(shí)，G(n,k)統(tǒng)計(jì)表

從表1可以看出，G(ξ)取值滿足

1)當(dāng)k=n(即ξ=0)時(shí)，G(0)=1；

2)當(dāng)k=n-1(即ξ=1)時(shí)，G(1)=2(H-1)；

3)當(dāng)k≤n-2時(shí)，G(ξ)滿足如下差分方程

(8)

另外，利用MATLAB程序獲得H=3～9時(shí)G(n,k)的統(tǒng)計(jì)值，其結(jié)果仍然滿足以上3點(diǎn)。求解(8)式的差分方程，并代入初始值G(1)，G(2)得

(9)

用k替換變量ξ，用RL(k)表示n次試驗(yàn)中游程為k的可能出現(xiàn)次數(shù)，則

RL(k)=

(10)

將p=1/H代入(7)式，化簡(jiǎn)得

RL(k)=

(11)

在n次獨(dú)立試驗(yàn)，每次試驗(yàn)可取值H種，樣本總數(shù)z(n)=Hn=p-n，則平均每個(gè)樣本中長(zhǎng)度為k的游程個(gè)數(shù)為

g(k)=

(12)

另外，若將(6)式中的ξ用n-k進(jìn)行替換，兩端同除以Hn，則平均每個(gè)樣本長(zhǎng)度為k的游程個(gè)數(shù)g(k)(稱(chēng)g(k)為某狀態(tài)的長(zhǎng)度k游程的頻次)的差分方程為

g(k)-2pg(k+1)+p2g(k+2)=0

(13)

求解(13)式并代入初始條件，即可得出(11)式。

采用組合方法獲得的關(guān)于某事件狀態(tài)游程的差分方程中，各事件個(gè)數(shù)為整數(shù)且依均勻分布出現(xiàn)，即事件元素取值H≥2，相應(yīng)概率p=1/H≤0.5。但在時(shí)隙ALOHA系統(tǒng)中，信道狀態(tài)雖然為空閑、成功傳輸及沖突3種情況，但其分布卻不是等概率的。

采用“二分法”模型將概率空間劃分為[0,p]和[p,1]2個(gè)部分，在MATLAB中運(yùn)用蒙特卡洛方法模擬該隨機(jī)試驗(yàn)，然后統(tǒng)計(jì)每個(gè)樣本中游程為k的頻次g′(k)，并與(11)式得到的結(jié)論進(jìn)行比較。模擬環(huán)境參數(shù)設(shè)置如下：樣本容量n=100，樣本個(gè)數(shù)(模擬次數(shù))m=100 000。并將其與(12)式進(jìn)行比較，其結(jié)果如圖4所示。

圖4的比較結(jié)果表明，當(dāng)樣本量很大時(shí)，模擬結(jié)果非常接近由(12)式得到的理論結(jié)果，表明g(k)與g′(k)滿足同一個(gè)差分方程(13)式。由此可以得出，若某事件E發(fā)生的概率為p，其互斥事件E′發(fā)生的概率為1-p。在n次獨(dú)立試驗(yàn)中平均每個(gè)樣本中長(zhǎng)度為k的游程個(gè)數(shù)滿足差分方程(13)式。

圖4　PBCA調(diào)整過(guò)程中的平均吞吐量Fig.4　Throughput of PBCA in the adjusting

2.2信道狀態(tài)游程的概率分布

定義每個(gè)樣本中狀態(tài)E的長(zhǎng)度為k的游程期望次數(shù)與該狀態(tài)各種游程總的期望次數(shù)頻次之比為長(zhǎng)度為k某狀態(tài)游程的概率密度函數(shù)f(k)，即

(14)

而

(15)

代入(14)式，得

f(k)=

(16)

當(dāng)n→∞時(shí)，

(17)

(17)式表明當(dāng)n較大時(shí)，信道某種狀態(tài)的長(zhǎng)度為k的游程分布可近似為幾何分布隨機(jī)變量。在n個(gè)時(shí)隙的數(shù)據(jù)傳輸所構(gòu)形成的樣本中，用變量R表示信道某種狀態(tài)E的游程，長(zhǎng)度不小于k的游程的概率分布為

(18)

當(dāng)n→∞時(shí)，k?n時(shí)，

(19)

定理1在時(shí)隙ALOHA系統(tǒng)中，將信道劃分為空閑狀態(tài)E(概率為p)和非空閑狀態(tài)E′。在一個(gè)經(jīng)過(guò)n(n>6)個(gè)時(shí)隙的傳輸后，若檢測(cè)到信道空閑狀態(tài)長(zhǎng)度為6的游程序列，則在0.90的單側(cè)置信區(qū)間認(rèn)為p≥exp(-0.5)≈0.61，且系統(tǒng)的實(shí)際節(jié)點(diǎn)數(shù)小于估計(jì)節(jié)點(diǎn)數(shù)的1/2。

證明用變量R表示信道空閑狀態(tài)E的游程，P[R

(20)

由(17)式可知，要滿足P[R

F(k)=P[R≥k]<1-0.90=0.10

(21)

當(dāng)n較大時(shí)，將p=exp(-0.5)≈0.61代入(19)式，(23)式的不等式變換為

-0.5(k-1)≤ln0.10

(k-1)≥-2ln0.05≈2*2.3≈5?k≥6

(22)

由(19)式易知，F(xiàn)(k)是p∈[0,1]單調(diào)遞增函數(shù)，(22)式表明，當(dāng)p

由(1)式，p=Pidle=exp(-N/M)≥exp(-0.5)時(shí)，

N/M≤0.5?N≤M/2

(23)

定理1得證。

3分級(jí)自適應(yīng)快速控制算法

3.1分級(jí)算法快速自適應(yīng)算法設(shè)計(jì)

前一節(jié)定理表明，若系統(tǒng)連續(xù)檢測(cè)到7個(gè)空閑狀態(tài)(長(zhǎng)度為7的信道空閑狀態(tài)游程)，在0.95的單側(cè)置信區(qū)間認(rèn)為信道空閑概率Pidle≥0.61，系統(tǒng)實(shí)際節(jié)點(diǎn)數(shù)小于當(dāng)前窗口估計(jì)節(jié)點(diǎn)的0.5并將估計(jì)節(jié)點(diǎn)數(shù)M更新為原先的1/2(即M=M/2)，同時(shí)節(jié)點(diǎn)使用新的概率P=1/M進(jìn)行數(shù)據(jù)傳輸。同理，將信道狀態(tài)分成沖突與非沖突2種狀態(tài)，由(1)式，當(dāng)系統(tǒng)的實(shí)際節(jié)點(diǎn)數(shù)N為估計(jì)節(jié)點(diǎn)數(shù)的2倍時(shí)，信道沖突的概率Pcoll≈0.6。且β=N/M越大，Pcoll越大。當(dāng)系統(tǒng)檢測(cè)長(zhǎng)度為6的沖突狀態(tài)游程時(shí)，在單側(cè)0.90的置信區(qū)間亦可認(rèn)為實(shí)際節(jié)點(diǎn)數(shù)N大于估計(jì)節(jié)點(diǎn)數(shù)M的2倍，控制算法即可調(diào)節(jié)節(jié)點(diǎn)的發(fā)送概率為原先的1/2。

然而，由PBCA算法中的(6)式可知，當(dāng)系統(tǒng)檢測(cè)到成功傳輸或信道空閑時(shí)，其調(diào)整步長(zhǎng)為λ-1，而信道沖突后的調(diào)整步長(zhǎng)為λ+1/(e-2)。λ作為新包生成率，應(yīng)該滿足λ≤0.368，在PBCA算法設(shè)計(jì)中，λ取系統(tǒng)最大理論吞吐量值0.368。假定系統(tǒng)估計(jì)節(jié)點(diǎn)數(shù)M小等于15時(shí)，系統(tǒng)實(shí)際節(jié)點(diǎn)數(shù)N小于M/3，各節(jié)點(diǎn)依據(jù)概率Pt=1/M進(jìn)行數(shù)據(jù)傳輸,信道空閑的概率為

0.72

(24)

假定系統(tǒng)檢測(cè)6個(gè)空閑時(shí)隙，并依據(jù)定理1將系統(tǒng)估計(jì)節(jié)點(diǎn)數(shù)調(diào)整為原先的一半。但實(shí)際上，由于每檢測(cè)到一次空閑后，系統(tǒng)的估計(jì)節(jié)點(diǎn)會(huì)減小0.632。經(jīng)過(guò)6次空閑后，系統(tǒng)估計(jì)節(jié)點(diǎn)已經(jīng)變?yōu)?0左右，若再進(jìn)行減半調(diào)整，估計(jì)節(jié)點(diǎn)數(shù)變?yōu)?，與系統(tǒng)實(shí)際節(jié)點(diǎn)數(shù)相近。若再采用乘性控制算法，則容易產(chǎn)生振蕩調(diào)整的過(guò)程，從而使信道吞吐量下降。針對(duì)該問(wèn)題，提出的分級(jí)快速自適應(yīng)控制算法做如下處理：依據(jù)估計(jì)節(jié)點(diǎn)數(shù)設(shè)置一個(gè)臨界值Nth，當(dāng)估計(jì)N

分級(jí)快速自適應(yīng)偽貝葉斯控制(RFA-PBCA) 算法實(shí)現(xiàn)步驟如下：

1) 在時(shí)隙v，假定系統(tǒng)中的節(jié)點(diǎn)數(shù)為Nv，每個(gè)節(jié)點(diǎn)以概率qr(Nv)=min{1,1/Nv}發(fā)送數(shù)據(jù)分組；

2)快速自適應(yīng)算法處理：若系統(tǒng)檢測(cè)到游程為6的空閑狀態(tài)時(shí)，且Nv>Nth將Nv+1=Nv/2；若系統(tǒng)檢測(cè)到游程為6的沖突狀態(tài)時(shí)，將Nv+1=2Nv；跳轉(zhuǎn)到4);

3)正常的偽貝葉斯算法處理：下一時(shí)隙的需發(fā)送數(shù)據(jù)組的節(jié)點(diǎn)數(shù)用(25)式進(jìn)行估計(jì)

(25)

(25)式中，λ為新包到達(dá)率。由于時(shí)隙ALOHA的最大吞吐量為0.368，因此，在以后的仿真分析中，λ取0.368

4)下一時(shí)隙各節(jié)點(diǎn)以1/Nv+1的概率發(fā)送請(qǐng)求分組。

3.2算法仿真與驗(yàn)證

系統(tǒng)吞吐量是評(píng)價(jià)網(wǎng)絡(luò)性能的重要指標(biāo)，在基于競(jìng)爭(zhēng)的MAC協(xié)議中，高的吞吐量也意味著低的時(shí)延。利用MATLAB工具對(duì)RFA-PBCA在穩(wěn)定性調(diào)節(jié)過(guò)程的吞吐量及調(diào)節(jié)時(shí)間進(jìn)行了仿真。仿真環(huán)境設(shè)置為：系統(tǒng)以時(shí)隙為單位進(jìn)行劃分，在起始時(shí)刻t0=0系統(tǒng)處于穩(wěn)定狀態(tài)，而在t=20節(jié)點(diǎn)數(shù)由m變化為n，仿真時(shí)間為200個(gè)時(shí)隙。

圖5及圖6是FA-PBCA與PBCA算法吞吐量性能比較圖。其中，圖5為系統(tǒng)初始節(jié)點(diǎn)數(shù)為較大值(m為80，200)劇變?yōu)檩^小值(2,5,10)環(huán)境下，系統(tǒng)調(diào)節(jié)過(guò)程中每個(gè)時(shí)間的平均吞吐量。圖5a、圖5b的仿真顯示，當(dāng)初始節(jié)點(diǎn)數(shù)越大，而變化后節(jié)點(diǎn)數(shù)越小，PBCA吞吐量越小，達(dá)到穩(wěn)定最大吞吐量所需的時(shí)間越長(zhǎng)。而RFA-PBCA能快速將系統(tǒng)吞吐量調(diào)節(jié)到穩(wěn)定最大吞吐量。當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)從較大的值變?yōu)楹苄〉闹禃r(shí)(如從200個(gè)節(jié)點(diǎn)突然變化為小于10個(gè)節(jié)點(diǎn)情況)，在PBCA控制算法下經(jīng)過(guò)近200個(gè)時(shí)隙的調(diào)整，系統(tǒng)的吞吐量也只能達(dá)到最大理論吞吐量的30%以下；而RFA-PBCA經(jīng)過(guò)約30個(gè)時(shí)隙的調(diào)整就能達(dá)到最大吞吐的90%左右。

圖5　m較大情況下RFA-PBCA與PBCA調(diào)節(jié)過(guò)程吞吐量Fig.5　Throughput of RFA-PBCA vs. PBCA as m is larger

圖6　m較小情況下RFA-PBCA與PBCA吞吐量Fig.6　Throughput of RFA-PBCA vs. PBCA as m is smaller

圖6為初始節(jié)點(diǎn)數(shù)較小(m為2,10)劇變?yōu)檩^大值(60,120,240)時(shí)系統(tǒng)RFA-PBCA與PBCA算法調(diào)節(jié)性能比較圖，從仿真結(jié)果可以看出RFA-PBCA能明顯提高系統(tǒng)的調(diào)節(jié)性能，加快調(diào)節(jié)速度。比較圖5與圖6可以看出,網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)從較大情況變?yōu)檩^小情況的調(diào)節(jié)時(shí)間大于網(wǎng)絡(luò)節(jié)點(diǎn)從較小值變?yōu)檩^大值的場(chǎng)景。

為測(cè)試RFA-PBCA、PBCA的在不同節(jié)點(diǎn)變化情況下系統(tǒng)平均吞吐量性能，基于MATLAB仿真平臺(tái)進(jìn)行了仿真測(cè)試，仿真時(shí)間為200個(gè)時(shí)隙。得到各種場(chǎng)景下系統(tǒng)的平均吞吐量如圖7所示。圖7a、圖7b為系統(tǒng)初始節(jié)點(diǎn)數(shù)較小情況下(m分別為2，10)在某一時(shí)隙節(jié)點(diǎn)數(shù)發(fā)生變化后，經(jīng)過(guò)200個(gè)時(shí)隙得出的平均吞吐量。仿真結(jié)果表明，RFA-PBCA即使要系統(tǒng)節(jié)點(diǎn)增加到其15倍以上，也可以保證信道獲得0.32的利用率，接近最大吞吐量的90%。圖7c、圖7d為系統(tǒng)初始節(jié)點(diǎn)數(shù)較大情況下(m分別為200、300)在某一時(shí)隙節(jié)點(diǎn)數(shù)發(fā)生變化后，經(jīng)過(guò)200個(gè)時(shí)隙得出的平均吞吐量。從圖7可以看出，即使節(jié)點(diǎn)數(shù)變?yōu)楹苄〉闹担琑FA-PBCA可以在200時(shí)隙內(nèi)的平均吞吐量大于0.32，大于時(shí)隙ALOHA系統(tǒng)的最大吞吐量0.368的90%，而采用傳統(tǒng)的PBCA時(shí)，當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)從比較大的值(大等于200)突變?yōu)橐粋€(gè)很小的值時(shí)(如小于15)，經(jīng)過(guò)200個(gè)時(shí)隙后，得到的平均吞吐量仍低于0.1。

4結(jié)束語(yǔ)

當(dāng)時(shí)隙ALOHA系統(tǒng)中的節(jié)點(diǎn)數(shù)在某時(shí)刻發(fā)生劇變時(shí)，傳統(tǒng)的PBCA需要較長(zhǎng)的時(shí)間才能達(dá)到穩(wěn)定的接近最大理論值的吞吐量。分級(jí)快速自適應(yīng)控制算法(FA)將信道狀態(tài)分成空閑狀態(tài)和非空閑狀態(tài)，并依據(jù)系統(tǒng)當(dāng)前的估計(jì)值設(shè)置了一個(gè)門(mén)限值nth(本算法中nth=15)。當(dāng)信道檢測(cè)到6個(gè)空閑時(shí)隙時(shí)，在0.90置信區(qū)間認(rèn)為實(shí)際節(jié)點(diǎn)數(shù)為估計(jì)節(jié)點(diǎn)數(shù)的1/2，若當(dāng)前估計(jì)節(jié)點(diǎn)m>nth，則將估計(jì)節(jié)點(diǎn)數(shù)M調(diào)整為M/2，若當(dāng)前估計(jì)節(jié)點(diǎn)m

圖7　RFA-PBCA與PBCA平均吞吐量Fig.7　Average Throughput of RFA-PBCA vs. PBCA

參考文獻(xiàn)：

[1]MA R T B, MISRA V, RUBENSTEIN D. An Analysis of Generalized Slotted-Aloha Protocols[J]. IEEE/ACM Transactions on Networking, 2009, 17(3): 936-949.

[2]WU Haifeng, ZENG Yu, FENG Jihua, et al. Binary tree slotted ALOHA for passive RFID tag anticollision[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(1): 19-31.

[3]YUN Hanbae.Analysis of Optimal Random Access for Broadcasting with Deadline in Cognitive Radio Networks[J].IEEE Communications Letters.2013,17(3):573-575.

[4]WU Juanmei, WANG Yichen, DENG Jianguo. Performance of a Cognitive p-persistent Slotted Aloha Protocol[C]//Proc. 2015 IEEE International Conference on Communication Workshop. UK, London:IEEE press,2015: 405-410.

[5]CHENG Nan, ZHANG Ning, LU Ning, et al. Opportunistic Spectrum Access for CR-VANETs: A Game Theoretic Approach[J]. IEEE Transactions on Vehicular Technology, 2013, 63(1): 237-251.

[6]PU Lina, LUO Yu, ZHU Yibo, et al. Impact of real modem characteristics on practical underwater MAC design[C]// Proc. 2012 OCEANS. korea ,Yeosu:IEEE press,2012:1-6.

[7]HUI Hungka,YUE Onching,WING Cheong lau.FRASA:Feedback Retransmission Approximation for the Stability Region of Finite-User Slotted ALOHA[J].IEEE Transactions on Information Theory,2013,59(1):384-396.

[8]RIVEST R L. Network Control by Bayesian Broadcast[J]. IEEE Transactions on Information Theory, 1987, 33(3): 323-328.

[9]LOREN P C. Control procedures for slotted Aloha systems that achieve stability [J]. ACM SIGCOMM Computer Communication Review, 1986, 16(3): 302-309.

[10] SARKER J H. Auto-controlled algorithm for slotted ALOHA[J]. IEE Proceedings Communications, 2003, 150(1): 53-58.

[11] SARKER J H, MOUFTAH H T. A Retransmission Cut-Off Random Access Protocol with Multi-packet Reception Capability for Wireless Networks[C]//Proc. 3rd International Conference on Sensor Technologies and Applications. Athens,Greece: IEEE press.2009:217-222.

[12] SARKER J H. Stable and unstable operating regions of slotted ALOHA with number of retransmission attempts and number of power levels[J]. IEE Proceedings Communications, 2006, 153(3): 355-364.

[13] YOUNGMI J, KESIDIS G, JU W J. A Channel Aware MAC Protocol in an ALOHA Network with Selfish Users[J]. IEEE Journal on Selected Areas in Communications,2012, 30(1): 128-137.

[14] BARCELO J, INALTEKIN H, BELLALTA B. Obey or Play: Asymptotic Equivalence of Slotted Aloha with a Game Theoretic Contention Model[J]. Communications Letters, IEEE, 2011, 15(6): 623-625.

[15] JEON W S, JEONG D G. Combined Channel Access and Sensing in Cognitive Radio Slotted-ALOHA Networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(5): 2128-2133.

[16] LYU J, CHEW Y H, WONG W C. Aloha Games with Spatial Reuse[J]. IEEE Transactions on Wireless Communications, 2013, 12(8): 3932-3941.

[17] WANG Chonggang, LI Bo, LI lemin. A new collision resolution mechanism to enhance the performance of IEEE 802.11 dcf[J].IEEE Transactions On Vehicular Technology, 2004, 53(4):1235-1246.

[18] WU Huasen, ZHU Chenxi, LA R J. FASA: Accelerated S-ALOHA Using Access History for Event-Driven M2M Communications[J]. IEEE/ACM Transactions on Networking, 2013, 99(2): 1-14.

[19] 馬秀峰.隨機(jī)序列輪長(zhǎng)與輪次的統(tǒng)計(jì)規(guī)則[J].水科學(xué)進(jìn)展,1994, 5(2):95-100.

MA Xiufeng. Run and Run-Length Characteristics of Stochastic Sequences[J]. Advance in Water Science, 1994, 5(2):95-100.

[20] FANG Fei, MAO Yuming, LENG Supeng. An adaptive Slotted ALOHA Algorithm[J]. Przeglad elektrotechniczny(Electrical Review), 2012, 88(5b): 17-21.

Ranked adaptive pseudo bayesian control algorithm for slotted ALOHA

FANG Fei1,2，YU Wenchun1

(1. Engineering and Technology College of NeiJiang Normal University, NeiJiang 641110, P. R. China；2. School of Communication and Information Engineering, University of Electronic Science and Technology of China,Chengdu 611731, P. R. China)

Abstract:The control algorithm is necessary for slotted ALOHA in order to achieve the stable system throughput. The essentiality of control algorithm is to derive the acute number of system nodes. The classic control algorithm suffers performance loss when the system nodes sharply changes. In this paper, a ranked fast adaptive pseudo Bayesian control algorithm (RFA-PBCA) was proposed to promote the performance of ALOHA. Firstly, a threshold valuenthis set up to divide the channel into two types of high intensity and low intensity. Then, the channels are grouped into two states, idle (or conflict) and not idle(or not conflict) by the technology of run. When 6 idle channels are detected and the number of estimated nodenis greater thannth, all nodes update their probability of transmitting data as 2 times. Similarly, if 6 collision slots are detected, the number of estimate nodes will be doubled and the probability of transmitting data is updated as 1/2 times. In other cases, the pseudo Bayesian control algorithms (PBCA) are adopted. The results of simulation show that can PFA-PBCA well adapt to the scenarios where node of system rapidly changes, its performance outperforms than pseudo-Bayesian control algorithms.

Keywords：slotted ALOHA; run; ranked fast adaptive; pseudo-bayesian control algorithm

DOI：10.3979/j.issn.1673-825X.2016.03.004

收稿日期：2015-12-22

修訂日期：2016-06-12通訊作者：方飛fangfei_nj@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61471102)；四川省教育廳重點(diǎn)項(xiàng)目資助(13ZA0005)

Foundation Items：The National Natural Science Foundation of China(61471102)；The Key Project of Sichuan Education Department(13ZA0005.)

中圖分類(lèi)號(hào)：TN929.5

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)03-0303-09

作者簡(jiǎn)介：

方飛(1974-)，男，四川南江人，副教授，博士。主要研究方向?yàn)閷拵o(wú)線局域網(wǎng)絡(luò)、物聯(lián)網(wǎng)。E-mail:fangfei_nj@163.com。

余文春(1974-)，男，四川廣元人，講師，碩士。主要研究方向?yàn)榫W(wǎng)絡(luò)數(shù)據(jù)庫(kù)，物聯(lián)網(wǎng)。E-mail: ywclmxx@163.com。

(編輯：張誠(chéng))