一個在無基礎行動網路上之網格式螞蟻路由演算法

Abstract

無基礎行動網路(mobile ad hoc networks)為一群行動主機所自行組成(self-organized)的無線網路，其優點就是不需要透過基礎設備(infrastructure)的支援，由於無基礎行動網路的特點與傳統有線網路特點不同，如：移動性(mobility)，多點跳躍(multi-hop)等，因此，許多學者紛紛針對無基礎行動網路提出路由演算法(routing algorithm)。對於解決路由上的一些問題，也因此有各種不同類別的路由方法被探討，螞蟻路由演算法(ant routing)利用群體智慧(swarm-intelligence)找尋路徑，而且同時能夠找到多條備援路徑，但是，螞蟻路由演算法會因為行動主機數目愈來愈多情況下，而導致路由演算法效率降低，因此本論文以GRID為概念，融入螞蟻演算法中，讓螞蟻是採用網格對網格(grid-by-grid)方式傳輸，改善螞蟻路由演算法在行動主機數目愈來愈多情況下的效率(Efficiency)與效能(Performance)。經過模擬分析後，證實在大規模無基礎行動網路下，GARA能夠獲得與ARAMA一樣高的封包到達率，而對於路由成本與資料成本的付出，只需要負擔大約60%的成本支出。

Mobile ad hoc network (MANET) can be self-organized by some mobile nodes. Its advantage is capable of operating without the support of any infrastructure. Because MANET’s features is different to conventional wired networks, such as mobility, multi-hop, there are more and more new routing protocols proposed. For some routing problems, there are some routing algorithms being discussed. Ant routing use Swarm-Intelligence for route discovery and also have multi-paths for backup and balance. However, the efficiency of ant routing can more and more go down in large-scale mobile ad hoc networks. For solving such condition, improving the efficiency of ant routing, this research proposes the algorithm that combines both the GRID and ant routing, called grid-based ant routing algorithm (GARA). GARA can improve efficiency of ant routing in large-scale mobile ad hoc networks. With simulating, the fact is proved that GARA can achieve high delivery rate the same as ARAMA, but reduce forty percentage of cost less than ARAMA. So GARA outperforms ARAMA on Routing Cost and Data Cost.