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

楊志軍 孫洋洋

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

關(guān)鍵詞： 輪詢控制系統(tǒng); 理論分析; 門限服務(wù); 并行調(diào)度; 平均排隊(duì)隊(duì)長(zhǎng); 平均等待時(shí)間

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

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

1 ?系統(tǒng)模型

1.1 ?模型原理分析

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

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

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

1.2 ?變量定義

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

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

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

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

[vi（n）]：服務(wù)器服務(wù)[i]號(hào)普通站點(diǎn)所需要的時(shí)間。

[vh（n*）]：服務(wù)器服務(wù)中心站點(diǎn)所需要的時(shí)間。

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

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

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

1.3 ?概率母函數(shù)

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

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

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

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

2 ?仿真實(shí)驗(yàn)

2.1 ?仿真實(shí)驗(yàn)

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

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

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

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

圖2 ?平均排隊(duì)隊(duì)長(zhǎng)與負(fù)載關(guān)系

圖3 ?平均查詢周期與負(fù)載關(guān)系

2.2 ?結(jié)果分析

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

1） 圖2～圖5反映了平均排隊(duì)隊(duì)長(zhǎng)、平均查詢周期、吞吐量和平均等待時(shí)間與系統(tǒng)負(fù)載的正相關(guān)關(guān)系，都隨著負(fù)載的增加呈增大趨勢(shì)，顯示出系統(tǒng)的正確合理性。這是因?yàn)樵谡军c(diǎn)個(gè)數(shù)N一定的情況下，負(fù)載的增加造成到達(dá)率[λ]的增加，因此系統(tǒng)平均排隊(duì)隊(duì)長(zhǎng)，平均查詢周期，吞吐量和平均等待時(shí)間也會(huì)相應(yīng)合理增加。

圖4 ?吞吐量與負(fù)載關(guān)系

圖5 ?平均等待時(shí)間與負(fù)載關(guān)系

圖6 ?平均等待時(shí)間比較 （一）

圖7 ?平均等待時(shí)間比較 （二）

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

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

4） 圖6與圖7分別是本模型系統(tǒng)與單一的門限服務(wù)和完全服務(wù)對(duì)比圖，以平均等待時(shí)間作為比較對(duì)象，可以看出本模型系統(tǒng)的普通站點(diǎn)和中心站點(diǎn)的平均等待時(shí)間都小于門限服務(wù)和完全服務(wù)，這是因?yàn)楸灸Ｐ筒捎貌⑿姓{(diào)度的控制方式，減少了系統(tǒng)站點(diǎn)之間的轉(zhuǎn)換時(shí)間，提高了普通站點(diǎn)和中心站點(diǎn)的工作效率。

3 ?結(jié) ?語

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

參考文獻(xiàn)

[1] 王寶珠，李蓬勃，齊存康，等.一種工業(yè)無線自適應(yīng)退避競(jìng)爭(zhēng)接入方法的研究[J].現(xiàn)代電子技術(shù)，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中層次型拓?fù)淇刂婆c網(wǎng)絡(luò)資源配置聯(lián)合設(shè)計(jì)方法[J].自動(dòng)化學(xué)報(bào)，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)絡(luò)中基于公平的EDCA算法研究[J].現(xiàn)代電子技術(shù)，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架構(gòu)的并行挖掘算法研究[J].現(xiàn)代電子技術(shù)，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的動(dòng)態(tài)優(yōu)先輪詢策略在Ad Hoc網(wǎng)絡(luò)數(shù)據(jù)采集系統(tǒng)中的研究與應(yīng)用[J].云南大學(xué)學(xué)報(bào)（自然科學(xué)版），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)先級(jí)的無線多跳Mesh網(wǎng)絡(luò)數(shù)據(jù)分發(fā)算法[J].現(xiàn)代電子技術(shù)，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] 官錚，楊志軍，何敏，等.依托站點(diǎn)狀態(tài)的兩級(jí)輪詢控制系統(tǒng)時(shí)延特性分析[J].自動(dòng)化學(xué)報(bào)，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] 楊志軍，丁洪偉，陳傳龍.完全服務(wù)和門限服務(wù)兩級(jí)輪詢系統(tǒng)E（x）特性分析[J].電子學(xué)報(bào)，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ī)場(chǎng)及其在場(chǎng)景理解中的應(yīng)用[J].自動(dòng)化學(xué)報(bào)，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拓?fù)鋬?yōu)化算法設(shè)計(jì)及仿真研究[J].現(xiàn)代電子技術(shù)，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)融合中寬帶接入輪詢控制機(jī)制研究[D].昆明：云南大學(xué)，2016.

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