AP-Assisted Online Task Assignment Algorithms for Mobile Crowdsensing
- PDF / 1,814,946 Bytes
- 14 Pages / 595.224 x 790.955 pts Page_size
- 15 Downloads / 205 Views
AP-Assisted Online Task Assignment Algorithms for Mobile Crowdsensing Shuo Peng1 · Wei Gong1 · Baoxian Zhang1
· Yongxiang Zhao2 · Cheng Li3
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Mobile crowdsensing has become a new way to perceive and collect information due to the widespread of smart devices. In this paper, we study the task assignment problem in mobile crowdsensing systems, which is aimed to reducing the average and largest makespan of all tasks. We consider scenarios where task requester needs the help of mobile users for task completion when they encounter directly or through AP cloud (i.e., several APs connected via wired/wireless links) in an opportunistic manner. We describe the mobile crowdsensing system and formulate the problems under study. We first derive the conditional expected encountering time between requester and different users by jointly considering the opportunities via direct encountering and indirect encountering via AP cloud. Then we propose an AP-assisted average makespan sensitive online task assignment (AP-AOTA) algorithm and an AP-assisted largest makespan sensitive online task assignment (AP-LOTA) algorithm. We present detailed design for both algorithms. We deduce the computational complexities of both algorithms to be O(mn2 ), where m represents the number of tasks and n represent the number of users. We conduct simulations on a real trace data set and a synthetic trace data set and the results show that our proposed algorithms significantly outperform existing work. Keywords Mobile crowdsensing · Wireless access point · Task assignment
1 Introduction The wide spreading of mobile devices has changed people’s daily lives. Mobile devices with rich embedded sensors have Baoxian Zhang
[email protected] Shuo Peng [email protected] Wei Gong [email protected] Yongxiang Zhao [email protected] Cheng Li [email protected] 1
Research Center of Ubiquitous Sensor Networks, University of Chinese Academy of Sciences, Beijing, 100049, China
2
School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing, 100044, China
3
Faculty of Engineering and Applied Science, Memorial University, St. John’s, NL, A1B 3X5, Canada
enabled a new sensing paradigm: Mobile crowdsensing. Mobile crowdsensing is a sensing paradigm that utilizes smart devices (smartphones, wearable devices, etc.) for data collection and task performing. In a mobile crowdsensing system, mobile users use their mobile devices to perform sensing tasks. Compared with traditional Wireless Sensor Networks (WSNs), it has many advantages such as high sensing coverage, low deployment costs, etc. Mobile crowdsensing has many application scenarios such as environment monitoring, social networks, smart city, and intelligent traffic system [9, 10, 14, 16, 25, 29, 31]. Task assignment is a critical issue in mobile crowdsensing and much work has been carried out in this area [4, 6–8, 13, 19, 20, 23, 30]. In a mobile crowdsensing system, task requester has a serie
Data Loading...
