物联网(internet-of-things, IoT)应用的飞速发展对终端设备的低功耗特性提出了新的要求^[1-3]。LoRa作为低功耗广域网，因其开放标准使用户能够在无需第三方基础设施的情况下构建私有LoRa网络而备受关注^[4-5]。

现有的LoRa网络时间同步方案可以按同步的触发对象分为两类：由终端设备触发和由服务器触发。在终端设备触发的方法^[6-10]中，每个终端设备通过LoRa网关向服务器发送携带时间戳的数据包，服务器再将更新后的时间戳返回给终端设备。通过多个时间戳的交换，终端设备可将本地时钟与服务器同步，达到较高的同步精度(如文献[6]的10 μs以内)。然而，这种方法主要针对单个终端设备的时间同步，对于整个网络的时间同步效率较低。如多个LoRa终端设备若在同一时隙以不同的扩频因子发送带时间戳的数据包以请求时间同步，它们必须同时等待来自网关的回复(LoRa中的扩频因子具有近似正交性，因此使用不同扩频因子的LoRa信号可以在相同信道传播而不产生干扰)。然而LoRa网络中的下行链路(即从网关到终端设备的传输)是单播的形式，即网关不能同时向多个终端设备发送数据包。因此，终端设备之间将产生竞争，且某些节点无法完成时间同步。

在服务器触发的方法中，网关在给定的时隙广播同步报文，所有终端设备将在该时隙^[11-12]收听，同步报文包含服务器的时间戳和网络规模等基本信息。通过考虑数据包在服务器上的准备时间和信号传播时间等，终端设备可以更新其本地时钟。与由终端设备触发相比，该方法只有两个时间戳可用于时间同步，因此同步精度较低(如文献[11]中的1 ms)，同步精度在1 ms就可以支持LoRa网络中的大部分时隙调度应用^[12]；也可同时更新连接中的所有终端设备，更适合同步整个LoRa网络。因此，本文主要针对服务器触发的时间同步。

现有的由服务器触发的方案存在3个问题。首先，终端设备之间的本地时钟漂移速度不同，因此同步时间 (即网关广播同步报文的时间点) 的选择会影响同步精度；其次，现有方法主要针对单网关的 LoRa 网络，不能很好地利用多网关场景，忽略了扩频因子的选择产生的影响；第三，现有工作通常忽略了移动的终端设备在跨多个网关时可能产生同步失败的问题。

为了解决上述问题，本文提出了一种用于多网关LoRa网络的移动感知的时间同步框架，综合考虑了同步时间和多网关扩频因子的选择，并将多网关同步规约为优化问题，以提升LoRa网络的时间同步精度。考虑到网关和终端设备的匹配问题，上述优化问题为NP难，本文采用遗传算法进行求解。为了应对终端设备跨网关的移动性，本文提出了一种让移动终端设备重新与新网关保持同步的自适应算法。

1.   研究动机

本文首先在真实的LoRa网络平台进行了初步实验，以展示同步时间对同步精度的影响，并证明在多网关场景中，扩频因子的选择和终端设备的移动性也会影响终端设备的时间同步精度。

1.1   同步时间的选择

本文通过GPS模块比较本地时间和服务器上的全局时间，测量了3个LoRa终端设备的时钟漂移。这3个终端设备在30 min内以不同的扩频因子向网关发送数据包，网关会在此期间广播同步报文以同步终端设备(扩频因子9、频率470.3 MHz)。图1展示了3个终端设备的传输时间以及同步时间的选择。

图  1  3个终端设备的数据调度

下载: 全尺寸图片 幻灯片

由于终端设备上的本地时钟只会在同步时间之后同步，因此不同终端设备发送数据包时(如图1中的t1、t2和t3时刻)，会等待不同的时间段，可能会导致它们的数据传输失败。本文收集了3个终端设备的本地时钟和全局服务器时钟之间的偏移，如图2所示，其中同步时间为图1中的t1时刻。可以看出终端设备的本地时钟不断偏移，且在传输自身数据之前具有不同的时钟偏移速度和等待时间，因此它们具有不同的时钟漂移和同步精度。

图  2  不同终端设备的时钟漂移速度

下载: 全尺寸图片 幻灯片

1.2   多网关场景下的扩频因子选择

在单网关LoRa网络中进行时间同步时，网关必须使用最大的扩频因子来广播同步数据包，以便最远的终端设备可以接收到它们。众所周知，扩频因子较大的LoRa信号比扩频因子较小的信号消耗更多的能量^[13]。在多网关LoRa网络中，网关的覆盖范围彼此重叠，一个终端设备可以被多个网关覆盖。因此，终端设备可以选择其中一个网关，使用与其相同的扩频因子来接收其同步报文。图3表示了终端设备可以选择具有不同扩频因子和同步时间的网关进行时间同步，导致不同的同步精度。在图3a中，网关只能发送扩频因子为10的同步报文，以保证③号和④号终端设备可以接收到它。在图3b中，第二个网关的存在使①号和②号终端设备能够接收具有更小扩频因子8的同步报文，而③号和④号终端设备可以接收具有扩频因子7的同步报文，因此它们可以节省一半以上的能耗^[14]。但是，如果两个网关的同步时间、时钟漂移速度和终端设备的占空比导致时钟漂移较大，则其发送报文时时间同步可能会失败，且只能以扩频因子10从第一个网关处接收同步报文。

图  3  LoRa网络

下载: 全尺寸图片 幻灯片

1.3   终端设备的移动性

LoRa终端设备可以部署在移动物体上(如公交车^[15]和无人机^[16]等)，LoRa终端设备的移动性也会影响时间同步的性能。

考虑图3b中具有两个网关的LoRa网络，其中①号终端设备只能被①号网关覆盖。当①号终端设备移动到另一个位置时，如图4所示，它需要连接到新的②号网关。但两个网关在不同时间广播具有不同扩频因子的同步报文，导致①号终端设备无法正常同步，因为它无法从②号网关处接收数据。因此，该终端设备会同步失败，无法被调度。

图  4  LoRa移动性的示例

下载: 全尺寸图片 幻灯片

上述示例表明，同步时间对LoRa网络的同步精度有较大影响，网关应考虑所覆盖终端设备的时钟漂移并选择同步时间，终端设备还应仔细选择相应的扩频因子来接收同步报文。此外，由于使用不同扩频因子的网关和终端设备无法通信，时间同步还会受到LoRa终端设备移动性的影响。

本文提出了一种用于多网关LoRa网络的移动感知的时间同步方案，综合考虑了同步时间和扩频因子的选择，以提高同步精度。

2.   多网关的LoRa时间同步设计

2.1   系统建模

在LoRa网络中，终端设备收集环境数据并通过周围的网关将其发送到远端的服务器。多个网关可以同时接收来自终端设备的数据包，这些网关将数据中继到中央服务器进行处理。遵循最大占空比约束，每个终端设备以周期T发送数据。在基于时间同步的LoRa网络中，终端设备的数据传输被安排在不同的时隙，以避免干扰并提高信道容量^[11]。为了使终端设备与服务器上的全局时钟同步，服务器使网关向终端设备广播同步报文。每个网关可以在不同的时间$ {t}_{k}^{b} $以不同的扩展因子$ {{\rm{sf}}}_{k}^{b} $广播同步报文。LoRa终端设备上的时钟漂移速度为：

式中，$ {m}_{i} $为测量终端设备i的本地时钟的时间间隔；m为服务器时钟的时间间隔。

2.1.1   单网关模型

每个周期终端设备i在时间$ {t}_{i}^{s} $发送其数据包，${t}_{i}^{s}\in \left\{{t}_{i,0}^{s}\right.+nT|n=\mathrm{0,1},2,\left.\cdots \right\}$，网关在时间$ {t}_{k}^{s} $广播同步报文，${t}_{k}^{b}\in \left\{{t}_{k,0}^{b}\right.+nT|n=\mathrm{0,1},2,\left.\cdots \right\}$。终端设备不会在同步完成后立即发送其数据，而是需要等待一段时间，因此不同的终端设备在发送数据时会经历不同的等待时间，产生不同的时钟漂移。通过时钟漂移速度的模型，可以计算得到不同终端设备的时钟漂移，并且选择最佳的同步时间。如终端设备i在发送其数据时的时钟漂移为：

式中，$ {t}_{k}^{b} $到$ {t}_{i}^{s} $为终端设备从同步完成到数据传输等待的时间；$ {s}_{i} $为由上述模型得到的时钟漂移速度。

终端设备的时钟漂移会使其数据传输偏离原有的时间，时钟漂移越大，传输可能越会破坏MAC协议的传输调度，导致终端设备之间发生信号冲突。 通过为每个时隙设置保护时间，为终端设备的时钟漂移提供一定的容错能力，作为时钟漂移程度的阈值^[7,17-18]。此外，具有不同扩频因子的LoRa信号传输会经历不同的传输时间，因此应针对不同的扩频因子，对保护时间进行相应的调整^[9]。根据终端设备的时钟漂移和保护时间的不同，定义终端设备i的同步精度如下：

式中，$ {g}_{i} $表示终端设备i的保护时间，且与其使用的扩频因子相关。若$ {A}_{i}\le 0 $，表明终端设备i的时钟漂移在可接受的范围之内，否则，其时间同步无效。根据文献[9]，本文计算不同扩频因子的保护时间如表1所示。

表  1  不同扩频因子的保护时间

扩频因子	7	8	9	10	11	12
保护时间/ms	15.25	20.5	31	52	94	178

下载: 导出CSV 

| 显示表格

2.1.2   多网关模型

多网关场景增加了LoRa网络中时间同步方案的复杂度，因为网关可以在不同时间以不同的扩频因子广播它们的同步报文。因此，终端设备必须选择一个扩频因子和同步时间来接收同步报文，这个选择可决定终端设备时间同步的精度。

本文目标为通过合理安排扩频因子和同步时间，提高同步精度以避免传输冲突，并提高LoRa网络的可靠性。具体来说，网关考虑其覆盖的终端设备并选择最佳同步时间，终端设备考虑不同网关为其带来的同步精度，选择网关并接收其同步报文。本文将此问题归纳为优化问题，令整个网络中时间同步失败的终端设备数量最小，为：

式中，N为网络中终端设备的数量；$ {{x}}_{i} $是二进制变量。若终端设备i的时钟同步精度在可接受的范围内，即$ {A}_{i}\le 0 $，则$ {{x}}_{i}=0 $，否则$ {{x}}_{i}=1 $。

式(4)中的约束条件(C1)定义了终端设备和网关的匹配关系。每个网关k在时间$ {t}_{k}^{b} $以扩频因子$ {\mathrm{s}\mathrm{f}}_{k} $广播同步报文，由此可以组成参数集合${P}= \left\{\right(\mathrm{sf}_{0}^{b},{t}_{0}^{b}),(\mathrm{sf}_{1}^{b},{t}_{1}^{b}),\cdots ,(\mathrm{sf}_{k}^{b},{t}_{k}^{b}\left)\right\} {S}{i}$。由于每个终端设备都需要从某个网关处接收同步报文，它们必须从该集合中选择一个参数。

式(4)中的约束条件(C2)限制了终端设备i从网关k接收同步报文的扩频因子范围。由于使用不同扩频因子的LoRa信号可实现不同的传输距离，对每个终端设备i，都存在一个最小的可以保证i和k之间通信的扩频因子$ {\mathrm{t}\mathrm{h}}_{i,k} $。约束条件(C3)和(C4)则分别约束了时间同步过程中同步时间和终端设备传输数据的时间范围。

2.1.3   复杂性分析

由于上述问题的最优解取决于网关和终端设备的匹配以及同步时间的选择，因此搜索空间与终端设备、网关的数量(即N和K)和时隙数量相关，即O((SN) K)。此外，上述问题可以被规约为经典的NP难问题——整数规划问题。因此本文提出了一种基于遗传算法的启发式算法来计算终端设备和网关的同步时间和扩频因子。

2.2   同步时间与扩频因子选择算法

基于遗传算法对上述问题进行求解，通过获取以下内容来解决式(4)：1)网关广播同步报文使用的扩频因子和同步时间；2)终端设备接收同步报文的扩频因子和同步时间。

具体地，首先生成个体的初始种群，其中每个个体由LoRa网络中的参数选择编码的染色体表示。为了衡量个体染色体的适应性，算法将式(4)中的优化目标进行取倒数变换并作为拟合函数，令算法最大化。通过对每条染色体的评估，算法选出与前一个种群相同数量的染色体并产生下一代个体，采用轮盘选择方法^[19]将选定的概率分配给染色体。使用选定的染色体进行交叉以产生后代，同时以较小的概率产生突变。该算法通过迭代生成和选择新的染色体，逐步提高LoRa网络的同步精度。算法在优化目标的提高值达到阈值δ或算法执行到第500代时停止，上述算法描述如下。

算法 1　LoRa时间同步算法

population=Initial()；

while ${\varDelta _{{\rm{obj}}}} < \delta$ and ${\rm{iter}} \le 500$ do

For indiv∈ population do

measure.append=Fitness(indiv)；

probabilities=Roulette(measure)；

For indiv∈ population do

parent.append(indiv, possibilities[indiv])；

offspring=Crossover(parent,rate)；

population=Mutation(offspring)；

calc($\dfrac{1}{{{\rm{object}}}}$)；

2.3   移动感知的自适应同步算法

当LoRa网络被首次部署且终端设备位置固定时，2.2节中的算法会为终端设备进行时间同步。在实际应用中，部署在公交车或动物等移动物体上的终端设备可能会跨越不同网关的覆盖范围。

由于LoRa网络中的时间同步需要终端设备和网关通过扩频因子进行匹配，终端设备的移动性会显著影响时间同步的性能。首先，当终端设备移动到新的网关的覆盖范围时，它可能使用与新网关不同的同步时间和扩频因子，且无法接收其同步报文，也无法正常完成时间同步。其次，移动的终端设备很难重新连接到新网关，因为它可能会与其他终端设备使用相同的扩频因子，产生信号冲突。在这种情况下，该终端设备会与LoRa网络断开连接，无法被服务器或网关发现，也无法与新的网关建立通信以获取新的扩频因子和同步时间。

本节提出了一种自适应算法来解决上述移动性问题。利用终端设备可以同时被周围多个网关收到的机会，令移动的终端设备在周期内持续监听信道，直到它们可以从某个网关收到同步报文。

当一个终端设备移动到另一个网关的覆盖范围时，如果它的数据传输与新网关下的其他终端设备没有冲突，服务器就可以识别它，并通过新网关将新的同步时间通知它，以便该终端设备可以在下一个周期完成时间同步。但是，如果终端设备与新网关范围内的其他终端设备发生冲突，服务器将无法意识到其移动性，终端设备将尝试以旧的同步时间接收同步报文，导致同步失败。因此，若终端设备在3个周期内无法收到同步报文，自适应算法将令其持续监听信道，直到收到新的同步报文。

另外，只有当终端设备和新的网关使用相同的扩频因子时，上述方案才能工作。然而，在实际应用中，移动的终端设备可能无法从新网关接收同步报文。算法利用终端设备的数据可被周围多个网关接收。传统做法会在在远端服务器上对多个网关接收到的冗余数据进行去重，但是，冗余数据可以表明哪些网关覆盖了该终端设备。同步报文广播时，除了时间戳信息外，还包括所有周围网关的参数。当终端设备与网络断开连接并且无法被服务器注意到时，自适应算法令其使用周围网关的扩频因子持续监听以接收同步报文。如果在一个周期后没有收到同步报文，终端设备将选择另一个网关的扩频因子并继续监听。自适应算法的处理流程描述如下。

算法2　移动感知的同步机制

function Server(){

if Receive(device_i) do

if gateways_rec ≠ gateways_old do；

send(params, gateways, device_i)；}

function Enddevice(){

${\rm{SF = \{ }}{\rm{sf}}_0{\rm{,}}\;{\rm{sf}}_1 \cdots {\rm{sf}}_k{\rm{\} }} $；

fail=0；

while True Do

receiveSync()；

if FailReceive() Do

fail+=1；

if fail==3 Do

listening(SF)}

以图5为例，终端设备最初被左侧的两个网关覆盖，并从①号网关接收同步报文。当此终端设备远离①号网关但仍被②号网关覆盖时，服务器可以根据①号网关无法接收到终端设备的信号来识别该情况。即使终端设备无法再从①号网关接收同步报文，服务器仍然可以通过②号网关同步它。当终端设备继续移动到位置③号时，其上行链路将与其他终端设备发生冲突。在此情况下，终端设备不能被③号网关同步。因此，终端设备将持续监听③号网关的扩频因子以接收同步报文，并重新连接到服务器进行时间同步。

图  5  移动感知的自适应算法

下载: 全尺寸图片 幻灯片

3.   实验及结果分析

本文在真实的LoRa平台和仿真平台NS-3 上进行了一系列实验^[20]。

3.1   对比工作

将本文提出的方法(用Mats表示)与Lightweight-sync和TS-LoRa进行性能比较，后两者都是LoRa网络中由服务器触发时间同步的方案。在Lightweight-sync中，网关在每个周期开始时广播同步报文，而TS-LoRa则在周期结束时进行时间同步。

3.2   对比指标

使用以下指标评估时间同步的性能。

1) 时钟漂移：当终端设备发送数据时，其本地时钟和全局时钟之间的差值。为简化表示，本文将负值的时钟漂移转换为正数。

2) 同步精度：本文用时钟漂移没有超过保护时间的终端设备的比例来表示LoRa网络的同步精度。

3) 时钟漂移的容限：时钟漂移与保护时间的差值，用于表示终端设备当前的时钟偏移与成功的时间同步的差距。

3.3   基于真实LoRa网络的实验

3.3.1   实验设置

LoRa网络包括两个网关和10个终端设备。本文将Arduino Uno与工作在433 MHz频段的InAir9B模块(LoRa信号收发器)相结合，作为LoRa终端设备，并使用RAK2245 Pi Hat LoRa模块和Raspberry Pi 3构建LoRa网关。每个终端设备都配备了OriginGPS ORG1411模块，用以收集真实的全局时钟^[6]。

每个终端设备定期向网关发送数据(实验中设置为60 min)，作为物联网应用中常见的数据收集行为。实验使用两个扩频因子7和10发送数据，带宽和编码率固定为125 KHz和4/5^[21]。为了排除信号冲突的影响，实验将10个终端设备分配在不同的时间发送数据，保证在传输过程中互不重叠。每次实验持续3 h，包含3次时间同步，实验重复5次。

3.3.2   同步时间的影响

实验首先部署1个网关和10个终端设备来展示同步时间选择对性能的影响。终端设备每60 min发送1次数据包，并在给定时间同步其本地时钟。由于不同的扩展因子7和10用于向网关发送数据包，因此终端设备对时钟漂移的容忍度不同。

图6显示了终端设备在发送数据时的时钟漂移。可以看出，同步时间不同，终端设备的时钟漂移有很大不同，因为这个终端设备从同步完成到发送数据的等待时间不同。此外，图6中的虚线表示不同终端设备的保护时间，结果表明本文方法可以保证大多数终端设备的正常同步，而Lightweight-sync和TS-LoRa都存在无法正确同步的终端设备。

图  6  终端设备的时钟漂移

下载: 全尺寸图片 幻灯片

3.3.3   扩频因子选择的影响

两个网关分别以扩频因子7和10向终端设备广播同步报文，设备使用其中之一以不同的同步时间接收。实验将权重参数$ \mathrm{\alpha } $设置为0.5并计算扩频因子和同步时间，然后更改使用某个扩频因子的终端设备的数量。图7的结果表明，在多网关场景中，本文方法可以充分利用多网关的不同扩频因子来提高网络的同步精度。此外，与单网关LoRa网络相比(即所有终端设备使用相同的扩频因子)，本文方法可以从多个网关中受益更多，同步精度比使用扩频因子7提高50%。

3.3.4   移动性的影响

实验在校园内部署两个网关，分别以不同的同步时间和扩频因子(7和10)广播同步报文。10个终端设备首先放置在只有一个网关可以覆盖的地方。1 h后，它们被带到另一个网关的覆盖范围。上述过程重复6次，即终端设备在每个网关的覆盖范围内停留3 h。

图8选择了4个有代表性的终端设备来显示它们在实验期间的时钟漂移。可以看出大多数终端设备在移动到另一个位置后仍然可以进行同步，且时钟漂移会周期性地突然下降。另外，某些终端设备无法像其他终端设备一样正常同步，如2号和4号终端设备在第1.65 h表现。这是由于新网关在2号和4号终端设备向它发送数据后，才能感知到其移动性，并向它们广播同步报文。

图  8  移动终端设备的时钟漂移

下载: 全尺寸图片 幻灯片

图  7  扩频因子选择的影响

下载: 全尺寸图片 幻灯片

3.4   基于NS-3的大规模仿真实验

3.4.1   实验设置

NS-3仿真实验是基于文献[22]提出的LoRa网络模块，支持多网关场景下的数据传输。半径1 km的范围内部署了不同数量的网关和终端设备。实验使用LoRa中所有6个可用的扩频因子，终端设备每60 min向网关发送一次数据，且它们的传输互不重叠。

3.4.2   时间同步精度

图9展示了3种时间同步方法的同步精度。终端设备的数量从100增加到300，网关数量从1增加为3。为清晰表示，本文将同步精度表示为“时钟漂移超过保护时间的终端设备的百分比”。当部署更多的终端设备时，未同步的终端设备百分比会增加。其原因是终端设备越多，仅用一个同步时间对所有终端设备进行时间同步就越困难。但是在100个终端设备和一个网关的情况下，本文方法比Lightweight-sync和TS-LoRa的同步精度分别提高了58.6%和61.1%。此外，在终端设备数量相同的情况下，可通过部署更多的网关来提高同步精度，这是由于终端设备可以选择更适合的网关来提高同步精度。随着网关数量的增加，提升空间也在扩大，同步精度可以进一步提高。

图  9  同步失败的终端设备百分比

下载: 全尺寸图片 幻灯片

3.4.3   时钟容限的CDF

图10显示了3种同步方法的时钟漂移容限的累积分布函数(cumulative distribution function, CDF)。图中的Mats-1-100表示使用部署一个网关和100个终端设备，负值表示时钟漂移没有超过保护时间，而正值表示同步失败。结果显示，本文方法的时钟漂移容限主要分布在负值区域内，而另外两种方法的时钟漂移容限几乎有一半落在了正值区域。

图  10  时钟容限的CDF

下载: 全尺寸图片 幻灯片

4.   结 束 语

本文提出了在多网关LoRa网络中提高网络同步精度的时间同步机制。综合考虑同步时间和扩频因子选择的影响，将问题归纳为优化问题，由于该优化问题的NP难特性，使用了遗传算法来求解同步时间和扩频因子的选择。此外，为了应对终端设备的移动性，本文使服务器能够感知终端设备的移动性，并令新的网关通知其新的同步时间和扩频因子。如果服务器丢失了移动终端设备，终端设备将持续监听信道以重新连接到服务器并同步其时钟。在真实的LoRa网络和仿真实验平台上的大量实验表明，与其他现有方法相比，本文方法可以实现更高的时间同步精度。