(57)【要約】  本発明は、無線通信システムにおいて携帯端末によって実行されるルーティング方法であって、（ｉ）送信先携帯端末へのルート調査信号を他の携帯端末から受けるステップと、（ｉｉ）前記ルート調査信号およびシステム性能パラメータにしたがって、前記携帯端末を経由する前記送信先携帯端末へのルートコストを計算するステップと、（ｉｉｉ）計算されたルートコストにしたがって、前記他の携帯端末に対して応答メッセージを送るステップとを含むルーティング方法を提案する。この方法は、ホップバイホップ最適化によってもたらされる問題を扱うため、ルート上のホップ数でルートコストを重み付ける。
2007506337.tif 000002
【特許請求の範囲】
【請求項１】
携帯端末によって実行される無線通信システムにおけるルーティング方法であって、
（ｉ）送信先携帯端末へのルート調査信号を他の携帯端末から受けるステップと、
（ｉｉ）前記ルート調査信号およびシステム性能パラメータにしたがって、前記携帯端末を経由する前記送信先携帯端末へのルートコストを計算するステップと、
（ｉｉｉ）計算されたルートコストにしたがって、前記他の携帯端末に対して応答メッセージを送るステップと、
を備える、ルーティング方法。
【請求項２】
前記ルート調査信号を前記携帯端末のルートリスト中の別の携帯端末に対して転送するステップと、
前記別の携帯端末からの応答メッセージにしたがって、前記別の携帯端末を経由する前記送信先携帯端末への各ルートコストを取得するステップと、
を更に備え、
前記ステップ（ｉｉｉ）は、
前記計算されたルートコストと前記取得された各ルートコストとを比較し、
比較結果にしたがって、前記他の携帯端末に対して応答メッセージを送る、
ことを含んでいる、請求項１に記載の方法。
【請求項３】
前記携帯端末のルートリスト中の各携帯端末に対してルート調査信号を送るステップと、
前記各携帯端末から受けた応答メッセージにしたがって、前記送信先携帯端末へのリンクを選択するステップと、
を更に備える、請求項１に記載の方法。
【請求項４】
前記携帯端末のルートリスト中の各携帯端末に対してルート調査信号を送るステップと、
前記各携帯端末から受けた応答メッセージにしたがって、前記送信先携帯端末へのリンクを選択するステップと、
を更に備える、請求項２に記載の方法。
【請求項５】
前記システム性能パラメータは、ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数を少なくとも含み、
前記ルート調査信号は、前記ソース携帯端末から前記携帯端末までの各ホップのルートコストを含んでいる、
請求項１から４のいずれか一項に記載の方法。
【請求項６】
前記ステップ（ｉｉ）は、以下の式を用いて計算し、
【数１】
2007506337.tif 000018
ここで、
ｆｃｏｓｔ ｎｅｗはルートコストであり、
Ｎは、前記ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数であり、
ｆ１（Ｎ）は、システム性能におけるコスト補償関数であり、
ｆ２（Ｎ）は、リンク性能におけるコスト調整関数であり、
ｎは、無線リンクのホップ列であり、
Ｃ（ｎ）は、ｎ番目のホップに対応する無線ルートコストである、
請求項５に記載の方法。
【請求項７】
システム性能における前記コスト補償関数ｆ１（Ｎ）＝２Ｎ−１である、請求項６に記載の方法。
【請求項８】
携帯端末によって実行される無線通信システムにしたがったルーティング方法であって、
（ｉ）前記携帯端末のルートリスト中の各携帯端末に対してルート調査信号を送るステップと、
（ｉｉ）前記各携帯端末から受けた応答メッセージおよびシステム性能パラメータにしたがって、前記各携帯端末を経由する送信先携帯端末へのルートコストを計算するステップと、
（ｉｉｉ）前記各ルートのコストを比較して、前記送信先携帯端末へのリンクを選択するステップと、
を備える、ルーティング方法。
【請求項９】
他の携帯端末からルート調査信号を受けるステップと、
前記携帯端末を経由する前記送信先携帯端末へのルートコストに関する情報を前記他の携帯端末に対して送るステップと、
を更に備える、請求項８に記載の方法。
【請求項１０】
前記携帯端末のルートリスト中の別の携帯端末に対して前記ルート調査信号を転送するステップと、
前記別の携帯端末からの応答メッセージにしたがって、前記別の携帯端末を経由する前記送信先携帯端末へのルートコストに関する情報を、前記携帯端末へルート調査信号を送る携帯端末に対して送信するステップと、
を更に備える、請求項８に記載の方法。
【請求項１１】
前記携帯端末のルートリスト中の別の携帯端末に対して前記ルート調査信号を転送するステップと、
前記別の携帯端末からの応答メッセージにしたがって、前記別の携帯端末を経由する前記送信先携帯端末へのルートコストに関する情報を、前記他の携帯端末に対して送信するステップと、
を更に備える、請求項９に記載の方法。
【請求項１２】
前記システム性能パラメータは、ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数を少なくとも含んでいる、請求項８から１１のいずれか一項に記載の方法。
【請求項１３】
前記ステップ（ｉｉ）は、以下の式を用いて計算し、
【数２】
2007506337.tif 000019
ここで、
ｆｃｏｓｔ ｎｅｗはルートコストであり、
Ｎは、前記ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数であり、
ｆ１（Ｎ）は、システム性能におけるコスト補償関数であり、
ｆ２（Ｎ）は、リンク性能におけるコスト調整関数であり、
ｎは、無線リンクのホップ列であり、
Ｃ（ｎ）は、ｎ番目のホップに対応する無線ルートコストである、
請求項１２に記載の方法。
【請求項１４】
システム性能における前記コスト補償関数ｆ１（Ｎ）＝２Ｎ−１である、請求項１３に記載の方法。
【請求項１５】
携帯端末であって、
送信先携帯端末へのルート調査信号を他の携帯端末から受けるための受信手段と、
前記ルート調査信号およびシステム性能パラメータにしたがって、前記携帯端末を経由する前記送信先携帯端末へのルートコストを計算するための計算手段と、
計算されたルートコストにしたがって、前記他の携帯端末に対して応答メッセージを送るための送信手段と、
を備える携帯端末。
【請求項１６】
前記ルート調査信号を前記携帯端末のルートリスト中の別の携帯端末に対して転送するための転送手段と、
前記別の携帯端末からの応答メッセージにしたがって、前記別の携帯端末を経由する前記送信先携帯端末への各ルートコストを取得するための取得手段と、
前記計算されたルートコストと前記取得された各ルートコストとを比較するための比較手段と、
比較結果にしたがって、前記他の携帯端末に対して応答メッセージを送るための送信手段と、
を更に備えている、請求項１５に記載の携帯端末。
【請求項１７】
前記送信手段は、前記携帯端末のルートリスト中の各携帯端末に対してルート調査信号を送り、
前記受信手段によって受けられた前記各携帯端末からの応答メッセージにしたがって、前記送信先携帯端末へのリンクを選択するための選択手段を更に備えている、請求項１５または１６に記載の携帯端末。
【請求項１８】
前記システム性能パラメータは、ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数を少なくとも含み、
前記ルート調査信号は、前記ソース携帯端末から前記携帯端末までの各ホップのルートコストを含んでいる、
請求項１５または１６に記載の携帯端末。
【請求項１９】
前記計算手段は、以下の式を用いてルートコストを計算し、
【数３】
2007506337.tif 000020
ここで、
ｆｃｏｓｔ ｎｅｗはルートコストであり、
Ｎは、前記ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数であり、
ｆ１（Ｎ）は、システム性能におけるコスト補償関数であり、
ｆ２（Ｎ）は、リンク性能におけるコスト調整関数であり、
ｎは、無線リンクのホップ列であり、
Ｃ（ｎ）は、ｎ番目のホップに対応する無線ルートコストである、
請求項１８に記載の携帯端末。
【請求項２０】
携帯端末であって、
前記携帯端末のルートリスト中の各携帯端末に対してルート調査信号を送るための送信手段と、
前記各携帯端末からの応答メッセージおよびシステム性能パラメータにしたがって、前記各携帯端末を経由する送信先携帯端末へのルートコストを計算するための計算手段と、
前記送信先携帯端末へのリンクを選択するために前記各ルートのコストを比較するための比較手段と、
を備える携帯端末。
【請求項２１】
前記システム性能パラメータは、ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数を少なくとも含んでいる請求項２０に記載の携帯端末。
【請求項２２】
前記計算手段は、以下の式を用いてルートコスト計算し、
【数４】
2007506337.tif 000021
ここで、
ｆｃｏｓｔ ｎｅｗはルートコストであり、
Ｎは、前記ソース携帯端末から前記携帯端末を経由して前記送信先携帯端末へと至る無線リンクのホップ数であり、
ｆ１（Ｎ）は、システム性能におけるコスト補償関数であり、
ｆ２（Ｎ）は、リンク性能におけるコスト調整関数であり、
ｎは、無線リンクのホップ列であり、
Ｃ（ｎ）は、ｎ番目のホップに対応する無線ルートコストである、
請求項２１に記載の携帯端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に無線通信システムにおけるルーティング方法に関し、特に通信プロセス中のルーティング方法および当該方法を実行するための携帯端末に関する。
【背景技術】
【０００２】
場所を問わずに、偏在的な計算能力および情報アクセスを与えるため、無線ネットワークは、現在の社会生活においては益々一般的となってきている。
【０００３】
現在、モバイル無線ネットワークには、２つのバリエーション、すなわち、セルラーネットワークやＷＬＡＮ（無線ローカルエリアネットワーク）等のインフラ構造に基づくモバイル無線ネットワークと、インフラ構造を持たないモバイルアドホックネットワーク等の無線ネットワークとがある。一般に、インフラ構造に基づく無線ネットワークでは、基地局またはＡＰ（アクセスポイント）の受信可能範囲がセルのサイズを決定し、セル内に留まる移動ノード（携帯端末）が最も近いブリッジ（基地局またはアクセスポイント）と接続して直接に通信を行なう。一方、モバイルアドホックネットワークでは、移動ノードが自己編成する。２つの通信する移動ノードは、ソースから送信先へとパケットを転送するルータの機能を果たす中間の移動ノードを介してそれらが互いに連絡できる場合には、それらが無線範囲から外れていても互いに通信を維持することができる。インフラ構造に基づく無線ネットワークでは、移動ノードが基地局またはＡＰに対して直接に接続されているため、インフラ構造に基づく無線ネットワークは１ホップネットワークと見なされる。一方、モバイルアドホックネットワークでは、通常、２つの移動ノード間に直接リンクが存在せず、これらの移動ノードが他の移動ノードの中継を介して通信しなければならないため、モバイルアドホックネットワークはマルチホップネットワークとも呼ばれている。
【０００４】
配置の潜在的な容易性により、モバイルアドホックネットワークは、ＰＡＮ、ＨＡＮ、軍事環境、探索救助活動を含む多くの実用的用途へと急速に広まっている。移動ノードと基地局との間の直接１ホップリンクを、一時的中継器として働く他の移動ノードとのマルチホップリンクへと分けると、理論的な全伝送パワーが減少するため、アドホックネトワーキング、特に中継通信機構は、セルラーネットワークの受信可能範囲（カバレージ）を広げ且つシステム能力を高めるための興味深い手法となっている。図１は、セルラー通信システムにおけるマルチホップ概念およびアドホックの適用例を示している。また、モバイルアドホックネットワークは、能力の問題を解決するために、高速ＷＬＡＮにも適用できる。
【０００５】
幅広い可能な用途は、モバルアドホックネットワーキングの分野における最近の研究開発活動の高まりを世界中にわたってもたらしてきている。しかしながら、モバルアドホックネットワークから得られる利点は、特に動的トポロジー構造をサポートするために無線ルーティングアルゴリズムを採用する場合に、幾つかの更なるネットワーキング複雑度を犠牲にする。少なくとも１０年間にわたって、無線ルーティングは、モバイルおよび無線分野において活発な研究テーマとなってきた。モバイル技術および無線技術が数多く生まれるにつれて、この分野が益々注目されてきており、例えばＩＥＴＦのＭＡＮＥＴグループ、ＡＴＭフォーラムのモバイルＡＴＭ、３Ｇ無線規格における多くの試みなど、関連する規格や企業が多く存在する。アドホックルーティングプロトコルにおけるそのような大きな注目にもかかわらず、全ての用途に適し得るプロトコルは未だ１つも存在していない。無線ルーティングは、アドホックネットワークにおける移動ノードの移動性に起因して、未だに難しい研究テーマである。
【０００６】
モバイルアドホックネットワークにおけるルーティング問題は、従来のネットワークにおけるそれよりもやりがいがある。第１に、インフラ構造に基づくセルラーネットワークの解決策などの従来の解決策では、ネットワークトポロジー構造が比較的安定しているのに対し、アドホックネットワークのトポロジー（マルチホップでアドホック機能が有効となるインフラ構造に基づくシステムおよび所定のインフラ構造がないシステム）は絶えず変化していると仮定される。第２に、従来のルーティング解決策は、幾つかのネットワークノードまたは指定の管理ノードに記憶された分散ルーティングデータベースに依存しており、モバイルアドホックネットワークがなければ、ルーティング情報が幾つかのノードに永久的に記憶される可能性は低く、更に、ノードに記憶された情報が常に本物で信頼性があるとは限らない。したがって、従来のインフラ構造に基づくセルラーネットワークにおいては、通常、ルート計算を中央で集中的に行なって簡単に実施できるが、モバイルアドホックネッワークにおいては、かなり小さいネットワークであっても動的ネットワークにおける中央集中的なルーティングが不可能であるため、ルート計算を分散させなければならない。
【０００７】
一般に、モバイルアドホックネッワークにおいて、分散ルーティングはベルマンフォードアルゴリズムによって実現される。この場合、１つの移動ノードが宛先ノードへのそのルートコストを他のノードに伝え、その後、他のノードは、移動ノードから受けた応答メッセージに示されたルートコストと移動ノードへの他のノードのそれぞれのルートコストとを組み合わせることにより、宛先ノードへの全ルートコストを計算し、また、ソースノードは、宛先ノードへの全ルートコストが最も低くなるノードにわたって中継することを選択する。このルーティングプロトコルおよびアルゴリズムの殆どは、ベルマンフォードに基づく変形であり、システムオーバーヘッド、パケット待ち時間、バッテリ消費量、伝送パワー記憶装置、システム安定性など、コストフォーカスが異なるだけである。
【０００８】
ベルマンフォードアルゴリズムの基本的な考えが図２に示されている。この場合、円は移動ノードを示しており、円同士を接続する線は既存の無線リンクを示しており、また、ライン上のデータは、無線接続性に関与する１つのノードから他のノードまでパケットを転送するためのホップコストを示している。ホップコストは、ホップまたはノードにおける性能パラメータのうちの１つまたは群、例えばシステムオーバーヘッド、パケット待ち時間、バッテリ消費量、伝送パワー、記憶装置、ノード移動性等であっても良い。異なる性能におけるコストは、同じ重みを用いて単位を測定するために正規化される。
【０００９】
以下、ノードＡからノードＴまでのルートを見つけるための例として、上記ベルマンフォードアルゴリズムがどのように機能するかについて説明する。
【００１０】
まず最初に、ルーティング方法を説明する前に、ネットワークシステムが以下の３つの条件を満たしているものと仮定する。
【００１１】
（１）ノードＡからのルート調査信号は、異なる伝送パワーで異なる範囲をもってノードに達することができる。
【００１２】
（２）ノードＡは、直接に到達可能なノードＴとのリンクを有していても良く或いは有していなくても良い。コスト値が特定の設定値を超えると、リンクを実質的に到達できないと見なすことができる。
【００１３】
（３）ノードＸ１とノードＸ２との間のリンク上のコストが低い場合、システム干渉を減らすように送信ノードの伝送パワーを減少させることができる。
【００１４】
前記３つの仮定条件を用いると、ノードＡからノードＴまでの最良のルート（最低コスト）を見つけるためのプロセスは、以下を含んでいる。
【００１５】
（１）ノードＡは、特定の伝送パワーでルート調査信号を送り、また、ルート調査信号を受けたノードは、それがノードＴへのルートを有している場合には応答メッセージをノードＡに対して送り戻し、それがノードＴへのルートリストを有していない場合にはルート調査信号を転送する。図２において、ノードＢおよびノードＧはそれぞれ、ノードＡからルート調査信号を受けている。
【００１６】
（２）ノードＢまたはノードＧは、それ自身のルートリストをチェックする。ルートリスト上にノードＴへのルートが存在する場合には、関連するルートリストがノードＡに対して送られ、また、ルートリスト上にノードＴへの利用可能なルートが存在しない場合には、ルート調査信号が転送される。図２において、ノードＣおよびノードＨはそれぞれ、ノードＢおよびノードＧから転送されたルート調査信号を受けている。
【００１７】
（３）ノードＣは、ノードＴへの２つのルートをＣ−Ｄ−Ｔ（８＋８）およびＣ−Ｔ（２０）としてそれぞれ有している。ノードＣは、２つのルートのコストを比較し、ノードＴへのその最低コストルートをＣ−Ｄ−Ｔ（１６）としてノードＢに応答する。無論、ノードＣは、ノードＴへの２つのルートをコスト表示を伴ってノードＢに対し応答することもできる。
【００１８】
（４）ノードＢは、ノードＴへのその最良ルートをＢ−Ｃ−Ｄ−Ｔ（１０＋１６）としてノードＡに応答する。無論、ノードＢは、ノードＴへのその全ルートをＢ−Ｔ（４０）、Ｂ−Ｃ−Ｄ−Ｔ（２６）、Ｂ−Ｃ−Ｔ（３２）としてノードＡに応答することもできる。
【００１９】
（５）ノードＢと同様に、ノードＧは、ノードＴへのその最良のルートをＧ−Ｈ−Ｉ−Ｊ−Ｔ（２７）としてノードＡに応答し、または、ノードＴへのその全ルートをＧ−Ｔ（４２）、Ｇ−Ｈ−Ｋ（３２）、Ｇ−Ｈ−Ｉ−Ｊ−Ｔ（２７）としてノードＡに応答する。
【００２０】
（６）ノードＡは、前記調査手続きによって、ノードＴへのそのルートを得る。ルート調査信号を受けたノードが最低コストルートだけで関連する転送ノードに応答する場合、ノードＡは、ノードＴへのその３つのルートをＡ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔ（３５）、Ａ−Ｂ−Ｃ−Ｄ−Ｔ（４６）、Ａ−Ｔ（１２０）として得る。ルート調査信号を受けたノードが全ての可能なルートで関連する転送ノードに対して応答する場合、ノードＡは、表１に示される７つのルートを受ける。
【００２１】
（７）最低コストルートによれば、ノードＡは、ルートが幾つのホップを有している場合であっても、ノードＴへのその現在のルートとしてＡ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔ（３５）を選択する。
【００２２】
ルートコスト計算は、以下のように表わすことができる。
【数１】
2007506337.tif 000003
【００２３】
ここで、ｎ＝１，２，．．．．，Ｎはルート上のホップ列であり、Ｎはルート上のホップ数であり、Ｃ（ｎ）は、ｎ番目のホップに対応するコスト、例えば伝送パワーやノード待ち時間等である。
【００２４】
表１は、ベルマンフォードアルゴリズムに基づいた移動ノードＡから移動ノードＴまでのルートの計算および選択をまとめている。１番目の縦列は、ソースノードＡから宛先（送信先）ノードＴまでの可能なルートの全てをリストアップしており、２番目の縦列から６番目の縦列は、ルートリスト上の関連するノード間のホップコストであり、７番目の縦列は、関連するルートにおけるホップ数であり、最後の縦列は、ベルマンフォードアルゴリズムに基づいたルート上の全てのホップの全コストの計算結果である。最低コスト規則によれば、最良のルートは、３５単位のコストしかとらないＡ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔとなるはずである。一方、他のルートは３５単位を上回っている。全コスト単位が同じルートは、各ルートにホップが幾つ含まれていようとも、同じ質を有していると見なされる。
【表１】
2007506337.tif 000004
【００２５】
ベルマンフォードアルゴリズム及びその変形は、最低コストルートを選択するためのホップバイホップ最適ルート計算に対して実に良好な解決策を与える。しかしながら、ホップ毎に（ホップバイホップで）コストが決定されるとともに、ホップにおけるコスト決定には、関連するノードおよびこれらの間の無線リンクしか関与していないため、ここでのコスト概念は、新たなホップが導入されるときのシステム性能への影響を考慮しない。また、これらのアルゴリズムは、全コストと全ての１ホップリンクコストとの間の関係が線形であると暗に仮定しているが、その仮定は常に正しいとは限らない。例えば、伝送パワー（ｄＢ）やノードでのパケット待ち時間等のコストは、ルート上の全てのノードにおいて線形であるが、他の性能パラメータに関しては以下の理由により幾つかの例外がある。
【００２６】
（１）ルートが幾つかの移動ノードを含んでいる場合、全ルートの接続可能性は、全ての１ホップの接続可能性の積となるはずである。このことは、全ての関連するリンクが組み合わされて一体のルートになるときに各１ホップの接続可能性の関係が乗法的であることを意味している。移動性によってもたらされるトポロジーの変動に起因して、選択された最良のルートが破壊されると、新たなルートを見つけるために更に多くの労力が必要になる。ルート上のホップが多いということは、接続可能性が低く、ルートを維持するために必要な労力が大きいということである。
【００２７】
（２）新たなノードがルートに対して導入されると、そのノードは、データを転送し或いは隣のリストをもってその最後のステップのノードに応答する。このような動作はノードツリーの増殖のように見え、一方、メンテナンスおよびルート発見におけるリソースオーバーヘッドは非線形的に増大する。
【００２８】
（３）データパケットがソースノードから宛先ノードへと転送されると、サービスのために必要なリソースは、現在の既存のルート上のホップ数によって決まる。リソースオーバーヘッドの増大も、現在のシステム負荷および現在の既存のルート上のホップ数に依存している。
【００２９】
前述したように、無線ルートコストは、各ホップの無線リンクコストだけでなく、リンクに含まれるホップ数にも関与しているため、現在のベルマンフォードアルゴリズムは、最適なルートを選択するために採用される際に欠点を有する。
【発明の開示】
【課題を解決するための手段】
【００３０】
本発明は、新規なルーティング方法および当該方法を実行するための携帯端末を提案する。前記ルーティング方法は、ホップバイホップ最適化によってもたらされる問題を扱うため、ルート上のホップ数でルートコストを重み付ける。
【００３１】
本発明においては、無線通信システムにおいて携帯端末によって実行されるルーティング方法であって、（ｉ）送信先携帯端末へのルート調査信号を他の携帯端末から受けるステップと、（ｉｉ）前記ルート調査信号およびシステム性能パラメータにしたがって、前記携帯端末を経由する前記送信先携帯端末へのルートコストを計算するステップと、（ｉｉｉ）計算されたルートコストにしたがって、前記他の携帯端末に対して応答メッセージを送るステップとを含むルーティング方法が提案される。
【発明を実施するための最良の形態】
【００３２】
本発明で提案される新規なルーティング（経路指定）方法も分散ベルマンフォードルーティングアルゴリズムに基づいているが、この新規なルーティング方法は、ルートコスト計算のためにホップ数での重み付けを導入する。新規なルーティング方法の主な考え方は、コスト性能パラメータの異なる特性にしたがってルートコストをホップバイホップコストとホップインオールコストとに分類することである。これは、以下のように表わすことができる。
【数２】
2007506337.tif 000005
【００３３】
ここで、ｎ＝１，２，．．．．，Ｎはルート上のホップ列であり、Ｎはルート上のホップ数であり、Ｃ（ｎ）はｎ番目のホップに対応するコストであり、コストは、伝送パワーやノード待ち時間などの幾つかのパラメータを考慮しても良い。また、ｆ１（Ｎ）はシステムリソースオーバーヘッドの補償等のシステム性能におけるコスト補償関数であり、ｆ２（Ｎ）はリンク接続性や干渉可能性における調整関数等のリンク性能におけるコスト調整関数である。ｆ１（Ｎ）およびｆ２（Ｎ）の両方は、実験的に或いは現在のシステムパラメータによって決定できる関数である。ｆ１（Ｎ）＝０およびｆ２（Ｎ）＝１の場合、新規なルーティング方式は分散ベルマンフォードルーティングアルゴリズムに収束する。全ての性能パラメータを考慮すると、Ｃ（ｎ）は以下のように表わすことができる。
【数３】
2007506337.tif 000006
【００３４】
前記方程式（３）において、ｗｘは各性能パラメータの重みを表わしており、ｆｘは性能パラメータと我々がルート選択において考慮する測定値との間のマッピング関係の関数である。ここで、ｗｐは伝送パワーの重みであり、ｗｄは伝送遅延の重みであり、ｗｂはノードのバッテリの重みであり、ｗｃはノードの処理能力の重みであり、ｗｍはノードのメモリの重みであり、ｗｍｂはノードの移動性の重みである。この方程式には他の性能パラメータを加えることもできる。Ｐ１はｎ番目のホップの伝送パワーであり、Ｄｅｌａｙはｎ番目のリンクの伝送遅延であり、Ｂａｔｔｅｒｙはリレイヤ（中継器）としてのｎ番目のノードのバッテリ量であり、  Ｐｒｏｃ ｃａｐａｂｉｌｉｔｙはｎ番目のノードの処理能力であり、ｍｅｍｏｒｙはｎ番目のノードの記憶空間であり、ｍｏｂｉｌｉｔｙは移動速度を用いて測定できるｎ番目のノードの移動性である。
【００３５】
前記重みｗｘの全ておよびｆ１，ｆ２を含むマッピング関数は、ネットワークの状態および実験によって決定することができる。我々は、本発明におけるルーティング方式を説明するために簡単な実施例を示す。この実施形態において、我々は、３つのファクタ、すなわち、全伝送パワー、全遅延、システムオーバーヘッドのみを考慮し、また、全てのマッピング関数が以下の条件を満たすものとする。
【数４】
2007506337.tif 000007
ここで、Ｐｂは我々が設定した基本パワーであり、Ｐｔはノードの伝送パワーである。
【数５】
2007506337.tif 000008
ここで、Ｄｅｌａｙはリンクの伝送遅延であり、Ｄｅｌａｙｂは設定基本伝送遅延である。
【００３６】
また、全ての重みが以下の通りであるとする。
ｗｐ＝０．６、ｗｄ＝０．４、ｗｂ＝０．０、ｗｃ＝０．０、ｗｍ＝０．０、ｗｍｂ＝０．０
【００３７】
各直接リンクをＸ→Ｙ（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）として表わすことができる場合、ａはノードＸとノードＹとの間のｆｐを表わし、ｂはノードＸとノードＹとの間のｆｄを表わし、ｃはノードＹのｆｂを表わし、ｄはＹのｆｐｃを表わし、ｅはＹのｆｍを表わし、ｆはノードＸに対するノードＹのｆｍｂを表わす。ノードＹが宛先ノードである場合には、ｆｂ，ｆｐｃ，ｆｍが全て０に設定される。しかし、本発明の実施形態において、我々は、全伝送パワーおよび全遅延のみを考慮するため、各直接リンクをＸ→Ｙ（ａ，ｂ）として表わすことができる。
【００３８】
本発明のルーティング方式を明確にするため、ｆ１（Ｎ）およびｆ２（Ｎ）を単に以下のように仮定する。
【数６】
2007506337.tif 000009
【００３９】
したがって、方程式（２）を以下のように簡略化することができる。
【数７】
2007506337.tif 000010
【００４０】
ｆ１（Ｎ）は、新たなホップによってもたらされるシステムリソースオーバーヘッドとして説明することができるとともに、全ホップの増大に伴って指数関数的に増加する。Ｃ（ｎ）は、２つのノード間の経路損失を克服するための伝送パワーコストとして表わすことができ、また、ｆ２（Ｎ）＝１は、ホップバイホップ重み付けがとられないことを意味している。
【００４１】
以下において、図３は、本発明で提案された方法を用いてノードＡからノードＴまでのルートを見つける方法を説明するための一例とも見なされる。
【００４２】
我々は、図３の全てのノードが同じ処理能力を有し且つこれらのノードのチャンネル環境が同じである（例えば、各ノードが空き領域内にある）と仮定する。したがって、図中の各ノードを以下のように表わすことができる。
【数８】
2007506337.tif 000011
【００４３】
前述した仮定を用いると、ソースノードＡから宛先ノードＴまでの最良のルートを見つけるためのプロセスは以下のようになる。
【００４４】
（１）ノードＡは、特定の伝送パワーでルート調査信号を送り、また、ルート調査信号を受けたノードは、それがノードＴへのルートを有している場合には応答メッセージをノードＡに対して送り戻し、そうでない場合にはルート調査信号を転送する。図３において、ノードＢおよびノードＧはそれぞれ、ノードＡからルート調査信号を受けている。
【００４５】
（２）ノードＢまたはノードＧは、それ自身のルートリストをチェックし、そのルートリスト上にノードＴへのルートを有している場合には、関連するルートリストをもってノードＡに対して応答し、あるいは、そのルートリスト上にノードＴへの利用可能なルートを有していない場合には、ルート調査信号を転送する。図３において、ノードＣおよびノードＨはそれぞれ、ノードＢおよびノードＧから転送されたルート調査信号を受けている。
【００４６】
（３）ノードＣは、ノードＴへの２つのルートをＣ−Ｄ−ＴおよびＣ−Ｔとしてそれぞれ有している。ノードＣは、２つのルートのコストを比較するとき、Ｃまでのそのルート上のリンクコストをＡ−Ｂ−Ｃとして合計するだけでなく、ルート調査信号転送ルートに関する知識（コストおよびホップの数）を組み合わせる。最低コストルートだけがルート調査信号転送ノード（ノードＢ）に対して戻される場合には、ルートコスト計算がノードＣにおいて行なわれる。到達可能な全てのルートが、ルート調査信号転送ノード（ノードＢ）に対して、したがってソースノード（ノードＡ）に対して戻される場合には、ルートコスト計算がノードＡにおいて行なわれる。前者の状況の場合（ルートコストがノードＣにおいて行なわれる場合）、ノードＣによって受けられたルート調査信号は、調査転送ルート情報（各ホップのコストおよびホップ）を含んでいなければならない。一方、後者の状況（ルートコストがノードＡにおいて計算される状況）においては、そのような情報は任意である。両方の状況における計算規則は方程式（２）に従わなければならない。このことは、コスト計算が、２つの部分、すなわち、ソースノードＡから現在のノードＣまでのルートおよび現在のノードＣから宛先ノードＴまでのルートを含むルート全体に関するものであることを意味している。
【００４７】
（ｉ）ルートＡ−Ｂ−Ｃ−Ｄ−Ｔの場合
【数９】
2007506337.tif 000012
【００４８】
（ｉｉ）Ａ−Ｂ−Ｃ−Ｔの場合
【数１０】
2007506337.tif 000013
【００４９】
最低ルートコスト規則によれば、ノードＣは、ノードＢを経由する最低コストルートとしてルートＡ−Ｂ−Ｃ−Ｄ−ＴをもってノードＢに対して応答する。無論、ノードＣは、ノードＴへの２つのルートＣ−ＴおよびＣ−Ｄ−Ｔのホップおよびリンクコストを戻すこともでき、したがって、Ａ−Ｂ−Ｃ−Ｔのルートコスト（８９．２）およびＡ−Ｂ−Ｃ−Ｄ−Ｔのルートコスト（１１９．２）をノードＡ〜ノードＢにおいて計算することができる。
【００５０】
（４）ノードＣと同様に、ノードＢは、その到達可能なルートの全てにおけるコストを方程式（８）にしたがって計算する。実際には、ノードＣを経由するルートにおけるコスト計算結果は、利用可能であり、ノードＢに対するノードＣの応答メッセージ内に含まれる。そのため、ノードＢは、ルートＡ−Ｂ−Ｔにおける関連するコストを計算するだけで済む。
【００５１】
ルートＡ−Ｂ−Ｔの場合、
【数１１】
2007506337.tif 000014
【００５２】
ルートＡ−Ｂ−Ｃ−Ｔのコストと比較すると、ノードＢを経由する宛先ノードＴへのルートはノードＣを経由するルートであり、このことは、ルートＡ−Ｂ−Ｃ−Ｄ−ＴがノードＢを経由する最低コストルートとしてソースノードＡに対して戻されることを意味している。
【００５３】
可能なルートのそれぞれのコストがソースノードＡにおいて計算される場合、ノードＢは、可能なルートのそれぞれのルートコストをノードＡで計算できるように、リンクオーバーヘッドおよびノードＢを経由する各ルート（Ａ−Ｂ−Ｔ，Ａ−Ｂ−Ｃ−Ｔ，Ａ−Ｂ−Ｃ−Ｄ−Ｔ）のホップを伴う応答をノードＡに対して行なうこともできる。
【００５４】
（５）ノードＢと同様に、ノードＧは、その到達可能なルートの全てにおけるコストを方程式（８）にしたがって計算する。ノードＧは、ルート調査信号をノードＨに対して転送する。ノードＨが宛先ノードＴへのルートリストを有している場合、ノードＨによるルートにおけるコスト計算は、２つの部分、すなわち、ソースノードＡから現在のノードＨまでの調査転送ルート（Ａ−Ｇ−Ｈ）の情報（コストおよびホップ）と、現在のノードＨから宛先ノードＴまでの可能なルート（Ｈ−Ｋ−ＴおよびＨ−Ｉ−Ｊ−Ｔ）の情報（コストおよびホップ）とを含んでいる。
【００５５】
（ｉ）  ルートＡ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔの場合
【数１２】
2007506337.tif 000015
【００５６】
（ｉｉ）ルートＡ−Ｇ−Ｈ−Ｋ−Ｔの場合
【数１３】
2007506337.tif 000016
【００５７】
Ａ−Ｇ−Ｈ−Ｉ−Ｊ−ＴはＡ−Ｇ−Ｈ−Ｋ−Ｔよりも多くのホップを有しているが、Ａ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔの全ホップバイホップコストはＡ−Ｇ−Ｈ−Ｋ−Ｔのそれよりも低く、そのため、ルートＡ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔは、最低ルートコスト規則にしたがって、ノードＧを経由する最低コストルートとしてノードＡに対して応答される。
【００５８】
可能なルートのそれぞれのコストがソースノードＡ以外の各転送ノードにおいて計算されない場合、ノードＧは、ノードＢと同様に、各ルートコストをノードＡで計算できるように、リンクコストおよびノードＧを経由する可能な各ルート（Ａ−Ｇ−Ｔ，Ａ−Ｇ−Ｈ−Ｉ−Ｊ−Ｔ，Ａ−Ｇ−Ｈ−Ｋ−Ｔ）のホップを伴う応答をノードＡに対して行なう。
【００５９】
（６）ノードＢおよびノードＧの両方は、その最低コストルートをもってノードＡに対して応答する。ノードＡは、全てのコストを比較して、ノードＴへの最良ルートとして最低コストルートを選択する。この実施形態では、ルートＡ−Ｂ−Ｃ−Ｔが最良ルートとして選択される。
【００６０】
各ルートコストがソースノードＡにおいて計算される場合には、宛先ノードへの可能な全てのルートのホップおよびコストが、各転送ノードを介してソースノードＡへと応答され、その後、ノードＴへの最良のルートとして最低コストルートを選択するために、ソースノードＡにおいてコスト計算を行なうことができる。
【００６１】
表２は、ソースノードＡから宛先ノードＴまでの可能な全てのルートをまとめている。この表から分かるように、最良ルートの選択は、全ホップバイホップコストだけに依存せず、ルート上のホップの数と直接関連するホップインオールコスト相補性にも依存する。
【表２】
2007506337.tif 000017
【００６２】
前述した実施形態のｆ１（Ｎ），ｆ２（Ｎ），Ｃ（ｎ）における関数定義および物理的特性は仮定を用いて決定されるが、これらは、実用的用途およびシステム性能特徴に応じた様々な方法で様々なシステムパラメータとして説明することができる。例えば、ｆ１（Ｎ）は、ルート発見およびメンテナンスにおける平均システムオーバーヘッドとして説明することができ、また、ｆ２（Ｎ）は、ルート上の全遅延として説明することができる。
【００６３】
本発明で提案された上記ルーティング方式は、携帯端末におけるコンピュータソフトウェアまたはコンピュータソフトウェアあるいはソフトウェアとハードウェアとの組み合わせで実施することができる。
【００６４】
発明の効果
前述したように、本発明において与えられる無線ルーティング方法に関しては、ルートコストに対するホップの影響（効果）が導入される。このことは、システム性能パラメータを反映できる関数によってルートコストが重み付けられることを意味している。ルーティング選択優先規則は、様々な性能パラメータの重要性にしたがってｆ１（Ｎ）およびｆ２（Ｎ）を調整することにより調整することができる。また、ルーティング方式は、ｆ１（Ｎ）およびｆ２（Ｎ）を調整して調査の氾濫を避け且つルートカバレージを助けることによりルート上のホップ数を制限することができ、したがって、ルート発見を容易にする。
【００６５】
モバイルアドホックネットワークの典型的な実施形態に関連して分散ルーティング方式を図示して説明してきたが、当業者であれば分かるように、この方式は、アドホックネットワークに限定されず、セルラーモバイル通信システムおよびアドホックを伴い或いはマルチホップ機能が可能なＷＬＡＮにも適用できる。
【００６６】
特定の実施形態に関して本発明を図示して説明してきたが、当業者であれば分かるように、添付の請求項によって規定される本発明の思想および範囲から逸脱することなく、様々な変形、省略、追加を行なうことができる。
【図面の簡単な説明】
【００６７】
【図１】セルラー方式におけるマルチホップ概念の適用を示すブロック図である。
【図２】ベルマンフォードアルゴリズムに基づくルート選択を示す概略図である。
【図３】本発明に係るルート選択を示す概略図である。
【符号の説明】
【００６８】
Ａ〜Ｔ  ノード
【図１】
2007506337.tif 000022
【図２】
2007506337.tif 000023
【図３】
2007506337.tif 000024
【国際調査報告】
2007506337.tif 000025
2007506337.tif 000026
2007506337.tif 000027