Optimal New Node Insertion for Strong Minimum Energy Topology in IoT Networks

摘要

To provide seamless services by low powered small devices having stringent energy constraint in Internet of Things (IoT) networks, it is highly sought over the past few decades to design a competent energy-aware network. In that sense, thereof, the strong minimum energy topology (SMET) is investigated in the existing works to minimize the total power consumption while maintaining the strong connectivity between any pair of nodes (small IoT devices) in the network consisting only bidirectional links. Nevertheless, to significantly improve it, in this paper, we further explore the SMET with respect to insertion of a new node among the existing nodes which is defined as node insertion problem (NIP) for SMET (NIP-SMET). It has been proved that the NIP-SMET is NP-complete, therefore, we propose a heuristic based on Prim-incremental power greedy heuristic to solve it in polynomial time. Also, analytically, it has been shown that the NIP-SMET can provide significant energy-aware improvement over SMET. Via obtained numerical results, we find that the proposed heuristic can reduce the total power dissipation by 50% against the existing heuristic for SMET.