liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Boru̇vka-incremental power greedy heuristic for strong minimum energy topology in wireless sensor networks
Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India.
Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India.
Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India.ORCID iD: 0000-0002-3225-6495
Indian Institute of Technology Delhi, Hauz Khas, New Delhi 110016, India.
2015 (English)In: Proceeding ICDCN '15 Proceedings of the 2015 International Conference on Distributed Computing and Networking, Association for Computing Machinery , 2015, article id 25Conference paper, Published paper (Refereed)
Abstract [en]

Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmission range to each sensor node so that the sum of the transmission range for all the sensor is minimum subject to the constraint that the network is strongly connected (there is a directed path between every pair of nodes in the Network). This problem is known to be NP-hard. As this problem has lots of practical applications, several approximation algorithms and heuristics have been proposed. In this paper, we propose a new heuristic called Boru̇vka-incremental power greedy heuristic based on the Boru̇vka algorithm for the minimum spanning tree (MST) problem for solving the SMET problem. We compare the performance of the Boru̇vka-incremental power greedy heuristic with Kruskal-incremental power greedy heuristic and Prim-incremental power greedy heuristic. Extensive simulation results illustrate that Boru̇vka heuristic outperforms the Kruskal-incremental power greedy heuristic and Prim-incremental power greedy heuristic. We have also proved that apart from providing significant improvement in terms of average power savings, Boru̇vka incremental power greedy heuristic takes O(n) time for planar graphs as compared to O(n log n) time taken by Kruskal-incremental power greedy heuristic and O(n2) time taken by Prim-incremental power greedy heuristic, where n is the number of nodes in the network.

Place, publisher, year, edition, pages
Association for Computing Machinery , 2015. article id 25
Keywords [en]
Algorithms; Approximation algorithms; Distributed computer systems; Graph theory; Problem solving; Sensor nodes; Telecommunication networks; Topology; Trees (mathematics), Extensive simulations; Graph algorithms; Minimum Spanning Tree problem; Minimum spanning trees; Minimum-energy topologies; Strongly connected; Topology control; Transmission ranges, Wireless sensor networks
National Category
Signal Processing Communication Systems Computer and Information Sciences
Identifiers
URN: urn:nbn:se:liu:diva-155765DOI: 10.1145/2684464.2684490ISBN: 9781450329286 (print)OAI: oai:DiVA.org:liu-155765DiVA, id: diva2:1299039
Conference
ICDCN '15 Proceedings of the 2015 International Conference on Distributed Computing and Networking, January 4-7, 2015, Goa, India
Available from: 2019-03-26 Created: 2019-03-26 Last updated: 2019-03-26Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Mishra, Deepak

Search in DiVA

By author/editor
Mishra, Deepak
Signal ProcessingCommunication SystemsComputer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf