Multiple Sink Positioning and Routing to Maximize the Lifetime of Sensor Networks

Haeyong KIM  Taekyoung KWON  Pyeongsoo MAH  

IEICE TRANSACTIONS on Communications   Vol.E91-B   No.11   pp.3499-3506
Publication Date: 2008/11/01
Online ISSN: 1745-1345
DOI: 10.1093/ietcom/e91-b.11.3499
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Emerging Technologies for Practical Ubiquitous and Sensor Networks)
multiple sinks,  lifetime,  sensor network,  

Full Text: PDF>>
Buy this Article

In wireless sensor networks, the sensor nodes collect data, which are routed to a sink node. Most of the existing proposals address the routing problem to maximize network lifetime in the case of a single sink node. In this paper, we extend this problem into the case of multiple sink nodes. To maximize network lifetime, we consider the two problems: (i) how to position multiple sink nodes in the area, and (ii) how to route traffic flows from sensor nodes to sink nodes. In this paper, the solutions to these problems are formulated into a Mixed Integer Linear Programming (MILP) model. However, it is computationally difficult to solve the MILP formulation as the size of sensor network grows because MILP is NP-hard. Thus, we propose a heuristic algorithm, which produces a solution in polynomial time. From our experiments, we found out that the proposed heuristic algorithm provides a near-optimal solution for maximizing network lifetime in dense sensor networks.