## 4 A Privacy-Aware and Secure Decentralized Framework
### Routing and Sink Placement Optimization  
Our integrated approach concerns the sink placement from the point of view of routing feasibility. Therefore, we first consider the sink placement problem in a formal way. Let \(G=(V,E)\) be an undirected connected unweighted graph representing the sensor network. It is important to note that the questions regarding sink placement can be generalized for weighted networks, where the edge weights represent the cost of communication between the nodes. Nevertheless, as the goal is to identify the sink nodes in the network, in the case of a decentralized system, the weights can be also dynamic as the communication cost between the sink nodes can be different from the cost between sensor nodes (or sensor-gateway communication). By the above fact, the generalization in the case of certain conditions is not straightforward. Our goal is to identify an optimal gateway placement in a graph \(G\) with respect to some cost function defined on the network. We assume that the number of \(k\) gateways is determined in advance. In different versions of the problem, because of the characteristics of the distributed systems, we need to ensure that all sink nodes (or a certain percentage of the sink nodes) have all the data measured by the sensors. On the theoretical level, we also assume that the system is operating by synchronous steps via data communication executed through edges connecting adjacent nodes. In order to define the sink placement problem, it is important to introduce different methods for the routing paths. We suppose that the routing from each sensor is arranged in a unique way. In practice, multipath routing is possible [70], but it is considered in a stochastic manner (one routing will be ending at a single gateway, but the choices during the routing can be stochastic). In the following, we will distinguish several versions of the problem. In certain cases, multipath routing has no influence on the model, while, in other cases, it could be handled by a stochastic model only with an expected value for each gateway having all the data. Thisstochastic feature would cause a problem in ensuring the required level of data sharing among the gateways; hence, in this study, we will consider deterministic models only. First, we suppose that the set \(S\) of \(k\) gateways is selected. A path \(p\) from a sensor node \(v\) to a gateway node \(w\) is called an _S-routing path_ if \(p\) contains a gateway node \(u\) such that \(p[v,u]\) is running outside from \(S\), while \(p[u,w]\) is running inside \(S\). In that case, \(p[v,u]\) is called the _external prefix_ of \(p\), and \(u\) is referred as the _S-entrance_ of \(p\). If \(p\) is equal to its external prefix, then it is called an _external \(S\)-routing path_. An _S-routing system_\(\mathcal{R}\) is a set of \(S\)-routing paths such that each sensor node \(v\) is the endpoint of a path in \(\mathcal{R}\) with all paths starting from \(v\) having the same external prefix. We will call \(\mathcal{R}\) a _weak \(S\)-routing system_ if each path of \(\mathcal{R}\) is external. If each sensor node is connected with each gateway node by a path of \(\mathcal{R}\), then \(\mathcal{R}\) is called a _strong \(S\)-routing system_. We will define problems for both weak and strong routing systems with appropriate cost functions. In each case, the cost \(c(S)\) of a gateway placement \(S\) is the cost of the weak (respectively, strong) \(S\)-routing system with minimum cost. In a _Type 1 problem_, a gateway set \(S\) is given and determines \(c(S)\) and the \(S\)-routing system with cost \(c(S)\), while in the _Type 2 problem_, the objective is to determine the feasible gateway set \(S\) with minimum cost \(c(S)\). Generally, _Type 1 problems_ can be handled with some standard path algorithms in polynomial time; on the other hand, _Type 2 problems_ are hard. The feasibility of the solutions can be defined in different ways.