On Hardness of Connectivity Maintenance Problem in Drone Networks

摘要

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.