On Hardness of Connectivity Maintenance Problem in Drone Networks
Bildiriler > Tam Metin Bildiri · 2018
Yazarlar: Vahıd AKRAM, Orhan DAĞDEVİREN
2018 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom), Gürcistan, Uluslararası, Sözlü Sunum, Tam Metin Bildiri, 2018-2018, ss 1-5
DOI: 10.1109/blackseacom.2018.8433713
Özet
Drone networks have attracted great interest from researchers very recently. One of the vital requirements of drone networks is to preserve the connectivity between nodes in the network for providing reliable data communication. Connectivity maintenance in a drone network can be a complicated task because moving any node can affect the existing links between other nodes. In this paper, we study on the movement assisted connectivity restoration problem (MACR) in drone networks. We investigate the Steiner tree problem with minimum number of Steiner points and bounded edge length (STP-MSPBEL) which is one of the known NP-Hard problems. We prove that MACR problem is also an NP-Hard problem by reducing STP-MSPBEL to MACR. This theoretical finding is important to show the hardness of the emerging problem.