Constructing connected dominating sets in battery-free networks

Abstract

Currently, the limitation of battery has become a serious obstacle for the development of Internet of things (IoTs). Therefore, a new network architecture, named as battery-free network, were proposed. In a typical battery-free network, the battery-free nodes are equipped with any battery and can only gain energy from the environment. Such network extremely expands the scope of the IoT applications, however, it also brings many troubles for some network operations, e.g. data collection, since the energy of each node is quite small. Considering that the Connected Dominating Sets (CDSs) are commonly used to support data collection and network communication in wireless networks, and thus we will also investigate the CDS construction problem in battery-free networks. In this paper, the problem of constructing CDS in a battery-free network is formally defined, and we prove that it is NP-Complete. Thus, four approximation algorithms were proposed to deal with the snapshot, continuous and time-window based CDS construction requirements, respectively. Finally, the extensive experiments were carried out and the results verify that the proposed algorithms have high performance in term of accuracy and efficiency.