(57)【要約】【課題】メッシュネットワーク内のノードの相対位置を判定するプロトコルを提供する。【解決手段】一実施形態では、ネイバロケーションディスカバリプロトコル（ＮＬＤＰ）を、ノードが指向性アンテナを備え、ＧＰＳを使用できないアドホック無線ネットワーク用に実装できる。ＮＬＤＰは、少なくとも２つのＲＦトランシーバを有するノードに依拠するが、１つのＲＦトランシーバだけを使用する、以前に提案されたプロトコルに比べて重要な利点を提供する。ＮＬＤＰでは、アンテナハードウェアは、単純で、実装が簡単で、容易に入手できる。さらに、ＮＬＤＰは、オーバーラップしないチャネルにわたり同時に動作するホストノードの能力を活用し、急速に近接ノード位置に収束する。【選択図】図６
2006279951.tif 000002
【特許請求の範囲】
【請求項１】
メッシュネットワークにおける相対的なネイバロケーションをディスカバリする方法であって、
新規ネットワークノードにより前記メッシュネットワークに隣接するステップと、
前記新規ネットワークノードにより、制御チャネルを介してジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記メッシュネットワーク内の第２のネットワークノードで前記ジェネラルディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードにアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ジェネラルディスカバリリクエストメッセージに応答するステップと、
前記新規ネットワークノードで前記アクノリッジメントメッセージを受信し、ネイバロケーションテーブル内に対応するエントリを作成するステップと、
前記新規ノードにより、データチャネルのアンテナを経由して、前記アンテナの現在の方向に対応する方向に、前記データチャネルを介してディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記ディレクショナルジェネラルディスカバリリクエストメッセージを前記第２のネットワークノードで受信するステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答するステップと、
前記新規ネットワークノードで前記第２のアクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
を備えたことを特徴とする方法。
【請求項２】
前記ジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つステップと、
アクノリッジメントメッセージが前記時間中に前記新規ノードで受信されない場合に、前記新規ネットワークノードにより、前記制御チャネルを介して前記ジェネラルディスカバリリクエストメッセージを再ブロードキャストするステップと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項３】
相対的なネイバロケーションのディスカバリを打ち切る前に、前記待つステップおよび前記再ブロードキャストするステップを指定された反復回数だけ繰り返すステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項４】
前記待つステップの後に、前記新規ノードによって受信された、以前のジェネラルディスカバリリクエストメッセージのシーケンス番号と一致するシーケンス番号を有するすべてのアクノリッジメントメッセージを前記新規ノードにより破棄するステップをさらに備えたことを特徴とする請求項２に記載の方法。
【請求項５】
前記ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つステップと、
前記アンテナを次の方向に可動するステップと、
前記ディレクショナルジェネラルディスカバリリクエストメッセージのシーケンス番号をインクリメントするステップと、
前記新規ノードにより、前記データチャネルのアンテナを経由して、前記アンテナの前記現在の方向に対応する方向に、前記データチャネルを介して、ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記第２のネットワークノードで前記ディレクショナルジェネラルディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答するステップと、
前記新規ネットワークノードで前記第２のアクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項６】
前記ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つ前記ステップと、前記アンテナを前記次の方向に可動する前記ステップと、前記ディレクショナルジェネラルディスカバリリクエストメッセージのシーケンス番号をインクリメントする前記ステップと、前記新規ノードにより、前記データチャネルのアンテナを経由して、前記アンテナの前記現在の方向に対応する方向に、前記データチャネルを介して、ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストする前記ステップと、前記第２のネットワークノードで前記ディレクショナルジェネラルディスカバリリクエストメッセージを受信する前記ステップと、前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答する前記ステップと、前記新規ネットワークノードで前記第２のアクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新する前記ステップとが、前記アンテナが完全に１回転するまで繰り返されることを特徴とする請求項５に記載の方法。
【請求項７】
前記新規ネットワークノードに対応するエントリについて前記第２のネットワークノード上のネイバロケーションテーブルを調べるステップと、
前記新規ネットワークノードに対応するエントリが存在しない場合に、前記第２のネットワークノードのネイバロケーションテーブル内に前記新規ネットワークノードに対応するエントリを作成するステップと、
前記新規ネットワークノードと前記第２のネットワークノードとの間のトラフィックの一時的な休止が生じるまで待つステップと、
前記第２のネットワークノードにより、前記制御を介して前記新規ネットワークノードにターゲテッドディスカバリリクエストメッセージを送信するステップと、
前記ターゲテッドディスカバリリクエストの送信が成功した場合に、前記第２のネットワークノードにより、前記データチャネルを介して前記新規ネットワークノードにディレクショナルターゲテッドディスカバリリクエストメッセージを送信するステップと、
前記新規ネットワークノードで前記ディレクショナルターゲテッドディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記新規ネットワークノードから前記第２のネットワークノードにアクノリッジメントメッセージを送信することによって、前記第２のノードによって送信された前記ディレクショナルターゲテッドディスカバリリクエストメッセージに応答するステップと、
前記第２のネットワークノードで前記アクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項８】
前記ネイバロケーションテーブルは、発見された近接ノードの各々についてのエントリを含み、前記エントリは、前記近接ノードの方向アンテナパターンを含むことを特徴とする請求項１に記載の方法。
【請求項９】
請求項１に記載のステップを実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読取り可能な記憶媒体。
【請求項１０】
メッシュネットワークにおける相対的なネイバロケーションをディスカバリする方法であって、
新規ネットワークノードにより前記メッシュネットワークに隣接するステップと、
前記新規ネットワークノードにより、制御チャネルを介してジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記メッシュネットワーク内の第２のネットワークノードで前記ジェネラルディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードにアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ジェネラルディスカバリリクエストメッセージに応答するステップと、
前記新規ネットワークノードで前記アクノリッジメントメッセージを受信し、ネイバロケーションテーブル内に対応するエントリを作成するステップと、
前記新規ノードにより、データチャネルのアンテナを経由して、前記アンテナの現在の方向に対応する方向に、前記データチャネルを介して、ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記第２のネットワークノードで前記ディレクショナルジェネラルディスカバリリクエストメッセージを受信するステップと、
前記新規ネットワークノードからのラウンド完了メッセージが前記第２のネットワークノードで受信されるまで、前記第２のネットワークノードでアンテナ方向を一定に保つステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答するステップと、
前記第２のアクノリッジメントメッセージを前記新規ネットワークノードで受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
を備えたことを特徴とする方法。
【請求項１１】
前記ジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つステップと、
アクノリッジメントメッセージが前記所定の時間中に前記新規ノードで受信されない場合に、前記新規ネットワークノードにより、前記制御チャネルを介して前記ジェネラルディスカバリリクエストメッセージを再ブロードキャストするステップと
をさらに備えたことを特徴とする請求項１０に記載の方法。
【請求項１２】
相対的なネイバロケーションのディスカバリを打ち切る前に、前記待つステップおよび前記再ブロードキャストするステップを指定された反復回数だけ繰り返すステップをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記待つステップの後に、前記新規ノードによって受信された、以前のジェネラルディスカバリリクエストメッセージのシーケンス番号と一致するシーケンス番号を有するすべてのアクノリッジメントメッセージを前記新規ノードにより破棄するステップをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つステップと、
前記アンテナを次の方向に可動するステップと、
前記ディレクショナルジェネラルディスカバリリクエストメッセージのシーケンス番号をインクリメントするステップと、
前記新規ノードにより、前記データチャネルのアンテナを経由して、前記アンテナの前記現在の方向に対応する方向に、前記データチャネルを介して、ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストするステップと、
前記第２のネットワークノードで前記ディレクショナルジェネラルディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答するステップと、
前記新規ネットワークノードで前記第２のアクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
をさらに備えたことを特徴とする請求項１０に記載の方法。
【請求項１５】
前記ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストした後に、前記新規ノードにより所定の時間だけ待つ前記ステップと、前記アンテナを前記次の方向に可動する前記ステップと、前記ディレクショナルジェネラルディスカバリリクエストメッセージのシーケンス番号をインクリメントする前記ステップと、前記新規ノードにより、前記データチャネルのアンテナを経由して、前記アンテナの前記現在の方向に対応する方向に、前記データチャネルを介して、ディレクショナルジェネラルディスカバリリクエストメッセージをブロードキャストする前記ステップと、前記第２のネットワークノードで前記ディレクショナルジェネラルディスカバリリクエストメッセージを受信する前記ステップと、前記制御チャネルを介して前記第２のネットワークノードから前記新規ネットワークノードに第２のアクノリッジメントメッセージを送信することによって、前記新規ノードによってブロードキャストされた前記ディレクショナルジェネラルディスカバリリクエストメッセージに応答する前記ステップと、前記新規ネットワークノードで前記第２のアクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新する前記ステップとが、前記アンテナが完全に１回転するまで繰り返されることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記新規ネットワークノードに対応するエントリについて前記第２のネットワークノード上のネイバロケーションテーブルを調べるステップと、
前記新規ネットワークノードに対応するエントリが存在しない場合に、前記第２のネットワークノードのネイバロケーションテーブル内に前記新規ネットワークノードに対応するエントリを作成するステップと、
前記新規ネットワークノードと前記第２のネットワークノードとの間のトラフィックの一時的な休止が生じるまで待つステップと、
前記第２のネットワークノードにより、前記制御チャネルを介して前記新規ネットワークノードにターゲテッドディスカバリリクエストメッセージを送信するステップと、
前記ターゲテッドディスカバリリクエストの送信が成功した場合に、前記第２のネットワークノードにより、前記データチャネルを介して前記新規ネットワークノードにディレクショナルターゲテッドディスカバリリクエストメッセージを送信するステップと、
前記新規ネットワークノードで前記ディレクショナルターゲテッドディスカバリリクエストメッセージを受信するステップと、
前記制御チャネルを介して前記新規ネットワークノードから前記第２のネットワークノードにアクノリッジメントメッセージを送信することによって、前記第２のノードによって送信された前記ディレクショナルターゲテッドディスカバリリクエストメッセージに応答するステップと、
前記第２のネットワークノードで前記アクノリッジメントメッセージを受信し、前記ネイバロケーションテーブル内の前記対応するエントリを更新するステップと
をさらに備えたことを特徴とする請求項１０に記載の方法。
【請求項１７】
前記ネイバロケーションテーブルは、発見された近接ノードの各々についてのエントリを含み、前記エントリは、前記近接ノードの送信方向アンテナパターンおよび前記近接ノードの受信方向アンテナパターンを含むことを特徴とする請求項１０に記載の方法。
【請求項１８】
請求項１０に記載のステップを実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にはコンピュータネットワークに関し、より詳細には、マルチホップ無線メッシュネットワークに関する。
【背景技術】
【０００２】
マルチホップ無線ネットワークは、過去十年間にわたって研究の対象とされてきた。独創的な研究の多くは、戦場での通信などの軍事応用分野によって動機付けられたものであった。しかし、最近になって、無線近傍ネットワーク（wireless neighborhood network）または無線メッシュネットワークの構築に対する関心の急増をもたらしているいくつかの興味深い商用の応用例が生じている。１つの例が、おそらくはＩＥＥＥ  ８０２．１１標準規格に基づくマルチホップ無線ネットワークを使用して人々の家庭に「ラストマイル（last-mile）」ブロードバンドインターネットアクセスを提供する「コミュニティ無線メッシュネットワーク（community wireless mesh network）」である。
【０００３】
そのような接続を使用可能にすることに対しては複数の利点がある。例えば、近接にあるものが、協力して、互いにパケットを転送するとき、これらは、専用の有線インターネット接続を個別にインストールする必要はないが、その代わりに、これらの近傍に配置された、有線インターネットへのより高速でよりコスト効率のよいゲートウェイを共有することができる。パケットは、動的にルートを見つけ、ある近接のノードから別の近接のノードにホップして、ゲートウェイのうちの１つを介してインターネットに達する。マルチホップ無線メッシュ技術のもう１つの利点は、新しい応用例が可能になることであり、例えば、近接にあるものが、分散バックアップ技術を協力して展開でき、したがって、壊滅的なディスク障害に起因して情報を失うことについて心配する必要がなくなる。第３の利点は、この技術が、インターネットサービスプロバイダを使用することを必要とせずに、ローカルで作成されたデータをローカルで使用することを可能にすることである。近傍コミュニティメッシュネットワーク（neighborhood community mesh network）は、キャッシングされた情報およびローカルコミュニティに関連する情報のより高速でより簡単な発信を可能にする。
【０００４】
残念ながら、実際の郊外の近傍トポロジ（neighborhood topology）および既製のＩＥＥＥ  ８０２．１１無線ハードウェアを使用するシミュレーション研究から、マルチホップ無線メッシュネットワークは、各ルータノードが単一の無線周波数トランシーバを使用する場合に、満足のいくレベルに達していないことが示されている。さらに、現行の最新無線ＬＡＮ技術は、そのようなコミュニティネットワークを可能にするために必要なレンジを提供しない。
【０００５】
コミュニティメッシュネットワークを発展し得るものにするために、メッシュネットワーク内の個々のリンクのレンジおよびメッシュネットワークの総容量の両方について改善が必要である。複数のトランシーバおよび指向性アンテナを各メッシュルータに取り付けることは、これらの目的を満たすものと期待される１つの手法である。コミュニティネットワーキングのシナリオでは、メッシュルータは屋内に配置され、コンセントに差し込むことができるので、ルータモビリティが制限され、バッテリ容量は問題ではないことに留意されたい。
【０００６】
しかし、上記の手法は、課題がないわけではない。具体的に言うと、指向性アンテナを正しく使用するためには、送信側ノードが、そのアンテナを宛先ノードの方向に向ける必要がある。さらに長いレンジの通信を可能にするために、送信側ノードおよび受信側ノードの両方が、２つのルータが通信するためにその指向性アンテナを正しい方向に向けさせる必要がある場合がある。問題は、１）送信側ノードが、宛先ノードがどこにあるかをどうやって知るかと、２）対象となる受信器が、送信側ノードがどこにあるかをどうやって知るかである。これまでに、ネイバディスカバリプロトコル（neighbor discovery protocol）の開発を目指す複数の試みがあったが、その各々が、かなりの欠点を有する。
【０００７】
ナシプリディスカバリプロトコル（Nasipuri Discovery Protocol）は、セクタライズドアンテナ（sectorized antenna）を有するノード用に設計され、ここで、ネットワーク内の各ノードは、各々が同一のビーム幅（３６０°／Ｍ）を有するＭ個のオーバーラップしない指向性アンテナを備える（例えば、非特許文献１参照）。各ノードは、移動時であっても、そのアンテナは常に同一の方位を向いていることが期待される。セクタライズドアンテナを使用するので、アイドルノード（idle node）は、そのすべてのアンテナで到達する通信をリスンすることができ、送信側ノードは、そのすべてのアンテナで送信することによってすべての方向にパケットを送信することができる。このプロトコルは、送信側ノードがメッセージを送信することを望むとき、全方向性ＲＴＳメッセージを使用し、次いで、対象となる宛先ノードが、やはり全方向的に（omni-directionally）送信されるＣＴＳメッセージをもって応答する。宛先ノードは、どのアンテナが最も強い信号を有したかを判定することによって、ＲＴＳメッセージをどのセクタから受信したかを記録し、ソースノードは、ＣＴＳメッセージに対して同一の技法を使用して、宛先ノードがどのセクタにあるかを判定する。ノードはモバイルであると仮定されるので、どのセクタを使用すべきかに関する情報は、単一のパケットを送信する間だけ記憶される。
【０００８】
ローテーショナルセクタレシーブプロトコル（Rotational Sector Receive Protocol）では、ネットワーク内の各ノードが、１つのＲＦトランシーバおよび１つのアンテナを備える。アンテナを使用して、全方向的に送受信することができ、または指向的に（directionally）送信することができる（例えば、非特許文献２参照）。アイドル時に、ノードは、全方向性センシングモードをデフォルトとし、パケットを感知するとき、ローテーショナルセクタレシーブモードに切り替える。ローテーショナルモードでは、アンテナを順次４５°インクリメントして切り替えて、ノードの周囲の３６０度空間全体をカバーする。
【０００９】
特定の近接ノードを探し出すために、イニシエータノードは、制御パケットに先立つ２００マイクロ秒の信号トーンとともに各制御パケットを送信する。このトーンを感知するとき、宛先ノードは、そのアンテナをローテーショナルモードに切り替え、すべての可能な方向で指向的にトーンを受信する。ノードは、異なる方向における信号強度を調べて、最大の信号強度を提供する方向に止まる。次いで、そのノードは、後続データを受信するためにその方向にビームをセットする。トーンの持続時間は、宛先ノードがそのビームを３６０°回転し、その別個の方向の各々でトーンを受信できるようにするほど十分に長い。位置を決定すると、ノードは、そのアクティブノードリスト（Active Node List）（ＡＮＬ）に情報を格納する。すべてのノードが、周期的に、トーン信号に続いてＡＮＬを全方向にブロードキャストする。これは、そのノードの位置キャッシュ内の位置情報の妥当性を維持するのに役立つ。送信の方向を含むＲＴＳ／ＣＴＳ（Ｒｅｑｕｅｓｔ  ｔｏ  Ｓｅｎｄ／Ｃｌｅａｒ  ｔｏ  Ｓｅｎｄ）交換が、全方向性アンテナ全体にわたって行われて、通信の開始に関して近接ノードに知らせ、パケット衝突の可能性を減らす。
【００１０】
ここで、このプロトコルは、送信側が送信中であり、受信側がアイドルである場合だけを規定している。すなわち、受信器は、全方向的に（in an omni-directional way）リスンしている。説明されていないのは、受信器が進行中の通信でビジーである可能性がある場合である。そのような場合に、受信器は、その近接送信側のディスカバリメッセージを受信し、これに応答することができず、したがって、発見されなくなる。さらに、このプロトコルは、一定のオーバーヘッドを有する。受信器が最初のトーンを受信するとき、実際の制御パケットを受信する前に、２００マイクロ秒が完全に経過しなければならない。この手法のもう１つの重大な欠点は、互いに全方向のレンジ内にあるノードの間のネイバディスカバリだけが可能になることである。したがって、指向性アンテナを使用して可能になるべきレンジの通信よりも長いレンジの通信は可能にならない。
【００１１】
サーキュラＲＴＳプロトコル（Circular RTS Protocol）（例えば、非特許文献３参照）では、ネットワーク内の各ノードは、１つのＲＦトランシーバと、全方向的に、または指向的に受信できるが、指向的にしか送信できない１つのアンテナとを備える。アンテナの他の詳細は、このプロトコルについては示されていない。モデルは、全方向性送信（omni-directional transmission）を、連続する順次指向性送信（sequential directional transmission）を用いて達成することである。パケット受信時に、ノードは、そのパケットが着信した方向を突き止める能力と定義される選択ダイバーシチ（selection diversity）を使用することができる。選択ダイバーシチは、最大の信号電力を感知するアンテナ要素の組合せを選択することによって可能となる。このアンテナモデルは、従来のセクタライズドアンテナではないが、多数の類似性を有する。
【００１２】
このプロトコルでは、送信器が、可能な方向の各々で１回、事前定義のシーケンスでＲＴＳパケットを連続して送信し、そのノードの周囲のエリア全体をカバーすることによって開始する。近接ノードの各々が、全方向的にこのＲＴＳを受信する。ＲＴＳ受信時に、宛先ノードは、選択ダイバーシチを使用して、送信器の方向を判定し、そのアンテナを送信器に向ける。宛先ノードは、送信器がサーキュラＲＴＳの送信を完了するのを待ち、次いで、ＲＴＳ送信器の方向にＣＴＳを送信することによって応答する。ＲＴＳ送信器は、全方向的にＣＴＳを受信し、選択ダイバーシチを使用して、ＣＴＳパケットが着信した方向を判定する。次いで、送信器は、アンテナビームをその方向に向ける。送信器および受信器の方向がわかると、これらのノードは、その位置を「ロケーションテーブル（Location Table）」に保存する。
【００１３】
ここで、このプロトコルは、アンテナ技術に関する重大な仮定をおく。例えば、このプロトコルは、選択ダイバーシチ、および、ごくわずかなスイッチング時間に強く依拠する。全方向性アンテナを用いて選択ダイバーシチがどれほど簡単に実装されるかははっきりとしない。さらに、このプロトコルは、ビームスイッチング時間がごくわずかではない場合を規定していない。遅いスイッチング時間は、単純なディスカバリプロトコルではそれほど問題ではないが、このスキームのようにディスカバリプロトコルがＭＡＣ（メディアアクセス制御）に結び付けられている場合には、スイッチング時間が性能に影響を及ぼす可能性がある。この提案されたスキームのもう１つの欠点は、指向性サーキュラＲＴＳの完了と、後続ＣＴＳ応答との調整に必要な微細な時間同期化要件（time synchronization requirement）である。宛先ノードは、ＲＴＳパケットの一部として含まれるビーム番号（１．．．Ｍ）を調べることによって、ＲＴＳがいつ終了するかを判定する。もう１つの問題は、このプロトコルが、非対称リンクの場合に対処しないことである。また、このプロトコルは、アンテナビームのオーバーラップしない方向を考慮している。実際には、これはほとんど達成できない。この要件を厳密に満たすことができない場合には、プロトコル変更が必要である。この手法のもう１つの重大な欠点は、このプロトコルが、２つのノードが両方のアンテナが正しく向けられているとき、その方向への送信およびその方向からの受信を介した通信でしか、その２つのノードの間の通信を可能にしないことである。
【００１４】
ＵＤＡＡＮディスカバリプロトコル（UDAAN Discovery Protocol）（例えば、非特許文献４参照）は、切替型のビームアンテナと、可動型（steerable）の指向性アンテナとを区別せず、両方にビームフォーミング（ＢＦ）アンテナという名称を付けている。このプロトコルは、ノードが、ａ）全方向的にしか送信できず、全方向的にしか受信できない（Ｎ−ＢＦ）、ｂ）指向的に送信できるが、全方向的にしか受信できない（Ｔ−ＢＦ）、および、ｃ）指向的に送信でき、指向的に受信できる（ＴＲ−ＢＦ）、混合モードネットワークを考慮している。
【００１５】
このネットワーク内の各ノードは、「ハロー」メッセージを周期的にブロードキャストする。ノードは、これらのハートビートメッセージを受信することによって、別のノードが存在することを知る。Ｎ−ＢＦの場合においては、これは、従来のネイバディスカバリ技法に帰着される。Ｔ−ＢＦおよびＴＲ−ＢＦについては、このプロトコルにより、２つのディスカバリ方法すなわち、インフォームドディスカバリ（informed discovery）およびブラインドディスカバリ（blind discovery）が説明されている。この２つの間の相違は、ノードが宛先ノードの存在について知っているかどうかに関連する。インフォームドＴ−ＢＦおよびインフォームドＴＲ−ＢＦについては、ノードは、宛先ノードがあると考えられるおおよその方向にアンテナを向けることによって、ノード自体の位置を含む指向性ハートビートを送信する。ターゲットノードは、全方向的にこのハートビートを受信し、メッセージから送信側ノードの位置を判定し、次いで、開始ノードに向けてそれ自体のハートビートを送信する。ブラインドＴ−ＢＦについては、ノードは、すべての可能な方向をスキャンし、事前に規定した時間間隔で各方向にハートビートを送信する。ターゲットは、このメッセージを受信するとき、ブラインドハートビートのイニシエータによりインフォームドＴ−ＢＦプロセスを開始する。ブラインドＴＲ−ＢＦを用いてネイバディスカバリを達成する際に、このプロトコルは、おそらくはＧＰＳ（全地球測位システム）などの共通のクロックソースを用いて、すべてのノード上のクロックが同期化されていることを必要とする。周期的に、すべてのノードが、同時にブラインドＴＲ−ＢＦディスカバリとやり取りする。ある方向が、時刻に基づいて選択され、各ノードは、その方向へのハートビートの送信と、反対方向におけるそのようなハートビートのリスンとを、ランダムに交互に行う。１つの完全なサイクルの後に、すべてのＴＲ−ＢＦ近接ノードが発見される。ブラインドＴＲ−ＢＦディスカバリは、２次元でのみ正常に機能する。
【００１６】
【非特許文献１】A. Nasipuri, S. Ye, J. You, and R.E. Hiromoto, "A MAC Protocol for Mobile Ad Hoc Networks Using Directional Antennas", IEEE WCNC 2000, September 2000
【非特許文献２】Somprakash Bandyopadhyay, Dola Sana, Siuli Roy, Tetsuro Ueda, and Shinsuke Tanaka, "A Network-Aware MAC and Routing Protocol for Effective Load Balancing in Ad Hoc Wireless Networks with Directional Antenna", ACM MobiHoc 2003, June 2003
【非特許文献３】T. Korakis, G. Jakllari, and L. Tassiulas "A MAC Protocol for Full Exploitation of Directional Antennas in Ad-hoc Wireless Networks", ACM Mobihoc 2003, June 2003
【非特許文献４】Ram Ramanathan, Jason Redi, Cesar Santivanez, David Wiggins, Stephen Polit "Ad Hoc Networking with Directional Antennas: A Complete System Solution", IEEE Journal on Selected Areas in Communications, vol. 23, no. 3, March 2005
【発明の開示】
【発明が解決しようとする課題】
【００１７】
以上のように、上記のネイバディスカバリプロトコルのアンテナハードウェアまたは動作は非常に複雑であること、および、コストが高いことに起因して、各プロトコルには、望まれる点が多い。したがって、ノードがメッシュネットワーク内の近接ノード（単一ホップをもって直接に到達可能なノード）の相対位置を効率的かつ効果的に判定することができる方法が必要とされる。本発明は、そのような方法を提供する。本発明の上記および他の利点ならびに追加の発明的特徴は、本明細書で提供する本発明の記載から明白になるであろう。
【課題を解決するための手段】
【００１８】
上記に鑑みて、本発明は、メッシュネットワーク内のノードの相対位置を判定するネイバロケーションディスカバリプロトコル（Neighbor Location Discovery Protocol）（ＮＬＤＰ）を提供する。一実施形態では、本発明のネイバロケーションディスカバリプロトコルは、ノードが指向性アンテナを備え、ＧＰＳを使用できないアドホック無線ネットワーク用に設計されている。開示するプロトコルは、ルータノードのハードウェア構成の相違の結果として、以前に提案されたプロトコルに比べて重要な利点を提供する。ＮＬＤＰは、少なくとも２つのＲＦトランシーバを有するノードに依拠するが、以前のプロトコルは、１つのＲＦトランシーバだけしか使用しない。
【００１９】
アンテナの複雑さと、収束速度と、トランシーバの個数との間にはトレードオフが存在する。ＮＬＤＰでは、アンテナハードウェアは、単純であり、実装しやすく、容易に入手できる。さらに、ＮＬＤＰは、オーバーラップしないチャネルにわたって同時に動作するホストノードの能力を活用し、急速に近接ノードの位置に収束する。以前の提案の一部と異なって、新たな近接ノードを発見するための単一の無線解決策に関連する不利益はない。最後に、ノードを探し出すと、送信側と将来の宛先ノードがアンテナを異なる方向に向けていて、他のノードと通信している間であっても、複数のトランシーバが、送信側に指向性アンテナを向けるよう「将来の」宛先ノードに知らせる可能性を提供する。
【００２０】
ＮＬＤＰは、全方向的に機能する制御チャネルのレンジによって制限される。しかし、低周波帯域、高電力、および低データレートを選択することによって、適切な方向を向いた指向性アンテナが送信器と受信器の両方によって使用されるとき、全方向性制御チャネルレンジ（omni-directional range of the control channel）を、データチャネルのレンジと一致する（または、それより大きくなる）ように広げることができる。最後の考慮事項として、追加のトランシーバは、ノード上で電力浪費を引き起こす可能性があるが、コミュニティネットワーキングシナリオなどのシナリオでは、バッテリ容量は問題ではない。これは、ルータを近傍の屋内で無限の電源元（コンセント）の近くに配置することができるという事実によるためである。
【発明を実施するための最良の形態】
【００２１】
特許請求の範囲に本発明の特徴を詳細に示すが、図面と併せて以下の詳細な説明を解釈されることから、本発明は、その目的および利点と共に、最もよく理解されるであろう。
【００２２】
以下の説明では、別段の指示がない限り、１つまたは複数のコンピューティングデバイスによって実行される動作およびオペレーションの記号表現を参照して本発明を説明する。したがって、時にはコンピュータにより実行されていると呼ばれるそのような動作およびオペレーションには、構造化された形のデータを表現する電気信号のコンピューティングデバイスの処理装置による操作が含まれることを理解されたい。この操作は、データを変換するか、または、コンピューティングデバイスのメモリシステム内の位置でデータを保持し、これによって、コンピューティングデバイスの動作が当業者によってよく理解される形で再構成されまたは他の形で変更される。データがそこで保持されるデータ構造は、データのフォーマットによって定義される特定の特性を有するメモリの物理的位置である。しかし、本発明を、前述のコンテキストにおいて説明しているが、以下で説明する複数の動作およびオペレーションをハードウェアでも実装できることを当業者なら理解するので、これは、限定的であることを意味しない。
【００２３】
図面に移ると、類似する符号は類似する要素を指すが、本発明は、適切なコンピューティング環境で実装されるものとして示されている。以下の説明は、本発明の例示的な実施形態に基づくが、本明細書に明示的に記載されていない代替実施形態に関して本発明を限定するものと解釈されるべきではない。
【００２４】
Ｉ．例示的な環境
図１を参照すると、本発明は、接続されたコンピュータネットワーク上のネットワークノード間の通信に関する。ネットワークノードの各々は、多数の異なるコンピュータアーキテクチャのうちの１つを有することができるコンピューティングデバイス内に存在する。説明のために、図１は、これらのデバイスのために使用できる例示的なアーキテクチャの概略図を示す。図示したアーキテクチャは、適切な環境の一例にすぎず、本発明の使用または機能の範囲に関して限定を示唆することを意図するものではない。図１に例示したコンポーネントのうちのいずれか１つ、または、その組合せに関して、このコンピュータデバイスが何らかの依存関係、または、要件を有するものと解釈すべきではない。本発明は、多数の他の汎用または専用コンピューティング環境、コンピューティング構成、通信環境、または通信構成と共に動作する。本発明と共に使用するための適切な周知のコンピューティングシステム、コンピューティング環境、およびコンピューティング構成の例には、携帯電話、ポケットコンピュータ、パーソナルコンピュータ、サーバ、マルチプロセッサシステム、マイクロプロセッサベースシステム、ミニコンピュータ、メインフレームコンピュータ、および上記のシステムまたはデバイスのいずれかを含む分散コンピューティング環境が含まれるが、これらに限定はされない。
【００２５】
その最も基本的な構成では、コンピューティングデバイス１００には、通常、少なくとも１つの処理装置１０２およびメモリ１０４が含まれる。メモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭおよびフラッシュメモリなど）、または、この２つの所定の組合せとすることができる。この最も基本的な構成が、図１では、破線１０６によって示されている。
【００２６】
コンピューティングデバイス１００はまた、追加の特徴および機能を有することができる記憶媒体デバイス１０８および１１０も備えることができる。例えば、これらは、（取外し可能な、および、固定の）追加ストレージを含むことができ、これらの追加のストレージには、ＰＣＭＣＩＡカード、磁気ディスク、光ディスク、および磁気テープが含まれるが、これらに限定されない。そのような追加ストレージは、図１では、取外し可能なストレージ１０８および固定ストレージ１１０によって例示されている。コンピュータ記憶媒体には、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または他のデータなどの情報の記憶のために任意の方法または技術で実装された、揮発性媒体および不揮発性媒体、取外し可能な媒体および固定媒体が含まれる。メモリ１０４、取外し可能なストレージ１０８、および固定ストレージ１１０はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク、他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、他の磁気ストレージデバイス、および所望の情報を保存するのに使用でき、コンピューティングデバイスによってアクセスできる任意の他の媒体が含まれるが、これらに限定はされない。
【００２７】
コンピューティングデバイス１００はまた、このデバイスが他のデバイスと通信できるようにする通信チャネル１１２を備えることもできる。通信チャネル１１２は、通信媒体の例である。通信媒体は、通常、コンピュータ読取り可能命令、データ構造、プログラムモジュール、または他のデータを、搬送波や他の移送機構などの被変調データ信号として表現したものであって、すべての情報配信媒体を含む。用語「被変調データ信号」は、信号中の情報を符号化するような方式で設定または変更された特性の１つまたは複数を有する信号を意味する。例えば、通信媒体には、有線ネットワークおよび直接配線接続などの有線媒体と、音波、無線、赤外線、および他の無線媒体などの無線媒体とが含まれる。本明細書で使用する用語コンピュータ読取り可能媒体には、記憶媒体と通信媒体の両方が含まれる。コンピューティングデバイス１００はまた、キーボード、マウス、ペン、音声入力コンポーネント、および接触入力デバイスなどの入力コンポーネント１１４を備えることもできる。出力コンポーネント１１６には、スクリーンディスプレイ、スピーカ、プリンタが、およびこれらを駆動するための（しばしば、「アダプタ」と呼ばれる）レンダリングモジュールが含まれる。コンピューティングデバイス１００は、電源１１８を備える。これらのコンポーネントはすべて、当技術分野で周知であり、ここで詳細に説明される必要はない。
【００２８】
ＩＩ．ノード構成
本発明は、メッシュネットワーク内のコンピューティングデバイスノードの相対位置を判定するネイバロケーションディスカバリプロトコル（ＮＬＤＰ）を対象とする。ＮＬＤＰを説明する前に、まず、メッシュネットワーク内の各ノードのハードウェア構成を説明する。
【００２９】
ネットワーク内の各ノードは、少なくとも２つの無線周波数（ＲＦ）トランシーバを有するように構成される。これらのトランシーバのうちの１つまたは複数は、高周波数帯域（例えば、５ＧＨｚ帯域）で動作し、１つのトランシーバは、低周波数帯域（例えば、７００ＭＨｚ帯域）で動作する。これらのトランシーバは、それぞれデータチャネル無線として、および制御チャネル無線として設計される。すべてのノードが、これらのチャネルを介して同時に通信することができる。
【００３０】
制御チャネル無線は、全方向送信全方向受信（omni-send-omni-receive）（ＯＳＯＲ）モードで機能し、データチャネル無線は、２つのモード、すなわち、一方向送信全方向受信（directional-send-omni-receive）（ＤＳＯＲ）モード、または、一方向送信一方向受信（directional-send-directional-receive）（ＤＳＤＲ）モードのうちの１つで機能する。ＯＳＯＲモードにおける制御チャネル無線のレンジは、ＤＳＯＲモードまたはＤＳＤＲモードにおけるデータチャネル無線のレンジより大きいか、または等しい。この要件は、送信電力を適切に管理することにより、および、ＲＦ信号が低周波数帯域での方が高周波数帯域よりはるかに良く伝搬するということにより確実にされる。
【００３１】
データチャネルにおける指向性アンテナは、Ｋ°単位で可動できる。Ｗ°のビーム幅を仮定し、Ｋ＜Ｗであることが望ましい。さらに、指向性アンテナを可動する（steer）には、中程度のコストがかかり、Ｋ°の回転の各々は、完了にＴｓｔｅｅｒミリ秒を要すると仮定する。
【００３２】
制御チャネルは、データチャネル（例えば、すべてのデータチャネルについては２００ＭＨｚ、データチャネルごとに２０ＭＨｚ）と比較して、非常に小さなスペクトル（例えば、１から２ＭＨｚ）を必要とする。したがって、制御チャネル送信レートは、データチャネル送信レート（例えば、５４Ｍｂｐｓまで）よりかなり低い（例えば、１Ｍｂｐｓ）。ＲＦトランシーバは、複数の異なるデータレート（例えば、６、９、１２、１８、２４、３６、４８、および５４Ｍｂｐｓ）のうちのいずれのレートでも動作することができるので、無線のレンジは、固定された送信レートで測定される。したがって、データレートの動的変化のためにレンジが変化するチャネルを扱う必要はない。
【００３３】
本発明の複数の可能な実施形態のうちの１つでは、搬送波検知多重アクセス（ＣＳＭＡ）ＭＡＣが、制御チャネルおよびデータチャネルのために使用される。しかし、ＮＬＤＰは、ＭＡＣの選択によって制限されないことに留意されたい。さらに、メッシュルータノードのための一般的な構成では、３つのＲＦレシーバを使用するかもしれないが、正しいオペレーションのために、本発明のプロトコルは、２つのトランシーバ（制御チャネル用に１つ、データチャネル用に１つ）のみを用いて実装することができる。したがって、このプロトコルは、２つのトランシーバのみを用いて実装されるものとして説明する。
【００３４】
ＩＩＩ．ネイバロケーションディスカバリプロトコル
まずはじめに、ＮＬＤＰについて、本明細書ではネイバロケーションディスカバリに関して説明することに目を向けることは価値がある。近接ノードの位置を判定すると、所与の時点でアンテナをどこに向けるかを最終的に決定するのは、ルーティングプロトコルである。まず、ＮＬＤＰを、ＤＳＯＲ構成（一方向送信全方向受信）を使用するノードについて説明し、次いで、ＤＳＤＲ構成（一方向送信一方向受信）にも対応するように拡張する。
【００３５】
通常、メッシュネットワークに参加する新規ノードは、セットアップの一部としてネイバロケーションディスカバリを開始する。既にメッシュのメンバであるノードは、ａ）まだ近接ノードのテーブルに含まれていない新規ノードの存在を知り、それを探し出すことを望むとき、またはｂ）ネイバロケーションテーブル（以下で説明する）のエントリが失効したとき、ネイバロケーションディスカバリを開始することができる。失効は、そのノードに対してターゲテッドネイバディスカバリ（targeted neighbor discovery）を始動させる。失効時間は、複数のエントリの同時失効を防ぐためにランダム化されている。
【００３６】
各メッシュノードは、ネイバロケーションテーブルを保持し、このテーブルには、近接ノードに関する情報が含まれる。各近接ノードは、ノードＩＤによって識別され、このノードＩＤは、ＤＮＳ名、ＩＰアドレス、ＭＡＣアドレスなどのうちの１つまたは複数とすることができる。ノードＩＤに関連するのが、このノードにデータを送信するためにアンテナを向けなければならない方向である。方向は、その特定の近接ノードに達するためにアンテナをそのベース位置から時計回りの方向に切り替えなければならない連続する切替の回数を表す数値である。このエントリには、この近接ノードがホストノードとの成功した通信に最後にかかわったときを示すタイムスタンプも含まれる。ネイバロケーションテーブル内のエントリは、所定の時間の間その近接ノードに伴うアクティビティがない場合に失効する。ネイバロケーションテーブルの内容の例を、以下の表１に示す。
【００３７】
【表１】
2006279951.tif 000003
【００３８】
表１における最初のレコードは、ノード０×３４が、デフォルトベース位置から３回アンテナを可動することによって到達可能であると解釈することができる。このレコードに、ノード０×３４が最後に「目撃」されたのが午後１時６分２９秒であることも示されている。このノードが複数のデータチャネル無線を有する場合、近接ノードはトランシーバ−アンテナ対識別子（transceiver-antenna pair identifier）（例えば２）を介して到達可能であり、このテーブルはトランシーバ−アンテナ対識別子を含むカラムをもって拡張されることに留意されたい。
【００３９】
ＮＬＤＰは、そのオペレーションにおいて７つのメッセージを使用する。ジェネラルディスカバリリクエスト（General Discovery Request）（ＧＤＲ）は、制御チャネルを介して送信されるブロードキャストメッセージである。これには、送信側のノードＩＤ、ローカルタイムスタンプ、およびリクエストシーケンス番号が含まれる。リクエストシーケンス番号は、ノードがＧＤＲメッセージを送信するたびにインクリメントされる。ＧＤＲ−ＡＣＫは、制御チャネルを介して送信されるユニキャストメッセージである。ＧＤＲを受信した各ノードは、ＧＤＲ−ＡＣＫをもって応答する。ＧＤＲ−ＡＣＫには、ＧＤＲメッセージからのタイムスタンプおよびラウンド番号のエコーが含まれる。ＧＤＲ−ＡＣＫには、そのＧＤＲ−ＡＣＫを送信するノードのノードＩＤ情報も含まれる。
【００４０】
ターゲテッドディスカバリリクエスト（Targeted Discovery Request）（ＴＤＲ）は、制御チャネルを介して送信されるユニキャストメッセージである。このメッセージは、特定のノードを探し出すのに使用されることを除いて、ＧＤＲに類似している。ＴＤＲは、ターゲットのＩＤが既知である場合に限って送信できることに留意されたい。制御チャネルはＭＡＣレベルのアクノリッジメント（acknowledgement）をサポートすると仮定されているので、ＴＤＲ−ＡＣＫメッセージはない。
【００４１】
ディレクショナルジェネラルディスカバリリクエスト（Directional General Discovery Request）（ＤＧＤＲ）は、ある方向に向けられたアンテナによってデータチャネルを介して送信されるブロードキャストメッセージである。このメッセージは、ＧＤＲメッセージを送信し、少なくとも１つのＧＤＲ−ＡＣＫを受信した後でしか送信することができない。このメッセージには、ノードＩＤ、タイムスタンプ、およびこのノードがＤＧＤＲメッセージまたはＤＴＤＲメッセージを送信するたびにインクリメントされるシーケンス番号が含まれる。ＤＧＤＲ−ＡＣＫは、ＤＧＤＲメッセージに応答して制御チャネルを介して送信されるユニキャストメッセージである。このメッセージには、ＤＧＤＲメッセージからのすべてのデータのエコー、ならびに、このＤＧＤＲ−ＡＣＫを送信するノードのＩＤが含まれる。
【００４２】
ディレクショナルターゲテッドディスカバリリクエスト（Directional Targeted Discovery Request）（ＤＴＤＲ）は、データチャネルを介して特定のターゲットに送信されるユニキャストメッセージである。これは、ＴＤＲメッセージの後に送信されることを除いて、ＤＧＤＲに類似している。ＤＴＤＲ−ＡＣＫは、ＤＴＤＲメッセージに応答して制御チャネルを介して送信されるユニキャストメッセージである。メッセージフォーマットは、ＤＧＤＲ−ＡＣＫに類似している。以下の表２に、どのメッセージがどのチャネルを介して送信されるかが要約されている。
【００４３】
【表２】
2006279951.tif 000004
【００４４】
ＮＬＤＰプロトコルは、２フェーズで動作する。フェーズ１では、このプロトコルは、近接ノードが存在するかどうかを判定する。フェーズ２では、このプロトコルは、これらのノードの位置を判定する。このプロトコルが、異なるレンジを有する異なる周波数帯域で動作する２つのＲＦトランシーバを利用するという事実に起因して、隣接ノードを発見できるが、隣接ノードは到達可能でないことがあり得る。
【００４５】
図２、３、４、および５に移ると、多数のノードを有する例示的なコミュニティメッシュネットワークが例示されている。新規ノード（図では、目立つノードとして示されている）がメッシュに参加しようとしている場合、新規ノードの指向性アンテナは、ある任意の方向に向けられる。ネットワークに参加する際に、新規ノードは、図２、３、４、５、および６に示したイベントのシーケンスを経る。
【００４６】
フェーズ１、すなわち、近接ノードが存在するかどうかの判定は、新規ノード１００が制御チャネル２０２を介してＧＤＲメッセージ２００をブロードキャストするとき、ステップ６００で開始される。ＧＤＲメッセージ２００を送信した後に、新規ノード１００は、ステップ６０２で、ＧＤＲ−ＡＣＫメッセージ３００を受信するために、事前定義の時間ＴｂｄｇｒＷａｉｔだけ待つ。次に、ステップ６０４で、新規ノード１００は、ＧＤＲ−ＡＣＫ  ３００がこの時間の間に受信されなかった場合に、ＧＤＲメッセージ２００を再送信する。これは、ステップ６０６で指定された回数だけ繰り返され、その後、新規ノード１００は、ステップ６０８でこのディスカバリプロトコルを打ち切る。不要な複製（spurious duplication）または遅いＧＤＲ−ＡＣＫ  ３００からそれ自体を保護するために、新規ノード１００は、ＧＤＲメッセージ２００が送信されてからＴｂｄｇｒＷａｉｔの時間だけ後に受信したすべてのＧＤＲ−ＡＣＫ  ３００を破棄する。シーケンス番号を使用して、この待機期間中に生じた、以前のＧＤＲメッセージ２００からの任意のＧＤＲ−ＡＣＫ  ３００を無視することができる。ステップ６１０でＧＤＲメッセージ２００を受信したとき、メッシュノード１００が、ステップ６１２でＧＤＲ−ＡＣＫメッセージ３００をもって応答する。ＧＤＲ−ＡＣＫ  ３００はユニキャストされるので、制御チャネルＭＡＣが、衝突の解決および再送信を自動的に試みると仮定することができる。続いて、ステップ６１４で、受信したＧＤＲ−ＡＣＫ  ３００の各々について、新規ノード１００は、そのネイバロケーションテーブル３０２内にエントリを作成する。アンテナ方向を除くすべての値が、この時点で書き込まれる。アンテナ方向は、未知として入力される。
【００４７】
フェーズ２、すなわち、近接ノードの位置の判定は、ＴｂｄｇｒＷａｉｔ時間だけ待った後に、ステップ６１６で新規ノード１００が、データチャネル４０２を介してデータチャネル無線アンテナが向いている方向にＤＧＤＲメッセージ４００をブロードキャストするとき開始される。ＤＧＤＲメッセージ４００はブロードキャストされるので、限られた量の衝突回避だけしか提供されず、自動再送信がされない可能性が高い。やはり、ＧＤＲメッセージ２００と同様に、ノード１００は、必要な場合に、それ自体のハイレベル再送信を行うことができる。これは、このセクタ内に実際にノード１００がまったくない場合があるという事実によって複雑になり得る。ＤＧＤＲメッセージ４００を送信した後に、ステップ６１８において、新規ノード１００は、時間ＴｇｎｄｒＷａｉｔだけ待った後に、次の方向にアンテナを可動する。次に、ステップ６２０で、新規ノード１００は、ＤＧＤＲシーケンス番号をインクリメントし、ブロードキャストプロセスを繰り返す。
【００４８】
続いて、ステップ６２２で、ＤＧＤＲメッセージ４００を受信したいずれかのノード１００は、ステップ６２４で、ＤＧＤＲ−ＡＣＫ  ５００をもって制御チャネル２０２を介して応答する。このＤＧＤＲ−ＡＣＫメッセージ５００は、新規ノード１００にユニキャストされ、やはり、新規ノード１００は、通常のＭＡＣレベル機構に依拠して、配信を部分的に確実にすることができる。ＤＧＤＲ−ＡＣＫ  ５００が着信すると、新規ノード１００は、ステップ６２６でそのネイバロケーションテーブル３０２を更新する。ＤＧＤＲ−ＡＣＫ  ５００は、ＤＧＤＲメッセージ４００のシーケンス番号のエコーを保持するので、新規ノード１００は、このＤＧＤＲ−ＡＣＫ  ５００がどのＤＧＤＲメッセージ４００に対応するか（したがって、アンテナがどこを指していたか）を必ず知ることになる。したがって、ＤＧＤＲ−ＡＣＫ  ５００は、任意の順序で着信することができる。これによって、応答するノード１００が自分のペースでＤＧＤＲ−ＡＣＫ  ５００を送信することも可能になる。ここで、タイムアウトが必要である。というのは、送信された可能性がある非常に古いＧＤＲメッセージ２００に対応するＤＧＤＲ−ＡＣＫ  ５００の受け入れは望ましくないからである。現在時刻がｔであると仮定すると、新規ノード１００が、現在のＤＧＤＲシーケンス番号未満のシーケンス番号を保持し、ｔ−３＊（ＴｇｎｄｒＷａｉｔ＋Ｔｓｔｅｅｒ）以内に送信されたことをタイムスタンプが示すＤＧＤＲ−ＡＣＫ  ５００をもってネイバロケーションテーブル３０２を更新しなければならないことを提案することができる。
【００４９】
新規ノード１００は、アンテナの１回転（すなわち、３６０°全体）を終えると、ネイバロケーションテーブル３０２のエントリの多くを書き込まなければならない。残りのエントリのすべてが、この時点で破棄されることが好ましい。これは、ＯＳＯＲモードにおける制御チャネル２０２のレンジが、ＤＳＯＲモードにおけるデータチャネル４０２のレンジより大きくなり得るという事実に起因する。したがって、データチャネル４０２での通信の見込みがないノード１００からのＧＤＲ−ＡＣＫ  ３００が受信された可能性がある。ことによるとＤＧＤＲ−ＡＣＫ  ５００をまったく届けることができなかったいくつかの近接ノード１００を見過ごす危険性があるが、その可能性は無視できる。さらに、このディスカバリプロセスは、周期的に行うことができ、その時点で、前のラウンドでＤＧＤＲ−ＡＣＫ  ５００をまったく届けることができなかったノード１００が発見される可能性が高い。
【００５０】
新規ノード１００からＤＧＤＲメッセージ４００を受信した各ノード１００は、それ自体のネイバロケーションテーブル３０２を調べて、その新規ノード１００にどのように送信すべきかを知っているかどうかを確かめる。その新規ノード１００に関するエントリが存在しない場合には、アンテナ方向に未知をセットしたエントリを作成する。どちらの場合でも、ノード１００は、それ自体のターゲテッドディスカバリプロセスを開始して、その新規ノード１００と通信する方法を見つけなければならない。これは、次のように行われる。ノード１００が、新規ノード１００からＤＧＤＲ  ４００を受信したばかりであり、ＤＧＤＲ−ＡＣＫ  ５００をもって応答したと仮定すると、ノード１００は、現在、新規ノード１００を探し出そうとしている。ノード１００は、そのディスカバリを開始する準備ができるまで待つ。ディスカバリは、潜在的にアンテナの可動を必要とする可能性があるので、進行中の通信を中断する。反対に、ノード１００は、ディスカバリを開始する前に、トラフィックの一時的な休止（lull in the traffic）が生じるまで待たなければならない。ここにはトレードオフがあり、新規ノード１００への方向を見つけることは、潜在的に新しいよりよい位置情報をもたらす可能性があるが、進行中の通信がその過程で損なわれる可能性もある。
【００５１】
ここで、ノード１００が、制御チャネル２０２を介してＴＤＲメッセージを送信する。このメッセージはユニキャストされるので、基礎になるＭＡＣ再送信機構が、より高い度合の配信の信頼性を達成するのを助けることに留意されたい。しかし、望まれる場合に、その上にさらなる再送信機構を追加することができる。制御チャネルＭＡＣがＭＡＣレベルＡＣＫを送信すると仮定される場合に、ＴＤＲ−ＡＣＫメッセージの必要がないことにも留意されたい。ＴＤＲの送信が成功した場合に、ノード１００は、ＤＴＤＲメッセージを送信する。新規ノード１００に送信するためのアンテナの位置がわかっている場合には、そのセクタを最初に試すことができ、アンテナの位置がわかっていない場合には、ＤＧＤＲに類似した全回転捜索が実行される。
【００５２】
上記で説明したＮＬＤＰプロトコルは、ＤＳＯＲ構成用に設計されており、一方向送信一方向受信（ＤＳＤＲ）の場合を処理しない。この理由は、ノードがＤＧＤＲメッセージまたはＤＴＤＲメッセージを送信するとき、必ず、受信器がそのメッセージを受信できると仮定されるからである。ＤＳＤＲ構成においては、受信器が、ディスカバリ要求を受信するために、そのアンテナを正しい方向に向けていることを確実にしなければならない。
【００５３】
この場合を処理するために、次の変更を行うことができる。まず、ネイバロケーションテーブルを変更して、２つの方向すなわち送信方向および受信方向を含めることができる。一般的な場合に、この２つの方向は同一であるが、必ずそうであるという保証はない。ディスカバリプロトコルは、「ラウンド」に分割することによって変更することもでき、この場合に、単一のラウンド内で、発見するノードが、ＤＧＤＲメッセージを繰り返してブロードキャストし、各ＤＧＤＲメッセージを送信した後に次の位置にアンテナを回転し、その間、対象となる受信側のすべては、そのアンテナ方向を一定に保つ。１ラウンドが終わるのは、発見するノードが３６０°全体を回転し終えたときであり、その時点で、発見するノードは、制御チャネルを介してＮＥＸＴＲＯＵＮＤメッセージをブロードキャストして、対象となるすべての受信側に、それらの受信側が次の位置にアンテナを回転しなければならないことを示す。Ｋが、ノードがそのアンテナを回転する度数である場合、ディスカバリプロセスが終了する前に３６０／Ｋ  回のラウンドが必要であり、各ラウンド内に、発見するノードは３６０／Ｋ  個のＤＧＤＲメッセージを送信する。ＮＬＤＰのＤＳＯＲバージョンと同様に、ディスカバリメッセージには、送信側（すなわち、発見するノード）が、ＤＧＤＲメッセージを送信したときアンテナがどの方向を向いていたかを判定するのに使用するシーケンス番号が含まれる。受信側は、ＤＧＤＲメッセージを受信したとき、そのネイバテーブルの「受信方向」フィールドに、そのアンテナが向いていた方向を記録し、そのＤＧＤＲメッセージが首尾よく配信されたとき向いていた「送信方向」を送信側が記録できるようにするために、送信側のシーケンス番号を含むＤＧＤＲ−ＡＣＫメッセージをもって制御チャネルを介して応答する。前のＤＳＯＲプロトコルと同様に、このプロトコルは、ＤＴＤＲメッセージを伴うターゲテッドディスカバリもサポートする。前と同様に、ＤＧＤＲとＤＴＤＲとの主要な相違は、ＤＴＤＲメッセージおよびＮＥＸＴＲＯＵＮＤメッセージがブロードキャストされないこと、および、単一の対象となる受信側ノードだけが、各ＮＥＸＴＲＯＵＮＤメッセージの受信時にそのアンテナを回転していることである。
【００５４】
このプロトコルは、ＤＳＤＲにおいて機能するデータチャネルのレンジが、ＯＳＯＲモードにおいて機能する制御チャネルのレンジより小さいか、または、等しいと仮定している。そうでない場合には、ＮＬＤＰは、通信するのにＤＳＤＲを使用することができるであろうある種のノードを発見しない。
【００５５】
本発明の原理を適用できる多数の可能な実施形態を考慮して、図面を参照して本明細書で説明した実施形態が、例示的であるに過ぎないことを意図されており、本発明の範囲を限定するものと解釈されてはならないことを理解されたい。例えば、性能上の理由から、本発明の方法を、ソフトウェアにおいてではなくハードウェアにおいて実装することができる。したがって、本明細書に記載した本発明は、特許請求の範囲およびその均等の範囲に含めることができるものとして、すべてのそのような実施形態を企図している。
【図面の簡単な説明】
【００５６】
【図１】本発明のネイバロケーションディスカバリプロトコルを実装できる例示的なコンピュータアーキテクチャを示す概略図である。
【図２】本発明のネイバロケーションディスカバリプロトコルを利用して近接ノードを探し出すプロセスの初期ステップを示す概略図である。
【図３】本発明のネイバロケーションディスカバリプロトコルを利用して近接ノードを探し出すプロセスの最終ステップを示す概略図である。
【図４】本発明のネイバロケーションディスカバリプロトコルを利用して近接ノードの方向を見つけるプロセスの初期ステップを示す概略図である。
【図５】本発明のネイバロケーションディスカバリプロトコルを利用して近接ノードの方向を見つけるプロセスの最終ステップを示す概略図である。
【図６】本発明のネイバロケーションディスカバリプロトコルを示すフローチャートである。
【符号の説明】
【００５７】
１００  ノード
２００  ＧＤＲメッセージ
２０２  制御チャネル
３００  ＧＤＲ−ＡＣＫメッセージ
３０２  ネイバロケーションテーブル
４００、５００  ＤＧＤＲ−ＡＣＫメッセージ
４０２  データチャネル
【図１】
2006279951.tif 000005
【図２】
2006279951.tif 000006
【図３】
2006279951.tif 000007
【図４】
2006279951.tif 000008
【図５】
2006279951.tif 000009
【図６】
2006279951.tif 000010