Stable Strategy Formation for Mobile Users in Crowdsensing Using Co-Evolutionary Model
Liangguang Wu*1,*2, Yonghua Xiong*1,*2,, Kang-Zhi Liu*3, and Jinhua She*4
*1School of Automation, China University of Geosciences
No.388 Lumo Road, Hongshan District, Wuhan, Hubei 430074, China
*2Hubei Key Laboratory of Advanced Control and Intelligent Automation for Complex Systems
No.388 Lumo Road, Hongshan District, Wuhan, Hubei 430074, China
*3Department of Electrical and Electronic Engineering, Chiba University
Chiba 263-8522, Japan
*4School of Engineering, Tokyo University of Technology
1404-1 Katakura, Hachioji, Tokyo 192-0982, Japan
In crowdsensing, the diversity of the sensing tasks and an enhancement of the smart devices enable mobile users to accept multiple types of tasks simultaneously. In this study, we propose a new practical framework for dealing with the challenges of task assignment and user incentives posed by complex heterogeneous task scenarios in a crowdsensing market full of competition. First, based on the non-cooperative game property of mobile users, the problem is formulated into a Nash equilibrium problem. Then, to provide an efficient solution, a judgment method based on constraints (sensing time and sensing task dimension) is designed to decompose the problems into different situations according to the complexity. We propose a genetic-algorithm-based approach to find the combination of tasks that maximizes the utility of users and adopts a co-evolutionary model to formulate a stable sensing strategy that maintains the maximum utility of all users. Furthermore, we reveal the impact of competition between users and tasks on user strategies and use a cooperative weight to reflect it mathematically. Based on this, an infeasible solution repair method is designed in the genetic algorithm to reduce the search space, thus effectively accelerating the convergence speed. Extensive simulations demonstrate the effectiveness of the proposed method.
-  H. Elazhary, “Internet of Things (IoT), mobile cloud, cloudlet, mobile IoT, IoT cloud, fog, mobile edge, and edge emerging computing paradigms: Disambiguation and research directions,” J. of Network and Computer Applications, Vol.128, pp. 105-140, 2019.
-  S. Harrison and P. Johnson, “Challenges in the adoption of crisis crowdsourcing and social media in Canadian emergency management,” Government Information Quarterly, Vol.36, No.3, pp. 501-509, 2019.
-  F. Restuccia, P. Ferraro, S. Silvestri, S. K. Das, and G. L. Re, “IncentMe: Effective Mechanism Design to Stimulate Crowdsensing Participants with Uncertain Mobility,” IEEE Trans. on Mobile Computing, Vol.18, No.7, pp. 1571-1584, 2019.
-  F. Restuccia, N. Ghosh, S. Bhattacharjee, S. K. Das, and T. Melodia, “Quality of information in mobile crowdsensing: Survey and research challenges,” ACM Trans. on Sensor Networks (TOSN), Vol.13, No.4, pp. 1-43, 2017.
-  M. Ye and G. Hu, “A distributed method for simultaneous social cost minimization and Nash equilibrium seeking in multi-agent games,” 2017 13th IEEE Int. Conf. on Control & Automation (ICCA), pp. 799-804, 2017.
-  J. Peng, Y. Zhu, W. Shu, and M.-Y. Wu, “When data contributors meet multiple crowdsourcers: Bilateral competition in mobile crowdsourcing,” Computer Networks, Vol.95, pp. 1-14, 2016.
-  L. Wu, Y. Xiong, M. Wu, Y. He, and J. She, “A Task Assignment Method for Sweep Coverage Optimization Based on Crowdsensing,” IEEE Internet of Things J., Vol.6, No.6, pp. 10686-10699, 2019.
-  M. Xiao, J. Wu, L. Huang, R. Cheng, and Y. Wang, “Online task assignment for crowdsensing in predictable mobile social networks,” IEEE Trans. on Mobile Computing, Vol.16, No.8, pp. 2306-2320, 2016.
-  S. He, D.-H. Shin, J. Zhang, J. Chen, and P. Lin, “An exchange market approach to mobile crowdsensing: pricing, task allocation, and walrasian equilibrium,” IEEE J. on Selected Areas in Communications, Vol.35, No.4, pp. 921-934, 2017.
-  X. Duan, C. Zhao, S. He, P. Cheng, and J. Zhang, “Distributed algorithms to compute Walrasian equilibrium in mobile crowdsensing,” IEEE Trans. on Industrial Electronics, Vol.64, No.5, pp. 4048-4057, 2016.
-  L. Wang, Z. Yu, D. Zhang, B. Guo, and C. H. Liu, “Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation,” IEEE Trans. on Mobile Computing, Vol.18, No.1, pp. 84-97, 2018.
-  B. Cao, S. Xia, J. Han, and Y. Li, “A distributed game methodology for crowdsensing in uncertain wireless scenario,” IEEE Trans. on Mobile Computing, Vol.19, No.1, pp. 15-28, 2019.
-  H. Cai, Y. Zhu, and Z. Feng, “A truthful incentive mechanism for mobile crowd sensing with location-Sensitive weighted tasks,” Computer Networks, Vol.132, pp. 1-14, 2018.
-  D. Yang, G. Xue, X. Fang, and J. Tang, “Incentive mechanisms for crowdsensing: Crowdsourcing with smartphones,” IEEE/ACM Trans. on Networking, Vol.24, No.3, pp. 1732-1744, 2015.
-  A. Chakeri and L. G. Jaimes, “An incentive mechanism for crowdsensing markets with multiple crowdsourcers,” IEEE Internet of Things J., Vol.5, No.2, pp. 708-715, 2017.
-  X. Ma, J. Ma, H. Li, Q. Jiang, and S. Gao, “RTRC: a reputation-based incentive game model for trustworthy crowdsourcing service,” China Communications, Vol.13, No.12, pp. 199-215, 2016.
-  J. Nocedal and S. J. Wright, “Sequential Quadratic Programming,” J. Nocedal and S. J. Wright, “Numerical Optimization,” pp. 529-562, Springer, 2006.
-  A. Koh, “An evolutionary algorithm based on Nash dominance for equilibrium problems with equilibrium constraints,” Applied Soft Computing, Vol.12, No.1, pp. 161-173, 2012.
-  F. E. Curtis and M. L. Overton, “A sequential quadratic programming algorithm for nonconvex, nonsmooth constrained optimization,” SIAM J. on Optimization, Vol.22, No.2, pp. 474-500, 2012.
-  A. Rezaee, “The Nash Equilibrium Point of Dynamic Games Using Evolutionary Algorithms in Linear Dynamics and Quadratic System,” Automatic Control and Computer Sciences, Vol.52, No.2, pp. 109-117, 2018.
-  J. Nash, “Non-cooperative games,” Annals of Mathematics, Vol.54, No.2, pp. 286-295, 1951.
-  Y. S. Son and R. Baldick, “Hybrid coevolutionary programming for Nash equilibrium search in games with local optima,” IEEE Trans. on Evolutionary Computation, Vol.8, No.4, pp. 305-315, 2004.
-  F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” Annals of Operations Research, Vol.175, No.1, pp. 177-211, 2010.
-  A. Hammoud, A. Mourad, H. Otrok, O. A. Wahab, and H. Harmanani, “Cloud federation formation using genetic and evolutionary game theoretical models,” Future Generation Computer Systems, Vol.104, pp. 92-104, 2020.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.