并行調(diào)度兩級輪詢控制系統(tǒng)分析研究

楊志軍 孫洋洋

摘 ?要： 為了保證系統(tǒng)公平性不受損害，文中提出中心站點采用門限服務，普通站點采用并行調(diào)度完全服務的兩級優(yōu)先級輪詢控制系統(tǒng)模型。通過馬爾科夫鏈與概率母函數(shù)相結(jié)合的方法對模型的平均排隊隊長、平均等待時間等重要參數(shù)進行解析。經(jīng)仿真得出，模擬仿真值與理論值誤差較小，近似相等，表明模型理論分析合理正確。數(shù)值結(jié)果對比表明，模型區(qū)分網(wǎng)絡業(yè)務高低優(yōu)先級的性能優(yōu)良，且普通站點工作效率得以提高，從而保證了系統(tǒng)公平性。

關鍵詞： 輪詢控制系統(tǒng); 理論分析; 門限服務; 并行調(diào)度; 平均排隊隊長; 平均等待時間

中圖分類號： TN911?34 ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）12?0016?05

Abstract： A two?level priority polling control system model with the central site using the threshold service， and the ordinary sites using the parallel scheduling full service is proposed in this paper to prevent the system′s fairness from damage. The method of combining the Markov chain with the probability generating function is adopted to analyze the model′s important parameters such as average queue length and average waiting time. The simulation results show that the simulation values have only small errors and are approximately equal to theoretical values， indicating that the theoretical analysis of the model is reasonable and correct. The comparison of the numerical results show that the model has a good performance in distinguishing the high and low priorities of network service， and the work efficiency of the ordinary sites is improved， which can ensure the fairness of the system.

Keywords： polling control system; theoretical analysis; threshold service; parallel scheduling; average queue length; average waiting time

0 ?引 ?言

無線傳感器網(wǎng)絡作為下一代的傳感器網(wǎng)絡，在人們生產(chǎn)生活中有著巨大的應用前景[1]。輪詢控制系統(tǒng)自從被研究和開發(fā)以來，因其靈活性和實用性廣泛應用于無線傳感器網(wǎng)絡中[2]。文獻[3?4]分別分析研究了輪詢控制系統(tǒng)在無線網(wǎng)絡以及Hadoop架構中的應用，文獻[5]研究了FPGA與輪詢控制模型相結(jié)合而應用于溫濕度采集系統(tǒng)。隨著物聯(lián)網(wǎng)、計算機網(wǎng)絡的快速發(fā)展，實際應用中對輪詢控制系統(tǒng)提出了更高的要求，比如信息傳輸過程中高低優(yōu)先級[6]的區(qū)分，一直都是研究的熱點問題。文獻[7]構建兩級模型即保證中心站點優(yōu)先級又避免了對普通站點空閑查詢，可是這樣大大降低了系統(tǒng)靈活性，增加了系統(tǒng)實際操作的復雜度。文獻[8]研究了中心站點采用完全服務，普通站點采用門限服務的兩級輪詢模型系統(tǒng)，可是并沒有分析平均等待時間這一重要系統(tǒng)參數(shù)。輪詢服務系統(tǒng)中服務器服務完成當前站點后再服務下一個站點時要耗費一個站點之間的轉(zhuǎn)換時間，而根據(jù)并行[9]調(diào)度原理，就是在服務當前站點的同時查詢下一個需要服務的站點，這樣系統(tǒng)不再損耗單獨的轉(zhuǎn)換時間。

針對以上分析過程出現(xiàn)的問題，提出中心站點采用門限服務，普通站點采用并行調(diào)度完全服務的混合兩級輪詢控制系統(tǒng)模型，既能把站點的高低優(yōu)先級區(qū)別開來，又能提高系統(tǒng)公平性。采用并行控制方式減少了轉(zhuǎn)換時間，提高了系統(tǒng)工作效率和資源利用率。本文利用概率母函數(shù)以及嵌入式馬爾科夫鏈[10]的方法深入分析了系統(tǒng)各個重要特性參數(shù)，仿真模擬值與理論計算值誤差較小，表明了模型構建的合理性以及數(shù)學理論分析推導的正確性。

1 ?系統(tǒng)模型

1.1 ?模型原理分析

輪詢系統(tǒng)模型如圖1所示。該系統(tǒng)由一個中心站點h，一個服務器和N個普通站點構成。普通站點用并行調(diào)度完全服務策略傳輸?shù)蛢?yōu)先級的信息分組，中心站點用門限服務機制發(fā)送高優(yōu)先級的信息分組。系統(tǒng)工作的基本原理為：首先服務器服務中心站點按門限方式進行，當中心站點服務完成后，服務器采用并行調(diào)度完全服務策略對[i]號普通站點進行服務，通過并行處理，就是在服務中心站點的同時查詢[i]號普通站點，所以中心站點服務完成后立即開始對[i]號普通站點進行服務，對[i]號普通站點服務完成后，經(jīng)過一個轉(zhuǎn)換時間再服務中心站點;然后采用并行調(diào)度服務[i+1]號普通站點，即[h→i→h→i+1…h(huán)→N→h]。

圖1 ?輪詢系統(tǒng)模型

該系統(tǒng)采用兩級輪詢混合式的服務控制機制，可以讓中心站點獲得更多的服務時間，實現(xiàn)了中心站點與普通站點之間的優(yōu)先級區(qū)分;而普通站點采用并行完全服務方式保證了系統(tǒng)公平性，提升了系統(tǒng)工作效率和資源利用率。

1.2 ?變量定義

1） 任何時刻進入各站點的信息量服從泊松過程，其分布的概率母函數(shù)、均值、方差分別為[Ai（zi）]，[λ=A′（1）]，[σλ2=A"（1）+λ-λ2]，中心站點分布為[Ah（zh）]，[λh=A′h（1）] 以及[σ2λh=A″h（1）+λh-λ2h]。

2） 服務一個信息分組所耗費的時間服從同分布的概率分布，其分布的概率母函數(shù)、均值、方差分別為[Bi（zi）]，[β=B′1]，[σ2β=B"（1）+β-β2]，中心站點為[Bh（zh）]，[βh=β′h1]以及[δ2βh=B″h（1）+βh-β2h]。

3） 服務器從普通站點到中心站點的轉(zhuǎn)換時間服從獨立、同分布的概率分布，其分布的概率母函數(shù)、均值、方差分別為[Ri（zi）]，[γ=R′（1）]和[σ2γ=R"（1）+γ-γ2]。

[μi（n）]：[i]號普通站點完成服務后，轉(zhuǎn)換到中心站點的時間損耗。

[vi（n）]：服務器服務[i]號普通站點所需要的時間。

[vh（n*）]：服務器服務中心站點所需要的時間。

[μj（μi）] ：在[μi（n）]時間內(nèi)到達第[j]個站點的數(shù)據(jù)信息分組個數(shù)。

[ηj（vi）]：在[vi（n）]時間內(nèi)進入第[j]個站點的數(shù)據(jù)信息分組個數(shù)。

[ηj（vh）]：在[vh（n*）]時間內(nèi)進入第[j]個站點的數(shù)據(jù)信息分組個數(shù)。

1.3 ?概率母函數(shù)

假定在[tn]時刻[i]號普通站點[（i=1，2，…，N）]接收服務，當[i]號普通站點的信息分組服務完成后，在[tn+1]時刻服務器轉(zhuǎn)去服務中心站點。

定義隨機變量[ξi（n）]為[i]號普通站點[（i=1，2，…，N）]在[tn]時刻其緩存的數(shù)據(jù)信息分組的個數(shù)，則在[tn]時刻的狀態(tài)可表示為[[ξ1（n），ξ2（n），…，ξN（n）]]，隨機變量[ξh（n）]為中心站點在[tn+1]時刻其緩存的數(shù)據(jù)信息分組的個數(shù)，在[tn+1]時刻系統(tǒng)的狀態(tài)可表示為：[ξ1（n+1），ξ2（n+1），…，ξN（n+1）]

因為輪詢系統(tǒng)的站點個數(shù)相對固定，輪詢開始時，系統(tǒng)的狀態(tài)是可數(shù)的，嵌入式馬爾科夫鏈由離散時間可數(shù)狀態(tài)變量組成，當系統(tǒng)處于穩(wěn)定時，就構成了不可約、齊次、非周期的馬爾科夫過程，并且穩(wěn)態(tài)分布唯一。穩(wěn)態(tài)狀態(tài)下概率分布為：

1.7 ?系統(tǒng)平均查詢周期

2 ?仿真實驗

2.1 ?仿真實驗

根據(jù)以上對系統(tǒng)模型的深入解析進行仿真實驗，系統(tǒng)參數(shù)理論值為式（8）～式（10），式（16）～式（19）。站點中的信息分組個數(shù)以[λi]為均值的隨機泊松數(shù)來模擬。

1） 由中心站點轉(zhuǎn)向普通站點采用并行調(diào)度方式，無轉(zhuǎn)換查詢時間;

2） 系統(tǒng)穩(wěn)定條件為[（Nρ+ρh）<1];

3） 系統(tǒng)各仿真參數(shù)標注如圖2～圖7所示。

圖2 ?平均排隊隊長與負載關系

圖3 ?平均查詢周期與負載關系

2.2 ?結(jié)果分析

首先圖2～圖7表明模擬仿真結(jié)果與理論計算結(jié)果誤差較小，近似相等，說明所提系統(tǒng)的模型建立以及理論分析正確可靠。進一步對各個仿真圖分析可知：

1） 圖2～圖5反映了平均排隊隊長、平均查詢周期、吞吐量和平均等待時間與系統(tǒng)負載的正相關關系，都隨著負載的增加呈增大趨勢，顯示出系統(tǒng)的正確合理性。這是因為在站點個數(shù)N一定的情況下，負載的增加造成到達率[λ]的增加，因此系統(tǒng)平均排隊隊長，平均查詢周期，吞吐量和平均等待時間也會相應合理增加。

圖4 ?吞吐量與負載關系

圖5 ?平均等待時間與負載關系

圖6 ?平均等待時間比較 （一）

圖7 ?平均等待時間比較 （二）

2） 由圖2，圖3，圖5可以看出：普通站點的平均排隊隊長、平均查詢周期和平均等待時間遠遠大于中心站點，普通站點與中心站點得到很好區(qū)分，顯示出了系統(tǒng)區(qū)分網(wǎng)絡業(yè)務優(yōu)先級的優(yōu)良性能。

3） 由圖4可以看出，系統(tǒng)吞吐量隨著負載的增大而增大，同時由圖2，圖3，圖5可以看出，負載的增加又會造成系統(tǒng)平均排隊隊長、平均查詢周期和平均等待時間的增加，在實際應用中增加系統(tǒng)吞吐量時，還應該把系統(tǒng)平均等待時間，平均排隊隊長以及平均查詢周期作為限制條件加以約束。

4） 圖6與圖7分別是本模型系統(tǒng)與單一的門限服務和完全服務對比圖，以平均等待時間作為比較對象，可以看出本模型系統(tǒng)的普通站點和中心站點的平均等待時間都小于門限服務和完全服務，這是因為本模型采用并行調(diào)度的控制方式，減少了系統(tǒng)站點之間的轉(zhuǎn)換時間，提高了普通站點和中心站點的工作效率。

3 ?結(jié) ?語

本文提出的區(qū)分高低優(yōu)先級的輪詢控制系統(tǒng)模型，不僅能夠很好區(qū)分中心站點與普通站點的高低優(yōu)先級，同時還進一步提高了系統(tǒng)工作效率。主要在于通過增加中心站點的服務時間保證了其高優(yōu)先級傳輸服務，通過并行處理，節(jié)約了系統(tǒng)站點之間的轉(zhuǎn)換時間，提高了系統(tǒng)的資源利用率和工作效率。為了保障系統(tǒng)公平性輪詢控制策略采用無競爭控制的周期性方式且服務質(zhì)量（Quantity of Service，QoS）優(yōu)良，是計算機網(wǎng)絡MAC層的重要的控制策略。三網(wǎng)融合的重要接入部分是高性能同軸電纜網(wǎng)絡（High Performance Network Over Coax，HINOC），而HINOC的MAC協(xié)議研究對于加快三網(wǎng)融合的發(fā)展至關重要，本模型能很好地區(qū)分網(wǎng)絡業(yè)務優(yōu)先級，相信對于三網(wǎng)融合的發(fā)展必將做出突出貢獻[12]。

參考文獻

[1] 王寶珠，李蓬勃，齊存康，等.一種工業(yè)無線自適應退避競爭接入方法的研究[J].現(xiàn)代電子技術，2017，40（19）：28?32.

WANG Baozhu， LI Pengbo， QI Cunkang， et al. Study on an adaptive keeping?off competition access method of industrial wireless networks [J]. Modern electronics technique， 2017， 40（19）： 28?32.

[2] 趙繼軍，谷志群，薛亮，等.WSN中層次型拓撲控制與網(wǎng)絡資源配置聯(lián)合設計方法[J].自動化學報，2015，41（3）：646?660.

ZHAO Jijun， GU Zhiqun， XUE Liang， et al. A joint design method of hierarchical topology control and network resource allocation for wireless sensor networks [J]. Acta automatica sinica， 2015， 41（3）： 646?660.

[3] 夏漢鑄，劉輝元.無線Mesh網(wǎng)絡中基于公平的EDCA算法研究[J].現(xiàn)代電子技術，2014，37（7）：21?24.

XIA Hanzhu， LIU Huiyuan. Research on fairness?based EDCA algorithm in wireless Mesh networks [J]. Modern electronics technique， 2014， 37（7）： 21?24.

[4] 曾俊.一種基于Hadoop架構的并行挖掘算法研究[J].現(xiàn)代電子技術，2018，41（1）：117?119.

ZENG Jun. A parallel mining algorithm based on Hadoop architecture [J]. Modern electronics technique， 2018， 41（1）： 117?119.

[5] 于艷艷，黃倩，王磊，等.基于FPGA的動態(tài)優(yōu)先輪詢策略在Ad Hoc網(wǎng)絡數(shù)據(jù)采集系統(tǒng)中的研究與應用[J].云南大學學報（自然科學版），2014，36（1）：16?20.

YU Yanyan， HUANG Qian， WANG Lei， et al. The research and application of dynamic priority polling strategy based on FPGA in Ad Hoc network data acquisition system [J]. Journal of Yunnan University （Natural sciences edition）， 2014， 36（1）： 16?20.

[6] 杜松江，張佳.基于數(shù)據(jù)塊優(yōu)先級的無線多跳Mesh網(wǎng)絡數(shù)據(jù)分發(fā)算法[J].現(xiàn)代電子技術，2016，39（21）：40?43.

DU Songjiang， ZHANG Jia. Wireless multi?hop mesh network data distribution algorithm based on data block priority [J]. Modern electronics technique， 2016， 39（21）： 40?43.

[7] 官錚，楊志軍，何敏，等.依托站點狀態(tài)的兩級輪詢控制系統(tǒng)時延特性分析[J].自動化學報，2016，42（8）：1207?1214.

GUAN Zheng， YANG Zhijun， HE Min， et al. Study on the delay performance of station dependent two?level polling systems [J]. Acta automatica sinica， 2016， 42（8）： 1207?1214.

[8] 楊志軍，丁洪偉，陳傳龍.完全服務和門限服務兩級輪詢系統(tǒng)E（x）特性分析[J].電子學報，2014，42（4）：774?778.

YANG Zhijun， DING Hongwei， CHEN Chuanlong. Research on E（x） characteristics of two?class polling system of exhaustive?gated service [J]. Acta electronica sinica， 2014， 42（4）： 774?778.

[9] ZHANG W F， YANG Z J， GUAN Z， et al. Research on priority differentiated polling mechanism with limited service in wireless sensor networks： extended abstract [C]// Proceedings of 5th International Conference on Communications and Broadband Networking. Bali： ACM， 2017： 12?18.

[10] 余淼，胡占義.高階馬爾科夫隨機場及其在場景理解中的應用[J].自動化學報，2015，41（7）：1213?1234.

YU Miao， HU Zhanyi. Higher?order Markov random fields and their applications in scene understanding [J]. Acta automatica sinica， 2015， 41（7）： 1213?1234.

[11] 王紅艷，劉暐.基于穩(wěn)定鏈路的WSNs拓撲優(yōu)化算法設計及仿真研究[J].現(xiàn)代電子技術，2017，40（19）：45?48.

WANG Hongyan， LIU Wei. Design and simulation of stable link based topology optimization algorithm for WSNs [J]. Modern electronics technique， 2017， 40（19）： 45?48.

[12] 朱龍正.三網(wǎng)融合中寬帶接入輪詢控制機制研究[D].昆明：云南大學，2016.

ZHU Longzheng. Research on broadband access polling control mechanism in triple play [D]. Kunming： Yunnan University， 2016.