Географическая маршрутизация
Ключевые слова и синонимы
Направленная маршрутизация; геометрическая маршрутизация; маршрутизация на основе географического местоположения; маршрутизация на основе положения
Постановка задачи
Географическая маршрутизация – это тип маршрутизации, особенно подходящий для динамических децентрализованных сетей. Иногда ее называют направленной или геометрической маршрутизацией, а также маршрутизацией на основе географического местоположения или на основе положения. Она основывается на двух принципиальных предположениях. Во-первых, предполагается, что каждая вершина знает свое положение и положение своих соседей по сети. Во-вторых, предполагается, что вершине-источнику сообщения известно положение вершины-адресата. Географическая маршрутизация определяется на евклидовом графе – то есть графе, вершины которого встроены в евклидову плоскость. Формально алгоритмы географической децентрализованной маршрутизации можно определить следующим образом:
Определение 1 (алгоритм географической децентрализованной маршрутизации)
Пусть G = (V, E) – евклидов граф. Задача алгоритма географической децентрализованной маршрутизации [math]\displaystyle{ \mathcal{A} \; }[/math] заключается в передаче сообщения от вершины-источника [math]\displaystyle{ s \in V \; }[/math] вершине-адресату [math]\displaystyle{ t \in V \; }[/math] при помощи отправки пакетов по ребрам графа G с соблюдением следующих условий:
• Всем вершинам [math]\displaystyle{ v \in V \; }[/math] известно их собственное географическое положение, а также географическое положение всех их соседей в графе G.
• Вершине-источнику s известно положение вершины-адресата t.
• Управляющая информация, которая может храниться в пакете, ограничена O(log n) бит – таким образом, он может содержать данные только о константном количестве вершин.
• Помимо временного сохранения пакетов перед отправкой, вершины не могут хранить какую бы то ни было информацию.
Географическая маршрутизация особенно интересна по той причине, что не требует использования каких-либо таблиц маршрутизации. Кроме того, как только положение вершины-адресата становится известно, все операции оказываются строго локальными, то есть каждая вершина должна отслеживать только своих непосредственных соседей. Эти два фактора – отсутствие необходимости в поддержке актуальных таблиц маршрутизации и независимость от происходящих на большом расстоянии изменений топологии – делают географическую маршрутизацию исключительно удобным инструментом для работы в децентрализованных сетях. Кроме того, географическую маршрутизацию можно в некотором смысле рассматривать как «урезанную» версию маршрутизации от источника, подходящую для динамических сетей: если при маршрутизации от источника весь маршрут сообщения от одной вершины к другой (hop-by-hop) задается вершиной-источником, то в случае географической маршрутизации источник просто прикрепляет к сообщению положение вершины-адресата. Поскольку положение вершины-адресата в общем случае меняется медленно в сравнении с частотой изменений топологии между источником и адресатом, рационально было бы отслеживать положение адресата вместо поддержки информации о топологии сети в актуальном состоянии; если вершина-адресат не перемещается слишком быстро, сообщение будет доставлено вне зависимости от возможных изменений топологии промежуточных вершин.
Стоимостные границы, приводимые в данной статье, достигаются на графах единичных дисков, которые определяются следующим образом.
Определение 2 (граф единичных дисков)
Пусть [math]\displaystyle{ V \subset \mathbb{R}^2 \; }[/math] – множество точек на двумерной плоскости. Граф, ребра которого соединяют все вершины, находящиеся на расстоянии не более 1, называется графом единичных дисков для V.
Графы единичных дисков часто применяются для моделирования беспроводных децентрализованных сетей.
Рассматриваемые алгоритмы маршрутизации работают на планарных графах, не имеющих пересекающихся ребер. Существуют строго локальные алгоритмы, которые строят подобные планарные графы из заданных графов единичных дисков. Ребра планарных графов разбивают евклидову плоскость на непрерывные области – так называемые грани. Алгоритмы, упоминающиеся в данной статье, основаны на использовании граней.
Основные результаты
Первым алгоритмом географической маршрутизации, всегда обеспечивавшим доставку сообщения адресату, был алгоритм маршрутизации по граням (Face Routing), предложенный в работе [14].
Теорема 1. Если между источником и адресатом есть связь, алгоритм Face Routing, выполняемый на произвольном планарном графе, всегда находит путь к вершине-адресату. Его выполнение требует не более O(n) шагов, где n – общее количество вершин в сети.
Однако существует алгоритм географической маршрутизации, стоимость которого ограничивается не только общим количеством вершин, но и отношением к кратчайшему пути между источником и адресатом: алгоритм GOAFR+ [15, 16, 18, 24] сочетает жадную маршрутизацию, при которой каждая промежуточная вершина перенаправляет сообщение своему соседу, расположенному ближе всего к вершине-адресату, с маршрутизацией по граням. При использовании совместно с техникой планаризации локально вычислимых графов Гэбриэла затраты алгоритма GOAFR+ ограничены следующим образом:
Теорема 2. Пусть c – стоимость оптимального пути из s в t в заданном графе единичных дисков. Стоимость достижения алгоритмом GOAFR+ вершины t составляет [math]\displaystyle{ O(c^2) \; }[/math], если между s и t имеется связь. Если s и t не связаны между собой, GOAFR+ сообщает об этом источнику.
С другой стороны, можно показать, что на определенных графах, представляющих собой наихудший случай, ни один алгоритм географической маршрутизации, работающий в соответствии с вышеприведенным определением, не работает асимптотически лучше, чем GOAFR+:
Теорема 3. Существуют графы, на которых любой детерминированный (рандомизированный) децентрализованный алгоритм маршрутизации имеет (ожидаемую) стоимость [math]\displaystyle{ \Omega(c^2) \; }[/math].
Из этого можно сделать следующий вывод:
Теорема 4. Затраты на достижение алгоритмом GOAFR+ вершины-адресата в графе единичных дисков являются асимптотически оптимальными.
Кроме того, было показано, что алгоритм GOAFR+ не только гарантированно имеет низкую стоимость в наихудшем случае, но и эффективно работает в сетях в среднем случае, когда вершины случайным образом распределены по плоскости [15, 24].
Применение
Благодаря своей строго локальной природе географическая маршрутизация особенно хорошо подходит для применения в потенциально высокодинамических беспроводных децентрализованных сетях. Однако применение в динамических сетях общего вида также может оказаться разумным.
Открытые вопросы
Некоторые задачи, имеющие отношение к географической маршрутизации, остаются нерешенными. Это относится в первую очередь к распространению по сети информации о положении вершины-получателя, а кроме того, к контексту мобильности вершин и динамики сети. Различные подходы к решению этих задач были предложены в работе [7] и главах 11 и 12 в [24]. В более общем плане, непочатый край работы остается в сфере более широкого применения географической маршрутизации в практических беспроводных децентрализованных сетях [12, 13]. И, наконец, остается открытым вопрос о том, можно ли адаптировать подход географической маршрутизации к сетям, вершины которых располагаются в трехмерном пространстве.
Экспериментальные результаты
Были проведены первые эксперименты с применением географической маршрутизации и, в частности, маршрутизации по граням в практических сетях [12, 13]. Были рассмотрены, документированы и в некоторой мере разрешены возникающие на практике проблемы, связанные с планаризацией графов.
См. также
Литература
1. Barriere, L., Fraigniaud, P., Narayanan, L.: Robust Position-Based Routing in Wireless Ad Hoc Networks with Unstable Transmission Ranges. In: Proc. of the 5th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), pp 19-27. ACM Press, New York (2001)
2. Bose, P., Brodnik, A., Carlsson, S., Demaine, E., Fleischer R., Lopez-Ortiz, A., Morin, P., Munro, J.: Online Routing in Convex Subdivisions. In: International Symposium on Algorithms and Computation (ISAAC). LNCS, vol. 1969, pp47-59. Springer, Berlin/New York (2000)
3. Bose, P., Morin, P.: Online Routing in Triangulations. In: Proc. 10th Int. Symposium on Algorithms and Computation (ISAAC). LNCS, vol. 1741, pp 113-122. Springer, Berlin (1999)
4. Bose, P.,Morin, P., Stojmenovic, I., Urrutia J.: Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. In: Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M), 1999, pp 48-55
5. Datta, S., Stojmenovic, I., Wu J.: Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks. In: Cluster Computing 5, pp 169-178. Kluwer Academic Publishers, Dordrecht (2002)
6. Finn G.: Routing and Addressing Problems in Large Metropolitan-scale Internetworks. Tech. Report ISI/RR-87-180, USC/ISI, March (1987)
7. Flury, R., Wattenhofer, R.: MLS: An Efficient Location Service for Mobile Ad Hoc Networks. In: Proceedings of the 7th ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), Florence, Italy, May 2006
8. Fonseca, R., Ratnasamy, S., Zhao, J., Ее, СТ., Culler, D., Shenker, S., Stoica, I.: Beacon Vector Routing: Scalable Point-to-Point Routing in Wireless Sensornets. In: 2nd Symposium on Networked Systems Design & Implementation (NSDI), Boston, Massachusetts, USA, May 2005
9. Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Geometric Spanner for Routing in Mobile Networks. In: Proc. 2nd ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), Long Beach, CA, USA, October 2001
10. Hou, T., Li, V.: Transmission Range Control in Multihop Packet Radio Networks. IEEE Tran. Commun. 34, 38-44 (1986)
11. Karp, B., Kung, H.: GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In: Proc. 6th Annual Int. Conf. on Mobile Computing and Networking (MobiCom), 2000, pp 243-254
12. Kim, Y.J., Govindan, R., Karp, B., Shenker, S.: Geographic Routing Made Practical. In: Proceedings of the Second USENIX/ACM Symposium on Networked System Design and Implementation (NSDI 2005), Boston, Massachusetts, USA, May 2005
13. Kim, Y.J., Govindan, R., Karp, B., Shenker, S.: On the Pitfalls of Geographic Face Routing. In: Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Cologne, Germany, September 2005
14. Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proc. 11th Canadian Conference on Computational Geometry, Vancouver, August 1999, pp 51-54
15. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric Routing: Of Theory and Practice. In: Proc. of the 22nd ACM Symposium on the Principles of Distributed Computing (PODC), 2003
16. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In: Proc. 6th Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Dial-M), pp 24-33. ACM Press, New York (2002)
17. Kuhn, F., Wattenhofer, R., Zollinger, A.: Ad-Hoc Networks Beyond Unit Disk Graphs. In: 1 st ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), San Diego, California, USA, September 2003
18. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-Case Optimal andAverage-Case Efficient Geometric Ad-Hoc Routing. In: Proc. 4th ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), 2003
19. Leong, B., Liskov, B., Morris, R.: Geographic Routing without Planarization. In: 3rd Symposium on Networked Systems Design & Implementation (NSDI), San Jose, California, USA, May 2006
20. Leong, B., Mitra, S., Liskov, B.: Path Vector Face Routing: Geographic Routing with Local Face Information. In: 13th IEEE International Conference on Network Protocols (ICNP), Boston, Massachusetts, USA, November 2005
21. Takagi, H., Kleinrock, L.: Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Trans. Commun. 32, 246-257 (1984)
22. Urrutia, J.: Routing with Guaranteed Delivery in Geometric and Wireless Networks. In: Stojmenovic, I. (ed.) Handbook of Wireless Networks and Mobile Computing, ch. 18 pp. 393-406. Wiley, Hoboken (2002)
23. Wattenhofer, M., Wattenhofer, R., Widmayer, P.: Geometric Routing without Geometry. In: 12th Colloquium on Structural Information and Communication Complexity (SIROCCO), Le Mont Saint-Michel, France, May 2005
24. Zollinger, A.: Networking Unleashed: Geographic Routing and Topology Control in Ad Hoc and Sensor Networks, Ph.D. thesis, ETH Zurich, Switzerland Diss. ETH 16025 (2005)
