An Energy Efficient Cluster Based Routing Algorithm

An Energy Efficient Cluster Based Routing Algorithm

Muhammad Zeshan Alam School of Engineering, Design and Technology

University of Bradford Bradford, UK

Yongqiang Jay Cheng

School of Engineering, Design and Technology

University of Bradford Bradford, UK

Arooba Zeshan Department Of Electrical Engineering

CIIT

Islamabad, Pakistan

Abstract– Wireless Sensor Network is one of the most rapidly advancing technologies and has gained the attention of scientists and researchers because of its potential for applications in various fields of science and technology. The combined capabilities of several tiny, self-powered remote sensing devices that automatically form multi hop reconfigurable network provide detailed observation of any physical phenomenon in the area of their deployment. WSN faces some severe computational and resource constraints which make their implementation a very hard task.

Among other resource constraints energy limitation is the major challenge for WSN. This is the reason why a large part of the research in WSN focuses on the development of energy efficient routing protocols. In this paper, an algorithm called Efficient Router Reduction Technique (ERRT) is proposed. The network is first divided into different sub-network areas which are further divided into clusters and then distance based assignment of router role as well as periodic activation of routers of different SNAs are performed to achieve energy conservation.

The performance evaluation of ERRT is carried out over MICA2 motes and the results prove the effectiveness of this algorithm in terms of network energy efficiency.

Keywords- Wireless Sensor Networks, Clustering Algorithms, Energy Efficient Routing

1. INTRODUCTION

   Wireless Sensor Networks (WSNs) consist of a large number of tiny, self-powered sensing devices (nodes) which communicate with each other through a wireless medium [1]. WSNs find their applications in wide range of areas including environmental monitoring, industrial monitoring, military, healthcare, and security [2]. Due to their deployment in physically tough environments which are difficult to be approached these nodes are often expected to operate over periods of many years as it becomes very challenging to replace batteries of the nodes. Therefore energy awareness is a crucial aspect of wireless sensor networks.

   Considerable research is being carried out in the development of energy-aware hardware, algorithms and protocols. Among different energy aware algorithms, clustering based algorithms for energy awareness are very effective. Clustering algorithm tries to conserve the networks energy by minimizing communication between the nodes yet maintaining minimum connectivity to keep the network operational and allows it to

   perform its functionality. Most of the protocols use clustering in order to provide energy efficiency and to extend the networks lifetime. In each cluster, a node is elected as the cluster head (CH) or router, and the remaining nodes in the cluster send their data to cluster head and the cluster head then sendsthe data to the base station. This data transfer can be performed in two alternative ways; either directly, in cases where the router is located near to the base station or via intermediate routers when the router is positioned away from the base station. The proposed algorithm also makes use of clustering but these clusters also form a bigger cluster known as Sub Network Area (SNA) which is totally independent of other SNAs and has a great impact on energy conservation as it helps in reducing the number of active routers in the network, which are the most power consuming network element.

   This paper is organized as follows. In Section 2, related work in energy efficient protocols ispresented. In Section 3, the proposed efficient router reduction technique is presented. In Section 4, router switching is discussed. The results of the proposed ERRT are presented in section 5. In Section 6,conclusions are drawn.

2. RELATED WORK

   Various research papers have developed various techniques in order to conserve energy in WSN. Low Energy Adaptive Clustering Hierarchy (LEACH) is one of the most discussed hierarchical protocol in which most nodes transmit to cluster heads, this technique was first presented in [3].

   The cluster head in LEACH is selected on the basis of a stochastic algorithm in every round. A node can only become a cluster head once; and cannot become a cluster head again for P rounds, where P is the desired percentage of cluster heads.

   Power-Efficient Gathering in Sensor Information Systems (PEGASIS) is an energy efficient protocol [5], which provides improvements over LEACH. In PEGASIS, nodes exchange data only by communicating with a nearby neighbor. The nodes transmit information to the base station turn by turn which reduces the amount of energy spent per round.

   PEGASIS has better performance compared to LEACH [5], but the nodes are grouped into chains that cause redundant data transmissions.

   ECHERP [6]protocol uses a more efficient mechanism to select a node as the cluster head. This is performed by considering the current and the estimated future residual energy of the nodes, along with the number of rounds that they could be cluster heads, in order to maximize the networks lifetime. ECHERP models the network and the energy spent by the nodes as a linear system using the Gaussian elimination algorithm.

   The cluster head election in ELCH routing protocol [7] is achieved through voting by nodes in the network.

   In Energy efficient cluster formation protocol (EECFP) [8] the cluster head selection is based on the residual energy, so the node with highest energy gets selected and to balance the energy consumption the selection is rotated after every round.

   In saving energy clustering algorithm (SECA) [9] the networks lifetimes is extended through the load balancing in network clusters and uniform cluster location.

   In SLGC [10] algorithm,the network was organized in to girds and cluster headin each grid is elected using clustering and middle position of nodes and threshold energy in the grid.

   In Multi-Weight Based Clustering Algorithm(MWBCA) [11] the cluster head is selected on the basis of function known as combined weight which is the combination of transmission power of the node and residual energy.

   The cluster formation in heed [12] is dependent on the communication with in the cluster and the residual energy of the sensor nodes, the node with greater residual energy becomes the cluster head.

   All the above mentioned techniques try to reduce energy consumption of the network through different clustering algorithms. The proposed Efficient Router Reduction Technique ERRT also uses the concept of clustering for energy conservation. However, it does not only periodically selects the cluster head based on the different parameters to balance the power consumption among the nodes, but also reduces the number of active cluster heads in the network to further minimize energy consumption.

3. EFFICIENT ROUTER REDUCTION

   TECHNIQUE (ERRT)

   Maximum energy consumed by a sensor mote under consideration (mica 2) is during the transmission phase. However, this is not the only time when energy is being utilized by these motes; it also dissipates power during other phases like listening, idle and reception. Idle and listening phases have negligible energy consumption as compared to the transmission phase.

   Energy consumption by the router is far greater than energy consumed by theend devices, because router is responsible for carrying out communication in the network and also for assigning roles to nodes whereas end devices send the sensor data to the router only after a required interval. Therefore considerable energy can be saved if number of routers in the network is reduced. The ERRT technique achieves this using the fundamental principal of clustering technique that is to make use of node density in a network to extend networks life. ERRT performance increases with the increase in networks coverage area (increase in number of nodes). The network is divided in to a number of sub network areas

   (SNAs) and SNA is further divided in to levels or clusters. As the network is dynamically configurable, the number of levels in an SNA and the number of SNAs in a network can increase or decrease at any time.The physical layout of the network is shown in Fig. 1.

   FIGURE 1: NETWORK ARCHICTECTURE

   1. Base station selects the most distant node in level one of SNA 1as router and the other nodes of that level start sending data directly to the base station after a regular interval.

   2. The router of level one then starts listening to the nodes of level two and selects a node with lowest RSSI value, or in other words the node with the maximum distance from level 1 router. While all rest of the nodes in that level start sending data to previous level router at regular intervals.

   3. This process continues until the last node (most distant node in highest level) in SNA1 gets connected to the base station via routers in between. The last node always acts as router in order to detect the presence of any node at any time in its coverage area in SNA 1.

   4. The highest level router sends data to the previous level router which in turn sends data of the higher level router as well the data of higher level nodes to the previous level router until the data from all the nodes reaches the base station.

   5. The same mechanism is adopted in all the SNAs. This technique reduces one router in each SNA by making the most distant node a router, which otherwise will require one more node to connect all the nodes in the SNA. This can clearly be seen in Fig. 2 and Fig. 3.

   Fig. 2:Reduced routers through ERRT

   Fig. 3: Increased number of routers without ERRT

   In Fig. 2 the base station selected the most distant node as a router in level1, according to ERRT, and hence two routers were needed to cover the area while the same area with same number of nodes was covered by three routers in Fig. 3where ERRT was not applied because the second most distant node in level 1 is selected as routerwhose coverage area did not include the last node in second level thus required another router to cover all nodes.

   Therefore with the increase in networks coverage area there is an increase in the number of SNAs and hence more routers can be reduced which will increase the difference between energy consumption by the network with or without the implementation of algorithm. The total number of routers reduced is equal to the number of SNAs in the network. ERRT minimizes the routers further by using periodic activation of router nodes.

   Initially the base station enables one router in level 1 of SNA1 which in turn activates the second level router of SNA 1 and then waits till the data from second level nodes is being received. In the meanwhile despite of sending empty message the base station deactivates its roles as a router and in turn enables the first level router of SNA 2 and then the process continues till the level 1 node of SNA1 is reactivated. This technique keeps only one active router in the level 1 of entire network instead of routers equal to the number of SNAs and as the number of SNAs increases more routers are reduced.

   However its very important to keep in mind the interval after which the nodes in level send their data back to previous level router in order to avoid data loss.

   This technique can be further applied to higher level routers for further router reduction depending upon the number of levels in a network which will make the router reduction two dimensional, with the increase in number of SNAs and also with the increase in number of levels in an SNA.

   As mentioned earlier, purpose of reducing number of routers is that a routers transmission rate is higher compared to an end device that is:

   >> (1)

   Where NTmrand NTme are number of transmissions by the router and the end devices respectively.

   Suppose that the power depleted in one transmission is given as

   1 = × (2)

   is the voltage of the two batteries and is the current drawn by the mote during one transmission

   The power consumption by router,over a given time, is given by

   = 1 × × (3)

   And the power consumption by end device,over a given time, is given by

   in the networkby a greater amount as compared to the power consumption without ERRT.

   = 1 × × (4)

   Where Nr and Ne are number of routers and end devices respectively.

   Thus the total power consumption by network = +

   .

4. ROUTER SWITCHING

   The main purpose of ERRT is to increase networks lifetime. Therefore another important aspect of ERRT is router switching based on the remaining battery level of the router. If battery level of the router goes below a certain threshold level, which is required to keep the router operational, it automatically becomes an end device and another node in that level which is the second most distant node from previous level router becomes a router for that level which adds another cycle to the networks life time. And then if the newly elected routers battery level goes below threshold level same changes take place to add another cycle to networks life time. This technique avoids network dis-connectivity and prevents it from shutting down.

5. RESULTS

The results were obtained by implementing the algorithm on MICA2motes. The network was divided into five SNAs with each SNA having two levels containing five motes each.

Hence the total number motes used to obtain these results were fifty.

The results obtained from ERRT by making the most distant mote a router using RSSI value show that significant amount of power consumption by the network is reduced. Even though more power is consumed by a distant router during transmission but as one router is reduced all the transmission involved with that router is also reduced which results in lesser power consumption as shown in Fig. 4.

Fig. 4: Power efficiency results

Time based cyclic activation and deactivation of routers of first level in all SNAs further reduced the power consumption

Fig.5: Improved power efficiency results with level 1

The extension of ERRT algorithm two the second level in all SNA resulted in the decrease in power consumption by the amount shown in Fig. 6.

Fig. 6: Improved power efficiency results with level 2

As the network design is based on dynamic configuration, thus with the increase in the networks depth (increase in number of level in an SNA) as well as with the increase in number of SNAs ERRT becomes more efficient resulting in the greater decrease in the network power consumption as compared to the consumption without ERRT, however the overall consumption obviously tends to increase as the network coverage area has increased and more nodes are now consuming power. But the network life time has increased as more and more cycles have been added.

CONCLUSION

In this paper, ERRT, an energy conservation algorithm for WSNs, was presented. This algorithm reduces the power consumption of the network by reducing the number of active routers in the network. ERRT achieves substantial energy efficiency which is evident from the results. ERRT can be further enhanced by implementing on the higher level routers in a similar manner as the first two level routers ofSNAs which will make the algorithm two dimensional. The technique is based on balancing the load among the nodes in cluster heads as other algorithms present in literature butit also reduces the number of active routers which is a novelty and has a huge effect in power consumption.

REFERENCES

1. Rabaey, R.S.a.J., Energy aware routing for low energy adhoc sensor networks. 2002.

2. Ababneh, N., Viglas, A. ; Labiod, H. ; Boukhatem, N., ECTC: Energy Efficient Topology Sciences, Hawaii, HI, USA, 2000; pp 110.

3. Heinzelman, W.; Chandrakasan, A.; Balakrishnan H. Energy- Efficient Communication Protocol for Wireless Microsensor Networks.

4. Lindsey, S.; Raghavendra, C. PEGASIS: Power-Efficient Gathering in Sensor Information Systems. In Proceedings of the IEEE Aerospace Conference, Los Angeles, USA, 2002, pp, 1125-1130

5. Jung, S.; Han, Y.; Chung, T. The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS.

   Gangwon-Korea 2007. Pp. 260-265

6. Stefanos A. Nikolidakis, DionisisKandris,Dimitrios D. Vergados and Christos Douligeris: Energy Efficient Routing in Wireless Sensor Networks Through Balanced Clustering. Open Access Algorithms. pp 33-35.

7. Lotf, J.; Bonab, M.; Khorsandi, S. A Novel Cluster-based Routing Protocol with Extending Lifetime for Wireless Sensor Networks.In Proceedings of the 5th International Conference onWireless and Optical Communications Networks, Surabaya, India, 2008; pp. 15.

8. Allirani, A.; Suganthi, M. An Energy Efficient Cluster Formation Protocol with Low Latency InWireless Sensor Networks. World Acad. Sci., Eng. Tech. 2009, 51, 17.

9. Rathna. R and Sivasubramanian. A. Improving Energy Efficiency In Wireless Sensor Networks Through Scheduling And Routing. International Journal Of Advanced Smart Sensor Network Systems ( IJASSN ), Vol 2, No.1, January 2012.

10. A. G. Delavar, S. Shamsi, N. Mirkazemi, and J. Artin, SLGC: A New Cluster Routing Algorithm in Wireless Sensor Network for DecreaseEnergy Consumption.

11. Z. Fan and Z. Jin, A Multi-weight Based Clustering Algorithm for Wireless Sensor Networks, College of Computer Science & Educational Software Guangzhou University, 2012.

12. O. Younis and S. Fahmy, HEED: A Hybrid , Energy-Efficient, Distributed Clustering Approach for Ad-hoc Sensor Networks, IEEE Transactions on Mobile Computing, vol. 3, no. 4, pp. 366 379, 2004.