Routing and Clustering Protocols for Unmanned Aerial Vehicle Networks

Abstract

최근 몇 년간 무인비행체 (UAV) 네트워크는 학계와 산업연구계의 관심 영역이었으며, 많은 군사 및 민간 용도에 사용되어 왔다. UAV 네트워크는 모바일 애드혹 네트워크, 차량 애드혹 네트워크와는 다른 고유한 특징을 가지고 있다. 동적 다중 UAV 네트워크에서는 위치 측정, 클러스터링, 라우팅이 협력 제어의 기본 기능이다. 그러나 UAV의 이동성이 높고 토폴로지가 급변하기 때문에 UAV의 위치 측정, 클러스터링, 라우팅 등은 도전 과제이다. 네트워크 성능을 향상시키기 위해, 클러스터링 접근법은 UAV 라우팅 문제를 해결하기 위해 사용되어 왔다. 다중 UAV 네트워크에서는 네트워크의 확장성과 안정성을 처리하기 위해 클러스터링을 사용한다. 에너지 한계로 인해, 네트워크 수명은 UAV 네트워크에서 중요한 요소이다. 나아가 UAV는 이동성이 크므로 통신 간섭을 줄이기 위해서는 위상 제어가 필수적이다. 마지막으로, UAV 네트워크에서 클러스터링과 함께 위치 측정 기술의 사용은 오버헤드, 지연 시간 및 에너지 소비량을 낮추면서 네트워크 성능을 향상시킬 수 있다.

첫 번째 연구에서는 UAV 네트워크에 대해 위치 기반 전달을 SCF (Store-carry-forward) 기법과 결합한 위치 기반 전달을 이용하는 재난 후속 과정에 사용하기 위한 위치 기반 지연 허용 라우팅(LADTR) 프로토콜을 제안한다. 전달 UAV는 효율적인 SCF를 가능하게 하기 위해 도입되었으며, 이는 UAV 네트워크 경로에 전달 UAV를 도입하여 사용하는 최초의 시도이다. 전달 UAV는 UAV 검색과 지상국 간 연결 경로의 가용성이 향상시킴으로써 종단간 지연이 감소하고 패킷 전송률이 높아진다. 향후의 UAV 위치는 위성 위치 확인 시스템(GPS)이 장착된 UAV의 위치와 속도를 기준으로 추정한다. 포워딩 UAV 노드는 대상 UAV 노드의 위치를 예측한 다음 포워딩할 위치를 결정한다. 제안된 LADTR은 UAV 노드 간의 접촉률이 높은 상태를 유지하도록 하여 패킷 전송률이 높은 것을 보장하고, 각 메시지의 복제를 피하기 위해 단일 복사 데이터 전달을 보장한다.

두 번째 연구에서는 긴급 통신을 위한 UAV 네트워크에 군집 지능 기반의 위치 측정 및 클러스터링 기법을 제안한다. 우선 경계 상자 방식을 이용해 제한된 경계에서 입자 검색 공간을 활용하는 입자 군집 최적화(PSO) 기반의 새로운 3차원(3D) 군집 지능 기반 위치 측정 (SIL) 알고리즘을 제안한다. 3D 검색 공간에서는 앵커 UAV 노드가 무작위로 분포하고 SIL 알고리즘이 기존 앵커 노드와의 거리를 측정해 대상 UAV 노드의 위치를 추정한다. 낮은 계산 비용으로 수렴 시간과 위치 측정 정확도가 향상된다. 둘째로, 우리는 PSO에 기반한 에너지 효율적인 군집 지능 기반 클러스터링(SIC) 알고리즘을 제안한다. PSO는 클러스터 상호간 거리, 클러스터 내 노드간 거리, 잔존 에너지 및 지리적 위치에 대한 입자 적합성 기능을 활용한다. 에너지 효율적인 클러스터링의 경우 향상된 입자 최적화를 기반으로 클러스터 헤드를 선택한다.

마지막 연구에서는, 산불 발견 및 감시를 위한 UAV 네트워크에서의 위치 측정 및 클러스터링을 위한 생물학 기반 알고리즘을 제안한다. 먼저 에너지 효율이 높은 3차원 생물학 기반 위치 측정(BIL) 알고리즘을 제안한다. 알고리즘은 하이브리드 회색 늑대 최적화(HGWO)에 기반해 노드 위치 측정 오류를 줄이고 거리 측정 오류에서 플립 모호성(FA)을 피할 수 있으며 높은 위치 측정 정확도를 달성할 수 있다. UAV 노드 사이의 거리를 측정한 후, HGWO 알고리즘은 UAV의 위치를 추정하여 결과의 글로벌 수렴을 보장한다. 둘째, HGWO 알고리즘을 기반으로 UAV의 에너지를 절약할 수 있는 새로운 에너지 효율 생물학 기반 클러스터링(BIC) 알고리즘을 제안한다. BIC 알고리즘은 회색 늑대 리더십 계층 구조를 활용해 클러스터링 효율을 개선한다. 또한, 최소 전송 수를 제공하는 최적의 클러스터 수를 결정하기 위한 분석 모델을 개발한다. 마지막으로 클러스터 헤드(CH)에서 기지국(BS)으로 데이터를 전송하는 GWO 기반 압축 센싱(CS-GWO)을 제안한다. 제안된 CS-GWO는 CH에서 BS로 효율적인 라우팅 트리를 구축하여 라우팅 지연과 전송 횟수를 줄인다.

제안된 각 알고리즘의 성능을 기존 연구과 비교하기 위하여 컴퓨터 시뮬레이션을 통해 평가한다. 제안한 LADTR은 패킷 전달 비율, 평균 지연시간 및 라우팅 오버헤드 측면에서 기존 4개의 라우팅 프로토콜보다 우수함을 보여준다. 제안한 SIC는 패킷 전송 비율, 평균 종단간 지연시간, 라우팅 오버헤드 측면에서 기존 5개의 라우팅 프로토콜을 능가한다. 더욱이 SIC는 에너지를 덜 소비하고 네트워크 수명을 연장한다. 제안한 BIL과 BIC는 서로 다른 시나리오의 다양한 성능 척도에서 기존 방법들보다 우수한 성능을 나타낸다. |In recent years, unmanned aerial vehicle (UAV) networks have been a focus area of the academic and industrial research community. They have been used in many military and civilian applications. UAV networks have unique features and characteristics that are different from mobile ad hoc networks and vehicular ad hoc networks. In dynamic multi-UAV networks, localization, clustering and routing are the fundamental functions for cooperative control. However, due to the high mobility of UAVs and rapid topology change, UAV localization, clustering and routing are the challenging task. In order to improve the network performance, the clustering approach has been used to address the UAV routing problem. In multi-UAV networks, clustering is used to handle the scalability and stability of networks. Due to energy limitations, network lifetime is a crucial parameter in UAV networks. Furthermore, due to the high mobility of UAVs, topology control is essential to reduce communication interference. Finally, the use of localization with clustering in UAV networks can increase network performance with lower overhead, latency, and energy consumption.

In the first work, we propose a location-aided delay tolerant routing (LADTR) protocol for UAV networks for use in post-disaster operations, which exploits location-aided forwarding combined with a store-carry-forward (SCF) technique. Ferrying UAVs are introduced to enable an efficient SCF, and this is the first attempt at introducing and using ferrying UAVs for routing in UAV networks, to the best of our knowledge. Ferrying UAVs improve the availability of connection paths between searching UAVs and the ground station, thus reducing end-to-end delays and increasing the packet delivery ratio. Future UAV locations are estimated based on the location and speed of UAVs equipped with a global positioning system. The forwarding UAV node predicts the position of the destination UAV node and then decides where to forward. The proposed LADTR ensures that the contact rate between UAV nodes remains high, which enables a high packet delivery ratio, and ensures single-copy data forwarding to avoid replication of each message.

In the second work, we propose swarm-intelligence-based localization and clustering schemes in UAV networks for emergency communications. First, we propose a new three-dimensional (3D) swarm-intelligence-based localization (SIL) algorithm based on particle swarm optimization (PSO) that exploits the particle search space in a limited boundary by using the bounding box method. In the 3D search space, anchor UAV nodes are randomly distributed and the SIL algorithm measures the distance to existing anchor nodes for estimating the location of the target UAV nodes. Convergence time and localization accuracy are improved with lower computational cost. Second, we propose an energy-efficient swarm-intelligence-based clustering (SIC) algorithm based on PSO, in which the particle fitness function is exploited for inter-cluster distance, intra-cluster distance, residual energy, and geographic location. For energy-efficient clustering, cluster heads are selected based on improved particle optimization.

In the last work, we propose bio-inspired localization and clustering schemes in UAV networks for wildfire detection and monitoring. First, we propose an energy-efficient bio-inspired three-dimensional localization (BIL) algorithm. The algorithm is based on hybrid grey wolf optimization (HGWO), which can reduce node localization errors and avoid flip ambiguity (FA) in bounded distance measurement errors and achieves high localization accuracy. After measuring the distance between UAV nodes, the HGWO algorithm estimates the locations of the UAVs, which ensures the global convergence of the results. Second, based on the HGWO algorithm, we propose a new energy-efficient bio-inspired clustering (BIC) algorithm to save the energy of UAVs. The BIC algorithm utilizes the grey wolf leadership hierarchy to improve clustering efficiency. Furthermore, we develop an analytical model for determining the optimal number of clusters that provide the minimum number of transmissions. Finally, we propose GWO-based compressive sensing (CS-GWO) to transmit data from cluster heads (CHs) to the base station (BS). The proposed CS-GWO constructs an efficient routing tree from CHs to BS, thereby reducing the routing delay and the number of transmissions.

The performance of each proposed algorithm has been evaluated by computer simulation with the comparison to the existing works. Our performance study shows that the proposed LADTR outperforms the four typical routing protocols reported in the literature in terms of packet delivery ratio, average delay, and routing overhead. The proposed SIC outperforms five typical routing protocols regarding to packet delivery ratio, average end-to-end delay, and routing overhead. Moreover, SIC consumes less energy and prolongs network lifetime. Finally, the proposed BIL and BIC significantly outperform conventional schemes, in terms of various performance metrics under different scenarios.