Subscribe Now Subscribe Today
Research Article

EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks

B. Baranidharan and B. Santhi
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

Energy efficient transferring of packets is a major issue in resource constrained wireless sensor networks. Clustering techniques used for energy efficient data collection works better than the direct transmission in number of cases. Since cluster heads nodes in these schemes are having more responsibilities than the other normal nodes its energy depletes faster than the normal node which affects the stability of the network. In this study, EEGTP protocol is introduced which reduces the energy consumption of the CH by avoiding direct transmission to the base station. Instead of all the CH nodes directly communicating to the base station it data are given to the BS through multi hop communication. The final nodes in the multi hop communication acts as the super aggregator which aggregates the data from all the CH nodes and send it to the base station. In delay insensitive networks EEGTP protocol proves to be more efficient than the other clustering protocols.

Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

B. Baranidharan and B. Santhi, 2012. EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks. Information Technology Journal, 11: 808-811.

DOI: 10.3923/itj.2012.808.811

Received: November 14, 2011; Accepted: January 03, 2012; Published: March 26, 2012


Wireless sensor networks are the interconnected tiny sensor nodes which sense the external physical phenomenon and report its data to the central repository. Wireless Sensor Network (WSN) found its wide applicability ranging from the military field to the civilian field. A sensor node is made up of following three subsystems sensing subsystem, processing subsystem and radio subsystem (Bajaber and Awan, 2011). The sensing subsystem may be having one or more sensor for sensing the physical world phenomenon like temperature, light, seismic signals. The processing subsystem is having the dedicated processor according to the need of the application. The radio subsystem is used to give connectivity to the sensor node with other nodes or base station. Collaborative signal and information processing approach (Zhao et al., 2003) is used in the WSN, where the localization and tracking of the target is made by the groups of sensor nodes which organizes among itself and exchange their data. Some of the major issues in the CSIP are network issues like suitable routing protocols, database issues like data abstraction and query optimization and security problems. In this routing is the major problem which affects the lifetime of the network. In WSN sending a bit would be taking much more energy than processing a bit. In many practical applications like battle field monitoring, agricultural practices the sensor network should run unattended for more number of days. It becomes possible only when we are designing an exclusive suitable protocol for WSN. The clustering methods (Akkaya and Younis, 2005) are suitable for sensor networks due to its scalability factor and eliminating the redundancy among the data collected. In some applications of WSN it needs to run without any human assistance and report it to the base station. Here power consumption becomes the major issue as we can’t replace the batteries in the node. The other possible solutions to this problem is concentrating on MAC layer of the sensor, designing energy efficient routing protocol for WSN.

The WSN can exhibit continual reporting of events or intermittent reporting depending upon its application need. In both the cases clustering proves to be the suitable strategy than the direct and sequential transmission. The clustering techniques have the advantages like balancing the network load by distributing the energy consumption all over the network, fault tolerant network, increasing connectivity within the network and increased scalability factor. The clustering protocol is divided into variable convergence time and constant convergence time algorithms (Abbasi and Younis, 2007). Many clustering algorithms have been proposed till date and it varies on its CH node selection, data aggregation points.

LEACH (Heinzelman et al., 2002) is a popular clustering protocol for the WSN. It supports the distributed cluster formation. Each node selects its CH based on the received signal strength from all the eligible CH nodes. Before each data collection round, the CH nodes will advertise itself with other nodes in the network. The non-CH node will check the highest Received Signal Strength value from the CH node and attaches itself with the particular cluster. Once the cluster is finalized, the data from each cluster member is given to its respective CH nodes. The responsibility of a CH node is to aggregate these data and send it to the base station. Due to its additional work energy consumption will be more for the CH nodes than the other nodes. To avoid this rapid depletion of rare resource like energy in CH nodes, this CH node position became rotational.

LEACH follows the proactive strategy but for certain application we need to follow the reactive strategy like reporting to the base station when a particular have occurred in the environment. In that case, TEEN (Manjeshwar and Agrawal, 2001) protocol suits our need. This reactive protocol uses two threshold value called as Hard Threshold (HT) and Soft Threshold (ST). When a node senses a value higher than the HT and differs equal or greater than ST, it transmits its value to the CH node. By using HT and ST number of transmission is greatly reduced which makes it suitable for time critical events.

In APTEEN (Manjeshwar and Agarwal, 2002), both Proactive and Reactive strategies are implemented. It gives both periodic reading and time critical readings. The users have been given the choice to set time interval for periodic data collection.

Yang and Zhang (2009) used unequal clusters to solve the hot spots in the sensor networks. Hierarchical clustering algorithm UDCA was proposed by (Abidoye et al., 2011). The sensor network is divided into different layers. In each the nodes with stronger probability value will be elected as Cluster Heads (CH). The node which is having stronger probability value than all other nodes will be elected as CH node at the highest layer, it compress the data given to it by its lower layers and pass it to the base station.

GRESS (Shan et al., 2011) works in two phases. In Initialization phase, all the nodes will find its communication cost with the BS. Then the network will be divided into static clusters. In a cluster, the node which is having low cost will be elected as cluster Head (CH). All non-CH nodes have to send its ID, cost and energy residual to CH node. The CH node will compute the sleep scheduling for each node in its clusters based on this information. The sleep schedule differs for nodes based on its residual energy. In State transformation phase, the non CH nodes after its stipulated sleep time interval will go to listen state and check whether it have received any query packet from the current CH node. If receives any packet it will enter active state and becomes new CH node. The old CH node will become a non-CH member of the cluster and enter into sleep state.

ADRP (Bajaber and Awan, 2011) provides us with the adaptive routing strategy. It follows the centralized approach. All the sensor nodes will be transmitting its residual energy level to the base station. The base station will select the CH node with a set of next eligible CH nodes and send it to each sensor nodes. Due to any environmental factors if a CH node dies, the next CH node will be selected from the list without informing BS and reclustering. Because of these factors it comes for more number of data collection rounds than LEACH.

EECPL (Bajaber and Awan, 2011) also follows the centralized approach. The initial configuration of the sensor nodes will be given to the BS. Based on its remaining energy level, new CH nodes are selected and informed to the sensor nodes. This protocol reduces the responsibility of the CH nodes by transferring the duty of data transmission to the cluster sender node. The CH node only generates the TDMA schedule for its cluster member node. The cluster member nodes will be transmitting data to their neighbor nodes and aggregates there. At the end the aggregated data will be given to the cluster sender and from there it will be sent to the base station.

All these protocol are functioning in the manner that the CH node will be sending its data directly to the base station. Those CH nodes located away from the base station will be spending a considerable amount of its energy during its transmission. This paper gives a new protocol where the distanced CH nodes send its data in multi hop fashion to conserve its energy.


System model: The sensor network is randomly distributed over the sensing region. The cluster Head nodes are elected by the Base Station in each data round by its remaining energy levels. The cluster member nodes have to send its data to the CH nodes in its scheduled time and aggregation is done in CH node. This paper assumes that a unique identifier is given for each sensor node in the network and it knows its location by using GPS receiver. EEGTP protocol operates in two different phase.

Cluster formation phase: The sensor nodes will be communicating its location data gathered through the use of GPS (Fig. 1) and its remaining energy reserves to the central base station. The base station will elect the CH nodes which is having its energy level more than the Threshold level. And in each data collection round the Threshold level is reduced to elect new CH nodes. Also the already elected CH nodes would not be participating in next election of CH nodes to evenly distribute the energy consumption among the nodes.

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 1: Sensor nodes is transmitting its residual energy and location data to the central base station

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 2: Taking the shortest energy path in choosing the next hop within the intra-cluster communication

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 3: Intra-cluster communication model

The base station will be sending the new CH node ID for each sensor. If a sensor node receives its ID it becomes CH nodes for current data collection round.

Data collection phase: When the cluster member nodes are sending its data to its CH nodes there is a higher probability of collision to occur. In order to avoid the collision the CH node is generating the TDMA schedule for its member node. A minimum spanning tree (Fig. 2) is built between the far by sensor node with the CH node. The member node have to wake up its radio only during its time and go to the sleep state after sending its data to its neighbor node which involves less transmission cost as shown in Fig. 3, so as to conserve its radio consumption.

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 4: Acyclic graph for intra-cluster and shortest path for intra-cluster communication

The data aggregation takes place in every node and the final aggregated is given to the CH node. The CH node sends the aggregated data to the base station through the shortest path which involves multi hop transmission. The intermediate nodes in the multi hop communication are the other CH nodes. The inter cluster communication is avoided by using separate CDMA codes for each Clusters. Acyclic graph for Intra-Cluster and Shortest path for Inter-Cluster Communication has been shown in Fig. 4.

Radio model: The radio chosen for this EEGTP is same as (Bajaber and Awan, 2011):

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks

Where, n = Number of bits, d = Distance between two nodes, Eelec = Electronics energy and εfs = Power loss in free space. EEGTP assumes n = 4000 bits, Eelec = 50 nJ bit-1, εfs = 10 pJ bit-1 and initial of each sensor node is equal to 1 Joule. The aggregation cost for per bit is 50 nJ bit-1.


The sensor network is simulated in the MATLAB environment. The sensor nodes are randomly distributed as shown in the Fig. 5. EEGTP performance is compared with LEACH-C in intra cluster energy consumption in each round, average energy consumption for a node and total energy consumption of the CH nodes in each round. In all the three above criteria EEGTP outperforms LEACH-C. We compared EEGTP with LEACH-C since both uses centralized approach.

Intra cluster energy consumption: In LEACH-C all the cluster members are directly sending its data to the CH nodes and the CH node is in responsibility of aggregating the data and sending it to the base station.

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 5: Random distribution of 100 sensor nodes

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 6: Intra-cluster energy consumption comparison

Image for - EEGTP: Energy Efficient Graph Theory Protocol for Wireless Sensor Networks
Fig. 7: Average energy consumption of the nodes

In EEGTP each node is sending its data to its nearby neighbor node which involves lesser transmission cost. The aggregation takes place at all the nodes except the first sending node which reduces aggregation cost in CH nodes (Fig. 6).

Average energy consumption of nodes: In Fig. 7, average energy consumption of nodes in LEACH-C is compared with the EEGTP protocol. Since in EEGTP the nodes are only communicating with its neighbor nodes and even CH nodes itself is transmitting the aggregated data to the base station in the shortest path, there is a drastic reduction in the energy consumption of the nodes.


Energy efficient data gathering is a major constrained in wireless sensor networks. In this paper lifetime of the network is analyzed, it’s metrics differs based upon the sensing application. EEGTP proves to be more efficient than its counterpart. But when it goes for latency in the network it lag behind its rival protocols. In our future work, the latency of the network also will be considered.


1:  Abbasi, A.A. and M. Younis, 2007. A survey on clustering algorithms for wireless sensor networks. Comput. Commun., 30: 2826-2841.
CrossRef  |  Direct Link  |  

2:  Abidoye, A.P., N.A. Azeez, A.O. Adesina and K.K. Agbele, 2011. UDCA: Energy optimization in wireless sensor networks using uniform distributed clustering algorithms. Res. J. Inform. Technol., 3: 191-200.
CrossRef  |  

3:  Zhao, F., J. Liu, J. Liu, L. Guibas and J. Reich, 2003. Collaborative signal and information processing: An information directed approach. Proc. IEEE, 91: 1199-1209.
CrossRef  |  

4:  Bajaber, F. and I. Awan, 2011. Adaptive decentralized re-clustering protocol for wireless sensor networks. J. Comput. Syst. Sci., 77: 282-292.
CrossRef  |  Direct Link  |  

5:  Yang, J. and D. Zhang, 2009. An energy-balancing unequal clustering protocol for wireless sensor networks. Inform. Technol. J., 8: 57-63.
CrossRef  |  Direct Link  |  

6:  Akkaya, K. and M. Younis, 2005. A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 3: 325-349.
CrossRef  |  Direct Link  |  

7:  Shan, L., Y. Liu and W. Wei, 2011. GRESS: Based on gradient and residual energy of sleep scheduling in the distributed sensor networks. Res. J. Inform. Technol., 3: 132-139.
CrossRef  |  Direct Link  |  

8:  Manjeshwar, A. and D.P. Agrawal, 2001. TEEN: A routing protocol for enhanced efficiency in wireless sensor networks. Proceedings of the 15th International Parallel and Distributed Processing Symposium, April 23-27, 2001, San Francisco, CL., USA., pp: 30189-30189
CrossRef  |  

9:  Manjeshwar, A. and D.P. Agrawal, 2002. APTEEN: A hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. Proceedings of the 16th International Parallel and Distributed Processing Symposium, April 15-19, 2002, Fort Lauderdale, FL., USA., pp: 195-202
CrossRef  |  

10:  Heinzelman, W.B., A.P. Chandrakasan and H. Balakrishnan, 2002. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. Wireless Commun., 1: 660-670.
CrossRef  |  Direct Link  |  

©  2022 Science Alert. All Rights Reserved