Algorithm design and analysis in wireless networks

Algorithms are perhaps the most fundamental and fascinating elements in computer science asa whole. Networks and networked systems are no exception. This habilitation thesis summarizesmy research during the last eight years on some algorithmic problems of both fundamental andpractical importance in modern networks and networked systems, more specifically, wireless networks.Generically, wireless networks have a number of common features which form a commonground on which algorithms for wireless networks are designed. These features include the lackof network-wide coordination, large number of nodes, limited energy and computation resource,and the unreliable wireless links. These constraints and considerations make the algorithmic studyfor wireless networks an emerging research field requiring new tools and methodologies, some ofwhich cannot be drawn from existing state-of-the-art research in either algorithm or networkingcommunity.Motivated by this observation, we aim at making a tiny while systematic step forwards in thedesign and analysis of algorithms that can scale elegantly, act efficiently in terms of computationand communication, while keeping operations as local and distributed as possible. Specifically, weexpose our works on a number of algorithmic problems in emerging wireless networks that aresimple 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 neighbordiscovery, (2) opportunistic channel access, (3) distributed learning, (4) path optimizationand 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 characterizethe performance of the optimal solution as well as some natural and intuitive algorithmsin some cases. These results usually give us pertinent insights on the structuralproperties of the problem including the theoretical limit and the performance gap betweenthe limit and any algorithm that is not carefully devised.- Optimum or approximation algorithm design. Guided by the theoretical results establishedin the first step, we then direct our efforts to the design and analysis of efficientalgorithms for the target problem. By efficient we mean that our algorithms produce eitherthe optimum solution, or, in case where the problem is NP-hard, constant-factor or logarithmicapproximations in polynomial or quasi-polynomial time.- Further extension and generalization. Once we have established a complete frameworksolving or approximately solving the problem, we further analyze the lessons that can belearnt from the analysis process and demonstrate how our framework can be extended oradapted to address a generic class of problems in a wider range of applications presentingsimilar structural properties