The longevity of wireless sensor networks is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by further involving sink mobility. As most proposals give their evidence of lifetime improvement through either (small-scale) field tests or numerical simulations on rather arbitrary cases, a theoretical understanding of the reason for this improvement and the tractability of the joint optimization problem is still missing. In this paper, we build a unified framework for investigating the joint sink mobility and routing problem. We formally prove the NP-hardness of the problem. We also investigate the induced sub-problems. In particular, we develop an efficient interior point algorithm to solve the sub-problem involving a single sink, then we generalize this algorithm to approximate the original problem. Finally, we apply the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggest the desirable moving traces of a sink.