JP4927658B2 - Routing method and node device - Google Patents

Description

  The present invention relates to a routing method and a node apparatus in which each node autonomously selects a communication path for transmitting information in a network in which a plurality of nodes are interconnected, and more specifically, The present invention relates to an improvement in an autonomous configuration method of a routing group that performs communication by selecting an optimum communication path according to service quality such as delay time, throughput, and error rate in an interconnected network.

  In a network in which packets are exchanged between nodes using wireless communication, the connection form between nodes is not fixed, and the network in which the network configuration changes adaptively depending on the propagation environment and other conditions is called an ad hoc network.

  In an ad hoc network, when performing multi-hop transmission in which a packet is transmitted via a plurality of nodes, packet transmission at a node constituting a route from the packet generation node to the destination node of the transmission packet is performed. It is necessary to determine the order, that is, to perform a routing operation. A routing function if the propagation environment between nodes is fixed in time or the change is made over a sufficiently long time compared to the time for generating and transmitting a series of packets. As long as it satisfies certainty and optimality performance, it is sufficient as an application for the actually used network. However, in an environment where the propagation environment between nodes changes greatly at short intervals due to reasons such as the movement of nodes, the routing function provided in the ad hoc network takes a short time until the routing is determined. And a function to reconstruct an appropriate route at high speed in response to environmental changes.

  The Internet Engineering Task Force Mobile Ad-hoc Netwok (manet) Dynamic Source Routing (DSR) Protocol (hereinafter referred to as DSR protocol) being standardized by the Internet Engineering Task Force Mobile Ad-hoc Netwok (manet) Working Group Has been proposed). The detailed provisions of the proposal are published on The Internet Engineering Task Force's Mobile Ad-hoc Netwok (manet) Workig Group Internet website: http://www.ietf.org/html.charters/manet-charter.html Non-Patent Document 1, The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4 (RFC 4728).

  Hereinafter, an outline of the operation of the network that realizes the routing function using the DSR protocol which is the conventional technique described in Non-Patent Document 1 will be described.

  FIG. 10 is a network configuration diagram for explaining a path reconfiguration operation in a conventional network.

  In FIG. 10, a node 900 is a transmission source node that generates a packet destined for the node 901. In the initial state, when sending a packet, the node 900 searches for a route to the destination node 901 according to the route discovery procedure (“Route Discovery Processing”) described in Chapter 8.2 of Non-Patent Document 1. Route Request) 930 to 933 are broadcast. The Route Request message is relayed and retransmitted in the network up to a predetermined number of hops by the transmission source node 900 (not shown). When the Route Request message reaches the destination node 901, the destination node 901 transmits a message (Route Reply: 940) for transmitting the route 950 toward the transmission source node 900. The Route Reply message 940 is transferred to the sending node 900 following the route 950 followed by the Route Request message 932 in the reverse direction. The transmission source node 900 that has received the Route Reply message 940 accumulates the route 950 that can reach the destination node 901, adds this route 950 to the packet to be transmitted, and transmits it to each packet to be relayed. The route can be displayed to the node, and the packet can be transmitted to the destination node 901. In addition, the route 950 is accumulated in all the nodes constituting the route 950 through which the Route Reply message 940 is transmitted and all the neighboring nodes that can intercept the Route Reply message 940. The As a result, when a new packet is generated that is addressed not only to the destination node 901 but also to any of the nodes constituting the route 950, the stored route information is not activated without starting the route discovery procedure. By using a part, it is possible to transmit a packet to a new destination node. Further, not only the nodes constituting the path 950 but also all the nodes capable of receiving signals sent from these nodes as transmission sources and new packets with any node constituting the path 950 as the destination node are newly created. Even when the packet is generated, the packet can be transmitted without using the route discovery procedure by using a part of the accumulated route information.

  Next, a route maintenance procedure (“Route Maintenance Processing”) described in Chapter 8.3 of Non-Patent Document 1 will be described.

  FIG. 11 is a network configuration diagram for explaining a path reconfiguration operation in a conventional network.

  In FIG. 11, the nodes arranged in the initial state and the set route are the same as those in FIG. 10 referred to in the description of the route discovery procedure. Now, the operation of the network when the node located in the node 1007-A in the initial state moves to the position of the node 1007-B and can no longer configure the route out of the communication reachability will be described.

  When a packet transferred along the path 1050 from the transmission source node 1000 toward the destination node 1001 reaches the node 1006, the node 1006 refers to the path 1050 stored in the packet and transfers the packet next. The packet is transmitted toward the power node 1007-A. However, since the node 1007-A has already moved to the position of the node 1007-B and is outside the reachable range of the signal transmitted by the node 1006, this packet cannot be received. Each node has means for detecting that the node that is the transfer destination of the next stage of the packet has received (or has not been able to receive) the packet. Using this means, the node 1007-A (or 1007) is used. -B) detects that this packet cannot be received, and transmits a message (Route Error) indicating that the route 1050 is unavailable to the transmission source node 1000. This Route Error message includes the same route information as the route 1050 included in the original packet transferred toward the destination node 1001, and the Route Error message is sent from the source node 1000 on this route. Each node between the source node 1006 and the source node 1006 forwards the Route Error message by following the route 1050 in reverse while referring to the route information. In addition, each node on the route that transfers the Route Error message invalidates the same information as the route information included in the Route Error message from the accumulated route information.

  When the transmission source node 1000 receives the Route Error message, the route information reaching the destination node 1001 is searched from the accumulated route information. If this valid route information is stored, the stored route information is used as route information included in a packet sent to the destination node 1001 thereafter. When effective route information that can reach the destination node 1001 cannot be found in the accumulated route information, and there is a packet to be sent to the destination node 1001, the route is found according to the route finding procedure. The packet can be sent only after it is discovered.

  Note that, according to the provisions of Chapter 8.3.6 of Non-Patent Document 1, when a Route Error message is transferred toward the transmission source node 1000, the node 1006 that generated this Route Error message sends it to the transmission source node 1000. In which the node 1005 located between the nodes stores the route information 1051 having the same destination node as the destination node of the route information included in the Route Error message. If the information of the original packet that has been transferred to the destination node 1001 is included, the Route Error message is removed from the packet, and the route information included in the packet is replaced with the accumulated route information. Generated and transferred according to the path 1001. However, even in this case, the Route Error message continues to be forwarded to the source node 1000 at the same time, and the source node 1000 discovers a new route by searching for another effective accumulated route information or a route discovery procedure. The source node 1000 cannot send out the packet addressed to the destination node 1001 unless it has been done.

According to the DSR protocol technique described in Non-Patent Document 1 described above, a transmission path of a packet is determined in an ad hoc network, and the transmission path is reconfigured in response to a change in transmission state caused by movement of a node constituting the path. Function can be realized.
Request for Comments (RFC) 4728: The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4, February 2007, The Internet Engineering Task Force

  However, in such a conventional DSR protocol, when a link between nodes constituting a route is disconnected, a Route Error message is returned from the node that detected the link disconnection to the transmission source node, and this message is transmitted. When the received transmission source node does not have valid route information that can reach the same destination node in the accumulated route information, it is necessary to reconstruct the entire length of the route according to the route discovery procedure again. In particular, in the route restructuring procedure over the entire length of the route, it is necessary to broadcast a Route Request message to be retransmitted over at least the number of hops more than the shortest hop number necessary to form an effective route, There was a problem that the entire network traffic was occupied by the flooding of this Route Request message. Furthermore, after detecting a link break, at least return a Route Error message to the source node, broadcast transmission of a Route Request message from the source node to the destination node, and return a Route Reply message from the destination node to the source node Since the route reconstruction is not completed until after each of the above procedures, there is a problem that the time required for the route reconstruction is increased and the throughput of the network is deteriorated. In addition, since all node information constituting the route from the transmission source node to the destination node needs to be accumulated in each node, the storage capacity required for the node increases as the route length increases. There is also a problem that the circuit scale of the node becomes large.

  The present invention has been made in view of the above, can reduce the influence on the traffic of the entire network, and shortens the time required for route reconstruction by limiting the route through which each message is transmitted. It is an object of the present invention to provide a routing method and a node device that can suppress degradation of network throughput.

  Another object of the present invention is to provide a routing method and a node device that can reduce the route information to be accumulated in each node and reduce the circuit scale of the node.

  The routing method of the present invention is a routing method in which each node autonomously selects a communication path for transmitting information in a network in which a plurality of nodes are interconnected, and has a signal to be transmitted. When a node broadcasts a message for searching for a route, and a node that should be located at the end of the route receives the message, it returns a response message by reversing the route through which the message has passed. A step of determining a communication path; and the response message includes at least information indicating the number of nodes constituting the path and the position of each node, and the node receiving the response message includes information included in the message. Originally, a step of forming a group of two or more nodes, respectively, A loop shares a node located at the boundary between adjacent groups, and at least in a node located at the boundary between the groups, the step of accumulating at least routing information in the group to which the own node belongs; and between the groups In the node located at the boundary of the information, information indicating the route information in the group is added to the information to be transmitted, or the information is transmitted to the node located at the end of the route by repeating the replacement operation. Steps.

  The node device of the present invention is a node device having a function for realizing the above routing method.

  According to the present invention, the route information to be accumulated in each node can be greatly reduced, and the circuit scale constituting the node can be reduced.

  Specifically, when the disconnection of a link constituting a route is detected, the route request message is broadcasted by applying the route discovery procedure only to the minimum range that bypasses the disconnected link. Can be limited to a small value. As a result, the influence on the traffic of the entire network can be reduced, and the time required to reconstruct the route can be shortened by limiting the route through which each message is transmitted. As a result, degradation of network throughput can be suppressed.

  Further, since the route information to be accumulated in each node can be reduced, the circuit scale of the node can be reduced.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

(Embodiment 1)
FIG. 1 is a network diagram in which a route is configured by the routing method according to the first embodiment of the present invention.

  In FIG. 1, a node 100 is a source node that generates a packet destined for the node 101. In the initial state, when the node 100 transmits a packet, a message (Route Request) for searching for a route to the destination node 101 according to a route discovery processing described in Chapter 8.2 of Non-Patent Document 1 (Route Discovery Processing). ) 130 to 133 are broadcasted. The Route Request message is defined in advance by the transmission source node 100, and is relayed and retransmitted within the network up to the number of hops displayed in the message (not shown). When the Route Request message reaches the destination node 101, the destination node 101 transmits a response message (Route Reply) 140 to the transmission source node 100. A list of information elements included in the Route Reply message 140 is shown in [Table 1].

Route Replyメッセージ１４０は、Route Requestメッセージ１３２がたどった経路１５０を逆向きにたどって送出ノード１００へ転送される。あて先ノード１０１は、前記あらかじめ規定されたホップ数の限度内で伝達されたRoute Requestメッセージのすべてに対して、それぞれのメッセージがたどった経路（図示せず）を逆向きにたどって、この経路を表す情報要素を含むRoute Replyメッセージ（図示せず）をそれぞれ返送する。

The Route Reply message 140 is transferred to the sending node 100 by following the route 150 followed by the Route Request message 132 in the reverse direction. The destination node 101 reverses the route (not shown) taken by each message in the reverse direction with respect to all Route Request messages transmitted within the limit of the hop number defined in advance. A Route Reply message (not shown) including an information element to be represented is returned.

  In the following, an extended function for the prior art made by the present embodiment will be described.

  FIG. 2 is a flowchart showing processing performed in each node when a Route Reply message is received. In the figure, S indicates each step of the flow.

  Upon receiving the Route Reply message (step S200), each node constituting the route 150 refers to the information element included in the message in step S201, and is closer to the transmission source node 100 than the own node (hereinafter referred to as upstream). The route reply message received is forwarded to the adjacent node.

  Next, the number of nodes constituting the route is acquired in step S202, and the local node position k in the route is acquired in step S203. In step S204, the route grouping means divides the nodes on the route into a certain number of groups according to the number of nodes constituting the route and a predetermined calculation method (not shown). Each of the groups is composed of two or more nodes, and a node located at the end of each group (hereinafter referred to as a group boundary node) is shared by adjacent groups.

  In step S205, it is determined whether or not the own node is a group boundary from the calculation result of the route grouping means in step S204 and the position of the own node acquired by the received Route Reply message. If it is determined in step S205 that the own node is a group boundary node, in step S206, this node accumulates the route in the upstream group among the two groups to which the own node belongs. If it is determined in step S205 that the own node is not a group boundary node, the process proceeds to step S207 without executing step S206.

  In step S207, the routes in the group to which the own node belongs (in the group boundary node, the group in the direction close to the destination node 101 (hereinafter referred to as the downstream) of the two groups to which the own node belongs) are accumulated. This flow ends.

  As an example, as a pre-defined calculation method in the route grouping means, the source node is set to 0, each node on the route to the destination node is numbered by 1 for each hop, A node having a number (ie, 3 and 7) closest to an integer multiple (ie, about 3.32 and about 6.64) of the square root (about 3.32) of the total number of nodes “11” that constitutes FIG. 3 shows a group configuration in the case where a means for configuring three groups as nodes is taken.

  FIG. 3 is a network diagram showing a group configuration when an example of a desirable calculation method is applied. In FIG. 3, a packet transmitted from the transmission source node 300 is transferred along the path 350 toward the destination node 301.

  The route information accumulated in the nodes 300 and 302 to 304 belonging to the group 360 is shown in [Table 2]. The route information accumulated in the nodes 304 to 308 belonging to the group 361 is shown in [Table 3].

このとき、グループ境界ノードにあっては、自ノードがともに属する、接して存在する２つのグループ内の経路をともに蓄積する。すなわち、ノード３０４においては、〔表２〕及び〔表３〕の内容をともに蓄積する。

At this time, in the group boundary node, the routes in the two groups existing in contact with each other are stored together. That is, in the node 304, the contents of [Table 2] and [Table 3] are stored together.

  By the means described above, the route information to be accumulated in each node can be greatly reduced as compared with the prior art, and thus the circuit scale constituting the node can be reduced.

  Next, an operation for transferring a packet from the transmission source node 300 to the destination node 301 will be described.

  The transmission source node 300 accumulates only the routes in the group 360 to which the own node belongs in the route 350. Further, only the accumulated route in the group 360 is added to the packet to be transmitted to the destination node 301 and transmitted. This packet displays the path to each node in the group 360 that constitutes the path 350, and each node forwards the packet to the group boundary node 304 accordingly. The group boundary node 304 refers to the address of the destination node included in the route information of the received packet, extracts the route information in the corresponding group 361 from the accumulated route information, and extracts the route information included in the received packet. Replaced with the accumulated path information and sent. By performing the same operation also at the group boundary node 308 located at the boundary between the group 361 and the group 362, this packet can be transferred to the target destination node 301.

  As a result, the route information contained in the packet can be greatly reduced compared to the prior art, and the proportion of information to be transmitted in the information amount of the entire transmitted packet can be increased. In an environment where the physical transmission speed is realized, the system throughput can be improved.

  In the above description, the route grouping means is configured to be provided in all nodes. However, this means is provided only for a node that can be a destination node, and a packet including a Route Reply message or a Route Reply message is transmitted. In order to transmit the packet, the group configuration information is sent to another packet sent on the same route at a timing close to the packet sent, and each node on the route receiving this packet receives the group configuration in the packet. By configuring so that route information to be accumulated can be selected by referring to the information, it is possible to configure so that a node other than a node that can be a destination node does not include route grouping means. With this configuration, it is possible to reduce the circuit scale of nodes other than the node that can be the destination node, reduce the processing time required to transfer the Route Reply message, and pass the node that should be the group boundary node. At this time, it becomes possible to transfer the Route Reply message from which the route information of the downstream group is deleted. For this reason, since the size of the Route Reply message can be reduced, and the transmission load of control information occupying the system transmission capacity can be reduced, the system throughput can be improved. Furthermore, when changing the route grouping means or when constructing a system for dynamically changing this means, it is not necessary to update the processing procedure for all the nodes in the network. By performing this update only for nodes that can be nodes, the processing procedure of the entire system can be updated.

  Further, in the above description, the procedure for determining the group configuration based on only the total number of nodes constituting the route is shown as a pre-defined calculation method in the route grouping means. By adding parameters such as hardware processing capability, communication quality between nodes, communication speed, and node density to the calculation basis, transmission of control information in communication reliability, communication speed, time required for route determination, and system throughput The group configuration may be determined so as to optimize conditions such as load. Still further, it is possible to configure such that the calculation method is dynamically changed in accordance with parameters that are measured or estimated by the node itself or that are separately provided from the measurement means or the estimation means. .

  By the way, in a neighboring node that can intercept a Route Reply message transmitted from a node constituting the route 350, which is routed when the Route Reply message is transmitted, the route 350 included in the intercepted Route Reply message and , You can know the address of the node that sent the intercepted message directly. Even in the neighboring nodes, the group configuration made for the route 350 can be known by applying the route grouping means. As a result, only the route in the group to which the node that transmitted the intercepted message belongs is selectively accumulated, and when a new packet is generated that is addressed to any of the nodes that constitute the route in the group, A packet can be transmitted to a new destination node by using a part of the accumulated route information without activating the route discovery procedure. Furthermore, even when a packet destined for the destination node 101 is newly generated, the route information at the group boundary node can be obtained without using the broadcast transmission means in the route discovery procedure by using the accumulated route information. The packet corresponding to the Route Request message can be transmitted to the destination node by unicast communication. As a result, each node on the route that receives a packet corresponding to the Route Reply message returned from the destination node can form an optimum group for the newly added route.

  As described above, as in the case of using the conventional technique, not only the packet transmission path but also the path of the packet transmitted from the node capable of intercepting the transmission packet can be determined.

  As described above in detail, according to the routing method of the present embodiment, the node has the function of executing the processing procedure shown in FIG. 2 when the Route Reply message is received, and the node located at the group boundary is suitable for the node. It has a function of replacing the path information included in the transmission packet. As a result, the information to be stored in the node can be reduced to reduce the circuit scale, and the information to be included in the transmission packet can be reduced to improve the system throughput.

  That is, the route information to be transmitted together with the information to be transmitted can include only a part of the route information, not the information over the entire length of the route, and the route information to be accumulated in the nodes constituting the route is also reduced. Therefore, the circuit scale of hardware constituting the node can be reduced.

  Further, in the present embodiment, it is detected that the information cannot be transmitted when information cannot be transmitted through one or more links among the links between the nodes constituting the route. The node transmits a message indicating that the route is unusable toward the group boundary node in the direction to which the information to be transmitted of the group to which the node belongs is transmitted. The group boundary node that has received this message searches the accumulated route information for an alternative route that can reach the group boundary node located at the other end of the group. If an alternative route can be found, this alternative route is used instead of the previously used route. As a result, when reconstructing a route, it is not necessary to reconstruct the entire length, and information can be transmitted by reconstructing only part of the route. This has the effect of reducing the load on the throughput.

  The effects described above are listed below.

  Compared with the conventional DSR protocol in which the effect is re-routed for the entire path for every change in the link state, <effect 1> the traffic amount of the control packet is not increased.

  <Effect 2> It can be applied to a large-scale (route including many hops) network.

  <Effect 3> It is possible to shorten the time required for reconfiguration of routing.

  <Effect 4> The capacity of the path information table to be held by each node can be reduced.

  <Effect 5> The size and the number of transmissions of control packets required for the conventional DSR routing can be made equal or less.

(Embodiment 2)
FIG. 4 is a network diagram in which routes are reconfigured by the routing method according to the second embodiment of the present invention.

  FIG. 4 shows the configuration of a network that transmits a packet from the transmission source node 400 to the destination node 401 on a route 450 configured in the same procedure as that shown in the first embodiment.

  Hereinafter, the operation of the network when the node located at the node 407-A moves to the position of the node 407-B when the route is configured and becomes unable to configure the route outside the communication reachable range will be described.

  When a packet transferred from the transmission source node 400 to the destination node 401 through the path 450 reaches the node 406, the node 406, as described in the first embodiment, stores the group stored in the packet. Referring to the route in 461, the packet is transmitted toward the node 407-A to be transferred next. However, since the node 407-A has already moved to the position of the node 407-B and is outside the reachable range of the signal transmitted by the node 406, this packet cannot be received. Each node is able to receive the packet by the node that is the next transfer destination of the packet by means equivalent to the prior art described in chapters 8.3.1 to 83.3 of Non-Patent Document 1. It has a means for detecting (or failed), and this means is used to detect that the node 407-A (or 407-B) cannot receive this packet. Thereafter, the node 406 transmits a message (Route Error) indicating that the route 450 is not available according to the procedure shown in Chapter 8.3.4 of Non-Patent Document 1.

  By using the extended function of the present invention described in the first embodiment, the Route Error message includes the group included in the original packet transferred to the destination node 401. The same route information as the route in 461 is included, and on this route, each node between the upstream group boundary node 404 and the source node 406 of the Route Error message refers to this route information. The route in the group 461 is traced in reverse and the Route Error message is transferred. In addition, each node on the route for transferring the Route Error message removes the same information as the route information included in the Route Error message from the accumulated route information.

  Hereinafter, an extended function for the related art made by the present invention will be described.

  FIG. 5 is a flowchart showing processing performed when the group boundary node 404 receives a Route Error message.

  When the upstream group boundary node 404 receives the Route Error message (step S500), the upstream group boundary node 404 that has received the Route Error message in step S501 determines the downstream group boundary node 408 of the group 461 from the accumulated route information. Search for route information that reaches.

  In step S502, it is determined whether or not there is valid route information. If valid route information is stored, the route information is rewritten in step S503, and this flow ends. Specifically, the rewriting of the route information is to use the intra-accumulation group route information as the intra-group 461 route information included in the packet sent to the destination node 401 thereafter.

  If valid route information that can reach the downstream group boundary node 408 cannot be found in the intra-accumulation group route information, a message corresponding to the Route Request message destined for the group boundary node 408 is broadcasted in step S504. To search for a route. Hereinafter, a message corresponding to the Route Request message is referred to as a Route Request 2 message.

  In step S505, it is determined whether or not Route Reply 2 has been received. If Route Reply 2 has not been received, it is determined whether or not a timeout has occurred in step S506. If not timed out, the process returns to step S505 to continue receiving Route Reply2.

  If Route Reply 2 is received in step S505, the storage group internal route is replaced in step S507, and this flow is terminated.

  If a time-out occurs in step S506, a predetermined number of retries are performed in step S508, a Route Error message is transmitted in step S509, and this flow ends.

  For example, by limiting the maximum number of transmission hops of a packet including the Route Request 2 message to a number increased at a specified rate with reference to the number of hops of the original intra-group route (here, 4), the broadcasted packet Can be prevented from being flooded over a wide area of the network, and thus the system throughput can be prevented from being lowered by the control packet. Further, by setting a timeout time according to the limited maximum number of transmission hops, a message corresponding to a Route Reply message to be received as a reply to the Route Request 2 message (hereinafter referred to as a Route Reply 2 message) is not received. Even if it is a case (see NO in step S506), that is, when the route search has failed, the time required for taking the re-search means can be shortened, and thus the time required for the route reconstruction Therefore, the system throughput can be improved by reducing the total time required for packet transmission.

  When the Route Reply 2 message is returned along the route 451 from the downstream group boundary node 408 of the group 461, each node on the route 451 refers to the route information included in the Route Reply 2 message, Forward to 404. At this time, regardless of the description in the first embodiment, the group configuration operation and the path are not selectively accumulated in each node, and in this message according to the conventional technique described in Chapter 82.6 of Non-Patent Document 1. All the route information is stored. The upstream group boundary node 404 that has received the Route Reply 2 message replaces the accumulated route information in the group 461 with the newly discovered route information (see step S507), and thereafter forwards it to the destination node 401. The route information of the packet to be replaced is replaced with the accumulated route information.

  In addition, when the route restructuring means in the group described in this embodiment fails, that is, the Route Reply message returned from the downstream group boundary node 408 of the group 461 in FIG. 4 is received within the predetermined timeout time. In the case of failure (see YES in step S506), the probability of discovery can be increased by repeating a predetermined number of trials (see step S508), and the route can be found by the predetermined number of trials. If not, the packet including the Route Error message is transmitted to the packet transmission source node 400 (see step S509), so that chapters 8.3.4 to 8.3. You can also start rebuilding the entire route according to the prior art procedure described in Chapter 5. wear. In this case, when the Route Error message is received by the group boundary node 404, the transmission source is replaced by replacing the route information in the group 461 included in the packet with the route information in the group 460, contrary to the packet transfer procedure. Packets can be forwarded to node 400.

  As described above, according to the second embodiment, when reachability of a link in a route for transmitting a packet cannot be ensured, when a route is reconstructed, an attempt is made to reconstruct the entire route. Precede attempts to reconstruct routes within a group. This makes it possible to set an optimal maximum hop count limit, so that not only can the system throughput be prevented from dropping, but also the time required for route reconstruction can be reduced because the timeout time can be set short. System throughput can be improved.

(Embodiment 3)
Embodiment 3 includes second route grouping means for grouping routes with a new reference as route grouping means in the processing flowchart shown in FIG. 2 of Embodiment 1. The second route grouping means has the same number of nodes having a group boundary node different from the group formed by the route grouping means (hereinafter referred to as the first route grouping means) in the first embodiment. Are formed (hereinafter referred to as a second route group).

  FIG. 6 is a network diagram showing a group configuration when an example of a desirable calculation method of the routing method according to the third embodiment of the present invention is applied, and is a route composed of groups configured by two route grouping means. Indicates a network with

  In FIG. 6, groups 660 to 662 are groups (hereinafter referred to as a first route group) formed by route grouping means having the calculation method described with reference to FIG. 3 of the first embodiment.

  As a pre-defined calculation method in the second route grouping means, the source node is set to 0, and each node on the route to the destination node is numbered by 1 for each hop, Is multiplied by an integral multiple (including 0, ie, 0, about 3.32, and about 6.63) of the square root of the total number of nodes “11” “11” (about 3.32). Stipulates that two groups not including the source node and the destination node are configured with the node having the number closest to the number obtained by adding about 1.66) (that is, 2, 5, and 8) as the group boundary node To do.

  Group 670 and group 671 are second route groups formed by the second route grouping means. In the second route group, it is assumed that only the group boundary nodes accumulate the routes in the group and accumulate only the routes in the downstream group.

  The operation when the intra-group route reconstruction attempt fails will be described below.

  When a packet transferred along the path 650 from the transmission source node 600 toward the destination node 601 reaches the node 606, the node 606, as described in the first embodiment, stores the group stored in the packet. Referring to the path in 661, the packet is transmitted to the node 607-A to be transferred next. Here, since the node 607-A has already moved to the position indicated by 607-B and is outside the reachable range of the signal transmitted by the node 606, this packet cannot be received. The node 606 that detects this activates the intra-group route reconstruction operation described in the second embodiment, but fails to reconstruct the route to the downstream group boundary node 609 of the group 661.

  In the following, an extended function for the prior art made by the present embodiment will be described.

  The group boundary node 604 that has detected that the intra-group route reconstruction attempt has failed has failed to reconfigure the intra-group route to the node 606 that generated the Route Error message that caused the attempt to reconstruct the intra-group route. Send a message indicating failure. Hereinafter, this message is referred to as a Reroute Failure message.

  The node 606 that has received this Reroute Failure message transmits a message corresponding to the Route Error message to the upstream boundary node of the group to which the node belongs in the second group. Hereinafter, this message is referred to as a Route Error 3 message. In FIG. 6, since the node 606 is a group boundary node in the second group, the following procedure is executed without transmitting the Route Error 3 message.

  When the group boundary node 606 receives the Reroute Failure message or the Route Error 3 message, the node 606 searches the accumulated route information for route information that reaches the downstream group boundary node 609 of the second group 671. When this valid route information is accumulated, a message requesting partial reconstruction of a route including this route is sent from the transmission source node 600 to the node 609 from the upstream group boundary node of the second group. Hereinafter, this message is referred to as a Reroute Request message.

  When effective route information that can reach the node 609 cannot be found in the intra-storage group route information, the route is searched by broadcasting the Route Request 2 message described in the second embodiment with the node 609 as the destination.

  At this time, the maximum transmission hop count of the packet including the Route Request 2 message was broadcast by limiting it to a number increased at a specified rate with reference to the hop count of the original intra-group route (here, 4). It is possible to prevent the packet from being flooded over a wide area of the network, and thus to prevent the system throughput from being lowered by the control packet. Furthermore, by setting a timeout time according to the limited maximum number of transmission hops, even when the Route Reply 2 message is not received as a response to the Route Request 2 message, that is, when the route search fails, the time is re-sent. The time required to take the search means can be shortened, thereby shortening the time required to reconstruct the route, thereby reducing the total time required for packet transmission and system throughput. There is also an effect that can be improved.

  When a Route Reply 2 message is returned from the node 609 along the route 651, each node on the route 651 refers to the route information included in the Route Reply 2 message and transfers this message to the node 606. At this time, regardless of the description of the first embodiment and the description of the prior art described in Chapter 8.2.6 of Non-Patent Document 1, no route information is stored in this message.

  When the node 606 finds valid route information that can reach the node 609 from the accumulated information, or when receiving the Route Reply2 message returned from the node 609, the node 606 finds the route information found from the accumulated information. Alternatively, the Reroute Request including the route information obtained by adding the route information from the upstream group boundary node 604 to the own node accumulated in the own node in the route information from the node 606 to the node 609 notified by the Route Reply 2 message. A message is transmitted to the node 609. The node 609 that has received this Reroute Request message reaches the node 609 from the node 604 included in the received Reroute Request message with the route information from the accumulated route information to the downstream group boundary node of the group to which the node belongs. The route from the node 604 to the node 601 is completed by adding to the route information. Next, the node 609 transmits a message including the completed route information to the node 606. Hereinafter, this message is referred to as a Reroute Reply message.

  Each node that receives the Reroute Reply message refers to the route information from the node 606 to the node 601 included in this message, and transfers this message to the node 606. At this time, each node performs grouping of routes by the group 2 route restructuring means, and performs processing according to the processing flowchart of FIG. 2 in the first embodiment. At this time, the route grouping means is to be read as group 2 route restructuring means, and the calculation method is not necessarily the same.

  For example, as a calculation method in the group 2 route restructuring means, the source node is set to 0, and each node on the route to the destination node is numbered by 1 for each hop, and the route is configured. The group configuration in the case where means for forming two groups having a node having a number closest to one half of the total number of nodes “10” (ie, 5) as a group boundary node is taken as a group 680 in FIG. And Group 681.

  As described above, according to the third embodiment, when reachability of a link in a route for transmitting a packet cannot be ensured, when a route is reconstructed, an attempt is made to reconstruct the entire route. Precede the attempt to reconstruct the route in the second group set in advance. This makes it possible to set an optimal maximum hop count limit, so that not only can the system throughput be prevented from dropping, but also the time required for route reconstruction can be reduced because the timeout time can be set short. System throughput can be improved.

  In addition, the path information accumulated in the group boundary node in the second group that is set to be different from the group boundary node in the first group can reach the downstream group boundary node in the same second group. When routes are accumulated, a new route can be constructed without taking a route search procedure by broadcast transmission. As a result, it is possible to realize the reconstruction of the route in a short period of time as compared with the case where the entire route is reconstructed and only having an extremely small influence on the system throughput.

(Embodiment 4)
In the processing flowchart shown in FIG. 2 of the first embodiment, the fourth embodiment accumulates the upstream intra-group route (step S206) when it knows that its own node position is a group boundary (see YES in step S205). In addition, when a downstream adjacent group further exists in the downstream group of the two adjacent groups to which the node belongs, a means for accumulating the address of the downstream group boundary node of the downstream adjacent group is additionally provided. . FIG. 7 shows a process flowchart in which this address storage means is added.

  FIG. 7 is a flowchart showing processing performed in each node when a Route Reply message is received in the routing method according to the fourth embodiment of the present invention. Steps that perform the same processing as the processing steps shown in FIG.

  When the route in the upstream group is accumulated in step S206, the downstream group boundary node address in the downstream adjacent group is accumulated in step S710, and the process proceeds to step S207. The address accumulating means is processed at the position shown in step S710.

  FIG. 8 is a network diagram showing a group structure when an example of a desirable calculation method of the routing method according to the fourth embodiment of the present invention is applied.

  Hereinafter, the operation of the fourth embodiment when the intra-group route reconstruction attempt described in the second embodiment fails will be described.

  When the packet transferred along the path 850 from the transmission source node 800 toward the destination node 801 reaches the node 806, the node 806 is stored in the packet as described in the first embodiment. The packet is transmitted to the node 807-A to be transferred next with reference to the path in the group 861. Here, since the node 807-A has already moved to the position indicated by 807-B and is outside the reachable range of the signal transmitted by the node 806, this packet cannot be received. The node 806 that detects this activates the intra-group route reconstruction operation described in the second embodiment, but fails to reconstruct the route to the downstream group boundary node 808 of the group 861.

  In the following, an extended function for the prior art made by the present embodiment will be described.

  The group boundary node 804 that has detected that the intra-group route reconstruction attempt has failed has been accumulated in advance, and the downstream group boundary node of the group 862 adjacent to the downstream group 861 to which the own node belongs (in FIG. 8, The address of the destination node) 801 is taken out.

  Next, the node 804 searches for a route by broadcasting a message corresponding to the Route Request message with the extracted node 801 as a destination. Hereinafter, a message corresponding to the Route Request message is referred to as a Route Request 4 message.

  Here, in addition to means for accumulating addresses of downstream group boundary nodes of groups adjacent to the downstream group to which the own node belongs, means for accumulating the number of hops from the own node to the downstream group boundary node is provided. By limiting the maximum number of transmission hops of the packet including the Route Request 4 message to the number increased at a specified rate with reference to the accumulated number of hops (7 in FIG. 8), Can be prevented from being flooded over a wide area of the network, and thus the system throughput can be prevented from being lowered by the control packet. Furthermore, by setting a timeout time according to the limited maximum number of transmission hops, a message corresponding to a Route Reply message transmitted by the node 801 as a response to the Route Request 4 message (hereinafter referred to as a Route Reply 4 message) is received. Even if there is no route search, that is, when the route search fails, it is possible to shorten the time until the re-search means is taken, thereby shortening the time required to reconstruct the route. Therefore, the system throughput can be improved by reducing the total time required for packet transmission.

  When the Route Reply 4 message is returned from the node 801 along the discovered new route 851, each node on the route 851 stores the route information from the node 804 to the node 801 included in the Route Reply 4 message. With reference, this message is forwarded to the node 804. Each node that receives Route Reply 4 performs processing according to the flowchart shown in FIG. 7, and stores only the routes in the group to which the node belongs according to the route grouping means.

  Of the processing contents of the flowchart shown in FIG. 7, the calculation method referred to by the route grouping unit may be a method different from the calculation method exemplified in the first embodiment, and preferably, A method of calculating so as to form two groups configured so that the total number of nodes constituting the newly discovered route 851 is approximately equally divided can be used.

  When the node 804 receives the Route Reply 4 message, a newly discovered route 851 is accumulated instead of the route 850 that is no longer valid. The route 851 is used as a route to be transmitted.

  As described above, according to the fourth embodiment, in the group boundary node, in addition to the path information in the group, the address of the downstream group boundary node of the downstream adjacent group, and preferably from the own node to this downstream group boundary node When the number of hops is accumulated and it is detected that the route used for packet transmission becomes unavailable, a new route is searched for by transmitting a broadcast packet. Thereby, it is possible to shorten the time for finding a route as compared with the conventional technique.

  Further, by limiting the transmission range of the broadcast packet to a range determined based on the accumulated number of hops, the influence on the system throughput can be reduced.

  Further, in order to complete the route reconstruction operation in the prior art, the Route Reply message must be transmitted to the source node, whereas the Route Request 4 message belongs to the node that detected the link breakage. Since the route reconstruction operation can be completed by being transmitted to the group boundary node, it is possible to reduce the necessary time and to reduce the load on the system throughput due to the transmission of the control packet.

(Embodiment 5)
In the fifth embodiment, similarly to the fourth embodiment, when a packet transferred from the transmission source node 800 to the destination node 801 along the path 850 reaches the node 806, the node 806 As described in 1, the packet is transmitted to the node 807-A to be transferred next with reference to the route in the group 861 stored in the packet. Here, since the node 807-A has already moved to the position indicated by 807-B and is outside the reachable range of the signal transmitted by the node 806, this packet cannot be received. The node 806 that detects this activates the intra-group route reconstruction operation described in the second embodiment, but fails to reconstruct the route to the downstream group boundary node 809 of the group 861.

  In the following, an extended function for the prior art made by the present embodiment will be described.

  The group boundary node 804 that detects that the intra-group route reconstruction attempt has failed, extracts the address of the destination node 801 from the route information accumulated in advance.

  Next, the node 804 searches for a route by broadcasting a message corresponding to the Route Request message with the extracted node 801 as a destination. Hereinafter, a message corresponding to the Route Request message is referred to as a Route Request 5 message.

  In this case, in the flowchart of the process to be performed at each node when receiving the Route Reply message shown in FIG. 2 described in the first embodiment, the process of accumulating the upstream intra-group route (step S206 in FIG. 7). At the same time, by providing means for accumulating the number of hops from the own node to the destination node 801, the maximum transmission hop count of the packet including the Route Request 5 message is set to the accumulated hop count (7 in FIG. 8). ) As a standard, it is possible to prevent broadcast packets from being flooded over a wide area of the network by limiting the number to an increased number at a specified rate, and thus to prevent a decrease in system throughput due to control packets. Can do. Furthermore, by setting a timeout time corresponding to the limited maximum number of transmission hops, a message corresponding to a Route Reply message transmitted by the node 801 as a response to the Route Request 5 message (hereinafter referred to as a Route Reply 5 message) is received. Even if there is no route search, that is, when the route search fails, it is possible to shorten the time until the re-search means is taken, thereby shortening the time required to reconstruct the route. Therefore, the system throughput can be improved by reducing the total time required for packet transmission.

  When the Route Reply 5 message is returned from the destination node 801 along the discovered new route 851, each node on the route 851 contains the route information from the node 804 to the node 801 included in this Route Reply 5 message. This message is transferred to the node 804 with reference to FIG. Each node that receives Route Reply 5 performs processing according to the flowchart shown in FIG. 7, and stores only the routes in the group to which the node belongs according to the route grouping means.

  Of the processing contents of the flowchart shown in FIG. 7, the calculation method referred to by the route grouping means can be a method different from the calculation method exemplified in the first embodiment, and preferably the route It is equal to the number of groups existing between the own node 804 and the destination node 801 at 850 (2 in FIG. 8) or close to the average number of nodes included per group (4 in FIG. 8). A method of calculating so as to configure a group of nodes on a newly discovered route 851 can be used. Further, when the same method as in the first embodiment is used as the calculation method, the structures of the Route Request 5 message and the Route Reply 5 message are the same as the structures of the Route Request message and the Route Reply message of the prior art, respectively. A structure can be taken, and no special additional function is required for processing in each node.

  When the node 804 receives the Route Reply 5 message, a newly discovered route 851 is accumulated instead of the route 850 that is no longer valid. Thereafter, a packet forwarded from the source node 800 to the destination node 801 is stored. The route 851 is used as a route to be transmitted.

  As described above, according to the fifth embodiment, when it is detected that the route used for packet transmission is unavailable, the group to which the node that has detected that the route is unavailable is included. A new route is searched for by transmitting a broadcast packet starting from the upstream group boundary node. Thereby, it is possible to shorten the time for finding a route as compared with the conventional technique.

  In addition, when processing a Route Reply message transferred when constructing a route, by configuring the node to accumulate the number of hops from the group boundary node to the destination node, the transmission range of the broadcast packet Is limited to the range determined based on the accumulated number of hops, the influence on the system throughput can be reduced.

  Further, in order to complete the route reconstruction operation in the prior art, the Route Reply message must be transmitted to the transmission source node, whereas the Route Request 5 message is transmitted to the group boundary node that transmitted this message. Since the route reconstruction operation can be completed by being transmitted, the necessary time can be shortened and the load on the system throughput can be reduced by transmitting the control packet.

(Embodiment 6)
In each of the above embodiments, all nodes included in the route are grouped, and routing is reconfigured only within the group. If the problem cannot be resolved within the group, the route from the upstream node of the group to the target node is searched and the group is reconfigured. Groups are configured autonomously according to the contents of the Route Reply option header in DSR. With this configuration, it is possible to include only a part of the route information to be transmitted together with the information to be transmitted, not the information over the entire length of the route, and the route to be accumulated in the nodes constituting the route. Since information can also be reduced, the circuit scale of the hardware constituting the node can be reduced. However, it is conceivable that the conventional example is good when cutting at the boundary point of the group.

  In the sixth embodiment, an example will be described in which another group is virtually created and is switched to a virtual group when disconnected at a boundary point.

  FIG. 9 is a network diagram in which a route is configured by the routing method according to the sixth embodiment of the present invention.

In FIG. 9, the following method is adopted for the case (α) where a route break occurs.
i) If route search within the group fails (β),
ii) In-group re-search (γ) is performed in a route re-search dedicated group (A, B) that is shifted by about ½ of the number of hops in the routing group,
iii) Re-search for the entire route from the transmission source node (conventional technology) only when it fails again.

Thereby, the following effects can be acquired in the route re-search group.
i) Since it can be configured autonomously simultaneously with the routing group, <Effect 1>, <Effect 2> and <Effect 5> described in the first embodiment are not impaired.
ii) Although the route information table size of <Effect 4> described in the first embodiment is inferior to that in the first embodiment, the superiority to the conventional technology is maintained.
iii) Conditions for shortening the reconstruction time of <Effect 3> described in the first embodiment can be greatly expanded.

  The above description is an illustration of a preferred embodiment of the present invention, and the scope of the present invention is not limited to this. For example, it can be applied to a network that implements a routing function using the DSR protocol described in Non-Patent Document 1, but a communication path for transmitting information in a network in which a plurality of nodes are interconnected is used. Any routing method in which each node autonomously selects and communicates may be used, and this includes the case where a higher version is formulated.

  Further, although the names routing method and node device are used in the present embodiment, this is for convenience of explanation, and it is needless to say that it may be a routing group autonomous configuration method or the like.

  Further, the routing method and the components constituting the node device, for example, the types of encryption key generation units, the number thereof, the connection method, and the like may be any.

  The routing method described above is also realized by a program for causing the routing method to function. This program is stored in a computer-readable recording medium.

  As described above, since the routing method according to the present invention can reduce the route information to be accumulated in the node, the circuit scale of hardware constituting the node can be reduced, and the route information included in the packet to be transferred can be reduced. The transmission throughput can be improved because of the reduction, and even when the configured path becomes unusable due to a change in the transmission state, the path can be re-transmitted at a high speed while reducing the amount of control packet transmission. Since it can be constructed, it has the effect of reducing the influence on the system throughput, and is useful as a routing method used in a communication system that performs communication by selecting an optimum communication path.

The network figure which comprised the path | route by the routing method which concerns on Embodiment 1 of this invention The flowchart which shows the process performed in each node, when the Route Reply message of the routing method which concerns on this Embodiment 1 is received. The network figure which shows the structure of a group when the example of the preferable calculation method of the routing method which concerns on this Embodiment 1 is applied. The network figure which reconfigure | reconstructed the path | route by the routing method which concerns on Embodiment 2 of this invention The flowchart which shows the process performed when the group boundary node of the routing method which concerns on this Embodiment 2 receives a Route Error message. The network figure which shows the structure of a group when the example of the preferable calculation method of the routing method which concerns on Embodiment 3 of this invention is applied. The flowchart which shows the process performed in each node, when the Route Reply message of the routing method which concerns on Embodiment 4 of this invention is received. The network figure which shows the structure of a group when the example of the desirable calculation method of the routing method which concerns on this Embodiment 4 is applied. The network figure which comprised the path | route by the routing method which concerns on Embodiment 6 of this invention Network configuration diagram explaining path reconfiguration operation in a conventional network Network configuration diagram explaining path reconfiguration operation in a conventional network

Explanation of symbols

100, 101-110, 300, 301-310, 400, 401-410, 600, 601-610, 620, 621, 622, 623, 800, 801-810, node 150, 350, 450, 451, 650, 651 , 850, 851 route

Claims (29)

In a network in which a plurality of nodes are interconnected, a routing method in which each node autonomously selects a communication path for transmitting information and performs communication,
When a node having a signal to transmit broadcasts a message for searching for a route, and a node to be positioned at the end of the route receives the message, it responds by reversing the route through which the message has passed. Confirming the communication path by replying a message;
The response message includes at least information indicating the number of nodes constituting the route and the position of each node, and each node receiving the response message has two or more nodes based on the information included in the message. Forming a group consisting of:
Each of the configured groups shares a node located at a boundary between adjacent groups, and at least a node located at the boundary between the groups accumulates route information in a group to which the own node belongs at least. Steps,
In a node located at the boundary between groups, information indicating route information in the group is added to information to be transmitted, or information is transferred to the node located at the end of the route by repeating the replacement operation. Step to communicate
A routing method.   2. The routing method according to claim 1, further comprising the step of accumulating path information in both of the two groups to which the node belongs at a node located at a boundary between adjacent groups. And the total no-number integer multiple of the de square root of the number of or the total number of nodes of the square root of the integral multiple group boundary node a node with the number closest to the number obtained by adding one-half of the square root, which constitutes the path it allows routing method of claim 1, further comprising a step that constitutes a group. Performing a calculation to form a group only on nodes that can be destinations of information to be transmitted;
The node that performs the calculation is a group calculated by a response message to a message for searching for a route or a message transmitted to a node that has transmitted a message for searching for the route at a timing close to the response message. Notifying the information to display the configuration;
The routing method according to claim 1, further comprising a step of performing a routing operation in accordance with the displayed group configuration. When transmitting a message including information indicating the calculated group configuration transmitted from the destination node of the signal to be transmitted to the node having the signal,
5. The step of deleting group configuration information related to a route in a direction closer to a destination node than the group boundary node before transmitting the message at a node designated as a group boundary node in the displayed group configuration. Routing method. In addition to information included in a response message to a message for searching for a route, or a message transmitted to a node that has transmitted a message for searching for a route at a timing close to the response message,
The routing method according to claim 1, further comprising a step of determining a group configuration by adding information stored, calculated, measured, or acquired by a node that has received the message. When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
In the group boundary node that has received the message, searching for an alternative route that can reach the group boundary node located at the other end of the group from the accumulated route information; and
The routing method according to claim 1, further comprising the step of using the alternative route thereafter, instead of the route previously used when the alternative route is found. When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
In the group boundary node that has received the message, broadcasting a message for searching for an alternative route that can reach the group boundary node located at the other end of the group; and
When a group boundary node located at the other end receives a message for searching for the route, a step of returning a response message by reversing the route through which the message has passed;
The routing method according to claim 1, further comprising: a step of using the alternative route after the group boundary node receiving the response message instead of the route used previously. Storing in advance the number of nodes constituting the group;
9. The routing method according to claim 8, further comprising the step of setting a limit hop number calculated by a prescribed calculation method based on the number of stored nodes in a message to be broadcasted to search for an alternative route. When a response message to a message broadcast to search for an alternative route is not received within a predetermined timeout period,
9. The routing method according to claim 8, further comprising the step of repeating a broadcast transmission a predetermined number of times.   The routing method according to claim 10, further comprising a step of increasing a limit hop number of information to be broadcasted at a predetermined rate in accordance with the number of times of repeated transmission when broadcast transmission is repeated to search for an alternative route. Configuring two or more overlapping groups on the path that do not share group boundary nodes;
At least one of the two or more groups is used for transmitting information,
8. The routing method according to claim 7, further comprising the step of using a group other than the group used for transmitting the information only in a procedure for searching for an alternative route. If a new route is successfully configured in a group that is used only in the procedure for searching for an alternative route,
In a group used for transmission of information, including a group used only in the procedure for searching for the alternative route,
Sending a message notifying the alternative route to two group boundary nodes not included in the group used only in the procedure of searching for the alternative route;
13. The routing method according to claim 12, further comprising the step of configuring two groups used for transmission of information in a path between the two group boundary nodes. When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
In the group boundary node that has received the message, a group that is adjacent to the group and that is located in the direction in which the information is to be transmitted is an alternative that can reach the group boundary node that is located at the end of the direction in which the information is to be transmitted. Retrieving a route from the accumulated route information; and
The routing method according to claim 1, further comprising: a step of using the alternative route thereafter instead of the route previously used when the alternative route is found. When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
In the group boundary node that has received the message, a group that is adjacent to the group and that is located in the direction in which the information is to be transmitted is an alternative that can reach the group boundary node that is located at the end of the direction in which the information is to be transmitted. Broadcasting a message for searching for a route;
When a border node of the adjacent group receives a message for searching for the route, returning a response message by reversing the route through which the message has passed;
The routing method according to claim 1, further comprising: a step of using the alternative route after the group boundary node receiving the response message instead of the route used previously. If the alternate route is successfully configured,
16. The routing method according to claim 15, further comprising the step of configuring two groups in an alternative path configured between two group boundary nodes. Preliminarily storing the total number of nodes constituting two adjacent groups;
16. The routing method according to claim 15, further comprising the step of setting a limit hop count calculated by a specified calculation method based on a total of the stored number of nodes in a message to be broadcasted to search for an alternative route. When a response message to a message broadcast to search for an alternative route is not received within a predetermined timeout period,
16. The routing method according to claim 15, further comprising a step of repeating a predetermined number of broadcast transmissions. When repeating broadcast transmission to search for alternative routes,
19. The routing method according to claim 18, further comprising a step of increasing the limit hop number of the information to be broadcasted at a predetermined rate in accordance with the number of transmission repetitions. The routing method according to claim 16 , wherein the difference between the number of nodes included in the two groups is 1 or less . When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
In the group boundary node that has received the message, searching for an alternative route that can reach the destination node of the information to be transmitted from the accumulated route information;
The routing method according to claim 1, further comprising the step of using the alternative route thereafter, instead of the route previously used when the alternative route is found. When transmission of information is impossible in one or more links among the links between nodes constituting the route,
A node that detects that the information cannot be transmitted is a group boundary in a direction in which the information to be transmitted is sent from the group to which the node belongs, indicating that the route is not usable. Sending to the node;
The group boundary node that has received the message broadcasts a message for searching for an alternative route that can reach the destination node of the information to be transmitted; and
When the addressed Sakino over de receives a message for searching the route, a step of returning a response message by following the path through the said message to the contrary,
The routing method according to claim 1, further comprising: a step of using the alternative route after the group boundary node receiving the response message instead of the route used previously. Storing in advance the number of nodes constituting the group;
Successful construction of the alternative pathway, in the alternative pathway, the stored routing method of claim 22, further comprising the step of forming the group consisting of the number of nodes of node numbers ± 1. Storing in advance the number of nodes constituting the route from the group boundary node to the destination node;
23. The routing method according to claim 22, further comprising the step of setting a limit hop number calculated by a prescribed calculation method based on the number of stored nodes, in a message that is broadcast to search for an alternative route. When a response message to a message broadcast to search for an alternative route is not received within a predetermined timeout period,
23. The routing method according to claim 22, further comprising the step of repeating a predetermined number of broadcast transmissions. When repeating broadcast transmission to search for alternative routes,
26. The routing method according to claim 25, further comprising a step of increasing the limit hop number of the information to be broadcasted at a predetermined rate in accordance with the number of transmission repetitions.   The routing method according to claim 1, wherein the number of all nodes constituting the route is compared with a predetermined number, and the routing is performed when the number of nodes is a predetermined number or more. A step of claim 7, claim 8 to claim 14 and claim 21, a step of claim 15 to claim 20, a step of claim 22 to claim 26 A plurality of steps of any two or more,
A routing method that activates another step of the plurality of steps or repeats the activated step only when the path reconstructing operation by one step among the plurality of steps fails.   A node device having a function of realizing the routing method according to any one of claims 1 to 28.

Images