王亞軍，張 艷，周圣武，李金玉

(中國礦業(yè)大學(xué))

基于生滅論的通信緩存區(qū)數(shù)據(jù)隊長研究*

王亞軍，張 艷，周圣武，李金玉

(中國礦業(yè)大學(xué))

在通信網(wǎng)絡(luò)中，基站和終端數(shù)據(jù)傳輸上下行的速率不同，數(shù)據(jù)成功上傳之前，經(jīng)常會有一定的數(shù)據(jù)包滯留在終端，這個滯留區(qū)稱作緩存區(qū).本文研究了緩存區(qū)滯留數(shù)據(jù)包的隊長問題，求得了隊長的絕對分布和數(shù)據(jù)包平均隊長、平均滯留時間的穩(wěn)態(tài)解.

生滅論；通信網(wǎng)絡(luò)；緩存區(qū)；隊長

0 引言

緩存(Cache memory)是硬盤控制器上的一塊內(nèi)存芯片，它是計算機硬盤內(nèi)部存儲和外界接口之間的緩沖器.由于硬盤的內(nèi)部數(shù)據(jù)傳輸速度和外界介面?zhèn)鬏斔俣炔煌?，緩存在其中起到一個緩沖的作用.通信系統(tǒng)中，首先需要對通信網(wǎng)絡(luò)進(jìn)行建模，一個普遍的通信系統(tǒng)模型是一個AP接入點為一組物理設(shè)備提供服務(wù)，這里稱接入點為基站，每個物理設(shè)備稱為終端.基站和終端之間要進(jìn)行數(shù)據(jù)的交換，它們對數(shù)據(jù)包的處理能力不同，因此基站和終端之間數(shù)據(jù)交換的上下行的速度不同.終端接收數(shù)據(jù)后上傳到基站或其他終端設(shè)備前，需要對數(shù)據(jù)進(jìn)行分析和處理，這段時間數(shù)據(jù)就停留在終端設(shè)備，此時終端設(shè)備就起到數(shù)據(jù)緩存區(qū)的作用.緩存區(qū)數(shù)據(jù)包的個數(shù)稱為數(shù)據(jù)隊長，分析緩存區(qū)數(shù)據(jù)的隊長對通信系統(tǒng)的網(wǎng)絡(luò)建模具有重要意義.

1 緩存區(qū)數(shù)據(jù)隊長的提出

一個普遍的通信網(wǎng)絡(luò)模型是一個基站為多個終端提供服務(wù)[1]，即數(shù)據(jù)的交換.此時假設(shè)通信在n個時隙中有k個終端想要與之進(jìn)行數(shù)據(jù)傳輸，定義Lmn為第m個終端在第n個時隙中緩存中數(shù)據(jù)包的個數(shù)(即隊長)，第m個終端在第n個時隙中接收數(shù)據(jù)包的概率p1(h)=λ1h+o(h),λi>0，終端向基站上行數(shù)據(jù)包的概率p2(h)=μih+o(h),μi>0，數(shù)據(jù)上傳后從緩存區(qū)刪除，否則繼續(xù)存在于緩存區(qū)，接收的數(shù)據(jù)包在緩存區(qū)累加排隊處理，按照先進(jìn)先出的原則依次處理和上傳數(shù)據(jù).相鄰兩個數(shù)據(jù)包的上行和下行都具有一定的時間間隔，在非常短的時間間隔內(nèi)只有1個數(shù)據(jù)包的上行或下行.該文考慮的是一個數(shù)據(jù)終端的隊長情況，因此把Lmn簡記為Lm.

2 數(shù)據(jù)隊長模型

根據(jù)模型和實際情況，有如下狀態(tài)轉(zhuǎn)移式：

這里pi,i+1(h)表示在時間為h的間隔內(nèi)，緩存區(qū)數(shù)據(jù)隊長由i增加到i+1的概率，λi表示增加的速率，μi表示減少的速率，它們反映單位時間內(nèi)基站和終端上下行數(shù)據(jù)包的多少.第i個終端t時刻緩存區(qū)隊長Lm只依賴t-1時刻的取值，而與t-1之前的結(jié)果無關(guān)，因此隊長Lm(t)是一個馬爾科夫鏈，具體講它是一個生滅過程，其狀態(tài)空間E={0,1,2,…}，狀態(tài)轉(zhuǎn)移僅僅在相鄰的狀態(tài)中進(jìn)行，其狀態(tài)轉(zhuǎn)移圖如圖1所示.

圖1

該生滅過程可作如下解釋[2]：Lm(t)代表時刻第m個終端緩存中數(shù)據(jù)包的隊長，則在很小的時隙內(nèi)，緩存中隊長的變化有三種可能，狀態(tài)由i變到i+1，即基站向終端發(fā)送數(shù)據(jù)，緩存數(shù)據(jù)包增加一個，其概率為λih+o(h)；狀態(tài)由i變到i-1，緩存數(shù)據(jù)包減少一個，其概率為μih+o(h)；數(shù)據(jù)包數(shù)量不變，其概率為1-λih-μih+o(h)，若記狀態(tài)轉(zhuǎn)移矩陣p(h)=(pij(h))，I為同階單位矩陣，則該過程的狀態(tài)轉(zhuǎn)移速率矩陣Q為

對于一般化的通信系統(tǒng)，假定基站向終端源源不斷的發(fā)送數(shù)據(jù)，終端緩存區(qū)所允許的數(shù)據(jù)包的隊長是無限的，對于終端，基站的下行數(shù)據(jù)包的到達(dá)均為Poisson到達(dá)[3]，到達(dá)強度為λ.因此在長度為h的時間間隔內(nèi)終端接收到一個數(shù)據(jù)包的概率為λh+o(h)，多于一個數(shù)據(jù)包的概率為o(h)，沒有數(shù)據(jù)包到達(dá)的概率為1-λh+o(h).有泊松理論，接收到相鄰兩個數(shù)據(jù)包的時間間隔是獨立同參數(shù)為λ的指數(shù)變量.另一方面，在長度為h的時間間隔內(nèi)終端上傳一個數(shù)據(jù)包的概率為μh+o(h)，多于一個數(shù)據(jù)包離開的概率為o(h)，沒有數(shù)據(jù)包上傳的概率為1-μh+o(h)，上傳相鄰兩個數(shù)據(jù)包的時間間隔是獨立同參數(shù)為μ的指數(shù)變量.若記L(t),(t≥0)表示時刻緩存區(qū)的隊長，其狀態(tài)空間是E={0,1,2,…}，于是它的Q矩陣

由柯爾莫格洛夫向后方程可得{L(t),t≥0}的絕對概率分布pj(t)=P{L(t)=j},(j∈E)滿足方程

由上述Q矩陣，在t時刻緩存區(qū)數(shù)據(jù)隊長所滿足的微分方程為

3 數(shù)據(jù)隊長的極限分布求解

k>0

該分布為幾何分布.這里π0為緩存區(qū)沒有數(shù)據(jù)包的概率，而1-π0表示緩存區(qū)有數(shù)據(jù)包等待的概率.

有了上述極限分布之后，不難算出下面2個緩存區(qū)在穩(wěn)態(tài)時的數(shù)值參量：

(1)緩存區(qū)數(shù)據(jù)包的平均數(shù)即平均隊長為

(2)數(shù)據(jù)包在緩存區(qū)的平均滯留時間，由文獻(xiàn)[4-5]可得

4 結(jié)束語

通信系統(tǒng)中進(jìn)行數(shù)據(jù)傳輸經(jīng)常遇到輸入和輸出速率不對稱的情況，基站和服務(wù)終端數(shù)據(jù)傳送由于終端對數(shù)據(jù)的分析與處理也會導(dǎo)致上下行速率不一，終端在上行或轉(zhuǎn)發(fā)數(shù)據(jù)之前會把數(shù)據(jù)暫存于緩存區(qū)，這樣，數(shù)據(jù)包經(jīng)常在緩存區(qū)滯留.該文研究了緩存區(qū)的數(shù)據(jù)包的隊長問題，得出了其平穩(wěn)分布、平均隊長、平均滯留時間的穩(wěn)態(tài)解.文中考慮的是最普通的通信網(wǎng)絡(luò)系統(tǒng)的情形，對更復(fù)雜的多基站多終端組成的通信網(wǎng)絡(luò)緩存區(qū)隊長研究具有重要意義.

[1] 趙天馳，邢遠(yuǎn)．基于馬爾科夫鏈理論的通信網(wǎng)絡(luò)建模與性能分析[J]．電子科學(xué)技術(shù)，2015，2(6)：657-660.

[2] 孫洪祥．隨機過程[M]．北京：機械工業(yè)出版社，2009.

[3] 戴琳，秦叔明，董艷梅．切換排隊且排隊優(yōu)先的通信信道配置模型[J]．云南師范大學(xué)學(xué)報，2012，32(2)：42-46．

[4] 王亞軍，張艷．σ-代數(shù)下條件期望的若干應(yīng)用[J]．哈爾濱師范大學(xué)自然科學(xué)學(xué)報，2016，32(3)：1-3．

[5] 陳紅燕，鄧臻．隨機變量數(shù)學(xué)期望計算[J]．哈爾濱師范大學(xué)自然科學(xué)學(xué)報，2015，31(5)：44-45.

ResearchonDataQueueofCommunicationBufferBasedonBirth-DeathTheory

Wang Yajun, Zhang Yan, Zhou Shengwu, Li Jingyu

(China University of Mining and Technology)

In a communication network, the rate of uplink and downlink of data transmission between base station and terminal is different. Before the data is uploaded successfully, a certain number of packets are stuck at the terminal. This retention area is called the buffer zone. In this paper, the queue length problem of the buffer packets is studied, and the absolute distribution of the queue length and the steady-state solution of the average queue length and the average residence time of the packets are obtained.

Birth death theory; Communication network; Buffer area; Queue length

季春陽)

O211.62；TN911

A

1000-5617(2017)04-0006-03

2017-04-11

*中國礦業(yè)大學(xué)2017年校教育教學(xué)改革立項項目(2017YB28)