Hybrid Two-Phase Task Allocation for Mobile Crowd Sensing

As a result of the popularity of mobile devices,Mobile Crowd Sensing (MCS) has attracted a lot of attention. Task allocation is a significant problem in MCS. Most previous studies mainly focused on stationary spatial tasks while neglecting the changes of tasks and workers. In this paper,the proposed hybrid two-phase task allocation algorithm considers heterogeneous tasks and diverse workers.For heterogeneous tasks,there are different start times and deadlines. In each round,the tasks are divided into urgent and non-urgent tasks. The diverse workers are classified into opportunistic and participatory workers.The former complete tasks on their way,so they only receive a fixed payment as employment compensation,while the latter commute a certain distance that a distance fee is paid to complete the tasks in each round as needed apart from basic employment compensation. The task allocation stage is divided into multiple rounds consisting of the opportunistic worker phase and the participatory worker phase. At the start of each round,the hiring of opportunistic workers is considered because they cost less to complete each task. The Poisson distribution is used to predict the location that the workers are going to visit,and greedily choose the ones with high utility. For participatory workers,the urgent tasks are clustered by employing hierarchical clustering after selecting the tasks from the uncompleted task set.After completing the above steps,the tasks are assigned to participatory workers by extending the Kuhn-Munkres (KM) algorithm.The rest of the uncompleted tasks are non-urgent tasks which are added to the task set for the next round.Experiments are conducted based on a real dataset,Brightkite,and three typical baseline methods are selected for comparison. Experimental results show that the proposed algorithm has better performance in terms of total cost as well as efficiency under the constraint that all tasks are completed.

Balancing D2D Communication Relayed Traffic Offloading in Multi-Tier HetNets

In Heterogeneous Networks (HetNets), Integrating Device-to-Device communication (D2D) techniques presents as a promising solution for improving system performance by offloading traffic from heavily loaded macro cell (MC) to small cells (SCs). For instance, D2D can be used to offload traffic from heavily-loaded cells to light-loaded small cells. However, offloading new users may result in an unfair load distribution among small cells and consequently may affect the quality of service of some users. To achieve better performance and reduce blocking probability load balancing among small cells should be considered when we offload traffic from macro to small cells. In this paper, we consider a centralized offloaded relay selection scheme, in which a cellular provider can decide whether users can assist each other to relay their traffic to small cells. We propose a joint user-relay selection with dynamic load balancing scheme based on D2D communications using the Kuhn-Munkres (K-M) method. The offloading process considers the load from MC to SCs and among SCs. Compared to previous works, our simulation results show that the proposed scheme increases the number of admitted users in the system, and achieves a higher load balancing fairness index among small cells. Also, our scheme achieves a higher rate fairness index among users by adjusting the signal to interference plus noise ratio (SINR) threshold.

An intelligent target detection method of UAV swarms based on improved KM algorithm

Complete and efficient detection of unknown targets is the most popular application of UAV swarms. Under most situations, targets have directional characteristics so that they can only be successfully detected within specific angles. In such cases, how to coordinate UAVs and allocate optimal paths for them to efficiently detect all the targets is the primary issue to be solved. In this paper, an intelligent target detection method is proposed for UAV swarms to achieve real-time detection requirements. First, a target-feature-information-based disintegration method is built up to divide the search space into a set of cubes. Theoretically, when the cubes are traversed, all the targets can be detected. Then, a Kuhn-Munkres(KM)-algorithm-based path planning method is proposed for UAVs to traverse the cubes. Finally, to further improve search efficiency, a 3 D realtime probability map is established over the search space which estimates the possibility of detecting new targets at each point. This map is adopted to modify the weights in KM algorithm, thereby optimizing the UAVs’ paths during the search process. Simulation results show that with the proposed method, all targets, with detection angle limitations, can be found by UAVs. Moreover, by implementing the 3 D probability map, the search efficiency is improved by 23.4%–78.1%.