A congestion aware routing for lifetime improving in grid-based sensor networks

Abstract

Wireless sensor networks (WSNs) consist of a large number of tiny, low cost, memory/computational constraint, battery-operated sensor nodes deployed randomly in two (or three) dimensional plane. Due to limited amount of energy in sensors, the network seeks to attain energy efficient routing for prolonging their lifetime. Existing grid based routing protocols reduce the energy dissipation at nodes, however they suffer from congestion. Network congestion may lead to excessive energy consumption, which in turn minimizes the lifetime of network. In this paper, we propose a new Congestion Aware Lifetime Improving Routing Protocol (abbreviated shortly as CALIRP) for grid-based WSNs, which improves the network lifetime by minimizing congestion at nodes. In CALIRP, routing is conducted in a grid by grid manner through the cell-headers. To save the energy and avoid congestion, multiple routing paths are established from the source to the base station. The paths are selected based on Transmitting Factor (TF) of cell-headers which take queue occupancy, queue length and residual energy into account. In addition, CALIRP adjusts node’s transmitting factor for reconstructing the paths so that the lifetime of network is prolonged. Simulation results highlight that the proposed CALIRP outperforms other existing routing algorithms in terms of success rate, queue occupancy and number of alive nodes etc.

Keywords

Grid-based sensor network grid length cell-header neighboring cell adjacent cell transmitting factor multipath routing congestion network lifetime

1. Introduction

Wireless sensor network (WSN) [2] is a collection of large number of tiny, low cost, memory/computational constraint sensor nodes which are capable of monitoring environment, noise, heath, object tracking and weather. In practical scenarios, these nodes are deployed in unattended remote and hostile area, where failure of a single node may cause network segmentation. Since sensor nodes are operated on batteries with limited energy supply, energy consumption becomes a crucial constraint to keep them active. High energy consumption reduces the lifetime of node and degrades the performance of the network. In WSNs, a sensor node consumes most of its energy in communication (transmission and reception), sensing and computation. Generally, sensing energy is constant and can be assumed to be negligible in many cases. However a lion’s share of energy consumption is due to the wireless communication, which increases with the distance between a transmitter and a receiver. Therefore, minimizing energy consumption is a challenging issue to prolong the network lifetime. We adopt the common definition of network lifetime [12] as the time when the first node runs out its energy completely, which is widely utilized in sensor networks. Numerous solutions, such as topology control, energy efficient routing, scheduling, and power control have been proposed in the literature to improve the network lifetime. Among them, energy efficient routing is the most attractive one.

In recent years, many energy aware routing algorithms – clustering [7,12,13], tree [3] and grid-based techniques [1,6,8,14] – have been designed. Unlike the previous two schemes, the grid-based approach is most popular for dynamic network configuration and selection of routing paths. Moreover, the existence of multiple paths between the source and the base station in grid topology minimizes energy dissipation at nodes by splitting the traffic (or data requests) over multiple paths. Nevertheless, most of the grid-based algorithms focus on energy consumption and lifetime of sensor nodes, the negative impact of congestion on the network lifetime is still uncovered. To overcome the problem, buffer-based congestion aware routing protocols [5,10] have been addressed by researchers, but they do not consider residual energy level of the nodes to alleviate congestion.

In this paper, we propose a new routing scheme, referred to as Congestion Aware Lifetime Improving Routing Protocol (abbreviated shortly as CALIRP), for grid-based WSNs where sensor nodes periodically forward the data requests to the base station. The key objective is to maximize the network lifetime and increase the success rate of data request delivery. CALIRP considers congestion level of node and also residual energy to maximize the success rate of the network while ensuring energy efficient routes. In our proposed scheme, the sensor field is partitioned into $M \times M$ number of grid cells of identical size and then a connected network comprised of cell-headers is formed to transmit the data request to the base station. In each grid cell, the cell-header is selected based on the minimum distance from the centroid and also based on its residual energy which is greater than some threshold value. In order to minimize the energy consumption and to avoid congestion, CALIRP establishes multiple routing paths from the source cell-header to the base station. During routing, a cell-header in a cell transmits its data request to the cell-headers of adjacent cells and /or neighboring cells based on transmitting factor (TF) which takes queue occupancy, queue length and residual energy into account. In addition, by adjusting the TF at each node, CALIRP reconstructs the routing paths towards the base station. The performance of the proposed algorithm is evaluated through simulations and results reveal that our scheme improves the network performance compared to other existing routing protocols in terms of success rate, queue occupancy and number of alive nodes, $FND / AND$ ratio.

The organization of the paper is as follows: In Section 2, related work is briefly discussed. In Section 3, the system model is described. Section 4 presents the proposed algorithm in details. The simulation results are presented and analyzed in Section 5. Finally, Section 6 concludes the paper.

2. Related work

According to the network architecture, existing routing algorithms in WSNs can be broadly classified into three categories – flat based [3], location aided and hierarchical [7,12,13]. Among them, hierarchical routing is frequently used to reduce the energy consumption of nodes and improve the efficient data transmission in a network. In hierarchical (also known as cluster based routing), nodes are organized into different cluster and each cluster has a special node referred to as clusterhead with other member nodes. Many clustering algorithms have been developed in last few years to improve the lifetime of sensor networks. Hierarchical routing can be single hop or multi hop. In [7], the authors proposed a single hop clustering algorithm, Low Energy Adaptive Clustering Hierarchy (LEACH) to minimize the transmission load and data redundancy of large scale sensor networks. LEACH follows random clusterhead selection and causes unbalanced energy dissipation among nodes. In [12], Hybrid Energy-Efficient Distributed (HEED) clustering was proposed, where clusterheads are selected on basis of residual energy of the sensor nodes. HEED uses multihop routing strategy for transmitting the packet to the base station. Energy Aware Distributed Unequal Clustering (EADUC) [13] considers only residual energy of node for selecting clusterhead in heterogeneous networks. Unlike HEED, EADUC divides the whole region into unequal size of clusters and tries to minimize the energy consumption at overburdened nodes. Nevertheless the algorithms cited above improve energy efficiency of the network; they put extra energy and message overhead for constructing clusters in multiple levels.

Grid-based routing techniques are similar with hierarchical routing techniques which divide the network into some grids of equal size and then use the grid structure to group the nodes of the network. Extensive research has been conducted in last few years for energy efficient grid-based routing in WSN. In this paper, we discuss some of recent works which are conceptually related to our work for completeness. Authors in [1] designed a grid-based routing protocol in WSNs based on flooding technique. The proposed protocol [1] improves the network lifetime by choosing high energy node as a co-ordinator in each grid. The co-ordinator stays active until complete exhaustion of the battery and then new co-ordinator is selected. To route the data, the authors in [1] utilized single path based load balancing routing technique. Another grid-based clustering and routing algorithm for wireless micro sensor networks was proposed in [14] to eliminate the overhead of the periodic flooding process. Here, the role of clusterhead is rotated among the nodes based on their energy level. Furthermore, the authors in [14] introduced a randomized routing technique to prolong the network lifetime. In [8], the authors proposed an integrated grid-based clustering and routing (GBCMRA) to minimize the hot spot problem of WSNs.

Several researchers include multiple sink or mobile sink technique for increasing the lifetime of senor nodes. Authors in [9] introduced a virtual grid-based routing technique, known as Virtual Grid based Dynamic Routes Adjustment (VGDRA) for mobile sink based sensor networks. VGDRA uses a set of communication rules for constructing the routes of source nodes to the nearest location of a sink with minimal routing overhead. In VGDRA, nodes near to the centre of grid cell are usually appointed as grid heads and boarder nodes communicate with the sink. Nevertheless, VGDRA improves packet delivery ratio, grid head at centre of cell depletes its energy much earlier. Energy Aware Grid-based Routing Scheme (EAGER) proposed in [6] considered multiple mobile sinks to extend the lifetime of sensor networks. EAGER utilizes rerouting method for improving the energy efficiency in dynamic network topology and employs a time-scheduling mechanism to save energy consumption of the grid. Grid-based Energy Efficient Routing Protocol (GEERP) [4] divides the senor field into two levels: (i) secondary level grid (SG) and (ii) premier level grid (PG). PGs are formed using adjacent SGs and SGs send their data to PGs to transmit it to the base station in multihop fashion. Data aggregation is one of the effective techniques for minimizing energy consumption at nodes. Grid based Data Aggregation Scheme (GBDAS) [11] utilized chaining mechanism for reducing the energy consumption at node. In GBDAS, the node with higher residual energy is selected as cell head and each cell head is linked further to form a chain. In each round, the cell head with the maximum residual energy is chosen as a chain header for transmitting the data packet to the base station. However GBDAS minimizes energy dissipation at nodes, it puts extra burden at head node and increases end to end delay in the network.

Most of the algorithms mentioned above only concern the energy level of nodes and do not consider congestion in data transmission process. However, these two parameters need to be considered collectively to provide an efficient routing solution for wireless sensor networks.

3. System model

3.1. Network model and assumptions

In this paper, we consider a WSN which consists of N number of sensor nodes distributed randomly in $L \times L$ region. The base station (BS) is placed outside the region and it is not limited in energy and computation power/memory. Sensor nodes are stationary, have unique identification (ID) and same transmission range ( $T_{X}$ ). We assume that every node u knows own location ( $x_{u}, y_{u}$ ) and uses this information to communicate with the other nodes in the network. Each node generates the data requests at a constant rate and transmits them to the neighbor node only if two nodes are within the range of each other. For ease of analysis, we assume that nodes have a uniform queue length Q (i.e., actual queue size) but different queue occupancy $Q O$ . The initial energy of each node is $E_{0}$ . At any instance of time, nodes can adjust their transmission power depending on the distance between two nodes.

3.2. Proposed grid based network model

The sensor network proposed in this work is viewed as a grid-based topology where the whole network is divided into $(M \times M)$ number of grid cells of equal size, as shown in Fig. 1. Each grid cell is square of size $D \times D$ where D is grid length, which remains same for all cells till the end of the network operation. Grid length D is calculated based on the region size $L^{2}$ and number of grids $M^{2}$ using Eq. (1) $\begin{matrix} (1) & D = ⌈ \sqrt{\frac{L^{2}}{M^{2}}} ⌉ . \end{matrix}$

Fig. 1.

Construction of grid structure with transmission range $= T_{X} = \sqrt{5 D}$ , grid length $= D$ , diameter of cell $= \sqrt{2 D}$ .

Each grid is identified by grid identifier (GID), denoted by $C_{i, j}$ where $i, j = 0, 1, 2, \dots, M - 1$ . However, nodes belonging to same cell have same GID. Each node u can calculate its $GID C_{i, j}$ using own location ( $x_{u}, y_{u}$ ) and grid length D as follows [14] $\begin{matrix} (2) & C_{i, j} = ⌈ \frac{x_{u}}{D} ⌉ ⌈ \frac{y_{u}}{D} ⌉ . \end{matrix}$

As the sensor filed is divided into number of grids, each cell contains a set of sensor nodes in which one node is recognized as cell-header and others are the normal nodes. When the source node is willing to transmit the data, it first sends the data to the corresponding cell-header and the cell-header relays the data to the BS through adjacent and/or neighboring cell headers. In our work, we assume that a cell header has four neighboring cell-headers and four adjacent cell headers. Two headers are said to be neighboring cell-headers only if they are within the range of each other. We have used the value of D to calculate the transmission range $T_{X}$ of each cell-header determined as $\sqrt{5 D}$ (shown in Fig. 1) and thus guarantee that a cell-header in $C_{i, j}$ can communicate directly with four neighboring cells such as ${(C_{i + 1, j}), (C_{i, j + 1}), (C_{i - 1, j}), (C_{i, j - 1})}$ . However the maximum distance from the cell-header in $C_{i, j}$ to four adjacent cells such as ${C_{i - 1, j - 1}, C_{i + 1, j - 1}, C_{i + 1, j + 1}, C_{i - 1, j + 1}}$ is $2 \sqrt{2} D$ . In this paper, $T_{X}$ is uniform to all cell-headers since the D value is same for all cells. Figure 1 illustrates the neighbor cells and adjacent cells of cell $C_{1, 1}$ . Cells covered with shades (i.e., $C_{1, 2}, C_{2, 1}, C_{0, 1}, C_{1, 0}$ ) are four neighboring cells of $C_{1, 1}$ , while cells without shades ( $C_{0, 2}, C_{2, 2}, C_{0, 0}, C_{2, 0}$ ) are the adjacent cells of $C_{1, 1}$ .

3.3. Energy model

Power consumption is an important criterion for evaluating the performance of the sensor network. Premature death of a node can interrupt the on-going communications in the network and in consequence the network may eventually become partitioned [3]. In this paper, First Order Radio Model [7] is adopted to calculate the amount of energy consumed by a node. According to this model, the energy dissipation of a node depends on energy consumed for transmission, reception and aggregation. If $E_{elc}$ is the energy required by the transmitter/receiver circuit and $E_{amp}$ is the energy dissipated by the amplifier, then the energy consumed by a sensor node to transmit/receive an l-bit data request (assuming $1 / d^{2}$ path loss where d is Euclidean distance between transmitter and receiver) is given as: $\begin{array}{l} (3) & E_{T x} (l, d) = E_{elc} \times l + E_{amp} \times l \times d^{2}, \\ (4) & E_{R x} (l) = E_{elc} \times l, \end{array}$ where $E_{T x} (E_{R x})$ is energy required to send (receive) l-bits data. If $E_{A}$ is the energy expenditure for aggregating l-bit data, then total energy consumption of a node will be: $\begin{matrix} E_{N} = E_{T x} + E_{R x} + E_{A} . \end{matrix}$

4. Proposed algorithm

In this section, we give the detailed description of our Congestion Aware Lifetime Improving Routing Protocol (CALIRP). The proposed algorithm works in rounds. Each round is divided into two phases, namely cell header election and routing. In first phase, we select energy efficient cell-headers for the grid cells. In second phase, a new multipath based data request distribution technique is introduced, where each cell header forwards its data to the base station using adjacent cell-headers and neighboring cell-headers. The phase is described subsequently in the following sections.

4.1. Phase I: Cell-header election

In CALIRP, cell-headers are selected based on their residual energy and their distances from the respective centroids of the grid cell. The header election is described as follows. Initially, the centroid of the cell is determined and each node sharing same GID with the centroid calculates its distance ( $d_{u}$ ) from it $\begin{matrix} (5) & d_{u} = SQRT ({(x_{u} - \overline{X_{i}})}^{2} + {(y_{u} - \overline{Y_{j}})}^{2}), \end{matrix}$ where $\overline{X_{i}} = (\frac{\sum_{u = 1}^{n} x_{u}}{n})$ , $\overline{Y_{j}} = (\frac{\sum_{u = 1}^{n} y_{u}}{n})$ and n is the number of nodes in the grid cell.

Next, the average residual energy of the grid cell ( $R_{avg}$ ) is computed using Eq. (6) and the node will become a candidate head node $(CHN)$ only if its residual energy is greater than $R_{avg}$ $\begin{matrix} (6) & R_{avg} = \sum_{u = 1}^{n} \frac{{RE}_{u}}{n} . \end{matrix}$

If no node is found, then the node with the smallest distance from the centroid becomes the head of that cell. Each CHN broadcasts a $< c o m p e t i t i o n >$ message which includes id, residual energy and distance from the centroid within its competition range ( $R_{X}$ ). To guarantee that all nodes will receive the message, we set $R_{X}$ to the diameter of the cell (i.e., $\sqrt{2 D}$ ). After receiving the message, each CHN calculates its Head Selection Factor $(HSF)$ – a ratio between residual energy and distance from the centroid and the node with the maximum HSF is elected as cell-header of the grid cell. If two or more $CHN s$ have the same HSF value, then the node with the smallest distance from the centroid becomes the cell-header. Each header sends a $< n o t i f i c a t i o n >$ message to the surrounding nodes within the cell. A node may receive multiple notifications; however it associates itself to the closet one. The proposed cell-header election is described in Algorithm 1 $\begin{matrix} (7) & HSF = \{\begin{matrix} \infty & if {RE}_{u} < R_{avg}, \\ (\frac{{RE}_{u}}{d_{u}}) & other wise. \end{matrix} \end{matrix}$

Algorithm 1

Cell-header in each cell (Grid length D, cell $C_{i, j}$ , residual energy ${RE}_{u}$ , distance from centroid $d_{u}$ )

4.2. Phase II: Multipath based data request distribution

After selecting cell-header in each cell, the proposed algorithm initiates the data transmission by establishing multiple paths from the source header to the BS. With our grid based structure, a cell-header in a cell requires three neighboring cells, two from the same column but adjacent rows and one from the same row but the adjacent column for the data request propagation. However the cell-headers in the first column of the grid being one-hop from the BS, and thereby, set the BS as the next hop. In each round, a cell-header say node u, (except those in the first column) selects its next hops from the cells that are closer to the BS, and forwards maximum two data requests to them – either directly or indirectly, i.e. through the neighboring cells of the same column. In our scheme, the cell-headers at most $2 \sqrt{2} D$ distance from u are the potential candidates for the next hop nodes and the next hop is selected based on Transmitting Factor (TF) as detailed subsequently. For example, in Fig. 2, the cell-header of $C_{2, 1}$ calculates the TF for the cell-headers of $C_{1, 2}$ , $C_{1, 1}$ and $C_{1, 0}$ and selects any two of them as the next hop nodes. The detailed of next hop selection and data request forwarding is presented in Algorithm 2.

Fig. 2.

Scheme for forwarding of requests in each round.

(1) Transmitting factor (TF)

As mentioned earlier, the TF is used for selecting the next hop nodes. The TF has three components: residual energy for minimizing energy consumption, queue occupancy for avoiding congestion and queue length for normalization. During data transmission, a cell-header u in cell ( $C_{i, j}$ ) calculates the TF for every adjacent and neighboring cell-header v in the next column towards the BS. The TF of cell-header v is defined as follows: $\begin{matrix} (8) & {TF}_{v} = [1 - {\frac{Q O_{v}}{Q}}] \times {RE}_{v}, \end{matrix}$ where ${RE}_{v}$ is residual energy of node $v, Q O_{v}$ is queue occupancy of node v and Q is given queue length. The ratio ( $\frac{Q O_{v}}{Q}$ ) must be within [0, 1]. When ( $\frac{Q O_{v}}{Q}$ ) becomes 0, ${TF}_{v}$ depends only on residual energy of adjacent cell-header. On the other hand, when ( $\frac{Q O_{v}}{Q}$ ) is 1, the cell-header will be blocked for the next possible transmissions. The TF will be maximum if the node has smaller queue occupancy and larger residual energy.

After calculating the TF for all neighboring and adjacent cell-headers in the next column, cell-header u selects first two cell-headers with the maximum TF and forwards two requests to them either directly or using its neighboring cells. In other words, the cell-header of $C_{i, j}$ can send the data requests to $C_{i - 1, j}$ directly and $C_{i - 1, j + 1}$ and $C_{i - 1, j - 1}$ through $C_{i, j + 1}$ and $C_{i, j - 1}$ respectively. While transmitting the request, a node checks both queue occupancy and energy level of the neighboring and adjacent cell-headers. If the cell-header does not have any vacant slots or energy, the cell-header will wait for another round and store the requests in its queue. Therefore, the number of data requests forwarded by cell-header v in each round is: $\begin{matrix} (9) & No. of forwarding requests (F) = ⌈ δ \times Q O_{v} ⌉, \end{matrix}$ where δ is a co-efficient of request forwarding. The value of δ is calculated in such a way that it provides maximum success rate and network lifetime. In our simulation, δ varies from 0.1 to 0.15.

(2) Algorithm description

Next hop selection for forwarding the data request towards the BS is determined by Nexthop_Selection(·) algorithm, as shown in Algorithm 2. Using this algorithm, the cell-header selects its next hop nodes according to the TF, as described earlier. In each round, each node generates a random number of requests (P) and stores them in its queue. When a next hop receives a request, it stores the request at own queue and the iteration is incremented by one. When residual energy level of the node is lower than some threshold value, the request generation for that particular node is temporarily deferred.

Algorithm 2

Nexthop $_$ Selection(Node id u, grid id $C_{i, j}$ , residual energy ${RE}_{v}$ , queue occupancy $Q O$ queue length Q)

5. Simulation and results

In this section, we evaluate the performance of our scheme CALIRP through simulations and results are compared with CA algorithm [5] and GBDAS [11] with respect to various performance metrics. These include success rate, queue occupancy, number of alive nodes and $FND / AND$ (First Node Die/All Node Die) ratio. All experiments are carried out using Java Programming language and MATLAB on Intel Core i3, Processor 2.1 GHz and 2 GB RAM. Simulations run for at least 20 times and then we take the average value. In this simulation study, we consider that 100 sensor nodes are randomly distributed in a two dimensional square area of size $100 m \times 100 m$ . The BS is placed outside the field. The base station is only responsible for receiving the data request. All nodes are assumed to have same transmission range. Each node generates 10 random data request of size 30 bytes in each round. The number of cells considered in our experiments is $6 \times 6$ , $8 \times 8$ and $10 \times 10$ . Simulation parameters used in our work are listed in Table 1. We consider two scenarios for conducting our simulation.

Table 1
Simulation parameters table

Parameter Value

Area size $100 m \times 100 m$

Number of nodes 100

Number of cells $6 \times 6$ , $8 \times 8$ , $10 \times 10$

Initial energy $0.5 J$ , $0.3 J$ – $0.5 J$

Queue length 15

Buffer rate $2 data requests$

Number of requests per round 10

Request size $30 bytes$

δ 0.10 to 0.15

$E_{elc}$ $50 nJ / bit$

$E_{amp}$ $100 pJ / bit / m^{2}$

Simulation period 2000 s

Parameter	Value
Area size	$100 m \times 100 m$
Number of nodes	100
Number of cells	$6 \times 6$ , $8 \times 8$ , $10 \times 10$
Initial energy	$0.5 J$ , $0.3 J$ – $0.5 J$
Queue length	15
Buffer rate	$2 data requests$
Number of requests per round	10
Request size	$30 bytes$
δ	0.10 to 0.15
$E_{elc}$	$50 nJ / bit$
$E_{amp}$	$100 pJ / bit / m^{2}$
Simulation period	2000 s

Scenario 1. We simulate WSN with the sensor nodes having uniform initial energy (0.5 J).

Scenario 2. We simulate WSN with the nodes having different initial energy (0.3 J–0.5 J).

5.1. Success rate

Success rate of the network is defined as the number of data requests successfully arrived at the base station. In our simulation, we measure the success rate when (i) congestion is more in the network and (ii) congestion is less in the network. Figure 3 shows the success rate of the proposed CALIRP against the number of rounds for various number of cells for scenario 1. It is clear from the figure that the success rate increases as the number of cells scales up. The reason is that as the number of cells increases, the grid length and traffic load at each grid decreases and as a result the success rate of the network increases. Moreover, with higher number of cells, more paths are available for the data request transmission – another reason for the success rate improvement in our scheme.

Fig. 3.

Success rate vs number of rounds for various cells (Congestion is present) in Scenario 1.

Figure 4(a) compares the success rate of our CALIRP for different number of cells with CA algorithm for scenario 1. It is found that the success rate decreases as the round proceeds. Note that, the success rate of our method is better than CA algorithm when number of cells increases. This is because our scheme follows multipath data distribution technique for forwarding the requests to the base station, whereas CA algorithm uses the single path based approach. Furthermore, in CALIRP, we have considered both congestion and residual energy of node for selecting the next hop. In contrast, CA algorithm takes the congestion level of node to find the next hop and thus, has lower success rate than CALIRP. Results in Fig. 4(b) are similar to Fig. 4(a). However the success rate shown in Fig. 4(b) is slightly lower than those in Fig. 4(a). This is due to the different initial energy of nodes and their energy loss.

Fig. 4.

Success rate vs number of rounds (Congestion is less) in (a) Scenario 1 and (b) Scenario 2.

5.2. Queue occupancy

Queue occupancy defines the number of buffered requests at each node. Figure 5 displays the queue occupancy of the proposed algorithm against the number of rounds for different number of cells for scenario 1. As shown in Fig. 5, increasing number of cells in our simulation area minimizes the queue occupancy at the nodes. This is due to the fact that when the number of cells increases, load at each node decreases, so less number of requests would be buffered at node and as a result the queue occupancy reduces.

Fig. 5.

Queue occupancy vs number of rounds for different cell numbers in Scenario 1.

In Fig. 6(a) and (b), the queue occupancy of CALIRP for different number of cells and CA algorithm is compared for scenario 1 and scenario 2 respectively. In Fig. 6(b), queue occupancy is faster as compared to Fig. 6(a). However, our algorithm outperforms existing CA algorithm in both scenarios when number of cells increases. The proposed method utilizes multiple paths for forwarding the data requests towards the base station and thereby causes less congestion at nodes. On the other hand, due to the single path routing, the queues in CA protocol are filled up faster than CALIRP.

Fig. 6.

(a) Queue occupancy vs number of rounds in Scenario 1. (b) Queue occupancy vs number of rounds in Scenario 2.

5.3. Number of alive nodes

Number of alive nodes is widely used metric to measure the overall lifetime of the sensor network. It is also used to check the connectivity of the network. When energy consumption among nodes is balanced, the number of alive nodes increases. The performance of the proposed scheme in terms of number of alive nodes for varying number of cells is shown in Fig. 7 for scenario 1. The figure indicates that the number of alive nodes increases with the growth in cell numbers. In CALIRP, large number of cells reduces the grid length of cell and the transmission range of node, lowering energy consumption at node. In addition, our scheme uses multiple paths for distributing the data requests which minimizes both transmission cost and reception energy cost at nodes and thus improves the overall lifetime of the network.

Fig. 7.

Number of alive nodes vs number of rounds for different cell numbers in Scenario 1.

Results in Fig. 8(a) and (b) demonstrate the performance of the proposed CALRIP for different number of cells with respect to the existing CA algorithm in terms of number of alive nodes and number of rounds in scenario 1 and scenario 2. Notice that, the number of alive node decreases as the round proceeds. This trend is true for both the algorithms as shown in Fig. 8(a) and (b). It is seen that with large grid cells, the number of alive of CALIRP is slightly lower than CA algorithm. Our proposed CALRIP even performs better when the grid length decreases. The reason behind this phenomenon is that CALIRP selects the energy efficient next hop nodes based on transmitting factor and sets up multiple paths from the source cell-header to the base station. These paths are even reconstructed at each round on basis of the transmitting factor of nodes. As a result, we have lower transmission energy and higher number of alive nodes. From Fig. 8(a), it can also be observed that the proposed scheme has better number of alive nodes as compared to Fig. 8(b). It may appear that the nodes with different initial energy in scenario 2 have slightly higher energy expenditure than the nodes with uniform energy level.

Fig. 8.

Number of alive nodes vs number of rounds in (a) Scenario 1 and (b) Scenario 2.

5.4. First node die/last node die ratio

This metric is also used to assess the network performance in terms of network connectivity. First node die ( $FND$ ) and last node die ( $LND$ ) are commonly used definitions to define the lifetime of sensor networks. Higher ratio value implies better network lifetime and network coverage. In Fig. 9, the $FND / AND$ ratio is compared with various routing algorithms by varying number of cells for scenario 1. We have already stated that increasing number of cells shortens the transmission distance between the nodes and improves energy saving at the nodes. Figure 9 shows that our algorithm (CALIRP) achieves better network performance than GBDAS and CA algorithm in terms of $FND / AND$ . We observe that CA algorithm has lowest $FND / AND$ ratio, whereas CALIRP has highest $FND / AND$ ratio. However, the performance of GBDAS is close to CALIRP. This can be explained as follows. CA algorithm does not consider the residual energy of node to select the next hop and GBDAS selects its parent based on the energy expenditure, though it follows the chain rule for propagating the data requests. This causes uneven energy consumption at some nodes in the network. On the other hand, our proposed CALIRP considers two parameters i.e., residual energy and congestion level to select the next hop node and balances the energy consumption among nodes by distributing the data requests over multiple paths. Since energy consumption at nodes is minimized, our proposed CALIRP improves the connectivity than other two algorithms.

Fig. 9.

FND/AND ratio vs number of cells in Scenario 1.

6. Conclusion

In this paper, we have proposed a new Congestion – Aware Lifetime Improving Routing Protocol (CALIRP) for grid-based WSNs which not only prolongs the network lifetime but also improves the success rate of the network. In the proposed scheme, cell-header is selected based on the energy level and the distance from the centroid. To forward the generated data request, surrounding cells of a grid are divided into neighboring cells and adjacent cells. During routing, CALIRP collects the data requests from neighboring cell-headers and forwards them to the next hop nodes via neighboring cells. CALIRP follows multipath routing and selects the next hop nodes from neighboring cell and/or adjacent cells based on transmitting factor. Paths are reconstructed to improve the energy efficiency of the network depending on the transmitting factor of nodes. Performance evaluation is done to evaluate the effectiveness of our algorithm. Simulation results show the improved network performance of CALIRP in terms of various metrics compared to other existing routing algorithms.

Footnotes

Acknowledgements

The authors gratefully acknowledge the facilities and support provided by the Director, National Institute of Technology, Durgapur 713 209, India. The authors are thankful to the anonymous reviewers for their helpful comments which led to improvement of the manuscript.

References

Akl and

Sawant, Grid based coordinate rouitng in wireless sensor networks, in: Proceedings of IEEE Conputer, Communications and Networking Conference, 2007, pp. 860–864.

I.F.

Akyildiz,

Su,

Sankarasubramaniam and

Cayirci, A survey on sensor networks, IEEE Communications Magazine 40 (2002), 102–114. doi:10.1109/MCOM.2002.1024422.

Bhattacharjee and

Bandyopadhyay, Lifetime maximizing dynamic energy efficient routing protocol for multi hop wireless networks, Simulation Modelling Practice and Theory 32 (2013), 15–29. doi:10.1016/j.simpat.2012.11.006.

Chen

et al., A grid based energy efficient routing protocol in wireless sensor networks, in: Proceedings of International Symposium on Wireless and Pervasive Computing, 2013, pp. 1–6.

Chen and

Yang, Congestion avoidance based on lightweight buffer management in sensor networks, IEEE Transactions on Parallel and Distributed Systems 17 (2006), 934–946. doi:10.1109/TPDS.2006.115.

Y.P.

Chi and

H.P.

Chang, An energy aware grid based routing scheme for wireless sensor networks, International Journal of Telecommunication Systems 54 (2013), 405–415. doi:10.1007/s11235-013-9742-x.

W.R.

Heinzlman,

Chandrakasan and

Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000, pp. 1–10.

Jannu and

P.K.

Jana, Energy efficient grid based clustering and routing algorithms for wireless sensor netwoks, in: Proceedings of IEEE International Conference on Communication, Systems and Network Technologies, 2014, pp. 63–68.

A.W.

Khan

et al., VGDRA: A virtual grid based dynamic routes adjustment scheme for mobile sink based wireless sensor networks, IEEE Sensors Journal 15 (2015), 526–534. doi:10.1109/JSEN.2014.2347137.

10.

Kumar

et al., Congestion aware routing in sensor networks, Technical report, Department of Computer Science and Engineering, Pennsylvania State University, 2006.

11.

N.C.

Wang

et al., Grid based data aggregation for wireless sensor networks, Journal of Advances in Computer Networks 1 (2013), 329–333.

12.

Younis and

Fahmy, HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks, IEEE Transactions on Mobile Computing 3 (2004), 366–379. doi:10.1109/TMC.2004.41.

13.

J.G.

Yu,

Y.Y.

Qi,

Wang,

Guo and

Gu, An energy-aware distributed unequal clustering protocol for wireless sensor networks, International Journal of Distributed Sensor Networks 2011 (2011), 1–8. doi:10.1155/2011/202145.

14.

Zhuang,

Pan and

Wu, Energy optimal grid based clustering in wireless micro sensor netwoks, in: Proceedings of IEEE International Conference on Distributed Computing Systems Workshops, 2009, pp. 96–102.