Route selection in wireless networks

Path selection in wireless network

The present invention relates to wireless networks, and more specifically relates to wireless mesh networks. More specifically, the present invention relates to the processing of route request messages in an on-demand routing protocol.

On-demand routing protocols (for example, the ad hoc on-demand distance vector (AODV) routing protocol defined by the MANET working group in the IETF) use a path request and path reply mechanism to communicate in wireless mesh networks/ad hoc networks Establish a path between two nodes. When a source node wants to send a data packet/frame to a destination node, if the source node does not have and needs a valid path to the destination node, the source node spreads a path request (RREQ) message Discover the path to the destination in the entire network. A reverse path back to the source node is generated when the node in the network receives and forwards the RREQ. When a node receives an RREQ, the receiving node responds to the request by generating a path reply (RREP) message in any of the following situations: (1) the receiving node itself is the destination, or (2) the receiving node There is a valid path to the destination and the "Destination Only" ('D') flag is not set in RREQ. The RREP is forwarded to the source node in a single-point propagation via the established reverse path, and a forward path to the destination in the intermediate node and finally in the source node is thus generated. If the established paths are not used within the service life of a given path, the paths expire.

In AODV, the "destination only" flag of the RREQ message is set by the source node, and it is not changed by the intermediate node. If the source node sets the "destination only" flag in the RREQ, even if the intermediate/receiving node has a valid path to the destination node, the intermediate node does not respond to the RREQ with a RREP message. It forwards/re-spreads RREQ to its neighbors. Only the destination node responds to this RREQ. In this mode of operation, although the latest and best path between the source node and the destination node is finally found in the process, the path discovery waiting time may be longer. Low latency is very important for real-time applications such as voice and video communications.

If the source node does not set the "destination only" flag, any intermediate node with a valid path to the destination node responds to the RREQ with a RREP message. The RREP message is sent back to the source node in a unicast, and a forward path to the destination node is established. If the "RREP" ('G') flag is set in the RREQ, the intermediate node will also broadcast a single point of a free RREP to the destination node, so that the destination node learns the path to the source node. However, in AODV, if an intermediate node does not generate an RREP (because the intermediate node has a valid path to the destination node), the intermediate node discards the RREQ. With this method, the source node can find a path to the destination node more quickly, because the source node does not have to wait for the destination node to reply. However, because the path cached in the intermediate node may not be the best path to the destination node, the best end-to-end path may not be found. The metric may have changed due to the dynamics of the wireless network, making the cache path less desirable. That is, due to changes in network topology, routing metrics, etc., it is possible that the cached path in the intermediate node may become worse or other paths with a better end-to-end metric may become useful, thereby making other The path is more desirable.

The problem solved by the present invention is how to use RREQ and RREP mechanisms to quickly find the best path between a source node and one or more destination nodes.

The present invention discloses a method and system for processing/forwarding route request (RREQ) messages and generating route reply (RREP) messages using an on-demand routing protocol (AODV is an example), so that the best route can be found It will not cause significant path discovery delay/waiting time in the wireless mesh network/specialized network. Specifically, when a source node wants to find a path to a destination node, the source node broadcasts an RREQ message in the network, where the destination node is specified in the destination list and the metric field is initialized to 0 . The RREQ message contains a new flag "Intermediate Reply (IR)" for each destination node. When the source node initiates RREQ dissemination to find a path to the destination node(s), the source node sets a flag corresponding to the destination node in the RREQ. During the RREQ dissemination, the first intermediate node with a valid path to the destination node responds to the RREQ with a RREP message. The RREP message is sent to the source node by single-point propagation and thereby a temporary forward path to the destination is quickly established. Therefore, the source node can use this temporary forward path to send data packets/frames with a low path discovery delay/wait time. The first intermediate node resets/clears the "IR" flag in the RREQ message, and forwards the updated RREQ message downstream to the destination node. Because the "IR" in the RREQ has been reset, even if the downstream intermediate nodes have a valid path to the destination node(s), the downstream intermediate nodes will not respond to the RREQ but only propagate the RREQ. RREQ finally reaches the destination node(s). The destination node(s) can select the best path/route based on end-to-end metrics and send a new RREP back to the source node to establish the best path between the source node and the destination node. If the optimal route is different from the temporary forward route established via the RREP from the intermediate node, once the optimal route has been established, the source node switches to the optimal route.

A system and method for discovering a path between a source node and a destination node in a wireless network are described. The method includes: setting an intermediate reply flag of a path request message by the source node; The request message is spread in the wireless network; and a first intermediate node responds to the path request message with a path reply message, and the first intermediate node has an effective path to the destination node. The system and method then update the path request message and re-spread the path request message in the wireless network. The response action thereby establishes a temporary forward path between the source node and the destination node of the wireless network. A system and method for discovering a best path are also described. In this case, the path reply message becomes a first path reply message. The system and method for discovering an optimal path include: the destination node selects the optimal path between itself and the source node based on the cumulative metric received in the path request message received by the destination node; and generating a Another route reply message and single-point propagation of the other route reply message to the source node. If the temporary forward path is the best path, the other path reply message serves as a confirmation, and if the temporary forward path is not the best path, the other path reply message is used when the source node receives the The best route will be established after the other route responds to the message.

When a source node/network point wants to send a data packet/frame to a destination node, it checks its routing table to obtain a path. If there is a valid path, it transmits the packets/frames to the next hop specified for the destination node in the routing table. If there is no valid path, the source node initiates path discovery by spreading a path request (RREQ) message throughout the wireless mesh network/specialized network. The data packets/frames may originate from the node or, if the node is a wireless access point, from a station associated with the node. It is possible that a source node needs to discover paths/routes to multiple destination nodes. The source node can distribute an RREQ for each destination, or in order to reduce routing additional items, a single RREQ message with a list of multiple destination node addresses embedded in it can be disseminated in the network.

Figure 1 shows an exemplary RREQ message format, other formats are also possible. The RREQ message contains (for example) the source/source node address, the serial number of the start node, the destination node address and the destination serial number (or the number of destinations and the list of destination addresses and serial numbers), RREQ ID, message ID, message length, time-to-live (TTL), hop count, routing metrics, flags and other information. In addition to the flags "Destination Only" ('D') and "Free RREP" ('G'), a new flag is included in the RREQ message, which is referred to as the "Intermediate Reply" (IR) flag in this article Mark. The'D' and'G' flags are carried as the tradition of AODV. These two flags are not set/used by the source node and are ignored by the intermediate node and the destination node. An alternative embodiment is that the RREQ message does not contain the'D' and'G' flags at all. If the RREQ message carries a list of destination addresses, the RREQ message includes a plurality of "intermediate reply" flags, and each flag corresponds to a destination address. When the source node wants to find a path from one to one or more destination addresses, it sets an "intermediate reply" (IR) flag corresponding to the destination address(s). It should be noted that the destination node address(s) can be an Internet Protocol (IP) address or a layer 2 (Media Access Control MAC) address. In order to adapt to changes in network conditions and to maintain the best measurement path between nodes, each active source node can broadcast a periodic RREQ message (remaining RREQ) to the wireless network as needed for the destination address it communicates with. Mesh network/special network. The "IR" flag is not set in the holding RREQ. The intermediate node and the destination node follow the same rules as those used to process a non-retained RREQ in the discovery phase to process the retained RREQ.

Therefore, it can be seen that distributing non-retaining RREQ messages and maintaining RREQ messages in a wireless mesh network/specialized network will result in the creation/update of an intermediate node and a destination node to the reverse of the originating node (source node) of RREQ path. Delivery of non-holding RREQ messages also triggers RREP messages from the destination node and possible intermediate nodes. The RREQ message to keep the distribution triggers the RREP message from the destination node.

When an intermediate node or destination node receives an RREQ message, it generates a reverse path to the source node, or when the RREQ message passes through a reverse path to the source node to provide a better measure of the path/route Next, update its current reverse path. It should be noted that each node can receive multiple copies of the same RREQ message (initiated by the same source node and have the same RREQ ID), and each RREQ message traverses a different route from the source node to the receiving/intermediate/destination node. If a reverse path is generated or modified, or this is the "first copy" of an RREQ message, the RREQ message is forwarded (re-spread). "The first copy" is used in this text to mean that this copy of the RREQ message is received by the receiving/intermediate/destination node or viewed by its starting node address and RREQ The first copy or first copy of this specific RREQ message identified by the ID. When an intermediate node forwards an RREQ message, the metric field in the RREQ message is updated to reflect the cumulative metric of the path from the intermediate node to the source node of the RREQ. In addition, if the "IR" flag is set for a destination node in the destination node list of the received RREQ message, and the intermediate node has a valid path to the destination node, the intermediate node replies to RREP with a path The messages should be RREQ messages back and forth. The route reply message is sent to the source node by single-point propagation and a forward route to the destination node is established. Then the source node can immediately use this path to send the data frame/packet to the destination node. If the intermediate node responds to the RREQ message with a RREP message to a destination node in the RREQ destination node list, it resets/clears the "IR" flag used for the destination node in the RREQ message, and then retransmits it. The updated RREQ message is broadcast on the network. The reason for resetting the "IR" flag after sending a RREP message is to suppress any RREP messages from downstream intermediate nodes. Only the first intermediate node with a valid path to the destination node along the path traversed by the spread of the RREQ message responds with a RREP message for the destination node. If the "IR" flag for a destination is reset/cleared in the RREQ message, even if an intermediate node has a valid path to the destination node, it will not respond with an RREP message.

After generating/establishing or updating a reverse path to the source node, the destination node sends a unicast RREP message back to the source node. After receiving the RREP message, the intermediate node generates a forward path to the destination node(s), and forwards the RREP message to the source node. When the source node receives the RREP message, it generates a forward path to the destination node. If the destination node receives another RREQ message with a better metric, the destination node updates its path to the source node to a new path and also sends a new RREP message back to the source node along the updated path. The new RREP message establishes a better (updated) forward path from the source node to the destination node in the intermediate node and finally in the source node. Once this better forward path is established, the source node uses it to send data. Finally, a two-way, best end-to-end measurement path is established between the source node and the destination node. Using this method, the source node can quickly obtain a path to the destination node, the path is established by the RREP message, and the RREP message is replied by the intermediate node using an effective path to the destination node. If the path is not the best end-to-end measurement path between the source node and the destination node, then the path is updated to the best path thereafter.

Referring now to Figure 2, it depicts the routing request (RREQ) message being broadcast in the wireless mesh network/special network, and the intermediate node B (which has a valid path to the destination node E) responds back and forth with a RREP message RREQ message. Consider an example where the source node A tries to find a path to the destination node E. The source node A broadcasts the route request (RREQ) message to the "IR" flag set in the wireless mesh network/special network. Assume that the intermediate node B already has a valid path BCDE to the destination node E. When the intermediate node B receives the RREQ, it generates a reverse path to the source node, and the source node from which the intermediate node B receives the RREQ serves as the next hop (source node A) of the reverse path/route. The intermediate node B responds to the RREQ with a single-point propagation RREP, because it has a valid path to the destination E and the "IR" flag is set in the RREQ. RREP establishes a forward path in the source node A to the destination node E. Once the source node A uses the RREP from the intermediate node B to generate a path/route to the destination node E, the source node A can start to send data packets/frames to the destination node E via the path ABCDE. The intermediate node B resets the "IR" flag in the RREQ message and further forwards it. The reason for resetting the "IR" flag is to limit the response to the RREQ dissemination to the first intermediate node that only has a valid path to the destination node. Other downstream intermediate nodes (for example, C and D) do not need to respond to this RREQ with a RREP because the "IR" flag is not set. Assume that the intermediate nodes F, G, and H do not have a valid path to the destination node E. When the intermediate nodes F, G, and H receive the disseminated RREQ message, it generates a reverse path to the source node A, where each of the intermediate nodes F, G, and H receives the RREQ from the node from which the RREQ is received as the reverse path Next hop. Each of the intermediate nodes F, G, and H then further forwards the RREQ message.

In this example, the destination node E receives two copies of this RREQ, and each copy traverses a different route: ABCDE and AFGHE. Assuming that the two RREQs arrive at the destination node E in the following order: ABCDE and then AFGHE, once the destination node E receives the RREQ along the path/route ABCDE, the destination node E first generates a path through the intermediate node D to the source node A. At this time, the reverse path to the source node A has been established in the intermediate nodes B, C, and D. The destination node E sends a RREP along the path EDCBA. This RREP only refreshes the path ABCDE. If there are any other destination nodes in the RREQ destination list (for example, node 1), the destination node E removes itself from the destination list, and then further forwards the RREQ (for example, to node 1). If there are no other destination nodes in the RREQ destination list, the RREQ is not forwarded.

Now refer to Figure 3, which depicts a wireless area mesh network, which shows that after receiving the RREQ via ABCDE, the destination node E responds with a RREP(1), and sends a new RREP( 2) To establish a better forward path/route. When the destination node E receives the RREQ arriving along AFGHE, the destination node E determines that the RREQ arrived along a route with a better metric than the temporary forward path/route ABCDE. Therefore, the destination node E modifies/updates the hop from the intermediate node D to the intermediate node H, and updates the metric. The destination node E then sends a unicast RREP back to the source node A via the intermediate node H, and updates and forwards the RREQ if there are one or more other destination nodes in the RREQ destination list. RREP establishes a path to source node A via intermediate nodes H, G, and F. When the source node A receives this RREP, it modifies/updates the next hop for the destination node E from the intermediate node B to the intermediate node F. The path to the destination node E is changed to AFGHE.

Now refer to FIG. 4, which is a flowchart of processing an RREQ message. When a node receives an RREQ message, if necessary, it first generates/establishes or updates a reverse path to the previous hop from which the node receives the RREQ message at 410. Then the intermediate/receiving node can generate or update the reverse path to the start node of the RREQ as follows. If a reverse path to the starting node of the RREQ message at 415 and 420 does not exist in the routing table or is invalid, then the reverse path is generated or updated. The next hop in the routing table of the reverse path of the RREQ start node becomes the previous hop (the node from which the RREQ message is received). If there is a valid reverse path to the starting node of the RREQ, the source sequence number in the RREQ message is compared with the sequence number of the path entry in the routing table of the reverse path at 425. If the sequence number in the RREQ message is older, it will be discarded at 445 and no further processing will be performed. On the other hand, if the new metric at 430 is better than the metric of the current path to the start node in the routing table, then the current reverse path to the start node is modified. The new metric is defined as the metric in the RREQ message plus the link metric between the node through which the RREQ message is received and itself. If the new measurement is not better than the measurement of the current reverse path in the routing table entry, but the source sequence number in RREQ at 435 is greater than the sequence number in the reverse path routing table (new), then in the middle of 450 The node checks whether the mesh network supports the optional processing functions of hysteresis and best candidate path caching. If these optional processing functions are not supported, the reverse path to the RREQ starting node is updated at 455. When a reverse path is generated or modified, the sequence number in the routing table of the reverse path is set as the source sequence number in the RREQ message, the next hop becomes the node from which the RREQ message is received, and the metric is set as the new metric. And set the hop count to be one greater than the hop count in the RREQ message.

If a reverse path to the source node is generated or modified at 420, or the RREQ message at 440 is the first copy of a new RREQ message (the RREQ ID has not been seen by the source node before), then execute the instructions in this article at 475 Describe the RREQ forwarding and RREP generation routines. There may be other situations in which a node executes the RREQ forwarding and RREP generation routines described herein. For example, in a certain best candidate path cache method, the RREQ message can be stored in a waiting queue with a timer during the candidate path cache period. When the waiting queue timer expires, the RREQ forwarding and RREP generation routines are executed.

The source node can send a periodic hold RREQ message to refresh its effective forward path and reverse path. Each time the source node sends a keep RREQ message is called a path refresh cycle. It is possible that a node that already has the best reverse path to the source node receives an RREQ message with a newer sequence number but a poor metric path to the source node before receiving the RREQ message via the current best metric path. In addition, during the dissemination period, the copy of the RREQ message propagated along the current best metric path may be lost. Such events can cause the path to drift. In order to reduce path flutter and select the best path during each path refresh cycle, a certain type of hysteresis and best candidate path caching mechanism can be used. If it is determined that a mesh network implements the hysteresis and best candidate path caching option, if the source sequence number in the RREQ message at 460 is larger (new) than the sequence number in the routing table entry by a value greater than a threshold value, Then an intermediate node updates the routing table and modifies the reverse path. Otherwise, the reverse path can be cached and stored at 465 as a potential candidate alternative path.

If the node subsequently learns that the current reverse path has been degraded and becomes worse than the candidate reverse path, it can change to the candidate path learned earlier in the same refresh cycle. The present invention describes a method and system for forwarding a RREQ message and generating a RREP message to find the best path without causing a large path discovery delay/wait time in a wireless mesh network. The method of the present invention can work with or independently of hysteresis and best candidate/alternative path caching.

Referring now to FIG. 5, which is a flowchart depicting the RREQ forwarding and RREP generation method of the present invention, at 505 a node determines whether it is a destination node, that is, one or more addresses of the node (self_addr) Whether it matches the requested destination address rreq.dest in the destination list of the RREQ message. It should be noted that a node itself can have multiple addresses or it can be a proxy server for other nodes. For example, a node may be an access point and generate/manage routing information on behalf of the old-style stations associated with it (the proxy servers of those stations). The functionality in this case is similar to the case when a node has multiple addresses. The destination address of the associated station can be regarded as the alias address of the access point. If one or more addresses specified in the destination list of the RREQ message belong to a node or one of the nodes uses the node as a proxy server, the node is a destination node. When a node receives an RREQ message in which the destination node is a node proxied by the node, it should process the RREQ message as if the destination node address is its own address. In addition, a node can be the destination node of one of the requested addresses in the destination list of the RREQ message, but is an intermediate node of the other requested address in the destination list of the RREQ message.

If one or more addresses of the node match the requested destination address in the destination list of the RREQ message, the node generates a unicast RREP message for these matched destination addresses at 510 and will It is sent to the start node of the RREQ message. A destination node removes its own/proxy server address from the RREQ message destination list at 515. Thereafter, if there is no remaining requested address in the destination list of the RREQ message at 520, the RREQ message is discarded at 525. If the node is not the destination node (505) of any requested address in the destination list of the RREQ message or there is a destination address other than the address of the node in the destination list of the RREQ message, also That is, if the node is an intermediate node of one or more addresses in the destination list of the RREQ message, the node checks the remaining addresses in the destination list of the RREQ message as follows. Assume that rreq.dest[i] represents the (i+1)th address in the destination list of the RREQ message. The node initializes an index (for example, i) at 545 and checks rreq.dest[i] (that is, the first address in the destination list of the RREQ message) at 550 to determine whether there is an index from rreq.dest [i] represents the effective forward path of the destination node. If an intermediate node has a valid path to the destination, the path to the destination node is valid (555), the serial number is at least as large as the serial number indicated in the original RREQ message (560), and the "intermediate reply (IR) )" flag (570), the intermediate node generates a RREP message for the requested destination address at 575 and sends the generated RREP message to the start node of the RREQ message in a single-point propagation along the current reverse path. At 580, the "IR" flag used for the requested destination in the RREQ message is reset. The node increments the exponent (e.g., increments by 1) and checks at 590 whether there are any additional addresses in the destination list of the RREQ message. If there are any additional addresses in the destination list of the RREQ message, repeat the above loop at 550. That is, if a RREP message needs to be sent for the next requested destination, the loop is repeated. Repeat this loop until all addresses in the destination list of the RREQ message have been checked.

At 530, the original incoming RREQ message is checked to determine whether the time-to-live (TTL) value is greater than one. If the TTL value is greater than 1, the information in the original RREQ message is updated at 535, including reducing the TTL value in the outgoing RREQ message (for example, by 1). At 535, the source number, metric, and hop count are also set as the corresponding information in the updated path entry of the source node. At 540, the updated RREQ message is forwarded.

Note that a destination node can own/agent one or more addresses and an intermediate node can have valid paths to one or more destination addresses. An RREQ message can carry one or more destination addresses in its destination address list. A processing/intermediate/destination node can meet the above conditions and send a RREP message to multiple requested addresses in the destination list of the RREQ message. If a node sends a RREP message for multiple destinations, it can send multiple RREP messages (one RREP message is for one destination), or it can send a single with multiple destination addresses in the address list Gather RREP messages.

FIG. 6 is a block diagram illustrating the details of the node 600 of the present invention. The node includes a link quality and load measurement module 605, a route measurement calculation module 610, a path selection module 615, and a communication module 620. The link quality and load measurement module 605 measures the quality and load of the link/channel to each of its neighbors. It provides the measurement result to the routing metric calculation module 610 so that the routing metric calculation module 610 can determine the link cost/metric to each of its neighbors. Note that a node can have multiple neighbors, multiple radio interfaces, and multiple physical/logical channels/links. All of them need to be measured. The routing metric calculation module 610 of each node uses the measurement performed by the link quality and load measurement module and other information to calculate the routing metric for each node it communicates with. Periodically update the routing metric. The path selection module 615 determines/selects a path/route for forwarding/transmitting data to a destination node based on the calculated routing metric. The path selection module 615 exchanges routing control messages and data with other nodes in the mesh network via the communication module 620. It should be noted that a node may have one or more radio communication interfaces and other communication interfaces. It should be understood that the path selection module may actually be composed of several smaller units or be combined with other modules described herein. It should be further understood that the process described herein (especially with reference to the description of FIGS. 3 and 4) can be software, hardware, firmware, or any combination thereof executed in the path selection module or executed by the path selection module .

It should be understood that, for example, the present invention can be implemented in various forms of hardware, software, firmware, dedicated processors, or a combination thereof in a mobile terminal, an access point, or a cellular network. Preferably, the present invention is implemented as a combination of hardware and software. In addition, the software is preferably implemented as an application program that can be clearly embodied on a program storage device. The application can be uploaded to and executed by a machine with any suitable architecture. Preferably, the machine is implemented on a computer platform with hardware (such as one or more central processing units (CPU), a random access memory (RAM), and input/output (I/O) interface) . The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein can be part of the microinstruction code or part of the application program (or a combination thereof), which is executed by the operating system. In addition, various other peripheral devices can be connected to the computer platform, such as an additional data storage device and a printing device.

It should be further understood that because some of the system components and method steps depicted in the accompanying drawings are preferably implemented in software, the actual connections between these system components (or processing steps) can visually formulate the present invention. The way is different. Given the teachings herein, those skilled in the art will be able to anticipate these and similar embodiments or configurations of the present invention.

Figure 1 shows an exemplary RREQ message format.

Figure 2 is a schematic diagram of a wireless mesh network according to one of the principles of the present invention.

Fig. 3 is a schematic diagram of a wireless mesh network according to one of the principles of the present invention.

Figure 4 is a flowchart showing the use of the on-demand routing protocol of the present invention.

Figure 5 is a flow chart of the method of the present invention.

Fig. 6 is a block diagram of a node according to the principle of the present invention.