Cooperative game theory based routing protocol to enhance biology essay

ABSTRACT

Wireless Sensor Network (WSN) plays a major role in collecting physical data from various locations using battery powered sensor nodes and forward it to the sink node. Limited energy resource is the major constraint associated with WSN, since in most cases it may not be possible to change or recharge batteries. For successful communication, the lifetime of sensor nodes or motes plays the important role. Hence designing of energy efficient routing algorithm is one of the key challenges that need to be addressed for extending the life time of the network. In this paper, cooperative game theoretic approach is applied in A Novel Clustering Algorithm for Energy Efficiency algorithm (G-ANCAEE) and low energy adaptive clustering hierarchy (G-LEACH). The G-ANCAEE achieves good performance in terms of minimizing energy consumption during data transmission and enhances the life time of the nodes. The G-ANCAEE involves fixed clusters and randomized weighted algorithm for cluster head selection which efficiently reduces the energy consumption. Cooperative game theory is used to select healthier cluster-heads having sufficient residual energy with high trust level. Simulation results of the G-ANCAEE shows that the energy expended in the network can be reduced as the number of frames per round is increased compared to G-LEACH protocol. Keywords: WSN, energy consumption, cooperative game, G-LEACH, G-ANCAEE

INTRODUCTION

Wireless Sensor Network (WSN) is a network which consists of a large number of tiny spatially distributed radio-equipped sensors called nodes. The sensor node not only senses but also processes to make it into a meaningful data using its embedded microprocessors and communicates through the receiver. Nodes are used for gathering information needed by smart environments and are particularly useful in unattended situations where terrain, climate and other environmental constraints may hinder in the deployment of wired/conventional networks [1].

Fig. 1 Sensor Network Architecture

An individual node failure is not an issue because of the large scale deployment of these nodes and normally the target area is monitored by several nodes. Primarily these sensors are used for data acquisition and are required to disseminate the acquired parameters to special nodes called sinks or base-stations over the wireless link as shown in Fig 1. The base-station or sink collects data from all the nodes, and then analyzes this data to draw conclusions about the on-going activity in the area of interest.

Related Work

The important aspect of WSN is that nodes are often unattended after deployment and their energy cannot be replenished. Traditional routing protocols used in wired and existing wireless schemes may not be applicable to WSN due to limited energy and bandwidth of wireless links connecting the sensor nodes. The routing protocol must meet the design targets of being power efficient and reliable. LEACH is the first cluster based routing protocol for WSNs, which uses a stochastic model for cluster head selection. LEACH has motivated the design of several other protocols which try to optimize energy consumption in different ways, [1]. The operation of LEACH protocol is divided into rounds. Each round consists of set-up phase and steady- state phase. During the set-up phase, sensor nodes are organized into different clusters based on the received signal strength and cluster heads are selected for each cluster as routers to the base station. This algorithm saves energy, since only CHs are allowed to transmit data to the base station rather than all nodes. It allows CHs to rotate randomly to balance energy consumption of nodes in the networks. Basically, each node elects itself to be a CH in a given round. LEACH achieves reduction in energy consumption seven times compared with direct communication and between 4 to 8 times compared with minimum transmission energy (MTE) routing protocol [5]. Despite these benefits, LEACH suffers several shortcomings. CHs are not uniformly distributed in LEACH, CHs may be chosen from one part of the network. If this occurs, energy dissipation will be more than conventional protocols [6]. The operation of LEACH can be separated into two phases: the setup phase and the steady state phase. In the setup phase, the clusters are organized and cluster heads are selected. In the steady state phase, the actual data transfer to the base station takes place. In short the former is for clustering and the latter is for data transmission. The system repeats the clustering and transmission in every round. The duration of the steady state phase is longer than the duration of the setup phase. By this method overheads can be minimized. During the setup phase, the CHs are selected based on an elective percentage of deployed nodes also by considering a factor that so far how many times an individual node performed the role of cluster head. A predetermined fraction of nodes, p, elect themselves as cluster heads as follows. A sensor node chooses a random number, between 0 and 1. If this random number is less than a threshold value, T(n), then the node becomes a cluster head for the current round. The threshold value is calculated based on an equation that incorporates the desired percentage to become a cluster head, the current round, and the set of nodes not selected as a cluster head in the last (1/ p) rounds, denoted by G. After the cluster heads have been elected, they broadcast an advertisement message to the rest of the nodes in the network that they are the new cluster heads. Upon receiving this advertisement, all the non cluster head nodes, decide the cluster to which it should belong, based on the signal strength of the advertisement it receives from the cluster-heads. The non cluster head nodes inform the appropriate cluster heads that they will be members of that cluster. After receiving all the messages from the nodes that would like to be included in the cluster and based on the number of nodes in the cluster, the cluster head node creates a TDMA schedule and assigns each node a time slot deciding when it can transmit. This schedule is broadcast to all the nodes in the cluster. When the network diameter is increased beyond certain level, distance between cluster-head and base station is increased enormously. This scenario is not suitable for LEACH routing protocol in which base station is at single-hop to cluster-head. In this case energy dissipation of cluster-head is not affordable. To address this problem Multi-hop LEACH (M-LEACH) is proposed with the extension of LEACH routing protocol to increase energy efficiency of the wireless sensor network.

SYSTEM MODEL

A Novel Clustering Algorithm for Energy Efficiency in Wireless Sensor Networks (ANCAEE) has been applied to achieve good performance in terms of minimizing energy consumption during data transmission and energy consumptions are distributed uniformly among all nodes. ANCAEE uses a new method of clusters formation and election of cluster heads. The algorithm ensures that a node transmits its data to the CH with one hop transmission and cluster heads forward their data to the base station with multi hops. It involves grouping of sensor nodes together, so that nodes communicate their sensed data to the CH. CHs collect, aggregate and transmit the aggregated data to the processing centre called base station for further analysis. Clustering provides resource utilization and minimizes energy consumption in WSNs which is done by reducing the number of sensor nodes taking part in long distance communication.

2. 1 Cluster Heads Selection

In order for a node to become cluster head in a cluster the following assumptions were made. All nodes should have equal initial energy. There are s nodes in the sensor field. The number of clusters is k. Based on the above assumptions, the average number of sensor nodes in each cluster is m which is given in equation(1)After m rounds, each of the nodes must have been a cluster head (CH) once. each node have unique identifier i, for all 0, 1, 2, 3, 4,…s-1. Variable i is used to test whether it is the turn of a node to become a CH. Originally, all nodes are the same, i. e. there is no CHs in each cluster, j = 0 where j is CHs counter. A node q is selected among all nodes and continuously executes the following steps: Firstly, q increments i by 1 and check if i is even, if yes that node is selected as the CH for that round and announces its new position to all member nodes in the cluster. Else if i is odd, it cannot be a CH for that round, it will wait for the next round and be ready to receive advertisement message from the new CH. A predetermined value is set (threshold value) for the new CH to transmit for that round. When the value has reached, j will be incremented by 1 and the process of selection of new CH begins. It tests if the following two conditions hold. That a sensor node has not become cluster head for the past (1/p) rounds . That the residual energy of a node is more than the average energy of all the sensor nodes in the clustering. Thus, the probability Pi of a node becoming a new cluster head is(2)where, eres is the remaining energy in node (i), eavg is the average energy of all the nodes in a cluster which is given(3)Where eavg-Average energy in a cluster and Ni. eres-Residual energy of node i in a cluster. The procedure continues until j = k. The algorithm stops when j = k. The new CHs collect sensed data from member nodes, aggregate them, and transmit the compressed data to the next cluster head or base station.

2. 2 Cluster formation

The next step in the clustering phase is cluster formation after CHs have been elected. The description of new cluster formation is as followsStep 1: The new cluster heads elected above broadcast advertisements (ADV) message to all non-cluster nodes in the network using Carrier Sense Multiple Access (CSMA) MAC Protocol. Step 2: Each sensor node determines which clusters it will join, by choosing CH that requires minimum communication energy. Step 3: Each non-cluster node uses CSMA to send message back to the CHs informing them about the cluster it wants to belong. Step 4: After CHs have received messages from all nodes, Time Division Multiple Access (TDMA) scheduling table will be created and send it to all nodes. This message contains time allocated to each node to transmit to the CH within each cluster. Step 5: Each sensor node uses TDMA allocated to it to transmit data to the CH with a single- hop transmission and switch off its transceiver whenever the distance between the node and CH is more than one hop to conserve energy. To avoid a single node transmitting data multiple times in one round, we set a threshold value G. G is the total time of all nodes in the cluster forwarding their data to the CH in one round. Step 6: CHs will issue new TDMA slots to all nodes in their clusters when allocated time for G has elapsed, for each node to know exact time it will transmit data to avoid data collision during transmission that can increase energy consumption. Step 7: CH transceiver is always turn-on to receive data from each node in its cluster and prepare them for inter-clusters transmission. Inter-cluster transmission is of two types: single hop and multi-hop. We adopted multi-hop transmission in order to save more energy during inter-cluster transmission.

2. 3 Energy Consumption

Basically, the energy required for transmitting a signal is highly related to the distance. The following equation shows the energy consumed when sending a signal to a distance d by an amplifier. Energy Consumption = (4)Using d0 as a threshold, if the transmission distance is shorter than d, a free-space propagation model is used to calculate the consumed energy, which is proportional to the square of distance. If transmission distance is longer than calculation and the consumed energy is proportional to the fourth power of distance. In that case, the consumed energy has a great influence on the wireless communication system. In the above equation, fs and tr are the parameters for the free-space propagation model and two ray ground propagation model. Here, d0 is defined as which is the threshold of transmission distance and its value is about 87. 7. The energy for data aggregation at the cluster head is given as eDA. On implementation with the number of bits transferred the equation (4) becomes to transmit an l-bit message to a distance d0(5)and to receive this message, the radio expends the energy(6)Where the electronics energy, eelec depends on factors such as the digital coding, modulation, filtering, and spreading of the signal, where as the amplifier energy, fs d2 or tr d4, depends on the distance to the receiver and the acceptable bit-error rate. With n nodes distributed uniformly and k clusters, there are on an average n/k nodes per cluster (one cluster and (n/k)-1 non-cluster head nodes (i. e) normal nodes). Each cluster head dissipates energy receiving signals from the nodes, aggregating the signals, and transmitting the aggregate signal to the sink node. Since the sink node is far from the nodes, presumably the energy dissipation follows the multipath model(power loss). Therefore, the energy dissipated in the cluster head node during a single frame is(7)where l is the number of bits in each data message, dto sink is the distance from the cluster head node to the BS, it is assumed that it has perfect data aggregation. Each non-cluster head node only needs to transmit its data to the cluster head once during a frame. Presumably the distance to the cluster head is small, so the energy dissipation follows the Friss free-space model (d2 power loss). Thus, the energy used in each non-cluster head node is calculated(8)where dto CH is the distance from the node to the cluster head

GAME FORMULATION

Game theory (GT) is a mathematical model that describes the phenomenon of conflict and cooperation between intelligent rational decision-makers. In particular, the theory has been proven very useful in the design of wireless sensor networks (WSNs). Furthermore it also helps to predict the possible outcomes of the interactive decision problem. A game is defined by a set of players, a set of actions for each player, and the payoffs for the players. A player chooses an action and the complete plan of action is referred to as the strategy. When the action is chosen deterministically, it is called a pure strategy. Cooperative games consider the set of joint actions that any group of players can take. The outcome of a cooperative game will be specified by which group of player’s forms, and the joint action that that group takes. On application of the co-operative game theory concept to the existing protocol like LEACH, we obtained a better result, the similar better result is obtained by implementing it in EECP. This would result in further lifetime enhancement. Here a pre-defined threshold value for each node is calculated, which helps in estimating the successful transmission. In addition to the weight calculation, a utility value is also calculated. The calculated value, if greater than the threshold, is titled as a ‘ successful transmitting node’ and given the strategy as one (i. e) a win situation. Else it is given the strategy of zero (i. e) a lose situation. With the strategy as one, the node forwards data else it remains idle and the process looks for another successful transmitting node. With strategy ‘ one’, the utility value is more, showing that it has more chances in becoming cluster-heads in the next rounds . Since it specifically chooses the efficient cluster-head in transmission, the time taken for choosing the cluster-head is reduced and hence the unwanted checking of the ineffective cluster-head is not made, which reduces the overhead.

Pseudo code

Assign old= present energy value of CH1. Select the nearby clusterheadif(the selected CH2 has more energy comparatively)Calculate the energy consumed by CH1 for hopping to CH2. Calculate the energy consumed by CH2 for reception of that data. if(the CH2 has still more energy to forward the data to sink node)CH2 is elected for hopping purpose.

else

CH1 finds other CH2 or straightly forward the data to sink node.

endif

endif

RESULTS AND DISCUSSION

MATLAB 10. 0 is used to validate the proposed game. The parameters considered for simulation is summarised in Table 1. The performance of proposed game based routing protocol was evaluated in terms of alive nodes and residual energy in the network.

Table: 1 Simulation Parameters

PARAMETERS

VALUES

Number of sensors nodes deployed100Network size(100×100)m2Initial Energy0. 5JEnergy for Transmitting the data (etx)50nJ/bitEnergy for Receiving the data (erx)50nJ/bitSink Position(50, 150)Free space propagation model ()10pJ/bit/m2Two ray ground propagation model ()0. 0013pJ/bit/m4Energy for Data Aggregation eda5nJ/bit/signalControl packet length200 bitsPacket length6400 bits

4. 1 Deployment of Nodes

Figure 4. 1 depicts the deployment of the nodes. It can be seen from the figure that the network area of 100 × 100 is divided into sectors. The nodes deployed in each sector to form a cluster. These clusters remain constant throughout the network lifetime. The nodes indicated with red-color (star) show the cluster-head for the corresponding cluster for a round. The node which has the maximum weight is chosen as the cluster-head for a round. The cluster-head changes in each round based on the calculated weight.

Figure 4. 1 Deployments of Nodes

4. 2 Analysis of Alive Nodes among Protocols

Figure 4. 2 shows the comparison of the alive nodes of three protocols (LEACH, ANCAEE, EECP). Lifetime is defined as the total period for the network to be alive to perform successful transmission. LEACH which is the basic protocol has its total death of nodes around 800-1000 rounds and ANCAEE which has energy efficient CH election has a little longer period for its total node death and it is around 1050-1300 rounds. EECP performs better than former two and it has its total node death around 1600. This is because the election of CHs based on its weight, which is allocated with respect to its residual energy, its distance from sink and other nodes and average energy prevailing in the respective clusters. With these criteria into consideration, there is distributed energy utilization. This leads to increased lifetime.

Figure 4. 2 Alive nodes Vs number of rounds

4. 3 Analysis of Residual Energy among Protocols

The residual energy analysis of LEACH, ANCAEE and EECP is shown in Figure 4. 3. Residual energy is the left over energy in a node after its successful transmission and reception. The average residual energy for the network is 0. 5. The residual energy is approximately 37. 8% more in ANCAEE compared with LEACH when the analysis at the round 750. This is because by effective choosing of the CHs there is even distribution of energy in the network. It is found that residual energy is 34. 82 % and 59. 5 % more in EECP when compared with ANCAEE and LEACH respectively.

Figure 4. 3 Average Residual Energy Vs number of rounds

4. 4 Analysis of Alive nodes among protocols with game

The comparison of the three protocols (LEACH, ANCAEE and EECP) along with its Co-operative game theory is shown in Figure 4. 4. Game theory is a paradigm which is used to elect healthier CHs having sufficient residual energy and high trust level during the selection of cluster-head and transmission. Co-operative game theory refers to the concept that each node is known of the other node’s energy before its transmission. It is seen that on application of co-operative game theory to each protocol there is 20% – 40% increment in Lifetime (number of rounds). Hence, EECP which is an efficient protocol shows 65% – 70% increment when compared with the basic LEACH protocol.

Figure 4. 4 Alive nodes Vs Lifetime (in rounds)

4. 5 Analysis of Residual energy among protocols with Game

Figure 4. 5 shows the residual energy analysis of LEACH, ANCAEE and EECP along with its co-operative game theory. The game theory based protocols show better results than its origin protocols. It can be seen that the LEACH with game has 15% – 20% more residual energy than LEACH at 500 rounds. The residual energy is approximately 17% more in the EECP with game when compared with its origin protocol, EECP. On comparison with ANCAEE and ANCAEE with game, it has 20%-30% more residual energy. And when compared with LEACH and LEACH with game, it outperforms by 35%-40%. Hence EECP with game is more efficient in energy compared to other protocols under comparison.

Figure 4. 5 Average residual energy Vs number of rounds

4. 6 Comparison of the protocols in terms of node deaths

Figure 4. 6 gives a vivid illustration of the first node and last node death of the protocols viz.. LEACH, LEACH with game, ANCAEE, ANCAEE with game, EECP and EECP with game. The first node death (FND) occurs around 400-500 rounds in the older protocols whereas in EECP it occurs around 200-300 itself because there occurs repeated cluster-head election amongst the nodes near the sink in the beginning and losses its energy, resulting in its quick death. And it clearly shows that 100% of the node death (i. e) last node death (LND) occurs at 1700 rounds for EECP with game, where as it is at 900, 1100, 1250, 1390, 1450 for LEACH, LEACH with game, ANCAEE , ANCAEE with game, EECP. Graph5. jpg

Figure 4. 6 First and Last Node Death

It is estimated that the EECP with game performs better than LEACH by 47%. This is due to the reduction of unwanted energy usage for forming the Clusters and the avoidance of over utilization of a particular node during CH selection. Graph6. jpg

Figure 4. 7 Percentile of Node death

Figure 4. 7 gives a clear note on the death of 10% of the nodes and 90% of nodes in all protocols. There is a gradual death of the nodes in EECP and EECP with game. It is seen that there is sudden death of nodes for LEACH, ANCAEE and its derivatives where the CH election is random irrespective of its residual energy. Hence EECP and EECP with game’s efficiency are more comparatively.

CONCLUSION

In this paper, a new objective for maximizing the network lifetime using EECP algorithm is presented. This algorithm partitions the network area into different clusters and elects a node as the cluster head for each cluster. Each node within the cluster sends its data to the cluster head with single hop transmission and cluster heads receives, aggregates the data and transmits it to the base station via multi-hop transmission. Here the clusters are fixed; hence the energy required for forming clusters in each round is negligible. The approach searches for the best cluster-head, based on its weight allocation formulated with energy and distance. Further improved results were obtained when co-operative game theory on energy calculation for successful transmission was implemented on this protocol. Simulation results which provide 45-50 % increase in the lifetime of the network on comparison with protocols like LEACH, ANCAEE validates the effectiveness and efficiency of the approach, indicating that EECP and EECP with game are promising methods for prolonging the lifetime of homogeneous WSNs.