無線アドホックネットワークは、固定電話網、携帯電話網、インターネットなど既存の特定のネットワークインフラに依存することなく、中継機能を搭載した端末だけから構成された一時的なネットワークを意味している。このような無線アドホックネットワークは、ユビキタス社会を実現する次世代移動通信に最も望ましい端末ネットワークの一つと考えられている。さらに、TDMA(Time Division Multiple Access)に基づく無線アドホックネットワークは、衝突のないデータ転送によって、マルチメディア応用向けのQoS(Quality of Service: 品質)の保証が比較的容易に実現できるため、注目されている。

QoSの指標は、帯域、遅延、スループットなど様々である。マルチメディア応用に最も重要で基本的な指標は帯域保証である。無線アドホックネットワークには、無線チャネルや端末能力等、必要な資源が一般にかなり限られているうえ、ルートのマルチホップ性、リンク間の干渉、基地局への非依存性など、他に見られない数々の特徴があり、他のネットワークの帯域保証方法をそのまま応用することができない。また、無線アドホックネットワークの帯域保証に関する研究は少なく、研究が完全に空白なテーマもある。しかも少ない既存研究には大きな欠陥があり、実用性が低いという問題もある。

そこで、将来における重要さと有望さの観点から、マルチメディアへの応用を可能とするため、無線アドホックネットワークにおける帯域保証という極めてチャレンジングな未開拓技術の研究を、緊急の重要課題と判断して実施した。具体的には、以下の三つの課題の解決策の開拓に取り組んだ。

課題1:無線ルートの帯域の定量的な導出方法

課題2:帯域最大化のためのタイムスロットの割り当て法

課題3:帯域保証のためのルートの選定法

以上の三つの課題を解決するための研究の成果をとりまとめた本論文は全8章よりなる。

第1章は「序論」で、研究の背景と目的を述べている。

第2章は、課題1の「無線ルートの帯域の定量的な導出」についての研究結果である。無線アドホックネットワークにおいて中核となる、ルートの帯域の定量的な導出に関する既存の関連研究では、一つのルート内の干渉だけを考慮しており、ルート間の干渉を考慮していない。その結果、帯域の導出結果は実際的でなく実用性に欠ける。そこで、本研究では、全てのルート間の無線干渉を考慮した、ルートの帯域の定量的な導出方法を初めて明らかにしており、更にその正しさを帰納法で証明した。

第3章から第6章までは、課題2の「帯域最大化のためのタイムスロットの割り当てアルゴリズム」についての研究結果である。

TDMA方式では、時間をタイムスロットに分割して各ユーザに割り当て、各ユーザは割り当てられたタイムスロットだけを使ってパケットを転送できる。このため、タイムスロットの割り当てはTDMAベースの無線アドホックネットワークにおける帯域保証に必須の重要な技術である。割り当てられたタイムスロット時間中、ユーザは通信路の全帯域幅を使用できる。その結果、ネットワークのトラヒックが増大してもパケット衝突が発生しない転送を実現できるため、無線アドホックネットワークのQoS保証に極めて有効であり、TDMAベースの無線アドホックネットワークは多くの注目を浴びている。

本研究では、TDMAベースの無線アドホックネットワークにおいて、各ノードは一つのトランシーバを持つこととしている。トランシーバは一つの無指向性のアンテナを持っており、送受信は同時にはできない。本研究でのタイムスロット割り当ての目的は、できるだけ多くのタイムスロットをルート内の各リンクに割り当て,、ルートの帯域を最大化することにある。

第3章では、タイムスロット割り当てをMIP (Mixed Integer Programming)問題として定式化した。その結果、理想的なタイムスロット割り当ては、例えばGLPK (GNU Linear Programming Kit)のような線形ツールを使って求めることが可能になった。

この方法は最大帯域を得ることが可能であるが、無線アドホックネットワークの規模が大きくなって、ルートが長くなったり、タイムスロット数が多くなったりすると、タイムスロットの割り当て時間が急激に増大するという問題がある。そのため、一般に資源がかなり限られる無線アドホックネットワークにおいては、この方法を実際に採用することは不可能になってしまう。

従って、現実的にはタイムスロット割り当ての近似法を採用しなければならない。これまでの研究によって得られている近似法では、ソースノードから宛先ノードまでその順番でタイムスロットを順次割り当てる。つまり、一つのノードでタイムスロットを割り当てるとき、以降のノードでの割当を考慮しない。このため、この方法で得られた帯域は狭く、本来は割当が可能な空きタイムスロットを割り当てられないことが多々あり、結果的にタイムスロットの利用効率が低くなってしまう。既存のタイムスロット割当法に関するこのような調査と分析をすることによって、タイムスロット割り当て問題を高速で解く新しい近似解法アルゴリズムの考案して詳細に設計し、その結果をSAGO (Slot Assignment by Global Overview)と命名し、第4章で具体的に論じた。

SAGOは、ソースノードと宛先ノード、及びそれらを結ぶ一つのルートが与えられた場合、そのルートの最大の帯域を求める方法である。具体的には、SAGO はreactive型のルーティングプロトコルを前提にしており、ソースノードから宛先ノードに対して、RREQ(Route REQuest Packet)を送出し、各ノードが持っている全タイムスロットの使用状況、すなわち、各タイムスロットが使えるか否かという情報をRREQに順次付け加えていき、宛先ノードでこれらをすべて収集しタイムスロットの割り当てを決める。

SAGOには次の特徴がある:

タイムスロット割り当てをソースノードから宛先ノードまで順次行うという既存研究と異なり、空きタイムスロットが最も少ないボトルネックリンクから両端のノードまでそれぞれ割り当てる;

ルート帯域を予め推定し、この推定値を使って、割り当てを試み始める;

割り当てできなくなった場合は、推定値を1だけ減らして、割り当ての試みを繰り返す;

割り当てるとき、各スロットと近隣リンクの関連度によって、リンク内の割当タイムスロットを選ぶ。

また、第4章で、SAGOの有効性・割り当ての速さをシミュレーションによって実証した。

更に、第5章では、SAGOをCDMA(Code Division Multiple Access)/TDMAベースの無線アドホックネットワークに拡張した。CDMA/TDMAベースの無線アドホックネットワークはTDMAと同様にQoS保証が容易である。CDMA/TDMAベースの無線アドホックネットワークとTDMAベースの無線アドホックネットワークは共通点もあるが、違いも存在する。例えば、TDMAモデルでは、データ転送時に二つの衝突の可能性がある。一つは各ノードが同じタイムスロットで同時に送受信できないために発生する。もう一つの衝突は各ノードが一つのタイムスロットで同時に二つのノードからのパケットを受けられないために発生する。一方、CDMAモデルでは、後者の衝突が起きないので、前者の衝突だけ存在する。つまり、タイムスロットの利用率を更に向上させることが可能である。

本研究では、CDMA/TDMAに基づくアドホックネットワークにおけるタイムスロットの割り当て方法を考案し設計して、SAP (Slot Assignment by Priority)と命名したアルゴリズムを提示して論じ、シミュレーションによって第4章と同様な実証を行った。

以上の研究はリンクの方向性をまったく考慮していない。しかし、リンクの方向性を考慮すれば、タイムスロットの使用率を更に大きくすることが可能になる。そのため、第6章では、TDMAアドホックネットワークにおいて、リンクの方向性を考慮したタイムスロットの割り当て問題を定式化した。次に、その問題を高速で解く近似解法アルゴリズムを考案した。また、考案した近似解法アルゴリズムの近似度・計算量に関して、定量的に評価した。更に、リンクの方向性を考慮しない近似アルゴリズムと比較して、タイムスロット使用率の向上度に関してシミュレーションで評価した。

第7章は課題3の「帯域保証のルートの選定法」についての研究成果である。即ち、第6章までの研究の前提として必要となる、最も重要なルート選定法について検討し、新しい選定法を提案した。そして、シミュレーションによって、このルート選定法を、TDMAベースの無線アドホックネットワークにおいて評価し、その有効性を定量的に実証した。

第8章は本論文の結論であり、第7章までの研究成果をとりまとめた結果を論じた。

本研究の成果は、無線アドホックネットワークにおけるアクセス制御や負荷のバランス化などにも応用できると考えられる。つまり、本研究成果の適用領域の拡大を図ることによって、エンドツーエンドのQoS保証と将来のユビキタスネットワーク技術の発展に大きく貢献できるものと期待される。

将来の課題として、遅延やスループットなどの他のQoS指標の保証と制御に取り組むことが挙げられる。

本論文は「Time Slot Assignment for Maximum Bandwidth in Slotted Wireless Ad Hoc Networks (TDMA ベース無線アドホックネットワークにおける最大帯域タイムスロット割り当て)」と題し、無線アドホックネットワークにおいて、所要伝送帯域の情報転送を実現することを目的として、最大伝送帯域を持つルートを選定する手法、及び選定されたルートでそのような最大伝送帯域を実現するためのタイムスロット割当法を提案し、それらの有効性をシミュレーションによって実証したもので、全8章から構成されている。

第1章は「序論」であり、近年無線技術や小型通信端末技術等の発展により、無線ノードのみから構成されるアドホックネットワークが、特にユビキタス社会の到来に伴って極めて重要になってきたことを述べ、その実現に向けては、安定したマルチメディア通信のために特に所要伝送帯域を満たすことの重要性を指摘し、本論文の研究の意義を明らかにしている。

第2章は「伝送帯域の導出」と題し、本論文で扱うアドホックネットワークのモデル化を行い、そのモデルを前提として、任意のルートの伝送帯域を計算するための公式を導出している。この公式の特徴は、他のルートにおけるトラヒックの存在を考慮し、それらとの電波干渉を考慮した目的ルートの伝送帯域が導出可能な点にある。

第3章は「タイムスロット割当問題の定式化」と題し、時分割多重方式をベースとするアドホックネットワークを具体的に説明した後、そのようなアドホックネットワークの中で与えられたルートにおいて最大伝送帯域を実現するタイムスロット割当を定式化した結果を論じている。この定式化結果は、一つの混合整数計画問題であり、時分割多重度やルート内ホップ数が多くなると問題規模が大きくなってしまい、実用性のある時間内で最大伝送帯域を計算することが不可能であることを示し、近似解法が現実には必要であることを述べている。

第4章は「タイムスロット割当法」と題し、第3章で必要性を述べたタイムスロット割当問題の近似解法SAGOを提案している。SAGOの特徴は、与えられたルートにおいて空きスロットが最も少ないボトルネックのリンクからタイムスロットの割当を開始し、近傍リンクでの使用度合いが高いタイムスロットから優先的に順次割り当てることにあり、その結果使用タイムスロットをできる限り詰めていくことが可能になるため、結果としてほぼ最大帯域のタイムスロットを比較的短時間で割り当てられることにある。そして、シミュレーションによって、この特徴を定量的に論じている。

第5章は「タイムスロット割当のCDMA/TDMAへの応用」と題し、第4章で論じた近似最適タイムスロット割当法SAGOを、TDMAだけでなく他の多重方式に基づくアドホックネットワークに応用するための手法について論じている。具体的には、他の多重方式としてCDMA/TDMAをとりあげ、SAGOの拡張によってCDMA/TDMAでもSAGOが有効であることをシミュレーションによって明らかにしている。

第6章は「無線リンクの方向性を考慮したタイムスロット割当」と題し、第四章と同一の目的を果たすため、各リンクにおけるタイムスロットの電波伝送方向を考慮し、干渉が生じない範囲で、可能な限り多くのタイムスロットを割り当てる方法SAGO-Dを提案している。そして、その新しい提案法によって、伝送帯域を確実に増大できることを、シミュレーションによって定量的に論じている。

第7章は「最大伝送帯域のためのルーティング」と題し、最大伝送帯域を持つルートを選定する手法を論じている。具体的には、各ルートの伝送帯域の上限値を計算してその上限値が最も大きいルートを選ぶこととし、もしそのようなルートが複数ある場合は、それらにSAGO-Dを適用して実際に伝送帯域を導出し、その中から最も大きな伝送帯域を持つルートを最終的に選択する。この手法によって、ルート選択に要する処理時間が大幅に短縮できることをシミュレーションによって明らかにしている。

第8章は「結論と将来課題」であり、本論文の研究成果と今後の展開をとりまとめている。

以上を要するに、本論文は、時分割多重方式に基づくアドホックネットワークにおいて、所要伝送帯域を実現するための基礎技術として、最大伝送帯域を持つと考えられるルートを高速に選定する方法を開拓するとともに、そのルートにおいて最大伝送帯域を実現するための近似タイムスロット最適割当法を考案して技術確立したものであり、情報学の基盤に貢献するところが少なくない。

したがって、博士(科学)の学位を授与できると認める。