基于蚁群协作模型的P2P网络研究
|
摘要
目前,对等网络(P2P:Peer-to-Peer)技术,充斥着我们网络生活的方方面面,在文件共享、分布计算和分布存储等方面已经取得了巨大成功。但是,目前存在的四种主要拓扑类P2P网络也显现了许多的问题,如:监管问题、流量问题、可靠性问题。这些问题的出现严重影响了P2P网络的形象和用户的使用体验。
本文主要针对目前P2P网络中的流量问题、网络稳定性问题、网络资源利用率问题进行研究,采用的是蚁群和蚁群算法模式构建协作机制的P2P网络模型来对这些问题进行探讨研究解决。在蚂蚁社群组织结构的启示下本文提出了基于协作模型的P2P网络,该模型最大的特色是网络中所有角色结点均有普通参与者来担任,网络中新增了候补结点和超级结点的选举机制,网络中的集群可以创建和注销,网络中的消息转发在超级结点间进行,旨在提高网络的可扩展性和可靠性可维护性和支持复杂查询。基于改进的应用于协作模型P2P网络的综合考虑信息素蚁群算法的设计,该设计在传统的蚁群算法基础上对于信息素进行了新的设计,信息素的含量代表的是网络结点中拥有资源和质量的综合评价,能帮助提高资源查找命中率和查询满意率。
最后,对于整个协作模型P2P网络的整体性能分析和仿真,切实论证了在全员参与的模式下的协作模型的P2P网络能够很好的解决网络的扩展性、可靠性、可维护性、能够支持复杂查询和部署基于集群算法的资源查询方式,网络中部署的综合信息素蚁群算法的资源查找方式在衡量算法效率的:平均查找跳数、查找满意率、查找效率三个衡量标准上表现优秀。综合评定,协作模型的P2P网络在目前的P2P网络基础上,性能有了较大的提高。
Nowadays, the P2P( Peer to Peer ) technology is all around our network-life, it’s already make great success in file-sharing, distributing computing and storing field. But the main kind of P2P network still have a lot of problems, such as hard to supervise, occupying too much traffic, bad reliability. The problems above bring big trouble to the impression of P2P technology and the using experience of P2P-user.
This thesis focus on the traffic problem, network stability problem, network efficiency problem. The resolvent of these problems solve under the inspiration of the ant colony, and bring forward a new truss of P2P network, that is P2P Network Based on Cooperative Mode, the main feature of this network is all the task finish by the common participator and create a new role called backup-node, and make a rule of voting for super-node, so when the super-node of the network breakdown, there is a reliable node take on the mission of manipulating the system. The P2P network with this mode has better expansibility and dependability and easier to conduct. In the system, the assemblies could register and logout, and this make the system performs better in the expansibility. A new version of ACO( Ant Colony Optimization ) based on integrate examination of the node in the network is advanced, in order to raise the finding efficiency and the finding hits.
At last, the analysis and simulate result that, under the cooperative mode, the P2P system shows good expansibility, reliability, maintenance, support complex query, easy to deploy the ACO. The performance of the modified ACO tests in three criterions: Ave rage finding step, finding satisfaction, finding efficiency, and the outcome illuminates that the arithmetic is excellent. Anyway, considering all the aspects of the P2P network, the cooperative mode P2P network is better than the other mode.
本文主要针对目前P2P网络中的流量问题、网络稳定性问题、网络资源利用率问题进行研究,采用的是蚁群和蚁群算法模式构建协作机制的P2P网络模型来对这些问题进行探讨研究解决。在蚂蚁社群组织结构的启示下本文提出了基于协作模型的P2P网络,该模型最大的特色是网络中所有角色结点均有普通参与者来担任,网络中新增了候补结点和超级结点的选举机制,网络中的集群可以创建和注销,网络中的消息转发在超级结点间进行,旨在提高网络的可扩展性和可靠性可维护性和支持复杂查询。基于改进的应用于协作模型P2P网络的综合考虑信息素蚁群算法的设计,该设计在传统的蚁群算法基础上对于信息素进行了新的设计,信息素的含量代表的是网络结点中拥有资源和质量的综合评价,能帮助提高资源查找命中率和查询满意率。
最后,对于整个协作模型P2P网络的整体性能分析和仿真,切实论证了在全员参与的模式下的协作模型的P2P网络能够很好的解决网络的扩展性、可靠性、可维护性、能够支持复杂查询和部署基于集群算法的资源查询方式,网络中部署的综合信息素蚁群算法的资源查找方式在衡量算法效率的:平均查找跳数、查找满意率、查找效率三个衡量标准上表现优秀。综合评定,协作模型的P2P网络在目前的P2P网络基础上,性能有了较大的提高。
Nowadays, the P2P( Peer to Peer ) technology is all around our network-life, it’s already make great success in file-sharing, distributing computing and storing field. But the main kind of P2P network still have a lot of problems, such as hard to supervise, occupying too much traffic, bad reliability. The problems above bring big trouble to the impression of P2P technology and the using experience of P2P-user.
This thesis focus on the traffic problem, network stability problem, network efficiency problem. The resolvent of these problems solve under the inspiration of the ant colony, and bring forward a new truss of P2P network, that is P2P Network Based on Cooperative Mode, the main feature of this network is all the task finish by the common participator and create a new role called backup-node, and make a rule of voting for super-node, so when the super-node of the network breakdown, there is a reliable node take on the mission of manipulating the system. The P2P network with this mode has better expansibility and dependability and easier to conduct. In the system, the assemblies could register and logout, and this make the system performs better in the expansibility. A new version of ACO( Ant Colony Optimization ) based on integrate examination of the node in the network is advanced, in order to raise the finding efficiency and the finding hits.
At last, the analysis and simulate result that, under the cooperative mode, the P2P system shows good expansibility, reliability, maintenance, support complex query, easy to deploy the ACO. The performance of the modified ACO tests in three criterions: Ave rage finding step, finding satisfaction, finding efficiency, and the outcome illuminates that the arithmetic is excellent. Anyway, considering all the aspects of the P2P network, the cooperative mode P2P network is better than the other mode.
引文
[1] Korpela, E., Werthimer, D., Anderson, D., Cobb, J., and Lebofsky, M. SETI@home: Massively distributed computing for SETI. Comput. Sci. Engin. 3, 1 (Jan.--Feb. 2001), 79.
[2] A. Louveau, S. Shelah and B. VelickoviC, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic, 63 (1993), 271-281.
[3] L. Jianming, C. Xueqi, J. Qing, Y. Jing, Z. Tieying, L. Iming, and W. Lei, "LiveBT: Providing Video-on-Demand Streaming Service over BitTorrent Systems," in Parallel and Distributed Computing, Applications and Technologies, 2007. PDCAT '07. Eighth International Conference on, 2007, pp. 501-508.
[4] S.A. Baset, H. Schulzrinne, An analysis of the skype peer-to-peer internet telephony protocol, IEEE Infocom'06, Barcelona, Spain, April 2006.
[5] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz. Maintenance free global storage in oceanstore. In Proc. of IEEE Internet Computing. IEEE, September 2001.
[6] Y. Yun, L. Ke, C. Jinjun, L. Xiao, Y. Dong, and J. Hai, "An Algorithm in SwinDeW-C for Scheduling Transaction-Intensive Cost-Constrained Cloud Workflows," in eScience, 2008. eScience '08. IEEE Fourth International Conference on, 2008, pp. 374-375.
[7] E. P. Markatos. Tracing a large scale peer to peer system: an hour in life of gnutella. Second IEEE/ACM International Symposium on Cluster Computing and the Grid, 2002.
[8] N. Leibowitz, M. Ripeanu, and A. Wierzbicki, "Deconstructing the Kazaa network," in Internet Applications. WIAPP 2003. Proceedings. The Third IEEE Workshop on, 2003, pp. 112-120.
[9] T. J. Harmer, J. McCabe, P. Donachy, R. H. Perrott, C. Chambers, S. Craig, R. Lewis, B. Mallon, and L. Sluman, "Gridcast: a grid and Web service broadcast infrastructure," in Services Computing, 2005 IEEE International Conference on, 2005, pp. 35-42 vol.1.
[10] J. Hai, Y. Hong, L. Xiaofei, Y. Sirui, L. Wei, and J. Yong, "PKTown: A Peer-to-Peer Middleware to Support Multiplayer Online Games," in Multimedia and Ubiquitous Engineering, 2007. MUE '07. International Conference on, 2007, pp. 54-59.
[11] Y. Lingna, W. Wenxiang, W. Yanyu, and G. Yubin, "Approach to a Coaxial Arbitrary-Shaped Groove Cylindrical Waveguide for Application in Wideband Gyro-TWTs," Plasma Science, IEEE Transactions on, vol. 35, pp. 551-558, 2007.
[12] S. K. Basu, "DHT: diagonally hybridized tree is an efficient VLSI structure for parallel computation," in TENCON 90. 1990 IEEE Region 10 Conference on Computer and Communication Systems, 1990, pp. 514-518 vol.2.
[13] M. Kubo and Y. Kakazu, "Simulating a competition for foods between ant colonies as a coordinated model of autonomous agents," in Systems, Man and Cybernetics, 1993. 'Systems Engineering in the Service of Humans', Conference Proceedings.,International Conference on, 1993, pp. 142-148 vol.5.
[14] Y. Xue-song, L. Han-min, Y. Jia, and W. Qing-hua, "A Fast Evolutionary Algorithm for Traveling Salesman Problem," in Natural Computation, 2007. ICNC 2007. Third International Conference on, 2007, pp. 85-90.
[15] H.-B. Shan and S. Li, "The Comparison Between Genetic Simulated Annealing Algorithm and Ant Colony Optimization Algorithm for ASP," in Wireless Communications, Networking and Mobile Computing, 2008. WiCOM '08. 4th International Conference on, 2008, pp. 1-6.
[16] A. V. Naik and A. L. Selman, "A note on p-selective sets and on adaptive versus nonadaptive queries to NP," in Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on, 1996, pp. 224-232.
[17] N. Wakamiya and M. Murata, "Overlay Network Symbiosis: Evolution and Cooperation," in Bio-Inspired Models of Network, Information and Computing Systems, 2006. 1st, 2006, pp. 1-5.
[18] Bakos, Y. The emerging role of electronic marketplaces on the internet. Commun. ACM 41, 8 (Aug. 1998), 35-42.
[19] Carlson, J.M. and Doyle, J. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Review E60, 2 (Aug. 1999), 1412--1427.
[20] H. Ekiz, A. Kutlu, and E. T. Powner, "Design and implementation of a CAN/CAN bridge," in Parallel Architectures, Algorithms, and Networks, 1996. Proceedings. Second International Symposium on, 1996, pp. 507-513.
[21] N. C. Maddage, M. S. Kankanhalli, and L. Haizhou, "A Hierarchical Approach for Music Chord Modeling Based on the Analysis of Tonal Characteristics," in Multimedia and Expo, 2006 IEEE International Conference on, 2006, pp. 945-948.
[22] J. Chen and L. Wang, "Improved Hierarchical Network Model Based on Pastry Scheme," in Knowledge Discovery and Data Mining, 2009. WKDD 2009. Second International Workshop on, 2009, pp. 859-862.
[23] B. Y. Zhao, H. Ling, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, "Tapestry: a resilient global-scale overlay for service deployment," Selected Areas in Communications, IEEE Journal on, vol. 22, pp. 41-53, 2004.
[24] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, pp. 29-41, 1996.
[25] S. Lin and B. W. Kernighan,“An effective heuristic algorithm for theTSP,”Oper. Res., vol. 21, 498-516, 1973.
[26]李绍滋,曹阳,周昌乐.基于非结构化的P2P信息检索关键技术研究[J].智能系统学报, 2006,(02) .
[27]李建春,赵宗渠. P2P中基于蚁群算法的智能搜索研究[J].科技资讯, 2006,(04).
[28]赵宏,谢伟志,张晨曦.基于蚁群算法的非结构化P2P搜索研究[J].计算机技术与发展, 2009,(02)
[29]蓝慧琴,钟诚,李智.一种基于蚁群算法的非结构化P2P网络搜索算法[J].计算机技术与发展, 2006,(10)
[30]伍乐生.一种改进的基于蚁群算法的P2P搜索研究[J].科技信息(科学教研), 2007,(34) .
[31]吴湘宁,汪渊.基于蚁群算法的P2P文件共享系统[J].计算机工程与应用,2007,(20)
[32]候孟书,卢显良,周旭,詹川.系统的信任研究[J].计算机科学, 2005, 32(4).
[33] M. Barbera, A. Lombardo, G. Schembra, and M. Tribastone, "A Markov model of a freerider in a BitTorrent P2P network," in Global Telecommunications Conference, 2005. GLOBECOM '05. IEEE, 2005, p. 5 pp.
[34] G. Philippe, L. B. Kevin, M. Ilya, et al.Incentives for Sharing in Peer-to-Peer Networds[C]. Proceedings of the ACM Conference on Electronic Commerce. Tampa:DBLP, 2001.
[35] B. Yang, H. GMolina. Micorpayments for Peer-to-Peer Systems[C].Proceeding of the 10th ACM Conference on Computer and Communications Security. Washington: ACM press, 2003.
[36] J.Ioannidis, S.Ioannidis, A.D.Keromytis,et al.Fileteller:Paying and Geting Paid for File Storage[C]. In: Proceedings of the Sixth Annual Conference on Financial Cryptography. Bermuda: Springer-Verlag,2002.
[37] S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina.Incentives for Combating Freeriding on P2P Networks[C]. In Euro-Par 2003. June, 2003..
[38] R. T. B.Ma, S.C.M.Lee, J. C. S. Lui, et al. An Incentive Mechanism for P2P Networks[C]. In Proceedings of the 24th International Conference on Distributed Computing Systems, 2004. March, 2004.
[39] Q. Sun, H. Garcia-Molina. SLIC: A Selfish Link-Based Incentive Mechanism for Unstructuerd Peer-to-Peer Networks[C]. In ICDCS, 2004.
[40] W. Kejun, J. Hongzhang, and L. Guobin, "Synthetical backpropagation algorithm," in Intelligent Processing Systems, 1997. ICIPS '97. 1997 IEEE International Conference on, 1997, pp. 458-462 vol.1.
[2] A. Louveau, S. Shelah and B. VelickoviC, Borel partitions of infinite subtrees of a perfect tree, Annals of Pure and Applied Logic, 63 (1993), 271-281.
[3] L. Jianming, C. Xueqi, J. Qing, Y. Jing, Z. Tieying, L. Iming, and W. Lei, "LiveBT: Providing Video-on-Demand Streaming Service over BitTorrent Systems," in Parallel and Distributed Computing, Applications and Technologies, 2007. PDCAT '07. Eighth International Conference on, 2007, pp. 501-508.
[4] S.A. Baset, H. Schulzrinne, An analysis of the skype peer-to-peer internet telephony protocol, IEEE Infocom'06, Barcelona, Spain, April 2006.
[5] S. Rhea, C. Wells, P. Eaton, D. Geels, B. Zhao, H. Weatherspoon, and J. Kubiatowicz. Maintenance free global storage in oceanstore. In Proc. of IEEE Internet Computing. IEEE, September 2001.
[6] Y. Yun, L. Ke, C. Jinjun, L. Xiao, Y. Dong, and J. Hai, "An Algorithm in SwinDeW-C for Scheduling Transaction-Intensive Cost-Constrained Cloud Workflows," in eScience, 2008. eScience '08. IEEE Fourth International Conference on, 2008, pp. 374-375.
[7] E. P. Markatos. Tracing a large scale peer to peer system: an hour in life of gnutella. Second IEEE/ACM International Symposium on Cluster Computing and the Grid, 2002.
[8] N. Leibowitz, M. Ripeanu, and A. Wierzbicki, "Deconstructing the Kazaa network," in Internet Applications. WIAPP 2003. Proceedings. The Third IEEE Workshop on, 2003, pp. 112-120.
[9] T. J. Harmer, J. McCabe, P. Donachy, R. H. Perrott, C. Chambers, S. Craig, R. Lewis, B. Mallon, and L. Sluman, "Gridcast: a grid and Web service broadcast infrastructure," in Services Computing, 2005 IEEE International Conference on, 2005, pp. 35-42 vol.1.
[10] J. Hai, Y. Hong, L. Xiaofei, Y. Sirui, L. Wei, and J. Yong, "PKTown: A Peer-to-Peer Middleware to Support Multiplayer Online Games," in Multimedia and Ubiquitous Engineering, 2007. MUE '07. International Conference on, 2007, pp. 54-59.
[11] Y. Lingna, W. Wenxiang, W. Yanyu, and G. Yubin, "Approach to a Coaxial Arbitrary-Shaped Groove Cylindrical Waveguide for Application in Wideband Gyro-TWTs," Plasma Science, IEEE Transactions on, vol. 35, pp. 551-558, 2007.
[12] S. K. Basu, "DHT: diagonally hybridized tree is an efficient VLSI structure for parallel computation," in TENCON 90. 1990 IEEE Region 10 Conference on Computer and Communication Systems, 1990, pp. 514-518 vol.2.
[13] M. Kubo and Y. Kakazu, "Simulating a competition for foods between ant colonies as a coordinated model of autonomous agents," in Systems, Man and Cybernetics, 1993. 'Systems Engineering in the Service of Humans', Conference Proceedings.,International Conference on, 1993, pp. 142-148 vol.5.
[14] Y. Xue-song, L. Han-min, Y. Jia, and W. Qing-hua, "A Fast Evolutionary Algorithm for Traveling Salesman Problem," in Natural Computation, 2007. ICNC 2007. Third International Conference on, 2007, pp. 85-90.
[15] H.-B. Shan and S. Li, "The Comparison Between Genetic Simulated Annealing Algorithm and Ant Colony Optimization Algorithm for ASP," in Wireless Communications, Networking and Mobile Computing, 2008. WiCOM '08. 4th International Conference on, 2008, pp. 1-6.
[16] A. V. Naik and A. L. Selman, "A note on p-selective sets and on adaptive versus nonadaptive queries to NP," in Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on, 1996, pp. 224-232.
[17] N. Wakamiya and M. Murata, "Overlay Network Symbiosis: Evolution and Cooperation," in Bio-Inspired Models of Network, Information and Computing Systems, 2006. 1st, 2006, pp. 1-5.
[18] Bakos, Y. The emerging role of electronic marketplaces on the internet. Commun. ACM 41, 8 (Aug. 1998), 35-42.
[19] Carlson, J.M. and Doyle, J. Highly optimized tolerance: A mechanism for power laws in designed systems. Physical Review E60, 2 (Aug. 1999), 1412--1427.
[20] H. Ekiz, A. Kutlu, and E. T. Powner, "Design and implementation of a CAN/CAN bridge," in Parallel Architectures, Algorithms, and Networks, 1996. Proceedings. Second International Symposium on, 1996, pp. 507-513.
[21] N. C. Maddage, M. S. Kankanhalli, and L. Haizhou, "A Hierarchical Approach for Music Chord Modeling Based on the Analysis of Tonal Characteristics," in Multimedia and Expo, 2006 IEEE International Conference on, 2006, pp. 945-948.
[22] J. Chen and L. Wang, "Improved Hierarchical Network Model Based on Pastry Scheme," in Knowledge Discovery and Data Mining, 2009. WKDD 2009. Second International Workshop on, 2009, pp. 859-862.
[23] B. Y. Zhao, H. Ling, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, "Tapestry: a resilient global-scale overlay for service deployment," Selected Areas in Communications, IEEE Journal on, vol. 22, pp. 41-53, 2004.
[24] M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 26, pp. 29-41, 1996.
[25] S. Lin and B. W. Kernighan,“An effective heuristic algorithm for theTSP,”Oper. Res., vol. 21, 498-516, 1973.
[26]李绍滋,曹阳,周昌乐.基于非结构化的P2P信息检索关键技术研究[J].智能系统学报, 2006,(02) .
[27]李建春,赵宗渠. P2P中基于蚁群算法的智能搜索研究[J].科技资讯, 2006,(04).
[28]赵宏,谢伟志,张晨曦.基于蚁群算法的非结构化P2P搜索研究[J].计算机技术与发展, 2009,(02)
[29]蓝慧琴,钟诚,李智.一种基于蚁群算法的非结构化P2P网络搜索算法[J].计算机技术与发展, 2006,(10)
[30]伍乐生.一种改进的基于蚁群算法的P2P搜索研究[J].科技信息(科学教研), 2007,(34) .
[31]吴湘宁,汪渊.基于蚁群算法的P2P文件共享系统[J].计算机工程与应用,2007,(20)
[32]候孟书,卢显良,周旭,詹川.系统的信任研究[J].计算机科学, 2005, 32(4).
[33] M. Barbera, A. Lombardo, G. Schembra, and M. Tribastone, "A Markov model of a freerider in a BitTorrent P2P network," in Global Telecommunications Conference, 2005. GLOBECOM '05. IEEE, 2005, p. 5 pp.
[34] G. Philippe, L. B. Kevin, M. Ilya, et al.Incentives for Sharing in Peer-to-Peer Networds[C]. Proceedings of the ACM Conference on Electronic Commerce. Tampa:DBLP, 2001.
[35] B. Yang, H. GMolina. Micorpayments for Peer-to-Peer Systems[C].Proceeding of the 10th ACM Conference on Computer and Communications Security. Washington: ACM press, 2003.
[36] J.Ioannidis, S.Ioannidis, A.D.Keromytis,et al.Fileteller:Paying and Geting Paid for File Storage[C]. In: Proceedings of the Sixth Annual Conference on Financial Cryptography. Bermuda: Springer-Verlag,2002.
[37] S. D. Kamvar, M. T. Schlosser, H. Garcia-Molina.Incentives for Combating Freeriding on P2P Networks[C]. In Euro-Par 2003. June, 2003..
[38] R. T. B.Ma, S.C.M.Lee, J. C. S. Lui, et al. An Incentive Mechanism for P2P Networks[C]. In Proceedings of the 24th International Conference on Distributed Computing Systems, 2004. March, 2004.
[39] Q. Sun, H. Garcia-Molina. SLIC: A Selfish Link-Based Incentive Mechanism for Unstructuerd Peer-to-Peer Networks[C]. In ICDCS, 2004.
[40] W. Kejun, J. Hongzhang, and L. Guobin, "Synthetical backpropagation algorithm," in Intelligent Processing Systems, 1997. ICIPS '97. 1997 IEEE International Conference on, 1997, pp. 458-462 vol.1.