Simulation of Topology Control Algorithms in Wireless Sensor Networks Using Cellular Automata ()
1. Introduction
A cellular automaton (CA) [1] is an idealization of a physical system in which space and time are discrete and the physical quantities take only a finite set of values. Informally, a cellular automaton is a lattice of cells, each of which may be in a predetermined number of discrete states (like, for instance, On/Off). The grid can be in any finite number of dimensions. A neighbourhood relation is defined over this lattice, indicating for each cell which cells are considered to be its neighbours during state updates. For example, the neighbourhood of a cell might be defined as the set of cells at distance two (i.e., two hops) or less from the cell.
In each time step, every cell updates its state using a transition rule that takes as input the states of all cells in its neighbourhood (which usually includes the cell itself). All cells in the cellular automaton are synchronously updated. At time t = 0 the initial state of the cellular automaton must be defined; then, repeated synchronous application of the transition function to all cells in the lattice will lead to the deterministic evolution of the cellular automaton over time. Typically, the rule for updateing the state of cells is the same for each cell and does not change over time, though exceptions are known.
Formally, a CA is a 4-tuple where C denotes a d-dimensional array of cells or lattice (cells are indexed by vectors from ZN), Σ denotes the alphabet giving the possible states each cell may take, N denotes the neighbourhood (i.e.,) and f denotes the transition function of type. The state of all cells in time is called configuration.
A cellular automaton is a discrete computational model, which is capable to provide the same computational power as Turing Machine, therefore it is Turing Complete. Cellular automata were firstly used by Jon von Neumann [1] in late 1940s when he was trying to describe a self-reproducing automaton. He succeeded by introducing two dimensional Von Neumann’s cellular automaton with rules and starting configuration such that after a certain amount of time steps there were two copies of the pattern from starting configuration and so on.
Cellular automata have received extensive academic study into their fundamental characteristics and capabilities and been applied successfully to the modeling of natural phenomena. In this respect, two notable developments can be credited to Conway and Wolfram. In the 1970, the mathematician John Conway proposed his now famous Game of Life [2] which received widespread interest among researchers. Conway’s CA involves a 2-dimensional infinite grid of cells where each cell has two possible states, dead or alive, and simulates the evolution of a population using four basic transition rules. Its neighbourhood consists of the middle cell and the eight cells surround it (i.e., Moore neighbourhood) [2-4] unlike the von Neumann neighbourhood that contains a cell together with the four cells in the four directions attached to it [1,3,4]. Later on, in 1980s, Stephen Wolfram [5] defined four classes of cellular automata depending on complexity and predictability of their behavior; he has also studied in much detail a family of simple one-dimensional CA rules (known as Wolfram rules [6]) showing that even these simplest rules are capable of emulating complex behavior.
Based on the theoretical concept of universality, researchers have tried to develop simpler and more practical architectures of CA that can be used to model widely divergent application areas, including theoretical biology [3], game theory [7] etc. In particular, CA have been suggested in public key cryptography [8], channel assignment in mobile networks [9], pattern recognition [10], games like the Firing Squad [6] etc. Furthermore, CA have been used in medical applications regarding the growth of tumors [11], the implementation of the immune system [12] and the treatment of HIV [13]. Other applications of CA include the simulation of natural phenomena [14,15], urban growth [16], behavior of a population in a certain situation [17] etc. Cellular automata have successfully been used as a means for modeling and simulation of topology control algorithms in Wireless Sensor Networks (WSNs) [18-23]. A WSN is a special kind of network composed of a large number of autonomous sensor nodes geographically scattered on a surface with the ability to monitor an area inside their range and collect data about physical and environmental conditions such as temperature, sound, vibration, pressure, motion or pollutants. A source collects this data and can be located anywhere in the network. WSNs were initially used by the army for tactical surveillance without the need of human presence; however, WSNs have been used in a wide range of applications, such as environmental monitoring, industrial process monitoring and control, machine health monitoring etc.
Important characteristics of WSNs include low computational power, low computational speed, small bandwidth, limited memory, limited energy, high failure tolerance, no demand for human or artificial supervision. The most important performance aspect in WSNs is the need to be energy efficient as sensor nodes have a finite energy reserve offered by a battery.
Topology control is a technique used to reduce the initial topology of a WSN in order to save energy, avoid interference and extend the lifetime of the network by discovering a minimum configuration of nodes capable of monitoring a region equivalent to the monitored one for all nodes [24,25]. Efficient topology control techniques in WSN are very critical and essential: sensors operate on limited energy (i.e., batteries). Managing this scarce resource efficiently by controlling the network topology directly influences (i.e., extends) the network lifetime. Evaluation of topology control algorithms requires simulation since setting up a real WSN is very costly. There is a long literature, both theoretical and experimental, on topology control algorithms for WSN [24,26-28].
In this work, we focus on a subset of topology control algorithms (duty cycling and scheduling while maintaining connectivity and coverage) and use the cellular automata simulation approach suggested in [20] in order to experimentally investigate which type of neighbourhood should be preferred for obtaining efficient simulations for topology control algorithms in WSN. Existing implementations of cellular automata have been developed using Java and C/C++, Matlab or C-based special-purpose simulating tools like COOJA, OMNeT++, Casim tool that require advanced programming skills on behalf of the user/developer. In our work, instead of using an existing simulator, we have used Matlab, Java and Python for implementing cellular automata from scratch: the main motivation for this approach has been to investtigate whether researchers who (do not wish to go into the details of an existing cellular automata simulator, but) prefer to build their own simple simulation environment using cellular automata can be assisted by very popular programming environments like Matlab, Java and Python.
The paper is organized as follows. In Section 2, we present the different neighbourhoods adopted in our work. The topology control algorithms suggested in this paper are presented in Section 3. We present implementation details and experimental results in Section 4 and we conclude in Section 5.
2. Neighbourhood Schemes
In order to investigate how the selection of the neighbourhood in cellular automata models can affect the performance of simulations of topology control algorithms in WSNs, various neighbourhood schemes have been studied.
In a cellular automaton, a neighbourhood relation is defined over a lattice of cells and indicates the neighbours of each cell considered during state updates. For example, the neighbourhood of a cell can be defined as the set of cells at distance two (i.e., two hops) or less from the cell. In each time step, every cell updates its state using a transition function/rule that takes as input the states of all cells in its neighbourhood (which usually includes the cell itself).
We investigate the effect that application of different neighbourhoods can have on the performance of a topology control algorithm in a WSN: for instance, assuming that each cell contains a sensor, the neighbourhood type adopted can impose limitations on the number of the active sensors used to cover an area.
In what follows, we briefly describe the neighbourhood schemes of the cellular automata used in our simulations.
The Moore neighbourhood [2-4] of a cell includes the central cell and the eight cells adjacent to it (Figure 1). The Von Neumann neighbourhood [1,3,4], shown in Figure 2, includes the central cell and the four cells that are horizontally and vertically adjacent to it. The Margolus neighbourhood [29,30], is the basic variation of cellular automata block neighbourhoods. At each step, the neighbourhood divides the lattice into blocks of four cells. Each cell belongs to two blocks that alternate during each time step according to whether the step is an odd or an even number. Margolus neighbourhood is presented in Figure 3. The Weighted Margolus neighbourhood [18] is a variation of the simple Margolus neighbourhood which uses weights. At each time step, each cell decides its state for the next step not only according to the neighbourhood block to which it belongs during the current step but also according to the neighbourhood block in which it belonged during the previous step. The overall size of the neighbourhood is 7 cells. The Block neighbourhood, shown in Figure 4, is a second variation of the simple Margolus neighbourhood. Each cell of the lattice belongs to four blocks of four cells each. Each block is used by the algorithm every four steps (in the same fashion as Margolus blocks).
The Weighted Block neighbourhood has been designed based on the main idea of the Weighted Margolus neighbourhood. In particual, we use the Block neighbourhood with weights. At each step, each cell makes decisions about its state in the next step not only according to the neighbourhood block that belongs to during the current time step but also according to the neighbourhood block to which it belonged two time steps earlier. That technique also results in a 7-cell neighbourhood. When a Slider neighbourhood is assumed, the lattice is divided into 3 × 3 blocks that share one common cell; these blocks alternate every three time steps (Figure 5). A Slider neighbourhood combines the advantage of a 9-cell neighbourhood, which increases knowledge of the
Figure 3. Margolus neighbourhood. Red and blue blocks are applied at odd and even times steps respectively.
surrounding environment of a particular cell (like for instance the Moore neighbourhood) and the interchange of blocks (like for instance the Margolus neighbourhood). In the recent literature, routing algorithms for wireless networks are based on the assumption that each node is aware of its neighbors [31,32] and of its neighbors’ neighbors positions [33]. According to this hypothesis, each sensor can be aware of the state of its surrounding cells (as in a Moore neighbourhood) and of the state of its neighbors at distance 2.
3. Topology Control Algorithms
Usually, in WSNs, an area is covered by redundant sensors due to their random deployment. When many redundant sensors remain active simultaneously, the global energy of the network is rapidly reduced and the network lifetime is being shortened. The main idea of a WSN topology control algorithm (as sketched in [34]) is that network nodes should remain active only if there are few neighbouring active nodes; otherwise they remain idle saving their energy.
In our work, we have implemented two basic Topology Control Algorithms (TCA) (together with several variations of them), namely TCA-1 and TCA-2, and have used cellular automata for experimentally studying their performance. All topology control algorithms are based on the selection of an appropriate subset of sensor nodes that must remain active. In TCA-1, the decision regarding the node state (active or idle) is made by the nodes themselves (i.e., according to the state of the nodes in their neighbourhood), while in TCA-2, this decision is made in terms of predefined categories in which nodes have been classified (i.e., nodes in one of these categories remain in their current states ignoring the state of the nodes in their neighbourhoods). The cellular automaton used for TCA-1 has been implemented in previous works using the Matlab [18] as well as the Java [19] programming environment. Furthermore, in this work, we have developed cellular automata for TCA-1 and TCA-2 using the Python programming environment.
The main idea of our topology control algorithms is that, every alive sensor node (i.e., active or idle), in every step, counts its active neighbours: if there are at least l active neighbours, the node becomes/remains idle; otherwise, the node becomes/remains active. By l we denote the maximum number of sensor nodes that must remain active during each time step assuming a particular neighbourhood scheme adopted for the cellular automaton used for simulation.
The sensor nodes of the network can be in one of three different states: active (i.e., the sensor monitors, transmits and wastes energy), idle (i.e., the sensor wastes a little energy in order to remain stand-by) and dead (i.e., the sensor has no energy and is turned off). Therefore, active and idle states imply that the sensor node is alive. Initially, each node has 0.8 units of energy; energy consumption is assumed to be 0.0165 units/step for active nodes and 0.00006 units/step for idle nodes [20,34]. A sensor node turns off when it runs out of energy. The algorithms implemented in our work terminate when there is no alive (active or idle) node in the network.
3.1. Topology Control Algorithm 1 (TCA-1)
The main idea of the basic version of TCA-1 lies in the selection of an appropriate subset of sensor nodes that must remain active in order to extend network lifetime, maintaining best possible coverage and connectivity. More specifically, nodes decide whether to remain active or idle based on the redundancy of active nodes in their neighbourhood. A detailed description of the basic version of TCA-1 can be found in [18].
The cellular automaton used for the simulation of TCA-1 and its variations uses a n × n lattice of cells. Each cell cij of the lattice represents a sensor node (a sensor of the network) and contains information about the sensor position in the network (determined by its coordinates (i,j)), its remaining energy, its state and a timer Tci,j (i.e., a counter). Cells can be in one of the following two states: a cell cij is in state 1 when the corresponding network node contains an active sensor; ci,j is in state 0 when the corresponding network node contains an idle sensor and cij is in state 2, when the corresponding network node contains a dead sensor (i.e., a sensor with no energy) or no sensor at all.
Initially, all network nodes are active (i.e., state 1). The timer Tcij assigned to each node is randomly initialized with an integer value in [0, 5] and decreases by one in each time step. When the value of the timer of a node decreases to zero, the node checks its neighbourhood for active nodes. If there are at least l active sensor nodes, the node is/remains deactivated (i.e., becomes idle); otherwise, the node becomes/remains active. The node re-initializes its timer and repeats the same procedure until it runs out of energy. The pseudo-code of TCA-1 is presented in Table 1.
Cellular Automata Used for the Simulation of Topology Control Algorithm 1 (TCA-1)
In our work, we have studied variations of the TCA-1 algorithm resulting from the neighbourhood schemes
used in the corresponding cellular automaton. In all variations, each alive sensor node in the WSN, counts in each time step the number of active sensor nodes in its neighbourhood in order to decide whether to remain/ become active or idle. l denotes the maximum necessary number of active sensor nodes at each time step in each neighbourhood and varies according to the neighbourhood scheme adopted. In the following, transition functions/rules of the corresponding cellular automata are presented in detail.
CAMoore is the cellular automaton used for the simulation of TCA-1 using a Moore neighbourhood (Figure 1). Nodes update their state based on the following rule: a node remains/becomes active if there are at most two (l = 2) active sensor nodes in its neighbourhood; otherwise it remains/becomes idle. Typically, this transition function can be expressed as:
otherwise, (1)
where denotes a cell, Sci.j denotes the cell state during each time step and Ni,j denotes the neighbourhood of cell cij.
CAvonNeumann is the cellular automaton used for the simulation of TCA-1 using a von Neumann neighbourhood (Figure 2). It uses the transition function given by Equation (1) presented before. Nodes update their state based on the following rule: a node remains/becomes active if there are at least two (l = 2) active sensor nodes in its neighbourhood; otherwise it remains/becomes idle.
CAMargolus is the cellular automaton used for the simulation of TCA-1 using a Margolus neighbourhood (Figure 3). The 4-cell blocks of each neighbourhood alternate during even and odd time steps. Nodes update their state based on the following rule: a node remains/becomes active if there are at most l active sensor nodes in its current neighbourhood block; otherwise it remains/becomes idle. Note that when CAMargolus is used, l can be either 1 or 2: when l = 1, at most 1 active sensor node can exist in each block per step. When l = 2, at most 2 active sensor nodes can exist in each block per step. Typically, this transition function can be expressed as:
otherwise. (2)
CAWMargolus is the cellular automaton used for the simulation of TCA-1 using a Weighted Margolus neighbourhood. At each time step, every sensor node which is alive counts the number of active nodes 1) in the neighbourhood block it belongs during the current time step, CB, and 2) in the neighbourhood block it belonged during the previous time step, PB. Nodes update their state based on the following rule: a node remains/becomes active if there is at most l = 1 active sensor node in both blocks CB and PB; otherwise it remains/becomes idle. Typically, the transition function can be expressed as:
otherwise. (3)
CABlock is the cellular automaton used for the simulation of TCA-1 using a Block neighbourhood (Figure 4). It uses the transition function given by Equation (2) presented before. Nodes update their state based on the following rule: a node remains/becomes active, if there are at most l active sensor nodes in its neighbourhood block; otherwise it remains/becomes idle. Note that when CABlock is used, l can be either 1 or 2: when l = 1, at most 1 active sensor node can exist in each block per step. When l = 2, at most 2 active sensor nodes can exist in each block per step.
CAWBlock is the cellular automaton used for the simulation of TCA-1 assuming a Weighted Block neighbourhood which is used in the same fashion as the Weighted Margolus neighbourhood in CAWMargolus. It uses transition function given by Equation (3) presented before. At each time step, every sensor node which is alive counts the number of active nodes 1) in the neighbourhood block it belongs during the current time step, CB, and 2) in the neighbourhood block it belonged two time steps ago, PB, (in order to form a 7-cell neighbourhood). Nodes update their state based on the following rule: a node remains/becomes active if there is at most l = 1 active sensor node in both blocks CB and PB; otherwise it remains/becomes idle.
CASlider is the cellular automaton used for the simulation of TCA-1 using a Slider neighbourhood (Figure 5). The 9-cell blocks of each neighbourhood alternate during even and odd time steps. Nodes update their state based on the following rule: a node remains/becomes active if there are at most l = 2 active sensor nodes in its current neighbourhood block; otherwise it remains/becomes idle. Typically, this transition function can be expressed as:
otherwise. (4)
3.2. Topology Control Algorithm 2 (TCA-2)
Like TCA-1, TCA-2 aims to select an appropriate subset of sensor nodes that must remain active in order to extend network lifetime, maintaining best possible coverage and connectivity. However, TCA-2 uses a simple (weak) source of randomization in order to more efficiently select the subset of sensor nodes that will remain active. Instead of letting all nodes decide whether they will remain active or idle based on the redundancy of active nodes in their neighbourhoods, a sort of node classification is induced and only 2/3 of the WSN nodes are randomly selected to make such a decision. The main intuition behind this trick lies in 1) uniformly selecting a “small”, “fixed” subset of active nodes and 2) facilitating nodes to make a more efficient decision on whether to remain active or idle by clarifying the redundancy level around them.
The cellular automaton used for the simulation of TCA-2 follows the description of that used for the simulation of TCA-1 but it additionally contains a clock attached to each cell which determines whether the cell will perform a topology control algorithm. The clock is initially randomly initialized with an integer value in [0, 2] and works according to the following rule:
• If its clock has the value 0 at step t, then the cell maintains its state during the current step and sets its clock value to 1.
• If its clock has the value 1 at step t, then the cell updates its state (according to TCA-2) during the current step and sets its clock value to 2.
• If its clock has the value 2 at step t, then the cell updates its state (according to TCA-2) during the current step and sets its clock value to 0.
The clock essentially implies the classification of sensor nodes into two distinct categories during a particular time step: nodes performing the topology control algorithm and nodes that do not.
Nodes update their status according to the following rule: when its timer decreases to zero, a node checks its neighbourhood (which includes the node itself) for active nodes. If there are at most two active nodes (l = 2), the node remains/becomes active; otherwise, the node becomes/remains idle. The node re-initializes its timer and repeats the same procedure until it runs out of energy. The pseudo-code of TCA-2 is presented in Table 2.
4. Implementation Details and Experimental Results
We have simulated algorithms TCA-1 and TCA-2 using cellular automata. We have also implemented variations of the basic version of TCA-1 using different neighbourhood schemes in the corresponding cellular automata. Our objective has been: 1) to evaluate how the type of neighbourhood adopted for our cellular automata can affect the performance of the simulation since it can impose limitations on the number of the active sensors used to cover an area and 2) to investigate whether randomization can result in more efficient topology control in WSN. In the following, implementation details and
experimental results are discussed.
Simulations have been developed in three very popular programming environments:
1) Matlab Version 7.0.0.19920 (R14), executed on an Intel Core i3 530 processor at 2.93 GHz with 6144 MBytes DDR3 RAM running Windows 7 operating system. Details on the corresponding implementations of TCA-1 and its variations (assuming Moore, Margolus and Weighted Margolus neighbourhoods) can be found in [18].
2) Sun Java 1.6.0.u26, executed on an AMD Athlon II x4 640 Processor at at 3 GHz and 3.6 GHz DDR3 RAM running OpenSUSE 11.4 (Linux Distribution) operating system. Details on the implementations of TCA-1 and its variation assuming a Moore neighbourhood can be found in [19]; we extended this work and implemented in Java variations of TCA-1using additional neighbouring schemes for the corresponding cellular automata.
3) Python version 2.7, executed on an AMD Athlon II x4 640 Processor at 3 GHz and 3.6 GHz DDR3 RAM running Ubuntu 12.04 (Linux Distribution) operating system. We have implemented in Python cellular automata for algorithms TCA-1 (and its variations) and TCA-2. Figures were plotted using the matplotlib. pyplot mathematical library (http://matplotlib.org/), which includes Matlab plot functions and can be manually imported to the python environment.
We have evaluated our algorithms using metrics commonly used in WSNs: 1) number of the active sensors in the network at each time step; increasing the number of active sensors improves network performance, 2) coverage and connectivity: coverage reflects the percentage of active sensors in the network and its value shows the degree to which the network is covered by active nodes; connectivity reflects the ability of the network nodes to communicate and increases as the number of active nodes in a neighbourhood increases and 3) global energy of the network; the sum of the remaining energy of the batteries of all alive (both active and idle) nodes: if the global energy is slowly reduced, the network lifetime is extended. The simulation results given in this section are obtained on a 50 × 50 WSN. Comparisons have also been made towards the case when all sensors are active until their energy is exhausted (i.e., when no topology control algorithm is used).
Figure 6 shows a comparison of Matlab, Java and Python implementations based on the simulation results of TCA-1 via a cellular automaton with a Moore neighbourhood. It can be seen that the use of a different programming environment does not affect performance of the WSN in terms of network lifetime (Figure 6(a)), connectivity (Figure 6(b)), coverage (Figure 6(c)) and global energy (Figure 6(d)).
However, the programming environment does affect 1) the size of the WSN used for simulation purposes 2) the visualization of simulation results and 3) how easy it is for a new researcher to use a programming environment in order to conduct simulations using cellular automata.
Matlab can efficiently support large network sizes (e.g., WSN of at least 250.000 sensors). However, it is rather inefficient for the development of GUI-based simulations and rather hard to learn for a researcher with only
basic programming knowledge. Java can efficiently support large enough network sizes (e.g., WSN of approximately 22.500 sensors) and, in addition, it can simplify the design and development of GUI-based simulations, demanding, however, a sophisticated (thus costly) computing system. Java is a programming environment quite easy to learn and should be preferred by researchers with basic programming skills. Python can be a good choice for simulating small WSN (e.g., WSN of at most 6.500 sensors) and a perfect choice for the development of user-friendly GUI-based simulations. Note that Python can be used for simulations involving very large WSN as well, but lacks efficiency when it comes to visualization. Python is an easy-to-learn and very flexible programming environment and certainly makes a perfect choice for researchers no matter how skilled they are in terms of programming.
4.1. TCA-1 Simulation Results
The following simulations have been implemented using the Python programming environment.
Figure 7 shows simulation results for algorithm TCA-1 via cellular automata with 1) a Margolus neighbourhood with at most 1 (l = 1) active sensors in each neighbourhood, 2) a Margolus neighbourhood with at most 2 (l = 2) active sensors in each neighbourhood) and 3) a Weighted Margolus neighbourhood.