(57)【特許請求の範囲】
【請求項１】
複数のコンピューティングデバイスを含むネットワークの電源管理のための方法であって、
所定の期間内で１つまたは複数のコンピューティングデバイスの間のフローの順番を識別するステップと、
コンピューティングデバイスを共有する隣接フローの数を増すことによって、少なくとも１つのコンピューティングデバイスのためのウェイクアップの数を減らすステップと
を備え、
前記１つまたは複数のデバイスのためのウェイクアップの数を減らす前記ステップは、
頂点／エッジグラフを導出するステップであって、前記頂点／エッジグラフの頂点はコンピューティングデバイスを表現し、前記頂点／エッジグラフのエッジはコンピューティングデバイスのペアの間のデータ通信を表現するステップと、
２つの関連付けられた頂点の間に渡る第１のエッジを選択するステップであって、前記２つの関連付けられた頂点は、他のいかなる関連付けられた頂点のペアと比較しても縮小ディグリーを有するステップと、
前記第１のエッジを除去するステップと、
前記第１のエッジの後続の隣のエッジを選択し、前記後続のエッジを除去するステップと、
前記後続のエッジを除去するステップとによって実行され、
前記第１のエッジおよびいかなる後続のエッジもが除去される順番は、前記ネットワーク内の前記フローの前記順番に対応することを特徴とする方法。
【請求項２】
前記エッジの前記縮小ディグリーは、前記関連付けられた頂点のうち一方は前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有すること、および、前記エッジの他方の関連付けられた頂点は、前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有する１つの頂点の隣のものである他のいかなる頂点よりも低いディグリーを有することを、示すことを特徴とする請求項１に記載の方法。
【請求項３】
前記１つまたは複数のデバイスのためのウェイクアップの数を減らす前記ステップは、各タイムフレーム内のコンピューティングデバイスの順番を、縮小ディグリーサーチ計算に基づいてスケジューリングすることによって実行されることを特徴とする請求項１に記載の方法。
【請求項４】
前記ネットワークはローカルエリアネットワーク（ＬＡＮ）を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記ネットワークは無線パーソナルエリアネットワーク（ＷＰＡＮ）を含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記ネットワークはＩＥＥＥ ８０２．１５．３規格に準拠することを特徴とする請求項１に記載の方法。
【請求項７】
前記ネットワークは無線ネットワークを含むことを特徴とする請求項１に記載の方法。
【請求項８】
前記ネットワーク内の多数のコンピューティングデバイスの間のデータ通信を、いくつかの頂点およびいくつかのエッジを含むようにグラフィカルに表現することができることを特徴とする請求項１に記載の方法。
【請求項９】
頂点／エッジグラフを生成するステップをさらに備え、前記ネットワークは、前記頂点／エッジグラフ内の複数の異なる頂点の間に渡るいくつかのエッジを含み、前記エッジを前記フローに関連付けるステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
時分割多元接続（ＴＤＭＡ）ネットワークのための電源管理の方法であって、
前記ＴＤＭＡネットワークを表現する頂点／エッジグラフを導出するステップであって、前記頂点／エッジグラフの頂点はコンピューティングデバイスを表現し、前記頂点／エッジグラフのエッジはコンピューティングデバイスのペアの間のデータ通信のためのリクエストを表現するステップと、
関連付けられた第１の頂点のペアを有する第１のエッジを選択するステップであって、前記関連付けられた第１の頂点のペアは、前記頂点／エッジグラフ内のいかなるエッジの関連付けられた頂点のいかなるのペアとも同じかまたはより低い順番を有するステップと、
前記選択された第１のエッジを前記頂点／エッジグラフから除去するステップと、
２つの関連付けられた第２の頂点を有する、前記第１のエッジの隣のものである第２のエッジを選択するステップであって、前記関連付けられた第２の頂点は、前記頂点／エッジグラフ内の前記第１のエッジのいかなる隣のエッジの関連付けられた頂点のいかなるペアとも同じかまたはより低いディグリーを有するステップと、
前記選択された第２のエッジを前記頂点エッジグラフから除去するステップとを備え、  前記第１のエッジおよびいかなる後続のエッジもが除去される順序は、対応するコンピューティングデバイスが対応するデータ信号を前記ＴＤＭＡネットワークを介して送信するようになる順番に相関することを特徴とする電源管理の方法。
【請求項１１】
２つの関連付けられた第３の頂点を有する、前記第２のエッジの隣のものである第３のエッジを選択するステップをさらに備え、前記関連付けられた第３の頂点は、前記頂点／エッジグラフ内の前記第２のエッジのいかなる隣のエッジの関連付けられた頂点のいかなるペアとも同じかまたはより低いディグリーを有し、各エッジが除去される順番は、対応するコンピューティングデバイスが対応するデータ信号を前記ＴＤＭＡネットワークを介して送信するようになる順番に相関することを特徴とする請求項１０に記載の電源管理の方法。
【請求項１２】
前記第１のエッジの縮小ディグリーは、前記第１のエッジの前記関連付けられた頂点のうち一方は前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有すること、および、前記第１のエッジの他方の関連付けられた頂点は、前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有する１つの頂点の隣のものである他のいかなる頂点よりも低いディグリーを有することを、示すことを特徴とする請求項１０に記載の電源管理の方法。
【請求項１３】
第１の候補頂点および第１の隣の頂点の前記ディグリーを減らすステップは、縮小結合ディグリーを有する前記頂点のペアを選択することを可能にすることを特徴とする請求項１０に記載の電源管理の方法。
【請求項１４】
第１の候補頂点および第１の隣の頂点の前記ディグリーを減らすステップは、縮小結合ディグリーを有する前記頂点のペアを選択することを可能にすることを特徴とする請求項１０に記載の電源管理の方法。
【請求項１５】
プロセッサによって実行されたとき、前記プロセッサに、電源管理を複数のコンピューティングデバイスに提供させる、コンピュータ可読命令を有するコンピュータ可読媒体であって、前記提供は、
データを所定の期間内で送信することができる１つまたは複数のコンピューティングデバイスの順序を得ることによって行われ、
前記電源管理は、所定の期間内で共通コンピューティングデバイスを共有する、関連付けられたチャネル時間割り振り期間の数を増すことによって実行される、ネットワーク内で前記コンピューティングデバイスのためのウェイクアップの数を減らすことによって、提供され、
前記ウェイクアップの数を減らすことは、
前記ネットワークを表現する頂点／エッジグラフを導出することであって、頂点はコンピューティングデバイスを表現し、エッジはコンピューティングデバイスのペアの間のデータ通信のためのリクエストを表現すること、
関連付けられた第１の頂点のペアを有する第１のエッジを選択することであって、前記関連付けられた第１の頂点のペアは、前記頂点／エッジグラフ内の関連付けられた頂点のいかなるペアもの最低のディグリーを有するかあるいは共有すること、
前記選択された第１のエッジを除去すること、
前記除去された第１のエッジの隣のものであった第２のエッジを選択することであって、前記第２のエッジは、関連付けられた第２の頂点のペアを有し、前記関連付けられた第２の頂点のペアは、前記除去された第１のエッジのいかなる隣のもののいかなる関連付けられた頂点のペアの前記ディグリーよりも低いかまたはそれに等しいこと、および
前記選択された第２のエッジを除去することによって実行され、
前記第１のエッジ、前記第２のエッジ、およびいかなる後続の選択されたエッジもが除去される順序は、対応するコンピューティングデバイスが対応するデータ信号を前記ネットワークを介して送信するようになる順番に対応することを特徴とするコンピュータ可読媒体。
【請求項１６】
時分割多元接続（ＴＤＭＡ）ネットワークのための電源管理部を備え、前記ＴＤＭＡネットワークは複数のコンピューティングデバイスを含み、前記電源管理部は、前記ＴＤＭＡネットワーク内のコンピューティングデバイスのためのウェイクアップの数を、
前記ＴＤＭＡネットワークを表現する頂点／エッジグラフを導出する手段であって、頂点はコンピューティングデバイスを表現し、１つのエッジはコンピューティングデバイスのペアの間のデータ通信のための各リクエストを表現する手段と、
前記頂点／エッジグラフ内のいかなるエッジもの最低ディグリーを少なくとも共有する第１のエッジを選択する手段と、
前記選択された第１のエッジを除去する手段と、
前記第１のエッジの隣のものである隣のエッジを選択する手段であって、前記隣のエッジは、前記第１のエッジの隣のものであるいかなるエッジもの最低ディグリーを有するかあるいは共有する手段と、
前記隣のエッジを除去する手段とを使用することによって減らし、
前記第１のエッジおよび前記隣のエッジが除去される順番は、対応するコンピューティングデバイスが前記ＴＤＭＡネットワークを使用することを許可されるようになる順番に対応することを特徴とする装置。
【請求項１７】
前記第１のエッジの最低ディグリーを選択する手段は、前記第１のエッジの関連付けられた頂点のうち一方は前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有すること、および、前記第１のエッジの他方の関連付けられた頂点は、前記グラフ内でいかなる頂点とも同じかまたはより低いディグリーを有する１つの頂点の隣のものである他のいかなる頂点よりも低いディグリーを有することを、示すことを特徴とする請求項１６に記載の装置。
【請求項１８】
前記隣のエッジを選択すること、および前記隣のエッジを除去することを繰り返す手段をさらに備えることを特徴とする請求項１６に記載の装置。
【請求項１９】
前記第１のエッジの前記ディグリーを減らす手段は、縮小結合ディグリーを有する、前記第１のエッジへの関連付けられた頂点の選択を可能にすることを特徴とする請求項１６に記載の装置。
【請求項２０】
前記隣のエッジの前記ディグリーを減らす手段は、縮小結合ディグリーを有する、前記隣のエッジへの関連付けられた頂点の選択を可能にすることを特徴とする請求項１６に記載の装置。
【請求項２１】
複数のコンピューティングデバイスを有する時分割多元接続ネットワークのための電源管理部を備え、前記電源管理部は、前記ネットワーク内のコンピューティングデバイスのためのウェイクアップの数を、
頂点／エッジグラフであって、前記頂点／エッジグラフの頂点はコンピューティングデバイスを表現し、前記頂点／エッジグラフのエッジはコンピューティングデバイスのペアの間のデータ通信のためのリクエストを表現する、頂点／エッジグラフと、
２つの関連付けられた第１の頂点を有する第１のエッジであって、前記２つの関連付けられた第１の頂点は、前記頂点／エッジグラフ内のいかなる関連付けられた頂点のペアのディグリーの合計にも等しいかまたはより少ない合計ディグリーを有する、第１のエッジとを使用することによって減らし、
前記電源管理部は、前記第１のエッジおよびいかなる後続のエッジもが除去される順番を、対応するコンピューティングデバイスが前記ネットワークを使用することを許可されるようになる順番に関係付けられると見なすことを特徴とする装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピューティングデバイスに関し、より詳細には、コンピューティングデバイスを含むネットワーク内で電力を節約することに関する。
【背景技術】
【０００２】
ある時分割多元接続（ＴＤＭＡ）ネットワークは、いくつかのコンピューティングデバイスを、ＴＤＭＡ技術に基づいたリンクを介して接続する。ＴＤＭＡでは、ネットワークアクセスはいくつかのコンピュータの間で、いくつかの連続したタイムスロット内で細分される。タイムフレーム内の各タイムスロット中に、１つのコンピューティングデバイスにネットワークの使用が割り振られる。コンピューティングデバイスは、特定のタイムスロット内でデータを送信または受信中である場合、そのタイムスロットについてアウェイク（ａｗａｋｅ）になることができる。（特に無線ネットワーク内で、および／または、携帯情報端末（ＰＤＡ）およびハンドヘルドもしくは携帯電話など、バッテリで動作するコンピューティングデバイスで）電力を節約するために、コンピューティングデバイスを、データの送信または受信中でないタイムスロット中にスリープさせることが望ましい場合がある。しかし、コンピューティングデバイスをウェイクアップさせることもまた、相当な電力を消費する。したがって、ネットワーク内のコンピューティングデバイスの電源管理はしばしば、コンピューティングデバイスをアウェイクのまま保つことによって消費される電力を、あるコンピューティングデバイスをスリープさせた直後にそれらのコンピューティングデバイスをウェイクアップさせることによって消費される電力と比較して、このバランスを取ることを伴う。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
あるコンピューティングデバイス、無線および携帯電話、ＰＤＡおよび無線電子デバイスは、バッテリを使用する。バッテリベースのコンピューティングデバイスのためのエネルギー消費量を減らすことにより、デバイスのバッテリ充電寿命が増す。電力消費量はしばしば、コンピューティングデバイスがアウェイクのまま保たれるかどうか、スリープに入ることが許可されるかどうか、または、アウェイク状態とスリープ状態の間で移行されるかどうかに関係付けられる。電源管理は、長期間に渡ってネットワーク上で動作することができるコンピューティングデバイスの設計において、重要な要素となる。
【０００４】
コンピューティングデバイスのための電源管理を改善することが有益となるであろう。
【０００５】
【非特許文献１】"Part 15.3: Wireless WPAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications for High Rate Wireless Personal Area Networks (WPAN)"という名称のIEEE 802.15.3
【課題を解決するための手段】
【０００６】
本開示は、複数のコンピューティングデバイスを含むネットワークのための電源管理技術の多数の態様を説明する。この電源管理技術は、複数のコンピューティングデバイスのうち１つまたは複数のデバイスがデータを所定の期間内で送信することができる順序を識別することを含む。ネットワーク内のコンピューティングデバイスのためのウェイクアップの数は、所定の期間内で共通コンピューティングデバイスを共有する、隣接チャネル時間割り振り期間の数を増すことによって、減らされる。
【発明を実施するための最良の形態】
【０００７】
同じ符号を、本明細書の全体に渡って、類似のコンポーネントおよび／または特徴を参照するために使用する。  
本開示はコンピューティングデバイスに関し、より詳細には、図１および１１に関して説明するような、時分割多元接続（ＴＤＭＡ）ネットワーク内に配列されるコンピューティングデバイスの電源管理に関する。「フロー」は、図３、４ａおよび４ｂに関して説明するように、ＴＤＭＡベースのネットワーク内である順序で配列することができる複数の異なるコンピューティングデバイスの間の望ましい通信パスに関する。本開示は、ＴＤＭＡベースのネットワーク内のコンピューティングデバイスのためのウェイクアップの数を減らすために、各フローについての順序を導出する、縮小ディグリーサーチ（ｒｅｄｕｃｅｄ  ｄｅｇｒｅｅ  ｓｅａｒｃｈ）技術を提供する。
【０００８】
縮小ディグリーサーチ技術はＴＤＭＡネットワークを、コンピュータベースの頂点／エッジグラフを使用してモデリングする。この頂点／エッジグラフの実施例を図５、６、８、９および１０に関して説明する。頂点／エッジグラフでは、頂点は個々のコンピューティングデバイスをモデリングし、エッジは個々のコンピューティングデバイスの間のフローをモデリングする。頂点／エッジグラフ内の各頂点のディグリー（縮小ディグリーサーチ技術において検討される）は、頂点に接続するエッジの数を示す。縮小ディグリーサーチ技術の一実施形態を、図７のフロープロセスにおいて説明する。
【０００９】
電源管理  
コンピューティングデバイス（パーソナルコンピュータ、ネットワークコンピュータ、ワークステーション、メインフレーム、無線デバイス、コンシューマエレクトロニックデバイス、ポータブル、無線および携帯電話デバイス、オーディオデバイス、ビデオデバイス、グラフィックデバイス、ポータブルマルチ媒体デバイスなど）を、無線パーソナルエリアネットワーク（ＷＰＡＮ）など、様々なネットワークに接続させることができる。本開示では、「コンピューティングデバイス」という用語は幅広く解釈されるように意図され、計算の結果を導出、使用および／または表示するいかなるデバイスにも適用される。適用可能なＷＰＡＮ規格がある（例えば、非特許文献１参照。）。しばしば、ＷＰＡＮなどのネットワークは１つまたは複数のバッテリベースのコンピューティングデバイスを含む。このようなバッテリベースのコンピューティングデバイスの充電持続時間はしばしば制限されており、ネットワークの電源管理において、これらのコンピューティングデバイスのバッテリ充電持続時間を延ばすための要素となる可能性がある。
【００１０】
ＷＰＡＮプロトコルは、タイムスロット（例えば、ＷＰＡＮにおけるチャネル割り振りスロット）をネットワーク内の異なるコンピューティングデバイスに割り振るために、媒体アクセス制御層に適用されるような、時分割多元接続（ＴＤＭＡ）の概念に依拠する。本開示内では、ＴＤＭＡという用語は、タイムスロットがコンピューティングデバイスに割り振られるいかなるプロトコルにも適用される。ＴＤＭＡにより、多数のネットワークコンピューティングデバイスはそれぞれリソース（ネットワークまたはサーバなど）へのアクセスを、ある競合割り振りスキーム（ｃｏｎｔｅｎｔｉｏｎ  ａｌｌｏｃａｔｉｏｎ  ｓｃｈｅｍｅ）を使用して共有する。ＴＤＭＡは、フレームのシーケンスを含むフレーム構造に基づき、各フレームは多数のタイムスロットを含む。各タイムスロット中に、１つの特定のコンピューティングデバイスがネットワークの使用を割り振られる。
【００１１】
１つのコンピューティングデバイス（本開示では、ネットワークコーディネータデバイスと称する）は、どのコンピューティングデバイスがいずれかのタイムスロット中にネットワークを介してデータを送信するかをコントロールする。ネットワークコーディネータデバイスは、タイムスロットを競合スキームに基づいて割り振る。一実施形態では、ネットワークコーディネータデバイスは、ネットワーク使用をリクエスト中であるコンピューティングデバイスの間で、タイムスロットを各フレームに対して割り振る。
【００１２】
本開示は、デバイスがスリーピング状態からアウェイクされる頻度を減らすことによって、コンピューティングデバイスの多数によって費やされる電力を減らす電源管理技術を提供する。ネットワーク上のコンピューティングデバイスによって使用される電力を減らすことにより、これらのコンピューティングデバイスの（バッテリを交換または再充電する前の）バッテリ充電寿命が延長される。
【００１３】
図１は、ネットワーク１０１を含む、コンピューティング環境１００の一実施形態のブロック図を示す。ネットワーク１０１には、ＬＡＮ、ＷＰＡＮ、複数のネットワークタイプの組み合わせ、または他のいかなるタイプのネットワークもが含まれる可能性がある。図１に関して説明するネットワーク１０１を、スタンドアロンネットワークとして構成することができ、あるいは代替として、このネットワークを、このような追加のネットワークとデータを通信するために接続することができる。ネットワークコンピューティング環境１００には、ネットワークコーディネータデバイス１０５、１つまたは複数のコンピューティングデバイス１０６、および、複数のビーコン信号１０７を含めることができる。ネットワーク１０１のネットワークコーディネータデバイス１０５を、ハブ、ルータまたは別のスイッチデバイスとして構成して、ネットワークコンピューティング環境１００内の無線および／または有線ネットワーク１０１を作成することができる。
【００１４】
ビーコン信号１０７を、無線および／または有線コネクタを介して物理的に送信することができる。異なる実施形態では、コンピューティングデバイス１０６は、再充電可能または使い捨て可能なバッテリ（図示せず）のいずれかを使用して動作するようになる。バッテリは、様々なコンピューティングデバイスおよび他のコンピューティングデバイスにポータビリティを提供する。
【００１５】
ネットワーク１０１内の電源管理は、ネットワーク１０１内で機能中であるときにコンピューティングデバイスによって用いられる電力を減らすことに関する。３つの電力状態が、本開示内のネットワークにおける各コンピューティングデバイスに関与する可能性がある。コンピューティングデバイス１０１の第１の電力状態はアウェイクであり、この状態でコンピューティングデバイスはその通常のオペレーションを実行することができる。「アウェイク」という用語は、異なるコンピューティングデバイスおよび異なるネットワークによる異なる機能を可能にすることができるが、アウェイクコンピュータはネットワーク上で信号を通常の方法で送信／受信するように動作することができると想定される。コンピューティングデバイス１０６の第２の電力状態はスリープであり、この状態でコンピューティングデバイスは省電力状態であり、通常のオペレーションを実行することはできない。コンピューティングデバイス１０６の第３の電力状態は、スリープ状態とアウェイク状態の間で移行すること（すなわち、ウェイクアップ）であり、その間に、コンピューティングデバイスは相当量の電力を用いる。
【００１６】
各データ信号１０８は、ＴＤＭＡサービスを複数のコンピューティングデバイス１０６の間に提供するための方法で、複数のコンピューティングデバイス１０６の１つを別のコンピューティングデバイスへデジタル的に結合する。ネットワークコーディネータデバイス１０５、コンピューティングデバイス１０６およびデータ信号１０８は共に、ＴＤＭＡネットワーク１０１を表す。
【００１７】
図１のように、１つのビーコン信号１０７はネットワーク１０１内で、ネットコーディネータデバイス１０５から各コンピューティングデバイス１０６へ達する。一実施形態では、ネットワークコーディネータデバイス１０５はビーコン信号１０７を送信して、各コンピューティングデバイス１０６に、異なるフレーム内のタイムスロットが異なるコンピューティングデバイスに割り振られる順序を送信（例えば、ブロードキャスト）する。ネットワークコーディネータ１０５を、ネットワークを介して他のコンピューティングデバイスと効果的に通信させることができ、中央コントロール機能をネットワーク１０１に対して実行することができる、１つのコンピューティングデバイス１０６として構成し、見なすことができる。ネットワークコーディネータ１０５は、（ハードウェア、ソフトウェアおよび／またはファームウェアの態様を考察すると）ネットワーク１０１内の他のコンピューティングデバイスに類似している可能性があるが、ただし、複数の異なるコンピューティングデバイスの間でネットワークアクセスを調整する機能を提供するコンポーネントの追加がある。ネットワークコーディネータは、ＴＤＭＡネットワーク内のコンピューティングデバイスのシステムタイミング、サービス品質（ＱｏＳ）管理、電源管理、セキュリティなどを担うことができる。
【００１８】
ＴＤＭＡベースのネットワーク１０１のある実施形態は、チャネル割り振りスロット２０６（ＷＰＡＮネットワーク内で使用されるなど、タイムスロットの一実施形態である）を使用し、これを図２のフレーム２０２に関して説明する。１つのコンピューティングデバイスのみが、データ（例えば、パケット）をネットワーク１０１内で、各チャネル割り振りスロット２０６中に送信することができる。ネットワーク１０１内で動作するコンピューティングデバイス１０６は、信号を送信または受信中であるこれらのＴＤＭＡベースのチャネル割り振りスロット２０６（またはタイムスロット）中にアウェイクであり、信号を送信または受信中である他のチャネル割り振りスロット（またはタイムスロット）中にスリープになり、電力を節約することができる。コンピューティングデバイス１０６をスリープ状態からアウェイク状態へウェイクアップするには、相当量の電力がそのコンピューティングデバイス１０６によって費やされる必要がある。したがって、ネットワーク１０１のための効率的な電源管理設計を提供することは、コンピューティングデバイスをそのアウェイク状態に維持することから節約される電力を、コンピューティングデバイスをそのよりエネルギー効率の良いスリープ状態に移行して、次いでコンピューティングデバイスが参加中である次のタイムスロット中に、コンピューティングデバイスをそのアウェイク状態にウェイクアップさせる必要があるために費やされる電力と比較して、バランスを取ることを伴う。
【００１９】
本開示内でネットワーク１０１に関して説明した電源管理メカニズムは、ネットワークコンピューティングデバイス１０６のバッテリ放電率を下げる。コンピューティングデバイスをそれらの「スリープ」状態からウェイクさせる頻度が低いことにより、コンピューティングデバイス１０６の（再充電の間の）バッテリ寿命が増す。一般に、あるネットワーク内でバッテリ寿命が持続する持続時間が増すことは、ネットワーク１０１がユーザーによってよりよく受け入れられるようになる助けとなる。ＷＰＡＮは特に低電力／低コストのデバイス向けに設計される。本開示の電源節約態様はしたがって、特にＷＰＡＮにとってコンピューティングデバイスのバッテリ充電持続時間を延ばすために適している。
【００２０】
図２は、図１のネットワーク１０１内の通信に構造を提供するフレーム２０２の一実施形態（ＷＰＡＮプロトコルで説明されるスーパーフレームなど）を説明する。図１のネットワーク１０１のＭＡＣ層は、図２に関して説明するフレーム２０２の使用など、ＴＤＭＡの概念に大きく依拠する。通常のオペレーション中に、ネットワークコーディネータデバイス１０５は図１のビーコン信号１０７を、ネットワーク１０１内の互いのコンピューティングデバイス１０６に、図２のフレーム２０２内のビーコン期間２０８中にブロードキャストする。ビーコン期間２０８中に送信されたビーコン信号１０７は、各コンピューティングデバイスについてチャネル割り振りスロット２０６の特定の順序および持続時間を伝える。
【００２１】
図２に関して説明する各フレーム２０２は、チャネル割り振り期間２０４、ビーコン期間２０８および競合アクセス期間２１０（ｃｏｎｔｅｎｔｉｏｎ  ａｃｃｅｓｓ  ｐｅｒｉｏｄ）を含む。フレーム２０２をまた、ある実施形態では「スーパーフレーム」とも称する場合がある（例えば、ＷＰＡＮネットワークに適用されるものなど）。フレーム２０２内に提示される場合、競合アクセス期間２１０を使用して、コマンドおよび／または非同期データを通信することができる。
【００２２】
チャネル割り振り期間２０４の一実施形態は、１つまたは複数の管理チャネル時間割り振り（ＭＣＴＡ）期間２１２、および、１つまたは複数のチャネル割り振りスロットまたはタイムスロット（ＣＴＡ）２０６を含む。２つの例示的チャネル割り振りスロットまたはタイムスロット２０６のみを図２に示すが、多数のチャネル割り振りスロットまたはタイムスロットが存在する可能性がある。一実施形態では、ＭＣＴＡ２１２は、コンピューティングデバイス１０６とコーディネータデバイス１０５の間の通信のために使用されるＣＴＡ２０６の１タイプである。チャネル割り振りスロット２０６はフレーム２０２内で、競合ベースのＴＤＭＡプロトコルにおける単位と見なされ、これにおいて１つの特定のコンピューティングデバイスはネットワークを介してデータを送信することができる。ネットワーク１０１内の各ユーザーは、ネットワーク内のデータ転送を、フレーム２０２内のそれらの各チャネル割り振りスロット２０６中にコントロールする。
【００２３】
図１に関して説明したネットワークコーディネータ１０５は、チャネル割り振り期間２０４内で異なるチャネル割り振りスロット２０６を異なるコンピューティングデバイス１０６へ、本明細書で説明する縮小ディグリーサーチメカニズムに基づいて割り当てる。特定のチャネル割り振りスロット２０６中にどのコンピューティングデバイスがデータを受信または送信するべきであるかは、ネットワークコーディネータ１０５によって、ビーコン期間２０８中にビーコン信号を使用して識別される。ネットワークコーディネータ１０５は、各チャネル割り振り期間中に信号送信のコントロールを有するコンピューティングデバイスを導出し、これを以下でより詳細に論じる。チャネル割り振り期間の持続時間は通常、ネットワーク１０１内で設定することができる。
【００２４】
図３は、各々がコンピューティングデバイスを表現する複数の頂点、および、複数のコンピューティングデバイスの間でリクエストされた信号接続を表現するフローで構成される、フロートポロジグラフ３１０の一実施形態を説明する。フロートポロジグラフ３１０内で、フロー（図３のｆＡＢ、ｆＢＣおよびｆＣＤとして図示）は、複数のコンピューティングデバイス１０６の間のデータ信号１０８のグラフィカル表現を表現する。
【００２５】
コンピューティングデバイスは通常、スリープ状態にあるときよりもアウェイク状態にあるときに、より多くのエネルギーを消費する。全体的に電力を節約するため、コンピューティングデバイス１０６は、デバイスと接触中であるフローの両端によって示すようにアクティブにデータを送信または受信中でない、チャネル割り振り期間２０４中にスリープすることができることが望ましく、また、それらのフローについて割り振られるチャネル割り振り期間中にウェイクアップすることができることが望ましい。各コンピューティングデバイス１０６はしたがって、（図１に示すデータ信号１０８の両端、または図３に関して説明するフローで）各コンピューティングデバイス１０６がその中に含まれるチャネル割り振り期間内でのみ、ウェイクアップすることができる。各コンピューティングデバイスは、そのコンピューティングデバイスが次のチャネル割り振り期間２０４内に含まれない場合、チャネル割り振り期間の端でスリープに入ることができる。
【００２６】
本明細書で説明するように、電源管理の問題は、フロートポロジグラフ３１０（図１のネットワーク１０１内のコンピューティングデバイス１０６に関する）内で複数のコンピューティングデバイス３１２の間のフローの順序を選択して、コンピューティングデバイスのウェイクアップの総数を減らすことに関連付けられるようになる。電源管理技術（本明細書で説明する縮小ディグリーサーチ技術など）の適用は、通常のマルチコンピューティングデバイスおよびマルチフロー環境内で有益である。
【００２７】
図３のフロートポロジグラフ３１０は、コンピューティングデバイスＡ３１２とコンピューティングデバイスＢ３１２の間に渡るフローｆＡＢを含む。フローｆＢＣは、コンピューティングデバイスＢ３１２とコンピューティングデバイスＣ３１２の間に渡る。フローｆＣＤは、コンピューティングデバイスＣ３１２とコンピューティングデバイスＤ３１２の間に渡る。図３に示すフロートポロジグラフ３１０では、コンピューティングデバイスＢ３１２はデータストリームをコンピューティングデバイスＡ３１２とコンピューティングデバイスＣ３１２の間で転送することができる。コンピューティングデバイスＣ３１２は、データストリームをコンピューティングデバイスＢ３１２とコンピューティングデバイスＤ３１２の間で送信する。例えば、コンピューティングデバイスＡとコンピューティングデバイスＢの間のｆＡＢなどの例示的フロー中に、データをコンピューティングデバイスＡからコンピューティングデバイスＢへ、またはその逆へ送信することができる。したがって、フローを無方向性と見なすことができる。
【００２８】
フローの順序は、各フレーム中にウェイクアップされなければならないコンピューティングデバイス３１２の数を決定する。ネットワーク１０１内の電源管理におけるフローの順序の影響を、図４ａおよび４ｂのフローダイアグラム内で明示する。図４ａおよび４ｂのフローダイアグラムは、図３の例示的フロートポロジグラフ３１０に基づく。
【００２９】
図４ａおよび４ｂは、図３の例示的フローに示すｆＡＢ、ｆＢＣ、およびｆＣＤの複数の順序を例示する、２つの代替実施例のフローダイアグラム４００を示す。一連の３つのフローｆＡＢ、ｆＢＣおよびｆＣＤはそれぞれフレーム２０２として、図４ａおよび４ｂで配列される。フローダイアグラム４００内のフローの順序は、いくつのコンピューティングデバイス１０６がフレーム２０２中にウェイアップされなければならないかを決定する。フローダイアグラム４００内の各フローは、ゼロ、１つまたは２つのコンピューティングデバイスをウェイクアップさせることができる。２つのウェイクアップを有するフローでは、２つのコンピューティングデバイスがウェイクアップされなければならない。１つのウェイクアップを有するフローでは、１つのコンピューティングデバイスのみがウェイクアップされなければならない。ウェイクアップを有していないフローでは、ウェイクアップされなければならないコンピュータデバイスはない。
【００３０】
複数のフローがコンピューティングデバイス１０６のいずれかのペアの間にある場合、複数のフローを、図３に示すようなフローダイアグラム内で単一のフローに結合させることができ、これは、複数のフローをフレーム２０２内の連続するチャネル割り振り期間で割り振ることができるからである。同じペアのフローの間のこれらの各フローは、それにより、コンピューティングデバイスのペアの間に渡る単一のフローに関連付けられた１つのウェイクアップを超えて、ゼロのウェイクアップを与える。同じコンピューティングデバイスのペアの間の複数のフローを単一のフローに結合することにより、ネットワーク内のコンピューティングデバイスによって使用される電力が減る。
【００３１】
本開示内で論じたように、本開示内で説明する電源管理問題は主に、各コンピューティングデバイスがスリープに入っていた後にウェイクアップするために多くの電力をしばしば必要とする結果として生じる。フローダイアグラムのためのウェイクアップの数が大きいほど、より多くの平均電力がネットワーク１０１内のコンピューティングデバイスによって使用される。
【００３２】
したがって、ネットワーク１０１内のすべてのコンピューティングデバイス１０５がアウェイクされる回数が少ないほど（フローのすべての縮小された順番によって示すことができる）、一般に、ネットワーク１０１内のコンピューティングデバイスによって使用される電力は少ない。ネットワーク１０１内のコンピューティングデバイス１０５がアウェイクされる回数が少ないときほど、ネットワーク１０１内のコンピューティングデバイスによってより多くの電力が節約される。
【００３３】
図４ａおよび４ｂはフローダイアグラムの２つの実施形態を提供し、これらを使用して、あるコンピューティングデバイスが他のフローと比較してあるフローを使用することによって節約することができる電力を明示する。図４ａのフローダイアグラムを考察する。フローｆＡＢは、それが最初のフローであるので２のウェイクアップを与え、したがって、フレーム２０２内にそれより前のフローがないので前のフローとコンピューティングデバイスを共有することはできない。２つの連続したフローが共通のコンピューティングデバイスＡを共有すると、結果として、コンピューティングデバイスのための１のウェイクアップが生じる。図４ａのフローダイアグラムでは、フローｆＡＢはフローｆＢＣの直前で発生する。これらの２つの連続したフローはコンピューティングデバイスＢを共有し、したがって、フローｆＢＣは１つのウェイクアップを有する。フローｆＢＣはフローｆＣＤの直前で発生し、これらの２つの連続したフローはコンピューティングデバイスＣを共有し、したがって、フローｆＣＤは１つのウェイクアップを有する。図４ａのウェイクアップの総数は、したがって２＋１＋１＝４である。
【００３４】
図４ｂのフローダイアグラムでは、フローｆＡＢは、それが最初のフローであり、前のフローとコンピューティングデバイスを共有することができないので（図４ｂに示すフレーム２０２内でフローｆＡＢより前のフローがないため）、２つのウェイクアップを与える。したがって、両方のコンピューティングデバイスＡおよびＢがウェイクアップされなければならない。フローｆＣＤは、それが前のフローｆＡＢといかなるデバイスをも共有しないので、２つのウェイクアップを与える。したがって、両方のコンピューティングデバイスＣおよびＤがウェイクアップされなければならない。したがって、コンピューティングデバイスＢは、フローｆＡＢの後でスリープに戻るようになり、コンピューティングデバイスＢが３番目のフローｆＢＣに含まれることを考慮すると、次いでコンピューティングデバイスＢは、フローｆＢＣのための３番目のチャネル割り振り期間のために再度ウェイクアップする必要がある。フローｆＢＣはフローｆＣＤに隣接しており、これらの２つのフローはコンピューティングデバイスＣを共有し、したがって、フローｆＣＤは１つのウェイクアップを有する。図４ｂのウェイクアップの総数は、したがって２＋２＋１＝５である。
【００３５】
上記の開示に基づいて、図４ａのフローダイアグラムは合計４つのウェイクアップを有するが、図４ｂのフローダイアグラムは合計５つのウェイクアップを有する。図４ａのフローダイアグラムおよび図４ｂのフローダイアグラムは、フローの順序のみが異なる。図３に示すようにネットワーク１０１内のコンピューティングデバイス１０６は、図４ａのフローダイアグラムに従うときよりも、図４ｂのフローダイアグラムに従うときに、ウェイクアップの数がより大きいために、平均してより高い電力消費量となる。比較的小規模なネットワーク１０１内でも多数のフレーム２０２が発生することを考慮すると、フレーム２０２の多数の内でウェイクアップの数を減らすことは、それにより結果として、ネットワーク１０１内のコンピューティングデバイスにとって著しい省電力となる。
【００３６】
頂点／エッジグラフを使用した縮小ディグリーサーチ  
上述のように、電力管理問題の一態様を、図３のフロートポロジグラフ３１０内のフローの望ましい順序を導出することと見なすことができる。本開示は、図７に示すような「縮小ディグリーサーチ」メカニズムを説明し、このメカニズムは多くの場合、図３のフロートポロジグラフ３１０内で改善されたフロー順序に適用される結果を導出して、各フレーム中にウェイクアップしなければならないコンピューティングデバイス１０５の総数を減らすことができる。縮小ディグリーサーチメカニズムをこのとき説明し、図７の縮小ディグリーサーチメカニズムと図３のフロートポロジグラフの間の関係を以下で説明する。
【００３７】
頂点のディグリーは、その頂点で終了する頂点の数を記述する。縮小ディグリーサーチメカニズムは、本開示で説明するように、順序をエッジおよび頂点に基づいて導出するグラフの範囲内で動作する。「縮小ディグリーサーチ」メカニズムの一実施形態は、ネットワーク１０１内のコンピューティングデバイス１０５のすべてのためのウェイクアップの総数を減らすことによって、ネットワーク１０１内で動作中であるコンピューティングデバイスの多数のための電力を節約するために使用することができるエッジの順序を導出することができ、この実施形態をこのとき説明する。図７の「縮小ディグリーサーチ」メカニズムは、頂点／エッジグラフＧ１を確立することを含み、このグラフの実施例を、図５および６に関して、以下のルールに従って説明する。
【００３８】
１．図１のネットワークコンピューティング環境１００内の各コンピューティングデバイス１０６は、頂点／エッジグラフＧ１内で頂点Ｖｍ５０４と示され、ただし、ｍは各個々のコンピューティングデバイス１０６を頂点５０４の整数値に基づいて明確に識別する整数を表す。したがって、参照文字「Ｖｍ」は、図５および６内の対応するコンピューティングデバイスのためのノード内に示される。図５および６では、頂点Ｖｍの数は、対応するデバイス１０６に適用される整数によって表される。
【００３９】
２．図３のフロートポロジグラフにおいてネットワーク１０１内でこれらの２つの対応する２つのコンピューティングデバイス１０６の間にフローがある場合にのみ、２つの頂点５０４の間のエッジｅｎ（ただし、ｎは図５および６に示す整数として指定される）を提供する。各エッジｅｎは２つの頂点の間に渡り、他のエッジに対して識別することができる。頂点の各ペアの間にエッジがある必要はない。
【００４０】
頂点／エッジグラフＧ１（図５および６に示す実施例）は、これらのルールを適用した結果として生じる。頂点／エッジグラフＧ１内の各頂点はコンピューティングデバイスに対応し、頂点／エッジグラフＧ１内の各エッジは２つのコンピューティングデバイスの間のフローに対応する。Ｍ個の頂点５０４およびＮ個のエッジｅｎが頂点／エッジグラフ内にあると仮定する。電源管理問題を、頂点／エッジグラフＧ１内でエッジｅｎをスケジューリングして、最大数の連続するエッジ（好ましくは、２つ毎の連続するエッジ）が共通の頂点５０４を共有するようにすることに、単純化することができる。
【００４１】
少なくとも１つの新しいコンピューティングデバイス１０６は、新しいフローがサービスされるたびにウェイクアップする必要があるので、ウェイクアップの縮小数は、Ｎ＋Ｄによって下限が付けられ、Ｄは頂点／エッジグラフＧ１内のパッチの数を示す（パッチ内のすべての頂点は互いにエッジにより接続される）。例えば、図６の頂点／エッジグラフは、第１のパッチ６０２ａ内の３つの相互接続された頂点５０４、および、第２のパッチ６０２ｂ内の２つの相互接続された頂点を含む。各「パッチ」を、相互接続された頂点の島として視覚化することができ、この島において、すべての頂点は少なくとも１つのエッジによってパッチ内の互いの頂点に直接的または間接的に相互接続される。あるパッチ内に含まれた頂点は、エッジによって、別のパッチ内に含まれた頂点に接続されない。例えば、パッチ６０２ａ内の頂点をパッチ６０２ｂ内のいかなる頂点にも（直接的にも間接的にも）接続させることはできず、これは、これらの頂点が異なるパッチ内にあるからである。頂点／エッジグラフＧ１が連結グラフであり、図５のように、エッジによって接続されるこれらの頂点がただ１つのパッチ内で維持されるとき、ウェイクアップの縮小数の下限はＮ＋１である。２つのパッチを有する図６では、ウェイクアップの縮小数の下限はＮ＋２である。グラフ理論を使用して、ネットワーク１０１内のコンピューティングデバイスのための縮小ウェイクアップ回数のための下限および上限を、知られているアルゴリズムであるハミルトンパスを使用して決定することができる。
【００４２】
本明細書で説明する「縮小ディグリーサーチ」メカニズムは、各連続するフローのペアが共通のコンピューティングデバイスを共有するようになるフローの順番を発見しようと試みる。修正済頂点／エッジグラフが連結グラフではなく、図６に関して説明したように、頂点のあるものがある他のエッジに直接的にも間接的にも接続されないときなど、この試みは必ずしも達成可能ではない。所与の頂点／エッジグラフでは、ディグリーは上述の下限を達成することはできない。現在のメカニズムによって提供されるような、最適なディグリーの網羅的なサーチは、Ｎ階乗（Ｎ！）のような、頂点／エッジグラフ内のエッジの潜在的順序を発見する複雑性を有し、これは過剰なコンピューティングリソース、コンピューティング労力および処理時間を要する。「縮小ディグリーサーチ」メカニズムはコンピューティング労力および処理時間を多くの場合に減らし、これは、図１内で説明したコンピューティングデバイスのバッテリ動作および無線の実施態様に関して特に説明したように、ネットワーク１０１など、電源管理アプリケーションにおいて特に著しい。
【００４３】
縮小ディグリーサーチアルゴリズムの一実施形態を、表１に関して説明する。縮小ディグリーサーチアルゴリズムをさらに本開示内で、図７に関してより詳細に説明する。
【００４４】
【表１】
0004681308.tif 000002
【００４５】
表１の縮小ディグリーサーチ技術は、コンピューティングデバイスの間のフローの望ましい順序に相関させることができるエッジの順序を作成する、図７の流れ図の一実施形態に関して多少拡張される。表１のステップ２の脚注１に示すように、「最低ディグリーを有する、エッジの関連付けられた頂点の両方」という句は、最初に、すべての候補頂点の中で、最小ディグリーを有する（０より大きいディグリーを有する）ものを発見することを意味する。最小ディグリーを有する各候補頂点について、その隣の頂点が最小ディグリーを有するものを発見する。最後に、最小ディグリーを有する頂点のペアを選択する。このようなコンピューティングデバイスは、コンピューティングデバイスのウェイクアップの縮小数を体験し、それにより、電源管理技術を使用して動作するとして見なすことができる。図７の縮小ディグリーサーチ技術７００は、図５および６（および、エッジがエッジ番号によるのではなくそれらの隣接頂点によって示される、図８、９および１０）のように、代表の頂点／エッジグラフＧ１を生成および解析することに依拠し、これにおいて、それらの関連付けられた各頂点の間のエッジの選択を各タイムスロットについて決定することができる。オペレーション７０４で、修正済頂点／エッジグラフＧが頂点／エッジグラフＧ１から導出される（および、最初にそのコピーにすることができる）。頂点／エッジグラフＧ１および修正済頂点／エッジグラフＧは、図１に関して説明したように、ネットワーク１０１内の複数のコンピューティングデバイスの間で通信するデータ信号１０８にグラフィカルに対応する、相互接続する関連付けられた頂点を有するエッジを含む。エッジを修正済グラフＧから、縮小ディグリーサーチ技術を使用して、計算的に除去することができる。エッジが除去される順番は、図３のフロートポロジグラフ３１０内のフローの選択された順序に対応することに留意されたい。頂点／エッジグラフＧの考察を図５および６に関して論じ、値ｊは各エッジｅｊのエッジ番号変数を識別し、表１に関して説明するように、エッジ番号変数ｊは修正済頂点／エッジグラフＧ内で最初に０に初期化される。オペレーション７０９または７１６で、エッジ番号変数が増分されて、縮小ディグリーサーチ技術中に頂点／エッジグラフＧ１内で連続するエッジｅｊを通じて進行される。
【００４６】
縮小ディグリーサーチ技術７００は、図５または図６の頂点／エッジグラフＧ１から得られる修正済頂点／エッジグラフＧを使用して、順序内で頂点を共有する連続するエッジの数を増す順序でエッジを除去する。オペレーション７０６で、その２つの関連付けられた頂点が同じ縮小ディグリー（例えば、最小ディグリーである可能性がある）を共有するいずれかのエッジが選択される。縮小ディグリーは、ａ）；修正済頂点／エッジグラフ内で最小ディグリーを有するすべての頂点を発見すること、および次いで、ｂ）；ａ）で発見された頂点を使用して、ａ）からの頂点の少なくとも１つを有し、最小の和を有する関連付けられた頂点を有するエッジを選択することによって、発見される。複数のエッジがｂ）のクエリを満たす場合、ある他の基準によって１つをランダムに選択することができる。縮小ディグリーは、ａ）；修正済頂点／エッジグラフＧ全体内で最小ディグリーを有する頂点のすべてを発見すること、および、ｂ）；ａ）で発見された頂点を使用して、ａ）からの頂点の少なくとも１つを有し、最小の和を有する関連付けられた頂点を有するエッジを選択することによって決定される。複数のエッジがｂ）のクエリを満たす場合、１つをランダムに選択するか、あるいはある他の基準を使用することができる。
【００４７】
例えば、図５に示す頂点／エッジグラフでは、エッジｅ２のみが、２のディグリー（図５におけるいかなる頂点についても最低のディグリーである）を有するその関連付けられた頂点Ｖ１およびＶ４の両方を有する。したがって、図７の縮小ディグリーサーチ技術を、図５に示すような修正済頂点／エッジグラフＧに適用することによって、その関連付けられた頂点が共に同じ最小値を共有するであろう、選択されたエッジは、ｅ２となる。したがって、エッジｅ２は、グラフＧから除去される最初のエッジである。
【００４８】
縮小（例えば、最小）ディグリーを有する候補頂点は、修正済頂点／エッジグラフＧ内で、頂点に接触するエッジｅｊの縮小数を検討することによって決定される。したがって、より少数のエッジと接触する頂点は、頂点／エッジグラフの縮小ディグリーを有することに対応する。本開示は、同じ縮小ディグリーを有する関連付けられた頂点を有するエッジを、表１のステップ２に基づいて発見するための技術を提供する。一般に、その関連付けられた頂点がより高いディグリーを有するエッジよりも早く、その関連付けられた頂点がより低いディグリーを有するエッジを除去することによって、以前に除去されたエッジの関連付けられた頂点を各パッチから切り離すために比較的少数のエッジを除去すればよい。したがって、エッジをパッチから除去するための効率的な技術が提供される。
【００４９】
縮小ディグリーサーチ技術の判断７０８は、頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝内で、エッジの現在のセット｛ｅ０，ｅ１，．．．，ｅｊ｝を検討して、７０６で選択されたエッジにいずれかの隣のエッジがあるかどうかを判断する。本開示内で、「隣のもの」という用語は、頂点にもエッジにも適用することができる。第１の頂点および第２の頂点に接続するエッジがある場合にのみ、第１の頂点は第２の頂点の隣のものである。第１のエッジおよび第２のエッジが同じ頂点に接触する場合にのみ、第１のエッジは第２のエッジの隣のものである。
【００５０】
関連付けられた各頂点の１つに関連付けられるいかなる各コンピューティングデバイスも、エッジがアウェイクである各タイムスロット中にアウェイクでなければならないので、エッジは無方向性であると見なされる。したがって、あるエッジの隣のエッジには、いずれかの所与のエッジへの両方の関連付けられた頂点に接触するエッジが含まれる。
【００５１】
判断７０８に対する答えがＮｏであり、選択されたエッジに接続される隣のエッジがさらにないことを示す場合、縮小ディグリーサーチ技術は判断７０９に進む。７０９で、エッジ（ｅｊ）を表現するエッジ番号変数（ｊ）が増分され、縮小ディグリーサーチ技術は次のエッジへ進む。
【００５２】
７０９の後に続いて、縮小ディグリーサーチメカニズムは判断７１０に進み、いずれかのさらなるエッジ（例えば、図６に関して説明したような６０２ａおよび６０２ｂ）があるかどうかを、
【００５３】
【数１】
0004681308.tif 000003
【００５４】
かどうかを検討することによって検討する。判断７１０に対する答えがＮｏである場合、縮小ディグリーサーチ技術７００は終了し、これは、すべてのエッジが、頂点／エッジグラフＧ１内に含まれたすべてのパッチについて検討されたからである。判断７１０に対する答えがＹｅｓである場合、縮小ディグリーサーチ技術はオペレーション７１１に進み、さらなるパッチのための他のエッジへの処理を継続する。オペレーション７１１で、修正済頂点／エッジグラフは、最後に選択されたエッジが除去されることによって、再構成される。エッジが除去される順序は、図４ａおよび４ｂのように、フレーム２０２内のフローの順番に対応する。７１１の後に続いて、縮小ディグリーサーチ技術７００は７０６に戻り、上述のように新しいエッジを選択し、新しいパッチ内でさらなる候補頂点を評価する。
【００５５】
上述のような判断７０８に対する答えが代わりにＹｅｓである場合、現在の候補頂点が位置するパッチ内にさらなるエッジがある。次いで、これらのエッジが除去される順番が決定される。縮小ディグリーサーチ技術７００はオペレーション７１２に進み、（７０６から）選択されたエッジｅｊの隣のエッジが検討されて、その関連付けられた頂点が、エッジｅｊの隣のものであるいずれかのエッジの最小ディグリーを有する、１つの隣のエッジｅｊ＋１が選択される。多数の実施形態では、オペレーション７１２は、エッジｅｊの隣のエッジｅｊ＋１を選択して、２つの関連付けられた頂点が、選択されたエッジの隣のものである他のいずれかのエッジの最低ディグリー（例えば、多くの場合、最小ディグリー）を有するように、動作する。
【００５６】
オペレーション７１２の後に続いて、縮小ディグリーサーチ技術はオペレーション７１６に進み、現在のエッジが除去され、エッジ番号変数（ｊ）が増分される。現在のエッジを除去し、エッジ番号変数を増分する結果は、パッチ内で連続する隣のエッジを通じて進むことであり、元のエッジｅｊは頂点／エッジグラフから除去される。エッジｅｊがグラフから除去される順序は、各データ信号１０８（図１に関して上述）に関連付けられるコンピューティングデバイス１０６の選択されたペアが、そのデータ信号を送信するためにネットワークのコントロールを提供される順序に対応する。
【００５７】
オペレーション７１６で、エッジを頂点／エッジグラフから除去することによって、このエッジ、および、もはやエッジによってパッチ内の別の頂点に接続されないいかなる頂点も、もはやパッチの一部としてみなされない。隣のエッジ（次に選択される候補エッジになるもの）、および、１つまたは複数のエッジを介して隣のエッジに接続するいずれかのさらなる頂点（および、これらの相互接続するエッジ）は、同じパッチの残りを形成するようになる。オペレーション７１６の後に続いて、除去されたエッジを介して候補頂点に接続された頂点は、新しい候補頂点となる。７１６の後に続いて、縮小ディグリーサーチ技術は判断７０８に戻り、グラフ内でいずれかのさらなるエッジが残っているかどうかが判断される。
【００５８】
判断７０８ならびにオペレーション７１２および７１６は、縮小ディグリーサーチ技術内でループを形成し、このループは、判断７０８に対する応答がＮｏになるまで継続され、Ｎｏになる時点で、すべてのエッジが頂点／エッジグラフＧ内のパッチから除去されている。図７に関して説明した縮小ディグリーサーチ技術７００はそれにより、別の隣のエッジがないような時間になるまで、判断７０８ならびにオペレーション７１２および７１６によって示されたループ内に残るようになる。この時点で、パッチ内にさらなるエッジはなく、縮小ディグリーサーチ技術７００は、新しいパッチを探し出すため、または代替としてルーチンを終了させるために、判断７０８、オペレーション７０９、判断７１０、オペレーション７１１およびオペレーション７０６へと上述のように進む。
【００５９】
各エッジがグラフＧから、図７の縮小ディグリーサーチメカニズムによって決定されたように除去される順序は、フローが、図３に関して説明したようにフレーム内で配列される順序に対応する。したがって、例えば、第１のフローは、グラフＧから除去される最初のエッジに対応するフローとなる。縮小ディグリーサーチメカニズムを使用して、図３内の複数のコンピューティングデバイス３１２の間のフローの順序を決定することで、図３、４ａおよび４ｂに関連して説明したようにコンピューティングデバイスのためのウェイクアップの縮小数を提供することができる、効果的なフローの順番を提供することができる。
【００６０】
縮小ディグリーサーチ技術の実施例  
図５および６の頂点／エッジグラフＧ１に関して説明した縮小ディグリーサーチ技術をさらに説明するため、図８、９および１０を参照して、図７の縮小ディグリーサーチメカニズムを適用することができる３つの頂点／エッジグラフの実施例をさらに提供する。本開示における図８、９および１０内で、各エッジは、関連付けられた頂点の参照文字によって定義される。例えば、頂点Ａと頂点Ｂの間に走るエッジはエッジＡＢと記述される。図５および６に示すようなエッジのためのもう１つの名称は、ある順序（例えば、ｅ１，ｅ２，．．．，ｅｊ）のエッジの数値セットを示す。表１に示す各ステップ（１から５）をこのとき、各図８、９および１０の頂点／エッジグラフ内で説明する。
【００６１】
最初の実施例は、図８に示す頂点／エッジグラフＧ１に関する。表１のステップ１では、図８の頂点／エッジグラフＧ１は修正済頂点／エッジグラフＧとして割り当てられ、エッジ番号変数ｊを０に割り当てるものとする。
【００６２】
表１の第２のステップでは、エッジをｅ０として修正済頂点／エッジグラフＧ内で選択し、２つの関連付けられた頂点の両方が、いずれかのエッジの最小ディグリーを有するようにする。関連付けられた頂点の両方が最小ディグリーを有することを保証するため、最初に、ディグリーが修正済頂点／エッジグラフＧ内のすべての頂点（頂点ＡからＬ）の間で０より大きい最低ディグリーを有する、選択された頂点を発見する。次いで、各選択された頂点についてのとなりの頂点のすべてについて、最小ディグリーを有する隣の頂点を発見する。最後に、結合して最小合計ディグリーを生じる、１つの選択された頂点および１つの隣の頂点を含むペアを選択する。修正済頂点／エッジグラフＧにおいてこれを検討すると、頂点Ａ、頂点Ｃ、頂点Ｆおよび頂点Ｇはすべて１のディグリー（なお０より大きい最小の潜在的ディグリー）を有する。頂点Ｍは０のディグリーを有するが、この頂点は検討されない。
【００６３】
表１のステップ２の後に続いて、頂点Ａ、頂点Ｃ、頂点Ｆおよび頂点Ｇの各々の隣の頂点が検討される。頂点Ａは、２のディグリーを有する１つの隣の頂点Ｂのみを有する。頂点Ｃのただ１つの隣のものは、３のディグリーを有する頂点Ｄである。頂点Ｆのただ１つの隣のものは、３のディグリーを有する頂点Ｅである。頂点Ｇのただ１つの隣のものは、３のディグリーを有する頂点Ｅである。したがって、頂点Ａ、頂点Ｃ、頂点Ｆおよび頂点Ｇはそれぞれ１のディグリーを有するが、頂点Ａは、２の最小ディグリーを有する隣の頂点Ｂを有する。したがって、エッジｅ０はＡＢとして割り当てられる。
【００６４】
表１のステップ３で、修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝内の現在のエッジのセットｅ０，ｅ１，．．．，ｅｊでは、エッジ
【００６５】
【数２】
0004681308.tif 000004
【００６６】
の隣のエッジがない場合、エッジ番号変数が増分されて（ｊを増分）次のエッジに進み、縮小ディグリーサーチ技術は表１のステップ５に続く。そうでない場合、エッジｅｊの隣のエッジの中で、あるエッジがｅｊ＋１として、２つの関連付けられた頂点が両方とも最小ディグリーを有するように選択され、エッジ番号変数が増分されて（ｊを増分）次のエッジに進む。したがって、修正済頂点／エッジグラフＧ＝Ｇ１−ｅ０では、エッジｅ０＝ＡＢはただ１つの隣のエッジＢＤしか有しておらず、そのためエッジｅ１がエッジＢＤとして選択される。次いで、エッジ番号変数は１に設定される（ｊ＝１）。
【００６７】
残りの修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ｝では、エッジｅ１＝ＢＤの隣のエッジはエッジＣＤおよびエッジＤＥである。これらの２つのエッジのうち１つがｅ２として選択され、選択されたものの関連付けられた２つの頂点が最小ディグリーを有するようにされる。エッジＣＤおよびＤＥは共通の頂点Ｄを共有し、そのため頂点Ｃおよび頂点Ｅのディグリーが比較される。頂点Ｃのディグリーは１であるが、頂点Ｅのディグリーは３である。したがって、エッジｅ２＝ＣＤが選択される。次いで、エッジ番号変数が２に増分される（ｊ＝２）。
【００６８】
残りの修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ｝では、エッジｅ２＝ＣＤのただ１つの隣のエッジはエッジＤＥである。エッジＤＥがエッジｅ３として選択される。エッジ番号変数が３に増分される（ｊ＝３）。残りの修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ｝を検討すると、エッジｅ３＝ＤＥの隣のエッジはエッジＥＦおよびＥＧである。これらのうち１つがエッジｅ４として選択され、選択されたものの関連付けられた２つの頂点がこれらの２つのエッジの間の最小ディグリーを有するようにされる。エッジＥＦおよびエッジＥＧは共通の頂点Ｅを共有し、そのため頂点Ｆのディグリーが頂点Ｇと比較されることに留意されたい。両方の頂点Ｆおよび頂点Ｇは同じ１のディグリーを有するので、エッジＥＦが任意にエッジｅ４として選択される。エッジ番号変数は４に増分される（ｊ＝４）。
【００６９】
修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ｝では、エッジｅ４＝ＥＦのただ１つの隣のエッジはエッジＥＧである。そのため、エッジＥＧがエッジｅ５として選択され、これは、図８に示す上方のパッチ内の最後のエッジを表現する。エッジ番号変数は５に増分される（ｊ＝５）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ｝では、エッジＥＧの隣のエッジはない。エッジ番号変数はさらに６に増分され（ｊ＝６）、表１のステップ３は表１のステップ４に続く。さらにエッジはなく、したがって、縮小ディグリーサーチアルゴリズムは表１のステップ４のように進行することができない。  
表１のステップ５で、
【００７０】
【数３】
0004681308.tif 000005
【００７１】
である場合、修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝とし、表１のステップ２に戻り、そうでない場合は停止する。Ｅがすべてのエッジのセットを示す場合、
【００７２】
【数４】
0004681308.tif 000006
【００７３】
である。したがって、縮小ディグリーサーチ技術は表１のステップ２に戻り、再度、図８の左下のパス内のエッジを検討する。
【００７４】
図８に適用されたような縮小ディグリーサーチ技術を使用する表１のステップ２では、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ｝＝｛ＨＪ，ＨＫ，ＪＫ，ＫＬ，ＪＬ｝である。エッジｅ６は、選択されたエッジの２つの関連付けられた頂点が最小ディグリーを有するように選択される。「選択されたエッジの２つの関連付けられた頂点が最小ディグリーを有する」の解釈にしたがって、最初に、すべての候補頂点｛Ｈ，Ｊ，Ｋ，Ｌ｝の中で最小ディグリーを有する頂点を発見し、次いでこれらの選択された頂点の各々について、最小ディグリーを有する隣の頂点が発見される。頂点ＨおよびＬはそれぞれ２のディグリーを有するが、頂点ＪおよびＫはそれぞれ３のディグリーを有する。したがって、候補頂点は｛Ｈ，Ｌ｝である。頂点Ｈでは、その隣のものは頂点Ｋ（ディグリー＝３）および頂点Ｊ（ディグリー＝３）である。最小ディグリーを有する隣のものは、頂点Ｋとして任意に選択される。頂点Ｌは、隣の頂点Ｋ（ディグリー＝３を有する）および頂点Ｊ（ディグリー＝３）を有する。そのため、頂点Ｋが、最小ディグリーを有するその隣のものとして任意に選択される。頂点Ｈおよび頂点Ｌは同じディグリーを有し、さらに、それらの隣のものの最小ディグリーも同じであるので、エッジＨＫは、修正済頂点／エッジグラフ内で任意にエッジｅ６として選択される。  
表１のステップ３に続くと、エッジｅ６の隣のエッジは
【００７５】
【数５】
0004681308.tif 000007
【００７６】
であり、そのため１つのエッジがエッジセット｛ＨＪ，ＫＪ，ＫＬ｝の中でエッジｅ７として選択される。選択されたエッジの２つの関連付けられた頂点は最小ディグリーを有するべきであるという基準によれば、このようなものはエッジＨＪ（頂点Ｈ＝１のディグリーおよび頂点Ｊ＝３のディグリー）によって満たされる。そのため、エッジＨＪがエッジｅ７として選択され、エッジ番号変数が７に設定される（ｊ＝７）。修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ，ＨＫ，ＨＪ｝では、エッジＨＪの隣のエッジはエッジＪＫおよびエッジＪＬである。類似の手順に従うことによって、次のエッジｅ８をエッジＪＫまたはエッジＪＬのいずれかとして選択することができる。エッジｅ８は任意にエッジＪＫとして選択され、エッジ番号変数は８に設定される（ｊ＝８）。修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ，ＨＫ，ＨＪ，ＪＫ｝では、エッジＪＫの隣のエッジはエッジＫＬおよびエッジＪＬである。
【００７７】
類似の手順に従うことによって、次のエッジｅ９はエッジＪＬまたはエッジＫＬとして選択される。エッジｅ９は任意にエッジＫＬとして選択され、エッジ番号変数は９に設定される（ｊ＝９）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ，ＨＫ，ＨＪ，ＪＫ，ＫＬ｝では、エッジＫＬの隣のエッジはエッジＪＬである。類似の手順に従うことによって、次のエッジｅ１０がエッジＪＬとして選択され、エッジ番号変数は１０に設定される（ｊ＝１０）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＣＤ，ＤＥ，ＥＦ，ＥＧ，ＨＫ，ＨＪ，ＪＫ，ＫＬ，ＪＬ｝では、エッジ番号変数を１１に設定する（ｊ＝１１）。エッジＪＬの隣のエッジは
【００７８】
【数６】
0004681308.tif 000008
【００７９】
であり、表１のステップ４によれば、進行することはできず、ステップ５に続く。  
表１のステップ５で、
【００８０】
【数７】
0004681308.tif 000009
【００８１】
である場合、修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝とし、ステップ２に戻り、そうでない場合は停止する。
【００８２】
【数８】
0004681308.tif 000010
【００８３】
であるため、縮小ディグリーサーチ技術は停止する。
【００８４】
フローの順番は、図８の修正済頂点／エッジグラフにおいて、エッジＡＢ、エッジＢＤ、エッジＣＤ、エッジＤＥ、エッジＥＦ、エッジＥＧ、エッジＨＫ、エッジＨＪ、エッジＪＫ、エッジＫＬおよびエッジＪＬに対応する。縮小ディグリーサーチ技術は、隣接するパッチの間で移行することが必要である場合を除いて、２つ毎の連続するエッジが共通の頂点を共有するので、下限を達成する縮小処理ソリューションを提供する。
【００８５】
縮小ディグリーサーチ技術の第２の実施例を図９に関して説明する。縮小ディグリーサーチ技術を、この頂点／エッジグラフＧ１についてステップ毎に説明する。表１のステップ１で、修正済頂点／エッジグラフＧは頂点エッジグラフＧ１の値に等しいものとし、エッジ番号変数は０に設定される（ｊ＝０）。
【００８６】
表１の第２のステップでは、あるエッジがｅ０として修正済頂点／エッジグラフＧ内で選択され、２つの関連付けられた頂点の両方が最小ディグリーを有するようにされる。修正済頂点／エッジグラフＧでは、頂点Ａは１のディグリーを有する。加えて、頂点Ａはただ１つの隣の頂点Ｂを有する。そのため、エッジｅ０＝ＡＢを選択する。頂点／エッジグラフＧ１では、頂点Ｃのディグリーは２であり、頂点Ｄのディグリーは２であるが（そのため、エッジＣＤの２つの頂点のための合計ディグリーは４であり、１＋４＝５であるエッジＡＢの合計ディグリーより小さい）、しかし、基準にしたがって、エッジＣＤではなくエッジＡＢをエッジｅ０として選択し、これは、頂点Ａがいかなる頂点もの最小ディグリー（１）を有するからである。
【００８７】
表１のステップ３は以下のように適用される。修正済頂点／エッジグラフＧ＝Ｇ１−ｅ０では、エッジｅ０＝ＡＢは４つの隣のエッジ｛ＢＣ，ＢＤ，ＢＥ，ＢＦ｝を有する。これらの隣のエッジのうち１つがエッジｅ１として選択され、選択されたものの２つの関連付けられた頂点のディグリーが最小であるようにされる。すべての４つのエッジは共通の頂点Ｂを共有し、そのため、頂点Ｃ、頂点Ｄ、頂点Ｅおよび頂点Ｆのディグリーのみを比較する必要がある。それらのディグリーはすべて２に等しいので、そのため任意にエッジｅ１＝ＢＤを選択する。エッジ番号変数は１に設定される（ｊ＝１）。修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ｝では、エッジｅ１＝ＢＤの隣のエッジは｛ＢＣ，ＢＥ，ＢＦ，ＤＣ｝であり、そのうちの１つがエッジｅ２として選択され、合計された頂点が結合して最小ディグリーになるようにされる。修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ｝では、エッジｅ２はエッジＤＣとして選択され、これは、頂点Ｄが最小ディグリー（１）を有するからである。エッジ番号変数は２に設定される（ｊ＝２）。
【００８８】
修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＤＣ｝では、エッジｅ２＝ＤＣのただ１つの隣のエッジはエッジＢＣである。そのため、エッジｅ３＝ＢＣを選択する。エッジ番号変数は３に設定される（ｊ＝３）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＤＣ，ＢＣ｝では、エッジｅ３＝ＢＣの隣のエッジは｛ＢＥ，ＢＦ｝であり、そのため、これらのエッジのうち１つがエッジｅ４として選択される。頂点Ｅは頂点Ｆと同じディグリーを有するので、エッジｅ４は任意にエッジＢＥとして選択される。エッジ番号変数は４に設定される（ｊ＝４）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＤＣ，ＢＣ，ＢＥ｝では、エッジｅ４＝ＢＥの隣のエッジは｛ＢＦ，ＥＦ｝である。エッジＢＦはエッジＥＦと共通の頂点Ｆを共有するので、頂点Ｂおよび頂点Ｅのディグリーを比較する。これらの２つの頂点は同じディグリーを有する。そのため、エッジｅ５＝ＢＦを任意に選択する。エッジ番号変数を５に設定する（ｊ＝５）。
【００８９】
このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＤＣ，ＢＣ，ＢＥ，ＢＦ｝では、エッジｅ５＝ＢＦのただ１つの隣のエッジはエッジＥＦであり、これがエッジｅ６として選択される。エッジ番号変数は６に設定される（ｊ＝６）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＡＢ，ＢＤ，ＤＣ，ＢＣ，ＢＥ，ＢＦ，ＥＦ｝では、エッジｅ６の隣のエッジは
【００９０】
【数９】
0004681308.tif 000011
【００９１】
である。表１のステップ４のように、さらに進行することができず、そのため、エッジ番号変数を７に設定し（ｊ＝７）、ステップ５に続く。
【００９２】
【数１０】
0004681308.tif 000012
【００９３】
である場合、修正済頂点／エッジグラフ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝とし、表１のステップ２に戻り、そうでない場合は縮小ディグリーサーチ技術を停止させる。
【００９４】
【数１１】
0004681308.tif 000013
【００９５】
であるため、縮小ディグリーサーチ技術は完了する。
【００９６】
第２の縮小ディグリーサーチの実施例から得られるフローの順序は、修正済頂点／エッジグラフＧ内で、エッジＡＢ、エッジＢＤ、エッジＤＣ、エッジＢＣ、エッジＢＥ、エッジＢＦおよびエッジＥＦに対応する。この頂点およびエッジの構成では、発見されたソリューションは最適であり、２つ毎の連続するエッジが共通の頂点を共有する（また、対応するフローは共通のコンピューティングデバイスを共有する）ので、下限を達成する。
【００９７】
第３の実施例では、縮小ディグリーサーチ技術を、図１０に示す頂点／エッジグラフＧ１について、ステップ毎に説明する。表１のステップ１のように、修正済頂点／エッジグラフＧ＝Ｇ１とし、エッジ番号変数を０に設定する（ｊ＝０）。
【００９８】
表１の第２のステップでは、修正済頂点／エッジグラフＧで、あるエッジがｅ０として修正済頂点／エッジグラフＧ内で選択され、そのエッジの関連付けられた頂点の両方が最小ディグリーを有するようにされる。具体的には、修正済頂点／エッジグラフＧでは、頂点Ｃ、頂点Ｅおよび頂点Ｇはそれぞれ１のディグリーを有する。加えて、頂点Ｃのただ１つの隣の頂点は、２のディグリーを有する頂点Ｂである。頂点Ｅのただ１つの隣の頂点は、２のディグリーを有する頂点Ｄである。頂点Ｇのただ１つの隣の頂点は、２のディグリーを有する頂点Ｆである。そのため、任意にエッジｅ０＝ＢＣを選択する。
【００９９】
修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝で、エッジｅ０，ｅ１，．．．，ｅｊの現在のセットについて、エッジｅｊの隣のエッジ＝
【０１００】
【数１２】
0004681308.tif 000014
【０１０１】
である場合、エッジ番号変数を増分して（ｊを増分）、次のエッジに進行し、表１のステップ５に行き、そうでない場合は、エッジｅｊの隣のエッジの中で、あるエッジをエッジｅｊ＋１として選択し、２つの関連付けられた頂点が最小ディグリー値を有するようにし、エッジ番号変数を増分して（ｊを増分）、次のエッジへ続く。修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ｝では、エッジｅ０＝ＢＣのただ１つの隣のものはエッジＡＢであり、そのため、エッジｅ１＝ＡＢを選択し、エッジ番号変数を１に設定する（ｊ＝１）。
【０１０２】
表１のステップ３に続く。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ，ＡＢ｝では、エッジｅ１＝ＡＢの隣のエッジは｛ＡＤ，ＡＦ｝である。そのため、タスクは、これらのうち１つをエッジｅ２として選択し、選択されたものの関連付けられた２つの頂点が最小ディグリーを有するようにすることである。これらの２つは共通の頂点Ａを共有するので、頂点Ｄおよび頂点Ｆのディグリーのみを比較する必要がある。頂点Ｄおよび頂点Ｆは同じディグリー（＝２）を有するので、任意にエッジｅ２＝ＡＤを選択し、エッジ番号変数を２に設定する（ｊ＝２）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ，ＡＢ，ＡＤ｝では、エッジｅ２＝ＡＤの隣のエッジは｛ＤＥ，ＡＦ｝である。これらのうち１つがエッジｅ２として選択され、選択されたものの関連付けられた２つの頂点が最小ディグリーを有するようにされる。最初に、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ，ＡＢ，ＡＤ｝では、頂点Ｄ、頂点Ｅおよび頂点Ａはすべて１のディグリーを有する。次に、頂点Ｄの隣のものは、１のディグリーを有する頂点Ｅであり、頂点Ｅの隣のものは、１のディグリーを有する頂点Ｄであり、頂点Ａの隣のものは、２のディグリーを有する頂点Ｆである。そのため、最後に、頂点Ｄおよび頂点Ｅが選択され（すなわち、エッジｅ３＝ＤＥ）、エッジ番号変数を３に設定する（ｊ＝３）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ，ＡＢ，ＡＤ，ＤＥ｝では、エッジｅ３＝ＤＥの隣のエッジは空である。そのため、エッジ番号変数を４に設定し（ｊ＝４）、表１のステップ５に行く。
【０１０３】
【数１３】
0004681308.tif 000015
【０１０４】
である場合、修正済頂点／エッジグラフ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝とし、表１のステップ２に戻り、そうでない場合は停止する。このとき、
【０１０５】
【数１４】
0004681308.tif 000016
【０１０６】
であるため、修正済頂点／エッジグラフ＝Ｇ１−｛ＢＣ，ＡＢ，ＡＤ，ＤＥ｝とし、表１のステップ２に戻る。修正済頂点／エッジグラフＧでは、あるエッジをｅ０として修正済頂点／エッジグラフＧ内で選択し、２つの関連付けられた頂点の両方が最小ディグリーを有するようにする。このとき、修正済頂点／エッジグラフＧでは、２つのエッジ｛ＡＦ，ＦＧ｝しか有していない。最初に、最小ディグリーを有する頂点はＡおよびＧであり、両方とも１のディグリーを有する。他方では、それらのただ１つの隣のものは頂点Ｆである。そのため、エッジｅ４＝ＡＦを任意に選択する。修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝で、現在のセットｅ０，ｅ１，．．．，ｅｊについて、エッジｅｊの隣のエッジ＝
【０１０７】
【数１５】
0004681308.tif 000017
【０１０８】
である場合、エッジ番号変数を増分して（ｊを増分）、次のエッジに進行し、表１のステップ５に続き、そうでない場合は、エッジｅｊの隣のエッジの中で、あるエッジをエッジｅｊ＋１として選択し、２つの関連付けられた頂点が最小ディグリーを有するようにし、エッジ番号変数を増分して（ｊを増分）、次のエッジへ続く。現在のエッジｅ４＝ＡＦであるので、ただ１つの隣のものはエッジＦＧであり、そのためエッジｅ５＝ＦＧを選択し、エッジ番号変数を５に設定する（ｊ＝５）。このとき、修正済頂点／エッジグラフＧ＝Ｇ１−｛ＢＣ，ＡＢ，ＡＤ，ＤＥ，ＡＦ，ＦＧ｝では、エッジｅ５＝ＦＧの隣のエッジは空である。そのため、エッジ番号変数を６に設定し（ｊ＝６）、表１のステップ５に行く。
【０１０９】
【数１６】
0004681308.tif 000018
【０１１０】
である場合、修正済頂点／エッジグラフＧ＝Ｇ１−｛ｅ０，ｅ１，．．．，ｅｊ｝とし、表１のステップ２に戻り、そうでない場合は停止する。このとき、
【０１１１】
【数１７】
0004681308.tif 000019
【０１１２】
であり、そのため停止する。第３の縮小ディグリーサーチの実施例から得られるフローの順序は、頂点／エッジダイアグラムＧ１内で、エッジＢＣ、エッジＡＢ、エッジＡＤ、エッジＤＥ、エッジＡＦおよびエッジＦＧに対応する。頂点／エッジグラフＧ１は連結グラフであるが、下限を達成するための方法はない。エッジＤＥからエッジＡＦまで、共通の頂点はなく、縮小ディグリーサーチ技術に従うことは、実際には表１のステップ５を３回進む。したがって、１つのパッチしかない頂点／エッジグラフの場合（例えば、連結グラフのため）でも、表１のステップ５を複数回ループする必要がある場合がある。
【０１１３】
コンピューティングデバイス  
図１に示すようなネットワーク１０１およびコンピューティングデバイス１０６をサポートして、図７の縮小ディグリーサーチ技術７００を実行することができる、コンピュータ環境１１００の一実施形態を、本開示内で図１１に関して説明する。図１に関連して説明したネットワーク１０１は、図１１に関連して説明するコンピュータ環境１１００の一実施形態を表す。図１１に例示したコンピューティング環境１１００は汎用コンピュータ環境であり、少なくとも１つの汎用コンピューティングデバイス１１０２を含む。コンピューティングデバイス１１０２には、例えば、１つまたは複数のスタンドアロンコンピュータ、ネットワークコンピュータ、メインフレームコンピュータ、ＰＤＡ、携帯電話、ポータブルハンドヘルド電話、無線デバイス、電子デバイス、マイクロコンピュータもしくはマイクロプロセッサ、または、メモリと結合してプロセッサを使用する他のいかなるコンピュータデバイスもが含まれる可能性がある。
【０１１４】
コンピューティングデバイス１１０２のコンポーネントには、それだけに限定されないが、１つまたは複数のプロセッサまたは処理クライアント１１０４（オプションで、暗号プロセッサおよび／またはコプロセッサを含む）、システムメモリ１１０６、および、様々なシステムコンポーネントを結合するシステムバス１１０８が含まれる可能性がある。コンピュータ環境１１００には、有線部分、および／または、一般にネットワークデバイスにより知られるような無線部分が含まれる可能性がある。
【０１１５】
コンピュータ１１０２はまた、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージ媒体も含むことができる。例として、図１１は、非リムーバブル、不揮発性の磁気媒体（図示せず）に対する読み書きを行うためのハードディスクドライブ１１１５、リムーバブル、不揮発性磁気ディスク１１２０（例えば「フロッピー（登録商標）ディスク」）に対する読み書きを行うための磁気ディスクドライブ１１１８、および、ＣＤ  ＲＯＭ、ＤＶＤ−ＲＯＭまたは他の光媒体など、リムーバブル、不揮発性の光ディスク１１２４に対する読み取りおよび／または書き込みを行うための光ディスクドライブ１１２２を例示する。ハードディスクドライブ１１１５、磁気ディスクドライブ１１１８および光ディスクドライブ１１２２はそれぞれシステムバス１１０８に、１つまたは複数のデータ媒体インターフェイス１１２７によって接続される。代替として、ハードディスクドライブ１１１５、磁気ディスクドライブ１１１８および光ディスクドライブ１１２２をシステムバス１１０８に、１つまたは複数のインターフェイス（図示せず）によって接続することができる。
【０１１６】
これらのディスクドライブおよびそれらの関連付けられたコンピュータ可読媒体は、コンピュータ１１０２用のコンピュータ可読命令、コントロールノードデータ構造、プログラムモジュールおよび他のデータの不揮発性ストレージを提供する。この実施例はハードディスクドライブ１１１５内のハードディスク、リムーバブル磁気ディスク１１２０および不揮発性光ディスク１１２４を例示するが、コンピュータによってアクセス可能であるデータを格納することができる他のタイプのコンピュータ可読媒体も、例示的コンピュータ環境１１００を実施するために利用することができ、これらの他のタイプのコンピュータ可読媒体は、磁気カセットもしくは他の磁気ストレージデバイス、フラッシュメモリカード、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ストレージ、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、電気的消去可能なプログラマブル読み取り専用メモリ（ＥＥＰＲＯＭ）などであることを理解されたい。
【０１１７】
いかなる数のプログラムモジュールも、ハードディスクドライブ１１１５内に含まれるハードディスク、磁気ディスク１１２０、不揮発性光ディスク１１２４、ＲＯＭ１１１２および／またはＲＡＭ１１１０上に格納することができ、これらのプログラムモジュールには、例として、ＯＳ１１２６、１つまたは複数のアプリケーションプログラム１１２８、他のプログラムモジュール１１３０およびプログラムデータ１１３２が含まれる。ＯＳ１１２６、１つまたは複数のアプリケーションプログラム１１２８、他のプログラムモジュール１１３０およびプログラムデータ１１３２の各々（またはそのある組み合わせ）は、図１に示すネットワーク１０１を介して使用されるアプリケーションプログラムの全部または一部を実装することができる。
【０１１８】
コンピュータ１１０２はネットワーク環境において、リモートコンピュータデバイス１１４８など、１つまたは複数のリモートコンピュータへの論理データ信号接続を使用して動作することができる。例として、リモートコンピュータデバイス１１４８は、パーソナルコンピュータ、ポータブルコンピュータ、サーバ、ルータ、ネットワークコンピュータ、ピアデバイスまたは他の共通ネットワークノード、ゲームコンソールなどにすることができる。リモートコンピュータデバイス１１４８は、本明細書でコンピュータ１１０２に関連して上述した要素および特徴の多数またはすべてを含むことができるポータブルコンピュータとして例示される。
【０１１９】
コンピュータ１１０２とリモートコンピュータデバイス１１４８の間の論理データ信号は、ローカルエリアネットワーク（ＬＡＮ）１１５０および一般的なワイドエリアネットワーク（ＷＡＮ）１１５２として示される。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネットおよびインターネットにおいて一般的である。
【０１２０】
コンピュータ環境１１００により例示されるものなど、ネットワーク環境では、コンピュータ１１０２に関連して示したプログラムモジュールまたはその一部を、リモートメモリストレージデバイス内に格納することができる。例として、リモートアプリケーションプログラム１１５８はリモートコンピュータ１１４８のメモリデバイス上に存在する。
【０１２１】
本明細書で説明した様々なモジュールおよび技術は、１つまたは複数のコンピュータまたは他のデバイスによって実行される、プログラムモジュールなど、コンピュータ実行可能命令の一般的なコンテキストに関係する可能性がある。一般に、プログラムモジュールには、ルーチン、プログラム、コントロールオブジェクト１１５０、コンポーネント、コントロールノードデータ構造１１５４などが含まれ、これらは特定のタスクを実行するか、あるいは特定の抽象データ型を実装する。しばしば、プログラムモジュールの機能を、様々な実施形態において望まれるように結合または分散させることができる。
【０１２２】
これらのモジュールおよび技術の一実施態様を、コンピュータ可読媒体のある形態上に格納するか、あるいはそれを介して送信することができる。コンピュータ可読媒体を、コンピュータによってアクセスすることができるいかなる使用可能な媒体にすることもできる。例として、限定ではなく、コンピュータ可読媒体は、「コンピュータストレージ媒体」および「通信媒体」を含むことができる。
【０１２３】
「コンピュータストレージ媒体」には、揮発性および不揮発性、リムーバブルおよび非リムーバブルの媒体が含まれ、これらの媒体は、コンピュータ可読命令、コントロールノードデータ構造、プログラムモジュールまたは他のデータなど、情報の格納のためのいずれかのプロセスまたは技術において実装される。コンピュータストレージ媒体には、それだけに限定されないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または、所望の情報を格納するために使用することができ、コンピュータによってアクセスすることができる他のいかなる媒体もが含まれる。
【０１２４】
「通信媒体」という用語には、それだけに限定されないが、搬送波または他の移送メカニズムなどの変調データ信号におけるコンピュータ可読命令、命令コード、コントロールノードデータ構造、プログラムモジュールまたは他のデータが含まれる。通信媒体にはまた、いかなる情報配信媒体もが含まれる。「変調データ信号」という用語は、それだけに限定されないがＴＤＭＡ技術を含む、信号に情報を符号化するような方法で、その特性の１つまたは複数が設定または変更されている信号を意味する。例として、限定ではなく、通信媒体には、有線ネットワークまたは直接有線データ信号などの有線媒体、ならびに、音響、ＲＦ、赤外線および他の無線媒体などの無線媒体が含まれる。上記のいずれの組み合わせも、コンピュータ可読媒体の範囲内に含まれる。
【０１２５】
上記の説明は、構造的な特徴および／または方法論的な動作に特有である言語を使用するが、添付の特許請求の範囲内で定義された本発明は、上述の特定の特徴または動作に限定されないことを理解されたい。むしろ、特定の特徴および動作は、本発明を実施する例示的形態として開示される。
【図面の簡単な説明】
【０１２６】
【図１】複数のコンピューティングデバイスを含むネットワークの一実施形態のブロック図である。
【図２】多数のコンピューティングデバイスの間で時分割多元接続（ＴＤＭＡ）データを送信するために使用されるものなど、サンプルフレームおよびそのコンポーネントの図である。
【図３】フローによって関連付けられた複数のコンピューティングデバイスを含む、フロートポロジのサンプルのグラフィカル表現の図である。
【図４ａ】図３のフロートポロジからのフローの順序を説明するフローダイアグラムである。
【図４ｂ】図３のフロートポロジからのフローの順序を説明するフローダイアグラムである。
【図５】すべての頂点が直接的または間接的に接続される単一のパッチ内に、頂点がすべて配列される、生成された頂点／エッジグラフの一実施例の図である。
【図６】頂点が２つのパッチ内に配列される、生成された頂点／エッジグラフの一実施例の図であり、各パッチ内ですべての頂点が直接的または間接的に接続される図である。
【図７】縮小ディグリーサーチメカニズムの一実施形態の図である。
【図８】図７の縮小ディグリーサーチメカニズムを適用することができるグラフの一実施例の図である。
【図９】図７の縮小ディグリーサーチメカニズムを適用することができるグラフの一実施例の図である。
【図１０】図７の縮小ディグリーサーチメカニズムを適用することができるグラフの一実施例の図である。
【図１１】縮小ディグリーサーチメカニズムを実行することができるような、コンピューティング環境の一実施形態のブロック図である。
【符号の説明】
【０１２７】
１０１  ネットワーク
１０５  ネットワークコーディネータデバイス（例えば、コンピューティングデバイス）
１０６  コンピューティングデバイス
２０２  フレーム
２０４  チャネル時間割り振り期間
２０６  チャネル時間割り振り
２０８  ビーコン
２１０  競合アクセス期間
２１２  管理チャネル時間割り振り
１１０４  処理装置
１１０６  システムメモリ
１１０８  システムバス
１１１０  ＲＡＭ
１１１２  ＲＯＭ
１１１４  ＢＩＯＳ
１１２６  オペレーティングシステム
１１２７  データ媒体インターフェイス
１１２８  アプリケーションプログラム
１１３０  他のプログラムモジュール
１１３２  プログラムデータ
１１３４  キーボード
１１３６  マウス
１１３８  他のデバイス
１１４０  Ｉ／Ｏインターフェイス
１１４２  コンピュータディスプレイ
１１４４  ビデオアダプタ
１１４６  プリンタ
１１４８  リモートコンピューティングデバイス
１１５０  ＬＡＮ
１１５２  インターネット
１１５４  ネットワークアダプタ
１１５６  モデム
１１５８  リモートアプリケーションプログラム
【図１】
0004681308.tif 000020
【図２】
0004681308.tif 000021
【図３】
0004681308.tif 000022
【図４ａ】
0004681308.tif 000023
【図４ｂ】
0004681308.tif 000024
【図５】
0004681308.tif 000025
【図６】
0004681308.tif 000026
【図７】
0004681308.tif 000027
【図８】
0004681308.tif 000028
【図９】
0004681308.tif 000029
【図１０】
0004681308.tif 000030
【図１１】
0004681308.tif 000031