臺灣博碩士論文加值系統

動態來源繞送(DSR)協定通常利用快取(cache)技術來降低路由負載和路徑探索所造成的延遲。為了使快取更有效率，繞送協定的設計需能應付頻繁的拓樸變動。本篇論文提出兩項機制來增加快取的正確性及提升傳送路徑的穩定性。第一項為加強型路徑錯誤封包傳播機制，將連結(link)斷裂的資訊送到所有曾經將此連結存入自己快取中的節點。第二項機制是結合連結穩定度測量的階層式連結快取(Hierarchical link cache)結構。將每一個節點裡的快取分成兩層：主要快取(primary cache)與第二快取(secondary cache)。當需要路徑時，會先從節點的主要快取中根據連結穩定度選擇一條路徑，以提供穩定的傳送。模擬結果顯示所提出的機制至少減少了13%的連結斷裂訊息，在路由負載和點對點的延遲上亦都優於其他DSR所使用的快取─path caches與包含可調式timeout機制的Link-MaxLife。

The Dynamic Source Routing (DSR) protocol usually utilizes route caching to reduce the routing overhead and route discovery latency. For caches to be effective, the protocol needs to adapt to the frequent topology changes. In this paper, we propose two mechanisms to improve cache correctness and route stability. The first is the RERR-Enhance mechanism in which a broken link message will be sent to all nodes that had cached the broken link. The second mechanism is the hierarchical link cache structure accompanied with a link stability measurement. The cache in each node falls into two tiers: the primary cache and the secondary cache. The node selects a route from the primary cache first, based on link stability, to provide stable transmission. The proposed mechanism reduces at least 13% of the broken link messages; it also reduces routing overhead and end-to-end delay, compared to DSR with path caches and with Link-MaxLife, an adaptive timeout mechanism for link caches.

中文摘要..................................................I
英文摘要.................................................II
目錄....................................................III
圖目錄...................................................VI
表格目錄...............................................VIII
字母縮寫對照表...........................................IX
第一章 導論...............................................1
1.1 簡介................................................1
1.1.1 隨意式無線網路的研究重點........................8
1.1.2 主要繞送協定的分類..............................9
1.2 動態來源繞送協定 (DSR)簡介.......................12
1.2.1 路徑搜尋機制...................................12
1.2.2 路徑維護機制...................................14
1.2.3 路徑快取.......................................14
1.3 研究動機...........................................15
1.4 論文架構...........................................17
第二章 背景與相關研究....................................18
第三章 系統之架構與運作..................................24
3.1 加強型路徑錯誤封包傳播機制(RERR-Enhance mechanism)
..................................................24
3.1.1 探討路徑錯誤封包的傳播方式.....................24
3.1.2 快取的儲存特性.................................25
3.1.3 連結資訊表(Link table).........................27
3.1.4 加強型路徑錯誤封包傳播.........................29
3.2 階層式連結快取 (Hierarchical link cache) 結構.........
..................................................30
3.2.1連結穩定度的測量................................31
3.2.2階層式連結快取結構..............................32
3.2.3快取的維護......................................33
第四章 模擬結果及分析....................................36
4.1 模擬環境假設.......................................36
4.2 模擬環境參數設定...................................37
4.3 數據分析與討論.....................................40
4.3.1 數據分析軟體...................................40
4.3.2 封包抵達率分析.................................43
4.3.3 延遲時間分析...................................45
4.3.4 路徑錯誤封包數分析.............................47
4.3.5 控制封包數分析.................................49
第五章 結論與未來展望....................................52
參考文獻.................................................53

[1]J. Broch, D. Maltz, D. Johnson, Y-C. Hu, and J.Jetcheva, “A performance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceedings of 4th ACM MobiCom, October 1998, Dallas, Texas, USA, pp. 85-97.
[2]S. Das et al, “Comparative performance evaluation of routing protocols for ad hoc networks,” in Proceedings of 7th International Conference on Computer Communication and Networks (IC3N), October 1998, Lafayette, Louisiana, USA, pp 153-161.
[3]M. Gerharz, C de Waal, P. Martini and P. James, “Strategies for finding stable paths in mobile wireless ad hoc networks,” in Proceedings of 28th IEEE Conference on Local Computer Networks (LCN), October 2003, Bonn, Konigswinter, Germany, pp.130-139.
[4]G. Holland and N. Vaidya, “Analysis of TCP performance over mobile ad hoc networks,” in Proceedings of 5th ACM MobiCom, August 1999, Seattle, Washington, USA, pp.219-230.
[5]Y.-C.Hu and D. Johnson, “Caching strategies in on-demand routing protocols for wireless ad hoc networks,” in Proceedings of 6th ACM MobiCom, August 2000, Boston, Massachusetts, USA, pp.231-242.
[6]Y-C. Hu and D. Johnson, “Ensuring cache freshness in on-demand ad hoc network routing protocols,” in Proceedings of 2nd Workshop on Principles of Mobile Computing (POMC), October 2002, Toulouse, France, pp. 25-30.
[7]IEEE Std. 802.11, “IEEE Standard for Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specification,” June 1997.
[8]M. Joa and I. T. Lu, “A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks,” IEEE Journal on Selected Areas in Communications, Vol. 17 no. 8, August 1999, pp. 1415-1425.
[9]D. Johnson and D. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” in Mobile Computing, edited by Tomasz Imielinski and Hank Korth, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.
[10]D. Johnson, D. Maltz, and Y.-C. Hu, “The Dynamic Source Routing for mobile ad hoc networks,” IETF Internet Draft. http://www.ietf.org/internet-drafts/draft-ietf-manet-dsr-10.txt, July 2004.
[11]W. Lou and Y. Fang, “Predictive caching strategy for on-demand routing protocols in wireless ad hoc networks,” Wireless Networks, Vol. 8, Issue 6, November 2002, pp. 671-679.
[12]D. Maltz, J. Brooch,J. Jetcheva, and D. Johnson. “The effects of on-demand behavior in routing protocols for multi-hop wireless ad hoc networks,” IEEE Journal on Selected Areas in Communication, Vol. 17, Issue 8, August 1999, pp. 1439-1453.
[13]M.Marina and S. Das, “Performance of routing caching strategies in Dynamic Source Routing,” in Proceedings of 2nd Workshop on Wireless Networks and Mobile Computing (WNMC), April 2001, Phoenix, Arizona, USA, pp. 425-432.
[14]N.Meghanathan, “Comparison of stable path selection strategies for mobile ad hoc networks,” in Proceedings of IEEE ICNICONSMCL, April 2006, Mauritius, pp. 67-67.
[15]S. Murphy and J.J. Garcia-Luna-Aceves, “An efficient routing protocol for wireless networks,” ACM/Baltzer Journal on Mobile Networks and Applications, Special Issue on Routing in Mobile Communication Networks, October 1996, pp 183-197.
[16]V. Park, M. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” in Proceedings of the IEEE International Conference on Computer Communication (INFOCOM), Vol.3, April, 1997, Kobe, Japan, pp.1405-1413.
[17]M. R. Pearlman and Z. J. Haas, "Determining the Optimal Configuration for the Zone Routing Protocol", IEEE Journal on Selected Areas in Communications, Vol. 17, no. 8, August 1999, pp. 1395-1414.
[18]C. Perkins and P. Bhagwat, “Highly dynamic destination -sequenced distance-vector routing (DSDV) for mobile computers,” Computer Communication Review, ACM SIGCOMM, Vol.24, No.4, August 1994, London, England, pp. 232-244.
[19]C. Perkins, E. Royer, S. Das, and M.Marina, “Performance comparison of two on-demand routing protocols for ad hoc networks,” IEEE Personal Communications, Vol. 8. Issue 1, February 2001, pp. 16-28.
[20]C. Perkins, E. Royer, and S. Das, “Ad hoc On-demand Distance Vector (AODV) Routing,” RFC 3561. http://www.ietf.org/ rfc/rfc3561.txt?number=3561, July 2003.
[21]X. Yu, Z. Kedem, “A distributed adaptive cache update algorithm for the dynamic source routing protocol,” in Proceedings of the IEEE International Conference on Computer Communication (INFOCOM), Vol. 1, March 2005, Miami, Florida, USA, pp.730-739.
[22]NS - Network Simulator：http://www.isi.edu/nsnam/ns/
[23]NS manual：http://www.isi.edu/nsnam/ns/ns-documentation.html
[24]Trace Graph：http://www.tracegraph.com/