Asymptotically Optimal Distributed Gateway Load-Balancing for the Internet of Things
Ilai Bistritz, Nicholas Bambos · 2019
Consider a network of N sensors that collect data. Each sensor transmits this data to one out of G gateways. The gateways perform the preprocessing of the data and store it in the cloud. In order not to lose data, sensors need to route their packets to the gateway that has higher chances of successfully receiving them. However, this might overload some gateways that are the best gateway for many sensors, forcing them to drop packets. We design an asynchronous distributed algorithm where each sensor randomizes its destination, taking into account both the transmission success probabilities and the average input data rate of each gateway. Sensors estimate the transmission success probabilities online by sending pilot sequences and gateways broadcast the input data rates to all sensors. We show that our algorithm converges to a close to optimal solution. Specifically, when the number of sensors N approaches infinity, the ratio of the total throughput of our algorithm to the optimal throughput converges in probability to one.