Способ для администрирования адаптивным и совместным образом политики маршрутизации и политики повторной передачи у узла в подводной сети и средство для его реализации

Изобретение относится к способу для выбора, в подводной сенсорной сети связи, на каждой передаче/повторной передаче пакета, набора узлов, к которым упомянутый пакет должен быть отправлен и который предусматривает, для каждого узла, модуль, который регулирует политику передачи/повторной передачи уровня LLC, и модуль маршрутизации. Технический результат заключается в возможности оптимизировать производительность сети. Способ содержит этапы, на которых: используют самообучающийся алгоритм, который определяет, для каждого пакета, автономно и без явного обмена сообщениями квитирования, учитывая число раз, которое данный пакет уже был передан, оптимальный набор узлов, к которым данный пакет должен быть повторно отправлен; и определяют максимальное число повторных передач, которое должно быть выполнено, выбирая наилучший рабочий режим, в соответствии с конкретными характеристиками сети связи. 12 з.п. ф-лы, 8 ил., 1 табл.

 

Область техники, к которой относится изобретение

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

Использование UWSN (Подводные Беспроводные Сенсорные Сети) предоставляет широкий диапазон приложений, таких как, среди прочего, мониторинг окружающей среды, мониторинг критических инфраструктур и морских платформ, наблюдение за портами и побережьями, и т.д.

Подводная сенсорная сеть (Фигура 1) состоит из набора узлов, соответственно позиционированных, чтобы покрывать зону интереса, и расположенных на различных глубинах, некоторые из которых могут быть мобильными автономными транспортными средствами. Каждый узел оборудован датчиками и одним или более устройствами связи. Узлы собирают из окружающей среды данные, которые, после этапа локальной обработки, отправляются одному или более средству сбора данных или узлам-получателям, которые сохраняют/обрабатывают/транспортируют данные в другие места на основании типа приложения. Обмен данными также может рассматривать отправку команд или информации о состоянии устройств.

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

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

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

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

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

Изобретательский замысел, лежащий в основе настоящего изобретения, состоит в объединении политики выбора узлов-ретрансляторов (функция маршрутизации) с политикой повторной передачи для того, чтобы оптимизировать производительность с точки зрения надежности передач, сетевой задержки, и потребления энергии. Выбор осуществляется динамическим и адаптивным образом, посредством применения алгоритма, исполняемого каждым узлом (и, следовательно, распределенного), который позволяет узлам узнавать и выбирать динамически наилучшее число и набор соседей, которым передавать каждый пакет, и максимальное число раз, в соответствии с которым повторно передавать каждый пакет.

Оптимизация выполняется локально каждым узлом на основании получаемой в результате обмена локальной информации, и обеспечивает задание рабочего режима узла. Разные узлы могут вести себя по-разному (т.е., часть сети может следовать протоколу с одним путем, тогда как другая зона сети использует протокол со множеством путей, или даже протокол лавинной адресации).

Даже несмотря на то, что в литературе [BaPe14] [HuFe10] [PlWa14] решения адаптивной маршрутизации уже были предложены, эти решения представляют ограничения с точки зрения производительности и предусматривают много более ограниченное использование адаптивности в сравнении с предлагаемым решением. Точно такие же соображения могут применяться в отношении двух патентных заявок [US2026] и [US1082]. Первый патент не предлагает стратегии маршрутизации, а лишь метод повторной передачи пакетов. Предложение в соответствии с настоящим изобретением, тем не менее, на основании этого отличается, так как настоящая стратегия повторной передачи не предусматривает явного обмена обратной связью между сетевыми узлами. Патент [US2004/071082], с другой стороны, рассматривает протокол маршрутизации, который является исключительно типа с одним путем и не предлагает какой-либо динамичности с изменением числа повторных передач пакета.

В результате, настоящее изобретение обеспечивает задание процедуры, которая вводит локальную логику межуровневого «мета-протокола», позволяющего сети работать своевременно в соответствии с разными протоколами, и разным частям сети работать в соответствии с разными логиками протокола, что является существенной отличительной особенностью для оптимизации производительности, и все вместе отсутствует в решениях предшествующего уровня техники.

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Сущность

В области подводных сенсорных сетей, настоящее изобретение состоит в объединении политики выбора узлов-ретрансляторов (т.е., узлов которым передавать пакет для того, чтобы осуществлять его маршрутизацию к узлу-получателю) с политикой повторной передачи для того, чтобы получать наилучшую производительность с точки зрения надежности передач, сетевой задержки, и потребления энергии (и/или их сочетания).

В частности:

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

- способ является полностью децентрализованным: каждый узел определяет автономно набор узлов для переадресации в соответствии с числом уже выполненных передач;

- способ является идентичным для всех узлов;

- способ является динамическим: по мере того, как меняются сетевые условия, используя самообучающийся алгоритм (который в свою очередь является децентрализованным) каждый узел может модифицировать свою собственную политику с точки зрения числа и идентичности узлов, выбранных в качестве адресатов и/или числа повторных передач, которые должны предприниматься для заданного пакета.

Даже несмотря на то, что способ является распределенным и идентичным для каждого узла, он основан на изучении сетевых условий на основе обмена локальной информацией между соседними узлами (где под «соседними узлами» подразумеваются узлы, которые обладают возможностью корректного приема передач, выполненных друг другом), что заставляет сеть оптимизировать свою общую производительность, используя возможность допущения того, чтобы узлы системы работали по-разному (разное число ретрансляторов выбирается для каждой передачи, разное число повторных передач используется узлами).

Другие отличительные особенности изобретения будут четко вытекать из следующего описания со ссылкой на приложенные листы чертежей, на которых:

Фигура 1 является схематической иллюстрацией стандартной подводной сети;

Фигура 2 является схемой стека протоколов OSI;

Фигура 3 показывает поток исполнения подуровня LLC;

Фигура 4 показывает подробно модуль для обучения и выбора узлов следующего перехода;

Фигура 5 показывает PDR (т.е., отношение пакет-доставка, которое является отношением между числом пакетов, принятых корректно узлом-получателем, и числом пакетов, сгенерированных узлами) как функцию сетевого трафика, в сравнении протокола CARMA в соответствии с изобретением с известными протоколами QELAR и EFlood;

Фигура 6 показывает разные графики энергии, потребляемой сетью для корректной доставки бита данных узлу-получателю, как функции сетевой нагрузки, в трех ссылочных протоколах Фигуры 5;

Фигура 7 сравнивает среднюю задержку, заданную как время между генерированием пакетов и временем их корректной доставки узлу-получателю, в трех разных протоколах Фигур 5 и 6; и

Фигура 8 показывает энергию, потраченную сетевыми узлами для успешной доставки бита информации в случае низкого и высокого трафика.

Подробное описание изобретения

Со ссылкой на фигуры, рассмотрим подводную сенсорную сеть, как ту, что на Фигуре 1, состоящую из множества узлов, соответственно позиционированных, чтобы покрывать зону, представляющую интерес. Безотносительно того, является ли узел фиксированным или представленным мобильным транспортным средством, каждый узел оборудован датчиками и одним или более устройствами связи. Узлы собирают из окружающей среды данные, которые, после локальной обработки, отправляются одному или более узлам-получателям, которые сохраняют/обрабатывают/транспортируют данные в другие места на основании типа приложения.

Настоящее изобретение является межуровневым решением, которое интегрирует сетевой уровень (маршрутизация) с подуровнем LLC (Управление Логической Связью) канального уровня.

Предлагаемый способ состоит в определении автономно, узел за узлом, для каждого пакета, который должен быть передан/повторно передан (логика LLC), какому подмножеству узлов он должен быть передан (логика маршрутизации) и максимального числа повторных передач, которые должны быть выполнены.

С этой целью, для каждого узла, предоставляется модуль, который регулирует политику передачи и повторной передачи уровня LLC (верхний подуровень канального уровня модели ISO-OSI), как впрочем и модуль маршрутизации, который, используя алгоритм самообучения, основанный на Q-обучении, определяет, для каждого пакета, также в соответствии с числом раз, которое данный пакет уже был передан, оптимальный набор узлов, к которым данный пакет должен быть повторно отправлен, как будет описано подробно в дальнейшем.

Подуровень LLC (Управление Логической Связью)

Подуровень LLC регулирует логику повторной передачи у узла, который иллюстрируется на Фигуре 2. Когда узел должен отправить пакет (или повторно отправить пакет, в случае повторной передачи), он взаимодействует с модулем маршрутизации (стрелки A и B), чтобы идентифицировать узлы, к которым пакет должен быть отправлен. С этой целью, подуровень LLC отправляет модулю маршрутизации число раз, которое пакет уже был (неуспешно) передан, и принимает от последнего набор узлов, к которым пакет должен быть отправлен (набор, который в целом будет также функцией числа повторных передач того пакета).

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

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

Каждый пакет передается каждым узлом не больше числа K раз, после чего пакет отбрасывается. Параметр K устанавливается динамически в соответствии с оценкой интенсивности сетевого трафика, как описывается далее.

Модуль маршрутизации

Модуль маршрутизации регулирует логику маршрутизации, определяя, для каждого пакета, также в соответствии с числом раз, которое он уже был передан, оптимальный набор узлов, к которым он должен быть (повторно) передан.

Предлагаемое решение основано на общем математическом методе обучения с подкреплением, известном как Q-обучение [SuBa98]. Способ Q-обучения основан на Q функциях (Q-значения), которые представляют собой оценку затрат, ассоциированных с каждым возможным действием для каждого возможного состояния системы. Итеративно, алгоритм обновляет разнообразные оценки и, на основании этого, указывает в качестве действия, которое должно быть исполнено, действие минимальных затрат.

Конкретный алгоритм, используемый модулем маршрутизации, описывается далее и представлен на Фигуре 4. В каждом узле, состояние s пакета представляется числом раз, которое он уже был передан (если s=0, пакет еще не передавался, если s=1, пакет уже был передан один раз, и т.д.), тогда как возможные действия a являются различными поднаборами узлов, к которым пакет может быть отправлен (если a={j}, то пакет отправляется только узлу j, если a={j₁,j₂}, то пакет отправляется к j₁ и j₂, если a={j₁,j₂,…,j_n}, то пакет отправляется к узлам j₁,j₂,…,j_n, и т.д.).

Для каждой пары состояние/действие (s,a), т.е. пары, формируемой числом повторных передач и набором из возможных адресатов, модуль маршрутизации каждого узла i оценивает Q-функцию Q_i(s,a), т.е. затраты, ассоциированные с исполнением действия a, когда он находится в состоянии s, т.е., затраты на отправку пакета, который уже был передан s раз к узлам в наборе a (строки 2-7).

Псевдокод алгоритма обучения

Как только различные оценки были обновлены, выбор узлов-адресатов падает на набор a, с которым ассоциированы наилучшие затраты (строка 9).

Вероятности для вычисления значений Q_i(s,a) (строка 5) получаются начиная с вероятностей пакета, отправленного узлом i, корректно принятого узлом j, как показано ниже

Сутью работы метода обучения является спецификация функции затрат, ассоциированной с различными парами состояние/действие, которая фактически определяет логику выбора набора ретрансляторов.

В предложенном здесь решении, функция , ассоциированная с каждым действием, задана ниже

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

Выражением для затрат узлов в основном направлении является

где c_j равно затратам для узла j на передачу пакета к месту назначения, т.е.,

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

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

Подробности

Оценка качества линии связи

Каждый узел продолжает отслеживать число n_i,j пакетов, корректно принятых от соседних узлов. Данное вычисление выполняется по всем пакетам, безотносительного того, является ли узел адресатом или нет одного пакета. Как только узел j корректно принял пакет, отправленный узлом i, определяется из порядкового номера пакета число n_i пакетов, отправленных узлом и из этого качество линии связи оценивается как:

где качество P_ij линии связи представляет собой вероятность того, что пакет, отправленный узлом i, будет корректно принят узлом j. Для того, чтобы иметь оценки, которые учитывают отмеченную динамичность подводного канала, значения n_i и n_ij вычисляются по отношению к скользящему временному окну соответствующих размеров.

Динамическая установка максимального числа K повторных передач

K является фундаментальным параметром протокола. Низкое значение способствует ограничению сетевого трафика, но может приводить к низкой вероятности успеха передач. Вместо этого, высокое значение K увеличивает вероятность того, что пакет принимается, но за счет увеличения сетевого трафика: адекватное значение K с низким трафиком может легко привести к условиям перегрузки сети в условиях устойчивого трафика, тем самым приводя к падению сети. В предлагаемом решении, параметр K динамически устанавливается таким образом, что среднее число G передач, выполненных во время временного окна, длина которого равна времени, необходимому для отправки пакета, равно 0.5 (идея состоит в аппроксимации поведения уровня 2 сети к широковещательной без слотов сети ALOHA, для которой известно, что пик возможности передачи сети получается при G=0.5).

Используя следующую аппроксимацию для максимальной нагрузки сети

где t_col является временем конфликта, т.е., суммой времени передачи пакета и максимального времени распространения сети (значение, которое может быть оценено на основании размера самой сети) и λ обозначает трафик в сети, значение, которое может быть оценено динамически каждым узлом на основании трафика, наблюдаемого локально, для максимального числа повторных передач, получается следующая формула:

где обозначение обозначает наименьшее целое число, которое больше x.

РАСШИРЕНИЕ ДЛЯ ДИНАМИЧЕСКОГО ВЫБОРА УСТРОЙСТВА СВЯЗИ

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

Возможные действия a указывают не только разные поднаборы узлов, к которым может быть отправлен пакет, но также устройство связи, которое должно быть использовано среди нескольких, которые могут быть доступны (если a={m₁, [j]}, то пакет отправляется только узлу j, используя устройство m₁, если a={m₂, [j₁,j₂]}, то пакет отправляется к j₁ и j₂, используя устройство m₂, если a={m₁, [j₁,j₂,…,j_n]}, то пакет отправляется узлам j₁,j₂,…,j_n, используя устройство m₁, и т.д.).

Затраты на передачу пакета также учитывают конкретное устройство m связи, выбранное для передачи пакета, при условии, что ассоциированы с разными устройствами, например, разными уровнями потребления энергии или возможностями передачи.

Вероятность того, что пакет, отправленный узлом i, будет корректно принят узлом j задается как , поскольку она зависит от конкретного используемого устройства m. Она вычисляется следующим образом: узел j, как только он корректно принял пакет, отправленный узлом i, используя устройство m, определяет, из порядкового номера пакета, число пакетов, отправленных узлом, используя упомянутое устройство, и использует в качестве оценки качества линии связи, соответствующей m, отношение

где является числом пакетов, отправленных узлом i с помощью устройства m и корректно принятых посредством j.

ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ

Чтоб подчеркнуть преимущества изобретения, далее иллюстрируются экспериментальные результаты, полученные через моделирование. Производительность CARMA была сравнена с производительностью QELAR [HuFe10], протоколом, основанным на обучении с подкреплением, который стремится получить однородное потребление энергии между узлами, но который не учитывает множество путей, и EFlood [BaPe14], улучшенная версия протокола лавинной адресации, разработанного явно для уменьшения конфликтов и повышения устойчивости к ошибкам протокола. Моделируемая подводная среда соответствует части Норвежского фьорда у берегов Трондхейма. Вся информация, необходимая для моделирования подводной среды, была получена из Базы Данных Мирового Океана (http://www.nodc.noaa.qov/OC5/WOA05/pr______woa05.html), Общей Батиметрической Карты Мирового Океана (GEBCO) (http://www.gebco.net), и базы данных National Geophysical Data Center Deck41 (http://www.ngdc.noaa.gov/mgg/geology/deck41.html).

В экспериментах, рассматривалась статическая сеть из 40 узлов (39 узлов плюс узел-получатель) позиционированных случайным образом по области 4км. × 1км. и на разных глубинах, в диапазоне между 10 и 240м. Сетевой трафик генерировался в соответствии с пуассоновским процессом параметра λ пакетов в секунду, где λ предполагает значения в наборе {0.01, 0.02, 0.04, 0.0666, 0.1}. Кроме того, рассматривалось три разных размера пакета, а именно, 50Б, 500Б, и 1000Б.

Производительность протоколов оценивалась, используя следующие метрики производительности:

- отношение пакет-доставка (PDR), а именно отношение пакетов доставленных к узлу-получателю, заданных как дробь между пакетами корректно принятыми узлом-получателем и всеми пакетами, сгенерированными узлом;

- задержка между оконечными пунктами, задана как время, которое прошло между генерированием пакета и его корректным приемом на узле-получателе; и

- энергия на бит, задана как энергия, потребленная в сети на доставку бита данных к узлу-получателю.

Результаты моделирования

Фигуры 5, 6, и 7 показывают производительность трех протоколов в описанном сценарии моделирования. Результаты относятся к размеру пакета в 1000Б, который соответствует наилучшей производительности для всех трех рассматриваемых протоколов (производительность для других размеров пакета резюмируется в Таблице 1). Для того, чтобы получить сравнение в одинаковых условиях между протоколами, характеристические параметры QELAR и EFlood были установлены в оптимальные значения, предложенные соответствующими авторами.

Метрика	50 Байт	500 Байт
CARMA	QELAR	EFlood	CARMA	QELAR	EFlood	CARMA	QELAR	EFlood	CARMA	QELAR	EFlood
Отношение пакет доставка (%)	99	64	85	58	40	49	99	98	73	77	20	32
Задержка между конечными пунктами (с)	3.77	198.8	39.21	14.85	1360.0	423.8	6.56	9.58	21.23	14.68	64.0	27.68
Энергия на бит (Дж/бит)	0.029	0.129	0.145	0.032	0.187	0.109	0.016	0.016	0.109	0.021	0.128	0.089
Потери на бит	2.48	6.44	0.23	3.67	10.15	0.18	0.17	0.055	0.160	0.29	1.12	0.132

Таблица 1 - Результаты моделирования для разного сетевого трафика и размера пакета

Отношение пакет-доставка. PDR, которое было измерено для каждого протокола фигурирует на Фигуре 5. Результаты согласуются с ожиданиями. В частности, PDR уменьшается по мере того, как растет сетевой трафик, поскольку конфликты между пакетами и вероятность нахождения занятого канала увеличиваются. В любом случае, CARMA показывает наилучшую производительность: его PDR падает со 100% до 85% только когда сетевой трафик очень высокий.

Производительность CARMA главным образом зависит от трех факторов: 1) протокол минимизирует общее число передач, необходимых для передачи пакета от источника к получателю, и, следовательно, способен идентифицировать маршруты с наивысшей вероятностью доставки пакета к месту назначения; 2) переадресация пакетов по множеству путей по мере того, как растут повторные передачи, увеличивает устойчивость к ошибкам протокола; 3) максимальное число K повторных передач вычисляется динамически на основании трафика, тем самым сокращая число повторных передач, когда трафик выше, и, следовательно, уменьшая конфликты между пакетами. Среди всех протоколов, EFlood показывает наихудшую производительность по причине высокого числа передач, которые, прежде всего по мере увеличения нагрузки, приводят к высокому числу конфликтов. С другой стороны, QELAR показывает хорошую производительность до тех пор, пока трафик в сети низкий, но его PDR быстро снижается, когда увеличивается трафик. Это происходит потому, что у него отсутствует динамическое управление числом повторных передач и потому, что он осуществляет оценку менее точно, чем это делает CARMA, качества линий связи. При высоких нагрузках сложность подслушивания пакетов, которое является основным механизмом, используемым QELAR для оценки качества линии связи, приводит к много менее точной оценке и, следовательно, неоптимальным решениям маршрутизации.

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

CARMA и QELAR показывают хорошую производительность при низких интенсивностях трафика, при этом CARMA способен значительно уменьшать потребление в случае меньшего размера пакета (Таблица 1). Тем не менее, по мере того, как растет уровень трафика, производительность QELAR снижается в результате более высокого числа повторных передач и из-за более низкого числа битов данных, корректно доставляемых получателю.

Фигура 8 показывает, каким образом энергия на бит меняется между сетевыми узлами, рассматривая два сценария, соответствующие низкому и высокому уровню нагрузки. Эффективность энергии очень однородна в CARMA, тогда как она представляет большую изменчивость в двух других протоколах.

Задержка между конечными пунктами. Фигура 7 показывает среднюю задержку для доставки пакетов к узлу-получателю. Как и следовало ожидать, по мере того, как увеличивается уровень трафика, также растет время, необходимое для доставки пакета. CARMA доставляет пакеты в наиболее короткое время во всех рассматриваемых сценариях. Посредством сокращения числа повторных передач, необходимых для доставки пакета, CARMA эффективно действует на задержку. EFlood представляет, вместо этого, более длительные задержки, которые зависят от запаздываний, которые вводятся для десинхронизации передающих узлов, но которые остаются сходными безотносительно сетевого трафика. В EFlood каждый пакет передается точно раз каждым узлом (отсутствуют повторные передачи), ограничивая задержку, но за счет более низкого PDR. QELAR представляет задержку сравнимую с той, что у CARMA при низких уровнях трафика, за исключением того, что она значительно растет по мере того, как растет уровень трафика. Это происходит потому, что протокол QELAR отличается высоким коэффициентом повторной передачи (на 150% выше коэффициента, когда трафик низкий) совместно со сложностью приема неявных квитанций, которые подвергают риску возможность корректной маршрутизации пакетов.

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

ССЫЛКИ

[SuBa98] R. S. Sutton и A. G. Barto, Reinforcement Learning: An Introduction. Cambridge Univ. Press, 1998г.

[BaPe14] S. Basagni, C. Petrioli. R. Petroccia и D. Spaccini. «CARP: A Channel-aware Routing Protocol for Underwater Acoustic Wireless Networks», в прессе, Elsevier Ad Hoc Networks and Physical Communication. 2014г.

[HuFe10] T. Hu и Y. Fei, «QELAR: A Machine Learning Based Adaptive Routing Protocol for Energy Efficient and Lifetime Extended Underwater Sensor Networks», IEEE Transactions on Mobile Computing, Том 9, №. 6, стр. 796-808, июнь 2010г.

[PlWa14] R. Plate, C. Wakayama, «Uti1izing kinematics and selective sweeping in reinforcement learning based routing algorithms for underwater networks», в прессе, Elsevier Ad Hoc Networks and Physical Communication. 2014г.

[US2026] US 2012/192026 A1 (CHEN REN-JR [TW] И ДРУГИЕ) 26 июля 2012г.

[US1082] US 2004/071082 A1 (BASU ANINDYA [US] И ДРУГИЕ) 15 апреля 2004г.

1. Способ для выбора, в подводной сенсорной сети связи, на каждой передаче/повторной передаче пакета, набора узлов, к которым упомянутый пакет должен быть отправлен и который предусматривает, для каждого узла, модуль, который регулирует политику передачи/повторной передачи уровня LLC (Управление Логической Связью), и модуль маршрутизации, причем упомянутый способ отличается тем, что он содержит этапы, на которых:

используют самообучающийся алгоритм, который определяет, для каждого пакета, автономно и без явного обмена сообщениями квитирования, учитывая число раз, которое данный пакет уже был передан, оптимальный набор узлов, к которым данный пакет должен быть повторно отправлен (логика маршрутизации); и

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

при этом подуровень LLC регулирует логику повторной передачи у узла посредством выполнения последовательно следующих этапов:

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

после того, как узел отправил пакет и установил таймер, он ожидает неявной квитанции, используя метод подслушивания, в силу чего пакет считается успешно отправленным, если, по меньшей мере, один из узлов, к которым он отправил пакет, повторно передает его, и затем переходит к передаче следующего пакета;

если, вместо этого, не обнаруживается копии пакета, предполагают, что ни один из узлов не принял пакет, и осуществляют повторную передачу пакета после периода отсрочки;

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

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

3. Способ по любому из предшествующих пунктов, отличающийся тем, что упомянутый алгоритм является идентичным для всех узлов и основан на Q-обучении.

4. Способ по предшествующему пункту, отличающийся тем, что в упомянутом самообучающемся алгоритме, в каждом узле i состояние s пакета представляется числом раз, которое пакет был передан (s=0, если пакет еще не передавался, s=1, если пакет уже был передан один раз), тогда как возможные действия a являются различными подмножествами узлов, к которым пакет может быть отправлен:

(a={j}: пакет отправляется только узлу j, a={j₁,j₂}: пакет отправляется к узлам j₁ и j₂,

a={j₁,j₂,…,j_n}: пакет отправляется к узлам j₁,j₂,…,j_n);

и тем, что

для каждого состояния самообучающийся алгоритм продолжает отслеживать набор переменных Q_i(s,a) для каждого значения s и a, причем Q_i(s,a) представляет собой локальную оценку модуля маршрутизации касательно затрат, ассоциированных с исполнением действия a, когда узел i находится в состоянии s, т.е. суммарные затраты, ассоциированные с отправкой к узлам в наборе a пакета, который уже был передан s раз.

5. Способ по предшествующему пункту, отличающийся тем, что алгоритм предусматривает, что всякий раз, когда узел должен отправлять пакет, он выполняет следующие два этапа: на первом этапе, он обновляет оценки Q_i(s,a); и на втором этапе, он выбирает, на основании значений этих оценок, набор узлов, к которым отправлять пакет.

6. Способ по предшествующему пункту, отличающийся тем, что, на этапе обновления, он вычисляет новое значение Q_i(s,a) как сумму из: суммарных затрат, ассоциированных с текущей передачей к узлам в наборе a пакета, который уже был передан s раз; и средние затраты - дисконтированные на коэффициент гамма, заключенный между 0 и 1 - из затрат возможно дальнейших повторных передач того пакета,

где

суммарные затраты, ассоциированные с текущей передачей к узлам в наборе a пакета, который уже был передан s раз, равны сумме следующих трех членов:

i. затраты на передачу пакета к набору узлов, ассоциированному с действием a;

ii. затраты, используемые узлами набора a, чтобы доставлять пакет в место назначения, причем упомянутые затраты задаются как сумма затрат на передачу каждого узла j принадлежащего к набору a, причем каждые взвешенные с помощью вероятности того, что пакет, отправленный узлом i достигает узла j; и

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

при этом, в сумме, члены i и iii взвешиваются (с помощью неотрицательных весовых коэффициентов, общая сумма которых равна 1) на основании прикладных требований; и

более того, если число s повторных передач меньше максимального значения K повторных передач, член iii не рассматривается поскольку пакет еще не считается потерянным.

7. Способ по предшествующему пункту, отличающийся тем, что

как только различные оценки были обновлены, выбор узлов-адресатов падает на набор a, с которым ассоциированы наилучшие затраты (самое низкое значение).

8. Способ по п. 1, отличающийся тем, что:

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

как только узел j принял корректно пакет, отправленный узлом i, он определяет, из порядкового номера пакета, число пакетов n_i, отправленных узлом, и использует в качестве оценки качества линии связи отношение между принятыми пакетами и отправленными пакетами, вычисленное по отношению к скользящему временному окну соответствующих размеров, для того, чтобы иметь оценки, которые учитывают отмеченную динамичность подводного канала.

9. Способ по любому из предшествующих пунктов, отличающийся тем, что:

максимальное число K повторных передач равно наименьшему целому числу, которое больше отношения между числом 0.5 и произведением между временем конфликта, т.е. суммой времени передачи пакета и максимальным временем распространения сети (значение, которое может быть оценено на основании размера самой сети), и сетевым трафиком, который является значением, которое может быть оценено динамически каждым узлом на основании трафика, наблюдаемого локально.

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

11. Способ по п. 10 или 4, дополнительно отличающийся тем, что в упомянутом самообучающемся алгоритме, в каждом узле i, состояние s пакета представляется числом раз, которое пакет был передан (s=0, если пакет еще не был передан, s=1, если пакет уже был передан один раз), тогда как возможные действия a указывают устройство связи, которое должно быть использовано, и разные поднаборы узлов, к которым пакет может быть отправлен:

a={m₁, [j]}, если пакет отправляется только узлу j, используя устройство m₁;

a={m₂, [j₁,j₂]}, если пакет отправляется к j₁ и j₂, используя устройство m_2;

a={m₁, [j₁,j₂,…,j_n]}, если пакет отправляется узлам j₁,j₂,…,j_n, используя устройство m₁.

12. Способ по п. 10 или 6, дополнительно отличающийся тем, что полные затраты, ассоциированные с текущей передачей, к узлам набора a, пакета, который уже был передан s раз равны сумме следующих трех членов:

i. затраты на передачу пакета, используя устройство связи, указанное действием a;

ii. затраты, используемые узлами набора a, чтобы доставлять пакет в место назначения, заданы как сумма затрат на передачу каждого узла j принадлежащего к набору a, причем каждые взвешенные с помощью вероятности того, что пакет, отправленный узлом i достигает узла j (вероятность, которая зависит от конкретного используемого устройства связи); и

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

13. Способ по п. 10, отличающийся тем, что:

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

узел j, как только он корректно принял пакет, отправленный узлом i, используя устройство m, определяет, из порядкового номера пакета, число пакетов, отправленных узлом, используя упомянутое устройство, и использует в качестве оценки качества линии связи, соответствующей m отношение между принятыми пакетами и отправленными пакетами, вычисленное по отношению к скользящему временному окну соответствующих размеров, для того, чтобы иметь оценки, которые учитывают отмеченную динамичность подводного канала.