Despite the disparity in the objectives of sensor applications, the main task of sensor networks is to sense and collect data from a target domain, process the collected data, and transmit the information back to the base station. Achieving this task efficiently requires the development of an energy-efficient routing protocol to set up paths between sensor nodes and the base station. The path selection must be such that the lifetime of the network is maximized. The definition of this metric is determined by the type of the provided service. Using several definitions of lifetime and a common evaluation framework, the lifetime of some representative flat and hierarchical sensor network routing protocols has been analyzed, namely: DIRECT, FLOODING, GOSSIPING, LEACH, and HEED. Extensive simulations have been carried out yielding a detailed analysis of the spatial-temporal distribution of lifetimes. Through this study, a new technique aimed at providing a good spatial-temporal distribution of lifetime is proposed. The resulting EHEED protocol is compared to others. Experimental results show that EHEED can extend remarkably the network lifetime and can be very effective for long-lived sensor network.