Online Packet Admission and Oblivious Routing in Sensor Networks

摘要

The concept of Oblivious Routing for general undirected networks was introduced by Raecke when he showed that there exists an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. In a following result, Raecke and Rosen presented admission control algorithms achieving a polylogarithmic fraction (in the size of the network) of the optimal number of accepted messages. Both these results assume that the network incurs a cost only after it is accepted and the message is routed. Admission control and routing algorithms for sensor networks under energy constraints, however, need to account for the energy spent in checking for feasible routes prior to the acceptance of a message and hence, it is unclear if these algorithms achieve polylogarithmic bounds under this condition. In this paper, we address this problem and prove that such algorithms do not exist when messages are generated by an adversary. Furthermore, we show that an oblivious routing algorithm cannot have a polylogarithmic competitive ratio without a packet-admission protocol. We present a deterministic O(ρ log n)-competitive algorithm for tree networks where the capacity of any node is in [k, pk]. For grids, we present an O(log n)-competitive algorithm when nodes have capacities in θ(log n) under the assumption that each message is drawn uniformly at random from all pairs of nodes in the grid.