Dynamic Sleep and Transmission Scheduling in Wireless Ad-hoc and Sensor Networks

November 1, 2006
Time: 1:30pm-2:30pm
CEPSR Interschool Lab, 7th floor
Hosted by: Distributed Network Analysis (DNA) Lab
Speaker: Koushik Kar, Rensselaer Polytechnic Institute


In near future, large-scale ad-hoc and sensor networks are expected to form the backbone of a vast range of applications, including military and relief operations, intra-community communication, and environmental and health monitoring. Due to the shared nature of the wireless medium and limitations on battery capacities, these networks are considerably more constrained in terms of bandwidth and energy than traditional wired networks. Thus efficient management of bandwidth and energy is crucial to the successful operation of ad-hoc and sensor networks. On the other hand, due to their large-scale, dynamic nature, resource management algorithms designed for such networks must be distributed in nature, and  have a low per-node message-complexity. In this talk, we will describe our recent results on two key resource management questions in such  networks, namely sleep scheduling and transmission scheduling. We will first discuss the question of dynamic sleep scheduling in a rechargeable  sensor network, with the objective of maximizing a time-average generalized coverage metric by appropriately putting sensors to `sleep' and waking them up when necessary. Under random energy discharge/recharge processes, we will argue that a simple, local threshold policy is provably optimal in certain special cases, and present simulation results that demonstrate the near-optimal performance of this policy in general networks. We will also show, through analysis and simulation, that spatial correlation in the recharge/discharge processes worsens system performance. We will then address the question of transmission scheduling in a wireless ad-hoc network, with the goal of maximizing the long-term throughput of the system under random packet arrivals. The transmission scheduling question will again be discussed in a stochastic  optimization framework; we will show that a class of simple scheduling policies, maximal scheduling, that can be implemented with low-complexity local message exchanges, attains a constant fraction of the maximum system throughput. Finally, we will compare and contrast the sleep and transmission scheduling questions and our approaches in addressing them, and outline open research issues.


Koushik Kar is an assistant professor in the Electrical, Computer & Systems Engineering department at Rensselaer Polytechnic Institute, Troy,
NY, a position he has held since 2002. He received his B.Tech. degree in Electrical Engineering in 1997 from the Indian Institute of Technology, Kanpur, and his Ph.D. in Electrical & Computer Engineering in 2002 from the University of Maryland, College Park. Dr. Kar's research interests are in modeling and performance optimization of communication networks, and includes issues like access control, traffic engineering, congestion control and energy management in such networks. His recent research work is primarily focused on developing distributed optimization  algorithms for efficient usage of bandwidth and energy in wireless ad-hoc and sensor networks. Dr. Kar received the Career Award from the  National Science Foundation in 2005.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University