Adaptive scheduling in wireless sensor networks based on Potts model

Recent advances in wireless sensor network's technology have developed using this technology in various fields. For the importance and intense application of these networks, many efforts and researchers have been done to confront challenges. In this paper, to conquer one of the most important challenges of these networks, that is the limitation in energy resources, an adaptive scheduling algorithm based in Potts model was applied. According to this model, for every element of a system, q different states are considered. Each element converts its state to a new state or remains in that state due to its current state and its adjacent neighbours and with the effect of environment. In this project, this model was used in wireless sensor networks such that each sensor node is considered as an element of sensor network system and three active, inactive and standby states are defined for that node, which it selects one of these three states according to its current state and neighbours and environment effect and adapts its activity with the environment in a way that the least energy to be consumed. By comparing this algorithm and similar algorithm (with two states), it is observed that in identical conditions, Potts model with three states represents better results and more lifetimes for network.


INTRODUCTION
Wireless Sensor Networks (WSNs) [1] consist of the limited resources constrained devices, called sensor node, which communicate wirelessly to each other. These nodes are able to recognize changes of states occur in their impact domain and to report processed obtained data to respective centres. This property causes usage of this technology various applications. One of them is to tracking a target which is used for different applications in benign environments and also harsh ones. As mentioned previously, these networks are composed of nodes with limited energy resources; therefore, one of the most important challenges of these networks is energy limitation and attempt to increase the operational lifetime of network.
To use effectively of sensor networks, requires resourceaware operation and takes care of resource as much as possible; this is because sensor nodes are distributed only once and resources of sensor nodes are hardly ever rechargeable. To decrease energy consumption of network, it is usually tried to reduce node's duty cycles, but in such applications of Sensor networks for event detection and tracking, it is impossible to use a fixed rule to decrease node's duty cycles because events of interest are often rare and unpredictable. So if operational cycles of nodes are reduced, when nodes are not active, an event may occur, which its incorrect detection and tracking led to serious consequences and irreparable losses. Many researches were done due to wireless sensor Networks challenges and energy saving of these Networks, particularly in application of target tracking and various algorithms has been designed. One of these algorithms is A-SAS algorithm [2].
According to this algorithm, node's activities are scheduled such that network nodes could be able to detect targets all the time and determine target's path correctly. The main goal of this paper is to develop the algorithm such that in addition to detect objective correctly, nodes to be scheduled in a way that to consume the least energy. In the proposed algorithm, Potts model was used to develop the algorithm. This paper is organized as following: in section II, Ising model and Potts model will be introduced. The proposed algorithm will be studied in section III. In section IV, after evaluating algorithm efficiency, the algorithm will be compared with Ising model with the same conditions, and in the last section, conclusions will be given.

II. INTRODUCING ISING MODEL AND POTTS MODEL
The Potts model studies long term behaviour of complex systems. The model is able to investigate how the internal elements of the system react with one another based on certain characteristics that each element has. As these reactions take place macroscopic properties of the system will evolve. The Potts model has proven to be a very useful tool for simulating real systems. This model is used in the area of mathematical modelling so called statistical mechanics. In this model, the system is mapped to a graph such that graph nodes are the composing elements of the system, and its edges are the connections between these elements. For many applications it is expedient to assume that the graph has a regular structure, such as a lattice. On the vertices of these graphs anything can be considered, like atom, human, liquids and cells and even sensor node. Potts model, models how the nearest elements with different spins are related with other elements in the lattice [3].
This model is the extended of Ising model. In Ising model, two states are considered for each vertex, but in Potts model, q different states can be considered for every vertex. one another depending on their position on the lattice and their specific spins, there will be some measure of overall energy of the system. The function which measures the overall energy of a complex is the Hamiltonian [4].
Where, J is the interaction energy between adjacent elements of the system, and R i R is the spin value assigned to vertex i in the state , and a 1 is placed on edges between neighbours with like spins and a 0 on edges with elements which have different spins. p

A. 4 B The Potts Model Partition Function
For a graph with n vertices which its vertex can have q different spins, there are qP n P states. In fact, Potts model studies these states. The Potts model probability function is the function which calculates the probability of finding the lattice in a particular state. This function is dependent on Boltzmann distribution in statistical mechanics. Equation 2 shows above function with exponential distribution. This equation computes the probability of finding a particular state =1/ kT, T represents the temperature of the system, and k = 1.38 × 10P -23 P "joules/Kelvin" is the Boltzmann constant. However computing the partition function is only tractable for small lattices and small values of q. In general, this function is NPhard to compute.
Mathematicians explore properties of the Potts model partition function in a variety of ways. One way is to interpret it as an evaluation of the Tutte polynomial [5]. Another is to approximate the function using a simulation technique such as the Metropolis Algorithm [6]. This calculation is not exact; however, it allows researchers to use the Potts model to investigate complex applications.

III. 2 B THE PROPOSED METHOD
The idea of using Potts model in wireless sensor networks was expressed in an algorithm called A-SAS [2]. This algorithm is a distributed algorithm for wireless sensor networks to be able to detect and track rare and random events. However, in this algorithm, Ising model was used, that is for sensor node, just two active and inactive states were considered.
The algorithm which is represented here is extended of A-SAS algorithm using Potts model. Therefore, instead of two states for nodes, three states are considered and the third state as standby is added. The sensor nodes are assumed to be equipped with relevant sensing transducers and data processing algorithms as needed for detection and tracking of events under consideration. Node's task is that until resources are available, they detect and track rare events. Problem assumptions: (1) the network only deployed once. (2) Sensor nodes are static. The neighbours are fixed and predetermined. (3) Sensor node connected to its nearest neighbours through a short single-hop wireless communication.
Sensor network is considered as a weighted graph. If G is the set of all nodes of the sensor network and E is the set of all edges of graph G which each edge specifies the distance between two nodes of S that are connected together with single-hop and is determined by an edge (sR i R, sR j R) E. Function W expresses the weight of the graph's edges and has the value W((sR i R, sR j R)) = wR ij R. The strength of interaction this function is dictated by factors such as physical distance between the sensor nodes.
To describe the problem, some definitions have to be stated: (1) Markov Random Field: suppose R i R}R si RR S R be the neighbour set for a node sR i R. Then, with respect to , a random field is called a Markov Random Field (MRF) if and only if hold the Markov properties (I.e. P(wR i R KR R) = P(wR i R KR S\{i RR } R)) [7]. where, K R S\{i} R and KR R are configurations specified for node set S\{i} and R i R, respectively; P is the probability of random field F. This condition of Markov property ensures that the probability of a node being in a state depends only on its neighbours. (2) a set of nodes, c, which is a subset of S or equal to S(c S) is called clique, If a graph which has been induced on c by G is complete (that is each two nodes in G have mutual neighborhood with each other) [8]. (3) The Hamiltonian or energy function for a configuration K is defined as:

A. 5 B Formulating Potts model for a sensor network
In this section, Potts model of a sensor network, which was introduced as a Markov random field on graph G, is formulated. The base of this formulation is that the behaviour of each sensor node is strongly dependent on its nearest neighbours would be relatively distance nodes do not influence the behaviour of the desired node. Sensor nodes introduce as binary random variables and the potential of each clique is determined. This potential is used for modelling the behaviour of nodes. The objective here is to 1 DELTA EQUAL TO: equal to by definition. achieve the desired activity of the sensor network with a distributed probabilistic approach as explained below. The State (or label) set is selected as active, inactive, standby}, to be a discrete set. Random field F is defined as: And the clique potentials are defined as: Where |c| is the basis for determining the potential; is the time -dependent value of the node s i dependent on time ; is as a defined function ; and is the expected value of j . It should be noted that V c ( i j ) V c ( j i ). In the Potts-model, corresponds to the external magnetic field and wR ij Rto the coupling constant [9] and has positive values. Cliques of size more than two would require to investigate of neighbours of neighbours, which become cumbersome for a large |c|. Therefore, from the implementation vision, cliques with size greater than 2 are not raised in the formulation and the potential value will be considered as zero. The Hamilton that shows the energy of the K configuration is now written in terms of the potentials VR c RR Ras: According to equation (4), for supposed configuration K, conditional probability P(wR i R KR S\{i} R) is expressed as: Where, CR i Ris the set of all cliques containing node sR i R; and KP ' P is a configuration of K in which node sR i R is labeled with wP ' P R i R. Assume that H ( R i R) be node sR i R energy changes with its state change from one state into another. For node sR i R, the probability of activeness via equation (8) is stated as: Obtained results show that the probability of being active , is a function of current state of node sR i R and expecting behavior of its neighbours. In the absence of magnetic-field indicating the external effect in the sense of a function of , the node probabilities is only dependent on its neighbours. Sensor network system would have a fixed point at PP * P = 0.5. The fixed point of the system determines when there is no event in the sensor field, system's operations properties to be usual and natural ( R i R=0 i). Therefore, in order to apply a sensor network, selection potential of P* has to be defined and 0< P*<1. Let clique potentials be defined as: Where, And be the change in expecting spin of the neighbor. For considered P*, Therefore, And according equations (11) and (12), it is obtained that: Due to these equations, for the moment that node sR i R senses an event around itself, According to the state of node sR i R and its neighbours, delta calculated, and it is placed in equation (9) to obtain the probability of being active. The formulation that presented here essentially follows a hybrid model [10] where the clique potentials and the probabilities are functions of two variables, a discrete variable ( R i R) and a continuous variable . To adapt the dynamic operational environment, sensor nodes recursively calculate their probabilities based on their interactions of neighbours and most recently sensed data.

B. 6 B Implementing the algorithm
To implement this algorithm, OPNET simulating software was used [11]. Sensor network is simulated with two-dimensional of sensor nodes (like [12] or [13]). Sensor network was formed with nodes 35 (7*5) that exposure in the uniform network. Each node has at most four neighbours which are orthogonally adjacent to each other and the distance between each two adjacent nodes is about 2.5 units. Note that with nearest orthogonal neighbors, cliques of order 3 or more are not present. the measurable value R i Ris taken to balanced (normalized) the signal intensity that detected by the sensor node sR i R." Fig. 1" illustrates this network. Each node of it is considered as a Markov random field with three states. " Fig. 2" represents a node of sensor network.  For each sensor node can be considered four different Modes: (1) active (Sensing and snaffing for messages from neighbors); (2) inactive (neither sensing nor receiving); (3) standby (neither sensing nor receiving, in fact this mode is a status of inactive mode that sensors work in low power but wake up with a speed about 5 to 10 microseconds [14]) and; (4) transition (sending new p a to neighbours).
Each pair of sensor nodes can Exchange the information only if any two nodes are in active state and communication mode. Activity of a sensor network is scheduling with a random update of node states, which is shown in " Fig. 3". In a discrete scheduling, node s i compute based on current in each time step, and identified neighbours probabilities and broadcasts them to neighbours (note that in each broadcasting, sending packet is sent to those neighbour nodes, which are in distance w from node s i ). Nodes broadcast new only when it changes with by . This is done so that insignificant changes in P a are not broadcasted. Then, a sensor node assigns a state active inactive or standby in this time step with aprobability of for active state and ½-½ for inactive and standby states to itself. The stochastic local decision is to adapt to environment. To change the state of nodes, each node acts as following; if is greater than ½-½ , node s i assigns active state to itself and otherwise, since the probabilities of inactive and standby states are the same, it generates a random number. If generated number is greater than P*, node goes into standby state, otherwise converts into inactive one. Suppose that the network of " Fig. 1" was embedded in a border region to track enemy infiltration and it wants to pass a path which is determined on the scheme. Sensor nodes detect considered target along the path and declare obtained results from their detection to data sink. In the proposed algorithm, neighbourhood interaction enables a sensor node to schedule its activity for an event occurring in its vicinity. To show the effects of neighbourhood interaction, the event is simulated to be detected by only one sensor node.With respect to " Fig. 1", in initial moments, the first the only node which detects the target is s 29 , this condition will be shown in p a computation by setting 29 =1 for s 29 and i =0 for all nodes Si that i . Other parameters P*, ,w and BR 1 Rare set 0.3, 0.2, 2.5 and 10, respectively. in this algorithm for change in the activity probability to broadcast pP a P to all neighbors, pP a P considered to be equal to 0.02. In " Fig. 3", TR act R, TR inact R, TR standby Rwhich are time durations of active, inactive and standby states, respectively, are taken values 1, 2 and 1 second, here. Also, the ratio of energy consumption in each state and node state conversion into active one are defined as: ER Inactive R<ER standby R<ER standby_to_active R< ER Inactive_to_active R<ER active Table I [ 15] is used for pattern of energy consumption of sensor nodes.

IV. 3 B EVALUATING ALGORITHM EFFICIENCY
To evaluate the above algorithm efficiency, both algorithms were simulated and the results were recorded. Table II shows network lifetime (in terms of second) in Potts and Ising models.  Figure 4. Comparing network lifetime of Potts and Ising models.
According obtained results, it is observed that Potts model has longer lifetime than Ising model, in the same conditions. However, in both algorithms, by increasing w, network lifetime decreases. This is for that increasing w is increase the radius of broadcast and more nodes are in active state that causes more energy consumption and consequently, network lifetime reduction. In presented Figure, the counts of active nodes were shown at each instant of simulation. " Fig. 5" indicate that in this algorithm, which was simulated by Potts model, the count of nodes in standby state in terms of time is more than active nodes, i.e., when no event is detected around nodes, instead of becoming inactive that in case of need to become active with consuming high energy, nodes become standby that consume low energy and in case of need to become active, they consume very low energy. Figure 6. 1 T Energy changes diagram for a node of the wireless network in Potts and Ising model.
1 0 B ACKNOWLEDGMENT In this paper, Potts model was utilized to increase wireless sensor network lifetime and to enhance objective tracking. Due to this model, three states are considered for each sensor node: active, inactive and standby. Each node is scheduled such that if a sensor node detects a target or becomes informed of passing a target by receiving a signal from its neighbours, it becomes active and informs other neighbours around itself of this event. Otherwise, if no event exists around the node, first it becomes standby and after passing some time, if no event occurs, it become inactive. The advantage of standby state is that when a node is in this state, not only it consumes less energy than active state, but also changes its state into active state much faster and with less energy than inactive state in case of an event occurrence. Therefore, it saves energy. In diagrams, it is observed that the number of standby states is more than of active states. But, with increasing w, that is by increasing the radius of sending packets, network lifetime decreases because of communication Increase in both models.