Design of Fault-tolerant Structures for Underwater Sensor Networks Based on Markov Chains

Ongoing research in underwater sensor networks focuses on the development of energy-efficient communication protocols tailored to the challenges of underwater acoustic channels [21, 22]. Researchers are exploring adaptive protocols that can effectively navigate variable propagation delays and limited bandwidth, ensuring optimal data transmission and prolonged network operation.

Advancements in accurate localization techniques for underwater sensor nodes are very important [23,24]. Precise localization is essential for oceanographic studies, environmental monitoring, and navigation of autonomous underwater vehicles. Researchers are developing novel methods to enhance the accuracy of node positioning in dynamic underwater environments.

The improvement of acoustic communication in USNs is one of the critical areas of exploration [25]. Research efforts are directed toward enhancing the reliability, data rates, and range of acoustic communication. This includes investigating innovative modulation techniques and signal processing algorithms to overcome the challenges posed by underwater acoustic channels.

Research in sensing technology for USNs involves the development of specialized and accurate sensors [26, 27]. This includes advancements in chemical, biological, and optical sensors to expand the data collection capabilities of USNs. Integrating diverse sensors contributes to a more comprehensive understanding of underwater environments.

Research is dedicated to creating adaptive and cognitive sensor networks that can autonomously adjust to changing underwater conditions [28,29]. This involves exploring self-configuring, self-optimizing, and learningbased approaches, such as cognitive radio techniques, to dynamically adapt to spectrum availability and mitigate interference.

Ensuring the security and privacy of data in USNs is an equally important task when developing these networks. Scientists are designing secure communication protocols and encryption techniques to protect data in transit, addressing the unique challenges posed by the underwater environment [30, 31].

Bio-inspired algorithms and strategies are being researched to optimize USN functionality [32,33]. This includes the use of evolutionary and swarm intelligence algorithms to optimize structures, energy consumption, routing, node aggregation, power control, scheduling of sensor activities, functionality, and more.

Bio-inspired intelligent approaches [34–36], soft computing [37–39] and different machine learning algorithms [40–42] have proven themselves to be very effective tools for solving diverse problems in various fields.

Along with the areas discussed, even more significant is research aimed at increasing the fault tolerance, reliability and survivability of underwater sensor networks [43, 44]. The importance of fault tolerance in underwater sensor networks cannot be overstated, as these networks operate in challenging and dynamic aquatic environments where sensor nodes are susceptible to various forms of failure. Fault tolerance is crucial for ensuring the reliability and continuous operation of USNs, where sensor nodes may experience malfunctions due to factors such as harsh underwater conditions, hardware failures, or energy depletion. Given the remote and inaccessible nature of many underwater deployment sites, timely maintenance and node replacement are often impractical. Fault-tolerant mechanisms allow USNs to detect, isolate, and adapt to faults, ensuring that the network can continue its mission-critical functions even in the presence of node failures. This resilience is vital for applications ranging from environmental monitoring and marine research to underwater infrastructure maintenance and defense operations, where uninterrupted and accurate data collection is paramount. Fault-tolerant USNs contribute to the overall robustness and effectiveness of underwater exploration and monitoring, providing a foundation for sustained and reliable performance in challenging underwater environments.

The quest for enhancing the fault tolerance of underwater sensor networks has spurred a prolific body of research, and a comprehensive review of the methods reveals a dynamic landscape of innovative approaches. Several key strategies have been explored to fortify USNs against the challenges posed by the harsh underwater environment [45,46]. The utilization of advanced error detection and correction mechanisms, including error-correcting codes and checksums, has shown promise in mitigating the impact of data transmission errors [20, 47]. Additionally, adaptive routing protocols dynamically reroute data paths in response to changing network conditions, offering a proactive approach to fault tolerance [48,49]. Machine learning algorithms are increasingly employed for anomaly detection, allowing USNs to identify and isolate faulty nodes based on deviations from normal behavior [33,50,51]. Energy-aware strategies, focusing on efficient power management and the utilization of energy harvesting technologies, contribute not only to prolonging network lifespan but also to bolstering fault tolerance [52]. Moreover, redundancybased methods, such as node duplication and data replication, have been prominent, providing resilience by ensuring that critical functions persist even in the face of node failures [19,53,54].

In addition, Markov chains are quite effectively used to assess the obtained fault tolerance and analyze the reliability of the generated architectures of various sensor networks [55–57].

Despite the constant increasing of hardware reliability, efficiency of routing and data processing, redundancy of sensors, etc., the challenge of creating an architecture guaranteed to provide the required number of cycles before failure for each specific case with the given network parameters remains unsolved.

Hence, it is advisable to develop a method of designing fault-tolerant structures for underwater sensor networks using Markov chains mathematical apparatus. This approach will ensure the creation of underwater sensor networks that exhibit the necessary number of operation cycles before encountering failure for the given USN parameters. Therefore, the main aim of this paper is to develop and investigate a design method of fault-tolerant structures for underwater sensor networks utilizing the principles of Markov chains.

The main contributions of the authors are as follows:

creation of the step-by-step method for designing the fault-tolerant structures of the underwater sensor networks based on Markov chains;

Specialized underwater sensor networks are used to collect various types of information about the state of the underwater environment, transmit this information, and further process it. The primary collection of information is carried out from certain information sources using specialized sensors installed in the underwater environment. In turn, the number of data sources and, accordingly, sensors is equal to X₀. Signals from these sensors are transmitted to the main information processing unit using data transmission channels.

Since the number of sensors (initial information sources) is quite large (can number several hundreds or thousands), the transfer of data directly from them to the main information processing node through communication channels is quite complicated. This is explained by the fact that the sensors will need to have a sufficiently high signal transmission power and, accordingly, high energy consumption to ensure the transmission of a large amount of information over long distances.

And the main information processing unit will have very high complexity and cost, as well as fairly low reliability, which, of course, will significantly increase the cost and reduce the reliability of the entire system. Therefore, in order to reduce the overall cost and increase the reliability of the USN, it is advisable to form its structure according to a hierarchical principle. To do this, it is advisable to use intermediate data collection nodes that will perform functions of signal grouping with certain information processing. As a result of such processing, these nodes will transmit further smaller amounts of information while preserving all valuable data. Thus, intermediate nodes of the 1st level of the hierarchy will group and process signals from sensors and send them to nodes of the 2nd level of the hierarchy, and so on to the main node of the system.

In this paper we consider the tree-like or pyramidal architecture that is a specific type of hierarchical architecture. In this structure, nodes are organized in a tree-like fashion, with multiple levels and the main sink node at the root. Each level consists of nodes that communicate with nodes in the level above them, ultimately reaching the sink node. The given architecture is highly effective and can provide reduced energy consumption and improved scalability as well as adaptation to varying node densities. In particular, by organizing nodes hierarchically, the number of hops required for data transmission to the sink node is minimized. This can lead to significant energy savings, especially for nodes located deeper in the water. Moreover, this architecture can be wellsuited for larger networks, as it provides a structured way to manage communication and data flow. Finally, in environments with varying node densities, the treelike structure allows for more efficient data collection and transmission.

The generalized functional structure of the hierarchical underwater sensor network is presented in Fig. 1.

Figure 1.

Generalized functional structure of the hierarchical underwater sensor network.

In this system, the lowest (zero) level is the level of underwater sensors, which are used to measure various parameters (pressure, temperature, salinity, pH, current speed, etc.). Typically, these sensors have built-in power sources and contactlessly transmit measured information to higher levels using acoustic signals. The possible operating time of these sensors depends on the capacity of the power source, the required frequency of measurement and information transmission, as well as the signal transmission power to ensure data transfer over specified distances. In some cases, sensors can be powered by wire, for example, in the presence of nearby sources of alternative energy (wind, wave, etc.). In turn, the data transmission can also be carried out in the same way, but wired connections significantly complicate the initial deployment and further maintenance of the network in the event of a breakdown.

The next (first) level of the network is implemented using unmanned underwater vehicles (UUVs), which receive information from sensors, process it in a certain way and transmit it further to higher levels of the hierarchy. Moreover, UUVs also transmit data using acoustic signals; however, due to some filtering, processing and structuring, smaller volumes of higher quality information are transmitted.

This makes it possible to significantly save data transmission energy without overloading the network with redundant unnecessary information. These underwater vehicles must be replaced periodically to recharge power supplies and perform maintenance. At higher levels of the USN’s hierarchy there are surface buoys that receive acoustic signals underwater from the UUVs and, using radio signals, transmit information above the water to terrestrial communication nodes. These buoys with radio and acoustic communication can have either autonomous power sources or be powered by nearby alternative energy sources.

In turn, the terrestrial communication nodes transmit information using radio signals or by wires. As a result, all data flows through the main node at the highest level of the hierarchy to the terrestrial monitoring station, where the information is analyzed on computers and further stored on servers. In addition, the information is also processed and structured on the buoys and terrestrial communication nodes, as on the UUVs. The number of hierarchy levels implemented on UUVs, buoys and terrestrial communication nodes may vary depending on specific conditions, the selected network topology, the required data transmission distance, the distance of data collection from the shore and the monitoring station and many other factors. Herewith, the fewer the hierarchy levels and, accordingly, data transmission stages, the more powerful the signal transmitters, power supplies and computing capabilities of nodes must be to simultaneously process a large amount of information and send it over long distances. This will substantially affect the overall cost of the network and the significance of the loss of its individual elements. On the other hand, with a smaller number of sequentially connected levels, reliability and fault tolerance will increase in a certain way. This paper does not consider cost optimization of the network structure. However, it should be borne in mind that using a large number of simple and cheap elements will cost less than a smaller number of expensive ones, since the cost of nodes increases exponentially with the increase in the number of input signals and the required data transmission range. This pattern is even more pronounced when it is necessary to reserve elements of certain levels of the hierarchy.

When creating an USN, its structure can be denoted by the vector X with dimension i_max + 1, which corresponds to the total (pre-selected) number of hierarchy levels and a zero level. Each variable of this vector X_i(i = 0, 1,…, i_max) corresponds to the selected number of nodes on the i-th level of the hierarchy. In turn, the number of nodes X_i at the i-th level of the hierarchy can be chosen according to the condition (1), 1Xi≤ floor (Xi−12), since each node of a given hierarchy level (except zero) must have at least 2 inputs (n_i ≥ 2, i = 1,…, i_max), so that the dimension of the levels decreases as information moves to the upper level. At the same time, X_{i max} = 1, since there is only one main node of the system at the last (highest) level of the hierarchy. Also, at the penultimate level of the hierarchy (i_max – 1), the number of nodes must be at least 2 (X_{i max} - 1 ≥ 2).

If X_i nodes are selected at each i-th level of the structure hierarchy, the number of inputs n_i for each node can be calculated based on the dependence (2) 2ni=Xi−1Xi.

If the calculated value of n_i is an integer, then all nodes at a given level of the hierarchy will have the given number of inputs. Otherwise, the number of node inputs is calculated as follows. At a given level of hierarchy there will be nodes with the number of inputs equal to the largest integer less than n_i, and with the number of inputs equal to the smallest integer greater than n_i. In this case, the number of nodes with the number of inputs equal to the smallest integer greater than n_i, as a percentage of the total number of nodes ofa given hierarchy level, will be equal to the fractional part of the calculated number n_i.

For example, the structure of the USN for the number of initial sensors (information sources) X₀ = 13 and three hierarchy levels (i_max = 3) can be schematically depicted in Fig. 2.

Figure 2.

Schematic hierarchical structure of the USN with X₀ = 13 and i_max = 3.

The nodes of the system are sequentially connected by communication channels, starting from the 1st level of the hierarchy to the last i_max. At the same time, nodes of the level (i – 1) are connected only to nodes of the level i, taking into account the number of inputs of the latter. The output of each node of the level (i – 1) can be connected to only one input of the node of the level i.

For a given network, the vector X will have the form 3X={13,5,2,1}.

Since the main components of the network operate in harsh underwater environments, where various types of malfunctions and failures occur quite often, the most important task is providing the specified fault-tolerant qualities to extend the USN life and maximize the effective realization of its internal potential. To ensure the required fault tolerance margin of an underwater sensor network, it is necessary to synthesize its hierarchical structure using the advanced method proposed by the authors, the main aspects of which are discussed in the next subsection.

Fault tolerance of an underwater sensor network is the ability to maintain its full or partial functionality after the failure of one or more of its components [56,58]. Fault tolerance is determined by the number of single failures of the component elements (malfunctions) of the system, after the occurrence of which the operability of the system as a whole is still maintained. The basic level of fault tolerance implies protection against failure of any element. Therefore, the main way to increase fault tolerance is redundancy. This approach has been successfully used to manage fault tolerance and survivability both in USNs and in a number of other critical infrastructure facilities [59,60]. Redundancy is most effectively implemented in hardware, through reservation. In this case, failures due to wear and aging are not considered, since for the main elements of the system, the energy reserve of the power sources is used up much earlier than the intended operating life. The main reason for system failure before the power supply runs out is random failures caused by harsh network operating environment.

To determine the fault tolerance of a USN with a branched hierarchical structure, it is necessary to calculate the maximum number of cycles of its operation N_max before failure occurs in conditions of periodic malfunctions of its individual elements. If it is necessary to determine the maximum operating time of the system before failure, the operating cycles can be quite easily translated into time, knowing the duration of one cycle. By the USN failure we mean the inability to transmit a certain number of signals (a certain percentage of information) through its nodes and channels. For example, a system can be considered operational as long as it transmits signals from more than 50% of the initial measurement sensors. If information is transmitted from no more than 50% or less of the sensors, then it can be considered that a system failure has occurred. Since the levels of the USN hierarchy are connected to each other in series, it is obvious that the failure of the entire system can occur as a result of the failure of at least one of its hierarchy levels. In turn, this can happen when 50% of the nodes or channels (or nodes and channels) of a given hierarchy level are down or damaged due to disturbances.

Failure or damage of any one node (or channel) of any hierarchy level will be called a malfunction in the operation of this hierarchy level. Thus, a failure of a certain hierarchy level (that corresponds to the failure of the whole system) can occur as a result of sequential malfunctions, the number of which is equal to the (prespecified) critical number of nodes X_ic of a given i-th hierarchy level (i = 0, 1,…,i_max). For example, when selecting a critical number of 50% of signals from all sensors, for a level with 10 nodes, the failure will be considered the malfunctions of5 or more nodes (X_ic ≥ 0.5 X_i ≥ 5).

The probability of a malfunction occurring at each specific level of the USN_pMi can be preset or calculated based on the average value of the number of operation cycles between single malfunctions N_Mi (determined experimentally) in accordance with the expression (4) 4pMi=1NMi.

In turn, the probability p_Mi can differ significantly at different hierarchical levels of the USN, which is caused by different properties of the elements and different environmental conditions in which these elements are located and operate. For instance, the lowest (zero) level of the hierarchy, which includes sensors for the initial measurement of quantities, has the highest probability of a malfunction occurring, since, due to the harsh conditions of being in the underwater environment, its sensors can quite often fail due to mechanical damage or loss connections with nodes of higher levels of the system. The levels with underwater vehicles and buoys are also located in aggressive underwater and surface environments, respectively; however, they have lower probability values p_Mi due to their higher inherent reliability.

As for the levels with the terrestrial communication nodes including the highest level with the main node, their probability values p_Mi are much lower, since they are on the ground and have a fairly high reliability.

To calculate the probability of failure p_Fi of the i-th level of the USN, it is advisable to use a simple homogeneous Markov chain, the structure of which is shown in Fig. 3 [61].

Figure 3.

A homogeneous Markov chain for calculating the probability of failure of the i-th level of the USN.

The state S₀ corresponds to the absence of a malfunction when performing the next operating cycle. If the first malfunction (a failure of one node) occurs during the operation of the system at the i-th level of the hierarchy, then the transition to the state S₁ is performed. The probability of this transition is p_Mi. On the next cycle, with the probability p_Mi, a second malfunction (which corresponds to the inoperative state of two nodes of this level) may occur at this level of the hierarchy (transition to the state S₂) or with the probability 1 – p_Mi no malfunction will occur, which will correspond to the preservation of the state S₁. In turn, returning from the state S₁ to the previous state S₀ is impossible. A failure of the whole level corresponds to the S_Xic state, into which the system will fall after X_ic malfunctions occur at the i-th hierarchy level (i.e., a critical number of nodes X_ic fail sequentially for a given hierarchy level). Transitions from the state S_Xic to the other states are not possible. For the calculation, we assume that the system moves from the state S_Xic to this state with the probability 1.

Herewith, for the last (highest) level of the USN’s hierarchy, on which there is a single main node (X_i = 1), the Markov chain will have the form presented in Fig. 4.

Figure 4.

A homogeneous Markov chain for calculating the probability of failure of the last (highest) level of the USN.

To describe the probabilities of transitions from state to state at the i-th level of the hierarchy (i = 0, 1,…, i_max), it is advisable to use matrices of transition probabilities R_Xic. As an example, for hierarchy levels with a critical number of nodes X_ic = 2, X_ic = 3, X_ic = 4, X_ic = 5, these matrices have the form: 5R2=| 1−pMipMi001−pMipMi001 |; 6R3=| 1−pMipMi0001−pMipMi0001−pMipMi0001 |; 7R4=| 1−pMipMi00001−pMipMi00001−pMipMi00001−pMipMi00001 |; 8R5=| 1−pMipMi000001−pMipMi000001−pMipMi000001−pMipMi000001−pMipMi000001 |

The probability of failure p_Fi of the i-th level of the USN is the probability of transition from the initial state S₀ to the state S_Xic, i.e. is equal to the conditional probability located in the last column of the first row (upper right corner of the matrix of transition probabilities) [61]. At the beginning of the operation of the USN (at the “zero” operating cycle), this probability is zero.

Analyzing expressions (5)-(8) it can be concluded that for a certain level of the hierarchy, the matrix of transition probabilities will have an order of one greater than the critical number of nodes in a given hierarchy level (X_ic + 1). Thus, for the last (highest) level of the USN with a single main node (X_imax = 1), the matrix of transition probabilities will be of 2nd order: 9R1=| 1−pMi max pMimax 01 |.

In this case, for the matrix (9) already at the beginning of operation p_Fimax = p_Mimax.

In turn, the probability of failure of the entire system P_{F Σ} can be calculated based on the expression (10), since all the levels of the hierarchy are connected in series. 10PFL=1−(1−pF0)·(1−pF1)·(1−pF2)×…·(1−pFi)·…·(1−pFimax ), where p_Fi is the probability of failure of the i-th level of the USN; p_{Fi max} is the probability of failure of the last (highest) level of the USN.

To find the probability of failure of the i-th level of the system (i = 0, 1,…, i_max) on the N-th cycle, it is necessary to raise its matrix of transition probabilities to the N-th integer power: RXicN .

Thus, to calculate the maximum number of operating cycles N_{i max} of the i-th level of the USN before failure occurs, it is necessary to determine the power to which the matrix of transition probabilities of a given level must be raised so that the probability in the last column of the first row of the matrix is equal to one (p_Fi = 1). To reduce calculations, instead of one in the upper right corner of the matrix, we can use a probability of 0.999 (p_Fi ≥ 0.999). For example, if the probability of a malfunction at the i-th level of the hierarchy is p_Mi = 0.7, then the value of the maximum number of operation cycles of this level for the given matrices R₁, R₂, R₃, R₄, R₅, respectively, will be: N_max = 6, N_max = 9, N_max = 11, N_max = 13, N_max = 15.

In turn, to calculate the maximum number of cycles of operation before failure of the entire system_Σmax, it is necessary to determine the power to which the matrices of transition probabilities of all levels must be raised so that the probability of failure of the entire system is greater than or equal to 0.999 (P_FΣ ≥ 0.999).

Analyzing the obtained values N_{i max}, it can be argued that for the same probability value p_Mi, the greater the critical number of nodes X_ic at the i-th level of the hierarchy, the greater the value of the maximum number of cycles before failure N_{i max} of this level. In addition, increasing the number of levels of the hierarchy i_max will significantly increase the probability of failure of the entire system P_FΣ.

Thus, to increase the number of cycles to failure, two main ways can be distinguished: 1) increasing the critical number of nodes at each specific level of the hierarchy; 2) reducing the number of levels of the system hierarchy.

Herewith, the second way in some cases may not give the desired results due to the presence of initial restrictions on the distance of signal transmission and on the types of network’s elements used. For example, if there is only a certain type of elements (sensors, UUVs, buoys and other nodes) and a given distance for transmitting information to a terrestrial monitoring station, then to create a network it will be necessary to form a given number of hierarchy levels, which cannot be reduced.

Therefore, to ensure a given number of the USN operation cycles (or operating time) under different initial conditions, the most effective way is to increase the critical number of nodes at specific network’s levels through redundancy.

Taking into account the expression (10), the probability of failure of the entire system P_FΣ is always greater than the probability of failure of each individual level p_Fi, and, accordingly, the level, for which this value is the greatest. Therefore, to increase the number of operation cycles (or operating time) before failure of the entire system, it is first necessary to reserve elements of the level with the smallest value of this quantity.

At the same time, since it is unknown which node will fail, in order to ensure a stable increase in the critical number of nodes at a certain level, it is necessary to reserve all nodes at this level. For example, if there are 10 nodes at a certain USN’s level and the critical number of nodes is 5 (when choosing 50%), then for redundancy at the initial stage it is necessary to duplicate all 10 nodes. Then, there will already be 20 nodes at this level, and the critical number of nodes is guaranteed to increase to 10. If this number will be still not enough to ensure the given number of operation cycles, then it is necessary to continue to sequentially reserve nodes, with step by step increasing their number to 30, 40, and so on.

Next, based on the above principles, we formulate the method for development of the fault-tolerant structures for USNs.

The authors’ proposed design method of faulttolerant structures for USNs consists of the following sequential steps.

Step 12

Completion of the process of designing fault-tolerant structure of the USN. After this, the implementation and configuration of the USN with designed structure can be carried out.

The block diagram of the proposed designing method of fault-tolerant structures for USNs is shown in Fig. 5.

Figure 5.

A block diagram of the designing method of fault-tolerant structures for USNs.

To study the effectiveness of the proposed method, the next section presents the example of designing the fault-tolerant structure of the specific underwater sensor network.