To facilitate more efficient control, massive amounts of sensors or measurement devices will be deployed in the Smart Grid. Data collection then becomes non-trivial. In this paper, we study the scenario where a data collector is responsible for collecting data from multiple measurement devices, but only some of them can communicate with the data collector directly. Others have to rely on other devices to relay the data. We first develop a communication protocol so that the data reported by each device is protected again honest-but-curious data collector and devices. To reduce the time to collect data from all devices within a certain security level, we formulate our approach as an integer linear programming problem. As the problem is NP-hard, obtaining the optimal solution in a large network is not very feasible. We thus develop an approximation algorithm to solve the problem. We test the performance of our algorithm using real topologies. The results show that our algorithm successfully identifies good solutions within reasonable amount of time.
展开▼