A novel circle covering algorithm based on Coulomb Force Model for the problem of locating repeaters

摘要

In this paper, we present a novel circle covering algorithm for the problem of locating repeaters when users in a certain area need to be covered. A fundamental issue is the circle covering problem, where "single-layer covering" equals "covered". However, single-layer is not applicable anymore for the covering of repeaters, because the service capacity of a single repeater is so limited that it cannot accommodate all the users inside its service area. Therefore, "multi-layer covering" should be taken into consideration. To solve this multi-layer problem, we propose a physical model — the Coulomb Force Model. In our method, repeater node is regarded as positively charged particle; Areas with insufficient and surplus covering of repeaters are respectively regarded as negative electric particles and positive ones. We simulate the movement of repeater nodes in this electric field according to Coulomb's Law, and finally they will reach a dynamic balanced state. In this way, an optimal solution can be obtained for the problem of locating repeaters.