Updating routing and outage information in a communications network

Update path selection and interruption information in the communication network

The subject of this disclosure usually relates to packet routing in a communication network, and more particularly relates to the ability to quickly update routing information and send related notifications after a communication is interrupted.

When a node begins to appear on the network, it needs to obtain information that enables it to communicate with the destination node. In the case of a fixed wired network, its information can be programmed in the nodes in advance, so once it is activated, it can immediately communicate with other nodes. However, in other types of networks, nodes may need to know the configuration of the network before they can communicate with other required points. For example, a wireless specific subnet may have only one or at most a few access (access) points through which nodes of the subnet can communicate with destinations outside the subnet. Not all nodes in the subnet may have a direct link to the access point, so it relies on neighboring nodes to provide a communication path to and from the access point. Therefore, in order to assist the communication available in the network, nodes may exchange routing information, which provides information related to the number, length, latency, etc. of various access points.

When a node is first installed on a specific network, it may undergo a search process in which the nearest neighbors, that is, other nodes with direct communication links with it, are identified, and the direct links of these nodes It can provide a path to the access point. The node may continue to exchange information with its neighbors and update path selection information to ensure that it can still communicate reliably with the access point in an accessible way under dynamically changing network conditions. An example of the processing procedure that the node establishes the path to the access point through this procedure is disclosed in US Patent Application No. 2007/0120705.

Another situation in which a node may need to establish or confirm path selection information is after a reboot operation has been performed. This restart may be the result of many different conditions, such as software updates, power loss, scheduled maintenance procedures, and so on. After rebooting, the node may undergo, for example, the above-mentioned type of complete network search process to obtain path selection information and thereby resume communication. However, such processing may require a significant amount of time. It is better to use the information that may have been available for the node due to the network communication generated before the restart, so that the node can quickly recover and resume communication after the restart.

In a special application, a wireless specific network can be used to provide communication between the central control facility of the public utility and the meter provided by the utility to measure the power consumption of the user. When the dissemination of the power transmission to the user in which the consumption measurement power meter is co-located, the public infrastructure interruption occurs, the communication node of the specific wireless network associated with the meter and co-located may also lose power, and When the power transmission resumes, it needs to be restarted. In some cases, the power supply control facility may not be aware of the fact that the power has been restored with the user as the premises until the network node co-located with the power meter reconnects to the network on those premises and states that it has resumed operation. When a large-scale outage occurs and service personnel are returning to the facility on site, it may be expected that the utility will quickly learn whether the electricity has been restored, and if it has already responded, learn which node it has reached and which part of the public infrastructure has been disseminated. This recognition will enable the public utility to determine whether all the faults have been repaired and whether the recovery action can be terminated, or whether other faults still exist and whether some users still have no power.

According to an aspect of the disclosed invention, by evaluating the reliability of path selection information that can be accessed from other nodes in the network, the path selection information is updated in nodes that have undergone a reboot operation. What depends on the restart of the first node is that it receives restart information from at least another node in the network. The first node will retrieve the reboot information of other nodes previously stored in the memory. The restart information received from other nodes is compared with the information retrieved from the memory. If the comparison of the received and retrieved reboot information indicates that other nodes have not experienced a reboot recently as the first node, the path selection information downloaded from the second node is used to update the path selection information of the first node.

According to another aspect of the disclosed invention, after power is restored to a node of the utility network, the node will use a neighboring node to act as a proxy host to relay the message to the central control facility of the utility. The message contains information related to the returned node, and can also contain information related to one or more neighboring nodes. This information may include the restart counter, the number of times the node has been shut down, short interruptions or power fluctuations, and/or power recovery time.

FIG. 1 is a generalized block diagram illustrating a communication network 100 having a plurality of nodes 101. The node 101 may include a processing unit, memory (such as non-volatile memory), and a network interface. If the communication network is a wireless communication network, its nodes can also include one or more radio devices (or radio transceivers) to communicate with other nodes in the network. One or more nodes can also serve as an access point (or gateway) 102 to another network 103. One or more electronic computer devices 105 can be connected to the communication network 103. Examples of electronic computer devices include, but are not limited to, servers, personal computers, portable devices, mobile computing devices, mobile phones, and so on. One or more nodes may also be relay nodes 104, which relay packets between nodes and/or between one or more nodes 101 and gateway 102.

In a communication network with access point nodes, a node can be regarded as the "upstream" of another node, that is, it is considered to be closer to the access point node (closer can refer to the number of hops, geographical proximity, link cost, Link reliability, certain combinations of the foregoing, or other factors independently or in combination with the other factors listed). The "downstream" node may preferentially and/or choose to receive the path selection update of the upstream node.

During the operation of the communication network 100, a node can be restarted for any reason (spontaneous or non-spontaneous), including but not limited to power loss, operation and maintenance, automatic servo disconnection, and after firmware update The path selection node is refreshed, or other reasons. When the node is restarted and then restarted and then restored to its original state, it is better to receive path selection information from other nodes. When the restarted node has not been able to receive the update of path selection information, it is in "downtime". As other nodes in the communication network may also be down and have recently been restarted, the restarted node can receive path selection updates first, or from the node that has not been restarted recently or has been restarted at least before restarting and is more likely to have Other updates of nodes with newer path selection information.

Figure 2 is a generalized flowchart of updating and providing restart information to other nodes in the communication network. In step 201, a node is restarted. Corresponding to this reboot, in step 202, the node updates its reboot information. The node can update its reboot information during or after the reboot period. If the restart information is a restart counter, this update can increase the restart counter. The restart counter can be incremented by one, or some other operations on the restart counter can be changed. If the reboot information is a time stamp of reboot, then the time stamp of this reboot will be changed, so as to reboot the computer for the time. If the reboot information is a recent reboot value, this last reboot value can be set to indicate a value representing the reboot behavior within a predetermined period of time. Other restart information may include but is not limited to the latest firmware update list of neighboring nodes, link and path quality changes, and statistics of successful messages between neighboring nodes. In step 203, the reboot information is stored. In a currently preferred embodiment, the reboot information is stored in a non-volatile memory in the node. One example of a non-volatile memory type is flash memory. Other embodiments may store the reboot information in a volatile memory in the node, or in a volatile or non-volatile memory in a device or computer accessible by the node.

In step 204, a node such as a reboot will receive a request for information from another node in the communication network. The information request may be a specific request for reboot information, or the request may be for other information, such as a request for link or path selection information. In step 205, the node corresponds to the request for routing information. If the request is for path selection or other information, the restart information preferably includes the response. In addition, the path selection information request received by the node may include restart information corresponding to other nodes in the communication network. In another embodiment, the reboot information is exchanged with the path selection information separately. In this event, upon an information request, restart information corresponding to other nodes is received, and the node can store the received restart information. Preferably, the storage of the reboot information is in the non-volatile memory of the node such as flash memory. Other embodiments may store the received restart information in a volatile memory in the node, or in a volatile or non-volatile memory in a device or computer accessible by the node.

The requesting node will receive restart information from at least one other node. The requesting node can store the received restart information. The restart information can be stored in the memory or storage device associated with the node. In a preferred embodiment, the restart information is stored in a non-volatile memory such as flash memory of the receiving node. Other embodiments may store the received restart information in a volatile memory in the receiving node, or in a volatile or non-volatile memory in a device or computer accessible by the receiving node.

FIG. 3 is a generalized flowchart of the process 300 of using restart information to determine whether the path selection information from other nodes is used to update the path selection information of a given node. In step 301, the first node (or the node being restarted) will be restarted. During or after the reboot period, the first node may initiate a path selection update process, where in step 302, the first node transmits a path information update message to at least one neighboring node. In a preferred embodiment, the first node sends the path selection update message to the node that has been discovered. The nodes detected by the first node may be included in a list that can be stored in volatile or non-volatile memory, and located in its location or in a different location where it can be accessed safely and/or reliably. Preferably, these nodes are neighboring nodes. Alternatively, the first node can initiate a search process to find the node, which is performed as when the first node is not aware of other nodes in the communication network (as if the node has joined the network for the first time, or if the list of known nodes is missing or deleted, Or it may happen when the list of known nodes cannot be reached or is deemed unreliable). The path selection update message may include reboot information of the first node, and may include a request for reboot information update. The list of searched nodes can be used in the route selection update message sent in step 302. In step 303, the first node will receive path selection update information. In a preferred embodiment, the response to the path selection update information includes restart information. In another embodiment, the restart information can be received in a separate message, which can be received in response to a path selection update request, a restart information request, a request corresponding to other information, or automatically without Request from rebooting the node. In step 304, the first node can retrieve the reboot information held in other nodes. As discussed above, the reboot information can be stored in the memory, or in another accessible device or storage unit, and in step 304, the first node will retrieve the data on other nodes from this location. Saved reboot information. In a preferred embodiment, the retrieved reboot information may correspond to at least one node associated with the received reboot information, so that the first node will access the stored reboot information and at least one node location. Both of the received restart information.

In step 305, the first node may check the stored reboot information and the reboot information received by at least one node by, for example, comparing, so as to determine whether the associated node or most nodes have recently undergone a reboot. More specifically, the first node can make a judgment based on whether a given node corresponding to the stored restart information and the received restart information has newer path selection information than the first node. If the given node has not been restarted since receiving the corresponding stored restart information, or if the given node has not been restarted within a predetermined time interval before the first node restarts, the first node may Decide to use the reboot information obtained from the given node to update its path selection information. Depending on the type of reboot information obtained, the comparison made may change. For example, if the restart information is a restart counter, the comparison action may be whether the stored restart counter is equal to the received restart counter. If the stored restart counter is equal to the received restart counter, it can be determined that the given node has not restarted since the stored restart counter was received, and it can be determined that the first node will use the The path selection information of the node is used to update its path selection information. If in step 305 at least one node is determined to have path selection information that is newer than the path selection information of the first node, then in step 306, the first node will use the path selection information from the first node that has been determined to have more path selection information than the first node. The path selection information of at least one node of the new path selection information is used to update the path selection information. If the path selection information has not been received, the first node can make a request for path selection information to update the first node.

If none of the nodes checked in step 305 can be determined to have path selection information that is newer than the path selection information of the first node, then in step 307, the first node can determine whether there is another comparable node. If there is no other node that can be compared, the processing can end in step 308. If in step 307, the first node determines that there is another node to be compared, it can return to step 302 to obtain additional information from other nodes, and follow the comparison process from step 302. As the first node may have compared all nodes on which restart information is maintained, the first node may proceed to step 302, thereby requesting the stored restart information of other nodes, or even corresponding to the requested stored restart information. Reboot information to request reboot information from the node. Alternatively, if in step 307, the first node determines that there is another node to check the latest reboot, and the first node has the information required for the check, the first node can return to steps 304, 305, or any An appropriate other step.

The first node may compare the stored and received restart information of other nodes known by the first node in step 305 until it can find a node with newer path selection information than the path selection information of the first node. This may include requests for sending other reboot information for other nodes' reboot information. If a node that has not been rebooted recently is found, the first node will proceed to step 306 to update its path selection information.

In various different embodiments, the above processing may be combined in whole or in part without modification. For illustrative purposes, most exemplary embodiments are provided below.

Although the above embodiments are related to updating the routing information, alternative embodiments can update other information besides updating the routing information, or can update other information without updating the routing information.

<b><u style="single">Example 1</u></b>: A wireless FHSS (Frequency Hopping Spread Spectrum) communication network with 5000 nodes with most subnets uses IP-based communication protocols (for example, IPv4 or IPv6) to provide communication to 5000 public utilities. The utility meter measures the consumption of daily necessities provided by the utility (in this example, the daily necessities measured are electricity, but other embodiments can also measure water, gas, or other independent or combined daily supplies). A node of a utility (may include a meter, or may be coupled to a meter to provide meter reading and/or control). Contains routing information to allow nodes to communicate with one or more back office systems through most access point nodes. Most of the public utility nodes in the public utility network cannot directly communicate with the access point nodes. Therefore, a packet sent to and from a given node for part of the communication with a back office system is typically sent to another utility node from the beginning, which will relay the packet to the given node and one or more storage devices. Take points between nodes.

The utility will maintain and exchange restart counters. The reboot counter is an integer value, representing the number of reboots that the utility node has experienced. The restart counter of the utility node in the communication network is stored in the flash memory of the utility node. For example, if a given utility node called UN-471 has been rebooted three times, the reboot counter RebootCounter=3 can be maintained. According to the reboot action, the utility node UN-471 will increase its reboot counter by 1, resulting in RebootCounter=4. The utility node UN-471 will share its restart counter with its neighboring nodes (in this example, the nodes it knows and the information communicators with it). The sharing behavior is performed quickly after the restart counter is increased, and it can also be performed routinely (for example, when updating links and other information, or when exchanging packets).

When the utility node UN-471 performs a reboot, it first establishes a connection with one or more neighboring nodes based on the stored neighboring point information. After establishing contact with one or more neighboring nodes, the utility node UN-471 will request at least one neighboring node to provide its restart counter. If the utility node UN-464 is the neighboring node in communication with UN-471, the utility node UN-471 has requested the restart counter of the utility node UN-464, and the utility node UN-464 can be given It responds with the reboot counter, which is RebootCounterreceived=6. The utility node UN-471 retrieves the restart counter stored in UN-464, which is RebotCounterstored=5. The utility node UN-471 compares the restart counter stored in UN-464 with the received restart counter, and based on the fact that the stored restart counter is not equal to the received restart counter, infers UN-464 itself The reboot counter has experienced one reboot since the last time it was updated. Therefore, it is determined not to use the path selection information of UN-464 to update the path selection information of UN-471. UN-471 then tried to find the node that had not increased its restart counter and exceeded its stored restart counter. UN-471 can compare the restart counters of other nodes that have received and have their corresponding stored restart counters. It is also possible to request restart counters from other utility nodes. The utility node UN-471 will receive the restart counters of five other nodes, UN-469, UN-472, UN-473, UN-478 and UN-485, and UN471 also has the stored restart counters. By comparing the stored and received restart counters, UN-471 judges that UN-485 and UN-473 have not increased their restart counters (both the UN-485 stored and received restart counters are equal to 2. The UN-473's stored and added restart counters are both equal to 11). According to UN-485 is located upstream of UN-471 (in other words, both UN-471 and UN-485 are located on the same subnet, UN-485 has fewer connections to the access points of the subnet, and varies according to various Path selection, from UN-471 to Packets returned to UN-485 can be effectively transmitted through UN-485), UN-471 uses the information from UN-485 to update the path selection information of UN-471. Therefore, UN-471 requests route selection update information from UN485, and uses the received route selection update information to update UN-471 route selection information.

<b><u style="single">Example 2</u></b>: A wireless mesh network of multiple sensors (wireless sensor network) has 800 sensor test nodes. A mesh network has three distinct subnets, and some sensor nodes are located on more than one subnet. The sensor node maintains a reboot time stamp, which indicates the last reboot of the node. The last reboot of a sensor node labeled SN206 in the wireless mesh network was at 4:13 am on August 23, 2007, so the time stamp of the reboot is RBTS=0823070413. When other nodes request link or path selection information from SN-206, SN-206 and other nodes will share the time stamp. SN-206 is located on two subnets labeled SUB-1 and SUB-2 in the wireless mesh network. On its SUB-1, which maintains link information, SN-206 has ten neighboring nodes, and it also stores restart timestamps for the ten neighboring nodes. At 3:44 pm on September 17, 2007, SN-206 rebooted. During the reboot process, SN206 will update its reboot time stamp, which is RBTS=0917071544 at this time. After rebooting, SN-206 establishes contact with its neighboring sensor nodes and requests time stamp information from all neighboring nodes. In this exemplary embodiment, before requesting restart information, the SN-206 will wait until the neighboring node directly connected to it stabilizes. Eight out of ten neighboring nodes on SUB-1 can react. SN-206 compares the received timestamp with the stored timestamp for the eight nodes that responded. Only two of the eight neighboring nodes from SUB-1 to SN-206 have rebooted since SN-206 received the time stamp stored in its own memory. SN-206 selects one of the six neighboring nodes that have been judged to have not rebooted recently to request routing update information. In this example embodiment, SN-206 will select the neighboring point "upstream" of SN-206 in subnet SUB-1 with the lowest link cost, request routing information from this node, and target The subnet SUB-1 uses the received routing information to update the routing information of the SN-206. Similarly, SN-206 also establishes connections with its neighbors on the subnet SUB-2. SN-206 has five neighboring nodes on SUB-2, and SN-206 will request to come Reboot time stamp information from all five nodes. All five will respond by providing their current reboot timestamp to the SN-206. By comparing the stored and received restart timestamps, SN-206 will determine that no corresponding neighboring node has been restarted recently. Therefore, SN-206 selects the "upstream" neighboring node of SN-206 in subnet SUB-2 with the lowest link cost, requests routing information from that node, and uses it for subnet SUB-2 The routing information it receives is used to update the routing information of the SN-206.

<b><u style="single">Example 3</u></b>: The wireless mesh network of 1200 communication nodes is configured in a single network without subnets. The communication node is configured in a predetermined geographic area. There are two access point nodes and multiple relay nodes in the wireless mesh communication network. The communication node uses the restart information to maintain the restart path, which is a recent restart value indicating whether the communication node has been restarted within this time interval. The communication node CN-783 has not been restarted for more than one hour, so its most recent restart value is set to zero (RR_CN-783=0). It restarted at 9:21 am on September 19, 2007. During the reboot period, CN-783 will set the value of the most recent reboot to one (RR_CN-783=1), to indicate that it has recently undergone a reboot process. CN-783 requests the reboot information of the neighboring point it directly accesses. CN-783 has seven direct access neighboring points, five of which will return the last reboot value with a value of 1, indicating a reboot within the last hour. The two direct access nodes CN-773 and CN-779 will send back the zero recent reboot value to indicate that they have not rebooted within the last hour. Based on the returned reboot value, CN-783 selects the direct access node that has not been rebooted to receive path selection updates. Based on the link cost factor, CN-783 makes selections to request and receive routing information from CN-779 to update its routing information. One hour after rebooting, if it has not undergone another reboot, CN-783 will change its reboot value back to zero to indicate that it has not been rebooted within the predetermined "recent" time range. Similarly, other communication nodes in the wireless mesh network will update their recent restart counters according to the configuration.

FIG. 4 is a generalized block diagram illustrating a communication network 400 with a plurality of nodes 401. The node 401 is configured into two subnets 400-a and 400-b. A node with two or more network members may be referred to as a network overlapping node (NON) 405, or may be referred to as a node participating in a majority network. An example of a network overlapping node is a node with most subnet members in a given network. Subnets can be organized according to many feasible standards that include but are not limited to geographic areas. As discussed in the following example where subnets are arranged according to geographic factors, network overlapping nodes can communicate on more than one subnet, according to which such network overlapping nodes exist in which two or more subnets overlap In the area. One or more nodes can also serve as an access point (or gateway) 402 of another network 403. One or more electronic computer devices 407 can be connected to the communication network 403. Electronic computer devices include, but are not limited to, servers, personal computers, handheld devices, mobile computing devices, mobile phones, and so on. One or more nodes may also be relay nodes 404, which relay packets between nodes and/or between one or more nodes 401 and gateway 402. The relay node can also be part of more than two sub-networks, and can be referred to as a network overlapping relay node (NON relay) 406.

As above, in a communication network with access point nodes, one node can be regarded as the "upstream" of another node, that is, it is considered to be closer to the access point node (closer can refer to the number of hops, geographical proximity , Link cost, link reliability, some combination of the foregoing, or other factors). "Downstream" nodes can preferentially and/or choose to receive routing updates from upstream nodes.

During the operation of the communication network 400, a node or network overlapping nodes can be restarted for any reason (spontaneous or non-spontaneous), including but not limited to power loss, operation and maintenance, automatic servo disconnection, The path selection node refresh after the firmware update, or other reasons. When the rebooted node returns to its original state after rebooting, it is better to receive path selection information from other nodes. When the rebooted node cannot receive the update of path selection information, it "stops". As other nodes in the communication network may also be down and have been restarted recently, the restarted node can receive path selection updates first, or from the node that has not been restarted recently or has been restarted at least before restarting and is more likely to have Other updates of nodes that update path selection information. In addition, nodes that are restarting can preferentially receive routing update information from overlapping nodes in the network. According to such a node, it may have the latest path selection or other information, or a network overlapping node may provide network access to a given node or another network that can communicate through a network access point.

FIG. 5 is a generalized flowchart illustrating the process 500 of searching for an information update node by a node that is being rebooted. In step 501, the first node (or the node that is being restarted) restarts. During or after the reboot period, the first node may initiate a path selection update process, where in step 502, the first node transmits a path information update message to at least one neighboring node. In a preferred embodiment, the first node sends the path selection update message to the node that has been discovered. The nodes detected by the first node can be included in a list that can be stored in volatile or non-volatile memory, depending on their location or different locations that can be accessed safely and/or reliably. Preferably, these nodes are neighboring nodes. Alternatively, the first node can initiate a search process to find a node, as it can do when the first node does not know other nodes in the communication network (for example, because the node joins the network for the first time, or if the node list is known It may be lost or deleted, or when the list of known nodes cannot be reached or is deemed unreliable). The path selection update may include the restart information of the first node, and may include a request to update the restart information. The list of searched nodes can be used in the route selection update message sent in step 502. In step 503, the first node will receive path selection update information. In a preferred embodiment, the response to the path selection update information includes restart information. In another embodiment, the restart information may be received in a separate message, and its reception may correspond to a request for path selection update, a request corresponding to the restart information, a request corresponding to other information, or automatically not from Request to reboot the node. In step 504, the first node can retrieve the reboot information held in other nodes. As discussed above, the reboot information can be stored in memory, or in another accessible device or storage unit, and in step 504, the first node will retrieve the stored information on other nodes from this location The reboot information. In a preferred embodiment, the retrieved reboot information may correspond to at least one node associated with the received reboot information, so that the first node will access the stored reboot information and at least one node location. Both of the received restart information.

In step 505, the first node may check the stored reboot information and the reboot information received by at least one node by, for example, comparing, so as to determine whether the associated node or most nodes have recently undergone a reboot. More specifically, the first node can determine whether a given node corresponding to the stored restart information and the received restart information has newer path selection information for the first node. If the given node has not restarted since receiving the corresponding stored restart information, or if the given node has not restarted within the predetermined time interval before the first node restarts, then the first node You can decide to use the reboot information obtained from a given node to update its routing information. Depending on the type of reboot information obtained, the comparison made may change. For example, if the reboot information is a reboot counter, the comparison can be whether the stored reboot counter is equal to the received reboot counter. If the stored reboot counter is equal to the received reboot counter, it can be determined that the given node has not rebooted since receiving the stored reboot counter, and that the first node will be used from the given node To update its routing information. If it is determined in step 505 that at least one node has path selection information that is newer than the path selection information of the first node, then in step 506, the first node will use the path selection information from the node that has been determined to have more path selection information than the first node. The path selection information of at least one node of the new path selection information updates its path selection information. If the path selection information has not been received, the first node can make a request for path selection information to update the first node.

If none of the nodes checked in step 505 can determine that it has path selection information that is newer than the path selection information of the first node, then in step 507, the first node can determine whether there is another comparable node. The judgment of whether there are network overlapping nodes that check or retrieve updated information can be based on different types of information, which may exist in or be retrieved from different locations. For example, the first node may maintain a list of overlapping nodes in the network, and this list may be stored in the memory of the node. The node can compare the information on the nodes to determine whether any node can also communicate on the second (or more) network. Other alternative embodiments may enable the first node to send a message to request information for identifying the network overlapping node or allowing it to determine the network overlapping node through a response to the network overlapping node information request.

If there are network overlapping nodes, the first node can return to step 502 to request information on the network overlapping nodes, or it can return to another appropriate step to check the network overlapping nodes to determine whether the same is true. Experienced a recent reboot. In this preferred embodiment, if the network overlapping node has recently undergone a reboot, the first node will not select a network overlapping node for the purpose of updating path selection information. However, other alternative embodiments may choose to receive restart information from a network overlapping node that has been restarted. If it cannot find another node that has not been restarted recently, it includes any other network overlapping node.

In a preferred embodiment, if no network overlap node is found, or a network overlap node that has not been restarted recently is not found, the first node can proceed to step 508, where it can determine whether there is Alternate (replace) power nodes. Alternating power nodes may be any kind of nodes with alternate power sources. For example, if the first node is located on the first power network, restarting may have been the result of power loss on the first power network. When the first power network experiences interruption or power loss, using an alternative power source different from the first power network may not experience power loss. Examples of alternate power sources can be a separate electrical grid, an "off-grid type" power source (such as may occur with alternate power sources such as backup generators, such as wind, solar, etc.), batteries, or backup batteries (normally operated on Such as the first power source, but it also has a battery and a backup battery node that provides power if the main power source is lost).

The determination of whether there are alternate power nodes to be checked or requesting updated information can be based on different types of information, which may exist or be retrieved from various locations. For example, the first node may maintain a list of alternate power nodes, and this list may be stored in the memory of the node. The first node can compare the information on the nodes to determine whether any node is the same kind of alternate power node. Other alternative embodiments may enable the first node to send a message to request information, which identifies the alternate power node, or allows the first node to determine the alternate power node in response to a request for alternate power node information. If the first node determines that there is an alternate power node in step 508, the first node may return to step 502 to request information on the alternate power node, or may return to another appropriate step to check the alternate power node to determine Have any of them also experienced a recent reboot. In a preferred embodiment, if the alternate power node has recently undergone a reboot, the first node will not select an alternate power node for routing information update. However, other alternative embodiments may choose to receive the restart information of the alternate power node that has been restarted by itself, if it is impossible to find another node that has not been restarted recently, including any other alternate power node.

If there are no other nodes to check, its processing can be terminated at step 509. If in step 507 or 508, the first node determines that there are other nodes to be compared, it can return to step 502 to obtain additional information from these other nodes, and imitate the comparison process of step 502. As the first node may have compared all nodes on which restart information is maintained, the first node may proceed to step 502 to request the stored restart information of other nodes, or even request path selection updates. Alternatively, if in step 507 or 508, the first node determines that there is another node to be checked for the recent reboot, and the first node has the information required for the check, the first node may return to steps 504, 505, or Any other appropriate steps.

In step 505, the first node compares the reboot information stored and received by other nodes known to itself until it can find a node with path selection information that is newer than the path selection information of the first node. This can include requests for other node reboot information to send other reboot information. If it is found that the node has not been restarted recently, the first node will proceed to step 506 to update its path selection information.

Although the process illustrated in FIG. 5 causes the first node to check other nodes to find network overlap nodes or alternate power nodes, other embodiments may try to find nodes that act as both alternate power nodes and network overlap nodes at the same time. . Although the process illustrated in FIG. 5 causes the first node to check other nodes to find a network overlapping node before checking the node to find an alternate power node, other embodiments may try to find a network overlapping node before attempting to find a network overlapping node. Find an alternate power node, or you can try to find a network overlap node and an alternate power node in parallel, or you can try to find a network overlap node or an alternate power node, instead of trying to find the alternate power node and the network together Road overlaps both nodes. Although the processing illustrated in FIG. 5 causes the first node to compare the most recently restarted node after judging that the node is an alternate power node or judging that the node is a network overlapping node, an alternative embodiment is to judge that the found node is a network After one (or both) of overlapping nodes or (and) alternate power nodes, it can directly receive and/or use path selection to update information. Although the processing illustrated in Figure 5 causes the first node to check other nodes to determine whether a node has recently been restarted before finding one (or both) of the network overlap node or (and) the alternate power node, Other embodiments may try to find alternate power nodes or (and) network overlapping nodes before attempting to find nodes that are not one (or both) of alternate power nodes or (and) network overlapping nodes and have not been restarted recently. One (or both).

In various different embodiments, the above processing may be completely or partially combined without modification. For illustrative purposes, most exemplary embodiments are provided below.

<b><u style="single">Fan</u></b><b><u style="single">example</u></b><b><u style="single">4</u></b><b>：</b>A wireless mesh network of 6000 utility nodes coupled to utility meters. The wireless utility nodes are arranged in two sub-networks called UN-SUB1 and UN-SUB2. UN-SUB1 and UN-SUB2 each have a single access point node. The utility node labeled M2381 in the network resides in UN-SUB1. The utility node M2381 has twenty-six direct access adjacent nodes. The M2381 and other utility nodes in the network will maintain the restart information of neighboring points in their non-volatile memory. In particular, the utility network node in this embodiment uses a restart counter, which is periodically exchanged with its neighboring nodes during the period of routine network maintenance signaling. After rebooting, M2381 will request reboot information from other nodes, including the neighboring points of its direct link. The neighboring node responds with its individual reboot counter. The utility node M2381 compares the received restart counter with the corresponding stored restart counter, and judges that all corresponding nodes have also experienced a restart recently. The utility node M2381 requests restart information of another node. In particular, M2381 requests restart information from the upstream node. After receiving the response and comparing the received and stored restart counters, no node that has not undergone a recent restart is found. The utility node M2381 infers that the subnet UN-SUB1 has experienced a general interruption. Therefore, the utility node M2381 then sends the request of the routine announcement message to one or more network overlapping nodes to receive the routing information. The network overlap node selected to receive routine announcement messages is retrieved from the memory of the utility node M2381. Occasionally, there is no network overlapping node retrieved from memory between the nodes that M2381 has contacted. Based on the response received from the network overlapping node receiving the inquiry, it is determined that a network overlapping node M3947 has not restarted within the considered time range. Therefore, M2381 updates its routing information based on the routing information obtained from M3947.

Although in the above example, the network overlapping nodes are not between the intermediate nodes contacted by M2381 earlier after the restart, other embodiments may enable one or more network overlapping nodes to request restart information During the period and before judging that the subnet has experienced a general interruption, it is located between the contacted nodes.

<b><u style="single">Example 5</u></b>: A wireless mesh network of 10,000 utility nodes, where the utility node is coupled to the meter of the utility. Wireless utility nodes are arranged in most sub-networks, including networks UN-SUB6 and UN-SUB7. Both UN-SUB6 and UN-SUB7 have a single access point. The utility node labeled UM6411 in the network remains in UN-SUB6. The utility node UM6411 has fifty-three direct access neighboring points. After a reboot, UM6411 will request the membership information of the subnet from most nodes. The neighboring node will respond with its subnet member information. The utility node UM6411 analyzes the received subnet member information to determine whether any responding node is located on a subnet other than UM6411 as a member, especially the subnet UN-SUB6. Another utility node UM7948 responding with subnet member information is a member of UN-SUB7 and UN-SUB6, so it is a kind of network overlapping node. Therefore, the utility node UM6411 will then send the route selection announcement message to UM7948 to receive route update information. Therefore, UM6411 will update its routing information based on the routing information obtained from UM7948.

Although in the above example the node UM6411 can locate a network overlapping node through the first request of subnet member information, other embodiments may require most of the messages to be sent to locate a network overlapping node.

Although in the above example the node UM6411 can locate a network overlapping node through the first request of subnet member information sent after rebooting, other embodiments may allow the node to check its stored information , So as to locate a network overlapping node before sending a request for subnet member information.

Although the node UM6411 can locate a network overlapping node in the above example, in other embodiments, the node may not locate a network overlapping node, but may check the restart information of other nodes, so as to check the restart information of other nodes. The booted node receives the reboot information, as described in the other embodiments above.

Although the above example embodiment will update the path selection information based on the reboot information, other embodiments may update other information, including but not limited to path and link costs, the degree of environmental noise, and reference to a group of upstream nodes. Announce success rate, MAC address, time synchronization information, and FHSS spread spectrum sequence code. The path selection information may include the complete path to the destination, the partial path to the destination, or the packet to be sent to the next node under the destination, or any information that the node can use to select the path of the packet to the destination. It should be noted that the destination does not need to be in the same subnet or the same network as the transmitting node.

In some other embodiments, the requesting node that has been rebooted can be based on normal operation time (defined by how long the node has been served and operated between other nodes (which may all have the same reboot counter setting and path cost)). ) To select nodes for path selection information and update and next feasible jump selection.

As mentioned before, one situation that may cause the node to restart is the loss of power, which may be caused by the breakdown or interruption of the servo in the area given by the power distribution infrastructure. Figure 6A illustrates an example of a public utility communication network in which an outage has occurred. The utility network includes a wireless mesh network 600 composed of nodes 601, where each node is coupled to a utility meter at the user's premises. The node of the utility communicates with the back office server 602 of the utility through one or more access points 603, which provide a way out into and out of the wireless mesh network 600 formed by the node 601. The access point 603 communicates with the back office server 602 through an appropriate communication network 604 such as a wide area network. In the example of FIG. 6, the utility nodes labeled "A" to "H" are currently active and communicate with each other through the wireless link 605 in the network 600. In this example, the power interruption has occurred in some parts of the distribution network covered by the wireless network 600, which has caused some other nodes depicted in shaded areas to have no power and cannot communicate because of the lack of power.

FIG. 6B describes a situation in which power has been restored to a place where some utility nodes that previously had no power were associated. These newly replied nodes are represented by dashed circles, and are labeled "J" to "Q" and "X". These nodes can quickly obtain path selection information after rebooting, and resume normal network operations. Even before such normal operations are fully restored, they can inform the back office server 602 that the power has been restored to the location associated with the user. Individual nodes. Various embodiments for providing such notifications to the back office server are described below.

In one embodiment, after the power of the supply node is restored and the node completes the restart operation, it will start the process of searching for its neighbors, that is, other nodes with which it can directly communicate. In the example of FIG. 6B, node X finds that its current neighbors include nodes C, E, G, L, N, and Q. When node X establishes communication with each of its neighbors, it will exchange messages, including, among other information, the amount of time (age) that it has been continuously acting on the network since the node was last rebooted, And its path selection status. Based on this information, node X selects a neighboring node to act as its proxy host, and sends a recovery message destined for the proxy host node. Corresponding to the reception of this message, the agent host node operates in a normal manner, thereby selecting the path of the message to the back office server, and thereby notifying the node X that has recovered from the power loss.

The selection of the proxy host node can be based on one or more criteria. For example, the node being selected may only select neighboring points whose age is greater than a standard threshold and/or advertise that it has a path to the access point 603.

If most neighboring nodes advertise such a path, the selecting node may choose the neighboring point with the lowest path cost and link cost of its proxy host, where the lower cost represents the reliability of path selection. In the example of FIG. 6B, nodes L, N, and Q have only recently been online with node X, and therefore their age values may be small. In contrast, since nodes C, E, and G are not affected by the interruption, they may have acceptable age values. In addition, each node C, E, and G can provide a path to the access point 603. Based on the shorter path it provides to the access point (that is, the minimum number of hops), node X of the three nodes can select node C to act as its proxy host for sending recovery messages. It may be noted that the shortest path is only a choice. In other embodiments, if the path and link cost are lower than the shortest path selection, the longer path may be accepted for path selection.

The recovery message from node X that is recovering to the proxy host node C contains appropriate information related to its recovery state. This information may include the restart counter of the recovery node, the amount of time without power, any brief power outages or disturbances experienced, and/or power recovery time. The content of the recovery message may also include information related to the neighboring point of node X that has been searched. For example, in the example of FIG. 6, node N has not found a proxy host to send the recovery message because all neighbors are also affected by the interruption, and therefore may not meet any selection criteria. The recovery message from node X may contain information to indicate that it has been able to establish communication with each node L and Q, and may be its individual recovery state. Therefore, the utility will be informed that the power has been restored to all these nodes, even if each node has not been able to directly propagate its status to the utility. The recovery message from node X preferably includes an appropriate time stamp so that the utility can determine how new the information it has received about each node that is recovering.

The message can also be authenticated. The node that is recovering may use a public key cryptographic system to sign off the message, or it may use a shared secret and symmetric key cryptographic system. If the sending node uses a public key cryptosystem, both the neighboring point and the back office server can determine the message originating from the correct node. If a symmetric key cryptosystem is used, the authentication process may occur in two stages. The node that is recovering may choose a key shared between itself and the neighboring point of the proxy host. The proxy host then checks the authentication of the message, and if it is authentic, the proxy host can re-sign the message with its own key and send the message to the back office. Alternatively, the node that is recovering can use a secret code shared with the back office to sign the message. In this situation, the proxy host node may not be able to check the authenticity of the message.

The agent host node (referred to as node C in the above example) receiving the indicated recovery message can deliver the message to the back office server 602 through a known abnormal trapping and interruption mechanism. Within the Internet, certain incidents are regarded as abnormal incidents that the utility should be notified immediately. Power interruption and recovery from power interruption are two such abnormal events. The abnormal trap interrupt message is within the wireless network and is given priority by the access point 603 to assist its rapid transmission to the public utility back office server 602. When a message is sent using an abnormal trapping interrupt, the server of the utility is immediately notified of the message reception, enabling it to perform appropriate actions.

In another embodiment, the replied node does not need to wait for the neighbor search to start the notification processing. An example of this embodiment is illustrated in FIG. 6C. For reference, as soon as the power is restored and the node N has been restarted, it will automatically broadcast a restoration message. This broadcast can occur before and/or during the search process. If the geographic propagation of these nodes is sufficiently dense, the currently active node may cross-talk the broadcast recovery message, even if the active node is not a direct neighbor of the broadcast node N. In the example of FIG. 6C, each of nodes C and G will receive broadcast messages from node N. Once such a message is received, the receiving node can act as a proxy host and deliver the broadcast recovery message to the back office server 602 through the access point 603, thereby notifying the server and the access point of its power Has reverted to node N.

In the previous embodiment, the node that is recovering will take the initiative to send a recovery message to inform the back office server node of the power recovery after the interruption. In another embodiment, the server's notification can be initiated by a node instead of a node that has just been restored recently. Referring to FIG. 6, after the power has been restored, nodes L, X, and Q have searched for their neighboring points A, C, E, and G that are not affected by the interruption. Due to the messages exchanged during the search process, each of the nodes A, C, E, and G will be able to determine that the nodes L, X, and Q have an age less than a predetermined threshold (for example, 5 minutes). If the node that is not affected by the interruption remains for a minimum period of time (for example, 10 minutes), it will operate as a self-appointed proxy host, and generate to inform the back office server that some nodes have been on the network A message that has recently become active has been searched. Therefore, in this example, node A can send a message that node L has been found to the back office server and report its age, node C can send a message that each of nodes L and X has been found, And to report its individual age, node E can also send a report about the search of node X and its age, and node G can send a message related to the search and age of nodes X and Q. In this embodiment, the back office server relies on the "older" node to identify and inform it that it has recently returned to the restoration of the node.

In some implementations of this embodiment, a specific node that functions as a self-appointed proxy server to report information about restored nodes can be based on network density, the history of outage events within the network, and/or by the utility The performance measurement set by the server dynamically resets the age threshold used to report the node, so that the node can return to operation as soon as possible by using multiple redundant information collection techniques. For example, the age threshold for reporting nodes can be lowered to allow more nodes near the interrupted area, or some nodes recovered from the interruption, so as to report the health and status of the neighboring points of these nodes to the server. This helps the server to ensure that the reply is indeed in progress.

Theoretically, every time a node restarts, it can send the restored message to the back office server. However, from a practical point of view, when rebooting is an a priori event, there is no need to send such a message, for example, due to software upgrades, routine maintenance, commands corresponding to the server, and so on. The messages sent in these situations can cause unnecessary traffic on the network. Therefore, it is preferable that the transmission of the resume message is limited to the situation of restarting due to power loss, or other conditions that cause the node to undesirably shut down such an event.

For this purpose, it is possible to provide a mechanism for the node to enable it to judge whether the restart is according to plan or unexpected when it is restarted. As an example, when a node undergoes a planned reboot, it undergoes an orderly shutdown process to store its state and ensure that data will not be lost. At the moment when this process is suspended, it can set a flag to indicate that the shutdown is prudent, appropriate and complete. When restarting, the node can check the status of the flag, and if the flag is set, the normal search process will continue to operate, and the path selection information will be obtained. However, if the flag is not set (to indicate that the shutdown is not expected and/or is not performed in a methodical manner), the resume message can be transmitted as soon as possible.

In some embodiments, a node may have the ability to recognize when its main power supply has been interrupted, and to respond to such a situation by transmitting a "dying out" message that it is losing power and performing an orderly shutdown. For example, this point may have a small backup energy source, such as a battery or a capacitor storage device that provides sufficient power to perform such operations. In these embodiments, the node can set a flag to indicate that it shuts down due to power failure. When the node restarts, it can check the status of the flag, and if the flag is set, it will send a resumption message to indicate that the power has been restored.

Therefore, when the node shuts down unexpectedly, for example due to power loss, a dedicated message can be quickly sent to the back office server to provide a notification that the node has come back online. Even the node that is being restored can still transmit this message before it resumes the normal network operation associated with the path selection of the message. Instead of sending a message head-to-head from the originating node to the back office server acting as the destination, the restored message is assigned to the neighboring node that functions as a proxy host for the restoration node, and its processing is used to ensure Route selection function for sending messages to back office servers or other appropriate destinations.

The embodiments described here combine subsystems and functions to illustrate the current preferred embodiments. Other alternative embodiments include fewer or additional subsystems, processing, or functional perspectives, or can be used with other subsystems, processing, or functional perspectives, depending on the desired implementation. In the scope of the following patent applications, various features and advantages of the present invention are proposed.

<p>100. . . Communication network</p><p>101. . . node</p><p>102. . . Access point</p><p>103. . . Communication network</p><p>104. . . Relay node</p><p>105. . . Computer device</p><p>400. . . Communication network</p><p>400a/b. . . Subnet</p><p>401. . . node</p><p>402. . . Gateway</p><p>403. . . Communication network</p><p>404. . . Relay node</p><p>405. . . Network overlap node</p><p>406. . . Network overlap relay node</p><p>407. . . Computer device</p><p>600. . . Wireless mesh network</p><p>601. . . node</p><p>602. . . Back office server</p><p>603. . . Access point</p><p>604. . . Wide area network</p><p>605. . . Wireless link</p>

When combined with the drawings, it is easy to see and better understand the foregoing viewpoints and many accompanying advantages of the present invention by referring to the above detailed description, among which:

FIG. 1 is a generalized block diagram illustrating a network on which path selection update processing can be implemented according to a feasible embodiment.

FIG. 2 is a generalized flow chart of the process of updating restart information and notifying other nodes of restart information according to a feasible embodiment.

FIG. 3 is a generalized flowchart illustrating the process of using restart information to determine whether the path selection information from another node can be used to update the given path selection information according to a feasible embodiment.

Fig. 4 is a generalized block diagram illustrating a communication network with a plurality of nodes according to a feasible embodiment.

FIG. 5 is a generalized flowchart illustrating the process of searching for nodes to update information through a restart point according to a feasible embodiment.

Figures 6A-6D illustrate a utility communication network that has experienced a power outage, and various embodiments that provide notifications in response to nodes.