Relay Placement for Reliable Base Station Connectivity in Polymorphous Networks

With emerging demand for online surveillance and management, persistent and reliable connectivity to base stations (BSs) is indispensable so that network operators, which have access to all BSs, can collect measurements from all wireless terminals in the field, monitor their status and respond to critical incidents in real-time. However, disconnected networks make reliable BS connectivity problematic. Many papers have studied the problem of placing the minimum number of relays to retain connectivity. However, none of them considered polymorphous networks, which have multiple topologies, due to terminal movement, unsynchronized wakeup schedule and packet forwarding policy. Our paper makes the first attempt towards the study of relay placement problem in polymorphous networks. We propose two heuristic algorithms, topology stitch algorithm and topology iterative algorithm, which are built upon constrained relay placement algorithms for monomorphous networks with a single topology. Also, we propose the weigh-and-place algorithm (WPA), which optimizes relay placement across topologies with balanced load based on integer programming formulation. Evaluation shows that WPA places a smaller number of relays than the other two heuristic algorithms and achieves good load balance among multiple BSs.