Reconfigurable encoding arrays for reduced outage probability sensor networks

• US 10,404,409 B2
• Filed: 12/11/2014
• Issued: 09/03/2019
• Est. Priority Date: 12/11/2014
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sandell, Magnus Stig Torsten, Tosato, Filippo, Gormus, Sedat
• Primary Examiner(s): Abraham, Esaw T
• Application Number:
  US15/503,579
• Publication Number:
  US 20180083734A1
• Time in Patent Office: 1,727 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 1/0045 Arrangements at the receiver end
• CPC Class Codes: H04L 1/0058 Block-coded modulation
• CPC Class Codes: H04L 1/206 for modulated signals

Abstract

In an embodiment, a method of managing distributed storage in a wireless network is disclosed. The wireless network comprises a plurality of data generating nodes, each data generating node configured to generate and store data symbols and parity symbols. The parity symbols depend on data symbols stored on other data generating nodes. The method comprises receiving indications of link quality estimates for wireless links between the data generating nodes; selecting an arrangement of an array code from a plurality of possible arrangements using the indications of link quality estimates, the array code depending on the number of data generating nodes in the plurality of data generating nodes and a required number of nodes from which all of the data symbols stored in the wireless network can be generated, the arrangement indicating for each data generating node, the dependence of the parity symbols stored on that data generating node on the data symbols stored on other data generating nodes; and sending an indication of the selected arrangement to the data generating nodes.

Claims

1. A method of communicating data symbols in a wireless network, the wireless network comprising a concentrator node, a first data generating node, and a plurality of other data generating nodes, the method comprising:

receiving, at the first data generating node, data symbols from the other data generating nodes;

receiving, at the first data generating node, an indication of an arrangement of an array code from the concentrator node;

receiving, at the first data generating node, a request from the concentrator node for data symbols from the wireless network; and

transmitting, by the first data generating node to the concentrator node, a data symbol generated by the first data generating node and the parity symbol,

wherein the array code comprises a plurality of entries, and

wherein each entry indicates the dependence of a parity symbol generated by a node on the data symbols received from other nodes, and the arrangement of the array code indicates which entry corresponds to which data generating node of the wireless network, the arrangement of the array code being determined by;

receiving, at the concentrator node, a plurality of link-quality indications, wherein each link-quality indication represents the quality of the wireless communication link between two nodes of the plurality of data generating nodes; and

assigning an entry of the array code to each data generating node in a manner that minimizes an outage probability of the wireless network, wherein the outage probability represents the probability that parity symbols cannot be formed by the plurality of data generating nodes and is based on the plurality of link-quality indications received by the concentrator node.

2. A method according to claim 1, further comprising sending an indication of the arrangement to the data generating nodes by sending to each data generating node an indication of the dependence of the parity symbols stored on that data generating node on the data symbols stored on other data generating nodes.

3. A method according to claim 1, further comprising sending an indication of the arrangement to the data generating nodes by sending to each data generating node an indication of data generating nodes of the wireless network to which to send the data symbols stored on that node.

4. A method according to claim 1 wherein the indications of link-quality are internode error probabilities.

5. A method according to claim 4, further comprising identifying a pair of nodes having the highest internode error probability and selecting an arrangement in which no data symbols are exchanged between the identified pair of nodes.

6. A method according to claim 5, further comprising iteratively grouping nodes having the highest internode probability together to form a set of subgraphs and determining the arrangement for the array code from a complement graph of the set of subgraphs.

7. A method according to claim 4, further comprising determining an outage probability for each of the plurality of possible arrangements and selecting the possible arrangement having the lowest outage probability.

8. A method according to claim 1 wherein the arrangement of the array code from is selected from a plurality of stored possible arrangements.

9. A method according to claim 1, further comprising selecting an arrangement of the array code from a plurality of possible arrangements using the indications of link-quality by determining an array code from the number of data generating nodes in the network and an indication of the required redundancy of the array code, and determining the plurality of possible arrangements from the array code.

19. A non-transitory computer readable carrier medium carrying processor executable instructions which when executed on a processor cause the processor to carry out a method according to claim 1.

10. A controller for a wireless network, the wireless network comprising a plurality of data generating nodes, each data generating node configured to generate and store data symbols and parity symbols, the parity symbols depending on data symbols stored on other data generating nodes, the controller comprising:

a wireless interface configured to receive indications of link quality estimates for wireless links between the data generating nodes; and

a processor configured to select an arrangement for an array code from a plurality of possible arrangements,

wherein the array code comprises a plurality of entries,

wherein each entry indicates the dependence of the parity symbols generated by a node on the data symbols received from other data generating nodes, and the arrangement of the array code indicates which entry corresponds to which data generating node of the wireless network, the arrangement of the array code being determined by;

assigning an entry of the array code to each data generating node in a manner that minimizes an outage probability of the wireless network, wherein the outage probability represents the probability that parity symbols cannot be formed by the plurality of data generating nodes and is based on the plurality of link quality estimates received by the controller, and

wherein the wireless interface is further configured to send an indication of the selected arrangement to the data generating nodes.

11. A controller according to claim 10, further comprising storage for the plurality of possible arrangements.

12. A controller according to claim 11, wherein the storage is configured to store a plurality of array codes and the processor is further configured to select an array code from the plurality of array codes.

13. A controller according to claim 10, wherein the wireless interface is further configured to send each data generating node an indication of the dependence according to the configured array code of the parity symbols stored on that data generating node on the data symbols stored on other data generating nodes.

14. A controller according to claim 10, wherein the wireless interface is further configured to send to each data generating node an indication of data generating nodes of the wireless network to which to send the data stored on that node.

15. A controller according to claim 10, wherein the indications of link quality estimates are internode error probabilities.

16. A controller according to claim 15 wherein the processor is further configured to identify a pair of nodes having the highest internode error probability and select an arrangement in which there is no dependence of parity symbols on data symbols between the identified pair of nodes.

17. A controller according to claim 16 wherein the processor is further configured to iteratively group nodes having the highest internode probability together to form a set of subgraphs and to determine the arrangement for the array code from a complement graph of the set of subgraphs.

18. A controller according to claim 15 wherein the processor is further configured to determine an outage probability for each of the plurality of possible arrangements and selecting the possible arrangement having the lowest outage probability.