Adaptive Allocation of Network Resource
一、 前言
文章选于ICNP2020，作者提出了AdaLoRa，一种细粒度的模型，能够对动态网络进行资源分配，并最大化LoRa网络的lifetime。不仅仅要实现资源分配，还要使分配的结果更为公平。具体表现为，网络中出现第一个电量耗尽的设备时，其他设备还剩余多少电量。
查询最后结果得知，这个lifetime的时间单位是年。在之前的论文中，我们分别关注了网络协议的设计以及路由决策问题。而网络部署和网络结构设计对我来说仅停留于概念。考虑这样的工程场景，我需要搭建一个带地面站的机群局域网，怎么搭建？是否有效？是否有水平？可靠性、稳定性如何？再或者，一个成熟的项目具备哪些评价指标，能否被同行认可？这篇文章解决了我的一些问题。
二、 文章概述
LoRa网络的优点是通信范围大，终端设备低功耗。但是，也因为范围大的特点，为了把信息送到远处的gateway，需要使用大的扩频因子（SF）和高的传输电压，因此这些设备的电量可能就会被先耗尽。且由于LoRa的特点之一是SF在网络中执行多路复用，选用相同的SF或channel可能会发生碰撞，需要重传。而且在传输过程中，可能会影响信号质量，造成收到的信号和真实的信号不一致，在这种情况下也需要重传。
EF-LoRa虽然考虑了能量公平和资源分配问题，但是它采用静态的资源分配方式且只在初次部署网络时分配一次。且没有利用LoRa采用汉明码能为信息包纠错的特点，属于packet-level，而非细粒度的。随着运行时间的增加、网络的动态变化，可靠性明显降低。因为它缺乏适应动态变化的能力，缺乏“稳定回路”。
作者采用了RS码，开发了一个更为细粒度的模型，可以通过控制冗余位来降低PER，并且该方法能够适应网络的动态变化，可以有效的实现能量公平的资源分配，增加网络的lifetime，相比于EF-LoRa有很大的提高。关于LoRa网络再补充一点，LoRa不同于无线传感器网络和蜂巢网络，它是单跳的，因此作者认为它不涉及路由决策问题。上行：终端设备>>gateway>>server。下行：server>>gateway>>server。并且，设备发送信息包以广播的形式，所以就可能有多个gateway收集到信息包，gateway再转发给server，这就可以增加设计的冗余，更为稳定、有效。
三、 算法设计
作者将最大化lifetime的问题转化为优化问题，每当网络链接动态变化时就求解一次。下式L中的四个变量分别为：扩频因子、传输电压、频道、编码率。
- SF：影响通信范围和数据速率。
- 传输电压：影响能量消耗和通信范围。
- 频道：多路传输减少干扰。
- 编码率：RS码代替汉明码。（由于LoRa中已经集成了汉明码，因此作者是在packet被汉明码编码后再用RS码编码一次）
如果要对网络中所有设备进行求解，这不太现实，因为从N个设备中任意挑选两个更改其变量都会是一个计算度
n
2
n^2
n2的问题，因此直接求解会得到一个NP-hard问题。而且，如果一次调整的设备过多、周期时间过长，网络状态可能会先于指令发生变化，也就是说指令”已经迟了“。
因此，在资源调整的时候，从离得比较近的设备开始，距离远近可以用延迟大小来衡量。对设备按延迟排序，将其从所有设备的大集合N中，分出若干个subsets子集合。然后根据他们目前的分配情况估计状态，并设立一个阈值，将预计提升结果与当前状态估计结果相比较，如果带来的提升能超过这个阈值，就应用它。同时，server>>gateway>>device.这一轮周期结束。
网络的lifetime定义为，所有设备中lifetime最小的，也就是只要有一个设备的电量先耗尽，网络寿命也就到此为止了。下式，是对没有接收到调整决策信号的设备的lifetime计算，形式很简单，总的能量除以一轮周期中设备的传输消耗能量和睡眠消耗能量再乘以周期时间。其中传输能量考虑了重传的情况，r代表PER-packet error rate。
下面的公式和上面的公式相比，多了接收决策信息所消耗的能量。集合U代表收到决策包，需要改变自身决策状态的设备。
可以发现，其中比较关键的地方在于r，如何来衡量PER，作者开发了一种细粒度的模型。从干扰等可能影响信号质量的因素来建模并计算r，相关数学公式较多，这里便不再介绍。最后，作者通过这种细粒度模型将PER和BER建立起了联系。
算法的伪代码如下：
四、 算法评估
作者选取EF-LoRa作为对照，选取了网络寿命、网络剩余能量作为评价指标，并讨论了实验过程中阈值对算法和延迟的影响。
实验准备：20 end devices、4 gateways。覆盖了校园中1.5平方公里的面积，gateway被放置在建筑物的顶部，可以通过开关来调整gateway的数量，从1-4进行实验。终端设备部署在静态网络中，并且不会移动。
- end device 实现：Arduino Uno结合RFM95W模块（LoRa信号收发器）在470MHz频段（中国是470MHz）工作。
- gateway 实现：RAK2245 Pi HAT Board 配备 SX1301。
- 为了模拟干扰环境，用4个channel、3个最大占空比为10%的SF，模拟一个具有约20×2×2×10=800个终端设备的网络，使用八个信道、六个扩展因子和1%的占空比。
可以看到，AdapLoRa这种动态的适应方法相比EF-LoRa不仅提升了网络的寿命还使得分得更加公平。
AdapLoRa performs better with larger thresholds (i.e., 20%) when the network lifetime is long (i.e., 3.6 years), but it performs worse when network lifetime is less than three years. The reason is that sometimes AdapLoRa with a large threshold cannot achieve a large improvement thus adaptation is not performed, and network lifetime is not improved.
有时网络无法实现较大的改进，因此不会执行自适应。关于图9，高阈值带来了高延时我的理解是，作者设计的延迟不仅包括了自适应决策包传输的延迟，还包括了算法运行的时间。所以这也能反映为什么阈值会对延迟产生影响。说明，高阈值增加了算法运行的时间。因为低阈值能容易达到，特别是对离得比较近的设备，算法容易更新。
五、 工作总结
我想补充一下资源分配的过程，设立这个阈值和分组的好处还有一个地方体现在，我先让反应快速的设备调整，在下一轮中，这些离得近也就是反应快速的设备不一定会带来更大的提升，因此我对下一个集合进行优化，可以把距离从近拉到远。从而避免了求解所有设备的Li，选取最小的Li再对其进行优化，这样复杂而可能会带来NP-hard的方法。总结下来，收获还是蛮大的。