Mobile Crowdsensing User Recruitment Algorithm Based on Combination Multi-Armed Bandit
-
摘要: 在移动群智感知任务分配中，数据平台不知道用户的感知质量或成本值的前提下，如何建立合适的用户招募机制是该文需要解决的关键问题，不仅需要在用户执行的过程学习其感知质量值，还要尽可能保证移动群智感知平台的高效性和利润最大化。因此该文提出基于组合多臂赌博机(CMAB)的移动群智感知用户招募算法来解决用户成本已知和未知的招募问题。首先把用户招募过程建模为组合多臂赌博机模型，每个摇臂代表选择不同的用户，所获得的收益代表用户的感知质量；其次提出基于上限置信区间 (UCB)算法的感知质量函数，根据任务完成情况更新用户的感知质量；然后在每轮的用户招募过程中，学习用户的感知质量和成本，并提出一种新颖的贪婪修复算法。该算法是将用户的感知质量值从高到低进行排序，再选择满足预算条件下感知质量值与招募成本最大比率的用户，最后分配任务和更新其感知质量。最后进行了大量基于真实数据集的实验仿真，以此验证算法的可行性与有效性。Abstract: In the mobile crowdsensing task assignment, under the premise that the data platform does not know the user's perceived quality or cost value, how to establish a suitable user recruitment mechanism is the key issue that this article needs to solve. It is necessary to try to ensure the efficiency and profit maximization of the mobile crowdsensing platform. Therefore, a mobile crowdsensing user recruitment algorithm based on a Combined Multi-Armed Bandit (CMAB) is proposed to solve the recruitment problem of known and unknown user costs. Firstly, the user recruitment process is modeled as a combined multi-arm bandit model. Each rocker is represented by a different user’s choice, and the income obtained represents the user’s perceived quality. Secondly, the Upper Confidence Bound (UCB) algorithm is proposed to update the user’s perceived quality according to the completion of the task. Users’ perceived quality values are sorted from high to low, and then the user with the largest ratio of perceived quality to recruitment cost is selected under budget conditions, tasks are assigned, and their perceived quality is updated. Finally, A large number of experimental simulations based on real data sets are carried out to verify the feasibility and effectiveness of the algorithm.
-
表 1 本文主要符号和释义
符号 释义 P,A 移动用户和任务的集合 i, j, t 移动用户、感知任务和轮次的索引值 $ M_i^l \subset M $,$ c_i^l = {\xi _i} * f\left( {\left| {T_i^l} \right|} \right) $ 用户i表示可完成的任务集合，$ C_i^l $表示相应的成本，$ {\xi _i} $表示用户的成本参数 $ {w_j} $ 任务的权重 P,$ {P^t} $, L ,Y 所有选项的集合，在第i轮次选中的选项集合， 每个用户最大的选项数目，每轮选择的用户数量 B 任务发起者给出的预算值 $ q_i^tj $ 用户i在第ｔ轮次中完成任务j的感知质量值 $ {\bar q_i}(t) $ 第t轮次，用户i的平均感知质量值 $ {\hat q_i}(t) $ 直到第t轮次，用户i基于UCB的感知质量值 $ {q_i} $ 用户i的感知质量的期望值 $ {n_i}(t) $ 直到第t轮次，移动用户i被选中的次数 
下载: 导出CSV
表 2 贪婪修复算法(GRA)
输入：$ p_i^l $,Q[0,1,···,n],F[i], ${C}_{i}^{l} $,B,Cost,j 输出：Q′[0,1,···,n] (1) $p_i^l $←0,F[i]←0, j←0； (2) Cost←0,i←0 (3) 在第r轮次中，将${p}_{i}^{l} $降序排列候选用户并存储在数组Q[0,1,···,n] (4) for(i←0 to n) do (5) Cost= Cost+${C}_{i}^{l} $; (6) If (Cost≤ B && F[i]=0) (7) F[i] ←1, Q′[j++]=Q[i] (8) else (9) Cost= Cost–$C_i^l $ (10) return $Q' $[j]
下载: 导出CSV
表 3 基于CMAB 的用户已知成本招募算法
输入：R, P, $p_i^l = < M_i^l,c_i^l > $,B,Y, $p_i^l $ Q[0,1,···,n] ,Cost, ${n_i}(r) $ ,任务集合$A_i^l $ 输出：${P}^{r} $ (1) r=1，选中每一个用户的第1个选项，获得初始参数 (2) 更新对应的$ c_i^l $, ${{q}}_{{i}}^{{l}}{j} $, $ B\prime = B\; - \;\sum\nolimits_{pr} {c_i^l} $, ${n_i}(r) = \left| {M_i^l} \right| $, Cost=0 (3) 感知任务质量的平均值：${q_i}(r) = \mathop \sum \limits_{r = 1} q_i^lj/\left| {M_i^l} \right| $ (4) while true do (5) r=r+1, ${P^r} = \varPhi$ (6) while $ \left| {{P^r}} \right| < Y $
(7) 计算所有用户感知质量函数值和成本的比率$P_i^l = \mathop { {\text{argmax} } }\limits_{p_{i'}^{l'} \in p} \dfrac{ { {u_{ {Q_i}(r)} }\left( { {P^r} \cup p_{i'}^{l'} } \right) - {u_{ {Q_i}(r)} }\left( { {P^r} } \right)} }{ {c_{i'}^{l'} } }$(8) 将$p_i^l $降序排列候选用户并存储在数组Q[0,1,···,n] (9) for(i←1 to n) (10) ${} {\rm{Cost} } = { {\rm{Cost} } } + c_i^l$ (11) if(${{\rm{Cost}}} < B'$&&F[i] =0 ) $ {B'}\&\& {F}\left[ {i}\right]=0 $ (12) F[i] ←1 (13) 将$p_i^l $加入${P^r} $中 (14) else (15) ${{\rm{Cost}}} = {{\rm{Cost}}} - c_i^l$ (16) ${B'} $=${B'} $–Cost
下载: 导出CSV
表 4 基于CMAB 的用户未知成本招募算法
输入：R,P,${p}_{i}^{l}= < {M}_{i}^{l},{c}_{i}^{l} > $B,Y,$p_i^l $,Q[0,1,···,n] ,Cost,${n}_{i}\left(r\right) $,${C_i} $,${\widehat{Q}}_{i}^{l}(t) $,$m_i^l $ 输出：${P}^{r} $ (1) r=1，选中每个用户的第1个选项，获得用户的初始参数$p_i^l $,${q}_{i}^{l} $,$\xi _i^l $ (2)更新对应的$\xi _i^l $,$q_i^l $${{\xi }}_{{i}}^{{l}}，{{C}}_{{i}}^{{l}} {{q}}_{{i}}^{{l}}$, $ \hat Q_i^l(t)$, $B' = B\; - \;\sum\nolimits_{pr} {\xi _i^lf(|M_i^l|)} $, ${n_i}(r) = \left| {M_i^l} \right| $, Cost=0 (3) WHILE true do (4) r=r+1; (5) while $ \left| {{P^r}} \right| < Y $ (6) 对于每个被选中的用户i先获得成本参数$\xi _i^l $ (7) 计算所有用户感知质量函数值和成本的比率$p_i^l = \arg \max {u_{\hat Q_i^l(r - 1)} }\left( { {P^r} \cup \left\{ {p_{i'}^{l'} } \right\} } \right) - {u_{\hat Q_i^l(r - 1)} }\left( { {P^r} } \right)$ (8) 将$p_i^l $降序排列候选用户并存储在数组Q[0,1,···,n] (9) FOR i = 0 to n do (10) ${\text{Cost} } = {\text{Cost} } + \xi _i^lf(|M_i^l|)$; (11) if($ {\rm{Cost}} < B' $&&F[i] =0 ) ${B}{\text{'}}\&\&{ }{F}\left[{i}\right]=0 $ (12) F[i] ←1 (13) 将$p_i^l $加入${P^r} $中 (14) else (15) ${{\rm{Cos}}} {\text{t}} = {{\rm{Cos}}} {\text{t}} - \xi _i^lf(|M_i^l|) $ (16) $B' $=$B' $–Cost
下载: 导出CSV
表 5 算法2实验情况设定
情况 成本(B) 每轮招募人数(Y) 用户数量(A) 任务数量(P) 1 5000 50～120 150 800 2 5000 80 50～200 800 3 5000 80 150 200～1200 4 10000 50～120 150 800 5 10000 80 50～200 800 6 10000 80 150 200～1200 7 15000 50～120 150 800 8 15000 80 50～200 800 9 15000 80 150 200～1200
下载: 导出CSV
-
[1] YANG Jing and XU Jialiang. Participant service ability aware data collecting mechanism for mobile crowd sensing[J]. Sensors, 2018, 18(12): 4219. doi: 10.3390/s18124219 [2] 王健, 黄越, 赵国生, 等. 面向任务代价差异的移动群智感知激励模型[J]. 电子与信息学报, 2019, 41(6): 1503–1509. doi: 10.11999/JEIT180640WANG Jian, HUANG Yue, ZHAO Guosheng, et al. The incentive model for mobile crowd sensing oriented to differences in mission costs[J]. Journal of Electronics &Information Technology, 2019, 41(6): 1503–1509. doi: 10.11999/JEIT180640 [3] THARWAT A, MAHDI H, ELHOSENY M, et al. Recognizing human activity in mobile crowdsensing environment using optimized k-NN algorithm[J]. Expert Systems with Applications, 2018, 107: 32–44. doi: 10.1016/j.eswa.2018.04.017 [4] 赵国生, 张慧, 王健. 基于Tangle网络的移动群智感知数据安全交付模型[J]. 电子与信息学报, 2020, 42(4): 965–971. doi: 10.11999/JEIT190370ZHAO Guosheng, ZHANG Hui, and WANG Jian. A mobile crowdsensing data security delivery model based on Tangle network[J]. Journal of Electronics &Information, 2020, 42(4): 965–971. doi: 10.11999/JEIT190370 [5] WANG Feng, HU Liang, SUN Rui, et al. SRMCS: A semantic-aware recommendation framework for mobile crowd sensing[J]. Information Sciences, 2018, 433/434: 333–345. doi: 10.1016/j.ins.2017.04.045 [6] AZZAM R, MIZOUNI R, OTROK H, et al. A stability-based group recruitment system for continuous mobile crowd sensing[J]. Computer Communications, 2018, 119: 1–14. doi: 10.1016/j.comcom.2018.01.012 [7] XU Zheng, MEI Lin, CHOO K K R, et al. Mobile crowd sensing of human-like intelligence using social sensors: A survey[J]. Neurocomputing, 2018, 279: 3–10. doi: 10.1016/j.neucom.2017.01.127 [8] CHEN Yueyue, LV Pin, GUO Deke, et al. Trajectory segment selection with limited budget in mobile crowd sensing[J]. Pervasive and Mobile Computing, 2017, 40: 123–138. doi: 10.1016/j.pmcj.2017.06.010 [9] CIANCIULLI D, CANFORA G, and ZIMEO E. Beacon-based context-aware architecture for crowd sensing public transportation scheduling and user habits[J]. Procedia Computer Science, 2017, 109: 1110–1115. doi: 10.1016/j.procs.2017.05.451 [10] LOUKAS G, YOON Y, SAKELLARI G, et al. Computation offloading of a vehicle’s continuous intrusion detection workload for energy efficiency and performance[J]. Simulation Modelling Practice and Theory, 2017, 73: 83–94. doi: 10.1016/j.simpat.2016.08.005 [11] CHEN Qinghua, WENG Zhengqiu, HAN Yang, et al. A distributed algorithm for maximizing utility of data collection in a crowd sensing system[J]. International Journal of Distributed Sensor Networks, 2016, 12(9): 1550147716668083. [12] XU Jia, XIANG Jinxin, and LI Yanxu. Incentivize maximum continuous time interval coverage under budget constraint in mobile crowd sensing[J]. Wireless Networks, 2017, 23(5): 1549–1562. doi: 10.1007/s11276-016-1244-9 [13] 刘琰, 郭斌, 吴文乐, 等. 移动群智感知多任务参与者优选方法研究[J]. 计算机学报, 2017, 40(8): 1872–1887. doi: 10.11897/SP.J.1016.2017.01872LIU Yan, GUO Bin, WU Wenle, et al. Multitask-oriented participant selection in mobile crowd sensing[J]. Chinese Journal of Computers, 2017, 40(8): 1872–1887. doi: 10.11897/SP.J.1016.2017.01872 [14] 周杰, 於志勇, 郭文忠, 等. “t-时隙 k-覆盖”群智感知任务的参与者选择方法[J]. 计算机科学, 2018, 45(2): 157–164,196. doi: 10.11896/j.issn.1002-137X.2018.02.028ZHOU Jie, YU Zhiyong, GUO Wenzhong, et al. Participant selection algorithm for t-sweep k-coverage crowd sensing tasks[J]. Computer Science, 2018, 45(2): 157–164,196. doi: 10.11896/j.issn.1002-137X.2018.02.028 [15] WANG Yanan, SUN Guodong, and DING Xingjian. Coverage-balancing user selection in mobile crowd sensing with budget constraint[J]. Sensors, 2019, 19(10): 2371. doi: 10.3390/s19102371 [16] 蒋伟进, 刘晓亮. 群智感知中移动用户招募的防贪婪激励机制研究[J]. 控制与决策, 2022, 37(1): 28–36. doi: 10.13195/j.kzyjc.2020.0744JIANG Weijin and LIU Xiaoliang. Anti-greedy incentive mechanism for mobile user recruitment in crowd sensing[J]. Control and Decision, 2022, 37(1): 28–36. doi: 10.13195/j.kzyjc.2020.0744 [17] SONG Shiwei, LIU Zhidan, LI Zhenjiang, et al. Coverage-oriented task assignment for mobile crowdsensing[J]. IEEE Internet of Things Journal, 2020, 7(8): 7407–7418. doi: 10.1109/JIOT.2020.2984826 [18] ZHANG Yifan, ZHANG Xinglin, and LI Feng. BiCrowd: Online biobjective incentive mechanism for mobile crowdsensing[J]. IEEE Internet of Things Journal, 2020, 7(11): 11078–11091. doi: 10.1109/JIOT.2020.2994365 [19] XIAO Mingjun, GAO Guoju, WU Jie, et al. Privacy-preserving user recruitment protocol for mobile crowdsensing[J]. IEEE/ACM Transactions on Networking, 2020, 28(2): 519–532. doi: 10.1109/TNET.2019.2962362 -
图(14) / 表(5)
计量
- 文章访问数: 747
- HTML全文浏览量: 302
- PDF下载量: 96
- 被引次数: 0
下载:
