臺灣博碩士論文加值系統

由於無線隨意式網路（Wireless Ad Hoc Network）具有主機可以隨意移動、網路頻寬、記憶體容量和電池持續力等資源都有限的特性，如何設計有效的路由演算法，便具有相當的挑戰性。
早期針對無線隨意式網路的路由研究，學者多專注於單播路由協定（Unicast Routing Protocol）之研究，但隨著網路應用的改變，群播路由協定（Multicast Routing Protocol）應用層面變廣，重要性也更為增加。目前已有部份學者針對無線隨意式網路提出群播路由協定，在眾多的群播路由協定中，以ODMRP（On Demand Multicast Routing Protocol）的效能較佳。
因此，我們修改ODMRP，提出一個動態的隨選群播路由協定（Dynamic On-demand Multicast Routing Protocol），簡稱為D-ODMRP，此群播路由協定能針對網路狀態穩定與不穩定，而適當地調整網徑的大小，同時為了降低成本和封包遞送延遲時間，群播傳送端採用動態的廣播機制，更可因應無線隨意式網路拓蹼易改變的環境。我們透過NS-2來評估D-ODMRP的效能，不管在何種負載下，D-ODMRP都可以跟ODMRP一樣達到相當高的封包遞送率，且擁有較小的網路流量負載，而在高負載方案，D-ODMRP的遞送延遲時間是最短的，這些結果顯示D-ODMRP具有比ODMRP較佳的效能。

A wireless ad hoc network is characterized by the highly-dynamic topology with limited bandwidth, memory, and power. How to design an efficient routing protocol in this environment is a challenge.
Most prior works in a wireless ad hoc network focused on developing an unicast routing protocol. However, recently multicast routing becomes an important issue because the applications using this technique become popular. As a result, several multicast routing protocols in ad hoc networks have been proposed. Among these proposed multicast routing protocols, ODMRP（On Demand Multicast Routing Protocol） has the best performance.
Therefore, we modify ODMRP and propose a Dynamic On-demand Multicast Routing Protocol, called D-ODMRP. It can appropriately adjust mesh size depending on whether the network state is stable or not. For reducing overhead and packet delivery latency, the multicast source adopts a dynamic broadcasting mechanism against the rapid change of network topology. We compare the performance of D-ODMRP and ODMRP through NS-2. Regardless of any load, D-ODMRP can achieve high packet delivery ratio as ODMRP, while the former has a less overhead than the latter. In high loaded case, D-ODMRP has the shortest packet delivery latency. These simulation results show that D-ODMRP has the better performance than ODMRP.

摘要 I
Abstract II
誌謝 III
第一章 簡介 1
1.1 概論 1
1.2 研究動機 3
1.3 論文架構 5
第二章 相關研究 6
2.1 Mobile Ad Hoc Network（MANET） 6
2.2 Tree-based群播路由協定 7
2.2.1 AMRoute 7
2.2.2 MAODV 8
2.2.3 AMRIS 10
2.2.4 ABAM 11
2.3 Mesh-based群播路由協定 12
2.3.1 ODMRP 12
2.3.2 CAMP 13
2.3.3 NSMP 14
第三章 D-ODMRP（Dynamic On-demand Multicast Routing Protocol） 16
3.1 D-ODMRP所用到的資料結構 17
3.2 路徑需求階段 21
3.3 路徑回應階段 27
3.4 動態網徑路徑的建立 31
3.5 轉送群播資料封包 34
3.6 同步(Sync)資料封包傳送 35
3.7 D-ODMRP之路徑修復 37
3.8 動態路徑需求通知 40
3.9 離開群播群組 42
第四章 模擬結果分析 43
4.1 模擬方案 43
4.2 效能度量 45
4.3 D-ODMRP和ODMRP所用到的模擬參數 45
4.4 模擬結果和分析 46
4.4.1 不同的暫停時間 47
4.4.1.1 封包遞送率（Packet Delivery Ratio）分析 47
4.4.1.2 轉送效率（Forwarding Efficiency）分析 50
4.4.1.3 封包成本（Packet Overhead）分析 52
4.4.1.4 遞送延遲時間（Delivery Latency）分析 55
4.4.2 不同的節點個數 58
4.4.2.1 封包遞送率（Packet Delivery Ratio）分析 58
4.4.2.2 轉送效率（Forwarding Efficiency）分析 61
4.4.2.3 封包成本（Packet Overhead）分析 63
4.4.2.4 遞送延遲時間（Delivery Latency）分析 65
4.4.3 不同的移動速度 68
4.4.3.1 封包遞送率（Packet Delivery Ratio）分析 68
4.4.3.2 轉送效率（Forwarding Efficiency）分析 70
4.4.3.3 封包成本（Packet Overhead）分析 72
4.4.3.4 遞送延遲時間（Delivery Latency）分析 74
第五章 結論 76
參考文獻 77
附錄 中英文索引 80
作者簡介 82
圖 表 索 引
圖1-1 有基礎架構的無線網路……………..……………..…………………………2
圖1-2 無基礎架構的無線網路（Wireless Ad Hoc Network）……………………..3
圖3-1 群播傳送端廣播RREQ……………..……………..………………………...23
圖3-2 群播接收端發出RREP建立路徑……………..……………..……………..28
圖3-3 備份路徑的建立……………..……………..………………………………..32
圖3-4 群播資料封包的傳輸……………..……………..…………………………..35
圖3-5 同步資料封包的傳輸……………..……………..…………………………..36
圖3-6 強制觸發封包的傳輸之範例一……………..……………..………………..38
圖3-7 強制觸發封包的傳輸之範例二……………..……………..………………..39
圖4-1 在1x1x15環境中，無線節點不同的暫停時間，對封包遞送率之影響分析.47
圖4-2 在3x3x10環境中，無線節點不同的暫停時間，對封包遞送率之影響分析.49
圖4-3 在1x1x15環境中，無線節點不同的暫停時間，對轉送效率之影響分析….50
圖4-4 在3x3x10環境中，無線節點不同的暫停時間，對轉送效率之影響分析….51
圖4-5 在1x1x15環境中，無線節點不同的暫停時間，對封包成本之影響分析….52
圖4-6 在3x3x10環境中，無線節點不同的暫停時間，對封包成本之影響分析….54
圖4-7 在1x1x15環境中，無線節點不同的暫停時間，對遞送延遲時間之影響分析…………………………………………………………………………………….55
圖4-8 在3x3x10環境中，無線節點不同的暫停時間，對遞送延遲時間之影響分析……………..……………..………………………..……………..………………..56
圖4-9 在1x1x15環境中，不同的無線節點個數，對封包遞送率之影響分析... 58
圖4-10 在3x3x10環境中，不同的無線節點個數，對封包遞送率之影響分析…60
圖4-11 在1x1x15環境中，不同的無線節點個數，對轉送效率之影響分析…...61
圖4-12 在3x3x10環境中，不同的無線節點個數，對轉送效率之影響分析…...62
圖4-13 在1x1x15環境中，不同的無線節點個數，對封包成本之影響分析…...63
圖4-14 在3x3x10環境中，不同的無線節點個數，對封包成本之影響分析…...64
圖4-15 在1x1x15環境中，不同的無線節點個數，對遞送延遲時間之影響分析……………………………………………………………………………………..65
圖4-16 在3x3x10環境中，不同的無線節點個數，對遞送延遲時間之影響分析……………………………………………………………………………………..66
圖4-17 在1x1x15環境中，節點不同的移動速度，對封包遞送率之影響分析..68
圖4-18 在3x3x10環境中，節點不同的移動速度，對封包遞送率之影響分析..69
圖4-19 在1x1x15環境中，節點不同的移動速度，對轉送效率之影響分析…..70
圖4-20 在3x3x10環境中，節點不同的移動速度，對轉送效率之影響分析…..71
圖4-21 在1x1x15環境中，節點不同的移動速度，對封包成本之影響分析…..72
圖4-22 在3x3x10環境中，節點不同的移動速度，對封包成本之影響分析…..73
圖4-23 在1x1x15環境中，節點不同的移動速度，對遞送延遲時間之影響分析……………………………………………………………………………………..74
圖4-24 在3x3x10環境中，節點不同的移動速度，對遞送延遲時間之影響分析……………………………………………………………………………………..75
表一 路徑需求封包的資料結構 18
表二 路徑回應封包的資料結構 18
表三 路徑觸發封包的資料結構 19
表四 強制路徑觸發封包的資料結構 19
表五 路徑異常封包的資料結構 20
表六 路由表的資料結構 20
表七 轉送封包表格的資料結構 21
表八 S節點所廣播出來的RREQ內容 23
表九 K節點將修改後的RREQ廣播出去之內容 24
表十 K節點收到J節點送來的RREQ後，所更新的路由表內容 24
表十一 K節點收到G節點送來的RREQ後，所更新的路由表內容 25
表十二 K節點將修改後的RREQ廣播出去之內容 25
表十三 K節點再次收到G節點送來的RREQ後，所更新的路由表內容 26
表十四 K節點收到L節點送來的RREQ後，所更新的路由表內容 26
表十五 K節點傳送出來的RREP內容 29
表十六 G節點收到K節點送來的RREP後，所更新的轉送封包表格之內容 30
表十七 G節點傳送出來的RREP內容 30
表十八 C節點傳送出來的RREP內容 30
表十九 K節點請求J節點轉送RTRI時，RTRI之內容 33
表二十 K節點請求L節點轉送RTRI時，RTRI之內容 33
表二十一 L節點收到K節點送來的RTRI後，所更新的轉送封包表格之內容 34
表二十二 L節點請求H節點轉送RTRI時，RTRI之內容 34
表二十三 群播傳送端動態RREQ間隔時間範例 41

[1] Bommaiah, McAuley, and Talpade. AMRoute: Adhoc Multicast Routing Protocol. Internet-Draft, draft-talpade-manet-amroute-00.txt, February 1999. Work in progress.
[2] S.-J. Lee, Mario Gerla, and C.-C. Chiang. On-Demand Multicast Routing Protocol. In Proceedings of the IEEE Wireless Communications and Networking Conference, WCNC ’99, pages 1298-1304, September 1999.
[3] S.-J. Lee, W. Su, J. Hsu, M. Gerla, and R. Bagrodia. A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols. In Proceedings of IEEE INFOCOM 2000, pages 565-574, March 2000.
[4] Kevin Fall and Kannan Varadhan, editors. Ns Notes and Documentation. The VINT Project, UC Berkeley, LBL, USC/ISI, and Xerox PARC, November 1997. Available from http://www-mash.cs.berkeley.edu/ns/.
[5] C.-K Toh, Guillermo Guichala, and Santithorn Bunchua. ABAM: On-Demand Associativity-Based Multicast Routing for Ad Hoc Mobile Networks. In Proceedings of IEEE Vehicular Technology Conference, VTC 2000, pages 987-993, September 2000.
[6] C.W. Wu, Y.C. Tay, and C-K. Toh. Ad hoc Multicast Routing protocol utilizing Increasing id-numberS (AMRIS). Internet-Draft, draft-ietf-manet-amris-spec-00.txt, November 1998. Work in progress.
[7] Elizabeth M. Royer and charles E. Perkins. Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol. In Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking, Mobicom ’99, pages 207-218, August 1999.
[8] M.S. Corson and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,“ Request For Comments 2501, Internet Engineering Task Force, Jan. 1999.
[9] J.J. Garcia-Luna-Aceves and E.L. Madruga, “The Core-Assisted Mesh Protocol,” IEEE Journal on Selected Areas in Communications. Vol. 17, no. 8, Aug. 1999, pp. 1380-1394.
[10] S. Lee and C. Kim, “Neighbor Supporting Ad hoc Multicast Routing Protocol, “Proceedings of the ACM/IEEE Workshop on Mobile Ad Hoc Networking and Computing (MOBIHOC), Boston, MA, August 2000, pp. 37-44. 2
[11] C. Perkins, P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing（DSDV）for Mobile Computers,” ACM SIGCOMM, Oct. 1994
[12] S. Murthy, and J.J. Garcia-Luna-Aceves, “An Efficient routing protocol for wireless networks,” ACM Mobile Network and Applications Journal, Special issue on Routing in Mobile Communication Networks, 1996.
[13] V. Park, and S. Corson, “Temporally-ordered routing algorithm（TORA）Version 1,” Internet draft, IETF, Aug. 1998.
[14] Josh Broch, David B. Johnson, and David A. Maltz, “The dynamic source routing in ad hoc wireless networks, “ In Mobile Computing, edited by Tomase Imielinski and Hank Korth, Chapter 5, pages 153-181, Kluwer Academic Publishers, 1996.
[15] Charles Perkins, Elizabeth M. Royer, and Samir R. Das, “Ad hoc on demand distance vector（AODV）routing” Internet draft, IETF, Jun. 1999.
[16] C. K. Toh, “Long-lived ad hoc routing based on the concept of associativity,” Internet draft, IETF, Mar. 1999.
[17] G. Aggelou, and R. Tafazolli, “RDMAR: a bandwidth-efficient routing protocol for mobile ad hoc networks,” Proceedings of The Second ACM International Workshop on Wireless Mobile Multimedia（WoWMoM）, Seattle, Washington, Aug. 1999.
[18] J. Broch, D. A. Maltz, D. B. Johnson, Y. Hu, and J. Jetcheva, “A performance comparison of multi-hop wireless ad hoc network routing protocols,” Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, ACM, Dallas, TX, Oct. 1998.
[19] P. Johansson, T. Larsson, N. Hedman, B. Mielczarek, and M. Degermark, “Scenario-based performance analysis of routing protocols for mobile ad-hoc networks,” MobiCom ’99, Aug. 1999.
[20] C.-C. Chiang, "Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel" Proceedings of IEEE SICON'97, Apr.1997, pages 197-211.
[21] The Monarch Project. Monarch Project: Mobile Networking Architectures. Available at http://monarch.cs.rice.edu/.