Algorithm design and analysis in wireless networks - Laboratoire Interdisciplinaire des Sciences du Numérique Access content directly
Habilitation À Diriger Des Recherches Year : 2017

Algorithm design and analysis in wireless networks

Lin Chen


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.
Fichier principal
Vignette du fichier
hdr.pdf (1.37 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

tel-01688436 , version 1 (24-01-2018)


  • HAL Id : tel-01688436 , version 1


Lin Chen. Algorithm design and analysis in wireless networks. Data Structures and Algorithms [cs.DS]. Paris-Sud XI, 2017. ⟨tel-01688436⟩
302 View
472 Download


Gmail Facebook Twitter LinkedIn More