[논문]군사용 위성통신망을 위한 동적 WDRR기반의 스케줄링 알고리즘

이기엽; 송경섭; 김동성

doi:10.5573/ieek.2013.50.1.196

군사용 위성통신망을 위한 동적 WDRR기반의 스케줄링 알고리즘
Scheduling Algorithm for Military Satellite Networks using Dynamic WDRR(Weighted Deficit Round Robin) 원문보기

Journal of the Institute of Electronics Engineers of Korea = 전자공학회논문지, v.50 no.1, 2013년, pp.196 - 204

이기엽 (금오공과대학교 전자공학과) , 송경섭 (금오공과대학교 전자공학과) , 김동성 (금오공과대학교 전자공학과)

초록
AI-Helper

본 논문에서는 WDRR(Weighted Deficit Round Robin) 기법을 토대로 군사 위성통신망의 QoS를 향상시키기 위한 스케줄링 기법을 제안한다. 제안된 동적 WDRR기법은 통신망 대기열의 패킷의 크기가 커지는 경우 지수이동평균을 이용, 적절한 추가 퀀텀을 부여하여 대기열의 패킷을 효율적으로 전송하는 방법이다. 제안된 알고리즘의 효용성을 증명하기 위해 OPNET Modeler를 이용하여 모의실험환경을 구축하고, 제안된 알고리즘의 신뢰성 및 실시간성을 분석하였다. 이를 통하여, 기존 군사용 위성통신망 스케줄링 기법에 사용되는 WRR(Weighted Round Robin), DRR(Deficit Round Robin), WDRR(Weighted Deficit Round Robin) 등을 비교 분석한 모의실험 결과를 통해 통신망 지연시간과 패킷 손실율에 관한 성능 향상을 보였다.

Abstract ▼ AI-Helper

In this paper, a scheduling algorithm is proposed for military satellite networks to improve QoS(Quality of Service) based on WDRR(Weighted Deficit Round Robin) method. When the packet size that has been queued to be larger, the proposed scheme DWDRR(Dynamic WDRR) method give appropriate additional quantum using EWMA(Exponentially Weighted Moving Average). To demonstrate an usefulness of proposed algorithm using OPNET modeler that built the simulation environment, reliability and real-time availability of the proposed algorithm is analyzed. The simulation results show an availability of proposed scheme in terms of reduce queuing delay and packet drop rate compared and analyzed the existing algorithms WRR(Weighted Round Robin), DRR(Deficit Round Robin) and WDRR with DWDRR.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 라운드 로빈 알고리즘을 토대로 군 위성망의 다운링크를 위한 위성 지상기지국과 하위노드에 적합한 DWDRR 스케줄링 기법을 제안하였다. 기존의 위성에 적용 되던 DRR, WDRR 등 기존 라운드 로빈기반의 군사 위성통신망 스케줄링 알고리즘은 다양한 데이터 타입을 지원하기 힘들고 노드 부하가 커지면 대기열에서 대기하는 패킷이 증가했다.
그러나 WDRR 알고리즘은 고정된 퀀텀으로 인해 유동적인 환경에 적용하기에는 문제점이 있다. 본 논문에서는 이를 개선하기 위해 트래픽 사용량에 따라 동적으로 퀀텀을 제공하는 DWDRR(Dynamic WDRR)을 제안한다. 제안하는 스케줄링 알고리즘은 대기열(queue)에 대기 중인 패킷의 크기가 커지는 경우 지수이동평균을 이용하여 적절한 추가 퀀텀을 부여하는 방법이다.
본 논문에서는 제안된 기법을 모의실험을 통하여 패킷 손실율과 대기열 지연시간에 관하여 성능 향상을 보였다. 향후 과제로 저부하 환경과 과부하 환경에서의 성능분석과 앞서 언급한 지상 링크간의 우선순위를 고려한 모의실험이 있다.
WDRR은 WRR과 DRR 알고리즘을 혼합한 방식으로 DRR과 같이 퀀텀을 기초로 하는 방식과 가중치를 부여하여 대역폭을 할당하는 WRR방식을 모두 사용하고 있다. 이 알고리즘은 기존 DRR과 WRR이 가지고 있던 단점들을 보완하여 스케줄링 공평성을 유지할 수 있는 알고리즘이다.

가설 설정

그러나 실제 전장 환경에서는 북한을 대비하는 만큼 북쪽의 지상 위성링크가 더 큰 우선순위를 가질 수 있다. 대한민국의 면적(10만 ㎢)과 배타적 경제수역을 고려한 직경 12,000 ㎞ 범위를 군 전력 전술 지휘 통제 망으로 활용하기 위해 위성링크를 47개로 설정하고 하위노드는 약 4000개로 가정하였다. 하나의 지상 위성링크에는 탱크, 무인항공기, 잠수함, 연대와 대대의 이동용 단말기 등 한 개 사단 규모의 약 80개 하위노드들을 설정하였으며 통신망은 메시(mesh)형으로 구성하였다.
지상 위성링크간의 우선순위는 없다고 가정한다. 그러나 실제 전장 환경에서는 북한을 대비하는 만큼 북쪽의 지상 위성링크가 더 큰 우선순위를 가질 수 있다.

제안 방법

이를 위해 EWMA(Exponentially Weighted Moving Average)를 사용하였다. EWMA를 바탕으로 반 고정되어 있는 평균 버퍼율(BAV)과 고정퀀텀(QA)을 연산하여 과거 값에 적용하고, 항상 유동적인 현재 버퍼율(BN)과 잔여퀀텀(QN)을 계산하여 현재 값에 적용한다.
국방정보화 발전계획에 반영된 70여개의 주요 정보 체계사업을 대상으로 하는 수학적 모델기법의 통신수요예측 방법을 적용하여 국방정보통신망의 기반 구조에 필요한 군 정보유통량 분석 및 통신수요를 예측하였다. 예측방법은 제대별 평균 메시지 크기를 가정하고 도착시간 분포와 서비스 조건, 자원수를 사용하여 트래픽을 산출하는 대기식 완전선군 모델을 적용하였다^[9].
모의실험을 위해 각 위성 지구기지국에서 임의의 길이를 가진 데이터의 종류를 4가지로 분류하여 평균 요구도에 따라 랜덤하게 전송한다. 가장 큰 우선순위를 가지는 우선순위 1은 4522∼6240 Kbps의 패킷전송을 요구하고 대표적으로 명령/보고, VoIP, 영상, 무인항공기 등의 정보를 가진다.
알고리즘의 성능 비교는 평균 대기열 지연시간과 각 라운드에서 각 대기열의 패킷들이 손실되는 비율을 비교한다. 본 논문에서는 대기열 지연시간의 성능 비교를 위해 데이터양을 1.
국방정보화 발전계획에 반영된 70여개의 주요 정보 체계사업을 대상으로 하는 수학적 모델기법의 통신수요예측 방법을 적용하여 국방정보통신망의 기반 구조에 필요한 군 정보유통량 분석 및 통신수요를 예측하였다. 예측방법은 제대별 평균 메시지 크기를 가정하고 도착시간 분포와 서비스 조건, 자원수를 사용하여 트래픽을 산출하는 대기식 완전선군 모델을 적용하였다^[9].
이런 점을 보완하기 위해 본 논문에서는 DWDRR을 적용하여 순간적으로 데이터 패킷의 크기가 커지는 경우 추가적인 퀀텀에 의해 6 싸이클보다 빠른 시간 내에 데이터를 전송한다. 이를 통하여 대기열 내부의 패킷 정체 현상을 유연하게 처리할 수 있고, 패킷 우선순위가 변하여도 각 노드별 가중치 및 차등에 따라 공평하고 효율적으로 데이터 전송을 처리할 수 있다.
본 논문에서는 이를 개선하기 위해 트래픽 사용량에 따라 동적으로 퀀텀을 제공하는 DWDRR(Dynamic WDRR)을 제안한다. 제안하는 스케줄링 알고리즘은 대기열(queue)에 대기 중인 패킷의 크기가 커지는 경우 지수이동평균을 이용하여 적절한 추가 퀀텀을 부여하는 방법이다. 이를 통해 군사용 위성통신망의 QoS를 향상시켰다.
하나의 지상 위성링크에는 탱크, 무인항공기, 잠수함, 연대와 대대의 이동용 단말기 등 한 개 사단 규모의 약 80개 하위노드들을 설정하였으며 통신망은 메시(mesh)형으로 구성하였다. 지상 위성링크와 위성간의 통신은 50개의 타임 슬롯으로 나누어진 TDMA(Time Division Multiple Access)방식으로 구성하였다.
대한민국의 면적(10만 ㎢)과 배타적 경제수역을 고려한 직경 12,000 ㎞ 범위를 군 전력 전술 지휘 통제 망으로 활용하기 위해 위성링크를 47개로 설정하고 하위노드는 약 4000개로 가정하였다. 하나의 지상 위성링크에는 탱크, 무인항공기, 잠수함, 연대와 대대의 이동용 단말기 등 한 개 사단 규모의 약 80개 하위노드들을 설정하였으며 통신망은 메시(mesh)형으로 구성하였다. 지상 위성링크와 위성간의 통신은 50개의 타임 슬롯으로 나누어진 TDMA(Time Division Multiple Access)방식으로 구성하였다.

데이터처리

제안된 DWDRR 알고리즘의 성능 분석을 위해 기존 군사용 위성통신망 라운드 로빈 스케줄링 기법에서 파생된 DRR, WDRR을 비교분석 하였다. DRR과 WDRR은 모두 데이터 길이가 가변적이고 트래픽이 가중된 시스템 환경에 직접 적용하기에는 한계가 있었지만, DWDRR은 2.

이론/모형

본 논문에서의 주요 핵심 사항중 하나는 순간적으로 패킷의 크기가 커지는 경우 추가퀀텀을 어떤 방법으로 부여하느냐이다. 이를 위해 EWMA(Exponentially Weighted Moving Average)를 사용하였다. EWMA를 바탕으로 반 고정되어 있는 평균 버퍼율(BAV)과 고정퀀텀(QA)을 연산하여 과거 값에 적용하고, 항상 유동적인 현재 버퍼율(BN)과 잔여퀀텀(QN)을 계산하여 현재 값에 적용한다.

성능/효과

제안된 DWDRR 알고리즘의 성능 분석을 위해 기존 군사용 위성통신망 라운드 로빈 스케줄링 기법에서 파생된 DRR, WDRR을 비교분석 하였다. DRR과 WDRR은 모두 데이터 길이가 가변적이고 트래픽이 가중된 시스템 환경에 직접 적용하기에는 한계가 있었지만, DWDRR은 2.55 Gbps이후부터 성능향상을 보였다.
이를 통해 군사용 위성통신망의 QoS를 향상시켰다. OPNET Modeler를 이용하여 제안하는 알고리즘과 기존 알고리즘을 상호 비교 분석함으로서 제안하는 알고리즘이 가능함을 보이고, 패킷 손실률과 대기 지연시간 감소에 관한 성능 향상을 보였다.
35 Gbps 구간에서는 세 가지 알고리즘이 비슷한 성능을 보였다. 그러나 2.35 Gbps 이후로 제안된 알고리즘이 기존 알고리즘보다 성능이 향상 되었다. 이 부분에서는 기존의 DRR이 WDRR보다 성능이 우수함을 보였다.
제안된 알고리즘인 DWDRR은 기존의 고정위성에 적용되던 DRR과 WDRR보다 과부하 상황에서 패킷 손실율이 낮고 우선순위가 낮은 패킷도 상대적으로 대기열 지연시간이 적다. 그러나 미세한 차이지만 우선순위 1, 2, 3의 지연시간이 증가하고 데이터 전송율이 1.4 Gbps 미만일 때 제안하는 알고리즘의 지연시간이 기존 알고리즘 보다 상대적으로 높은 모습을 보인다. 이는 데이터양이 급격히 증가하는 상황을 고려한 시뮬레이션이기때문에 저부하 상황에서 딜레이 시간이 높게 나오는 것이라 판단된다.
그림 15는 데이터율을 서서히 증가시켰을 때 우선순위 4에서의 패킷 손실율을 비교한 값이다. 다른 우선순위의 패킷 손실율에 비해 제안된 알고리즘의 성능이 향상되지 않았다. 이 실험 결과에서는 세 가지 방식 모두 특정구간에서 두드러진 성능향상이 나타나지 않기 때문에 비교할 수 없다.
즉, 사용자가 임의로 퀀텀을 부여할 수 있기 때문에 DRR과 WDRR 또는 DWDRR의 비교는 퀀텀을 어떻게 부과하느냐에 따라 그 성능이 달라질 수 있다. 따라서 WDRR의 퀀텀과 DWDRR의 고정퀀텀을 똑같이 부과함으로서 각각의 스케줄링 알고리즘간의 성능을 정확히 비교할 수 있다.
실제적으로 대기열 지연시간이 패킷 드랍율에 영향을 미치지만 이 두 요소가 항상 비례하는 것은 아니다. 모의실험 결과와 같이 DRR과 WDRR의 대기열 지연시간과 패킷 손실율을 비교하여 보면 지연시간이 높더라도 패킷 손실율이 낮거나 지연시간이 낮아도 패킷 손실율이 높은 구간을 볼 수 있다.
알고리즘의 성능 비교는 평균 대기열 지연시간과 각 라운드에서 각 대기열의 패킷들이 손실되는 비율을 비교한다. 본 논문에서는 대기열 지연시간의 성능 비교를 위해 데이터양을 1.5 Gbps에서 3.9 Gbps로 늘였다. 평균 패킷의 처리 시간이 짧을수록 해당 알고리즘이 같은 양의 패킷을 더 짧은 시간에 서비스한다는 것을 의미하며 각 대기열의 패킷 손실률은 과부하 상황에서 패킷 오버플로우(overflow)가 발생되지 않고, 얼마나 스케줄링이 잘 이루어지는가를 나타낸다^[10].
그림 12와 13은 각 알고리즘들의 우선순위 1, 2에서 패킷 손실율을 비교한 내용이다. 우선순위 1, 2에서 데이터율을 서서히 증가시켰을 때 DRR과 WDRR은 2.4 Gbps에서 패킷 손실율이 상승하지만 제안하는 알고리즘은 2.55 Gbps에서 반응을 보이고 그 이후로도 평균 패킷 손실율이 낮음을 나타낸다.
제안된 알고리즘인 DWDRR은 기존의 고정위성에 적용되던 DRR과 WDRR보다 과부하 상황에서 패킷 손실율이 낮고 우선순위가 낮은 패킷도 상대적으로 대기열 지연시간이 적다. 그러나 미세한 차이지만 우선순위 1, 2, 3의 지연시간이 증가하고 데이터 전송율이 1.
이 실험 결과에서는 세 가지 방식 모두 특정구간에서 두드러진 성능향상이 나타나지 않기 때문에 비교할 수 없다. 평균 대기열 지연시간의 실험결과와 비교하여 보면, 트레이드오프에 의해 대기열 지연시간의 향상이 이루어져도 패킷 손실율에는 크게 영향을 미치지 않는다는 것을 알 수 있다.

후속연구

본 논문에서는 제안된 기법을 모의실험을 통하여 패킷 손실율과 대기열 지연시간에 관하여 성능 향상을 보였다. 향후 과제로 저부하 환경과 과부하 환경에서의 성능분석과 앞서 언급한 지상 링크간의 우선순위를 고려한 모의실험이 있다. 하위노드들의 핸드오버에 의한 우선순위 변화를 고려한 모의실험과 위성을 복수로 설정하여 위성간의 링크도 고려하는 시스템의 모의실험도 필요하다.

질의응답

핵심어	질문	논문에서 추출한 답변
	WDRR방식이란?	그 중 대표적인 알고리즘이 WDRR(Weighted Deficit Round Robin)이다. WDRR은 기존의 WRR방식과 DRR방식의 혼합형으로 WRR의 가중치 메커니즘과 DRR의 퀀텀 메커니즘을 모두 사용하는 방식이다. 다시 말해, WRR과 DRR의 단점을 보완한 기술이다.
	라운드로빈 방식의 장점 및 단점은?	군사 위성통신망에서 라운드로빈 방식은 계산 복잡도가 낮고 구현이 쉬운 스케줄링 기법이지만 트래픽이 집중되어 과부하 상황이 될 때에는 실시간성을 만족하지 못하게 된다. 실시간 전송을 할 수 없더라도 우선순위에 따라 가능한 빠르게 전송할 수 있는 알고리즘이 필요하다[1].
	WDRR은 무엇의 단점을 보완하며 무엇이 가능한 기술인가?	WDRR은 기존의 WRR방식과 DRR방식의 혼합형으로 WRR의 가중치 메커니즘과 DRR의 퀀텀 메커니즘을 모두 사용하는 방식이다. 다시 말해, WRR과 DRR의 단점을 보완한 기술이다. 또한 이 스케줄링 기법은 다양한 형식의 데이터 지원이 가능하다[4∼6]. 그러나 WDRR 알고리즘은 고정된 퀀텀으로 인해 유동적인 환경에 적용하기에는 문제점이 있다.

참고문헌 (10)

Blackmore, P.A, "Information Scheduling in a Military Satellite Broadcast System", IEEE International conference on ICON '99, pp 313-323, 2002
Paul D. Mitchell, David Grace, "Analytical Model of Round-Robin Scheduling for a Geostationary Satellite System" IEEE Communications Letters, Vol 7, No.11, pp. 546-548, Nov 2003

상세보기
William M. Shvodian, "Multiple Priority Distributed Round Robin MAC Protocol for Satellite ATM", IEEE Military Communications Conference, Vol. 1, pp 258-262, 1998
Idris A. Rai and Murat Alanyali, "Uniform Weighted Round Robin Scheduling Algorithms for Input Queued Switches", IEEE International Conference on ICC, Vol. 7, pp. 2028-2032, 2001
Soren Sonntag and Helmut Reinig, "An Efficient Weighted-Round-Robin Algorithm for Multiprocessor Architectures", IEEE 41st Annual Simulation Symposium, pp. 193-199, 2008
"Efficient QoS-based Uplink Scheduling Scheme in IEEE 802.16e Mobile Stations", IEEE Transactions on Wireless Communications and Networking Conference, pp. 1-6, 2009
Zeng yuan, Gong wen-bin, Liu hui-jie, liang xu-wen, "LEO Satellite Scheduler Model and Simulation" 4th international conference on Wireless Communications, Networking and Mobile Computing, pp. 1-5, 2008
김형민, "인공위성을 이용한 군 통신망 구축 요구 사항에 관한 연구", 동의대학교 산업기술대학원, 2004
최영민, 임영갑, 김영호, "전술통신 시스템의 효율적인 설계를 위한 정보교환 요구량 분석", Telecommunication review, 제 20권 2호, 2010년 4월
고인아, "WDRR 스케줄링 방식의 패킷지연시간에 한 확률적 분석", 한국과학기술원, 2005

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증