1、Research on distributed computing WSN task scheduling in intelligent building indoor environmentAbstract：For addressing the tasks complexity and completing the large-scale compution in intelligent environment building ,a structure model of WSN based on distributed CPS conception is formed. A task al
2、location strategy based on the computability complexity and a dynamic scheduling algorithm based on the task scheduling strategy are designed. First, according to Multi-band Turing machine task is decomposed the directed acyclic graph by namely a number of sub-tasks, then selecting a appropriate com
3、puting nodes calculate.Second, the tasks in each computing node are arranged through scheduling priority,task scheduling sequence tables are formed, and tasks are processed in sequence.The experimental results show that this strategy reduces the communication costs among tasks of distributed running
4、-time waiting times, meanwhile improving the success rate of the task Scheduler is improved, the final optimized efficiency of the system,finally operational efficiency of the system is optimized.Key words:WSN; Turing machines; The directed acyclic graph;Task scheduling; Intelligent building智能建筑室内环境
5、分布式可计算WSN任务调度研究摘要：针对智能建筑室内环境下任务的复杂性及大规模计算问题，本文构建了基于分布式CPS思想的无线传感器网络（WSN）模型，并分别设计了基于可计算复杂性的任务分配策略和基于动态调度算法的任务调度策略。通过先将任务分配成若干个子任务，采用多带图灵机输入任务，由合适的计算节点进行计算，形成有向无环图，再按调度优先级排列任务，形成任务调度序列表，依序处理任务，从而达到了将任务分配、调度和执行相结合的目的。实验结果表明该策略可有效减少智能建筑室内环境分布式可计算WSN分布运行时任务之间的通讯开销和等待时间，同时提高了任务调度的成功率，最终优化系统的运行效率。关键词：WSN；图
6、灵机；有向无环图；任务调度；智能建筑9随着信息技术的飞速发展和人们对智能建筑室内环境综合需求的不断提升，智能建筑室内环境中环境舒适度监测、火灾信号检测和能耗检测与节能等多任务调度及大规模计算问题已成为制约智能建筑发展的瓶颈，基于信息物理融合系统（Cyber-Physical System，CPS）1,2分布式可计算WSN的出现，为人们解决这一问题提供了全新的方法，因而受到学术界的广泛关注。信息物理融合系统（CPS）是重要而且全新的研究领域，随着相关研讨会的相继召开和专家的不断深入研究，CPS得到了越来越多的青睐。2007年7月，美国总统科学技术顾问委员会(PCAST)在题为挑战下的领先竞争世界
7、中的信息技术研发的报告中将CPS列为八大关键信息技术的首位1。CPS在智能交通系统、医疗设备系统、能源保护、环境监控、航空航天软件、关键基础设施（电力、水）、普适自适应通信、节能建筑、生物系统等领域具有广阔的应用前景。而高性能的计算能力是CPS实时性、准确性应用的保证，分布式技术的发展为高性能的CPS系统提供了可能，保证了系统的可靠性。所谓分布式，主要指数据分布和计算分布，数据分布是指数据分散的存储在不同计算机中；计算分布则是将计算任务分配给不同的计算节点进行分布处理，实现快速准确的分布式管理，保证系统的可靠性，任务优化调度方法尤为重要。一直以来多任务调度是调度理论中的经典问题，主要分为静态任
8、务调度和动态任务调度的算法3-6。现如今基于CPS的WSN是分布、异构且复杂的系统，静态调度算法以不太适用，对动态调度算法的研究趋于主流，例如最小完成时间算法MCT7（Minimum Completion Time）、遗传算法8，最小最早完成时间算法（Min-min算法）9，Mehdi.N.A等人研究的MCT算法10简单实用，易实现，但由于其以将每个任务分配给任务完成时间最早的资源为目的，会造成一些任务未被分配到最佳资源的问题，分配成功率较低；熊聪聪等人研究的遗传算法，则容易出现早熟收敛、搜索效率低、收敛性能差以及搜索时间过长等现象，缺乏灵活性；Panda Sanjaya Kumar等人研究的
9、Min-min算法，在任务调度次序的选择上仅仅以完成时间为标准，负载过度集中在某些节点上，造成高性能节点超负荷运转，而其余性能较低的节点的处理能力却没有得到很好的利用的缺点。本文在构建智能建筑室内环境下分布式可计算WSN模型的基础上，主要针对负责任务调度的WSN网络进行了建模，采用分布式技术的思想，将任务调度分为任务分配和资源调度两个方面，在任务分配的的过程中按照执行时间、资源利用率等方面进行任务的调度，找寻任务被合理调度的的过程，实现了更高的任务调度成功率，有效降低了任务总体完成时间。1 WSN系统设计本文WSN系统的任务处理部分采用分布式技术，它将传感器节点中参与计算的计算节点连成整体，其
10、计算节点的处理能力远大于传统无线网络，实现安全资源管理、合理任务分配以及快速结果输出，并提供各种资源环境接口。本文所设计的WSN系统结构图如图1所示。传感器网络感知建筑的物理环境数据信息以及用户终端的任务请求命令均发送到信息中心，再由WSN网路进行数据分析以及任务的处理，通过执行器网络控制建筑物理环境。其中本文的任务调度设计主要由传感器计算节点来完成。图1 建筑智能环境分布式可计算WSN系统结构图2 WSN网络分布式的任务调度架构设计针对WSN系统结构图中的传感器计算节点部分，本文主要采用分布式的任务调度策略，任务调度结构图如图2所示。任务调度主要分为两个部分：任务分配和资源调度。一个任务会根
11、据不同的数据约束关系和可计算复杂性等要求分解成若干个子任务，任务分配的目的是解决任务的分解问题以及将分解后的若干子任务分配到合适的计算节点上的过程，选择任务或子任务在哪些计算节点上执行，任务调度则涉及到在某一个计算节点上，任务将按怎样的顺序被合理的调度执行的过程。任务分配决策必须在任务调度执行之前作出决策。图2 分布式任务调度结构图2.1 基于可计算复杂性的任务分配设计WSN系统是智能建筑的发展方向，是实现智慧生活的保证11-13。本文针对WSN系统结构图中的WSN网路部分的任务分配过程，主要对任务分配器进行了设计。1936年图灵(Turnig)提出著名的图灵机判据：“如果一个函数能用图灵机来
12、计算，则这个函数是可计算的。”14,15。采用图灵机输入任务，并根据图灵可计算复杂性的思想对任务进行合理化的分配，实现智能建筑环境WSN系统任务的快速、准确的处理能力。由于任务的多样性，采用多带图灵机模型（如图3）进行。多带图灵机M：关系系统为，有限状态集Q；输入符号的有穷集；带符号集，满足；转移函数，则图3 多带图灵机，表示机器当前状态为q，当前读写头读出的符号为X，当转移状态到p时，用Y代替X，读写头向（）方向移动,若，表示停留在原地不动；空白符号，开始时空白出现在除输入的所有单元中；终结状态的集合，当控制达到此集合中任意状态时，计算过程结束。 多带图灵机M的初始状态为，设输入任务为w，M
13、接受w的计算时间被记为，WSN系统中的每个参与的计算节点中，都存在一个上述的多带图灵机服务器，多带图灵机服务器根据时间复杂性将任务分解成若干个子任务，分解的同时，其他计算节点根据本身的计算能力和计算资源与子任务进行匹配，任务分配有向无环图DGA（Direct Acyclic Graph）如图4所示，如此反复的任务、子任务的分解和变换，从而完成任务。图4 任务分配有向无环拓扑图任务提交到WSN网络的同时，计算节点中的多带图灵机服务器通过可计算时间复杂性的判断，将一个需要分布式技术解决的任务划分为若干个子任务，其他网络中参与计算的计算节点中的多带图灵机服务器会与子任务进行匹配，并通过任务调度算法将
14、子任务调度到适合其快速计算的计算节点中进行计算，如若本计算节点无法完成计算，则将任务继续向下一级分解和匹配，但每个计算节点的计算过程可能需要其不定的上N级有效结果，形成有向无环图，得其最终结果。2.2 基于动态调度算法的任务调度设计在满足一定的性能指标和依赖关系的前提下，将任务（子任务）调度到满足其条件的计算节点中，同时安排计算节点可并行执行的任务的执行次序，满足执行时间最短。本设计中，针对WSN系统结构图中网路部分的任务调度过程，采用动态调度算法进行任务调度设计，程序流程图如图5所示。输入：一个物理环境发出的任务信息或用户提出的任务信息，其中：任务模型G，时间限制t；输出：最优调度列表f。假
15、设有向无环拓扑图模型为，节点集；弧集；非负向量为计算节点权重向量，元素代表计算节点的时间开销；非负矩阵为弧权重矩阵，元素表示弧的时间开销；表示计算节点的运算速度；表示需要从任务（子任务）传送到的数据量、表示任务（子任务）的计算量；表示计算节点到的数据信息传输速率。第1步：检查就绪列表是否为空，如果不为空，继续；否则结束任务调度；第2步：查询任务，获取输入任务的有向无环图DGA参数。第3步：随机生成的调度列表f，求解过程中用于记录最新的调度列表。第4步：通过式（1）计算任务的优先级程度，如果任务的优先级最高，则更新调度列表；如果无最高优先级，按照原调度列表运行。 （1）其中：为处理单元计算能力中
16、值，为链路传输能力中值。第5步：判断是否满足最小，如果满足则结束；否则返回步骤4。其中，表示任务的运行时间，即任务从起始节点开始计算到终止节点完成计算所经历的时间长度。为执行代价，表示任务在处理器节点上的执行时间，；为通信代价，假定任务运行在处理器节点上，运行在处理器上，处理器之间的通信时间，。 在任务调度的过程中采用动态调度算法，以运行时间最短为目标，在满足带宽约束的条件下，经过根据优先级制定的调度列表进行任务的调度，在以可计算复杂度的准确任务分配的基础上，缩短任务的执行之间。3 实验与分析在智能建筑室内环境的分布式WSN网络中，根据可计算复杂性的思想进行任务分配，再采用动态调度算法进行任务
17、调度，并通过MATLAB仿真实验验证其优越性。结合本文的分布式任务管理模型，利用MATLAB进行仿真实验。针对智能建筑室内环境资源任务的特点，设置20种传感器普通节点，其中有10个计算节点，随机产生30、50、60、100和150个任务。资源的参数设置如表1所示。图5 动态调度算法程序流程图本文对算法运行时间和任务的完成时间进行了MATLAB仿真实验。图6所示为算法运行时间与任务数关系，由图6可以更直观的看出，随着任务数量的增加，各算法运行时间均所增加，当任务数为60时，MCT、遗传算法和Min-min三种算法运行时间分别为270ms、255ms和240ms，而本文算法运行时间为230ms；当
18、任务数增至100时，本文算法运行时间为270ms，仍明显低于其他三种算法运行时间，进而显现出本文算法在运行时间上的优势。表1 资源参数ID处理器数/个处理能力MIPS通信速度（Mb/s）平均负载率14515200.0082524377300.0066334377200.0058742377400.0089452380200.0074766410200.00894716410400.00671816410500.0071692380100.00606104410200.00877图6 算法运行时间比较图通过与MCT算法、遗传算法和Min-min算法三种较为经典的任务调度算法的比较，得出图7的任务
19、完成时间比较图。采用本文算法，任务完成时间明显小于其它三种任务调度算法，并随着任务数量的增加，在缩短任务完成时间方面优势越来越明显。 图7 任务完成时间比较图在任务调度成功率方面，本文算法较MCT算法、遗传算法和Min-min算法体现了优越性，如图8所示。图8 任务调度成功率比较图从图8中可以看出，与MCT算法、遗传算法和Min-min算法三种算法相比，本文算法以任务优先级为标准进行调度，任务均可以在其有效期间内完成，成功率可达到90%以上，而MCT算法、遗传算法和Min-min算法三种算法都比较注重任务完成时间短的任务调度，当计算节点空闲时才开始执行完成时间长但重要率高的任务，导致其最终计算
20、结果失效，成功率低。在网络环境复杂繁多的WSN中，本文算法具有非常好的应用前景。 由以上仿真实验可以看出，相对于MCT算法、遗传算法和Min-min算法三种比较经典的任务调度算法，在智能建筑室内环境分布式WSN网络中，采用任务分配和任务调度独立工作但结果又相互融合的方式进行任务调度的方案是可行的，既可以加快任务处理的速度，而且还可以增加任务调度成功率，同时在任务分配和处理的同时，系统的资源库不断更新，不仅加快了未来数据访问速度和任务的处理速度，而且通过图灵机服务器的记忆功能，还实现了系统的自主学习能力。4 结语本文在智能建筑室内环境分布式可计算WSN系统中，采用分布式技术的思想，利用可计算复杂
21、性和动态调度算法进行任务的分配、调度和处理工作，可以将各种高性能服务器和计算节点等有机的结合起来，实现分布式的资源高度共享。实验结果表明本文所提出的调度机制可有效的提高整个任务调度的总体完成时间和任务调度的成功率，与MCT、遗传算法和Min-min三种算法相比，本文算法具有较低的算法运行时间，可有效解决智能建筑室内环境下多任务调度的复杂性及大规模计算问题。参考文献1Presidents Council of Advisers on Science and Technology(PCAST),USA.Leadership Under Challenge:Information Technolog
22、y R&D in a Competitive World:An Assessment of the Federal Networking and Information Technology R&D Program .2何积丰.Cyber-physical SystemsJ.中国计算机学会通讯,2010,6(1):25-29.3张栋,吴春明.分布式系统中资源分配的一致性算法综述J.信息工程大学学报,2009,10(1):37-40.4王中杰,谢璐璐.信息物理融合系统研究综述J.自动化学报,2011,37(10): 1157-1166.5Mehdi.N.A,Mamat Ali,Amer Ali.
23、Minimumcompletion time for power-awarescheduling in cloud computingC.Procee-dings-4th International Conference onDevelopments in Systems Engineering,2011: 484-489.6熊聪聪,冯龙.云计算中基于遗传算法的任务调度算法研究J.华中科技大学学报,2012(40):1-4.7Panda Sanjaya Kumar,Bhoi Sourav Kumar, Khilar Pabitra Mohan.A semi-interquartile min-
24、min max-min(SIM2)approach for grid task schedulingJ.Advances in Intelligent Systems and Computing,2013:415-421.8Yang J D,Xu H,Pan L,Jia P F.Task scheduling using Bayesian optimization algorithm for heterogeneous computing environments. Applied Soft Computing, 2011,11(4):3297-3310.9Lee Y C, Zomaya A
25、Y.A novel state transition method for metaheuristic-based scheduling in heterogeneous computing systems. IEEE Transactions on Parallel and Distributed Systems, 2008, 19 (9): 1215-1223.10孟宪福,王敏.基于改进免疫克隆选择的对等网络任务调度机制J.计算机集成制造系统，2009，15(9)：1795-1802.11Tang Xiaoyong,Li Kenli.A stochastic scheduling algo
26、rithm for precedence constrained tasks on Grid. 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（3）：1-6.15王宁,屈国栋.一种基于Eclipse RCP的任务管理系统设计与实现J.微计算机信息,2011,27(4)：119-121.
