어소시에이티비티 베이스 라우팅

Associativity-based routing

어소시에이티비티 베이스[1][2][3][4] 라우팅(통칭 ABR)은 무선 애드혹네트워크용으로 개발된 모바일라우팅 프로토콜입니다.Mobile Ad Hoc Network(MANET; 모바일애드혹 네트워크) 및 무선 메쉬 네트워크라고도 불립니다.ABR은 1993년 발명돼 1996년 미국 특허를 출원해 1999년 특허를 부여했다.ABR은 케임브리지 대학에서 박사과정을 밟고 있을 때 Chai Keong Toh에 의해 발명되었다.

루트 디스커버리 단계

ABR에는 3가지 단계가 있습니다.첫 번째 단계는 루트 디스커버리 단계입니다.사용자가 데이터 전송을 시작하면 프로토콜은 요청을 가로채 무선 인터페이스를 통해 검색 패킷을 브로드캐스트합니다.검색 패킷이 노드간에 전파되면, 노드 ID 및 안정성 정보가 패킷에 부가됩니다.패킷이 최종적으로 행선지 노드에 도달하면, 송신원으로부터 행선지까지의 패스를 기술하는 모든 정보를 수신하게 됩니다.이 경우, 행선지는 최적의 루트를 선택해(송신원으로부터 행선지에 복수의 패스가 존재할 가능성이 있기 때문에), 선택한 패스를 개입시켜 송신원노드로 REPLY 를 반송합니다.

패킷이 수신처로부터 송신원으로 역방향으로 전송되면, 각 중간 노드는 라우팅 테이블을 갱신해, 업스트림노드로부터 데이터를 수신했을 때에 라우팅 방법을 인식하게 되는 것에 주의해 주세요.송신원노드가 REPLY를 수신하면, 루트는 정상적으로 검출되어 확립됩니다.이 프로세스는 실시간으로 수행되며 몇 밀리초밖에 걸리지 않습니다.

루트 재구성 단계

ABR은 장기간의 루트 또는 어소시에이티비티가 안정된 루트를 확립하기 때문에 확립된 대부분의 루트에서 링크 파손은 거의 발생하지 않습니다.다만, 1개 이상의 링크가 파손되었을 경우, 그 ABR는 즉시 RRC(루트 재구축 단계)를 호출합니다.RRC는 기본적으로 업스트림노드(링크브레이크를 감지하는 것)에 로컬루트 복구를 실시함으로써 절단된 링크를 복구합니다.로컬화된 루트 복구는 로컬화된 브로드캐스트쿼리를 실행하여 행선지에 대한 대체 롱라이프 부분 루트를 검색합니다.

ABR 루트 유지보수는 다음과 같이 구성됩니다.

  • (a) 부분 루트 디스커버리
  • (b) 무효 경로 삭제,
  • (c) 유효한 경로 갱신
  • (d) 새로운 루트 디스커버리(경우).

루트 삭제 단계

검출된 루트가 불필요해지면 루트 내의 모든 중간 노드가 라우팅 테이블엔트리를 갱신하고 이 삭제된 루트와 관련된 릴레이 데이터 패킷을 정지하도록 소스 노드에 의해 RD(Route Delete) 패킷이 시작됩니다.

RD를 사용하여 루트를 삭제하는 것 외에 ABR은 일정 기간 동안 루트와 관련된 트래픽액티비티가 없을 때 루트엔트리가 타임아웃 후 만료되거나 비활성화되는 소프트스테이트 어프로치를 실장할 수도 있습니다.

실용성

1998년에 ABR은 WaveLAN 802.11a PCMCIA 무선 어댑터를 탑재한 다양한 브랜드 노트북(IBM Thinkpad, COMPAQ, 도시바 등)에 Linux 커널에 성공적으로[5][6][7][8] 구현되었습니다.600미터 이상의 거리에 걸친 6노드 와이드 무선 애드혹네트워크가 실현되어 1999년 모바일 컴퓨팅 매거진에 게재되었습니다.네트워크에서 다양한 테스트가 수행되었습니다.

  1. 3 홉 루트를 통해 송신원으로부터 수신처로 최대 500 MBytes의 데이터 전송.
  2. 링크 절단 및 자동 링크 복구가 기능하는 것으로 확인됨
  3. 자동 루트 검출
  4. 루트 삭제
  5. 애드혹 모드의 웹 서버– 소스가 클라이언트, 수신처가 웹 서버
  6. 멀티미디어 정보(오디오[9] 및 비디오) 전송
  7. 애드혹 경유 TELNET
  8. 애드혹 경유 FTP
  9. HTTP over 애드혹

또한 다음 사항에 대한 네트워크 성능 측정이 수행되었습니다.

  1. 엔드 투 엔드 지연
  2. TCP 스루풋
  3. 패킷 손실률
  4. 루트 디스커버리 지연
  5. 루트 복구 지연
  6. 패킷 크기가 스루풋에 미치는 영향
  7. 비콘 간격이 스루풋과 배터리 잔량에 미치는 영향

향상된 버전의 프로토콜은 2002년 방위 계약업체인 TRW Inc.에 의해 현장에서[10] 구현되었다.프로토콜에 추가된 기능에는 (a) 네트워크 계층 QoS 추가 및 (b) 경로 우선 기능이 포함됩니다.

특허 및 업무 확장

ABR은 미국 특허 5987011을[11] 받았으며, 양수인은 영국 캠브리지의 King's College입니다.

다음과 같은 몇몇 다른 모바일 애드혹라우팅 프로토콜은 ABR의 안정성 개념을 포함하거나 ABR 프로토콜의 확장을 수행했습니다.

  • 신호 안정성 기반 Adaptive Routing Protocol(SSA)[12]
  • Enhanced Associativity Based Routing Protocol(EABR)[citation needed]
  • Associativity-Based Routing(AEABR;[13] 어소시에이티비티 베이스 라우팅)의 대체 확장
  • OAB(Optimized Associativity Threshold Routing)TR)[14]
  • Associativity-Based Clustering Protocol(ABCP),[15]
  • 퍼지 베이스 신뢰 어소시에이션 베이스 라우팅(퍼지 ABR)
  • Associativity Tick Averaged Associativity Based Routing(ATA-AR;[16] 어소시에이티비티 평균 어소시에이션 베이스 라우팅),
  • 자기 적응형 Q-러닝 기반 신뢰 ABR(QTABR)[17]
  • ABR(QoSE-ABR)[18]로의 Quality of Service 확장
  • 어소시에이션 베이스 멀티캐스트라우팅(ABM)[19]
  • Multipath Associativity Based Routing(MABR)[20]
  • 무선 센서 네트워크의 어소시에이티비티
  • 관련 차량용 애드혹 네트워크(VANET)

레퍼런스

  1. ^ Toh, Chai-Keong (March 1997). "Associativity-based routing for ad hoc mobile networks". Wireless Personal Communications. 4 (2): 103–139. doi:10.1023/A:1008812928561.
  2. ^ Toh, Chai-Keong (March 1996). A novel distributed routing protocol to support ad-hoc mobile computing. Proceedings of the IEEE Fifteenth Annual International Phoenix Conference on Computers and Communications.
  3. ^ Toh, Chai-Keong (December 2001). Ad Hoc Mobile Wireless Networks. Prentice Hall. ISBN 978-0-13-007817-9.
  4. ^ Long-lived ad-hoc routing based on the concept of Associativity, IETF Draft 1999
  5. ^ "Mobile Computing Magazine Interview Article - First practical ad hoc wireless network implementation outdoors, 1999 (PDF)
  6. ^ Toh, C.-K.; Lin, G.; Delwar, M. (2000), "Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks", Implementation and evaluation of an adaptive routing protocol for infrastructureless mobile networks, Proceedings of 9th International Conference on Computer Communications and Networks, 2000., pp. 20–27, doi:10.1109/ICCCN.2000.885465, ISBN 978-0-7803-6494-3
  7. ^ Evaluating the communication performance of an ad hoc wireless network, IEEE Transactions on Wireless Communications, 2000
  8. ^ Toh, C.-K.; Chen, Richard; Delwar, Minar; Allen, Donald (2000), "Experimenting with an Ad Hoc wireless network, ACM SIGMETRICS Performance Evaluation Review, Volume 28 Issue 3, Dec. 2000", ACM SIGMETRICS Performance Evaluation Review, 28 (3): 21–29, doi:10.1145/377616.377622
  9. ^ Transporting Audio over Wireless Ad Hoc Networks, Proc. International Conference on Personal, Indoor And Mobile Radio Communications, Pimrc, 2003, v. 1, p. 772-777 (PDF)
  10. ^ "Next-Generation Tactical Ad Hoc Mobile Wireless Networks". TRW Technology Review Journal. 2004.
  11. ^ A Routing Method for Ad Hoc Mobile Networks, US Patent 5987011, granted 1996, filed 1994.
  12. ^ Dube, Rohit; Rais, Cynthia D.; Wang, Kuang-Yeh; Tripathi, Satish K. (1996), Signal stability based adaptive routing (SSA) for ad-hoc mobile networks
  13. ^ Alternative Enhancement of Associativity-Based Routing, 2009, doi:10.1007/978-3-642-11817-3_7, S2CID 8920485
  14. ^ Optimized Associativity Threshold Routing, CiteSeerX 10.1.1.79.8653
  15. ^ Associativity-Based Clustering Protocol for Mobile Ad Hoc Networks (PDF)
  16. ^ Associativity Tick Averaged Associativity-Based Routing for Realtime Mobile Networks (PDF)
  17. ^ Vijaya Kumar, A.; Jeyapal, A. (2014), "Self-Adaptive Trust Based ABR Protocol for MANETs Using Q-Learning", The Scientific World Journal, 2014: 452362, doi:10.1155/2014/452362, PMC 4164804, PMID 25254243
  18. ^ Adding Quality of Service Extensions to the Associativity Based Routing Protocol for Mobile Ad Hoc Networks, Apscc '08, 2008, pp. 631–637, doi:10.1109/APSCC.2008.234, ISBN 9780769534732
  19. ^ ABAM: On-Demand Associativity-Based Multicast
  20. ^ Carthy, P.M.; Grigoras, D. (2005), "Multipath Associativity Based Routing", Second Annual Conference on Wireless On-demand Network Systems and Services, pp. 60–69, doi:10.1109/WONS.2005.24, ISBN 0769522904
  21. ^ Eltarras, Ramy; Eltoweissy, Mohamed (2011), "Associative routing for wireless sensor networks", Computer Communications, 34 (18): 2162–2173, doi:10.1016/j.comcom.2011.01.010
  22. ^ Yu, Hyun; Ahn, Sanghyun; Yoo, Joon (2013), "A Stable Routing Protocol for Vehicles in Urban Environments", International Journal of Distributed Sensor Networks, 9 (11): 759261, doi:10.1155/2013/759261