面向移动群智感知的多任务分发算法
2017-04-17徐哲，李卓,2，陈昕
徐 哲，李 卓,2，陈 昕
(1.北京信息科技大学 计算机学院，北京 100101； 2.网络文化与数字传播北京市重点实验室(北京信息科技大学)，北京 100101)
(*通信作者电子邮箱lizhuo@bistu.edu.cn)
面向移动群智感知的多任务分发算法
徐 哲1，李 卓1,2*，陈 昕1
(1.北京信息科技大学 计算机学院，北京 100101； 2.网络文化与数字传播北京市重点实验室(北京信息科技大学)，北京 100101)
(*通信作者电子邮箱lizhuo@bistu.edu.cn)
针对在移动群智感知中基于机会通信完成数据传输会消耗大量时间成本的问题，提出了一种基于中枢节点的多任务分发(HTA)算法。该算法利用节点在移动网络中社交关系属性不同的特点，通过中枢节点选择算法将部分节点作为中枢节点，并将其用于协助任务请求节点分发任务。在任务请求节点与中枢节点相遇时，同时给中枢节点本身和它的从属节点分配任务，并由中枢节点负责向从属节点分发任务与回收任务结果。基于The ONE模拟器进行实验，与在线任务分配(NTA)算法相比，HTA算法时间成本平均降低了24.9%，同时任务完成率平均提高150%。实验结果表明，HTA算法能够提高任务的完成速度，降低时间成本消耗。
移动群智感知；机会通信；多任务分发；社交；中枢节点
0 引言
近年来，智能手机、平板电脑、可穿戴设备、车载感知设备等智能终端设备迅速发展普及。这些设备集成了越来越多的传感器，拥有越来越强大的计算、感知、存储和通信能力。随之出现了一种新的物联网感知方式——移动群智感知[1]。移动群智感知是将众包的思想与移动感知相结合的产物，将普通用户的移动设备作为基本感知单元，通过移动互联网进行有意识或无意识的协作，形成群智感知网络，实现感知任务分发与感知数据收集利用，最终完成大规模的、复杂的感知任务。
目前，移动群智感知已在环境监测[2-3]、智能交通[4]、公共安全[5]、城市环境感知[6]等领域有很多应用。但许多群智感知应用需要将大量的感知数据传输到数据中心，采用移动蜂窝网络将消耗大量的电量和流量成本。为节约数据传输成本，移动群智感知网络中的各节点通过短距离通信技术使用“存储-携带-转发”的数据传输机制(如图1)交换数据。这种数据传输机制是基于机会通信的传输机制[7]，通信机会的出现依赖于移动节点间的相遇。由于移动节点的位置会随着时间动态变化，同时移动节点间的相遇时间间隔也有大范围的波动，因此在数据传输阶段会消耗大量时间开销[8]，这将导致任务的整体时间成本巨大。要在最小化电量和流量成本的同时，实现较低的时间成本，则需要设计新的任务分发算法。
根据上述分析，由于移动节点间通信链路的间隙性等原因，如何快速有效地实现任务分发及数据收集是移动群智感知亟待解决的关键问题之一。由于移动节点的位置一直动态变化，难以准确对节点间的相遇机会进行建模和预测来优化感知任务的分发和分配。因此，如何确定高效任务分发、分配策略，将感知任务低成本、高效地传递给移动节点，既克服移动节点的带宽资源限制，同时保障数据收集效率是移动群智感知实用化的关键。
移动节点在现实环境中依据自身规律不停地移动，虽然存在随机性，但又具有显著的规律性[9]。同时移动机会网络拓扑演化特性受移动节点社交属性影响，因此移动节点间的相遇特性与其社交关系相关，两移动节点间的社交关系的强弱决定了彼此相遇机会的高低。社交网络分析(Social Network Analysis， SNA)[10]中有两个关键概念：社区(Communities)和中心性(Centrality)，从整个网络的角度抽象出节点间的社交关系，刻画了不同移动节点在整个网络中的影响力。如果两个彼此相遇概率较低的节点在高影响力节点的影响范围内，则它们利用高影响力的节点作为中继可提高节点间传递数据的效率，进而用于优化感知任务的分发与分配。因此，本文拟利用各用户节点的社会属性，通过利用合适的中继节点减少移动群智感知任务的时间成本。
图1 机会网络中的“存储-携带-转发”传输机制
本文主要研究移动节点的社交属性对数据转发性能及任务分配策略的影响。本文提出了一种面向移动群智感知的多任务分发算法——基于中枢节点的多任务分发(Hub-based multi-Task Assignment, HTA)算法，设计并实现了基于移动节点社交属性的中枢节点发现算法。本文基于St Andrews大学的Andrews_sassy数据集[11]和人工合成数据集，利用The ONE机会网络模拟器进行了实验。结果表明，比使用直接等待策略的在线任务分配(oNline Task Assignment, NTA)算法[12]缩短24.9%的任务平均完成时间，同时任务完成率也有平均150%的提高。
1 相关工作
移动群智感知任务可分为三个阶段：任务分发阶段、任务执行阶段和任务结果返回阶段。在任务分发阶段和任务结果返回阶段利用“存储-携带-转发”机制进行任务数据传递，需要解决数据传递时延高的问题，机会网络中的路由策略相关研究对该问题进行了广泛的研究。这方面代表性工作主要包括：洪泛[13]是最极端的一种数据路由策略，它的思想是节点将数据传递给每一个与自己接触的节点，通过网络中存在多份数据来提高数据的投递成功率和速率。由于网络中存在多份数据，使得网络负载增加，对每个智能设备的存储能力造成巨大压力，存储容量很快会被占满并无法再接收新的数据，导致网络性能降低。直接等待[14]是另一种极端的数据转发策略，它当且仅当源节点遇到目的节点时才投递数据，数据的投递成功率最低、速率最慢。喷射-等待[15]是机会网络中的一种典型数据转发策略，通过限制网络中消息的副本数，有效降低了网络负载。但是在移动机会网络中，节点由于社会关系的影响，转发能力存在较大的差异，造成喷射等待效率较低。文献[16]中提出的一种BUBBLE转发策略利用了人的社会性，根据节点的移动轨迹计算出每个节点的活跃度，然后依据节点活跃度在系统和社区的排名，进行消息路由策略的选择：源节点将消息传输给全局活跃度大于自己的节点，直到将消息传输到与目标节点位于同一社区的中继节点，然后中继节点再将消息传输给社区活跃度大于自己的节点，直到消息达到目的节点。该算法考虑社会关系对数据传输机会的影响，利用了活跃度高的节点与其他节点接触机会较多的特点，但要求机会网络中的各节点清楚所有节点的社区划分情况以及所有节点的活跃度，这使得该策略的应用环境受到限制，实用性面临挑战。
在任务执行阶段，节点处理在任务分发阶段接收到的任务，这里涉及到任务处理顺序的问题，目前最相关的研究在并行机调度领域。这方面代表性工作文献[17-18]针对传统并行机调度问题的研究进展作出了详细的总结。此外，文献[12]提出一种针对移动社交网络(与移动机会网络具有相似的用户移动模型)环境下多任务分配问题的算法，以动态在线模式运行的情况下得到的实验结果显示时间性能优于现有其他算法。
以上总结中，虽然有很多相关的研究成果可用于移动群智感知的任务分发问题中来，但是，各阶段的理论又很难结合在一起，比如，数据路由问题的解决方案要求在作出决策前确定要传输的数据，而任务分配算法则需要在任务分发者和普通节点相遇时再确定任务分配策略(即待传输的数据)。因此，为进一步减少感知任务的整体时间消耗，需要利用移动机会网络中的社交属性，提出新的算法，将任务分发与任务调度结合。
文献[12]对于任务分发和结果返回的路由问题采用的是直接等待策略，并对这种情况下的多任务分配问题提出了解决方案。与文献[12]不同的是，本文将任务分发与任务调度结合，使用单跳转发策略，通过增加中枢节点辅助任务请求者分发感知任务，并提出了一种新的多任务分配与分发算法。
2 网络模型与问题定义
在一个由n个用户组成的移动机会网络中，每个用户节点均携带着一个具有一定计算、存储、通信能力的智能设备，并按照各自的活动规律在地图中移动。假设有一个被称为任务分发者的特殊用户，用v0表示，他有m个感知任务需要分发给网络中的其他用户。如果v0与其他用户vi相遇，v0将分配若干手中的感知任务给vi。然后，vi将花费一定量的时间去完成分配给自己的任务。接着，vi在完成感知任务后，将一直等到自己与v0再次相遇时，将所得到的感知结果返回给v0。
本文假设：
1)近距离通信设备的传输性能满足：分配任务和返回结果等数据能够在节点间的一次机会连接断开之前传输完成。
2)移动用户i和j相遇间隔时间服从特征值为λi, j的指数分布。
3)每对用户之间的关系参数λi, j代表了在单位时间内，用户i与用户j之间的平均相遇次数。通过历史相遇记录或历史连接记录可以计算出参数λi, j。假设两用户在一段时间内的接触历史记录由集合C表示，每条记录用ci表示，则：
(1)
定义1 任务完成时间(Makespan)。一个感知任务的完成时间等于t1+t2+t3，其中：t1为任务分发者开始分发任务到节点i接收到该任务的时长，t2为任务在节点i手中停留的时长，t3为节点i将任务结果传递回任务分发者的时长。对于任务j的Makespan，使用M(j)表示。
本文假设，任务分发者v0有m个独立的感知任务，用J={j1,j2,…,jm}表示，这些任务可能属于不同的任务类型。为了简化问题，将任务的工作量(workload)统一为感知用时；使用t1,t2,…,tm表示且J中各任务的工作量大小,关系为t1≤t2≤…≤tm。假定v0将所有任务全部分配给其他用户，且每个任务只会分配给一名用户。
使用AM(Π)表示对于任务分配策略Π中的所有任务的AverageMakespan。公式表示为：
(2)
问题1 多任务分配问题。给定一个节点集合V={v0,v1,v2,…,vn-1}以及节点关系矩阵R[n][n]、一个感知任务集合J={J0,J1,J2,…,Jn-1}及其对应的任务工作量集合T={T1,T2,…,Tm}。其中R[n][n]表示节点i和节点j之间的单位时间内的平均相遇次数，则多任务分配问题是如何确定一个任务分配策略Π={J1,J2,…,Jn}，使AM(Π)最小。
在任务分发阶段之前，任务分发者需要确定任务的分配策略才能将任务分发给各节点，任务分发阶段和任务结果返回阶段的时间成本又是必须考虑的因素。但是由于节点的移动具有随机性，难以准确预测节点彼此何时相遇，所以任务分配策略难以实现最优。
定理1 多任务分配问题是NP-完全问题。
证明 首先，本文引入非相关并行机调度问题。该问题可描述为：任给m个工件，n台机器，对每个i=1,2,…,n和每个j=1,2,…,m，第j个工件在第i台机器上的加工时间为pij=ti+ti′+τj，对所有m个工件在n台机器上安排加工时间表，使得在这些机器上最后加工完的平均任务完成时间最短。
在清楚所有节点间相遇时间的情况下，设任务分发者与节点v1,v2,…,vn的相遇时间为t1,t2,…,tn，距离下次相遇的时间间隔为t1′,t2′,…,tn′，对于m个任务，第j个任务的执行时间为τj，则多任务分配问题与非相关并行机调度问题等价。
非相关并行机调度问题已被证明为NP-完全问题[19]，因此在清楚所有节点彼此相遇时间的情况下，多任务分配问题是NP-完全问题。清楚所有节点彼此相遇时间的是多任务分配问题的一个特例，因此多任务分配问题是NP-完全问题。
接下来将介绍利用移动节点社交属性提出的一种多任务分配算法。
3 基于节点社交属性的多任务分配算法
根据文献[12]所述，为实现最优任务分配策略，任务分发者应该在与某节点相遇时才确定对应需要分配的任务集。移动群智感知网络中的任务分发节点在遇到其他节点之前并不确定要分配给每个节点的任务集，更无法确定接收任务数据的目标节点。因此，目前针对机会网络的数据传输转发策略[13-16]并不直接适用于移动群智感知环境，这些策略均需要在数据传递初始阶段就确定要传递的数据。在群智感知的数据分发领域，目前广泛使用的策略是直接交付型，相当于直接等待策略。因此，通过整合任务分配策略与数据分发策略的决策环节，优化任务调度和数据分发流程，实现优化AM。
本文提出了一种借助中枢节点协助分发任务的任务分配(HTA)算法。该算法的主要思想是依据节点之间的社交属性筛选出中枢节点和对应的从属节点，任务分发者与中枢节点相遇时同时确定从属节点的任务分配，然后借助该中枢节点协助分发从属节点的任务。在完整介绍该算法前，先对中枢节点选择算法进行完整阐述。
3.1 中枢节点选择算法
给定一个节点集合V={v0,v1,v2,…,vn-1}以及节点关系矩阵λ[n][n]。其中λi, j表示节点i和节点j之间的单位时间内的平均相遇次数。令ti, j表示节点i与节点j通信的时间成本，即节点i与节点j相遇的平均时间间隔。
问题2 中枢节点选择问题。从除v0以外的其他节点中选择一个节点子集A，使v0仅向节点集A中的节点发送消息，最多通过一次转发就可使所有节点接收到消息，且t0,i+ti, j≤t0, j(i∈A,j∉A)。
根据对本文要解决问题的分析，可以得出中枢节点在整个网络中应该是影响力较大的节点。中枢节点选择问题可以通过转换为求Top-K问题[20]，然后使用相应的求解办法求出结果，文献[21]提出的算法能够找出重要节点。但，针对本文问题的分析，发现得到重要节点集后，重要节点以外的其他节点的归属问题依然没有解决。
通过分析，得出中枢节点应当具有以下属性：某从属节点vi与中枢节点的相遇概率应高于节点vi与任务分发节点v0之间的相遇概率。因此，本文提出了一种新的中枢节点选择算法。直接根据节点间相遇概率的高低确定中枢节点。根据2.1节对移动社交网络中的各节点的关系属性λ的定义，每两个节点之间的关系属性λ代表了这两个节点的相遇概率高低，λ的数值越大对应两节点的相遇概率越高；另一方面它也反映了这两个节点关系远近程度。
中枢节点选择算法的基本思路是：要判断vj是否为中枢节点，只需遍历关系矩阵的每一行，判断第j列的每一个值在其对应的第i行中是否为最大值，如果为最大值则vj是vi的中枢节点。
具体实现方法是：若节点vj是另一节点vi的中枢节点，则在关系矩阵的第i行中，λi, j是最大值。要判断vj是否为中枢节点，只需遍历关系矩阵的每一行，求出其中的最大值，然后判断该值是否在第j列。算法具体步骤见算法1。
在算法1第1)步中的result记录了节点Vi的从属节点，如果result为空集，则表示节点vi不作为中枢节点。
下面用一个简单的例子对该算法进行解释：首先，假设一个移动社交网络(Mobile Social Network, MSN)中有5个节点，其中的关系矩阵为：
先判断节点1是否为某些节点的中枢节点：首先，在第2行中寻找最大值，第2行的最大值在第3列，不在第1列，所以节点1不是节点2的中枢节点；然后继续在第3行中选择最大值，第3行中的最大值在第2列，也不在第1列，所以节点1不是节点3的中枢节点；一直扫描到第5行，发现第一列中的数值在对应的每一行里都不是最大值，所以，得到的计算结果是节点1不作为中枢节点。再来尝试判断节点2是否为某些节点的中枢节点，可以发现在第3行和第4行中，第2列的数值为所在行的最大值，说明节点3和节点4均与节点2的相遇频率高于与其他节点的相遇频率，所以节点2作为节点3和节点4的中枢节点。依次判断节点3、4、5可以计算得，节点3是节点1、2的中枢节点，节点4是节点5的中枢节点，节点5不是中枢节点
算法1 中枢节点选择算法。
输入：节点集合V={v0,v1,v2,…,vn-1}；关系矩阵λ[n][n]。 输出：每个节点对应的从属节点集合，若某节点的从属节点集为空，则其不作为中枢节点。
1)
result=[∅,∅,…,∅],result初始状态有n个空集
2)
fori← 1 ton-1:
3)
forj ← 1ton-1:
4)
max=λj,0
5)
indexmax=0
6)
fork ← 1ton-1:
7)
如果λj,k大于max
8)
max=λj,k
9)
indexmax=k
10)
endfor
11)
如果indexmax等于i，则将vj加入result[i]
12)
endfor
13)
endfor
14)
输出result
通过分析，该算法的时间复杂度为O(n2)，且仅计算了一个节点是否为中枢节点，若要对所有节点均计算一遍，则时间复杂度为O(n3)。在实际应用中还可以采用另一种优化后的实现，一次求出所有中枢节点及其从属节点，时间复杂度为O(n2)。
算法的主要思路与算法1基本相同，主要区别在第7)～10)步上，具体步骤见算法2。
算法2 优化后的中枢节点选择算法。
输入：节点集合V={v0,v1,v2,…,vn-1}；关系矩阵λ[n][n]。 输出：每个节点对应的从属节点集合，若某节点的从属节点集为空，则其不作为中枢节点。
1)
result=[∅,∅,…,∅],result初始状态有n个空集
2)
forj← 1 ton-1:
3)
max=λj,0
4)
indexmax=0
5)
fork ← 1ton-1:
6)
如果λj,k大于max
7)
max=λj,k
8)
indexmax=k
9)
endfor
10)
result[indexmax]=result[indexmax]+{vj}
11)
end for
12)
输出result
3.2 任务分配与分发算法
通过3.1节的介绍，清楚了如何对中枢节点进行选择，本节将结合中枢节点选择算法，计算感知任务集的分配策略并确定分发路径。算法完整过程见算法3。
算法3 任务分配与分发算法。
输入：待分配的任务集J={j1,j2,…,jm;t1≤t2≤…≤tm}；待分配任务的节点集V={v1,v2,…,vn}；关系矩阵λ[n][n]；任务分发者遇到的节点对应序号i。 输出：任务集Ji及JF={Jj|j∈Fi}，Fi是vi的从属节点集。
当任务分发者v0与节点vi相遇，执行以下步骤：
1)
在中枢节点选择算法得到的所有从属节点集中找出Fi
2)
如果Fi非空:
3)
将vi作为中枢节点，且Fi对应中枢节点vi的从属节点集
4)
fork← 1 ton-1:
5)
IPTk=2/λ0,k
6)
endfor
7)
IPTi=1/λ0,i,IPTj=1/λ0,i+1/λi, j,j∈Fi
8)
m等于剩余未分配任务数量
9)
forp← 1 tom:
10)
找出IPT值最小的节点对应的序号indexmin
11)
Jindexmin=Jindexmin+{jp}
12)
IPTindexmin=IPTindexmin+tp
13)
如果indexmin等于i或indexmin对应节点在Fi集中，则：
14)
J=J-{jp}
15)
endfor
16)
输出Ji及JF={Jj|j∈Fi}，其余节点得到的结果抛弃
每次执行任务分配算法后，只将相遇节点及其从属节点(如果相遇节点被作为中枢节点)分配到的任务分发出去，其余节点分配到的任务只是暂时的，不作为最终结果。
在中枢节点选择算法中有可能会出现这样的情况，两个节点vi和vj互为中枢节点，则处理方案为，任务分发者v0先与节点vi相遇，就将vi作为vj的中枢节点。其次，消息准备从中枢节点传递给从属节点前，从属节点判断消息的上一次传递路径是否为从属节点本身，避免循环传递消息，即浪费网络资源，又有可能造成死循环。之所以可能出现上述问题，是因为从从属节点的角度看，自身也是中枢节点，中枢节点也是从属节点的从属节点。
本文使用算法3将任务分配和分发收集的完整流程优化为以下步骤：
1)在任务分发者v0，从开始分发感知任务起第一次遇到节点vi时，执行任务分配和分发算法3，计算出节点vi及其从属节点(若节点vi被确定为中枢节点)的任务分配策略。将vi及其从属节点从节点集V中移除。
2)中枢节点vi接收到任务分配策略后，立即开始按照工作量从小到大的顺序依次执行分配给自己的感知任务；同时在之后的第一次遇到属于自己的从属节点时，将自己保存的从属节点任务分配策略分发给从属节点。当节点vi再一次遇到任务分发者时，将自己已经完成的感知任务结果和来自从属节点的感知任务结果传递给任务分发者。
3)从属节点也开始按照工作量从小到大的顺序依次执行分配给自己的感知任务。等到再一次自己遇到自己的中枢节点时，将自己已经完成的感知任务结果传递给中枢节点。
4)一直等到任务分发者接收到所有感知任务的执行结果后，过程终止。
下面对该任务分配与分发算法的实际应用可行性进行分析。算法1至3将网络全局信息即关系矩阵λ[n][n]作为输入，且仅被任务分发者使用，而剩余其他节点在完成感知任务的整个流程中均不需要关系矩阵λ[n][n]。而在实际系统实现中可参与群智感知任务的移动节点会向系统提交注册信息，可要求移动节点上报自己与整个网络其他节点的接触历史用于计算出整个网络各节点之间的关系。任务分发者通过系统获取参与群智感知任务的节点集的同时，获取关系矩阵λ[n][n]即可。因此，由于只有任务分发者一个节点需要了解移动机会网络的全局信息，降低了系统实现难度，具有实际应用可行性。
4 实验结果与分析
4.1 实验环境
本文使用TheONE模拟器对HTA算法的性能进行验证，另外将NTA作为对照算法。本次实验所采用的现实环境数据集是来自StAndrews大学的Andrews_sassy数据集[11]。该数据集是由来自StAndrews大学的25名志愿者各自所携带的装有传感器的智能设备记录的彼此相遇记录和这些志愿者在Facebook上的社交网络数据组成。另外本次实验还使用了人工生成的用户接触记录的虚拟数据集。用于生成数据所采用的用户移动模型为工作日移动模型(WorkingDayMovementmodel,WDM)[22]，模拟了40位用户持续1 944h的活动。各数据集的详细参数如表1。本文将每个数据集中前三分之一时间的相遇记录用于计算用户节点彼此的社交网络关系权重，后三分之二时间的相遇记录用于模拟实验。
表1 实验所用数据集的统计信息
此外，针对存在的两个中枢节点选择算法1、2，本文实验使用改进后的算法2。
为了提高实验说服力，达到充分实验的目的，将每个数据集中的各个节点分别作为任务分发者分配一次感知任务，通过节点在移动网络中所具有的社交属性不同来揭示算法在各种环境下的性能表现。此外，实验中用到的感知任务集通过程序随机生成，由多组具有不同任务数量和平均workload的数据组成，参数设置如表2。其中任务数量为100，200和300，平均workload为500,600,…,1 000,2 000,…,5 000s。此外，本次实验不考虑任务的时效性问题，即任务不会过期，只要任务的结果能够传回任务分发者即视为任务完成。通过简单计算，可以得出本次实验在使用Andrews_sassy数据集时，一共进行了3×10×25=750次完整的模拟移动群智感知过程；在使用人工数据时，一共进行了3×10×27=810次完整的模拟移动群智感知过程。实验的结果采用相同感知任务集下每个节点做一次任务分发者时的平均任务完成率和平均AM为评价指标。
4.2 实验结果
先对真实数据集下的实验进行分析。图2显示了在Andrew_sassy数据集和不同任务集下，HTA和NTA在AM方面的相对性能对比结果。整体而言，HTA大幅缩短了完成任务所需要的平均时间，平均缩短了24.9%。同时，如图3所示，与NTA相比，HTA在绝大多数节点上还实现了任务完成率的大幅提高；对于所有节点，平均提高了150%。按任务集的平均工作量对实验分组，结果显示任务集数量越大，HTA算法对平均完成时间所缩短的百分比越大、任务抵达率所提高的百分比也越大。
表2 实验所用任务集的参数配置
图2 HTA相比NTA的AM提升百分比(Andrew_sassy数据集)
图3 HTA相比NTA的消息抵达率提升百分比(Andrew_sassy数据集)
下面对人工生成的模拟数据集进行性能分析。在所有任务集下，使用HTA得到的AM比使用NTA得到的AM平均缩短34.9%，详细的AM性能比较如图4；同时消息抵达率平均有111.1%的提高，详细的消息抵达率性能比较如图5。
图4 HTA相比NTA的AM提升百分比(人工合成数据集)
通过图2和图4，还可发现，按任务集的任务数量分组后，对不同平均工作量的任务集进行对比，结果显示HTA算法对任务的AM所实现的改进百分比随任务集平均工作量的增加而有所降低，但缩短的绝对时间长度是增加的。通过分析得出，这一改进百分比变小的现象是由于任务工作量增加，任务分发阶段消耗的时间t1与任务结果收集阶段消耗的时间t3所占比重减小、任务执行阶段消耗的时间t2所占比重增加的原因造成的。因此，可以得出结论，本文所提算法对工作量越小的感知任务集越适用。
图5 HTA相比NTA的消息抵达率提升百分比(人工合成数据集)
根据性能分析，发现HTA算法对AM性能的改进程度有差异，根据数据集的具体特点进行分析得出：因为HTA算法依赖于移动机会网络中各节点之间的稳定强关系，而作为任务分发者的节点遇到的其他节点在移动机会网络中的活跃程度各不相同，在任务分发者节点与其他普通节点的相遇次数较多时，并不能发挥中枢节点协助分发与收集任务的功效；另一个原因是，某些节点作为任务分发者时，与其他节点的相遇次数过少或过于集中，不能满足分配感知任务和接收感知任务结果的需要，换句话说，就是受限于采用的数据集。那么这表明，移动机会网络的规模越大，越能发挥HTA算法在缩短任务分发与收集阶段时间消耗的优势。
5 结语
如何确定高效的任务分发与分配策略是移动群智感知数据收集的核心问题之一。本文将社交网络分析中的中心性和社区概念与任务分配策略结合，提出一种最小化任务平均完成时间的基于中枢的多任务分配(HTA)算法。该算法的核心思想是经过中枢节点选择算法筛选出的部分节点被用于辅助分发和收集任务数据，并参与决策任务分配策略，以进一步降低移动群智感知任务在数据分发与收集上的时间消耗。实验结果显示，本文提出的HTA算法比NTA算法平均缩短了任务完成时间24.9%，同时任务抵达率平均提高了150%。经过对实验结果的进一步分析，得出该算法在工作量小于1 000s的任务集下更能发挥优势。
此外，本文所提算法假设感知任务分配给不同移动节点能够得到相同结果。考虑到不同节点的活跃度、任务完成能力等会影响感知任务的完成质量，以及感知任务可能对地理位置有要求，在实现最小化平均完成时间的同时，如何保证最低数据完成质量要求将是下一步的研究重点。
)
[1] 赵东,马华东.群智感知网络的发展及挑战[J].信息通信技术,2014(5):66-70.(ZHAOD,MAHD.Developmentandchallengesofcrowdsensingnetworks[J].InformationandCommunicationsTechnologies, 2014(5): 66-70.)
[2]DUTTAP,AOKIP,KUMARN,etal.Commonsense:participatoryurbansensingusinganetworkofhandheldairqualitymonitors[C]//SenSys’ 09:Proceedingsofthe7thACMConferenceonEmbeddedNetworkedSensorSystems.NewYork:ACM, 2009: 349-350.
[3]KIMS,ROBSONC,ZIMMERMANT,etal.Creekwatch:pairingusefulnessandusabilityforsuccessfulcitizenscience[C]//CHI’ 11:Proceedingsofthe2011SIGCHIConferenceonHumanFactorsinComputingSystems.NewYork:ACM, 2011: 2125-2134.
[4]GANTIR,PHAMN,AHMADIH,etal.GreenGPS:aparticipatorysensingfuel-efficientmapsapplication[C]//MobiSys’ 10:Proceedingsofthe8thInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2010: 151-164.
[5]SIMOENSP,XIAOY,PILLAIP,etal.Scalablecrowdsourcingofvideofrommobiledevices[C]//MobiSys’ 13:Proceedingsofthe11thAnnualInternationalConferenceonMobileSystems,Applications,andServices.NewYork:ACM, 2013: 139-152.
[6]RANARK,CHOUCT,KANHERESS,etal.Ear-phone:anend-to-endparticipatoryurbannoisemappingsystem[C]//Proceedingsofthe9thACM/IEEEInternationalConferenceonInformationProcessinginSensorNetworks.NewYork:ACM, 2010: 105-116.
[7] 陈翔,徐佳,吴敏,等.基于社会行为分析的群智感知数据收集研究[J].计算机应用研究,2015,32(12):3534-3541.(CHENX,XUJ,WUM,etal.Researchofdatacollectiontechnologyincrowdsensingbasedonsocialbehavioranalysis[J].ApplicationResearchofComputers, 2015, 32(12): 3534-3541.)
[8]PELUSIL,PASSARELLAA,CONTIM.Opportunisticnetwor-king:dataforwardingindisconnectedmobileAdHocnetworks[J].IEEECommunicationsMagazine, 2006, 44(11): 134-141.
[9]BULUTE,SZYMANSKIBK.Exploitingfriendshiprelationsforefficientroutinginmobilesocialnetworks[J].IEEETransactionsonParallelandDistributedSystems, 2012, 23(12): 2254-2265.
[10]SRINIVASANV,MOTANIM,OOIWT.Analysisandimplicationsofstudentcontactpatternsderivedfromcampusschedules[C]//Proceedingsofthe12thAnnualInternationalConferenceonMobileComputingandNetworking.NewYork:ACM, 2006: 86-97.
[11]BIGWOODG,HENDERSONT,REHUNATHAND,etal.CRAWDADdatasetst_andrews_sassy[DS/OL].[2011-06-03]http://crawdad.org/st_andrews/sassy/20110603.
[12]XIAOM,WUJ,HUANGL,etal.Multi-taskassignmentforcrowdsensinginmobilesocialnetworks[C]//INFOCOM2015:Proceedingsofthe2015IEEEConferenceonComputerCommunications.Piscataway,NJ:IEEE, 2015: 2227-2235.
[13]ZHANGX,NEGLIAG,KUROSEJ,etal.Performancemodelingofepidemicrouting[J].ComputerNetworks, 2007, 51(10): 2867-2891.
[14]FRENKIELRH,BADRINATHBR,BORRASJ,etal.Theinfostationschallenge:Balancingcostandubiquityindeliveringwirelessdata[J].IEEEPersonalCommunications, 2000, 7(2): 66-71.
[15]SPYROPOULOST,PSOUNISK,RAGHAVENDRACS.Sprayandwait:anefficientroutingschemeforintermittentlyconnectedmobilenetworks[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelay-TolerantNetworking.NewYork:ACM, 2005: 252-259.
[16] HUI P, CROWCROFT J, YONEKI E.BUBBLE rap: social-based forwarding in delay tolerant networks [C]// Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York: ACM, 2008: 241-250.
[17] ALLAHVERDI A, NG C, CHENG T, et al.A survey of scheduling problems with setup times or costs [J].European Journal of Operational Research, 2008, 187(3): 985-1032.
[18] CHENG T, SIN C.A state-of-the-art review of parallel-machine scheduling research [J].European Journal of Operational Research, 1990, 47(3): 271-292.
[19] LENSTRA J K, SHMOYS D B, TARDOS É.Approximation algorithms for scheduling unrelated parallel machines [J].Mathematical Programming, 1990, 46(1/2/3): 259-271.
[20] KEMPE D, KLEINBERG J, TARDOS É.Maximizing the spread of influence through a social network [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2003: 137-146.
[21] WANG Y, CONG G, SONG G, et al.Community-based greedy algorithm for mining top-kinfluential nodes in mobile social networks [C]// Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York: ACM, 2010: 1039-1048.
This work is partially supported by the National Natural Science Foundation of China (61370065, 61502040), the Program for Excellent Talents in Beijing Municipality (2014000020124G099), the Open Program of the Beijing Key Laboratory of Internet Culture and Digital Dissemination (ICDD201406), the Program of Key Laboratory of Modern Measurement & Control Technology (Ministry of Education)/Beijing Key Laboratory of Electromechanical System Measurement and Control (KF20151123205).
XU Zhe, born in 1993, M.S.candidate.His research interests include crowdsensing.
LI Zhuo, born in 1983, Ph.D., lecturer.His research interests include mobile wireless networks, distributed computing.
CHEN Xin, born in 1965, Ph.D., professor.His research interests include network performance evaluation, network security.
Multi-task assignment algorithm for mobile crowdsensing
XU Zhe1, LI Zhuo1,2*, CHEN Xin1
(1.SchoolofComputerScience,BeijingInformationScienceandTechnologyUniversity,Beijing100101,China;2.BeijingKeyLaboratoryofInternetCultureandDigitalDissemination(BeijingInformationScienceandTechnologyUniversity),Beijing100101,China)
Data transmission based on opportunistic communication in mobile crowdsensing may take a long period of time.To address this issue, a new Hub-based multi-Task Assignment (HTA) algorithm was proposed.In this algorithm, some nodes were selected to perform as the hubs which could help the requester node to deliver the tasks, according to the different characteristics of the social relationship of the nodes in mobile networks.When the task requester encountered a hub node, the hub node itself and its slave nodes were assigned tasks.After that, the hub node would distribute the tasks to the salve nodes, and received the results from them.Simulations were conducted on The ONE simulator.Compared with the oNline Task Assignment (NTA) algorithm, HTA algorithm reduced the time cost by 24.9% on average and improved the task completion ratio by 150% on average.The experimental results demonstrate that HTA algorithm can accelerate the accomplishment speed of the task and reduce the time cost.
mobile crowdsensing; opportunistic communication; multi-task assignment; social relationship; hub node
2016-08-01;
2016-08-12。 基金项目:国家自然科学基金资助项目(61370065, 61502040)；北京市优秀人才培养资助青年骨干个人项目(2014000020124G099)；网络文化与数字传播北京市重点实验室资助项目(ICDD201406)；现代测控技术教育部重点实验室/机电系统测控北京市重点实验室资助项目(KF20151123205)。
徐哲(1993—)，男，山东阳谷人，硕士研究生，主要研究方向：移动群智感知； 李卓(1983—)，男，河南南阳人，讲师，博士，CCF会员，主要研究方向：移动无线网络、分布式计算； 陈昕(1965—)，男，江西南昌人，教授，博士，CCF会员，主要研究方向：网络性能评价、网络安全。
1001-9081(2017)01-0018-06
10.11772/j.issn.1001-9081.2017.01.0018
TP393.01
A
