艾克斯-马赛大学博士学校184计算机科学与系统实验室为获得博士学位而提交的论文学科：计算机科学塞德里克·贝伦格大型低功耗网状网络：用于同步、距离测量和分区的可扩展的低功耗网状网络：用于同步、距离测量和分区的最于2021年1月14日在评审团面前进行了答辩，评审团成员包括：伊曼纽尔·戈达尔艾克斯-马赛大学，LIS检查员克莱尔·古尔索住处：里昂、因里亚和CITI审查员托马斯·诺埃尔斯特拉斯堡PU大学，iCube报告员彼得·尼伯特WCF艾克斯-马赛大学，LIS主任娜塔莉·米顿Inria Lille-Nord Europe博士，FUN报告员凯文·佩罗特WCF艾克斯-马赛大学，LIS联合主任国家论文编号/本地后缀：2021 AIXM 0024/002 ED 184本作品根据知识共享署名-无商业用途-无修改4.0国际许可证的条款提供摘要3微控制器，这些小型、低成本的嵌入式计算机，让我们今天有了远大的目标。它们的低消耗和设备使它们能够与环境互动，同时通过电波向我们传达它们的那么，为什么不形成一个大的网络来管理和监控一个家庭，一个工业综合体，甚至整个城市呢？ 这样的扩展被证明是困难的，并且即使已经存在许多用于管理网状网络的解决方案，鲁棒性和效率的要求也导致了一些折衷，将实现的简单性、低功耗以及网状网络的理想传递到完全对等通信的第二平面。在这篇论文中，我们贡献了一个替代的解决方案，我们实现了我们自己的妥协：我们正在寻找一个最小的方法，允许建立大规模的网状网络，能源自给自足，并能够自我管理没有协调员。我们的第一个选择是编程模型。我们希望以元胞自动机的方式在同步循环中运行分布式应用在实践中建立这样一个模型使我们对同步问题产生了兴趣：两个节点永远不会以相同的速度移动，这会导致随着时间的推移而扩大的差距，但我们需要使节点在本地彼此同步。我们提出了一个最小化的同步算法，允许建立同步执行回合。无线介质的共享性质和对干扰的敏感性不允许在无线网络中直接使用我们的同步算法因此，在第二步中，我们提出了一种为无线节点的同步提供节俭框架的协议在建立了执行同步算法所需的上下文之后 我们已经开发了一种技术，通过利用波传播的延迟和它们的时钟之间的微小频率差异，可以精确地测量两个邻居之间的距离。最后，我们考虑了集中式到分布式接口的可能性，该接口允许通过多个入口点广播数据流。摘要4微控制器是一种小型、廉价的嵌入式计算机，可以做伟大的事情。 由于功耗低，它们可以与环境相互作用，并使用无线电波向我们提供反馈。 有了这样的能力，我们可以建立一个巨大的网状网络，监视一所房子，一个工业设施，或事件一个完整的城市。然而，这种网状网络的可扩展性是一个复杂的峰值，并且许多现有的用于管理网状网络的解决方案受到鲁棒性和性能约束，会受到影响。具有低功耗、支持网状拓扑和使用对等通信的解决方案很难找到，也不容易简单化。在这篇博士论文中，我们根据自己的妥协，提出了一个替代解决方案。我们提出了一种极简主义的方法来构建可扩展的网状能量网络--自治节点，能够在没有中央协调的情况下自组织。首先，我们选择一个编程模型。我们使用同步循环运行分布式应用程序，就像蜂窝自动机一样。为了将这样一个模型付诸实践，我们讨论了同步的主题：两个节点永远不会以完全相同的速度运行，因此时钟值之间的时间偏差会增加。但是，我们需要保持相邻节点彼此同步。 我们提供了一个最小化的同步算法来设置同步执行回合。无线通信介质的共享特性及其对电磁干扰的敏感性使其在没有调整的情况下不适合我们的同步算法。 因此，我们提出了一个协议，为我们的同步算法在无线节点上工作提供了一个必要的节俭框架。一旦我们能够在节点上运行同步算法，我们就可以通过使用软件技术添加地理定位来简单地部署这样的网络。 我们利用节点时钟速度的微小差异来精确测量由邻居交换的无线电波的传播延迟。最后，我们考虑一种将集中式系统与我们的分布式网络接口的方法，允许使用多个入口点广播数据流。谢谢你5当然，我首先要感谢我的论文导师Peter Niebert，他从本科二年级起就一直陪伴着我，帮助我发现了微控制器和分布式算法。 我在电子学和网络方面的大部分知识都要归功于他，正是由于他，我才能在论文中研究各种各样的、令人兴奋的主题，这些主题经常在理论和实践之间摇摆不定。然后，我想特别感谢我的论文联合主任凯文·佩罗特，他总是在我怀疑的时候出现，他对手稿进行了大量的校对和修改总是积极和相关的，他极大地帮助带来了必要的严谨性，手稿以及我感谢M.感谢Thomas Noël和Nathalie Mitton女士荣幸地担任我的 我还要感谢Emmanuel Godard和Claire Goursaud女士同意成为我的论文评审团的一员。我要感谢LIS实验室的所有同事，特别是Manon、Sébastien D.、弗朗索瓦、西奥多、阿米莉亚、辛迪、弗兰克、弗洛里安、蒂博、达米安、帕科姆、何塞-路易斯、迪迪埃、利奥等，我能够与他们 我要特别感谢我的同事塞巴斯蒂安·R. 还有杰里米，他总是愿意花时间对演示、章节或插图提出批评意见，这些年来，他一直有耐心支持我以前的中心主义他们感谢我的母亲，她没有计算机科学的高级背景，仔细阅读了论文的不同版本，并检查了不同的部分是否可以独立理解和阅读。他的建议极大地促进了叙事的普及，并使其阅读更加流畅。也感谢我的祖母在语法和拼写方面的专业知识，她纠正了大量的错别字感谢我在初创公司LED'sChat的同事们最后，感谢我的家人，我的父亲和我的妹妹在准备答辩的帮助，并感谢所有那些谁来参加我的论文答辩这么多，尽管事实上，它是在这样一个奇异的时期（2021年1月）在视频中进行材料表6目录61引言101.1计划111.2目标、极简主义和交互式可视化131.3微控制器：基础141.4时钟和时间161.4.1信号和时钟前端1.4.2时间：一系列1.4.3外围计数器181.4.4对事件的看法181.4.5频率漂移201.5能源消耗221.5.1能源1.5.2外围设备的消耗231.5.3"低能量"操作模式231.6过渡期242有线同步252.1同步抽象262.1.1一般原则和优点262.1.2第27层的功能2.1.3执行情况292.2同步：最新技术水平2.3时钟和时间表模型2.3.1标称频率和有效频率312.3.2随机抖动312.3.3示例：抖动322.3.4示例：脉冲同步脉冲同步322.4原始版本：GooseSync332.4.1选择名称Goose Sync342.4.2功能352.5行为和2.5.1领导者和追随者362.5.2向单一领导者362.5.3内隐记忆和加速传播37材料表72.6实证研究382.6.1离散事件模拟392.6.2通过43个转弯进行模拟2.6.3物理演示者：LED2.7分析研究的要素2.7.1脉冲同步有界鹅同步方差（√n）482.7.2假设：快速传播速度与直径无关492.7.3直径的弱依赖性方差492.8结论503网状网络的无线同步523.1中无线533.1.1无线电通信：物理和实践533.1.2与有线电视相关的困难563.2最新技术水平3.2.1媒体多路复用技术573.2.2现有介质访问协议3.2.3网状结构、低能耗和效率之间的折衷583.2.4我们的建议：MeeMSyP593.3通过叠加60多路复用3.4MeeMSyP61协议3.4.13个通道中的协议组织623.4.2完整伪代码703.5能源消耗773.5.1收听消耗相当于3.5.2与使用天线79相关的延迟3.5.3循环比：节约使用3.5.4时间：1秒保持反应803.5.5按频道划分的通话时间分布3.5.6节能模式3.5.7结论833.6稳定性、鲁棒性和可扩展性843.6.1同步：相消干涉843.6.2区分同步脉冲串和环境噪声853.6.3针对网络外部发射机的安全性和鲁棒性3.6.4针对恶意设备的安全性3.6.5平均值873.6.6模拟893.7开放：能源的收获3.7.1太阳能电池板收集的平均能量953.7.2收集和储存3.7.3利用剩余3.8结论974小于时钟周期的延迟测量4.1微控制器延迟测量基础1004.1.1低分辨率：超声波101材料表84.1.2高分辨率：电磁波1024.2短时间的测量：最新技术水平4.2.1逻辑门链方法1034.2.2双振荡器Vernier标度法4.2.3ToF106集成电路4.3理想化模型下的协议1074.4响应时间1074.4.1描述和直觉1094.4.2时间表的计算：正式说明1154.4.3多次扫描：δ大1184.5飞行时间测量1224.5.1飞行时间测量协议：描述和见解1234.5.2时间计算：正式说明1274.5.3模拟1314.6与物理现实1344.6.1时钟速度的漂移1354.6.2模拟链的影响1374.6.3原型红外飞行4.6.4无线电波飞行时间测量装置4.6.5实验条件4.7结论1495干涉定位和观测5.1最新技术水平5.2型号1535.31D干涉模拟1545.3.1使用1555.3.2照片1D1555.4实际实现1565.5结果和局限性1575.6平面与空间的推广5.6.12D干扰1585.6.22D图像1585.6.3结论、观点和应用1606将未加权网格平衡划分为相关区域1626.1引言1626.1.1最初动机162材料表6.1.2分区问题和变体的陈述1636.1.3165计划6.2相关工作1656.3型号1666.4NP-难度1686.4.1建筑的直觉1696.4.2减少：从施工6.4.3减少的校正和计算173材料表9×6.4.4相关区域的r-平衡划分（rBCP）1776.5Q平方连通网格的划分1776.5.1q-平方连通性：全局定义1786.5.2q-平方连通性：局部定义1806.5.3非根变体182的算法6.5.4模拟1896.6网格系列2，1916.6.1模拟1936.6.2使用1936.7展望和未来工作1946.7.1算法的优化6.7.2面向根问题的算法1957结论和展望197一般参考书目200个人参考书目204101 简介微控制器是微型计算机，能够执行程序，并根据在模拟或数字输入上观察到的事件产生物理动作作为输出。例如，当微控制器检测到来自红外存在传感器的电信号中的显著变化时，微控制器可以点亮灯。 微控制器是廉价、可靠且需要很少功率的集成电路。微控制器组可以通过电缆或无线电收发器进行交互和交换信息。 因此，将大量微控制器互连以形成传感器网络并访问更广泛的应用领域是令人感兴趣的：在不部署重型基础设施的情况下，这种传感器网络一方面允许通过收集大地理区域的数据来监视和映射环境，另一方面允许对环境做出反应以响应事件。 该应用领域从军事领域延伸到公共领域，在健康、工业、生态以及家庭自动化领域具有许多实际用途。微控制器网络目前正处于蓬勃发展的阶段在"物联网"的旗帜下，用于创建微控制器网络的技术和方法比比皆是。 与传统计算机不同的是，传统计算机有既定的标准来规定不同的网络节点应该如何通信（例如IP互联网协议、用于无线链路的Wifi和用于有线链路的以太网），目前还没有事实上的标准来建立微控制器网络。 此外，各种可能的应用和微控制器的低资源使得不可能存在满足所有用例的通用方法。然而，所有这些技术的一个共同点实际上，网络协议的主要目标是控制信息的流通。然而，为了使这种流通有效，没有假日或延误，网络成员之间的通信必须是有序这种基本的调度任务是复杂的，特别是当考虑大型网络时，因为一个节点的通信调度依赖于其邻居的通信调度，并且微控制器时钟的不精确性导致延迟或提前的时间累积。最后，物理定律限制了集中式方法的范围1引言11同步大型网络。由于电磁波的传播时间在长距离上变得不可忽略（例如巴黎和马赛之间的2.20ms延迟），因此不可能在不引入远程节点对之间的延迟的情况下此外，在有线和无线中，这种同步信号很难实现，因为为了覆盖大的区域，它需要强大的发射机或中继器，这不可避免地因此，在本论文中，我们关注两个本质上相关的问题：大规模微控制器网络;以及时间管理和测量首先，我们将了解如何使用本地同步在节点之间建立通信链路（首先是有线链路，然后是无线链路）。然后，我们将精确地测量传播延迟，以便对节点进行地理定位并绘制网络地图。最后，我们将组织数据路由，以优化从中央服务器在网络中传播和收集信息时的带宽。1.1 计划在本文中，我们提出了一套构建、管理和部署超大型微控制器网络的方法第1章是介绍性章节，介绍微控制器、其操作的基础知识以及通过时钟信号进行的时间在第一章中，我们试图建立一个管理网络通信的框架我们的网络管理基于自稳定的本地同步基元：我们通过本地补偿流中的任何延迟，为网络节点提供正确的行为，以有效地传播信息。在第2章中，我们针对有线情况研究了这种同步基元;我们对这种基元的良好可伸缩性进行了模拟器上的经验分析，并给出了一些方法来制定其性质的分析证明。在第3章中，我们看到无线通信带来了额外的约束，并提出了一个协议来克服这些约束。在这里，我们再次在模拟器上经验地验证了协议的正确行为。此外，我们还详细讨论了能耗以及如何最大限度地降低能耗，以便使用产生几微安电流的光伏电源运行电网第4章和第5章继续研究时钟的同步和漂移，重点讨论时间和时钟漂移的测量。1引言12来吧。我们使用时钟漂移作为资产：它们允许在微控制器的时钟信号所取的不同相位值下观察周期性在这些章节中，我们提出了两种不同的方法来精确测量无线电传输的传播延迟，以测量微控制器对之间的距离，而不需要额外的硬件。 这对我们的网络有许多应用，包括部署时在节点空间中的位置。在第4章中，我们测量了两个微控制器（一个发送节点、一个接收节点）之间的短距离（10米）往返延迟我们通过在智能选择的时间帧上进行上采样来获得这样的分辨率：该时间帧实际上由发送节点和接收节点的时钟前端之间的渐进相位差的周期来限定我们将看到，我们介绍了我们的实验结果，并详细说明了补偿电源电压、温度和自增益等寄生效应所在第5章中，我们通过观察两个发射机节点之间故意干扰的影响来测量距离。通过故意在多个节点的传输之间产生干扰，我们产生了平稳波。在这里，我们再次使用节点时钟之间的渐进相位差来定位节点相对于这些静止波的位置我们发现，在最佳条件下，测量可以精确到几毫米以内，然而，我们将讨论获得这样的条件的困难最后，更具理论性的第6章介绍了信息从一个集中式源到一个大型分布式微控制器网络的传播。问题是带宽管理：如果服务器仅连接到网络中的一个节点，则吞吐量受到链路容量的限制 如果网络增长，添加到其他节点的链路可以增加吞吐量，同时必须决定如何通过避免来自不同链路的流的交叉来共享该吞吐量，并且必须为每个节点决定其信息源。为了解决这个问题，我们研究了如何将图划分为平衡的连通区域 我们已经在平面网格图上研究了这个问题。 对于一般情况，我们给出了NP-困难的证明。 尽管如此，通过放宽一些约束，我们提出了两种多项式算法，以解决两个直观拓扑族的实际问题。虽然因此，章节可以按任何顺序进行1简介131.2 目标、极简主义和交互式可视化在开始这篇论文时，我们的具体目标是创建和使用大规模、低成本、简单、高性能的微控制器网络，同时保持低延迟和低功耗。 为了解决这个实际问题，我们从这个目标出发，一步一步地解决了我们遇到的问题，每次都在寻找最小的可能解决方案。保持极简主义至关重要，因为我们使用的嵌入式系统资源较少，例如中端型号的64KBRAM。此外，我们必须保持准确预测由数千个微控制器组成的网络的长期行为的能力使用过于复杂的方法在理论上很难分析，在实践中也很难我们的工作以应用为导向，主要是以环境为导向的。本文档旨在保持直观性，并使任何嵌入式系统工程师都能使用我们的算法快速简单地设计具有全软件基元的大型微控制器网络，以实现我们以直观、图形和交互的方式进行推理因此，我们提出想法，并保持形式主义，以消除任何模糊，如果需要的话。本PDF文档中的每一章都配有 每个模拟都在一个HTML文件中用javascript编码，该文件的源代码链接到该模型。 只需单击每一章中出现的超链接，即可在最新的浏览器中启动动画1。1. 使用Mozilla Firefox 76.0.1（64位）开发并测试模拟。1简介141.3 微控制器：基础知识FIGURE 1.1微控制器是当今它们嵌入在大多数交互式设备中，这些设备可以测量值或它们单独取代了这些系统中的大多数专用电子电路我们可以举出一些经典的例子：遥控器、时钟、秤、恒温器、连接的物体。微控制器，简称µC，是一个完整的多功能计算机，集成在一个小芯片中，能够处理信息，监控事件，并根据这些事件采取为此，微控制器包括处理器、程序存储器（闪存）、工作存储器（RAM）以及用于管理时间和通信的各种特定于每个型号的外围设备（1.1）。顾名思义它具有物理控制系统的传感器和致动器所需的资源。该芯片实际上能够例如，微控制器可以点亮LED灯相反，术语微处理器指的是一个计算单元，它不能在没有外围设备支持的系统中单独工作。1简介15和外部存储器。如今，嵌入式系统设计人员有事实上，制造商提供了广泛的模型，以满足大量的限制。其中一个限制是外形，一些µC，如Attiny 20 UUR，可以容纳在一个1.5x1.5mm的正方形内，而其他需要更多输入/输出引脚或需要提供更多电流的µ C另一个限制是目标应用领域的限制 根据所需的用途，制造商将外围设备集成到微控制器中，以专门解决特定任务。 这些外围设备包括：用于信号处理的浮动计算单元;用于从传感器获取数据的类比到数字转换器;无线电收发器（用于连接对象的蓝牙）;以及电机控制。 此外，为了满足行业的质量要求，同一芯片有不同的鲁棒性等级，标准级、汽车级或军用级。最后，最后一个约束是成本。 最基本和晦涩的型号2，如制造商Padauk的PMS150C，价格不到0.03 C3，而装备最好的型号很少超过50欧元。根据经验，成本低于2C4的型号足以满足绝大多数应用。在本文档中，我们将以Nordic制造商（编号ORDIC-SEMICONDUCTOR2017）的nRF 52832微控制器为例，该微控制器配备由于其低成本，中端微控制器在资源和性能方面远远无法与台式机相事实上，微控制器不是为执行各种任务而设计的计算机，它们的资源足以满足精确的以下是微控制器的经典特性的值范围：微控制器通常配备有对于执行频率关于存储程序的内存（闪存ROM，相当于硬盘驱动器），我们不再谈论几十千兆字节，而是谈论几十/几百公斤字节，甚至兆字节的高端。最后，对于RAM，我们将以几十千字节为单位进行讨论。下表列出了从nRF52832技术文档中提取的特征2. 未翻译的文档、难以访问的硬件和软件开发工具3. 型号PMS 150 C-S 08售价0.024美元（@1000件），LCSC价格于2020年8月12日上调4. nRF52832型号的价格为1. 83美元（@1000件），LCSC价格于2020年8月12日上调5. 具有多个内核的微控制器是存在的，但它们的使用并不常见。1引言16特征值单位CPU频率64 MHz 外围设备频率 16 MHzRAM内存64 KB闪存512 KB总线宽度32位无线电速率2 MbpsEEMBC核心标记评分215表1.1具体的。此外，为了说明最新一代的8位AVC微控制器atmega系列，包括著名的atmega328p电源Arduino板，得分为20分（atmega4809）。与在PC上编程时所需的资源相比，这些低资源乍一看似乎非常有限事实并非如此：与必须运行复杂操作系统、用户应用程序、高分辨率图像等的台式机相比，它对内存和执行速度的要求要低得多在微控制器上，我们实际上很少耗尽内存，矛盾的是，微控制器（重新）的工作速度比台式机快这是因为PC运行着一个复杂的操作系统，该系统并行处理大量的进程。事件，例如输入和输出，在被最终考虑之前，必须通过大量的物理和软件接口层，例如缓冲器和数据总线。累积的延迟会产生毫秒级的延迟。相反，微控制器仅专用于单个应用，通常不使用通用操作系统，并且I/O事件直接由中断机制处理，这使微控制器具有微秒级的响应能力。因此，微控制器是实时系统。1.4 时钟和时间测量在这篇论文中，我们将集中在时间和它的安全在本节中，我们将介绍6. Benchmark eembc Coremark，分数考虑操作管道、内存访问（带缓存）以及整数操作1引言17允许微控制器执行这种测量的机制。我们将看到，我们还将看到，微控制器使用计数器设备来测量两个事件之间的延迟。最后，我们将研究测量时间的准确性，以及两个不同的微控制器以略微不同的速度进行的测量的一致性。1.4.1 信号和时钟前端微控制器是一个主要是同步的系统。为了有效地杀死每一个动作，他需要此顶部用于对操作进行排序，以事实上，在没有同步不同组件的事件的情况下，微控制器的每个部分都以自己的速度运行，这不可避免地产生不一致例如，微控制器的处理器部分可以在存储器部分的响应在总线上可用之前读取存储器部分的输出这些顶部由时钟提供，时钟是中控制器内部的电子电路，提供有规律的周期性信号 该时钟信号通常是通过将来自石英振荡器（通常在微控制器之外）或来自RC振荡器的正弦信号离散化而获得的方波信号，其中电容器周期性地充电和放电（通常在微控制器内部）。另一个例子是MEMS振荡器，即微机电系统，它由硅中的复杂机电结构组成，可以以更高的功耗为代价实现更好的特性（E PSON -DEVICE 2014）。为了获得其时钟顶部时钟信号从低逻辑电平到高逻辑电平的转换1.4.2 时间：状态的继承根据定义，时间是指环境状态的演变、一系列变化、一系列事件和进展感知时间当中间控制器响应于时钟峰值而动作这里，它的序数计数器7. 异步µC也存在，但与同步µC相比很少1引言18测量持续时间是一种相对操作，它是将环境的第一特征的演变与用作参考的第二特征的演变进行对于微控制器，该参考是其内部状态，其在每个时钟顶部更新因此，微控制器可测量的最小持续时间是时钟信号的两个顶部、两个前沿我们将此单位称为时钟周期要将以时钟周期数表示的相对测量值转换为以秒为单位的绝对测量值，可以使用制造商提供的1.4.3 外围计数器为了这些计数器可由系统随意激活或停止 一旦被触发，计数器将在时钟信号的每个新前沿自动递增。因此，要测量两个事件之间的持续时间，只需在第一个事件上激活计数器，并在第二个事件上停止计数器。然后，程序将能够稍后读取计数值，该值可通过存储器寄存器访问。1.4.4 对事件微控制器具有输入-输出支腿，允许 例如，它可以通过接收来自亮度传感器的信号来感知夜晚，并决定打开灯--通过继电器。微控制器系统地感知时钟前端上的事件。因此，在两个时钟前端或"顶部"之间发生的任何事件1引言19图1.2因此，如果在两个相同的时钟顶部之间发生两个事件，例如两个输入相继从低逻辑电平切换到高逻辑电平，则微控制器不能确定这些事件中的哪一个因此，如果两个事件之间的时间小于时钟周期，就不可能精确测量该时间我们将在后面提出一种技术来测量可重复事件的这种短持续该技术利用1引言201.4.5 频率的漂移F图 1.3时钟信号来源于振荡器产生的模拟信号，见图1.3。主要使用的两种类型的振荡器是RC（电阻器/电容器）振荡器和石英振荡器，RC振荡器通过电阻器周期性地对电容器充电和放电来工作，石英振荡器更精确地利用石英换能器的压电特性来产生正弦信号。如果通过以标称振荡频率（例如16MHz）为目标来校准振荡器此外，根据所使用的振荡器的类型RC振荡器简单、便宜且功耗低这种振荡器通常直接集成到微控制器芯片中，并用作这些振荡器的弱点是它们缺乏精确性和稳定性。事实上，不仅频率可以8. 振荡器电路所需的电容器，请参见应用说明SWRA495H（JAMES MURDOCK2015）德州仪器
