Node discovery and culling in wireless mesh communications networks

Discovery and Elimination of Nodes in Wireless Mesh Communication Network

The present invention generally relates to wireless mesh communication networks, and more particularly relates to route and link evaluation in wireless mesh communication networks.

<b>Cross reference of related applications</b>

This application is a partial continuation of U.S. Patent Application No. 11/818,887 filed on June 15, 2007, which is fully incorporated herein by reference.

The main content presented in this article is generally about networks and network-based computer systems, and more specifically about the methods and systems of networks and routing protocols used to provide public facilities and home area services.

The exemplary embodiment of the present invention explains a routing transmission technology and protocol operating in an RF network (terrestrial or wireless LAN) in FHSS mode for use in a public facility and multiple home devices (they are the RF LAN network). To achieve two-way communication between the IP host (such as electricity meters, water meters, gas flow meters, distribution automation (DA) devices, and indoor devices), the RF LAN network will communicate with the utility host system (Utility Host System) (It is also called back-office server or BOS) interconnected, where the utility host system is an IP host in a wireless or wired WAN (Wide Area Network) infrastructure. The IP version in the exemplary embodiment is IPv6. When crossing a typical IPv4 WAN cloud, IPv6 packets will be encapsulated into IPv4 for transmission. The method of routing and transmitting IPv6 packets in a wireless LAN network includes the provision of a gateway capable of encapsulation (for example, encapsulating IPv6 into IPv4 packets) as a gateway between LAN and WAN within the scope of its capabilities. , And provide multiple IPv6 endpoints or devices that seem to be directly connected to the gateway at the IPv6 level.

In fact, these endpoints or devices can establish a radio transmission path directly connected to the gateway (single hop to the gateway) or to other IPv6 devices (multiple hops to the gateway). The invented algorithm and method will explain how to create the network topology below the gateway and how to use the data link layer (layer 2 in the OSI model) to route packets. The device or node starts up, explores available networks, selects the network to join, selects an orderly set of practicable upstream candidates in their routing transmission technology as their next hop, registers with the best path and The upstream nodes of the link cost and the gateways associated with one or more of these available networks are recorded at the end. The network discovery process performed by the node ensures that there is a route to send the packet upstream to the gateway in order to leave the utility host system; and the explicit recording of the upstream nodes and gateways will allow The gateway keeps track of the latest state of the network and ensures that data traffic can also flow downstream to the node. This is a multi-egress (multi-ingress) routing technology in which nodes may be part of multiple networks passing through one or more gateways.

In a network characterized by a utility network, the distribution part of the network may include: a plurality of nodes located at the endpoint utility meter, which will have a smaller number of nodes acting as relays Point; and one or more gateways to provide an exit from the end nodes. The utility network may also be composed of parts of the infrastructure (substation, feeder station, transformer location, generation facility) where monitoring and control sensors reside. facility)). These devices may also be directly connected to a utility server through a WAN or part of a utility network connected to a utility server through a gateway in a wireless network. The construction of the routing algorithm may allow the infrastructure nodes, and any selected distribution endpoint nodes, to establish a two-way connection with the shortest waiting time and the fastest path. In some embodiments, the infrastructure nodes and selected endpoint nodes may have additional capabilities to improve network reliability.

The above and other features of the present invention will now be explained in more detail with reference to the accompanying drawings, which include various novel implementation details and essential combinations, and these features will be proposed in the scope of the patent application. It should be understood that the special methods and systems described in this article are only shown by way of explanation and not restrictive. Those familiar with the technology will understand that the principles and features described herein can be applied to various and numerous embodiments without departing from the scope of the present invention.

In the following description, for the purpose of explanation, clear terminology will be put forward to thoroughly understand the various novel concepts disclosed in this article. However, those who are familiar with the technology will understand that these clear details may not be required to implement the various novel concepts disclosed in this article.

Some parts of the detailed description below are presented in the form of algorithms and symbolic representations of operations performed on data bits in computer memory. These algorithmic descriptions and representative symbols are used by those who are familiar with data processing technology to effectively convey the substance of their research results to other people who are familiar with the technology. In this article, and generally speaking, an algorithm will be regarded as a sequence of logical equations composed of multiple sequential steps and parallel steps that lead to a certain result. These steps are those requiring physical quantity manipulation.

However, it should be kept in mind that these and similar terms are related to appropriate physical quantities and are only suitable terms applicable to these physical quantities. Unless specifically mentioned, it is obvious from the following discussion: It should be understood that in the entire description, the terms "processing" or "calculation" or "estimation" or "decision" or "display" or similar words are used. The discussion of words refers to the actions and processing of a computer system or similar electronic computing device. The computer system or similar electronic computing device will represent the registers and memory of the computer system as physical (electronic) quantities. The data is converted into the computer system memory or register, or other information storage, transmission, or display devices, which are also expressed as other data in physical quantities.

The main content presented in this article is also about a device used to implement the operations described in this article. This equipment may be specially constructed for essential purposes; or it may include a general-purpose computer, which is selectively activated or reconfigured by a computer program stored in the computer. This computer program may be stored in the included, but not limited to the following computer readable storage media and each of them will be coupled to a computer system bus, for example: any type of disc, which includes Magnetic discs, optical discs, CD-ROMs, and magneto-optical discs; read-only memory (ROM); random access memory (RAM); EPROM; EEPROM; magnetic or optical card; or suitable for storing electronic instructions Of any type of media.

The algorithms, processing, and methods proposed in this article are not essentially related to or limited to any special computer or other equipment. Various general-purpose systems can be used with programs based on the teaching content of this article; or, it has been proved that it is also very suitable to construct more specialized equipment to implement the necessary method steps. The necessary structure of the various aforementioned systems will be understood from the following description. In addition, this article does not refer to any special programming language to illustrate the present invention. It should be understood that various programming languages can be used to implement the teachings of the present invention described herein.

<b>Wireless network</b>

Referring now to FIG. 1A, a communication network may include a plurality of devices 140 and 130 (nodes), which are connected to each other (at least one or more) and are connected to one or more gateways in a wireless LAN 160. Unless specifically mentioned, the gateway can also be referred to as an "Access Point" or AP. Then, the gateway may be connected to one or more back office utility servers (BOS) 150 through one or more networks 110 (usually Wide Area Network (WAN)) . The logistics server can be implemented on one or more computing devices, for example, a utility server, such as the server 150 shown in FIG. 1B; and can be implemented across one or more networks.

The infrastructure device node 170 shown in FIG. 1b is located in a wireless LAN. There may be more infrastructure device nodes (IN nodes) scattered on the wireless networks or the public facility infrastructure. If the IN nodes are part of the wireless LANs, they may try to leave through one or more gateways in the wireless LAN to which they belong and go to the utility BOS. In some embodiments, the IN nodes may directly access the utility BOS through a WAN or radio backhaul. In some embodiments, the IN nodes may also be connected to each other via radio.

Referring now to FIG. 1B, a node (such as a battery powered device (BPD) 130 and/or a constant powered device (CPD) 140) and an infrastructure device 170 may be able to listen to it. All neighbors with which the link is established are used to explore the available network 110; a network that should be joined may be selected; and a set of feasible upstream candidates may be selected as the next hop. Please note that in one embodiment, the CPD may act as a proxy server for the BPD. However, alternative embodiments may also allow the BPD to directly serve as a node in the wireless network without any proxy server. In certain other embodiments, the IN nodes 170 may directly access the utility BOS through the WAN 110 instead of the AP 120. In certain situations, many IN nodes may be chained together through the radio add/drop (add/drop) backhaul transmission system, and will be connected to each other and to the utility BOS.

<b>example</b>

Node M-1 (a continuous power supply device 140 in FIG. 1A, which is a node in the wireless LAN 160) will know from its neighbors that it passes through one or more WAN networks 110 (WAN-1 and WAN- 2) To access the relevant information of the BOS 150, and to register both AP-1 and AP-2 120 of the gateway type (they have unique IP addresses), these AP-1 and Both AP-2 120 will provide an exit to BOS 150 through one or more WAN 110 exits. It will achieve this through the upstream nodes M-5, M-6, M-18, M-2, and M-12 140 of the continuous power supply device type in order to communicate with the BOS-1 150 of the utility server type communication. Each of these nodes may construct a routing table with an ordered list of the next hop and the corresponding link cost (the proximity cost between the area node and the next hop) and the path cost ( Export costs announced in the next jump). Then, each node will register itself in its upstream neighboring point and gateway 120. The gateway 120 may track the network topology and capabilities of all devices under its control, as well as other devices. Nodes may retain the state of the area and the state of their immediate neighbors, and may periodically update their login items.

In an embodiment, the network nodes 130, 140, and 150 may be one or more wireless LANs Part of 160. In the example of a utility network, the LAN may be a neighboring area network (NAN), which corresponds to a neighboring area or service area of the utility. As shown in the exemplary embodiment, multiple or overlapping or non-overlapping LANs may be used, so a given network device may only be connected to one wireless LAN or be connected to multiple wireless LANs (or It may be only part of one wireless LAN or part of multiple wireless LANs). These nodes may be any type of network device. Examples of network devices or nodes include utility nodes, which may include a utility meter or may be connected to a utility meter. A utility meter is a device capable of measuring the physical quantity (which is usually a valuable commodity, such as electricity, water, natural gas, etc.) to be calculated by the meter. A utility node connected to a utility meter may include a network interface card (NIC) for communication on a network; may include one or more RF transceivers for communication on a wireless LAN. And may include utility meter interface devices (a given utility node may interface with multiple meters, which may or may not measure different valuable commodities, such as electricity, gas Gas, water,... etc.). The utility node may also include an indoor device interface for connecting to indoor devices via an indoor network (which may or may not be a wireless network). The indoor device interface is connected to the indoor device to provide a communication link between the utility node and the indoor devices. In addition, the utility node may also provide a communication link between the indoor devices and the wireless communication network connected to the utility node. Other examples of network devices include various communication devices, such as set-top boxes (which may be used in cable or satellite TV transmission); household appliances (for example, refrigerators, heaters, lighting, cooking appliances,... Etc.); computers or computing devices (for example, game consoles, storage devices, PCs, servers,... etc.); network connection devices (such as repeaters, gateways, routers); telephones or cellular Telephones; battery storage devices; transportation devices; transportation vehicles (for example, electric vehicles or hybrid vehicles or other vehicles, which may or may not be able to "plug-in" into a utility grid Receive metered/monitored valuable goods, such as electricity; entertainment devices (for example, TVs, DVD players, set-top boxes, game consoles,... Etc.); or other devices that may be found in homes, companies, roads or parking lots, or other places. The repeater 130 (an example of which is M3 in FIG. 1a) may handle the communication between the network node 140 and the gateway 120. For example, a repeater may provide communication between the network node and the infrastructure of the utility network. Unless specifically mentioned, other devices in the network (such as meters, electronic devices, gateways,..., etc.) can all act as repeaters, and repeaters can implement other devices in the network The function of the device or software. The wireless LAN 160 may be any type of wireless network, and may use any frequency, communication channel, or communication protocol. In some embodiments of the present invention, one or more of the wireless LANs 160 are FHSS networks or DSSS (Direct Sequence Spread Spectrum) networks.

The wireless network 160 may be connected to one or more gateways 120. A given wireless network may only be connected to a single gateway, or it may be connected to two or more gateways. The gateways 120 may be connected to one or more wide area networks (WAN) 110. The WAN 110 may be connected to one or more BOS 150. These logistic servers may handle a variety of business or management tasks, including: participating in the collection of metering information, managing metering devices, network security, or other functions that may be required in the AMI network. Examples of logistics systems include: accounting and accounting systems, proxy servers, supply interruption detection systems (which may be used in utility networks), data storage systems, ... etc.

In one embodiment, the routing protocol used is a "next hop" type multiple-out/multiple-in algorithm for determining the best route to/from a destination, which uses stable The path cost and/or historical data of the upstream and/or downstream routing transmission of the routing packet is used as the measurement value of the next hop of the routing packet. In one embodiment, as described below, the hop count is not used to estimate the path cost, but the hop count is used to prevent routing loops from occurring. In this embodiment, a node may choose the route with the lowest path cost measurement value to choose a better route for transmitting the packet.

In one embodiment, in the initial network exploration stage, a node may use a scanning process to scan the communication slot or channel in order to obtain its neighbors and obtain the confirmation message reply, and from the discovered ones An initial link quality estimate value is obtained at the neighboring point. This initial link quality estimate can be used to select the best upstream neighbors to talk to (the selected number can be configured for configuration).

When a node wishes to use these upstream nodes to leave for another network, the node will continue the process of "registering" its upstream node. In response to the login message from the node, the upstream node will add the registered downstream node to the downstream routing table entry reserved by the upstream node. The upstream nodes may also continue to retain the latest time information related to the downstream node that is registered in response to the registration performed by the downstream node. It is better to establish nodes that will route through each other so as to periodically exchange time information, so as to keep synchronization and exchange packets in the wireless network. In one embodiment, the wireless network may be based on frequency hopping spread spectrum (FHSS). In another embodiment, the time update information will be carried on any data transmission message; however, if there is no data exchange in a pre-configured time interval (for example, the size is 30 minutes) , It may trigger a clear time information exchange.

Then, a node may log into one or more of these gateways. This login process may prompt the gateway to add the login node to its routing table and ensure that the status of the node is the latest state. Nodes logging in to the gateway may be performed periodically, but they are not as frequent as logging in to upstream nodes. In a currently preferred embodiment, the login frequency is performed every 12 hours.

<b>Addressing</b>

<b>IPv6 addressing:</b>

Each node 130, 140 in the wireless communication network can be identified by a unique IPv6 address for point-to-point routing in any special network. An IPv6 address is usually composed of two logical parts: a 64-bit network prefix and a 64-bit main part. When a node successfully logs in to the gateway, the gateway may submit a TLV (Type Length Value) type data packet containing the network configuration to the node, which contains the data packets required by the node The IPv6 global routing preamble associated with the added subnet. Then, the node may send a dynamic DNS update request (RFC 2136) to the DNS server of the network host utility system (BOS). When the utility server (BOS) 150 wants to send data traffic to the wireless LAN, it may resolve the DNS name of the node into an IPv6 address for layer 3 (IP) routing through the WAN to the correct Gateway. If the WAN is based on IPv4, then it may use appropriate preambles to encapsulate IPv6 packets in IPv4 so as to tunnel through the IPv4 cloud. The received IPv6 packet will be decapsulated at the BOS 150 and the gateway 120.

A node may register multiple networks on the same gateway or multiple gateways. In this case, the node may set its belonging based on the estimated value or calculated value of its lowest cost path The priority of the network. In the presently preferred embodiment, the node has an IP address in each network where it is registered. The DNS server may associate the IP addresses with the hostname of the node in a better order according to the policies defined in the DNS server. When a BOS server in the WAN network wishes to send data traffic to the wireless LAN, the DNS server will sequentially pass the candidate IPv6 addresses when resolving the host name of the node.

<b>Link layer addressing</b>

Each node 130, 140 can be identified for routing in the wireless LAN by a unique link layer address assigned to its radio interface. In this embodiment, each node may only have a single interface. Other embodiments may have multiple different link layer addresses. The link layer address usually has a length of 8 bytes and is the MAC address of the device. The link layer broadcast address may be hexadecimal (hex) ff:ff:ff:ff:ff:ff (all 1). Packets transmitted using this area broadcast address may be processed by the device that receives them.

<b>RF link layer packet delivery</b>

The system shown in Figure 2 may carry the bit composition of the link layer header which may carry the information explained in Table 1 below. Table 1 also describes a number of flags carried by the link layer header.

<tables><img file="TW201014393A_D0001.tif" /></tables>

As shown in Figure 2, the flag is followed by the source address of the node that generated the packet. In one embodiment, the source address of the flag may not be set as the broadcast address.

As shown in Figure 2, the source address may be followed by the next hop address where the packet will be delivered. In one embodiment, if the source route bit is set, it may be included in the entire hop address list ending with the destination address; otherwise, only the next hop may be clearly specified. In either case, the final address is the destination to which the packet will be routed.

If the source route bit is set, the packet header may contain the entire path that the packet will take. It should be noted that the packet may be routed between two nodes from the source without any intermediate hops (that is, the address count (Add Count) is 2, and the destination address is the node address or broadcast address. site). This mechanism may be used to interrogate individual nodes 130, 140 from a terminal (such as a debugging mobile station).

If the source route bit is not set, then the L2 delivery code on a node may make a decision based on the value of the address count field. For example, if the address count on a packet to be sent from the RF LAN to the WAN network (110) or utility server (150) is equal to 1, this means that the packet may be delivered to the Any exit node or gateway in the system. If the address count is greater than 1, this means that all additional addresses in the delivery table at the node can be used as L2 egress destinations. The addresses in the delivery table of a certain network can be sorted according to preferences (from least favorite to favorite).

If the address count is greater than 1, in the event of congestion or failure, the packet can be rerouted to a different L2 destination. When a different L2 destination is selected, the previous network should be removed (by decrementing the current offset or zeroing the previous field). Removal of the previous network is expected to help reduce the occurrence of routing loops; when a routing loop occurs, the packet may be resent further away from the destination than the original source packet.

When a packet is delivered through L2 of a node, the TTL may be decremented. When the TTL becomes zero, packets that are being delivered by L2 may be dropped; messages with zero TTL destined for hosts in this area may be handed over to the stack. Nodes 130 and 140 that are sending messages to the gateway 120 without using the complete source route may set the TTL to at least the number of hops on their longest path to the gateway 120. The maximum TTL can be configured and set by the administrator. In one embodiment, packets sent with the destination address set to L2 broadcast are not delivered.

The delivery of unicast packets may be confirmed by the DLC (Data Link Control) layer. Broadcast packets may be designed as unicast packets in FHSS technology, and may also be confirmed. It may not be able to send unconfirmed unicast packets. When the nodes 130 and 140 send a packet to a neighbor, the MAC layer may report the number of retries and the result of the final successful transmission. The network layer may keep a count of this information on a per-neighbor basis.

<b>Routing subsystem</b>

In one embodiment, the routing and transmission subsystem may be divided into four functional components:

-Neighboring point scanning and exploration

-Neighboring point maintenance

-Node login upstream neighboring point

-Node login gateway

An embodiment of the routing subsystem may be applied to a code entity DLF (Data Link Delivery) for layer 2 routing and a code entity MLME to obtain adjacent nodes and maintain time information between nodes (Media access control sub-layer management entity). DLF will interface with the MLME through a set of APIs.

<b>Neighboring point scanning and exploration</b>

For example, when the following conditions occur, a node such as CPD 140 (Figure 1b) may initiate network exploration:

There is no feasible exit node (not associated with any gateway)

The communication with the upstream node has been interrupted, according to management needs or due to parts failure or transmission loss

The periodic login message sent to one of its multiple gateways has failed at least 3 times

Announced a new network

For example, if the link with its designated master device (CPD node 140) has been interrupted, a node such as BPD 130 may initiate network exploration.

In an exemplary embodiment, a node may use two basic methods to explore neighboring nodes: broadcast exploration and neighbor query. When a node appears, MLME may use the "broadcast discovery method" to find all neighbors (or directly connected RF links) of the node. It may perform this task randomly to determine when to start sending the broadcast discovery frame, and then select the channel on which the broadcast discovery frame is to be sent (channel selection may be performed randomly). Then, it may cycle through each communication slot, transmit each successive broadcast exploration frame on the next communication slot, and wrap it at the last communication slot. In one embodiment, this method can ensure that a broadcast discovery frame will be sent on each channel in the hopping sequence of the FHSS-based network.

In these exemplary embodiments, there may be two broadcast exploration modes: active and passive. When the device is turned on, the device node may enter the active exploration mode, in which the exploration frame will be sent out at random time intervals, and the size of the time interval may be milliseconds. When the active exploration duration has expired, it may enter the passive exploration mode. In the passive exploration mode, the node may wait a long time between sending the broadcast exploration frame, and the size level is usually minutes.

Once the exploration method has found a neighboring point (neighboring point), or a group of neighboring points, MLME may then query the direct neighbors (direct neighboring points) of the explored neighboring points. May be provided in response to the query). This allows faster exploration of the network environment (different from broadcasting a large number of frames and hoping to contact any special device). The neighbor query mechanism may be a simple query/reply mechanism: a node that receives a neighbor query applies the criterion to the nodes in its list; nodes that "comply" the criterion will be placed in the neighboring points Replying. If no criteria are assumed, then all nodes in the list may be placed in the adjacent point response.

MLME may notify when the DLF exploration will end, that is, these nodes have been queried for their neighbors and have tried to reach these neighbors.

Using the neighbor list established by MLME, the DLF can try and find the published exit route. It may accomplish this task by listening to the "Network Advertisement (NADV)" messages from these nodes in the neighbor table of MLME.

NADV messages may announce a set of exit routes, which may include the path costs and jump counts of these exit routes. The path cost may be the lowest cost associated with the exit (gateway) among all candidate paths. The jump count may be the highest number of jumps made to reach the exit. Hop count can be used to prevent routing loops from occurring, and it may not be used in conjunction with path cost. An example of the format of the NADV message is shown in Figure 3. The destination MAC address may be the MAC address of the node that sent the network announcement information. In most cases, it may be the exit point (or gateway), because the network can be identified by the exit node of the network.

Each node can construct a routing table from the received NADV message type announcement information, which will list: available networks; used to identify the egress node of each of these networks (Gateway); and the available path to the exit node. Each of the available paths may be described as follows: the next hop; a flag to describe the type of path; and link cost and path cost. These flags may indicate the type of route-whether it is a permanent entry in the table; whether it can be published by the node... etc. In an embodiment, the node may decide to log in to the upstream node because the total cost (link cost and path cost) of an upstream node to the network is the smallest. Other embodiments may use other criteria, including the effective reliability of the link in providing long-distance egress to the network. An example of the information that may be captured in the routing table is shown in Figure 4.

The node can construct a delivery or next hop table from the routing table information, which has a list of destination MAC addresses, the type associated with each address, and its path cost. In one embodiment, this type reflects the preferences associated with the destination and may be one of the following five types: source-routed, hop-by-hop , Directly adjacent point type (direct adjacency), breadcrumb, or local. Figure 5 provides examples of the types of routes that can be listed. In the case of an embodiment of a hop-by-hop type destination, it may also list the next hop from the source node. In the case of source routing transmission type destinations, the destinations in the delivery table may be used to describe a hopping array in detail. Multiple entries for the same destination may be listed in the order of preference, which may be determined by both the type flag and the path cost. In one embodiment, when trying to reach the destination 4, the node may first use one of the successive hopping entries stored in a linked list in the order of increasing path cost. In other embodiments, the routing algorithm allows the routing information stored at the source node to generate a source routing routing entry for destination 4 by constructing a delivery path combination to the destination address . Also, in other embodiments, the node may use the navigation trail type route that it has picked up from the transfer data traffic at a certain point in time.

<b>Neighbor point maintenance</b>

In one embodiment, the MLME beacon or the targeted periodic keep alive message that is used to synchronize clocks and ensure that nodes can still exchange packets with each other can be used continuously. Maintain upstream neighbors and downstream neighbors. The L2 routing transport layer can use this continuous connection and feedback to achieve multiple purposes, which may include:

Neighboring point updates are transmitted to downstream devices in time update beacons.

If the downstream node or upstream node of the node is still functional, the node will use MLME for detection.

For example, when the following situations occur, the upstream link characteristics of a node may change:

Upstream nodes can no longer be reused

Detected a new better upstream node

The link quality has changed (smoothed over time)

In an embodiment, the aforementioned rule may be applied recursively to all upstream nodes in a certain path. When an adjustment occurs, the node will recalculate the cost of each of its multiple exit nodes. When the cost of a node to its upstream node significantly changes the cost of one of the multiple networks it will route through, it may spread this information to its downstream nodes in the next MLME beacon set.

In one embodiment, changes in network information may be propagated along with the "Neighbor List" message, and the protocol type field will be set to 0x2 to indicate that part of the change list is being distributed . In one embodiment, this can reflect the cost of adding a new network or changing an existing network. When an upstream node disappears, causing a particular network to actually become unrouted, the "neighbor list" message may be sent with the protocol type set to 0x3 to indicate the network Has been removed from the upstream node network list.

In one embodiment, the unicast of periodic network registration messages is used to notify each gateway of changes in the network. These messages may be sent by every node in the gateway's network, and may contain a complete list of its upstream nodes and the link cost of connecting each of the upstream nodes.

In one embodiment, MLME will keep the following two smoothed average values. DLF can use these average values to determine the link cost for routing purposes: the smoothed RSSI and the smoothed info The success percentage (info success percentage). The term "smoothing" refers to the type of average calculation performed on the data. In one embodiment, the average calculation uses the following formula: smoothed average=A*average+B*sample; B=(1-A). This type of average calculation does not require a large amount of storage memory (different from storing the most recent N samples), and it also has a controllable amount of "historical data". The term "historical data" refers to the extent to which the new value affects the current smoothed average. This may be controlled by the A value and the B value: a large A value indicates that the historical data of the average value is greater than a smaller A value. Other embodiments may use other averaging techniques desired under prevailing network conditions.

RSSI is the strength indicator of the received signal. It may measure this value for all frames received from a node. In some embodiments, its use in link quality calculation is quite limited because it may not be able to clearly indicate the bit error rate of the link. When any frame is received from a node, it may use the average calculation formula to average the RSSI of the frame into a smoothed RSSI.

In one embodiment, the "info" success percentage criterion can be used as the best link quality measurement value, and thus used to make routing decisions. The type of "info" success percentage is packet success rate. The term "(info)" refers to a frame other than the frame where communication is initiated. The first frame sent to the calibrated node in its hopping sequence may fail due to interference or because the receiver is busy. In the frame that only contains the frame that the calibration node is listening and is not the start of the communication, the info success percentage provides a link quality measurement value that may not change significantly with the load of the receiver. The success percentage of info may be a better indicator of link quality.

<b>Node login upstream adjacent point</b>

Each node may explicitly register the upstream node it wants to use in a network. This registration means that the upstream node may now try to keep the latest time information related to the registering node and keep the downstream routing table entry. Therefore, the data flow may not only flow to the exit, but also flow back to the node (downstream).

The node will log in to the upstream node by sending an "upstream registration" message to its upstream node. The "upstream registration" message may contain the type of the device and the neighborhood health metric. The sanity measure of the neighboring area can be used to eliminate downstream nodes when an upstream node is overloaded. A device with a low neighboring area soundness measure (so, it can be presumed that it will have low path diversity) may be selected before a device with a high neighboring area soundness measure.

An exemplary format of the "upstream login" message is illustrated in detail in Figure 6a. The message type indicates that it is an upstream login. The adjacent area cost is a measure of the soundness of the adjacent area based on the combination of the number of potential upstream nodes and the number of active upstream nodes.

Potential upstream nodes will use the "Upstream Login Confirmation" message to positively or negatively confirm the "Upstream Login" message. The "adjacent area soundness" of a device can be updated based on the value of this confirmation message. The weights provided by potential upstream nodes may be less than the confirmed upstream nodes.

An exemplary format of the "Upstream Login Confirmation" message is presented in Figure 6b. The type indicates that it is an "Upstream Login Confirmation" message. "Seq Num" is the sequence number sent by the requester in the "upstream registration" message. The response status code may be one of the following:

0x0, the node successfully joined

0x1, node join failed

0x2, the node is rejected due to high load

0x3, the node has been maintained

<b>Node login to AP</b>

A node may register itself in a gateway by sending a unicast "AP registration" message (AREG). The AREG message may contain a list of the addresses of nodes in the gateway's network that are regarded as upstream nodes by the registering node and the link cost associated with each of the upstream nodes. It may also contain a list of other candidate networks (represented by the exit nodes of these networks) and their costs.

An exemplary format of the AREG message is presented in FIG. 7a. The type may be set to indicate that it is an AREG message. If there is still data to be sent, the M bit may be set. Seq Num may be the serial number of the login message. When the login message is sent in multiple parts, a message number may be used. Each AREG neighbor (AREG Neighbor) may describe an upstream node located in the path used by the login node.

An exemplary format of the description of the AREG neighboring points in the AREG message is presented in FIG. 7b. The MAC address may correspond to the upstream node or the login node is notifying the network exit point of the gateway. The cost may be the recorded cost to the upstream node or the described network exit point. The E bit is the bit of the network exit node. If the neighboring point description represents a network exit node rather than an upstream neighboring point, the E bit will be set.

In one embodiment, when the node successfully logs in to the gateway, the gateway may put the node in its routing table and keep the latest state of the node. The node may send periodic login messages to the gateway (the size level is once every 12 hours). The gateway may update its routing table when it sees subsequent AP login messages. If the gateway loses three consecutive registration messages, the node may be removed from the routing table of the gateway, and the node itself may need to be re-registered.

In response to the first successful login, the gateway may send down a set of TLVs containing any network configuration information. In addition to other information, this list may also include the following information: the gateways global routing IPv6 prefix, the gateways MAC address, DNS server address, network transmission timer, and L2/L3 Any other variables related to routing. Fig. 7c is an example of an AREG message with a network address sent to the login node.

If a gateway is overloaded with too many nodes, it may start to eliminate nodes with other candidate networks. It can evaluate this result by examining the different networks reported in the AREG message, and can remove the most sound candidates from the network and notify them of any actions they have taken.

<b>example</b>

The small RF network drawn in Figure 8 can be used to illustrate a preferred embodiment of how route decision and propagation work in a typical scenario, in which gateways (821, 822,...) and medium are discussed first. Repeaters (831, 832,...), and then the end nodes (841, 842, 843,...) will be discussed. As shown in Figure 9, the link cost will be mapped between the nodes that establish communication with each other in the RF layer.

In the example shown in Figures 8 and 9, based on the published path costs received from its neighboring points (including R1 and R2), nodes M1, M2, and M3 will establish gateways AP1 and AP1 and M3 respectively. AP2's routing options are sent in order to leave. In most cases, each node in the next-hop (next-hop, NH) configuration will have multiple prioritized routing options through one or more of its neighboring points.

In one embodiment, the routing mechanism may be adapted to be compatible with and make good use of the frequency hopping spread spectrum (FHSS) access technology used in the wireless network of an embodiment, and use some inherent features of FHSS Operating characteristics. In the frequency hopping technology, regular time updates are performed in order to solve the clock drift at each node that should be kept synchronized and exchange packets synchronously. The routing protocol can use the frequency hopping time update as a "keep-alive message" for sending link status information to keep the minimum packet recurring data. Alternatively, the time update information can also be carried on any data packet to be delivered. Unless specifically mentioned, keep-alive messages may be sent to update information and may be sent regularly. For example, when a node is initially booted up or just introduced into a network, the "I'm alive" message (which can also be used to update routing information) may usually be Send for announcement.

In this embodiment, in the network using the FHSS technology, the routing protocol may not be broadcast in any conventional sense. The nodes may be directly calibrated one by one for packet exchange. The routing protocol proposed in this article may use the abstract concept of broadcasting. Therefore, the MAC address of the 8-byte group of all 1s (ff:ff:ff:ff:ff:ff in hexadecimal) will be used in each When a communication slot or channel is transmitted, it will start from a randomly selected communication slot and there will be a preset waiting time between each transmission.

In one embodiment, the routing protocol described in this document uses the beaconing function in the FHSS-based wireless network, where the beacon is a specific beacon that can be recognized by all neighbors. Know a periodic broadcast on the frequency hopping sequence. The utility of the broadcast beacon that can be received by multiple neighboring points is greater than sending a routing update to each neighboring point. Compared to routing updates, the beacon may also be a shorter transmission with less overhead, because there may not be any confirmation messages and thus less retransmission of packets in case of failure.

In one embodiment, the routing protocol described in this article is designed to use the collective computing resources of the devices (nodes) in the network to calculate routes and distribute the routes to all nodes, instead of relying on the A gateway at the source of the wireless network. Based on the announcement of the exit route with the associated path cost for each route and each hop, the endpoint may be selected as the better set of multiple upstream nodes in order for the next hop to pass through multiple gateways (It is also called AP) to leave a WAN network. When the upstream or the main route to the gateway fails, it may immediately fall back to the second route and/or gateway in the database of the endpoint without waiting for the routing algorithm Perform re-convergence calculations, because these routes have been pre-converged calculations.

In one embodiment, the routing protocol allows nodes to migrate from one network to another. When an upstream node announces its known route to a downstream node, it may send a set of exit routes to the available network. The routing table at each node will list the next hop through multiple gateways in the available network, allowing rapid migration if the main or default network is unavailable.

In one embodiment, each node logs itself in the upstream node it wants to use. The upstream node may now maintain the downstream routing table entry of the node. Data traffic destined for an endpoint may now be routed first in a hop-by-hop manner, where the next hop originating from the source node or any node can be sequentially added to the message header of the packet. Of course, the destination address may be incorporated as usual. The source routing transmission of the ordered node list through which multiple packets in the message header can be clearly stated by the gateway is also within the scope of this algorithm as the second option. The routing protocol disclosed in this article can allow each node to have multiple next hops in its knowledge base and enable it to select from them for the purpose of hop-by-hop delivery. In this way, the packets can prevent the occurrence of problematic links without transmission failure and without retransmission, and it is more conducive to use in wireless networks where the RF links tend to be short-lived in nature. . In addition, this can also prevent the occurrence of open-end route exploration loops and disputes over problematic routes, in which source routing transmission technology is forcibly incorporated in the event of a failed link.

The complete routing implementation in the utility network may perform many functions to ensure that the network and the nodes will operate in the best way. The disclosures in this article illustrate several novel ways to enhance network performance, which utilize the same routing function as previously described.

<b>Configuration management</b>

There may be a suitable and up-to-date configuration on the nodes in the network, and this configuration information can be distributed to other nodes in the network. For the public facilities logistics server (BOS) used to manage the network, the peer-to-peer network nodes must have end-to-end reachability. These nodes can be configured correctly and have sufficient information related to the overall network configuration, which will use the upstream node as a proxy to disseminate configuration information.

There may be certain "settings" specific to the site/site on the network device (node). These settings can be expressed as configuration variables on the device. Once the configuration variables are set, they can be written to permanent storage. Examples of these settings are as follows: DNS server used by the meter, SNTP trap host information, time zone information, etc.

Furthermore, some configuration variables may also be "knob", which can be used to adjust the implementation of the network, for example: the rate of sending network registrations; it can be used in the link cost algorithm Some smoothing parameters. There may be situations where the knob needs to be adjusted at the entire network level in order to change the behavior of multiple devices in the network. In order to achieve these functions, it may be quite practical to distribute, implement, and manage these configuration levels at the device and network levels from time to time.

The disclosure presented in this article provides a method for performing configuration management. When nodes send a routing transfer registration to the gateway (NREG), the nodes may incorporate their configured SHA-1 hash value (security hash algorithm). If the SHA-1 hash value does not match the hash value stored in the gateway, the gateway may send its new configuration to the node. This SHA-1 hash value may contain:

List of variables to be merged into SHA-1

The variables to be used in the SHA

The variable list may be very important, because if new variables need to be incorporated in the configuration SHA-1, changing the list will result in a SHA-1 mismatch.

<b>Time synchronization:</b>

This project is related to configuration management, and its uniqueness lies in the concept of time synchronization being incorporated into the network registration (NREG) message. It does not separately make requests to the back-office time server or the time server on the gateway; instead, when a device sends an NREG message, the new node or the restarted node will be added as a given time (Rejoin) Part of the network. This novelty has several advantages, including: (a) Time information can be obtained almost immediately; (b) At least two point-to-point packets can be saved.

When time synchronization is spread across a network, there may usually be a basic request/reply mechanism. The network node may be configured to request time from a specific MAC address. If the address is not configured in these nodes, they may request time from a gateway in their routing table. The gateway can execute SNTP (Simple Network Time Protocol). If these gateways have time, they can respond in the following way: The reply packet may be time-stamped by the application layer. When the packet is handed down downward, it may be "marked" as a transmission delay at the MAC layer. The packet may have a field for the total transmission delay, and this value may be updated at every hop. When the requesting node receives the reply, it can add the time stamp value and the transmission delay to obtain the current time. To improve efficiency, there may be a "flag" in the packet to indicate that it should be checked at every hop. This may be a general flag and can be reused by other protocols (for example, traceroute).

The time synchronization request can be sent as a stand-alone IP packet (for example, IPv4 or IPv6); or to improve efficiency, it can also be combined in a network registration (NREG) packet. It will not be directly incorporated into the payload of the network registration packet; rather, it will be inserted into the data-link interface (DLI) TLV. The DLI TLV may be processed before the packet is handed up to the application layer. If the gateway receives a time synchronization request with network registration, the response may be incorporated into the DLI TLV in the network registration confirmation message (NREG ACK).

<b>Regional load management by network nodes</b>

The field would like to avoid the following situation: multiple nodes in the network are "ranked" behind the best cost node and use this node for routing. The node may soon be too busy to deliver the data traffic of all nodes that are using the node. This may also make routing transmissions very fragile, causing congestion, and may make many nodes unreachable. Furthermore, there may be a lot of confusion when forming a new route.

The novelty disclosed in this article can force better nodes to increase the cost of being published to a random set of neighboring points. The better node(s) may receive a "keep" packet from the node that is using it. The "maintain" packet may be a request from a downstream node to request the upstream node to continue to incorporate the node into its active packet delivery (routing) list. If the better node has too many active maintenance nodes, it may increase its path cost (according to the algorithm designed to achieve the purpose of reducing the specified but variable percentage of packet data traffic), and may change this The new cost is sent to a randomly selected neighbor that it wishes to discard or to a number of neighbors selected according to a load balancing or data flow balancing algorithm. It may continue to send actual costs to the remaining nodes. The goal of this action is to prevent a smaller (but a preset percentage) set of nodes from leaving the better node. The algorithm may consider the following two factors to prevent large fluctuations in network data traffic:

-By spreading "high" path costs to most nodes to force a large number of nodes to seek alternative routes and create routing loops.

-Prevent the occurrence of situations where downstream nodes that continue to receive actual path costs will not unintentionally announce this cost to nodes that have received high path costs from better nodes, thereby forcing them to publish through such issuing in some cases The node routes the packets back to the better node.

Maintenance packets may be sent at regular intervals and may not change like network data traffic. They can be sent at approximately the same rate as the route announcement period, so that these nodes should let the maintenance packet be returned by the next announcement period. In one embodiment, the rta (routing advertisement) period may be set to 20 minutes and the maintenance period may be set to 10 minutes.

The present invention may assume that unless the cost of nodes leading to the current upstream neighboring point in order to leave is increased by 10%, they will not switch to a better or alternative route. Therefore, the algorithm used in one embodiment may force the upstream node to increase the cost of the route by ~10%. In one embodiment, the route cost increase will remain less than 20%. In addition, if these nodes start to switch and cause more data traffic to flow downstream, it may trigger rta.

The downstream nodes can also be randomly selected from all nodes to which the better upstream node is sending the rta, and the better upstream node does not only send the rta to the node that is sending the maintenance messages to it. This can prevent the node from switching to the better node immediately when their routing conditions force them to select the better node. This is an effective preventive solution to avoid receiving a large number of login requests from new downstream nodes.

<b>Regional load management by gateway</b>

In some network situations, some gateways may be overloaded due to the data traffic in the field, while other gateways have only a few nodes to log in, resulting in unbalanced data traffic. An exemplary method of managing the data traffic flowing into the gateway may be to control the number of network nodes that log in to the gateway. On the other hand, the gateway can also prevent nodes from getting trapped (that is, they cannot log in to any gateway) to control the login operations.

In the routing algorithm disclosed in this article, there may be at least three mechanisms to control the number of network nodes that need to log in to a gateway:

1) A routing announcement announces the number of hops propagated to the network

2) Gateway pushback (send negative NREG ACK)

3) Increasing the route transmission cost announced by the gateway (if the gateway replaces several selected nodes to announce routes to provide exits for those registered nodes)

<b>Jump count control:</b>

The routing algorithm disclosed in this article can adjust the number of hops that the routing announcement can be delivered to the network. The algorithm may also include a basic feedback control algorithm. One type of this algorithm may be unique to the gateway, where the gateway individually adjusts their hop counts based on the number of target nodes that it hopes to have in its registry. The second type may be a possibly global control loop, in which gateways adjust their jump counts relative to each other. If there are more registered nodes in one gateway than another gateway, it may decrease its hop count, and the other gateway will increase its hop count.

<b>Gateway pushback:</b>

In one embodiment, when logging in to the gateway, the node may inform the gateway whether it is their primary, secondary, or third route. The gateway may have strict limits on the number of routes to start sending negative acknowledgement messages (NACK) to the third node and the secondary node. In one embodiment, the gateway may not send a NACK to the main NREG to avoid trapping these nodes.

Once the number of routes (nodes) registered by a gateway is above the limit set for managing the network data traffic, the gateway may start sending NACKs to those trying to register as the third route Any node. The level of the secondary NACK may be higher than the level of the third NACK. When this level is reached, the gateway may start sending NACKs to both the third registrant and the secondary registrant.

When a node receives a NACK from a gateway, it may put it in the hold-down list. Announcements from gateways in the reserved list may be discarded. Putting the gateway into the reserved list can prevent the node from logging in to the gateway again immediately. After a node receives a re-registration message and the same route announcement message from the gateway, the node can restart the registration of the gateway. Once the gateway is removed from the reserved list, the node can log in to the gateway again. In one embodiment, a gateway may be placed in the reserved list for 3 hours after a NACK. If a node loses all routes for more than a certain period, it can assume that the network has changed significantly. In this case, the gateway from which the node has received the NACK can be removed from the reserved list.

In yet another embodiment, another variable use of the gateway pushback is to synchronize the gateways with each other globally to set the secondary and primary levels. This level may vary depending on the load conditions of other gateways under the control.

<b>Route evaluation (exploration and maintenance)</b>

<b>Link evaluation</b>

When a node is explored, the MLME (MAC Layer Management Entity) of the source node may not have any idea about whether the explored node is a good neighbor. In this regard, it may wish to evaluate the success rate of its routing to the node. In one embodiment, the evaluation phase includes sending 20 (configurable) packets to a node and then calculating how many of these packets are successfully delivered (in this embodiment, an exponential filter may be used To evaluate the success rate of the link information). The source node may send its latest link cost in the evaluation packet. Each evaluation packet may also be confirmed. This can achieve the following purposes: 1) the neighbor can talk to the node in the reverse direction, and 2) the source node will know the link cost of the neighbor to it. Knowing the two-way link cost can be very important for routing, because data traffic will move downstream in the reverse direction. The bidirectional link cost may also be incorporated into the maintenance packet confirmation message sent by the source node to the upstream node that can be used for routing later.

This evaluation process may result in considerable packet data traffic. A node may not be able to evaluate all its neighbors at once. However, the source node may evaluate the best node first, so that the node can start to join the routing transmission. Therefore, in one embodiment, the source node will select a configurable set number of best RSSI neighbors and evaluate them first. In one embodiment, the number will be set to five (5).

<b>Maintenance mechanism</b>

In a wireless independent network, nodes may retain certain information about their neighbors. This information may be stored in a list. As mentioned in this article, this list is called "nodeq".

The maintenance mechanism may have the following three items:

1) Let neighbors know that they are upstream for routing, and therefore, unless there is actual need, they should not discard the node that sent the maintenance message to them from nodeq;

2) Obtain bidirectional link information so that the route cost can be predicted;

3) If a node has been discarded from the nodeq of an upstream node, they will grasp this situation as soon as possible (in one embodiment, before the 2x20 minute routing announcement period has elapsed).

The maintenance mechanism can operate in the following way: the MLME of the source node may send maintenance packets to the upstream node that is being used by the routing transport layer every 10 minutes. The maintenance packets may be confirmed, and the confirmation message may contain the link cost from the upstream node to the node.

1) When a node receives a maintenance message, it may mark the transmitting node as a maintenance node, and may not remove the node from nodeq.

2) The maintenance message may provide the node with a way to grasp the cost of the upstream link. In some embodiments, if the maintenance message is not delivered, there may only be very low data traffic flowing from a downstream node to an upstream node. An example might be when a utility meter is read only once a day. In this case, the maintenance message data flow can be used to maintain a stable route in a network with very low burst data flow. In the direction to the downstream, there may be routed and published data traffic every 20 minutes. Therefore, sending periodic maintenance packets will help measure the link cost and transmit it to two nodes so that they can keep the latest two-way link cost.

3) When a node is discarded from the nodeq of an upstream node, the discarded node may immediately receive a "cull cull" message from the upstream node. However, if for some reason the discarded node does not receive the message (for example, when a node just restarts... etc.), then if the message is not received during its next maintenance message cycle Confirm the message, you can infer that it has been discarded. And this result will occur faster than the sample time of approximately 40 minutes assigned to the route delivery announcement overdue. Therefore, it can make the network more responsive to changes and can adapt more quickly.

<b>Link evaluation algorithm</b>

a) Direct link evaluation through info success percentage:

In one embodiment, the data link layer (DLL) of the node communicates with neighboring points by polling them first, so as to check whether the neighboring points can be used. If the polling confirmation message is received, the data frame may be sent. This exchange is called PADA exchange (polling-confirmation-data-confirmation). When no acknowledgment (ACK) of polling or data frames is received, a random back-off time may be generated, and the retransmission will be performed when the back-off time has expired.

The term INFO refers to the data sent in the PADA exchange. The quality of the INFO frame (different from the POLL frame) lets the transmitter know the receiver that will listen to the transmitter. Therefore, one of the reasons why the transmitter cannot obtain the ACK message of an INFO frame may be that the INFO frame is incorrect or the ACK message is received incorrectly. Each node can use an exponentially weighted moving average formula to calculate the INFO success percentage (INFO%) to each of its neighbors. This calculation can be performed when any INFO frame is successfully transmitted or the transmission fails; this calculation may not be performed when a POLL failure occurs. The link cost algorithm may use the INFO% only because it can better represent the link quality between directly connected links.

This delay algorithm will be executed regardless of when the POLL frame or the INFO frame fails. A random delay value can be generated in the current delay window. The current delay window may be a geometrically increasing window; each successive failure may increase the window whose random delay value is rotated. Therefore, a lower percentage of successful packet transmission may result in a larger delay value.

The link cost may be designed to represent the average amount of time it takes to send a fixed-size PADA transaction. In one embodiment, the fixed size may be selected as 50 milliseconds. In some cases, 50 milliseconds may be ideal because it represents the typical packet data size in the network. Other PADA transaction sizes are also fully applicable to the present invention. Then, this time can be calculated for various INFO% (POLL can be assumed to always succeed), which contains the average amount of delay time under the premise of the INFO%. This data may be stored in a lookup table by the network node. By looking up the PADA transaction time under the INFO% in the lookup table, the link cost to a neighboring point can be calculated. For example, the lookup table may maintain a 4% increment.

In one embodiment, a bidirectional value may be used to obtain the final link cost. That is: the upstream node may send its INFO% success rate to the source node. Then, the source node can tabulate the "average time" from the INFO% of the source node to the upstream node and the INFO% sent to the upstream node to the source node. This can result in a stable two-way route, because routing may require a node to successfully send packets upstream and downstream.

b) Path cost assessment

The path cost can be calculated by adding the link cost on a path. Because link costs may be in units of time (not INFO%), they can be added and do not need to be multiplied together.

<b>Adjacent point query &amp; bad adjacent point list</b>

Adjacent point query may be a way for nodes to quickly explore a large set of adjacent points without having to randomly send exploration packets. When a node explores adjacent points, it may enter the "active" adjacent point exploration cycle. During this time, it may ask neighbors about nodes they know. This initial inquiry may be conducted at a fast rate. Once the initial exploration process is stable and the node is in the normal operation mode (no interruption, restart, etc.), the neighbor query can be sent out in a relatively slow manner. In addition, in order to prevent nodeq from being too unstable (the size continues to increase, then culling,... etc.), if the node has more than 90% of the desired number of nodes in its queue, it may not send neighbor queries .

Adjacent point query can be done in one-shot mode. When a node receives a neighbor query, it may send back information related to its active neighbors (MAC address, hopping sequence, etc.), except for the interface management unit (IMU's, Interface Management Units) Outside the adjacent point (the interface management unit is the unit placed on the water meter and gas flow meter). These IMU's may have limited energy, so they do not want to be explored by many meters and serve as possible relay nodes for many meters.

There are some nodes that the questioning node received during the neighbor query process and could not talk with it. It may receive notifications related to these unreachable nodes in multiple neighbor queries. These nodes may be placed in a bad nodeq in order to prevent the node from continuously trying to talk to neighboring points that it already knows cannot talk to. When a node is for some reason (some examples are as follows: repeated shutdowns and restarts; very poor link and path costs; alarms from network servers and gateways that exclude nodes; security alarms; etc. ) And when removed, they may also be placed in the bad node list. The nodes on the bad node list may not be added to the nodeq of a node unless they have been restarted and their link conditions have been recognized. The bad nodeq also helps to stabilize the real nodeq, because the node may not be able to regain the nodes immediately after other nodes are removed. The node may be removed from the bad nodeq after the specified period.

If a node does not have enough neighbors, it may also be removed from the bad nodeq. In order to be eligible for rejoining the normal nodeq, the nodes in the bad nodeq list may have been accessed by the reinstating node in the near future and have some kind of link information in its storage. This ensures that the node has talked to them once, and that if they are not on the bad nodeq list, they will be explored in the neighbor query.

<b>Weed out</b>

The culling process may eliminate several adjacent points from the node's nodeq before the memory is used up, so as to allocate node indicators. The culling may be done preemptively so that new nodes/disconnected nodes have room to connect to a special node and can also be used to control data flow. The number of nodes to be eliminated and the choice of which nodes to eliminate may affect connectivity and network operations.

The targets for culling include:

Keep a small nodeq to minimize network congestion and interference

Reserve space for new/disconnected meters on nodeq to use

Cut out infrequently to minimize instability

Minimize the impact of elimination on routing transmission

Let nodes maintain high link quality

The first step in designing the elimination algorithm may be to determine the optimal number of nodes in nodeq should be 100 to 110 nodes (based on data flow). The culling algorithm may create a hysteresis in it. This implies that the nodes in the nodeq may have a high level and a low level. Once the number of nodes exceeds the high level, the node may be eliminated until the nodeq is at the low level.

The next step of the elimination algorithm may be to determine which nodes to eliminate for the source node when it needs to be eliminated. In order not to disrupt the routing transmission, the routing transmission layer of the source node may mark the node that is currently acting as the upstream node. These nodes may not be eliminated. Then, the node that is using the source node as the upstream node may not be eliminated. Furthermore, the source node may also avoid eliminating infrastructure nodes because they help reduce the number of hops in routing and the chance of network interruption. Infrastructure nodes may be repeaters, gateways, and field service units (FSU). FSU cannot be removed for on-site debugging, firmware update, and other maintenance functions. Each node may be instructed to reserve a certain number of gateways and repeaters on its nodeq (the number can be expressed as a percentage of the size of nodeq). Finally, when a node has a route to a certain AP, it may try to avoid removing nodes that have not yet obtained the route. These nodes may obtain a route through the source node, so they should remain on the nodeq.

In one embodiment, the operation of the algorithm is as follows: Whenever N nodes are to be eliminated, a total of three actions may be performed through the nodeq to select the nodes to be eliminated. Each action may select nodes based on link quality (for example, each action will eliminate the lowest link quality). The first action may determine whether the node already has a route. If the node does not have any route, it may skip the first action and directly enter the elimination criterion in the second action described below. During the first action, a node may try to find N adjacent points that already have independent routes (nodes that do not use each other as upstream nodes). A node may know which neighbor it is using and which neighbors are using it, because those nodes that are not using it may send routing announcements to it every 20 minutes. If N nodes are found during the first action, no further actions may be taken, and the selected nodes can be eliminated. In the second action, the condition of "with a route" may be relaxed and nodes without a route may be eliminated. However, during this action, the node that is sending the maintenance message may not be selected. In the third action, even the node sending the maintenance message may still be selected for rejection. Ideally, the third action is not often reached because it may disrupt routing.

When a node is about to be removed, it may send a removal message to the node to let it know that it is no longer on the nodeq. This will prevent the following asymmetry: the culled node may still communicate with the culled node; however, the culled node will no longer communicate with it because the culled node is no longer on nodeq. To communicate.

When a node is selected to be culled, the cull sched flag may be marked and a culling message may be scheduled via the MLME scheduler. After the rejection message has been successfully transmitted, the designated node can be discarded. Occasionally, it may not be possible to send the culling message to the node. In this case, the node may be abandoned after several retries.

<b>Contingency routing technology reverse source route</b>

When a node has lost its network (in the reserved list) or for some reason receives a packet from a gateway that is not configured for it, it may not be able to contact the node. There may be many ways to establish a static route to the node; however, these methods can be very time-consuming. Furthermore, it may be difficult to insert a static route connected to a node, because before a person can obtain confirmation from the node/talk to the node, the person may have to insert the route into the routing table of the node.

The disclosure presented in this article provides a solution to this problem. When a node receives a source-routed packet from a gateway that is not in its routing table (or an IPv6 preamble configured with multihome), it may be automatically configured Set up the necessary multipath configuration, reverse the source route, and insert it into its IPv6 and its routing table. The route may only be valid for a short time (about eight seconds in one embodiment) so that the node can answer the AP. In one embodiment, whenever the AP sends a packet to the node, even if the route is no longer legal, it may still be reinserted.

<b>Through the downstream diversity of the guided trail-type route</b>

In some exemplary embodiments, the node may only reserve the route of the access point in the network. Therefore, they may not have any routes to other nodes. In the downstream direction, the packet may be routed out by a gateway. If they fail in a particular hop, they may not be delivered (the node may not keep the routing tables of all other nodes in the network).

The disclosure presented in this article can provide a way to overcome this problem and introduce downstream diversity. In one embodiment, the nodes may insert a guided trail route in the routing table of the destination to which they intend to deliver data traffic. When a node delivers a packet from a downstream source node, a guided trail route may be inserted into its routing table. The delivering node may know the MAC address of the source node, as well as the node that relayed the packet during the last hop and was located directly downstream of it. The delivering node may interpolate the layer 2 route to the source node passing through the immediate downstream node. Therefore, when the delivering node receives a packet destined for the original source node, it will have a route for delivering the packet. In one embodiment, if a node cannot deliver the packet along the source route in a packet, it may choose the guided trail route. In an exemplary embodiment, when it is determined that a packet cannot be delivered, the node may hand it over to the MAC layer; and if the MAC layer cannot send it within 8 seconds, up to 32 retries, it The packet may be deemed undeliverable. In one embodiment, nodes may store every navigation trail route they see. In another embodiment, the node may store two navigation trail-type routes for each destination (the newer one will replace the older one). In one embodiment, the navigation trails may be placed in a first-in first-out queue. In one embodiment, there may be room to store 2000 to 3000 routes. In one embodiment, the older route may be replaced by the newer route.

<b>Power management</b>

Power management technology can reduce interference/congestion in an ultra-dense deployment area in a utility network by reducing the transmission power of nodes. In one embodiment, a plurality of these nodes may be kept at low power; however, some nodes may still operate at high transmission power, so that they may be regarded as links leaving the dense area , Without increasing the number of hops used for routing transmission. Another feature of this technology is that nodes can automatically explore and adjust their power levels without any operational interference. In one embodiment, the hardware can adjust its transmission power. One way to achieve this is to provide a scale from 0 to 65 units in a predominantly linear scale range. For example, a value of 0 may represent 23dB, and a value of 65 in the predominantly linear scale range may represent 30dB.

An exemplary power management technique can be summarized as follows:

<u style="single">Detect this situation</u>: The source node may monitor how many nodes it wants to eliminate and also track the elimination messages from neighboring nodes with good RSSI/INFO%. The total number of nodes eliminated by the source node in its TX message, and the total number of nodes eliminated by another node in the receive (RX) message of the source node can be defined as K. For example, if the number K is greater than 100 (or another configuration setting number), then the node may be in a high-density deployment. In one embodiment, the number 100 is selected due to typical data traffic analysis in a utility network.

<u style="single">After detecting high density</u>: The node may use a random number to determine how much power it wants to reduce. In some embodiments, the power range may be from 35 to the minimum value of 1. At a percentage of 1/(4K), the node may let its power be at the maximum. In addition, if K&gt;200, the power level may be randomly selected in the range of 1 to 5. In certain other cases, the selected value may be in the range of 5-10. Therefore, after the first drop, there may be a second drop. After the end of the power drop, about 2 to 4 nodes may have the maximum power among 100 nodes.

<u style="single">When the node increases power</u>: If a node has too few nodes in nodeq (&lt;25 nodes) and the "neighbor restart" is completed (at this time, the excluded nodes in the bad neighbor list have been removed and two have passed Hours to re-acquire neighboring points) After the node still has nodes &lt;50 in the nodeq, the node may increase its power by 5 points.

<b>Route transmission interruption recovery</b>

When a network node restarts, it may need to notify the utility logistic server that the network node will experience a specific characteristic interruption event (full system interruption, regional network interruption, node device interruption, other interruption events) Has been rebooted.

In order to save packets in the utility network, it may be very inefficient to send a separate notification message to inform the logistics server every time the node restarts. Instead, in the present invention, each node may include an element that informs the gateway that the node has been restarted during network registration. The node may inform the gateway of the following together with the information:

How long has it been on

What is the nature of the interruption

Whether it has been rebooted "cleanly" or "uncleanly"

Whether there is a core on the node

What is the version of the core (if there is a core)

The information may be compiled on the gateway based on the state of the entire network. The gateway may form an SNMP TRAP that is sent to the logistics server. Therefore, the method of the present invention saves network data traffic and more quickly informs the logistics server that the nodes in the field have been shut down or restarted.

Although the main content of the present invention has been described with reference to specific embodiments in this article; however, those familiar with the technology can easily understand that there may be other embodiments other than those described above. It will not deviate from the spirit of the scope of patent application.

Therefore, the embodiments of the present invention are only explanatory and should not be regarded as having any restrictive meaning. The present invention intends to cover the scope given by the scope of the attached patent application (not the previous description) and all the variations and equivalent examples falling within the scope of the patent application.

<p>110. . . Network/WAN</p><p>120. . . AP/Gateway</p><p>130. . . Battery-powered device/network node/repeater</p><p>140. . . Continuous power supply device/network node/repeater</p><p>150. . . Utility Server (BOS)</p><p>160. . . Unlimited LAN</p><p>170. . . Infrastructure device node</p><p>810. . . WAN (Wide Area Network)</p><p>821-822. . . Gateway</p><p>831-832 (R1-R2). . . Repeater/adjacent point</p><p>841-843 (M1-M3). . . End node</p><p>860. . . BOS (Logistics Server)</p><p>870. . . Wireless LAN</p>

Figure 1A shows the overall network architecture of a possible embodiment.

FIG. 1B is an alternative representative diagram of the overall network architecture of a possible embodiment.

Figure 2 shows a representative diagram of the bit-by-bit structure of the link layer header of a packet to be routed.

Figure 3 shows an exemplary format of a network advertising message sent by a node to a special network known to it in the best path.

FIG. 4 is a simplified representative diagram of an exemplary routing table constructed at a node after receiving network advertisements from its neighbors.

The system shown in FIG. 5 may appear as an example of a route list composed of different route types at a node.

Figure 6a shows an exemplary format of an "upstream registration" message sent from a node upstream to another node; Figure 6b shows an exemplary format of an "upstream registration confirmation" message sent by the upstream node to the node that performs the registration .

Figure 7a shows an example format of an "Gateway Registration" (AREG) message sent by a node to the gateway it wants to register; Figure 7b shows an example of an AREG message with neighboring point information Sexual format; Figure 7c further illustrates the content of the AREG confirmation message with a network address.

The network shown in Figure 8 is a local network where multiple gateways, repeaters, and endpoint devices will appear one by one.

FIG. 9 shows an exemplary map of link costs between nodes that can establish RF communication links with each other in a possible embodiment shown in FIG. 8.