A New Bidirectional Research Chord Method Based on Bacterial Foraging Algorithm

Hang Li ； Lin Teng ； Shoulin Yin

《電腦學刊》 29卷3期 (2018/06) Pp. 210-219

https://doi.org/10.3966/199115992018062903020

摘要

In order to improve mismatching problem between physical topology and the logical topology in traditional Chord, and improve low search efficiency produced by space complexity, we propose a new bidirectional research Chord method based on bacterial foraging algorithm, which combines the advantage of bidirectional research method and bacterial foraging algorithm. This new algorithm regards topology matching problem as one traveling salesman problem, because bacterial foraging algorithm can get optimal solution for TSP, then we use the optimal solution to construct Chord ring, which can solve the mismatching problem. On this basis, we use the bidirectional search method to further accelerate the search speed. The experimental results show that the new algorithm has better performance than the traditional Chord algorithm on the aspect of query path length and finding the hop number. We also make comparison to other latest algorithms with the new method.

關鍵字

bacterial foraging algorithm ； bidirectional research ； chord method ； physical topology ； traveling salesman problem