(57)【特許請求の範囲】
【請求項１】
コントローラによって、ワイヤレスネットワークにおける分散型の記憶を管理する方法であって、
前記ワイヤレスネットワークが複数のデータ生成ノードを備え、各データ生成ノードがデータシンボルとパリティシンボルとを生成して記憶するように構成され、前記パリティシンボルは、各データ生成ノードが、他のデータ生成ノードに記憶され、前記他のデータ生成ノードからワイヤレスリンクを介して受信するデータシンボルに依存し、
前記パリティシンボルの生成のために、前記複数のデータ生成ノードの間でどのデータ生成ノードがどのデータ生成ノードにデータシンボルを送信するかのデータ生成ノード間の連結を示すアレイ符号が定義され、前記アレイ符号は、前記複数のデータ生成ノード中のデータ生成ノードの数と、前記ワイヤレスネットワークに記憶されている前記データシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存する複数の連結配列を構成することができ、
前記方法は、
前記コントローラが、前記データ生成ノード間のワイヤレスリンクに対するリンク品質推定の指示を受信することと、
リンク品質推定の前記指示を使用して、複数の可能な前記連結配列から好適な連結を有するある配列を選択することと、
選択された前記配列を示す指示を前記データ生成ノードに送信することと、
を備える、方法。
【請求項２】
選択された前記配列を示す指示を前記データ生成ノードに送信することが、各データ生成ノードに記憶される前記パリティシンボルの、他のデータ生成ノードに記憶される前記データシンボルに対する依存の指示を、当該各データ生成ノードに送信することを備える、請求項１に記載の方法。
【請求項３】
選択された前記配列を示す指示を前記データ生成ノードに送信することが、各データ生成ノードに記憶される前記データシンボルを、前記パリティシンボルの生成のためにどの他のデータ生成ノードに送信すべきかの指示を、当該各データ生成ノードに送信することを備える、請求項１に記載の方法。
【請求項４】
リンク品質推定の前記指示がノード間誤り確率である、請求項１に記載の方法。
【請求項５】
最高のノード間誤り確率を有するノードのペアを識別することと、前記識別されたノードのペアの間でデータシンボルが交換されない連結配列を選択することとをさらに備える、請求項４に記載の方法。
【請求項６】
部分グラフの集合を形成するために、前記複数のデータ生成ノードの集合から始めて、最高のノード間誤り確率を有するノードを、繰り返し、部分グラフの前記集合にグループ化することと、
部分グラフの前記集合の補グラフから前記ある配列を決定することと、
をさらに備える、請求項５に記載の方法。
【請求項７】
複数の可能な前記連結配列の各々に対する停止確率を決定することと、最低の停止確率を有する連結配列を選択することとを備える、請求項４に記載の方法。
【請求項８】
前記データ生成ノードに送信される配列が、記憶されている複数の可能な前記連結配列から選択される、請求項１に記載の方法。
【請求項９】
リンク品質推定の前記指示を使用して、複数の可能な前記連結配列から好適な連結を有するある配列を選択することが、前記連結配列を、前記ワイヤレスネットワーク中のデータ生成ノードの前記数、および、前記アレイ符号に要求される冗長性の指示から複数の可能な前記連結配列を決定することを備える、請求項１に記載の方法。
【請求項１０】
ワイヤレスネットワークのためのコントローラであって、
前記ワイヤレスネットワークが複数のデータ生成ノードを備え、各データ生成ノードがデータシンボルとパリティシンボルとを生成して記憶するように構成され、前記パリティシンボルは、各データ生成ノードが、他のデータ生成ノードに記憶され、前記他のデータ生成ノードからワイヤレスリンクを介して受信するデータシンボルに依存し、
前記パリティシンボルの生成のために、前記複数のデータ生成ノードの間でどのデータ生成ノードがどのデータ生成ノードにデータシンボルを送信するかのデータ生成ノード間の連結を示すアレイ符号が定義され、前記アレイ符号は、前記複数のデータ生成ノード中のデータ生成ノードの数と、前記ワイヤレスネットワークに記憶されている前記データシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存する複数の連結配列を構成することができ、
前記コントローラが、
前記データ生成ノード間のワイヤレスリンクに対するリンク品質推定の指示を受信するように構成されるワイヤレスインターフェースと、
リンク品質推定の前記指示を使用して、複数の可能な前記連結配列から好適な連結を有するある配列を選択するように構成されるプロセッサと、
を備え、
前記ワイヤレスインターフェースが、さらに、選択された前記配列を示す指示を前記データ生成ノードに送信するように構成される、
コントローラ。
【請求項１１】
複数の可能な前記連結配列に対する記憶装置をさらに備える、請求項１０に記載のコントローラ。
【請求項１２】
前記記憶装置が複数の前記連結配列を記憶するように構成され、
前記プロセッサが、さらに、複数の前記連結配列から前記ある配列を選択するように構成される、請求項１１に記載のコントローラ。
【請求項１３】
前記ワイヤレスインターフェースが、選択された前記配列を示す指示として、各データ生成ノードに記憶される前記パリティシンボルの、他のデータ生成ノードに記憶される前記データシンボルに対する依存の指示を、当該各データ生成ノードに送信するように構成される、請求項１０に記載のコントローラ。
【請求項１４】
前記ワイヤレスインターフェースが、選択された前記配列を示す指示として、各データ生成ノードに記憶される前記データシンボルを、前記パリティシンボルの生成のためにどの他のデータ生成ノードに送信すべきかの指示を、当該各データ生成ノードに送信するように構成される、請求項１０に記載のコントローラ。
【請求項１５】
リンク品質推定の前記指示がノード間誤り確率である、請求項１０に記載のコントローラ。
【請求項１６】
前記プロセッサが、さらに、最高のノード間誤り確率を有するノードのペアを識別し、前記識別されたノードのペアの間でデータシンボルが交換されない連結配列を選択するように構成される、請求項１５に記載のコントローラ。
【請求項１７】
前記プロセッサが、さらに、部分グラフの集合を形成するために、前記複数のデータ生成ノードの集合から始めて、最高のノード間誤り確率を有するノードを、繰り返し、部分グラフの前記集合にグループ化し、部分グラフの前記集合の補グラフから前記ある配列を決定するように構成される、請求項１６に記載のコントローラ。
【請求項１８】
前記プロセッサがさらに、複数の可能な前記の連結配列の各々に対する停止確率を決定し、最低の停止確率を有する連結配列を選択するように構成される、請求項１５に記載のコントローラ。
【請求項１９】
プロセッサ上で実行されると、前記プロセッサに、請求項１に記載の方法を実行させるプロセッサ実行可能命令を記憶する、コンピュータ可読の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書で説明される実施形態は、ワイヤレス・センサ・ネットワークなどの複数のデータ生成ノードを有するワイヤレスネットワークにおいて使用するための、アレイ符号の構成に関する。
【背景技術】
【０００２】
ワイヤレス・センサ・ネットワーク（ＷＳＮ：Wireless Sensor Network）には、ｅ−Ｈｅａｌｔｈ、スマートコミュニティ、およびスマートグリッドなどの領域に適用例がある。ＷＳＮは、自律的に動作して適用例固有のパラメータ（application specific parameters）を中央サーバに報告する、センサから構成される。これらのパラメータは、健康管理のシナリオでは患者のバイタルサイン（vital signs）であり、または「スマートシティ」の適用例では大気質の監視（air quality monitoring）であり得る。これらの適用例の多くは、センサが電池で駆動され確実に長い時間の期間にわたって動作することを必要とする。ネットワークにおけるエネルギー消費を減らすための１つの方法は、ネットワークのライフタイムを延ばすために無線インターフェースにデューティサイクルを設定することである。一方、いくつかの場合、ネットワーク中でのアグリゲーション（in-network aggregation）および記憶を利用することが可能であることがあり、このとき、センサデバイスは、ネットワークトラフィックを減らしてネットワークのライフタイムを延ばすために、生成されたデータをローカルに記憶する。この場合、データはイベントに基づく手法でシンクノードに転送され、このとき、トリガイベントとシンクからのクエリのいずれかが、センサデータをシンクノードに運ぶために使用される。この場合、生成されたセンサデータを確実に記憶して取り出すことが重要であり、このことは分散型の記憶手法を使用して達成されることが可能であり、このとき、あるノードに属するデータがいくつかのノードにわたって記憶され、ノードまたはリンクの障害の際にこれらのノードの部分集合を連結すること（connecting）によって取り出される。
【０００３】
冗長性をもたらし、ノードまたはリンクの障害から保護するために、ネットワークにおいてアレイ符号（array codes）が使用され得る。これは、ノードにデータシンボルを交換させて、他のノードからのデータに基づいてパリティシンボルを記憶することによって、達成される。しかしながら、これらのデータシンボルの交換が成功する場合にだけ、パリティシンボルは計算されることが可能である。  
以下では、添付の図面を参照して、単なる例として実施形態が説明される。
【図面の簡単な説明】
【０００４】
【図１】ある実施形態によるワイヤレスネットワークを示す図。
【図２】ある実施形態によるワイヤレスネットワークのためのコントローラを示す図。
【図２ａ】ある実施形態によるワイヤレスネットワークにおける分散型の記憶（distributed storage）を管理する方法を示す図。
【図３】アレイ符号の有向グラフの表現（directed graph representation）を示す図。
【図４】ある実施形態におけるノード間誤り確率（internode error probabilities）を示す図。
【図５ａ】図３に示されるグラフに対する同値類（equivalence classes）を示す図。
【図５ｂ】図３に示されるグラフに対する同値類を示す図。
【図５ｃ】図３に示されるグラフに対する同値類を示す図。
【図５ｄ】図３に示されるグラフに対する同値類を示す図。
【図５ｅ】図３に示されるグラフに対する同値類を示す図。
【図５ｆ】図３に示されるグラフに対する同値類を示す図。
【図６ａ】ｒ＝２個の障害を訂正することが可能なｎ＝４個のノードを有するアレイ符号の例示的なグラフを示す図。
【図６ｂ】図６ａに示されるノード連結の無向グラフを示す図。
【図７ａ】図６ｂに示されるグラフの同値類を示す図。
【図７ｂ】図６ｂに示されるグラフの同値類を示す図。
【図７ｃ】図６ｂに示されるグラフの同値類を示す図。
【図８】図６ｂに示されるグラフの補グラフ（complement graph）を示す図。
【図９】ある実施形態によるアレイ符号を構成する方法を示すフローチャート。
【図１０ａ】ｒ＝３個の消失（erasures）を訂正することが可能なｎ＝６個のノードを有するアレイ符号の例を示す図。
【図１０ｂ】図１０ａに示されるアレイ符号の連結グラフを示す図。
【図１１】例示的なネットワークに対するノード間誤り確率を示す図。
【図１２】図１０ｂに示される連結グラフの補グラフを示す図。
【図１３】ある実施形態に従って構成されるアレイ符号を示す図。
【図１４】性能の実施形態の評価を示す図。
【詳細な説明】
【０００５】
ある実施形態では、ワイヤレスネットワークにおける分散型の記憶を管理する方法が開示される。ワイヤレスネットワークは、複数のデータ生成ノードを備え、各データ生成ノードは、データシンボルとパリティシンボルとを生成して記憶するように構成される。パリティシンボルは、他のデータ生成ノードに記憶されているデータシンボルに依存する。方法は、データ生成ノード間のワイヤレスリンクに対するリンク品質推定（link quality estimates）の指示を受信することと、リンク品質推定の指示を使用して複数の可能な配列からアレイ符号（array code）のある配列（arrangement）を選択することと、アレイ符号は、複数のデータ生成ノード中のデータ生成ノードの数と、ワイヤレスネットワークに記憶されているデータシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存し、配列は、各データ生成ノードに対して、そのデータ生成ノードに記憶されているパリティシンボルの、他のデータ生成ノードに記憶されているデータシンボルに対する依存（dependence）を示す、選択された配列の指示をデータ生成ノードに送信することとを備える。
【０００６】
ある実施形態では、選択された配列の指示をデータ生成ノードに送信することは、各データ生成ノードに、そのデータ生成ノードに記憶されているパリティシンボルの、他のデータ生成ノードに記憶されているデータシンボルに対する依存の指示を送信することを備える。
【０００７】
ある実施形態では、選択された配列の指示をデータ生成ノードに送信することは、各データ生成ノードに、そのノードに記憶されているデータシンボルを送信すべきワイヤレスネットワークのデータ生成ノードの指示を送信することを備える。
【０００８】
ある実施形態では、リンク品質推定の指示は、ノード間誤り確率である。
【０００９】
ある実施形態では、方法はさらに、最高のノード間誤り確率を有するノードのペアを識別することと、識別されたノードのペアの間でデータシンボルが交換されない配列を選択することとを備える。
【００１０】
ある実施形態では、方法はさらに、部分グラフの集合を形成するために最高のノード間確率を有するノードを繰り返し一緒にグループ化することと、部分グラフの集合の補グラフからアレイ符号の配列を決定することとを備える。
【００１１】
ある実施形態では、方法はさらに、複数の可能な配列の各々に対する停止確率（outage probability）を決定することと、最低の停止確率を有する可能な配列を選択することとを備える。
【００１２】
ある実施形態では、アレイ符号フロムの配列は、複数の記憶されている可能な配列から選択される。
【００１３】
ある実施形態では、リンク品質推定の指示を使用して複数の可能な配列からアレイ符号のある配列を選択することは、アレイ符号を、ネットワーク中のデータ生成ノードの数およびアレイ符号の要求される冗長性の指示から決定することと、アレイ符号から複数の可能な配列を決定することとを備える。
【００１４】
ある実施形態では、ワイヤレスネットワークのためのコントローラが開示される。ワイヤレスネットワークは、複数のデータ生成ノードを備える。各データ生成ノードは、データシンボルとパリティシンボルとを生成して記憶するように構成される。パリティシンボルは、他のデータ生成ノードに記憶されているデータシンボルに依存する。コントローラは、データ生成ノード間のワイヤレスリンクに対するリンク品質推定の指示を受信するように構成されるワイヤレスインターフェースと、リンク品質推定の指示を使用して複数の可能な配列からアレイ符号のある配列を選択するように構成されるプロセッサとを備え、アレイ符号は、複数のデータ生成ノード中のデータ生成ノードの数と、ワイヤレスネットワークに記憶されているデータシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存し、配列は、各データ生成ノードに対して、そのデータ生成ノードに記憶されているパリティシンボルの、他のデータ生成ノードに記憶されているデータシンボルに対する依存を示し、ワイヤレスインターフェースはさらに、選択された配列の指示をデータ生成ノードに送信するように構成される。
【００１５】
ある実施形態では、コントローラはさらに、複数の可能な配列のための記憶装置を備える。
【００１６】
ある実施形態では、記憶装置は、複数のアレイ符号を記憶するように構成され、プロセッサはさらに、複数のアレイ符号からあるアレイ符号を選択するように構成される。
【００１７】
ある実施形態では、ワイヤレスインターフェースはさらに、各データ生成ノードに、そのデータ生成ノードに記憶されているパリティシンボルの構成されたアレイ符号に従った、他のデータ生成ノードに記憶されているデータシンボルに対する依存の指示を送信するように構成される。
【００１８】
ある実施形態では、ワイヤレスインターフェースはさらに、各データ生成ノードに、そのノードに記憶されているデータを送信すべきワイヤレスネットワークのデータ生成ノードの指示を送信するように構成される。
【００１９】
ある実施形態では、リンク品質推定の指示はノード間誤り確率である。
【００２０】
ある実施形態では、プロセッサはさらに、最高のノード間誤り確率を有するノードのペアを識別し、識別されたノードのペアの間でデータシンボルに対するパリティシンボルの依存がない配列を選択するように構成される。
【００２１】
ある実施形態では、プロセッサはさらに、部分グラフの集合を形成するために最高のノード間確率を有するノードを繰り返し一緒にグループ化し、部分グラフの集合の補グラフからアレイ符号の配列を決定するように構成される。
【００２２】
ある実施形態では、プロセッサはさらに、複数の可能な配列の各々に対する停止確率を決定し、最低の停止確率を有する可能な配列を選択するように構成される。
【００２３】
説明される実施形態は、特定のハードウェアデバイス、適切なソフトウェアによって構成される汎用デバイス、または両方の組合せへと組み込まれ得る。態様は、完全なソフトウェアの実装形態と、既存のソフトウェアの修正または増強のためのアドオンコンポーネント（プラグインなど）とのいずれかとして、ソフトウェア製品において具現化され得る。そのようなソフトウェア製品は、記憶媒体（たとえば、光学ディスク、またはフラッシュメモリなどの大容量記憶メモリ）または信号媒体（ダウンロードなど）などの、キャリア媒体（carrier medium）において具現化され得る。実施形態に適した特定のハードウェアデバイスは、ＡＳＩＣ、ＦＰＧＡもしくはＤＳＰ、または他の専用機能ハードウェア手段などの、用途固有のデバイスを含み得る。ソフトウェアまたはハードウェアにおける実施形態の前述の議論はいずれも、まだ発見または定義されていない実行の手段に対する本発明の今後の実装形態を限定するものではないことを、読者は理解するであろう。
【００２４】
図１は、ある実施形態によるワイヤレスネットワーク１００を示す。ワイヤレスネットワークは、複数のデータ生成ノードを備える。図１に示される実施形態では、ネットワーク１００は、第１のデータ生成ノード１１０と、第２のデータ生成ノード１２０と、第３のデータ生成ノード１３０と、第４のデータ生成ノード１４０とを備える。
【００２５】
データ生成ノードの各々は、ノードに特有のパラメータを測定するように構成されるセンサを備える。たとえば、データ生成ノードは、ボディ・エリア・ネットワーク（body area network）では患者のバイタルサインを測定するセンサであってよく、データ生成ノードは、エネルギー使用量を測定するスマートメーターであってよく、または、データ生成ノードは、大気質などの環境変数を測定することができ得る。
【００２６】
データ生成ノードは、ワイヤレスネットワーク１００を通じて互いにワイヤレスに通信するように構成される。このことは、個々のノード上で測定されたデータが取り出されることを可能にする。
【００２７】
多くの場合、すべてのノードからのデータを、それらの部分集合だけと通信することによって取得するのが望ましい。このことは、冗長性がネットワークに導入されれば、すなわち、あるノードからのデータが１つまたは複数の他のノードに記憶されれば、可能である。適切な計画により、すべてのｎ個のノードからデータを、そのうちのｋ個だけから取り出すことが可能であり得る。別の利点は、すべてのノードとの通信が可能である場合であっても、コンセントレータ・ノード（concentrator node）はｋ個のノードとコンタクトを取るだけでよいということであり得る。
【００２８】
これは、抹消コーディング（erasure coding）を利用することによって達成されることが可能であり、抹消コーディングは、一部の観測結果が入手できない場合であっても、すべてのデータを再構築することを可能にする。これは、アレイ符号を用いて達成されることが可能であり、ここで各列は、ネットワーク中のノードを表し、それの固有のデータおよび他のノードからのデータのためのパリティシンボルからなる。ｎ個のノードがある場合、データは、列のうちのｋ個だけを知ることで再構築することが可能であるべきである。
【００２９】
抹消符号（erasure code）が冗長性のもとで最大の数の消失したシンボルを訂正することができる場合、その符号はＭＤＳ（ｍａｘｉｍａｌ−ｄｉｓｔａｎｃｅ  ｓｅｐａｒａｂｌｅ）であると言われる。パリティシンボルが可能な限り少数のデータシンボルの関数であることも重要であり、それは、このことが、ノード間で交換される必要のあるデータパケットの数を最小にするからである。この性質をもつ抹消符号は、低密度と呼ばれる。
【００３０】
抹消符号がセンサ・ネットワークの状況で動作する方法は、ネットワーク中の各ノードがそれの固有のデータを生成するというものである。各ノードは次いで、ノードに障害が発生するであろう場合には、そのデータのコピーを持つためにそのデータを他のノードと共有するであろう。あるノードからのすべてのデータが、単純に、ｒ個の他のノードに完全にコピーされ得ることに留意されたい。それは、データが今やｒ＋１個のノードに存在し、少なくとも１つのコピーが生き残るので、それらのうちのｒ個のノードの障害に対処できるからである。しかしながら、これは、ノードの障害への回復力（resilient）を持たせるには非効率な方法であり、同じレベルの抹消訂正（erasure correction）を実現することが可能でありながら冗長性および記憶量がはるかに小さい、より良い符号が設計され得る。コンセントレータ・ノードがネットワークからのデータを必要とするとき、ｎ個のノードのうちのｋ個に連結するだけで十分であり、抹消符号により、ｎ−ｋ個の障害ノードからのデータが再構築されることが可能である。これは、ｋ個の生き残ったノードにおけるパリティシンボルに対するデータの既知の依存性を使用することによって行われる。
【００３１】
パリティシンボルを形成するために、データ生成ノードはデータを交換することが必要である。このノード間通信（internode communication）に障害がある場合、パリティシンボルは計算されることが不可能であり、ノードの障害に対する回復力（resilience）が下がる。少なくとも１つのノード間リンクがダウンすると、これは停止（outage）と呼ばれる。
【００３２】
しかしながら、たとえば長期間の測定値を使用することによって、ノード間誤り確率が知られている場合、ノード間誤り確率はアレイ符号を構成するために使用され得る。所与のアレイ符号はノードの名前を変えることによって多くの等価な方法で構成され得るので、ノード間誤り確率は停止確率を下げるために利用され得る。
【００３３】
図２は、ある実施形態によるコントローラ２００を示す。コントローラは、ネットワークのノードによって使用されるべきアレイ符号の構成を決定する。コントローラ２００は、ワイヤレスネットワークのデータ生成ノードとして実装され得る。それは、上記で説明されたようなコンセントレータ・ノードであり得る。
【００３４】
コントローラ２００は、ワイヤレスインターフェース２１０と、プロセッサ２２０と、記憶装置２３０とを備える。ワイヤレスインターフェース２１０は、コントローラ２００が、ワイヤレスネットワークのデータ生成ノードから情報を受信することと、ワイヤレスネットワークのデータ生成ノードから情報を受信することとを可能にする。ワイヤレスインターフェースは、データ生成ノード間のリンクのリンク品質の指示を受信する。これらの指示は、ノード間誤り確率であり得る。ワイヤレスインターフェース２１０はまた、アレイ符号と構成との指示をデータ生成ノードに送信するように動作可能である。これらの指示は、各ノードに記憶されているパリティシンボルがどのように計算されるべきであるかということと、パリティシンボルが計算され得るように、ネットワークのどのノードに各データ生成ノードがそのノードに記憶されているデータの部分の指示を送信すべきかということとの指示を備え得る。
【００３５】
これらの指示は、各ノードが、どのデータシンボルをどこに送信すべきかということと、そのノードに記憶されるべきパリティシンボルをどのように計算するかということとを知ることを可能にする。アレイ符号が構成されると、この情報はすべてのノードにシグナリングされる。
【００３６】
ある実施形態では、どの構成が使用されるべきかを示すインデックスは、実際の構成ではなくすべてのノードに分配される。
【００３７】
プロセッサ２２０は、データ生成ノードによって使用されるべきアレイ符号の配列を選択するために、リンク品質の受信された指示を使用するように動作可能である。実施形態に従って配列を選択するプロセスは、以下でより詳細に論じられる。
【００３８】
記憶装置２３０は、アレイ符号２３２と、アレイ符号のための可能な配列２３４とを記憶する。以下でより詳細に説明されるように、アレイ符号は、パリティシンボルがデータ生成ノードに記憶されているデータシンボルからどのように計算されるかを示す。各アレイ符号に対して、複数の可能な配列がある。プロセッサ２２０は、停止確率を減らす、または最小にするために、可能な配列のうちの１つを選択するように構成される。
【００３９】
図２ａは、ある実施形態による、ワイヤレスネットワークにおいて分散される管理の方法を示す。方法は、図２に示されるコントローラ２００によって実行され得る。
【００４０】
ステップＳ２０２において、コントローラは、ワイヤレスネットワークのノードからリンク品質推定の指示を受信する。これらの指示は、ノード間誤り確率であり得る。
【００４１】
ステップＳ２０４において、コントローラは、リンク品質の受信された指示を使用して、複数の可能な配列からアレイ符号のある配列を選択する。
【００４２】
ステップＳ２０６において、コントローラは、選択された配列の指示をデータ生成ノードに送信する。ステップＳ２０６に続いて、データ生成ノードは、選択された配列においてアレイ符号によって特定されるようにデータシンボルを交換し、パリティシンボルを生成する。
【００４３】
ノードの障害からネットワークを保護するために、各ノードは、冗長性をもたらすように情報を交換することができる。たとえば、ｒ＝２個の消失を訂正することが可能なｎ＝４個のノードにおけるアレイ符号は、パリティシンボル
【００４４】
【数１】
0006357580.tif 000002
をアレイ
【００４５】
【表１】
0006357580.tif 000003
へと形成し（すべての演算がＧＦ（２）の中にある）、ここで、ｄi,jおよびｆi,jはそれぞれ、ノードｊにおけるｉ番目のデータとパリティシンボルとを示す。図３は、ｒ＝２個の消失を訂正することが可能なｎ＝４個のノードについて上で説明されたアレイ符号の有向グラフの表現を示す。データ生成ノードは、０、１、２、および３と名付けられる。各エッジは、パリティシンボルを形成するために別のノードと交換される必要のあるデータシンボルを表す。図３に示されるように、ノード０は、データｄ0,0をノード１および２に送信し、データｄ0,1をノード１から、およびデータｄ0,3をノード３から受信する。上記の式において示されるように、ノード０は、ノード０に記憶されているパリティシンボルｆ0,0を計算するために、データｄ0,1とデータｄ0,3とを使用する。
【００４６】
少なくとも１つのノード間通信に障害がある場合、いくつかのパリティシンボルは形成されることが不可能であり、これを停止と呼ぶ。ノードｉとノードｊの間の通信に障害が発生する確率がｐi,jである場合、停止確率は、
【００４７】
【数２】
0006357580.tif 000004
である。
【００４８】
一次の近似は、
【００４９】
【数３】
0006357580.tif 000005
である。
【００５０】
しかしながら、図３から、すべての交換が必要とされることは限らないことがわかり、たとえば、ノード１はノード２に何も送信しない。Ｅが有向連結グラフ（directed connectivity graph）におけるエッジの集合を示す場合、停止確率は、
【００５１】
【数４】
0006357580.tif 000006
と書かれ得る。
【００５２】
図４は、ある実施形態におけるノード間誤り確率を示す。図４に示されるように、ノード０とノード１の間のノード間誤り確率は０．１４３であり、ノード０とノード２の間のノード間誤り確率は０．０９７であり、ノード０とノード３の間のノード間誤り確率は０．０６０である。ノード１とノード２の間のノード間誤り確率は０．０７４であり、ノード１とノード３の間のノード間誤り確率は０．０８８であり、ノード２とノード３の間のノード間誤り確率は０．０６８である。簡単にするために、誤り確率は対称的（ｐi,j＝ｐj,i）であると仮定されるが、本明細書で説明されるすべての方法は、誤り確率が対称的ではないとしても機能することに留意されたい。ノード間誤り確率が図４のようである場合、停止確率は０．５４２７である。
【００５３】
２つのグラフＧ1およびＧ2は、（ｕ，ｖ）がＧ2におけるエッジである場合にだけ（φ（ｕ），φ（ｖ））がＧ1におけるエッジとなるような、全単射の写像（bijective mapping）φが存在する場合、同型である（isomorphic）と言われる。これは、ノードの「名前変更（renaming）」として考えられることが可能であり、名前変更はグラフを変更するが、新たなグラフにおいて連結性は等価であるので、基本的に同じものである。同型であるすべてのグラフの集合は、いくつかの同値類へと分けられ得る。
【００５４】
図５ａから図５ｆは、図３に示されるグラフに対する同値類を示す。上記のアレイ符号は、すべてのこれらのグラフによって表され得ることが明らかである。たとえば、（ａ）と（ｂ）の違いは、ノード０と３が入れ替わっていることと、ノード１と２が入れ替わっていることである。アレイ符号は同じままであるが、エッジの集合Ｅが異なるので、停止確率は６つの構成の各々に対して異なる。
【００５５】
同じノード間誤り確率を使用すると、停止確率は、図（ａ）から図（ｆ）に示される同値類に対してそれぞれ、０．５４２７、０．５２８５、０．５２８５、０．５０１６、０．５０１６である。したがって、構成（ｅ）または（ｆ）のいずれかが、停止確率をより低くしながら同じ抹消訂正能力を達成するために使用され得る。この観測結果を使用することによって、実施形態では、等価な連結グラフを選ぶことによって、すなわちノードの名前を変えることによって、停止確率が下げられ、または最小にされ得る。
【００５６】
このことは、ノード間誤り確率ｐi,jが、たとえば長期間の測定値を介して知られている場合、アレイ符号が最適な方法で構成され得ることを意味する。
【００５７】
一実施形態では、停止確率は、アレイ符号の連結グラフのすべての同値類に対して上記の式に従って計算され、最良のものが選ばれる。同値類は、アレイ符号生成行列だけに依存するので、事前に計算され得る。
【００５８】
最良の構成が確立されると、最良の構成は、たとえばマスターノードとして活動するコレクタノードまたはネットワークノードによって、ノードに通信され得る。このことは、ノード間誤り確率が変化するときは常に、アレイ符号が動的に構成され得ることを意味する。たとえば、車両が２つのノード間に一時的に停車している場合、そのノード間誤り確率は、ある時間の期間の間非常に大きい可能性がある。これがネットワークによって検出されるとき、アレイ符号は、停止確率を最小にするように再構成され得る。
【００５９】
抹消符号は、ノード数ｎおよび障害の数ｒのそれぞれに対して生成され得る。抹消符号の例は、ｎがｒで割り切れるときである。
【００６０】
図６ａは、ｒ＝２個の障害を訂正することが可能なｎ＝４個のノードを有するアレイ符号の例示的なグラフを示す。各ノードは、ｍ＝１個のデータシンボルとｐ＝１個のパリティシンボルとを記憶する。データシンボルがｄ0,i、ｉ＝０，…，３によって示される場合、パリティシンボルは、
【００６１】
【数５】
0006357580.tif 000007
として形成され、ここですべての演算がＧＦ（３）において行われる。
【００６２】
これは、図６ａに示されるグラフによって表されることが可能であり、図６ａは、どのノードがどのノードに連結することが必要かを示す。このタイプのアレイ符号に対して、ノードｉがデータシンボルの少なくとも１つをノードｊに送信する場合、このことは、ノードｊが少なくとも１つのデータシンボルをノードｉに送信することを示唆することに留意されたい。したがって、連結性は無向グラフ（undirected graph）によって表され得る。
【００６３】
図６ｂは、図６ａに示されるノード連結性の無向グラフを示す。図６ｂのグラフは、４つのノードを有する２−正則グラフ（2-regular graph）である（一般に、このタイプのアレイ符号はｎ個のノードを有する（ｎ−ｒ）−正則グラフである）。
【００６４】
図７ａから図７ｃは、図６ｂに示されるグラフの同値類を示す。これらのグラフは同型であり、ノードが並べ替えられただけであることがわかる。それの構造により、アレイ符号を構成するための準最適なアルゴリズムを設計することが可能である。
【００６５】
多数のノードおよび／またはノードの障害に対して、同値類の数は非常に大きいことがあり、アレイ符号のためにそれらのすべてを評価することは非現実的であり、および／または複雑すぎることがある。
【００６６】
実施形態において、上記で論じられる徹底的な探索（exhaustive search）よりもかなり複雑さが低い準最適なアルゴリズムが使用される。アルゴリズムは欲張りな手法（greedy approach）を使用する。
【００６７】
ｎがｒで割り切れる場合、アレイ符号の例は連結性（隣接性（adjacency））行列を有する。  
【００６８】
【数６】
0006357580.tif 000008
この連結グラフは正則完全多部グラフ（regular complete multipartite graph）であることが示され得る。このことは、ｎ個のノードがｒ個のノードを各々有するｎ／ｒ個の集合へと並べられ得ることを意味し、各ノードは他の集合中のすべてのノードに連結されるが、自身の固有の集合中のいずれのノードにも連結されない。たとえば、図６ｂでは、ノード｛０，２｝はある集合を形成し、ノード｛１，３｝もある集合を形成する。ノード内の連結はないが、各ノードは自身の固有の集合の外部のすべてのノードに連結されている。
【００６９】
グラフＧの補グラフは、同じノード上のグラフ
【００７０】
【数７】
0006357580.tif 000009
であり、ただし、
【００７１】
【数８】
0006357580.tif 000010
の中の２つのノードが、Ｇにおいて連結されていない場合にだけ連結されるようなものである。正則完全多部グラフの補グラフは、互いに素である完全部分グラフのユニオン（union of disjoint complete subgraphs）である。
【００７２】
図８は、図６ｂに示されるグラフの補グラフを示す。  
【００７３】
【数９】
0006357580.tif 000011
【００７４】
個の部分グラフの各々はｒ＝２個のノードを有し、ノード｛０，２｝は完全部分グラフを形成し、ノード｛１，３｝も完全部分グラフを形成し、これらの部分グラフは互いに素である。
【００７５】
ある実施形態では、エッジ集合Ｅにわたる誤り確率の合計を最小にする代わりに、この合計は、補エッジ集合（complement edge set）
【００７６】
【数１０】
0006357580.tif 000012
にわたって最大にされ、それは、
【００７７】
【数１１】
0006357580.tif 000013
【００７８】
であるからである。  
これに基づいて、最良の利用可能な誤り確率に従ってアレイ符号中のノードを並べる、欲張りアルゴリズム（greedy algorithm）が考案され得る。
【００７９】
図９は、上記で説明されたような欲張りアルゴリズムに基づいてアレイ符号を構成する方法を示すフローチャートである。
【００８０】
ステップＳ９０２に示されるようなアルゴリズムへの入力は、ノード間誤り確率ｐi,jである。ステップＳ９０４において、このアルゴリズムは、すべてのノードの集合Ｖ＝｛０，…，ｎ−１｝を形成することによって初期化し、部分グラフカウンタηは１に設定される。アルゴリズムが動作するにつれて、ノードは集合Ｖから、
【００８１】
【数１２】
0006357580.tif 000014
【００８２】
の部分グラフに対応する集合へと移される。ステップＳ９０６において、
【００８３】
【数１３】
0006357580.tif 000015
【００８４】
のη番目の部分グラフに対するノードの集合が形成される。
【００８５】
ステップＳ９０８において、集合Ｖの中で最大のノード間誤り確率を有するノードのペアが識別される。ノードのこのペアは、部分グラフ集合Ｖηに移され、集合Ｖから除去される。部分グラフＶηにおける状況下でノード番号に対するカウンタρは、３に設定される。このカウンタは、ステップＳ９０８において２つのノードがすでに部分グラフＶηに追加されているので、３に設定される。
【００８６】
ステップＳ９１０において、ノード番号に対するカウンタρは、障害の数ｒと比較される。上記で述べられたように、各集合はｒ個のノードを有する。カウンタがｒより小さい場合、方法はステップＳ９１２に移る。カウンタがｒより大きい場合、方法はステップＳ９１４に移る。
【００８７】
ステップＳ９１２において、Ｖの中の他の残りのノードとの最高の総ノード間誤り確率を有する、Ｖの中の残りのノードが識別される。この最良の残りのノードは次いで、部分グラフ集合Ｖηに移され、集合Ｖから除去される。次いで、部分グラフＶηにおける状況下でノード番号に対するカウンタρがインクリメントされる。
【００８８】
ステップＳ９１４において、部分グラフカウンタηがインクリメントされる。ステップＳ９１６において、部分グラフカウンタηは、すべての部分グラフが生成されたかどうかを確認するために、
【００８９】
【数１４】
0006357580.tif 000016
と比較される。  
【００９０】
【数１５】
0006357580.tif 000017
がηより大きい場合、方法はステップＳ９０６に戻り、次の部分グラフが形成される。  
【００９１】
【数１６】
0006357580.tif 000018
がηより大きくない場合、方法は終了する。
【００９２】
図１０ａは、ｒ＝３個の消失を訂正することが可能なｎ＝６個のノードを有するアレイ符号の例を示す。すべての演算はＧＦ（５）の中にある。
【００９３】
図１０ｂは、図１０ａに示されるアレイ符号に対する連結グラフを示す。
【００９４】
図１１は、ノード間誤り確率を示す。上記で論じられたように、方法が機能するためにノード間誤り確率が対称的である必要はないことに留意されたい。
【００９５】
図９における欲張りアルゴリズムを使用して、第１のノード｛１，２｝が選択され、それは、ｐ1,2が最大の誤り確率であるからである。したがって、このステップの後では、Ｖ1＝｛１，２｝およびＶ＝｛０，３，４，５｝である。そして、残りのノードの最良のものはノード４であり、それは、ａｒｇ  ｍａｘi∈VΣj∈V1ｐi,j＝４であるからである。その結果、このステップの後では、Ｖ1＝｛１，２，４｝およびＶ＝｛０，３，５｝である。このことは、部分グラフのノード集合Ｖ1を完成させ、それはその集合の中にｒ＝３個のノードがあるからである。
【００９６】
アルゴリズムは次いで、次の互いに素である部分グラフを発見することに移る。最大の残りの確率はａｒｇ  ｍａｘ(i,j)∈Vｐi,j＝（０，５）であるので、Ｖ2＝｛０，５｝およびＶ＝｛３｝である。最良の（および唯一の）残りのノードは３であり、これはＶ2＝｛０，３，５｝を完成させる。すべての
【００９７】
【数１７】
0006357580.tif 000019
個の部分グラフがここで発見される。
【００９８】
ここで、補グラフに注目することによって、アレイ符号の構成（ノードの名前変更）が行われる。
【００９９】
図１２は、図１０ｂに示される連結グラフの補グラフを示す。３つの連結されるノード｛０，２，４｝はＶ1＝｛１，２，４｝にマッピングされるべきであり、他の連結されるノード｛１，３，５｝はＶ2＝｛０，３，５｝にマッピングされるべきである。このマッピングは一意ではないことに留意されたい。
【０１００】
図１３は、再構成されるアレイ符号を示す。図１０ｂでは１つのグラフに対して１０個の同型グラフがあるので、徹底的な探索はそれらのすべてを確認して、最良のものを選ぶであろう。この例では、図９の欲張りアルゴリズムが最良のものを発見することが判明するが、それは保証されていない。
【０１０１】
図１４は、上記で説明された欲張りアルゴリズムの性能の評価を示す。欲張りアルゴリズムの平均の性能を評価するために、ノード間誤り確率は１０eとしてモデル化され、ここでｅは間隔［−４，−２］において均一に分布するランダムな変数である。そして、停止確率もランダムな変数であり、それの確率密度関数（ＰＤＦ：probability density function）が示されている。以上のように、欲張りアルゴリズムは、構成なしの場合よりもはるかに良好な、また、最適なもの（徹底的な探索）とほぼ同じくらい良好な性能がある。
【０１０２】
本明細書で説明される実施形態は、停止確率を下げるようにアレイ符号を構成する方法を提供する。たとえば、長期間の測定値を使用することによって、ノード間誤り確率が知られている場合、ノード間誤り確率は、アレイ符号を構成するために使用される。所与のアレイ符号は、単にノードの名前を変えることによって、多くの等価な方法で構成され得るので、ノード間誤り確率は、停止確率を下げるために利用され得る。
【０１０３】
いくつかの実施形態が説明されてきたが、これらの実施形態は例としてのみ提示されており、本発明の範囲を制限することは意図されていない。実際には、本明細書で説明される新規の方法、システム、デバイス、およびネットワークは、様々な他の形式で具現化され得る。さらに、本発明の趣旨から逸脱することなく、様々な省略、置換、および変更が行われ得る。添付の特許請求の範囲およびその等価物は、本発明の範囲および趣旨の範囲内に入るような形式または修正を包含することが意図される。
以下、本願出願当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
ワイヤレスネットワークにおける分散型の記憶を管理する方法であって、前記ワイヤレスネットワークが複数のデータ生成ノードを備え、各データ生成ノードがデータシンボルとパリティシンボルとを生成して記憶するように構成され、前記パリティシンボルが他のデータ生成ノードに記憶されているデータシンボルに依存し、前記方法は、
前記データ生成ノード間のワイヤレスリンクに対するリンク品質推定の指示を受信することと、
リンク品質推定の前記指示を使用して複数の可能な配列からアレイ符号のある配列を選択することと、前記アレイ符号は、前記複数のデータ生成ノード中のデータ生成ノードの数と、前記ワイヤレスネットワークに記憶されている前記データシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存し、前記配列は、各データ生成ノードに対して、当該データ生成ノードに記憶されている前記パリティシンボルの、他のデータ生成ノードに記憶されている前記データシンボルに対する依存を示す、
前記選択された配列の指示を前記データ生成ノードに送信することとを備える、方法。
［Ｃ２］
前記選択された配列の指示を前記データ生成ノードに送信することが、各データ生成ノードに、当該データ生成ノードに記憶されている前記パリティシンボルの、他のデータ生成ノードに記憶されている前記データシンボルに対する前記依存の指示を送信することを備える、［Ｃ１］に記載の方法。
［Ｃ３］
前記選択された配列の指示を前記データ生成ノードに送信することが、各データ生成ノードに、当該ノードに記憶されている前記データシンボルを送信すべき前記ワイヤレスネットワークのデータ生成ノードの指示を送信することを備える、［Ｃ１］に記載の方法。
［Ｃ４］
リンク品質推定の前記指示がノード間誤り確率である、［Ｃ１］に記載の方法。
［Ｃ５］
最高のノード間誤り確率を有するノードのペアを識別することと、前記識別されたノードのペアの間でデータシンボルが交換されない配列を選択することとをさらに備える、［Ｃ４］に記載の方法。
［Ｃ６］
部分グラフの集合を形成するために前記最高のノード間確率を有するノードを繰り返し一緒にグループ化することと、部分グラフの前記集合の補グラフから前記アレイ符号の前記配列を決定することとをさらに備える、［Ｃ５］に記載の方法。
［Ｃ７］
前記複数の可能な配列の各々に対する停止確率を決定することと、最低の停止確率を有する可能な配列を選択することとを備える、［Ｃ４］に記載の方法。
［Ｃ８］
前記アレイ符号フロムの前記配列が、複数の記憶されている可能な配列から選択される、［Ｃ１］に記載の方法。
［Ｃ９］
リンク品質推定の前記指示を使用して複数の可能な配列から前記アレイ符号のある配列を選択することが、アレイ符号を、前記ネットワーク中のデータ生成ノードの前記数および前記アレイ符号の要求される冗長性の指示から決定することと、前記アレイ符号から前記複数の可能な配列を決定することとを備える、［Ｃ１］に記載の方法。
［Ｃ１０］
ワイヤレスネットワークのためのコントローラであって、前記ワイヤレスネットワークが複数のデータ生成ノードを備え、各データ生成ノードがデータシンボルとパリティシンボルとを生成して記憶するように構成され、前記パリティシンボルが他のデータ生成ノードに記憶されているデータシンボルに依存し、前記コントローラが、  前記データ生成ノード間のワイヤレスリンクに対するリンク品質推定の指示を受信するように構成されるワイヤレスインターフェースと、
リンク品質推定の前記指示を使用して複数の可能な配列からアレイ符号のある配列を選択するように構成されるプロセッサとを備え、前記アレイ符号が、前記複数のデータ生成ノード中のデータ生成ノードの数と、前記ワイヤレスネットワークに記憶されている前記データシンボルのすべてがノードから生成され得るのに必要なノードの数とに依存し、前記配列が、各データ生成ノードに対して、当該データ生成ノードに記憶されている前記パリティシンボルの、他のデータ生成ノードに記憶されている前記データシンボルに対する依存を示し、
前記ワイヤレスインターフェースがさらに、前記選択された配列の指示を前記データ生成ノードに送信するように構成される、コントローラ。
［Ｃ１１］
前記複数の可能な配列に対する記憶装置をさらに備える、［Ｃ１０］に記載のコントローラ。
［Ｃ１２］
前記記憶装置が複数のアレイ符号を記憶するように構成され、前記プロセッサがさらに前記複数のアレイ符号からあるアレイ符号を選択するように構成される、［Ｃ１１］に記載のコントローラ。
［Ｃ１３］
前記ワイヤレスインターフェースがさらに、各データ生成ノードに、当該データ生成ノードに記憶されている前記パリティシンボルの前記構成されたアレイ符号に従った、他のデータ生成ノードに記憶されている前記データシンボルに対する依存の指示を送信するように構成される、［Ｃ１０］に記載のコントローラ。
［Ｃ１４］
前記ワイヤレスインターフェースがさらに、各データ生成ノードに、当該ノードに記憶されている前記データを送信すべき前記ワイヤレスネットワークのデータ生成ノードの指示を送信するように構成される、［Ｃ１０］に記載のコントローラ。
［Ｃ１５］
リンク品質推定の前記指示がノード間誤り確率である、［Ｃ１０］に記載のコントローラ。
［Ｃ１６］
前記プロセッサがさらに、最高のノード間誤り確率を有するノードのペアを識別し、前記識別されたノードのペアの間でデータシンボルに対するパリティシンボルの依存がない配列を選択するように構成される、［Ｃ１５］に記載のコントローラ。
［Ｃ１７］
前記プロセッサがさらに、部分グラフの集合を形成するために前記最高のノード間確率を有するノードを繰り返し一緒にグループ化し、部分グラフの前記集合の補グラフからアレイ符号の前記配列を決定するように構成される、［Ｃ１６］に記載のコントローラ。
［Ｃ１８］
前記プロセッサがさらに、前記複数の可能な配列の各々に対する停止確率を決定し、最低の停止確率を有する可能な配列を選択するように構成される、［Ｃ１５］に記載のコントローラ。
［Ｃ１９］
プロセッサ上で実行されると、前記プロセッサに、［Ｃ１］に記載の方法を実行させるプロセッサ実行可能命令を搬送する、非一時的コンピュータ可読キャリア媒体。
【図１】
0006357580.tif 000020
【図２】
0006357580.tif 000021
【図２ａ】
0006357580.tif 000022
【図３】
0006357580.tif 000023
【図４】
0006357580.tif 000024
【図５（ａ）】
0006357580.tif 000025
【図５（ｂ）】
0006357580.tif 000026
【図５（ｃ）】
0006357580.tif 000027
【図５（ｄ）】
0006357580.tif 000028
【図５（ｅ）】
0006357580.tif 000029
【図５（ｆ）】
0006357580.tif 000030
【図６（ａ）】
0006357580.tif 000031
【図６（ｂ）】
0006357580.tif 000032
【図７ａ】
0006357580.tif 000033
【図７ｂ】
0006357580.tif 000034
【図７ｃ】
0006357580.tif 000035
【図８】
0006357580.tif 000036
【図９】
0006357580.tif 000037
【図１０（ａ）】
0006357580.tif 000038
【図１０（ｂ）】
0006357580.tif 000039
【図１１】
0006357580.tif 000040
【図１２】
0006357580.tif 000041
【図１３】
0006357580.tif 000042
【図１４】
0006357580.tif 000043