Comparison of Algorithms for the Optimization of Multi-waveform Networks

Environmental factors, including terrain and weather, significantly affect wireless network communication speed. In this research paper, the wireless mesh network topology model [1] was adapted to the wireless tree topology model to solve the thesis paper’s general problem [2]. The model considers a sector connectivity graph to define an antenna direction for each node. Also, we used a single-beam antenna for each sector and modeled signal patterns and interference through an ideal cone shape. We also modeled a mixed-integer linear programming problem to find the most congested link in the network. An iterative local search algorithm was used to solve our problem quickly and effectively with Gurobi software. The proposed algorithm was evaluated using five different problem instances and analyzing a different number of links per sector. The computation showed that the proposed algorithm could find the most congested link in the network in a relatively short time. In addition, the algorithm’s performance is robust even when the number of links per sector increases. However, the resulting network topology had a disconnected link in the network. As a result, the objective value for this network was less than the one we found from model [2]. To generate a fully connected network, we added a constraint to help us reduce the number of links that can have zero direct throughputs. This forced the adapted model to generate a fully connected network topology. We also compared our algorithm with [2] and observed that path loss and fade margin significantly affect solution quality.

Résumé

Les facteurs environnementaux, y compris le terrain et la météo, affectent considérablement la vitesse de communication du réseau sans fil. Dans cet article de recherche, le modèle de topologie de réseau maillé sans fil [1] est adapté au modèle de topologie arborescente sans fil pour résoudre le problème général de l’article de thèse [2]. Le modèle considère un graphe de connectivité de secteur pour définir une direction d’antenne pour chaque noeud. De plus, nous avons utilisé une antenne à faisceau unique pour chaque secteur et modélisé les modèles de signal et les interférences par une forme de cône idéale. Nous avons également modélisé un problème de programmation linéaire en nombres entiers mixtes pour trouver le lien le plus encombré du réseau. Un algorithme de recherche locale itérative est utilisé pour résoudre notre problème rapidement et efficacement avec le logiciel Gurobi. L’algorithme proposé a été évalué en utilisant cinq instances de problème différentes et en analysant un nombre différent de liens par secteur. Le calcul a montré que l’algorithme proposé pouvait trouver le lien le plus encombré du réseau en un temps relativement court. De plus, les performances de l’algorithme sont robustes même lorsque le nombre de liens par secteur augmente. Cependant, la topologie de réseau résultante avait un lien déconnecté dans le réseau. Par conséquent la valeur objectif pour ce réseau devient inférieure au modèle [2]. Pour générer un réseau entièrement connecté, nous avons ajouté une contrainte qui nous aide à réduire le nombre de liens pouvant avoir un débit direct nul. Cela a forcé le modèle adapté à générer une topologie de réseau entièrement connectée. Nous avons également comparé notre algorithme avec [2]. Dans cette comparaison, nous avons observé que la perte de trajet et la marge d’évanouissement affectent de manière significative la qualité de la solution.