数据驱动下交互网络群智感知任务分配仿真

赵 敏

(贵州民族大学数据科学与信息工程学院，贵州 贵阳 550025)

1 引言

车载感知设备、智能手机、可穿戴设备和平板电脑等终端设备在近年来得到了普及和发展，上述智能设备中存在了大量的传感器，具有通信、计算、存储和感知的能力，促进了群智感知技术的发展[1]。群智感知技术是移动感知和众包思想结合生成的，其感知单元是用户身上存在的移动设备，构成移动网络，通过网络进行无意识或有意识的协作，实现数据收集、任务分发，可以完成复杂、大规模的感知任务[2]。群智感知技术被广泛的应用在城市环境感知、环境检测、公共安全和智能交通等领域中[3]。时间变化的同时移动节点在网络中的位置也会发生变化，使节点在网络中相遇的时间出现较大的波动，所以节点在传输数据的过程中所用的时间较长，提高了实现任务的时间成本，因此需要研究网络群智感知任务的分配方法[4]。

基于混合任务网络的任务分配方法考虑服务群体的协同水平和胜任度构建群智感知任务分配模型，通过粒子群算法求解任务分配模型，引入加权TOPSIS评估方法结合网络实际情况和用户偏好得到群智感知任务的分配方案，该方法分配任务所用的时间较长，任务分配效率低[5]。基于Q学习的网络任务分配方法通过Q学习方法确定多目标在网络中相遇的最好时机，利用回报函数和Q学习函数得到最优簇首在目标并行阶段中的切换方案，采用动态最小簇成员总数和信息效用函数保证网络剩余能量的同时，选择不同阶段中的簇成员和最优簇首，实现网络任务的分配，该方法将任务分配给用户后，只有少数的用户能够完成任务，存在任务完成率低的问题[6]。基于双边匹配的任务分配方法分析网络用户的属性指标信息，采用聚类方法根据用户的相关信息对用户做聚类处理，采用优势数分析和用户偏好信息的任务评价排序方法，评价每个聚类的任务集，在双边匹配理论的基础上实现用户和任务的匹配，完成网络任务的分配，该方法中的算法较为复杂，存在计算所用的时间较长、分配效率低的问题[7]。

针对当前任务分配方法中存在的分配效率低和任务完成率低的问题，提出数据驱动下交互网络群智感知任务分配方法。

2 群智感知环境和约束条件

1)群智感知环境

用户的移动设备在群智感知环境中可以作为无线传感器，通过设备的通信、感知、存储和计算功能协同完成任务。群智感知技术可以以较小的代价实现城市Wifi描述、交通信息映射等复杂且规模较大的感知任务。一般情况下通过视频、文本、音频和图像等媒介存储群智感知的数据和任务。群智感知问题可以描述为在未知环境中请求者利用环境感知学习实现任务的调度。

(1)

(2)

式中，TL代表的是最晚完成时间；EPT代表的是移动用户uj执行任务ti需要的时间；TM代表的是理论最小完成时间，其计算公式如下

(3)

式中，CPj代表的是第j个设备在交互网络中的处理能力；TAT代表的是为移动用户uj分配任务ti所用的时间。

设Ti，j代表的是在第j个设备中运行第i个任务实际花费的时间，其计算公式如下

(4)

交互网络群智感知环境中处理任务的过程主要为：通过交互网络为用户设备中传送任务；用户通过设备执行任务；在利用交互网络将任务处理结果传送到设备中。

2)约束条件

在分配任务时，所用的时间越少方法的性能越好，分配任务过程中消耗的能量也是需要任务分配方法考虑的因素[8]。

设E代表的是分配任务消耗的能量，其计算公式如下

(5)

式中，TMEM(ti，uj)代表的是在用户uj的内核中运行任务ti消耗的最大能量。

如果在交互网络群智感知环境中将任务分配给其他用户时，则从移动设备中接收任务和将任务发送给移动用户是任务在设备中的主要能量消耗，其中接收任务消耗的能量较小，所以用户采用移动终端执行任务消耗的能量可以只考虑发送任务消耗的能量。

任务请求者通过交互网络将任务传送给用户，设Trans(ti)代表的是传送任务所用的时间，其计算公式如下

Trans(ti)=WS(ti)/B

(6)

式中，WS(ti)代表的是任务ti中存在的工作量；B代表的是任务传输带宽。

用户会考虑本身在网络中空闲的资源总数对接收到的任务进行处理，接收到任务后用户判断自身资源是否能够处理任务，设EPT(ti，uj)代表的是处理任务花费的时间，其计算公式如下

EPT(ti，uj)=WS(ti)/[Trans(ti)·CPj]

(7)

利用交互网络将任务处理结果传送给请求者。

为用户分配任务是任务分配方法的最终目标，在满足分配约束的条件下，尽可能的缩短分配任务所用的时间[9]。任务分配时间主要包括任务传输时间和任务处理时间。

在满足服务约束和资源约束的基础上，最小化用户处理任务需要的时间

(8)

3 群智感知任务分配方法

数据驱动下交互网络群智感知任务分配方法通过信誉模型实现群智感知任务的分配，首先在交互网络中为不同的用户设置对应的信誉值，用户在交互网络中竞争感知任务时，交互网络优先将任务分配给信誉值高的用户，采用因子对用户处理任务的代价花费进行调节，在数据驱动下实现交互网络中群智感知任务的分配，具体步骤如下：

1)当交互网络群智感知环境中存在需要处理的任务时，对任务集T进行划分，得到多个子任务k⊂{1，2，…，K}。设U代表的是用户集，存在于任务发布区域中，划分任务集，得到Ui，其中i⊂{1，2，…，N}。

为用户i在交互网络群智感知环境中设置阈值Thresi，交互网络群智感知环境中的其他用户不知道该阈值，设Qi代表的是信誉值，由用户单个阈值和全部用户阈值得到，其计算公式如下

(9)

设uk=f(ξ，ξk)代表的是不同子任务对应的效用值，其计算公式如下

(10)

式中，ξk代表的是第k个子任务在交互网络中的大小；ξ代表的是所有任务在交互网络中的大小。

2)交互网络会选用信誉值大的用户处理子任务，参与在群智感知环境中处理任务的过程，用户在交互网络中处理任务k时，会生成花费代价。设ci=f(ξk，uk，Qi)代表的是子任务在交互网络中对应的代价函数，用户信誉值和子任务的大小都会影响用户的代价，用户代价分别与信誉值和子任务大小成反比和正比，其计算公式如下

(11)

式中，因子α和因子β符合下式：

α+β=10

(12)

3)为了促进用户在交互网络群智感知环境中处理任务，不同的子任务在交互网络中都对应着相应的报酬。设Pk=f(uk，N(t)，B(t))代表的是报酬函数，其中，N(t)代表的是用户在时间t时在交互网络中参与任务处理的比例；B(t)代表的是在时间t时交互网络中剩余的预算，其计算公式如下

(13)

式中，c代表的是常数。在上述方式中，初始段中交互网络提供的报酬较高，用来激励用户参与处理群智感知任务。用户参与交互网络中群智感知任务处理的比例逐渐升高，最后趋近于稳定，交互网络提供的报酬最终也会在某个值附近保持平稳[10]。

4)用户根据交互网络处理任务k需要支付的报酬Pk以及处理任务k付出的代价ci，决定是否接受交互网络中的群智感知任务，通过函数Ji=f(ci，Pk，Thresi)表示上述结果，函数的表达式如下

(14)

对比用户阈值Thresi和交互网络处理任务付出的代价ci与处理任务k需要支付的报酬Pk比例的大小，如果用户阈值小于比例，用户接受交互网络中存在的群智感知任务；如果用户阈值小于比例，用户不接受交互网络中存在的群智感知任务。

5)采用用户处理交互网络中群智感知任务对应的效用值对用户信誉值进行更行，利用更新后的信誉值进行交互网络中下一个群智感知任务的处理，直到将交互网络中存在的任务全部分配完为止，结束。

4 实验结果与分析

为了验证数据驱动下交互网络群智感知任务分配方法的整体有效性，需要进行测试，在本次测试过程中用到的数据来源为Andrews_sassy数据集和St Andrews大学，本次测试的平台为Visual C++开发的TTE平台。分别采用数据驱动下交互网络群智感知任务分配方法、基于混合任务网络的任务分配方法和基于Q学习的网络任务分配方法进行测试，对比三种不同方法分配任务花费的时间，测试结果如图1所示。

图1 三种不同方法的任务分配时间

分析图1(a)可知，采用数据驱动下交互网络群智感知任务分配方法分配任务时，花费的分配时间均在3s以内；分析图1(b)可知，采用基于混合任务网络的任务分配方法分配网络任务时，在第6次迭代中花费的分配时间高达13s，其余迭代中花费的分配时间均高于11s；分析图1(c)可知，采用基于Q学习的网络任务分配方法分配群智感知任务时，花费的时间均在7s以上，最高为10s。对比三种不同方法的测试结果可知，数据驱动下交互网络群智感知任务分配方法分配任务花费的时间均少于基于混合任务网络的任务分配方法和基于Q学习的网络任务分配方法分配任务花费的时间，因为所提方法在分配任务之前，基于服务约束和资源约束，在群智感知环境中最小化用户处理任务需要的时间，缩短了分配任务花费的时间，提高了数据驱动下交互网络群智感知任务分配方法的分配效率。

将任务完成率作为衡量指标进一步测试数据驱动下交互网络群智感知任务分配方法、基于混合任务网络的任务分配方法和基于Q学习的网络任务分配方法的有效性，测试结果如图2所示。

图2 三种不同方法的任务完成率

分析图2可知，数据驱动下交互网络群智感知任务分配方法的任务完成率在多次迭代中均在80%以上，基于混合任务网络的任务分配方法和基于Q学习的网络任务分配方法的任务完成率均在50%和20%附近波动。对比三种不同方法的任务完成率可知，数据驱动下交互网络群智感知任务分配方法的任务完成率最高，因为该方法利用信誉模型分配群智感知任务，优先将任务分配给信誉值高的用户，提高了群智感知任务的完成率，验证数据驱动下交互网络群智感知任务分配方法的任务完成率高。

5 结束语

移动智能终端具有高性能的内置，被广泛的应用到各个领域中，目前获取环境信息、感知数据的主要方法是群智感知技术，为激励并协调用户参与交互网络中任务的处理，保证数据在网络中的可靠性和有效性，需要研究群智感知任务分配方法，当前群智感知任务分配方法存在分配效率低和任务完成率低的问题，提出数据驱动下交互网络群智感知任务分配方法，可在短时间内完成群智感知任务的分配，并且用户完成任务的概率较高，解决了当前任务分配方法中存在的问题，为群智感知技术的发展奠定了基础。