Coordinated convergecast for AD HOC wireless networks
View Patent ↗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.
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 forwarding node, a packet received from a sending node, the forwarding node receiving the packet from the sending node and forwarding to the root 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 2 +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 the root node;
determining a delay, by the forwarding node, after which the packet received by the sending node is to be forwarded by the forwarding node to the root node; and
determining a probability of forwarding the packet to the root node and forwarding the packet to the root node based on the determined probability.
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 the root node;
determining, for a forwarding node that receives a packet from a sending node, whether to forward the packet to the root node;
delaying forwarding the packet received from the sending node by the forwarding node 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 and forwarding the packet to the root node based on the determined probability.
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 received from a sending node from a forwarding node to the root node;
the controller delaying forwarding the packet received from a sending node by the forwarding node 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 the sending node;
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; and
the controller forwarding the packet to the root node based on the determined probability.
18. A machine-readable medium that stores instructions provided 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 forwarding node, a packet received from a sending node, the forwarding node receiving the packet from the sending node and forwarding to the root 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 stores instructions provided 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 the root node;
determining a delay after which the packet received from the sending node is to be forwarded by the forwarding node to the root node; and
determining a probability of forwarding the packet to the root node and forwarding the packet to the root node based on the determined probability.