Рандомизированная широковещательная передача в радиосетях: различия между версиями

Модель состоит из произвольной (неориентированной) сети, процессоры которой общаются в синхронных временных интервалах, подчиняясь следующим правилам. В каждом временном интервале каждый процессор выступает либо в роли ''передатчика'', либо в роли ''приемника''. Мы говорим, что процессор, выступающий в роли приемника, получает сообщение во временном интервале <math>t</math>, если ровно один из его соседей ведет передачу в этом временном интервале. Полученное сообщение соответствует переданному. Если в данном временном интервале несколько соседей ведут передачу, возникает ''конфликт''. В этом случае приемник может либо получить сообщение от одного из передающих соседей, либо не получить никакого сообщения. Предполагается, что конфликты (или ''коллизии'') необнаружимы, поэтому процессор не может отличить случай, когда ни один сосед не ведет передачу, от случая, когда два или более его соседей передают в этом временном интервале. Процессоры не обязаны иметь идентификаторы и не знают своих соседей; в частности, процессорам неизвестна топология сети.

Единственными входными данными, необходимыми протоколу, являются <math>n</math> – количество процессоров в сети, <math>\Delta</math> – априорно известная верхняя граница максимальной степени сети и граница ошибки – <math>\epsilon</math>. (Все границы априорно известны алгоритму).

Основным результатом является рандомизированный протокол, который обеспечивает широковещательную передачу за время, оптимальное с точностью до логарифмического множителя. В частности, с вероятностью <math>1 - \epsilon</math> протокол обеспечивает широковещательную передачу за <math>O((D + log \; n / \epsilon) \cdot log \; n)</math> временных интервалов.

Далее следует описание процедуры отправки сообщения m, которая выполняется каждым процессором после получения m:

'''Теорема 1. Пусть <math>y</math> – вершина из <math>G</math>. Пусть <math>d \ge 2</math> соседей <math>y</math> выполняют процедуру ''Decay'' в течение интервала времени [0, k) (предполагается, что все они начинают выполнение в Time = 0). Тогда <math>P(k, d)</math> – вероятность того, что <math>y</math> получит сообщение к моменту Time = k – удовлетворяет следующим свойствам:

Протокол широковещательной передачи выполняет несколько вызовов процедуры ''Decay''(k, m). Согласно теореме 1 (2), чтобы вероятность получения сообщения процессором <math>y</math> была не ниже 1/2, параметр <math>k</math> должен быть не меньше <math>2 \; log \; d</math> (где <math>d</math> – число соседей, посылающих сообщение процессору <math>y</math>). Поскольку <math>d</math> неизвестно, параметр был выбран равным <math>k = 2 \lceil log \; \Delta \rceil</math> (напомним, что параметр <math>\Delta</math> был определен как верхняя граница полустепени захода). Теорема 1 также требует, чтобы все участники начинали выполнять процедуру ''Decay'' в один и тот же временной интервал. Поэтому ''Decay'' запускается только при целочисленных кратных <math>2 \lceil log \; \Delta \rceil</math>.

 

     дождаться (Time mod k) = 0;

   Decay(k, m); }

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

'''Теорема 2. Пусть <math>T = 2D + 5 max \{ \sqrt{D}, \sqrt{log(n / \epsilon}) \} \cdot \sqrt{log(n / \epsilon})</math>. Предположим, что Broadcast_scheme запускается в момент времени Time = 0. Тогда с вероятностью выше <math>1 - 2 \epsilon</math> к моменту времени <math>2 \lceil log \; \Delta \rceil \cdot T</math> все узлы получат сообщение. Более того, с вероятностью выше <math>1 - 2 \epsilon</math> все узлы завершат работу к моменту времени <math>2 \lceil log \; \Delta \rceil \cdot (T + \lceil log(N / \epsilon) \rceil )</math>.'''

• '''Знание размера сети''': протокол работает почти так же хорошо, если вместо фактического числа процессоров (т. е. n) дать «хорошую» верхнюю границу этого числа (обозначается N). Верхняя граница, полиномиальная от n, дает ту же самую временную сложность с поправкой на константный коэффициент (поскольку сложность логарифмически зависит от N).

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

• Простота и быстрота локальных вычислений: в каждый временной интервал каждый процессор выполняет постоянный объем локальных вычислений.

• Сложность по числу сообщений: каждый процессор активен в течение [log(We)] последовательных фаз, а среднее число передач за фазу составляет не более 2. Таким образом, ожидаемое число передач всей сети ограничено 2n - flog(We)].

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

• Ориентированные сети: протокол не использует подтверждения. Таким образом, он может применяться даже тогда, когда каналы связи не симметричны; иначе говоря, тот факт, что процессор v может передать сообщение процессору u, не означает, что и может передать сообщение v. (Соответствующей моделью сети, таким образом, является ориентированный граф). В реальной жизни такая ситуация возникает, например, когда v имеет более мощный передатчик, чем u.

Для детерминированных алгоритмов можно продемонстрировать нижнюю границу: для любого n существует семейство n-узловых сетей, такое, что каждая детерминированная широковещательная схема требует O(n) времени. Для любого непустого подмножества S С {1, 2...n g рассмотрим следующую сеть GS (рис. 1).

Узел 0 является источником, а узел n + 1 – стоком. Источник инициирует сообщение, и задача широковещательной передачи в GS заключается в том, чтобы достичь стока. Сложность проистекает из того факта, что разбиение среднего уровня (т. е. S) не известно заранее. Следующая теорема может быть доказана путем ряда сокращений до определенной «игры на попадание»:

'''Теорема 3. Каждый детерминированный протокол широковещательной передачи, корректный для всех n-узловых сетей, требует O(n) времени.'''

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

Процедура Decay использовалась для разрешения соперничества устройств в радиосетях и сетях сотовой связи.

• Алон и др. [ ] доказали существование семейства сетей радиуса 2 с n вершинами, для которых любое расписание широковещательной передачи требует не менее £?(log n) временных слотов.

• Кушилевиц и Мансур [ ] показали, что для любого рандомизированного широковещательного протокола существует сеть, в которой ожидаемое время передачи сообщения равно ^(Dlog(WD)).

• Бруски и Дель Пинто [ ] показали, что для любого детерминированного алгоритма распределенной трансляции, любых n и D < n/2 существует сеть с n узлами диаметром D, такая, что время, необходимое для широковещательной передачи, равно £2(Dlogn).

• Ковальски и Пелц [ ] обсудили сети, в которых коллизии неотличимы от отсутствия передачи. Они представили нижнюю границу £?(nlog n/log(n/D)) и верхнюю границу O(nlogn). Для этой модели они также предложили рандомизированный алгоритм O(Dlog n + log2 n), подтвердив нижнюю границу из [ ] и улучшив границу из работы [ ] для графов, для которых D = e(n/logn).