Coordinated convergecast for AD HOC wireless networks

• US 20060120371A1
• Filed: 12/07/2004
• Published: 06/08/2006
• Est. Priority Date: 12/07/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zhang, Ying, Huang, Qingfeng
• Granted Patent: US 7,474,630 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A network routing method and system may include initializing the network by determining, for each node of the network, a number of hops to a root node and delaying forwarding to the root node, for each node, a packet received, wherein the delay in forwarding the packet received to the root node from a forwarding node depends upon the number of hops separating the root node from the forwarding node. A network routing method and system may include initializing the network by determining, for each node of the network, a number of hops to a root node, determining, for a forwarding node that receives a packet from a sending node, whether to forward the packet to a root node, determining a delay after which the packet is to be forwarded to the root node and determining a probability of forwarding the packet to the root node.

Claims

1. A network routing method, comprising:

initializing the network by determining, for each node of the network, a number of hops to a root node; and

delaying forwarding to the root node, for each node, a packet received from a sending node;

wherein

the delay in forwarding the received packet to the root node from the sending node depends upon the number of hops separating the root node from the forwarding node.

2. The method of claim 1, wherein:

the delay is defined as t(h)=ah+bh+c+r, wherein a, b and c are constants and r is a uniformly distributed random number.

3. The method of claim 1, wherein:

the delay is defined as t(h)=d/2[h(h−

1)+r] τ

, wherein d is a local density corresponding to a number of neighbors of a given node and r is a random uniformly distributed variable.

4. The method of claim 1, wherein:

the network is a square-lattice network; and

the delay is defined as t(h)=2h (h−

1)τ

, wherein h is the number of hops and τ

is an average transmission time for one hop.

5. The method of claim 1, wherein:

the network is a square-lattice network; and

the delay is defined as t(h)=2h (h−

1)τ

−

(h−

1) τ

−

h τ

, wherein h is the number of hops and τ

is an average transmission time for one hop.

6. A network routing method, comprising:

initializing the network by determining, for each node of the network, a number of hops to a root node;

determining, for a forwarding node that receives a packet from a sending node, whether to forward the packet to a root node;

determining a delay after which the packet is to be forwarded to the root node; and

determining a probability of forwarding the packet to the root node.

7. The method of claim 6, wherein initializing the network takes place at a time of query broadcasting.

8. The method of claim 6, wherein initializing the network takes place at a time of bootstrapping.

9. The method of claim 6, wherein determining whether to forward the node to the root node is based on a relative distance to the root node between the forwarding node and the sending node.

10. The method of claim 9, wherein the packet is not forwarded to the root when the forwarding node is further from the root node than the sending node.

11. The method of claim 6, wherein the delay is determined based on a relative distance to the root node between the forwarding node and the sending node.

12. The method of claim 11, wherein the delay is shorter when the forwarding node is closer to the root node.

13. The method of claim 6, wherein determining the probability of forwarding the packet to the root node is based on a number of times the forwarding node receives a same packet.

14. The method of claim 13, wherein the probability of forwarding the packet to the root node is inversely proportional to the number of times the forwarding node receives the same packet.

15. The method of claim 13, wherein the probability of forwarding the packet to the root node is 1/N, wherein N is the number of times the forwarding node receives the same packet.

16. A network routing method, comprising:

initializing the network by determining, for each node of the network, a number of hops to a root node;

determining, for a forwarding node that receives a packet form a sending node, whether to forward the packet to a root node;

delaying forwarding to the root node, wherein the delay in forwarding the received packet to the root node depends upon the number of hops separating the root node from the forwarding node and depends upon a relative distance to the root node between the forwarding node and the sending node; and

determining a probability of forwarding the packet to the root node.

17. A network routing system, comprising:

a controller;

the controller initializing the network such that, for each node of the network, a number of hops to a root node is determined;

the controller determining whether to forward a packet from a forwarding node to a root node;

the controller delaying forwarding the packet to the root node, wherein the delay in forwarding the packet to the root node depends upon the number of hops separating the root node from the forwarding node and depends upon a relative distance to the root node between the forwarding node and a sending node; and

the controller determining a probability of forwarding the packet to the root node based on a number of times the forwarding node receives the packet.

18. A machine-readable medium that provides instructions for network routing, the instructions, when executed by a processor, cause the processor to perform operations comprising:

initializing the network by determining, for each node of the network, a number of hops to a root node; and

delaying forwarding to the root node, for each node, of a received packet from a forwarding node;

wherein

the delay in forwarding the packet received to the root node from the forwarding node depends upon the number of hops separating the root node from the forwarding node.

19. A machine-readable medium that provides instructions for network routing, the instructions, when executed by a processor, cause the processor to perform operations comprising:

initializing the network by determining, for each node of the network, a number of hops to a root node;

determining, for a forwarding node that receives a packet from a sending node, whether to forward the packet to a root node;

determining a delay after which the packet is to be forwarded to the root node; and

determining a probability of forwarding the packet to the root node.