Network Lifetime Optimization by Duality Approach for Multi-Source and Single-Sink Topology in Wireless Sensor Networks

The multi-source and single-sink (MSSS) topology, in wireless sensor networks, is defined as the network topology, where all of nodes can gather, receive and transmit data to the sink. We consider the problem of finding the joint optimal scheme with consideration of physical, medium access control (MAC), and network layers to maximize the network lifetime (NL) for the MSSS topology in the energy-constrained wireless sensor networks (WSNs). The optimization problem, when the link access is an interference-free time division multiple access (TDMA) scheme, can be formulated as a mixed integer-convex programming and relaxed to the convex programming. According to the transcendental equations in programming model, we take two rather different approaches to maximize the NL in such network. First, based on the result of the SSSS network, we decompose the MSSS problem into the various SSSS issues. Another approach is to utilize the Karush-Kuhn-Tucker (KKT) optimization conditions to analytically solve this convex problem. Analytical expression of the optimal NL is a function of the initial energy and quantities of data held by the sources, taking the influence of data rates, link access and routing method into account. Although some dual gaps exist, the analytical result agrees well with numerical result of optimization solver, and can be applied to algorithms in WSNs aiming at maximizing NL.