基于组角色的物联网任务分配算法

刘 凡，葛方振，李 想，刘怀愚

(淮北师范大学 计算机科学与技术学院，安徽 淮北 235000)

物联网系统感知层由大量异构设备构成，不同功能的设备协作完成物联网环境中产生的任务[1]，使系统可以快速响应用户的请求，实现智能化的服务.由于设备资源和计算能力受限，设备仅能在动态环境下自主执行满足其能力和资源的任务，否则将导致终端设备负载不均衡、系统不稳定，从而降低用户体验.因此，任务分配问题是关键，即如何合理地分配物联网任务到终端设备，并符合终端设备有限的计算能力和资源[2].

目前，国内外相关学者从3个方面研究物联网中的任务分配问题.

第1，从物联网的任务类型研究.Atzori等[3]提出一种降低设备能耗的任务分配算法，把社会物联网中的定位传感任务分配给移动设备，然没能充分考虑设备的异构性；许志凯等[4]提出一种基于组合双向拍卖的搜索任务分配模型，合理地分配搜索任务，但难以实现模糊环境下的准确分配；Wu等[1]提出一种多物联网计算机任务的跨层云调度框架，使物联网服务可以动态选择合适的算法，能够有效地利用资源，完成不同目标的计算机任务，该框架任务调度结果精确度不高.

第2，从优化角度研究.Colistra等[5]从资源配置角度出发，提出一种基于物联网节点的分布式资源决策协议，实现网络中所有节点间的资源均匀分配；Khalil[6]在文献[5]的基础上，将异构感知启发式算法引入共识协议，把任务分配问题视为单目标优化问题，再利用元启发式优化模型，均衡网络实体能耗；Ahmad等[7]提出一种基于动态实时物联网系统下的资源感知算法，提高任务分配的准确性，降低能量消耗.以上研究从资源分配或降低能耗方面考虑问题，而诸如设备的存储、电量等资源，考虑不够全面，难以保证终端设备的负载均衡.

第3，从物理对象与任务的相关性研究.Ahmad等[8]给出一种基于设备最佳相关性的任务到虚拟对象(virtual object,VO)的映射平面，不同的任务自动被映射到虚拟对象上；Chen等[9]提出一种基于智能网关协调的计算任务再分配算法，实现协同边缘设备间感知任务分配和能量共享；Pilloni等[10]为所需任务找到物理设备的最佳匹配，提出一种分布式的虚拟对象协商算法，通过协商达成资源分配共识与任务分配组合优化.以上研究在动态环境下，由于物理对象有限的计算能力，难以实现系统自主分配.

上述研究表明，虽从不同方面解决任务分配问题，但大多从资源分配、能量消耗、资源利用率等角度考虑，而对设备执行效益最优问题的研究较少.为此，提出一种基于组角色的任务分配算法(group role-based task assignment，GR-BTA)，将物联网任务分配问题看作优化问题，充分考虑设备的感知、计算等能力，以及设备所处的环境和位置等属性条件，从设备执行效益角度衡量任务分配的准确性.首先将任务组与虚拟对象的概念引入到任务分配问题中，描述车间搬运系统；其次结合E-CARGO模型对问题建模，使用基于角色协作框架将任务映射为角色集，设备映射为虚拟对象集，并建立目标函数和约束条件，提出GR-BTA算法；最后以实验仿真验证GR-BTA算法的有效性，用示例说明在效益最大化条件下，任务分配的准确性较高，保证终端负载均衡和系统的稳定性.

1 物联网任务分配问题

1.1 物联网任务分配系统

物联网感知层设备，一般具有智能性，如智能手机、机器人、AGV小车等，用于通信、交换信息、智能决策[11]，为用户提供便捷、智能的服务.例如，工业物联网被誉为智能制造的神经系统，将工业生产加工过程与物联网技术高度融合，实现对各种生产资源的智能管理和设备可视化调度.图1为物联网环境下，某车间生产系统中的搬运系统，包含4个位置：物料区、检测点、库存区、加工点.整个搬运系统工作流程为：AGV从物料区取出物料，将其搬运到加工点加工；加工完成后，AGV搬到检测点检测质量；若产品检测质量合格，AGV再搬运到库存区将其存储，否则由AGV搬运回物料区，对物料重加工.因此，整个搬运过程中有4种搬运任务：搬运加工任务、搬运检测任务、搬运库存任务、搬运物料任务.应用服务器(application server，AS)响应用户请求，发布任务，AGV小车协商搬运任务由哪个AGV执行，把最终分配方案反馈给AS.

如何将当前搬运任务与AGV进行组合优化，找到最佳的分配方案，并充分利用设备计算能力和资源，使系统获得最大的效益值，就此问题展开研究.

1.2 任务分配问题描述

根据文献[10]，物联网的终端设备可以抽象为虚拟对象，是真实设备的虚拟副本，继承终端设备的所有功能、属性等，能够协作、交互、执行特定任务，由AS激活和管理.本文沿用此概念.

如图1，假定该物联网系统中有L个任务组和m个虚拟对象vo，任务分配问题是将L个任务组和m个vo间形成映射，目的是实现vo执行能力与任务执行需求的最佳匹配.任务分配问题的相关参数如表1.

任务分配的交互关系如图2.在物联网车间搬运系统中，AS一方面负责接收、解析用户请求，确定任务类型，分组任务，将任务组映射成不同的角色类型，得到vo可扮演角色的集合；另一方面查询所有状态，根据其状态及属性，评估每个vo执行各个任务的能力，将评估结果告知各vo.vo感知数据，响应AS的请求，接收评估结果，并把最终执行效益返回给AS.

表1 问题参数意义

例如，某用户发出需要原材料和检测产品质量的请求，经AS分析，确定搬运系统中需执行搬运物料任务、检测任务，对应任务组类型分别为Taskg0、Taskg1，其中需1个从物料区取出物料，并将其搬运到加工点的任务(Taskg0={t0})，2个从加工点搬运到检测点的任务(Taskg1={t0,t1})；AS将任务(组)映射成角色类型role0[1]、role1[2]，其中role0[1]表示有1个搬运物料任务角色，role1[2]表示有2个搬运检测任务角色；AS查询系统中每个AGV的状态和属性，评估其执行每个任务的执行力，并把结果返回给各AGV.把角色成功分配给AGV，让每个搬运任务都能匹配到合适的AGV.

2 物联网任务分配问题建模

2.1 RBC与E-CARGO模型简介

朱海滨教授提出基于角色的协同(role-based collaboration，RBC)，RBC是一种研究角色及它们之间复杂关系的计算方法学，支持复杂动态系统中协同优化，并以E-CARGO模型构建协同系统[12].E-CARGO模型采用九元组∑∷=C,O,A,M,R,E,G,S0,H描述系统协作原理，各元素意义见表2.通过RBC方法与E-CARGO清晰定义，Agent通过扮演角色，承担任务，进行交互、协作，完成角色的职责.

表2 E-CARGO元素意义

RBC方法已应用于组合优化、指派等问题，取得突出成果[12-16].Zhu等[12]把群组指派问题转化为一般的分配问题，提出一种基于匈牙利算法的高效算法，解决了群组角色指派优化问题；Zhu等[13]对KM算法回溯改进，提出一种KMB多对多的角色指派算法，给多对多分配问题提供一种解决方案；文献[14]证明了群组多角色分配问题有可行解的充要条件，并给出一种基于IBM ILOG CPLEX优化软件包带约束GRA问题的解决方案；文献[15]提出一个具有合作、冲突因素的群体角色分配问题，通过角色分配创建一个高性能组，同时考虑合作和冲突，使用IBM ILOG CPLEX最大化策略优化包求解最佳解决方案；Zhu等[16]针对自适应协作系统中的协同问题，构建基于RBC和E-CARGO的自适应协同框架，优化系统中群体性能.

以上研究说明RBC方法具有完整的工程方法论体系，可以用来建模、理解和解决组合优化问题.由此，利用RBC方法对物联网系统中的智能对象(如机器人、智能设备等)进行有效的权责分解，优化对象间的协作是非常可行，为物联网环境下任务分配问题提供一种新思路.

2.2 角色协作机制

RBC思想是从团队的角度考虑协作系统的设计、运行和优化.将某物联网功能性任务分成若干个任务,各个Agent扮演角色，即承担任务.只要Agent评估合理,扮演角色得当,团队协作就可得到最佳效能.RBC协作过程包括角色协商、Agent评估、指派角色、扮演角色和角色转移等阶段[17].主要阶段有3个：角色协商、指派角色、扮演角色.E-CARGO模型规范了目标、角色、代理和组的属性以及相互约束关系.

物联网环境下车间生产系统中，当某作业位置产生搬运任务时，先将任务发送给AS，AS搜集所有AGV的位置、是否空闲等信息；然后通过竞标等计算，再从中筛选出最佳分配方案；最后AS通知被选中的AGV，令其完成搬运任务.此分配过程与RBC中的角色协商、指派角色、扮演角色3步骤相对应，为解决任务分配问题提供了思路.

基于RBC思想，考虑物联网任务分配问题.将任务视为角色，vo作为角色扮演者，即执行任务的实体.vo间通过基于角色的协作机制，履行角色的职责，即可共同完成任务分配，其中任务分配、任务执行分别视为角色指派、角色扮演.如此，以角色和vo为媒介，可以解决物联网中的任务分配问题.

综上，物联网中任务分配过程可按照RBC思想规划，如图3所示.

Step 1 角色协商：系统中成员vo之间讨论，确定所涉及的角色，如果达成一致的决策方案，则进行Step 2，否则系统重新进行Step 1，当超过截止时间，协商仍未完成，则协商失败并终止；

Step 2 指派角色：AS评估并发布每个成员vo的执行力，负责决策的vo将决策结果下发至每一个成员vo，如果角色分配成功，则转至Step 3，否则协作终止；

Step 3 扮演角色：根据vo间协商的分配方案，系统中的vo扮演其所分配的角色，直至完成整个任务，若在扮演角色的过程中，出现角色冲突或设备故障等原因，则需重新进行角色协商.

2.3 物联网任务分配模型

基于上文描述，对E-CARGO模型改进，给出具体含义，提出基于组角色的物联网任务分配模型.文中用到的符号如表3所示.

表3 文中用到的符号

定义1 任务R∷=id,Mt,Vt,Vo,Vc表征任务，其参数与RBC中的角色相对应.其中id为任务的标识号；Mt表示向相关vo发送的消息，包括传入和传出消息；Vt为能承担任务t的vo集；Vo为曾经承担过任务t的vo集；Vc为当前承担任务t的vo集.

定义2 虚拟对象VO是执行任务的抽象对象.VO∷=id,Ro,Rc,Ng,Dv,Pv,Sv表示候选虚拟对象vo集合.其中id表示虚拟对象标识号；Ro为vo曾经承担过的任务集合；Rc为vo当前承担的任务集合；Ng表示vo所属群组；Dv={d0,d1,…,di,…dm-1}为voi能力特征，反映vo具有承担任务的基本能力，包括感知能力、信息处理能力等；Pv={p0,p1,…,pi,…pm-1}是voi位置状态；Sv={s0,s1,…,si,…sm-1}表示voi属性状态，0≤i≤m，m为虚拟对象数量.

定义3 任务权重向量W表示物联网环境E、组g中任务重要程度[18]，记为向量W，w[j]∈[0,1]，j是g.E的任务编号，0≤j

定义4 任务参数向量Lr是物联网环境E、组g中某个任务组中的任务参数取值范围，记为Lr[j]∈N，其中0≤N

定义5 任务分配矩阵X是一个m×n矩阵X:VO×R→{0,1}.若x[i,j]=1，则表示任务j分配给voi，相反，x[i,j]=0表示任务j没有分配给voi，其中0≤i

按照上述方法，计算任务与voi的匹配值，得到m×n矩阵Q表示如下：

综上分析和定义，物联网任务分配问题可形式化为组合优化问题，转化为求解任务-终端设备的最佳映射方案.任务分配目标就是找到一个可行的分配矩阵X，满足：

(1)

s.tx[i,j]∈{0,1}.

(2)

(3)

(4)

w[j]∈[0,1].

(5)

α，0≤i

(6)

式(1)是目标函数，满足以下约束：约束条件(2)表示任务分配矩阵的取值只能是0或1，即是否将任务分配给vo；约束条件(3)表示任务分配矩阵X每列中1的个数总和分别等于任务需求向量Lr中的每个值；约束条件(4)表示同一时刻任务只能分配到一个vo；(5)中w[j]∈[0,1]表示任务权重值范围；约束条件(6)表示i,j的取值范围，α确保有足够多满足资格阈值的vo承担任务.目标函数在满足多约束条件下，求得一个可行的任务分配矩阵X，使目标函数值最大.

2.4 基于组角色的物联网任务分配GR-BTA算法

解决角色协同问题是使用文献[12]中群组角色分配(group role assignment problems, GRAP)算法，以团队性能为目标的角色指派优化方法，GRAP分配问题通常先转化为一般角色分配问题(general assignment problems, GAP)，把多对多指派问题，转化为一对一的指派问题，再利用匈牙利算法(K-M算法)计算分配矩阵，在原GRAP问题基础上进行一些扩展，得到GR-BTA算法,具体算法见图4.

图4 GR-BTA算法伪码

3 实验环境与实验结果分析

3.1 实验环境配置

为了验证GR-BTA算法的性能，本文进行了实验测试与结果分析.实验硬件环境是一台笔记本电脑，CPU主频是2.50GHz，内存容量为4GB，操作系统为Windows 10 Enterprise64位，开发环境为Eclipse 4.12，JDK版本为12.0.1，64Bit.

因匈牙利算法复杂度为O(m3)，即复杂性主要取决于m的值，故在实验中把vo数量m与任务数量n关系设计3种，分别为m=2n,m=3n,m=4n.下面，针对m与n的3种关系，进行3次实验测试，每次实验测试十组数据，每组数据重复运行300次，每组数据包括vo数量m、最大运行时间、最小运行时间、平均运行时间和成功分配率.矩阵Q利用随机函数生成，为0～1之间的数值.为保证有足够数量的vo进行任务分配，Lr值根据需要随机设置.

3.2 算法性能分析

第1次实验，vo数量m分别设为10,20,30,40,50,60,70,80,90,100，m=2n，任务参数向量Lr值随机设置为1或2.表4记录了每组测试结果最大运行时间、最小运行时间、平均运行时间和成功分配率.图5给出了vo数量m递增时，最大运行时间、最小运行时间、平均运行时间变化情况.

表4 GR-BTA算法测试结果

注:m=2n,α=0.5.

从表4可以看出，GR-BTA算法运行时间随着m增大而增大，但对成功分配率无影响.当m=10时，平均时间为 2.18 ms,当m=100时，最大时间不到 143 ms，平均时间仅为 80 ms 左右.根据互联网用户响应时间2-5-8标准，用户在 2 s 以内得到响应，能感到系统响应速度非常快，所以GR-BTA算法运行时间满足互联网要求.

从图5可以看出，vo数量m影响运行时间明显，即m取值越大，运行时间越长，计算时间消耗较多.

第2次实验，vo数量分别设为9,18,27,36,45,54,63,72,81,90,99，共11组，每组也重复300次，m=3n，Lr随机取1、2、3中任意值.同样，矩阵Q使用0～1之间均匀分布随机数产生.表5记录每组测试结果，图6给出vo数量递增时，最大运行时间、最小运行时间、平均运行时间变化情况.

表5与表4数据变化规律相同，图7和图6变化趋势相同.

注：m=3n,α=0.5.

第3次实验，vo数量分别设为8,16,24,32,40,48,56,64,72,80,88,96，共12组，每组实验重复300次.m=4n，Lr数值随机取1、2、3、4中任意值，同样Q矩阵使用0～1之间均匀分布随机数产生.表6为每组测试结果，包括最大时间、最小时间、平均时间和成功分配率.图7给出vo数量递增时，最大运行时间、最小运行时间、平均运行时间变化情况.

表6 GR-BTA算法测试结果

注：m=4n,α=0.5.

从表6中数据可看出，随着m值增大，运行时间也增加.图7与图6、图5变化趋势基本一致.

综合表4～6、图5～7，可观察到：①最大运行时间曲线波动较大，出现vo数量多的测试组的最大运行时间比vo数量少的测试组的短，m和n的倍数关系越大，波动越明显，这是因为测试组中Q与Lr的值是随机产生，影响了算法的最大运行时间，而对平均运行时间、最小运行时间变化趋势无影响；②运行时间随分配问题规模增大而增加，而非随vo数量幂级增加，且均在毫秒级内，分配成功率高，能使物联网终端设备在极短时间内得到最佳任务分配方案，快速响应任务请求.

因此，GR-BTA算法运行时间短、成功率高，主要原因是，该算法引入角色概念，降低了物联网节点管理和协调难度.给物联网节点确定角色，大幅度减少决策空间，减少决策时间，故不会出现随分配问题规模呈幂级增长.同时根据角色特征进行协调，不需要过多考虑节点个体属性，提高算法的协同性，分配成功率高，从而使得终端设备负载均衡、物联网系统稳定性.

3.3 分配示例

以基于智能节点的物联网车间智能调度原型系统为基础，该系统中的搬运任务分配问题实质是在离散事件上一个组合优化问题.针对图1，系统沿用虚拟对象思想，将AGV小车设计为物联网系统的智能终端，形成基于虚拟对象的智能终端物联网车间指派模型.如1.2节描述，系统中产生4种搬运任务组，分别是搬运物料任务组、搬运检测任务组、搬运加工任务组、搬运库存区任务组.在AGV搬运系统中，AGV同一时刻仅能执行一个搬运任务，并且只有完成当前任务后，才能继续执行下一个可搬运的任务.

系统中现有12辆智能AGV小车，4种任务组对应的角色分别为搬运物料任务的角色、搬运检测任务的角色、搬运加工任务的角色、搬运库存区任务的角色.某时刻需要1辆搬运重量为200 kg物料的AGV，2个重量为 100 kg 的物料在某加工点完成加工后，需由2辆AGV搬运到检测点进行质量检测，并在此时检测点有3个检测合格的零件需搬运到下一个加工点，加工完成的零件有2个需搬运到库存区.此时任务参数向量为Lr=[1,2,3,2]，假设每种任务所占的权重为W[j]=[0.20,0.32.0.30,0.18]，根据定义8，AGV扮演各角色的执行力评分矩阵Q，如图8.

根据已知条件，现有m=12个智能AGV，任务参数向量为Lr=[1,2,3,2]，任务权重W[j]=[0.20,0.32,0.30,0.18].图9中标下划线对应的AGV,即为扮演对应角色的最佳AGV.表7为任务组、任务与角色对应关系，表8为角色与AGV对应关系.

表7 任务组、任务与角色对应关系

表8 AGV与角色对应关系

以上示例表明，物联网中引入任务组、虚拟对象以及角色概念，不仅有效降低设备管理、协调难度，提高任务执行效率和分配准确性，而且有利于物联网系统组织和协作开展，优化终端设备协作效果，从而减少设备层协调复杂度，平衡终端负载.

4 结语

将角色概念引入物联网中的任务分配问题，建立物联网智能终端设备与虚拟节点间联系，使用虚拟对象和任务组概念，并结合基于角色的协作工程理论与方法及其E-CARGO模型，对物联网中任务分配问题建模，设计GR-BTA算法，解决物联网中的任务分配问题.实验测试结果表明，该方法有效且精度高、速度快，通过AGV小车搬运系统仿真实验，实现物联网多变环境下的任务分配与协同自主，再次验证该算法精度高.