Cost-efficient approximation algorithm for aggregation points planning in smart grid communications

Smart grid is in need of an efficient communication network to guarantee reliable two-way data transmission between the control center and smart meters (SMs). In this work, a software-defined networking (SDN) based smart grid communication (SGC) scheme is introduced to fulfill the information transmission requirement, where the control plane is separated from the data plane to support diverse services flexibly in the smart grid. In such an SDN-based SGC system, to guarantee effective data processing and forwarding between the SMs and the control center, aggregation points (APs) are introduced. These APs should be deployed in an optimal way so as to cut down the total capital expenditure of the SGC system. The total cost generally includes the transmission cost between APs and the control center as well as APs and SMs. The construction and maintenance cost of the APs is also included. An approximation algorithm is introduced in this paper. The algorithm can deal with the formulated intractable APs planning task and produce performance-guaranteed solutions with reasonable complexity. Experiments indicate that the proposed algorithm works well for geographical areas with different densities of SMs. Our proposal yields cost-efficient APs deployment scheme and sheds insight into the reduction of the capital expenditure of the SGC system.