Demand-driven prioritized data structure

• US 8,908,530 B2
• Filed: 08/12/2010
• Issued: 12/09/2014
• Est. Priority Date: 11/27/2006
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: TTI Inventions C LLC (Intellectual Ventures LLC)
• Inventors: Lau, Richard, Kim, Heechang, Siegell, Bruce
• Primary Examiner(s): PATEL, CHANDRAHAS B
• Application Number:
  US12/855,359
• Publication Number:
  US 20100302970A1
• Time in Patent Office: 1,580 Days
• Field of Search: 370/238, 709/238, 333/187, 333/199, 333/189
• US Class Current: 370/238
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2433 Allocation of priorities to traffic types
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system and method for optimizing the efficiency of data sharing among a set of radio nodes in a radio environment is provided. The technique includes identifying a data unit and assigning it a class, identifying a connectivity type, computing a significance factor based on connectivity type and assigned class, mapping the significance factor to a priority factor, and scheduling output of the data unit based on the priority factor. A scheduler algorithm can be used for scheduling output. The class can be assigned based on which nodes of the set of radio nodes possess copies of the data unit at a given time. An arbitration process can be used to determine the priority factor. A significance factor weighting algorithm, based on how many nodes will be receiving the data and on how much a node needs the data, can be used to determine the significance factor.

Claims

1. A method for optimizing efficiency of data sharing among a plurality of radio nodes in a radio environment, the method comprising:

mapping one or more data units stored in a first node to a first digest, wherein the plurality of radio nodes comprise the first node and one or more second nodes;

broadcasting the first digest to at least one node of the one or more second nodes;

comparing the first digest to at least one second digest from at least one node of the one or more second nodes to determine significance weighting factors for the one or more data units; and

broadcasting at least one of the one or more data units to at least one of the one or more second nodes according to a schedule of significance factors based at least in part upon the significance weighting factors and connectivity among the plurality of radio nodes, the connectivity comprising at least one of proximity of radio nodes to others of the plurality of radio nodes or channel conditions among the plurality of radio nodes, wherein the schedule effects broadcasting at higher priorities the at least one of the one or more data units to radio nodes having a greater number of radio nodes connected thereto within a predetermined number of radio hops.

2. The method of claim 1 wherein mapping the one or more data units stored in the first node to the first digest comprises mapping the one or more data units stored in the first node to a first data map where the one or more data units are arranged according to at least one of a grid location, a time unit, or position data.

3. The method of claim 1 wherein comparing the first digest to the at least one second digest comprises comparing the first digest to the at least one second digest based at least in part on particular data units stored at individual ones of the plurality of radio nodes.

4. The method of claim 1 further comprising scheduling broadcasting of the at least one of the one or more data units using a scheduler algorithm.

5. The method of claim 1 further comprising mapping the significance weighting factors for respective data units of the one or more data units to a priority factor.

6. The method of claim 5 wherein the mapping the significance weighting factors for the respective data units of the one or more data units to the priority factor further comprises performing an arbitration process to determine the priority factor.

7. The method of claim 1 further comprising identifying a connectivity type between the first node and at least one node of the one or more second nodes, wherein the connectivity type comprises at least one of a topology of the plurality of radio nodes or a transmission rate among the plurality of radio nodes.

8. A non-transitory computer readable medium having instructions stored thereon, the instructions configured to cause a device to perform operations comprising:

mapping one or more data units stored in a first node to a first digest, wherein the plurality of radio nodes comprise the first node and one or more second nodes;

broadcasting the first digest to at least one node of the one or more second nodes;

comparing the first digest to at least one second digest from at least one node of the one or more second nodes to determine significance weighting factors for the one or more data units; and

broadcasting at least one of the one or more data units to at least one of the one or more second nodes according to a schedule of significance factors based at least in part upon the significance weighting factors and connectivity among the plurality of radio nodes, the connectivity comprising at least one of proximity of radio nodes to others of the plurality of radio nodes or channel conditions among the plurality of radio nodes, wherein the schedule effects broadcasting at higher priorities the at least one of the one or more data units to radio nodes having a greater number of radio nodes connected thereto within a predetermined number of radio hops.

9. The non-transitory computer readable medium of claim 8 wherein mapping the one or more data units stored in the first node to the first digest comprises mapping the one or more data units stored in the first node to a first data map where the one or more data units are arranged according to at least one of a grid location, a time unit, or position data.

10. The non-transitory computer readable medium of claim 8 wherein comparing the first digest to the at least one second digest comprises comparing the first digest to the at least one second digest based at least in part on particular data units stored at individual ones of the plurality of radio nodes.

11. The non-transitory computer readable medium of claim 8 wherein the operations further comprise scheduling broadcasting of the at least one of the one or more data units using a scheduler algorithm.

12. The non-transitory computer readable medium of claim 8 wherein the operations further comprise mapping the significance weighting factors for respective data units of the one or more data units to a priority factor.

13. The non-transitory computer readable medium of claim 12 wherein the mapping the significance weighting factors for the respective data units of the one or more data units to the priority factor further comprises performing an arbitration process to determine the priority factor.

14. The non-transitory computer readable medium of claim 8 wherein the operations further comprise identifying a connectivity type between the first node and at least one node of the one or more second nodes, wherein the connectivity type comprises at least one of a topology of the plurality of radio nodes or a transmission rate among the plurality of radio nodes.

15. A radio node comprising:

a memory;

a communication device;

a processing device, in communication with the memory and the communication device, configured to;

map one or more data units stored in the memory to a local digest;

broadcast the local digest using the communication device to at least one node in a plurality of radio nodes, the plurality of radio nodes comprising the radio node and one or more second radio nodes;

receive a remote digest from at least one node of the one or more second radio nodes using the communication device;

compare the remote digest and the local digest to determine significance weighting factors for the one or more data units; and

broadcast at least one of the one or more data units using the communication device to at least one node of the second radio nodes according to a schedule of significance factors based at least in part upon the significance weighting factors and connectivity among the plurality of radio nodes, the connectivity comprising at least one of proximity of radio nodes to others of the plurality of radio nodes and channel conditions among the plurality of radio nodes, wherein the schedule effects broadcasting at higher priorities the at least one of the one or more data units to radio nodes having a greater number of radio nodes connected thereto within a predetermined number of radio hops.

16. The radio node of claim 15 wherein the local digest comprises a data map where the one or more data units are arranged according to at least one of a grid location, a time unit, or position data.

17. The radio node of claim 15 wherein the significance weighting factors are based at least in part on particular data units stored at individual ones of the plurality of radio nodes.

18. The radio node of claim 15 wherein the processing device is configured to determine the schedule of significance factors according to a scheduler algorithm.

19. The radio node of claim 15 wherein the one or more data units comprises a locally measured data type.

20. The radio node of claim 19 wherein the locally measured data type comprises at least one of SNR from a specific radio source, radio link SNR between nodes, or GPS location at a given time.