지리적 라우팅

Geographic routing

지리적 라우팅(Georouting[1] 또는 위치 기반 라우팅이라고도 함)은 지리적 위치 정보에 의존하는 라우팅 원리다. 주로 무선 네트워크에 제안되며, 소스가 네트워크 주소를 사용하는 대신 목적지의 지리적 위치에 메시지를 보낸다는 생각에 근거한다. 패킷 무선 네트워크 영역에서, 라우팅에 위치 정보를 사용하는 아이디어는 1980년대에[2] 상호 접속 네트워크에 대해 처음 제안되었다.[3] 지리적 라우팅은 각 노드가 자신의 위치를 결정할 수 있고 소스가 목적지의 위치를 알고 있어야 한다. 이 정보로 네트워크 토폴로지나 사전 경로 검색에 대한 지식 없이 메시지를 대상으로 라우팅할 수 있다.

접근

단일 경로, 다중 경로, 홍수 기반 전략 등 다양한 접근 방식이 있다(설문은 조사 참조[4]). 대부분의 단일 경로 전략은 욕심 많은 포워딩과 페이스 라우팅이라는 두 가지 기법에 의존한다. 욕심 많은 포워딩은 로컬 정보만 사용하여 각 단계에서 메시지를 목적지에 더 가까이 가져오려고 한다. 따라서 각 노드는 로컬 관점에서 가장 적합한 인접 네트워크로 메시지를 전달한다. 가장 적합한 이웃은 각 단계(자유)에서 목적지까지의 거리를 최소화하는 사람이 될 수 있다. 대안적으로, 다른 개념, 즉 소스-대상선에서의 예상 거리(MFR, NFP) 또는 이웃과 목적지 사이의 최소 각도(Compass Routing)를 고려할 수 있다. 이 전략들 모두가 루프가 없는 것은 아니다. 즉, 메시지는 특정 별자리의 노드들 사이에서 순환할 수 있다. 기본 욕심 전략과 MFR은 루프가 없는 반면 NFP와 나침반 라우팅은 그렇지 않은 것으로 알려졌다.[5]

욕심 많은 전달 변형: 소스 노드(S)는 메시지를 대상(D)에 추가로 전달하기 위해 릴레이 노드를 찾을 수 있는 선택사항이 다르다. A = 가장 가까운 Forwarding Progress(NFP), B = Radius(MFR), C = 컴퍼스 라우팅, E = 욕심쟁이
면 라우팅: 메시지는 통신 그래프의 면 내부를 따라 라우팅되며, 가장자리의 면 변화가 S-D 라인(빨간색)을 가로지른다. 최종 라우팅 경로는 파란색으로 표시된다.

욕심 많은 포워딩은 목적지에 더 가까운 이웃이 없는 막다른 골목으로 이어질 수 있다. 그런 다음 페이스 라우팅은 이러한 상황을 복구하고 탐욕스러운 포워딩이 재개될 수 있는 다른 노드로의 경로를 찾는 데 도움이 된다. 메시지가 목적지에 전달될 수 있도록 하기 위해서는 페이스 라우팅과 같은 복구 전략이 필요하다. 욕심 많은 포워딩과 페이스 라우팅의 조합은 GFG(Greedy-Face-Greedy)라는 이름으로 1999년에 처음 제안되었다.[6] 이른바 유닛 디스크 그래프 네트워크 모델에서 전달을 보장한다. 나중에 비단위 디스크 그래프에 대해 제안된 다양한 변형은 GFG의 원리에 기초한다.[1]

얼굴 라우팅은 일반적으로 평면 하위그래프에 의존한다. 그러나 분산형 평면화는 실제 무선 센서 네트워크에서는 어렵고 3D 환경으로 잘 확장되지 않는다. [8]

탐욕스러운 임베딩

원래 각 노드의 물리적 위치를 이용하는 라우팅 체계로 개발되었지만, 지리적 라우팅 알고리즘은 각 노드가 물리적 위치와 무관하게 가상 공간의 한 지점과 연결되는 네트워크에도 적용되어 왔다. 이러한 위치를 이용한 지리적 라우팅이 성공하도록 보장되는 네트워크 노드의 가상 위치 집합을 찾는 과정을 탐욕스러운 임베딩이라고 한다.[9]

참고 항목

참조

  1. ^ Jump up to: a b Ruehrup, Stefan (2009). Liu; Chu; Leung (eds.). Theory and Practice of Geographic Routing (PDF). Ad Hoc and Sensor Wireless Networks: Architectures, Algorithms and Protocols. Bentham Science.
  2. ^ Takagi, H.; Kleinrock, L. (March 1984). "Optimal transmission ranges for randomly distributed packet radio terminals". IEEE Transactions on Communications. 32 (3): 246–257. CiteSeerX 10.1.1.64.9747. doi:10.1109/TCOM.1984.1096061.
  3. ^ Finn, Gregory G. (March 1987). "Routing and Addressing Problems in Large Metropolitan-Scale Internetworks" (PDF). University of Southern California, ISI/RR-87-180. Cite 저널은 필요로 한다. journal= (도움말)
  4. ^ Stojmenovic, Ivan (2002). "Position based routing in ad hoc networks". IEEE Communications Magazine. 40 (7): 128–134. CiteSeerX 10.1.1.6.6012. doi:10.1109/MCOM.2002.1018018.
  5. ^ Stojmenovic, Ivan; Lin, Xu (2001). "Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks". IEEE Transactions on Parallel and Distributed Systems. 12 (10): 1023–1032. CiteSeerX 10.1.1.67.7527. doi:10.1109/71.963415.
  6. ^ Bose, P.; Morin, P.; Stojmenovic, I.; Urrutia, J. (1999). "Routing with guaranteed delivery in ad hoc wireless networks". Proc. of the 3rd international workshop on discrete algorithms and methods for mobile computing and communications (DIALM '99). pp. 48–55. doi:10.1145/313239.313282.
  7. ^ Djenouri, Djamel; Balasingham, Ilangko (2011). "Traffic-Differentiation-Based Modular QoS Localized Routing for Wireless Sensor Networks". IEEE Transactions on Mobile Computing. 10 (6): 797–809. doi:10.1109/TMC.2010.212. S2CID 11139687.
  8. ^ Kim, Y; Ramesh Govindan; Karp, Brad.; Scott Shenker (2005). "On the Pitfalls of Geographic Face Routing". Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing. pp. 34–43. doi:10.1145/1080810.1080818.
  9. ^ Rao, Ananth; Ratnasamy, Sylvia; Papadimitriou, Christos H.; Shenker, Scott; Stoica, Ion (2003), "Geographic routing without location information", Proc. 9th ACM Mobile Computing and Networking (MobiCom), pp. 96–108.