TOP > 国内特許検索 > 通信方法 > 明細書

明細書 :通信方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4686662号 (P4686662)
公開番号 特開2006-186446 (P2006-186446A)
登録日 平成23年2月25日(2011.2.25)
発行日 平成23年5月25日(2011.5.25)
公開日 平成18年7月13日(2006.7.13)
発明の名称または考案の名称 通信方法
国際特許分類 H04W  74/08        (2009.01)
H04W  84/12        (2009.01)
FI H04L 12/28 307
請求項の数または発明の数 9
全頁数 15
出願番号 特願2004-375170 (P2004-375170)
出願日 平成16年12月27日(2004.12.27)
審査請求日 平成19年12月21日(2007.12.21)
特許権者または実用新案権者 【識別番号】510108951
【氏名又は名称】公立大学法人広島市立大学
発明者または考案者 【氏名】角田 良明
【氏名】大田 知行
審査官 【審査官】福岡 裕貴
参考文献・文献 特開2004-266653(JP,A)
藤本 宗彦,適応的階層構造構成法に基づくアドホックネットワーク階層ルーティングの性能評価,電子情報通信学会技術研究報告 IN 情報ネットワーク,2003年12月 5日,Vol.103 No.493 ,p.59-64
大田 知行,アドホックネットワークにおける適応的クラスタリング手法,電子情報通信学会技術研究報告 IN 情報ネットワーク,2002年11月 8日,Vol.102 No.441,p.57-62
調査した分野 H04W 4/00-99/00
H04L 12/28-12/46
特許請求の範囲 【請求項1】
同一のクラスタIDを有する複数のノードから成るクラスタを生成し、前記クラスタでアドホックネットワークを構成する通信方法であり、
前記ノードは、隣接する隣接ノードのクラスタIDを取得し、
前記ノードのクラスタIDとは異なるクラスタIDを有する隣接ノードの割合が、全ての前記隣接ノードに対して所定の値以上であるときは、前記ノードが自身のクラスタIDを更新することを特徴とする通信方法。
【請求項2】
前記隣接ノードの少なくとも1つは、前記ノードと同一のクラスタIDを有することを特徴とする請求項1記載の通信方法。
【請求項3】
前記クラスタを構成するノードは、クラスタを管理するクラスタヘッドと、異なるクラスタIDを有するノードに隣接するゲートウェイを含み、
前記隣接ノードの全ては、前記ゲートウェイであることを特徴とする請求項1記載の通信方法。
【請求項4】
前記ノードは、移動可能な通信端末であることを特徴とする請求項1記載の通信方法。
【請求項5】
前記ノードのクラスタIDとは異なるクラスタIDを有する隣接ノードの割合が、全ての前記隣接ノードに対して40%以上であるときに、前記ノードのクラスタIDを更新することを特徴とする請求項1記載の通信方法。
【請求項6】
同一のクラスタIDを有する複数のノードから成るクラスタを生成し、前記クラスタでアドホックネットワークを構成する通信方法であり、
前記ノードは、隣接する隣接ノードのクラスタIDを取得し、
前記ノードと同一のクラスタIDを有する前記隣接ノードの数が、前記ノードとは異なるクラスタIDを有する前記隣接ノードよりも少ないときは、前記ノードが自身のクラスタIDを更新することを特徴とする通信方法。
【請求項7】
前記ノードと同一のクラスタIDを有する隣接ノードの数が2以下、且つ、前記ノードとは異なるクラスタIDを有する前記隣接ノードの数が3以上であるときに、前記ノードのクラスタIDを更新することを特徴とする請求項6記載の通信方法。
【請求項8】
前記クラスタを構成するノードは、クラスタを管理するクラスタヘッドと、異なるクラスタIDを有するノードに隣接するゲートウェイを含み、
前記隣接ノードの全ては、前記ゲートウェイであることを特徴とする請求項6記載の通信方法。
【請求項9】
前記ノードは、移動可能な通信端末であることを特徴とする請求項6記載の通信方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、通信方法に関し、特に、アドホックネットワークを構成するクラスタを適正に生成できる通信方法に関するものである。
【背景技術】
【0002】
アドホックネットワークとは、有線ネットワークにおけるルータのようなルーティング機能を持つモバイル端末の集合である。モバイル端末が他のモバイル端末と通信する場合、送信元モバイル端末から発生したデータパケットは、他のモバイル端末を経由する。すなわち、アドホックネットワークにおけるモバイル端末は、携帯電話システムのような基地局を用いることなく通信が行える。モバイル端末がどの方向へ、またどんな速度でネットワーク内を移動しても、集合から離れなければお互いに通信することが可能である。
【0003】
アドホックネットワークを用いる場合は、クラスタリングとルーティングを適正に行うことが重要である(下記特許文献1を参照)。ここで、クラスタリングとはネットワークをクラスタと呼ばれるサブネットワークに分割することである。また、ルーティングとは、パケット(情報)を転送する端末間の経路を決定することである。

【特許文献1】特開2004-215064号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、一般的なクラスタリングでは、各クラスタの地理的形状が考慮されていない。従って、細長いクラスタの形状が構成されてしまう恐れがある。この場合は、クラスタ内のゲートウェイ数が増加し、クラスタ間のパケットコリージョンが引き起こされる恐れがある。更に、クラスタ間のルーティングが非効率に成ってしまう可能性もある。
【0005】
また、各モバイル端末の地理的位置情報を利用することにより、上記の問題は回避可能である。しかしながら、地理的位置情報を用いると、各モバイル端末を経由する情報量が増大してネットワークに与える負荷が大きくなってしまう問題があった。
【0006】
本発明は、上記問題を鑑みて成されたものである。本発明の主たる目的は、ネットワークの接続状態が変化した場合でも、クラスタの地理的な形状が考慮された通信方法を提供することにある。
【課題を解決するための手段】
【0007】
本発明の通信方法は、同一のクラスタIDを有する複数のノードから成るクラスタを生成し、前記クラスタでアドホックネットワークを構成する通信方法であり、 前記ノードは、隣接する隣接ノードのクラスタIDを取得し、前記ノードのクラスタIDとは異なるクラスタIDを有する隣接ノードの割合が、全ての前記隣接ノードに対して所定の値以上であるときは、前記ノードが自身のクラスタIDを更新することを特徴とする。

【0008】
更に、本発明の通信方法は、同一のクラスタIDを有する複数のノードから成るクラスタを生成し、前記クラスタでアドホックネットワークを構成する通信方法であり、前記ノードは、隣接する隣接ノードのクラスタIDを取得し、前記ノードと同一のクラスタIDを有する前記隣接ノードの数が、前記ノードとは異なるクラスタIDを有する前記隣接ノードよりも少ないときは、前記ノードが自身のクラスタIDを更新することを特徴とする。

【発明の効果】
【0016】
本発明の通信方法に依れば、地理的な形状が考慮されたクラスタリングを行うことができる。従って、各クラスタは丸みを帯びた形状となる。結果的に、各クラスタのゲートウェイ数を削減することが可能となる。従って、ノードが移動することによりネットワークトポロジが変化した場合でも、丸みを帯びたクラスタを再構築することができる。
【0017】
更に、クラスタリングを行う際に、各ノードの地理的位置情報を用いていないので、制御パケット数の増加を抑止して、効率的なクラスタリングを行うことができる。
【発明を実施するための最良の形態】
【0018】
以下、図を参照して本発明の実施の形態を説明する。
【0019】
先ず、図1を参照してアドホックネットワーク10の概要を説明する。
【0020】
アドホックネットワークとは、モバイル基地局や優先リンクを持たず、基本的に交換機能を有するモバイル端末(以下ノードを呼ぶ)だけで構成されるネットワークである。本形態では、アドホックネットワークは、複数のクラスタに分割されている。ここでは、アドホックネット10は、第1のクラスタ11A、第2のクラスタ11Bおよび第3のクラスタ11Cの3つに分割されている。実際は、更に多数個のクラスタ11によりネットワークが構成される。
【0021】
クラスタ11は複数のノード12から構成される。ここでは、第1のクラスタ11Aはノード12A~12Dから成る。そして、第2のクラスタ11Bは、ノード12E~12Hから成る。更に、第3のクラスタ11Cは、ノード12J~12Lから成る。各ノードは、クラスタヘッド、ゲートウェイ、クラスタメンバの何れかの役割を有する。
【0022】
本形態では、クラスタは以下の特徴が満たされるように維持される。クラスタヘッドのノードIDが管理するクラスタのIDとなり、このIDをクラスタIDと呼ぶ。クラスタ内の任意のノードは、同じクラスタIDを持つ隣接ノード間の無線リンクによって接続される。更に、クラスタのサイズは下限L及び上限Uで制限される。例えば、クラスタ内のノードの数は、10から25程度の間に制限することができる。更に、各ノードは、ノードID、クラスタID、状態、隣接ノードリストの状態に関する情報を所有している。
【0023】
例えば、アドホックネットワークを用いて、モバイル端末であるノード12Aとノード12Lとが通信を行う場合は、以下の経路にて両者が接続される。即ち、12A→12B→12F→12H→12I→12K→12Lの経路で、ノード12Aとノード12Lとは通信可能になる。
【0024】
図2を参照して、アドホックネットワークを構成するクラスタを更に詳細に説明する。
【0025】
クラスタヘッドとは、クラスタを管理するノードである。図2で示されるように、クラスタヘッドはクラスタ内の全ノードに関する情報を効率良く収集するため、クラスタ内にスパニングツリーを形成する。スパニングツリーとは、クラスタヘッドを根としたツリー状の接続形態であり、クラスタ内のデータパケットの転送に利用される。スパニングツリーを用いることにより、ループを無くした経路が実現される。
【0026】
クラスタヘッドは、収集した情報を元に、クラスタ内のノードのリストを作成する。次に、クラスタヘッドは、隣接クラスタに関する情報を収集することで、隣接する全てのクラスタのリストを作成する。これら二つのリストを用いて、クラスタヘッドは以下のようにクラスタ内のノード数を調整する。即ち、クラスタ内のノード数がL(例えば10個)未満の場合、クラスタヘッドは全隣接クラスタのサイズを調べ、自クラスタを隣接クラスタの一つと結合する。また、クラスタ内のノード数がU(例えば25個)より大きい場合、クラスタヘッドは自クラスタを二つのクラスタに分割する。どちらの場合も、結合あるいは分割されたクラスタの隣接クラスタは更新されるが、クラスタの結合及び分割の影響は制限される。なぜなら、クラスタの維持は局所的に行われるからである。
【0027】
ゲートウェイは、異なるクラスタIDを有するノードに隣接しているノードである。ここでは、黒塗りで示されているノードがゲートウェイである。即ち、ノードVのクラスタIDと異なるクラスタIDを持つノードがVに隣接している場合、Vはゲートウェイと呼ばれる。ゲートウェイVは、隣接クラスタ内のゲートウェイと情報を交換することで、その隣接クラスタのノード数を知ることができる。
【0028】
クラスタ維持のため、クラスタヘッドは定期的にクラスタ内に''clustermember''メッセージをブロードキャストする。ここで、ブロードキャストとは、クラスタ内の全てのノードに対して情報を発信することを指す。clustermemberメッセージを受信したクラスタ内の各ノードは、木に沿ってクラスタヘッドに向けてREPLYメッセージを返信する。このとき、クラスタメンバ及びゲートウェイは、それぞれ自分自身のID及び隣接クラスタの情報をREPLYメッセージに含める。その結果、クラスタヘッドはクラスタ内のクラスタメンバと隣接クラスタの両方に関する情報を集めることができる。各ノードは隣接ノードがブロードキャストするあらゆるメッセージを受信できるので、局所情報を収集できる。また、各ノードはその局所情報に従ってクラスタ内の自分の役割を変化させるため、自律的にクラスタを構成することが可能となる。
【0029】
図3を参照して、次に、クラスタを構成するノードの状態と役割に関して説明する。本形態のクラスタリング手法では、各ノードは一つの状態を持ち、その状態に対応する役割を果たす。ノードは、NSN、CN、BN、BCN、ONのいずれかの状態にあり、各状態での役割を以下で説明する。
・Normal State Node(NSN):ノードはクラスタヘッドや、ゲートウェイの機能を持たない。例えば、第1のクラスタ11Aに含まれるノード12Cが、NSNの一例である。
・Control Node(CN):ノードはクラスタヘッドの役割を果たす。例えば、第1のクラスタ11Aに含まれるノード12Aが、CNの一例である。ここでは、ノード12Aにより、第1のクラスタ11Aに含まれる全てのノードが制御されている。そして、ノード12AのノードIDが、第1のクラスタ11AのクラスタIDとなる。
・Border Node(BN):ノードはゲートウェイとなる。例えば、第1のクラスタ11Aに含まれる、ノード12Bおよびノード12Dが、BNの一例である。
・Border Control Node(BCN):ノードはクラスタヘッドとゲートウェイの役割を担うことになる。例えば、第2のクラスタ11Bに含まれるノード12Fが、BCNの一例である。
・Orphan Node(ON):ノードの状態がONのとき。ノードはクラスタIDを持たない。新しくネットワークに加えられたノードは、最初はこの状態である。例えば、第3のノード11Cに含まれるノード12Mが、ONの一例である。
【0030】
次に、ノードの状態遷移に関して説明する。クラスタヘッドやゲートウェイのような、クラスタリングにおいて不可欠な役割を果たすノードさえもネットワーク中を動き回る。そのため、そのノードが役割を果たせなくなった場合はいつでも、他のノードが代わりにその役割を果たさなければならない。ノードが移動してもクラスタリングを維持するために、ノードは自律的に自分の状態を変化させ、その状態に対応した役割を果たす。各ノードの状態は、隣接ノードの状態の変化に応じて変化する。ノードは常にネットワーク中を移動するので、ノードの移動に対する適応性はクラスタリングにとって最も重要な特徴の一つである。
【0031】
図4を参照して、上記各状態に於ける動作を説明する。ここで、NNをノードViの隣接ノードの集合とする。ノードViは隣接ノードからのhelloパケットを受信することでこの集合を認識する。NNにおけるノードのクラスタIDも、helloパケットから得られる。このクラスタIDに基づき、ノードViが持つべきクラスタIDは以下のように割り当てられるか、あるいは更新される。ここでは、ノードの状態が、ONの場合とそれ以外の場合に分けて説明する。
【0032】
ノードViの状態がONの場合は、以下の2つのケース(ケース1およびケース2)に従って、クラスタIDが更新される。
【0033】
ケース1:図4(A)参照
ノードViがONであるノードからhelloパケットを受信した場合、ノードViは隣接ノードも全てONであると認識し、ある確率で自分のクラスタIDにiを割りあてる。具体的には、ノード12A~12Fから成るNNが構成されている。そして、Viは、状態がONであるノード12DからHELLOパケットを受信すると、集合体NNを構成する全てのノード12の状態がONであると判断される。そして、ViのクラスタIDにiを割り当てる。
【0034】
ケース2:図4(B)参照
ノードViが、クラスタIDがkである隣接ノードからHELLOパケットを受信した場合、ノードViはクラスタIDkを持つ隣接ノードの存在を認識する。そして、ノードViのクラスタIDはkとなる。
【0035】
ノードViの状態が、CN、BCN、BN、NSNの何れかである場合(ON以外である場合)は、以下のケース3に従って、クラスタIDが更新される。
【0036】
ケース3:図4(C)参照
ノードViのクラスタIDはkである。そして、ノードViにはクラスタIDkを有する隣接ノードがいたと仮定する。ノードViが各隣接ノードからHELLOパケットを受信して、そのパケットのクラスタIDがk以外であった場合、ノードViはクラスタIDkを有する隣接ノードは全て消失したと認識する。即ち、ノードViを取り巻く隣接ノードのクラスタIDは、k以外であると認識する。そして、全隣接ノードに対して最も多いノードが有するクラスタIDを、ノードViのクラスタIDとする。
【0037】
具体的には、ノードViは、第1のクラスタ11A、第2のクラスタ11Bおよび第3のクラスタ11Cに囲まれている。第1のクラスタ11AのクラスタIDはpであり、第2クラスタ11BのクラスタIDはqであり、第3のクラスタ11CのクラスタIDはrである。また、第1のクラスタ11Aは2つのノードを含み、第2のクラスタ11Bも2つのノードを含み、第3のクラスタ11Cは3つのノードを含む。また、この状態では、ノードViは、自分自身と同一のクラスタIDは隣接ノードに存在しないと認識している。
【0038】
ノードViは、各クラスタ11から得られたHELLOパケットを基に、自らのクラスタIDを決定する。更に、最も数が多いノードのクラスタIDに、ノードViのクラスタIDは更新される。ここでは、3つの各クラスタ11A、11B、11Cに含まれるノード12の各々から、HELLOパケットがノードViに発信されている。そして、第3のクラスタ11Cは、3つのノード12がノードViに隣接しており、最も数が多い。そして、第3のクラスタIDは、rである。従って、ノードViのクラスタIDは、rに更新される。即ち、ノードViは、第3のクラスタ11Cに取り込まれる。
【0039】
図5を参照して、本形態では、ノードViが持つべきクラスタIDは、隣接するのノードの集合体から得られる。更に、このクラスタIDの情報に基づき、ノードViが持つべき状態は、以下のように変化する。本形態では、この状態変化を状態遷移と呼ぶ。
【0040】
以下で記述する状態遷移条件が満たされるなら、ノードViは図5に示すような状態遷移A-Eを行う。
・遷移Aの条件:クラスタIDが変更され、そのIDがViのノードIDと一致した。この遷移は、ノードViにクラスタヘッドの役割の追加することを意味している。
・遷移Bの条件:クラスタIDが変更され、そのIDがノードViのノードIDと一致しない。この遷移は、ノードViが通常の端末に戻ることを意味している。
・遷移Cの条件:ノードViのノードIDと異なる隣接ノードが現れた。この遷移は、ノードViにゲートウェイの役割を追加することを意味している。
・遷移Dの条件:全ての隣接ノードのIDが、ノードViのノードIDと一致しない。この遷移は、ノードViから、ゲートウェイの役割の削除を意味している。
・遷移Eの条件:ノードViに隣接するノードが無くなった。あるいは、ノードViがクラスタヘッドからのメッセージをある期間受信できない。この遷移は、ノードViをON状態にすることを意味している。
【0041】
上述したように、各ノードのクラスタIDは、ケース1、2、3で説明したように変化する。ネットワークが密な場合は、上述した方法を用いると、クラスタ間のパケットコリジョンや非効率なルーティングが発生する恐れがある。その理由は、この方法ではクラスタの地理的形状が考慮されていないので、細長い形状のクラスタが形成される恐れがあるからである。
【0042】
パケットコリジョンとは、パケット同士が衝突する不具合のことである。具体的には、クラスタの形状が細長くなり、ゲートウェイ数が増加することにより、この問題は引き起こされる。非効率なルーティングも、クラスタが細長くなることにより引き起こされる。即ち、クラスタの形状が細長い場合、データパケットが多くのゲートウェイを介して遠回りしてしまう。
【0043】
図6から図8を参照して、クラスタの地理的形状が考慮されたクラスタリング手法を説明する。以下に説明するクラスタリング手法では、ONを除く各ノードのクラスタIDは、ケースA、ケースB、ケースCで説明されるように変化する。以下の説明では、ノードに関する地理的情報を利用せずに、地理的形状が考慮されたクラスタリングを行うことができる。
【0044】
ケースA:図6を参照
このケースは、等しいクラスタIDを有するノードViの隣接ノードが消失した場合のクラスタリングである。図6(A)はケースAのクラスタリングを行う前のクラスタを示し、図6(B)はクラスタリングを行った後のクラスタを示す図である。
【0045】
図6(A)を参照して、ノードViは、第1のクラスタ11A、第2のクラスタ11Bおよび第3のクラスタ11Cに囲まれている。第1のクラスタ11Aおよび第2のクラスタ11Bは、2つのノード12を含み、第3のクラスタ11Cは3つのノードを含む。
【0046】
ここで、ノードViのクラスタIDがkであり、且つ、ノードViにはクラスタIDkを有する隣接ノードが存在していたと仮定する。ノードViは、隣接ノードからHELLOパケットを受信することで、クラスタIDkを有する隣接ノードが全て消滅したと認識する。次に、ノードViのクラスタIDは、k以外に更新される。ここでは、全ノードに対して最も数が多いノードが有するクラスタIDが採用される。即ち、第3のクラスタ11CのクラスタIDであるrが、ノードViのクラスタIDとなる。
【0047】
図6(B)を参照して、ケースAのクラスタリングを行うことにより、ノードViは第3のクラスタに取り込まれている。
【0048】
ケースB:図7を参照
このケースは、ノードViが細長いクラスタに囲まれた場合のクラスタリングである。図7(A)はケースBのクラスタリングを行う前のクラスタを示し、図7(B)はクラスタリングを行った後のクラスタを示す図である。
【0049】
図7(A)を参照して、ここでは、第1のクラスタ11A~第4のクラスタ11Dが隣接している。第1のクラスタ11Aは直列に配置された6個のノード12からなり、細長く延在している。第2のクラスタ11Bに含まれるノードViは、第1のクラスタ11Aに囲まれるように位置している。第3のクラスタ11Cおよび第4のクラスタ11Dに含まれるノード12も、ノードViに隣接している。上述したケースAでは、ノードViと同様のクラスタIDを有する隣接ノードが消滅していたが、ケースBでは同様のクラスタIDを有する隣接ノードが存在している。
【0050】
ノードViは、隣接ノードからHELLOパケットを受信して、クラスタIDを更新する。具体的には、隣接ノード数が最も多く、そのノード数が全隣接ノード数のh%以上であった場合に、ノードViのクラスタIDはそのノードのクラスタIDに更新される。具体的なh%の値としては、例えば、40%、50%、60%、70%、80%等が採用される。
【0051】
ここでは、ノード12A~ノード12I間での9個のノードが、ノードViに隣接している。第1のクラスタ11Aでは、ノード12Aから12Fまでの6個のノードが、ノードViに隣接している。そして、第3のクラスタ11Cでは、1つのノード12IのみがノードViに隣接している。また、第4のクラスタ11Dでも、1つのノード12GのみがノードViに隣接している。従って、最も多くのノード12が隣接しているクラスタは、第1のクラスタ11Aであり、そのノード数の全隣接ノードに占める割合は約67%である。更に、ノードViの隣接ノードは全てがゲートウェイである。このことから、hの値を60以下にした場合は、この第1のクラスタ11AのクラスタIDであるpが、ノードViのクラスタIDとなる。
【0052】
図7(B)を参照して、上記クラスタリングにより、ノードViは第1のクラスタ11Aに取り込まれている。ノードViが取り込まれることにより、第1のクラスタ11Aは丸みを帯びた形状となり、総ノード数に対するゲートウェイ数が削減されている。
【0053】
このケースBは、ノードViが属するクラスタが細長くない場合でも、ゲートウェイであるノードViが、細長い他のクラスタに囲まれることで、ノードViがそのクラスタに取り込まれる。
【0054】
ケースC:図8を参照
このケースは、ノードVi自身が属するクラスタが細長い形状を有する場合のクラスタリングである。図8(A)はケースBのクラスタリングを行う前のクラスタを示し、図8(B)はクラスタリングを行った後のクラスタを示す図である。
【0055】
図8(A)を参照して、ここでは、第1のクラスタ11A~第4のクラスタ11Dが隣接している。第1のクラスタ11Aおよび第2のクラスタ11Bは、ノードViに隣接するノード12を2個含んでいる。また、第3のクラスタ11Cは、ノードViに隣接するノードを3個含んでいる。ここでは、ノードViは、それ自身が細長く延在する第4のクラスタ11Dの端部に位置するノードである。
【0056】
ノードViは、隣接ノードからHELLOパケットを受信して、クラスタIDを更新する。そして、ノードViと同じクラスタIDkを有する隣接ノードの数よりも、異なるクラスタIDを有する隣接ノードの数が多かった場合に、ノードViのクラスタIDは更新される。例えば、同じクラスタIDを有する隣接ノードの数が2個以下、且つ、異なるクラスタIDを有する隣接ノードが3個以上であった場合に、ノードViのクラスタIDは更新される。また、ノードViのクラスタIDは、全隣接ノードに対して数が最も多いノードが属するクラスタIDに変更される。更に、隣接ノードの全てがゲートウェイであることも、ノードViのクラスタIDを更新するための条件である。
【0057】
ここでは、ノードViと同じクラスタIDkを有するノードは、ノード12Iおよびノード12Hの2つのノードがある。そして、クラスタIDpを有する2つのノード12A、12Bが、ノードViに隣接している。更に、クラスタIDqを有する2つのノード12C、12Dが、ノードViに隣接している。更にまた、クラスタIDrを有する3つのノード12E、12Fおよび12Gが、ノードViに隣接している。
【0058】
上記のことから、ノードViとは異なるクラスタIDであるクラスタIDrを有する隣接ノードの数が最も多く、その個数は3個である。一方、ノードViと同じくラスタIDrを有するノードの数は2個である。従って、ノードViのクラスタIDを変更する上記の条件は満たされているので、ノードViのクラスタIDは、kからrに変更される。
【0059】
図8(B)を参照して、ノードViのクラスタIDはrに変更されて、第3のクラスタ11Cに取り込まれている。このことにより、第4のクラスタ11Dの形状は丸みを帯びる。
【0060】
上記したケースBでは、ノードViの隣接ノードが以下の条件を満たすと、ノードViと同様のクラスタIDが隣接している場合でも、そのクラスタIDが更新される。
・ゲートウェイであるノードのみに囲まれている。
・隣接ノードの大部分が、ノードViとは異なるクラスタIDを有している。
【0061】
また、ケースCでは、ノードViの隣接ノードが以下の条件を満たすと、ノードViと同様のクラスタIDが隣接している場合でも、そのクラスタIDが更新される。従って、ノードViのリンクが切れる可能性を回避することができる。
・ゲートウェイであるノードのみに囲まれている。
・ノードViと等しいクラスタIDの隣接ノードが、1つまたは2つしかない。
【0062】
上記したケースBは、ノードViが細長いクラスタに囲まれたときに、その細長いクラスタにノードViが取り込まれることで、クラスタの形状を丸くすることができる。また、ケースCでは、ノードViが属するクラスタ自身が細長いときに、クラスタの端部に位置するノードViが他のクラスタに属することで、クラスタの形状を丸くすることができる。従って、ケースBとケースCとは互いに補完する関係にあるので、両者を用いたクラスタリングを行うことにより、結果としてゲートウェイ数を削減することができる。従って、効率よく通信を行うことができるアドホックネットワークを構成することができる。
【0063】
次に、図9以降の図を参照して、上記本形態のクラスタリングをシミュレーションにより評価する。ここでは、本形態のクラスタリングを以下の2つの基準で評価する。
(1)ゲートウェイ数:総ゲートウェイ数とクラスタ毎の平均ゲートウェイ数をシミュレーション実験で計測した。
(2)クラスタの形状:一般的に、クラスタの形状が丸みを帯びているかどうかを量的に示すのは難しい。そのため、各ノードにおいて、そのノードのクラスタIDと同じクラスタIDを持つ平均隣接ノード数と、各ノードの平均隣接ノード数をシミュレーション実験で計測した。後者の平均数に対する前者の平均数の割合を計算した。
【0064】
全てのクラスタのサイズ(すなわち、ノード数)がほぼ等しい場合は、上記の割合が高くなるにつれ、クラスタの形状はより丸みを帯びたものになると言える。
【0065】
図9(A)および(B)に、本シミュレーションの条件を示す。各パラメータの組み合わせに対して10回ずつシミュレーション実験を行った。尚、以下の説明では上記したケース1、ケース2、ケース3を適用したクラスタリングを比較例「Previous」とする。また、G-40、G-50、G-60、G-70、G-80はそれぞれ、上記したケースBに於けるhの値が40、50、60、70、80である時の本形態のクラスタリングを示す。
【0066】
図10から図14を参照して、シミュレーション結果を説明する。
【0067】
図10はネットワーク中の総ゲートウェイ数を表している。これらの値は、0.25秒毎に計測したネットワーク中の総ゲートウェイ数の平均により求められている。シミュレーションの総ノード数は150であるため、比較法と本形態でのゲートウェイ数は、それぞれ全ノード数の約75%と60%に相当する。ゲートウェイ数は5m/sから20m/sまで徐々に減少しており、どの場合でも減少割合はほとんど同じである。従って、どのノード速度においても本形態では約20%ゲートウェイ数を削減している。
【0068】
図11を参照して、次に、各クラスタのゲートウェイ数に関する結果を示す。図11(A)と図11(B)は、それぞれ各クラスタの平均ゲートウェイ数と平均ノード数を表す。これらの値は、0.25秒毎に計測したネットワーク中の各クラスタ内のゲートウェイ数とノード数の平均により求められている。図11(A)と図11(B)で示されているように、各クラスタのゲートウェイ数とノード数はノード速度が速くなるにつれて増加しており、増加割合はどの場合でもほとんど同じである。本形態による各クラスタのゲートウェイ数は約20%減少している。一方、各クラスタのノード数は比較法でも本形態でもほぼ同数である。この結果は、本形態はクラスタサイズを維持しつつ、ゲートウェイの大幅な削減を実現していることを意味する。
【0069】
図12を参照して、クラスタの形状に関する結果を説明する。このグラフは、各ノードにおいて、ノードのクラスタIDと同じクラスタIDを持つ平均隣接ノード数を表している。本形態での同じクラスタIDをもつ隣接ノード数は、どのノード速度でも比較法より多く、ノードの速度が速い場合は約10%から20%多い。
【0070】
図13(A)は、平均隣接ノード数に対する上記の平均数の割合を示している。ノードの速度が速い場合は本形態における割合は約70%、比較法における割合は約55%となっているため、割合は約20%減少していることを示している。これらの結果から、本形態でのクラスタの形状は比較法と比較すると丸みを帯びていると言える。
【0071】
図13(B)を参照して、オーバヘッドに関する結果を説明する。比較法と本形態での制御パケット数を比較することで、本形態のオーバヘッドを考察する。このグラフは制御パケット数を示しており、本形態における制御パケット数は比較法とほとんど等しい。この結果から、本形態で新しく導入されたケースBおよびケースCは余分な制御パケットを生成してはいないと言える。この理由は、隣接クラスタに関する位置情報に基づいて自律的に各ノードがクラスタIDを変化させるからである。従って、ほとんど同じオーバヘッドであるにも関わらず、本形態によってゲートウェイ数が大幅に削減され、クラスタが丸みを帯びた形状になったことは注目に値する。
【0072】
図14(A)は、ケースBあるいはケースCの適用回数に対するケースBの割合を表している。本形態では、ケースBとケースCを適用させることでゲートウェイ数を削減した。ケースBの定義から、値hが小さくなるほどケースBはケースCより適用されるようになる。この図から、割合はノード速度に依存せず、hの値が小さくなるにつれて割合は増加しているが、増加割合は減少しており、hが50のときはほとんど0になっていることが分かる。ケースBとケースCは互いにほとんど依存性がないから、ケースBの値hが変わったときでさえケースCの適応回数ほとんど変化していない。最適なhの値は、上述した割合だけでなく以下のオシレーションも考慮して決定すべきである。ここで、あるノードのクラスタIDが変わってから2秒以内に再びそのノードのクラスタID変わることをオシレーションと定義する。オシレーションとは、非効率的なクラスタIDの変化を意味する。
【0073】
図14(B)は、ケースBとケースCによるクラスタID変更回数に対するオシレーション回数の割合を表している。この図から、hの値が小さくなるにつれて割合は増加している。従って、ケースBあるいはケースCの適用回数とオシレーションが起こる回数はトレードオフの関係にある。ケースBとケースCを多く適用し、かつ非効率的なオシレーションを可能な限り回避することがベターである。これら2つの観点から、60が適当なhの値と考えられる。
【図面の簡単な説明】
【0074】
【図1】本発明を適用したアドホックネットワークを示す図である。
【図2】本発明を適用したアドホックネットワークを構成するクラスタを示す図である。
【図3】本発明を適用したアドホックネットワークを構成するクラスタを示す図である。
【図4】(A)、(B)および(C)は、本発明を適用したクラスタリングの基本的方法を説明する図である。
【図5】本発明を適用したアドホックネットワークを構成するノードの役割を説明する図である。
【図6】(A)および(B)は、本発明を適用したクラスタリングを説明する図である。
【図7】(A)および(B)は、本発明を適用したクラスタリングを説明する図である。
【図8】(A)および(B)は、本発明を適用したクラスタリングを説明する図である。
【図9】(A)および(B)は、シミュレーションの条件を示す表である。
【図10】シミュレーション結果を示すグラフである。
【図11】(A)および(B)は、シミュレーション結果を示すグラフである。
【図12】シミュレーション結果を示すグラフである。
【図13】(A)および(B)は、シミュレーション結果を示すグラフである。
【図14】(A)および(B)は、シミュレーション結果を示すグラフである。
【符号の説明】
【0075】
10 アドホックネットワーク
11A~11D クラスタ
12A~12H ノード
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13