The Steiner Tree Problem and its Application in Point-to-Multipoint Networks

Abstract

Point-to-Multipoint communication is an efficient method of data transmission that has revolutionized the way information is broadcasted to various receivers. This type of communication involves a single transmitter that disseminates data to multiple receivers over a shared network. It has a wide range of applications in the field of telecommunications, such as cellular networks, cable TV distribution, industrial and Internet of Things sectors, or even satellite communications. Given its importance nowadays, one of the most critical aspects to consider when planning the development and deployment of a Point-to-Multipoint network is to do so at the minimum possible cost. However, this often represents a challenge due to certain constraints that may exist, such as distance or budget limitations. The formulation of the Steiner Tree Problem proves to be an excellent approach to face this difficulty. Its focus lies on finding the most cost-effective connection between a set of desired points in a network. This connection can include additional points that are not a part of the set, as long as their inclusion contributes to cost reduction. For smaller and less complex networks, it is possible to obtain the minimum cost solution with an exact algorithm within reasonable time. However, given its NP-Hard nature this proves to be quite challenging for more complex networks. For this reason, many researchers have shifted their attention to the development of heuristic methods capable of determining a suboptimal solution, or even the optimal solution, in acceptable time. This dissertation presents a mathematical formulation of the Steiner Tree Problem along with some useful base algorithms which assist in addressing this problem. Additionally, it describes a heuristic method, proposed by Takahashi and Matsuyama, that enables the acquisition of a good initial solution , followed by manipulations performed on this solution and the analysis of the obtained results. The manipulation process is the focus of this work and involves the usage of functions that perform random addition and removal of nodes. It can be applied in the context of a more advanced and specialized heuristic method.

A comunicação Ponto-a-Multiponto é um método eficiente de transmissão de dados que revolucionou a maneira como a informação é disseminada para vários recetores. Este tipo de comunicação pressupõe a existência de um único transmissor que transmite informação para vários recetores através de uma rede partilhada. Tem inúmeras aplicações na área das Telecomunicações, tais como em redes celulares, distribuição de televisão por cabo, setores industriais e Internet das Coisas, e até na comunicação via satélite. Dada a sua importância nos dias atuais, um dos aspetos mais cruciais a ter em conta ao fazer o planeamento de uma rede Ponto-a-Multiponto é conseguir implementar a rede com o menor custo possível. Em muitas ocasiões, existem certos impedimentos, tais como limitações de distância ou de recursos, pelo que esta necessidade se torna desafiante. A formulação do Problema da Árvore de Steiner provou ser uma boa abordagem para enfrentar esta dificuldade. O seu foco está em encontrar a ligação mais barata entre um conjunto de pontos de uma rede. Esta ligação pode conter pontos adicionais que não estão no conjunto inicial, desde que a sua inclusão contribua para a redução do custo total. Para redes de menor dimensão e menos complexas, muitas vezes é possível obter a solução mais barata em tempo útil através do uso de algoritmos exatos. No entanto, dada a natureza NP-Difícil deste problema, torna-se muito desafiante conseguir obter a solução ótima em tempo aceitável para redes de maiores dimensões. Devido a esta razão, muitos investigadores focaram-se no desenvolvimento de métodos heurísticos capazes de obter uma solução subótima, ou mesmo a solução ótima, em tempo útil. Esta dissertação apresenta uma formulação matemática do Problema da Árvore de Steiner juntamente com a apresentação de algoritmos base que auxiliam na resolução deste problema. Adicionalmente, descreve um método heurístico, proposto por Takahashi e Matsuyama, que permite obter uma boa solução inicial, seguido de manipulações feitas nesta solução e análise das soluções obtidas. O processo das manipulações é o foco principal do trabalho e consiste no uso de funções que realizam a adição e remoção aleatória de nós. Este processo pode ser aplicado no contexto de heurísticas mais avançadas e sofisticadas.