基于分布式哈希表的覆盖网络的路由机制

摘要

一种在诸如基于分布式哈希表的覆盖网络等覆盖网络内使用并配置为跨覆盖网络路由分组的节点。节点包括用于基于覆盖网络中对等节点的集合的功耗水平和/或功率可用性的知识做出路由判定的部件。

说明书

技术领域

本发明涉及基于分布式哈希表的覆盖网络的路由机制。本发明特别适用于确定对等网络中资源请求的路由的优化过程。

背景技术

对等或P2P网络利用包括处理能力和通信带宽等参与节点的合并资源，以有利于包括文件共享和因特网话音协议(VoIP)电话的各种各样的服务。在缺少中央服务器时，特定P2P服务可利用“覆盖网络”优化资源位置。覆盖网络包括由虚拟链路连接的节点，虚拟链路表示在基础网络(例如，因特网)中的可能许多物理链路上延伸的路径。覆盖网络中的每个节点保持包含到覆盖网络内某些其它节点的链路的集合的路由表。资源请求在节点之间传递，直至它们到达负责该资源的节点。

哈希表是将密钥与值相关联的数据结构。密钥例如能够是人员的名字和该人员的联系地址(例如，电子邮件地址或会话启动协议(SIP)统一资源标识符(URI))的相关联值。哈希表支持的主要操作是查找-即给定一个密钥，哈希表找到对应的值。分布式哈希表(DHT)提供类似于哈希表的查找服务。然而，不同于常规哈希表，DHT是在分布式系统或网络中使用的非集中哈希表。在DHT中，保持从名称到值的映射的责任分布在参与系统的节点之间。这通过在参与节点之间划分密钥空间来实现。

DHT提供了用于将资源名称(“密钥”)映射到覆盖网络内位置的有效方式。DHT利用哈希算法将例如歌曲标题、SIP URI等密钥映射到例如128比特等有限值空间。哈希算法经选择以确保哈希值在值空间上的相对均匀分布。因此，例如，100个歌曲标题的哈希将可能产生100个哈希值，这些值在值空间上相对均匀地间隔开。通过用户名标识覆盖网络内的节点，用户名本身哈希为相应哈希值。每个节点随后变为对值空间内与其自己值相邻的哈希值的集合负责。实际上，节点将存储资源位置(例如，IP地址)，从资源位置能够获得匹配它“拥有”的资源名称的资源。在覆盖网络中的节点接收对资源的请求时，节点确定它是否拥有对应的哈希值。如果是，它将资源的位置返回到请求者(经由覆盖网络)。如果它不拥有该哈希值，则它检查其路由表以识别表内具有与该请求的哈希值最接近的哈希值的节点，并且将该请求转发到该节点。接收节点重复该过程并继续，直至该请求到达确实拥有对应于该请求的哈希值并因此知道资源位置的节点。

在诸如Chord[I.Stoica、R.Morris、D.Karger、M.F.Kaashoek及H.Balakrishnan所著：“Chord：因特网应用的可扩展对等查找服务”(Chord：A Scalable Peer-to-peer Lookup Service for Internet Applications)-Proceedings of the ACM SIGCOMM′01 Conference，August 2001，San Diego，California，USA.]等一些DHT中，路由表中的条目称为指部指示符(pointer)。除路由表外，每个节点也保持称为邻居列表的另一数据结构。邻居列表包含到覆盖网络中节点的紧邻的后继(successor)和前趋(predecessor)(即邻居)的指示符。节点根据网络的拓扑挑选其邻居。

邻居(其能够是前趋或后继)与指部之间的不同在图1中示出，图1示出了具有环状拓扑的覆盖网络(仅示出在该环内的少量节点)。每个节点保持一个路由表，路由表包含在环中少量后继和前趋节点及少量更远节点的位置和哈希值。在所示网络中，节点X在其路由表中保持两个后继节点、两个前趋节点及三个远程节点的位置。例如，在上述Chord DHT算法中，每个节点n保持带有最多m个指部的路由表(m经选择以便它等于节点标识符中的比特数量)。在节点n处的表中第i个条目包含标识符环上在n后至少2^i-1的第一节点s的身份。

图2示出Chord环的一个示例，其中，m＝5，表示每个节点保持5个指部。节点N将标识符环划分成五个不同指部间隔，其范围在表1中列出。例如，间隔3的指部F3是在标识符环上在N后至少2^3-1＝4的第一节点。

  指部间隔  开始  结束  1  N+1  N+2  2  N+2  N+4  3  N+4  N+8  4  N+8  N+16  5  N+16  N+32

表1-节点N的指部间隔的范围

Chord DHT算法也能扩展，以便它保持每个指部间隔的备选指部指示符。实现此操作的一种方式是让主指部对等体返回Chord环上其后继节点的列表，然后，除主指部指示符外还保持到这些节点的指示符。

虽然在路由表内较大数量的条目能够使网络在路由方面更有效，并且对防止节点撤消更稳固，但大的表难以保持并因此增大了网络的不可靠性。通过尝试周期性地联系其邻居，覆盖网络内的节点确保在其路由表中的信息是最新的。

其它DHT拓扑的示例包括树拓扑。例如，Kademlia DHT[P.Maymounkov和D.Mazieres所著：“基于：基于异或量度的一种对等信息系统”(Kademlia：A peer-to-peer information system based on the xor metric″，Proceedings of IPTPS02，Cambridge，USA，March 2002])以二进制树状结构组织节点。例如，如果使用160比特节点标识符，则在Kademlia中，对于i的每个值，其中，0＜i＜160，每个节点为与其本身在2ⁱ与2ⁱ⁺¹之间距离的节点保持<IP地址，端口，节点ID>三元组的列表。这些列表称为k桶(bucket)，并且每个k桶能够包含最多k个条目。Kademlia路由表是二进制树，其叶是k桶。图3示出网络的一个极简单示例，其中，节点110保持示为三个圆1、2和3的三个k桶。k桶3包含其与节点001的距离为1的节点，k桶2包含距离2或3的节点，以及k桶1包含距离在4与7之间的节点。

在Kademlia中的查找以迭代方式进行：首先，查找启动方选择a个节点，这些节点是与其最近非空k桶距离为a(a的典型值为3)的节点。接着，启动方发送并行查找请求到它已选的a个节点。查找请求的每个接收方返回它知道离目标ID最近的k个节点的三元组。这些三元组能够来自单个k桶，或者在最近的k桶未满时它们可来自多个k桶。然而，如果查找请求的接收方拥有正在搜索的资源，则它在它生成的对于查找请求的响应中只返回该资源。查找过程也具有递归步骤(不要与下面所述的递归路由相混淆)，其中，启动方将查询请求重新发送到它已经从前面的查找响应了解的节点。在启动方接收所需资源时，查找进程停止。

随着诸如宽带码分多址(WCDMA)和高速分组接入(HSPA)等宽带无线技术变得更普遍，预期诸如对等会话启动协议(P2PSIP)和文件共享等对等(P2P)应用的移动终端会被更多地使用。这为一般具有有限电池容量的移动终端带来了问题，这是因为在基于DHT的P2P覆盖网络中充当对等体的移动终端需要中继其它用户的业务以及发送和接收频繁的DHT保持消息。在第二代(2G)和第三代(3G)移动网络中，人们发现在持久连接上发送的频繁的消息耗用大量的能量。大多数移动终端具有休眠模式，该模式用于在装置已开机但未活动地传送或接收消息时避免用尽终端电池。DHT需要频繁地通过无线电接口传输数据，并且因而可能很快耗尽移动终端的电池，这是因为每个消息迫使终端频繁地从休眠模式更改为活动模式(即，唤醒)。

本发明构想时考虑了以上所述内容。

发明内容

本发明提议了一种允许覆盖网络中的对等体交换有关其功耗的信息的机制。它也允许对等体无论何时将要从休眠模式切换到活动模式以及从活动模式切换到休眠模式时通知其连接的对等体。此信息随后能用于优化在功耗方面路由算法的路由性能。

根据本发明的第一方面，提供了一种在覆盖网络内使用并包括用于基于覆盖网络中对等节点的集合的功耗水平和/或功率可用性的知识做出路由判定的判定单元的节点。

例如，该节点可以是移动用户终端。

在所述的对等节点的集合是路由邻居节点的情况下，该节点可包括存储器，所述存储器用于存储路由表以及用于每个路由邻居的路由表中的参数或与该路由表相关联的参数，对于每个路由邻居节点路由表包含节点的覆盖网络地址与节点的物理定位器之间的映射。参数包括：

1)功率使用参数，指示多个操作状态中每个操作状态的功耗水平，以及

2)功率管理状态PMS参数，指示当前或最近通知的路由邻居的操作状态；以及

3)处理单元，配置为基于路由邻居的功率使用参数和PMS参数确定消息要转发到的路由邻居。

节点可配置为从路由邻居接收指示该路由邻居将要更改其操作状态的状态更新消息，状态更新消息包括对于该路由邻居将要进入的操作状态该路由邻居的新PMS参数。接收节点在用于该路由邻居的路由表条目中存储PMS参数。

节点可配置为根据路由表中路由邻居的参数确定任何路由邻居是否处于休眠模式，这种情况下，它存储覆盖网络中的状态更新消息以便以后在休眠路由邻居将状态从休眠模式更改为活动或受限模式时输送给休眠路由邻居。

节点可配置为将节点的多个操作状态中的每个操作状态的功耗水平提供到覆盖网络中的其它节点，并且通知网络中的一个或多个对等节点该节点的操作状态即将更改。同样地，节点可以是移动用户终端。

节点可包括：存储指示所述功耗水平的功率使用参数的存储器；以及处理单元，所述处理单元配置为：在发送到覆盖网络中其它节点的对等协议消息中提供所述功率使用参数，以及在发送到网络的其它节点的通知中提供指示节点将要进入的操作状态的PMS参数。节点可还配置为将状态更新消息发送到所述覆盖网络内的一个或多个路由邻居，指示它将要更改其操作状态，状态更新消息包括对于节点将要进入的操作状态节点的PMS参数。

节点可配置为将有关其剩余电池容量的信息提供到网络的其它节点，其中，剩余电池容量包括如果节点仍处于活动状态，它将在某个时间量内用尽电池容量的指示。节点也可配置为指示其供电不受限，例如，连接到供电线(main supply)。

在移动终端的情况下，节点可配置为访问无线电资源控制RRC状态机以确定操作状态信息。例如，节点可包括在节点的本地平台上运行以便访问RRC状态机的应用。节点可包括配置为访问RRC状态机的供应商特定编程接口(API)或借助于Java规范请求(JSR)获得的Java应用，Java应用允许访问RRC状态机。

节点可配置为通过参考节点的终端型号，以及从web服务器或者从在所述节点驻留的P2P应用提供的数据获得节点的功率使用参数。节点可通过参考系统属性确定终端的型号。

在节点不能确定另一对等体的操作状态的情况下，节点可配置为在它发起的对等体协议消息中将PMS参数设为“未知”。

例如，可在包括以下一项或多项的功率使用参数方面指定功耗水平：

休眠模式功率使用PMU参数，指定节点在处于节能或休眠模式时的功耗；

活动模式功率使用AMPU参数，指定节点在活动模式中操作时的功耗；以及

受限模式功率使用RMPU参数，指定节点在受限模式中操作时的功耗。

PMS参数可指示从以下选择的一种操作状态：节能或休眠状态；活动状态；受限状态；及未知状态。

根据本发明的第二方面，提供了一种在覆盖网络的路由节点做出路由判定的方法。方法包括基于对等节点的功耗水平和/或功率可用性的知识，选择覆盖网络中消息要转发到的对等节点的集合中的一个或多个对等节点。

覆盖网络可采用分布式哈希表DHT，并且其中覆盖网络包括保持路由表的节点。对于在覆盖网络中路由邻居节点的集合的每个路由邻居节点路由表包含在节点的覆盖网络地址与节点的物理定位器之间的映射。该方法还在每个所述覆盖网络节点包括：

保持用于每个路由邻居的路由表中的参数或与该路由表相关联的参数，参数包括：

功率使用参数，指示多个操作状态中每个操作状态的功耗水平，以及

功率管理状态PMS参数，指示当前或最近通知的路由邻居的操作状态。

保持参数的步骤可包括从路由邻居接收状态更新消息，状态更新消息包括PMS参数，指定路由邻居将要进入的下一操作状态，并更新在其路由表中或与其路由表相关联的路由邻居的PMS参数。

方法可包括检查路由邻居的PMS状态，并且在路由邻居不在休眠时发送状态更新消息到路由邻居，或者在路由邻居正在休眠时，存储覆盖网络中的消息以便以后输送到该路由邻居。存储在覆盖网络中的状态更新消息的步骤包括：检查休眠路由邻居的直接路由邻居的PMS状态，以识别非休眠直接路由邻居，并且将目的地为该休眠路由邻居的状态更新消息发送到非休眠直接邻居以便存储。当非休眠直接路由邻居将要进入休眠模式时，方法还包括将状态更新消息转发到休眠路由邻居的另一非休眠直接路由邻居。

方法可在对等P2P网络中有利地采用，与功耗水平和/或功率可用性有关的信息在使用诸如P2PSIP等对等协议在节点之间发送的消息中提供。

选择消息要转发到的路由邻居的步骤可包括：

确定备选路由邻居的集合为要路由到目的地对等体的消息的下一跳对等节点；

检查下一跳对等节点的操作状态；以及

如果在消息发送到下一跳对等节点时将不需要状态更改，则将消息转发到该节点；或者

如果所有节点都将需要状态更改，则检查下一跳对等节点的功耗水平，计算在更改每个下一跳对等体的状态中涉及的功耗的增大，以及将消息转发到需要功耗最小增大的下一跳对等体。

在使用基于DHT的覆盖网络的情况下，DHT使用Chord算法或Kademlia算法操作。备选，基于DHT的覆盖网络可以递归方式或迭代方式路由消息。

在本发明的至少某些实施例中，路由邻居是分层覆盖网络中的超级对等体。

可在包括一个或多个“未知”状态参数的PMS参数方面指定路由邻居的操作状态，在此情况下，方法包括以下步骤：

A)如果备选下一跳节点的集合包含处于活动模式的至少一个对等体，则将消息转发到处于活动模式中的对等体之一；以及

B)如果备选下一跳节点的集合不包含处于活动模式中的对等体，则从具有未知状态的对等体中选择在活动模式中具有最小功耗的对等体。

至少某些实施例的优点是，本文中所述经济路径查找器机制的操作允许与在移动终端中使用P2P应用相关联的功耗水平显著减少。这通过允许对等体交换与在不同操作状态中其功耗水平有关的信息和有关其当前操作状态(功率管理状态-例如，休眠模式或活动模式)的信息来实现。由于对等体知道其路由邻居的功耗和功率管理状态，因此，它能基于此信息优化路由判定。这允许网络通过以低成本将消息路由到邻居(即，功耗的增大)来节能，并且延长电池供电终端的使用寿命。该机制也适用于其它类型的对等体，并且通常能够由在不同功耗水平操作并且需要节能的所有类型的对等体采用。也能够扩展该机制以便在做出路由判定时将无线节点的剩余电池容量考虑在内。

也有利的是经济路径查找器机制能够应用到采用任何DHT算法的覆盖网络，并且该机制既适用于迭代路由模式也适用于递归路由模式。该机制也能用于选择低成本(在功耗方面)超级对等体。

附图说明

图1以示意图方式示出包括多个节点、基于DHT的环状覆盖网络；

图2进一步示出基于DHT的环状覆盖网络，显示了在节点之间的邻居关系；

图3示出基于Kademlia DHT的树状覆盖网络的一个简单示例；

图4a和4b示出根据本发明的实施例在路由机制的操作中的信号流；

图5是根据本发明的实施例的方法的流程图；以及

图6以示意图方式示出覆盖网络的路由节点。

具体实施方式

下面描述一种经济路径查找器机制实施例，并且该机制使用在对等协议消息中携带的四个新参数。对等协议是参与P2P覆盖网络的节点用于在相互之间交换信息的协议。这四个新参数称为休眠模式功率使用(SMPU)、受限模式功率使用(RMPU)、活动模式功率使用(AMPU)及功率管理状态(PMS)。除对等协议消息外，相同的参数也在覆盖网络中每个对等体保持的路由表中存储。

休眠模式功率使用(SMPU)参数指定对等装置在它处于其节能(即休眠)模式中时的功耗(例如，以毫瓦为单位)。活动模式功率使用(AMPU)指定装置在活动模式中操作时的功耗(例如，以毫瓦为单位)，例如，在移动终端已分配有专用上行链路和下行链路无线电信道时。受限模式功率使用(RMPU)参数指定装置在受限模式中操作时(例如，移动终端未分配有专用上行链路和下行链路信道，而是对于上行链路和下行链路传输均使用默认共用或共享传输信道时)的功耗。在状态更新消息中使用的功率管理状态(PMS)参数指定发送方将要进入的下一功率管理状态。参数能够具有以下四个值之一：“休眠”、“受限”、“活动”和“未知”。

图4a和4b示出在对等体之间的信号流序列。在此所示示例中，对等体的PMS参数始终是“休眠”、“受限”或“活动”。使用“未知”参数的情况在以后描述。对等体N是覆盖网络中的一个典型节点(例如参见图2)。对等体F是对等体N的路由邻居或指部，并且对等体F_neighbour是对等体F的直接邻居。如果对等体N要与对等体F建立连接，则对等体N将SMPU、RMPU和AMPU参数包括到自此以后称为连接请求的初始请求中。这在图4a中以步骤401示出。在生成对连接请求的响应(步骤402)时，指部F将在该响应中包括其自己的SMPU、RMPU和AMPU值。如果任一对等体N或F不支持节能模式，则它在消息中不包括SMPU和RMPU参数，或者它将所有功率使用参数设为具有相同值，使得SMPU＝RMPU＝AMPU。另外，这些功率使用参数包括在下面将更详细描述的对状态更新消息的响应中。

对等体N构建和发送的连接请求(步骤401)包括PMS参数及功率使用参数SMPU、RMPU和AMPU。视对等体N所处的状态而定，PMS参数的值设为“受限”或“活动”(由于对等体N正在传送数据，因此，该值不能为“休眠”)。同样地，对等体F将其当前功率管理状态PMS参数与其三个功率使用参数(SMPU、RMPU和AMPU)一起包括在到对等体N的连接响应中(步骤402)。在接收连接响应时，在步骤403，对等体N将三个功率使用参数的值存储到它为对等体F保持的路由表条目中。另外，在步骤404，对等体N将PMS参数的值设为对等体F返回的值。

如果对等体F更改其功率管理状态，则如在步骤405所示，它通过发送状态更新消息来通知它正与其保持连接的每个对等体(包括对等体N和F_neighbour)状态更新(1)。状态更新(1)包含PMS参数，其值已根据发送方对等体F将要进入的状态而设为“活动”、“受限”或“休眠”。在步骤406，在对等体N接收状态更新(1)消息时，它使用从对等体F收到的PMS参数的新值更新它为对等体F保持的路由表条目。

对等体应避免发送状态更新消息到正在休眠的路由邻居，这是因为这将迫使对等体唤醒并因此增大其能耗。然而，休眠对等体仍应在它们醒来时便接收状态更新消息，以便它们会具有关于它们与其保持连接的对等体的状态的最新信息。这通过使覆盖网络中的节点在其目的地对等体正在休眠时负责存储状态更新消息，并在它们醒来时输送状态更新消息到对等体来实现。

如图4b所示，在步骤407，对等体N将要切换到休眠模式，并因此需要将状态更新消息发送到其路由邻居，包括对等体F。对等体N先检查其路由表以检查对等体F的PMS状态(如上所述，对等体N在它具有的用于对等体F的路由表条目中保持此信息)。如果对等体F不在休眠，则对等体N能如在步骤408一样简单地将消息状态更新(2)发送到对等体F。然而，如果对等体F正在休眠，则在步骤409-412，对等体N存储在覆盖网络中的状态更新消息。注意，由于对等体N将要进入休眠模式，因此，它本身存储消息是不够的。当处于休眠模式中时，它将不知道对等体F何时醒来，并且将不能在它正休眠时输送消息。

如上所述，通过要求主指部对等体返回其后继的列表，以及通过保持与所有或一部分这些后继的连接，能够为单一指部间隔保持多个备选指部指示符。因此，对等体F是对等体N的主指部，对等体N也与包括F_neighbour在内的对等体F的直接邻居保持连接。因此，在步骤409，对等体N选择不支持休眠模式(即，始终活动)或当前醒着的对等体F的一个后继。如果对等体F具有始终活动的后继，则对等体N从那些后继的集合中选择离对等体F最近的一个。如果对等体F只有支持休眠模式的后继，并且它们中的一些醒着，则对等体N从活动后继的集合中选择离对等体F最近的一个。在任一情况下，对等体N随后在步骤410向选定后继F_neighbour发送状态更新(3)消息，其中该消息的目的地对等体ID设为对等体F的ID。

在接收状态更新(3)消息时，在步骤411，对等体F_neighbour检查消息的目的地对等体ID，并且确定预期接收方是对等体F。由于对等体F是对等体F_neighbour的直接邻居之一，并且它知道对等体F正在休眠，因此，在步骤412，对等体F_neighbour存储状态更新(3)消息以便一旦对等体F醒来便将该消息输送到对等体F。然而，如果在步骤409，对等体N确定对等体F的直接邻居均未醒着(如步骤409a所示)，则在步骤413，对等体N被迫将状态更新(3)消息直接发送到对等体F，以便对等体F在步骤414醒来。

假设在F的邻居处存储状态更新消息，则如果离对等体F更近的对等体F的另一后继变成活动的，对等体F_neighbour应将它存储的状态更新消息转移到该更近的后继。

对等体F可由于多种原因而醒来-即，不一定是如在步骤414一样因为对等体F接收状态更新消息，而是由于任何原因，诸如因为对等体F的用户想开始呼叫。在对等体F醒来时，它先需要获得当对等体F已休眠时覆盖网络已存储的任何状态更新消息。这允许对等体F了解其邻居的当前状态。如果对等体F具有始终活动的后继，则对等体F能够从最近的始终活动后继获得存储的状态更新消息。然而，如果对等体F没有始终活动的任何后继，则它不能知道哪个后继正在存储对等体F在休眠时发送到它的状态更新消息。另外，对等体F不知道其后继的当前状态。因此，对等体F要逐个联系其后继以了解哪个后继正在存储状态更新。由于状态更新消息始终由最近活动后继存储，因此，对等体F开始联系其最近后继。对等体F一旦发现保留存储的状态更新消息的后继后便能够停止联系其它后继。

将要进入休眠模式的每个对等体P也应在其后继之一中存储寻址到其本身的空状态更新消息。如果对等体P具有不支持休眠模式(即，始终活动)的后继，则空状态更新应存储在最近的此类后继中。如果对等体P的所有后继均支持休眠模式，则对等体P应从活动后继的集合中选择离对等体P最近的活动后继。如果所有后继正在休眠，则对等体P不应存储空状态更新请求，这是因为这样做将迫使它唤醒一个后继。存储空状态更新请求的好处在于在对等体P醒来时，可能其它节点在对等体P正休眠时未存储目的地为对等体P的任何状态更新消息。在醒来时，对等体P需要发现哪个后继正在存储状态更新。如果没有存储的状态更新消息，则对等体P需要联系每个其后继以确保没有后继具有用于它的任何存储的消息。然而，如果对等体P在进入休眠模式前存储了空状态更新请求，则一旦对等体P发现保留空状态更新请求的后继，它便能够停止检查。

一旦对等体F获得了任何存储的状态更新消息，它便了解其直接邻居(即，后继和前趋)及其路由邻居(即，指部)的当前状态。注意，对等体F能够延迟联系其指部和前趋，直至它已从后继之一获得存储的状态更新请求。这样，对等体F始终避免唤醒其前趋和指部中正在休眠的那些的成本；在获得存储的状态更新消息后，对等体F知道其前趋、指部和它在搜索存储的消息时未联系的那些后继的当前状态。

如在图4b中以步骤415示出的一样，在对等体F醒来时，它从休眠更改为受限或活动状态，并将状态更新(4)消息发送到其后继之一F_neighbour以获得后继为对等体F存储的状态更新消息。此状态更新(4)消息由对等体F_neighbour接收。随后，在步骤416，对等体F_neighbour向对等体F发送从对等体N收到的原状态更新(3)消息。在步骤417，对等体F使用在状态更新消息(3)中的信息更新用于对等体N的其路由表条目。

如在图4b中以步骤418所示的一样，在对等体F_neighbour在能够输送状态更新(3)消息到对等体F前必须进入休眠模式的情况下，则在步骤419，它从其自己的路由表中确定不在休眠的对等体F的另一邻居(非休眠F_neighbour)，并且在步骤420将状态更新消息转发到非休眠F_neighbour。

此外，在步骤419，存储目的地为对等体F的状态更新(3)消息的对等体F_neighbour可能在将要进入休眠模式时确定对等体F的所有其它邻居正在休眠。在该情况下，它被迫将状态更新(3)消息发送到对等体F，由此唤醒对等体F。

注意，在覆盖网络除支持休眠模式的对等体外，也具有始终活动(即不支持休眠模式)的对等体时，上述机制实现了最佳性能。具有始终活动的对等体是具有固定和移动对等体的P2P网络中的一种现实假设，这是因为许多固定对等体(例如，带有固定因特网访问的个人计算机)始终活动。然而，如果覆盖网络仅具有支持休眠模式的对等体，则此处所述方案寻求将必须由给定对等体从休眠模式唤醒以发现给定对等体与其保持连接的节点的当前状态的后继的数量降到最低。

例如，SMPU、RMPU和AMPU参数能够被映射到WCDMA无线电资源控制(RRC)状态机的不同状态[3GPP TS 25.331，Yeh 2004]。此RRC状态机具有两种状态，其中终端处于休眠模式以及其中数据传输不可能进行：这些状态是CELL_PCH和URA_PCH状态。在此情况下，SMPU参数指定在这些状态中的最大功耗。RRC状态机也具有CELL_FACH状态，在该状态中终端不具有分配到它的专用信道，但对于上行链路和下行链路传输指配有默认、共用或共享传输信道。此共享传输信道适合用于诸如web浏览等突发业务，并且比专用信道耗用更少的能量。在此情况下，RMPU参数用于指定在CELL_FACH状态中的功耗。最后，RRC状态机具有CELL_DCH状态，在该状态中终端在上行链路和下行链路方向上均分配有专用信道。CELL_DCH状态适合用于诸如话音、流视频和文件传送协议(FTP)业务等业务。能耗比在其它状态中更高，并且因此AMPU参数用于指定在CELL_DCH状态中的功耗。

应注意的是，此处WCDMA只用作一个示例。此实施例的路径查找器机制适用于其它无线技术及具有不同功耗水平的非无线节点。

功率管理状态(PMS)参数在状态更新消息中使用(如上所述)以指定发送节点将要进入的下一功率管理状态。对等协议(如P2PSIP)一般情况下使用二进制编码。如表2所示，PMS参数能够包括为对等协议消息中的二进制值。

表2-PMS参数值

另外，三个功率使用参数(SMPU、RMPU和AMPU)能够包括为二进制值。假设在0与4095之间的12比特值范围对每个功率使用参数是足够的，总共只需要38比特(36比特用于功率使用参数，加上2比特用于PMS参数)添加到对等协议消息。因此，发送另外参数代表了发送消息的功耗和成本的极小量增加。

知道其对等体的功率使用参数和PMS参数允许对等节点N做出路由判定以将功耗降到最低。图5的流程图中示出采用DHT的覆盖网络的节点使用本发明的经济路径查找器机制的概述。该节点保持路由表，对于节点的每个路由邻居，路由表包含节点的覆盖网络地址与节点的物理定位器之间的映射。该节点也保持用于每个路由邻居的路由表中的或与该路由表相关联的路由邻居的功率使用参数和PMS参数。在步骤501，节点确定(或通过覆盖网络接收指示)消息要通过覆盖网络发送到目的地。在步骤502，节点确定(根据在使用的DHT算法)消息要转发到的可能路由邻居的集合。在步骤503，节点检查其路由表并确定每个选定路由邻居的功率使用参数和PMS参数。在步骤504，它在发送消息到每个路由邻居的功耗方面(如上所述)计算成本。最后，在步骤505，它将消息发送到具有最低功耗成本的路由邻居。

这将相对于两个示例更详细地描述。对等体N先确定要路由到目的地对等体D的消息的备选下一跳对等体的集合。在我们的第一示例中，我们将假设最靠近D的标识符的指部间隔(即，路由表条目)包含表3中所列的四个对等体F1、F2、F3和F4。PMS参数示出对等体F1、F2和F3处于休眠模式，而对等体F4处于活动状态。在此情况下，最佳判定是将消息路由到对等体F4，因为这不涉及另外功耗。应避免将消息路由到F1、F2和F3，这是因为这些对等体将需要从休眠模式醒来(即，其功耗将从SMPU增大到RMPU)以便能够接收新消息。假设处于休眠模式的对等体在醒来时先转变到受限模式。对等体可在以后(例如)需要更高带宽时进入活动模式。因此，始终通过从RMPU减去SMPU来计算唤醒对等体时功耗的增大。

表3-用于指部间隔的备选指部指示符的第一示例

  对等体  PMS  SMPU  RMPU  AMPU  F1  休眠  10  100  250  F2  休眠  500  1000  2000  F3  休眠  500  750  1500  F4  活动  10  125  800

如果所有对等体F1、F2、F3和F4都处于休眠模式，则出现了一种不同情况。在该情况下，对等体N需要决定唤醒哪个对等体。为此，此对等体N计算在唤醒四个对等体中每个对等体时涉及的功耗增大(RMPU-SMPU)，并选择增大最小的对等体，在此示例中这是对等体F1，功耗增大为90mW。

注意，如果所有对等体F1、F2、F3和F4均处于活动模式，则所有对等体以峰值功耗操作。在该情况下，对等体N能够自由选择下一跳对等体，这是因为将不存在功耗的增大(或者它能够使用不同的选择方法，例如负载平衡机制)。

表4示出第二示例的功耗和PMS参数，其中，对等体F1处于休眠模式，并且对等体F2、F3和F4处于受限模式。在此情况下，节点N应避免唤醒对等体F1，并且从对等体F2、F3和F4之中选择作为当前和将来消息的优选下一跳对等体。这能够意味着选定对等体将需要从受限模式转到活动模式(例如，因为它需要增大其带宽以处理业务的增大)。对等体N因此应选择从受限模式转到活动模式时功耗增大最小的对等体。对等体F2、F3和F4的功耗增大分别是1000mW、750mW和675mW。因此，应选择对等体F4。

表4-用于指部间隔的备选指部指示符的第二示例

  对等体  PMS  SMPU[mW]  RMPU[mW]  AMPU[mW]  F1  休眠  10  100  250  F2  受限  500  1000  2000  F3  受限  500  750  1500  F4  受限  10  125  800

图6以示意图方式示出适合用于实现所述方法的覆盖网络的节点1。节点包括状态确定块2，该块能够确定节点将要切换到的操作状态，即休眠、受限或活动。功耗块3记录在各种操作状态的功耗。如果状态更改即将发生，则信息传播器(information disseminator)4配置为向对等节点(邻居和指部)提供所需状态更新。分组路由器5接收经由覆盖网络发送的分组，并根据判定块6提供的指令适当地转发它们。

基于DHT的覆盖网络能够以迭代或递归方式路由消息。上述实施例是基于使用递归路由的覆盖网络，其中，对等体将消息转发到朝向目的地对等体的路径上的下一跳对等体。换而言之，对等体X在接收目的地为对等体Y的消息时，将目的地为Y的消息转发到下一跳对等体(或在对等体X知道对等体Y的联系地址时，直接转发到对等体Y)。在迭代路由中，对等体不转发消息。相反，对等体只返回其它节点的联系地址。因此，如果对等体X从对等体W接收以对等体Y为目的地的查找查询，则对等体X将向对等体W返回对等体Y的联系地址(如果对等体X知道该地址)，或者在朝向对等体Y的路径上的下一跳对等体的联系地址。在迭代DHT算法(诸如Kademlia)中，所有路由判定由查找启动方(即，始发对等体)做出。因此，在使用迭代DHT算法的本发明的实施例中，在对等体返回有关其它可能下一跳节点(Kademlia中的k个节点)的信息时，它包括其它节点的功率使用参数(SMPU，RMPU，AMPU)和PMS及路由表条目，以便查找启动方能够执行做出最佳路由判定所需的计算。另一方面，在递归DHT算法中，路由判定由转发节点做出，因此，无需在查找期间在节点之间发送功率使用参数。

在使用迭代路由的覆盖网络中，查找请求的接收方通过查找响应回复查找启动方。查找响应包括响应方了解的离查找目标最近的节点的路由表条目。因此，当正在使用经济路径查找器机制时，响应方能只将SMPU、RMPU、AMPU及PMS参数包括到查找响应中。查找启动方随后能使用这些参数计算在朝向目标节点的路径上的最佳下一跳节点。例如，在基于Kademlia DHT算法的覆盖中，响应方不返回<节点ID，IP地址，端口>三元组，而是返回它了解的离目标节点最近的k个节点的<节点ID，IP地址，端口，SMPU，RMPU，AMPU，PMS>七元组。

在此实施例中，参与基于迭代DHT的覆盖网络的对等体保持每个路由表条目的备选联系。诸如Kademlia等一些DHT算法对于每个路由表条目默认保持多个联系。如上所述，Kademlia中的路由表条目称为k桶，并且每个k桶包含最多k个对等体的联系信息。在接收查找请求时，节点将有关它了解的离查找目标最近的k个节点的信息返回到查找启动方。此信息不再是三元组(如上所述)，而是每个k节点的七元组<节点ID，IP地址，端口，SMPU，RMPU，AMPU，PMS>。查找启动方使用此信息构建基于联系每个可能的下一跳节点的成本(在功耗方面)排序的列表。随后，通过选择带有最低成本的a个节点，并将迭代查找请求发送到这些节点来进行下一轮的迭代查找。仅在较低成本对等体未能返回带有离查找目标更近节点的地址的响应时才联系较高成本的对等体。

诸如Chord等其它DHT算法不保持冗余路由表条目，但能够轻松地修改为保持冗余路由表条目。如已经描述的一样，实现此方面的一种方式是为每个指部间隔保持多个指部指示符。例如能够通过要求每个指部返回其后继指示符而获得备选指部指示符。指部对等体及其后继随后能用于构建指部指示符集合。转发节点随后能基于节点的功耗信息，从指部指示符集合中的节点中选择下一跳节点。

除功率使用参数外，对等体也能将有关其剩余电池容量的信息发送到其路由邻居。例如，对等体能够通知其邻居，如果它仍处于活动状态(功耗保持在AMPU)，则它15分钟就会用尽电池容量。此信息能够用于进一步优化路由判定。更具体地说，它能用于防止在接近用尽电池电能时将低成本对等体从休眠模式唤醒的情况。这能够实现为一种可配置限制，以便其剩余电池时间小于预定义量的对等体除非是绝对必需(例如它是查找目标时)，否则将不被从休眠模式唤醒。通过将剩余电池时间作为新参数包括在连接和状态更新请求中和/或包括在诸如保活(keep-alive)消息和路由表同步消息等周期性DHT维护消息中，能够将它传递到其它对等体。此新参数此处称为剩余电池时间(RBT)参数，并且它包含消息的发送方以秒为单位的剩余电池时间。非电池供电对等体可将RBT参数的值设为特殊值，诸如“-1”，以向其它对等体指示它们无需将所述的对等体的剩余电池电能考虑在内。

然而，除无线电池供电对等体外，在其它类型对等体具有不同操作功耗水平的情况下，例如，非电池供电对等体具有有线网络连接(例如，在个人计算机上运行的对等体)，功率使用参数也可由那些对等体使用。

诸如分层网络等一些覆盖网络使用超级对等体操作DHT，有两种类型的节点：超级对等体和客户端。两种类型的节点之间的不同之处在于超级对等体参与DHT的操作(即，路由消息和存储在覆盖中的资源，以及参与DHT维护操作)，而客户端通过一个或多个超级对等体使用覆盖网络的服务。带有足够资源(诸如带宽、公共IP地址等)的移动对等体可被选择为充当分层P2P覆盖网络中的超级对等体。在此类情况下，可使用超级对等体的功率使用参数和PMS参数，以便连接到多个超级对等体的客户端能操作本发明的经济路径查找器机制，以便从客户端连接到的超级对等体的集合中选择在功耗方面最低成本超级对等体。

在WCDMA中覆盖网络的上述示例中，为使用经济路径查找器机制，在移动终端上运行的应用需要具有对无线电资源控制(RRC)状态信息的访问权。此信息能由在终端的本地平台上运行的应用访问，该应用可由终端供应商提供。另一方面，受信任的第三方应用也可通过终端上的供应商特定应用编程接口(API)访问此信息，条件是API配置为访问此类信息。然而，如果在终端上运行的Java应用访问该信息，则不需要来自供应商提供的API的支持。此类应用可由终端借助于Java规范请求(JSR)获得。

然而，可存在第三方P2P应用不具有对终端的RRC状态信息的访问权，或者终端配置为不提供其功耗信息到第三方(即，在相关API是专用的情况下)的情况。在此类情况下，第三方应用可能通过参考终端的型号来获得功率使用参数。例如，此信息可从web服务器得到，或者它可包括为随P2P应用提供的数据。P2P应用可配置为通过参考系统属性来确定终端的型号。例如，终端的系统属性可变得对于所有基于Java微编辑(JME)的应用是可用的。

不过，不具有对RRC状态信息的访问权的P2P应用不能确定终端的PMS状态，并且因此不能知道终端是处于休眠还是处于活动或受限模式。在该情况下，P2P应用在它发起的对等协议消息中将PMS参数设为“未知”。

对其中PMS参数包括一个或多个“未知”参数的路由判定处理如下：

A)如果备选下一跳节点的集合包含处于活动模式的至少一个对等体以及其功率管理状态未知的一个或多个对等体(及可能包括其状态为“受限”或“休眠”的其它对等体)，则消息始终路由到活动对等体之一。这避免了增大其状态未知但正好处在非活动模式的任何对等体的功耗的任何风险。

B)如果备选下一跳节点的集合中没有活动对等体，但存在其功率管理状态未知的一个或多个对等体(及可能包括其状态为“受限”或“休眠”的其它对等体)，则从该对等体的集合中选择带有未知状态以及带有最低AMPU值的对等体。在此情况下，假设其功率管理状态未知的所有对等体处于活动状态。这避免了将消息路由到带有大活动模式功耗的节点，同时仍避免了路由到已知为休眠或处于受限模式的对等体。

下面的表5中给出了备选下一跳节点的集合的功率使用和PMS参数的一个示例。在此情况下，消息应路由到对等体F1，这是因为(A)没有活动对等体，以及(B)在其功率管理状态未知的两个对等体中，对等体F1具有最低AMPU。注意，在对等体的功率管理状态未知时，SMPU和RMPU值是不相关的。

表5

  对等体  PMS  SMPU  RMPU  AMPU  F1  未知  -  -  250  F2  来知  -  -  1000  F3  休眠  500  750  1500  F4  受限  10  125  1250

本领域的技术人员将理解，在不脱离本发明范围的情况下，可对上述实施例进行各种修改。