Minimal Marking of Trap-Regions for Efficient Greedy Forwarding in WSNs

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

Published Mar 1, 2016
https://doi.org/10.47164/ijngc.v7i1.104
Download
pdf
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 7, Issue 1, March 2016

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

Rajesh Sharma
National Institute of Technology - Hamirpur
Lalit Kumar Awasthi
National Institute of Technology - Hamirpur
Naveen Chauhan
National Institute of Technology - Hamirpur

Abstract

Geographic routing has emerged as a promising routing paradigm for Wireless Sensor Networks (WSNs). Localized operation, stateless nature, and ability to operate in absence of unique node addresses, are some of the characteristics that make geographic routing particularly suitable for WSN applications. Greedy forwarding is a simpler and efficient form of geographic routing in which a packet is forwarded to a neighboring node that makes maximum positive progress towards the destination. However, in the presence of communication voids, greedy forwarding may fail at some dead-end – a node that does not have any optimal neighbor for greedy forwarding. The dead-end situation is usually handled by switching to some other supplementary routing methods like flooding, perimeter routing, or face routing, which are highly inefficient and hence should be avoided whenever possible. The overall performance of geographic routing methods which utilize greedy forwarding can be significantly improved by denying a packet originating in Greedily-Routable-Region (GRR) to enter into a dead-end region during routing. In this work, we propose a simple yet effective method called Minimal Marking of Trap-Regions (MMTR) for maximizing the GRR in WSNs. MMTR performs the on-demand marking of minimum nodes of a trap-region so as to transform a WSN into a dead-end free network for greedy forwarding. The proposed solution also addresses the hotspot problem observed along the border of dead-end region.

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

How to Cite
Rajesh Sharma, Lalit Kumar Awasthi, & Naveen Chauhan. (2016). Minimal Marking of Trap-Regions for Efficient Greedy Forwarding in WSNs. International Journal of Next-Generation Computing, 7(1), 58–68. https://doi.org/10.47164/ijngc.v7i1.104
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Anastasi, G., Conti, M., Di Francesco, M., and Passarella, A. 2009. Energy conservation in wireless sensor networks: A survey. Ad Hoc Netw. 7, 3 (May), 537–568.
  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. 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.
  4. Chen, D. and Varshney, P. K. 2007. A survey of void handling techniques for geographic routing in wireless networks. Commun. Surveys Tuts. 9, 1 (Jan.), 50–67.
  5. 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 Trans. Comput. 60, 11 (Nov.), 1610–1621.
  6. Fang, Q., Gao, J., and Guibas, L. J. 2006. Locating and bypassing holes in sensor networks. Mob. Netw. Appl. 11, 2 (April), 187–200.
  7. Finn, G. G. 1987. Routing and Addressing Problems in Large Metropolitan-Scale Internetworks. Heinzelman, W. R., Chandrakasan, A., and Balakrishnan, H. 2000. Energy-efficient communication protocol for wireless microsensor networks. In Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8 - Volume 8, HICSS ’00, Washington, DC, USA, pp. 8020–. IEEE Computer Society.
  8. Hightower, J. and Borriello, G. 2001. Location systems for ubiquitous computing. Computer 34, 8 (Aug.), 57–66.
  9. Hou, T.-C. and Li, V. 1986. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications 34, 1 (Jan), 38–44.
  10. Huc, F., Jarry, A., Leone, P., Moraru, L., Nikoletseas, S., and Rolim, J. 2009. Algorithmic aspects of wireless sensor networks. Chapter Early Obstacle Detection and Avoidance for All to All Traffic Pattern in Wireless Sensor Networks, pp. 102–115. Berlin, Heidelberg: Springer-Verlag.
  11. Intanagonwiwat, C., Govindan, R., and Estrin, D. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, MobiCom ’00, New York, NY, USA, pp. 56–67. ACM.
  12. Karl, H. and Willig, A. 2005. Protocols and Architectures for Wireless Sensor Networks. John Wiley & Sons.
  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. Ko, Y.-B. and Vaidya, N. H. 2000. Location-aided routing (lar) in mobile ad hoc networks. Wirel. Netw. 6, 4 (July), 307–321.
  17. Kranakis, E., Singh, H., and Urrutia, J. 1999. Compass routing on geometric networks. In Proceedings of 11th Canadian Conference On Coputational Geometry, pp. 51–54.
  18. 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.
  19. 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.
  20. 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.
  21. Leong, B., Liskov, B., and Morris, R. 2006. Geographic routing without planarization. In Proceedings of the 3rd Conference on Networked Systems Design & Implementation - Volume 3, NSDI’06, Berkeley, CA, USA, pp. 25–25. USENIX Association.
  22. Li, J. and Mohapatra, P. 2007. Analytical modeling and mitigation techniques for the energy hole problem in sensor networks. Pervasive Mob. Comput. 3, 3 (June), 233–254.
  23. 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 (October), 1719–1729.
  24. 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.
  25. 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.
  26. 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.
  27. Pottie, G. J. and Kaiser, W. J. 2000. Wireless integrated network sensors. Commun. ACM 43, 5 (May), 51–58.
  28. Powell, O. and Nikoletseas, S. E. 2007. Simple and efficient geographic routing around obstacles for wireless sensor networks. In Experimental Algorithms, 6th International Workshop, WEA 2007, Rome, Italy, June 6-8, 2007, Proceedings, pp. 161–174.
  29. 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.
  30. Takagi, H. and Kleinrock, L. 1984. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications COM-32, 3 (March), 246–257. (Also ”Multiple Access Communications, Foundations for Emerging Technologies”, Norman Abramson (Ed.), IEEE Press, 1992, pp.342-353.).
  31. Tan, G. and Kermarrec, A.-M. 2012. Greedy geographic routing in large-scale sensor networks: A minimum network decomposition approach. IEEE/ACM Trans. Netw. 20, 3 (June), 864–877.
  32. Tilak, S., Abu-Ghazaleh, N. B., and Heinzelman, W. 2002. A taxonomy of wireless micro-sensor network models. SIGMOBILE Mob. Comput. Commun. Rev. 6, 2 (April), 28–36.
  33. Xu, Y., Heidemann, J., and Estrin, D. 2001. Geography-informed energy conservation for ad hoc routing. In Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, MobiCom ’01, New York, NY, USA, pp. 70–84. ACM.
  34. Yu, Y., Govindan, R., and Estrin, D. 2001. Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks. Technical report.