TECHNICAL FIELD

[0001] The present disclosure relates generally to wireless technologies and more specifically to forward-looking probabilistic statistical routing for wireless ad-hoc networks.

BACKGROUND

[0002] Unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section. [0003] A wireless ad-hoc network is a network of computers and devices (hereafter simply as "nodes") that are connected by wireless communication links (hereafter simply as "links"). As each link has a limited communication range, some nodes cannot communicate directly so they forward packets to each other via one or more cooperating intermediate nodes. A source node transmits a packet to a neighboring node with which it can communicate directly. The neighboring node in turn transmits the packet to one of its neighboring nodes, and so on until the packet is transmitted to a destination node. Each link that a packet is sent over is referred to as a hop, and the set of links that a packet travels over from the source node to the destination node is called a route or a path. Routes are determined by running a routing protocol on the wireless ad-hoc multi-hop network. Routes may be distributive determined at each node based on local information available to the node.

[0004] The links may be implemented with digital packet radios. The links may be lossy as a result of the use of inexpensive radios and low cost and low power requirements for the wireless ad-hoc network. Thus, what is needed is a routing protocol suitable for a wireless ad-hoc network with lossy links. SUMMARY

[0005] Some embodiments of the present disclosure may generally relate to methods for a node in a wireless network to forward a packet using a routing protocol. An example method may include receiving the packet from an other node, operating in a forward progress mode of the routing protocol, and sending the packet to the selected neighbor node. Operating in a forward progress mode of the routing protocol may further include identifying neighbor nodes and performing some operations for each identified neighbor node. Some example operations may include determining a progress value based on an immediate hop from the node to the identified neighbor node, determining a prospect value based on any consequent hop from the identified neighbor node toward a destination node, identifying a routing objection function value for the identified neighbor node based on one or more of the progress value and the prospect value, and selecting one of the identified neighbor- nodes as a selected neighbor node based on the identified routing objective function values.

[0006] Additional embodiments of the present disclosure may generally relate to methods for determining a routing objective function for a routing protocol in a wireless network that includes nodes. An example method may include collecting empirical data from the wireless network and building a statistical model of the wireless network from the empirical data. The example method may also include identifying one or more properties indicative of routing quality from the statistical model and applying statistical analysis to select one or more of the identified properties indicative of routing quality. The example method may further include applying statistical analysis to identify a routing objective function based on the selected properties and saving the identified routing objective function to nodes in the wireless network, wherein the nodes in the wireless network use the routing objective function to send packets to each other.

[0007] Some embodiments of the present disclosure may generally relate to a computer- readable storage medium encoded with computer-executable instructions for a node in a wireless network to forward a packet using a routing protocol. When the computer- executable instructions are executed by the node, the node is configured to receive the packet from an other node, operate in a forward progress mode of the routing protocol, and send the packet to the selected neighbor node. To operate in a forward progress mode of the routing protocol may further include identifying neighbor nodes and performing some operations for each identified neighbor node. Some example operations may include determining a progress value based on an immediate hop from the node to the identified neighbor node, determining a prospect value based on any consequent hop from the identified neighbor node toward a destination node, identifying a routing objection function value for the identified neighbor node based on one or more of the progress value and the prospect value, and selecting one of the identified neighbor nodes as a selected neighbor node based on the identified routing objective function values. [0008] The foregoing summary is illustrative only and is not intended to be in any way limiting. In addition to the illustrative aspects, embodiments, and features described above, further aspects, embodiments, and features will become apparent by reference to the drawings and the following detailed description. BRIEF DESCRIPTION OF THE DRAWINGS

[0009] The foregoing and other features of the present disclosure will become more fully apparent from the following description and appended claims, taken in conjunction with the accompanying drawings. Understanding that these drawings depict only several embodiments in accordance with the disclosure and are, therefore, not to be considered limiting of its scope, the disclosure will be described with additional specificity and detail through use of the accompanying drawings.

[0010] In the drawings:

Fig. 1 illustrates a wireless ad-hoc network utilizing a forward-looking probabilistic statistical routing (FPSR) protocol;

Fig. 2 is a flowchart of a method to determine a routing objective function

(ROF) of the FPSR protocol for the wireless network of Fig. 1 ;

Fig. 3 is a scatter plot of reception rates of links from sending nodes to receiving nodes as a function of the geometric distance between the sending and the receiving nodes based on example empirical data;

Fig. 4 is a plot of a monotonic kernel estimation of a function that maps the reception rats the forward links to reception rates of reverse links based on the example empirical data;

Figs. 5 and 6 are plots of the sorted relative quality of the transmitters and the receivers in the nodes, respectively, based on the example empirical data;

Fig. 7 shows an example of a compound reception rate for sending packets between two nodes;

Fig. 8 is a plot nf estimated costs of least cost paths from source nodes to destination nodes as a function of geometric distances between the source and the destination nodes based on the example empirical data;

Fig. 9 is a plot of ROF level sets of neighbor nodes with respect to change in normalized progress and normalized prospect;

Fig. 10 is a plot of ROF level sets of Fig. 9after statistical processing; Fig. 11 is a flowchart of a method for a current node n _c to execute the FPSR protocol to determine the neighbor node with the best ROF value to forward a packet;

Fig. 12 shows a pseudo code of an algorithm that summarizes a probabilistic approach for escaping the local;

Fig. 13 a flowchart of a method for implementing the algorithm of Fig. 12;

Fig. 14 illustrates an example node for implementing one or more embodiments of the FPSR protocol; and

Fig. 15 is a block diagram illustrating a computer program product for the node of Fig. 14, all arranged in accordance with at least some embodiments of the present disclosure.

DETAILED DESCRIPTION

[0011] In the following detailed description, reference is made to the accompanying drawings, which form-a part hereof. In the drawings, similar symbols may identify similar components, unless context dictates otherwise. The illustrative embodiments described in the detailed description, drawings, and claims are not meant to be limiting. Other embodiments may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented here. It will be readily understood that the aspects of the present disclosure, as generally described herein, and illustrated in the Figures, can be arranged, substituted, combined, and designed in a wide variety of different configurations, all of which are explicitly contemplated and make part of this disclosure.

[0012] This disclosure is drawn, inter alia, to methods, apparatus, computer programs, and systems related to routing protocols for wireless ad-hoc networks with lossy links.

[0013] Embodiments of the present disclosure generally relate to a method for designing a localized routing protocol for a wireless network based on statistical modeling and evaluation. One example localized routing protocol is the Forward-looking Probabilistic Statistical Routing (FPRR) protocol. The FPSR protocol may consider the properties and the impact of lossy links in the networks. The FPSR protocol may be forward-looking because it may consider the "progress" towards the destination node made in an immediate hop from a current node to a neighbor node, and the "prospect" from consequent hops towards the destination node after the immediate hop. In other words, progress may represent the estimated cost of the overall route while prospect may represent the estimate cost of the immediate node selection. Progress may be defined as the sum of a locally estimated cost from the current node to the neighbor node and a globally estimated cost from the neighbor node to the destination node. In one or more embodiments, prospect may be based on the estimated link quality of the next hop from the neighbor node, which may be based on the relative link quality of the neighbor node with respect to its neighbor nodes. A routing objective function (ROF) based on progress and prospect may be used to evaluate each neighbor node.

[0014] The FPSR protocol may be statistical because progress and prospect may be statistical measures. The FPSR protocol may be probabilistic because it may use probabilistic mechanisms to detect and escape from local minima in the routing (i.e., any neighbor node that does not have a neighbor node that is closer to the destination node than itself).

[0015] Fig. 1 illustrates a wireless network 100 utilizing the FPSR protocol in one or more embodiments of the present disclosure. Wireless network 100 includes nodes n _a , n _b , n _c , n _d , and n _s . [0016] The FPSR protocol is a distributed routing algorithm that may be executed locally at each node to determine the next hop in a route from a source node to a destination node. In a running example throughout the present disclosure, the FPSR protocol may be explained in the context of a current node n _c determining which of its neighbor nodes n _a and n _b to forward a packet that originated from a source node n _s and may be destined for a destination node n _d . Alternatively, current node n _c may send a packet on its own for destination node n _d .

[0017] Nodes n _a , n _b , n _c , and n _s may be wireless sensors, cellular telephones, laptops, computers, handheld computing devices, and other wireless devices. Destination node n _d may be a stationary gateway to an external internet. Current node n _c may include an antenna 102, a digital packet radio 104, a processor 106, and a memory 108 for storing the FPSR protocol. Processor 106 may execute the FPSR protocol from memory 108 and may be configured to utilize digital packet radio 104 with antenna 102 to send/receive packets to/from other nodes. Digital packet radio 104 may include a separate transmitter and receiver, or a transceiver when the transmitter and receiver functions are combined. For simplicity, other hardware and software components of current node n _c are not shown. Nodes n _a , n _b , n _d , and n _s may be similarly configured as current node n _c . Node ni is used hereafter denote any of the nodes. [0018] The FPSR protocol may be optimized to deliver a packet from current node n _c to destination node n _d using the minimal number of transmissions (including retransmissions). The FPSR protocol may have a small-state routing strategy where each node may utilize locally available information to select one of its neighbor nodes as the next node to send the packet. The locally available information may include one or more of a 2D location of the node and its neighbor nodes, the forward and reverse reception rates of links (forward and reverse links) between the node and its neighbor nodes, the forward and reverse reception rates of the links between its neighbor nodes and their neighbor nodes, and/or the 2D location of the destination. [0019] Fig. 2 is a flowchart of a method 200 for designing the FPSR protocol for wireless network 100 in one or more embodiments of the present disclosure. Method 200 includes one or more operations, functions, or actions illustrated by blocks 202, 204, 206, 208, 210, 212, 214, 216 and/or 218. Method 200 may be implemented with the assistance of a computer. [0020] Processing for method 200 may begin at block 202, where the method may collect empirical data from the wireless network. Continuing to block 204, the method may build a composite link model of the wireless network may to fit the collected empirical data.

Processing may continue at block 206, where the method may identify one or more geometric properties of neighbor nodes from the composite link model, where the identified geometric properties may increase the likelihood that the neighbor node is on a least cost path from a current node toward a destination node. Processing may proceed to block 208, where the method may identify one or more constellation properties of neighbor nodes in the composite link model, where the identified constellation properties may increase the likelihood that the neighbor node is on a least cost path from the current node toward the destination node. The method may continue at block 210, where the method may identify one or more communication properties of a link from the current node to a neighbor node in the composite link model, where the identified communication property may increase the likelihood that the neighbor node is on a least cost path from the current node toward the destination node. Proceeding to block 212, the method may apply statistical analyses to the identified properties to select those properties that may be suitable to guide routing. Continuing to block 214, the method may define normalized progress and normalized prospect from the selected properties. Proceeding to block 216, the method may apply statistical analysis to define a routing objective function (ROF) as a function of the normalized progress and the normalized prospect. Continuing to block 218, the method may save information for localized routing using the ROF to the nodes in the wireless network. Block 218 may be followed by block 202, where method 200 may be repeated.

[0021] In block 202, empirical data may be collected from wireless network 100 as follows. Each node may be adapted to broadcast a probe packet in a round robin fashion. The nodes in wireless network 100 may each be configured to record the probe packets received. From the empirical data, the reception rate of each link from a sending node to a receiving node and the geometric distance between the sending and the receiving node may be determined. The empirical data may be collected over a period of time or continuously. A learn and test method may be used where the empirical data may be collected until the reception rate of each link has settled to a consistent value. Periodically a smaller sample of the empirical data may be collected to determine if the reception rate of each link remains consistent with its prior value. If not, the empirical data may be collected until the reception rate of each link has settled to a consistent value.

[0022] If the wireless network has already been operational, the empirical data may be collected in the following manner. Nodes that have better links to neighbor nodes (e.g., have high reception rates) may transmit more for collecting empirical data often so they may be well modeled with sufficient empirical data as they are more likely to be used in any routing protocol. Also, nodes that have links that are difficult to model (e.g., the links have high temporal variability) may transmit more often so they may be well modeled with sufficient empirical data. Furthermore, nodes that have many neighbor nodes may transmit more often so many links may be well modeled with sufficient empirical data. Block 202 may be followed by block 204.

[0023] In block 204, various link models of wireless network 100 may be built to fit the empirical data as follows. A network designer/operator or a software program, such as one that employs machine learning software tools, may build the statistical models. The statistical models of wireless network 100 may be studied to determine properties that may be used for routing. The statistical models may be link models, radio models, channel models, traffic models, location models, and any combination thereof. One or more link models may be used to determine progress, and one or more radio models may be used to determine prospect. In one or more embodiments of the present disclosure, the link models of wireless network 100 may include one or more frequency link models, including, but not limited to one or more of: (i) a single link model, (ii) a forward and reverse link model, and/or (iii) an average cost per distance model. In one or more embodiments of the present disclosure, the radio models of wireless network 100 may include one or more frequency radio models, including, but not limited to, a speaking and listening qualities model. These models are described later after method 200.

[0024] In block 204, a cost metric may also be defined. The cost metric may quantify the cost of transmitting a single packet in terms of energy, bandwidth, and latency as described below. In the underlying communication protocol in wireless network 100, a sending node (hereafter "node n _A ") may be adapted to send a packet to a receiving node (hereafter "node n _B ") and wait for receipt of an acknowledgement packet from node n _B . The wait interval may be several times longer than the time required for node n _B to receive the packet and to send an acknowledgement back to node n _a . If node n _A does not receive an acknowledgement from node n _B after the expiration of the wait interval, node n _A may retransmit the packet to node n _B .

[0025] There may be a forward link from the transmitter of node n _A to the receiver of node n _B with an estimated forward reception rate P _Λ E, and a reverse link from the transmitter of node n _B to the receiver at node n _A with an estimated reverse reception rate P _BA . It may be assumed that there is no correlation between two consecutive transmissions. The estimated number of transmissions of a packet from node n _A to node n _B required for node n _B to successfully receive the packet may be expressed as 1/P _AS - The estimated number of transmissions of a packet from node n _A to node n _B required for node n _A to receive an acknowledgement from node n _B in reply may be denoted by FR _AB and may be defined as follows. pAB ^p BA

The estimated number of transmissions of an acknowledgement from node n _B to node n _A required for node n _A to successfully receive the acknowledgement may be denoted by BR _BA and may be defined as follows.

BRBA = T ^P TABfPB-A = j PB-A ⁽ 2 ⁾

The estimated total number of transmissions by both nodes n _A and n _B may be denoted by a compound reception rate (CRR _AB ) and may be defined as follows.

CRR _AB = FR _AB + BR _BA = -^- + -±- (3)

^P AB ^P BA ^P BA CRR _A B may be set as the estimated two-way link cost from node n _A to node n _B . An interesting observation is that FR _AB may be similar to BR _BA , but CRR _A B and CRRBA may be very different. Fig. 7 shows an example of CRR _A B for sending packets between nodes n _A and n _B , in accordance with the present disclosure. While FR _AB and BR _BA are both 10 based on reception rates P _A B and PB _A provided in Fig. 7, CRRAB is 20 and CRRBA is 11.

[0026] Referring back to Fig. 2, in block 206, one or more geometric properties of neighbor node n, that may increase the likelihood that neighbor node n* is on a least cost path from current node n _c toward destination node n _d may be identified from observing the link models. A network designer/operator or a software program that uses statistical rules, heuristic rules, or both, may identify the geometric properties. Geometric properties of neighbor node ni include one or more of the location coordinates, the reduction in geometric distance to destination node n _d , the normalized unexplored area, the weighted unexplored area, and any combination of these properties.

[0027] Location coordinates, (Xj, yι), of neighbor node ni may provide a complete specification of both its progress toward the destination node n _d as well as the area around neighbor node ni that is unknown to current node n _c .

[0028] The reduction in geometric distance to destination, DRi ₀ , from selecting neighbor node ni may be the difference between a first geometric distance, D _α j, from current node n _c to destination node n _d and a second geometric distance, D _id , from neighbor node n* to destination node n _d .

[0029] The normalized unexplored area, AUi, of neighbor node ni may be the area around neighbor node ni that is unknown to current node n _c . It may assume that after a certain geometric distance r, the links have a close to zero reception rate. Geometric distance r may be 12 meters in wireless network 100. The normalized unexplored area of neighbor node ni may be the area that is covered by the maximal communication range in a radius around neighbor node n* but does not include the maximal communication range radius around current node n _c . The normalized unexplored area of neighbor node ni may be approximated using the following trigonometric formula:

^ _{= B} r»~r»(g-sin(g» ₍₄₎ where q = 2 * arccosf— J and d is the geometric distance between current node n _c and neighbor node n,.

[0030] The weighted unexplored area, AUR,, of neighbor node n, may be a portion of the normalized unexplored area that is closer to destination node n _d than current node n _c . The weighted unexplored areas may be approximated using the formula: cos(θi) * AU _L (5) where O ₁ is the angle between a first line formed by current node n _c and destination node n _D , and a second line formed by current node n _c and destination node n,. Block 206 may be followed by block 208. [0031] In block 208, one or more constellation (graph topology) properties of neighbor node n, that may increase the likelihood that neighbor node n, is on a least cost path from current node n _c toward destination node n _d may be identified from observing the link models. A network designer/operator or a software program that uses statistical rules, heuristic rules, or both, may identify the constellation properties. Constellation properties include the number of common neighbor nodes between current node n _c and neighbor node n,, the geometric distance from each common neighbor node to destination node n _d , the normalized unexplored area of each common neighbor node, and any combination of these properties. The constellation properties may help to identify a path that passes two or more hops through known neighbor nodes since shorter links may be of better quality than long direct links. Block 208 may be followed by block 210.

[0032] In block 210, one or more communication properties of a link from current node n _c to a neighbor n, that may increase the likelihood that neighbor node n, is on a least cost path from current node n _c toward destination node n _d may be identified from observing the link models. A network designer/operator or a software program that uses statistical rules, heuristic rules, or both, may identify the communication properties. The communication properties include the estimated two-way link cost from current node n _c to neighbor n,, the speaking and listening qualities of neighbor node n,, and any combination of these properties.

[0033] The estimated two-way link cost from current node n _c to neighbor n,, C _α , may be equal to the CCR and may be rewritten as follows.

Pd is the estimated forward reception rate from the transmitter of current node n _c to the receiver of neighbor node n,, and P _ic is the estimated reverse reception rate from the transmitter of neighbor node n, to the receiver at current node n _c . [0034] The speaking and listening qualities of neighbor node nj, SL], may be the geometric mean of listening quality S(nι) and listening quality L(nι). Block 210 may be followed by block 212.

[0035] In block 212, statistical analyses may be applied to the identified properties to select those that may be suitable to guide routing. A network designer/operator or a software program that uses statistical rules, heuristic rules, or both, may select the properties. Monte Carlo (MC) simulations of wireless network 100 may be used to find the effects of each property on the overall efficiency of the routing. Each neighbor node n; may be given two coordinates: (i) a first coordinate that indicates the value (or relative ranking) of the targeted property, and (ii) a second coordinate that indicates the cost (or relative ranking) of the least cost path from current node n _c through neighbor node rtj to destination node n _d . The least cost path may be determined with the Floyd-Warshall algorithm, the Dijkstra algorithm, or a combination of the algorithms.

[0036] One to several millions of MC simulations may be run for each property by determining the least cost path between randomly selected source and destination nodes and tracking the coordinates of the neighbor nodes. Once the simulation data is collected, statistical techniques such as regression and kernel smoothing may be applied. Isotonic regression and isotonic density estimation may be used. The use of statistical analysis may result in a reduction of 3 orders of magnitude in the required amount of Monte Carlo simulation runs for obtaining a particular level of confidence. [0037] The properties may be analyzed by either building statistical models that predict routability from a property or by using consistency measures. Consistency may indicate the percentage of situations for which a higher value of a property corresponds to a smaller path and a lower value of the property coincides with a longer path. Both consistency values close to 100% and 0% may indicate a good predictor and the values close to 50% may indicate poor predictors since the change in the property does not affect the length of the path in a particular way. Based on the statistical models or the consistency measures, the selected properties may be the two-way link cost and the conditional speaker quality (described later). Block 212 may be followed by block 214.

[0038] In block 214, normalized progress and normalized prospect may be defined from the selected properties. A network designer/operator or a software program can use a combination of search and statistical software tools to find the best definition for a given objective and a wireless network or even in general.

[0039] Progress of a neighbor node n, may be defined as the estimated path cost from current node n _c to destination node n _d through neighbor node n,. Progress has two components: an estimated two-way link cost from current node n _c to neighbor node n,, and an average estimated path cost from neighbor node n, to destination node n _d . Normalized progress may be determined by dividing progress by the best (e.g., lowest) progress of all the neighbor nodes.

[0040] There may be ways to further refine the normalized progress. The estimated two- way link cost may have a higher weight than the average estimated path cost because the two-way link cost may be known more accurately and any localized routing scheme may not be able to determine a path as well as well as the optimal strategy. In one or more embodiments, the estimated two-way link cost and the average estimated path cost may be weighed equally to avoid over-tuning the FPSR protocol and to increase the robustness of the FPSR protocol. [0041] Normalized prospect of a neighbor node n, may capture the impact of the information that is available to current node n _c about what may be achieved in one hop immediately after the hop to neighbor node n,. The information may be related to the transmitter quality of each of the neighbor nodes, common neighbor nodes of current node n _c and neighbor node n,, the likelihood that significant and cost-effective progress toward destination node n _d can be made using neighbor node n, as the intermediate hop toward the common neighbor nodes, and the weighted unexplored area of neighbor node n,.

[0042] Normalized prospect may be defined as the conditional speaker (transmitter) quality (CSQ) of a neighbor node n,. The CSQ of neighbor node n, may be equal to the speaking quality of neighbor node n, if it has at least one neighbor node that provides more than a predetermined chance for a faster rate of progress toward the destination. To determine if neighbor node n, has a neighbor node that provides more than a predetermined chance for a faster rate of progress toward the destination, the difference between speaker qualifies of the two nodes is divided by the speaker quality of neighbor node n _s to see if the result is greater than the predetermined chance. The speaking qualities of neighboring nodes may be periodically exchanged with dedicated packets or be included in acknowledgment packets. The predetermined chance may be 50%. When neighbor node ni does not have at least one neighbor node that provides more than a predetermined chance for a faster rate of progress toward the destination, the CSQ of neighbor node n, may be set equal to zero. Alternatively, the normalized prospect may be set equal to the product of CSQ, normalized weighted unexplored area, and the normalized number of known neighbor nodes. Block 214 may be followed by block 216. [0043] In block 216, the ROF may be defined as a function of the normalized progress and the normalized prospect. A network designer/operator or a software program can use a search software tool to find the best definition for a given objective and a wireless network or even in general. The neighbor node with the best ROF value may be selected as the next node in the path to destination node n _d in the FPSR protocol. Monte Carlo simulations and statistical analysis may be used to determine the ROF. Fig. 9 shows the ROF level sets of neighbor nodes with respect to the difference in normalized progresses between current node n _c and neighbor node nι, and normalized prospect (CSQ), in accordance with the present disclosure. The darker area may indicate a higher percentage of the neighbor nodes belonging to the least cost path. [0044] To enhance robustness and to reduce the storage needs, the ROF level sets in Fig. 9 may be statistically approximated using the quadratic regression functions. Fig. 10 is a plot of ROF level sets of Fig. 9 after statistical processing, in accordance with the present disclosure. The quadratic regression functions of Fig. 10 may be stored at each node. The neighbor node that is below the largest number of the quadratic regression functions may be the node with the best ROF and may be selected as the node with next node in the path to destination node n _d . Block 216 may be followed by block 218.

[0045] In block 218, the information for localized routing using the ROF may be saved to the nodes in wireless network 100. The information may include one or more of the cost metric, the average estimated path cost function (Fig. 8), the equations for the normalized progress, the normalized prospect, the speaking quality, and the CSQ, an/or the quadratic regression functions of the ROF (Fig. 10).

[0046] SINGLE LINK MODEL [0047] Fig. 3 shows is a scatter plot of reception rates of links from sending nodes to receiving nodes as a function of the geometric distance between the sending and the receiving nodes based on example empirical data, in accordance with the present disclosure. A bold piecewise linear line shows an U monotonic regression fit of the data points in the scatter plot. It may be important to consider both the geometric distance and the reception rate of a particular link because there may be a range of reception rates for a given geometric distance and some longer links may have better reception ranges than some shorter links.

[0048] FORWARD AND REVERSE LINK MODEL [0049] There are two links between each pair of neighbor nodes: (1) a forward link from the transmitter of the first neighbor node to the receiver of the second neighbor node, and (2) a reverse link from the transmitter of the first neighbor node to the receiver at the second neighbor node. Fig. 4 shows a monotonic kernel estimation of a function that maps the RR of the forward link (x-axis) to the RR of a reverse link (y-axis) based on the example empirical data, in accordance with the present disclosure. The piecewise lines from the bottom to the top indicate that 12.5%, 25%, 50%, 75%, and 87.5% of the data points are respective below each of the lines. Even though link asymmetry exists, the forward links with high reception rates may have a higher probability of having high reception rates on the corresponding reverse links than forward links with low reception rates. [0050] SPEAKING AND LISTENING QUALITIES

[0051] The digital packet radios in the nodes may be of different qualities. The qualities of the transmitter and the receiver (or the transceiver, depending on the specific

implementation) of the digital packet radio of a node may be separately evaluated. The transmitter quality (hereafter "speaking quality") and the receiver quality (hereafter "listening quality") of a node ni may be defined as follows.

Kn _f ) = πj£i ^Nw yc£ (8)

S(rii) is the speaking quality of neighbor node n,, L(n{) is the listening quality of neighbor node nι, N _Ni is the total number of neighbor nodes of node ni where each neighbor node of node ni is denoted by n _k , k = 1 , .... N _N i, C _ik is the estimated two-way link cost from node n* to neighbor node n _k , and C _ki is the estimated two-way link cost from neighbor node n _k to node n _f . A cost metric for determining estimated two-way link costs based on the reception rates is described later.

[0052] Figs. 5 and 6 show the sorted relative quality of the transmitters and the receivers in the nodes, respectively, based on the example empirical data, in accordance with the present disclosure. The relative speaking or listening quality is defined as the average of S(nι) or L(rii). On the x-axis is the normalized speaking or listening quality of the transmitter or the receiver. On the y-axis is the smooth value of the cumulative distribution function (CDF). In some examples, the model of Figs. 5 and 6 is applicable for speaking and listening qualities less than or equal to approximately 0.65. It may be advantageous to send packets through some nodes than others because their radios are intrinsically better than the radios in other nodes.

[0053] AVERAGE COST PER DISTANCE MODEL

[0054] Fig. 8 shows a plot of estimated costs of least cost paths from source nodes to destination nodes as a function of geometric distances between the source and the destination nodes based on the example empirical data, in accordance with the present disclosure. The least cost path from a source node to a destination node may be determined from the Floyd-Warshall algorithm, the Dijkstra algorithm, or a combination of the algorithms. The estimated cost of a least cost path may be the sum of the estimated two-way link costs in the least cost path. A line in the plot may show a linear regression fit of the data points. As the geometric distance between the source and the destination nodes increases, the relative accuracy of the estimated cost of the least cost path may increase.

[0055] In addition to reception rates, autocorrelation values and cross-correlation values may be determined from the example empirical data. Based on their values, a temporal link model or a frequency-temporal link model may be constructed instead of the frequency link model described above.

Fig. 11 is a flowchart of a method 1100 for a current node n _c to execute the FPSR protocol to determine the neighbor node ni with the best ROF value to forward a packet in one or more embodiments of the present disclosure. Method 1100 may include one or more operations, functions, or actions illustrated by blocks 1102, 1104, 1106, 1108, 1110, and/or 1112. Processing for method 1100 may begin at block 1102. [0056] In block 1102, current node n _c may be adapted to determine locally available information including one or more of the location of current node n _c , the location of neighbor nodes, the location of destination node n _d , the estimated forward and reverse reception rates between current node n _c and neighbor nodes, and/or the speaking qualities of neighbors to the neighbor nodes.

[0057] Current node n _c may be adapted to determine one or more of the location of current node n _c , the location of neighbor nodes, the location of destination node n _d . The determination of one or more locations may be made based on a localization method that may employ acoustic, radio frequency (RF), light, or global positioning system (GPS) localization. The localization methods may use triangulation where some nodes have know positions or multilateration where most nodes have unknown positions. The locations of one or more of the nodes may also be provided by a system administrator 110 (Fig. 1) to each node.

[0058] Current node n _c may be adapted to determine the estimated forward and reverse reception rates between current node n _c and neighbor nodes as follows. In each round, current node n _c may be configured to send a probe packet to a neighbor node n, and wait for receipt of an acknowledgment packet from neighbor node n,. The wait interval may be longer than the time required for neighbor node n, to receive the probe packet and to send an acknowledgement packet back. When neighbor node n, receives the probe packet, it may send an acknowledgment packet to current node n _c . The acknowledgment packet may include information indicating the number of times neighbor node n, has received the probe packet. The round may be repeated for a number of times. The number of rounds may range from 20 for very good or very bad links to several hundreds for links of medium quality. This process may be performed continually, periodically, or on demand so that the forward and the reverse reception rates between current node n _c and neighbor nodes may be updated as needed.

[0059] As current node n _c knows how many probe packets it has sent and how many probe packets neighbor node n, has received, current node n _c can be configured to determine the estimated forward reception rate P _α to the neighbor nodes. As current node n _c also knows how many acknowledgments it has received and how many probe packets neighbor node n, has received, current node n _c can also be configured to determine the estimated reverse reception rate P, _c from neighbor node n, to current node n _c . [0060] From its neighbor nodes, current node n _c may be adapted to receive information about the speaking qualities of neighbor nodes from time to time. This speaking quality information may be included in the acknowledgment packets received from the neighbor nodes. Alternatively, each neighbor node may be configured to send a packet with this information periodically to current node n _c . Block 1102 may be followed by block 1104.

[0061] In block 1104, current node n _c may be configured to receive a packet destined for destination node n _d . Alternatively, current node n _c may itself have a packet it needs to send to destination node n _d . Block 1104 is optionally followed by block 1106.

[0062] In block 1106, current node n _c may be configured to determine the normalized progress for each of the neighboring nodes of current node n _c . As discussed above, the normalized progress for a neighbor node n, may be equal to the sum of the estimated two- way link cost from current node n _c to neighbor node n, and the average estimated path cost from neighbor node n, to destination node n _d . The estimated two-way link cost from current node n _c to neighbor node n, may be determined based on the estimated forward and revere reception rates P _α and P, _c . The average estimated path cost from neighbor node n, to destination node n _d may be determined from the function of Fig. 8 based on the geometric distance between neighbor node n, and destination node n _d . Block 1106 may be followed by block 1108.

[0063] In block 1108, current node n _c may be configured to determine the normalized prospect for each of the neighbor nodes. As described above, the normalized prospect for a neighbor node n, may be defined as the CSQ of neighbor node n,. The CSQ of neighbor node n, may be determined from the speaking quality of neighbor node n, and the speaking qualities of the neighbor's neighbor nodes as described above. Block 1108 may be followed by block 1110. [0064] In block 1110, current node n _c may be configured to determine the neighbor node with the best ROF value based on the change in the normalized progress and the normalized prospect values of the neighbor nodes. As described above, the neighbor node with the best ROF value may be the one located below the largest number of the quadratic regression functions of Fig. 10. Block 1110 may be followed by block 1112. [0065] In block 1112, current node n _c may be configured to send the packet to the neighbor node with the best ROF value. [0066] In routing, current node n _c may encounter a local minimum where the neighbor node with the best ROF is not closer to destination node n _d than current node n _c . To avoid local minima, the FPSR protocol may use one or more of the following mechanisms: (i) detection of a local minimum; (ii) measuring the current escape time t _e for escaping the local minimum ; (iii) measuring the overall routing time to for the packet; and/or (iv) selecting the preferred direction for the escape route. The first mechanism may be deterministic and the last three may be probabilistic. Other additional mechanisms may also be employed.

[0067] The FPSR protocol may operate in multiple modes: (i) forward progress mode or (ii) local minima escape mode. In both modes current node n _c may be configured to send the packet to the neighbor node with the best ROF. However, while in the forward progress mode, the FPSR protocol may be configured to target the real destination node n _d . In the local minima escape mode, the FPSR protocol may be configured to target a virtual destination node. The position of the virtual destination may be on the same geometric distance as the real destination node n _d from current node n _c but its angle may increase from approximately 0 to approximately 90 degrees as the overall routing time t ₀ increases. Both the overall routing time t ₀ and the current escape time t _e may be measured using probabilistic mechanisms.

[0068] The transition from the forward progress mode to the local minima escape mode may be triggered when a message to current node n _c is determined to be the neighbor node with the best ROF. The transition from the local minima escape mode to the forward progress mode may be triggered when a predefined maximal escape time is determined to expire.

[0069] Fig. 12 shows a pseudo code of an algorithm 1 that summarizes a probabilistic approach for escaping the local minima in one or more embodiments of the present disclosure. In the illustrated algorithm, maximal escape time k _em and maximal overall routing time k _om may denote predefined maximal allowed times for the current escape time t _e and the overall routing time t ₀ , respectively. State bits (1+k _o +k _e ) may be included in each packet where one mode state bit indicates whether the FPSR protocol is in the forward progress mode or the local minima escape mode, one or more state bits k _e indicate the current escape time t _e , and one or more state bits k _o indicate the overall routing time t ₀ . Both state bits k _o and state bits k _e may be 0 or more. A probabilistic timing mechanism, denoted by probability function prob() in lines 7 and 14 of algorithm 1 may be used to reduce the required number of state bits k _e and k ₀ used for storing current escape time t _e and overall routing time t ₀ , respectively. For wireless network 100, the probabilities for incrementing state bits k _o and state bits k _e may be on the order of approximately 0.1 , and approximately 0.2 to approximately 0.5, respectively. The probabilities may be reduced for larger wireless networks and increased for smaller wireless networks. The probability for state bits k _e may be reduced as its value increases for very large and non-uniform wireless networks. State bits k ₀ may be increased when state bits k _e reach its maximal value and is reset. The number of bits and the probabilities may be determined statistically from the example empirical data. In some examples, state bits k _o may be two bits and state bits k _e may be one bit. [0070] Fig. 13 is a flowchart of a method 1300 for implementing the algorithm of Fig. 12 in accordance with one or more embodiments of the present disclosure. Method 2100 includes one or more operations, functions, or actions as illustrated by blocks 1302, 1304, 1306, 1308, 1310, 1312, 1314, 1316, 1318, 1320, 1322, 1324, 1326, 1328, 1330, and/or 1332. Processing for method 1300 may begin at block 1302. [0071] In block 1302, current node n _c may be adapted to receive and parse a packet for source node n _s , destination node n _d , the sending node (the neighbor node that just sent the packet to the current node n _c ), the mode of the FPSR protocol, overall routing time t ₀ , and/or current escape time t _e . As described above, the mode of the FPSR protocol may be represented by one mode state bit, overall routing time t _o may be represented by state bits ko, and current escape time t _e may be represented by state bits k _e . Block 1302 may be followed by block 1304.

[0072] In block 1304, current node n _c may be configured to determine if overall routing time t ₀ is greater than maximal overall routing time k _om . When overall routing time t ₀ is greater than maximal overall routing time k _om , block 1304 may be followed by block 1306.

Otherwise block 1304 may be followed by block 1308 when the overall routing time t ₀ fails to be greater than maximal overall routing time k _Om .

[0073] In block 1306, current node n _c may be configured to abandon delivery of the packet by discarding the packet. Current node n _c may also be arranged to send an error packet to source node n _s to indicate that the delivery of the packet has failed. Block 1306 may loop back to block 1302 to process another packet.

[0074] In block 1308, current node n _c may be arranged to determine if the FPSR protocol is in the forward progress mode or the local minima escape mode. When the FPSR protocol is determined to be in the forward progress mode, block 1308 may be followed by block 1310. When the FPSR protocol is determined to be in the local minima escape mode, block 1308 may be followed by block 1320.

[0075] In block 1310, current node n ₀ may be arranged to identify the neighbor node with the best ROF for destination node n _d as previously described in blocks 1104 to 1110 of Fig. 11. Block 1310 may be followed by block 1312.

[0076] In block 1312, current node n _c may be arranged to determine if the neighbor node with the best ROF for destination node n _d is also the sending node (the neighbor node that just sent the packet to the current node n _c ). When the neighbor node with the best ROF for destination node n _d is also the sending node, current node n _c may have found a local minimum and block 1312 may be followed by block 1320. Otherwise block 1312 may be followed by block 1314 when the sending node is not determined to be the neighbor node with the best ROF.

[0077] In block 1314, current node n _c may be arranged to determine if the best ROF for destination node n _d is better than a threshold Thres _R0F - When the best ROF for destination node n _d is determined to be better than threshold Thres _R0F , block 1314 may be followed by block 1316. For the ROF defined in Fig. 10, the best ROF may be better when it is smaller than threshold Thres _R0 F- Otherwise block 134 may be followed by block 1320 when the best ROF for destination node n _d is not determined to be better than threshold Thres _R o _F - [0078] In block 1316, current node n _c may be configured to increment overall routing time to in the packet with a probability function. As described above, overall routing time to may be represented by two state bits k ₀ and the probability for the probability function may be on the order of approximately 0.1. Block 1316 may be followed by block 1318.

[0079] In block 1318, current node n _c may be configured to send the packet to the neighbor node with the best ROF for destination node n _d . Block 1318 may loop back to block 1302 to process another packet.

[0080] In block 1320, current node n _c may be adapted to enter the local minima escape mode of the FPSR protocol. Current node n _c may change the mode state bit in the packet from indicating the forward progress mode to the local minima escape mode. Block 1320 may be followed by block 1322. [0081] In block 1322, current node n _c may be configured to increment overall routing time t ₀ and current escape time t _e in the packet with respective probability functions. As described above, delivery time t _o may be two k ₀ state bits and the probability for the probability function may be on the order of approximately 0.1 , and current escape time t _e may be one k _e state bit and the probability for the probability function may be on the order of approximately 0.2 to approximately 0.5. Block 1322 may be followed by block 1324.

[0082] In block 1324, current node n _c may be arranged to determine if current escape time t _e is greater than maximal escape time k _em . When current escape time t _e is determined to be greater than maximal escape time k _em , block 1324 may be followed by block 1326. Otherwise block 1324 may be followed by block 1328 when the current escape time t _e is determined to not be greater than maximal escape time k _em -

[0083] In block 1326, current node n _c may arranged to adapt the FPSR protocol to transition from the local minima escape mode to the progress forward mode at the next neighbor node in the route. Current node n _c may be arranged to change the mode state bit in the packet from indicating the local minima local escape mode to the forward progress mode and set current escape time t _e equal to zero. Block 1326 may be followed by block 1328.

[0084] In block 1328, current node n _c may be arranged to determine the position of a virtual destination node. As described above, the virtual destination node may be determined to be located at the same geometric distance as destination node n _d from current node n _c and may have an angle that increases from approximately 0 to approximately 90 degrees as overall routing time t ₀ increases. Block 1328 may be followed by block 1330.

[0085] In block 1330, current node n _c determines the neighbor node with the best ROF for the virtual destination node as described in blocks 1104 to 1110 of Fig. 11. Block 1330 may be followed by block 1332. [0086] In block 1332, current node n _c sends the packet to the neighbor node with the best ROF for the virtual destination node. Block 1332 may loop back to block 1302 to process another packet.

[0087] In one or more embodiments of the present disclosure, the FPSR protocol may select a subset of the links with a particular quality and treat all of them as perfect links while the other links may be considered non-operational. Two prime candidates may be links with high reception rate and links which have high ratio of distance (between the two nodes) to the two-way link cost. Links that have high ratio of distance to the two-way link cost may be links with a ratio higher than 0.3 m per transmission.

[0088] Fig. 14 illustrates an example node 1400 for implementing one or more

embodiments of the FPSR protocol of the present disclosure. Node 1400 may include a processor 1402, memory 1404, and/or one or more drives 1406. Drives 1406 may be configured to provide storage of computer readable instructions, data structures, program modules, content, and other data for node 1400. Drives 1406 may include an operating system 1408, the FPSR protocol 1412, and/or data 1414. Node 1400 may further include an input interface 1416 through which commands and data may be entered. Input devices may be coupled to the input interface 1416, and may comprise an electronic digitizer, a microphone, a keyboard or a pointing device, commonly referred to as a mouse, trackball or touch pad. Other example input devices may include a joystick, game pad, satellite dish, scanner, or the like.

[0089] These and other input devices may be coupled to processor 1402 through the input interface 1416 that may be coupled to a system bus 1418, but may be coupled by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). Node 1400 may also include other peripheral output devices such as speakers and video displays which may be coupled through an output interface 1420 or the like.

[0090] Node 1400 may communicate to other nodes in wireless network 100 through a digital packet radio 1422. The other nodes may be a personal computer (PC), a server, a router, a network PC, a mobile phone, a peer device, or other common network node, and may include many or all of the elements described above relative to node 1400. Wireless network 100 may be a wireless sensor network, a wireless mesh network, or another wireless ad-hoc network. According to one or more embodiments, node 1400 may be coupled to wireless network 100 and configured such that processor 1402 may perform the FPSR protocol 1412.

[0091] Fig. 15 is a block diagram illustrating a computer program product 1500 for node 1400, arranged in accordance with one or more embodiments of the present disclosure. Computer program product 1500 may include one or more sets of instructions 1502 for executing the methods of the FPSR protocol. Computer program product 1500 may be transmitted in a signal bearing medium 1504 or another similar communication medium 1506. Computer program product 1500 may be recorded in a computer readable medium 1508 or another similar recordable medium 1510.

[0092] There is little distinction left between hardware and software implementations of aspects of systems; the use of hardware or software is generally (but not always, in that in certain contexts the choice between hardware and software can become significant) a design choice representing cost vs. efficiency tradeoffs. There are various vehicles by which processes and/or systems and/or other technologies described herein can be effected (e.g., hardware, software, and/or firmware), and that the preferred vehicle will vary with the context in which the processes and/or systems and/or other technologies are deployed. For example, if an implementer determines that speed and accuracy are paramount, the implementer may opt for a mainly hardware and/or firmware vehicle; if flexibility is paramount, the implementer may opt for a mainly software implementation; or, yet again alternatively, the implementer may opt for some combination of hardware, software, and/or firmware. [0093] The foregoing detailed description has set forth various embodiments of the devices and/or processes via the use of block diagrams, flowcharts, and/or examples. Insofar as such block diagrams, flowcharts, and/or examples contain one or more functions and/or operations, it will be understood by those within the art that each function and/or operation within such block diagrams, flowcharts, or examples can be implemented, individually and/or collectively, by a wide range of hardware, software, firmware, or virtually any combination thereof. In one embodiment, several portions of the subject matter described herein may be implemented via Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs), digital signal processors (DSPs), or other integrated formats. However, those skilled in the art will recognize that some aspects of the embodiments disclosed herein, in whole or in part, can be equivalents implemented in integrated circuits, as one or more computer programs running on one or more computers (e.g., as one or more programs running on one or more computer systems), as one or more programs running on one or more processors (e.g., as one or more programs running on one or more microprocessors), as firmware, or as virtually any combination thereof, and that designing the circuitry and/or writing the code for the software and or firmware would be well within the skill of one of skill in the art in light of this disclosure. In addition, those skilled in the art will appreciate that the mechanisms of the subject matter described herein are capable of being distributed as a program product in a variety of forms, and that an illustrative embodiment of the subject matter described herein applies regardless of the particular type of signal bearing medium used to actually carry out the distribution. Examples of a signal bearing medium include, but are not limited to, the following: a recordable type medium such as a floppy disk, a hard disk drive, a Compact Disc (CD), a Digital Video Disk (DVD), a digital tape, a computer memory, etc.; and a transmission type medium such as a digital and/or an analog communication medium (e.g., a fiber optic cable, a waveguide, a wired communications link, a wireless communication link, etc.).

[0094] Those skilled in the art will recognize that it is common within the art to describe devices and/or processes in the fashion set forth herein, and thereafter use engineering practices to integrate such described devices and/or processes into data processing systems. That is, at least a portion of the devices and/or processes described herein can be integrated into a data processing system via a reasonable amount of

experimentation. Those having skill in the art will recognize that a typical data processing system generally includes one or more of a system unit housing, a video display device, a memory such as volatile and non-volatile memory, processors such as microprocessors and digital signal processors, computational entities such as operating systems, drivers, graphical user interfaces, and applications programs, one or more interaction devices, such as a touch pad or screen, and/or control systems including feedback loops and control motors (e.g., feedback for sensing position and/or velocity; control motors for moving and/or adjusting components and/or quantities). A data processing system may be implemented utilizing any suitable commercially available components, such as those that may be found in data computing/communication and/or network computing/communication systems.

[0095] The herein described subject matter sometimes illustrates different components contained within, or connected with, different other components. It is to be understood that such depicted architectures are merely exemplary, and that in fact many other architectures can be implemented which achieve the same functionality. In a conceptual sense, any arrangement of components to achieve the same functionality is effectively "associated" such that the desired functionality is achieved. Hence, any two components herein combined to achieve a particular functionality can be seen as "associated with" each other such that the desired functionality is achieved, irrespective of architectures or intermedial components. Likewise, any two components so associated can also be viewed as being "operably connected", or "operably coupled", to each other to achieve the desired functionality, and any two components capable of being so associated can also be viewed as being "operably couplable", to each other to achieve the desired functionality. Specific examples of operably couplable include but are not limited to physically mateable and/or physically interacting components and/or wirelessly interactable and/or wirelessly interacting components and/or logically interacting and/or logically interactable components.

[0096] With respect to the use of substantially any plural and/or singular terms herein, those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.

[0097] It will be understood by those within the art that, in general, terms used herein, and especially in the appended claims (e.g., bodies of the appended claims) are generally intended as "open" terms (e.g., the term "including" should be interpreted as "including but not limited to," the term "having" should be interpreted as "having at least," the term "includes" should be interpreted as "includes but is not limited to," etc.). It will be further understood by those within the art that if a specific number of an introduced claim recitation is intended, such an intent will be explicitly recited in the claim, and in the absence of such recitation no such intent is present. For example, as an aid to understanding, the following appended claims may contain usage of the introductory phrases "at least one" and "one or more" to introduce claim recitations. However, the use of such phrases should not be construed to imply that the introduction of a claim recitation by the indefinite articles "a" or "an" limits any particular claim containing such introduced claim recitation to inventions containing only one such recitation, even when the same claim includes the introductory phrases "one or more" or "at least one" and indefinite articles such as "a" or "an" (e.g., "a" and/or "an" should typically be interpreted to mean "at least one" or "one or more"); the same holds true for the use of definite articles used to introduce claim recitations. In addition, even if a specific number of an introduced claim recitation is explicitly recited, those skilled in the art will recognize that such recitation should typically be interpreted to mean at least the recited number (e.g., the bare recitation of "two recitations," without other modifiers, typically means at least two recitations, or two or more recitations). Furthermore, in those instances where a convention analogous to "at least one of A, B, and C, etc." is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., "a system having at least one of A, B, and C" would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). In those instances where a convention analogous to "at least one of A, B, or C, etc." is used, in general such a construction is intended in the sense one having skill in the art would understand the convention (e.g., "a system having at least one of A, B, or C" would include but not be limited to systems that have A alone, B alone, C alone, A and B together, A and C together, B and C together, and/or A, B, and C together, etc.). It will be further understood by those within the art that virtually any disjunctive word and/or phrase presenting two or more alternative terms, whether in the description, claims, or drawings, should be understood to contemplate the possibilities of including one of the terms, either of the terms, or both terms. For example, the phrase "A or B" will be understood to include the possibilities of "A" or "B" or "A and B."

[0098] While various aspects and embodiments have been disclosed herein, other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting, with the true scope and spirit being indicated by the following claims.