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
New heuristics for strong minimum energy topology with reduced time complexity
Computer Science and Application Group, Department of Mathematic, IIT Delhi, New Delhi 110016, India.
Computer Science and Application Group, Department of Mathematic, IIT Delhi, New Delhi 110016, India.
Department of Electrical Engineering, IIT Delhi, New Delhi 110016, India.ORCID iD: 0000-0002-3225-6495
Department of Electrical Engineering, IIT Delhi, New Delhi 110016, India.
2018 (English)In: 2017 IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), Institute of Electrical and Electronics Engineers (IEEE), 2018, p. 1-6Conference paper, Published paper (Refereed)
Abstract [en]

The strong minimum energy topology (SMET) problem is to assign transmission range to a set of sensors, such that the resulting topology is strongly connected and the sum of transmit powers of all the sensors is minimized. This problem, having wide range of applications, is known to be NP-hard and also APX-hard for 3-dimension space. Several heuristics and approximation algorithms have been proposed for this problem. In this paper, we first present an enhanced version of Prim-incremental power greedy heuristic which improves the running time of the existing algorithm by a factor of n, i.e., from O(n3) to O(n2), where n is the number of nodes in the network. Simulations results are also presented to support the theoretical result. Next we propose a new heuristics for SMET problem called Hybrid heuristic, which is based on BorÛvka and Prim MST algorithms and is shown to have lower complexity than both of them. Lastly, we show that this Hybrid heuristics which can provide energy efficiency gains over the existing ones is also the fastest power greedy heuristics for SMET problem when the nodes and links of the network form a planar graph.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. p. 1-6
Keywords [en]
Approximation algorithms; Energy efficiency; Graph theory; Heuristic algorithms, Greedy heuristics; Heuristics and approximations; Hybrid heuristics; Lower complexity; Minimum-energy topologies; Nodes and links; Strongly connected; Transmission ranges, Complex networks
National Category
Communication Systems Signal Processing Computer and Information Sciences
Identifiers
URN: urn:nbn:se:liu:diva-155739DOI: 10.1109/ANTS.2017.8384173ISBN: 9781538623473 (electronic)ISBN: 9781538623466 (electronic)ISBN: 9781538623480 (electronic)OAI: oai:DiVA.org:liu-155739DiVA, id: diva2:1299148
Conference
IEEE International Conference on Advanced Networks and Telecommunications Systems (ANTS), 17-20 December, Bhubaneswar, 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
Communication SystemsSignal ProcessingComputer 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