1 Introduction

Wireless sensor networks (WSNs) are applied to sense and monitor an environment. Sensor nodes are small devices with the ability to monitor an environment for various objectives. The transmission radius of sensor nodes is restricted, and therefore, they should be connected over a multi-hop network [1]. The inherent limitations of sensor nodes prevent WSNs functionality and this necessitates application of, therefore, topology management techniques therein. Several topology management techniques have been proposed for tolerating node failures in WSNs like node discovery, sleep scheduling, clustering, power saving, multi-path routing, etc. [2]. Multi-path routing can be facilitated through the relay node placement in WSNs.

In this paper, the proposed approach is based on the relay node placement to provide multi-path routing and fault tolerance with higher network connectivity in heterogeneous WSNs. A WSN can tolerate the failure of up to k-1 nodes if and only if it contains at least k internally disjoint paths between every sensor pair. The relay nodes would applied to assure that there exist at least k vertex-disjoint paths between all sensor node pairs because the initial WSN may not contain enough paths. The relay nodes only receive/forward data from/to other nodes and cannot sense the environment. The problem of finding the minimum relay node count to establish k vertex-disjoint paths is a nondeterministic polynomial (NP)-hard problem [3].

This paper addresses relay node placement in the context of heterogeneous WSNs in order to reach more practical results. In this type of WSN, the sensor nodes have different transmission radii, while all of the relay nodes use an identical transmission radius [4]. The focus of this study is on creating a fault-tolerant heterogeneous WSN for suffering the failure of k-1 sensor nodes by placing the least relay node count. To reach this aim a method (KCN) is proposed to establish k vertex-disjoint paths between all sensor node pairs.

The proposed method consists of two phases. The first phase is creating a k-vertex connected graph with the minimum length of edges. In [5] Chartrand et al. noted that “let G be a k-connected graph and S be any set of k vertices. If a graph H is obtained from G by adding a new vertex w and joining w to the vertices of S, then H is also k-connected”. Algorithm 1 is developed to create a k-vertex connected graph with the minimum length of edges based on this lemma. The second phase is reducing the required relay node count for creating the k-connected network. In this phase, two algorithms are developed to implement the edges that are obtained in phase 1 with the least relay node count. Algorithm 2 determines the candidate relay nodes and their locations for implementing each edge. Algorithm 3 decides on whether to disregard a candidate relay node based on some heuristics. During making the decision on each candidate relay node, the possibility of playing its role through the sensor nodes and the previous placed relay nodes is investigated. The WSN remains k-connected, even if the algorithm decides to disregard all candidate relay nodes.

The contributions of this paper are summarized as follows:

  • According to the mentioned lemma in [5], Algorithm 1 is presented to create a minimum k-vertex connected graph.

  • An interesting technique is developed to reduce the time complexity of Algorithm 1 from O(n3) to O(n2).

  • Algorithm 2 is developed to locate a set of candidate relay nodes for implementing each edge in the k-vertex connected graph.

  • Lemmas 1 and 2 and Sub-lemma 1.1 with their proofs are stated to reduce the required relay node count.

  • Algorithm 3, which uses Algorithms 1 and 2 and Lemmas 1 and 2, is developed to create k-connected WSNs with placing the least relay node count.

The rest of this paper is organized as follows: literature is reviewed in Sect. 2; the method is proposed in Sect. 3; the method performance is evaluated in Sect. 4 and the article is concluded in Sect. 5.

2 Literature Review

The problem of relay node placement in order to address fault tolerant WSNs is assessed by many prior studies with various views and under different situations in the networks [6]. In each study, a specific problem is addressed and some special assumptions are made for the networks are considered and a heuristic or meta-heuristic scheme is proposed to solve the problem in the given network. Some aspects of concern are: node structure (homogenous/heterogeneous), node location (constrained/unconstrained) and connectivity type (between all node pairs/between each node and the sink).

Sitanayah et al. [7] exploited a WSN, where all sensor nodes send/receive data through k disjoint paths with limited length to/from a set of sinks. Their proposed method consists of two phases. In the first phase, the k shortest paths between each sensor node and all of the sinks are identified through a heuristic method if possible and in the second phase, the relay nodes are added to the network applying a greedy algorithm in order to set paths are not found in the previous phase.

Nitesh et al. [8] introduced an algorithm that applies Jarvis March approach for relay node placement, where k relay nodes are placed in transmission radius of each sensor node (k-coverage) and there are s relay nodes with at least one path to the sink in transmission radius of each relay node (s-connectivity).

In some cases, the WSN divided into several separated sectors because of nodes failures. The key issue of concern here is to connect these separated sectors through the relay node placement. In the study of [9], relay nodes are placed to set a MST of sectors, and furthermore, maximize the connectivity degree of sectors with the finite relay node count. They implemented this method over grid and non-grid WSN.

WSNs consisting of the nodes with the same transmission radii are named homogeneous-WSN while WSNs are heterogeneous when the nodes have different transmission radii. The different transmission radii of the nodes lead to the asymmetric communication links between adjacent nodes in the network. There are two kinds of connection between nodes as follows: two-way connection and one-way connection. In the two-way connection, data transmission is carried out in both directions, while in the one-way connection; there only exists one direction transmission.

Han et al. [4] proposed connectivity-first algorithm (CFA) for addressing four problems in heterogeneous WSNs as follows: One-way partial fault-tolerant relay node placement, Two-way partial fault-tolerant relay node placement, One-way full fault-tolerant relay node placement, and Two-way full fault-tolerant relay node placement. In their study, the full fault-tolerant network is introduced as a WSN, where there exist k disjoint paths between every sensor and/or relay node pair while in the partial fault-tolerant WSN, k disjoint paths are only between every all sensor node pairs regardless of relay nodes. They apply a σ-approximation algorithm to generate a minimum k vertex connected spanning graph through placing the least relay node count.

Some methods based on the evolutionary algorithms like genetic, bee colony, biogeography based, ant colony and imperialist competitive algorithm are introduced to solve the k connectivity problem in WSNs [10,11,12,13,14,15,16]. These methods require much time to solve the problem due to some reasons such as a prolonged time in exploring the problem space, generating the initial population and improving them.

3 The Proposed Method

In this section, KCN the proposed method for creating the k-connected heterogeneous WSNs is designed. The work model, notations and terms are presented in Sect. 3.1 and the proposed algorithms are described in Sects. 3.2, 3.3 and 3.4.

3.1 Work Model and Assumptions

The initial heterogeneous WSN only includes the sensor nodes with different transmission radii. These sensor nodes are scatter in a random manner on a two-dimensional are of interest. The problem is creating a fault-tolerant WSN by establishing k (> = 1) vertex-disjoint paths between all sensor node pairs through deploying the least relay node count. A WSN can be modelled as a graph G(V,E), where V is a set of vertices and E is a set of edges. The notations, terms and their semantics used in proposed algorithm are listed in Table 1.

Table 1 Notations and semantics
Full size table

3.2 The Minimum k-Vertex Connected Graph

The algorithm for creating the k-vertex connected graphs based on finding the shortest edges is developed here. According to the mentioned lemma in [5], a new method is proposed as a pseudo code in Algorithm 1.

Algorithm 1 is illustrated by an example in Fig. 1. There are 5 sensor nodes in S as depicted in Fig. 1a and the goal is to generate a minimum 3-vertex connected graph (k = 3). The distances between all nodes in the graph are shown in Fig. 1a. S1 is selected as the first node and added to V. Note that it is not important which sensor is the first node and any other sensor can be selected as the first sensor. In the first iteration of the example, m is 1, S5 is selected to be added to V and E15 is added to E as shown in Fig. 1b. In the second iteration, m is 2, S3 is added to V and two edges E31 and E35 are added to E (Fig. 1c). In the third iteration, m is equal to 3, S2 is selected and added to V and three edges E21, E23 and E25 are added to E (Fig. 1d). In the last iteration, m is equal to 3, S4 is added to V and three edges E42, E43 and E45 are add to E (Fig. 1e).

Fig. 1
figure 1

An example of running Algorithm 1

Full size image

3.3 Determining the Candidate Relay Nodes

In this section, an algorithm is presented to locate a set of candidate relay nodes for implementing each edge in the k-vertex connected graph. There are three cases as follows:

  1. 1.

    |Eij| is shorter than both transmission radius of Si and Sj: A two-way (duplex) connection is established currently and no need to deploy the redundant relay nodes.

  2. 2.

    |Eij| is between the transmission radii of Si and Sj: A one-way (simplex) connection is established currently and relay node placement is required in order to establish the opposite (direction) connection.

  3. 3.

    |Eij| is longer than both transmission radii of Si and Sj: There is no connection between two sensor nodes and relay node placement is required for establishing connection in both directions.

A pseudo code for locating the candidate relay nodes for each edge in the k-vertex connected graph is illustrated in Algorithm 2. To better understand Algorithm 2, three examples are presented in Fig. 2. As is shown in Fig. 2a, there is not any need to deploy a candidate relay node when distance between Si and Sj is less than both Ti and Tj. Figure 2b, c show the required candidate relay nodes for cases 2 and 3, respectively. In Fig. 2, cr indicates a candidate relay node.

Fig. 2
figure 2

The candidate relay nodes for implementing an edge (cr indicates a candidate relay node)

Full size image
figure d
figure e

3.4 Creating KFTN

The aim of this section is to propose an algorithm to implement a k-connected WSN based on the k-vertex connected graph the output of Algorithm 1. An edge in a graph can only connect two vertices, however, a relay node in a WSN may connect more than two sensor/relay nodes. The reason behind this fact is that a relay node has a transmission radius and all of the nodes in its transmission radius can send/receive data to/from it. An example of implementing two edges through only applying one relay node is shown in Fig. 3. Four sensor nodes x, y, z and u and their two corresponding edges Exy and Ezu are indicated in Fig. 3a. Both of these edges can be established by one relay node r (Fig. 3b). This idea is the basis of the technique applied here to reduce the required relay node count. The terminologies which are used in this section are described below:

Fig. 3
figure 3

Applying of one relay node for implementing two edges

Full size image

K-Fault-Tolerant-Network (KFTN): the WSN that remains connected after k-1 nodes (sensor or relay) failures.

Sub(CRt): the set of at least k sensor and relay nodes placed previously. The nodes of this set can play the role of the candidate relay node CRt in setting up the edge between two sensor nodes.

SCRij = [Si, CR1, CR2, …, CRm, Sj]: the sorted set of required candidate relay nodes to implement the edge between Si and Sj. The set of candidate relay nodes obtained from Algorithm 2 is sorted based on the polar coordinates of the nodes over a straight line from Si to Sj. The term m is use to indicate the number of candidate relay nodes for setting up the edge Eij. If Eij does not require any relay nodes then SCRij = [Si, Sj].

The flowing lemmas applied in Algorithm 3 are introduced as follow:

Lemma 1

Let Eij be an edge in a KFTN and CRt is a candidate relay node over this edge. If there exist at least k placed nodes (sensor or relay) where each of them has a two-way connection with both the previous and the next nodes of CRt in the set SCRij then placing the CRt can be disregarded without disconnecting Eij and losing k-connectivity in the KFTN. These placed nodes are added to the set Sub(CRt).

Proof

According to the mentioned assumptions \(\left| {\left| {~Sub\left( {CR_{t} } \right)} \right|} \right| \ge k\). Removing k-1 nodes from the set Sub(CRt) cannot disconnect the edge Eij, because at least one node remains in the set Sub(CRt) which connects the previous and the next nodes of CRt over the edge Eij. These removed nodes in the worst case lead to a 1FTN. Thus, the network will stay as a KFTN even if the placement of CRt is disregarded.

Lemma 1.1

The Sub(CRt) must have at least k placed nodes (sensor or relay).

Proof

Suppose the set Sub(CRt) has k-1 nodes. Removing all these k-1 nodes in a KFTN can lead to a 1FTN without respect to Eij in the worst case. Since the connection between the previous node (CRt-1 or Si) and the next node (CRt+1 or Sj) of CRt over the edge Eij is lost, Eij would be disconnected, and consequently, the network is not connected any more. Therefore, substituting CRt with at most k-1 nodes does not assure that the network is KFTN.

An example of using Lemma 1 to reduce the required relay node count is shown in Fig. 4. Assume that k = 2 and the edge between Si and Sj (Eij) exists in E (according to Algorithm 1) and three candidate relay nodes CR1, CR2 and CR3 are required to implement Eij (according to Algorithm 2). The sensor node Sz is one of the initial sensor nodes (set of S) and Ri is the relay node which has been deployed previously (according to Algorithm 3). As are represented in Figs. 4.a, 4.b and 4.c, two nodes Sz and Ri can play the role of CR2 and connect CR1 to CR3, therefore Sub(CR2) = {Sz, Ri} and based on Lemma 1, CR2 can be disregarded while the network would remain 2FTN.

Fig. 4
figure 4

An example of using Lemma 1

Full size image

Lemma 2

Let Eij be an edge in a KFTN and CRt is the candidate relay node over this edge and CRt-1 is disregarded based on Lemma 1. If there exist at least k deployed nodes (sensor or relay) that each one has a two-way connection with the next node of CRt in the set SCRij and at least one node from Sub(CRt−1) separately, then placing the CRt can be disregarded without disconnecting Eij and losing k-connectivity in the KFTN. These placed nodes are added to the set Sub(CRt).

Proof

The initial network is a KFTN and \(||Sub\left({CR}_{t}\right)||\ge k\). Removing k-1 nodes from Sub(CRt) cannot disconnect the edge Eij and at least one node remains that can connect Sub(CRt-1) to the next node of CRt over the edge Eij. In the worst case, the removed nodes lead to a 1FTN. Thus, the network will be a KFTN after disregarding the placement of CRt.

Figure 5 shows an example of applying Lemma 2 on the network in Fig. 4 after disregarding CR2. This case considers how candidate relay node CR3 would be disregarded. Assume that the sensor node St and the relay node Rj have been placed previously. As observed in Figs. 5.a and 5.b, St can connect Ri to Sj and vice versa as well as Rj can connect Sz to Sj and vice versa. As a result, Sub(CR3) = {St, Rj} and based on Lemma 2, CR2 can be disregarded while the network would remain 2FTN.

Fig. 5
figure 5

An example of using Lemma 2

Full size image

According to Lemmas 1 and 2 a new algorithm to implement a KFTN with placing the least relay node count is proposed as a pseudo code in Algorithm 3.

3.5 Time complexity

Algorithm 3 consists of two parts which run sequentially: the first part is line 1 which calls Algorithm 1 and the second part is a while-loop (starting from line 3). The runtime of these two parts are calculated firstly and then the summation of them is introduced as total runtime.

figure f

The first part: Algorithm 1 has a while-loop (starting from line 7) which is repeated n (the number of sensor nodes) times because ||S||= n and in the beginning ||V||= 0. There is a for-loop (starting from line 12) into the while-loop. This loop is iterated n-1 times in the first cycle of the while-loop, n-2 times in the second cycle and etc. In this for-loop, there is another for-loop (starting from line 13) repeated maximum k times in each cycle. Therefore, the runtime is cculated based on Eqs. (1 and 2).

$$T1\left( n \right) = k\left( {n - 1} \right) + k\left( {n - 2} \right) + \cdots + 2k + k$$
(1)
$$T1\left( n \right) = {\text{}}\frac{{kn^{2} - kn}}{2}{\text{}}$$
(2)

The second part: As mentioned above, the second part of Algorithm 3 is a while-loop (starting from line 3). The number of iterations of this loop is c k-vertex connected graph returned through Algorithm 1 (presented in Eq. (3)).

$$\left| {\left| E \right|} \right| = \underbrace {{1 + 2 + \cdots + \left( {k - 1} \right) + \overbrace {{k + k + \cdots + k}}^{{n - k}}}}_{{n - 1}}$$
(3)

Algorithm 2 does not have any loop and returns the candidate relay nodes for each edge. Assume that the number of candidate relay nodes for each edge is t (a constant value). The inner for-loop (line 7) is iterated t times. Therefore, the runtime of the second part is calculated according to Eq. (4).

$$T2\left( n \right) = {\text{}}\frac{{2kn - {\text{}}k^{2} - k}}{2}{\text{}} \times t$$
(4)

The time complexity of Algorithm 3 is expressed through Eq. (5). Accorngly, the overall time complexity of KCN is O(n2).

$$T\left( n \right) = T1\left( n \right) + T2\left( n \right) = {\text{}}\frac{{kn^{2} - kn}}{2} + {\text{}}\frac{{2kn - {\text{}}k^{2} - k}}{2}{\text{}} \times t$$
(5)

4 Performance Evaluation

The performance of KCN is compared to CFA [4] and simple-KCN by using simulation. To the best of the authors’ knowledge here, The CFA is the only method in the literature that creates k separate paths between all sensor pairs in heterogeneous WSNs. Therefore, both KCN and CFA focus on the same problem. The CFA method creates a k-vertex connected graph through adding edges with the highest contribution from the complete graph. The contribution of each edge is defined based on the sensor pairs that disjoint paths between them are fewer than k and the connectivity of them can be improved through this edge. The simple-KCN method creates the k-vertex connected graph and determines the set of candidate relay nodes for all edges in the graph and places all candidate relay nodes without disregarding any of them. MATLAB is used as the simulation environment.

In the simulation experiments, the area of interest size is 1000 m × 1000 m and the sensor nodes are scattered on this area in a random manner. Two types of simulations are considered in this work. In both the types, all sensor nodes have a random transmission radius between 200 and 500 m and the average outputs of 50 runs are considered as the final simulation results.

In the first simulation, the transmission radius of all relay nodes is 350 m. The sensor node count is gradually increased from 5 to 50. The comparison between KCN with CFA and simple-KCN in terms of the required relay node count to assure that the WSN is k-connected are diagrammed in Fig. 6. There are some interesting tips. In Fig. 6a (k = 2), KCN always requires less relay nodes than CFA and arrives at zero in 40, however, CFA in 50. In Fig. 6b (k = 4), KCN has better results in many times but not all times. When the sensor node count is small or large (in both Fig. 6a, b), the KCN and simple- KCN have the same results. In a sparse WSN, the distances between sensors are too far and it is unlikely to disregard a candidate relay node. Also if the sensor node count is large, the connectivity of the initial network is high, and therefore, the difference of results of both KCN and Simple-KCN is slight.

Fig. 6
figure 6

The required relay node count. a k = 2. b k = 4

Full size image

In the second simulation, the transmission radius of all relay nodes is gradually increased from 200 to 500 m. Figure 7 compares the methods in terms of required relay node count for connectivity level k = 4. Figure 7a shows the results for 20 sensor nodes and Fig. 7b shows for 60 sensor nodes. As shown, when the sensor node count is 20, CFA has slightly better results, while for 60 sensors the results of KCN are significantly better than CFA. The reason behind this better result is that KCN tries to use the initial sensor nodes instead of deploying new relay nodes. Thus, the more the number of sensor nodes, the better the performance of KCN.

Fig. 7
figure 7

The required relay node count. a n = 20. b n = 60

Full size image

5 Conclusion

The problem of relay node deployment in heterogeneous WSNs is assessed here, where all sensor pairs must be connected by at least k separate paths. To solve this problem, the KCN method consisting of three heuristic algorithms, is proposed. Algorithm 1 creates the minimum k-vertex connected graph; Algorithm 2 determines the candidate relay nodes and Algorithm 3 minimizes the deployed relay node count. The method applies Lemmas 1 and 2 to decide on whether to disregard a candidate relay node based on some heuristics. To evaluate the performance of the proposed algorithm, two key issues are considered: the time complexity and the required relay node count. As proved, KCN has a low time complexity of O(n2), where n is the sensor node count. The simulation results confirm that the ability of KCN in reducing the required relay node count is higher than the most closely related approach. The future work will focus on reducing the edge count of the k-vertex connected graph in order to reduce the network cost.