Distributed Algorithm for Tree-Structured Data Aggregation Service Placement in Smart Grid

Smart grid, regarded as the next generation of power grid, uses two-way flows of electricity and information to create a widely distributed automated energy delivery network. One distinguishing aspect of smart grid communication networks is the large-scale deployment of smart meters and sensors. Thus, a large amount of data and information will be generated from metering, sensing, monitoring, etc. Data aggregation (integration or fusion) aims at the merging of data from disparate sources with differing conceptual, contextual, and typographical representations. In order to satisfy the requirement of different information services, the placement of data aggregation services in smart grid communication networks is a critical design issue. In this paper, we propose a minimum-cost-forwarding-based asynchronous distributed algorithm to find the optimal placement for the data aggregation service tree with optimal cost of in-network processing. It is shown that minimum-cost forwarding can dramatically reduce message overheads of the asynchronous algorithm. It is also shown that our algorithm has less message overheads than the synchronous algorithm (Sync) by both mathematical analysis and simulation-based evaluation. For a regular grid network and a complete binary service tree, the messages sent at each node are O(root NM) for our proposed algorithm and O(root NM log(2)M) for the Sync, where N is the number of network nodes and M is the number of data objects in the service tree.