## 3 Related Work
### Routing and Sink Placement Optimization  
The problem of optimal sink placement requires data about distance from any node to any potential sink. From the perspective of an individual node, the problem is a well-known single-source shortest path problem (SSSP), which has at least two traditional solutions, the Dijkstra's and the Bellman-Ford's solutions ([44]). Both solutions are centralized, which means that the complete network description has to be made available at a node, which performs computation. However, Bellman-Ford's solution can be changed to also work ina distributed environment, where each node is aware only of its direct neighborhood and information in it. This change is built into the Routing Information Protocol (RIP, [45; 46; 47]).  
In our scenario, initially all nodes are the same and only later are some of them defined as sinks or gateways. In other words, any node can also potentially be a sink. Consequently, we are not solving \(n\), where \(n\) is a number of nodes, unrelated SSSP problems, but one single all-pairs shortest path problem (APSP). The traditional algorithm solving this problem is a dynamic-programming centralized Floyd-Warshall algorithm ([44; 48]). Indeed, some attempts were made to make it parallel, and most of them applied techniques used in parallel matrix multiplication (cf. [49]).  
The network design of a Wireless Sensor Network (WSN) can play a critical role in the effectiveness of the proposed system. The two basic important performance indicators are the coverage and the connectivity. The objective of the coverage is to monitor a set of targets with a subset of sensor nodes, while, without connectivity, the sensor nodes cannot send the measured data to the sink nodes. The literature often combines these two questions in the case of centralized systems [50]. However, in the case of decentralized systems, the objectives can be separated on the network level; no specific approach is requested for coverage, and we need to concentrate on connectivity and communication.  
For both centralized and decentralized systems, the optimal placement of the sink nodes and the route optimization have a huge effect on the behavior of the system regarding the main design questions, including robustness [51], production cost [52], power consumption [53], etc. In the case of sink placement, the sensor network is given, and the goal is to identify the sink nodes in an optimal way.  
The mathematical formulation of the discussed issues leads back to two graph theoretical problems, the dominating set problem [54] and the facility location problem [55]. Because of the connectivity constraints on the level of the sink nodes, for both problems, the connected version is relevant: the connected dominating set and the connected facility location problems. In the case of a dominating set problem, subproblems, for example, distance dominating set [56] and k-hop connected dominating sets [57], are used in the area of Wireless Sensor Networks. In our case, the problem is very similar; however, our objective is to minimize the distances with a given fixed dominating set size. Regarding dominating sets, several different approaches can be found in the literature [58; 59; 60].  
The original facility location problem is about placing facilities based on geographical demands in an optimal way in order to minimize facility costs and transportation distances; however, it can also be used in sink placement. The difference in our case is that each node can also be a demand. A similar subproblem of the facility location is the rent or buy problem [61]. Regarding the facility location problem, different approaches can be found in the literature [62; 63; 64].