US-12627584-B2 - Determining network reliability using message success rates

US12627584B2US 12627584 B2US12627584 B2US 12627584B2US-12627584-B2

Abstract

Techniques for determining network reliability using message success rates include receiving, by a first node and for a plurality of respective potential parent nodes, respective accumulated uplink message success rates, wherein a respective accumulated uplink message success rate for a respective potential parent node indicates a probability of successfully transmitting messages from that respective potential parent node to a target destination; determining, by the first node, respective local uplink message success rates for the plurality of respective potential parent nodes, wherein a respective local uplink message success rate indicates a probability of successfully transmitting messages from the first node to that respective potential parent node; and selecting, by the first node based on the respective accumulated uplink message success rates and the respective local uplink message success rates, a first respective potential parent node from the plurality of respective potential parent nodes as a parent node.

Inventors

Thomas F. Uhling
Keith Wayne Barnes

Assignees

ITRON, INC.

Dates

Publication Date: 20260512
Application Date: 20240802

Claims (20)

1 . A method comprising: receiving, by a first node and for a plurality of respective potential parent nodes, respective accumulated uplink message success rates, wherein a respective accumulated uplink message success rate for a respective potential parent node indicates a probability of successfully transmitting messages from that respective potential parent node to a target destination; determining, by the first node, respective local uplink message success rates for the plurality of respective potential parent nodes, wherein a respective local uplink message success rate indicates a probability of successfully transmitting messages from the first node to that respective potential parent node; and selecting, by the first node based on the respective accumulated uplink message success rates and the respective local uplink message success rates, a first respective potential parent node from the plurality of respective potential parent nodes as a parent node.
2 . The method of claim 1 , further comprising computing, by the first node, respective second accumulated uplink message success rates based on the respective local uplink message success rates and the respective accumulated uplink message success rates, wherein a respective second accumulated uplink message success rate indicates a probability of successfully transmitting messages from the first node to the target destination through the respective potential parent node.
3 . The method of claim 2 , wherein selecting the first respective potential parent node as the parent node comprises determining that a respective second accumulated message success rate associated with the first respective potential parent node is higher than respective second accumulated uplink message success rates associated with other respective potential parent nodes from the plurality of respective potential parent nodes.
4 . The method of claim 2 , further comprising transmitting, by the first node, a respective second accumulated message success rate associated with the first respective potential parent node to a third node.
5 . The method of claim 1 , wherein selecting the first respective potential parent node as the parent node comprises: determining that a first respective local uplink message success rate associated with the first respective potential parent node is greater than a second respective local uplink message success rate associated with a second respective potential parent node included in the plurality of respective potential parent nodes; and determining that a first respective accumulated uplink message success rate associated with the first respective potential parent node is less than a second respective accumulated uplink message success rate associated with the second respective potential parent node.
6 . The method of claim 1 , further comprising storing a respective accumulated uplink message success rate and a respective local uplink message success rate associated with the first respective potential parent node as an entry in a table, wherein the entry is associated with the first respective potential parent node.
7 . The method of claim 1 , further comprising: receiving, by the first node and for respective potential parent nodes from the plurality of respective potential parent nodes, respective accumulated downlink message success rates, wherein a respective accumulated downlink message success rate for the respective potential parent node indicates a probability of successfully receiving, at that respective potential parent node, a message from the target destination; and determining, by the first node, respective local downlink message success rates for the plurality of respective potential parent nodes, wherein a respective local downlink message success rate indicates a probability of successfully receiving, at the first node, messages transmitted by that respective potential parent node.
8 . The method of claim 7 , further comprising: computing, by the first node, respective combined accumulated message success rates for the respective potential parent nodes based on the respective accumulated downlink message success rates and the respective accumulated uplink message success rates.
9 . The method of claim 1 , wherein selecting the first respective potential parent node as the parent node comprises filtering the plurality of respective potential parent nodes based on one or more message success rate criteria.
10 . The method of claim 2 , wherein selecting the first respective potential parent node as the parent node further comprises filtering the plurality of respective potential parent nodes based on one or more hierarchical secondary selection criteria.
11 . One or more non-transitory computer-readable media storing instructions that, when executed by one or more processors at a first node device in a mesh network, cause the one or more processors to perform operations comprising: receiving respective path transmit success rates for a plurality of candidate parent node devices, wherein a respective path transmit success rate for a respective candidate parent node device indicates a likelihood that a data packet transmitted by the respective candidate parent node device to a destination device via a respective path will successfully be received at the destination device; determining respective local transmit success rates for the plurality of candidate parent node devices, wherein a respective local transmit success rate indicates for the respective candidate parent node device indicates a likelihood that a data packet transmitted by the first node device will successfully be received at the respective candidate parent node device; and choosing a second node device as a parent node device for the first node device based on the respective local transmit success rates and the respective path transmit success rates.
12 . The one or more non-transitory computer-readable media of claim 11 , wherein the operations further comprise determining, based on the respective local transmit success rates and the respective path transmit success rates, respective second path transmit success rates, wherein a respective second path transmit success rate for the respective candidate parent node device indicates a likelihood that a packet transmitted by the first node device to the destination device via the respective candidate parent node device and the respective path will be successfully received at the destination device.
13 . The one or more non-transitory computer-readable media of claim 12 , wherein choosing the second node device as the parent node device for the first node device comprises determining that a respective second path transmit success rate associated with the second node device is higher than respective second path transmit success rates associated with other node devices from the plurality of candidate parent node devices.
14 . The one or more non-transitory computer-readable media of claim 11 , wherein the operations further comprise: determining respective path receive success rates for the plurality of candidate parent node devices, wherein a respective path receive success rate for the respective candidate parent node device indicates a likelihood that a packet transmitted by the destination device via a reverse of the respective path and the respective candidate parent node device will be successfully received at the first node device; wherein choosing the second node device as the parent node device for the first node device is further based on the respective path receive success rates.
15 . The one or more non-transitory computer-readable media of claim 14 , wherein the operations further comprise: calculating respective combined path success rates for the plurality of candidate parent node devices based on the respective path transmit success rates and the respective path receive success rates; wherein the second node device has a highest respective combined path success rate from the respective combined path receive success rates.
16 . The one or more non-transitory computer-readable media of claim 11 , wherein choosing the second node device as the parent node device to the first node device comprises filtering the plurality of respective candidate parent node devices based on one or more hierarchical secondary selection criteria.
17 . A network device comprising: one or more processors; and a memory storing instructions that when executed by the one or more processors causes the network device to perform operations comprising: receiving respective accumulated transmit reliability rates for a plurality of neighbor devices to the network device in a mesh network, wherein a respective transmit reliability rate for a respective neighbor device indicates a probability that network traffic transmitted by the respective neighbor device will reach a destination network device; determining respective local transmit reliability rates for the plurality of neighbor devices, wherein a respective local transmit reliability rate for the respective neighbor device indicates a probability that network traffic transmitted by the network device will reach the respective neighbor device; and selecting one of the plurality of neighbor devices to be a parent device to the network device based on the respective local transmit reliability rates and the respective accumulated transmit reliability rates.
18 . The network device of claim 17 , wherein the operations further comprise: determining, based on the respective local transmit reliability rates and the respective accumulated transmit success rates, respective second accumulated transmit reliability rates, wherein a respective second accumulated transmit reliability rate for the respective neighbor device indicates a probability that network traffic transmitted via the respective neighbor device will reach the destination network device; wherein the selected neighbor device has a greatest respective second accumulated transmit reliability rate.
19 . The network device of claim 17 , wherein the operations further comprise: determining respective accumulated receive reliability rates for the plurality of neighbor devices, wherein a respective accumulated receive reliability rate for the respective neighbor device indicates a probability that network traffic transmitted by the destination network device via the respective neighbor device will reach the network device; wherein selecting the one of the plurality of neighbor devices to be the parent device is further based on the respective accumulated receive reliability rates.
20 . The network device of claim 17 , wherein selecting the one of the plurality of neighbor devices to be the parent device comprises determining that the accumulated transmit reliability rate for the selected neighbor device exceeds a minimum threshold value.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS This application is a continuation of United States Patent Application titled, “DETERMINING NETWORK RELIABILITY USING MESSAGE SUCCESS RATES,” filed on Aug. 13, 2021, and having Ser. No. 17/402,231. The subject matter of this related application is hereby incorporated herein by reference. BACKGROUND Field of the Various Embodiments Various embodiments of the present disclosure relate generally to computer science and mesh networking and, more specifically, to determining network reliability using message success rates. Description of the Related Art A conventional utility distribution infrastructure typically includes multiple consumers (e.g., houses, business, etc.) coupled to a set of intermediate distribution entities. The distribution entities draw resources from upstream providers and distribute the resources to the downstream consumers. In a modern utility distribution infrastructure, the consumers and/or intermediate distribution entities may include Internet-of-Things (IoT) devices, such as smart utility meters and other network-capable hardware. These IoT devices can include battery-powered devices (BPDs) that draw power from an internal battery and/or mains-powered devices (MPDs) that draw power from mains electricity, a power grid, and/or other external power source. Among other things, these IoT devices measure the consumption levels of various resources to generate related metrology data and periodically report the metrology data across the Internet and/or other networks to a centralized management facility, often referred to as a “back office.” In many cases, the back office performs various management operations for the utility distribution infrastructure on behalf of one or more customers. For example, a customer could include a utility company or other corporate entity that owns and/or operates all or part of the utility distribution infrastructure. Typically, the back office periodically collects metrology data associated with the utility distribution infrastructure and provides that data to customers. For example, the back office could obtain metrology data from a set of IoT devices every eight hours indicating utility consumption over an eight-hour interval. The back office also occasionally initiates on-demand read requests to read metrology data from one or more specific IoT devices at the behest of the customer. For example, the customer could require a final utility meter reading from a smart utility meter located at a recently sold residence to prorate a utility bill. In such a situation, the back office would transmit an on-demand read request to that smart meter to cause the smart meter to report the current meter reading. An important objective of the utility distribution infrastructure, therefore, is to reliability retrieve metrology data from the IoT devices. In some implementations, instead of communicating directly with the back office, a group of IoT devices may establish an ad-hoc mesh network and route communications to the back office through the mesh network. Such a mesh network is typically formed by establishing communication links between pairs of IoT devices that reside relatively close to one another. The IoT devices then use the communication links within the mesh network to exchange and/or aggregate metrology data, propagate commands, and/or participate in other decisions or actions. Thus, in order to reliably send data to the back office and receive messages from the back office, the IoT devices need to establish and maintain reliable communication paths through the mesh network and to and from the back office. One approach for evaluating the quality of a connection between two nodes of a mesh network is to evaluate the received signal strength indication (RSSI) associated with the communication link between the nodes. The RSSI is a measure of the strength of the signal that one of the nodes is receiving from the other node. As a general matter, a lower RSSI indicates that the communication link has weaker signal strength and, therefore, is a less reliable connection. However, one drawback of using RSSIs is that a given node can use an RSSI only to estimate whether that node is reliably receiving messages from a second node. Notably, the RSSI does not indicate whether the second node is reliably receiving messages that are being transmitted by the given node or whether the second node is reliably receiving messages that are directed to the given node. Additionally, a path from the given node to a target destination typically includes multiple intermediary connections, such as connections between the second node and its neighbors. The RSSI does not indicate the quality or reliability of these intermediary connections. Therefore, if the second node is not reliably receiving messages and/or if any of the intermediary connections are not reliable, then messages to and from the given node may not be reliably received even though