Route selection in wireless networks
Abstract
This record has no abstract on file.
Term
Term ended
Projected expiry passed 9 November 2025, 0.9 years ago.
- Priority and filed
- Published
- Projected expiry
- Today
6 claims: 3 independent, 3 dependent
- 1Zastrzeżenia claim 1. A system for routing between the source node (A) and the destination node (E) in a wireless network, including:1. System do wytyczania trasy pomiędzy węzłem źródłowym (A) a węzłem docelowym (E) w sieci bezprzewodowej, obejmujący: means for receiving the route request message (RREQ) sent by said source node (A);środki do odbierania wiadomości żądającej podania trasy (RREQ) wysyłanej przez wspomniany węzeł źródłowy (A);means for responding to said message request (RREQ) of route request by message (RREP) response to route request request by the first intermediate node (B) having a valid route to said destination node (E);środki do odpowiadania na wspomnianą wiadomość (RREQ) żądania podania trasy za pomocą wiadomości (RREP) odpowiedzi na żądanie podania trasy przez pierwszy węzeł pośredniczący (B) posiadający obowiązującą trasę do wspomnianego węzła docelowego (E);means for updating said route request message (RREQ);and means for re-priming said wireless network with said route request message;środki do aktualizowania wspomnianej wiadomości żądającej podania trasy (RREQ);oraz środki do powtórnego zalewania wspomnianej sieci bezprzewodowej wspomnianą wiadomością żądającą podania trasy;characterized in that said intermediate node (B) comprises means for responding to said message (RREQ) requesting a route when the marker (IR) in said message (RREQ) requesting a route is set, and in that said intermediate node (B) ) further includes means for re-priming said wireless network with said message (RREQ) requesting a route with a reset of said tag (IR). znamienny tym, że wspomniany węzeł pośredniczący (B) obejmuje środki do odpowiadania na wspomnianą wiadomość (RREQ) żądającą podania trasy, gdy znacznik (IR) we wspomnianej wiadomości (RREQ) żądającej podania trasy jest ustawiony, oraz tym, że wspomniany węzeł pośredniczący (B) obejmuje ponadto środki do powtórnego zalewania wspomnianej sieci bezprzewodowej wspomnianą wiadomością (RREQ) żądającą podania trasy ze zresetowanym wspomnianym znacznikiem (IR).
- 3The system according to any of claims 1 to 2, wherein said means for responding in this way establishes a temporary shipping route between said source node (A) and said destination node (E) of said wireless network. 3. System według któregokolwiek z zastrzeżeń 1 do 2, w którym wspomniane środki do odpowiadania tym sposobem ustanawiają tymczasową trasę wysyłkową pomiędzy wspomnianym węzłem źródłowym (A), a wspomnianym węzłem docelowym (E) wspomnianej sieci bezprzewodowej.
- 6The system according to any of claims 1 to 5, wherein said wireless network is a wireless mesh network, said said response message requesting the route of said means for responding is a one-time sending to said source node in which the address of said destination node is one of the protocol addresses Internet and media access control address, wherein said destination node includes destination nodes that are associated with one proxy and access point, 6. System według któregokolwiek z zastrzeżeń 1 do 5, w którym wspomniana sieć bezprzewodowa jest bezprzewodową siecią kratową, gdzie wspomniana wiadomość odpowiedzi na żądanie podania trasy wspomnianych środków do odpowiadania jest jednorazowym wysłaniem do wspomnianego węzła źródłowego, w której adres wspomnianego węzła docelowego jest jednym z adresów protokołu internetowego i adresem kontroli dostępu do mediów, gdzie wspomniany węzeł docelowy obejmuje węzły docelowe które są powiązane z jednym z proxy i punktem dostępowym, Authorized:Thomson Licensing Uprawniony: Thomson Licensing Pełnomocnik: Proxy: dr inż. Robert Teofilak Patent Attorney dr inż. Robert Teofilak Rzecznik patentowy DŁUGOŚĆ ZNACZNIKI |nL LICZNIK LICZBA RREQ ID ADRES NUMER JODLE- cc LENGTH MARKERS | nL COUNTER NUMBER RREQ ID ADDRESS JODLE number FIG. 2 FIG. 3 FIG. 2 FIG. 3 PRZETWARZANIE RREQ RREQ PROCESSING PRZEKAZYWANIE DALEJ RREQ ORAZ TWORZENIE RREP SUBMISSION OF RREQ AND CREATION OF RREP ARE MORE ADDRESSES IN RREQ.DEST [i]? CZY JEST WIĘCEJ ADRESATÓW W RREQ.DEST[i]? DOCUMENTS CITED IN THE DESCRIPTION DOKUMENTY CYTOWANE W OPISIE Ta lista dokumentów cytowanych przez Zgłaszającego została przyjęta jedynie dla informacji czytającego i nie jest częścią europejskiego opisu patentowego. Została ona utworzona z dużą starannością;Europejski Urząd Patentowy nie ponosi jednak żadnej odpowiedzialności za ewentualne błędy i braki. This list of documents cited by the Applicant was accepted only for the information of the reader and is not part of the European patent specification. It was created with great care;However, the European Patent Office shall not be liable for any errors or omissions. Dokumenty patentowe cytowane w opisie • WO 0141375 A [0006] • EP 1467524 A [0006] Patent documents cited in the description • WO 0141375 A [0006] • EP 1467524 A [0006] Dokumenty niepatentowe cytowane w opisie • PERKINS i in. Ad-hoc On-Demand Vector Routing. PROCEEDINGS WMCSA, 25 lutego 1999 r. [0005] Non-patent documents cited in the description • PERKINS et al. Ad-hoc On-Demand Vector Routing. WMCSA PROCEEDINGS, February 25, 1999 [0005]
Independent claims3
34 paragraphs, as filed
[0001] The present invention relates to wireless networks, in particular wireless mesh networks. In particular, the present invention relates to the processing of messages requesting routing in on-demand routing protocols.
BACKGROUND OF THE INVENTION [0002] On-demand routing protocols, such as the Ad Hoc Ondemand Distance Vector (AODV) routing protocol defined by the MANET working group in IETF, use the Route Request mechanism and Route Reply (route response request) to establish routes between two nodes in wireless mesh networks / ad hoc networks. When the source node wants to send packets / frames of data to the destination node, the source node calculates the route by flooding the network with a Route Request (RREQ) message, if the source node does not have and needs a valid route to the destination node. A return route back to the source is created by nodes in the network when they receive and forward RREQ. When the node receives the RREQ, the receiving node responds to this request by generating a Route Reply (RREP) message when either: (1) the receiving node itself is the destination node, or (2) the receiving node has a valid route to the destination, and a flag is NOT set "Destination only" ('D') in the RREQ message. RREP is forwarded to the source node in a one-time send via the established return route and dispatch route to the recipient at intermediate nodes and is ultimately created in this way at the source node. Established routes expire if they are not used within the set service life of the routes.
[0003] In AODV, the "destination only" flag of the RREQ message is set by the source node and is not changed by the intermediate nodes. If the "destination only" tag is set in the RREQ message by the source node, then the intermediate nodes do not respond to the RREQ with the RREP message even if the intermediate / receiving node has a valid route to the destination node. Forwards / floods his neighbors with RREQ message again. Only the destination node responds to RREQ. In this mode of operation, the mapping delay can be large, although ultimately the best route is currently mapped in the process between the source node and the destination node. Low latency is very important for real-time applications such as voice and video connections.
[0004] If the "destination only" tag is not set by the source node, then each intermediate node with a valid route to the destination node responds to the RREQ with a RREP message. The RREP message is sent back in a one-time send to the source node and establishes the shipping route to the destination node. If the "Gratuitous RREP" tag ('G') is set in the RREQ message, then this intermediate node also sends a one-time send of unnecessary RREQ to the destination node so that the destination node knows the routes to the source node. However, in AODV, if the intermediate nodes generate RREP, however (because the intermediate node has a valid route to the destination node), then the intermediate node rejects the RREQ. With this approach, the source node can route to the destination node faster because the source node does not have to wait for the destination node to respond. However, the best route from end to end may not be calculated because the buffered route at the intermediate node may not be the best route to the destination node. The distance may change due to the dynamics of wireless networks, making the cached route less desirable. Thus, due to changes in network topology, route distances, etc., it is possible that the buffered route may become worse or other routes with a more favorable end-to-end distance may become available, causing these other routes will be more desirable.
[0005] Perkins et al. in "Ad-hoc On-Demand Vector Routing" (in PROCEEDINGS WMCSA, 25 February 1999, XP002173721) discloses the "Emergency Remote On-Demand Vector Routing" (AODV) algorithm for routing operations in a wireless network without a centralized access point. The algorithm consists in dynamically establishing routing table entries on intermediate nodes and uses the Route Request (RREQ) and Route Reply (RREQ) mechanisms. This algorithm reduces the delay in finding the route to the destination node, however, unlike the end-to-end routing mechanism, the system is not suitable for plotting the best route from end to end (e.g. the shortest route). Because the RREQ message is not propagated to the destination node, when the valid route is found in the intermediate node, the distance from the end to the end is not systematically reported in the RREP message to the source node, and the valid route buffered by the intermediate node may not be the best route to destination node.
[0006] WO 01/41375 discloses a routing protocol algorithm for ad-hoc (ad-hoc) networks, both based on source routing and distance vector routing. Pursuant to WO 01/41375, both the source routing request message and the updated routing request, recognized by the tag, are poured into the network after a predetermined event, such as counter time elapsed, connection interruption ... However, WO 01/41375 fails to disclose a system suitable for both quickly tracing the source node and the destination node and for mapping the best route between the source and destination node in response to a request from the source, while limiting request / response messages on the network. EP1467524 discloses an algorithm for an ad hoc network routing protocol suitable for considering quality of service, such as delay and bandwidth in communication. According to EP 1467524, in addition to the lowest link costs, number of sequences, other criteria are considered, such as link bandwidth, to establish the best route between nodes. However, as mentioned for the current state of the art, EP1467524 fails to determine a system that matches both the fast routing between source and destination nodes and the best route between source and destination nodes.
[0007] The problem addressed by the present invention is how to use the RREQ and RREP mechanism to quickly plot the best route between a source node and one or more destination nodes.
DESCRIPTION OF THE INVENTION [0008] The present invention discloses a method and system for processing / forwarding Route Request (RREQ) messages and generating Route Reply (RREP) messages in request routing protocols, of which AODV is an example so that the best route can be mapped without introducing a significant delay / delay in wireless mesh / ad-hoc networks. In particular, when the source node wants to route to the destination node, the source node floods the network with a RREQ message with the destination node specified in the list of recipients and the distance field initialized to 0. The RREQ message contains a new "Intermediate Reply (IR) tag" agent) for each destination node. The source node sets the flag corresponding to the destination node in the RREQ when it initiates flooding with the RREQ message to route it to the destination node (s). When flooding with a RREQ message, the first intermediate node that has a valid route to the destination node responds to the RREQ with the RREP message. The RREP message is sent once to the source node and thus quickly establishes a temporary shipping route to the destination. Thus, the source node may use this temporary sending route to send packets / data frames with low delay / routing delay. The first intermediate node resets / cancels the "IR" flag in the RREQ message and forwards the updated RREQ message towards the destination node. Because the "IR" tag in the RREQ message has been reset, subsequent intermediate nodes will not respond to this RREQ message, but will only spread RREQ, even if the subsequent intermediate nodes have a route to the destination node (s). Eventually, the RREQ messages reach the destination node (s). The destination node (s) may (may) choose the best route / path based on the distance between its ends, and sends a new RREP message back to the source node to establish the best route between the source node and destination. If this best route differs from the temporary shipping route that was established via the RREP message from the intermediate node, then the source node will switch to the best route as soon as the best route has been established.
[0009] A system and method of mapping a route between a source node and a destination node in a wireless network has been described, including setting an intermediary response marker for a route request request message by the source node, flooding the wireless network with a route request message, and responding to a route request message with a response message route request from the first intermediate node that has a valid route to the destination node. The system and method then updates the route request message and floods the wireless network again with the route request message. Said act of responding in this way establishes a temporary shipping route between the source node and the destination node of the wireless network.
The system and method of mapping the best route are also described, in which case the route response message becomes the first route response message. The system and method of mapping the best route includes selecting by the destination node the best route between itself and the source node based on the cumulative distances received by the destination node in route request messages, creating another response message on route request and sending the next response message once route request to source node. If the temporary shipping route is the best route, then the next route response message serves as confirmation, and if the temporary shipping route is not the best route, then the next route response message is used to establish the best route, after receiving the next response message on route request by source node.
BRIEF DESCRIPTION OF THE DRAWINGS [0010] The present invention is most easily understood from the following detailed description when read in conjunction with the accompanying drawing. The drawing contains the following figures briefly described below:
Fig. 1 is an exemplary RREQ message format.
Fig. 2 is a schematic diagram of a wireless mesh network according to the principles of the present invention.
Fig. 3 is a schematic diagram of a wireless mesh network according to the principles of the present invention.
Fig. 4 is a flow diagram of an on-demand routing protocol showing where the present invention is used.
Fig. 5 is a flowchart of the method of the present invention.
Fig. 6 is a block diagram of the node according to the principles of the present invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS [0011] When a point of the source node / lattice wants to send packets / frames of data to a certain destination node, it checks the routing table to get the route. If there is a valid route there, it transmits packets / frames to the next hop specified for this destination node through the routing table. If there is no valid route, then the source node initiates route mapping by flooding the wireless mesh / ad hoc network with a Route Request (RREQ) message. Packets / data frames can originate from a node or from stations associated with that node if the node is a wireless access point. It is possible that the source node needs to route / route to multiple destination nodes. The source node can distribute the RREQ message to each destination, or, to reduce routing overhead, flood the network with a single RREQ message that has a list of multiple destination addresses contained therein.
[0012] Fig. 1 shows an exemplary RREQ message format, other formats are possible. The RREQ message contains, for example, the start / source node address, its sequence number, destination node address and destination sequence number (or the number of destinations and list of destination addresses and their sequence numbers), RREQ ID, message ID, message length, lifetime (TTL), hop count, route length, markers, and other information. In addition to the 'Destination Only' ('D') tags ('addressee') and 'Gratuitous RREP' ('G') tags (RREP not needed), a new tag is included in the RREQ message, called 'Intermediate Reply' (IR) ). The "D" and "G" tags are moved older, for regular AODV. Both of these tags are not set / used by the source node and are ignored by the intermediate and destination nodes. One alternative embodiment is that the RREQ message has no 'D' or 'G' markers at all. If the RREQ message contains a list of destination addresses, then the RREQ message contains multiple "Intermediate Reply" tags, each of which corresponds to a destination address. If the source node wants to route to one or more destination addresses, it sets the "Intermediate Reply" (IR) tag (s) corresponding to the destination address. It should be noted that the address (addresses) of the destination node may (may) be the Internet Protocol (IP) address (s) or Layer 2 address (s) (MAC media access control). To adapt to network changes and maintain the route with the best distance between nodes, each active source node can optionally flood the wireless mesh network / ad hoc periodic RREQ (maintenance RREQ) message for the destination address (destination) to which it connects . The "IR" flag in the RREQ maintenance message is not set. Intermediate and destination nodes process the RREQ maintenance message using the same principles that are used to process non-maintenance RREQ messages during the staking phase.
[0013] Thus, it can be seen that the dissemination of maintenance and non-maintenance RREQ messages on wireless mesh / ad-hoc networks results in the establishment / update of a return route to the originator (source node) of the RREQ message at intermediate nodes and destination nodes. Spreading non-conservative RREQ messages also triggers RREP messages from destination nodes, and possibly from intermediate nodes. Spreading maintenance RREQ messages triggers RREP messages from destination nodes.
[0014] When the intermediate or destination node receives the RREQ message, it creates a return route to the source node or updates the current return route if the RREQ message has followed a route / path that offers a better distance than the current return route to the source node. It should be noted that each node may receive multiple copies of the same RREQ message (originating from the same source node and having the same RREQ ID), with each RREQ message passing a different route from the source node to the receiving / intermediate / destination node. If the return route is created or modified, or it is the "first copy" of the RREQ message, the RREQ message is forwarded (floods the network again). Here, the term "first copy" is used in the sense that this copy of this RREQ message is the first copy or time when this receiving / intermediary / destination node received or noticed this particular RREQ message recognized by its originator's address and RREQ ID. When the intermediate node forwards the RREQ message, the distance field in the RREQ message is updated to reflect the cumulative route length to the source node of that RREQ from the intermediate node. Furthermore, if the "IR" flag for the destination node in the destination node list of the received RREQ message is set and the intermediate node has a valid route to the destination node, the intermediate node responds to the RREQ message with a RREP route request reply message. This route request response is sent once to the source node, and a shipping route is established to the destination node. The source node then immediately uses this route to send data packets / frames to the destination node. If the intermediate node responds to the RREQ message with the RREP message for the destination node from the node list to the target RREQ message, it resets / clears the "IR" tag for that destination node in the RREQ message before it floods the network with the updated RREQ message. The reason to reset the "IR" tag after the RREP message is sent is to reduce the amount of any RREP messages from subsequent intermediate node data streams. Only the first intermediate node that has a valid route to the destination node along with the route traveled during the flooding with the RREQ message corresponds with the RREP message for that destination node. If the "IR" flag for the destination node is reset / deleted in the RREQ message, then the intermediate node should not respond with the RREP message, even if it has a valid route to the destination node.
[0015] After creating / establishing or updating the return route to the source node, the destination node sends the RREP message once back to the source node. Intermediate nodes create forwarding routes to the destination node (s) after receiving the RREP message, as well as forward the RREP message towards the source node. When the source node receives the RREP message, it creates a forwarding route towards the destination node. If the destination node receives further RREQ messages with better distances, the destination node updates its route to the source node on a new route, and also sends a new RREP message with the updated route back to the source node via this updated route. The new RREP message establishes a better (updated) shipping route from the source node to the destination node at the intermediate nodes and finally at the source node. As soon as a better shipping route is established, the source node uses it to send data. Finally, the best route with the best distance between the source node and the destination node is established. By using this approach, the source node can quickly get the route to the destination node, which it establishes thanks to the RREP message, which corresponds to the intermediate node having the valid route to the destination node. If this route is not the best end-to-end distance between the source node and the destination node, then the route is then updated to the best route.
[0016] Fig. 2 shows flooding of a wireless mesh / ad-hoc network with a Route Request (RREQ) message, and intermediate node B having a valid route to destination node E responding to a RREQ message with a RREP message. Consider the example where source node A attempts to route to destination node E. Source node A is flooding the wireless mesh / ad hoc route message (RREQ) with the "IR" flag set. Suppose that intermediate node B already has a valid BCDE route to destination node E. When intermediate node B receives an RREQ, it creates a return route to the source node from which it receives the RREQ message as the next hop (source node A) of the route / return path. Intermediate node B responds to the RREQ message with a one-time RREP message because it has a valid route to destination node E and the "IR" flag in RREQ is set. RREP establishes a shipping route to destination node E at source node A. As soon as source node A creates a route / path to destination node E, thanks to RREP message from intermediate node B, source node A can start sending data packets / frames to destination node E ABCDE route. Intermediate B resets the "IR" flag in the RREQ message and forwards it. The reason for resetting the "IR" tag is to limit the response to flooding with the RREQ message to only the first intermediate node that has a valid route to the destination node. Other intermediary nodes in this data stream, such as C and D, do not need to respond to this RREQ message with a RREP message because the "IR" flag is not set. Let's assume that intermediate nodes F, G and H do not have a valid route to destination node E. When intermediate nodes F, G and H receive flooding RREQ messages, they form a return route to source node A with the node from which each intermediate node F, G and H receives RREQ as the next hop on the return route. Then, each of the intermediate nodes F, G and H forwards RREQ messages.
[0017] In this example, destination node E receives two copies of this RREQ, each traveling on a different route: ABCDE, AFGHE. Assuming that these two RREQs reached destination node E in the following order ABCDE, followed by AFGHE, then destination node E first creates a route to source node A via intermediate node D as soon as destination node E receives the RREQ via route ABCDE. At this point, the return route to source node A is established at intermediate nodes B, C and D. Destination node E sends the RREP along the EDCBA route. The RREP message simply refreshes the ABCDE route. If there are other destination nodes on the list of RREQ message recipients, e.g. node I, destination node E removes itself from the list of recipients, and then forwards the RREQ message (e.g. to node I). If there are no other destination nodes in the list of RREQ message recipients, RREQ is not forwarded.
[0018] Referring to Fig. 3, which shows a wireless local mesh network, a situation is shown in which the destination node E responds with a RREP message (1) after the RREQ is received by ABCDE and sends a new RREP (2) to establish a better route / path mail order, after receiving RREQ via AFGHE path. When destination node E receives the RREQ that came through the AFGHE path, destination node E determines that this RREQ came along the path with a better distance to A than the ABCDE temporary route / shipping path. Therefore, destination node E changes / updates the next hop from intermediate node D to intermediate node H and updates distances. Then, with a one-time sending, destination node E sends RREP back to source node A via intermediate node H, as well as updates and forwards the RREQ message if there are one or more destination nodes in the list of RREQ message recipients. RREP establishes a route to source node A through the intermediate nodes H, G and F. When source node A receives this RREP, it changes / updates the next hop to destination node E from intermediate node B to intermediate node F. The route to destination node E is changed to AFGHE.
[0019] Reference will now be made to Fig. 4, which is a flowchart of RREQ message processing. When the node receives the RREQ message, it first creates / establishes or updates the return route to the previous hop from step 410 from which the node received the RREQ message, if needed. The broker / receiving node can then create or update the return route to the creator of the RREQ message as follows. If the route back to the creator of the RREQ message does not exist in the routing table or is invalid in steps 415 and 420, it is created or updated. The next hop in the routing table for the return route to the RREQ creator becomes the previous hop (node from which the RREQ message was received). If there is a valid return route to the RREQ creator, the source sequence number in the RREQ message is compared in step 425 with the route entry sequence number in the route table for the return route. If the sequence number in the RREQ message is older, it is abandoned and no further processing is done in step 445. Otherwise, the current route back to the creator is changed in step 430, as long as the new distance is better than the distance from the current route to the creator in the routing table. The new distance is defined as the distance in the RREQ message plus the length of the link from each other to the node from which the RREQ message was received. If the new distance is not better than the distance of the current return route in the routing table entry, but the number of the source sequence in RREQ is greater (newer) than the sequence number in the routing table for the reverse route in step 435, then the intermediate node checks in step 450 whether they are Optional hysteresis processing and buffering best route candidates supported by the mesh network. If these optional processing functions are not supported, the return route to the RREQ creator is updated in step 455. When a reverse route is created or changed, the sequence number in the routing table for the return route is set to the source sequence number in the RREQ message, the next hop becomes the node from which the RREQ message was received, the distance is set to the new distance, and the number of hops is set to one more than the hop count in the RREQ message.
[0020] If the return route to the source node was created or changed in step 420 and 440, or the RREQ message was the first copy of a new RREQ message (the RREQ ID was not previously seen from the source), the procedures for forwarding the RREQ message and creating the RREP message here described are performed in step 475. Other cases may occur when the RREQ forwarding and RREP message creation procedures described herein are performed by a node. For example, in some caching routine for top route candidates, RREQ messages may be stored in a waiting queue under timer supervision while caching a candidate route. When the timer counts down the waiting queue, the procedures for forwarding RREQ messages and creating RREP messages are performed.
[0021] The source node may periodically send maintenance RREQ messages to refresh its operational forwarding and return routes. Each time the source sends a maintenance RREQ message, this is called a route refresh cycle. It is possible that nodes already having the best return routes to the source node receive the RREQ message with a newer sequence number, but with a worse distance to the source node before receiving the RREQ message via the current best route. In addition, a copy of the RREQ message that is spread along with the best route that is currently running may be lost during flooding. These cases can lead to the sending of the advertised route back and forth. In order to reduce the effect of sending the advertised route back and forth, and to select the best route during each route refresh cycle, a mechanism such as hysteresis and a mechanism for buffering the best route candidates may be used. If in step 450 it was specified that the mesh network uses hysteresis and caching options for the best route candidates, the intermediate node updates the routing table and changes the return route, provided that the source sequence number in the RREQ message is larger (newer) than the sequence number in the routing table entry by more than the threshold. Otherwise, the reverse route may be buffered in step 465 as a potential alternative route candidate.
[0022] If, as a consequence, the node realizes that the current reverse route has deteriorated and becomes worse than the reverse route candidate, it may switch to the route candidate previously known in the same refresh cycle. The present invention describes a method and system for forwarding RREQ messages and creating RREP messages for mapping the best route without introducing a significant delay / delay in wireless mesh networks. The method of the present invention works with or without hysteresis and buffering of the best candidate / route alternative. [0023] Figure 5, which is a flowchart describing how to forward RREQ and generate RREP according to the present invention, shows a node that determines in step 505 whether it is a destination node, i.e. if one address or more node (self_addr) matches the desired destination addresses in the rreq.dest list of RREQ destination addresses. Note that the node itself can have multiple addresses or can be a proxy (proxy) for other nodes. For example, a node may be an access point and generate / manage messages on behalf of older stations associated with it (proxy for these stations). The functionality for this case is similar to when a node has multiple addresses. Destination addresses of associated stations can be treated as placeholders for the access point. A node is a destination node if one or more of the addresses specified in the list of RREQ message recipients belongs to it, or one of the nodes uses it as a proxy. When a node receives a RREQ message in which the destination node is the node through which the proxy is referring, it should process the RREQ message as if the destination node's address was its own address. Furthermore, the node may be the destination node for the requested addresses from the list of RREQ message recipients, but also an intermediate node for other requested addresses from the list of RREQ message recipients.
[0024] If one or more node addresses match the desired destination addresses from the RREQ message destination list, then for those addresses matching the destination addresses, the node creates and sends in step 510 a one-time sent RREP message to the creator of the RREQ message. The destination node removes the e-mail address (s) / proxy from the list of RREQ message recipients in step 515. Then, if no desired addresses remain in the RREQ message recipient list in step 520, the RREQ message is rejected in step 525. If the node is not the destination node for any of the requested addresses from the list of RREQ message recipients (step 505), or if there are other requested addresses from the list of RREQ message recipients different from the addresses of that node, i.e. the node is an intermediate node for one or more addresses from the list of RREQ message addresses, the node checks the remaining addresses from the list of RREQ message recipients as follows. Let's assume that rreq.dest [i] expresses (i + 1) the -th address on the list of RREQ message recipients. The node initiates the indicator (i.e., i) in step 545 and checks rreq.dest [i] in step 550, i.e. the first address from the list of RREQ message recipients to determine if there is an active shipping route to the destination node represented by rreq. dest [i]. If the intermediate node has an active route to the destination node, then the route to the destination node is valid (step 555), the sequence number at least as large as that indicated in the original RREQ message (step 560), and the "Intermediate Reply (IR)" tag is set (step 570), the intermediate node generates the RREP message for the requested destination address in step 575 and sends the generated RREP message once by sending the RREQ message to the creator on the current return route. The "IR" flag for this requested destination node in the RREQ message is reset in step 580. The node increases the indicator (for example, by one) (step 585) and checks in step 590 if there are any additional addresses in the list of RREQ message recipients. If there are any additional addresses on the list of RREQ message recipients, then the execution of the above described loop is repeated starting from step 550. Thus, the loop is repeated if it is necessary to send a RREP message for the next desired destination node. The loop is repeated until all addresses from the list of RREQ message recipients have been checked.
[0025] In step 530, the original incoming RREQ message is checked to determine if the time-to-live (TTL) value is greater than 1. If the TTL value is greater than one, the information in the original message RREQ is updated at step 535, including a TTL decrease, for example, by one, in the outgoing RREQ message. The source sequence number, distance, hop count are also set to the appropriate information in step 535 in the updated route entry for the source. The updated RREQ message is forwarded in step 540. [0026] Note that the destination node may have / proxy one or more destination addresses, and the intermediate node may have a valid route (s) to one or more destination addresses. A RREQ message may move one destination address or more addresses on its list of recipients. The processing / intermediary / destination node can meet the above conditions and sends a RREP message to many requested addresses from the list of RREQ message recipients. If a node sends a RREP message to multiple destination nodes, it may send multiple RREP messages, one for each of the destination nodes, or may send a single composite RREP message with multiple destination addresses in the address list.
[0027] Fig. 6 is a block diagram illustrating the details of the node 600 of the present invention. The node includes a module 605 for measuring quality and link load, module 610 for calculating route distance, module 615 for route selection, and module 620 for communication. The link quality and load measurement module 605 measures the link / channel quality and load to each of its neighbors. It provides measurement results to the route distance calculation module 610 so that the route distance calculation module 610 can determine the cost / distance of the link to each of its neighbors. It is worth noting that a node can have numerous neighbors, numerous radio interfaces, and numerous physical / logical channels / links. They must all be measured. The module 610 for calculating the route distance of each node uses measurements made by the quality and link load measurement module along with other information to calculate the route distance for each of the nodes with which it connects. The route distance is updated periodically. Route selection module 615 determines / selects the route / path for transmitting / communicating data to the destination node based on the calculated route distances. Route selection module 615 exchanges data and messages controlling routing with other nodes in the mesh network via communication module 620. It should be noted that the node may have one or more radio interfaces and other communication interfaces. It is understood that the route selection module may actually consist of several smaller units, or be combined with other modules described herein. Furthermore, it is understood that the processes described herein (in particular with reference to Figures 3 and 4) may be software, hardware, firmware, or any combination thereof that are performed in a module or by a route selection module.
[0028] It is understood that the present invention may be implemented in various forms of hardware, software, firmware, special purpose processors or combinations thereof, for example, in a mobile terminal, access point or cellular network. Preferably, the present invention is implemented as a combination of hardware and software. Furthermore, the software is preferably implemented as an application program actually contained in the software storage device. The application program can be uploaded there and executed by a device with appropriate architecture. Preferably, the device is implemented on a computer platform having hardware such as a processor (CPU) or several processors, operational memory (RAM) and I / O interface (s). The computer platform also includes an operating system and microinstruction code. The various processes and functions described herein may either be part of the microinstruction code, or part of the application program (or a combination of those) that are executed through the operating system. In addition, various other peripheral devices may be connected to the computer platform, such as an additional storage device and a printing device.
[0029] In addition, it is understood that since certain components of the system components and method steps described in the accompanying figures are preferably implemented in software, the actual connections between the system components (or processing steps) may vary depending on how it is programmed the present invention. Given these teachings, one of skill in the art will be able to consider these and similar implementations or configurations of the present invention.
60 members in 17 offices
Priority claims8
| Document | Office | Kind | Date |
|---|---|---|---|
| 05824653 | European Patent Office (EPO) | A | |
| 05824653 | European Patent Office (EPO) | A | |
| 10189237 | European Patent Office (EPO) | A | |
| 2005040699 | United States of America | W | |
| 2005040699 | United States of America | W | |
| EP20050824653 | – | – | – |
| EP20100189237 | – | – | – |
| WO2005US40699 | – | – | – |
Members60
| Document | Office | Kind | |
|---|---|---|---|
| AU2005338057A1 | Australia | A1 | |
| CA2627432A1 | Canada | A1 | |
| WO2007055689A1 | World Intellectual Property Organization (WIPO) | A1 | |
| TW200729836A | Taiwan Province of China | A | |
| EP1952588A1 | European Patent Office (EPO) | A1 | |
| KR20080074876A | Republic of Korea | A | |
| CN101305559A | China | A | |
| HK1120963A1 | Hong Kong, China | A1 | |
| JP2009515473A | Japan | A | |
| BRPI0520670A2 | Brazil | A2 | |
| US2009135824A1 | United States of America | A1 | |
| AU2009212921A1 | Australia | A1 | |
| KR20090116808A | Republic of Korea | A | |
| TW201001989A | Taiwan Province of China | A | |
| AU2010202493A1 | Australia | A1 | |
| KR20100103678A | Republic of Korea | A | |
| EP2296325A2 | European Patent Office (EPO) | A2 | |
| EP2296326A1 | European Patent Office (EPO) | A1 | |
| AU2005338057B2 | Australia | B2 | |
| EP1952588B1 | European Patent Office (EPO) | B1 | |
| AT509448T | Austria | T | |
| ATE509448T1 | Austria | T1 | |
| EP2296325A3 | European Patent Office (EPO) | A3 | |
| TW201123770A | Taiwan Province of China | A | |
| PT1952588E | Portugal | E | |
| AU2009212921B2 | Australia | B2 | |
| ES2366373T3 | Spain | T3 | |
| US2011255479A1 | United States of America | A1 | |
| US8064416B2 | United States of America | B2 | |
| RU2010120572A | Russian Federation | A | |
| RU2010120573A | Russian Federation | A | |
| CN101305559B | China | B | |
| PL1952588T3 | Poland | T3 | |
| TWI357242B | Taiwan Province of China | B | |
| JP4939544B2 | Japan | B2 | |
| KR101183342B1 | Republic of Korea | B1 | |
| KR101192937B1 | Republic of Korea | B1 | |
| KR101225274B1 | Republic of Korea | B1 | |
| EP2296326B1 | European Patent Office (EPO) | B1 | |
| AU2010202493B2 | Australia | B2 | |
| ES2413433T3 | Spain | T3 | |
| PL2296326T3This record | Poland | T3 | |
| TWI430619B | Taiwan Province of China | B | |
| EP2296325B1 | European Patent Office (EPO) | B1 | |
| PT2296325E | Portugal | E | |
| ES2472691T3 | Spain | T3 | |
| PL2296325T3 | Poland | T3 | |
| CA2627432C | Canada | C | |
| RU2544985C2 | Russian Federation | C2 | |
| RU2550151C2 | Russian Federation | C2 | |
| RU2013151444A | Russian Federation | A | |
| PH12012502208A1 | Philippines | A1 | |
| PH12012502208B1 | Philippines | B1 | |
| RU2628334C2 | Russian Federation | C2 | |
| RU2017116747A | Russian Federation | A | |
| RU2017116747A3 | Russian Federation | A3 | |
| BRPI0520670B1 | Brazil | B1 | |
| BRPI0520873B1 | Brazil | B1 | |
| BRPI0520882B1 | Brazil | B1 | |
| RU2682930C2 | Russian Federation | C2 |
Numbers
- Publication, DOCDB
- 2296326
- Publication, EPODOC
- PL2296326T
- Application
- 20100189237
- Application, DOCDB
- 10189237
- Application, EPODOC
- PL20100189237T
Titles2
- English
- Route selection in wireless networks
- Polish
- Wyznaczanie trasy w sieciach bezprzewodowych
Classification
- CPC, 9
- H04L45/26
- H04W40/28
- H04L45/32
- H04W40/248
- H04W40/02
- H04W40/00
- Y02D30/70
- H04W40/023
- H04L45/02
- IPC, 2
- H04W40 24
- H04L45 02