A Multi Task Allocation Based Time Optimization Framework Using Social Networks in Mobile Crowd Sensing

A Multi Task Allocation Based Time Optimization Framework Using Social Networks in Mobile Crowd Sensing

Sasireka VeerapathiranShyamala Ramachandran

Department of CSE, Oxford College of Engineering, Thiruvannamalai 606803, India

Department of IT, University College of Engineering, Anna University, Tindivanam 604001, India

Corresponding Author Email: 
29 October 2022
19 December 2022
31 December 2022
| Citation



The quality of data and its sensing cost is the important concern for task allocation in crowd sensing. The sensing capabilities of a device to send the collection of sensor data to a cloud requires crowd sensing in order to receive reliable data. Crowd sensing is used in many areas such as traffic monitoring, smart cities, health care, transportations, environmental monitoring and many more. Most of existing works are only based on assumptions in task scheduling about the number of candidate users and are mainly performed optimization of single task allocation. If the candidate users are few, then the completion of task with in the schedule can be difficult for many sensor applications. In this work, we proposed a social network-based task allocation scheme for the optimization of multi task allocation. The main idea of the proposed work is to maximize the task completion within the allocated schedule. It is evident that the task scheduling algorithms are NP-hard and we introduced a decreasing threshold task allocation (DTT) and fast greedy selections (FGS) algorithms along with Crow COOT Foraging Optimization (CCFO) algorithm to allocate the tasks parallelly with maximum efficiency. The proposed algorithms such as C-DTT (CCFO-DTT) and C-FGS (CCFO-FGS_ are used for the efficient allocation of tasks. The combination of these algorithms can be helpful in selecting the candidate users who will perform the completion of maximum tasks. Due to the selection of proper users in each round, the time consumption of the tasks to be completed is greatly reduced. The experimental results also indicates that the proposed work performs well in the optimization of multi task allocation than the other state of the art models.


crowd sensing, greedy algorithms, optimization, task allocation

1. Introduction

Mobile crowd sensing has become more popular recently due to the exponential growth of the mobile devices and the communication standards. In crowd sensing, sensory applications are playing vital role in sending the sensed data of the mobile users to the cloud. This platform should support ubiquitous nature so that the transfer of sensed data can be handled in a smooth way during the sensory analysis [1, 2]. There are enormous crowd sensing applications have been emerged in many fields such as transportation, pollution monitoring, emergency care, ecological monitoring, and intelligent transport systems [3, 4]. This platform can also be helpful in collecting the user’s information that will be useful for location-based services. The tasks in this context can be distributed either by human intelligence or by crowd. The process of crowd sensing can be categorized into 4 stages such as creation of new tasks, allocation of tasks, execution of tasks and integration of data. However, task allocation is considered as the primary task since it determines the quality of sensor and the sensing cost. Unlike wireless sensor network, here the efficient users who are qualified for completing the tasks are only selected so that the task can be completed in a limited time. There are many task allocation schemes are existed [5-10]. In the existing works, the quality of sensor and the sensing cost can be minimized by selecting the users from a large candidate pool and thus the data quality can be maintained. However, the crowd sensing is used in enormous applications for the collection of sensed data and the required candidate users may not be available for any applications. These are due to the fact that the task allocations are done with few users and they may not enable their location services. Because of this reason, crowd sensing platform will strive to complete the tasks with few numbers of users. In crowd, a greater number of opinions, independent computation, division of the work among crowd, gathering the sensor information to produce meaningful data makes the process smarter. Crowd sensing and computing are merged to provide a unified framework and generate many applications that are required in our day-to-day life. Social networks are helpful in allocating sensing tasks by propagating the information to the users. They can build a social relationship among others and the sensing tasks can be assigned to the users. There are several benefits of using social network for allocating tasks. Sensing tasks can be greatly reduced by recruiting a few seed to propagate the task information. Based on the friendship, the user can help their friends to process the sensing tasks. Therefore, the sensing nature can be raised in the task allocation method using social networks. However, the users will not share their location information if they are not registered in the platform that can avoid the risk of data leakage. With the inspiration of this platform, the work aims to assign the tasks with the help of social network. The work first analyzes the issues in existing task allocation schemes. Then, we created a multi task allocation with limited candidate pool. The existing works are focused on decreasing the computational cost, and communication cost. However, there should be a balanced mechanism to achieve this so that the platform could be better in large scale task allocation. The main aim of this paper is to improve the allocation of task using an optimized CCFO algorithm and to reduce the computational complexity with the help of DTT (decreasing threshold task allocation) and FGS (fast greedy selections algorithms). The main reason for the improvement of our work is due to the selection of proper users in each round and hence the time consumption of the tasks to be completed is greatly reduced. The rest of the sections are organized as follows: section 2 describes the existing works available for crowd sensing, their meris and demerits. In section 3, the proposed multi task allocation based time optimization framework is introduced. Section 4 discuss the results obtained by the proposed work. Section 5 concludes the work.

2. Related Work

Task allocations have been considered as a significant problem recently by various researchers. Single task allocation and multi task allocation are the existing solutions for task allocation problems. In single task allocation problem, the candidate users are few and the recruitments are minimum. Zhang et al. [11] proposed single task allocation problem where proper users are selected based on the time constraints, location and the behavior of users. The main idea of the paper is to maximize the spatial coverage by selecting the appropriate users. However, the paper does not focus on the task allocation with maximum candidate pool. Due to this, the efficiency of the proposed method could not be achieved. Wang et al. describes the task allocation process based on single task framework and the budget constraint is used in the work to increase the quality of coverage. Even though, the work reduces the recruitment cost, the set of users in candidate pool does not guarantee the predefined requirements. Multiple tasks can be allocated after the growth of crowdsensing. Optimization of tasks allocation should be considered with several factors such as spatial and temporal granularity property while performing multiple task allocation. Yu et al. [12] introduced a 2 stage multi task algorithm where users can perform the tasks without the need of location information. The work claims that the number of candidate users can be minimized in the allocations. However, it is unclear that the proposed algorithm performs task allocation well with minimum users for the large number of tasks to be allocated. The heterogeneous nature of sensing devices is considered in [13] where the work utilizes particle swarm optimization algorithm (PSO) for the selection of users in order to increase the quantity of completed tasks. In contrast to this method, authors of the study [14] proposed a 3-stage task allocation method where the same data property are shared between different tasks. This method considers the spatial and temporal properties along with data property of sensory data. Based on the above studies, we understand that most of the studies focused on speed up the process of completing the tasks under participant selection task. This might cause two issues: participant may not select the location information remotely. They may not be interested with a greater number of tasks. To overcome these issues, the authors [15] proposed introduced a SAT framework to complete the several assigned tasks. Here, each participant is assigned a task under SAT. However, the research done by the author is under assumptions that there are sufficient candidate users for completing the tasks. They are not suitable for multi task allocation if the required number of tasks to be completed is increased because these tasks are large and a greater number of users may require. We also observed that most of the multi task allocation techniques satisfy only one objective. However, two objectives such as incentives to the participants and quality utility needs to be satisfied for any multi task allocation framework and appropriate constraint must be found. Therefore, it is necessary to satisfy the two objectives by optimizing them to achieve better results in multi task allocation. In our previous work we used Crow COOT Foraging Optimization (CCFO) algorithm where the best candidate is chosen based on the fitness function. In the proposed work, we have focused on improving the objectives such as incentives and quality utility for the allocation of multiple tasks with minimum number of users in the candidate pool. We also used two greedy algorithms such as DTT and FGS along with CCFO to solve the constrain method in multi task allocation.

3. The Proposed Model

The work design optimization model for crowd sensing where the users such as PUs and SUs are distributed among the networks and encouraged by the social relationship and incentives. After that SH is used to perform a coordination for sensing the data in order to prevent high sensing cost. PU and SU are mobile users including friends and strangers for a certain region. To find the status of any primary user, SR will gather information via social circle. Here the friends in the circle will help the SR and they will get help from SR in future. By these kinds of processes, they build a strong relationship among all the users. To join the network, the users should request SR and they will be allowed inside the network after the reputation value of the users is verified. Therefore, the selection of the users is based on their reputation values. This reputation value is calculated from the past contributions of the users. Figure 1 shows the system model where F1 - F6 are friends and S1 to S10 are strangers, PU - primary user, SR- Sensing Requestor, SU - secondary user, SH- Sensing helper.

Figure 1. System model

After defining the system model, we then formulate the multi task problem as a first part for this platform. In crowd sensing, platform and the users are the important entities. All the task such as T1, T2, ..., Tn are published by the platform and they are assumed to be spatial-temporal tasks are denoted by A1, A2, ..., An and the sub areas are denoted by S1, S2, ...,Sn. The tasks are usually transfers sensor data and the users may require consumption of different resources. In multi task model, the incentives are allocated by the platform and it is denoted by I1, I2, …, In. The capabilities of all the users should be predefined so that the tasks can be perfectly assigned to each user and the maximum tasks can be allotted to the users with low capability value. However, to avoid any discrepancies of the data which are received from the users, minimum threshold tasks need to be maintained which is denoted as minThi, for the task Ti .it means that each area Aishould have sensed by minimum number of threshold value. To check if the minimum value is satisfied or not, the work uses the following formula

$B_{i, j}^K=\left\{\begin{array}{c}0, \quad G_{i, j}^K\left(H^2\right) \leq \operatorname{minTh}_k \\ 1, G_{i, j}^K\left(H^2\right) \geq \operatorname{minTh}_k\end{array}\right.$          (1)

Then the sensing quality can be can be increased as

$S(V)=\frac{\sum_x^{y i} \sum_y^j e_{x, y}^z}{I+j}$          (2)

S(V) denotes the sensing quality with regards to vector allocation V. Sensing quality should be estimated for the appropriate selection of participants in sensing tasks and the interested participants to be selected are denoted as a Vector V={V1, V2, …, Vm}. The total quality can be defined as

$T Q(V)=\sum_{i=1}^j w_f X S(V)$          (3)

The above formula represents the mean of sensing quality and the weights are denoted as w. whenever the candidates finished the tasks that are allotted to them, the users are eligible for incentives and the incentive for task t can be defined as follows

$\operatorname{INt}(V)=I_{m, n}^k(V) * N_t$          (4)

Even though the system model can be applied for the optimization of multi task allocation, the expected number of users to complete the tasks cannot be determined. The work mainly focused to limit the overall incentives with limited number of users. We introduced a probabilistic model to predict the expected number of users then the problem is transformed to improve the overall quality and incentives with limited number of users. The required number of users can be computed as

$U_i^j(V)=\sum_{m=1}^t m_{w, t} * n_{w: i, j}$          (5)

The sensing quality for the number of tasks can be defined as follows

$E S(V)=\frac{\sum_x^{y i} \quad\sum_y^j \quad e_{x, y}^z}{m+n}$         (6)

where $e_{x, y}^Z$  represents the expected number of data that does not exceeds the threshold value. Therefore, the expected tasks that can be completed are identified with two stages. First, the expected users who will complete the maximum tasks are selected. Then, the users who cannot complete the assigned tasks are identified.

Algorithm 1: C-DTT

Input: S; Social network, C: candidate users, Ti: number of tasks

Output: Expected users for task completion Ti

1. $U \leftarrow \emptyset$

2. While |U|<C

  1. for sS | U do
  2. $s \leftarrow \max \{\emptyset(U S\{s\})-\emptyset(U)\}$
    1. if ∆f(S|U)≥θ
  3. $U \leftarrow t$
  4. $S \leftarrow\{|S \| U|\}$
  5. Else
    1. If ∆f(S|U)≥θ
  6. $U \leftarrow U \backslash\{s\}$
    1. End if

              ii. End if

  1. End for
  2. Tasks Ti for the completion

 3. End while

 4. Return U

The integration of CCFO and decreasing threshold task allocation algorithm aims to find the expected number of tasks completed by the candidate users. The algorithm first assigns the tasks to the users in the candidate pool. Here all the tasks are evaluated to find the maximum incentives for the completion of all the allocated tasks. The marginal value is calculated for the incentives and this will be identified as the maximum threshold value. After identifying the threshold, the algorithm assigns all the qualified tasks to the available users and thus the tasks are completed with minimum incentives. We further introduced fast greedy selection algorithm that will identify the set of tasks that the users can complete. The algorithm consists of 2 phases. In the first phase, the algorithm will select the tasks to be completed. Here, sensing tasks are completed by selecting the users who can have the ability to complete the tasks. In the second phase, the pending tasks needs to be completed by the rest users. However, all the important tasks are completed in the first stage itself and only the parts need to be done in the second stage. Algorithm for C-FGS is given below.

Algorithm 2: C-FGS

Input: Social network, C: candidate users, Ti: number of tasks

Output: Expected users for task completion Ti

1. $U \leftarrow \emptyset$ , f=0

2. c & f=0 do

  1. for s S | U do
  2. s $\leftarrow$ max (number of complete}

3. if max (number of complete} ==0

  1. f=1

4. End if

               i. if ∆f(S|U)≥θ  

  1. $U \leftarrow t$
  2. $S \leftarrow\{|S||U|\}$
  3. Else
    1. If ∆f(S|U)≥θ
  4. $U \leftarrow U \backslash\{s\}$
    1. End if

             ii. End if

  1. End for
  2. Tasks Ti for the completion

5. End while

6. if |U|<C

7. $U \leftarrow U \backslash\{s\}$

8. End if

9. Return U

4. Results and Discussion

The performance of the proposed algorithm is evaluated by setting up the network topology where the candidates are distributed among the networks in the region of 5 x 5 km to determine the quality of sensing. As a first part of the work, the work uses Monte Carlo simulation to find the values such as mean, run time and objective function. We made an assumption that there are 200 tasks to be done and the threshold value is set based on the number of available candidate users. The proposed algorithm is evaluated by varying the number of candidates. The overall quality of the system is increased when the number of tasks getting increased and the quality is still higher in fewer candidates. Therefore, the algorithm works well even in limited number of users in the candidate pool. The run time analysis is shown in Figure 2 by comparing the proposed algorithm with SGA, and LDTT. The running time is also decreased when the algorithm is compared with other state of the algorithms. The expected number of tasks are analyzed by increasing the number of users such as C-FGS, LDTT and SGA as shown in Figure 3. The reason for the increased run time of the existing works is due to the fact that they are taking much computational processes for the allocation of tasks.

Figure 2. Comparison of run time analysis

From Figure 3, we observed that the number is increases when the number of candidates is also increased. It is acceptable because a large number of users can complete a greater number of tasks in a stipulated time. The proposed algorithm shows the good performance in the completion of tasks even in the limited number of users when compared to the traditional algorithms such as SGA, DTT, LDTT, and FGS. From Figure 4, we observed that the proposed C-FGS (COOT-fast greedy selection) algorithm outperforms the other algorithms and it assigns increased number of task when it is 60 and 200. Therefore, it is confirmed that C-FGS achieves highest allocation tasks The experimental analysis shows that the C-FGS algorithm improves the overall quality of the task allocation scheme and it achieves good results for the users in terms of assigned tasks and un assigned tasks.

Figure 3. Analysis of completion of task by increased users

Figure 4. Variation of number of tasks

5. Conclusions

Most of existing works are only based on assumptions in task scheduling about the number of candidate users and are mainly performed optimization of single task allocation. If the candidate users are few, then the completion of task with in the schedule can be difficult for many sensor applications. The proposed work in this paper aims to improve the quality of multi task allocations in mobile crowd sensing environment. The important objective of the work is to build a social network-based task allocation in crowd sensing. The eligible users are chosen for task completion based on their relationship in the social network. In this work, the sensing users are having cordial relationship in the network such as friendship, membership which can be helpful to assign the tasks to the users who is having good reputation values. The proposed work is compared with the state of the algorithm and it is observed that the work outperforms other algorithms in terms of running time, functional value and number of task allocations. However, there should be a privacy while choosing the sensing users to safeguard their private information. It is also important that the false identification reputation values should be avoided. As part of future work, we plan to propose a secured task allocation model by considering the above points in to account.


[1] Lu, A.Q., Zhu, J.H. (2020). Worker recruitment with cost and time constraints in mobile crowd sensing. Future Generation Computer Systems, 112: 819-831. https://doi.org/10.1016/j.future.2020.06.043

[2] Guo, W., Zhu, W., Yu, Z., Wang, J., Guo, B. (2019). A survey of task allocation: contrastive perspectives from wireless sensor networks and mobile crowdsensing. IEEE Access, 7: 78406-78420. https://doi.org/10.1109/ACCESS.2019.2896226

[3] Chen, J., Yang, J. (2019). Maximizing coverage quality with budget constrained in mobile crowd-sensing network for environmental monitoring applications. Sensors, 19(10): 2399. https://doi.org/10.3390/s19102399

[4] Ni, W., Cheng, P., Chen, L., Lin, X. (2020). Task allocation in dependency-aware spatial crowdsourcing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), Dallas, TX, USA, pp. 985-996. https://doi.org/10.1109/ICDE48307.2020.00090

[5] Zhou, L., Tokekar, P. (2019). Sensor assignment algorithms to improve observability while tracking targets. IEEE Transactions on Robotics, 35(5): 1206-1219. https://doi.org/10.1109/TRO.2019.2920749

[6] Sun, P., Wang, Z., Feng, Y., Wu, L., Li, Y., Qi, H., Wang, Z. (2020). Towards personalized privacy-preserving incentive for truth discovery in crowdsourced binary-choice question answering. In IEEE INFOCOM 2020-IEEE Conference on Computer Communications, Toronto, ON, Canada, pp. 1133-1142. https://doi.org/10.1109/INFOCOM41043.2020.9155429

[7] Liu, T., Zhu, Y., Huang, L. (2019). TGBA: A two-phase group buying based auction mechanism for recruiting workers in mobile crowd sensing. Computer Networks, 149: 56-75. https://doi.org/10.1016/j.comnet.2018.11.015

[8] Wu, H., Wang, L., Xue, G., Tang, J., Yang, D. (2019). Enabling data trustworthiness and user privacy in mobile crowdsensing. IEEE/ACM Transactions on Networking, 27(6): 2294-2307. https://doi.org/10.1109/TNET.2019.2944984

[9] Abasi, A.K., Khader, A.T., Al-Betar, M.A., Naim, S., Makhadmeh, S.N., Alyasseri, Z.A.A. (2020). Link-based multi-verse optimizer for text documents clustering. Applied Soft Computing, 87: 106002. https://doi.org/10.1016/j.asoc.2019.106002

[10] da Silva Santos, C.E., Sampaio, R.C., dos Santos Coelho, L., Bestard, G.A., Llanos, C.H. (2021). Multi-objective adaptive differential evolution for SVM/SVR hyperparameters selection. Pattern Recognition, 110: 107649. https://doi.org/10.1016/j.patcog.2020.107649

[11] Zhang, M., Yang, P., Tian, C., Tang, S., Gao, X., Wang, B., Xiao, F. (2015). Quality-aware sensing coverage in budget-constrained mobile crowdsensing networks. IEEE Transactions on Vehicular Technology, 65(9): 7698-7707. https://doi.org/10.1109/TVT.2015.2490679

[12] Yu, Z., Zhou, J., Guo, W., Guo, L., Yu, Z. (2018). Participant selection for t-sweep k-coverage crowd sensing tasks. World Wide Web, 21(3): 741-758. https://doi.org/10.1007/s11280-017-0481-x

[13] Wang, X., Wu, W., Qi, D. (2017). Mobility-aware participant recruitment for vehicle-based mobile crowdsensing. IEEE Transactions on Vehicular Technology, 67(5): 4415-4426. https://doi.org/10.1109/TVT.2017.2787750

[14] Zhao, Y., Guo, J., Chen, X., Hao, J., Zhou, X., Zheng, K. (2021). Coalition-based task assignment in spatial crowdsourcing. In 2021 IEEE 37th International Conference on Data Engineering (ICDE), Chania, Greece, pp. 241-252. https://doi.org/10.1109/ICDE51399.2021.00028

[15] Yucel, F., Yuksel, M., Bulut, E. (2021). Coverage-aware stable task assignment in opportunistic mobile crowdsensing. IEEE Transactions on Vehicular Technology, 70(4): 3831-3845. https://doi.org/10.1109/TVT.2021.3065688