Method for forwarding in multi-hop networks

• US 6,798,765 B2
• Filed: 10/04/2001
• Issued: 09/28/2004
• Est. Priority Date: 10/27/2000
• Status: Expired due to Term

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Larsson, Peter
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): Wong, Blanche
• Application Number:
  US09/970,023
• Publication Number:
  US 20020051425A1
• Time in Patent Office: 1,090 Days
• Field of Search: 370/254, 370/256, 370/351, 370/389, 370/392, 370/400, 370/401, 370/428
• US Class Current: 370/351
• CPC Class Codes: H04B 7/2606 Arrangements for base station coverage control, e.g. by using relays in tunnels
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 52/46 in multi hop networks, e.g. wireless relay networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A system and method for forwarding information in a multi-hop network. An originating node broadcasts or multicasts a probe message to a plurality of other network nodes, including at least one candidate relay node, in a general direction in which the information is to be forwarded. Each candidate relay node that successfully receives the probe message returns an acknowledgment to the originating node, which then selects one of the acknowledging nodes. The originating node then transmits the information to the selected relay node, which returns an acknowledgment when the information is received. The selected relay node is then designated as the originating node, and the process is repeated to propagate the information through the network. If the acknowledgment of the data is not received, the originating node may select a different one of the candidate relay nodes that acknowledged the probe message, or may repeat the selection process.

Claims

1. A method of forwarding information in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

transmitting a message from an originating node to a plurality of candidate relay nodes in a general direction in which the information is to be forwarded;

transmitting from each of the candidate relay nodes that successfully received the message, an acknowledgment of the message to the originating node;

selecting by the originating node, at least one of the candidate relay nodes that acknowledged receiving the message;

transmitting a forwarding order from the originating node to the selected candidate relay node, said order instructing the selected node to forward the previously received message to a next node;

forwarding the message to the next node by the selected relay node; and

transmitting an acknowledgment of the forwarding order from the selected candidate relay node to the originating node.

2. The method of claim 1, wherein the steps of transmitting the message, transmitting the acknowledgment of the message, selecting one of the candidate relay nodes, transmitting the forwarding order, forwarding the message, and transmitting the acknowledgment of the forwarding order are repeated until the message traverses the multi-hop network.

3. The method of claim 1, further comprising the step of altering transmit parameters and repeating the step of transmitting the message from the originating node, when the originating node does not receive an acknowledgment of the message from any of the plurality of candidate relay nodes.

4. The method of claim 1, further comprising the step of altering transmit parameters and repeating the step of transmitting the message from the originating node, when the originating node receives less than a predetermined number of acknowledgments of the message.

6. The method of claim 1, wherein the step of transmitting the message is performed as a broadcast.

7. The method of claim 1, wherein the step of transmitting the message is performed as a multicast.

8. The method of claim 1, wherein the step of transmitting the message is performed using Carrier Sense.

9. The method of claim 1, further comprising the step of discarding the message from non-selected candidate relay nodes after the step of transmitting the acknowledgment of the forwarding order.

10. The method of claim 1, wherein each message acknowledgment includes node-specific information related to cost or quality of service available through the acknowledging node.

11. The method of claim 1, further comprising the step of selecting transmit parameters prior to transmitting the message.

5. A method of forwarding information in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

transmitting a message from an originating node directly to a plurality of candidate relay nodes without a sensing channel, wherein the message is transmitted in a general direction in which the information is to be forwarded;

transmitting from each of the candidate relay nodes that successfully received the message, an acknowledgment of the message to the originating node, said acknowledgment including node-specific information related to cost or quality of service available through the acknowledging node;

selecting by the originating node, at least one of the candidate relay nodes that acknowledged receiving the message, based upon the node-specific information;

transmitting a forwarding order from the originating node to the selected candidate relay node, said order instructing the selected node to forward the previously received message to a next node;

forwarding the message to the next node by the selected relay node; and

transmitting an acknowledgment of the forwarding order from the selected candidate relay node to the originating node.

12. A method of forwarding information in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

designating a network node as an originating node;

selecting a node in the network, different from the originating node, as a candidate relay node;

transmitting a message from the originating node to a plurality of other network nodes in a general direction in which the information is to be forwarded, wherein the plurality of other nodes includes the selected candidate relay node, and wherein the message includes a forwarding order directed to the selected candidate relay node;

in the event the selected candidate relay node receives the message, performing the steps of;

transmitting an acknowledgment of the message from the selected candidate relay node to the originating node;

designating the selected candidate relay node as the originating node; and

repeating the steps of selecting a candidate relay node and transmitting the message;

in the event the originating node does not receive an acknowledgment of the message from the selected candidate relay node, performing the steps of;

transmitting an acknowledgment of the message to the originating node from each of the plurality of network nodes that successfully received the message from the originating node;

selecting one of the network nodes that acknowledged receiving the message as a new candidate relay node;

transmitting a forwarding order from the originating node to the newly selected candidate relay node;

transmitting an acknowledgment of the forwarding order from the newly selected candidate relay node to the originating node; and

designating the newly selected candidate relay node as the originating node.

13. The method of claim 12, wherein the steps performed in the event the originating node does not receive an acknowledgment of the message from the selected candidate relay node, further comprise repeating the steps of selecting a candidate relay node and transmitting the message after designating the newly selected candidate relay node.

14. The method of claim 12, further comprising the step of transmitting an acknowledgment of the message to the originating node from each of the plurality of network nodes that successfully received the message from the originating node, in the event the selected candidate relay node receives the message.

15. A method of forwarding information in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

selecting by an originating node in the network, a node in the network, different from the originating node, as a first candidate relay node;

transmitting a message from the originating node in the network to a plurality of candidate relay nodes in the network in a general direction in which the information is to be forwarded, wherein the plurality of candidate relay nodes includes the selected first candidate relay node, and wherein the message includes an order directing the selected first candidate relay node to select a second one of the plurality of candidate relay nodes to forward the message;

transmitting to the first selected candidate relay node, an acknowledgment of the message from each of the plurality of candidate relay nodes that received the message;

based on the transmitted acknowledgments of the message, selecting by the first selected candidate relay node, a second one of the candidate relay nodes to forward the message;

sending a forwarding order from the selected first candidate relay node to the selected second candidate relay node, said order instructing the selected second candidate relay node to forward the previously received message to a next node; and

in response to the forwarding order, forwarding the message from the selected second candidate relay node to the next node.

16. The method of claim 15, wherein the step of forwarding the message from the selected second candidate relay node comprises:

designating the selected second candidate relay node as the originating node; and

repeating the steps of selecting the first candidate relay node, transmitting the message, transmitting an acknowledgment of the message from each of the plurality of candidate relay nodes that received the message, selecting a second one of the candidate relay nodes to forward the message, and sending a forwarding order from the selected first candidate relay node to the selected second candidate relay node.

17. The method of claim 15, further comprising the step of sending an acknowledgment of the forwarding order, from at least one of the first and second selected candidate relay nodes, to the originating node.

18. The method of claim 17, further comprising the step of discarding the message from the originating node and non-selected ones of the plurality of candidate relay nodes after forwarding the message from the selected second candidate relay node.

19. The method of claim 17, wherein in the step of selecting a second one of the candidate relay nodes, the selected first candidate relay node is selected as the selected second candidate relay node.

20. The method of claim 17, further comprising, in the event the originating node does not receive an acknowledgment of the forwarding order, repeating the steps of selecting a first candidate relay node in the network, and transmitting the message from the originating node in the network to a plurality of candidate relay nodes.

37. The method of claim 15, wherein each acknowledgment message transmitted from each of the plurality of candidate relay nodes to the first selected candidate relay node includes node-specific information related to cost or quality of service available through the acknowledging node, and the step of selecting a second one of the candidate relay nodes to forward the message includes selecting the second candidate relay node based on the node-specific information in the transmitted acknowledgments of the message.

21. A method of forwarding information in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

transmitting multiple packets from an originating node in the network to a plurality of candidate relay nodes in the network in a general direction in which the information is to be forwarded;

transmitting an acknowledgment from each of the plurality of candidate relay nodes that received at least one of the multiple packets, to the originating node;

based on acknowledgments of the multiple packets received at the originating node, resending packets that were not received by at least a predetermined number of candidate relay nodes, until each packet has been received by at least the predetermined number of candidate relay nodes;

selecting at least one of the plurality of candidate relay nodes;

sending a forwarding order from the originating node, to each of the selected at least one candidate relay node; and

in response to the forwarding order, forwarding received packets from each of the selected at least one candidate relay node.

22. A system for forwarding a message, comprising a plurality of nodes forming a network, wherein:

an originating node forwards the message to a plurality of candidate relay nodes in the network in a general direction in which the message is to be forwarded;

those of the plurality of candidate relay nodes that receive the message, transmit an acknowledgment to the originating node;

based on the acknowledgments, the originating node selects one of the candidate relay nodes that acknowledged receiving the message, and transmits a forwarding order to the selected candidate relay node instructing the selected candidate relay node to forward the previously received message to a next node; and

the selected candidate relay node forwards the message to the next node, and transmits an acknowledgment of the forwarding order to the originating node.

38. The system of claim 22, wherein each acknowledgment message transmitted from each of the plurality of candidate relay nodes to the originating node includes node-specific information related to cost or quality of service available through the acknowledging node, and the originating node selects one of the candidate relay nodes based on the node-specific information in the transmitted acknowledgments of the message.

23. A system for forwarding a message, comprising a plurality of nodes forming a network, wherein:

an originating node selects a candidate relay node in the network;

the originating node transmits a message to a plurality of candidate relay nodes in the network in a general direction in which the message is to be forwarded, wherein the plurality of candidate relay nodes includes the selected candidate relay node, and wherein the message includes a forwarding order directed to the selected candidate relay node;

in the event the selected candidate relay node receives the message, the selected candidate relay node transmits an acknowledgment of the message to the originating node, and forwards the message; and

in the event the originating node does not receive an acknowledgment of the message from the selected candidate relay node, a) each of the at least one candidate relay node that successfully received the message from the originating node, transmits an acknowledgment of the message to the originating node, b) the originating node selects one of the at least one candidate relay nodes that acknowledged receiving the message and transmits a forwarding order to the newly selected candidate relay node, and d) the newly selected candidate relay node transmits an acknowledgment of the forwarding order to the originating node and forwards the message.

24. A system for forwarding a message, comprising a plurality of nodes forming a network, wherein:

an originating node selects a first candidate relay node in the network;

the originating node transmits a message to a plurality of candidate relay nodes in the network in a general direction in which the message is to be forwarded, wherein the plurality of candidate relay nodes includes the selected first candidate relay node, and wherein the message includes an order directing the selected first candidate relay node to select a second one of the plurality of candidate relay nodes to forward the message;

each of the plurality of candidate relay nodes that received the message, transmits an acknowledgment of the message to the first selected candidate relay node;

first selected candidate relay node selects a second one of the candidate relay nodes to forward the message, based on received acknowledgments of the message;

the first selected candidate relay node sends a forwarding order to the selected second candidate relay node; and

selected second candidate relay node forwards the message in response to the forwarding order.

25. A system for forwarding data packets, comprising a plurality of nodes forming a network, wherein:

an originating node transmits multiple packets to a plurality of candidate relay nodes in the network in a general direction in which the packets are to be forwarded;

each of the plurality of candidate relay nodes that received at least one of the multiple packets, transmits an acknowledgment to the originating node;

the originating node determines which packets were not received by at least a predetermined number of candidate relay nodes, based on received acknowledgments of the multiple packets, and resends packets that were not received by at least a predetermined number of candidate relay nodes, until each packet has been received by the at least predetermined number of candidate relay nodes;

the originating node selects at least one of the plurality of candidate relay nodes based on the received acknowledgments;

the originating node sends a forwarding order to each of the selected at least one candidate relay node; and

each of the selected at least one candidate relay node forwards packets it has received, in response to the forwarding order.

26. A method of forwarding data in a multi-hop network having a plurality of network nodes, said method comprising the steps of:

transmitting a probe message from an originating node to a plurality of candidate relay nodes in a general direction in which the data is to be forwarded;

transmitting an acknowledgment of the probe message to the originating node, from each of the candidate relay nodes that successfully received the message from the originating node;

based on acknowledgments of the probe message received by the originating node, selecting at least one of the candidate relay nodes that acknowledged receiving the probe message;

transmitting the data from the originating node to the selected candidate relay node;

upon successfully receiving the data, transmitting an acknowledgment of the data from the selected candidate relay node to the originating node; and

designating the selected candidate relay node as a new originating node for further forwarding of the data.

27. The method of claim 26, further comprising the steps of:

determining whether an acknowledgment of the data is received by the originating node; and

upon determining that the originating node did not receive an acknowledgment of the data, selecting a different one of the at least one candidate relay nodes.

28. The method of claim 26, further comprising the steps of:

determining whether an acknowledgment of the data is received by the originating node; and

upon determining that the originating node did not receive an acknowledgment of the data, repeating the steps of claim 26.

29. The method of claim 26, further comprising the steps of:

determining whether an acknowledgment of the data is received by the originating node; and

upon determining that the originating node did not receive an acknowledgment of the data, transmitting a message to request all nodes hearing the message to reply with an indication of whether the replying node received the data.

30. The method of claim 26, wherein:

the probe message is multicast and instructs all nodes hearing the probe message and not addressed in the probe message, to be silent for a time duration.

31. The method of claim 26, wherein:

the acknowledgment of the data from the selected candidate relay node instructs all nodes hearing the acknowledgment that are not the originating node, to be silent for a time duration.

32. The method of claim 26, wherein each acknowledgment message transmitted from each of the plurality of candidate relay nodes to the originating node includes node-specific information related to cost or quality of service available through the acknowledging node, and the step of selecting one of the candidate relay nodes includes selecting a candidate relay node based on the node-specific information in the transmitted acknowledgments of the message.

33. A communication node in a communication network, comprising:

means for communicating as an originating node in the network, comprising;

means for transmitting a message to a plurality of candidate relay nodes in the network in a general direction in which the information is to be forwarded;

means for receiving acknowledgments transmitted by those of the plurality of candidate relay nodes that received the message;

means for selecting one of the candidate relay nodes that acknowledged receiving the message, based on the acknowledgments; and

means for transmitting a forwarding order to the selected candidate relay node; and

means for communicating as a relay node in the network, comprising;

means for receiving a message from an originating node in the network;

means responsive to receiving the message, for transmitting an acknowledgment to the originating node;

means for receiving a forwarding order from the originating node, said forwarding order ordering the communication node to forward the received message in the general direction in which the information is to be forwarded; and

means for forwarding the message.

34. A communication node in a communication network, comprising:

means for communicating as an originating node in the network, comprising;

means for selecting a candidate relay node in the network;

means for transmitting a message to a plurality of candidate relay nodes in the network in a general direction in which the information is to be forwarded, wherein the plurality of candidate relay nodes includes the selected candidate relay node, and wherein the message includes a forwarding order directed to the selected candidate relay node; and

means for selecting one of the at least one candidate relay nodes that acknowledged receiving the message and transmitted a forwarding order to the newly selected candidate relay node, upon determining that the communication node did not receive an acknowledgment of the message from the selected candidate relay node; and

means for communicating as a relay node in the network, comprising;

means for receiving a message that includes a forwarding order from an originating node in the network;

means for determining whether the forwarding order selects the communication node to forward the message;

means responsive to determining that the forwarding order selects the communication node, for transmitting an acknowledgment of the message to the originating node and forwarding the message;

means responsive to determining that the forwarding order does not select the communication node, for determining whether a candidate relay node in the network transmits an acknowledgment of the message to the originating node within a predetermined time period, and if not, transmitting an acknowledgment of the message to the originating node;

means for receiving a subsequent forwarding order from the originating node selecting the communication node; and

means responsive to receiving the subsequent forwarding order, for transmitting an acknowledgment of the forwarding order to the originating node, and forwarding the message.

35. A communication node in a communication network, comprising:

means for communicating as an originating node in a network, comprising;

means for selecting a first candidate relay node in the network; and

means for transmitting a message to a plurality of candidate relay nodes in the network in a general direction in which the information is to be forwarded, wherein the plurality of candidate relay nodes includes the selected first candidate relay node, and wherein the message includes an order directing the selected first candidate relay node to select a second one of the plurality of candidate relay nodes to forward the message; and

means for communicating as a relay node in the network, comprising;

means for receiving a message that includes an order from an originating node;

means for determining whether the order in the message selects the communication node as the first selected candidate relay node;

means responsive to determining that the order does not select the communication node as the first selected candidate relay node, for transmitting an acknowledgment of the message to the first selected candidate relay node;

means responsive to determining that the order in the message selects the communication node as the first selected candidate relay node, for selecting a second one of the candidate relay nodes to forward the message, based on received acknowledgments of the message from candidate relay nodes in the network;

means for sending a forwarding order to the selected second candidate relay node; and

means responsive to receiving a forwarding order from the selected first candidate relay node, after receiving and acknowledging the message, for forwarding the message.

36. A communication node in a communication network, comprising:

means for communicating as an originating node in a network, comprising;

means for transmitting multiple packets to a plurality of candidate relay nodes in a general direction in which the information is to be forwarded;

means for receiving any acknowledgments of the transmitted packets from the plurality of candidate relay nodes;

means for determining which packets were not received by at least a predetermined number of candidate relay nodes, based on received acknowledgments of the multiple packets;

means for resending packets that were not received by at least a predetermined number of candidate relay nodes, until each packet has been received by the at least predetermined number of candidate relay nodes;

means for selecting at least one of the plurality of candidate relay nodes based on the received acknowledgments; and

means for sending a forwarding order to each of the selected at least one candidate relay nodes; and

means for communicating as a relay node in the network, comprising;

means for receiving one or more multiple packets from an originating node in the network;

means for transmitting an acknowledgment to the originating node confirming receipt of the received packets;

means for receiving a forwarding order instructing the communication node to forward received packets; and

means for forwarding the received packets.