LoRaWAN 数据碎块传输算法

JiapengLi -

LoRaWAN 数据碎块传输算法

本文是《LoRaWAN Fragmented Data Block Transport Specification》协议的解读

https://lora-alliance.org/sites/default/files/2018-09/fragmented_data_block_transport_v1.0.0.pdf

《LoRaWAN Fragmented Data Block Transport Specification》 是 LoRa Alliance 为了向 LoRaWAN 中添加固件空中升级（FUOTA）功能而定制的。并且同时兼顾考虑了如下几个方面：

  • LoRaWAN 低速率传输
  • 无线通信不稳定，数据易丢失
  • 高效利用无线通信带宽
  • 理想情况下，丢包在允许范围内，仅依靠单向下行通信完成“大数据”量数据传输（大于1KB）

本文并不对 Port 201 通信做过多介绍，协议的定义比较符合设计直觉，并无太多太大的独到之处，中规中矩。这里比较令人感兴趣的是协议中提到的一种前向纠错算法。这个算法也不是 LoRa Alliance 首创的，算法作者名叫 Robert Gallager，论文（Low Density Parity Check）可以从网上下载到 http://www.inference.phy.cam.ac.uk/mackay/gallager/papers/ldpc.pdf。这篇论文比《LoRaWAN Fragmented Data Block Transport Specification》协议的页数还多，里面充斥了各种算法公式，以及概率运算等内容，对于我这样一个工程师而言有些超纲了。感兴趣的同学可以翻看一下，干货满满。

闲话不多说，对于工程师而言，这个事情的精髓是怎么把算法应用起来，用代码把它给实现了，知道算法的大致优劣进行运用就可以拿到不错的分数了。下面开始正文，把我对这个算法的理解和实现做个记录，其中的术语根据个人喜好起名，尽量贴合愿意。

概述

为了行文简便，后文对 《LoRaWAN Fragmented Data Block Transport Specification》简称为 FDBT 协议。对于数据块传输算法统称为 LDPC 算法。下面将给出一个针对 LDPC 算法的一个感性描述。

编码（Encode）

  • 算法统一对一个大的数据块做等长划分成 M 块，每块中包含的字节数 FragSize
  • 原始数据就变成了一个数据矩阵 [B1, B2, B3, ... , Bm]，矩阵长度为M，协议中由 NbFrag 定义。注意：每一个 Bx 都包含 FragSize 个字节。在看官方文档时，这个地方没能理解好导致走了很多弯路。
  • B1, B2, B3, ... , Bm 在算法中被定义为未编码数据块
  • 针对这 M 块数据，算法将进行冗余编码处理，并将其扩充为 N 块，N 大于 M。从第 M + 1 到 第 N 块数据属于编码数据块，FDBT 协议中使用 P(M, N) 标识，根据个人理解，这个标识似乎有一些迷惑性，很容易把人绕晕。这里我使用 [Bm+1, Bm+2, Bm+3, ... BN] 来标识。
  • [Bm+1, Bm+2, Bm+3, ... BN] 使用 LDPC 算法中规定的编码规则通过运算得到，运算中需要用到的输入参数有未编码数据 [B1, B2, B3, ... , Bm]，数据块向量长度 M，以及每个编码数据的下标（m+1、m+2 …… N）。
    • 首先根据编码数据块下标 Bx 和数据块矩阵长度 M 来计算出一个向量 Cx，向量 Cx 的长度为 M，成员列表为 [Cx1, Cx2, Cx3, ... Cxm]，成员取值为 0 或 1。(x = m+1, m+2, ... , N)
    • 其中Cx = matrix_line(x-m, M)。注意：matrix_line 的第一个参数对应为编码数据块的索引，例如第 m + 1 块数据应为第一个编码数据块，故此，Cx 的传参对应为 x - m。matrix_line 的本质是一个伪随机布尔向量生成器。FDBT 协议中给出了标准实现。
    • 编码数据 Bx = Cx1.B1 ^ Cx2.B2 ^ ... ^ Cxm.Bm （^ 按位异或，Cxx = 0 或 1，0.Bx = 0，1.Bx = Bx）
    • 针对每个编码数据 Bx 可以分别得到一个矩阵向量 Cx，重复以上过程可得 N - M 个编码数据块 [Bm+1, Bm+2, Bm+3, ... BN]
  • 将 [Bm+1, Bm+2, Bm+3, ... BN] 附于 [B1, B2, B3, ... , Bm] 之后可得到，编码后的全部数据块 [B1, B2, B3, ... , BN]。
  • 服务器发送数据时依次将各个数据块连同其序号发送给接收端进行解码。注意：序号必须显式发送接收端方能解码。

解码（Decode）

编码在 LDPC 算法中是很轻松容易的，因为所有材料都齐全，得出相应的输出也比较简单。但是解码重新组帧的情况就复杂的多了，因为传输过程中任何一个数据块都有可能丢失，解码过程前面数据包的恢复或者丢失与否不能影响后续过程。而且对于类似于 FUOTA 这类的应用，解码过程都是在 MCU 这类资源受限型平台上完成的，这样解码过程就不能耗费太多存储资源。在算法设计和实现的过程都需要考虑这一点。综合以上过程给出算法，下面给出的算法，其一是 FDBT 协议描述的算法，一个是 Semtech 设计实现的算法（部分由我优化）。

算法一、协议实现

  • 定义一个位矩阵 A = MxM 个点，用于存储数据块向量信息
  • 划分一个区域 S 用于接收数据，S 大小为 NbFrag x FragSize，数据正确回复后 S 中存储的数据应为 [B1, B2, B3, ... , Bm]
  • 结束的开始接收数据，假设接收到数据索引为 i ，数据为 B，通过索引判断：
  • 如果 i <= M，接收到未编码数据
    • 制作向量 C，长度为 M，
    • 设置 C1 至 Cm 为0， Ci = 1
    • 将 C 存于矩阵 A 的 Ai 位置。并将 B 写至 Si。
  • 如果 i > M，接收到编码数据
    • 利用 matrix_line 生成向量 C
    • 从 1 至 m 遍历 C，每次得到 Ck
    • 如果 Ck = 1，取 Ak 列向量
      • 如果 A(k, k) 为 0，将 C 写入至 Ak，并将 B 写至 Sk。
      • 如果 A(k, k) 为 1，C = C ^ Ak，B = B ^ Sk 并继续遍历，直至结束
  • 每次有新数据写入至 S 时，应进行一次计数，当计数值等于 NbFrag 时，证明已经接收到的数据可以重构出 [B1, B2, B3, ... , Bm]，开始恢复流程。此时 A 矩阵的对角线上应全部为1，左下角全部为0，已经完成对角化。
    • 恢复流程从矩阵 A 第 M 行开始，一直恢复到第一行结束。
    • 从 m - 1 至 1 遍历 A 矩阵，取 Ai，Si
      • 从 i + 1 至 m 遍历 Ai，取 A(i,k)
        • 如果 A(i, k) = 1，取 Ak ，Sk
          • Ai = Ai ^ Ak，Si = Si ^ Sk
    • 直至遍历结束数据重构完毕

算法二、Semtech 官方实现

算法一是一个通用型的实现，不受其他制约，缺点是当 M 比较大的时候导致 MxM 位点阵占用数据过多。算法二是牺牲了一些解析上的便利对算法一内存占用方面的不足所做的优化。

  • 思路
    • 算法一 A 矩阵记录了全部 B1 ... Bm 所对应的点阵信息，而这些数据中一部分是通过未编码数据生成的，另一部分通过编码数据生成的。当丢包率比较低的情况下 A 矩阵的浪费比较严重。
    • 算法二利用这个特性预先定义一个新的变量 T。表示未编码数据的丢包所允许的最大丢包数。同时生成对应的矩阵。仅对丢包生成恢复矩阵。当 T 等于 M 时，占用的空间与M是一样多的。
    • 变量定义：
      • lost_frm_bm：记录未编码数据帧的丢包情况（位映射）
      • lost_frm_count：记录总丢包个数
      • lost_frm_matrix_bm：所有丢包数据帧对应的编码数据位矩阵
      • filled_lost_frm_count：丢帧数据使用编码数据填充计数
    • 每次收到未编码数据帧更新 lost_frm_bm 与 lost_frm_count。
    • 每次收到编码数据帧更新 lost_frm_matrix_bm 与 filled_lost_frm_count
    • 当 lost_frm_count = filled_lost_frm_count 时，开始恢复完整数据
  • 其他信息请参见代码实现：https://github.com/JiapengLi/LoRaWANFragmentedDataBlockTransportAlgorithm，这里面的弯弯绕绕特别多，代码量不大，但是读起来还是有些烧脑

算法二带来的问题是当未编码数据丢包数目过多时，将会导致数据包无法重构。

解码算法对比

内存占用

算法一：M * M + 2 * M

算法二：T * T + 2 * T + 2 * M

运行速度

算法一比算法二应该要快很多。目前没有实际测试数据。

其他

  • 数据块长度无法均等分成 M 份怎么办？
    • 使用 Padding 做填充，并将 Padding 数目通过协议传给接收方

后记

根据 FDBT 协议的描述，其采用的 LDPC 算法在原有的算法基础上有简化，使其更适用于在 单片机上运行。

写这篇记录的过程中有了一个新的想法，由于 A 矩阵仅有对角线及上半部分有数据，那么其实可以通过这个特性利用一个三角形矩阵，替代方形矩阵更进一步节省空间。