(57)【要約】  アドホックネットワークにおけるチャンネル割り当ての要求に対処すべく、チャンネル割り当てのための方法及び装置を提供する。特に、通信システム（１００）は、チャンネルの再利用を可能にしてアドホックネットワークの拡張性を高めるノード（１０１〜１０７）チャンネル割り当てを決定する方法を利用している。チャンネル割り当ては、使用可能な最大チャンネル数、ネットワークでの最大許容レベル、及び親ノードが保有できる最大の子ノード数のみならず、特定のノードの現在のレベルに依存する。
2007507170.tif 000002
【特許請求の範囲】
【請求項１】
アドホックネットワークにおいてチャンネルを割り当てる方法であって、
ルートノードへのホップ数（Ｌｉ）を決定する段階と、
ルートノードへのホップ数に基づきチャンネル（ＳＬｉ）を決定する段階と、
前記チャンネルを利用してデータを送信する段階と
を備える方法。
【請求項２】
請求項１に記載の方法は更に、使用可能なチャンネルの最大数（Ｓｍａｘ）を決定する段階を備え、
前記チャンネルを決定する段階が更にＳｍａｘに基づいている方法。
【請求項３】
請求項１に記載の方法は更に、ネットワークでの最大許容レベル（Ｌｍ）を決定する段階を備え、
前記チャンネルを決定する段階が更にＬｍに基づいている方法。
【請求項４】
請求項１に記載の方法は更に、親ノードが保有できる最大の子ノード数（Ｃｍ）を決定する段階を備え、
前記チャンネルを決定する段階が更にＣｍに基づいている方法。
【請求項５】
請求項１に記載の方法は更に、近隣のノード間のチャンネルスプレッド（ｉｎｍｏｄ）を決定する段階を備え、
前記チャンネルを決定する段階が更にｉｎｍｏｄに基づいている方法。
【請求項６】
請求項１に記載の方法は更に、各ノードに対して割り当てられる固有の番号を示すノード番号（ｊ）を決定する段階を備え、
前記チャンネルを決定する段階が更にｊに基づいている方法。
【請求項７】
請求項１に記載の方法は更に、
使用可能な最大のチャンネル数（Ｓｍａｘ）を決定する段階と、
ネットワークでの最大許容レベル（Ｌｍ）を決定する段階と、
親ノードが保有できる最大の子ノード数（Ｃｍ）を決定する段階と、
特定のレベルに属するノードの順番を示すノード番号（ｊ）を決定する段階と、
近隣のノード間のチャンネルスプレッド（ｉｎｍｏｄ）を決定する段階と
を備え、前記チャンネルを決定する段階が、
ＳＬｉ，ｊ＝mod（mod（ｊ，inmod）＋inmod＊（Ｌｍ−Ｌｉ），Ｓｍａｘ），
ｊ＝１→ＣｍＬｉ，Ｌｉ＝０→Ｌｍ
を決定する段階を含む方法。
【請求項８】
ルートノードへのホップ数（Ｌｉ）を決定すると共に、ルートノードへのホップ数に基づきチャンネル（ＳＬｉ）を決定するマイクロプロセッサと、
前記チャンネルを利用してデータを送信するＲＦ回路と
を備える装置。
【請求項９】
請求項８に記載の装置において、前記マイクロプロセッサが更に使用可能な最大のチャンネル数（Ｓｍａｘ）を決定し、前記チャンネルが更にＳｍａｘに基づいている装置。
【請求項１０】
請求項８に記載の装置において、前記マイクロプロセッサが更にネットワークでの最大許容レベル（Ｌｍ）を決定し、前記チャンネルが更にＬｍに基づいている装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はアドホックネットワーク一般に関し、特にアドホックネットワーク内におけるチャンネル割り当てのための方法及び装置に関するものである。
【背景技術】
【０００２】
干渉はしばしば通信システムの性能を低下させる。通信システムを使用しているユーザがしばしば遭遇する干渉のひとつのタイプに他のユーザの送信によって引き起こされる干渉がある。この干渉は、典型的には同じ周波数帯を使っている多数のユーザの送信によって引き起こされ、同一チャンネル干渉といわれている。同一チャンネル干渉を減らすために、多くの通信システムでは、送信機が異なる周波数で送信を行う周波数再利用パターンを採用している。しかし、自己組織化したネットワークにおいては、ネットワークが送信ノードの地理的分布を前もって知ることはできない。このような事実にもかかわらず、分布はノードの移動と共にしばしば変化する。また、ネットワークが自己組織化しているため、論理的リンクの構成を事前に決定することができない。それ故に、同一チャンネル干渉がアドホックネットワークの性能を低下させ、また、現在そのようなアドホックネットワークで適切にチャンネルを割り当てる方法が存在しないので、同一チャンネル干渉の発生率を劇的に減らすアドホックネットワークにおけるチャンネル割り当てのための方法及び装置が必要とされている。
【発明の開示】
【０００３】
アドホックネットワークにおけるチャンネル割り当ての要求に対処すべく、チャンネル割り当てのための方法及び装置をここに提供する。特に、通信システムは、チャンネルの再利用を可能にしてアドホックネットワークの拡張性を高めるノードチャンネル割り当てを決定する方法を利用している。チャンネル割り当ては、使用可能な最大チャンネル数、ネットワークでの最大許容レベル、及び親ノードが保有できる最大の子ノード数のみならず、特定のノードの現在のレベルに依存する。
【０００４】
本発明は、アドホックネットワークでのチャンネル割り当てのための方法を含んでいる。この方法は、ルートノードへのホップ数（Ｌｉ）を決定する段階と、ルートノードへのホップ数に基づきチャンネル（ＳＬｉ）を決定する段階と、このチャンネルを利用してデータを送信する段階とを含んでいる。
【０００５】
本発明は更に、ルートノードへのホップ数（Ｌｉ）を決定すると共にルートノードへのホップ数に基づいてチャンネル（ＳＬｉ）を決定するマイクロプロセッサと、このチャンネルを利用してデータを送信するＲＦ回路とを備える装置をも含んでいる。
【発明を実施するための最良の形態】
【０００６】
次に図面を参照しながら説明する。なお、図面において、同様の符号は同様の構成要素を指している。図１はアドホックネットワーク１００のブロック図である。図面から明らかなように、アドホックネットワーク１００は、互いに通信する複数のネットワークノード１０１〜１０７を備えている。アドホックネットワーク１００は、米国特許出願第０９／８０３２５９号明細書に記述されているようなｎｅｕＲＦｏｎ（登録商標）システムプロトコルを利用することが好ましい。当業者なら分かるように、ｎｅｕＲＦｏｎ（登録商標）システムプロトコルでは、ひとつのノード１０４がルートノードとして機能し、他のノード１０３，１０５（「子ノード」という）は、子ノードの最大数（Ｃｍ）までルートノードに直接リンクする。同様にして、各子ノード１０１〜１０３，１０５〜１０７は、Ｃｍまでの子ノードを保有できる。従って、Ｃｍ＝２である図１では、ルートノード１０４は２つの子ノード１０３，１０５を保有している。同様にして、子ノード１０３，１０５の各々は、自身と直接通信する２つの子ノードを保有している。詳しくは、子ノード１０３は自身と直接通信するノード１０１，１０２を保有しており、子ノード１０５は自身と直接通信するノード１０６，１０７を保有している。
【０００７】
通信システム１００内の各ノード１０１〜１０７には、通信中にノードがルートノードから何回ホップしたかを示す値（レベル）が割り当てられている。例えば、ルートノード１０４はレベル０であり、ノード１０３，１０５はレベル１であって、ルートノードから１回「ホップ」している。同様にして、ノード１０１，１０２，１０６，１０７はレベル２であって、ルートノード１０４から２回ホップしている。従って、Ｃｍがノードが保有できる最大の子ノード数であるとき、与えられたレベル（Ｌｉ）に対して、（Ｃｍ）Ｌｉ個のノードがレベルＬｉに存在することが可能である。更に、特定のレベルにあるノードにはノード番号（ｊ）が割り当てられており、このノード番号（ｊ）は例えば特定のレベルに属するノードの順番を示している。従って図１では、例えば、ノード１０１はレベル２における最初のノードなのでＬｉ＝２，ｊ＝１であり、ノード１０２はレベル２における２番目のノードなのでＬｉ＝２，ｊ＝２である。
【０００８】
上述したように、同一チャンネル干渉はしばしば通信システムの能力を低下させる。従って、通信システム中の全ノード１０１〜１０７に対して、同一チャンネル干渉を減らすようにチャンネルを割り当てることが重要である。この目的を果たすために、通信システム１００は、チャンネル再利用を可能にしてアドホックネットワークの拡張性を向上させるノードチャンネル割り当てを決定する方法を利用している。チャンネル割り当ては特定のノードの現在のレベルに依存する。具体的には、各ノードのチャンネル割り当て（ＳＬｉ，ｊ）は次のアルゴリズムに基づく。
ＳＬｉ，ｊ＝mod（mod（ｊ，inmod）＋inmod＊（Ｌｍ−Ｌｉ），Ｓｍａｘ），
ｊ＝１→ＣｍＬｉ，Ｌｉ＝０→Ｌｍ                                    （１）
但し、
ＳＬｉ，ｊはレベルＬｉにあるノードｊに対するチャンネル割り当て、
Ｓｍａｘは使用可能な最大のチャンネル数、
Ｌｍはネットワークでの最大許容レベル、
Ｃｍは親ノードが保有できる最大の子ノード数、
ｉｎｍｏｄは近隣のノード間のチャンネルスプレッドを定義する数である。
【０００９】
なお、ｉｎｍｏｄの決定は、ネットワークにおいて最適なチャンネル割り当てのために重要であって、ネットワークの定められたＣｍに依存することに留意されたい。どのノードも、その親とその子とが同じチャンネルを共有しないように、ｉｎｍｏｄを最大限大きくとることが望ましい。表１は、様々なＣｍで、Ｓｍａｘ＝１６で、８ビットのアドレスを割り当てたときのｉｎｍｏｄの値を示している。
【００１０】
【表１】
2007507170.tif 000003
上述したチャンネル割り当てをより詳細に説明すべく、図２はＣｍ＝２，Ｌｍ＝７，ｉｎｍｏｄ＝５，Ｓｍａｘ＝１６（すなわちチャンネルは０〜１５）のネットワークを示している。明らかなように、上記のチャンネル割り当て手順により、ノード１０１にはチャンネル５が割り当てられることになる。同様にして、ノード１０２〜１０７には各々Ｓ＝６，１０，１５，１１，８が割り当てられる。上記したチャンネル割り当てはＣｍ>２の状況にも拡張することができる。このことは図３〜７で説明しており、各ノードの隣にある番号はそのノードが利用するチャンネルである。
【００１１】
図８は上述したチャンネル割り当ての手順を利用したノード８００のブロック図である。図示されたノード８００は、ＲＦ回路８０１とマイクロプロセッサ８０２とを備えている。ノードがオンに切り替えられると、ＲＦ回路８０１はリッスン状態になり、他のノードからのハローメッセージを探索する（ハローメッセージは送信ノードを特定するための簡単なブロードキャストメッセージである）。他のノードからのハローメッセージを受信したら、ノード８００はどのノードを子ノードとするかを（ハローメッセージで送られてくる情報やノード間でやり取りされる更なるメッセージや別の基準を使って）決定する。次に、ノード８００は（関連付けリクエストを送信し、親ノードからの関連付け応答を受信することにより）ネットワークに参加する。ネットワークに参加した後は、ノード８００は適切なチャンネルを選択する。これはいくつかの方法で実施することができる。一つの方法は、ノード８００に対してＣｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘと、更に親のＬｉ-１及びｊ（どの子、すなわち、ノード８００はＬｉ層の１番なのか２番なのか）を受け取らせ、そして自身の適切なチャンネルを計算させる。他の方法として、ｉｎｍｏｄ及びＳｍａｘをノード８００に先行して読み込ませることもできる。
【００１２】
親ノードが適切な子ノード（例えばノード８００）のチャンネルを計算してもよい。その後、その情報をノード８００に送信し、それ以降はそのハローメッセージのためにチャンネルが使われる。この場合は、親は更にＣｍ及びＬｍをノード８００に送信し、（将来参加するであろう）ノード８００の子のためのチャンネル割り当てを計算するために、その情報を使えるようにすべきであることに留意されたい。ノード８００がネットワークのルートノードとして動作するときは、Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘを受信することができない。この場合は、ルートノードはこれらの値を事前に保持していなければならず、これらの値を使って適切なチャンネルを選択する。
【００１３】
図９はノード８００の動作を示すフローチャートである。処理は、ノード８００がオンに切り替わるステップ９０１で始まる。ステップ９０３において、マイクロプロセッサ８０３がＣｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘ，Ｌｉ，ｊを決定する。上述したように、マイクロプロセッサ８０３がこれらの値を決定する方法は、本発明の様々な実施形態で変更し得る。例えば、ノード８００がルートノードとして動作するときは、Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘ，Ｌｉ，ｊの値はノード８００にプログラムされていて、データベース８０５に存在した方が望ましい。逆に、ノード８００が子ノードとして動作するときは、Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘ，Ｌｉ，ｊは親ノードから得ることができる。これらの値を得る方法にかかわらず、マイクロプロセッサ８０３はＣｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘ，Ｌｉ，ｊに基づいて現在のチャンネル（ＳＬｉ，ｊ）を計算する（ステップ９０５）。明らかなように、ＳＬｉ，ｊは０とＳｍａｘの間のスカラー値である。当業者なら分かるように、関連付けはＳＬｉ，ｊと実際のチャンネル（例えば、周波数、タイムスロット、拡散コード等）との間で行わなければならない。このことは、データベース８０５に蓄積された情報にアクセスすることで簡単に成し遂げることができる。更に、データベース８０５はＳＬｉ，ｊの各値と、対応する周波数、タイムスロット、拡散コード等との関連を表形式で保持していることが望ましい。ＳＬｉ，ｊの値でデータベース８０５にアクセスすることで、適切な送信チャンネルが得られる。
【００１４】
続いてステップ９０７では、データは特定のチャンネルで送信するＲＦ回路８０１を使ってノード８００により送信される。ＲＦ回路８０１は、通信システム１００で使われる特定のプロトコルを使って送信するために設計された、よく知られた回路である。データはＲＦ送信機に入り、適切にエラーコントロールがなされ、コード化され、モジュール化され、そして特定のチャンネルを使って送信される。
【００１５】
発明を特別な実施形態を例示しながら詳しく説明したが、当業者であれば、この発明の精神や範囲から外れること無く様々な変更形態が可能であることが理解できる。例えば、変数「ｊ」は上記では特定のレベルに属するノードの順番を示す番号であると説明したが、異なる実施形態として、変数ｊの値が特定のレベル内で固有のものである限り、使用可能な何れかのチャンネルに基づいてノードを選択してもよい。更に、ノードが自分が使用するチャンネルを決定するときに、このアルゴリズムに基づいた数多くのオプションがある（すなわち、自身の親に所属する何れかのｊ（従ってｊに関連するいかなるチャンネル）にもなりえる）。ノードが選択する特定のｊ（あるいはチャンネル）の選択は、ノードが選択可能なチャンネル（この情報は親から来る）を知った後に行うことができ、チャンネルを監視し、使っていないチャンネルを選択する。これはノードに柔軟性を与え、近隣の枝分かれから近隣のノードを使うようなさらなるチャンネルの利用を避ける。このような変更が請求の範囲内に含まれることが意図される。
【図面の簡単な説明】
【００１６】
【図１】アドホックネットワークのブロック図。
【図２】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図３】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図４】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図５】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図６】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図７】Ｃｍ，Ｌｍ，ｉｎｍｏｄ，Ｓｍａｘが様々な値のときのネットワークでのチャンネル割り当てを示す図。
【図８】図１の通信システム内のノードのブロック図。
【図９】図８のノードの動作を示すフローチャート。
【図１】
2007507170.tif 000004
【図２】
2007507170.tif 000005
【図３】
2007507170.tif 000006
【図４】
2007507170.tif 000007
【図５】
2007507170.tif 000008
【図６】
2007507170.tif 000009
【図７】
2007507170.tif 000010
【図８】
2007507170.tif 000011
【図９】
2007507170.tif 000012
【国際調査報告】
2007507170.tif 000013
2007507170.tif 000014