Jump to content

    

Mesh сеть между подвижными объектами.

Александр, добрый день!

Посидел поразбирался немного с atmel lightweight mesh и у меня возникли ряд вопросов.

Насколько я понял после принятия пакета смотрится наличие записи в таблице маршрутизации для nwkSrcAddr пришедшего пакета. Если запись не найдена, то она создается. В эту же запись заноситься и параметр качества канала LQI.

При этом если например у нас есть такая топология(цифры в разрывах стрелок обозначают показатель качества данного отрезка канала):

0649b06df282.jpg

Когда узел 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...

Edited by Pasha_a13

Share this post


Link to post
Share on other sites
Я правильно понимаю?

 

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

 

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

AODV будет использовать узел 4.

 

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

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

Share this post


Link to post
Share on other sites

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

я просто не уловил как тут переключается алгоритм поиска маршрута.

Share this post


Link to post
Share on other sites
а в функции nwkRouteFrameReceived(frame) какой алгоритм используется?

я просто не уловил как тут переключается алгоритм поиска маршрута.

 

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

 

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

Если NWK_ENABLE_ROUTE_DISCOVERY выключена, то это простой алгоритм, который смотрит только на LQI принятого кадра не зависимо от того как он сюда добрался.

Share this post


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

 

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

AODV будет использовать узел 4.

 

 

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

Я понял насчет вероятности.

Упустил момент насчет того что выбирается максимальное из LQI на последнем участке, я подумал изначально что это полный LQI всего пути учитывается и исходя из него выбирается.

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

 

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

 

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

Если NWK_ENABLE_ROUTE_DISCOVERY выключена, то это простой алгоритм, который смотрит только на LQI принятого кадра не зависимо от того как он сюда добрался.

уже увидел #ifNdef в начале функции

void nwkRouteFrameReceived(NwkFrame_t *frame). Упустил этот момент.

Share this post


Link to post
Share on other sites
Но вообще идея получается в том что не конечный и не начальный уровень выбирает какой из путей для него самый оптимальный, фактически промежуточные узлы сами отсеивают менее хорошие пути и такие узлы как, например , 5, через которые проходят все маршруты, берут на себя роль выбирающего обратный маршрут узла. Так?

 

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

Share this post


Link to post
Share on other sites

Я правильно понял последовательность вызова процедуры поиска маршрута при разрешенном route discovery:

void nwkTxFrame(NwkFrame_t *frame) -> nwkRoutePrepareTx(frame) -> nwkRouteDiscoveryRequest(frame) -> nwkRouteDiscoverySendRequest(entry, NWK_ROUTE_DISCOVERY_BEST_LINK_QUALITY) ?

А сами функции обработки при приеме запроса маршрута nwkRouteDiscoveryRequestReceived(ind) и ответа маршрута nwkRouteDiscoveryReplyReceived(ind) ..это уже обрабатывается на уровне application?

Share this post


Link to post
Share on other sites
Я правильно понял последовательность вызова процедуры поиска маршрута при разрешенном 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 и обрабатываются. Приложение об этом и не знает, для него это выглядит как просто задержка в отправке данных.

 

Share this post


Link to post
Share on other sites

Если Вам не сложно, можете пожалуйста, в двух словах расписать как работает функция 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;

}

}

Я честно говоря не очень крут в программировании, потому не все моменты для меня понятны :(

Edited by Pasha_a13

Share this post


Link to post
Share on other sites

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

 

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

 

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

Share this post


Link to post
Share on other sites
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;

 

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; ? Или я неправильно понял как работает этот фрагмент кода?

Share this post


Link to post
Share on other sites
А в режиме широкополосной рассылки есть какие-то ограничения наподобии что первый пакет мы переслали, а другие пакеты с nwkSrc+nwkSeq отбрасываем?
Да, это тоже делается через Duplicate Rejection Table.

 

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

 

Если это доступная для разглашения информация, то как работает алгоритм в nwkRxRejectDuplicate(header), в частности фрагмент кода
Или импользуйте тег code или не цитируйте большие куски кода, когда нет необходимости.

 

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

 

Share this post


Link to post
Share on other sites
Или импользуйте тег code или не цитируйте большие куски кода, когда нет необходимости.

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

 

 

А в режиме широкополосной рассылки есть какие-то ограничения наподобии что первый пакет мы переслали, а другие пакеты с nwkSrc+nwkSeq отбрасываем?

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

96b20e48bad5.jpg

Пакет от узла 2 идет к узлу 4, далее к 3, а затем снова к 2.

Узел 2 отсеивает повторные пакеты приходящие к нему только по такому критерию что у этого пакета будет хуже LQI(длиннее путь)?

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

if (entry->mask & (1 << diff))//значение это будет постоянно false
        {        
        }
        entry->mask |= (1 << diff);//и маска тоже не меняется
        return false;

Share this post


Link to post
Share on other sites

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

 

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

Share this post


Link to post
Share on other sites

Александр, спасибо Вам за пояснения!

Еще не до конца понял как работает маска и почему мы не фильтруем пакеты с текущим nwkSeq(который заносим в таблицу), а только последующие..

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

Завтра постараюсь разобраться.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this