Deep Reinforcement Learning and Prim's Algorithm for $k$-Coverage in Wireless Sensor Networks

Abstract

Wireless Sensor Networks are fundamental to modern monitoring applications, where extending the life of the network is the most critical challenge. For applications that require high reliability and fault tolerance, ${k}$-coverage is an appealing solution, where every point is covered (or sensed) by at least ${k}$ sensors simultaneously. Although analytical methods can determine optimal static deployments, they often lack the flexibility to adapt to dynamic network conditions, such as node failures. Furthermore, many energy saving algorithms only focus on minimizing the number of active sensors but neglect the significant communication energy required for these nodes to form a connected network. This paper addresses this gap by proposing a holistic adaptive framework based on deep reinforcement learning (DRL). We design a Deep Q-Network agent that learns to solve the connected ${k}$-coverage problem by processing a rich, image based representation of the entire network state. The core innovation of our approach lies in the design of a sophisticated reward function that integrates communication efficiency. At each step, we use Prim's algorithm to calculate the cost of the minimum spanning tree connecting all active nodes, and this cost is used as a direct penalty in the agent's reward. This forces the agent to learn a robust policy that simultaneously balances three competing objectives: maintaining ${k}$-coverage, minimizing the number of active sensors, and ensuring a geographically efficient communication backbone. Simulation results demonstrate that our DRL agent significantly outperforms static optimizers like differential evolution, achieving superior ${k}$-coverage reliability and efficiency, while extending the network lifetime.