Keywords

1 Introduction

WSNs have been comprehensively deliberated for their wide ranging applications, for example, border or combat zone surveillance, space discovery, assessment of geological characteristics of a region, search and rescue operations, industrial process monitoring and management, and many others [1]. WSNs are usually consisting of substantially large set of miniature sensors typically restrained in their battery power, computation and communication reserves. These sensor nodes cooperate with each other in a disseminated and self-governing way to collectively achieve an assignment usually without having an infrastructural support in the environment. Ensuring energy efficiency and restoring network-wide connectivity in the event of failures are some of the indispensable characteristics for WSNs to make the network functionally sustainable in the case of sensor’s battery power exhaustion, hardware/software malfunctioning, link failures, or hostile environmental circumstances [2]. Topology management is one of the significant techniques employed to substantially minimize battery power utilization and sustaining network-wide connectivity [3]. In the literature, numerous proactive and reactive topology management techniques have been propositioned to tolerate sensor breakdowns in WSNs [4].

In this paper, we propose a proactive fault-tolerant topology management algorithm which is to be employed in a heterogeneous WSN deployment. This is a two-layered sensor node deployment framework where the lower layer is composed of resource-constrained sensor nodes with restricted battery power, low communication and computational capabilities. The higher layer is composed of resource-extensive sensor nodes with enhanced battery power, storage, and high computational and communication capabilities. However, these resource-extensive sensor nodes (supernodes) are deployed in limited quantity owing to their high cost. These supernodes experience longer transmission ranges and higher transmission rates between them. In this heterogeneous WSN, deployed sensor nodes accumulate data from their environment and forward their accumulated data to the supernodes for further processing. Such category of WSN setup is considered to be more consistent and has enhanced network life span compared to homogeneous WSN setups.

This paper proposes an algorithm called the transmission power efficient disjoint path (TEDP) for instituting a fault-tolerant topology to trail accumulated data by sensor nodes to supernodes. In WSNs, assuring k-connectivity in the network topology is essential to ensure a definite degree of fault tolerance [4]. In the worst case, the ensuing topology can sustain up to k − 1 sensor failures. We present a distributed algorithm TEDP for resolving k-connectivity problem in an effective means with respect to total transmission power of the ensuing topologies, utmost dispensed transmission power of sensor nodes, and entailed transmissions of control messages. The experimental outcomes demonstrate that our TEDP algorithm realizes on an average 25% decline in total transmission power necessitated in the network based on the packet failure rate, and a 30% decline in utmost transmission power necessitated in a node contrasting to some of the extant solutions. The effectiveness of power optimization is the outcome of our proposed scheme that we employ while ascertaining the disjoint routes. This scheme entails in accumulating the entire route information in preference to just having information about the next node on the routes and offers a large-scale discovery of the best routes all over the network except for the need of information about span of the network.

We present interrelated work on topology management techniques designed for WSNs in Sect. 2. Section 3 illustrates our proposed approach and TEDP algorithm and the experimental outcomes in Sect. 4. Finally, our proposed work is concluded in Sect. 5.

2 Related Works

Topology management is best described as managing a group of neighbor nodes in a WSN by means of fine-tuning the transmission range and/or deciding on distinct nodes in order to ensure the messages getting forwarded [5]. Topology management strategies may be split primarily into two categories, specifically, homogeneous as well as nonhomogeneous. In homogeneous strategies, all sensors do have identical transmission ranges in contrast to nonhomogeneous strategies where sensors may have diverse transmission ranges.

There are numerous topology management strategies recommended in literary works, and they may be categorized in line with the techniques they employ [6]. Several topology management techniques are designed on the transmission power regulation technique which in turn is dependent upon the capability associated with sensors to manage their transmission power [7, 8]. A number of algorithms employ sleep scheduling mechanism which is designed to diminish energy utilization while nodes are in the state of idle [9,10,11]. Some others employ symmetrical configurations, position and directional information [12,13,14]. The distinction among most of these studies and our proposed work is that we make an effort to lessen nodes’ overall transmission power in two-tiered heterogeneous WSN setups while others resort to homogeneous setups. Moreover we give attention to connectivity amid a sensor node and supernodes, while they concentrate on ensuring connectivity amid any pair nodes.

Clustering may also be viewed as one more means of ensuring topology management in which the intention is to coordinate the network into a hierarchical organized structure to ensure load balancing among the nodes and enhancing the network life span [15]. Some techniques choose cluster heads based on numerous standardized criteria and build a layered structure [16, 17]. Nevertheless, in our proposed work we build a layered topology having supernodes and sustain fault-tolerant connectivity amid sensor nodes and supernodes.

Wireless sensor and actor networks (WSANs) typically have a two-tiered setup in which the lower layer is composed of inexpensive sensors and the higher layer is composed of resource-expensive nodes (often known as actors or supernodes) which usually undertake suitable measures [18]. WSANs essentially have two types of communication links: sensor-to-actor and actor-to-actor [19]. Numerous strategies have been suggested with regard to sustaining reliable sensor-supernode connectivity [20, 21]. However, these techniques do not make use of k-vertex disjoint connectivity amid inexpensive sensor nodes and supernodes, and therefore, the network may not withstand the failure of k − 1 sensor nodes. Though the technique prescribed in [19] ensures the k-supernode connectivity, it does not take into account the power effectiveness of the ensuing topologies. Our proposed technique varies from most of these efforts by sustaining k-connectivity as well as dealing with energy effectiveness in unison.

Cardei et al. [22] suggested a fault-tolerant topology control mechanism intended for heterogeneous WSNs having two-layer architecture ensuring both k-connectivity and energy effectiveness. This mechanism is designed to amend sensors’ communication range to realize k-vertex disjoint connectivity to supernode as well as to minimize the utmost communication power level of inexpensive sensors. Authors recommend a centralized mechanism named global anycast topology control (GATC). This mechanism strives to minimize the communication power level of inexpensive sensors but achieves this having network-wide topology information. However, this may not be realistic considering its implementation in significantly large WSNs. Authors proposed a distributed approach named distributed anycast topology control (DATC) that offers k-vertex disjoint connectivity to supernode by means of augmenting the communication coverage of sensors by small raises. However, the distributed DATC algorithm provides a far more realistic means to ensure k-connectivity. DATC entails 1-hop neighborhood topology information, which may be stretched to n-hop. The aim of this algorithm is to make sure that any sensor node SNi is either directly reachable to any other sensor node SNj in its accessible region or presence of minimum k disjoint routes amid SNi and SNj.

The localized DATC starts with building a minimum set of neighbors with the least communication power level for every node. The power level of each node is augmented with little increments to discover other accessible nodes from the paths of neighbors. The path discovery scope may get restrained owing to this fact that several nodes outside the accessible neighborhood may be unknown to the node executing discovery. DATC is having this significant constraint for the reason that it has minimal possibility to uncover k disjoint paths for the 1- or 2-hop distance neighbor nodes from the node executing discovery. As opposed to DATC, our proposed algorithm ensures each node to uncover paths which includes nodes beyond its accessible region by storing entire path information from supernodes to sensor nodes. This information is stored in the local information table maintained by each sensor node. Like this, our proposed algorithm offers a lot more possibility to uncover improved k-disjoint paths and better power optimization in comparison with DATC. In the course of uncovering disjoint paths, sensor nodes serve possibly with the utmost transmission power as a consequence of improving the possibility of uncovering more disjoint paths. Our experimental outcomes are in compliance with our proposed discussion.

3 Transmission Power Efficient Disjoint Path

Our proposed fault-tolerant topology management algorithm operates in a two-tiered heterogeneous WSN architecture comprising resource-intensive supernodes and resource-constrained sensor nodes.

In order to accomplish fault-tolerant topology, we give attention to k-vertex disjoint connectivity to supernodes. This means every sensor has connectivity to a minimum of one supernode by means of k-vertex independent routes. In the worst case, the resultant topology is able to sustain the failure of k − 1 sensor node failures. Our presented algorithm tends to eliminate the edges which do not belong to any one of the sensor-to-supernode k-disjoint paths. To make this happen, we figure out neighbor nodes that are on one such disjoint paths and that are not. This algorithm discovers a set of essential vertices to assure k-vertex supernode connectivity. Obtaining the set of essential vertices, each sensor node eliminates those edges not connected to an essential vertex. Subsequently, in order to save battery power of sensors, we reduce the transmission range of sensors nevertheless can reach the furthest node in the newly constructed neighbor set. Since this proposed algorithm is a localized and distributed algorithm, hence is implemented by every sensor node in the network. It does not require global topology information. Rather each node requires 1-hop topology information. The messages discover the disjoint paths from sensor nodes to supernodes incorporating path information from supernodes to inexpensive sensors.

3.1 Network Model

Our algorithm makes a consideration of a nonhomogeneous network comprising of SPN resource-intensive nodes and SN low-cost sensor nodes, where SPN ≪ SN. Sensors are positioned at random, whereas supernodes are positioned at identified sites. We are concerned about the communications from sensor node to sensor node and from sensor node to supernode. We are least concerned about the communications from one supernode to another supernode for the reason that they are resource-intensive and can communicate directly employing their utmost transmission range. In the original WSN deployment structure, every sensor is having a maximum transmission range TRmax.

3.2 Problem Statement

We intend to build a two-tiered heterogeneous WSN topology to ensure k-vertex supernode connectivity in order to route data accumulated by sensor nodes to the supernodes. We strive to lessen the dispensed power required for transmission for each and every deployed sensor nodes and at the same time sustaining k number of disjoint routes from every sensor node to the subset of supernodes. Herein newly formulated topology, each sensor node ought to be connected to a minimum of one supernode having k number of vertex disjoint communication routes.

We characterize this problem in this way: provided a k-vertex disjoint supernode linked topology having SPN resource-intensive nodes as well as SN resource-restrained nodes able to regulate the communication range to a predesignated constant TRmax, ascertain the communication range of every SN with the aim to substantially reduce the overall power required for transmission and the ensued topology continues to be having k-vertex supernode connectivity.

3.3 Algorithm for K-Vertex Supernode Connectivity

The proposed localized algorithm TEDP effectively dispenses diverse transmission power levels for nodes while sustaining k-vertex supernode connectivity. It operates in five phases. The first is the route information assortment phase which is undertaken by the supernodes via Initialize messages. This message can only be created and sent out by a supernode and encompasses supernode ID. All sensors deployed in the network receive this message and initiate the updation in their local information table based on the data encompassed in the Initialize message. Every sensor node does maintain a disjoint route list. If any updation takes place in the route list, then sensor nodes send out RouteInfo messages. When this RouteInfo messages are received by the sensor nodes, each sensor node makes a computation on the disjoint routes based on the entries in the information table and the information is incorporated in the received RouteInfo. If there is a reduction in the disjoint route cost after the computation is observed, then the message incorporating the revised information related to the route is forwarded. The highest cost of the route is the cost of the disjoint route in the set of disjoint routes maintained by a sensor node. The moment it is observed that no further reduction in the computation of routes lists, the first phase of the proposed algorithm comes to an end. The second phase ensures every sensor node computes its entailed neighbors by employing the locally computed disjoint routes list.

The third phase ensures every sensor node constructs a Notification message for each distinct disjoint route and forwards the message downward the successive nodes in the disjoint route. Each node in the distinct route tags each other as a neighbor for establishing k-vertex disjoint connectivity to supernode. The fourth phase eliminates those untagged neighbor nodes from the list of neighbors maintained at each sensor node. The concluding phase makes certain that each sensor node regulates its transmission power level to be within the coverage of the farthest neighbor in consistent with the newly formulated topology. The TEDP algorithm notations are introduced in Table 1. The route information assortment phase in TEDP is given in Algorithm 1.

Table 1 TEDP Notations
Full size table

Algorithm 1. Path Information Collection in TEDP

The initial phase commences with supernodes broadcasting Initialize messages throughout the network. Upon receiving the message, each node initiates to update its own route information table by creating a new entry on behalf of the newly instituted route to supernode. The entry information will consist of supernode ID and the link cost (span of the link) between the node which received the message and the supernode. The route cost is the span of the most elongated link in the route. The routes in the information table are arranged in accordance with cost in an increasing order.

When the information table is updated, each sensor constructs and relays a RouteInfo message containing its ID and information table to their accessible neighborhood employing utmost transmission power. Upon receiving RouteInfo message, each sensor node computes the union of the routes received through RouteInfo message and the existing in its local information table. The least cost for a set of disjoint routes for the recently computed union and the existing is estimated. The size of the estimated disjoint sets is no more than k since we provision k number of disjoint routes in the ensuing topology. The route information table gets updated when the newly computed cost is less than the existing route cost. Finding disjoint routes (DIS) is given in Algorithm 2.

Algorithm 2. Finding Disjoint Routes to Supernodes (DIS)

If a RouteInfo message has not affected any update in the disjoint path list of the receiver, in that case no RouteInfo message is relayed by that node. Any update can be effect if a lesser cost disjoint route is ascertained through this message. The algorithm provisions an upper bound on the count of RouteInfo messages to be sent by the sensor for the duration of this phase. This restriction assures the convergence of this algorithm. It may happen in the worst case that there may be │E│ disjoint routes with distinct costs in the order of reducing costs. │E│ is the count of edges in the network. Then the sensor node will have to send maximum │E│ number of RouteInfo messages. Since we may have at most \({\text{O}}(n^{2} )\) edges given a graph having n number of nodes, we may come to this conclusion that a sensor node may send out \({\text{O}}(n^{2} )\) RouteInfo messages. This is an exceptional case when every node has an edge with every other node in the network. This upper bound may be articulated as \({\text{O}}({\text{nd}})\); here \({\text{d}}\) indicates the utmost node degree.

It is proposed to restrict the count of hops a RouteInfo message has to travel for the duration of route information phase. The supernode specifies a time-to-live (TTL) field value for the RouteInfo communication and sends this value to sensor nodes through Initialize message. This TTL value is incorporated in every RouteInfo message and has the effect on the count of hops in the concluding established path. When a sensor node receives a RouteInfo message, it checks its TTL value in the message and if the TTL value has reached the preassigned value then no more RouteInfo message is initiated by the receiver node irrespective of whether this message has caused any update in its disjoint list. This is to ensure that the disjoint routes having the length exceeding certain prescribed restricted value are not contemplated in the computation of disjoint list.

The next phase of this algorithm ensures each and every node in a preferred route is to be tagged as essential neighbor nodes. In order to ensure this, every node sends out a Notification message to all its preferred routes. This message gets communicated alongside the route. Every neighbor node along the route tags one another as essential neighbors. If any pair of neighbors does not tag one another, then it is understood that the connected link amid these neighbors is not indispensable hence may be subsequently eliminated. Obtaining the decided list of essential neighbors, each node tends to regulate its transmission power to extend its coverage access to the furthest neighbor in the newly formulated topology.

The execution time complexity of this algorithm is Ο(nd2); here n is count of sensors deployed in the network, and d is the utmost node degree.

4 Performance Evaluation

4.1 Experimental Setup

In our simulation setup, the low-cost sensors are positioned indiscriminately in a 500 m × 500 m region and the least (5% of total deployed sensors) count of resource-rich supernodes are deployed uniformly in a deployment region. The utmost transmission range TRmax of the sensors is set to be 100 m, and the path attenuation exponent is set to be 2, and the degree of disjoint connectivity (k) is equal to 2. We assume the adaptable transmission range of supernodes is up to 300 m.

4.2 Overall Transmission Power

We take an account of our simulation outcomes presenting the power expended by the sensor nodes in the formulated topology (with k = 2) subsequent to the implementation of DATCh = 1 (1-hop) and DATCh = 2 (2-hop) local neighbor. In Fig. 1, the count of sensors enhanced from 100 to 500 and the count of supernodes is fixed at 5% of the count of sensors deployed in the network. This clearly indicates that the induced topologies by our TEDP algorithm incur less total transmission power than DATC algorithm for values of h = 1 and 2. This gives the explanation that the DATC approach encounters intricacies in finding the alternate disjoint routes to an elongated disjoint edge employing 1-hop or 2-hop neighbor region information. This leads to restricted disjoint path search scope; hence, the elongated disjoint paths cannot be replaced with shortened paths, in consequence, ensuing long transmission ranges and thus expended transmission power. One more significant observation associated with the implementation of DATCh = 1 and DATCh = 2 is that DATCh = 2 having larger search scope offers considerably better results than DATCh = 1 with restricted search scope.

Fig. 1
figure 1

Overall transmission power

Full size image

4.3 Utmost Transmission Power

Utmost transmission power is certainly an imperative performance metric for the induced topologies for the reason that this metric provides significance to ensuring equilibrium of battery power utilization among all nodes. Even though the total transmission power in the generated topologies is low, the topology may get disengaged if some of the sensors with large communication ranges employ utmost transmission power utilizing more battery energy than others leading to faster exhaustion of battery energy. In this section, we take an account of our simulation outcomes on utmost power among the entire nodes in the ensuing topologies induced by TEDP and DATC for the value of k = 2 and the count of supernodes which is 5% shown in Fig. 2.

Fig. 2
figure 2

Utmost transmission power

Full size image

The performance of our TEDP algorithm is considerably improved than that of DATC. This is because our algorithm can find k number of disjoint routes to the supernodes with the information available in the local path tables maintained by each sensor node, whereas DATC cannot find as many disjoint paths as our algorithm because DATC is having an access to information restricted to only its reachable neighborhood effecting utmost transmission ranges.

4.4 Overall Count of Control Message Transmissions

Here, we illustrate our simulation outcomes with respect to total count of transmissions of control messages for the duration of the implementation of TEDP and DATC. This is imperative to consider control message transmission as a performance metric as it is essential to take into account of energy utilization in the induced topologies as well as for the formation of those topologies. High message transmission cost may not be effective for ensuring energy efficiency in the formation of a stable topology. We observe that DATCh = 2 necessitates larger count of message transmissions as compared to TEDP or DATCh = 1. This is because DATCh = 2 necessitates each node to inform to all its 2-hop neighbor nodes. In contrast, both DATCh = 1 and TEDP entail a single message transmission when there is a path information table update. In DATCh = 2, each sensor node necessitates d number of message transmissions, where d is the node degree. Since DATCh = 2 entails larger count of message transmissions, hence, may not be realistic to put into practice. Transmission of too many messages for the duration of execution may trigger all the sensor nodes to exhaust their battery power more quickly, hence making the network ineffective.

4.5 Packet Loss Effect

In wireless medium, transmissions may suffer from intermittent packet losses as a result of communication link failures, collisions, deficiency of strong signal, high bit error, etc. In this paper, we intent to show a network situation where any communication link may suffer from packet losses with a known probability. We take a view that the overall transmission power increases with the increased value of PLR. This is because a large count of messages gets lost during transmissions owing to having a large PLR value causing the sensor node to have partial information about topology from the sensors in their neighborhood. Utilizing this limited information about the topology, algorithms may fail to obtain optimized disjoint paths for the reason that message encompassing the path information may be lost during its transmission due to transmission failures.

5 Conclusion

In this paper, we present a distributed fault-tolerant topology management algorithm for a nonhomogeneous WSN composed of resource-intensive supernodes and resource-constrained sensor nodes. Our algorithm ensures that every sensor node strives to establish k number of vertex disjoint connections with supernodes. The aim of our algorithm is to substantially reduce overall power utilization in WSM. Simulation outcomes show that our TEDP algorithm in comparison to existing DATC algorithm attains the decline in overall transmission power substantially by 25% and the decline in utmost transmission power needed in a sensor node by 30% under the supposition of no packet losses. With the consideration of PLR between 0.2 and 0.3, DATCh = 2 performs considerably better compared to TEDP with respect to overall transmission power. In addition, TEDP entails fewer message transmissions and receptions in comparison to DATC. Our proposed distributed algorithm is appropriate for real WSN applications on account of its scalability to large networks.