1 Introduction

The energy efficient clustering and routing are the challenging research issues in wireless sensor network (WSN) due to low battery life, computational overhead, no conventional addressing scheme, self organization and limited transmission range of sensor nodes. An efficient utilization of sensor battery capacity is needed to increase the life time of the network. Moreover the routing algorithm must select a communication void free route for delivering the sensed data to the base station without any interruption.

Several clustering and routing algorithms are reported so far. The base station (BS) needs the global information about the network for electing cluster heads (CHs) in centralized algorithm [1] which increases routing overhead and time complexity.

In [2] the BS maintains a list of CHs based on the energy. The proposed algorithm decreases the number of packet reception between CHs and cluster members to minimize the energy consumption but not assured to form disjoint clustering which increases the possibility of data loss.

Barolli et al. proposed an intelligent fuzzy-based cluster head selection algorithm in [3]. It uses three input parameters for fuzzy logic control during CH selection. These parameters are cluster-centric distance, remaining energy degree and number of neighbor nodes. It uses compositional rule of inference to infer the output of the system which incurs a high computational cost and a poor response performance.

An energy efficient scheduling for cluster-tree wireless sensor network is proposed in [4]. The cluster is active only once during the schedule period when there are the flows in opposite direction in a wireless sensor network. But the adaptive behavior of the scheduling problem after the addition of new tasks to the original schedule and after the mobility of sensor node or the router is not addressed.

A secure data collection using mobile data collector in cluster wireless sensor networks is proposed in [5]. Tree based sensor key management technique is used for the shared key between the nodes. The proposed clustering schemes have time stamp protocol, polynomial points sharing protocol and secret sharing protocol. But the algorithm introduction complexity is high and efficiency is low.

In efficient routing LEACH protocol [6], the authors have focused on data aggregated by sensor nodes rather than sending to the BS. It selects the CH during set up phase and a new CH is selected in case of failure of an existing CH which makes CH selection algorithm quite complex mainly in case of multiple CH failure.

A cluster based routing algorithm is proposed in [7]. The CH sends the aggregated data to the BS directly if the distance between them is less than a predefined threshold. Otherwise it forwards the aggregated data to the next CH having higher residual energy. But communication void may occur in absence of suitable CH.

In [8] the sensor nodes are deployed non-uniformly in WSN field. The density of node increases towards BS. Hence the data from low node density region may not reach to the BS which leads to spatially unbalanced energy consumption mainly if the width of each region is large.

A centralized routing protocol is proposed in [9]. Each node sends information about its current location and energy level to the BS. The BS determines the cluster and selects a route between clusters for reducing the number of nodes that communicate with it. But the time complexity of cluster formation is very high due to its centralized nature. Moreover the selected route may not be optimal.

A multihop routing protocol is proposed in [10]. It is a distributed clustering based routing protocol. It increases energy efficiency when the network diameter is increased beyond certain level. In set up phase some nodes elect themselves as cluster heads and other nodes associate themselves with elected cluster head to complete cluster formation. The cluster head receives data from all nodes at single-hop and transmits the aggregated data directly to base station or through intermediate cluster head. But communication void may occur when the distance between the cluster head and base station is large.

The present work is a communication void free routing protocol in wireless sensor network. It uses distributed clustering algorithm to form disjoint clusters unlike of [2] in which each node is either a cluster head or a member node that belongs to exactly one cluster. The member nodes in a cluster are able to transmit data to the cluster head or base station. Each cluster head collects the sensed data from the member nodes within its cluster and stores the value of the average aggregated sensed data. A distributed routing algorithm is used to select a route from a source cluster head to base station through intermediate cluster heads or through member nodes in case of communication void. The source cluster head is selected at the time of simulation. It selects the next node towards base station as next forwarder using next forwarder selection algorithm for transferring its sensed data. The next forwarder node repeats the same step till the selected route reaches to base station.

As per the simulation results the proposed distributed clustering algorithm has less execution time than [11] and has less energy consumption than [12]. The equal number of member nodes per cluster causes identical energy consumption of all the cluster heads which helps to improve route stability. Unlike [7, 10] communication void is not occur in the proposed routing algorithm as shown in Sect. 3. Moreover the proposed routing algorithm has less energy consumption than [13], less energy dissipation than [14] and also has less transmission delay than [13] as observed during simulation.

2 Present Work

The distributed clustering algorithm and communication void free routing algorithm are elaborated in this section. The N number of sensor nodes is deployed randomly within a square monitoring field and a base station is placed at the outside of the square monitoring field. The sensor nodes and the base station are all stationary after deployment. All sensor nodes are homogeneous in nature and have the same initial energy. The WSN field after random deployment of 100 sensors is shown in Fig. 1.

2.1 Clustering Algorithm

It is the combination of cluster head selection algorithm and cluster member selection algorithm.

Fig. 1
figure 1

WSN field after deployment of sensor nodes. Blue astric sensor nodes. (Color figure online)

Full size image

2.1.1 Cluster Head Selection Algorithm

This algorithm is elaborated for the selection of ith cluster head \((\hbox {CH}_{\mathrm{i}})\). T is a set of all sensor nodes (N) deployed in WSN field. A prediction value (P, \(0\le \hbox {P}\le 1\)) is chosen for selecting the cluster head and a random number (R, \(0\le \hbox {R}\le 1\)) is generated for each element in T. Let \(\hbox {R}_{\mathrm{i}}\) is the random number which is generated for ith element in T. If \(\hbox {R}_{\mathrm{i}}\le \hbox {P}\) (assumption), \(\hbox {CH}_{\mathrm{i}}\) is selected as a cluster head and is added in a set (CH). So \(\hbox {CH}=\{\hbox {CH}_{\mathrm{i}}\}\). The algorithm repeats the same steps of operation for all the elements in T. Let NO_OF_CH is the number of cluster head and NO_OF_NCH (N-NO_OF_CH) is the number of non cluster head. The result of 4 sensor nodes as an example output of this algorithm is shown in tabular form (Table 1). The WSN field after the execution of cluster head selection algorithm is shown in Fig. 2. It can be observed from Table 1 that the sensor nodes 1 and 4 are selected as cluster head.

Fig. 2
figure 2

WSN field after the execution of cluster head selection algorithm. Blue astric Sensor node. Red astric Cluster head of clustering sensor node. (Color figure online)

Full size image
Table 1 Example output of cluster head selection algorithm
Full size table

2.1.2 Cluster Member Selection Algorithm

The function of this algorithm at \(\hbox {CH}_{\mathrm{i}}\) is elaborated in this section. It calculates the maximum possible number of member nodes per cluster \((\hbox {CM}_{\mathrm{max}})\) as \(\lceil \)(number of non cluster head/total number of cluster heads)\(\rceil \) and broadcasts message to know the position of its neighbors. The algorithm at \(\hbox {CH}_{\mathrm{i}}\) calculates its distance \((\hbox {Dist}_{\mathrm{ij}})\) from jth node \((\hbox {N}_{\mathrm{j}}, 1\le \hbox {j}\le \hbox {NO}\_\hbox {OF}\_\hbox {NCH})\) as \(\surd (\hbox {y}_{\mathrm{i}}- \hbox {y}_{\mathrm{j}})^{2}+(\hbox {x}_{\mathrm{i}}- \hbox {x}_{\mathrm{j}})^{2}\) where \((\hbox {x}_{\mathrm{i}}, \hbox {y}_{\mathrm{i}})\) is the coordinate of \(\hbox {CH}_{\mathrm{i}}\) and \((\hbox {x}_{\mathrm{j}}, \hbox {y}_{\mathrm{j}})\) is the coordinate of \(\hbox {N}_{\mathrm{j}}\). If \(\hbox {Dist}_{\mathrm{ij}}\le 2\hbox {RR}\), where RR is the radio range of each sensor node, \(\hbox {N}_{\mathrm{j}}\) is selected as a member node under \(\hbox {CH}_{\mathrm{i}}\) and the algorithm inserts \(\hbox {N}_{\mathrm{j}}\) in a set (\(\hbox {Cluster}\_\hbox {Member}_{\mathrm{i}})\). The algorithm at \(\hbox {CH}_{\mathrm{i}}\) repeats these steps of operation till the number of elements in \(\hbox {Cluster}\_\hbox {Member}_{\mathrm{i}}\) is \(\hbox {CM}_{\mathrm{max}}\). The WSN field after the execution of the cluster member selection algorithm is shown in Fig. 3.

Fig. 3
figure 3

WSN field after the execution of the cluster member selection algorithm. Blue astric Sensor node. Red astric Cluster head of clustering sensor node. (Color figure online)

Full size image

2.2 Routing Algorithm

The routing algorithm is used to select a route from a source cluster head to base station through intermediate cluster heads or member nodes (in case of communication void) in WSN field. The source cluster head is selected at the time of simulation. It selects the next node towards base station as next forwarder using next forwarder selection algorithm for transferring its sensed data. The selected next forwarder may be another cluster head which is the neighbor of source cluster head or may be a member node in the cluster associated with the source cluster head. The next forwarder selected by the source cluster head becomes the member of the route and it repeats the same steps of operation to select the next forwarder as the next member of the same route. This process will continue till the route reaches to the base station. Hence the routing algorithm is the combination of a few next forwarder selection algorithm which are executed by the cluster heads or member nodes to establish the route.

2.2.1 Next Forwarder Selection Algorithm

The function of this algorithm is elaborated considering \(\hbox {CH}_{\mathrm{i}}\) as source cluster head. \(\hbox {CH}_{\mathrm{i}}\) broadcasts a “hello” message within its radio range for its neighbor cluster heads. In response the neighbor cluster heads send an acknowledgement message to \(\hbox {CH}_{\mathrm{i}}\). Let \(\hbox {CH}_{\mathrm{i}}\) receives an acknowledgement message in the form \((\hbox {CH}_{\mathrm{k}}, \hbox {E}_{\mathrm{k}}, \hbox {Numlink}_{\mathrm{k}})\). In this message \(\hbox {CH}_{\mathrm{k}}\) (\(\hbox {kth}\) cluster head, \(1\le \hbox {k}\le \hbox {NO}\_\hbox {OF}\_\hbox {CH}-1\)) is the neighbor of cluster head \(\hbox {CH}_{\mathrm{i}}\), \(\hbox {E}_{\mathrm{k}}\) is the existing battery power of \(\hbox {CH}_{\mathrm{k}}\), \(\hbox {Numlink}_{\mathrm{k}}\) is the number of neighbor cluster heads of \(\hbox {CH}_{\mathrm{k}}\). \(\hbox {CH}_{\mathrm{i}}\) compares \(\hbox {E}_{\mathrm{k}}\) with a predefined threshold charge (T_CH). If \(\hbox {E}_{\mathrm{k}}\) is greater than T_CH \(\hbox {CH}_{\mathrm{i}}\) adds \(\hbox {CH}_{\mathrm{k}}\) in a set \((\hbox {Next}\_\hbox {forward}_{\mathrm{i}})\). Otherwise \(\hbox {CH}_{\mathrm{i}}\) ignores \(\hbox {CH}_{\mathrm{k}}\). \(\hbox {CH}_{\mathrm{i}}\) repeats the same steps of operation for all the received acknowledgement messages from its neighbors. In the worst case the number of neighbor cluster heads of \(\hbox {CH}_{\mathrm{i}}\) is (NO_OF_CH-1). Hence the maximum possible number of acknowledgement message received by \(\hbox {CH}_{\mathrm{i}}\) is (NO_OF_CH-1). \(\hbox {CH}_{\mathrm{i}}\) arranges the elements of \(\hbox {Next}\_\hbox {forward}_{\mathrm{i}}\) in the ascending order of their Numlink value as obtained from their acknowledgement messages and selects the cluster head having the minimum Numlink value as next forwarder to minimize energy consumption. \(\hbox {CH}_{\mathrm{i}}\) sends the average aggregated sensed data to the selected next forwarder. The next forwarder computes the new average aggregated sensed data considering its own sensed data and the received data from \(\hbox {CH}_{\mathrm{i}}\).

If the number of elements in \(\hbox {Next}\_\hbox {forward}_{\mathrm{i}}\) is 0 or the Numlink value of all the elements in \(\hbox {Next}\_\hbox {forward}_{\mathrm{i}}\) is 0 communication void occurs in WSN field. \(\hbox {CH}_{\mathrm{i}}\) searches for a member node from its cluster which is nearest to the base station. The member node of \(\hbox {CH}_{\mathrm{i}}\) having maximum X-coordinate value is such a node. \(\hbox {CH}_{\mathrm{i}}\) sends its average aggregated sensed data to the selected member node. The selected member node sends the received data of \(\hbox {CH}_{\mathrm{i}}\) to the base station if its distance from base station is less than equal to 2RR. Otherwise it triggers the next forwarder selection algorithm.

3 Simulation

The performance of the proposed algorithm is evaluated using MATLAB 9.0 in a WSN field of size (\(100 \times 100\)) \(\hbox {m}^{2}\). The simulation experiment is conducted in presence of 100 number of sensor nodes. The coordinate of the base station is (101, 101), the transmission range of nodes (RR) is assumed as 10 m and the value of T_CH is assumed as 25J. The number of cluster heads in the WSN field varies for different values of P. The plot of the number of cluster heads vs. P is shown in Fig. 4. It can be observed from Fig. 4 that the number of cluster heads in WSN field increases with the value of P. The possibility of communication void occurrence increases with the reduction in the number of cluster head. The reduction in the number of cluster head also increases \(\hbox {CM}_{\mathrm{max}}\) which in turn increases the time complexity and energy consumption of cluster member selection algorithm. However the number of neighbors per cluster head increases with the increase in the number of cluster heads in WSN field which causes an increase in the number of hello and acknowledgement messages. Hence the complexity of next forwarder selection algorithm increases with the increase in the number of cluster heads. Hence it needs to vary the number of cluster heads in WSN field by varying P to achieve the optimal performance of the proposed scheme.

3.1 Performance of Clustering Algorithm

The performance of the proposed clustering algorithm is evaluated on the basis of the execution time of clustering algorithm and energy consumption. Both the execution time and energy consumption of the clustering algorithm depend upon the number of cluster heads in the WSN field.

Fig. 4
figure 4

Number of cluster heads vs. P

Full size image

3.1.1 Measurement of Execution Time

The execution time of clustering algorithm is the summation of the execution time of cluster head selection algorithm and cluster member selection algorithm. The plot of execution time of clustering algorithm vs. the number of cluster head is shown in Fig. 5. The increase in the number of cluster head reduces the number of non cluster heads and the value of \(\hbox {CM}_{\mathrm{max}}\) which causes reduction in time complexity of the cluster member selection algorithm due to distance calculation. Hence the execution time reduces with the increase in the number of cluster heads. It can be observed from Fig. 5 that the maximum execution time of clustering algorithm in the proposed scheme is 0.017 s whereas it is fixed to 5.5 s in [11].

Fig. 5
figure 5

Time of execution vs. Number of cluster head

Full size image

3.1.2 Measurement of Energy Consumption

The energy consumption during clustering is due to the computation of distance for member selection by cluster member selection algorithm. The plot of energy consumption vs. number of cluster heads is shown in Fig. 6. It can be observed from Fig. 6 that the energy consumption increases with the number of cluster heads. Each cluster head executes the cluster member selection algorithm independently. Hence the increase in the number of cluster heads increases energy consumption but it is less than the energy consumption in [12] as observed from Fig. 6.

Fig. 6
figure 6

Energy consumption vs. Number of cluster heads

Full size image
Fig. 7
figure 7

Data analysis for clustering algorithm

Full size image

3.1.3 Data Analysis for Clustering Algorithm

The data analysis of clustering algorithm for 10 number of sensor nodes are shown in Fig. 7. The data1 at the top of Fig. 7 represents the sensed value of 11 number of sensor nodes (including base station) which are deployed in WSN field. The CH, MCH, CHX, CHY, MCHX, MCHY, DIST, VALUE_CH, VALUE_MCH at the middle of Fig. 7 represent the identification of the cluster head (1), identification of the member nodes of cluster head number 1 (5, 6, 8), X-coordinate of cluster head, Y-coordinate of cluster head, X-coordinate of member nodes, Y-coordinate of member nodes, distance between cluster head and member nodes, sensed value of cluster head, sensed value of member nodes respectively. The CLUSTER HEAD, CHX, CHY, AVERAGE AGGREGATED VALUE at the bottom of Fig. 7 represent the nodes which are selected as cluster heads (1,2,3,4,7,9,10,11), X-coordinate of the selected cluster heads, Y-coordinate of the selected cluster heads, average aggregated value of the selected cluster heads respectively. For example, the average aggregated value at cluster head number 1 is computed as (sensed value of cluster head 1\(+\) sensed value of member node 5\(+\) sensed value of member node 6\(+\) sensed value of member node 8)/4. The time required for clustering and computation of average aggregated value is evaluated as 0.058781 sec as observed from Fig. 7.

3.2 Performance of Routing Algorithm

The performance of the proposed routing algorithm is evaluated on the basis of energy consumption and transmission delay after every 1 s of simulation. The performance of the routing algorithm is also studied on the basis of energy dissipation versus the life time of the network.

3.2.1 Measurement of Energy Consumption

The energy consumption while route selection is due to the transmission of hello messages and reception of acknowledgement messages for next forwarder selection. The size of these messages is assumed as 100 bytes [13]. The energy consumption is computed as the product of voltage (V), current (I) and time (t). As per the data sheet of tmote sky [15] V \(=\) 3.6 V, I \(=\) 0.02  amp for transmission and 0.023 amp for reception. The transmission time and reception time (t) of 100 byte message at a rate 250 kbps (as per IEEE 802.15.4 standard) is 3.1 ms. Hence the energy consumption due to the transmission and reception of 100 byte is 0.234 mJ and 0.256 mJ respectively. The plot of energy consumption versus time interval is shown in Fig. 8. The energy consumption to select an optimal route is the sum of energy consumption of all the nodes (cluster heads or member nodes in case of communication void) which are associated with the selected route. It can be observed from Fig. 8 that the energy consumption is almost negligible in the present scheme than [13].

Fig. 8
figure 8

Energy consumption vs. Time interval

Full size image

3.2.2 Measurement of Energy Dissipation

A cluster head sends hello message to all its neighbors at the time of next forwarder selection and receives acknowledgement message from all these neighbors. But only one neighbor is selected as next forwarder. Hence the wastage of energy or energy dissipation occurs due to the exchange of extra hello and acknowledgement messages. The plot of cumulative energy dissipation versus life time of the network (\(\uptau \)) in sec is shown in Fig. 9. It can be observed from Fig. 9 that the energy dissipation increases with \(\uptau \) but it is less than [14].

Fig. 9
figure 9

Energy dissipation vs. \(\uptau \)

Full size image

3.2.3 Measurement of Transmission Delay

The transmission delay is the time required to send the average aggregated value from the source cluster head to the base station through the selected route. The plot of transmission delay versus time interval is shown in Fig. 10. It can be observed from Fig. 10 that the transmission delay increases slowly with time due to the increase of the size of aggregated data but it is less than [13].

Fig. 10
figure 10

Transmission delay vs. Time interval

Full size image

3.2.4 Data Analysis for Routing Algorithm

The data analysis of routing algorithm without communication void for (\(50 \times 50\)) \(\hbox {m}^{2}\) WSN field having 100 sensor nodes is shown in Fig. 11. The identification of base station is 101.

Fig. 11
figure 11

Data analysis of routing algorithm without communication void

Full size image

The CLUSTER HEAD, CHX, CHY, AGGREGATED VALUE at the top of Fig. 11 represent the identification of the cluster heads, X-coordinate of cluster heads, Y-coordinate of cluster heads, average aggregated value of the cluster heads respectively. The cluster head 18 is selected as the source cluster head as observed from the lower part of Fig. 11. The selected route passes through the cluster heads 18, 13, 14, 1, 15, 17, 27, 101 as observed under route in Fig. 11. The X-coordinate and Y-coordinate of the cluster heads associated with the selected route are shown at the left bottom corner in Fig. 11. The selected route is shown graphically at the right bottom corner in Fig. 11. The X-axis and Y-axis of this graph are the X-coordinate and Y-coordinate of the cluster heads associated with the selected route.

Fig. 12
figure 12

Data analysis of routing algorithm with communication void

Full size image

The data analysis of the routing algorithm with communication void for (\(20\times 20\)) \(\hbox {m}^{2}\) WSN field having 30 sensor nodes is shown in Fig. 12. The identification of base station is 31. As observed from the middle part of Fig. 12 the cluster head 23 is selected as the source cluster head and the cluster head 2 is selected as the next forwarder by cluster head 23. The cluster head 2 finds communication void while executing next forwarder selection algorithm and it selects member node 1 as next forwarder due to its highest value of X-coordinate (14.619778) than the other member nodes (5, 6) of cluster head 2 as observed from the top of Fig. 12. The X-coordinate of the base station (cluster head 31) is 21. Hence the member node 1 sends the aggregated data to the base station (node id 31) directly as the distance among them is less than equal to 2*RR. The communication void free route passes through the cluster head 23, cluster head 2, member node 1 of cluster head 2 and base station as observed under route in Fig. 12. The graphical representation of the selected route is shown at the right bottom corner of Fig. 12 as shown in Fig. 11.

3.3 Performance Analysis of Clustering and Routing Algorithm

The performance of the combined clustering and routing algorithm is evaluated on the basis of energy consumption (total energy consumption) and delay (total delay).

3.3.1 Measurement of Total Energy Consumption

It is the sum of energy consumption due to the execution of clustering and routing algorithm. The plot of total energy consumption versus the number of cluster heads is shown in Fig. 13.

Fig. 13
figure 13

Total energy consumption vs. Number of cluster heads

Full size image
Fig. 14
figure 14

Total delay vs. Number of cluster heads

Full size image

3.3.2 Measurement of Total Delay

It is the sum of delay due to the execution of clustering and routing algorithm. The plot of total delay versus the number of cluster heads is shown in Fig. 14.

3.3.3 Discussion of Result

When the number of cluster head increases, number of non cluster head reduces which causes reduction in time complexity of cluster member selection algorithm which in turn reduces energy consumption and delay during clustering. But the increase in the number of cluster head increases the number of neighbors per cluster head. Hence the number of message exchange (hello and acknowledgement message) at the time of next forwarder selection increases which in turn increases the energy consumption and delay.

4 Conclusion

An energy efficient communication void free routing algorithm is proposed in the present work. The proposed clustering algorithm and routing algorithm perform well in terms of energy consumption, energy dissipation, execution time and transmission delay than the existing algorithms. The performance of the proposed scheme may be studied by varying the number of sensor nodes and T_CH. The multilevel clustering may be included for better efficiency.