Minimum-Latency Communication Scheduling in Multihop Wireless Networks

 

Abstract

A wide range of applications for multihop wireless networks are time-critical and impose stringent requirement on the communication latency. The major obstacle for low communication latency in multihop wireless networks is the wireless interference. A communication schedule for a communication task not only specifies a communication routing but also assigns a time-slot to every communication link in the routing subject to the constraint that the communication links assigned in each time-slot are interference-free. The problem Minimum-Latency Communication Scheduling (MLCS) seeks a shortest communication schedule for a specified communication task. In this talk, we study MLCS for a number of primitive communication tasks including beaconing, boadcasting, data aggregation, data collection, and gossiping. All of these problems are NP-hard. We present approximations for them.

Short Bio

Peng-Jun Wan is an Associate Professor in the Department of Computer Science at Illinois Institute of Technology in Chicago. His research interests are wireless networking, optical networking, and algorithm design and analysis. He received his BS in Applied Mathematics from Tsinghua University, his MS in Applied Mathematics from the Chinese Academy of Sciences, and his PhD in Computer Science from University of Minnesota. He has served as the program chairs of ACM MobiHoc'08, MSN'08, WASA'07, and SPIE OptiComm'01, and as co-organizers of a number of worksops.

 

BACK