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

Ранние алгоритмы «пересылки наиболее продвинутому узлу в пределах диапазона» (most forward within range, MFR) или жадной географической маршрутизации [14] направляли сообщения, исходя из соображений максимизации в процессе каждого скачка продвижения по спроецированной линии на пути к точке назначения – или, напротив, минимизации оставшегося расстояния до точки назначения сообщения. Обе эти жадные эвристики объединяются по общим названием «''жадная переадресация''» (greedy forwarding, GF). Эта техника маршрутизации выглядит весьма многообещающей для применения в беспроводных сетях датчиков, чему есть немало причин. (1) Жадная переадресация, как это почти повсеместно требуется, является ''полностью децентрализованной''. (2) Это ''легкая'' техника в том смысле, что она не добавляет расходов на управление топологией. (3) Она обеспечивает коммуникацию типа «''все со всеми''», а не «все с одним». (4) Благодаря отсутствию предположений о структуре коммуникационного графа, который может быть ориентированным, неориентированным, стабильным или динамическим (например, вершины могут быть мобильными, а беспроводные связи могут появляться и исчезать – скажем, в силу изменений окружающей обстановки или в результате работы более низких уровней стека протоколов, таких как схемы перехода в спящий режим и выхода из него с целью экономии энергии), техника оказывается весьма ''надежной''. (5) Она работает ''по запросу'': до распространения сообщения не строится таблицы маршрутизации или градиента. (6) Ее ''эффективность'' связана с тем, что сообщения находят короткие пути к точкам назначения (в терминах количества скачков). (7) Техника ''проста'' и в силу этого ''удобна для внедрения''. (8) Она ''эффективно использует память'' в том смысле, что (8а) в заголовке сообщения хранится только информация о точке назначения и (8б) процесс работает «экологично», поскольку в посещаемых сообщением сенсорных узлах не остается «мусорной» информации.

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