楊志軍 孫洋洋

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

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

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

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

1 ?系統(tǒng)模型

1.1 ?模型原理分析

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

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

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

1.2 ?變量定義

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

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

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

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

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

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

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

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

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

1.3 ?概率母函數(shù)

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

定義隨機變量[ξ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)變量組成，當(dāng)系統(tǒng)處于穩(wěn)定時，就構(gòu)成了不可約、齊次、非周期的馬爾科夫過程，并且穩(wěn)態(tài)分布唯一。穩(wěn)態(tài)狀態(tài)下概率分布為：

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

2 ?仿真實驗

2.1 ?仿真實驗

根據(jù)以上對系統(tǒng)模型的深入解析進(jìn)行仿真實驗，系統(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ù)標(biāo)注如圖2～圖7所示。

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

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

2.2 ?結(jié)果分析

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

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

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

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

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

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

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

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

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

3 ?結(jié) ?語

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

參考文獻(xiàn)

[1] 王寶珠，李蓬勃，齊存康，等.一種工業(yè)無線自適應(yī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].自動化學(xué)報，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的動態(tài)優(yōu)先輪詢策略在Ad Hoc網(wǎng)絡(luò)數(shù)據(jù)采集系統(tǒng)中的研究與應(yīng)用[J].云南大學(xué)學(xué)報（自然科學(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)先級的無線多跳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] 官錚，楊志軍，何敏，等.依托站點狀態(tài)的兩級輪詢控制系統(tǒng)時延特性分析[J].自動化學(xué)報，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ù)兩級輪詢系統(tǒng)E（x）特性分析[J].電子學(xué)報，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] 余淼，胡占義.高階馬爾科夫隨機場及其在場景理解中的應(yīng)用[J].自動化學(xué)報，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].現(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)融合中寬帶接入輪詢控制機制研究[D].昆明：云南大學(xué)，2016.

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