Battery-powered wireless sensor networks are prone to premature failures because some nodes deplete their batteries more rapidly than others due to workload variations, the many-to-one traffic pattern, and heterogeneous hardware. Most previous sensor network lifetime enhancement techniques focused on balancing the power distribution, assuming the usage of the identical battery. This paper proposes a novel fine-grained cost-constrained lifetime-aware battery allocation solution for sensor networks with arbitrary topologies and heterogeneous power distributions. Based on an energy–cost battery pack model and optimal node partitioning algorithm, a rapid battery pack selection heuristic is developed and its deviation from optimality is quantified. Furthermore, we investigate the impacts of the power variations on the lifetime extension by battery allocation. We prove a theorem to show that power variations of nodes are more likely to reduce the lifetime than to increase it. Experimental results indicate that the proposed technique achieves network lifetime improvements ranging from 4–13 over the uniform battery allocation, with no more than 10 battery pack levels and 2-5 orders of magnitudes speedup compared with a standard integer nonlinear program solver (INLP).