(57)【要約】複数のネットワークノードを有する有線又は無線ネットワークのバウンダリスキャンテストを提供するシステムと方法を提示する。本システムは、ネットワークに通信可能に接続されるテストステーションを含む。テストステーションは、ネットワーク内の各リンクを含みかつネットワークに使用されるルーティング機構及びプロトコルとは独立なＭＡＣ層のスキャンテストルートシーケンスを生成し、このシーケンスの各リンクを探索するように構成されるテストエージェントを生成する。テストエージェントがネットワーク上で展開され、テストエージェントがリンクを調べた後にリンク情報がテストステーションへ報告される。スキャンテストルートシーケンスは、一連のブロードキャストメッセージをネットワークの１つ又は複数のノードから送信し、ネットワーク全体に対してネットワーク巡回路を逐次に適用するか又は深さ優先サーチを実行することにより生成される。【特許請求の範囲】
【請求項１】
複数のネットワーク装置を通信可能であるように接続するネットワーク内のリンクを試験するための方法であって、
通信ネットワーク内の各リンクを含むＭＡＣ層のスキャンテストルートシーケンスを確立することと、
上記スキャンテストルートシーケンスにおける各リンクを探索するように構成されるテストエージェントを生成することと、
上記テストエージェントを上記通信ネットワーク上へ配備することとを含み、上記テストエージェントは上記スキャンテストルートシーケンス内のリンクを調べて上記リンクに関する情報を決定する方法。
【請求項２】
上記確立するステップは、上記通信ネットワーク内の複数のネットワーク装置の各々から一連のブロードキャストメッセージを送信することを含む請求項１記載の方法。
【請求項３】
上記確立するステップは、ネットワーク巡回路の逐次的な適用を含む請求項１記載の方法。
【請求項４】
上記ネットワーク巡回路は郵便配達人巡回路である請求項３記載の方法。
【請求項５】
上記確立するステップは、上記通信ネットワークの深さ優先サーチを実行することを含む請求項１記載の方法。
【請求項６】
上記実行するステップは、上記通信ネットワーク内の各ネットワーク装置においてスキャンチェーンテーブルを構成することを含む請求項５記載の方法。
【請求項７】
上記実行するステップは、ホップカウントに基づいて正規アドレッシングスキームを生成することを含む請求項５記載の方法。
【請求項８】
上記テストエージェントは、上記スキャンテストルートシーケンス内の各リンクを調べて、上記通信ネットワークに関する情報を決定する請求項１記載の方法。
【請求項９】
上記テストエージェントは上記リンク情報をテストステーションへ報告する請求項１記載の方法。
【請求項１０】
複数のテストエージェントを生成することと、
上記複数のテストエージェントの各々を上記通信ネットワーク上へ配備することとをさらに含む請求項１記載の方法。
【請求項１１】
上記複数のテストエージェントはリンク情報を単一のテストステーションへ報告する請求項１０記載の方法。
【請求項１２】
上記テストエージェントは、１つ又は複数の通信パケットのデータペイロードにおける伝送用に構成される抽象データ型である請求項１記載の方法。
【請求項１３】
上記テストエージェントは、リンク上で実行されるテストのタイプを識別するテストタイプ指示子を備える請求項１２記載の方法。
【請求項１４】
上記テストエージェントはソースルート情報を備えた請求項１２記載の方法。
【請求項１５】
上記テストエージェントは中間リンク情報の結果を備えた請求項１２記載の方法。
【請求項１６】
上記テストエージェントは、リンクの調査に関連して解析されるリンク属性を備えた請求項１２記載の方法。
【請求項１７】
上記リンク属性はリンクの接続状態である請求項１６記載の方法。
【請求項１８】
上記リンク属性はネットワーク装置のルーティング構成である請求項１６記載の方法。
【請求項１９】
上記テストエージェントは、リンクの調査に関連して実行される実行可能な命令を備えた請求項１２記載の方法。
【請求項２０】
上記実行可能な命令は、リンクを調査する際に上記テストエージェントによって実行されるテストを変更する請求項１９記載の方法。
【請求項２１】
上記実行可能な命令は、上記複数のネットワーク装置の部分集合において呼び出される請求項１９記載の方法。
【請求項２２】
複数のネットワーク装置を通信可能であるように接続するネットワーク内のリンクを試験するためのシステムであって、
ネットワーク通信手段及びメモリを有し、ネットワークを介して複数のネットワーク装置と通信可能であるように接続されたテストステーションと、
上記ネットワーク内の各リンクを含むスキャンテストルートシーケンスと、
上記スキャンテストルートシーケンス内のリンクを調べて上記リンクに関する情報を決定するように構成されたテストエージェントとを備えたシステム。
【請求項２３】
上記通信手段は無線送受信機である請求項２２記載のシステム。
【請求項２４】
上記テストエージェントは上記テストステーションによって生成される請求項２２記載のシステム。
【請求項２５】
上記テストエージェントはさらに、上記リンク情報をテストステーションへ報告するように構成される請求項２２記載のシステム。
【請求項２６】
上記テストエージェントはさらに、上記スキャンテストルートシーケンス内の各リンクを調べて、上記通信ネットワークに関する情報を決定するように構成される請求項２２記載のシステム。
【請求項２７】
上記テストエージェントは、１つ又は複数の通信パケットのデータペイロードにおける伝送用に構成される抽象データ型である請求項２２記載のシステム。
【請求項２８】
上記テストエージェントは、リンク上で実行されるテストのタイプを識別するテストタイプ指示子を備えた請求項２２記載のシステム。
【請求項２９】
上記テストエージェントはソースルート情報を備えた請求項２２記載のシステム。
【請求項３０】
上記テストエージェントは中間リンク情報の結果を備えた請求項２２記載のシステム。
【請求項３１】
上記テストエージェントは、リンクの調査に関連して解析されるリンク属性を備えた請求項２２記載のシステム。
【請求項３２】
上記リンク属性はリンクの接続状態である請求項３１記載のシステム。
【請求項３３】
上記リンク属性はネットワーク装置のルーティング構成である請求項３１記載のシステム。
【請求項３４】
上記テストエージェントは、リンクの調査に関連して実行される実行可能な命令を備えた請求項２２記載のシステム。
【請求項３５】
上記実行可能な命令は、リンクを調査する際に上記テストエージェントによって実行されるテストを変更する請求項３４記載のシステム。
【請求項３６】
上記実行可能な命令は、上記複数のネットワーク装置の部分集合において呼び出される請求項３４記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に通信ネットワークにおけるディジタルデータ伝送に関し、より特定的には、有線又は無線ネットワークに対してバウンダリスキャンテスト又はロービングリンクテスト（roving link test）を実行するための機構に関する。
【背景技術】
【０００２】
今日のネットワークではエラーの発生頻度が非常に高く、その配備と診断と修理とが困難である。ネットワークに障害が発生すると、問題のあるスポットの位置を特定する作業は困難でありかつ労力のかかるものである。例えば、ルーティングテーブルが使用されるシステムでは、障害が発生すればルーティングテーブルにおける情報はもはや有効ではない。エラーを報告すること、所定の障害の位置を特定すること、及びネットワーク性能をモニタリングすることのためには、インターネット制御メッセージプロトコル（internet control message protocol：「ＩＣＭＰ」）又は類似タイプのプロトコルを使用可能である。しかしながら、自己組織化する有線又は無線パケットネットワークにおける重大な欠点は、可能なすべての代替ルートを試験すること、すなわち、現行で利用されていないが、既存のルートが不満足な信号伝送又は完全な障害を有すると必要になる可能性のあるルートを試験することができないことにある。
【０００３】
バウンダリスキャンをサポートする装置は、ＩＥＥＥ  １１４９．１規格のジョイントテストアクショングループ（joint test action group：「ＪＴＡＧ」）がバックプレーンバスとして使用されることを許容し、このバックプレーンバスが、バックプレーン相互接続試験の可能性を開きまたマルチドロップアーキテクチャを利用可能にし、システム統合化及びフィールドサービスのシナリオにおけるバックプレーン−ボード−チップの診断を可能にする。例えば、あるＩＣチップのすべてのメモリ構成要素は長いシフトレジスタ内において最小オーバーヘッドで接続されることが可能であり、次いでチップ上の汎用シリアルポートを用いて任意のテストベクトルがチップの中へ、またチップの外へシフトされる。これらのテストベクトルは、チップ全体を機能試験し、次いで結果を動作中のチップと比較して正しさを検証することを可能にする。今日、複合型チップはすべてＪＴＡＧ対応インターフェースを介して試験され、この技術はマイクロプロセッサのハードウェアデバッグを実施することにも使用される。
【０００４】
さらに、システム構成規格におけるＩＥＥＥ  １５３２−２０００の開発は、コンプレックス・プログラマブル・ロジック・デバイス（complex programmable logic device：「ＣＰＬＤ」）及びフィールド・プログラマブル・ゲート・アレイ（field programmable gate array：「ＦＰＧＡ」）のそのままの状態（in situ）でのプログラミングを可能にするＩＥＥＥ  １１４９．１構成をてこ入れしている。今日のＩＥＥＥ  １１４９．１規格はディジタルエレクトロニクスに限定され、一般にＪＴＡＧ機能を有するチップのみを対象とする。しかしながら数年のうちには、混合信号のテストバスのためのＩＥＥＥ  １１４９．１規格により、アナログ回路のテストも可能になるであろう。
【０００５】
グラフ理論は、複数のエンティティ（ノードと呼ぶ。）と、ノード間の複数の接続（リンクと呼ぶ。）とを扱う数学の一分野である。重要な探索問題は、与えられたグラフにおいて、各辺をただ１度だけ通りかつ起点ノードで終わる巡回路（ツアー）を発見することにある。このような巡回路は、オイラー巡回路と呼ばれる。オイラー巡回路は、すべてのノードが、それに接続された偶数個のリンクを有する場合にのみ存在可能である。このことは、偶数次数を有していると呼ばれる。
【０００６】
すべてのグラフにオイラー巡回路が存在するわけではないので、各リンクを少なくとも一度は通る最小長さの巡回路を決定することが共通の問題となる。この問題は、郵便配達人問題（postman problem）として知られる。グラフに重複リンクを追加するために、グラフのオイラー化（Eulerization）と呼ばれる処理が使用される。これらの重複リンクは、接続された偶数個のリンクをこれらがグラフ内の各ノードに提供するように追加される。田舎の郵便配達人問題として知られる、郵便配達人問題の一般化は、グラフ内の複数のリンクのうちの特定の部分集合に対して、最小コストの探索を決定することである。無向グラフ又は有向グラフに係る田舎の郵便配達人巡回路は多項式時間で計算可能であるが、混合グラフ（すなわち、無向リンク及び有向リンクを有するグラフ）に係る田舎の郵便配達人巡回路はＮＰ困難である。簡単な解法は、所定の探索コストを示す辺によって偶数次数の部分グラフのすべてを置き換え、次に奇数次数の頂点上での最小マッチングを計算することである。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
近年、田舎の郵便配達人巡回路アルゴリズムを使用するネットワークプロトコル適合試験が作成された。この技術では、２つの決定性有限状態マシンを用いてプロトコルの仕様及びプロトコルの実装が各々モデル化される。こうしてこの試験は、テストシーケンスの全長を最小化することに焦点を合わせながら、２つの状態マシンによる探索の結果を比較する。郵便配達人巡回路技術はまた同様に、ネットワークのルーティングテーブルに基づいてネットワークの全リンクを探索することにも使用可能である。しかしながら、経時的に変化するネットワーク内の信号送受信条件は、静的に構成される田舎の郵便配達人巡回路を、実行時間中には不完全なものにすることが多い。従って、当該技術分野には、有線又は無線ネットワークのリンク状態をリアルタイムで試験するための頑健な方法が存在せず、未だ満たされていない解決方法に対するニーズが生じている。
【課題を解決するための手段】
【０００８】
従って、本明細書に開示する方法及びアルゴリズムは、通信ネットワークを介して通信するための手段をそれぞれ有する複数のネットワーク装置（本明細書では「ネットワークノード」、「ノード」又は「ネットワークステーション」とも呼ぶ。）を含む通信ネットワークに適用される。ネットワークプロトコル及びルーティング通信に使用される既存のルーティング機構及びプロトコルとは独立して、スキャンテストルートシーケンス（scan test route sequence）が構築される。これは、試験対象であるネットワーク内の個々のノードによる複数のブロードキャスト動作にてなるシーケンスによって達成される。あるいは、スキャンテストルートシーケンスは、田舎の郵便配達人巡回路（rural postman tour：「ＲＰＴ」）アルゴリズムを逐次に適用することによって構築されることが可能である。ＲＰＴアルゴリズムを逐次に使用することは、ネットワークをあふれさせる可能性のあるブロードキャスト動作を回避する。別の装置では、ネットワーク内の各ノードにスキャンチェーンテーブルを構築することにより、テストステーションから深さ優先サーチ（depth first search：「ＤＦＳ」）アルゴリズムを用いてネットワーク構成がサーチされるように、スキャンテストルートシーケンスはオンラインで計算される。
【０００９】
スキャンテストルートシーケンスが確立されると、ルートシーケンス内の各リンクを探索するためにロービングテストエージェントが展開される。ロービングテストエージェントは、ネットワーク上で１つ又は複数の通信パケットのデータペイロードで伝送される抽象データ型である。ロービングテストエージェントは、ソースルート情報と、試験対象である属性と、中間結果とを含んでいてもよい。またロービングテストエージェントは、エージェントにより既に実行されている試験を実行したり又は変更したりするために、各ネットワークノード又は選択されたネットワークノードにおいて呼び出されることが可能な、実行可能なコードを含んでいてもよい。試験対象である属性は、リンク接続性、ノードルーティング（nodal routing）構成、又は関心の持たれた他の属性であることが可能である。
【発明の効果】
【００１０】
本発明が従来のアプローチを凌ぐ多くの重要な優位点を提供することは、以下の説明から明らかであろう。本発明は、ネットワークプロトコル層又は対応する確立されたルーティングテーブルに依存することなく、有線又は無線ネットワークのトラブルシューティングを自動的に実行するための、より下位層の機構を提供する。さらには、通常のルーティングシステムをバイパスすることにより、本発明は、有利なことには、障害がある可能性のあるルーティングテーブルへの循環的な依存を回避する。このようにして、ネットワーク内の接続性に関する問題を迅速に発見するための頑健で簡単化されたソリューションが提供される。
【発明を実施するための最良の形態】
【００１１】
本発明の詳細は、部分的には添付の図面を検討することにより、その構成及び動作の双方について探り出すことができる。図面を通じて、同じ参照番号は同じ部分を示す。
【００１２】
本明細書に開示する所定の実施形態は、有線又は無線ネットワークにおいてバウンダリスキャンテストを実装するシステム及び方法を提供する。例えば、本明細書で開示する一方法は、ネットワーク上のテストステーションが、深さ優先サーチ技術を用いてＭＡＣ層のスキャンテストルートシーケンスを生成し、次いで上記テストステーションが、このスキャンテストルートシーケンスにおける複数のリンクを探索しかつスキャンテストルートシーケンスにおける様々なリンクに関する情報をテストステーションに報告し返すテストエージェントを生み出すことを可能にする。
【００１３】
本明細書を読めば、当業者には、様々な代替実施形態及び代替アプリケーションにおいて本発明を実装する方法が明らかとなるであろう。しかしながら、本明細書では本発明の様々な実施形態について記述するが、これらの実施形態は単なる例として提示するものであり、限定的なものでないことは理解される。従って、様々な代替実施形態についてのこの詳細な説明は、添付の請求の範囲に記載されている本発明の範囲又は広さを限定するものとして解釈されるべきではない。
【００１４】
図１は、本発明の一実施形態に係る例示的な有線、無線又はハイブリッドのネットワーク５０を示す、高レベルネットワークの図である。図示した本実施形態では、本システムは複数のネットワーク装置１０、２０及び３０を通信可能であるように接続するネットワーク５０を備える。
【００１５】
ネットワーク５０は、有線ネットワークであるか、無線ネットワークであるか、あるいは有線及び無線の双方を含む複数の同種又は異種ネットワークの組み合わせであることが可能である。ネットワーク５０は、パーソナルエリアネットワーク（「ＰＡＮ」）であるか、ローカルエリアネットワーク（「ＬＡＮ」）であるか、広域ネットワーク（「ＷＡＮ」）であるか、又はインターネット等のグローバルな通信ネットワークを集合的に構成する、複数のネットワークの分散された組み合わせであることが可能である。ネットワーク５０はアドホックなネットワーク又は永続的なネットワークであることが可能であり、ある場所に固定されている場合もあれば移動体である場合もあり、又は固定された構成要素及び移動体構成要素の組み合わせを含む可能性もある。さらにネットワーク５０は、単一のネットワークプロトコル又は複数のネットワークプロトコルに対応した通信情報を伝送することができる。例えばネットワーク５０は、８０２．３イーサネットトラフィック及び８０２．１１無線トラフィックを伝送することが可能である。
【００１６】
ネットワーク装置は、好適にはネットワーク５０等の通信ネットワークを介して通信する能力を有する装置である。例えばネットワーク装置１０は、パーソナルコンピュータ（「ＰＣ」）、ラップトップコンピュータ、プリンタ、タブレットＰＣ、ＴＶセットトップボックス、ゲームステーションであり、又は、個人情報端末（personal digital assistant：「ＰＤＡ」）、セルラー電話機、ページャもしくは無線ネットワークを介してデータ通信を行う能力を有する他の装置等の無線通信装置であることが可能である。好適には、ネットワーク装置１０、２０及び３０等の様々な異なるネットワーク装置は、ネットワーク５０を介して通信可能であるように接続される。
【００１７】
この詳細な説明においては、ネットワーク装置１０等のネットワーク装置は、ネットワーク装置、ネットワークノード、ノード、無線通信装置、無線ネットワーク装置及び無線ノードと呼ばれる場合もある。本明細書では様々な名称を使用しているが、ネットワーク装置は、図１２及び図１３に関連して説明している構成要素及び機能的能力のすべて又は最小限の部分集合を備える可能性がある。
【００１８】
図２は、本発明の一実施形態に係る、ネットワーク内の様々なノードを接続する例示的なリンク集合を示すネットワークの図である。図示した実施形態では、ネットワーク装置１０、２０及び３０は一連のリンクを介して通信可能であるように接続される。例えば、リンク４２はノード１０とノード２０とを接続し、リンク４４はノード２０とノード３０とを接続し、リンク４６はノード３０とノード１０とを接続する。リンク４２、４４及び４６を逐次に探索することはネットワーク巡回路を完成させるが、この巡回路は、図示した実施形態ではオイラー巡回路でもある。
【００１９】
この詳細な説明における一貫性及び簡単化を目的として、本明細書で言及しかつ詳細に説明している様々なリンクは、双方向的かつ対称な通信リンクとして記載している。従って、特定の方向のリンク、すなわち特定のソースノードから特定の宛先ノードまでのリンクについてのテストの成功は、初期の宛先ノードを起点として初期の起点ノードへと進む同じリンクのテストも成功することを示す。しかしながら、当業者には理解されるであろうが、本詳細な説明により意図される広範な範囲は、方向の決まった通信ネットワーク及び非対称の通信ネットワークに対して、ここで説明した技術を適用することを含む。
【００２０】
図３は、本発明の一実施形態に係る、奇数次数を有するノード間における例示的なリンク集合を示すグラフの図である。図示した実施形態では、ネットワーク５４はノード１００、１０２、１０４及び１０６を含む。通信リンクＡは、ノード１００と１０２とを接続する。通信リンクＢは、ノード１００と１０４とを接続する。通信リンクＣは、ノード１００と１０６とを接続する。同様に、通信リンクＤ及びＦはノード１０２と１０４とを接続し、通信リンクＥ及びＧはノード１０４と１０６とを接続する。また、各ノードの次数も図示されていて、ノード１００、１０２及び１０６は次数３を有し、ノード１０４は次数５を有する。
【００２１】
図示したネットワークグラフはオイラー形式ではない。これは、各リンクを１回通過するためには、グラフ内のいくつかのリンクは２回以上通過しなければならないことを意味する。例えば、Ａ、Ｆ、Ｄ、Ｆ、Ｇ、Ｅ、Ｂ、Ｃ、Ｃの順にリンクを通過する探索は、各リンクを少なくとも１回通って起点ノードへ戻るが、リンクＦ及びＣは２回通過されることになる。
【００２２】
図４は、本発明の一実施形態に係る、偶数次数を有するノード間における、オイラー化された例示的なリンク集合を示すグラフの図である。図示した実施形態では、ネットワーク５４は同じくノード１００、１０２、１０４及び１０６を含む。通信リンクＡは、ノード１００と１０２とを接続する。通信リンクＢは、ノード１００と１０４とを接続する。通信リンクＣ及びＪは、ノード１００と１０６とを接続する。同様に、通信リンクＤ、Ｆ及びＨはノード１０２と１０４とを接続し、通信リンクＥ及びＧはノード１０４と１０６とを接続する。また、各ノードの次数も図示されていて、ノード１００、１０２及び１０６は次数４を有し、ノード１０４は次数６を有する。各ノードが偶数次数を有するので、このネットワークグラフはオイラー形式である。従って、Ａ、Ｆ、Ｄ、Ｈ、Ｇ、Ｅ、Ｂ、Ｃ、Ｊの順にリンクを通過する探索は、各リンクを１回通って最初のノード、すなわちノード１００へ戻ることになる。
【００２３】
図５は、それぞれ対応する通信範囲２１１、２２１、２３１及び２４１を有するネットワーク装置２１０、２２０、２３０及び２４０の例示的な集合を示すネットワークの図である。さらには、可能な通信リンク２５１、２５２、２５３、２５４、２５５及び２５６からなる母集団も図示されている。任意のノードによりブロードキャストされる任意の通信パケットは、ネットワークにおいて最大２ホップ以内にある各ノードにより認識されるので、ネットワーク２００は２ホップの最大半径を有する。
【００２４】
図示した実施形態では、逐次的なブロードキャスト処理を用いてスキャンテストルートシーケンスを生成することができる。例えば、ノード２１０はまず、ノード２３０によってのみ受信されるシングルホップのブロードキャストメッセージを送信する。このブロードキャストメッセージは、通信パケットである場合もあれば、ロービングエージェントである場合もある。ある実施形態では、通信パケットはそのデータペイロードにテストエージェントを有していてもよい。ノード２３０は、これを受信すると、肯定応答メッセージによりリンク２５１を検証し、リンク２５１の品質を記録する。このリンクを検証してリンク品質を記録した後、ノード２３０（及びこの最初のブロードキャストを受信した他の任意のノード）は、ノード２１０、ノード２２０及びノード２４０によって受信される、対応するシングルホップのブロードキャストメッセージを送信する。
【００２５】
ブロードキャストメッセージの発信元としてのノード２１０は、ノード２３０によって送り出されたブロードキャストメッセージを抑止する。これに対してノード２２０及び２４０はこのブロードキャストメッセージに対して肯定応答し、これによりリンク２５３及び２５２を各々検証する。対応するリンク品質も、記録される。ブロードキャストメッセージを再送する次のノード（ノード２２０又はノード４０のいずれか）は、肯定応答によりリンク２５４を検証させ、リンク品質が記録される。さらに、ノード２２０がブロードキャストメッセージを再送すると、このブロードキャストメッセージはノード２１０へ到達する。ノード２１０は、最初にノード２２０から肯定応答を取得していないので、このブロードキャストメッセージを廃棄し、これによりリンク２５５を検証しない可能性がある。あるいは、ノード２１０はノード２３０を介してノード２２０へ肯定応答メッセージを送信し、これによりリンク２５５を検証してもよい。有利なことに、ノード２２０は、ノード２３０を介して受信される肯定応答メッセージから、リンク２５５が一方向リンクであると決定することができる。特に、潜在的なリンク２５６は決して検証されることはなく、よって存在しないとされるか、又は使用不可であると識別される。
【００２６】
有利なことに、テストブロードキャストメッセージの結果は、指向性のトレースバック（例えば逆順）方法でノード２１０へ送り返される。例えば、ノード２４０は、それ自体がそのブロードキャストメッセージから収集したリンク検証及びリンク品質をノード２３０へ送り返し、一方、ノード２３０は、それ自体がそのブロードキャストメッセージから収集したリンク検証及びリンク品質をノード２１０へ供給する。同様に、ノード２２０はそのリンク検証及びリンク品質をノード２３０へ送り、ノード２３０は再度この情報をノード２１０へ送る。
【００２７】
図６は、本発明の一実施形態に係る例示的なブロードキャストメッセージフレーム３００を示すブロック図である。図示した実施形態では、メッセージフレーム３００は一連のフィールドを含む。これらのフィールドは、メッセージのタイプを格納したタイプフィールド３０２を含み、上記メッセージのタイプは、例えば当該メッセージが図５に関連して先に説明したスキャンテストルートシーケンスのブロードキャストであることを示すように設定されることが可能である。また、送信側アドレスフィールド３０４、ソースノードアドレスフィールド３０６、パケットが廃棄されるまでの残りホップ数を示す存続時間（time-to-live）フィールド３０８、エージェント識別フィールド３１０、及びエージェントフィールド３１２も含まれる。エージェントフィールド３１２は、好適にはそのエージェント自体を含む。例えば、エージェントフィールド３１２は、実行可能な命令を含んでもよい。
【００２８】
図７は、本発明の一実施形態に係る例示的な応答メッセージフレーム４００を示すブロック図である。図示した実施形態では、メッセージフレーム４００は一連のフィールドを含む。これらのフィールドは、ユニキャスト応答メッセージのタイプを示すタイプフィールド４０２を含む。また、受信側アドレスフィールド４０４、送信側アドレスフィールド４０６、宛先アドレスフィールド４０８、ソースノードアドレスフィールド４１０、存続時間フィールド４１２、エージェント識別フィールド４１４、及び結果フィールド４１６も含まれる。結果フィールド４１６は、好適にはスキャンテストブロードキャストメッセージの結果を含む。ある実施形態では、結果フィールド４１６は、スキャンテストによって決定される対応した属性値を有する複数のリンクのリストとして配置される。
【００２９】
図８は、本発明の一実施形態に係る例示的なネットワーク巡回路メッセージフレーム５００を示すブロック図である。図示した実施形態では、本メッセージフレームは一連のフィールドを含む。これらのフィールドは、メッセージのタイプを含むタイプフィールド５０２を含み、例えば上記タイプは、スキャンテストルートシーケンスを生成するために使用される、連続したネットワーク巡回路メッセージを示すことが可能である。また、長さフィールド５０４、フィールド内の最初と最後のアドレスが好適にはネットワーク巡回路の開始点であるソースルートフィールド５０６、存続時間フィールド５０８、エージェント識別フィールド５１０、エージェントフィールド５１２、及び結果フィールド５１４も含まれる。
【００３０】
図６乃至図８に関連して先に説明したメッセージフレームを使用するある例示的な実施形態では、ネットワーク内の任意に指定されるノードでスキャンテストルートシーケンスの生成が開始される。ブロードキャストメッセージは、ブロードキャストメッセージに含まれるロービングリンクテストエージェントの複数のインスタンスが、ネットワークの全体にわたって探索することを許容するために送信される。例えば、ブロードキャストメッセージのパケットフォーマットは、図６に示すメッセージフレームの形式をとることが可能である。有利なことに、ブロードキャストメッセージフレームは、タイプフィールド、送信側アドレス、起点ソースノードアドレス、パケットの存続時間（ＴＴＬ）、ロービングテストエージェントＩＤ及びエージェント自体において、ブロードキャスト動作を指定する。エージェント自体は、実行されるべき（複数の）テスト及び試験されるべき属性を典型的には指定するが、またテストに係る実行可能な命令又はテストを変更する実行可能な命令を含んでもよい。
【００３１】
起点ノード（「指定されたノード」とも呼ばれる。）からのブロードキャストメッセージ（パケット又はロービングテストエージェント）が別のノードによって受信されると、これら２つのノード間のリンクが検証され、リンクの品質が記録される。最初のブロードキャストを受信する各ノード（「層（tier）２のノード」）はブロードキャストメッセージ（例えばテストエージェント）を再送し、また同じブロードキャストメッセージである引き続き受信される任意の通信情報の廃棄も行う。これは、起点ノードが最上位にあり、層２のノード（すなわち、１ホップ離れているノード）が次にあり、さらにネットワークの周辺部へと下降して層３、層４、等々を形成している、ブロードキャスト階層を定義する。
【００３２】
テストエージェントを再ブロードキャストすることに加えて、層２以上にある各受信側ノードは、指定されたリンクテストを完了し、そのテストエージェントを送信した親ノードへユニキャスト応答を供給する。このような応答メッセージフレームは図７に関連して先に説明したものであり、受信側アドレス、送信側アドレス、宛先アドレス、ソースアドレス、エージェントＩＤ、及びテスト結果を含む可能性がある。テスト結果は、典型的には、テストによって決定される属性値を有する複数のリンクのリストとして編成される。有利なことに、ブロードキャストに肯定応答する各受信側により、受信側とブロードキャストの送信側との間のリンクが機能試験され、よって検証されることが可能である。
【００３３】
テスト結果に含まれる属性には、リンクの接続性、リンク品質、相対的信号強度指示子、ノードルーティング構成、又は関心の持たれた他の属性が含まれてもよい。ある実施形態では、複数のテスト結果がビットベクトルとして表現される。この構成では、５０００個のリンクを有するネットワーク（例えば、１００個のノードよりなる完全に接続されたネットワーク）は、およそ０．６２５キロバイトのデータが伝送されることを必要とする。またテスト結果は、例えば大規模ネットワークの場合には２つ以上の通信パケットを用いて、指定されたノードへ移送される場合もある。信頼性の高い移送を保証するために、テスト結果の通信に対して肯定応答し、必要であれば再送してもよい。また、様々なレベルの細分性でリンク品質を示すために、又は複数のリンク属性を組み込むために、複数ビット／リンクの方法が使用可能である。最後に、ネットワークスキャンテストは、有利なことに小さいデータパケットを使用し、ネットワークを無駄なデータで塞ぐ可能性のあるルーティングテーブルを排除する。
【００３４】
ある実施形態では、テスト結果は各受信側ノードで記録され、肯定応答パケットを介してブロードキャストの送信側ノードへ送り返される。このような実施形態では、中間ノード（例えば、層２のノード）が肯定応答を複数回にわたって供給することが期待される。例えば、先に述べたブロードキャスト動作の場合のｍホップの半径（すなわち、ｍ−１個の層）を備えたネットワークでは、起点ノードで開始されるブロードキャストに係る最大回数の肯定応答動作は、指定されたノードから１ホップ離れたノードで発生し、肯定応答は合計ｍ回になる。
【００３５】
ここでいうネットワーク半径は、最も遠隔のノードに到達するために中間ノードにより転送されなければならないブロードキャスト動作の最小回数として定義される。中間ノードにおける肯定応答の数を減らすために、ネットワークのブロードキャスト半径が推定可能であり、ホップ当たりの往復遅延が推定可能であり、指定されたノードからｎホップの各ブロードキャストリングにおけるすべてのノードについてタイムアウト期間の適正値が計算可能である。これらのタイムアウトパラメータを用いて、層２のノードは、有利なことに、指定されたノードへその肯定応答を送信する前に、その下位ノードからの肯定応答のうちの大部分又はすべてが累積されるまで待機する。この構成は、実装を簡単化しかつほとんどメモリを必要としないという優位点も有する。特に、中間ノードは、それら自体の下位ノードによる応答を待ちながら、ブロードキャスト階層におけるその直接の親ノードへ肯定応答を送る方法を知るだけでよい。これらのノードでは、スキャンテストルートシーケンスの構成を容易にするために余分なルーティングテーブルを構築する必要はない。
【００３６】
タイムアウト期間が経過すると、指定されたノードにおける受信されたスキャンテストルートシーケンスの結果はすべて、試験対象であるネットワークの各リンクの接続性及びリンク品質を示すリンクマップを構成するために使用可能である。このリンクマップがスキャンテストルートシーケンスである。従って、ネットワークのバウンダリスキャンテストは、各ノードでのただ１回のブロードキャスト動作のみを必要とする。さらに、ネットワークのバウンダリスキャンテストは、各中間ノード及びリーフノードにおける実装が簡単でかつ演算及びメモリ要件が低いという優位点を有する。
【００３７】
図９Ａ乃至図９Ｄは、本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的なネットワーク巡回路技術を示すグラフの図である。図９Ａには、４つのノード６２０、６２２、６２４及び６２６を含むネットワークが示されている。また、リンク６３０、６３２、６３４、６３６、６３８及び６４０を含む理論上のリンクもすべて示されている。図９Ｂには、グラフをオイラー形式に適合させるために、このネットワークの図に２つの追加リンク６４２及び６４４が加えられている。図示した実施形態が示すように、各ノード６２０、６２２、６２４及び６２６は偶数次数を有する。これで、ネットワーク巡回路（すなわち郵便配達人巡回路）は、
６４０、６３４、６３６、６３０、６３８、６４２、６３２及び６４４
として構成されることが可能である。このようなネットワーク巡回路はノード６２０で始まり、ネットワーク内の各リンクをただ一度だけ通ってノード６２０で終わる。
【００３８】
図９Ｃに示す実施形態では、ノード６２０と６２４とは通信不能である。例えばこれらは、互いに同じレンジ内に存在しない無線通信装置である可能性がある。従って、リンク６４０の初回の探索（すなわちテスト）は検証に失敗する。よって、スキャンテストルートシーケンスの生成処理では、リンク６４０を削除し、リンク６４４等のすべての等価なリンクを削除する。図９Ｃは、このような措置の後の残ったリンクを示し、これは、この時点でネットワーク巡回路が、
６３６、６３４、６３２、６３８、６４２及び６３０
として構成されることを要求する。この場合も同じく、ネットワーク巡回路はノード６２０で始まり、ネットワーク内の各リンクをただ１度だけ通ってノード６２０で終わる。
【００３９】
図９Ｄに示す実施形態では、スキャンテストルートシーケンスの処理が新たなネットワーク巡回路ルートに沿ってノード６２２へ到達すると、リンク６３８上の障害が検出される。この時点で、スキャンテストルートシーケンスの処理はそれまで試験に成功したリンクをすべて削除し、グラフの他の部分の残りのノードのために、すなわちリンク６３０で接続されるノード６２０及びノード６２２のために新たなネットワーク巡回路を構成する。この残りの部分グラフは、新たなリンク６４６を追加することによりオイラー形式へ変換される。この部分グラフのネットワーク巡回路はこれで、
６３０及び６４６
として構成されることが可能である。この場合、ネットワーク巡回路はノード６２２で始まり、残りの部分ネットワーク内の各リンクをただ１度だけ通り、ノード６２２へ戻って終わる。
【００４０】
リンク６３０及び６４６が検証されると、テスト結果が累積され、元の開始点、つまりノード６２０へ送り返される。結果を返送するための経路は、再構成されたリンクの逆順であり、すなわち６３２、６３４及び６３６の順になる。あるいは、スキャンテストルートシーケンスの処理は、リンク６３０を探索（しかつ検証）した後にノード６２０へのその帰還を検出してもよく、処理はそこで終了し、有利なことには、リンク６４６の冗長な探索と、リンク６３２、６３４及び６３６をたどってノード６２０へ戻る動作とを除去してもよい。
【００４１】
田舎の郵便配達人巡回路を採用する実施形態では、ルートスキャンテストシーケンスは、ネットワークの探索可能な各部分グラフに対して構成される一連の田舎の郵便配達人巡回路を介して生成される。特に、試験対象であるネットワークは無向グラフによって表現される。田舎の郵便配達人巡回路はこのように構成されることが可能であり、各リンクを探索するネットワークを介する完全ルート（「ソースルート」）として表現される。次には、ソースルートに従ってグラフを探索するためにロービングテストエージェントが配備され、このテストエージェントは、ネットワーク全体にわたって移動する際にソースルートのコピーを含んでいる。探索される各リンクについて、指定されたリンクテストが実行され、結果が記録される。テスト結果は指定されたノードへ即時報告して返される場合もあれば、後に報告して返すためにロービングテストエージェントにより伝送される場合もある。
【００４２】
リンクの試験が成功すると、ロービングテストエージェントはソースルートに従って次のノードへ進む。リンクの試験が不成功に終わると、すなわち失敗したり又は存在しないとされたりすると、現時点の巡回路はサスペンドされる。この時点で、新たな部分グラフが構成され、成功又は不成功に関わらず試験されたすべてのリンクが削除され、このリンクの削除の後に、もはや部分グラフに関係のないノードも削除される。次いで、先行した巡回路がサスペンドされたノードを巡回路の開始点（例えば指定されたノード）として、新たな田舎の郵便配達人巡回路が構成される。このようにして、ロービングテストは、田舎の郵便配達人巡回路を最終的にかつ成功裡に完成できるまで継続される。ロービングテストエージェントは次に、成功したすべてのリンクに沿って逆方向へ探索し、巡回路の元の開始点へ到達する。このようにして、ネットワーク内のすべてのリンクは少なくとも一度試験される。
【００４３】
有利なことに、続いて構成される田舎の郵便配達人巡回路の部分グラフは、常に、先行する巡回路のグラフ又は部分グラフより単純になる（すなわち、より少数のリンク又はより少数のノードを有する）。このことは、アルゴリズムが収束性であることを保証する。田舎の郵便配達人巡回路の構成は計算上は多項式的であり、上記構成はまた、最新のほとんどの通信機器がノードの処理パワーにより制約されることはないので、ネットワークノードに容易に収容されることが可能である。さらに、逐次的な田舎の郵便配達人巡回路計算の使用は、ネットワークを不必要にあふれさせる可能性のあるブロードキャストメッセージ動作を回避する。複雑さ（エラーを除く伝送回数）はＯ（Ｎ２）である。ここで、Ｎは試験対象であるネットワーク内の全ノード数である。
【００４４】
図１０は、本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的な深さ優先サーチ技術を示すグラフの図である。図示した実施形態では、様々なノード間に存在する階層的な通信リンクに沿って一連のネットワークノードＡ乃至Ｉが示されている。また、例えばノードＢ、Ｃ及びＤ等の共通のレベル上のノード間には、追加の通信リンクが存在してもよい。
【００４５】
図示した実施形態において、スキャンテストルートシーケンスは、深さ優先サーチ処理を用いてテストステーションからネットワークグラフ内のノードがサーチされるようにオンラインで計算される。図に示すように、ノードＡがテストステーションである。深さ優先サーチは、２つのフェーズにおいて進行する。第１のフェーズにおいて、１次ノードは、その近傍ノードのすべてのリストを含むスキャンチェーンテーブルを構成する。これは、ブロードキャストメッセージを送出することによって行われる。第２のフェーズでは、１次ノードは、その近傍リストにおけるノードの各々にユニキャストメッセージを送る。ユニキャストメッセージは連続して送出されるが、第１のユニキャストメッセージからの応答が受信されるまで第２のユニキャストメッセージが送信されないように送出される。
【００４６】
このように、ネットワーク全体にわたって探索して包括的なスキャンチェーンテーブルを構築することを深さ優先サーチの制御に実行させる、一連のブロードキャスト及びユニキャストメッセージが存在する。図示した実施形態では、フローは下記経路、すなわち
Ａ、Ｂ、Ｅ、Ｆ、Ｃ、Ｇ、Ｄ、Ｈ、Ｉ
に沿って進む。
【００４７】
スキャンチェーンテーブルの構成に際して、テストステーションＡは、好適には先行するどのスキャンチェーン構成を開始することにも使用されていないテストベクトル識別子を選択する。さらに、深さ識別子変数がまずゼロに設定される。テストステーションＡは次に当該テストステーションＡ自体を１次ノードとしてアサートし、ブロードキャストエコー要求を送ってそれに最も近いすべての近傍のリストを収集する。ブロードキャストは、この特定の試験ラウンドを一意に識別するテストベクトル識別子を含む。さらに、ブロードキャストは、それまでにスキャンチェーンへ接続されているノードの個数を示す深さ識別子（例えばホップ数）を含む。
【００４８】
ブロードキャストエコーがテストステーションＡによって受信されると、テストベクトル識別子と、深さ識別子と、近傍フィンガ（例えば、最も近い近傍を示すポインタ）と、最も近いすべての近傍のリストとを含む記録が構成される。またテストステーションＡは、最後の近傍が応答するときスキャンチェーン構成が終了することを特定するフラグも含む。最後に、テストステーションＡはその最も近い近傍（例えば、ノードＢ）へユニキャストメッセージを送信し、このユニキャストメッセージは、１次ノードになってスキャンチェーンテーブルの構成を続けるように当該最も近い近傍に命令する。
【００４９】
最も近い近傍（例えば、ノードＢ）は、テストステーションからユニキャストメッセージを受信すると、当該近傍自体を１次ノードとしてアサートし、テストメッセージの再ブロードキャストを送出してその最も近い近傍を識別する。ノードＢによって送出されるブロードキャストメッセージは、元のブロードキャストからのものと同じテストベクトル識別子を含む。またノードＢは、そのエコー応答を受信すると、テストベクトル識別子と、深さ識別子と、近傍フィンガ（例えば、最も近い近傍を示すポインタ）と、最も近いすべての近傍のリストとを含む記録を生成する。またノードＢは、例えばノードＡを最も近い近傍のリストの最後に入力することにより、完了時にはスキャンチェーンテーブルがノードＡへ戻されるべきであるということを指定するフラグを、その記録において含む。最後に、ノードＢは、その最も近い近傍（例えばノードＥ）へユニキャストメッセージを送り、１次ノードになってスキャンチェーンテーブルの構成を続けるようにそのノードに命令する。このユニキャストメッセージは、元のメッセージからのものと同じテストベクトル識別子を含むが、深さ識別子は、別のノードがチェーンに追加されていることを示すためにインクリメントされる。
【００５０】
本処理はノードＥ及びＦで継続されるが、部分グラフの一部分がテストステーションＡへ戻ると、テストステーションＡは、その記録において識別されているその次に近い近傍へと進み、ノードＣに対して、当該ノードＣ自体を１次ノードとしてアサートしてスキャンチェーンテーブルの構成を継続するように命令する。有利なことに、深さ識別子は決してリセットされることはなく、よってテストステーションＡがノードＣへユニキャストメッセージを送ると深さ識別子は７になり、チェーンに沿ってノードＡからノードＣへ至るまでのホップ数（下降及び逆行）が反映される。
【００５１】
本処理は、テストステーションがその近傍リスト内の最後のノードを過ぎて進むまで継続され、その時点でスキャンチェーンテーブルが完成される。有利なことに、スキャンチェーンテーブルはバウンダリスキャンチェーンを介してプローブメッセージを送るために使用可能である。例えば、スキャンチェーン上のｎ番目のノードへメッセージを送るために、テストステーションＡは、３つのフィールドを有するブロードキャストメッセージを送る。ブロードキャストメッセージのこれらのフィールドは、（ａ）宛先ノードｎと、（ｂ）次ホップノードｋ（その初期値は１であるが、パケットが転送される毎にインクリメントされる。）と、（ｃ）テストベクトル識別子（これは、使用されるべき適正なスキャンチェーンの記録を照合するために使用される。）とを含む。
【００５２】
このようなブロードキャストがターゲットノードをｎとして送信されるときは常に、各ノードはテストベクトル識別子を照合して、これまでにメッセージを転送する際の深さ識別子としてｋを使用したか否かを決定する。あるノードがｋを使用したことがある場合、このノードはメッセージを受け入れ、ｋ＋１の次ホップ識別子を有するメッセージを再ブロードキャストする。あるホストが、ｎ＝ｋを有するメッセージを受け入れれば、当該ホストは、意図された受信側であり、そのメッセージを処理する。このようなメッセージに応答するために、ターゲット宛先を無限大とする新たなメッセージが生成される。これにより、メッセージはテストステーションＡへ戻るようにルーティングされる。最悪の場合、田舎の郵便配達人巡回路のための貪欲なオンラインアルゴリズムは、Ｍ個の辺を有するグラフにおいて２Ｍ個の辺を探索しなければならない。図１０に関連して説明したような深さ優先サーチはこの性能の限界に到達し、よって貪欲なオンラインアルゴリズムの全可能性の中で最適である。
【００５３】
有利なことに、ここで説明したスキャンテストルートシーケンスを生成するための深さ優先サーチ技術は、実装が簡単であるという優位点を有し、ネットワークノードにおける計算をほとんど必要とせず、しかもスキャンテストメッセージをネットワークグラフの深さ方向へと拡散させることによりネットワークの輻輳を回避する。さらに本技術は、任意サイズのネットワークに拡張可能（スケーラブル）であり、また本技術は、既存のルーティングテーブル又はネットワーク層通信プロトコルに依存しない、より信頼性の高い通信をもたらす。
【００５４】
図１１は、本発明の一実施形態に係る、ホップカウント（すなわち、スキャンチェーンの位置）に基づく例示的なネットワークアドレスのリストである。図示したこのネットワークアドレスのリストにおいて、ノードＡは、これがルート（根）ノードであるので、ゼロのネットワークアドレスを有する。ノードＢは、これがスキャンテストルートシーケンスに沿って１ホップで到達されるので、ネットワークアドレス１を有する。ノードＣは、従来のルーティングではノードＡから同じく１ホップ離れているとされるところであるが、スキャンテストルートシーケンスによれば、ノードＣはノードＡから７ホップ離れていて、よってそのネットワークアドレスは７である。同様に、ノードＤはネットワークアドレス１１を有する。従って、ノードＥはネットワークアドレス２を有し、ノードＦはネットワークアドレス４を有し、ノードＧはネットワークアドレス８を有し、ノードＨはネットワークアドレス１２を有し、ノードＩはネットワークアドレス１４を有する。
【００５５】
ある実施形態では、ノードＡは、有利なことには、より低いネットワークアドレスを有する任意の中間ノードを介して特定のノードへ通信パケットをルーティングすることが可能である。従って、通信パケットをノードＩへ配信するために、ノードＡはまずノードＢ、ノードＣ又はノードＤを介してパケットを送り、パケットのノードＩへの到達を保証することが可能である。これは、スキャンテストルートシーケンスの逐次的性質と、通信パケットを受信側ノードにより次ノードへ順次に転送することとに基づくものである。
【００５６】
図１２は、本明細書に記載した様々な実施形態に関連して使用可能な例示的な無線通信装置７００を示すブロック図である。例えば、無線通信装置７００は、ハンドセット又はＰＤＡネットワーク装置とともに使用可能であり、又は無線メッシュネットワークにおけるセンサノードの一部として使用可能である。しかしながら、当業者には明らかなことであろうが、他の無線通信装置及び／又はアーキテクチャも使用可能である。
【００５７】
図示した実施形態では、無線通信装置７００は、アンテナ７０２、デュプレクサ７０４、低雑音増幅器（「ＬＮＡ」）７０６、電力増幅器（「ＰＡ」）７０８、変調回路７１０、ベースバンドプロセッサ７１２、スピーカ７１４、マイクロフォン７１６、中央処理装置（「ＣＰＵ」）７１８、及びデータ記憶エリア７２０を備える。本無線通信装置７００では、アンテナ７０２により無線周波数（「ＲＦ」）信号が送受信される。デュプレクサ７０４はスイッチとして動作し、アンテナ７０２を信号送信経路と信号受信経路との間に接続させる。受信経路では、受信されたＲＦ信号がデュプレクサ７０４からＬＮＡ７０６へ接続される。ＬＮＡ７０６は受信されたＲＦ信号を増幅し、増幅された信号を変調回路７１０の復調部分へ接続させる。
【００５８】
典型的には、変調回路７１０は、復調器と変調器とを１つの集積回路（「ＩＣ」）に組み合わせる。復調器及び変調器は、別々の構成要素である場合もある。復調器はＲＦ搬送波信号を除去してベースバンドの受信音声信号を残し、これが復調器出力からベースバンドプロセッサ７１２へ送られる。
【００５９】
ベースバンドの受信音声信号が音声情報を含んでいれば、ベースバンドプロセッサ７１２はこの信号を復号化し、これをアナログ信号に変換する。次に、信号は増幅されてスピーカ７１４へ送られる。ベースバンドプロセッサ７１２はまた、マイクロフォン７１６からアナログ音声信号を受信する。これらのアナログ音声信号はディジタル信号に変換され、ベースバンドプロセッサ７１２によって符号化される。ベースバンドプロセッサ７１２はまた、ディジタル信号を伝送用に符号化してベースバンドの送信音声信号を発生させ、
このベースバンドの送信音声信号は、変調回路７１０の変調器部分へルーティングされる。変調器はこのベースバンド送信音声信号とＲＦ搬送波信号とを混合してＲＦ送信信号を発生させ、このＲＦ送信信号は、電力増幅器７０８へルーティングされる。電力増幅器７０８はこのＲＦ送信信号を増幅してこれをデュプレクサ７０４へルーティングし、信号はデュプレクサ７０４においてアンテナポートへ切り換えられ、アンテナ７０２により送信される。
【００６０】
ベースバンドプロセッサ７１２はまた、中央処理装置７１８と通信可能であるように接続される。中央処理装置７１８は、データ記憶エリア７２０へのアクセスを有する。中央処理装置７１８は、好適には、データ記憶エリア７２０に格納されることが可能な命令（すなわち、コンピュータプログラム又はソフトウェア）を実行するように構成される。コンピュータプログラムはベースバンドプロセッサ７１２から受信されて、データ記憶エリア７２０に格納されるか、受信時に実行されることも可能である。このようなコンピュータプログラムは、実行されると、先に述べたように無線通信装置７００が本発明の様々な機能を実行することを可能にする。
【００６１】
本明細書における「コンピュータが読み取り可能な媒体」という用語は、実行可能な命令（例えば、ソフトウェア又はコンピュータプログラム）を中央処理装置７１８により実行させるために無線通信装置７００へ供給するためにに使用される任意の媒体を示すように使用される。これらの媒体の例には、データ記憶エリア７２０、（ベースバンドプロセッサ７１２を介する）マイクロフォン７１６、及び（同じくベースバンドプロセッサ７１２を介する）アンテナ７０２が含まれる。コンピュータが読み取り可能なこれらの媒体は、実行可能なコードとプログラミング命令とソフトウェアとを無線通信装置７００へ供給するための手段である。実行可能なコード、プログラミング命令及びソフトウェアは、中央処理装置７１８によって実行されると、好適には、本明細書で先に説明した本発明に係る特徴及び機能を中央処理装置７１８に実行させる。
【００６２】
図１３は、本明細書に記載した様々な実施形態に関連して使用可能な例示的なコンピュータシステム７５０を示すブロック図である。例えば、本コンピュータシステム７５０は、ネットワーク装置、ネットワークアクセスポイント、ルータ、ブリッジ、又は他のネットワークインフラストラクチャ構成要素と併せて使用可能である。しかしながら、当業者には明らかであろうが、他のコンピュータシステム及び／又はアーキテクチャも使用可能である。
【００６３】
コンピュータシステム７５０は、好適には、プロセッサ７５２等の１つ又は複数のプロセッサを含む。追加のプロセッサとして、入／出力を管理する補助プロセッサ、浮動小数点の数学的演算を実行する補助プロセッサ、信号処理アルゴリズムの高速実行に適したアーキテクチャを有する専用マイクロプロセッサ（例えば、ディジタル信号プロセッサ）、メイン処理システムに従属するスレーブプロセッサ（例えば、バックエンドプロセッサ）、デュアルもしくはマルチプロセッサシステムのための追加的マイクロプロセッサもしくはコントローラ、又はコプロセッサ等が供給されてもよい。このような補助プロセッサは、独立した（ディスクリートの）プロセッサである場合もあれば、プロセッサ７５２に一体化される場合もある。
【００６４】
プロセッサ７５２は、好適には通信バス７５４へ接続される。通信バス７５４は、コンピュータシステム７５０の記憶装置と他の周辺構成要素との間の情報転送を促進するためのデータチャンネルを含むことが可能である。通信バス７５４はさらに、プロセッサ７５２と通信するために使用される信号のセットを供給することが可能であり、データバス、アドレスバス及び制御バス（図示せず。）を含む。通信バス７５４は、任意の標準又は非標準のバスアーキテクチャを含むことが可能であり、例えば、工業標準アーキテクチャ（industry standard architecture：「ＩＳＡ」）、拡張工業標準アーキテクチャ（extended industry standard architecture：「ＥＩＳＡ」）、マイクロチャンネルアーキテクチャ（Micro Channel Architecture：「ＭＣＡ」）、ペリフェラルコンポーネントインターコネクト（peripheral component interconnect：「ＰＣＩ」）のローカルバス、又は、ＩＥＥＥ  ４８８の汎用インターフェースバス（general-purpose interface bus：「ＧＰＩＢ」）やＩＥＥＥ  ６９６／Ｓ−１００などを含む米国電気電子学会（Institute of Electrical and Electronic Engineers：「ＩＥＥＥ」）により公表されている規格等に準拠したバスアーキテクチャを含むことが可能である。
【００６５】
コンピュータシステム７５０は、好適には主メモリ７５６を含み、また、補助メモリ（２次メモリ）７５８を含むことも可能である。主メモリ７５６は、プロセッサ７５２上で実行されるプログラムのための命令及びデータの記憶装置を提供する。主メモリ７５６は典型的には、ダイナミックランダムアクセスメモリ（「ＤＲＡＭ」）及び／又はスタティックランダムアクセスメモリ（「ＳＲＡＭ」）等の、半導体に基づいたメモリである。半導体に基づいた他のタイプのメモリとしては、例えば、同期ダイナミックランダムアクセスメモリ（「ＳＤＲＡＭ」）、ラムバスダイナミックランダムアクセスメモリ（「ＲＤＲＡＭ」）、強誘電体ランダムアクセスメモリ（「ＦＲＡＭ」）及びこれらに類似するものが含まれ、また読み出し専用メモリ（「ＲＯＭ」）が含まれる。
【００６６】
補助メモリ７５８は、オプションとして、ハードディスクドライブ７６０を含んでもよく、及び／又は、例えばフロッピーディスクドライブ、磁気テープドライブ、コンパクトディスク（「ＣＤ」）ドライブ、ディジタルバーサタイルディスク（「ＤＶＤ」）ドライブなどのリムーバブル記憶ドライブ７６２を含んでもよい。リムーバブル記憶ドライブ７６２は、リムーバブル記憶媒体７６４に対して、既知の方法により読み出し及び／又は書き込みを行なう。リムーバブル記憶媒体７６４は、例えばフロッピーディスク、磁気テープ、ＣＤ、ＤＶＤなどであることが可能である。
【００６７】
リムーバブル記憶媒体７６４は、好適には、コンピュータが実行可能なコード（すなわちソフトウェア）及び／又はデータを上に記憶している、コンピュータが読み取り可能な媒体である。リムーバブル記憶媒体７６４上に格納されるコンピュータソフトウェア又はデータは、電気的な通信信号７７８としてコンピュータシステム７５０の中に読み込まれる。
【００６８】
代替実施形態では、補助メモリ７５８は、コンピュータプログラム又は他のデータ又は命令がコンピュータシステム７５０の中へロードされることを可能にするための他の類似手段を含んでもよい。このような手段は、例えば外部記憶媒体７７２及びインターフェース７７０を含む可能性がある。外部記憶媒体７７２の例には、外部ハードディスクドライブもしくは外部光ドライブ、及び／又は外部光磁気ドライブが含まれる可能性がある。
【００６９】
補助メモリ７５８の他の例としては、プログラム可能な読み出し専用メモリ（「ＰＲＯＭ」）、消去可能かつプログラム可能な読み出し専用メモリ（「ＥＰＲＯＭ」）、電気的に消去可能な読み出し専用メモリ（「ＥＥＰＲＯＭ」）又はフラッシュメモリ（ＥＥＰＲＯＭに似たブロック指向（block oriented）のメモリ）等の、半導体に基づいたメモリを含むことが可能である。また、他の任意のリムーバブル記憶装置７７２及びインターフェース７７０も含まれ、これにより、ソフトウェア及びデータがリムーバブル記憶装置７７２からコンピュータシステム７５０へ転送されることが可能になる。
【００７０】
またコンピュータシステム７５０は、通信インターフェース７７４を含むことが可能である。通信インターフェース７７４は、ソフトウェア及びデータがコンピュータシステム７５０と外部装置（例えばプリンタ）、ネットワーク又は情報ソースとの間で転送されることを可能にする。例えば、コンピュータソフトウェア又は実行可能なコードは、ネットワークサーバから通信インターフェース７７４を介してコンピュータシステム７５０へ転送されることが可能である。通信インターフェース７７４の例には、多少の例を挙げると、モデムと、ネットワークインターフェースカード（「ＮＩＣ」）と、通信ポートと、ＰＣＭＣＩＡスロット及びカードと、赤外線インターフェースと、ＩＥＥＥ  １３９４ファイヤーワイヤーとが含まれる。
【００７１】
通信インターフェース７７４は、好適には、業界において公表されたプロトコル規格を実装し、例えば、イーサネットＩＥＥＥ  ８０２規格、ファイバチャネル、ディジタル加入者線（「ＤＳＬ」）、非同期ディジタル加入者線（「ＡＤＳＬ」）、フレームリレー、非同期転送モード（「ＡＴＭ」）、サービス総合ディジタル網（「ＩＳＤＮ」）、パーソナルコミュニケーションサービス（「ＰＣＳ」）、伝送制御プロトコル／インターネットプロトコル（「ＴＣＰ／ＩＰ」）、シリアルラインインターネットプロトコル／ポイント・ツー・ポイントプロトコル（「ＳＬＩＰ／ＰＰＰ」）などを実装するが、カスタマイズされたインターフェースプロトコル又は非標準のインターフェースプロトコルを実装してもよい。
【００７２】
通信インターフェース７７４を介して転送されるソフトウェア及びデータは、一般には電気的な通信信号７７８の形式である。これらの信号７７８は、好適には、通信チャンネル７７６を介して通信インターフェース７７４へ供給される。通信チャンネル７７６は信号７７８を伝送するが、通信チャンネル７７６は、多少の例を挙げると、ワイヤーもしくはケーブル、光ファイバ、従来の電話回線、セルラー電話リンク、無線周波（ＲＦ）リンク、又は赤外線リンクを含む様々な通信手段を用いて実装可能である。
【００７３】
主メモリ７５６及び／又は補助メモリ７５８には、コンピュータが実行可能なコード（すなわち、コンピュータプログラム又はソフトウェア）が格納される。コンピュータプログラムは、通信インターフェース７７４を介して受信されて主メモリ７５６及び／又は補助メモリ７５８に格納される場合もある。このようなコンピュータプログラムは、実行されると、先に説明したような本発明の様々な機能をコンピュータシステム７５０が実行することを可能にする。
【００７４】
この明細書における「コンピュータが読み取り可能な媒体」という用語は、コンピュータが実行可能なコード（例えば、ソフトウェア及びコンピュータプログラム）をコンピュータシステム７５０へ供給するために使用される任意の媒体を示すように使用される。これらの媒体の例には、主メモリ７５６と、補助メモリ７５８（ハードディスクドライブ７６０、リムーバブル記憶媒体７６４及び外部記憶媒体７７２を含む）と、通信インターフェース７７４に通信可能であるように接続される任意の周辺装置（ネットワーク情報サーバ又は他のネットワーク装置を含む）とが含まれる。これらのコンピュータが読み取り可能な媒体は、実行可能なコード、プログラミング命令及びソフトウェアをコンピュータシステム７５０へ供給するための手段である。
【００７５】
ソフトウェアを用いて実装される実施形態では、ソフトウェアは、コンピュータが読み取り可能な媒体上へ格納され、リムーバブル記憶ドライブ７６２、インターフェース７７０又は通信インターフェース７７４によってコンピュータシステム７５０へロードされることが可能である。このような実施形態では、ソフトウェアは電気的な通信信号７７８の形式でコンピュータシステム７５０へロードされる。ソフトウェアは、プロセッサ７５２によって実行されると、好適には、本明細書で先に説明した本発明に係る特徴及び機能をプロセッサ７５２に実行させる。
【００７６】
また様々な実施形態は、例えば特定用途向け集積回路（application specific integrated circuit：「ＡＳＩＣ」）又はフィールド・プログラマブル・ゲート・アレイ（「ＦＰＧＡ」）等の構成要素を用いて、まずハードウェアとして実装されてもよい。また当業者には、本明細書で説明した機能を実行する能力のあるハードウェア状態マシンを実装することも明らかであろう。様々な実施形態はまた、ハードウェア及びソフトウェア双方の組み合わせを用いて実装されてもよい。
【００７７】
本明細書で詳しく示しかつ説明した特定のシステム及び方法は、先に説明した本発明の目的を十分に達成し得るものであるが、本明細書に提示した説明及び図面は現時点での本発明の好適な実施形態を示すものであり、よって本発明により広範に意図される発明対象を表現するものであることは理解されるべきである。さらに、本発明の範囲は、当業者には自明となるであろう他の実施形態を完全に包含すること、よって本発明の範囲は添付の請求の範囲によってのみ限定されることも理解される。
【図面の簡単な説明】
【００７８】
【図１】本発明の一実施形態に係る、例示的な有線、無線又はハイブリッドのネットワークトポロジーの高レベルネットワークの図である。
【図２】本発明の一実施形態に係る、ネットワーク内の様々なノードを接続する例示的なリンク集合を示すネットワークの図である。
【図３】本発明の一実施形態に係る、奇数次数を有するノード間における例示的なリンク集合を示すグラフの図である。
【図４】本発明の一実施形態に係る、偶数次数を有するノード間におけるオイラー化された例示的なリンク集合を示すグラフの図である。
【図５】本発明の一実施形態に係る例示的なネットワーク装置の集合であって、それらの対応する通信範囲及び可能な通信リンクを有するネットワーク装置の集合を示すネットワークの図である。
【図６】本発明の一実施形態に係る例示的なブロードキャストメッセージフレームを示すブロック図である。
【図７】本発明の一実施形態に係る例示的な応答メッセージフレームを示すブロック図である。
【図８】本発明の一実施形態に係る例示的なネットワーク巡回路メッセージフレームを示すブロック図である。
【図９Ａ】本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的なネットワーク巡回路技術を示すグラフの図である。
【図９Ｂ】本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的なネットワーク巡回路技術を示すグラフの図である。
【図９Ｃ】本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的なネットワーク巡回路技術を示すグラフの図である。
【図９Ｄ】本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的なネットワーク巡回路技術を示すグラフの図である。
【図１０】本発明の一実施形態に係る、スキャンテストルートシーケンスを生成するための例示的な深さ優先サーチ技術を示すグラフの図である。
【図１１】本発明の一実施形態に係る、ホップ・カウントに基づく例示的なネットワークアドレスのリストである。
【図１２】本明細書に記載した様々な実施形態に関連して使用可能な例示的な無線通信装置を示すブロック図である。
【図１３】本明細書に記載した様々な実施形態に関連して使用可能な例示的なコンピュータシステムを示すブロック図である。
【図１】
2006526303.tif 000002
【図２】
2006526303.tif 000003
【図３】
2006526303.tif 000004
【図４】
2006526303.tif 000005
【図５】
2006526303.tif 000006
【図６】
2006526303.tif 000007
【図７】
2006526303.tif 000008
【図８】
2006526303.tif 000009
2006526303.tif 000010
2006526303.tif 000011
【図１０】
2006526303.tif 000012
【図１１】
2006526303.tif 000013
【図１２】
2006526303.tif 000014
【図１３】
2006526303.tif 000015
【国際調査報告】
2006526303.tif 000016
2006526303.tif 000017