Thesis (M.S.)--State University of New York at Binghamton, Dept. of Electrical & Computer Engineering, 2006. / Includes bibliographical references.

On April 27, 1802, I gave a shout of joy ... It was seven years ago I proposed to myself a problem which I have not been able to solve directly, but for which I had found by chance a solution, and I knew that it was correct, without being able to prove it. The matter often returned to my mind and I had sought twenty times unsuccessfully for this solution. For some days I had carried the idea about with me continually. At last, I do not know how, I found it, together with a large number of curious and new considerations concerning the theory of probability. Andre Marie Ampere. Facility location problems (or plant location problems) are general models that can be used when a set of clients has to be served by facilities. More precisely, we are given a set of potential facility locations and a set of clients. The optimization problem is to select a subset of the locations at which to place facilities and then to assign clients to theses facilities so as to minimize total cost. Most formulations considered in this thesis can be viewed as general models that can be applied to a wide range of context and practical situations. However, as this research has been partly initiated by the interest of the author in telecommunication network design we will introduce these models by considering problems in this particular area. In the context of telecommunication network design an application of discrete location theory is the optimization of access networks with concentrators. Typically, we have a number of terminal points that must be connected to a service point. An obvious solution is to use a dedicated link for each terminal (star network). However, it is clear that this solution can be very expensive when the number of terminals is large and when they are far from the service point. Access networks are often constructed by inserting concentrators between the terminals and the service point. Many terminals are connected to a facility which in turn is connected by a single link to the service point. The objective is to build a network that will provide the service at minimum cost. If no extra constraints are involved the mmimum cost network problem can be expressed as an uncapacitated facility location problem (UFL). If the number of terminals that can be connected to a concentrator is limited we obtain a so-called capacitated facility location problem (CFL). CFL can be extended to consider various types of concentrators with various capacities. This problem is the multi-capacitated facility location problem (MCFL). MCFL is a straightforward model for low speed packet switched data networks typical among which are networks connecting sellingpoint terminals to a database. For other networks, the problem may involve various traffic constraints. In chapter 1 we present those problems and compare solutions obtained by Lagrangian relaxation and simulated annealing algorithms. The architecture mentioned above can be extended with more than one hierarchical level of concentrator. Unfortunately, we pay for this cost saving through a decrease of reliability. Therefore, the number of levels is often limited to one or two. In chapter 2 we study an extension of UFL and CFL to two levels of concentrators. Obviously, the structure of a network changes according to the way requirements vary with time. In order to plan investments and to develop strategies, the evolution of a network has to be determined for several years ahead (typically four or five years). In this case the main questions to answer are: Where and when to establish concentrators and of what size? In chapter 3 we study this problem for the dynamic version of UFL. Now, with the network optimization problem, there naturally arises the problem of allocating the total minimum cost among customers fairly. Namely, we would like to allocate the cost in such a way that no subgroup of users would have incentive to withdraw and build their own network. The standard way to approach such a problem is by the means of cooperative game theory. In chapter 4 we study the core of location games derived from UFL and CFL, and in chapter 5 we propose methods to compute the nucleolus of these games.

Thesis (Ph. D.)--School of Computing and Engineering. University of Missouri--Kansas City, 2006. / "A dissertation in computer networking and telecommunication networking." Advisor: Deep Medhi. Typescript. Vita. Title from "catalog record" of the print edition Description based on contents viewed Oct. 31, 2007. Includes bibliographical references (leaves 168-172). Online version of the print edition.

In a dynamic, high-growth, highly competitive service environment, a service provider's ability to meet increasing demands for efficiency of network resource allocation, productivity and reliability when provisioning services for customers depends on having up-to-date network inventory information available. An accurate resource inventory management system allows a service provider to improve the control and understanding of its communications infrastructure, expedite the management of customer orders and automate the provisioning of services. The basic goal and final result of presented work is the information system developed for the purposes of network inventory management and accounting tasks which is capable to meet the requirements of “Lietuvos Telekomas”. Presented work covers: · analysis and specification of requirements of “Lietuvos Telekomas” for information system being developed; · analysis and evaluation of some generic conceptual cooperative work models for the purpose to make right decision on data model of IS; · analysis of basic telecommunication services, definition of data structures for the services that are to be modelled; · analysis and specification of those business processes of “Lietuvos Telekomas” that directly involve use of network resources; · analysis of generic functional architecture of transport networks, described in ITU-T recommendation G.805; · introduce of simplified (Black box) transport network model based on physical view to the... [to full text]

Power transmission grid infrastructures deliver electricity across large distance and are vital to the functioning of modern society. Increasingly these setups embody highly-coupled cyber-physical systems where advanced telecommunications networks are used to send status and control information to operate power transmission grid components, i.e., "smart grids". However, due to the high inter-dependency between the communication and power grid network layers, failure events can lead to further loss of control of key grid components, i.e., even if they are undamaged. In turn, such dependencies can exacerbate cascading failures and lead to larger electricity blackouts, particularly under disaster conditions. As a result, a range of studies have looked at modelling failures in interdependent smart grids. However most of these designs have not considered the use of proactive network-level survivability schemes. Indeed, these strategies can help maintain vital control connectivity during failures and potentially lead to reduced outages. Hence this thesis addresses this critical area and applies connection protection methodologies to reduce communication/control disruption in transmission grids. The performance of these schemes is then analyzed using detailed simulation for a sample IEEE transmission grid. Overall findings show a good reduction in the number of overloaded transmission lines when applying network-level recovery schemes.

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal's attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately. To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm. It was found that valid cuts generated using the analytic center cutting plane method reduce the number of times the integer Benders master problem is solved and therefore reduce the computational time. It was also found that the combinatorial Benders reduces the complexity of the integer master problem by reducing the number of integer variables in it. The valid cuts generated within the nested Benders algorithm proved to be beneficial in reducing the number of times the combinatorial Benders master problem is solved and in reducing the computational time that the overall algorithm takes. Over 110 instances of the UMTS/W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality.

Network planning is an essential phase in successfully operating state-of-the-art telecommunication systems. It helps carriers increase revenues by deploying the right technologies in a cost effective manner. More importantly, through the network planning phase, carriers determine the capital needed to build the network as well as the competitive pricing for the offered services. Through this phase, radio tower locations are selected from a pool of candidate locations so as to maximize the net revenue acquired from servicing a number of subscribers. In the Universal Mobile Telecommunication System (UMTS) which is based on the Wideband Code Division Multiple Access scheme (W-CDMA), the coverage area of each tower, called a cell, is not only affected by the signal's attenuation but is also affected by the assignment of the users to the towers. As the number of users in the system increases, interference levels increase and cell sizes decrease. This complicates the network planning problem since the capacity and coverage problems cannot be solved separately. To identify the optimal base station locations, traffic intensity and potential locations are determined in advance, then locations of base stations are chosen so as to satisfy minimum geographical coverage and minimum quality of service levels imposed by licensing agencies. This is implemented through two types of power control mechanisms. The power based power control mechanism, which is often discussed in literature, controls the power of the transmitted signal so that the power at the receiver exceeds a given threshold. On the other hand, the signal-to-interference ratio (SIR) based power control mechanism controls the power of the transmitted signal so that the ratio of the power of the received signal over the power of the interfering signals exceeds a given threshold. Solving the SIR based UMTS/W-CDMA network planning problem helps network providers in designing efficient and cost effective network infrastructure. In contrast to the power based UMTS/W-CDMA network planning problem, the solution of the SIR based model results in higher profits. In SIR based models, the power of the transmitted signals is decreased which lowers the interference and therefore increases the capacity of the overall network. Even though the SIR based power control mechanism is more efficient than the power based power control mechanism, it has a more complex implementation which has gained less attention in the network planning literature. In this thesis, a non-linear mixed integer problem that models the SIR based power control system is presented. The non-linear constraints are reformulated using linear expressions and the problem is exactly solved using a Benders decomposition approach. To overcome the computational difficulties faced by Benders decomposition, two novel extensions are presented. The first extension uses the analytic center cutting plane method for the Benders master problem, in an attempt to reduce the number of times the integer Benders master problem is solved. Additionally, we describe a heuristic that uses the analytic center properties to find feasible solutions for mixed integer problems. The second extension introduces a combinatorial Benders decomposition algorithm. This algorithm may be used for solving mixed integer problems with binary variables. In contrast to the classical Benders decomposition algorithm where the master problem is a mixed integer problem and the subproblem is a linear problem, this algorithm decomposes the problem into a mixed integer master problem and a mixed integer subproblem. The subproblem is then decomposed using classical Benders decomposition, leading to a nested Benders algorithm. Valid cuts are generated at the classical Benders subproblem and are added to the combinatorial Benders master problem to enhance the performance of the algorithm. It was found that valid cuts generated using the analytic center cutting plane method reduce the number of times the integer Benders master problem is solved and therefore reduce the computational time. It was also found that the combinatorial Benders reduces the complexity of the integer master problem by reducing the number of integer variables in it. The valid cuts generated within the nested Benders algorithm proved to be beneficial in reducing the number of times the combinatorial Benders master problem is solved and in reducing the computational time that the overall algorithm takes. Over 110 instances of the UMTS/W-CDMA network planning problem ranging from 20 demand points and 10 base stations to 140 demand points and 30 base stations are solved to optimality.

The Project “Resources evaluation system of SDH telecommunication network” is used for investigation of the efficiency of utilization of the existing TEO LT, AB SDH Trunk Network resources. The essential problem is the lack of precise information on the free and used resources of the Network, their distribution and usage in the optimum and efficient manner. It was rather hard to establish the free and used SDH network resources and evaluate the efficiency of the Network. This brings essential influence and difficulties into the planning of network and investments since it is rather hard to take the economically viable decisions regarding the usage of the existing resources. The SDH network resources evaluation system can be used for planning of trunk network resources and quick creation of flows’ transmission routes in a very efficient manner. The System gives the possibility to verify the new routes creation possibilities from any point of the network and execute the customers’ orders in a quick manner. The System is developed as software with a direct interface with the TEO LT Network Information System SQL Base, and is going to use the data, stored in the SQL Base. The Content of this project consists from: • Analytical part of investigation • Specification of requirements for designed system • Common system requirements • Data structure • Network Resources Information Module • Testing and User Guide According content above the System “Resources evaluation system of SDH... [to full text]

L'objectif de cette thèse est de réunir les deux approches suivantes qui existent actuellement pour étudier une foule: ou bien à temps fixé on s'intéresse à la distribution spatiale des individus, ou bien on suit un seul individu à la fois au cours du temps. On se propose de construire des processus spatio-temporels, qui, comme leur nom l'indique, permettraient de rendre compte du caractère aléatoire des usages d'une foule dans un réseau de télécommunication, à la fois du point de vue spatial (modèles de route) et du point de vue temporel (déplacements sur ces routes, usages qui varient au cours de ces déplacements…). Une fois ces processus construits de manière rigoureuse, on étudie leur comportement d'une manière fine. Nous développons trois modèles différents qui chacun mènent à des formules analytiques fermées, ce qui permet de les utiliser d'une manière très confortable à des fins de dimensionnement. / This thesis consists in joining two approaches that currently exist when one wants to study crowds phenomena: either taking a snapshot by freezing time to study the spatial repartition of the individuals, or following one given individual over time.We build space-time processes that let us model random phenomena in a crowd, being on a spatial level (roads models) or a time level (movings on these roads, space-dependent behaviors…). Once we have built them in a rigorous manner, we study their properties, which let us obtain analytical closed formulas that can be widely used for dimensioning purposes.

Devido à tendência mundial de crescimento sem precedentes na história das telecomunicações, verifica-se atualmente um aumento crescente no segmento das redes de comunicações com respeito ao seu tamanho e em seus correspondentes elementos, tornando o seu gerenciamento uma atividade árdua e complexa do ponto de vista de sua operação. Adicione-se a isto o fato de que o sucesso no empreendimento dos diferentes negócios atuais, no contexto da utilização das redes de comunicações, é dependente exclusivamente da qualidade do serviço e funcionamento dessas redes. A ocorrência de falhas em qualquer sistema de comunicação é de certa forma inevitável e, portanto, mais críticos em sistemas de grande porte, seja em termos de quantidade e variedade de falhas. Dessa forma, é desejável que sejam desenvolvidas novas técnicas que permitam à rede de comunicação uma maior rapidez e eficiência na detecção e correção de operações sistêmicas anormais e, consequentemente, sejam consideradas como atributos prioritários em seu projeto. Em outras palavras, a implementação destas novas técnicas permitirá ao sistema a capacidade de detecção, isolação e reconfiguração de um dado componente falho com referência aos requisitos de maior rapidez e eficiência, aumentando sobremaneira a disponibilidade da rede. Neste trabalho de dissertação é proposto um algoritmo e uma arquitetura para o gerenciamento de falhas, além de verificar a sua aderência quanto ao requisito disponibilidade de rede. / Due to the unprecedented world growth trend in the telecommunications history, it is currently realized the enormous increase in the communication networks segment regarding in the size and in its correspondent elements as well, becoming its own management an arduous and complex activity in the operation point of view consideration. Also, it must be taken into account that the real success concerning the currently and different business enterprise in the communications networks usage context are exclusively dependant on the quality of the service and the correct working of these networks. The fault occurrence in any communication system is generally inevitable and therefore more critical when considering large systems configuration, in terms of number and variety of faults. In this way, it is desirable that new techniques be developed, allowing the communication networks the ability to handle faster and more efficiency the detection and correction in case of anormal systemic operations. Therefore, it must be considered as a priority attribute in the new networks design. In other words, the implementation of these new techniques will allow the systems to have the capacity to detect, isolate and reconfigure a given fault component, regarding the quickness and efficiency attribute, increasing the network availability. It is proposed in this dissertation, an algorithm and an architecture for fault management and how they are adhered to the network availability.