Александр, добрый день!
Посидел поразбирался немного с atmel lightweight mesh и у меня возникли ряд вопросов.
Насколько я понял после принятия пакета смотрится наличие записи в таблице маршрутизации для nwkSrcAddr пришедшего пакета. Если запись не найдена, то она создается. В эту же запись заноситься и параметр качества канала LQI.
При этом если например у нас есть такая топология(цифры в разрывах стрелок обозначают показатель качества данного отрезка канала):

Когда узел 0 начинает поиск пути к узлу 6, то он посылает широковещательные пакеты, которые пройдя по путям 0-1-5, 0-2-5, 0-3-4-5 все проходят через узел 5, но в результате в таблице маршрутизации узла 5 остается лишь одна запись, в которой nextHop=4, т.к. у этого пути максимальное суммарное число LQI и обратные пакеты ответа (если они немного задержаться в узле 6), все пойдут только по этому пути к узлу 0, независимо от того пути по которому они изначально пришли к узлу 5.
Я правильно понимаю?
И еще вопрос - я так понял учитывается только полный LQI всего пути до узла, который заносит это в свою таблицу маршрутизации и выбирает nextHop исходя из максимального значения LQI. А как учитывается ситуация когда например весь канал довольно с хорошим качеством, но есть один участок между двумя какими-то из его узлов где плохие условия приема, но за счет большего количества узлов по пути набегает большее значение LQI...или я неправильно понял как именно считается LQI...

Сообщение отредактировал Pasha_a13 - Aug 7 2013, 17:34

Если речь идет о простом методе поиска маршрута (не AODV), то суммарная стоимость маршрута не считается, просто локально каждый сегмент берет в качестве узла назначения узел с максимальным LQI. Глобально этот алгоритм не оптимален, соответственно. В данном случае 5 в сторону 0 выберет узел 1 или 2.

AODV считает суммарный LQI, только это не арифметическая сумма, а произведение LQI отмасштабированных до диапазона 0-1. LQI еще нелинейно трансформируются чтобы отражать реальную вероятность доставки кадра через сегмент, тогда произведение вероятностей - это вероятность доставки через весь маршрут.
AODV будет использовать узел 4.


См. ответ про вероятности.

а в функции nwkRouteFrameReceived(frame) какой алгоритм используется?
я просто не уловил как тут переключается алгоритм поиска маршрута.

nwkRouteFrameReceived() вызывается в любом случае для каждого принятого кадра.

Если NWK_ENABLE_ROUTE_DISCOVERY включена, то функция ничего не делает - это AODV, так как при AODV маршруты находятся один раз и позже не оптимизируются.
Если NWK_ENABLE_ROUTE_DISCOVERY выключена, то это простой алгоритм, который смотрит только на LQI принятого кадра не зависимо от того как он сюда добрался.

Я понял насчет вероятности.
Упустил момент насчет того что выбирается максимальное из LQI на последнем участке, я подумал изначально что это полный LQI всего пути учитывается и исходя из него выбирается.
Но вообще идея получается в том что не конечный и не начальный уровень выбирает какой из путей для него самый оптимальный, фактически промежуточные узлы сами отсеивают менее хорошие пути и такие узлы как, например , 5, через которые проходят все маршруты, берут на себя роль выбирающего обратный маршрут узла. Так?


уже увидел #ifNdef в начале функции
void nwkRouteFrameReceived(NwkFrame_t *frame). Упустил этот момент.

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

Я правильно понял последовательность вызова процедуры поиска маршрута при разрешенном route discovery:
void nwkTxFrame(NwkFrame_t *frame) -> nwkRoutePrepareTx(frame) -> nwkRouteDiscoveryRequest(frame) -> nwkRouteDiscoverySendRequest(entry, NWK_ROUTE_DISCOVERY_BEST_LINK_QUALITY) ?
А сами функции обработки при приеме запроса маршрута nwkRouteDiscoveryRequestReceived(ind) и ответа маршрута nwkRouteDiscoveryReplyReceived(ind) ..это уже обрабатывается на уровне application?

Да, так начинается поиск маршрута.

Нет, там же в nwkRouteDiscovery.c и обрабатываются. Приложение об этом и не знает, для него это выглядит как просто задержка в отправке данных.

Если Вам не сложно, можете пожалуйста, в двух словах расписать как работает функция NWK_OpenEndpoint(NWK_SERVICE_ENDPOINT_ID, nwkRxSeriveDataInd); и как мы узнаем когда пришел пакет запроса маршрута и как мы снова попадем в nwkRxSeriveDataInd, когда она вызовется?

static bool nwkRxSeriveDataInd(NWK_DataInd_t *ind)
{
uint8_t cmd = ind->data[0];
switch (cmd)
{
#ifdef NWK_ENABLE_ROUTE_DISCOVERY
case NWK_COMMAND_ROUTE_REQUEST:
nwkRouteDiscoveryRequestReceived(ind);
return true;

case NWK_COMMAND_ROUTE_REPLY:
nwkRouteDiscoveryReplyReceived(ind);
return true;
#endif
default:
return false;
}
}
Я честно говоря не очень крут в программировании, потому не все моменты для меня понятны

Сообщение отредактировал Pasha_a13 - Aug 7 2013, 18:12

NWK_OpenEndpoint() регистрирует обработчик принятых данных для Enpoint (число 0-15, 0 зарезервирован за стеком, 1-15 для приложений).

nwkRxSeriveDataInd() - это обработчик всех принятых кадров с dstEndpoint = 0 и все команды внутри стека отправляются так.

Как видно Ack - это тоже обычная команда.

Спасибо большое! А то я голову ломал, не мог понять.

А в режиме широкополосной рассылки есть какие-то ограничения наподобии что первый пакет мы переслали, а другие пакеты с nwkSrc+nwkSeq отбрасываем?
Я смотрю что при приеме пакета void nwkRxTaskHandler(void)->nwkRxHandleReceivedFrame(frame)-> сначала идет функция
nwkRouteFrameReceived(frame) которая делает запись в таблицу маршрутизации в случае большего LQI, либо создает запись если ее нет, а дальше в
nwkRxHandleReceivedFrame(frame)-> идет функция nwkRxRejectDuplicate(header), но...эта функция работает только с nwkSeq, но ведь это значение инкрементируется только в случае когда координатор шлет другой пакет, промежуточные узлы на это значение не влияют.
Если это доступная для разглашения информация, то как работает алгоритм в nwkRxRejectDuplicate(header), в частности фрагмент кода
for (uint8_t i = 0; i < NWK_DUPLICATE_REJECTION_TABLE_SIZE; i++)
{
entry = &nwkRxDuplicateRejectionTable[i];

if (entry->ttl && header->nwkSrcAddr == entry->src)
{
uint8_t diff = (int8_t)entry->seq - header->nwkSeq;

if (diff < 8)
{
if (entry->mask & (1 << diff))
{
#ifdef NWK_ENABLE_ROUTING
if (nwkIb.addr == header->macDstAddr)
nwkRouteRemove(header->nwkDstAddr, header->nwkFcf.multicast);
#endif
return true;
}

entry->mask |= (1 << diff);
return false;
}
else
{
uint8_t shift = -(int8_t)diff;

entry->seq = header->nwkSeq;
entry->mask = (entry->mask << shift) | 1;
entry->ttl = DUPLICATE_REJECTION_TTL;
return false;
}
}

if (0 == entry->ttl)
freeEntry = entry;
}

if (NULL == freeEntry)
return true;

freeEntry->src = header->nwkSrcAddr;
freeEntry->seq = header->nwkSeq;
freeEntry->mask = 1;
freeEntry->ttl = DUPLICATE_REJECTION_TTL;

SYS_TimerStart(&nwkRxDuplicateRejectionTimer);
Я понял что сначала когда первый раз принимается пакет, то записи в таблице nwkRxDuplicateRejectionTable еще нет и мы ее делаем там(src,seq,mask,ttl), плюс запускаем таймер, который раз в 100мс декрементирует значение ttl в записи таблицы. Тоесть запись действительна фактически на протяжении 1000мс.
Когда координатор шлет следующие пакеты то пока их количество меньше 8-и(относительно номера пакета зафиксированного в записи в таблице), то мы в функции не трогаем каждый первый пакет (+1,+2...+7) и зарезаем все остальные их ретрансляции через этот узел.
А зачем мы вычисляем разницу именно между номерами пакетов посланных координатором uint8_t diff = (int8_t)entry->seq - header->nwkSeq; ? Или я неправильно понял как работает этот фрагмент кода?

Да, это тоже делается через Duplicate Rejection Table.

Но им все-равно нужно знать обрабатывали они этот кадр уже или нет. Например для определения циклов в таблицах маршрутизации.

Или импользуйте тег code или не цитируйте большие куски кода, когда нет необходимости.

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

Прошу прощения! Я как-то не обратил внимания что есть такой тег.



я имел ввиду ситуацию на подобии как на рисунке:

Пакет от узла 2 идет к узлу 4, далее к 3, а затем снова к 2.
Узел 2 отсеивает повторные пакеты приходящие к нему только по такому критерию что у этого пакета будет хуже LQI(длиннее путь)?
Я просто смотрю что rejectionTable работает только с nwkSeq, и если nwkSeq постоянный(по сети гуляет один и тот же исходный запрос, меняются только macSeq,macSrc и LQI), то первый раз маска равна 1, а дальше, т.к. diff=0, маска не меняется

Это то самое обнаружение петель в маршрутах. LQI тут никак не используется. Для обычных кадров он даже не накапливается, так что невозможно сказать насколько длинный маршрут.

"return true;" под приведенным if-ом говорит о том, что кадр нужно игнорировать. Маску при этом как раз менять не нужно, она показывает какие кадры мы уже видели.

Александр, спасибо Вам за пояснения!
Еще не до конца понял как работает маска и почему мы не фильтруем пакеты с текущим nwkSeq(который заносим в таблицу), а только последующие..
Я просто не пойму как число 8(эта разница в номерах пакетов) связано с DUPLICATE_REJECTION_TTL(1000мс), ведь когда разница больше 8-и то тогда мы переписываем маску и перезапускаем ttl, а когда меньше 8-и то не трогаем ttl, ждем пока выйдет таймаут.
Завтра постараюсь разобраться.