Group:Wireless Sensor Network Group
Title: Complexity in Geometric SINR; Self-synchronization Using Coupled Oscillators
Speaker: Guanyu Wang, Jinbiao Chen University
Time: 2010-10-25 10:00-2010-10-25 11:30
Venue: FIT 1-222

Abstract:

Abstract of "Complexity in Geometric SINR":

In this paper we study the problem of scheduling wireless links in the geometric SINR model, which explicitly uses the fact that nodes are distributed in the Euclidean plane. We present the first NP-completeness proofs in such a model. In particular, we prove two problems to be NP-complete: Scheduling and One-Shot Scheduling. The first problem consists in finding a minimum-length schedule for a given set of links. The second problem receives a weighted set of links as input and consists in finding a maximum-weight subset of links to be scheduled simultaneously in one shot. In addition to the complexity proofs, we devise an approximation algorithm for each problem.

Abstract of "self-synchronization using coupled oscillators":

First I will briefly introduce some self-synchronization phenomenon in nature, and the theory of coupled oscillators and the utilization of this theory in time-synchronization and desynchronization. To spread out, then I will emphasize the estimation of a common set of parameters using this theory, which I believe is very important and useful for our own design, finally, I will briefly talk about our research routine in this brand new area.




Short Bio: