使用分群演算法於自療式通訊網路中進行備用容量配置

Abstract

本研究在於使用分群演算法（Clustering Algorithm）於自療式通訊網路中進行備用容量配置。自療式通訊網路之備用容量配置問題已被歸類為NP Hard問題。隨著網路節點（node）和路段（link）增加，求解的困難度隨之增加。本研究在於先使用分群演算法對整個網路節點和路段依照某些屬性進行分群，形成若干個虛擬節點（virtual node），成為一個虛擬的網路。然後針對此虛擬網路進行備用容量配置計算。因虛擬網路的節點（node）數目和路段（link）數目都已經簡化，意即簡化網路之拓樸型態，故可有效降低複雜度，使計算過程能夠以較為簡單的方式進行，降低處理該類問題之複雜度。虛擬節點所涵蓋之路段數目愈高的自療式通訊網路拓樸型態，使用分群演算法確實能有效的降低計算此種問題的複雜度。

This study employs clustering algorithm to reduce the complexity of self-healing communication network spare capacity allocation problem. The self-healing communication network spare capacity allocation problem is NP-hard, implying exponential growth in execution time with network size increases. By using some attributes of node and link, some nodes of the network can form several “virtual nodes” and the original network can be transferred to a simple one, called “virtual network”. Comparing to the spare capacity allocation problem of original network, the new one of the “virtual network” is easier to solve. If the number of the links which covered by virtual nodes is higher, using clustering algorithm to solving spare capacity allocation problem is more efficiency.