Forward-looking probabilistic statistical routing for wireless ad-hoc networks with lossy links
View Patent ↗Techniques related to a localized routing approach are generally described where the number of transmissions, the maximum number of transmission per node, effective bandwidth, the latency, overall energy consumption, the maximum energy consumption, or other individual or composite objective in a wireless network may be optimized. The localized routing approach may use a metric that combines immediate progress benefit and expense with a statistics-based forward looking estimation of future routing properties and cost. The protocol may also employ a combination of probabilistic and deterministic mechanism to detect and escape local minima.
1. A method for a node in a wireless network to forward a packet using a routing protocol, the method comprising:
receiving the packet from another node; and
operating in a forward progress mode of the routing protocol, comprising:
identifying neighbor nodes, for each identified neighbor node:
determining a progress value based on an immediate hop from the node to the identified neighbor node, comprising determining a first expected cost of sending the packet from the node to the identified neighbor node as Cc i , wherein Cc i is given as:
C
ci
=
1
P
ci
P
ic
+
1
P
ic
,
where P Ci is a probability of a successful packet transmission from the node to the identified neighbor node, and P ic is a probability of a successful packet transmission from the identified neighbor node to the node;
determining a prospect value based on any consequent hop from the identified neighbor node toward a destination node; and
identifying a routing objection function value for the identified neighbor node based on one or more of the progress value and the prospect value;
selecting one of the identified neighbor nodes as a selected neighbor node based on the identified routing objective function values; and
sending the packet to the selected neighbor node.
2. The method of claim 1 , wherein determining the progress value comprises:
determining a second expected cost of sending the packet from the identified neighbor node toward the destination node; and
summing the Cc i first and the second expected cost.
3. The method of claim 2 , wherein determining the second expected cost comprises:
determining an average expected cost from the identified neighbor node to the destination node based on empirical data collected from the wireless network.
4. The method of claim 1 , wherein determining the prospect value comprises:
determining when a neighbor node of the identified neighbor node provides a rate of progress toward the destination node that is faster by a predetermined amount than a rate of progress provided by the identified neighbor node toward the destination node;
when a neighbor node of the identified neighbor node provides a rate of progress toward the destination node that is faster by the predetermined amount than the rate of progress provided by the identified neighbor node toward the destination node, setting the prospect value equal to a transmitter quality value of the identified neighbor node, the transmitter quality value of the identified neighbor node being based on the empirical data; and
setting the prospect value equal to zero when no neighbor node of the identified neighbor node provides a rate of progress toward the destination node that is faster by the predetermined amount than the rate of progress provided the identified neighbor node toward the destination node.
5. The method of claim 1 , further comprising:
parsing the packet to determine an overall routing time; and
when the overall routing time is determined to be greater than a maximal routing time:
dropping the packet to the destination node; and
sending another packet to a source node of the packet, the other packet indicating that the packet has been dropped.
6. The method of claim 1 , further comprising:
parsing the packet to determine an overall routing time; and
incrementing the overall routing time with a probability function.
7. The method of claim 1 , further comprising:
parsing the packet to identify one or more of an overall routing time, a current escape time, and a mode of the routing protocol, wherein the mode of the routing protocol is either the forward progress mode or an escape mode;
when the packet is identified with the forward progress mode, adapting the routing protocol to operate in the forward progress mode;
when the packet is identified with the escape mode, adapting the routing protocol to operate in the escape mode, the escape mode comprising:
incrementing the overall routing time and the current escape time in the packet;
determining a virtual destination node; and
sending the packet to one of the identified neighbor nodes based on routing objective function values of the identified neighbor nodes for the virtual destination node.
8. The method of claim 7 , wherein the duration of the overall routing time and the current escape time are incremented by probability functions.
9. The method of claim 7 , wherein the escape mode of the routing protocol further comprises:
determining when the current escape time is greater than a maximal escape time; and
when the current escape time is determined to be greater than the maximal escape time, changing the mode of the routing protocol recorded in the packet to the forward progress mode of the routing protocol.
10. The method of claim 7 , wherein the forward progress mode further comprises:
determining when the selected neighbor node is the other node;
when the selected neighbor node is the other node:
changing the mode of the routing protocol recorded in the packet to the escape mode of the routing protocol; and
adapting the routing protocol to operate in the escape mode.
11. The method of claim 10 , wherein determining the virtual destination node comprises:
placing the virtual destination node at a distance from the node equal to a distance from the node to the destination node; and
placing the virtual destination node at an angle from a line defined between the node and the destination node, wherein the angle is based on the overall routing time.
12. A non-transitory computer-readable storage medium encoded with computer-executable instructions for a node in a wireless network to forward a packet using a routing protocol, the instructions comprising:
receiving the packet from another node; and
operating in a forward progress mode of the routing protocol, comprising:
identifying neighbor nodes, for each identified neighbor node:
determining a progress value based on an immediate hop from the node to the identified neighbor node, comprising determining a first expected cost of sending the packet from the node to the identified neighbor node as Cc i , wherein Cc i is given as:
C
ci
=
1
P
ci
P
ic
+
1
P
ic
,
where P Ci is a probability of a successful packet transmission from the node to the identified neighbor node and P iC is a probability of a successful packet transmission from the identified neighbor node to the node;
determining a prospect value based on any consequent hop from the identified neighbor node toward a destination node; and
identifying a routing objection function value for the identified neighbor node based on one or more of the progress value and the prospect value;
selecting one of the identified neighbor nodes as a selected neighbor node based on the identified routing objective function values; and
sending the packet to the selected neighbor node.
13. The non-transitory computer-readable storage medium of claim 12 , wherein the instructions further comprise:
parsing the packet to identify one or more of an overall routing time, a current escape time, and a mode of the routing protocol, wherein the mode of the routing protocol is either the forward progress mode or an escape mode;
when the packet is identified with the forward progress mode, adapting the routing protocol to operate in the forward progress mode;
when the packet is identified with the escape mode, adapting the routing protocol to operate in the escape mode, the escape mode comprising:
incrementing the overall routing time and the current escape time in the packet;
determining a virtual destination node; and
sending the packet to one of the identified neighbor nodes based on routing objective function values of the identified neighbor nodes for the virtual destination node.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the duration of the overall routing time and the current escape time are incremented by probability functions.
15. The non-transitory computer-readable storage medium of claim 13 , wherein the instructions for the forward progress mode further comprise:
determining when the selected neighbor node is the other node;
when the selected neighbor node is the other node:
changing the mode of the routing protocol recorded in the packet to the escape mode of the routing protocol; and
adapting the routing protocol to operate in the escape mode.