An Efficient Priority Based Routing Technique That Maximizes the Lifetime and Coverage of Wireless Sensor Networks ()
1. Introduction
Recent advances in Nano-electromechanical systems (NEMS) paved the way to new applications for Wireless sensor networks [1-3]. Sensor networks comprise a large number of small-size nodes with sensing, computation, and wireless communication capabilities. These nodes collaborate together by performing desired measurements, process measured data, and transmitting it to some special nodes, commonly referred to as sink node [2]. One limitation to sensor nodes is the limited battery capacity [2,3]. Usually, the sensor nodes are deployed in a hard to reach areas. For that, it has a limited lifetime. Many researches in the literature have the objective to maximize the lifetime of sensor nodes by developing new routing techniques [4]. Hence, it is vital to develop solutions that are energy efficient and maximizing the network lifetime [1,4].
Energy depletion is mainly due to data reception and transmission, where the later is large when compared to data reception [2]. There are many ways for data to be received (collected) or propagate to end (sink node) node. Either by, single-hop transmission [5,6], multi-hop transmission, or cluster-based transmission [1]. Single-hop transmission is the simplest transmission method which tries to communicate directly with the sink node, but this consumes higher power rates. Multi-hop transmission delivers data by forwarding it to one of its adjacent nodes, which are closer to the sink node; the data propagate from the source node to the sink from one node to another until it reaches the sink node. A drawback of this methodology, nodes closer to the sink must forward data received from other nodes as well as transmitting their own data to the sink base station. For that, their batteries drain quickly more than others, and as results produce blind areas and cause network partitions. In cluster based transmission [5,6], nodes are grouped into clusters and one node which is the cluster head is responsible of sending other nodes data to the sink.
In our work, we are concerned with the first two methods and we try to balance between them when necessary to gain higher lifetimes and coverage as we will see later in the discussion. We accomplished this by developing energy-aware routing heuristics (pERPMT) that tries to optimize network lifetime by managing routes in a way that will save power as much as possible so that the lifetime of the network is maximized.
Prolonging the lifetime is the same as increasing the coverage of WSN. By prolonging the lifetime of sensor node, the vicinity of sensor node area is kept covered [2,3]. One of our purposes was to keep all or most of the network nodes active (alive) most of the network lifetime.
The reminder of the paper is organized as follows: Section 2 introduces the wireless sensor networks mathematical model. In Section 3, we provide simulation and modeling of pERPMT. Simulation data and discussion of pERPMT is introduced in Section 4. Section 5 is concluding the paper.
2. Literature Review
The main problem in most of energy-aware routing heuristics is that they find the lowest energy route and use it for every communication [2,7,8]. Using low energy path more frequently will leads to energy depletion of the nodes along that path especially the nodes closer to the sink. Once the sensor node dies it leads to network partition that cause blind areas (areas that can not be sensed by any node). Some heuristics have been proposed to solve this problem by taking into account the residual energy at nodes and delay the depletion of nodes that are already low in energy [9,10]. In [11], the researchers proposed the MRPC (Maximum Residual Packet Capacity) lifetime-maximization, which depends not only on the residual battery energy on a node, but also on the expected energy spent in forwarding a packet over a specific link. MRPC selects the path that has the largest packet capacity at the node which has the smallest residual packet transmission capacity. They also present CMRPC, a conditional variant of MRPC that switches from MRPC only when the packet forwarding capacity of nodes falls below a predetermined threshold. In [12], they proposed the CMAX (Capacity Maximization). The capacity is the number of messages routed over some time period, heuristic which provides a single path for each message (no multiple paths) chosen with respect to the link weights. The heuristic makes admission control. That is, it rejects some routes that are possible in order to increase lifetime. In [13,14], the authors introduced localized heuristics to maximize lifetime in which they define a new power cost metric based on both nodes life time and distance-based power metrics. They also show that the required transmission power can be reduced if additional nodes placed at desired locations between two nodes at distance D. Park and Sahni [15] proposed the OML (Online Maximum Lifetime) heuristic where two shortest path computations are done to route each message. In order to maximize lifetime, we need to delay as much as possible the depletion of a sensor’s energy to a level below that needed to transmit to its closest neighbor. Al-Sharaeh, et al. [16], introduced a Multi-Dimensional Poisson Distribution Heuristic to better evaluate the routing heuristics; by taking into account earth’s terrain and the multi-dimensional concept and this is done by the method of placement of sensors and the probability of the connections between sensors nodes. The positions of the sensors (x and y-coordinates) are chosen either from a Uniform or Poisson distributions. A major effect on the performance of different routing heuristics was gained. In [17], they introduced a study of the deployment strategy effect on maximizing the lifetime of the wireless sensor networks; it shows that changing the statistical techniques of distribution—such as Poisson Distribution— that meet real environment requirements affect the performance of maximizing lifetime routing heuristics in many aspects, such as average lifetime and network capacity. In [9] the authors prolonged the life time by proposing new heuristic based-on dividing the energy of nodes into two parts. The heuristic named an Efficient Routing Protocol Management Technique (ERPMT). The Alpha part reserved to own data transmission, while the Beta part for other nodes data (i.e. to relay other nodes data). One draw back of their work is that, the nodes close to the sink nodes, say, one hop, deplete their energy very fast as compared to two hops.
In this work, we proposed a heuristic that delays the depletion of one-hop nodes by adding a priority metric. The priority number that we have is based on two factors. One is the number of hopes and the second is based on the energy level of the node. In order to have fair comparison, we perform a battery power management at the node level with and without priority based scheme, such that the total power of the sensor battery is divided into two parts; the first is dedicated for sending data generated by the sensor itself, while the other is for data relays from other sensors [9,10]. Our approach can be used along with any existing routing heuristics. For that, we compared pERPMT against two well known routing heuristics: OML, CMAX, and ERPMT.
3. WSN Mathematical Model
A wireless sensor network is represented by a directed graph
, where V is the set of nodes, and E is the set of edges between these nodes, there will be a directed edge from node v to node u (i.e.
) if u and v in the range of each others. Such modeling can be used to represent Wireless Sensor Networks (WSN). for each
, in case of single hop transmission from sensor u to sensor v, the current energy in sensor u, ce(u) is represented by Equation (1) [12]
(1)
where ce(u) is the current energy in sensor u, such as 
and 
is the energy required to make a single hop transmission from sensor u to sensor v, such that
. We also assume that the receiver of a message consumes no energy during message reception. Thus, the current energy in sensor (v) is not affected by the transmission from u to v. In our work the energy is divided into two ratios, one for data originated from the node (α), the other is for relays from other sensors (β); if the data is originated from the node itself, it will use the energy from the first ratio otherwise it will use energy from the other ratio.
An adjacency matrix can be used to represent directed graphs of WSN [12-16]. The adjacency matrix of a finite directed graph G on n vertices (where
), is the n × n matrix such that, the non-diagonal entry
, represents the existence of an edge from sensor i to sensor j. While the diagonal entry 
is assigned by zeros here because we assume that there is no internal loops in the WSN.
There exists a unique adjacency matrix for each graph. For example, Figure 1(a) shows a simple representation for sensor network S. A directed graph is used, where the represented nodes are sensors, and the edges represent the existence of edges between the sensor nodes. Figure 1(b) shows the adjacency matrix of the sensor network S modeled in Figure 1(a). It is obvious that Figure 1(b) depicts a network that has been implemented using one dimension to represent sensors. Such representation for sensors has been used by Al-Sharaeh, et al. [16].
In most of the studies to represent a sensor location as well as connectivity a random number from Uniform distribution was used [12]. It is better to use the Uniform distribution for flat terrain environment, because the sensors can be distributed evenly as shown in Figure 2, but the real environment usually characterized by terrains, such as in case of sensors deployed in high mountains or deep oceans. In this case, the Uniform distribution does not give a good realistic that match the terrain changes. For that, it is better to use Poisson distribution as it is best fits the asymmetric environment [16,17]. Figure 3
(a) (b)
Figure 1. Representation of wireless sensor network, (a) Simple graph network representation; (b) Corresponding adjacency matrix representation.
Figure 2. 3D Sensor nodes distribution based on Uniform distribution.
Figure 3. 3D Sensor nodes distribution based-on Poisson distribution.
shows sensor nodes distribution based on Poisson distribution, it is clear that the sensors location concentrated around the mean. This kind of deployment imitates a deployment of sensors via airplane in a terrain that is close to valleys. For fair comparisons with the heuristics in the literature we used Uniform distribution.
An example of sensor deployment application is avalanching predictions, mountainous terrains portrait all the challenges that may face sensor deployment in order to make full coverage. For that, deployment strategy has a major effect on evaluating a routing heuristic. This is due to the fact of terrain changes of real life environment. Figure 4 depicts the landscape of typical environment that ranges from flat land, hilltop, cliffs, valleys, to mountains top. In order to make fair comparison between different routing protocols, a major attention should be paid to the deployment strategy. This factor can be taken into consideration by the way we generate the random graph that both simulate the position as well as the connectivity that at the end will simulate the way the sensors are connected.
To determine connectivity between the nodes, we used a threshold which was equal to the mean of the dimensions of network nodes. All nodes were recursively checked by comparing their X-, Yand Z-dimension in case of 3D deployment with the mean of the Euclidian dimensions for these 3 dimensions (X, Y, and Z) for all network nodes. For the case of 1D, we only work with just the X dimension. Each node with a dimension value greater than or equal to the mean of the same dimension will be considered connected, otherwise it will be disconnected [16].
4. pERPMT Heuristic
We have used two well known heuristics to apply pERPMT on, these two different heuristics were proposed to extend the lifetime of the network and they obtained the best lifetime in the literature, CMAX and OML.
Figure 5 shows the details of our proposed heuristic, which is pERPMT_C and it is an enhancement over the CMAX, where we assume that the current energy in each sensor is divided in two ratios, the first is for the sensor originated data (α), the other is for relays from other sensors (β). For each routing step there are three steps. In