基于改进型蚁群算法的P2P网络资源搜索的研究

doi:10.3969/j.issn.1000-0801.2012.03.010

摘要/Abstract

摘要：

目前P2P网络中的资源搜索算法以泛洪法为核心，产生的巨大网络流量加重了网络负载，只适合小型网络。蚁群优化算法具有较好的鲁棒性、并行性等优点，已有不少学者将其应用于P2P资源搜索。本文在分析蚁群算法应用于P2P网络中资源搜索面临的问题的基础上，给出一个适合蚁群算法的新型的P2P文件共享构架，以解决P2P路由的不一致性等问题。在P2P网络中应用能见度会带来3个缺点：容易导致局部极小解、容易导致流量集中、实际网络中的实现有较大难度，由此本文提出了去能见度蚁群算法。构建了开放式的网络仿真拓扑结构，通过一系列的实验结果验证了去能见度蚁群算法的全局能力更强。

关键词: 蚁群算法, P2P, 能见度, 资源搜索

Abstract:

The resource search algorithm in P2P networks is mainly based on flooding algorithm.However,flooding algorithm is only suitable for small networks due to the huge traffic caused by it.Ant algorithm has many advantages such as robustness and parallelism to name a few,and many researchers have already used it for resource search in P2P networks.This paper analyzes the problems when using ant algorithms in P2P networks,and then proposes a new P2P network architecture which is more suitable for ant algorithm.An open network architecture for simulation is then presented.Visibility is always one of two basic elements of ant algorithm.However,this paper shows that using visibility in P2P networks will cause three disadvantages: to result in local minimum,to make flux convergent and to make the realization of the ant colony algorithm difficult.This paper presents a new ant algorithm without visibility.A series of experiments show that the global ability of the new algorithm is better than that of others.

Key words: ant algorithm, P2P, visibility, resource search

蔡康. 基于改进型蚁群算法的P2P网络资源搜索的研究[J]. 电信科学, 2012, 28(3): 32-42.

Kang Cai. Study on Resource Search in P2P Networks Based on Improved Ant Algorithm[J]. Telecommunications Science, 2012, 28(3): 32-42.

图/表 12

图1

图2

图3

图4

图5

表1

表2

图6

图7

图8

表3

表4

参考文献 22

1	Dorigo M , Maniezzo V , Colorni A . Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems,Man and Cybernetics,Part B: Cybernetics, 1996,26(1): 29～41
2	Stützle T , Hoos H . The max-min ant system and local search for the traveling salesman problem. Proceedings of IEEE-ICEC-EPS' 97,IEEE International Conference on Evolutionary Computation and Evolutionary Programming Conference,IEEE Press, 1997: 309～314
3	Stützle T , Hoos H . Improvements on the ant system: introducing max-min ant system. Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien, 1997: 245～249
4	Stützle T , Hoos H . Max-min ant system and local search for combinatorial optimization problems. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer,Bosto, 1998: 137～154
5	Stützle T . Max-min Ant System for Quadratic Assignment Problems. Technical Report AIDA-97-04,Intellectics Group,Department of Computer Science, Darmstadt University of Technology,Germany, 1997
6	吴庆洪，张纪会，徐心和 . 具有变异特征的蚁群算法. 计算机研究与发展， 1999，36（10）: 1240～1245
7	Marcin L P , Tony W . Using genetic algorithms to optimize ACS-TSP. Proceedings of 3rd Int Workshop ANTS, Brussels, 2002: 282～287
8	Chi-Jen Wu , Kai-Hsiang Yang , Jan-Ming Ho . An ant search algorithm in unstructured Peer-to-Peer networks. Proceedings of the 11th IEEE Symposium on Computers and Communications, 2006
9	Junqing Li , Quanke Pan , Shengxian Xie . Research on peer selection in Peer-to-Peer networks using ant colony optimization. Proceedings of the Fourth International Conference on Natural Computation, 2008
10	Walter J , Gutjahr . ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters, 2002(82): 145～153
11	吴湘宁，汪渊 . 基于蚁群算法的P2P文件共享系统. 计算机工程与应用， 2007，43（20）: 145～148
12	刘萍，高飞，杨云 . 基于遗传算法和蚁群算法融合的QoS路由算法. 计算机应用研究， 2007，24（9）: 224～227
13	刘永娟 . 改进蚁群算法在QoS路由中的应用与研究. 通信技术， 2008，41（9）: 128～133
14	陈岩，杨华江，沈林成 . 基于再励学习蚁群算法的多约束QoS路由方法. 计算机科学， 2007，134（15）: 25～44
15	杨华江，陈岩，沈林成 . 基于改进蚁群算法的多约束QoS路由方法. 计算机应用与软件， 2008，25（5）: 15～17
16	Wu C J , Yang K H , Ho J M . Antsearch: an ant search algorithm in unstructured peer-to-peer networks. Proceedings of the 11th IEEE Symposium on Computers and Communications, Cagliari, 2006: 429～434
17	Wu G Y , Liu J Y , Shen X , et al. ERAntBudget: a search algorithm in unstructured P2P networks. Proceedings of the Second International Symposium on Intelligent Information Technology Application, Shanghai, 2008: 765～769
18	Li J Q , Pan Q K , Xie S X . Research on peer selection in peer-to-peer networks using ant colony optimizatio. Proceedings of the Fourth International Conference on Natural Computation, Jinan, 2008: 516～520
19	Cao Y , Li S Z . Research on P2P hybrid information retrieval based on ant colony algorithm. Proceedings of the 10th International Conference on Computer Supported Cooperative Work in Design, Nanjing, 2006: 1048～1052
20	刘萍，高飞，杨云 . 基于遗传算法和蚁群算法融合的QoS路由算法. 计算机应用研究 2007，24（9）: 224～227
21	焦利，林宇，王文东等. 一种负载均衡网络中内部链路时延推测算法. 软件学报， 2005，16（5）: 886～893
22	郭小雪，秦勇，蔡昭权等. 多链路时延反馈共享令牌流量拥塞控制. 计算机工程与应用， 2010，46（2）: 75～78

	无能见度	有能见度
最小值	194.4	194.4
平均值	196.55	204.26
获得最小的次数（次）	48	6

	无能见度	有能见度
最小值	194.4	194.4
平均值	196.98	207.89
获得最小的次数（次）	50	9

	无能见度	有能见度
最小值	190.8	190.8
平均值	193.94	196.61
最小值次数（次）	24	6

	无能见度	有能见度
最小值	190.8	190.8
平均值	194.12	201.83
最小值次数（次）	24	7

[1]	房新彦, 张艳霞, 崔瑞琳, 罗思维. P2P网络视频监控技术机制解析[J]. 电信科学, 2022, 38(12): 152-162.
[2]	李攀攀,谢正霞,乐光学,马柏林,陈丽,刘建华. SSDHT：基于社交网络的DHT安全增强机制[J]. 电信科学, 2018, 34(11): 10-20.
[3]	马丽芳,陈伟峰,兰世战,陆松,张玉兰,莫晓斌,何昌智. 基于蚁群优化的移动P2P网络路由选择算法[J]. 电信科学, 2016, 32(7): 121-125.
[4]	合尼古力·吾买尔. ACO结合P2P信任模型的无线传感器网络Sinkhole攻击检测[J]. 电信科学, 2016, 32(4): 52-58.
[5]	赵晗,黄少卿. 基于改进蚁群算法的无线传感器网络最小跳数路由选择方法[J]. 电信科学, 2016, 32(3): 113-117.
[6]	余翔,易明敏,杨路. 一种SDN架构下业务属性相关的多径路由算法[J]. 电信科学, 2016, 32(11): 10-15.
[7]	朱国晖,鲁春兰,张瑞. 非结构化P2P网络引导型进化博弈算法[J]. 电信科学, 2016, 32(1): 60-65.
[8]	陈杰,姚娜. 沙尘对沙漠边缘地区WCDMA信号的影响[J]. 电信科学, 2015, 31(6): 75-78.
[9]	王雨薇,兰巨龙,席孝强,范茜勉,江逸茗. 一种软件定义网络中基于蚁群算法的一致性路由策略[J]. 电信科学, 2015, 31(11): 7-14.
[10]	钱亚冠,张旻. 基于过抽样技术的P2P流量识别方法[J]. 电信科学, 2014, 30(4): 109-113.
[11]	冯传奋. 基于P2P内容交换技术的IMS网络架构探讨[J]. 电信科学, 2013, 29(9): 79-82.
[12]	孙韩林,刘建华. 一种基于P2P的统一身份服务网络模型[J]. 电信科学, 2013, 29(7): 49-53.
[13]	张同光,赵晓莉. P2P网络中基于语义组的自适应资源预测复制算法[J]. 电信科学, 2012, 28(3): 79-82.
[14]	赵佩章,张同光. 无结构P2P网络中一种高效的资源搜索机制[J]. 电信科学, 2012, 28(3): 110-115.
[15]	徐雅斌,李艳平,刘曦子. 一个基于云计算的P2P流量识别系统模型的研究[J]. 电信科学, 2012, 28(10): 58-63.