Fractional edge coloring for wireless link scheduling in the physical interference mode

• Ano de defesa: 2018
• Autor(a) principal: Ricardo, Guilherme Iecker
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal do Rio de Janeiro; Brasil; Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia; Programa de Pós-Graduação em Engenharia de Sistemas e Computação; UFRJ
• Palavras-chave em Português: Wireless Networks; Link Scheduling; Operational Research; CNPQ::ENGENHARIAS
• Link de acesso: http://hdl.handle.net/11422/13016

The popularity of Wireless Sensor Networks (WSN) and Internet of Things (IoT) applications is experiencing an unprecedent increase in the last few years. Along with it, the demand for more efficient and economic Wireless Mesh Networks (WMNs) in terms of resource management. The Link Scheduling problem aims to improve network capacity and the resource usage of WMNs through adopting a smart strategy for wireless links activation. This strategy guarantees the strict communication between network devices, satisfying the adopted Physical Interference Model (PIM) constraints. The current work offers an approach to find the optimal scheduling by modeling the Link Scheduling problem as a Fractional Edge-Coloring problem. A Linear Programming (LP) formulation with exponential complexity on the graph size and an algorithm to aid efficiently building such models are introduced. Finally, a considerable amount of experiments were run in order to assess the technique’s practical applicability and performance.