A Model for Obstacles to be used in Simulations of Wireless Sensor Networks and its Application in studying Routing Protocol Performance

Abstract

We propose a simple obstacle model to be used while simulating wireless sensor networks. To the best of our knowledge, this is the first time such an integrated and systematic obstacle model for these networks has been proposed. We define several types of obstacles that can be found inside the deployment area of a wireless sensor network and provide a categorization of these obstacles based on their nature (physical and communication obstacles, i.e. obstacles that are formed out of node distribution patterns or have physical presence, respectively), their shape and their change of nature over time. We make an eXtension to a custom-made sensor network simulator (simDust) and conduct a number of simulations in order to study the effect of obstacles on the performance of some representative (in terms of their logic) data propagation protocols for wireless sensor networks. Our findings confirm that obstacle presence has a significant impact on protocol performance, and also that different obstacle shapes and sizes may affect each protocol in different ways. This provides an insight into how a routing protocol will perform in the presence of obstacles and highlights possible protocol shortcomings. Moreover, our results show that the effect of obstacles is not directly related to the density of a sensor network, and cannot be emulated only by changing the network density.

Keywords

Applications in computer networks sensor networks modeling and simulation environments parallel and distributed computing performance evaluation obstacle avoidance routing

Get full access to this article

View all access options for this article.

References

I.F. Akyildiz , W. Su , Y. Sankarasubramaniam , and E. Cayirci. 2002. Wireless sensor networks: a survey. Journal of Computer Networks 38, 393—422.

A. Jardosh , E. Belding-Royer , K. Almeroth , and S. Suri. 2003. Towards realistic mobility models for mobile ad hoc networks. In Proceedings of 9th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2003), San Diego, CA, pp. 217—229.

A. Jardosh , E. Belding-Royer , K. Almeroth , and S. Suri. 2005. Real world environment models for mobile ad hoc networks. IEEE Journal on Special Areas in Communications Special Issue on Wireless Ad hoc Networks 23(3), 622—632.

Q. Fang , J. Gao and L. Guibas. 2004. Locating and Bypassing Routing Holes in Sensor Networks . In Proceedings of the 23rd Conference of the IEEE Communications Society (Infocom), pp. 2458—2468.

A. Rao , S. Ratnasamy , C. Papadimitriou , S. Shenker and I. Stoica. 2003. Geographic routing without location information. In Proceedings of 9th ACM/IEEE Annual International Conference on Mobile Computing (MOBICOM 2003), San Diego, CA, pp. 96— 108.

R. Fonseca , S. Ratnasamy , J. Zhao , C.T. Ee , D. Culler , S. Schenker , and I. Stoica. 2005. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), Boston, USA.

Y. Kim , R. Govindan , B. Karp and S. Schenker. 2005. Geographic Routing made practical. In Proceedings of 2nd Symposium on Networked Systems Design and Implementation NSDI 2005.

R.C. Shah , A. Wolisz , and J.M. Rabaey. 2005. On the Performance of Geographical Routing in the Presence of Localization Errors. In Proceedings of the IEEE International Conference on Communications (ICC 2005).

P. Bose , P. Morin , I. Stojmenovic , and J. Urrutia. 1999. Routing with guaranteed delivery in ad hoc wireless networks. In Proceedings of the ACM Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications , pp. 48—55.

10.

M. O' Dell , R. O' Dell , M. Wattenhofer and R. Wattenhofer. 2005. Lost in Space or Positioning in Sensor Networks. In Proceedings of the Workshop on Real-World Wireless Sensor Networks (RE-ALWSN'05).

11.

I. Chatzigiannakis , A. Kinalis , and S. Nikoletseas. 2006. Efficient and Robust Data Dissemination using Limited Extra Network Knowledge. In Proceedings of the IEEE International Conference on Distributed Computing in Sensor Networks (DCOSS), Lecture Notes in Computer Science (LNCS) , pp. 218—233, Springer Verlag.

12.

O. Powell and S. Nikoletseas. 2007. Simple and Efficient Geographic Routing around Obstacles for Wireless Sensor Networks. In Proceedings of the 6th Workshop on Experimental Algorithms (WEA07).

13.

T. Rappaport . 2000. Wireless communications: Principles and practice. Prentice Hall.

14.

Tossim. Simulating TinyOS Networks. http://www.cs.berkeley.edu/pal/research/tossim.html .

15.

A. Boukerche , S.K. Das , A. Fabbri , and O. Yildiz. 1999. Exploiting Model Independence for Parallel PCS Network Simulation. In Proceedings of ACM Workshop on Parallel and Distributed Simulation, 166—173.

16.

A. Boukerche , S.K. Das , and A. Fabbri. 2001. SWiMNet: A Scalable Parallel Simulation Testbed for Wireless and Mobile Networks. ACM/Kluwer Wireless Networks 7, 467—486.

17.

T. Antoniou , A. Boukerche , I. Chatzigiannakis , G. Mylonas , and S. Nikoletseas 2004. A new energy efficient and fault-tolerant protocol for data propagation in smart dust networks using varying transmission range. In Proceedings of 37th Annual Simulation Symposium (ANSS 2004), IEEE Press, pp. 43—52.

18.

I. Chatzigiannakis , T. Dimitriou , M. Mavronicolas , S. Nikoletseas , and P. Spirakis. 2003. A comparative study of protocols for efficient data propagation in smart dust networks. Journal of Parallel Processing Letters PPL 13(4), 615—627.

19.

I. Chatzigiannakis , T. Dimitriou , S. Nikoletseas , and P. Spirakis. 2006. A Probabilistic Algorithm for Efficient and Robust Data Propagation in Smart Dust Networks. In Proceedings of 5th European Wireless Conference on Mobile and Wireless Systems beyond 3G (EW 2004), pp. 344—350.

20.

I. Chatzigiannakis and S. Nikoletseas. 2003. A sleep-awake protocol for information propagation in smart dust networks. In Proceedings of 3rd International Workshop on Mobile, Ad-hoc and Sensor Networks (WMAN 2003), IPDPS Workshops, p. 225. [21] I. Chatzigiannakis , S. Nikoletseas , and P. Spirakis. 2002. Smart dust protocols for local detection and propagation. In Proceedings of 2nd ACM International Annual Workshop on Principles of Mobile Computing (POMC 2002), pp. 9—16.

21.

S. Nikoletseas , I. Chatzigiannakis , H. Euthimiou , A. Kinalis , T. Antoniou , and G. Mylonas. 2004. Energy efficient protocols for sensing multiple events in smart dust networks . In Proceedings of 37th Annual Simulation Symposium (ANSS 2004), IEEE Press, pp. 15—24.

22.

I. Chatzigiannakis , G. Mylonas , and S. Nikoletseas. 2006. Modeling and Evaluation of the Effect of Obstacles on the Performance of Wireless Sensor Networks . In Proceedings of ANSS '06, pp. 50— 60.

23.

A. Boukerche , R.W.N. Pazzi , and R.B. Araujo. 2004. A supporting protocol to periodic, event-driven and query-based application scenarios for critical conditions surveillance. In Proceedings of 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS 2004), Springer-Verlag, Lecture Notes in Computer Science, LNCS 3121, pp. 137—146.

24.

C. Intanagonwiwat , R. Govindan , and D. Estrin. 2000. Directed diffusion: A scalable and robust communication paradigm for sensor networks. In Proceedings of 6th ACM/IEEE Annual International Conference on Mobile Computing, pp. 56—67.

25.

W.R. Heinzelman , A. Chandrakasan , and H. Balakrishnan. 2000. Energy-efficient communication protocol for wireless microsensor networks . In Proceedings of 33rd IEEE Hawaii International Conference on System Sciences, pp. 3005—3014.