Enhancing Task Assignment in Crowdsensing Systems Based on Sensing Intervals and Location

Rasha Sleem,Nagham Mekky,Shaker El-Sappagh,Louai Alarabi,Noha A.Hikal and

Mohammed Elmogy1

1Faculty of Computers and Information,Mansoura University,Mansoura,35516,Egypt

2Faculty of Computers and Artificial Intelligence,Benha University,Banha,13518,Egypt

3Faculty of Computer Science and Engineering,Galala University,Suez,435611,Egypt

4College of Computer and Information Systems,Umm Al-Qura University,Mecca,715,Saudi Arabia

Abstract: The popularity of mobile devices with sensors is captivating the attention of researchers to modern techniques,such as the internet of things(IoT) and mobile crowdsensing (MCS).The core concept behind MCS is to use the power of mobile sensors to accomplish a difficult task collaboratively, with each mobile user completing much simpler micro-tasks.This paper discusses the task assignment problem in mobile crowdsensing, which is dependent on sensing time and path planning with the constraints of participant travel distance budgets and sensing time intervals.The goal is to minimize aggregate sensing time for mobile users, which reduces energy consumption to encourage more participants to engage in sensing activities and maximize total task quality.This paper introduces a two-phase task assignment framework called location time-based algorithm(LTBA).LTBA is a framework that enhances task assignment in MCS, whereas assigning tasks requires overlapping time intervals between tasks and mobile users’tasks and the location of tasks and mobile users’paths.The process of assigning the nearest task to the mobile user’s current path depends on the ant colony optimization algorithm(ACO)and Euclidean distance.LTBA combines two algorithms:(1)greedy online allocation algorithm and(2)bio-inspired traveldistance-balance-based algorithm(B-DBA).The greedy algorithm was sensing time interval-based and worked on reducing the overall sensing time of the mobile user.B-DBA was location-based and worked on maximizing total task quality.The results demonstrate that the average task quality is 0.8158,0.7093,and 0.7733 for LTBA,B-DBA,and greedy,respectively.The sensing time was reduced to 644, 1782, and 685 time units for LTBA, B-DBA, and greedy, respectively.Combining the algorithms improves task assignment in MCS for both total task quality and sensing time.The results demonstrate that combining the two algorithms in LTBA is the best performance for total task quality and total sensing time,and the greedy algorithm follows it then B-DBA.

Keywords: Mobile crowdsensing; online task assignment; participatory sensing;path planning;sensing time intervals;ant colony optimization

1 Introduction

The popularity of mobile devices that consists of internal sensors (camera, temperature, microphone,GPS,Wi-Fi/3G/4G interfaces,accelerometer,etc.)and external sensors(Google glass,healthcare sensors, wearable sensors, etc.) is captivating the attention of researchers for the internet of things (IoT) [1,2] and mobile crowdsensing (MCS) [3,4] techniques.MCS is a novel paradigm of crowdsourcing that is a methodology in which many people use their mobile sensors for sensing,collecting,sharing data,and extracting information to analyze[5].

Comparing MCS with traditional sensor networks, one of the significant benefits is the active participation of workers in the collection and sharing of sensing data.This is attributed to that MCS is a powerful paradigm because of has extraordinary sensing requirements [5–8].The sensing requirements, communication capabilities, and computation allow smartphones to execute more complicated tasks.There are many applications examples of MCS include intelligent transportation [9], air quality monitoring [10], road traffic monitoring [11], surface monitoring of road pavements [12], noise level sensing, location-based/mobile/spatial crowdsourcing, smart cities,etc.

Participatory sensing and opportunistic sensing are the two paradigms of MCS.Active engagement of mobile users is not required in opportunistic sensing [13], and mobile users typically walk along predetermined pathways or follow movement patterns driven by their everyday schedules,tastes, or desires.Mobile devices may be designed to capture sensing data when their owners travel automatically.Mobile users are expected to travel to certain task sites to complete those activities in participatory sensing[14].The motions of such users are planned around delegated sensing tasks,and their participation is voluntary and regulated.

Mobile crowdsensing had many challenges for research, such as maximizing data and tasks quality,minimizing sensing cost,privacy guarantee,the storage and energy limitation of mobile node resources,and task assignment.To overcome these challenges,this work focuses on the tasks assignment considering various constraints, such as spatial coverage travel budget, energy consumption,travel cost,sensing time intervals,and sensing task quality[15].To maximize the sensed data quality,the scenario allocated sensing tasks to a suitable number of participants in a certain area with minimum sensing time.

MCS process consists of:(1)requesters,who send tasks,(2)workers,who have sensor-rich devices,and(3)platform,which receives sensing tasks from requesters and allocates them to workers then sends data back to requesters.The relationship between workers and tasks is critical to the success of MCS applications.The sensing tasks are an essential part of the sensing process.

Selecting tasks for a mobile user might be difficult because different task assignment schemes have varying assignment criteria.Therefore the online task assignment problem for MCS is described in this work.There are many challenges for allocating tasks for a mobile user:

■Challenge 1: There is a large number of sensing tasks for a large number of participants,and a single mobile user may participate in multiple sensing tasks.The sensing tasks need data from various sensors at various times.

■Challenge 2:Encourage more people to engage in sensing activities.

■Challenge 3:Determine whether the task has the smallest increasing aggregate sensing time assigned to a mobile user.

■Challenge 4:Locating the nearest task for the mobile user whose total travel budget is less than the worker’s total travel distance.

To address these challenges, there are two mechanisms.First, reducing the total sensing time of mobile users reduces energy consumption to encourage more participants to engage in sensing activities.Second,determining the location of both mobile users and tasks then choosing the nearest task to the mobile user’s path.This work presents a framework location time-based algorithm(LTBA).The framework works on reducing total sensing time based on overlapping in sensing time intervals and assigning the nearest task to the path of the mobile user.Reducing total sensing time and increasing task quality incentivizes mobile users to participate in mobile crowdsensing applications.

LTBA enhances performance metrics for total tasks quality and aggregate sensing time.LTBA combines two algorithms: (1) greedy online allocation algorithm [16,17] and (2) bio-inspired traveldistance-balance-based algorithm(B-DBA)[18].B-DBA was location-based and worked on maximizing total task quality.The greedy algorithm was sensing time interval-based and worked on reducing the overall sensing time of the mobile user.Combining the algorithms improves task assignment in MCS for both total task quality and sensing time of both mobile users and tasks.

The scenario has a sensing task setTand a mobile worker setMthat arrive in sequence at the service platform.Their arrival obeys a Poisson distribution without knowing what will happen next.The service platform must reply to each incoming request,and delegate tasks in the tasks setTto users in the users setM.The smartphone’s sensing capabilities can be fully utilized.Because of location privacy for mobile users in mobile crowdsensing,the cases focused on where they are anonymous,and no single mobile user’s contribution history is tracked.

The main contributions of this paper are summarized as follows:

■This work formulates and enhances the problem of sensing tasks assignment in MCS by a tradeoff between maximizing total tasks quality and minimizing aggregate sensing time.

■Considering two critical attributes:sensing time of mobile user and location of both tasks and mobile user.

■For improving tasks assignment,this work proposes a combination of two algorithms:(1)greedy online allocation algorithm and(2)B-DBA.

■Overlapping or covering in the sensing time interval, in this scenario, the service platform divides the available tasks into two task groups based on the complete or partial intersection in time intervals of tasks and mobile user’s task pool.

■Determining the nearest task.The service platform chooses the nearest task in the available task set to the mobile user’s path without exceeding budget constraints for increasing task quality.Selecting tasks depends on the ant colony optimization algorithm (ACO) [19] and Euclidean distance.

■Both synthetic and real-world data are used.The synthesis data set is used to generate information on tasks and mobile users.The real data set is for the location of both tasks and mobile users.

The rest of the paper is structured as follows.Section 2 introduces previous work.Section 3 formulates the task assignment problem and designs the system models.Section 4 discusses in detail the combination of two task assignment algorithms.Section 5 discusses the results’ simulation for success assessment.Finally,Section 6 concludes the work and represents the future direction.

2 Related Work

In this section,some previous work that studied task assignment problems based on two attributes:sensing time and location of both sensing tasks and mobile users are addressed.MCS employs smartphones to collect data on a much bigger scale than is possible with traditional methods.Selecting tasks for a mobile user might be difficult because different task assignment schemes have varying assignment criteria and objectives.For example,Zhao et al.[16,17]introduced two allocation algorithms, approximation algorithm for offline model and greedy algorithm for the online model.Allocating tasks with mobile users was depended on time overlapping between tasks’sensing intervals that needed the same sensing services from mobile users.They focused on the energy consumption of smartphones,fairness in assigning tasks,and task arrivals that were dynamic and unexpected.They did not work on heterogeneous sensing tasks or with flexible times’starting and ending and concentrated on reducing smartphone sensing time,but no energy savings have been reported.

Gong et al.[18,20]designed four algorithms to assign workers based on the location of tasks and the current location of workers to increase task quality.Whereas quality/progress-based algorithm(QPA) chose the work with the highest task quality increment to trip cost ratio, task density-based(TDA)tended to direct users to high task-density regions.At the same time,travel-distance-balancebased(DBA)considered journey distance balance information.Bio-inspired travel-distance-balancebased(B-DBA),the final algorithm,combines the travel-distance-balance-aware measure in DBA with a bio-inspired search to further boost job assignment performance.One type of task was assigned to workers.

Wang et al.[21] used spatiotemporal correlations to address heterogeneous crowdsensing tasks.They involved all sharing the same resources but had different spatiotemporal granularities.They used assignment stages such as intra-and inter-task.To enhance the time efficiency,they developed a decomposition-and-combination framework.They aimed to improve data quality while reducing the total incentive budget.

Xia et al.[22] employed geoindistinguishability to make workers’location privacy more secure and minimize workers’travel distance.So,they designed two probability-based distance comparison mechanisms,the worker-based distance comparison mechanism(WDCM)and the task-based distance comparison mechanism (TDCM).Yin et al.[23] introduced task assignment in crowdsourcing platforms by allocating one task to multiple workers using a many-to-one matching approach.They focused on budgetary limits, quality requirements of tasks, and heterogeneity in sensing tasks and workers.Tao et al.[24]worked on the task assignment that depended on the location of both workers and tasks to maximize data quality and increase worker profit.They provided a genetic algorithm(GA)and a detective algorithm(DA).

Miao et al.[25,26]assigned crowdsourcing task allocation dependent on participant position.The aim is to use a quality-aware online task assignment(QAOTA)algorithm to improve overall efficiency for location-based tasks.Gad-ElRab et al.[27]classified tasks based on sensors that required providing interval tree structure in interval tree-based task scheduling method (ITBTS) and determined the overlapping between sensing time instances to minimize the energy consumption and time for the sensing process.Lai et al.[28] focused on the sensitive duration of each task and the capabilities of participants.The objective was to increase the number of tasks that were completed.For allocating tasks to participants,that article used a greedy heuristic algorithm.Xiao et al.[29]studied mobile social networks(MSNs)using MCS to solve the makespan-sensitive task assignment.The goal for different types of sensing tasks was minimizing the average or the largest makespan.Average makespan sensitive online task assignment(AOTA)algorithm and the largest makespan sensitive online task assignment(LOTA)algorithm.

Wu et al.[30] evaluated the extrinsic and intrinsic ability of mobile users for allocating tasks.A modified Thompson sampling worker selection(MTS-WS)algorithm was context-aware that was designed to evaluate a worker’s service quality.Huang et al.[31]outlined task assignments based on the performing task time.They illustrated a task assigning technique called the optimized allocation scheme of time-dependent tasks(OPAT)to increase each mobile user’s sensing capacity.

The previous studies focused on the sensitive duration of tasks, sending tasks, receiving results,context or location.Tab.1 summarizes previous literature on task assignment problems in MCS.This paper addresses the task assignment,total sensing time,and path planning problem.The requests of mobile crowdsensing tasks determine the time interval for sensing the required data in specific regions.For the mobile user’s tour,he moves from his starting point to his destination.In contrast,this work differs from them in terms of problem definition.It redefines the task assignment problem by working with task sensing time interval and location for both tasks and mobile users’constraints.Combining the two metrics improves the task assignment process in MCS, increasing the total task quality and reducing the overall aggregate sensing time.

Table 1: A summary of some of the current related work

Table 1:Continued

3 The Proposed Method

This section discusses the system model and constructs the problem of online task assignment based on two constraints: (1) task sensing time interval and (2) location for both task and mobile user(the starting location and predetermined destination).The next subsections illustrate the system model, task model, mobile user model, and algorithm design.Fig.1 illustrates the proposed framework.The proposed framework is explained in detail in Subsection 3.4.The proposed framework consists of three phases.First,the preprocessing phase sets available tasks into task setTand mobile users into worker setM.Second,overlapping or covering in time interval phase divides the available tasks into two task groups based on a complete or partial intersection in time intervals of tasks and worker’s task pool.Third,determining the nearest task phase chooses the nearest task in the available task setTto mobile user mipath.

3.1 System Model

In the MCS sensing process,a mobile user mi has a tour from his starting point to his destination.The requests of mobile crowdsensing tasks determine the time interval for the sensing required data in specific regions.A mobile user mi is allocated with sensing tasks in mi path without exceeding mi travel budget.In a real-time system,requesters’mobile users and tasks arrive at the service platform online sequentially.The service platform must reply to each incoming request without knowing what will happen next.Because of location privacy for mobile users in MCS,this work focuses on cases where users are anonymous,and no single mobile user’s contribution history is tracked.The assignment is dependent on the tasks that are still available on the service platform that have arrived and have not yet expired.The algorithm regards tasks that demand the same sensing service from mobile users to be homogeneous.Tab.2 shows a list of notations that are used in this work.

Figure 1:The framework of location time-based algorithm(LTBA)

Table 2: The basic notations in this work

Table 2:Continued

3.2 Task Model

Requesters send sensing tasks to the service platform that are published dynamically upon their arrival.The sensing tasks set are denotedT={t1,t2,.....,tn}every task has attributes such as tj={TID,TLoc,sj,ej,p˙j},?ti∈T,where TIDis the composition of task id and the task number,TLocrepresents longitude and latitude of task location,sjis the start of sensing time interval for tj,ejis the end of sensing time interval andp˙jdenotes the probability,that a randomly selected mobile user would provide correct data for task tj.For each task tj,the increment of aggregate sensing time of mobile user miis checked if task tjis allocated to it as[16]:

whereliis the aggregate sensing time of mobile user mi.The number of mobile users who perform a task denoted bykaffects the task quality function Ap˙j(k) in [18].Because the reliability of each individual mobile user is unknown,the outcome is assumed using the majority voting rule:

■for odd values ofk:

■else,

wherekis the number of mobile users that perform task tjand a non-negative integer.p˙jis more than 0.5.This is due to the fact that for tasks with pjless than 0.5, the mobile users’results are reversed,then correct answers are obtained with a probability greater than 0.5.The task quality increases with oddkand stays the same otherwise.In[18],an auxiliary function Fpj(k)is designed to smooth quality function.

■for zero and odd values of k:

■else

3.3 Mobile User Model

The mobile user intended to travel from his or her current location to a destination.The service platform assigns tasks to mobile users’tours to perform without exceeding their travel budget.Every mobile user sends his information to the service platform.Mobile users set is denoted asM= {m1,m2,....,mm}.Every user has attributes such as mi={UID,iniLoc,desti,Bi,Mi},where UIDrepresents both mobile user number and id, iniLocis the current location of user mi, destiis the predetermined destination of user mi,Birepresents traveling distance budget.Miis the maximum number of sensing tasks that he can execute.The mobile user is now at iniLocand plans to go to desti.However,completing tasks can require him to take a detour,resulting in extra travel costs.The overall travel cost does not surpass Bi.Any function that measures the cost of traveling from one place to another can be used to calculate the travel cost.In this work,Euclidean distance is used.

■Mobile user sensing time constraint:

■Mobile user capacity constraint:

■Mobile user travel cost budget constraint:

■

whereΔlij=lij-li.liis the sensing time of mobile user mi.lijis the sensing time of miafter assigning task tj.Δlij=0 means that the sensing interval of task tjis within a task interval inPmi.Pmiis a task pool that contains mobile user tasks.|Pmi|is the number of tasks in a mobile user’s task pool.dist(locik,locj)denotes the distance between current mobile user locationlocikand task locationlocj.dist(iniLoc,desti)is the travel distance between the starting location to the destination of mobile user mi.θdenotes travel budget ratio.

3.4 Algorithm Design

The sensing tasks and mobile users arrive at the service platform upon arrival rate.At each time instance,the service platform schedules available tasks in task setTand available mobile user in worker setMbased on the sensing time interval of each task and location of both tasks and workers.LTBA algorithm consists of three phases:

1) Preprocessing phase:In this phase, the service platform sets available tasks into task setTand mobile users into worker setM.To explain this phase in detail, at each time instance of arrival rate,the service platform adds the arrival tasks to task setTand the arrival mobile user to worker setM, then extracts tasks’attributes (i.e., location TLoc, start sensing time sj,end sensing time ejand task correctnessp˙j)and mobile user’s attributes(i.e.,current location iniLoc,destination desti,path length,sensing timeli,distance budgetBiand capacityMi).The path length is the total travel distance of the mobile user from starting location to the current location,passing through all tasks in the worker’s task pool Pmi.Sensing time for miis the sum of sensing time for tasks in the worker’s task pool Pmi.CapacityMiis the maximum number of tasks that user mican execute.

2) Overlapping or covering in time interval phase:In this phase, the service platform divides the

available tasks into two task groups based on the complete or partial intersection in time intervals of tasks and worker’s task pool.To explain this phase in detail,mi in worker setΔlij is determined for each mobile user,representing the increasing sensing time for miafter allocating task tjto him,whereΔlij=lij-li.

For example,a mobile user mihas task tj[2,5]in task pool Pmi.Task set contains tx[3,4],ty[4,6],and tz[6,8].Each task has to sense intervalI=[sj,ej].The sensing time for mi,lij=l{[2,5]}=3.There are some cases to select the best task,

1.In the case of adding txto Pmi,sx＞sjand ex＜ej,so txis covered by tj.lijx=l{[2,5]∪[3,4]}=l{[2,5]}=3 andΔlijx=lijx-lij,Δlijx=0.

2.In the case of adding tyis Pmi, so,lijy=l{[2,5]∪[4,6]}=l{[2,6]}=4 andΔlijy=1.There is overlapping between tjand ty.

3.In the case of adding tzto Pmi,so,lijz=l{[2,5]∪[6,8]}=3+2=5 andΔlijz=2.

From the previous example,the delta sensingΔlij and the sensing time lij are smaller in cases 1 and 2.In case1,tx is covered by tj.In case 2,there is an overlapping between tj and ty.So,the chance of choosing these tasks for the next phase is greater.Then dividing available task set into two groups,one has tasks with smaller sensing time and the other with greater sensing time.In this phase, the algorithm uses two rules[16].“Rule 1:assigning a task to a smartphone if it can be fulfilled by other tasks already assigned to that smartphone.Rule 2:assign a task to the smartphone with the shortest aggregate sensing time if the task were to be assigned.

3) Determining the nearest task phase:In this phase,the service platform chooses the nearest task in the available task setTto mobile user mipath.To explain this phase in detail,use the task group TGi with smaller sensing time from the previous phase to find the nearest mobile user mithat exceeds the mobile user’s budget.The algorithm uses B-DBA[18].Selecting the nearest tasks process depends on the ACO algorithm and Euclidean distance[32].

For ACO,intelligent ants begin their moves to search for food randomly.When an ant finds food,it returns to the colony and leaves a trail of pheromones.Other ants use that route in search of food if they detect the pheromone.The pheromone fades with time,preventing the algorithm from reaching a local optimum solution.The basic idea of B-DBA was dependent on the bio-inspired search and travel distance.B-DBA works as follows:it consists of rounds where(round ＞1).Each round has a group of ants that move from the user’s current position and all available tasks to the destination.In the first round,the initial global pheromoneτ0is the same for each task location.Then measure preferences of the available tasks using Eq.(10)for each ant to select the next task’s location in the user’s tour.

Euclidean distance between two locations:

whereτtail,tjdenotes local pheromone between the current user’s location and task tj.ε,γandαare weighting parameters.length(pi)is path length of user mi.dist(ptail,tj)denotes distance between current user’s location and tasktj.edijdenotes distance between user’s destination and tasktj.lattail and lontailare latitude and longitude of current user’s location.latt and lontare latitude and longitude of task’s location.

The chance of selecting task tj as the next task depends on its probability and performance value.The highest preference value of task tj gives a high probability to tj to be chosen as the next task.The pheromone on the path between task tj and the current path tail is reduced by evaporation rateλ,when selecting tj as the next task.For updating local pheromone:

After determining all ants’ pathways for one round, select the two highest increments of task quality of two ants.The best two ant’s global pheromones of task locations are increased byτ0for the best ant andτ0/2 for the second-best ant,on the path that they follow,then a new round starts after all local pheromones have been modified to match their global pheromones.

Algorithm 1 illustrates the steps of the LTBA scenario.New tasks from available tasks are assigned to mobile users at every arrival without exceeding the budget and capacity constraints.Line 2 initializes,sensing time,delta,and creates task group TGiset.Lines 3 and 4 calculate sensing time by CalcSensingTime()function at Algorithm 2 and delta sensing time for each task tj,if it is added to the worker’s task pool.Lines from 5 to 9 check if task covered by any tasks in worker’s pool,then add tj to TGielse add sensing time and delta sensing to subsetsΔ,TL.Line 12 checks for overlapping and append those tasks with minimum delta and sensing time to TGi.Line 13 calls TGito TheClosestTask()function.

CalcSensingTime () at Algorithm 2 checks the length of the worker’s pool to determine sensing time then return it.TheClosestTask()function at Algorithm 3 is used to find the nearest task tj in the mobile user mipath.Line 2 determines the global pheromone for the tasks in TGi.Using iteration of rounds to select the nearest task.Line 4 uses a global pheromone as a local pheromone.Line 5 makes iterations for a group of ants to select the best next task.Lines from 6 to 11 calculate preference for each task,and the task with the maximum preference is selected,then update the local pheromone of the chosen task.At the end of ant iterations,choose the best two ants,update the global pheromone of tasks chosen, and start a new round iteration.Line 16 adds the nearest task tj to the worker’s pool Pmi.

?

?

Algorithm 3:Procedure for TheClosestTask()function.Input:TGi.Output:choose the Closest tj to the path of mi.1:function TheClosestTask(TGi)2: calculate global pheromone τ0 3: for round=1:30 do 4: τtail,j ←τ0 5: for ant=1:30 do 6: Calculate preference for ant 7: to find next task using Eq.(10).8: pre(tj)=τε tail,tj.ΔFpj·(Bi-length(ti)-dist(ttail,tj)-eij)α dist(ttail,tj)γ 9: choose next task with max preference 10: then update local pheromone for the newly 11: chosen task Eq.(12)12: end for 13: choose the best two ants then update 14: global pheromone of tasks’chosen 15: end for 16: Pmi←tj 17:end function

4 Experimental Results

In this section,the performance is measured using two metrics:total task quality and aggregate sensing time.This work aims to reduce total sensing time that reduces energy consumption, and increase the quality of tasks metrics to encourage more participants and tasks requesters to engage in sensing activities.The default parameter settings are discussed in the next subsection.The B-DBA and greedy online allocation algorithms are used as the performance comparison baseline with LTBA.The used dataset and simulation settings are illustrated in the next Subsections 4.1 and 4.2.

4.1 Dataset

This paper uses both synthetic and real-world datasets.The synthesis data set is used to generate information on tasks and mobile users.The real data set is for the location of both tasks and mobile users.Gowalla[33]is the real data set,a location-based social networking service where users check in to report their whereabouts.It contains user-id,check-in time,latitude,longitude,and location id.The location of tasks and mobile users is selected spatially uniformly distributed from 5000 data set records.

4.2 Evaluation Metrics

The algorithms were implemented using MATLAB R2018a and running on a laptop with 16 GB memory and Intel Core i7-8550U CPU.Both synthesis and real datasets are used.Calculating the average of total tasks quality performance by:

where n is the number of tasks,and aggregate sensing time by:

The default parameters for sensing tasks are as follows:the arrival rate,location,the end of sensing task intervals, and the probability of task correctness.Poisson distribution is used to determine the arrival rate for tasks that are spatially uniformly distributed.The task arrival rate is set to 2.0 by default.The task-lasting time intervals follow a normal distribution with default mean and standard deviation values of 100 and 30,respectively.The probability of a task correctness pjfollows a normal distribution with 0.8 and 0.15 as the default mean and standard deviation,respectively.

The default parameters for mobile users are as follows:the arrival rate,the current location,the travel budget ratio, and capacity.For the arrival rate, Poisson distribution is used and set to 1.0 by default.The starting location and predetermined destination are spatially uniformly distributed.The shortest trip distance between mobile users’ starting location and destination is denoted as travel budget ratio (≥1) that follows a normal distribution with default 1.5 and 0.6 values for mean and standard deviation,respectively.Capacity is set to 3.

The default setting for LTBA and DBA parameters,γis 1, weighting parametersεis 3,evaporation rateλis 0.9.Furthermore, theroundnumber and theantpopulation size are set to 30 and 30, respectively.Euclidean distance is used to measure the distance between tasks’location and the mobile user’s current location.The default parameter settings are displayed in Tab.3.

Table 3: The parameters settings

4.3 Parameters Analysis

These parameters are determined by trial and error to achieve the best performance for the tradeoff between higher task quality and lower sensing time in LTBA than in B-DBA and greedy.The travel budget of mobile users is computed as Bi=dist(iniLoc,desti)*θ.θf(wàn)ollows N(μθ,σθ)and the probability of a task correctness pjfollows N(μpj,σpj)as[18]and[25].

Effects of theantpopulation size on optimum solution, execution time, and pheromone buildup [34].The performance of the algorithm is not improved by having a largeantpopulation size.As a result,a limited number is recommended.In general,to restrict the worst-case complexity,the values ofroundandantare small.CapacityMiis set to 3, which largely restricts the worst-case complexity.

5 Simulation Results

There are several scenarios for parameters settings that influence the tasks’quality and sensing time.The simulation results for parameters of different algorithms are presented.Varying parameter settings,while the default values are used for other parameters.

5.1 The Impact of γ

The impact ofγon tasks’ quality in Fig.2a and sensing time Fig.2c.γis tested in the range[1,5],increasing by 1.The quality of The total task is higher for both LTBA and B-DBA atγequal 2.However,sensing time is less atγequal to 1.The tasks’quality and sensing time are constant in the greedy online allocation algorithm.The expected value ofγis 1 or 2.To determineγ,the difference in values is calculated.The difference in the quality value atγof 1 and 2 is very small,but the difference in the sensing time atγ1 and 2 is large.γis equal to 1 for the optimal value for both task quality and sensing time.

Figure 2: y and task lasting time intervals settings vs. total tasks quality and overall sensing time.(a)The impact of y on tasks’quality.(b)The impact of the task-lasting time interval on tasks’quality.(c)The impact of y on sensing time.(d)The impact of the task-lasting time interval on sensing time

5.2 The Impact of Sensing Time Intervals

In this test,the simulations are to see how the lasting task interval impacts different algorithms.The task-lasting time interval follows a normal distribution with a default mean equals to 30.Figs.2b and 2d illustrate the average tasks quality and total sensing timevs.standard deviation value that is changed from 80 to 160.The task-lasting time interval is set to be 100 to achieve the best performance for both quality and sensing time for LTBA sensing time.

5.3 The Impact of Task Arrival Rate

In this test, we are varying the task arrival rate from 1.0 to 5.0.Figs.3a and 3c present the performance of average task quality and overall sensing time under different settingsvs.varying task arrival rates.In LTBA,the peak for the average task quality is at an arrival rate of 4.0,and the next is at an arrival rate of 2.0.However,the minimum value of the sensing time is at a task arrival rate of 3.0,and the next is at 2.0.In B-DBA and greedy,the peak is at 2.0.Therefore,the task arrival rate is set to be 2.0 to achieve the optimal solution for increasing the average task quality and decreasing the sensing time for LTBA.

Figure 3:The arrival rate settings for both tasks and mobile users vs.total tasks quality and overall

5.4 The Impact of Mobile User Arrival Rate

In this test,we are varying the mobile user arrival rate from 1.0 to 5.0.Figs.3b and 3d illustrate the performance of average task quality and overall sensing time under different settingsvs.varying mobile user arrival rates.The peak of the average task quality is at the mobile user arrival rate of 1.0 for LTBA,B-DBA,and greedy.The minimum value of the sensing time is at a mobile user arrival rate of 1.0 for LTBA and greedy but for B-DBA is at 5.0.Therefore,the mobile user arrival rate is set to be 1.0 to achieve the optimal solution for increasing the average task quality and decreasing the sensing time for LTBA.

5.5 Different Cases of Tasks and Mobile Users

In Figs.4a and 3b,different cases of tasks and mobile users are tested.In the case of increasing tasks and mobile users,the total task quality decreases,and the overall sensing time increases.LTBA is the best total task quality and the least sensing time,and the greedy algorithm follows it.The B-DBA algorithm performs the worst if the number of tasks is greater than the number of mobile users.LTBA is better than sensing time but smaller than the greedy algorithm in total task quality.

Figure 4:The different cases of tasks and mobile users vs.(a)total tasks quality and(b)overall sensing time

5.6 Discussion

The previous observation motivates us to investigate the problem of assignment sensing tasks for minimizing sensing time while maximizing total task quality based on sensing time and path planning attributes.However,there are still a number of major challenges to be resolved.Striking a good balance between maximizing overall job quality and minimizing sensing time is extremely important.

The requesters determine the time interval for each sensing task to collect the required sensing data and the area of interest.In the proposed method,the covered phase is used because the optimal solution remains optimal after assigning tasks covered by the optimal solution tasks.The optimal aggregate sensing time remains constant.

This work uses the D-BDA, which consists of a bio-inspired search algorithm and a traveldistance-balance-based Algorithm(BDA).ACO is easy to integrate with other methods,and it excels at solving challenging optimization problems.The idea of BDA is based on whether there are two possible tasks to consider:1 and 2.The work quality increment is the same for both tasks,as is the extra trip distance.The distance between task 1 and the user destination,on the other hand,is substantially greater than the distance between task 2 and the user destination.As a result,if task 1 is chosen,a far larger travel distance budget must be set aside for the user to arrive at his or her destination finally.If task 1 is chosen,the trip distance budget for visiting other task sites will be considerably reduced.We should act based on this observation.

Using the default parameter settings in Tab.3 to calculate both total task quality and sensing time for LTBA,B-DBA,and greedy.Tab.4 shows the results.The results demonstrate that combining the two algorithms in LTBA is the best performance for total task quality and total sensing time, and the greedy algorithm follows it then B-DBA.Combining the algorithms improves task assignment in MCS for both total task quality and sensing time.

Table 4: The results of the compared algorithms

The computational complexity of function that calculates sensing time for all available sensing tasks is O(n).The function that determines the closest task to the mobile user path has O(rρlog n)whereris theroundnumber andρis size ofantpopulation.The computational complexity of the available mobile user set for LTBA is O(n log n).

The performance metric for task assignment is based on task quality.D-BDA was compared with quality-aware online task assignment QAOTA [25], which improved the overall task quality of location-based.QAOTA has the lowest performance and the highest complexity.So,LTBA is the best performance for total task quality and total sensing time, and the greedy algorithm follows it, then B-DBA then QAOTA.

6 Conclusion

This work presents LTBA that enhances the task assignment in MCS,whereas assigning tasks is restricted by time intervals and location of both tasks and mobile users.LTBA aims to achieve the best performance for the tradeoff between higher task quality and lower sensing time.LTBA combines two algorithms:(1)B-DBA,which was location-based and focused on increasing total task quality,and(2)the greedy online allocation algorithm,which focused on minimizing overall sensing time for mobile users.Minimizing the aggregate sensing time of the mobile user is based on the overlapping between sensing time intervals.The process of assigning the nearest task to the mobile user’s current path depends on the ACO algorithm and Euclidean distance.Using a combination of the two algorithms to improve task assignment in MCS enhances task quality and reduces overall sensing time for mobile users.Under various settings,LTBA outperforms the compared algorithms(B-DBA and greedy).The future study will investigate ways to increase the performance of the proposed algorithm as well as investigate their performance in other scenarios, such as discussing the privacy of mobile workers’locations.The heterogeneous crowdsensing tasks will be the scope of the next work to maximize the quality of the collected data.

Funding Statement:The authors received no specific funding for this study.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.