2、 电 话：021-34204045；传真：021-34204478；手机：13764521149
3、 Email: email@example.com
SIMPLE APPROXIMATIONS TO HARD PROBLEMS IN NETWORKING:
MULTICONSTRAINED QOS ROUTING AND RELAY NODE PLACEMENT
Guoliang Xue, Professor
Department of Computer Science and Engineering,
In this graduate level short course, Professor Guoliang Xue will present recent advances and challenges in the areas of multi-constrained quality of service (QoS) routing and relay node placement in wireless sensor networks. These problems are fundamental problems in networking, and are intrinsically hard to solve. However, these hard problem admit very simple approximation algorithms with provably good performance. The lectures will start with background knowledge of the problems, and cover recent results published in IEEE/ACM Transactions on Networking (the premier journal in networking), IEEE INFOCOM (the premier conference in computer communications), and ACM MOBIHOC (the premier conference in mobile ad hoc networks). The lectures will also discuss open research issues in these areas.
A fundamental problem in quality of service (QoS) routing is to find a path between a specified source-destination node pair that satisfies K additive QoS constraints, where K>=2 is a constant integer. This problem is known to be NP-hard, and has been heavily studied for the case of K=2, where the two QoS parameters denote cost and delay, respectively. Existing approaches to this problem can generally be divided into two classes: simple heuristics that does not provide performance guarantees, or sophisticated approximation algorithms that provide worst case performance guarantees but are complicated for implementation. We present some recent advances for solving the general problem with K>=2 QoS constraints. These include faster (1+epsilon)-approximation algorithms, and a class of K-approximation algorithms which run as fast as the well-known shortest path algorithms.
The relay node placement problem is concerned with deploying the minimum number of relay nodes into a field of sensor nodes to meet certain system requirements. While the functions of the sensor nodes are sensing and short range communication, the functions of relay nodes are for communication only. System requirements can be in the form of connectivity or survivability. Depending whether the sensor nodes are selfish or not, the problem can be either two-tiered or single-tiered. While most of these problems are known to be NP-hard, we will present simple approximation algorithms with provably good performance.
Guoliang Xue(薛国良)is a Professor of Computer Science and Engineering at Arizona State University. He received the PhD degree in Computer Science from the University of Minnesota in 1991. He has held previous positions as Assistant/Associate Professor of Computer Science at the University of Vermont. His research interests include quality of service routing, resource allocation in wireless networks, and relay node placement in wireless sensor networks. He currently serves on the editorial boards of Computer Networks, IEEE Network Magazine, and IEEE Transactions on Wireless Communications. He has served as a TPC co-Chair of IEEE IPCCC'2003, a TPC co-Chair of IEEE HPSR'2004, a TPC co-Chair of IEEE Globecom'2006 Ad Hoc and Sensor Networking Symposium, a TPC co-Chair of IEEE ICC'2007 Ad Hoc and Sensor Networking Symposium.He is also the General Chair of IEEE IPCCC'2005, and a General co-Chair of IEEE HPSR'2008. He will serve as a TPC co-Chair of IEEE ICC'2009 Ad Hoc and Sensor Networking Symposium, and a TPC co-Chair of IEEE INFOCOM'2010.
More information can be found at http://optimization.asu.edu/~xue.
* Basic knowledge in computer networks and algorithms
* Basic graph theory knowledge on minimum spanning trees and shortest paths