基于改进CAN的查找算法

An improved search algorithm based on CAN

摘要:

为了减少CAN网络的查询跳数,提高搜索效率,将指针表的概念引入到CAN网络中.在规模为2L的标识符空间上采取折半查找的方法对各维坐标进行划分,并建立相应的下一跳节点集合——指针表,使搜索空间由全网缩减到一个相对较小的指定局部区域.仿真实验表明,改进后的查找算法所产生的节点坐标相对于原算法有着更为均匀的分布.在规模为26和27的CAN网络中,各有90%和70%的查询跳数减少,平均减少长度为53.2%和31.5%.扩大实验样本空间后,给出了规模分别为25、26和27的CAN网络的查询长度缩短率分布.实验证明,改进后的CAN算法较原算法有更少的查询跳数.

Abstract:

In order to reduce the hoop count and increase search efficiency,the notion of pointer table is introduced into CAN.In a scale of 2L identifier space,coordinates in each dimension are divided with binary search.The nodes corresponding to the divided coordinates compose the next hoop set as a pointer table,which cuts down the search scope from the whole CAN to a local CAN area.Simulation results show that the distribution of nodes’coordinates generated by improved CAN search algorithm is more uniform than that of the original CAN model.In the scale of 26 CAN and the scale of 27 CAN,90% and 70% searches cut their hoop figures,and the rates of decrease are 53.2% and 31.5% respectively.The distribution rates of search length reduction in the scales of 25,25 and 27 CANs are given after the sample space is extended.The experiment demonstrates that the improved algorithm based on CAN has less search hoop count than the original one.