Long-delay 단일홉 무선 네트워크에서 Link Utilization 향상을 위한 All-to-All Broadcast 기법
All-to-All Broadcast Schemes for Improving Link Utilization in Long-delay Single-hop Wireless Networks
- 발행기관 아주대학교
- 지도교수 임재성
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 학과 및 전공 정보통신전문대학원 정보통신공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000009799
- 본문언어 한국어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
본 논문에서는 propagation delay가 transmission delay보다 상대적으로 매우 긴 long-delay 무선 네트워크에서 all-to-all broadcast할 경우 전체 all-to-all broadcast 시간을 단축하고 link utilization을 올리는 기법들을 제안한다. 제안하는 all-to-all broadcast 기법은 크게 순차형 기법과 병렬형 기법으로 나눌 수 있다. 순차형 기법은 패킷의 충돌을 피하기 위해 한 노드 의 broadcasting이 완전히 끝난 후 다른 노드가 broadcasting을 시작할 수 있는 기법이다. 이 기법에는 중앙 집중 환경에서 Traveling Salesman Problem을 적용하여 전체 all-to-all broadcast 시간을 최소로 하는 broadcasting 순서를 찾아내지만 시간복잡도가 매우 큰 기법과, 분산 환경에서 다음 차례에 broadcasting 할 노드를 자신과 가장 가까운 노드를 선택하여 최적의 해답은 아니지만 그에 근접하는 결과를 나타내고 시간복잡도가 낮은 기법이 있다. 병렬형 기법은 한 노드의 broadcasting이 완전히 끝나기전에 다른 노드가 broadcasting을 시작할 수 있는 기법이다. 다른 노드의 위치 정보를 알고 있다고 가정하면 한 노드가 보낸 패킷이 다른 노드에게 언제 도착하는지 알 수 있고 패킷 충돌은 수신단 입장에서만 나지 않으면되는 것이므로 이를 바탕으로 송신단이 언제 패킷을 전송할 것인지 적절하게 조절해 준다. 이를 위해 all-to-all broadcast 과정을 행렬로 변환하고 충돌없이 all-to-all broadcast 할 수 있도록 그 행렬을 푸는 알고리즘을 제안한다. 본 논문에서는 시뮬레이션을 통하여 제안하는 알고리즘들의 장단점을 비교 분석하였다.
more목차
제 1장. 서 론 ----------------------------------------------------- 1
제 2장. Long-delay 환경에서 Propagation Delay가 Link Utilization에 미치는 영향 -- 3
제 3장. 제안하는 All-to-All Broadcast 기법 ------------------------------ 6
제 1절. 순차형 All-to-All Broadcast 기법 --------------------------- 6
제 2절. 병렬형 All-to-All Broadcast 기법 --------------------------- 11
제 4장. 시뮬레이션 ------------------------------------------------ 24
제 1절. 시뮬레이션 환경 --------------------------------------- 24
제 2절. 시뮬레이션 결과 --------------------------------------- 28
제 5장. 결 론 ---------------------------------------------------- 35
참고문헌 -------------------------------------------------------- 37
Abstract -------------------------------------------------------- 39
목차
그림 2.1 거리에 따른 α의 변화 --------------------------- 4
그림 3.1 Traveling Salesman 예 -------------------------- 7
그림 3.2 다음 차례에 broadcasting 할 노드 선택 과정 --------- 9
그림 3.3 단위 시간의 예 -------------------------------- 13
그림 3.4 노드 분포의 예 -------------------------------- 15
그림 3.5 All-to-all broadcast를 행렬로 변환 ----------------- 15
그림 3.6 행렬 푸는 알고리즘 순서도 ----------------------- 19
그림 3.7 행렬 푸는 알고리즘 예시 3 ----------------------- 22
그림 3.8 행렬 푸는 알고리즘 예시 4 ----------------------- 23
그림 4.1 시뮬레이션에 사용된 TSP 알고리즘 ----------------- 26
그림 4.2 노드 수 증가에 따른 전체 all-to-all broadcast 시간 ---- 27
그림 4.3 노드 수 증가에 따른 계산 시간 -------------------- 29
그림 4.4 전송 범위 증가에 따른 전체 all-to-all broadcast 시간 --- 30
그림 4.5 노드 수 증가에 따른 Link Utilization ----------------- 32
그림 4.6 전송 범위 증가에 따른 Link Utilization --------------- 34
목차
표 3.1 행렬 푸는 알고리즘 예시 1 ------------- 20
표 3.2 행렬 푸는 알고리즘 예시 2 ------------- 21
표 4.1 시뮬레이션 파라미터 ------------------ 25
