Abstract
We present Obstacle-aware Virtual Circuit geographic Routing (OVCR), a novel routing mechanism for obstacle-aware wireless sensor networks that uses the obstacle-free path computed by the sink to make the greedy forwarding of geographic routing dependable. OVCR discovers obstacle-free paths by the powerful sink as obstacles are detected. To bypass obstacles, the information of obstacle-free paths is forwarded to sensors close to obstacles for finding virtual circuits in a distributed manner. A virtual circuit containing a sequence of relay positions (temporary destinations) is used for obstacle-free data packet forwarding. Data packets can then be forwarded greedily, either by the location of the destination, or the relay position. Simulation results show that OVCR is more dependable since the success rate of packet forwarding is raised and more efficient since the hop count is reduced.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Akyildiz, F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: a survey. Computer Networks 38(4), 393–422 (2002)
Kuhn, F., Wattenhofer, R., Zollinger, A.: An Algorithmic Approach to Geographic Routing in Ad Hoc and Sensor Networks. IEEE/ACM Trans. on Networking 16(1), 51–62 (2008)
Chang, Y.S., Hsu, M.T., Junag, T.Y., Liu, H.H.: Fault-map based Dependable Geographical Routing on Wireless Sensor Networks. In: Lee, Y.-H., Kim, H.-N., Kim, J., Park, Y.W., Yang, L.T., Kim, S.W. (eds.) ICESS 2007. LNCS, vol. 4523, pp. 403–414. Springer, Heidelberg (2007)
Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric Ad-Hoc Routing: of Theory and Practice. Principles of Distributed Computing, 63–72 (2003)
Yu, Y., Estrin, D., Govindan, R.: Geographical and Energy Aware Routing: a recursive data dissemination protocol for wireless sensor networks, UCLA Computer Science Department Technical Report (2001)
Karp, B., Kung, H.T.: GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In: MobiCom 2000, pp. 243–254 (2000)
Ji, X., Zha, H.: Sensor Positioning in Wireless Ad-hoc Sensor Networks Using Multidimensional Scaling. In: INFOCOM 2004, vol. 4, pp. 2652–2661 (2004)
Al-Karaki, J.N., Kamal, A.E.: Routing Techniques in Wireless Sensor Networks: a survey. IEEE Wireless Communications 11(6), 6–28 (2004)
Fang, Q., Gao, J., Guibas, L.J.: Locating and Bypassing Routing Holes in Sensor Networks. Mobile Networks and Applications 11(2), 187–200 (2006)
Funke, S.: Topological Hole Detection in Wireless Sensor Networks and its Applications. In: Proc. of the 2005 joint workshop on Foundations of mobile computing, pp. 44–53 (2005)
Chang, Y.S., Juang, T.Y., Lo, C.J., Hsu, M.T., Huang, J.H.: Fault Estimation and Fault Map Construction in Cluster-Based Wireless Sensor Networks. In: Proc. of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, vol. 2, pp. 14–19 (2006)
Luo, X., Dong, M., Huang, Y.: On Distributed Fault-Tolerant Detection in Wireless Sensor Networks. IEEE Trans. on Computers 55(1), 58–70 (2006)
Tseng, Y.C., Pan, M.S., Tsai, Y.Y.: Wireless Sensor Networks for Emergency Navigation. IEEE Computer 39(7), 55–62 (2006)
Li, Q., Rus, D.: Navigation Protocols in Sensor Networks. ACM Trans. on Sensor Networks 1(1), 3–35 (2005)
Karlof, C., Wagner, D.: Secure routing in wireless sensor networks: attacks and countermeasures. Ad Hoc Networks 1(2-3), 293–315 (2003)
Sun, B., Osborne, L., Xiao, Y., Guizani, S.: Intrusion Detection Techniques in Mobile Ad Hoc and Wireless Sensor Networks. IEEE Wireless Communications 14(5), 56–63 (2007)
Leong, B., Liskov, B., Morris, R.: Geographic Routing without Planarization. In: Proceedings of NSDI (2006)
Clouqueur, T., Saluja, K.K., Ramanathan, P.: Fault Tolerance in Collaborative Sensor Networks for Target Detection. IEEE Trans. on Computers 53(3), 320–333 (2004)
Jain, R., Puri, A., Sengupta, R.: Geographical Routing Using Partial Information for Wireless Ad Hoc Networks. IEEE Personal Communication 8(1), 48–57 (2001)
Finn, G.G.: Routing and Addressing Problems in Large Metropolitanscale Internetworks, USC/ISI Report ISU/RR-87-180 (1987)
Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proc. the 11th Canadian Conference Computer Geometry (1999)
Boukerche, A., Chatzigiannakis, I., Nikoletseas, S.: A new energy efficient and fault-tolerant protocol for data propagation in smart dust networks using varying transmission range. Computer Comm. 29(4), 477–489 (2006)
Rao, A., Papadimitriou, C., Shenker, S., Stoica, I.: Geographic routing without location information. In: Proc. of the 9th Annual International Conference on Mobile Computing and Networking, pp. 96–108 (2003)
Toussaint, G.T.: A simple linear algorithm for intersecting convex polygons. The Visual Computer 1, 118–123 (1985)
Toussaint, G.T.: Solving geometric problems with the rotating calipers. In: Proc. of IEEE MELECON 1983 (1983)
Hsu, M.T., Lin, F.Y.S., Chang, Y.S., Junag, T.Y.: The Fault Probability Estimation and Decision Reliability Improvement in WSNs. In: IEEE TENCON (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hsu, MT., Lin, F.YS., Chang, YS., Juang, TY. (2009). Reliable Greedy Forwarding in Obstacle-Aware Wireless Sensor Networks. In: Hua, A., Chang, SL. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2009. Lecture Notes in Computer Science, vol 5574. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03095-6_75
Download citation
DOI: https://doi.org/10.1007/978-3-642-03095-6_75
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03094-9
Online ISBN: 978-3-642-03095-6
eBook Packages: Computer ScienceComputer Science (R0)