基于物理位置的分层Chord路由方法

摘要

本发明提供了一种基于物理位置的分层Chord路由方法，该路由方法将基站的物理位置信息加入到基于DHT原理的Chord环中，同时将性能比较高的节点设置为超级节点，由基站和超级节点构成内层Chord环，查询过程中可以首先判断资源的实际物理位置范围，避免了对整个网络所有节点的遍历，加快了资源的快速定位，提高了网络的搜索速度，同时利用超级节点对其他普通节点进行控制和管理，在基站失效的情况下，节点之间还能够通过超级节点进行联系和通信，提高了网络的稳定性和安全性。

权利要求

1.一种基于物理位置的分层Chord路由方法，其特征在于包括以下步骤：

A.由至少一个基站和属于所述基站的节点构成外层Chord环，所述节点的节点标识符由基站的物理位置标识和经过哈希运算的该节点的逻辑位置标识组成；

B.计算所述外层Chord环中节点的能力评分为W＝aB+bS+cT+dC+eK，其中，B为节点网络带宽评分，S为节点可靠度评分，T为节点平均在线时间评分，C为节点计算能力评分，K为节点存储能力评分，a、b、c、d、e为加权系数，将能力评分W高于预设阈值的节点设置为超级节点，由所述超级节点和所述基站构成内层Chord环并建立路由表；

C.查询起始节点到资源的路由，根据所述资源的关键字标识符查询到对应的目标节点的节点标识符，如果所述起始节点的节点标识符与所述目标节点的节点标识符相同，将所述起始节点记为目标节点，查询结束；否则，如果所述起始节点所属的超级节点的节点标识符与所述目标节点的节点标识符相同，就将所述超级节点记为目标节点，查询结束；否则，查询所述目标节点的节点标识符中物理位置标识以找出距离资源最近的超级节点，查询该超级节点连接的节点，直到查询到存储所述资源的目标节点，将从所述起始节点到所述目标节点的路由路径加入路由表中。

2.根据权利要求1所述的基于物理位置的分层Chord路由方法，其特征在于：还包括新节点加入步骤，所述新节点加入步骤为：获取新节点所属基站的物理位置标识和新节点的逻辑位置标识，组成所述新节点的节点标识符；

选择一个所述外层Chord环中的节点作为所述新节点的引导节点，如果所述引导节点为超级节点，所述引导节点为所述新节点提供前趋节点信息和后继节点信息，如果所述引导节点为除超级节点外的普通节点，所述引导节点将所述新节点的加入请求传输给所述引导节点所属的超级节点后，由该超级节点为所述新节点提供前趋节点信息和后继节点信息。

3.根据权利要求1所述的基于物理位置的分层Chord路由方法，其特征在于：还包括节点退出步骤，所述节点退出步骤为：如果超级节点需要退出网络，所述超级节点向前趋超级节点和后继超级节点发出退出信息并转交自身保存的信息，同时向所述超级节点所属的基站发出退出信息；

如果除超级节点外的普通节点需要退出网络，所述普通节点向前趋节点发出退出信息，并将自身保存的信息转交给后继节点。

4.根据权利要求1所述的基于物理位置的分层Chord路由方法，其特征在于：还包括热点资源管理步骤，所述热点资源管理步骤为：所述节点周期性地统计自身管理的资源的访问情况，将一个周期内访问次数超过网络中同一周期内所有资源平均访问次数的资源记为热点资源，发送到所述节点所属的超级节点上，由所述超级节点将所述资源复制到同一基站下的所有超级节点上，各超级节点建立热点资源索引表。

5.根据权利要求4所述的基于物理位置的分层Chord路由方法，其特征在于：所述热点资源管理步骤还包括：所述超级节点周期性地统计所述热点资源索引表中热点资源的访问情况，将一个周期内访问次数小于其自身前三个周期内平均访问次数的50％的热点资源从所述热点资源索引表中删除。

说明书

基于物理位置的分层Chord路由方法

技术领域

[0001] 本发明涉及一种移动P2P(Peer-to-Peer，端对端)环境中的通信方法，具体地讲，是一种基于物理位置的分层Chord路由方法。

背景技术

[0002] P2P技术的产生和发展，改变了互联网的资源共享方式。在移动P2P网络中一个很重要的问题是如何实现资源的查找定位，Chord(带弦状拓扑)路由方法就是一种用于实现资源查找定位的方法。在传统的Chord方法中，基于DHT(Distributed Hash Table，分布式哈希表)结构化P2P系统采用统一的相容哈希算法，建立节点的NodeID(Node Identification，节点标识符)与资源关键字的KeyID(Key Identification，关键字标识符)之间的一一对应关系，从而实现资源的存储和查找。传统的Chord拓扑结构如图1所示，节点的路由信息表包括节点的关键字信息、起始节点信息、区间节点信息和后继节点信息，节点n的查找表的第i个表项包含节点n的后继节点信息I：

[0003] I＝successor(n+2i-1)mod(2m)，1≤i≤m (1)

[0004] 其中NodeID和KeyID的位长m＝6。在图1中，节点N8的后继节点为N14，路由0 1 m-1
节点信息包括：8+2，8+2，…8+2 。资源信息存储在KeyID号最近的后继节点上，在图1中表示为节点N14和N42存储了相应的关键字标识符KeyID为K10和K38的资源信息，节点N32存储了K24和K30。

[0005] Chord路由方法通过把网络虚拟成单一环形的拓扑结构，完成了信息的快速搜索，提高了查询效率，但是存在以下两方面的问题：一是Chord网络的绕路(Detouring)问题，二是未考虑节点性能，包括计算能力、存储能力、网络带宽等性能上的差异，严重影响了网络的稳定性和搜索信息的速度。

[0006] 目前已经有一些文献提出对Chord路由方法进行改进，其中最有代表性的是文献《一种改进的chord路由算法》(姜守旭，韩希先，李建中．一种改进的chord路由算法[J]．计算机应用，2006，26(4)：918-921．)，它的基本思想是去掉路由表中的冗余信息，在Chord的长度为m的初始路由表构建完毕以后，对表中的元素进行再次操作，删除表中冗余信息，增加有效的路由信息以提高系统的性能。但是它存在的问题是平均查询路径长度没有明显变化，仍为 。文献《Dual-chord：一种更加有效的分布式哈希表》(张浩，金海，聂江武等．Dual-chord：一种更加有效的分布式哈希表[J]．小型微型计算机系统，2006，27(8)：1450—1454．)提出的双向路由Chord是从前节点的顺时针和逆时针方向同时构建路由表，减少了平均查询路由长度，同时每个节点路由表是原始的两倍，增大了网络传输的信息量。文献《基于小世界层次分布式路由模型研究》(朱晓妹，周娅，黄桂敏．基于小世界层次分布式路由模型研究[J]．计算机工程，2006，32(15)：120—122．)根据IPv6网络中前缀分配有很强的层次性的特点，利用哈希节点IP地址的前缀和剩余部分来分段构建节点的标识符。由于具有相同前缀的节点物理空间相近，实现了逻辑空间和物理拓扑的有效吻合，更好地将同一个域的节点分配在一起，在一定程度上提高了查询的效率，但是也破坏了原有Chord的负载均衡性。

发明内容

[0007] 针对现有技术的不足，本发明的目的是提供一种搜索效率高的基于物理位置的分层Chord路由方法。

[0008] 为此，本发明提供了一种基于物理位置的分层Chord路由方法，包括以下步骤：A.由至少一个基站和属于基站的节点构成外层Chord环，节点的节点标识符由基站的物理位置标识和经过哈希运算的该节点的逻辑位置标识组成；B.计算外层Chord环中节点的能力评分为W＝aB+bS+cT+dC+eK，其中，B为节点网络带宽评分，S为节点可靠度评分，T为节点平均在线时间评分，C为节点计算能力评分，K为节点存储能力评分，a、b、c、d、e为加权系数，将能力评分W高于预设阈值的节点设置为超级节点，由超级节点和基站构成内层Chord环并建立路由表；C.查询起始节点到资源的路由，根据资源的关键字标识符查询到对应的目标节点的节点标识符，如果起始节点的节点标识符与目标节点的节点标识符相同，将起始节点记为目标节点，查询结束；否则，如果起始节点所属的超级节点的节点标识符与目标节点的节点标识符相同，就将超级节点记为目标节点，查询结束；否则，查询目标节点的节点标识符中物理位置标识以找出距离资源最近的超级节点，查询该超级节点连接的节点，直到查询到存储资源的目标节点，将从起始节点到目标节点的路由路径加入路由表中。

[0009] 根据本发明的一个方面，基于物理位置的分层Chord路由方法还包括新节点加入步骤，新节点加入步骤为：获取新节点所属基站的物理位置标识和新节点的逻辑位置标识，组成新节点的节点标识符；选择一个外层Chord环中的节点作为新节点的引导节点，如果引导节点为超级节点，引导节点为新节点提供前趋节点信息和后继节点信息，如果引导节点为除超级节点外的普通节点，引导节点将新节点的加入请求传输给引导节点所属的超级节点后，由该超级节点为新节点提供前趋节点信息和后继节点信息。

[0010] 根据本发明的另一个方面，基于物理位置的分层Chord路由方法还包括节点退出步骤，节点退出步骤为：如果超级节点需要退出网络，超级节点向前趋超级节点和后继超级节点发出退出信息并转交自身保存的信息，同时向超级节点所属的基站发出退出信息；如果除超级节点外的普通节点需要退出网络，普通节点向前趋节点发出退出信息，并将自身保存的信息转交给后继节点。

[0011] 根据本发明的又一个方面，基于物理位置的分层Chord路由方法还包括热点资源管理步骤，热点资源管理步骤为：节点周期性地统计自身管理的资源的访问情况，将一个周期内访问次数超过网络中同一周期内所有资源平均访问次数的资源记为热点资源，发送到节点所属的超级节点上，由超级节点将资源复制到同一基站下的所有超级节点上，各超级节点建立热点资源索引表。

[0012] 根据本发明的又一个方面，热点资源管理步骤还包括：超级节点周期性地统计热点资源索引表中热点资源的访问情况，将一个周期内访问次数小于其自身前三个周期内平均访问次数的50％的热点资源从热点资源索引表中删除。

[0013] 与现有技术相比，本发明的有益效果是：该基于物理位置的分层Chord路由方法将基站引入到Chord环中，使得节点标识符中包含了实际物理位置信息，查询时先确定资源属于哪个基站的范围内，不再需要遍历整个网络的所有节点，从而加快了资源的快速定位，同时引入超级节点的概念，提取性能较高的节点由基站直接管理，而其他普通节点由超级节点进行管理，充分利用了超级节点优秀的工作性能，提高了网络的搜索速度，在基站失效的情况下，节点之间还能够通过超级节点进行联系和通信，提高了网络的稳定性和安全性。

附图说明

[0014] 本发明上述的各方面优点，可以从下面附图和对实例的描述中将变得明显和容易理解，其中：

[0015] 图1为现有技术中的Chord环的结构示意图；

[0016] 图2为本发明的PLHChord环的结构示意图；

[0017] 图3为本发明的基于物理位置的分层Chord路由方法的流程图；

[0018] 图4为本发明的基于物理位置的分层Chord路由方法中新节点加入步骤的流程图；

[0019] 图5为本发明的基于物理位置的分层Chord路由方法的平均路由跳数示意图；

[0020] 图6为本发明的基于物理位置的分层Chord路由方法的平均路由延迟伸展度示意图。

具体实施方式

[0021] 下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的器件或具有相同或类似功能的器件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。

[0022] 图 2 示 出 的 是 本 发 明 的 PLHChord(Physical Location Based HierarchicalChord，基于物理位置的分层Chord环，唐朝伟、陈宏旦、王恒，重庆大学，邵艳清，重庆电子工程职业学院)的体系结构。在PLHChord模型中，整个网络外层Chord环是由至少一个基站和属于这些基站的节点彼此互连构成的，内层是由超级节点和基站组成的Chord环，由节点的NodeID号可以看出节点是根据实际物理地址划分的，需要周期性的向基站来检测自己的地理位置来变化NodeID中用于表示实际物理位置的高位信息。Chord环中的节点依然按照Chord协议的规则组成结构化的P2P网络，当同一个基站内的节点之间没有资源的时候可以通过超级节点来完成通信。

[0023] 根据本发明的分层Chord路由方法，包括以下步骤：

[0024] A.首先由至少一个基站和属于基站的节点构成外层Chord环，节点的节点标识符由基站的物理位置标识和经过哈希运算的该节点的逻辑位置标识组成；

[0025] B.计算外层Chord环中节点的能力评分为：

[0026] W＝aB+bS+cT+dC+eK (2)

[0027] 其中，B为节点网络带宽评分，S为节点可靠度评分，T为节点平均在线时间评分，C为节点计算能力评分，K为节点存储能力评分，a、b、c、d、e为加权系数，将能力评分W高于预设阈值的节点设置为超级节点，由超级节点和基站构成内层Chord环。在本发明的一个实施例中，评分B、S、T、C和K分别由1、2、3、4分来表示，其中4分表示能力最高，1分表示能力最低，加权系数a、b、c、d、e设置为1、1.5、3、2、2，如果一个节点N的各项得分依次为B＝2、S＝2、T＝4、C＝3和K＝4，那么这个节点N的能力评分为W＝2×1+2×1.5+4×3+3×2+4×2＝31。确定超级节点的阈值根据实际网络环境决定，比如一个基站包含有1024个节点，一个超级节点的能力足以管理256个节点，那么一共只需要4个超级节点，此时将所有节点的能力评分W按从大到小进行排序，令阈值等于其中第5位的W，从而将高于阈值的4个节点提取为超级节点。

[0028] 可以看出，超级节点是基站所连接的节点中具有很好的计算能力、存储能力和网络带宽的高性能节点，因此它被赋予了更多的职责，也对网络性能起到了更大的影响作用。超级节点建立路由表以保存信息，在外层负责保存与其前趋超级节点之间的普通节点和本基站中超级节点的信息，在内层根据Chord路由保存其他超级节点的信息，同时需要复制目前网络中流行的文件，新节点的加入也需要超级节点的协助。在PLHChord环中，一个基站负责管理其后到下一个基站之前的所有节点，具体而言，基站直接管理控制超级节点，再由每个超级节点来管理一定范围内的包含自身在内的节点，还是以上述包含1024个节点的基站为例，如果节点N1、N300、N700、N1000为超级节点，那么该基站直接管理超级节点N1、N300、N700、N1000，再由超级节点N1管理节点N1～N256，超级节点N300管理节点N257～N512，超级节点N700管理节点N513～N768，超级节点N1000管理节点N769～N1024。

[0029] C.然后查询起始节点到资源的路由，根据资源的关键字标识符查询到对应的目标节点的节点标识符，如果起始节点的节点标识符与目标节点的节点标识符相同，将起始节点记为目标节点，查询结束；否则，如果起始节点所属的超级节点的节点标识符与目标节点的节点标识符相同，就将超级节点记为目标节点，查询结束；否则，查询目标节点的节点标识符中基站的物理位置标识以找出距离资源最近的超级节点，查询该超级节点连接的节点，直到查询到存储资源的目标节点，将从起始节点到目标节点的路由路径加入路由表中。

[0030] 图3示出的是本发明的分层Chord路由方法的流程。一个节点N要查询关键字key的资源的路由过程为：

[0031] a.首先找到与哈希运算后的资源的关键字标识符KeyID相对应的节点标识符NodeID，再查询起始节点N的Local表，判断关键字key是否落在Local表范围内，Local表是节点的本地路由表，也就是节点的指针表(Finger表)，存储的是连接其他节点的路由信息。如果是就返回相应目标节点，查询结束，否则转向b。

[0032] b.通过supernode表将查询发送到超级节点。超级节点查询其Local表，Cache表和HotResource表。Cache表是缓存路由信息表，同时也可以把下载次数多的、比较热点的资源信息存储到HotResource表，缓存一定数量的信息，碰到热点信息的时候直接从HotResource表中查找即可，节省时间，提高效率。如果找到就返回目标节点地址，查找结束。否则转向c。

[0033] c.超级节点查询其Finger表和Bucket表，分别找出一个在关键字key之前且距离key最近的超级节点。Bucket表是按顺序存储的节点的缓存信息表，利用NodeID中包含的物理位置信息可以快速判定出资源位于哪个基站的范围内，提高了搜索速度。

[0034] d.该超级节点将查询其Local表，Cache表和HotResource表等本地信息，把信息发送给该起始节点。

[0035] e.当一个目标节点收到查询时，它将在Bucket表中缓存起始节点地址信息。当一个查询完成时，节点通知超级节点及其副本缓存查询成功的节点信息。当表填充满时利用LRU(Least Recently Used，最近最久未使用法则)替换策略管理表中的信息。

[0036] 图4示出的是本发明的分层Chord路由方法中新节点加入步骤，新节点加入步骤为：获取新节点N所属基站的物理位置标识和新节点的逻辑位置标识，组成新节点的节点标识符NodeID；选择一个外层Chord环中的节点M作为新节点N的引导节点，如果引导节点M为超级节点，引导节点M为新节点N提供前趋节点信息和后继节点信息，如果引导节点M为除超级节点外的普通节点，引导节点M将新节点N的加入请求传输给引导节点M所属的超级节点后，由该超级节点为新节点提供前趋节点信息和后继节点信息。新节点N的加入算法与现有Chord模型中的节点加入算法类似，只是由超级节点来进行管理控制，提高了P2P网络的动态性。

[0037] 分层Chord路由方法还包括节点退出步骤，节点退出步骤为：如果超级节点需要退出网络，因为不但要做普通节点退出网络所做的工作来保持Chord环的完整性，而且还要维护内层Chord环的连接关系，所以超级节点要向其前趋超级节点和后继超级节点发出退出信息并转交自身保存的信息，同时向超级节点所属的基站发出退出信息；如果除超级节点外的普通节点需要退出网络，只需遵循Chord协议的节点退出规则退出它所在基站节点的Chord环即可，因为在PLHChord模型中，普通节点只需维护它在本站中的位置，无需知道其他基站节点的信息，与其他站内节点没有直接的联系，因此普通节点只需向其前趋节点发出退出信息，并将自身保存的信息转交给其后继节点。

[0038] 在实际查询过程中，某些信息可能被频繁地查询而形成热点资源，因此分层Chord路由方法还包括热点资源管理步骤，热点资源管理步骤为：节点周期性地统计自身管理的资源的访问情况，将一个周期内访问次数超过网络中所有资源平均访问次数的资源记为热点资源，发送到节点所属的超级节点上，由超级节点将资源复制到同一基站下的所有超级节点上，各超级节点建立热点资源索引表。当某个查询路由到该基站时，可以选择其中一个超级节点进行访问，可以减轻其他超级节点的负担。

[0039] 热点资源索引表保存从别的超级节点冗余过来的资源信息，超级节点周期性地统计热点资源索引表中热点资源的访问情况，如果某个热点资源在一个周期内访问次数小于其自身前三个周期内平均访问次数的50％，说明它已经不能再被认为是热点资源，需要将其从热点资源索引表中删除。

[0040] 采用仿真试验来检验本发明点分层PLHChord路由方法的工作性能，仿真试验中采用BRITG(Boston university Representative Internet Topology Generator，波士顿大学的典型网络拓扑生成器)来模拟网络拓扑结构，BRITG生成的底层网络拓扑结构与实际网络拓扑结构十分相似。路由结构使用Waxman模式。本仿真试验环境配置如下：一台pc机，其cpu为Intel P42.6GHz，内存为1G RAM，操作系统为Redhat linux9.0。仿真软件开发语言：C++，开发工具：ECLIPSE3.2。安装了基于p2psim-0.3修改的覆盖网仿真器，m＝32
32，故标识空间为O～2 -1。

[0041] 仿真试验中通过p2psim比较原来的可扩展Chord路由协议和改进后的PLHChord路由协议在资源定位性能方面的差别。p2psim运行之后，从它的输出可以得到很多重要的数据，包括平均路由跳数、平均查找延迟时间等，在这里只需要考虑这两方面的数据。

[0042] 平均查找路由跳数是评价P2P系统的重要指标，结构化DHT算法Chord模型的平均查找路由跳数是 Nnode为网络节点数。

[0043] PLHChord模型是基于物理位置的分层网络模型，利用基站物理位置ID实现了节点的NodeID和资源的KeyID的相互匹配，提高了物理网络的位置距离与覆盖层逻辑排列的一致性，通过内层的查找减少了查询的路由跳数。

[0044] 假设一个超级节点管理Mnode个普通节点，那么PLHChord模型下路由路径为：从普通节点到内层超级节点到资源所属节点。最大路由跳数为： 如果超级节点为基站节点则通过核心网一跳到所属资源基站节点，跳数为4。当Mnode取16、64、256，以及随机模拟情况时进行实验仿真。采用512、1024、2048、4096、6144、8192、10240一共七组不同数量规模的节点分别来进行仿真试验，其中每个节点分别存储50个文件，每个节点平均随机请求2次。

[0045] 图5示出的是不同算法下的平均路由跳数的仿真结果。从图5中可以看出PLHChord在平均路由跳数上比原Chord减少了22％到38％。由于在Local表节点设置了限定区间且超级节点包含更多的节点信息，其覆盖的逻辑距离肯定比原Chord算法更加逼近目标，故PLHChord系统相对于原Chord路由效率有了很大的提升。

[0046] 消息的端到端路由延时(end-to-end latency)是衡量P2P系统实际路由性能的重要参数。由于查询消息在覆盖网络中的所经过的距离和在底层网络中实际的距离不一致，所以通常用平均延迟伸展度(Latency Stretch)来表示距离之间的比值。平均延迟伸展度S定义为系统平均逻辑延迟与平均物理延迟的比值，具体表达式为：

[0047]

[0048] 式中，DChord(i，j)为逻辑网络Chord下节点i到节点j之间的延时，DIP(i，j)为物理网络IP(Internet Protocol，网络互连协议)下节点i到节点j之间的延时，Nnode为网络节点个数。若延迟伸展度大，则说明覆盖网络和底层网络差异很大，反之，延迟伸展度越小，说明覆盖网络与底层网络越一致。在实际Internet网络中，域内的延时总是远远小于域间延时。因此假定站内跳数开销为20ms，而站间跳数开销为100ms。同样为了实验数据的准确性，采用256、1024、2048、4096、6000、8192、10000等七组不同规模的情况进行1000次路由查找操作，仿真结果如图6所示。从图6中可以看出，随着网络节点数的增加，HChord(Hierarchical Chord，分层Chord环)路由方法由于考虑了超级节点的影响，使得其工作性能明显好于Chord路由方法，而PLHChord路由方法综合考虑了超级节点和基站对网络性能的影响，其工作性能相比于HChord路由方法又有了进一步的提高。

[0049] 由于节点标识符NodeID哈希值的高位信息表示的是基站物理位置信息，根据资源KeyID可以找到相应基站位置，查询路径从起始查询节点到所属基站节点到核心网再到资源所属基站节点最后到目标资源节点，基站节点之间的路由基本是一致的。PLHChord的平均延迟伸展度基本趋于稳定，节点物理距离越远延迟伸展度反而更小。

[0050] 在实际移动P2P网络环境中，节点之间的通信会受到多径衰落、障碍物、节点的移动速度快等多种不利因素的影响，使得通信不畅，导致查找时间延长或者通信中断，在经过节点判断后认定节点失效，需选择新的路由路径。这两种情况下使得PLHChord路由方法整个资源查询时间延长，但对平均路由跳数和平均延迟伸展度没有太大影响。相反，PLHChord路由方法利用超级节点能更快的更新路由表，选择新的路径，比Chord路由方法更迅捷，受网络环境的影响更小。

[0051] 以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。