One of the major issue in wireless sensor network in recent years is how to maximize the network life time and fault tolerant capabilities. Sensors used in wide range of applications such as area monitoring, environmental sensing, industrial monitoring, etc. tend to be heterogeneous and requires a fault tolerant network to minimize connectivity failure. In this paper, we address a suitable solution for maximizing lifetime by the optimal placement and usage of minimal relay nodes. Energy consumption intensity of relay nodes is used and the algorithm proposed ensures a fault tolerant network by developing a k-connected graph. Minimal numbers of relay and sensor nodes are used by scheduling them appropriately. A local search procedure is used for scheduling sensors and sinks separately to avoid redundancy and ensure optimal usage covering the entire target area without any coverage hole. Thus we minimize the overall deployment cost and enhance the network lifetime. © 2012 IEEE.