Scaling hierarchical clustering and energy aware routing for sensor networks

Abstract

Energy efficiency in wireless sensor networks (WSNs) is of a primary concern due to the limited energy capacity of sensor nodes. Since most power dissipation occurs in wireless communication, it becomes imperative to reduce the energy costs of communication by developing power efficient communication protocols. To that end, this paper presents scaling hierarchical power efficient clustering with energy aware routing (SHEAR), which offers a clustering based scalable topology control coupled with an energy aware path selection scheme. By selecting cluster heads based on the maximum local residual energy of neighboring nodes, the topology control of SHEAR distributes energy dissipation evenly among all clusters. Additionally, routes for packet flows are allocated such that the aggregate energy consumption along a chosen path is minimized while avoiding the nodes with low energy levels. Simulation results demonstrate the effectiveness of SHEAR in attaining reasonably long-lived WSNs.

Background

Advances in the fields of low power radio and micro-electromechanical systems have given rise to smart devices with embedded control systems and computational units. The impact of such smart devices has become pervasive in controlling the environment we live in or care about. Smart devices that also benefit from micro-sensor technologies and communication components are referred to as sensor nodes that can monitor physical phenomena or measure parameters of interest such as temperature, vibrations, humidity and so on. To collect and communicate the sensed information from a spatial environment, sensor nodes are deployed distributively over wide geographical areas and are interconnected wirelessly. This constitutes a WSN that performs concurrent data acquisition from distributed nodes and transmits the sensed data over its wireless channel to a supervisory control point, called a Base Station (BS), for monitoring or onward transmission purposes (Yang 2014). WSNs are complex networks (Batool et al. 2014; Kumar et al. 2015), which have found their applications ranging diversely from military to industrial to environmental implementations and so forth.

Despite however all the profound advantages of their usage, a key challenge limiting the widespread adoption of WSNs is the energy constraint (Khan et al. 2015; Rawat et al. 2014; Batool et al. 2014; Ahamed et al. 2013; Anastasi et al. 2009). Small batteries with limited storage capacities are generally the main energy source of sensor nodes as solar energy is not always an option. Once deployed, sensor nodes are typically left unattended at remote and hostile environments where it is mostly unfeasible to access the nodes to replace or recharge batteries.¹ This constraint makes energy the most valuable commodity of sensor nodes since a network should have a lifetime long enough to fulfill its application requirements. Generally, the network lifetime is quantified in terms of the number of packets transmitted in a network until the first node dies due to a completely depleted energy (Senouci et al. 2012; Younis and Fahmy 2004). Thus, it turns out that in order to increase the lifetime of WSNs, the most important design goal is to attain power conservation at all layers of the protocol stack of sensor nodes, which encompass sensing, data processing and wireless communication subsystems. The “communication subsystem” of sensor nodes generally has energy consumption several orders of magnitude higher than those of the other subsystems. This is to the extent that transmitting one bit may consume as much energy as executing a few thousand instructions (Anastasi et al. 2009; Mohanoor et al. 2009). Therefore, research on the network layer aims mainly at energy efficient routing protocols.

Consequently, several categories of routing protocols exist for WSNs, as overviewed in (Pantazis et al. 2013; Boukerche et al. 2011; Singh et al. 2010). The work in this paper falls in the category called hierarchical or clustering routing (Liu 2012), wherein the generic design philosophy is to have topology control by building a hierarchy of nodes to perform data aggregation at various levels of the hierarchy and thereby reduce the communication overhead. Hierarchical routing technique have attracted a great attention for their ability to exploit the tradeoffs among energy, latency and accuracy to earn energy conservation for prolonging the network lifetime (Ahamed et al. 2013; Senouci et al. 2012; Liu 2012; Boukerche et al. 2011; Liu 2012). However, a critical aspect concerning the design of energy efficient routing protocols is the scalability argument (Hamid et al. 2013; Singh et al. 2010). A routing protocol should be readily scalable to large-region WSNs, unaffected by the significant increase in the number of nodes, and should be able to sustain performance in handling long distances that the sensed data must traverse from nodes to BS.

Another front in the research on the network layer tackles the problem of maximizing the network lifetime through developing efficient path selection schemes for packet flows (Boukerche et al. 2011; Hamid et al. 2013). The efficiency of a path selection scheme is of paramount importance in WSNs from the perspective of network lifetime. This is because the energy consumed in transmitting each packet depends largely upon the appropriateness of path selected. If a path selection scheme transmits through several particular nodes invariably, these nodes will die sooner resulting in reduced lifetime of the network (Vergados et al. 2008). Thus, another challenging aspect is to carefully design the path selection scheme of a routing protocol to allocate paths between sensor nodes and the BS in such a way that the network lifetime is maximized.

This paper presents the SHEAR protocol that is aimed at the aforementioned design objectives. SHEAR inherits the clustering approach of the SHPER protocol (Kandris et al. 2009), which is distinguished for its key features of power efficient topology control and scalability. However, one of the significant shortcomings of SHPER is the inappropriate path selection scheme that may lead to longer routes and, thus, to an increased energy consumption. To overcome this shortcoming, the energy aware scheme of SHEAR utilizes those nodes having higher energy levels and avoids those having lower energy levels, such that the overall energy consumption along a data forwarding path is minimized. We make a number of other enhancements to SHPER by improving its localization accuracy, and by augmenting its cluster formation and cluster-head (CH) election mechanisms.

The remainder of this paper is organized as follows. Section "Related work" presents the necessary background and reviews the prominent routing strategies belonging to the hierarchical category of protocols. Section "Hierarchical clustering model of the SHEAR protocol" presents the proposed hierarchical clustering model and the path selection scheme of the SHEAR protocol. Section "Performance evaluation" validates the proposed protocol through simulation based performance evaluation, and "Conclusion" concludes the paper.

Related work

Based on the structure of sensor networks, WSN routing protocols can be broadly categorized into flat and hierarchical approaches (Liu 2012; Pantazis et al. 2013). In flat routing, all nodes are peers and perform data transmissions hop-by-hop, usually in the form of flooding. However, as the networks grow in size, flat routing may become infeasible due to the increased bandwidth requirements, increased routing table sizes and the increased processing overhead caused by the large volumes of messages transmitted directly to BSes (Boukerche et al. 2011; Liu 2012; Pantazis et al. 2013). Conversely, in the hierarchical approaches, the network is divided into geographically clustered layers by using some clustering technique, and according to specific requirements or metrics, such as the energy reserves and proximity of sensor nodes (Singh et al. 2010; Pantazis et al. 2013; Jain and Gupta 2015). Each cluster comprises a CH, which is elected based on different election algorithms, and which is responsible for coordination among the clustered nodes, data aggregation, fusion and routing to the other CHs or the BS. This decreases the number of messages transmitted to the BS to efficiently reduce the energy consumption of sensor nodes. Moreover, hierarchical approaches reduce the size of routing tables and, thus, reduce the load on sensor nodes providing better scalability (Boukerche et al. 2011; Liu 2012; Pantazis et al. 2013; Singh and Sharma 2015). As energy efficiency and scalability are the most important design objectives for WSNs, hierarchical protocols are becoming an active are of routing research (Jain and Gupta 2015; Singh and Sharma 2015). Owing to the aforementioned advantages, we are interested in the hierarchical routing approach. While, all hierarchical protocols share the common goals of energy efficiency and scalability, the key differentiating factors among these protocols are their clustering techniques and the ways of finding and maintaining the routes between source–destination pairs. The remainder of this sections reviews the eminent hierarchical routing protocols.

The clustering routing paradigm is pioneered by Heinzelman et al. (2000) through a simple approach, called low energy adaptive clustering hierarchical (LEACH). LEACH is an adaptive clustering and self-organizing protocol that uses randomization to distribute the energy load equally among nodes. Clusters are formed dynamically and a CH is elected on a rotational basis in each cluster. CHs periodically collect and aggregate data from all other nodes and forward it to the BS. Time division multiple access (TDMA) scheduling is used to avoid excessive energy dissipation by preventing CHs from unnecessary collisions. However, due to single-hop routing, LEACH is unscalable to large-region WSNs.

Nevertheless, the fundamental idea of clustering introduced by LEACH has been an inspiration for many subsequent routing protocols. Numerous variants of LEACH have been proposed, which can be coarsely categorized into centralized and distributed protocols, based on the underlying topology control manners of clustering (Liu 2012; Hamid et al. 2013). Centralized approaches need global information of a network, for a CH to control its cluster, and generally face lower scalability and higher energy consumption issues. Conversely, distributed approaches are promising for their ability to enable added energy efficiency without compromising the service and without requiring global information (Liu 2012; Naeimi et al. 2012). We focus our attention here on the distributed category protocols of the LEACH family, referring the reader to (Tyagi and Kumar 2013) for a more detailed overview. Prominent distributed category extensions to LEACH, which share similar features with the proposed SHEAR in terms of dynamic clustering and multi-hop routing, include TEEN (Manjeshwar and Agrawal 2001), HEED (Younis and Fahmy 2004), TL-LEACH (Loscri et al. 2005), MR-LEACH (Farooq et al. 2010), EHEED (Senouci et al. 2012), and SHPER (Kandris et al. 2009).

Threshold sensitive energy efficient sensor network protocol (TEEN) employs a data centric approach. To reduce the number of transmissions, two sensed attributes, namely hard and soft thresholds, are broadcasted by a CH to inform its member nodes about when to transmit to the CH. Hard threshold restricts nodes to transmitting only if the sensed attribute transcends a critical minimum value, whereas the soft threshold ensures that nodes do not transmit in presence of little or no change in a sensed attribute. TEEN is known as one of the most efficient algorithms in terms of energy efficiency (Pantazis et al. 2013; Liu 2012). Hybrid Energy-Efficient Distributed Clustering (HEED) increases network lifetime by producing well-distributed CHs. It probabilistically elects CHs based on the hybrid combination of a node’s residual energy and the associated intra-cluster transmission cost. Two-Level Hierarchy LEACH (TL-LEACH)_introduces an additional level of hierarchy to include primary and secondary CHs with randomized rotation. Primary CHs act as relay between the secondary CHs and BS for improved energy load distribution. Multi-hop Routing with LEACH (MR-LEACH) divides the network into multiple layers of clusters to minimize energy consumption by adaptively increasing the clustering hierarchy. CHs of each layer relay data for CHs at lower layers and collaborate with each other to transmit sensed data to BS. Any node in a specified layer reaches BS in equal number of hops. Extended HEED (EHEED) considers the network lifetime distribution overtime and space and extends HEED by allowing some non-CH nodes to act as relays between CHs and other non-CH nodes in order to further reduce energy consumption.

While the discussed variants of LEACH considerably improve on the network lifetime, they have their own demerits. For instance, due to the reaction in an abrupt variation of the sensed attributes, TEEN is suitable only for time critical and reactive applications and is inappropriate for applications requiring periodic reports as nodes may not communicate if thresholds are not reached. HEED and EHEED face communication overhead as cluster formation in these approaches requires several rounds, each with a high number of iterations. MR-LEACH has no communication load balancing for each cluster, and the two-hop inter-cluster routing of TL-LEACH is not suitable for dense WSNs. More importantly, a common and noteworthy shortcoming in all these approaches is their inability to scale well to large-region networks (Pantazis et al. 2013; Liu 2012; Naeimi et al. 2012; Tyagi and Kumar 2013).

One of the eminent hierarchical techniques is Scaling Hierarchical Power Efficient Routing (SHPER) (Kandris et al. 2009), which meets both energy efficiency and scalability objectives. The CH election in SHPER is non-randomized and is based on the residual energy of nodes in a cluster. A collection of CHs located close to BS are able to directly communicate with the BS and are termed as upper level CHs. Another category of CHs comprises those located far away from the BS. These are called lower level CHs, which communicate with the BS through adjacent CHs of the upper level. The significance of SHPER lies in the high scalability of its routing procedure that is able to retain performance irrespective of the increase in the network size. Even the most distant nodes in a network are able to route their messages by multi-hop routing via neighboring lower level CHs through the upper level CHs to the BS. SHPER has been demonstrated to outperform TEEN in terms of energy efficiency and scalability and is considered as one of the best-known techniques (Pantazis et al. 2013; Fernandez-Luque et al. 2013; Bangash et al. 2014; Patel and Srivastava 2012).

However, we may identify a number of shortcomings in the SHPER (Kandris et al. 2009) protocol. Firstly, the path selection scheme in SHPER takes into account only the maximum residual energy metric and ignores the total energy consumed along data forwarding paths. This may lead to extremely long routes and subsequently to increased energy consumption, as shall be detailed in "Cluster setup phase". Secondly, just as in TEEN (Manjeshwar and Agrawal 2001), SHPER uses threshold based sensing and, as such, is unsuitable for applications that need periodic reports because nodes may not communicate if thresholds are not reached. Thirdly, SHPER follows an indeterminate random procedure to create the upper and lower levels of the sensor field. This may cause discrepancies in cluster formation and thereby lead to instability of clusters. With the aim to further enhance the network lifetime, this work extends SHPER to overcome its aforementioned shortcomings while making enhancements to its localization and CH election mechanisms.

Hierarchical clustering model of the SHEAR protocol

This section presents the proposed SHEAR protocol. The aims of SHEAR are to enhance the network lifetime by using power efficient and scalable clustering together with an energy aware path selection scheme. The hierarchical clustering strategy of the proposed protocol has been derived from SHPER (Kandris et al. 2009). SHEAR adapts the SHPER’s strong features of scalability and power efficiency while overcomes its aforementioned shortcomings and, at the same time, makes enhancements to its localization and CH election mechanisms.

The model of the SHEAR protocol assumes a set of homogeneous, immobile, and power constrained sensor nodes coexisting with a BS that has an abundant power supply and is capable of transmitting with high enough energy to the entire network. The groups of sensor nodes are distributed arbitrarily within a defined region of interest and the BS is situated statically at a remote location, away from the sensor field. The network is dynamically partitioned into sub-zones called clusters. The network functions are divided in two phases in SHEAR, namely, the cluster setup phase and the communication phase. In the former phase, different clusters are formed each with an elected CH and, in the latter phase, the communication of sensed data from nodes to CHs and from CHs to BS takes place using a least energy cost path. The operation of SHEAR is divided into rounds and each round consists of both the cluster setup and communication phases, as detailed below.

Cluster setup phase

At the beginning of each round, the BS collects information about the existing number of nodes, and their locations and distances. The receivers of all nodes are kept active to let the BS send requests to the nodes to advertise themselves. To that end, the BS creates and broadcasts a TDMA schedule equal in size to the number of alive nodes in the network. In response to the received advertisement request, each node transmits its location information to the BS during its allocated timeslot. As opposed to SHPER (Kandris et al. 2009), wherein the positions and spatial coordinates of nodes are estimated using the received signal strength (RSS); SHEAR uses global positioning system (GPS) for accuracy of localization. This is because RSS based localization is traditionally viewed as a coarse measure of range, which features considerable estimation error due to several negative effects related to signal propagation and suffers inapplicability in rapidly changing environments (Patwari et al. 2003; Whitehouse et al. 2007; Moravek et al. 2011). However, equipping all sensor nodes with GPS receivers is not required in SHEAR since only a few GPS enabled nodes may be sufficient, as shall be discussed in "Discussion".

Next, the BS divides the sensor field into two levels, i.e., a low-level and a high-level, based upon the location information received. Nodes are arranged in the ascending order based on their distances from the BS. The first half, situated close enough to the BS, is included in the high-level, whereas the other half, located far away from the BS, is included in the low-level. Note that SHPER (Kandris et al. 2009) divides the field into two halves using an indeterminate random procedure which may lead to discrepancies in cluster formation. SHEAR further partitions each level into clusters and a node within each cluster is elected as a CH. This hierarchical architecture is illustrated in Fig. 1. The process of election of CHs is described later in this section.

Fig. 1

Graphical depiction of sensor field adopted in SHEAR

The high-level CHs are capable of transmitting directly to the BS. Low-level CHs, however, cannot communicate directly with the BS and transmit via a path consisting of high-level CHs by using multi-hop routing. As with SHPER (Kandris et al. 2009), this setup ensures scalability since the performance of routing procedure is not affected if the overall network size is increased. This is because even the most distant nodes in the network are able to route their messages by multi-hop routing via neighboring low-level CHs through high-level CHs to the BS.

In each round, a node with a maximum residual energy within each cluster is elected as a CH. It is worth noting that SHPER produces CHs by using a threshold residual energy and by comparing the threshold with neighbors for electing a CH. On the contrary, a key feature of the proposed protocol is that CHs are elected based on the maximum local residual energy of neighboring nodes. This is to distribute energy dissipation evenly among all clusters in each round. To that end, each node broadcasts its residual energy to all its neighboring nodes in the timeslot allocated. This process is repeated for the entire network and, as such, every node gets the residual energy from all its neighbors. Each node then compares its own residual energy with that of its neighbors. If a node’s residual energy is greater than all its neighbors, it announces itself as a CH; otherwise, it remains silent. After the CH election, each node would either be a CH or it would have received a CH message from one or more CHs.

Every non-CH node then decides to affiliate itself with a CH from which it receives the CH announcements message. In case if a non-CH node receives more than one CH announcements, it would affiliate itself with a CH having greater residual energy. Once a node has determined which cluster it fits in, the node sends a message to its related CH with request to be a member of its cluster using Carrier Sense Multiple Access (CSMA) protocol. In this way each CH receives messages from sensor nodes requesting to be members of its cluster. The CH then generates a TDMA access schedule equivalent in size to the number of member nodes in the cluster. This schedule is then broadcasted to the member nodes by their CH to inform each node when to transmit.

Communication phase

Once the cluster has been set up in the current round, the data communication phase is initiated, wherein the actual transmission of sensed data from nodes to CHs and CHs to BS takes place. Each non-CH node transmits its sensed data to its CH during an allocated time slot according to the TDMA schedule. To further minimize the power dissipation, each non-CH can turn off its radio until its own allocated timeslot occurs. After receiving sensed data from all its member nodes, each CH performs signal processing to aggregate its own sensed data with the received data into a single composite message along with the IDs of source nodes. This aggregated message is then transmitted to the BS by each CH in its own timeslot, as shall be detailed in the remainder of this section. After completion of the current round, the next round is initiated and the whole process repeats till the lifetime of nodes. The flowchart of the SHEAR protocol is depicted in Fig. 2.

Fig. 2

Procedural flowchart of the proposed SHEAR protocol

High-level CH nodes can transmit directly to the BS using TDMA scheduling. However, since the low-level CHs cannot communicate directly with the BS, they transmit their messages through a path comprising high-level CH nodes. To facilitate this, the low-level CH nodes which are located far away from the high-level may transmit their messages through the adjacent low-level CH nodes located nearer to the high-level of the network using multi-hop routing. Due to this transmission scenario, there may be multiple routes that could be followed by the nodes to forward sensed data to the BS. To determine an optimal data forwarding path at each CH, the route selection scheme of the proposed SHEAR protocol solves a least energy cost path problem, described in the following subsection. Once the least energy cost path is computed, each CH transmits the aggregated sensed information of its cluster to the BS using this path.

Path selection scheme

In developing energy aware route selection schemes, WSNs are typically modeled as graphs with vertices indicating wireless nodes and edges representing communication links between vertices. Graphs are a suitable model to describe complex networks, such as WSNs (Kumar et al. 2015). The weight on a vertex denotes residual energy of that node and the weight on an edge indicates the amount of energy that a node requires to transmit a unit of information along the edge. The residual energy of a route is defined as the lowest energy level of any node on the route (Mohanoor et al. 2009; Liu 2012). The energy consumed along a route is the sum of weights on all the edges present on the route. The most appropriate energy aware route selection scheme for WSNs is to utilize those nodes having higher energy levels and avoid those having lower energy levels, such that the overall energy consumption along the data forwarding path is minimized (Boukerche et al. 2011; Liu et al. 2012).

The SHPER protocol (Kandris et al. 2009) aims to extend the network lifetime based on the residual energy metric by determining a path whereon the residual energy is maximum, and it forwards data packets along this path. However, the energy consumed along the data forwarding path is not taken into account. It is well-established that merely employing the residual energy metric may induce higher network-wide energy consumption (Mohanoor et al. 2009; Boukerche et al. 2011; Hamid et al. 2013; Liu et al. 2012). In case of SHPER, ignoring the energy consumption metric may tend the path selection scheme to intermittently choose longer routes and, thus, compromise energy efficiency, as shall be demonstrated in "Performance evaluation". The aim of the proposed SHEAR protocol is to have an energy aware route selection scheme to balance the two metrics–that is, finding all paths with maximal residual energy and selecting the path that has the minimum energy consumption.

To formally describe the route selection problem for SHEAR, let a graph $G = \left( {N, L} \right)$ represent the wireless network of cluster head nodes $N$(hereinafter referred to as nodes) and edges $L$ consisting of a set of communication links between the nodes. Let the energy required to transmit a packet from node $u, u \in N,$ to node $v, v \in N,$ be represented as $r\left( {u, v} \right), \left( {u, v} \right) \in L;$ and $a\left( u \right)$ be the available energy at node $u.$ Let $E\left( {p\left( {v_{0} , v_{k} } \right)} \right)$ be the energy consumed along a path $p\left( {v_{0} , v_{k} } \right) = v_{0} , v_{1} , \ldots , v_{k}$, which is given as:

$$E\left( {p\left( {v_{0} , v_{k} } \right)} \right) = \mathop \sum \limits_{i = 0}^{k - 1} r\left( {v_{i} , v_{i + 1} } \right).$$

(1)

After sending each packet, the available energy at a node is decreased by the amount of energy required to transmit a packet. Thus, the residual energy $R\left( {p\left( {v_{0} , v_{k} } \right)} \right)$ of the path $p\left( {v_{0} , v_{k} } \right)$ is given by:

$$R\left( {p\left( {v_{0} , v_{k} } \right)} \right) = { \hbox{min} }_{i} \left( {a\left( {v_{i} } \right) - r\left( {v_{i} , v_{i + 1} } \right)} \right)\;\;0 \le i < k$$

(2)

Given a source node –source, and a destination node –dest, the problem to route a packet through an optimal path between the source and dest can now be defined as finding a path $p\left( {source, dest} \right)$ that has: (1) maximum residual energy $R\left( {p\left( {source, dest} \right)} \right)$, and (2) minimum energy consumption $E\left( {p\left( {source, dest} \right)} \right)$. Such an optimal path is referred to as the least energy cost path. The two-fold least energy cost path problem requires data forwarding paths to be selected such that the cumulative energy consumption is minimized along the path while avoiding the nodes that have low energy levels. Nevertheless, finding paths having least energy consumption and finding paths that avoid energy depleted nodes give rise to the conflicting objectives.

We start by outlining the solution to this twofold problem for SHEAR by adapting the two-phased polynomial time combinatorial route selection technique (Mohanoor et al. 2009), which effectively balances the two aforementioned conflicting objectives (Boukerche et al. 2011; Liu et al. 2012). To that end, the undirected graph $G$ is modified into a directed energy graph $EG = \left( {N, L} \right)$ by leaving the vertices intact and by substituting each single undirected edge with two directional edges. The weight on each directional edge in EG is made equal to the difference between the $source$’s energy level and the cost of transmission along the edge to yield the residual energy of the ${\text{source}}$. Next, the algorithm WidestShortestPath is executed on $EG$ for a given $source - dest$ pair.

The algorithm applies a variant of the Dijkstra’s procedure to first find a globally widest path in the network, denoted as $\hat{R}$, which is a path whose residual energy $R\left( {p\left( {source, dest} \right)} \right)$ is the maximum in $EG$. However, there may be a number of paths in EG between source and $dest,$ which have a residual energy of $\hat{R}$. To that end, the algorithm derives a set of all such paths in EG having their residual energy equal to $\hat{R}$ and then determines, from this set, a path having the minimum energy consumption. This is carried out as follows. Let $L^{'}$ be the set of all edges in EG having their residual energy less than $\hat{R}$. These undesired edges are purged from EG and the shortest route is computed on $EG\backslash L^{'}$ using the Dijkstra’s algorithm to yield the least energy cost path. If a number of such paths exist, the algorithm selects one among them arbitrarily. Each CH, thus, computes the least energy cost path by using the WidestShortestPath algorithm and transmits the sensed information to the BS using this route. The purged edges L ^′ are reinstated in $EG$ before the computation of next route.

Performance evaluation

The results of the analysis presented in this section are derived from ns-2 (ver. 2.35) simulations using the 802.11 wireless communication standard. The open source, easily extendable, discrete event simulation platform offered by ns-2 is suitable for studying wired, wireless, mobile and satellite networks. In particular, it provides substantial support and flexibility for analysing the characteristics of wireless networks by offering a wide range of protocols in all layers (Fall and Varadhan 2011), and is known as one of the efficient simulation tools for WSNs (Singh et al. 2008; Korkalainen et al. 2009; Abuarqoub et al. 2012; Tonneau et al. 2015). The object oriented design of ns-2 further simplifies the creation and simulation of new protocols. Moreover, due to the support for localization, CSMA and TDMA protocols required for cluster formation and to allocate each node a data transmission slot to send packets, ns-2 is widely used for the simulation of hierarchical routing protocols (Singh et al. 2008; Zhang et al. 2009). The 802.11 model used in this work supports the authentication, inter-node communication, transmission coordination, and modulation. Further, to avoid unnecessary power consumption, each node is able to turn its radio on and off explicitly by invoking the existing APIs.

Simulation setup

The proposed SHEAR protocol is simulated against SHPER (Kandris et al. 2009), in order to evaluate the network lifetime achieved by these protocols. To that end, the performance evaluation metrics include the number of transmissions, energy consumption, and the number of nodes alive over time. The network field consists of stationary nodes randomly deployed in the sensor field. Each node is equipped with an omnidirectional antenna and has the capability to monitor its residual energy. The routing algorithm of the sensor nodes is replaced with those of SHPER and the proposed SHEAR protocols for simulations and comparisons. To evaluate the consumption of the radio energy in wireless communications, we adopt the widely used first-order radio model of Heinzelman et al. (2000).

All simulations are based on the parameters listed in Table 1. The values for the parameter such as the initial energy of nodes, transceiver circuitry dissipation, sensing and processing dissipation, and the transmit amplifier dissipation are the most commonly used values (Heinzelman et al. 2000; Kandris et al. 2009; Farooq et al. 2010; Tyagi and Kumar 2013; Abdul and Dixit 2015). The SHPER sensing thresholds are the same as originally proposed in (Kandris et al. 2009). However, unlike SHPER where the network size and the number of sensors are kept fixed at 100 × 100 m² and 100 nodes, respectively; we use a wide range of values for these parameters to enable an extensive performance evaluation. To that end, the topology area consists of a flat grid with variable dimensions ranging from 100 × 100  to 500 × 500 m² for the various scenarios presented. The BS is deployed at a distance d away from the field. The value of d and the number of nodes are also varied for each scenario.

Table 1 Simulation parameters (unless specified otherwise)

A total of 320 extensive simulations have been carried out. All results presented in the following subsections are based on twenty replicated simulation runs for each scenario by maintaining fixed values of input parameters and varying the random seeds in each run. The graphs only plot mean values for better readability.

Number of transmissions

Reducing the number of transmissions is crucial to the extension of network lifetime. The SHPER and SHEAR protocols are evaluated in terms of the number of transmissions required in forwarding the sensed information from a source node to the BS. As the number of transmissions is proportional to the number of hops traversed on the forwarding path in the data communication phase, the effectiveness of an underlying path selection scheme is determined by the number of transmissions since a path consisting of fewer hops will induce fewer onward transmissions.

Simulations in this subsection are based on scenarios with sensor field size of 100 × 100 m², the distance d of 100 ${\text{m }}$ between BS and the sensor field, while the number of randomly deployed nodes in the field is varied in each scenario. In SHEAR, nodes transmit sensed data periodically; while for SHPER, incidents are generated at random locations in the field with the frequency that matches the periodic intervals of sensing and transmissions in SHEAR. The radio channel is assumed to be symmetrical and the transmission environment is both conflict and error free, eliminating the need for retransmissions. For brevity of presentation, an average number of transmissions per node over a simulation period of one round of each protocol are plotted.

In the first scenario, wherein the number of nodes is increased to 50, the average number of transmissions in both protocols is increased gradually with an increasing number of nodes, as shown in Fig. 3. However, SHEAR enables fewer transmissions as opposed to the SHPER protocol. Similarly, Figs. 4 and 5 demonstrate the advantage gained in terms of reduced number of transmissions required by SHEAR when the number of nodes is increased to 70 and 90, respectively. Figure 6 presents a comparison of the performance of both the protocols for a WSN with 800 sensor nodes. It is clear from the figure that SHEAR retains its superior performance for networks with a large number of nodes. The percentage improvement in the network performance when using the SHEAR protocol is given in Table 2. For the four aforementioned scenarios, an overall 34 % average network-wide reduction in number of transmissions has been observed.

Fig. 3

Average number of transmissions for 50 nodes

Fig. 4

Average number of transmissions for 70 nodes

Fig. 5

Average number of transmissions for 90 nodes

Fig. 6

Average number of transmissions for 800 nodes

Table 2 Percentage improvement in reduction of average number of transmissions when using SHEAR

Energy consumption

To evaluate the consumption of radio energy in wireless communications, we adopt the widely used first-order radio model (Heinzelman et al. 2000). The energy E _tx consumed by the radio transmitter of a node in one transmission of $b$ bits over a distance d is $E_{tx} \left( {b, d} \right) = E_{elec} \cdot b + E_{amp} \cdot b \cdot d^{2}$, where E _elec is the energy dissipated per bit by the transmitter or receiver circuitry and E _amp is the transmit amplifier energy dissipation per bit per square meter. The energy $E_{rx}$ dissipated by a node in receiving a message of b bits is $E_{rx} \left( b \right) = b \cdot E_{elec}.$ Thus, the total energy dissipated by a node during communication is $E_{total} = N_{t} \cdot E_{tx} + N_{r} \cdot E_{rx}$, where $N_{t}$ is the total number of transmissions, and N _r is the total number of receptions by a node. Using the simulation setup described in the preceding subsection, the energy consumption is evaluated by varying the number of randomly deployed nodes and by repeating the simulations for one round of each protocol. For brevity of presentation, only the network-wide average energy consumption is plotted in all scenarios in this subsection.

In the first scenario, wherein the number of nodes is increased to 50, the average network-wide energy consumption under SHPER and SHEAR protocols is compared in Fig. 7. The figure shows that the energy dissipation is increased gradually under both protocols with an increased number of nodes. Figures 8 and 9 demonstrate the energy efficiency of SHEAR when the number of nodes is increased to 60 and 70, respectively. Again, as the number of nodes is increased, the energy dissipation is increased under both protocols. However, the average energy consumed by the network when using the SHEAR protocol is much lower in all scenarios presented. Figure 10 compares the network-wide energy consumption of both the protocols for a WSN with 600 nodes. It is clear from the figure that SHEAR retains its performance for networks with a large number of sensors. The improvement in the network performance in terms of reduced energy consumption is given in Table 3. For the four aforementioned scenarios, an overall 47 percent average network-wide reduction in the energy consumption has been observed when using SHEAR.

Fig. 7

Energy consumption in a WSN with 50 nodes

Fig. 8

Energy consumption in a WSN with 60 nodes

Fig. 9

Energy consumption in a WSN with 70 nodes

Fig. 10

Energy consumption in a WSN with 600 nodes

Table 3 Percentage improvement in reduction of energy consumption by SHEAR

Number of nodes alive over time

Network lifetime can be quantified in one of several ways depending upon the requirements of a particular WSN application. In some applications, such as intrusion or fire detection, all nodes must remain alive for as long as possible because the network credibility or the quality degrade sharply once a single node has completely depleted its energy. The first-node-dies (FND) metric is used to evaluate a protocol’s performance in such applications. In other applications, the loss of a few nodes does not diminish the quality of the network service. For such applications, the half-nodes-die (HND) metric is used to evaluate a protocol’s performance; whereas the last-node-dies (LND) metric is used to evaluate a protocol’s performance for applications that can fulfill their purpose until the survival of the last sensor node in the network (Senouci et al. 2012).

The impact of SHEAR’s reduced number of transmissions and its low energy consumption, demonstrated in the preceding subsections, is reflected in terms of an improved network lifetime. Simulations in this subsection demonstrate this impact through extensive scenarios, wherein the area of the flat grid is varied from 100 × 100  to 500 × 500 m² and the distance d between the BS and the network field is varied from 100 m to 500 m. All simulations are run until the death of the last node, while the statistics are collected for each of the FND, HND and LND metrics, in order to compare the overall network lifetime achieved by the SHPER and SHEAR protocols.

For the first scenario, when the sensor field size is 100 × 100 m² with d = 100 m and containing 50 randomly deployed sensor nodes, Fig. 11 plots the number of nodes remaining alive over the simulation time. The first node dies after 20 rounds in case of SHPER; whereas, the first node dies after 30 rounds in case of SHEAR. According to the FDN metric, the network lifetime has prolonged in case of the SHEAR as a factor of 10 rounds. It is worth noting that as nodes do not dissipate energy exactly uniformly, the number of nodes remaining alive at any specific time is not a linear function. The nodes consume energy by taking participation in transmission or reception. Therefore, the residual energy of every node is reduced as a function of the number of rounds. The number of nodes remaining alive is decreased in both protocols, as shown in Fig. 11. Nevertheless, SHEAR demonstrates reasonable improvement as an ample number of nodes stay alive.

Fig. 11

Number of nodes alive over time [d = 100 m]

For the second scenario illustrated in Fig. 12, when the field size is 125 × 125 m², the number of nodes is 50 and d is 125 m, the first node dies after 6 rounds in case of SHPER; whereas, the first node dies after 19 rounds in case of SHEAR. Hence, the lifetime of the network has prolonged under SHEAR as a factor of 13 rounds according to the FND metric. Nevertheless, the number of nodes remaining alive decreases in both protocols over the number of rounds as the field size and the distance $d$ are increased. Yet, SHEAR outperforms SHPER since an ample number of nodes stay alive.

Fig. 12

Number of nodes alive over time [d = 125 m]

Similarly, for the third scenario illustrated in Fig. 13, when the sensor field size is 150 × 150 m², the number of nodes is 50 and d is 150 m, the first node dies after 2 rounds in case of SHPER; whereas, the first node dies after 17 rounds in case of SHEAR. Hence the lifetime is prolonging in case of the SHEAR, as opposed to the SHPER, as a factor of 15 rounds. The number of nodes remaining alive is decreased sharply in both the protocols by increasing the distance d and the field size.

Fig. 13

Number of nodes alive over time [d = 150 m]

Figure 14 presents the comparison of both protocols for the network lifetime using a scenario with 500 sensor nodes randomly deployed in the field of size 500 × 500 m² and having the distance d of 500 m. It is clear from the results in Fig. 14 that SHEAR is able to retain its performance and is suitable for sensor networks with heavy load and wide coverage area. For the four aforementioned scenarios, Table 4 shows the percentage of improved performance in terms of the FND, HND, and LND metrics, achieved by the use of SHEAR over SHPER.

Fig. 14

Number of nodes alive over time [500 nodes]

Table 4 Percentage improvement in the average number of nodes alive over time under SHEAR

Discussion

The proposed SHEAR protocol adapts the hierarchical clustering approach of SHPER (Kandris et al. 2009), which enables scalability and power efficiency. In order to further enhance the network lifetime, SHEAR addresses the shortcomings of SHPER, highlighted in "Related work", and makes the following contributions.

Whereas SHPER uses a threshold residual energy of nodes for electing CHs, in SHEAR the CHs are elected based on the maximum local residual energy of the neighboring nodes. This to distribute energy dissipation evenly among all nodes. As in SHPER, the sensor field is divided into high and low levels to ensure scalability since the performance of routing procedure is not affected if the overall network size is increased. However, SHPER follows an indeterminate random procedure to create the high and low levels, which may cause discrepancies in cluster formation and may lead to instability of the clusters. In SHEAR, the nodes are arranged in the ascending order based on their distances from the BS. The half situated close enough to the BS is included in the high-level, whereas the half situated far away from the BS is included in the low-level. As opposed to SHPER, wherein the positions and spatial coordinates of nodes are estimated using the received signal strength, SHEAR uses GPS for the accuracy of localization. Furthermore, SHPER uses threshold based sensing and, as such, is unsuitable for applications that need periodic reports because nodes may not communicate if thresholds are not reached. In SHEAR, nodes transmit sensed data periodically. These enhancements have been detailed in "Cluster setup phase". More importantly, the path selection scheme in SHPER takes into account only the maximum residual energy metric and ignores the total energy consumed along data forwarding paths. This may lead to extremely long routes and subsequently to increased energy consumption. This shortcoming has been addressed by the SHEAR’s path selection scheme presented in "Communication phase". For performance evaluation, we have used a multitude of scenarios with a variety of network sizes and a large number of sensor nodes, unlike SHPER where the network size and the number of sensors are kept fixed at 100 × 100 m² and 100 nodes, respectively.

Thorough study of the simulation results and analyses of the data in Tables 2 through 4 lead us to the inference that the use of SHEAR instead of SHPER has the following implications. SHEAR chooses the shortest paths during the data communication phase and requires minimal communications during the cluster setup phase. This minimizes the communication overhead, as the average number of transmissions per node is much lower in case of SHEAR. An overall 34 % average network-wide reduction in the number of transmissions has been observed, as discussed in "Number of transmissions".

Due to the reduced number of transmissions, the energy of sensor nodes is also conserved. Moreover, through its efficient cluster formation and by selecting widest path for data communication, SHEAR distributed the energy dissipation evenly among clusters. This is demonstrated by the reduced average energy consumption per node in SHEAR, as discussed in "Energy consumption". The energy dissipation is increased gradually under both protocols with the increased number of nodes. However, the average energy consumed by the network when using SHEAR is much lower. An overall 47 % average network-wide reduction in energy consumption has been observed when using SHEAR.

These factors, further contribute towards an overall network lifetime extension under SHEAR. The number of nodes remaining alive at a specific time is not a linear function. When the BS is deployed closer to the sensor field, the average time for the first node depletion is considerably increased in case of SHEAR. The extension, however, diminishes gradually as the distance between the BS and the sensor field is increased. Although, for long distances, there is a marginal extension in the depletion of the first node, the overall lifetime of the network remains reasonably extended in terms of the half and last node depletions. An overall 23 % improvement in the network lifetime has been observed when using SHEAR.

The use of GPS in the proposed SHEAR protocol is aimed at the accuracy of localization. Nevertheless, GPS may be an expensive trade-off and may become an impeding factor in the practical deployment of SHEAR. However, equipping all sensor nodes with a GPS receiver in SHEAR is not required. The cost of the GPS based localization can be reduced considerably by using the well-known Ad-Hoc Localization System (Savvides et al. 2001), whereby a small fraction of nodes use GPS and assist all other nodes in the network to determine their locations terrestrially.

Conclusion

Energy efficiency and scalability are the most important design objectives for WSNs. We have presented a distributed, energy efficient clustering routing protocol with energy aware path selection schemes to improve the lifetime of sensor networks. A key feature of the proposed approach is that cluster heads are elected based on the maximum local residual energy of the neighboring nodes to distribute energy dissipation evenly among all clusters. Based upon this approach, we have introduced the SHEAR protocol that inherits the power efficient and scalable hierarchical topology control of SHPER; and overcomes the weakness of its indeterminate random procedure for dividing the sensor field into upper and lower levels. The energy aware path selection scheme of SHEAR further balances the network-wide energy consumption by finding the least energy cost paths. This is achieved by exploiting relationship between the residual energy of bottleneck nodes present on a path and the total energy consumed along the path. Simulation results demonstrate that SHEAR reduces both the number of transmissions and the energy consumption when compared with one of the best known protocols in the literature and can be very effective in prolonging the network lifetime. Our future work will extend into multilevel hierarchies for the topology control and will consider transmission delay to further enhance network lifetime while overcoming the latency. Scalability analysis for larger scale networks will be another direction for the future work.