Введение в LoRa. Meshtastic

Введение

В эпоху постоянных блокировок и отключений интернета mesh-сети переживают второе рождение: интерес к ним заметно растёт за счёт их надёжности и отказоустойчивости.

Mesh-сеть — это топология сети, построенная на принципе соединения устройств друг с другом напрямую и их возможностью выступать в роли коммутатора для остальных. Топологию сети для простоты понимания можно понимать, как способ соединения разных устройств между собой. Устройства в сети принято называть нодами (nodes). Такие сети, хотя и сложны в настройке, обеспечивают высокий уровень отказоустойчивости, так как в случае отказа одной ноды, сообщение будет перенаправлено через остальные.

Mesh-сети могут работать поверх разных физических протоколов:

• Wi-Fi (802.11s)
• LoRa
• Bluetooth/BLE
• TCP/IP
• Ethernet
• UHF/VHF

Сети на базе LoRa являются самыми распространёнными для простого обмена сообщениями, так как имеют хорошую эффективную дальность и в то же время небольшое энергопотребление. Cамым популярным решением, собравшим за счёт своей простоты большую базу пользователей, является Meshtastic.

Long Range — маломощная технология модуляции сети передачи данных со скоростью до 27 Кб/с и дальностью до 15 км (в идеальных условиях). Передача происходит в диапазоне частот, не требующих лицензии. Покрывает физический уровень передачи данных и умеет работать с геолокацией устройств.

В этой статье предлагаю познакомиться с устройством технологии LoRa и передачей данных с помощью радиосигнала, а также разобраться, как Meshtastic применяет эту технологию для построения mesh-мессенджера.

LoRa

LoRa-mesh

На физическом уровне, mesh-сетью является набор нод, имеющий 3 одинаковых параметра:

• Коэфициент расширения спектра (SF, Spreading factor) — параметр, определяющий длительность сигнала. Чем больше этот коэфициент, тем больше дальность передачи сигнала, его помехоустойчивость и длительность трансляции.
• Центральная частота (CF, Central frequency) — средняя точка спектра, который занимает радиосигнал и вокруг которой происходит его модуляция.

  Модуляция —- правила изменения параметров волны (частоты, амплитуды и др.), согласно которым производится кодировка и декодировка информации.

• Диапазон частот (bandwidth) — диапазон частот, в котором происходит передача сигнала.

Эти параметры сгруппированы в пресеты, которые можно выставить при настройке ноды.

Chirp-ы и CSS модуляция

LoRa использует CSS модуляцию (chirp spread spectrum) основанную на chirp-ах — сигналах с циклически линейно-изменяющейся частотой во времени.

В различных источниках используется самый разнообразный перевод данного термина: от “чирпа” до “свистка”. Так как перевод данного термина совершенно бессмысленен, и не привносит никакого дополнительного контекста и/или понимания темы, предлагаю придерживаться оригинального устоявшегося термина.

Пример LoRa сигнала. Преамбула отделяется от данных последовательностью down-chirp-ов.

Chirp-ы бывают возрастающие (увеличивающие частоту) и убывающие (уменьшающие частоту). Убывающие нужны только как разделитель между преамбулой и данными, во всех остальных случаях используются возрастающие.
Если сигнал достигает верхней грани диапазона, то происходит wrap и сигнал продолжается с нижней границы. Этот wrap является точкой разрыва, за счёт которого достигается модуляция. Место (а точнее время) расположения этого разрыва в пределах одного chirp-а кодирует символ.
Так как параметр SF определяет длительность сигнала в этом диапазоне, то он так же определяет количество возможных точек разрыва в каждом chirp. Следовательно, чем длительнее chirp, тем большим количеством бит кодируется каждый символ.

Устойчивость к помехам

Особенностью LoRa (а точнее CSS-модуляции) является способность работать при отрицательном SNR (Signal-to-Noise Ratio) — отношение мощности сигнала к мощности шума. При SF12 сигнал может быть декодирован при мощности сигнала на 20 дБ ниже уровня шума.
Это достигается за счёт применения механизма корреляции. Приёмник знает форму эталонного chirp-а (напомню, что эталонный chirp —- это циклический линейный сигнал, который задаётся тройкой параметров, рассмотренных выше).

$$\sum (chirp + noise) = \underbrace{\sum (chirp \times ref)}_{\propto \ T} + \underbrace{\sum (noise \times ref)}_{\to \ 0 \ \text{при} \ T \to \ \infin}$$

Так как шум случаен и не коррелирует с эталоном (ref), то при суммировании за длинный период положительные и отрицательные значения взаимно компенсируются. Сигнал с эталоном коррелирует сильно, поэтому результирующее значение будет расти пропорционально времени передачи сигнала.
Чем дольше транслируется один символ, тем больше энергии несёт в себе его сигнал (т.к. мощность передатчика фиксирована) и тем больше времени для того, чтобы компенсировать шум и получить результат.
В LoRa приёмник намеренно ждёт весь chirp для того, чтобы декодировать символ и отличить его от шума. Это отличает LoRa от, например, FM (frequency modulation, частотная модуляция), где информация кодируется в мгновенном значении частоты.
Однако, чем больше устойчивость к шуму, тем дольше транслируется один символ. SF12 при ширине диапазона в 125 кГц требует 32 мс для передачи одного символа. Зависимость затрачиваемой энергии и максимального битрейта от расстояния трансляции LoRa сигнала.

Meshtastic

Принцип работы

Плата подключается к ПК или мобильному устройству с установленным клиентским приложением с помощью Bluetooth или COM-порта. При отправке пакета (сообщения) Meshtastic использует LoRa трансмиттер на плате.
Heltec v3. Одна из самых популярных плат на базе микроконтроллера серии ESP32

Когда пакет достигает ноды, она проверяет, был ли этот пакет получен ранее. Если да, то он игнорируется, в противном случае — ретранслируется дальше.
Нода имеет небольшую встроенную память, в которой хранится ~30 пакетов, полученных в то время, пока плата не подключена к клиентскому приложению. В случае переполнения этой памяти, старые пакеты затираются новыми.
Поверх радиосигнала существуют логические каналы —- группа нод, объединённые общим названием канала и симметричным ключом шифрования (PSK). Ключ хранится в памяти ноды. Количество каналов, которое нода может хранить ограничено 8. Это архитектурное решение, которое минимизирует требуемые технические характеристики устройства, пригодного для Meshtastic.

Пакет данных meshtastic

Пакет данных meshtastic передаётся в разделе данных LoRa payload. Сам пакет содержит в себе незашифрованные метаданные маршрута и зашифрованные данные приложения. Последние также закодированы в формате protobuf.
Содержимое пакета meshtastic следующее:

1. To — 4 байта Содержит номер ноды назначения. В случае, если пакет предназначен для всех нод, то содержит 0xFFFFFFFF
2. From — 4 байта
3. Packet ID — 4 байта Уникальный идентификатор пакета, по которому нода определяет дубликаты
4. Packet Flags — 1 байт
   1. Hop limit — 3 бита Число оставшихся ретрансляций данного пакета. При ретрансляции нода уменьшает это значение на единицу.
   2. Want Ack — 1 бит Определяет, требует ли отправитель подтвердить получение пакета нодой назначения
   3. Via MQTT — 1 бит Показывает, был ли пакет запущен в mesh-сеть через MQTT.
      MQTT (Message Queuing Telemetry Transport) — легкий протокол обмена сообщениями по модели publish/subscribe. В Meshtastic используется как опциональный мост между Mesh-сетью и интернетом. Нода с доступом к Wi-Fi может пересылать пакеты из mesh в MQTT-брокер и наоборот, что позволяет объединять географически разрозненные mesh-сети через интернет.
   4. Hop start — 3 бита Содержит изначальное максимальное число ретрансляций пакета. Нужен для определения количества ретрансляций между нодой отправки и назначения
5. Channel hash — 1 байт Показывает, к какому каналу принадлежит пакет. Данный хеш вычисляется из названия канала и его ключа шифрования. Получая пакет, нода перебирает имеющиеся в памяти ключи шифрования для расшифровки пакета.
6. Next hop — 1 байт При использовании механизма next-hop routing содержит адрес ноды для пересылки. Размер меньше чем поля From или To, потому что содержит в себе адрес соседней ноды, а не полный адрес в mesh-сети.

   Next-hop routing — более эффективный, чем классический flood routing, механизм пересылки сообщений, появившийся в Meshtastic v2.6. Принцип его работы будет рассмотрен позже.

7. Relay node — 1 байт Идентификатор ноды, являющейся текущим ретранслятором.
8. Payload — 239 байт, зашифровано
   1. Portnum — 1 байт Идентификатор порта приложения, который определяет, как интерпретировать переданные данные
   2. Want Response — 1 бит Ожидается ли ответ от получателя. Нешифрованный флаг Want Ack определяет необходимость от самой mesh-сети, т.е. подтверждение доставки пакета. Данное поле определяет необходимость ответа непосредственно от ноды, например, данные о её геопозиции.
   3. Reply ID — 4 байта Идентификатор сообщения, ответом к которому является текущее сообщение
   4. Emoji flag — 1 бит Определяет, требуется ли интерпретировать текст внутри, как эмодзи
   5. Application payload — <200 байт Содержит ключевую передаваемую информацию: текст сообщения, данные геолокации, телеметрия, обновлённые данные о ноде.
   6. Bitfield — 1 байт Битовая маска с булевыми атрибутами пакета, определяемые ПО Meshtastic. Содержит, например, информацию можно ли передавать пакет через MQTT.

Кроме всех описанных выше полей пакета, он также содержит информацию о приоритете передачи пакета, временной метке, мощности принимаемого сигнала и SNR. С помощью этих данных выстраивается оптимальный маршрут пакета от отправителя до получателя.

Алгоритм mesh-сети meshtastic

В документации meshtastic, сеть делится на 4 слоя:

1. LoRa radio
   Это физический слой на котором данные кодируются в радиосигнал. Преамбула показывает начало сигнала и позволяет приёмнику понять, что в данный момент начинает транслироваться пакет. После преамбулы идёт слово синхронизации, которое позволяет отделить различные сети, транслируемые на одной частоте. Для сети Meshtastic это 0x2B. Заголовок LoRa пакета содержит информацию о длине пакета. После идёт информация о самом Meshtastic пакете, а в конце содержится CRC блок, который позволяет исправить ошибки передачи.
   В данном слое система не имеет представления о пакетах, она оперирует непосредственно физическими сигналами — chirp-ами.
   LoRa сигнал, состоящий из отдельных chirp-ов, внутри которого содержится Meshtastic пакет.

2. Ненадёжная прямая передача сообщений (Unreliable Zero Hop Messaging)
   Данный слой вводит описание пакета и способа его передачи. Пакет пересылается всем соседям транслирующей ноды в зоне прямой радиовидимости. Перед отправкой пакета, нода обязана проводить CAD (Channel Activity Detection) — проверку занятости канала передачи сообщения другой нодой. В случае, если канал в данный момент занят, нода ждёт случайное время, определяемое окном конкуренции (Contention window, CW). Это время тем больше, чем более загружен в данный момент канал. За счёт этого происходит минимизация коллизий.
   На данном слое система знает, что из себя представляет пакет и умеет его корректно транслировать, однако никаких гарантий того, что пакет будет доставлен, нет.

3. Надёжная прямая передача сообщений (Reliable Zero Hop Messaging)
   Данный слой надстраивает над предыдущим механизм гарантированной доставки через флаг WantAck в заголовке пакета. Поведение различается в зависимости от типа пакета. Для DM нода-получатель отправляет ACK обратно отправителю — явное подтверждение что пакет дошёл.
   Для Broadcast классический ACK неприменим: если каждая нода в сети отвечала бы подтверждением, это моментально перегрузило бы эфир.

   Сообщения в Meshtastic делятся на 2 вида:
       1. Broadcast — сообщения, транслируемые всем нодам в сети
       2. DM (Direct messages) — сообщения, имеющие конкретную ноду-получатель.

   Вместо этого, нода-транслятор прослушивает канал и в случае, если хотя бы одна другая нода начала ретрансляцию пакета, то отправитель самостоятельно генерирует implicit ACK.

   Если в течение определенного таймаута отправитель не получил ни ACK, ни NAK, то с помощью предыдущего слоя будет выполнена повторная попытка трансляции пакета вплоть до 3 раз. Если повторные попытки также оказались неудачными, то отправитель генерирует NAK и прекращает трансляцию.

4. Многоузловая передача сообщений (Multi-hop messaging)

   Как было сказано ранее, в случае Broadcast сообщений, нода ретранслирует их вплоть до истечения Hop Limit. В случае, если какое-то сообщение уже ретранслируется другой нодой, то текущая проигнорирует это сообщение и не станет его ретранслировать, чтобы не перегружать эфир. Такой подход называется управляемым флудингом (Managed flooding).
   Для DM используется упомянутый ранее алгоритм Next-hop routing. Принцип его работы проиллюстрирован ниже.
   

   Принцип работы алгоритма next-hop routing.

   Первый пакет от ноды A до ноды D отправляется с помощью managed flooding. Если пакет успешно доставлен и вернулся ACK, при этом вернулся он через ту же ноду, которая участвовала в изначальной передаче пакета, то она запоминается для этого маршрута.
   Таким образом, при отправке последующих пакетов по тому же адресу они будут транслироваться не всем нодам в радиусе покрытия радиосигнала, а конкретной ноде, чтобы уменьшить зашумление эфира. При этом такой маршрут определяется при каждой трансляции пакета. В случае, если не получилось доставить пакет с помощью next-hop routing, то выполняются стандартные 3 повторные попытки. По их истечению пакет транслируется через managed flooding.

Зависимость CW от SNR и косвенное вычисление расстояния

При ограниченном Hop limit выгоднее ретранслировать пакет через самые дальние ноды — так он распространится дальше за то же число прыжков. Проблема в том, что ноды не знают ни своего положения в пространстве, ни расстояния до соседей.

Да, Meshtastic может работать с данными геопозиции, но во-первых, это дополнительные данные, которые нужно хранить, а во-вторых, не все ноды по умолчанию идут с предустановленным GPS-модулем.

Косвенным индикатором расстояния служит SNR. Напомню, что SNR — это параметр, показывающий отношение мощности сигнала к мощности постороннего шума. Мощность шума примерно постоянна, а мощность сигнала падает с расстоянием из-за затухания в свободном пространстве — значит SNR тем ниже, чем дальше нода от источника.
Чтобы использовать это без явного обмена значениями SNR между нодами размер окна конкуренции (CW) привязана к параметру SNR напрямую. Чем меньше SNR, тем меньше CW, тем раньше нода начнёт ретрансляцию. Таким образом, дальняя нода статистически раньше начнёт ретрансляцию, чем ближняя.

Источники

1. https://en.wikipedia.org/wiki/Mesh\_networking
2. https://en.wikipedia.org/wiki/LoRa
3. https://www.mokosmart.com/de/lora-frequency/
4. https://www.nolilab.com/ru/blog/lora-lorawan-a-simple-guide/
5. https://meshtastic.org/docs/overview/