Enhanced PEGASIS using Dynamic Programming for Data Gathering in Wireless Sensor Network

  • Mohammad Robihul Mufid Politeknik Elektronika Negeri Surabaya
  • M. Udin Harun Al Rasyid Politeknik Elektronika Negeri Surabaya
  • Iwan Syarif Politeknik Elektronika Negeri Surabaya
Keywords: Wireless Sensor Network, EPDP, LEACH, PEGASIS, dynamic programming


A number of routing protocol algorithms such as Low-Energy Adaptive Clustering Hierarchy (LEACH) and Power-Efficient Gathering in Sensor Information Systems (PEGASIS) have been proposed to overcome the problem of energy consumption in Wireless Sensor Network (WSN) technology. PEGASIS is a development of the LEACH protocol, where within PEGASIS all nodes are active during data transfer rounds thus limiting the lifetime of the WSN. This study aims to propose improvements from the previous PEGASIS version by giving the name Enhanced PEGASIS using Dynamic Programming (EPDP). EPDP uses the Dominating Set (DS) concept in selecting a subset of nodes to be activated and using dynamic programming based optimization in forming chains from each node. There are 2 topology nodes that we use, namely random and static. Then for the Base Station (BS), it will also be divided into several scenarios, namely the BS is placed outside the network, in the corner of the network, and in the middle of the network. Whereas to determine the performance between EPDP, PEGASIS and LEACH, an analysis of the number of die nodes, number of alive nodes, and remaining of energy were analyzed. From the experiment result, it was found that the EPDP protocol had better performance compared to the LEACH and PEGASIS protocols in terms of number of die nodes, number of alive nodes, and remaining of energy. Whereas the best BS placement is in the middle of the network and uses static node distribution topologies to save more energy.

Author Biographies

Mohammad Robihul Mufid, Politeknik Elektronika Negeri Surabaya
Departement of Information and Computer Engineering
M. Udin Harun Al Rasyid, Politeknik Elektronika Negeri Surabaya
Departement of Information and Computer Engineering
Iwan Syarif, Politeknik Elektronika Negeri Surabaya
Departement of Information and Computer Engineering


Frank L. Lewis, Wireless sensor networks, Smart environments: technologies, protocols, and applications, pp. 11-46, 2004.

M. Robihul Mufid, M. Udin Harun Al Rasyid, Amang Sudarsono, Allocation Strategy Guaranteed Time Slots (GTS) on Real Hardware Wireless Sensor Network (WSN), International Conference on Information & Communication Technology and System (ICTS), pp. 187-192, Oct. 2017.

IEEE 802.15.4, Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs), IEEE Standard for Local and metropolitan area networks, Sep. 2011.

M. Udin Harun Al Rasyid, Bih-Hwang Lee, Iwan Syarif, Mokhammad Muqoffi Arkham, LEACH Partition Topology for Wireless Sensor Network, International Conference on Consumer Electronics – Taiwan (ICCE-TW), pp. 1-5, May 2018.

Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan, Energy efficient communication protocol for wireless microsensor networks, International Conference on Hawaii International Conference in System Sciences (HICSS), pp. 3005-3014, Jan. 2000.

Stephanie Lindsey, Cauligi Raghavendra, and Krishna M. Sivalingam, Data gathering algorithms in sensor networks using energy metrics, IEEE Trans. Parallel Distrib. Syst., vol. 13, no. 9, pp. 924–935, Sep. 2002.

Wendi Rabiner Heinzelman, Anantha P. Chandrakasan, and Hari Balakrishnan, An application-specific protocol architecture for wireless microsensor networks, IEEE Trans. Wireless Communications, vol. 1, no. 4, pp. 660- 670, Oct. 2002.

Balakrishnan Baranidharan, and B. Santhi, GAECH: Genetic Algorithm Based Energy Efficient Clustering Hierarchy in Wireless Sensor Networks, Journal of. Sensors, 2015.

Stephanie Lindsey and Cauligi S. Raghavendra, PEGASIS: Power-efficient gathering in sensor information systems, In Aerospace conference proceedings, vol. 3, pp. 3-3, 2002.

Alekha Kumar Mishra, Rukshan Ur Rahman, Rahul Bharadwaj, and Rohit Sharma, An Enhancement of PEGASIS Protocol with Improved Network Lifetime for Wireless Sensor Networks, Communication and Information Technology Conference (PCITC), pp. 142-147, 2015.

Jin Wang, Jiayi Cao, Yiquan Cao, Bin Li, and Sungyoung Lee, An improved energy-efficient clustering algorithm based on MECA and PEGASIS for WSNs, International Conference on Advanced Cloud and Big Data, pp. 262-266, 2015.

Saurav Ghosh, Sanjoy Mondal, and Utpal Biswas, Enhanced PEGASIS using ant colony optimization for data gathering in WSN, International Conference on Information Communication and Embedded Systems (ICICES), pp. 1-6, 2016.

Azrina Abd Aziz, and Y. Ahmet ÅžekercioÄŸlu. A distributed energy aware connected dominating set technique for wireless sensor networks, International Conference on Intelligent and Advanced Systems (ICIAS), vol. 1, pp. 241-246, Jun. 2012.

Kui, X., Sheng, Y., Du, H., & Liang, J. (2013). Constructing a CDS-based network backbone for data collection in wireless sensor networks, International Journal of Distributed Sensor Networks, vol. 9, no. 4, pp. 258081, 2013.

Ronald A. Howard, Dynamic Programming and Markov Processes, MIT Press and Wiley, New York, 1960.