论文部分内容阅读
摘要：随着视频侦查手段在公安部门的日益推广，为公安部门提供破案线索支持的视频智能分析平台也日益受到重视。任务调度机制作为视频智能分析平台的关键技术，必须保证视频分析任务在不同计算节点间调度的合理性和有效性。论文提出了一种新的视频分析平台上的任务主动调度机制，减少了任务调度开销，保证了任务总执行时间，提升了视频分析平台的视频分析效率。
关键词：视频分析 任务调度 主动调度
1 概述
随着当前智慧城市、平安城市等相关建设在各地的大力推广，各地都建立了一定层次的视频监控网络，为保证城市安全、维护社会稳定起到了重要的作用。视频侦查手段在公安部门的案件侦查、社会管理等业务中的重要性也日益突出，越来越受到各地公安部门的重视。然而随着视频监控网络建设的不断推进，公安部门在案件侦查过程中所需分析处理的案件视频越来越多，人工对案件视频进行分析的难度也越来越大。
航天长峰为提升公安部门的视频侦查水平，增进公安部门的侦查办案效率，建设了一套基于海量视频的事件轨迹快速检索平台。该平台通过多个进行视频分析的计算节点，对视频进行同步智能分析，为用户提供诸如视频智能摘要、目标智能检索的视频分析服务，大大缩短了公安民警人工观看视频的时间，在多地的使用中取得了良好的效果。
该视频分析平台稳定高效运行所面临的核心挑战就是如何响应用户提出的视频分析并发任务请求，并将其分配到合适的计算节点上加以分析，在用户期望的时间内向用户返回结果。也就是说，如何对视频分析任务实施合理的调度，形成视频分析平台的视频分析任务智能调度机制，是系统实现的一大关键技术。
本文通过对视频分析任务的特点加以分析，结合主动和被动调度思想，提出了一种新的任务调度机制，并在测试中验证了该机制的合理性和有效性。
2 视频分析任务的特点
观察视频分析任务的运行时间，可以发现视频分析任务所需的运行时间不确定性很高。其主要原因在于不同监控视频的分辨率、清晰度、目标数目等众多因素存在很大区别，而视频分析任务的执行时间受原始视频的影响很大。这就造成视频分析任务的时间很难预测，变化也很大。
记录50次对同样长度视频进行的视频分析任务的执行时间，结果如图1所示。
由以上结果可见，对同样长度视频进行的视频分析的时间分布相当随机，不确定性很高。
学术界过去对任务调度问题的研究主要集中于任务执行时间可以预测的情形[1]。例如LS、Min-Min等被动调度算法，它们都需要了解任务在计算节点上的预期计算时间，并基于此预期计算时间进行调度。然而从上面的分析可见，视频分析任务运行时间很难在事先确定，因此很难利用被动调度算法对视频分析任务进行有效的调度。而必须根据视频分析任务的实际情形，结合主动调度相关思想，提出创新的视频分析任务调度机制。
3 视频分析任务的调度机制
显然视频分析任务的调度机制应当保证在高并发、大任务量时将任务合理地分配到各个计算节点上。此时的任务调度既要保证任务在用户的预期执行时间内完成，即最小化任务的执行时间；也要保证不同计算节点的负载相对均衡，使得计算节点能够有效地完成视频分析任务；还要尽量减小任务调度自身的时间、网络等开销。
如前所述，视频分析任务很难在任务执行之前准确预测执行时间，也就导致视频分析平台难于利用被动调度相关算法进行任务调度。具体而言，当有大量任务同时到达时，视频分析平台很难由调度服务器自身决定应当将任务分配到哪一个计算节点上进行计算，而必须利用主动调度策略，由计算节点在空闲时向调度服务器申请任务，完成相关功能。
但同时也注意到当系统空闲时，在主动调度机制下，计算节点会占用大量网络资源向调度服务器请求任务[2]。这既造成了网络资源的浪费，也不利于系统的稳定、可靠运行。由于在系统不繁忙时，大量的计算节点空闲，偶然出现的任务总是会被分配到计算能力最强的节点上。为了在系统空闲时能够合理地减小调度开销，则可以引入被动调度机制，由调度服务器直接决定任务分配的计算节点。
基于上述分析，设计视频分析平台的任务调度机制如图2所示。
视频分析平台的任务调度机制的运行流程如下：
①视频分析平台以主动模式开始运行。此时，调度服务器的用户请求处理模块接收用户请求，将其缓存于自身的用户任务队列中。
②计算节点的状态监测模块开始运行后就不断跟踪每一个用户任务的处理，统计出计算节点的平均响应时间，并结合自身的CPU、内存和网络带宽的利用率以及网络可达性，周期性（如每秒1次）地计算自身的负载容量。
③计算节点的主动调度模块根据状态监测模块的决策规划，将自身的服务质量信息以及负载容量反馈给调度服务器的计算节点监测模块，主动向调度服务器发出请求，要求获得与其负载能力相当的视频分析任务。
④调度服务器的调度模块根据计算节点的运行状态，利用一定的调度算法决定应当分配给相应计算节点的视频分析任务。并将这些任务通过任务分发模块分发给对应的计算节点。
⑤计算节点在接收到视频分析任务后，利用自身的视频分析模块进行视频分析，并根据视频分析任务包含的任务来源等相关信息，直接将结果反馈给发出任务的用户。
⑥调度服务器始终监测所有计算节点的状态，当过去一段时间（如10分钟）内所有的计算节点都处于空闲状态，则通知所有计算节点转入被动调度模式。在被动模式下，计算节点的状态监测功能退化为简单的心跳功能，只在每隔较长的一段时间（如10分钟）时向调度服务器发送心跳确认在线。当调度服务器在被动调度模式下收到任务时，在计算节点中选取合适的计算节点进行处理，同时唤醒所有计算节点，将视频分析平台重新切入主动调度模式，即转入第1步。
可以看出，在上面的任务调度流程中，分别牵涉到被动模式下和主动模式下的任务调度算法，即在被动模式下如何选择合适的计算节点为新到来的视频分析任务服务，以及在主动模式下如何为请求任務的计算节点分配适当数目的任务。 首先讨论被动模式下的任务调度算法，由于此时所有计算节点都处于空闲状态，而调度服务器也刚刚接收到了新的视频分析任务，无论采取何种调度算法都不大可能对任务执行时间产生大的影响。因此可以在这时利用简单的MET调度算法[3]，即将任务调度到能够最快完成该任务的计算节点上。由于视频分析任务的不可预测性，这也就意味着该任务应当被调度到具有最高配置的计算节点上执行。
而视频分析平台在主动模式下的调度算法则可以采用主动调度模式下效果最好的TSS调度算法进行[3]。该算法可以不断调整分配给计算节点的任务块大小，在保证任务执行时间的前提下实现各计算节点间的负载均衡。
4 任务调度机制测试
本文为测试配置了8个计算节点，其中节点1-3使用Intel Core i5处理器，主频为3.0GHz；节点4-8使用Intel Core2处理器，主频为1.66GHz。在进行任务调度时，模拟100个视频分析任务供计算节点处理。为充分测试算法在不同情况下的调度可靠性，分别对计算节点数为2（取计算节点1、4参与计算）、4（取计算节点1、2、4、5参与计算）、8（取全部计算节点参与计算）这三种情况展开测试。
在仿真环境下对任务调度机制进行测试，并记录各个计算节点对任务的处理时间和由于通信、任务切换等因素造成的等待时间。同时也测试了单纯将任务平均分配到各个计算节点上这种最“差”的调度机制。为直观表明任务调度效果，以平均分配这一最“差”的调度机制形成的任务执行时间除以新的调度机制形成的任务执行时间，作为调度机制的加速比。由此绘制视频分析任务的加速比如图3所示。
■
图3 任务执行时间加速比
上述测试结果表明，本文提出的调度机制在多计算节点情况下，面对高并发的大量复杂计算任务，能够进行合理有效的任务调度，取得良好的调度效果。在计算节点越多时，调度效果越好，平均可以提升效率两倍左右。
参考文献：
[1]储雅，马廷淮，赵立成.云计算资源调度：策略与算法[J].计算机科学，2013，40（11）：8-13.
[2]金士尧，钱迎进，章文嵩，王晓川.主动与被动混合调度网络集群服务系统[J].计算机工程与科学.2009，31（1）：17-19.
[3]A.T.Chronopoulos，R.Andonie，M.Benche，D.Grosu.A Class of Loop Self-Scheduling for Heterogeneous Clusters[C]. Proceedings of the 2001 IEEE International Conference on Cluster Computing.2002：113-122.
基金項目：
浙江省科技厅重大科技专项重点工业项目（2013C01045）。
作者简介：
陆成刚（1973-），男，上海人，高级工程师，理学博士，智慧安居；
王安（1985-），男，江西抚州人，工程师，硕士，图像与信息处理；
王汗（1989-），男，江苏沭阳县人，硕士研究生在读，数字图像处理；
洪榛（1983-），男，浙江台州人，讲师，工学博士，智慧安居。
关键词：视频分析 任务调度 主动调度
1 概述
随着当前智慧城市、平安城市等相关建设在各地的大力推广，各地都建立了一定层次的视频监控网络，为保证城市安全、维护社会稳定起到了重要的作用。视频侦查手段在公安部门的案件侦查、社会管理等业务中的重要性也日益突出，越来越受到各地公安部门的重视。然而随着视频监控网络建设的不断推进，公安部门在案件侦查过程中所需分析处理的案件视频越来越多，人工对案件视频进行分析的难度也越来越大。
航天长峰为提升公安部门的视频侦查水平，增进公安部门的侦查办案效率，建设了一套基于海量视频的事件轨迹快速检索平台。该平台通过多个进行视频分析的计算节点，对视频进行同步智能分析，为用户提供诸如视频智能摘要、目标智能检索的视频分析服务，大大缩短了公安民警人工观看视频的时间，在多地的使用中取得了良好的效果。
该视频分析平台稳定高效运行所面临的核心挑战就是如何响应用户提出的视频分析并发任务请求，并将其分配到合适的计算节点上加以分析，在用户期望的时间内向用户返回结果。也就是说，如何对视频分析任务实施合理的调度，形成视频分析平台的视频分析任务智能调度机制，是系统实现的一大关键技术。
本文通过对视频分析任务的特点加以分析，结合主动和被动调度思想，提出了一种新的任务调度机制，并在测试中验证了该机制的合理性和有效性。
2 视频分析任务的特点
观察视频分析任务的运行时间，可以发现视频分析任务所需的运行时间不确定性很高。其主要原因在于不同监控视频的分辨率、清晰度、目标数目等众多因素存在很大区别，而视频分析任务的执行时间受原始视频的影响很大。这就造成视频分析任务的时间很难预测，变化也很大。
记录50次对同样长度视频进行的视频分析任务的执行时间，结果如图1所示。
由以上结果可见，对同样长度视频进行的视频分析的时间分布相当随机，不确定性很高。
学术界过去对任务调度问题的研究主要集中于任务执行时间可以预测的情形[1]。例如LS、Min-Min等被动调度算法，它们都需要了解任务在计算节点上的预期计算时间，并基于此预期计算时间进行调度。然而从上面的分析可见，视频分析任务运行时间很难在事先确定，因此很难利用被动调度算法对视频分析任务进行有效的调度。而必须根据视频分析任务的实际情形，结合主动调度相关思想，提出创新的视频分析任务调度机制。
3 视频分析任务的调度机制
显然视频分析任务的调度机制应当保证在高并发、大任务量时将任务合理地分配到各个计算节点上。此时的任务调度既要保证任务在用户的预期执行时间内完成，即最小化任务的执行时间；也要保证不同计算节点的负载相对均衡，使得计算节点能够有效地完成视频分析任务；还要尽量减小任务调度自身的时间、网络等开销。
如前所述，视频分析任务很难在任务执行之前准确预测执行时间，也就导致视频分析平台难于利用被动调度相关算法进行任务调度。具体而言，当有大量任务同时到达时，视频分析平台很难由调度服务器自身决定应当将任务分配到哪一个计算节点上进行计算，而必须利用主动调度策略，由计算节点在空闲时向调度服务器申请任务，完成相关功能。
但同时也注意到当系统空闲时，在主动调度机制下，计算节点会占用大量网络资源向调度服务器请求任务[2]。这既造成了网络资源的浪费，也不利于系统的稳定、可靠运行。由于在系统不繁忙时，大量的计算节点空闲，偶然出现的任务总是会被分配到计算能力最强的节点上。为了在系统空闲时能够合理地减小调度开销，则可以引入被动调度机制，由调度服务器直接决定任务分配的计算节点。
基于上述分析，设计视频分析平台的任务调度机制如图2所示。
视频分析平台的任务调度机制的运行流程如下：
①视频分析平台以主动模式开始运行。此时，调度服务器的用户请求处理模块接收用户请求，将其缓存于自身的用户任务队列中。
②计算节点的状态监测模块开始运行后就不断跟踪每一个用户任务的处理，统计出计算节点的平均响应时间，并结合自身的CPU、内存和网络带宽的利用率以及网络可达性，周期性（如每秒1次）地计算自身的负载容量。
③计算节点的主动调度模块根据状态监测模块的决策规划，将自身的服务质量信息以及负载容量反馈给调度服务器的计算节点监测模块，主动向调度服务器发出请求，要求获得与其负载能力相当的视频分析任务。
④调度服务器的调度模块根据计算节点的运行状态，利用一定的调度算法决定应当分配给相应计算节点的视频分析任务。并将这些任务通过任务分发模块分发给对应的计算节点。
⑤计算节点在接收到视频分析任务后，利用自身的视频分析模块进行视频分析，并根据视频分析任务包含的任务来源等相关信息，直接将结果反馈给发出任务的用户。
⑥调度服务器始终监测所有计算节点的状态，当过去一段时间（如10分钟）内所有的计算节点都处于空闲状态，则通知所有计算节点转入被动调度模式。在被动模式下，计算节点的状态监测功能退化为简单的心跳功能，只在每隔较长的一段时间（如10分钟）时向调度服务器发送心跳确认在线。当调度服务器在被动调度模式下收到任务时，在计算节点中选取合适的计算节点进行处理，同时唤醒所有计算节点，将视频分析平台重新切入主动调度模式，即转入第1步。
可以看出，在上面的任务调度流程中，分别牵涉到被动模式下和主动模式下的任务调度算法，即在被动模式下如何选择合适的计算节点为新到来的视频分析任务服务，以及在主动模式下如何为请求任務的计算节点分配适当数目的任务。 首先讨论被动模式下的任务调度算法，由于此时所有计算节点都处于空闲状态，而调度服务器也刚刚接收到了新的视频分析任务，无论采取何种调度算法都不大可能对任务执行时间产生大的影响。因此可以在这时利用简单的MET调度算法[3]，即将任务调度到能够最快完成该任务的计算节点上。由于视频分析任务的不可预测性，这也就意味着该任务应当被调度到具有最高配置的计算节点上执行。
而视频分析平台在主动模式下的调度算法则可以采用主动调度模式下效果最好的TSS调度算法进行[3]。该算法可以不断调整分配给计算节点的任务块大小，在保证任务执行时间的前提下实现各计算节点间的负载均衡。
4 任务调度机制测试
本文为测试配置了8个计算节点，其中节点1-3使用Intel Core i5处理器，主频为3.0GHz；节点4-8使用Intel Core2处理器，主频为1.66GHz。在进行任务调度时，模拟100个视频分析任务供计算节点处理。为充分测试算法在不同情况下的调度可靠性，分别对计算节点数为2（取计算节点1、4参与计算）、4（取计算节点1、2、4、5参与计算）、8（取全部计算节点参与计算）这三种情况展开测试。
在仿真环境下对任务调度机制进行测试，并记录各个计算节点对任务的处理时间和由于通信、任务切换等因素造成的等待时间。同时也测试了单纯将任务平均分配到各个计算节点上这种最“差”的调度机制。为直观表明任务调度效果，以平均分配这一最“差”的调度机制形成的任务执行时间除以新的调度机制形成的任务执行时间，作为调度机制的加速比。由此绘制视频分析任务的加速比如图3所示。
■
图3 任务执行时间加速比
上述测试结果表明，本文提出的调度机制在多计算节点情况下，面对高并发的大量复杂计算任务，能够进行合理有效的任务调度，取得良好的调度效果。在计算节点越多时，调度效果越好，平均可以提升效率两倍左右。
参考文献：
[1]储雅，马廷淮，赵立成.云计算资源调度：策略与算法[J].计算机科学，2013，40（11）：8-13.
[2]金士尧，钱迎进，章文嵩，王晓川.主动与被动混合调度网络集群服务系统[J].计算机工程与科学.2009，31（1）：17-19.
[3]A.T.Chronopoulos，R.Andonie，M.Benche，D.Grosu.A Class of Loop Self-Scheduling for Heterogeneous Clusters[C]. Proceedings of the 2001 IEEE International Conference on Cluster Computing.2002：113-122.
基金項目：
浙江省科技厅重大科技专项重点工业项目（2013C01045）。
作者简介：
陆成刚（1973-），男，上海人，高级工程师，理学博士，智慧安居；
王安（1985-），男，江西抚州人，工程师，硕士，图像与信息处理；
王汗（1989-），男，江苏沭阳县人，硕士研究生在读，数字图像处理；
洪榛（1983-），男，浙江台州人，讲师，工学博士，智慧安居。