複数のトレードオフを念頭にワイヤレスネットワークを自動設計(2/3)

１．複数のトレードオフを念頭にワイヤレスネットワークを自動設計(2/3)まとめ

・詳細な地理データを使用することで正確な経路損失予測が可能になり分散計算で高速実行が可能
・オートプランニングの入力には需要点候補拠点、予測信号強度、および予算枠を含める事が可能
・ネットワーク品質を最適化する目的に特化した局所探索アルゴリズムを開発して利用している

２．オートプランナーの仕組み

以下、ai.googleblog.comより「Challenges in Multi-objective Optimization for Automatic Wireless Network Planning」の意訳です。元記事は2022年5月12日、Sara AhmadianさんとMatthew Fahrbachさんによる投稿です。

アイキャッチ画像のクレジットはPhoto by Nastya Dulhiier on Unsplash

このようなハイブリッドアプローチは一般的ですが、詳細な地理データを使用することで、1m以下の解像度でも正確な経路損失予測が可能になります。

私達の伝搬エンジンは、ポイント・ツー・ポイントの経路損失計算を高速に行い、分散計算により大規模に拡張することができます。例えば、米国本土に散在する25,000台のトランシーバーのカバー領域を計算する場合、4メートルの解像度で、1000CPUコアを使用して、わずか1.5時間で完了することが可能です。

Google Earthの写真画質な3Dモデル(左上)と対応する電波障害物の高さを示したクラッタモデル(右上)。クラッタモデル(下)において、送信元から送信先までの建物と樹木を通る経路プロファイル。灰色は建物、緑色は樹木を表しています。

オートプランニングの入力

正確な範囲推定が可能になると、それを使ってネットワーク計画を最適化することができます。例えば、ネットワーク品質を最大化するために、何百もの新しい拠点をどこに配置するかを決定することができます。オートプランニングソルバーは、このような大規模な組合せ最適化問題に、高速かつ堅牢で規模拡大可能なアプローチで対応します。

正式には、オートプランニングの入力実体には、サービスを提供する需要点(通常は正方形の格子)、トランシーバの候補拠点、候補拠点から需要点までの予測信号強度(伝搬モデルを使用)、および予算枠が含まれます。各需要点には需要量(例えば、無線ユーザーの人口から推定)が含まれ、各拠点にはコストと容量が含まれます。特定の閾値以下の信号強度は省略されます。最後に、入力は、全体的な予算枠を含むことができます。

大規模インスタンスのデータを要約

オートプランニングの入力は、候補サイトの数(数万)、需要点の数(数十億)だけでなく、近くのすべての候補拠点からすべての需要点への信号強度を必要とするため、巨大になる可能性があります。

また、人口密度は地域によって大きく異なるため、単純にダウンサンプリングするだけでは不十分です。そこで、プライオリティ・サンプリングのような手法を適用してデータを縮小します。この手法では、ネットワークトラフィックと干渉統計の正確なビューを維持しながら、元のデータの低バイアス推定値を生成し、都市サイズの実体が1台のマシンのメモリに収まる程度に入力データを縮小することができます。

局所探索アルゴリズムを使った多目的最適化

組合せ最適化問題は依然として困難な課題であるため、私達はネットワーク品質を最適化するための本領域に特化した局所探索アルゴリズム(domain-specific local search algorithm)を開発しました。

局所探索アルゴリズムのパラダイムは、計算が困難な最適化問題を扱うために広く適用されています。このようなアルゴリズムは、局所的な小さな変化を適用することによって、候補解の探索空間内をある解から別の解へと移動し、時間制限または解が局所的に最適化された時点で停止します。候補ネットワークの品質を評価するために、次のセクションで説明するように、異なる目的関数を1つにまとめます。

現実のネットワークを扱う場合、局所最適に到達するまでの局所ステップ数、ステップごとに評価する候補の数、各候補の評価時間は、いずれも巨大になる可能性があります。数日ではなく数時間で終了する高品質なアルゴリズムを実現するためには、これらの各要素に対処する必要があります。

各候補の評価を高速に実施するためには、各需要点と候補ソリューションの中で最も強いシグナルを提供する拠点との間のマッピングを維持する動的なデータ構造が大きく寄与しています。この「最強信号(strongest-signal)」マップは、局所探索中に候補解が進化すると、効率的に更新されます。以下の考察により、収束までのステップ数とステップごとの評価数の両方を制限することができます。

候補地(左)と需要地(右)を表す2部グラフ
選択された拠点は赤丸で囲まれており、各需要点は利用可能な最も強い接続に割り当てられています。一番上の需要点には、到達可能な唯一の拠点が選択されないため、サービス提供がありません。上から3番目と4番目の需要点は、グレーの辺に付けられた信号強度が赤の辺に付けられた信号強度よりわずかに低い場合、高い干渉を受ける可能性があります。一番下の拠点は、多くの需要ポイントがそのサイトからサービスを得ているため、混雑度が高く、その容量を超えている可能性があります。