Lexicographically Optimal Routing for Wireless Sensor Networks With Multiple Sinks

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.