隨意型無線網路環境中高效能之虛擬網格繞徑機制研究

On Design of Highly Efficient Virtual Grid Routing Mechanism in Ad Hoc Network

曾方甫(Fung-Fu Tseng)

指導教授 ： 黃士殷

元智大學/資訊學院/資訊工程學系/碩士(2004年)

摘要

在隨意型無線網路(MANET)繞徑協定中，讓所建立的路徑之步數越少是一項非常重要的目標，因為路徑步數越少代表著路徑所經過之節點也越少，節點越少則路徑穩定性也能夠相對提高。而另一方面，由於在隨意型無線網路(MANET)中廣播封包可能會產生廣播風暴的問題，因此能夠有效降低廣播封包的數量亦為另一個重要之目標。在本篇論文中，我們提出一個邊緣網格繞徑協定(Border Grid Routing Protocol, BGRP)，透過以邊緣網格繞徑之方式來達到所尋求之路徑短且穩定性高，並透過網格交換資訊的方式來提升修復路徑能力，同時利用選擇出來的網格閘道節點來廣播封包以限制廣播封包數量，我們所提出之演算法，能夠兼具路徑短且穩定性高、生存時間長且廣播封包數量低等優點。

關鍵字

隨意型無線網路 ； 路徑步數 ； 路徑穩定性 ； 廣播封包量 ； 廣播風暴 ； 網格 ； 邊緣網格 ； 邊緣網格繞徑協定

並列摘要

In Mobile Ad Hoc Network (MANET), it’s a vary important goal that finding a route which has fewer hop counts. Thus the route stability would also improve. In addition, the broadcasting on Mobile Ad Hoc Network (MANET) may lead to the broadcast storm problem so another important goal is to reduce the number of broadcast packets. In this thesis, we propose a border grid routing named Border Grid Routing Protocol (BGRP). It uses the border grid to search route and achieves to find shorter path、route stability. Border Grid Routing also can improve ability of route maintenance via the grid-to-grid communication and use the border gateways to forwarding packet so this could limit the number of broadcast packets. Our algorithm has those advantages: finding the shorter path、 higher route stability and route lifetime、 lower number of broadcast packets.

並列關鍵字

Mobile Ad Hoc Network ； hop count ； route stability ； number of broadcast messages ； broadcast storm ； grid ； border grid ； Border Grid Routing Protocol

參考文獻

[1] Royer, E.M. , Chai-Keong Toh, “A review of current routing protocols for ad hoc mobile wireless networks.”, IEEE Personal Communication, Volume: 6 Issue: 2, April 1999.

[2] Xiaoyan Hong Kaixin Xu, Mario Gerla, “Scalable Routing Protocols for Mobile Ad Hoc Networks.”, IEEE Network Magazine, July-Aug, 2002.

[3] Carlos de Marais Cordeiro, Hrishikesh Gossain, and Dharma P. Agrawal, “Multicast over Wireless Mobile Ad Hoc Networks: Present and Future Directions.”, IEEE Network, Volume: 17 , Issue: 1 , Pages:52 — 59, Jan.-Feb. 2003.

[6] C.E. Perkins, M. S. Corson, “Highly Dynamic Destination-Seqenced Distance-Vector Routing (DSDV) for Mobile Computers.” Computer Communication Review, pp. 234-244, October 1994.

[7] C.-C. Chiang, “Routing in Clustered Multihop, Mobile Wireless Networks With Fading Channel.” Proc. IEEE SICON ’97, April, 1997