TEORIA DOSJOGOSAPLICADA A PROBLEMAS DECOMUNICAÇÕES MÓVEIS CamilaMariaGabrielGussen DissertaçãodeMestradoapresentadaaoPrograma de Pós-graduação em Engenharia Elétrica, COPPE, da Universidade Federal do Rio de Janeiro, como parte dos requisitos necessários à obtenção do título de Mestre em Engenharia Elétrica. Orientador:PauloSergio RamirezDiniz RiodeJaneiro Janeiro de2012 TEORIA DOSJOGOSAPLICADA A PROBLEMAS DECOMUNICAÇÕES MÓVEIS CamilaMariaGabrielGussen DISSERTAÇÃO SUBMETIDA AO CORPO DOCENTE DO INSTITUTO ALBERTO LUIZCOIMBRADEPÓS-GRADUAÇÃOEPESQUISADEENGENHARIA(COPPE) DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM ENGENHARIA ELÉTRICA. Examinadapor: Prof. PauloSergio RamirezDiniz,Ph.D. Prof. Sergio LimaNetto,Ph.D. Prof. JoséAntonioApolinárioJr.,D.Sc. RIO DEJANEIRO, RJ – BRASIL JANEIRO DE 2012 Gussen,CamilaMariaGabriel Teoria dos Jogos Aplicada a Problemas de Comunicações Móveis/Camila Maria Gabriel Gussen. – Rio de Janeiro: UFRJ/COPPE, 2012. XV, 99 p.:il.;29,7cm. Orientador: PauloSergio Ramirez Diniz Dissertação (mestrado) – UFRJ/COPPE/Programa de EngenhariaElétrica,2012. Referências Bibliográficas: p. 47– 49. 1. Teoria dos jogos. 2. Comunicações Móveis. 3. Equilíbrio de Wardrop. 4. Stackelberg Game. 5. Small- cells. 6. Femtocells. I. Diniz, Paulo Sergio Ramirez. II. UniversidadeFederaldoRiodeJaneiro,COPPE, Programade EngenhariaElétrica. III. Título. iii À minhafamília. iv Agradecimentos “Nós somoso quepensamos. Tudoquesomossurgecom nossospensamentos. Com nossospensamentosnósfazemoso mundo.” Buda AgradeçoaDeuspordealgumaformatermedadoasoportunidadesnecessárias para queeu conseguisseatingirefinalizarmaisumaetapadaminha vida. Agradeço muitoameuspais,VeraJoanaeJoséAlberto,porterem meproporcionado uma excelente formação pessoal e educacional. Agradeço também a eles por sempre estarem comigo em todos os momentos da minha vida. Agradeço à minha irmã Clarissa porsersempreminhaamigaepormeentender(ou tentar!) nas diversassituações. Agradeço especialmente à minha avó Angelina e à minha tia Tici por sempre me apoiarem em todos os momentos. Agradeço também a todos os meus familiares que sempretorceram pormim! Agradeço ao meu namorado, Reinaldo, pela compreensão e pelo apoio em todos os momentoseporestarsempredo meulado. Agradeço ao meu orientador Paulo Diniz por ter me orientado neste trabalho fora de sua área de pesquisa, e também por ter possibilitado a realização do meu sonho de morarfora do Brasil. Mesmomuitoatarefado, sempreestavadisponívelpara me auxiliar no trabalho! E também por ser um exemplo a ser seguido de realização profissional e pessoal. Agradeço ao meu orientador na França, prof. Mérouane Debbah por ter me aceito para trabalhar em seu grupo e também por ter me proporcionado a ida a um congresso internacional. Agradeço à Elena Veronica Belmega que me co-orientou nestes três meses que eu passei no Supélec. Agradeço também a todo o apoio e atenção tanto durante quanto depoisdotrabalho. Comcertezaotrabalhofeitonãoseriaomesmosemasuaorientação! Agradeço a todos os professores que tive, tanto no mestrado, quanto na graduação e no colégio. É com o conhecimento ensinado por eles que consegui finalizar mais uma etapa! Agradeço aos professores Sergio LimaNettoe JoséApolinárioporterem participado deminhabancademestrado. v AgradeçoaosalunosefuncionáriosdoLaboratóriodeProcessamentodeSinaispelos momentosdedescontração! Agradeço tambématodas aspessoas queconhecino Supélec. Foram elas quecontri- buírampara a minhaestadaem Paris sermaravilhosa! Em especial gostariade agradecer aoprofessorRauldeLacerdaporsuascaronasdiáriaseportodaasuaajudanesteperíodo. Agradeço à CAPES e à FAPERJ pelos dois anos de bolsa de mestrado e também a AlcatelLucent pelosuportefinanceiro duranteaminhaestadano Supélec. Enfim,gostariadeagradeceratodosquecontribuíramnaminhavida. Espero queconsigadeixarumacontribuiçãoaindamaiorpara asociedade. vi Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitos necessáriospara aobtençãodo grau deMestreem Ciências (M.Sc.) TEORIA DOSJOGOSAPLICADA A PROBLEMAS DECOMUNICAÇÕES MÓVEIS CamilaMariaGabrielGussen Janeiro/2012 Orientador:PauloSergio Ramirez Diniz Programa: EngenhariaElétrica Esta dissertação tem como objetivo aplicar teoria dos jogos a problemas de comuni- caçõesmóveis. Nestetrabalho,algunsdosmaisimportantesconceitosdeteoriadosjogos são apresentados. As formas de representação de um jogo são descritas e exemplifica- das, assim como algumas das classificações mais utilizadas na literatura. Os principais conceitosdesolução,equilíbriodeNash eequilíbriodeWardrop, são descritos. Nestetrabalhoéresolvidotambémumjogosobreadisputaderecursosdisponíveisde um usuário que está no estado idle. Neste jogo, existem usuários que estão transmitindo comumataxadetransmissãoabaixodanecessáriaeumusuáriocomrecursosdisponíveis para auxiliarestes outros. Para este problema, são apresentadas simulações para analisar oganhodecapacidade. É estudada também uma rede em que o operador implanta tecnologias heterogêneas comoporexemplomacro-cell,small-cellefemto-cell. Baseadonestastecnologias,oope- radorpodeproverpara osconsumidoresdiferentestiposdeserviços. Para esteproblema, éformalizadaaalocaçãoconjuntadospreçosedasbandascomoumjogodeStackelberg. Éanalisadatambémasoluçãodojogocorrespondente,tantomatematicamentecomoatra- vés desimulaçõesnuméricas. Observa-sequepara provermelhoresserviços eobteruma maiorreceita,recursos(comobanda)devemseralocadosparaassmall-cellsefemtocells. Além disto, mudando o preço e a alocação das bandas, o operador pode manipular a demandado sistemanopontodeequilíbrioem operação. vii Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of the requirementsforthedegreeofMasterofScience(M.Sc.) GAMETHEORYAPPLIED TO WIRELESS COMMUNICATIONSPROBLEMS CamilaMariaGabrielGussen January/2012 Advisor:Paulo Sergio RamirezDiniz Department: ElectricalEngineering Theobjectiveofthisworkistoapplygametheoryforwirelesscommunicationsprob- lems. Here the main concepts of game theory are presented. Representation of games as well as some types of games are described and examples are given. The main con- cepts related to the solutions are described; namely: Nash equilibrium and the Wardrop Equilibrium. In this work, we also solve a resource allocation game. In this game, some users are transmitting with lower rate than the necessary; and a user, that is in idle state, has availableresourcestohelptheothers. Inthisproblem,wepresentsomenumericalresults toanalysethecapacity gain. We also study a multi-tier network where an operator deploys heterogeneous tech- nologies, e.g., composed of macrocells, small-cells and femtocells. Based on these tech- nologies,theoperatorcanprovidetoitscustomersseveral typesofservices. Weformalize thejointpricingandbandwidthallocationproblemasaStackelberggame. Weanalysethe solutionofthecorrespondinggame,both,mathematicallyandvianumericalsimulations. We observe that, in order to provide enhanced services leading to higher revenue, some network resources (e.g., bandwidth)must be allocated to the small-cells and femto-cells. Furthermore, by tuning the pricing and the bandwidth allocation policy, the operator can manipulatethesystemloadsat theequilibriumoperatingpoint. viii Sumário Listade Figuras xii Listade Tabelas xv 1 Introdução 1 1.1 TrabalhosRelacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Principais Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Teoria dos Jogos 5 2.1 TeoriadosJogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.1 Representações dosjogos . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Tiposdos jogos . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 TiposdeEstratégias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 EstratégiaPura . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.2 EstratégiaMista . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 TiposdeEquilíbrio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 EquilíbriodeNash . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.2 EquilíbriodeWardrop . . . . . . . . . . . . . . . . . . . . . . . 15 2.5 ExemplodeJogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Problema de Alocaçãode Potência 21 3.1 Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Modelo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2.1 Problemadeteoriadosjogos . . . . . . . . . . . . . . . . . . . . 24 3.2.2 Problemadeotimização . . . . . . . . . . . . . . . . . . . . . . 25 3.2.3 Solução doProblemadeTeoriadosJogos . . . . . . . . . . . . . 25 3.2.4 Considerações Gerais . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2.5 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 ix 4 Economia das Femtocells 36 4.1 AspectosEconômicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.1.1 Problemadeotimização . . . . . . . . . . . . . . . . . . . . . . 37 4.1.2 ProblemadeTeoriadosJogos . . . . . . . . . . . . . . . . . . . 37 4.2 ResultadosNuméricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5 Atribuição de Preços a Serviços de uma RedeHeterogênea 40 5.1 Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 ResultadosNuméricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6 Problema de AlocaçãoConjunta de Banda ePreços 43 6.1 Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6.2 ResultadosNuméricos . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 7 Conclusões eTrabalhos Futuros 45 7.1 TrabalhosFuturos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Referências Bibliográficas 47 A Economics ofFemtocells 50 A.1 Economicaspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 A.1.1 Optimizationproblem . . . . . . . . . . . . . . . . . . . . . . . 51 A.1.2 GameTheoryproblem . . . . . . . . . . . . . . . . . . . . . . . 51 A.2 Communicationsaspects . . . . . . . . . . . . . . . . . . . . . . . . . . 53 A.2.1 Theutilityfunctions . . . . . . . . . . . . . . . . . . . . . . . . 53 A.2.2 TheMacrocell Throughput . . . . . . . . . . . . . . . . . . . . . 54 A.3 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 B Pricing ina Multiple-Service Heterogeneous Network 70 B.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 B.2 Case 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 B.2.1 ProofoftheExistenceoftheThresholdsattheWardropEquilibrium 72 B.2.2 FindingtheThresholdsat theWardrop Equilibrium . . . . . . . . 75 B.3 Case 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 B.3.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 B.4 Specific Case: Three AvailableServices . . . . . . . . . . . . . . . . . . 77 B.4.1 Modelofthethroughputfunctions . . . . . . . . . . . . . . . . . 77 B.4.2 NumericalResults . . . . . . . . . . . . . . . . . . . . . . . . . 80 C JointPricing and Bandwidth AllocationProblem 93 C.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 x