移動隨意網路中以弱連結支配集為輔之基於蟻群的需求式分群路由演算法

簡易檢索 / 詳目顯示

回結果列表

研究生：	李坤翰 Kuen-Han Li
論文名稱：	移動隨意網路中以弱連結支配集為輔之基於蟻群的需求式分群路由演算法 Weakly Connected Dominating Set Assisted Ant-based On-demand Clustering Routing Protocol for Mobile Ad-hoc Network
指導教授：	呂政修 Jenq-Shiou Leu
口試委員:	石維寬 Wei-Kuan Shih 林木盛 Mu-Sheng Lin 陳省隆 Hsing-Lung Chen 鄭瑞光 Ray-Guang Cheng
學位類別：	碩士 Master
系所名稱：	電資學院 - 電子工程系 Department of Electronic and Computer Engineering
論文出版年：	2013
畢業學年度：	101
語文別：	中文
論文頁數：	56
中文關鍵詞：	蟻群優化演算法、需求式路由、弱連結支配集、移動隨意網路
外文關鍵詞：	Ant Colony Optimization (ACO), On-demand Routing, Weakly Connected Dominating Set (WCDS), Mobile Ad-hoc Network (MANET)
相關次數：	點閱：246 下載：10
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近年來在移動隨意網路(mobile ad-hoc network)技術的發展，促使了人們開發許多的新方法來增強網路的效能，其中最熱門的方法之一就是群體智慧(swarm intelligence)，透過模仿生物的集體行為來解決網路上的路由問題；同時，弱連結支配集(Weakly Connected Dominating Set，WCDS)可以提供一個輔助結構用以群集網路上的節點。此篇論文利用WCDS的群集概念在移動隨意網路上提出了一種基於螞蟻演算法的需求式群集路由協定(Ant-based On-demand Clustering Routing，AOCR)，網路上的狀態資訊可透過前行的螞蟻(Forward_Ant)中獲得，然後只會從每個群集的群首(cluster-head)廣播出去給其他的群集，從而降低了傳送螞蟻封包所需要的開銷，此外為了提高網路的效率，回退的螞蟻(Backward_Ant)採用了偽隨機比例選擇(pseudo-random-proportional-selection)的策略並根據節點的剩餘電量、網路平均剩餘電量以及路徑平均剩餘電量來評估出從起始節點到目的地節點的最佳路徑。最後在網路模擬器(Network Simulator version 2，NS-2)上的模擬結果顯示了本研究所提出的演算法在網路效能上比無基礎式需求距離向量路由協定(Ad-hoc On-demand Distance Vector，AODV)及傳統的螞蟻演算法來的更有效率。

Advances in wireless ad-hoc network techniques have spurred the development of new approaches to increase network efficiency. One of the more popular approaches is swarm intelligence, which imitates the collective behavior of biological species to solve network routing problems. Meanwhile, weakly connected dominating sets (WCDS) can serve as auxiliary structures for clustering nodes in the network. This paper uses the clustering concept of WCDS to propose an improved ant-based on-demand clustering routing (AOCR) protocol for wireless ad-hoc networks. Network state information is obtained from the Forward_Ant, and is only broadcast by the head of each cluster, thus decreasing the overhead required to transmit ant packets. To increase network efficiency, the pseudo-random-proportional-selection strategy is used to obtain the best path from the source node to the destination node by the Backward_Ant, based on the node’s residual energy, average network energy and average path energy. Simulation results on NS-2 show that our algorithm produces more network-efficiency than AODV or traditional ant-based algorithms.

論文摘要.................................................................I
ABSTRACT...............................................................II
誌謝..................................................................III
目錄...................................................................IV
圖片索引.................................................................V
表格索引................................................................VI
第 1 章	緒論............................................................1
第 2 章	相關研究.........................................................5
第 3 章	相關技術.........................................................8
3.1	無基礎式需求距離向量路由協定(Ad-hoc On-demand Distance Vector).......8
3.2	螞蟻路由演算法(Ant-based Routing Algorithm)......................11
3.3	弱連結支配集(Weakly Connected Dominating Set)....................14
第 4 章	Ant-based On-demand Clustering Routing的設計....................17
4.1	AOCR的介紹......................................................17
4.2	WCDS架構的形成...................................................18
4.3	網路探索........................................................22
第 5 章	模擬結果分析.....................................................27
5.1	效能指標........................................................27
5.2	模擬環境設定.....................................................29
5.3	模擬結果........................................................32
5.3.1.	靜態網路之模擬環境分析.............................................32
5.3.1.1	封包抵達率(Packet Delivery Ratio)...............................32
5.3.1.2	網路實際資料吞吐量(Network Goodput)..............................33
5.3.1.3	平均點對點延遲(Average End-to-End Delay)........................34
5.3.1.4	網路開銷(Network Overhead).....................................35
5.3.1.5	網路剩餘能量率(Network Residual Energy Ratio)...................36
5.3.2.	動態網路之模擬情境分析...........................................37
5.3.2.1.	封包抵達率(Packet Delivery Ratio)......................37
5.3.2.2.	網路實際資料吞吐量(Network Goodput)......................38
5.3.2.3.	平均點對點延遲(Average End-to-End Delay)................39
5.3.2.4.	網路剩餘能量率(Network Residual Energy Ratio)...........40
5.3.3.	費洛蒙蒸發率之影響...............................................41
第 6 章	結論及未來展望..................................................44
參考文獻...............................................................47

                                

[1] S. Corson and J. Macker, Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations: RFC Editor, 1999.
[2] M. Dorigo, M. Birattari, and T. Stutzle, "Ant Colony Optimization," Computational Intelligence Magazine, IEEE, vol. 1, pp. 28-39, 2006.
[3] O. Dagdeviren and K. Erciyes, "A Distributed Backbone Formation Algorithm for Mobile Ad Hoc Networks," presented at the Proceedings of the 4th international conference on Parallel and Distributed Processing and Applications, Sorrento, Italy, 2006.
[4] J. Y. Yu and P. H. J. Chong, "A Survey of Clustering Schemes for Mobile Ad Hoc Networks," Communications Surveys & Tutorials, IEEE, vol. 7, pp. 32-48, 2005.
[5] J. Wang, E. Osagie, P. Thulasiraman, and R. K. Thulasiram, "HOPNET: A Hybrid Ant Colony Optimization Routing Algorithm for Mobile Ad Hoc Network," Ad Hoc Networks, vol. 7, pp. 690-705, 2009.
[6] C. E. Perkins and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers," SIGCOMM Comput. Commun. Rev., vol. 24, pp. 234-244, 1994.
[7] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot, "Optimized Link State Routing Protocol for Ad Hoc Networks," in Multi Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International, 2001, pp. 62-68.
[8] W. Liu, C. Chiang, H. Wu, and C. Gerla, "Routing in Clustered Multihop Mobile Wireless Networks with Fading Channel," in Proc. IEEE SICON'97, 1997, pp. 197-211.
[9] C. E. Perkins and E. M. Royer, "Ad-hoc On-demand Distance Vector Routing," in Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA '99. Second IEEE Workshop on, New Orleans, LA, USA, 1999, pp. 90-100.
[10] D. Johnson and D. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks," in Mobile Computing. vol. 353, Imielinski and Korth, Eds., ed: Kluwer Academic Publishers, 1996.
[11] E. Weiss, G. R. Hiertz, and X. Bangnan, "Performance Analysis of Temporally Ordered Routing Algorithm based on IEEE 802.11a," in Vehicular Technology Conference, 2005. VTC 2005-Spring. 2005 IEEE 61st, 2005, pp. 2565-2569 Vol. 4.
[12] M. R. Pearlman and Z. J. Haas, "Determining the Optimal Configuration for the Zone Routing Protocol," Selected Areas in Communications, IEEE Journal on, vol. 17, pp. 1395-1414, 1999.
[13] M. Joa-Ng and I. T. Lu, "A Peer-to-Peer Zone-based Two-level Link State Routing for Mobile Ad Hoc Networks," Selected Areas in Communications, IEEE Journal on, vol. 17, pp. 1415-1425, 1999.
[14] V. Ramasubramanian, Z. J. Haas, and E. G. Sirer, "SHARP: A Hybrid Adaptive Routing Protocol for Mobile Ad Hoc Networks," presented at the Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, Annapolis, Maryland, USA, 2003.
[15] S. S. Iyengar, H.-C. Wu, N. Balakrishnan, and S.-Y. Chang, "Biologically Inspired Cooperative Routing for Wireless Mobile Sensor Networks," Systems Journal, IEEE, vol. 1, pp. 29-37, 2007.
[16] H. F. Wedde, M. Farooq, T. Pannenbaecker, B. Vogel, C. Mueller, J. Meth, and R. Jeruschkat, "BeeAdHoc: An Energy Efficient Routing Algorithm for Mobile Ad Hoc Networks Inspired by Bee Behavior," presented at the Proceedings of the 2005 conference on Genetic and evolutionary computation, Washington DC, USA, 2005.
[17] G. Di Caro and M. Dorigo, "AntNet: Distributed Stigmergetic Control for Communications Networks," Journal of Artificial Intelligence Research, vol. 9, pp. 317-365, 1998.
[18] M. Roth and S. Wicker, "Termite: Ad-Hoc Networking with Stigmergy," in Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE, 2003, pp. 2937-2941 vol.5.
[19] S. Chinara and S. K. Rath, "A Survey on One-Hop Clustering Algorithms in Mobile Ad Hoc Networks," J. Netw. Syst. Manage., vol. 17, pp. 183-207, 2009.
[20] F. D. Tolba, D. Magoni, and P. Lorenz, "A Stable Clustering Algorithm for Highly Mobile Ad Hoc Networks," presented at the Proceedings of the Second International Conference on Systems and Networks Communications, 2007.
[21] J. Sucec and I. Marsic, "Hierarchical routing overhead in mobile ad hoc networks," Mobile Computing, IEEE Transactions on, vol. 3, pp. 46-56, 2004.
[22] Y. P. Chen and A. L. Liestman, "Approximating Minimum Size Weakly-Connected Dominating Sets for Clustering Mobile Ad Hoc Networks," presented at the Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking \& computing, Lausanne, Switzerland, 2002.
[23] S. Guha and S. Khuller, "Approximation Algorithms for Connected Dominating Sets," Algorithmica, vol. 20, pp. 374-387, 1998.
[24] Y. P. Chen and A. L. Liestman, " A Zonal Algorithm for Clustering Ad Hoc Networks " International Journal of Foundations of Computer Science vol. 14 pp. 305-323 April 2003
[25] K.-H. Li, J.-S. Leu, and J. Hošek, "Ant-based On-demand Clustering Routing Protocol for Mobile Ad-hoc Networks," presented at the The 3rd International Workshop on Ad Hoc and Ubiquitous Computing (AHUC 2013), 2013.
[26] I. D. Chakeres and L. Klein-Berndt, "AODVjr, AODV Simplified," SIGMOBILE Mob. Comput. Commun. Rev., vol. 6, pp. 100-101, 2002.
[27] T. Camilo, C. Carreto, J. Silva, and F. Boavida, "An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks," ed, 2006, pp. 49-59.
[28] (June 14). AntSense - A NS-2 Module for Ant Colony Optimization. Available: http://eden.dei.uc.pt/~tandre/antsense/
[29] B. Han and W. Jia, "Clustering Wireless Ad Hoc Networks with Weakly Connected Dominating Set," J. Parallel Distrib. Comput., vol. 67, pp. 727-737, 2007.
[30] H. Bo and J. Weijia, "Efficient Construction of Weakly-Connected Dominating Set for Clustering Wireless Ad Hoc Networks," in Global Telecommunications Conference, 2006. GLOBECOM '06. IEEE, 2006, pp. 1-5.
[31] N. Chakchouk, B. Hamdaoui, and M. Frikha, "WCDS-Induced Routing for Data-Aggregation in Wireless Sensor Networks," in Communications and Networking, 2009. ComNet 2009. First International Conference on, 2009, pp. 1-6.
[32] B. Shuang, Z. Li, and J. Chen, "An Ant-Based On-Demand Energy Route Protocol for IEEE 802.15.4 Mesh Network," IJWIN, vol. 16, pp. 225-236, 2009.
[33] 柯志亨, 程榮祥, 鄧德雋, 謝錫堃, and 黃文祥, 計算機網路實驗—以NS2模擬工具實作: 學貫行銷股份有限公司, 2005.
[34] M.-S. Lin, J.-S. Leu, K.-H. Li, and J.-L. C. Wu, "TABOA: Terrain-Aware Beacon Order Adaptation Scheme in 3D Zigbee Sensor Networks," Wireless Communications, IEEE, vol. 20, pp. 122-128, 2013.
[35] M.-S. Lin, J.-S. Leu, W.-C. Yu, K.-H. Li, and J.-L. C. Wu, "TBRA: Termites Based Routing Algorithm in 3D Wireless Sensor Networks," in Vehicular Technology Conference (VTC Spring), 2012 IEEE 75th, 2012, pp. 1-5.
[36] M.-S. Lin, J.-S. Leu, K.-H. Li, and J.-L. C. Wu, "Zigbee-based Internet of Things in 3D Terrains," Computers & Electrical Engineering.
[37] W. Qinghua and Z. Tingting, "A multi-homing extension of wireless node implementation in NS-2," in Communications and Networking in China, 2009. ChinaCOM 2009. Fourth International Conference on, 2009, pp. 1-6.

簡易檢索 / 詳目顯示

相關論文