Research on Distributed Computing WSN Task Scheduling in Intelligent Building Indoor Environment*

GAO Zhijun，WANG Hongyu，WANG Xin，HAN Zhonghua

(1.School of Information and Communication Engineering，Dalian University of Technology，Dalian Liaoning 116024，China; 2.School of Information and Control Engineering，Shenyang Jianzhu University，Shenyang 110168，China)

Research on Distributed Computing WSN Task Scheduling in Intelligent Building Indoor Environment*

GAO Zhijun1，2，WANG Hongyu1*，WANG Xin2，HAN Zhonghua2

(1.School of Information and Communication Engineering，Dalian University of Technology，Dalian Liaoning 116024，China; 2.School of Information and Control Engineering，Shenyang Jianzhu University，Shenyang 110168，China)

To solve the dynamic task scheduling problems of distribution parallel computing in intelligent building，a structure model of WSN based on distributed CPS conception is proposed.The task allocation strategy based on the computability complexity and dynamic scheduling algorithm based on the task scheduling strategy are designed.Firstly，the task is decomposed to a number of sub-tasks，Multi-band Turing machine is applied to the input of the task.The directed acyclic graph is formed though the calculation of the appropriate selected nodes.Second，task scheduling sequence tables are formed and tasks are processed in sequence through scheduling priority.The experimental results show that this strategy reduces the communication time and waiting time of running tasks in WSN.Meanwhile，the success rate of the task scheduler is improved and the efficiency of the system is optimized effectively.

WSN;task scheduling;turing machines;the directed acyclic graph;intelligent building

随着信息技术的飞速发展和人们对智能建筑室内环境综合需求的不断提升，智能建筑室内环境中环境舒适度监测、火灾信号检测和能耗检测与节能等多任务调度及大规模计算问题已成为制约智能建筑发展的瓶颈，基于信息物理融合系统CPS(Cyber-Physical System)［1-2］分布式可计算WSN的出现，为人们解决这一问题提供了全新的方法，因而受到学术界的广泛关注。

信息物理融合系统(CPS)是重要而且全新的研究领域，随着相关研讨会的相继召开和专家的不断深入研究，CPS得到了越来越多的青睐。2007年7月，美国总统科学技术顾问委员会(PCAST)在题为《挑战下的领先——竞争世界中的信息技术研发》的报告中将CPS列为八大关键信息技术的首位［1］。CPS在智能交通系统、医疗设备系统、能源保护、环境监控、航空航天软件、关键基础设施(电力、水)、普适自适应通信、节能建筑、生物系统等领域具有广阔的应用前景。而高性能的计算能力是CPS实时性、准确性应用的保证，分布式技术的发展为高性能的CPS系统提供了可能，保证了系统的可靠性。所谓分布式，主要指数据分布和计算分布，数据分布是指数据分散的存储在不同计算机中;计算分布则是将计算任务分配给不同的计算节点进行分布处理，实现快速准确的分布式管理，保证系统的可靠性，任务优化调度方法尤为重要。

一直以来多任务调度是调度理论中的经典问题，主要分为静态任务调度和动态任务调度的算法［3-6］。现如今基于CPS的WSN是分布、异构且复杂的系统，静态调度算法以不太适用，对动态调度算法的研究趋于主流，例如最小完成时间算法MCT［7］(Minimum Completion Time)、遗传算法［8］，最小最早完成时间算法(Min-min算法)［9］，Mehdi.N.A等人提出了MCT算法［10］，该方法简单实用，易实现，但由于其以将每个任务分配给任务完成时间最早的资源为目的，会造成一些任务未被分配到最佳资源的问题，分配成功率较低;熊聪聪等人将遗传算法用于任务调度中，但容易出现早熟收敛、搜索效率低、收敛性能差以及搜索时间过长等现象，缺乏灵活性; Panda Sanjaya Kumar等人提出了Min-min算法，在任务调度次序的选择上仅仅以完成时间为标准，负载过度集中在某些节点上，造成高性能节点超负荷运转，而其余性能较低的节点的处理能力却没有得到很好的利用的缺点。

本文在构建智能建筑室内环境下分布式可计算WSN模型的基础上，主要针对负责任务调度的WSN网络进行了建模，采用分布式技术的思想，将任务调度分为任务分配和资源调度两个方面，在任务分配的的过程中按照执行时间、资源利用率等方面进行任务的调度，找寻任务被合理调度的过程，实现了更高的任务调度成功率，有效降低了任务总体完成时间。

1 WSN系统设计

通常，建筑室内环境下WSN处理任务包括滤波、计算、分析、处理、融合等，因此本文WSN系统的任务处理部分采用分布式技术，它将传感器节点中参与计算的计算节点连成整体，其计算节点的处理能力远大于传统无线网络，实现安全资源管理、合理任务分配以及快速结果输出，并提供各种资源环境接口。本文所设计的WSN系统结构图如图1所示。传感器网络感知建筑的物理环境数据信息以及用户终端的任务请求命令均发送到信息中心，再由WSN网路进行数据分析以及任务的处理，通过执行器网络控制建筑物理环境。其中本文的任务调度设计主要由传感器计算节点来完成。

图1 建筑智能环境分布式可计算WSN系统结构图

2 WSN分布式的任务调度架构设计

针对WSN系统结构图中的传感器计算节点部分，本文主要采用分布式的任务调度策略，任务调度结构图如图2所示。任务调度主要分为两个部分:任务分配和资源调度。一个任务会根据不同的数据约束关系和可计算复杂性等要求分解成若干个子任务，任务分配的目的是解决任务的分解问题以及将分解后的若干子任务分配到合适的计算节点上的过程，选择任务或子任务在哪些计算节点上执行，任务调度则涉及到在某一个计算节点上，任务将按怎样的顺序被合理的调度执行的过程。任务分配决策必须在任务调度执行之前作出决策。

图2 分布式任务调度结构图

2.1 基于可计算复杂性的任务分配设计

WSN系统是智能建筑的发展方向，是实现智慧生活的保证［11-13］。本文针对WSN系统结构图中的WSN网路部分的任务分配过程，主要对任务分配器进行了设计。1936年图灵(Turing)提出著名的图灵机判据:“如果一个函数能用图灵机来计算，则这个函数是可计算的。”［14-15］。采用图灵机输入任务，并根据图灵可计算复杂性的思想对任务进行合理化的分配，实现智能建筑环境WSN系统任务的快速、准确的处理能力。由于任务的多样性，采用多带图灵机模型(如图3)进行。

图3 多带图灵机

多带图灵机M:关系系统为M=(Q，Σ，Γ，δ，B，F)，有限状态集Q;输入符号的有穷集Σ;带符号集Γ，满足Σ⊆Γ;转移函数δ:Q×Γk→Q×Γk×{L，R，S}k，则δ(q，X1，…，Xk)=(p，Y1，…，Yk，D1，…Dk)，表示机器当前状态为q，当前读写头读出的符号为X，当转移状态到p时，用Y代替X，读写头向Di(i=1…k)方向移动，若Di=S，表示停留在原地不动;空白符号B∈Γ-Σ，开始时空白出现在除输入的所有单元中;终结状态的集合F⊆Q，当控制达到此集合中任意状态时，计算过程结束。

多带图灵机M的初始状态为q0(q0∈Q)，设输入任务为w，M接受w的计算时间被记为tM(w)，WSN系统中的每个参与的计算节点中，都存在一个上述的多带图灵机服务器，多带图灵机服务器根据时间复杂性TM(n)=max{tM(w):|w|=n，w∈L(M)}将任务分解成若干个子任务，分解的同时，其他计算节点根据本身的计算能力和计算资源与子任务进行匹配，任务分配有向无环图DGA(Direct A-cyclic Graph)如图4所示，如此反复的任务、子任务的分解和变换，从而完成任务。

图4 任务分配有向无环拓扑图

任务提交到WSN网络的同时，计算节点中的多带图灵机服务器通过可计算时间复杂性的判断，将一个需要分布式技术解决的任务划分为若干个子任务，其他网络中参与计算的计算节点中的多带图灵机服务器会与子任务进行匹配，并通过任务调度算法将子任务调度到适合其快速计算的计算节点中进行计算，如若本计算节点无法完成计算，则将任务继续向下一级分解和匹配，但每个计算节点的计算过程可能需要其不定的上N级有效结果，形成有向无环图，得其最终结果。

2.2 基于动态调度算法的任务调度设计

在满足一定的性能指标和依赖关系的前提下，将任务(子任务)调度到满足其条件的计算节点中，同时安排计算节点可并行执行的任务的执行次序，满足执行时间最短。本设计中，针对WSN系统结构图中网路部分的任务调度过程，采用动态调度算法进行任务调度设计，程序流程图如图5所示。

图5 动态调度算法程序流程图

输入:一个物理环境发出的任务信息或用户提出的任务信息(G，t)，其中:任务模型G，时间限制t;

输出:最优调度列表f。

假设有向无环拓扑图模型为G=(V，E，p，W，s，D，R)，节点集V={1，2，…，n};弧集E={(i1，j1)，…，(im，jm)};非负向量p为计算节点权重向量，元素pi代表计算节点i的时间开销;非负矩阵W为弧权重矩阵，元素wk，j表示弧(k，j)的时间开销;si表示计算节点Vi的运算速度;Di，j表示需要从任务(子任务)ti传送到tj的数据量、di表示任务(子任务)ti的计算量; Ri，j表示计算节点Vi到Vj的数据信息传输速率。

第1步:检查就绪列表是否为空，如果不为空，继续;否则结束任务调度;

第2步:查询任务，获取输入任务的有向无环图DGA参数。

第3步:随机生成的调度列表f，求解过程中用于记录最新的调度列表。

第4步:通过式(1)计算任务的优先级程度，如果任务ti的优先级最高，则更新调度列表;如果无最高优先级，按照原调度列表运行。

其中:Mp为处理单元计算能力中值，Mc为链路传输能力中值。

第5步:判断是否满足|f|最小，如果满足则结束;否则返回步骤4。

pi，j为执行代价，表示任务ti在处理器节点Vj上的执行时间，pi，j=di/sj+pj;Wi，j为通信代价，假定任务ti运行在处理器节点Vf上，tj运行在处理器Vt上，处理器Vf和Vt之间的通信时间，Wi，j=pf+Di，j/Rf，t。

定义:调度成功率为规定时间条件之下正确处理任务数与需处理的总任务数之比。

在任务调度的过程中采用动态调度算法，以运行时间最短为目标，在满足带宽约束的条件下，经过根据优先级制定的调度列表进行任务的调度，在以可计算复杂度的准确任务分配的基础上，缩短任务的执行之间。

3 实验与分析

在智能建筑室内环境的分布式WSN网络中，根据可计算复杂性的思想进行任务分配，再采用动态调度算法进行任务调度，并通过MATLAB仿真实验验证其优越性。

结合本文的分布式任务管理模型，利用MATLAB进行仿真实验。针对智能建筑室内环境资源任务的特点，设置20种传感器普通节点，其中有10个计算节点，随机产生30、50、60、100和150个任务，实验仿真统计次数均为1 000。资源的参数设置如表1所示。

表1 资源参数

本文对算法运行时间和任务的完成时间进行了MATLAB仿真实验。图6所示为算法运行时间与任务数关系，由图6可以更直观的看出，随着任务数量的增加，各算法运行时间均所增加，当任务数为60时，MCT、遗传算法和Min-min 3种算法运行时间分别为270 ms、255 ms和240 ms，而本文算法运行时间为230 ms;当任务数增至100时，本文算法运行时间为270 ms，仍明显低于其他3种算法运行时间，这主要是因为MCT算法易于出现部分任务未被分配到最佳资源;Min-min算法则产生负载过度集中在某些节点上，造成高性能节点超负荷运转问题;遗传算法容易出现早熟收敛、搜索效率低;而本文算法中采用在任务分配的的过程中按照执行时间、资源利用率等方面进行任务的调度，有效克服了以上算法所存在的缺陷，大大缩短了算法运行时间，进而显现出本文算法在运行时间上的优势。

图6 算法运行时间比较图

通过与MCT算法、遗传算法和Min-min算法3种较为经典的任务调度算法的比较，仿真得出图7的任务完成时间比较图。采用本文算法，任务完成时间明显小于其他3种任务调度算法，这主要是本文在调度算法中分成任务分配和资源调度两个部分，再将复杂任务分解为若干个子任务，使其复杂度简化，并利用优先级调度机制。随着任务数量的增加，在缩短任务完成时间方面优势越来越明显。

在任务调度成功率方面，本文算法较MCT算法、遗传算法和Min-min算法体现了优越性，如图8所示。

图7 任务完成时间比较图

图8 任务调度成功率比较图

从图8中可以看出，与MCT算法、遗传算法和Min-min算法3种算法相比，本文算法以任务优先级为标准进行调度，任务均可以在其有效期间内完成，成功率可达到90%以上，而MCT算法、遗传算法和Min-min算法3种算法都比较注重任务完成时间短的任务调度，当计算节点空闲时才开始执行完成时间长但重要率高的任务，导致其最终计算结果失效，成功率低。在网络环境复杂繁多的WSN中，本文算法具有非常好的应用前景。

由以上仿真实验可以看出，相对于MCT算法、遗传算法和Min-min算法3种比较经典的任务调度算法，在智能建筑室内环境分布式WSN网络中，采用任务分配和任务调度独立工作但结果又相互融合的方式进行任务调度的方案是可行的，既可以加快任务处理的速度，而且还可以增加任务调度成功率，同时在任务分配和处理的同时，系统的资源库不断更新，不仅加快了未来数据访问速度和任务的处理速度，而且通过图灵机服务器的记忆功能，还实现了系统的自主学习能力。

4 结语

本文在智能建筑室内环境分布式可计算WSN系统中，采用分布式技术的思想，利用可计算复杂性和动态调度算法进行任务的分配、调度和处理工作，可以将各种高性能服务器和计算节点等有机的结合起来，实现分布式的资源高度共享。实验结果表明本文所提出的调度机制可有效的提高整个任务调度的总体完成时间和任务调度的成功率，与MCT、遗传算法和Min-min 3种算法相比，本文算法具有较低的算法运行时间，可有效解决智能建筑室内环境下多任务调度的复杂性及大规模计算问题。

［1］王小乐，黄宏斌，邓苏.处理顺序约束的信息物理融合系统静态任务表调度算法［J］.自动化学报，2012，38(11):1870 -1879.

［2］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26(1):116-121.

［3］孔玉静，侯鑫，华尔天，等.基于BP神经网络的无线传感器网络路由协议的研究［J］.传感技术学报，2013，26(2):246 -251.

［4］王中杰，谢璐璐.信息物理融合系统研究综述［J］.自动化学报，2011，37(10):1157-1166.

［5］Mehdi N A，Mamat Ali，Amer Ali.Minimum Completion Time for Power-Aware Scheduling in Cloud Computing［C］//Proceedings of the 4th International Conference on Developments in Systems Engineering，2011:484-489.

［6］熊聪聪，冯龙.云计算中基于遗传算法的任务调度算法研究［J］.华中科技大学学报，2012(40):1-4.

［7］Panda Sanjaya Kumar，Bhoi Sourav Kumar，Khilar Pabitra Mohan. A Semi-Interquartile min-min max-min(SIM2)Approach for Grid Task Scheduling［J］.Advances in Intelligent Systems and Computing，2013:415-421.

［8］Yang J D，Xu H，Pan L，et al.Task Scheduling Using Bayesian Optimization Algorithm for Heterogeneous Computing Environments［J］.Applied Soft Computing，2011，11(4):3297-3310.

［9］Lee Y C，Zomaya A Y.A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(9):1215-1223.

［10］孟宪福，王敏.基于改进免疫克隆选择的对等网络任务调度机制［J］.计算机集成制造系统，2009，15(9):1795-1802.

［11］Tang Xiaoyong，Li Kenli.A Stochastic Scheduling Algorithm for Precedence Constrained Tasks on Grid［J］.Future Generation Computer Systems，2011，27(8):1083-1091.

［12］王金良，苏志强.网络使用研究进展——影响因素、后果变量及影响机制［J］.西南大学学报，2012，38(3):82-90.

［13］谭朋柳，舒坚.一种信息-物理融合系统体系结构［J］.计算机研究与发展，2010，47:312-316.

［14］宋文，牟行军.计算的模型:图灵机与Petri网［J］.西华大学学报，2013(3):1-6.

［15］王宁，屈国栋.一种基于Eclipse RCP的任务管理系统设计与实现［J］.微计算机信息，2011，27(4):119-121.

高治军(1978-)，男，大连理工大学博士研究生生，主要从事无线传感器网络技术与应用、无线网络技术、智能建筑等方面的研究，gzj1267@sjzu.edu.cn;

王洪玉(1968-)，男，大连理工大学教授、博士生导师，IEEE会员，中国电子学会高级会员，主要从事无线定位技术、移动自组织网络技术、移动通信先进物理层技术等方向的研究，whyu@ dlut.edu.cn。

智能建筑室内环境分布式可计算WSN任务调度研究*

高治军1，2，王洪玉1*，王鑫2，韩忠华2
(1.大连理工大学信息与通信工程学院，辽宁大连116024;2.沈阳建筑大学信息与控制工程学院，沈阳110168)

针对智能建筑室内环境下并行计算的动态任务调度问题，构建了基于分布式CPS思想的无线传感器网络(WSN)模型，并分别设计了基于可计算复杂性的任务分配策略和基于动态调度算法的任务调度策略。通过先将任务分配成若干个子任务，采用多带图灵机输入任务，由合适的计算节点进行计算，形成有向无环图，再按调度优先级排列任务，形成任务调度序列表，依序处理任务，从而达到了将任务分配、调度和执行相结合的目的。实验结果表明该策略可有效减少智能建筑室内环境分布式可计算WSN分布运行时任务之间的通讯时间和等待时间，同时提高了任务调度的成功率，最终优化系统的运行效率。

WSN;任务调度;图灵机;有向无环图;智能建筑

TP393

A

1004－1699(2014)03－0378－05

2013-10-10修改日期:2014-03-02

C:6150P

10.3969/j.issn.1004－1699.2014.03.020

项目来源:国家自然科学基金项目(61172058);住房与城乡建设部研究开发项目(2009-K9-25)