進階搜尋


 
系統識別號 U0026-0812200915033847
論文名稱(中文) 運用探索式分割法與知識推論解決隨建即連網路之群播路由問題
論文名稱(英文) Applying a Heuristic Partition Procedure and Knowledge-Based Inferences for Solving Multicast Routing Problems in Ad-hoc Networks
校院名稱 成功大學
系所名稱(中) 工程科學系碩博士班
系所名稱(英) Department of Engineering Science
學年度 97
學期 1
出版年 98
研究生(中文) 姜自強
研究生(英文) Tzu-Chiang Chiang
電子信箱 steve@mail.hku.edu.tw
學號 n9892105
學位類別 博士
語文別 英文
論文頁數 66頁
口試委員 口試委員-蔡尚榮
口試委員-陳澤生
口試委員-黃宗傳
指導教授-侯廷偉
口試委員-曾黎明
召集委員-陳祈男
口試委員-謝錫堃
中文關鍵字 無線隨建即連網路  知識推論演算法  探索式分割演算法  群播路由協定 
英文關鍵字 multicast routing protocol  knowledge-based inference  ad hoc networks  partition scheme 
學科別分類
中文摘要 隨建即連網路(ad hoc networks)中群播路由在合作式與分散式計算下扮演了一個重要的角色。本論文在無線隨建即連網路中探索群播路由發送問題,並提出二種協定機制,分別為(一) 具適應性雙向一致分割法的群播路由(AUPMR)與(二) 具知識推論的群播路由(KIMR)並運用模糊派翠網路( fuzzy Petri nets)。
AUPMR 由多個群播路由請求中產生一組近似優選的群播路由解答。作法是將多組群播路由請求分成二組解答並尋找有效的近似優選的一組解答,同時也有效率地解決大量群播路由請求問題。在我們的模擬實驗中顯示經由分割法選定的群播路由網路傳輸平均等待時間減少了38%,也模擬了無線網路架構下由8 個結點到64 個結點的擴展性網路效能,其中改善的效率達18%。
另一個我們要處理的群播路由問題為當群播路由選擇協定需要為一個新加入接收節點建立一條新路徑時,我們的KIMR方法可以減少由接收節點觸發而建立新的群播路由樹時的網路控制負荷。傳統上大多以最短路徑方法尋找新加入的接收節點與最近的向前傳輸節點(forwarding node)之間的一條最近的路徑,建立新的群播路由樹;但在一個碰撞嚴重的網路環境下卻未必是最好的解答,還需要考慮來源結點和群播成員之間距離、等待時間和傳輸封包的遺失等因素。所以,我們提出了一個基於知識推論演算法(KIMR)作為群播路由中為新加入的接收節點尋找一條有別於最短路徑演算法的新路徑演算法。KIMR演算法使得每個向前傳輸節點動態的可以學習並提供適合的網路條件,例如跳躍數(Hop counts)、鄰近節點數與路徑頻寬大小。在我們的模擬實驗結果中顯示,所提出的方法在網路封包傳遞下是具有效率的方法,與最差條件下的方法其中改善的效率達67%。
英文摘要 Multicast routing protocols play an important role in mobile ad hoc networks (MANETs) to support collaborative and distributed computing. This dissertation proposes two approaches to the multicast routing problems in MANETs: (1) Adaptive two-way uniform partition algorithm for multicast routing (AUPMR), and (2) A knowledge-based inference multicast routing (KIMR) using adaptive fuzzy Petri nets.
AUPMR finds a near-optimal routing solution for multicast requests by a heuristic partitioning algorithm. We consider scheduling a set of multicast requests each of which has a source node with multiple destinations respectively. Our heuristic method for partitioning arbitrary routing requests is both effective in finding a near-optimal solution, and efficient to solve large multicast requests. Our simulation shows that the average overall latency reduces up to 38%. We also find the network efficiency improvement is 18% comparing with the wireless mobile nodes from 8 nodes to 64 nodes.
KIMR is proposed to reduce the control overhead in the multicast tree construction initiated by the multicast receivers. Multicast routing protocols need a new path discovery algorithm for a newly joining node (receiver) in a MANET. Different from finding the shortest path from the source node to the new join node, our proposed method is to find the nearest forwarding node for a new node. The latter may increase the distance between the source node and the new members which would increase latency and packet loss, as compared with the shortest path algorithms. Therefore, we propose a knowledge-based inference approach for discovering a new path for a new node. KIMR is introduced at each node to learn and to adjust it to fit the dynamic conditions. The simulation results show that the proposed approach is more efficient about 67% in the packet delivery ratio as compared with the worst case of the bandwidth effective multicast routing protocol.
論文目次 中文摘要 I
ABSTRACT II
ACKNOWLEDGEMENT IV
CONTENTS V
LIST OF TABLES VI
LIST OF FIGURES VII

CHAPTER 1 INTRODUCTION 1
1.1 Definition of the problems 1
1.2 Paper contributions 2
1.3 Organization of this dissertation 3

CHAPTER 2 BACKGROUND STUDY AND OUR RELATED WORKS 4
2.1 Multicast routing in mobile ad hoc networks 4
2.2 An infrastructure of two-tier heterogeneous mobile ad hoc network architecture 5
2.3 The genetic algorithm for solving multicast routing problem 11
2.4 Bandwidth efficient multicast routing protocol 13

CHAPTER 3 ADAPTIVE TWO-WAY UNIFROM PARTITION ALGORITHM FOR MULTICAST ROUTING 14
3.1 Adaptive two-way uniform partition for multicast problems 14
3.2 An example PMRP multicast routing request problem 18
3.3 Simulation results and performances via NS-2 simulation 26
3.4 Summary 31

CHAPTER 4 A KNOWLEDGE-BASED INFERENCE MULTICAST PROTOCOL USING ADAPTIVE FUZZY NETS 32
4.1 Mapping fuzzy production rules into fuzzy Petri nets of a network topology 32
4.2 Knowledge representation of fuzzy logic based rules for multicast routing 35
4.3 Knowledge Inference based bandwidth-efficient Multicast Protocol 42
4.4 Simulation results 48
4.5 Summary 53

CHAPTER 5 CONCLUSION AND FUTURE WORKS 55
REFERENCES 57
APPENDIX 63
自述 66
參考文獻 [1] Huang Y. M., Chiang T. C., and Hou T. W.: “A Partition Network Model for Ad Hoc Networks in Overlay Environments”, Wireless Communication Mobile Computing, Vol. 6, Issue 5, pp. 711–725, 2006.
[2] Kumar Viswanath, Katia Obraczka and Gene Tsudik.: “Exploring Mesh and Tree-Based Multicast Routing Protocols for MANETs”, IEEE Transactions on Mobile Computing, Vol. 5, No. 1, pp. 28-42, 2006.
[3] Ayman El-Sayed and Vincent Roca, INRIA Rhone-Alpes.: “A Survey of Proposals for an Alternative Group Communication Service”, IEEE Network, Vol. 17, Issue 1, pp. 46-51, 2003.
[4] Shlomi Dolev, Elad Schiller, and Jennifer L. Welch.: “Random Walk for Self-Stabilizing Group Communication in Ad Hoc Networks”, IEEE Transactions on Mobile Computing, Vol. 5, No. 7, pp. 893-905, 2006.
[5] Sandrasegaran, K.; Prag, K.: “Planning Point-to-Multipoint Rural Radio Access Networks Using Expert Systems”, Expert Systems with Applications Vol. 17, Issue 3, pp. 145-166, October, 1999.
[6] Ashish Khisti, Uri Erez and Gregory W. Wornell.: “Fundamental Limits and Scaling Behavior of Cooperative Multicasting in Wireless Networks”, IEEE Transactions on Information Theory, Vol. 52, No. 6, pp. 2762-2770, 2006.
[7] Gregory V. Chockler, Idid Keidar and Roman Vitenberg.: ”Group communication specifications: a comprehensive study”, ACM Computing Surveys, Vol. 33, Issue 4, pp. 427 - 469 , 2001.
[8] Hui Cheng, Jiannong Cao and Xingwei Wang.: “A Heuristic Multicast Algorithm to Support QoS Group Communications in Heterogeneous Network”, IEEE Transactions on Vehicular Technology, Vol. 55, No. 3, pp. 831-838, 2006.
[9] Ki-Il Kim and Sang-Ha Kim.: “A Novel Overlay Multicast Protocol in Mobile Ad Hoc Networks: Design and Evaluation”, IEEE Transactions on Vehicular Technology, Vol. 54, No. 6, pp. 2094-2101, 2005.
[10] Li Lao and Jun-Hong Cui.: “Reducing Multicast Traffic Load for Cellular Networks Using Ad Hoc Networks”, IEEE Transactions on Vehicular Technology, Vol. 55, No. 3, pp. 822-830, 2006.
[11] Zongpeng Li and Baochun Li.: “Improving Throughput in Multihop Wireless Networks”, IEEE Transactions on Vehicular Technology, Vol. 55, No. 3, pp. 762-773, 2006.
[12] Wei Wei and Avideh Zakhor.: “Multiple Tree Video Multicast Over Wireless Ad Hoc Networks”, IEEE Transactions on Circuits And Systems for Video Technology, Vol. 17, No. 1, pp. 2-15, 2007.
[13] Wei Wei and Avideh Zakhor.: “Multipath, Unicast and Multicast Video Communication over Wireless Ad Hoc Networks”, Proceedings of the First International Conference on Broadband Networks, pp. 496-505, 2004.
[14] Iti Saha Misra, Debroop Poddar, Pushpak Nandi, Uttiya Santra, Srimoyee Panda.: “Congestion Control of Reliable Multi Path Source Routing in Ad-hoc Networks”, International Conference on Personal Wireless Communications, pp. 72-76, 2005.
[15] Ali Dasdan and Cevdet Aykanat.: “Two Novel Multiway Circuit Partitioning Algorithms Using Relaxed Locking”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 2, pp. 169-178, 1997.
[16] B. W. Kernighan and S. Lin.: “An Efficient Heuristic Procedure for Partitioning Graphs”, The Bell System Technical Journal, Vol. 49, No. 2, pp. 291-307, 1970.
[17] Lee SJ, Su W, Gerla M: “Wireless Ad Hoc Multicast Routing with Mobility Prediction”, Mobile Networks and Applications, Vol. 6, No. 4, pp. 351–360, 2001.
[18] Lee S, Gerla M, Chiang C: “On-demand Multicast Routing Protocol”, Proceedings of IEEE Wireless Communications and Networking, Vol. 3, pp. 1298–1302, 1999.
[19] Mao S, Cheng X, Thomas Y and Hanif D. Sherali: “Multiple Description Video Multicast in Wireless Ad Hoc Networks”, Mobile Networks and Applications, Vol. 11, No. 1, pp. 63–73, 2006.
[20] Toh C, Guichala G, and Bunchua S : “ABAM: On-Demand Associativity-Based Multicast Routing for Ad Hoc Mobile Networks”, Proceedings of IEEE Vehicular Technology Conference, Vol. 3, pp. 987–993, 2000.
[21] Wu C, Tay Y: “AMRIS: A Multicast Protocol for Ad Hoc Wireless Networks”, Proceedings of Military Communications Conference, Vol. 1, pp. 25–29, 1999.
[22] Xie J, Talpade R et al: “AMRoute: Adhoc Multicast Routing Protocol”, Mobile Networks, pp.429–439, 2002.
[23] Jubin J, Tornow JD: “The DARPA Packet Radio Network Protocols”, Proceeding of the IEEE; Vol. 75, No. 1, pp. 21–32, 1987.
[24] Chlamtac I, Pinter SS: ”Distributed Nodes Organization Algorithm for Channel Access in a Multihop Dynamic Radio Network”, IEEE Transactions on Computers, Vol. C-36, Issue 6, pp. 728–737, 1987.
[25] Sung-Ju L, Su W, Hsu J, Gerla M, “Bagrodia R. A Performance Comparison Study of Ad Hoc Wireless Multicast Protocols”, INFOCOM 2000, Nineteenth Annual Joint Conference of IEEE Computer and communications Societies, Proceedings, Vol. 2, pp. 565–574, 2000.
[26] Xie J, Talpade RR, Mcauley A, Liu M. “AMRoute: Ad Hoc Multicast Routing Protocol”, Mobile Networks and Applications, Vol. 7, No. 6, pp. 429–439, 2002.
[27] Wu C. W., Tay Y. C. “AMRIS: a Multicast Protocol for Ad Hoc Wireless Networks”, Military Communications Conference Proceedings, Vol. 1, pp. 25–29, 1999.
[28] Lee S. J, Gerla M, Chiang C. C.. “On-demand Multicast Routing Protocol”, Proceedings of IEEE Wireless Communications and Networking, Vol. 3, pp. 1298–1304, September 1999.
[29]. Garcia-Luna-Aceves JJ, Madruga EL. “Core-assisted Mesh Protocol”, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, pp. 784–792, 1999.
[30] Baker DJ, Ephremides A. “The Architectural Organization of a Mobile Radio Network via a Distributed Algorithm”, IEEE Transactions on Communications, Vol. 29, No. 11, pp. 1694–1701, 1981.
[31] Huang C. F., Lee H. W., and Tseng Y. C.: “A Two-tier Heterogeneous Mobile Ad Hoc Network Architecture and Its Load-balance Routing Problem”, Mobile networks and applications, Vol. 9, No. 4, pp. 379-391, 2004.
[32] Zongpeng Li, Baochun Li and Lap Chi Lau.: “On Achieving Maximum Multicast Throughput in Undirected Networks”, IEEE Transactions on Information Theory, Vol. 52, No. 6, pp. 2467-2485, 2006.
[33] Pablo Galiasso, Roger L. Wainwright. “A Hybrid Genetic Algorithm for the Point to Multipoint Routing Problem with Single Split Paths”, Proceedings of ACM symposium on Applied computing, pp. 263-268, 2001.
[34] Liming Zhu; Wainwright, R.L.; Schoenefeld, D.A. “A Genetic Algorithm for the Point to Multipoint Routing Problem with Varying Number of Requests”, Evolutionary Computation Proceedings, IEEE World Congress on Computational Intelligence, pp. 77-89, 1998.
[35] Thang Nguyen Bui and Byung Ro Moon.: “Genetic Algorithm and Graph Partitioning”, IEEE Transactions on Computers, Vol. 45, No. 7, pp. 841-855, 1996.
[36] Weifa Liang.: ”Approximate Minimum-Energy Multicasting in Wireless Ad Hoc Networks”, IEEE Transactions on Mobile Computing, Vol. 5, No. 4, 377-287, 2006.
[37] Hui Cheng, Jiannong Cao and Xingwei Wang. “A Heuristic Multicast Algorithm to Support QoS Group Communications in Heterogeneous Network”, IEEE Transactions on Vehicular Technology, Vol. 55, No. 3, pp. 831-838, 2006.
[38] Tomochika Ozaki, Jaime Bae Kim, and Tatsuya Suda. “Bandwidth-Efficient Multicast Routing for Multihop Ad-Hoc Wireless Networks”, IEEE INFOCOM, Vol. 2, pp. 1182-1191, 2001.
[39] Weifa Liang. “Approximate Minimum-Energy Multicasting in Wireless Ad Hoc Networks”, IEEE Transactions on Mobile Computing, Vol. 5, No. 4, pp. 277-287, 2006.
[40] Wei-Po Lee. “Deploying Personalized Mobile Services in an Agent-based Environment”, Expert Systems with Applications, Vol. 32, Issue 4, pp. 1194-1207, 2007.
[41] Shyi-Ming Chen, Jyh-Sheng, and Jin-Fu Chang. “Knowledge Representation using Fuzzy Petri Nets”, IEEE Transactions on Knowledge and Data Engineering, Vol. 2, No. 3, pp. 311-319, 1990.
[42] X. Li, F Lara-Rosano. “Adaptive fuzzy petri nets for dynamic knowledge representation and inference”, Expert Systems with Applications Vol. 19, Issue 3, pp. 235-241, 2000.
[43] Tzu-Chiang Chiang and Yueh-Min Huang. “Multicast Routing Representation in Ad Hoc Networks Using Fuzzy Petri Nets”, The 18th International Conference on Advanced Information Networking and Applications, Vol. 2, pp. 1- 4, 2004.
[44] Li Lao and Jun-Hong Cui. “Reducing Multicast Traffic Load for Cellular Networks Using Ad Hoc Networks”, IEEE Transactions on Vehicular Technology, Vol. 55, No. 3, pp. 822-830, 2006.
[45] Sandrasegaran, K.; Prag, K. “Planning Point-to-multipoint Rural Radio Access Networks Using Expert Systems”, Expert Systems with Applications Vol. 17, Issue 3, pp. 145-166, 1999.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2008-12-11起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2008-12-11起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw