Lexicographically Optimal Routing for Wireless Sensor Networks With Multiple Sinks

• Published in: IEEE transactions on vehicular technology 2009-03, Vol.58 (3), p.1490-1500
• Main Authors: Shah-Mansouri, V., Mohsenian-Rad, A.-H., Wong, V.W.S.
• Format: Article
• Language: English
• Subjects: Acoustic sensors; Algorithms; Applied sciences; Batteries; Commodities; Computer networks; Connection and protection apparatus; Direct energy conversion and energy accumulation; Electrical engineering. Electrical power engineering; Electrical power engineering; Electrochemical conversion: primary and secondary batteries, fuel cells; Energy consumption; Exact sciences and technology; Humidity; Iterative algorithms; Lexicographical optimality; Lifetime; multiple sinks; Network topology; Networks; Optimization; Relays; Routing; Routing (telecommunications); routing flow; Sensors; Services and terminals of telecommunications; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Telemetry. Remote supervision. Telewarning. Remote control; Temperature sensors; Transmission and modulation (techniques and equipments); Wireless sensor networks; wireless sensor networks (WSNs)
• ISSN: 0018-9545; 1939-9359
• DOI: 10.1109/TVT.2008.928898

In wireless sensor networks (WSNs), the field information (e.g., temperature, humidity, airflow) is acquired via several battery-equipped wireless sensors and is relayed toward a sink node. As the size of the WSNs increases, it becomes inefficient (in terms of power consumption) when gathering all information in a single sink. To tackle this problem, one can increase the number of sinks. The set of sensor nodes that are sending data to sink k is called commodity k . In this paper, we formulate the lexicographically optimal commodity lifetime (LOCL) routing problem. A stepwise centralized algorithm called the LOCL algorithm is proposed, which can obtain the optimal routing solution and lead to lexicographical fairness among commodity lifetimes. We then show that, under certain assumptions, the lexicographical optimality among commodity lifetimes can be achieved by providing lexicographical optimality among node lifetimes. This motivates us to propose our second algorithm, which is called the lexicographically optimal node lifetime (LONL) algorithm, which is suitable for practical implementation. Simulation results show that our proposed LOCL and LONL algorithms increase the normalized commodity and node lifetimes compared with the maximum lifetime with multiple sinks (MLMS) and lexicographical max-min fair (LMM) routing algorithms.