CosMAC: Constellation-Aware Medium Access and Scheduling for IoT Satellites

Pico-satellite (picosat) constellations aim to become the de facto connectivity solution for Internet of Things (IoT) devices. These constellations rely on a large number of small picosats and offer global plug-and-play connectivity at low data rates, without the need for Earth-based gateways. As picosat constellations scale, they run into new bottlenecks due to their traditional medium access designs optimized for single (or few) satellite operations. We present CosMAC – a new constellation-scale medium access and scheduling system for picosat networks. CosMAC includes a new overlap-aware medium access approach for uplink from IoT to picosats and a new network layer that schedules downlink traffic from satellites. We empirically evaluate CosMAC using measurements from three picosats and large-scale trace-driven simulations for a 173 picosat network supporting 100k devices. Our results demonstrate that CosMAC can improve the overall network throughput by up to 6.5× over prior state-of-the-art satellite medium access schemes.

皮卫星（picosat）星座旨在成为物联网（IoT）设备的首选连接解决方案。这些星座依靠大量小型皮卫星，以较低的数据速率提供全球性的即插即用连接，且无需依赖地面网关。然而，随着皮卫星星座规模的扩大，其为单个（或少量）卫星运行而优化的传统介质访问设计遇到了新的瓶颈。为此，我们提出了 CosMAC —— 一种全新的、面向星座规模的皮卫星网络介质访问与调度系统 。CosMAC 包含一种用于物联网到皮卫星上行链路的重叠感知介质访问新方法，以及一个用于调度卫星下行流量的新网络层。我们通过对三颗在轨皮卫星的实际测量，以及对一个包含173颗皮卫星和10万台设备的大型网络进行的轨迹驱动仿真，对 CosMAC 进行了实证评估。结果表明，与当前最先进的卫星介质访问方案相比，CosMAC 能够将整体网络吞吐量提升高达6.5倍。

TL; DR

• 上行碰撞：物联网设备处于多颗卫星重叠覆盖区时，其传输会造成多重碰撞
  • 解决：采用“重叠感知”随机接入协议， 对这类"高影响"的传输进行抑制
• 下行调度：皮卫星使用全向天线，导致下行传输时对多个地面站产生“一对多”干扰
  • 解决：设计 新的调度算法 ，确保同时传输的卫星各自拥有足够数量的无干扰地面站
• 流量控制：卫星高速移动导致反馈过时，无法有效调整设备传输率
  • 解决：利用卫星信标向覆盖区内所有设备进行 广播式反馈，统一调整

Introduction

Constellations of pico-satellites (picosats) in low earth orbits (LEO) promise to enable universal plug-and-play connectivity for Internet-of-things (IoT) devices. Picosats (Fig. 1) are small in size and are built using off-the-shelf low-complexity hardware. Therefore, they are inexpensive to build and launch into orbit. With picosat constellations, users do not need the technical expertise to deploy network backhauls, power infrastructure, and gateways before they can enable IoT connectivity. IoT devices, compatible with picosats, can simply be turned on and connected to the Internet. Excited by this vision, more than a dozen companies have deployed constellations of hundreds of picosats and providing commercial IoT connectivity services today [2, 4–6, 10, 13].

Direct-to-satellite (DtS) is the prevalent connectivity model for IoT-picosat connectivity [1, 7, 34, 61, 62]. In DtS, IoT devices first receive a beacon from a picosat overhead and then directly transmit their data to picosats in orbit (Fig. 2a). After receiving the data, the picosat opportunistically forwards the data to ground stations on Earth. Lastly, the ground stations, which are connected to terrestrial networks such as the Internet, forward the received data to the cloud for aggregation.

IoT-picosat networks differ from terrestrial IoT networks in terms of power constraints, backhaul infrastructure, and mobility. In terrestrial IoT networks such as LoRaWAN, IoT devices communicate with stationary gateways that benefit from consistent power sources and backhaul. For picosat networks, IoT devices directly talk to picosats. Such picosats are powe-constrained because their small size (Fig. 1) prevents them from using large solar panels and large batteries. Besides, due to their orbital motion in low orbits, picosats move fast with respect to the Earth and cannot connect to a ground device for more than ten minutes at a stretch [62, 69]. Thus, picosats have intermittent backhaul connectivity to ground stations and a fast-changing picosat-IoT device relationship. In essence, unlike terrestrial networks which operate with constrained IoT devices and well-resourced gateways, picosat networks must deal with constraints at both the IoT devices and picosats (functioning as gateways).

位于低地球轨道（LEO）的皮卫星（picosats）星座有望为物联网（IoT）设备实现普适性的即插即用连接。皮卫星（图1）体积小，采用现成的低复杂度硬件构建，因此其制造成本和发射成本都较低。借助皮卫星星座，用户无需具备部署网络回程、电力基础设施和网关的专业技术，即可实现物联网连接。兼容皮卫星的物联网设备只需开机即可接入互联网。受此愿景激励，已有十几家公司部署了由数百颗皮卫星组成的星座，并已在提供商业化的物联网连接服务 [2, 4–6, 10, 13]。

直连卫星（Direct-to-satellite, DtS） 是当前物联网-皮卫星连接的主流模式 [1, 7, 34, 61, 62]。在 DtS 模式中，物联网设备首先接收来自头顶皮卫星的信标，然后将其数据直接传输给在轨的皮卫星（图2a） 。皮卫星接收到数据后，会伺机将数据转发给地球上的地面站。最后，连接到互联网等地面网络的地面站，会将接收到的数据转发至云端进行聚合。

物联网-皮卫星网络在功率限制、回程基础设施和移动性方面与地面物联网网络不同。在诸如 LoRaWAN 的地面物联网网络中，物联网设备与固定的网关通信，这些网关受益于稳定的电源和回程链路。而在皮卫星网络中，物联网设备直接与皮卫星通信。这类皮卫星受到严格的功率限制，因为其尺寸过小（图1），无法使用大型太阳能电池板和大容量电池。此外，由于在低轨道上的高速运动，皮卫星相对于地球移动迅速，单次与地面设备的连接时间无法超过十分钟 [62, 69]。因此，皮卫星与地面站的回程连接是间歇性的，且皮卫星与物联网设备之间的关系也在快速变化。本质上，不同于地面网络中物联网设备受限而网关资源充足的情况，皮卫星网络必须同时应对物联网设备和充当网关的皮卫星两端的限制。

Due to these constraints and the growing scale of picosat networks, IoT-picosat networks face the following key challenges (highlighted in Fig. 2b):

Challenge 1: Uplink Collisions at the Satellite: Uplink transmissions from IoT devices to picosats encounter a high incidence of collisions. This arises because picosats have large footprints – a satellite can receive transmissions from areas spanning a few million 𝐾𝑚 2 containing thousands of devices. The large number of devices, combined with the limited spectrum, make it challenging for the satellite to explicitly coordinate medium access through time or frequencydomain multiplexing. These devices, due to their terrestrial distances and obstacles, lack the ability to overhear each other’s transmissions and utilize carrier-sense-based medium access. Moreover, IoT devices employ omnidirectional antennas, making it impossible to direct their transmissions toward a specific satellite. Consequently, they rely on random-access protocols like Aloha. Their transmissions generate interference at multiple satellites, resulting in multiple collisions stemming from a single transmission. While there has been limited past work in optimizing random access for individual satellites [20, 70], it does not consider the impact of overlaps in the footprints of multiple satellites, as shown in Fig. 2b.

Challenge 2: Acknowledgments and Flow Control: Traditional networks like Wi-Fi and RFIDs rely on feedback (e.g., acknowledgments) from the gateway to control the sending rate. However, in IoT-picosat networks, IoT traffic is infrequent, typically consisting of only a few tens of packets per day. Consequently, the feedback obtained by a device from one transmission (through its corresponding acknowledgment) becomes outdated by the time of the next transmission. Moreover, with IoT devices not enduring contact with any given satellite for more than a few minutes, the subsequent transmissions happen to a different satellite. Given these constraints, we need to find new mechanisms for adapting the data transmission rate from IoT devices.

Challenge 3: Scheduling Ground Station Contacts: Traditional satellites use phased arrays or large dishes to beamform data directly to ground stations. When multiple satellites and ground stations are in sight of each other, a centralized scheduler identifies which satellites should talk to which ground stations and establish one-to-one links. Extensive research [18, 29, 69] exists in identifying the best set of links to activate at any time. However, picosats use omnidirectional antennas and cannot perform beamforming for one-to-one communication with ground stations. Moreover, picosats increasingly rely on distributed ground station designs like TinyGS [12] having 1000+ small ground stations deployed globally [62]. Therefore, picosats establish one-to-many links with dense ground station deployment. Specifically, when one satellite is allowed to transmit, its signal interferes at multiple ground stations that can no longer receive signals from other satellites. Existing scheduling algorithms do not account for such one-to-many interference patterns.

由于这些限制以及皮卫星网络规模的日益增长，物联网-皮卫星网络面临以下关键挑战（如图2b所示）：

挑战1：卫星上行链路的碰撞问题：从物联网设备到皮卫星的上行传输会遭遇高概率的碰撞。这是因为皮卫星的覆盖范围（footprint）巨大 —— 一颗卫星可以接收来自数百万平方公里区域内数千台设备的传输。大量的设备和有限的频谱资源，使得卫星难以通过时分或频分复用等方式显式地协调介质访问。这些设备由于地面距离和障碍物的存在，无法监听到彼此的传输，因而不能使用基于载波侦听的介质访问协议。此外，物联网设备使用全向天线，无法将其传输指向特定的卫星。因此，它们依赖于如 Aloha 等随机接入协议。它们的传输会对多颗卫星产生干扰，导致单次传输引发多次碰撞。虽然过去有一些针对单个卫星优化随机接入的研究 [20, 70]，但并未考虑到多颗卫星覆盖范围重叠所带来的影响，如图2b所示。

挑战2：确认机制与流量控制：像Wi-Fi和RFID这样的传统网络依赖于来自网关的反馈（例如，确认信号）来控制发送速率。然而，在物联网-皮卫星网络中，物联网流量的传输频次很低，通常每天只有几十个数据包。因此，设备从一次传输（通过其对应的确认信号）获得的反馈，到下一次传输时已经过时了。而且，由于物联网设备与任何一颗特定卫星的持续连接时间不超过几分钟，其后续的传输通常是发往另一颗不同的卫星。鉴于这些限制，我们需要寻找新的机制来调整物联网设备的数据传输速率。

挑战3：地面站通信的调度：传统卫星使用相控阵或大型碟形天线进行波束成形，以直接与地面站通信。当多颗卫星和多个地面站互在视线范围内时，由一个中心调度器确定哪些卫星应与哪些地面站通信，并建立一对一的链路。关于如何在任何时刻激活最佳链路组合，已有广泛的研究 [18, 29, 69]。然而， 皮卫星使用全向天线，无法进行波束成形以实现与地面站的一对一通信 。此外，皮卫星越来越依赖于像 TinyGS [12] 这样的分布式地面站设计，其在全球部署了超过1000个小型地面站 [62]。因此， 皮卫星与密集的地面站部署之间建立的是一对多的链路。具体来说，当一颗卫星被允许传输时，其信号会对多个地面站造成干扰，导致这些地面站无法再接收来自其他卫星的信号 。现有的调度算法没有考虑到这种一对多的干扰模式。

In this paper, we present CosMAC a new system that addresses the above challenges to improve scalability, robustness, and performance of picosat networks. CosMAC contains a new overlap-aware medium access scheme and a novel scheduling architecture. CosMAC does not require hardware changes at the satellites or ground stations and operates at the software/firmware level. While past work has optimized individual satellite or ground station design, CosMAC takes a unique constellation-scale collaborative approach that reveals new optimization opportunities. CosMAC’s design consists of three key components:

(i) Mitigating Uplink Collisions: In IoT-picosat networks, we observe that the costs of a single transmission from different IoT devices are not equal. For example, if a device is in the overlapping footprint region of multiple satellites, its transmissions prevent these satellites from receiving transmissions from other IoT devices (collision) as illustrated by Fig. 2b. Based on this observation, we create a new overlapaware random access protocol that penalizes such heavy hitters from an overlapping region. It contrasts to medium access approaches used in terrestrial networks, where such schemes would cause starvation to the devices in overlapping regions. However, in satellite networks, the orbital motion ensures that the satellite footprints as well as the overlapping regions move across the Earth. Our approach minimizes collisions and improves the overall uplink throughput.

(ii) Dynamic Flow Control: Due to the variable data generation rate of devices (e.g., event-driven traffic), we need to regularly adapt the transmission rate of IoT devices. To achieve this objective with minimal overhead, we design a collaborative flow control scheme which leverages beacons transmitted from off-the-shelf picosats. With CosMAC, picosats provide feedback to all devices under their footprints for adjusting their transmission rates. The picosat determines when devices need to scale back their transmissions by detecting and measuring collisions over time. If the number of collisions measured is significantly larger than the amount expected from periodic traffic, the picosat can include a ‘backoff’ signal in its periodic beacon message and vice versa.

(iii) One-to-many Scheduling: CosMAC designs a new scheduling algorithm for one-to-many satellite-ground station connections. Our algorithm strives to ensure that two satellites transmitting concurrently must have at least 𝐾 nonoverlapping (i.e., interference free) ground stations available to each satellite. By achieving the above goal, CosMAC is able to optimize the satellite downlink schedule for both network reliability and network robustness. We formulate CosMAC’s schedule as a graph problem and demonstrate that our problem can be mapped to the maximum weighted independent set problem from traditional graph theory, which is known to be NP-Hard, making it challenging to solve. We use a randomized approximation algorithm to determine the final schedule for the satellites. Our formulation is specifically designed such that the scheduler prioritizes links with high channel capacity and achievable data rates, while also accounting for receiver diversity to ensure reliability.

To evaluate CosMAC, we devise a comprehensive research platform for IoT-picosat networks, encompassing both realworld picosat based IoT deployments and large-scale, reliable simulations. Our platform comprises three picosats in orbit, launched in collaboration with FOSSA Systems [5], a commercial IoT-picosat service provider. Specifically, one picosat was launched exclusively for this research endeavor, while the other two are utilized for extended evaluations. The setup further includes two ground stations and multiple IoT nodes. For large-scale experimentation, we develop new open-source trace-driven simulator, CosmicBeats, using data and models derived from our real-world setup. We have released this simulator and the models in the public domain [60]. We conduct simulations involving constellations comprising 173 satellites, 100,000 devices, and 1,048 ground stations. Our results show that CosMAC can improve net end-to-end throughput by 6.5× compared to state-of-the-art baselines.

在本文中，我们提出了 CosMAC，一个旨在解决上述挑战以提升皮卫星网络可扩展性、鲁棒性和性能的新系统。CosMAC 包含一种新的重叠感知介质访问方案和一种新颖的调度架构。CosMAC 无需对卫星或地面站进行硬件改造，完全在软件/固件层面运行。虽然过去的工作侧重于优化单个卫星或地面站的设计，但 CosMAC 采用了一种独特的星座级协同方法，揭示了新的优化机会。CosMAC 的设计包括三个关键组成部分：

(i) 缓解上行链路碰撞：在物联网-皮卫星网络中，我们观察到不同物联网设备单次传输的成本是不相等的。 例如，如果一个设备位于多颗卫星的重叠覆盖区域内，其传输会阻止这些卫星接收来自其他物联网设备的传输（即碰撞） ，如图2b所示。基于这一观察，我们创建了一种新的重叠感知随机接入协议，该协议会 对来自重叠区域的这类“重度影响者（heavy hitters）”进行惩罚 。这与地面网络中使用的介质访问方法形成对比，在地面网络中此类方案可能导致重叠区域内的设备“饿死”（starvation）。然而，在卫星网络中，轨道运动确保了卫星的覆盖范围以及重叠区域在地球表面上是移动的。我们的方法最大限度地减少了碰撞，并提高了整体上行链路的吞吐量。

(ii) 动态流量控制：由于设备的数据生成率是可变的（例如，事件驱动型流量），我们需要 定期调整物联网设备的传输速率 。为了以最小的开销实现这一目标，我们设计了一种协同流量控制方案，该方案利用了现成皮卫星发射的信标。通过 CosMAC， 皮卫星向其覆盖范围内的所有设备提供反馈，以调整它们的传输速率。 皮卫星通过检测和测量一段时间内的碰撞来判断设备何时需要缩减其传输。如果测量到的碰撞次数显著高于周期性流量所预期的数量，皮卫星可以在其周期性信标消息中包含一个“退避（backoff）”信号，反之亦然。

(iii) 一对多调度：CosMAC 为一对多的卫星-地面站连接设计了一种新的调度算法。我们的 算法致力于确保同时传输的两颗卫星必须各自至少拥有 K 个非重叠（即无干扰）的可用地面站。 通过实现这一目标，CosMAC 能够为网络可靠性和网络鲁棒性优化卫星下行链路的调度。我们将 CosMAC 的调度问题建模为一个图论问题，并证明该问题可以映射到传统图论中的最大权独立集问题，这是一个已知的 NP难（NP-Hard） 问题，求解难度很高。我们使用一个随机近似算法来确定卫星的最终调度方案。我们的模型经过专门设计，使得调度器优先考虑具有高信道容量和可实现数据速率的链路，同时也会考虑接收分集以确保可靠性。

为了评估 CosMAC，我们设计了一个全面的物联网-皮卫星网络研究平台，涵盖了真实世界的皮卫星物联网部署和大规模、高可靠性的仿真。我们的平台包括三颗与商业物联网-皮卫星服务提供商 FOSSA Systems [5] 合作发射的在轨皮卫星。具体来说，其中一颗皮卫星是专为本研究项目发射的，另外两颗则用于扩展评估。该平台还包括两个地面站和多个物联网节点。为了进行大规模实验，我们利用从真实平台获得的数据和模型，开发了一款新的开源轨迹驱动仿真器 CosmicBeats。我们已经将该仿真器及相关模型公开发布 [60]。我们进行了涉及173颗卫星、10万台设备和1048个地面站的星座仿真。结果表明，与当前最先进的基准方案相比，CosMAC 能够将净端到端吞吐量提升6.5倍。

Our contributions in CosMAC are:

• We describe a new constellation-aware random access uplink technique that improves net uplink throughput.

• We design a novel downlink scheduler for satellite-ground station links that account performance and reliability.

• We build a real-world research platform consisting of three picosats, two ground stations, and multiple IoT nodes.

• We leverage the measurements from our real-world setup to build the first data-driven open source simulator for IoT picosat networks, CosmicBeats [60], and perform a large scale evaluation of CosMAC.

我们在 CosMAC 中的贡献如下：

• 我们描述了一种新的星座感知随机接入上行链路技术，该技术提升了净上行链路吞吐量

• 我们为卫星-地面站链路设计了一种新颖的下行链路调度器，该调度器兼顾了性能与可靠性

• 我们构建了一个由三颗皮卫星、两个地面站和多个物联网节点组成的真实世界研究平台

• 我们利用从真实平台获得的测量数据，构建了首个用于物联网皮卫星网络的数据驱动开源仿真器 CosmicBeats [60]，并对 CosMAC 进行了大规模评估