并行调度两级轮询控制系统分析研究

杨志军 孙洋洋

摘  要： 为了保证系统公平性不受损害，文中提出中心站点采用门限服务，普通站点采用并行调度完全服务的两级优先级轮询控制系统模型。通过马尔科夫链与概率母函数相结合的方法对模型的平均排队队长、平均等待时间等重要参数进行解析。经仿真得出，模拟仿真值与理论值误差较小，近似相等，表明模型理论分析合理正确。数值结果对比表明，模型区分网络业务高低优先级的性能优良，且普通站点工作效率得以提高，从而保证了系统公平性。

关键词： 轮询控制系统; 理论分析; 门限服务; 并行调度; 平均排队队长; 平均等待时间

中图分类号： 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  引  言

无线传感器网络作为下一代的传感器网络，在人们生产生活中有着巨大的应用前景[1]。轮询控制系统自从被研究和开发以来，因其灵活性和实用性广泛应用于无线传感器网络中[2]。文献[3?4]分别分析研究了轮询控制系统在无线网络以及Hadoop架构中的应用，文献[5]研究了FPGA与轮询控制模型相结合而应用于温湿度采集系统。随着物联网、计算机网络的快速发展，实际应用中对轮询控制系统提出了更高的要求，比如信息传输过程中高低优先级[6]的区分，一直都是研究的热点问题。文献[7]构建两级模型即保证中心站点优先级又避免了对普通站点空闲查询，可是这样大大降低了系统灵活性，增加了系统实际操作的复杂度。文献[8]研究了中心站点采用完全服务，普通站点采用门限服务的两级轮询模型系统，可是并没有分析平均等待时间这一重要系统参数。轮询服务系统中服务器服务完成当前站点后再服务下一个站点时要耗费一个站点之间的转换时间，而根据并行[9]调度原理，就是在服务当前站点的同时查询下一个需要服务的站点，这样系统不再损耗单独的转换时间。

针对以上分析过程出现的问题，提出中心站点采用门限服务，普通站点采用并行调度完全服务的混合两级轮询控制系统模型，既能把站点的高低优先级区别开来，又能提高系统公平性。采用并行控制方式减少了转换时间，提高了系统工作效率和资源利用率。本文利用概率母函数以及嵌入式马尔科夫链[10]的方法深入分析了系统各个重要特性参数，仿真模拟值与理论计算值误差较小，表明了模型构建的合理性以及数学理论分析推导的正确性。

1  系统模型

1.1  模型原理分析

轮询系统模型如图1所示。该系统由一个中心站点h，一个服务器和N个普通站点构成。普通站点用并行调度完全服务策略传输低优先级的信息分组，中心站点用门限服务机制发送高优先级的信息分组。系统工作的基本原理为：首先服务器服务中心站点按门限方式进行，當中心站点服务完成后，服务器采用并行调度完全服务策略对[i]号普通站点进行服务，通过并行处理，就是在服务中心站点的同时查询[i]号普通站点，所以中心站点服务完成后立即开始对[i]号普通站点进行服务，对[i]号普通站点服务完成后，经过一个转换时间再服务中心站点;然后采用并行调度服务[i+1]号普通站点，即[h→i→h→i+1…h→N→h]。

图1  轮询系统模型

该系统采用两级轮询混合式的服务控制机制，可以让中心站点获得更多的服务时间，实现了中心站点与普通站点之间的优先级区分;而普通站点采用并行完全服务方式保证了系统公平性，提升了系统工作效率和资源利用率。

1.2  變量定义

1） 任何时刻进入各站点的信息量服从泊松过程，其分布的概率母函数、均值、方差分别为[Ai（zi）]，[λ=A′（1）]，[σλ2=A"（1）+λ-λ2]，中心站点分布为[Ah（zh）]，[λh=A′h（1）] 以及[σ2λh=A″h（1）+λh-λ2h]。

2） 服务一个信息分组所耗费的时间服从同分布的概率分布，其分布的概率母函数、均值、方差分别为[Bi（zi）]，[β=B′1]，[σ2β=B"（1）+β-β2]，中心站点为[Bh（zh）]，[βh=β′h1]以及[δ2βh=B″h（1）+βh-β2h]。

3） 服务器从普通站点到中心站点的转换时间服从独立、同分布的概率分布，其分布的概率母函数、均值、方差分别为[Ri（zi）]，[γ=R′（1）]和[σ2γ=R"（1）+γ-γ2]。

[μi（n）]：[i]号普通站点完成服务后，转换到中心站点的时间损耗。

[vi（n）]：服务器服务[i]号普通站点所需要的时间。

[vh（n*）]：服务器服务中心站点所需要的时间。

[μj（μi）] ：在[μi（n）]时间内到达第[j]个站点的数据信息分组个数。

[ηj（vi）]：在[vi（n）]时间内进入第[j]个站点的数据信息分组个数。

[ηj（vh）]：在[vh（n*）]时间内进入第[j]个站点的数据信息分组个数。

1.3  概率母函数

假定在[tn]时刻[i]号普通站点[（i=1，2，…，N）]接收服务，当[i]号普通站点的信息分组服务完成后，在[tn+1]时刻服务器转去服务中心站点。

定义随机变量[ξi（n）]为[i]号普通站点[（i=1，2，…，N）]在[tn]时刻其缓存的数据信息分组的个数，则在[tn]时刻的状态可表示为[[ξ1（n），ξ2（n），…，ξN（n）]]，随机变量[ξh（n）]为中心站点在[tn+1]时刻其缓存的数据信息分组的个数，在[tn+1]时刻系统的状态可表示为：[ξ1（n+1），ξ2（n+1），…，ξN（n+1）]

因为轮询系统的站点个数相对固定，轮询开始时，系统的状态是可数的，嵌入式马尔科夫链由离散时间可数状态变量组成，当系统处于稳定时，就构成了不可约、齐次、非周期的马尔科夫过程，并且稳态分布唯一。稳态状态下概率分布为：

1.7  系统平均查询周期

2  仿真实验

2.1  仿真实验

根据以上对系统模型的深入解析进行仿真实验，系统参数理论值为式（8）～式（10），式（16）～式（19）。站点中的信息分组个数以[λi]为均值的随机泊松数来模拟。

1） 由中心站点转向普通站点采用并行调度方式，无转换查询时间;

2） 系统稳定条件为[（Nρ+ρh）<1];

3） 系统各仿真参数标注如图2～图7所示。

图2  平均排队队长与负载关系

图3  平均查询周期与负载关系

2.2  结果分析

首先图2～图7表明模拟仿真结果与理论计算结果误差较小，近似相等，说明所提系统的模型建立以及理论分析正确可靠。进一步对各个仿真图分析可知：

1） 图2～图5反映了平均排队队长、平均查询周期、吞吐量和平均等待时间与系统负载的正相关关系，都随着负载的增加呈增大趋势，显示出系统的正确合理性。这是因为在站点个数N一定的情况下，负载的增加造成到达率[λ]的增加，因此系统平均排队队长，平均查询周期，吞吐量和平均等待时间也会相应合理增加。

图4  吞吐量与负载关系

图5  平均等待时间与负载关系

图6  平均等待时间比较 （一）

图7  平均等待时间比较 （二）

2） 由图2，图3，图5可以看出：普通站点的平均排队队长、平均查询周期和平均等待时间远远大于中心站点，普通站点与中心站点得到很好区分，显示出了系统区分网络业务优先级的优良性能。

3） 由图4可以看出，系统吞吐量随着负载的增大而增大，同时由图2，图3，图5可以看出，负载的增加又会造成系统平均排队队长、平均查询周期和平均等待时间的增加，在实际应用中增加系统吞吐量时，还应该把系统平均等待时间，平均排队队长以及平均查询周期作为限制条件加以约束。

4） 图6与图7分别是本模型系统与单一的门限服务和完全服务对比图，以平均等待时间作为比较对象，可以看出本模型系统的普通站点和中心站点的平均等待时间都小于门限服务和完全服务，这是因为本模型采用并行调度的控制方式，减少了系统站点之间的转换时间，提高了普通站点和中心站点的工作效率。

3  结  语

本文提出的区分高低优先级的轮询控制系统模型，不仅能够很好区分中心站点与普通站点的高低优先级，同时还进一步提高了系统工作效率。主要在于通过增加中心站点的服务时间保证了其高优先级传输服务，通过并行处理，节约了系统站点之间的转换时间，提高了系统的资源利用率和工作效率。为了保障系统公平性轮询控制策略采用无竞争控制的周期性方式且服务质量（Quantity of Service，QoS）优良，是计算机网络MAC层的重要的控制策略。三网融合的重要接入部分是高性能同轴电缆网络（High Performance Network Over Coax，HINOC），而HINOC的MAC协议研究对于加快三网融合的发展至关重要，本模型能很好地区分网络业务优先级，相信对于三网融合的发展必将做出突出贡献[12]。

参考文献

[1] 王宝珠，李蓬勃，齐存康，等.一种工业无线自适应退避竞争接入方法的研究[J].现代电子技术，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中层次型拓扑控制与网络资源配置联合设计方法[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网络中基于公平的EDCA算法研究[J].现代电子技术，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].现代电子技术，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的动态优先轮询策略在Ad Hoc网络数据采集系统中的研究与应用[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] 杜松江，张佳.基于数据块优先级的无线多跳Mesh网络数据分发算法[J].现代电子技术，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] 官铮，杨志军，何敏，等.依托站点状态的两级轮询控制系统时延特性分析[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] 杨志军，丁洪伟，陈传龙.完全服务和门限服务两级轮询系统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] 王红艳，刘暐.基于稳定链路的WSNs拓扑优化算法设计及仿真研究[J].现代电子技术，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] 朱龙正.三网融合中宽带接入轮询控制机制研究[D].昆明：云南大学，2016.

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