题 目：近似算法设计和应用实例--无线传感器网络基站最佳位置

报告人：石 怡 高级研究员

单 位：美国智能自动化公司

时 间: 2014年7月2日（周三）上午10：00

地 点：：校学术活动中心二楼小报告厅

报告人简介：石怡博士2007年毕业于弗吉尼亚理工大学电子和计算机工程系，现为美国智能自动化公司高级研究员，美国弗吉尼亚理工大学客座助理教授，IEEE高级会员。石博士的研究领域集中在无线网络干扰信号管理，能量管理，认知无线网络，MIMO网络，协作通讯网络，无线传感器网络，无线Ad Hoc网络，卫星网络，社交网络等。石博士参与编写了5本书，在国际知名期刊和会议上发表论文近百篇。2006年，石博士以华盛顿区第一名的身份获得由中国政府颁发的“国家优秀自费留学生”的奖励；2008年和2011年，石博士的论文先后两次在IEEE INFOCOM会议中获得最佳论文奖及最佳论文入围奖。石博士担任IEEE Communications Surveys and Tutorials编辑，担任过3个workshop的技术委员会主席和近50个国际会议的技术委员会委员，包括IEEE INFOCOM, ACM MobiHoc, IEEE MILCOM, IEEE ICC, IEEE WCNC, IEEE GLOBECOM等。

内容简介：In this talk, I will show how to design (1 − ε)-optimal algorithm. We first give a brief overview on approximation algorithms. Such algorithms are designed to offer solutions that can approximate the unknown optimal solution according to certain benchmark performance criteria. In particular, in wireless network research, the most popular approximation algorithms can be classified as constant-factor approximation algorithms and (1 − ε)-optimal approximation algorithms. The constant-factor approximation algorithms would only be useful if c is close to 1. But unfortunately, many results in the literature offer results that may be far away from 1. Our preference is toward the design of (1 − ε)-optimal approximation algorithms, which will be presented with a case study. Such algorithms are intellectually challenging and require much novelty in their design. Nevertheless, should one be able to design such an algorithm, then both its theoretical significance and practical value would be assured.

The case study is a classic and fundamental problem on base station placement in a wireless sensor network (WSN). We aim to find the optimal location for the base station so that the network lifetime (until any sensor node runs out of energy) is maximized.