mesh-alg

Текущий алгоритм

Протокол маршрутизации для Meshtastic разработан для поддержки различных сценариев использования. Что наиболее важно, он не предполагает наличие только статических узлов. Если вы хотите протестировать его теоретическую производительность, ознакомьтесь с симулятором. Протокол в значительной степени основан на алгоритме маршрутизации в mesh-сети из RadioHead (который использовался в очень ранних версиях этого проекта). У него четыре концептуальных слоя и (начиная с версии 2.6) используется другой подход для широковещательных сообщений и прямых сообщений.

Заметка о Protocol Buffers

Поскольку мы хотим, чтобы наши устройства работали с различными производителями и реализациями, мы повсеместно используем Protocol Buffers. Для целей этого документа вам в основном нужно учитывать только типы сообщений MeshPacket и Sub-packet.

Слой 0: LoRa Радио

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

Эта преамбула позволяет принимающим радиоустройствам синхронизировать часы и начать кадрирование. Мы используем длину преамбулы 16, что длиннее минимальной длины преамбулы 8, чтобы позволить приемникам LoRa SX126x спать некоторое время, что снижает энергопотребление.

После преамбулы следует физический заголовок LoRa, который содержит информацию о длине пакета, а также слово синхронизации для различения сетей. Для Meshtastic оно установлено в 0x2B.

Слой 1: Ненадежная передача сообщений с нулевым количеством прыжков

Этот слой представляет собой обычную ненадежную передачу пакетов LoRa. Пакет, сгенерированный устройством Meshtastic, имеет следующее представление перед кодированием для передачи:

Флаги заголовка пакета

Подробности использования

• Packet Header: описан непосредственно классом PacketHeader в исходном коде на C++. Но косвенно он соответствует первой части определения protobuf MeshPacket. Обратите внимание, что заголовок пакета не кодируется с использованием protobuf, а отправляется как сырые байты. Это экономит эфирное время и позволяет аппаратному обеспечению приемного радио опционально фильтровать пакеты до пробуждения основного процессора.

• Packet Header - NodeIDs: формируются из младших четырех байтов MAC-адреса Bluetooth-адреса. Поскольку OUI назначается IEEE, и мы в настоящее время поддерживаем только несколько производителей процессоров, старший байт фактически гарантированно уникален для каждого производителя. Младшие 3 байта гарантированно уникальны у этого производителя.

• Packet Header - Unique ID: ID — это большой 32-битный идентификатор, чтобы обеспечить достаточно уникального состояния для защиты зашифрованной нагрузки от атак.

• Payload: Зашифрованное и упакованное кодирование protobuf для protobuf SubPacket. Только SubPacket шифруется, в то время как заголовки — нет. Это позволяет в будущем дать узлам возможность маршрутизировать пакеты, не зная ничего о зашифрованной нагрузке. Подробнее см. шифрование и Справочник API Protobuf. Любые данные сверх максимальной длины обрезаются.

Carrier-Sense Multiple Access with Collision Avoidance (CSMA/CA)

Meshtastic использует CSMA/CA, аналогично WiFi. Это означает, что все передатчики должны выполнять обнаружение активности канала (CAD) перед попыткой передачи. Если канал считается занятым, узел будет ждать, пока он не освободится. Поскольку после освобождения канала несколько узлов могут захотеть начать передачу, узел должен ждать случайное кратное слотовое время. Слотовое время — это время, необходимое для надежного выполнения CAD. Количество слотовых времен для ожидания выбирается случайно из окна конкуренции (CW), размер которого зависит от текущей загрузки канала. Окно конкуренции больше при высокой загрузке канала, чтобы ограничить вероятность коллизий.

Слой 2: Надежная передача сообщений с нулевым количеством прыжков

Этот слой добавляет надежную передачу сообщений только между узлом и его непосредственными соседями.

Стандартная передача сообщений, предоставляемая слоем 1, расширяется установкой флага WantAck в protobuf MeshPacket. Если установлен WantAck, применяется следующая документация из mesh.proto:

This packet is being sent as a reliable message, we would prefer it to arrive at the destination. We would like to receive an ACK packet in response.

Broadcast messages treat this flag specially: Since ACKs for broadcasts would rapidly flood the channel, the normal ACK behavior is suppressed. Instead, the original sender listens to see if at least one node is rebroadcasting this packet (because naive flooding algorithm). If it hears that, the odds (given typical LoRa topology) are very high that every node should eventually receive the message. So FloodingRouter.cpp generates an implicit ACK which is delivered to the original sender. If after some time we don't hear anyone rebroadcast our packet, we will timeout and re-transmit, using the regular resend logic.

Если передающий узел не получает пакет ACK (или NAK) после определенного времени истечения, он использует слой 1 для попытки повторной передачи отправленного пакета. Надежный пакет (на этом уровне «нулевого прыжка») будет повторно отправлен максимум три раза. Если к этому моменту ACK или NAK не получены, локальный узел внутренне сгенерирует NAK (либо для локального использования, либо для использования высшими слоями протокола). Время истечения для повторной передачи основано на максимальном времени, необходимом для получения (неявного) ACK, с учетом эфирного времени отправленного пакета и любой задержки обработки. Для прямых сообщений предполагаемый получатель также отправит реальный ACK обратно оригинальному отправителю, но устройство будет повторно передавать только если не получило ACK вообще.

Слой 3: Передача сообщений с несколькими прыжками

Широковещательная передача с использованием управляемого затопления

Учитывая различные сценарии использования, которые поддерживает Meshtastic, большая часть нашего протокола построена вокруг затопления, то есть каждый узел переотправляет полученный пакет до определенного лимита прыжков. Однако важное отличие в Meshtastic заключается в том, что перед переотправкой узел некоторое время слушает, не переотправил ли другой узел этот пакет уже. Если да, он не переотправляет. Поэтому «управляемое затопление» — более точный термин.

Принцип следующий. Если любой узел mesh видит пакет с HopLimit, отличным от нуля, он уменьшает этот HopLimit и пытается переотправить от имени оригинального отправляющего узла. Чтобы способствовать тому, чтобы узлы, находящиеся дальше, затопляли сообщение, чтобы оно в итоге достигло большего расстояния, окно конкуренции (см. слой 1) для сообщения затопления зависит от отношения сигнал/шум (SNR) полученного пакета. Размер CW мал для низкого SNR, чтобы узлы, находящиеся дальше, с большей вероятностью затопили первыми, а ближайшие узлы, услышавшие это, воздержались от затопления. Исключение составляют роли ROUTER и REPEATER, которые имеют более высокий приоритет для переотправки и сделают это даже если услышат переотправку от другого узла.

Пример

Ниже приведена примерная топология из четырех узлов в режиме CLIENT, где в определенный момент узел 0 хочет отправить широковещательное сообщение. Из-за ограниченного покрытия оно достигает только узлов 1 и 2. Поскольку узел 2 дальше, его SNR ниже, поэтому он начинает переотправку раньше, чем узел 1. После того как узел 0 получил эту переотправку, его сообщение признано доставленным. Обратите внимание, что сообщение уже признано доставленным, как только получена переотправка от любого узла Meshtastic (независимо от того, имеет ли он тот же ключ шифрования). Поскольку узел 1 услышал ретрансляцию от 2, он не будет ретранслировать снова. Узел 3 услышал сообщение впервые, и HopLimit ещё не равен нулю, поэтому он начинает ретрансляцию для потенциальных других получателей.

Прямые сообщения с использованием маршрутизации по следующему хопу

Начиная с версии 2.6, Meshtastic использует другой подход для прямых сообщений. Изначально используется подход управляемого затопления, упомянутый ранее, для достижения получателя.
Затем мы отслеживаем узел(ы), которые пытаются ретранслировать пакет для нас. Если после успешной доставки приходит ответ (например, ответ NodeInfo, подтверждение или трассировка маршрута) и узел, который ретранслирует это в вашу сторону, также был (одним из) узлов, ретранслировавших исходный пакет, он будет обозначен как next-hop отныне. Это означает, что вместо того чтобы позволять всем узлам пытаться ретранслировать пакет, ретранслировать будет только узел, для которого байт next-hop совпадает. Обратите внимание, что это определяется на каждый хоп, поэтому если есть асимметричная связь или узел на старой прошивке посередине, на этом хопе будет использоваться управляемое затопление. Когда узел перемещается или изменяются условия RF, next-hop может стать недействительным. Поэтому узел всегда вернётся к управляемому затоплению на последней попытке повторной передачи, если не услышит ретрансляцию от своего next-hop.
Процедура визуализирована на следующей диаграмме:

Регулярные интервалы вещания

Без дополнительных настроенных модулей узлы будут генерировать три различных типа регулярно интервалированного трафика в рамках mesh:

1. Телеметрия устройства
2. Управляется telemetry.device_update_interval
3. По умолчанию: 30 минут
4. Позиция
5. Управляется position.position_broadcast_secs
6. По умолчанию: 15 минут* (с включённым smart broadcast)
7. NodeInfo пользователя
8. Управляется device.node_info_broadcast_secs
9. По умолчанию: 3 часа

По мере роста сетей mesh и увеличения конкуренции трафика прошивка будет увеличивать эти интервалы. Это в дополнение к ограничению duty cycle, канала и использования времени в эфире.

Начиная с версии 2.4.0, прошивка будет сокращать телеметрию, позицию и другой дополнительный трафик портов для сетей mesh большего чем 40 узлов (узлы, виденные в последние 2 часа) с использованием следующего алгоритма:

ScaledInterval = Interval * (1.0 + ((NumberOfOnlineNodes - 40) * 0.075))

Например, активная сеть mesh из 62 узлов сократит telemetry.device_update_interval до 79.5 минут вместо 30-минутного значения по умолчанию.