隠れ端末問題とグラフ理論の関係についての質問

質問

現在、大学の理工学部の情報工学科に所属し、アドホックネットワークを研究している研究室に配属された者です。この研究室ではアドホックネットワークについて、「グラフ理論の応用」を基本的な方針としています。

　私は卒研のテーマとして、アドホックネットワークにおける重要な問題である「隠れ端末問題」を研究することになりましたが、正直、どう研究を進めていって良いか全く分かりません。

　「グラフ理論を用いて、隠れ端末問題を研究する」という、漠然とした方針は決まっているのですが、そもそも、隠れ端末問題とグラフ理論がどう関わっているのか、そして、何が問題となっていて、何を目的として研究をすれば良いのかが分かりません。

　論文を検索するWebサイトで、「隠れ端末問題」や「グラフ理論」をキーワードにして色々と検索してみたのですが、隠れ端末問題の解決においてグラフ理論を利用している論文は全く見つかりませんし、論文を見ても、隠れ端末問題において現在何が問題となっていて、そして何を目標として研究するべきなのかが把握できません。

　研究室の教授は放任主義で、こちらが質問をしてもはっきりとした答えが返ってきません。

　もしこの分野にお詳しい方がいらっしゃいましたら、

・隠れ端末問題とグラフ理論がどう関係しているのか
・隠れ端末問題において、現在何が問題なのか
・問題を解決するための研究の目的と流れ

以上の質問に答えて頂けると有り難いです。

回答No.3

hrsmmhr

いえ、全くないとは申しません
移動のない無線通信でも僻地などで使う可能性もあります
でもその場合、隠れ端末が仮題にするメディアの利用効率の向上が
意味がある利用形態は今あまり必要とされていないと言うことです

グラフ理論ならマルチホップのルーティングの方が
関連しているのではないですか？

回答No.2

hrsmmhr

隠れ端末問題は直接はグラフ理論を用いないと思います
単純にいってしまえば、通信する端末の位置関係が分かり、
タイミングをあらかじめ合意できていれば問題は発生しないので
アドホックのように位置関係が変動していて合意がとれていないときに
いかに論理的に重複しない時間と空間とチャネルを選択できるかです
その課題の研究はご存じかと思いますがかなりやられていて
グラフ理論の切り口で、新しい面を見いだしたい気持ちは分かりますが
グラフ構造の把握の情報交換がアドホックの位置関係の変動になかなか追従するほど
速い通信は行えないものが実用的で研究対象としては多い気がします
もう少し対象を限定できないと、一般的には意味がないという回答になると思います

お礼

御回答ありがとう御座いました。

　ついでに質問させて頂きたいのですが、グラフ理論の切り口では、隠れ端末問題は研究の余地が全く無いという事なのでしょうか。

回答No.1

stomachman

詳しいわけじゃないんで、あくまでジョーシキの範囲での素人考えですが。
　隠れ端末問題ってのは、要するに「お互い存在を知らない同士A,Bが、同じ相手Cに同時に送信を行うのをなんとかやめさせて欲しい。せめてそういうことが生じる確率を小さくして欲しい」ということ。
　たとえば、AがCに送信したらCはすぐに「今受信中。待ってね」とブロードキャストし、終わったら「終わった」と放送する、というやりかただと、Aの送信中にBが送信を始める確率は下げられるけれども、「終わった」と聞いたとたんに送信を始めようとする連中が殺到してしまう。そこでさらに、各ノードにリソース（使って良いいくつかのチャネルとか、送信を始めて良いタイミングとか）を割り当てておくとしましょう。たとえばノード全部の時計をいつも合わせておいて、ミリ秒の下一桁が「Aさんは0のとき」「Bさんは2のとき」という風に。そうするとしかし、Cに送信する可能性があるノードがやたら沢山あって、しかも大抵のノードは滅多に送信を行わない、という状況では、Cが結構ヒマしている時でもAはリソースの空きを延々待っていることになりかねない。
　一例として、これをなんとかしたいという問題を考えたらどうなるか。
　お互い存在を知っているノードをアークで繋いだグラフを作る。A,B,Cは全部このグラフGに含まれているのだけれども、このグラフのうち「Aが存在を知っているノード」だけに限定した部分グラフG(A)と、「Bが存在を知っているノード」だけに限定した部分グラフG(B)とを作ると、G(A)にはBが入っておらず、G(B)にはAが入っておらず、でもCはG(A), G(B)の両方に入っている。（受信するノード（ホスト・サーバ・ルータ、呼び名は何でも良いが）がCだけならG(C)=Gだけど、必ずしもそういう場合ばかりではない。）
　さて、G(A)の全てのノードは、Aが送信を始めたことを検知でき、検知したらぶつからないように回避（待つか、使って良い別のチャネルを探索）するので、Aと同じリソースを割り当てられていても衝突は起こさない。
　こういう状況で、Gをどういう風に分割すれば、最少の種類のリソースで済ませられるか。要するに、Gを完全グラフになっている部分グラフに分割しろ、というだけのことであり、これならとっても簡単。
　しかし、Gが経時的に変化するのに応じて、しょっちゅう割当て方を変えなくてはならない。割当ての変更の必要性を即座に認識し、割当を決定し、間違いなく必要なノードに伝えるにはどうしたらいいか。さらに、それをできればCに頼らず局所的に（部分グラフのノード間だけで）行えないか。いつも最適な割当て方を保証できるか。あるいは、あらかじめうまく割当てることで、割当ての変更の期待値が最小になるようにできないか。というような問題を考えると、そう簡単ではなくなってくるような気がします。

　これはリソースを割り当てる、という例でしたけれども、もう少し抽象化して言ってみれば、グラフGが変化するのを常時監視して正しく認識し続けること、もう少し正確には、各ノードが、グラフGの変化のうちそのノードにとって「意味がある」変化を漏らさず認識し続けること。そのためのコスト（通信）が本来のデータ伝送の邪魔になるべくならないようにすること(「できればCに頼らず局所的に」はこれに関わる条件の一例です）。なんだかロボカップにおける選手間の通信の話と似ているな、とも思います。