1 Introduction

Wireless Sensor Networks (WSN) is an energy-constrained, low-cost wireless nodes, typically called a mote, comprising sensing, computation and communication elements and occasionally location tracking element, in the form of a Global Positioning System (GPS). A wireless node (WN) is used for measuring physical or behavioural patterns from the environment under observation. The physical or behavioural quantity measured depends on the type of sensing element/s embedded into the WN which include, but are not limited to mechanical-, optical-, magnetic-, electromagnetic-, chemical-, thermal-, biological- and acoustic- sensors for measurands like pressure, temperature, humidity, flow, position, velocity, acceleration, proximity, distance, position and biological agents. Typical applications of WSN include, but are not limited to air-traffic control, biological monitoring, control of temperature, disaster management, home and industrial automation, localisation, mobile robotics, process control, traffic flow and surveillance, volcanic eruptions and weather monitoring [1].

As far as routing strategies are concerned, they can be broadly classified into three different categories, namely; proactive, reactive and hybrid strategies. Under the proactive category, there is a periodic dissemination of information across sensor nodes. This strategy does not require maintenance of costly routing information in sensor nodes. Under the reactive category, the calculation regarding which next node needs to be sent the data is decided on-demand, dynamically. Under the hybrid category, proactive routing is used within the cluster and reactive routing is used for sending data and control information among the cluster heads.

There are yet another classification criteria on the basis of which this paper is organised. The first among this classification is data-centric routing. Here, a query is issued by the sink node for the information of a specific attribute of importance rather than issuing the query against a single node (called the address-based routing). The second classification criterion is that of hierarchical routing. Here, data is transmitted from the sensing node to the data forwarding node towards the sink node. A single node is responsible for allowing transit data from a number of nodes. The third among this category is location based routing. In this, the location information of individual node is taken into consideration for deciding the next node to which data has to be forwarded.

In this paper, we will be simulating the behaviour of four routing algorithms; namely 1-D Flooding, 2-D Flooding, Spanning Tree and angle-based dynamic path construction (ADPC). 1-D and 2-D Flooding belong to the category of flat routing while Spanning Tree belongs to the category of hierarchical routing and ADPC belongs to location-based routing. Spanning Tree performs data aggregation, in addition to simply routing, to reduce the data traffic at the sink node/s. Typically, data compression is performed.

Re-transmission probability is a very important network criterion. It decides whether the data a node has received needs to be re-forwarded to the next node or not. This is especially important for introducing a reliability factor into the network. Higher the value of the retransmission probability, greater will be the reliability of the network. It also has a degrading effect on the amount of energy consumption. It is observed that there is less loss of data due to the size of data in WSN and more loss due to the unreliability inherent due to the wireless nature of the network, there is a need to mitigate this effect. This is overcome by incorporating node to node error recovery rather than an end-to-end error recovery. The assumption made here is: if the packet error rate is ‘p’ across a single link, then, the successful delivery of data across a single link is (1−p) and (1−p)n consecutively across ‘n’ number of hops. If we consider that error recovery is computed end-to-end, then a single error may get propagated through the entire duration of communication and hence rise exponentially. To prevent this, it is imperative that error recovery routine be run across every hop through which data passes. During the simulation, the pre-set re-transmission probability is checked against a randomly generated number. Only when its value is greater than the randomly generated number, the data is re-forwarded to the next node. The main concept behind this is that if the value of this probability is higher, then there is more chance of error free arrival of data in case of an unreliable link.

The rest of the paper is organised as follows. In Sect. 2, we discuss the present research carried out in the field of aforementioned routing algorithms; namely 1-D Flooding, 2-D Flooding, spanning tree and ADPC. In Sect. 3, we present the working of algorithms considered in this paper for the deterministic as well as random deployment strategies. In Sect. 4, we illustrate their simulation and obtain the corresponding results. Section 5 concludes the paper.

2 Related Work

In the case of flat-based routing, there is a pre-defined flow of data from the source to the sink node. The data is forwarded from the source node en route to all the neighbouring nodes. However, there can be excessive traffic at times because of the unnecessary flow of data from one node to the other. There are some major drawbacks that flooding experiences [1]. The most common is traffic implosion according to which the same data or control packets are sent to the nodes repeatedly. The second problem with flooding is that of overlapping. Here, since there can be many nodes concentrated over a single region, they measure the same value of interest and disseminate this redundant information over neighbouring nodes. Resource blindness is also a reason that can introduce unpredictable delays in the network. There are many different ways in which these three problems can be avoided. One such remedy is Gossiping. Contrary to the case of flooding where data and control packets are transferred to all the neighbours, gossiping transfers data to only one randomly selected neighbour and not to all the neighbours. Literature [2] suggests decreasing the flooding attack on the network by proposing an analytical, stochastic modelling of the challenge-based broadcasting in Carrier Sense Multiple-Access with Collision Avoidance (CSMA/CD). It models a non-stationary network by the initial issuance of the request by a recursive method and tries to find the broadcaster’s approximate payoff. The same article also investigates the case where the sender is considered as a malicious node with abnormally high transmission and reception ranges. In [3], an approximation algorithm called MAX-secure flooding in WSN with neighbourhood keys (SFNK) comes out with a novel technique to show how 100% network coverage can be obtained by reducing packet transmissions per node to be 0.75. It makes out a comparison with the original SFNK algorithm which, in the same paper has been proved to be NP-Hard in nature. The simulation result for execution time shows that it takes less than 1 second to select a set of keys for optimal flooding. Similar work [4] compares flooding with clock speed agreement (FCFA), which forces all the nodes to run at the same time, along with flooding time synchronization protocol (FTSP) that makes use of slow flooding, PulseSync that employs rapid flooding and gradient time synchronisation protocol (GTSP). The basic issue discussed here is to reduce the abnormal effect of slow synchronisation by changing the propagation speed of the data disseminated during the process of flooding. A low-duty cycle, reliable flooding scheme called dynamic switching-based reliable flooding (DSRF) [5], explores both good links and bad links for carrying out the decision for packet forwarding against a normal flooding protocol. Here, there are 12–25 number of packet transmissions and 10–15% reduction in flooding delay as compared to normal flooding. Performance benefits obtained is very much close to the theoretical lower bound.

As discussed earlier, the second category of routing protocol is the hierarchical routing. Under this category, we can have spanning tree, connected dominating set (CDS) and low-energy adaptive clustering hierarchy (LEACH) as the data transmission framework. However, in this paper, we focus on spanning tree only. In a spanning tree based WSN infrastructure, there is a categorisation of nodes into sensing nodes and communicating nodes and the sink node is located at the root of the tree. Data routing takes place from the sensing node through the intermediary transit nodes towards the sink node. As we move up in the tree, the energy consumption of nodes also increases as the transit data being carried increases upwards. Hence, there is a need of non-uniform allocation of initial energy to nodes; sink node being the one with the maximum initial energy. During the course of data transmission, data aggregation can also take place. A distributed algorithm for the construction of an approximate minimum spanning tree (MST), called the nearest neighbour tree is provided in [6] whose construction requires much less energy asymptotically than a conventionally distributed MST. The radius of the neighbourhood is considered to be \(1.6\sqrt {\frac{\ln \left( n \right)}{n}}\), which is the least required for getting a connected network. A new method is proposed for the construction of an MST using LEACH, in which nodes are initially added to the clusters on the basis of minimum distances among the nodes [7]. Continuous balancing of the nodes needs to be done which is accomplished using AVL algorithm. A technique to reduce the occurrence of global reconstruction of spanning tree, backup path needs to be used. It presents a dynamic prediction model to estimate the possibility of node failure. Hence, the backup node increases the network lifetime [8]. Similar researches calculate the spanning tree of the network by considering the competitiveness function (CF) of each and every node. It assumes that nodes with higher value of CF have got more chances of getting allocated the resources and participating in the construction of MST. Simulation results show improvement in lifetime under such architectures [9]. Spanning multi-tree (SMT) algorithm with multi-sink nodes is illustrated in [10], which comes up with three different algorithms; namely largest-traffic-first (LTF), smallest-extensibility-first (SEF), smallest-extensibility-first-smallest-potentially-first (SEF-SPS) to balance the total traffic around sink adjacent nodes (SAN) and gives the best load balancing performance.

The third category of routing is location-based routing. In this case, we need information about the address of individual nodes in order to transmit data to the node nearest to the transmitting node. A comparative analysis of single path routing (SPR) with angle-based dynamic path construction (ADPC) confirms that ADPC outperforms SPR [11]. In ADPC, the set of neighbouring nodes is reduced to a limited number by choosing a routing angle that best determines the next neighbour to be selected. From this set of minimal number of nodes, a node which is nearest to the sink node is chosen. In the case where sensor nodes are mobile while the sink node is stationary, angle-based dynamic source routing (ADSR) [12] broadcasts the route request (RREQ) message to all the neighbouring nodes. All the neighbouring nodes whose angle with the sink node and sender node is less than the pre-defined threshold value of the routing angle, re-broadcast the packet; otherwise discards the RREQ message. Simulation comparison of ADSR with DSR shows performance benefits on overhead, data delivery and end-to-end delay. In similar works, intra-cluster multi-hop routing finds a path between an intra-cluster node and the cluster head [13]. Data is transferred from the source node to the intermediate node only when the angle created by the intermediate node to the cluster head and source node is greater than a pre-determined forwarding restriction angle. Space angle based energy-aware routing defines the routing in the three dimensional space [14]. The algorithm is based on the selection of a set of candidate nodes, determination of space angle, computation of transmission energy consumption and determining the node of next step.

3 Routing Protocols

The article discusses four different routing protocols; namely 1-D flooding and 2-D flooding (both belonging to flat routing), spanning tree (hierarchical routing) and Angle-Based Routing (location-based routing) for both random as well as deterministic deployment of nodes. In 1-D as well as 2-D flooding, each and every node is given a unique id, called radio frequency identification (RFID). In 1-D flooding (both random and deterministic), data is always transferred from a node which has unique id one more than the previous node. Thus, data is always transferred in a sequential manner from preceding node to the succeeding one. The node with the lowest RFID is considered to be the source node initiating the communication and node with the largest RFID is considered to be the sink node. In the case of 2-D flooding, data is always sent from a node to all the neighbouring nodes. Once communication starts, data reaches sink node via a number of intermediate nodes. In the case of spanning tree, there is a division of nodes into two categories; sensing nodes and communicating nodes. All the leaf nodes are considered to be the sensing nodes and all the non-leaf nodes as communicating nodes, with the parent node bearing the exception of sink node. Communication is always initiated by the sink node. The sink node issues queries to the sensing nodes and; sensing nodes, in response, furnish the relevant data. For Angle-Based Routing, initially on the basis of the transmission radius, a limited set of nodes are determined out of which, a minimal set of nodes are found out which takes the data closer to the sink node. From this set, further filtration is carried out on the basis of routing angle. Selection of this routing angle is always an optimisation decision [11].

4 System Design

The system is modelled as a disk graph which is a type of Intersection Graph [15]. In this setup, two nodes are adjacent to each other if they are within their transmission ranges. The nodes are modelled as vertices of the graph and edges are modelled as the interconnections among them. In the deterministic deployment case, we adopt the grid deployment strategy. The random deployment adopts the standard algorithm for random co-ordinate selection. The nodes under this deployment area are assumed to form a convex set, since Euclidean distance is used to find the distance among nodes and not the Toroidal distance. Once nodes are deployed under either of the deployment strategies, interconnections among them are established by transmission range assignment (TRA) problem [16]. Using TRA, we calculate the minimum Transmission Range which is required to get a connected network. According to [16], in order to get a minimum node degree of at least 1, the formulation is given by:

$$r_{0} \ge \sqrt {\frac{{ - \ln \left( {1 - p^{{{\raise0.7ex\hbox{$1$} \!\mathord{\left/ {\vphantom {1 n}}\right.\kern-0pt} \!\lower0.7ex\hbox{$n$}}}} } \right)}}{\rho \varPi }}$$
(1)

The value of probability is assumed to be >99% in all the cases, denoted by the letter ‘p’ in the above equation. Such high value of probability is attributed to the Border Effect caused by the restricted deployment area. It is due to this reason that we cannot guarantee a connected network even with such high probability. The network topology is constructed in a square Region of interest (RoI) on which simulation of the considered routing protocols are conducted and analysed. Simulation parameters are given in Table 1.

Table 1 Simulation parameters
Full size table

The simulation works on two different optimisation criteria: energy consumption and end-to-end delay. The energy consumption considers three different models; namely the sensor energy model, the transceiver energy model and the computation energy model. However, we only consider transceiver energy model since it consumes the maximum amount of energy. Also, within this model, energy consumption in the idle state, during channel request, due to transmission and reception and due to the reception of collided packets is considered. The energy is computed according to  [17]:

$$\mathop \sum \limits_{i = 1}^{{N_{TX} }} \frac{{V_{tr} \cdot I_{TX} \cdot L_{i} }}{R} + \mathop \sum \limits_{i = 1}^{{N_{RX} }} \frac{{V_{tr} \cdot I_{RX} \cdot L_{i} }}{R} + V_{tr} \left( {I_{idle - check} \cdot T_{idle - check} + I_{request} \cdot T_{request} } \right)$$
(2)

where, \(N_{TX}\) is the total number of transmissions, \(N_{RX}\) is the total number of receptions, \(V_{tr}\) is the working voltage, R is the transmission rate, \(L_{i}\) is the size of data packet in bits, \(P_{idle - check}\) is the power required to check whether channel is idle, \(T_{idle - check}\) is the time required to check whether channel is idle, \(P_{request}\) is the power required to request the channel and \(T_{request}\) is the time required to request the channel. The typical values of energy parameters are given in Table 2.

Table 2 Energy parameters
Full size table

The second optimisation criterion is end-to-end delay (settling time); the time communication starts from the source node to the time when data is received by the sink node. After every successful communication termination, settling time is computed.

Prowler is used for simulation purposes which is an event-based probabilistic simulator designed for Berkeley mica hardware platform running applications which are built on TinyOS [18]. The simulator consists of three different modules; namely, radio model, application and prowler. The simulator is built on MATLAB platform. The MAC layer is implemented using carrier sense multiple access (CSMA). Radio propagation model represents ideal channel attenuation.

5 Simulation Results

The considered Region of Interest is a 2-D square area of deployment chosen according to the simulation parameters specified in Table 1. The nodes are deployed randomly or deterministically. Also, we need to find the re-transmission probability which needs to be set for all the four protocols at which minimum value of energy consumption and settling time is achieved. The two employed optimisation criteria on two different topologies are given in Table 3.

Table 3 Matrix showing optimisation criteria and topologies
Full size table

According to Table 3, firstly we analyse the impact of re-transmission probabilities (RPs) on the topologies by ranging it from 0.0 to 1.0 in steps of + 0.25 for number of nodes set to 100 for all the four algorithms discussed previously. Plots of variance in energy depletion for change in re-transmission probabilities against the four different routing algorithms is shown in Fig. 1a, b respectively for random and uniform deployment topologies. From the result depicted in the figure, it is evident that all the algorithms converge with the least value of variance at the value of probability p = 0.5 for both random as well as deterministic deployment strategies. It can be inferred that at low re-transmission probability, the reliability of the network is low and the rate of collision among the packets increases. However, when its value is more, there may be unnecessary transmission of packets, hence consuming more energy. Therefore, we obtain minimum variance at an optimal value of RP = 0.5. Figure 2a, b gives the plot of settling time against RP further supporting the value of RP = 0.5 in this case also. We thereby set the value of RP to 0.5 for both energy consumption and settling time for further analysis and experimentation of the four routing algorithms.

Fig. 1
figure 1

a Variance in energy consumption for random deployment of nodes (number of nodes = 100). b Variance in energy consumption for uniform deployment of nodes (number of nodes = 100)

Full size image
Fig. 2
figure 2

a Variance in settling time for uniform deployment of nodes (number of nodes = 100). b Variance in settling time for random deployment of nodes (number of nodes = 100)

Full size image

For a constant value of RP for both random and uniform grid deployment of nodes, we perform a comparative analysis of all the algorithms. A series of 50 independent simulations help us analyse the performance of the routing algorithms in context to scalability of the network. The node density is thereby varied as [5, 10,15, 35, 50, 75, 100, 125, 150, 175, 200]. Figure 3a, b depict the corresponding energy consumption statistics while Fig. 4a, b present the results for settling time.

Fig. 3
figure 3

a Average energy consumption under uniform deployment (after 50 independent simulations). b Average energy consumption under random deployment (after 50 independent simulations)

Full size image
Fig. 4
figure 4

a Average settling time under uniform deployment (after 50 independent simulations). b Average settling time under random deployment (after 50 independent simulations)

Full size image

As obvious from Fig. 3a, 2-D flooding consumes the most amount of energy as data is disseminated to all the neighbouring nodes in the uniform deployment of nodes. In Fig. 3b, this effect is shown by 1-D flooding because data is always forwarded to a node having higher node id than the preceding node. In the case of random deployment on nodes, the position of nodes cannot be controlled in accordance with their IDs. Angle-based dynamic path construction (ADPC) performs the best as far as conservation of energy is concerned in both random as well as deterministic deployment strategies. Also, the rate of increase in energy consumption is more in 1-D flooding and 2-D flooding than the other two algorithms. In case of settling time, given in Fig. 4a, b, the simulation results show that in the case of uniform deployment, the settling time of 2-D flooding is maximum. This is because, due to flooding in the network, congestion arises and the succeeding packets are dropped leading to re-transmissions until error free delivery of data. On the other hand, settling time is the highest in 1-D flooding in random deployment due to the random placement of nodes but data is always routed in a pre-defined order in 1-D flooding.

6 Conclusion

This article presents a comparative analysis on the scalability of network under different protocols; namely 1-D flooding, 2-D flooding, spanning tree and angle-based dynamic path construction. We have initially considered the variance in energy consumption and settling time for which we are getting the least value of re-transmission probability. In our case, this value is fixed at 0.5 according to the data obtained by the simulation results. It is found out that ADPC performs in the most optimal manner for both energy consumption and settling time as compared to the other algorithms irrespective of the network density.

Also, heterogeneity of nodes in terms of initial assignment of energy, called transmission range assignment, affects the uniform consumption of energy. As an extension to this paper, we consider mobile nodes which can move across different places within the area of interest. In a subsequent paper, we also try to analyse the effect of topology maintenance on energy depletion and settling time, specifically for the case of location-based routing.