无线个人区域网中建立最佳路由的路由选择系统及其方法

摘要

一种在具有包括目的节点和源节点在内多个节点的移动通信系统中进行路由选择的系统和路由选择方法，旨在建立到目的节点的路由，其中至少一个节点不存储路由表。该方法包括：存储关于中间节点的信息，该中间节点使用包括在接收到的路由请求消息中的信息转接路由请求消息；并且发送路由请求消息到相邻节点。通过使用存储的消息、响应与接收到的路由请求消息的应答消息被转送到请求路由建立的节点。

说明书

技术领域

本发明一般涉及一种无线个人区域网(WPAN)，更具体而言，涉及在无线个人区域网中建立从源节点到目的节点的路由的路由选择系统和方法。

背景技术

一般来说，数据在移动通信系统中的移动单元和基站之间被发送和接收。也就是说，移动单元和基站无需经过其它节点而是直接发送和接收数据。相比之下，无线个人区域网(WPAN)已发展成在很短的距离内互相连接设备。WAPN是一种特设(ad-hoc)的数据通信系统，允许多个节点相互间进行通信。包含于特设网络中的发送节点经由其它的节点将数据发送至接收节点。如果接收节点在发送节点的邻域内，数据在节点间被直接发送。现在参照图1，根据常规的算法关于配置特设网络的节点描述了数据发送。

图1的特设网络包括至少两个节点。节点分为两种，一种是保留路由表的节点，由“N+”表示。另一种是没有路由表的节点，由“N-”表示。

将在下面描述在包括N+及N-的特设网络中建立路由的常规方法。让节点A作为源节点，节点I作为目的节点。源节点请求到目的节点的路由设置。这样，在步骤S100，节点A发送路由请求RREQ消息到邻近的节点B以建立到节点I的路由。节点B是一个N+节点，用所接收到的RREQ消息产生一个路由表，并存储所产生的路由表。在步骤S102和S108，刚一接收到RREQ消息，节点B就分别发送RREQ消息到节点C和G。节点C是一个N+节点，也用接收到的RREQ消息产生一个路由表，并存储所产生的路由表。在步骤S104和S106，刚一接收到RREQ消息，，节点C就分别发送RREQ消息到节点D和F。

在步骤S128，刚一接收到RREQ消息，节点G就响应RREQ消息发送路由应答RREP消息到节点B。根据常规的算法，特设网络中的N-节点响应RREQ消息发送RREP消息。尽管N-节点不是接收到的RREQ消息中请求的目的节点，但由于可依据群集树(cluster-tree)路由器的计算发现目的节点的下一个跳跃节点(hop node)，因此N-节点可发送RREP消息，而无需进行最佳路经的查找。在步骤S120，来自节点G的RREP消息经由节点B被转送到节点A。在步骤S110，刚一发送RREP消息，节点G就发送RREQ消息到相邻的节点F。一般来说，N-在设计阶段知道在一定距离内的节点，比如，1个跳跃的信息。

节点D完成与节点G相同的操作。因此，在步骤S124，S122，和S120，由节点D产生的RREP消息经由节点C和B转送到节点A。在步骤S112和S114，刚一从节点C或节点G接收到RREQ消息，节点F就分别发送RREQ消息到节点E和节点H。节点E完成与节点D相同的操作。在步骤S116，节点H转送接收到的RREQ消息到节点I。刚一接收到RREQ消息，节点I就识别出节点A已向其请求路径。从而，节点I响应RREQ消息产生RREP消息。RREP消息沿着RREQ消息的路由转送给节点A。结果，节点A和节点I之间的路由被建立。尽管没有描述，具有路由表的N+节点更新接收到的RREQ消息，并将已更新的RREQ消息转送到相邻的节点。一般来讲，N+节点更新并转送跳跃数到相邻的节点。具有最少跳跃数的路由被选择作为节点间的路由。根据前面的叙述，节点A响应于单个RREQ消息接收到4个RREP消息。其间，对于N-节点不必发送RREP消息。

图2说明了使用特设网络节点建立路由的另一个示范性的过程；图2说明的过程引起环路(loop)问题。在当前的举例中，在节点A和节点E间建立路由，并且到节点E的路由根据节点A的请求经由节点B，C和D被建立。然而，由于如图2所示的信道恶化，节点D和节点E之间的无线信道可以被切断。在这种情况下，节点D转送路由选择错误RERR消息到节点A。RERR消息包括指示节点D和E间路由故障的信息。来自节点D的RERR消息经由节点C和B转送到节点A。然而，由于节点A和B，或节点B和C之间的无线信道恶化，RERR消息也可以被转送到节点A。

如果一个新的分组产生以从节点D发送到节点E，在步骤S200，因为节点D已经知道由于节点D和E间的无线信道恶化，链路被破坏了，因此节点D广播RREQ消息以找到到节点E的新路由，然而，如果有无线信道断开，节点E不能从节点D接收到RREQ消息。如果节点C接收RREQ消息，在步骤S202，节点C广播RREQ消息。在步骤S204，接收到RREQ消息的节点F广播RREQ消息。在步骤S210，刚一接收到RREQ，作为一个N-节点的节点A根据群集树路由器计算，识别经由节点B到目的节点E的路由，并发送RREP消息到节点F。在步骤S212，刚一接收到RREP消息，节点F就发送RREP消息到节点C，并且在步骤S214，刚一接收到RREP消息，节点C就发送RREP消息到节点D。根据图2的过程，节点D的数据分组沿路由D→C→F→A→B→C→D被发送，结果，数据分组不是沿着已建立的路由被发送，并且产生了不必要的环路。

图3说明了依据常规的算法，使用特设网络中的节点建立路由的另一个示范性的过程；图3说明的这一过程也引起环路问题。节点E旨在建立到节点A的路由。在步骤S300和S302，节点E分别发送RREQ消息到节点D和F。在步骤S308和S304，节点D分别发送RREQ消息到节点C和G。在步骤S306，节点F也发送RREQ消息到节点G。在步骤S330，节点G发送RREP消息到节点F。在步骤S332，节点F发送接收到的RREP消息到源节点E。这是允许的，因为到源节点E的路由通过节点F，依照群集树路由器的计算能被计算出来。在步骤S310，刚一接收到RREQ消息，节点C就发送RREQ消息到节点B。在步骤S312，刚一接收到RREQ消息，节点B就发送RREQ消息到节点A。刚一接收到RREQ消息，节点A就识别出它是节点E请求的路由的目的节点。因此，节点A响应RREQ消息产生RREP消息。在步骤S320，S322，和S324，所产生的RREP消息经由节点B和C被转送到节点D。在步骤S326，节点D转送接收到的RREP消息到节点E。当源节点E早于节点A从节点G接收RREP消息时，问题就发生了。在这种情况下，分组的发送路由形成沿着路由D→G→F→D的环路。

图4也说明了根据常规的算法，使用特设网络的节点建立路由的又一个示范性的过程，其中，正向和后向路由互不相同。

节点A试图建立到节点E的路由。节点A通过查询所存储的路由表确定到节点E的路由是否被建立。当它确定没有节点E的路由，在步骤S400，节点A发送RREQ消息到节点B。刚一接收到的RREQ消息，节点B也查询存储的路由表并确定到节点E的路由是否被建立。在步骤S402，当确定没有建立到节点E的路由时，节点B发送RREQ消息到节点C。

节点C确定它是否是节点A请求的路由的目的节点。因为节点C不是目的节点，在步骤S404，节点C沿群集树路由向节点D发送RREQ消息。节点D也确定它是否是节点A请求的路由的目的节点。因为节点D不是目的节点，在步骤S406，节点D发送RREQ消息到节点E。节点E识别出它是节点A请求的路由的目的节点。

节点E响应RREQ消息产生RREP消息。在步骤S410，产生的RREP消息被发送到节点D。在步骤S412，节点D发送接收到的RREP消息到节点F。节点F沿着树转送RREP消息到源节点A。结果，正向路由与后向路由不同，并且需要解决该问题。

发明内容

本发明示范性的方面是解决至少上述问题和/或缺点并且至少提供下面描述的优点。因此，本发明示范性的方面是提供一种用来防止响应RREQ消息接收多个RREP消息的系统和方法，。

本发明的另一个示范性的方面是提供一种允许源节点迅速确定给定路由的断开的系统和方法。

本发明的再一个示范性的方面是提供一种防止路由中的环路的系统和方法。

本发明的又一个示范性的方面是提供一种建立与正向路由相同的后向路由的系统和方法。

本发明的又一个示范性的方面是提供一种建立关于单个目的节点具有最小跳跃数的单个路由的系统和方法。

为了实现上述本发明的方面，一种在具有包括目的节点和源节点的多个节点的移动通信系统中的转接方法，旨在建立一个到目的节点的路由，其中，至少一个节点没有存储路由表。本方法包括：存储关于转接节点的信息，该转接节点使用包含于接收到的路由请求消息中的信息转接路由请求消息；发送路由请求消息到相邻的节点；以及通过使用所存储的信息、转送响应接收到的路由请求消息的应答消息到请求路由建立的节点。

一种涉及具有包括目的节点和源节点的多个节点的移动通信系统的路由选择系统，旨在建立一个到目的节点的路由，该无线通信系统具有至少一个不存储路由表的节点。该移动通信系统包括一个用于产生路由请求消息并将产生的路由请求消息发送到邻近节点的源节点，还包括一个中间节点，用于使用包含于接收到的路由请求消息中的信息存储关于转接节点的消息；该中间节点不在路由表中存储响应接收到的路由请求消息的应答消息。

附图说明

从下列结合附图的实施例的描述中，这些和/或本发明的其它的方面和优点，将变得清晰并且更加容易被理解。

图1是示出用于在特设网络中建立路由的常规过程的一个例子的图；

图2是示出用于在特设网络中建立路由的常规步骤的另一个例子的示意图；

图3是示出用于在特设网络中建立路由的常规步骤的又一个例子的示意图；

图4是示出用于在特设网络中建立路由的常规步骤的再一个例子的示意图；

图5是说明了根据本发明的实施例，由源节点建立路由的示范性步骤的流程图；及

图6是示出用于根据本发明的实施例，在特设网络中建立路由的示范性步骤的示意图。

具体实施方式

现在将对本发明的实施例做详细描述，举例在附图中被说明，其中，相同的参考数字在全文中代表相同的单元。为了解释本发明，参照附图，在下面详细描述本发明的实施例。

图1说明了响应单个的RREQ消息至少两个RREP消息被发送的情况。为了致力于克服图1中所示的缺点，N-节点可以限制发送RREP消息。详细来说，仅当所接收到的RREQ消息的目的节点是它本身时，N-节点才能发送RREP消息。结果，节点D，E和G将不发送RREP消息，并且只有节点I将产生转送给节点A的RREP消息。

正如上面指出的那样，图2说明了由于在特设网络中建立的路由导致环路时的情况。为了致力于克服图2中所示的缺点，保持有效(KEEP-ALIVE)消息替代RERR消息被发送。保持有效消息可以包括源节点A和目的节点E的地址。节点E在第一预定时间间隔可将保持有效消息转送给节点A。第一预定时间间隔可被使用者调整。如果特设网络的节点间的无线信道恶化，第一预定时间间隔可以被调整的短些。如果节点间的无线信道是正常的，第一预定时间间隔可以被调整的长些。节点E沿预设的路由转送保持有效消息。也就是说，节点E沿着路由D→C→B转送保持有效消息到节点A。

节点A可以确定在第二预定时间间隔保持有效消息是否从节点B被接收。一般来说，第二预定时间间隔可以设置的比第一设定时间长一些，因为从节点E发送到节点A的保持有效消息的发送由于无线信道故障而可能被延迟。

节点A可以确定在第二预定时间间隔内保持有效消息是否被接收。如果节点A确定在第二预定时间间隔内保持有效消息已经被接收，它将识别出在节点A和节点E之间的路由是正常的。如果节点A确定在第二预定时间间隔内保持有效消息没有被接收到，它将识别出在节点A和节点E之间的路由发生故障。这样，节点A可以重新发现一个到节点E的新路由。为了减少建立和重新发现路由的时间，预设路由被使用。

图5是说明了根据本发明的示范性的实施例由源节点执行的特定示范性步骤的流程图。现在参照图5，由源节点执行的示范性步骤将变得清晰。如上面所描述的，目的节点在第一预定时间间隔发送保持有效消息。

在步骤S500，源节点设置关于目的节点的消息并且设置相应于目的节点的第二预定时间间隔。一般来说，源节点从至少两个目的节点接收保持有效消息。在图5所示的实施例中，为了清楚起见，仅从单个目的节点接收保持有效消息。

在步骤S502，源节点启动计数。在步骤S504，源节点确定保持有效消息在第二预定时间间隔是否被接收。如果保持有效消息被接收，在步骤S508，源节点复位计数。如果没有接收到，在步骤S506，路由被重建。在步骤S508后，源节点返回到步骤S502。根据前面的叙述，重建的路由是一个预设的路由。

为了致力于克服如前面参照图3和图4描述的缺点，本发明提出N-节点存储最小限度的信息。这样小限度的信息可被存储在路由表中。根据本发明的示范性实施例，RREQ和RREP消息将仅包含必要的信息。RREQ消息可包括源节点的地址和RREQ标识符(ID)，目的节点的地址，和跳跃数。RREP消息可包括源节点的ID和目的节点的地址，跳跃数，沿着路由的N+节点的数目。沿着路由的N+节点将在后面描述。

表1描述了N-节点中存储的路由表的一个例子。

                         [表1]

                         源节点地址

         目的节点地址         RREQ ID         跳跃数         N+节点数

尽管图3中的源节点E接收到两个RREP消息，通过选择具有沿着E→D→C→B→A的更少跳跃数的路由，环路问题可以被避免。

图6说明了正向路由与反向路由相同的情况。

节点A旨在建立一个到节点E的路由。从节点A到节点E的RREQ消息的发送与图4中的相同。从节点E到节点A的RREP消息的发送将在下面进行详细描述。

节点E响应RREQ消息产生RREP消息。在步骤S410，产生的RREP消息被发送到节点D。节点D识别出相应于RREP消息的RREQ消息已经使用存储的路由表从节点C被接收。因此，在步骤S414，节点D发送RREP消息到节点C。节点C识别出相应于RREP消息的RREQ消息已经使用存储的路由表从节点B被接收。因此，在步骤S416，节点C发送RREP消息到节点B。在步骤S418，依据存储的路由表，节点B发送RREP消息到节点A。因此，依据N-节点中信息存储的最小限度需求，正向路由与反向路由相同。

作为选择，RREP消息可以包括关于“边界”节点的信息。“边界”节点是指一个沿着其它树路由连接节点的节点。回过来参照图6，其它树路由包括从节点F到节点A的路由，从节点F到节点B的路由，以及从节点F到节点C或E的路由。在建立正向路由中，节点A，B和C分别定位在不同的路由。这样，RREP消息包含边界节点的信息。在步骤S410，节点E发送所产生的RREP消息到节点D。在步骤S414，节点D从接收到的RREP消息中获得关于节点C的信息，并根据获得的信息，发送RREP消息到节点C。在步骤S416，节点C从接收到的RREP消息获得关于节点B的信息，并根据获得的信息，发送RREP消息到节点B。在步骤S418，通过使用存储的路由表或RREP消息中的信息，节点B发送接收到的RREP消息到节点A。尽管上面没有描述，每个节点更新接收到RREP消息并发送更新的RREP消息到下一个节点。

因为N+节点比N-节点的错误概率低，当至少两个路由被设置到单个目的节点时，沿着路由的N+节点数被包含在RREP消息中，以便沿着有更多N+节点的路由发送数据。

尽管已经描述了本发明的实施例，对于本领域的技术人员来说，一旦掌握了的基本发明概念，就可以对实施例做出另外的变化和修改。因此，意图是随后的权利要求将被解释为包括前面的实施例和落入在本发明的精神和范围内的所有的变化和修改。