对等网络环境中同步站的选择

摘要

本发明公开了用于在对等通信环境中选择一个或多个同步站或主设备的系统、装置和方法。同步站广播周期性同步帧以通告未来的可用性窗口，设备在所述可用性窗口期间会合以进行发现和通信。可以作为同步站的设备对优先值进行通告，该优先值指示它们对于该角色的优先级或适用性。所有设备执行相同算法来对优先值进行排序并辨识根同步站和任意数量的分支同步站；叶子设备与根同步站或分支同步站同步。该被动同步方案允许各个设备节省电力，因为它们不需要主动地发现其他设备和服务，并且可以在多个时间周期关闭其无线电部件而不牺牲可发现性。本文所提供的同步和对等通信与其它设备的要求共存，例如操作和基于基础结构的通信。

权利要求

1.用于从对等通信环境内的多个对等设备中选择一个或多个同步站的装置，所述装置包括：处理器；

无线通信模块；

存储优先值的存储器部件，其中所述优先值反映所述装置作为同步站的优先级；

第一逻辑，所述第一逻辑能够被所述处理器执行以从所述多个对等设备与所述装置的排序列表中辨识所述一个或多个同步站；和第二逻辑，所述第二逻辑能够被所述处理器执行以在所述装置被辨识为同步站的情况下广播同步帧。

2.根据权利要求1所述的装置，其中由所述装置的一组量度来计算所述装置的所述优先值。

3.根据权利要求1所述的装置，其中通过根据所述多个对等设备和所述装置的优先值对所述多个对等设备和所述装置进行排序来汇编所述排序列表。

4.根据权利要求1所述的装置，其中辨识一个或多个同步站包括：辨识负责为所述多个对等设备设置会合调度的根同步站；以及辨识负责在整个所述通信环境中传播所述会合调度的一个或多个分支同步站。

5.根据权利要求1所述的装置，其中所述第一逻辑还能够执行以：辨识所述装置的第一范围内的第一同步站；以及辨识所述装置的第二范围内的第二同步站。

6.根据权利要求1所述的装置，其中由所述装置传输的同步帧辨识所述优先值。

7.根据权利要求1所述的装置，其中由所述装置传输的同步帧辨识可用性窗口，所述多个对等设备在所述可用性窗口期间在指定的时间在指定的通信信道上会合。

8.一种通信设备，包括：

处理器；

第一逻辑，所述第一逻辑能够被所述处理器执行以辨识所述通信设备在对等设备的网络内的角色，其中所述通信设备的角色为下列之一：根同步站；

分支同步站；和

叶子设备；

第二逻辑，所述第二逻辑能够被所述处理器执行以在所述通信设备的角色为所述根同步站或分支同步站的情况下生成同步帧来同步所述对等设备的子组，其中每个同步帧包括：时间戳；和

数据，所述数据被配置为辨识所述对等设备的所述子组中的会合；以及无线电部件，所述无线电部件用于广播所述同步帧。

9.根据权利要求8所述的通信设备，还包括：存储器模块，所述存储器模块存储包括所述通信设备在内的多个相应对等设备的优先值，其中每个优先值辨识相应对等设备作为同步站的优先级。

10.根据权利要求9所述的通信设备，其中由对相应对等设备可使用的电力的测量来计算优先值。

11.根据权利要求9所述的通信设备，其中由下列中的至少一者来计算优先值：所述相应对等设备的功率消耗的速率；

所述相应对等设备能够使用的频带；

所述相应对等设备的处理器的负载；

所述相应对等设备的通信范围；和

所述相应对等设备的类型。

12.一种通信设备的网络，包括：

根同步站，所述根同步站具有高于所述根同步站的范围内的其他通信设备的优先值，其中所述根同步站传输指示所述根同步站优先值的周期性同步帧；

对于N个层级(N≥1)中的每一个的一个或多个分支同步站，所述一个或多个分支同步站具有的优先值低于所述根同步站的优先值；和选择代码，所述选择代码由所述通信设备的网络中的每个通信设备执行且被配置为将所述设备的一个或多个选择量度转换为所述设备的优先值。

13.根据权利要求12所述的网络，其中给定设备的所述一个或多个选择量度包括对所述给定设备可使用的电力的测量。

14.根据权利要求13所述的网络，其中所述给定设备的所述一个或多个选择量度还包括下列中的至少一者：所述给定设备的功率消耗的速率；

所述给定设备能够使用的频带；

所述给定设备的处理器的负载；

所述给定设备的通信范围；和

所述给定设备的类型。

15.一种辨识多个通信设备的分级结构内第一设备的角色的方法，所述方法包括在所述第一设备处：收集所述多个通信设备的优先值，其中设备的所述优先值指示所述设备作为同步站的优先级；

将所述多个通信设备中具有最高优先值的设备辨识为所述分级结构的根同步站；

将优先值低于所述最高优先值的一组设备辨识为分支同步站；以及如果所述第一设备被辨识为所述根同步站或分支同步站，则广播同步帧以有利于所述多个通信设备的同步。

16.根据权利要求15所述的方法，还包括：如果所述第一设备没有被辨识为根同步站，并且也没有被辨识为分支同步站，则承担叶子设备的角色并且避免广播同步帧。

17.根据权利要求16所述的方法，还包括：在所述根同步站和所述分支同步站中识别所述第一设备能够以超过阈值的信号强度来监听的一个或多个同步站；以及与在所述一个或多个同步站中具有最高优先值的所识别的同步站同步。

18.根据权利要求15所述的方法，还包括，如果所述第一设备被辨识为分支同步站，则：在所述根同步站和不是所述第一设备的所述分支同步站中，识别所述第一设备能够从其监听到同步帧的同步站；以及与具有最高优先值的所识别的同步站同步。

19.根据权利要求15所述的方法，其中收集优先值包括：操作所述设备的无线电部件以从所述多个通信设备接收通信；

从所述通信中提取所述优先值；以及

更新数据库以记录与相应设备关联的每个优先值。

20.根据权利要求15所述的方法，其中辨识根同步站包括：比较所收集的优先值，而与距对应于所收集的优先值的设备中的第一设备的范围无关。

21.根据权利要求15所述的方法，其中辨识为分支同步站包括：确定阈值信号强度；

将从所述多个通信设备接收的通信的信号强度与所述阈值信号强度进行比较；以及过滤掉从其接收的通信的信号强度小于所述阈值信号强度的任何设备。

22.根据权利要求21所述的方法，其中辨识为分支同步站还包括：确定分支同步站的最大数量；

根据它们的相应优先值，对不是被过滤掉的任何设备的所述一组设备进行排序；以及从所排序的一组设备中，选择优先值高于所排序的组中的其他设备但不超过所述最大数量的一个或多个设备。

23.一种存储指令的非暂态计算机可读介质，所述指令在被通信设备的硬件处理器执行时使所述通信设备执行一种辨识第一设备在多个通信设备的分级结构内的角色的方法，所述方法包括在所述第一设备处：收集所述多个通信设备的优先值，其中设备的所述优先值指示所述设备作为同步站的优先级；

将所述多个通信设备中具有最高优先值的设备辨识为所述分级结构的根同步站；

将优先值低于所述最高优先值的一组设备辨识为分支同步站；以及如果所述第一设备被辨识为所述根同步站或分支同步站，则广播同步帧以有利于所述多个通信设备的同步。

说明书

对等网络环境中同步站的选择

背景技术

[0001] 本发明涉及通信领域。更具体地，本发明提供了一种系统、装置和方法来在同步的对等联网环境内选择一个或多个主设备。

[0002] 对等网络协议或技术允许各个节点或设备直接与其它对等实体通信，并且可以与基于基础结构的环境形成对比，在基于基础结构的环境中，必要的中央节点(例如服务器、路由器、开关、接入点)在不同节点之间传递通信。直接对等通信的一个优点是其避免了通过其他设备的通信的不必要的额外路由和处理。

[0003] 但是，现有对等网络技术具有减弱其可用性、可扩展性和/或性能的局限。例如，一些技术只提供受限的对等通信能力，因为它们着眼于基于基础结构的方案并且因此需要中央节点。这些环境中的对等通信需要与中央节点协商，并且可能在不共用一个共有中央节点的设备之间是不可能的。此外，对等实体之间的通信可能受到中央节点的能力(例如频带、带宽、调制)的限制。

[0004] 由于其突出的作用，中央节点可能变得拥塞，并且因此增大通信延迟并减少该环境内的通信吞吐量。而且，中央节点起到单点故障的作用。即使另一节点可以接手发生故障或丢失的中央节点的功能，但是在此之前，网络可能已经严重劣化。

[0005] 允许对等通信的一些其他技术要求各个节点需要显著的功率消耗，而这对于依赖于电池电力的设备(例如智能电话、平板电脑、膝上型电脑和笔记本计算机)而言是一个重要的关注点。对等实体的过量功率消耗可能是由于对服务和/或其他设备的低效率发现、由于不得不作为中央节点、由于对设备的收发器效率低下的使用、和/或由于其他原因而导致的。例如，要求设备连续地或定期地轮询或查询其他设备将使其消耗相当量的电力，尤其是对于行进通过不同空间区域的无线设备而言。

[0006] 另外，支持对等通信的一些联网技术或协议不与其它技术共存。例如，在无线环境中，典型的对等协议的灵活性不足以与其他协议或者在应用之间共享设备的无线电部件、天线或频谱(例如为了保持 连接)。一些对等技术还不允许多播通信，而是要求设备单个地接触多个对等实体，并且/或者当环境变得更加密集地占用时不能很好地扩展。

发明内容

[0007] 在本发明的一些实施例中，提供了一种系统、装置和方法，用于在多个试图进行对等通信的设备中选择一个或多个同步站。在这些实施例中，所选择的站广播会合调度，以对设备进行同步并在逻辑上将它们安排到分级结构(例如，树)中。

[0008] 单个根同步站或顶部主站充当该分级结构的根，设置会合调度，并且充当被同步设备的主时钟。任何数量(即零个或更多个)分支同步站将会合调度传播遍及整个环境，这延伸了该分级结构的范围。根同步站不充当通信的中央切换点，并且可以容易地被另一设备替代，而对设备通信的影响很小(如果有影响的话)。

[0009] 每个同步站在一个或多个社交信道上发出周期性同步帧。这些同步帧为一个或多个即将到来的设备会合辨识信道和时间。会合可以被称为“可用性窗口”。

[0010] 同步帧还可以传送其他信息，诸如将被设备用来将站选择作为同步站的数据、发出同步帧的根同步站和/或分支同步站的属性、时间戳等。所有设备应用相同的算法来辨识应该充当同步站的那些设备。在一些具体实施中，设备应用该算法来首先确定其是否应该是根同步站，然后确定其是否应该是分支同步站。如果没有被放置到同步站的角色中，则其将会是分级结构内的叶子设备。

附图说明

[0011] 图1示出了根据本发明的一些实施例使用周期性同步帧来在设备之间实现和保持同步。

[0012] 图2是根据本发明的一些实施例展示周期性同步帧中所辨识的可用性窗口序列的示意图。

[0013] 图3是根据本发明的一些实施例展示无线通信环境中设备与对等实体社区同步的流程图。

[0014] 图4是根据本发明的一些实施例展示带外交换的示意图。

[0015] 图5A至5D根据本发明的一些实施例示出了在一组对等通信设备内对同步站的选择。

[0016] 图6是根据本发明的一些实施例展示一种用于在对等通信环境中选择一个或多个同步站的方法的流程图。

[0017] 图7A至7E根据本发明的一些实施例示出了图6中所示的方法的执行。

[0018] 图8是根据本发明一些实施例的一种对等设备的框图。

[0019] 图9A至9B根据本发明的一些实施例示出了在对等环境中通信设备的分级集合内组的创建。

[0020] 图10A至10C示出了根据本发明一些实施例的多个组的合并。

具体实施方式

[0021] 给出以下描述是为了使本领域的技术人员能够实现和使用本发明，并且以下描述是在特定应用及其要求的上下文背景下被提供的。本领域技术人员将很容易想到所公开的实施例的各种修改形式，并且本文中所限定的一般性原则可应用于其他实施例和应用，而不脱离本发明的范围。因此，本发明并不旨在限于所示的实施例，而是要符合根据本文公开的原理和特征的最广泛范围。

[0022] 在本发明的一些实施例中，提供了一种系统、装置和方法，用于对在分级社区中工作于对等通信环境中的设备进行同步，同时允许在不离开该社区的情况下对设备进行局部分组。因此，默认的设备分级结构提供用于对环境中所有设备进行同步的构架，而各个组或组分级结构允许设备的局部协作，而不丧失在更大的分级结构中与设备进行交互的能力。

[0023] 简介

[0024] 无线通信环境可以通过任意数量的相同类型和/或不同类型的设备来表征，所述设备诸如智能电话、平板电脑、个人数字助理、膝上型电脑和桌上型计算机等。不同的设备将具有不同的特征，可以执行不同的应用程序，可能具有不同的功率级(例如电池强度)、不同的通信需要、不同的负载(例如在处理器上、在天线上)，可能以变化的信号强度被其他设备监听到，等等。此外，通信环境可能是易变的，设备不断地进入、移动通过以及离开构成该环境的空间区域。

[0025] 本文中所公开的一个发明的一些实施例提供了一种协议、机制和/或过程，用于使这样的环境中的设备能够相互发现并且直接对等地通信。这些实施例：有助于即使在使设备和服务能够很容易被发现的同时也实现低功率消耗；与其他通信技术(例如)共存；支持多频段操作(例如2.4GHz和5GHz)；避免网络基础结构(例如接入点)经常遭遇的吞吐量和延迟劣化，同时保持与基于基础结构的技术的兼容性；如果以及当充当同步站(或主设备)的设备离开该环境时，容易地且快速地恢复；并且是可扩展的，以适应具有许多设备的密集环境。在下文中将描述这些和其他特征和优点。

[0026] 在本发明的实施例中，设备被同步，从而它们在预定信道上在预定时间会合。设备会合的时间段被称为可用性窗口，并且所有同步站广播或通告可用性窗口的相同或相似调度。在可用性窗口期间，对等实体可以交换多播和/或单播数据通信，以及发现其他设备和服务。设备可以延伸其在可用性窗口处的出席，以适应与对等实体的持续通信。

[0027] 一个或多个即将到来的会合的参数(例如时间和信道)经由在一个或多个社交信道上广播的周期性同步帧(PSF)来进行通信。设备被预编程为周期性地在至少一个社交信道上进行监听长达足以监听到至少一个PSF的时间长度。

[0028] 因此，当设备启动或者进入到对等设备环境中时，该设备将调谐到预定的社交信道并且快速地获悉它在哪里以及何时可以与其他设备会合。如果该设备没有监听到PSF，则它将假设其应当充当主设备，并且开始发布其自身的PSF以促进与可能存在或者随后将出现的其他设备的同步。

[0029] 在一些具体实施中，同步参数(例如，即将到来的可用性窗口的调度)也可以在可用性窗口期间被通告，从而节省设备将其无线电部件切换到社交信道以接收这些参数的花费。设备甚至可以在不监听PSF、参与可用性窗口或者将其用于其他某种目的时关闭其无线电部件。参与被同步的分级结构的设备因此可以与该设备的另一功能(诸如基础结构连接或 链路)共享无线电部件、天线和/或其他通信资源。

[0030] 在对等设备社区内，应用选择过程来确定谁将成为同步站并且负责对其他设备进行同步。所选择的同步站的数量可以取决于存在的对等设备的数量、它们的信号强度、信号传播模式、工作参数等。如下面所描述的那样，选择或辨识同步站的过程实际上可以考虑参与的设备的任何相关因素。

[0031] 虽然通信环境中的设备在没有基础结构要求负担的情况下进行对等通信，但是为了同步的目的，对同步站或主设备的选择将在逻辑上将这些设备安排到分级结构中。在该分级结构内，根同步站(或“顶部主设备”)负责经由其广播的PSF所传送的同步参数对设备进行整体同步。每个下级主设备(被称为分支同步站)与该根同步站或与中间的分支同步站同步，并且在其自身的PSF内重新传输或重新封装该根同步站的同步参数，从而延伸所述整体同步的范围。

[0032] 单个无线设备(例如根同步站)的无线电范围是有限的，这通常会阻止该设备组织超过本地区域之外的设备。需要下级分支同步站来重新广播其同步参数允许这单个无线设备同步分散在更大区域上的设备集合。整个社区享受所得到的有益效果(例如准备好发现服务和其他设备、较低的功率消耗)。

[0033] 与具有基础结构要求(例如经由接入点的协调)的环境不同，由于同步站的主要任务仅仅是传播会合参数，所以失步站很容易被校正。例如，由丢失的同步站公布的会合调度将简单地在选择替代实体期间被保持，从而使所有设备保持同步。并且，那个替代实体一般将保持相同的调度。

[0034] 用于选择同步站或主设备的不同算法可以在不同时间和/或在不同环境中被应用，但是一般都用于促进这些目的中的任何目的或所有目的：主设备在整个环境中均匀的空间分布、环境内主设备的可调节的密度、以及对构成环境的地理区域的大小的控制。

[0035] 在本发明的一些实施例中，用于选择或辨识主设备的算法定期地执行，以基于设备的多种量度或属性，确保最适当的设备充当同步站。选择过程还可以考虑在区域中已经存在多少同步站、给定对等设备可以监听多少同步站、它们距离多远(例如基于信号强度或其他某种距离测量)等。

[0036] 与更大的默认分级结构分开地或者与更大的默认分级结构并行地，环境内的设备组可以在它们之间同步。例如，它们可以组织以共享文件或执行公共应用程序。组可以模仿默认分级结构，并且通过选择一个或多个分支同步站(或组主设备)来保持内部同步，其中其他设备(即叶子或从设备)与所选择的分支同步站同步。组根同步站(或“顶部组主设备”)可以与附近或周围的分级结构的成员同步(或者试图与其同步)。

[0037] 并非组中的所有成员都需要来自单个分级结构。例如，在与多个分级结构相邻的空间区域中，组可以从这些空间区域中两个或更多个中获得成员。

[0038] 在本发明的实施例中，“默认”分级结构是可以包括数量相对多的设备(例如给定空间区域内所有设备)的分级结构。默认分级结构的成员将具有(并且通告)匹配的“默认”辨识符。“组”分级结构由私有组的成员构成。组分级结构的成员将具有(并且通告)匹配的“组”辨识符。

[0039] 虽然组中的所有成员通常也将属于默认分级结构，但是默认分级结构的各个成员可以是或者可以不是任何组分级结构的成员。默认和组辨识符可与其它设备辨识符(例如IP地址、MAC地址、IMEI码、IMSI号)区分开。

[0040] 本文后面的章节根据本发明的一些实施例讨论对等环境内设备的同步以形成默认分级结构、分级结构内同步站或主设备的选择、默认分级结构内或跨多个默认分级结构的设备组的组织、以及示例性的对等设备。

[0041] 设备的同步

[0042] 如上所述,根据本发明一些实施例的无线通信环境内设备的同步允许这些设备容易地发现彼此、辨识可用服务以及进行直接对等通信(单播和/或多播)，而同时节省电力资源并且与其他通信过程共存。

[0043] 设备一上线或者一移动到运行兼容协议的至少一个其他设备的范围内，同步就开始，并且只要该设备在覆盖被同步设备的空间区域内在线(例如只要其在对等设备的范围内)，同步就可以被保持。

[0044] 通过同步和主设备选择过程，设备被自动地组织到分级结构中，其中该分级结构每个级别(或层级)处的同步站(或主设备)周期性地广播同步参数，以便实现和保持区域内设备之间的同步。周期性同步帧(PSF)是一种用于传播同步参数的机制，并且被所有被同步设备消费。

[0045] 周期性同步帧用于传送信息，诸如但不限于用于对设备的时钟进行同步的信息、被同步设备可以会合的一个或多个即将到来的可用性窗口的描述、以及传输PSF的根同步站和分支同步站的量度或属性。在本发明的其他实施例中，PSF可以包括不同的信息集合，但是一般将包括辨识至少一个可用性窗口的标准。

[0046] 分级结构的形成以及其中设备的同步可能受到配置或操作参数的影响，诸如但不限于：最大深度或层级、PSF的周期性、同步站的数量(例如总数量和/或给定设备范围内的数量)、用于选择同步站或主设备的选择算法、选择算法所考虑的设备量度或属性等等。在本发明的不同实施例中，可以应用不同的参数。

[0047] 图1示出了根据本发明一些实施例使用周期性同步帧来实现和保持设备之间的同步。

[0048] 在这些实施例中，周期性同步帧110(例如帧110a、110b、110n)定期地在一个或多个社交信道120(例如信道120a、120b、120n)上被传输。

[0049] 不同同步站可以在相同或不同的社交信道上传输周期性同步帧，并且任何给定同步站可以使用一个或多个社交信道来传送其PSF。单个环境中不同同步站可以使用不同社交信道，这或许是为了避免相互干扰，因为一个主设备所使用的社交信道可能被不同主设备用于不同目的(例如基础结构连接)，和/或出于其他某种原因。

[0050] 虽然在图1中示出了多个社交信道120，但是在一些具体实施中，一个环境和分级结构中的所有主站可以使用同一社交信道。本文中所讨论的社交信道和/或其他信道可以是IEEE802.11无线信道。

[0051] 在社交信道120a、120b、120n上，相应的周期性同步帧110a、110b、110n被负责的同步站周期性地广播。单个信道上由单个同步站所广播的PSF中的每一个(例如帧110a)可以是相同的或者可以略为不同，诸如在其传送的可用性窗口调度方面略为不同。

[0052] 虽然在图1中，每个信道的PSF周期(PA，PB，PN)是不同的，但是在本发明的一些实施例(其中多个社交信道被使用)中，两个或更多个信道的PSF周期可以是相同的。一个信道上PSF之间的示例性周期可以大约为100毫秒。不同同步站可以使用相同或不同的PSF周期。在一些具体实施中，PSF周期的长度或持续时间可以与广播PSF的同步站的总数量(或者特定区域中同步站的数量)成反比例。

[0053] 在本发明的一些实施例中，在每个社交信道上，PSF周期将各不相同；但是，发布PSF的同步站的可用性窗口周期可以是相同的。因此，在一个分级结构内，可以实现多个PSF周期和单个可用性窗口周期。

[0054] 在传输PSF时，进行发布的同步站或主设备仅仅需要将其无线电部件调谐到正确的信道并且将其通电长达足以发送该PSF。不需要在发布PSF后仍然保持在该信道上，而是可以关闭其无线电部件以节省电力、将其切换到另一社交信道(例如以准备在另一信道上传输PSF)或者将其用于其它某种目的(诸如出席可用性窗口(如下所述)、处理基础结构通信等)。

[0055] 在本发明的不同实施例中，PSF可以包含示例性PSF110x的元素的子组或超集，或者可以包含完全不同的信息元素集。PSF110x的同步参数(或可用性窗口参数)–信道130、时间132和持续时间134的组合–限定被同步设备在该期间可以会合的一个可用性窗口。信道130辨识它们将在其上会合的信道(例如802.11无线信道)，时间132辨识它们将会合的时间，而持续时间134指出窗口的最短持续时间。

[0056] PSF的同步参数或数据可以辨识任意数量的可用性窗口(零个或更多个)。在相同或不同社交信道上传输的以及由不同主设备传输的不同PSF可以辨识相同或不同的可用性窗口。但是，在一些实施例中，根同步站所设定的同步参数(包括可用性窗口的调度或序列)在整个分级结构中被应用。

[0057] PSF110x的同步参数的时间元素132可以辨识绝对起始事件(例如基于被同步时钟、UTC(协调世界时)或其他某种通用基准)和/或相对时间。在一些具体实施中，时间戳字段携带发布PSF110x的站的TSF(时间同步功能)。

[0058] 在本发明的一些实施例中，时间132包括进行同步的设备用于计算可用性窗口的起始时间的多个值。在这些实施例中，时间132可以包括被配置为指示在进行发布的同步站内PSF110x何时被形成和排队等待传输(例如PSF何时被放置到传输缓冲中)的“目标”时间戳、以及被配置为指示PSF实际上何时经由站的天线被调度的“实际”时间戳。从同步站计算“主偏置”参数时起，PSF就被认为形成了。

[0059] 主偏置值(作为时间132的一部分或者作为另一信息元素而也包括在PSF110x内)表示从进行发布的同步站释放PSF时测量，进行发布的同步站的相对于下一可用性窗口开始的内部偏置。换言之，主偏置测量发布同步帧的站所计算的从目标时间戳直到可用性窗口开始的时间周期。

[0060] 利用这些值，监听到发布PSF110x的站的或与发布PSF110x的站同步的设备可以如下地计算相对于可用性窗口起始时间的偏置：

[0061] 偏置＝主偏置–(实际时间戳–目标时间戳)

[0062] 进行同步的设备因此接收主偏置，并且可以根据目标和实际时间戳来测量已经经过了该主偏置时间周期的多少；其然后将经过的时间段从主偏置中减去，以确定在可用性窗口之前仍然剩余的时间量。

[0063] PSF110x的持续时间134指示在可用性窗口期间，发布PSF110x的同步站将监听以及可用于通信的最少时间量。持续时间也可以应用于被同步设备；也就是说，出席该窗口的设备可以被要求至少在该时间周期中可用，这是从该窗口开始时算起的。

[0064] 在本发明的一些实施例中，只要至少一个站在与主设备通信，该主设备就可以自动地延展其可用性窗口(例如递增地匹配持续时间134或其他某种时间段)。因此，即使多个站希望与该主设备通信，它们也可以能够这样做，而不需要等待另一个可用性窗口，这是因为窗口将被延展。

[0065] 类似地，出席该可用性窗口的设备可以延展其窗口，只要其对等实体中至少一者与其进行通信。因此，希望与另一对等实体通信的一个对等实体可以简单地在可用性窗口期间向该另一对等实体发布第一组分组、数据报、消息或其他通信单元。然后，这两个对等实体由于活动的通信而将自动地延展它们的窗口。有利地，这允许在可用性窗口延展期间大量的对等通信，而不会在可用性窗口期间占满或独占带宽。

[0066] 同步站在可用性窗口期间存在的最长持续时间可以在PSF110x中指定，和/或可以在可用性窗口期间被通告。示例性地，同步站可能需要离开该窗口以便在另一信道上发布PSF、将其无线电部件用于另一通信功能、或由于其他某种原因。至于各个设备，它们可以在持续时间134之后离开可用性窗口，如果它们没有什么要进行通信并且如果没有其他设备在该窗口内的某个时间段期间与其通信的话。

[0067] 返回图1，优先值(或者被称为主设备优先值或选择值)是用于辨识设备作为主设备或同步站的适用性或优先的值(例如整数)。优先值是利用相应设备的多种量度、属性或特性、并且可能还有设备分级结构或通信环境的特性来计算的。用于计算设备优先值的示例性量度包括可用电力资源(例如电池强度、AC连接)、处理器负载、信号强度等。

[0068] 如在下面的章节中所描述的那样，作为选择过程的一部分，对被同步设备的优先值进行比较以确定哪些设备应该是同步站。该过程可以定期地执行，诸如在每个可用性窗口序列期间或在每个可用性窗口序列之后、按固定的日程等等。

[0069] 在PSF110x中，分支同步优先值136是广播PSF110x的分支同步站的主设备优先值，并且指出该站在其默认分级结构内作为同步站的适用性或优先级。通过通告其优先值，该站范围内的所有设备可以正确地应用选择过程，并且例如确定它们是否更适于作为同步站。

[0070] 类似地，根同步优先值140是PSF110x在其中被广播的默认分级结构的根同步站的主设备优先值，并且指出该站作为同步站的适用性或优先级。如将在下文中看到的那样，通过在整个分级结构中传播根同步优先值140，通信环境边缘处的或重叠多个独立分级结构的区域中的设备可以确定加入哪个分级结构。此外，被同步分级结构中的所有设备可以确定它们是否更适于作为根同步站。

[0071] 分支同步量度138包括发布PSF110x的同步站的多个量度或属性，可能包括用于计算分支同步优先值136的量度。类似地，根同步量度142包括默认分级结构的根同步站的量度或属性。除了上面提到的数据之外，量度138和/或量度142可以包括站的名称和/或地址(例如MAC地址)、站的默认根同步站的名称或地址、时间戳、其在默认分级结构内的级别或层级(或距离根的跳转数量)、该站的PSF的周期性、该站所使用的社交信道等等。

[0072] 当PSF110x被默认分级结构的根同步站发布时，优先值136、140将匹配，并且量度138、142也将匹配。或者，可以忽略优先值字段中的一者和量度字段中的一者。

[0073] 此外，在组分级结构内工作的同步站所发布的PSF可以包含附加信息元素用于传递关于该组的优先值和/或量度。特别地，并且如在下面的章节中将讨论的那样，分开地为默认分级结构和组分级结构执行主设备选择过程，以为每一者选择或辨识要作为同步站的设备。量度和/或一个或多个附加优先值将涉及进行发布的站的组。

[0074] 在本发明的其中量度138、142包括用于计算优先值136、140的数据的一些实施例中，可以从周期性同步帧中省去优先值。相反地，如果优先值136、140提供了消费PSF110x(例如为了辨识或选择同步站的目的)的设备所需要的所有信息，则可以省去量度138、142。

[0075] 一个或多个同步辨识符150包括分配给发布了PSF110x的站参与其中的默认和/或组分级结构的辨识符。如上所述，默认辨识符可以用于辨识包含区域中所有对等设备的总体分级结构。组辨识符可以辨识设备的私有组。其他同步辨识符可以用于其他目的。

[0076] 在本发明的一些实施例中，用于分级结构内所有设备的默认辨识符通常将为0，并且只有希望与接入点或其他基础结构设备保持对齐的主设备将使用值不为0的默认辨识符。在这种情况下，主设备例如可以利用预定算法，根据接入点的BSSID(基本服务集辨识符)来得到其默认辨识符。该情形中的主设备可以只能够与也与同一接入点保持对齐的对等实体同步。

[0077] 但是，组辨识符可以由组根同步站、由另一组成员、随机地或者以其他某种方式来设定，如在下面的章节中所描述的那样。为0的组辨识符可以被设备用来指示其不是任何组的成员。因此，空闲对等设备可以具有默认和组辨识符对0/0，表明在其与默认分级结构同步期间，其不参与到任何组中。在私有组内活动的对等设备通常可以具有辨识符对0/x，其中x是设备的组所使用的数字。组可以具有任意数量的成员。

[0078] 在一些实施例中，PSF可以包括不是图1中所示的那些信息元素的信息元素。例如，PSF可以辨识用于选择同步站或主设备的算法，指定对同步站的限制(例如有多少可以位于相互范围内)，通告用于设备的分级结构的最大深度，提供关于站正离开网络的通知等等。

[0079] 此外，当作为组成员的同步站发布PSF时，那些帧可以包括特定于该组的信息元素，作为上面提到的组特定优先值/量度的补充或作为上面提到的组特定优先值/量度的替代。例如，站发布的PSF可以包括组特定的元素集，该组特定的元素集包括下列中的一些或所有：站的优先值、其在组中的级别或层级(或者距离组根的跳转数量)、组根同步站的名称或地址、组辨识符、以及/或者与站所属于的组分级结构和/或默认分级结构相关的任何其他数据。

[0080] 虽然同步站可能对于周期性同步帧的发布具有规定的周期，但是该周期是灵活的，并且对于变化可以有很高的公差。给定PSF可能由于对站的无线电部件的其他要求、由于通信信道上的争用、或者由于某种其他原因而在时间上提前或延后。在一些具体实施中，PSF可能每100毫秒变化大约+/-20毫秒。

[0081] 周期性同步帧可以伺机被传输，也就是说，如果同步站的无线电部件在其通常会在社交信道上发布PSF时被调谐到另一信道，则其可以替代性地在其当前信道上发布PSF。PSF广播将在能够的情况下返回到其在一个或多个社交信道上的正常调度。

[0082] 其中PSF在非社交信道上发送以辨识将来可用性窗口的这种类型的情形对于设备的局部群集可能是非常有用的。这样的设备可能将与同一(非社交)信道上的同一基础结构网络关联。在该信道上传输PSF就为这些设备节省了信道切换(即切换到社交信道)的成本，并且避免了干扰其基础结构通信。

[0083] 在最坏的情况下，被调谐到同步站的正常社交信道的新设备可能丢失有限数量的PSF，如果同步站在另一信道上忙的话。但是，同步站可以被调谐到常用频率(例如特定应用所要求的基础结构信道，如上所述)，并且因此可以在不同时间到达同一设备。

[0084] 图2是根据本发明一些实施例示出了在周期性同步帧中辨识的可用性窗口序列的示意图。所有同步站的可用性窗口可以被调度用于相同时间、用于相同或不同信道上，虽然不是在本发明的所有实施例中都这样要求。

[0085] 图2中所示的可用性窗口230被编号和管理为重复序列。特别地，分组同步帧210包括展示n个可用性窗口(编号为230(0)到230(n-1))的调度的同步参数。在一个循环之后，可用性窗口序列编号重复(即从0到n-1)。周期性同步帧可以限定任意数量的可用性窗口。

[0086] 除了辨识可用性窗口的部分或完整序列的调度之外，PSF还可以用信息元素(诸如PSF210的元素212)辨识下一个是哪一个可用性窗口序列编号。周期性同步帧还可以包括其他信息，诸如上述用于帮助进行接收的设备正确地计算在下一可用性窗口之前还剩余的时间的计时信息。

[0087] 可以被包括在PSF中的其他信息还有进行发布的站用于发送周期性同步帧的周期、以及PSF将在其上被广播的一个信道或多个信道。这允许对等设备确定其为了监听到PSF和获悉可用性窗口调度而必须在特定社交信道上监听的最大时间量。

[0088] 在一些具体实施中，PSF可以报告可用性窗口周期，并且各个设备可以计算窗口何时将出现，而不是辨识离散的可用性窗口。例如，PSF可以提供相对于下一可用性窗口的计时或偏置信息，并且报告进行发布的同步站的PSF周期。监听进行发布的同步站的设备于是可以确定可用性窗口的序列。PSF还可以辨识当前/下一可用性窗口的序列号。

[0089] 同步站所调度的可用性窗口可以按规则周期、也可以不按规则周期出现，并且可以与站的PSF同步、也可以不与站的PSF同步。换言之，可用性窗口不需要以相对于PSF相同的偏置来出现。可用性窗口的完整序列所占据的时间的一个示例性持续时间可以大约为5秒，但是本发明实施例的一具体实施可以使用更短或更长的持续时间。

[0090] 在本发明的一些实施例中，对于可用性窗口周期的公差比对于周期性同步帧周期的公差小，可能大约为每秒+/-100微秒(而对于PSF而言为每秒+/-200毫秒)。PSF非常短(例如小于1毫秒)但是频繁发布，而可用性窗口相对长(例如长于50毫秒)并且不频繁地实施(例如大约每秒一个)。PSF由于其持续时间短所以可以伺机地调度，但是可用性窗口被配置用于设备发现和通信，并且因此通常不能被伺机地调度。

[0091] 虽然不频繁，但是可用性窗口可以独占无线电接口长达显著的时间段；因此，遵循严格的调度是有利的，尤其是如果有其他无线电技术(例如蓝牙)存在的话。此外，其他(被同步)设备正依赖于所通告的窗口调度来进行发现和/或对等通信，这留出较少的变化空间。

[0092] 因此，在本发明的一些实施例中，PSF传输周期将具有相对高的变化公差，而可用性窗口周期具有相对低的变化公差。该策略的一个优点是其考虑了在每个周期性同步帧传输时出现的Wi-Fi连接。PSF传输只有在所选择的社交信道没有被使用时才是可能的，并且对信道或无线电部件的争用可能延迟、也可能不延迟PSF的发布。因此，所有PSF传输的严格调度会很难实现。

[0093] 当对等设备首先与主设备同步并且开始出席可用性窗口时，在第一窗口(和/或要求所有设备出席的第一窗口)中，其可以发布消息辨识其自身、辨识其优先值、提供其选择量度、通告其服务等。然后希望与其通信的任何设备可以进行联系。

[0094] 经由图2中的PSF210通告的n个可用性窗口在两个不同信道220x、220y(即分别在信道X和信道Y)上实施，这两个不同信道通常不是社交信道，但是可以是社交信道。或者，同步站所调度的可用性窗口可以在同一信道上进行或者可以分布在不止两个信道上。

[0095] 虽然可用性窗口被提供作为用于对等设备相互发现以及发现所提供的服务的主要机制，但是设备(包括同步站)可以跳过序列中的一个或多个窗口。例如，如果对等设备需要在可用性窗口期间将其无线电部件用于其他某种目的，则其可以根本不出席该窗口、可以晚到达或者可以早离开。设备可以(例如经由多播消息)向同步站或其他设备建议其缺席，也可以不向同步站或其他设备建议其缺席。

[0096] 在本发明的一些实施例中，设备可以为其自身设置“存在模式”，并且将该值通告给其同步站和/或其他对等实体，以指示其将多频繁地调谐到或出席所通告的可用性窗口。在一些实施例中，存在模式(或PM)是整数值，诸如1、2、4等。设备的PM的倒数是指示其将出席序列中多少可用性窗口的分数。例如，如果设备的PM＝1，则该设备将出席每个可用性窗口；如果其PM＝2，则该设备将出席每个序列号为2的倍数的窗口(即窗口的1/2)；如果PM＝4，则其将出席每个序列号为4的倍数的窗口(即窗口的1/4)。

[0097] 越高的存在模式值就允许设备跳过越多的窗口并且关闭其无线电部件，从而节省电力。最终，存在模式等于序列中可用性窗口的数量(即在图2中为n)就表示设备对于每个序列将只出席一个可用性窗口。PM值为零可以表示设备始终可供使用(即不仅仅在可用性窗口期间)。

[0098] 在本发明的一些实施例中，每个被同步设备必须出席其主设备所通告的序列中的至少一个可用性窗口。例如，设备可能被要求在每个序列的可用性窗口0期间同步。因此，在这种情况下，PM值等于可用性窗口序列的长度就表明设备将只在序列号为0的可用性窗口期间出现。

[0099] 可用性窗口序列的长度一般为2的幂(例如8、32、256)。如图2中所示，主设备所发布的可用性窗口的序列号从零开始，并且每次增加1，直到值为长度-1(例如7、31、255)，之后序列号又重复。分支同步站被要求(在其同步帧中)采用和重复其主设备(即根同步站或另一分支同步站)的当前序列号。因此，在一个根同步站下同步的所有设备将商定哪个可用性窗口具有序列号0。

[0100] 在本发明的一些实施例中，不同同步站所通告的可用性窗口序列可以是长度不同的。但是，所有序列都将对齐，从而具有某个存在模式值的所有设备将出席相同的窗口。换言之，所有设备将商定哪些具体窗口是给定数的倍数。

[0101] 例如，考虑这样一种分级结构，其中长度为8、16和64的可用性窗口序列在不同设备集(例如与不同同步站同步的设备)中使用。在实现八个窗口的序列的设备中，每第八个窗口将被认为是序列号为0的可用性窗口。并且，对于那些设备而言序列号为0的每个可用性窗口将被认为是对于具有长度为16个窗口的序列的那些设备而言序列号为0或8的可用性窗口，并且被认为是对于在其序列中具有64个可用性窗口的那些设备而言序列号为0、8、16、24、32、40、48或56的可用性窗口。

[0102] 设备可以出席多于其PM所指示的可用性窗口，但是通过通告其存在模式值(例如经由可用性窗口序列号0中的多播消息)，其他设备将知道它们何时可以与其交互。并且，如上所述，只要一个其他设备发送通信到具有最大PM值(等于可用性窗口序列的长度)的设备，在进行接收的设备所出席的窗口期间该设备就将延伸其在该信道上的出现，以便进行该通信。

[0103] 此外，在一些实施例中，每当存在模式大于1(或其他某个阈值)的对等设备接收通信时，其就可以自动地将其存在模式设置为1(或某个其他更小值)，以便促进所希望的通信。另外，具有低存在模式(例如零或一)的设备在一个可用性窗口中接收到多播帧之后可以在一个或多个后续窗口中对其进行重复，以帮助使其到达其对等实体。

[0104] 同步站可以具有任何PM值；虽然其按周期性间隔(可能甚至在可用性窗口期间)发送同步帧，但是其在可用性窗口期间当其不是正在发送同步帧时可以关闭其无线电部件或者将其无线电部件或天线用于其他通信要求。

[0105] 图2中所示的PSF210的格式仅仅是示例性的；在其他具体实施中，必要信息(例如同步参数)可以以其他形式被传送。例如，可用性窗口的调度可以作为信道、时间、持续时间和周期的组合来被传播。在该格式中，信道元素辨识通信信道，时间元素辨识可用性窗口的起始时间，持续时间元素指示可用性窗口的正常持续时间，而周期元素报告下列周期，即可用性窗口将以该周期来实施。

[0106] 在本发明的一些实施例中，希望进行相对延长的通信周期(例如用于文件传输，为了进行游戏或其他应用)的两个或更多个对等设备可以与总体同步并行地、但是在调度的可用性窗口之外或作为调度的可用性窗口的补充，建立其自身的同步用于交换数据的目的。在这些实施例中，这两个或更多个设备中的一者可以担当非选择主设备的角色，也就是说，其不参与在下面的章节中所描述的主设备选择过程，但是可供其它设备用于同步到或与之同步(例如为了进行文件传输，为了玩游戏)。与非选择主设备同步的设备可以形成基本服务集(BSS)。

[0107] 非选择主设备可以发布其将与之进行通信的其他对等设备将用来与非选择主设备同步、但是社区中的其他设备将忽略的同步帧。示例性地，这些同步帧可以在可用性窗口期间或者在商定的信道上被传输。非选择主设备的同步帧可以指定该设备是非选择主设备，从而不需要直接与其通信的那些设备将知道它们不应与其同步。

[0108] 希望与对等实体社区同步或保持同步的设备可能不能这样做，这可能是因为其不能监视社区的一个或多个社交信道、在调度的可用性窗口期间具有其他承诺、或者出于其他某种原因。在这种情况下，该设备可以成为非选择主设备(并且辨识其何时可供使用)来帮助其他设备发现它。或者，其可以请求同步站改变其同步调度来适应该设备(例如改变同步站的可用性窗口的时间和/或一个或多个信道)，或者可以在其选择优先值表明其应该的情况下成为同步站。作为同步站，尤其是作为根同步站，其可以改变可用性窗口调度。

[0109] 在本发明的一些实施例中，在会合信道上在可用性窗口期间，同步站或其他设备(例如非选择主设备)可以广播被称为主指示帧(MIF)的另一类型的同步帧。在这些实施例中，主指示帧提供帮助对等设备实现或保持(要么与发布定期PSF的同步站，要么与设备可与之同步来直接交换数据的非选择主设备)同步的信息。主指示帧可以在可用性窗口期间被发送，但是一般将不会在社交信道上被发送，除非例如一个主指示帧在正在社交信道上发生的可用性窗口期间被发送。

[0110] 主指示帧可以包括周期性同步帧可能包括的任何数据、以及/或者其他信息。例如，MIF可以被同步站发送以报告其将开始使用另一社交信道来发送PSF，可以被非选择主设备发送以报告其将在特定时间在特定信道上具有可用性的窗口，可以被另一设备发送以报告其从其他某个同步站监听到的同步数据或以通告其可用性，等等。

[0111] 当可用性窗口与PSF通常会被发送(即根据进行发布的同步站的PSF周期)的时间重叠时，定期PSF可以在可用性窗口实施的信道上(并且不是在社交信道上)被发送。在不与主设备的PSF周期的届满重叠的可用性窗口期间，主设备可以发送MIF以确保与其同步的设备具有必要的同步数据，而不必调谐到社交信道用于定期PSF。但是，设备可以仍然周期性地监听一个或多个社交信道以获悉其他主设备。

[0112] 因为存在模式值不为1的对等设备不可能出席每个可用性窗口，但是可能被要求在序列号为0的可用性窗口期间出现，所以同步站可以在默认情况下始终在这些窗口期间广播PSF或MIF。PSF短但是频繁，而MIF更长并且更不频繁，并且可以封装延伸服务和设备能力有效载荷。

[0113] 可能会注意到，周期性同步帧频繁地被发送，通常在可用性窗口之外被发送，以便帮助未同步的设备与其对等实体同步。在设备集合被同步之后，那些设备可以只(或主要)在相对稀疏的可用性窗口期间相遇，尤其是那些已经调整其存在模式以更少地使用其无线电部件并因此节省电力的设备。为了保持同步，这些设备可以依赖于在可用性窗口期间发送的主指示帧。

[0114] 在本发明的一些实施例中，设备被要求在一些(或全部)可用性窗口开始处实现保护周期，在该保护周期期间，它们监听并且可以接收通信，但是不传输。在本发明的不同实施例中，该限制可以始终适用于、也可以不始终适用于发布定期PSF的同步站，但是一般将始终适用于非选择主设备。

[0115] 图3是根据本发明一些实施例展示无线通信环境中设备与对等实体社区的同步的流程图。

[0116] 在操作302中，设备通电或进入该环境，并且开始在一个或多个预定的社交信道上针对周期性同步帧(PSF)进行监听。其可以被编程有关于PSF的默认或可能的周期性的信息，并且因此可以只需要在给定社交信道上监听有限数量的那些周期(例如一个、两个)，以便截获同步站在该信道上广播的PSF。

[0117] 在操作304中，设备监听到一个或多个PSF，并且提取其同步数据。在本发明的该图示的实施例中，同一设备分级结构内同步站所发布的所有PSF将通告相同的可用性窗口序列或调度。同步站可以在相同或不同的社交信道上传输其PSF，并且可以在相同的非社交信道上实施可用性窗口。

[0118] 如果设备没有监听到任何周期性同步帧，则其可以假设没有同步站在范围内。因此，其可以承担根同步站的角色，并且开始发布其自身的PSF以便对范围内的其他设备进行同步。如下一章节中所描述的那样，用于选择同步站的过程可以定期地或者甚至持续地被应用，以辨识应该作为主设备的设备。

[0119] 在操作306中，设备将其无线电部件调谐到指定的信道，并且出席下一可用性窗口，如果其无线电部件没有被另一应用或服务抢占的话。如果不能出席，则该设备将出席其能出席的下一可用性窗口，尽管其可能需要再次在社交信道上监听以接收下一组同步数据并获悉其信道和起始时间。设备可以推迟出席可用性窗口直到下一窗口序列开始，并且因此调谐到下一所要求的窗口(通常是序列号为0的窗口)。

[0120] 在操作308中，在可用性窗口期间，同步帧由该设备当前与之同步的同步站广播(例如PSF或MIF)。这可以使设备不需要扫描一个或多个社交信道。同步帧示例性地可以在可用性窗口开始处的初始保护周期或静默周期期间被传输，在该周期期间，并非同步站的设备(例如叶子设备)不可以传输。

[0121] 在操作310中，设备在必要或期望的情况下(例如如果设备不能出席可用性窗口的完整序列)设置其存在模式。至少在其出席的第一个可用性窗口和/或序列号为0的第一可用性窗口期间，设备在对所有被同步设备的消息广播中辨识其自身(例如地址、名称、服务信息)。其可以同时通告其存在模式。

[0122] 在可选操作312中，设备可以直接与其被同步的对等实体中的一者或多者在可用性窗口期间和/或带外通信，或者它们可以与该设备通信。如上所述，设备可以延伸其在窗口处的出席一次或多次以便促进通信，将向其活动的对等实体通告其是否以及何时必须离开窗口(例如为了将其无线电部件用于其他某种目的)，并且可以与另一对等实体信道外地设置单独会合。

[0123] 在本发明的一些实施例中，可以在一些或所有可用性窗口期间实施业务量减少或限制措施，以便减少通信拥塞和冲突。示例性地，控制可用性窗口序列的同步站可以指定措施何时就位。在一些具体实施中，业务量减少措施只在可用性窗口期间被应用，而不在可用性窗口扩展期间被应用。在强制可用性窗口(即序列号为0的可用性窗口)中，业务量减少措施可以是强制性的。

[0124] 以举例的方式，业务量减少措施可以用于针对设备在一个可用性窗口期间可以传输的多播帧的数量(例如大约三个)来对设备进行限制。单播帧的传输也可以被限制。

[0125] 例如，可以只允许到(和/或来自)存在模式值未知或者值大于1(或其他某个阈值)的设备的单播传输。对单播或多播帧传输的限制可以不应用于为了有限目的(诸如文件传输)而在相互之间(例如与非选择主设备)同步的设备。

[0126] 在操作314中，设备可以在不需要监听社交信道上的PSF或出席可用性窗口时关闭其无线电部件。

[0127] 图3中所示的本发明的方法仅仅是示例性的，而并不限制根据本发明其他实施例的方法。

[0128] 如上所述，在任何可用性窗口外面或者除了任何可用性窗口之外，两个或更多个对等实体可以进行其自身的同步。例如，它们中的一者可以担当非选择主设备的角色并且在可用性窗口期间发布主指示帧或其他同步帧，以向其对等实体建议它们何时以及在哪里(即时间和信道)可以与其同步。

[0129] 但是，一个对等实体可能希望在不同步的情况下与另一对等实体进行短的通信交换。例如，与一个分级结构同步的设备可能希望发现在另一(例如相邻)分级结构内同步的(一个或多个)对等实体所提供的服务，可能希望轮询相邻对等实体等。至少初始地，它们不想要进行显著的数据交换(例如如同文件传输)。本发明的一些实施例以带外查询和响应的形式提供这种能力。

[0130] 更具体地，第一对等实体可以监听到相邻分级结构的同步帧，并且因此获悉其可用性窗口的调度。如果能够的话，其可以出席相邻分级结构的可用性窗口中的一个或多个，并且由此发现其他设备，并且其可以发送带外帧给相邻设备中的一个或多个。

[0131] 图4是根据本发明一些实施例展示带外交换的示意图。如同上面所描述的周期性同步帧的计时那样，进行传输的设备必须考虑在其自身内将发生的在其释放或准备用于传输的查询时与其实际被传输时之间的延迟。

[0132] 查询时间线410反映在进行查询的设备处的活动，而响应时间线430反映在进行响应的设备处的活动。在发布查询时，进行查询的设备必须选择适当的查询寿命450，使得进行响应的设备将有时间来接收、处理查询并对查询进行反应。

[0133] 在图示的查询和响应中，查询在目标传输时间412处排队等待从设备传输。由于天线或介质的争用、以及/或者其他延迟(在图4中被总体地表示为争用414)，查询在实际传输时间416之前没有被物理地传输。

[0134] 停留时间418是查询寿命的剩余时间，在该剩余时间期间，进行响应的设备必须接收该查询并且生成并传输其响应。停留时间418的持续时间取决于进行查询的设备所设置的查询寿命以及争用414的持续时间。进行响应的设备也可能经历在其目标传输时间432和响应的实际传输时间436之间的延迟；该延迟被表示为争用434。

[0135] 查询可以(在带外查询中)辨识相关时间参数(例如查询寿命、目标传输时间、实际传输时间、争用)中的任何或全部，使得进行响应的设备可以确定其是否将能够在查询失效之前进行响应。如果不能，则其将丢弃该查询或者中止其响应。如果进行查询的设备在查询寿命期间没有接收到响应，则其可以重试(例如以更长的寿命)、放弃该查询或者进行其他动作。

[0136] 在本发明的一些实施例中，对等设备可以向其可以监听到、但是并没有同步到的同步站发布带外查询，以便辨识该同步站以及同步到该站的设备所提供的服务。在一些具体实施中，其可以将关于其他同步站的信息转播到其同步的对等实体，诸如在它们的可用性窗口中的一个或多个期间。可以被透露的关于另一同步站(或其他对等设备)的信息可以包括诸如其监视的社交信道、其可用性窗口(例如时间、信道、周期)、主偏置、其提供的服务、地址等这样的事情。因此，带外查询可以充当准PSF或准MIF，因为其可以允许设备同步到查询发送方的分级结构。

[0137] 一些未同步的主设备(例如没有任何叶子设备或下级主设备已经同步到的同步站)可以采用低功率操作模式。该低功率操作模式可以在站的同步帧中被指出，或者可以由可用性窗口的序列或调度以及/或者同步帧中所通告的存在模式来推断。

[0138] 在一个这样的操作模式中，未同步的主设备仍然可以发送周期性同步帧，但是提供具有长周期(例如几秒)的短可用性窗口。由于可用性窗口短、稀疏的本质，对等实体可能要花一些时间来发现未同步的主设备所提供的服务。

[0139] 在根据本发明一些实施例的通信环境内对等实体同步期间，因为对等设备被组织到分级结构中，所以叶子(或从)设备与范围内的分支同步站同步；那些站(并且可能还有其它叶子设备)与较高分支同步站同步，以此类推，其中一个根同步站为整个环境提供同步信息。叶子设备可以直接与根同步站同步，如果其在范围内的话。

[0140] 环境内设备的工作参数可以指定设备的分级结构的最大深度，其可以被定义为同步站的级别或层级的数量。根同步站的位置被定义为层级0，而分支同步站将位于层级1到层级D，其中D是同步站可能位于的最大层级。

[0141] 在默认情况下，在分级结构正被组织时，对等设备可以发布周期性同步帧，直到其落到作为叶子的位置，而在这样的时候，其停止传输PSF。即使可应用的选择算法可能使设备作为同步站，该设备也可以选择作为叶子，除非在该设备的范围中没有同步站。如果在范围中没有同步站，则该设备必须担当该角色。

[0142] 所有主设备继续发布PSF以维持其区域内的同步，并且可以以作为其在分级结构中的级别或层级的函数的周期性来继续发布。例如，位于层级0处的根同步站可以大约每100毫秒(ms)发布PSF，层级1处的分支同步站可以大约每150ms发布PSF，层级2处的分支同步站可以每500ms发布PSF，以此类推。这些值仅仅是示例性的，而并不是要以任何形式对PSF周期的持续时间进行限制或限定；不同层级内的同步站可以采用相同的周期，而相同层级中的同步站可以采用不同的周期。

[0143] 主设备的层级通常将在其PSF中被报告。该信息允许进行监听的设备确定分级结构有多深是在其环境区域内。根据该深度和/或其它信息(例如其可以监听到多少同步站在发布PSF，最大分级结构深度)，设备可能能够确定其应当作为叶子还是其应当继续发布PSF并且仍然作为同步站。

[0144] 分级结构的最大深度参数可以被编程到设备中和/或在周期性同步帧内被通告。还可能施加其它限制，诸如同步站的最大数量、要求同步站只有在其只能够监听到不多于阈值数量的其它主设备(例如在特定范围内，在特定层级处，总体地)的情况下才继续其角色等等。

[0145] 例如，如果分级结构的最大深度为D，则位于层级S≥1(即除了根之外的所有层级)的同步站可以只被允许监听到D–S个在层级S中工作的其它同步站，并且仍然继续作为同步站(假设那些其它主设备具有较高或更好的选择优先值)。该规定可以允许将较高级别的分支同步站集中在根同步站附近，以及将分支同步站分散得更远。

[0146] 在本发明的一些实施例中，选择算法或过程可以更宁愿保持现任的同步站，而不是否则可能会被给予优先级的另一设备，除非该另一设备的选择优先值超过现任的选择优先值的量达到了阈值。这可有助于避免同步站无意义的(thrashing)或过度的切换。但是，因为同步站的主要任务仅仅是广播同步数据，所以切换同步站并不会对分级结构或单个设备带来高的交易成本。

[0147] 在本发明的一些实施例中，设备将与其能监听到的最佳同步站(即具有最高优先值的同步站)、或者其能在给定范围内(例如以超过特定阈值的信号强度)监听到的最佳同步站同步。

[0148] 当设备在环境中上线并且监听PSF时，如果其只从位于分级结构的最深层级或最大层级处的分支同步站监听到，则其可以作为叶子同步到该站。但是，如果该设备还可以监听到另一分级结构中的另一同步站(例如如在周期性同步帧中通告的根同步站属性所确定的)，则其可以更愿意加入该分级结构，如果该另一同步站不是位于最大深度或层级处或者如果该另一同步站具有更好的选择优先值。

[0149] 只能监听到分级结构中相对深(例如高的层级值)处的其它设备的设备可以能够确定其处于环境的边缘处。如果这些其它设备中大多数或全部都已经处于最大深度处，则新的分级结构可以产生，尤其是如果具有高优先值的设备出现的话。

[0150] 新的环境/分级结构还可能在现有的环境/分级结构跨越太大空间区域时出现。例如，分级结构的深度、关于对等设备有多近的测量、和/或其它因素的组合可以导致新的分级结构产生。如在下一章节中讨论的那样，在对等实体之间检测到的信号强度可以是确定对等实体有多近的一种方式。

[0151] 要求对等实体只与与其相对近的主设备同步就可以使分级结构相对紧凑。相反，对树的最大深度的高限制可以允许分级结构覆盖更多区域。通过调整这些(和/或其它参数)，可以形成适当的分级结构。

[0152] 用于配置分级结构的不同参数将根据设备密度、通信负载和/或其它因素而适配于不同环境。例如，如果负载相对轻(例如设备是低功率传感器)，则与隐藏节点问题关联的缺点应该被限制，并且可以实施相对深的分级结构(例如大约10到15个级别)。此外，在更稀疏的环境中，下面所述的用于选择同步站的过程将更快地解决。

[0153] 隐藏节点问题是指下列一种情形，即其中不在相互范围内的多个设备试图与共同的对等实体通信。因为它们不能监听到相互的传输，所以它们不能相互避开，并且它们与该共同的对等实体的通信可能冲突。虽然这可能由于需要在相对短的时间周期期间(即在可用性窗口内)通信而加剧，但是轻的负载可以帮助减轻该问题，并且允许与在具有更重负载的密集环境中将可能实现的分级结构更深的分级结构。

[0154] 如果没有本文中所描述的同步方法，则为了发现环境中所有设备而需要的发现帧的总数量可能接近设备数量的平方(即每个设备都可能需要发送至少一个帧给其它每个设备)。这些帧会在随机的时间在任意信道上被发送。

[0155] 相反，本发明的实施例所提供的集体同步使得能够实现基于来自所选设备集(即同步站)的定期传输的同步，并且很好地扩展。在一极好地同步的环境中，所有设备相互发现所需要的帧的数量与设备的数量成比例。在序列号为0的可用性窗口期间广播的一个发现帧将到达范围内的所有其它设备。

[0156] 同步站的选择

[0157] 在本发明的不同实施例中，可以应用不同算法来确定哪些对等设备应当作为同步站(也被称为主设备)。在给定环境中应用的算法通常将是对称的，也就是说，每个设备对于其自身及其对等实体使用相同的数据，并且对于那些数据使用相同的标准，并且从而每个设备将对于哪个设备应当作为根同步站以及哪些其它设备应当作为分支同步站得到相同的结论。在一些实施例中，所指定的选择算法在每个可用性窗口(以及该窗口的任何延伸)之前、期间或之后，或者在某个可配置数量的可用性窗口之后被执行。

[0158] 如在前一章节中所描述的那样，在选择同步站中可能扮演重要角色的一个设备参数是主设备优先值，其指出该设备优先作为同步站或主设备。

[0159] 每个设备的优先值以相同的方式，利用该设备的相同的量度(“选择量度”)和属性来得到。示例性的选择量度包括可用的电力(例如电池强度)、设备是否连接到AC(交流电)电源、设备类型、设备配置(例如特征、资源)、是否(以及有多少)应用程序或实用程序要求使用设备的无线电部件、设备是否具有多个天线和收发器、设备是否可以工作于多个频带(例如2.4GHz和5GHz)、处理器负载、传输争用、存在模式等。

[0160] 在一个简单的具体实施中，设备的优先值可以是与其剩余电池电力成比例的整数值。特定高值可能表示设备连接到AC电源。多个设备的优先值相当则可以通过比较网络(例如MAC)地址、IMSI(国际移动用户辨识)、IMEI(国际移动设备身份)或设备的其它某种独特特性来解决。

[0161] 在一些具体实施中，设备可以仅仅相互发送其优先值，但是可以附加地或者替代地发送用于计算优先值的选择量度。如前面所讨论的那样，分级结构的根同步站的优先值和/或选择量度可以被包括在所有周期性同步帧中，分支同步站的数据可以被包括在其发布的PSF中，而叶子设备的数据可以在可用性窗口期间被通告。

[0162] 在本发明的一些实施例中，具有最高优先值的对等设备成为环境的默认分级结构的根同步站。还可以选择分支同步站以扩展同步区域，而其它对等实体将作为叶子设备(或从设备)。除了根同步站之外的每个设备要么同步到根同步站，要么同步到其它同步站中的一者。

[0163] 在本发明的一些实施例中，除了被部署在分级结构内的特定层级处之外，其它对等设备可以通过它们在物理上距离特定设备多近来相对于给定设备被分类。例如，在一个具体实施中，给定设备可以将其可以监听到的对等设备分类到三个范围之一中：“近距范围”、“中距范围”或“远距范围”。

[0164] 范围测量或评估可以由接收信号强度指示(RSSI)和/或其它距离指示(例如GPS数据)来得到。示例性地而非限制性地，“近距范围”可以被定义为大约5米，“中距范围”可以被定义为大约10米，而“远距范围”可以被定义为大约15米或更远。

[0165] 在其它具体实施中可以使用其它范围(多于或少于三种范围)。例如，设备可以只考虑一种范围，其可以对应于以上近距范围、中距范围或远距范围评估中的一者，或者可以对应于其它某种范围或信号强度。为了避免边界条件，对等设备可能需要至少以阈值RSSI被监听到才能在选择过程中被考虑。

[0166] 选择过程可以定期地操作，诸如在每个可用性窗口之后(或期间)、在每个完整的可用性窗口序列之后、或者按照其它某种调度。作为组成员的设备可以分开地为其组分级结构及其默认分级结构执行选择过程。例如，其可以首先在组内执行适当的选择过程以找到其角色/位置，然后再次进行选择过程以确定其在默认分级结构内的角色/位置。这两个过程可以是相同的，也可以是在一定程度上不同的。

[0167] 当其执行主设备选择过程时，进入被同步通信环境的新设备可以篡夺现有的同步站，分级结构中作为叶子或较低分支同步站的设备可以向上移动(例如因为具有更好优先值的其它设备已经离开)，另一设备可以从作为分支同步站向下移动到作为叶子，等等。

[0168] 在设备在分级结构中获得作为叶子或同步站的位置之后，其将继续监听同步帧，以确定其是否比发送那些帧的站更适于作为同步站。例如，其可以继续收集和处理设备的优先值或选择量度，以确定其它设备是否比该设备自身更适于作为同步站。

[0169] 当设备监听到来自不同对等实体的同步帧时，其可以汇编其监听到的和/或在帧中辨识的主设备的列表。这允许该设备周期性地确定其是否应当作为主设备并开始发布同步帧。这样的确定可以依赖于其优先值(或选择量度)与其它设备的优先值(或选择量度)的对比情况、其监听到多少主设备、那些主设备有多远、以及/或者其它因素。

[0170] 图5A根据本发明一些实施例示出了可以在单个默认分级结构内选择同步站并且同步的对等通信设备的集合。在所示情景中，对等设备510同时地或几乎同时地上线或进入它们的环境，从而几乎同时要求所有设备为自身在分级结构中确定适当的位置。

[0171] 当设备510a至510j上线时，它们将在至少一个指定的社交信道上进行监听。该信道可以被编程在设备的固件中，可以由服务提供商作为设置过程的一部分来编程，或者可以以某种其它方式被设备知道。

[0172] 它们中每一个都监听等于或大于一个已知或默认PSF周期(例如100ms)的持续时间，在该持续时间期间，同步站(分支或根)通常会广播一个周期性同步帧(当存在时)。因为在所示环境中在设备510出现之前没有其它设备存在，所以它们没有监听到PSF。在一些具体实施中，设备可以在多个不同社交信道上进行监听，和/或可以在认为没有同步站存在之前监听更长的时间(例如几个PSF周期)。

[0173] 因为没有检测到主设备，所以它们全部几乎同时地决定它们应该作为同步站，并且因此它们全部都开始发布PSF。如在前一章节中所述，PSF通告一个或多个可用性窗口的序列，指定它们正工作于哪个层级(在这种情况下，层级0或根)，报告它们的默认和组辨识符，并且还提供发布者的优先值和/或选择量度。

[0174] 为了描述本发明的实施例的目的，在图5A中，设备510f具有最佳(例如最高的)优先值，然后是设备510d。分级结构的最大深度为2，也就是说，将只有两个级别或层级的主设备：根同步站(在层级0处)和其之下一个级别的分支同步站(在层级1处)。所有其他对等实体将作为同步到同步站的叶子设备。

[0175] 因为它们全部都发布PSF，所以所有这些设备都将检测到至少一个对等设备的周期性同步帧。尽管有冲突、干扰和重新传输，每个设备都将意识到有对等实体作为或试图作为同步站。

[0176] 每个设备将要么继续发布PSF，要么将停止，这取决于其优先值、其他对等实体的优先值，和/或其他因素。因为所有广播同步帧的设备都报告其优先值(或其选择量度)，所以可以容易地将这些设备进行比较以确定哪些应当作为同步站。

[0177] 在图5A所示的实施例中，设备可以被编程为如果其(例如总体地，在特定层级内，在特定范围内)监听到阈值数量的同步站，尤其是如果这些其他设备具有更好或较高的主设备优先值，则自动地停止发布PSF。特别地，所有设备认为自身是第一主设备，并且它们的PSF将指出它们位于层级0(即根)处。因为该级别处同步站的阈值被配置为1(即只能有一个根同步站)，所以一旦设备监听到一个PSF来自工作于层级0且具有更好优先值的对等实体，其就应当停止发布PSF。

[0178] 但是，如上所述，在本发明的一些实施例中，设备首先与离其近的同步站同步，然后设备才进一步向外看。因此，它们可能首先只将自身(其选择量度或主设备优先值)与其(例如基于RSSI)检测为处于近距范围(例如5米)内的设备比较。

[0179] 主设备选择算法或过程可规定在多个范围中的每一者内同步站的最大数量。第一范围(例如“近距”范围)内竞争作为根同步站(或顶部主设备)的设备将在认识到该范围内更有资格的设备的数量达到或超过对于该范围而言同步站的最大数量(即1)时停止竞争(并且停止广播同步帧)。类似地，第二范围(例如“远距”范围)内竞争作为根同步站的设备将在认识到该范围内更有资格的设备的数量达到或超过对于该范围而言同步站的最大数量(即，还是1)时停止。

[0180] 通过首先与“近距”主设备同步，环境至少初始地往往聚集为局部集群。这可以帮助减少干扰，并且还反映现实情况，其中设备的使用者经常与其附近的使用者共享数据，而不是与更远的某个人共享数据。通过随后进一步向外看，设备的集群可以发现更大环境并且与之同步。

[0181] 在图5A中所示的环境中，考虑两个范围：“近距”和“远距”。如前面所述，将设备分类为近距还是远距可以取决于这两个设备之间的信号强度和/或其他因素。在其他实施例中，可以考虑其他范围。

[0182] 在图5A中，为具有最佳主设备优先值的两个设备(设备510f、510d)示出了“近距”范围圈。还为不将成为同步站的一个示例性设备(设备510a)示出了近距范围圈。

[0183] 继续上面的描述，由于每个设备认识到只能有一个根同步站(在层级0)，所以如果在近距范围内存在具有较高优先值的设备，则它们全部都停止发布PSF。这意味着，在它们各自的近距范围内，只有设备510f和510d继续发布周期性同步帧；它们每一个因此成为其自身的近距范围内的根同步站。因此，在所示情景中，暂时存在至少两个单独的默认分级结构，一个根在设备510f处，而另一个根在设备510d处。如很快将看到的那样，它们将合并。

[0184] 这两个根同步站的范围内的其他设备同步到它们，并且可以开始出席它们的可用性窗口。需要指出的是，位于这两个根同步站近距范围内的设备510i同步到设备510f，因为其与设备510d相比通告更好的主设备优先值。

[0185] 既然每个设备都识别了其根同步站，并非级别0主设备的每个设备就可以确定其是否应当争取作为层级1处的主设备。该确定可以取决于诸如分级结构的最大深度、其在该级别处监听到多少其他主设备候选者(如果有的话)、其与那些其他主设备候选者距离多近、设备的优先值等等这样的因素。

[0186] 在图5A至5D中所示的本发明实施例中，环境的操作或配置参数可以决定在给定层级或级别，设备将假设需要另一同步站(并且其是该位置的候选者)，除非其可以在该层级处监听到某个阈值的其他同步站具有更好的选择优先值。

[0187] 在图5A至5D中所示的实例中，在层级1处并且在分级结构的最大深度为2(例如两层同步站，在层级0和1处)的情况下，可能设备只能争取成为层级1分支同步站，如果其在该层级没有监听到任何其他同步站(或者在特定范围内没有监听到任何其他分支同步站)的话。换言之，在任何其他设备的范围内在层级1只可以有一个分支同步站。任何监听到来自层级1同步站的PSF的设备不会传输其自身的PSF以及试图成为层级1中的主设备，只要它监听到的同步站具有较高的主设备优先值。

[0188] 因此，在图5A中，不是设备510f和510d的一些设备将发布PSF来通告与其根同步站(510f，510d)相同的可用性窗口，但是报告其自身的层级(即1)和其优先值。监听到这些对等实体的PSF的设备在其优先值更差的情况下将中止其自身成为级别1主设备的试图，但是在其优先值更好的情况下将继续。

[0189] 因此，设备510g、510h、510i中至少一者将成为根同步站510f之下的层级1分支同步站。类似地，设备510a、510b、510c、510e中的至少一者将成为设备510d之下的层级1分支同步站。因为它们当前仅仅是在选择近距主设备，并且由于对等实体之间的距离，所以在分开的分级结构中实际上将选择不止一个层级1分支同步站。

[0190] 位于根同步站近距范围内、但是具有不足主设备优先的其他设备将作为叶子设备(或从设备)，并且将保持与同步站同步。层级1分支同步站将延伸分级结构的范围，并且帮助使更多设备同步。

[0191] 例如，超出设备510f和设备510d二者近距范围的设备510j可能已经建立了其自身的单节点分级结构。需要记住，所有设备510同时上线并且开始发布PSF来提名自身作为根同步站。假设设备510j具有高于其附近的任何设备(例如设备510a、510h)的主设备优先值，则其会继续作为同步站，即使是在其附近的任何设备遵从其他设备并且停止发布PSF之后也是如此。再假设设备510j的优先值低于设备510d和510f的优先值，则附近设备(例如设备510a、510h)将与设备510d和510f而不是与设备510j同步。因此，设备510j暂时形成其自身的环境和分级结构。

[0192] 现在，如果设备510a、510h中任一者或它们二者成为层级1主设备，则它们将开始发布通告其根同步站的优先值的PSF。设备510j将监听到那些PSF并且认识到根在“更好的”根同步站处的分级结构在范围内，并且因此将与通告最佳根同步站的设备(即，如果其可以监听到510h和510a二者则为设备510h)同步。

[0193] 该场景展示了设备(例如设备510j)可以与具有较低主设备优先值的对等实体(例如设备510h)同步并成为其之下的叶子，如果该设备不能直接监听到该对等实体的主设备或如果该主设备超出设备当前正在监听的范围之外的话。如果叶子设备被配置为进一步向外看(例如向“远距”范围)，则其可以直接同步到该远距范围同步站或者完全同步到另一设备。或者，在作为其自身的单节点分级结构的根同步站期间，设备510j可以开始监听更好的远距范围同步站并且直接与设备510f同步。

[0194] 在本发明的一些实施例中，除了考虑设备当前可以监听到多少同步站之外，在设备确定其是否应该停止试图作为同步站时还可以考虑那些同步站的范围。例如并且如上所述，如果对等设备监听到第一阈值数量的(例如一个)具有更好优先值的近距范围对等实体，则对等设备可以停止发布周期性同步帧，并且遵从这样的具有更好优先值的近距范围对等实体。在这些实施例中，即使没有监听到任何更好的近距范围同步站，如果对等设备监听到第二阈值的(例如三个)具有更好主设备优先值的远距范围对等设备的话，对等设备也可以停止发布PSF。

[0195] 图5B是根据本发明一些实施例可以得自图5A中所示的主设备近距范围同步和选择的分级结构的示意图。线段表示同步，其中箭头指向正在发布PSF并且管理可用性窗口的同步站。

[0196] 虽然可能有多个设备正作为层级1分支同步站并且发送PSF，但是在图5B中只有其中的一者(设备510h)实际已经将其分级结构延伸到其根同步站的范围之外。图5B中所示的设备同步和组织可以在从所有设备上线时开始计算大约1秒钟或者一个可用性窗口时实现。对于不同具体实施，所有对等实体安置到适当角色和层级中所需要的持续时间将不同，这取决于设备的数量、主设备选择算法在该期间被执行的可用性窗口的频率和持续时间、和/或其他因素。

[0197] 在本发明的一些实施例中，同步树或分级结构(诸如图5B中所示的同步树或分级结构)并不是要用于路由的目的，而是用于对区域内的设备进行同步，使得它们可以以对等方式直接通信。

[0198] 在本发明的所示实施例中，在近距范围的同步之后，根同步站(即级别0处的那些：设备510f、510d)现在进一步向外看，以确定它们是否应该同步到另一同步站。为了示例的目的，可以假设“远距”范围大约为近距范围的距离的两倍。

[0199] 在其他一些实施例中，所有同步站监听更长范围的设备；叶子设备仍然关注近距范围。如果它们具有的优先值不足以其成为近距范围内的同步站，则基本上没有理由使它们试图确定它们是否应该是更长范围的同步站。在另外一些实施例中，所有设备可以监听更长范围的设备。

[0200] 图5C示出了在远距主设备选择和同步开始时图5A中的设备。虽然在图5C中没有示出完整的范围圈，但是可以假设设备510f的远距范围包含除了设备510b、510c之外的所有设备，而设备510d的远距范围包括除了设备510g之外的所有设备。因此，所有设备都在这两个顶部设备中至少一者的远距范围内。

[0201] 根同步站510f将不减退地继续发布PSF并且通告其可用性窗口序列，因为即使在远距范围，其也没有监听到报告具有较高主设备优先级的同步站的任何同步帧。但是，根同步站510d很快获悉设备510f具有更好的主设备优先值。设备510d可以直接从设备510f的PSF或者从作为根同步站510f之下层级1分支同步站的设备510h、510i中的一者所发布的PSF获悉这个。

[0202] 但是，因为设备510d没有监听到范围内任何更适于作为层级1分支同步站的设备，所以其开始发布PSF，该PSF通告根同步站510f所指示的可用性窗口的调度、通告其在层级1中的位置、以及报告其自身的优先值和设备510f的优先值。

[0203] 可能已经作为层级1分支同步站的设备510d的近距范围内的其他设备会监听到设备510d并且停止作为层级1分支同步站发布PSF，因为设备510d具有第二高的主设备优先值，只有根同步站510f超过了它，并且因为使它们必须停止作为主设备的更好主设备阈值数量为1。在所示环境中，因为分级结构的最大深度为2(即层级0和1)，所以在层级2不会有任何主设备。

[0204] 设备510a、510b、510c、510e将作为叶子设备(它们都不能作为主设备)保持同步到设备510d，并且将遵循设备510f颁布并且现在被设备510d通告的新的可用性窗口调度。在本发明的所示实施例中，设备510a、510b、510c、510e不监听远距范围设备，因为它们都不是根同步站，并且因此它们不直接与设备510f同步。在其他其中它们监听最佳远距范围同步站的实施例中，它们可以直接与设备510f同步。

[0205] 设备510j已经与作为级别1分支同步站的设备510h同步。因为设备510h不监听远距范围设备(其不是根同步站)，所以它没有监听到设备510d，并且因此它可以仍然是设备510j的近距范围内最佳级别1分支同步站候选者。如果是这样，则设备510j保持与设备510h同步。

[0206] 这使设备510g成为没有监听到阈值数量的层级1分支同步站的唯一设备。因为它不是根同步站，所以它仍然只监听近距范围设备。因此，它将保持与设备510f同步，并且开始发送与设备510d的PSF类似的PSF，将其自身放置在层级1中并且通告其主设备优先值。

[0207] 图5D根据本发明一些实施例示出了通过合并图5B所示的两个分开的分级结构而形成的分级结构。

[0208] 在选择总体根同步站之后，同一分级结构中的所有同步站通告相同的可用性窗口调度和序列。因此，同步到同一分级结构内的一个主设备而非另一主设备并不会产生多大区别。但是，设备必须遵从任何适用的配置参数(例如分级结构的最大深度、给定范围内同步站的最大数量)。

[0209] 如图5A至5D中所示，在本发明的一些实施例中，对等设备首先将它们自身组织到近距范围分级结构中。此后不久，这些局部集群合并为单个默认的被同步环境。在所示实施例中，仅近距范围根同步站查看(或监听)超过近距范围，并且因此只有少量设备需要从与一个设备同步改变为与另一设备同步。在其中更多(或所有)设备进一步向外看的另一实施例中，更多设备会可能将同步从其局部或近距范围主设备改变到远距范围主设备。

[0210] 当近距范围处的根同步站查看超过近距范围时，基于其主设备优先值，其可以改变层级，或者可以保持在同一级别。根同步站之下的分支同步站同样可以改变级别。例如，在提供足够深度的环境中，如果近距范围根同步站在其在更长范围竞争之后降级，则其分支同步站可以自动地被降级相同数量的级别，以便保持相关组织。

[0211] 但是，作为此的一种替代形式，在近距范围根同步站的新层级被确定之后，其分支同步站可以重新开始该选择过程，以确定近距范围同步站下方的近距范围分级结构。

[0212] 在本发明的一些实施例中，对等设备不能随意地提名自身(例如通过发布PSF)作为分级结构任何级别处的同步站。当设备监听到同步站时，与该站的层级S无关，并且假设同步站具有高于该设备的主设备优先值，该设备可以成为该设备之下的叶子，或者如果它没有监听到阈值数量的较低级别层级S+1分支同步站，则其可以成为级别S+1处的分支同步站。

[0213] 图6是根据本发明一些实施例展示一种在对等通信环境内在默认分级结构中选择一个或多个同步站的方法的流程图。所示方法可以在每个可用性窗口之前、期间或之后、在所有可用性窗口的某个子组之后(例如在同步站的指定序列中第一或最后一个窗口之后)、在可用性窗口的某个倍数之后(例如在每两个窗口之后)或者按其他某种规律性执行，并且不同于图5A至5D所示的选择过程。图6中所示的过程利用多个范围，其可以对应于、也可以不对应于上面所讨论的近距、中距和远距范围。

[0214] 在图6所示流程图中所反映的本发明的实施例中，叶子(或从)设备将与其以比对应于被称为“closeLeaf”的范围的信号强度更大的信号强度监听到的最佳同步站同步。分支同步站将与其在对应于另一信号强度的“closeMaster”范围内监听到的最佳同步站同步；该站可以是根同步站。

[0215] 进行比较，closeMaster范围大于closeLeaf范围，这意味着与closeLeaf范围关联的信号强度阈值高于与closeMaster范围关联的信号强度阈值。这促进叶子设备的局部聚集，而分支同步站能够与更远的更好分支同步站(或者可能是根同步站)同步。

[0216] “远距”范围可以被用于代表任何设备将监听的最远距离。因此，“远距”范围大于closeLeaf和closeMaster范围二者，而相应的信号强度低于与那些范围相对应的信号强度。

[0217] 在所示过程中，如果给定设备在closeLeaf范围处(如果该设备是叶子)或者在closeMaster范围处(如果该设备是主设备)监听到的最佳对等设备是该设备自身，则它将与其在远距范围处监听到的最佳主设备同步。在一些具体实施中，每个设备将保持跟踪其在远距范围处以及在closeLeaf或closeMaster范围(无论哪一个适当)处监听到的最佳同步站，并且将(例如在存储器中)存储它们的同步参数和主设备优先值。

[0218] 除了用于辨识给定设备应该与哪个同步站同步的上述三个范围之外，可以使用其他范围来帮助确定所述给定设备角色是作为同步站(或主设备)还是作为叶子、或者其是否应当继续竞争作为同步站。例如，设备可以跟踪其在两个范围(被称为shortRange和midRange)内监听到的同步站的数量。

[0219] 在一示例性的具体实施中，shortRange可为大约1米，closeLeaf和closeMaster范围可为大约4米和5米，midRange可以在5到10米之间，而远距范围可为大约30米。在本发明的其他实施例中，主设备选择过程可以考虑更少的或附加的范围，其实际上可以延伸任何距离并且其可以对应于变化的信号强度。

[0220] 因此，可以使用一组范围(例如closeLeaf、closeMaster、midLeaf、midMaster、远距)来确定给定设备将与什么主设备同步。另一组范围(例如shortRange、midRange)可以被用于辨识设备的角色。

[0221] 在操作604中，设备确定其最近是否已经从其所同步的同步站接收到同步帧(例如PSF、MIF)。如果在最近的PSF周期内或者在其他某个可应用的时间周期(例如可用性窗口周期)内已经接收到同步帧，则方法前进到操作610；否则，方法在操作606继续。

[0222] 在操作606中，设备确定是否已经经过了阈值数量的可用性窗口或可用性窗口时间周期(或其他可应用的时间周期)而没有接收到同步帧。如果是，则方法在操作608继续；否则，设备保存其当前状态和当前同步，并且退出所示方法而不执行主设备选择过程。虽然不需要进行显著的校正动作(因为丢失的PSF的数量还没有达到阈值)，但是设备最近还没有同步，并且可能不具有当前主设备优先值来用于选择同步站。

[0223] 在操作608中，设备成为对等设备的分级结构的根同步站，但是可以保持先前根同步站的可用性窗口序列或调度以及PSF周期性，除非其与该设备的其他操作冲突。替换任何同步站(包括根同步站)时的目标是在环境内保持同步；因此，如果可能的话，优选是以相同同步参数继续。在操作608之后，主设备选择过程对于设备结束。

[0224] 在操作610中，设备开始执行可应用的主设备选择算法，利用其已经经由同步帧(例如PSF、MIF)接收到的和/或从其他设备(例如其当前未同步到的同步站)监听到的或者已经被其他设备转播的优先值(或选择量度)。特别地，设备将把其主设备优先值与其他设备的主设备优先值进行比较。

[0225] 如上所述，可以在不同范围处检查同步站。在这些实施例中，从同步站候选者接收到的同步帧的RSSI(接收信号强度指示)、或者其他设备的信号的强度的其他某种测量(诸如RCPI(接收信道功率指示))可以被用于确定它们的范围。

[0226] 作为操作610的一部分，设备计算与设备执行图6所示方法相关的几个值，包括下列值(范围如上所述)：

[0227]

[0228] 在本发明的一些实施例中，在比较主设备优先值时，设备将把其自身与其可以监听到的一个或多个其他设备中的每一个进行比较，并且利用下列规则将其自身与它们相比来排名。

[0229] 规则1：如果该设备是根同步站而其他设备在根的树中(反之亦然)，或者如果该设备是叶子而其他设备是该设备的当前同步站(反之亦然)，则比较它们的主设备优先值。具有较高优先值的设备胜出并且排名较高；如果相等，则比较它们的MAC地址，并且较高的(或较低的)MAC地址胜出。

[0230] 规则2：如果规则1不适用，并且没有设备是根同步站，但是它们在同一个树中，则比较依赖于它们的层级。如果它们在不同的层级中，则位于编号较低(即更接近根)的层级中的设备胜出。如果它们在同一层级中，则具有较高主设备优先值的设备胜出；如果相等，则比较它们的MAC地址。

[0231] 规则3：如果设备位于不同分级结构中(即它们不具有相同的根同步站)，则比较它们的根同步站的主设备优先值。根同步站具有较高优先值的设备胜出；如果相等，则比较它们的MAC地址或者它们的根同步站的MAC地址。

[0232] 规则1和2促进同步分级结构的稳定性，同时一般建立从给定设备到分级结构的根同步站的最短路径。规则3确保相互邻近的两个单独的分级结构有机会合并为单个分级结构。

[0233] 在进行操作610的同时，实施所示方法的设备考虑由其他设备所通告的默认和组辨识符，并且可以忽略通告与其自身的默认辨识符不同的默认辨识符的设备。如上所介绍的那样，默认辨识符辨识较大的对等设备分级结构，而组辨识符辨识较小的对等实体分级结构。

[0234] 如在下一章节中所描述的那样，执行用于辨识或选择同步站的过程的设备也可以忽略通告不同组辨识符的设备，除非该设备是其私有组的根同步站。更具体地，组的成员一般可以执行与图6所示选择过程类似的选择过程，但是只考虑属于该组的设备，而组根同步站可以然后执行所示方法来与默认分级结构同步。

[0235] 在操作612中，设备确定其是否是bestFarMaster(即是否具有该设备的远距范围内的所有设备中最高的主设备优先级)。如果是，则方法返回到操作608；否则，方法前进到操作614。

[0236] 在操作614中，设备确定numHigherM(即midRange内具有较高主设备优先级的同步站的数量)是否少于midRange同步站的阈值或最大数量(maxM)，以及numHigherS(即shortRange内具有较高主设备优先级的同步站的数量)是否少于shortRange同步站的阈值或最大数量(maxS)。如果是，则方法前进到操作630；否则，方法在操作620继续。

[0237] 在本发明的一些实施例中，如果numHigherM小于maxM或numHigherS

[0238] 在操作620中，设备将自身指定为叶子，因为即使其具有高于一些其他设备的主设备优先值，shortRange内阈值数量的具有较高值的同步站已经就位。如果设备已经发布周期性同步帧，则其停止。

[0239] 在操作622中，设备确定其是否是closeLeaf范围内的最佳设备(即closeLeaf范围内的最佳候选者)。如果是，则方法前进到操作640；否则，其在操作624继续。

[0240] 在操作624中，设备与bestCloseLeaf(即closeLeaf范围内具有最高主设备优先值的同步站)同步。然后，方法结束。

[0241] 在操作630中，设备担当同步站的角色。这将要求其发布周期性同步帧并且管理可用性窗口序列来同步其他对等设备。

[0242] 在操作632中，设备确定其是否是closeMaster范围处的最佳设备(即closeMaster范围内具有最高主设备优先值的设备)。如果是，则方法前进到操作640；否则，在操作634处继续。

[0243] 在操作634中，设备与bestCloseMaster(即closeMaster范围内的最佳同步站)同步。然后，方法结束。

[0244] 在操作640中，设备与bestFarMaster(即远距范围内具有最高主设备优先值的设备)同步，bestFarMaster可以是根同步站。然后，方法结束。

[0245] 图7A至7E示出了根据本发明一些实施例的图6所示主设备选择过程的执行。

[0246] 图7A示出了分布在环境内的对等设备的集合。设备标记指示设备的按其主设备优先值(并且如果两个设备的量度相当，则还有其MAC地址)的倒序的排名，其中设备710a<设备710b<设备710c<…<设备710i<设备710j。因此，环境内的所有设备中，设备
710j具有最高的主设备优先值，并且被认为是环境中的“最佳”设备。

[0247] 如上所述，多个不同范围对同步站的选择和设备的同步是重要的。在图7A至7E中示出了用于顶端三个设备(设备710h、710i、710j)的“远距”范围的极限，连同标尺702展示了一个示例性的“近距”范围。在所示实施例中，(如上面参考图6所述的)closeLeaf和closeMaster范围是相等的，并且匹配标尺702所表示的近距范围。

[0248] 图7B示出了在每个设备与其可以监听到的最近同步站同步(例如在操作634中)时建立的近距范围连接。在所示场景中，大多数设备位于顶端三个设备中的一者的近距范围内，并且因此与这些设备中的一者同步。但是，设备710c、710d在近距范围内没有发现其他设备，并且因此暂时继续未同步(即在其自身的单设备分级结构中)。

[0249] 可以注意到，一些设备(例如设备710b、710e、710f)可以监听到比它们初始与之同步的那些同步站更好的同步站，但是当前正寻找最接近的同步站，而不是它们可以监听到的最佳同步站。此外，所有设备可以仍然正在发送同步帧，因为还没有任何设备发现成为叶子的理由。

[0250] 图7C示出了当同步站监听并连接到远距范围处的更好同步站时的环境。例如，根据图6中所示的方法，设备710c、710d、710i在操作630处成为同步站，在操作632中发现它们是近距范围内的最佳同步站，然后执行操作640，其中它们与远距范围内的最佳同步站同步。因此，设备710i与设备710j同步，而设备710c、710d与设备710i同步。

[0251] 此外，一些设备现在变换到叶子状态，因为它们在近距和/或中距范围监听到阈值数量的具有更好选择优先值的同步站。例如，如下根据图6中所示的方法，设备710a、710b(和/或其他设备)到达操作614，并且确定它们在短距范围和在中距范围监听到多少主设备。这些值中的一者或二者等于或超过它们的阈值，并且因此设备执行操作620、622和624来成为同步到closeLeaf范围内最佳同步站的叶子。示例性地，短距范围和中距范围二者都是长于近距范围，但是短于远距范围的距离。

[0252] 设备710a、710b和710f的虚线表示它们现在是叶子设备。作为叶子，它们停止发布周期性同步帧。

[0253] 还参考图7C，非叶子设备开始或继续发布同步帧，该同步帧通告其主设备优先值及其根同步站的优先值。例如，设备710e将通告设备710e和710h的优先值，而设备710g将通告设备710g和710j的优先值。

[0254] 图7D示出了在设备710g物理地移动到离设备710e更近、但是仍然超出设备710h的远距范围之后的环境。特别地，设备710g移动到设备710e的近距范围内。

[0255] 经由其同步帧，设备710g通告其主设备优先值和设备710j的优先值。当作为主设备选择过程的一部分，设备710e比较这些值时，将注意到设备710j优先于设备710h。因此，设备710e现在将与设备710g同步。

[0256] 在图7E中，设备710e已经开始发布通告其优先值及其新的根同步站(设备710j)的优先值的同步帧。设备710h将把设备710j的主设备优先值与它自身的进行比较，并且知道设备710j是优选的根。

[0257] 如果如图7E中所示，分级结构的最大深度参数允许的话，设备710h因此可以与设备710j的延伸的分级结构同步。如果设备710e位于分级结构的最大深度处，则设备710h可以与设备710e同步，但是只能作为叶子。如果设备710g已经在最大深度处，则设备710e只可能已经是叶子，并且如果没有其他对等实体在范围内，则设备710h可以开始其自身的分级结构。

[0258] 在本发明的一些实施例中，主设备选择算法或过程是持续的。在这些实施例中，该过程随着每个可用性窗口而重新开始或重复，并且因此可能需要一些时间才能使所有设备在分级结构中位于其“正确”的级别。随着设备移动进入环境、在环境内移动、以及移动离开环境，分级结构可以不断地改变。

[0259] 但是，应当指出的是，设备同步发生得更迅速得多，并且不会被持续的主设备选择过程劣化。也就是说，同步不依赖于使每个设备位于其正确的逻辑位置中。

[0260] 特别地，即使作为分级结构的根同步站和分支同步站的设备可能随着时间而变化，在大多数具体实施中这也不会中断同步。在这些具体实施中，相同的可用性窗口调度应用在整个分级结构中；因此，任何新担当根同步站角色(或分支同步站角色)的设备将已经与其它设备同步，并且这些其它设备将与其同步。

[0261] 在本发明的一些实施例中，用于计算设备的主设备优先值的选择量度包括其传输范围和功率级。作为一个简单的实例，具有较高传输功率或范围的设备相对于具有更小传输功率/范围的所有设备将具有作为同步站的优先级。随着设备的功率储备减少，其优先值同样将降低。在其它实施例中，可以考虑其它量度。

[0262] 在这些实施例中，如果传输功率/范围不可用(或者如果在设备之间相当)，则具有最多剩余电池电荷的设备将具有较高的优先值。如果传输范围和电池电荷二者都是未知的(或相当的)，则可以比较设备的MAC地址(或其它地址/辨识符)。

[0263] 因为在这些实施例中，主设备或同步站的选择是连续的或定期的过程，所以在不同对等实体之间分担作为同步站的成本(例如功率使用)。当一个站的功率级降低(例如由于定期发布周期性同步帧)时，另一设备将取代其位置。

[0264] 在其它实施例中，可以考虑其它量度。如前面所述，这些主设备选择量度、和/或表示量度组合的简单主设备优先值在设备广播同步帧时被设备广播。

[0265] 私有组

[0266] 在本发明的一些实施例中，默认分级结构(或不同默认分级结构)的两个或更多个成员可以形成组来进行文件传输、玩游戏或者进行其他某种活动。通过组织为组，成员可以受益于较高的带宽、较低的延迟、更少的争用、和/或其它合作优势。例如，两个(或更多个)设备可以创建私有组来进行增强数据率会话以交换数据。

[0267] 如在前一章节中所述，设备在其广播的同步帧(例如PSF、MIF)内可以广播多个辨识符，诸如设备现在或先前同步到的分级结构的“默认”辨识符以及设备所属于的组的“组”辨识符。在本发明的一些实施例中，所有分级结构采用相同的默认辨识符(诸如0)，以反映正常的对等操作。在多个默认分级结构附近的设备可以简单地加入通告更好根同步站或顶部主设备的那个。因此，在不同分级结构之间使用相同的默认辨识符并不导致冲突。

[0268] 在本发明该实施例的一些具体实施中，不能或者不与典型的默认分级结构保持同步的设备通告非零默认辨识符。必须与基础结构信标(例如接入点)保持对齐的主设备是通告非零默认辨识符的设备的一个示例。

[0269] 可以通过执行预定算法，根据基础结构信标的BSSID(基本服务集辨识符)来得到这样的主设备的非零默认辨识符。与基础结构信标同步的主设备可以属于也可以不属于组，并且可以只能够与其他与相同信标对齐的设备同步。

[0270] 组辨识符0或者没有组辨识符就可以辨识当前不参与任何组的设备。大于0的值可以被保留给活动组使用。在不同具体实施中，组辨识符可以具有不同的量值(例如16位，32位)。

[0271] 在本发明的实施例中，被采用作为组辨识符的具体值由将在组成员之间公共地执TM TM行的应用或服务(例如AirPrint 、App Game Kit 应用、文件共享实用程序)、或者支持该应用的较高级别协议层来选择，可能是随机地选择。应用将组成员辨识到较低级别协议层(例如通过MAC地址或其他辨识符)，并且在成员之间分发组辨识符。

[0272] 在本发明的一些实施例中，默认和组辨识符对“0/0”用于辨识空闲设备，空闲设备可以被定义为在默认分级结构内同步但是在组内部不活动，并且因此不参与活动的数据会话的设备。空闲设备将简单地操作发现协议、其他寻址和路由协议等。如果以及当两个或更多个设备选择以某种方式(例如通过共享数据或应用)协作时，它们将创建或加入组。

[0273] 属于同一组的设备将在它们之间同步以形成组分级结构，类似于上面对于同步整个默认组结构所述的方式。只要设备保持在组中，它们就将保持相互同步。

[0274] 根据组内设备的数量以及任何其他可应用的参数，组的一些成员可以是组根同步站(即组的根同步站，也被称为顶部组主设备)之下的分支同步站，其中所有其他成员是叶子(或从设备)。组成员可以继续执行用于选择或辨识主设备或同步站的过程，但是它们在组中的成员身份将调整该过程，使得它们只考虑选择组成员作为同步站，并且由此建立组分级结构。所选的组根同步站将横跨组和默认分级结构之间的界限，并且如所指出的那样，试图与默认分级结构同步。因此，与在组分级结构中活动无关，设备通常都将只具有一个其同步到的或与之同步的主设备。

[0275] 在本发明的一些实施例中，为了同步的目的，组的每个成员顺次地考虑诸如如下的规则，直到找到并应用指定其应该如何同步(例如应该同步到谁)的规则。类似于上面对于默认分级结构所述的参数(例如同步站的最大数量、特定范围内同步站的数量)，组成员在确定其是否应当作为同步站时可以考虑多个因素或参数。

[0276] 规则1：组设备与近距范围内(不是其自身)同时也是同一组的成员(即通告相同组辨识符)的最佳设备同步。该设备将要么是组根同步站，要么是组分支同步站。

[0277] 规则2：如果设备是近距范围内同时也是该组的成员的最佳设备，则其与远距范围内(不是其自身)同时也是该组的成员的最佳设备同步。

[0278] 规则3：如果设备是远距范围内同时也是该组的成员的最佳设备，则其担当组根同步站的角色，并且与近距范围处(不是其自身)通告相同默认辨识符(例如0)、并且因此是同一默认分级结构的一部分、并且要么不通告组辨识符要么通告另一组辨识符的最佳同步站同步。但是，在一些具体实施中，组根同步站不会与在另一组中活动的同步站同步。

[0279] 规则4：如果设备是组根同步站，也是默认分级结构内近距范围处的最佳同步站，则其将与远距范围处同时也是同一默认分级结构的成员的最佳同步站同步。

[0280] 规则5：如果设备是组根同步站，也是默认分级结构内远距范围处的最佳同步站，则其是组和默认分级结构二者的根同步站，并且不同步到任何其它设备。其将保持其在应用这些规则之前所工作于的同步参数，并且在其发布的任何同步帧中通告它们。

[0281] 组分级结构内通告的同步参数可以与默认分级结构的同步参数类似或相同。特别地，可用性窗口可以被调度用于相同时间、具有相同持续时间、在相同或不同的通信信道上。

[0282] 可用性窗口调度的该同步可以自然地发生，因为组的成员可以源自同一默认分级结构，并且因此先前已经在共同的一组同步参数下同步。此外，当组的根同步站同步到默认分级结构时，其将从其同步到的同步站得到其组同步参数，这将是默认分级结构的同步参数。

[0283] 但是，组根同步站的所公布的可用性窗口调度可以被配置为避免拥塞的通信信道，可以使用5GHz频带中的信道(如果所有成员设备都能够使用该频带的话)，可以在必要的情况下调整其可用性窗口参数(例如长度、周期)以避免干扰成员设备所共享的应用或服务，和/或考虑其他因素。因此，在不同环境或不同具体实施中，组的同步参数可以与相邻默认分级结构的同步参数相同，也可以在任何程度上不同。

[0284] 当组解散时，成员可以初始地保持同步到其已经与之同步的组同步站。每个组同步站要么直接同步到分级结构(在组根同步站的情况下)，要么与组根同步站同步。因为组根同步站与分级结构同步，所以其通告该分级结构的根同步站的同步参数。通过与组根同步站同步，因此组成员可以已经与分级结构同步。当成员离开组并且重新开始执行主设备选择算法时，它们将再次考虑默认分级结构中的所有主设备用于可能的同步，而不仅仅是组同步站。

[0285] 在本发明的一些实施例中，打开用于组操作的应用的第一设备设置私有辨识符，并且开始通告组(例如经由周期性同步帧和/或主指示帧)。组的本质或目的可以在相同通信中作为私有辨识符来辨识，可以经由发现或服务协议来确定，或者可以以其他某种方式来获悉。

[0286] 虽然从设备或叶子设备在分级结构内通常是沉默的(即不发布同步帧)，但是其可以在其于可用性窗口期间广播的主指示帧内通告私有组。该通告可以经由支持联网或多TM用户社交应用(诸如The Game Creators的App Game Kit )或者其他某种游戏或内容共享应用的特定应用级协议来传送。当其他设备接触第一设备时，该应用接收并接受它们的加入请求。

[0287] 设备通过将其私有辨识符设置为匹配组的辨识符并且通过与组同步站同步，来加入组。因此，其出席其与之同步的组主设备所通告的可用性窗口。

[0288] 图9A至9B根据本发明的一些实施例示出了分级地组织的对等设备环境内私有组的创建。

[0289] 在这些附图中，按照主设备优先值的顺序来标记设备910a至910m，使得设备910a>设备910b>设备910c>…>设备910m。示例性设备910e的表示被放大；如放大中所示，设备标号下方的数对以x/y的形式辨识设备的默认和组辨识符，其中x是默认辨识符，而y是组辨识符。标尺902示出了环境中等于近距范围的距离。

[0290] 在图9A中，对等设备的集合被组织到两个分级结构中，一个的根位于设备910a处，另一个的根位于设备910c处。所有设备当前都空闲，如其默认和组辨识符对0/0所指示的。

[0291] 可以注意到，为其示出了近距范围极限的设备910g已经与根在910c处的树而不是与根在设备910a处的树同步，即使其在设备910f、910j的近距范围内，设备910f、910j中任一者或者二者会通告高于设备910i所通告的主设备优先值(关于设备910c)的主设备优先值(关于设备910a)。

[0292] 这可以例如在设备910f和910j二者都不能作为同步站(可能是因为协议所指定的最大分级结构深度被实施)的情况下发生。在该具体实施中，分级结构的最大深度是指根同步站与最远叶子设备之间的最大跳转数量。因此，在最大深度为3的情况下，会最多有3个级别的主设备(层级0处的一个根同步站以及层级1和2处的分支同步站)，然后是一层叶子设备。换言之，分级结构的最大深度可以辨识可以找到同步站的层级或级别的最大数量，并且叶子设备可以在那些层级(除了根层级0)和一个附加层级中被找到。

[0293] 在图9A的环境中，如果设备910g、910h、910i和910j选择交换数据(例如玩游戏或共享文档)，则它们将实施另一组辨识符，例如1。通过使用可应用的规则和适当的选择过程(例如在前一章节中所述的过程)，这些设备将选择设备910g作为组的根同步站，因为它具有这些设备中最佳主设备优先值。

[0294] 在一个示例性具体实施中，在第一设备打开具有多玩家特性的游戏应用时开始创建组。游戏可以使用 协议或其他方式来随同组辨识符一起通告游戏实例的可用性。因此向其他潜在玩家的设备通知如果它们想加入的话，它们应该相应地改变其组辨识符。

[0295] 图9B示出了在私有组已经采用组辨识符1并且在它们之间已经同步之后图9A所示的环境和设备。设备910h、910i和910j已经与其组根同步站(设备910g)同步(例如如上面的规则1(或2)所要求的那样)，并且设备910g已经与作为远距范围内最佳默认分级结构主设备的设备910c同步(例如如上面规则4所要求的那样)。

[0296] 设备910g将发布定期同步帧(例如PSF)来保持组成员同步，并且还将出席设备910c所通告的可用性窗口，以保持与设备910c的分级结构同步。通过调度其可用性窗口中一个或多个来匹配设备910c所通告的调度，设备910g还可以将设备910h和910i与根在设备910c处的分级结构同步。

[0297] 在图9B所示的环境中，设备910m可以在组1活动期间保持与设备910h同步，因为设备910h是近距范围内具有相同默认辨识符的最佳主设备。当私有组解散时，组的各个设备将重新开始正常地执行其主设备选择算法，并且如果环境中的对等设备还没有改变位置，则设备配置可以返回到图9A中所示，或者返回到类似配置。

[0298] 在本发明的一些实施例中，组具有其自身的最大分级结构深度，并且该最大组深度可以被应用以延伸默认分级结构的最大分级结构深度(例如当组的根同步站与作为默认分级结构的成员的非组设备同步时)。例如，参考图9B，假设设备910d具有的主设备优先值高于设备910c(或者假设它们交换位置)，并且它们二者都在组根同步站910g的远距范围内但是不在近距范围内。以上同步规则会决定设备910g与设备910d同步，但是这通常会因为默认分级结构的最大深度(即，3)而被禁止。

[0299] 但是，在本发明的这些实施例中，默认最大深度延伸组的最大深度参数。因此，如果图9B中所示的最大默认分级结构深度为3，并且如果最大组分级结构深度为2，则从默认根同步站到叶子设备的穿过至少一个组成员的最长路径是5。在该示例性场景中，设备910g可以例如与设备910d同步，并且最大路径距离于是会展示在默认根同步站910a与叶子设备910m之间(即910a→910b→910d→910g→910h→910m)。

[0300] 具有不同组辨识符但是操作相同应用的两个或更多个组可以合并。类似于分级结构内的同步过程，成员将同步在同时也是被结合的组的成员的最佳同步站之下，并且采用该站的组辨识符或可能为合并的组生成新的组辨识符。

[0301] 图10A至10C示出了根据本发明一些实施例的多个私有组的合并。在这些实施例中，设备可以正操作相同或兼容的应用以共享文件、玩游戏、使用共享资源等。例如，一个私有组的设备可以移动到距离正使用相同应用的另一私有组更近，并且较低等级协议层可以向较高层(例如应用)告知其他设备的可用性。应用可以将(也可以不将)那些设备添加到其组，这取决于其配置或施加在应用上的限制。

[0302] 在图10A中，设备按照其优先值的顺序来标记，其中设备1010a>设备1010b>…>设备1010e。设备1010a和1010b形成一个私有组，具有组辨识符1，而设备1010c、1010d和1010e形成具有组辨识符2的第二组。它们的组根同步站(即设备1010a、1010c)可以同步到相同分级结构或不同分级结构，并且甚至可以在默认分级结构内同步到同一设备。

[0303] 当这两个设备组移动得更近时，或者当根在设备1010c处的组中的设备检测到通告更好组根同步站的另一组时，这些组可以开始合并。关于是否合并操作公共应用、但具有不同组辨识符的多个组的决定由该应用来作出。如果它们合并，则它们中的一者丢弃其组辨识符，并且采用另一个的组辨识符。在两个不同组各自独立地采用相同组辨识符的情形中，如果以及当它们变为邻近时，则它们可以自动地合并。

[0304] 图10B示出了在设备1010d监听到设备1010b的同步帧之后图10A所示的设备。因为组根同步站1010a具有高于设备1010c的优先值，所以设备1010d采用该组的组辨识符，并且中断与设备1010c的同步。

[0305] 导致设备1010d改变组的设备1010b所发布的同步帧可以是在社交信道上发布的主指示帧(MIF)。在图10A至10C所示的本发明实施例中，设备被编程为偶尔调谐到社交信道，这允许它们监听到不是它们已经与之同步的那些设备的设备。在这种情况下，允许设备1010d监听到设备1010b所发布的MIF。

[0306] 在组或其他被同步设备组遵守的大多数可用性窗口期间，设备将在未广泛使用的信道(例如并非社交信道)上会合。但是，在一些可用性窗口(例如在64个可用性窗口的序列中序列号为0、15、31和47的那些可用性窗口)期间，会合发生在社交信道上。因此，虽然因为两个分开的组将其大多数时间花费在不同(非社交)信道上，设备1010d通常不会监听到设备1010b，但是一个或多个社交信道上的周期性MIF广播允许设备获悉其自身的被同步设备集群之外的设备。

[0307] 图10C示出了在设备1010c、1010e监听到通告组1和设备1010a的主设备优先值的设备1010d之后的环境。它们还丢弃组2，并且与该组同步。

[0308] 在图10A至10C所示的本发明实施例中，合并使用公共应用的两个分开的组的过程可以涉及更多交互。在该实施例中，当这两个组首先进入范围中，使得这两个组中的一者中的设备可以监听到另一组中的设备时，这两个组的设备将首先在其公共默认分级结构内同步。这将它们二者放到可用性窗口的相同调度上，这就允许它们容易发现彼此及其服务(例如它们现在可以运行Bonjour协议)。例如，因为它们现在正在应用相同的可用性窗口调度，所以它们将在相同社交信道上周期性地会合(例如至少在可用性窗口序列号0期间)。

[0309] 经由在这些周期性社交会合期间所发布的MIF和/或Bonjour帧，设备1010d(和/或其他设备)将检测其相对于正在使用相同应用但是具有不同组辨识符的对等设备的接近度，反之亦然。在这些设备上，公共应用(或某个实用软件或通信协议的上层)将决定组辨识符中的一者必须被丢弃，从而这两个组的设备可以一起工作。

[0310] 假设组2被丢弃，则设备1010d将采用组辨识符1，并且应用用于与组同步的一组规则，诸如上面所述的那些规则。上面的规则1会使设备1010d与设备1010b同步，因为其是近距范围中最佳组设备或同步站。

[0311] 设备1010c、1010e然后将获悉另一组(例如经由社交信道上在可用性窗口期间的MIF，或者经由Bonjour)，将用组辨识符2交换组辨识符1，并且将应用可应用的组同步规则。同步规则(诸如上面所述的那些同步规则)的集合可以指示设备1010e应当与设备1010c同步(例如根据规则1)。但是，用于该情景的有效规则集合可以将更多权重和重点给予与分级结构中处于较低层级(即更接近根)的设备同步。因此，因为设备1010d位于层级1并且在近距范围内，而设备1010c位于层级2，所以设备1010e将选择设备1010d作为其主设备。

[0312] 在本发明的一些实施例中，设备所应用的配置参数和/或设备行为在私有组被创建、维持或解散时可以改变。例如，最大分级结构深度参数可以被覆写，以允许组的成员经由其组根同步站与分级结构同步，即使该参数否则会阻止一些或所有组成员保持与分级结构的同步。

[0313] 如上所述，当组形成时，附加最大“组”分级结构深度可以被添加到默认分级结构的最大深度。距离组内设备的默认根同步站的，或者距离不是组成员但是通过组成员与默认分级结构同步的设备的默认根同步站的跳转最大数量等于这两个深度参数之和。

[0314] 又如，已经在默认分级结构中作为叶子并且因此没有广播同步帧的设备可以这样做，如果以及当其成为私有组的成员时。该改变的行为可以只是暂时的，并且可以允许组包括否则不会获悉它的设备。此外，并且如已经讨论的那样，在组内选择主设备的过程可以不同于、并且可以覆写设备在其不是私有组一部分时执行的“正常”主设备选择过程。

[0315] 对等设备

[0316] 图8是根据本发明一些实施例的一种对等通信设备的框图。在图8中示出了两个基本协议层或操作层：逻辑链路层和数据链路层。在逻辑链路层之上，一个或多个应用和/或实用程序(例如mDNS，Bonjour)可以工作；在数据链路层之下是物理层，负责通过传输介质传输帧以及从传输介质接收帧。

[0317] 在本发明的一些实施例中，逻辑链路层和数据链路层可以由分开的处理器或者由位于单个部件上的集成电路来物理地实现。在图8所示的示例性通信设备中，出于清楚展示的原因省略了设备的一些部件，诸如处理器、存储器、显示器、天线和通信端口部件等等。

[0318] 在数据链路层内，同步帧(例如周期性同步帧或PSF、主指示帧或MIF)被同步状态机810发布和/或接收。输入的同步帧被路由到主设备数据库820，并且然后向上传递到逻辑链路层。数据帧被分组队列822处理。

[0319] 在一些具体实施中，同步状态机810具有两个模式(叶子和主设备)并且连续运行。如早前所讨论的那样，主设备(也被称为同步站)是发布周期性同步帧的设备，而叶子设备不发布周期性同步帧，但是与主设备同步。

[0320] 状态机负责将对等设备同步到其当前的同步站(例如，如果设备是叶子的话)。如果设备是主设备，则状态机810管理其对周期性同步帧和/或主指示帧的传输，并且还管理其可用性窗口存在。

[0321] 扫描状态机812针对周期性同步帧而扫描社交信道。无线电信道管理器814管理与其它实体(例如基础结构模块)的以及不同无线电部件(例如Wi-Fi、蓝牙)之间的无线电资源(例如共享的天线)。同步状态机810与无线电信道管理器814交互，以在适当的时间将设备的无线电部件切换到正确信道用于可用性窗口。为了其他目的(例如扫描信道以寻找新设备)，扫描状态机812和/或设备的其他部件可以与无线电信道管理器交互。

[0322] 对等高速缓存816存储主机对等设备正在与之通信或者将要与之通信的有限数量的其他设备的相关信息。该高速缓存的使用可以帮助缓解在一些硬件/固件具体实施中与存储器限制关联的问题。例如，数据链路层可以由专用Wi-Fi芯片组实现，其通常不具有对大存储体的访问权限。对等高速缓存816中的信息与对等数据库836中的信息同步。

[0323] 主设备选择代码818被周期性地执行，以利用来自对等数据库836的信息和/或其他信息，执行用于选择或辨识同步站的选择过程。例如，该代码的执行可以导致基于主设备数据库820中的设备作为主设备的适用性来对这些设备排名。

[0324] 主设备数据库820存储关于对等设备知道的所有主设备的数据。这样的数据可以被用于同步和/或主设备选择，并且可以包括但不限于RSSI(例如最新帧的RSSI、多个帧的平均值、最小值、最大值)、主设备优先值、选择量度和同步参数。

[0325] 在本发明的一些实施例中，主设备数据库820被填充或更新，并且主设备选择代码818在接收到每个周期性同步帧时执行。

[0326] 数据链路层的分组队列822存储输入和/或输出的数据帧。逻辑链路层的分组队列832存储从其他设备输入的以及输出到其他设备的对等业务。

[0327] 分组调度器830调度到被同步设备的多播、广播和单播业务，以及到对等实体没有与之同步的主设备(“未同步主设备”)和到与未同步主设备同步的设备的带外查询/响应。对等数据库存储关于未同步主设备的可用性窗口的信息、存在模式以及其他计时相关信息。

[0328] 存在模式管理器834基于可以包括但不限于如下因素的因素来控制对等设备的存在模式：到被同步设备的当前活动的数据链路、到那些设备的当前数据率、扫描要求、带外查询要求、功率管理状态、蓝牙要求、其他无线电要求等。

[0329] 对等数据库836辨识图8中所示的对等设备知道的所有设备，并且存储关于每个设备的信息。该信息可以包括但不限于：其根主设备、其他主设备、主设备选择量度、能力(例如支持的频带、信道带宽、调制/数据率)、存在模式、设备支持的服务、未完成块ACK协定等。对等数据库836因此可以通过提供可以按优先值排序的候选设备列表来协助主设备选择过程。

[0330] 应用界面838包括到较高系统层和模块的接口，其可以包括但不限于：配置和网络管理、GUI(图形用户界面)、服务通告和发现等等。GUI可以向设备使用者呈现周围对等实体的列表、它们的物理接近度、范围或信号强度、它们的服务列表、和/或其他信息。

[0331] 图8中所示的对等设备的配置是示例性的。在本发明的其他实施例中，对等设备的配置可以在不同程度上有所不同。例如，图8所示的对等设备的部件的功能可以以不同方式被组合，单个部件的功能可以被划分，并且/或者多个部件的功能可以被合并。

[0332] 在一些具体实施例中，对等设备包括应用处理器来支持应用(例如图8中位于较高层中的应用程序和实用程序)。应用处理器提供存储器管理、图形处理和/或应用需要的其他功能。这些实施例中的对等设备还包括用于执行无线通信的基带处理器、以及用于支持通信和通信处理的相应存储器和收发器。

[0333] 基带处理器可以包括在逻辑链路层和数据链路层中所示的所有部件以及结合这些部件所述的功能性。基带处理器还可以处理通常与物理层关联的一些任务(例如信道编码)。

[0334] 因此，在本发明的一些实施例中，对等设备的“通信模块”或“无线通信模块”可以指上面刚刚描述的稳健基带处理器。在其他一些实施例中，通信模块可以包括基带处理器和用于操作或管理设备的天线的相应收发器，并且还可能包括基带处理器使用的存储器。在再一些实施例中，通信模块可以包括图8所示的逻辑链路层和数据链路层的部件、以及向对等设备传输数据和从对等设备接收数据所必需的其他部件。

[0335] 本发明的一些实施例促进如本文所述的对等通信协议与要求对等设备的无线电部件或其他通信资源的其他应用的共存。例如，设备可以操作应用或另一协议，诸如[0336] 在这些实施例中，蓝牙通信可以根据需要执行，除了在设备的可用性窗口及其任何延伸期间之外。在可用性窗口之外，蓝牙扫描、查询和/或其他操作是允许的，并且遵循根据这里提供的协议甚至可以相对于数据帧具有优先级。

[0337] 主设备的周期性同步帧可能由于使用设备天线的蓝牙(或其他应用/协议)操作而被延迟，但是通常不将被丢弃。在带外查询和响应期间可以不允许蓝牙或其他操作。

[0338] 本文所提供的对等设备的同步和操作也可以与依赖于并非对等设备分级结构一部分的某种通信基础结构(例如接入点)的应用或协议共存。

[0339] 本发明一些实施例在其中执行的环境可以包含通用计算机或专用设备，诸如手持式计算机、智能电话或其他移动设备。为了清楚说明，可以省略这样的设备的细节(例如处理器、存储器、数据存储装置、显示器)。

[0340] 此具体实施方式中描述的数据结构和代码通常存储在计算机可读存储介质上，其可以是能够存储供计算机系统使用的代码和/或数据的任何设备或介质。计算机可读存储介质包括但不限于非易失性存储器、磁性和光学存储设备(如磁盘驱动器、磁带、CD(光盘)、DVD(数字通用光盘或数字视频光盘))，或能够存储现在已知或以后开发出的计算机可读介质的其他介质。

[0341] 具体实施方式部分中所述的方法和过程可实施为代码和/或数据，其可存储在如上所述的计算机可读存储介质中。当计算机系统读取并执行计算机可读存储介质上存储的代码和/或数据时，计算机系统执行具体化为数据结构和代码并存储于计算机可读存储介质内的方法和过程。

[0342] 此外，以下所述的方法和过程可以被包括在硬件模块中。例如，硬件模块可以包括但不限于专用集成电路(ASIC)芯片、现场可编程门阵列(FPGA)和现在已知或未来开发的其他可编程逻辑器件。当硬件模块被启动时，硬件模块执行被包括在硬件模块内的方法和过程。

[0343] 前面对本发明实施例的描述仅仅是为了示例性和描述性的目的而提供的。它们并非意图是穷尽性的，也并非意图要将本发明限制到所公开的形式。因此，对于本领域熟练的从业者而言许多修改和变型将是显而易见的。本发明的范围由所附权利要求而非由前面的公开内容限定。