2. 西安交通大学 陕西省计算机网络重点实验室, 西安 710049
针对节点移动性、社会性及复杂性给众包服务带来的挑战,研究了可信协作众包机制,提出基于层次分析法的服务节点发现和选择算法,定义服务质量因子、链路可靠性因子和区域热度因子等众包决策因子,实现基于分级激励的感知任务众包分配. 仿真实验进一步验证了所提方法的正确性和有效性.
2. Shaanxi Province Key Laboratory of Computer Network, Xi'an Jiaotong University, Xi'an 710049, China
According to the mobility, sociality and complexity of persons, how to achieve crowdsourcing allocation was noticed based on credible interactions between users in the article. First, a new credible crowdsourcing assignment model was proposed based on social relationships cognition and community detection. Then, how to reasonably assess user crowdsourcing preferences, service quality factor, link reliability factor, and region heat factor was defined, and a crowdsourcing algorithm based on analytic hierarchy process(AHP) theory was given. Simulation was conducted to prove the correctness and effectiveness of method.
群智感知是指利用节点(人)及所携带的各种智能终端来实现对物理世界的实时感知，它通过节点的移动性和社会性等特性解决现实网络的感知空洞问题，以此提高情景感知服务的实时性和可靠性[1]. 在研究场景中，面向群智感知的服务众包是通过分析节点之间的移动性、社会性和信任关系，将感知任务按照一定约束机制进行合理分配，以此实现感知任务的可靠传递和有效分发，并最终提高服务效率.
通过分析可知[2, 3, 4]，现有的众包技术都是在一定的激励条件下进行任务分发，采取的协作机制通常只有集中式或分布式2种模式，研究关注的重点都是任务自身，移动节点在众包过程中往往处于被动地位，较少融合多维环境信息，且很少考虑到用户的社会化信息. 此外，在众包过程中，对于用户之间的信任关系，用户与任务之间的关联性和差异性，用户的体验与任务之间的粘合度等问题都没有更深入的研究，这都将影响移动环境下的服务众包效率和精度.
在群智感知服务众包过程中，由于服务节点的移动性、随机性和复杂性，服务模式将有本质的改变. 服务众包的成功与否不仅要考虑到服务提供者的服务能力，例如，服务提供者的历史服务质量、服务交互时间等. 同时也要关注具体的服务环境，例如，服务交互链路的可靠性、目标服务区域的热度等因素. 因此，笔者将针对移动环境下的服务众包方法展开研究，以前期移动节点社会关系、活动规律、网络结构划分等为基础[5]，研究基于可信交互的服务众包方法. 通过定义并计算包括服务质量因子(SQF，service quality factor)、链路可靠性因子(LRF，link reliability factor)和区域热度因子(RHF，region heat factor)等在内的决策因子，提出一种基于层次分析法(AHP，analytic hierarchy process)的众包节点发现和选择算法，对用户服务请求进行合理量化. 同时，在众包服务过程中，引入激励机制，构建面向不同感知需求的众包节点候选集，实现满足用户偏好的众包分配机制.
1 众包决策因子的计算 1.1 服务质量因子SQF是服务过程中对节点相关历史服务参数的客观评价，SQF的定义体现了服务提供者的服务质量.
定义1 服务节点Mi在位置Lk的SQF与该节点在此位置的历史服务记录H有关，设节点的历史服务参数具体包括服务节点成功率Ssucc、平均服务延迟Sdel、服务满意度Ssat表示. 计算公式分别为
| \[\left. {\begin{array}{*{20}{l}} \begin{array}{l} {S_{{\rm{succ}}}}({M_i},{L_k}) = \frac{{{N_{{\rm{succ}}}}}}{{{N_{total}} - {N_{{\rm{succ}}}}}}\\ \end{array}\\ {{S_{del}}({M_i},{L_k}) = \frac{{\sum\limits_{{h_j} \in H} {d({h_j})} }}{{{\rm{|}}s({M_i},{L_k}) - e({M_i},{L_k}){\rm{|}}}}}\\ {}\\ {{S_{sat}}({M_i},{L_k}) = \sum\limits_{{h_j} \in H} {{\rho _{{h_j}}}d({h_j})} } \end{array}} \right\}\] | (1) |
其中：Nsucc为历史服务成功次数，Ntotal为历史服务总数，d(hj)为历史服务hj的持续时间(hj∈H)，s(Mi,Lk)为节点Mi到达位置Lk的时间，e(Mi,Lk)为节点Mi离开位置Lk的时间.
ρ为历史服务记录衰减因子. 历史服务记录是对服务节点过去相关服务参数的一个记录，同时也是在未来节点选择过程中的一个重要决策依据. 考虑到服务记录的实效性，它是一种随时间变化而动态衰减的量，即所隔时间越久，以前记录的参考价值对现在服务决策的贡献越小，ρhj的计算公式为
| \[{\rho _{{h_j}}} = \left\{ \begin{array}{l} 1,\;\;{h_j} = H\\ \rho ({h_j} - 1) = \rho ({h_j}) - 1/H,\;\;1 \le {h_j} \le H \end{array} \right.\] | (2) |
由于节点的移动性、随机性和复杂性，服务模式将有本质的改变. 服务众包的成功与否不仅要考虑到服务提供者的服务能力，同时也要关注服务交互链路的可靠度，可靠的链路服务请求将更加有助于服务的最终成功. 因此，在选择合适的众包节点时，除了考虑服务提供者本身的服务质量，同时需要考虑服务众包链路建立的可靠性.
定义2 节点Mi在位置Lk的LRF与该节点在此位置的历史服务记录H有关，在研究中，影响LRF因子的参数包括链路强度Slink、衰减因子ρ和转发次数FN. 具体计算公式为
| \[{S_{link}}({M_i},{L_k}) = \sum\limits_{{h_j} \in H} {{\rho _{{h_j}}}{E_{{M_i},{L_k}}}({h_j})} \] | (3) |
其中：ρ为衰减因子，与式(2)一致，EMi,Lk(hj)为移动节点Mi在位置Lk的历史服务hj中，感知服务请求链路的强度，它基于转发节点间的社会关系，计算公式为
| \[{E_{{M_i},{L_k}}}({h_j}) = \prod\limits_{i = 1}^{{\rm{FN}}} {V({x_i},{x_{SUCC}})} \] | (4) |
其中：FN为服务请求链路中源节点到目标节点的个数，V(xi,xsucc)为从源节点到目的节点的社会关系传递路径上移动节点xi与它的后继节点的社会关系值. 节点间社会关系的计算可由笔者前期工作中获得[5].
1.3 区域热度因子感知区域是对移动节点在时间周期内活动规律的提取和凝聚，是宏观上对移动节点活动范围的有效划分. 在移动感知服务中，服务请求的提出和最终众包服务的实现都是基于不同感知区域的，感知区域的热度维度则是在时间周期内，统计移动节点到达不同区域的频繁度. 考虑到移动节点的活动轨迹具有时空特性，一个区域的热度不仅与到达次数有关，而且与在该区域的持续时间有关.
定义3 设节点Mi在活动范围U内到达不同感知区域的热度RHF与节点在不同位置到达频率Sfre和持续时间Sdur相关. 具体计算公式为
| \[{S_{dur}}({M_i},{L_k}) = \exp \left( {\frac{{\sum\limits_{{L_k} \in U} {e({M_i},{L_k}) - s({M_i},{L_k}){\rm{|}}} }}{{{S_{fre}}({M_i},{L_k})}}} \right)\] | (5) |
其中：Sdur(Mi,Lk)为统计时间周期内移动节点Mi在同一感知区域Lk的持续时间，Sfre(Mi,Lk)为统计时间周期内移动节点Mi在到达同一感知区域Lk的频率.
| \[\left. \begin{array}{l} {S_{{\rm{fre}}}}({M_i},{L_k}) = 1 + P({M_i},{L_k})1{\rm{b}}P({M_i},{L_k})\\ P({M_i},{L_k}) = \frac{{{N_{{\rm{num}}}}({M_i},{L_k})}}{{\sum\limits_{{L_j} \in U} {{N_{{\rm{num}}}}({M_i},{L_j})} }} \end{array} \right\}\] | (6) |
其中：P(Mi,Lk)为移动节点Mi到达位置Lk的概率，Nnum(Mi,Lk)为统计时间周期内移动节点Mi到达位置Lk的次数.
2 基于AHP的服务众包算法 2.1 候选服务节点的选择如图 1所示，模型根据用户的服务需求特性划分为服务质量维度、链路可靠性维度以及区域热度维度. 其中，服务质量维度包括服务节点成功率、服务平均延迟和服务满意度. 这些参数都是针对服务交互过程中，服务提供者自身的服务质量出发，考虑影响用户服务体验的参数. 服务链路维度则是从交互链路可靠性出发，分析影响链路可靠的具体参数. 笔者在构建3维服务众包模型的基础上，结合AHP层次化系统分析思想对用户在服务节点选择过程中带有主观性、模糊性的约束条件进行分析和量化处理，实现满足不同服务需求的节点选择策略.
|
图1 基于AHP的服务节点选择层次模块 |
任务激励是指通过设计适当的奖酬措施，激发用户参与众包服务的积极性，提高最终服务的成功率和服务质量. 针对现有激励机制存在的不足，笔者拟提出一种基于分级激励(Elo)的任务分配方法，该方法以服务节点在众包过程中的消费付出和收益作为奖励影响因子K，依据分级模型计算竞标节点的胜出概率W(i)，并根据平均胜出概率和K确定最终众包服务节点的服务收益R(i). 该激励方法在计算过程中不仅充分考虑到竞标节点以往的服务质量，同时通过构建等级量表和区间尺度，避免因处于不同服务级别而造成的收益差距过大. 这样既能充分调动“弱”节点的服务积极性，同时保证“强”节点持续提供高质量服务以获得更多奖励，从而保证众包感知的服务质量. 具体步骤如下.
步骤1 服务发布. 服务请求者向服务平台提出感知服务请求，并设定激励影响因子K作为后期服务评价过程中的奖励分配基数.
步骤2 胜出概率计算. 服务提供者根据历史服务记录H选择最优节点作为胜出节点i，并将它与其余N-1个非胜出节点进行竞争评价.
| \[\left. \begin{array}{l} W(i) = \frac{1}{{1 + {{10}^{\frac{{{R_j} - {R_i}}}{{400}}}}}}\\ W(j) = \frac{1}{{1 + {{10}^{\frac{{{R_i} - {R_j}}}{{400}}}}}} \end{array} \right\}\] | (7) |
其中：Ri和Rj分别为节点i与j的初始积分值，W(i)和W(j)分别为节点i与j在一次竞争中的胜出概率.
步骤3 服务节点激励计算. 根据胜出节点与其他N-1个非胜出节点形成的N-1个竞争过程，得到胜出节点的平均胜率，进而得到胜出节点的奖励.
| \[\left. \begin{array}{l} \overline W (i) = \sum\limits_{j = 1}^{N - 1} {W(j)} \\ {{R'}_i} = {R_i} + K(1 - W(i)) \end{array} \right\}\] | (8) |
步骤4 计算候选节点相关服务参数的不同分值，并按照大小进行最优排序.
3 实验结果与分析为了分析笔者所提模型与算法的正确性和有效性，实验通过自主开发的移动感知平台和Matlab软件进行测试和分析. 原始数据集选用MIT的Reality Mining提供的标准数据集[6]. 通过收集数据集中节点的相关服务信息，模拟从众包服务请求提交到众包服务节点的发现和选择过程. 实验主要参数设置如下：节点数N为64个，采样天数为128 d，采样间隔t为30min，服务请求阈值α为10min.
3.1 模型正确性分析在模型正确性分析中，把服务众包过程中用户偏好选择分为代表性的3类： 1)对服务可靠性因子要求最高的用户RLRF； 2)对服务质量因子要求最高的用户RSQF； 3)对感知区域热度因子要求最高的用户RRHF. 分别计算在不同偏好选择下的候选节点排序.
通过设置不同的服务众包偏好，利用AHP算法生成相应的属性权重，可以对10个候选服务众包节点进行评判，计算结果如图 2所示. 可以看出，对于RLRF用户来说，移动节点9和3均是合适的选择，而节点1和3是满足RSQF用户的需求. 如果用户对RRHF要求较高，则节点9和10都可以考虑.
|
图2 模型正确性分析 |
服务众包的目的是为移动环境下大规模的分散目标或区域数据的感知和服务获取提供一种智能化手段，提高移动感知的服务效率. 为了验证模型与算法的有效性，实验将考察2种典型情况：1)无具体服务众包偏好下的随机节点选择策略(RSA，random selection approach)，即随机选择候选节点；2)基于Elo算法的最优选择策略，即根据用户服务众包偏好选择能够实现感知服务的最优节点，实验以SQF决策因子为服务偏好属性.
实验在不同服务请求次数情况下，计算服务众包模型的执行效率，如图 3所示. 其中，K代表不同的分配激励技术. 在服务过程中，不同的众包策略在执行效率上将会产生较大的差异. 当K=10时，模型的平均成功率要高出RSA 16.5%左右. 分析原因可知，笔者所提模型在服务众包过程中不仅考虑节点的服务属性偏好，同时引入激励机制，能够进一步提高节点参与服务的积极性，而RSA只是单纯地采用随机选择方法，对节点自身服务质量、活动规律和链路可靠性等因素排除在外. 故笔者所提模型与算法在提高服务交互成功率和减少通信负载时间上都有较好的表现.
|
图3 模型有效性分析 |
在全面考虑面向群智感知的服务众包过程中涉及不同服务参数的基础上，提出基于服务质量维度、服务链路维度和感知区域热度维度的3层服务选择模型. 在此基础上，结合AHP层次化思想，对用户感知服务过程中的偏好选择进行合理量化，并实现基于Elo的分级激励方法. 实验结果表明，笔者所提算法在正确性和有效性方面都有较好的表现.
| [1] | Lane N, Miluzzo E, Lu H, et al. A survey of mobile phone sensing[J]. IEEE Communications Magazine, 2010, 48(9): 140-150.[引用本文:1] |
| [2] | Yang Dejun, Xue Guoliang, Fang Xi, et al. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing[J]. Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, MobiCom'12, ACM, Istanbul, Turkey, 2012: 173-184.[引用本文:1] |
| [3] | Gao Wei, Cao Guohong, La P T, et al. On exploiting transient social contact patterns for data forwarding in delay-tolerant networks[J]. Mobile Computing, IEEE Transactions on, 2013, 12(1): 151-165.[引用本文:1] |
| [4] | Howe J. The rise of crowdsourcing[J]. Wired Magine, 2006, 14(6): 1-4.[引用本文:1] |
| [5] | An Jian, Gui Xiaolin, Zhang Wendong, et al. Research on social relations cognitive model of mobile nodes in Internet of things[J]. Journal of Network and Computer Application, 2013, 36(2): 799-810.[引用本文:2] |
| [6] | Eagle N, Pentland A, Lazer D. Inferring friendship network structure by using mobile phone data[C]// Proc Nat'1 Academy of Sciences.2009: 15274-15278.[引用本文:1] |