研究紹介

  • 担当教員: 金澤 尚史 講師  [E-mail]
  • ゲーム理論を用いた工学システムの制御と設計

    経済学の分野で生まれたゲーム理論ですが、工学・社会システムに対して様々な応用研究がなされています。本研究室では、以下の4つの例を中心に、工学システムの制御と設計に対するゲーム理論の応用に関する研究を行っています。

    (1)税と補助金による制御法の利己的ルーティングへの応用

    近年、通信ネットワークが高度に発達するなかで、その資源の有効利用が問題となっています。利己的ルーティングとは、ネットワークを利用するユーザが、送りたいデータに複数の伝送経路がある時に、自身のデータを早く送ることだけを考えて利己的に伝送経路を選択することを言います。多数の機器やユーザが関わるネットワークにおいては、各ユーザが利己的ルーティングを行うことでかえって全体のパフォーマンスが劣化し、データの平均伝送遅延が最小となるフローが実現されない場合があります。これはまさに社会ジレンマと同様の構造を持った問題です。そこで本研究室では、一旦、税に対応する付加的な遅延を一律に全てのユーザに課し、補助金に対応する遅延をそこから割り引くという方法で、税と補助金による制御法を利己的ルーティングに対して適用し、伝送遅延が最小となるフローを実現する制御法を提案しています。今後はアルゴリズム的ゲーム理論で研究されている他のテーマ、例えば、計算機の資源配分や、負荷分散といった問題に対する研究も積極的に行っていきたいと考えています。

    (2)ポテンシャルゲーム理論を用いたセンサの最適配置

    多くの移動センサ間をネットワークで接続し、ある領域の状態をできるだけ正確に把握することは、しばしば重要な課題となります。このとき、監視対象の領域には重要度の高い部分と低い部分が混在するのが普通です。例えば、自然災害の監視が目的であれば、地盤の緩い岸壁や乾燥した草原などの災害の発生する確率の高い部分、大規模な人工システムであれば、故障しやすい部分や故障が致命的になる部分を重点的に監視する必要が有ります。このような場合、監視する領域の重要度に応じて適切にセンサを配置する必要があります。また、移動センサに関しては、内蔵バッテリーの消耗を抑制することでセンサの寿命を延ばすことができるため、消費電力の削減も重要な課題となります。しかしながら一般に、多くの電力を費やすほどより広い範囲を正確にセンシングすることができますので、消費電力の削減とセンシング性能の改善はトレードオフの関係にあります。

    そこで本研究室では、センサの位置とセンシングに利用する電圧を最適化するため、センシング性能に関する評価と消費エネルギーに関する評価を重み付けして組み合わせた評価関数を定義することで最適化問題を定式化し、レプリケータダイナミクスを用いて評価関数の極大点を求める手法を提案しています。消費電力の削減よりもセンシング性能を重視すると(図5 左)、中央部の重要度の高い領域を複数のセンサで集中的にセンシングする結果が得られますが、センシング性能よりも消費電力の削減を重視すると(図5 右)、中央部の重要度の高い領域を1台のセンサできちんと被覆しつつも、他のセンサはセンシングを全く行わないという結果が得られ、目的に応じてセンシング性能と消費電力の重みを考慮した最適配置と消費電力を求めることができます。また、領域全体を監視する場合、領域上の各点を最も近いセンサが被覆するとすると、各センサの受け持つ領域はボロノイ分割と呼ばれる分割によって与えられます。この条件下で、センシング性能の最大化と同時に障害物の回避を考慮した最適化問題を定式化し、同様にレプリケータダイナミクスを用いて最適なセンサ配置を求めるボロノイ被覆についても研究を進めています(図6)。

    ポテンシャルゲーム理論を用いたセンサの最適配置

    (3)ポテンシャルゲーム理論を用いたMP-SoCの周波数最適化

    複数のプロセッサ要素(PE)とそれらを相互に接続する通信ネットワークを1つのチップ上に実装したMP-SoC(Multiprocessor System-on-a-Chip)と呼ばれるVLSI(大規模集積回路)が有ります。MP-SoCでは、独自のプロセッサとメモリを備えた各PE上でタスクを並列に処理することができるため、リアルタイム性や低消費電力を求められる組込みシステム上でのマルチタスクアプリケーションの処理に適しています。このため近年、情報通信や信号処理、マルチメディア処理の分野で幅広く利用され始めています。

    ポテンシャルゲーム理論を用いたMP-SoCの周波数最適化

    本研究室では、各PEにDVFS(Dynamic Voltage Frequency Scaling)が実装されていて、プロセッサのクロック周波数を他のPEと独立に、動的に変更できるMP-SoCを対象とし、各PEのクロック周波数を最適化する問題を考えています。MP-SoCでは、過剰な温度上昇がパフォーマンスの劣化や信頼性の低下をもたらすため、タスクの処理効率だけでなく、温度上昇を抑制することも重要な課題となります。クロック周波数が高いほど、タスクの処理にかかる時間は短くなりますが、消費電力が大きく、発熱が大きくなります。さらに、各PEでの発熱は隣接するPEの温度にも影響を与えます(図7)。このため、温度上昇の抑制とMP-SoCのパフォーマンスのトレードオフを考慮しながら、各PEの動作クロック周波数を決定する必要があります。しかしながら、すべてのPEの周波数を同時に決定する最適化問題は、組み合わせ最適化問題と呼ばれる非常に難しい問題です。そこで本研究室では、MP-SoCにおいて温度と実行時間の優先度を表すパラメータを導入し、温度上昇と実行時間とのトレードオフを表現する評価関数を導入しました。そして、この評価関数をポテンシャル関数とするポテンシャルゲームを構成することで、各PEで分散的にクロック周波数を最適化する手法を提案しています。

    (4)メカニズムデザインを用いた虚偽の申告に頑健なリソース配分法

    近年、情報通信技術や仮想化技術の発達に伴って、大量の物理リソースを統合し、仮想化技術を用いて複数のクライアントで共有するクラウドコンピューティングシステムが非常に重要な役割を果たすようになっています。クラウドコンピューティングシステムを利用することで、各クライアントは、物理リソースの管理コストを軽減した上でタスクを効率よく処理することが可能となります。クラウドコンピューティングシステムは一般に多量のリソースからなりますが、複数のクライアントが同時に大量のリソースを必要とする処理を行おうとすると、全てのクライアントの希望するリソース利用量の合計が、利用可能なリソースの総量を超えてしまう場合が有ります。このような場合には、各クライアントにいかに公平にリソースを配分するかが重要な問題となります。本研究室では、各クライアントに同じ量のリソースを配分するのではなく、各クライアントが配分されたリソースで処理したタスクの品質(QoSレベル)が等しいという意味で公平なリソース配分の実現を目指して研究を進めています。

    一般にリソース管理者は、各クライアントがこれからどのようなタスクを実行するか事前に知ることはできません。そのため、QoSレベルが同じ値になるリソース配分を決定するためには、各クライアントに、どの程度のリソースを用いてタスクを処理するとどの程度のQoSレベルとなるか、その関係を事前に申告させる必要があります。リソース管理者は、この事前申告に基づいて、公平なリソース配分を求めることになります。しかしながら各クライアントは、自身のタスクのQoSレベルを大きくしたいため、虚偽の申告をすることでより多くのリソースの配分を受けようとします。そこで本研究室では、タスクの実行後にはQoSレベルが実際に観測できるとし、その観測結果と各クライアントの事前申告を元に、嘘をついたクライアントにペナルティを課すことで、各クライアントが嘘をついても得をしない、虚偽の申告に頑健なりソース配分法を提案しています(図8)。

    虚偽の申告に頑健なクラウドコンピューティングシステムのリソース配分法
    ページの先頭へ