Method and system for providing a network and routing protocols for utility services

METHOD AND SYSTEM FOR PROVIDING A NETWORK AND DIRECTION PROTOCOLS FOR UTILITY SERVICES

0001 The field of use of the invention relates generally to network-based computer networks and systems, and more specifically to a method and system for providing a network and routing protocols for utility and home services.

0002 Illustrative embodiments show a routing scheme and protocols in an RF network (a wired or wireless LAN) operating in FHSS mode to allow two-way communication between utility and home appliances (such as electric meters). , water meters, gas meters, Automatic Distribution (DA) devices, and basement devices) that are IP hosts in the RF LAN, interconnecting with the Utility Host System (also called Administration Server or BOS) which is an IP host from a wireless or WAN (Wide Area Network) infrastructure. The IP version of the illustrative embodiment is IPv6. IPv6 packets are encapsulated in IPv4 for transmission over the WAN cloud, usually based on IPv4. The method of routing IPv6 packets within the wireless LAN includes providing an Access Point (AP) that can encapsulate (for example, IPv6 in IPv4 packets) in its LAN and WAN gateway capability, and provide a a multitude of IPv6 endpoints or devices that appear to be directly connected to the IPv6-level PA access point.

0003 Physically, endpoints or devices are able to establish radio transmission paths directly to the PA access point (single jump to the PA access point) or to other IPv6 devices (multiple jumps to the PA access point) , and the algorithm and methods according to the present invention describe how the network topology is created between the PA access points and how the packets are directional using the data link layer (Layer 2 of the OSI model). Devices or nodes become available, discover available networks, select networks to connect to, choose an ordered set of viable uplink candidates as the next leap in their routing scheme, register with uplink nodes with the best route and connection cost, Finally, it is registered with the PA access points associated with one or more.

4¾ Λ * tel, ^ - z

STATEMENT OF INVENTION AND TRADEMARK Patent Application

r ..... f^; ua deposit ..........; ...........^;

⁇^κ-2009-01 040-2 7 -05- 2008 more networks available. The network discovery process performed by the nodes ensures that there are routes for forwarding packets forwarding to the PA access point to exit the Utility Host System, along with explicit registration with the upstream nodes, and the PA access points provide PA with the most up-to-date information about the network and ensures that traffic can flow downstream of the node. This is a routing scheme with multiple outputs and multiple inputs, in which a network node can be part of several networks through one or more PA access points (access gates).

0004 The above features as well as others, including various new implementation details and combinations of elements, will now be described in more detail with reference to the accompanying drawings and underlined in the claims. It will be understood that the particular methods and systems described below are presented by way of illustration only and not by way of limitation. As will be understood by those skilled in the art, the principles and features described herein may be used in a variety of embodiments without departing from the scope of the invention.

0005 Figure 1A illustrates the entire network architecture according to a possible embodiment.

0006 Figure 1B is an alternative representation of the entire network architecture according to a possible embodiment.

0007 Figure 1C is a generalized block diagram of a wireless utility network according to a possible embodiment.

0008 Figure 2 is a bitwise representation of a starting block on the link layer for a packet that is directional.

0009 Figure 3 shows the format of the Network Warning message sent by a node about the best route to a particular network known to it.

0010 Figure 4 is a simplified representation of the routing table built at a node after it receives network warnings from neighbors.

0011 Figure 5 is an example of a list of routes with different types of routes that may be present at a node.

0012 Figure 6 shows the format for an “upstream registration” message sent by one node to another node upstream.

<img file="RO125809A2_D0001.tif" />

2009-01040-2 7 -05- 2008

0013 Figure 7 is an example format for an upstream registration acceptance message ”sent by the upstream node to the node that wants the registration.

0014 Figure 8 is an example format for a “PA recording message” sent by a node to a PA with which it wants to register.

0015 Figure 9 further illustrates the contents for the description of the neighboring AREG contained within the PA registration message ”.

0016 Figure 10 shows a network in which the end node is connected by several relays to more than one PA access point that provides the output in a WAN.

0017 Figure 11 is a representation of the order list of upstream jumps generated by the end node M1041 for networking during the networking process illustrated in Figure 10.

0018 Figure 12 illustrates the network in Figure 11 where a change in one of the connection costs occurred.

0019 Figure 13 is a representation of the rearranged list of upstream jumps generated by the end node M for exiting a Network during the process of updating the route in the network illustrated in Figure 13.

0020 Figure 14 is a sample network where multiple PA access points, relays, and endpoint devices appear one at a time.

0021 Figure 15 shows a map of the costs of connections between all nodes that can establish RF communication links with each other, in a possible embodiment.

0022 Figure 16 provides descriptions of the notations used in Figure 17.

0023 Figure 17 is a summary of the process of determining and propagating the route that occurs when a node is turned on in the network in Figure 14 to obtain the link.

0024 Figure 18 describes a network configuration with multiple outputs / multiple inputs for adaptive targeting.

0025 In the following description, for the purpose of explanation, specific language is provided to provide a full understanding of the various inventive concepts disclosed herein. However, it will be apparent to one skilled in the art that these specific details are not necessary for the implementation of the various inventive concepts disclosed herein.

^-2009-01040-2 7 “05“ 2008

0026 Portions of the following detailed description are presented in terms of algorithms and symbolic representations of operations on data bits inside a computer memory. These descriptions and algorithmic representations are the means used by those skilled in the art in the fields of data processing to most effectively transfer the essence of their work to others skilled in the art. An algorithm is designed in this case, and in general, to be an independent sequence of steps in series and in parallel leading to the desired result. The stages are those that require manipulations of the physical quantities.

0027 It should be borne in mind, however, that all these and similar terms must be associated with the appropriate physical sizes and only appropriate labels applied to these sizes. Unless specifically stated otherwise as is evident from the following description, it is appreciated that in the course of the description, submissions using terms such as "processing" or computing "or calculating" or determining "or displaying" or the like refer to the action and processes of a computer system, or similar electronic computing device, which manipulates and transfers data represented as physical quantities (electronically) in computer system registers and memories to other data similarly represented as physical quantities in computer system memories and registers or other such storage, transmission or display devices.

0028 The present invention also relates to an apparatus for performing the operations herein. This device may be built specifically for its intended purpose, or it may comprise an ordinary computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program can be stored on a computer-readable medium, such as, but not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magneto-optical disks, memory only ROMs, random access memories (RAM), EPROMs, EEPROMs, magnetic or optical cards or any other suitable medium for storing electronic instructions, and each coupled to a computer system channel.

0029 The algorithms, processes, and methods set forth herein are not inherently associated with or restricted to a particular computer or device. Various general purpose systems may be used with programs in accordance with

<img file="RO125809A2_D0002.tif" />

^ -2009-01040-2 7 -05 “2008 disclosures herein, or it may prove advantageous to build a more specialized apparatus for performing the required method steps. The structure required for a variety of such systems will emerge from the description below. In addition, the present invention is not described with reference to any particular programming language. It will be appreciated that a variety of programming languages ​​may be used to implement the disclosures of the invention, as described herein.

WIRELESS NETWORK

0030 Referring to Figure 1A, a communication network includes a plurality of 140 and 130 devices (nodes) connected to each other (at least one or more) and to one or more Access Points (APs) within the network. wireless LAN 160. Unless otherwise stated, PA access points may alternatively be referred to as Gateways. ' In contrast, PA access points can be connected to one or more management systems (BOS) 150 via one or more networks 110, typically Wide Area Networks (WANs). An administration system may be deployed on one or more computing devices, for example a central server, such as the central server 150 as shown in Figure 1B, and may be deployed across one or more networks.

0031 Referring to Figure 1B, nodes, such as Battery Powered Devices (BPDs) 130 and / or Constant Powered Devices (CPDs) 140, can discover available networks 110 by listening to all neighbors with whom they can connect, select one to which they can connect and can choose a set of upstream variable candidates as their next leap. It should be noted that in this preferred embodiment, CPDs can act as intermediates for BPD. However, alternative embodiments may allow BPD to participate directly as nodes in the wireless network without an intermediate element.

Example 1

0032 Node M-1, a constantly powered device 140 in Figure 1A, hears about two WAN-1 and WAN-2 networks such as WAN 110 (with unique IP addresses) from its neighbors and registers with both PA-1 and with PA-2 type Access Point 120 that provides access to WANs. It does this through the upstream nodes M-5, M-6, M-18, M-2 and M-12, of the Constant Power Device type 140 in order to communicate with BOS-1 of the Central Server type 150. / ΜΜτ ' Αχ gray.

AA Ș '

- 2 Ο Ο 9 - Ο 1 Ο 4 Ο - 2 7 “05“ 2008

Each of these nodes can build a direction table with an order list of the next jumps and the costs associated with the link (costs adjacent between the local node and the next jump) and route costs (the cost required to exit by the next jump). Each node is still registered with the upstream neighbor and the access gate 120. Gateway 120 can track the network topology and capabilities of all devices in its controller, as well as other devices. Nodes can maintain the local state and the state of their close neighbors, and can periodically update their records.

WIRELESS UTILITIES NETWORK

0033 The following illustrative embodiment provides a network-based system and the method of monitoring or controlling a utility meter in a utility network.

0034 Figure 1C is a generalized block diagram for a utility network 170 that can be used to practice the embodiments of the present invention. The utility network 170 may include one or more electronic devices 171, or nodes. In a preferred embodiment, the electronic devices 171 may be connected to a wireless local area network (LAN) 172. In the utility network example, a LAN may be a neighboring area network (NAN) corresponding to a neighboring area or utility service. As shown in the illustrative embodiment, multiple LANs may be used, which may or may not overlap, so that a given electronic device may be connected to (or may be part of) only one wireless LAN. or to multiple wireless LANs. Nodes can be any type of electronic device. Examples of electronic devices, or nodes, include utility nodes, which may include a utility counter or connect to a utility counter. A utility meter is a device that is able to measure a metered size, usually a product such as electricity, water, natural gas, and so on. Utility nodes connecting a utility counter may include a network interface card (NIC) for network communication, may include one or more RF transmitting / receiving devices for communication over one or more wireless LANs, and may include one or more utility meter interface devices (a given utility node may interface with multiple meters, which may or may not meter different products, such as electricity, gas, water, etc.). Utility nodes may include

<img file="RO125809A2_D0003.tif" />

5:2- _TO.

η υΰ * '^ 2 0 0 9 - 0 1 0 40'2 7 -05- 2008 also an interface for basement devices to connect devices in the basement via a network in the basement (which may or may not be a wireless network). The interface with the footer device connects to the footer devices to ensure the communication link between the utility node and the footer devices. In addition, the utility node can provide a communication link between the devices in the basement and the wireless communication network connected to the utility node. Other examples of electronic devices include communication devices, such as height-fixed cassettes (such as those used in the provision of cable or satellite television services), household appliances (eg refrigerators, radiators, lighting). ni), cooking appliances, etc.), computers or computing devices (eg game consoles, storage devices, PCs, servers, etc.) network implementation devices such as relays, access gates, access points, routers or other devices for implementing a network, telephones or mobile phones, battery storage devices, transport devices, transport vehicles (for example, an electric or hybrid car or other vehicle, which may or may not be able to “connect” to a utility network to receive a metered / monitored product such as electricity), entertainment devices (e.g., TVs, DVDs, height-mounted cassettes, game consoles, etc.), or other device that can be found in a home, office on the highway or in a parking lot, or in another location. Relays can handle communication between electronic devices 171 and the wireless network 172. For example, a relay can provide communication between the electronic device and the infrastructure of the wireless network. Unless otherwise noted, other devices in the network, such as meters, electronic devices, gateways, etc., may act as relays, and the relays may perform the functions of other devices or computer programs in the network.

0035 The LAN 172 can be any type of wireless network, and can use any frequency, communication channel, or communication protocol. In a preferred embodiment, that one or more LAN 172 wireless networks are FHSS (Frequency Spread Spectrum) networks.

0036 LANs 172 are typically connected to one or more access points (PAs) 173. A given LAN may be connected to a single PA access point, or may be connected to two or more access points. Access points 173 may be connected to one or more wide area networks

<img file="RO125809A2_D0004.tif" />

L \ - 2 OO 9 - D 1 O 4 O - 2 7 -05- 2008 (WAN) 174. WAN 174 can be connected to one or more management systems (BOC) 175. The management system can handle a variety of business or management tasks, including participation in the collection of metering information, metering device management, network security or other functions, as may be desired in an AMI network. Examples of management systems include billing and accounting systems, proxy servers, downtime detection systems (such as those used in a utility network), data storage systems, and so on.

0037 Nodes in a communication network, which can be a LAN or WAN, or a combination of the two, can communicate using one or more protocols. Nodes can include an electronic device, a relay, an access point, a router, or a BOS. Node lines may be able to communicate using IPv6, some may be able to communicate using IPv4, while some may be able to communicate on both IPv4 and IPv6. Some nodes may be able to encapsulate IPv6 packets into an IPv4 packet. In addition, some nodes may be able to establish an IPv4 tunnel over an IPv6 network. The communication between the nodes and the routing and used inside the wireless communication network that connects the nodes, are described in more detail below.

0038 In a preferred embodiment, a routing protocol used is a multi-exit / multi-entry hop-on algorithm for determining an optimal route to / from the destination, which may use route cost and / or a history. of stable upstream or downstream targeting as a metric for determining the next jump for targeting a packet. In this preferred embodiment, jump accounts are not used to estimate the cost of the route, but are used to prevent routing loops, as described below. In such an embodiment, a node may select the route with the lowest cost value as the preferred route for packet transmission.

0039 In a preferred embodiment, a targeting protocol is used in the scanning process to detect the initial network by the new node through all slots or channels to find (preferably) all neighbors and to obtain acceptance responses and a initial value of the estimated values ​​regarding the quality of the connection for those discovered neighbors. This value + - 2 0 0 9 - 0 1 0 4 0 -2 7 -05- 2008

<img file="RO125809A2_D0005.tif" />

Initial link quality estimate can be used to select a number of the best upstream neighbors to discuss (the selected number can be configurable).

0040 registering a node with its upstream nodes in this preferred embodiment means that the node intends to use these upstream nodes to exit to another network. In response to the upstream node entry, the upstream node will add the downstream node that was registered to the downstream routing table entries maintained by the downstream node. Upstream nodes can also keep up-to-date timing information about the node that was recorded in response to the downstream node record. The routing of nodes through each other is preferably set to periodically change timing information in order to stay in sync and exchange packets in the RF LAN using FHSS methods. In this embodiment, time updates are carried on any data transfer messages, but an explicit exchange of time information may be triggered if there was no data exchange for a pre-configured interval (e.g. order of 30 minutes).

0041 registration of a node with one or more PA access points can then take place. This registration process will preferably require the PA to add the node it wants to register to its targeting table and ensure that the node status is updated. PA node registration may occur periodically but less frequently than upstream node registration. In the present preferred embodiment, the frequency is in the order of every 12 hours.

ASSIGNING AN ADDRESS

ASSIGNING AN IPv6 ADDRESS

0042 Each node 130, 140 within the wireless network can be identified for end-to-end routing in any particular network by a unique IPv6 address. IPv6 addresses typically consist of two logical portions: a 64-bit network prefix and a 64-bit host portion. After successful registration by a node with a PA access point, the PA access point can transmit to the node a set of TLVs (Length Type Value) containing the node configuration, including the associated IPv6 global addressable prefix

<img file="RO125809A2_D0006.tif" />

a- 2 0 0 9 - 0 1040-2 7 -05- 2008 with the sub-network to which the node joined. The node can then send a Dynamic DNS update request (RFC 2136) to the DNS server (BOS) of the Network Host Utility System. When an application server wants to send traffic to the wireless LAN, it can change the DNS name of the node to a Layer 3 (IP) IPv6 address by directing it over the WAN to the correct PA access point. If the WAN is based on IPv4, IPv6 packets can be encapsulated in IPv4 with the appropriate prefixes for channeling through an IPv4 cloud. At the BOS level, the received IPv6 packet will be decapsulated.

0043 A node can be registered with multiple networks either on the same PA access point or on multiple PA access points, in which case it can set the order of priorities for the networks it belongs to based on its estimates or cost calculations. the lowest route. In this preferred embodiment, the node will have an IP address for each network with which it is registered. The DNS server can associate these IP addresses with the node's hostname in a preferred order according to the policies defined on the DNS server. When the BAN server in the WAN wants to send traffic to the wireless LAN, the DNS server goes through IPv6 addresses to resolve the node host name. As described above, the IPv4 cloud in the WAN can be traversed by encapsulating the IPv6 packet at the BOS server in an IPv4 packet with the appropriate prefix to allow channeling.

ASSIGNMENT OF THE LINK ADDRESS

0044 Each node 130, 140 can be identified by routing in the wireless LAN through a unique address for the link layer assigned to its radio interface, in this embodiment, each node has only one interface. Other embodiments may have several discrete addresses for the bonding layer. The addresses of the link layer are typically 8 bits long and represent the MAC address of the device. The radio address of the link layer can be hex ff: ff: ff: ff: ff: ff (all of them). Transmission packets with this local radio address are preferably processed by each recipient.

Forwarding a packet on the RF link layer

0045 Figure 2 illustrates the bit composition for the link layer title file that can carry the information as explained in the table below.

<img file="RO125809A2_D0007.tif" />

χ - 2009-01040-2 7 -05- 2008

0046 The label tags worn by the link layer title file shown in Figure 2 are shown in Table 1:

Table 1

<td>Bit (s)</td><td>Name</td><td>Description</td>

<td> 0-3</td><td>Version</td><td>Protocol version number. If a larger version is received, the frame is removed</td>

<td> 4-7</td><td>Protocol ID</td><td>Protocol id on top layer: - 0x03 SSN targeting protocol - 0x04. IPv4 network transmission protocol - 0x06: IPv6 network transmission protocol - 0x07. follow data link</td>

<td> 8-12</td><td>Account Address</td><td>Indicates the total number of addresses contained in the data link title file, including the source, destination, and any intermediate address for source-directed packets</td>

<td> 13-17</td><td>TTL</td><td>This is set when the package is generated. The initial value is set to "Automatic TTL" and is configurable. TTL is reduced with each jump the packet traverses</td>

<td> 18-22</td><td>Current gap</td><td>Set to 0 for packets that do not use source routes. This is set to 0 when the packet is first sent over the network. It is increased with each jump that the packet crosses</td>

<td> 23-25</td><td>Priority</td><td>The DLC layer supports 8 priority levels, this field falling directly on those priorities.</td>

<td> 26</td><td>Source Route Bit</td><td>Indicates whether the package contains the entire hop-by-hop route to be used between source and destination</td>

<td> 27</td><td>Route Preservation Source Route</td><td>Determined when the forwarding code L2 will preserve the items in the source path when forwarding the packet downstream. If this is not set, the forwarding code L2 may decrement the intermediate jump address once a forwarding decision has been made.</td>

<td> 28-31</td><td>Reserved</td><td>Book for future use</td>

0047 As shown in Figure 2, the labels are followed by the source address of the node that generated the packet. In this preferred embodiment, the address of the source of the label can never be set as the radio communication address.

0048 As shown in Figure 2, the source address is followed by the address of the next hop on which the packet is to be transmitted. In this preferred embodiment, if the Source Route bit is set then the entire list of hop addresses ending with the destination address is included, otherwise

<img file="RO125809A2_D0008.tif" />

Λ- -Î0C9 - Ο 1 0 (Ο - 2 7 -05- 2008 only one next jump is specified. In each case, the final address is the destination to which the packet should be directed.

0049 If the source path bit is set, the packet title file contains the full path that the packet will follow. Note that a packet can be directional from the source between two nodes without intermediate hops (i.e. Add Cnt is 2, and the destination address is either a node or the radio communication address). This is a mechanism that can be used to query individual nodes 120, 140 from a terminal such as a mobile de-virus station.

0050 If the source path bit is not set, the L2 forwarding code from a node can make a decision based on the value of the Address Account field. For example, if the Address Account is equal to 1 on a packet to be sent from the RF LAN to the WAN (117) or Central Server (150), it means that the packet can be forwarded to any exit node or access point. PA from the system. If the respective Address Account is greater than 1, it means that all additional addresses in the transmission table farther from the node have L2 output destinations allowed. The addresses in the forwarding table for a network are preferably sorted from least preferred to most desired.

0051 If the respective Account Account is larger than 1, the packet may be redirected to a different L2 destination in the event of a congestion or error. When a different L2 destination is selected, the previous network must be removed (either by reducing the Current Offset or assigning the zero value to the previous field). Removing the previous network is intended to help reduce the occurrence of routing loops, where a packet can be re-injected farther from the destination than the original source.

0052 Preferably, TTL gets a lower value when a packet passes through L2 of a node. Packets passing through L2 are lost when TTL becomes zero; Zero TTL messages for the local host are delivered from the stack. Nodes 130, 140 that send messages to the access point PA (gateway) 120 without fully using the source route of preference shall set their TTL so that there is at least the number of jumps on the longest path leading to access point PA 120. Maximum TTL can be configured by the administrator. In the present embodiment y sa î iz c \ - 2 OO 9 * 0 1 O 4 O - 2 7 -05- 2008 preferred, packets sent with the destination address set to be the value of L2 radio communication, are not forwarded.

0053 Preferential packet delivery is preferably accepted by the DLC (Data Link Control) layer. Broadcast packets may be implemented in the form of packets transmitted preferentially in the FHSS scheme, and are also preferably accepted. Unsupported packets cannot be transmitted preferentially. When a node 130, 140 transmits packets to a neighbor, the MAC layer can report the number of withdrawals and the possible success of the transmission. The network layer can keep records of this information on a per-neighbor basis.

DIRECTION SUBSYSTEM

0054 In this preferred embodiment, the targeting subsystem can be divided into four functional components:

- scanning and discovering neighbors

- keeping neighbors

-recording the node with the upstream neighbors

-recording the node with the access point PA

0055 This preferred embodiment of the targeting subsystem uses the DLF (Data Link Forwarding) code entity for Layer 2 and the MLME (Media Access Control Sublayer Management Entity) code entity for the acquisition of nodes. neighbor and maintaining timing information between neighbors. The DLC code interfaces with MLME through a set of APIs.

SCANNING AND DISCOVERING NEIGHBORS

0056 Nodes such as CPD 140 can initiate network discovery when, for example:

- has no viable output nodes (not associated with any of the PA access points)

- communications with upstream nodes have been interrupted, either administratively or due to partial problems or loss of propagation

- a regular recording message at one of its PA access points failed at least 3 times

- a new network is announced

<img file="RO125809A2_D0009.tif" />

(> 2 Ο Ο 9 - Ο 1 Ο 4 Ο - 2 7 -05- 2008

0057 Nodes such as BPD 130 can initiate network discovery, for example, if the connection to the nominated master (node ​​CPD 140) has been broken.

0058 In the illustrative embodiments, a node discovers neighboring nodes using two basic processes: discovering radio communication and searching for neighbors. When a node appears, MLME can find all the adjacent nodes (or connected directly to the RF links) through a process of radio communication discovery ”. He can do this randomly to determine when to start transmitting radio detection frames and then choose the channel on which to transmit the radio detection frame (the channel section can be done randomly). It can then move through each slot, transmitting each successive frame of radio communication discovery from the next slot, wrapping on the last slot. In the preferred embodiment, this process ensures that a radio communication detection frame is transmitted on each channel in a sequence in jumps over the FHSS-based network.

0059 In the illustrative embodiments, there are two ways of discovering radio communication: aggressive and passive. When powered, a device can aggressively enter detection mode by sending detection frames at random intervals that can be in the order of milliseconds. It can enter passive detection mode when the aggressive detection time has expired. In passive detection mode, a node may wait a longer period of time between sending radio communication detection frames, usually in the order of minutes.

0060 Once the discovery process has found a neighbor (an adjacency), or a set of neighbors, MLME can then search for the discovered neighbors to establish direct neighbors (preferably, all direct neighbors will be provided in response). This can be done to discover the vicinity of the network faster (in contrast to the radio communication of a large number of frames in jumps for contacting any particular device). The neighbor search mechanism is preferably a simple question / answer procedure: a node that receives the neighbor search query applies the criterion, preferably to all nodes in its list, and preferably all nodes that "match" the criterion are placed in response to the neighbor. If no criteria is given, all nodes in the list can be placed in the neighbor's answer.

<img file="RO125809A2_D0010.tif" />

_⁇-2 Ο Ο 9Ο 1 Ο 4⁰ ‘ ^⁇ 2 7 -05- 2008

<img file="RO125809A2_D0011.tif" />

0061 MLME can notify DLF when the discovery procedure is completed, i.e. (preferably) all nodes have been queried over their neighbors and an attempt has been made to obtain these neighbors.

0062 Using the list of neighbors built by MLME, DLF will try to find the announced exit routes. This can be accomplished by listening to the “Network Announcement” (NADV) messages from the devices in the MLME Neighbor Table.

0063 The NADV message may announce a set of exit routes, which may include the cost of the route and the jump value of the exit routes. The cost of the route is the lowest cost associated with that exit (PA) of all candidate routes. The jump value is the largest number of jumps that must be performed to reach the exit. The value of the jumps is used to prevent the direction loops, and is not used in conjunction with the cost of the route. The format of the NADV message is shown in Figure 3. The destination MAC address is the MAC address of the device from which the last network alert came. in most cases this is the exit point (or PA) because the networks are identified by their output nodes.

0064 From the announcements received as NADV messages, each node can build a targeting table that lists all available networks, the outgoing node (AP) that identifies each network, and the available paths for that outgoing node. Preferably, each of the available routes is described by the next jump, the labels describing the type of route and the costs associated with the connection and the route. Labels indicate the type of route - if it is a permanent entry in the table, if it can be announced by the node, etc. In the preferred embodiment, the node will decide to register with that upstream node for which the total cost (connection and route costs) of the network is the lowest. Other embodiments may use other criteria including validation of link reliability to ensure long-term networking. An example of information that can be retained in the targeting table is shown in Figure 4.

0065 From the information in the targeting table, nodes can build a forwarding table or for the next jump with a list of destination MAC addresses, a type associated with each address, and the cost of the route for it. In this preferred embodiment, the type reflects the preference of the selection associated with the destination and can be one of five: source-directed, jump

<img file="RO125809A2_D0012.tif" />

- 2 Ο 0 9 - Ο 1 Ο 4 Ο - 2 7 -05- 2008

<img file="RO125809A2_D0013.tif" />

with jump, direct adjacency, route history, or local. Figure 5 provides an example of the types of routes that can be listed. In the present preferred embodiment of the hop-by-hop target destination, it is listed together with the next hop from the source node. in the case of a directional destination from the source, a series of jumps with the destination in the transmission table is explicitly mentioned below. Multiple entries for the same destination can be listed in order of preference, which can be determined by both the label type and the cost of the route. In this preferred embodiment, when attempting to reach Destination 4 in the example below, the node will first use one of the hop-by-hop entries that are kept in an attached list to increase the cost of the route. In other embodiments, the routing algorithm allows the routing information to be maintained in the source node to create an input to the source path for Destination 4, by structuring a subsequent set of paths to the destination address. In addition, in other embodiments, the node will use the previous route that was picked up by traversing traffic through certain points in time.

MAINTAINING NEIGHBORS

0066 In this case, the preferred upstream and downstream neighbors are constantly maintained by MLME warning signals or periodic directional maintenance messages precisely used to synchronize hours and ensure that nodes can still exchange packets with each other. This constant contact and feedback can be used by the L2 targeting layer for several purposes, which may include:

- Neighboring updates are communicated to downstream devices in time update signals

- nodes use MLME to detect if their downstream and upstream routes still exist.

0067 The upstream link characteristics of a node may change, for example, when:

- an upstream node disappears

- a new preferred upstream link is detected

- link quality changes (smooth over time)

0068 In the present preferred embodiment, these rules are applied to all upstream nodes on a route, respectively. When a occurs

<img file="RO125809A2_D0014.tif" />

0 9 - 0 1 0 4 0 -2 7 -05- 2000/4 τ 'adjustment, the node recalculates the costs for each of its output nodes. When the cost of a node on the uplink significantly changes the cost to one of the networks to which it is directed, it distributes this information in the next set of MLME warning signals to its downstream nodes.

0069 In this preferred example, a change in the network information is propagated with a "Neighbor List" message, with the protocol field set to 0x2 indicating that a partial list of changes is distributed. In one embodiment this may reflect the addition of new networks or changes in the cost of existing networks. When an upstream link disappears, causing a private network to be virtually out of reach, a “Neighbor List” message is sent with the protocol set 0x3 to indicate that the network has been removed from the list of nodes upstream of the network. .

0070 In this preferred example, PA access points are notified of changes in the network topology by periodic network registration messages that are transmitted exclusively to them. These messages can be transmitted by each node in the network of access points, and can contain a complete list of their upstream nodes and / or the costs of connections to each of them.

0071 In this preferred example, MLME maintains two straightforward averages that can be used by DLF to determine link costs for targeting purposes: a balanced RSSI value and a balanced success rate. The term "balanced" refers to the type of mediation performed on the data. In the present preferred example, the calculation of means uses the formula: balanced mean = A * mean + B * sample; B = (1 - A). This type of mediation does not require a large amount of memory for storage (as opposed to storing the last N samples) and also has a controllable amount of history ”. The term history refers to how much it affects the new current balanced average value. This can be controlled by A and B values: high A values ​​mean that the average has a longer history than lower A values. Other embodiments may use other averaging methods that are appropriate to the conditions that characterize the network.

0072 RSSI is an indicator of the strength of the received signal. This value can be measured on all received frames in a node. In some embodiments it has only a limited use for link quality calculations

<img file="RO125809A2_D0015.tif" />

^ -2009-01040-2 7 -05- 2008 because it may not provide a clear indication of the bit error rate on the link. Preferably, when any frame in a node is received, the RSSI of that frame is mediated in a balanced RSSI using the averaging formula.

0073 In this preferred example, the success rate criterion "info" is used as the best link quality measure and therefore for targeting decisions. Success rate "info" is a form of package success rate. The term "info" is used to refer to staff other than those who started communications. The first frame transmitted to a node directed at its jump sequence may give error due to interference or due to the occupancy of the receiver. The success rate of info, by including only those frames that the desired node listens to and not the frames from the beginning of communications, ensures a measure of the quality of the connection that does not vary strongly with the loading of the receiver. Success rate info is considered to be the best indicator of link quality.

REGISTRATION OF THE NODE WITH UPPER NEIGHBORS

0074 Each node can be explicitly registered with the upstream nodes that it intends to use in a network. This record means that the upstream node will now try to keep the time information about the node that wants the record up to date, and keep the entry in the downstream routing table. This ensures that traffic can flow not only to the exit but also back to the node.

0075 The node is registered with its upstream node by sending to it an upstream registration message ”. The upstream registration message "contains the type of device and a metric related to the health of the neighborhood. Neighborhood health metrics are used to calm downstream nodes when an upstream link becomes overloaded. Devices with a low neighborhood health metric (and therefore possible with low route diversity) are preferably selected over devices with high neighborhood health metrics.

0076 The format for the upstream registration message ”is specified in Figure 6. The message type indicates that it is an upstream registration. Neighborhood cost means neighborhood health metrics based on a combination of potential and active upstream node numbers.

ryiVfcTÎ 'ț' —1009-01040-- \

7 -05- 2008 Τ

0077 Potential upstream nodes either accept positively or negatively the upstream registration message "using the Accept upstream registration message". The “Neighborhood Health Metric” of a device is updated based on the value of this acceptance. Potential upstream nodes give less weight than accepted upstream nodes.

0078 The format for the Upstream Registration Accept message is shown in Figure 7. The type indicates that it is an Upstream Registration Accept message ”. "Seq Num" represents the sequence number transmitted by the applicant in the upstream registration message ". The response status code can be one of the following:

- OxO, Node successfully added

- 0x1, Error adding node

- 0x2, Node rejected due to high load

- 0x3, The node is already maintained

NODE REGISTRATION WITH PA ACCESS POINT

0079 A node registers itself with a PA access point by transmitting an individual PA registration message ”(AREG). The AREG message contains the list of addresses of the nodes in the PA network that the node uses as upstream nodes, and the cost of the link associated with each of these upstream nodes. It may also contain a list of other candidate networks (represented by the output nodes of these networks), and their costs.

0080 The format of the AREG message is shown in Fig. 8. The type is set to indicate that it is an AREG message. The M bit is set if there is more data to transmit. Seq Number is the sequence number of the recording message. The message number is used when the registration message is sent in several parts. Each AREG Neighbor describes an upstream node on the routes used by the node that wants to register.

0081 The format for the AREG Neighbor description in the AREG message is shown in Figure 9. The MAC address corresponds to the upstream node or a network exit point that the node that wants to record informs the PA access point. The cost is recorded either at the upstream node or at the network exit point that has been described. The E bit is the Network Output Node bit. It is determined whether the description of the neighbors is an outgoing network node and not an upstream neighbor.

<img file="RO125809A2_D0016.tif" />

2009-2009-01040-2 7 Ό5- 2008

0082 When a node is successfully registered at the PA access point, the PA will place the node in its targeting table, and ensure that it keeps the node status up to date. The node transmits periodic recording messages to the PA (about every 12 hours). The PA will update its targeting table when it sees the next registration message to the PA. If the PA loses three consecutive log messages, the node will be removed from the PA's targeting table, and will have to re-log itself.

0083 In response to a successful first record, PA will preferably send a set of TLVs containing any network configuration information. This list may include, but is not limited to, PA's global addressable IPv6 prefix, PA's MAC address, DNS server address, network transmission times, and any other variables related to L2 / L3 routing.

0084 If a PA becomes overloaded with too many nodes it can start withdrawing nodes that have other candidate networks. It can be evaluated by looking at different networks reported in AREG messages, and can remove candidates! less reliable network.

0085 The preferred process here regarding the output of a node can be summarized as follows using Figures 10 and 11. Figure 10 shows a network deployment with PA 1021 and PA 1022 providing the output to Network 1 1010. Relays R1 1031, R2 1032 and R3 1033 and Access points PA1 and PA2 are considered to have already been established. M1 1041 is the first end node whose networking process is described below. Tables 2a and 2b list the link costs for all links that are detected and established.

Table 2a

<td></td><td>Network 1 1010</td><td>PA (1021)</td><td>PA (1022)</td><td>R (1031)</td><td>R (1032)</td><td>R (1033)</td><td>M (1041)</td>

<td>Network 1 1010</td><td></td><td> 5</td><td> 10</td><td></td><td></td><td></td><td></td>

<td>PA (1021)</td><td> 5</td><td></td><td></td><td> 20</td><td> 40</td><td></td><td></td>

<td>PA (1022)</td><td> 10</td><td></td><td></td><td></td><td></td><td> 30</td><td></td>

<td>R (1031)</td><td></td><td> 20</td><td></td><td></td><td> 10</td><td></td><td></td>

<td>R (1032)</td><td></td><td> 40</td><td></td><td> 10</td><td></td><td> 10</td><td></td>

<td>R (1033)</td><td></td><td></td><td> 30</td><td></td><td> 10</td><td></td><td> 15</td>

<td>M (1041)</td><td></td><td></td><td></td><td></td><td> 30</td><td> 15</td><td></td>

Table 2b

<td>Link</td><td>Connection cost</td>

<td>PA (1021) &lt;-&gt; Network (1010)</td><td> 5</td>

<img file="RO125809A2_D0017.tif" />

Ă - 2 OO 9 - O 1 O 4 O - 2 7 -05 “2008

<td>PA (1022) &lt;-&gt; Network (1010)</td><td> 10</td>

<td>R (1031) &lt;-&gt; PA (1021)</td><td> 20</td>

<td>R (1031) &lt;-&gt; R (1032)</td><td> 10</td>

<td>PA (1021) &lt;-&gt; R (1032)</td><td> 40</td>

<td>R (1032) &lt;-&gt; R (1033)</td><td> 10</td>

<td>PA (1022) &lt;-&gt; R (1033)</td><td> 30</td>

0086 When M 1 (1041) appears, the MLME neighbor scans for the adjacency of R2 (1032) and R3 (1033) in the first stage. During the adjacency setting, R2 (1032) and R3 (1033) send Network Announcement messages. Specifically, in the second step, R2 (1032) sends the message Network Announcement announcing an exit route to Network 1 (1010) via PA1 (1021). The message contains the MAC address of PA1 (1021), the class or subnet mask of the network address (IPv6 or IPv4 address), the cost of adjacency to M1 (1041) as seen by R1 (1031), the maximum number of hops it makes it reach the output node (2), and the lowest cost of output from the network (35). Using a short notation, we can specify [R2 (1032) send NADV (30, MAC_ADDRESS (PA1 (1021)), 2, 35)]. It should be noted that R2 (1032) does not announce the direct route it has to PA1 (1021) because the cost of the route is 45 which is higher than 35. Next, in the third stage, R3 (1033) sends the message NADV in response to the announcement of an exit route via PA2 (1022). in short notation we can write [R3 (1033) send NADV (15, MAC_ADDRESS (PA2 (1022)), 1.40)]. This is followed in the fourth step by the calculation by M 1 (1041) of the total cost of the networks by adding the cost of the route and the cost of the connection and creating an order list with the following upstream jumps to be used. Upstream node R3 (1033) has a total cost of 55 while upstream node R2 (1032) has a total cost of 65. R3 (1033) is therefore preferred and placed above R2 (1032) in the list, as is indicated in Tables 2a and 2b above. In the fifth step, M1 (1041) attempts to register with R3 (1033) by transmitting an upstream recording message to R3 (1033), reporting no other possible node for this output. The sixth step occurs when R3 (1033) sends an Upstream Registration Accept message to M1 (1041) accepting M1 (1041). M1 (1041) is accepted because it has no other possible node for this output. This is followed by the seventh step in which M1 (1041) attempts to register with R2 (1032) by transmitting an upstream registration message to R2 (1032), reporting no other possible node for this output. then follows the

<img file="RO125809A2_D0018.tif" />

^ -2009-01040-2 7 -05- 2008 the eighth step in which R2 (1032) sends an Accept upstream registration message to M1 (1041), accepting M1 (1041). M1 (1041) is accepted because it has no other possible node for this output. In the ninth step, M1 (1041) attempts to register with PA2 (1022) by transmitting a PA registration message. It reports R3 (1033) as an upstream node that it wants to use. The tenth stage follows in which PA2 (1022) accepts M1 (1041) by sending a PA Registration Accept Message and passes M1 (1041) to the network configuration (mainly IPv6 address, DNS address, PA2 network prefix (1022). PA2 (1022) can now direct M 1 (1041) The next or eleventh step is where M1 (1041) tries to register with PA1 (1021) by sending a PA Registration Message. It reports R2 (1032) as an upstream node that it wants to use. In the twelfth step, PA1 (1021) accepts M 1 (1041) by sending the PA Registration Accept Message and passes M 1 (1041) to the network configuration (mainly IPv6 address, DNS address, PA1 network prefix (1021). PA1 (1021) can now target M1 (1041) as well. Next, in the thirteenth step, M1 (1041) sends the DNS Dynamic Update message (RFC 2136) to the Network 1 DNS server with the IPv6 address via PA2 (1022). The last step is when M 1 (1041) sends the DNS Dynamic Update message (RFC 2136) to the Network 1 DNS server with its second IPv6 address via PA1 (1021).

0087 The method of updating routes when a network change occurs is illustrated using an example of changing the cost of the network connection to 1000. The modified network is shown in Figure 12 with the only difference being the black line indicating that the cost of the route from R1 ( 1031) to PA1 (1021) was changed from 20 to 5.

0088 First, R1 (1031) updates R2 (1032) via MLME because R2 (1032) uses R1 (1031) and an upstream flow to PA2 (1021). R2 (1032) recalculates its cost to PA2 (1021). The cost is now 15. R2 (1032) updates M 1 (1041) via MLME on the new cost of the route which is 20. M 1 (1041) then recalculates the total cost of the networks by adding the cost of the route and the cost of the connection and creates a order list for the next jumps to be used. Upstream node R3 (1033) has a total cost of 55 while upstream node R2 (1032) has a total cost of 50. R2 (1032) is therefore preferred now and placed above R3 (1033) in the list. Reordered list of information

ÎT T? ROra μ =. ·_λ 22 l LC A ::

(Κ- 2 Ο Ο 9 - Ο 1 0 4 Ο - 2 7 -05- 2008

<img file="RO125809A2_D0019.tif" />

The targeting is shown in Figure 13. Finally, R1 (1031), R2 (1032) and M1 (1041) send the updated information to both PA1 (1021) and PA2 (1022) via their next periodic PA recording message.

0089 A small-scale RF network is illustrated in Figure 14 and will be used below to illustrate the preferred embodiment of how route determination and propagation operations work in a common scenario where Access Points (1520 series) ) and the relays (1530 series) are brought first and then the end points (1540 series) are stopped. As shown in Figure 15, the costs of the links are mapped between the nodes that establish communications with each other on the RF layer. Figure 16 is used in conjunction with Figure 17 to illustrate the preferred embodiment in which a complete sequence of changes takes place between nodes to establish routes or routes for packet delivery upstream in the announced network or downstream of the announced WAN network in the RF network. .

0090 It should be noted that in Stage 4 of Figure 17, R2 (1532) never announces the route with 3 jumps for Neti through R1 (1531) back to R1 (1531). This method of not announcing routing information back along an already traversed route is called the "separate horizon" method and prevents routing loops.

0091 In a preferred embodiment the targeting mechanism is adapted to be compatible with, and uses the advantage of, the Frequency Jump Spectrum (FHSS) access scheme used in the wireless network according to the preferred embodiment, and increases some of the the inherent operational characteristics of the FHSS. Regular time updates are required in the frequency hopping method to correlate the different time lags of the different nodes that must remain correlated with the synchronously changed packets. The routing protocol keeps packet overcrowding to a minimum by using time breaks on frequency hikes in the form of "on" messages to transmit link status information. Alternatively, time updates may also be carried on any of the data packets that are transmitted. Unless otherwise noted, maintenance messages are messages sent to update information, and may be transmitted on a regular basis. The message "I work", which can also be used to update targeting information,

<img file="RO125809A2_D0020.tif" />

_⁇-2 009-01040-2 7 -05- 2008 are usually sent to announce, for example, the time when the node is initially powered or when it is introduced into a network.

0092 In such an embodiment there may be a radio communication in the conventional sense in the network routing protocol using the FHSS scheme. The nodes are directed directly one by one for the packet exchange. The targeting protocol according to this invention discloses the use of an abstract radio communication relationship in which the frame broadcast on the link layer uses an 8-bit MAC address all in hex) being transmitted on each slot or channel starting from a randomly selected slot and with a predetermined waiting time between each transmission.

0093 In the preferred embodiment of the present invention, the targeting protocol described herein uses FHSS-based wireless signaling capabilities where a warning signal is a periodic transmission over a specific known frequency hopping sequence. which can be recognized by all neighbors. The communicated warning signal that can be received by multiple neighbors is much more effective than sending a targeting update to each neighbor. A warning signal is also a shorter transmission with less overcrowding than a routing update because there are no acceptance messages and therefore fewer packets re-transmitted during an error.

0094 In the present preferred embodiment, the routing protocol described below is intended to exploit the collective computing resources of devices (nodes) in the network instead of relying on a single gateway to the base of the wireless network to calculate and distribute routes to all nodes. . Endpoints select a preferred set with the ordered multiplication of upstream nodes to be used as the next jumps to the WAN network through multiple Access Points (also called gateways) based on associated route exit announcements of the route for each route and each jump. During an error of the main route upstream or to the Access Point, the return to the secondary routes and / or Access Points in the endpoint database is immediate without waiting for a routing algorithm to re-converge because the routes are already pre-close.

0095 In a preferred embodiment, the routing protocol allows nodes to migrate from one WAN to another WAN. When a node

<img file="RO125809A2_D0021.tif" />

⁽'· “2 009-01040-2 7 -05- 2008 upstream announces its known routes to a downstream node, it sends a set of outbound routes to all available WANs. The routing table for each node lists the following hops through multiple Access Points for all available WANs, enabling fast migration if the main or established network becomes unavailable.

0096 In a preferred embodiment, each node registers itself with all the upstream nodes that it intends to use. The upstream node can now store an entry in the downstream routing table for that node. The traffic destined for an endpoint can now be directional, first and foremost jump-to-jump where only the next hop from the source or any next node is added to the packet message title. Of course, the destination address is usually included. Routing from the source where the entire order list of the nodes through which the packet must pass is explicitly mentioned by the access gate in the message title is also for the purpose of this algorithm. The targeting protocol disclosed in this invention allows each node to have several subsequent jumps in its knowledge base and gives it the ability to choose from which to pass forward step by step. By doing so, packets can bypass problematic connections without transmission and retransmission errors, and it is much more advantageous in a wireless network where RF connections tend to be transient in nature. In addition, the present invention avoids open-ended routing loops in which source targeting methods are forced in the event of faulty connections.

0097 The example routing protocol described in this framework provides "historical" routes that represent alternate routes gathered by a node in the traffic passing through it. "Historic" routes are removed from the node routing table when the allocated memory is full and expires after a specified period of time. These routes, which are in addition to the announced routes, serve to expand the list of redundant links available for a node to ensure the successful transmission of a packet.

0098 The example routing protocol described in this case allows you to sort and preferentially sort the next available hops for a node to route packets to a destination on an IPv6 network. The logical sorting program may vary in different implementations. In this embodiment, the logical sort program uses both the origin of the targeting information and

<img file="RO125809A2_D0022.tif" />

-2009-01040-2 7 -05- 2008 the cost of the route to the destination and the cost of the connection to the desired jump. For example, the next hop is picked up from the "historical" route that was collected from past traffic using an inconsistent route and receives a lower level of preference than the next hop marked as being used frequently in the "hop by hop" traffic. Several next jumps in the "historical" category or the "jump by jump" category will be sorted in an orderly list according to the cost of the route. There are other options available for route selection, and these options are described in detail in this invention.

0099 The example targeting protocol described here allows an extension of the sorting logic program to prefer the most recently used link or the link that has passed the most traffic or a configurable window (and therefore called "strong"). , thus allowing greater control of traffic flow. To bypass overloaded links, a current traffic load size on each available link to a possible next hop is also considered when a node selects to use the next best hop.

0100 With the node allowed to register on multiple networks (resulting in the node obtaining multiple IP addresses) and the DNS server capable of sorting these IP addresses according to the configuration policies for resolving the node's hostname, a method is now provided for traffic entry control in the RF LAN.

LOADING BALANCING MECHANISM AND ROBUST STEERING FOR DIRECTION

0101 Figure 18 shows a particular network deployment scenario that amplifies the routing algorithm described in the application to ensure load balancing mechanisms and robust deployment.

0102 The targeting algorithm described herein is particularly adaptable to deployments such as the one shown in Figure 18. The notion of multi-point recording and the notion of configurable link costs can be amplified to allow (near) removal snapshots of multilayer errors. For example, if PA-1, an Access Point device (1810) fails, then the next available point PA-2 can be selected, essentially immediately. In addition, if PA-2 fails, packets can be supported on routes via PA-3, and so on.

<img file="RO125809A2_D0023.tif" />

ί ^ -2009-01040-2 7 -05- 2008

<img file="RO125809A2_D0024.tif" />

Consolidating all PA access points in a more central location encourages the network to announce routes through all PA access points to endpoint nodes, resulting in a record of these endpoint nodes with all PAs instead of one or two endpoints. PA access as in the scenario where PA access points are scattered. These lead to different PAs in the central location to look very similar in terms of link cost, thus ensuring that all of these are part of the node targeting table (in the preferred embodiment) and thus provide a robust error avoidance mechanism. . Relays (1830) can be used to extend the reach of these announcements for the best ratio between PA and endpoint node. Moreover, traffic management policies at PA access points can be used to regulate the connection or cost of routes to Access Points in order to achieve a load balancing or to allow the conservation of resources for certain types of traffic.

0103 The invention has been described with reference to specific embodiments. However, it will be apparent to those skilled in the art that it is possible to implement the invention in specific forms other than those of the preferred embodiments described above. This can be done without straying from the spirit of the invention.

0104 Thus, the preferred embodiment is illustrative only and should not be considered restrictive in any way. The object of the invention is set out in the dependent claims and not in the foregoing description, and all embodiments and equivalent means within the scope of the claims are intended to be incorporated therein.

<img file="RO125809A2_D0025.tif" />