將二度空間路由應用至三度空間之方法與條件

Abstract

地理位址路由是一種非常適合應用於無線隨意網路之路由方法，也在二度空間的環境中有許多深入的研究。然而針對三度空間中的地理位址路由提案卻寥寥無幾。在這篇論文中，我們發展出Slab Routing，利用投影的方式將二度空間的地理路由演算法延伸至三度空間，並保留其原有的短路徑優點。Slab Routing的做法是即時的切割出一個稱作slab的空間，將在其中之點投影至一個平面後擷取平面圖，再執行二度空間的地理路由演算法。雖然Slab Routing的操作方式無法確保所有訊息都可以抵達其目的地，我們推導出一個可以根據網路部署環境預測傳送機率的數學模型，並以實驗驗證之。

Geographic routing, an attractive routing solution for wireless ad hoc networks, has been studied extensively in two-dimensional environments. However, three-dimensional space has proven to be much more challenging, with only a few existing proposals. In this paper, we present Slab Routing - a novel projection based method for adapting two-dimensional geographic face routing techniques to three-dimensional space, avoiding flooding and preserving their route optimality properties. Slab Routing accomplishes this by executing face routing over the planar projected graph of nodes contained within a dynamically created space partition, called a slab. While the adaption does not offer guaranteed delivery, we provide an analysis of the conditions required to achieve a desired delivery probability and verify the results through simulation.