Open Access Open Access  Restricted Access Subscription or Fee Access

Optimal Local Topology Knowledge for Energy Efficient Geographical Routing in Wireless Sensor Networks

A. Ranjith Kumar, A. Padmaja

Abstract


A number of energy-aware routing protocols were proposed to seek the energy efficiency of routes in multihop wireless networks. Among them, several geographical localized routing protocols were proposed to help making smarter routing decision using only local information and reduce the routing overhead. Previous localized routing protocols are not energy efficient, i.e., the total energy consumed by their route could be very large compared with the optimal. However, all proposed localized routing methods cannot guarantee the energy efficiency of their routes. In this paper, we first give a simple localized routing algorithm, called Localized Energy-Aware Restricted Neighborhood routing (L.E.A.R.N), which can guarantee the energy efficiency of its route if it can find the route successfully. We then theoretically study its critical transmission radius in random networks which can guarantee that LEARN routing finds a route for any source and destination pairs asymptotically almost surely. We also extend the proposed routing into three-dimensional (3.D) networks and derive its critical transmission radius in 3.D random networks. Simulations results confirm our theoretical analysis of L.E.A.R.N routing and demonstrate its energy efficiency in large scale random networks

Keywords


Localized Routing, Energy Efficient, Critical Transmission Radius, Wireless Networks.

Full Text:

PDF

References


K. Kar, M. Kodialam, T. Lakshman, and L. Tassiulas, “Routing for Network Capacity Maximization in Energy-Constrained Ad-Hoc Networks,” Proc. IEEE INFOCOM, 2003.

J.-H. Chang and L. Tassiulas, “Energy Conserving Routing in Wireless Ad-Hoc Networks,” Proc. IEEE INFOCOM, 2000.

Q. Li, J. Aslam, and D. Rus, “Online Power-Aware Routing in Wireless Ad-Hoc Networks,” Proc. ACM Mobicom, 2001.

Q. Dong, S. Banerjee, M. Adler, and A. Misra, “Minimum Energy Reliable Paths Using Unreliable Wireless Links,” Proc. ACM Int’l Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), 2005.

T. Melodia, D. Pompili, and I.F. Akyildiz, “Optimal Local Topology Knowledge for Energy Efficient Geographical Routing in Sensor Networks,” Proc. IEEE INFOCOM, 2004.

I. Stojmenovic and S. Datta, “Power and Cost Aware Localized Routing with Guaranteed Delivery in Wireless Networks,” Wireless Comm. and Mobile Computing, vol. 4, no. 2, pp. 175-188, 2004.

I. Stojmenovic and X. Lin, “Loop-Free Hybrid Single-Path Flooding Routing Algorithms with Guaranteed Delivery forWireless Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 10, pp. 1023-1032, Oct. 2001.

J. Kuruvila, A. Nayak, and I. Stojmenovic, “Progress and LocationBased Localized Power Aware Routing for Ad Hoc and SensorWireless Networks,” Int’l J. Distributed Sensor Networks, vol. 2,pp. 147-159, 2006.

P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia, “Routing with Guaranteed Delivery in Ad Hoc Wireless Networks,” ACM/ Kluwer Wireless Networks, vol. 7, no. 6, pp. 609-616, 2001.

F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger, “Geometric Ad-Hoc Routing: Of Theory and Practice,” Proc. ACM Symp. Principles of Distributed Computing (PODC), 2003.

F. Kuhn, R. Wattenhofer, and A. Zollinger, “Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing,” Proc. ACM Int’l Symp. Mobile Ad Hoc Networking and Computing (MobiHoc), 2003.

C.-P. Li, W.-J. Hsu, B. Krishnamachari, and A. Helmy, “A Local Metric for Geographic Routing with Power Control in Wireless

Networks,” Proc. IEEE Comm. Soc. Sensor and Ad Hoc Comm. And Networks (SECON), 2005.

K. Seada, M. Zuniga, A. Helmy, and B. Krishnamachari, “Energy- Efficient Forwarding Strategies for Geographic Routing in Lossy Wireless Sensor Networks,” Proc. ACM Int’l Conf. Embedded Networked Sensor Systems (Sensys), 2004.

F. Kuhn, R. Wattenhofer, and A. Zollinger, “Asymptotically Optimal Geometric Mobile Ad-Hoc Routing,” Proc. Sixth Int’l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. (Dial-M), 2002.

Y. Wang, W.-Z. Song, W. Wang, X.-Y. Li, and T.A. Dahlberg, “LEARN: Localized Energy Aware Restricted Neighborhood Routing for Ad Hoc Networks,” Proc. IEEE Comm. Soc. Sensor and Ad Hoc Comm. and Networks (SECON), 2006.

I. Stojmenovic, “Localized Network Layer Protocols in Wireless Sensor Networks Based on Optimizing Cost over Progress Ratio,” IEEE Networks, vol. 20, no. 1, pp. 21-27, Jan./Feb. 2006.

X.-Y. Li, G. Calinescu, P.-J. Wan, and Y. Wang, “Localized elaunay Triangulation with Applications in Wireless Ad Hoc etworks,” IEEE Trans. Parallel and Distributed Systems, vol. 14, o. 10, pp. 1035-1047, Oct. 2003.

P. Gupta and P.R. Kumar, “Critical Power for Asymptotic cnnectivity in Wireless ntworks,” Stochastic Analysis, Control, ptimization and Applications: A Volume in Honor of W.H. Fleming .M. McEneaney, G. Yin, and Q. Zhang, eds., Springer, 1998.

X.-Y. Li, P.-J. Wan, Y. Wang, C.-W. Yi, and O. Frieder, “Robust eployment and Fault Tolerant Topology Control for Wireless AHoc Networks,” Wiley J. Wireless Comm. and Mobile Computing,vol. 4, no. 1, pp. 109-125, 2004.

C. Bettstetter, “On the Minimum Node Degree and Connectivityof aWireless Multihop Network,” Proc. ACM Int’l Symp. Mobile AdHoc Networking and Computing (MobiHoc), June 2002.

H. Takagi and L. Kleinrock, “Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminal,” IEEE Trans. Comm., vol. C-32, no. 3, pp. 246-257, Mar. 1984.

P.-J. Wan, C.-W. Yi, L. Wang, F. Yao, and X. Jia, “Asymptotic Critical Transmission Radius for Greedy Forward Routing in Wireless Ad Hoc Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 57, no. 5, p. 1433, May 2009.

V. Ravelomanana, “Extremal Properties of Three-Dimensional Sensor Networks with Applications,” IEEE Trans. Mobile Computing, vol. 3, no. 3, pp. 246-257, July/Aug. 2004.

S.M.N. Alam and Z.J. Haas, “Coverage and Connectivity in Three- Dimensional Networks,” Proc. ACM Mobicom, 2006.

Y. Wang, C.-W. Yi, and F. Li, “Delivery Guarantee of Greedy Routing in Three Dimensional Wireless Networks,” Proc. Int’l Conf. Wireless Algorithms, Systems, and Applications (WASA), 2008.

S. Durocher, D. Kirkpatrick, and L. Narayanan, “On Routing with Guaranteed Delivery in Three-Dimensional Ad Hoc Wireless Networks,” Proc. Int’l Conf. Distributed Computing and Networking (ICDCN), 2008.

R. Flury and R. Wattenhofer, “Randomized 3D Geographic Routing,” Proc. IEEE INFOCOM, 2008.

E. Kranakis, H. Singh, and J. Urrutia, “Compass Routing on Geometric Networks,” Proc. Canadian Conf. Computational Geometry, 1999.

P. Bose and P. Morin, “Online Routing in Triangulations,” Proc. Ann. Int’l Symp. Algorithms and Computation (ISAAC), 1999.

Y. Wang and X.-Y. Li, “Efficient Delaunay-Based Localized Routing for Ad Hoc Sensor Networks,” Int’l J. Comm. Systems, vol. 20, no. 7, pp. 767-789, 2007.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.