# Privacy-Preserving Overgrid: Secure Data Collection for the Smart Grid
## 3 The Overgrid Concept
### The Distributed Demand Response Scheme  
In Overgrid, the nodes monitor a set of local and global parameters needed to implement the distributed DR. In particular, to follow the DSO requests, each node must: (i) receive the DSO request and contribute to spreading it to other nodes; (ii) estimate the total consumption of the network; and (iii) compute a reduction on the current power demand (potentially different for every node) to comply with the DSO request. All of these tasks can be executed by means of the gossiping protocol, which is used for disseminating the information about the DSO request and for implementing a distributed evaluation of the total power demand. Different approaches can be exploited for estimating the total power demand. We chose to exploit a distributed aggregation technique, called Flow Updating [14], which is very robust for error-prone overlay networks. The scheme is based on the concept of mass saving of the network: starting from the local variable available in each node (the _local_ power demand), the nodes iteratively update their estimates on the _total_ power demand by averaging the local value with their neighbors estimates. In more detail, Flow Updating uses the concept of _flow_ in graph theory and computes the  
Figure 1: Reference scenario for the Overgrid. average directly from the input (local) value and the contribution of the flows along graph edges to the neighbors:  
\[e_{i}=v_{i}-\sum_{j\in n_{i}}f_{ij}, \tag{1}\]  
where, at each node \(i\), the local estimate \(e_{i}\) of the average across the network is computed as the local node value \(v_{i}\) minus the sum of the \"flows\" \(f_{ij}\) from node \(i\) towards each neighbor \(j\). The algorithm works as follows: each node \(i\) stores the flow \(f_{ij}\) (initially set to 0) to each neighbor \(j\); the node \(i\) sends a message to node \(j\) containing information on flow \(f_{ij}\) and node \(j\) updates its own flow \(f_{ji}\) with \(-f_{ij}\), simply overwriting the previous value. The flows are simply the difference between the local and the neighbor estimates, as defined in [14]. By iterating the estimation process multiple times, each nodes' estimate converges towards the global average value of the network. Figure 2 shows an example with three nodes. The local estimate \(e\) is first initialized with the node's value \(v\) (6, 1, and 2, respectively), while flows are set to 0. Then, in the first round, each node sends messages to its neighboring nodes containing the flow towards it and the local estimate (e.g., A will send to B f = 0 and e = 6). At reception of the packets, the nodes update their estimate using Equation (1), i.e., comparing the internal value and the sum of the flows with the neighbors. The results obtained after round 1 are shown in the second row of the figure, where flows \"compensate\" the difference between estimates: the estimates in the center of the node circle are equal to the flow plus the estimate of the neighbor (at the previous step). The algorithm continues in the same way and converges after the second round. The fast convergence of this technique has been widely studied and demonstrated in [14; 15], comparing Flow Updating against other state-of-the-art methods based on Push-Sum Protocol, Push-Pull Gossiping, Distributed Random Grouping and Push-Synopses. The algorithm allows all nodes to converge to the same result (usually the average of a certain variable, but other functions are possible, e.g., counting and summing), independently of the network topology and dynamically adapting to network changes. In Overgrid, we use Flow Updating to estimate the average power \(p\) consumed by the nodes and the total number of nodes \(N\) currently in the network. For this second evaluation, one single node (e.g., the one that starts the Overgrid) is initialized with a local parameter equal to 1 and all the other nodes with a local parameter equal to 0: the number of nodes is given by the reciprocal of the resulting average value.