摄像机网络中基于任务域的任务分配方法

李 骎，张亚英，叶 晨

(同济大学嵌入式系统与服务计算教育部重点实验室，上海200092)

0 引 言

随着智能交通应用规模的扩大，基于视频图像处理技术的智能摄像机广泛应用于智能交通监管系统［1，2］。智能摄像机网络系统综合了嵌入式系统、网络技术、视频传输和图像处理等技术，可以同时实现多种应用需求，如视频监控、车流量检测、交通事件检测、车辆识别与跟踪等［3］。但通常情况下，摄像机网络中系统资源是受限的，如摄像机节点的处理能力、网络的带宽、I/O等资源均是有限的。而在智能交通应用场景中，摄像机网络系统需要满足多样化的任务需求。因此，如何在有限的系统资源条件下有效实现智能摄像机网络中的任务分配是当前需要解决的重要问题。

摄像机网络中节点任务的分配是根据交通路口的具体应用需求，将任务分配到各个智能摄像机节点上，通常需要考虑如何在系统资源利用率达到最大的同时满足任务自身的实时性要求。近年来，针对智能摄像机网络的任务分配问题已有许多研究成果。在目前任务分配的研究中，主要研究策略是先将任务分配问题进行形式化［4］，再应用诸如兴趣匹配［5］、博弈论［6］、基于市场拍卖［7］等方法提出任务分配的算法模型。上述方法针对视频监控、协同跟踪等单个应用场景提出了很好的理论模型，但无法适用于多种应用需求同时并存的智能交通应用场景。如针对某个路口同时兼顾视频监控、事件检测和协同跟踪等多种类型的任务时，该路口单个摄像机节点可能需要执行多个不同类型的任务。此时需要考虑多个任务在单节点执行对任务QoS(Quality of Service)的影响，因此需要加入新的任务分配策略。

笔者针对基于视频图像处理的智能交通综合应用，研究交叉路口道路区域中摄像机网络的任务分配方法。在实际场景中，任务和摄像机节点的监控范围有紧密联系，对于监控同一路口的多个智能摄像机节点，存在节点的视域(FOV:Fields of View)可能出现部分重合的情况。笔者提出的一个任务对应一块图像处理区域，当该区域同时处于多个监控摄像机节点的视域中时，意味着该任务能被多个节点执行，因而，需要决策任务的执行节点。笔者提出了一种基于任务域并综合考虑任务QoS和系统资源利用率的任务分配方法，力求达到系统资源利用率最大化并保证执行任务的服务质量。

1 任务分配问题描述

1.1 任务域和任务相关组

在智能摄像机网络中，假设有n个摄像机节点C={c1，c2，…，cn}部署在s个交通路口，每个交通路口Rk(k=1，2，…，s)由若干节点覆盖，节点通过网络互联进行通信。所有摄像机节点均能连接到远程管理中心，远程管理中心作为节点管理者和任务分配者，对网络内各个节点进行任务分配。

为了将m个任务分配给部署在路口Rk的摄像机节点，首先定义路口任务集合为Tk={t1，t2，…，tm}。任务集Tk描述了某一时刻针对路口Rk的任务需求，任务分配者根据任务分配策略生成路口Rk中各节点的节点任务集，通过对各个路口Rk进行任务分配实现整个摄像机网络的任务分配。

对于每个节点，其计算能力和网络带宽资源限制了节点能执行的任务数量，节点ci的总处理能力记为csi。笔者采取一种静态的分配策略，在任务分配决策前，节点向任务分配者反馈当前负载Li，任务分配者根据各节点的负载Li进行任务决策。决策完成后，任务分配者将节点任务集Ti分别发送至各个节点完成任务分配，随后各节点可以开始执行被分配的任务。

在实际交通应用场景中，各类任务执行的本质是节点对监控区域的图像进行处理。图1a为一个实际交通路口，某个摄像机节点对图中白色虚线框内的图像进行实时处理以检测路口车流量。图1b显示的是检测车道车辆队列长度的应用，路口某个节点对白色标定区域的车辆排队长度进行计算。视域FOV定义为摄像机的视野区域，上述两个任务的共同点是节点对摄像机视域中部分区域的图像数据进行处理，将该区域定义为任务域。如图1c所示，以监控路面为平面，图中扇形区域为节点ci的视域FOVi，在此监控区域内，视域中的方框型区域分别为t1和t2两个任务域FOT1和FOT2。每个任务tj有其对应的唯一任务域FOTj。在节点ci中，任务tj的执行过程即对相应任务域FOTj的图像处理过程。

图1 任务域模型Fig.1 Model of FOT

在实际场景中，存在多个摄像机节点的FOV有重合的情况(多个节点同时监控一个路口)。若tj的FOTj在Nj个节点的FOV中，则这些节点均能执行该任务，定义能执行任务tj的节点组成该任务的任务相关组 Gj={c1，c2，…，cNj}。

1.2 任务负载

任务在节点上运行时一般主要消耗两类系统资源:1)节点进行图像处理所消耗的本地计算资源;2)任务执行过程中产生的网络通信开销，可采用节点间的消息通信数量衡量［8］。为简单起见，假设网络内的摄像机节点均具有相同的计算能力。在嵌入式智能摄像机中，考虑其CPU、内存和网络I/O为主要资源，节点ci的总处理能力为

其中Sc为节点CPU计算资源，Sm为内存资源，Sn为网络资源。k1，k2，k3分别为对应资源的权重。对于Tk中的某个任务tj，定义其资源消耗值为

其中Sc，Sm，Sn分别为节点执行任务tj所消耗的CPU、内存和网络资源，p1，p2，p3分别为对应资源的权重。在嵌入式智能摄像机中，任务的执行过程主要在于运行图像处理算法，对节点CPU资源的消耗为主要资源消耗。一般情况下，取k1和p1为较大值，也可根据具体实验评估各权重参数的选取。

对于一个运行中的节点ci，当前执行的所有任务组成节点任务集Ti，则在当前的任务分配方案中，节点的计算负载为

在任务分配决策过程中，任务分配者获取各节点当前的Li值。任务决策完成后，任务分配者将新的任务加入到节点任务集Ti，并将更新后的Ti发送至节点，节点依据新的Ti更新自身的计算负载。

1.3 任务服务质量QoS

对于任务tj，其QoS由一系列服务质量参数定义。QoS参数包含可处理图像的分辨率和图像处理帧率(Frame Rate)等［8］，这里采用图像处理帧率衡量任务的QoS。随着节点处理的任务数增多，节点计算负载Li升高，节点的图像处理帧率会下降，将影响到该节点当前执行任务的实时性。

因此，可通过控制节点的计算负载Li，避免节点执行过多的任务，以保证该节点执行任务的QoS。对于任务tj，为保证其在节点运行的QoS，为其设定一个运行时的阈值Qj。定义节点负载Li＜Qj时，可保证任务tj执行时的QoS。对于一个运行中的节点ci，为保证当前节点任务集Ti中所有任务的QoS，需满足

若新任务tj的加入导致节点负载Li＞min(Q1，Q2，…，Qj)时，节点ci将无法满足任务集Ti中所有任务的QoS，此时任务tj无法被分配至节点ci。

2 任务分配决策流程

对一个路口进行任务分配的目标是在保证任务QoS的前提下尽可能分配更多的任务，达到路口各节点资源利用最大化。在如图2所示的任务分配场景中，路口Rk部署有4个摄像机节点Ck={c1，c2，c3，c4}，在初始状态，各节点均处于未分配任务的空闲状态。在一次任务分配过程中，分配给路口Rk的任务集为Tk={t1，t2，t3，t4，t5}，其对应的任务域分别为FOT1～FOT5。为简单起见，假设每个摄像机节点的处理能力相同，各任务的资源消耗值与任务域的大小成正比，任务集Tk的资源消耗为Sk={0.6，0.6，0.4，0.2，0.2}。

如图2所示，对于FOT1和FOT2两个任务域，其在c1～c44个节点的视域FOV内，由此确定任务t1和t2的任务相关组G1=G2={c1，c2，c3，c4}，表示4个节点均能执行任务t1和t2。由于FOT3在c1和c2的视域内，则任务t3的任务相关组为G3={c1，c2}，同理，任务t4和t5的任务相关组分别为G4={c2}和G5={c4}。任务相关组信息如表1所示。

图2 任务分配示意图Fig.2 Schematic of task assignment

表1 任务相关组Tab.1 Group of relevant tasks

多任务多节点的任务分配问题是一个近似装载问题［9］，任务分配的第1步是根据上述任务相关组所含元素个数，将任务按资源消耗值以非递减排序生成任务的FIFO(First Input First Output)队列，定义任务集Tk排序后的任务队列为Tok={t4，t5，t3，t1，t2}。任务分配决策时，按照任务队列的顺序做出任务分配决策。首先从Tok中取出第1个待分配任务t4，由于其任务相关组为G4={c2}，即仅能在节点c2上执行，则无需决策，直接将任务t4分配给c2节点。c2的执行任务集更新为T2={t4}，并计算更新c2的负载值L2，最后将t4移出任务集Tok，完成了对任务t4的分配，同理可完成对任务t5的分配。之后处理任务t3的分配，任务相关组为G3={c1，c2}，即t3可在节点c1或c2上执行，此时，需要选择决策该任务的执行节点。分别计算两个节点的负载值L1和L2，选择负载值较小的节点作为任务分配节点，此处为L1，则将任务t3分配给节点c1。同理，将任务t1分配给节点c3。

现在考虑任务队列最后一个任务t2的分配，先比较任务相关组G2中各节点的负载值，选取其中最小的负载值Lmin=min(L1，L2，L3，L4)，其对应的节点为cmin。此时4个节点均已分配了任务，将t2预分配给cmin，更新其当前负载值Lnow。根据前述的任务QoS策略，若满足式(2)，则可将任务t2分配给节点cmin，若式(2)的条件无法满足，则任务t2无法分配给节点cmin。在该情况下，一般的方法是将任务t2定义为无法分配，并反馈信息。按照上述分配决策流程直至Tok为空，标志所有的任务分配决策完成，任务分配者将节点任务集Ti分别发送至各个节点，完成任务分配过程。图3给出了任务分配决策流程。

图3 任务分配流程图Fig.3 Flow chart of task assignment

3 任务转移策略

在上述任务分配决策流程中，当任务tj的加入导致节点cs无法满足任务QoS，即不满足式(4)时，tj无法分配至节点cs，此时可采用任务转移策略。节点cs将作为发起者在摄像机网络内寻找资源相对空闲的伙伴节点作为任务的接收者cr，并将任务转移分配至该节点。这种策略可以实现系统计算资源的负载均衡，提高了系统资源利用率，但同时需要转移图像数据，加大了系统网络开销。其实现的关键是如何在网络内部选取一个合适的节点作为任务接收节点。针对这一问题，笔者提出了基于节点间相对价值的任务转移评价函数，并基于此评价函数提出一种任务转移策略。

3.1 任务转移评价函数

定义Vcij为节点cj对ci的相对价值，Vcij由节点cj当前的计算负载Lj和节点间的网络通信距离Ccij衡量。Ccij用于描述图像数据流从ci传递至cj的网络延时，以此衡量任务转移的实时性。Ccij值越大，表明任务转移的网络开销越大，越不利于任务的转移执行，即对于任务接收节点的计算负载Lj，当Lj越小时，有更大可能满足任务QoS，则其作为任务接收者的概率越大，即

综上，节点cj对ci的相对价值可表示为

其中ωL，ωC分别为计算负载和网络通信距离的权重。一般情况下，取ωL为较大值，也可根据具体实验评估各权重参数的选取。

3.2 含任务转移策略的任务分配

根据上述转移评价函数，节点选取网络内Vcij值最高的节点作为任务转移接收节点。对于任务接收者cr，任务tj转移至cr将增加其负载，因此，需要判断式(4)是否满足任务接收者的任务QoS要求。若满足条件，则任务分配者将任务tj标记为转移型任务，同时生成包含任务接收节点信息在内的任务转移信息，加入到tj的任务描述信息中。最后，任务分配者将任务tj加入节点cr的任务队列中，并更新节点cr的负载。

任务转移策略是对前述任务分配决策流程的补充，下面给出含任务转移策略的任务分配算法，该算法的复杂度取决于任务分配总数和网络内节点总数。假设一次任务分配过程中将m个任务分配给由n个节点组成的网络，决策过程的主要代价分为两部分。首先，由任务集生成任务队列过程中，根据任务相关组大小排序，其复杂度为O(mlog m)。其次，在单个任务决策过程中，若直接分配，则需寻找任务相关组中节点负载最小者，其复杂度的上界为O(n);若采用了任务转移策略，则单次任务转移在网络内寻找相对价值最大的节点，其复杂度的上界为O(n)。假设有l个任务需要采用任务转移策略，则任务决策的复杂度为O(ln+(m－l)n)，即O(mn)。综合上述两部分，任务决策的复杂度为O(mlog m+mn)。

算法1 任务分配算法

3.3 任务转移执行过程

根据算法1的描述，依据在任务决策过程中是否需采用任务转移策略，任务可分为两类:第1类是可直接决策分配的任务;第2类是需要采用任务转移策略进行决策分配的任务。对于这两种任务，假设经过算法1的任务决策后，任务ti被分配到节点ci，任务分配者将ti加入到ci的执行任务集Ti。当所有任务决策完毕，任务分配者将Ti发送至节点ci，完成对ci的任务分配过程，此后，节点ci进入任务执行状态。

在节点任务执行过程中，节点ci依据任务集Ti执行任务。Ti中存在上述两类任务，对于第1类任务，节点可直接在本地分配任务资源并执行任务;对于第2类任务，节点需要执行任务转移流程。下面以任务tj为例详细描述任务转移的执行过程。

对于tj，在任务转移过程中，假设节点cs作为任务转移发起者，cr作为任务接收者。首先，cs作为客户端主动与cr建立连接，并将任务tj的任务描述信息s(tj)发送至cr。cr接收任务信息stj后，准备执行任务tj的相关资源，准备完毕后发送任务准备完成信号r(tj)至cs。任务接收节点cr接收到r(tj)信号，开辟新的图像数据传输连接，并开始连续发送任务tj所需任务域FOTj的图像数据流d(tj)。cr接收到图像数据流后，在本地对接收到的图像数据流执行相应的图像处理算法，进入任务执行状态。当节点cs接收到新的任务分配消息或任务tj执行完毕时，进入关闭任务转移流程，节点cs停止传输图像数据流，并发送任务结束信号e(tj)至cr，节点cr收到信号后停止执行tj并释放相应的节点资源。图4描述了任务转移流程，在整个任务转移过程中，若发生由于节点资源不足或网络故障导致任务转移失败或中止时，节点cs将中止任务转移并向任务分配者反馈任务转移失败信息。

图4 任务转移执行过程Fig.4 The process of task transfer

4 实 验

4.1 实验系统

笔者在实验室环境内架设由4台智能摄像机组成的智能摄像机网络系统，4台摄像机节点通过交换机连入以太网。智能摄像机采用ROSEEK公司的EagleEye3E系列智能摄像机，它具有逐行扫描CCD(Charge－Coupled Device)传感器，内嵌主频1 125 MHz的TMS320DM648嵌入式DSP(Digital Signal Process)芯片，配置512 MByte DDR2内存及100 Mbit/s以太网接口。实验在嵌入式智能摄像机上实现智能摄像机网络系统，软件结构如图5所示。该软件结构分为3层［10］:集成多种算法的图像处理应用库的应用层，分析系统资源和网络控制信号并控制摄像机行为的控制决策层以及负责摄像机和外界通信的通信层。

图5 系统软件结构图Fig.5 Structure diagram of the system software

4.2 实验环境

在如图6所示的交通多路口场景中，共含有两个路口，每个路口分别布置了4个节点。其中c1，c2监控道路1，c3，c4监控道路2。为模拟多任务及任务转移场景，调节摄像机使监控每条道路的两个节点视域FOV均重合，并在PC上模拟实现布置于路口2的4个节点，作为任务转移过程的接收节点。

图6 实验环境Fig.6 Experiment environment

初始状态下，路口的节点均处于空闲状态。各节点的应用库配置了两种典型的任务应用:1)视频监控;2)区域检测，对应的QoS阈值分别为Qa=1，Qb=0.85。假定单个节点总计算负载为1，根据实验测试，视频监控任务的资源消耗值S(ta)=0.2，区域检测任务的资源消耗值S(tb)与具体任务检测区域的大小成正比。因此，向不同区域分配面积大小不等的检测任务可模拟路口执行多种任务组合的场景。针对任务转移场景，在相对价值Vcij的计算中取ωL=0.9，ωCD=0.1。本实验开发了运行于PC端的远程配置工具客户端作为任务分配者，可显示当前智能摄像机网络各节点的工作状态，具有发送消息分配任务的功能。

实验中对路口的两个道路进行任务分配，并逐步增加任务分配数，在远程配置工具上跟踪各节点任务执行状态。例如，在一次总任务数为4的任务分配过程中，分配给路口1的任务集为T1={t1，t2，t3，t4}。其中t1为视频监控任务，其余3个任务为区域检测任务。根据实验测试，其资源消耗值集合Sk={0.2，0.3，0.3，0.4}。任务分配者按照不同的任务分配策略分配任务，比较各种策略的任务分配效果。

4.3 实验结果和分析

本实验比较了3种不同方法的任务执行质量，任务丢弃率［11］和资源利用率。任务执行质量采用节点图像处理帧率衡量，任务丢弃率即丢弃的任务占总分配任务数的比率，资源利用率即运行任务消耗的系统资源占总系统资源的比率。方法1为传统任务分配方法(TA:Task Allocation)［12］，该方法仅考虑节点负载，以单节点运行最大数量任务为目标。方法2为笔者提出的综合考虑任务QoS和节点负载的任务分配方法(QTA:QoS－aware Task Allocation)。方法3是在方法2的基础上使用了任务转移策略的任务分配方法(TQTA:Tranfer based QoS－aware Task Allocation)。

随着任务数的增大，节点负载提高导致图像处理帧率下降。理论上，在本次实验所用智能摄像机上，为保证检测车辆最大速率可达到90 km/h，图像处理帧率需达到Ft=10帧/s，不妨将满足该要求的任务称为合格任务。图7a统计了TA方法和QTA方法在系统中运行的合格任务数占总任务分配数的比率。当任务分配数不大于8时，两种方法均能保证所执行的任务质量。当任务分配数大于8时，两种方法的任务合格数均开始下降，且TA方法的合格任务数占比下降较QTA快，当任务分配数达到16时，采用TA方法将导致所有节点任务均不满足任务质量要求。这是因为随着分配任务数的增大节点负载提升，TA方法没有相关保证任务质量的机制而导致之前运行任务的QoS下降，而考虑了任务QoS的QTA方法较TA方法有更好的任务执行质量。

图7b比较了QTA方法和TQTA方法的系统资源利用率，随着分配任务数的增大，采用任务转移策略的TQTA方法比QTA方法有更高的资源利用率。当路口各节点任务达到饱和时，TQTA方法较QTA方法的资源利用率提高了50%。图7c比较了QTA方法和TQTA方法的系统任务丢弃率，随着任务数的增多，TQTA方法较QTA方法有更低的任务丢弃率。当路口各节点任务达到饱和时，TQTA方法较QTA方法的任务丢弃率降低了40%。这是因为TQTA方法通过任务转移策略，将原本需要丢弃的任务转移到网络内相对空闲的节点上执行，提高了系统资源利用率并降低了任务丢弃率。

图7 实验结果Fig.7 The results of experiments

由于TQTA方法采用了任务转移策略，其任务转移过程中存在节点间的图像数据传输，因而加大了系统网络开销。图8显示了系统平均网络负载，随着任务数量的加大，采用TQTA方法使系统网络负载成本提高，而QTA方法仅存在任务分配等少量网络通信，其网络负载值可以忽略。在实验室100 Mbit/s以太网环境中，由于智能摄像机网络节点数目较少，增加的网络负载并未影响到系统的实时性。随着系统规模的扩大，需要考虑网络负载的加大对系统执行任务实时性的影响。

由于实验环境所限，笔者仅测试了模拟两个交通路口场景的智能摄像机网络。由于路口的摄像机都是独立的并且网络内各节点能对等通信，对路口添加一个摄像机，可远程配置摄像机的基本参数，连入网络的摄像机向任务分配者反馈其基本信息便可加入到智能摄像机网络。因此，可通过增加节点数量扩大系统规模，使该方法适合于交通应用中多个类型任务综合存在的场景，系统具有良好的可扩展性。

图8 网络负载Fig.8 The network load

5 结语

笔者研究了智能摄像机网络的多任务分配问题，针对智能交通应用场景，将任务分配问题形式化抽象，提出基于任务域并综合考虑节点负载和任务QoS的任务分配方法。为解决节点在任务分配过程中出现的任务饱和问题，提出基于节点间相对价值的任务转移策略，并给出了任务分配算法。针对实际场景中的应用，设计了一种可在嵌入式智能摄像机上实现的智能摄像机网络。模拟场景的实验分析表明，上述任务分配方法提高了系统整体资源利用率和任务分配的成功率，能较好适应交通应用的多任务场景。但是，采用任务转移策略的任务分配方法加大了系统网络负载，在更大规模场景中应用需要考虑其对任务QoS的影响。因此，未来的工作考虑随着系统规模扩大和任务分配数量的提升，系统网络负载提升的条件下如何提高系统的实时性。

［1］RINNER B，WOLF W.A Bright Future for Distributed Smart Cameras［J］.Proceedings of the IEEE，2008，96(10):1562－1564.

［2］QI W，QIAO F，YANG H.Distributed Smart Camera Network［J］.Recent Patents on Electrical＆ Electronic Engineering，2012，5(1):20－29.

［3］LI Y，BHANU B.Task－Oriented Camera Assignment in a Video Network［C］∥2009 16th IEEE International Conference on Image Processing(ICIP).Cairo，Egypt:IEEE，2009:3473－3476.

［4］CUI L，JIA W.Weighted Capacitated Popular Matching for Task Assignment in Multi－Camera Networks［C］∥2013 25th International Teletraffic Congress(ITC).Ghent，Belgium:IEEE，2013:1－4.

［5］YE Chuang，ZHENG Yu，VELIPASALAR S，et al.Energy－Aware and Robust Task(Re)Assignment in Embedded Smart Camera Networks［C］∥2013 10th IEEE International Conference on Advanced Video and Signal Based Surveillance(AVSS).Krakow，Poland:IEEE，2013:123－128.

［6］PLETZER F，RINNER B.Distributed Task Allocation for Visual Sensor Networks:A Market－Based Approach［C］∥2010 FourthIEEE International Conference on Self－Adaptive and Self－Organizing Systems Workshop(SASOW).Budapest，Hungary:IEEE，2010:59－62.

［7］ZAREZADEH A A，BOBDA C.Enabling Communication Infrastructure and Protocol on Embedded Distributed Smart Cameras［C］∥2011 Fifth ACM/IEEE International Conference on Distributed Smart Cameras(ICDSC).Palo Alto，CA，USA:IEEE，2011:1－6.

［8］SCHRIEBL W，WINKLER T，STARZACHER A，et al.A Pervasive Smart Camera Network Architecture Applied for Multi－Camera Object Classification［C］∥Third ACM/IEEE International Conference on Distributed Smart Cameras(ICDSC).Como，Italy:IEEE，2009:1－8.

［9］KUMAR S，KUMAR S，NANDI S.Distributed Smart Camera Network and Mobile Devices［C］∥Proceedings of the International Conference on Advances in Computing and Artificial Intelligence(ACITY).Chennai，India:ACM，2011:21－24.

［10］BRAMBERGER M，BRUNNER J，RINNER B，et al.Real－Time Video Analysis on an Embedded Smart Camera for Traffic Surveillance［C］∥Real－Time and Embedded Technology and Applications Symposium 2004.Proceedings of RTAS 2004 of 10th IEEE.Toronto，Canada:IEEE，2004:174－181.

［11］HOFFMANN M，WITTKE M，HÄHNER J，et al.Spatial Partitioning in Self－Organizing Smart Camera Systems［J］.IEEE Journal of Selected Topics in Signal Processing，2008，2(4):480－492.

［12］CENEDESE A，CERRUTI F，FABBRO M，et al.Decentralized Task Assignment in Camera Networks［C］∥2010 49th IEEE Conference on Decision and Control(CDC).Atlanta，Georgia，USA:IEEE，2010:126－131.