Optimization of data harvesters deployment in an urban areas for an emergency scenario

摘要

Since its appearance in the VANETs research community, data collection where vehicles have to explore an area and collect various local data, brings various issues and challenges. Some architectures were proposed to meet data collection requirements. They can be classified into two categories: Decentralized and Centralized self-organizing where different components and techniques are used depending on the application type. In this paper, we treat time-constrained applications in the context of search and rescue missions. For this reason, we propose a centralized architecture where a central unit plans and manages a set of vehicles namely harvesters to get a clear overview about an affected area. But, choosing the optimal number of harvesters to be deployed and the corresponding area to explore for such time-constrained applications are a real issue. In this paper, we model the problem with its constraints, then we propose a heuristic algorithm called Variable Neighborhood Search (VNS) to get the optimal number of harvesters and define areas to be explored by each one. The proposed solution combines two algorithms: The first is a greedy Best Insertion heuristic reshaped to meet our problem definition to get an initial solution and the second is a 2-Opt merged with a String Exchange heuristics which defines neighborhoods and responsible for local search and global optimization of the initial solution. Finally, the solution is analyzed regarding its optimality and the CPU calculation cost.