Access protocol for wireless ad hoc networks using synchronous collision resolution

• US 20050190784A1
• Filed: 04/18/2005
• Published: 09/01/2005
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: SCR Networks LLC
• Original Assignee: John A. Stine
• Inventors: Stine, John A.
• Granted Patent: US 7,653,003 B2
• Time in Patent Office: Days
• US Class Current: 370/445
• CPC Class Codes: H04L 45/40 Wormhole routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 56/00 Synchronisation arrangements
• CPC Class Codes: H04W 74/0833 Random access procedures, e.g. with 4-step access
• 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

An ad hoc network organizes itself to provide communications without need for an a priori designated central control mechanism or base stations. Such self-organization is challenging in a multihop ad hoc network having member nodes that are highly mobile and widely distributed. A Synchronous Collision Resolution (SCR) protocol is well suited to provide efficient medium access control is such networks. SCR is an access protocol that archives high capacity collision free access using a signaling approach that creates a random cellular-like network after each signaling period. In use, the present invention provides quality of service and supports energy conservation for the mobile nodes.

Claims

1. A method of medium access control among nodes in an ad hoc wireless network comprising:

synchronizing the nodes to a common time;

synchronously arbitrating contention of nodes for access to a transmission channel during one or more signaling phases; and

authorizing the nodes that win an arbitration to use the transmission channel simultaneously.

2. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein synchronously arbitrating contention of nodes for access to a transmission channel during one or more signaling phases comprises:

applying a preemption rule to a node contending for access to a transmission channel during one of the one or more signaling phases; and

determining at the contending node whether the contending node survives the contention according to the preemption rule.

3. The method of medium access control among nodes in an ad hoc wireless network of claim 2, where in the preemption rule is selected from the group consisting of a first-to-assert rule and a last-to-assert rule.

4. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein synchronously arbitrating contention of nodes for access to a transmission channel during one or more signaling phases comprises:

applying a first preemption rule to a node contending for access to a transmission channel during a first signaling phase;

determining at the contending node whether the contending node survives the contention according to the first preemption rule;

if the contending node survives the contention according to the first preemption rule then applying a second preemption to the contending node for access to a transmission channel during a second signaling phase; and

determining at the contending node whether the contending node survives the contention according to the second preemption rule.

5. The method of medium access control among nodes in an ad hoc wireless network of claim 2, where in the first preemption rule and the second preemption rule are selected from the group consisting of a first-to-assert rule and a last-to-assert rule.

6. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the one or more signaling phases comprise one or more signaling slots.

7. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the one or more signaling slots occupy of equal time units.

8. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the one or more signaling slots occupy variable time units.

9. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein a node that wins an arbitration comprises a node that survives contention for access to a transmission channel during each of the one or more signaling phases.

10. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the method further comprises:

synchronizing the transmission of data packets from nodes that survive arbitration to destination nodes during the transmission channel.

11. The method of medium access control among nodes in an ad hoc wireless network of claim 10, wherein the method further comprises:

synchronizing the transmission of acknowledgement packets from destination nodes that receive data packets.

12. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the method further comprises determining whether a data packet will be received without collision prior to sending the data packet.

13. The method of medium access control among nodes in an ad hoc wireless network of claim 12, wherein determining whether a data packet will be received without collision prior to sending the data packet comprises:

synchronously sending request to send (RTS) messages from authorized nodes;

synchronously sending clear to send (CTS) messages from destination nodes in receipt of an RTS message; and

sending data packets from authorized nodes only in response to receipt of CTS messages.

14. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein the method further comprises instructing one or more of nodes that do not survive contention for access to a transmission channel during a signaling phase to echo a contention signal received from a node that survives arbitration.

15. The method of medium access control among nodes in an ad hoc wireless network of claim 14, wherein synchronously arbitrating contention of nodes for access to a transmission channel during one or more signaling phases comprises:

applying a preemption rule to a node contending for access to a transmission channel (the contending node) during one of the one or more signaling phases;

determining at the contending node whether the contending node survives the contention according to the preemption rule;

if the contending node survives contention according to the preemption rule, determining if the contending node receives an echoed contention signal; and

if the contending node does not receive an echoed contention signal, then determining that the contending node survives the signaling phase.

16. The method of medium access control among nodes in an ad hoc wireless network of claim 1, wherein further comprising:

determining whether a node is a participant in a packet exchange;

if the node is not a participant, scheduling a wakeup interval for the non-participating node; and

entering at the non-participating node a dozing state.

17. The method of medium access control among nodes in an ad hoc wireless network of claim 16 wherein the wakeup interval comprises a number of transmission slots.

18. The method of medium access control among nodes in an ad hoc wireless network of claim 17 wherein determining whether a node is a participant in a packet exchange comprises listening for signaling from a contending node.

19. The method of medium access control among nodes in an ad hoc wireless network of claim 16 wherein entering at the non-participating a dozing state comprises:

coordinating with a neighboring node for the receipt of packet data units directed to the non-participating node;

broadcasting from the non-participating node a wakeup interval and the address of the neighboring node to receive packet data units for the non-participating node; and

wherein the method further comprises;

while the non-participating node is in the dozing state, receiving at the neighboring node the packet data units for the non-participating node; and

upon leaving the dozing state, receiving at the non-participating node the packet data units received by the neighboring node.

20. The method of medium access control among nodes in an ad hoc wireless network of claim 19 wherein the method further comprises:

after leaving the dozing state, listening at the non-participating node for a priority signal;

if no priority signal is heard, broadcasting from the non-participating node a wakeup interval and the address of the neighboring node to receive packet data units for the non-participating node; and

reentering the dozing state.

21. A method of establishing priority of access among nodes in an ad hoc wireless network comprising:

synchronizing the nodes to a common time;

assigning a service priority to a priority signaling slot within a priority phase based on a packet differentiator;

permitting contending nodes having packets to transmit comprising the packet differentiator to transmit a contention signal in the priority signaling slot based on the packet differentiator of a payload packet;

applying a first-to-assert preemption rule to the priority phase; and

determining at the contending nodes whether the contending node survived the priority phase contention.

22. The method of medium access control among nodes in an ad hoc wireless network of claim 21, wherein the packet differentiator is selected from the group consisting of a time to live, a network application, a packet'"'"'s purpose, a packet source, and a packet destination.

23. A method of managing stream-based packets among nodes in an ad hoc wireless network comprising:

synchronizing the nodes to a common time;

assigning a service priority to a quality-of-service (QoS) signaling slot within a priority phase based on a packet differentiator;

synchronously arbitrating contention of nodes within the QoS signaling slot for access to a transmission channel within a constant bit rate (CBR) frame during the priority signaling phase;

determining at the contending nodes whether the contending node survived the priority phase contention within the QoS signaling slot; and

if a contending node survived the priority phase contention, then authorizing the surviving contending node to transmit in the nth-slot in the CBR frame.

24. The method of managing stream-based traffic among nodes in an ad hoc wireless network of claim 23, wherein the packet differentiator is selected from the group consisting of a time to live, a network application, a packet'"'"'s purpose, a packet source, and a packet destination.

25. The method of managing stream-based traffic among nodes in an ad hoc wireless network of claim 23, wherein the priority phase further comprises a CBR slot and the method further comprises:

allowing the node with a first packet in a stream to signal using the QoS signaling slot;

allowing surviving contending nodes that successfully exchange a packet in the CBR frame to signal in the CBR slot; and

authorizing the surviving contending nodes that transmit in the CBR frame to transmit in the nth-slot of the next CBR frame.

26. The method of managing stream-based traffic among nodes in an ad hoc wireless network of claim 25, wherein the network further comprises a signaling phase and wherein the method further comprises:

determining at a destination node that it is a recipient of a CBR transmission from a surviving node;

simultaneously sending an assertion signal from the surviving node and from the destination node during a cooperative signaling slot of the signaling phase; and

authorizing the surviving node and the destination node to use the signaling slot thereby assuring only the surviving node and destination node survive the signaling phase.

27. A method of establishing receiver channels in an ad hoc wireless network comprising:

obtaining at a home node a channel selection of neighboring nodes within range of the home node'"'"'s receiver;

selecting a peer-to-peer receiver channel at the home node;

determining whether the peer-to-peer receiver channel selected by the home node is the peer-to-peer receiver channel selected by a neighboring node;

if the peer-to-peer receiver channel selected by the home node is not the peer-to-peer receiver channel selected by a neighboring node, then using the received channel selected by the home node; and

if the peer-to-peer receiver channel selected by the home node is the peer-to-peer receiver channel selected by a neighboring node, then selecting an unused peer-to-peer receiver channel.

28. The method of establishing peer-to-peer receiver channels in an ad hoc wireless network of claim 27, wherein the method further comprises, if the peer-to-peer receiver channel selected by the home node is the peer-to-peer receiver channel selected by a neighboring node, and if there are no unused peer-to-peer receiver channels, then applying a channel selection rule to select an in-use peer-to-peer receiver channel at the home node.

29. The method of establishing receiver channels in an ad hoc wireless network of claim 27, wherein the method further comprises broadcasting from the home node the peer-to-peer receiver channel selected by the home node.

30. The method of establishing receiver channels in an ad hoc wireless network of claim 27, wherein the home node further comprises a broadcast receiver channel and wherein the method further comprises:

listening at the home node for contention signals from neighboring nodes;

determining whether the contention signals are indicative of a broadcast communication or a peer-to-peer communication;

if the contention signals are indicative of a broadcast communication, then selecting at the home node the broadcast receiver channel; and

if the contention signals are indicative of a peer-to-peer communication then selecting at the home node the peer-to-peer receiver channel.

31. The method of establishing receiver channels in an ad hoc wireless network of claim 29, further comprises:

determining at a sending node the peer-to-peer channel selected by the home node; and

transmitting a packet to the home node using the peer-to-peer channel selected by the home node from the sending node.