Access protocol for wireless ad hoc networks using synchronous collision resolution

• US 7,653,003 B2
• Filed: 04/18/2005
• Issued: 01/26/2010
• Est. Priority Date: 03/21/2002
• Status: Active Grant

• Current Assignee: SCR Networks LLC
• Original Assignee: John A. Stine
• Inventors: Stine, John A.
• Primary Examiner(s): Juntima; Nittaya
• Application Number:
  US11/108,457
• Publication Number:
  US 20050190784A1
• Time in Patent Office: 1,744 Days
• Field of Search: 370/252, 370254-255, 370328-329, 370/345, 370/347, 370/348, 370/445, 370/447, 370/458, 370461-462, 370/465, 370/468
• US Class Current: 370/252
• 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 a wireless network, comprising:

synchronizing nodes on a wireless channel of the wireless network to a common time;

dividing a wireless channel into transmission slots;

establishing a plurality of signaling phases on the wireless channel at the beginning of a transmission slot, wherein each of the plurality of signaling phases is associated with a signaling process selected from the group consisting of a first to assert signaling process and a last to assert signaling process, and wherein each of the plurality of signaling phases comprises one or more signaling slots;

synchronizing transmission of access signals of contending nodes relative to the signaling phases, wherein each of the contending nodes comprises a packet to send and wherein each of the contending nodes contends simultaneously for access to the wireless channel;

determining surviving nodes of a signaling phase among the contending nodes by applying the signaling process associated with the signaling phase to the access signals transmitted by the contending nodes;

determining ultimate surviving nodes of a channel access attempt among the surviving nodes by identifying the surviving nodes of each of the plurality of signaling phases among the contending nodes; and

authorizing the ultimate surviving nodes to transmit packets.

2. The method of claim 1 further comprising:

synchronizing the transmission of request-to-send (RTS) messages from the ultimate surviving nodes;

synchronizing the transmission of clear-to-send (CTS) messages from the nodes that respond to an RTS message from an ultimate surviving node;

synchronizing the transmission of payload packets from the surviving nodes to destination nodes during the transmission slot; and

synchronizing the transmission of acknowledgement (ACK) messages from the nodes that respond to receiving the transmitted packets.

3. The method of claim 2 further comprising:

determining a route for sending a payload packet from a contending node to a destination node using a routing table, wherein the route comprises a node adjacent to the ultimate surviving node (herein, the “

next hop node”

);

sending a request to send (RTS) message from an ultimate surviving node for receipt by the next hop node;

sending a clear to send (CTS) message from the next hop node when the RTS message is received by the next hop node;

sending the payload packet from the ultimate surviving node to the next hop node if the CTS message is received by the ultimate surviving node; and

sending an acknowledgement (ACK) message from the next hop node for receipt by the ultimate surviving node if the payload packet is received by the next hop node.

4. The method of claim 2 further comprising:

selecting a payload packet for broadcast by a contending node to a plurality of neighboring nodes;

determining that the contending node is the ultimate surviving node;

sending a request to send (RTS) message from the ultimate surviving node for receipt by a broadcast address;

silencing nodes that receive the RTS during a CTS message time frame;

sending the payload packet from the ultimate surviving node to the broadcast address; and

silencing nodes that receive the payload packet during an ACK message time frame.

5. The method of claim 1, wherein the method further comprises:

synchronizing the transmission of payload packets from ultimate surviving nodes to nodes adjacent to the ultimate surviving node during a transmission slot.

6. The method of claim 1, wherein the method further comprises:

synchronizing the transmission of acknowledgement packets from nodes that receive the payload packets.

7. The method of claim 1, wherein establishing a plurality of signaling phases on the wireless channel at the beginning of a transmission slot comprises at least:

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

permitting contending nodes having packets 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 a priority phase; and

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

8. The method of claim 7, wherein the packet differentiator is selected from the group consisting of a time to live, a network application, a content of a packet, a source of a packet, and a destination of a packet.

9. The method of claim 7 further comprising:

organizing the transmission slots into constant bit rate (CBR) frames; and

repeating the CBR frames at a rate where one slot per frame supports a lowest CBR service.

10. The method of claim 9 further comprising reserving transmission slots on a use-or-lose basis comprising:

implementing a quality of service (QoS) priority for initial access to a transmission slot in a CBR frame;

implementing a CBR priority for subsequent access to the same transmission slot of a next CBR frame;

implementing a policy whereby contending nodes that have used at least one of a QoS signaling slot and a CBR signaling slot in a transmission slot of a previous CBR frame may use the CBR signaling slot in the same transmission slot of a current CBR frame;

implementing a policy whereby destination nodes that received a packet in a transmission slot that was contended for using at least one of the QoS signaling slot and the CBR signaling slot in the transmission slot of the previous CBR frame may cooperate in the contention signaling in the same transmission slot of the current CBR frame when the CBR signaling slot is used in the contention;

implementing a cooperative signaling slot in a first position of a subsequent first to assert signaling phase that is used in tandem with the use of the CBR signaling slot; and

implementing a policy whereby a contending node that contends using the CBR signaling slot and the destination node of a packet received in the same transmission slot of the previous CBR frame may also signal using the cooperative signaling slot.

11. The method of claim 10 further comprising:

forming multiple queues, wherein the multiple queues are each associated with a different priority of service and wherein the multiple queues comprise constant bit rate (CBR) stream queues and variable bit rate (VBR) stream queues;

providing a queue for each new CBR and VBR stream;

implementing a policy to send packets from highest priority queues first; and

implementing a policy to associate CBR and VBR queues to specific reserved transmission slots in each CBR frame and wherein the contending nodes contend to send packets from the queues using the CBR priority.

12. The method of claim 10, wherein the packet differentiator is selected from the group consisting of a time to live, a network application, a content of a packet, a source of a packet, and a destination of a packet.

13. The method of claim 1 further comprising supporting the selection of a unique channel for the exchange of peer-to-peer traffic between contending nodes and nodes adjacent to a contending node (herein, the “

next hop nodes”

) using signaling slots comprising;

providing a receiver directed channel for each node;

providing a broadcast channel to be shared by each node;

providing a broadcast priority group comprising a subset of priority signaling slots;

implementing a policy whereby non-contending nodes listen for packets on their receiver directed channel whenever any priority signaling slot other than a signaling slot from the broadcast priority group is used; and

implementing a policy whereby non-contending nodes listen for packets in the broadcast channel whenever the broadcast priority group was used to gain access.

14. The method of claim 13 further comprising the ultimate surviving nodes transmitting multiple different packets of data to different next hop nodes simultaneously, wherein the ultimate surviving nodes each comprise a number of transceivers at least equal to the number of different next hop nodes and wherein each transceiver transmits on a different channel.

15. The method of claim 13 further comprising the contending nodes transmitting different packets of data to different next hop nodes simultaneously using a single transceiver adapted to code-multiplex a signal from the single transceiver.

16. The method of claim 3 further comprising:

identifying an attribute of a received RTS packet at the next hop node;

sending the attribute to the ultimate surviving node in the CTS packet.

17. The method of claim 16, wherein the attribute is a measure of the signal power of the received RTS packet and wherein the method further comprises using the attribute at the ultimate surviving node to adjust the transmission power of a payload packet.

18. The method of claim 1, wherein each of the ultimate surviving nodes comprises a directional antenna and the method further comprises:

determining at the ultimate surviving node the direction of a node adjacent to the surviving node (herein, the “

next hop node”

); and

pointing a directional antenna of the ultimate surviving node in the direction of the next hop node during packet transmissions and receptions over the transmission channel.

19. The method of claim 1, wherein a node adjacent to an ultimate surviving node (herein, the “

next hop node”

) comprises a directional antenna and wherein the method further comprises;

determining at the next hop node the direction of the ultimate surviving node; and

pointing the directional antenna of the next hop node in the direction of the ultimate surviving node during packet receptions and transmissions over the transmission channel.

20. The method of claim 1 further comprising transmitting signals from a non-contending node to assist contention by the contending nodes.

21. The method of claim 20 further comprising providing a a slot designated for cooperative signaling in a signaling phase and wherein the method further comprises:

determining at a node adjacent to a surviving node (herein, the “

next hop node”

) that it is a recipient of a CBR transmission from the surviving node; and

sending an assertion signal during the cooperative signaling slot of the signaling phase.

22. The method of claim 21 further comprising:

at a receiving node, detecting the simultaneous arrival of a plurality of signals for the receiving node, wherein the plurality of signals interfere with reception at the receiving node; and

echoing a signal to suppress interfering contending nodes.

23. The method of claim 1 further comprising:

allowing a node to enter a low energy state;

implementing a slot-based policy whereby the node can enter the low energy state for the remainder of a transmission if the node has no pending traffic for that slot;

implementing a channel-based policy whereby the node can enter a low energy state for a predefined period if the channel is not in use; and

implementing a coordination policy whereby the node coordinates with other nodes to define a period for entering and remaining in a low energy state.

24. The method of claim 23, 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 node; and

placing the node in a dozing state.

25. The method of claim 24, wherein the wakeup interval comprises a number of transmission slots.

26. The method of claim 25, wherein determining whether a node is a participant in a packet exchange comprises listening for signaling from a contending node.

27. The method of claim 24, wherein placing the node in a dozing state comprises:

coordinating with a neighboring node for the receipt of packets directed to the node entering the dozing state;

broadcasting from the node entering the dozing state a wakeup interval and the address of the neighboring node to receive packets for the node entering the dozing state; and

wherein the method further comprises;

while the node is in the dozing state, receiving at the neighboring node the packets for the node; and

upon leaving the dozing state, receiving at the node the packets received by the neighboring node.

28. The method of claim 27 wherein the method further comprises:

after leaving the dozing state, listening for a priority signal;

if no priority signal is heard, broadcasting from the node entering the dozing state a wakeup interval and the address of the neighboring node to receive packets for the node entering the dozing state; and

reentering the dozing state.

29. The method of claim 1 further comprising:

associating signal tones with a specified node behavior, wherein the signal tones elicit the specified behavior when received by a node; and

sending a collision resolution signal from the contending node, wherein the collision resolution signal comprises the signal tones.

30. The method of claim 1, wherein an access signal only occupies one signaling slot.

31. The method of claim 1, wherein an access signal occupies one or more contiguous signaling slots.