ノード装置及びプログラム
【課題】簡易な構造で、かつ、ネットワークに負荷をかけずに、自律的に適切な経路を選択可能なノード装置／プログラムを提供する。
【解決手段】通信ネットワークの中のノード装置１において、ＦＩＤ管理テーブル５にフレームを一意に識別するＦＩＤとフレームの送出先ノードに関する情報とを格納し、重み付けテーブル７にフレームの最終宛先ノードごとに、フレームを中継するため送出先とする他ノードについての重み付け情報を格納する。自ノード宛に送信されたフレームを受信すると、受信したフレームのＦＩＤがＦＩＤ管理テーブル５に格納されている場合には、ＦＩＤと対応付けられた送出先ノードについてのデータを更新する。フレーム受信手段により受信したフレームのＦＩＤが、ＦＩＤ管理テーブル５に格納されていない場合には、フレームの宛先ノードに該当する重み付けテーブル５を参照して、フレームを中継するための宛先とする他ノードを決定する。
【解決手段】通信ネットワークの中のノード装置１において、ＦＩＤ管理テーブル５にフレームを一意に識別するＦＩＤとフレームの送出先ノードに関する情報とを格納し、重み付けテーブル７にフレームの最終宛先ノードごとに、フレームを中継するため送出先とする他ノードについての重み付け情報を格納する。自ノード宛に送信されたフレームを受信すると、受信したフレームのＦＩＤがＦＩＤ管理テーブル５に格納されている場合には、ＦＩＤと対応付けられた送出先ノードについてのデータを更新する。フレーム受信手段により受信したフレームのＦＩＤが、ＦＩＤ管理テーブル５に格納されていない場合には、フレームの宛先ノードに該当する重み付けテーブル５を参照して、フレームを中継するための宛先とする他ノードを決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードを含むネットワークにおける、経路選択可能な装置／プログラムに関する。
【背景技術】
【０００２】
ネットワーク装置は、これまで非常に多くの研究がなされている。最も普及しているのは、ＩＰ（Internet Protocol）ネットワークを利用したネットワーク装置である。また
、複数のプロトコルやネットワークを収容することを目的としたＭＰＬＳ（Multi Protocol Labeled Switching）は、自動的に経路を作成する機構を持つネットワーク装置である。また、アドホックアルゴリズムの代表例としてＡＯＤＶ（Ad-hoc On-Demand Vector）
やＯＬＳＲ（Optimized Link State Routing）がある。
【０００３】
ＩＰネットワーク装置では、ＩＰアドレスに従いルーティングを決定する。ＩＰアドレス自体が木構造を持つため、ＩＰアドレスの上位から合致するＩＰネットワークを管理するネットワーク装置に伝送することで、最終的に目標とする端末へフレームを伝送することができる。ルーティングはＩＰアドレス体系により決定されている。どのネットワーク装置かどのＩＰネットワークを管理しているかは、ルーティングテーブルによって規定される。ルーティングテーブルは主に手動で設定されることも多いが、ＲＩＰ（Routing Information Protocol）により自動的に更新されることもある。ＲＩＰとは、ネットワーク装置が管理するＩＰネットワークを周囲にブロードキャストし、ネットワーク装置が互いの管理するＩＰネットワークを確認する方式である。
【０００４】
ＭＰＬＳでは、ネットワークがＬＳＲ（Label Switch Router）と呼ばれるネットワー
ク装置間と外部ネットワークとに分離される。外部ネットワークからのフレームは、エッジノードと呼ばれる外部ネットワークと内部ネットワークの両方にまたがるネットワーク装置によって内部ネットワークに取り込まれる。このとき、外部フレームの先頭にはラベルが挿入される。各ＬＳＲは、それぞれがラベル転送テーブルを持つ。ラベル転送テーブルは、入力フレームのラベルと出力フレームのラベルおよびあて先を保持する。ＬＳＲは入力されるフレームのラベルを取り出し、該当するラベルをラベル転送テーブルから発見し、出力フレームのラベルに書き換え、該当するあて先に送出する。ラベル転送テーブルのＬＤＰ（Label Distribution Protocol）によって行われる。ＬＤＰは、まずＲＩＰな
どによりルーティングテーブルの作成を行い、これにラベルを付加し、隣接ノード間で通知しあうプロトコルである。
【０００５】
ＡＯＤＶは、経路検索にブロードキャストを用いて、他の通信ノード装置がブロードキャストを繰り返し目的のノード装置への経路を発見する手法である。通信ノード装置は、目標とする経路を発見するために周囲に「Route Request（ＲＲＥＱ）」というフレーム
を送出する。このフレームには、検索目標の通信ノードＩＤが明記されている。周囲の通信ノード装置は、自身を検索していない場合は、新たにＲＲＥＱフレームを作成して、周囲へのブロードキャストを繰り返し行う。このとき各通信ノード装置は、送り元のメッセージが、隣接するどの通信ノード装置から受信されたものなのかを記録する。ＲＲＥＱメッセージが目的の通信ノード装置に達したとき、その目的の通信ノード装置は、「Route Reply（ＲＲＥＰ）」フレームを作成し、送り元のノードに対して、ＲＲＥＱフレームが
送られてきた経路をたどるようにしてＲＲＥＰフレームを送信する。このようにして、双方向の通信経路が作成されている。
【０００６】
ＯＬＳＲ（Optimized Link State Routing）では、通信ノード装置同士が定期的にフレ
ームを交換しあうことで、ネットワーク全体を把握し、目的の通信ノードまでの経路を検出するという方式を採用している。通信ノード装置は、周期的にＨＥＬＬＯ（ハロー）フレームを送出し、互いにその存在を通知しあう。通信相手となる通信ノード装置の存在が判明したところで次に効率的にネットワーク全体にフレームを配信するためのフラッディング用のパスを生成する。これをＭＰＲ（Multi Point Relay）と呼ぶ。ＭＰＲにより、
各通信ノード装置から効率よくフレームをネットワーク全体へブロードキャストできる。次にこのＭＰＲを用いて、経路作成メッセージであるＴＣ（Topology Control）フレームをノード装置同士が互いに配信することで全ノード装置がネットワークトポロジーを知ることができる。フレームを、目標とする通信ノード装置に送るには、送出元となる通信ノード装置自身が知っているネットワークトポロジーを参照し、送るべき隣接通信ノード装置にフレームを託す。隣接ノード装置も同様に処理を行い、最終的に目標ノード装置にフレームを届ける。
【０００７】
アドホック無線通信ネットワークに関しては、公知の技術として、各ノードがハローメッセージとして自ノードの存在を通知する情報と、自ノードまでのルートメトリックとを含んだ情報を放送し、該ハローメッセージを受信した他ノードは、受信したルートメトリックにハローメッセージを放送してきたノードと自ノードとの間のルートのためのルートメトリックを追加し、該追加後のルートメトリックを使用する技術について提供されている（例えば、特許文献１）。ここでのルートメトリックは、ホップ数、リンク品質等の因子により算出される、送信元と宛先とのコストを表す値である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特表２００６−５２６９３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＩＰネットワーク装置やＭＰＬＳでは、前提としてアドレスによってネットワーク自体が構造を持っていることを利用している。ＩＰアドレスが木構造であるため、アドレスが上位からマッチしていく方向を選択することにより経路が決定する。また、これらは有線の接続を前提としている。２つの通信端末間で有線接続は安定した通信ができ、接続されていない通信機器はフレームを受信することはないため、単純に通信機のホップ数だけで決めることができる。
【００１０】
しかし無線通信を前提としたとき、これらの方式では通信品質のよい経路作成は困難である。無線通信では、通信品質は有線通信と比較した場合に悪く、かつ通信とは直接関係しない他の通信端末にも影響を与える。また通信品質は、距離や周囲の環境の依存性も高く、時間的変化も伴う。このような環境下で上記プロトコルを実施した場合、ホップ数のみで決定すると、アルゴリズムが遠くの通信端末を経由しようとする場合がありえる。しかしながら、距離が遠ければその分通信品質も悪いため非常に品質の悪い経路を作成してしまう。
【００１１】
ＡＯＤＶは、経路作成時にネットワークに負荷をかける。通信端末数が少ない場合は問題ないが、通信端末数が多くなり通信量が増えた場合ネットワークへの負荷が高くなってしまう。その結果、通信がすでに確立している通信ノード装置にも影響を与え、リンク切れを起こす可能性が高く、結果的に通信できるノード装置は非常に少なくなりそのほとんどが経路確立できなくなる。また、上記のようにホップ数をベースとしているため通信品質の悪い経路を作成してしまうことも考えられる。
【００１２】
ＯＬＳＲでは、全ノード装置がネットワークトポロジーを知る必要がある。このためス
ケールに限界が生じる。また、全ノード装置のトポロジーが判明する時間が必要となる。
【００１３】
上記のとおり、有線無線を問わず、ネットワークにおいては、通信量や周囲の環境影響によりノード装置間の通信品質が変化することがあり、特に無線では変化が大きい。このため、非常に多くのノード装置を含んだネットワークを考えた場合、ネットワークを統括するサーバを設置し、該サーバによってネットワークの管理を行うことは実用的ではない。というのは、ノード装置の個数が多いのでサーバから制御指示を送信するだけでも大変な負荷になってしまうからである。そこで、非常に多くのノード装置からネットワークがつくられている場合には、各ノード装置が自律的に経路選択や死活監視などの動作をすることが望まれる。
【００１４】
さて、各ノード装置が自律的に動作することを考えた場合、上述の通り通信品質は変化するので、あるノード装置に宛てた送信フレームを中継する際には、現時点で有効な経路を各ノード装置が把握しておく必要がある。例えば、固定的な構造を持つネットワークや一般的な検索手法である二分木探索などの手法では、ネットワークや木の全体像が初めからわかっているため、どこまで経路を探索したかを容易に判別可能であるのに対し、本願が対象とするノード装置間のリンクが変化してゆくようなネットワークでは、各ノード装置は、周囲のノード装置の先にどのようなノード装置がリンクされているかを知らないので、どこまで経路を探索したかを知るための仕組が必要になる。
【００１５】
本発明では、簡易な構造で、かつ、ネットワークに負荷をかけずに、自律的に適切な経路を選択可能なノード装置／プログラムを提供する。
【課題を解決するための手段】
【００１６】
本発明の実施形態にかかるノード装置は、複数のノード装置を含むネットワークの中の、ノード装置において、自ノードが送信したフレームの情報として、フレームを一意に識別するための識別情報と該フレームの送出先ノードに関する情報とを格納する識別情報管理テーブルと、フレームの最終宛先ノードごとに、フレームを中継するため送出先とする他ノードについての重み付け情報を格納する宛先ノード別重み付けテーブルと、他ノードから自ノードに宛てて送信されたフレームを受信するフレーム受信手段と、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されている場合に、該識別情報と対応付けて格納されている前記送出先ノードについて、該フレームの最終宛先に対応する前記宛先ノード別重み付けテーブルのデータを更新する宛先ノード別重み付けテーブル更新手段と、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されていない場合に、前記フレームの最終宛先ノードに該当する前記宛先ノード別重み付けテーブルを参照して、該フレームを中継するための送出先とする他ノードを決定するフレーム送出先決定手段とを備える。
【００１７】
他ノードからフレームを受信すると、宛先ノード別重み付けテーブルを参照し、転送すべきノードを決定する。転送先のノードを重みにしたがって決定し、また、他ノードへのフレームの転送の成否に応じて重みが更新される。ノード装置は、自律的に経路を学習できる。
【００１８】
前記宛先ノード別重み付けテーブル更新手段は、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されている場合に、該識別情報と対応付けて格納されている前記送出先ノードについて、該フレームの最終宛先に対応する前記宛先ノード別重み付けテーブルの該送出先ノードに対する重み付けを、優先度が低くなるように更新するようにしてもよい。
【００１９】
更には、自ノードの周囲に存在する他ノードに関する情報を格納する隣接ノード管理テ
ーブルと、ハローメッセージとして、自ノードの存在を知らせる情報と、前記隣接ノード管理テーブルから読み出した情報であって、周囲の経路に関する情報とを送信するハローメッセージ送信手段と、他ノードからの送信されたハローメッセージを受信するハローメッセージ受信手段と、前記ハローメッセージ受信手段により受信したハローメッセージの送出元ノードに関する情報に基づき、前記隣接ノード管理テーブルを更新する隣接ノード管理テーブル更新手段と、を更に備え、前記隣接ノード管理テーブルにおいて、所定の状態になった第１のノードを検出した場合には、前記宛先ノード別重み付けテーブル更新手段は、前記宛先ノード別重み付けテーブルの送出先ノードが該第１のノードであるデータを優先度が低くなるように更新するようにしてもよい。
【発明の効果】
【００２０】
本発明の実施形態にかかるノード装置によれば、ノード装置間のリンクが変化するようなネットワークにおいても、各ノード装置は、保有する重みに関する情報を参照して転送先のノードを決定し、重みに関する情報を更新する。これにより、ネットワークの全体を把握せずとも、自律的に最適な経路を学習して通信を行うことが可能となる。
【図面の簡単な説明】
【００２１】
【図１】通信システムの全体概念図である。
【図２】本発明の実施形態に係るノード装置の概略図である。
【図３】本発明の実施形態に係るノード装置の詳細な模式図である。
【図４】隣接ノード管理テーブルの構造を示す図である。
【図５】フレームのフォーマット例である。
【図６】図５のフレームのフォーマット例の説明である。
【図７】隣接ノード管理テーブルに基づくデータ転送処理を説明する図である。
【図８】フレームの転送結果により重みに関する情報を操作する処理を説明する図である。
【図９】ＦＩＤ管理テーブルの例を示す図である。
【図１０】本発明の実施形態に係るノード装置のデータフレーム受信時の処理を示したフローチャートの概略（その１）である。
【図１１】本発明の実施形態に係るノード装置のデータフレーム受信時の処理を示したフローチャートの概略（その２）である。
【図１２】ハローヘッダのフォーマットを示す図である。
【図１３】本発明の実施形態に係るノード装置において、遅延により通信品質を計測する方法を説明する図である。
【図１４】ハローヘッダを含んだハローフレームの詳細なフォーマットを示す図である。
【図１５】重み付けテーブルの構造を詳細に説明する図である。
【図１６】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その１）である。
【図１７】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その２）である。
【図１８】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その３）である。
【図１９】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その４）である。
【図２０】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その５）である。
【図２１】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その６）である。
【図２２】ハローフレームの交換シーケンスを示す図である。
【図２３】本発明の実施形態にかかるノード装置もしくはプログラムを実施可能なハードウェアを示す概要図である。
【発明を実施するための形態】
【００２２】
以下、本発明の好適な実施の形態について、図面を参照して詳細に説明する。
まず、本明細書での用語について説明をする。
【００２３】
「フレーム」とは、プロトコルが扱うデータ単位のことを指す。「フレーム」には、例えば「ハローフレーム」「データフレーム」が含まれるが、これらに限定はされない。
【００２４】
「ハローフレーム（HELLOフレーム）」とは、本発明の実施形態にかかるノード装置が
、別のノード装置に対して互いの存在・状態の確認のために送出する特別なフレームのことを指す。
【００２５】
「データフレーム」とは、ネットワークが（スタートノードからゴールノードへと）伝送しようとするデータのことを指す。なお当然のことながら本発明の実施形態にかかるノード装置は、「ハローフレーム」と「データフレーム」を識別するための適切な手段を有することができる。
【００２６】
「Local Destination (LD)」とは、或るノード装置を主体として観たときに、次にフレームを渡すべき隣接ノード装置を表すあて先ノードIDのことを指す。なお本明細書ではLDのことを、「ローカル宛先アドレス」と称することもある。
【００２７】
「Local Source (LS)」とは、LDへフレームを送るその直接の送り元となるノード装置
（すなわち、LDにとっての自ノード装置）を表したノードIDのことを指す。なお本明細書ではLSのことを、「ローカル差出アドレス」と称することもある。
【００２８】
「Global Destination (GD)」とは、データフレームのネットワークに跨った一連の伝
播に関する最終的なあて先となるノードIDのことを指す。なお本明細書ではGDのことを、「グローバル宛先アドレス」と称することもある。
【００２９】
「Global Source (GS)」とは、データフレームのネットワークに跨った一連の伝播に関する最初の送り元であるノードIDのことを指す。なお本明細書ではGSのことを、「グローバル差出アドレス」と称することもある。
【００３０】
「フレームID (FID)」とは、各フレームが持つ固有の識別情報のことである。FIDとし
ては例えば一連の番号を用いることができるが、これに限定はされない。
【００３１】
「重み」とは、本発明の実施形態にかかるフレーム伝播経路選択にあたって考慮される値である。重みとしては、復路リンク重み、往路リンク重み、双方向リンク重み、経路品質重み、復路品質重み、リンク間到達重み、が本明細書に例示されているが、これらに限定はされない。なお本明細書の記載において「重み」または「重みに関する情報」と言うときには、何らかの種類の重みを用いて算定した値のことを指すこともあると解釈されたい。
【００３２】
「復路リンク重み」とは、復路を来たるフレームに関する重みのことである。なお、或るノード装置を主体として考えるとき、そのノード装置が別の隣接するノード装置からフレームを受けるとするなら、そのフレームは「復路」を通ってきたことになる。
【００３３】
「往路リンク重み」とは、往路を行くフレームに関する重みのことである。なお、或る
ノード装置を主体として考えるとき、そのノード装置が別の隣接するノード装置へフレームを送るとするなら、そのフレームは「往路」を通ることになる。
【００３４】
「双方向リンク重み」とは、上述した往路リンク重みと復路リンク重みとを組み合わせて算出する重みのことである。本発明の実施形態では、「復路リンク重み」「往路リンク重み」「双方向リンク重み」は、後に詳述する隣接ノード管理テーブルが含むことができるデータである。しかし他の実施形態では、これ以外の組み合わせを含むようにしてもかまわない。
【００３５】
「経路品質重み」とは、GDまでの経路上での遅延を数値化したものを指す。
「復路品質重み」とは、相手となるノード装置から自ノード装置へ至る方向への通信品質を数値化したものを指す。
【００３６】
「リンク間到達重み」とは、フレームのリンク間での転送の成否を数値化した値である。本発明の実施形態では、「経路品質重み」「復路品質重み」「リンク間到達重み」は、後に詳述する重み付けテーブルが含むことができるデータである。しかし他の実施形態では、これ以外の組み合わせを含むようにしてもかまわない。
【００３７】
図１は、通信システムの全体概念図である。図１に示すように、ネットワークにはノード装置（ａ、ｂ、…、ｓ、ｔ）が互いに接続されて含まれている
。本通信システムにおいては、スタートノード（図１の例ではノード装置ｂ）からゴールノード（図１の例ではノード装置ｔ）へと情報を伝達するにあたり、各ノード装置が中継器として動作する。
【００３８】
各ノード装置は、それぞれ固有の識別情報（ＩＤ、Identification）を保有する。各ノード装置に割り当てられたＩＤを、以下ノードＩＤとする。各ノード装置は、互いに隣接しているノード装置やネットワーク全体については把握していない。初期状態においては、互いのリンクは存在しておらず、各ノード装置は、自身以外のノード装置についてはその存在・状態を把握していない。
【００３９】
そこで、図１に示す通信システムにおいてスタートノード{b}からゴールノード{t}へと情報を伝達するには、まず、ネットワークを構築する必要がある。ネットワークを構築する手順は、以下のとおりである。
【００４０】
まず行われるのは、周囲のノード装置の検出である。或るノード装置は、自身の存在を近隣に存在するノード装置へ周期的に通知する。近隣ノード装置への通知には、経路作成に関連した情報が付随されている。各ノード装置は、通知を受信すると、周囲のノード装置についてのリストを作成して、自装置の周囲のノード装置の存在を把握することができる。
【００４１】
周囲のノード装置を検出したノード装置は、作成したリストに基づいて、自身が情報を転送する相手となるべきノード装置を決定して、そのノード装置に情報を転送する。
【００４２】
或るノード装置が、情報を転送すべきノード装置を決定するにあたって、周囲に存在する複数のノード装置のうちいずれのノード装置に情報を託せば、目的とするゴールノードに情報を到達させられるかについては、この時点では未だこのノード装置は識らない。そこで、本実施形態に係るノード装置では、周囲のノード装置のいずれに優先的に情報を転送すべきかを示す重み付けテーブルを作成し、重み付けテーブルに格納されている重みに関する情報にしたがって、情報の転送の対象となるべきノード装置を決定する。
【００４３】
以下、本実施形態に係るノード装置について、具体的に説明する。
図２は、本実施形態に係るノード装置の概略図である。図２におおまかな概要を示すノード装置１は、フレーム処理部２、リンク管理部３、ルーティング決定部４、ＦＩＤ（フレームＩＤ）管理テーブル５、隣接ノード管理テーブル６、及び重み付けテーブル７を有する。図２には明示されていないが、当該技術分野において既知である何らかの種類の記憶装置（例えば、DRAMもしくはフラッシュメモリ）が、ＦＩＤ（フレームＩＤ）管理テーブル５、隣接ノード管理テーブル６、及び重み付けテーブル７をデータテーブルとして格納できる。
【００４４】
フレーム処理部２は、ノード装置１に隣接するノード装置との間で交換されるデータフレームの処理を行う。フレーム処理部２はまた、データフレームを受信した場合に、記憶装置（図２には示されていない）にアクセスしてＦＩＤ管理テーブル５（請求項の識別情報管理テーブルに相当）を用い、ループの発生の検出も行う。
【００４５】
リンク管理部３は、記憶装置（図２には示されていない）にアクセスして隣接ノード管理テーブル６を用い、隣接するノード装置の死活及びリンク強度を管理する。
【００４６】
ルーティング決定部４は、記憶装置（図２には示されていない）にアクセスして重み付けテーブル７（請求項の宛先ノード別重み付けテーブルに相当）を参照し、フレームを次にどの隣接ノード装置に転送すべきかを決定する。重み付けテーブル７は、フレームの最終的な宛先（すなわち、Global Destination (GD)）ごとに作成される。
【００４７】
なお、図１に示すネットワークを構築する複数のノード装置の各々は、それぞれが図２に示すような構造をとるが、以下の説明においては、他のノード装置と区別して、自ノード装置について符号「１」もしくは「１ａ」を付して説明している。また、各ノード装置は、無線によって接続されていてもよいし、有線によって接続されていても構わない。所望であれば、無線と有線が混在したネットワークに本発明の実施形態にかかる装置もしくはプログラムを適用できることも、本発明の実施形態では想定されている。
【００４８】
図３は、実施形態に係るノード装置をさらに説明するための、より詳細な模式図である。なお、参照番号についた接尾辞"a"は、同番号の構成要素（element）と同様であるかもしくは類似した構成要素を指していることに留意されたい。なお本明細書では、例えば或る装置ＸＸＸと装置ＸＸＸａがともに実施形態に包摂されうる。また、参照番号の接尾辞を省略して、接尾辞が無いものと有るものとを包括する概念を指すこともある。例えば、装置ＸＸＸと表記したとき、矛盾が生じないかぎりは、装置ＸＸＸａのことも含んでいると解釈される。
【００４９】
図３のノード装置１ａは、フレーム処理部２ａ、リンク管理部３ａ、ルーティング決定部４ａ、ＦＩＤ管理テーブル５ａ、隣接ノード管理テーブル６ａ、重み付けテーブル７ａ、受信部１０、送信部２０を有する。なお、ＦＩＤ管理テーブル５ａ、隣接ノード管理テーブル６ａ、及び重み付けテーブル７ａは、任意の適切な記憶装置に格納できる。そしてその記憶装置をノード装置１ａの内部に収めることもできるし、外部に設置することも可能である。また、そうした記憶装置は、各ノード装置ごとに単一のものであってもよいし、複数存在してもよい。
【００５０】
上述したLSに対応するノード装置１ａが、受信部１０にてフレーム（データフレームおよびハローフレームを含む）を受信すると、フレーム分岐処理部１２がフレームの種別を識別して、その種別に応じて処理を分岐させる。詳しくは後述するが、フレーム分岐処理部１２は、フレームに付されたそのフレームの種別を表すための識別子を用いることができる。
【００５１】
受信されたフレームがハローフレームであった場合には、フレーム分岐処理部１２が、フレームをリンク管理部３ａに渡す。リンク管理部３ａは、隣接ノード管理テーブル６ａを格納した記憶装置にアクセスし、隣接するノード装置の死活及びリンク強度を管理する。そしてリンク管理部３ａは、ループが検出された場合には、重み付けテーブル７ａを格納した記憶装置にアクセスし、重みに関する情報の登録または更新を行う（詳しくは後述する）。
【００５２】
受信されたフレームがデータフレームであった場合には、フレーム分岐処理部１２が、フレームをフレーム処理部２ａに渡す。フレーム処理部２ａは、FID管理テーブル５ａを
格納した記憶装置にアクセスし、FID、LD、およびGSに関する情報を管理する。そしてフ
レーム処理部２ａはフレームをルーティング決定部４ａに渡す。また、フレーム処理部２ａは、ループが検出された場合には、重み付けテーブル７ａを格納した記憶装置にアクセスし、重みに関する情報の登録または更新を行う（詳しくは後述する）。
【００５３】
ルーティング決定部４ａは、重み付けテーブル７ａを格納した記憶装置にアクセスして重みに関する情報を得たうえで、フレームをどのノード装置へ送信するかを決定する。そして、送信部２０にフレームを渡す。
【００５４】
送信部２０は、ルーティング決定部４ａから受けとったフレームを他のノード装置へ送信するにあたり、送信処理部２２にFID管理テーブル５ａを格納した記憶装置にアクセス
させて、FIDとLDおよびGSに関する情報を登録・更新する。
【００５５】
本発明の実施形態では、上述したように、隣接ノード装置管理テーブル、FID（フレー
ムID）管理テーブル、重み付けテーブルといったテーブルを使用する。まず、隣接ノード装置管理テーブルについての説明を行う。
【００５６】
図４は、隣接ノード管理テーブル６もしくは６ａの構造を示す図である。隣接ノード管理テーブル６もしくは６ａは、ノードＩＤ、最終更新時間及びリンク強度を含む。
【００５７】
ノードＩＤは、ネットワークを構築するノード装置を識別するために各ノード装置に割り当てられた識別情報である。
【００５８】
最終更新時間は、各ノードＩＤが示すノード装置について、最後に情報が更新された日時情報である。具体的には例えば、最終更新時間としてリンク強度が更新された日時情報を格納できる。
【００５９】
リンク強度は、ノード装置１もしくは１ａが、隣接するノード装置から受信したハローフレームに含まれるリンク強度に基づき算出され、適切な記憶装置に格納される。リンク強度は例えば、電波強度やフレーム到達率を用いて算出できる。リンク強度は例えば、双方向リンク重みに対応している。
【００６０】
上記のとおり、まず、事前にネットワークを構築するために、隣接ノード間で通知用のフレーム（ハローフレーム）が交換される。そして、図２に示す隣接ノード管理テーブル６もしくは図３に示す隣接ノード管理テーブル６ａ、ならびに図２に示す重み付けテーブル７もしくは図３に示す重み付けテーブル７aが、各ノード装置において作成される。図
１の説明においても述べたとおり、本実施形態に係るノード装置１においては、ネットワークトポロジーを把握する必要はない。
【００６１】
隣接ノード管理テーブル６もしくは６ａが作成されると、隣接ノード管理テーブル６も
しくは６ａに対応する情報が格納されている隣接ノードのうち、フレームを転送すべきノード装置を決定する。フレームを転送すべきノード装置を決定するときに参照される重み付けテーブル７は、フレームを隣接ノード装置から受信したあとの処理にて更新される。
【００６２】
図５および図６は、フレームのフォーマット例である。図５に示すフレームは、隣接ノードの宛先ノード（Local Destination）についてのノードＩＤ（ＬＤ）、隣接ノードの
送信元ノード（Local Source）についてのノードＩＤ（ＬＳ）、宛先ノード（Global Destination）についてのノードＩＤ（ＧＤ）、送信元ノード（Global Source）についての
ノードＩＤ（ＧＳ）、フレームＩＤ（ＦＩＤ）、フレームタイプ（ＴＹＰＥ）、データ長（ＤＡＴＡＬＥＮ）、及びデータ本体（ＤＡＴＡ）を含む。
【００６３】
ＬＤには、ノード装置１の隣接ノードのうち、フレームを転送する宛先ノードのノードＩＤが格納される。
【００６４】
ＬＳには、LDとなる隣接ノード装置へフレームを転送する送信元のノード装置のノードＩＤが格納される。例えば、LDがノード装置１に隣接するノード装置のいずれかのノードIDであったならば、LSはそのノード装置１のノードIDとなる。
【００６５】
ＧＤには、フレームの本来の宛先のノードＩＤが格納され、ＧＳには、フレームの本来の送信元のノードＩＤが格納される。
【００６６】
フレームＩＤは、フレームを識別するための識別情報が格納される。
フレームタイプには、そのフレームの種類を示す情報が格納される。フレームの種類としては、例えば、データフレームや、ハローフレーム等があるが、これらに限定はされない。
【００６７】
データ長には、データ本体の長さ（データ長、またはフレームサイズとも称する）が格納される。
【００６８】
データ本体には、ネットワークを伝播する対象であるデータが格納される。
なおここに示したフォーマットはあくまで一例であることに留意されたい。本発明の別の実施形態では、これとは異なったフォーマットを使用することもでき、かつその別の実施形態は本発明の範囲に包摂されうる。
【００６９】
図７は、或る実施形態にかかる、隣接ノード管理テーブル６もしくは６ａに基づくフレーム転送処理を説明する図である。このうち、図７（ａ）は、隣接ノード装置ごとの重みの概要を示す図であり、図７（ｂ）は、隣接ノード管理テーブル６もしくは６ａの簡単な例を示す図である。
【００７０】
この実施形態に係るノード１もしくは１ａは、隣接するノード装置のうちいずれかからフレームを受信すると、フレームの送信元すなわちＬＳであるノード装置以外のうち、重みに関する情報に鑑みてより優先度の高いノード装置に、そのフレームを転送する。ノード装置１もしくは１ａは、隣接ノード装置のそれぞれに対してリンク番号を付しており、これによって各隣接ノード装置を識別している。
【００７１】
なお、この実施形態においては、重みに関する情報（例えば、双方向リンク重みなど）として用いる値を、0以上1以下の範囲として設定してある。この値が小さいほど、優先度が高いものとして扱う。重みに関する情報初期値として例えば0.5を設定しておき、その
後のフレーム転送の成否やループの検出の有無等に応じて変更してゆくことができる。
【００７２】
重みに関する情報の設定及び更新は、後述する重み操作関数（例えば、リンク強度を考慮した関数）により行う。重み操作関数は、ネットワーク全体の振る舞いに影響するため、ネットワークの用途に応じて変更する必要があるだろう。
【００７３】
図７（ａ）においては、リンク番号ｉの隣接ノード装置からフレームを受信した場合の、重みに関する情報による転送先ノード装置の決定方法を示している。
【００７４】
リンク番号ｉの隣接ノード装置から転送されたフレームを受信すると、ノード装置１もしくは１ａは、保有する隣接ノード管理テーブル６もしくは６ａのうち、GDのノード装置に対応する重み付けテーブルを参照する。そして、重みに関する情報を踏まえて最も優先度が高く、リンク番号が「ｉ」以外である隣接ノード装置に対して、受信したフレームが転送されることになる。
【００７５】
図７（ｂ）に示すように、隣接ノード管理テーブル６もしくは６ａでは、隣接ノード装置ごとに割り当てられるリンク番号と、リンク番号に対応付けた隣接ノード装置の重みを格納する。なお、リンク番号は、ノードＩＤで代用することも可能である。ノード装置１もしくは１ａは、リンク番号ｉの隣接ノード装置から受信したフレームにしたがって、隣接ノード管理テーブル６もしくは６ａを更新し、重みに関する情報を操作する。
【００７６】
図８は、データの転送結果により重みを操作する処理を説明する図である。
図８に示す例では、重みに関する情報として、隣接ノード装置Ａ、Ｂ、Ｃ、Ｄに対しそれぞれ、リンク番号1, 2, 3, 4 および重み w1, w2, w3, w4 を設定してある。
【００７７】
なお、例えばノード装置間の通信が無線である場合には、通信時における環境やノード装置間の距離等が通信品質に影響することがあり、ノード装置間の通信が有線である場合には、例えばトラフィック量が通信品質に影響することがある。その影響を考慮し、ここでは重みの初期値を０．５とし、かつその値の範囲を０以上１以下としているが、これはあくまで一例であって、それ以外の値をとりうる重みを用いる実施形態が想定できる。また、この実施形態においては、重みが小さい（0に近い）ほど優先度が高いとしているが
、これもまた一例である。それ以外の優先度の定めかた（例えば、重みが大きいほど優先度が高いような定めかた）をした実施形態もまた想定されている。
【００７８】
また、重み付けテーブルには、フレームを転送する際に優先的に転送すべき隣接ノード装置と、それ以外のノード装置とを示す情報を格納してもよい。例えば、フラグ等を用意しておき、フレームの転送の成否に応じて値を重み付けテーブルに設定することも可能である。
【００７９】
ノード装置１もしくは１ａは、これまで隣接ノード装置にフレームを転送した結果に応じて重みに関する情報（例えば双方向リンク重み）を操作する。まず、各重みの大小関係が、ｗ１＜ｗ２＜ｗ３＜ｗ４であるとする。すなわち、隣接ノード装置Ａについての優先度が最も高く、隣接ノード装置Ｄについての優先度が最も低いと仮定する。
【００８０】
このような場合にノード装置１もしくは１ａがフレームを隣接ノード装置Ａ〜Ｄ以外の隣接ノード装置ｉから受信すると、ノード装置１もしくは１ａは、最も優先度の高い隣接ノード装置Ａから順にフレームを転送しようとする。隣接ノード装置Ａへのデータ転送に失敗すると、次に優先度の高いノード装置Ｂにデータを転送する。
【００８１】
最終的に、隣接ノード装置Ａ及びＢのいずれについてもデータ転送が失敗し、隣接ノード装置Ｃについてはデータ転送が成功したとすると、ノード装置１もしくは１ａは、隣接ノード装置Ａ、Ｂについては重みを最大（最悪値）にして、優先度を最低に設定する。そ
して、隣接ノード装置Ｃについての重みが減らされ、優先度が高く設定されることになる。
【００８２】
次回以降のデータフレーム転送においては、このようにして更新された重みの関係（ｗ３＜ｗ４＜ｗ１＝ｗ２）に基づいて、フレームの転送先（ＬＤ）を決定し、最も優先度の高い隣接ノード装置Ｃからフレームの転送を試みることとなる。
【００８３】
次に、ループの発生を検出する方法について説明する。
図９は、ＦＩＤ管理テーブル５もしくは５ａの構成の一例を示す図である。図９に示した実施形態においては、ＦＩＤ管理テーブル５もしくは５ａは例えば、ＦＩＦＯ（First In First Out）型バッファである。ＦＩＤ管理テーブル５もしくは５ａには、フレームＩＤ（ＦＩＤ）、送信元ノードＧＳのノードＩＤ、転送先ノードＬＤのノードＩＤ、及び送信元ノードＬＳのノードＩＤが含まれる。ＦＩＤ、ＧＳ／ＬＤ／ＬＳのノードＩＤの定義については、図６に示すデータフレームのそれぞれ対応するフィールドと同様である。
【００８４】
ノード装置１もしくは１ａは、隣接ノード装置からフレームを受信すると、フレームのＦＩＤ及びＧＳのフィールドの値と、ＦＩＤ管理テーブル５もしくは５ａに格納されているレコードとを比較する。比較した結果、受信したフレームと同じＦＩＤ及びＧＳを有するレコードがＦＩＤ管理テーブル５に格納されていた場合は、ノード装置１もしくは１ａは、そのフレームが過去に一度受信したフレームと同一のフレームであると判断して、「ループが発生した」か、「途中の経路の遮断により戻りが発生した」と見做す。ループまたは戻りの発生が検出された場合には、重み付けテーブル７もしくは７ａを更新し、そのフレームのＬＳのノードＩＤに対応する重みに関する情報に、最悪値（この実施形態では最大の値）を設定する。
【００８５】
一方、同一のＦＩＤ及びＧＳを有するレコードが存在しなかった場合には、ノード装置１もしくは１ａが、受信したフレームからＦＩＤ、ＧＳ、ＬＤ、及びＬＳの各フィールドから値を取り出して、ＦＩＤ管理テーブル５に１レコード登録する。
【００８６】
つづいて、ノード装置がデータフレームを受信した際に行う処理に関し、よりいっそう詳しく説明を行ってゆく。
【００８７】
図１０及び図１１は、或る実施形態に係るノード装置１もしくは１ａのデータフレーム受信時の処理を示したフローチャートである。
【００８８】
まず、ステップＳ１で、初期化処理を実行する。ステップＳ１の初期化処理においては、例えば、無線で隣接ノード装置と通信を行う場合には、使用周波数を合わせる処理や、変調方式を決定する処理等を実行する。なお、ステップＳ１の初期化処理は、ノード装置１もしくは１ａをネットワークに設置したときにのみ実行される。
【００８９】
ステップＳ２では、データフレームの受信を待機する。ステップＳ２で、データフレームを受信すると、ステップＳ３に進み、ＬＤのフィールドに格納されているノードＩＤが自装置のノードＩＤであるか否かを判定する。LDに自装置以外のノードＩＤが格納されていた場合には、ステップＳ２に戻って待機を続ける。
【００９０】
また、ステップＳ１の処理とステップＳ２の処理との間には、上記のとおり、ハローフレームによるネットワーク構築処理も行われているが、ハローフレームの送受信については図１０及び図１１に示す処理とは異なるスレッドによって実行されるため、ここでは説明を省略する。
【００９１】
ステップＳ３で、ＬＤのフィールドに自装置のノードＩＤが格納されていると判定されると、ステップＳ４に進む。
【００９２】
ステップＳ４では、ＧＤのフィールドに格納されているノードＩＤは、自装置のノードＩＤであるか否かを判定する。ステップＳ４において、ＧＤのフィールドに、自装置のノードＩＤが格納されていると判定された場合は、つまりネットワークに跨る一連のデータ伝播の終着点が自ノード装置であったということである。したがってフローはステップＳ１０に進み、受信したデータフレームを（上位層で）処理し、一連の処理を終了する。
【００９３】
ステップＳ４において、ＧＤのフィールドに格納されているノードＩＤが、自装置以外のノードＩＤであると判定されると、フローはステップＳ５に進む。そして、ステップＳ５で、ＦＩＤ管理テーブル５に、受信したデータフレームのＦＩＤ及びＧＳとそれぞれ一致するＦＩＤ及びＧＳの組み合わせを有するレコードが、存在するか否かを判定する。
【００９４】
ステップＳ５において、ＦＩＤ管理テーブル５にデータフレームのＦＩＤ及びＧＳと一致するレコードが存在したと判定されると、フローはステップＳ６に進む。ステップＳ６では、ＦＩＤ管理テーブル５のうち、ＦＩＤ及びＧＳがいずれもデータフレームのＦＩＤ及びＧＳと一致すると判定されたレコードから、ＬＤを取り出す。そして、ステップＳ７で、データフレームのＧＤに対応する重み付けテーブル７もしくは７ａについて、ステップＳ６において取り出したＬＤと一致するノードＩＤを有するレコードについて更新を行う。例えばこの実施形態では、項LastとしてFID管理テーブルで最後にFIDを持つフレームを送出したノードIDを設定している。そしてこの項Lastに対応する重みに関する情報が、優先度がもっとも低い最悪値（例えば1.0）となるように変更できる。重み付けテーブル
７もしくは７ａを更新すると、図１１の記号（Ａ）に進む。
【００９５】
一方、ステップＳ５において、ＦＩＤ管理テーブル５に一致するＦＩＤ及びＧＳは存在しないと判定されると、フローはステップＳ８に進む。ステップＳ８では、データフレームのＧＤに対応する重み付けテーブル７もしくは７ａが存在するか否かを判定する。
【００９６】
ステップＳ８において、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａが存在しないと判定されると、フローはステップＳ９に進む。そして、ステップＳ９では、データフレームのＧＤについての重み付けテーブル７もしくは７ａを作成し、その後フローは図１１の記号（Ａ）に進む。
【００９７】
なお他の実施形態においては、ステップＳ９にて、例えば、図５に示す隣接ノード管理テーブル６もしくは６ａのリンク強度を参照して重み付けテーブルを作成してもよい。
【００９８】
ステップＳ８において、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａが存在すると判定された場合には、特に処理を行わず、図１１の記号（Ａ）に進む。
【００９９】
図１１に示す処理においては、まず記号（Ａ）からステップＳ１１に進み、重み付けテーブル７もしくは７ａから最も優先度の高い評価値に対応するノードＩＤを取得する。そしてステップＳ１２で、取得したノードＩＤに対応する適切なノード装置を発見することができるか否かを判定する。
【０１００】
ステップＳ１２において、適切なノード装置を発見することができたと判定された場合には、フローはステップＳ１３に進み、ステップＳ１１で取得したノードＩＤに対してデータフレームを転送する。
【０１０１】
そして、ステップＳ１４では、転送したデータフレームに含まれるデータに基づき、ＦＩＤ管理テーブル５にフレームのＦＩＤ及びＧＳと、ＬＤと、ＬＳとを追加する。
【０１０２】
つづいてステップＳ１５で、データフレームの転送が成功したか否かを転送先ノード装置からの応答により判断する。例えば、転送先ノード装置からａｃｋ信号を受信した場合には転送が成功したと判定し、所定時間経過してもａｃｋ信号を受信しなかった場合には失敗したと判定するようにできる。成功したと判定された場合には、ステップＳ１６で、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａについて、転送先のノード装置についてのノードＩＤに対応する評価値を操作しての優先度を上げ、図１０の記号（Ｂ）に戻る。
【０１０３】
一方、ステップＳ１５において、データフレームの転送が失敗したと判定された場合には、ステップＳ１７で、転送先のノード装置についてのノードＩＤに対応する評価値を操作して優先度を下げ、ステップＳ１１に戻る。
【０１０４】
以降は、データフレームの転送が成功するか、重み付けテーブルに適切なノードＩＤが存在しなくなるまで、ステップＳ１１以降の処理を繰り返す。
【０１０５】
ステップＳ１２において、重み付けテーブル７もしくは７ａから適切なノード装置（ノードＩＤ）が発見できないと判定された場合には、ステップＳ１８に進み、受信したデータフレームをＬＳが示すノード装置に転送し、図１０の記号（Ｂ）に戻る。
【０１０６】
以上説明したように、本実施形態に係るノード装置１もしくは１ａによれば、データフレームを転送するときに、保有する重み付けテーブル７もしくは７ａを参照して優先的にデータ転送すべきノード装置を判断し、データ転送の成否により重みに関する情報（例えば評価値）を更新する。重みに関する情報にしたがって優先的にフレームを転送すべきノード装置を判断することで、ループの発生にともなうデータフレームの戻りや、ネットワークの状態の変化によりそれまで通信可能であった経路が遮断された際のデータフレームの戻りを検出し、そのことを踏まえて経路を迂回して最適な経路で通信を継続することが可能となる。なお上述したように、重み付けテーブル７もしくは７ａはGDごとに作成されうるものであるが、ここではあくまで一例として、わかりやすくするためにひとつの重み付けテーブルだけを考えていることに留意されたい。
【０１０７】
ところで、図１に示す通信システムにおいては、各ノード装置がネットワークの状態を監視している。以下、本実施形態に係るノード装置によるネットワークの監視方法について説明する。
【０１０８】
上記のとおり、各ノード装置は、ハローフレームに他のノード装置から受信した電波の通信品質に関わる情報を含めて送信している。ノード装置は、他のノード装置から受信したハローフレームを参照して、隣接ノード装置の通信品質を算出し、図５に示す隣接ノード管理テーブル６もしくは６ａに算出した通信品質に関わる情報を保持する。或る実施形態においては、遅延及びホップ数により通信品質を決定する。
【０１０９】
図１２は、ハローフレームのうちの所定の領域に格納されるハローヘッダのフォーマットを示す図である。図１２に示すように、ハローヘッダは、グローバル宛先アドレス（すなわちGD）、ホップ数ｈ、経路品質重みｄ、復路品質重み、及びノードタイプを含む。
【０１１０】
グローバル宛先アドレス（GD）は例えば、図１２に示すハローヘッダを含むハローフレームの最初の送信元（GS）であるノード装置が持つ、重み付けテーブル７に対応するグローバル宛先アドレス（GD）の情報である。
【０１１１】
ホップ数hは例えば、このハローフレームの送信元から最終目的地（GD）であるノード
装置までのホップ数の情報である。
【０１１２】
経路品質重みｄは、GDまでの経路上での遅延から求めた値が格納される。
復路品質重みは、相手のノード装置（ここでは、ハローフレームを送信したノード装置）から自ノード装置へ至る方向の通信品質に基づいて求めた値が格納される。
【０１１３】
ノードタイプには、ゲートウェイ、中継器、及び端末等の種類が定義される。
ハローヘッダに格納される情報のうち、経路品質重みｄを求める方法について、図１３を参照してさらに具体的に説明してゆく。
【０１１４】
図１３は、本実施形態に係るノード装置１もしくは１ａにおいて、遅延により通信品質を計測する方法を説明する概念図である。「発生元」のノード装置は、定期的にハローフレームを外部に向けて送出している。図１３中に楕円形に示している網掛け部は、発生元ノード装置が送信するハローフレームを受信可能な範囲を示している。ノード装置ａ及びｂは、発生元のノード装置から順次送出されるハローフレームを受信し、１つのフレームを受信してから次のフレームを受信するまでに要する時間を計測する。以下、次のフレームを受信するまでに要する時間を、「受信周期」とも称する。
【０１１５】
図１３において、ノード装置ａ及びｂにおける受信周期と受信回数との関係を図中のグラフ（縦軸は出現回数、横軸は受信間隔）に示す。図示するとおり、各ノード装置における受信周期と受信回数との関係は、一般的に、正規分布となる。
【０１１６】
そして、一般的に、発生元のノード装置からの距離が比較的遠いノード装置ｂでは、フレームロスが発生しやすくなる。従って、ノード装置ｂでは、ノード装置ａよりもフレームロスによるフレームの受信抜けが発生しやすくなり、次のフレームを受信するまでの時間が長くなる傾向にある。このことから、本発明にかかる或る実施形態においては、受信周期Ｔが大きいことを、遅延が大きいことであると見做すような近似を行って、受信周期Ｔにより通信品質を求めている。
【０１１７】
受信周期により通信品質を求めるやりかたを説明する。まず、ある時刻ｔにハローフレームを受信し、次に時刻がｔ＋ｔ１にハローフレームを受信したとする。この場合、受信周期Ｔ＝ｔ１である。所定の期間に観測された受信周期の集合をＴ｛ｔ１、ｔ２、…、ｔｎ｜ｎ∈Ｎ｝（ｔｉ（ｉ＝１、２、…、ｎ）は各時点での観測値）とする。この場合の観測された受信周期に基づく標準偏差ｌは、以下の式（１）で表される。なお、式中の
【０１１８】
【数１】
【０１１９】
は、受信周期の観測値の平均値である。
【０１２０】
【数２】
（１）
【０１２１】
上記（１）式により得られる標準偏差を、復路リンク重みとして、隣接ノード管理テーブル６もしくは６ａの所定のフィールド（不図示）に格納する。なお、（１）式で求めた復路リンク重みを、ハローフレームに格納して相手のノード装置に送信すると、相手のノード装置は、受信した情報から往路リンク重みを得られる。このように、互いに相手のノード装置から受信したハローフレームにより自装置内で復路リンク重みを求め、求めた復路リンク重みを今度はハローフレームに含めて相手のノード装置と交換することで、往路リンク重みを得られるのである。
【０１２２】
取得した往路リンク重み及び復路リンク重みから、双方向リンク重みを算出するにあたっては、当該技術分野において適切とされるさまざまな手法を使用可能である。その一例として、双方向リンク重みは、以下の式（２）で算出可能である。
【０１２３】
(双方向リンク重み) = [{(往路リンク重み)+1}{(復路リンク重み)+1}-1]1/2 （２）
【０１２４】
図１４は、本発明の或る実施形態がアドホックネットワークにおいて使用可能な、ハローヘッダを含んだハローフレームの詳細なフォーマットを詳細に説明するための図である。なお、本発明の別の実施形態では、これとは異なったフォーマットを使用でき、かつその別の実施形態は本発明の範囲に包摂されうる。
【０１２５】
図１４に示したフレームは、おおまかには、アドホックヘッダと、圧縮ヘッダと、ペイロードとに分けられる。
【０１２６】
この実施形態においては、アドホックヘッダは、"ローカル宛先アドレス"（LD）と、"
ローカル差出アドレス"（LS）と、フレームの種別を表す"フレームタイプ"と、圧縮後の
フレームのサイズを表す"フレームサイズ"というフィールドを有している。
【０１２７】
圧縮ヘッダは、ペイロードの圧縮手法を示す"圧縮タイプ"と、圧縮前のフレームのサイズを表す"フレームサイズ"というフィールドを有している。各ノード装置は、この圧縮タイプを考慮して、適切にペイロードの伸張を行うことができる。
【０１２８】
また、ペイロードには、ハローメッセージヘッダと、一個以上のハローヘッダと、署名を示すハッシュとが圧縮して含まれている。なお、この実施形態にかかるフレームで圧縮を行っているのはフレームのサイズを軽減して通信帯域を節約するという効果を得るためである。当然のことながら、圧縮をせずにデータを有するようなフレームもまた、本発明の他の実施形態に包摂されている。
【０１２９】
ペイロードに含まれるハローメッセージヘッダには、サービスの種別を表す"サービス
タイプ"と、ペイロード内の分割状況を表す"分割情報"と、ペイロードが含むハローヘッ
ダの個数を示す"ハローヘッダ数"と、ノード装置のIDを示す"装置ID"と、暗号化された情報を復号するための"アクセスキー"というフィールドが含まれる。なおこの"装置ID"というフィールドには、図２２に関連して後述するハロー要求の送信元であるノード装置のIDが格納できる。
【０１３０】
そしてペイロードに含まれる一個以上のハローヘッダは、"グローバル差出アドレス"（GS）と、ゲートウェイ（GW）の情報についてのホップ数を表す"GW情報ホップ数"と、前述の"経路品質重み"（d）および"復路品質重み"というフィールドを含んでいる。
【０１３１】
なお以上に述べてきたフィールドの種類および順番はあくまで例に過ぎない。本発明の他の実施形態においては、上述したフィールドとそれ以外の当業者が適切と考える任意の
フィールドとを、任意の適切な順番で各ヘッダ内に配置できる。
【０１３２】
図１５は、重み付けテーブル７もしくは７ａの構造をさらに詳細に説明する図である。図１５に示す重み付けテーブル７もしくは７ａは、グローバル宛先アドレス（GD）、ローカル宛先アドレス（LD）、ホップ数ｈ、リンク間到達重みｗ、経路品質重みｄ、及び評価値Ｅを含む。また図１５には示していないが、重み付けテーブル７もしくは７ａはこの他の情報を含んでもよく、例えば、データを更新した時間情報を示す最終更新時間のデータを含んでもよい。上述したように、こうした重み付けテーブルは、それぞれのノード装置が有するものである。
【０１３３】
グローバル宛先アドレス（GD）には、受信したハローフレーム（ここでは、ノード装置を起動してから、図１６〜図２１に関連させて後述するハローフレーム受信処理が複数回行われたとして、そのいずれかの受信処理において受信したハローフレーム、という意味として解釈されたい）のハローヘッダ内のグローバル宛先アドレス（GD）のフィールドに示されるデータが格納される。
【０１３４】
ローカル宛先アドレス（LD）には、受信したハローフレームに含まれているローカル差出アドレス（LS）に示されるデータが格納される。つまり、このハローフレームを受信したノード装置を主体として考えたとき、受信したハローフレームのLSが、次に別のフレームを送信する際のLD候補となるということである。
【０１３５】
ホップ数ｈは、この重み付けテーブルを有するノード装置からGDまでのホップ数が格納されるデータである。つまり、受信したハローフレームのハローヘッダ内のホップ数に示される値に１を加算した値が格納される。
【０１３６】
ノードタイプは、ノードの種類を定義するデータであって、受信したハローフレームのハローヘッダ内のノードタイプに示されるデータが格納される。
【０１３７】
リンク間到達重みｗは、データフレームのリンク間での転送の成否を数値化したものである。この実施形態では、リンク間到達重みｗとして、受信したハローフレームのハローヘッダ内の復路品質重みに基づいて算出されたデータが格納される。
【０１３８】
経路品質重みｄは、図１２及び図１３を参照して説明したとおり、ハローフレームの受信周期の分散に基づいて算出される値である。
【０１３９】
評価値Ｅは、受信したハローフレームのハローヘッダ内の上記ホップ数ｈ、リンク間到達重みｗ、及び経路品質重みｄを用いて算出した、総合的な経路評価情報が格納される。
【０１４０】
本技術分野では、ホップ数hが増すにつれ指数関数的に通信不安程度が高まる（スルー
プットが低下する）ことが経験的に知られている。これを踏まえて、例えば、評価値Ｅを以下の（３）式で表すことができる。
【０１４１】
Ｅ（ｈ，ｗ，ｄ）＝２（ｈ＋ｗ）＋ｄ （３）
【０１４２】
とはいえ、上述した（３）式を用いること以外にも、適切に評価値Eを導出する手法を
用いてもよく、かつそうした手法は本発明の実施形態群に包摂されうる。本発明の他の実施形態においては、ホップ数h、経路品質重みｄ、リンク間到達重みｗ、受信信号強度、
もしくはその他の当該技術分野にて適切と考えられる任意のパラメータ、のうちの少なくとも一種を使って、適切に評価値Eを導出することができる。例えば、E = d+h+5w+20/r
という式を使って評価値Eを算出してもよい（ここでdは経路品質重み、hはホップ数、wは
リンク間到達重み、rは最新のハローフレームを受信した際の受信信号（電力）強度であ
る）。
【０１４３】
更に、上記リンク間到達重みｗを定義し、データ転送が失敗した場合にはｗ＝ｗ＋１、成功した場合にはｗ＝ｗ−１（例えば、０を最小値とする）とし、ｗを上記（３）式のようにすることで、データ転送時の隣接ノードの微調整を行うことができる。
【０１４４】
このように、本実施形態に係るノード装置１もしくは１ａは、他のノード装置からのハローフレームの受信状況に基づき、ネットワークの状態を監視することができる。
【０１４５】
図１６から図２１は、本発明の実施形態に係るノード装置のハローフレーム受信時の処理を示した詳細なフローチャートである。以下、これらの図にわたってフローを説明してゆく。以下に本発明の実施形態に係るノード装置の処理をおおまかに述べる。
(i) ステップＳ１６００からＳ１６１４にて隣接ノード管理テーブルの更新を行う。
(ii) ステップＳ１７００からＳ１７１０’にて、ハローフレームのハローヘッダを用い
てハローヘッダのGDごとに、自ノード装置の持つ重み付けテーブルに登録しているハローフレームの送信元（LS）の評価値の更新を行う。
(iii) ステップＳ１８５０からＳ１７００’にて、GDがハロー送信元（LS）である自ノード装置の持つ重み付けテーブルの評価値の更新を行う。
(iv) ステップＳ２０００からＳ２０１０’にて、自ノード装置の持つ重み付けテーブル
にハローフレームの送信元（LS）が登録されていない場合に新たに登録し、自ノード装置の持つ重み付けテーブルにハローヘッダのGDが登録されていない場合に新たに登録する。
【０１４６】
この実施形態にかかるフローはまず、図１６にて、視点を置くノード装置（自ノード装置）にハローフレームが受信されたところから始まる。
【０１４７】
ステップＳ１６００からＳ１６１４では、ハロー（HELLO）フレームの送信元（LS）に
対応する隣接ノード管理テーブルのレコードにおける重みに関する情報を更新する。
【０１４８】
ステップＳ１６００では、ハローフレームを受けとったノード装置が、そのノード装置が有する隣接ノード管理テーブル中にハローフレームの送信元（LS）のノード装置に該当するレコードが存在するかどうかを確認するために検索を行う。この検索に際しては、このLSからの前回のハローフレーム受信時刻および今回のハローフレーム受信時刻とを比較する。こうすることで、受信時刻の逆転が起こっていないかを確認してLSの"なりすまし"（つまり、LSを偽って送られているフレーム）が無いかを判断することも可能となる。
【０１４９】
ステップＳ１６０２にて、検索によりハローフレームの送信元（LS）が隣接ノード管理テーブル内に無いことがわかったならば、フローはステップＳ１６０４へ進む。そして、隣接ノード管理テーブルにLSを新規に追加し、復路リンク重みの初期値を設定する。ステップＳ１６０２にて、検索によりハローフレームの送信元（LS）が隣接ノード管理テーブル内に在ることがわかったならば、フローはステップＳ１６０６へ進む。そして、隣接ノード管理テーブル中でのLSに該当するレコードにて、復路リンク重みの値を更新する。
【０１５０】
その後のステップＳ１６０８では、ハローフレーム内のハローヘッダに、自ノード装置の情報（IDなど）が含まれているかという検索を行う。このときに、LSの持つノード間のリンク品質情報（すなわち、LSからの復路リンク重み）を参照する。そしてステップＳ１６１０にて自ノード装置の情報が存在することがわかった場合に、フローはステップＳ１６１２に進み、隣接ノード装置に関する往路リンク重みの計算を行う。
【０１５１】
その後のステップＳ１６１４では、隣接ノード装置に関する双方向リンク重みを算出す
る。そして図１７の記号(I)へ進む。
【０１５２】
図１７のステップＳ１７００では、まず自ノード装置が有する重み付けテーブルのレコード一個ごとについてのくりかえし処理（ループ処理）を開始する。そしてステップＳ１７１０でさらに、ハローフレームに含まれるハローヘッダ一個ごとのくりかえし処理をネストする。
【０１５３】
ステップＳ１７１２では、重み付けテーブルのGDと、ハローフレーム内のハローヘッダのGD（つまり、本来はハローフレームの送信元（LS）が持つ重み付けテーブルに含まれていたもの）が一致するかを判定する。
【０１５４】
ステップＳ１７１４にて重み付けテーブルのGDとハローヘッダのGDとが一致しなかったら、フローは図１７の記号(IV)へ飛び、ステップＳ１７１０’にて1つのくりかえしサイ
クルを了える。ステップＳ１７１４にて重み付けテーブルのGDとハローヘッダのGDとが一致したら、フローはステップＳ１７１６に進む。
【０１５５】
ステップＳ１７１６では、ハローフレームの送信元（LS）に対応する重み付けテーブルに、自ノード装置がフレームを送る宛先となるLD候補が存在するかを検索する。
【０１５６】
ステップＳ１７１８にて、宛先となるLD候補（宛先LD候補）が存在したら、ステップＳ１７２０にて重み付けテーブル中のその宛先LD候補についてのレコードで、ホップ数hを
、ハローヘッダのホップ数+1として更新する。そしてステップＳ１７２２で、このハローフレームに関する経路品質重みdを算出し、宛先LD候補に関する経路品質重みdを更新する。なおここでいうハローフレームに関する経路品質重みdとは例えば、ハローフレームの
送信元から観た経路品質重みと、ハローフレームの受信周期の分散から得られる復路品質重みとから算出される経路全体（もしくは経路全体の少なくとも一部分）での双方向リンク重みを、加算または何らかの演算を施した値が、すなわち経路品質重みとなる。これは要するに、或るノード装置において、受信したハローフレームに関する経路品質重みdを
、重み付けテーブルの経路品質重みdに加えられ、そうして得られた更新された経路品質
重みdが、今度は送信されるハローフレームに収められた経路品質重みとなって、次のノ
ード装置へと送信される、ということである。端的にいえば、ハローヘッダごとの双方向リンク重みの積算が、重み付けテーブルの経路品質重みdとなると考えてもよい。この実
施形態においては、一連のくりかえし処理Ｓ１７１０〜Ｓ１７１０’またはくりかえし処理Ｓ１７００〜Ｓ１７００’のあいだに得られる各々の双方向リンク重みを積算して、くりかえし処理の対象となっていた重み付けテーブルの経路品質重みdを算出できる。さて
それから図１８の記号(II)へフローを進める。
【０１５７】
ステップＳ１８２４では、宛先LD候補に関する受信電力（なお、図１５では受信電力についてのフィールドは示していない）を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１８２６では、このハローフレームに関する評価値Eを上述し
たように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１８２
８にて、宛先LD候補に関するエージングカウンタ（重み付けテーブルの有効期間を設定するための手段）をリセットする。そしてフローはステップＳ１８４０に進み、宛先LD候補を評価値の順にソートして、優先度的に好ましい候補を絞りこむようにできる。そしてステップＳ１７１０’にて1つのくりかえしサイクルが完了する。
【０１５８】
一方、ステップＳ１７１８にて、宛先となるLD候補が存在しなかった場合には、まずそのハローフレームの送信元（LS）を、重み付けテーブルに宛先となるLD候補として新規に登録をし、フローはステップＳ１７３０に進む。ステップＳ１７３０にてその新たな宛先LD候補についてのレコードで、ホップ数hを、ハローヘッダのホップ数+1として更新する
。そしてステップＳ１７３２で、このハローフレームに関する経路品質重みdを算出し、
宛先LD候補に関する経路品質重みdを更新する。それから図１８の記号(III)へフローを進める。ステップＳ１８３４では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１８３６では、このハローフレームに関する評価値Eを上述したように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１８３８にて、宛先LD候補に関するエージングカウンタをリセットする。そしてフローはステップＳ１８４０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７１０’にて1つのくりかえしサイクルが完了する。
【０１５９】
くりかえし処理Ｓ１７１０〜Ｓ１７１０’が一通り完了したところで、フローはステップＳ１８５０へ進む。
【０１６０】
ステップＳ１８５０では、くりかえし処理Ｓ１７１０〜Ｓ１７１０’における処理にてハローヘッダを用いた宛先LD候補の更新があったか、すなわちステップＳ１７１４からＳ１７１６へ一度でも進んだかどうかを確認する。更新があった場合には、フローは図１９の記号(VII)へ飛び、ステップＳ１７００’にて1つのくりかえしサイクルを了える。更新が無かった場合には、フローはステップＳ１８５２へ進む。ステップＳ１８５２では、ハローフレームの送信元であるノード装置（LS）にあたる値が、（図１５に示したような）重み付けテーブルのGDにあたるかどうかを判定する。この実施形態ではこのようにして、ルーティングの評価を行っている。
【０１６１】
ハローフレームの送信元であるノード装置（LS）が、重み付けテーブルのGDと一致しなかった場合には、フローは図１９の記号(VI)へ飛び、ステップＳ１９３０で宛先LD候補を評価値順にソートする。そしてステップＳ１７００’にて1つのくりかえしサイクルを了
える。
【０１６２】
ハローフレームの送信元であるノード装置（LS）が、重み付けテーブルのGDと一致した場合には、フローはステップＳ１８５４へ進む。そして、ハローフレームの送信元（LS）に対応する重み付けテーブルに、隣接ノードの候補が存在するかどうかを検索する。そして図１９の記号(V)を挟んでステップＳ１９００にて、宛先LD候補が有る場合にはフロー
はステップＳ１９１０へ進む。ステップＳ１９１０では、このハローフレームに関する経路品質重みdを計算して、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ１９１２では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１９１４では、このハローフレームに関する評価値Eを
上述したように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ
１９１６にて、宛先LD候補に関するエージングカウンタをリセットする。なお紙幅の関係で省略したが、宛先LD候補が複数存在する場合にはステップＳ１９１０からステップＳ１９１６をその個数分くりかえすこともできる。そしてフローはステップＳ１９３０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７００’にて1つのくりかえしサイ
クルが完了する。
【０１６３】
一方、ステップＳ１９００にて宛先LD候補が無い場合にはフローはステップＳ１９２０へ進む。ステップＳ１９２０では、新たな宛先LD候補のホップ数を初期値（ここでは1）
に設定する。ステップＳ１９２２では、宛先LD候補のリンク間到達重みwに初期値（例え
ば0.5）を設定する。ステップＳ１９２４では、このハローフレームに関する経路品質重
みdを計算して、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ１９２６では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１９２８では、このハローフレームに関する評価値Eを上述した
ように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１９２９
にて、宛先LD候補に関するエージングカウンタをリセットする。そしてフローはステップ
Ｓ１９３０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７００’にて1つ
のくりかえしサイクルが完了する。
【０１６４】
くりかえし処理Ｓ１７００〜Ｓ１７００’が一通り完了したところで、フローは記号(VIII)を挟んで図２０のステップＳ２０００へ進む。
【０１６５】
ステップＳ２０００では、ハローフレームの送信元であるノード装置（LS）に対応する（そのLSがGDとなっている）エントリが、自ノード装置の持つ重み付けテーブル（群）のうちに存在するかどうかを確認する。重み付けテーブルに該当エントリが存在した場合には、フローはステップＳ２０１０へ飛ぶ。重み付けテーブルに該当エントリが存在しなかった場合には、フローはステップＳ２００１へ進む。
【０１６６】
ステップＳ２００１では、そのLSをGDとした新たな重み付けテーブルを作成する。ステップＳ２００２では、新たな宛先LD候補のホップ数を初期値（ここでは1）に設定する。
ステップＳ２００３では、宛先LD候補のリンク間到達重みwに初期値（例えば0.5）を設定する。ステップＳ２００４では、このハローフレームに関する経路品質重みdを計算して
、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ２００５では、宛先LD
候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ２００６では、このハローフレームに関する評価値Eを上述したように算出し
て、宛先LD候補に関する評価値Eを更新する。それからステップＳ２００７にて、宛先LD
候補に関するエージングカウンタをリセットする。それからフローはステップＳ２０１０に進む。
【０１６７】
ステップＳ２０１０では、ハローフレームに含まれるハローヘッダ一個ごとのくりかえし処理を開始する。
【０１６８】
記号(IX)を挟んで図２１のステップＳ２１００では、ハローヘッダのGDが、自ノード装置の持つ重み付けテーブルに存在するかどうかを確認する。重み付けテーブルに該当エントリが存在した場合には、フローはステップＳ２０１０’へ飛び、1つのくりかえしサイ
クルが完了する。重み付けテーブルに該当エントリが存在しなかった場合には、フローはステップＳ２１０１へ進む。
【０１６９】
ステップＳ２１０１では、そのハローヘッダのGDに対応した新たな重み付けテーブルを作成するとともに、そのテーブルに、ハローフレームの持つアドホックヘッダのLSをフィールドLDの値として持つようなエントリを作成する。ステップＳ２１０２では、新たな宛先LD候補のホップ数hを、ハローヘッダのホップ数+1として設定する。ステップＳ２１０
３では、宛先LD候補のリンク間到達重みwに初期値（例えば0.5）を設定する。ステップＳ２１０４では、このハローヘッダに関する経路品質重みdを使って経路品質重みdを再計算して、その宛先LD候補に関する経路品質重みdを初期化する。ステップＳ２１０５では、
宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ２１０６では、このハローヘッダに関する評価値Eを算出して、宛先LD
候補に関する評価値Eを更新する。それからステップＳ２１０７にて、宛先LD候補に関す
るエージングカウンタをリセットする。それからフローはステップＳ２０１０’に進み、1つのくりかえしサイクルが完了する。
【０１７０】
そしてくりかえし処理Ｓ２０１０〜Ｓ２０１０’が一通り完了すると、一連のフローは終了する。
【０１７１】
図２２は、ハローフレームの交換シーケンスを示す図である。各ノード装置は、ハローフレームを近隣のノード装置に向けてブロードキャスト送信する。ハローフレームには、
各ノードまでの経路の中で最適と判定されたリンク情報が含まれている。各ノード装置は、ハローフレームを受信すると、保有する隣接ノード管理テーブル６もしくは６ａおよび重み付けテーブル７もしくは７ａと比較して、各ノード装置についての重みに関する情報の作成及び更新を行っていく。また、隣接ノード管理テーブル６もしくは６ａを参照して、ハローフレームのリンク情報の更新を行う。この動作を各ノード装置が複数回繰り返すことで、ノード装置は、他のノード装置のそれぞれまでのルーティングを可能とするリンク先情報を複数個持つことが可能となる。
【０１７２】
或る実施形態においては、ノード装置１もしくは１ａが、特定のノード装置からそれまで受信できていたハローフレームを所定の期間内（例えば３０分以内）に受信できなくなった場合に、その特定のノード装置を、通信不能状態にあると見做して、その旨をゲートウェイ装置に通知することができる。また、受信したハローフレームの内容から判断を行ったうえで、異常が検出されればその旨をゲートウェイ装置へ通知することもできる。更には、隣接ノード管理テーブル６もしくは６ａを参照して、あるノード装置について異常が検出された場合には、上記重み付けテーブル７もしくは７ａの対応する重みを更新して、そのノード装置についての優先度を低くしてもよい。
【０１７３】
更に或る実施形態では、図２２に示すとおり、ゲートウェイ装置との間でハローフレームを送受することにより、ゲートウェイ装置の死活監視を行うこともできる。
【０１７４】
ノード装置間での状態監視については、所定の時間内に相手のノード装置からハローフレームを受信しない場合には、相手のノード装置に対してハローフレーム発生要求を送信し、相手のノード装置からハローフレームを受信するか否かにより、相手のノード装置の状態を監視するような構造をとってもよい。
【０１７５】
或る実施形態では、上記のようにして各ノード装置においてネットワークを監視し、ハローフレームにそのハローフレームが通過した経路上のノード装置についての情報を付加してゆき、さらにサーバで集計することにより、ネットワークの監視を行うこともできる。
【０１７６】
本発明の実施形態に応じて、ハローフレームを用いて各ノード装置がネットワークの監視を行うことで、ネットワーク監視用のフレームを別途流通させる必要がなく、流通フレーム数を抑制することができる。また、隣接ノード装置とで送受するハローフレームを用いてネットワーク監視を行うことにより、センターからネットワーク監視用のフレームを送信してその応答により状態を監視する場合と比較して、ターンアラウンドを小さく抑えたリアルタイムに近い監視が可能となる。
【０１７７】
図２３は、本発明の実施形態にかかるノード装置もしくはプログラムを実施可能なハードウェアを示す概要図である。
【０１７８】
図２３にはまず、各種計算処理を担うマイクロプロセッサユニット（MPU）２３００が
示されている。マイクロプロセッサユニット２３００は、有線物理層処理部（PHY）２３
１２とMII（Media Independent Interface）/MDIO（Management Data Input/Output）イ
ンターフェイス２３１０を介して通信可能に接続されている（なお"MII/MDIO"とは、「MIIまたはMDIO」を意味する）。MIIとMDIOはいずれも、物理層とMAC副層（Media Access Control sublayer）との間のインターフェイスである。
またマイクロプロセッサ２３００は、時刻の計測などを担うタイマIC２３２２と、I2C（Inter-Integrated Circuit）/PIO（Parallel Input/Output）バス２３２０を介して通信可能に接続されている（なお"I2C/PIO"とは、「I2CまたはPIO」を意味する）。さらにマイ
クロプロセッサ２３００は、記憶手段であるダイナミックランダムアクセスメモリ（DRAM
）２３３２およびフラッシュメモリ２３３４、ならびにネットワークインターフェイスである無線LAN処理部２３３６と、PCI（Peripheral Component Interconnect）バス２３３
０を介して通信可能に接続されている。当然のことながら、当該技術分野の常識に照らし、ここに例示した規格・種類以外の装置を適宜使用してもかまわない。
【０１７９】
MPU２３００は、不揮発性記憶装置の一種であるフラッシュメモリ２３３４上に格納さ
れたファームウェアなどの種々のプログラムを、DRAM２３３２上にロードして実行することで、様々な処理を実行できる。MPU２３００は例えば、上述した各種処理をノード装置
１に実行させるためのファームウェアプログラムなど、種々のプログラムを実行できる。
【０１８０】
なお、DRAM２３３２は、フレームの送信バッファ及び受信バッファとしても使用可能である。フラッシュメモリ２３３４は、上述したようにファームウェアプログラムなどを格納できる。また、フラッシュメモリ２３３４には、ノード装置１もしくは１ａ自身に固有の情報（例えば、ノードＩＤやＭＡＣアドレス）も格納できる。
【０１８１】
有線PHY処理部２３１２は、有線接続における物理層の処理を行う回路である。また、
無線LAN処理部２３３６は、無線ＬＡＮ接続における物理層の処理を行うハードウェアで
ある。無線LAN処理部２３３６は、例えばアンテナ、ＡＤＣ（Analog-to-Digital Converter）、ＤＡＣ（Digital-to-Analog Converter）、変調器、復調器などを含むことができ
、物理層とＭＡＣ副層の処理を行う。したがって、本実施形態では、ノード装置１もしくは１ａが、有線通信と無線通信の双方を行うことができる。当然ながらノード装置１もしくは１ａが、有線通信又は無線通信の一方のみを行う実施形態も可能である。
【０１８２】
タイマIC２３２２は、設定された時間が経過するまでカウントアップ動作を行い、設定された時間が経過すると割り込み信号を出力する回路である。
【０１８３】
なお、上記の実施形態においては、ノード装置について主に説明したが、上記の方法をコンピュータに実行させる制御プログラムも、本発明の実施形態の一例に含まれる。当該制御プログラムは、磁気ディスク、光磁気ディスク、不揮発性の半導体メモリ、光ディスクなどの、コンピュータ読み取り可能な記憶媒体に格納されて提供され、コンピュータにロードされ、コンピュータにより実行されてもよい。
【０１８４】
当該制御プログラムを実行するコンピュータは、不図示のノード装置に内蔵又は接続され、上記不図示のノード装置が上記実施形態のノード装置１もしくは１ａと同様に動作するように、当該制御プログラムにしたがって上記不図示のノード装置を制御する。例えば、上記実施形態を別の観点から見れば、ノード装置１もしくは１ａの内蔵コンピュータであるＭＰＵ２３００は、フラッシュメモリ２３３４に格納された制御プログラムにしたがってノード装置１もしくは１ａを制御し、上記各処理をノード装置１もしくは１ａに行わせている、とも見做せる。
【０１８５】
以上説明したように、上記の実施形態に係るノード装置によれば、大規模の通信ネットワークに適用する場合であっても、各ノード装置が隣接ノード装置から受信した情報により経路の最適化を行うことやネットワークの監視を行うことが可能となる。
【０１８６】
また、本実施形態では各種のデータについて、理解しやすいようにテーブル形式の例を開示したが、この例に限らず、データを対応付けて管理可能なＸＭＬやツリー構造など他の管理形式を採用してもよい。
【技術分野】
【０００１】
本発明は、複数のノードを含むネットワークにおける、経路選択可能な装置／プログラムに関する。
【背景技術】
【０００２】
ネットワーク装置は、これまで非常に多くの研究がなされている。最も普及しているのは、ＩＰ（Internet Protocol）ネットワークを利用したネットワーク装置である。また
、複数のプロトコルやネットワークを収容することを目的としたＭＰＬＳ（Multi Protocol Labeled Switching）は、自動的に経路を作成する機構を持つネットワーク装置である。また、アドホックアルゴリズムの代表例としてＡＯＤＶ（Ad-hoc On-Demand Vector）
やＯＬＳＲ（Optimized Link State Routing）がある。
【０００３】
ＩＰネットワーク装置では、ＩＰアドレスに従いルーティングを決定する。ＩＰアドレス自体が木構造を持つため、ＩＰアドレスの上位から合致するＩＰネットワークを管理するネットワーク装置に伝送することで、最終的に目標とする端末へフレームを伝送することができる。ルーティングはＩＰアドレス体系により決定されている。どのネットワーク装置かどのＩＰネットワークを管理しているかは、ルーティングテーブルによって規定される。ルーティングテーブルは主に手動で設定されることも多いが、ＲＩＰ（Routing Information Protocol）により自動的に更新されることもある。ＲＩＰとは、ネットワーク装置が管理するＩＰネットワークを周囲にブロードキャストし、ネットワーク装置が互いの管理するＩＰネットワークを確認する方式である。
【０００４】
ＭＰＬＳでは、ネットワークがＬＳＲ（Label Switch Router）と呼ばれるネットワー
ク装置間と外部ネットワークとに分離される。外部ネットワークからのフレームは、エッジノードと呼ばれる外部ネットワークと内部ネットワークの両方にまたがるネットワーク装置によって内部ネットワークに取り込まれる。このとき、外部フレームの先頭にはラベルが挿入される。各ＬＳＲは、それぞれがラベル転送テーブルを持つ。ラベル転送テーブルは、入力フレームのラベルと出力フレームのラベルおよびあて先を保持する。ＬＳＲは入力されるフレームのラベルを取り出し、該当するラベルをラベル転送テーブルから発見し、出力フレームのラベルに書き換え、該当するあて先に送出する。ラベル転送テーブルのＬＤＰ（Label Distribution Protocol）によって行われる。ＬＤＰは、まずＲＩＰな
どによりルーティングテーブルの作成を行い、これにラベルを付加し、隣接ノード間で通知しあうプロトコルである。
【０００５】
ＡＯＤＶは、経路検索にブロードキャストを用いて、他の通信ノード装置がブロードキャストを繰り返し目的のノード装置への経路を発見する手法である。通信ノード装置は、目標とする経路を発見するために周囲に「Route Request（ＲＲＥＱ）」というフレーム
を送出する。このフレームには、検索目標の通信ノードＩＤが明記されている。周囲の通信ノード装置は、自身を検索していない場合は、新たにＲＲＥＱフレームを作成して、周囲へのブロードキャストを繰り返し行う。このとき各通信ノード装置は、送り元のメッセージが、隣接するどの通信ノード装置から受信されたものなのかを記録する。ＲＲＥＱメッセージが目的の通信ノード装置に達したとき、その目的の通信ノード装置は、「Route Reply（ＲＲＥＰ）」フレームを作成し、送り元のノードに対して、ＲＲＥＱフレームが
送られてきた経路をたどるようにしてＲＲＥＰフレームを送信する。このようにして、双方向の通信経路が作成されている。
【０００６】
ＯＬＳＲ（Optimized Link State Routing）では、通信ノード装置同士が定期的にフレ
ームを交換しあうことで、ネットワーク全体を把握し、目的の通信ノードまでの経路を検出するという方式を採用している。通信ノード装置は、周期的にＨＥＬＬＯ（ハロー）フレームを送出し、互いにその存在を通知しあう。通信相手となる通信ノード装置の存在が判明したところで次に効率的にネットワーク全体にフレームを配信するためのフラッディング用のパスを生成する。これをＭＰＲ（Multi Point Relay）と呼ぶ。ＭＰＲにより、
各通信ノード装置から効率よくフレームをネットワーク全体へブロードキャストできる。次にこのＭＰＲを用いて、経路作成メッセージであるＴＣ（Topology Control）フレームをノード装置同士が互いに配信することで全ノード装置がネットワークトポロジーを知ることができる。フレームを、目標とする通信ノード装置に送るには、送出元となる通信ノード装置自身が知っているネットワークトポロジーを参照し、送るべき隣接通信ノード装置にフレームを託す。隣接ノード装置も同様に処理を行い、最終的に目標ノード装置にフレームを届ける。
【０００７】
アドホック無線通信ネットワークに関しては、公知の技術として、各ノードがハローメッセージとして自ノードの存在を通知する情報と、自ノードまでのルートメトリックとを含んだ情報を放送し、該ハローメッセージを受信した他ノードは、受信したルートメトリックにハローメッセージを放送してきたノードと自ノードとの間のルートのためのルートメトリックを追加し、該追加後のルートメトリックを使用する技術について提供されている（例えば、特許文献１）。ここでのルートメトリックは、ホップ数、リンク品質等の因子により算出される、送信元と宛先とのコストを表す値である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特表２００６−５２６９３７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＩＰネットワーク装置やＭＰＬＳでは、前提としてアドレスによってネットワーク自体が構造を持っていることを利用している。ＩＰアドレスが木構造であるため、アドレスが上位からマッチしていく方向を選択することにより経路が決定する。また、これらは有線の接続を前提としている。２つの通信端末間で有線接続は安定した通信ができ、接続されていない通信機器はフレームを受信することはないため、単純に通信機のホップ数だけで決めることができる。
【００１０】
しかし無線通信を前提としたとき、これらの方式では通信品質のよい経路作成は困難である。無線通信では、通信品質は有線通信と比較した場合に悪く、かつ通信とは直接関係しない他の通信端末にも影響を与える。また通信品質は、距離や周囲の環境の依存性も高く、時間的変化も伴う。このような環境下で上記プロトコルを実施した場合、ホップ数のみで決定すると、アルゴリズムが遠くの通信端末を経由しようとする場合がありえる。しかしながら、距離が遠ければその分通信品質も悪いため非常に品質の悪い経路を作成してしまう。
【００１１】
ＡＯＤＶは、経路作成時にネットワークに負荷をかける。通信端末数が少ない場合は問題ないが、通信端末数が多くなり通信量が増えた場合ネットワークへの負荷が高くなってしまう。その結果、通信がすでに確立している通信ノード装置にも影響を与え、リンク切れを起こす可能性が高く、結果的に通信できるノード装置は非常に少なくなりそのほとんどが経路確立できなくなる。また、上記のようにホップ数をベースとしているため通信品質の悪い経路を作成してしまうことも考えられる。
【００１２】
ＯＬＳＲでは、全ノード装置がネットワークトポロジーを知る必要がある。このためス
ケールに限界が生じる。また、全ノード装置のトポロジーが判明する時間が必要となる。
【００１３】
上記のとおり、有線無線を問わず、ネットワークにおいては、通信量や周囲の環境影響によりノード装置間の通信品質が変化することがあり、特に無線では変化が大きい。このため、非常に多くのノード装置を含んだネットワークを考えた場合、ネットワークを統括するサーバを設置し、該サーバによってネットワークの管理を行うことは実用的ではない。というのは、ノード装置の個数が多いのでサーバから制御指示を送信するだけでも大変な負荷になってしまうからである。そこで、非常に多くのノード装置からネットワークがつくられている場合には、各ノード装置が自律的に経路選択や死活監視などの動作をすることが望まれる。
【００１４】
さて、各ノード装置が自律的に動作することを考えた場合、上述の通り通信品質は変化するので、あるノード装置に宛てた送信フレームを中継する際には、現時点で有効な経路を各ノード装置が把握しておく必要がある。例えば、固定的な構造を持つネットワークや一般的な検索手法である二分木探索などの手法では、ネットワークや木の全体像が初めからわかっているため、どこまで経路を探索したかを容易に判別可能であるのに対し、本願が対象とするノード装置間のリンクが変化してゆくようなネットワークでは、各ノード装置は、周囲のノード装置の先にどのようなノード装置がリンクされているかを知らないので、どこまで経路を探索したかを知るための仕組が必要になる。
【００１５】
本発明では、簡易な構造で、かつ、ネットワークに負荷をかけずに、自律的に適切な経路を選択可能なノード装置／プログラムを提供する。
【課題を解決するための手段】
【００１６】
本発明の実施形態にかかるノード装置は、複数のノード装置を含むネットワークの中の、ノード装置において、自ノードが送信したフレームの情報として、フレームを一意に識別するための識別情報と該フレームの送出先ノードに関する情報とを格納する識別情報管理テーブルと、フレームの最終宛先ノードごとに、フレームを中継するため送出先とする他ノードについての重み付け情報を格納する宛先ノード別重み付けテーブルと、他ノードから自ノードに宛てて送信されたフレームを受信するフレーム受信手段と、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されている場合に、該識別情報と対応付けて格納されている前記送出先ノードについて、該フレームの最終宛先に対応する前記宛先ノード別重み付けテーブルのデータを更新する宛先ノード別重み付けテーブル更新手段と、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されていない場合に、前記フレームの最終宛先ノードに該当する前記宛先ノード別重み付けテーブルを参照して、該フレームを中継するための送出先とする他ノードを決定するフレーム送出先決定手段とを備える。
【００１７】
他ノードからフレームを受信すると、宛先ノード別重み付けテーブルを参照し、転送すべきノードを決定する。転送先のノードを重みにしたがって決定し、また、他ノードへのフレームの転送の成否に応じて重みが更新される。ノード装置は、自律的に経路を学習できる。
【００１８】
前記宛先ノード別重み付けテーブル更新手段は、前記フレーム受信手段により受信した前記フレームの識別情報が、前記識別情報管理テーブルに格納されている場合に、該識別情報と対応付けて格納されている前記送出先ノードについて、該フレームの最終宛先に対応する前記宛先ノード別重み付けテーブルの該送出先ノードに対する重み付けを、優先度が低くなるように更新するようにしてもよい。
【００１９】
更には、自ノードの周囲に存在する他ノードに関する情報を格納する隣接ノード管理テ
ーブルと、ハローメッセージとして、自ノードの存在を知らせる情報と、前記隣接ノード管理テーブルから読み出した情報であって、周囲の経路に関する情報とを送信するハローメッセージ送信手段と、他ノードからの送信されたハローメッセージを受信するハローメッセージ受信手段と、前記ハローメッセージ受信手段により受信したハローメッセージの送出元ノードに関する情報に基づき、前記隣接ノード管理テーブルを更新する隣接ノード管理テーブル更新手段と、を更に備え、前記隣接ノード管理テーブルにおいて、所定の状態になった第１のノードを検出した場合には、前記宛先ノード別重み付けテーブル更新手段は、前記宛先ノード別重み付けテーブルの送出先ノードが該第１のノードであるデータを優先度が低くなるように更新するようにしてもよい。
【発明の効果】
【００２０】
本発明の実施形態にかかるノード装置によれば、ノード装置間のリンクが変化するようなネットワークにおいても、各ノード装置は、保有する重みに関する情報を参照して転送先のノードを決定し、重みに関する情報を更新する。これにより、ネットワークの全体を把握せずとも、自律的に最適な経路を学習して通信を行うことが可能となる。
【図面の簡単な説明】
【００２１】
【図１】通信システムの全体概念図である。
【図２】本発明の実施形態に係るノード装置の概略図である。
【図３】本発明の実施形態に係るノード装置の詳細な模式図である。
【図４】隣接ノード管理テーブルの構造を示す図である。
【図５】フレームのフォーマット例である。
【図６】図５のフレームのフォーマット例の説明である。
【図７】隣接ノード管理テーブルに基づくデータ転送処理を説明する図である。
【図８】フレームの転送結果により重みに関する情報を操作する処理を説明する図である。
【図９】ＦＩＤ管理テーブルの例を示す図である。
【図１０】本発明の実施形態に係るノード装置のデータフレーム受信時の処理を示したフローチャートの概略（その１）である。
【図１１】本発明の実施形態に係るノード装置のデータフレーム受信時の処理を示したフローチャートの概略（その２）である。
【図１２】ハローヘッダのフォーマットを示す図である。
【図１３】本発明の実施形態に係るノード装置において、遅延により通信品質を計測する方法を説明する図である。
【図１４】ハローヘッダを含んだハローフレームの詳細なフォーマットを示す図である。
【図１５】重み付けテーブルの構造を詳細に説明する図である。
【図１６】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その１）である。
【図１７】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その２）である。
【図１８】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その３）である。
【図１９】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その４）である。
【図２０】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その５）である。
【図２１】本発明の実施形態に係るノード装置のフレーム受信時の処理を示した詳細なフローチャート（その６）である。
【図２２】ハローフレームの交換シーケンスを示す図である。
【図２３】本発明の実施形態にかかるノード装置もしくはプログラムを実施可能なハードウェアを示す概要図である。
【発明を実施するための形態】
【００２２】
以下、本発明の好適な実施の形態について、図面を参照して詳細に説明する。
まず、本明細書での用語について説明をする。
【００２３】
「フレーム」とは、プロトコルが扱うデータ単位のことを指す。「フレーム」には、例えば「ハローフレーム」「データフレーム」が含まれるが、これらに限定はされない。
【００２４】
「ハローフレーム（HELLOフレーム）」とは、本発明の実施形態にかかるノード装置が
、別のノード装置に対して互いの存在・状態の確認のために送出する特別なフレームのことを指す。
【００２５】
「データフレーム」とは、ネットワークが（スタートノードからゴールノードへと）伝送しようとするデータのことを指す。なお当然のことながら本発明の実施形態にかかるノード装置は、「ハローフレーム」と「データフレーム」を識別するための適切な手段を有することができる。
【００２６】
「Local Destination (LD)」とは、或るノード装置を主体として観たときに、次にフレームを渡すべき隣接ノード装置を表すあて先ノードIDのことを指す。なお本明細書ではLDのことを、「ローカル宛先アドレス」と称することもある。
【００２７】
「Local Source (LS)」とは、LDへフレームを送るその直接の送り元となるノード装置
（すなわち、LDにとっての自ノード装置）を表したノードIDのことを指す。なお本明細書ではLSのことを、「ローカル差出アドレス」と称することもある。
【００２８】
「Global Destination (GD)」とは、データフレームのネットワークに跨った一連の伝
播に関する最終的なあて先となるノードIDのことを指す。なお本明細書ではGDのことを、「グローバル宛先アドレス」と称することもある。
【００２９】
「Global Source (GS)」とは、データフレームのネットワークに跨った一連の伝播に関する最初の送り元であるノードIDのことを指す。なお本明細書ではGSのことを、「グローバル差出アドレス」と称することもある。
【００３０】
「フレームID (FID)」とは、各フレームが持つ固有の識別情報のことである。FIDとし
ては例えば一連の番号を用いることができるが、これに限定はされない。
【００３１】
「重み」とは、本発明の実施形態にかかるフレーム伝播経路選択にあたって考慮される値である。重みとしては、復路リンク重み、往路リンク重み、双方向リンク重み、経路品質重み、復路品質重み、リンク間到達重み、が本明細書に例示されているが、これらに限定はされない。なお本明細書の記載において「重み」または「重みに関する情報」と言うときには、何らかの種類の重みを用いて算定した値のことを指すこともあると解釈されたい。
【００３２】
「復路リンク重み」とは、復路を来たるフレームに関する重みのことである。なお、或るノード装置を主体として考えるとき、そのノード装置が別の隣接するノード装置からフレームを受けるとするなら、そのフレームは「復路」を通ってきたことになる。
【００３３】
「往路リンク重み」とは、往路を行くフレームに関する重みのことである。なお、或る
ノード装置を主体として考えるとき、そのノード装置が別の隣接するノード装置へフレームを送るとするなら、そのフレームは「往路」を通ることになる。
【００３４】
「双方向リンク重み」とは、上述した往路リンク重みと復路リンク重みとを組み合わせて算出する重みのことである。本発明の実施形態では、「復路リンク重み」「往路リンク重み」「双方向リンク重み」は、後に詳述する隣接ノード管理テーブルが含むことができるデータである。しかし他の実施形態では、これ以外の組み合わせを含むようにしてもかまわない。
【００３５】
「経路品質重み」とは、GDまでの経路上での遅延を数値化したものを指す。
「復路品質重み」とは、相手となるノード装置から自ノード装置へ至る方向への通信品質を数値化したものを指す。
【００３６】
「リンク間到達重み」とは、フレームのリンク間での転送の成否を数値化した値である。本発明の実施形態では、「経路品質重み」「復路品質重み」「リンク間到達重み」は、後に詳述する重み付けテーブルが含むことができるデータである。しかし他の実施形態では、これ以外の組み合わせを含むようにしてもかまわない。
【００３７】
図１は、通信システムの全体概念図である。図１に示すように、ネットワークにはノード装置（ａ、ｂ、…、ｓ、ｔ）が互いに接続されて含まれている
。本通信システムにおいては、スタートノード（図１の例ではノード装置ｂ）からゴールノード（図１の例ではノード装置ｔ）へと情報を伝達するにあたり、各ノード装置が中継器として動作する。
【００３８】
各ノード装置は、それぞれ固有の識別情報（ＩＤ、Identification）を保有する。各ノード装置に割り当てられたＩＤを、以下ノードＩＤとする。各ノード装置は、互いに隣接しているノード装置やネットワーク全体については把握していない。初期状態においては、互いのリンクは存在しておらず、各ノード装置は、自身以外のノード装置についてはその存在・状態を把握していない。
【００３９】
そこで、図１に示す通信システムにおいてスタートノード{b}からゴールノード{t}へと情報を伝達するには、まず、ネットワークを構築する必要がある。ネットワークを構築する手順は、以下のとおりである。
【００４０】
まず行われるのは、周囲のノード装置の検出である。或るノード装置は、自身の存在を近隣に存在するノード装置へ周期的に通知する。近隣ノード装置への通知には、経路作成に関連した情報が付随されている。各ノード装置は、通知を受信すると、周囲のノード装置についてのリストを作成して、自装置の周囲のノード装置の存在を把握することができる。
【００４１】
周囲のノード装置を検出したノード装置は、作成したリストに基づいて、自身が情報を転送する相手となるべきノード装置を決定して、そのノード装置に情報を転送する。
【００４２】
或るノード装置が、情報を転送すべきノード装置を決定するにあたって、周囲に存在する複数のノード装置のうちいずれのノード装置に情報を託せば、目的とするゴールノードに情報を到達させられるかについては、この時点では未だこのノード装置は識らない。そこで、本実施形態に係るノード装置では、周囲のノード装置のいずれに優先的に情報を転送すべきかを示す重み付けテーブルを作成し、重み付けテーブルに格納されている重みに関する情報にしたがって、情報の転送の対象となるべきノード装置を決定する。
【００４３】
以下、本実施形態に係るノード装置について、具体的に説明する。
図２は、本実施形態に係るノード装置の概略図である。図２におおまかな概要を示すノード装置１は、フレーム処理部２、リンク管理部３、ルーティング決定部４、ＦＩＤ（フレームＩＤ）管理テーブル５、隣接ノード管理テーブル６、及び重み付けテーブル７を有する。図２には明示されていないが、当該技術分野において既知である何らかの種類の記憶装置（例えば、DRAMもしくはフラッシュメモリ）が、ＦＩＤ（フレームＩＤ）管理テーブル５、隣接ノード管理テーブル６、及び重み付けテーブル７をデータテーブルとして格納できる。
【００４４】
フレーム処理部２は、ノード装置１に隣接するノード装置との間で交換されるデータフレームの処理を行う。フレーム処理部２はまた、データフレームを受信した場合に、記憶装置（図２には示されていない）にアクセスしてＦＩＤ管理テーブル５（請求項の識別情報管理テーブルに相当）を用い、ループの発生の検出も行う。
【００４５】
リンク管理部３は、記憶装置（図２には示されていない）にアクセスして隣接ノード管理テーブル６を用い、隣接するノード装置の死活及びリンク強度を管理する。
【００４６】
ルーティング決定部４は、記憶装置（図２には示されていない）にアクセスして重み付けテーブル７（請求項の宛先ノード別重み付けテーブルに相当）を参照し、フレームを次にどの隣接ノード装置に転送すべきかを決定する。重み付けテーブル７は、フレームの最終的な宛先（すなわち、Global Destination (GD)）ごとに作成される。
【００４７】
なお、図１に示すネットワークを構築する複数のノード装置の各々は、それぞれが図２に示すような構造をとるが、以下の説明においては、他のノード装置と区別して、自ノード装置について符号「１」もしくは「１ａ」を付して説明している。また、各ノード装置は、無線によって接続されていてもよいし、有線によって接続されていても構わない。所望であれば、無線と有線が混在したネットワークに本発明の実施形態にかかる装置もしくはプログラムを適用できることも、本発明の実施形態では想定されている。
【００４８】
図３は、実施形態に係るノード装置をさらに説明するための、より詳細な模式図である。なお、参照番号についた接尾辞"a"は、同番号の構成要素（element）と同様であるかもしくは類似した構成要素を指していることに留意されたい。なお本明細書では、例えば或る装置ＸＸＸと装置ＸＸＸａがともに実施形態に包摂されうる。また、参照番号の接尾辞を省略して、接尾辞が無いものと有るものとを包括する概念を指すこともある。例えば、装置ＸＸＸと表記したとき、矛盾が生じないかぎりは、装置ＸＸＸａのことも含んでいると解釈される。
【００４９】
図３のノード装置１ａは、フレーム処理部２ａ、リンク管理部３ａ、ルーティング決定部４ａ、ＦＩＤ管理テーブル５ａ、隣接ノード管理テーブル６ａ、重み付けテーブル７ａ、受信部１０、送信部２０を有する。なお、ＦＩＤ管理テーブル５ａ、隣接ノード管理テーブル６ａ、及び重み付けテーブル７ａは、任意の適切な記憶装置に格納できる。そしてその記憶装置をノード装置１ａの内部に収めることもできるし、外部に設置することも可能である。また、そうした記憶装置は、各ノード装置ごとに単一のものであってもよいし、複数存在してもよい。
【００５０】
上述したLSに対応するノード装置１ａが、受信部１０にてフレーム（データフレームおよびハローフレームを含む）を受信すると、フレーム分岐処理部１２がフレームの種別を識別して、その種別に応じて処理を分岐させる。詳しくは後述するが、フレーム分岐処理部１２は、フレームに付されたそのフレームの種別を表すための識別子を用いることができる。
【００５１】
受信されたフレームがハローフレームであった場合には、フレーム分岐処理部１２が、フレームをリンク管理部３ａに渡す。リンク管理部３ａは、隣接ノード管理テーブル６ａを格納した記憶装置にアクセスし、隣接するノード装置の死活及びリンク強度を管理する。そしてリンク管理部３ａは、ループが検出された場合には、重み付けテーブル７ａを格納した記憶装置にアクセスし、重みに関する情報の登録または更新を行う（詳しくは後述する）。
【００５２】
受信されたフレームがデータフレームであった場合には、フレーム分岐処理部１２が、フレームをフレーム処理部２ａに渡す。フレーム処理部２ａは、FID管理テーブル５ａを
格納した記憶装置にアクセスし、FID、LD、およびGSに関する情報を管理する。そしてフ
レーム処理部２ａはフレームをルーティング決定部４ａに渡す。また、フレーム処理部２ａは、ループが検出された場合には、重み付けテーブル７ａを格納した記憶装置にアクセスし、重みに関する情報の登録または更新を行う（詳しくは後述する）。
【００５３】
ルーティング決定部４ａは、重み付けテーブル７ａを格納した記憶装置にアクセスして重みに関する情報を得たうえで、フレームをどのノード装置へ送信するかを決定する。そして、送信部２０にフレームを渡す。
【００５４】
送信部２０は、ルーティング決定部４ａから受けとったフレームを他のノード装置へ送信するにあたり、送信処理部２２にFID管理テーブル５ａを格納した記憶装置にアクセス
させて、FIDとLDおよびGSに関する情報を登録・更新する。
【００５５】
本発明の実施形態では、上述したように、隣接ノード装置管理テーブル、FID（フレー
ムID）管理テーブル、重み付けテーブルといったテーブルを使用する。まず、隣接ノード装置管理テーブルについての説明を行う。
【００５６】
図４は、隣接ノード管理テーブル６もしくは６ａの構造を示す図である。隣接ノード管理テーブル６もしくは６ａは、ノードＩＤ、最終更新時間及びリンク強度を含む。
【００５７】
ノードＩＤは、ネットワークを構築するノード装置を識別するために各ノード装置に割り当てられた識別情報である。
【００５８】
最終更新時間は、各ノードＩＤが示すノード装置について、最後に情報が更新された日時情報である。具体的には例えば、最終更新時間としてリンク強度が更新された日時情報を格納できる。
【００５９】
リンク強度は、ノード装置１もしくは１ａが、隣接するノード装置から受信したハローフレームに含まれるリンク強度に基づき算出され、適切な記憶装置に格納される。リンク強度は例えば、電波強度やフレーム到達率を用いて算出できる。リンク強度は例えば、双方向リンク重みに対応している。
【００６０】
上記のとおり、まず、事前にネットワークを構築するために、隣接ノード間で通知用のフレーム（ハローフレーム）が交換される。そして、図２に示す隣接ノード管理テーブル６もしくは図３に示す隣接ノード管理テーブル６ａ、ならびに図２に示す重み付けテーブル７もしくは図３に示す重み付けテーブル７aが、各ノード装置において作成される。図
１の説明においても述べたとおり、本実施形態に係るノード装置１においては、ネットワークトポロジーを把握する必要はない。
【００６１】
隣接ノード管理テーブル６もしくは６ａが作成されると、隣接ノード管理テーブル６も
しくは６ａに対応する情報が格納されている隣接ノードのうち、フレームを転送すべきノード装置を決定する。フレームを転送すべきノード装置を決定するときに参照される重み付けテーブル７は、フレームを隣接ノード装置から受信したあとの処理にて更新される。
【００６２】
図５および図６は、フレームのフォーマット例である。図５に示すフレームは、隣接ノードの宛先ノード（Local Destination）についてのノードＩＤ（ＬＤ）、隣接ノードの
送信元ノード（Local Source）についてのノードＩＤ（ＬＳ）、宛先ノード（Global Destination）についてのノードＩＤ（ＧＤ）、送信元ノード（Global Source）についての
ノードＩＤ（ＧＳ）、フレームＩＤ（ＦＩＤ）、フレームタイプ（ＴＹＰＥ）、データ長（ＤＡＴＡＬＥＮ）、及びデータ本体（ＤＡＴＡ）を含む。
【００６３】
ＬＤには、ノード装置１の隣接ノードのうち、フレームを転送する宛先ノードのノードＩＤが格納される。
【００６４】
ＬＳには、LDとなる隣接ノード装置へフレームを転送する送信元のノード装置のノードＩＤが格納される。例えば、LDがノード装置１に隣接するノード装置のいずれかのノードIDであったならば、LSはそのノード装置１のノードIDとなる。
【００６５】
ＧＤには、フレームの本来の宛先のノードＩＤが格納され、ＧＳには、フレームの本来の送信元のノードＩＤが格納される。
【００６６】
フレームＩＤは、フレームを識別するための識別情報が格納される。
フレームタイプには、そのフレームの種類を示す情報が格納される。フレームの種類としては、例えば、データフレームや、ハローフレーム等があるが、これらに限定はされない。
【００６７】
データ長には、データ本体の長さ（データ長、またはフレームサイズとも称する）が格納される。
【００６８】
データ本体には、ネットワークを伝播する対象であるデータが格納される。
なおここに示したフォーマットはあくまで一例であることに留意されたい。本発明の別の実施形態では、これとは異なったフォーマットを使用することもでき、かつその別の実施形態は本発明の範囲に包摂されうる。
【００６９】
図７は、或る実施形態にかかる、隣接ノード管理テーブル６もしくは６ａに基づくフレーム転送処理を説明する図である。このうち、図７（ａ）は、隣接ノード装置ごとの重みの概要を示す図であり、図７（ｂ）は、隣接ノード管理テーブル６もしくは６ａの簡単な例を示す図である。
【００７０】
この実施形態に係るノード１もしくは１ａは、隣接するノード装置のうちいずれかからフレームを受信すると、フレームの送信元すなわちＬＳであるノード装置以外のうち、重みに関する情報に鑑みてより優先度の高いノード装置に、そのフレームを転送する。ノード装置１もしくは１ａは、隣接ノード装置のそれぞれに対してリンク番号を付しており、これによって各隣接ノード装置を識別している。
【００７１】
なお、この実施形態においては、重みに関する情報（例えば、双方向リンク重みなど）として用いる値を、0以上1以下の範囲として設定してある。この値が小さいほど、優先度が高いものとして扱う。重みに関する情報初期値として例えば0.5を設定しておき、その
後のフレーム転送の成否やループの検出の有無等に応じて変更してゆくことができる。
【００７２】
重みに関する情報の設定及び更新は、後述する重み操作関数（例えば、リンク強度を考慮した関数）により行う。重み操作関数は、ネットワーク全体の振る舞いに影響するため、ネットワークの用途に応じて変更する必要があるだろう。
【００７３】
図７（ａ）においては、リンク番号ｉの隣接ノード装置からフレームを受信した場合の、重みに関する情報による転送先ノード装置の決定方法を示している。
【００７４】
リンク番号ｉの隣接ノード装置から転送されたフレームを受信すると、ノード装置１もしくは１ａは、保有する隣接ノード管理テーブル６もしくは６ａのうち、GDのノード装置に対応する重み付けテーブルを参照する。そして、重みに関する情報を踏まえて最も優先度が高く、リンク番号が「ｉ」以外である隣接ノード装置に対して、受信したフレームが転送されることになる。
【００７５】
図７（ｂ）に示すように、隣接ノード管理テーブル６もしくは６ａでは、隣接ノード装置ごとに割り当てられるリンク番号と、リンク番号に対応付けた隣接ノード装置の重みを格納する。なお、リンク番号は、ノードＩＤで代用することも可能である。ノード装置１もしくは１ａは、リンク番号ｉの隣接ノード装置から受信したフレームにしたがって、隣接ノード管理テーブル６もしくは６ａを更新し、重みに関する情報を操作する。
【００７６】
図８は、データの転送結果により重みを操作する処理を説明する図である。
図８に示す例では、重みに関する情報として、隣接ノード装置Ａ、Ｂ、Ｃ、Ｄに対しそれぞれ、リンク番号1, 2, 3, 4 および重み w1, w2, w3, w4 を設定してある。
【００７７】
なお、例えばノード装置間の通信が無線である場合には、通信時における環境やノード装置間の距離等が通信品質に影響することがあり、ノード装置間の通信が有線である場合には、例えばトラフィック量が通信品質に影響することがある。その影響を考慮し、ここでは重みの初期値を０．５とし、かつその値の範囲を０以上１以下としているが、これはあくまで一例であって、それ以外の値をとりうる重みを用いる実施形態が想定できる。また、この実施形態においては、重みが小さい（0に近い）ほど優先度が高いとしているが
、これもまた一例である。それ以外の優先度の定めかた（例えば、重みが大きいほど優先度が高いような定めかた）をした実施形態もまた想定されている。
【００７８】
また、重み付けテーブルには、フレームを転送する際に優先的に転送すべき隣接ノード装置と、それ以外のノード装置とを示す情報を格納してもよい。例えば、フラグ等を用意しておき、フレームの転送の成否に応じて値を重み付けテーブルに設定することも可能である。
【００７９】
ノード装置１もしくは１ａは、これまで隣接ノード装置にフレームを転送した結果に応じて重みに関する情報（例えば双方向リンク重み）を操作する。まず、各重みの大小関係が、ｗ１＜ｗ２＜ｗ３＜ｗ４であるとする。すなわち、隣接ノード装置Ａについての優先度が最も高く、隣接ノード装置Ｄについての優先度が最も低いと仮定する。
【００８０】
このような場合にノード装置１もしくは１ａがフレームを隣接ノード装置Ａ〜Ｄ以外の隣接ノード装置ｉから受信すると、ノード装置１もしくは１ａは、最も優先度の高い隣接ノード装置Ａから順にフレームを転送しようとする。隣接ノード装置Ａへのデータ転送に失敗すると、次に優先度の高いノード装置Ｂにデータを転送する。
【００８１】
最終的に、隣接ノード装置Ａ及びＢのいずれについてもデータ転送が失敗し、隣接ノード装置Ｃについてはデータ転送が成功したとすると、ノード装置１もしくは１ａは、隣接ノード装置Ａ、Ｂについては重みを最大（最悪値）にして、優先度を最低に設定する。そ
して、隣接ノード装置Ｃについての重みが減らされ、優先度が高く設定されることになる。
【００８２】
次回以降のデータフレーム転送においては、このようにして更新された重みの関係（ｗ３＜ｗ４＜ｗ１＝ｗ２）に基づいて、フレームの転送先（ＬＤ）を決定し、最も優先度の高い隣接ノード装置Ｃからフレームの転送を試みることとなる。
【００８３】
次に、ループの発生を検出する方法について説明する。
図９は、ＦＩＤ管理テーブル５もしくは５ａの構成の一例を示す図である。図９に示した実施形態においては、ＦＩＤ管理テーブル５もしくは５ａは例えば、ＦＩＦＯ（First In First Out）型バッファである。ＦＩＤ管理テーブル５もしくは５ａには、フレームＩＤ（ＦＩＤ）、送信元ノードＧＳのノードＩＤ、転送先ノードＬＤのノードＩＤ、及び送信元ノードＬＳのノードＩＤが含まれる。ＦＩＤ、ＧＳ／ＬＤ／ＬＳのノードＩＤの定義については、図６に示すデータフレームのそれぞれ対応するフィールドと同様である。
【００８４】
ノード装置１もしくは１ａは、隣接ノード装置からフレームを受信すると、フレームのＦＩＤ及びＧＳのフィールドの値と、ＦＩＤ管理テーブル５もしくは５ａに格納されているレコードとを比較する。比較した結果、受信したフレームと同じＦＩＤ及びＧＳを有するレコードがＦＩＤ管理テーブル５に格納されていた場合は、ノード装置１もしくは１ａは、そのフレームが過去に一度受信したフレームと同一のフレームであると判断して、「ループが発生した」か、「途中の経路の遮断により戻りが発生した」と見做す。ループまたは戻りの発生が検出された場合には、重み付けテーブル７もしくは７ａを更新し、そのフレームのＬＳのノードＩＤに対応する重みに関する情報に、最悪値（この実施形態では最大の値）を設定する。
【００８５】
一方、同一のＦＩＤ及びＧＳを有するレコードが存在しなかった場合には、ノード装置１もしくは１ａが、受信したフレームからＦＩＤ、ＧＳ、ＬＤ、及びＬＳの各フィールドから値を取り出して、ＦＩＤ管理テーブル５に１レコード登録する。
【００８６】
つづいて、ノード装置がデータフレームを受信した際に行う処理に関し、よりいっそう詳しく説明を行ってゆく。
【００８７】
図１０及び図１１は、或る実施形態に係るノード装置１もしくは１ａのデータフレーム受信時の処理を示したフローチャートである。
【００８８】
まず、ステップＳ１で、初期化処理を実行する。ステップＳ１の初期化処理においては、例えば、無線で隣接ノード装置と通信を行う場合には、使用周波数を合わせる処理や、変調方式を決定する処理等を実行する。なお、ステップＳ１の初期化処理は、ノード装置１もしくは１ａをネットワークに設置したときにのみ実行される。
【００８９】
ステップＳ２では、データフレームの受信を待機する。ステップＳ２で、データフレームを受信すると、ステップＳ３に進み、ＬＤのフィールドに格納されているノードＩＤが自装置のノードＩＤであるか否かを判定する。LDに自装置以外のノードＩＤが格納されていた場合には、ステップＳ２に戻って待機を続ける。
【００９０】
また、ステップＳ１の処理とステップＳ２の処理との間には、上記のとおり、ハローフレームによるネットワーク構築処理も行われているが、ハローフレームの送受信については図１０及び図１１に示す処理とは異なるスレッドによって実行されるため、ここでは説明を省略する。
【００９１】
ステップＳ３で、ＬＤのフィールドに自装置のノードＩＤが格納されていると判定されると、ステップＳ４に進む。
【００９２】
ステップＳ４では、ＧＤのフィールドに格納されているノードＩＤは、自装置のノードＩＤであるか否かを判定する。ステップＳ４において、ＧＤのフィールドに、自装置のノードＩＤが格納されていると判定された場合は、つまりネットワークに跨る一連のデータ伝播の終着点が自ノード装置であったということである。したがってフローはステップＳ１０に進み、受信したデータフレームを（上位層で）処理し、一連の処理を終了する。
【００９３】
ステップＳ４において、ＧＤのフィールドに格納されているノードＩＤが、自装置以外のノードＩＤであると判定されると、フローはステップＳ５に進む。そして、ステップＳ５で、ＦＩＤ管理テーブル５に、受信したデータフレームのＦＩＤ及びＧＳとそれぞれ一致するＦＩＤ及びＧＳの組み合わせを有するレコードが、存在するか否かを判定する。
【００９４】
ステップＳ５において、ＦＩＤ管理テーブル５にデータフレームのＦＩＤ及びＧＳと一致するレコードが存在したと判定されると、フローはステップＳ６に進む。ステップＳ６では、ＦＩＤ管理テーブル５のうち、ＦＩＤ及びＧＳがいずれもデータフレームのＦＩＤ及びＧＳと一致すると判定されたレコードから、ＬＤを取り出す。そして、ステップＳ７で、データフレームのＧＤに対応する重み付けテーブル７もしくは７ａについて、ステップＳ６において取り出したＬＤと一致するノードＩＤを有するレコードについて更新を行う。例えばこの実施形態では、項LastとしてFID管理テーブルで最後にFIDを持つフレームを送出したノードIDを設定している。そしてこの項Lastに対応する重みに関する情報が、優先度がもっとも低い最悪値（例えば1.0）となるように変更できる。重み付けテーブル
７もしくは７ａを更新すると、図１１の記号（Ａ）に進む。
【００９５】
一方、ステップＳ５において、ＦＩＤ管理テーブル５に一致するＦＩＤ及びＧＳは存在しないと判定されると、フローはステップＳ８に進む。ステップＳ８では、データフレームのＧＤに対応する重み付けテーブル７もしくは７ａが存在するか否かを判定する。
【００９６】
ステップＳ８において、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａが存在しないと判定されると、フローはステップＳ９に進む。そして、ステップＳ９では、データフレームのＧＤについての重み付けテーブル７もしくは７ａを作成し、その後フローは図１１の記号（Ａ）に進む。
【００９７】
なお他の実施形態においては、ステップＳ９にて、例えば、図５に示す隣接ノード管理テーブル６もしくは６ａのリンク強度を参照して重み付けテーブルを作成してもよい。
【００９８】
ステップＳ８において、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａが存在すると判定された場合には、特に処理を行わず、図１１の記号（Ａ）に進む。
【００９９】
図１１に示す処理においては、まず記号（Ａ）からステップＳ１１に進み、重み付けテーブル７もしくは７ａから最も優先度の高い評価値に対応するノードＩＤを取得する。そしてステップＳ１２で、取得したノードＩＤに対応する適切なノード装置を発見することができるか否かを判定する。
【０１００】
ステップＳ１２において、適切なノード装置を発見することができたと判定された場合には、フローはステップＳ１３に進み、ステップＳ１１で取得したノードＩＤに対してデータフレームを転送する。
【０１０１】
そして、ステップＳ１４では、転送したデータフレームに含まれるデータに基づき、ＦＩＤ管理テーブル５にフレームのＦＩＤ及びＧＳと、ＬＤと、ＬＳとを追加する。
【０１０２】
つづいてステップＳ１５で、データフレームの転送が成功したか否かを転送先ノード装置からの応答により判断する。例えば、転送先ノード装置からａｃｋ信号を受信した場合には転送が成功したと判定し、所定時間経過してもａｃｋ信号を受信しなかった場合には失敗したと判定するようにできる。成功したと判定された場合には、ステップＳ１６で、データフレームのＧＤが示すノード装置についての重み付けテーブル７もしくは７ａについて、転送先のノード装置についてのノードＩＤに対応する評価値を操作しての優先度を上げ、図１０の記号（Ｂ）に戻る。
【０１０３】
一方、ステップＳ１５において、データフレームの転送が失敗したと判定された場合には、ステップＳ１７で、転送先のノード装置についてのノードＩＤに対応する評価値を操作して優先度を下げ、ステップＳ１１に戻る。
【０１０４】
以降は、データフレームの転送が成功するか、重み付けテーブルに適切なノードＩＤが存在しなくなるまで、ステップＳ１１以降の処理を繰り返す。
【０１０５】
ステップＳ１２において、重み付けテーブル７もしくは７ａから適切なノード装置（ノードＩＤ）が発見できないと判定された場合には、ステップＳ１８に進み、受信したデータフレームをＬＳが示すノード装置に転送し、図１０の記号（Ｂ）に戻る。
【０１０６】
以上説明したように、本実施形態に係るノード装置１もしくは１ａによれば、データフレームを転送するときに、保有する重み付けテーブル７もしくは７ａを参照して優先的にデータ転送すべきノード装置を判断し、データ転送の成否により重みに関する情報（例えば評価値）を更新する。重みに関する情報にしたがって優先的にフレームを転送すべきノード装置を判断することで、ループの発生にともなうデータフレームの戻りや、ネットワークの状態の変化によりそれまで通信可能であった経路が遮断された際のデータフレームの戻りを検出し、そのことを踏まえて経路を迂回して最適な経路で通信を継続することが可能となる。なお上述したように、重み付けテーブル７もしくは７ａはGDごとに作成されうるものであるが、ここではあくまで一例として、わかりやすくするためにひとつの重み付けテーブルだけを考えていることに留意されたい。
【０１０７】
ところで、図１に示す通信システムにおいては、各ノード装置がネットワークの状態を監視している。以下、本実施形態に係るノード装置によるネットワークの監視方法について説明する。
【０１０８】
上記のとおり、各ノード装置は、ハローフレームに他のノード装置から受信した電波の通信品質に関わる情報を含めて送信している。ノード装置は、他のノード装置から受信したハローフレームを参照して、隣接ノード装置の通信品質を算出し、図５に示す隣接ノード管理テーブル６もしくは６ａに算出した通信品質に関わる情報を保持する。或る実施形態においては、遅延及びホップ数により通信品質を決定する。
【０１０９】
図１２は、ハローフレームのうちの所定の領域に格納されるハローヘッダのフォーマットを示す図である。図１２に示すように、ハローヘッダは、グローバル宛先アドレス（すなわちGD）、ホップ数ｈ、経路品質重みｄ、復路品質重み、及びノードタイプを含む。
【０１１０】
グローバル宛先アドレス（GD）は例えば、図１２に示すハローヘッダを含むハローフレームの最初の送信元（GS）であるノード装置が持つ、重み付けテーブル７に対応するグローバル宛先アドレス（GD）の情報である。
【０１１１】
ホップ数hは例えば、このハローフレームの送信元から最終目的地（GD）であるノード
装置までのホップ数の情報である。
【０１１２】
経路品質重みｄは、GDまでの経路上での遅延から求めた値が格納される。
復路品質重みは、相手のノード装置（ここでは、ハローフレームを送信したノード装置）から自ノード装置へ至る方向の通信品質に基づいて求めた値が格納される。
【０１１３】
ノードタイプには、ゲートウェイ、中継器、及び端末等の種類が定義される。
ハローヘッダに格納される情報のうち、経路品質重みｄを求める方法について、図１３を参照してさらに具体的に説明してゆく。
【０１１４】
図１３は、本実施形態に係るノード装置１もしくは１ａにおいて、遅延により通信品質を計測する方法を説明する概念図である。「発生元」のノード装置は、定期的にハローフレームを外部に向けて送出している。図１３中に楕円形に示している網掛け部は、発生元ノード装置が送信するハローフレームを受信可能な範囲を示している。ノード装置ａ及びｂは、発生元のノード装置から順次送出されるハローフレームを受信し、１つのフレームを受信してから次のフレームを受信するまでに要する時間を計測する。以下、次のフレームを受信するまでに要する時間を、「受信周期」とも称する。
【０１１５】
図１３において、ノード装置ａ及びｂにおける受信周期と受信回数との関係を図中のグラフ（縦軸は出現回数、横軸は受信間隔）に示す。図示するとおり、各ノード装置における受信周期と受信回数との関係は、一般的に、正規分布となる。
【０１１６】
そして、一般的に、発生元のノード装置からの距離が比較的遠いノード装置ｂでは、フレームロスが発生しやすくなる。従って、ノード装置ｂでは、ノード装置ａよりもフレームロスによるフレームの受信抜けが発生しやすくなり、次のフレームを受信するまでの時間が長くなる傾向にある。このことから、本発明にかかる或る実施形態においては、受信周期Ｔが大きいことを、遅延が大きいことであると見做すような近似を行って、受信周期Ｔにより通信品質を求めている。
【０１１７】
受信周期により通信品質を求めるやりかたを説明する。まず、ある時刻ｔにハローフレームを受信し、次に時刻がｔ＋ｔ１にハローフレームを受信したとする。この場合、受信周期Ｔ＝ｔ１である。所定の期間に観測された受信周期の集合をＴ｛ｔ１、ｔ２、…、ｔｎ｜ｎ∈Ｎ｝（ｔｉ（ｉ＝１、２、…、ｎ）は各時点での観測値）とする。この場合の観測された受信周期に基づく標準偏差ｌは、以下の式（１）で表される。なお、式中の
【０１１８】
【数１】
【０１１９】
は、受信周期の観測値の平均値である。
【０１２０】
【数２】
（１）
【０１２１】
上記（１）式により得られる標準偏差を、復路リンク重みとして、隣接ノード管理テーブル６もしくは６ａの所定のフィールド（不図示）に格納する。なお、（１）式で求めた復路リンク重みを、ハローフレームに格納して相手のノード装置に送信すると、相手のノード装置は、受信した情報から往路リンク重みを得られる。このように、互いに相手のノード装置から受信したハローフレームにより自装置内で復路リンク重みを求め、求めた復路リンク重みを今度はハローフレームに含めて相手のノード装置と交換することで、往路リンク重みを得られるのである。
【０１２２】
取得した往路リンク重み及び復路リンク重みから、双方向リンク重みを算出するにあたっては、当該技術分野において適切とされるさまざまな手法を使用可能である。その一例として、双方向リンク重みは、以下の式（２）で算出可能である。
【０１２３】
(双方向リンク重み) = [{(往路リンク重み)+1}{(復路リンク重み)+1}-1]1/2 （２）
【０１２４】
図１４は、本発明の或る実施形態がアドホックネットワークにおいて使用可能な、ハローヘッダを含んだハローフレームの詳細なフォーマットを詳細に説明するための図である。なお、本発明の別の実施形態では、これとは異なったフォーマットを使用でき、かつその別の実施形態は本発明の範囲に包摂されうる。
【０１２５】
図１４に示したフレームは、おおまかには、アドホックヘッダと、圧縮ヘッダと、ペイロードとに分けられる。
【０１２６】
この実施形態においては、アドホックヘッダは、"ローカル宛先アドレス"（LD）と、"
ローカル差出アドレス"（LS）と、フレームの種別を表す"フレームタイプ"と、圧縮後の
フレームのサイズを表す"フレームサイズ"というフィールドを有している。
【０１２７】
圧縮ヘッダは、ペイロードの圧縮手法を示す"圧縮タイプ"と、圧縮前のフレームのサイズを表す"フレームサイズ"というフィールドを有している。各ノード装置は、この圧縮タイプを考慮して、適切にペイロードの伸張を行うことができる。
【０１２８】
また、ペイロードには、ハローメッセージヘッダと、一個以上のハローヘッダと、署名を示すハッシュとが圧縮して含まれている。なお、この実施形態にかかるフレームで圧縮を行っているのはフレームのサイズを軽減して通信帯域を節約するという効果を得るためである。当然のことながら、圧縮をせずにデータを有するようなフレームもまた、本発明の他の実施形態に包摂されている。
【０１２９】
ペイロードに含まれるハローメッセージヘッダには、サービスの種別を表す"サービス
タイプ"と、ペイロード内の分割状況を表す"分割情報"と、ペイロードが含むハローヘッ
ダの個数を示す"ハローヘッダ数"と、ノード装置のIDを示す"装置ID"と、暗号化された情報を復号するための"アクセスキー"というフィールドが含まれる。なおこの"装置ID"というフィールドには、図２２に関連して後述するハロー要求の送信元であるノード装置のIDが格納できる。
【０１３０】
そしてペイロードに含まれる一個以上のハローヘッダは、"グローバル差出アドレス"（GS）と、ゲートウェイ（GW）の情報についてのホップ数を表す"GW情報ホップ数"と、前述の"経路品質重み"（d）および"復路品質重み"というフィールドを含んでいる。
【０１３１】
なお以上に述べてきたフィールドの種類および順番はあくまで例に過ぎない。本発明の他の実施形態においては、上述したフィールドとそれ以外の当業者が適切と考える任意の
フィールドとを、任意の適切な順番で各ヘッダ内に配置できる。
【０１３２】
図１５は、重み付けテーブル７もしくは７ａの構造をさらに詳細に説明する図である。図１５に示す重み付けテーブル７もしくは７ａは、グローバル宛先アドレス（GD）、ローカル宛先アドレス（LD）、ホップ数ｈ、リンク間到達重みｗ、経路品質重みｄ、及び評価値Ｅを含む。また図１５には示していないが、重み付けテーブル７もしくは７ａはこの他の情報を含んでもよく、例えば、データを更新した時間情報を示す最終更新時間のデータを含んでもよい。上述したように、こうした重み付けテーブルは、それぞれのノード装置が有するものである。
【０１３３】
グローバル宛先アドレス（GD）には、受信したハローフレーム（ここでは、ノード装置を起動してから、図１６〜図２１に関連させて後述するハローフレーム受信処理が複数回行われたとして、そのいずれかの受信処理において受信したハローフレーム、という意味として解釈されたい）のハローヘッダ内のグローバル宛先アドレス（GD）のフィールドに示されるデータが格納される。
【０１３４】
ローカル宛先アドレス（LD）には、受信したハローフレームに含まれているローカル差出アドレス（LS）に示されるデータが格納される。つまり、このハローフレームを受信したノード装置を主体として考えたとき、受信したハローフレームのLSが、次に別のフレームを送信する際のLD候補となるということである。
【０１３５】
ホップ数ｈは、この重み付けテーブルを有するノード装置からGDまでのホップ数が格納されるデータである。つまり、受信したハローフレームのハローヘッダ内のホップ数に示される値に１を加算した値が格納される。
【０１３６】
ノードタイプは、ノードの種類を定義するデータであって、受信したハローフレームのハローヘッダ内のノードタイプに示されるデータが格納される。
【０１３７】
リンク間到達重みｗは、データフレームのリンク間での転送の成否を数値化したものである。この実施形態では、リンク間到達重みｗとして、受信したハローフレームのハローヘッダ内の復路品質重みに基づいて算出されたデータが格納される。
【０１３８】
経路品質重みｄは、図１２及び図１３を参照して説明したとおり、ハローフレームの受信周期の分散に基づいて算出される値である。
【０１３９】
評価値Ｅは、受信したハローフレームのハローヘッダ内の上記ホップ数ｈ、リンク間到達重みｗ、及び経路品質重みｄを用いて算出した、総合的な経路評価情報が格納される。
【０１４０】
本技術分野では、ホップ数hが増すにつれ指数関数的に通信不安程度が高まる（スルー
プットが低下する）ことが経験的に知られている。これを踏まえて、例えば、評価値Ｅを以下の（３）式で表すことができる。
【０１４１】
Ｅ（ｈ，ｗ，ｄ）＝２（ｈ＋ｗ）＋ｄ （３）
【０１４２】
とはいえ、上述した（３）式を用いること以外にも、適切に評価値Eを導出する手法を
用いてもよく、かつそうした手法は本発明の実施形態群に包摂されうる。本発明の他の実施形態においては、ホップ数h、経路品質重みｄ、リンク間到達重みｗ、受信信号強度、
もしくはその他の当該技術分野にて適切と考えられる任意のパラメータ、のうちの少なくとも一種を使って、適切に評価値Eを導出することができる。例えば、E = d+h+5w+20/r
という式を使って評価値Eを算出してもよい（ここでdは経路品質重み、hはホップ数、wは
リンク間到達重み、rは最新のハローフレームを受信した際の受信信号（電力）強度であ
る）。
【０１４３】
更に、上記リンク間到達重みｗを定義し、データ転送が失敗した場合にはｗ＝ｗ＋１、成功した場合にはｗ＝ｗ−１（例えば、０を最小値とする）とし、ｗを上記（３）式のようにすることで、データ転送時の隣接ノードの微調整を行うことができる。
【０１４４】
このように、本実施形態に係るノード装置１もしくは１ａは、他のノード装置からのハローフレームの受信状況に基づき、ネットワークの状態を監視することができる。
【０１４５】
図１６から図２１は、本発明の実施形態に係るノード装置のハローフレーム受信時の処理を示した詳細なフローチャートである。以下、これらの図にわたってフローを説明してゆく。以下に本発明の実施形態に係るノード装置の処理をおおまかに述べる。
(i) ステップＳ１６００からＳ１６１４にて隣接ノード管理テーブルの更新を行う。
(ii) ステップＳ１７００からＳ１７１０’にて、ハローフレームのハローヘッダを用い
てハローヘッダのGDごとに、自ノード装置の持つ重み付けテーブルに登録しているハローフレームの送信元（LS）の評価値の更新を行う。
(iii) ステップＳ１８５０からＳ１７００’にて、GDがハロー送信元（LS）である自ノード装置の持つ重み付けテーブルの評価値の更新を行う。
(iv) ステップＳ２０００からＳ２０１０’にて、自ノード装置の持つ重み付けテーブル
にハローフレームの送信元（LS）が登録されていない場合に新たに登録し、自ノード装置の持つ重み付けテーブルにハローヘッダのGDが登録されていない場合に新たに登録する。
【０１４６】
この実施形態にかかるフローはまず、図１６にて、視点を置くノード装置（自ノード装置）にハローフレームが受信されたところから始まる。
【０１４７】
ステップＳ１６００からＳ１６１４では、ハロー（HELLO）フレームの送信元（LS）に
対応する隣接ノード管理テーブルのレコードにおける重みに関する情報を更新する。
【０１４８】
ステップＳ１６００では、ハローフレームを受けとったノード装置が、そのノード装置が有する隣接ノード管理テーブル中にハローフレームの送信元（LS）のノード装置に該当するレコードが存在するかどうかを確認するために検索を行う。この検索に際しては、このLSからの前回のハローフレーム受信時刻および今回のハローフレーム受信時刻とを比較する。こうすることで、受信時刻の逆転が起こっていないかを確認してLSの"なりすまし"（つまり、LSを偽って送られているフレーム）が無いかを判断することも可能となる。
【０１４９】
ステップＳ１６０２にて、検索によりハローフレームの送信元（LS）が隣接ノード管理テーブル内に無いことがわかったならば、フローはステップＳ１６０４へ進む。そして、隣接ノード管理テーブルにLSを新規に追加し、復路リンク重みの初期値を設定する。ステップＳ１６０２にて、検索によりハローフレームの送信元（LS）が隣接ノード管理テーブル内に在ることがわかったならば、フローはステップＳ１６０６へ進む。そして、隣接ノード管理テーブル中でのLSに該当するレコードにて、復路リンク重みの値を更新する。
【０１５０】
その後のステップＳ１６０８では、ハローフレーム内のハローヘッダに、自ノード装置の情報（IDなど）が含まれているかという検索を行う。このときに、LSの持つノード間のリンク品質情報（すなわち、LSからの復路リンク重み）を参照する。そしてステップＳ１６１０にて自ノード装置の情報が存在することがわかった場合に、フローはステップＳ１６１２に進み、隣接ノード装置に関する往路リンク重みの計算を行う。
【０１５１】
その後のステップＳ１６１４では、隣接ノード装置に関する双方向リンク重みを算出す
る。そして図１７の記号(I)へ進む。
【０１５２】
図１７のステップＳ１７００では、まず自ノード装置が有する重み付けテーブルのレコード一個ごとについてのくりかえし処理（ループ処理）を開始する。そしてステップＳ１７１０でさらに、ハローフレームに含まれるハローヘッダ一個ごとのくりかえし処理をネストする。
【０１５３】
ステップＳ１７１２では、重み付けテーブルのGDと、ハローフレーム内のハローヘッダのGD（つまり、本来はハローフレームの送信元（LS）が持つ重み付けテーブルに含まれていたもの）が一致するかを判定する。
【０１５４】
ステップＳ１７１４にて重み付けテーブルのGDとハローヘッダのGDとが一致しなかったら、フローは図１７の記号(IV)へ飛び、ステップＳ１７１０’にて1つのくりかえしサイ
クルを了える。ステップＳ１７１４にて重み付けテーブルのGDとハローヘッダのGDとが一致したら、フローはステップＳ１７１６に進む。
【０１５５】
ステップＳ１７１６では、ハローフレームの送信元（LS）に対応する重み付けテーブルに、自ノード装置がフレームを送る宛先となるLD候補が存在するかを検索する。
【０１５６】
ステップＳ１７１８にて、宛先となるLD候補（宛先LD候補）が存在したら、ステップＳ１７２０にて重み付けテーブル中のその宛先LD候補についてのレコードで、ホップ数hを
、ハローヘッダのホップ数+1として更新する。そしてステップＳ１７２２で、このハローフレームに関する経路品質重みdを算出し、宛先LD候補に関する経路品質重みdを更新する。なおここでいうハローフレームに関する経路品質重みdとは例えば、ハローフレームの
送信元から観た経路品質重みと、ハローフレームの受信周期の分散から得られる復路品質重みとから算出される経路全体（もしくは経路全体の少なくとも一部分）での双方向リンク重みを、加算または何らかの演算を施した値が、すなわち経路品質重みとなる。これは要するに、或るノード装置において、受信したハローフレームに関する経路品質重みdを
、重み付けテーブルの経路品質重みdに加えられ、そうして得られた更新された経路品質
重みdが、今度は送信されるハローフレームに収められた経路品質重みとなって、次のノ
ード装置へと送信される、ということである。端的にいえば、ハローヘッダごとの双方向リンク重みの積算が、重み付けテーブルの経路品質重みdとなると考えてもよい。この実
施形態においては、一連のくりかえし処理Ｓ１７１０〜Ｓ１７１０’またはくりかえし処理Ｓ１７００〜Ｓ１７００’のあいだに得られる各々の双方向リンク重みを積算して、くりかえし処理の対象となっていた重み付けテーブルの経路品質重みdを算出できる。さて
それから図１８の記号(II)へフローを進める。
【０１５７】
ステップＳ１８２４では、宛先LD候補に関する受信電力（なお、図１５では受信電力についてのフィールドは示していない）を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１８２６では、このハローフレームに関する評価値Eを上述し
たように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１８２
８にて、宛先LD候補に関するエージングカウンタ（重み付けテーブルの有効期間を設定するための手段）をリセットする。そしてフローはステップＳ１８４０に進み、宛先LD候補を評価値の順にソートして、優先度的に好ましい候補を絞りこむようにできる。そしてステップＳ１７１０’にて1つのくりかえしサイクルが完了する。
【０１５８】
一方、ステップＳ１７１８にて、宛先となるLD候補が存在しなかった場合には、まずそのハローフレームの送信元（LS）を、重み付けテーブルに宛先となるLD候補として新規に登録をし、フローはステップＳ１７３０に進む。ステップＳ１７３０にてその新たな宛先LD候補についてのレコードで、ホップ数hを、ハローヘッダのホップ数+1として更新する
。そしてステップＳ１７３２で、このハローフレームに関する経路品質重みdを算出し、
宛先LD候補に関する経路品質重みdを更新する。それから図１８の記号(III)へフローを進める。ステップＳ１８３４では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１８３６では、このハローフレームに関する評価値Eを上述したように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１８３８にて、宛先LD候補に関するエージングカウンタをリセットする。そしてフローはステップＳ１８４０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７１０’にて1つのくりかえしサイクルが完了する。
【０１５９】
くりかえし処理Ｓ１７１０〜Ｓ１７１０’が一通り完了したところで、フローはステップＳ１８５０へ進む。
【０１６０】
ステップＳ１８５０では、くりかえし処理Ｓ１７１０〜Ｓ１７１０’における処理にてハローヘッダを用いた宛先LD候補の更新があったか、すなわちステップＳ１７１４からＳ１７１６へ一度でも進んだかどうかを確認する。更新があった場合には、フローは図１９の記号(VII)へ飛び、ステップＳ１７００’にて1つのくりかえしサイクルを了える。更新が無かった場合には、フローはステップＳ１８５２へ進む。ステップＳ１８５２では、ハローフレームの送信元であるノード装置（LS）にあたる値が、（図１５に示したような）重み付けテーブルのGDにあたるかどうかを判定する。この実施形態ではこのようにして、ルーティングの評価を行っている。
【０１６１】
ハローフレームの送信元であるノード装置（LS）が、重み付けテーブルのGDと一致しなかった場合には、フローは図１９の記号(VI)へ飛び、ステップＳ１９３０で宛先LD候補を評価値順にソートする。そしてステップＳ１７００’にて1つのくりかえしサイクルを了
える。
【０１６２】
ハローフレームの送信元であるノード装置（LS）が、重み付けテーブルのGDと一致した場合には、フローはステップＳ１８５４へ進む。そして、ハローフレームの送信元（LS）に対応する重み付けテーブルに、隣接ノードの候補が存在するかどうかを検索する。そして図１９の記号(V)を挟んでステップＳ１９００にて、宛先LD候補が有る場合にはフロー
はステップＳ１９１０へ進む。ステップＳ１９１０では、このハローフレームに関する経路品質重みdを計算して、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ１９１２では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１９１４では、このハローフレームに関する評価値Eを
上述したように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ
１９１６にて、宛先LD候補に関するエージングカウンタをリセットする。なお紙幅の関係で省略したが、宛先LD候補が複数存在する場合にはステップＳ１９１０からステップＳ１９１６をその個数分くりかえすこともできる。そしてフローはステップＳ１９３０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７００’にて1つのくりかえしサイ
クルが完了する。
【０１６３】
一方、ステップＳ１９００にて宛先LD候補が無い場合にはフローはステップＳ１９２０へ進む。ステップＳ１９２０では、新たな宛先LD候補のホップ数を初期値（ここでは1）
に設定する。ステップＳ１９２２では、宛先LD候補のリンク間到達重みwに初期値（例え
ば0.5）を設定する。ステップＳ１９２４では、このハローフレームに関する経路品質重
みdを計算して、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ１９２６では、宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ１９２８では、このハローフレームに関する評価値Eを上述した
ように算出して、宛先LD候補に関する評価値Eを更新する。それからステップＳ１９２９
にて、宛先LD候補に関するエージングカウンタをリセットする。そしてフローはステップ
Ｓ１９３０に進み、宛先LD候補を評価値の順にソートし、ステップＳ１７００’にて1つ
のくりかえしサイクルが完了する。
【０１６４】
くりかえし処理Ｓ１７００〜Ｓ１７００’が一通り完了したところで、フローは記号(VIII)を挟んで図２０のステップＳ２０００へ進む。
【０１６５】
ステップＳ２０００では、ハローフレームの送信元であるノード装置（LS）に対応する（そのLSがGDとなっている）エントリが、自ノード装置の持つ重み付けテーブル（群）のうちに存在するかどうかを確認する。重み付けテーブルに該当エントリが存在した場合には、フローはステップＳ２０１０へ飛ぶ。重み付けテーブルに該当エントリが存在しなかった場合には、フローはステップＳ２００１へ進む。
【０１６６】
ステップＳ２００１では、そのLSをGDとした新たな重み付けテーブルを作成する。ステップＳ２００２では、新たな宛先LD候補のホップ数を初期値（ここでは1）に設定する。
ステップＳ２００３では、宛先LD候補のリンク間到達重みwに初期値（例えば0.5）を設定する。ステップＳ２００４では、このハローフレームに関する経路品質重みdを計算して
、その宛先LD候補に関する経路品質重みdを更新する。ステップＳ２００５では、宛先LD
候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ２００６では、このハローフレームに関する評価値Eを上述したように算出し
て、宛先LD候補に関する評価値Eを更新する。それからステップＳ２００７にて、宛先LD
候補に関するエージングカウンタをリセットする。それからフローはステップＳ２０１０に進む。
【０１６７】
ステップＳ２０１０では、ハローフレームに含まれるハローヘッダ一個ごとのくりかえし処理を開始する。
【０１６８】
記号(IX)を挟んで図２１のステップＳ２１００では、ハローヘッダのGDが、自ノード装置の持つ重み付けテーブルに存在するかどうかを確認する。重み付けテーブルに該当エントリが存在した場合には、フローはステップＳ２０１０’へ飛び、1つのくりかえしサイ
クルが完了する。重み付けテーブルに該当エントリが存在しなかった場合には、フローはステップＳ２１０１へ進む。
【０１６９】
ステップＳ２１０１では、そのハローヘッダのGDに対応した新たな重み付けテーブルを作成するとともに、そのテーブルに、ハローフレームの持つアドホックヘッダのLSをフィールドLDの値として持つようなエントリを作成する。ステップＳ２１０２では、新たな宛先LD候補のホップ数hを、ハローヘッダのホップ数+1として設定する。ステップＳ２１０
３では、宛先LD候補のリンク間到達重みwに初期値（例えば0.5）を設定する。ステップＳ２１０４では、このハローヘッダに関する経路品質重みdを使って経路品質重みdを再計算して、その宛先LD候補に関する経路品質重みdを初期化する。ステップＳ２１０５では、
宛先LD候補に関する受信電力を、このハローフレームを受信した際の受信電力として更新する。ステップＳ２１０６では、このハローヘッダに関する評価値Eを算出して、宛先LD
候補に関する評価値Eを更新する。それからステップＳ２１０７にて、宛先LD候補に関す
るエージングカウンタをリセットする。それからフローはステップＳ２０１０’に進み、1つのくりかえしサイクルが完了する。
【０１７０】
そしてくりかえし処理Ｓ２０１０〜Ｓ２０１０’が一通り完了すると、一連のフローは終了する。
【０１７１】
図２２は、ハローフレームの交換シーケンスを示す図である。各ノード装置は、ハローフレームを近隣のノード装置に向けてブロードキャスト送信する。ハローフレームには、
各ノードまでの経路の中で最適と判定されたリンク情報が含まれている。各ノード装置は、ハローフレームを受信すると、保有する隣接ノード管理テーブル６もしくは６ａおよび重み付けテーブル７もしくは７ａと比較して、各ノード装置についての重みに関する情報の作成及び更新を行っていく。また、隣接ノード管理テーブル６もしくは６ａを参照して、ハローフレームのリンク情報の更新を行う。この動作を各ノード装置が複数回繰り返すことで、ノード装置は、他のノード装置のそれぞれまでのルーティングを可能とするリンク先情報を複数個持つことが可能となる。
【０１７２】
或る実施形態においては、ノード装置１もしくは１ａが、特定のノード装置からそれまで受信できていたハローフレームを所定の期間内（例えば３０分以内）に受信できなくなった場合に、その特定のノード装置を、通信不能状態にあると見做して、その旨をゲートウェイ装置に通知することができる。また、受信したハローフレームの内容から判断を行ったうえで、異常が検出されればその旨をゲートウェイ装置へ通知することもできる。更には、隣接ノード管理テーブル６もしくは６ａを参照して、あるノード装置について異常が検出された場合には、上記重み付けテーブル７もしくは７ａの対応する重みを更新して、そのノード装置についての優先度を低くしてもよい。
【０１７３】
更に或る実施形態では、図２２に示すとおり、ゲートウェイ装置との間でハローフレームを送受することにより、ゲートウェイ装置の死活監視を行うこともできる。
【０１７４】
ノード装置間での状態監視については、所定の時間内に相手のノード装置からハローフレームを受信しない場合には、相手のノード装置に対してハローフレーム発生要求を送信し、相手のノード装置からハローフレームを受信するか否かにより、相手のノード装置の状態を監視するような構造をとってもよい。
【０１７５】
或る実施形態では、上記のようにして各ノード装置においてネットワークを監視し、ハローフレームにそのハローフレームが通過した経路上のノード装置についての情報を付加してゆき、さらにサーバで集計することにより、ネットワークの監視を行うこともできる。
【０１７６】
本発明の実施形態に応じて、ハローフレームを用いて各ノード装置がネットワークの監視を行うことで、ネットワーク監視用のフレームを別途流通させる必要がなく、流通フレーム数を抑制することができる。また、隣接ノード装置とで送受するハローフレームを用いてネットワーク監視を行うことにより、センターからネットワーク監視用のフレームを送信してその応答により状態を監視する場合と比較して、ターンアラウンドを小さく抑えたリアルタイムに近い監視が可能となる。
【０１７７】
図２３は、本発明の実施形態にかかるノード装置もしくはプログラムを実施可能なハードウェアを示す概要図である。
【０１７８】
図２３にはまず、各種計算処理を担うマイクロプロセッサユニット（MPU）２３００が
示されている。マイクロプロセッサユニット２３００は、有線物理層処理部（PHY）２３
１２とMII（Media Independent Interface）/MDIO（Management Data Input/Output）イ
ンターフェイス２３１０を介して通信可能に接続されている（なお"MII/MDIO"とは、「MIIまたはMDIO」を意味する）。MIIとMDIOはいずれも、物理層とMAC副層（Media Access Control sublayer）との間のインターフェイスである。
またマイクロプロセッサ２３００は、時刻の計測などを担うタイマIC２３２２と、I2C（Inter-Integrated Circuit）/PIO（Parallel Input/Output）バス２３２０を介して通信可能に接続されている（なお"I2C/PIO"とは、「I2CまたはPIO」を意味する）。さらにマイ
クロプロセッサ２３００は、記憶手段であるダイナミックランダムアクセスメモリ（DRAM
）２３３２およびフラッシュメモリ２３３４、ならびにネットワークインターフェイスである無線LAN処理部２３３６と、PCI（Peripheral Component Interconnect）バス２３３
０を介して通信可能に接続されている。当然のことながら、当該技術分野の常識に照らし、ここに例示した規格・種類以外の装置を適宜使用してもかまわない。
【０１７９】
MPU２３００は、不揮発性記憶装置の一種であるフラッシュメモリ２３３４上に格納さ
れたファームウェアなどの種々のプログラムを、DRAM２３３２上にロードして実行することで、様々な処理を実行できる。MPU２３００は例えば、上述した各種処理をノード装置
１に実行させるためのファームウェアプログラムなど、種々のプログラムを実行できる。
【０１８０】
なお、DRAM２３３２は、フレームの送信バッファ及び受信バッファとしても使用可能である。フラッシュメモリ２３３４は、上述したようにファームウェアプログラムなどを格納できる。また、フラッシュメモリ２３３４には、ノード装置１もしくは１ａ自身に固有の情報（例えば、ノードＩＤやＭＡＣアドレス）も格納できる。
【０１８１】
有線PHY処理部２３１２は、有線接続における物理層の処理を行う回路である。また、
無線LAN処理部２３３６は、無線ＬＡＮ接続における物理層の処理を行うハードウェアで
ある。無線LAN処理部２３３６は、例えばアンテナ、ＡＤＣ（Analog-to-Digital Converter）、ＤＡＣ（Digital-to-Analog Converter）、変調器、復調器などを含むことができ
、物理層とＭＡＣ副層の処理を行う。したがって、本実施形態では、ノード装置１もしくは１ａが、有線通信と無線通信の双方を行うことができる。当然ながらノード装置１もしくは１ａが、有線通信又は無線通信の一方のみを行う実施形態も可能である。
【０１８２】
タイマIC２３２２は、設定された時間が経過するまでカウントアップ動作を行い、設定された時間が経過すると割り込み信号を出力する回路である。
【０１８３】
なお、上記の実施形態においては、ノード装置について主に説明したが、上記の方法をコンピュータに実行させる制御プログラムも、本発明の実施形態の一例に含まれる。当該制御プログラムは、磁気ディスク、光磁気ディスク、不揮発性の半導体メモリ、光ディスクなどの、コンピュータ読み取り可能な記憶媒体に格納されて提供され、コンピュータにロードされ、コンピュータにより実行されてもよい。
【０１８４】
当該制御プログラムを実行するコンピュータは、不図示のノード装置に内蔵又は接続され、上記不図示のノード装置が上記実施形態のノード装置１もしくは１ａと同様に動作するように、当該制御プログラムにしたがって上記不図示のノード装置を制御する。例えば、上記実施形態を別の観点から見れば、ノード装置１もしくは１ａの内蔵コンピュータであるＭＰＵ２３００は、フラッシュメモリ２３３４に格納された制御プログラムにしたがってノード装置１もしくは１ａを制御し、上記各処理をノード装置１もしくは１ａに行わせている、とも見做せる。
【０１８５】
以上説明したように、上記の実施形態に係るノード装置によれば、大規模の通信ネットワークに適用する場合であっても、各ノード装置が隣接ノード装置から受信した情報により経路の最適化を行うことやネットワークの監視を行うことが可能となる。
【０１８６】
また、本実施形態では各種のデータについて、理解しやすいようにテーブル形式の例を開示したが、この例に限らず、データを対応付けて管理可能なＸＭＬやツリー構造など他の管理形式を採用してもよい。
【特許請求の範囲】
【請求項１】
複数のノード装置を含んだネットワークの中の、ノード装置において、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信する、フレーム受信手段と、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを格納する、記憶手段と、
前記テーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定める、優先度判定手段と、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、フレーム送信手段と
を含むことを特徴とするノード装置。
【請求項２】
前記フレーム受信手段が受信した、前記ひとつ以上の相手ノードから前記自ノードに宛てて送信されたハローフレームに基づいて、前記優先度判定手段が前記評価値を定め、
前記ひとつ以上の相手ノードのいずれかから前記自ノードに宛てて送られたデータフレームを、前記フレーム受信手段が受信し、
前記フレーム送信手段が、前記評価値を用いて、前記データフレームを前記ひとつ以上の相手ノードのうちの適切なノードへ送信する
ことを特徴とする、請求項１記載のノード装置。
【請求項３】
複数のノード装置を含んだネットワークの中の、ノード装置が実行する方法おいて、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信し、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを記憶手段に格納し、
前記記憶手段に格納されたテーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定め、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、
処理を含むことを特徴とする、ノード装置が実行する方法。
【請求項４】
複数のノード装置を含むネットワークの中の、ノード装置であるコンピュータに実行させるためのプログラムであって、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信し、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを記憶手段に格納し、
前記記憶手段に格納されたテーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定め、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、
処理をコンピュータに実行させるためのプログラム。
【請求項１】
複数のノード装置を含んだネットワークの中の、ノード装置において、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信する、フレーム受信手段と、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを格納する、記憶手段と、
前記テーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定める、優先度判定手段と、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、フレーム送信手段と
を含むことを特徴とするノード装置。
【請求項２】
前記フレーム受信手段が受信した、前記ひとつ以上の相手ノードから前記自ノードに宛てて送信されたハローフレームに基づいて、前記優先度判定手段が前記評価値を定め、
前記ひとつ以上の相手ノードのいずれかから前記自ノードに宛てて送られたデータフレームを、前記フレーム受信手段が受信し、
前記フレーム送信手段が、前記評価値を用いて、前記データフレームを前記ひとつ以上の相手ノードのうちの適切なノードへ送信する
ことを特徴とする、請求項１記載のノード装置。
【請求項３】
複数のノード装置を含んだネットワークの中の、ノード装置が実行する方法おいて、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信し、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを記憶手段に格納し、
前記記憶手段に格納されたテーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定め、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、
処理を含むことを特徴とする、ノード装置が実行する方法。
【請求項４】
複数のノード装置を含むネットワークの中の、ノード装置であるコンピュータに実行させるためのプログラムであって、
ひとつ以上の相手ノードから自ノードに宛てて送信されたフレームを受信し、
前記自ノードから前記ひとつ以上の相手ノードの各々へと送信するフレームの通信品質に関する、第一の情報、
前記ひとつ以上の相手ノードの各々から前記自ノードへと送信されるフレームの通信品質に関する、第二の情報、および
前記第一の情報と前記第二の情報とから算出される、双方向の通信品質に関する第三の情報を含んだテーブルを記憶手段に格納し、
前記記憶手段に格納されたテーブルに基づいて、前記ひとつ以上の相手ノードの各々に関する優先度を示す評価値を定め、
前記評価値を用いて、前記ひとつ以上の相手ノードのうちのもっとも優先度の高いノードへフレームを送信する、
処理をコンピュータに実行させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１３−８５２９５（Ｐ２０１３−８５２９５Ａ）
【公開日】平成２５年５月９日（２０１３．５．９）
【国際特許分類】
【出願番号】特願２０１３−６５４３（Ｐ２０１３−６５４３）
【出願日】平成２５年１月１７日（２０１３．１．１７）
【分割の表示】特願２０１１−２３２２３１（Ｐ２０１１−２３２２３１）の分割
【原出願日】平成２１年４月２７日（２００９．４．２７）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年５月９日（２０１３．５．９）
【国際特許分類】
【出願日】平成２５年１月１７日（２０１３．１．１７）
【分割の表示】特願２０１１−２３２２３１（Ｐ２０１１−２３２２３１）の分割
【原出願日】平成２１年４月２７日（２００９．４．２７）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]