CN103444231A

CN103444231A - 网络中节点集合的发现

Info

Publication number: CN103444231A
Application number: CN2012800146731A
Authority: CN
Inventors: C·隆布里泽; H-L·特鲁昂; U·亨克勒
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 2011-03-30
Filing date: 2012-03-12
Publication date: 2013-12-11
Anticipated expiration: 2032-03-12
Also published as: US20140016560A1; DE112012000699B4; GB2503146A; US20160308728A1; US10027552B2; US20180167284A1; GB201316093D0; US11038767B2; WO2012131512A1; CA2824268C; DE112012000699T5; CN103444231B; GB2503146B; US9414296B2; CA2824268A1; MX2013008626A; JP6029120B2; US20200044935A1; US10523515B2; JP2014514825A

Abstract

本发明特别地涉及用于发现网络（165）中的节点集合（20，30）的方法和系统，包括：-在待处理的节点群组中的节点之中选择（S11）节点（20）；以及，-指示（S12）实现针对所选择的节点的发现过程，所述过程包括：10-在网络的共享传输介质（1）上从当前选择的节点（20）广播（S22）邻居发现请求；以及，-在当前选择的节点（20）处接收由邻居节点在共享传输介质上发送（S34）的回复，并且将所述邻居节点添加（S13）到待处理节点群组中；以及，-针对待处理节点群组中的其他节点（30）来重复选择和指示的步骤，直到发现集合的所有节点。

Description

网络中节点集合的发现

技术领域

本发明概括地涉及用于允许在网络中发现节点集合的计算机化方法和系统，并且特别地涉及对于集中无线传感器网络架构的拓扑发现过程。

背景技术

例如在环境监测或者数据采集领域中，多对一通信是诸如传感器网络应用的网络应用的常见需求。传感器节点（SN）基本上与基站（BS）交换信息，SN之间很少交换信息。SN生成周期数据采样并且将其发送（可能使用其他SN来转发消息）至BS以用于进一步处理。

与SN相比，BS通常配备有更加强大的处理单元以及用于程序和数据的更多的存储器。集中式网络架构最适合这种环境，因为其可以开发BS中可用的资源来执行复杂的路由功能，由此保持传感器节点尽量简单。

为了能够计算所需要的路由信息，BS需要知道网络的完整拓扑，即，所部属的所有SN以及这些节点之间的无线链路的质量。

在相当静态的网络拓扑的情况下，BS可以被手动地配置拓扑信息，但是这种方法易于出错，并且在无线SN的数目较大时变得不切实际。

大多数传感器网络具有分布式架构，其中，传感器节点通过与相邻节点交换信息来建立本地拓扑数据库。在这种分布式架构中，不需要知道“全局”拓扑。

所谓的PEDAMACS架构[1]是集中式传感器网络架构，其操作需要自动拓扑发现。PEDAMACS的拓扑发现包括两个阶段：拓扑学习和拓扑收集阶段。BS通过广播协调消息而开始学习阶段，假设该协调消息将被网络中的所有节点接收到。在协调消息之后，BS利用由SN重新广播的树构造消息来泛洪网络。节点使用其从邻居接收的树构造消息来建立其本地拓扑信息（即，其相邻节点和到这些节点的链路的质量），并且选择在其想要向BS发送消息的情况下将使用的节点（父节点）。

在拓扑学习阶段之后，BS还通过广播协调消息而开始拓扑收集阶段，再次假设该协调消息将被网络中的所有节点接收。当节点接收到第二协调消息时，其向其父节点发送在前一阶段已经收集的本地拓扑，以便随后向BS转发。

在两个阶段中，节点彼此之间尚未协调，并且使用载波感应多路访问（CSMA）来处理可能的传输冲突。

TSMP[2]是另一种集中式传感器网络架构。这是基于TDMA的，并且保留时隙用于周期邻居发现过程。在该时隙期间，节点随机地交换发现消息以用于链路探测的目的。通过周期性健康报告的方式报告结果。

Chandra等人[3]公开了混合无线网络中的自适应拓扑发现，其中网络发现过程接近于PEDAMACS的网络发现过程。也就是，该过程包括将发现消息泛洪（广播）到网络中。有趣的是，通过发送机重传直到接收到确认来确定所广播的消息的接收。该解决方案增加了所传输的消息的总数，并且随之需要广播强度。

上文引用的以下参考由此作为本发明的背景技术的一部分：

[1]S.C.Ergen,P.Varaija,“PEDAMACS:Power Efficient andDelay Aware Medium Access Protocol for Sensor Networks”，IEEETrans on Mobile Computing，第5卷第7号，2006年7月；

[2]K.Pister,L.Doherty,“TSMP:Time Synchronized MeshProtocol”,Proc IASTED Int.Symposium Distributed Sensor Networks(DSN2008),2008年11月16-18日，美国佛罗里达州奥兰多；以及

[3]R.Chandra,C.Fetzer,K.Hogstedt;“Adaptive TopologyDiscovery in Hybrid Wireless Networks”;Informatics’02。

发明内容

根据第一方面，本发明实现为一种发现网络中的节点集合的方法，包括：

-在要被处理的节点群组中的节点之中选择节点；以及

-指示实现针对所选择的节点的发现过程，所述过程包括：

-在网络的共享传输介质上从当前选择的节点广播邻居发现请求；以及

-在当前选择的节点处接收由邻居节点在共享传输介质上发送的回复，并且将所述邻居节点添加到待处理节点群组；以及

-针对所述待处理节点群组中的其他节点（30）重复（S14）选择和指示的步骤，直到发现集合的所有节点。

在其他实施方式中，所述方法可以包括以下特征中的一个或多个：

-在针对当前选择的节点的发现过程期间，在接收到至少一个回复之后，并且优选地，在接收到若干回复之后，触发针对其他节点来重复选择和指示的步骤；

-指示包括指示经由源路由机制来实现针对所选择的节点的发现过程；

-最初从诸如基站的源节点实现源路由机制；

-该方法还包括：指示实现针对所选择的节点的链路探测过程，所述链路探测过程包括：从当前选择的节点向邻居节点发送一个或多个链路探测消息，以用于链路质量的后续测量，其中，发送优选地包括在共享传输介质上广播所述一个或多个链路探测消息；

-在完成针对至少所述所选择的节点的发现过程之后，优选地，在已经发现节点集合的所有节点之后，针对所选择的节点实现链路探测过程；

-链路探测过程的实现与发现过程交织，以使得在实现针对所选择的节点的发现过程时接收的回复中的至少一个回复包括与当前选择的节点和邻居节点之间的链路质量的测量相关的数据；

-在广播所述邻居发现请求之前执行发送所述一个或多个链路探测消息；

-在实现针对所选择的节点的发现过程时接收的回复由邻居节点单播；

-在实现针对所选择的节点的发现过程时接收的回复由邻居节点使用类似于CSMA的协议来单播，从而所述回复中的每一个在共享介质上没有其他业务的情况下被发送；

-在实现针对所述所选择的节点的发现过程时接收的回复仅在有限时间期间在所选择的节点处被考虑；以及

-重复广播邻居发现请求的步骤，其中优选地，邻居发现请求包括与邻居节点是否应当回复有关的信息。

根据另一方面，本发明实现为使用包括节点集合的网络的方法，包括：根据前述权利要求中任一项所述的方法发现所述节点集合中的节点；以及，使得所发现的节点使用时分复用进行通信。

根据又一方面，本发明实现为驻留在计算机可读介质上的计算机程序，包括用于使得计算机化网络的节点实现根据本发明的实施方式的方法的步骤中的每个步骤的指令。

根据最后一个方面，本发明实现为计算机化网络，包括节点，优选地包括传感器节点，每个节点具有与存储器可操作地互连的至少一个处理器，从而计算机化网络配置用于实现根据本发明的实施方式的方法的步骤中的每个步骤。

现在将通过非限制性示例的方式并且参考附图来描述实现本发明的网络、方法和计算机程序功能。

附图说明

-图1和图2示意性地示出了根据实施方式的网络发现过程中不同步骤的网络节点；

-图3示意性地绘出了根据本发明的实施方式的适用于实现方法步骤的计算机化单元（例如，基站或者传感器节点）的示例；

-图4是示出根据实施方式的与链路探测过程交错的网络发现过程的高层步骤；

-图5示出了实现在备选实施方式中的典型高层步骤的另一流程图，其中在链路探测过程之前执行发现过程；

-图6-图10将图5的步骤中的一些分解为实施方式中包括的详细的子步骤。

具体实施方式

首先，讨论根据本发明的实施方式的方法的一般方面连同其高层变化（部分1）。接下来，在部分2中，描述更加具体的实施方式。

1、本发明的一般方面

参考图1-图10，本方法在计算机化网络165中实现，该计算机化网络165包括节点20、30，该节点20、30使用共享传输介质1（例如，无线）用于通信。优选地，如贯穿以下示例所讨论的，网络是无线传感器网络。

通常，假设以源节点10为中心的集中式网络架构，在下文中称为基站（BS）。此类环境采用BS中可用的资源来执行重要任务，诸如路由功能，保持节点功能尽可能简单。

在下文中，将描述迭代过程，该过程允许节点的自动发现。如图1和图2所示，标号20表示“当前”选择的节点；标号30表示邻居节点。当前选择的节点在下文将讨论的迭代过程中会改变。可以伴随地或者随后探讨节点之间的双向链路的质量。

此类过程允许发现距离源节点若干跳的节点；还允许较短和确定的运行时间。另外，在操作之间节点不需要维护少量状态信息或者不需要维护任何状态信息。

1.1方法的一般实施方式

从监控实体（例如，BS）的角度来看，实现了以下步骤（重点为图1、图2、图4和图5）：

-步骤S11：在标记为“待处理”的节点之中首先选择节点20，意味着必需针对该节点执行网络发现（ND）过程的实现。被标记为“待处理”的节点的群组（例如，列表）通常在BS处维护。在第一次迭代时，BS选择其自身作为“待处理”节点；

-步骤S12：对所选择的节点20指示实现ND过程。ND过程包括：

ο步骤S22：在共享传输介质1上（即，从当前选择的节点20）广播ND请求；以及

ο步骤S23：接收（即，在当前选择的节点20处）由邻居节点30响应于ND请求而在共享传输介质上发送的回复，参见步骤S34。回复节点从而被标识为潜在的待处理节点。因此，将其添加到“待处理”节点的群组中，例如，当前选择的节点20或者BS。明显地，如果所述节点已经被处理，则不需要将其添加到（或者保持在）群组中。例如，节点20向BS报告已经回复的所有节点，并且BS确定哪些节点仍然需要被处理。由于该过程可能导致多次标识节点，所以BS优选地维护没有副本的群组。

最后，步骤S14：针对被标记为“待处理”的其他节点30重复以上步骤，直到发现了所有相关节点，即，针对群组中的任何节点重新实现ND过程使得该群组不变。

如上文所述，一次在一个节点处实现发现过程，即，一次仅在一个节点处发生至少广播步骤。因此降低了冲突风险。

1.2高层变化

迭代通常由基站控制。在选择用于实现新的ND过程的另一候选节点之前，BS等待当前选择的节点完成（至少）广播步骤，如上文所述。当前选择的节点例如可以在完成最早的广播步骤时向BS报告，例如为了避免广播重叠。

现在，在（非优选的）实现中，可以选择ND过程的其他步骤进行重叠，例如，第n个发现节点（节点n）从节点n+2接收回复，同时已经指示节点n+1广播ND请求。此类变化可以加速ND过程。

优选地，在当前选择的节点20已经从邻居节点接收到回复之后，触发新的ND过程，以便进一步最小化共享传输介质的使用。由此，通常在从当前选择的节点接收到报告时开始新的ND，该报告证明从邻居节点接收到至少一个回复。由于应当看到具体的过程是优选的，其导致在完成ND过程（假设接收到所有回复）时，仅从当前节点发送一个报告。

如何到达节点优选地根据源路由机制实现。源路由本身是已知的。将该机制应用于本上下文允许BS向给定节点发送ND命令。基于先前检测到所述给定节点的节点的源路由信息，来逐步地建立针对给定节点的源路由信息。例如，如果节点A是由BS自身检测到的邻居，则从BS到节点A的源路由可以记录为“BS-A”；如果另外节点B是A的邻居，则从BS到B的源路由将是“BS-A-B”，以此类推。所产生的源路由不仅由BS用于发送请求，还由节点用于向BS报告（通过使用反向源路由）。利用源路由机制，BS和节点可以彼此直接交换消息，而不需要泛洪/广播机制。并且，因为BS指示节点逐个地实现ND过程，所以防止了冲突。因此，节点在向BS发送其回复时不需要使用CSMA。

与上述迭代过程一起使用，源路由机制允许间接地到达远程节点，以使得即使在直接广播长度（单跳）之外的节点也可以到达。由此，本发明应用于地理扩展网络，BS广播的消息可以被网络中的所有节点直接接收到，这并不重要。

接下来，除了ND过程之外，应当优选地执行链路探测（LP）过程。LP过程的目的在于评估在ND过程期间所标识的节点之间的链路质量。LP过程与ND过程类似：其是通常由BS控制的迭代过程。

LP过程可以与ND过程交织，如图4所示。然而，可以预期若干调度可能性，即，何时开始LP过程。例如，LP过程可以在完成针对至少所述当前节点的ND过程之后在当前节点20处实现。在优选变体中，一旦已经发现了所有节点即开始LP过程，如图5所示。该最后一个场景是更加确定的：完成ND过程所需要的时间（较短）易于确定，并且不会被交织的LP过程扰乱。

为了开始LP过程，BS指示（图4，步骤S12，或者图5，步骤S16）当前选择的节点20以实现LP过程。此类LP过程通常通过向与所选择的节点20相邻的节点30“发送”一个或多个LP消息而开始（步骤S21），以用于后续的链路质量的测量（步骤S31）。

可以考虑两种变体，即，“发送”可以指链路方法或者广播方法：

-链路方法：

在该方法中，所有相关链路是独立探测的。BS向（发现节点列表之外的）给定节点20发送用于探测从给定邻居n（即，节点30之中的一个节点）的链路的请求。在接收到该请求时，节点20要求节点n向其发送多个消息。节点20监听节点n发送的消息，对其可以接收到无错的消息进行计数，测量所接收的信号强度指示符（RSSI，即，所接收的无线电信号中存在的功率的度量）和/或其他指示符等，并且将结果报告回BS。在BS已经要求所有节点探测所有邻接的链路时，针对节点20的链路探测过程终止。

-广播方法：

在该方法中，在接收到由BS发送的链路探测请求时，所选择的节点20广播多个消息。可以接收广播的邻居节点30对其可以接收到的无错消息的数目进行计数，测量产生的RSSI等。

接下来，关于如何向BS传送结果存在至少两种选项，也就是

ο节点20独立地询问每个邻居30，并且向基站发送结果，或者

ο基站直接从相邻节点请求结果。

另一选项将参考图4在下文中讨论。

就像在ND过程中一样，在共享传输介质上广播LP消息，由于一次选择一个节点（节点20）从而仍然是有效的方法。例如，针对具有N个节点的网络，广播方法仅需要O(N)次测量，而链路方法需要O(N²)次测量。因此，广播方法的运行时间显著地较短。还需要注意，在链路方法和广播方法二者中，节点不会同时传输，因此不需要类似于CSMA的方法。

现在，为了效率，优选地单播在实现ND和/或LP过程时由邻居节点发送的回复（步骤S34）。回复消息的成功接收可以被确认，例如，使用802.15.4MAC层的链路确认机制。

由于多个节点可能同时回复，所以此时回复节点可以使用类似于CSMA的协议来处理可能的冲突，从而在共享介质1上没有其他业务的情况下发送回复，如本身已知的。这将参考图7进一步讨论。

而且，优选地仅在有限的时间（提前触发了定时器TB）期间将在当前选择的节点20处接收的回复纳入考虑，使得该过程更加确定。通常，广播ND请求的步骤重复多次，ND请求包括与邻居节点是否应当回复有关的信息。仅以下节点才会使用与针对第一回合相同的过程来回复新的请求：

-例如由于时间限制而没有在之前的回合中发送其回复；或者

-不知道之前的回合。

通过使用语针对第一回合相同的过程对新的请求回答。这将减少回复节点的数目，并且由此增加其成功回复的机会。整个过程仍然是确定的。

根据节点密度，节点可能需要不同的发现回合来发现其所有邻居。作为实现选项，发现过程可以在固定数目的回合之后终止，或者在上一回合期间应答节点的数目小于特定值时终止。

2.具体实施方式

图4和图5的实施方式本质上的区别在于ND过程和LP过程的排序。在图4中：两个过程是交织的，而在图5中，在触发LP过程之前完成ND过程。首先详细讨论图5的实施方式。

2.1连续的ND和LP过程

在下文中，参考图5-图10描述用于支持网络发现的方法和系统的具体实施方式。此处，一旦发现了所有节点即在当前节点20处实现LP过程（步骤S15-S17），如图5所示。该场景比图4的场景更加“确定”，因为完成ND过程所需的时间（较短）易于确定，并且不会被（较长的）LP过程扰乱。更具体地，LP过程基本上具有确定的持续时间，而ND没有（即，在开始，不知道存在多少节点）。优点在于通常可以重复（S24）短的ND核心步骤S22-S23，直到找到所有的已知节点（假如有必要），而不会造成本质上的持续时间的后果。相反，较长的LP过程仅执行一次。

通常，BS10在尚未处理的节点之中选择当前节点20（步骤S11），并且指示所选择的节点20首先开始ND过程，步骤S12。简言之，BS例如使用源路由向节点20发送命令ND-CMD。节点20通过将ND请求广播到介质1上而作出反应。在接收到ND请求时（步骤S31），邻居节点30处理该请求（步骤S33），并且回复适当的响应ND_RESP（步骤S34），从而向节点20标识其自身。在节点20处在步骤S23中接收该响应，节点20因此使用反向源路由向BS报告（步骤S25）。

上述步骤可以进一步分解为若干子步骤，现在参考图6（描述当前选择的节点20处执行的步骤）和图7（与邻居节点相关）进行描述。

参考图6，可以实现以下方案：

-步骤S220：节点20正在监听（其不知道其已经被BS选择）；

-步骤S221：其从BS接收ND命令（ND_CMD）；

-步骤S222：节点20将计数器BC初始化为零，并且初始化回复节点的集合N；

-步骤S223：节点20广播ND请求，以及

-步骤S224：开始定时器TB；

-步骤S225：节点20返回监听模式，等待可能的响应；

可以实现的是，以上步骤221-225仅对应于图5的步骤S22。更一般地，可以考虑更一般地包括接收ND命令和广播ND请求的任何适当方案。

类似地，图5的步骤S23可以分解（参见图6）为：

-步骤S231：当在节点20处从邻居节点30之中的特定节点n接收到响应ND_RESP时，

-步骤S232：节点20根据回复者n来更新集合N（将节点n的适当的标识符添加到N中）；

-步骤S233：节点20返回监听模式，等待进一步的响应；

-步骤S234：另一方面，如果先前设置的定时器TB已经超时，则；

-步骤S235：节点20增加BC；以及

-步骤S236：检查是否已经达到最大计数器值。如果没有，应当重新广播ND_REQ（步骤S223）。节点20因此重新发送ND_REQ若干次，如图5所示（步骤S24）。由此，仅在有限时间期间将在实现针对所选择的节点20的ND过程时接收的回复纳入考虑，继而，节点20准备并且向BS发送报告（ND_REPORT）（步骤S25）。节点20最后返回到监听模式。

同时，可以在邻居节点30处实现以下方案。考虑邻居节点30之中的特定节点（例如节点n）：

-步骤S330：节点正在监听；

-步骤S33（也见图5中）分解为：

ο步骤S331：从节点20接收ND_REQ。如所述的，ND请求包括与邻居节点是否应当回复有关的信息。通常，所述信息包括已经回复的节点的标识符（ID）；

ο步骤S332：节点n因此检查ND请求是否包含其自己的ID。如果是，则节点30返回到监听模式（步骤S340）。如果不是，则节点n将通过发送ND响应而进行回复（步骤S34），也参见图5。如先前所述的，该响应通常使用类似于CSMA的协议进行单播，即，该响应在没有其他业务的情况下发送。

-步骤S34：因此，响应过程可以分解为：

ο步骤S341：启动定时器；

ο步骤S342：节点n检查介质（例如，无线电信道）是否空闲；

ο步骤S343：如果不是，则节点n开始随机退避（backoff）；

ο步骤S344：节点等待随机退避超时；

ο步骤S345：当退避超时时，节点n返回到步骤S342以检查介质是否空闲；

ο步骤S346：另一方面，如果在步骤S341处设置的定时器超时，

ο步骤S347：则，节点n停止退避，并且返回到监听模式（步骤S340）；

ο步骤S348：现在，如果在步骤S342处检查到介质空闲，则节点n可以转到向请求节点20单播响应，

ο步骤S349：由此停止在步骤S341处设置的定时器，并且节点n返回到监听模式（步骤S340）。

基于从节点20接收的报告ND_REPORT，BS现在可以确定节点30仍然待处理（步骤S13）。从而，重新迭代ND过程（步骤S14），直到已经发现了所有节点。

接下来，在完成ND过程时，BS10知道已经应答的节点的集合，并且可以开始LP过程。BS甚至具有节点的列表，该节点的列表包括针对每个节点的其邻居的列表以及可以用于向所述每个节点发送消息的源路由。基于该信息，BS请求列表上的每个不同节点来执行链路探测过程，下文将详细描述。当列表中的所有节点都已经执行了链路探测过程，并且向基站传送了结果时，链路探测过程终止。基于所收集的统计，链路质量在BS处累积。

为了实现LP过程，BS应当首先选择（图5，步骤S15）节点（再一次由参考标号20表示），并且指示所选择的节点20来局部地开始LP过程。也就是，BS向节点20发送命令LP_CMD（步骤S16）。

广泛地，所选择的节点20通过广播一个或多个链路探测消息LP_MSG而作出反应（图5，步骤S21）。更加详细地，如图8所示，节点20执行以下步骤：

-步骤S220：节点20监听网络；

-步骤S221：其接收从基站发送的LP命令；

-步骤S222：转而，其广播M次链路探测消息LP_MSG；

-步骤S223：其因此向BS确认（发送LP_ACK，也在步骤S21中示出），并且返回到监听模式。BS可以与其他节点20继续发送（步骤S17）（并且重新迭代步骤S15、S16等）。

相应地，（邻居节点30之中的）邻居节点n可以根据图9继续，也就是：

-步骤S310：节点n正在监听；

-步骤S311：从节点20接收到LP消息LP_MSG；

-步骤S312：节点n检查相应链路探测消息训练的ID（LP_ID），即，用以检查是否已经针对刚接收的消息LP_MSG所属于的消息训练运行链路质量测量。另外，LP_MSG包括发送节点的ID；

-步骤S313：如果链路探测消息训练的ID是新的，则节点n删除当前LQM过程运行，以及

-步骤S314：开始新的LQM过程；

-步骤S315：如果LP消息训练的ID不是新的（意味着LQM过程已经针对该LP消息训练运行），则节点n指示更新当前的LQM过程运行。

LMQ过程的结果可以由任何节点请求。优选地，BS将收集LQM结果，如图5所示。因此命令从BS发送（步骤S18），在节点n处接收（步骤S35），结果（LQM_RSP）继而被发送回请求方（步骤S36），以用于那里的后续处理（步骤S19）。从节点n接收的角度来看，另外在图10中简要概括如何管理。首先，节点n正在监听（步骤S350）。继而，接收到（由任何节点20或者BS发送的）LMQ_REQ（步骤S35）。继而，相关LMQ过程的结果可以被封装到相应的响应LMQ_RSP中，并且向请求方发送（步骤S36）。

最后，一旦知道了所有的LQM结果，适当的通信就可以开始，例如使用TDMA（未示出）。

2.2交织的ND和LP过程

在下文中，将参考图4更加具体地描述支持网络发现的实施方式。如先前提到的，LP过程和ND过程现在是交织的。应当看出，LP和ND过程的交织步骤允许节省一些步骤，并且可能在某些情况下更加有效。

更加精确地，并且如图4所示，LP过程与ND交织，以使得响应于ND请求而在（当前选择的）节点20处接收的回复包括与当前节点20和回复节点n之间的链路质量的测量相关的数据（步骤S23）。换言之，在那种情况下，在ND之前发起LP，以使得当ND请求到达时，与链路质量测量（LQM）相关的数据可用。因此可以响应于ND请求而添加此类结果，以使得ND响应和LQM结果可以被收集在一起。

更加具体地，在那种情况下，BS10通常将指示所选择的节点20开始LP过程和ND过程二者，参见图4。也就是，BS例如使用源路由向节点20发送专用命令，称为LP/ND_CMD。在变体中，BS首先发送LP_CMD，并且随后，在得到节点20的确认时，发送ND-CMD。

接下来，所选择的节点20通过发送一个或多个链路探测消息LP_MSG（例如通过广播所述消息）而作出反应。如果需要的话，所选择的节点20可以进一步确认LP_CMD的接收。

在接收时（步骤S31），邻居30之中的给定邻居节点n进行到LQM，并且存储结果以用于随后使用。广播节点20或者BS随后选择的其他节点，其他邻居节点实际上应当基本上以相同的方式来进行。

随后（例如，在定时器超时或者接收到来自BS的指示之后），当节点20广播ND请求（ND_REQ）时，相同的邻居节点n可以处理该ND请求（步骤S33），并且通过发送相应的响应（ND_RESP），邻接LQM的结果而进行回复（步骤S34）。因此，邻居节点30的联合响应将可能包括对ND请求的响应和对相关链路的LQM结果二者，从而节省了一个重传步骤。

在当前节点20处接收联合响应（步骤S23）。通常重复广播ND请求的步骤（步骤S24），以保证所有邻居的安全接收。

接下来，当前节点20可以向BS10报告（步骤S25）哪些节点已经回复从而被标识，以用于BS处的后续处理。另外，LQM结果被递送至BS。

BS因此确定哪些新节点仍然需要“待处理”，即，针对其实现LP/ND过程的这些节点可能导致其他节点到目前为止尚未标识。

BS因此对所有节点进行迭代，直到所有节点被处理（步骤S14）。最后，一旦标识了所有节点，并且LQM结果已知，即可以在节点之间实现适当的通信，例如使用诸如时分多址（TDMA，未示出）的时分复用方案。只要节点彼此不知道，就不涉及时分复用。

接下来，作为可能的变体，可以考虑合并ND和LP广播步骤（步骤S21和S22）。也就是，链路探测消息可以充当邻居发现请求，并且步骤S21和S22可以是一个相同的步骤。然而，这将可能扩展整个过程的持续时间，以为LP过程通常广播非常大量的消息，而ND过程仅需要发送一个消息，该一个消息被重新广播若干次，例如，1-3次。

3.节点描述

优选地，考虑传感器节点。传感器节点（或者微粒）配置用于采集感知信息，执行某些（有限）处理并且与网络中其他的连接节点通信。如先前提到的，BS通常配置用于执行较复杂的任务。其可以视为超级节点，具有更多的计算和存储能力。在所有情况下，节点和BS每个可以视为计算机化单元，诸如图3所示。

如所知的，传感器节点的主要组件通常是：

-微处理器，包括：

ο处理器核，

ο存储器，

ο程序，以及

ο可编程输入/输出外围设备，诸如定时器、事件计数器等。

微处理器处理数据（执行简单任务），并且控制节点中的其他组件，一般是：

-收发机（或者更加广泛的，网络接口），用于与网络交互，

-外部存储器或者内存，

-电源；以及

-通过输入控制器对接的一个或多个传感器。

节点和BS涉及为实现以上描述的本发明的方面。在这一方面，将可以理解，在此描述的方法大部分是非交互式的和自动的。在示例性实施方式中，在此描述的方法可以实现为交互式、部分交互式或者非交互式系统。在此描述的方法可以在软件（例如，固件）、硬件或者其组合中实现。在示例性实施方式中，在此描述的方法在软件（例如，可执行程序）中实现，可执行程序由专用计算机（节点和BS）执行。更广泛地，本发明的实施方式可以使用通用数字计算机实现，诸如个人计算机、工作站等。

图3中绘出的系统100示意性地表示了计算机化单元101，例如，通用计算机，其可以充当传感器节点或者BS的功能。在示例性实施方式中，在硬件架构方面，如图3所示，单元101包括处理器105、耦接至存储器控制器115的存储器110以及一个或多个输入和/或输出（I/O）设备140、145、150、155（或者外围设备），这些I/O设备经由本地输入/输出控制器135通信地耦接。输入/输出控制器135可以是但不限于，一个或多个总线，或者其他有线或者无线连接，如本领域所知。输入/输出控制器135可以具有附加元件（为了简化而省略），诸如控制器、缓冲器（高速缓存）、驱动器、中继器和接收机，以用于支持通信。另外，本地接口可以包括地址、控制和/或数据连接，以用于支持前述组件之间的适当的通信。

处理器105是用于执行（特别是存储在存储器110中的）软件的硬件设备。处理器105可以是任何定制或者可商购的处理器、中央处理单元（CPU）、与计算机相关联的若干处理器之中的辅助处理器、基于半导体的微处理器（以微芯片或者芯片组的形式），或者广泛地，用于执行软件指令的任何设备。

存储器110可以包括易失性存储器元件（例如，随机存取存储器）和非易失性存储器元件中的任何一个或者组合。另外，存储器110可以并入电子、磁、光和/或其他类型的存储介质。注意，存储器110可以具有分布式架构，其中，各种组件彼此位置远离，但是可以由处理器105访问。

存储器110中的软件可以包括一个或多个独立的程序，其中每个程序包括用于实现逻辑功能的可执行指令的有序列表。在图3的示例中，存储器110中的软件包括根据示例性实施方式在此描述的方法以及适当的操作系统（OS）111。OS111基本上控制其他计算机程序（诸如在此描述的方法，例如参见图4-图10）的执行，并且提供调度、输入-输出控制、文件和数据管理、存储器管理和通信控制以及相关服务。

在此描述的方法可以按照源程序、可执行程序（目标代码）、脚本或者包括待执行的指令集的任何其他实体的形式。当按照源程序形式时，程序需要经由编译器、汇编器、解释器等进行翻译，这些可能包括或者不包括在存储器110内，以便于OS111适当结合地操作。另外，方法可以编写为面向对象的编程语言（其具有数据和方法的类）或者过程编程语言（其具有例程、子例程和/或函数）。

可能地，传统的键盘150和鼠标155可以耦接至输入/输出控制器135（特别是对于BS，如果需要的话）。其他I/O设备140-155可以包括传感器（尤其是在节点的情况下），即，对类似于温度或者压力的物理条件（待监测的物理数据）下的改变产生可测量响应的硬件设备。通常，传感器产生的模拟信号通过模数转换器进行数字化，并且被发送至控制器135以用于进一步处理。传感器节点理想上是较小的，消耗较低能量，自治的并且无人操作的。由于无线传感器节点通常是小的电子设备，所以其优选地配备有有限电源，例如，小于0.5-2安培-小时和1.2-3.7伏特。

另外，I/O设备140-155还可以包括传输输入和输出二者的设备。系统100还可以包括耦接至显示器130的显示器控制器125。在示例性实施方式中，系统100还可以包括用于耦接至网络165的网络接口或者收发机160。

网络165在单元101和外部系统（节点/BS）之间发送和接收数据。如所述的，网络165优选地以无线方式实现，例如，使用无线协议和技术。本实施方式优选地集中于低功率网络，例如，IEEE802.15.4。然而，可以考虑使用其他协议和技术的其他实施方式。存在很多这样的技术（例如，固定无线网络、无线局域网（LAN）、无线广域网（WAN）等），这些本身是已知的，在此不需要进一步描述。网络165还可以是分组交换网络，诸如局域网、广域网、因特网或者其他类型的网络环境。

如果单元101是PC、工作站、智能设备等，则存储器110中的软件还可以包括基本输入输出系统（BIOS）（为了简化而省略）。BIOS存储在ROM中，以使得可以在计算机101启动时执行BIOS。

当单元101在操作中时，处理器105配置用于执行存储在存储器110内的软件，以便往来于存储器110传送数据，并且根据软件广泛地控制计算机101的操作。在此描述的方法和OS111整体或者部分由处理器105读取，通常在处理器105内缓冲，并且继而被执行。

当在此描述的系统和方法以软件实现时，方法可以存储在任何计算机可读介质上，诸如存储120，以用于由任何计算机相关系统或者方法使用或者与其结合使用。

本领域技术人员可以理解，本发明的方面可以实现为系统、方法或者计算机程序产品。因此，本发明的方面可以采用完全硬件实施方式、完全软件实施方式（包括固件、驻留软件、微代码等）或者组合软件和硬件方面的实施方式的形式。另外，本发明的方面可以采用在一个或多个计算机可读介质中实现的计算机程序产品的形式，所述计算机可读介质具有实现在其上的计算机可读程序代码。

可以使用一个或多个计算机可读介质的任意组合。计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质。计算机可读存储介质可以例如是但不限于电子、磁、光、电磁、红外或者半导体系统、装置或设备，或者前述的任何适当组合。计算机可读存储介质的更具体实例（非穷举列表）将包括以下：具有一个或多个线路的电连接，硬盘，随机存取存储器（RAM）、只读存储器（ROM）、可擦除可编程只读存储器（EPROM或闪存）、光纤、便携式光盘只读存储器（CD-ROM），光存储设备，磁存储设备，或者前述的任何适当组合。在本文档的上下文中，计算机只读存储介质可以是任何有形介质，其可以包含或者存储程序，程序由指令执行系统、装置或者设备使用或者与其结合使用。

计算机可读信号介质可以包括具有实现在其中的计算机可读程序代码的传播数据信号，例如，基带信号或者作为载波的一部分。此类传播信号可以采用多种形式，包括但不限于电磁、光或者其任何适当组合。计算机可读信号介质可以是并非计算机可读存储介质的并且可以通信、传播或者传送程序的任何计算机可读介质，所述程序由指令执行系统、装置或者设备使用或者与其结合使用。

实现在计算机可读介质上的程序代码可以使用任何适当的介质进行传输，包括但不限于无线、有线、光纤电缆、RF等或者前述的任何适当组合。

用于实现本发明的方面的操作的计算机程序代码可以用一种或多种编程语言的任何组合来编写，编程语言包括面向对象的编程语言（诸如Java、Smalltalk、C++等）以及传统的过程编程语言（诸如“C”编程语言或者类似的编程语言）。程序代码可以完全在单元101（节点或者BS）上执行，部分在其上执行，部分在单元101和另一单元101上执行，与其类似或不类似的。其可以部分在用户的计算机上执行，并且部分在远程计算机上执行，或者全部在远程计算机或者服务器上执行。

以上参考根据本发明的实施方式的方法、装置（系统）和计算机程序产品的流程图示图和/或框图来描述了本发明的方面。可以理解，流程图示图和/或框图的每个框可以由计算机程序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机或者其他可编程数据处理装置的处理器，以用于产生机器，以使得经由计算机或者其他可编程数据处理装置的处理器执行的指令创建用于实现流程图和/或框图中的一个或多个框中指定的功能/动作的装置。

计算机程序指令还可以加载到计算机、其他可编程数据处理装置或者其他设备上，以产生要在计算机、其他可编程装置或者其他设备上执行的一系列操作步骤，从而产生计算机实现的过程，以使得在计算机或者其他可编程装置上执行的指令提供用于实现流程图和/或框图中的一个或多个框中指定的功能/动作的过程。

附图中的流程图和框图示出了根据本发明的各种实施方式的系统、方法和计算机程序产品的可能实现的架构、功能和操作。在这一方面，流程图或者框图中的每个框可以表示模块、分段或者代码的部分，其包括用于实现所指定的逻辑功能的一个或多个可执行指令。应当注意，在一些备选实现中，框中提到的功能可以不按照附图中提及的顺序发生。例如，连续示出的两个框可能实际上基本同时执行，或者有时框可以按照相反顺序执行，这取决于所涉及的功能和算法优化。还应当注意，框图和/或流程图示图的每个框以及框图和/或流程图示图中的框的组合，可以由执行所指定的功能或动作的专用的基于硬件的系统或者专用硬件和计算机指令的组合来实现。

虽然已经参考特定实施方式描述了本发明，但是本领域技术人员可以理解，在不脱离本发明的范围的情况下，可以做出各种改变，并且等效物可以替换。另外，在不脱离其范围的情况下，可以做出很多修改，以使得特定情境适应本发明的教导。因此，本发明并不旨在限制于所公开的特定实施方式，本发明将包括落在所附权利要求范围内的所有实施方式。例如，在实施方式中，对CSMA协议的很多修改可以用于对请求节点的单播响应，例如，具有冲突检测的载波侦听多路访问（CSMA/CD）或者具有冲突避免的载波侦听多路访问（CSMA/CA）等。在某些地方，在适当的情况下，取决于应用，单播过程可以替换广播过程，反之亦然。一些通常的BS任务可以被委派给节点，例如，向待处理的节点群组添加（步骤S13）中继邻居节点，等等。

Claims

1.一种用于发现网络（165）中的节点集合（20，30）的方法，包括：

-在待处理节点的群组中的节点之中选择（S11）节点（20）；以及

-指示（S12）实施针对所选择的节点的发现过程，

所述过程包括：

-在所述网络的共享传输介质（1）上从当前选择的节点（20）广播（S22）邻居发现请求；以及

-在当前选择的所述节点（20）处接收（S23）由邻居节点在所述共享传输介质上发送（S34）的回复，并且将所述邻居节点添加（S13）到待处理节点的所述群组；以及

-针对待处理节点的所述群组中的其他节点（30）重复（S14）选择和指示的所述步骤，直到发现所述集合的所有节点。

2.根据权利要求1所述的方法，其中，在针对当前选择的节点的发现过程期间，在接收（S23）至少一个回复之后，并且优选地，在接收若干个回复之后，触发针对其他节点来重复选择和指示的所述步骤。

3.根据权利要求1或2所述的方法，其中，指示包括：指示经由源路由机制来实施针对选择的所述节点的所述发现过程。

4.根据权利要求3所述的方法，其中，最初从诸如基站的源节点（10）实施所述源路由机制。

5.根据权利要求1至4中任一项所述的方法，还包括：

-指示（S12，S16）实施针对所选择的节点的链路探测过程，所述链路探测过程包括：

-从当前选择的节点（20）向邻居节点（30）发送（S21）一个或多个链路探测消息，以用于链路质量的后续测量（S31），其中，发送优选地包括在所述共享传输介质上广播（S21）所述一个或多个链路探测消息。

6.根据权利要求5所述的方法，其中，在完成针对至少选择的所述节点的所述发现过程（S11-S14）之后，并且优选地，在已经发现所述节点集合的所有节点之后，针对选择的所述节点（20）实施所述链路探测过程（S15-S17）。

7.根据权利要求5所述的方法，其中，所述链路探测过程的实施与所述发现过程交织，以使得在实施针对所选择的节点的所述发现过程时接收（S23）的回复中的至少一个包括与当前选择的所述节点（20）和邻居节点（30）之间的链路质量的测量相关的数据。

8.根据权利要求7所述的方法，其中，在广播所述邻居发现请求之前执行发送所述一个或多个链路探测消息。

9.根据权利要求1至8中任一项所述的方法，其中，在实施针对所选择的节点的发现过程时接收的回复由邻居节点单播（S34）。

10.根据权利要求9所述的方法，其中，在实施针对所选择的节点的发现过程时接收的回复由邻居节点使用类似于CSMA的协议单播，从而所述回复中的每一个在所述共享介质上没有其他业务的情况下被发送。

11.根据权利要求1至10中任一项所述的方法，其中，在实施针对所选择的节点的发现过程时接收的回复仅在有限时间期间在选择的所述节点处被考虑。

12.根据权利要求1至11中任一项所述的方法，其中，重复广播邻居发现请求的所述步骤，其中优选地，所述邻居发现请求包括与邻居节点是否应当回复有关的信息。

13.一种使用包括节点集合的网络（165）的方法，包括：

-根据前述权利要求中任一项所述的方法来发现（S11-S26）所述节点集合中的节点；以及

-使所发现的节点使用时分复用进行通信。

14.一种驻留在计算机可读介质上的计算机程序，包括用于使得计算机化网络（165）的节点（20，30）实现根据权利要求1至13中任一项所述的方法的步骤中的每个步骤的指令。

15.一种计算机化网络（165），包括节点（20，30），所述节点优选地是传感器节点，每个节点具有与存储器可操作地互连的至少一个处理器，从而所述计算机化网络被配置用于实现根据权利要求1至13中任一项所述的方法的步骤中的每个步骤。