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

Модель состоит из произвольной (неориентированной) сети, процессоры которой общаются в синхронных временных интервалах, подчиняясь следующим правилам. В каждом временном интервале каждый процессор выступает либо в роли ''передатчика'', либо в роли ''приемника''. Мы говорим, что процессор, выступающий в роли приемника, получает сообщение во временном интервале <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>.'''

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

Процедура 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).