以位置為基礎之無線隨意網路路由演算法之研究

Abstract

本論文考慮的問題是如何設計有效率的以位置為基礎的無線隨意網路路由演算 法。當節點在傳送封包時，是依據位置資訊，則路由演算法將被稱為是以位置為 基礎的路由演算法。貪婪法、羅盤法、橢圓法、面路由，是四個有名的以位置為 基礎的路由演算法。其中前三個演算法的執行速度很快，但卻不能保證封包一定 送達。面路由的執行速度不快，但能保證封包一定送達。要開發執行速度非常快、 同時兼具高送達率的演算法，確實是一個很具挑戰性的任務。本論文的目的即在 於提出兩個這樣的演算法。實驗的結果顯示我們的演算法是相當不錯的。

This thesis considers the problem of designing efficient position- based routing algorithms for wireless ad hoc networks. A routing algorithm is position-based if a node forwards its packet according to the position information (i.e., coordinates in the plane). GREEDY, COMPASS, ELLIPSOID, and FACE are four famous position-based routing algorithms. The former three algorithms run very fast but cannot guarantee message delivery. On the other hand, FACE does not run fast but it guarantees message delivery. It is indeed a challenge to develop an algorithm that can run very fast and can have high delivery rate at the same time. The purpose of this thesis is to propose two such algorithms. Experimental results show that our algorithms are quite good.