Маршрутизация пакетов при использовании технологии идентификации генетических полиморфизмов в прикладных системах

Константин Зайцев (Докт. техн. наук, профессор, Национальный исследовательский ядерный университет МИФИ)
Антон Чураев (Аспирант, Национальный исследовательский ядерный университет МИФИ)

Введение

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

Совершенствование подходов к маршрутизации

Самоорганизация сети

Синхронизированные кластеры

Операции над кластерами

Межкластерная маршрутизация

Список использованной литературы

Введение

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

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

Несмотря на внимание, уделяемое в последние годы проблеме генетической идентификации личности во всем мире, имеется ряд нерешенных задач, препятствующих широкому применению этих новых технологий в «полевой» практике. Одной из них, наряду с совершенствованием приборной и реактивной составляющих, является существенная минимизация времени идентификации личности, то есть времени обмена сообщениями в сети передачи идентификационных данных, центральным звеном которой является оптимизация маршрутов. Отметим также, что в подавляющем большинстве случаев приходится иметь дело с сетями с переменной топологией. Исследованию этой задачи в рамках реализации проекта ФЦП «Научные и научно­педагогические кадры инновационной России» на 2009­2013 годы и посвящена настоящая статья.

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

Качество работы сети напрямую зависит от того, насколько эффективны используемые алгоритмы доставки пакетов идентификационных данных. К настоящему времени разработано множество алгоритмов маршрутизации различной степени эффективности и универсальности, успешно работающих в сетях с постоянной и переменной топологией, — AODV [1], OSPF [2], DSR [3], OLSR [4], TORA  [5, 6], HSLS [7]. Эти и множество других алгоритмов маршрутизации можно условно разделить на два класса: реактивные (reactive, on­demand routing) и проактивные (proactive).

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

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

Однако эффективность работы и проактивных и реактивных алгоритмов резко снижается при увеличении скорости изменения топологии сети. Снижение эффективности работы реактивных алгоритмов объясняется тем, что кэшированные маршруты транспортировки пакетов быстро устаревают из­за разрушения составляющих их связей. В предельном случае применение реактивного алгоритма становится невозможным из­за того, что маршруты доставки пакетов будут успевать разрушаться за время их нахождения. Использование проактивных алгоритмов в сети с высокой скоростью изменения топологии приведет к резкому повышению объема служебного трафика для поддержания актуальности маршрутных таблиц, что, в свою очередь, является предвестником коллапса сети из­за того, что будет исчерпан ресурс пропускной способности каналов связи. Поэтому для организации процесса маршрутизации пакетов данных в сети с быстро меняющейся топологией ни проактивные, ни реактивные алгоритмы в чистом виде не могут применяться. Они пытаются построить полный путь от узла­отправителя к узлу­получателю, что в большой сети с быстро меняющейся топологией приводит к тому, что длинные маршруты успевают разрушаться быстрее их окончательного построения. Это заставляет базироваться на локальных свойствах сети при построении эффективных алгоритмов маршрутизации. «Локальный» подход дает два преимущества. Во­первых, происходит экономия ресурсов при реагировании на изменение топологии сети, а во­вторых, при быстром изменении топологии, как бы ни был отлажен механизм оповещения, узел знает ситуацию в непосредственной близости от себя лучше, чем в остальной части сети, и алгоритм маршрутизации должен извлекать из этого выгоду.

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

Иллюстрацией двух этих принципов служит распределенный алгоритм маршрутизации TORA (Temporally­Ordered Routing Algorithm) для мобильных беспроводных сетей с ретрансляторами. Алгоритм разработан для минимизации требуемой реакции на изменение топологии путем устранения взаимосвязи между генерацией глобальных управляющих сообщений и частотой изменения топологии сети. Это позволяет алгоритму не перегружать сеть служебным трафиком даже при крайне нестабильной топологии.

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

Совершенствование подходов к маршрутизации

Одним из путей совершенствования алгоритмов маршрутизации является применение вероятностных характеристик при построении маршрутов [9]. При таком подходе удается использовать статистическую информацию об изменениях в топологии сети для выявления наиболее вероятных кратчайших маршрутов между узлами. Предполагается, что в сети многие узлы связаны между собой, но связь эта непостоянна и может периодически выключаться. Выключение связи в реальных сетях может соответствовать удалению мобильных устройств друг от друга (за пределы радиуса действия) или выключению сенсорных датчиков с целью экономии заряда аккумуляторов. В качестве модели функционирования связи предлагается применять стационарный, Марковский процесс с двумя состояниями: связь работает и связь не работает. При этом интенсивности переходов состояний считаются постоянными величинами и введены вероятности нахождения связи в каждом из состояний в каждый момент времени.

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

В [9] описана серия экспериментов для исследования сравнительной эффективности вероятностного и классического подходов. Эксперимент показал, что эффективность классического алгоритма довольно быстро снижается с течением времени, в то время как эффективность вероятностного алгоритма остается примерно постоянной, несмотря на то что в начале эксперимента классический подход выглядит предпочтительным. Чем быстрее изменяется топология сети, тем быстрее падает эффективность классического алгоритма. Очевидно, что в чистом виде вероятностный подход не годится для практического применения, так как имеет хотя и постоянную, но довольно низкую эффективность. Поэтому следует комбинировать его с классическим подходом.

Если перемещение узлов сети ограничено пределами некой относительно небольшой области либо узлы периодически меняют состояние по некому циклическому алгоритму (так называемые сети с ограниченной мобильностью [10]), то статистические параметры связей являются стабильными, гарантируя возможность путем достаточно длительного наблюдения за состоянием связи установить параметры случайного процесса ее переключения. Поскольку в каждый момент времени список доступных узлов­соседей может быть мал, хотя полный их список известен и относительно велик, многие стандартные сетевые алгоритмы, в частности лавинная рассылка и случайные блуждания в сетях с ограниченной мобильностью, несколько видоизменяются. Классический алгоритм лавинной рассылки широко применяется для служебных целей в составе различных алгоритмов маршрутизации, в том числе предназначенных для использования в сетях с переменной топологией. Принцип его действия заключается в следующем:

• узел, получивший пакет данных, проверяет, не истекло ли его время жизни TTL (Time to live);
• если TTL пришедшего пакета данных истек — пакет уничтожается;
• проверяется, обрабатывал ли уже текущий узел этот пакет (это нужно для предотвращения дублирующих рассылок). Если пакет уже обрабатывался текущим узлом — он уничтожается;
• в противном случае TTL уменьшается на единицу и пакет рассылается всем узлам, смежным с текущим (кроме узла, от которого пришел пакет).

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

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

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

1. Узел­отправитель высылает некоторое количество экземпляров пакета данных своим соседям (как правило, различным), выбранным случайным образом (это количество является параметром алгоритма).
2. Узел, получивший пакет и не являющийся адресатом, проверяет, не истек ли TTL пакета.
3. Если TTL пакета оказывается равен нулю, то пакет уничтожается.
4. В противном случае узел уменьшает TTL пакета на единицу и пересылает его соседнему узлу, выбранному случайным образом (отличному от того, от которого этот пакет был получен).

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

Самоорганизация сети

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

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

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

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

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

Сеть с выделенным в ней узлом­координатором представляет собой нулевой уровень самоорганизации. Поскольку на этом этапе сеть не организована, то применяться могут только простейшие алгоритмы маршрутизации «без состояния» вроде лавинной рассылки и случайных блужданий с поправкой на специфику сетей с переменной топологией.

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

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

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

Синхронизированные кластеры

Заметим, что в пределах синхронизированного кластера можно эффективно решать задачи по построению устойчивого канала связи (УКС), например с помощью подхода, предлагаемого в [4]. Также поскольку между кластерами по­прежнему сохраняется хаос или, в лучшем случае, имеется простейшая вероятностная метрика, то маршрутизация сообщений вне кластеров должна выполняться с использованием соответствующих алгоритмов. В случае если кластеры захватят достаточно большую часть сети, представляется целесообразным применять для этой цели различные виды случайных блужданий, например модифицированный адаптивный алгоритм EBAS [5]. Разумеется, с учетом специфики блужданий в сетях с переменной топологией.

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

1. В некий момент времени один из узлов сети принимает решение установить устойчивое соединение с другим узлом.
2. Узел блокирует себя от выключения.
3. Узел формирует специальный пакет данных, информирующий об инициализации процесса построения канала, и высылает его в пункт назначения узлу­координатору с помощью имеющегося в его распоряжении узла алгоритма маршрутизации.
4. Каждый узел, получивший служебный пакет, направленный узлу­получателю и сформированный на третьем шаге, блокирует себя от выключения и выполняет дальнейшую пересылку этого пакета.
5. Как только узел­получатель принимает служебный пакет, информирующий об инициации процесса построения канала, он отправляет по сформированной цепочке пакет, информирующий об успешном завершении построения.
6. Получив пакет об успешном построении канала, узел, инициировавший его построение, начинает передачу данных.

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

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

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

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

Помимо этой есть и другие причины ввода кластеров на пространстве сети:

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

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

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

Операции над кластерами

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

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

Кластер объединяет узлы, связи между которыми проявляют стабильность на протяжении некоторого времени. Но это не все требования для объединения. Основной причиной разделения сети на кластеры является то, что управление меньшими множествами является более простым. Поэтому для объединения узлов введем критерии принятия узла в кластер.

Первым критерием является определение возможности расширения кластера на один узел. Самым простым решением этой задачи является сравнение мощности кластера с максимально допустимой, которая определяется на стадии проектирования сети. Но этот подход не является оптимальным, так как ввиду высокой мобильности узлы могут изменять свое местоположение довольно часто, что вызывает уничтожение существующих связей между ними. И несмотря на то, что приведенный критерий может применяться только для определения «насыщенности» кластера, уже на этом этапе можно фильтровать узлы по «лояльности». Это поможет не только увеличить вероятность создания стабильного кластера, но и обеспечит уменьшение вычислительной нагрузки на координатора сети, а также на саму сеть из­за сокращения служебного трафика.

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

При заполнении кластера узлы могут включаться в него, пока мощность кластера (рис. 1) не достигнет некого порогового значения Kh. По достижении этой мощности кластер либо должен разделиться на два при попытке подключения к нему новых узлов, либо из него могут только удаляться какие­то узлы. Добавлять же узлы к кластеру нельзя до тех пор, пока его мощность не снизится до Kl. Верхняя метка вводится на узел­координатор из­за ограничений по вычислительным возможностям, нижняя — для предотвращения частого деления кластеров. Она позволяет создавать стабильные кластеры.

Рис. 1. Пороговые метки заполнения кластера

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

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

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

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

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

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

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

Рассмотрим также процедуру удаления узла из кластера, которая необходима при:

• перемещении узла;
• выключении либо перемещении узла­шлюза;
• выключении узла.

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

Межкластерная маршрутизация

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

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

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

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

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

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

Рис. 2. Число пересылок в модифицированный алгоритм случайных блужданий

Для получения данных о средней задержке передачи пакета были использованы остаточные значения TTL запроса. Усреднив значения, найденные путем вычитания из начального значения TTL значения TTL, полученного на конкретном узле, мы составили график зависимости задержки доставки пакета от доли узлов, не объединенных в кластер (рис. 3).

Рис. 3. Задержка передачи в модифицированном алгоритме случайных блужданий в кластеризованной сети

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

N1 + N1N2x+…+N1…Nkx^k–1,

А для распределения задержки передачи пакета:

1+x^N1+x^N1+N1N2+…+x^{N1+…N1…N2},

где N=[N1N2…Nk] — число ветвлений при каждой пересылке.

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

Список использованной литературы

1. Ad hoc On­Demand Distance Vector (AODV) Routing [Электр. ресурс] / http://tools.ietf.org/html/rfc3561.
2. OSPF Version 2 [Электр. ресурс] / http://tools.ietf.org/html/rfc2328.
3. The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4 [Электр. ресурс] / http://tools.ietf.org/html/rfc4728.
4. Optimized Link State Routing Protocol (OLSR) [Электр. ресурс] / http://tools.ietf.org/html/rfc3626.
5. Temporally­Ordered Routing Algorithm (TORA) Version 1 Fucntion Specification [Электр. ресурс] / http://ietf.org/proceedings/53/I­D/draft­ietf­manet­tora­spec­04.txt.
6. A Performance Comparison of the Temporaly­Ordered Routing Algorithm and Ideal Link­State Routing [Электр. ресурс] / http://doi.ieeecomputersociety.org/10.1109/ISCC. 1998.702600.
7. Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm [Электр. ресурс] /
   http://ir.bbn.com/documents/techmemos/TM1201.pdf.
8. Гуляев Ю.В. Сенсорные сети на основе сопряженных разнородных каналов связи // Перспективные технологии в средствах передачи информации: Материалы VII Международной конференции. Владимир, 2007.
9. Батаев Р.А. Вероятностный подход в создании алгоритмов маршрутизации в сетях с изменяющейся топологией. СПб., 2007.
10. Шамин П.Ю. Многоцелевая маршрутизация в самоорганизующихся сетях с ограниченной мобильностью. Владимир, 2008.

САПР и графика 10`2010