AncomWiki

무선 네트워크의 이웃 발견을 위한 효율적 알고리즘

Properties1
description이 논문은 무선 어드 혹 네트워크 초기화 단계인 이웃 발견(Neighbor Discovery) 문제를 다룹니다. 단일 홉 네트워크에서 충돌 감지 여부에 따라 ALOHA 유사 알고리즘($\Theta(n \ln n)$)과 수신기 피드백 기반 알고리즘($\Theta(n)$)을 제안하며, 동기화나 이웃 수 사전 추정 없이 비동기적으로 실행 가능합니다. 다중 홉 환경에서는 최대 노드 차수($\Delta$)와 노드 수($n$)를 고려한…

13 min read

무선 네트워크의 이웃 발견을 위한 효율적 알고리즘

Source

  • Evernote/Papers/Efficient Algorithms for Neighbor Discovery in Wireless Networks.md

Summary

이 논문은 무선 어드 혹 네트워크 초기화 단계인 이웃 발견(Neighbor Discovery) 문제를 다룹니다. 단일 홉 네트워크에서 충돌 감지 여부에 따라 ALOHA 유사 알고리즘()과 수신기 피드백 기반 알고리즘()을 제안하며, 동기화나 이웃 수 사전 추정 없이 비동기적으로 실행 가능합니다. 다중 홉 환경에서는 최대 노드 차수()와 노드 수()를 고려한 상한 과 하한 을 증명하여, 제안된 알고리즘이 최적 대비 최대 배 느릴 뿐임을 보였습니다.

Key Points

  • 무선 어드 혹 네트워크의 이웃 발견 알고리즘 설계 및 분석
  • 충돌 감지 불가 시: 복잡도의 ALOHA 유사 알고리즘 제안
  • 충돌 감지 가능 시: 복잡도의 수신기 피드백 기반 최적 알고리즘 제안
  • 알고리즘 특징: 동기화 불필요, 이웃 수 사전 지식 불필요, 비동기 시작/종료 지원
  • 다중 홉 네트워크 분석: 상한 , 하한 증명
  • ALOHA 유사 알고리즘의 최적 대비 성능 격차는 최대 배로 제한됨

그래프 뷰

백링크