Ad hoc 無線網路上的有效繞路演算法

Abstract

本論文利用叢集(Cluster)和虛擬骨幹(Virtual backbone)的觀念，在 ad hoc 無線網路上，設計一個有效的繞路演算法。我們首先提出了標貼叢集演算法(Label-Clustering Algorithm)，此演算法法在 O(\V\)時間內將整個網路分成數個叢集，並且所得的叢集個數，在平均上會小於等於已知的叢集演算法，如高連結度叢集演算法(High-Connectivity Clustering Algorithm)；接著，我們在 O(logn)的時間裡，將叢集的管理者(Cluster head)架成一個虛擬骨幹，其中 n 為叢集管理者的個數，而此骨幹的點數最多為3n。最後，藉由此緊緻的虛擬骨幹及良好的資料儲存到有效的繞路。