Clustering nodes in Internet of Things environments with time and energy constraints: a multiobjective optimization formulation for the gateway placement problem in LoRaWAN ® networks

Abstract

The Internet of Things (IoT) has become the leading technology to support smart environments, with growing set of applications being devised to provide intelligence in different scenarios. Precision agriculture, Industry 4.0, sustainable smart cities, and smart homes are just some of the more active areas in which the IoT is gaining space. The use of hierarchical networks in which the last mile is used to interconnect end-devices with gateways in charge of routing messages to and from the Internet is the most accepted network architecture. When messages have time constraints and nodes operate on batteries, the network organization should consider the cost of gateways, the total energy demand, the bandwidth utilization, and the satisfaction of time constraints. Planning the operation of such a network gives rise to a multi-objective optimization problem, which is considered in this work. This paper presents three main contributions: (i) a proof of the NP-hardness of this problem, (ii) an integer linear programming formulation for this problem, and (iii) a greedy heuristic and a multi-objective genetic framework for this problem. An extensive computational experimentation is presented, including an analysis of the Pareto front, a comparison between the proposed methods, and a performance evaluation of the greedy heuristic for large instances. According to our computational experiments, the greedy heuristic is able to approximate the Pareto front with small running times and memory footprints.