楊志軍，寇倩蘭，丁洪偉

(1. 云南大學(xué)信息學(xué)院，云南 昆明 650500；2. 云南省教育廳教學(xué)儀器裝備中心，云南 昆明 650223)

1 引言

如今，各行各業(yè)都與信息技術(shù)有著深入的結(jié)合，無線傳感器網(wǎng)絡(luò)在整個社會的服務(wù)領(lǐng)域都產(chǎn)生較大影響。特別是5G時代的到來，超大顧客流量、密集站點接入和超高可靠與低時延服務(wù)的需求，對基本輪詢系統(tǒng)的服務(wù)效率和拓展輪詢應(yīng)用空間提出來更高的要求[1]。網(wǎng)絡(luò)并發(fā)量增加急需降低網(wǎng)絡(luò)時延，提高服務(wù)質(zhì)量。一直以來也有許多的針對輪詢系統(tǒng)降低延遲、提高系統(tǒng)性能方面的研究。輪詢系統(tǒng)作為一種廣泛使用的防沖突協(xié)議[2]，基本可分為三種：門限服務(wù)、完全服務(wù)和限定服務(wù)。在三種服務(wù)策略的對比中可以發(fā)現(xiàn)限定服務(wù)的公平性最好[3]。但是其工作效率卻因為服務(wù)器一次只對站點中的K個信息分組進行服務(wù)而受到限制。在優(yōu)化輪詢系統(tǒng)性能過程中，平均排隊隊長、平均等待時間和平均輪詢周期常常作為三個重要指標參與研究討論[4]。

三種基本輪詢策略常?？梢宰龀龆喾N改變以改善輪詢系統(tǒng)性能。為減少系統(tǒng)能耗，站點的忙閑狀態(tài)常作為系統(tǒng)在低負載時是否選擇休眠的依據(jù)[5-7]。文獻[8]提出了分忙閑站點的限定K=2輪詢系統(tǒng)模型。依據(jù)站點的忙閑狀態(tài)采用并行調(diào)度方式對有信息分組的忙站點提供發(fā)送服務(wù)，以節(jié)省轉(zhuǎn)換發(fā)送時間，降低系統(tǒng)時延。文獻[9]提出一種基于輪詢機制的機會干擾對齊算法，在提升公平性的同時，有效地減少傳輸塊數(shù)，增強系統(tǒng)容量，靈活滿足用戶通信需求。當沒有流量控制或沒有采用標準的以太網(wǎng)暫停幀流量控制時，投放點會有很高的緩沖區(qū)占用率。為了減少這種投放點緩沖區(qū)占用問題，文獻[10]引入了兩種門限流量控制協(xié)議對服務(wù)策略進行調(diào)整。在眾多研究中，提高系統(tǒng)吞吐量和總線利用率也是對輪詢系統(tǒng)進行改進的重點[11]。文獻[12]提出一種針對可擴展的MAC協(xié)議模型，為得到飽和吞吐量，通過四態(tài)傳統(tǒng)馬爾可夫模型對其進行建模，減輕了多媒體流量負擔。文獻[13]將輪詢順序與包括門限和完全服務(wù)在內(nèi)的訪問策略相結(jié)合，提出了一種新的WSN中基于優(yōu)先級的并行調(diào)度輪詢MAC協(xié)議，用以實現(xiàn)基于優(yōu)先級的方案，同時通過并行調(diào)度減少開銷時間。通過嵌入式馬爾可夫鏈和生成函數(shù)建立模型，分析了平均隊列長度、周期時間和吞吐量等關(guān)鍵系統(tǒng)性能特征。結(jié)果表明，新協(xié)議具有更好的性能。

上述文獻從不同方面針對輪詢系統(tǒng)的優(yōu)化進行了研究，但基本上都是在單個服務(wù)器基礎(chǔ)上開展的，缺乏對服務(wù)器個數(shù)變化的系統(tǒng)性能研究。本文就是基于此點，提出了雙服務(wù)器的輪詢控制系統(tǒng)。在分布式多服務(wù)器系統(tǒng)和網(wǎng)絡(luò)中，對各個站點的服務(wù)可以進行批處理[14]，每個用戶也可以由不同的服務(wù)器分配資源以獲得公平性和服務(wù)[15]。由于門限服務(wù)需對服務(wù)站點內(nèi)當前服務(wù)時間前的所有信息分組進行服務(wù)；完全服務(wù)更需要對當前服務(wù)站點內(nèi)全部信息分組服務(wù)完畢，直到該站點為空才能轉(zhuǎn)向下一站點。故這兩種服務(wù)策略的公平性都遠遠小于限定服務(wù)。為保證系統(tǒng)公平性，本文選擇一次只對站點中的K個信息分組進行服務(wù)的限定雙服務(wù)器輪詢系統(tǒng)模型。采用嵌入式馬爾可夫鏈理論和概率母函數(shù)方法[16]對限定K=1和限定K=2同步雙服務(wù)器系統(tǒng)進行建模，得出平均排隊隊長和平均等待時間的理論表達式。然后在Matlab中仿真，驗證方案的可行性。最后將同步和異步方式的限定雙服務(wù)器輪詢系統(tǒng)與單服務(wù)器進行對比，得出一種最佳服務(wù)方式。

2 輪詢系統(tǒng)模型

輪詢系統(tǒng)具有公平性、靈活性、高效性、實用性、高服務(wù)質(zhì)量等特性，被廣泛應(yīng)用于無線傳感器網(wǎng)絡(luò)中[17]。避免數(shù)據(jù)沖突、減小傳輸時延、提高系統(tǒng)吞吐量和總線利用率等方向始終是輪詢系統(tǒng)研究的熱點[18]。本文主要針對增加服務(wù)器數(shù)量和改變服務(wù)方式對系統(tǒng)性能的改變做出研究，整個過程采用限定服務(wù)策略。

限定雙服務(wù)器輪詢系統(tǒng)是由兩個服務(wù)器和N個站點組成，如圖1所示。服務(wù)器從第一個站點開始對其存儲器內(nèi)的信息分組按照一個方向進行服務(wù)，服務(wù)結(jié)束則轉(zhuǎn)向下一個站點，直到第N個站點也服務(wù)完畢又轉(zhuǎn)向第一個站點重新開始。服務(wù)器調(diào)度有同步和異步兩種方式。本文針對同步方式又分別研究了限定K=1和限定K=2兩種系統(tǒng)模式。對異步方式則研究了限定K=1服務(wù)。

圖1 限定雙服務(wù)器系統(tǒng)模型

3 同步方式

同步服務(wù)方式是指兩個服務(wù)器同時到達站點并對其存儲器內(nèi)等待發(fā)送的信息分組進行服務(wù)，服務(wù)完畢同時離開。同步方式下各站點的狀態(tài)轉(zhuǎn)移過程如圖2所示。

圖2 同步方式各站點服務(wù)狀態(tài)轉(zhuǎn)移圖

限定K=1同步雙服務(wù)器模型具體服務(wù)策略為：

從第一個站點開始，服務(wù)器按照同步服務(wù)方式每次只對非空站點內(nèi)的一個信息分組服務(wù)，服務(wù)完成之后立即轉(zhuǎn)向下一站點。直到對站點N內(nèi)的信息分組也完成服務(wù)后又轉(zhuǎn)向第一個站點重復(fù)進行相同操作。

限定K=2同步雙服務(wù)器模型具體服務(wù)策略為：

1) 服務(wù)器按照同步服務(wù)方式從第一個站點開始服務(wù)，依次往后，直到最后一個站點也被服務(wù)之后再轉(zhuǎn)向第一個站點；

2) 當站點為空時，不對其進行服務(wù)；當站點存儲器中只有一個等待發(fā)送的信息分組時，只對該站點中這一個信息分組進行服務(wù)，服務(wù)完畢立即轉(zhuǎn)向下一站點；當站點存儲器中等待發(fā)送的信息分組超過一個時，則只對該站點內(nèi)兩個信息分組進行服務(wù)，完成服務(wù)后轉(zhuǎn)向下一站點[19]。

對于同步服務(wù)方式通過概率母函數(shù)和馬爾可夫理論建?？赏茖?dǎo)出平均排隊隊長、平均等待時間的理論表達式。下面將進行詳細推導(dǎo)。

3.1 定義變量

系統(tǒng)工作環(huán)境及相關(guān)變量定義：

4) 各個站點內(nèi)存儲器能夠容納足夠多的信息分組；

5) 各個站點存儲器中等待發(fā)送的信息分組按照先進先出的原則進行傳輸。

假設(shè)兩個服務(wù)器在tn時刻對i號站點進行服務(wù)，當服務(wù)完i號站點內(nèi)的信息分組之后，轉(zhuǎn)向在tn+1時刻接受服務(wù)i+1號站點，對其存儲器內(nèi)等待發(fā)送的信息分組提供服務(wù)。ξi(n)表示tn時刻i號站點中存儲器內(nèi)等待發(fā)送信息分組總數(shù)，tn時刻系統(tǒng)的狀態(tài)變量可表示為[ξ1(n)，ξ2(n)，…，ξi(n)，…，ξN(n)]，tn+1時刻系統(tǒng)的狀態(tài)變量為[ξ2(n)，ξ3(n)，…，ξi+1(n)，…，ξN+1(n)]，系統(tǒng)保持穩(wěn)定的條件為：Nλβ<2。其限定K=1服務(wù)概率母函數(shù)為：

Gi+1(1)(z1，z2，…，zi，…，zN)

[Gi(z1，z2，…，zi，…，zN)

-Gi(z1，z2，…，zi-1，0，zi+1，…，zN)]

+Gi(z1，z2，…，zi-1，0，zi+1，…，zN)}

i=1，2，…，N

(1)

限定K=2服務(wù)概率母函數(shù)為

Gi+1(2)(z1，z2，…zi，…，zN)

ziGi′(z1，…，zi-1，0，zi+1，…，zN)-

Gi(z1，…，zi-1，0，zi+1，…，zN)]+

+Gi(z1，…，zi-1，0，zi+1，…，zN)}

i=1，2，…N

(2)

3.2 平均排隊隊長

平均排隊隊長是指服務(wù)器在tn時刻對i號站點提供服務(wù)時，各個站點存儲器中平均存儲的信息分組數(shù)?？梢酝ㄟ^對系統(tǒng)的概率母函數(shù)求導(dǎo)得出在tn時刻j號站點內(nèi)存儲的信息分組數(shù)，用gi(j)表示。

(3)

由式(1)(3)可求得限定K=1同步雙服務(wù)器的平均排隊隊長為

i=1，2，…，N

(4)

同理可得，限定K=2同步雙服務(wù)器的平均排隊隊長為

4Nλγ-2N2λγρ-Nλ2γ2]

i=1，2，…，N

(5)

其中，ρ=λβ。

3.3 平均等待時間

平均等待時間是指信息分組從進入站點存儲器內(nèi)到被發(fā)送出去的這段時間。與單服務(wù)器的計算方法類似，借用文獻[20]的方法，計算限定K=1同步雙服務(wù)器的平均等待時間得：

NλR″(1)]

(6)

同理可得，限定K=2同步雙服務(wù)器的平均等待時間得

(7)

其中，ρ=λβ。

4 異步方式

異步方式是指兩個服務(wù)器分別到達不同的站點按照限定服務(wù)規(guī)則對站點內(nèi)信息分組進行服務(wù)。異步方式下各站點的狀態(tài)轉(zhuǎn)移過程如圖3所示。

圖3 異步方式各站點服務(wù)狀態(tài)轉(zhuǎn)移圖

限定K=1異步雙服務(wù)器模型具體服務(wù)策略為：

1) 如果到達時有服務(wù)器正在對站點服務(wù)就直接離開對下一站點進行服務(wù)，反之則對當前站點內(nèi)相應(yīng)數(shù)量的信息分組進行服務(wù)，服務(wù)完成再轉(zhuǎn)向下一個站點；

2) 服務(wù)器按照異步服務(wù)方式每次只對非空站點內(nèi)的一個信息分組進行服務(wù)。

由于異步服務(wù)方式調(diào)度的復(fù)雜性，無法推導(dǎo)出排隊隊長和平均時延的理論表達式，故直接采用Matlab進行實驗分析其性能。

5 仿真與分析

5.1 同步方式性能分析

根據(jù)第二節(jié)建立的系統(tǒng)模型，在系統(tǒng)穩(wěn)定條件下進行數(shù)值計算和仿真，理論值由式(4)-(7)計算得出，實驗在Matlab2019a平臺展開。設(shè)定系統(tǒng)有10個站點，服務(wù)器按照限定服務(wù)方式提供服務(wù)，單個服務(wù)器對一個信息分組服務(wù)需要2時隙，服務(wù)器在相鄰站點間的轉(zhuǎn)換查詢時間為1時隙。將信息分組進入站點存儲器內(nèi)的到達率設(shè)為自變量，在從0.0001到0.001依次變化，觀察信息分組的平均隊長和平均時延的情況，結(jié)果如圖4和圖5所示。

圖4 限定K=1同步雙服務(wù)器平均排隊隊長

圖5 限定K=1同步雙服務(wù)器平均等待時間

圖4-5對限定K=1同步雙服務(wù)器系統(tǒng)的平均排隊隊長和平均等待時間進行仿真，得到對應(yīng)的理論值和仿真值對比。可以看出平均排隊隊長和平均等待時間都隨著到達率的增加而呈線性增長，即隨著站點內(nèi)到達的信息分組的數(shù)量增長，存儲器內(nèi)隊列長度也跟著變長，信息延遲增加。該現(xiàn)象與實際相符。在到達率小于0.005之前其平均隊長和平均時延的理論值和仿真值近似相等，仿真效果較好。當?shù)竭_率處于0.005-0.01之間時，理論值和仿真值存在一個較小的誤差，但仍在可允許范圍之內(nèi)。故證明了理論分析的正確性。

圖6-7對限定K=2同步雙服務(wù)器系統(tǒng)的平均隊長和平均等待時間進行仿真。平均隊長和平均時延都到達率的增加而增加，與實際相符?？梢悦黠@看出K=2限定條件下兩個目標參數(shù)的理論值和仿真值之間誤差非常小，可忽略不計，效果顯然好于限定K=1。再次驗證了該方案分析的正確性。

圖6 限定K=2同步雙服務(wù)器平均排隊隊長

圖7 限定K=2同步雙服務(wù)器平均等待時間

圖8將傳統(tǒng)限定K=1單服務(wù)器系統(tǒng)、限定K=2單服務(wù)器系統(tǒng)、限定K=1同步雙服務(wù)器系統(tǒng)和限定K=2同步雙服務(wù)器系統(tǒng)的平均隊長進行對比。由圖8可知，兩個限定單服務(wù)器系統(tǒng)的平均隊長大致相等，說明限定條件K=1和K=2的變化并不影響站點內(nèi)信息分組的隊列長度。兩個限定同步雙服務(wù)器系統(tǒng)的平均隊長也幾乎相等，并且理論值和仿真值之間的誤差小于限定單服務(wù)器系統(tǒng)，再次驗證了K=1和K=2的限定條件不影響隊列長度的結(jié)論。同時，同步雙服務(wù)器系統(tǒng)的平均隊長明顯小于單服務(wù)器的隊長，說明使用雙服務(wù)器提供服務(wù)，降低了站點內(nèi)信息分組的平均排隊隊長，提高了系統(tǒng)性能。

圖8 單服務(wù)器與同步雙服務(wù)器的平均隊長對比

圖9是將K=1和K=2條件下的傳統(tǒng)限定單服務(wù)器系統(tǒng)和同步雙服務(wù)器系統(tǒng)進行對比。容易知道，傳統(tǒng)限定K=1單服務(wù)器系統(tǒng)的平均時延是最高的。當把限定條件改為K=2時，平均時延就下降很多，且隨著站點內(nèi)的信息分組越多，下降越明顯，優(yōu)化效果越好。而同步雙服務(wù)器系統(tǒng)的平均時延均小于傳統(tǒng)單服務(wù)器系統(tǒng)，且K=1時的時延大于K=2條件下的時延。隨到達率增加，站點內(nèi)吞吐量變大，這種差距就越大。該結(jié)論與單服務(wù)器系統(tǒng)的結(jié)論相符，也再次說明該方案的正確性。所以，同步雙服務(wù)器系統(tǒng)能大大降低系統(tǒng)時延，加快信息處理速度，改進系統(tǒng)性能。且限定條件K=2的降低幅度明顯大于K=1，故限定K=2同步雙服務(wù)器系統(tǒng)的優(yōu)化效果是最好的。

圖9 單服務(wù)器與同步雙服務(wù)器的平均時延對比

圖10將4種系統(tǒng)的平均輪詢周期做比較，結(jié)果證明K=1和K=2的限定條件不影響服務(wù)器對站點服務(wù)的輪詢周期，但同步雙服務(wù)器系統(tǒng)的平均周期遠小于單服務(wù)器系統(tǒng)。因此，使用同步雙服務(wù)器系統(tǒng)明顯降低了輪詢周期，提高了輪詢效率。

圖10 單服務(wù)器與同步雙服務(wù)器的平均周期對比

綜上所述，輪詢系統(tǒng)服務(wù)器個數(shù)增加，使得信息分組的排隊隊長降低，減少了分組時延，提高了信息分組傳遞效率。在同樣的負載下，雙服務(wù)器系統(tǒng)具有更高的效率。且在限定條件為K=2時，信息分組的延遲小于K=1時，信息處理速率更快。

5.2 異步方式性能分析

圖11將限定條件為K=1和K=2下的單服務(wù)器系統(tǒng)與限定K=1異步雙服務(wù)器系統(tǒng)的平均排隊隊長進行對比。由圖11可知，異步雙服務(wù)器系統(tǒng)的平均排隊隊長明顯小于單服務(wù)器系統(tǒng)，大大降低了站點內(nèi)信息分組的隊列長度，減少信息傳輸時延。

圖11 單服務(wù)器與異步雙服務(wù)器的平均隊長對比

圖12將限定條件為K=1和K=2下的單服務(wù)器系統(tǒng)與限定K=1異步雙服務(wù)器系統(tǒng)的平均等待時間進行對比。由圖12可知，單服務(wù)器系統(tǒng)的平均時延遠遠大于異步雙服務(wù)器系統(tǒng)，且隨到達率的增加，平均時延有一個明顯的上升趨勢。而異步雙服務(wù)器系統(tǒng)不僅平均時延大大降低，同時隨到達率的增加，平均時延只是有一個緩慢的增長。故輪詢系統(tǒng)通過增加服務(wù)器個數(shù)并采用異步方式可以很好的降低延遲，增加系統(tǒng)吞吐量，提高信息處理速率。

圖12 單服務(wù)器與異步雙服務(wù)器的平均時延對比

圖13將限定條件為K=1和K=2下的單服務(wù)器系統(tǒng)與限定K=1異步雙服務(wù)器系統(tǒng)的平均輪詢時間進行對比。由圖13可知，異步雙服務(wù)器系統(tǒng)輪詢周期明顯小于單服務(wù)器系統(tǒng)，故采用異步雙服務(wù)器模式可減少輪詢周期，提高輪詢效率，加快信息傳輸。

圖13 單服務(wù)器與異步雙服務(wù)器的平均周期對比

綜上所述，不論采用同步或異步方式，增加輪詢系統(tǒng)服務(wù)器個數(shù)都能減少信息分組排隊長度，降低延遲，增加系統(tǒng)吞吐量，提高信息處理效率。

圖14 同步與異步方式的平均隊長對比

圖14-15將在限定K=1和K=2條件下的同步雙服務(wù)器系統(tǒng)與限定K=1異步雙服務(wù)器系統(tǒng)進行對比，研究同為雙服務(wù)器系統(tǒng)下的同步和異步方式對系統(tǒng)性能的影響。圖14表明，異步方式的平均排隊隊長明顯小于同步方式，故異步處理系統(tǒng)的性能比同步更好。

圖15 同步與異步方式的平均時延對比

圖15表明，異步方式的平均等待時間遠小于同步方式。同步方式中的K=2限定條件針對異步方式并沒有明顯優(yōu)勢。即異步極大的降低了信息分組的等待時間，加快信息處理及輪詢效率。

綜上所述，雙服務(wù)器的運用明顯降低了信息分組在存儲器中的排隊時間，進而降低了數(shù)據(jù)包延遲，提高了信息處理效率，擴大了系統(tǒng)吞吐量。在一定條件下，K的取值越大，對限定同步服務(wù)方式的系統(tǒng)性能改善越好。而對于限定K=1服務(wù)系統(tǒng)，異步方式的處理使得系統(tǒng)平均隊長和時延更低。相較同步雙服務(wù)器系統(tǒng)，異步方式在降低平均隊長和時延方面，表現(xiàn)得更好。故同樣條件下，異步比同步更易達成信息分組的高效傳輸。

6 結(jié)論

如今，網(wǎng)絡(luò)用戶的數(shù)量迅速增加，其需求量也隨之擴大。由于輪詢系統(tǒng)本身具有防沖突性，且限定服務(wù)策略的公平性最好。故為保證在較高的網(wǎng)絡(luò)并發(fā)量中實現(xiàn)高效傳輸，本文提出限定雙服務(wù)器系統(tǒng)。同時通過馬爾科夫鏈并運用概率母函數(shù)方法建立限定雙服務(wù)器系統(tǒng)的數(shù)學(xué)模型對其展開研究。

本文在第一部分，對輪詢研究進行分析，并提出多服務(wù)輪詢控制方式。在第二、三和四部分，對同步和異步兩種服務(wù)方式的數(shù)據(jù)分發(fā)過程做了詳細分析，同時推導(dǎo)了同步服務(wù)系統(tǒng)的平均排隊隊長和平均等待時間兩個目標參數(shù)及其理論表達式。在第五部分對系統(tǒng)模型進行仿真及性能研究。結(jié)果表明，同步雙服務(wù)器明顯降低了平均隊長、平均時延和平均周期，其中限定K=2同步雙服務(wù)系統(tǒng)的系統(tǒng)性能最好。異步方式相對其它服務(wù)方式極大的提高了信息傳輸速率，性能效果最好。故系統(tǒng)限定雙服務(wù)器系統(tǒng)能在保證公平性的基礎(chǔ)上實現(xiàn)高效傳輸。