(57)【要約】【課題】  アドホックネットワーク内で容量を共有する分散システムおよび方法を提供する。【解決手段】  本発明は、共通リソースを共有するノードの集合（１０）を含み、前記ノード同士が通信リンク（１１）を介して接続可能である通信ネットワークにおける容量共有システム（１００）を提案する。各ノードは、各リンク（ｋ，ｌ）に、当日まで当該リンクが使用されていないと考えられる日付を表す満了時間Ｎｋｌを関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の少なくとも１つの集合を局所的に保持可能である。当該ノードは、所定の周期ｐに従い、リンクの集合を介して制御メッセージを周期的に交換すべく構成されていて、各制御メッセージは所与のリンクを介して、１個のノードにより局所的に保持され且つ前記所与のリンクと競合するリンクに対応する前記三つ組の集合を含む前記１個のノードにより送信される。【選択図】      図２Ａ
2015065653.tif 000002
【特許請求の範囲】
【請求項１】
共通リソースを共有するノードの集合（１０）を含み、前記ノード同士が通信リンク（１１）を介して接続可能である通信ネットワークにおける容量共有システム（１００）であって、各ノードは、各リンク（ｋ，ｌ）に、当日まで当該リンクが使用されていないと考えられる日付を表す満了時間Ｎｋｌを関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の少なくとも１つの集合を局所的に保持可能であり、前記ノードが、所定の周期ｐに従い、リンクの集合を介して制御メッセージを周期的に交換すべく構成されていて、各制御メッセージは所与のリンクを介して、１個のノードにより局所的に保持され且つ前記所与のリンクと競合するリンクに対応する前記三つ組の集合を含む前記１個のノードにより送信されることを特徴とするシステム。
【請求項２】
各ノードに局所的に保持される前記集合が、前記ノードに隣接するリンクおよび前記隣接するリンクと競合するリンクに関係する三つ組を含むことを特徴とする、請求項１に記載の容量共有システム。
【請求項３】
リンク（ｉ，ｊ）を介して所与のノードｉにより送信される各制御メッセージが、前記リンク（ｉ，ｊ）と競合するリンクに対応する前記三つ組の集合の要素を含むことを特徴とする、請求項２に記載の容量共有システム。
【請求項４】
各ノードが、自身が保持する前記三つ組の集合の所与のリンクに関連付けられた満了時間を、前記リンクの前記満了時間の現在の値より後である新規の値を含む制御メッセージの受信に応答して更新できることを特徴とする、請求項１〜３のいずれか１項に記載の容量共有システム。
【請求項５】
各ノードが、制御メッセージを送信する前に、自身が保持する前記三つ組の集合内にある自身の下りリンクに関連付けられた前記満了時間を更新できることを特徴とする、請求項１〜４のいずれか１項に記載の容量共有システム。
【請求項６】
対象日付ｔで使用されていない下りリンクに対して、前記リンクの満了時間の値をｔ＋Ｑに更新され、ここで、Ｑは前記下りリンクが他のノードにより使用されていないと考えられる期間を表すことを特徴とする、請求項５に記載の容量共有システム。
【請求項７】
所与のノードにより各リンクを介して制御メッセージを伝送する周期ｐは以下のように選択され、
Ｑ＞（Ｎ＋１）×ｐ
ここで、Ｎ＋１は、あるノードがネットワークのトポロジー内の別のノードの状況を知り得る厳密に最大のホップ数としての距離を表すことを特徴とする、請求項６に記載の容量共有システム。
【請求項８】
所与のリンクの満了時間を離散化してＮ＋１個の値に因子分解でき、前記パラメータＮ＋１が、あるノードがネットワークのトポロジー内の別のノードの状況を知り得る厳密に最大のホップ数としての距離を表し、各ノードが、制御メッセージを送信するために三つ組
【数１】
2015065653.tif 000048
のＮ＋１個の離散集合を０〜Ｎの範囲の値ｎに対して生成でき、且つ前記三つ組
【数２】
2015065653.tif 000049
のＮ＋１個の離散集合を送信前に前記制御メッセージ内に含めることができ、前記三つ組
【数３】
2015065653.tif 000050
のＮ＋１個の離散集合が、前記ノードにより局所的に保持された前記三つ組の集合およびトポロジーに関する情報から出発して生成できることを特徴とする、請求項１に記載の容量共有システム。
【請求項９】
前記離散化間隔が、持続期間Δｎから以下のように得られる
【数４】
2015065653.tif 000051
ことを特徴とする、請求項８に記載の容量共有システム。
【請求項１０】
リンク（ｉ，ｊ）を介したノードｉによる制御メッセージの生成が、日付ｔにおいて、全てのリンク（ｉ，ｌ）に対し、競合するリンクが頻繁に使用されない場合は、前記競合するリンクに関連付けられた満了時間を値ｔ＋Ｑに延長し、前記リンクが頻繁に使用される場合は、前記リンク（ｉ，ｌ）に関連付けられた満了時間を値ｔに短縮するステップを含む、請求項８または９に記載の容量共有システム。
【請求項１１】
各ノードが、所与のリンク（ｉ，ｊ）に関連付けられた集合
【数５】
2015065653.tif 000052
を表すＢｌｏｏｍフィルタを使用し、前記Ｂｌｏｏｍフィルタが、各リンクをｋ個のキーに関連付けるべくｍ個のビットおよびｋ個のハッシュ関数のテーブルを含み、前記キーは前記テーブル内の位置に対応しており、前記システムが前記Ｂｌｏｏｍフィルタを用いて、あるリンクが前記集合
【数６】
2015065653.tif 000053
に含まれているか否かを確実に判定することを特徴とする、請求項８または９に記載の容量共有システム。
【請求項１２】
日付ｔにおけるノードｊによる前記集合
【数７】
2015065653.tif 000054
を含む制御メッセージのリンク（ｉ，ｊ）を介した受信が、前記リンク（ｉ，ｊ）と競合する各リンク（ｋ，ｌ）に対し（ここで、ｋはｉとは異なり、ｎは０〜Ｎの範囲の任意の値である）、
−前記リンク（ｋ，ｌ）が前記集合
【数８】
2015065653.tif 000055
内に存在し（６０４）、且つ前記ノードｉと前記ノードｋとの間のホップ数としての距離が前記ノードｊと前記ノードｋとの間の距離よりも厳密に短い場合は、前記リンク（ｋ，ｌ）の満了時間Ｎｋｌを値ｔ＋Δｎ−１に短縮し、
−前記リンク（ｋ，ｌ）が前記集合
【数９】
2015065653.tif 000056
内に存在しない場合（６０４）は、前記リンク（ｋ，ｌ）の満了時間Ｎｋｌを値ｔ＋Δｎに延長する（６０５）ステップを含むことを特徴とする、請求項１１に記載の容量共有システム。
【請求項１３】
日付ｔにおけるリンク（ｉ，ｊ）を介した制御メッセージの生成が、各リンク（ｉ，ｌ）に対して、
−前記リンク（ｉ，ｌ）が頻繁に使用される場合、前記リンク（ｉ，ｌ）の満了時間Ｎｉｌを値ｔに短縮し、
−前記リンク（ｉ，ｌ）が頻繁に使用されない場合、前記リンク（ｉ，ｌ）の満了時間Ｎｉｌを値ｔ＋Ｑに延長する（５０６）ステップを含むことを特徴とする、請求項１１または１２に記載の容量共有システム。
【請求項１４】
日付ｔにおけるリンク（ｉ，ｊ）を介した制御メッセージの生成が、前記リンク（ｉ，ｊ）と競合する各リンク（ｋ，ｌ）に対して、ｌがｊと異なり、ｎが０〜Ｎの範囲の任意の値であるように、Ｎｋｌが厳密にｔ＋Δｎより小さい場合、前記リンク（ｋ，ｌ）を前記集合
【数１０】
2015065653.tif 000057
に挿入するステップを含むことを特徴とする、請求項１１〜１３のいずれか１項に記載の容量共有システム。
【請求項１５】
共通リソースを共有するノードの集合（１０）を含む通信ネットワーク内で容量を共有し、前記ノードを通信リンクを介してペアとして接続することが可能な方法であって、
−各ノードで、各リンク（ｋ，ｌ）に、当日まで前記リンクが使用されていないと考えられる日付を表す満了時間Ｎｋｌを関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の少なくとも１つの集合を局所的に保持するステップと、
−所定の周期ｐに従い、選択されたリンクの集合を介して各ノードから制御メッセージを周期的に送信するステップにであって、各制御メッセージが所与のリンクを介して、１個のノードにより局所的に保持され且つ前記所与のリンクと競合するリンクに対応する三つ組の集合を含む前記１個のノードにより送信されるステップとを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に、電気通信ネットワークに関し、特にアドホック型の無線通信ネットワークに関する。
【背景技術】
【０００２】
アドホックモバイルネットワークとは、所定のインフラが一切無くても自己構築が可能な無線ネットワークである。アドホックネットワークにおいて、無線通信媒体は、互いの通信圏内に存在する移動局により共有される。従って同一ネットワークの移動局間でパケットの送受信ができるように伝送媒体が共有される。２つの移動局が１つの伝送媒体を介して同時に発信した場合、競合のリスクが存在する。
【０００３】
ＣＳＭＡ／ＣＡ（Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  ｗｉｔｈ  Ｃｏｌｌｉｓｉｏｎ  Ａｖｏｉｄａｎｃｅの略語）と呼ばれている公知のランダムアクセスプロトコルを用いてネットワーク内でのそのような競合を避けることができる。このアクセス方式によれば、各移動局（以下「ノード」とも称する）は、伝送チャネルが空いている場合、換言すれば移動中の信号が検出されていない場合に自由に通信することができる。伝送障害が、特に競合に起因して、生じたか否かを判定するために受信肯定応答（ＡＣＫ）が一般に用いられる。そのような状況が生じた場合、移動局は通常、通信を再開する前にランダムな時間だけ待機することにより、競合の確率が下がる。
【０００４】
ＣＳＭＡ／ＣＡ法は、共通リソースへのアクセスを求めるリンク間の競合関係の形で表現可能な相互排除に基づいている。アドホックネットワークが標準的なＩＥＥＥ８０２．１１方式のプロトコルを用いる場合、これらのリンクがトポロジーの観点から充分に近い場合ば常に、２つの移動局を接続するリンク間に競合関係が存在するものと仮定される。より正確には、ノード対｛ａ，ａ'｝｛ａ，ｂ'｝｛ｂ，ａ’｝および｛ｂ，ｂ’｝の間のトポロジーのホップ数としての最短距離がパラメータＮ−１（ａ、ｂ、ａ’およびｂ’はノードを表す）以下である場合に２個のリンク（ａ，ｂ）および（ａ'，ｂ’）の間に競合関係が存在すると考えられる。パラメータＮは、ルーティングプロトコルにより定義されるホップ数を表し、各ノードはネットワークのトポロジーの状況を少なくともＮ＋１ホップまで知ることが可能である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従ってＣＳＭＡ／ＣＡランダムアクセス法により、互いに干渉し合うリスクを有する同時送信を回避すると共に、メッセージの再送信を制限することができる。しかし、ＣＳＭＡ／ＣＡアクセス方式では、競合するリンク間で共通リソースを公平に配分することができない。この結果、あるリンクと競合する他のリンクがリソースの配分を過度に受けている場合に当該リンクでリソースが不足する恐れがある。
【課題を解決するための手段】
【０００６】
本発明は、上記の状況を改善すべく設計されている。この目的で、本発明は、共通リソースを共有するノードの集合を含み、ノード同士が通信リンクを介して接続可能である通信ネットワークにおける容量共有システムを提供する。本発明の一態様によれば、各ノードは、各リンク（ｋ，ｌ）に、当日まで当該リンクが使用されていないと考えられる日付を表す満了時間Ｎｋｌを関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の少なくとも１つの集合を局所的に保持可能であるのに対し、当該ノードは、所定の周期ｐに従い、リンクの集合を介して制御メッセージを周期的に交換すべく構成されていて、各制御メッセージは所与のリンクを介して、１個のノードにより局所的に保持され且つ当該所与のリンクと競合するリンクに対応する三つ組の集合を含む当該１個のノードにより送信される。
【０００７】
特に、各ノードで局所的に保持される集合は、当該ノードに隣接するリンク、および当該隣接リンクと競合するリンクに関係する三つ組を含んでいてよい。
【０００８】
本発明の一特徴によれば、リンク（ｉ，ｊ）を介して所与のノードｉにより送信される各制御メッセージは、リンク（ｉ，ｊ）と競合するリンクに対応する三つ組の集合の要素を含んでいてよい。
【０００９】
本発明の別の特徴によれば、各ノードは、自身が保持する三つ組の集合内の所与のリンクに関連付けられた満了時間を、当該リンクの満了時間の現在の値より後である新規の値を含む制御メッセージの受信に応答して更新することができる。
【００１０】
更に、各ノードは、制御メッセージを送信する前に、自身が保持する三つ組の集合内にある自身の下りリンクに関連付けられた満了時間に更新することができる。
【００１１】
本発明の一実施形態において、対象日付ｔで使用されていない下りリンクについて、当該リンクの満了時間を値ｔ＋Ｑに更新することができる。ここで、Ｑは他のノードが当該下りリンクを使用していないと考えられる時間間隔を表す。
【００１２】
特に、所与のノードにより各リンクを介して制御メッセージを伝送する周期ｐは以下のように選択することができる。
Ｑ＞（Ｎ＋１）×ｐ
ここで、Ｎは、あるノードがネットワークのトポロジー内の別のノードの状況を知り得る厳密に最大のホップ数としての距離を表す。
【００１３】
所与のリンクの満了時間は離散化してＮ＋１個の値に因子分解でき、パラメータＮは、あるノードがネットワークのトポロジー内の別のノードの状況を知り得る厳密に最大のホップ数としての距離を表し、各ノードは、制御メッセージを送信するために三つ組
【数１】
2015065653.tif 000003
のＮ＋１個の離散集合を０〜Ｎの範囲の値ｎについて生成でき、且つ前記三つ組
【数２】
2015065653.tif 000004
のＮ＋１個の離散集合を送信前に当該制御メッセージ内に含めることができる。三つ組
【数３】
2015065653.tif 000005
のＮ＋１個の離散集合は、ノードにより局所的に保持された三つ組の集合およびトポロジーに関する情報から出発して生成することができる。
【００１４】
離散化間隔は特に、持続期間Δｎから以下のように得られる。
【数４】
2015065653.tif 000006
【００１５】
本発明の別の特徴によれば、リンク（ｉ，ｊ）を介したノードｉによる制御メッセージの生成は、日付ｔにおいて、全てのリンク（ｉ，ｌ）に対し、競合するリンクが頻繁に使用されない場合は、前記競合するリンクに関連付けられた満了時間を値ｔ＋Ｑに延長し、当該リンクが頻繁に使用される場合は、リンク（ｉ，ｌ）に関連付けられた満了時間を値ｔに短縮するステップを含んでいてよい。
【００１６】
本発明の特定の一実施形態において、各ノードは、所与のリンク（ｉ，ｊ）に関連付けられた集合
【数５】
2015065653.tif 000007
を表すＢｌｏｏｍフィルタを用いることができ、当該Ｂｌｏｏｍフィルタは、各リンクをｋ個のキーに関連付けるべくｍ個のビットおよびｋ個のハッシュ関数のテーブルを含み、当該キーはテーブル内の位置に対応している一方、本システムはＢｌｏｏｍフィルタを用いて、あるリンクが集合
【数６】
2015065653.tif 000008
に含まれているか否かを確実に判定する。
【００１７】
日付ｔにおけるノードｊによる集合
【数７】
2015065653.tif 000009
を含む制御メッセージのリンク（ｉ，ｊ）を介した受信は次いで、前記リンク（ｉ，ｊ）と競合する各リンク（ｋ，ｌ）に対し（ｋはｉとは異なり、ｎは０〜Ｎの範囲の任意の値）、
−リンク（ｋ，ｌ）が集合
【数８】
2015065653.tif 000010
内に存在し、且つノードｉとノードｋとの間のホップ数としての距離がノードｊとノードｋとの間の距離よりも厳密に短い場合、リンク（ｋ，ｌ）の満了時間Ｎｋｌを値ｔ＋Δｎ−１に短縮し、
−リンク（ｋ，ｌ）が集合
【数９】
2015065653.tif 000011
内に存在しない場合、リンク（ｋ，ｌ）の満了時間Ｎｋｌを値ｔ＋Δｎに延長するステップを含んでいてよい。
【００１８】
更に、日付ｔにおけるリンク（ｉ，ｊ）を介した制御メッセージの生成は、各リンク（ｉ，ｌ）について、
−リンク（ｉ，ｌ）が頻繁に使用される場合、リンク（ｉ，ｌ）の満了時間Ｎｉｌを値ｔに短縮し、
−リンク（ｉ，ｌ）が頻繁に使用されない場合、リンク（ｉ，ｌ）の満了時間Ｎｉｌを値ｔ＋Ｑに延長するステップを含んでいてよい。
【００１９】
日付ｔにおけるリンク（ｉ，ｊ）を介した制御メッセージの生成は、リンク（ｉ，ｊ）と競合する各リンク（ｋ，ｌ）について、ｌがｊと異なり、ｎが０〜Ｎの範囲の任意の値であるように、Ｎｋｌが厳密にｔ＋Δｎより小さい場合、リンク（ｋ，ｌ）を集合
【数１０】
2015065653.tif 000012
に挿入するステップを含んでいてよい。
【００２０】
本発明は更に、共通リソースを共有するノードの集合を含む通信ネットワーク内で容量を共有し、当該ノードを通信リンクを介してペアとして接続することが可能な方法を提供する。本方法は、有利な点として、
−各ノードで、各リンク（ｋ，ｌ）に、当日まで当該リンクが使用されていないと考えられる日付を表す満了時間Ｎｋｌを関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の少なくとも１つの集合を局所的に保持するステップと、
−所定の周期ｐに従い、選択されたリンクの集合を介して各ノードから制御メッセージを周期的に送信するステップであって、各制御メッセージが所与のリンクを介して、１個のノードにより局所的に保持され且つ当該所与のリンクと競合するリンクに対応する三つ組の集合の要素を含む当該１個のノードにより送信されるステップとを含む。
【００２１】
本発明による容量共有を行う分散システムおよび方法は従って、各リンクの上流におけるデータ速度を制限することができる。これらは特に、各リンクに割り当てられるリソースの割合を最適化することにより、容量の公平な共有を可能にする。共通リソースの共有度合の向上はネットワークの正常な動作に直接的な影響を及ぼす。
【００２２】
本発明の他の特徴および利点は、以下の説明および添付の図面を参照することにより明らかになろう。
【図面の簡単な説明】
【００２３】
【図１】パラメータＮ＝２の場合に、６個のノードを有するトポロジーの一例における競合関係を示す。
【図２Ａ】本発明の特定の実施形態による、ネットワーク内で共通リソースを公平に共有する分散処理システムのアーキテクチャを示す。
【図２Ｂ】本発明の特定の実施形態による三つ組の例を示す。
【図３】本発明の一実施形態による、因子分解されたメッセージを解釈する方法を記述するフロー図である。
【図４】集合｛ｘ，ｙ，ｚ｝を表すＢｌｏｏｍフィルタの一例を示す。
【図５】本発明の特定の実施形態による、最適化メッセージを生成する方法を記述するフロー図である。
【図６】本発明の別の実施形態による、因子分解されたメッセージを解釈する方法を表すフロー図である。
【発明を実施するための形態】
【００２４】
これらの図面は主に、以下の記述への理解を深めるために用いるだけでなく、適宜本発明の定義にも寄与する要素を含む。
【００２５】
図１に、アドホック型のモバイルネットワーク内で６個のノード（ａ，ｂ，ｃ，ｄ，ｅ，ｆ）を含むトポロジーに存在する競合関係を示す（パラメータＮは２に固定されている）。Ｎはルーティングプロトコルにより定義されるホップ数を表し、各ノードは少なくともＮ＋１ホップまでネットワークのトポロジーの状況を知ることが可能である。従って、図１の例において、各ノードは少なくとも３ホップまでネットワークのトポロジーの状況を知ることができる。
【００２６】
図１の例に示すように、リンク（ａ，ｂ）は他の５個のリンク（ｂ，ａ）、（ｂ，ｃ）、（ｃ，ｂ）、（ｃ，ｄ）および（ｄ，ｃ）と競合する。実際、これらのリンクの各々において、少なくとも１つの終端のａまたはｂからの距離が１ホップ以下である。他のリンクでは距離が遠すぎる。従って、リンク（ｄ，ｅ）において、ｄはａから３ホップ、ｂから２ホップ離れており、ｅはａから４ホップ、ｂから３ホップ離れている。
【００２７】
各ノードが少なくともＮ＋１ホップまでネットワークのトポロジーの状況を知り得るルーティングプロトコルを用いる従来のネットワークにおいて、所与のノードは、他のどのリンクが各下りリンクのいずれと競合するかを知ることができる。当該ノードは次いで、自身の下りリンクの各々について、競合するリンクが同じ時間だけ使用されることを阻害することなくリンクを効率的に使用できる最大の時間配分を計算することができる。実際、少なくともＮ＋１ホップまで達する局所トポロジーの状況を知ることで、ノードは競合グラフを計算して自身の下りリンクが属する全てのクリーク（最大完全部分グラフ）を知ることができる。リンクが使用できる最大時間配分は従って、自身が属する競合グラフで最大クリークのサイズの逆数である。
【００２８】
所与のノードの下りリンクは、当該所与のノードが上流のデータ速度を制限可能なリンクを表す。所与のノードは、自身が送信元であるリンクの上流しか制限することができない。
【００２９】
図１の例において、リンク（ａ，ｂ）が他の５個のリンク（ｂ，ａ）、（ｂ，ｃ）、（ｃ，ｂ）、（ｃ，ｄ）および（ｄ，ｃ）と競合するため、ノードａはリンク（ａ，ｂ）の使用を全時間の１／６に制限する必要がある。実際、図１の例では、（ａ，ｂ）と競合する全てのリンクは単一のクリーク（最大完全部分グラフ）を形成する。従って、リンク（ａ，ｂ）が属する最大クリークは６個のリンクからなる。その結果、リンク（ａ，ｂ）が全時間の１／６より長くは使用できない。リンク（ｂ，ｃ）を考慮するに、以下の２個のクリーク、
｛（ａ，ｂ）、（ｂ，ａ）、（ｂ，ｃ）、（ｃ，ｂ）、（ｃ，ｄ）、（ｄ，ｃ）｝および｛（ｂ，ｃ）、（ｃ，ｂ）、（ｃ，ｄ）、（ｄ，ｃ）、（ｄ，ｅ）、（ｅ，ｄ）｝が観察できる。
【００３０】
これら２個のクリークは同一サイズ（６）であるため、リンク（ｂ，ｃ）が使用できる時間配分は１／６である。
【００３１】
しかし、そのような先回り方式は、たとえリンクが使用されていなくても同等のリソース配分が確保されるという短所がある。従って、図１の例では、リンク（ａ，ｂ）だけが使用されている場合、当該リソースを使用しないリンクのために全時間の５／６が予約されてしまう。
【００３２】
本発明は、応答的な分散方式に基づいて、ノードがリンクの効率的な使用に関する通知を受けていることにより、利用可能な全てのリソースを効率的に使用されているリンク間で共有可能にする容量を共有する分散処理システムを提供することにより上述の状況を改善する。
【００３３】
本明細書の記述において、２個のリンク（ｉ，ｊ）、（ｋ，ｌ）間の競合の存在を表すために以下の表記を用いる。
【数１１】
2015065653.tif 000013
【００３４】
慣例により、あるリンクは自身と競合
【数１２】
2015065653.tif 000014
し、且つ逆向きのリンクとも競合する
【数１３】
2015065653.tif 000015
ものと更に仮定する。
【００３５】
図２Ａに、本発明の特定の実施形態による、容量共有分散処理システム１００を示す。共有システム１００は、リンク１１を介してペアとして接続可能なノードの集合１０を含む。
【００３６】
本発明の一態様によれば、容量共有システム１００は、全てのリンク１１を介したノード１０間における制御メッセージ１２の周期ｐに従う周期的な交換に基づいている。
【００３７】
このような交換は、以下で別途「満了時間」と称する日付Ｎｋｌを各リンク（ｋ，ｌ）に関連付ける三つ組（ｋ，ｌ，Ｎｋｌ）の集合Ｅｉを各ノードｉが局所的に保持可能にすべく提供される。所与のリンク（ｋ，ｌ）の満了時間Ｎｋｌは、当日まで当該リンクが使用されていないと考えられる日付を表す。特に、満了時間Ｎｋｌは、現在日付に近い日付を表す場合がある。満了時間Ｎｋｌは次いで、現在日付に関する情報を省略することにより圧縮可能である。より一般的には、満了時間用に選択されるフォーマット、および特に選択されたフォーマットの精度は、選択されたパラメータｐに依存していてよい。
【００３８】
所与のノードｉに保持された三つ組の各集合Ｅｉは、ｉの下りリンクと競合する全てのリンクの１つのエントリを含む。これらは、どの終端もノードｉにも対応しないリンクであってよい。
【００３９】
各ノードｉは、集合Ｅｉを保持すべく少なくとも１つのデータ構造１３を含んでいてよい。集合Ｅｉを保持すべく用いるデータ構造１３にはリスト、テーブル、木、ハッシュテーブル等が含まれるが、これらに限定されない。
【００４０】
本発明の一実施形態において、所与のノードｉの集合Ｅｉは、当該ノードに隣接するリンクの集合の、および隣接するリンクが競合するリンクの三つ組を含む。所与のノードｉに隣接するリンクは、両終端の一方がノードｉであるリンクに対応する。所与のノードｉに隣接するリンクは従って、当該ノードの上りリンクおよび下りリンクの和集合を形成する。
【００４１】
例えば、図１のノードａおよびｂは各々、以下の図２Ｂの集合ＥａおよびＥｂを含む。
【００４２】
図２Ｂの例では、ノードａに隣接するリンクは（ａ，ｂ）および（ｂ，ａ）であり、他のリンクは（ｂ，ｃ）、（ｃ，ｂ）、（ｃ，ｄ）および（ｄ，ｃ）である。ノードｂに隣接するリンクは（ａ，ｂ）、（ｂ，ａ）、（ｂ，ｃ）および（ｃ，ｂ）であり、他のリンクは（ｃ，ｄ）、（ｄ，ｃ）、（ｄ，ｅ）および（ｅ，ｄ）である。
【００４３】
本発明の別の態様によれば、ノードｉによりリンク（ｉ，ｊ）を介して送信される各制御メッセージは、（ｉ，ｊ）と競合するリンクに対応する集合Ｅｉの要素を含む。各制御メッセージで送信される要素の集合は以下においてＥｉｊと表記される。
【００４４】
従って以下の表記法を用いて集合Ｅｉｊの要素を特徴付けることができる。
【数１４】
2015065653.tif 000016
【００４５】
前提として、（ｉ，ｊ）と競合するリンクは、
【数１５】
2015065653.tif 000017
と競合するリンクに対応する。従って、ノードのｊによるノードｉからの制御メッセージの受信に応答して、ノードｊは集合Ｅｉｊから情報を用いて自身の集合Ｅｊを更新することができる。
【００４６】
従って、本記述の以下の部分において、集合Ｅｉはノードｉにより効率的に保持される集合を表記するのに対し、集合Ｅｉｊはｉからｊに送信されるＥｉの部分集合を表記する。集合Ｅｉが各ノードｉにより局所的に保持されるのに対し、集合Ｅｉｊは局所的集合Ｅｉおよびノードｉによる制御メッセージの生成時点における局所トポロジーに関する情報から出発して生成される。
【００４７】
本発明の別の特徴によれば、集合Ｅｊを保持する各ノードｊは、更新規則に従い、集合Ｅｉｊ内のリンク（ａ，ｂ）に対応する満了時間Ｎａｂを更新すべく構成できる。特に、満了時間に対する更新規則は、ノードｉにより送信された制御メッセージで当該満了時間に対する新規の値が受信され、且つ当該新規の値が集合Ｅｊ内の満了時間の現在の値よりも後ろである場合に、集合Ｅｉｊ内のリンク（ａ，ｂ）の満了時間Ｎａｂを修正するというものである。
【００４８】
更に、制御メッセージを送信する前に、所与のノードｉが、集合Ｅｉ内の自身の下りリンクの満了時間を更新すべく構成できる。特に、対象時刻ｔで使用されていない全てのリンク（ｉ，ｋ）に対して、満了時間Ｎｉｋは値ｔ＋Ｑに固定されている。ここで、Ｑはリンク（ｉ，ｋ）が他のノードにより使用されていないと考えられる時間間隔を表す（リンク（ｉ，ｋ）の効率的な使用を反映するように更新された場合、時刻ｔにおける満了時間Ｎｉｋの値によらない）。
【００４９】
本発明の別の態様によれば、所与のノードによる各リンクを介した制御メッセージの伝送周期ｐは以下のように選択することができる。
Ｑ＞（Ｎ＋１）×ｐ
【００５０】
本発明の好適な実施形態において、パラメータＱ（リンク（ｉ，ｋ）が他のノードにより使用されていないと考えられる時間間隔）およびｐ（所与のノードによる各リンクを介した制御メッセージの伝送周期ｐ）はネットワークの全てのノードに対して同一である。
【００５１】
本発明の特定の特徴によれば、制御メッセージ１２は全ての下りリンクを介して周期的に送信される。しかし、制御メッセージが送信される時刻はリンク間で非同期的であってよい。
【００５２】
制御メッセージのフォーマットは、メッセージを受信するノードが、当該メッセージがどのリンクを介して送信されたかを知るために、どのノードが当該メッセージを送信したかを判断できるように選択される。この目的のため、各制御メッセージは、当該メッセージを含むパケットの送信元および宛先アドレスを用いることができる。
【００５３】
制御メッセージ１２は更に、他の情報を含んでいてよい。また、満了時間に関する情報を担持すべく適当な伝送周波数を有する既存のメッセージを制御メッセージ１２として用いることも可能である。
【００５４】
制御メッセージ１２は、ユニキャストモードで送信することができる。受信承認の機構、および制御メッセージが受信されなかった場合には再送信の機構を用いることができる。これらの機構は特に、情報通信を向上させるべく伝送の成功確率を上げるために選択されていてよい。
【００５５】
本発明はこのように、リンク（ｉ，ｊ）を介して制御メッセージが送信された際にノードｉにより最近更新された満了時間が、当該満了時間に関係するリンクが常に使用されていない場合に、制御メッセージを２回受信する間に、より遠くのノードで満了するのを回避できるようにする。競合がＮホップに対して定義されているため、そのような満了時間に関係するノードは高々Ｎ＋１ホップ離れて配置されている。極端な場合、時刻ｔでノードｉにより更新された満了時間は、ノードｉからＮ＋１ホップ離れたノードに時刻ｔ＋（Ｎ＋１）×ｐに到着する。
【００５６】
パラメータｐは好適には全体システム１００に対して大域的に定義されている。ノードは次いで、システムにより定義された周期ｐを適用すべく当該システムの立ち上げ前に設定される。制御メッセージの伝送が信頼できないと考えられる状況において、システム１００は、満了時間が尚早に満了するのを回避するために周期ｐを短縮することができる。
【００５７】
当業者には、満了時間がリンクの不使用に関係し、リンクの使用には関係しないという事実を認識されよう。その結果、本発明の実施形態によるリソース１００を共有するシステムはメッセージの不用意な喪失に対してより強靭である。尚早に満了する満了時間は、リンクが使用されているとノードが誤って認識し、従って自身の下りリンクに割り当てる時間配分が少なくなるという結果が生じ得る。尚早な満了は、（ｉ，ｊ）と競合するノードｋの集合Ｅｋ内の未使用リンク（ｉ，ｊ）の満了時間Ｎｉｊの満了に対応する一方、リンク（ｉ，ｊ）は使用されないままである。これが起こり得るのは例えば、特定の理由（メッセージの処理または送信の遅延、メッセージの喪失等）で情報が充分速くｋに伝達されない場合である。しかし、尚早な満了では共通リソースの過度な使用は生じない。
【００５８】
図２に示す種類のネットワークにおいて、各制御メッセージで伝送されるデータ量は一般に、競合するリンクの個数の関数として極めて急速に増大し得る。
【００５９】
更に、満了時間として絶対日付を使用するには、全てのノードのクロックの同期化を必要とするが、これはアドホックネットワークでは比較的複雑になり得る。この目的のため、例えば全てのノードに共通のクロック送信元（例：ＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ（全地球移動局測定システム）の略語）レシーバ）またはＮＴＰ（Ｎｅｔｗｏｒｋ  Ｔｉｍｅ  Ｐｒｏｔｏｃｏｌ（ネットワークタイムプロトコル）の略語）同期化プロトコルのような同期化プロトコルを用いることが可能である。
【００６０】
これらの短所を克服すべく、本発明の特定の一実施形態において、容量共有分散処理システム１００は、満了時間を離散化してＮ＋１個の値に因子分解すべく構成できる。
【００６１】
本記述の以下の部分において、非限定的な例として、ｎ、ＮおよびＱの関数として定義される以下の周期を用いて満了時間を離散化および因子分解する。
【数１６】
2015065653.tif 000018
【００６２】
これらの周期を現在時刻ｔに共に用いて将来における時間間隔を定義する。
【００６３】
更に、本実施形態では、以下に定義するＮ＋１個の離散集合
【数１７】
2015065653.tif 000019
により集合Ｅｉｊを代替する。
【数１８】
2015065653.tif 000020
【００６４】
リンクの効率的な使用に関する情報は従ってこれらの離散集合内で符号化される。
【００６５】
リンクを介して送信された制御メッセージ（以下「因子分解された制御メッセージ」と表記）は従って、全体集合Ｅｉｊではなく（Ｎ＋１）個の離散集合
【数１９】
2015065653.tif 000021
（各集合
【数２０】
2015065653.tif 000022
は（ｉ，ｊ）と競合するリンクを含む）を含む。因子分解された制御メッセージの受信に応答して、ノードｊは本発明の特定の実施形態に従い、因子分解されたメッセージを解釈する方法を実行できる。
【００６６】
因子分解された集合をこのように用いることにより、満了時間は暗黙的であってよい。従ってメッセージはもはや、絶対日付を一切含まず、時間を跨って共通な基準を有している必要がない。また、絶対日付に代えて将来の期間を用いることで、もはやクロックの同期化は必要でない。
【００６７】
図３は、現在日付ｔにおいて、集合
【数２１】
2015065653.tif 000023
を含むリンク（ｉ，ｊ）を介して受信されたメッセージの受信（３００）に応答して、現在のノードｊにより因子分解された制御メッセージを解釈する方法を示すフロー図である。
【００６８】
リンク（ｉ，ｊ）と競合する全てのリンク（ｋ，ｌ）に対して（ステップ３０１）、ノードｊにより局所的に保持されたトポロジーに関する情報に基づいて送信元ｋが現在のノードｊでないか否かをステップ３０２において最初に判定する。
【００６９】
送信元ｋが現在のノードｊとは異なる場合、０〜Ｎの範囲で動く添え字ｎの各々の値に対してステップ３０４〜３０６を実行する（ステップ３０３）。
【００７０】
より正確には、ステップ３０４において、リンク（ｋ，ｌ）が集合
【数２２】
2015065653.tif 000024
に含まれているか否かを判定する。この目的のため、集合
【数２３】
2015065653.tif 000025
を添え字ｎの昇順に調べる。リンク（ｋ，ｌ）が集合
【数２４】
2015065653.tif 000026
内で発見されない限り、満了時間ＮｋｌがＮｋｌ≧ｔ＋Δｎを満たすものと考えられる。リンク（ｋ，ｌ）が集合
【数２５】
2015065653.tif 000027
に含まれていない場合、ステップ３０５においてリンク（ｋ，ｌ）の満了時間Ｎｋｌをｔ＋Δｎに延長する。満了時間Ｎｋｌを値ｔ＋Δｎに延長するのはＮｋｌの現在の値が当該値より小さい場合だけである。満了時間の更新はノードｊに局所集合Ｅｊ内で行われる。満了時間を延長するステップにより、より早く到達した先行情報よりも到達時間が遅かった情報に基づいてより大きい値が削減されないようにできる。例えば、三角形内の３個のノードａ、ｂ、ｃを考慮し、且つ、
−ａは最初に、リンク（ｃ，ｂ）が日付ｔ１まで使用されないことを示すメッセージをｃから受信し、
−ａは次いで、リンク（ｃ，ｂ）が日付ｔ２（ｔ２＜ｔ１）まで使用されないことを示すメッセージをｂから受信する
ことを仮定することにより、（ｃ，ｂ）の満了時間が更新されるのは最初のメッセージを受信したときだけである。
【００７１】
リンク（ｋ，ｌ）が既に集合
【数２６】
2015065653.tif 000028
に含まれている（３０４）場合、次のリンクは以降の添え字ｎの集合を考慮せずに処理される。より正確には、ステップ３０６においてｎがＮと異なる場合、ｎはステップ３０７で増分されて、ステップ３０４、３０５に従い次の集合
【数２７】
2015065653.tif 000029
が処理される。一方、ｎ＝Ｎの場合、未だ全てのリンクが処理済みでなければ、（ｉ，ｊ）と競合する新規のリンク（ｋ，ｌ）がステップ３０１を繰り返すことにより処理される。（ｉ，ｊ）と競合するリンク（ｋ，ｌ）が全て処理済みであれば本方法は終了する。
【００７２】
同様に、ステップ３０４においてリンク（ｋ，ｌ）が集合
【数２８】
2015065653.tif 000030
に含まれていると判定された場合、（ｉ，ｊ）と競合する新規のリンク（ｋ，ｊ）が全て処理済みではなく、且つ（ｉ，ｊ）と競合するリンク（ｋ，ｌ）が全て処理済みであれば本方法は終了する。
【００７３】
制御メッセージに含まれる情報量は、メッセージが送信されるリンクと競合するリンクの個数に依存する場合がある。本発明の特定の特徴によれば、特定のデータ構造を用いることにより、制御メッセージに固定サイズを割り当てることが可能である。
【００７４】
本発明の一実施形態において、Ｂｌｏｏｍフィルタを用いて集合
【数２９】
2015065653.tif 000031
を表現して集合
【数３０】
2015065653.tif 000032
内におけるリンクの存在を調べることができる。Ｂｌｏｏｍフィルタは集合の確率的表現である。従って各ノードｉは集合Ｅｉを保持し、Ｂｌｏｏｍフィルタにより集合
【数３１】
2015065653.tif 000033
を表す。ノードｊがメッセージを受信した場合、どの集合Ｅｉｊ（同じくＥｊｉに）に含まれるリンクであるかを知ることができ、メッセージ内でＢｌｏｏｍフィルタにより表現された集合
【数３２】
2015065653.tif 000034
内におけるそれらの存在を調べることができる。
【００７５】
集合
【数３３】
2015065653.tif 000035
を表現するためにＢｌｏｏｍフィルタを用いることで特に、固定サイズの制御メッセージの使用を可能にする。
【００７６】
図４に、Ｂｌｏｏｍフィルタ１３の一例を示す。図４に示すように、Ｂｌｏｏｍフィルタは、ある要素が集合に存在しない（「偽陰性」の欠如）ことが確実に分かり、ある確率で当該要素が存在する（「偽陽性」の可能性）ことが分かるコンパクトな確率的データ構造である。当該構造は特に、リンク（ｋ，ｌ）が集合
【数３４】
2015065653.tif 000036
内に含まれているか否かを確実性に判定すべく図３のステップ３０４で用いられてよい。
【００７７】
Ｂｌｏｏｍフィルタは、サイズｍのビットテーブル１３０および対象集合の要素のｋ個のハッシュ関数Ｈ０，Ｈ１，．．．，Ｈｋ−１を用いて実装できる。ハッシュ関数の集合により、テーブル１３０内での位置に対応するキー集合を当該集合の各要素に関連付けることができる。
【００７８】
図４の例は、Ｂｌｏｏｍフィルタの特徴を示す簡素化された例である。図に示すＢｌｏｏｍフィルタは、要素ｗと共に、集合｛ｘ，ｙ，ｚ｝を含む要素１３１に関連付けられている。矢印１３２は、３個のハッシュ関数により要素１３１（ｘ、ｙ、ｚおよびｗ）が関連付けられているテーブル１３０内の位置を示す。
【００７９】
Ｂｌｏｏｍフィルタを構築するには、最初にテーブルを全て０にリセットし、次いで添え字がｍを法とするキーであるテーブルのセルを１に設定することにより当該集合の各要素を初期化する。テーブルのある要素が当該集合に属するか否かを調べるために、最初に自身のキーをハッシュ関数を用いて計算する。続いて、計算されたキーの各々について、テーブル内の対応するビットが１であるか否かを判定する。これらのビットのうち少なくとも１つが０である場合、表現された集合に当該要素が含まれていないものと確実に推論することができる。しかし、当該ビットが全て１である場合、当該要素が当該集合内に事実上含まれている可能性があるが、確認された訳ではない。
【００８０】
図４の例では、テーブルのサイズはｍ＝２３であって、３個のハッシュ関数が用いられている（ｋ＝３）。テーブルを用いて、要素ｘ、ｙおよびｚが恐らくは存在し、関連付けられた位置の１個が０を含むため、当該集合内に要素ｗが存在しないと確実に判定できる。
【００８１】
各集合
【数３５】
2015065653.tif 000037
はこのようにＢｌｏｏｍフィルタにより表現でき、従って制御メッセージ内で固定サイズを占めることができる。集合
【数３６】
2015065653.tif 000038
内にリンクが存在することは、その不使用が日付ｔ＋Δｎ−１を越えてはならないことを意味する。従って、当該リンクは日付ｔ＋Δｎ−１から始めて使用されるものと考えられる。集合内の「偽陽性」は、ｊが実際には「未使用」のに「使用中」とされたリンクであることを意味する。しかし、「使用中」リンクは「未使用」とは見なされず、これにより利用可能なリソースが絶対に過剰使用されないことが保証される。
【００８２】
ノードｊはトポロジーの状況を知っているためリンク（ｋ，ｌ）の状況を知っており、Ｂｌｏｏｍフィルタにより表現される集合
【数３７】
2015065653.tif 000039
内におけるリンクの有無から満了時間Ｎｋｌが推論可能であるため、三つ組（ｋ，ｌ，Ｎｋｌ）へのアクセスが可能になる。
【００８３】
図５は、本発明の特定の実施形態に従い、送信される制御メッセージを経由させるリンク（ｉ，ｊ）に対して（５００）、現在のノードｉによる最適化された制御メッセージを生成する方法を表すフロー図である。
【００８４】
リンク（ｉ，ｊ）と競合する全てのリンク（ｋ，ｌ）に対して（ステップ５０１）、送信元ｋが現在のノードｉに対応するか否かをステップ５０２において判定する。
【００８５】
送信元ｋが現在のノードｉに対応する場合、次いでステップ５０４においてリンク（ｋ，ｌ）が頻繁に使用されているか否かを判定する。ステップ５０４は、本発明の用途に応じて異なる仕方で行われてよい。例えば、リンク（ｋ，ｌ）が頻繁に使用されるか否かを、ユーザデータの少なくとも１つのパケットが、システムによりパラメータとして与えられた最後の１秒または他の任意の期間内に送信されたことを確認することにより判定できる。
【００８６】
リンク（ｋ，ｌ）が頻繁に使用されている場合、ステップ５０５において（ｋ，ｌ）の満了時間Ｎｋｌをｔに短縮する。さもなければ、ステップ５０６において（ｋ，ｌ）の満了時間Ｎｋｌをｔ＋Ｑに延長する。
【００８７】
ステップ５０７において、送信元ｋが宛先ノードｊであるか否かを判定する。宛先ノードでない場合、０〜Ｎの範囲で動く添え字ｎの任意の値に対してステップ５０９、５１０が実行される（５０８）。
【００８８】
より正確には、ステップ５０９において、リンク（ｋ，ｌ）の満了時間Ｎｋｌがｔ＋Δｎより短いか否かを判定する。
【００８９】
満了時間Ｎｋｌがｔ＋Δｎより短い場合、ステップ５１０において、リンク（ｋ，ｌ）は集合
【数３８】
2015065653.tif 000040
に挿入される。
【００９０】
満了時間Ｎｋｌがｔ＋Δｎ以上の場合（５０９）、ｎがＮと異なれば新たなｎの値に対してステップ５０９、５１０が繰り返される（ステップ５１１、５１２）。ｎがＮに等しい場合、または集合
【数３９】
2015065653.tif 000041
へのリンクの挿入に応答して（５１０）、ステップ５０１においてリンク（ｉ，ｊ）と競合する別のリンクが処理される。競合する全てのリンクが処理済みであれば本方法は終了する。
【００９１】
メッセージの送信元はこのように、下りリンクが現在使用中である（ステップ５０５において）場合、下りリンクの満了時間を短縮する。最適化された制御メッセージを生成する本方法により、メッセージを受信するノードが、リンクの使用に関する情報をより速く伝達するために、特定の状況下で満了時間を短縮することができる。
【００９２】
図６は、本発明の好適な実施形態に従い、そのように最適化されたメッセージを、現在のノードｊが、現在日付ｔにおいてリンク（ｉ，ｊ）を介して受信された（６００）メッセージに応答して、当該メッセージに含まれる集合
【数４０】
2015065653.tif 000042
について、解釈するステップを示すフロー図である。図６のフロー図は、図３の解釈方法の拡張を構成する。
【００９３】
リンク（ｉ，ｊ）と競合する全てのリンク（ｋ，ｌ）に対して（６０１）、送信元ｋが現在のノードであるか否かをステップ６０２において判定する。
【００９４】
送信元ｋが現在のノードでない場合、ステップ６０４は、０〜Ｎの範囲の添え字ｎの任意の値に対して（６０３）実現される。
【００９５】
より正確には、ステップ６０４において、リンク（ｋ，ｌ）が集合
【数４１】
2015065653.tif 000043
内に含まれているか否かを判定する。リンク（ｋ，ｌ）が集合
【数４２】
2015065653.tif 000044
内に含まれていない場合、ステップ６０５において（ｋ，ｌ）の満了時間をｔ＋Δｎに延長する。
【００９６】
一方、リンク（ｋ，ｌ）が集合
【数４３】
2015065653.tif 000045
内に含まれている場合、ステップ６０６において、ｉとｋとの間の距離がｊとｋとの間の距離（ホップ数としての距離）より厳密に短いか否かを判定する。
【００９７】
ｉとｋとの間の距離がｊとｋとの間の距離より厳密に短い場合、ステップ６０７において（ｋ，ｌ）の満了時間をｔ＋Δｎ−１に短縮する。従って、ノードｉがｊよりもリンク（ｋ，ｌ）の送信元に近い場合、ｉにより伝達される情報が既にｊから知らされたものよりも「新鮮」である可能性が極めて高い。ｊが（ｋ，ｌ）の満了時間を短縮できるのはこのためである。従って効率的なリンクの使用に関する情報を伝達することが可能である。実際、あるリンクが使用され始めた場合、自身への割り当てが望まれるリソースの配分を取り戻すべく他のノードで当該リンクの満了時間が満了するのを待つのは、当該ノードがこの変化により速く応答するため無意味である。
【００９８】
ｉとｋとの間の距離がｊとｋとの間の距離以上であるか、または満了時間Ｎｋｌの更新（６０７）に応答して、（ｉ，ｊ）と競合する別のリンク（ｋ，ｌ）がステップ６０１において処理される。全てのリンクが処理済みであれば、本方法は終了する。
【００９９】
（ｋ，ｌ）の満了時間の延長に応答して（６０５）、ｎがＮと異なる場合、ステップ６０８においてｎは増分され、ステップ６０４において次の集合
【数４４】
2015065653.tif 000046
が処理される。一方、ｎ＝Ｎである場合、未だ全てのリンクが処理済みでなければ、（ｉ，ｊ）と競合する新規のリンク（ｋ，ｌ）がステップ６０１を繰り返すことにより処理される。（ｉ，ｊ）と競合するリンク（ｋ，ｌ）が全て処理済みであれば本方法は終了する。
【０１００】
共有システム１００は、補足的に、制御メッセージ１２の生成時点でノードが集合
【数４５】
2015065653.tif 000047
を生成できるようにすべく局所トポロジーを発見するプロトコルを用いる場合がある。発見プロトコルは、メッシュ、無線またはモバイルネットワーク向けに設計されたＯＬＳＲ（「Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｋ  Ｓｔａｔｅ  Ｒｏｕｔｉｎｇ（最適リンク状態ルーティング）」の略語）ルーティングプロトコルの例と同様に、使用するルーティングプロトコルの一部をなしていてよい。
【０１０１】
ここに記述する本発明の実施形態に従い満了時間を利用することで、任意の所与の時点において、どのリンクが使用されているかを知ることができる。リソースの使用可能な配分が下りリンクにより更新された場合、システム１００は、対象下りリンクを含む競合グラフのクリークにおいて使用されているリンクの最大数を判定することができる。
【０１０２】
従って本発明により、ネットワーク内のリンクの効率的な使用に関する情報を潜在的に注目されるノードに伝達することができる。
【０１０３】
この結果、競合するリンク間で共通リソースが公平に配分されるため、あるリンクと競合する他のリンクがリソースの配分を過度に受けている場合に当該リンクでリソースの不足を抑制できる状況がもたらされる。
【０１０４】
本発明は、非限定的な例を示して上で説明した実施形態に限定されない。本発明は、当業者に想到可能なあらゆる変型実施形態を包含している。特に、本発明はアドホックネットワークにおいて特に利点を有しているが、そのような通信ネットワークに限定されず、リンクのリソースが共通である他の種類の通信ネットワークにも適用できる。本発明はまた、特定の共通リソースに限定されない。例えば、ノード間で共有される共通リソースは容量（１秒当たりビット数での最大データ速度）、または複数の隣接するリンク間で共有される他の任意の種類のリソースであってよい。
【０１０５】
当業者には、本発明の実施形態による容量共有分散処理システムが下位要素と共に、ハードウェア、ソフトウェア、またはハードウェアとソフトウェアの組み合せにより様々な仕方で実装可能であることが理解されよう。
【０１０６】
特に、容量共有システムの要素は、本発明を実装するために組み合せても、あるいは下位要素に分割されてもよい。更に、これらの要素は、プロセッサにより実行されるコンピュータプログラムの形式で実装されてもよい。コンピュータプログラムは、コンピュータにより直接または間接的に使用可能な命令の集合である。
【０１０７】
コンピュータプログラムは、コンパイラまたはインタプリタ言語を含む任意の所与のプログラミング言語で書かれていてよく、且つ選択されたデータ処理環境内で任意の所与の形式で搭載されていてよい。
【符号の説明】
【０１０８】
１０  ノードの集合
１１  リンク
１２  制御メッセージ
１３  データ構造
１００  容量共有分散処理システム
１３０  ビットテーブル
１３１  テーブル要素
ａ，ｂ，ｃ，ｄ，ｅ，ｆ，ｉ，ｊ，ｋ，ｌ  ノード
ｗ，ｘ，ｙ，ｚ  要素
Ｅｉ，Ｅｊ，Ｅｋ，Ｅｌ  三つ組の集合
Ｎａｂ，Ｎｂａ，Ｎｂｃ，Ｎｃｂ，Ｎｃｄ，Ｎｄｃ，Ｎｄｅ，Ｎｅｄ  満了時間
【図１】
2015065653.tif 000058
【図２Ａ】
2015065653.tif 000059
【図２Ｂ】
2015065653.tif 000060
【図３】
2015065653.tif 000061
【図４】
2015065653.tif 000062
【図５】
2015065653.tif 000063
【図６】
2015065653.tif 000064
【外国語明細書】
2015065653000001.pdf