## 2 Related Works  
The network reliability problem is a classical reliability analysis problem [10] that can be classified as: _k-terminal_, _2-terminal_ or _all-terminal_. Suppose a network with \(N\) devices and a set of \(K\) devices (\(K\subset N\) and \(|K|<|N|\)). \(K\) is a set composed by a sink node and \(|K|-1\) field devices. Defining a sink device \(s\in K\), the _k-terminal_ problem is expressed as the probability that there is at least one path from \(s\) to each field device in \(K\). The _2-terminal_ problem is the case where \(|K|=2\), whereas the _all-terminal_ problem is the case where \(|K|=|N|\). These cases are known to be NP-hard problems, however several algorithms can be found for networks with limited size [11]. The network reliability problem has been widely studied for wired networks. For example, in [12] the author deals with the problem of measuring the reliability and availability of a wired network assuming hardware and software failures. The author gives an important insight about the state-space enumeration and the topology adaptation strategy when failures occur. The main difference between the reliability analysis of wired and wireless networks is related to the dynamics of the network. In a wireless networks, the dynamics of the network is greater since links fail more often and also due to the mobility of some of the devices. An early work about the reliability evaluation for a radio-broadcast network was conducted by [10]. In that work, the authors considered unreliable devices and reliable links and showed that the two-terminal reliability problem for radio broadcast networks is computationally difficult. In [13], the authors analyzed the reliability and the expected maximum delay for a distributed sensor network. The network is assumed to be dense and organized into clusters. The reliability was measured as the probability that there was at least one path between the sink device and a sensor node within a cluster. The authors assumed unreliable devices and reliable links. It was proved that the problem was, in general, NP-hard. However for a topology up to 40 devices the problem is still tractable. In [14], the network reliability was evaluated for mobile ad-hoc networks based on the 2-terminal problem. The authors assumed unreliable devices and dynamic network connectivity. The proposed algorithm, although not finding the minimal cut set for the network, can be extended for the type of static networks typically found in industrial applications. In [15], the authors analyzed the influence of adding redundant devices, in what concerns the reliability and availability of multi-hop wireless networks. This work provides an interesting discussion about the reliability and availability of a WSN, particularly if it is considered that a router node can be a redundant device. A tentative effort to create a methodology to evaluate the reliability of a WSN infrastructure was performed in [16]. The authors created a scheme based on reduced ordered binary decision diagrams (ROBDD) to model a cluster topology, where a reliability evaluation was also conducted. The authors do not considered multiple paths connecting a device to the sink. Thus, it is no longer possible to use self-healing routing protocols. Common-cause failures were considered, but the technique was focused in a single cluster. The methodology was applied only for a cluster topology with non-flexible failure conditions, and the criticality of devices was not determined. By introducing the concept of coverage-oriented reliability, the same authors extended the previous work [16] creating other mechanisms to evaluate the reliability of a WSN [17]. They assumed that the network fails if a specific point in the cluster is not covered by at least \(K\) devices. This give a more flexible way to configure failure conditions. However it is not possible to create two or more coverage subsets for the same cluster. Another coverage-oriented reliability mechanism was proposed in [18].