Routing Protocol By Using Of Cellular Automata Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract: Network(ed) sensor systems are seen by observers as an important technology that will experience major deployment in the next few years for a plethora of applications, not the least being national security. Typical applications include, but are not limited to, data collection, monitoring, surveillance, and medical telemetry. In addition to sensing, one is often also interested in control and activation.

For this purpose in this paper, cellular automata is used for independent routing in all nodes. so that each node independently chooses a route for data transmission. In this paper for optimal routing, a table is specified in each node to record neighbor nodes` information, including time and energy, to choose the appropriate route and avoid creating circular and waste route. After simulation, it is determined that this method improves energy consumption and packet delivery ratio in comparison with directed diffusion protocol.

Keyword: Wireless Sensor Network, Cellular Automata, Routing Protocol


A sensor network is an infrastructure comprised of sensing (measuring), computing, and communication elements that gives an administrator the ability to instrument, observe, and react to events and phenomena in a specified environment. The administrator typically is a civil, governmental, commercial, or industrial entity. The environment can be the physical world, a biological system, or an information technology (IT) framework.

Sensor networks are wireless ad hoc networks used for monitoring and information gathering. They are used to observe natural phenomena such as seismological and weather conditions, collect data in battlefields, and monitor traffic in urban areas[1]. Sensor networks consist of many small, selforganized nodes that form an ad hoc network that reports to a common sink at the edge of the network. In a typical sensor network, the sink sends a query which is disseminated throughout the sensor network with flooding. The query requests a subset of nodes to send their collected information. The nodes, which have the requested information, send it to the sink by forming a tree with the root at the receiver. However, collection of information with a single sink may not be appropriate for sensor networks. For a single sink, the top level of the tree contains relatively few nodes, compared to the total number of nodes. So, most of the energy is consumed by the few nodes close to the sink. This makes the nodes closest to the sink prone to energy drainage. [2]

In this paper, a new routing method by using of cellular automata theory is proposed. In this way, each node collects neighbor`s specifications and points to suitable neighbor node to make optimum way that can send data through.

In order to increase the flexibility of the routing protocol, when any changes happened in the network, new path to sink is created fast

Cellular automata

A cellular automaton (CA) is a discrete computing model which provides a simple yet flexible platform for simulating complicated systems and performing complex computation. Generally, it is an idealization of physical systems in which both space and time are assumed to be discrete[17]. Each cellular automaton consists of two components: a set of cells and a set of rules. The problem space of a CA is divided into cells; each cell can be in one of some finite states. The CA rules define transitions between the states of these cells. At each discrete time step, the rules are applied to each CA generation repeatedly, causing the system to evolve with time. Note that based on how a cell and rules are defined, CA can be used to simulate a simple or very complex system.[14]

Cellular automata is a cellular network that each cell can have k state. In each cell, an automaton is put that has Finite State Automaton. In one-dimension state, each cell has two near neighbour. In this situation, cell i state in time t+i is achieved by equation (1):


Proposed Routing

In the proposed method, to create an optimum route on the network, one table is emplaced in each node. In this table the information on neighboring nodes are classified by Ping. With respect to the limitations in sources existing in the wireless sensor networks, having information on nodes and predicting future status tends to be an important issue to keep the network stable.

Figure 1: Cellular automata routing in sample network

As in cellular automata, each node makes decision according to the condition of the adjacent nodes, to record the information on nodes and to predict the condition, it would be enough if each node records in the table the information related to the neighboring nodes. This information is calculated based on the nodes' energy status in response to Ping, and also the time consumed for going and returning of Ping package. The algorithm of the nodes' operation is described in detail below.

Proposed Algorithm

The algorithm of route formation for receiving and sending information in wireless sensor networks by cellular automata:

1. The network has n node.

2. The variable A equals zero in all nodes except in sink. L and R are zero in all nodes.

3. All nodes sent the expression Interest.

4. If the variable A of a node receiving the expression Interest equals 1, the node returns its value of L along with the energy measure in percentage (E) as response.

5. Nodes which receive response, insert the node's specifications along with delay of receipt time(D) on the table.

6. The name of the first node in the list with L lower than that of the very node enters the variable R.

7. In case there is no node with L lower than L of the very node inside the list, a message is sent to the prior nodes to remove the node from the list.

8. Nodes compare their received L with that of themselves. If their L equals zero, they increase their L one unit higher than of that of received L.

9. In case there is at least one node in the table, the value of A in the node equals 1.

10. The node sends the Ping message to the neighbors, and puts the responding nodes in the neighboring table.

11. The node with one neighbor sends a message to its neighbor asking to be removed from the neighboring table and sending table.

12. The node with energy lower than 10% sends a message to its neighboring nodes asking to be removed from the neighboring list as well as the sending list.

13. In each node, a line with the length of y is created for locating sequence number.

14. Before sending to the next node, each package that receives a node, compares its sequence number with the line.

a) if it has no number, the package puts it on the line.

b) if there is a number on the sending table, the package removes the first node from the sending table.

15. In sending table, a new value called P is considered for nodes which are achieved by the equation 2.

P=a/D+b/L+cE (2)

a,b,and c are quotients to be obtained according to the conditions.

16. In the sending table, nodes are classified based on P ( the lowest P is put on the top).

17. The node sends Interest message to the first node in the sending table in each X second.

18. If there is no response, it goes to the next nodes, and puts the first responding node at the first of the node.

19. After formation of the route, information is sent by the sender.

20. After receiving information, each node sends one Ack message to the previous node.

21. Information is sent by the node whose name is on the variable R, and the nodes prepared for receiving Ack.

22. In case of not receiving Ack, the node lower than the current node at the variable R is selected and located in variable R.

Simulation and Conclusions

The proposed protocol is simulated by Delphi software, and its results are compared with those of direct dissemination protocol. As represented on diagram 1, the nodes total energy is improved in the proposed protocol. As far as the packet delivery issue is concerned, as diagram 2 illustrates, the average energy of the direct dissemination protocol has less increase at the start of simulation. After some specific time, however, the proposed protocol has less increases.

This study proposes a new protocol with the help of cellular automata method. It develops an optimum routing based on the information storage of the neighboring nodes in each node. The results of the simulation indicates that this protocol increases the rate of packages dissemination on wireless sensor networks compared with the direct dissemination protocol. Ignoring the initial period, the network has lower energy increase.

Figure 2 : Nodes total energy in proposed routing protocol compared with directed diffusion

Figure 3 : Packet delivery issue in proposed routing protocol compared with directed diffusion