JAMMING GRAPH AND ITS APPLICATION IN NETWORK RESOURCE ASSIGNMENT

• US 20090310554A1
• Filed: 06/11/2009
• Published: 12/17/2009
• Est. Priority Date: 06/16/2008
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Sun, Jing, Ji, Tingfang, Khandekar, Aamod D.
• Granted Patent: US 8,559,908 B2
• Time in Patent Office: Days
• US Class Current: 370/329
• CPC Class Codes: H04L 5/0007 the frequencies being orthogonal, e.g. OFDM(A), DMT
• CPC Class Codes: H04L 5/0032 Distributed allocation, i.e. involving a plurality of allocating devices, each making partial allocation
• CPC Class Codes: H04L 5/0071 Allocation based on fairness other than the proportional kind
• CPC Class Codes: H04W 16/06 Hybrid resource partitioning, e.g. channel borrowing
• CPC Class Codes: H04W 16/10 Dynamic resource partitioning
• CPC Class Codes: H04W 72/20 Control channels or signalling for resource management

Abstract

A wireless communication network uses backhaul negotiation based upon static and dynamic resource assignment on jamming graphs. Static reuse factor design methods including fractional frequency reuse (FFR) are addressed. The jamming graph is used to summarize the interfering relationship between transmitters (nodes in the jamming graph). Negotiation-based algorithm is used to arrive at a static resource assignment so that a large reuse factor can be achieved while jamming scenario can be avoided. As a result of such algorithm, each transmitter is assigned some resources, over which traffic transmission can be done instantaneously to reduce the packet delay for short packets. Based on the result of static resource negotiation algorithm, a dynamic resource algorithm can be run, such that the resources assigned to different nodes can be share in a bursty traffic scenario to further reduce packet delay for larger packet size cases, while jamming be also avoided.

Claims

1. A method for allocation of wireless resources between nodes, comprising:

employing a processor executing computer executable instructions stored on a computer readable storage medium to implement the following acts;

determining at least one over-the-air resource used by a node and used by neighboring nodes of a neighborhood; and

negotiating with a neighboring node to assign resources without shared resource use between a pair of nodes in a jamming relationship.

2. The method of claim 1, further comprising maintaining a jamming graph that links nodes in the neighborhood based upon a jamming relationship between respective pairs of nodes.

3. The method of claim 1, further comprising receiving a report via backhaul signaling indicating that the selected node is jamming another node in the neighborhood.

4. The method of claim 1, further comprising generating a report indicating that the selected node is jamming another node in the neighborhood.

5. The method of claim 1, further comprising determining that a change in the neighborhood has occurred comprising a selected one of a group consisting of a node joining the jamming graph, a new branch being added between existing nodes in the jamming graph, a branch being removed from the jamming graph, and a traffic pattern change.

6. The method of claim 1, further comprising:

determining that resources being used interfere with the same resources being used by a neighboring node; and

negotiating to divide the resources with the neighboring node to resolve confliction.

7. The method of claim 1, further comprising:

determining that resources are not being used by any nodes in the neighborhood;

reporting to the nodes in the neighborhood a request to use the resources; and

transmitting data packets using the requested resources in response to not receiving any denials of the use.

8. The method of claim 1, further comprising accessing a report indicating that a change has occurred in the neighborhood comprising an unfair resource utilization.

9. The method of claim 8, further comprising maximizing an objective function of a resource allocation algorithm.

10. The method of claim 1, further comprising generating a node-based jamming graph that links pairs of nodes that serve or jam the same terminal in order to negotiate reallocation of resources with the neighboring node.

11. The method of claim 10, further comprising:

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

12. The method of claim 11, further comprising:

selecting a jamming graph having nodes with undecided resources;

selecting an undecided node in the selected jamming graph;

generating first and second derivative jamming graphs with the first having the node set to use the resources and the second having the node set to not use the resources;

discarding the first derivative graph in response to determining that the selected node causes jamming when using the resources by referencing the jamming graph;

setting another undecided node in the neighborhood to use the resources in response to determining that the another undecided node is not directly connected to yet another undecided node;

removing any jamming graph covered by another jamming graph; and

iterating to achieve a resource assignment pattern for the neighborhood of nodes.

13. The method of claim 1, further comprising optimizing selection of a resource assignment pattern that maximizes average reuse factor.

14. A computer program product for allocation of wireless resources between nodes, comprising:

computer readable storage medium having stored thereon the following computer executable components;

a first set of instructions for determining at least one over-the-air resource used by a node and used by neighboring nodes of a neighborhood;

a second set of instructions for

negotiating with a neighboring node to assign resources without shared resource use between a pair of nodes in a jamming relationship.

15. An apparatus for allocation of wireless resources between nodes, comprising:

at least one processor;

at least one computer readable storage medium storing computer executable instructions that when executed by the at least one processor implement components comprising;

means for determining at least one over-the-air resource used by a node and used by neighboring nodes of a neighborhood; and

means for negotiating with a neighboring node to assign resources without shared resource use between a pair of nodes in a jamming relationship.

16. An apparatus for allocation of wireless resources between nodes, comprising:

a transmitter for transmitting data packet communication to a served terminal;

a receiver for receiving data packet communication from the served terminal; and

a backhaul communication component for determining at least one over-the-air resource used by a node and used by neighboring nodes of a neighborhood, and for negotiating with a neighboring node to assign resources use without shared resource use between a pair of nodes in a jamming relationship.

17. The apparatus of claim 16, wherein the backhaul communication component is further for maintaining a jamming graph that links nodes in the neighborhood based upon a jamming relationship between respective pairs of nodes.

18. The apparatus of claim 16, wherein the backhaul communication component is further for receiving the report from a neighboring node via backhaul signaling indicating that the selected node is jamming another node in the neighborhood.

19. The apparatus of claim 16, wherein the receiver component is further for receiving the report from a served terminal indicating that the selected node is jamming another node in the neighborhood.

20. The apparatus of claim 16, wherein the backhaul communication component is further for generating the report indicating that the selected node is jamming another node in the neighborhood.

21. The apparatus of claim 16, wherein the backhaul communication component is further for determining a change in the neighborhood has occurred comprising a selected one of a group consisting of a node joining the jamming graph, a new branch being added between existing nodes in the jamming graph, a branch being removed from the jamming graph, and a traffic pattern change.

22. The apparatus of claim 16, wherein the backhaul communication component is further for,

determining that resources being used interfere with the same resources being used by a neighboring node;

and

negotiating to divide the resources with the neighboring node to resolve confliction.

23. The apparatus of claim 16, wherein the backhaul communication component is further for,

determining that resources are not being used by any nodes in the neighborhood;

reporting to the nodes in the neighborhood a request to use the resources; and

transmitting data packets using the requested resources in response to not receiving any denials of the use.

24. The apparatus of claim 16, wherein the backhaul communication component is further for accessing a report indicating that a change has occurred in the neighborhood comprising an unfair resource utilization.

25. The apparatus of claim 24, wherein the backhaul communication component is further for maximizing an objective function of a resource allocation algorithm.

26. The apparatus of claim 16, wherein the backhaul communication component is further for generating a node-based jamming graph that links pairs of nodes that serve or jam the same terminal in order to negotiate reallocation of resources with the neighboring node.

27. The apparatus of claim 26, wherein the backhaul communication component is further for,

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

28. The apparatus of claim 27, wherein the backhaul communication component is further for,

selecting a jamming graph having nodes with undecided resources;

selecting an undecided node in the selected jamming graph;

generating first and second derivative jamming graphs with the first having the node set to use the resources and the second having the node set to not use the resources;

discarding the first derivative graph in response to determining that the selected node causes jamming when using the resources by referencing the jamming graph;

setting another undecided node in the neighborhood to use the resources in response to determining that the another undecided node is not directly connected to yet another undecided node;

removing any jamming graph covered by another jamming graph; and

iterating to achieve a resource assignment pattern for the neighborhood of nodes.

29. The apparatus of claim 16, wherein the backhaul communication component is further for optimizing selection of a resource assignment pattern that maximizes average reuse factor.

30. A method for centralized static allocation of wireless resources between nodes, comprising:

employing a processor executing computer executable instructions stored on a computer readable storage medium to implement the following acts;

defining a wireless communication network comprising a plurality of nodes that serve respective terminals;

determining nodes that are linked based upon serving or jamming a selected terminal; and

assigning resources by backhaul signaling to the plurality of nodes for efficient resource use without shared resource use between a pair of nodes in a jamming relationship.

31. The method of claim 30, further comprising receiving a report indicating that the selected node is jamming another node in the neighborhood.

32. The method of claim 30, further comprising generating a report indicating that the selected node is jamming another node in the neighborhood.

33. The method of claim 30, further comprising maintaining a jamming graph that links nodes in the neighborhood based upon a jamming relationship between respective pairs of nodes.

34. The method of claim 33, further comprising:

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

35. The method of claim 34, further comprising:

selecting a jamming graph having nodes with undecided resources;

selecting an undecided node in the selected jamming graph;

generating first and second derivative jamming graphs with the first having the node set to use the resources and the second having the node set to not use the resources;

discarding the first derivative graph in response to determining that the selected node causes jamming when using the resources by referencing the jamming graph;

setting another undecided node in the neighborhood to use the resources in response to determining that the another undecided node is not directly connected to yet another undecided node;

removing any jamming graph covered by another jamming graph; and

iterating to achieve a resource assignment pattern for the neighborhood of nodes.

36. The method of claim 35, further comprising optimizing selection of a resource assignment pattern that maximizes average reuse factor.

37. The method of claim 30, further comprising reassigning a resource in response to determining unfair resource utilization.

38. The method of claim 30, further comprising maximizing an objective function of a resource allocation algorithm.

39. A computer program product for centralized static allocation of wireless resources between nodes, comprising:

computer readable storage medium having stored thereon the following computer executable components;

a first set of instructions for defining a wireless communication network comprising a plurality of nodes that serves respective terminals;

a second set of instructions for determining nodes that are linked based upon serving or jamming a selected terminal; and

a third set of instructions for assigning resources by backhaul signaling to the plurality of nodes for efficient resource use without shared resource use between a pair of nodes in a jamming relationship.

40. An apparatus for centralized static allocation of wireless resources between nodes, comprising:

at least one processor;

at least one computer readable storage medium storing computer executable instructions that when executed by the at least one processor implement components comprising;

means for defining a wireless communication network comprising a plurality of nodes that serve respective terminals;

means for determining nodes that are linked based upon serving or jamming a selected terminal; and

means for assigning resources by backhaul signaling to the plurality of nodes for efficient resource use without shared resource use between a pair of nodes in a jamming relationship.

41. An apparatus for centralized static allocation of wireless resources between nodes, comprising:

a transmitter for transmitting data packet communication to a served terminal;

a receiver for receiving data packet communication from the served terminal; and

a backhaul communication component for defining a wireless communication network comprising a plurality of nodes that serve respective terminals, for determining nodes that are linked based upon serving or jamming a selected terminal, and for assigning resources by backhaul signaling to the plurality of nodes for efficient resource use without shared resource use between a pair of nodes in a jamming relationship.

42. The apparatus of claim 41, wherein the backhaul communication component is further for receiving a report indicating that the selected node is jamming another node in the neighborhood.

43. The apparatus of claim 41, wherein the receiver is further for receiving a report from a served terminal indicating that the selected node is jamming another node in the neighborhood.

44. The apparatus of claim 41, wherein the backhaul communication component is further for generating a report indicating that the selected node is jamming another node in the neighborhood.

45. The apparatus of claim 41, wherein the backhaul communication component is further for maintaining a jamming graph that links nodes in the neighborhood based upon a jamming relationship between respective pairs of nodes.

46. The apparatus of claim 45, wherein the backhaul communication component is further for,

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

47. The apparatus of claim 46, wherein the backhaul communication component is further for,

selecting a jamming graph having nodes with undecided resources;

selecting an undecided node in the selected jamming graph;

generating first and second derivative jamming graphs with the first having the node set to use the resources and the second having the node set to not use the resources;

discarding the first derivative graph in response to determining that the selected node causes jamming when using the resources by referencing the jamming graph;

setting another undecided node in the neighborhood to use the resources in response to determining that the another undecided node is not directly connected to yet another undecided node;

removing any jamming graph covered by another jamming graph; and

iterating to achieve a resource assignment pattern for the neighborhood of nodes.

48. The apparatus of claim 47, wherein the backhaul communication component is further for optimizing selection of a resource assignment pattern that maximizes average reuse factor.

49. The apparatus of claim 41, wherein the backhaul communication component is further for reassigning a resource in response to determining unfair resource utilization.

50. The apparatus of claim 48, wherein the backhaul communication component is further for maximizing an objective function of a resource allocation algorithm.

51. A method for dynamically requesting grant of resources in order to transmit data packet communication, comprising:

employing a processor executing computer executable instructions stored on a computer readable storage medium to implement the following acts;

receiving a data packet for transmission at a first node in communication with a neighboring node of a network neighborhood;

accessing information for over-the-air resources assigned to the neighboring node;

requesting a temporary grant for the resources from the neighboring node;

receiving a grant for the resources from the neighboring node; and

transmitting the data packet using the granted resources.

52. The method of claim 51, further comprising selecting a resource to request in response to determining that the resource is underutilized.

53. The method of claim 51, further comprising:

synchronizing time across nodes in the neighborhood;

time stamping backhaul messages at time of transmission between nodes in the neighborhood; and

estimating backhaul delay based upon synchronized time of receipt of a time stamped backhaul message.

54. The method of claim 53, further comprising:

determining a time required to transmit a data packet; and

requesting a grant of resources from a neighboring node in response to determining that estimated backhaul delay is less than the time required to transmit.

55. The method of claim 51, further comprising:

receiving a request for grant of resources; and

granting or rejecting request based upon local traffic conditions.

56. The method of claim 51, further comprising:

determining a time required to transmit a data packet; and

requesting a grant of resources from a neighboring node including grant duration based upon the determined time required to transmit.

57. The method of claim 51, further comprising:

receiving a request for grant of resources including a grant duration; and

granting the request resources with a start time and an expiration time.

58. The method of claim 57, further comprising setting the start and expiration times to accommodate the requested grant duration.

59. The method of claim 57, further comprising:

setting the start and expiration times to less than the requested grant duration;

receiving a request to extend the grant; and

granting the extension to the expiration time.

60. The method of claim 57, further comprising requesting recall of the granted resources before the expiration time.

61. The method of claim 51, further comprising:

determining that multiple nodes in the neighborhood own the resources; and

requesting the resources from each of the multiple nodes.

62. The method of claim 61, further comprising releasing any resource grants received if one node of the multiple nodes rejects the grant request.

63. The method of claim 51, further comprising:

receiving a grant of resources including an expiration time;

completing transmission before the expiration time; and

backhaul signaling release of the granted resources.

64. The method of claim 63, further comprising:

estimating backhaul delay to a node that granted the resources;

estimating time to complete transmission; and

backhaul signaling release of the granted resources before transmission completion based upon the estimated backhaul delay and estimated time to complete.

65. The method of claim 51, further comprising:

receiving a persistent grant of resources with an expiration time;

completing a first transmission using the granted resources before the expiration time; and

maintaining the persistent grant without releasing in case another need arises for transmission.

66. The method of claim 51, further comprising:

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

67. The method of claim 66, further comprising:

granting resources to a node; and

informing other nodes in the neighborhood of the granted resources to avoid three-hop jamming.

68. The method of claim 51, further comprising granting a persistent grant of resources to a first node without having received a request for the grant.

69. The method of claim 68, further comprising:

receiving a request for a grant of resources from a second node;

granting the requested resources; and

granting the persistent grant of resources to the first node in response to determining that the first and second nodes are not linked on the jamming graph.

70. The method of claim 51, further comprising:

maintaining and disseminating a neighbor list to nodes in the neighborhood;

receiving a respective neighbor list from nodes in the neighborhood; and

determining that a grant received from a node in the neighborhood is sufficient based upon the plurality of maintained and received neighbor lists.

71. The method of claim 51, further comprising:

receiving a first request with a first priority for grant of resources from a first node;

receiving a second request with a second priority for grant of resources from a second node; and

granting the first request and rejecting the second request in response to the first priority being higher than the second priority.

72. The method of claim 51, further comprising reassigning a resource in response to determining unfair resource utilization.

73. The method of claim 51, further comprising maximizing an objective function of a resource allocation algorithm.

74. A computer program product for dynamically requesting grant of resources in order to transmit data packet communication, comprising:

at least one computer readable storage medium storing computer executable instructions that when executed by at least one processor implement components comprising;

a first set of instructions for receiving a data packet for transmission at a first node in communication with a neighboring node of a network neighborhood;

a second set of instructions for accessing information for over-the-air resources assigned to the neighboring node;

a third set of instructions for requesting a temporary grant for the resources from the neighboring node;

a fourth set of instructions for receiving a grant for the resources from the neighboring node; and

a fifth set of instructions for transmitting the data packet using the granted resources.

75. An apparatus for dynamically requesting grant of resources in order to transmit data packet communication, comprising:

means for employing a processor executing computer executable instructions stored on a computer readable storage medium to implement the following acts;

means for receiving a data packet for transmission at a first node in communication with a neighboring node of a network neighborhood;

means for accessing information for over-the-air resources assigned to the neighboring node;

means for requesting a temporary grant for the resources from the neighboring node;

means for receiving a grant for the resources from the neighboring node; and

means for transmitting the data packet using the granted resources.

76. An apparatus for dynamically requesting grant of resources in order to transmit data packet communication, comprising:

a receiver for receiving a data packet for transmission at a first node in communication with a neighboring node of a network neighborhood;

a computer readable storage medium for accessing information for over-the-air resources assigned to the neighboring node;

a backhaul communication component for requesting a temporary grant for the resources from the neighboring node and for receiving a grant for the resources from the neighboring node; and

a transmitter for transmitting the data packet using the granted resources.

77. The apparatus of claim 76, wherein the selecting a resource to request in response to determining that the resource is underutilized.

78. The apparatus of claim 76, wherein the backhaul communication component is further for, synchronizing time across nodes in the neighborhood;

time stamping backhaul messages at time of transmission between nodes in the neighborhood; and

estimating backhaul delay based upon synchronized time of receipt of a time stamped backhaul message.

79. The apparatus of claim 78, wherein the backhaul communication component is further for:

determining a time required to transmit a data packet; and

requesting a grant of resources from a neighboring node in response to determining that estimated backhaul delay is less than the time required to transmit.

80. The apparatus of claim 76, wherein the backhaul communication component is further for:

receiving a request for grant of resources; and

granting or rejecting request based upon local traffic conditions.

81. The apparatus of claim 76, wherein the backhaul communication component is further for:

determining a time required to transmit a data packet; and

requesting a grant of resources from a neighboring node including grant duration based upon the determined time required to transmit.

82. The apparatus of claim 76, wherein the backhaul communication component is further for:

receiving a request for grant of resources including a grant duration; and

granting the request resources with a start time and an expiration time.

83. The apparatus of claim 82, wherein the backhaul communication component is further for setting the start and expiration times to accommodate the requested grant duration.

84. The apparatus of claim 82, wherein the backhaul communication component is further for:

setting the start and expiration times to less than the requested grant duration;

receiving a request to extend the grant; and

granting the extension to the expiration time.

85. The apparatus of claim 82, wherein the backhaul communication component is further for requesting recall of the granted resources before the expiration time.

86. The apparatus of claim 76, wherein the backhaul communication component is further for:

determining that multiple nodes in the neighborhood own the resources; and

requesting the resources from each of the multiple nodes.

87. The apparatus of claim 86, wherein the backhaul communication component is further for releasing any resource grants received if one node of the multiple nodes rejects the grant request.

88. The apparatus of claim 76, wherein the backhaul communication component is further for receiving a grant of resources including an expiration time;

the transmitter is further for completing transmission before the expiration time; and

the backhaul communication component is further for backhaul signaling release of the granted resources.

89. The apparatus of claim 88, wherein the backhaul communication component is further for:

estimating backhaul delay to a node that granted the resources;

estimating time to complete transmission; and

backhaul signaling release of the granted resources before transmission completion based upon the estimated backhaul delay and estimated time to complete.

90. The apparatus of claim 76, wherein the backhaul communication component is further for:

receiving a persistent grant of resources with an expiration time;

completing a first transmission using the granted resources before the expiration time; and

maintaining the persistent grant without releasing in case another need arises for transmission.

91. The apparatus of claim 76, wherein the backhaul communication component is further for:

determining a node association that links terminals to a respective node that serves each terminal and links any terminal to a node that causes jamming;

determining a terminal-based jamming graph that link pairs of terminals that can receive the same node either in a serving capacity or a jamming capacity;

determining a node based jamming graph that links pairs of nodes that serve or jam the same terminal; and

assigning resources for a jamming-free condition wherein a given resource is not assigned to connected nodes in a jamming graph.

92. The apparatus of claim 91, wherein the backhaul communication component is further for:

granting resources to a node; and

informing other nodes in the neighborhood of the granted resources to avoid three-hop jamming.

93. The apparatus of claim 76, wherein the backhaul communication component is further for granting a persistent grant of resources to a first node without having received a request for the grant.

94. The apparatus of claim 93, wherein the backhaul communication component is further for:

receiving a request for a grant of resources from a second node;

granting the requested resources; and

granting the persistent grant of resources to the first node in response to determining that the first and second nodes are not linked on the jamming graph.

95. The apparatus of claim 76, wherein the backhaul communication component is further for:

maintaining and disseminating a neighbor list to nodes in the neighborhood;

receiving a respective neighbor list from nodes in the neighborhood; and

determining that a grant received from a node in the neighborhood is sufficient based upon the plurality of maintained and received neighbor lists.

96. The apparatus of claim 76, wherein the backhaul communication component is further for:

receiving a first request with a first priority for grant of resources from a first node;

receiving a second request with a second priority for grant of resources from a second node; and

granting the first request and rejecting the second request in response to the first priority being higher than the second priority.

97. The apparatus of claim 76, wherein the backhaul communication component is further for reassigning a resource in response to determining unfair resource utilization.

98. The apparatus of claim 76, wherein the backhaul communication component is further for maximizing an objective function of a resource allocation algorithm.