Spearker: Weifa Liang, School of Computer Science, Australian National University
Time:2013 年 4 月 9 日（周二）上午 9:00
Venue: 邯郸校区逸夫楼 604
Contact: 阚海斌 hbkan@fudan.edu.cn
Abstract:
To deploy a wireless sensor network for the purpose of large-scale monitoring, in this paper, we propose a heterogeneous and hierarchical wireless sensor network architecture. The architecture consists of sensor nodes, gateway nodes and mobile sinks. The sensors transmit their sensing data to the gateway nodes for temporary storage through multi-hop relays, while the mobile sinks travel along pre-determined trajectories to collect data from nearby gateway nodes.
Under this paradigm of data gathering, we formulate a novel constrained optimization problem, namely, the capacitated minimum forest problem, for the decision version of which we first show NP-completeness. We then devise approximation algorithms and provide upper bounds for their approximation ratios. We finally evaluate the performance of the proposed algorithms through experimental simulation. In our experiments, the approximation ratio delivered by the proposed algorithms is always less than 2. In the case of arbitrary gateway capacities, this contrasts our theoretical results which show that the approximation ratio is at most linear in the number of gateways. Our experiments thus indicate that, for realistic inputs, our worst case analysis of the approximation ratio is very conservative. The proposed algorithms are the first approximation algorithms for the capacitated minimum forest problem, and our techniques may be applicable to other constrained optimization problems beyond wireless sensor networks.
Bio:
Weifa Liang (M'99--SM'01) received the PhD degree from the Australian National University in 1998, the ME degree from the University of Science and Technology of Chinain 1989, and the BSc degree from Wuhan University, China in 1984, all in computer science. He is currently an Associate Professor in the Research School of Computer Science at the Australian National University. His research interests include design and analysis of energy-efficient routing protocols for wireless ad hoc and sensor networks, information processing in wireless sensor networks, routing protocol design for WDM optical networks, design and analysis of parallel and distributed algorithms, combinatorial optimization, and graph theory. He is a senior member of the IEEE.
