WiMAX網絡中自相似呼叫接納控制算法研究

胡永東，吳國新，錢寧，張三峰

(1. 東南大學 計算機科學與工程學院，江蘇 南京 210096；2. 東南大學 計算機網絡和信息集成教育部重點實驗室，江蘇 南京 210096；3. 南京林業(yè)大學 信息科學技術學院，江蘇 南京 210037)

1 引言

在“無線+寬帶”的網絡發(fā)展趨勢下，各種新的無線技術不斷涌現。WiMAX作為一個新興的無線接入技術一出現就成為業(yè)界關注的熱點。與其他的無線技術相比，它具有高帶寬和提供服務質量保證等優(yōu)點。IEEE 802.16d/e[1,2]標準定義了 WiMAX系統(tǒng)中服務質量保證的框架，但并未詳細給出無線資源管理方面的算法，留給各設備廠商自行設計。呼叫接納控制作為一種預防性的流量控制手段是實現網絡服務質量保證的重要手段。因此，在WiMAX系統(tǒng)中設計一個高效合理的呼叫接納控制算法具有重大意義。

呼叫接納控制是在用戶服務質量保證和網絡資源利用率之間保持一個合理的平衡，新的呼叫能被接納的條件是在已存在用戶的服務質量能被繼續(xù)保證的情況下，新用戶的服務質量能得到滿足。呼叫接納控制的2個關鍵問題是對網絡業(yè)務流的建模和接納控制的決策策略，業(yè)務流的建模直接影響接納控制的決策策略。目前，已有研究WiMAX系統(tǒng)中的呼叫接納控制算法[3～10]中，都是用經典的泊松過程來描述網絡業(yè)務流，側重對接納控制的決策策略進行設計和優(yōu)化，而忽略了業(yè)務流模型對接納控制決策策略的重大影響。但是，泊松過程在大多數情況下不能很好地描述互聯(lián)網的流量行為，Leland[11]等在20世紀90年代初發(fā)表的論文中第一次明確提出了網絡流量中存在著自相似現象，Cristina[12]和Dedi[13]等分析和評估了WiMAX業(yè)務流具有自相似和長相關特性。如果仍然采用泊松過程描述WiMAX業(yè)務流來進行流量預測，那么會使得預測的業(yè)務流量與實際使用的帶寬有一定的差距。按這種經典模型預測得到的業(yè)務流量來分配網絡資源，會造成網絡資源的浪費，降低網絡資源利用率。

本文根據WiMAX網絡業(yè)務流自相似特性，提出利用M/Pareto模型來對WiMAX網絡中不同服務等級的網絡業(yè)務流進行建模，在此基礎上推導出網絡有效帶寬的計算公式，據此設計一個自相似的呼叫接納控制(SS-CAC)算法。分析和仿真結果表明，M/Pareto模型能更精確地描述網絡業(yè)務流特征，各種業(yè)務流通過統(tǒng)計復用的方式來共享網絡資源，這樣使得自相似呼叫接納控制算法能有效地節(jié)省帶寬，從而提高了網絡資源的利用率。本文的第2節(jié)介紹理論基礎和相關公式的推導過程，第3節(jié)對WiMAX網絡業(yè)務流進行建模，第4節(jié)詳細說明自相似接納控制算法思想及算法流程，第5節(jié)介紹了算法的仿真環(huán)境和仿真結果，并對仿真結果進行分析，第6節(jié)是結束語。

2 理論基礎分析

2.1 自相似過程

定義1 (連續(xù)自相似過程)如果隨機過程{X( t),t∈R+}滿足：

則稱{X( t)}是自相似的(self-similar)，表示為H-ss，其中表示有限維上的分布相等，稱H為Hurst參數或自相似參數。

定義2 (嚴格自相似(exactly self-similar)過程)如果歸一化后的{X( at)}任意有限維分布{a-HX( ati),i∈Z+}都與原來的隨機過程{X( tj),j∈Z+}相同，則稱{X( t)}為嚴格自相似過程。

定義3 (漸近自相似(asymptotically self-similar)過程)如果{a-HX( ati),i∈Z+}與{X( tj),j∈Z+}只是均值和方差相等，則稱{X( t)}為漸近自相似過程。

2.2 M/Pareto模型及其自相似性

M/Pareto[14]流由一些重合疊加的突發(fā)流組成。這些突發(fā)按照速率為λ的Poisson過程到達，每個突發(fā)的持續(xù)時間是一個隨機變量，符合衰減速率為α，位置參數為δ(δ為突發(fā)最短的持續(xù)時間)的Pareto分布。假設突發(fā)的持續(xù)時間為服從Pareto分布的隨機變量X，其互補分布函數可表示為

假設突發(fā)中的數據分組傳輸率為r，且所有突發(fā)傳輸數據分組的速率相同，則突發(fā)大小的期望為，在一個長度為t的時間間隔內所有突發(fā)傳輸的總數據分組數的期望為

雖然Pareto分布的方差是無窮大，但M/Pareto過程的方差是有窮的。方差函數的累次積分形式為

式(3)通過累次積分得到：

假設定義H=(3-α)/2，則有隨著t的增長，方差近似正比于t2H，即：

這意味著這個過程是一個漸近自相似的過程，其Hurst參數為

聚集流的平均速率為

由式(5)和式(7)聯(lián)立起來可以推導出：

2.3 自相似網絡模型FBM流量預測

首先定義帶有自相似參數H(0.5≤H＜1)標準化的分形布朗運動Z(t)。Z(t)是一個隨機過程，文獻[15]利用Z(t)給出了基于分形布朗運動的自相似業(yè)務流模型A(t)，定義如下：

其中，A(t)表示到時刻t為止到達業(yè)務流的總量，它由3個參數來刻畫：m、a、H。m＞0為平均傳輸速率，a＞0為方差系數，H是Z(t)的自相似參數(Hurst參數)。它們之間的關系為

其中，σ2為一個時間單元內的業(yè)務流量的方差。然后，定義分形布朗緩存過程X(t)是一個隨機過程，即：

其中，C為系統(tǒng)服務率(也就是鏈路容量)，A(t)為分形布朗運動業(yè)務流模型。利用分形布朗存儲過程X(t)，Norros推導出了與緩存容量相關的有效帶寬計算公式：

其中，κ(H)=HH(1-H)1-H，m是業(yè)務流的平均比特率(bit/s)，a是業(yè)務流的方差系數(bit-sec)，H是自相似的Hurst參數(0.5≤H＜1)，ε為分組丟失率，x為緩存容量(bit)。值得注意的是，這個公式的推導是基于2個前提：一是業(yè)務流具有高斯特性；二是緩存容量必須足夠大，詳細描述見文獻[16]。所以在應用時必須要保證這2個條件成立，否則就得不到預期效果。

從2.2節(jié)和2.3節(jié)的描述可知，M/Pareto過程的聚集累加流表現為分形高斯過程，而且這一結論與A(t)的屬性相一致，如果用這2個模型來描述同一個具有分形的聚集累加到達過程，則表現出同樣的統(tǒng)計特性和自相似特性，所以兩者的期望和方差對應相等，自相似參數H也相等。A(t)的方差為

則由式(8)和式(13)可以得到：

3 WiMAX系統(tǒng)中的業(yè)務流模型

3.1 業(yè)務流的建模思想

在文獻[17]中證明了M/Pareto模型可以看作是由大量獨立且具有重尾分布的ON/OFF模型復合而成的。ON/OFF模型可以方便地描述具有以下特征的真實的網絡業(yè)務流。

1) 單個業(yè)務源產生包含隨機個數據分組的突發(fā)，突發(fā)長度的分布是重尾的，衰減服從Pareto分布，在突發(fā)產生完成后，保持一個隨機時間的靜默期。

基于以上述評，本文希望在以下方面尋求拓展：第一，在已有的文本分析及效果評價研究之間，探索針對政策文本的效力評估，以建立政策文本與政策效果間的對話機制。第二，在現有國家層面上、宏觀和中觀政策領域研究基礎上，著力進行地方層面上、機動車污染防治這一具體政策的效力評估，這也與機動車污染防治及其政策的地方性特征有關。第三，與已有截面數據為主的研究相比，文本選取2013-2017年機動車污染防治政策進行歷時性分析，并進一步考察機動車污染防治政策歷時性變化軌跡背后的情境因素。

2) 單個業(yè)務源的數目N足夠大，可以看作是無窮大，但數據源的到達率λ則是一個有限值。

3) 業(yè)務源中業(yè)務流的聚合流是一個漸近自相似過程，Hurst參數H(0.5≤H＜1)。

如前所述，由于WiMAX業(yè)務流具有自相似和長相關的特性，網絡中的單個業(yè)務流基本符合以上特征，所以采用這樣的ON/OFF模型來對該系統(tǒng)單個業(yè)務流源進行建模，并根據每種類型業(yè)務流的參數描述符 (峰值率PR，均值率SR)來確定相應參數。

3.2 業(yè)務流模型

根據IEEE802.16d/e標準，在WiMAX系統(tǒng)中，5種服務被支持：主動授權業(yè)務（UGS），實時輪詢業(yè)務（rtPS），擴展的實時輪詢業(yè)務（ertPS），非實時輪詢業(yè)務（nrtPS），盡力而為服務（BE）。

UGS支持定長分組和固定比特速率的實時業(yè)務流，在周期性的時間間隔內以固定速率發(fā)送分組數據。假設固定大小分組的數據傳輸率rUGS，則UGS業(yè)務流的峰值率PR1=rUGS，均值率SR1=rUGS。

rtPS支持變長分組、可變比特率的實時業(yè)務流。假設可變比特率的最大值為 rrtps-max，最小值為rrtps-min，則 rtPS業(yè)務流的峰值率 PR2=rrtps-max，均值率SR2=(rrtps-max+rrtps-min)/2。

nrtPS支持變長分組、可變比特率的非實時業(yè)務流。假設可變比特率的最大值為rnrtps-max，最小值為rnrtps-min，則nrtPS業(yè)務流的峰值率PR3=rnrtps-max，均值率SR3=(rnrtps-max+rnrtps-min)/2。

BE支持非實時無任何速率和時延抖動要求的分組業(yè)務流。由于此類型的業(yè)務流沒有速率要求，但系統(tǒng)每種業(yè)務流的最大傳輸率是有一定限制的，所以假設分組傳輸比特率最大值為 rbe-max，最小值為rbe-min=0，則BE業(yè)務流的峰值率PR4=rbe-max，均值率SR4=(rbe-max+rbe-min)/2。

ertPS支持變長分組、可變速率的實時業(yè)務流，但在帶寬的授權上像UGS，由802.16e增補。假設可變比特率的最大值為rertps-max，最小值為rertps-min，則 ertPS業(yè)務流的峰值率 PR5=rertps-max，均值率SR5=(rertps-max+rertps-min)/2。

3.3 聚合業(yè)務流ON/OFF模型

每種類型業(yè)務流的描述參數為{PRi，SRi}，根據流描述參數可以得到每種類型業(yè)務流source的活動率：

通過每種類型業(yè)務流的活動率，可以求得聚集業(yè)務流的平均速率：

其中，M表示業(yè)務流類型數；λi表示第i類型業(yè)務流的活動數， λi= ( Ni+ δij) ρi；Ni表示第i類型業(yè)務流正存在的連接數；PRi表示第i類型業(yè)務流的峰值率；δij表示新到達一個第j類型業(yè)務流，

4 自相似的呼叫接納控制(SS-CAC)算法

4.1 算法思想

通過收集系統(tǒng)中突發(fā)的持續(xù)時間數據，利用矩估計或極大似然估計的方法來確定 M/Pareto模型中Pareto分布參數α、δ，每個突發(fā)在ON期以最大速率PRi發(fā)送數據，每個時刻每種類型業(yè)務流連接數為 Ni，根據每個業(yè)務流的描述參數{PRi，SRi}可以計算出該類業(yè)務流在ON期的概率，再根據兩點分布的知識可以求得該類業(yè)務流的活動數λi，從而求出系統(tǒng)中聚集流的平均傳輸率m。

當一個新業(yè)務流j到達后，將該業(yè)務流的描述參數{PRj，SRj}以及相應參數值代入式(16)，可以計算出聚集流的平均傳輸率m，然后將已求出的m和相應的參數值代入式(14)得到方差系數a，這樣，利用 M/Pareto模型就確定出了分形布朗運動模型中的參數(m,a,H),然后根據分形布朗運動模型FBM中有效帶寬的計算式(12)就可以估算出聚集流所要求的帶寬 c，以此作為自相似呼叫接納控制算法(SS-CAC)的接納控制標準，如果c大于系統(tǒng)所配置的可用帶寬 C(即 c＞C)，則拒絕接納該流，否則接受該流。

4.2 算法實現

根據4.1節(jié)的設計思想，SS-CAC具體算法描述如下。

輸入：(PRj，SRj,，j)

j表示當前請求是第j類型的業(yè)務流，PRj表示該類業(yè)務流的峰值率，SRj表示該類業(yè)務流的均值率。

輸出：CAC決策

決策值為邏輯值，True表示接受該業(yè)務流請求，False表示拒絕該業(yè)務流請求。

SS-CAC(PRj，SRj，j)

begin

1) 通過輸入參數PRj，SRj和式(15)計算第j類型業(yè)務流的活動率ρj；

2) 根據現有的系統(tǒng)中的各類業(yè)務流數Ni，ρj，PRj和式(16)計算聚集流平均速率m；

3) 利用m、α、δ和式(14)計算業(yè)務流的方差系數a；

4) 將α代入式(6)計算自相似參數H；

5) 最后，使用計算得到的m,a,H值及式(12)計算聚集流的有效帶寬c；

6) 如果c＞C則不分配帶寬并返回 False，否則，分配相應帶寬并返回True；

end

說明：Pareto分布中的參數α、δ和ε(分組丟失率)、x(緩存容量)已經設置，C為系統(tǒng)中的可用帶寬。

5 算法仿真與分析

5.1 仿真參數設置

SS-CAC算法的仿真在NS2環(huán)境中來實現，利用MPareto ON/OFF來仿真業(yè)務源，也就是業(yè)務源的到達率為λ，每個業(yè)務源在ON期以峰值率發(fā)送數據，ON期時間服從Pareto分布，OFF期不發(fā)送數據，OFF期時間服從泊松分布，并且 ON期和OFF期交替。ON/OFF模型中的ON期和OFF期的平均時間設為500ms，ON期服從的Pareto分布的參數α=1.4，突發(fā)的發(fā)送速率為6.4kbit/s，每個分組的大小為200B，各種參數匯總如表1所示。

表1 ON/OFF模型參數設置

仿真網絡的拓撲結構如圖1所示。每個用戶站SSi向基站BS發(fā)送數據，基站BS接收并轉發(fā)。基站BS的帶寬為128kbit/s，緩存大小為1MB，分組丟失率為 0.001，為了研究的方便，在仿真系統(tǒng)中不考慮傳播延遲。

圖1 仿真網絡拓撲

SSi分別表示WiMAX中5種不同服務類型的業(yè)務源，為了簡化仿真過程，把這5種業(yè)務源分為2大類：一類是CBR，如UGS；另一類是VBR，如rtPS、ertPS、nrtPS、BE。CBR業(yè)務源的峰值率為6.4kbit/s，均值率為6.4kbit/s；VBR業(yè)務源的峰值率為6.4kbit/s，均值率為3.2kbit/s，如表2所示。

表2 業(yè)務流參數

5.2 仿真結果分析

5.2.1 WiMAX業(yè)務流的自相似性

Hurst參數是描述業(yè)務自相似和長相關的重要參數，若0.5≤H＜1，則序列具有長相關性，否則，序列不具備長相關性?，F有許多估計Hurst參數的方法，這些算法都能估計自相似序列的 H值，但在實際應用中，不同算法估計結果差異較大，這里選取聚類方差法(AV)、R/S法和留數回歸法(Res)來估計 WiMAX中業(yè)務流的自相似性Hurst參數。在仿真WiMAX業(yè)務流時設置泊松到達的到達率 λ=2、4、6、8、10時計算得到的 H值見表 3。計算仿真結果的平均值可以得到 H=0.785 4，這與理論值H=(3-1.4)/2=0.8基本吻合。從而也說明WiMAX業(yè)務流的確具有自相似性和長相關的特性。

表3 WiMAX業(yè)務流的Hurst參數值

5.2.2 帶寬利用率

在測量帶寬的利用率時，VBR業(yè)務流的到達率λ=5、10、15、20、25、30、35、40，CBR 業(yè)務流的到達率λ=0、2，同時，在仿真系統(tǒng)中采用SS-CAC算法和GCAC算法來進行呼叫接納控制，測得帶寬利用率的結果如圖2所示。當CBR業(yè)務流的到達率λ=0時，在VBR業(yè)務流的到達率λ=20之前，2種算法的利用率相同，在這之后，根據GCAC算法，系統(tǒng)不再接受新的呼叫，所以帶寬利用率不再增長，而根據SS-CAC算法系統(tǒng)帶寬還沒有分配完，所以繼續(xù)接受新的呼叫，帶寬利用率繼續(xù)提高，而且提高的幅度比較顯著，當 CBR業(yè)務流的到達率λ=2時也是如此。因此， SS-CAC算法在帶寬利用率上的優(yōu)勢比較明顯。由于 CBR業(yè)務流在系統(tǒng)中一直以恒比特率發(fā)送數據，所以在相同算法作用下，隨著 CBR業(yè)務流到達率的增大，帶寬利用率也會隨之增大。

圖2 帶寬利用率

5.2.3 呼叫阻塞率

在統(tǒng)計系統(tǒng)的呼叫阻塞率時，對VBR業(yè)務流和 CBR業(yè)務流的到達率設置同上，仍然采用SS-CAC算法和GCAC算法來進行呼叫接納控制，統(tǒng)計得到呼叫阻塞率的結果如圖3所示。從統(tǒng)計的結果可以看到，不管CBR業(yè)務流到達率λ=0還是2，SS-CAC算法比GCAC算法在呼叫阻塞率上有明顯降低。由于CBR業(yè)務流在系統(tǒng)中一直以恒比特率發(fā)送數據，所以在相同算法作用下，隨著CBR業(yè)務流到達率的增大，呼叫阻塞率也會隨之上升。

圖3 呼叫阻塞率

6 結束語

本文根據WiMAX網絡業(yè)務流具有自相似和長相關這一特性，提出了利用M/Pareto模型來對它進行建模，這樣可以比較精確地描述WiMAX網絡業(yè)務流。詳細分析和討論了 M/Pareto模型、MPareto ON/OFF模型和 FBM 業(yè)務流模型三者之間內在關系。以 M/Pareto模型作為橋梁，建立了 MPareto ON/OFF模型和FBM業(yè)務流模型參數映射關系，推導出了一個基于網絡業(yè)務流自相似特性的有效帶寬計算公式。在此基礎之上，設計出了一種自相似接納控制算法來改善網絡性能。仿真結果表明，使用有效帶寬計算公式估算的聚集流的帶寬與各個呼叫連接在各個時刻實際占用的網絡帶寬基本吻合，自相似接納控制算法減小了呼叫阻塞率，提高了系統(tǒng)的資源利用率和吞吐量。在此需要說明的是，文中的結論都是假設ON/OFF模型中的ON期時間服從同一Pareto分布，而實際的WiMAX網絡中5種業(yè)務流未必服從同一Pareto分布，這樣會對結論造成一定的影響，這部分待以后做進一步的研究和探討。

[1] IEEE 802.16d. IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access Systems[S]. 2004.

[2] IEEE 802.16e. IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum[S]. 2006.

[3] THEODORIDIS G , PAVLIDOU F N. A hybrid CAC algorithm for maximizing downlink capacity of M-WiMAX systems[J]. Wireless Networks, 2010,17(3): 1-16.

[4] CHANG B J, CHEN Y L. Adaptive hierarchical polling and Markov decision process based CAC for increasing network reward and reducing average delay in IEEE 802.16 WiMAX networks[J]. Computer Communications, 2008, 31(10): 2280-2292.

[5] THEODORIDIS G, PAVLIDOU F N. An SNR-based CAC algorithm for optimizing resource assignment in the downlink of M-WiMAX[A].IEEE Wireless Communications and Networking Conference[C].Sydney, Australia, 2010.1-6

[6] RONG B, QIAN Y, LU K J, et al. Call admission control optimization in WiMAX networks[J]. IEEE Transactions on Vehicular Technology,2008, 57(4): 2509-2522.

[7] LEE J Y , KIM K B. Statistical connection admission control for mobile WiMAX systems[A]. IEEE Wireless Communications and Networking Conference[C]. Las Vegas, USA, 2008. 2003-2008.

[8] CHAMMAKHI M I , DANIEL C, FETHI F. Scheduling and CAC in IEEE 802.16 fixed BWNs: a comprehensive survey and taxonomy[J].IEEE Communications Surveys and Tutorials, 2010, 12(4): 459-487.

[9] BORIN, FREITAG J, FONSECA D, et al. Uplink scheduler and admission control for the IEEE 802.16 standard[A]. GLOBECOM -IEEE Global Telecommunications Conference[C]. Honolulu, USA,2009, 1-6.

[10] LU J C , MA M D. A cross-layer elastic CAC and holistic opportunistic scheduling for QoS support in WiMAX[J]. Computer Networks,2010, 54(7): 1155-68.

[11] LELAND W E, TAQQU M S, WILLINGER W, et al. On the self-similar nature of ethernet traffic[J]. Computer Communications Review, 1993, 23(4): 203-213.

[12] CRISTINA S. Long-range dependence in WiMAX traffic a preliminary analysis[A].2010 9th International Symposium on Electronics and Telecommunications[C]. Tismisoara, Romania, 2010. 241-244.

[13] RAHMAWAN P D, KE K W, WU H T. Self-similar traffic assessment on QoS service classes of WiMAX network[A]. Proceedings of the 2009 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks[C]. 2009.1-6.

[14] ROBERTS J, MOCCI U, VIRTAMO J. Broadband Network Teletraffic[M]. Springer, 1996.

[15] ILKKA N. On the use of fractional Brownian motion in the theory of connectionless networks[J]. IEEE Journal on Selected Areas in Communications, 1995, 13(6):953-962.

[16] PATEL A, WILLIAMSON C. Effective bandwidth of self-Similar traffic sources: theoretical and simulation results[A]. Proceedings of the IASTED Conference on Applied Modeling and Simulation[C].Banff, England, 1997.298-302.

[17] LIKHANOV N, TSYBAKOV B, GEORGANAS N D. Analysis of an ATM buffer with self-similar (＂fractal＂)input traffic[A]. Proceedings IEEE INFOCOM[C]. BOSTON, MA, USA, 1995. 985-992.