非對稱門限服務與完全服務的性能解析①

蘇 楊, 丁陽洋

(云南大學 信息學院,昆明 650091)

1 引言

輪詢服務系統是一類調度控制模型的代表,它具有著很好的公平性[1],不僅可以對有限的資源進行分配,而且可以實現資源的共享,因此它在當前的計算網絡中得到了大量的使用. 輪詢系統自從被研究和使用以來,因其控制的靈活性、公平性和實用性,無論是在工業制造、過程控制,還是交通調度、設備維修以及通信和計算機網絡等領域都得到了廣泛應用[2,3]. 隨著研究的不斷深入以及應用的不斷擴展,有關輪詢系統的研究及應用也將會呈現前所未有的發展空間. 按服務方式的不同,輪詢服務系統可以分為門限、完全以及限定三類[4]. 而現今大多數對于輪詢服務的研究都集中在對稱性的輪詢服務當中,對于非對稱服務而言,任意時刻進入網絡的數據信息、服務時間和轉移時間等參數都是隨機可變的,因此其對應的性能分析具有相當的復雜度,所以實質性突破相對較難. 但非對稱的服務能夠更加靈活的運用于實際生活當中,由于在實際應用中,經常會有不同類信息或不同類站點,相應要求在同一種服務策略下,系統設置的參數需要滿足不同類站點自身所需的要求,這就需要非對稱的服務策略.同時,無線傳感器網絡作為下一代的傳感器網絡,它在人們的各個領域和生產活動都有著廣闊的應用前景.將輪詢服務與無線傳感器網絡相結合,可以提高系統的資源利用率,能夠減少數據業務在進行服務時帶來的沖突. 如圖1所示展現了本文的分析以及設計過程,主要由理論分析,仿真實驗和無線傳感器網絡的應用這三部分組成.

圖1 分析及設計過程

2 兩隊列的非對稱模型

2.1 非對稱服務的工作條件

(1) 在任意時刻進入隊列的數據信息是獨立、同分布的Poisson過程[5,6],其分布的概率母函數、均值和方差分別為其中i=1,2;

(2) 任意隊列中每一個數據信息接受的服務時間也是一個獨立、同分布的過程,其概率母函數、均值、方差為其中j=1,2;

(3) 查詢轉換時間分布過程的概率母函數、均值和方差各為其中k=1,2;

(4) 假設任意一個隊列的緩存容量是足夠大的,每個數據信息都可存儲在其中,不會有數據信息丟失的情況發生;

(5) 每個隊列中的每個數據信息遵照先到先服務(FCFS)的準則進行服務.

2.2 系統分析定義的變量

ui(n)：第i隊列發送完其所有的數據信息之后,轉向第i+1隊列所需的轉換時間長度;

vi(n)：第i隊列發送完其中所包含的數據信息所需的時間長度;

μj(ui)：表示在ui(n)這段時間內加入第j隊列的所有數據信息;

ηj(vi)：表示在vi(n)這段時間內加入第j隊列所有數據信息.

2.3 系統的性能分析

2.3.1 兩隊列的非對稱門限服務

由兩個隊列和一個服務器構成的兩隊列非對稱門限的輪詢服務系統[7]. 其中兩個隊列采用的服務方式是門限策略. 對于同在一個隊列所有的數據信息按照先進先出(FCFS)的方式接受服務. 隊列1中,服務的過程中仍然會有數據信息到達,而門限服務的方式是將在開始服務之前到達的全部的數據信息服務完成,至于在服務時段內到達的數據信息會被存儲下來,在下一次輪詢時再對其進行服務. 經過一個查詢轉換時間,服務器對當前隊列2所包含的數據信息進行服務,同樣,在服務期間到達的數據信息會累積下來,等下次輪詢服務開始時再對其進行訪問,隊列2服務完畢之又會經過一個查詢轉換時間,再一次轉到隊列1,以此來構成了兩隊列的非對稱輪詢服務系統. 因此可以得到,兩隊列非對稱門限服務的在tn+1時刻有如下關系式：

由此得狀態變量在tn+1時刻的概率母函數為：

對式(4)和式(5)求一階偏導可得：

其中,g1(1),g2(2)分別表示隊列1的平均排隊隊長,隊列2的平均排隊隊長. 系統的平均查詢周期是指同一個站點被系統服務器兩次查詢訪問之間的時間差的統計平均值,由轉換時間以及服務時間組成,通過計算得到其表達式為：

2.3.2 兩隊列非對稱完全服務

兩隊列非對稱完全服務的輪詢服務系統構成與門限服務相同,其服務方式是將隊列中所有的數據信息全部服務完(包括服務進入的數據信息),所以我們可以得到其狀態變量在tn+1時刻的概率母函數為：

對式(9),(10)都進行一階偏導可得

平均查詢周期為

式中g1(1)為隊列1的平均排隊隊長,g2(2)表示為隊列2的平均排隊隊長,其中兩個隊列使用的策略是非對稱完全服務.

3 多隊列非對稱模型

多隊列非對稱門限服務和多隊列非對稱完全服務輪詢系統,由一個服務器和多個隊列組成,其中多個隊列均采用門限服務的服務策略或均采用完全服務的服務策略進行工作. 對于同在一個隊列的所有數據信息也是按照先進先出(FCFS)的策略接受服務[9]. 當隊列i(i=1,2,…,N)采用門限服務時,隊列i只發送在開始服務之前隊列中所包含的數據信息,對于發送期間到達的數據信息將在下一周期輪詢時再發送. 如果隊列i使用完全服務,隊列i不僅要發送隊列中所有的數據信息,而且還要發送在服務期間進入的數據信息,直到隊列為空時,才停止發送,然后經過一個查詢轉換時間,服務器開始對下一隊列進行服務.

3.1 多隊列非對稱門限和完全服務

多隊列的非對稱門限服務和完全服務在分析的過程中,其工作條件和系統分析所定義的變量與兩隊列的服務系統保持一致,只是在此處分析過程中將兩隊列的服務機制,擴展為多對列的服務策略. 因此可以得到多隊列非對稱門限服務在tn+1時刻的系統方程為：

狀態變量在tn+1時刻的概率母函數為：

多隊列非對稱完全服務在tn+1時刻滿足的系統方程為：

則狀態變量在tn+1時刻的概率母函數為：

3.2 系統的特性分析

設定在tn時刻第i隊列發送數據信息時,第j隊列緩存區中平均存儲的數據信息為：

計算得到第i隊列使用非對稱門限服務時的平均排隊隊長為[10]：

計算得到第i隊列在接受非對稱完全服務時的平均排隊隊長為：

通過理論計算得到多隊列非對稱門限服務和完全服務系統的平均查詢周期的表達式均為：

4 仿真實驗及性能分析

根據以上所建立的非對稱門限、完全服務的系統模型,并基于下面的工作條件進行數值計算和仿真實驗．

(1) 各隊列的參數都遵從相同的概率分布,但并不具有對稱性;

(2) 任一時隙內進入各隊列的數據信息都滿足Poisson分布;

從圖2和圖3中,我們可以看出無論是非對稱門限服務還是還是非對稱完全服務,隨著到達率的增大,它們的平均排隊隊長都是隨之而增大的. 但是非對稱完全服務的平均排隊隊長小于非對稱門限服務的隊長,到達率越大,這種關系更加明顯. 從圖4中,可以觀察到,兩隊列的非對稱門限、完全服務的平均排隊隊長隨著服務率的增大,它們的平均排隊隊長也在變大,同時也滿足非對稱門限服務的平均排隊隊長大于非對稱完全服務的變化關系. 圖5至圖8為多隊列非對稱門限、完全服務系統性能特性的理論值計算與實驗仿真的關系圖,當選取統計循環次數足夠大時,信息分組的平均排隊隊長的實驗值與理論值結果保持一致,誤差較小. 對同一系統而言,兩種非對稱服務,受負載的影響是比較明顯的,尤其是當負載變大時,平均排隊隊長會急劇變大,從式(20)和式(21)中我們可以看出負載與隊長呈一個正比關系,所以圖形的變化情況與理論推導是相一致的. 與此同時,從圖5與圖6,兩種非對稱服務在隊列數N=5時平均排隊隊長隨負載變化的關系曲線,圖7與圖8,兩種服務在隊列數N=10時平均排隊隊長隨負載變化的關系曲線,都滿足在同一負載下,非對稱門限服務的平均排隊隊長大于非對稱完全服務的平均排隊隊長,隨著負載的變大這種關系更加明顯,而且無論隊列數是多還是少,這種關系是一直存在的.所以就其平均排隊隊長而言,非對稱完全服務是優越于非對稱門限服務的,然而從公平性來看非對稱門限服務要比非對稱的完全服務好. 綜上,也給在無線傳感器網絡中,選擇一種合適的輪詢服務提供了參考,例如,當數據業務量或者是網絡流量較大時,非對稱完全服務的公平性相對較差,業務的服務質量得不到很好的保障,此時我們應當選擇非對稱門限的機制來進行服務.

圖2 隊列1中到達率與平均排隊隊長的關系

圖3 隊列2中到達率與平均排隊隊長的關系

5 無線傳感器網絡中輪詢服務的設計

在無線傳感器網絡中實現非對稱的輪詢服務,我們將選擇由加州伯克利分校根據無線傳感器網絡的特點專門為其設計并實現的Tiny0S嵌入式操作系統作為軟件平臺[10,11]. 在硬件平臺的選擇上,我們選擇cc2538cb來作為傳感器節點. 測試過程中將設定一個節點作為匯聚節點來充當服務器,負責對其他多個子節點進行服務. 每個子節點在未接受服務之前,一直處于睡眠偵聽的狀態,當接收到來自于服務器的信標幀時,就會被喚醒,此時就會選擇門限服務或完全服務的方式對對數據包進行發送. 在無線傳感器網絡的應用中,我們可以根據此前分析得到兩種非對稱服務的性能差異去選擇一種合適的服務,因為在數據業務量較大時,完全服務系統的公平性和服務質量較差,此時就可以去選擇門限服務的方式.

節點程序主要用到的組件有main組件,led燈組件LedC,時鐘組件TimeC,IPStackC組件,還有StaticIPAddressTosIdC和UdpSocket組件,組件之間的連接關系如下圖9所示.

圖4 服務時間與平均排隊隊長的關系

圖5 非對稱門限服務平均排隊隊長受負載影響變化曲線(N=5)

圖6 非對稱完全服務平均排隊隊長受負載影響變化曲線(N=5)

6 結論

本文以兩對列的非對稱服務模型作為基墊,使用嵌入式馬爾可夫鏈和概率母函數的方法對非對稱性門限服務和非對稱完全服務控制技術建立了模型[12,13],對兩種非對稱服務的特性進行了比較,得到了兩隊列非對稱的輪詢服務系統中,隨著到達率和服務率的增大完全服務的平均排隊隊長小于門限服務的平均排隊隊長的變化關系. 同時,在此基礎之上,將兩種非對稱服務的分析拓展到多個隊列,隨之分析了兩種多對列的性能特性,通過理論計算和實驗仿真證明了兩種多隊列非對稱服務模型的有效性. 與對稱的輪詢服務相比較,對稱性的輪詢系統各參數是固定不變的,所以存在一定的局限性,但是在非對稱的輪詢服務中,其系統參數是可變化的,也因此其能夠更好的滿足實際應用的需求. 在未來的工作中,我們將對非對稱的輪詢服務在無線傳感器網絡中的應用中進行深入的研究,并可以根據本文分析得到的兩種非對稱服務的性能差異,針對應用實際的需要動態的選擇一種更為適合的輪詢服務.

圖7 非對稱門限服務平均排隊隊長受負載影響變化曲線(N=10)

圖8 非對稱完全服務平均排隊隊長受負載影響變化曲線(N=10)

圖9 組件的連接關系

1 楊志軍,趙東風,丁洪偉,等. 兩級優先級控制輪詢系統研究. 電子學報,2009,37(7)：1452-1456.

2 楊志軍,丁洪偉,陳傳龍. 完全服務和門限服務兩級輪詢系統E(x)特性分析. 電子學報,2014,42(4)：774-778.

3 楊志軍. 兩級優先級控制輪詢系統理論及應用研究[博士學位論文]. 昆明：云南大學,2008.

4 Yang ZJ,Ding HW,Guan Z,et al. A new transportation control system based on priority differentiated polling strategy. Proceedings of 2015 World Conference on Control,Electronics and Electrical Engineering. Shanghai,China 2015. 38-44.

5 Yang ZJ,Ding HW. Characteristics of a two-class polling system model. Tsinghua Science and Technology,2014,19(5)：516-520. [doi：10.1109/TST.2014.6919828]

6 He M,Guan Z,Bao LY. An analysis of polling access protocol for wireless sensor networking. 2015 IEEE International Conference on Cyber Technology in Automation,Control,and Intelligent Systems. Shenyang,China. 2015. 720-724.

7 Xiong JL,Yang ZJ,Ding HW,et al. The analysis of performance for priority distinction double-queue and triple-server communication network. 2015 International Conference on Computer Science and Software Engineering. 2015. 810-826.

8 趙東風,鄭蘇民. 周期查詢式門限服務排隊系統中信息分組的延遲分析. 通信學報,1994,15(2)：18-23.

9 趙東風,鄭蘇民. 查詢式完全服務排隊模型分析. 電子學報,1994,22(5)：102-107.

10 李遠英,王正萬. 基于ZigBee技術的無線傳感數據采集網絡研究與應用. 數字技術與應用,2015,(3)：29-30.

11 姜久超,郭玉霞,王紅艷,等. 基于C8051F040的CAN總線溫濕度數據采集系統設計. 電子設計工程,2015,23(19)：30-33. [doi：10.3969/j.issn.1674-6236.2015.19.010]

12 趙東風,李必海,鄭蘇民. 周期查詢式限定服務排隊系統研究. 電子科學學刊,1997,19(1)：44-49.

13 趙光蘭. 基于非對稱性的門限服務PCF問題分析[碩士學位論文]. 昆明：云南大學,2011.