Elsevier

Computer Networks

Volume 56, Issue 7, 3 May 2012, Pages 1951-1967
Computer Networks

Design principles and improvement of cost function based energy aware routing algorithms for wireless sensor networks

https://doi.org/10.1016/j.comnet.2012.01.023Get rights and content

Abstract

Cost function based routing has been widely studied in wireless sensor networks for energy efficiency improvement and network lifetime elongation. However, due to the complexity of the problem, existing solutions have various limitations. In this paper, we analyze the inherent factors, design principles and evaluation methods for cost function based routing algorithms. Two energy aware cost based routing algorithms named Exponential and Sine Cost Function based Route (ESCFR) and Double Cost Function based Route (DCFR) have been proposed in this paper. For ESCFR, its cost function can map small changes in nodal remaining energy to large changes in the function value. For DCFR, its cost function takes into consideration the end-to-end energy consumption, nodal remaining energy, resulting in a more balanced and efficient energy usage among nodes. The performance of the cost function design is analyzed. Extensive simulations demonstrate the proposed algorithms have significantly better performance than existing competing algorithms.

Introduction

Wireless sensor networks (WSNs) are collections of low-cost battery-powered devices, called sensors, which have integrated sensing, computing, and wireless communication capabilities [1]. They are deployed for detecting events of a predetermined nature and transmitting sensed event data to the data sink or base station for further analysis [2], [3]. It is recognized that WSNs have great potentials in many important applications such as military surveillance, environmental monitoring, infrastructure and facility diagnosis, and so on [4]. To reduce deployment budge, WSNs are expected to have minimized overall energy consumption and balanced energy usage among individual sensors. In WSNs, one of the main design challenges is to maximize network lifetime without scarifying network sensing performances (e.g., coverage and reliability).

The lifetime of a WSN can be defined as the time elapsed till the first sensor node in the network depletes its energy, since once a sensor node dies, the sensing capability of the network starts degrading [3]. To maximize network lifetime, an energy-efficient routing algorithm should be used for data communications. The algorithm needs to have the following three main features: (1) minimum total energy usage, (2) balanced energy consumption, and (3) distributed characteristics.

Cost function based routing has been studied extensively because of its distributed nature and good energy performance [5], [6]. In such routing algorithms, a node currently having a packet to transmit decides locally which of its neighbors is the next hop based on a cost function. A well-designed cost function will lead to energy-efficient decisions and prolonged network lifetime. There are many cost functions proposed in literature. They were, however, designed merely according to designers’ experience, which is suboptimal, and lacks of theoretical analysis on their performance.

In this paper, we analytically study existing cost function based routing algorithms and present the general principles and guidelines for cost functions construction. We propose a novel double cost function based routing (DCFR) algorithm, which is decentralized, adaptive, and outperforms existing cost function based solutions in terms of energy efficiency improvement and network lifetime elongation. Existing solutions consider only end-to-end energy consumption and nodal remaining energy, and achieve suboptimally balanced energy consumption. Unlike these schemes, DCFR additionally includes energy consumption rate in its cost function. The cost function has a rapidly increasing slope such that a small difference in energy consumption rate or available energy level can lead to a big difference in function values. Hence, DCFR has an excellent capability of balancing energy usage during routing. Each node chooses next hop to forward data according to the energy consumption rates as well as node remaining energy of its neighbors, so energy consumption is balanced in the entire network. We show the benefits of our proposed cost function design guideline. We evaluate the performance of our new routing algorithm DCFR through extensive simulation using various performance metrics. We compare DCFR with three well-known routing algorithms, i.e., DC (Direct Communication) [7], [8], minimum transmission energy (MTE) [9], and distributed energy balanced routing (DEBR) [5]. Our simulation confirms that DCFR indeed has significantly better performance than these existing algorithms in network lifetime elongation and energy balancing.

Section snippets

Related work

To prolong the lifetime of a WSN, a number of routing algorithms have been proposed. They mainly aim to minimize total energy usage in the network. However, sensors along paths with minimized total energy cost are repeatedly used and deplete their energy quickly, resulting in short network lifetime. Thus, researchers found that routing algorithms should consider not only total energy consumption, but also the amount of remaining energy in each sensor. By giving preference to sensors with high

Network topology

We adopt the same network model as [5], [16]. The network is composed of n homogenous sensors randomly and uniformly distributed over a target area. Events occur uniformly such that every sensor has one packet to report periodically. The neighboring distance is defined as the maximal reachable distance of radio frequency with the maximum transmission power. Each sensor can be aware of the current energy level of its neighbors and the energy required to transmit data from each of its neighboring

A case study of existing cost function based routing

We use an example to illustrate that existing cost function based routing strategies can be farther improved. In Fig. 1, there are two obstacles in a rectangular WSN. Assume that each sensor initially has the same amount of energy enough for transmitting and receiving m = 10,000 data packets. The area covered by the network is s = L × W(115 × 75) m2; node density is ρ = 0.06/m2; no sensor is deployed in the obstacle areas. There are n = 400 sensors in the network. The number of sensors in the red area is n1 =

Experimental results

In this section, we provide experimental results to validate the effectiveness of exponential and sine cost function based routing (ESCFR) and double cost function based routing (DCFR) algorithm. We compare them with three existing algorithms discussed in [7], [8]: direct communication (DC), minimum transmission energy (MTE), and distributed energy balanced routing (DEBR). In DC, every sensor simply transmits data directly to the base station without considering any energy efficiency. MTE

Conclusion

In this paper, we have studied cost function based energy-aware routing. We proposed the general principles of cost function design and evaluation criteria. Further, we presented two novel energy aware cost based routing algorithms, named exponential and sine cost functionbased routing (ESCFR) and double cost function based routing (DCFR). These two algorithms aim at maximizing the lifetime of the network by means of power consumption equalization. Comprehensive simulation results demonstrate

Acknowledgments

This research is supported by the National Natural Science Foundation of China (61073104, 61073186), China Postdoctoral Science Foundation (20100471789), Specialized Research Fund for the Doctoral Program of Higher Education of China (20090162120074), Hunan Provincial Natural Science Foundation of China (09JJ6095), and Ontario Research Fund Canada.

Anfeng Liu is an Associate Professor of School of Information Science and Engineering of Central South University. He is also a Member (E200012141M) of China Computer Federation (CCF). He received the M.Sc. and Ph.D degrees from Central South University, China, 2002 and 2005, both in computer science. Currently he is a Visiting Scholars in University of Waterloo, Canada. His major research interest is wireless sensor network.

References (25)

  • M. Ettus, System capacity, latency, and power consumption in multihop-routed SS-CDMA wireless networks, in: Proceedings...
  • O. Zytoune et al.

    A uniform balancing energy routing protocol for wireless sensor networks

    Wireless Pers. Commun.

    (2010)
  • Cited by (112)

    • Optimal routing methodology to enhance the life time of sensor network

      2021, Materials Today: Proceedings
      Citation Excerpt :

      This paper provides a solution to route the packet through the shortest path from source to sink by implementing DRM algorithm. The routing of data plays a key role in minimizing energy consumption of a network [3]. In this paper, to minimize the energy and to increase the overall life time of network, a new approach, Dijkstra’s routing management algorithm, is implemented and compared with the normal method of the Dijikstra.

    • Secure big data communication for energy efficient intra-cluster in WSNs

      2019, Information Sciences
      Citation Excerpt :

      After this, the improved method of the scheme has been proposed. The improvement direction mainly includes the following two types: reselecting the CH nodes and rebuilding the clusters [8–13] or finding multi-hop data transfer path from CHs to the BS [14–18]. When large volume of data is exchanged or proceed in the cluster, the long distance data communication will consume a large amount of energy [19].

    • E<sup>2</sup>BNAR: Energy Efficient Backup Node Assisted Routing for Wireless Sensor Networks

      2023, International Journal on Recent and Innovation Trends in Computing and Communication
    View all citing articles on Scopus

    Anfeng Liu is an Associate Professor of School of Information Science and Engineering of Central South University. He is also a Member (E200012141M) of China Computer Federation (CCF). He received the M.Sc. and Ph.D degrees from Central South University, China, 2002 and 2005, both in computer science. Currently he is a Visiting Scholars in University of Waterloo, Canada. His major research interest is wireless sensor network.

    Ju Ren received B.Sc. on 2009. Currently he is a master in School of Information Science and Engineering of Central South University. His research interest is in wireless sensor network.

    Xu Li received his Ph.D. degree from Carleton University, Canada (2008), his M.C.S. degree from the University of Ottawa, Canada, 2005, and his B.Sc. degree from Jilin University, China, 1998. In 2004, he held a visiting researcher position at National Research Council Canada. He is currently a postdoctoral fellow at SITE, University of Ottawa and at CNRS/INRIA, France. His current research interests are wireless ad hoc, sensor, and actuator networks, mobile robots, distributed and localized algorithms, and wireless security. He was/is involved in many scholarly activities including ACM FOWANC’09, IMAGINE’09, AdHoc-Now’08& 09, LOCALGOS’09, WWASN’09, IFIP WSAN’08, IEEE MASS’07, etc.

    Zhigang Chen received B.Sc. the M.Sc. and Ph.D degrees from Central South University, China, 1984, 1987 and 1998, He is a Ph.D. Supervisor and his research interests are in network computing and distributed processing.

    Xuemin (Sherman) Shen (M’97-SM’02-F’09) received the B.Sc. (1982) degree from Dalian Maritime University (China) and the M.Sc. (1987) and Ph.D. degrees (1990) from Rutgers University, New Jersey (USA), all in electrical engineering.

    He is a Professor and University Research Chair, Department of Electrical and Computer Engineering, University of Waterloo, Canada. Dr. Shen’s research focuses on resource management in interconnected wireless/wired networks, UWB wireless communications networks, wireless network security, wireless body area networks and vehicular ad hoc and sensor networks. He is a coauthor of three books, and has published more than 400 papers and book chapters in wireless communications and networks, control and filtering. Dr. Shen served as the Technical Program Committee Chair for IEEE VTC’10, the Symposia Chair for IEEE ICC’10, the Tutorial Chair for IEEE ICC’08, the Technical Program Committee Chair for IEEE Globecom’07, the General Co-Chair for Chinacom’07 and QShine’06, the Founding Chair for IEEE Communications Society Technical Committee on P2P Communications and Networking. He also served as a Founding Area Editor for IEEE Transactions on Wireless Communications; Editor-in-Chief for Peer-to-Peer Networking and Application; Associate Editor for IEEE Transactions on Vehicular Technology; Computer Networks; and ACM/Wireless Networks, etc., and the Guest Editor for IEEE JSAC, IEEE Wireless Communications, IEEE Communications Magazine, and ACM Mobile Networks and Applications, etc. Dr. Shen received the Excellent Graduate Supervision Award in 2006, and the Outstanding Performance Award in 2004 and 2008 from the University of Waterloo, the Premier’s Research Excellence Award (PREA) in 2003 from the Province of Ontario, Canada, and the Distinguished Performance Award in 2002 and 2007 from the Faculty of Engineering, University of Waterloo. Dr. Shen is a registered Professional Engineer of Ontario, Canada, an IEEE Fellow, an Engineering Institute of Canada Fellow, and a Distinguished Lecturer of IEEE Communications Society.

    View full text