近年、通信技術は急激に発展し、携帯電話やPDAなど、携帯端末が生活の中で欠かせないものとなってきている。そのような中で、新たな形態のネットワークとして、アドホックネットワークが注目されている。アドホックネットワークのような新しい形態の移動体通信においては、従来の固定的なネットワークの枠組みでは柔軟な対応が難しく、新たな通信方式の開発が盛んに行われている。
本研究では、アドホックネットワークにおいて、頑健で学習速度の速い確率的ルーティングアルゴリズムの提案と評価を行う。
アドホックネットワークとは移動体端末(以下ノード)が即席で形成する自律分散型のネットワークであり、以下のような特徴を持つ。
図1：アドホックネットワーク
アドホックネットワークにおけるルーティングアルゴリズムはIETF (The Internet Engineering Task ForceのMANET(Mobile Ad-hoc Network) Working groupにより多数提案されているが、それらの手法は制御通信量が多いという欠点がある。また、Q-routingをはじめとする強化学習的手法は学習が遅いという欠点があった。
そこで、履歴情報を用いることで学習量を増加させ、効率的な経路選択を行う確率的ルーティングを提案する。
まず、各ノードは送信先(Next hop)決定のための確率値テーブルを保持する(図2)。この確率値を更新していくことで経路を学習してゆく。
図2：ルーティングテーブル
メッセージパケットを送信する際には、その経路の履歴情報を格納しながら伝送する。図のように中継ノードと中継にかかった所要時間を記録し、宛先ノードまで送信する(図3)。履歴キューのサイズは一定で、情報の古いものから順に削除してゆく。これは情報の古い経路はノードの移動により切断されている可能性が高いためである。
図3：履歴の記録
メッセージパケットを受信したノードは、この履歴情報を元にルーティングテーブルを更新する。ノードxからノードyにメッセージが中継された場合の学習式を次に示す。
d'は履歴情報に記録されている各ノード、hはyからd'までのホップ数、γは割引率、nは学習率、td'はd'からyまでの所要時間である。確率値の変化量Δpを決定し、それをxを選択する確率値に足しこむ。また、全ての確率値を足すと1になるようにするためにx以外のNext hopに関しては正規化を行う。
学習率nに1ホップ離れるごとに割引率γを掛けることでより新しい、信頼できる経路に関しては多くの学習を行い、より古い、信頼性の低い経路に関しては少ない学習を行う。これにより効率的な学習を行うことができる。
提案手法の性能を評価するために実験を行った。16×16のフィールドに56個のノードをランダムに配置し、ユークリッド距離で3以内にあるノード同士を通信可能とする(図4)。
図4：実験環境
1ステップを処理単位とし、メッセージの生成・送受信、ノードの移動を行う。メッセージの処理待ちキューが空のノードのみが5％の確率でランダムな宛先のメッセージを発生させる。1ステップに1つのノードが移動する確率(MO)を0.1％,10％とし、実験を行った。1回のシミュレーションは50000ステップで、100回シミュレーションを行った平均値をグラフにしてある。
図5：MO=0.1％の平均メッセージ到達ステップ数
図6：MO=0.1％のネットワーク内パケット数
図7：MO=10％の平均メッセージ到達ステップ数
図8：MO=10％のネットワーク内パケット数
メッセージパケットが宛先ノードに到達するまでの平均ステップ数の比較を見てみると、提案手法が従来手法と比べ、より素早く少ないステップ数に収束していることがわかる。このことから、提案手法は従来手法と比較して学習速度が速いと言える。
また、輻輳の度合いを示すネットワーク内パケット数を見てみると、提案手法が安定して低いパケット数に抑えられていることがわかる。このことから提案手法はノードの移動が激しい場合においても効率よく頑健なルーティングを行うことができると言える。