Joint Optimization of Gateway Placement and Multi-hop Routing for the Internet of Things

The Internet of Things (IoT) has materialized smart homes, smart manufacturing, and smart cities for a better quality of life and new industrial opportunities. In an IoT network, a massive number of devices might lead to a serious problem of scalable performance. A possible approach for the scalability problem is to use the support of multi-hop routing for data communication and to group IoT devices into clusters. In this paper, we consider the joint optimization problem of gateway placement in a cluster and routing for an IoT network supporting multi-hop communication. We first formulate the problem as a Mixed Integer Linear Programming (MILP) model for obtaining the optimal solution. We then develop an approximation algorithm for addressing the problem in a large-scale IoT network. The evaluation results under a set of scenarios with various topologies and parameters show that the proposed algorithm achieves the results close to the optimal solution with a huge decrease in computation time. Our solution allows an IoT service provider to determine the optimal solution for the deployment of gateways and the optimal routing with a performance constraint in an IoT network.