在無線隨意網路中格狀繞境之臨界格子大小及傳輸半徑

Abstract

格狀繞徑法用於無線隨意網路，是一種以地理資訊為基礎的繞徑協定。在格狀繞徑法中，平面被分割成相同大小正方形網格。兩個網格被稱為鄰近網格倘若他們有共同的邊，兩個節點被稱做鄰近節點倘若他們位於鄰近網格且在彼此的傳輸範圍之內。除了最後一次的跳躍外，封包每次被送至一個較目前更為接近內含目的地節點的網格。 作為一個貪婪式的策略，最大的困難與挑戰在於如何克服局部最小點的存在，也就是當目前封包所在的節點，找不到一個鄰近節點比自己更為靠近目的地節點，可以代為繼續傳送封包。本論文主要探討如何藉由適當調整格狀繞徑法中兩個重要的參數—格網大小與傳輸半徑—來保證封包的可到達性。 本文假設節點是依照平均值為n的普瓦松點過程分布在一個單位面積的正方形上，令 l 代表格網大小， r 代表傳輸半徑。若 l=√(("β" lnn)/n) ，首先我們證明"β=1" 為保證封包可到達性下，格網長度最小的臨界值。 換句話說，若"β>1" ，則幾乎可保證不存在局部最小點；若"β<1" ，則幾乎保證會存在局部最小點。其次，在給定任一個大於一之常數"β" ，對於傳輸半徑r，我們找到一個充分條件來保證封包可到達性。最後，我們找出最小的傳輸半徑 r≅2.09√(lnn/n) 對應於 β≅1.092。本文亦討論了自來源到終點之間平均需要跳躍的次數，及每個網格平均交通流量。最後以模擬的方式驗證理論推導值的正確性。

Grid routing is a geographic-based routing protocol for wireless ad hoc networks. In grid routing, the plane is tessellated into equal-sized square cells. Two cells are called neighbor cells if they share a common boundary, and two nodes are called neighbor nodes if they are located in neighboring cells and within each other's transmission range. In each hop excepting the last one, each packet is forwarded to a neighbor node which is in a cell closer to the cell containing the destination node. As a greedy local strategy, nodes using grid routing may not be able to forward packet when none of its one-hop neighbors lies in a neighboring cell that is closer to the destination; this phenomenon is called local minimum. To guarantee the deliverability, in this thesis, we investigated two vital parameters of grid routing, the grid size and the transmission radius. Assume nodes are represented by a Poisson point process with rate n over a unit-area square, and let l denote the grid size and r denote the the transmission radius. First, we show that if l=√(("β" lnn)/n) for some constant "β" and r=√5 l, then "β=1" is the threshold for deliverability. In other word, there almost surely don't exist local minima if "β>1 " and there almost surely exist local minima if "β<1" . Next, for any give "β>1" , we gave a sufficient and necessary condition to determine the critical transmission radius for deliverability. Then we showed that the minimum critical transmission radius is r≅2.09√(lnn/n) which happens as β≅1.092. In addition, we derived the average hop-count between any source to destination and the average traffic flow through the cells. Finally, we conducted two simulations to verify our theoretical results.