Receiver-initiated multiple access for AD-HOC networks (RIMA)

• US 20020080768A1
• Filed: 08/10/2001
• Published: 06/27/2002
• Est. Priority Date: 08/11/2000
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Tzamaloukas, Asimakis, Garcia-Luna-Aceves, J.J.
• Granted Patent: US 6,996,074 B2
• Time in Patent Office: Days
• US Class Current: 370/349
• CPC Class Codes: H04W 74/06 using polling
• CPC Class Codes: H04W 74/0816 with collision avoidance

Abstract

Receiver-initiated collision avoidance methods for use in ad-hoc wireless networks in which carrier sensing is available. A number of protocol variants are described including RIMA-SP (simple polling), RIMA-DP (dual-purpose polling), and RIMA-BP (broadcast polling). These handshake methods according to the invention are capable of correctly avoiding collisions within a network that contains hidden nodes, and the RIMA-DP protocol provides higher performance levels than attainable with existing handshaking protocols within the ad-hoc wireless networks. The use of dual-purpose polling allows a control packet to be sent which has alternative functions, such as requesting data from the polled node, if available, and if not available then providing a transmission request from the polling node to send data to the polled node.

Claims

1. A method of providing a medium access control protocol within a wireless network having a plurality of nodes communicating over a channel, comprising:

transmitting a data packet over said channel by a first node, after a first collision-avoidance delay interval, in response to receipt of a ready-to-receive control packet from a second node indicating that said second node is ready to receive a data packet; and

canceling transmission of said data packet during said first collision-avoidance delay interval in response to receipt of a no-transmission-request control packet which indicates the detection of activity within said channel.

2. A method as recited in claim 1, wherein said first collision-avoidance delay interval is set to at least the maximum propagation delay between the nodes communicating over said channel.

3. A method as recited in claim 1:

wherein said ready-to-receive control packet further indicates that said second node is requesting transmission of data to said first node; and

wherein transmission of said data packet from said second node to said first node is responsive to the receipt of a clear-to-send control packet from said first node indicating that said second node is clear to send the data packet.

4. A method as recited in claim 3, wherein said clear-to-send control packet is of sufficient length that transmission thereof requires a length of time which exceeds the time for transmitting a ready-to-receive control packet by twice the maximum propagation delay between the nodes communicating over said channel.

5. A method as recited in claim 3, wherein said second collision-avoidance interval substantially equals or exceeds the time required for transmitting a ready-to-receive control packet plus seven times the maximum propagation delay between the nodes communicating over said channel.

6. A method as recited in claim 1,

wherein said first node is one of a plurality of nodes that have received said ready-to-receive control packet from said second node;

wherein transmission of said data packet from said second node is preceded by transmission of a clear-to-send control packet indicating that said second node is clear to send the data packet, followed by a second collision-avoidance interval; and

further comprising

canceling transmission from said second node to said first node, during said second collision-avoidance interval, in response to receipt of a no-transmission-request control packet.

7. A method as recited in claim 6, wherein said clear-to-send control packet is of sufficient length that transmission thereof requires a length of time which exceeds the time for transmitting a ready-to-receive control packet by twice the maximum propagation delay between the nodes communicating over said channel.

8. A method as recited in claim 6, wherein said second collision-avoidance interval substantially equals or exceeds the time required for transmitting a ready-to-receive control packet plus seven times the maximum propagation delay between the nodes communicating over said channel.

9. A method as recited in claim 1, wherein said channel of said wireless network is subject to the operation of hidden terminals.

10. A method as recited in claim 1, wherein each of said nodes communicating on said channel is adapted for detecting carrier within said channel.

12. A method as recited in claim 11, wherein said first collision-avoidance delay interval is set to at least the maximum propagation delay between the nodes communicating over said channel.

13. A method as recited in claim 11, wherein said clear-to-send control packet is of sufficient length wherein transmission requires a length of time which exceeds the time for transmitting a ready-to-receive control packet by twice the maximum propagation delay between the nodes communicating over said channel.

14. A method as recited in claim 11, wherein said second collision-avoidance interval substantially equals or exceeds the time required for transmitting a ready-to-receive control packet plus seven times the maximum propagation delay between the nodes communicating over said channel.

11. A method of providing collision-avoidance within a medium access control protocol within a wireless network having a plurality of nodes communicating over a channel, comprising:

receiving within a first node, a ready-to-receive-or-transmit control packet from a neighboring second node;

transmitting a data packet from said first node to said second node, following a first collision-avoidance delay interval, if data is available in said first node;

canceling transmission of said data packet from said first node to said second node if a no-transmission-request control packet is received by said first node during said first collision-avoidance interval;

transmitting a clear-to-send control packet, followed by a second collision-avoidance interval, followed by a data packet from said second node to said first node, if said first node has no data available for transmission to said second node; and

canceling transmission of said data packet from said second node to said first node if a no-transmission-request control packet is received by said second node during said second collision-avoidance interval;

15. A method as recited in claim 11, wherein said channel of said wireless network is subject to the operation of hidden terminals.

16. A method as recited in claim 11, wherein each of said nodes communicating on said channel is adapted for detecting carrier within said channel.

18. A method as recited in claim 17, wherein said transceiver nodes comprise single-channel radios having carrier sense capability.

19. A method as recited in claim 17, wherein said first collision-avoidance delay interval is set to at least the maximum propagation delay between the nodes communicating over said channel.

20. A method as recited in claim 17, wherein said RTR control packet further indicates that said first node is requesting a sender-initiated data transmission if said second node has no data packets for transmitting to said first node, and further comprising:

transmitting a CTS control packet (clear-to-send), or equivalent, by said second node, if said second node has no data packets for transmitting to said first node;

wherein said CTS control packet indicates that said first node is requesting to transmit data to said second node, if said second node has no data for transmitting to said first node; and

transmitting a data packet from said first node to said second node after receiving said CTS control packet.

21. A method as recited in claim 17, wherein transmission of said RTR control packet is from said first node to said second node along with at least one additional neighboring nodes of said first node, and further comprising:

transmitting an RTS control packet (ready-to-send) by said neighbors of said first node which have at least one data packet for transmitting to said first node; and

monitoring for an NTR control packet from said first node during a second collision-avoidance interval prior to transmitting of said data packet to said first node.

22. A method as recited in claim 21, wherein said second collision-avoidance interval substantially equals or exceeds the time required for transmitting said RTR control packet plus seven times the maximum propagation delay between the nodes communicating over said channel.

24. A method as recited in claim 23, wherein each of said nodes communicating on said channel is adapted for detecting carrier within said channel.

26. A method as recited in claim 25, wherein said first collision-avoidance waiting period is set to at least the maximum propagation delay between the nodes communicating over said channel.

17. A method of providing receiver-initiated collision-avoidance as a medium access control protocol within a wireless network having a plurality of transceiver nodes communicating over a channel, wherein correct collision-avoidance may be provided despite the existence of hidden terminals within said network, comprising:

transmitting an RTR (ready-to-receive) control packet, or equivalent, by a first node to a neighboring second node;

said RTR control packet indicative of a receiver-initiated transmission request wherein said first node is ready to receive a data packet over said channel;

receiving said RTR control packet from said first node by said second node wherein said second node pends for a sufficient first collision-avoidance interval;

transmitting an NTR (no-transmission-request) control packet, or equivalent, if channel activity is detected by said first node proximal to the sending of said RTR control packet;

said NTR control packet indicative that said second node is to cancel transmission of said data packet to avoid a data packet collision;

receiving said NTR control packet, or equivalent, by said second node to cancel the transmission of said data packet; and

transmitting said data packet from said second node to said first node if no NTR control packet was received within said first collision-avoidance interval.

23. In a wireless network utilizing a medium access control protocol for receiver-initiated collision-avoidance when communicating data packets over said network wherein RTR control packets (ready-to-receive) are sent from a polling node to a polled node to invite said polled node to send a data packet, wherein the improvement comprises:

transmitting an NTR (no-transmission-request) control packet, or equivalent, by said polling node during a period of time following said sending of an RTR control packet if channel activity is detected by said polling node;

receiving said NTR control packet, or equivalent, by said polled node wherein said polled node temporarily postpones the sending of said data packet; and

transmitting said data packet by said polled node only if said data packet is addressed to said polling node.

25. A method of receiver-initiated collision-avoidance within a wireless network having a plurality of nodes communicating data packets with one another over a channel that may include hidden terminals, comprising:

sending a ready-to-receive (RTR) control packet, or equivalent, from a first node to a second node;

receiving said RTR control packet, or equivalent, by said second node;

entering a first collision-avoidance waiting period by said second node upon receipt of said RTR control packet, in which no responses are made to said first node;

backing-off of the channel by a third node, wherein the access to the channel is relinquished for a given period of time, upon receipt of an RTR control packet destined for a node other than the third node;

monitoring said channel during said first collision-avoidance waiting period by said first node to detect ongoing transmission from nodes other than said second node;

sending a no-transmission-request (NTR) control packet, or equivalent, by said first node upon detecting any channel activity during said first collision-avoidance waiting period;

refraining from transmitting data by said second node, upon receipt of an NTR control packet, or equivalent, from said first node; and

transmitting a data packet from said second node only if it is addressed to said first node;

wherein transmitting of the data packet is pursuant to proper receipt of said RTR control packet and the availability of a data packet to be transmitted to said first node.

27. A method of receiver-initiated collision-avoidance within a medium access control protocol on nodes within a wireless network in which a plurality of nodes are capable of communicating with one another over a channel that may include hidden terminals, comprising:

entering a PASSIVE state, or equivalent, by said node when no transmission requests are pending, no data is available to be transmitted, and no carrier is sensed;

transitioning to a REMOTE state by said node while carrier is detected from communicating nodes and deferring ongoing transmissions;

said REMOTE state being of sufficient minimum duration to allow completion of a successful handshake between said communicating nodes;

transitioning from the PASSIVE state to a BACKOFF state, or equivalent, by said node upon detecting noise in the channel;

said BACKOFF state being of sufficient minimum duration to allow completion of a successful handshake between a sender-receiver pair;

transitioning to an RTR (ready-to-receive) state by said node upon receipt of a data packet to be sent to a neighboring node;

transmitting an RTR control packet by said node;

said transmission of an RTR control packet by said node being subject to carrier sensing, wherein if carrier is sensed upon attempting to send the RTR control packet then said node sends a NTR (no-transmission request) control packet to said neighboring node;

receiving said RTR control packet by said neighboring node;

waiting for a predetermined interval upon correct receipt of said RTR control packet by said neighboring node;

transitioning to a BACKOFF state by said neighboring node for a given period of time upon receipt of an NTR control packet from said node;

transitioning to a XMIT state (transmit) if no activity is detected by said neighboring node during the waiting period;

transmitting a data packet by said neighboring node to said node;

transmitting an ACK control packet (acknowledgment) by said node upon receipt of said data packet from said neighboring node; and

transitioning to the BACKOFF state by said neighboring node if said ACK control packet is not received from said first node within a sufficient interval.