Search of the Shortest Path in a Communication Network with Fuzzy Cost Functions

Symmetry

Sira M. Allende¹  Alfonso Ariza²  Gonzalo Joya²  Alicia Triviño²  Lissette Valdés² 

[1] Applied Mathematics Department, Mathematics and Computer Science Faculty, Havana University, Havana 10200, Cuba;Electronic Technology Department, ETSI Telecommunication, Málaga University, 29071 Málaga, Spain;

关键词: routing;    type-V fuzzy graph;    communication network;    Dijkstra algorithm;    triangular fuzzy number;    shortest path;   

DOI  :  10.3390/sym13081534

来源: DOAJ

【 摘 要 】

A communication network management system takes the measurements of its state variables at specific instants of time, considering them constant in the interval between two consecutive measurements. Nevertheless, this assumption is not true, since these variables evolve in real time. Therefore, uncertainty is inherent in the processing of the measurements during the intervals so that they cannot be efficiently managed using crisp variables. In this paper, we face this problem by modeling the communications network as a type-V fuzzy graph, where both the nodes and the links are described with precision, but the cost of each link is modeled as a triangular fuzzy number. Different fuzzy cost allocation functions and fuzzy optimization strategies are described and applied to the search for the shortest path between two nodes. An experimental study has been conducted using two representative networks: the backbone network of Nippon Telegraph and Telephone Corporation (NTT) and the National Science Foundation’s Network (NFSNET). In these networks, our fuzzy cost functions and strategies have been compared with the well-known crisp equivalents. The optimal search strategies are based on the proposed Fuzzy Dijkstra Algorithm (FDA), which is described deeply. The simulation results demonstrate that in all cases the fuzzy alternatives surpass or equal the crisp equivalents with statistically significant values. Specifically, the so-called Strategy 8 presents the best throughput, as it significantly exceeds the performance of all those evaluated, achieving a Global Mean Delivery Rate (GMDR) close to 1.

【 授权许可】

Unknown