 Open Access
 Total Downloads : 85
 Authors : Aniruddha. A. Pore, Shefali. P. Sonavane
 Paper ID : IJERTV5IS020578
 Volume & Issue : Volume 05, Issue 02 (February 2016)
 DOI : http://dx.doi.org/10.17577/IJERTV5IS020578
 Published (First Online): 01032016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.

INTRODUCTION

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.

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.


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.


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.



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 wellstudied 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 class1 CA. In periodic oscillations system oscillates between both coverage and connectivity and this type corresponds to class2 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 class3 or class4 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.

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.

Assumptions [12]

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

Every node is in range of sink node.

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


Considerations [12]

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

Transmitting power ETX = 24.75 mW.

Sleeping power ESL = 15 ÂµW

Each node has 0.5 J of energy at initial configuration.

Simulation time is 1000 units.

Value of k is 4000 bits.


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.


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 inline 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

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.

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

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

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

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

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.

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.

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.

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

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 169174, Mar. 2012.

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. 11591165, Jun. 2005.

A. Koubaa, M. Alves, and E. Tovar, Modeling and WorstCase Dimensioning of ClusterTree Wireless Sensor Networks, Proceedings of 27th IEEE International RealTime Systems Symposium, pp. 412 421, 2006.

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. 660670, 2002.

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