结合聚类与CMAB的群智感知车联网任务分配方法

doi:10.11959/j.issn.2096-3750.2021.00224

摘要/Abstract

摘要：

基于车联网（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.

Key words: crowdsensing, Internet of vehicles, CMAB model, trajectory clustering, task allocation

中图分类号:

TP391

冯心欣, 郭丹颖, 柳泽烽, 郑海峰. 结合聚类与CMAB的群智感知车联网任务分配方法[J]. 物联网学报, 2021, 5(3): 86-96.

Xinxin FENG, Danying GUO, Zefeng LIU, Haifeng ZHENG. Task allocation in IoV-based crowdsensing combing clustering and CMAB[J]. Chinese Journal on Internet of Things, 2021, 5(3): 86-96.

图/表 14

表1

图1

图2

表2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

参考文献 28

[1]	李陈生 . 基于城市交通的车载移动群体感知网络技术研究[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.
[2]	刘媛妮, 李慧聪, 关鑫 ,等. 移动群智感知激励机制研究综述[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.
[3]	DASARI V S , KANTARCI B , POURYAZDANPANAH M ,et al. Game theory in mobile crowdsensing:a comprehensive survey[J]. Sensors, 2020,20(7): 1-23.
[4]	方文凤, 周朝荣, 孙三山 . 移动群智感知中任务分配的研究[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.
[5]	黄涛 . 移动群智感知网络中任务分配机制研究[D]. 重庆：重庆大学, 2019.
	HUANG T . Research on task assignment mechanism in mobile crowdsensing network[D]. Chongqing:Chongqing University, 2019.
[6]	ROBBINS H . Some aspects of the sequential design of experiments[J]. Bulletin of the American Mathematical Society, 1952,58(5): 527-536.
[7]	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.
[8]	徐晓雨 . 车联网群智感知任务分发研究与实现[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.
[9]	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.
[10]	严嘉赟 . 基于群智感知的车联网节点优化方法与应用[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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	王涛春, 刘婷婷, 刘申 ,等. 群智感知中的参与者信誉评估方案[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.
[18]	孙鸿滨 . 移动群智感知中基于数据质量的参与者优选方法[D]. 北京:北京交通大学, 2019.
	SUN H B . Quality-aware based participant selection for mobile crowd sensing[D]. Beijing:Beijing Jiaotong University, 2019.
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	KROSE B . Learning from delayed reward[J]. Robotics and Autonomous Systems, 1995,15(4): 233-235.
[28]	AUER P , CESA-BIANCHI N ,, FISCHER P . Finite-time analysis of the multiarmed bandit problem[J]. Machine Learning, 2002,47(2): 235-256.

工作者ID	时间	经度	纬度
1	2016/11/1 15:26:21	104.075 75	30.685 06
1	2016/11/1 15:26:27	104.076 06	30.685 60
2	2016/11/1 15:00:02	104.082 70	30.682 71
?	?	?	?
496	2016/11/1 15:09:49	104.081 65	30.680 27

感知总工人数/人	选取工人总数量/人	最大迭代次数(maxIters)	聚类群集数
496	10	2 000	12