(57)【特許請求の範囲】
【請求項１】
互いに隣接した複数個の無線通信装置よりなるブルートゥースグループアドホックネットワークにおける通信方法において、
一つのピコネットでだけスレーブであるスレーブノード、一つのピコネットでだけマスタであるマスタノード、二つのピコネットにおいて全てスレーブで動作するスレーブ−スレーブジョイントノード、及び一のピコネットにおいてスレーブで動作すると共に他のピコネットにおいてマスタで動作するマスタ−スレーブジョイントノードを含む複数のピコネットで構成され、少なくとも２個以上のピコネットがスレーブ−スレーブジョイントノードにより連結されるようにしてネットワークを形成する段階と、
前記ジョイントノードが、Ｌ２ＣＡＰ上位層から通知されるルーティングトリガーを受信すれば、前記ジョイントノードは前記形成されたネットワークに属する前記ピコネットをブリッジングする段階とを備え、
前記ネットワークを形成する段階は、Ｌ２ＣＡＰとＢＮＥＰとの間に位置しているネットワークフォメーションプロトコルによって、ＩＰ層に位置しているネットワークルーティングプロトコルの案内の下で、いずれのノードが、前記スレーブノード、前記マスタノード、前記スレーブ−スレーブジョイントノードおよび前記マスタ−スレーブジョイントノードであるかを決める段階を含むことを特徴とするブルートゥースグループアドホックネットワークにおける通信方法。
【請求項２】
前記スレーブノードは新たなマスタにより発見されるようインクワイアリスキャンを規則的に行ない、
ルーティングトリガー信号を受信すれば、近くのネットワークを探すためにインクワイアリを行なうことを特徴とする請求項１に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項３】
前記スレーブノードは新たなマスタにより発見され新たなリンクが追加されればジョイントノードになることを特徴とする請求項１に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項４】
前記マスタノードは通信可能範囲に位置するフリーノードを発見するために規則的にインクワイアリを行ない、
前記マスタノードが別のマスタノードと互いに無線範囲にある際、別のマスタノードにより発見されるよう規則的にインクワイアリスキャンを行ない、
他のマスタノードによって発見されればスレーブノードに転換されることを特徴とする請求項１に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項５】
前記ルーティングトリガーはルーティングプロトコルまたは管理部から発生される信号であって、少なくともRoute REQuest(RREQ)、RouteREPly(RREP)またはRoute ERRor(RERR)のうちいずれか一つであることを特徴とする請求項１に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項６】
同一のピコネットまたは同一のネットワークに属するノードのデータ構造は、テーブルで記録されており、前記テーブルに基づきルーティングが行なわれることを特徴とする請求項１に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項７】
前記テーブルは新たなノードまたは新たなネットワークが発見されたときに更新され、リンクが失われれば該当ノードを前記テーブルから削除することを特徴とする請求項６に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項８】
前記テーブルには少なくともマスタノードＢＤ−ＡＤＤＲ、スレーブノードＢＤ−ＡＤＤＲ、コネクション寿命、ピコネットまたはネットワーク寿命、及びスレーブ−スレーブジョイントノードのＢＤ−ＡＤＤＲが記録されていることを特徴とする請求項６に記載のブルートゥースグループアドホックネットワークにおける通信方法。
【請求項９】
請求項１ないし請求項８のいずれか一項に記載の通信方法で形成されたネットワークを利用したブルートゥースオンデマンドルーティング方法において、
前記ネットワークは、前記スレーブノード、マスタノード、スレーブ−スレーブジョイントノード、及びマスタ−スレーブジョイントノードのいずれかであるソースノードと宛先ノード及び互いに独立した複数個のノードを備え、
前記ソースノードがルート要求メッセージを送信して前記ソースノードから前記宛先ノードへの全ての中間ノードが前記マスタ−スレーブジョイントノードである多重フォワード経路を設定する段階と、
前記ルート要求メッセージを受信した宛先ノードが前記多重設定されたフォワード経路のうちいずれか一つに沿って前記ソースノードにルート応答メッセージを送信して、前記多重設定されたいずれか１つのフォワード経路を構成する隣接した２つのマスタノードの間に前記スレーブ−スレーブジョイントノードを介在させたバックワード経路を設定する段階とを含み、
前記設定されたバックワード経路を通して前記ソースノードと宛先ノードとの間に最適の経路であるルートが形成され、前記多重フォワード経路に予め定められたライフタイムが尽きると、前記多重フォワード経路で前記バックワード経路を形成しない経路の連結がパークされることを特徴とするブルートゥースオンデマンドルーティング方法。
【請求項１０】
前記フォワード経路設定段階は、
前記ソースノードが宛先ノードへのルートを必要とし、前記ルートが少なくとも一つ以上利用可能な場合、ルート要求メッセージをブロードキャストする段階と、
前記ソースノードから次にホッピングされる少なくとも一つ以上の中間ノードが、前記ルート要求メッセージが前記宛先ノードに到達するまで、前記ブロードキャストされたルート要求メッセージを受信し、さらに次のホッピングノードに前記ルート要求メッセージを伝達する段階と、を含むことを特徴とする請求項９に記載のブルートゥースオンデマンドルーティング方法。
【請求項１１】
前記ソースノードと前記宛先ノードとの間に連結が設定されればソースノードはマスタとなり、その隣接する中間ノードはスレーブとなり、前記ルート要求メッセージは前記マスタからスレーブに転送されることを特徴とする請求項９に記載のブルートゥースオンデマンドルーティング方法。
【請求項１２】
フォワード経路に沿う全ての中間ノードはマスタスレーブジョイントノードであることを特徴とする請求項９に記載のブルートゥースオンデマンドルーティング方法。
【請求項１３】
前記ルート要求メッセージは、隣接ノードを発見して連結するためにソースノードでインクワイアリ動作を開始するルーティングトリガーであることを特徴とする請求項９に記載のブルートゥースオンデマンドルーティング方法。
【請求項１４】
前記ルーティングトリガーは、ブルートゥースのプロトコルでルーティング階層または管理部から提供されることを特徴とする請求項１３に記載のブルートゥースオンデマンドルーティング方法。
【請求項１５】
前記バックワード経路設定段階は、
前記ルート要求メッセージを受信した宛先ノードが前記形成されたフォワード経路のうちいずれか一つに沿って前記ソースノードに向かってルート応答メッセージを転送する段階と、
前記宛先ノードで前記ソース方向にホッピングされる中間ノードが、前記ルート応答メッセージが前記ソースノードに到達するまで、前記ルート応答メッセージを受信し、さらに次のホッピングノードに前記ルート応答メッセージを伝達する段階と、を備えることを特徴とする請求項９に記載のブルートゥースオンデマンドルーティング方法。
【請求項１６】
前記ルート応答メッセージは、マスタノードの間にスレーブ−スレーブジョイントノードを介在させるためにマスタ／スレーブスイッチングを開始するルーティングトリガーであることを特徴とする請求項１５に記載のブルートゥースオンデマンドルーティング方法。
【請求項１７】
前記マスタ／スレーブスイッチングは、前記宛先ノードから偶数離隔されたノードとその次のホッピングノードの間で行なわれることを特徴とする請求項１６に記載のブルートゥースオンデマンドルーティング方法。
【請求項１８】
ブルートゥースのプロトコルにおいてルーティング機能を行なうルーティングは、ネットワーク形成と独立して、ＢＮＥＰ階層またはＩＰ階層のうちいずれか一つに形成されることを特徴とする請求項１５に記載のブルートゥースオンデマンドルーティング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はブルートゥースグループにおける通信方法に関し、さらに詳しくはピコネットの数を最小化しネットワークを形成するブルートゥースオンデマンドルーティング方法、並びにブルートゥースグループアドホックネットワークにおける通信方法に関する。
【０００２】
【従来の技術】
まず、ブルートゥースネットワークにおける従来のネットワークフォメーションアルゴリズムについて説明する。
Salonidis等はスキャタネットフォーメーションのためのブルートゥーストポロジコンストラクションプロトコル(Bluetooth Topology Construction Protocol:BTCP)を提案した。このＢＴＣＰでは、３つの段階がある。一番目の段階では、対称リンクフォメーションのための状態変更技術を用いて、全てのノードについて情報を有している調整者(コーディネータ)が選択される。二番目の段階において、選択された調整者は各ノードの役目を決める。三番目の段階において、実質的な連結が行なわれる。ＢＴＣＰでは、全てのノードが互いの無線範囲内に位置するという条件に基づく。
【０００３】
このような条件の下で、そして規定された全てのノードに基づき、Aggarwal等は、ネットワークを個別的なピコネットクラスタにグループ化した。全てのノードに対する情報を有している、いわゆる「スーパマスタ(super-master)」が選択されれば、ピコネットの再構成過程及びピコネット間の連結がこのスーパリーダーの監視により、または調整により行なわれる。
【０００４】
Law等は、Ｏ(log n)倍の複合度及びＯ(ｎ)のメッセージ複合度を有する一段階スキャタネットフォメーションアルゴリズムを開示した。これによれば、全てのノードがただ一つのリーダーを有するよう分離される。その構成要素は、互いに連結されたノード群である。リーダーは、「シーク/スキャン(seek and scan)」段階に入り、選択的に「連結(connection)」、「マージ(merge)」、「ミティゲート(mitigate)」または装置移動などのプロセスを実行する。しかし、Law等が開示したことによると、全てのノードが互いの通信範囲内になければならないという制限が問題である。
【０００５】
ブルーツリーアルゴリズム(Blue-tree algorithm)では、ノードは、自分がルートノード(root node)であるか否かと、自分のワンホップ(one hop)周辺機器を知っていなければならない。
【０００６】
Tan等はそれぞれルート及びループフリー経路(loop free path)を一つずつ具備することにより、パケットのルーティング及びスケジュール調整を単純化した。しかし、このようなツリー型構造では、ジョイントノードが一つのピコネットではマスタであり、別のピコネットではスレーブなので二つのピコネットが互いに密接になる場合がある。
【０００７】
ところが、前述した全てのアルゴリズムが実際のトラフィック状況(traffic condition)とトラフィックリクエスト(traffic request)は考慮しないまま、データリンク層における単独の動作にのみスキャタネットフォーメーションの焦点を合わせている。１対１接続（point-to-point link）が、物理的リンクのレベルでスキャタネット全体で接続されたかを確かめるため、トラフィックがほとんどないようなときにも、「アクティブ」状態は、初期のスキャタネットフォーメーションの間、またはその後に周期的に再開されなければならない。
【０００８】
つまり、不要なリンク維持によって、無線通信機器において大事な存在である電力が浪費されている。このような問題に気づいたRaman等はオンデマンド型(on-demand)ルーティングを備えたスキャタネットリンクフォメーションの層間最適化理論を出してきた。しかし、これまでのところ、さらなる詳細な分析や見解については報告されていない。
【０００９】
【特許文献１】
特表２０００−５０２２２２号公報
【００１０】
BhagwatとSegallは形成されたスキャタネットでパケットのトラフィックをルーティングできるルーティングベクトル方法を提案した。Liu Y．は新たに定義されたLMP命令言語を使用したネットワークフォメーションを使った。しかし、模擬テストで発見された通り、ブルートゥース内の多くのインクワイアリによりトラフィックの待機時間がかなり延びた。
【００１１】
【発明が解決しようとする課題】
本発明は前述した問題点を解決するために案出されたもので、本発明に係る第１目的は、ネットワークフォメーションとルートを独立的に維持しつつピコネットの数も最小化できるブルートゥースグループアドホックネットワークにおける通信方法を提供する。
【００１２】
また、本発明に係る第２目的は、ブルートゥースのアドホックネットワークシステムでソースが希望する場合だけルートが形成されると共に、バッテリパワーを節約するブルートゥースオンデマンドルーティング方法を提供する。
【００１３】
【課題を解決するための手段】
前述した第１目的を達成するための本発明に係るブルートゥースグループアドホックネットワークにおける通信方法は、互いに隣接した複数個の無線通信装置よりなるブルートゥースグループアドホックネットワークにおける通信方法において、一つのピコネットでだけスレーブであるスレーブノード、一つのピコネットでだけマスタであるマスタノード、２個のピコネットにおいて全てスレーブで動作するスレーブ−スレーブジョイントノード、及び一のピコネットにおいてスレーブで動作すると共に他のピコネットにおいてマスタで動作するマスタ−スレーブジョイントノードを含む複数のピコネットで構成され、少なくとも２個以上のピコネットがスレーブ−スレーブジョイントノードにより連結されるようにしてネットワークを形成する段階と、前記ジョイントノードが、Ｌ２ＣＡＰ上位層から通知されるルーティングトリガーを受信すれば、前記ジョイントノードは前記形成されたネットワークに属する前記ピコネットをブリッジングする段階とを備え、前記ネットワークを形成する段階が、Ｌ２ＣＡＰとＢＮＥＰとの間に位置しているネットワークフォメーションプロトコルによって、ＩＰ層に位置しているネットワークルーティングプロトコルの案内の下で、いずれのノードが、前記スレーブノード、前記マスタノード、前記スレーブ−スレーブジョイントノードおよび前記マスタ−スレーブジョイントノードであるかを決める段階を含むことを特徴とする。
【００１４】
また、前記スレーブノードは新たなマスタにより発見されるようインクワイアリスキャンを規則的に行ない、ルーティングトリガー信号を受信すれば、近くのネットワークを探すためにインクワイアリを行なうことが望ましい。
【００１５】
そして、前記スレーブノードは新たなマスタにより発見され新たなリンクが追加されればジョイントノードになることが望ましい。
【００１６】
また、前記マスタノードは通信可能範囲に位置するフリーノードを発見するために規則的にインクワイアリを行ない、前記マスタノードが別のマスタノードと互いに無線範囲にある際、別のマスタノードにより発見されるよう規則的にインクワイアリスキャンを行ない、他のマスタノードによって発見されればスレーブノードに転換されることが望ましい。
【００１７】
また、前記ルーティングトリガーはルーティングプロトコルまたは管理部で発生する信号であって、少なくともRoute REQuest(RREQ)、Route REPly(RREP)またはRoute ERRor(RERR)のうちの一つであることが望ましい。
【００１８】
また、同一のピコネットまたは同一のネットワークに属するノードのデータ構造は、テーブルで記録されており、前記テーブルに基づきルーティングが行なわれることが望ましい。
【００１９】
また、前記テーブルは新たなノードまたは新たなネットワークが発見されたときに更新され、リンクが失われれば該当ノードを前記テーブルから削除することが望ましい。
【００２０】
そして、前記テーブルには、少なくともマスタノードＢＤ−ＡＤＤＲ、スレーブノードＢＤ−ＡＤＤＲ、コネクション寿命、ピコネットまたはネットワーク寿命、及びスレーブ−スレーブジョイントノードのＢＤ−ＡＤＤＲが記録されていることが望ましい。
【００２１】
前述した第２目的を達成するための本発明に係るブルートゥースオンデマンドルーティング方法は、請求項１ないし請求項８のいずれか一項に記載の通信方法で形成されたネットワークを利用したブルートゥースオンデマンドルーティング方法において、前記ネットワークは、前記スレーブノード、マスタノード、スレーブ−スレーブジョイントノード、及びマスタ−スレーブジョイントノードのいずれかであるソースノードと宛先ノード及び互いに独立した複数個のノードを備え、前記ソースノードがルート要求メッセージを送信して前記ソースノードから前記宛先ノードへの全ての中間ノードが前記マスタ−スレーブジョイントノードである多重フォワード経路を設定する段階と、前記ルート要求メッセージを受信した宛先ノードが前記多重設定されたフォワード経路のうちいずれか一つに沿って前記ソースノードにルート応答メッセージを送信して、前記多重設定されたいずれか１つのフォワード経路を構成する隣接した２つのマスタノードの間に前記スレーブ−スレーブジョイントノードを介在させたバックワード経路を設定する段階とを含み、前記設定されたバックワード経路を通して前記ソースノードと宛先ノードとの間に最適の経路であるルートが形成され、前記多重フォワード経路に予め定められたライフタイムが尽きると、前記多重フォワード経路で前記バックワード経路を形成しない経路の連結がパークされることを特徴とする。
【００２２】
望ましくは、前記フォワード経路設定段階は、前記ソースノードが宛先ノードへのルートを必要とし、前記ルートが少なくとも一つ以上利用可能な場合、ルート要求メッセージをブロードキャストする段階と、前記ソースノードで次にホッピングされる少なくとも一つ以上の中間ノードが、前記ルート要求メッセージが前記宛先ノードに到達するまで、前記ブロードキャストされたルート要求メッセージを受信し、さらに次のホッピングノードに前記ルート要求メッセージを伝達する段階とを含む。
【００２３】
ここで、前記ソースノードと前記宛先ノードとの間に連結が設定されれば、ソースノードはマスタとなり、その隣接する中間ノードはスレーブとなり、前記ルート要求メッセージは前記マスタからスレーブに転送されることが望ましい。
【００２４】
また、フォワード経路に沿う全ての中間ノードはマスタスレーブジョイントノードであることが望ましい。
【００２５】
また、前記ルート要求メッセージはその隣接ノードを発見して連結するためにソースノードでインクワイアリ動作を開始するルーティングトリガーであることが望ましい。
【００２６】
一方、前記バックワード経路設定段階は、前記ルート要求メッセージを受信した宛先ノードが前記形成されたフォワード経路のうちいずれか一つに沿って前記ソースノードに向かってルート応答メッセージを転送する段階と、前記宛先ノードで前記ソース方向にホッピングされる中間ノードが、前記ルート応答メッセージが前記ソースノードに到達するまで、前記ルート応答メッセージを受信し、さらに次のホッピングノードに前記ルート応答メッセージを伝達する段階とを含むことができる。
【００２７】
また、前記ルート応答メッセージは、マスタノードの間にスレーブ−スレーブジョイントノードを介在させるために、マスタ／スレーブスイッチングを開始するルーティングトリガーの役目を果たすことが望ましい。
【００２８】
さらに、前記マスタ／スレーブスイッチングは、前記宛先ノードから偶数離隔されたノードとその次のホッピングノードとの間で行なわれることが望ましい。
【００２９】
【発明の実施の形態】
以下、添付した図面に基づき本発明を詳述する。
ＩＥＥＥ８０２．１１ｂでは、同期化はフレーム別になされ事前リンク設定過程がないため、いずれのノードも互いの無線範囲内に位置すれば通信が行なえると記述している。これによれば、ネットワークは常に使用できるということである。マルチ−ホッピングの場合を挙げれば、ネットワーキングはルーティングアルゴリズムのために施される。ネットワーク形成システムのための８０２．１１における下部層(sub-layer)プロトコルスタックはない。
しかし、ブルートゥースノードはパケットを転送する前にまずピコネットを形成すべきである。簡単に説明すれば、ルーティングプロトコルと定義されたプロファイルは、ネットワークが構成された以降は主にソース(source)と宛先(destination)に重点をおいている一方、ネットワーク形成(network formation)は、ルートだけではなく、このソースと宛先との間におけるデータリンク層を基準に「より良質」なルートを提供し維持させるところにも重点をおいている。
【００３０】
二つのノード間には多数個の経路が存在でき、そのうち経路とルートを選択することがルーティングアルゴリズムと定義されたプロファイルの目的である(ここで、「経路」と「ルート」とに用語を分離して使用するのは、「経路」は二つのノード間の全てのネットワーク連結を、「ルート」はパケット転送のためにルーティングプロトコルにより選択された一つの経路を指すためである)。勿論、ルーティングアルゴリズムと定義されたプロファイルもネットワークの構成を助けることができる。この目的で知られているものが「オンデマンド型(on-demand)」ＭＡＮＥＴルーティングアルゴリズムの「ルートディスカバリー(Route Discovery)」である。また、マルチキャスティングとＱｏＳ保証(QoS guarantee)もルーティングプロトコル上でなされる。一方、全てのノードを選択されたルートを通して再構成することにより、ブルートゥース物理層及びデータリンクの次元でより良質のパケット転送を行なうようにすることがネットワーク形成の目的である。ここで、その重点は、「より良質」なネットワークである。従って、いつ、そしていずれのノードがマスタになり、スレーブになるべきか、またはソースと宛先の間のルート上にいずれの種類のジョイントノードがあるかを決定するのが非常に重要になる。
【００３１】
図１は、ブルートゥースグループアドホックネットワークで使用されるプロトコルスタックを示す。
【００３２】
ブルートゥースＳＩＧは、ブルートゥースノードとアプリケーションのネットワーキング能力を提供するため、ＢＮＥＰ(Bluetooth Network Encapsulation Protocol)層を定義している。
【００３３】
ネットワークフォメーション２６は、Ｌ２ＣＡＰ(Logical Link Control & Adaptation Protocol)２８とＢＮＥＰ２５の間に位置している。ネットワークフォメーション２６の主な目的は、ブルートゥースのデータリンク層及び物理層の観点から、早く、より良質のブルートゥースピコネット及びスキャタネットを実現するところにある。ネットワークフォメーション２６は、ルーティングプロトコルと通信可能である。
【００３４】
図１に示すように、ルーティングプロトコルはＩＰ層２４内に位置すると仮定する。これは、ルーティングプロトコルなどの上位層でブルートゥースを実行することを隠している。
【００３５】
一般に、ルーティングプロトコルは既存のネットワークトポロジのうち最善のルートを探し出すためのものである。ルーティングプロトコルの案内の下で、ネットワークフォメーション２６は、いずれのノードがマスタであり、いずれのノードがスレーブであるか、またはいずれの種類のジョイントノードであるかを決める。
【００３６】
与えられたネットワーク直径において最小限のピコネットを使用してネットワークを形成すれば、ピコネット間に干渉が少なくなり、隣接ピコネットとのパケットスケジューリングが少なくなる。その結果、ネットワークの維持が容易になる。
【００３７】
それぞれ動作は違うが、ルーティングプロトコルとネットワークフォメーションは、ブルートゥースグループアドホックネットワーク(Bluetooth Group Ad hoc network)に基づいて密接に関連している。
【００３８】
ここで、「Ｌ３トリガー(L3 trigger)」を、ネットワークフォメーションがルーティングプロトコルやその他の上位層のプロファイルと通信するためのメカニズムと定義する。Ｌ３トリガーの詳細については後述する。
【００３９】
図１の矢印はプロファイル、ルーティングプロトコル、及び管理部をネットワークフォメーションと連結するための信号線を示す。ネットワークフォメーションは、メッセージや命令を上位層のプロトコルまたはプロファイルと交換できる。
【００４０】
ネットワークフォメーション２６は、定義されたプロファイルまたはルーティングプロトコルの制御によって、より良質のネットワーク、ひいてはマルチホッピングネットワーク形成のためのユーティリティを提供する。一般に、小直径であり、パケット間の衝突が少なく、周辺ピコネットとの重複が少なく、ピコネット間スケジュールが多いネットワークであるほど、ピコネットの数も少なくなることは当然である。そして、ネットワークのメンテナンス費用は、できるだけ低価格にするべきである。
【００４１】
図２は、アドホックネットワークにおいてブルートゥースノードのプロトコルスタックを簡略に示す図である。
【００４２】
同図を参照すれば、ブルートゥースグループアドホックネットワーク環境下で、ルーティングプロトコルとネットワークフォメーションがどのように協調しているのかが分かる。ネットワーキングアプリケーション層２１、ルーティングプロトコル３３、及びネットワークフォメーションプロトコル２６の間に信号管(signaling pipe)が存在する。ネットワークアプリケーション層２１が二つのノード間の通信を初期化する。ルーティングプロトコルが宛先へのルートを分かっている場合なら、データパケットは直接に宛先に転送される。ルーティングプロトコルが宛先へのルートを分かっていない場合なら、ルーティングプロトコルは下に位置したネットワークフォメーション層２６に宛先への利用可能な経路を問い合わせる。ネットワークフォメーションプロトコルでソースと宛先の間で利用可能な経路があるならば、すべての利用可能な経路がルーティングプロトコルとして報告される。ルーティングプロトコルとネットワークフォメーションプロトコル間ではそれぞれストラテジと考慮要素が違うので、それぞれ記憶するネットワークトポロジは違ってくる。
【００４３】
ネットワークフォメーションプロトコル２６は、ルーティングプロトコル３３に比べてネットワークトポロジについてさらに情報を持つべきである。ルーティングプロトコル３３は、それらのうち一つのルートを選択する。もし、ネットワークフォメーションプロトコル２６に宛先への利用可能な経路がなければ、ルーティングプロトコル３３は、ＨＣｌ要求を通じて「インクワイアリ/ページ(Inquiry and page)」プロセスを開始し、近接したノードとの連結を設定する。すると、ネットワークトポロジ情報または宛先要求は、２個の近接ノードのネットワークフォメーションプロトコル間で交換される。このプロセスは宛先が発見されるか、別の条件により停止するまで繰り返される。
【００４４】
次に、ブルースターネットワークで使用される用語について定義する。
●フリーノード：別のノードと連結されないノード
●スレーブノード：一つのピコネットでだけスレーブメンバーであるノード
●マスタノード：一つのピコネットでだけマスタメンバーであるノード
●ジョイントノード：少なくとも二つ以上のピコネットでメンバーであるノード。ノードが加入できる最大ピコネットの数はＭである。ノードがＭ＋１番目のピコネットに加入した後、Ｍ個のピコネットのうち一つのリンクはダウンされるべきである。スキャタネットには、２種類のジョイントノード、すなわちＳ−ＳジョイントノードとＭ−Ｓジョイントノードがある。
●Ｓ−Ｓジョイントノード：両ピコネットにおいてスレーブで動作するジョイントノード
●Ｍ−Ｓジョイントノード：一のピコネットにおいてスレーブで動作すると共に他のピコネットにおいてマスタで動作するジョイントノード
●中間ノード：別のノードへ予定されたパケットを転送するのに同意したノード
●フォワード経路：ルートディスカバリー動作を開始したノードから所望の宛先に向かってデータパケットを転送するために設定された経路
●リバース(バックワード)経路：宛先ノードまたは宛先へのルートを有する中間ノードからソースにＲＲＥＰパケットを転送するために設定された経路
●ルーティングトリガー：特定イベントが発生したり、または発生しようとすることを知らせるオンデマンドルーティングプロトコルからの通知。この通知はパラメータ情報を含むことができ、ブルートゥースベースバンドで動作が開始される。ルーティングプロトコルはＩＰ層、管理者部、またはブルートゥースデータリンク層に位置することができる。
●インクワイアリ状態：ノードがインクワイアリトレインに応答すれば、２個のノード間にリンクを形成するようページ進行が行なわれる。
●休止(dormant)状態：コネクション状態及び待機状態、例えばホールドモード、スニフモード、及びパークモードなどのバッテリパワーを節約するためのブルートゥースノードの省電力状態
●ブルースターアイランド：ジョイントノードがＳ−Ｓジョイントノードであるピコネットまたはスキャタネット。ブルースターにおいて「スター」はスター型ネットワークトポロジ(topology)を示す。
●ピコネットにおいてマスタは中央である。Ｓ−Ｓジョイントノードを有するスキャタネットでは２個の中央がある。
【００４５】
図３は、本発明に係るオンデマンドルーティング方法において、フォワード経路とバックワード経路でのノードの機能を示す図である。
【００４６】
図３に示すように、ノードはフリーノード、マスタノード、スレーブノード、及びジョイントノードの４つの機能を果たすことが出来る。全てのノードは初期にフリーノードである。ルートの観点から説明すれば、パケットフォワードルートに沿って、ノードはソースノード、中間ノードまたは宛先ノードと称される。
【００４７】
全てのノードは、いずれの状態にあっても規則的にインクワイアリスキャン状態に入る。これは、ノードの状態にかかわらず発見できるようにするためである。
【００４８】
オンデマンドネットワーク形成は、ソースノードにより要求される時だけ可能である。その前は、全てのノードは独立している。ソースノードがパケットをある宛先ノードへ転送しようとし、宛先ノードへの有効なルートを有していなければ、ルーティングアルゴリズムは宛先を発見するために経路発見プロセスを開始する。
【００４９】
この経路発見プロセスは、宛先ノードへの経路が発見されるか、全ての可能な経路交換が検索されれば終了する。
【００５０】
ソースノードは、ＲＲＥＱメッセージをブロードキャストする。ルーティングプロトコルにおけるＲＲＥＱメッセージは、その隣接ノードを発見して連結するためにソースノードのベースバンドでインクワイアリ動作をトリガーする。
【００５１】
ルーティングプロトコルにおいて、宛先へのルートが必要であり、一つも利用可能なルートがない場合、ＲＲＥＱメッセージはブロードキャストされる。ノードはＲＲＥＱメッセージをその連結されたノードに送信する。
【００５２】
そのノードにとって、ＲＲＥＱメッセージは、ベースバンドでインクワイアリ動作を開始する「ルーティングトリガー」である。しかし、次の四種の場合は除外する。
【００５３】
第１に、Ｎ(Ｎ≦７)個のアクティブスレーブがマスタノードについて予め連結されている場合であり、第２に、ジョイントノードにより連結されているＭ個のピコネットがある場合である。第３に、ＲＲＥＱメッセージのＴＴＬ(time-to-leave)フィールドがルーティングプロトコルで終了する場合である。第４に、複写されたＲＲＥＱメッセージが受信される場合である。
【００５４】
インクワイアリ動作において新たなノードが発見されるイベントにおいて、ノードはマスタになり、新たなノードは新たに形成されたピコネットでスレーブになる。ＲＲＥＱメッセージはＢＮＥＰ連結が形成された後、新たなノードに転送される。もし、新たなノードがＭ＋１番目のピコネットに加わる場合、新たなノードは以前の連結のうちいずれかを切るべきである。
【００５５】
フォワード経路はライフタイム属性を有する。これは、限られた時間内でフォワード経路が確認されるべきであることを意味する。詳しくいうと、ライフタイム属性には、パークライフタイム(park lifetime)とディスコネクトライフタイム(disconnect lifetime)の二つがある。経路ライフタイムはネットワークで連結の属性である一方、ルートライフタイムはルーティングプロトコルでルーティングテーブルの属性である。
【００５６】
フォワード経路に沿って、全ての中間ノードはマスタスレーブジョイントノードである。
【００５７】
次いで、バックワード経路について図３を参照して説明する。
【００５８】
ルーティングプロトコルにおいて、宛先に対するＲＲＥＱメッセージを受信すれば、要求を満たすのに十分なルートを有しており、それ自身が宛先の場合、ノードはＲＲＥＰメッセージを発生する。フォワード経路に沿って、全ての中間ノードはＭ−Ｓジョイントノードである。
【００５９】
ＲＲＥＰメッセージは、進行中のインクワイアリ動作を中止し、バックワード経路に沿ってネットワーク再形成を開始して形成されたピコネットの数を減らすルーティングトリガーである。
【００６０】
一方、ＲＲＥＰパケットは、マスタノードの間にＳ−Ｓジョイントノードを介在させるためにマスタ／スレーブスイッチを開始するルーティングトリガーである。
【００６１】
ネットワーク再形成の原則は、マスタノードの間に可能なＳ−Ｓジョイントノードをインタリーブ(interleave)することである。これは、ピコネットの数を最小化する。
【００６２】
ネットワーク再形成セグメントは開始ノードと終了ノードとの間にある。終了ノードはＲＲＥＰメッセージが発生されるノードである。一方、開始ノードは、マスタで動作する際、空中にＲＲＥＱメッセージが最初に転送された場所である。また、開始ノードは、スレーブで動作する際、空中にＲＲＥＱメッセージが最初に転送された次ホップのノードである。
【００６３】
開始ノードはマスタで動作し、終了ノードはスレーブで動作する。
【００６４】
ネットワーキングアプリケーションプロファイルは、ノードの役目を決めるために高い優先順位を有しうる。マスタ−スレーブスイッチは、偶数離隔されたノードとその次のホップノード間でだけ行なわれる。
【００６５】
他の経路に対するそのルートテーブルは、ＴＴＬが経過しないノードであるか、または存在するネットワークの影響を最小化するためにノードの機能は変化できない。また、固定された機能をピコネットで維持することを希望するノードについては、ノードの機能が変化できない。
【００６６】
図４は、本発明に係るオンデマンドルーティング方法における、多重フォワード経路のうちバックワード経路のルーティングを示す図である。
【００６７】
図４に示したように、転送は、ソースノードＮ０から宛先ノードＮ８へ二つの経路に沿って行われる。しかし、ＲＲＥＰメッセージは、ノードＮ４〜ノードＮ６に沿っては進行しない。これは、ルーティングプロトコルは、それらからルートを一つだけ選択するからである。パークライフタイムが経過すれば、選択されないフォワード経路上のリンクはパークされ、ＡＭ−ＡＤＤＲを返還してバッテリパワーを節約する。ディスコネクトライフタイムが経過すれば、フォワード経路上のリンクは切れ、バッテリパワーをさらに節約するようになる。
【００６８】
次は、ルートエラー及びルートの終了について説明する。
【００６９】
ルーティングプロトコルにおいては、リンクが切れるか、ルートが終了すればＲＥＲＲ(Route ERRor)メッセージが発生されブロードキャストされる。ＲＥＲＲメッセージは、残った連結されたリンクについてパーク動作を開始する「ルーティングトリガー」である。ルーティングプロトコルにおいては、宛先へのルートが終了すれば、経路に沿った連結はパークされ、バッテリパワーを節約する。スレーブノードは、リンクを感知するために周期的に起きている必要がある。宛先へのルートがルートテーブルから削除されれば、経路に沿った連結が切れる。
【００７０】
ブルースターアイランドネットワークフォメーションは、２段階プロトコルである。ブルースターアイランドネットワークフォメーションの第１段階は、フリーノードで自動的に形成される。ブルースターアイランドは、ジョイントノードが両ピコネットでスレーブになるピコネットになることができ、またはスキャタネットとなることができる。電源が供給されたとき、ノードのデフォルトの機能は、フリーノードである。その後、ノードはインクワイアリ状態、インクワイアリスキャン状態、及び休止状態などにその状態を転換する。ノードはそれぞれ独立的であり、互いについて無知の状態である。各ノードはスレーブ資格で接続してスレーブノードになれ、マスタ資格で接続してマスタノードになれる。スレーブノードは、定期的にインクワイアリスキャン状態に入って別のピコネットに発見されることにより、ブルースターアイランドが形成されうる。マスタノードは、他のマスタに発見されるように、インクワイアリ状態に入る。このようにして、二つのマスタノードが互いの無線範囲内に進入することが防止される。全てのブルートゥースノードは自律構成されるので、個別的なマルチブルースターアイランドの形成も可能である。
【００７１】
図５は、二つの隣接したブルースターアイランドが互いに連結できない場合の例を示す図である。
【００７２】
ブルースターアイランドネットワークフォメーションの第２段階は、「Ｌ３トリガー」の開始によりブルースターアイランドをブリッジングすることである。ここで、「Ｌ３トリガー」はルーティングプロトコル、プロファイルあるいは管理部などから転送された短い通知である。例えば、「Ｌ３トリガー」はルーティングアルゴリズムの"Route REQuest"や、"HELLO"のようなメッセージである。また、プロファイルから転送された命令、例えば「サービスディスカバリー」命令も「Ｌ３トリガー」の一例と言える。「Ｌ３トリガー」があった後、全てのエッジノード、スレーブノードなどがインクワイアリ状態を行って無線範囲内に別のスレーブノードがあるかをチェックする。新たなブルースターアイランドが発見されれば、新たなピコネットが形成される。この場合、ジョイントノードは、Ｍ−Ｓジョイントノードを指す。
【００７３】
図６は、ブルースターネットワークフォメーションにおいてノードの役割の転換を示す図であり、図７はそれぞれのノードの状態を示す図である。
【００７４】
図６において、フリーノード５３は、ネットワークが形成される前に存在するノードであって、別のノードと連結を有しないノードと定義される。
【００７５】
フリーノード５３は、パワーオンされた後のデフォルトノードである。フリーノード５３は、別のノードと連結を有せず、連結状態にならない。フリーノード５３は、インクワイアリ状態、インクワイアリスキャン状態、及び休止状態に入る(段階Ｓ５０２)。パワーオンした後、または休止状態から覚めた後、フリーノードは[０，１]間で乱数(Rnode)を発生する。
【００７６】
Rnode<R０ならば、ノードはインクワイアリ状態に入る。
【００７７】
Rnode>R０ならば、ノードはインクワイアリスキャン状態に入る。
【００７８】
インクワイアリとインクワイアリスキャン後にいずれの連結設定もなければ、ノードは休止状態に入る。
【００７９】
トラフィックが発生すれば、フリーノード５３は、インクワイアリ動作を開始する。Ｒ０は、固定された臨界値である（Ｒ０の値はシミュレーションを通してＴＢＤである)。フリーノード５３は、インクワイアリ状態になる確率よりインクワイアリスキャン状態になる確率のほうが高くなくてはならない。フリーノード５３は、トラフィックパケットソースまたはパケット宛先でありうる。式のノードの役割の設定時までフリーノード５３はその役割を維持する。
【００８０】
役割が設定される時、フリーノード５３は、形成されたリンクの状態に応じてマスタノードまたはスレーブノードになれる(段階Ｓ５０４及び段階Ｓ５０５)。そして、スレーブノードまたはマスタノードのリンクが切れれば、スレーブノードまたはマスタノードは、フリーノードに転換される(段階Ｓ５０９、Ｓ５１０)。
【００８１】
スレーブノードは、一つのピコネットでだけスレーブメンバーノードと定義される。
【００８２】
スレーブノード５４は、トラフィックパケットソースまたはパケット宛先になれる。スレーブノード５４は、さらに大きいブルースターアイランドを形成するため新たなマスタにより発見されるようインクワイアリスキャン状態に規則的に入り、トラフィックがなければバッテリパワーを節約するために休止状態に入る(段階Ｓ５０６)。
【００８３】
上位層から「Ｌ３トリガー」を受信すれば、スレーブノード５４は近接したブルースターアイランドを発見するためにインクワイアリ状態に入る(段階Ｓ５０８)。スレーブノード５４のインクワイアリスケジュールは、注意深く配列されるべきである。全てのスレーブノード５４がインクワイアリを同時に行うと、深刻なＩＰパケット衝突が発生するおそれがある。これは、インクワイアリ動作の性能を低下させる。たとえば、連結設定を長くし、帯域幅の浪費を引き起こす。
【００８４】
別のピコネットとのリンクがダウンされるか、新たなリンクが追加されるまで、スレーブノード５４は、その機能を維持する。リンクがダウンされれば、スレーブノード５４はフリーノード５３になるよう転換され、リンクを失う(段階Ｓ５１０)。新たなリンクが追加されれば、スレーブノードはジョイントノードになるよう転換される。
【００８５】
一方、マスタノード５１はパケットソース、パケット宛先及びトラフィックパケットリレーノードになれる。マスタノード５１は、インクワイアリ状態とインクワイアリスキャン状態に規則的に入る(段階Ｓ５１２)。
【００８６】
マスタノード５１は、Ｎ個のアクティブスレーブ(Ｎ<=７)が発見されるまで、その範囲でフリーノードを発見するようインクワイアリ状態に規則的に入る。また、マスタノード５１は、インクワイアリスキャン状態に規則的に入る。これは、互いに無線領域に存する場合、別のマスタにより発見されることを可能にするためである。
【００８７】
第１マスタノードが第２マスタノードにより発見されれば、第１マスタノードは第２マスタノードのピコネットにおいてジョイントノード（Ｍ−Ｓジョイントノード）になる。すると、第１マスタノードは一つのスレーブノードとマスタ−スレーブスイッチングを行い、Ｓ−Ｓジョイントノードになる。
【００８８】
一方、第１マスタノードに属する別のスレーブノードは、新たなピコネットに加わろうとしてジョイントノードになる(段階Ｓ５１４)。スレーブノードは新たなピコネットに加わり、フリーノードになれない。
【００８９】
マスタノードはそれぞれの連結の寿命を記録し、連結を通して転送される全てのパケットについて寿命を更新する。連結寿命が経過した後、連結ノード（スレーブ）は、スレーブ資源になるため休止状態に入るよう命令される。
【００９０】
全てのリンクが切れるか、別のマスタにより発見されるまで、マスタノードはその役割を維持する。全てのリンクが切れるイベントにおいて、マスタノードはフリーノードに転換され、別のマスタにより発見されるイベントで、発見されたマスタノードはスレーブとの全てのリンクを切り、新たなピコネットでスレーブノードに転換される。
【００９１】
ジョイントノード５２は、パケットソース、パケット宛先、及びブルースターアイランドの間でトラフィックパケットリレーノードになれる。ジョイントノードは、近接したブルースターアイランドにより規則的に発見されるようインクワイアリスキャン状態に入れる。上位層において「Ｌ３トリガー」を受信すれば、ジョイントノードはインクワイアリ状態に入って、近接したブルースターアイランドを発見する。
【００９２】
Ｍ＋１番目のピコネットにジョインした後、ジョイントノードは結合寿命とピコネット寿命に基づき、現在のアクティブ連結を切るべきである。いずれにしても、ジョイントノードは、確実にルートボトルノード(bottle node)にならなければならない。Ｍ値はＴＢＤである。バッテリパワーを節減するため、トラフィックがなければジョイントノードは休止状態になる(段階Ｓ５１６)。
【００９３】
ジョイントノード５２は、一つのリンクが切れるまでその役割を維持する。Ｓ−Ｓジョイントノードリンクが切れれば、ジョイントノードはスレーブノードになる(段階Ｓ５１８)。Ｍ−Ｓジョイントノードリンクが切れれば、ジョイントノードは、いずれのノードが切れているのかによってマスタノードまたはスレーブノードになる。
【００９４】
次に、Ｌ３トリガーについて詳述する。
【００９５】
「Ｌ２トリガー」がＬ２層のためだけにＩＥＴＦドラフトで使用されたため、上位層を報告するために「Ｌ３トリガー」と命名された。ＩＥＴＦにおいて、Ｌ２トリガーは、Ｌ２から特定イベントが発生したかあるいは発生しようとするのかの通知の約束である(潜在的にパラメータ情報を含んで)。トリガーは多様な方法で実行できる。ここで、Ｌ３トリガーは、Ｌ２ＣＡＰ上位層から通知を示すよう使用する。
【００９６】
ルーティングプロトコルから、Ｌ３トリガーは、オンデマンドプロトコルでRREQタイプのメッセージであるか、テーブルドリブン及びオンデマンドプロトコルで"HELLO"タイプのメッセージでありうる。ＲＲＥＱメッセージはＩＰアドレスでラベルされたノードを発見するために使用される一方、HELLOメッセージは近接したノードが未だ利用可能なのかを感知するために使われる。別のノードからＲＲＥＱメッセージを受信すれば、スレーブノードは、ソースノードと宛先ノードとの中間に位置して、その到達可能な範囲に宛先があるかをチェックする。これは、ルーティングプロトコルにより行われる。
【００９７】
もし、到達可能な範囲に宛先があれば、ルーティングプロトコルでRREP(Route REPly)メッセージがルーティングアルゴリズムにより発生する。ノードはソースへのバックワード経路に沿ってＲＲＥＰメッセージを送信する。
【００９８】
もし、到達可能な範囲に宛先がなければ、ノードはＬ３トリガー信号を発生して全ての到達可能なスレーブノードに知らせて、アルゴリズムに基づき近接したブルースターアイランドを求めるようインクワイアリを行う。
【００９９】
インクワイアリに応答ノードがなければ、ノードはインクワイアリを中断する。
【０１００】
インクワイアリに応答するノードがあれば、それらの間にＢＮＥＰ連結が発生した後、RREQメッセージはノードに送信される。
【０１０１】
このプロセスは、宛先が発見されるか、最大ホップ(hop)数ｉｄに到達するまで繰り返される。
【０１０２】
このように、RREQメッセージは中間のブルースターアイランドにリレーされる。これとは逆に、HELLOメッセージは近接ノードを感知するためにだけ使用される。いずれの宛先ノードも定義されない。従って、HELLOメッセージは、リレーなしで、かつソースブルースターアイランドでだけ、トリガーを開始することができる。
【０１０３】
Ｌ３トリガーは管理部、限定的なプロファイル、またはサービスディスカバリーから来る場合がある。この場合、ネットワークフォメーションからルーティングプロトコルへの上向インタフェースだけがある。サービスディスカバリーと管理タイプのメッセージはＬ３トリガーでありうる。
【０１０４】
ネットワークトポロジを記録するため、全てのノードは、同一なピコネット及び同一なブルースターアイランドで到達可能なノードリストを維持すべきである。全てのノードはＭ−Ｓジョイントノードを介して通信することができる。ノードの可能なデータ構造は、表１のリストの通りである。新たなノードまたはブルースターアイランドが発見されると、ノードはその記録を加え、全ての到達可能なノードに情報を知らせる。リンクが失われれば、ノードは一つまたは１グループのノードをその記録から削除する。表１は、ルーティングプロトコルからベースバンドへの経路をマッピングしたものである。同一なものがルーティングプロトコルで発生する。コネクション寿命属性は、連結のアクティブ時間を記録するために使われる。リンクにおける全てのパケットは、寿命属性を新しくされる。ブルースターアイランド寿命は、二つのマスタが互いに無線範囲にある時、いずれがスレーブになるのか決めるために使用される。
【０１０５】
【表１】
0003840197.tif 000002
【０１０６】
テーブル駆動されたルーティングプロトコルは、ネットワーク情報と組み合わせるよう駆動される。ノード記録及びルーティングテーブルは殆んど同一である。オンデマンドルーティングプロトコルの場合、ルーティングテーブル及びノード記録は違う。
【０１０７】
【発明の効果】
以上述べた通り、本発明に係るブルートゥースオンデマンドルーティング方法によれば、バッテリパワーを節約することができ、進行中のトラフィックについて大きい帯域幅を提供することができる。また、バックワード経路に沿うマスタ／スレーブスイッチングにより、より良質のスキャタネット構成が実行できる。
【０１０８】
ネットワークフォメーションとルーティングを互いに重畳させず独立して維持することができ、テーブル駆動及びオンデマンドプロトコルのように全種類のルーティングプロトコルを受け入れられる。また、ジョイントノードがピコネットをブリッジングするので、ピコネットの数を最小化できる。そして、スレーブノードはただインクワイアリスキャンだけ行うため、管理を最小化し、バッテリパワー消費を最小化する。
【０１０９】
以上では本発明の望ましい実施例について説明したが、本発明は、前述した特定の実施例に限らず、請求の範囲で請求する本発明の要旨を逸脱しない限りにおいて、当該発明の属する技術分野において通常の知識を持つ者ならば誰でも多様な変形実施が可能なことは勿論、そのような変更は請求の範囲の記載の範囲内にある。
【図面の簡単な説明】
【図１】ブルートゥースグループアドホックネットワークで使用されるプロトコルスタックを示す図である。
【図２】アドホックネットワークでブルートゥースノードのプロトコルスタックを概略的に示す図である。
【図３】  本発明に係るブルートゥースオンデマンドルーティング方法において、フォワード経路及びバックワード経路時のノードの役割を説明するための図である。
【図４】  本発明に係るブルートゥースオンデマンドルーティング方法において、多重フォワード経路中バックワード経路のルートを説明するための図である。
【図５】二つの隣接したブルースターアイランドが互いに連結されていない場合の例を示す図である。
【図６】ブルースターネットワークフォメーションでノードの役割と役割の転換を示す信号流れ図である。
【図７】それぞれのノードの状態を示す図である。
【図１】
0003840197.tif 000003
【図２】
0003840197.tif 000004
【図３】
0003840197.tif 000005
【図４】
0003840197.tif 000006
【図５】
0003840197.tif 000007
【図６】
0003840197.tif 000008
【図７】
0003840197.tif 000009