Heuristic Traversal Path Algorithm Based on Linear Aggregation in Wireless Sensor Networks

Most wireless sensor networks (WSN) are deployed to monitor a region of interest for any intruding target. On the contrary, the intelligent target looks for the optimal path to traverse the enemy sensor networks for avoiding being detected. However, the target may be subject to traversal time constraint. It is difficult for most existing traversal algorithms based on breadth-first-search to satisfy a pre-determined time constraint value. Motivated by this reason, a traversal model is constructed and an approximately optimization algorithm is proposed in this paper. The algorithm makes the continuous path problem domain a discrete one by Voronoi diagram. Using exposure and traversal time as the path performance metric, the algorithm combines the linear aggregated routing mechanism to find the optimal path. It enables the intelligent target to traverse the enemy sensor networks field. And the traversal time from the source to the destination is less than a given threshold. Theoretically and experimentally, it is concluded that the proposed algorithm is able to solve the traversal path problem with time constraint. The k shortest path heuristic traversal path algorithm based on linear aggregation (kSP-LAHTP) is able to find a traversal path closer to the optimum with parameter k increasing.