説明

ノード、通信方法、およびプログラム

【課題】アドホックネットワークにおいて、輻輳を緩和する技術を提供する。
【解決手段】ノードは、自身を始点ノードとして、該始点ノードからの電波が到達する範囲内にある1以上の隣接ノードと、終点ノードとの間の地理的な距離を算出する距離算出手段と、前記隣接ノードにおける通信量に応じて変動する変数を取得する変数取得手段と、前記距離算出手段により算出された前記距離と、前記変数取得手段により取得された前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを前記始点ノードと前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する選択手段と、を有する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、移動体通信機器などのノードがアドホックモードで通信する技術に関する。
【背景技術】
【0002】
アドホックネットワークにおいては、クライアントのノード自体にデータ中継機能を持たせることにより、それぞれのノードは、基地局やアクセスポイントなどの固定局を介さずに通信することができる。これらの固定局を要しないので、アドホックモードは、コンサート会場、イベント会場、または災害地などにおいて構築される一時的なネットワークや、自動車などにおける移動体通信に適している。但し、アドホックモードでは、各ノードが中継局となり、各ノードが移動することにより経路が変更されることがあるので、輻輳が発生しやすい。
【0003】
輻輳を緩和するため、特許文献1および特許文献2に記載のノードは、トラフィック量又は通信負荷が小さいノードを中継用のノードとして選択する構成としている。また、アドホックネットワークで一般的に用いられるGreedy方式では、隣接ノードのうち、通信対象である終点ノードと地理的な距離が最も近いノードを中継用のノードとして選択し、中継用のノード数を最小とすることで輻輳の緩和を図っている。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2005−142909号公報
【特許文献2】特開2006−211375号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、特許文献1および特許文献2に開示された構成では、通信量は小さいが、終点ノードから地理的に遠い位置のノードを中継用のノードとして選択してしまうことがある。この場合、中継するノード数が多くなってしまうが、ホップ数が大きいと、各ノード間の通信量の変動の影響を受けやすくなり、始点と終点との間の通信が不安定になりやすい。
【0006】
また、Greedy方式では、終点ノードに地理的に近いが、通信量が大きいノードを選択してしまうことがある。この場合も、通信量の増大により、輻輳が生じやすくなる。
【0007】
このため、アドホックネットワークにおいて、輻輳が十分に緩和されないという問題があった。
【0008】
本発明は、アドホックネットワークにおいて、始点と終点との間の安定な通信を確保するとともに、中継ノードにおける輻輳を緩和する技術を提供することを目的とする。
【課題を解決するための手段】
【0009】
上記目的を達成するために、本発明のノードは、自身を始点ノードとして、該始点ノードからの電波が到達する範囲内にある1以上の隣接ノードと、終点ノードとの間の地理的な距離を算出する距離算出手段と、前記隣接ノードにおける通信量に応じて変動する変数を取得する変数取得手段と、前記距離算出手段により算出された前記距離と、前記変数取得手段により取得された前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを前記始点ノードと前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する選択手段と、を有する。
【0010】
本発明の通信方法は、始点ノードからの電波が到達する範囲内にある1以上の隣接ノードと、終点ノードとの間の地理的な距離を算出し、前記隣接ノードにおける通信量に応じて変動する変数を取得し、前記距離と前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを始点ノードと前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する、通信方法である。
【0011】
本発明のプログラムは、コンピュータに、自身を始点ノードとして、該始点ノードからの電波が到達する範囲内にある1以上の隣接ノードと、終点ノードとの間の地理的な距離を算出する距離取得手順、前記隣接ノードにおける通信量に応じて変動する変数を取得する変数取得手順、及び前記距離算出手順により算出された前記距離と、前記変数取得手順により取得された前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを自身と前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する選択手順、を実行させるためのプログラムである。
【発明の効果】
【0012】
本発明によれば、ノードは、隣接ノードから終点ノードまでの地理的な距離と、通信量に応じて変動する変数とに基づいて中継ノードを選択するため、終点ノードから地理的に遠すぎるノードを選択しない結果、中継ノード数が少なくなり、通信が安定する。また、ノードは、通信量が多すぎるノードを選択しないので、輻輳が緩和される。
【図面の簡単な説明】
【0013】
【図1】第1の実施形態の通信システムの構成を示す全体図である。
【図2】第1の実施形態のノードの構成を示すブロック図である。
【図3】第1の実施形態のr_SEおよびr_REを示す図である。
【図4】第1の実施形態のノード情報の構成の一例を示す図である。
【図5】第1の実施形態の選択処理を示すフローチャートである。
【図6】第1の実施形態の中継ノード決定処理を示すフローチャートである。
【図7】第1の実施形態の例外処理を示すフローチャートである。
【図8】第1の実施形態の選択処理の結果を示す図である。
【図9】第1の実施形態の選択処理の結果を示すグラフである。
【図10】第1の実施形態の中継ノード決定処理を示すフローチャートである。
【発明を実施するための形態】
【0014】
(第1の実施形態)
本発明を実施するための第1の形態について図面を参照して詳細に説明する。
【0015】
図1は、本実施形態の通信システム1の構成を示す全体図である。通信システム1は、複数のノードがピア・ツー・ピアで相互に無線通信を行うための通信システムである。同図を参照すると、通信システム1は、複数のノード(例えば10、11、12、および13)を有する。これらのノードは、基地局やアクセスポイントを介さずに相互に無線通信を行う機能を有する通信機器である。具体的には、これらのノードは、アドホックモードで通信する機能を有するカーナビゲーション装置、PDA(Personal Digital Assistant)、携帯ゲーム機、またはノートパソコンなどの移動体通信機器である。
【0016】
アドホックモードで通信するとき、各ノードは、自身を始点ノードとして、それぞれの電波が到達する範囲内に、通信対象のノード(終点ノード)がないのであれば、電波の到達範囲内のいずれかの隣接ノードを中継して、終点ノードと無線通信を行う。
【0017】
ここで、始点ノードは、終点ノードへの経路が選択される際に、起点とされるノードである。データの送信元であるエッジのノードは、経路選択において最初の始点ノードとなる。そして、この送信元のノードが中継用の中継ノードを選択したのであれば、その中継ノードは、自身を始点ノードとして終点ノードへの経路を選択する。
【0018】
終点ノードは、始点ノードがデータの送信先とするエッジのノードである。
【0019】
中継ノードは、始点ノードと終点ノードとの間で送受信されるデータを中継するノードである。
【0020】
隣接ノードは、始点ノードからみて、同一セグメント内にある終点ノード以外のノードである。
【0021】
図1において、例えば、ノード10が、自身の電波が到達する範囲外のノード13と無線通信を行うとき、ノード10は、自身からの電波が到達する範囲内のノード11を中継ノードとして選択する。ノード11は、自身を起点ノードとして、ノード12を、中継ノードとして選択し、ノード10は、これらの中継ノード(11および12)を介して、終点ノード(13)と通信する。同図において、一点鎖線の円は、ノード10の電波の到達範囲Eである。
【0022】
図2を参照して、ノード10の構成について説明する。同図は、ノード10の構成を示すブロック図である。同図を参照すると、ノード10は、距離算出部101、パラメータ取得部103、および選択部105を有する。
【0023】
距離算出部101は、通信システム1における各ノード(10、11、12、および13等)の地理的な位置を取得する。例えば、各ノードがGPS(Global Positioning System)を利用して自身の位置を示す位置情報を取得し、取得した位置情報を相互に通知しあう。
【0024】
そして、図3に示すように、距離算出部101は、始点ノード(10)と終点ノード(D−1)との間の距離r_SEを算出し、r_SEが始点ノードの電波が到達する範囲の半径R以下であるか否かを判断する。r_SEがRより大きいと、終点ノードが始点ノードの電波到達範囲外にあるので、データを中継する中継ノードを介しなければ、始点ノードは終点ノードと通信することができない。同図に示すように、r_SEがRより大きければ、中継ノードを決定するために、距離算出部101は、半径R内の各隣接ノード(N−1、N−2)と終点ノード(D−1)との間の距離r_REを算出する。これらの距離(R_REおよびR_SE)の単位は、例えば、メートルとする。
【0025】
パラメータ取得部103は、終点ノード以外の各隣接ノードについて、通信量により変動するパラメータを取得する。例えば、パラメータとして各ノードに割り当てられたバッファのうち、使用中のバッファ数(使用中バッファ数)Bを求める。
【0026】
選択部105は、始点ノード(10)の電波が到達する範囲(半径R)内に終点ノードがないのであれば、半径R内の隣接ノードのうちのいずれかを終点ノードへ送信するデータを中継する中継ノードとして選択する。具体的には、選択部105は、半径R内の隣接ノードごとに、下記(1)式で示される選択関数Zを算出する。
【0027】
Z=r_RE−(r_SE―R)+AV/(MAXB+1−B)・・・(1)
ここで、r_REは、距離算出部101により算出された、隣接ノードと終点ノードとの間の地理的な距離(m)を所定の基準値(例えば、10m)で除した値である。r_SEは、距離算出部101により算出された、始点ノード(10)と終点ノードとの間の地理的な距離(m)を所定の基準値で除した値である。
【0028】
Rは、ノード10の電波が到達する範囲の半径(m)である。AVは、パラメータ取得部103により取得された、隣接ノードの使用中バッファ数Bの平均値である。MAXBは、隣接ノードが許容する最大のバッファ数(最大バッファ数)である。Bは、各隣接ノードの使用中バッファ数である。
【0029】
MAXBおよびRの値は、予めノード10のメモリ(不図示)内に記憶されている。
【0030】
この選択関数Zは中継ノードを選択するための指標となる。このZにおいて、地理的な距離と通信量とが指標を決める要素となる。いずれかの要素あるいは両方の要素に係数を乗算することにより、中継ノードの選択における各要素の寄与度を適切な比率に設定してもよい。例えば、通信量を重視する場合、通信量の寄与度が高くなるような重みづけをすればよい。
【0031】
なお、通信量に基づくパラメータを使用するのであれば、使用中バッファ数の代わりに、バッファサイズや空いているバッファ数などを求め、(1)式を変形して選択関数Zを算出してもよい。
【0032】
選択部105は、算出した選択関数Zが最小のノードを中継ノードとして選択する。但し、トラフィックの集中を避けるため、使用中バッファ数Bが、最大バッファ数MAXBを超えるノード、つまり通信負荷の高いノードは除く。また、ループの発生を防ぐため、一度通ったノード、すなわち、中継ノードとして既に選択されたノードは除外する。
【0033】
選択部105は、中継ノードとして選択したノードに、ノード情報1051を送信する。
【0034】
図4は、ノード情報1051の構成の一例を示す図である。同図を参照すると、ノード情報1051は、「ノード識別番号」、「隣接ノード数」、「隣接ノード識別番号」、「選択関数」、「選択フラグ」を示す情報を含む。
【0035】
「ノード識別番号」は、データの送信元のノードおよび中継ノードを識別するための番号である。「隣接ノード数」は、「ノード識別番号」の示すノードからの電波の到達範囲内にある隣接ノードの数である。「隣接ノード識別番号」は、隣接ノードを識別するための番号である。「選択関数」は、隣接ノードについて算出された選択関数Zの値である。「選択フラグ」は、中継ノードとして選択されたか否かを示すフラグであり、選択された場合「1」、選択されなかった場合「0」が設定される。
【0036】
例えば、ノード10によりノード11が中継ノードとして選択し、ノード11がノード12を中継ノードとして選択したとき、ノード11は、データの送信元のノード10および中継ノード11についての「ノード識別番号」等を示す情報を含むノード情報1051を、ノード12に送信する。
【0037】
選択部105は、中継ノードでない隣接ノードの使用中バッファ数BがいずれもMAXBを超える場合、すなわち、選択関数Zを算出した隣接ノードが1つもない場合、ノード情報1051を利用して中継ノードを選択する。具体的には、この場合、選択部105は、「ノード識別番号」の示すノードのうち、「隣接ノード数」が最大のノードを求める。そして、選択部105は、求めたノードを始点ノードとし、その始点ノードに対応する「選択フラグ」が「0」のノードのうち、「選択関数」が最小のノードを、始点ノードに対応する中継ノードとして選択する。
【0038】
例えば、ノード11により、ノード12が中継ノードとして選択されたものの、ノード12の半径R内の隣接ノードはいずれも、中継ノード11を除き、使用バッファ数BがMAXB以上であった場合、これらの隣接ノードについてZは算出されない。この場合、ノード12は、「ノード識別番号」が10、11のノードのうち、「隣接ノード数」が最大のノード11を始点ノードとする。そして、ノード12は、ノード11の半径R内の「選択フラグ」が「0」の隣接ノードのうち、「選択関数」が最小のノード12aを、ノード11に対応する中継ノードとして選択する。
【0039】
ノード10は、選択部105により選択された中継ノードを介して終点ノードとアドホックモードで通信を行う。
【0040】
ノード11、12、および13の構成は、ノード10と同様である。
【0041】
次に、図6〜図7を参照して、ノード10の動作について説明する。図5は、ノード10の実行する選択処理を示すフローチャートである。選択処理は、始点ノード(10)から終点ノードへの経路を求める処理である。選択処理は、ノード10の電源が投入されたときに開始する。
【0042】
なお、ノード10は、所定のアプリケーションが開始されたときや、始点ノードと終点ノードとが通信を行うときに、選択処理を開始してもよい。
【0043】
選択処理において、ノード10は、ノード情報(1051)を受信する(ステップS1)。ただし、ノード10は、自身がデータの送信元のノードであれば、ステップS1を実行しない。距離算出部10は、始点ノード(10)と終点ノードとの間の地理的な距離r_SEを算出する(ステップ2)。距離算出部10は、r_SEがR以下であるか否かを判断する(ステップ3)。r_SEがRより大きければ、すなわち、終点ノードが電波の到達範囲になければ(ステップS3:NO)、距離算出部101は、半径R内の各隣接ノードと終点ノードとの間の地理的な距離r_REを算出する(ステップS4)。そして、パラメータ取得部103は、半径R内の各隣接ノードの使用中バッファ数Bを取得する(ステップS5)。選択部105は、中継ノード決定処理を実行する(ステップS6)。r_SEがR以下である場合(ステップS3:YES)、またはステップS6の後、選択部105は、ノード情報1051において、選択した中継ノードの「選択フラグ」を「1」にして、その中継ノードに送信する(ステップS7)。ステップS7の後、ノード10は、選択処理を終了する。
【0044】
図6は、中継ノード決定処理を示すフローチャートである。選択部105は、半径R内の隣接ノードのいずれか1つを選択し、その隣接ノードの使用中バッファ数Bが、最大バッファ数MAXBより大きい否かを判断する(ステップS61)。BがMAXB以下であれば(ステップS61:NO)、隣接ノードが中継ノードとして選択されたか否か、即ち、始点ノードから終点ノードへの経路において一度通ったノードであるか否かを判断する(ステップS62)。隣接ノードが一度通ったノードでなければ(ステップS62:NO)、選択部105は、上記(1)式を使用して、その隣接ノードの選択関数Zを算出する(ステップS63)。
【0045】
隣接ノードのBがMAXBより大きい場合(ステップS61:YES)、隣接ノードが一度通ったノードである場合(ステップS62:YES)、またはステップS63の後、選択部105は、半径R内にある隣接ノードの全てについてステップS91〜S95の処理を行ったか否かを判断する(ステップS64)。半径R内の隣接ノードの全てについて処理していない場合(ステップS64:NO)、選択部105は、他の隣接ノードについてステップS91〜S95の処理を実行する。
【0046】
半径R内の隣接ノードの全てについて処理したのであれば(ステップS64:YES)、Zを算出したノードが1以上であるか否かを判断する(ステップS65)。Zを算出したノードが1つもなかったのであれば(ステップS65:NO)、選択部105は、例外処理を実行する(ステップS66)。
【0047】
Zを算出したノードが1以上である場合(ステップS65:YES)、選択部105は、Zを算出した隣接ノードのうち、Zが最小のノードを中継ノードとして選択する(ステップS67)。ステップS66またはステップS67の後、選択部105は、中継ノード決定処理を終了する。
【0048】
図7は、例外処理を示すフローチャートである。同図を参照すると、選択部105は、ノード情報1051の示すノード、即ちデータの送信元のノードまたは中継ノードのうち、そのノードの半径R内の隣接ノード数が最大のノードを求め、求めたノードを始点ノードとする(ステップS661)。選択部105は、ノード情報1051において、始点ノードに対応する隣接ノードのうち、選択フラグが「0」で、且つ、「選択関数」が算出されたノードがあるか否かを判断する(ステップS662)。
【0049】
選択フラグが「0」で、且つ、「選択関数」が算出されたノードがあれば(ステップS662:YES)、選択部105は、「選択フラグ」が「0」の隣接ノードのうち、「選択関数」が最小のノードを、始点ノードに対応する中継ノードとして選択する(ステップS663)。ステップS663の後、選択部105は、例外処理を終了する。
【0050】
選択フラグが「0」で、且つ、「選択関数」が算出されたノードがなければ(ステップS662:NO)、選択部105は、残りのノードのうち、隣接ノード数が最大のノード、すなわち、次に隣接ノード数が大きいノードを始点ノードとし(ステップS664)、ステップS662に戻る。
【0051】
なお、ステップS662において、ステップS661において、半径R内の隣接ノード数が最大のノードを求めているが、選択部105は、隣接ノード数にかかわりなく、直前に選択された中継ノードを始点ノードとしてもよい。この場合、直前の隣接ノードにおいて、2番目に小さな選択関数が算出された隣接ノードが、中継ノードとして選択される。
【0052】
また、ステップS662において、選択部105は、ノード情報1051から既に算出された「選択関数」を読み出す構成としているが、再度、各ノードの使用中バッファ数Bを取得し、各隣接ノードの選択関数Zを算出しなおす構成としてもよい。
【0053】
また、ノード情報1051において、Zを算出したノードが1つもない場合、選択部105は、(1)式を使用しないで中継ノードを選択してもよい。この場合、選択部105は、例えば、Greedy方式を使用して、中継ノードを使用してもよいし、単に使用中バッファ数Bが最小のノードを選択してもよい。
【0054】
続いて、図8および図9を参照して、ノード10による選択処理の動作結果について説明する。
【0055】
図8は、通信システム1における各ノードの位置および使用中バッファ数の一例を示した図である。同図を参照すると、通信システム1は、ノード10、N−1、N−2、N−3、N−4、およびD−1を有する。このうち、ノード10がノードD−1と無線通信を行う場合について考える。
【0056】
ノード10にとって、同一セグメント内にある終点ノード以外のノードN−1、N−2、N−3、N−4は隣接ノードである。ノード10が最終的なデータの送信先とするノードD−1は終点ノードである。
【0057】
ノード10は、自身と終点ノードD−1との距離であるr_SEを算出する(ステップS1)。r_SEは100mと算出され、ノード10の電波の到達範囲Rは80mである。r_SEがRより大きいので(ステップS3:NO)、ノード10は、半径R内の各隣接ノードN−2、N−3、およびN−4について、隣接ノードと終点ノードとの間の距離r_REを算出する(ステップS4)。隣接ノードN−1は、ノード10の半径R内にないので、中継ノードの選択対象から除かれる。
【0058】
そして、ノード10は、半径R内の各隣接ノードN−2、N−3、およびN−4について、使用中バッファ数Bを求める(ステップS5)。ここで、ノードN−2、N−3、およびN−4のそれぞれのBは、5、22、および10である。
【0059】
ノード10は、BがMAXB以下であり(ステップS61:NO)、一度通ったノードでない(ステップS62:NO)、半径R内の隣接ノードのそれぞれについて選択関数Zを算出する(ステップS63)。最大バッファ数MAXBは21であり、隣接ノードN−3のBは22でMAXBより大きいので、ノード10は、隣接ノードN−3を除き、N−2およびN−4についてZを算出する。
【0060】
隣接ノードN−2およびN−4のr_REは、それぞれ80mおよび60mであり、Bは、それぞれ5および10である。また、基準値Sは10mである。(1)式に、これらの値を代入することにより、ノード10は、隣接ノードN−2およびN−4のZとして、11および14を算出する(ステップS63)。そして、ノード10は、Zが最小の隣接ノードN−2を中継ノードとして選択する(ステップS67)。図6において、斜線部分は、選択されたノードである。
【0061】
このように、ノード10は、Zを算出して、終点ノードまでの距離r_REが比較的遠く、且つ、使用中バッファ数Bが比較的小さいノードを選択する。このため、ノード10は、終点ノードまでの距離が遠すぎるノードを選択しないので、中継ノード数が少なくなり、通信が安定する。また、ノード10は、通信量が大きすぎるノードを選択しないので、輻輳が緩和される。
【0062】
これに対して、(1)式を使用せずに、単にr_REが小さいノードを選択するGreedy方式を用いる場合、中継ノードとしてノードN−4がノード10により選択される。しかし、ノードN−4の使用中バッファ数Bは、ノードN−2よりも多いので、N−4を中継ノードとすると、輻輳が生じやすくなることがある。
【0063】
また、(1)式を使用せずに、単にBの小さいノードを選択する方法を使用すると、終点ノードから地理的に遠いノードが選択され、中継ノード数が多くなる結果、輻輳が生じやすくなることがある。
【0064】
図9は、Greedy方式と(1)式を使用する方式とを比較した結果を示す図である。詳細には、同図は、一辺が1000mの正方形の空間内においてノードを1000個、各ノードの電波の到達距離Rを200m、基準値Sを10mとし、これらのノードについてランダムに始点ノードと終点ノードを3000回選択し、それぞれの方式で中継ノードを選択して通信したときの、1000個のノードそれぞれの使用中バッファ数Bをシミュレートした結果である。同図の縦軸は、使用中バッファ数B、横軸はノードそれぞれに付されたノード識別番号である。同図の実線は、(1)式を使用した場合の折れ線グラフであり、点線は、Greedy方式を使用した場合の折れ線グラフである。また、最大バッファ数MAXBは21である。
【0065】
図9を参照すると、Greedy方式を使用した場合は、Bが最大バッファ数MAXBに達するノードが全体の約5%に達しており、輻輳が生じていることが確認できる。一方、(1)式を使用した場合はBがMAXBに達するノードはなく、輻輳が緩和されていることが確認できる。
【0066】
以上説明したように、本実施形態によれば、隣接ノードと終点ノードとの間の地理的な距離r_REと、使用中バッファ数Bとに基づいて、具体的には、これらの値の和が最小のノードを中継ノードとして選択するので、終点ノードまでの地理的な距離が遠すぎたり、通信量が多すぎるノードを中継して各ノードが通信することがなくなる結果、アドホックネットワークにおいて輻輳が緩和される。
【0067】
また、ノード10、通信量に応じて変動するパラメータとして、使用中バッファ数を取得する。輻輳はノードがバッファ数を使いきったときに発生するので、使用中バッファ数が比較的低いノードを中継することにより、輻輳を緩和することができる。
【0068】
ノード10は、使用中バッファ数Bが最大バッファ数MAXBに満たないノードを選択するので、輻輳が生じているノードを誤って選択することがなく、輻輳を確実に緩和できる。
【0069】
そして、ノード10は、一度通ったノードを中継ノードとして選択しないので、ループが生じることがなくなる。
【0070】
Zが算出された隣接ノードが1つもなければ、選択部105は、ノード情報1051において、「隣接ノード数」が最大のノードを始点ノードとして、その始点ノードに対応する隣接ノードのうち、「選択フラグ」が「0」で、「選択関数」が最小のノードを中継ノードとして選択する。このため、隣接ノードの使用中バッファ数BがいずれもMAXB以上で、Zが算出されない場合でも、選択部105は、ノード情報1051を使用して中継ノードを選択することができる。
【0071】
(第2の実施形態)
本発明の第2の実施形態について、図10を参照して説明する。本実施形態のノード10の構成は、第1の実施形態の構成と同様である。同図は、本実施形態の選択処理を示すフローチャートである。
【0072】
図10を参照すると、本実施形態の選択処理は、ステップS5の代わりに、パラメータ算出部103がパラメータとして各ノードの単位時間当たりの受信データ量(通信負荷)を求める、ステップS5aを実行する。本実施形態のノード10は、通信量に応じて変動するパラメータとして通信負荷を求める点で、第1の実施形態と異なる。
【0073】
そして、選択部105は、(1)式において、バッファ数B、最大バッファ数MAXBの代わりに、通信負荷および許容される最大の通信負荷を代入してZを算出する。
【0074】
通信負荷の増大によっても輻輳が生じうるので、本実施形態によれば、通信負荷が比較的低いノードを中継することでノード10は輻輳を緩和することができる。
【0075】
なお、ノード10は通信量に応じて変動するパラメータであれば、通信量自体を求めてもよいし、他のパラメータを(1)式に使用してもよい。ノード10は、通信量に応じて変動する、複数の種類のパラメータを組み合わせて選択関数Zを算出してもよい。
【0076】
また、選択関数Zは、(1)式に限らず、隣接ノードと終点ノードとの距離が比較的大きく、且つ、通信量が比較的小さなノードを選択できるものであれば、他の式を使用して算出してもよい。例えば、選択部105は、それぞれの隣接ノードについて、隣接ノードから終点ノードまでの距離(r_RE)と、通信量に基づくパラメータ(B)との積を、求め、その値が最小のノードを中間ノードとして選択してもよい。
【0077】
図5〜図7、および図10に示したフローチャートの一部または全部の処理はコンピュータプログラムの実行により実現することもできる。
【符号の説明】
【0078】
1 通信システム
10、11、12、13 ノード
101 距離算出部
103 パラメータ取得部
105 選択部
B 使用中バッファ数
E 電波到達範囲
D−1 終点ノード
N−1、N−2、N−3、N−4 隣接ノード
R 半径
r_SE、r_RE 距離
S1〜S9、S91〜S99、S7a ステップ

【特許請求の範囲】
【請求項1】
自身を始点ノードとして、該始点ノードからの電波が到達する範囲内にある1以上の隣接ノードの地理的な位置と、終点ノードの地理的な位置とを取得する位置取得手段と、
前記隣接ノードにおける通信量に応じて変動する変数を取得する変数取得手段と、
前記位置取得手段により取得された1以上の前記隣接ノードの位置および前記終点ノードの位置と、前記変数取得手段により取得された前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを前記始点ノードと前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する選択手段と、
を有するノード。
【請求項2】
前記変数は、前記通信量の増大に伴い増大する変数であり、
前記選択手段は、1以上の前記隣接ノードのうち、1以上の前記隣接ノードと前記終点ノードとの間の地理的な距離と、前記変数取得手段により取得された前記変数との和を算出し、該和が最小となるノードを前記中継ノードとして選択する、請求項1のノード。
【請求項3】
前記変数取得手段は、前記隣接ノードが使用している使用中バッファ数を前記変数として取得する、請求項2に記載のノード。
【請求項4】
前記選択手段は、前記和が最小となるノードであって、且つ、前記変数取得手段により取得された前記使用中バッファ数が、前記隣接ノードが許容する最大の値である最大バッファ数に満たないノードを前記中継ノードとして選択する、請求項3に記載のノード。
【請求項5】
前記選択手段は、前記和が最小となるノードであって、前記中継ノードとして選択されたことがなく、且つ、前記データの送信元のノードでない前記隣接ノードを前記中継ノードとして選択する、請求項2又は3に記載のノード。
【請求項6】
前記選択手段は、前記和が算出された前記隣接ノードがなければ、前記データの送信元のノード又は前記中継ノードのうち、該ノードの電波が到達する範囲内にある隣接ノードの数が最大のノードを求め、求めた該ノードを始点ノードとして、該始点ノードの電波が到達する範囲内にある、前記中継ノードを除く隣接ノードのうち、該隣接ノードに対応する前記和が最小のノードを、該始点ノードと前記終点ノードとの間のデータを中継する中継ノードとして選択する、請求項2乃至5のいずれか1項に記載のノード。
【請求項7】
前記選択手段により選択された前記中継ノードを通じて前記終点ノードとアドホックモードで通信する通信手段を更に有する、請求項1乃至6のいずれか1項に記載のノード。
【請求項8】
前記位置取得手段は、前記隣接ノードと前記終点ノードとの間の地理的な距離をr_RE、前記始点ノードと該終点ノードとの間の地理的な距離をr_SEとして算出し、
前記変数取得手段は、1以上の前記隣接ノードに対応する前記使用中バッファ数の平均値をAVとして算出し、該隣接ノードごとの前記使用中バッファ数をBとして取得し、
前記選択手段は、自身からの電波が到達する範囲の半径をR、前記隣接ノードにおいて許容される最大の値である最大バッファ数をMAXBとして、
Z=r_RE−(r_SE―R)+AV/(MAXB+1−B)
を前記和とする、請求項3乃至7のいずれか1項に記載のノード。
【請求項9】
始点ノードからの電波が到達する範囲内にある1以上の隣接ノードの地理的な位置と、終点ノードの地理的な位置とを取得し、
前記隣接ノードにおける通信量に応じて変動する変数を取得し、
1以上の前記隣接ノードの位置および前記終点ノードの位置と、前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを始点ノードと前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する、通信方法。
【請求項10】
コンピュータに、
自身を始点ノードとして、該始点ノードからの電波が到達する範囲内にある1以上の隣接ノードの地理的な位置と、終点ノードの地理的な位置とを取得する位置取得手順、
前記隣接ノードにおける通信量に応じて変動する変数を取得する変数取得手順、及び
前記位置取得手順により取得された1以上の前記隣接ノードの位置および前記終点ノードの位置と、前記変数取得手順により取得された前記変数とに基づいて、1以上の前記隣接ノードのうち、いずれかを自身と前記終点ノードとの間で送受信されるデータを中継する中継ノードとして選択する選択手順、
を実行させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate


【公開番号】特開2013−21738(P2013−21738A)
【公開日】平成25年1月31日(2013.1.31)
【国際特許分類】
【出願番号】特願2012−241783(P2012−241783)
【出願日】平成24年11月1日(2012.11.1)
【分割の表示】特願2008−136492(P2008−136492)の分割
【原出願日】平成20年5月26日(2008.5.26)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】