Task allocation in IoV-based crowdsensing combing clustering and CMAB

Xinxin FENG; Danying GUO; Zefeng LIU; Haifeng ZHENG

doi:10.11959/j.issn.2096-3750.2021.00224

您当前的位置：

首页 >

文章列表页 >

Task allocation in IoV-based crowdsensing combing clustering and CMAB

Theory and Technology | 更新时间：2024-06-05

- Task allocation in IoV-based crowdsensing combing clustering and CMAB
- Chinese Journal on Internet of Things Vol. 5, Issue 3, Pages: 86-96(2021)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：10.11959/j.issn.2096-3750.2021.00224
  CLC： TP391
- Published：30 September 2021，
  
  Published Online：2021-09，
- 稿件说明：
移动端阅览
XINXIN FENG, DANYING GUO, ZEFENG LIU, et al. Task allocation in IoV-based crowdsensing combing clustering and CMAB. [J]. Chinese journal on internet of things, 2021, 5(3): 86-96.
DOI：

XINXIN FENG, DANYING GUO, ZEFENG LIU, et al. Task allocation in IoV-based crowdsensing combing clustering and CMAB. [J]. Chinese journal on internet of things, 2021, 5(3): 86-96. DOI： 10.11959/j.issn.2096-3750.2021.00224.

摘要

基于车联网（IoV

Internet of vehicles）用户的群智感知网络具有节点覆盖广泛、数据全面及时等优点。该技术实现的一大难点在于，如何通过充分挖掘和利用车联网用户的信息（如用户地理位置等）来选择合适的感知任务参与者，以合理地进行任务分配，进而提高感知任务的完成质量和任务发布者收益。为此提出了一种结合车辆用户轨迹特征与组合多臂赌博机（CMAB

combinatorial multi-armed bandits）算法的群智感知用户任务分配机制。首先，基于用户历史行车轨迹的相似程度，将用户聚类。然后，利用 CMAB 模型，将轨迹聚类信息作为用户任务分配的依据，求解最佳工作者组合。最后，利用真实出租车轨迹数据集对上述算法进行了验证。实验结果表明，考虑轨迹特征信息的任务分配算法具有更高的准确率，并能使任务发布者获得高收益。同时，所选出的工作者集合有相近的行车轨迹，对于同一地点的任务具有高的完成质量，能有效提高感知数据质量和任务发布者收益，适用于实际应用场景。

Abstract

The crowdsening network based on Internet of vehicles (IoV) users has the advantages of extensive node coverage

complete and timely data.A major difficulty in the realization of this technology lies in how to fully mine and use the information of connected vehicular users (such as the user's geographic location

etc.) to select appropriate perception task participants

so as to carry out reasonable task assignments

thereby improving the completion quality of perception tasks and task publisher’s benefits.To solve the above problems

a task allocation method combining the trajectory features and the combinatorial multi-armed bandits (CMAB) algorithm was proposed.Firstly

users were clustered based on the similarity of their historical driving trajectories.Then

the CMAB model was adopted so that the trajectory clustering information could be used as the basis for deciding the optimal worker combination.Finally

the proposed algorithm was verified using the real taxi-trajectory dataset.The experimental results show that the task assignment algorithm considering the trajectory feature information has a higher accuracy and higher profit.At the same time

the selected workers have a high completion quality for tasks at the same location

and can effectively improve the quality of perceived data and the benefits of task publishers

which is suitable for practical application scenarios.

关键词

群智感知车联网组合多臂赌博机模型轨迹聚类任务分配

Keywords

crowdsensingInternet of vehiclesCMAB modeltrajectory clusteringtask allocation

references

李陈生 . 基于城市交通的车载移动群体感知网络技术研究[D]. 北京：北京邮电大学, 2019.

LI C S . Research on vehicle mobile crowdsensign network technology based on urban public transportation[D]. Beijing:Beijing University of Posts and Telecommunications, 2019.

刘媛妮, 李慧聪, 关鑫 ,等. 移动群智感知激励机制研究综述[J]. 重庆邮电大学学报(自然科学版), 2018,30(2): 147-158.

LIU Y N, LI H C, GUAN X ,et al. Review of incentive mechanism for mobile crowd sensing[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2018,30(2): 147-158.

DASARI V S, KANTARCI B, POURYAZDANPANAH M ,et al. Game theory in mobile crowdsensing:a comprehensive survey[J]. Sensors, 2020,20(7): 1-23.

方文凤, 周朝荣, 孙三山 . 移动群智感知中任务分配的研究[J]. 计算机应用研究, 2018,35(11): 3206-3212.

FANG W F, ZHOU C R, SUN S S . Research on task assignment for mobile crowdsensing[J]. Application Research of Computers, 2018,35(11): 3206-3212.

黄涛 . 移动群智感知网络中任务分配机制研究[D]. 重庆：重庆大学, 2019.

HUANG T . Research on task assignment mechanism in mobile crowdsensing network[D]. Chongqing:Chongqing University, 2019.

ROBBINS H . Some aspects of the sequential design of experiments[J]. Bulletin of the American Mathematical Society, 1952,58(5): 527-536.

CHEN W, WANG Y J, YUAN Y ,et al. Combinatorial multi-armed bandit and its extension to probabilistically triggered arms[J]. Journal of Machine Learning Research, 2016,17(50): 1-33.

徐晓雨 . 车联网群智感知任务分发研究与实现[D]. 北京:北京工业大学, 2018.

XU X Y . Research and implementation of task allocation for crowd sensing in Internet of vehicles[D]. Beijing:Beijing Uiversity of Technology, 2018.

WAN J F, LIU J N, SHAO Z H ,et al. Mobile crowdsensing for traffic prediction in internet of vehicles[J]. Sensors, 2016,16(1): 88.

严嘉赟 . 基于群智感知的车联网节点优化方法与应用[D]. 南京:南京邮电大学, 2019.

YAN J Y . Optimization method and application of vehicle network node based on crowdsensing[D]. Nanjing:Nanjing University of Posts and Telecommunications, 2019.

ZHOU Z, LIU P, FENG J ,et al. Computation resource allocation and task assignment optimization in vehicular fog computing:a contract-Matching approach[J]. IEEE Transactions on Vehicular Technology, 2019,68(4): 3113-3125.

XIANG C C, HE S N, SHIN K G ,et al. Incentivizing platform–user interactions for crowdsensing[J]. IEEE Internet of Things Journal, 2020: 1-14.

XING Y P, WANG L M, LI Z Y ,et al. Multi-attribute crowdsourcing task assignment with stability and satisfactory[J]. IEEE Access, 2019,7: 133351-133361.

YANG S, WU F, TANG S J ,et al. Selecting most informative contributors with unknown costs for budgeted crowdsensing[C]// 2016 IEEE/ACM 24th International Symposium on Quality of Service (IWQoS). Beijing:IEEE Press, 2016: 1-6.

YANG S, QI X T, WU F ,et al. Bandit user selection algorithm for budgeted and time-limited mobile crowdsensing[C]// GLOBECOM 2017-2017 IEEE Global Communications Conference. Singapore:IEEE Press, 2017: 1-6.

GAO G J, WU J, XIAO M J ,et al. Combinatorial multi-armed bandit based unknown worker recruitment in heterogeneous crowdsensing[C]// Proceedings of the 39th IEEE International Conference on Computer Communications (INFOCOM 2020). Toronto:IEEE Press, 2020: 179-188.

王涛春, 刘婷婷, 刘申 ,等. 群智感知中的参与者信誉评估方案[J]. 计算机应用, 2018,38(3): 753.

WANG T C, LIU T T, LIU S ,et al. Participant reputation evaluation scheme in crowd sensing[J]. Journal of Computer Applications, 2018,38(3): 753.

孙鸿滨 . 移动群智感知中基于数据质量的参与者优选方法[D]. 北京:北京交通大学, 2019.

SUN H B . Quality-aware based participant selection for mobile crowd sensing[D]. Beijing:Beijing Jiaotong University, 2019.

YANG C Y, YU Z W, LIU Y M ,et al. Dynamic allocation for complex mobile crowdsourcing task with internal dependencies[C]// 2019 IEEE SmartWorld,Ubiquitous Intelligence ＆ Computing,Advanced ＆Trusted Computing,Scalable Computing ＆ Communications,Cloud＆ Big Data Computing,Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI). Leicester:IEEE Press, 2019: 818-825.

YUAN G, SUN P H, ZHAO J ,et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review, 2017,47(1): 123-144.

GAWDE G, PAWAR J . Similarity search of time series trajectories based on shape[C]// The ACM India Joint International Conference. New York:ACM Press, 2018: 340-343.

LEE J, HAN J, WHANG K . Trajectory clustering:a partition-and-group framework[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data. New York:ACM Press, 2007: 593-604.

TANG W, PI D C, HE Y . A density-based clustering algorithm with sampling for travel behavior analysis[C]// Intelligent Data Engineering and Automated Learning– IDEAL 2016. Yangzhou:Springer Press, 2016: 231-239.

CHENG Z Y, JIANG L, LIU D S ,et al. Density based spatio-temporal trajectory clustering algorithm[C]// IGARSS 2018 - 2018 IEEE International Geoscience and Remote Sensing Symposium. Valencia:IEEE Press, 2018: 3358-3361.

HAN B, LIU L, OMIECINSKI E . A systematic approach to clustering whole trajectories of mobile objects in road networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2017,29(5): 936-949.

PELEKIS N, KOPANAKIS I, KOSTIFAKOS E ,et al. Clustering trajectories of moving objects in an uncertain world[C]// 2009 9th IEEE International Conference on Data Mining. Miami:IEEE Press, 2009: 417-427.

KROSE B . Learning from delayed reward[J]. Robotics and Autonomous Systems, 1995,15(4): 233-235.

AUER P, CESA-BIANCHI N,, FISCHER P . Finite-time analysis of the multiarmed bandit problem[J]. Machine Learning, 2002,47(2): 235-256.

Views

549

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Edge server deployment decision based on improved NSGA-Ⅱ in the Internet of vehicles edge computing scenario

Edge intelligence empowered internet of vehicles: concept, framework, issues, implementation, and prospect

Cognitive waveform design for radar-communication transceiver networks

Research on the spectrum sensing and sharing technology in the dynamic spatiotemporal data driven cognitive Internet of vehicles

Space-air-ground integrated networks:review and prospect

Related Author

Yu WANG

Hao CHEN

Hai ZHU

Zhengyi CHAI

Chengrui YANG

Sifeng ZHU

Huan ZHOU

Hai LIN

Related Institution

School of Computer, Henan University of Engineering

School of Computer Science and Technology, Tiangong University

School of Computer and Information Engineering, Tianjin Chengjian University

Wuhan University

Huali SmartWays Technology Co., Ltd.

⁰