基于多态蚁群算法的P2P网络资源搜索机制研究-论文.pdf

《基于多态蚁群算法的P2P网络资源搜索机制研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于多态蚁群算法的P2P网络资源搜索机制研究苏锦旗郭玉龙(西安邮电大学经济与管理学院710061)【摘要】为了提高蚁群算法在P2P网络资源搜索中存在搜索盲目、搜式中，allowed：{C—tabu}表示蚂蚁k下一步允许选择的城索效率低的问题，论文将多态蚁群算法和应用到了P2P网络搜索。针市；a为信息启发式因子，反映蚂蚁在运动过程中所积累的信息在对搜索一段时间后网络中发起的对新的文件请求，引入合成信息素的蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂概念，以减少搜索初始阶段消息转发的盲目性。对无结构P2P网络中蚁经过的路

2、径；为期望启发式因子，反映蚂蚁在运动过程中启发的洪泛算法、蚁群算法、引入合成信息素后的蚁群算法进行模拟实验，信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概实验结果表明所提出的算法可有效提高P2P网络的搜索性能。率越接近于贪心规则；J，7(t)为启发函数，其表达式如下：【关键词】对等网；搜索；多态蚁群算法；合成信息素叼(￡)1(2)式中，表示相邻两个城市之间的距离。对蚂蚁而言，d越小，则叼(t)越大，P：(t)也就越大。显然，该启发函数表示蚂蚁从元素(城市)i转移到元素(城市)的期望程度。(2)信息素增量计算信息素增量A

3、z的计算如下式所示。△r=CIlf1(3)式中A、B、C均为常数，、根据情况可做适当调整，n为消息包经过的节点数即TTL，t、t分别为节点收到响应包和请求包时的时间戳。(3)信息素更新计算：在搜索过程中路径上的信息素积累得越来越多，为了避免信息素过多淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i√)上的信息量可按如下规则进行调整：(t十n)=(

4、1-p)·tr(t)+△r(￡)(4)△rjj()=∑△f：(t)(5)式中，P表示信息素挥发系数，1一p表示信息素残留因子，为了防止信息的无限积累，P的取值范围为：pc[0，1)；／X~-(t)表示本次循环中路径(i√)上的信息素增量，初始时刻A．r(0)=0，△：(t)表示第k只蚂蚁在本次循环中留在路径(i√)上的信息量。(4)信息素生成计算邻居节点i的信息素的生成按如下的公式进行计算。臀()㈤式中，P为经由邻居节点i查询到的文件的集合，为文件经过邻居节点i的信息素，P、为参数，可以取P：1、：1，此时也即合成信息素与经过这个

5、节点的所有文件的信息素的均值成正比，与经过这个节点查找到文件的总数成正比。3基于多态蚁群算法的P2P网络资源搜索3．1算法实现实际P2P网络中，每个节点上可能存放很多不同的文件，需要引入多种信息素标记所有的文件，标记邻居节点的信息素表与基本蚁群算法中的相同；标记文件状态的信息素则需做相应的调整，单个文件的信息素表记录数据项有文件名、记录邻居节点的标识、信息素和更新时间戳。由于对每个文件都需要记录其信息素，所以在信息素记录表项中不仅需要记录邻居节点的名字标识，还需要记录文件的名字。p=』{t)]’)]⋯⋯⋯～㈩(1)为方便查找可将每

6、个文件的信息素表链接在一起，组成链式存储结构，如图1所示。L0．else一104—File1-File2■Fllcn当节点收到查询包时，先将该查询包的标识符和缓存表中的记录作比较，缓存表中存在该条记录，说明是最近已经转发过的重复消息，将其丢弃；没有该条消息的标识符，则是新的消息，按照正1r，’常的步骤进行转发。为了使节点能够按原路的路径将查询结果消NoteINolel息传回，节点需要缓存最近一段时间消息的来源邻居节点地址，当Note2收到查询消息的响应时，将其转发回去。同时节点周期性的检测接收时间戳，当超过～定的时间以后，即使再收

7、到响应消息也失去NOt+l1意义，所以将超时的记录信息删除，以减少不必要的冗余消息。3．3信息素的更新为了提高搜索效率，需要将搜索信息及时存储到信息素中，为图1信息素存储方式后面的搜索提供指导。考虑多种不同文件的情况下，当节点收到在图1中，先将每个文件的信息素链接在一起(如File1)，每查询响应包时信息素的更新算法如下。个邻居节点均可以返回查询结果；其他文件也类似，将可以返回查(1)按照公式(3)计算机信息素变化量；找结果的邻居节点链接起来。该存储方式查找时可以根据文件名(2)根据响应包中的文件名从信息素链表中查找该文件的信快速

8、找到所有与其相关的邻居节点的信息素状态，效率相对要高息素组，若找到，按公式(4)将文件信息素更新；很多；但是更新邻居节点的状态信息的代价比较大，当某个节点失(3)生成一个空的信息素组结构，插入到信息素链表的对应效时必须通过文件名遍历链表，以删除所有