Simulation of Topology Control Algorithms in Wireless Sensor Networks Using Cellular Automata

Stavros Athanassopoulos, Christos Kaklamanis, Gerasimos Kalfountzos, Panagiota Katsikouli, Evi Papaioannou

.
Computer Technology Institute & Press “Diophantus”, Rion, Greece.

DOI: 10.4236/ijcns.2013.67036                

Abstract

We use cellular automata for simulating a series of topology control algorithms in Wireless Sensor Networks (WSNs) using various programming environments. A cellular automaton is a decentralized computing model providing an excellent platform for performing complex computations using only local information. WSNs are composed of a large number of distributed wireless sensor nodes operating on batteries. The objective of the topology control problem in WSNs is to select an appropriate subset of nodes able to monitor a region at a minimum energy consumption cost and, therefore, extend network lifetime. Herein, we present topology control algorithms based on the selection—in a deterministic or randomized way—of an appropriate subset of sensor nodes that must remain active. We use cellular automata for conducting simulations in order to evaluate the performance of these algorithms and investigate the effect/role of the neighbourhood selection in the efficient application of our algorithms. Furthermore, we implement our simulations in Matlab, Java and Python in order to investigate in which ways the selection of an appropriate programming environment can facilitate experimentation and can result in more efficient application of our algorithms.

Keywords

Cellular Automata; Neighbourhood; Topology Control; WSN; Simulation; Matlab; Java; Python

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	J. V. Neumann, “The Theory of Self-Reproducing Automata,” (Edited and Completed by A. W. Burks), University of Illinois Press, Urbana and London, 1966.
[2]	M. Gardner, “The Fantastic Combinations of John Conway’s New Solitaire Game ‘Life’,” Scientific American, Vol. 223, 1970, pp. 120-123.
[3]	B. Chopard and M. Droz, “Cellular Automata Modeling of Physical Systems,” Cambridge University Press, Cambridge, 1998.
[4]	A. Ilachinski, “Cellular Automata: A Discrete Universe,” World Scientific Publishing Co. Pte. Ltd, London, 2001.
[5]	S. Wolfram, “A New Kind of Science,” Wolfram Media, Inc., Champaign, 2002.
[6]	S. Wolfram, “Theory and Applications of Cellular Automata,” World Scientific, Singapore City, 1986.
[7]	M. Nowak and R. May, “Evolutionary Games and Spatial Chaos,” Nature, Vol. 359, No. 6398, 1992, pp. 826-829. doi:10.1038/359826a0
[8]	B. Applebaum, Y. Ishai and E. Kushilevitz, “Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?” Proceedings of the 1st Symposium on Innovations in Computer Science (ICS 10), Beijing, 5-7 January 2010, pp. 1-19.
[9]	H. Beigy and M. R. Meybodi, “A Self-Organizing Channel Assignment Algorithm: A Cellular Learning Automata Approach,” Intelligent Data Engineering and Automated Learning, Vol. 2690, 2003, pp. 119-126.
[10]	N. Ganguly, B. K. Sikdar, A. Deutsch, G. Canright and P. Pal Chaudhuri, “A Survey on Cellular Automata,” Technical Report, Centre for High Performance Computing, Dresden University of Technology, Dresden, 2003.
[11]	A. Boondirek, W. Triampo and N. Nuttavut, “A Review of Cellular Automata Models of Tumor Growth,” International Mathematical Forum, Vol. 5, No. 61, 2010, pp. 3023-3029.
[12]	T. Tome and J. R. D. De Felicio, “Probabilistic Cellular Automata Describing a Biological Immune System,” Physical Review E, Vol. 53, No. 4, 1996, pp. 3976-3981. doi:10.1103/PhysRevE.53.3976
[13]	P. Sloot, F. Chen and C. Boucher, “Cellular Automaton Model of Drug Therapy for HIV Infection,” Proceedings of the 5th International Conference on Cellular Automata for Research and Industry (ACRI 02), Geneva, 9-11 October 2002, pp. 282-293.
[14]	G. Iovine, S. Di Gregorio and V. Lupiano, “Debris-Flow Susceptibility Assessment through Cellular Automaton Modeling: An Example from 15-16 December 1999 Disaster at Cervinara and San Martino Valle Caudina (Campania, Southern Italy),” Natural Hazards and Earth System Sciences, Vol. 3, 2003, pp. 457-468. doi:10.5194/nhess-3-457-2003
[15]	M. Mitchell, P. T. Hraber and J. P. Crutcheld, “Revisiting the Edge of Chaos: Evolving Cellular Automata to Perform Computations,” Complex Systems, Vol. 7, No. 2, 1993, pp. 89-130.
[16]	H. Demirel and M. Cetin, “Modelling Urban Dynamics via Cellular Automata,” Proceedings of the 7th AGILE Conference on Geographic Information Science, Haifa, 15-17 March2010, pp. 313-323.
[17]	L. Z. Yang, W. F. Fang, J. Li, R. Huang and W. C. Fan, “Cellular Automaton Pedestrian Movement Model Considering Human Behavior,” Chinese Science Bulletin, Vol. 48, No. 16, 2003, pp. 1695-1699.
[18]	S. Athanassopoulos, C. Kaklamanis, G. Kalfountzos and E. Papaioannou, “Cellular Automata for Topology Control in Wireless Sensor Networks using Matlab,” Proceedings of the 7th FTRA International Conference on Future Information Technology (FutureTech 12), Vancouver, 26-28 June2012, pp. 13-21.
[19]	S. Athanassopoulos, C. Kaklamanis, P. Katsikouli and E. Papaioannou, “Cellular Automata for Topology Control in Wireless Sensor Networks,” Proceedings of the 16th Mediterranean Electrotechnical Conference (Melecon 12), Yasmine Hammamet, 25-28 March 2012, pp. 212-215.
[20]	R. O. Cunha, A. P. Silva, A. A. F. Loureiro and L. B. Ruiz, “Simulating Large Wireless Sensor Networks using Cellular Automata,” Proceedings of the 38th Annual Simulation Symposium, Washington DC, 4-6 April 2005, pp. 323-330.
[21]	W. Li, A. Y. Zomaya, and A. Al-Jumaily, “Cellular Automata Based Models of Wireless Sensor Networks,” Proceedings of the 7th ACM International Symposium on Mobility Management and Wireless Access (MobiWAC 09), New York, 2009, pp. 1-6.
[22]	B. Qela, G. Wainer and H. Mouftah, “Simulation of Large Wireless Sensor Networks using Cell-DEVS,” Proceedings of the 2009 Winter Simulation Conference, Austin, 13-16 December 2009, pp. 3189-3200.
[23]	W. Zhang, L. Zhang, J. Yuan, X. Yu and X. Shan, “Demonstration of Non-Cluster Based Topology Control Method for Wireless Sensor Networks,” Proceedings of the 6th IEEE Consumer Communications and Networking Conference (CCNC 2009), Las Vegas, 10-13 January 2009, pp. 1-2.
[24]	T. Lou, H. Tan, Y. Wang and F. C. M. Lau, “Minimizing Average Interference through Topology Control,” Algorithms for Sensor Systems, Vol. 7111, 2012, pp. 115-129.
[25]	P. Santi, “Topology Control in Wireless Ad-Hoc and Sensor Networks,” ACM Computing Surveys, Vol. 37, No. 2, 2005, pp. 164-194. doi:10.1145/1089733.1089736
[26]	M. Burkhart, M., P. von Rickenbach, R. Wattenhofer and A. Zollinger, “Does Topology Control Reduce Interference?” Proceedings of the 5th ACM International Symposium on Mobile ad hoc Networking and Computing (MobiHoc 2004), New York, ACM, 2004, pp. 9-19. doi:10.1145/989459.989462
[27]	T. Johansson and L. Carr-Motyckova, “Reducing Interference in Ad Hoc Networks through Topology Control,” Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC 2005), New York, 2005, pp. 17-23.
[28]	M. A. Labrador and P. M. Wightman, “Topology Control in Wireless Sensor Networks: With Companion Simulation Tool for Teaching and Research,” Springer, Berlin, 2009.
[29]	J. L. Schiff, “Partitioning Cellular Automata,” In: J. L. Schiff, Cellular Automata: A Discrete View of the World, John Wiley and Sons, Inc., Hoboken, 2008, pp. 115-116.
[30]	T. Toffoli and N. Margolus, “The Margolus Neighbourhood,” In: Cellular Automata Machines: A New Environment for Modeling, MIT Press in Scientific Computation, 1987, pp. 119-138.
[31]	B. Karp and H. T. Kung, “Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, New York, 2005, pp. 243-254.
[32]	F. Kuhn, R. Wattenhofer, Y. Zhang and A. Zollinger, “Geometric Ad-Hoc Routing: Of Theory and Practice,” Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, New York, 2003, pp. 63-72.
[33]	A. Rao, Ch. Papadimitriou, S. Shenker and I. Stoica, “Geographical Routing without Location Information,” Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, New York, 2003, pp. 96-108.
[34]	F. Ye, G. Zhong, S. Lu and L. Zhang, “Energy Efficient Robust Sensing Coverage in Large Sensor Networks,” UCLA Technical Report, 2002.