[논문 리뷰] Scheduling 기법이란?

Insight : Scheduling이 IoTN에서 어떻게 사용되고 있는가? 무슨 Scheduling이 있는가? [활용]

 

Title: An Efficient Data Packet Scheduling Scheme for Internet of Things Networks [2020]

 

L. Farhan, L. Alzubaidi, M. Abdulsalam, A. J. Abboud, M. Hammoudeh and R. Kharel, "An efficient data packet scheduling scheme for Internet of Things networks," 2018 1st International Scientific Conference of Engineering Sciences - 3rd Scientific Conference of Engineering Science (ISCES), Diyala, Iraq, 2018, pp. 1-6, doi: 10.1109/ISCES.2018.8340518.

---

Abstract

사물 인터넷(IoT) 디바이스의 에너지 공급이 부족하기 때문에 전력 사용량을 최적화하도록 네트워크의 아키텍처와 운영을 설계해야 합니다. 스케줄링 알고리즘은 WSN (Wireless Sensor Network) 및 IoT 네트워크의 필수적인 부분입니다. 이러한 알고리즘을 통해 대기열을 분류하고 실행할 프로세스를 결정할 수 있습니다.
 따라서 본 연구에서는 클러스터 헤드 노드에서의 스케줄링 메시지를 제안했습니다. 롱홉(LH) 우선 알고리즘은 먼 거리에서 들어오는 데이터의 우선순위를 높게 책정하고, 더 많은 수의 디바이스에 접속하여 우선적으로 라우팅하는 새로운 통합 스케줄링 기법입니다. 성능 실험을 통해 제안한 방법을 기존의 널리 사용되는 스케줄링 알고리즘인 선착순(FCFS) 및 근거리 작업 다음(NJN) 알고리즘과 비교했습니다. 결과와 시뮬레이션을 통해 제안된 연구가 전력 소비를 줄이고 처리량을 극대화하는 것으로 나타났습니다. 전력 소비는 최대 56%, 네트워크 처리량은 62.50%까지 절약할 수 있습니다. 또한 패킷 지연과 손실, 전송 거리를 최소화하여 네트워크의 수명을 연장할 수 있습니다.

 

지표 : 전력량, 처리량

 

Introduction

무선 센서 네트워크(Wireless Sensor Network, WSN)는 짧은 거리에서 무선으로 통신하는 저전력, 저비용의 다기능 센서 노드로 구성됩니다. 모트 노드에는 산불 예방, 기상 상태, 홍수 감지 등과 같은 물리적 현상이나 환경적 조건을 감지하고 제어하기 위한 센서가 장착되어 있습니다. 센서 네트워크는 수백 개에서 최대 수천 개의 연결된 센서로 구성됩니다[1]. 따라서 WSN의 급속한 기술 발전은 사물 인터넷(IoT)의 핵심 기술이 되고 있습니다. IoT는 글로벌 네트워크 인프라를 통해 네트워크로 연결되고 서로 통신하는 수많은 스마트 및 자체 구성 장치가 서로 연결되는 다분야 패러다임입니다. 이 기술의 주요 목표는 리소스가 제한된 네트워크에서 효과적인 통신을 통해 스마트 디바이스를 연결하는 것입니다[2, 3]. 이러한 각 디바이스와 시스템은 기존 프로토콜 스택, 아키텍처 및 데이터 형식을 기반으로 작동합니다. 대부분의 IoT 디바이스는 저용량, 프로세서, 메모리를 사용하며 배터리 또는 에너지 하베스팅 수단으로 구동되는 저전력 엔드 노드 객체입니다. 즉, HTTP나 TCP 등 기존 프로토콜처럼 불필요한 데이터와 프로토콜 오버헤드를 전송하여 에너지를 낭비하는 것은 합리적이지 않으므로 이러한 디바이스를 직접 구현하는 것은 효율적이지 않습니다. 대부분의 IoT 애플리케이션에서 트래픽 패턴은 [3, 4]로 분류됩니다:

* One-to-One: 두 지점 또는 엔드투엔드 사용자 간의 데이터 전송입니다. 전화 통화, 화상 통화 또는 소셜 커뮤니케이션을 통해 발생합니다.
* One-to-Many(또는 브로드캐스트): 한 노드가 전송한 데이터를 다수의 노드가 수신할 수 있을 때 발생합니다. 예를 들어 기지국(BS)이 업데이트 정보(예: 업데이트 라우팅 테이블, 소프트웨어 등)를 자신과 연결된 모든 노드에 전송하는 경우입니다.
* Many-to-One: 네트워크에 속한 모든 센서 노드에서 하나의 중앙 지점으로 데이터를 전송하는 것입니다. 예를 들어, 도시의 기상 환경은 많은 센서를 사용하여 해당 지역을 감지한 다음 중앙 애플리케이션으로 전송합니다.

 Many-to-One에서 센서 노드는 이러한 스마트 오브젝트의 무선 전송 거리가 수 미터이기 때문에 중간 노드를 사용하여 정보를 최종 수신기로 전송합니다. 중간 노드는 패킷의 릴레이 역할을 합니다. 따라서 패킷은 목적지에 도달하기 위해 여러 링크와 디바이스에 접속합니다[5]. 멀티홉 이동 중에는 네트워크 내의 다양한 알고리즘에 따라 패킷이 전송되며 패킷 도착률, 대역폭, 패킷의 데드라인, 메모리, 패킷 크기 등으로 인해 패킷이 떨어질 가능성이 존재합니다. 이 경우 장치가 전송된 패킷에 대한 확인을 보내거나 손실된 데이터의 재전송을 보고해야 합니다. 네트워크 장치에서 생성되는 ICMP(인터넷 제어 메시지 프로토콜)는 IP 패킷에 IP 주소가 캡슐화된 원래 소스로 전송되는 오류 보고 프로토콜입니다. ICMP 패킷은 ICMPv4와 ICMPv6의 경우 각각 8바이트의 ICMP 헤더 + 20바이트의 IPv4 또는 8바이트의 ICMP 헤더 + 40바이트의 IPv6로 구성됩니다[6]. 재전송 패킷은 안정적인 통신을 제공하지만 동시에 네트워크의 에너지와 대역폭을 더 많이 사용합니다. 이는 네트워크의 처리량을 감소시켜 시스템 성능에 영향을 미칩니다. 재전송은 패킷 드롭에 필요한 추가 시간으로 인해 지연 시간을 증가시킵니다. 또한 홉 수가 증가하여 패킷 손실 및 지연이 증가할 수 있습니다. 네트워크 리소스 제한으로 인해 디바이스 수가 급증하면 패킷 손실이 증가합니다. 따라서 이는 시스템과 애플리케이션의 서비스 품질(QoS)에 영향을 미칩니다[7, 8].

 미래의 네트워크는 넓은 지역에 수많은 디바이스를 배치할 것입니다. 따라서 솔루션은 더 많은 수의 노드와 더 넓은 영역을 고려해야 합니다. 이를 위해 본 연구의 목표와 범위는 IoT 애플리케이션의 패킷 손실과 에너지 사용량을 줄이는 것입니다. 이 연구에서는 우선 롱홉(LH) 스케줄링 알고리즘을 제안했습니다. LH 전략은 실시간 작업에 사용되는 동적 스케줄링 알고리즘으로, 프로세스를 우선순위 대기열에 배치합니다. 대기열은 노드 수가 많고 거리가 먼 패킷을 검색하여 최종 수신자에게 먼저 라우팅합니다.
 이 백서는 다음과 같이 진행됩니다: 섹션 II에서는 문헌에서 관련 연구를 검토합니다. 섹션 III에서는 IoT 시스템의 시스템 모델과 에너지 인식 메시지 스케줄링 알고리즘에 대해 설명합니다. 섹션 IV에서는 성능 평가 및 논의가 이루어집니다. 마지막으로 섹션 V에서 논문을 마무리합니다.

 

Related Work

WSN 및 IoT 네트워크 분야에서 에너지 절약 및 패킷 손실 문제에 대한 여러 연구가 조사되었습니다.

 

9]의 저자들은 IEEE 802.15.4e MAC 프로토콜을 위한 새로운 스케줄링 알고리즘으로 시간 동기화 채널 호핑(TSCH)을 제안합니다. 이 접근 방식은 고속도로 주소 지정이 가능한 원격 트랜스듀서를 기반으로 하는 멀티홉 WSN에 적합합니다. 제안된 방식은 짧은 지연 시간과 듀티 사이클을 개선하여 무선 센서 네트워크를 촉진함으로써 전력 효율을 극대화합니다.

 단시간 프로세스(SPT) 알고리즘은 [10]에서 구현되었습니다. 제안된 방식은 감지 영역을 하위 그룹으로 나누고 각 그룹에는 브로커가 있습니다. SPT 프로토콜은 브로커 수준에서 트래픽 강도에 따라 패킷을 선택해 최종 목적지로 전달합니다. 그 결과 에너지 소비와 서비스 응답 시간 측면에서 제안된 알고리즘이 IoT 네트워크에 효율적이고 효과적이라는 것이 입증되었습니다.
 또 다른 연구[11]에서는 가장 빠른 데드라인 우선(EDF) 알고리즘의 속성에 대해 설명합니다. EDF는 실시간 운영 체제에서 사용하는 동적 스케줄링 알고리즘입니다. 이 알고리즘은 대기열에서 초과된 시간에 가장 가까운 메시지에 높은 우선순위를 할당합니다. 그러나 동시에 도착하는 패킷과 더 높은 에너지를 소비하는 패킷은 고려하지 않습니다. 따라서 오류가 발생하더라도 스케줄링 작업은 만료 시간 내에 완료됩니다. 

 다른 연구[12]에서는 선착순(FCFS) 알고리즘을 조사합니다. FCFS는 대기열에 도착한 시간에 따라 패킷을 전달하는 데 널리 사용되는 기법입니다. 첫 번째 패킷이 큐에 도착한 다음 첫 번째 패킷이 목적지로 전달됩니다. 데이터를 목적지까지 전달하는 데는 공정하지만, 데이터가 여러 장치와 링크에 액세스하기 때문에 시스템에서 대기하는 데 많은 에너지를 사용하는 불공정한 방식입니다. 따라서 대기 시간으로 인해 패킷이 재전송될 확률이 높아집니다. 제안된 알고리즘은 처리량이 낮고 성능이 저하되며 시스템이 불안정하고 평균 대기 시간이 길어집니다.

 NJN(Nearest Job Next) 프로토콜은 항상 가장 가까운 장치를 첫 번째 작업으로 선택해 데이터를 수집한 후 최종 수신자에게 전달하는 스케줄링 알고리즘입니다. 제안된 연구는 시스템이 지연 시간을 줄이는 데 도움이 됩니다 [13-15].

 

 많은 연구자들이 WSN과 IoT 네트워크의 에너지 사용량을 개선하기 위해 노력하고 있지만, 문제는 IoT 자체의 특성에 있습니다. 원격 장치와 서비스가 증가할 것입니다. 이러한 애플리케이션의 대부분은 특정 작업을 수행하기 위해 임의의 영역에 배포됩니다. 따라서 서로 다른 위치에 위치한 노드가 패킷을 전달하기 위해 서로 다른 홉 수를 사용하는 문제를 해결하려면 스마트한 에너지 최적화가 필요합니다.

 IoT가 출시된 후 전 세계에 배포된 센서 노드의 수는 수백만 개, 수십억 개 또는 그 이상일 수 있습니다. 일반적으로 이러한 스마트 디바이스는 무선 전송 범위 때문에 멀티홉 기술을 사용합니다. 따라서 패킷은 다른 중간 노드를 거쳐 최종 수신기에 도달합니다. 먼 거리에 위치한 노드에서 전송되는 패킷은 더 많은 수의 디바이스를 거쳐 목표에 도달하기 때문에 노드의 에너지와 네트워크 대역폭을 소모하게 됩니다. 따라서 소비 전력을 최적화하고 네트워크 수명을 연장하기 위해서는 홉 수(따라서 거리)라는 요소도 고려해야 합니다. 앞서 언급한 목표를 달성하기 위해 본 연구에서는 롱홉(LH) 우선 스케줄링 기법을 도입했습니다. LH 기법은 먼 거리에서 전송된 패킷에 높은 우선순위를 부여하고 더 많은 수의 디바이스에 접속할 수 있도록 CH 노드에서 먼저 라우팅하는 방식입니다.

 

경쟁 기술 : [스케줄링 관련] LH 스케줄링 알고리즘, TSCH, SPT, EDF, RR 알고리즘

 

 

Proposed Energy Aware Message Scheduling Technique

시스템 인프라는 감지 필드에 무작위로 배치된 다수의 노드로 구성되며 하위 그룹으로 클러스터링됩니다. 이러한 센서 노드는 실외에서 이기종 패킷을 수집하여 클러스터 헤드(CH)로 전송하는 데 사용됩니다. (CH : 해당 network의 마지막 connecting device) 그룹에는 주변 센서로부터 정보를 수집하여 기지국(BS)으로 전달하는 역할을 담당하는 클러스터 헤드(CH)가 있습니다. 시스템 모델에서는 BS가 중앙 필드에 배치되고 전원이 완전히 공급된다고 가정했습니다. 그림 1은 많은 노드가 자체 CH에 연결되는 일반적인 IoT 시스템 아키텍처를 보여줍니다.

 

멀티홉 기술은 장치가 전송 범위 밖에 있더라도 장치가 서로 통신할 수 있도록 지원하는 데 사용됩니다. 따라서 원거리에 위치한 노드에서 전송되는 패킷은 패킷 이동(소스에서 목적지까지) 중에 높은 대역폭과 많은 양의 에너지를 소비합니다. 그림 2는 감지 필드에 무작위로 배치된 10번째 노드의 에너지 소비량 측정값을 보여줍니다.

 

이 노드들은 서로 다른 위치에 위치하며 패킷을 전달하기 위해 일부 중간 노드를 사용했습니다. 이는 멀리 떨어진 노드에서 전송된 패킷이 많은 디바이스에 액세스하고 목적지에 도달하기 위해 높은 에너지를 사용했음을 나타냅니다. 따라서 롱홉(LH) 우선 스케줄링 알고리즘은 먼 거리에서 오는 메시지에 높은 우선순위를 부여하고 멀티홉 통신 중 많은 수의 노드에 액세스하여 먼저 처리하도록 합니다. 

 

A. Long Hop (LH) Scheduling Algorithm

 앞서 설명한 것처럼 모든 센서 노드는 수집한 정보를 CH를 통해 중앙 애플리케이션(BS)으로 전송합니다. 따라서 CH는 주변 센서에서 전송되는 패킷 수가 많아지면 과부하가 걸리게 됩니다. 반대로 IoT 디바이스는 처리(패킷 송수신) 중에 패킷을 저장할 수 있는 메모리가 매우 작습니다. 또한 패킷 지연과 잠재적인 드롭 및 누락을 방지하기 위해 디바이스에 큰 메모리를 확보할 여유가 없습니다. 데이터가 도착할 때 버퍼가 할당되고 비어 있어야 합니다. 그렇지 않으면 데이터가 삭제되고 누락 횟수가 증가합니다. 이전 논문에서는 메모리 크기가 가득 차서 일부 패킷이 버려질 수 있음을 증명한 바 있습니다. 본 연구에서는 데이터가 동시에 도달하거나 CHs 큐에 있는 메시지 수를 초과할 때 패킷 손실이 발생합니다. 
 각 메시지 노드 msg(R_time,T_trans)에는 요청 기간 R_time과 요청의 전송 성공 시간 T_trans가 있습니다[16]. 트래픽이 정체되면 데이터가 의도한 목적지로 즉시 전송될 수 없습니다. 따라서 데이터는 대기열이 서비스할 준비가 될 때까지 일정 기간 동안 버퍼링됩니다. 따라서 일부 패킷은 전송 시간 만료로 인해 즉시 삭제됩니다. 또한 두 개 이상의 패킷이 동시에 무선 주파수(RF) 안테나에 도달하면 패킷이 삭제됩니다. 수신기는 소프트웨어 또는 하드웨어 흐름 제어로 인해 오버플로우를 방지하기 위해 하나의 패킷을 보유하고 다른 패킷을 삭제하거나 때로는 둘 다 삭제합니다[6]. 그림 3은 멀티 홉 기술을 사용하여 서로 연결되는 센서 노드 세트를 보여줍니다. 

 

 

 이 장치들은 작업을 BS로 전송하고 CH에서 버퍼링하며 대기열을 기다린다고 가정합니다. 각 작업은 홉 수와 거리가 다릅니다. LH 프로토콜은 가장 많은 홉과 긴 거리를 기준으로 CH 버퍼에서 패킷을 재배열하여 먼저 BS로 전달합니다. 대기 시간 동안 일부 패킷은 시간을 초과한 메시지(예: 노란색 패킷)로 인해 삭제됩니다. 또한 (주황색과 녹색) 패킷이 동시에 RF 안테나에 도달하는 경우도 있습니다. 이 경우 LH 정책은 더 높은 에너지를 사용한 패킷(즉, 녹색 패킷)을 취하고 다른 패킷(즉, 주황색 패킷)을 삭제합니다.

 

M/M/1 큐잉 모델은 디바이스에서 들어오는 모든 메시지의 서비스 속도와 도착률을 계산하는 데 사용되었습니다. 
M/M/1은 시스템에서 단일 서버의 대기열 길이를 나타내는 수학적 확률 이론에 속하는 큐잉 이론입니다. 서비스 시간은 지수 분포를 가지며 지수 도착률은 푸아송 프로세스[16]에 의해 결정됩니다.

 m 메시지에 대한 서비스 속도와 도착 속도는 각각 μ와 λ로 도입됩니다. 클러스터 헤드에서 시스템 트래픽을 평가한 후, 식 3에 따라 트래픽 강도(P)는 1보다 작아야 하지만, P가 1보다 크면 제안한 알고리즘은 패킷이 많은 장치에 액세스하고 재전송으로 인한 높은 에너지를 사용하는 것을 피합니다. 알고리즘 1은 LH 연산의 의사 코드를 사용하여 알고리즘을 설명합니다.

 

 

경쟁 기술: LH 알고리즘의 process