# Nonuniform Grid-Based Coordinated Routing in Wireless Sensor Networks

Authors: Robert Akl; Priyanka Kadiyala; Mohamad Haidar
Journal: Journal of Sensors
 (2009)

---

## Abstract

A nonuniform grid-based coordinated routing design in wireless sensor networks is presented. The conditions leading to network partition and analysis of energy consumption that prolongs the network lifetime are studied. We focus on implementing routing in densely populated sensor networks. By maintaining constant values for parameters such as path loss exponent, receiver sensitivity and transmit power, and varying between uniform and non-uniform grids, we observe energy consumption patterns for each of the grid structures and infer from the network lifetime the better suited grids for uniformly and randomly deployed sensor nodes.


---

## Body

## 1. Introduction

Wireless sensor networks, which are a form of ad hoc networks, are wireless networks consisting of autonomous sensor nodes, communicating with each other over wireless links. Each node in a sensor network consists of a central processing unit, memory, a Radio Frequency (RF) transceiver, and a power source, which is usually a battery.An efficient routing protocol in sensor networks can help minimize both the load on each individual node and the traffic overhead over the network. Traditional routing protocols are aimed at finding optimal routes to every host in the network and are not suitable for ad hoc networks. A mobile ad hoc networking (MANET) working group has been formed within the Internet Engineering Task Force (IETF) to develop a routing framework for IP-based protocols in the ad hoc networks [1]. These adhoc routing protocols are divided into table-driven and on-demand protocols.Table-driven protocols, such as Destination-Sequenced Distance Vector Routing (DSDVR), Clusterhead Gateway Switch Routing (CGSR), and Wireless Routing Protocol (WRP), require the use of routing tables at each node to keep track of routes to different nodes and make use of periodic broadcasts for periodic updates [1, 2]. They are advantageous in the fact that a route is available when required, and there is no delay experienced until the route can be determined.  However, table-driven algorithms are not suitable for self-configuring mobile ad hoc networks as most of the network capacity is used up in maintaining current routing information. On the other hand, On-demand algorithms, such as Ad Hoc On-Demand Distance Vector Routing, Dynamic Source Routing (DSR), Temporally Ordered Routing Algorithm (TORA), Associativity-Based Routing, and Signal Stability Routing, do not maintain such routing tables but use a procedure to identify a route when a source requires to transmit information to a destination [1]. Therefore, on-demand routing protocols are better suited for self-configuring mobile wireless sensor networks.In response to the needs of wireless sensor networks, new protocols have been proposed to meet the requirements of wireless sensor networks, such as flooding [3], gossiping [4], Sensor Protocols for Information via Negotiation (SPIN) [5, 6], Directed Diffusion [5–7] Low Energy Adaptive Clustering Hierarchy (LEACH) [5, 8], Power-Efficient Gathering in Sensor Information Systems (PEGASIS) [9], and Geographic and Energy Aware Routing (GEAR) [10].Another important aspect in wireless sensor networks is the battery lifetime of the node. Energy efficiency is a key challenge in wireless sensor networks and energy consumption is dominated by the energy required to keep the nodes active and running. Several energy conserving mechanisms have been proposed to extend the lifetime of the network, such as Span [11], Geographic Adaptive Fidelity (GAF) [12], Sparse Topology and Energy Management (STEM) [13], Adaptive Self-Configuring sEnsor Networks Topologies (ASCENT) [14], Cluster-based Energy Conservation (CEC) [15], and Adaptive Fidelity Energy-Conserving Algorithm (AFECA) [15]. Also, several topologies have been proposed for conserving energy in sensor networks including cluster, link, grid, and diffusion, which were adapted to route packets across the sensor network. Among these topology approaches, the grid-based approach, as put forward in the GAF algorithm, is more suited for sensor networks, since the grid topology can dynamically be configured with the configuration of the nodes.In [16], the authors explore grid-based coordinated routing in wireless sensor networks. The underlying routing protocol is based on flooding, but unlike flooding, grid-based coordinated routing reaches only selected nodes in the field. Sensor nodes are randomly deployed over a sensor field, and the entire field is divided into square shaped grids, of sizes defined by the user. One node in each grid is elected as the coordinator node, which actually takes part in the routing process while the remnant nodes power down their radios to save energy. The source floods the network with a query message to each coordinator. When the message reaches the sink node, the sink node sends information by tracing a route back to the source node. This process continues till a coordinator node in the route runs out of energy. Nodes in the network are assigned IDs. Coordinator nodes are elected based on the IDs. The node with the highest ID in the grid is elected to be the coordinator. If this node runs out of energy, the next highest node is elected as coordinator. New coordinators are elected to replace nodes that run out of energy.  The process continues till the network is partitioned, and the connection between the source and sink is lost. This scheme employs load balancing to keep the nodes running for a long time.  In [17], a directed grid topology is proposed from the source node to the sink node. This grid is constructed with respect to the diagonal line between the source and sink nodes. Here, the sink node can move around in the network, and hence the topology of the grid varies according to the positions of the source and sink nodes. The parameter determining the distance between the grids is the average transmission cost, unlike in the previous scheme. There are two criteria for selecting a grid node: the distance to the location of the ideal grid node and the residual power. A cost parameter has been defined as the metric to select a grid node. The next hop is determined by the node with the smallest value for the cost parameter. There are two contributions of this scheme; namely,k the optimal grid distance is derived from the transmission cost point of view. Also, the routing scheme can be used for one sink and single or multiple sources. In [18], the concept of grid-based routing is proposed wherein variants of grid-based routing are proposed for different environments. The authors maintain that grid-based routing requires as few grids as possible to participate while ensuring network connectivity. The notion that keeps the network connected to one node per grid is required to stay active. This is contradicted with the argument that a largely reduced subset of grids can still preserve the same degree of coverage.This paper therefore puts forward variants of grid-based routing schemes, which reduce the number of grids that are required to support routing while supporting network connectivity. Also, the authors demonstrate that diagonal routing with a different side length of grids outperforms rectilinear routing. The above-mentioned grid-based schemes are common with the fact that they propose routing schemes for a uniform grid structure. In [19], a non-uniform grid structure is proposed for the GAF protocol, by deducing the relationship between the optimal radio range and traffic in the network. The minimum energy consumption characteristic range is not a constant but varies with the amount of traffic. Optimal range increases as the loaded traffic decreases. To save energy by radio range adjustment, the network is divided into sections of different sizes according to a derived range-traffic relationship. The number of grid sections is not a free parameter as in the case of the GAF protocol. The authors demonstrate that lower energy consumption is achieved by the non-uniform virtual grid routing, as compared to the values for the uniform grid.The remainder of this paper is organized as follows. Section2 defines the problem and the objective pursued in the paper. Section 3 describes our non-uniform grid-based routing protocols. Section 4 provides simulations and results for various non-uniform grid-based structures, uniform grid structure, and the traditional flooding algorithm. Finally, Section 5 concludes the paper.


## 2. Problem Definition

### 2.1. Problem Statement

Sensor networks are easy to deploy and enable us to remotely monitor inaccessible areas. The major challenge posed by sensor networks is the wasteful usage of resources. Once deployed, sensor nodes are solely battery operated and left to self organize and process information. It is important to keep the nodes up and running for as long as possible. Hence, energy consumption becomes a serious issue in sensor networks. In [20], the authors recognize network partition as a major problem in sensor networks. In [16], network partition is defined as an event when the source node and the sink node are connected last. Therefore, we define the network as partitioned when no communication link can be established between the source node and the sink node. The loss of communication between the source and the sink nodes is a result of exhausted battery life of the sensor nodes in the network [16]. Hence, network partition is directly affected by the energy consumption of the nodes in the network.


### 2.2. Motivation

A wireless sensor network is a wireless network of spatially distributed sensors, which respond to any change in the physical or environmental conditions. The sensor node gathers information by responding to changes in its surroundings, processes the information gathered, and communicates with its neighbors. Power consumption is a very important issue for deploying wireless sensor networks as each node operates with limited power and the lifetime of the nodes effects the lifetime of the wireless sensor network. If each node were to transmit directly to its destination, the amount of power it consumes for each transmission would deprive the node of its energy completely. Hence, direct transmission is beneficial when the destination is within a limited coverage area.Transmitting packets in a multihop manner, wherein the consumption of power can be shared by all the nodes in the network, increases the network lifetime. Each node controls its transmission power and self organizes a network topology by controlling its coverage area. The network topology can therefore be dynamically changed in accordance with the neighboring nodes. In multihop transmission, selection of the intermediate node is done by not only considering the shortest path possible but also by taking into account the residual power of the potential intermediary nodes. This is important because selecting the same intermediate nodes often will result in depleting the intermediate nodes of their energy and causing the nodes to die which will, in turn, decrease the network lifetime. Therefore, focusing on network longevity, many topologies have been developed to route packets from the source node to the destination node.The various topologies adopted for routing packets in sensor networks are grid, cluster, link, and diffusion. Amongst them, the grid approach is the most beneficial, since the topology of the grid can be configured dynamically with respect to the source and the sink nodes. Also, there are multiple paths between the source and the destination, making the selection of the forwarding path and the intermediate nodes flexible.  The grid approach was designed to achieve node equivalence in a network and was implemented initially in the GAF and SPAN protocols [17].


### 2.3. Objective

This paper studies the conditions leading to network partition and analyzes energy consumption to prolong the network lifetime. We focus on implementing routing in a densely populated sensor networks. By maintaining constant values for parameters such as path loss exponent, receiver sensitivity, transmit power, and varying between uniform and non-uniform grids, we observe energy consumption patterns for each of the grid structures and infer from the network lifetime the better suited grids for uniformly and randomly deployed sensor nodes.


### 2.4. Contributions

The main contributions of this paper are:(i)
designing and implementing a non-uniform grid-based routing with different types of non-uniform grids;(ii)
maintaining load balancing among the sensor nodes;(iii)
determining the better type of grid suitable for uniform and random deployment for different node densities.


## 2.1. Problem Statement

Sensor networks are easy to deploy and enable us to remotely monitor inaccessible areas. The major challenge posed by sensor networks is the wasteful usage of resources. Once deployed, sensor nodes are solely battery operated and left to self organize and process information. It is important to keep the nodes up and running for as long as possible. Hence, energy consumption becomes a serious issue in sensor networks. In [20], the authors recognize network partition as a major problem in sensor networks. In [16], network partition is defined as an event when the source node and the sink node are connected last. Therefore, we define the network as partitioned when no communication link can be established between the source node and the sink node. The loss of communication between the source and the sink nodes is a result of exhausted battery life of the sensor nodes in the network [16]. Hence, network partition is directly affected by the energy consumption of the nodes in the network.


## 2.2. Motivation

A wireless sensor network is a wireless network of spatially distributed sensors, which respond to any change in the physical or environmental conditions. The sensor node gathers information by responding to changes in its surroundings, processes the information gathered, and communicates with its neighbors. Power consumption is a very important issue for deploying wireless sensor networks as each node operates with limited power and the lifetime of the nodes effects the lifetime of the wireless sensor network. If each node were to transmit directly to its destination, the amount of power it consumes for each transmission would deprive the node of its energy completely. Hence, direct transmission is beneficial when the destination is within a limited coverage area.Transmitting packets in a multihop manner, wherein the consumption of power can be shared by all the nodes in the network, increases the network lifetime. Each node controls its transmission power and self organizes a network topology by controlling its coverage area. The network topology can therefore be dynamically changed in accordance with the neighboring nodes. In multihop transmission, selection of the intermediate node is done by not only considering the shortest path possible but also by taking into account the residual power of the potential intermediary nodes. This is important because selecting the same intermediate nodes often will result in depleting the intermediate nodes of their energy and causing the nodes to die which will, in turn, decrease the network lifetime. Therefore, focusing on network longevity, many topologies have been developed to route packets from the source node to the destination node.The various topologies adopted for routing packets in sensor networks are grid, cluster, link, and diffusion. Amongst them, the grid approach is the most beneficial, since the topology of the grid can be configured dynamically with respect to the source and the sink nodes. Also, there are multiple paths between the source and the destination, making the selection of the forwarding path and the intermediate nodes flexible.  The grid approach was designed to achieve node equivalence in a network and was implemented initially in the GAF and SPAN protocols [17].


## 2.3. Objective

This paper studies the conditions leading to network partition and analyzes energy consumption to prolong the network lifetime. We focus on implementing routing in a densely populated sensor networks. By maintaining constant values for parameters such as path loss exponent, receiver sensitivity, transmit power, and varying between uniform and non-uniform grids, we observe energy consumption patterns for each of the grid structures and infer from the network lifetime the better suited grids for uniformly and randomly deployed sensor nodes.


## 2.4. Contributions

The main contributions of this paper are:(i)
designing and implementing a non-uniform grid-based routing with different types of non-uniform grids;(ii)
maintaining load balancing among the sensor nodes;(iii)
determining the better type of grid suitable for uniform and random deployment for different node densities.


## 3. Nonuniform Grid-Based Routing

### 3.1. Gird-Based Coordinated Routing

The main focus of Grid-Based Coordinated Routing (GBCR) is on partitioning the network into square-shaped grids to extend network lifetime. The entire network is divided into equally shaped grids, in each grid an active node,  and the coordinator is elected, like in the Span algorithm.In grid-based coordinated routing, information reaches only selected nodes in the field grids is to make only one node alive for each grid, while the rest of the nodes in that grid are sleeping so as to conserve their battery life. In each grid, the coordinator participates in routing as long as the amount of energy in that coordinator is above a certain threshold value. When the energy drops below the threshold, a new coordinator is elected for that grid. The source transmits information to the sink through the active coordinators, and the sink traces a route back to the source. The process of flooding continues till the nodes participating in the routing run out of energy, when new coordinators are elected and a new route back to the source from the sink is calculated. The source starts flooding by sending a query message to all the neighbor coordinators, which flood other coordinators in the network till the message reaches the sink node. Each coordinator node in grid-based routing has three states, namely, routing, warning, and depleted states. When coordinator nodes in a particular route die, or run out of energy, new coordinators are elected to replace the old nodes. All nodes in the network are randomly assigned IDs. In each grid, the node with the highest ID becomes the coordinator. When the node with the highest ID runs out of energy, the node with the next highest ID becomes the coordinator for that grid. Each time the coordinator node changes the sink node traces back a route to the source node. Grid-based coordinated routing adopts a grid structure as shown in Figure1.Figure 1
The uniform grid structure with 100 sensor nodes deployed uniformly.Each grid is a square of 200 m, for example. Different results have been observed by varying the grid size from 50 m to 200 m. When grid coordinators are selected, special consideration must be given to those who are able to connect to neighboring grid coordinators. Therefore, grid size is very important to maintain connectivity throughout the network as a very large grid size results in loss of connectivity of the nodes in the network. Connectivity in the network depends on the grid size, transmission range, and the sensitivity of the nodes. GBCR maintains load balancing as does GAF. The function of the coordinator node is distributed among the nodes in the network based on the ranking of the nodes in each grid. GBCR observes the effects of transmit power, receiver sensitivity, and grid size on network lifetime and determines the transmit power that increases the network lifetime.


### 3.2. Non-Uniform Gird-Based Coordinated Routing

Uniform grid-based routing is efficient when the distribution of the nodes in the sensor field is uniform. Varying the grid sizes in the network extends the lifetime of the network. The entire sensor field is divided into non-uniform sized grids. In [19], the relation between optimal radio range and traffic is used to define a non-uniform grid for the GAF protocol. In this paper, the non-uniform grid size for the grid-based coordinated routing protocol is applied and analysis of the results is presented.In this paper, three different non-uniform grids are considered. Figures3 to 5 show the different types of grid structures that are considered for simulation. In Figure 2, the alternating non-uniform grid structure is depicted where 100 sensor nodes are uniformly deployed across the study area. The alternating grids are 100 m each square (small grids) and 200 m squares (large grids). Figure 3 shows the source non-uniform structure where 100 sensor nodes are deployed uniformly in the study area. The area containing the source node (top left) is divided into small grid squares of 100 m each whereas the area containing the sink node (bottom right) is divided into grid squares 200 m each. Finally, the sink non-uniform grid structure with 100 sensor nodes deployed uniformly across the field is presented in Figure 4. The vicinity around the source node is divided into 200 m square grids while the area in the vicinity of the sink node is divided into 100 m square grids.Figure 2
Topology showing the alternating non-uniform grid structure.Figure 3
Simulation topology showing the source non-uniform structure.Figure 4
Simulation topology showing the sink non-uniform grid structure.Figure 5
Virtual GridIn each grid, as in the uniform grid-based routing, a coordinator node is elected from all the nodes of the grid that is involved in the routing process while the other nodes in the grid save their battery by putting themselves to sleep. New coordinators are elected when the node runs out of energy or falls below a threshold value.


### 3.3. Grid Size

To ensure connectivity between any two coordinator nodes in adjacent grids, proper grid size must be determined. Grid size is affected by factors such as the transmission range of the transmitter (or the transmit power) and the sensitivity of the nodes. If either the grid size is too large or the coordinator nodes are far from each other, this will lead to early partition of the network. Thus, a link between the nodes even cannot be formed even if the nodes are alive in each grid.Figure5 [12] shows the maximum limit for the side r can be estimated as follows:(1)r≤Rn5.By estimating the value ofRn and assigning values for Pt, Pr, and n, the value of r and the grid size can be determined; hence, the two coordinator nodes from adjacent grids can successfully communicate with each other. It is important not to have a very small grid sizes, as the transmit power and the receiver sensitivity allow a minimum distance between the nodes to be covered. Thus, having very small grid size will lead to wasted resources.


### 3.4. Grid Coordinator Election

As mentioned earlier, a grid-based coordinated routing requires having coordinator nodes in each grid that remain active while the other nodes in the grid are sleeping. Initially, all the nodes in the field have energy equal to 100% of battery life and are marked green in the simulation. As the nodes get elected and routing of information to and from the source takes place as a continuous process, the node energy depletes with time. When the node energy is equal to or below 25% of battery life, the node is marked in yellow, and, finally, when the node is out of energy (dead node), it is marked in red, as illustrated in Figure6.Figure 6
Simulation topology showing different node colors based on battery life remaining.In grid-based coordinated routing, all the nodes in the network are assigned IDs randomly. In each grid, the node with the highest ID becomes the coordinator node. When this coordinator is out of energy, the node that has the second highest ID is chosen to take its place and so on until all the nodes in the network are out of energy or no more communication links can be established from the source to the sink, thereby partitioning the network. Even when none of the nodes in the network is dead, if a successful route cannot be established from the source node to the sink node, the network is partitioned.The information traverses through the grid coordinators only, and the rest of the nodes in the network are put to sleep to conserve their battery life. Once the route from the source to the destination has been established, data travels from the source to the sink and back through that route only. The other coordinator nodes are also awake and listening while the coordinators in the route receive and transmit information. Hence, the coordinators in that particular route tend to lose energy more rapidly than the coordinator nodes that are not transmitting.


### 3.5. Load Balancing

To utilize the nodes to their maximum lifetime, a grid-based routing protocol should employ load balancing. The coordinator role is shared by all the nodes in the network to ensure fair usage of node resources. Each node in the network is initially assigned a rank. The node with the lowest rank is elected as the coordinator. To ensure load balancing, the node IDs are not considered to elect coordinator nodes. Initially, since all the nodes have the same rank, one node per grid is randomly elected as the coordinator node for that grid. Once transmissions to and from the source begin, the node energy gradually depletes. If the energy of the node is greater than 25% of its battery life, the rank of that node is incremented by one, and if the energy drops to or less than 25% of battery life, the rank of that node is incremented by two, and the node has to be put to sleep. When such a node is detected in the route, the link between the source and sink is disrupted as one of the coordinator nodes is now dead. Hence, the source node has to reflood the network once new coordinator nodes are elected in place of the nodes that have energies equal to or less than 25% battery life. The dead nodes are removed from the network and are no more ranked. The new coordinator nodes are the nodes that have a lower rank, more energy, and can handle routing for a longer time. Therefore, maintaining load balancing, grid-based routing protocol increases network lifetime. The process of node re-election continues till the network is partitioned and no link can be established between the source and the sink.


## 3.1. Gird-Based Coordinated Routing

The main focus of Grid-Based Coordinated Routing (GBCR) is on partitioning the network into square-shaped grids to extend network lifetime. The entire network is divided into equally shaped grids, in each grid an active node,  and the coordinator is elected, like in the Span algorithm.In grid-based coordinated routing, information reaches only selected nodes in the field grids is to make only one node alive for each grid, while the rest of the nodes in that grid are sleeping so as to conserve their battery life. In each grid, the coordinator participates in routing as long as the amount of energy in that coordinator is above a certain threshold value. When the energy drops below the threshold, a new coordinator is elected for that grid. The source transmits information to the sink through the active coordinators, and the sink traces a route back to the source. The process of flooding continues till the nodes participating in the routing run out of energy, when new coordinators are elected and a new route back to the source from the sink is calculated. The source starts flooding by sending a query message to all the neighbor coordinators, which flood other coordinators in the network till the message reaches the sink node. Each coordinator node in grid-based routing has three states, namely, routing, warning, and depleted states. When coordinator nodes in a particular route die, or run out of energy, new coordinators are elected to replace the old nodes. All nodes in the network are randomly assigned IDs. In each grid, the node with the highest ID becomes the coordinator. When the node with the highest ID runs out of energy, the node with the next highest ID becomes the coordinator for that grid. Each time the coordinator node changes the sink node traces back a route to the source node. Grid-based coordinated routing adopts a grid structure as shown in Figure1.Figure 1
The uniform grid structure with 100 sensor nodes deployed uniformly.Each grid is a square of 200 m, for example. Different results have been observed by varying the grid size from 50 m to 200 m. When grid coordinators are selected, special consideration must be given to those who are able to connect to neighboring grid coordinators. Therefore, grid size is very important to maintain connectivity throughout the network as a very large grid size results in loss of connectivity of the nodes in the network. Connectivity in the network depends on the grid size, transmission range, and the sensitivity of the nodes. GBCR maintains load balancing as does GAF. The function of the coordinator node is distributed among the nodes in the network based on the ranking of the nodes in each grid. GBCR observes the effects of transmit power, receiver sensitivity, and grid size on network lifetime and determines the transmit power that increases the network lifetime.


## 3.2. Non-Uniform Gird-Based Coordinated Routing

Uniform grid-based routing is efficient when the distribution of the nodes in the sensor field is uniform. Varying the grid sizes in the network extends the lifetime of the network. The entire sensor field is divided into non-uniform sized grids. In [19], the relation between optimal radio range and traffic is used to define a non-uniform grid for the GAF protocol. In this paper, the non-uniform grid size for the grid-based coordinated routing protocol is applied and analysis of the results is presented.In this paper, three different non-uniform grids are considered. Figures3 to 5 show the different types of grid structures that are considered for simulation. In Figure 2, the alternating non-uniform grid structure is depicted where 100 sensor nodes are uniformly deployed across the study area. The alternating grids are 100 m each square (small grids) and 200 m squares (large grids). Figure 3 shows the source non-uniform structure where 100 sensor nodes are deployed uniformly in the study area. The area containing the source node (top left) is divided into small grid squares of 100 m each whereas the area containing the sink node (bottom right) is divided into grid squares 200 m each. Finally, the sink non-uniform grid structure with 100 sensor nodes deployed uniformly across the field is presented in Figure 4. The vicinity around the source node is divided into 200 m square grids while the area in the vicinity of the sink node is divided into 100 m square grids.Figure 2
Topology showing the alternating non-uniform grid structure.Figure 3
Simulation topology showing the source non-uniform structure.Figure 4
Simulation topology showing the sink non-uniform grid structure.Figure 5
Virtual GridIn each grid, as in the uniform grid-based routing, a coordinator node is elected from all the nodes of the grid that is involved in the routing process while the other nodes in the grid save their battery by putting themselves to sleep. New coordinators are elected when the node runs out of energy or falls below a threshold value.


## 3.3. Grid Size

To ensure connectivity between any two coordinator nodes in adjacent grids, proper grid size must be determined. Grid size is affected by factors such as the transmission range of the transmitter (or the transmit power) and the sensitivity of the nodes. If either the grid size is too large or the coordinator nodes are far from each other, this will lead to early partition of the network. Thus, a link between the nodes even cannot be formed even if the nodes are alive in each grid.Figure5 [12] shows the maximum limit for the side r can be estimated as follows:(1)r≤Rn5.By estimating the value ofRn and assigning values for Pt, Pr, and n, the value of r and the grid size can be determined; hence, the two coordinator nodes from adjacent grids can successfully communicate with each other. It is important not to have a very small grid sizes, as the transmit power and the receiver sensitivity allow a minimum distance between the nodes to be covered. Thus, having very small grid size will lead to wasted resources.


## 3.4. Grid Coordinator Election

As mentioned earlier, a grid-based coordinated routing requires having coordinator nodes in each grid that remain active while the other nodes in the grid are sleeping. Initially, all the nodes in the field have energy equal to 100% of battery life and are marked green in the simulation. As the nodes get elected and routing of information to and from the source takes place as a continuous process, the node energy depletes with time. When the node energy is equal to or below 25% of battery life, the node is marked in yellow, and, finally, when the node is out of energy (dead node), it is marked in red, as illustrated in Figure6.Figure 6
Simulation topology showing different node colors based on battery life remaining.In grid-based coordinated routing, all the nodes in the network are assigned IDs randomly. In each grid, the node with the highest ID becomes the coordinator node. When this coordinator is out of energy, the node that has the second highest ID is chosen to take its place and so on until all the nodes in the network are out of energy or no more communication links can be established from the source to the sink, thereby partitioning the network. Even when none of the nodes in the network is dead, if a successful route cannot be established from the source node to the sink node, the network is partitioned.The information traverses through the grid coordinators only, and the rest of the nodes in the network are put to sleep to conserve their battery life. Once the route from the source to the destination has been established, data travels from the source to the sink and back through that route only. The other coordinator nodes are also awake and listening while the coordinators in the route receive and transmit information. Hence, the coordinators in that particular route tend to lose energy more rapidly than the coordinator nodes that are not transmitting.


## 3.5. Load Balancing

To utilize the nodes to their maximum lifetime, a grid-based routing protocol should employ load balancing. The coordinator role is shared by all the nodes in the network to ensure fair usage of node resources. Each node in the network is initially assigned a rank. The node with the lowest rank is elected as the coordinator. To ensure load balancing, the node IDs are not considered to elect coordinator nodes. Initially, since all the nodes have the same rank, one node per grid is randomly elected as the coordinator node for that grid. Once transmissions to and from the source begin, the node energy gradually depletes. If the energy of the node is greater than 25% of its battery life, the rank of that node is incremented by one, and if the energy drops to or less than 25% of battery life, the rank of that node is incremented by two, and the node has to be put to sleep. When such a node is detected in the route, the link between the source and sink is disrupted as one of the coordinator nodes is now dead. Hence, the source node has to reflood the network once new coordinator nodes are elected in place of the nodes that have energies equal to or less than 25% battery life. The dead nodes are removed from the network and are no more ranked. The new coordinator nodes are the nodes that have a lower rank, more energy, and can handle routing for a longer time. Therefore, maintaining load balancing, grid-based routing protocol increases network lifetime. The process of node re-election continues till the network is partitioned and no link can be established between the source and the sink.


## 4. Simulations and Results

This section presents the real-time simulations of the non-uniform grid-based coordinated routing protocol. Results compare the uniform grid-based coordinated routing with three different types of non-uniform grids and the traditional flooding algorithm. All results were carried out using MATLAB simulation tool.


### 4.1. Assumptions

In simulating the non-uniform grid-based coordinated routing protocol, the following assumptions are taken into consideration:


#### 4.1.1. The Energy Model

Sensor nodes consume energy while in idle mode (listening mode). The energy consumed is sometimes useful and other times not. So, one of the major constraints on the wireless ad hoc sensor networks is the excessive energy consumption, which leads to diminishing the network lifetime. It is important to note that the energy spent by a node in the transmitting, receiving, and idle modes may not be the same. The idle:receive:transmit ratio of energy is shown to be1.0:1.05:1.4 in [21], 1.0:2:2.5 in [22], and 1.0:1.2:1.7 in [11]. In our case, the energy spent by a node for idle listening is 1.0 unit, reception is 1.5 units, and transmission is 2.0 units. A counter array keeps track of the energy left in each node. If the node is elected as a coordinator node, it loses 1.0 unit of energy. Then, if the same node is used for transmission of data between nodes, it loses another unit of energy (i.e., a total of 2 units), but if it is a coordinator and only receives the information from a node and does not transmit the information to another coordinator, then, the node loses only 0.5 units of energy (for a total of 1.5 units). If a unit is not a coordinator but still is idle listening, it uses 1.0 unit of energy every one time-unit of simulation time.


#### 4.1.2. Simulation of the Sensor Field and Deployment of Nodes

A sensor field that is close to an actual sensor field is assumed. The size of the sensor field is limited to a 2D space, 1000 m in the x-axis and 1000 m in the y-axis. The field is devoid of any obstacles. The sensor nodes are assumed to be actual sensor nodes. A Graphical User Interface (GUI) for observing the flooding simulations and the behavior of the uniform and non-uniform routing protocols has been implemented. The sensor nodes in the field can be deployed either uniformly or randomly strewn across the fieldThe number of sensor nodes in the network can be varied between 100 and 1000 nodes. The network consists of two fixed nodes that are of infinite energy, the source node and the sink node. This assumption applies irrespective of the type of deployment of the nodes, uniform or random. Simulations are thereby observed for different node densities to analyze the scalability of the non-uniform grid-based coordinated routing protocol.


### 4.2. Parameters Affecting Routing in the Network

There are numerous parameters that affect the performance of a wireless sensor network, some of which include type of node, battery life of the node, application of the network, and so on. As pertains to our study, the following parameters affect the performance of the sensor network:(i)
node deployment: uniform and random,(ii)
node density: 100, 200, 400, and 1000 sensors,(iii)
grid size: varies with type of grid being used,(iv)
receiver Sensitivity: −90 dBm,(v)
transmit power: −2 dBm,(vi)
path loss exponent: 3.5,(vii)
node energy: 50 units.The following parameters (node deployment, node density, receiver sensitivity, transmission range, and node energy) affect the lifetime of the network. The grid size parameter is only used for uniform grid sizes, and the delay parameter is used to delay the routing process, which makes it easier to observe the routing process as the information traverse from the source to the destination. If the delay parameter is not introduced, the routing process occurs instantaneously and is difficult to observe. Therefore, the delay parameter does not affect the network efficiency in any way. The default parameter values that affect the routing in the network are shown in Figure7.Figure 7
Default parameter values.The node density is initially taken to be 100 and is gradually varied from 100 to 1000 nodes. The grid size varies with the type of grid being used, from uniform grid to the three different types of non-uniform grids. The node energy is fixed to be 50 units and gradually decreases with the participation of the node in routing. The transmission range or the transmit power is the range within which a node can transmit its information. Beyond this range, the signal for that node is lost. The sensitivity of the receiver is fixed to be at-90 dBm, and the path loss exponent (which is usually between 2 and 5) is set to 3.5, where we consider the deployment of the sensor network in a relatively lossy environment. The flooding can be observed node-by-node or level-by-level.


### 4.3. Analyzing the Results

In order to analyze the efficiency of the protocol, we have to determine how long the network stays alive while allowing transmissions from the source to destination. Two variables are considered: (i) the normalized energy, total time for which the network is up and running, and (ii) the count of the total transmissions that the network allows between the source and the sink. The total transmissions allowed in the network are important to assure that the network actually allows a fair amount of information to be exchanged as long as the network is alive. Normalized energy is defined as the ratio of the total current energy of all nodes to the total energy of all nodes at the start of the simulation. Network time is kept track of by a timer that starts once the network starts to flood and stops when there is no communication link between the source and the sink nodes. The timer is set once the routing begins and stops only when the network partitions, thereby calculating the total time for which the network is alive. Figure8 shows an example of the total transmissions in the network over time for 100 nodes deployed randomly over the sensor field and the alternating non-uniform grid structure.Figure 8
Transmissions for each successful link established between the source and the sink nodes.


### 4.4. Uniform Node Deployment

Figures9, 10, 11, and 12  show the results for the uniform and the non-uniform grid simulations.Figure 9
Flooding for 100 nodes uniformly distributed in the field of1000×1000 m2 for the alternating non-uniform grid structure.Figure 10
Flooding between the coordinator nodes in a1000×1000 m2 network for a grid structure with the source node in nodes of size 200 m and sink node in grids of size 100 m each.Figure 11
Flooding between the coordinator nodes in a1000×1000 m2 network for a grid structure with the source node in nodes of size 100 m and sink node in grids of size 200 m each.Figure 12
Flooding in the network for 100 nodes deployed uniformly in the sensor field (1000×1000 m2) for a uniform grid structure.From these simulations, it has been observed that the uniform grid-based coordinated routing protocol is better suited for uniform node deployment.


### 4.5. Random Node Deployment

We consider a non-uniform node deployment of 250 nodes in this section.  For a given node density, the efficiency of the different grid structures is analyzed by comparing the network alive times along with the total transmission of each structure. The longest network structure does not necessarily have to possess the maximum transmissions, but it should still support a fair amount of transmissions between the source and the sink. Thus, three cumulative graphs are provided:(i)
the network lifetime of the network for each grid structure,(ii)
the total transmissions for each grid structure,(iii)
the energy depletion graph.Figure13 shows total transmissions allowed in the network for a node density of 100 nodes for all the grid structures. Figure 14 presents the network lifetime of the different grid structures with 100 nodes deployed randomly.Figure 13
Total transmissions allowed for the same node density of 100 nodes with different grid structures.Figure 14
Network lifetime for different grid structures for 100 nodes deployed randomly across the sensor field.It is observed that the lifetime of a non-uniform grid structure exceeds the total transmissions allowed by the uniform grid structure. Figure15 shows the energy plot of different grid structures for 100 nodes resulting in a gradual decline of energy in the network with time.Figure 15
Energy versus Time performance of the different grid structures.The maximum network lifetime is nearly 900 time units for the alternating non-uniform grid structure, and this structure better utilizes the entire energy in the network since the energy gradually decreases from 1.0 unit to nearly 0.28 units. Two graphs are considered for the analysis of the simulations: the graph that plots the total transmissions supported by the network (Figure13) and the graph that plots the energy depletion (Figure 15).Figure16, 17, 18, and 19 show graphs representing network lifetime and energy depletion for different node densities.Figure 16
Network lifetime for 200 nodes for different grid structures.Figure 17
Network lifetime for 1000 nodes for uniform and alternate grid structures.Figure 18
Network energy decrease for various grid structures.Figure 19
Network energy decrease with time for 1000 nodes.


### 4.6. Comparison with the Traditional Flooding Algorithm

The main disadvantage of the traditional flooding algorithm is that the information travels throughout the network before it can reach the destination. Flooding does not pick a particular route to send information from the source to the sink. Instead, a node is alive all the time and transmits and receives data continuously. Therefore, according to our energy model, a node nearly spends 2.5 units of energy each second for being alive. Thus, if the node has 50 units of energy, the node can only sustain 20 transmissions before it dies. If we consider the flooding in Figure1, the information takes approximately 5 time units for a network of 100 nodes to travel from the source to the sink, the maximum network lifetime is 100 time units, which is very low as compared to uniform and non-uniform grid-based coordinated routing protocol.


### 4.7. Summary of Results

In varying the node density from hundreds to a thousand, we have analyzed the network lifetime for random node deployment. It has been shown that the non-uniform grid-based coordinated routing protocol is more effective than the uniform one. The comparison of network lifetime for the different grid structures with varying node density is shown in Table1.Table 1
Comparison of network lifetime for uniform and non-uniform grid structures.
Node   densityLifetime for Uniform grid (time units)Lifetime for Alternating non-uniform grid (time units)Lifetime for Source non-uniform grid (time units)Lifetime for Sink non-uniform grid (time units)100 nodes600880550800200 nodes68012507801170400 nodes18001840166012501000 nodes3000450040004300From Table1, it is shown that the alternating non-uniform grid structure is the better non-uniform grid structure for randomly deployed wireless sensor networks.


## 4.1. Assumptions

In simulating the non-uniform grid-based coordinated routing protocol, the following assumptions are taken into consideration:


### 4.1.1. The Energy Model

Sensor nodes consume energy while in idle mode (listening mode). The energy consumed is sometimes useful and other times not. So, one of the major constraints on the wireless ad hoc sensor networks is the excessive energy consumption, which leads to diminishing the network lifetime. It is important to note that the energy spent by a node in the transmitting, receiving, and idle modes may not be the same. The idle:receive:transmit ratio of energy is shown to be1.0:1.05:1.4 in [21], 1.0:2:2.5 in [22], and 1.0:1.2:1.7 in [11]. In our case, the energy spent by a node for idle listening is 1.0 unit, reception is 1.5 units, and transmission is 2.0 units. A counter array keeps track of the energy left in each node. If the node is elected as a coordinator node, it loses 1.0 unit of energy. Then, if the same node is used for transmission of data between nodes, it loses another unit of energy (i.e., a total of 2 units), but if it is a coordinator and only receives the information from a node and does not transmit the information to another coordinator, then, the node loses only 0.5 units of energy (for a total of 1.5 units). If a unit is not a coordinator but still is idle listening, it uses 1.0 unit of energy every one time-unit of simulation time.


### 4.1.2. Simulation of the Sensor Field and Deployment of Nodes

A sensor field that is close to an actual sensor field is assumed. The size of the sensor field is limited to a 2D space, 1000 m in the x-axis and 1000 m in the y-axis. The field is devoid of any obstacles. The sensor nodes are assumed to be actual sensor nodes. A Graphical User Interface (GUI) for observing the flooding simulations and the behavior of the uniform and non-uniform routing protocols has been implemented. The sensor nodes in the field can be deployed either uniformly or randomly strewn across the fieldThe number of sensor nodes in the network can be varied between 100 and 1000 nodes. The network consists of two fixed nodes that are of infinite energy, the source node and the sink node. This assumption applies irrespective of the type of deployment of the nodes, uniform or random. Simulations are thereby observed for different node densities to analyze the scalability of the non-uniform grid-based coordinated routing protocol.


## 4.1.1. The Energy Model

Sensor nodes consume energy while in idle mode (listening mode). The energy consumed is sometimes useful and other times not. So, one of the major constraints on the wireless ad hoc sensor networks is the excessive energy consumption, which leads to diminishing the network lifetime. It is important to note that the energy spent by a node in the transmitting, receiving, and idle modes may not be the same. The idle:receive:transmit ratio of energy is shown to be1.0:1.05:1.4 in [21], 1.0:2:2.5 in [22], and 1.0:1.2:1.7 in [11]. In our case, the energy spent by a node for idle listening is 1.0 unit, reception is 1.5 units, and transmission is 2.0 units. A counter array keeps track of the energy left in each node. If the node is elected as a coordinator node, it loses 1.0 unit of energy. Then, if the same node is used for transmission of data between nodes, it loses another unit of energy (i.e., a total of 2 units), but if it is a coordinator and only receives the information from a node and does not transmit the information to another coordinator, then, the node loses only 0.5 units of energy (for a total of 1.5 units). If a unit is not a coordinator but still is idle listening, it uses 1.0 unit of energy every one time-unit of simulation time.


## 4.1.2. Simulation of the Sensor Field and Deployment of Nodes

A sensor field that is close to an actual sensor field is assumed. The size of the sensor field is limited to a 2D space, 1000 m in the x-axis and 1000 m in the y-axis. The field is devoid of any obstacles. The sensor nodes are assumed to be actual sensor nodes. A Graphical User Interface (GUI) for observing the flooding simulations and the behavior of the uniform and non-uniform routing protocols has been implemented. The sensor nodes in the field can be deployed either uniformly or randomly strewn across the fieldThe number of sensor nodes in the network can be varied between 100 and 1000 nodes. The network consists of two fixed nodes that are of infinite energy, the source node and the sink node. This assumption applies irrespective of the type of deployment of the nodes, uniform or random. Simulations are thereby observed for different node densities to analyze the scalability of the non-uniform grid-based coordinated routing protocol.


## 4.2. Parameters Affecting Routing in the Network

There are numerous parameters that affect the performance of a wireless sensor network, some of which include type of node, battery life of the node, application of the network, and so on. As pertains to our study, the following parameters affect the performance of the sensor network:(i)
node deployment: uniform and random,(ii)
node density: 100, 200, 400, and 1000 sensors,(iii)
grid size: varies with type of grid being used,(iv)
receiver Sensitivity: −90 dBm,(v)
transmit power: −2 dBm,(vi)
path loss exponent: 3.5,(vii)
node energy: 50 units.The following parameters (node deployment, node density, receiver sensitivity, transmission range, and node energy) affect the lifetime of the network. The grid size parameter is only used for uniform grid sizes, and the delay parameter is used to delay the routing process, which makes it easier to observe the routing process as the information traverse from the source to the destination. If the delay parameter is not introduced, the routing process occurs instantaneously and is difficult to observe. Therefore, the delay parameter does not affect the network efficiency in any way. The default parameter values that affect the routing in the network are shown in Figure7.Figure 7
Default parameter values.The node density is initially taken to be 100 and is gradually varied from 100 to 1000 nodes. The grid size varies with the type of grid being used, from uniform grid to the three different types of non-uniform grids. The node energy is fixed to be 50 units and gradually decreases with the participation of the node in routing. The transmission range or the transmit power is the range within which a node can transmit its information. Beyond this range, the signal for that node is lost. The sensitivity of the receiver is fixed to be at-90 dBm, and the path loss exponent (which is usually between 2 and 5) is set to 3.5, where we consider the deployment of the sensor network in a relatively lossy environment. The flooding can be observed node-by-node or level-by-level.


## 4.3. Analyzing the Results

In order to analyze the efficiency of the protocol, we have to determine how long the network stays alive while allowing transmissions from the source to destination. Two variables are considered: (i) the normalized energy, total time for which the network is up and running, and (ii) the count of the total transmissions that the network allows between the source and the sink. The total transmissions allowed in the network are important to assure that the network actually allows a fair amount of information to be exchanged as long as the network is alive. Normalized energy is defined as the ratio of the total current energy of all nodes to the total energy of all nodes at the start of the simulation. Network time is kept track of by a timer that starts once the network starts to flood and stops when there is no communication link between the source and the sink nodes. The timer is set once the routing begins and stops only when the network partitions, thereby calculating the total time for which the network is alive. Figure8 shows an example of the total transmissions in the network over time for 100 nodes deployed randomly over the sensor field and the alternating non-uniform grid structure.Figure 8
Transmissions for each successful link established between the source and the sink nodes.


## 4.4. Uniform Node Deployment

Figures9, 10, 11, and 12  show the results for the uniform and the non-uniform grid simulations.Figure 9
Flooding for 100 nodes uniformly distributed in the field of1000×1000 m2 for the alternating non-uniform grid structure.Figure 10
Flooding between the coordinator nodes in a1000×1000 m2 network for a grid structure with the source node in nodes of size 200 m and sink node in grids of size 100 m each.Figure 11
Flooding between the coordinator nodes in a1000×1000 m2 network for a grid structure with the source node in nodes of size 100 m and sink node in grids of size 200 m each.Figure 12
Flooding in the network for 100 nodes deployed uniformly in the sensor field (1000×1000 m2) for a uniform grid structure.From these simulations, it has been observed that the uniform grid-based coordinated routing protocol is better suited for uniform node deployment.


## 4.5. Random Node Deployment

We consider a non-uniform node deployment of 250 nodes in this section.  For a given node density, the efficiency of the different grid structures is analyzed by comparing the network alive times along with the total transmission of each structure. The longest network structure does not necessarily have to possess the maximum transmissions, but it should still support a fair amount of transmissions between the source and the sink. Thus, three cumulative graphs are provided:(i)
the network lifetime of the network for each grid structure,(ii)
the total transmissions for each grid structure,(iii)
the energy depletion graph.Figure13 shows total transmissions allowed in the network for a node density of 100 nodes for all the grid structures. Figure 14 presents the network lifetime of the different grid structures with 100 nodes deployed randomly.Figure 13
Total transmissions allowed for the same node density of 100 nodes with different grid structures.Figure 14
Network lifetime for different grid structures for 100 nodes deployed randomly across the sensor field.It is observed that the lifetime of a non-uniform grid structure exceeds the total transmissions allowed by the uniform grid structure. Figure15 shows the energy plot of different grid structures for 100 nodes resulting in a gradual decline of energy in the network with time.Figure 15
Energy versus Time performance of the different grid structures.The maximum network lifetime is nearly 900 time units for the alternating non-uniform grid structure, and this structure better utilizes the entire energy in the network since the energy gradually decreases from 1.0 unit to nearly 0.28 units. Two graphs are considered for the analysis of the simulations: the graph that plots the total transmissions supported by the network (Figure13) and the graph that plots the energy depletion (Figure 15).Figure16, 17, 18, and 19 show graphs representing network lifetime and energy depletion for different node densities.Figure 16
Network lifetime for 200 nodes for different grid structures.Figure 17
Network lifetime for 1000 nodes for uniform and alternate grid structures.Figure 18
Network energy decrease for various grid structures.Figure 19
Network energy decrease with time for 1000 nodes.


## 4.6. Comparison with the Traditional Flooding Algorithm

The main disadvantage of the traditional flooding algorithm is that the information travels throughout the network before it can reach the destination. Flooding does not pick a particular route to send information from the source to the sink. Instead, a node is alive all the time and transmits and receives data continuously. Therefore, according to our energy model, a node nearly spends 2.5 units of energy each second for being alive. Thus, if the node has 50 units of energy, the node can only sustain 20 transmissions before it dies. If we consider the flooding in Figure1, the information takes approximately 5 time units for a network of 100 nodes to travel from the source to the sink, the maximum network lifetime is 100 time units, which is very low as compared to uniform and non-uniform grid-based coordinated routing protocol.


## 4.7. Summary of Results

In varying the node density from hundreds to a thousand, we have analyzed the network lifetime for random node deployment. It has been shown that the non-uniform grid-based coordinated routing protocol is more effective than the uniform one. The comparison of network lifetime for the different grid structures with varying node density is shown in Table1.Table 1
Comparison of network lifetime for uniform and non-uniform grid structures.
Node   densityLifetime for Uniform grid (time units)Lifetime for Alternating non-uniform grid (time units)Lifetime for Source non-uniform grid (time units)Lifetime for Sink non-uniform grid (time units)100 nodes600880550800200 nodes68012507801170400 nodes18001840166012501000 nodes3000450040004300From Table1, it is shown that the alternating non-uniform grid structure is the better non-uniform grid structure for randomly deployed wireless sensor networks.


## 5. Conclusions

Conservation of energy is a major area of research in routing in wireless sensor networks. Most of the routing protocols designed aim at conserving battery life of the sensor nodes, support scalability, and extending network partition time. The grid-based protocol has also been designed to keep the same view. Our non-uniform grid-based routing protocol was derived from the grid-based routing protocol. It follows the grid-based routing protocol in conserving power and surpasses uniform grid routing in dense wireless sensor networks. If the nodes in the network were not put to sleep to conserve energy, the node energy of all the nodes in the network would deplete with time and thus lead to early network partition. By using the non-uniform grid-based coordinated routing protocol the lifetime of the network was improved by a factor up to 1.5 times as compared to protocols that do not let the nodes enter sleeping mode. The possible future extensions to our work can be listed as(i)
Implementation on motes. The non-uniform grid-based routing protocol is simulated in Matlab. This can be extended onto actual motes and the results observed.(ii)
Mobility of nodes. The nodes in our network are stationary. Mobility may be added to the nodes in the network and the working of the protocol can be observed.(iii)
Irregular distribution of nodes. The protocol has only been simulated for node density distributed evenly across the network. There are no significantly dense area and sparse area in the network. The working of the protocol can be extended to observe results for dense and sparsely populated areas across the network.



---

*Source: 491349-2009-11-10.xml*