BLEX：蓝牙低功耗灵活多连接调度

1 引言

蓝牙是当今已深入我们日常生活的低功耗无线技术的代表。蓝牙专项兴趣小组（SIG），即蓝牙标准组织，预计每年将出货11.4亿台蓝牙设备，并且到 2024[2]年，每年将出货21亿台配备蓝牙功能的手机、平板电脑和个人电脑。此外，随着物联网（IoT）的发展，同时使用多个蓝牙设备的情况越来越普遍。例如，任何使用平板电脑的人可以一边用蓝牙键盘输入、用蓝牙鼠标（或蓝牙触控板）点击操作，一边通过蓝牙耳机听音乐。人们还经常将智能手机作为蓝牙中心，连接多个蓝牙外设，例如智能手表和耳机。

蓝牙技术在过去二十年中取得了显著发展。具体而言，2010年定义的蓝牙4.0规范引入了蓝牙低功耗（BLE），在保留经典蓝牙大部分优势的同时增强了低功耗特性，但不包括高吞吐量。蓝牙技术联盟最初将蓝牙低功耗设计用于低流量应用程序，但随后逐步演进以支持更高的流量。2014年的蓝牙4.2规范将蓝牙低功耗的数据包长度扩展至251字节，2016年的蓝牙5.0规范将其数据速率提升至2 Mbps。随着蓝牙低功耗带宽的大幅提升，其应用也日益多样化，包括

那些产生高流量的设备。例如，安卓和iOS中的助听器使用蓝牙低功耗[1, 5, 9]。蓝牙技术联盟最近提出了一种基于蓝牙低功耗的音频配置文件[7],，该配置文件过去仅由经典蓝牙支持。最近在[21]中提出了一种基于蓝牙低功耗的语音传输方案。

使用蓝牙低功耗（BLE）同时支持低流量和高流量应用程序，并与不同应用程序建立多个蓝牙低功耗连接，正变得越来越普遍。因此，有必要系统地研究BLE在链路层级别是否能够高效处理多个高流量（或低流量）应用程序，而这一层面的功能此前在商用芯片组中是被隐藏的。最新的Zephyr [11],是由北欧半导体、谷歌和英特尔等多家厂商共同维护的开源操作系统，它开放了BLE控制器（链路层）的实现，使得研究社区能够对BLE的链路层协议进行深入研究。具体而言，由于BLE规范中并未包含多连接所必需的资源调度技术，我们的工作聚焦于BLE的 ‐layer level=""> 多连接资源调度。据我们所知，这是该主题上的首个系统性研究方法。

在动机部分，我们首先使用具有厂商特定调度技术（封闭实现）的商用BLE芯片组进行了初步研究。我们的结果表明，即使通信资源充足，现有的调度技术也无法为多连接提供可靠的服务。在最坏的情况下，低流量应用分配到的通信资源远多于高流量应用。事实证明，这些技术均未考虑满足每个应用程序服务质量所需的资源实际数量。此外，现有调度器除非添加或删除连接，否则不会更新资源分配；一旦某个应用程序的资源分配不当，其服务质量将持续下降直至结束。

为了解决这些问题，建议预留与流量负载和服务质量需求相关且有用的信息资源。我们需要设计一种灵活的调度方法，根据需要为每个连接重新分配资源。为了使调度器能够在实际BLE芯片组上运行而不违反蓝牙低功耗规范，我们需要回答以下四个问题。

(1) 如何向控制器提供应用层服务质量信息：控制器（链路层）缺乏与服务质量相关的流量负载和延迟要求等信息，这使得合理的资源调度变得困难。为解决此问题，控制器需要定义并使用额外控制消息来获知应用程序的流量负载。否则，控制器必须通过一种尚未提出的新方法来推断应用程序的流量负载。

(2) 建立新连接时如何调度资源：在多个连接具有服务质量要求的情况下，调度器应为每个连接确定不同的连接事件长度，以及每个连接使用其时间资源的频率。具体到蓝牙低功耗，这最终归结为为每个连接确定两个参数：连接间隔和锚点。每当建立新连接时，都应完成此操作。

(3) 如何重新调度资源：即使调度方案在建立新连接时考虑了其应用程序级别的服务质量，所需的服务质量可能会随时间变化，或者初始的资源分配可能并非最优。如果出现这种情况，调度方案应调整每个连接的时间（即锚点），以提供刚好足够的资源来满足其服务质量要求。

(4) 何时执行资源调度：每个蓝牙低功耗设备（例如，本工作中使用的北欧半导体 nrf52840[8]）计算能力较低，但需要处理时间敏感的链路层任务。为了避免干扰其他关键的蓝牙低功耗操作，调度算法应尽量简单，并谨慎选择运行调度的时机。

为了解决上述问题，我们设计了BLEX，这是一种用于蓝牙低功耗的自适应资源调度系统，旨在满足各种应用的多连接服务质量需求。在资源调度方面，BLEX首先通过连接事件长度确定应用程序的流量大小。然后，在建立新连接时，BLEX调整每个连接的锚点。BLEX计算正在进行的连接的连接事件长度，并将新连接的锚点放置在空闲时间内。

由于仅使用空闲时间来建立新连接，BLEX不会降低现有连接的性能。在周期性更新期间，BLEX压缩每个连接的空闲时间，以最大化未来应用程序可用的空闲时间。最后，BLEX在空闲时间内执行计算，以避免干扰现有的时间敏感操作。我们在Zephyr上实现了BLEX，并使用Nordic nrf52840对其性能进行了广泛评估。结果表明，在各种场景下，BLEX的表现明显优于传统方案。

这项工作的贡献有三个方面。

通过初步实验，我们观察了现有商用BLE芯片组的调度方式，并发现事实上的系统无法满足多连接的各种服务质量要求。

我们提出了BLEX，一种调度系统，旨在通过调整锚点来保证多连接的服务质量，且无需额外开销。该系统不违反蓝牙规范，也不需要对主机部分进行修改，因此 BLEX可用于任何应用程序。

我们实现了所提出的系统原型，公开了其源代码，并在测试平台上进行了广泛的评估，结果表明该系统优于最先进的调度系统。

本文的组织结构如下。我们分别在第2节和第3节中讨论背景和动机。第4节设计了所提出的系统，并在第 5节中对其进行评估。我们在第6节中回顾相关工作，在第7节中提出局限性和未来工作，最后由第8节对全文进行总结。

2 背景：BLE

蓝牙低功耗支持两种类型的通信信道：用于无连接广播的广告信道和用于基于连接单播的数据信道。鉴于本工作专注于多个连接的资源调度，本节描述一对蓝牙低功耗设备如何建立连接，并通过已建立的数据信道交换数据。

2.1 连接建立

图1展示了蓝牙低功耗设备中的一对设备（发起设备和广播设备）如何通过使用三个广播信道（即信道37、38和39）建立连接。为了建立连接，发起设备扫描这三个广播信道，同时广播设备在这些信道上传输广播数据包。当发起设备接收到一个广播数据包后，会在 TIFS(150 μs)后向广播设备发送一个CONNECT_IND协议数据单元（PDU）。

连接建立后，两个设备开始在37个数据信道上通信，发起设备和广播设备分别称为主设备和从设备。主设备和从设备每隔连接间隔同时唤醒并交换数据包。数据包交换的周期性事件称为连接事件，每次连接事件开始的绝对时间称为锚点。因此，连接间隔

1https://github.com/ejparkNETLAB/BLEX_主设备， https://github.com/ejparkNETLAB/BLEX_从设备

是两个连续锚点之间的时间间隔。主设备在每个连接事件开始时，通过在相应的锚点发送一个数据包来启动。

CONNECT_IND PDU 包含用于维持连接的参数，例如影响连接锚点的WinOffset和WinSize。具体而言，如果 CONNECT_IND PDU 传输在时间 tind 结束，主设备将把该连接的第一个锚点设置在以下两个绝对时间之间：

tind+ transmitWindowDelay+ transmitWinOffset,(1)
tind+ transmitWindowDelay+ transmitWinOffset(2)
+transmitWinSize

其中

transmitWinOffset= WinOffset× 1.25msec, (3)
transmitWinSize= WinSize× 1.25msec (4)

且transmitWindowDelay为常数（1.25毫秒）。随后，每个锚点位于其前一个锚点之后的一个连接间隔处。将 WinSize设置为零可允许将新的锚点设置为特定值。

2.2 BLE资源调度基础

有两个对应用程序服务质量有显著影响的连接参数：（1）连接间隔和（2）锚点。连接间隔决定了连接进行

连接事件（即交换数据包的机会）的频率，直接影响延迟性能。锚点与连接事件长度相关，决定了连接在一次连接事件中可传输的流量大小。

图2展示了当主设备具有多连接时，锚点如何影响连接事件长度。由于同一时间只能有一个活跃的连接事件，蓝牙低功耗会在另一个连接事件开始时强制关闭当前的连接事件。例如，在图2中，即使从设备1正处于数据包传输过程中，其连接事件也会因从设备2的连接事件启动而被终止。文献[15]使用术语阻塞来描述

这种后一个连接阻塞前一个连接的现象。由于连接阻塞，当主设备处理多连接时，每个连接的锚点都会影响其他连接的事件长度。

因此，BLE资源调度最终归结为正确确定每个连接的连接间隔和锚点。BLE规范允许主设备的主机（上层）设置连接间隔的范围（最小值和最大值），并由主设备的控制器（链路层）在给定范围内选择一个具体的值。为此，BLE提供了一个主机‐控制器接口（HCI）命令，称为LE连接更新，该命令由主机发送给控制器，用于更新连接间隔。

相比之下，蓝牙低功耗仅允许控制器设置连接的锚点；没有HCI命令可以设置/访问WinOffset和WinSize。

图3描述了如何更新连接的锚点。为了更改现有连接的锚点，控制器不仅使用WinSize和WinOffset，还使用 Instant。新的锚点不会立即生效。Instant表示从当前锚点开始需要经过多少个连接间隔后，新锚点才会生效。

因此，如果在锚点为told且连接间隔为 TCI的连接事件中触发更新，则具有新参数的第一个锚点位于以下两个绝对时间之间：

told+ Instant × TCI+ transmitW inO f f set, (5)
told+ Instant × TCI+ transmitW inO f f set (6)
+transmitW inSize.

通过将WinSize设置为零，我们可以将新的锚点设置为特定值。

主机（上层）根据应用程序的延迟要求来确定每个连接的连接间隔。然而，锚点仅由控制器（链路层）控制，而控制器不具有任何应用层信息。因此，资源调度方案应考虑如何向控制器提供有关应用程序流量负载的信息。

2.3 Zephyr操作系统

最后，有必要提到Zephyr [11],是一个实时且开源的操作系统，支持多种协议，如蓝牙低功耗、Wi‐Fi、 IEEE 802.15.4、6LoWPAN、CoAP、IPv4、IPv6、 以太网和Thread。Zephyr由多家厂商共同维护，已在物联网领域得到越来越广泛的应用。特别是对蓝牙低功耗研究产生了重大影响，因为它开放了以往完全封闭的 BLE控制器代码。尽管蓝牙已经存在了二十年，但我们认为，随着软件定义的开放控制器的出现，前所未有的研究机会正在涌现。人们有机会深入探究BLE链路层的各个方面，例如通过调整锚点来实现资源调度。

3 动机

本节对现有的调度系统进行初步研究，考察这些系统是否能够同时支持多连接。根据研究结果，我们提出了一套设计要求，以实现资源调度系统对多连接的高效处理。

3.1 初步研究

我们评估了两款具有代表性的商用BLE芯片组：CSR 4.0 适配器[4]和BCM4356 芯片组[3]。CSR 4.0 适配器常用于将蓝牙耳机、键盘和鼠标连接到个人电脑，而BCM4356广泛应用于笔记本电脑、智能手机和平板电脑。在维持单个连接的情况下，CSR 4.0 适配器和BCM4356分别提供 285 kbps和185 kbps的最大吞吐量。

为了观察两个设备在存在多连接时的工作情况，我们将最多四个从设备以相同的40 ms连接间隔连接到主设备，其中从设备1、2、3和4按顺序与主设备建立连接。我们让每个从设备在三种不同的流量场景下向主设备产生流量：（1）同流量，（2）递增流量，和（3）递减流量。在同流量场景中，每个从设备产生最大吞吐量的1/4。在递增流量场景中，从设备1、2、3和4分别产生最大吞吐量的1/8、1/8、1/4和1/2。在递减流量场景中，从设备1、2、3和4分别产生最大吞吐量的1/2、1/4、1/8和1/8。

和图4(d)显示 每个从设备的流量相同时的情况，图4(b)和图4(e)显示从设备流量逐渐增加时的情况，图4(c)和图4(f)显示从设备流量逐渐减少时的情况。左侧条形为理想调度，右侧条形为实际测量。)

图4显示了根据从设备数量得出的结果。每种情况都有两个堆叠的条形：左侧的条形表示理想吞吐量，右侧的条形表示实际吞吐量。对结果的粗略分析表明， CSR 4.0 适配器和 BCM4356 都随着连接的从设备数量增加而出现显著的性能下降：吞吐量损失从27%到62%。

由于这两个设备的资源调度系统是隐藏的，因此有必要进行逆向工程

为了更深入地分析图4的结果，我们进行了另一个饱和流量下的实验。我们依次将四个从设备连接到主设备，并确保它们都尽可能多地产生流量。图5显示了从设备吞吐量相对于从设备数量的变化情况。

对于 CSR 4.0 适配器，如图5(a)所示，我们观察到每当从设备 2 在从设备 1 之后新加入时，从设备 2 会占用从设备 1 60% 的资源。鉴于所有从设备使用相同的连接间隔，该结果表明从设备 2 的锚点可能被设置为（从设备1的锚点+ 0.4*连接间隔），从而导致从设备 2 的连接事件阻塞从设备 1 的连接事件。当从设备 3 加入时，它通过阻塞从设备 2 的连接事件（即从设备 1 的）占用了从设备 2 60% 的资源

资源被完全保留，此时三个从设备的吞吐量按2:1:2分配。最后，当从设备4加入时，它阻塞了从设备1而不是从设备2和从设备3，导致从设备1的吞吐量急剧下降。我们可以推测，从设备4的锚点位于从设备1的锚点之后不久。之前阻塞从设备1的从设备2，现在转而阻塞从设备4。

鉴于实验结果能够反复重现，我们得出结论：CSR 4.0 适配器采用一种固定调度策略，如图6所示。

根据上述发现，让我们回到图4(a)‐(c)，即CSR 4.0 适配器的情况。在同流量场景中

BLEX：蓝牙低功耗灵活多连接调度

4 BLEX：面向蓝牙低功耗的灵活调度

本节介绍了BLEX，一种用于蓝牙低功耗的新型资源调度系统，旨在高效满足多连接的服务质量需求。我们首先概述整个BLEX系统，并描述其核心模块的细节。鉴于为每个连接设置连接间隔是简单的任务，可由主机通过考虑应用程序的延迟要求轻松完成，因此BLEX专注于更具挑战性的任务：在控制器上为多连接调度锚点。

4.1 系统概述

图7 总结了我们的 BLEX 系统的整体架构。BLEX 具有以下四个核心模块。

• Connection event length calculator 在控制器处估算每个连接的应用流量负载，而无需任何显式控制消息。该模块使BLEX能够监控每个连接的资源是否足以容纳其流量负载。
• Connection manager 构建一个时间表，其中包含每个连接的事件长度、连接间隔和锚点。该模块试图保持时间表的大小较小，以降低计算复杂度。
• WinOffset连接更新的 WinOffset 计算器 定期为每个现有连接更新WinOffset，以调整资源分配。其目标是使每个连接拥有刚好足够的资源来应对自身的流量，并使单个连接几乎拥有所有空闲资源。
• WinOffset连接建立的WinOffset计算器 为新加入的从设备提供WinOffset。该模块旨在为新从设备提供一个锚点，使其在不侵犯现有从设备服务质量的前提下，尽可能获得充足的资源。

BLEX是一种纯链路层机制，完全在Zephyr控制器代码中实现。通过将其整个系统与主机部分解耦， BLEX可以适用于各种蓝牙低功耗芯片组。此外，应用程序可以在不更改其配置文件和主机操作（例如，使用附加HCI命令）的情况下获得性能提升。

4.2 连接事件长度计算器

一个对BLEX的挑战是控制器不知道应用程序流量负载。解决此问题有几种方法。首先，可以定义一个新的 HCI命令，使主机向控制器提供流量负载信息。然而，这会带来额外的开销，并限制了该机制的适用性，因为需要同时修改主机部分。其次，控制器可以检查其发送（TX）队列长度。但是，这种方法仅适用于发送方。如果从设备向主设备发送流量，主设备无法获取流量负载信息，因为它不知道从设备的发送队列长度。为此，从设备应向主设备发送一个新的控制 PDU，其中包含其发送队列长度，但这会带来额外的开销。

相反，我们发现连接的事件长度可用于指示其流量负载。尽管连接拥有充足的资源，但如果无需传输流量，其连接事件会提前结束；连接事件长度与流量需求成正比。因此，我们通过测量每个连接的起始（即锚点）与其结束之间的时间差来确定其连接事件长度。

然而，要使用连接事件长度进行资源调度，还需要解决一些问题。首先，由于连接的事件长度会根据流量模式和链路层重传而变化，因此需要有一个合适的值来表示流量负载。为此，我们利用指数加权移动平均（EWMA）滤波器对每个连接的事件长度进行平均。其次，需要注意的是，当接收方连续两个数据包出现 CRC错误时，即使还有许多数据包等待发送，蓝牙低功耗也会提前终止连接事件。在这种情况下，即使流量负载较高，连接事件长度也会很短。为缓解这一问题，如果连接事件因CRC错误而被终止，我们将忽略该连接事件长度。

最后，连接事件长度计算器将测得的锚点和连接事件长度发送给连接管理器进行调度。

：转换连接间隔前的重复调度单元)

：转换连接间隔后的重复调度单元)

4.3 连接管理器

连接管理器利用从连接事件长度计算器接收的信息（即锚点和连接事件长度）来构建时间表，以高效地管理资源调度。为此，连接管理器需要解决一个挑战：当多个连接具有不同的连接间隔值时的时间表开销。

图8(a)说明了两个连接具有不同的连接间隔值 90 mesc和20 mesc时所面临的挑战。在这种情况下，连接管理器至少需要在一个 180 mesc间隔（90和20的最小公倍数）内了解所有锚点（以及连接事件长度），才能完整掌握资源调度情况：总共11个锚点。我们将包含完整资源调度的最小单元称为重复调度单元。连接管理器的时间表应至少包含一个重复调度单元；随着重复调度单元的大小增加，连接管理器的时间表大小和计算开销也随之增加。由于重复单元的大小与所有不同连接间隔值的最小公倍数成正比，因此其开销会成为问题，特别是当连接间隔值为互素时。

为了解决这一问题，BLEX将连接间隔限制为 1.25*2^n mesc。具体而言，当主机给出连接间隔范围时，控制器会选择该范围内可表示为1.25*2^n mesc形式的最大连接间隔。这样，各连接间隔值的最小公倍数始终等于最长的连接间隔，从而限制了重复调度单元的大小。

图8(b)展示了此限制的效果。从设备1的连接间隔变为 80 mesc(=1.25*2^6)，而不是 90 mesc，而从设备2的连接间隔保持不变（20= 1.25*2^4）。由于两者的最小公倍数为 80 mesc，重复调度单元的大小变为 80 mesc，不到之前的一半（即180mesc）。需要管理的锚点数量变为5，不到之前的一半（11）。

接下来，为了构建时间表，连接管理器使用每个连接的事件长度、锚点和连接间隔将重复调度单元划分为单元。每个从设备的单元数量等于重复调度单元的长度除以该从设备的连接间隔。由于时间表需要在从设备的活动时隙之间存储空闲单元，因此时间表最多需要存储两倍于活动时隙总数的单元。时间表中的每个单元条目都包含其锚点以及使用该单元的从设备的节点编号。如果没有从设备使用该单元（即空闲单元），则其节点编号为空，其锚点变为前一个单元结束的时间。

我们通过图8(b)中的示例说明如何构造时间表。重复调度单元从最先加入的从设备的单元开始，在本例中即从设备1。之后，连接管理器利用其已有的信息填充所有条目。如果每个从设备的锚点分别为250 mesc和 260 mesc，如表1所示，则该时间表包含从 250 mesc到 330 mesc的10个单元。表2显示了这10个单元的时间表。

由于从设备1的连接间隔与重复调度单元相同，因此它只有一个单元，其锚点为 250 mesc。从设备2需要四个单元，其锚点分别为 260 mesc、280mesc（即 260+ TCI）、 300 mesc（即 260+ 2TCI）和 320 mesc（即 260+ 3TCI），因为从设备2的连接间隔是重复调度单元的四分之一。

最后，还有五个空闲单元。每个空闲单元的锚点通过其前一个单元的锚点和事件长度计算得出。该方法即使在主设备拥有更多具有不同连接间隔的从设备时，也可以应用而不会失去通用性。

表1: Connection management example: Parameters of slave 1 and slave 2

从设备编号	连接间隔	锚点	连接事件长度
从设备 1	90 mesc	250 mesc	9 mesc
从设备 2	20 mesc	260 mesc	4 mesc

表2：连接管理示例：时间表

单元格编号	节点编号	起点（锚点）
0	1	250
1	NULL	259 (=250+9)
2	2	260
3	NULL	264 (=260+4)
4	2	280 (=260+20)
5	NULL	284 (=260+20+4)
6	2	300 (=260+20*2)
7	NULL	304 (=260+20*2+4)
8	2	320 (=260+20*3)
9	NULL	324 (=260+20*3+4)

：空闲时间过短)

：空闲时间过长)

4.4 WinOffset用于连接更新

通过时间表，WinOffset连接更新计算器可判断当前资源调度是否高效。当出现以下两种情况时，计算器会判定时间表效率低下：（1）两个活动单元之间没有（或过于短暂的）空闲单元；（2）两次连接事件之间存在过长的空闲单元（即最后一个空闲时隙被忽略）。在情况（1）下，BLEX可能需要更多资源，但它会判断后端从设备阻塞了前端从设备。在情况（2）下，存在压缩空闲单元的空间，从而为将来的连接增加最后一个空闲时隙。请注意，对于未来的资源分配而言，一个大的空闲单元优于多个小的空闲单元。如果两种情况同时发生，则优先处理情况（1），因为满足服务质量比效率更为重要。

图9 显示了 BLEX 如何为以下两种情况更新三个从设备的连接。

空闲单元过短的情况 ：图9(a) 说明了从设备 1 和从设备 2 的活动时隙之间的空闲单元过短（小于 1 mesc，即在 1 Mbps 物理层速率下传输最长数据包所需时间的一半 2 mesc）的情形。在此情况下，BLEX 应增加前端从设备（从设备 1）的单元以满足其服务质量。为此，BLEX重新配置锚点。

为了增加从设备 1 的活动单元大小，应增大活动单元之后的空闲单元。由于主设备的控制器不知道需要多少资源才能满足从设备 1 的服务质量（QoS），BLEX 应首先最大化从设备 1 活动单元后的空闲单元大小，以便从设备 1 可以使用尽可能多的资源。如果分配给从设备 1 的资源过多，情况（2）将重新调度这些不必要的资源。

最大化从设备 1 的资源时应谨慎进行，因为在此过程中不应影响其他从设备。为此，BLEX按以下顺序调整锚点：由于在从设备 2 和从设备 3 之间没有可用于压缩空闲单元的空间，但最后一个空闲时隙足够长，因此推迟从设备 3 的锚点以减少最后一个空闲时隙。随后，从设备 2 和从设备 3 之间的空闲单元增加。接下来，推迟从设备 2 的锚点以减少该空闲单元，从而增加从设备 1 可用的空闲时间。结果，BLEX为从设备 1 分配了更多时间资源。

空闲时间过长的情况 ：图9(b) 说明了从设备 1 和从设备 2 的活动单元之间的空闲单元过长（长于 2 mesc）的情形。在这种情况下，BLEX 调整锚点以减少空闲单元，从而最大化最后一个空闲单元。鉴于 BLEX 将最后一个空闲单元分配给新连接，因此通过压缩其他空闲单元来最大化最后一个空闲单元非常重要。具体而言，BLEX 将从设备 2 的锚点推迟（连接间隔 - 空闲空间长度），以最小化从设备 1 和 2 之间的空闲单元。然后推迟从设备 3 的锚点以最小化从设备 2 和 3 之间的空闲单元，从而最大化从设备 3 活动单元之后的最后一个空闲单元。结果，所有空闲资源都集中在最后一个空闲单元中。

4.5 WinOffset用于连接建立

最后，BLEX在建立新连接时分配资源。如果没有从设备连接到主设备，则新加入的从设备将成为时间表中的第一个从设备，其锚点并不重要。然而，如果存在现有从设备，则新加入的节点不应影响它们的服务质量。

这里的挑战在于，主设备不知道新从设备的流量需求，因为它对该从设备的连接事件长度没有任何信息。为了解决这个问题，BLEX会计算扫描可连接广告与最大空闲单元锚点之间的时间差，并将此值指定为WinOffset，发送 CONNECT_IND给新从设备。这样，新从设备的锚点就变为最大空闲单元的锚点。通过这种方式，新从设备在首次连接事件中即可实现可能的最大QoS。

如背景部分所述，从主设备扫描到可连接的广播包到主设备发送CONNECT_IND之间仅有 TIFS。然而，计算WinOffset需要较长的计算时间，这可能会阻碍 CONNECT_IND PDU的传输，从而影响连接建立。因此，BLEX会预先计算该WinOffset，以便当新节点尝试加入时，主设备可以立即发送此WinOffset。但是，问题在于我们并不知道未来要加入的从设备的连接间隔，因此BLEX也无法确定所需的单元数量。因此，有必要为所有可能的连接间隔集合存储相应的锚点。我们可以快速完成此操作，因为在连接管理器中已对连接间隔进行了限制。

蓝牙规范中定义的连接间隔范围从7.5 mesc最小值到4秒最大值，因此只有九个对应于1.25*2^n mesc的值。此外，如果重复调度单元小于2560 mesc，计算次数会进一步减少。在图8的示例中，如果连接间隔大于或等于 80 mesc，所需单元数量仅为一个，因此可以一次性完成计算。因此，需要预先计算的情况仅有四种：1）TCI,new ≥80 mesc，2）TCI,new = 40 mesc，3）TCI,new= 20 mesc，以及4）TCI,new = 10毫秒，其中TCI,new为新加入的从设备的连接间隔。

对于每个连接间隔，我们确定一个锚点，该锚点需满足以下条件：(1) 符合连接间隔要求，(2) 不与现有连接重叠，(3) 提供最高的服务质量。图10 显示了根据 TCI , new 确定的待分配锚点位置。如果TCI , new 大于或等于 80 mesc，则在当前时间表中仅分配一个单元，因此 BLEX 设置最大单元的开始时间将空闲单元分配给新的锚点。当TCI,new为 40 mesc时，由于当前时间表的长度为80毫秒，新从设备需要在该时间表中占用两个单元。此时，考虑TCI,new，可分配单元的集合为 {(1,5), (3,7), (5,9)}。根据之前的时间表，组合(3,7)可以为新从设备提供最充分的时间资源，因此将新的锚点放置在单元3和7的起始时间处。即使当TCI,new小于40毫秒时， BLEX仍可普遍适用相同的方法而不会失去通用性。

5 性能评估

为了评估BLEX的性能，我们在Zephyr控制器上实现了它，并将其构建在Nordic nrf52840[8]上。在Zephyr控制器中，我们修改了ull_master.c、ull_conn.c和lll_scan.c文件。Zephyr符合蓝牙规范，但连接建立和连接更新中的WinOffset更新部分尚未实现。因此，我们修改了主设备和从设备的event_conn_upd_prep、ctrl_rx以及isr_rx_pdu函数，使设备能够执行WinOffset更新过程。为了实现BLEX，我们修改了主设备端ull_conn.c中的ull_llcp_conn和ull_llcp_conn_done函数。

在 ull_llcp_conn 函数中，我们测量连接事件的长度并对其进行平均。在 ull_llcp_conn_done 函数中，我们使用此连接事件长度来管理调度并计算 WinOffset。当通过 lll_scan.c 中的 isr_rx 接收到可连接的广告消息后发送 CONNECT_IND PDU 时，该 WinOffset会被传输到从设备。此外，如果主设备确定需要进行锚点更新，则会通过修改后的 llcp_conn_update 发送 WinOff-set并更新连接。

Nordic nrf52840 是一款单板开发套件，配备 64 MHz Arm Cortex‐M4 与 FPU、1 MB 闪存和 256 KB 内存，并支持蓝牙低功耗、蓝牙网状网络、Thread[26], 和 ZigBee。该开发板已通过提供蓝牙5特性[12, 13, 33]被广泛应用于许多研究中。

为了进行比较，我们在Zephyr控制器上实现了基于CSR和基于BCM的方案，即CSR 4.0适配器和 BCM4356的实际调度方案。该实现基于动机部分中的真实实验。我们还将Zephyr默认操作与基于CSR和基于BCM的方案结合使用。Zephyr默认操作将 WinOffset设置为0，并在主设备接收到可连接的广播包时发送CONNECT_IND PDU，这意味着扫描发生的时间即成为锚点。我们验证了在连接间隔相同（即40毫秒）的情况下WinOffset对连接建立和连接更新的影响，然后在实际多应用场景中进行性能评估。

：相同流量场景)

：递增流量场景)

：递减流量场景)

5.1 WinOffset在连接建立中的应用

我们通过实验研究了当多个连接具有相同连接间隔时 BLEX的性能。我们在三种简单场景下评估每种方案的性能，以验证BLEX是否实现了我们的目标：在不降低现有连接服务质量的前提下，保证新连接的最大QoS。这三种场景涵盖了相等流量、递增流量和递减流量的情况，使用四个从设备和一个主设备，如动机部分所述。

在相同流量场景中，每个从设备向主设备产生 125 kbps 的流量。在递增流量场景中，主设备从从设备 1 和 2 接收 51 kbps，从从设备 3 接收 175 kbps，从从设备 4 接收 285 kbps。在递减流量场景中，主设备从从设备 1 接收 285 kbps，从从设备 2 接收 175 kbps，从从设备 3 和 4 接收 51 kbps。这些数值的选择使得应用程序能够在考虑运行 Zephyr 的 Nordic nrf52840 在一个从设备占用全部资源时吞吐量最高可达 600 kbps 的情况下，以固定速率发送流量。图11 和 图12 显示，BLEX 在建立新连接时通过更改 WinOffset 实现了最高的总吞吐量，同时不影响正在进行的从设备的服务质量。

相等流量场景 ： 图11(a)显示了测量吞吐量，图12(a)展示了每个从设备在相同流量场景下的QoS达成率。基于 CSR和基于BCM的方案无法保护现有从设备的QoS，因此，当一个从设备新加入时，这些方案会显著降低现有从设备的服务质量。在Zephyr默认操作的情况下，主设备执行扫描的时间会影响连接的锚点。由于扫描仅在空闲时间内进行，因此与基于 BCM和基于CSR的方案等事实标准方案相比，它对正在进行的从设备的服务质量影响不大。

与之相比，通过连接事件长度计算器，BLEX可保证为每个从设备分配其所需的时间（即平均连接事件长度），因此即使有新从设备加入，对现有从设备的影响也可忽略。BLEX相较于基于CSR的方案、基于BCM的方案和Zephyr默认操作，总吞吐量分别提升了19%、 16%和10%。这是因为BLEX优先为正在进行的从设备分配时间，然后将剩余时间压缩并分配给新从设备。

递增流量场景 ： 当现有从设备的流量较小时，它们所占用的连接事件长度较短，因此被中断的概率相对较小。在基于CSR的方案中，总吞吐量略高于所提出的方案，但当从设备 4 加入时，它占用了从设备 1 的大部分时间，导致现有从设备的服务质量无法得到保障。在基于 BCM的方案和Zephyr默认操作中，我们看到总吞吐量较低，同时无法满足现有从设备的服务质量。相比之下， BLEX在为新从设备分配尽可能多的时间的同时，保障了正在进行的传输的服务质量，即调度运行理想。

流量减少场景 ： 在此场景中，BLEX在三种方案中表现出最大的性能提升。原因是正在进行的从设备已经占用了大量时间。因此，在对比方案中，新从设备的锚点与现有从设备的连接事件发生重叠的概率较高，从而导致新从设备侵犯了正在进行的从设备的服务质量。特别是，在基于CSR的方案中，由于低流量的从设备4加入时占用了高流量的从设备1的大部分时间，总吞吐量显著降低。相比之下，BLEX在保证现有正在进行连接的服务质量的同时，为新从设备分配了最大可能的时间。

BLEX相较于基于CSR的方案、基于BCM的方案以及 Zephyr默认操作，总吞吐量性能分别提升了113%、 33%和38%。

：从设备 1 的服务质量失败)

：从设备 2 的服务质量失败)

5.2 WinOffset in Connection Update

To show the effect of WinOffset on the connection update, we connect two slaves sequentially to the master(until slave 2 establishes a connection, slave 1 does not generate traffic) and measure the QoS failure ratio by changing the amount of traffic to the slaves every 60 seconds. For the first 60 seconds, the master sends 220 kbps to slave 1 and 97 kbps to slave 2. Then the master sends 220 kbps to slave 2 and 97 kbps to slave 1 for the next 60 seconds. Traffic changes every 60 seconds.

图13比较了BLEX在有无连接更新情况下的性能。在没有连接更新的BLEX中，即BLEX‐fixed中，当第一个锚点确定后，无论流量如何变化，锚点都不会改变。长时间的变化导致资源浪费，即使流量发生变化，这些资源也不会分配给需要更多资源的从设备。在这种情况下，初始分配时间较少的从设备 1 会周期性地出现服务质量失败。然而，BLEX通过连接更新能够周期性地判断调度是否低效，并相应地调整锚点。BLEX能够自适应地为高流量的从设备分配更多时间，因此其服务质量失败率始终低于BLEX‐fixed。

：Achieved throughput)

：QoS achievement ratio)

5.3 多种服务质量需求

到目前为止，我们在一个简单但不实际的场景中进行了实验，其中所有从设备都使用相同的连接间隔来展示锚点调整的性能。然而，在使用蓝牙低功耗时，每个应用程序产生的流量不同，并且对延迟的要求也不同。本小节针对每个应用程序的吞吐量和延迟要求不同的场景进行实验。在基于CSR和基于BCM的方案中，由于连接间隔各不相同，与初步实验不同，我们额外进行了逆向工程，并将其结果反映在实现中。

我们将从设备1到从设备4依次连接到主设备，并假设从设备1和从设备3使用音频流应用，从设备2使用键盘应用，从设备4使用FTP应用，例如连接到照片打印机。根据 [6, 10],音频流应用所需的吞吐量约为192 kbps，键盘应用所需的吞吐量低于10 kbps。FTP应用假设需要超过 150 kbps的吞吐量，尽管这取决于文件大小。此外，参考[16]中的延迟要求：音频流应用要求延迟低于100毫秒，键盘应用要求50毫秒，而FTP应用要求200毫秒，因为延迟对FTP应用并不重要。假设没有链路丢失，我们使用这些延迟要求来确定最大连接间隔。图14显示了每个从设备的吞吐量和QoS达成率结果。

在所有对比方案中，我们观察到吞吐量下降程度相似或更严重，且服务质量达标率降低，与之前的实验结果相比情况更差。值得注意的是，当连接间隔相同时， Zephyr默认操作中的从设备2对从设备1的性能影响不大。但如果它们的连接间隔不同，从设备2的加入会显著降低从设备1的性能。原因是：当连接间隔相同时，在Zephyr默认操作下，第一个锚点始终位于空闲时间内，并且在下一个连接间隔也是如此。然而，当从设备 2使用的连接间隔小于从设备1时，即使扫描点处于空闲状态且第一个锚点恰好位于空闲单元内，下一个锚点仍可能与从设备1正在进行的连接事件发生重叠。相反， BLEX会周期性地检查调度并根据新连接的间隔计算合适的锚点，因此无论连接间隔是否相同，都能保证现有连接的服务质量。

5.4 连接间隔转换

最后要关注的是连接间隔转换对吞吐量性能的影响。之前，我们将连接间隔转换为可调度的值，以应用BLEX调度。然而，有时这个值可能不存在于主机定义的可能连接间隔范围内。我们展示了当BLEX无法转换连接间隔值时，BLEX的性能变化情况。图15显示了在上述多QoS应用场景中，从设备 4 的连接间隔对应的实验结果。特别是，在本例中，我们测量了未将从设备 4 的连接间隔值转换为我们期望值时的吞吐量。

无论从设备 4 使用何种连接间隔，BLEX的性能均优于 Zephyr默认操作。这是因为即使 BLEX无法转换 从设备 4 的连接间隔，BLEX仍可调度其他从设备。在最坏情况下，即使所有从设备的连接间隔均不可转换， BLEX至少也能达到 Zephyr默认操作的性能水平。

6 相关工作

在无线通信中，多个设备的资源调度是一个长期受关注的话题，因为多个设备共享有限的频率和时间资源 [14, 15, 17, 22–24, 27]。特别是在低功耗有损网络（LLNs）中，资源调度是一个更为关键的问题，因为 LLN设备无法支持复杂的机制或拥有集中式服务器。更严重的是，构成LLN的设备数量正在快速增长，但频率或计算能力等资源却是有限的。

时隙跳频（TSCH）是一种在IEEE 802.15.4e中定义的低功耗介质访问控制（MAC）协议，与蓝牙低功耗类似，它提供时间同步、信道跳频和周期性唤醒。因此，参考TSCH时隙调度系统来设计蓝牙低功耗调度系统具有重要意义。最新的TSCH资源调度技术 [18, 23, 24, 27, 28]以分布式或自主方式运行，在路由拓扑和/或流量负载变化时为每个节点或定向链路分配时隙。

文献[24]中的作者通过自适应调整时隙帧来分配时隙，同时考虑了拓扑结构以及每个节点产生的流量大小。在 [27],中所提出的方案并不感知流量，但通过为每条发送‐接收链路分配时隙来减少冲突。文献[23]中提出的方案在此基础上更进一步，构建了二进制资源树，在感知流量大小的同时为每条链路分配专用时隙以减少冲突。然而，与TSCH不同的是，在蓝牙低功耗中：

• 没有离散时隙。我们不分配时隙，而是仅设置连接事件的开始时间（即锚点）。
• 由于蓝牙低功耗是基于连接的，因此有必要交换控制包来调整参数。
• 默认网络配置是单跳星型拓扑，而不是多跳拓扑。因此，蓝牙低功耗中的主设备以集中式方式执行资源调度。

因此，蓝牙低功耗调度无法直接使用TSCH调度，这一点已在最近的多项研究中被提及。

尽管许多关于BLE调度的研究考虑了单连接场景 [29, 32, 33],，但也有一些先前的工作处理了多连接 [14, 15]。文献[14]的作者研究了一种降低功耗并提高数据包投递率的方法，并提出了一种针对信标（即广播数据包）的调度方案。然而，由于广播数据包最初旨在传输不需要高服务质量的数据，因此可靠的通信并非必需。

文献[15]的作者考虑了数据信道中用于调度的服务质量，但他们仅调整了连接间隔，而未考虑连接事件的锚点。然而，正如动机部分所述，仅通过连接间隔来解决问题存在局限性。据我们所知，目前尚无论文通过调整连接事件的锚点来改善蓝牙低功耗数据信道的服务质量。

自2016年Zephyr成为Linux基金会的项目以来， Zephyr通过可修改的BLE控制器在BLE研究领域的份额不断增加，而在此之前这一直具有挑战性。特别是，在[34],中，M. 斯波克等人实现了一种通过重传次数检测干扰并调整连接间隔的方案，并通过Zephyr评估了其性能。在[35],中，作者利用每个信道的数据包投递率和信噪比来提升蓝牙低功耗的自适应跳频性能，而这些参数此前难以使用。[20]中的作者提出了一种利用蓝牙低功耗的FSK（类）信号作为超低功耗FSK唤醒无线电的方案，并使用Zephyr实现了该方案。在[19],中， Zehpyr被用作广播设备以测试所提出的新扫描算法。

然而，目前尚无研究使用Zephyr修改BLE锚点以实现高效调度。

7 讨论

BLEX是首个灵活调整锚点的资源调度方案，但这并不意味着该研究领域的终结。在本节中，我们探讨进一步提升BLEX性能的潜力。

关于附加HCI命令和控制PDU 。BLEX可用于各种应用。这是因为其不违反蓝牙规范，也不需要主机级修改。如果我们允许主机在连接建立期间通过附加HCI命令和控制 PDU指定要转发的流量，则可能进一步提高BLEX的性能。然而，所提出的通过预测应用流量的方法连接事件长度已经显示出接近100%的QoS达成率。因此，通过额外控制所能获得的增益可以忽略不计。

关于扩展到多跳情况 。 针对 IEEE 802.15.4 的研究通常处理多跳情况，但关于蓝牙低功耗的多跳 [25, 30, 31] 研究较少。一个问题随之而来：我们能否将所提出的 BLEX 扩展到多跳场景？根据当前提出的 BLEX，主设备可以自由更改从设备的锚点。因此，如果一个从设备是另一个节点的主设备，则调度该从设备的从设备将导致混乱。为克服此问题，主设备与从设备之间交换额外的控制 PDU 是最直观的解决方案。或者，如果一个从设备同时充当主设备，则应拒绝更新锚点的请求。

关于何时更新连接 。 在我们的论文中，我们使用 1毫秒 和 2毫秒 作为判断 BLEX是否需要连接更新的基础。然而，考虑到单个数据包的长度，这可能过短，从而导致不必要的连接更新。增大该值以减少连接更新的频率将使BLEX更加稳定，但会造成时间资源的不必要浪费。该值应得到良好控制，因此有必要进行进一步实验以找到合适的值。

8 结论

本文证实了当多个从设备连接到一个主设备时，每个连接的锚点会显著影响连接的服务质量。在观察到现有调度方案即使拥有足够资源仍会显著降低性能后，我们设计了一种名为BLEX的新型调度系统来解决该问题。

BLEX通过调整蓝牙低功耗连接的锚点，旨在最大化总体服务质量，同时不牺牲现有连接的服务质量。我们在实际嵌入式平台上实现了BLEX，并验证了其能够成功调整蓝牙低功耗设备的锚点以满足预定义的服务质量要求。BLEX优于采用非常简单的锚点指定方式的基线方案。

作为首次对蓝牙低功耗锚点进行自适应调整的尝试，我们相信这项工作可以为其他研究人员在该领域进一步探索提供一块steppingstone。