Search

With the increasing maturity of wireless charging technology, especially the development of magnetic resonance wireless charging technology, the employment of mobile charging vehicles and wireless charging technology to replenish sensors' energy to ensure the continuous operation of wireless sensor networks has become a new research hotspot. This paper focused on how to schedule multiple charging vehicles to replenish energy to the sensors in a large-scale wireless sensor network. In order to balance the charging tasks of multiple charging vehicles and reduce the completion time of the whole charging task, the paper proposed the charging task completion time minimization problem, hoping to find K closed charging circles for K charging vehicles, so that the longest completion time among these K vehicles was the shortest. Since the charging task completion time minimization problem was an NP-hard problem and it was difficult to find an optimal solution in polynomial time, this paper proposed an approximation algorithm with a ratio of 5 for this problem. Finally, it demonstrated the performance of the algorithm by simulation experiments, and the experiments show that the actual approximation ratio of the proposed algorithm is less than 2. [ABSTRACT FROM AUTHOR]

A virtual backbone of wireless sensor networks is a subset of nodes and only virtual backbone nodes are responsible for routing-related tasks. The smaller a virtual backbone is, the less the network overhead, the size of a virtual backbone is the key factor to measure the quality of the vi11ual backbone. Frequently, the unit disk graph is used to model a wireless sensor network. In a wireless sensor network, the problem of finding the minimum virtual backbone is abstracted to the problem of finding the minimum connected dominating set in the unit disk graph corresponding to the wireless network. However, the problem of finding the minimum connected dominating set in the unit disk graph is a NP-hard problem, many works contribute to obtain the approximation algorithm of the minimum connected dominating set rather than finding the minimum connected dominating set in the unit disk graph. Constructing a 3-connected r-hop dominating set in wireless sensor networks is an effective means to obtain a connected dominating set with a smaller size such that can reduce the total amount of information forwarded between any nodes, which is a better approximation for finding the minimum virtual backbone. This paper proposed an algorithm to construct a 3-connected r-hop dominating set in wireless sensor network. It shows that the size of a 3-connected r-hop dominating set produced by the algorithm is no more than 5 (2r + 2β + 1) (r + 1) β| U' I - 10(2 + β) (r + 1) - 5r - 12. At the end, it analyzed the performance of the proposed algorithm by experiment simulation, and the experimental results are consistent with what expected. [ABSTRACT FROM AUTHOR]