Локальные вычисления в неструктурированных радиосетях: различия между версиями

Теорема 1. Если узлы не знают n, то в односкачковых сетях каждый (возможно, рандомизированный) алгоритм требует до J2(n/log n) временных интервалов, прежде чем хотя бы один узел сможет отправить сообщение.

Для односкачковых сетей, в случае если n известно глобально, в [8] представлен рандомизированный алгоритм, который с высокой вероятностью выбирает уникального лидера за время O( n log n). Впоследствии Юрдзински и Стаховяк [ ] улучшили этот результат до O(log2 n). Обобщенная задача пробуждения в многоскачковой радиосети была впервые изучена в работе [4].

Теорема 2. В модели неструктурированной радиосети ожидаемая O(1)-аппроксимация задачи нахождения доминирующего множества может быть вычислена за ожидаемое время O(log 2n). Иначе говоря, каждый узел решает, присоединиться ли к доминирующему множеству, в течение O(log n) временных интервалов после своего пробуждения.

В последующей работе [ ] было показано, что времени выполнения O(log n) достаточно даже для вычисления более сложной структуры максимального независимого множества. Этот результат является асимптотически оптимальным, поскольку, улучшая ранее известное ограничение £?(log n/loglogn)[ ], в [6] было доказано соответствующее нижнее ограничение Q(log n).

Теорема 3. С высокой вероятностью максимальное независимое множество может быть вычислено за ожидаемое время O(log n) в модели неструктурированной радиосети. Это время является асимптотически оптимальным.

Любопытно сравнить эту достижимую верхнюю границу для жесткой модели неструктурированной радиосети с лучшими известными нижними границами времени выполнения у моделей передачи сообщений: £?(log*n) на графах единичных дисков [12] и Q (log n/ log log log n) на графах общего вида [11]. Кроме того, в [7] была доказана временная граница O(log2n) в модели радиосети без асинхронного пробуждения, в которой узлы априори знают своих соседей. Наконец, также можно эффективно раскрашивать узлы сети, как было показано в [17], а затем улучшено и обобщено в главе 12 работы [15].

Теорема 4. В модели неструктурированной радиосети правильная раскраска не более чем в O(A) цветов может быть с высокой вероятностью вычислена за время O(A log n).

Аналогичные границы для модели с механизмами обнаружения конфликтов были доказаны в работе [ ].