Transmission Scheduling for Optimizing Sensor Network Lifetime: A Stochastic Shortest Path Approach
- 23 April 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 55 (5), 2294-2309
- https://doi.org/10.1109/tsp.2007.893213
Abstract
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 CSIKeywords
This publication has 33 references indexed in Scilit:
- POMDP Multi-armed Bandit Formulation for Energy Minimization in Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Type based estimation over multiaccess channelsIEEE Transactions on Signal Processing, 2006
- Maximizing system lifetime in wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Opportunistic Carrier Sensing for Energy-Efficient Information Retrieval in Sensor NetworksEURASIP Journal on Wireless Communications and Networking, 2005
- A Note on Bandits with a TwistSIAM Journal on Discrete Mathematics, 2004
- Fusion of decisions transmitted over fading channels in wireless sensor networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On Playing Golf with Two BallsSIAM Journal on Discrete Mathematics, 2003
- Algorithms for optimal scheduling and management of hidden Markov model sensorsIEEE Transactions on Signal Processing, 2002
- Restless bandits: activity allocation in a changing worldJournal of Applied Probability, 1988
- The Optimal Control of Partially Observable Markov Processes over a Finite HorizonOperations Research, 1973