Routing in wireless ad-hoc networks

• US 7,808,939 B2
• Filed: 03/28/2003
• Issued: 10/05/2010
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Lenovo PC International Limited (Lenovo Group Ltd.)
• Original Assignee: Lenovo Singapore Pte Limited (Lenovo Group Ltd.)
• Inventors: Bansal, Nikhil, Liu, Zhen
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US10/402,760
• Publication Number:
  US 20040190476A1
• Time in Patent Office: 2,748 Days
• Field of Search: 370/254, 370/255, 370/256, 370/299, 370/310, 370/328, 370/338, 370/349, 370/386, 370/400, 370/401, 370/402, 370/351, 370/395.32, 370/238, 370/238.1, 370/248, 370/270, 370/310.2, 370/312, 370/389, 370/390, 370/393, 370/331, 370/332, 370/343, 370/344, 370/252
• US Class Current: 370/310
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 40/38 adapting due to varying relative distances between nodes
• CPC Class Codes: H04W 8/08 Mobility data transfer
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Efficient routing techniques that meet performance objectives associated with an ad-hoc network environment and the like. More specifically, the invention provides a routing methodology proven to provide high (e.g., close-to-optimal) throughput and low delay guarantees. Further, the present invention preferably considers a network with both static and mobile nodes. The mobile nodes preferably follow a particular model of movement, referred to herein as a mobility model.

Claims

1. A method for use in a node of an ad-hoc network for routing one or more packets, the method comprising the steps of:

obtaining mobility information associated with one or more other nodes in the ad-hoc network, the mobility information relating to a direction of movement of the one or more other nodes relative to a destination of the one or more packets; and

routing the one or more packets to one of the one or more other nodes, for relay to the destination, based on the mobility information.

2. The method of claim 1, wherein at least one of a source and the destination of the one or more packets is a mobile node.

3. The method of claim 1, wherein at least one of a source and the destination of the one or more packets is a static node.

4. The method of claim 1, wherein a node relaying the one or more packets is a mobile node.

5. The method of claim 1, wherein a node relaying the one or more packets is a static node.

6. The method of claim 1, wherein a node has a handoff region associated therewith.

7. A method for use in a node of an ad-hoc network for routing one or more packets, the method comprising the steps of:

obtaining mobility information associated with one or more other nodes in the ad-hoc network, the mobility information relating to a direction associated with the one or more other nodes with respect to a destination of the one or more packets; and

routing the one or more packets to one of the one or more other nodes, for relay to the destination, based on the mobility information,

wherein at least one node in the ad-hoc network has a handoff deadline associated therewith.

8. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein the leader node originally receiving the one or more packets from the source node stores the one or more packets until a mobile relay node is within a given proximity to the leader node.

9. The method of claim 8, wherein at least one of the source node and the destination node is static.

10. The method of claim 8, wherein at least one of the source node and the destination node is mobile.

11. The method of claim 8, wherein transfers of packets between nodes are performed in accordance with different frequency channels so as to at least minimize interference.

12. The method of claim 8, wherein a mobile relay node has a handoff region associated therewith.

13. The method of claim 8, wherein a leader node is a source node.

14. The method of claim 8, wherein the distributed network is an ad-hoc network, and further wherein nodes communicate over wireless links.

15. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein the leader node originally receiving the one or more packets from the source node stores the one or more packets until a mobile relay node is identified as moving in a direction toward the destination node.

16. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein the one or more packets are transferred from one mobile relay node to another mobile relay node such that the one or more packets get closer to the destination node with each transfer.

17. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein the leader node originally receiving the one or more packets from the source node stores the one or more packets until a mobile relay node is within a given proximity to the leader node,

wherein at least one mobile relay node in the distributed network has a handoff deadline associated therewith.

18. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein there are m mobile nodes and n static nodes in the distributed network and further wherein each source node can achieve an average throughput of

19. A method of routing one or more packets in a distributed network, the method comprising the steps of:

clustering at least a portion of static nodes in the distributed network into groups, and identifying a leader node in each group;

transferring one or more packets, to be sent to a destination node, from a source node to a leader node in a group;

transferring the one or more packets from the leader node through one or more available mobile relay nodes in the distributed network; and

transferring the one or more packets from one of the one or more mobile relay nodes to at least one other leader node in at least one other group for delivery to the destination node;

wherein a maximum delay incurred by a packet is at most

20. A method for use in a static node of a distributed network for routing packets, the method comprising the steps of:

identifying the node as a leader node of a group comprising a plurality of static nodes in the distributed network, and storing one or more packets to be sent to a destination node in the leader node; and

transferring the one or more packets from the leader node to at least one available mobile relay node in the distributed network wherein the one or more packets may then be transferred to at least another leader node in at least another group for delivery to the destination node.

21. A method for use in a mobile node of a distributed network for routing packets, the method comprising the steps of:

receiving one or more packets from a node in the distributed network identified as a leader node, the leader node serving as a leader of a group comprising a plurality of static nodes in the distributed network; and

relaying the one or more packets from the mobile node through one or more other mobile nodes in the distributed network wherein the one or more packets may be transferred from one of the one or more mobile nodes to at least another leader node in at least another group for delivery to the destination node.

22. Apparatus for use in a node of an ad-hoc network for routing one or more packets, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain mobility information associated with one or more other nodes in the ad-hoc network, the mobility information relating to a direction of movement of the one or more other nodes relative to a destination of the one or more packets; and

(ii) route the one or more packets to one of the one or more other nodes, for relay to the destination, based on the mobility information.

23. The apparatus of claim 22, wherein at least one of a source and the destination of the one or more packets is a mobile node.

24. The apparatus of claim 22, wherein at least one of a source and the destination of the one or more packets is a static node.

25. The apparatus of claim 22, wherein a node relaying the one or more packets is a mobile node.

26. The apparatus of claim 22, wherein a node relaying the one or more packets is a static node.

27. The apparatus of claim 22, wherein a node has a handoff region associated therewith.

28. Apparatus for use in a node of an ad-hoc network for routing one or more packets, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) obtain mobility information associated with one or more other nodes in the ad-hoc network, the mobility information relating to a direction associated with the one or more other nodes with respect to a destination of the one or more packets; and

(ii) route the one or more packets to one of the one or more other nodes, for relay to the destination, based on the mobility information,

wherein at least one node in the ad-hoc network has a handoff deadline associated therewith.

29. An article of manufacture for use in a node of an ad-hoc network for routing one or more packets, comprising a computer readable storage medium containing one or more programs which when executed by a computer implement the steps of:

obtaining mobility information associated with one or more other nodes in the ad-hoc network, the mobility information relating to a direction of movement of the one or more other nodes relative to a destination of the one or more packets; and

routing the one or more packets to one of the one or more other nodes, for relay to the destination, based on the mobility information.