Approximate dynamic programming for condition-based node deployment in a wireless sensor network

The flexibility of deployment strategies combined with the low cost of individual sensor nodes allow wireless sensor networks (WSNs) to be integrated into a variety of applications. Network operations degrade over time as sensors consume a finite power supply and begin to fail. In this work we address the selective maintenance of a WSN through a condition-based deployment policy (CBDP) in which sensors are deployed over a series of missions. The main contribution is a Markov decision process (MDP) model to maintain a reliable WSN with respect to region coverage. Due to the resulting high dimensional state and outcome space, we explore approximate dynamic programming (ADP) methodology in the search for high quality CBDPs. Our model is one of the first related to the selective maintenance of a large-scale WSN through the repeated deployment of new sensor nodes with a reliability objective, and one of the first ADP applications for the maintenance of a complex WSN. Additionally, our methodology incorporates a destruction spectrum reliability estimate which has received significant attention with respect to network reliability, but its value in a maintenance setting has not been widely explored. We conclude with a discussion on CBDPs in a range of test instances, and compare the performance to alternative deployment strategies.