Algorithm design and analysis in wireless networks
Abstract
Algorithms are perhaps the most fundamental and fascinating elements in computer science as
a whole. Networks and networked systems are no exception. This habilitation thesis summarizes
my research during the last eight years on some algorithmic problems of both fundamental and
practical importance in modern networks and networked systems, more specifically, wireless networks.
Generically, wireless networks have a number of common features which form a common
ground on which algorithms for wireless networks are designed. These features include the lack
of network-wide coordination, large number of nodes, limited energy and computation resource,
and the unreliable wireless links. These constraints and considerations make the algorithmic study
for wireless networks an emerging research field requiring new tools and methodologies, some of
which cannot be drawn from existing state-of-the-art research in either algorithm or networking
community.
Motivated by this observation, we aim at making a tiny while systematic step forwards in the
design and analysis of algorithms that can scale elegantly, act efficiently in terms of computation
and communication, while keeping operations as local and distributed as possible. Specifically, we
expose our works on a number of algorithmic problems in emerging wireless networks that are
simple to state and intuitively understandable, while of both fundamental and practical importance,
and require non-trivial efforts to solve. These problems include (1) channel rendezvous and neighbor
discovery, (2) opportunistic channel access, (3) distributed learning, (4) path optimization
and scheduling, (5) algorithm design and analysis in radio-frequency identification systems.
Methodologically, most of our analysis is systematically articulated as follows.
- Theoretical performance bound. After formulating the target problem, we analytically characterize
the performance of the optimal solution as well as some natural and intuitive algorithms
in some cases. These results usually give us pertinent insights on the structural
properties of the problem including the theoretical limit and the performance gap between
the limit and any algorithm that is not carefully devised.
- Optimum or approximation algorithm design. Guided by the theoretical results established
in the first step, we then direct our efforts to the design and analysis of efficient
algorithms for the target problem. By efficient we mean that our algorithms produce either
the optimum solution, or, in case where the problem is NP-hard, constant-factor or logarithmic
approximations in polynomial or quasi-polynomial time.
- Further extension and generalization. Once we have established a complete framework
solving or approximately solving the problem, we further analyze the lessons that can be
learnt from the analysis process and demonstrate how our framework can be extended or
adapted to address a generic class of problems in a wider range of applications presenting
similar structural properties.
Origin : Files produced by the author(s)
Loading...