返回主页

 

《困难网络问题的简单逼近算法:多约束路由及传感网络中转播节点的部署》课程相关信息

一、授课时间、地点安排

授课时间:20085122008516

授课地点:上海交通大学闵行校区电信群楼3号楼404

二、住宿、交通安排

1、报到时间: 2008年5月11 ,地点:上海交通大学闵行校区电信群楼3号楼121。电话:021-34204045

2、住宿安排:学术活动中心

  点:上海交通大学闵行校区

  格:360/标准双人间(每人180元),24小时热水。

订房电话:021-54740800 021-54740317

3、交通路线:

飞机:  1)从浦东机场下飞机,乘机场七线到上海火车南站。转乘地铁1号线,到莘庄站转乘地铁5号线,到东川路站下车。乘出租车,到交大西校门。

2)从虹桥机场下飞机,乘806至徐家汇,转乘地铁一号线,到莘庄站换乘地铁五号线到东川路,乘出租车,到交大西校门。

火车: 1)从上海站下车,乘地铁1号线,到莘庄站转乘地铁5号线,到东川路站下车。乘出租车,到交大西校门。

2)从上海南站下车,乘地铁1号线,到莘庄站转乘地铁5号线,到东川路站下车。乘出租车,到交大西校门。

三、联系方式

1 联系人:赵铭辰

2 电 话:021-34204045;传真:021-34204478;手机:13764521149

3 Email: druidconanrei@gmail.com

 

《困难网络问题的简单逼近算法:多约束路由及传感网络中转播节点的部署》课程简介

 

SIMPLE APPROXIMATIONS TO HARD PROBLEMS IN NETWORKING:

MULTICONSTRAINED QOS ROUTING AND RELAY NODE PLACEMENT

 

Guoliang Xue, Professor

Department of Computer Science and Engineering,

Arizona State University

 

SYNOPSIS:

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.

BIOGRAPHY

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.

PREREQUISITES:

* Basic knowledge in computer networks and algorithms

* Basic graph theory knowledge on minimum spanning trees and shortest paths