Modelling the Data Aggregator Positioning Problem in Smart Grids

Smart meters are responsible for keeping track of user energy consumption in a smart grid infrastructure. This data is periodically sent to one or more data aggregation points (DAPs), typically via wireless communication. Efficiently choosing the best positions for installing DAPs is an NP-Complete problem and therefore a difficult task, specially in big cities that may contain thousands of smart meters in a single neighborhood. Nevertheless, network planning has a major impact on network performance. This work proposes a reduction of the DAP positioning problem to a problem in the optimization area known as the Set Covering and a heuristic to solve it. This reduction considers a pre-processed subset of reliable links estimated based on the neighborhood characteristics, device´s communication technology, antenna heights and transmission rate. The obtained solution corresponds to the least number of DAPs, and its positions, necessary to cover an entire neighborhood. Our heuristic divides the problem in smaller independent sets that are solved separately and united afterwards. A post-optimization method is also applied in order to improve the heuristic´s solution. Heuristic and linear programming techniques are compared and results show that our heuristic is capable of obtaining solutions 0.05% close to the optimal while reducing both the execution time and the memory consumption by 2.27 and 8.14 times, respectively. Additionally, our heuristic was able to obtain results for large instances where the optimal solution failed due to insufficient memory.