4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 16:45, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 61: | Строка 61: | ||
Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. | Этот результат верен также для узлов, сформированных при помощи равномерного распределения случайной величины. | ||
'''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология''' | '''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология''' | ||
| Строка 74: | Строка 75: | ||
3. Как только узел v получает сообщение UPDATEN от соседа u из N(v), он проверяет, не находится ли он сам в списке узлов, предназначенных для удаления: обнаружив себя в нем, он удаляет узел-отправитель u из списка N(v), в противном случае помечает u как BLACK в N(v). | 3. Как только узел v получает сообщение UPDATEN от соседа u из N(v), он проверяет, не находится ли он сам в списке узлов, предназначенных для удаления: обнаружив себя в нем, он удаляет узел-отправитель u из списка N(v), в противном случае помечает u как BLACK в N(v). | ||
4. После того, как все узлы будут обработаны, все выбранные ссылки | |||
4. После того, как все узлы будут обработаны, все выбранные ссылки <math>\{ uv | v \in N(u), \forall v \in GG \}</math> образуют финальную топологию сети, обозначаемую <math>S \Theta\ GG</math>. Каждый узел может уменьшить диапазон передачи таким образом, чтобы успешно доставать до самого далекого соседа в финальной топологии. | |||
| Строка 80: | Строка 82: | ||
1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные. | 1: Все вершины совокупно составляют граф <math>S \Theta\ GG</math> в локализованной форме, построенный при помощи алгоритма 1. Каждая вершина помечает инцидентные ей дуги в <math>S \Theta\ GG</math> как необработанные. | ||
2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей ЕгМ., определяемое следующим образом: £гМ = fuv 2 <math>S \Theta\ GG</math> j u или v 2 NUDG(X)G. Иными словами, ЕгМ представляет собой набор дуг в S | 2: Каждый узел u локально рассылает инцидентные ему дуги в <math>S \Theta\ GG</math> своим односкачковым соседям при помощи широковещательной трансляции и сам прослушивает своих соседей. Затем каждый узел x исследует существование множества двухскачковых связей ЕгМ., определяемое следующим образом: £гМ = fuv 2 <math>S \Theta\ GG</math> j u или v 2 NUDG(X)G. Иными словами, ЕгМ представляет собой набор дуг в <math>S \Theta\ GG</math>, имеющих по меньшей мере одну конечную точку в диапазоне передачи узла x. | ||
3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в E2(x), он удаляет дугу xy в случае, если существует дуга uv € ЕгМ (где u и v отличны от x и y), такая, что kxyk > max(kuvk; 3kuxk; 3kvyk); в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при попомщи широковещательного сообщения UPDATESTATUS(XY). | 3: После того, как узел x обнаружит, что необработанная инцидентная ему дуга xy имеет наименьший идентификатор среди всех необработанных связей в E2(x), он удаляет дугу xy в случае, если существует дуга uv € ЕгМ (где u и v отличны от x и y), такая, что kxyk > max(kuvk; 3kuxk; 3kvyk); в противном случае он помечает дугу xy как обработанную. Предположим, что uvyx представляет собой выпуклую оболочку, состоящую из узлов u, v, x и y. Тогда статус связи передается всем соседям при попомщи широковещательного сообщения UPDATESTATUS(XY). | ||
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | 4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | ||