學術產出-Theses
Article View/Open
Publication Export
-
題名 MANET中利用節點移動方向降低廣播風暴發生之路由策略
Direction-Based Routing Strategy to Reduce Broadcast Storm in MANET作者 洪志佳
Hung, Chih-Chia貢獻者 張宏慶
Jang,Hung-Chin
洪志佳
Hung, Chih-Chia關鍵詞 行動隨意無線網路
廣播風暴
衛星定位
MANET
Broadcast Storm
Global Positioning System日期 2009 上傳時間 9-May-2016 12:02:43 (UTC+8) 摘要 藉由許多配備無線通訊能力的嵌入式系統裝置,如筆記型電腦、行動電話、PDA、車用導航系統及車用電腦等,不同的裝置透過無線通訊的能力,將彼此連接,構成行動隨意網路 (Mobile Ad Hoc Network) 的環境。這些網路上的節點可能任意且快速移動,隨時改變既有網路拓樸,造成原先已經建立好的路由中斷。採用被動式路由協定 (Reactive Routing Protocol) 的路由重建,往往增加了資料傳送的延遲及重建路由時所需要大量路由發現 (Route Discovery) 的封包,造成廣播風暴 (Broadcast Storm),嚴重影響整個網路的效能。 在論文中,我們提出一個利用節點的移動方向做為選擇適當中繼節點 (Relay Node) 的策略,稱之為Directive Location-Aided Routing,簡稱DLAR。DLAR將節點的移動方向因素加入於既有的LAR中做為選擇中繼節點的考量。中繼節點的決定,需要符合與來源節點相同的移動方向,目的是維持較長的連線時間,且讓路由中斷的位置靠近目的節點,並使用AODV的Local Repair的機制做為路由搜尋的協定,加速路由的恢復。 實驗模擬結果顯示,DLAR與AODV、DSR及LAR比較,在減少找尋路由路徑時所需的路由請求封包、降低點對點 (End -To-End) 的延遲及資料成功送達率,都有較佳的表現。在網路中節點數較多時,DLAR在封包送達率能有6%– 55%的改善,降低搜尋及維持路由時需要的控制封包量達40%以上,降低廣播風暴發生的機率, DLAR也同時在End-to-End Delay的表現較之於其他路由機制,有20%以上的改善。
In MANET the nodes may move fast and unpredictable, this may cause the original set up route well broken. Adopt those Reactive Routing Protocols may not only cause seriously data delivery delay but also produce a large number of control packages (RREQ) thus reducing network capacity. This is known as Broadcast Storm Problem. In this thesis, we proposed a routing protocol, Directive Location-Aided Routing (DLAR), that helps to choose appropriate relay nodes (intermediate nodes) in MANET. DLAR considers the node movement direction factor in deciding a stable route. Relay node is considered to be the same movement direction as source node. The goal is to maintain longer path lifetime, and make the broken very close to the destination node. DLAR adopts AODV to discovery route and accelerate the route recovery using Local Repair mechanism. Simulations show that as the network loading is high, DLAR can increase the packet delivery ratio by 6% ~ 55 % and increase the bandwidth utility by 40%, reduce the largely broadcast storm probability, and reduce end-to-end delay by 20%.參考文獻 [1] “The Network Simulator NS-2,” http://www.isi.edu/nsnam/ns/, 2005. [2] Ahed M. Alshanyour and Uthman Baroudi, "Bypass AODV: improving performance of ad hoc on-demand distance vector (AODV) routing protocol in wireless ad hoc networks", IProceedings of the 1st international conference on Ambient media and systems, Quebec, Canada, February 11 - 14, 2008 [3] Josh Broch , David A. Maltz , David B. Johnson, Yih-Chun Hu , and Jorjeta Jetcheva , “A performance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’98), Dallas, Texas, U.S.A., October 1998, pp. 85 – 97. [4] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel”, Proceedings IEEE SICON ’97, pp. 197–211, Apr. 1997. [5] S. Corson and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” RFC 2501, January 1999. RFC2501 [6] K.-T. Feng and T.-E. Lu, “Velocity and location aided routing for mobile ad hoc networks,” in Proc. IEEE 60th VTC—Fall, Los Angeles, CA, 2004, pp. 2789–2793. [7] K.T. Feng, C.H. Hsu, and T.E. Lu, “Velocity-Assisted Predictive Mobility and Location-Aware Routing Protocols for Mobile Ad Hoc Networks,” IEEE Trans. on Vehicular Technology, vol. 57, no. 1, pp. 448–464, 2008. [8] Z. Hass and M. Pearlman, “The Performance of Query Control Schemes for the Zone Routing Protocol,” ACM SIGCOMM, Aug. 1998, pp. 167-177. [9] D. B. Jhonson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” In Mobile Computing, Kluwere Academic Publishers, 1996, pp.153-181. [10] P. Jacquet and L. Viennot, “Overhead in Mobile Ad Hoc Network Protocols,” INRIA Research Report RR-3965, available at http://www.inria.fr/Equipes/HIPERCOM-eng.html, July 2000. [11] Y. B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” in Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), Dallas, Texas, USA, 1998, pp. 66-75. [12] V. Namboodiri, M. Agarwal, L. Gao, ”A Study on the Feasibility of Mobile Gateways for Vehicular Ad-hoc Networks”. In Proceedings of the First ACM International Workshop on Vehicular Ad-Hoc Networks, Philadelphia, June 2004. [13] C. E. Perkins and E. M. Royer, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computer,” Proceeding of the 1994 ACM Special Interest Group on Data Communication, London, UK, Sep. 1994, pp. 234-244 [14] C. E. Perkins; E. M. Royer, “Ad-hoc on-demand distance vector routing”, in Proc. IEEE WMCSA ’99, pp. 90-100, Feb. 1999. [15] C. E. Perkins, Ad Hoc Networking, Addison Wesley, 2001. [16] C. Perkins, E. Belding-Royer and S. Das “Ad-hoc on-demand distance vector (AODV) routing”, RFC3561, July 2003. [17] C. Perkins, E.M. Royer, S.R. Das, and M.K. Marina, Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks, IEEE Personal Communications, pages 16-28, Feb. 2001. [18] E. Royer, and C.K. Toh, (1999), “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications Magazine, pp. 46-55 [19] Yu-Chee Tseng , Shib-Lin Wu , Wen-Hwa Liao and Chih-Min Chao , “Location Awareness in Ad Hoc Wireless Mobile Networks,” IEEE Computer, 2001, Page(s): 46 -52. [20] Y.-C. Tseng, S.-Y. Ni, Yuh-Shyan Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," ACM Wireless Networks (WINET), Vol. 8, No. 2, pp. 153-167, March 2002. (SCI) [21] Y.-C. Tseng, S.-Y. Ni, and E.-Y. Shih, Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network, IEEE Transactions on Computers, vol. 52, no. 5, pp. 545-557, May 2003. [22] Y.-C. Tseng, S.-Y. Ni, Yuh-Shyan Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," ACM Wireless Networks, Vol. 8, No. 2, pp. 153-167, March 2002. 描述 碩士
國立政治大學
資訊科學學系
94971020資料來源 http://thesis.lib.nccu.edu.tw/record/#G0949710201 資料類型 thesis dc.contributor.advisor 張宏慶 zh_TW dc.contributor.advisor Jang,Hung-Chin en_US dc.contributor.author (Authors) 洪志佳 zh_TW dc.contributor.author (Authors) Hung, Chih-Chia en_US dc.creator (作者) 洪志佳 zh_TW dc.creator (作者) Hung, Chih-Chia en_US dc.date (日期) 2009 en_US dc.date.accessioned 9-May-2016 12:02:43 (UTC+8) - dc.date.available 9-May-2016 12:02:43 (UTC+8) - dc.date.issued (上傳時間) 9-May-2016 12:02:43 (UTC+8) - dc.identifier (Other Identifiers) G0949710201 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/94863 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description (描述) 94971020 zh_TW dc.description.abstract (摘要) 藉由許多配備無線通訊能力的嵌入式系統裝置,如筆記型電腦、行動電話、PDA、車用導航系統及車用電腦等,不同的裝置透過無線通訊的能力,將彼此連接,構成行動隨意網路 (Mobile Ad Hoc Network) 的環境。這些網路上的節點可能任意且快速移動,隨時改變既有網路拓樸,造成原先已經建立好的路由中斷。採用被動式路由協定 (Reactive Routing Protocol) 的路由重建,往往增加了資料傳送的延遲及重建路由時所需要大量路由發現 (Route Discovery) 的封包,造成廣播風暴 (Broadcast Storm),嚴重影響整個網路的效能。 在論文中,我們提出一個利用節點的移動方向做為選擇適當中繼節點 (Relay Node) 的策略,稱之為Directive Location-Aided Routing,簡稱DLAR。DLAR將節點的移動方向因素加入於既有的LAR中做為選擇中繼節點的考量。中繼節點的決定,需要符合與來源節點相同的移動方向,目的是維持較長的連線時間,且讓路由中斷的位置靠近目的節點,並使用AODV的Local Repair的機制做為路由搜尋的協定,加速路由的恢復。 實驗模擬結果顯示,DLAR與AODV、DSR及LAR比較,在減少找尋路由路徑時所需的路由請求封包、降低點對點 (End -To-End) 的延遲及資料成功送達率,都有較佳的表現。在網路中節點數較多時,DLAR在封包送達率能有6%– 55%的改善,降低搜尋及維持路由時需要的控制封包量達40%以上,降低廣播風暴發生的機率, DLAR也同時在End-to-End Delay的表現較之於其他路由機制,有20%以上的改善。 zh_TW dc.description.abstract (摘要) In MANET the nodes may move fast and unpredictable, this may cause the original set up route well broken. Adopt those Reactive Routing Protocols may not only cause seriously data delivery delay but also produce a large number of control packages (RREQ) thus reducing network capacity. This is known as Broadcast Storm Problem. In this thesis, we proposed a routing protocol, Directive Location-Aided Routing (DLAR), that helps to choose appropriate relay nodes (intermediate nodes) in MANET. DLAR considers the node movement direction factor in deciding a stable route. Relay node is considered to be the same movement direction as source node. The goal is to maintain longer path lifetime, and make the broken very close to the destination node. DLAR adopts AODV to discovery route and accelerate the route recovery using Local Repair mechanism. Simulations show that as the network loading is high, DLAR can increase the packet delivery ratio by 6% ~ 55 % and increase the bandwidth utility by 40%, reduce the largely broadcast storm probability, and reduce end-to-end delay by 20%. en_US dc.description.tableofcontents 摘要.......................................................i ABSTRACT..................................................ii 致謝辭...................................................iii 目錄......................................................iv 表目錄....................................................vi 圖目錄...................................................vii 第一章 緒論................................................1 1.1 背景..................................................1 1.2 研究動機...............................................8 1.3 論文架構...............................................9 第二章 相關研究............................................11 2.1 廣播風暴..............................................11 2.1.1研究進程.............................................14 2.2 Location-Aided Routing (LAR).........................15 2.3 Local Repair Mechanism...............................18 第三章 研究方法............................................19 3.1 基本構想..............................................20 3.1.1 DLAR與PRAODV比較....................................21 3.1.2 考慮節點的移動方向....................................22 3.1.2 使用AODV做為LAR的路由搜尋機制.........................23 3.2 系統模型及環境假設......................................25 3.2.1 節點同方向性認定......................................25 3.2.2 控制封包擴充.........................................26 3.2.3維護及更新位置資訊.....................................28 3.3以節點移動方向輔助選擇合適中繼節點的策略...................28 3.3.1依據來源節點的移動方向.................................28 3.3.2演算法...............................................32 第四章 模擬結果及分析.......................................37 4.1 節點的分佈密度.........................................38 4.2 節點的移動速度.........................................43 4.3 節點連線需求數.........................................48 第五章結論與未來研究工作....................................54 參考文獻..................................................55 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0949710201 en_US dc.subject (關鍵詞) 行動隨意無線網路 zh_TW dc.subject (關鍵詞) 廣播風暴 zh_TW dc.subject (關鍵詞) 衛星定位 zh_TW dc.subject (關鍵詞) MANET en_US dc.subject (關鍵詞) Broadcast Storm en_US dc.subject (關鍵詞) Global Positioning System en_US dc.title (題名) MANET中利用節點移動方向降低廣播風暴發生之路由策略 zh_TW dc.title (題名) Direction-Based Routing Strategy to Reduce Broadcast Storm in MANET en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] “The Network Simulator NS-2,” http://www.isi.edu/nsnam/ns/, 2005. [2] Ahed M. Alshanyour and Uthman Baroudi, "Bypass AODV: improving performance of ad hoc on-demand distance vector (AODV) routing protocol in wireless ad hoc networks", IProceedings of the 1st international conference on Ambient media and systems, Quebec, Canada, February 11 - 14, 2008 [3] Josh Broch , David A. Maltz , David B. Johnson, Yih-Chun Hu , and Jorjeta Jetcheva , “A performance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’98), Dallas, Texas, U.S.A., October 1998, pp. 85 – 97. [4] C.-C. Chiang, H.-K. Wu, W. Liu, and M. Gerla, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel”, Proceedings IEEE SICON ’97, pp. 197–211, Apr. 1997. [5] S. Corson and J. Macker, “Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations,” RFC 2501, January 1999. RFC2501 [6] K.-T. Feng and T.-E. Lu, “Velocity and location aided routing for mobile ad hoc networks,” in Proc. IEEE 60th VTC—Fall, Los Angeles, CA, 2004, pp. 2789–2793. [7] K.T. Feng, C.H. Hsu, and T.E. Lu, “Velocity-Assisted Predictive Mobility and Location-Aware Routing Protocols for Mobile Ad Hoc Networks,” IEEE Trans. on Vehicular Technology, vol. 57, no. 1, pp. 448–464, 2008. [8] Z. Hass and M. Pearlman, “The Performance of Query Control Schemes for the Zone Routing Protocol,” ACM SIGCOMM, Aug. 1998, pp. 167-177. [9] D. B. Jhonson and D. A. Maltz, “Dynamic Source Routing in Ad Hoc Wireless Networks,” In Mobile Computing, Kluwere Academic Publishers, 1996, pp.153-181. [10] P. Jacquet and L. Viennot, “Overhead in Mobile Ad Hoc Network Protocols,” INRIA Research Report RR-3965, available at http://www.inria.fr/Equipes/HIPERCOM-eng.html, July 2000. [11] Y. B. Ko and N. H. Vaidya, “Location-Aided Routing (LAR) in Mobile Ad Hoc Networks,” in Proceedings of the ACM/IEEE International Conference on Mobile Computing and Networking (Mobicom), Dallas, Texas, USA, 1998, pp. 66-75. [12] V. Namboodiri, M. Agarwal, L. Gao, ”A Study on the Feasibility of Mobile Gateways for Vehicular Ad-hoc Networks”. In Proceedings of the First ACM International Workshop on Vehicular Ad-Hoc Networks, Philadelphia, June 2004. [13] C. E. Perkins and E. M. Royer, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computer,” Proceeding of the 1994 ACM Special Interest Group on Data Communication, London, UK, Sep. 1994, pp. 234-244 [14] C. E. Perkins; E. M. Royer, “Ad-hoc on-demand distance vector routing”, in Proc. IEEE WMCSA ’99, pp. 90-100, Feb. 1999. [15] C. E. Perkins, Ad Hoc Networking, Addison Wesley, 2001. [16] C. Perkins, E. Belding-Royer and S. Das “Ad-hoc on-demand distance vector (AODV) routing”, RFC3561, July 2003. [17] C. Perkins, E.M. Royer, S.R. Das, and M.K. Marina, Performance Comparison of Two On-demand Routing Protocols for Ad Hoc Networks, IEEE Personal Communications, pages 16-28, Feb. 2001. [18] E. Royer, and C.K. Toh, (1999), “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications Magazine, pp. 46-55 [19] Yu-Chee Tseng , Shib-Lin Wu , Wen-Hwa Liao and Chih-Min Chao , “Location Awareness in Ad Hoc Wireless Mobile Networks,” IEEE Computer, 2001, Page(s): 46 -52. [20] Y.-C. Tseng, S.-Y. Ni, Yuh-Shyan Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," ACM Wireless Networks (WINET), Vol. 8, No. 2, pp. 153-167, March 2002. (SCI) [21] Y.-C. Tseng, S.-Y. Ni, and E.-Y. Shih, Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc network, IEEE Transactions on Computers, vol. 52, no. 5, pp. 545-557, May 2003. [22] Y.-C. Tseng, S.-Y. Ni, Yuh-Shyan Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," ACM Wireless Networks, Vol. 8, No. 2, pp. 153-167, March 2002. zh_TW