蘇 楊, 丁陽洋

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

1 引言

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

圖1 分析及設(shè)計(jì)過程

2 兩隊(duì)列的非對(duì)稱模型

2.1 非對(duì)稱服務(wù)的工作條件

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

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

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

(4) 假設(shè)任意一個(gè)隊(duì)列的緩存容量是足夠大的,每個(gè)數(shù)據(jù)信息都可存儲(chǔ)在其中,不會(huì)有數(shù)據(jù)信息丟失的情況發(fā)生;

(5) 每個(gè)隊(duì)列中的每個(gè)數(shù)據(jù)信息遵照先到先服務(wù)(FCFS)的準(zhǔn)則進(jìn)行服務(wù).

2.2 系統(tǒng)分析定義的變量

ui(n)：第i隊(duì)列發(fā)送完其所有的數(shù)據(jù)信息之后,轉(zhuǎn)向第i+1隊(duì)列所需的轉(zhuǎn)換時(shí)間長度;

vi(n)：第i隊(duì)列發(fā)送完其中所包含的數(shù)據(jù)信息所需的時(shí)間長度;

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

ηj(vi)：表示在vi(n)這段時(shí)間內(nèi)加入第j隊(duì)列所有數(shù)據(jù)信息.

2.3 系統(tǒng)的性能分析

2.3.1 兩隊(duì)列的非對(duì)稱門限服務(wù)

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

由此得狀態(tài)變量在tn+1時(shí)刻的概率母函數(shù)為：

對(duì)式(4)和式(5)求一階偏導(dǎo)可得：

其中,g1(1),g2(2)分別表示隊(duì)列1的平均排隊(duì)隊(duì)長,隊(duì)列2的平均排隊(duì)隊(duì)長. 系統(tǒng)的平均查詢周期是指同一個(gè)站點(diǎn)被系統(tǒng)服務(wù)器兩次查詢?cè)L問之間的時(shí)間差的統(tǒng)計(jì)平均值,由轉(zhuǎn)換時(shí)間以及服務(wù)時(shí)間組成,通過計(jì)算得到其表達(dá)式為：

2.3.2 兩隊(duì)列非對(duì)稱完全服務(wù)

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

對(duì)式(9),(10)都進(jìn)行一階偏導(dǎo)可得

平均查詢周期為

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

3 多隊(duì)列非對(duì)稱模型

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

3.1 多隊(duì)列非對(duì)稱門限和完全服務(wù)

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

狀態(tài)變量在tn+1時(shí)刻的概率母函數(shù)為：

多隊(duì)列非對(duì)稱完全服務(wù)在tn+1時(shí)刻滿足的系統(tǒng)方程為：

則狀態(tài)變量在tn+1時(shí)刻的概率母函數(shù)為：

3.2 系統(tǒng)的特性分析

設(shè)定在tn時(shí)刻第i隊(duì)列發(fā)送數(shù)據(jù)信息時(shí),第j隊(duì)列緩存區(qū)中平均存儲(chǔ)的數(shù)據(jù)信息為：

計(jì)算得到第i隊(duì)列使用非對(duì)稱門限服務(wù)時(shí)的平均排隊(duì)隊(duì)長為[10]：

計(jì)算得到第i隊(duì)列在接受非對(duì)稱完全服務(wù)時(shí)的平均排隊(duì)隊(duì)長為：

通過理論計(jì)算得到多隊(duì)列非對(duì)稱門限服務(wù)和完全服務(wù)系統(tǒng)的平均查詢周期的表達(dá)式均為：

4 仿真實(shí)驗(yàn)及性能分析

根據(jù)以上所建立的非對(duì)稱門限、完全服務(wù)的系統(tǒng)模型,并基于下面的工作條件進(jìn)行數(shù)值計(jì)算和仿真實(shí)驗(yàn)．

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

(2) 任一時(shí)隙內(nèi)進(jìn)入各隊(duì)列的數(shù)據(jù)信息都滿足Poisson分布;

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

圖2 隊(duì)列1中到達(dá)率與平均排隊(duì)隊(duì)長的關(guān)系

圖3 隊(duì)列2中到達(dá)率與平均排隊(duì)隊(duì)長的關(guān)系

5 無線傳感器網(wǎng)絡(luò)中輪詢服務(wù)的設(shè)計(jì)

在無線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)非對(duì)稱的輪詢服務(wù),我們將選擇由加州伯克利分校根據(jù)無線傳感器網(wǎng)絡(luò)的特點(diǎn)專門為其設(shè)計(jì)并實(shí)現(xiàn)的Tiny0S嵌入式操作系統(tǒng)作為軟件平臺(tái)[10,11]. 在硬件平臺(tái)的選擇上,我們選擇cc2538cb來作為傳感器節(jié)點(diǎn). 測試過程中將設(shè)定一個(gè)節(jié)點(diǎn)作為匯聚節(jié)點(diǎn)來充當(dāng)服務(wù)器,負(fù)責(zé)對(duì)其他多個(gè)子節(jié)點(diǎn)進(jìn)行服務(wù). 每個(gè)子節(jié)點(diǎn)在未接受服務(wù)之前,一直處于睡眠偵聽的狀態(tài),當(dāng)接收到來自于服務(wù)器的信標(biāo)幀時(shí),就會(huì)被喚醒,此時(shí)就會(huì)選擇門限服務(wù)或完全服務(wù)的方式對(duì)對(duì)數(shù)據(jù)包進(jìn)行發(fā)送. 在無線傳感器網(wǎng)絡(luò)的應(yīng)用中,我們可以根據(jù)此前分析得到兩種非對(duì)稱服務(wù)的性能差異去選擇一種合適的服務(wù),因?yàn)樵跀?shù)據(jù)業(yè)務(wù)量較大時(shí),完全服務(wù)系統(tǒng)的公平性和服務(wù)質(zhì)量較差,此時(shí)就可以去選擇門限服務(wù)的方式.

節(jié)點(diǎn)程序主要用到的組件有main組件,led燈組件LedC,時(shí)鐘組件TimeC,IPStackC組件,還有StaticIPAddressTosIdC和UdpSocket組件,組件之間的連接關(guān)系如下圖9所示.

圖4 服務(wù)時(shí)間與平均排隊(duì)隊(duì)長的關(guān)系

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

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

6 結(jié)論

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

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

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

圖9 組件的連接關(guān)系

1 楊志軍,趙東風(fēng),丁洪偉,等. 兩級(jí)優(yōu)先級(jí)控制輪詢系統(tǒng)研究. 電子學(xué)報(bào),2009,37(7)：1452-1456.

2 楊志軍,丁洪偉,陳傳龍. 完全服務(wù)和門限服務(wù)兩級(jí)輪詢系統(tǒng)E(x)特性分析. 電子學(xué)報(bào),2014,42(4)：774-778.

3 楊志軍. 兩級(jí)優(yōu)先級(jí)控制輪詢系統(tǒng)理論及應(yīng)用研究[博士學(xué)位論文]. 昆明：云南大學(xué),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 趙東風(fēng),鄭蘇民. 周期查詢式門限服務(wù)排隊(duì)系統(tǒng)中信息分組的延遲分析. 通信學(xué)報(bào),1994,15(2)：18-23.

9 趙東風(fēng),鄭蘇民. 查詢式完全服務(wù)排隊(duì)模型分析. 電子學(xué)報(bào),1994,22(5)：102-107.

10 李遠(yuǎn)英,王正萬. 基于ZigBee技術(shù)的無線傳感數(shù)據(jù)采集網(wǎng)絡(luò)研究與應(yīng)用. 數(shù)字技術(shù)與應(yīng)用,2015,(3)：29-30.

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

12 趙東風(fēng),李必海,鄭蘇民. 周期查詢式限定服務(wù)排隊(duì)系統(tǒng)研究. 電子科學(xué)學(xué)刊,1997,19(1)：44-49.

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