CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Nesta dissertaÃÃo, nosso principal objetivo foi desenvolver uma tÃcnica de resoluÃÃo para um problema na Ãrea de telecomunicaÃÃes. O problema em questÃo à chamado de problema de PonderaÃÃo de Rodadas (PR) e foi inicialmente proposto em [Klasing,Morales,Perennes, 2008]. O contexto do problema envolve uma rede sem fio, onde as comunicaÃÃes sÃo realizadas via ondas de rÃdio e a rede funciona atravÃs de uma operaÃÃo da rede que satisfaz certas restriÃÃes.
Inicialmente, explicamos como à formada uma rede de rÃdio e descrevemos a forma de operaÃÃo da rede de rÃdio junto Ãs restriÃÃes usando um modelo matemÃtico. Em seguida, formalizamos o problema PR como um problema de otimizaÃÃo, especificando suas restriÃÃes, correspondente à geraÃÃo do conjunto de possÃveis operaÃÃes da rede, e critÃrio de otimizaÃÃo, referente ao uso dos recursos da rede. Posteriormente, mostramos um estudo preliminar do problema de ColoraÃÃo FracionÃria (CF) e apresentamos uma tÃcnica de resoluÃÃo deste problema atravÃs do uso de uma heurÃstica lagrangeana baseada em uma relaxaÃÃo lagrangeana de uma formulaÃÃo de programaÃÃo inteira do problema. Essa tÃcnica de resoluÃÃo à entÃo adaptada para o problema PR, consistindo na principal contribuiÃÃo de nossa pesquisa. Por fim, mostramos os resultados computacionais e anÃlises das nossas implementaÃÃes para os problemas CF e PR. / In this dissertation, our main objective was to develop a technique for resolution to a problem
in the area of telecommunications. The problem in question is called Round Weighting
Problem (RWP) and was originally proposed in (KLASING; MORALES; PeRENNES,
2008). The context of the problem involves a wireless network where communications are
performed by radio waves and the network operates through a network operation that
satises the constraints of the problem. Initially, we explain how a radio network is formed
and describe the mode of operation of the radio network with restrictions using a
mathematical model. Then, we formalize the RWP as an optimization problem, specifying
their restrictions, corresponding to the generation of the set of possible network operations,
and optimization criterion, regarding the use of network resources. Subsequently, we
show a preliminary study of the Fractional Coloring problem (FC problem) and present
a technique to solve this problem through the use of a lagrangian heuristic based on a
lagrangian relaxation of an integer programming formulation of the problem. This resolution
technique is then adapted to the RWP, consisting in the main contribution of our
research. Finally, we show the computational results and analyzes of our implementations
for the Fractional Coloring problem and RWP.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7898 |
| Date | 20 February 2014 |
| Creators | Paulo Henrique MacÃdo de AraÃjo |
| Contributors | Ricardo Cordeiro CorrÃa, Rafael Castro de Andrade, PlÃcido RogÃrio Pinheiro |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds