電波伝搬推定のための遺伝的アルゴリズムを用いたレイトレーシング処理の高速化法

(1)

電波伝搬推定のための遺伝的アルゴリズムを用いた

レイトレーシング処理の高速化法

今井

哲朗

†a)

Novel Ray-Tracing Acceleration Technique Employing Genetic Algorithm for

Radio Propagation Prediction

Tetsuro IMAI

†a)

あらましレイトレーシング法は，送信点から受信点に到達するレイを幾何学的にトレースするだけで様々な伝搬特性を一元的に推定できる魅力的な方法である．しかし，考慮すべき構造物が多く存在する伝搬環境においては，精度良く推定するために多くの演算処理を必要とする．したがって，以前より演算処理の高速化がレイトレーシング法の大きな課題の一つとされている．本論文では，生物が環境に合わせて進化する過程をモデル化した遺伝的アルゴリズムをレイトレーシング処理に適用することにより，演算精度を大きく損なうことなく処理の高速化が図れるレイトレーシング法を提案する．また，提案法のパフォーマンスを計算機シミュレーションにより明らかにする．キーワード電波伝搬推定，レイトレーシング法，遺伝的アルゴリズム，レイトレーシングの高速化法

1. まえがき

従来，携帯電話システムや無線LANのような無線システムの設計では，サービスエリアを把握するために電波の伝搬損推定が必須である．また，近年はシステムに適用する時空間信号処理技術の実伝搬路におけるパフォーマンスを評価するために，電波の伝搬遅延と到来方向（/出射方向）の特性も推定の対象となってきた[1], [2]．レイトレーシング法はこれらの伝搬特性を一元的に推定できる魅力的な方法である．レイトレーシング法では，送信点から放射される電波をレイ（Ray）とみなし，周辺構造物との相互作用（本論文では反射，透過，回折の総称）を経て受信点に到達するレイを幾何学的にトレース（Trace）する．受信点における伝搬の諸特性は，トレースした各々のレイの伝搬距離と到来角度（/出射角度）及び電界（複素振幅）を用いて求められる（詳細は文献[3]を参照）．ここで，レイトレーシング演算における精度と処理量 †_（株）_NTT_{ドコモ，横須賀市}

NTT DoCoMo, Inc., 3–5 Hikarino-oka, Yokosuka-shi, 239– 8536 Japan a) E-mail: imai@mlab.yrp.nttdocomo.co.jp はトレードオフの関係にある．すなわち，広範囲にわたる多くの構造物を対象に相互作用回数の上限値を高く設定してレイをトレースすれば，演算精度の向上とともに必要となる演算処理量も増大する．したがって，以前よりレイトレーシング処理の高速化は大きな課題の一つとされている．レイトレーシング処理を高速化するアプローチは大きく，1演算処理の効率化，2アルゴリズムの高速化，3演算処理の分散化の三つに分類できる．1のアプローチでは，これまでに得られている経験や知識より伝搬路モデルを仮定することにより“考慮する構造物の範囲”と“設定する相互作用回数の上限値”に制限を加える．伝搬路モデルが適切であれば演算精度の劣化を最小限に抑えつつ，大幅な演算量の削減が可能となる．例えば，市街地マクロセル環境の移動伝搬推定において効率良く三次元レイトレーシングを行うためのVertical Plane Launch（VPL）modelはこのアプローチに該当する[4], [5]．2のアプローチでは，イ

メージング法（Imaging method）やレイランチング法

（Ray-launching method）で代表されるレイのトレースアルゴリズムの高速化を図る．このアプローチは基本的に演算精度の劣化を伴わないが，レイトレーシン

(2)

グの前処理が必要となることが多い．このアプローチの例としては，Visibility Graphによるイメージング法[6]や三角グリッドによるレイランチング法[7]等が挙げられる．最後の3のアプローチでは，レイトレーシング演算をネットワークで接続した複数の計算機に分散させて並列処理する．このアプローチの場合，演算精度は劣化しない．また，ネットワーク容量による限界に達しない範囲であれば，トータルとしての演算速度は基本的に接続された計算機/CPUの数に比例する．実施例としては，例えば文献[8]を参照． 1 ∼3のアプローチにおいて，最も劇的な高速化の効果が期待できるのは1のアプローチである．ただし，既に述べたように，もととなる伝搬路モデルが事前に必要であり，これまでは主に実測によりモデルの構築と検証が行われてきた．また，伝搬路は電波が伝搬する環境（伝搬環境），例えば屋外であるか屋内であるかにより大きく異なる．したがって，伝搬路モデルは想定するすべての伝搬環境に対して用意する必要があり，一般的に困難である．しかし，視点を変えると，各々の伝搬環境に応じて適切な伝搬路モデルを自己組織化するようなアルゴリズムをレイトレーシング処理と組み合わせることができれば，極めて効果的な処理の高速化が実現できるといえる．本論文では伝搬路モデルを自己組織化するためのアルゴリズムとして，生物が環境に合わせて進化する過程をモデル化した遺伝的アルゴリズム（Genetic Algorithm: GA）に着目する[9], [10]．2.では遺伝的アルゴリズムをレイトレーシング処理に適用したGA レイトレーシング法を提案する．3.では，提案法の効果を計算機シミュレーションにより評価するための計算モデル，計算条件，評価方法について示す．4.では，計算機シミュレーションの結果より，提案法がレイトレーシング処理の高速化において極めて効果的であることを明らかにする．最後に5.で，まとめと今後の課題を述べる．

2. GA

レイトレーシング法

レイのトレースアルゴリズムには一般的にイメージング法とレイランチング法が知られており，これらは演算精度及び演算処理量においてそれぞれ異なった特徴をもつ[3], [8]．遺伝的アルゴリズムを各々のトレースアルゴリズムに対して適用することは可能であるが，本論文では送受信点間のレイを厳密にトレースすることができるイメージング法への適用法を提案する．図 1 面とエッジの組合せから設定されるレイパス Fig. 1 Ray-paths set up from combination of planes

and wedges. 2. 1 基本概念レイのトレースに送信点若しくは受信点の鏡像（イメージ）を用いるイメージング法では，まず図1に示すように，レイが送信点（Tx）から受信点（Rx）まで伝搬する経路（パス）を面とエッジの組合せから設定する．次に設定した各々のパスに対して相互作用を伴うポイントを幾何学的に探索することによりレイをトレースする．ここで，面/エッジの数をM，トレースするレイの相互作用の回数をNとすると，面とエッジの組合せとして設定されるパスの数NallはMNとなる．すなわち，N > 1の場合，考慮する面/エッジの数Mの増加に対してレイのトレース処理は非線形に激増することを意味する．ここで，一般的に，設定したMN 本のパスの中には“最終的にレイが存在せずに棄却されるパス”や“レイは存在するが受信特性に与える影響が極めて小さいパス”が数多く存在する．ただし，これらのパスを事前に判別することはできない．したがって，イメージング法は極めて演算効率の悪い方法といえる．提案法はGAを用いることによりトレースの対象パスを適切に制限し，演算効率を向上させることによりレイトレーシング処理の高速化を図る．なお，以降では，これまでの“考え得るすべての面/エッジに対してレイのトレースを行う”イメージング法を簡単に“従来法”と呼ぶこととする． 2. 2 基本モデル本節ではGAをイメージング法に基づくレイトレーシング処理に適用するためのモデルについて述べる．なお，本論文で基本とするGAは単純遺伝的アルゴリ

ズム（Simple Genetic Algorithm）である[9], [10]．

GAでは対応形質が異なる遺伝子の列で染色体を定

(3)

図 2 個体群モデル Fig. 2 Population model.

することにより各々の個体に多様性をもたせる．すなわち，個体は複数遺伝子の一つの組合せで表現され，その組合せ総数が表現可能な個体の種類となる．一方，2.1で述べたように，イメージング法ではレイのパスを面/エッジの組合せにより表現し，その組合せ総数がレイトレーシング処理対象の総パス数となる．このように，GAの個体表現とイメージング法のパス表現は極めて類似している．したがって，レイの1パスをGAの1個体とみなせば，一般的なGAの個体群のモデルはイメージング法のパラメータに容易に置き換えることが可能である．具体的には，図2に示すように，遺伝子を面/エッジに，染色体を設定パスの面/エッジの組合せに対応させて1個体を1パスとみなす．この場合，染色体のサイズはトレースするレイの相互作用の回数Nであり，各々の遺伝子がとり得る値は面/エッジの番号（m1∼mM，M：考慮する面/ エッジの総数）となる．また，個体群はパス群となるが，そのサイズ（1世代当りの個体数）Ncの上限値は Nall(= MN)となる．図2の個体群モデルを前提とする提案法の基本処理フローについて述べる．まず，Nall組の“考え得る面/エッジの組合せ”の中からランダムにNc組を選択し，それらを初期パス群（第一世代）として設定する．次に，各々のパスに対してレイのトレース及び電界計算を行う．ここで，提案法では各々の個体（パス）の適応度をトレースしたレイの受信電力で定義する．パスの適応度評価では，適応度によりソートした順序で各々のパスのラベルを振り直す．続いて，得られた結果があらかじめ設定した終了条件を満たすか否かを判定し，条件を満たしていない場合には，GA特有の“選択”，“交叉”，“突然変異”の操作に基づいてパス群の再設定（世代の更新）を行い，再設定したパス群に対してレイのトレースを行う．以上を終了条件が満たされるまで繰り返し，条件を満たした場合には，所望の伝搬特性（トータルの受信電力，遅延スプレッドなど）を算出して処理を終了する．なお，GAでは，世代を重ねる過程で，既に適応度を計算した個体が幾度も発現する．適応度計算の処理負荷が軽い場合にはそのたびに適応度を再計算してもよいが，処理負荷が重い場合にはこの再計算がトータルの演算速度に与える影響を無視することができない．提案法では処理負荷が極めて重い“レイのトレース処理”が適応度計算に含まれる．したがって，提案法を実際にコーディングする場合には，既に受信電力を計算したパスは再計算を行わないように，パスの計算情報（トレースしたレイの受信電力，伝搬距離など）を一時的にメモリに記憶させ，必要に応じて情報を抽出するようにした方が理想的/効率的である． “初期パス群の設定”と“パス群の再設定”において，提案法では次のルールに従ってパスを設定/再設定する． • ルール1：同一の面/エッジが連続する組合せは対象外 • ルール2：面/エッジの組合せが同一となるパスはパス群において唯一 “同一の面/エッジが連続する組合せ”，例えば，図1 に示す“Tx→ m1 → m1 → · · · →Rx”の組合せはレイを明らかにトレースできない．ルール1はこのような組合せのレイトレーシング処理をあらかじめ避けるためのものである．なお，ルール1を適用した場合の組合せ総数はM (M− 1)N−1となる．一方，ルール2 はパス群の中に同一経路（面/エッジの組合せ）をもつパスが増殖することを避けるためのものである．終了条件は演算精度と演算処理量を決定する重要な要因である．その条件には様々な方法が考えられるが，本論文では次式で定義する演算率ρを終了条件の指標とする． ρ = 1 Nall

i Ncal(i) (1) ただし，N_cal(i)は第i世代において初めてパス群の中に発現し，適応度を計算したパスの数．ユーザはあらかじめ演算率のしきい値ρth（ただし，0≤ ρth≤ 1の実数）を定めておき，演算は実際の演算率がこのしきい値を超えた時点で終了させる．演算率を用いることの利点は，“イメージング法の対象パスを制限するこ

(4)

図 3 連鎖モデル Fig. 3 Chain model.

とでレイトレーシング処理量の削減を図る”ことを目的とする提案法のパフォーマンスを直接的に評価できることにある．例えば，演算率がρであった場合，提案法の演算量（ただし，レイのトレース処理のみ）は，従来法における演算量のρ倍であるといえる． 2. 3 連鎖モデル本節では，多くの受信点を面的に配置した場合の計算，いわゆるエリア計算を前提とした場合のGA適用モデルについて述べる． GAのパフォーマンスは初期に設定する個体群に大きく依存する．すなわち，適切な個体群を初期に設定することができれば，少ない演算率で高い演算精度を得ることができる．しかし，一般的に適切な個体群を初期に見つけることは困難である．ところで，今，従来法を用いて二つの受信点Aと Bに対してレイのトレーシングを実行した場合を考える．2点間の距離が遠く離れている場合には受信点A と受信点Bにてトレースされるレイのパス（ここでは，面/エッジの組合せ）は大きく異なる．しかし，この距離を短くしていくと両受信点のレイパスには同一のものが多く含まれるようになり，最終的には完全に一致する．これは，“2点間の距離が短く”かつ“受信点Aの演算が既に終了”している場合，提案するGA レイトレーシング法においては“受信点Aの最終パス群が受信点Bの良好な初期パス群になり得る”ことを意味する．以上の考えをもとに，複数の受信点を連鎖的に計算するモデルが次に提案する連鎖モデルである．連鎖モデルについて図3を用いて具体的に説明する．本モデルでは，まず，計算エリア内にある受信点に対して，隣り合う受信点間距離∆rが互いに短くなるように演算順序を設定する（コース設定）．次に，受信点を • 初期化受信点Rx0：初期パス群を基本モデルに従ってランダムに設定する受信点 • 通常受信点Rx：初期パス群を隣接の受信点（演算コースにおいて一つ前の受信点）にて演算した結果を設定する受信点の2種類に分ける．ここで，∆R (≥ ∆r)は初期化受信点間の距離であり，∆R = ∆rと設定した場合にはすべてが初期化受信点となり，∆R =∞と設定した場合にはスタート点を除いてすべてが通常受信点となる．なお，すべてが初期化受信点となることは，連鎖モデルが適用されないことを意味する．また，図3において，ρ(0)_th とρthはそれぞれ初期化受信点及び通常受信点において設定する演算率のしきい値であり，基本的にρ(0)_th > ρthとなるように設定する．最後に，連鎖モデルを適用した際のGAレイトレーシング法の処理フローを図4に示す．

3. 計算機シミュレーション

本章では，提案するGAレイトレーシング法のパフォーマンスを計算機シミュレーションにより評価するための計算モデル，計算条件，評価方法について述べる． 3. 1 計算モデル本論文では提案法を容易に効率良く評価するため，図5に示す水平面内二次元モデルを用いる．構造物はすべて水平面に垂直な壁面（高さ：無限大，厚み：

(5)

図 4 連鎖モデルを適用した提案法の処理フロー Fig. 4 Flow of proposed method with chain model.

なし，幅：有限）であるとし，本モデルではそれらを 2 km× 2 kmの計算エリア内に複数配置する．ただし，壁面の位置と向きはともにランダムとする．また，本モデルで定義する壁面は一つの面と二つのエッジ（水平面に垂直で長さが高さ方向に無限）で構成されるものとする．したがって，M0個の構造物を配置した場合の面/エッジの総数Mは3M0である．送信点Txは図 5に示す座標（0，−500 m）の位置に固定とする．また，受信点は，その位置がP1 1：（0，500 m）に固定，P2 2：P1 から距離∆rの円周上，P3 3：設定するコース上に位置する場合の3種類とする．P1は提案法の基本モデルの適用効果を評価する場合に使用し，P2とP3は特に連鎖モデルの適用効果を評価する場合に使用する． 3. 2 計算条件表 1に計算条件を示す．考慮する構造物（壁面）図 5 計算モデル Fig. 5Calculation model.

は材質をコンクリート（比誘電率：6.76，導電率： 0.0023 S/m），幅を30 mとし，配置する数M0は10∼ 300とした（面/エッジの総数Mは30∼900）．トレースの対象は，最大透過回数：∞で反射/回折の回数N が2となるレイとする．ただし，本シミュレーションでは“同一の壁面内で反射/回折を連続して繰り返す組合せ”は2.2で述べたルール1に加えてトレースの対象外とする．レイの受信電力は，周波数を2 GHz， 1回当りの透過損を10 dBとし，反射係数と回折係数の計算にそれぞれ2層媒質におけるフレネル反射係数

及びUTD（Uniform Theory of Diﬀraction）を用いることにより求めるとする．なお，フレネル反射係数とUTDの詳細は付録参照．次にGAに関する条件について述べる．パス群のサイズNcは面/エッジの総数M 及び反射/回折数 N (= 2)に応じて大きく設定すべきであると考え，本シミュレーションではNc= 2M Nとする．ただし，最小サイズは100とする．次世代の生成は連続世代型であるエリート保存方式とする[9], [10]．具体的には，前世代の中から適応度の高いNc/3をエリートとして選択し，これらは無条件に次世代に残す．残りの2/3Nc はランダムに選ばれたエリートのペア間で1点交叉（交叉位置はランダム），突然変異（確率Pm= 0.01）

(6)

表 1 計算条件 Table 1 Calculation conditions.

により生成する．終了条件には2.2で述べた演算率ρ を使用する．ただし，前述したように，本シミュレーションではルール1に加えて“同一の壁面内で反射/ 回折を連続して繰り返す組合せ”も対象外としていることから，式(1)における総パス数Nallは， Nall= 3M0(3M0− 3)N−1 = M (M− 3)N−1 (2) となる．また，適応度の高いNc/3をエリートとして選択するエリート保存方式を用いて次世代を生成する場合，“設定する演算率しきい値ρth”と“演算が終了した時点の演算率ρ”の関係は

ρth≤ ρ < ρth+ ∆ρ, ρth> ρmin ρ = ρmin, otherwise (3) と表せる．ただし，ρminは第一世代（初期世代）終了時点の演算率，∆ρは第i世代において初めて演算を行うパスの総パス数に対する割合であり， ρmin= Nc Nall, ∆ρ = 2 3 Nc Nall (4) で与えられる．更に，式(2)と表1の計算条件を考慮すると，ρmin= 4/(M− 3)，∆ρ = 8/{3(M − 3)}となる． 3. 3 評価方法評価指標は互いにトレードオフの関係にある“演算量”と“演算精度”とし，いずれも従来法による結果を基準とする．提案法の演算は大きく，レイトレーシング演算（レイのトレース及び電界計算）とパス群の再設定演算（GA特有の“選択”，“交叉”，“突然変異”の操作に基づく演算）に分けられる．ここで，レイトレーシング演算は共通であることから，この処理量は従来法と提案法の間で容易に比較することができる．一方，パス群再設定演算は提案法固有のものであり，その処理量はプログラムを作成する際のコーディングに大きく依存する．したがって，トータルの演算処理量に対して従来法と提案法を正当にかつ一般化して比較することは困難である．そこで，本論文では“パス群再設定演算はレイトレーシング演算よりも十分に処理負荷が軽い”と仮定する．すなわち，演算量は式(1)で定義した演算率で評価する．演算精度は従来法の値を真とする受信電力の演算誤差として評価する．すなわち，従来法による受信電力をP0[dB]，提案法による受信電力をP [dB]とすると，演算誤差Perr[dB]は Perr= P− P0 (5) で与えられる．ここで，本論文では受信電力をトレースして得られたレイの電力加算値で定義する．したがって，パス数を制限している提案法の演算誤差Perr は必ず負の値となる．なお，以降では演算誤差の絶対値|Perr|を特に“絶対誤差Err”と呼ぶ．ところで，提案法の絶対誤差は設定する演算率しき

(7)

い値が大きいほど，すなわち，パス群の再設定回数が多いほど小さくなる．したがって，基本モデルのみに基づく提案法の絶対誤差Errは，初期パス群に対する誤差Err0とパス群の再設定による演算精度の改善量f (ρth)を用いて， Err = Err0− f(ρth) (6) と表せる．なお，0 < Err ≤ Err0であることから， 0≤ f(ρth) < Err0である．更に，連鎖モデルを提案法に適用すると，初期化受信点から第i番目となる通常受信点の絶対誤差Err(i) は， Err(i)=

Err0− f0

ρ(0)_th

, i = 0 Err(i−1)+ gi(∆r)− fi(ρth), i≥ 1 =Err0−f0

ρ(0)_th

+ i

j=1 {gj(∆r)−fj(ρth)} (7) と表せる．ただし，fi(ρth)とgi(∆r)はそれぞれ第i 番目受信点における“パス群の再設定による演算精度の改善量”と“第(i− 1)番目受信点と距離が∆r離れていることによる絶対誤差の増加量”である．ここで，“Err(i−1)+ gi(∆r)”は初期パス群として設定した第(i− 1)番目受信点の最終パス群に対する絶対誤差であり，その値は平均的にErr0以下となる．したがって，初期段階における絶対誤差が小さいことから，第i番目受信点において同一の演算率しきい値ρthを設定した場合には連鎖モデルを適用した方が絶対誤差 Err(i)は小さくなると期待できる．また，第i番目受信点の第(i− 1)番目受信点に対する絶対誤差の増加量∆Err(i) は式(7)より，

∆Err(i)= Err(i)− Err(i−1)

= gi(∆r)− fi(ρth) (8) と表せる．この式より明らかなように，連鎖モデル適用時の絶対誤差は，受信点の移動に伴い，∆Err1 (i) < 0 (i = 1, 2,· · ·)の場合には次第に小さくなり，逆に 2 ∆Err(i)_{> 0 (i = 1, 2,}_{· · ·)}_{の場合には累積的に増} 加することとなる．

4. シミュレーション結果

4. 1 基本モデルの適用効果まず，基本モデルの適用効果，すなわち“イメージ図 6 演算率しきい値と演算誤差の関係 Fig. 6 Relationship between threshold value of

calculation rate,_ρth, and calculation error.

ング法にGAを適用することによる基本的な効果”について明らかにする．なお，受信点はP1の1点のみとした．図6はM0 = 5 0として，式(6)に示す演算率しきい値ρthと演算誤差Perr(=−Err)との関係を評価した結果である．ただし，演算誤差は壁面の配置を100 通り変更して得られた平均値である．また，図には，考え得るパスの中から(ρth× Nall)本のパスをランダムに選択した場合の結果をランダム法として併せて示してある．図より，演算率が同一であれば提案法はランダム法に比べて常に絶対誤差が小さくなることが分かる．このランダム法との差分がGAを用いることによる演算利得といえる．この演算利得は設定する演算率しきい値が小さいほど大きい．例えば，ρth= 0.5 の場合に演算利得は約2 dBであるが，ρth= 0.2の場合には約7 dBとなる．また，これらの見方を変えると，許容誤差に対する演算量の削減効果を評価することができる．例えば，許容する絶対誤差を4 dBとすれば，ランダム法の演算削減率は5割（ρth= 0.5より）であるのに対して，提案法では8割（ρth= 0.2 より）となる．図7はρth= 0.2とした場合の壁面数M0と演算誤差Perr(=−Err)との関係である．ただし，演算誤差は壁面配置を100通り変更して得た平均値である．この結果より，ランダム法の絶対誤差は壁面数によらずほぼ一定であるのに対して，提案法では壁面数が多い

(8)

図 7 壁面数と演算誤差の関係

Fig. 7 Relationship between the number of walls,

M0, and calculation error.

ほど絶対誤差が小さくなることが分かる．換言すれば，演算利得が大きくなる．これは，壁面数（面/エッジの総数）が増えた場合，“受信電力に影響を与えるパスの数は総パス数Nallと同程度に増加する”が，“それらのパスを構成する面とエッジの種類はそれほど増えない”ことを意味する．すなわち，受信電力が大きなレイは比較的限られた面/エッジで反射/回折を伴う．このような場合には積み木仮説（詳しくは文献[9], [10] を参照のこと）を前提とするGAが特に効果的に動作するため，提案法の演算利得が大きくなったと考える． 4. 2 連鎖モデルの適用効果（1）最終パス群の参照効果初期化受信点と通常受信点がともに1点である場合のシミュレーション結果から，連鎖モデルの基本となる“隣接する受信点において既に得られている最終パス群を参照”することによる効果について明らかにする．ただし，計算モデルと計算条件は図5と表1に同じとし，通常受信点と初期化受信点の位置はそれぞれ P1及びP2とした．なお，以下に示す結果は，壁面の位置と向きに加えて初期化受信点の円周上位置も併せてランダムに100通り変更し，得られた値を平均化したものである．まず，初期化受信点（i = 0の受信点）からの距離∆r と通常受信点（i = 1の受信点）の演算誤差(−Err(1)) との関係を図8に示す．ただし，演算率しきい値は (ρ(0)_th, ρth) = (1, 0)としていることから，Err(0)= 0 図 8 受信点間距離と演算誤差の関係 Fig. 8 Relationship between distance, ∆r, and

calculation error. 及びf1(0) = 0である．すなわち，Err(1)= g1(∆r) であることから，図8はGAの演算と全く無関係な，距離のみに依存する誤差成分g1(∆r)の特性を示している．∆r = 0の場合，両受信点は完全に一致していることからg1(∆r) = 0である．しかし，初期化受信点からの距離∆rが長くなると，2点間の伝搬環境に相違が生じてくることからg1(∆r2) > g1(∆r1)（ただし，∆r2> ∆r1）となる．また，∆r > 100 mの領域では∆rが長いほどM0= 10と50の結果に大きな差が生じる．これは，2点間の伝搬環境の相違が，受信点間距離∆rに加えて構造物の配置（構造物のエリア内密度）にも依存するためと考える．そこで，本論文では，距離が∆rだけ離れた場合に生じる伝搬環境の変化量ηを η =

∆r A/M0 (9) で仮定する．ただし，Aは構造物（壁面）を配置した領域の面積である．したがって，

(A/M0)は壁面を配置した平均的な間隔を表し，伝搬環境の変化量ηはこの配置間隔で規格化した2点間距離を意味する．図8 の横軸をηに変更した結果を図9に示す．ただし，A は図5に示したように2 km× 2 kmである．図9より，η≤ 0.3である受信点を初期化受信点として結果を参照すれば，絶対誤差g1(∆r)は1 dB以下に抑えられることが分かる．なお，同図においてM0 = 10と

(9)

図 9 平均壁面配置間隔で規格化した受信点間距離と演算誤差の関係

Fig. 9 Relationship between distance normalized by average interval of structure position,_{η, and} calculation error. 50の演算誤差がほぼ一致していることから，式(9)の仮定は妥当であるといえる．また，式(8)よりη = 0.3 を与える受信点間距離∆rは，M0 = 10の場合：約 190 m，M0= 5 0の場合：約85mと求められる．次に初期化受信点と通常受信点の演算率の関係を図10に示す．横軸は初期化受信点において設定する演算率しきい値ρ(0)_th であり，縦軸は通常受信点において絶対誤差の許容値Err(target)= 3 dBを得るために必要な最小の演算率しきい値ρthである．なお，ρthの値は二分法[11]を用いて求めている．また，M0= 10， 20，50における最小演算率ρminは式(4)よりそれぞれ0.15，0.07，0.03であり，この値以下にしきい値を設定した場合には実効的にGAは動作しない．図 10 では値ρ(0)_th ≤ ρmin若しくはρth≤ ρminとなる領域にハッチングを掛けている．また，図に示す曲線は，特性を容易に評価できるように次のシグモイド関数より非線形回帰した結果である． ρth= a + b 1 + exp

c

ρ(0)_th + d

(10) ただし，a，b，c，dは回帰により決定されるパラメータである．図10より，ρ(0)_th を大きく設定することにより通常受信点で必要とされるρthは小さくなることが分かる．これは，通常受信点におけるρthの演算に伴う精度の改善量f1(ρth)が式(7)より， f1(ρth) =−f0

ρ(0)_th

+ g1(∆r) + Const

Const = Err0− Err(target) (11)

で与えられることによる．また，∆r = 10，100 mの場合ではρ(0)_th →1（この場合，f0(1) Err0）とすればρth≤ ρminにまで小さく抑えることが可能であるが，∆r = 1000 mの場合ではρ(0)_th →1としてもρth はρminよりも値が大きな下限値をもってしまう．例えば，M0= 5 0の場合の下限値は約0.2である．これは図8に示した特性と密接な関係にある．M0 = 5 0 の場合，図8において受信点間距離∆r = 10，100， 1000 mに対応する絶対誤差はそれぞれ0.4，1，5dB であった．したがって，∆r = 1000 mではρ(0)th →1 としても通常受信点の絶対誤差を5dBから3 dBにするためにρth= 0.2に相当する演算が必要である．以上より，g1(∆r) > Err(target)の場合には，ρthよりも値が大きな下限値をもつこととなる． ∆rとρ(0)th を一定として壁面数M0 を変化させた場合，図 10において壁面数M0が少ないほど所要の演算率しきい値ρthは大きくなっている．これは， M0≤ 50の領域において壁面数を減少させると，距離に依存する誤差成分g1(∆r)は図8に示すように小さくなるものの，それ以上に初期化受信点における絶対誤差Err(0)(= Err0− f0(ρ(0)_th))が図7に示すように大きくなるためである．以上が初期パス群の設定に隣接する受信点の最終パス群を参照することによる効果である．本方法は初期パス群をランダムに設定する場合と比べて， • 演算率が同じであれば演算精度の向上 • 許容誤差が同じであれば演算量の削減に極めて効果的であるといえる．また，受信点間の環境変化が小さく，かつ隣接受信点で得られている演算精度が高いほど，その効果は大きい．（2）連鎖による効果 “最終パス群の参照”を複数受信点で連鎖させることによる効果についてシミュレーションより明らかにする．計算モデルと計算条件は図5と表 1に同じである．ただし，壁面数はM0= 5 0とした．なお，壁面の位置と向きは図5に示すとおりである．演算コースは座標(−1000 m，−1000 m)をスタート点として図5に示すようにY 軸に対して蛇行するように設定した．詳しくは，コース上においてスタート点から第

(10)

(a) M₀=10 (b) M₀=20

(c) M₀=50

図 10 初期化受信点と通常受信点の演算率しきい値の関係

Fig. 10 Relationship between threshold values of calculation rate at initialized point P2and at normal point P1.

i番目(i = 0, 1,· · · , 40400)となる受信点の座標(xi, yi)は， xi =

−1000 + ∆r · j if k is even 1000− ∆r · j else yi = −1000 + ∆r · k (12a) ただし， j = i mod (2000/∆r + 1) k = [i/(2000/∆r + 1)] (12b) と定義した．なお，式(12b)において，[j]はjを超えない最大の整数を表すガウス記号である．また，本シミュレーションでは受信点間距離∆rは10 mとした．なお，受信点の総数は40401ポイントであり，受信点の1ステップの移動に対する伝搬環境の変化量ηは式 (9)より0.035である．また，∆R =∞（初期化受信点はスタート点のみ）としている．まず，連鎖モデル適用による誤差の距離特性を図11 に示す．スタート点では演算率しきい値をρ(0)_th = 0.01

(11)

図 11 連鎖モデルの適用効果 Fig. 11 Eﬀect of proposed chain model.

表 2 演算率しきい値ρthと世代数Ngeの関係 Table 2 Relationship between threshold value of

cal-culation rate, ρth and generation times,

Nge. （< ρmin）と設定したことから絶対誤差は22 dBと極めて大きい．しかし，その後の受信点においては演算率しきい値ρthがたかだか0.03であっても，受信点の移動に伴い絶対誤差は次第に減少する．これは，式(8) の絶対誤差の増加量∆Err(i)が計算エリア内において平均的に負の値になり，連鎖モデルの効果が有効に機能していることを意味する．また，絶対誤差がほぼ 0 dBとなるのは，ρth= 0.03，0.05，0.1，0.2に対してそれぞれスタート点から230，140，90，30 mの距離である．ここで，1受信点の演算に必要となる世代数Nge（ただし，平均値）と設定する演算率しきい値 ρthは表2の関係にある．したがって，図3，図4に示したように“通常受信点における初期パス群は前受信点の最終パス群と同一”であることを考慮，すなわち“通常受信点における初期パス群の世代は前受信点の最終世代と同世代である”と考えれば，ρth= 0.03 の場合には23世代（10 m進むごとに一つ世代が変わることより）をかけて絶対誤差をほぼ0 dBにしたと図 12 連鎖モデル適用時における通常受信点の演算率しきい値と演算誤差の関係

Fig. 12 Cumulative probability of calculation error with threshold value of calculation rate at normal point as a parameter when applying chain model. いえる．なお，受信点の移動とともに伝搬環境が急激に変化することにより，例えば図11の1や2のポイントのように絶対誤差が前受信点よりも増大する場合もある．このような場合においても，連鎖モデルが適用されていれば絶対誤差は再び減少に向かうことが図11より分かる．図11と同一の設定でコース終点まで演算を実効した結果を誤差の累積分布で図12に示す．なお，図12 には比較のために連鎖モデルを適用しない，すなわち各々の受信点を個別に演算した場合（ただし，演算率しきい値はρth= 0.2）の結果も併せて示してある．図より，(ρ(0)_th，ρth) = (0.01, 0.03)であっても絶対誤差の累積50%値は約1 dBと極めて小さいことが分かる．換言すれば，許容する絶対誤差を1 dBとすれば97%もの演算量が削減可能となる．一方，演算量がほぼ同一とみなせる個別演算（ρth= 0.2，without chain model）と(ρ(0)_th, ρth) = (0.01, 0.2)の結果を比較すると，演算量が同じであれば連鎖モデルの効果により演算精度を大幅に改善できることが分かる．次に，スタート点（初期化受信点）の演算精度がエリア全体に与える影響について述べる．スタート点の演算率しきい値ρ(0)_th をパラメータとし，コース終点まで演算を実行した結果を誤差の累積分布で図13に示す．ただし，ρth= 0.01 < ρminと設定したことから，

(12)

図 13 連鎖モデル適用時におけるスタート点（初期化受信点）の演算率しきい値と演算誤差の関係 Fig. 13 Cumulative probability of calculation error

with threshold value of calculation rate at start (or initialized) point as a parameter when applying the chain model.

通常受信点においてGAは実効的に動作していない．

また，比較のため図12と同様に個別演算（ρth= 0.2，

without chain model）の結果も併せて示してある．個別演算（ρth= 0.2，without chain model）よりも

誤差は大きいものの，ρ(0)_th を大きく設定してスタート点の演算精度を向上させるとエリア全体の精度も確実に向上している．これは，図8，図9において示したように，スタート点の演算精度が高ければその周辺に存在する受信点の演算精度も向上するためである．以上，初期化受信点と通常受信点の演算率しきい値を適切に組み合わせて設定すれば，少ない演算で演算誤差を大幅に改善することが可能といえる．（3）初期化による効果前述したように，連鎖モデルを適用すれば受信点の移動とともに絶対誤差を減少させて0 dBに近づけることが可能である．しかし，設定する演算率しきい値 ρthが適切な値よりも小さい場合，この絶対誤差の減少速度は図11に示したように遅くなる．特に突発的な環境の変化が頻繁に生じるような場合，絶対誤差は十分に減少する前に再び増加してしまい，結果としてエリア全体の演算精度は悪くなる．このような場合には初期化受信点（ただし，ρ(0)_th ρthに設定）の複数配置が効果的であると考える．そこで，最後に，初期 (a) ∆R = ∞ (b) ∆R = 100 m 図 14 連鎖モデルにおける初期化の効果 Fig. 14 Eﬀect of initialization in chain model.

化受信点を複数配置することによる効果について示す．図14はρ(0)_th = 0.5とし，∆Rを∞または100 m とした結果である．ただし，他のすべての条件（計算モデル，計算条件，演算コースなど）は図12，図13 に同じである．図14より，∆R = 100 mとすることでエリア内の演算精度は向上することが分かる．ただし，当然のことながら，通常受信点の演算率しきい値ρthが大きくなるとその効果は小さくなる．また， ρ(0)_th ρthと設定することから，エリア内における初期化受信点の割合が増えると演算量も同様に増加する．

(13)

表 3 シミュレーション結果の比較 Table 3 Comparison of simulation results.

したがって，初期化受信点を複数配置する場合にはこれらに十分留意する必要がある．図12，図14に示した主な結果の演算率と演算誤差をまとめて表3に示す．連鎖モデルを適用することにより，少ない演算で演算誤差を大幅に改善できる．例えば，(∆R, ρ(0)_th, ρth) = (∞, 0.5 , 0.05)の設定は従来法に対したかだか6%の演算量で絶対誤差（平均値）： 1.23 dBを実現できる．参考のため，計算エリア内における受信電力の分布を図15に示す．ただし，図15(a)：従来法の結果（本論文の定義より，演算誤差を求める際の基準となる結果），図15(b)：個別演算（ρth= 0.2，

without chain model）の結果，図15(c)：連鎖モデル(∆R =∞, ρ(0)_th = 0.5, ρth= 0.05)の適用結果である．この結果からも連鎖モデルの有効性は明らかである．ただし，一方で，図15(c)の例えば範囲Aで示した部分から，連鎖モデルが環境の変化に対して十分に追従できていない場所が少なからず存在していることもうかがえる．

5. むすび

本論文では，レイトレーシング法を用いた伝搬推定において，演算精度を損なうことなく演算処理の高速化が図れる“GAレイトレーシング法”を提案した．本方法では，イメージング法に基づくレイトレース処理に遺伝的アルゴリズムを適用することにより効率良く演算処理量を削減する．また，水平面内二次元モデルを用いたシミュレーションよりGAレイトレーシング法のパフォーマンスを評価し，得られた主な結果は以下のとおりである． • 推定すべき受信点が1点である場合，従来の 20%の演算処理量で誤差は平均4 dB程度． • 推定すべき受信点が複数である場合，従来の 6%の演算処理量で誤差は平均1 dB程度．ただし，計算モデルにおいて設定した壁面の数は50 であり，トレースしたレイの反射/回折回数は2回である．レイトレーシング処理を高速化するアプローチは大きく，1演算処理の効率化，2アルゴリズムの高速化， 3 演算処理の分散化の三つに分類でき，提案法は1のアプローチに属する．ここで，これらのアプローチは互いに排他的な関係にはない．したがって，提案法は他のアプローチ（2と3）による高速化法（ただし，イメージング法を前提）と効果的に組み合わせることが可能である．また，十分な効果が得られない可能性はあるが，1のアプローチに属する高速化法（ただし，イメージング法を前提）とも基本的には組み合わせることができる．これらを考慮しつつ，より実際的な伝搬推定システムへの提案法の実装方法及びその効果を検討することが今後の主な課題である．また，遺伝的アルゴリズムはレイランチング法に基づくレイトレース処理にも適用可能である．レイランチング法の演算精度と演算処理量はレイの出射本数に大きく依存する．

(14)

(a) Conventional ray-tracing method using imaging method

(b) Proposed ray-tracing method without chain model (_ρth= 0_.2)

(c) Proposed ray-tracing method with chain model (∆R = ∞, ρ(0)_th = 0.5, ρth= 0.05)

図 15 受信電力分布による比較

Fig. 15Comparison of calculated received power distributions. したがって，遺伝的アルゴリズムによりレイを効果的な方向に適切な数で出射させることができれば，演算精度を損なうことなく処理の高速化が期待できる．前述の課題と併せて検討していきたい．文献

[1] A. Paulraj and B.C. Ng, “Space-time modems for wireless personal communications,” IEEE Pers. Com-mun., pp.36–48, Feb. 1998.

[2] R.B. Ertel, P. Cardieri, K.W. Sowerby, T.S. Rappaport, and J.H. Reed, “Overview of spatial channel models for antenna array communication sys-tems,” IEEE Pers. Commun., pp.10–22, Feb. 1998. [3] 細矢良雄（監修），電波伝搬ハンドブック，第 2 部，第 15

章，リアライズ社，1999.

[4] G. Liang and H.L. Bertoni, “A new approach to 3-D ray tracing for propagation prediction in cities,” IEEE Trans. Antennas Propag., vol.46, no.6, pp.853– 863, June 1998.

[5] J. Rossi and Y. Gabillet, “A mixed ray launch-ing/tracing method for full 3-D UHF propagation modeling and comparison with wide-band measure-ments,” IEEE Trans. Antennas Propag., vol.50, no.4, pp.517–523, April 2002.

[6] F. Agelet, A. Formella, J. Rabanos, F. Vicente, and F. Fontan, “Eﬃcient ray-tracing acceleration tech-niques for radio propagation modeling,” IEEE Trans. Veh. Technol., vol.49, no.6, pp.2089–2104, Nov. 2000. [7] Z. Yun, Z. Zhang, and M. Iskander, “A ray-tracing method based on the triangular grid approach and application to propagation prediction in urban envi-ronments,” IEEE Trans. Antennas Propag., vol.50, no.5, pp.750–758, May 2002.

[8] 今井哲朗，角誠，多賀登喜雄，“レイトレーシング法を用いた市街地マクロセル伝搬推定システム，” NTT DoCoMo テクニカル・ジャーナル，vol.12, no.1, pp.41–49, April 2004.

[9] メラニーミッチェル，遺伝的アルゴリズムの方法，東京電機大学出版局，1997.

[10] 萩原将文，ニューロ・ファジイ・遺伝的アルゴリズム，産業図書，1994.

[11] W.H. Press, B.P. Flannery, S.A. Teukolsky, and W.T. Vetterling, Numerical Recipes in C [日本語版]，技術評論社，1993.

[12] 安達三郎，電磁波工学，コロナ社，1983.

[13] R.G. Kouyoumjian and P.H. Pathak, “A uniform geometrical theory of diﬀraction for an edge in a perfectly conducting surface,” Proc. IEEE, vol.62, pp.1448–1461, Nov. 1974.

[14] W.D. Burnside and K.W. Burgener, “High frequency scattering by a thin lossless dielectric slab,” IEEE Trans. Antennas Propag., vol.AP-31, no.1, pp.104– 110, Jan. 1983.

[15] K.A. Chamberlin and R.J. Luebbers, “An evaluation of longley-rice and GTD propagation models,” IEEE

(15)

Trans. Antennas Propag., vol.AP-30, no.6, pp.1093– 1098, Nov. 1982.

[16] R.J. Luebbers, “Finite conductivity uniform GTD versus knife edge diﬀraction in prediction of prop-agation path loss,” IEEE Trans. Antennas Propag., vol.AP-32, no.1, pp.70–76, Jan. 1984.

付

録

1. 反射係数図A· 1は2層媒質におけるフレネルの反射係数を説明するためのモデルである．媒質定数εi, µi, σiの均質な媒質iから，境界が平面で異なった媒質定数εj, µj, σjの半無限媒質jへ平面波が入射する場合のフレネルの反射係数r_||（TM入射），r⊥（TE入射）は，入射角をθiとすれば次式で与えられる[12]． r_||=µin 2 ijcos θi− µj

n2 ij− sin2θi µin2 ijcos θi+ µj

n2 ij− sin2θi (A·1a) r⊥=µjcos θi− µi

n2 ij− sin2θi µjcos θi+ µi

n2 ij− sin2θi (A·1b) ここで，nijは次式で表される媒質iに対する媒質j の比複素屈折率である． nij=

µj µi

εj− jσj/ω εi− jσi/ω (A·2) ただし，ωは入射波の角周波数である． 2. 回折係数図A· 2は，形状が楔（ウェッジ）である構造物に電波が斜め入射する場合の回折係数を計算するためのモデルである．図において，“0”faceと“n”faceはそれぞれ電波が入射する側と回折する側の楔の面であり，β とβはそれぞれ入射波及び回折波と楔のエッジの接線方向とのなす角であり，φ とφは楔に垂直な面に射影した入射波及び回折波の“0”faceとのなす角であり，(2− n)πは“0”faceと“n”faceのなす角図 A· 1 反射モデル

Fig. A_{· 1 Reﬂection model.}

である．またsとsはそれぞれ送信点から回折点ま

での距離及び回折点から受信点までの距離である．これらのパラメータを用いた回折係数の具体的な計算方法を以下に示す．なお，この方法は，一般的な完全導体におけるUTD（Uniform Geometrical Theory of Diﬀraction）[13]を，文献[14], [15]の結果より導電率が有限な媒体に適用できるように拡張された，文献[16]による回折係数の計算法である．回折係数は次のダイアディックで与えられる． ˜ D =− ˆβ· ˆβ Ds− ˆφ· ˆφDh (A·3) ここで，βˆとβˆ及びφˆとφˆはそれぞれ図に示す角度 βとβ及びφとφの単位ベクトルである．また，Ds とDhは以下で与えられる． Ds,h = −e −jπ/4 2n√2πk sin β

cot

π + (φ− φ) 2n

×F

kLa+

φ− φ

+ cot

π−(φ−φ) 2n

F

kLa−

φ−φ

+r(0)cot

π−(φ+φ) 2n

F

kLa−

φ+φ

+r(n)cot

π + (φ + φ) 2n

×F

kLa+

φ + φ

(A·4) 上式においてF (・)は次式で示すフレネル積分を表す．図 A· 2 回折モデル

(16)

F (x) = 2j√xejx

_∞ √_x e −jτ2_dτ _(A_·5) また，L及びa±(·)は以下で与えられる． L = ss s + ssin 2 β (A·6) a±(µ) = 2 cos2

2nπN±−µ 2

, µ = φ± φ(A·7) ここで，N±は次式を満足する値に最も近い整数である． 2nπN±− µ = ±π (A·8) また，式(A·4)のr(0) とr(n) はそれぞれ図A· 2に示す“0”faceと“n”faceに対する反射係数であり，式 (A·1)で与えられる．なお，この場合，偏波面に留意する必要があり，詳細は文献[14]を参照のこと．（平成 17 年 8 月 15 日受付，11 月 8 日再受付）今井哲朗（正員）平 3 東北大・工・電気卒．同年 NTT（株）入社．以来，陸上移動通信に関する電波伝搬，回線設計法の研究開発に従事．平 4 NTT移動通信網（株）（現，（株）NTT ドコモ）に転籍．平 14 年 9 月東北大大学院工学研究科電気・通信工学専攻博士課程了．現在，（株）NTT ドコモ IP 無線ネットワーク開発部担当課長．平 10 年度本会学術奨励賞受賞．IEEE 会員．