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

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

・近接したサイトは干渉を起こすため明示的に禁止して良い解決策へと探索を誘導している
・オートプランニングは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

近接した2つのサイトを選択することは、干渉を起こすため、通常理想的とは言えません。本アルゴリズムでは、このようなペアを明示的に禁止することで、より良い解決策へと探索を誘導し、ステップごとに考慮する移動の数を大幅に削減します。

私達は、禁止拠点同士を、それらがカバーする需要点に基づいて特定します。これは重み付きジャカード指数(weighted Jaccard index)によって測定されます。

これにより、単純な地理的距離よりも機能的な近接性をはるかによく捉える事ができ、特に電波伝搬が向きによる影響を受ける都市部や丘陵地において有効です。

また、ローカルサーチをエポックに分けることも有効です。最初のエポックでは、禁止ペアを避けながら、カバーエリアを広げるためにサイトを追加することがほとんどです。予算制限に近づくにつれ、干渉を微調整するために禁止ペア間の交換移動を含む2回目のエポックを開始します。この制限により、1ステップあたりの移動候補の数が制限され、より少ないカバー範囲の変化で干渉を改善するものに焦点が当てられるようになりました。

ローカルサーチの3つの候補
赤丸は選択された拠点、オレンジの辺は禁じられた組み合わせを示します

多様な解を出力

前述したように、オートプランニングは3つの競合する目的のバランスをとる必要があります。干渉と容量違反を最小限に抑えながら、予算の範囲でカバー範囲を最大化することです。

このため、本アルゴリズムでは、それぞれ重視した点が異なるネットワーク候補の小さなメニューを提供することで、最終決定をユーザーに委ねます。

各目的に対して乗数を適用し、その合計を最適化します。ある構成要素の乗数を上げると、その構成要素が強調されるようにアルゴリズムが誘導されます。乗数と予算のグリッドサーチを行い、多数の解を生成し、4つの要素(コストを含む)すべてにおいて他の解より悪いものをフィルタリングし、最終的に異なるトレードオフを表す小さなサブセットを選択します。

候補となる解決策のメニュー(1行に1つずつ、指標を表示)
解決策をクリックすると、選択した拠点がピンク色に変わり、カバー範囲と需要に渡る干渉分布のプロットが表示されます。選択されていない拠点は青色で表示されます。

おわりに

通信事業者が直面する最も困難な課題を解決するための私達の取り組みについて説明しました。私達は、組合せ数学の最適化問題と地理空間および電波伝搬モデリングを組み合わせて、ワイヤレス通信ネットワークのための規模拡大可能なオートプランナーを構築しました。私たちは、お客様のニーズに応えるために、これらの機能をどのように拡張していくかを積極的に検討しています。ご期待ください。

ご質問やお問い合わせは、wireless-network-interestまでメールでお願いします。

謝辞

これらの技術的進歩は、私達の共同研究者のたゆまぬ努力によって実現されたものです。Aaron Archer, Serge Barbosa Da Torre, Imad Fattouch, Danny Liberty, Pishoy Maksy, Zifei Tong, and Mat Varghese. Special thanks to Corinna Cortes, Mazin Gilbert, Rob Katcher, Michael Purdy, Bea Sebastian, Dave Vadasz, Josh Williams, および Aaron Yonas。
Serge、そして特にAaron Archerには、このブログ記事の執筆に協力してもらいました。