GRAB: Greedy Forwarding with Routing Along Boundaries in Wireless Sensor Networks

##plugins.themes.academic_pro.article.sidebar##

Published Nov 1, 2016
https://doi.org/10.47164/ijngc.v7i3.116
Download
pdf
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 7, Issue 3, November 2016

##plugins.themes.academic_pro.article.main##

Rajesh Sharma
N.I.T. - Hamirpur (H.P.)
Lalit Kumar Awasthi
N.I.T. - Hamirpur (H.P.)
Naveen Chauhan
N.I.T. - Hamirpur (H.P.)

Abstract

Geographic Routing (GR) has emerged as a method of choice for routing in Wireless Sensor Networks (WSNs) due to its inherent features like localized operation, small per-node state, scalability, ability to operate without node addresses, and robustness in highly dynamic network conditions. Greedy Forwarding (GF) is generally used as default routing strategy in GR-based schemes due to its efficiency. However, GF alone does not guarantee packet delivery due to its susceptibility to failure at local minima or dead-ends. Hence, GF is augmented with some standby recovery scheme to implement reliable end-to-end geographic routing. Recovery schemes are generally highly inefficient as compared to greedy forwarding. Hence, it is imperative to induce conditions favouring GF and minimize the application of recovery scheme during end-to-end geographic routing. Most of the recovery schemes are based on the assumption of Unit Disk Graph (UDG) model for wireless connectivity. UDG is too ideal to model the behaviour of real radio links. In this paper, a scheme called “Greedy Forwarding with Routing along Boundaries” (GRAB) is proposed that combines an efficient form of greedy forwarding called “Minimal Marking of Trap Regions” (MMTR) with a novel recovery scheme called “Rolling Circle Algorithm” (RCA) to devise an efficient end-to-end geographic routing scheme for WSNs. An early fallback criterion is also proposed in this work to terminate recovery process and resume greedy forwarding as early as possible. In simulation, GRAB demonstrates significantly lower Hop Stretch Factor (HSF) when compared with other schemes.

##plugins.themes.academic_pro.article.details##

How to Cite
Rajesh Sharma, Lalit Kumar Awasthi, & Naveen Chauhan. (2016). GRAB: Greedy Forwarding with Routing Along Boundaries in Wireless Sensor Networks. International Journal of Next-Generation Computing, 7(3), 164–175. https://doi.org/10.47164/ijngc.v7i3.116
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Bose, P., Devroye, L., Evans, W., and Kirkpatrick, D. 2002. On the spanning ratio of gabriel graphs and β-skeletons. In Latin American Symposium on Theoretical Informatics, pp. 479–493. Springer.
  2. Bose, P., Morin, P., Stojmenovic, I. ´ , and Urrutia, J. 1999. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, DIALM ’99, New York, NY, USA, pp. 48–55. ACM.
  3. Boukerche, A., Chatzigiannakis, I., and Nikoletseas, S. 2006. A new energy efficient and fault-tolerant protocol for data propagation in smart dust networks using varying transmission range. Computer Communications 29, 4, 477 – 489. Current areas of interest in wireless sensor networks designs.
  4. Cadger, F., Curran, K., Santos, J., and Moffett, S. 2013. A survey of geographical routing in wireless ad-hoc networks. IEEE Communications Surveys Tutorials 15, 2 (Second), 621–653.
  5. Carl, H. and Willig, A. 2005. Protocols and Architectures for Wireless Sensor Networks. John Wiley & Sons. Chen, D. and Varshney, P. K. 2007. A survey of void handling techniques for geographic routing in wireless networks. IEEE Communications Surveys & Tutorials 9, 1 (Jan.), 50–67.
  6. Chou, C.-H., Ssu, K.-F., Jiau, H. C., Wang, W.-T., and Wang, C. 2011. A dead-end free topology maintenance protocol for geographic forwarding in wireless sensor networks. IEEE Transactions on computers 60, 11, 1610– 1621.
  7. Edelsbrunner, H., Kirkpatrick, D., and Seidel, R. 1983. On the shape of a set of points in the plane. IEEE Transactions on information theory 29, 4, 551–559.
  8. Fang, Q., Gao, J., and Guibas, L. J. 2006. Locating and bypassing holes in sensor networks. Mob. Netw. Appl. 11, 2 (April), 187–200.
  9. Fayed, M. and Mouftah, H. T. 2009. Localised alpha-shape computations for boundary recognition in sensor networks. Ad Hoc Networks 7, 6, 1259–1269.
  10. Hightower, J. and Borriello, G. 2001. Location systems for ubiquitous computing. Computer 34, 8 (Aug.), 57–66.
  11. Huc, F., Jarry, A., Leone, P., Moraru, L., Nikoletseas, S., and Rolim, J. 2009. Early obstacle detection and avoidance for all to all traffic pattern in wireless sensor networks. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pp. 102–115. Springer.
  12. Jaromczyk, J. W. and Toussaint, G. T. 1992. Relative neighborhood graphs and their relatives. Proceedings of the IEEE 80, 9, 1502–1517.
  13. Karp, B. and Kung, H. T. 2000. Gpsr: Greedy perimeter stateless routing for wireless networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, MobiCom ’00, New York, NY, USA, pp. 243–254. ACM.
  14. Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. 2005a. Geographic routing made practical. In Proceedings of the 2Nd Conference on Symposium on Networked Systems Design & Implementation - Volume 2, NSDI’05, Berkeley, CA, USA, pp. 217–230. USENIX Association.
  15. Kim, Y.-J., Govindan, R., Karp, B., and Shenker, S. 2005b. On the pitfalls of geographic face routing. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing, DIALM-POMC ’05, New York, NY, USA, pp. 34–43. ACM.
  16. Kuhn, F., Wattenhofer, R., Zhang, Y., and Zollinger, A. 2003. Geometric ad-hoc routing: of theory and practice. In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 63–72. ACM.
  17. Kuhn, F., Wattenhofer, R., and Zollinger, A. 2002. Asymptotically optimal geometric mobile ad-hoc routing. In Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, DIALM ’02, New York, NY, USA, pp. 24–33. ACM.
  18. Kuhn, F., Wattenhofer, R., and Zollinger, A. 2003. Worst-case optimal and average-case efficient geometric ad-hoc routing. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking &Amp; Computing, MobiHoc ’03, New York, NY, USA, pp. 267–278. ACM.
  19. Kuhn, F., Wattenhofer, R., and Zollinger, A. 2008. An algorithmic approach to geographic routing in ad hoc and sensor networks. IEEE/ACM Trans. Netw. 16, 1 (Feb.), 51–62.
  20. Leong, B., Mitra, S., and Liskov, B. 2005. Path vector face routing: Geographic routing with local face information. In 13TH IEEE International Conference on Network Protocols (ICNP’05), pp. 12–pp. IEEE.
  21. Li, J., Jannotti, J., De Couto, D. S. J., Karger, D. R., and Morris, R. 2000. A scalable location service for geographic ad hoc routing. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, MobiCom ’00, New York, NY, USA, pp. 120–130. ACM.
  22. Li, X., Yang, J., Nayak, A., and Stojmenovic, I. 2012. Localized geographic routing to a mobile sink with guaranteed delivery in sensor networks. IEEE Journal on Selected Areas in Communications 30, 9, 1719–1729.
  23. Liu, W. J. and Feng, K. T. 2009. Greedy routing with anti-void traversal for wireless sensor networks. IEEE Transactions on Mobile Computing 8, 7 (July), 910–922.
  24. Ma, X., Sun, M.-T., Zhao, G., and Liu, X. 2008. An efficient path pruning algorithm for geographical routing in wireless networks. IEEE Transactions on Vehicular Technology 57, 4, 2474–2488.
  25. Moraru, L., Leone, P., Nikoletseas, S., and Rolim, J. 2008. Geographic routing with early obstacles detection and avoidance in dense wireless sensor networks. In Proceedings of the 7th International Conference on Ad-hoc, Mobile and Wireless Networks, ADHOC-NOW ’08, Berlin, Heidelberg, pp. 148–161. Springer-Verlag.
  26. Moraru, L., Leone, P., Nikoletseas, S., and Rolim, J. D. P. 2007. Near optimal geographic routing with obstacle avoidance in wireless sensor networks by fast-converging trust-based algorithms. In Proceedings of the 3rd ACM Workshop on QoS and Security for Wireless and Mobile Networks, Q2SWinet ’07, New York, NY, USA, pp. 31–38. ACM.
  27. Na, J. and Kim, C.-k. 2006. Glr: A novel geographic routing scheme for large wireless ad hoc networks. Comput. Netw. 50, 17 (Dec.), 3434–3448.
  28. Ruhrup, S. and Stojmenovi ¨ c, I. ` 2010. Contention-based georouting with guaranteed delivery, minimal communication overhead, and shorter paths in wireless sensor networks. In Parallel Distributed Processing (IPDPS), 2010 IEEE International Symposium on, pp. 1–9.
  29. Sharma, R., Awasthi, L. K., and Naveen, C. 2016. Minimal marking of trap-regions for efficient greedy forwarding in wsns. International Journal of Next Generation Computing 7, 1 (March), 58–68.
  30. Stojmenovic, I. and Lin, X. 2001. Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Trans. Parallel Distrib. Syst. 12, 10 (Oct.), 1023–1032.
  31. Tan, G. and Kermarrec, A.-M. 2012. Greedy geographic routing in large-scale sensor networks: a minimum network decomposition approach. IEEE/ACM Transactions on Networking (TON) 20, 3, 864–877.
  32. Varga, A. 2010. Omnet++. In Modeling and Tools for Network Simulation, pp. 35–59. Springer.