Optimal Placement of Radio Repeater Networks Control #10754

In this paper we consider the problem of placing radio repeaters to serve users in an area. Given a population distribution and geographical map, we use a hill-climbing algorithm to find a minimum number of repeaters required to cover an area and then a genetic algorithm to provide maximal population coverage and net-work connectedness. We then use hill-climbing techniques to allocate subnetworks based on population size at repeater locations so that two arbitrary users can com-municate even when all other users are communicating over the maximum number of possible networks. Our resulting algorithm is capable of producing a range of re-peater network allocations, from robust networks that are capable of handling worst-case usage scenarios to smaller networks that provide optimal population coverage and connectivity. On a set of real-world population and geography data, we found that the combination of the hill-climbing and genetic algorithms had 28 % better population coverage than a control algorithm did, as well as higher connectivity