Маршрутизация в геометрических сетях: различия между версиями

Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. Во всех трех классах особое внимание уделяется построению маршрута сообщения из источника к адресату, включающего минимально возможное количество этапов коммуникации. Заметим, что количество этапов коммуникации соответствует общему числу передач. Таким образом, минимизируя количество этапов коммуникации, мы уменьшаем и количество передач, способствуя экономии энергии. Далее рассмотрим список комбинаторных и алгоритмических определений, часто используемых контексте геометрической маршрутизации.

'''Граф единичных дисков''' (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором две вершины <math>u, v \in V</math> соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

'''Граф Гэбриэла''' (Gabriel Graph, GG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.