博碩士論文 955302026 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:38 、訪客IP:3.216.79.60
姓名 林浩偉(Hao-Wei Lin)  查詢紙本館藏   畢業系所 資訊工程學系在職專班
論文名稱 地理繞徑協定上改善Dead end的發生機率
(Dead end avoidance enhanced Mechanism in GPSR)
相關論文
★ 整合多樣配置組態下的藍芽射頻驗證系統★ 具檔案敘述相關語查詢之智慧型檔案搜尋系統
★ 具遲到者支援功能之網際網路簡報系統★ 以快速廣播法建構熱門視訊隨選服務伺服器
★ 具事件同步再現特性之遠程電傳展示伺服器★ 無線網路環境下之廣播資訊快速下載
★ 中文網站繁簡互訪協助系統★ 支援時光平移播放之調適性現場直播演算法
★ 用於互動式廣播之段落對齊法★ 熱門影片廣播法之影片區段復原機制
★ 配合熱門影片廣播的本地伺服器高效快取法★ 一個增進SIP在防火牆環境中應用的協同模組
★ 考量網頁熱門度之一致性雜湊法解決 網頁代理伺服器之負載平衡★ 以網域名稱伺服器為基礎之色情網站過濾系統
★ 使用熱門廣播法及支援點對點傳輸之影音內容傳遞網路★ 變動頻寬平滑化之熱門廣播演算法
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 雖然 Greedy Perimeter Stateless Routing (GPSR) 的地理繞徑貪婪演算法在無線隨意網路中有傳輸效能很好以及封包的負載較小等特性,但是在網路中的節點必須要知道他們自己的地理位置。另外,若網路中存在有缺口時,使用GPSR 橫越缺口的繞徑會導致在缺口邊界的節點負載過重,以及造成一些不必要的多餘繞徑。在本篇論文中,我們提出一個分散式的演算法以建構各點的區域性voronoi diagram的方式,先偵測出可能會造成封包傳送發生dead end的區域,並利用場論的概念,由發送端傳輸至目的端的路徑必定沿著兩點間的最短路徑,若路徑中的中繼點具有面臨缺口造成傳輸失敗的疑慮,則需使位於缺口邊界附近的節點在虛擬座標系統上向缺口的反方向靠攏,以降低其被選為中繼點的機率,如同於缺口方向存在一個帶有正電的電荷,而節點亦是一個帶正電的電荷,所以缺口方向會給予節點一股反向的推力,使其遠離缺口,藉此降低缺口邊界附近的節點被選為中繼節點的機率。我們的模擬結果呈現這個由我們的協定產生的虛擬座標系統可以有效率地支援地理繞徑,而且即時在這個網路中存在有一些缺口在裡面,這些透過我們的協定確實有效降低節點傳輸間遇到缺口的機率,尤其是在稀疏的網路環境及U型管般的網路拓墣中。
摘要(英) Geographic routing algorithms are an attractive alternative to traditional ad hoc routing algorithms. Although geographic routing like Greedy Perimeter Stateless Routing (GPSR) is efficient to mobile ad hoc wireless networks, it requires that nodes be aware of their physical positions to inform their neighbors. In addition, if there are exist geometric holes within the network topology, which is called “dead end”, routing across dead ends in GPSR [5] will lead to a lot of redundant routing paths during data transmission and overloaded nodes in the boundaries of dead ends. In this thesis, we proposed an approach, according to virtual coordinate system based on detecting possible dead ends among nodes to improve the routing performance of existing geographic routing algorithms. When exchanging beacon message among nodes, each node will construct a local Voronoi diagram on the basis of the message information which receives from its neighbors simultaneously, each node draws perpendicular bisectors with all of its neighbors and then it checks if any segments on its transmission circle are not covered, which is called “dead end area”. Encountering those nodes which is existed the dead end area when data packets were greedily forwarded. It may cause transmission end up. In order to reduce this kind of situation, we assume every mobile node within network was a positive electron and destination node is a negative electron. In accordance with field theory [25] the packet forwarding among the shortest path from source node to destination node is inevitable, if the node exist one or more dead end area within its broadcast range, there was existed an pseudo positive electron which locate out of node’’s broadcast range, the pseudo electron’s location was sum of two vectors, one is mobile node to the start point of dead end area, and the other is mobile node to the end of dead end area. And pseudo electron will give a repulsive force to mobile node which will force virtual coordinate of nodes moving away from the dead end area. For the purpose of reducing the risk of encountering dead end situation. After the mention above, the nodes in the network are aware of the relative virtual coordinates and each of them was notified to the neighbors by exchanging beacon message. In the final of this study, results of the simulation show that our approach can improve geographic routing more efficient, In addition, our approach is resilient to various network shapes especially for U-shaped-like topology within the sparse network. In this thesis, some programming effort was implemented for comparison using the NS2 simulator platform[17]. The simulation results show that the average number of dead end occurrences was significantly reduced about 5 to 10 times of packet to encounter the dead end situation. When our dead end avoidance enhanced mechanism was applied. The packet delivery ratio was improved also.
關鍵字(中) ★ 虛擬座標系統
★ 無線隨意網路
★ 地理繞徑
關鍵字(英) ★ mobile ad hoc networks
★ virtual coordinate system
★ Geographic routing
論文目次 Abstract ii
Chapter 1 : Introduction 1
Chapter 2 : Related works 4
Chapter 3 : Methodology 15
? 3.1 overview of Dead-end Problem 16
? 3.2 Overview of Enhance dead end avoidance mechanism 16
? 3.3 Construct Dead end avoidance mechanism 18
? 3.4 Enhance dead end avoidance mechanism Algorithm 23
Chapter 4 : Simulation 28
Chapter 5 : conclusion 34
References 35
Appendix 39
參考文獻 [1] Charles E. Perkins and Pravin Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV). In Proceedings of the conference on Communications architectures, protocols and applications (SIGCOMM ’94), London, United Kingdom, August 1994.
[2] D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353. 1996.
[3] C Perkins, EM Royer. Ad hoc On-Demand Distance Vector (AODV) Routing, IETF Internet Draft, June 2002
[4] Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proceedings of PODC 2003, July 2003.
[5] B. Karp and H. Kung. “GPSR: greedy perimeter stateless routing for wireless networks,” Proceedings of the sixth annual international conference on Mobile computing and networking, pp. 243-254, 2000.
[6] B. Leong, B. Liskov, and R. Morris. Geographic routing without planarization. In Proceedings of NSDI 2006, May 2006.
[7] B. Leong, S. Mitra, and B. Liskov. Path vector face routing: Geographic routing with local face information. In Proceedings of ICNP 2005, November 2005.
[8] Chou, C.-H. Ssu, K.-F. Jiau, H. C. Geographic Forwarding with Dead end Reduction in Mobile Ad Hoc Networks, appears in Vehicular Technology, IEEE Transactions on Publication Date: July 2008
[9] FRANZ AURENHAMMER. Voronoi Diagrams —A Survey of a Fundamental Geometric Data Structure, In Proceedings of ACM Computing Surveys, Vol. 2.3, No. 3, September 1991
[10] Nakagawa, H.; Ishida, K.; Ohta, T.; Kakuda, Y.; GOLI: Greedy On-Demand Routing Scheme Using Location Information for Mobile Ad Hoc Networks, Proceedings of Distributed Computing Systems Workshops, 2006. ICDCS Workshops 2006. 26th IEEE International Conference on 04-07 July 2006 Page(s):1 - 1
[11] Ben Leong; Liskov, B.; Morris, R.; Greedy Virtual Coordinates for Geographic Routing Network Protocols, 2007. ICNP 2007. IEEE International Conference on 16-19 Oct. 2007 Page(s):71 - 80
[12] G. G. Finn,;“Routing and Addressing Problems in Large MetropolitanScale Internetworks,” Tech. Rep. ISI/RR87180,Information Sciences Institute, University of Southern California, Mar. 1987.
[13] Xiaoyan Hong Kaixin Xu Gerla, M. California Univ., Los Angeles, CA; Scalable routing protocols for mobile ad hoc networks This paper appears in: Network, IEEE Publication Date: Jul/Aug 2002
[14] S. Basagni, I. Chlamtac, V. R. Syrotiuk, and B. A.Woodward, “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proceedings of the IEEE International Conference on Mobile Computing and Networking, pp. 76–84, Oct. 1998.
[15] N. Arad and Y. Shavitt, “Minimizing Recovery State in Geographic AdHoc Routing,” Tech. Rep. EE49, School of Electrical Engineering, Tel Aviv University, Sept. 2005.
[16] Q. Fang, J. Gao, and L. Guibas, “Locating and Bypassing Holes in Sensor Networks,” ACM/Springer Journal of Mobile Networks and Applications, vol. 11, no. 2, pp. 187–200, Apr. 2006.
[17]K. Fall and K. Varadhan (editors), The ns Manual (ns Notes and Documentation).TheVINTproject,www.isi.edu/nsnam/ns/nsdocumentation. html,Nov. 2005.
[18] PalChaudhuri, S. Le Boudec, J.-Y. Vojnovic, M. Comput. Sci., Rice Univ., Houston, TX, USA; Perfect simulations for random trip mobility models; appears in: Simulation Symposium, 2005. Proceedings. 38th AnnualPublication Date: 4-6 April 2005 On page(s): 72- 79
[19] B. Hofmann-Wellenhof, H. Lichtenegger, and J. Collins, “Global Positioning System: Theory and Practice,” 4th Edited, Springer Verlag, 1997.
[20] F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Monographs in Computer Science). Springer, New York, Aug. 1985.
[21] R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S. Shenker, and Stoica. Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of NSDI 2005, May 2005.
[22] Q. Fang, J. Gao, L. J. Guibas, V. de Silva, and L. Zhang. GLIDER:Gradient landmark-based distributed routing for sensor networks. In Proceedings of IEEE Infocom '05, March 2005.
[23] Ben Leong; Liskov, B.; Morris, R.; Greedy Virtual Coordinates for Geographic Routing Network Protocols, 2007. ICNP 2007. IEEE International Conference on 16-19 Oct. 2007 Page(s):71 - 80 Digital Object Identifier 10.1109/ICNP.2007.4375838
[24] Jinyang Li John Jannotti Douglas S. J. De Couto David R. Karger ; A Scalable Location Service for Geographic Ad Hoc Routing in M.I.T. Laboratory for Computer Science
[25] http://en.wikipedia.org/wiki/Field_theory_%28mathematics%29
[26] http://en.wikipedia.org/wiki/Coulomb%27s_law
[27] http://en.wikipedia.org/wiki/Law_of_cosines
指導教授 曾黎明(Li-Ming Tseng) 審核日期 2008-7-24
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明