Network lifetime maximization by D&C approach in wireless sensor networks

The multi-source and single-sink (MSSS) topology is defined as the network topology in wireless sensor networks (WSNs), 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 WSNs. We note that the multiple-hop (MH) routing is globally optimal scheme to maximize the NL for the single-source and single-sink (SSSS) topology in WSNs. However, since the scheme will cause the source nearest to the sink to run out of its energy earliest in the MSSS case, the results for network lifetime maximization (NLM) in the SSSS topology cannot be directly applied to the MSSS case. 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. When the integer constraints are relaxed to be real values, it becomes a convex problem. First of all, we employ the Karush-Kuhn-Tucker (KKT) optimality conditions to derive analytical expressions of the globally optimal NL for a linear SSSS topology. Then a decomposition and combination (D&C) approach is proposed to obtain suboptimal solutions. As a result, an analytical expression of the suboptimal NL is derived for WSNs with a linear MSSS topology. We also derive the globally optimal NL in the planar SSSS network. The analytical results can be applied to obtain the results in the Planar MSSS case based on the D&C idea. To validate the analysis, numerical results show that the upper-bounds of the NL obtained by our proposed optimization models are tight.