Method for forwarding in multi-hop networks

• US 6,788,670 B1
• Filed: 10/27/2000
• Issued: 09/07/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/697,352
• Time in Patent Office: 1,411 Days
• Field of Search: 370/254, 370/256, 370/351, 370/400, 370/389, 370/392, 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

In order to transmit a data message in a multi-hop environment, a first station broadcasts or multicasts a transmission to other stations or receivers nearby. After one or more of the stations replies to the first station, the first station selects one of the stations that replied and transmits a command message to the selected station to assume responsibility for forwarding the data message. The data message can accompany the first transmission from the first station, or can accompany the command message. In addition, the replies to the first station can include information regarding costs of routing the data message to its destination. In another variation, the first transmission can include both the data message and a command message designating one of the nearby stations, so that when the designated station receives the first transmission it can immediately forward the data message and then later reply to the first station. This variation also includes a backup mechanism so that if the designated station does not receive the first transmission, one or more of the other nearby stations that did receive the first transmission can reply to the first station, which can then evaluate the replies, select one of the stations that replied, and transmit a command message to the selected station.

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 directly to a plurality of candidate relay nodes without a sensing channel, said message being transmitted in a general direction in which the information is to be forwarded;

transmitting an acknowledgment of the message to the originating node from each candidate relay node that successfully received the message from 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;

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

designating the selected candidate relay node as the originating node.

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

3. The method of claim 1, wherein the step of transmitting an acknowledgment of the forwarding order is performed after the selected relay node transmits the message as the originating node.

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 does not receive an acknowledgment of the message.

5. 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, 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.

9. The method of claim 1, wherein each message acknowledgment includes node-specific information.

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

11. 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 directly to a plurality of other network nodes without a sensing channel, said message being transmitted 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.

12. The method of claim 11, 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.

13. The method of claim 11, 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.

14. 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 directly to a plurality of candidate relay nodes in the network without a sensing channel, said message being transmitted 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 an acknowledgment of the message from each of the plurality of candidate relay nodes that received the message, to the first selected candidate relay node;

based on the transmitted acknowledgments of the message, selecting 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; and

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

15. The method of claim 14, 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.

16. The method of claim 14, 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.

17. The method of claim 16, 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.

18. The method of claim 16, 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.

19. The method of claim 16, 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.

20. 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 directly to a plurality of candidate relay nodes in the network without a sensing channel, said packets being transmitted 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 first selected candidate relay 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.

21. A system for forwarding information, comprising a plurality of nodes forming a network, wherein:

an originating node forwards a message directly to a plurality of candidate relay nodes in the network without a sensing channel, said originating node forwarding the message in a general direction in which the information 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; and

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

22. A system for forwarding information, 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 directly to a plurality of candidate relay nodes in the network without a sensing channel, said originating node transmitting the message 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;

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.

23. A system for forwarding information, 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 directly to a plurality of candidate relay nodes in the network without a sensing channel, said originating node transmitting the message 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;

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.

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

an originating node transmits multiple packets directly to a plurality of candidate relay nodes in the network without a sensing channel, said originating node transmitting the message in a general direction in which the information is 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.

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

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

means for transmitting a message directly to a plurality of candidate relay nodes without a sensing channel, said originating node forwarding the message 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.

26. 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 directly to a plurality of candidate relay nodes without a sensing channel, said originating node forwarding the message 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.

27. 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 directly to a plurality of candidate relay nodes without a sensing channel, said originating node forwarding the message 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.

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

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

means for transmitting multiple packets directly to a plurality of candidate relay nodes without a sensing channel, said originating node forwarding the message 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.