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

方　飛，余文春

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

?

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

方飛1,2，余文春1

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

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

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

0引言

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

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

1偽貝葉斯控制算法

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

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

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

(1)

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

(2)

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

(3)

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

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

(4)

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

P(mi=k+1|succ)=

(5)

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

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

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

(6)

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

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

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

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

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

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

圖3　時隙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é)點和傳輸概率下信道狀態(tài)的游程分布，先以樣本取值元素個數(shù)為H(H≥2)，各樣本值依均勻分布(P=1/H)的隨機試驗X為參考模型，分析某一狀態(tài)E(假定為X=1)的游程分布情況。

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

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

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

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

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

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

(8)

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

(9)

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

RL(k)=

(10)

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

RL(k)=

(11)

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

g(k)=

(12)

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

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

(13)

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

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

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

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

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

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

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

(14)

而

(15)

代入(14)式，得

f(k)=

(16)

當(dāng)n→∞時，

(17)

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

(18)

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

(19)

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

N/M≤0.5?N≤M/2

(23)

定理1得證。

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

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

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

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

0.72

(24)

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

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

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

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

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

(25)

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

4)下一時隙各節(jié)點以1/Nv+1的概率發(fā)送請求分組。

3.2算法仿真與驗證

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

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

圖5　m較大情況下RFA-PBCA與PBCA調(diào)節(jié)過程吞吐量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é)點數(shù)較小(m為2,10)劇變?yōu)檩^大值(60,120,240)時系統(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é)點數(shù)從較大情況變?yōu)檩^小情況的調(diào)節(jié)時間大于網(wǎng)絡(luò)節(jié)點從較小值變?yōu)檩^大值的場景。

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

4結(jié)束語

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

基金項目：國家自然科學(xué)基金(61471102)；四川省教育廳重點項目資助(13ZA0005)

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

中圖分類號：TN929.5

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

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

作者簡介：

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

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

(編輯：張誠)