Network channel access protocol-interference and load adaptive

• US 20020176396A1
• Filed: 04/15/2002
• Published: 11/28/2002
• Est. Priority Date: 04/18/2001
• Status: Active Grant

• Current Assignee: Trilliant Networks Incorporated
• Original Assignee: SkyPilot Networks Incorporated (Trilliant Networks Incorporated)
• Inventors: Bradley, Kirk Alton, Rich, Mark J., Hammel, Thomas
• Granted Patent: US 7,283,494 B2
• Time in Patent Office: Days
• US Class Current: 370/347
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04W 16/02 Resource partitioning among network components, e.g. reuse partitioning
• CPC Class Codes: H04W 16/06 Hybrid resource partitioning, e.g. channel borrowing
• CPC Class Codes: H04W 16/12 Fixed resource partitioning
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 16/24 Cell structures
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 72/0446 Resources in time domain, e.g. slots or frames
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 72/54 based on quality criteria
• CPC Class Codes: H04W 72/541 using the level of interference
• CPC Class Codes: H04W 72/542 using measured or perceived quality
• CPC Class Codes: H04W 72/56 based on priority criteria
• CPC Class Codes: H04W 72/569 of the traffic information
• CPC Class Codes: H04W 74/00 Wireless channel access
• CPC Class Codes: H04W 74/04 Scheduled access hybrid access H04W74/02
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

Network channel access protocol is disclosed. More particularly, a distributed, locally determined, channel access protocol that adapts to load, avoids interference and controls access by a group of nodes to a set of shared channels is disclosed. Shared channel space is divided into a number of communication slots that are repeated at a predetermined interval. Permission to use a slot to communicate between any two nodes is dynamically adjusted by the channel access protocol, which locally: (i) estimates load to neighboring nodes; (ii) allocates or deallocates slot usage to adapt to load and avoid interference; and (iii) asserts and advertises slot usage within an interference area about itself.

Claims

1. A method for determining communication slot allocation, comprising:

providing an array;

determining whether there is at least one conflict for a planned transmission at a first node;

amending the array in response to the at least one conflict identified at the first node;

determining whether there is at least one conflict for the planned transmission at a second node;

amending the array in response to the at least one conflict identified at the second node;

identifying first potential interference between the first node and a first other node within an interference area of the first node for the planned transmission;

amending the array in response to the potential interference identified;

identifying second potential interference between the second node and a second other node within an interference area of the second node for the planned transmission;

amending the array in response to the second potential interference identified;

identifying third potential interference which would mitigate against selecting at least one communication slot for allocation thereof for the planned transmission;

amending the array in response to the third potential interference identified; and

selecting the at least one communication slot using the array as amended for allocation of the at least one communication slot for the planned transmission.

2. The method of claim 1 wherein the array is frequencies by times.

3. The method of claim 1 wherein the first node is a transmitting node and the second node is a receiving node, the at least one conflict is a self-conflict, the first potential interference is intranetwork interference associated with the transmitting node, the second potential interference is intranetwork interference associated with the receiving node, and the third potential interference is external interference.

4. The method of claim 1 wherein the array is frequencies by times, and wherein the at least one conflict is a self-conflict, the first potential interference and the second potential interference are intranetwork interference, and the third potential interference is external interference.

5. A signal-bearing medium containing a program which, when executed by a processor in response to receiving a request to determine available communication slots, causes execution of a method comprising:

determining whether there is at least one conflict for a planned transmission between a first node and a second node;

amending an array in response to the at least one conflict identified;

identifying first potential interference between the first node and a first other node within an interference area of the first node for the planned transmission;

amending the array in response to the potential interference identified;

identifying second potential interference between the second node and a second other node within an interference area of the second node for the planned transmission;

amending the array in response to the second potential interference identified;

identifying third potential interference which would mitigate against selecting at least one communication slot for allocation thereof for the planned transmission;

amending the array in response to the third potential interference identified; and

selecting the at least one communication slot using the array as amended for allocation of the at least one communication slot for the planned transmission.

6. The method of claim 5 wherein the array is frequencies by times.

7. The method of claim 6 wherein the at least one conflict is a self-conflict, the first potential interference and the second potential interference are intranetwork interference, and the third potential interference is external interference.

8. A method for determining self-conflicts between a transmitting node and a receiving node, comprising:

providing an array;

obtaining a communication slot;

checking the transmitting node and the receiving node to determine if either or both is pre-allocated to transmit or receive during the communication slot; and

if either or both the transmitting node and the receiving node is pre-allocated to transmit or receive during the communication slot, determining priority of each pre-allocation against priority of transmission from the transmitting node to the receiving node.

9. The method of claim 8 further comprising if the priority of the transmission from the transmitting node to the receiving node is not greater than the priority of each pre-allocation, amending the array to indicate that the communication slot is not available.

10. The method of claim 9 further comprising checking for another communication slot.

11. The method of claim 8 further comprising obtaining each other communication slot until all communication slots have been checked for self-conflicts.

12. The method of claim 8 wherein the step of amending the array comprises marking all frequencies associated with the communication slot as unavailable.

15. The method of claim 14 further comprising if the power level is of sufficient strength to cause interference with the reception of the first node, amending the array to indicate that a frequency associated with the communication slot is unavailable.

16. The method of claim 15 further comprising obtaining another communication slot.

17. The method of claim 16 further comprising checking for a second node, not the transmitting node or the receiving node, to process.

20. The method of claim 19 further comprising if the power level is sufficient to at least likely cause interference with the reception of the receiving node, amending the array to indicate that a frequency for the communication slot is unavailable.

21. The method of claim 20 further comprising obtaining another communication slot.

22. The method of claim 21 further comprising replacing the first node with a second node.

25. The method of claim 24 further comprising allocating the portion of the channel.

26. The method of claim 24 further comprising asserting control of the portion of the channel.

27. The method of claim 26 wherein the asserting comprises advertising assertion of allocation of the portion of the channel to one or more neighboring nodes.

28. The method of claim 27 wherein the advertising to the one or more neighboring nodes is only by point-to-point communication.

29. The method of claim 27 wherein the advertising to the one or more neighboring nodes is only by point-to-multipoint communication.

30. The method of claim 27 wherein the advertising to the one or more neighboring nodes is only by broadcast communication.

31. The method of claim 27 wherein the advertising to the one or more neighboring nodes is by one or more of point-to-point communication, point-to-multipoint communication and broadcast communication.

32. The method of claim 27 further comprising using the assertion of allocation of the portion of the channel to update the collection of information as located at the one or more neighboring nodes.

33. The method of claim 27 further comprising re-advertising by the one or more neighboring nodes of the assertion of allocation of the portion of the channel to neighboring nodes of the one or more neighboring nodes.

34. The method of claim 33 further comprising using the re-advertising by the one or more neighboring nodes of the assertion of allocation of the portion of the channel to the neighboring nodes of the one or more neighboring nodes to update the collection of information as located at the neighboring nodes of the one or more neighboring nodes.

35. The method of claim 33 wherein the re-advertising to the neighboring nodes of the one or more neighboring nodes is only by point-to-point communication.

36. The method of claim 33 wherein the re-advertising to the neighboring nodes of the one or more neighboring nodes is only by point-to-multipoint communication.

37. The method of claim 33 wherein the re-advertising to the neighboring nodes of the one or more neighboring nodes is only by broadcast communication.

38. The method of claim 33 wherein the re-advertising to the neighboring nodes of the one or more neighboring nodes is by one or more of point-to-point communication, point-to-multipoint communication and broadcast communication.

39. The method of claim 33 further comprising repeating the re-advertising until all nodes within an interference area of the node are informed of the assertion of allocation of the portion of the channel.

40. The method of claim 39 further comprising using the assertion of allocation of the portion of the channel as advertised and re-advertised to update the collection of information as located at receiving nodes of the advertised and re-advertised assertion.

41. The method of claim 24 wherein the interference comprises intranetwork and external interference.

42. The method of claim 24 wherein the interference comprises self-conflict.

13. A signal-bearing medium containing a program which, when executed by a processor in response to receiving a call to determine available communication slots, causes execution of a method comprising:

providing an array;

obtaining a communication slot;

checking the transmitting node and the receiving node to determine if either or both is pre-allocated to transmit or receive during the communication slot; and

if either or both the transmitting node and the receiving node is pre-allocated to transmit or receive during the communication slot, determining priority of each pre-allocation against priority of transmission from the transmitting node to the receiving node.

14. A method for determining intranetwork conflicts for a planned transmission from a transmitting node to a receiving node, comprising:

providing an array;

obtaining a first node not the transmitting node or the receiving node;

obtaining a communication slot;

determining whether the first node is pre-allocated to receive during the communication slot;

if the first node is pre-allocated to receive during the communication slot, checking the pre-allocated priority of the first node against priority of the planned transmission; and

if the priority of the planned transmission is not greater than the pre-allocated priority of the first node, determining whether a power level for the planned transmission is of sufficient strength to interfere with reception during the communication slot of the first node.

18. A signal-bearing medium containing a program which, when executed by a processor in response to receiving a call to determine available communication slots, causes execution of a method comprising:

providing an array;

obtaining a neighbor node of the transmitting node or the receiving node;

obtaining a communication slot;

determining whether the neighbor node is pre-allocated to receive during the communication slot; and

if the neighbor node is pre-allocated to receive during the communication slot, checking the pre-allocated priority of the neighbor node against priority of the planned transmission; and

if the priority of the planned transmission is not greater than the pre-allocated priority of the neighbor node, determining whether a power level for the planned transmission is of sufficient strength to interfere with reception during the communication slot of the neighbor node.

19. A method for determining intranetwork conflicts for a planned transmission from a transmitting node to a receiving node, comprising:

providing an array;

obtaining a first node not the transmitting node or the receiving node;

obtaining a communication slot;

determining whether the first node is pre-allocated to transmit during the communication slot;

if the first node is pre-allocated to transmit during the communication slot, comparing priorities of the preallocated transmission and the planned transmission; and

if the priority of the planned transmission is not greater than the pre-allocated transmission priority, determining whether a power level for the pre-allocated transmission by the first node is at least likely to interfere with reception by the receiving node of the planned transmission.

23. A signal-bearing medium containing a program which, when executed by a processor in response to receiving a call to determine available communication slots, causes execution of a method comprising:

providing an array;

obtaining a neighbor node not the transmitting node or the receiving node;

obtaining a communication slot;

determining whether the neighbor node is pre-allocated to transmit during the communication slot;

if the neighbor node is pre-allocated to transmit during the communication slot, comparing priorities of the pre-allocated transmission and the planned transmission;

if the priority of the planned transmission is not greater than the pre-allocated transmission priority, determining whether a power level for the pre-allocated transmission by the neighbor node is at least likely to interfere with reception by the receiving node of the planned transmission.

24. A method for locally determining channel access to avoid interference for communicating from a node to another node in a network of nodes, comprising:

providing a collection of information to the node;

checking for potential interference using the collection of information; and

identifying a portion of a channel to avoid the interference.

43. A method for determining channel access at a node that adapts to load and avoids conflicts and interference for communicating from the node to another node in a network of nodes, comprising:

providing the node with a collection of information;

estimating an expected load on the node;

adjusting slot allocation in response to the expected load on the node;

identifying a slot that is not likely to cause interference; and

asserting allocation of the slot including advertising the slot allocation to neighboring nodes of the node.

44. The method of claim 43 wherein the node to the another node communication is only by point-to-point communication.

45. The method of claim 43 wherein the node to the another node communication is only by point-to-multipoint communication.

46. The method of claim 43 wherein the node to the another node communication is only by broadcast communication.

47. The method of claim 43 wherein the node to the another node communication is by one or more of point-to-point communication, point-to-multipoint communication and broadcast communication.

49. The method of claim 48 wherein the step of asserting further comprises advertising to neighboring nodes of the first node other than the second node.

50. The method of claim 48 wherein communication between the first node and the second node is only by point-to-point communication.

51. The method of claim 48 wherein communication between the first node and the second node is only by point-to-multipoint communication.

52. The method of claim 48 wherein communication between the first node and the second node is only by broadcast communication.

53. The method of claim 48 wherein communication between the first node and the second node is by one or more of point-to-point point communication, point-to-multipoint communication and broadcast communication.

48. A method for determining channel access at a first node that adapts to load and avoids conflicts and interference for communicating from the first node to a second node in a network of nodes, comprising:

providing the first node with a database;

determining a load on the first node;

determining if slot allocation needs adjustment in response to the load on the first node;

checking for potential conflicts using the database;

checking for potential interference within an interference area of the first node using the database;

allocating a slot which avoids the potential conflicts and the potential interference; and

asserting the slot allocation including advertising the slot allocation to the second node.

54. A method for determining channel access at a first node that adapts to load and avoids conflicts and interference for communicating from the first node to a second node in a network of nodes, comprising:

providing the first node with a database for the network of nodes;

adaptively determining load on the first node;

determining if slot allocation needs adjustment in response to the load on the first node;

adjusting the slot allocation in response to the load;

checking for conflicts using the database;

checking for interference within an interference area of the first node using the database;

identifying a slot which avoids the conflicts and the interference;

allocating the slot; and

asserting the slot allocation including advertising the slot allocation to the second node.

55. The method of claim 54 wherein the step of asserting further comprises advertising to neighboring nodes of the first node other than the second node.

56. The method of claim 55 wherein the advertising is only by point-to-point communication.

57. The method of claim 55 wherein the advertising is only by point-to-multipoint communication.

58. The method of claim 55 wherein the advertising is only by broadcast communication.

59. The method of claim 55 wherein the advertising is by one or more of point-to-point communication, point-to-multipoint communication and broadcast communication.

60. The method of claim 54 wherein communication between the first node and the second node is only by point-to-point communication.

61. The method of claim 54 wherein communication between the first node and the second node is only by point-to-multipoint communication.

62. The method of claim 54 wherein communication between the first node and the second node is only by broadcast communication.

63. The method of claim 54 wherein communication between the first node and the second node is by one or more of point-to-point communication, point-to-multipoint communication and broadcast communication.

64. A method for allowing shared channel access among nodes for communicating from a node to another node in a wireless mesh network, comprising:

providing nodes in the wireless mesh network; and

communicating between the nodes using only point-to-point communication.

65. The method of claim 64 further comprising adaptively modifying the shared channel access in response to changes in load.

66. The method of claim 64 further comprising identifying potential interference between the nodes of the wireless mesh network.

67. The method of claim 66 further comprising avoiding the interference identified.

68. The method of claim 67 further comprising adaptively modifying the shared channel access in response to changes in load.