基于M/G/1排隊模型的業(yè)務流性能研究

王軍祥 ，林柏鋼

(1.福建船政交通職業(yè)學院信息工程系，福建福州 350007；2.福州大學網(wǎng)絡系統(tǒng)信息安全福建省高校重點實驗室，福建福州 350108)

基于M/G/1排隊模型的業(yè)務流性能研究

王軍祥1，2，林柏鋼2

(1.福建船政交通職業(yè)學院信息工程系，福建福州 350007；2.福州大學網(wǎng)絡系統(tǒng)信息安全福建省高校重點實驗室，福建福州 350108)

針對無線傳感器網(wǎng)絡可能存在的擁塞問題，提出了一種新的業(yè)務流性能刻畫方法.利用M/G/1排隊模型建立了一步轉(zhuǎn)移概率矩陣，在先來先服務策略的基礎上推導了業(yè)務流的隊列長度和等待時間的數(shù)學表達式，通過仿真實驗分析了當服務源分別服從定長分布和k階Erlang分布時，系統(tǒng)的等待時間與服務率、到達率之間的關系.結果表明，等待時間與到達率成正相關，與服務率成負相關，并且對k階Erlang分布的影響更大.

無線傳感器網(wǎng)絡；M/G/1排隊模型；轉(zhuǎn)移概率矩陣；到達率

0 引 言

無線傳感器網(wǎng)絡(WirelessSensor Networks，WSN)節(jié)點間以無線自組織方式構成，且節(jié)點間通過無線電波進行通信.由于無線電波本身的特性，加上節(jié)點所處復雜多變的環(huán)境中各種干擾源的存在，使得節(jié)點間通信質(zhì)量受到嚴重影響，從而造成節(jié)點間通信的不穩(wěn)定.同時，當傳感器節(jié)點接收數(shù)據(jù)包的速率大于其轉(zhuǎn)發(fā)速率時，則需要對過剩的數(shù)據(jù)包進行緩存，而當緩存的數(shù)據(jù)包隊列滿時就會產(chǎn)生丟棄現(xiàn)象，引發(fā)無線傳感器網(wǎng)絡的擁塞，導致網(wǎng)絡吞吐量降低.因此，如何有效地提高業(yè)務流性能是無線傳感器網(wǎng)絡技術研究的一個重要方面.對此，科研人員做了大量的研究工作，并給出了相應的解決方案[1-13].在此基礎上，本研究利用M/G/1排隊模型對無線傳感器網(wǎng)絡的業(yè)務流性能進行了分析，推導了業(yè)務流的隊列長度、逗留時間和等待時間的表達式，并通過數(shù)學仿真深入分析了影響業(yè)務流性能的因素.

1 基于M/G/1排隊模型的業(yè)務流性能研究

1.1 業(yè)務流性能刻畫方法

假設存在一個無線傳感器網(wǎng)絡如見圖1所示，其中，S為服務節(jié)點，Noden為各子節(jié)點，Noden節(jié)點的業(yè)務流以概率p的Poisson分布到達.考慮到服務節(jié)點S會受到能量和帶寬的影響，其服務率 μ可能動態(tài)變化，并服從一般分布G(t)，則，同時，假設系統(tǒng)滿足M/G/1排隊模型，系統(tǒng)的容量無限，并采用先來先服務的策略，業(yè)務流到達時如果服務源空閑就立即服務，否則進行排隊等待.則，業(yè)務流性能刻畫的具體步驟為:

圖1 無線傳感器網(wǎng)絡仿真結構圖

①在開始時刻(t=0)，初始化無線傳感器網(wǎng)絡，設置緩沖區(qū)大小、鏈路帶寬、時延和數(shù)據(jù)包大小等相關參數(shù)；

②根據(jù)M/G/1排隊模型建立網(wǎng)絡的一步轉(zhuǎn)移概率矩陣；

③由服務源的閑期和忙期確定業(yè)務流隊長；

④計算穩(wěn)態(tài)下業(yè)務流的等待時間與逗留時間分布；

⑤根據(jù)服務時間的具體分布來刻畫業(yè)務流的相關性能；

⑥令t=t+1，跳轉(zhuǎn)到步驟 ②進行下一時刻業(yè)務流的性能刻畫，直到運行完成.

1.2 業(yè)務流性能研究

令Qt表示t時刻系統(tǒng)到達的業(yè)務流，rt表示第t個服務時間段θt到達的業(yè)務流數(shù)量，{Qt，t≥0}是一個不可約、非齊次MC，則一步轉(zhuǎn)移概率pk為，

其中，k≥0.

由于{rt，t≥0}是獨立同分布的，所以{Qt，t≥0}的一步轉(zhuǎn)移概率為:①當i=0時，

②當k≥i-1，且 i≥1時，

③當k＜i-1，且 i≥1時，

故，{Qt，t≥0}的一步轉(zhuǎn)移概率矩陣可表示為，

假設，P(y)為pk的母函數(shù)，當p/μ＜1時，{Qt，t≥0}是正常返的，存在，

其中，|y|≤1，且，

假設d表示業(yè)務流開始的系統(tǒng)忙期，其與分布D(t)之間滿足，

其中，t≥0.

故，忙期d中第一個服務時間θ1內(nèi)到達的業(yè)務流數(shù)量為，

后續(xù)業(yè)務流服務時間為θn(n=2，3，4，…)，且θn之間相互獨立.利用全概率公式可得其隊列長度L(t)的瞬時分布[18]為:

其中，j≥1.

由于隊列長度L(t)只與業(yè)務流數(shù)量有關，則:

結合θn的獨立同分布性，有，

假設，W(t)、U(t)分別代表穩(wěn)態(tài)下業(yè)務流的等待時間和逗留時間分布，并滿足，

那么，在該逗留時間U(t)內(nèi)到達的業(yè)務流個數(shù)[18]為，

由于逗留時間為等待時間與服務時間之和，故業(yè)務流等待時間為，

2 仿真實驗

仿真實驗針對服務時間為定長分布和k階Erlang分布下的業(yè)務流進行.根據(jù)式(18)有，

①當服務時間服從1/μ的定長分布時，其業(yè)務流等待時間W1可表示為，

②當服務時間服從kμ的k階Erlang分布時，其業(yè)務流等待時間W2可表示為，

在OPENT中建立如圖1所示的拓撲結構，緩沖區(qū)大小為1 000 packets，各鏈路帶寬為10 Mbps，延時為20 ms，數(shù)據(jù)包大小為500 Byte.根據(jù)式(19)、(20)得到2種分布下業(yè)務流的等待時間與服務率之間的關系如圖2所示.

圖2 等待時間與服務率之間的關系

從圖2可以看出，隨著服務率的增加，業(yè)務流的等待時間在整體趨勢上隨之減小直至平穩(wěn).但是當處于相同服務率下時，k階Erlang分布比定長分布下降的速度快，這說明k階Erlang分布下的業(yè)務流等待時間更短，意味著要獲得相同的等待時間，定長分布下所要求系統(tǒng)的服務率更高，此時采用 k階Erlang分布能夠獲得更好的性能.

圖3顯示了2種分布下業(yè)務流的等待時間與到達率之間的關系.

圖3 等待時間與到達率之間的關系

從圖3可知，隨著到達率的增加，業(yè)務流的等待時間也增加.這一點容易理解，到達率增加必然使單位時間內(nèi)聚集更多的業(yè)務流，當服務率處于穩(wěn)定值時，單位時間內(nèi)接受服務的業(yè)務流個數(shù)不變，因此排隊等待服務的業(yè)務流數(shù)量增加，從而導致業(yè)務流等待時間延長.另外，在相同到達率下，k階Erlang分布比定長分布等待時間的上升速度快，說明到達率的增加對k階Erlang分布的業(yè)務流性能影響更大.仿真實驗表明，無線傳感器網(wǎng)絡業(yè)務流性能與服務率、到達率存在較大關系，同時還受其他因素的影響.

3 結 論

針對無線傳感器網(wǎng)絡服務節(jié)點的動態(tài)變化，本研究提出了一種新的業(yè)務流性能的刻畫方法.該方法利用M/G/1排隊模型建立一步轉(zhuǎn)移概率矩陣，在此基礎上推導了業(yè)務流的隊列長度、逗留時間和等待時間的表達式，同時，針對定長分布和k階Erlang分布進行了數(shù)學仿真，結果表明該方法具有一定的可行性.后續(xù)的研究將考慮結合無線傳感器網(wǎng)絡的可靠性、故障檢測及容錯機制等因素，建立關鍵節(jié)點和鏈路的性能評價體系.

:

[1]Wang C，Li B ，Sohraby K，et al.Upstream Congestion Control in WirelessSensor Networks Through Cross-layer Optimization[J].IEEE Journal on Selected Areas in Communications，2007，25(4):786-795.

[2]Chen S，Yang N.Congestion Avoidance Based on Lightweight BufferManagement inSensor Networks[J].IEEETransactions on Parallel and Distributed Systems，2006，17(9):934-946.

[3]李國華，李建中，高宏.ε-近似和加權公平性保證的無線傳感器網(wǎng)絡擁塞控制算法[J].計算機學報，2011，34(11):2197-2210.

[4]Akan O B，Akyildiz I.Event-to-sink Reliable Transport in WirelessSensor Networks[J].IEEE/ACM Transaction on Networking，2005，13(5):1003-1016.

[5]Siqueira I G，Ruiz L B ，Loureiro A A F，et al.Coverage Area Management for Wireless Sensor Networks[J].International Journal of Network Management，2007 ，17(1):17-31.

[6]Bisnik M，Abouzeid A A，Isler A A.Stochastic Event Capture UJsing Mobile Sensors Subject to a Quality Metric[J].IEEE Trans on Robotics，2007，23(4):676-692.

[7]孫佩剛，趙海，羅玎玎，等.無線傳感器網(wǎng)絡鏈路通信質(zhì)量測量研究[J].通信學報，2007，28(10):14-22.

[8]Couto D S J，Aguayo D，ChambersB A，et al.Performance of Multihop Wireless Networks:Shortest Path is Not Enough[J].ACM SIGCOMM Computer Communication Review ，2003，33(1):83-88.

[9]舒堅，劉琳嵐，樊佑磊，等.無感知分組丟失下的無線傳感器網(wǎng)絡鏈路質(zhì)量評估模型[J].通信學報，2011，32(4):103-111.

[10]胡海峰，楊震.無線傳感器網(wǎng)絡中基于空間相關性的移動代理路由算法[J].電子學報，2011，39(10):2397-2401.

[11]李豐，霍瑋，馮曉兵.面向無線傳感器網(wǎng)絡應用的自適應調(diào)試方法[J].計算機學報，2011，34(7):1195-1212.

[12]韓志杰，吳志斌，王汝傳，等.新的無線傳感器網(wǎng)絡覆蓋控制算法[J].通信學報，2011，32(10):174-184.

[13]付彬，李仁發(fā)，劉彩蘋，等.無線傳感器網(wǎng)絡中一種基于網(wǎng)絡編碼的擁塞感知路由協(xié)議[J].計算機研究與發(fā)展，2011，48(6):991-999.

[14]Kim B，Kim J.Tail Asymptotics for the Queue Size Distribution in a Discrete-time Geo/G/1Retrial Queue[J].Queueing System ，2009，61(2-3):243-254.

[15]朱翼雋，馮艷剛，周宗好.具有Bernoulli反饋的負顧客M/G/1休假排隊系統(tǒng)[J].工程數(shù)學學報，2009，26(2):369-372.

Study of Business Flow Performance Based on M/G/1 Queuing Model

WANGJunxiang1，2 ，LIN Bogang2

(1.Department of Information Technology and Engineering，F(xiàn)ujian Chuanzheng Communications College，F(xiàn)uzhou 350007，China；2.Fujian Provincial Key Lab of Information Security of Network Systems，F(xiàn)uzhou University，F(xiàn)uzhou 350008，China)

As wireless sensor networks may have congestion problem，a new performance characterization method was proposedwhich first usedM/G/1 queuing model to establish one-step transition probability matrix and derived the mathematic formulas of queue length and delay time for business flow based on First Come First Served policy.A simulationwas conducted to study the relationship betweenwaiting time of the system and service rate as well as arrival rate when service source respectively obeyed fixed-length distribution and k-Erlang distribution.The results show that waiting time has positive relationship with arrival rate and negative relationship with service rate and has much impact on k-Erlang distribution.

wireless sensor networks；M/G/1 queuing model；transition probability matrix ；arrival rate

TP212.9；TP393.0

A

1004-5422(2012)04-0350-04

2012-09-25.

福建省教育廳網(wǎng)絡系統(tǒng)信息安全共建平臺(0030822711)資助項目.

王軍祥(1975—)，男，碩士，講師，從事網(wǎng)絡與信息安全技術研究.