UAV Navigation Route Control Using Wireless Multi-hop Network

無人航空機（UAV: Unmanned aerial vehicle）は，配送サービスなど様々な場面で活用が期待されてい る．それら様々なサービスが混在し UAV の密度が高い環境となった場合，航空機と同様に航空保安無 線施設を用いた UAV 管制システムが必要になる．これに対し，パケット交換網に着想を得た，各家屋に設置した無線デバ イスによる無線マルチホップネットワークを用いた UAV 分散管理方式について解説する．本方式の核となる，モバイルアド ホックネットワーク（MANET）プロトコルをベースに，住宅が密集した危険な地区の上空（集中地区）を極力避け，安全で 効率的な航行経路を構築するルーチングプロトコルを示す．サービスが普及し複数 UAV が同時に航行する場合に対応し， 経路の重複による衝突の危険性をなくす，構築した経路で使用するリンクを，他 UAV の経路に利用できないようにロックす る方式を示す．本方式は，経路が占有されることによるリンク不足を解消するために，リンクが階層化されている．更にサー ビスが普及し大量の UAV が同時に航行する場合に対応し，送信先までの経路候補を複数構築し，動的に次ホップを選択す ることで空域の混雑を緩和し，空域の混雑に応じて UAV の流入を制限することで利用者間の公平性を担保する方式を示す． Key Words UAV 航行経路制御，無線マルチホップネットワーク，MANET，ルーチングプロトコル ⓒ 2025 電子情報通信学会 上田清志 Kiyoshi Ueda † 三好　匠 Takumi Miyoshi †† 山崎　託 Taku Yamazaki †† 山本　嶺 Ryo Yamamoto ††† † 日本大学，郡山市 Nihon Univ.，Koriyama-shi，963-8642 Japan †† 芝浦工業大学，さいたま市 Shibaura Inst. of Tech.，Saitama-shi，337-8570 Japan ††† 電気通信大学，調布市 The Univ. of Elec.-Commun.，Chufu-shi，182- 8585 Japan 解説論文 無線マルチホップネットワークによる UAV 航行経路制御 37 小特集 ドローンと通信技術による新たな価値創造を目指して Wang らは，UAV の 3D 経路計画用に改良された バットアルゴリズムを示した．このアルゴリズム は，適応性と障害物回避に重点を置いている (11)． Gautam らは，効率的な 3D UAV 経路計画のため に遺伝的アルゴリズムとニューラルネットワークを 組み合わせ，複雑な環境下での適応性を強化し た (12)．Goncharenko らは，様々な制約条件下で効 率的な UAV ルート構築を行うために，複数の手法 を統合したハイブリッドアルゴリズムを提案し た (13)．Ozlem らは，航空ナビゲーションシステム における飛行効率を改善するための到着ルートの最 適化手法を示している (14)．Schouwenaars らは， 効率的な複数車両の経路計画のために混合整数計画 法を適用し，経路最適化と衝突回避に取り組んでい る (15)．Evdokimenkov らは，協調ミッションのた めの分散制御システムに焦点を当て，UAV 群の飛行 前計画アルゴリズムを調査した (16)．Ramesh らは， UAV ナビゲーションアルゴリズムの包括的なレ ビューを行い，傾向，課題を示した (17)．Sivakumar らは，農業，監視，災害管理における UAV の役割 に焦点を当て，UAV の多様な民間利用について調 査した (18)．Fu らは，経路の効率性と適応性に焦点 を当て，UAV の経路計画に特化したヒューリス ティックな進化アルゴリズムを提案した (19)． Danancier らは，脅威の多い環境における UAV の 様々な経路計画アルゴリズムを比較し，その性能と 堅ろう性を評価した (20)．Hodge らは，UAV のナビ ゲーションに深層強化学習技術を適用し，センサ データを利用して知能意思決定を可能にした (21)． 将来的に UAV の本格的な利用が始まると，様々 なサービスが混在し高密度に UAV が飛行する環境 が想定される．そのような環境では，航空機の通常 の航空路のように航空保安無線施設を結んだ経路を 航行する，各 UAV を管制するためのシステムが必 要になる．これに対し，多数の UAV が飛行する空 域を管制するシステム (22) が提案されているが，事 前にシステムへの参加を登録した事業者のみの利用 を前提としており，個人や UAV の新規利用者など によるシステムへの自由かつ柔軟な参加は難しいと 考えられる． 筆者らは，パケット交換網のバーチャルサーキッ ト方式とデータグラム方式から着想を得た，UAV の分散管理システムを確立した (23)．本システムで は，図 1 に示すように，各家屋に設置した無線デ バイスで構成される無線マルチホップネットワーク を用いて，各 UAV を自律分散的に制御する．その 際，UAV をネットワークにおけるパケット，地上 の無線デバイスをルータ，無線デバイス間の接続関 係をリンクとして扱うことで，パケット交換網にお ける制御を UAV の飛行経路制御に応用している． （1） モバイルアドホックネットワーク（MANET）を ベースにした最適経路構築方式 全ての家が UAV 配送サービスを利用しており， 宛先（荷物などの宅配先）になる必要があることを 想定している．したがって，住宅が密集した危険な 地区（集中地区）の家屋のノードも含む無線マルチ ホップネットワークを構築する．従来の MANET 技術では最短経路が構築されるため，この方式で経 路を構築すると，UAV の航行の安全性が考慮され 図１　無線マルチホップネットワークによる UAV 経路ナビゲーション ①ルーチングプロトコル 無線マルチホップデバイス 例：特定小電力無線（920MHz帯） 送信元ノード 送信先ノード 経路表 経路表 経路表 経路表 経路表 ○△□運輸 経路表 ②UAV航行経路（経路表） ③次ホップノード情報収集 UAV（パケット相当） ④次ホップノードへ移動 38 通信ソサイエティマガジン No.73  夏号 2025 なくなる．したがって，図 2 に示すように，住宅 が密集した危険な集中地区の上空を極力避け，電池 切れの危険を避ける移動時間が長過ぎない，安全で 効率的な無線マルチホップネットワークを構築する 必要がある (23)． （2） 高密度 UAV が安全に飛行する衝突回避経路構 築方式 様々なサービスが混在し高密度に UAV が飛行す る環境で，経路の重複（経路コンフリクト）による 衝突の危険性をなくす必要がある．そのため， UAV が使用する経路のリンクを，ほかの UAV の経 路に利用しない制御を行う．また，経路が占有され ることによるリンク不足を解消するために，リンク を仮想階層化する． （3） 空域の混雑に応じ利用者に公平な UAV の流入 制限方式 空域の混雑と利用者の公平性を考慮し，送信先ま での経路候補を複数構築し動的に次ホップを選択す ることで空域の混雑を緩和し，空域の混雑に応じて UAV の流入を制限し，利用者間の公平性を担保す る． 2 MANET をベースにした最適経路構 築方式 MANET のリアクティブ型プロトコルの代表例であ る Ad hoc On-Demand Distance Vector（AODV） Routing (24) とプロアクティブ型プロトコルの代表 例である Optimized Link State Routing Protocol （OLSR） (25) をベースに，集中地区を極力避けた安 全で効率的な経路を構築する． ２. １　AODV ベース最適 UAV 経路構築方式 送信元ノードが発信し，各ノードが受信した i 番 目の RREQ メッセージを図 3 の式 (1) で評価し， 最適な RREQ メッセージを求める．集中地区上と 点在地区上を移動する際の UAV の速度 v1，v2 をあ らかじめ設定し，ノード間ごとの移動時間を加算す るため RREQ ヘッダに追加した集中距離と点在距 離を割り移動時間を求める．α は移動時間と安全性 のバランスを調整する係数（0 㱡 α 㱡 1）であり， 各ノード間の移動時間に重み付けすることにより， 集中地区を避ける安全性の観点と移動時間が長過ぎ ない観点の両方を総合的に判断する．同時に得られ た複数の RREQ を式 (1) で評価した結果から，安 全性を考慮した最適なルート選択方式が確立され た (26) ，(27)．本経路構築の流れを図 3 に示す． ⑴ 送信元ノードは RREQ をブロードキャスト送信 する． ⑵ RREQ を受け取ったノードは，自身が所属して いる地区と送ってきたノードの地区を確認する． ⑶ ⑵ で確認した地区により RREQ の集中距離，点 在距離を加算する．また，事前に設定されてい る速度 v1，v2 を用いて，移動時間を求める． ⑷ ⑶ の時間から，重み α を用いてコストを求める． ⑸ ⑷ で求めたコストが自ノードで保持するコスト より小さければ最適 RREQ として記憶し転送す る． ⑹ 送信先ノードは送られてきた複数の RREQ から 図２　UAV 経路となるネットワークトポロジー 住宅集中地区境界 一般ノード ノード間最短経路の ネットワークトポロジー 転送ノード UAVナビゲーション ネットワークトポロジー  集中地区：危険な航行経路である住宅集中地区  点在地区：より安全で優先される航行経路である住宅点在地区 解説論文 無線マルチホップネットワークによる UAV 航行経路制御 39 小特集 ドローンと通信技術による新たな価値創造を目指して 最適ルートを選択する． ⑺ ⑹ をタイムアウトまで行い，タイムアウト時に 送信先ノードが最適ルートを RREP として送信 元ノードにユニキャスト送信する． ⑻ 送信元ノードに RREP が届き，最適ルートが構 築される． ２. ２ OLSR ベース最適 UAV 経路構築方式 OLSR では，各ノードで経路表が事前に作成され る．そのため，OLSR は HELLO メッセージ・TC メッセージを定期的に送信し合い，ローカルリンク 情報の更新を行う． 従来の OLSR ではホップ数を基に経路を選択す るため，物理的に UAV が移動する距離を基にした 最適経路にはならない．本方式では，最短経路探索 アルゴリズムであるダイクストラ法 (28) を用いるこ とで，UAV の移動距離を考慮した経路構築を行う． また，距離にリンク間の安全度合いの重みを付ける ことで，最短距離ではなく，集中地区を避け安全 で，電池切れを避けられるよう移動距離が長過ぎな い経路が確立できるような経路構築方式が確立され ている (29)． あらかじめ，全てのノードに UAV が安全に移動 できる点在地区か，航行が危険な集中地区かの情報 を与えておく．各制御メッセージを受信したノード は，リンクの安全度によって重み付けされた距離を リンクコストとしたダイクストラ法により，各ノー ドの経路表を作成する．各ノードでの経路構築の処 理の流れを図 4 に示す． ⑴ スタートノードの値（最小コスト候補）を 0， 他のノードの値を未確定（または∞）に設定す る． ⑵ 全ノードが確定ノードとなるまで以下を繰り返 す． ・ 未確定ノードのうち，最小の ID 値を持つノー ドを「確定ノード」とする．（確定フラグを立 てる．） ・ 確定ノードに接続するノードへのリンクコスト を，集中地区へ向かうリンクは距離の 3 倍，点 在地区へ向かうリンクは距離の 0.6 倍の重み付 けを行う． ・ 確定ノードに接続するノートに対して「確定 ノードまでのコスト＋接続リンクコスト」を計 算し，そのノードのコスト値よりも小さければ 図３　AODV ベース最適 UAV 経路構築方式 集中距離 点在距離 RREQ評価 送信元 ノード RREQ RREQ RREQ RREQ 送信先 ノード B B B B A 70 70 70 70 100 100 RREQ評価 RREQ評価 B RREQ評価 RREQ評価 RREQ 0 0 70 0 70 70 RREQ RREP RREP RREP A B 集中地区ノード 点在地区ノード i番目に届いたRREQメッセージを，最適化問題の決定変数相当をiとし 目的関数相当である式(1)を用いて評価する � ：UAVが送信元からi番目のRREQメッセージを受信したノードまでの 集中地区内を移動する距離（集中距離） � ：UAVが送信元からi番目のRREQメッセージを受信したノードまでの 点在地区内を移動する距離（点在距離） � ：集中地区内を移動する際の速度 � ：点在地区内を移動する際の速度 α ：移動時間と安全性のバランスを調整する係数 ( 0 ≦ α ≦1 ) min �� � ����� �1 � �� � � ����� ������ (1) 更新する． ⑶ 図 4 の場合，距離 210 でコスト 464 の集中地区 ノードを通る経路よりも，距離 340 でコスト 204 の点在地区ノードを通る経路が選択される． ２. ３　 最適 UAV 経路構築方式による送信元から送信 先への総移動距離と集中地区上の移動距離 送信元から送信先への経路の総距離と集中地区 上の距離を，従来方式の AODV，OLSR と最適経 路構築方式とで比較し，従来方式からの経路短縮率 を確認した． 実環境に近いモデルで実験するために，NS-3 (30) を利用してシミュレーションを実施した．図 5 に 示すように，ノードの配置を 3×3 の 9 マスとして， 中心に集中地区を配置する．中心以外は点在地区と した．各マスのノード数は集中地区が 40 個，点在 地区は 20 個でランダムに配置し，ノードの通信可 能距離を 120 ｍとし，1 マスのサイズは縦 333 ｍ × 横 333 ｍとした．ノードの移動・追加・削除は 行わない．実験を 100 回繰り返し，構築された経 路の総距離と集中地区距離の平均を求めた．集中地 区をまたぐように点在地区ノードから送信元・送信 先を選択し，集中地区をう回する経路が構築できる かを検証した (26)，(29)． 総距離と集中距離の短縮率を図 5 に示す．最適 経路構築方式は，AODV ベースも OLSR ベースも， 従来方式と比べて総距離が 20% 程度増加している ことが確認できる．これに対して，集中地距離の比 較では約 98% の改善が確認できた．集中地区ノー ドをう回して経路を構築した結果，総距離は伸びた ものの大幅に危険領域の航行を削減できた． 3 UAV 衝突を回避する階層化 UAV 経 路リンクロック方式 複数の UAV で経路構築を行うと，同じノード間 のリンクが使用されることで UAV 同士が衝突する 危険がある．そのため，図 6 に示すように，パケッ ト交換網のバーチャルサーキット方式を応用し，同 じリンクを使用しない，経路コンフリクトが発生し ない経路を構築する方式が確立された． また，同じリンクを使用しない経路構築方式で は，試用できるリンクが減少し経路構築に失敗する 確率が上がってしまう．そこで，航行高度の多階層 ネットワーク構築方式が確立された． ３. １　 AODV ベースの階層化 UAV 経路リンクロッ ク方式 リアクティブ型の AODV ベースの経路構築手順 を以下に示す．①，②，③，④の手順を図 7 に， ⑤，⑥，⑦の手順を図 8 に示す．各リンクの上空 に UAV が同時に存在できる許容数（以下，階層高  経路表を事前に作成しておき，経路要求にすぐ応答できる Proactive型の代表例であるOLSRをベースに最適ルートを構築  すべてのノードに自身が集中地区か点在地区かの情報を付与  経路計算時に物理距離をリンクコストとしたダイクストラ法を利用  物理距離にリンク安全度で重み付けをすることにより 移動距離の超過と集中地区を避けた経路を構築することが可能 [3] H. Gunji, T. Yamazaki, R. Yamamoto, T. Miyoshi, K. Ueda, “Proactive Route Construction for UAV Delivery considering Distance and Safety using Wireless Multi-hop Network,” IEICE Communications Express, Vol.11 No.7, pp.411-416, April. 2022. 図４ OLSRベース最適UAV経路構築法 ×3.0 ×0.6 ×3.0 ×0.6 A→A A→B B→A B→B B B B B A A B A B 70 70 70 100 100 Cost:60 Cost:102 Cost:144 Cost:462 Cost:210 Cost:420 集中地区ノード 点在地区ノード 送信元 ノード 送信先 ノード Cost:204 図４　OLSR ベース最適 UAV 経路構築法 小特集 ドローンと通信技術による新たな価値創造を目指して ランダムノード配置モデル UAVナビゲーション ネットワークトポロジー ノード配置モデル 集中地区 20ノード 20ノード 20ノード 20ノード 40ノード 20ノード 20ノード 20ノード 20ノード 点在地区 | | AODVベース OLSRベース 最適UAV経路構築法 最適UAV経路構築法 | | --- | --- | | 送信元から送信先への UAV経路総距離の短縮率 | -14.7% -20.3% | | UAV経路の集中地区を 通る距離の短縮率 | 98.5% 98.3% | 経路短縮率=（１－最適UAV経路距離/最短経路距離） 図５　最適 UAV 経路構築法による送信元から送信先への総距離と集中地区上の距離 キャスト送信する（図 8 ②）． ⑹ 中継ノードは RREP を受信した際，空き階層を 確認して使用階層を決め，ノード自身の経路表 と空塞表に記入しその階層をロックする（図 8 ③）． ⑺ 経路表に従い RREP を転送する．これを送信元 ノードが受信するまで行う（図 8 ④，⑤，⑥， ⑦）． 度数）の情報を追加する．このリンクの両端ノード がリンク空塞表として管理する (26)． ⑴ 送信元ノードは RREQ をブロードキャスト送信 する．RREQ 送信時には高度を指定しない（図 7 ②）． ⑵ RREQ を受け取った中継ノードは経路表の作成， 更新を行う．同時に空塞表を確認し，使用でき る階層があるか確認する．式 (1) の評価式で最 適な RREQ であれば送信する（図 7 ③，④）． ⑶ ２．の経路構築の手順で送信先ノードに届くま で ⑵ を繰り返す（図 7 ⑤，⑥）． ⑷ ２．の経路構築の手順で送信先ノードが最適な 経路 RREQ を選択する（図 7 ⑦）． ⑸ 送信先ノードが RREP を送信元ノードにユニ ３. ２　 OLSR ベースの階層化 UAV 経路リンクロッ ク方式 プロアクティブ型の OLSR をベースにしたプロ トコルに，リンクをロックする Route Keep（RK） メッセージを追加し，多階層の仮想リンクを各ノー リンク1 リンク3 ノード1 ノード2 ノード3 1 1 未使用 使用中 A D 2 2 B E 3 3 F C 2 1 リンク2 リンク4 バーチャル サーキット 1 G 飛行可能領域 2 H 3 I ノード1 ノード2 ノード3 ノード4 ノード5 (a)パケット交換網のバーチャルサーキット方式 (b)