使用A*演算法在地理方位轉遞時避免Dead End問題

Using A* Algorithm to Avoid Dead End Problem for Geographic Forwarding

張建明(Jian-Ming Chang) ； 徐慶錡(Ching-Chi Hsu) ； 趙涵捷(Han-Chieh Chao) ； 陳俊良(Jiann-Liang Chen)

《網際網路技術學刊》 10卷4期 (2009/08) Pp. 363-368

https://doi.org/10.6138/JIT.2009.10.4.08

摘要

地理方位轉遞法(Geographic Forwarding)是一種以位置為基礎(Position-based)的路由方式。節點利用GPS所得的地理資訊來與其他鄰居做交換，透過所得到的地理位置資訊可以在不用預先知道網路拓樸分佈的情況下去做封包的路由。而貪婪轉遞法(Greedy Forwarding)是地理方位轉遞法的一種，它是依據目前節點的傳輸範圍裡可達到的最遠距離且最靠近目的端的節點做為下一個轉遞點(Relay Node)。這種路由方法的優點是其整體花費很小，可以說幾乎不需要路由表也不用對整個網路做氾濫式的尋路。在網路節點分布均勻的情況下可以保證在最少Hop的情況下將封包傳送到目的端。但是在網路節點分布不均勻以及節點分佈過於鬆散的情況下，則有可能會遇到「Dead End」的問題。Dead End的問題是當轉遞到某個節點時，此節點除了自己本身以外，在他傳輸範圍裡面找不到其他更靠近目的端的節點可以轉遞。當遇到Dead End的問題時，除了有可能發生封包遺失的情況，還必須付出額外的成本去找其他的替代節點。本篇論文提出將MANET分割成許多方格，在方格裡的節點會選舉出一個代理人來代表此方格。再利用一種含有啟發(Heuristic)概念的演算法「A*Algorithm」來找一條參考路徑，使節點能參考這條路徑來做地理方位轉遞。A*演算法結合了Dijkstra's Algorithm與Best-first Search的優點，透過啟發式函數來估計一條參考的路徑後，來源端就可參考這條參考路徑來作地理方位轉遞，以避免遇到Dead End問題。

關鍵字

地理方位轉遞 ； 死結問題 ； 無線行動網路 ； A*演算法

並列摘要

The method geographic forwarding is that node uses its neighbor's location information to forward data packets. Node doesn't need to know the whole network topology but its one hop neighbor's information. Although this method can reduce the size of the routing table and network flooding, it might encounter the situation called ”Dead end” that the relay node can not help the data keep forwarding. We propose to find a prior path before using geographic forwarding. This method first divide the network into several square, and each square have its own ID. Each square will have an agent voted by nodes with the same square ID. The agent will perform A* algorithm to find a reference path to source node, and source node then using geographic forwarding to avoid the dead end situation.

並列關鍵字

Geographic Forwarding ； Dead End ； MANET A* Algorithm