Recent advancements in sensory devices are presenting various opportunities for widespread applications of wireless sensor networks (WSNs). The most distinguishing characteristic of a WSN is the fact that its sensors have nite and non-renewable energy resources. Many research e orts aim at developing energy e cient network topology and routing schemes for prolonging the network lifetime. However, we notice that, in the majority of the literature, topology control and routing problems are handled separately, thus overlooking the interrelationships among them. In this dissertation, we consider an integrated topology control and routing problem in WSNs which are unique type of data gathering networks characterized by limited energy resources at the sensor nodes distributed over the network. We suggest an underlying hierarchical topology and routing structure that aims to achieve the most prolonged network lifetime via e cient use of limited energy resources and addressing operational speci cities of WSNs such as communication-computation trade-o , data aggregation, and multi-hop data transfer for better energy e ciency. We develop and examine three di erent objectives and their associated mathematical models that de- ne alternative policies to be employed in each period of a deployment cycle for the purpose of maximizing the number of periods so that the network lifetime is prolonged. On the methodology side, we develop e ective solution approaches that are based on decomposition techniques, heuristics and parallel heuristic algorithms. Furthermore, we devise visualization tools to support our optimization e orts and demonstrate that visualization can be very helpful in solving larger and realistic problems with dynamic nature. This dissertation research provides novel analytical models and solution methodologies for important practical problems in WSNs. The solution algorithms developed herein will also contribute to the generalized mixed-discrete optimization problem, especially for the problems with similar characteristics.

This dissertation investigates in which conditions the optimal configuration of an electric power network is a minimum length spanning tree, and in which conditions it is shortest path tree configuration. For this purpose the dissertation, it applies computational optimization mathematical models of an optimal local access network design problem. The focus of the study is the 13.8 kV spacer cable primary radial networks. Applied models seek for the balance betweenfixedcostsandvariablecosts.Savedvaluesfromanoptimalnetworkcouldbeapplied to increase the range of the network and people reached as well. The bibliographic research is compound by three parts: graph theory, local access network optimization models, and distribution network costs. Research methodology includes the choice of the distribution system, determination of fixed and variable costs, choice and implementation of the local access network optimization models, tests in hypothetical and realistic systems by using the CPLEX solver, analysis of the resulting configuration, and construction of graphics to facilitate the results evaluation. It was found that the relationship between fixed costs and variable costs influences the optimal configuration of the distribution network in such a way that a low value of the quotient between fixed costs and variable costs contributes to a shortest path tree. On the other hand, a high quotient between fixed costs and variable costs contributes to a minimum length spanning tree configuration. However, others parameters must be considered to determine the network configuration such as extension, arches demand and quantity of arches. / O presente trabalho visa investigar sob quais condições a configuração ótima de uma rede de distribuição elétrica é uma árvore geradora mínima (AGM) e sob quais é uma árvore de caminhos mínimos (ACM). Utilizando, para isso, modelos matemáticos computacionais de otimização topológica de redes de utilidade pública. As redes de distribuição estudadas foram do tipo aérea radial primária protegida (ARPP) com nível de tensão em 13,8 kV. Os modelos utilizados prezam pelo equilíbrio entre o custo de investimento inicial (fixo) e os custos decorrentes da transferência de energia elétrica (variável). Os valores economizados através de uma configuração ótima da rede podem ser convertidos em investimentos para aumentar o número de pessoas com acesso aos recursos energéticos com eficiência e qualidade. A revisão bibliográfica foi dividida em três partes: teoria dos grafos, modelos de otimização de redes de acesso local e custos de redes de distribuição. A metodologia utilizada compreendeu as seguintes etapas: escolha do tipo de sistema de distribuição, determinação dos custos fixo e variável, escolha e implementação (GAMS) dos modelos, testes com exemplos de redes usando o solver CPLEX, análise das configurações resultantes e elaboração de gráficos para facilitar a avaliação dos resultados. Os resultados mostraram que a relação entre o custo fixo β e o custo variável γ exerce influência determinante na configuração ótima de uma rede de distribuição ARPP. Um valor baixo de β/γ, favorece a ACM. Já valores elevados de β/γ, conduzem a solução para uma AGM. No entanto, essa relação não é o único fator que determina a configuração da rede, outros parâmetros como extensão, demanda dos nós e quantidade de possíveis arcos influenciam de forma significativa na solução apresentada.