A Survey on Cellular Automata based WSN Models

A Survey on Cellular Automata based WSN Models

Aniruddha. A. Pore Department of Information Technology Walchand College of Engineering, Sangli

Sangli, India

Shefali. P. Sonavane Department of Information Technology Walchand College of Engineering, Sangli

Sangli, India

Abstract Recently many applications of Cellular Automata are being discovered. One of them is modeling a simple Wireless Sensor Network. Many researchers have found that Cellular Automata can be efficiently and effectively used to model a simple WSN. In this paper a survey has been made for exploring CA based WSN models. A simple CA based WSN model is implemented for node scheduling and visualizing nodes state behavior using MATLAB environment. This research helped to overview the challenges faced in modeling the WSN using CA and future scope of these models.

Keywords Cellular Automata (CA), Wireless Sensor Network (WSN), network energy, network lifetime, connectivity, coverage, simulation, convergence.

1. INTRODUCTION

   1. Wireless Sensor Network (WSN)

      Due to the advancement of sensor communication technology, WSN [1] have been used in many applications. The sensor nodes are the main components of a WSN. A sensor node is a low cost small device with limited battery power, short communication range, limited processing power and limited memory. A typical WSN forms a distributed information processing system that gathers and processes various attributes of the network like humidity, temperature, etc. A traditional WSN also includes single or multiple base stations that gathers data from the sensors.

   2. Cellular automaton (CA)

      A cellular automaton (CA) [2] is a discrete model which is studied in wide range of domains such as computability theory, mathematics, theoretical biology, microstructure modeling and list goes on. In simple, it can be defined as quadruples (C, S, N, f) where C denotes n – dimensional cellular space (mostly one or two dimensional). S denotes set of possible states that each cell may take. N denotes the set of neighborhoods and f denotes transition function (or a rule) which is defined in terms of the states of cells that are part of a neighbourhood.

      Classification [3] includes four classes as:

      • Class 1: Pattern evolves into Homogeneous state.

      • Class 2: Pattern evolves to stable and periodic structures.

      • Class 3: Pattern evolves to chaotic structure.

      • Class 4: Pattern evolves to complex localized structures, sometimes long lived.

   3. Modelling a WSN using CA

      Following are some motivations for modelling WSN using CA.

      • One of the main features of the sensor network is locality. Some decisions are made locally (in distributed WSN solutions) by sensor nodes. Decisions such as whether to stay alive or go into sleep mode or communicate with neighbor. This local decision making is quite similar in CA using neighborhood structure like Moore neighborhood or Von Neumann neighborhood [3].

      • Each node consists of a processor that node communicate with its neighbors which is similar to CA structure.

      • WSN is discrete event model and so CA can be used to simulate such models and similar complex systems.

      • A large number of connected cells act as a parallel computing machine.

      • CA has been used as a theoretical tool for studying complexity and pattern formation.

   4. Terminologies

      Following are some terms considered in various CA based WSN models.

      • Network Lifetime: Time duration till last sensor is alive.

      • Network energy (or global energy): The sum of the residual energy remaining in all nodes at a particular time t.

      • Coverage: It is the capability of network to monitor a given area.

      • Connectivity: A metric to tell how strongly various network parts are connected to each other. In CA the mapping is like if a cell has at least one live neighbor then it is considered as connected.

      • Convergence: A provision to allow various services in a single network.

      • Active nodes: Count of all sensor nodes that are in active mode at time t.

      • Live nodes: Count of all sensor nodes at time t that still have energy.

2. LITERATURE SURVEY

   Till date many researches have been studied over WSN, but less effort are experimented on CA based WSN models. This section emphasizes more on CA based WSN models and its challenges.

   As the limited energy is a very important aspect of the WSN, maximizing the network lifetime while maintaining the coverage is a well-studied research problem in WSN. There are different algorithmic solutions for some problem. Some solutions are centralized and few are distributed. Centralized solutions face problems in scalability and are not supporting for some applications of the sensor networks, for example; animal monitoring, battlefield, etc. On the other hand, in a distributed solution, a sensor needs to communicate lots of messages with its neighbors that require energy too! However, in a local solution the sensor node requires little information to compute and is an ideal candidate for the various optimization problems of sensor networks.

   In the paper [4] authors proposed Topology Control Algorithm (TCA). They have considered Moore neighborhood (eight neighbors) structure. The authors TCA defines that nodes will become active only if there are less than two active neighbors else they will remain idle. They introduced an innovative idea of random decision making (at random time) of idle nodes to avoid repetitive pattern in node scheduling. They have developed java application for visualization and simulation. It takes network size and sensor nodes deployment scheme as input and returns number of active nodes and idle nodes in each step of simulation period. Topology schemes considered are full, random, row, circular and sparse arrangement of sensor nodes. Evaluation parameters considered are total network energy, coverage and connectivity. In evaluation two schemes are considered (full and random) and are compared with no algorithm on full deployment.

   In the paper [5] authors proposed deterministic and probabilistic algorithms. They focused on problem of maintaining field coverage, reducing energy consumption and improving the network lifetime. In CA model they have considered four neighborhoods structure. Simulation is carried out in MATLAB environment. They made comparison between deterministic and probabilistic algorithm and found that deterministic algorithm is slightly unstable in case of coverage. Variation is in between 70% and 30% coverage of network maintaining mean coverage around 50% in deterministic algorithm. Probabilistic algorithm shows stability in coverage and average coverage is about 60%. In result analysis of number of live sensors in each time step, deterministic algorithm shows staircase pattern while probabilistic algorithm shows smooth pattern. For energy consumption parameter both algorithms show linear decrease in energy. Energy consumption in deterministic algorithm is slower than in probabilistic algorithm. It shows significant increase in network lifetime.

   In the paper [6] authors proposed simple Topology Control Algorithm. Simulation is done using discrete event simulator

   i.e. CASim. In CA, neighborhood structure considered is Moore neighborhood. They introduced verification algorithm so as to reduce action of turning node on or off (in each time

   unit of network lifespan) which is expensiv in terms of energy. CA rule is that node will become active only if there are less than two active neighbors else it will remain idle. They used the traditional metrics such as global energy, coverage, active nodes and network lifetime to evaluate results. Result analysis indicates that CA can be used effectively to model WSN and there is a great scope to implement routing algorithms in CA based models.

   In the paper [7] authors proposed synchronous and asynchronous CA models. Metrics used to analyze the results are same traditional parameters i.e. network lifetime, live nodes, active nodes and global energy. Simulation is carried out in java simulator. Synchronous CA goes through problems like attenuation, periodic oscillations and homeostasis. In attenuation, after certain period CA stops at fixed state and no longer changes its state thus this comes under class-1 CA. In periodic oscillations system oscillates between both coverage and connectivity and this type corresponds to class-2 CA. In homeostasis, there are small oscillations in terms of coverage and connectivity but system stays little stable for long period, this type cannot exactly match to class-3 or class-4 CA. To overcome this problem asynchronous CA is introduced. In this CA no two nodes in same area involve in state renewal action so as to avoid deadlock. In asynchronous CA coverage is above 95% and connectivity remains 60% when coverage reaches 100%.

   In the paper [8] authors proposed new CA model. Simulation is performed in OMNeT++ network simulation framework. They considered various simulation parameters such as PHY/MAC protocol, maximum datagram size, transmission distance, network range, data flow which make simulation more realistic. Simulation results are verified using three different models which include service centric model (SCM) [9], cluster model (CM) [10], and their own CA model (CAM). They applied LEACH [11] to CM and CAM and compared the model convergence (energy*delay with each time step). Results showed CAM with best convergence value (i.e. minimum) while SCM with worst (not fixed value). In consecutive simulations, models are compared with number of paths between two cells. It is found that only in CAM more number of paths were discovered than other two models. In final simulation they included dynamic environment (node movement). Final result analysis shows that CAM achieves best performance even with increasing dynamic rate.

3. SIMPLE CA MODEL

   The simple CA based WSN model is implemented in laboratory for verification with certain assumptions and considerations. In this model each cell represents single sensor node.

   1. Assumptions [12]

      1. Homogeneous network (all nodes have same amount of energy).

      2. Every node is in range of sink node.

      3. Every node transfers k bits in one time unit to sink node when it is in active mode.

   2. Considerations [12]

      1. 6 * 6 grid network topology (total of 36 equally spaced nodes).

      2. Transmitting power ETX = 24.75 mW.

      3. Sleeping power ESL = 15 µW

      4. Each node has 0.5 J of energy at initial configuration.

      5. Simulation time is 1000 units.

      6. Value of k is 4000 bits.

   3. CA based algorithm

   Each cell at time t makes a decision of whether to stay in active or go into sleep mode. For making such decision at time t+1, it considers cellular space at time t. Node can be in two modes active or sleep. If a node has less than two active neighbors it goes or remain into sleep mode else become or remain active. In sleep mode node consumes some power which is considered as ESL. Similarly in active mode, node consumes ETX amount of energy. If the node becomes dead (i.e. if it runs out of energy) then it will go in sleep mode and no longer changes its state.

4. SIMULATION RESULTS

   Simulation is carried on desktop pc with AMD Phenom II

   3.2 GHz Quad core process, 8GB of RAM and using MATLAB® programming environment. Visualization of nodes state is made using various symbols.

   Diamond – active state of node. Circle – sleep state of a node. Cross – dead state of a node.

   Two metrics are considered for entire evaluation, number of live nodes (Figure.5) which was extension to [3] and total energy of network (Figure.6) in each time unit t.

   Fig.1 shows network state at time step = 1 which is the initial configuration of the network with 6 x 6 node grid.

   Figure 1. nodes state at time step = 1 unit

   Figure 2 shows network state at time step = 300 unit. Figure 3 shows network state at time step = 405 unit, when some of the nodes become dead for first time. The drastic drop to number of live nodes can be seen in Figure.5. This drastic change is due to implementation of deterministic algorithm, which is in-line with result discussed in [4]. In Figure 4 all nodes become dead at time step = 809 unit. Figure 6 shows

   Total energy (remaining energy) of network in each time step. After 800 time step some energy remained that is due to threshold value of node to become dead.

   Figure 2. nodes state at time step = 300 unit

   Figure 3. Nodes state at time step = 405 unit (first dead nodes)

   Figure 4. Nodes state at time step =809 unit ( all nodes become dead)

   Figure 5. Number of live nodes vs. time step.

   Figure 6. Network energy vs time step

5. DISCUSSION

   The discussions made are summarized and compared in Table I.

   WSN Parameter	References
   	[3]	[4]	[5]	[6]	[7]
   Energy constraints of sensor nodes	Yes	Yes	Yes	Yes	Yes
   Type of network	Homoge neous	Homog eneous	Homoge neous	Homoge neous	Homoge neous
   Topology	Grid, Row, Circular, Random	Grid	Grid	Grid	Random
   Mobility of nodes	No	No	No	No	Yes
   Data communication	No	No	No	No	Yes
   MAC protocol	No	No	No	No	Yes
   Routing protocol	No	No	No	No	No
   Scalability of deployment	No	No	No	No	No

   WSN Parameter	References
   	[3]	[4]	[5]	[6]	[7]
   Energy constraints of sensor nodes	Yes	Yes	Yes	Yes	Yes
   Type of network	Homoge neous	Homog eneous	Homoge neous	Homoge neous	Homoge neous
   Topology	Grid, Row, Circular, Random	Grid	Grid	Grid	Random
   Mobility of nodes	No	No	No	No	Yes
   Data communication	No	No	No	No	Yes
   MAC protocol	No	No	No	No	Yes
   Routing protocol	No	No	No	No	No
   Scalability of deployment	No	No	No	No	No

   TABLE I. ANALYSIS

   It is observed that the type of network considered is homogeneous only in all studies. If heterogeneous type of network is considered, more issues will rise. In that case, design of CA and its evolution is the problem of concern. The conventional routing protocols if used; the situation can be handled case by case. Similarly, if the WSN is understood with broader scope, the problem of scalability, topology reconstruction, its energy related issues and overall deployment is a serious challenge.

6. REMARK

The study helped to overview various CA based WSN models. It is found that some of the WSN parameters are considered for modeling. For certain application based WSN if parameter like heterogeneous network is considered various challenges will arise such as overlapping of various communication technologies (in particular protocols), scalability. In experimental CA model it is intended to modify to a probabilistic algorithm and add WSN parameter like data communication and routing protocol for future extension.

REFERENCES

1. I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, A survey on sensor networks, IEEE Communications Magazine, vol. 43, no. 8, pp. 102-114, 2002.

2. T. Toffoli, and N. H. Margolus, Cellular Automata Machines: a New Environment for Modeling, The MIT Press(1987).

3. https://en.wikipedia.org/wiki/Cellular_automaton

4. S. Athanassopoulos, C. Kaklamanis, P. Katsikouli and E. Papaioannou, Cellular Automata for Topology Control in Wireless Sensor Networks, Electrotechnical Conference (MELECON), 2012 16th IEEE Mediterranean, pp 212 215, Mar. 2012.

5. X. Xu, X. Zhang, L. Wang,Simulating energy efficient wireless sensor networks using cellular automata, Simulation Conference (WSC), Proceedings of the 2011 Winter, pp 3202 3211, Dec. 2011.

6. R. Cunha, A. Silva, A. Loreiro, L. Ruiz, Simulating Large Wireless Sensor Networks Using Cellular Automata, Simulation Symposium, 2005. 38th Annual Proceedings. pp 323 330, Apr. 2005.

7. W. Li, A. Zomaya, A. Al-Jumaily, Cellular Automata Based Models of Wireless Sensor Networks, 7th ACM International Symposium on Mobility Management and Wireless Access, pp. 1 6, Jan. 2009.

8. Y. Wang, Z. Qian, D. Sun, C. Zhou, A Cellular Automata Model for Wireless Sensor Networks, ICONS 2012. The Seventh International Conference on Systems, pp 169-174, Mar. 2012.

9. D. Gracanin, M. Eltoweissy, A. Wadaa, amd L. A. DaSilva,A Service- Centric Model for Wireless Sensor Networks, IEEE Journal on Selected Areas in Communications, vol. 23, no. 6, pp. 1159-1165, Jun. 2005.

10. A. Koubaa, M. Alves, and E. Tovar, Modeling and Worst-Case Dimensioning of Cluster-Tree Wireless Sensor Networks, Proceedings of 27th IEEE International Real-Time Systems Symposium, pp. 412- 421, 2006.

11. W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan, An application- specific protocol architecture for wireless microsensor networks, IEEE Transactions on Wireless Communication, vol. 1, no. 4, pp. 660-670, 2002.

12. H. Byun and J. Yu Cellular-Automaton-Based Node Scheduling Control for Wireless Sensor Networks, IEEE transactions on vehicular technology, vol. 63, no. 8, Oct. 2014.