Network lifetime (NL) maximization techniques have attracted a lot of research attention owing to their importance for extending the duration of the operations in the battery-constrained wireless sensor networks (WSNs). In this paper, we consider a two-stage NL maximization technique conceived for a fully-connected WSN, where the NL is strictly dependent on the source node's (SN) battery level, since we can transmit information generated at the SN to the destination node (DN) via alternative routes, each having a specific route lifetime (RL) value. During the first stage, the RL of the alternative routes spanning from the SN to the DN is evaluated, where the RL is defined as the earliest time, at which a sensor node lying in the route fully drains its battery charge. The second stage involves the summation of these RL values, until the SN's battery is fully depleted, which constitutes the lifetime of the WSN considered. Each alternative route is evaluated using cross-layer optimization of the power allocation, scheduling and routing operations for the sake of NL maximization for a predetermined per-link target signal-to-interference-plus-noise ratio values. Therefore, we propose the optimal but excessive-complexity algorithm, namely, the exhaustive search algorithm (ESA) and a near-optimal single objective genetic algorithm (SOGA) exhibiting a reduced complexity in a fully connected WSN. We demonstrate that in a high-complexity WSN, the SOGA is capable of approaching the ESA's NL within a tiny margin of 3.02% at a 2.56 times reduced complexity. We also show that our NL maximization approach is powerful in terms of prolonging the NL while striking a tradeoff between the NL and the quality of service requirements.