Game Theory Based Routing Protocol to Enhance the Lifetime of WSN

Game Theory Based Routing Protocol to Enhance the Lifetime of WSN

J. Padmini

PG Scholar, Department of ECE, SMVEC,

Puducherry, India

Abstract Wireless sensor network (WSN) requires robust and energy efficient routing protocols to minimize the energy consumption of the nodes as much as possible. The throughput of the network can be maximized by selecting efficient medium access control schemes. However the network lifetime is reduced due to noise and interferences. Fading can be minimized by adopting MIMO diversity techniques by which the diversity gain of the network is increased. To enhance the network lifetime, game theory based cooperative MIMO routing protocol is implemented for sensor networks which enables packet transmission from source to the sink, by allowing nodes to transmit and receive cooperatively.

Keywords: Cooperative MIMO, LEACH protocol, network lifetime, wireless sensor network.

1. INTRODUCTION

   A wireless sensor network (WSN) is a class of adhoc networks that consists of spatially distributed autonomous devices called nodes to monitor physical or environmental conditions such as temperature, sound, pressure, etc. and to cooperatively pass their data through the network to a main location. The sensor nodes are highly distributed networks of small, light weight wireless nodes deployed in large numbers.

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

   1. Characteristics and Constraints

      1. Dense node deployment

         Usually sensor nodes are deployed in a very dense field of interest. The number of sensor nodes in a sensor network will be of a higher magnitude than that in a MANET.

      2. Battery-powered sensor nodes

         Sensor nodes are usually battery powered. Mostly they are deployed in harsh environment where it is difficult to change or recharge the batteries.

      3. Self configurable

         Usually sensor nodes are randomly deployed without any careful planning. Once the sensor is deployed they should configure themselves to the communication network.

      4. Application specific

         Usually sensor nodes are designed for a specific application and hence the design requirements changes based on the application.

      5. Unreliable sensor nodes

         Usually sensor nodes are developed in harsh environments and operate without attendance. So they automatically get physical damages or failures.

      6. Frequent topology change

         Due to frequent node failure, damage, addition, energy depletion, or channel fading the network topology changes frequently.

      7. No Global identification

         Usually it is not possible to build a global addressing scheme for a sensor network due to the large number of sensor nodes, because it would introduce a high overhead for the identification.

   2. MIMO Systems

   MIMO systems can dramatically reduce the transmission energy consumption in wireless fading channels [2,3]. Cooperative transmission and reception of data among sensors is known to diminish the per-node energy consumption, increasing the network lifetime [4]. In these schemes, multiple individual single antenna nodes cooperate on data transmission and reception for energy efficient communication.

   Cooperative multi input single output (MISO) transmission scheme based on LEACH protocol performs only single hop transmission and does not prolong the network lifetime. To overcome these draw backs, the proposed model modifies the LEACH protocol [7,8] and allows cluster heads to form a multihop backbone and incorporates the cooperative MIMO scheme on each single hop transmission by utilizing a set of sending and receiving cooperative nodes in each cluster. For the proposed model, the energy consumed and the number of nodes alive for each round of data transmission is evaluated.

   The remainder of the paper is organized as follows: section 2 describes the proposed cooperative MIMO MAC scheme. The energy consumption model of proposed scheme is analyzed in section 3. Simulation results are discussed in section 4 and conclusions are drawn in section 5

2. COOPERATIVE MIMO MAC PROTOCOL

   Sensor network requires robust and efficient communication protocols to minimize delay and save energy. The throughput of WSN can be maximized by selecting an effective medium access control scheme depending on the contention level of the network. However, the lifetime of the network is reduced due to channel fading effects and interference. To enhance the network lifetime, a MIMO MAC scheme is proposed in this chapter for enabling packet transmission utilizing space time codes such as STBC by allowing nodes to transmit and receive information cooperatively [7, 14].

   1. Cluster- Based Cooperative MIMO Scheme

      In cooperative MIMO systems, transmit and receive diversity are achieved in a distributed manner by the sending and receiving groups. The cooperative MIMO system model is shown in Fig.2.1. It consists of cooperative sender having multiple sending nodes and receiver having multiple receiving nodes, each with a single antenna. In the sending group, the signals from multiple sending nodes are encoded by space time technique and transmitted to the receiving group. At the receiver, space time decoding is used to separate the received signals and extract the original information. At the beginning of each data transmission, the source node sends a Recruiting RTS (RRTS) message to its neighbours to solicit help for the transmission of data packet. The available neighbours will reply with a Sequential CTS (SCTS) message for the purpose of reducing collision with each other.

      Fig.2.1 Cooperative MIMO transmission model

      After recruiting the sending group, the source node sends a MIMO RTS (MRTS) control message to the destination node to establish data transmission link. The destination node recruits receiving group nodes using the same recruiting procedure as that of source node. After the destination node

      gets the SCTS reply, it sends broadcast messages to the

      message to destination node. The cooperative MIMO MAC transmission can be described by the following steps:

   2. Broadcasting

      The source node broadcasts data and synchronization information with low power to the selected neighbour nodes. The number of cooperative neighbours selected depends on the STC scheme. The source node also specifies the order for selected neighbour nodes so that each node will choose the corresponding row in space time code matrix for MIMO data transmission. Since the distance from the cooperative nodes to source node in the sending group is quite short the members of sending group need not send the acknowledgement back to the source node.

   3. STC MIMO transmission

      The cooperative nodes in sending group will use the corresponding row in STC code matrix, which is assigned in step1, to change the permutation of data bits. All nodes in the sending group, including the source node, will transmit space time coded data to the receiving group.

   4. Data collection and combining

   After receiving the data from sending group, each node in the receiving group uses CSI to decode the space time coded data. After decoding STC, the cooperative nodes in receiving group relay thei copies to the destination node. The destination receives signal copies from the cooperative nodes and detects them as soft symbols. The destination uses code combining and determines the most possible codeword based on the received soft symbols.

   If original data is decoded correctly, the destination node will send back an ACK message to the source node. Otherwise, no ACK is sent and the source nodes will timeout and initiate back off mechanism before attempting retransmission and the whole procedure is repeated.

3. ANALYSIS OF COOPERATIVE MAC PROTOCOL

   A mathematical model to evaluate the performance parameters such as, error probability, energy consumption and packet delay for the proposed cooperative MIMO MAC protocol is described below. The bit error probability is used to analyze the system energy consumption and delay incurred in the transmission of data from source to destination.

   1. Bit Error Probability

      The bit error performance of the cooperative MIMO system is evaluated taking into account that the system transmits QPSK signals through Rayleigh fading channel with additive white Gaussian noise. The relationship between the packet error probability pp and bit error probability pe for the

      selected receiving neighbours to recruit them and help in receiving MIMO data from the sending group. The destination

      frame length of L bits is given by

      e

      pp 1 (1 p )L

      (1)

      node then replies with a MIMO CTS (MCTS) message to source node to confirm the data transmission. If no MCTS is received, the source node times out and retransmits MRTS

      Data transmission errors are generated from two factors in cooperative MIMO i.e., from the sending to receiving group and from cooperative receiving nodes to destination. Thus the bit error performance for the transmission of data from

      transmit cooperative node to receive cooperative node and the performance for data collection at the destination is considered for analysis.

      rts

   2. Energy consumption analysis

      Tscoop Trts TBr Tcts TBs Tdata Tcol Tack

      and the duration for an unsuccessful attempt is

      (5)

      Consider a scenario with nT senders and nR receivers

      Tucoop T

      • TBr Tcts TBs Tdata Tcol Twait

      (6)

      involved in cooperative MIMO transmission. The energy consumed for an unsuccessful transmission attempt and for a successful transmission from sending to the receiving group using STBC and STTC MIMO MAC are calculated to analyse the overall energy consumption in a hop. The energy consumption for an unsuccessful transmission attempt is

      Eucoop Emrts Emcts 2Errts (n -1)Escts

      where

      Trts is the transmission time for the RTS

      TBr is the transmission time of a recruitment message sent by the destination node

      Tcts is the transmission time for the CTS

      TBs is the transmission time required for the source node to send the data packet to its cooperating nodes

      T

      R R

      (n 1)Escts Ebs Edata (n 1)Ecol

      and the energy consumption for a successful attempt is

      (2)

      Tdata is the transmission time for the data

      Tcol is the time required by the cooperating receiving nodes to send the data to the destination

      Tack is the transmission time for the ACK

      T R

      Escoop Emrts Emcts 2Errts (n

      1)Escts (n

      1)Escts

      (3)

      Twait is the duration for which sender waits for an ACK

      The total expected packet delay for cooperative MIMO MAC

      R

      Ebs Edata (n 1)Ecol Eack

      is given by

      Where Emrts is the energy consumed in sending MIMO RTS

      pp Tu

      d

      Ts

      (7)

      Emcts

      is the energy consumed in sending MIMO CTS

      (1 pp )

      coop coop

      Errts is the energy consumed in sending RRTS Escts is the energy consumed in sending SCTS

      Ebs is the energy spent by the source node to send the data.

      Edata is the energy consumption for data transmission between sending and receiving group

      Ecol is the energy consumed by destination or sink node to collect the data from cooperative receiving group

      Eack is the energy consumed in sending ACK

      The MRTS and MCTS messages are control messages between source and destination and they require higher transmission power for long distance transmission. The RRTS and SCTS are control messages between source/destination and their neighbours. Compared to the MIMO RTS and CTS, RRTS and SCTS messages are transmitted with less power due to shorter distance of transmission. In the receiving group, each node will transmit its signal back to the destination with energy Ecol and there are (nR 1) cooperative nodes in the receiving group, excluding the destination node.

      The total energy consumption for one-hop transmission in cooperative MIMO system is given by

4. GAME THEORY

   Game theory [8, 9] provides a formal analytical framework with a set of mathematical tools to study the complex interactions among rational players. Throughout the past decades, game theory has made revolutionary impact on a large number of disciplines ranging from engineering, economics, political science, philosophy, or even psychology. In recent years, there has been a significant growth in research activities that use game theory for analyzing communication networks. This is mainly due to:

   1. The need for developing autonomous, distributed, and flexible mobile networks where the network devices can make independent and rational strategic decisions and

   2. The need for low complexity distributed algorithms that can efficiently represent competitive or collaborative scenarios between network entities.

      In general, game theory can be divided into two branches:

      EM

      pp

      (1 pp )

      Eucoop

      • Es

      coop

      (4)

      1. Non-cooperative game theory and

      2. Cooperative game theory.

         Non-cooperative game theory studies the strategic

   1. Packet transmission delay

   Each packet transmission in cooperative MIMO requires more steps which may increase the packet delays. However, the reduction in the packet error probability with cooperative MIMO MAC reduces the occurrence of retransmissions which in turn reduces the packet delays. The duration of transmission attempt that is successful using cooperative MIMO transmission is given by

   choices resulting from the interactions among competing players, where each player chooses its strategy independently for improving its own performance (utility) or reducing its losses (costs). For solving non-cooperative games, several concepts exist such as the celebrated Nash equilibrium. The mainstream of existing research in communication networks focused on using non-cooperative games in various applications such as distributed resource allocation, congestion control, power control and spectrum sharing in cognitive radio, among others. This need for non-cooperative games led

   to numerous tutorials and books outlining its concepts and usage in communication.

   While non-cooperative game theory studies competitive scenarios, cooperative game theory provides analytical tools to study the behavior of rational players when they cooperate. The main branch of cooperative games describes the formation of cooperating groups of players, referred to as coalitions that can strengthen the players position in a game. Coalitional games have also been widely explored in different disciplines such as economics or political science.

   Recently, cooperation has emerged as a new networking paradigm that has a dramatic effect of improving the performance from the physical layer to the networking layers. However, implementing cooperation in large scale communication networks faces several challenges such as adequate modeling, efficiency, complexity, and fairness, among others. Coalitional games proveto be a very powerful tool for designing fair, robust, practical, and efficient cooperation strategies in communication networks.

   Most of the current research in the field is restricted to applying standard coalitional game models and techniques to study very limited aspects of cooperation in networks. This is mainly due to the scarcity of the literature that tackles coalitional games. In fact, most pioneering game theoretical references focuses on non-cooperative games.

5. LEACH PROTOCOL

   Low energy adaptive clustering hierarchy uses the clustering principle to distribute the energy consumption all along its network. Here, based on data collection, network is divided into Clusters and Cluster heads are elected randomly. The cluster head collects the information from the nodes which are coming under its cluster. Let us see the steps involved in each round in the LEACH protocol.

   1. Advertisement phase: This is the first step in LEACH protocol. The eligible cluster head nodes will be issuing a notification to the nodes coming under its range to become a cluster member in its cluster. The nodes will be accepting the offer based upon the Received Signal Strength (RSS).

   2. Cluster set-up phase: In this step the nodes will be responding to their selected cluster heads.

   3. Schedule creation: After receiving response from the nodes the cluster head have to make a TDMA scheme and send back to its cluster members to intimate them when they have to pass their information to it.

   4. Data transmission: The data collected by the individual sensors will be given to the cluster head during its time interval and on all other time the cluster members radio will be off to reduce it energy consumption.

      Here in the LEACH protocol multi cluster interference problem was solved by using unique CDMA codes for each cluster.

      It helps to prevent energy drain for the same sensor nodes which has been elected as the cluster leader, using randomization for each time cluster head would be changed.

      The cluster head is responsible for collecting data from its cluster members and fuse it. Finally each cluster head will be forwarding the fused data to the base station.

      In short LEACH operation is classified into rounds each of which has mainly two phases namely,

      Fig.5.1 LEACH clustering hierarchical model

      1. Setup phase

         • For organizing the network into clusters

         • Advertisements of the cluster heads

         • Transmission schedule creation

      2. Steady state phase involves

   • Data aggregation

   • Compression

   • Transmission to the sink

     In order to achieve the design goal the key tasks performed by LEACH are as follows:

   • Randomized rotation of the cluster heads and the corresponding clusters

   • Global communication reduction by the local compression Localized co-ordination and control for cluster setup and operation

   • Low energy media access control

   • Application specific data processing.

6. PERFORMANCE ANALYSIS

   In this project Matlab version 7.8.0.347(R2009a) is used as the simulation tool to execute the mathematical model of the energy efficient protocols in WSN. To obtain more accurate results, all experiments were performed 50 times to compute the average results.

   PARAMETERS	VALUES
   Number of sensors nodes deployed	100
   Network size	(100×100)m2
   Initial Energy	0.5J
   Energy for Transmitting the data (Etx)	50nJ/bit
   Energy for Receiving the data (Erx)	50nJ/bit
   Sink Position	(50,150)
   Free space propagation model ( fs )	10pJ/bit/m2
   Two ray ground propagation model ( tr )	0.0013pJ/bit/m4
   Energy for Data Aggregation ( EDA )	5nJ/bit/signal
   Control packet length	200 bits
   Packet length	6400 bits

   A. Simulation parameters

   NO.OF ROUNDS VS RESIDUAL ENERGY

   0.6

   leach

   leach with game

   0.5

   Residual Energy(In joules)

   0.4

   0.3

   0.2

   0.1

   0

   -0.1

   0 200 400 600 800 1000 1200 1400 1600

   Number of Rounds

   Fig 6.1 Number of rounds Vs residual energy

   NO OF ROUNDS VS ALIVE NODES

   100

   leach

   90 leach with game

   80

   70

   Dead nodes

   60

   50

   40

   30

   20

   10

   0

   0 200 400 600 800 1000 1200 1400 1600

   Number of Rounds

   Fig 6.2 Number of rounds Vs Dead nodes

7. CONCLUSION AND FUTURE SCOPE

   In this paper, improved results were obtained when co- operative game theory on energy calculation for successful transmission was implemented on this protocol. Simulation results provide 45-50 % increase in the lifetime of the network on comparison with LEACH and validate the effectiveness and efficiency of the approach, indicating that game theory is a promising method for prolonging the lifetime of homogeneous WSNs.

   Wireless Sensor Network is a growing technology. Cooperative MIMO technology is also widely used in many applications. This technology can be implemented in LEACH protocol and furthermore better results can be obtained. This work can further be extended to heterogeneous networks.

8. REFERENCES

1. G. Nallasivan, S. Lalitha, Distributed cooperative cluster based communication protocol for Energy efficiency in wireless sensor networks, International journal of computer science and engineering (IJCSE), Issn 2278-9960 Vol. 2, issue 2, May 2013.

2. Hsin-Yi-Shen, Haiming Yang and Shivkumar Kalyanaraman. Energy efficient cooperative MIMO systems, In Proceedings of IEEE Infocom. Phoenix, USA, 2008.

3. Nandakishor Sirdeshpande, Vishwanath Udupi, Lifetime Maximization Using Modified Leach Protocol for Energy Efficient Routing In Wireless Sensor Networks, International Journal Of Engineering And Science (IJES), Vol.2, Issue 2, 2013.

4. Prabhat Kumar, M.P.Singh and U.S.Triar, A Review of Routing Protocols in Wireless Sensor Network, International Journal of Engineering Research & Technology (IJERT) Vol. 1 Issue 4, ISSN: 2278-0181, June 2012

5. Xue Wang, Liang Ding, and Sheng Wang, 'Trust Evaluation Sensing for Wireless Sensor Networks," IEEE Transactions on Instrumentation and Measurement, vol. 60, no. 6, June 2011

6. Kiran Maraiya, Kamal Kant and Nitin Gupta, Efficient cluster head selection scheme for data aggregation in wireless sensor networks, International Journal of Computer Applications, Volume 23 No.9,

   June 2011

7. J. Vidhya and P. Dananjayan, Lifetime Maximization of Multihop WSN using Cluster-based Cooperative MIMO Scheme, International Journal of Computer Theory and Engineering, Vol. 2, No. 1 February, 2010

8. Saad, W.; Zhu, H.; Debbah, M.; Hjorungnes, A.; Basar, T. Coalitional game theory for communication networks: A tutorial, IEEE Sign. Process. Mag. 2009, 26, 7797.

9. Fatemeh Kazemeyni, Einar Broch Johnsen, Olaf Owe and Ilangko Balasingham, Group selection by nodes in wireless sensor networks using coalitional game theory, International Journal of Computer Science & Engineering Survey (IJCSES), June 2010.

10. K. Ramesh and Dr. K.Somasundaram, A comparative study of cluster head selection algorithms in wireless sensor networks, International Journal of Computer Science & Engineering Survey (IJCSES) Vol.2, No.4, November 2011.

11. p>Curt Schurgers and Mani B. Srivastava, Energy efficient routing in wireless sensor networks, International Journal of Computer Applications, May 2010.

12. H. Gou and Y. Yoo, An Energy Balancing LEACH Algorithm for Wireless Sensor Networks Proc. International Conference. Information Technology, pp. 822-827, 2010.

13. Yongming Qin, Qiuling Tang, Ye Liang, Xiuyu Yue, Xian Li, An Energy-Efficient Cooperative MIMO Scheme for Wireless Sensor Networks Based on Clustering 14th IEEE Conference on Computational Science and Engineering (CSE) pp. 471-474, 2011.

14. J.Vidhya and P.Dananjayan, Energy Efficient STBC Encoded Cooperative MIMO Routing Scheme for Cluster Based Wireless Sensor Networks, International Journal of Communication Networks and Information Security (IJCNIS) Vol. 2, No. 3, Dec 2010.

15. Nazia Majadi, U-LEACH: A Routing Protocol for Prolonging Lifetime of Wireless Sensor Networks, International Journal for

    Research and Application, Vol. 2, Issue4, July-August 2012, pp.1649- 1652

16. Shuang Li, Raghu Kishore, Cong Liu and Alvin Lim,Efficient multi-path protocol for wireless sensor networks, International Journal of Wireless and Mobile Networks, Vol.2, No.1, pp109- 131. 2010.

17. G. N. Bravos and G. Efthymoglou, MIMO-based and SISO multihop sensor network: Energy efficiency evaluation, Proceedings of IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, 2007.

18. Yang. H, Shen. H.Y. and Sikdar. B. A MAC protocol for cooperative MIMO transmissions in sensor networks. In Proceedings of IEEE Global Communications Conference, Exhibition and Industry Forum, Washington, USA, pp636- 640.2007.