Minimum Latency Communication Schedules for Information Dissemination and Aggregation in Wireless Ad Hoc and Sensor Networks

Project: Research

View graph of relations


This project focuses on the studies of algorithmic issues of minimum-latency schedules for broadcast and data aggregation in wireless ad hoc/sensor networks. The major tasks of the project include:Developing better approximation algorithms for minimum-latency broadcast schedules. The existing approximation algorithms have approximation ratios either in the polylogarithmic order or with very large constants (greater than 600). The development of new approximation algorithms with small constant approximation ratios (close to one) are expected.Developing good approximation algorithms for minimum-latency multicast schedules. Multicast is a general case of broadcast. The broadcast-schedule techniques will be extended to the case of multicast and similar approximation ratios for multicast will be achieved.Investigating the minimum-latency aggregation schedule problem, which has not yet been studied in the literature. Neither computation complexity nor approximation algorithms with provably good performance is known. The NP-hardness is expected to be proven along with the development of new scheduling techniques with minimum latency data aggregation.


Project number9041130
Grant typeGRF
Effective start/end date1/01/073/02/09