Transmission Scheduling for Optimizing Sensor Network Lifetime: A Stochastic Shortest Path Approach

We present transmission scheduling algorithms for maximizing the lifetime of a sensor network. In each data collection, only one group of sensors are scheduled to transmit their measurements directly to an access point (AP) through a fading channel, causing a reduction in battery energy levels of these sensors. We formulate the problem of dynamically choosing which group of sensors should communicate with the AP to maximize network lifetime as a stochastic shortest path Markov decision process. We consider three types of channel information structure: global channel state information (CSI), channel statistics, and local CSI. For optimal scheduling using global CSI (i.e., the scheduler has the information of all sensors' instantaneous channel realizations), we propose an algorithm that obtains the optimal stationary scheduling policy with computational complexity reduced from exponential to polynomial in network size when the network is dense. Due to the large implementation overhead in acquiring global CSI, we consider scheduling algorithms that use channel statistics (i.e., each sensor only knows its own channel distribution) or local CSI (i.e., each sensor knows its own instantaneous channel realization). The optimal scheduling using channel statistics is formulated as a shortest path multiarmed bandit problem, which has an indexable optimal policy. We derive a closed-form expression for the Gittins index. We further show that the Gittins index is simply the residual energy when the channel fading is identically (but not necessarily independently) distributed across sensors, i.e., the optimal scheduling policy in this case is to choose the sensor with the most residual energy. Finally, we study an asymptotically optimal scheduling protocol using local CSI. This protocol has a distributed implementation yet achieves a comparable performance as the optimal scheduling using global CSI