Efficient management of transient station failures in linear radio communication networks with bases

摘要

Given a communication network undergoing a transient component failure, a swap algorithm provides the maintenance of the network functionality by means of a minimum number of adjustments. Swap algorithms have recently received growing attention for managing transient failures in classic wired networks, due to their practical usefulness. In this paper, we propose efficient swap algorithms to guarantee survivability in a linear radio communication network undergoing transient station failures. More precisely, given an optimal range assignment for a set of n stations with bases spread on a line, and a bounded number of hops h, we show that, as a consequence of a single non-base station failure, the network survivability can always be guaranteed through a minimum number of adjustments, i.e., by updating either of one station in O(h log n) time, or two stations in O(n) time, or three stations in O(hn) time, all using O(n) space, depending on the structure of the network around the failed station. Furthermore, our swap algorithms identifies the best network reconfiguration in terms of the additional required power.