Title: Minimizing interference for the highway model in Wireless Ad-hoc and Sensor Networks

Abstract: Finding a low-interference connected topology is one of the fundamental problems in Wireless Sensor Networks(WSNs). The receiver-centric interference on a node is the number of other nodes whose transmission ranges cover the node. The problem of reducing interference through adjusting the nodes' transmission radii in a connected network is one of the most well-known open algorithmic problems in wireless sensor network optimization. In this talk, we introduce our work on minimization of the average interference and the maximum interference for the high-way model, where all the nodes are arbitrarily distributed on a line. Two exact algorithms are proposed. One constructs the optimal topology that minimizes the average interference among all the nodes in polynomial time, $O(n^3 \Delta^3)$, where $n$ is the number of nodes and $\Delta$ is the maximum node degree. The other algorithm constructs the optimal topology that minimizes the maximum interference in sub-exponential time, $O(n^3\Delta^{O(k)})$, where $k=O(\sqrt{\Delta})$ is the minimum maximum interference.

Title: Approximation Algorithms for the Physical Interference Model in WSN

Abstract: In this talk I will survey results from a newly emerging line of research that targets algorithm analysis in the physical interference model. In the main part of my talk I focus on wireless scheduling: given a set of communication requests, arbitrarily distributed in space, how can these requests be scheduled efficiently. I will talk about the difficulty of this problem and I examine algorithms for wireless scheduling with provable performance guarantees. Moreover, I present a few results for related problems and give additional context. There are two kind algorithm of the scheduling under SINR model: Scheduling with or without power control.