An Energy Efficient Routing Protocol for Wireless Sensor Networks using A-star Algorithm

Abstract

Sensors are regarded as significant components of electronic devices. In most applications of wireless sensor networks (WSNs), important and critical information must be delivered to the sink in a multi-hop and energy-efficient manner. Inasmuch as the energy of sensor nodes is limited, prolonging network lifetime in WSNs is considered to be a critical issue. In order to extend the network lifetime, researchers should consider energy consumption in routing protocols of WSNs. In this paper, a new energy-efficient routing protocol (EERP) has been proposed for WSNs using A-star algorithm. The proposed routing scheme improves the network lifetime by forwarding data packets via the optimal shortest path. The optimal path can be discovered with regard to the maximum residual energy of the next hop sensor node, high link quality, buffer occupancy and minimum hop counts. Simulation results indicate that the proposed scheme improves network lifetime in comparison with A-star and fuzzy logic(A&F) protocol.

1

Introduction

Recent advances in micro-electro-mechanical systems (MEMS) and wireless communications have highlighted the significance of WSNs as essential reporting devices. Indeed, sensor nodes in WSNs are deemed to be resource constrained in terms of energy, communication range, memory capacity and processing capability. WSNs include specifications and applications such as target tracking, environmental monitoring and battlefield applications. The main purpose of WSNs is to disseminate the information from the source to the sink in multi-hop scheme [1].

In general, since energy sources are scarce and constrained and batteries are low-powered, energy-efficient data forwarding is supposed to be a critical challenge in WSN applications. As Fig. 1 illustrates, sensor nodes send fire detection information to the sink node efficiently in real-time. Hence, it can be argued that energy consumption should be managed so that network lifetime of WSNs is significantly prolonged. On the other hand, the majority of routing algorithms in WSNs require reliable and real-time data forwarding to the sink node in many-to-one scheme [2, 3]. Thus, energy-efficiency and QoS-based data routing are considered as a crucial challenge in WSNs and there is a trade-off between energy-efficiency and QoS parameters [1, 3–5]. On the other hand, nonuniform energy consumption and load unbalancing are vital problems in many routing protocols of WSNs which result in network partitioning. Consequently, network partitioning has a negative impact on the successful packet delivery to the sink and hence it hinders the performance and the proper function of WSNs. With regard to the significance of WSNs' applications, reduction in the packet delivery ratio will have a negative impact on the energy consumption and hence network lifetime of WSNS.

Figure 1.

Energy-efficient data forwarding in wireless sensor networks.

In WSNs, transmission and reception of data packets are considered as the chief sources of energy consumption [6, 7]. As a result, to design energy-aware routing protocols for WSNs, we must efficiently control and manage energy consumption. Due to many-to-one traffic scheme, lack of energy consumption management will result in the quick loss and destruction of energy resource of the nodes near the sink; this is referred to as energy hole problem [8]. In the majority of routing algorithms, the periodical choice of the optimal path and the energy hole problem together impact on the life time of WSNs. As a result of these two problems, the network will be partitioned and the WSN will not be able to accomplish its intended critical function. The major problem in such routing protocols is that they minimize total energy consumption at the expense of non-uniform energy drainage in the network.

As regard the above-mentioned important challenges in WSNs, improving network lifetime is considered to be a crucial challenge for such networks and should definitely be taken into account in the design of routing protocol.

In line with the mentioned purpose for enhancing network lifetime, the following parameters should be taken into consideration: i) energy consumption balancing, ii) load balancing, iii) the selection of the shortest path, and iv) reducing packet retransmission with concern to packet reception rate. In this paper, we have proposed a new energy-efficient routing protocol (EERP) to maximize network lifetime of WSNs using an optimal aggregated cost function and A^* algorithm.

To achieve the above-mentioned purpose and to avoid network partitioning, the proposed algorithm takes into account such parameters of nodes as high residual energy, link quality, free buffer, and minimum hop count in order to select the optimal path. Considering the above-mentioned parameters can improve the lifetime of WSNs thanks to efficient and balanced energy consumption. As regards high residual energy, the selection of nodes with the highest remaining energy level will spread out the traffic load and subsequently it will prolong the WSN lifetime.

Moreover, in line with the parameter of free buffer, those nodes which have more free buffer should be selected so as to avoid traffic load and hence excessive energy consumption. We carried out extensive simulations in MATLAB to evaluate the performance of the proposed EERP algorithm. Simulation results indicated that EERP algorithm has better performance than A&F [9] in term of network lifetime.

The rest of the paper is organized as follows: section 2 presents the related work on improving network lifetime. Section 3 introduces and discusses the proposed scheme. Section 4 describes the simulation of EERP and the performance evaluation. Finally, section 5 concludes the paper.

2

Related Works

Network partitioning which is caused by the energy hole problem in WSNs and unbalanced energy consumption are regarded as critical challenges in WSNs and hence will affect the network lifetime of WSNs in routing protocols. Thus, prolonging network lifetime in WSNs has received significant consideration. In recent years, energy-efficient routing algorithms have been proposed to enhance the network lifetime of WSNs. In this section, we will review the literature on improving and prolonging WSNs' lifetime.

Many data forwarding schemes use clustering techniques in order to reduce and balance energy consumption via data aggregation and periodical selection of different nodes as the cluster head (CH). LEACH [6] is regarded as an important clustering protocol that has been proposed for WSNs. In this protocol, all cluster heads transmit their aggregated data directly to the sink. In a former paper [3], we proposed an energy-efficient QoS-aware Geographical Routing (EQGR) protocol for WSNs which maximizes network lifetime and uses optimum cost function to select the best neighbour node. In [10], the authors presented Hybrid Multi-Hop routing (HYMH) protocol which combined flat and hierarchical multi-hop routing algorithms with data aggregation scheme in order to optimize energy consumption and improve the lifetime of WSNs. In [11], a new scheme was proposed for improving the lifetime of WSNs with anycast and optimal sleep-wake scheduling for each sensor node. In [12], the authors introduced a novel sleep-scheduling method called VBS (Virtual Backbone Scheduling). VBS uses overlapped backbones which work alternatively to prolong the network lifetime [12]. In this work, only backbones forward data and the remaining nodes turn off their radios in order to conserve and save energy. The backbone-node selection is in a rotation scheme that balances the energy consumption of all nodes.

Alshavi et al. in [12] proposed a new routing protocol to increase WSNs' lifetime and balance energy consumption using a combination of fuzzy approach and A-star algorithm. In their proposed method, each node has to send their criteria to the sink in each round to determine routing schedule which will result in more packet congestion; hence, the inevitable consequence is higher consumption of energy and packet dropping. In [5], a new routing algorithm was proposed which used A^* algorithm to find the optimal path from the source node to the sink node based on node's minimum energy level. If the energy level of each node is less than the threshold level that node will not participate in the routing operation. In [13], the authors proposed an efficient routing protocol, called relative identification and direction-based sensor routing (RIDSR), which sorted out the routing loop problem and selected a shorter distance for the routing process. They also proposed a new energy-efficient algorithm, referred to as enhanced relative identification and direction-based sensor routing (ERIDSR) [13] which combined a triangle rule to determine a sensor node in order to save more energy.

Hence, having reviewed the literature related to increasing the network lifetime of WSNs, we can conclude that taking important parameters such as node's residual energy, path's hop count and balancing data transmission among multiple paths into account can remarkably improve the network lifetime. In this paper, we selected optimal and shortest path between source and sink based on parameters such as node's residual energy, free buffer and link quality between sensor nodes. We use A^* algorithm [14] to select optimal path with attention to above mentioned parameters.

3

The proposed energy-efficient routing algorithm

In this study, we used A^* algorithm to find the optimal path from the source node to the destination node (base station) with regard to some parameters of sensor nodes such as residual energy, packet reception rate (PRR) and node buffer state. In order to find the optimal path, the sink node should be aware of the criteria of each node. Thus, at the initial phase, each node must send its aforementioned parameters to the sink node. In the remaining round, if the sensor node has data to send toward the sink node, it will append its parameters to the data packet. Based on the gathered parameters, the sink node must determine and broadcast the routing schedule to each sensor node [9]. Then, A^* algorithm will search for the optimal path from the source node to the destination node. If the residual energy of sensor node is less than the energy threshold value (E_th), that node cannot participate in the routing process and hence will not send its parameters to the base station. The network load will be balanced with regard to the threshold value of the energy, and as aresult, the network lifetime will be enhanced.

A^* algorithm uses the method of best-first search and finds an optimal path from the initial node to the destination node[14]. It includes two lists, an OPEN list and a CLOSED list. It creates a tree structure of sensor nodes. The OPEN list is a priority queue and keeps track of those nodes that need to be examined while the CLOSED list keeps track of nodes that have already been examined [14]. A^* algorithm uses a distance-plus-cost heuristic function of node n, f(n) to determine the order in which the search visits nodes in the tree. This heuristic function is a sum of two functions as follows [14].

Where, g(n) is the cost from the source node to the current node n and h(n) is an admissible heuristic estimate of the distance from n to the destination node.

In the proposed scheme, the value of g(n) function is equal to the node cost of node n. Our intention is to forward data packets to the next neighbour node which has higher residual energy, higher free buffer, and higher packet reception rate. To achieve this, we made use of aggregated weight of the above-mentioned routing parameters. Here, we define the aggregated weight of a next neighbour node as the sum of normalized weights of its routing metrics as follows:

Where, E_res(n) and E_ini(n) are residual and initial energy of node n respectively. In addition, N_t(n) and N_r(n) are the number of transmitted and received packets respectively. B_f(n) and B_ini(n) referred to the number of free and initial buffer of node n respectively. In “Eq. 2”, ¿, ¿ and are weight parameters and ¿ + ¿ + ¿ = 1. The results of our extended simulation, performed in MATLAB 7.10, indicated that setting including ¿ = 0.6, ¿ = 0.2, and ¿ = 0.2 produces the best possible results.

The parameter of node cost is related to the linear combination of three normalized metrics. The first parameter is includes normalized residual energy which illustrates the residual energy of the next neighbouring node n. This parameter is aimed to ascertain that the sensor nodes' energy consumptions are balanced. Energy load must be evenly distributed among all the sensor nodes in order to prolong the network lifetime. The second parameter is called normalized number of received packets in n node. This metric corresponds with the packet reception rate of the next node. In other words, maximizing this metric is equal to maximizing the packet transmission efficiency. As aresult of taking this metric into account, the majority of the probability and hence this will prevent the retransmission of data packets which will significantly reduced the amount of energy consumption in the node. The third parameter stands for the magnitude of the available free buffer at the next neighbouring candidate, node n. this parameter plays the remarkable role in the proper distribution of traffic load. The packet will be sent to the next node which has the maximum free buffer.

Each source or intermediated node needs to know its neighboring nodes and their current parameters, e.g., position, battery state, free buffer, link quality, etc. This can be ensured via the execution of a HELLO protocol such as in [15, 16]. We assume that each node knows the position of sink node. The sink node broadcast its position to all sensor nodes in the network.

For updating packet reception rate, we use EWMA [12] as follows

Where, ¿ is waiting parameter and the value for h(n) function can be calculated as follows:

Where, Min(hcns) is the minimum hop count from node n to the destination node. In order to compute the minimum hop count from node n to the sink node, we must calculate the distance between node n and sink node via euclidean distance formula as follows:

Where, d(n, s) is equal to the Euclidian distance between the node n and sink node. Moreover, the hop count from node n to the sink node can be calculated as follows:

Where, avg(d(n,j)) is the average distance between the node n and its one hop neighbouring nodes (j). On the basis of “Eqs. 2 and 6”, we can calculate the value of evaluation cost function, f(x). Thus, for choosing the optimal path, we will select that node n which has the maximum evaluation function. The value of f(x) can be used to obtain the optimal path.

4

Performance Evaluation

In this papaer, the simulation of EERP was conducted in MATLAB 7.10 and the results were compaerd with those of A&F[9] in terms of average remaining energy and number of alive nodes. There exists twenty actors in the network for generating the data which are initially deployed in the network as a random state. Radio signal range of actors was assumed as 30 m and the current position of the actors is changed by RWP [17] every 100 rounds.

Furthermore, we analysed the impact of the number of transmission packets and the initial energy of the nodes on the average remain ing energy and the number of alive nodes. The number of transmission packets ranged from 4,000 to 44,000 packets. The senor nodes reported their criteria every 500 round to the base station in the A&F [9] method to update the scheduling table. The parameters of the simulation environment are listed in Table 1 in details.

Table 1.

Simulation Parameters.

Parameter	Value
Network Area [m×m]	200 × 200
Number of sensor nodes	50
Transmission radio range[m]	80
Maximum buffer size [Packet]	10
Position of sink [(m,m)]	(200,200)
Initial energy/J	5
Eelec[nj/bit]	50
¿amp[pj/bit/m^2]	100
Packet size[byte]	500
Number of transmission packets [Packet/Round]	4
Number of actors	20
Radio signal range of actors [m]	30
Node distribution	Uniform random
¿, ¿, ¿	0.6, 0.2, 0.2

Regarding the energy consumption model of the proposed EERP, we used the first order radio model which is the typical model in the area of routing protocol evaluation in WSN [6]. According to this model, the energy consumed for tranmitting and receiving k-bit data can be calculated as follows [6]:

Where, d is the distance from the sender node to the receiver node. E_elec and ¿_amp are per bit energy dissipation in transmiting or receiving circuitry and energy required per bit meter square for the amplifier to achive acceptable signal to noise ratio respectively. The total consumed energy can be calculated as follows [6]:

The impact of the number of transmission packets on the average remaining energy in two simulated protocols is illustrated in Fig. 2. It needs to be noted that the position of the sink was in two different spots, that is, at the top right corner, (200 m, 200 m), and at the center of the simulated area (100 m, 100 m).The purpose of changing the location of the sink node was to examine and compare the performance of the two methods. The simulation results in Fig. 2 indicated that the average remaining energy of the nodes in the EERP is more than that of A&F[9] method under the conditions of the two scenarios. The generation of much more redundant packets in A&F[9] method leads to the reduction of the average remaining energy. This is because EERP considers nodes' packet reception rate, remaining energy and nodes buffer state with minimum hop count path. The figure indicates that the proposed scheme is superior to A&F[9] method in term of saving nodes energy.

Figure 2.

Average remaining energy; (a) Sink in [200, 200]. (b) Sink in [100, 100].

Furthermore, the Fig. 3 shows that the number of alive nodes in EERP is more than the other method because the low consumption of energy results in an increase in the number of alive nodes. The difference in the simulation results of the two compared methods is very tangible and noticeable when number of transmission packets is low.

Figure 3.

Number of alive nodes; (a)sink in [200,200].(b)Sink in [100, 100].

Furthermore, as the simulation results in Fig. 4 (b) indicates, the average remaining energy of nodes in the EERP is higher than A&F[9]; the reason for this is that, in the proposed approach, the number of transmitted packets by the nodes is lower than that of the A&F[9] method. Furthermore the explanation for the superiority of the proposed method to the A&F[9] method is that load balancing and routing schedule managing in this method is more efficient than A&F[9].

Figure 4.

Average remaining energy as a function of initial energy; (a) Sink in [200, 200]. (b) Sink in [100, 100].

Fig. 5 shows that number of alive nodes in EERP is higher than that of A&F[9] due to the low consumption of energy of nodes for transmitting the packets. If the number of transmission packets in the network is low, consequently, the performance of the simulated packets will be very sensible.

Figure 5.

Number of alive nodes as a function of initial energy; (a) Sink in [200, 200]. (b) Sink in [100, 100].

It is noteworthy that when the sink is located at the center of the area, the energy consumption will be reduced and as aresult the average remaining energy increases. Unlike the position of the sink at the top corner of the area, when the sink is located at the center, the distance between the nodes and the sink will be notably shorter; consequently, the consumption of the energy will be reduced and the network lifetime will be expanded; moreover, the number of alive nodes will increase.

5

Conclusions

Since battery-powerd sensor nodes have limited energy, enhancing the lifetime of the WSNs is considered to be an important issue. This paper used A* algorithm and proposed a new scheme to improve the lifetime of WSNs. The EERP scheme accomodated a node's residual energy, packet reception rate and free buffer in order to finde the optimal path with mionimum hop count. The outstanding characteristic of the proposed scheme was that it allocated the task of data disseminiation to the sensor node with higher residual energy in order to prevent packet dropping as aresult of energy termination. Simulation results showed that our proposed was capable of increasing the network lifetime when compared with A&F[9] scheme.