Home

AIS는 자선의 위치 및 운항 정보를 담은 메시지를 VHF 주파수를 통해 주변 선박 및 연안국을 향해 자동으로 전파하는 기능을 수행하는 장치이다.

AIS는 SOLAS(International Convention for the Safety of Life at Sea) 협약 제5장 제19규칙에 따라 총톤수 300톤 이상 국제 항해에 종사하는 선박과 총톤수 500톤 이상 국제 항해에 종사하지 않는 선박, 그리고 크기에 상관없이 모든 여객선에 의무적으로 설치되어 운용되고 있다.

AIS 메시지에는 MMSI(Maritime Mobile Service Identity), IMO(International Maritime Organization) 번호, 호출부호(Call sign), 선명, 선종, 선박의 길이와 폭, 선박의 위치, UTC 시각, SOG(Speed Over Ground), COG(Course Over Ground), 선수방위(Heading), 항해상태, 선박의 흘수(Draft), 선적된 위험 화물의 종류, 목적지, ETA(Estimated Time of Arrival) 등의 다양한 정보가 포함되어 있다[2][3].

전 세계 해역에서 실시간으로 대량의 AIS 메시지가 생성되고 수집되고 있으며 이를 활용하여 유용한 정보를 도출하려는 많은 연구들이 수행되어 왔다. 이들 중 일부는 선박항로를 추출하는 방식에 대해 다루고 있다.

Rong 등[4]은 목적지에 기준하여 데이터를 분류하고 이들 각각에 대하여 DBSCAN 알고리즘을 적용하여 변침 구간(Turning section)과 이들을 연결하는 구간(Leg)을 구분하였다. 그리고 각 구간에 대해 선종, SOG, COG에 대한 통계 분석을 수행하고 이에 기반하여 이상운항을 감지하였다. Pallotta 등[5]은 DBSCAN을 점진적으로 수행하여 waypoint를 찾아내고 이들을 연결함으로써 선박항로를 추출하는 TREAD(Traffic Route Extraction and Anomaly Detection) 방법론을 정의하고 이를 이상운항 감지 및 항로의 예측에 사용하였다. Yan 등[6]은 선박 궤적에 부가적 의미를 부여한 객체인 STSO(Ship Trip Semantic Object)를 정의하였다. 그리고 그에 기반해 그래프 형태의 선박항로를 추출하는 방식을 고안하였다. Zhen 등[7]은 나이브 베이즈 분류기를 사용하여 선박 궤적들을 클러스터링하였다. 그리고 각 클러스터들의 특성을 추출함으로써 대표적인 선박항로를 도출하였다. Dobrkovic 등[8]은 DBSCAN 알고리즘 대신 유전 알고리즘에 기반하여 waypoint를 추출하고 이들을 연결함으로써 선박항로를 생성하였다. Filipiak 등[9]은 Dobrkovic 등의 연구로부터 영감을 얻어 선박항로 패턴의 추출에 유전 알고리즘을 적용하되 부가적으로 CUSUM 알고리즘을 적용하여 변침 및 선속의 변화가 일어나는 지점에 가중치를 부여하였으며 waypoint 추출에 사용되는 B-tree와 quad tree의 성능에 대해서도 비교 분석하였다.

본 논문에서는 AIS 데이터로부터 선박항로 패턴의 waypoint를 추출하기 위해 PSO 알고리즘에 기반한 클러스터링을 수행한다. PSO 알고리즘은 1995년 J. Kennedy와 R. C. Eberhart[10]에 의해 발표된 알고리즘으로, 새 떼나 물고기 떼 등의 생물 군집이 먹이를 탐색하거나 포식자를 피해 도망칠 때 개인적 경험뿐만 아니라 군집 전체의 움직임으로부터 얻은 군집 경험까지 반영하여 다음 움직임을 결정하는 행동 방식에 착안하고 있다.

PSO 알고리즘에서 군집(Swarm)은 여러개의 입자(Particle)들로 구성되며 각각의 입자들은 위치(Position)와 속도(Velocity)라는 두 가지 속성을 가진다. 입자들은 탐색 공간 내 임의의 위치와 임의의 속도로 초기화된 후 탐색을 시작한다. 매 탐색마다 각각의 입자는 개개의 최적위치(pBest)와 군집의 최적위치(gBest)를 함께 반영하여 속도를 갱신하고 갱신된 속도에 따라 다음 탐색위치로 이동한다. 그리고 다음 탐색위치에서 그 적합도를 평가하고 기존 최적위치에서의 적합도보다 점수가 높을 경우 개개의 최적위치와 군집의 최적위치를 갱신한다. 군집에 속하는 각 입자들의 속도(V(t)) 및 위치의 갱신(X(t))는 식 (1)과 식 (2)에 따라 수행된다.

여기서, w는 관성계수로서 현재속도를 보존하는 정도를 나타내며, c₁은 입자의 최적위치에 대한 반영 계수이고, c₂는 군집의 최적위치에 대한 반영 계수이다.

본 논문에서는 특정 해역을 통항하는 다수의 선박들이 사용하는 보편적인 선박항로 패턴을 추출하는 방식을 제안한다.

선박항로 패턴이란 특정 해역 내 다수의 선박항로들에서 공통적으로 나타나는 선박항로의 형태로, 개별 선박항로와 유사하게 waypoint와 leg로 구성된 형태로 정의한다. 이때 선박항로 패턴의 waypoint는 다수의 선박들이 변침하는 구간을 의미하고 leg는 이들 waypoint 사이를 잇는 구간을 의미한다. 선박항로 패턴은 방향 그래프(Directed graph)로 표현한다. 선박항로 패턴의 waypoint는 방향 그래프의 노드(Node)로, leg는 방향 그래프의 간선(Edge)으로 표현된다.

그림 1은 총 7개의 개별 선박항로들과 이들로부터 추출된 선박항로 패턴의 예시를 보여준다. 선박항로 패턴의 waypoint는 개별 항로들의 waypoint가 다수 분포하는 구역에서 나타나며, 선박항로 패턴의 leg는 이들 waypoint를 잇는 구간 중 다수의 개별 항로들이 포함되는 구간에서 나타난다.

Fig. 1. 
Ship routes and ship route pattern

추출되는 선박항로 패턴의 waypoint와 leg 각각에는 선박들의 통과 빈도가 반영되고 있다. 따라서 추출되는 선박항로 패턴은 해당 구간을 통항하는 선박들이 보편적으로 사용하는 항로로 볼 수 있다.

선박항로 패턴 추출은 총 세 단계로 나누어 수행된다. 첫 번째 단계는 전처리 단계이다. 전처리 단계에서는 AIS 데이터에 존재하는 오류 제거, 분석 대상이 되는 데이터의 선별, 이들로부터 궤적 데이터를 생성한 뒤 각 궤적별로 압축을 수행한다. 두 번째 단계는 waypoint 추출 단계이다. Waypoint 추출 단계에서는 PSO 알고리즘과 quad tree에 기반한 점진적 클러스터링을 수행하여 waypoint를 추출한다. 세 번째 단계는 leg 추출 단계이다. Leg 추출 단계에서는 앞서 추출된 waypoint와 전처리된 데이터로부터 leg를 추출하고 방향 그래프를 생성한다. 전체 프로세스를 도식으로 표현하면 그림 2와 같다.

Fig. 2. 
Diagram of whole processes

전처리 단계에서는 VHF를 통해 메시지를 송수신하는 AIS의 특성 상 존재할 수 있는 누락이나 변조 등의 오류를 제거하고 분석 대상이 되는 선박과 해역에 대한 데이터를 선별한다. 이때 데이터의 선별은 해역의 범위, 선종, 선박의 크기, 선속 등에 기반하여 수행된다. 이후 각 선박별 데이터에서 변침구간을 특정하기 위하여 궤적 압축을 수행한다. 이를 위해 Douglas-Peuker 알고리즘을 사용하여 변침 정도가 큰 구간 위주로 궤적을 압축한다.

Waypoint 추출 단계에서는 전처리된 데이터로부터 선박항로 패턴의 waypoint들을 추출한다. 앞서 선박항로 패턴의 waypoint를 많은 선박들이 변침을 수행하는 구간이라 정의하였으므로 waypoint 추출은 클러스터링을 통해 이뤄질 수 있다.

이때 대상 해역에는 수많은 waypoint가 존재할 수 있으므로 클러스터링 수행 시 클러스터의 개수를 모르는 상태에서 모든 클러스터를 찾아낼 수 있어야 한다. 이와 같은 방식으로 접근하는 대표적인 클러스터링 알고리즘으로 DBSCAN 알고리즘이 있으나 AIS 데이터와 같이 다양한 밀도와 클러스터간 거리를 가지는 데이터에서는 잘못된 클러스터링으로 이어지기 쉽다.

따라서 본 논문에서는 한 번에 탐색 공간에 존재하는 모든 클러스터를 찾는 대신에 한 번에 적은 수의 클러스터를 탐색하되 그 과정에 사용된 데이터를 탐색 공간으로부터 제거한 후 다시 반복하여 탐색을 수행함으로써 전체 클러스터를 찾아내는 점진적 방식을 사용하였다. 이때 PSO 알고리즘에 기반한 클러스터링과 quad tree를 적용하였다.

이러한 PSO알고리즘에 기반한 waypoint 추출을 위해 먼저 입자와 군집을 정의하였다. 하나의 입자는 탐색 공간내에서 한 번에 탐색할 n개의 waypoint들의 집합으로 구성하였다. 이들 각 입자는 위치와 속도라는 속성을 가지고 있는데, 위치는 waypoint들의 중심점의 위도, 경도, 반지름의 크기로 구성하였으며 속도는 중심점의 위도, 경도에만 부여하였다. 이와 같이 정의한 입자는 그림 3과 같이 표현될 수 있다.

Fig. 3. 
Composition of particle

군집은 그림 4와 같이 m개의 입자로 구성하였다. 군집에 속하는 각 입자들은 탐색 공간 내에서 n개씩 waypoint들을 추출하는 후보가 되며, 지정된 횟수만큼 각자 탐색을 수행한 후, 적합도를 계산하여 적합도가 가장 높은 입자의 waypoint들이 추출 결과가 된다.

Fig. 4. 
Composition of swarm

또한, 적합도에 따라 입자 개개의 최적위치와 군집의 최적위치(gBest)를 갱신하게 된다. 본 논문에서는 각 입자의 적합도를 반경(Rad) 내에 존재하는 개별 선박의 변침점들의 개수의 합으로 정의하였다.

그림 5는 군집에서 각 입자들의 탐색 과정을 보여주고 있다. 그림에서 군집은 2개의 입자로 구성되어 있으며, 각 입자들은 3개의 waypoint를 가지고 있다. 각 입자들은 개개의 최적위치와 군집의 최적위치를 반영하여 탐색을 수행하며 그 과정에서 점차 좋은 위치를 찾아간다. 즉, 지정된 횟수만큼 탐색을 수행한 뒤 군집 내에서 가장 적합한 입자를 선별하고, 그 입자의 waypoint들의 위치를 탐색 결과로 출력한다.

Fig. 5. 
Search process

Leg 추출 단계에서는 앞서 추출된 waypoint와 전처리된 데이터를 사용하여 선박항로 패턴의 leg를 추출하고 간선에 가중치를 가지는 방향 그래프를 생성한다. 각 간선에는 해당 간선을 통항하는 선박 궤적의 수만큼 가중치를 부여하며 이들 가중치에 최소값을 둠으로써 추출된 선박항로 패턴이 보편성을 가지도록 하였다.

본 논문에서 제안하는 방식의 정확성을 평가하기 위하여 실제 수집된 AIS 데이터를 사용하여 실험을 수행하였다. 실험은 Windows 11에서 수행되었으며 코드는 Python 3.7.11로 작성되었다. 실험에는 U.S. Coast Guard Navigation Center에서 수집하여 공개하고 있는 AIS 데이터를 사용하였다. 실험에 사용된 데이터의 제원은 표 1과 같다.

실험은 휴스턴 연안 해역(위도 28N~30N, 경도 93W~95W)에서 길이 200m 이상, 7knots 이상의 선속으로 항해한 화물선들을 대상으로 수행하였다.

전처리 단계에서는 대상 해역 및 대상 선박에 대한 선별을 수행하고 이들에 대한 압축 작업을 수행하였다. 그림 6은 휴스턴 연안 해역에서 2020년 1월 한달 간 수집된 데이터들의 전처리 전후 모습을 보여준다.

Fig. 6. 
Result of preprocessing

전처리 전후 비교를 통해 AIS 데이터 상 존재하는 오류들이 제거되었으며, 선박항로 패턴 추출의 대상인 대형 선박들이 통항할 수 없는 수로를 통항하는 소형 선박들과 저속으로 운항한 선박들의 데이터가 제거되었고, 또한 변침이 수행되는 지점 위주로 데이터가 압축된 것을 확인할 수 있다.

Waypoint 추출 단계에서는 quad tree의 각 노드에 포함되는 최대 데이터 개수, PSO의 입자를 구성하는 waypoint의 개수, 군집을 구성하는 입자의 개수, 군집의 탐색 횟수, waypoint의 반지름 크기 등 5개 파라미터가 사용자에 의해 지정되어야 하며 이들의 값에 따라 추출 성능과 속도가 달라진다.

따라서 각각의 파라미터별로 실험을 수행하였으며, 최종적으로 가장 적합한 추출 성능과 추출 속도를 보이는 파라미터 값들을 선정하고 waypoint를 추출하였다. 최종적으로 추출된 waypoint들은 그림 7과 같다.

Fig. 7. 
Result of waypoint extraction

Leg 추출 단계에서는 전 단계에서 추출된 waypoint와 전처리된 데이터에 기반하여 waypoint들 사이를 잇는 leg를 추출하고, 최종적으로 선박항로 패턴을 나타내는 방향 그래프를 생성하였다. 그 결과는 그림 8과 같다.

Fig. 8. 
Result of leg extraction

연안 해역에는 선박 통항량이 매우 많기 때문에 일반적으로 선박들의 안전 항해를 위해 해당 국가의 국내법으로 강제항로나 권고항로를 지정하여 운영하고 있으며, 해당 구역을 통과하는 선박들은 일반적으로 이들 지정항로를 따라 항해한다. 따라서 이와 같은 강제항로나 권고항로가 존재하는 해역에서 추출된 선박항로 패턴은 이들 지정항로와 유사한 형태를 보여야 한다. 이런 특성에 기반하여 추출된 선박항로 패턴과 지정항로를 동일 해도상에 표기하여 비교함으로써 추출 결과의 정확성을 평가할 수 있다.

본 실험의 대상이 되는 휴스턴 연안 해역에는 강제항로와 권고항로가 존재한다[11]. 비교를 위하여 휴스턴 연안 해역에서 추출된 선박항로 패턴을 해도 상에 표시하면 그림 9와 같다. 이때 그림 상에 굵은 주황색으로 표기된 부분은 지정항로를 나타내며 방향 그래프는 추출된 선박항로 패턴을 나타낸다.

Fig. 9. 
Designated route and extracted ship route pattern

비교 결과 추출된 선박항로 패턴이 지정항로와 거의 동일한 형태를 보이므로 본 연구에서 제안한 방식을 통해 정확한 선박항로 패턴을 추출할 수 있음을 확인할 수 있다. 또한 일부 선박들이 지정항로를 가로지르는 형태로 운항한다는 부가적인 점까지 확인할 수 있다.