|Tuo Shi||Harbin Institute of Technology, P.R. China|
|Jianzhong Li||Harbin Institute of Technology, P.R. China|
|Hong Gao||University of Harbin Institute Technology, P.R. China|
|Zhipeng Cai||Georgia State University, USA|
Battery-Free Wireless Sensor Network (BF-WSN) is a newly proposed network architecture to address the limitation of traditional Wireless Sensor Networks (WSNs). The special features of BF-WSNs make the coverage problem quite different and even more challenging from and than that in traditional WSNs. This paper defines a new coverage problem in BF-WSNs which aims at maximizing coverage quality rather than prolonging network lifetime. The newly defined coverage problem is proved to be at least NP-Hard. Two sufficient conditions, under which the optimal solution of the problem can be derived in polynomial time, are given in this paper. Furthermore, two approximate algorithms are proposed to derive nearly optimal coverage when the sufficient conditions are unsatisfied. The time complexity and approximate ratio of the two algorithms are analyzed. Extensive simulations are carried out to examine the performance of the proposed algorithms. The simulation results show that these algorithms are efficient and effective. I. MOTIVATION The Internet of Things (IoT) is rapidly spread nowadays in which Wireless Sensor Networks (WSNs) are important building components that can be widely deployed and used to monitor and collect information from the physical world -. However, traditional WSNs are powered by batteries and it is a serious challenge to replace batteries for nodes after a long-term working period. It is even impossible to replace batteries in many applications. The trouble of replacing batteries has hindered the development of the IoTs. To address the limitation of traditional WSNs, a new network architecture, Battery-Free Wireless Sensor Network (BF-WSN), is introduced and has been investigated in the recent years. In BF-WSNs, each battery-free nodes has no embedded batteries and is powered by the energy harvested from its ambient power resources, such as solar power, wind power, and RF signal power. Moreover, a super-capacitor, which can be recharged for unlimited times, is used by each battery-free node to store energy. This paper investigates the coverage problem in BF-WSNs. The coverage problem is a classical problem in traditional WSNs, and it is the fundamental of the data integrity  and data query  services, therefore many solutions have been proposed -. However, existing solutions are not suitable for BF-WSNs due to the following reasons. First, since the nodes in traditional WSNs are powered by batteries with limited energy, the network lifetime is finite if the batteries are not replaced. Accordingly, the objective of all the existing solutions is to save energy and prolong network lifetime. Differently, BF-WSNs have infinite network lifetime in terms of energy. Therefore, the objective of the coverage problem in BF-WSNs is how to effectively make use of the harvested energy to optimize coverage quality rather than to save energy and prolong network lifetime. Second, the nodes in traditional WSNs can monitor targets any time during their lifetime. However, the nodes in BF-WSNs are able to monitor targets only if they have harvested enough energy to support the monitoring, which means the nodes in BF-WSNs cannot monitor targets at any time. Therefore, the coverage problem in BF-WSNs is much harder than that in traditional WSNs. Third, unlike traditional energy-harvesting networks in which nodes are recharged by stable energy resources , due to the impact of ambient environment, the power supply of BF-WSNs is unstable. Furthermore, the energy recharging rate is uncertain and is usually lower than the energy consuming rate of the nodes, and the energy distribution among all the nodes in a network is unbalanced. The nodes in BF-WSNs may be out of service quite often due to the limitation of the energy capacitor and the uncertainty of the recharging rate. The aforementioned features of BF-WSNs bring new challenges to the coverage problem ,  and make coverage a new problem in BF-WSNs which is different from the one in traditional WSNs. This paper is to solve the new coverage problem in BF-WSNs. To the best of our knowledge, this is the first work to investigate the new coverage problem in the BF-WSNs. The main contributions are as follows. (1) A new metric, named as Coverage Quality, is introduced to measure coverage quality in a BF-WSN. This is the first work studying coverage quality in BF-WSNs. (2) A new coverage problem in BF-WSNs, called MC-BF, is defined. We prove that MC-BF is at least NP-Hard. Furthermore, the sufficient conditions are given, under which the optimal solution of MC-BF can be found in polynomial time. A corresponding polynomial algorithm to obtain the optimal solution of MC-BF is proposed. (3) Two approximate algorithms with polynomial time are also proposed for solving MC-BF. The approximate ratio of the algorithms is proved. (4) Extensive simulations are performed to evaluate the performance of the proposed algorithms. The simulation results show that these algorithms are efficient and effective. The rest of the paper is organized as follows. Section II surveys the related works. Section III presents the definition of MC-BF and the polynomial time algorithm for finding the optimal solution of MC-BF. In Section IV, two approximate algorithms are proposed with the approximate ratio. Section V shows the simulation results. Section VI concludes the paper.