JP4170566B2 - 通信方法、無線アドホックネットワーク、通信端末、およびブルートゥース端末 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、複数の無線局による通信に係り、特に、複数の無線局によってクラスタを構成して通信を行う通信方法等に関する。
【０００２】
【従来の技術】
近年、携帯情報端末の小型化、軽量化によって、情報端末を気軽に持ち運び、多くのユーザ間で使用されるようになっている。それに伴い、モバイル環境下で自由な情報交換を行うために、オンデマンド型の通信として無線アドホックネットワークを構築する研究が多くなされている。この無線アドホックネットワークは、モバイルコンピューティングの一形態として、距離と時間が近接した状況において、一時的に集合した端末の間でデータの送受信を行うための通信手段を提供することを目的とし、情報端末を持った複数の人間が、必要になったその場で構成するネットワークである。
【０００３】
一方で、多様な機器に製造過程で組み込まれる短距離無線技術を利用し、モバイルおよびビジネスユーザに便利なサービスを提供することを目的として、ブルートゥース(Bluetooth)が急速に注目され始めている。このBluetoothは、小型で高性能な無線トランシーバをベースとし、ＩＥＥＥ８０２標準に準拠する４８ｂｉｔアドレスが割り当てられており、規制のない２.４５ＧＨｚＩＳＭの自由帯域で稼働することが可能である。また、モバイルとビジネスユーザに最適な１０ｍをカバー範囲とし、消費電力がスタンバイモードでわずか０.３ｍＡであるため、バッテリ利用の機器の寿命を伸ばすことができる。このBluetoothは、電話やデジタルカメラ、プリンタなどの周辺機器に簡易に搭載でき、ノートパソコンやＰＤＡ(Personal Digital Assistance)などの情報端末機器にも標準装備されることが期待されている。その場合に、Bluetooth搭載のノートパソコンやＰＤＡを用いて、例えば会議室にてアドホックに通信できるといったシステムは、極めて自然な応用事例として考えることができる。
【０００４】
【発明が解決しようとする課題】
しかしながら、無線アドホック通信は、伝統的な有線ネットワークや、最近、実用化が進んでいる無線ネットワークと、通信路またはネットワークの構成において根本的に異なるところがあり、普及の障害となっている。
【０００５】
即ち、例えば、通信を開始するにあたっては、まず、ネットワークを構成しなければならないが、有線ネットワークにおいては、ネットワーク管理者が、ケーブルおよび端子の施設、ルーターの設置などの設備を事前に準備しており、ネットワークに参加するには、ユーザは端子に接続すればよい。無線ネットワークにおいても、ネットワーク管理者がサービスエリアを定義し、固定基地局を配しており、ネットワークに参加するには、ユーザはサービスエリアで基地局にアクセスすればよい。それに対し、アドホックネットワークでは、ネットワーク管理者が存在せず、通信を始める前に、アドホックに集まったユーザ同士がなんらかの形でネットワークを構成しなければならない。即ち、ユーザ同士が相談して、実質的な配線作業をしなければならないのである。このことを、人手を介さず自動的に実現するのは困難であると同時に、時間的制約を考慮すれば、でき上がった配線状態は、多くの場合最適なものとはならない。
【０００６】
また、各無線局が移動することが問題を更に複雑化している。アドホックネットワークでは、各無線局がばらばらに移動するため、定期的にネットワーク構成の最適化が必要となる。また、その最適化は、基地局のような不動なものを仮定することができないため、しばしば、ネットワークトポロジーを大きく変えるものになってしまう。
【０００７】
ここで、例えばBluetooth等による無線データ通信では、マスタ・スレーブ構成が取られている。このマスタ・スレーブ構成では、マスタによって複数のスレーブに接続することはできるが、スレーブ同士の通信を行うことはできない。このような制約下にあるアドホックネットワークにおいては、クラスタヘッドの選出が極めて重要な問題となる。ここでは、スレーブ同士の通信ができないことから、全ての通信はマスタ・スレーブ間の通信によって実現されることとなる。その結果、不適切なクラスタヘッドが選出されると、クラスタ全体の通信効率に直接、影響を与えることとなる。
【０００８】
通常のアドホックネットワークにおいては、クラスタメンバ同士にて通信が行える場合が多く、クラスタヘッドの仕事はクラスタの管理や、通信路の維持等が中心的である。そのため、クラスタヘッドの通信効率に与える影響はBluetoothほどは大きくない。また、たとえクラスタヘッドを最適に選んだとしても、クラスタメンバ各局、更にクラスタヘッド自体が移動するので、このトポロジーが維持されるとは限らない。そのため、従来では、取り敢えずつながればよい、という考え方が支配的であった。一般に、クラスタヘッドの選出を行うためには、通信周波数および送受信のタイミングを同期させるオーバヘッドが必要である上、無線特有の隠れ端末問題(例えば、局Ａが局Ｂ,Ｃと通信可能であっても、局Ｂと局Ｃは直接通信不可能であること)のため、クラスタの最適化、クラスタの再構成そのものが、効果的ではなかった。
【０００９】
その一方で、前述したような、会議室に人が集まってきて、それぞれの人が有するノートパソコンの間でファイルやメッセージの交換などの通信をアドホックに行いたいような典型的なアプリケーションを想定した場合には、クラスタヘッドの最適化が極めて重要となる。例えば、会議中、人はほとんど移動せず、移動してもせいぜい歩く程度のゆっくりした速度が普通であるが、その一方で、会議では参加者の出入りがあり、無線局の新たな増減がある。たとえ無線局の移動がなくても、こうした無線局の増減により、最適なクラスタヘッドが変わる可能性があり、通信の効率を保つためには、クラスタの動的な再構成が必要となる。しかしながら、クラスタの再構成に時間がかかるため、再構成中に通信が中断されるオーバヘッドの問題が生じてしまう。また、現在確立されているクラスタを解消してしまい、新たなクラスタに再構成するため、すべての無線局が新しいクラスタに移動できる保証がないことも大きな問題となる。
【００１０】
また、例えば、人の出入りに応じて、参加者が合議のもとで、人的操作によってクラスタヘッドを変更することも考えられる。しかしながら、人にとっては、どの無線局が最適なクラスタヘッドであるかを容易には判断することができない。即ち、無線通信の場合、目に見えない障害物や個々の無線局による性能によってエラーレートが異なってしまい、例えば、無線局間の距離が近いことが通信し易いことにはならないためである。その結果、通信状態を把握するためには、実際に通信して、エラーレートなどを観測する必要があり、人的操作によってクラスタヘッドを変更することは現実的ではない
【００１１】
一方、Bluetoothでは、マスタとスレーブにおける通信の開始には、無線局の探索に必要なInquiryというプロセスと、スレーブ局がマスタ局と接続を行うためのPageという時間のかかるプロセスが必要となる。スペックによれば、標準的なプロセスでInquiryを行うには最低１０.２４秒以上継続して電波を発信し続けなければならない。また、これによって発見されたデバイスと接続を確立するには１台あたり平均１.５秒のPageが必要とされる。従って、妨害のない標準的な場合においても、クラスタの再構成には２０秒程度の時間を要してしまう。
【００１２】
本発明は、以上のような技術的課題を解決するためになされたものであって、その目的とするところは、無線アドホック通信において、ネットワーク通信を自動的かつ最適に行うことにある。
また他の目的は、不適格なクラスタヘッドの状態を検出し、より良いクラスタヘッドを再選出することにある。
更に他の目的は、ネットワークの構成直後、または極めてエラーレートの高い無線局が発生したときに、ネットワーク構成を最適化することにある。
【００１３】
【課題を解決するための手段】
かかる目的のもと、本発明は、クラスタ内の各無線局を、予め取り決めた時刻と期間で順番に仮クラスタヘッドとして機能させてみて、それぞれが仮クラスタヘッドとなったときに構成する仮クラスタメンバとの受信レベル(接続電波状況)を取得し、それらを現在のクラスタヘッドとの接続電波状況と比較して改善される場合は、クラスタヘッドを交代するように構成している。即ち、本発明は、複数の無線局の間で所定のクラスタを形成し、クラスタの管理を行うクラスタヘッドを選択して、例えばスレーブ間通信ができないマスタ・スレーブ構成をとる無線アドホックネットワーク等にてグループ通信を行う通信方法であって、このクラスタに属する無線局の１つを仮クラスタヘッドとして動作させ、無線局が仮クラスタヘッドとなった場合における通信効率を判定し、判定された通信効率に基づいてクラスタを構成する無線局の中からクラスタにおけるクラスタヘッドを選定することを特徴としている。
【００１４】
ここで、この無線局を仮クラスタヘッドとして巡回させる動作およびクラスタを構成するそれぞれの無線局が仮クラスタヘッドに対して接続を試みる動作を定めたスケジュールを生成し、クラスタを構成する無線局は、生成されたこのスケジュールに基づいて同期して動作することを特徴とすれば、クラスタの再構成を非同期に行う場合に比べてクラスタの再構成にかかる時間を短縮できる点で好ましい。
また、この仮クラスタヘッドとしての動作後に、元のクラスタ構成に戻る動作および元のクラスタ構成に戻れない場合の回復動作を予め回復スケジュールとして定め、このクラスタを構成する無線局は、生成された回復スケジュールに基づいて同期して動作することを特徴とすれば、万一、クラスタヘッド交代作業中にエラーが発生した場合であっても、事前のスケジュールに基づいて対応をとることが可能となる。
【００１５】
一方、本発明は、クラスタヘッドであるノードおよび１つ以上のクラスタメンバであるノードからなるクラスタを構成する無線アドホックネットワークにおいて、このクラスタヘッドであるノードは、クラスタメンバであるノードに対する自らのリンク状態を把握し、このリンク状態の把握に基づいてクラスタヘッド交代スケジュールを生成してクラスタメンバであるノードに配布し、クラスタメンバであるノードは、配布されたクラスタヘッド交代スケジュールに基づきクラスタを構成するノードに対する自らのリンク状態を把握してクラスタヘッドであるノードに送信することを特徴としている。
【００１６】
ここで、このクラスタヘッドであるノードは、クラスタメンバであるノードから送信されたリンク状態に基づいてクラスタヘッドの権限を委譲するか否かを判断し、委譲する場合には、委譲してもよいノードに対して権限の委譲を試みることを特徴とすれば、クラスタの再構成を行う手間の割にリンク状態の改善効果が低い場合等、クラスタの状態に応じて最適な状況を選択することが可能となる。また、このクラスタヘッドであるノードは、委譲してもよいノードに対する委譲に失敗した場合には、自らがクラスタヘッドを継続する元のクラスタ構成に戻れるように、元のクラスタ構成に戻る時刻を予め定めることを特徴とすれば、クラスタヘッドの交代作業中にエラーが生じた場合でも適切に復旧することができる。
【００１７】
他の観点から把らえると、本発明は、クラスタヘッドであるノードおよび１つ以上のクラスタメンバであるノードからなるクラスタを構成する無線アドホックネットワークにおいて、このクラスタヘッドは、クラスタを構成するクラスタメンバに対して仮クラスタヘッドとなる巡回動作を定めたスケジュールを配布し、このクラスタメンバは、配布されたスケジュールに基づき、仮クラスタヘッドとして他のノードとの通信状態を把握してクラスタヘッドに送信し、クラスタヘッドからの権限の委譲に基づいて、新たにクラスタヘッドとなり得ることを特徴としている。
ここで、このクラスタヘッドは、クラスタの構成直後、または、エラーレートの高いノードが検出された時点で巡回動作を定めたスケジュールを配布することを特徴とすれば、クラスタの再構成が必要なときに、必要な作業を円滑に行うことができる点で好ましい。
【００１８】
一方、本発明は、クラスタを構成する複数のノードの１つとして構成可能であると共に、この複数のノードの中でクラスタヘッドとして残りのノードであるクラスタメンバとの通信を可能とする通信端末であって、クラスタメンバとのリンク状態を把握するリンク状態把握手段と、クラスタメンバが仮クラスタヘッドとなった場合における他のノードとのリンク状態を認識する仮クラスタヘッドリンク状態認識手段と、把握されたリンク状態と、認識されたリンク状態とに基づいて、特定のノードへのクラスタヘッドの委譲を決定する委譲決定手段とを備えることを特徴としている。
【００１９】
このリンク状態把握手段は、クラスタメンバごとにテストデータを送信してパケットエラーレートを検出することによりリンク状態を把握することを特徴とすることができる。
また、クラスタメンバを順番に仮クラスタヘッドとして巡回させるために、例えば、適切なクラスタヘッド候補を探索するために、仮クラスタヘッドをノード間で巡回させる時刻、それぞれのノードが仮クラスタヘッドに対して接続を試みる時刻、および試みようとする接続が失敗した場合に再接続を繰り返す期間が定められているスケジュールを作成するスケジュール作成手段と、このスケジュール作成手段により作成されたスケジュールをクラスタメンバに対して配布するスケジュール配布手段とを更に備えたことを特徴としている。
更に、このスケジュール作成手段は、リンク状態把握手段によりリンク状態に問題があると判断される場合に、スケジュールを作成することを特徴とすることができる。
【００２０】
また、本発明は、クラスタを構成する複数のノードの１つとして構成可能であると共に、この複数のノードの中でクラスタメンバとして他のノードであるクラスタヘッドとの通信を可能とする通信端末であって、クラスタヘッドからクラスタヘッドとしての適性度を判定するための巡回スケジュールを受信する受信手段と、受信した巡回スケジュールに基づいて、クラスタを構成する他のノードとの通信状態を把握する通信状態把握手段と、把握された通信状態をクラスタヘッドに対して送信する送信手段とを備えたことを特徴としている。
【００２１】
一方、本発明は、ピコネットを構成する複数の無線局の１つとして構成可能であると共に、マスタとして複数のスレーブを管理することができるブルートゥース端末であって、管理する複数のスレーブとの通信状態を把握する通信状態把握手段と、この通信状態把握手段による通信状態の把握によって、自らがマスタとして不適当であると判断される場合には、ピコネットを構成する所定のスレーブに対してマスタとしての権限を委譲してピコネットの再構成を行う権限委譲手段とを備えたことを特徴としている。
【００２２】
ここで、ピコネットを構成する複数のスレーブを順番に仮マスタとして巡回させるためのスケジュールを作成するスケジュール作成手段と、このスケジュール作成手段により作成されたスケジュールを複数のスレーブに対して配布するスケジュール配布手段とを更に備えたことを特徴とすれば、クラスタであるピコネットの再構成にかかる時間を劇的に短縮し、現状では実質的に困難であったピコネットの再構成ができる点で好ましい。
また、不適切なマスタが選出されると、ピコネット全体の通信効率に直接、影響を与えてしまうが、複数のスレーブから仮マスタとして巡回した際の他の無線局との通信状態を受信する通信状態受信手段と、この通信状態受信手段によって受信された通信状態に基づいて、所定のスレーブに対してマスタとしての権限を委譲することを決定することを特徴とすれば、通信状態に応じて最も適切なスレーブに対して権限を委譲することができる点で優れている。
【００２３】
【発明の実施の形態】
以下、添付図面に示す実施の形態に基づいて本発明を詳細に説明する。
まず、クラスタを構成する各情報端末機器(ノード)の具体的な構成を説明する前に、本実施の形態が適用される通信の場としてのクラスタ構成について説明する。
図１は、本実施の形態にて実現されるクラスタヘッド交代によるクラスタ構成の最適化を説明するための図である。図１の▲１▼〜▲５▼はクラスタを構成するノード(情報端末機器)であり、図の右側は最適化前のクラスタ構成を示し、図の左側は最適化後のクラスタ構成を示している。最適化前では、ノード▲５▼がクラスタヘッドであり、他はクラスタメンバである。このクラスタヘッドの仕事としては、クラスタの管理や通信路の維持等が中心である。
【００２４】
まず、図１の右側である最適化前にて、クラスタヘッドであるノード▲５▼が、ノード▲２▼への通信状態の異常を検出したものとする。そこで、ノード▲５▼は、ノード▲１▼,▲２▼,▲３▼,▲４▼と順番に仮のクラスタヘッドとし、仮のクラスタメンバ全てとの接続電波状況を調査する。
図２は、各ノードにおける接続電波状況の一例を示した図であり、クラスタを構成する各ノードが、順番にクラスタヘッドとなった場合の通信状態を示している。図２に示すように、ノード▲５▼では、ノード▲２▼との通信状態が悪く、それ以外のクラスタメンバとの通信状態は良好であることを示している。図２に示す例では、ノード▲４▼がクラスタヘッドとなった場合に、各クラスタメンバとの通信状態が全て良好となっている。
【００２５】
クラスタヘッドにおいては、通常の通信パケットのやり取りをモニタすることで、定期的に通信状態を算出することができる。一方、仮のクラスタヘッドにおいては、基本単位になるパケットを次々にクラスタメンバに送ることで、通信状態を計測することができる。Bluetoothの場合であれば、１.２５ｍｓに１パケットの往復テストが可能であり、７個までのスレーブでは、１秒も観測すれば、１スレーブあたり１００パケットの統計を取ることができる。ピコネットに属するスレーブノードが少ない場合は、更に短時間での観測が可能となる。
【００２６】
その後、再度、ノード▲５▼がクラスタヘッドとなり、自らがクラスタヘッドである場合のクラスタメンバとの接続電波状況と、ノード▲１▼,▲２▼,▲３▼,▲４▼を仮のクラスタヘッドとした場合の接続電波状況とを比較し、ノード▲４▼がより適切であると判断される。この判断によって、クラスタヘッドをノード▲５▼からノード▲４▼に変更し、図１の左側である最適化後のクラスタ構成を得ることができる。この図１の左側では、ノード▲４▼がクラスタヘッドとなり、ノード▲５▼はクラスタメンバに変わることで、通信の不都合がなく、効率の良い通信を行うことが可能となる。
【００２７】
ここで、クラスタヘッド交代のアルゴリズムとしては、例えば、電波強度が距離の３乗に反比例するものと仮定すると、距離１のときの電波強度を１として、距離５が通信可能限界で電波強度は０.００８となる。このことから、例えば、ノードを距離３以内(電波強度０.０３７０以上)にできるようにマスタ(クラスタヘッド)を選ぶように構成することが可能である。また、クラスタヘッド交代の条件を、例えば、距離４以上(電波強度０.０１５６以下)のノードがある(リンクが落ちそうである)。としたり、距離３以上(電波強度０.０３７０以下)のノードがあり、しかも全てのノードにおける電波強度の差が５倍以内である(クラスタヘッドが端にある場合)。等として仮定することも可能である。
【００２８】
図３(ａ),(ｂ)は、適性度の判定を、例えばスループットで行った場合の例を示すものである。このスループットとは、ある一定時間に送れるデータの量であり、図３(ａ)は最適化前のクラスタヘッドがノード▲５▼である場合を示し、図３(ｂ)は最適化後でクラスタヘッドがノード▲４▼に変更された場合を示している。それぞれ、横軸はクラスタヘッドからの距離を示し、縦軸はスループットの比較レベルを示している。図３(ａ)に示す最適化前では、クラスタヘッド(ノード▲５▼)からの各クラスタメンバの距離が何れも遠く、スループットのレベルもかなり低くなっている。一方、最適化後の図３(ｂ)では、クラスタヘッド(ノード▲４▼)からノード▲５▼までの距離は遠いものの、その他のクラスタメンバからの距離が近くなり、スループットも大きく改善されているのが理解できる。
【００２９】
ブルートゥース(Bluetooth)においては、ピコネット(Piconet)が本実施の形態におけるクラスタに該当し、マスタ(Master)がクラスタヘッドに、また、スレーブ(Slave)がクラスタメンバに該当する。このBluetoothでは、リンクマネージャープロトコル(Link Manager Protocol)に相手の送信出力を上下させるコマンドLMP_incr_power_reqとLMP_decr_power_reqが用意されており、実質的にＡＧＣ(Automatic Gain Control)が働き、多くのデバイスについては適正受信レベルとなっている。ただし、マスタの受信状態が悪く、出力増を要求(LMP_incr_power_req)してもスレーブはこれ以上出力レベルを上げられない(LMP_max_power)と返事をする場合がある。通常、このような場合には、相手のスレーブからも出力レベルを上げるように要求(LMP_incr_power_req)されているにもかかわらず、すでにマスタにとって限界である(LMP_max_power)ことが多い。このような場合は、マスタを交換して、最大出力レベルを必要としないピコネット構成を試みる。
【００３０】
また、マスタにおいて、スレーブからの受信レベルは正常であるのに、多くのスレーブから受信レベルが不適当であるとされる、非対称な場合も考えられる。これは、最大出力レベルの異なったデバイスが混在してピコネットを構成している場合に起こる。かかる場合には、このデバイスがマスタとして不適である可能性が高いので、マスタを交換して、より妥当なピコネット構成を試みる。Bluetoothの実装では、出力レベルの段階や制御は、各メーカによって異なることから、出力レベルを知るインタフェースは提供せず、出力を増加または減少しようとするときに、すでに上限または下限であることを通知することしかできない。
【００３１】
本実施の形態をBluetoothに適応した場合、ピコネットの再構成によって通信状態の確保と消費電力の削減を図ることができる。また、Bluetoothにおいては、良好な通信状態では、マルチスロットパケットをＦＥＣ(Forward Error Correction)なしで送信できるため、最大(point-to-pointの通信に換算した場合)７２３.２ｋｂｐｓ(ＤＨ５パケット)の通信が可能であるが、通信状態が劣化すると、シングルスロットパケットをＦＥＣ付きで送信することになり、最大１０８.８ｋｂｐｓ(２/３ＦＥＣあり、ＤＭ１パケット)と１５％程度に低下してしまう。本実施の形態によって良好な通信状態を確保することにより、結果的にスループットを向上させることができる。Bluetoothでは、ＡＰＩとして提供されるＨＣＩ(Host Controller Interface)で、Get_Link_QualityおよびRead_RSSIのコマンドにより、特定リンクの状態を知ることができるが、それぞれの適正レンジの値は、Bluetoothのホストコントローラ(Host Controller)の実装によって異なるため、各製造会社のスペックを参照することになる。
【００３２】
次に、クラスタを構成する情報端末機器(ノード)の構成から、本実施の形態を詳細に説明する。
図４は、本実施の形態における情報端末機器(ノード)の構成を説明するための機能構成図である。ここでは、制御装置としてクラスタヘッド適性度判定装置１１、クラスタヘッド交代スケジュール作成装置１２、およびスケジュール実行装置１３を備えている。また、機能装置として、リンク状態適性度監視装置２１、リンク状態表配布装置２２、テストデータ送信装置２３、スケジュール表配布装置２４、リンク状態表受信装置２５、クラスタ再構成装置２６、クラスタヘッド適性度表管理装置２７、推奨クラスタヘッド決定装置２８、およびスケジュール表受信装置２９を備えている。尚、図４において、実線は制御関係を示しており、破線はデータの流れを示している。
【００３３】
このクラスタヘッド適性度判定装置１１は、図２に示したような自らのノードとクラスタ内における他のノードとの接続電波状況を把握したリンク状態表１４を備え、自らがクラスタヘッドとなった場合に稼動し、クラスタヘッドの交代を試みるか否かを判定している。クラスタヘッド交代スケジュール作成装置１２は、クラスタ内における各ノードのスケジュール表１５を保持し、クラスタヘッドを交代する際に各ノードにて同期した行動が取れるように、各ノード毎に、いつ、何をするのか、のプログラムを作成している。スケジュール実行装置１３は、自ノードスケジュール表１６に従い、必要な機能を実行している。
【００３４】
リンク状態適性度監視装置２１は、クラスタヘッドとクラスタメンバとのリンク状態を監視し、エラーレートなどの統計情報を収集する(リンク状態表１４を作成する)機能を有する。作成されたリンク状態表１４は、クラスタヘッド適性度判定装置１１に送られる。リンク状態表配布装置２２は、リンク状態適性度監視装置２１で作成されたリンク状態表１４を他のノードに対して配布する機能を備えている。テストデータ送信装置２３は、仮クラスタヘッドになった場合に、各仮クラスタメンバへテストデータを送る機能を有する。スケジュール表配布装置２４は、他のノードに対してスケジュール表１５を送信する機能を有している。リンク状態表受信装置２５は、リンク状態表１４を受信する機能を有する。クラスタ再構成装置２６では、Page ScanやPageが行われ、クラスタ構成が変更される。クラスタヘッド適性度表管理装置２７では、各ノードにおいてリンク状態適性度監視装置２１で測定した結果が蓄えられる。本来はクラスタヘッドでのみ管理されれば充分であるが、仮クラスタヘッドを一巡した後、もとのクラスタに復帰できるとは限らないので、念のため、全てのノードで保持することが効果的である。推奨クラスタヘッド決定装置２８は、各ノードをクラスタヘッドとした場合のリンク状態表１４を並べてみて、リンク状態表１４を評価し、順位付けする機能を備える。また、スケジュール表受信装置２９は、他ノードよりスケジュール表を受信する機能を備えている。
【００３５】
図５は、本実施の形態におけるクラスタの最適化処理の流れを示したフローチャートである。まず、クラスタヘッドでは、クラスタヘッド適性度判定装置１１を活性化させ、リンク状態適性度監視装置２１による全てのクラスタメンバとの通信状態を把握して、リンク状態表１４を作成する(ステップ１０１)。そして、このリンク状態表１４に基づいて、通信状態不良のノードがあるか否かが判断される(ステップ１０２)。例えば、クラスタヘッドでは、クラスタメンバ毎にパケットエラーレートを記録し、この記録からクラスタ全体のエラーレートの平均値、標準偏差などを算出しクラスタヘッドとして適格であるか否かが判定される。特定の幾つかのクラスタメンバに対するエラーレートのみが高い場合や、全てのクラスタメンバに対するエラーレートが高い場合は、クラスタヘッドが不適格である場合が多い。ステップ１０２にて通信状態不良がないと判断される場合、即ち、クラスタが正常動作中である場合には、クラスタヘッドの交代を行う必要がなく、しばらくは現状のクラスタヘッドがクラスタヘッドとして通信に専念する(ステップ１０３)。クラスタヘッド適性度判定装置１１では、常に各ノードとの通信状態を監視しているリンク状態適性度監視装置２１の情報をもとに、リンク状態表１４を更新している。この通信状態不良がない場合には、他のノードであるクラスタメンバでは、特に何も行われない。
【００３６】
次に、ステップ１０２で通信状態不良があると判断される場合、即ち、クラスタヘッド適性度判定装置１１にて、一部のノードとのリンク状態が健全ではないことが検出されると、クラスタヘッドの交代を試みる決断がなされる。このクラスタヘッドの交代は、クラスタ内の各ノードを仮クラスタヘッドとし、この仮クラスタヘッドとして動作している間のリンク状態表１４が作成される。その後、この結果を集計して、相応しいクラスタヘッドを決定し、必要であればクラスタヘッドの交代を行うことで実現される。
【００３７】
このクラスタヘッドの交代作業に際し、クラスタヘッド交代スケジュール作成装置１２によって、各ノード毎に、いつ、何をすべきかのスケジュール表１５が作成される(ステップ１０４)。即ち、ここでは、仮クラスタヘッド評価のためのクラスタヘッド巡回プログラムであるスケジュール表１５が作成される。この相応しいクラスタヘッドを選定するに際しては、一時的にせよクラスタヘッドの交代が伴うことから、クラスタヘッドの交代に伴うオーバーヘッドを削減するために、事前にどのタイミングでクラスタヘッドを交代するというスケジュール表１５の作成が必要となる。このスケジュール表１５の作成にあたっては、クラスタのノード間での時刻ずれがないことが前提となる。但し、一般に、クラスタメンバはクラスタヘッドによって同期しており、例えば、Bluetoothでは、全てのノードはマスタのクロックに同期し、時刻のずれはない。また、スケジュール表１５の作成では、仮クラスタヘッドの巡回の手順と、元のクラスタヘッドへの回復手順を定め、それぞれの各手順において、各ノードの果たすべき役割が時刻毎に記述されている。
【００３８】
次に、スケジュール表配布装置２４から各ノードに対して、現在のクラスタ構成を利用してスケジュール表１５の配布が行われる(ステップ１０５)。同時に、クラスタヘッドによる不都合なリンク状態表１４も、後で必要となる場合を考慮して、全てのクラスタメンバに配布される。クラスタヘッドでは、自らのスケジュール表１５をスケジュール実行装置１３に自ノードスケジュール表１６として格納し、各クラスタメンバでは、クラスタヘッドから配布された自らのスケジュール表１５を、各クラスタメンバにおけるスケジュール実行装置１３に自ノードスケジュール表１６として格納する。
【００３９】
ここで、例えば、クラスタを構成するノードがノードＡ〜ノードＦで、現状のクラスタヘッドがノードＡ(クラスタヘッドＡ)であり、ノードＤとの通信に不都合があったとする。この場合、例えば、仮のクラスタヘッドをＡ→Ｂ→Ｃ→Ｅ→Ｆ→Ｄのように巡回させてリンク状態が評価される。また、評価後は、通常クラスタヘッドＡの現状に回復するものとするが、例えばノードＡが移動していなくなる等の回復不可能な場合を考慮して、どのようなクラスタとして回復するのかも順序付けしておくことが好ましい(例えば、Ａ→Ｂ→Ｃ→Ｅ→Ｆ→Ｄの順等)。
【００４０】
この巡回として、例えば、５秒後から１５秒ずつ、仮マスタをＢ(５秒〜２０秒)、 Ｃ(２０秒〜３５秒)、Ｅ(３５秒〜５０秒)、Ｆ(５０秒〜６５秒)、Ｄ(６５秒〜８０秒)と循環させ、その後(８０秒後)、クラスタヘッドＡとする元のクラスタ構成に戻るものとする。尚、不幸にして戻れなかった場合は、それぞれのクラスタメンバは、自分をクラスタヘッドとして順次、クラスタを回復しようとする。例えば、９０秒後までにＢがＡをクラスタヘッドとするクラスタに戻れなかった場合は、Ｂが９０秒後にクラスタ回復を試み、１００秒後までにＣがＡまたはＢをクラスタヘッドとするクラスタヘッドに戻れなかった場合は、Ｃが１００秒後にクラスタ回復を試み、以下同様に、Ｅは１１０秒後、Ｆは１２０秒後、Ｄは１３０秒後に、それぞれクラスタマスタとして他のメンバを迎えてクラスタを回復しようとする。つまり、元のクラスタヘッドＡのスケジュール表１５としては、５秒後、２０秒後、３５秒後、５０秒後、６５秒後にPage Scanを連続的に起動して仮クラスタヘッドのメンバになろうとし、８０秒後には、逆に、元のクラスタメンバに対してPageを順次行い、クラスタメンバとして取り込み、元のクラスタ構成を回復するものとなる。一方、元のクラスタメンバＢのスケジュール表１５としては、５秒後には、全てのクラスタメンバＡ,Ｃ,Ｄ,Ｅ,ＦにPageを順次行い、仮クラスタを構成し、通信状態のテストを行い、１５秒後までにはこの仮クラスタを解消し、更に、２０秒後、３５秒後、５０秒後、６５秒後には、Page Scanを連続的に起動し、他の仮クラスタヘッドのメンバになろうとし、８０秒後には、また、Page Scanを行い、Ａをクラスタヘッドとする元のクラスタ構成に戻ろうとする。ここで、９０秒後までにＡをクラスタヘッドとする元のクラスタ構成に戻れない場合は、Pageを起動し、自分をクラスタヘッドとし、クラスタの回復を試みるものとなる。
【００４１】
このとき、クラスタメンバにおいては、各々のノードにおけるスケジュール表受信装置２９にてスケジュール表１５を受信し、スケジュール実行装置１３にセットされる。また、現状のクラスタヘッド(例えばノードＡ)におけるリンク状態表１４も念のため送付されてくるので、仮クラスタヘッド巡回終了後に比較できるように、クラスタヘッド適性度表管理装置２７に蓄えられる。
【００４２】
次に、スケジュール表１５どおりにクラスタメンバが協調・同期して、仮クラスタヘッドを巡回させ、リンク状態を評価する(ステップ１０６)。このとき、元のクラスタヘッド(ノードＡ)は、その巡回期間中、クラスタメンバとして動作する。仮クラスタヘッドの巡回は、ノードＡ用のスケジュールに従い、Page Scanを行い、次々に仮のクラスタヘッドを変えていく。このとき、クラスタ再構成装置２６は、Page ScanやPageを行いクラスタ構成を変更している。ここで、それぞれの仮クラスタに接続できた場合は、ノードＡに対して仮クラスタヘッドからその時のリンク状態表１４が送られてくるので、それをクラスタヘッド適性度表管理装置２７に蓄えておく。接続できなかった場合は、後に別のクラスタヘッドに接続した時に、そのノードのクラスタヘッド適性度表管理装置２７から受け取るものとする。仮クラスタでクラスタヘッドとして動作する各ノードは、クラスタ再構成装置２６を起動して仮クラスタを構成し、テストデータ送信装置２３を使用して各クラスタメンバへテストデータを送信し、リンク状態適性度監視装置２１にてテストデータの送受信状態の表であるリンク状態表１４を作成する。作成したリンク状態表１４は、リンク状態表配布装置２２によって各クラスタメンバへ通知すると同時に、自らのクラスタヘッド適性度表管理装置２７にも蓄えておく。
【００４３】
次に、元のクラスタヘッドであるノードＡは、自身をクラスタヘッドとした場合に比べてかなり優れたリンク状態表１４があるか否かが判断される(ステップ１０７)。即ち、今までに集めたノードＡ,Ｂ,Ｃ,...Ｆのリンク状態表１４を、クラスタヘッド適性度表管理装置２７から推奨クラスタヘッド決定装置２８へ転送し、改善効果等が比較判断される。この判断の結果、かなり優れたリンク状態表１４がない場合には、元のクラスタ構成に戻してそのまま落ち着き、現状のクラスタヘッドがしばらくクラスタヘッドとして通信に専念する(ステップ１０３)。尚、クラスタヘッド適性度表管理装置２７は、同じ不都合(例えば、ノードＤとのリンク状態が不健全)が発生した場合に、クラスタヘッドの変更を試みても再度却下される可能性がある。そのために、例えば、他の不都合が発生するまで、この不都合の度合いが更に悪くなるまで、相当時間が経過するまで、等の条件で、この不都合を許容するように構成することができる。
【００４４】
次に、ステップ１０７にてかなり優れたリンク状態表１４がある場合には、元のクラスタ構成に戻った後に、クラスタヘッドが交代される。例えば、比較判断の結果、ノードＣが優れていることを発見し、クラスタヘッドＣに委譲する等である。このとき、現状のクラスタヘッドであるノードＡは、クラスタヘッドを委譲するためのプログラムを作成して配布する(ステップ１０８)。即ち、ノードＡにおけるクラスタヘッド交代スケジュール作成装置１２は、仮クラスタヘッド巡回の時と同様に、各ノードで実行すべきスケジュール表１５を作成し、スケジュール表配布装置２４によって、各クラスタメンバに配達し、同時に、自らのスケジュール表１５は自ノードスケジュール表１６として、自らのスケジュール実行装置１３に渡される。
このとき、クラスタヘッドを交代するにしても、同期をとって効率よく交代するために、最終的なクラスタヘッドとしてＣ、それがだめならＡ、それがだめならＢ、Ｅ、Ｆ、Ｄとすべてのノードに順序付けし、スムースな変更をする必要がある。そこで、本実施の形態では、クラスタヘッドとして優れているノードの順番をクラスタヘッド交代スケジュール作成装置１２へ通知するように構成している。
【００４５】
より具体的に述べると、スケジュールとして、例えば、Ｃ,Ａ,Ｂ.Ｅ,Ｆ,Ｄの順にクラスタヘッドとして適しているとすれば、各々１０秒後毎にクラスタヘッドとし、残りのノードをクラスタに取り込むように動作させることができる。例えば、Ｃは１０秒後からPageをして各々のノードを取り込んでクラスタを構成しようとする。Ａは１０秒後からPage ScanをしてＣに取り込まれようとし、だめであれば２０秒後から自らPageをし、他のノードを次々に取り込んでクラスタを構成しようとする。Ｂは１０秒後からPage Scanをし、ＣまたはＡのノードに取り込まれようとし、だめであれば自らが３０秒後からPageをし、他のメンバを次々に取り込みクラスタを構成しようとする。このようにして、Ｅ,Ｆ,Ｄについても同様な手順が図られるように、スケジュール表１５が作成される。
【００４６】
各クラスタメンバは、クラスタヘッドより送られてきたスケジュール表１５を受信し、自らのスケジュール実行装置１３にセットする。スケジュール実行装置１３では、クラスタ再構成装置２６を使用しながらクラスタ構成を変更し、うまくクラスタが構成されるまで、スケジュールを実行する。これによって、最適なノードがクラスタヘッドとして設定される(ステップ１０９)。
【００４７】
以上のような流れによって、最も効率が高いと判断されるノードをクラスタヘッドとして選択することが可能となるが、ステップ１０３に移る際に、現状のクラスタヘッドを用いた元のクラスタ構成に戻れない場合が考えられる。例えば、元のクラスタヘッドであるノードＡが電源断や移動等によって機能しなくなった場合等である。このような場合には、クラスタメンバに事前に順位を付けておき、リカバリのためのクラスタヘッドとなる時刻と期間、特定のリカバリにおけるクラスタヘッドのクラスタメンバとなろうとする時刻と期間を登録しておき、元のクラスタに近い形で回復できるようにする。即ち、前述の仮クラスタヘッドの巡回と同様に、クラスタヘッド交代スケジュール作成装置１２におけるクラスタヘッド交代のスケジュール表１５に基づき、例えば、Ｂ,Ｃ,...の順にクラスタが回復される。このように構成することで、クラスタ構成にエラーが生じた場合であっても、問題なく動作させることが可能となる。
【００４８】
尚、本実施の形態では、全てのクラスタメンバに対してクラスタヘッド適合検査を行い、また、全てのクラスタメンバがリカバリクラスタヘッダとなり得る場合について説明したが、クラスタメンバ個々の能力、過去の履歴などに応じて、幾つかのクラスタメンバを除くことも可能である。この幾つかのクラスタメンバを除くことによって、効率化が図れる場合も考えられる。
【００４９】
以上、詳述したように、本実施の形態によれば、クラスタの再構成にかかる時間を短縮するために、無線局(ノード)にかかわる情報を再構成以前に各無線局に配布し、無線局探索に必要な作業を軽減することができる。即ち、本実施の形態では、一時的、または最終的にクラスタヘッドを交代させるための手続きと、万一、クラスタヘッド交代作業中にエラーが発生した場合の復旧方法とを組として事前にスケジュールしておくように構成している。これによって、例えば、無線アドホック通信に特有な、無線局の移動や通信状態の不良に対しても、適切に対処することができる。
【００５０】
更に、本実施の形態では、順番にクラスタヘッドを交代させていく前に、個々の構成無線局(ノード)に対して、クラスタヘッドとしてクラスタを構成する時刻と期間とを相互に確認し、同期させて交代させている。これによって、いずれかの段階でも、各無線局は、クラスタヘッドとして動作すべきか、またはどのクラスタヘッドに対するクラスタメンバとして動作すべきか、が決まっており、交代の最中にクラスタヘッドとして機能できない無線局が発生したり、接続できないクラスタメンバを持つクラスタヘッドが形成されたとしても、当初の設定された一定時間で自動的に回復することができる。このクラスタヘッドの交代のメカニズムは、最適クラスタヘッド探索の際におけるクラスタヘッド巡回の場合だけではなく、探索後の評価を目的として元のクラスタ構成に戻るときや、最適なクラスタへのクラスタヘッド委譲の際にも用いることが可能である。
【００５１】
また、前述したように、Bluetoothでは、通信の開始に、無線局の探索のためのInquiryと、スレーブ局と接続を行うためのPageというプロセスが必要となり、標準的なプロセスでは、非常に多くの時間を必要としてしまう。しかしながら、本実施の形態を適用すれば、再構成を行う前にクラスタ所属の無線局の情報を各無線局に配布することで、Inquiryプロセスを不要とし、更に、Pageプロセスにかかる時間も２０ｍｓ程度まで劇的に短縮することが可能となる。従って、現状では実質的に不可能な、クラスタ再構成を可能とし、通信効率の向上を図ることが可能となる。特に、Bluetoothでは、小規模のクラスタが重なってできており、電波の干渉が起こり易く、従来の方式である、一度形成されたクラスタを解消して新たに探索をしてからクラスタを作る方法では、オーバーヘッドが余りにも大きくなる。しかしながら、本実施の形態によれば、同期させてクラスタを再構成することが可能となり、これらのオーバーヘッドを防止することができる。
【００５２】
更に、Bluetoothでは、１つのピコネット(クラスタ)では、１つのマスタ(クラスタヘッド)と７つまでの活動的なスレーブ(クラスタメンバ)から構成されるため、クラスタ内のメンバ数に８という上限があり、一般のアドホックネットワークよりも制約が強い。即ち、ピコネットは、８つまでの無線局しか扱えないことから、８つ以上の無線局が存在する場合に、たとえ全てが電波の届く範囲であったとしても、複数のピコネットをブリッジで繋ぐという構成をとる必要がある。しかしながら、本実施の形態を適用すれば、例えば、無線局の減少により２つのピコネットを併合しても良いときなど、動的にクラスタを再構成することが可能となり、即ち、複数のピコネットを対象とした分割、併合にも応用でき、Bluetoothにおけるアドホックネットワークの実現に際しても非常に有効である。
【００５３】
【発明の効果】
以上詳述したように、本発明によれば、クラスタヘッドの不適格な状態を検出して、より良いクラスタヘッドを再選出することが可能となる。
【図面の簡単な説明】
【図１】 本実施の形態にて実現されるクラスタヘッド交代によるクラスタ構成の最適化を説明するための図である。
【図２】 各ノードにおける接続電波状況の一例を示した図である。
【図３】 (ａ),(ｂ)は、適性度の判定を、例えばスループットで行った場合の例を示す図である。
【図４】 本実施の形態における情報端末機器(ノード)の構成を説明するための機能構成図である。
【図５】 本実施の形態におけるクラスタの最適化処理の流れを示したフローチャートである。
【符号の説明】
１１…クラスタヘッド適性度判定装置、１２…クラスタヘッド交代スケジュール作成装置、１３…スケジュール実行装置、１４…リンク状態表、１５…スケジュール表、１６…自ノードスケジュール表、２１…リンク状態適性度監視装置、２２…リンク状態表配布装置、２３…テストデータ送信装置、２４…スケジュール表配布装置、２５…リンク状態表受信装置、２６…クラスタ再構成装置、２７…クラスタヘッド適性度表管理装置、２８…推奨クラスタヘッド決定装置、２９…スケジュール表受信装置

Claims (13)

1. 複数の無線局の間で所定のクラスタを形成し、当該クラスタの管理を行うクラスタヘッドを選択してグループ通信を行う通信方法であって、
   前記クラスタを構成する前記クラスタヘッド以外の無線局を仮クラスタヘッドとして巡回させる動作および当該クラスタを構成するそれぞれの無線局が当該仮クラスタヘッドに対して接続を試みる動作、当該仮クラスタヘッドとして巡回させる動作の後に元のクラスタ構成に戻る動作を定めたスケジュールを生成し、
   前記クラスタを構成する無線局は、生成された前記スケジュールに基づいて同期して動作し、
   前記クラスタに属する無線局の１つ以上を仮クラスタヘッドとして動作させ、
   前記無線局が前記仮クラスタヘッドとなった場合における通信効率を判定し、
   判定された前記通信効率に基づいて前記クラスタを構成する無線局の中から当該クラスタにおけるクラスタヘッドを選定することを特徴とする通信方法。
2. 前記グループ通信は、スレーブ間通信ができないマスタ・スレーブ構成をとる無線アドホックネットワークにおいてなされることを特徴とする請求項１記載の通信方法。
3. 前記元のクラスタに戻る動作の後に当該元のクラスタ構成に戻れない場合の回復動作をさらに前記スケジュールとして定めることを特徴とする請求項１記載の通信方法。
4. クラスタヘッドであるノードおよび１つ以上のクラスタメンバであるノードからなるクラスタを構成する無線アドホックネットワークにおいて、
   前記クラスタヘッドであるノードは、前記クラスタメンバであるノードに対する自らのリンク状態を把握し、当該リンク状態の把握に基づいて、前記クラスタを構成する前記クラスタヘッド以外の前記クラスタメンバを仮クラスタヘッドとして巡回させる動作、当該仮クラスタヘッドとして巡回させる動作の後に元のクラスタ構成に戻る動作を定めたクラスタヘッド交代スケジュールを生成して当該クラスタメンバであるノードに配布し、
   前記クラスタメンバであるノードは、配布された前記クラスタヘッド交代スケジュールに基づき前記クラスタを構成するノードに対する自らのリンク状態を把握して前記クラスタヘッドであるノードに送信することを特徴とする無線アドホックネットワーク。
5. 前記クラスタヘッドであるノードは、前記クラスタメンバであるノードから送信された前記リンク状態に基づいてクラスタヘッドの権限を委譲するか否かを判断し、委譲する場合には、委譲してもよいノードに対して権限の委譲を試みることを特徴とする請求項４記載の無線アドホックネットワーク。
6. 前記クラスタヘッドであるノードは、委譲してもよい前記ノードに対する委譲に失敗した場合には、自らがクラスタヘッドを継続する元のクラスタ構成に戻れるように、元のクラスタ構成に戻る時刻を定めることを特徴とする請求項５記載の無線アドホックネットワーク。
7. クラスタヘッドであるノードおよび１つ以上のクラスタメンバであるノードからなるクラスタを構成する無線アドホックネットワークにおいて、
   前記クラスタヘッドは、前記クラスタを構成する前記クラスタメンバに対して当該クラスタメンバを仮クラスタヘッドとして巡回させる動作、当該仮クラスタヘッドとして巡回させる動作の後に元のクラスタ構成に戻る動作を定めたスケジュールを配布し、
   前記クラスタメンバは、配布された前記スケジュールに基づき、仮クラスタヘッドとして他のノードとの通信状態を把握して前記クラスタヘッドに送信し、当該クラスタヘッドからの権限の委譲に基づいて、新たにクラスタヘッドとなり得ることを特徴とする無線アドホックネットワーク。
8. 前記クラスタヘッドは、前記クラスタの構成直後、または、エラーレートの高いノードが検出された時点で前記巡回動作を定めたスケジュールを配布することを特徴とする請求項７記載の無線アドホックネットワーク。
9. クラスタを構成する複数のノードの１つとして構成可能であると共に、当該複数のノードの中でクラスタヘッドとして当該クラスタを構成する残りのノードであるクラスタメンバとの通信を可能とする通信端末であって、
   前記クラスタメンバとのリンク状態を把握するリンク状態把握手段と、
   前記クラスタメンバを仮クラスタヘッドとして巡回させる動作、当該仮クラスタヘッドとして巡回させる動作の後に元のクラスタ構成に戻る動作を定めたスケジュールを作成するスケジュール作成手段と、
   前記スケジュール作成手段により作成された前記スケジュールを前記クラスタメンバに対して配布するスケジュール配布手段と、
   前記スケジュール配布手段により配布された前記スケジュールに基づいて同期して動作する前記クラスタメンバが仮クラスタヘッドとなった場合における他のノードとのリンク状態を認識する仮クラスタヘッドリンク状態認識手段と、
   前記リンク状態把握手段により把握されたリンク状態と、前記仮クラスタヘッドリンク状態認識手段により認識されたリンク状態とに基づいて、特定のノードへのクラスタヘッドの委譲を決定する委譲決定手段とを備えることを特徴とする通信端末。
10. 前記リンク状態把握手段は、前記クラスタメンバごとにテストデータを送信してパケットエラーレートを検出することによりリンク状態を把握することを特徴とする請求項９記載の通信端末。
11. 前記スケジュール作成手段により作成される前記スケジュールは、適切なクラスタヘッド候補を探索するために、仮クラスタヘッドをノード間で巡回させる時刻、それぞれのノードが仮クラスタヘッドに対して接続を試みる時刻、および試みようとする接続が失敗した場合に再接続を繰り返す期間が定められていることを特徴とする請求項９記載の通信端末。
12. 前記スケジュール作成手段は、前記リンク状態把握手段により前記リンク状態に問題があると判断される場合に、前記スケジュールを作成することを特徴とする請求項９記載の通信端末。
13. ピコネットを構成する複数の無線局の１つとして構成可能であると共に、マスタとして複数のスレーブを管理することができるブルートゥース端末であって、
    前記ピコネットを構成する前記複数のスレーブを順番に仮マスタとして巡回させる動作、当該仮マスタとして巡回させる動作の後に元のピコネット構成に戻る動作を定めたスケジュールを作成するスケジュール作成手段と、
    前記スケジュール作成手段により作成された前記スケジュールを前記複数のスレーブに対して配布するスケジュール配布手段と、
    前記スケジュール配布手段により配布された前記スケジュールに基づいて、前記複数のスレーブから、仮マスタとして巡回した際の他の無線局との通信状態を受信する通信状態受信手段と、
    前記通信状態受信手段によって受信された通信状態に基づいて、自らがマスタとして不適当であると判断される場合には、前記ピコネットを構成する所定のスレーブに対してマスタとしての権限を委譲して当該ピコネットの再構成を行う権限委譲手段とを備えたことを特徴とするブルートゥース端末。

Images