Wireless Sensor Networks (WSNs) composed of inexpensive devices allow the possibility of large deployments aimed at monitoring remote, or possibly hostile, areas. However, due to the unique traffic patterns exhibited by monitoring sensor networks, the lifetime of a large WSN is constrained by the burden placed on nodes near the sink node to forward additional traffic as more nodes are deployed. We discuss approaches for deploying a WSN that will maximize the lifetime of an initial deployment. We then consider cases where the mission lifetime is of a duration such that overdeploying an initial network to meet this mission criteria would become prohibitively expensive. We then propose a replenishment control framework where additional nodes are added to an initial deployment in consecutive batches in order to meet mission lifetimes while reducing cost. The control framework consists of a failure process model used to forecast sensor failures due to energy depletion, and a two-stage limited lookahead controller used to determine the number of nodes to be added to the network and the approximate locations of their deployment.