Mathematical Model with Energy and Clustering Energy Based Routing Protocols as Remediation to the Directional Source Aware Routing Protocol in Wireless Sensor Networks ()
1. Introduction
A sensor is a little tiny battery-powered device that can sense, compute and communicate. The envisaged size of a single sensor node can vary from a shoebox-sized node down to the size of a grain of dust. That’s why it’s also called a “Smart Dust” [1]. For efficient monitoring, sensing, capturing and thereafter sending and transferring the information, a set of sensors must interconnect, communicate and transfer the sensed data; this group forms a sensor network. Wireless sensor networks (WSN) are complex distributed systems of nodes with data sensing, processing, storage capability and wireless-communication interfaces. They have a wide variety of applications and are becoming more and more utilized in our daily lives. Examples of these applications include but are not limited to tracking vehicles and traffic movement on roads, monitoring a forest for fires, finding and tracking soldiers in military applications, monitoring oceans and seas, and smart spaces … [2]. They are also used in medical applications, hospitality services, etc.
Previously, sensor networks consisted of small number of sensor nodes that were wired to a central processing station [3]. However, nowadays, the focus is more on wireless, distributed, sensing nodes. However, WSNs present many constraints; the major ones are energy efficiency, localization and routing. The paper will focus on the routing aspect of WSN.
This paper is organized as follows. After a brief introduction, section 2 briefs the principle of both the DSAP and MDSAP [4] routing protocols used in WSNs and highlights their respective limitations. In section 3, the new EBP protocol is proposed. CEB-P is introduced in section 4. Section 5 discusses a new mathematical model to optimize the distribution of sensor nodes in a wireless sensor network. Finally, section 6 goes over the main points and outlines our future research.
2. Directional Source Aware Routing Protocol (DSAP) and Modified DSAP
2.1. DSAP and MDSAP Principles
DSAP is a routing protocol that depends on the local information available from the neighbors of the transmitting node [5]. It is based on the idea of directional routing where each node needs to know the direction of the destination so it can forward the packet in that direction.
Two algorithms for DSAP have been proposed. The first one deals with the directional value as a metric to be used to find the final destination. The second one uses the directional value and a power aware metric to route the packet to the final destination. This is achieved by considering the maximum available power and minimal directional value in the node route selection.
The two existing types of the DSAP algorithm present many disadvantages: in the power aware case, sometimes the source chooses the path with the maximum power even if it’s not the shortest path. On the other hand, the power of the sensor will decrease while passing through it. This can lead to an unacceptable situation because some nodes will lose their power faster than other nodes. Also, sometimes the source are not obliged to take the path with maximum power. It can take the shortest path and leave the path with maximum power available and ready for use in case an urgent event happens.
A more reliable protocol, a modified version of the DSAP protocol noted MDSAP, was proposed making a compromise between the shortest path and the maximum power [6]. In MDSAP, the messages exchanged between the different sensor nodes are divided into three categories [7]: Low priority messages, high priority messages (urgent messages) and medium priority messages, and each type of messages will be treated and routed differently.
2.2. Limitations of DSAP and MDSAP
DSAP and MDSAP were simulated using OMNeT++, a network simulator useful for debugging, for illustration and performance evaluation purposes. The results showed that, in MDSAP [2], the lifetime of the network increases by 22% when using only high priority messages, 55% with medium priority, 77% with low priority and 88% with random priority when it is compared with the regular DSAP.
Even though the MDSAP showed better results than DSAP, there are still some important limitations that need to be considered.
1) The network topology is assumed static: grid architecture allows the calculation of the directional values of each node. A possible enhancement would be the proposition of a dynamic ad-hoc network; this topology can be adequate in some applications where non fixed network nodes (mobile nodes) are needed.
2) The classification of messages into categories based on priorities might not be needed in some applications where all messages should be equal in priority.
3) The problem of the barrier nodes at the destination proximity. Whatever is the technique used to send the information from the source to the destination, a message will not be able to reach the destination when all the neighbors are down.
To address all these, a new algorithm noted energy based protocol (EBP) was proposed. EBP is presented in the next section along with its simulation, advantages and limitations.
3. Energy Based Protocol (EBP)
The main objective of EBP is to maximize the wireless sensor network lifetime. To achieve this, the hypothesis is to consider the fact of using, to the maximum, the power available at each sensor of the network.
EBP is based on the idea of distributing sensors with different levels of energy over an N*N grid topology, so that the number of paths over the grid is N. This distribution is specified by EBP algorithm which will be described by a special case of a 5 * 5 grid topology, thus we have 5 paths.
The numbers shown in Figure 1 below define the level of energy that the sensor must have: 1 means E0, 5 means 5 * E0 etc…, E0 being the default sensor battery level.
First, the source and destination are specified as shown on the Figure 2 below. If the node has L = 1, it means the number of nodes on this diagonal is 1. To compute the level of energy at the source node, a simple mathematical operation is performed: N/L = 5/1 = 5, thus the energy is equal 5 × E0. As for L = 2, two nodes exists, this first node from below has an energy N/L = 5/2 = 2.5, so the level of energy is the rounded value, thus it is Ceil (2.5) = 3. For the second node the operation is calculated by subtracting N from the level of energy of the first node, this process will fix the energy of this node to 2 (i.e. 5-3).
This operation is repeated on the remaining diagonals of the first half of the grid to reach L = 5 where all nodes will have energy 1 * E0.
As for the second part which is highlight by the yellow color, it is a reverse symmetry of the first part going from L = 4 to reach the destination at L = 1.
Once an event is detected at the source, this information must be routed to the destination following the directional values process using EBP routing protocol.
3.1. Simulation of EBP Using TinyOs
TOSSIM [8], the simulator of TINYOS was chosen. This simulator provides
Figure 1. Sensors power distribution in a 5 × 5 network grid.
Figure 2. The diagonals of EBP topology.
direct interactions with the TinyOS enabled motes, i.e. with real sensor networks.
Figure 3 shows the paths chosen to reach the destination using EBP protocol by respecting the directional value process already addressed in DSAP. The power of the nodes using this path will be decremented. For simplicity of calculation, the assumption is that each message will decrease the node’s power by one. After establishing the first path and modify the energy accordingly, a second path is chosen.
3.2. Evaluation of EBP
In our EBP algorithm and after selecting all different paths, the simulation showed a drop down on all the nodes without leaving any missed energy. The network lifetime is maximized where each sensor’s power is fully used. On the other hand, the algorithm overcomes the limitation of same type of priority and the barrier across the destination. In addition, all nodes and paths will be taken making the destination always reachable.
Even though EBP is a promising protocol and showed better performance in terms of energy and efficiency comparing with MDSAP, it is still difficult to apply in real-time environment. Three limitations still exist: the inability to apply different energy on each sensor according to the distribution assigned by the energy based protocol, inability to detect information from multiple sources and finally the grid topology itself.
In the next section, a modified version of EBP noted clustering energy based protocol (CEB-P) is proposed to simplify the implementation of such algorithm (EBP) and resolve the Energy level limitation. Multi-source and nodes mobility are described in next sections.
4. Clustering Energy Based Protocol
The clustering energy based protocol (CEB-P) [9] aims to physically distribute
Figure 3. Paths chosen to route messages in EBP.
the number of sensors in one area called cluster to get the total power of the assigned value in one EBP node, having a fixed battery level for each cluster node as shown in Figure 4. Clustering like LEACH [10] and other protocols [11] [12] are needed because it is almost impossible, in real implementations, to control each sensor battery level.
Suppose that we have a mote of index 5 and the energy of each deployed sensor is 5, then the total energy at this mote is 25. To have this energy, a number of motes of equal energy are placed together as shown in Figure 5. In addition, a cluster head must be chosen and define a status for every mote (sleeping/Active). Only the cluster head is active to transmit the message, while all other nodes in the cluster are in a sleeping mode.
CEB-P needs to identify the level of energy needed at every node. Then, it classifies the energy level of the sensor chosen for the application and computes the number of sensors required. For example, if E0 = 5 and if a sensor k is chosen to have a value of 5, then we need 5 sensors in place of k to reach a total of energy of 5 * E0 = 25.
After placing the sensors in a cluster, the cluster head must be set. To differentiate between a cluster head and any other mote in a cluster, we have defined a flag. If the flag is equal to one, then this mote is the cluster head and is the only active mote in the cluster. All other motes will have a flag of zero and are thus in a sleeping mode. When the cluster head sense any information and send the message, it will change its status form Active to Sleep, thus changing its flag from 1 to 0. The next mote in the cluster will then handle the responsibility of becoming the cluster head and will take the id of the previous cluster head plus one. For example in Figure 5, if mote 0 was the cluster head then mote 1 will be
Figure 4. Example of cluster in 5 × 5 network grid.
Figure 5. Example of cluster representation in CEB-P.
next cluster head.
Comparison of CEB-P with MDSAP and EBP
To illustrate the differences between the different protocols MDSAP, EBP and CEB-P, a comparison was made of their performances in terms of number of messages sent over the network, the energy used ratio (energy used over the total network energy) and energy lost ratio (energy lost over the total network energy). To achieve this, a series of simulations were made where seven parameters are to be determined:
· The grid topology (grid of 5 × 5, 6 × 6, 7 × 7…etc).
· The total number of nodes in the network: in MDSAP and EBP each node is constituted of one sensor; in MDSAP all the sensors have the same power level whereas in EBP each sensor has a different power level based on the architecture of EBP. In CEB-P, each node is constituted of many sensors to meet the total energy required by EBP in each node.
· The total network energy: it’s the sum of the different power levels of all the sensors of the network
· Messages sent: the number of messages sent over the network before disaster. We are assuming that each message, while passing through a node, will decrease the total power of the node by 1.
· Energy used: it’s the ratio of the energy used (consumed energy) to send the total number of messages over the total network energy.
· Energy lost: it’s the remaining energy (remaining power at all nodes) after transmitting all the messages.
Here in Table 1, a comparison is made for the total number of messages sent in MDSAP, EBP and CEB-P before the network disaster (Figure 6). We can clearly notice that the highest number of messages sent is obtained with CEB-P.
In Figure 7, the energy used ratio in MDSAP, EBP and CEB-P is compared. The maximum optimization is obtained with EBP. However, as explained before, EBP could not be deployed in real scenarios. CEB-P shows a good energy used ratio compared to MDSAP while at the same time, CEB-P is able to transmit a higher number of messages than MDSAP.
5. Mathematical Model
5.1. Introduction
In wireless sensor networks, when the information is sent towards the destination, an important phenomenon is carried out: “the routing” which consumes a large quantity of energy where the transmission and the reception of the messages by a node also cost a considerable energy. However, these nodes are equipped of a small battery generally nonrenewable.
The major constraint in a wireless sensor network is the energy of the different nodes constituting this network: this energy determines the lifetime of the network. In other words, using efficiently the available energy maximizes the
Table 1. Summarizes the obtained results.
CEB-P vs. EBP and MDSAP.
network lifetime. For that, the use of a mathematical model (analytical) appears important to optimize the consumption of energy, thus increasing the lifespan of the network.
Different methods were proposed and some implemented to maximize the network lifetime. Some rely on the physical layer or MAC layer, others consider the routing aspect… The main objective of MDSAP, EBP and C-EBP routing protocols, proposed in previous sections of this article, is to efficiently use the available power in order to maximize the network lifetime and make the destination the most reachable.
Figure 6. Number of messages sent in MDSAP, EBP and CEB-P.
Figure 7. Energy used ratio in MDSAP, EBP and CEB-P.
In this section, a new mathematical model which can be applied to a grid topology of WSNs is proposed.
5.2. Proposed Mathematical Model
Let us consider the linear case where all the nodes are placed next to each others as shown in Figure 8 below:
Here, each node transmits its own message and the messages of the precedent nodes. So, the noted node i means the number of messages transmitted by this node i.
The aim is to get a mathematical formula that consists of finding a relation between the distance, the network lifetime and the number of sent messages.
The mathematical terms are as follows:
·
is the distance between the consecutive nodes i + 1 and i.
·
is the energy decrease of the node in function of the distance
, it is the energy lost per message.
· n is the network lifetime
· δ is a constant between 2 and 4 [13].
We also note
or E(i,t) the energy at time t on node i and
the initial energy (t0) on node i.
In general, we have:
(1)
In the below sections, three case will be elaborated. In the first case, the sensor nodes are uniformly distributed on a line. In the second, the wireless sensor nodes are set on a line in a random way. As for the third case, the nodes are set out again in the form of a grid on a rectangular ground.
In certain cases, we will try to find a well-defined relation which will enables us to find the distance between two successive nodes.
5.2.1. Uniform Distribution
Two variations in the linear uniform distribution are studied, in function of r and in function of t.
1) Variation in function of r
Let us consider the interval [r; r + dr]. On this interval, N nodes numbered from 1 to N are distributed, where the first node is placed on the edge r and the Nth node on the edge r + dr.
The energy available on node N after N messages sent at time t is equal to:
(2)
The initial energy available on Node 1 at timet is equal to:
(3)
By substituting Equation (3) from Equation (2), we get
(4)
By dividing Equation (4) by dr, we will have:
(5)
where α(r) indicates the decrease rate of the energy in function of the distancer.
From Equation (1), we have:
If we set ρ = density of node on the interval [r, r + dr], then Equation (4) implies:
(6)
By comparing Equation (5) to Equation (6), we get:
(7)
where
2) Variation in function of t
After sending N message, the energy of each node is equal = E0 – Nα(r)
Now, the calculation of the variation of the energy of a node between two times in the interval [t, t + dt] is needed.
From Equation (4), we can conclude:
(8)
Let us note that each node sends the received messages and its own message i.e. that the ith node sends (I − 1) + 1 = i messages; therefore one can notice that the number of the node is equal to the accumulation of messages.
At the same node, if we indicate by
the energy of the ith node at the moment n + 1 and
its energy at moment n, we can have:
(9)
where Idt = the number of messages
We finally have the following:
From Equation (7), we conclude that
(10)
Or Equation (9) gives:
(11)
By replacing the value of α(r) in Equation (11) by the value of Equation (10), we get:
where
(12)
So, Equation (12) results in having:
(13)
Having the result in Equation (13), it is concluded that we achieved the same consumption if we take the case in function of time or distance to route the information from one node to another.
5.2.2. Non-Uniform Distribution
In this section of non-Uniform distribution [14], it is indicated by ri the distance between the ith node and the following node.
From Equation (1), we have
1) Variation according to the distance
From Equation (2), we can conclude that
(14)
2) Variation according to time
If we look to the variation of energy in function of time and the position of the nodes while examining Equation (8), we can conclude that:
From Equation (11), we have:
(15)
This implies that:
(16)
where n = Network Lifetime
When the system “turns off” at the moment n, this will be the lifespan of the network then:
(17)
with
= initial Energy of ith node.
The aim is maximize n (the network lifetime) in a way to drop down the energy on all nodes at the same time. So, n must be constant which implies:
give
(18)
Thus,
(19)
Notice that when i increases (approaching to the destination), the distanceri decreases, which is ordinary since the ith node will send a larger number of the messages, so it must be closer to the destination so that its energy is enough.
Or if
and we substitute in Equation (19), this will imply:
Then
(20)
From the Equation (20), it is concluded that when i increase, the distance between the nodes decrease. So, the nodes of Figure 9 should be placed as follows.
5.2.3. Radial Case Uniform Distribution
In this part where the destination is in the center and the sources are set out on the edge, we make, on each way which connects the source with the destination, the same calculation that we have made in the linear case.
We obtain the already found relations from Equation (1) and (6):
With ρ the density of the nodes between the source and the destination and
where
is the decrease rate of energy with each message.
1) Case of a grid (2D) N × N
An N × N sensor nodes distributed in a square topology is considered as shown in Figure 10. The first stage is to calculate the number of paths which passes by each node according to the EBP protocol:
Then, the N paths are determined which connect the source which is at the higher left top of the grid and the destination which is at the lower right level. Here, we should state that the distance on any path between the source and destination is equal to
due to the fixed rectangular topology.
Figure 9. Non-linear uniform distribution.
This determination is done by using the Directional value of the DSAP method which consists in comparing the values
of neighbor nodes. The message will be transmitted to the node which has the largest value (this value will be replaced by
). If the neighbors are equal quality, the message will always be transmitted by the node which is on the left.
Once these routes are found, they are directly saved.
Now, let us consider that:
φ: (K, L) → (I, J) is not bijective.
K L is the route of the path where ij is index of the nodes in the topology
.
This function indicates the position of the node of index (I, J) “in the grid” and has its position in the kth way (which is already saved).
In this grid, at moment n the energy of the node of index (I, J) = φ(K, L) is equal to the initial energy minus the energy dissipated by the transmission of the messages.
To simplify terms, we will directly use:
and
(21)
where
is equal to the number of routes which pass by the node of index (i, j), n is the network lifetime and And
is the distance between the node on the kth path.
At the end, the system “turn off” then the energy of the node is null.
Thus
(22)
Also, from Equation (22), we conclude that
Which imply that
(23)
Or
length of the way with different distances between nodes in each different route.
Then, from Equation (23) we have:
(24)
So, the conclusion from Equation (24) is that the network lifetime is independent from the distance as shown in Equation (25):
(25)
5.3. Interpretation
In our proposed mathematical models, it is noticed from Equations (7) and (12) in the uniform distribution that the same energy is consumed in function of time or distance.
As for the non-uniform distribution, we can conclude that the distance should decrease when approaching to the destination. This is normal because it will need to tolerate more number of messages near the destination. If such scenario is applied, we can benefit from the barriers problems when routing the information towards the sink node. The same interpretation is applied to the radial case, but here we have multiple destinations.
As for the radial case which is strongly applied in our EBP routing algorithm, the conclusion is that the network lifetime can be independent form the distance as shown in Equation (25).
Moreover, If we consider
We have,
so:
(Inequation (1))
We can conclude from the Inequation (1) that there is a relation between the Network lifetime (n) and the number of sensor nodes (N). So to calculate the network lifetime of a grid N x N wireless sensor network, all what it needs is to know the number of nodes deployed in the ground.
6. Conclusions
In this paper, the DSAP routing algorithm principle is explained and presented its current limitations. Some enhancements were presented through a modified version called MDSAP, which is based on the type of messages exchanged between the sensor nodes. However, due to the main limitation found in the simulation of MDSAP concerning energy barriers in the destination proximity, the energy based protocol (EBP) is proposed as a solution. Simulation results in TinyOs evaluating the performance of this protocol were also presented.
The main constraint of EBP is to assign specific energy according to the distribution set in the algorithm which is quite impossible actually in a real-time environment. For this purpose, clustering energy based protocol (CEB-P) was proposed to be able to apply such distribution in real life. CEB-P distributes some sensors in each node’s place set by EBP to approximately reach the total designated power. A detailed comparison was carried out from different simulations to show the efficiency of the CEB-P in relation to the other stated protocols. However, CEB-P still deals with one source sending the sensed information; an enhancement could be the proposition of a multi-source routing protocol [15] and this will constitute an interesting continuing of this article.
Routing is one of the constraints in sensor networks. The major objective behind the implementation of an adequate routing algorithm is the minimization of energy consumption, which can lead to maximizing the sensor network lifetime. Energy consumption is a major constraint in WSNs. A mathematical model addressing this energy consumption problem was finally proposed at the end of this paper.