Multi-hop wireless communication system and its routing method

【0001】

[Technical field to which the invention belongs]

The present invention relates to a multi-hop wireless communication system and a route selection method thereof, and more particularly to a multi-hop wireless communication system capable of selecting an optimum route based on link quality and a route selection method thereof.

【0002】

[Conventional technology]

With the increase in communication demand, wireless communication tends to use high frequency bands in order to improve the transmission speed. However, in a wireless communication system using a high frequency band, the wireless coverage is narrowed and more base stations are required, which increases the base station installation cost. In order to avoid an increase in cost, it is effective to introduce a multi-hop wireless network system that effectively extends the coverage via a relay station or another terminal even outside the wireless coverage of the base station. In that case, an appropriate route control method (ad hoc routing protocol) is required to increase the system capacity.

【0003】

The IETF's MANET working group has proposed and examined a plurality of ad hoc routing protocols for such a route control method in a multi-hop wireless network.

【0004】

Many of the existing ad hoc routing protocols (AODV, DSR, etc. in MANET) have evolved from the route control of the wired network, and the standard of route selection is the number of hops (= number of transit nodes). In addition, since the network configuration changes dynamically, it is not possible to determine the route in advance using cost as in OSPF, which is a routing protocol for wired networks. Therefore, in a wireless system in which the wireless propagation environment fluctuates significantly and the transmission speed changes adaptively, it is not always possible to perform effective route control.

【0005】

In on-demand ad hoc routing protocols (AODV and DSR) that establish routes according to application layer requests, "route establishment request (= RREQ: Route Request) message" and "route establishment response (= RREP: Route)" A route is established using "Reply) message". FIG. 12 schematically shows a conventional route establishment procedure, and a route is selected by the following procedure. (1) The source node S broadcasts the RREQ message to all terminals within the communication range. (2) The relay node M that receives this RREQ message further broadcasts the RREQ message. In this way, the RREQ message is relayed until it arrives at the destination node D. Note that the relay node M retains the information of the relayed RREQ message, and does not re-relay the already relayed RREQ message. (3) When the RREQ message arrives at the destination node D, the destination node D returns RREP to the source node S of the RREQ message. RREQ messages arriving at destination node D after that are ignored. (4) When the RREP message arrives at the source node S via the relay node M, a route is established between the source node S and the destination node D.

【0006】

Due to such specifications, in the on-demand type ad hoc routing protocol, the route is established based on the control packet that arrives earliest. Here, since the packet propagation time is sufficiently shorter than the relay processing time at the wireless node, as a result, the route with the smallest number of transit nodes (that is, the route with the smallest number of hops) is always established in the prior art. Will be. Therefore, in FIG. 12, the route a capable of direct communication has priority over the route b via the relay node.

【0007】

However, in general, the radio wave is attenuated as the distance between the two points increases, and the quality of the link deteriorates. In FIG. 12, it is assumed that the transmission speed between the node SDs is 1 Mbps. On the other hand, if the distance between the node SM and the node MD is shorter than the distance between the node SD and a speed of 5 Mbps is obtained, the source node S transmits data to the node D via the relay node M. By performing the above, communication can be performed with higher link quality (transmission speed). However, since the link quality is not considered in the prior art, there is a drawback that the route having the minimum number of hops is always selected.

【0008】

Journal of the Society of Electronics, Information and Communication Engineers B Vol.J86-B No.3 pp.322-332 "Proposal and evaluation of route establishment protocol considering node load in high-load ad hoc network" (Nakachu, et al.) The purpose is to distribute the load and improve the data transfer performance of the entire network by intentionally discarding the route establishment request message according to the load of the node, but the route is selected based on the number of hops. Therefore, in an actual environment where the communication speed changes significantly depending on the propagation environment, it is not possible to set the optimum route for link quality.

【0009】

Further, in Japanese Patent Application Laid-Open No. 2001-127797 (ATR Co., Ltd. Environmental Adaptive Communication Laboratory, Mon et al.), In the ad hoc wireless network, the route is re-routed at the time of route interruption by using the terminal information table and the route interruption detection packet. Although the purpose is to shorten the construction time, since the route evaluation criteria uses the number of hops as described above, it is not possible to use an effective route with good link quality.

【0010】

An object of the present invention is to provide a multi-hop wireless communication system and a route selection method thereof that solve the above-mentioned problems of the prior art and enable the establishment of an optimum route in consideration of link quality.

【0011】

[Means for solving problems]

In order to achieve the above object, the present invention relates to a multi-hop radio communication system including a plurality of radio nodes and specifying a route consisting of a source node, a destination node and at least one relay node, and a route selection method thereof. It is characterized by taking the following measures.

【0012】

(1) The source node is a means for transmitting a route request message by designating a destination node, and a route in which a link quality metric of a route from the source node to the destination node is registered in response to the route request message. A means for receiving a response message, a means for generating route information based on the route response message, and a means for comparing the link quality metrics of a plurality of route response messages received in response to the same route request message. Includes means to select a good route for the link quality metric.

【0013】

( 2) The relay node moves from the source node to its own node based on the link quality metric registered in the received route request message and the quality of the link from the node that forwarded the route request message to its own node. A means for obtaining the link quality metric for the route to reach, a means for updating the link quality metric registered in the received route request message to the link quality metric for the route from the source node to the own node, and a means for transferring the received route. Includes means for relaying route response messages.

【0014】

(3) The destination node links the route from the source node to the local node based on the link quality metric registered in the received route request message and the quality of the adjacent link to which the route request message is transferred. The means for obtaining the quality metric, the means for generating the route response message in which the link quality metric from the source node to the own node is registered, and the means for returning the route response message to the source node are the same. A means for comparing the link quality metric from the source node to the own node obtained from the link quality metric registered in the route request message this time when the route request message is received by another route and the link quality metric. Includes means to return a route response message to the current route request message when the current link quality metric is superior to the previous link quality metric.

【0015】

According to the feature of (1) above, when the source node receives the same route response message on a plurality of routes in response to the route request message, the link quality metric can be compared by comparing the respective link quality metrics. You can choose an excellent route.

【0016】

According to the feature (2) above, the relay node can transfer a route request message including a link quality metric of the route from the source node to the own node.

【0017】

According to the feature (3) above, at the destination node, the link of the route to which this route request message is forwarded is based on the link quality metric registered in the received route request message and the link quality metric of the adjacent link. You can know the quality metric. Therefore, when a route request message is received by a plurality of routes, the excellent route of the link quality metric can be determined by comparing the respective link quality metrics.

【0018】

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings. FIG. 1 is a block diagram showing a configuration of a main part of a network terminal (hereinafter, may be referred to as a node) according to the present invention. Here, only the configuration necessary for the description of the present invention is shown, and others. The configuration of is omitted from the illustration.

【0019】

The network I / F1 controls the communication between the node and the network. For example, when a packet is received from an adjacent node, the link quality measurement unit 2 measures the transmission speed and registers the inverse of the measured value as the link quality in the adjacent link management table 503, which will be described later, for each adjacent node. In the present embodiment, the link quality is represented by the transmission speed, but it may be represented by one or more of the received power, the delay time, the remaining amount of the transmission buffer, the bit rate, and the like.

【0020】

As will be described in detail later, when the link quality metric calculation unit 3 receives the RREQ message from the neighboring node, the link quality metric registered in the RREQ message and the link quality metric registered in advance for the neighboring node Based on, the link quality metric from the source node of the RREQ message to the own node is calculated.

【0021】

When the link quality metric calculation unit 3 further receives the RREP message from the adjacent node, the link quality metric is set to the link quality metric registered in the RREP message and the link quality metric from the source node of the RREQ message to the own node. Based on this, the link quality metric from the local node to the destination node is calculated.

【0022】

The routing control unit 4 is a table management unit 403 that controls registration, update, deletion, etc. of data in the RREQ generation unit 401 that generates an RREQ message, the RREP generation unit 402 that generates an RREP message, and each data table 501,502,503 described later. And include.

【0023】

FIG. 2 is a diagram showing the header structure of the RREQ message. In the present embodiment, the conventionally registered destination IP address ADd, destination sequence number Nd_req, source IP address ADs, source sequence number Ns_req, etc. In addition, the link quality metric Qreq from the source node of the RREQ message to the own node calculated by the link quality metric calculation unit 3 is registered.

【0024】

FIG. 3 is a diagram showing the header structure of the RREP message. In the present embodiment, in addition to the conventionally registered destination IP address ADd, destination sequence number Nd_rep, and source IP address ADs, FIG. 3 shows the RREQ message. The link quality metric Qrep from the source node to the destination node is registered.

【0025】

Returning to FIG. 1, the database 5 stores the routing table 501, and the RREQ transfer information table 502 and the adjacent link management table 503 unique to the present invention.

【0026】

As shown in FIG. 4, in the routing table 501, a link quality metric from the local node to the destination node is registered together with the IP address of the transfer destination node and the source sequence number Nrt for each IP address of the destination node. ing. In the RREQ transfer information table 502, as shown in FIG. 5, as transfer information from the source node of the RREQ message to the local node, the source node of the RREQ message, the RREQ_ID, the destination of the RREQ message, and the transfer of the RREQ message are displayed. Along with the original node, the link quality metric from the source node to the local node is registered. As shown in FIG. 6, the adjacent link management table 503 shows the transmission speed when the packet transferred from the adjacent node to the own node is received as the link quality metric Qnext of the radio link from the adjacent node to the own node. Or the reciprocal of it (mean value and / or latest value) is registered for each adjacent link.

【0027】

FIG. 7 is a diagram schematically showing the calculation method of the link quality metric. Here, the transmission speed of the wireless link from the source node S to the relay node M is 5 Mbps, and the destination is from the relay node M. The case where the transmission speed of the wireless link to the node D is 2 Mbps will be described as an example. Each transmission speed is measured in advance by the link quality measuring unit 2 based on packets sent and received between each node, and is registered in the adjacent link management table 503.

【0028】

The link quality metric Qreq of the RREQ message broadcast from source node S is "0". The relay node M that has received this RREQ message reads the transmission speed (5 Mbps) from the corresponding record in the adjacent link management table 503. The link quality metric calculation unit 3 adds the link quality metric Qreq (here, 0) registered in the RREQ message and the reciprocal of the read transmission rate (0.2) to the source node. Find the link quality metric (0.2) from S to relay node M. The RREQ generation unit 401 of the relay node M generates an RREQ message in which the link quality metric Qreq is updated to 0.2, and broadcasts the RREQ message.

【0029】

The destination node D that has received this RREQ message reads the transmission speed (2 Mbps) from the corresponding record in the adjacent link management table 503. The link quality metric calculation unit 3 adds the link quality metric Qreq (here, 0.2) registered in the RREQ message and the reciprocal of the read transmission speed (0.5) to the source node. Find the link quality metric (0.7) from S to destination node D. The RREP generation unit 402 of the destination node D generates an RREP message in which 0.7 is registered as the link quality metric Qrep, and unicasts this to the source node S.

【0030】

In the relay node M that has received this RREP message, the link quality metric Qreq (here, "0.7") registered in the RREP message is linked to the link quality metric (0.2) from the source node S to the relay node M. By subtracting, the quality metric of the radio link from the relay node M to the destination node D is (0.5), and this is registered in the routing table 501. The source node S knows that the quality metric of the radio link from the source node S to the destination node D is (0.7) based on the link quality metric Qreq registered in the received RREP message. Register in the routing table 501.

【0031】

FIG. 8 is a flowchart showing the operation of the RREQ reception process executed at the time of receiving the RREQ at each node. Here, as shown in FIG. 9, the RREQ message transmitted from the source node S to the node D. However, the RREQ reception at each node is based on the case where the RREP message is first received directly to the destination node D and then the RREP message is returned, and then the RREP message is received again to the destination node D via the relay node M and the RREP message is returned. Explain the operation of the time.

【0032】

(1) RREQ message reception processing of relay node M [0033]

As shown in Fig. 10 (a), when the RREQ message is broadcast from the source node S at time t1 and received by the relay node M at time t2 as shown in Fig. 10 (b), the relay node In step M, in step S1, it is determined whether or not the record related to the received RREQ message is registered in the transfer information table 502. Initially, since the same addresses as the source address ADd and the destination address ADs of the RREQ message are not registered in the transfer information table 502, the process proceeds to step S2.

【0034】

In step S2, information about the RREQ message is registered in the transfer information table 502. At this time, based on the link quality metric Qreq registered in the RREQ message and the link quality metric Qnext managed in the adjacent link management table 503, the link quality metric from the source node S to the own node is described. It is obtained by the procedure described with respect to FIG. 7, and this is registered in the link quality metric column of the transfer information table 502.

【0035】

In step S3, the source sequence number Ns_req registered in the RREQ message is compared with the source sequence number Nrt registered in the corresponding record of the routing table 501. Here, if Nreq Nrt, the process proceeds to step S4, and if Ns_req <Nrt, the current RREQ message is ignored. In step S4, the routing table 501 is updated based on the RREQ message. At this time, no data is registered in the link quality metric column of the routing table 501.

【0036】

In step S5, the destination of the received RREQ message is referred to, and since it is determined that the destination is other than the local node, the process proceeds to step S6. In step S6, it is determined whether or not the route information to the destination is already registered in the routing table 501. Since it is determined that the registration has not been performed here, the process proceeds to step S7. In step S7, the received RREQ message is updated and broadcast. In this RREQ message, the link quality metric Qreq is rewritten to the link quality metric from the source node S to the local node.

【0037】

(2) RREQ message reception processing of destination node D [0038]

On the other hand, as shown in FIG. 10 (c), when the RREQ message is received by the destination node D at time t3, the same processing as in the case of the relay node M is executed from steps S1 to S4. .. In step S5, since the destination of the RREQ message is determined to be the local node, the process proceeds to step S9. In step S9, an RREP message in response to the RREQ message is generated and unicast to the source node S at time t4, as shown in FIG. 10 (d). At this time, the link quality metric from the source node S to the own node D calculated by the same procedure as described above is registered in the link quality metric column of the RREP message.

【0039】

Around this time, when the destination node D receives the RREQ message transferred from the relay node M, in step S1, the record related to the received RREQ message is determined to be registered in the transfer information table 502, so the process proceeds to step S21. .. In step S21, the RREQ_ID registered in this RREQ message is compared with the RREQ_ID registered in the corresponding record of the transfer information table 502. If the RREQ_ID of the RREQ message is newer than the corresponding RREQ_ID in the transfer information table 502, the process proceeds to step S23 to update the registered information. If both are the same, the process further proceeds to step S22. If the RREQ_ID of the RREQ message is older than the corresponding RREQ_ID in the transfer information table 502, the current RREQ message is ignored.

【0040】

In step S22, the latest link quality metric from the source node S to the local node D is obtained based on the link quality metric registered in the RREQ message and the link quality metric registered in the adjacent link management table 503. Be done. Then, this latest link quality metric is compared with the corresponding link quality metric already registered in the transfer information table 502. If the latest link quality metric is equal to or better than the registered corresponding link quality metric, the process proceeds to step S23, otherwise the RREQ message is ignored. In step S23, the corresponding record in the transfer information table 502 is updated based on the current RREQ message. At this time, the link quality metric from the source node S to the local node D is registered in the link quality metric column of the transfer information table 502.

【0041】

As described above, in the present embodiment, the RREQ transfer information table in which the transfer information from the source node of the RREQ message to the own node is registered is provided, and after the destination node D returns the RREP message, it is transmitted from the same source node. When the new RREQ message is received again, the quality metric of the radio link established by the previous RREQ message is compared with the quality metric of the radio link established by the current RREQ message. Then, if the quality metric of the wireless link established by this RREQ message is better, the RREP message is returned again in response to this RREQ message.

【0042】

If the route information to the destination node D is already registered in the relay node M in step S6, an RREP message in response to the RRPQ message is generated and unicast to the source node S. At this time, in the link quality metric column of the RREP message, the link quality metric from the source node S to the local node registered in the transfer information table 502 and the local node registered in the routing table 501 The total value with the link quality metric up to the destination node D is registered as the link quality metric from the source node S to the destination node D. The link quality metric from the local node to the destination node D is obtained by the procedure described with respect to FIG. 7, and is registered in the routing table 501 in advance.

【0043】

Next, the operation of each node when the RREP message is received will be described with reference to the flowchart of FIG.

【0044】

(3) RREP message reception processing of source node S [0045]

As shown in FIG. 10D, when the RREP message returned from the destination node D is received by the source node S at time t4, in step S31, information about the RREP message is information about the routing table 501. It is determined whether or not the node has already been registered. Here, since it is determined that the registration has not been performed, the process proceeds to step S34.

【0046】

In step S34, it is determined whether or not the destination of this RREP message is the local node, and here it is determined that the destination is the local node, and the process proceeds to step S35. In step S35, the routing information is newly registered in the routing table 501 based on the RREP message. At this time, the link quality metric Qrep registered in the received RREP message is registered as it is in the link quality metric column. After that, as shown in FIG. 10 (e), a route directly connecting the source node S and the destination node D is established.

【0047】

(4) RREP message reception processing of relay node M [0048]

As shown in FIG. 10 (f), when the RREP message returned from the destination node D is received by the relay node M at time t5, in steps S31 to S33, the same as in the case of the source node S. The process is executed. In step S34, since it is determined that the destination is other than the own node, the process proceeds to step S36. In step S36, the routing table 501 is updated based on the RREP message. At this time, in the link quality metric column of the routing table 501, from the link quality metric Qrep registered in the received RREP message, the source node S to the local node registered in the corresponding record of the transfer information table. The value obtained by subtracting the link quality metric up to M is registered as the link quality metric from the local node M to the destination node D. In step S37, the RREP message is forwarded to the source node S.

【0049】

(5) RREP message re-receipt processing of source node S [0050]

As shown in FIG. 10 (g), when the RREP message transferred from the relay node M is received by the source node S at time t6, in step S31, the record related to this RREP message is stored in the routing table 501. Since it is determined to be registered, the process proceeds to step S32. In step S32, the source sequence number registered in the RREP message is compared with the source sequence number registered in the corresponding record of the routing table. If the source sequence number of the RREP message is newer than the source sequence number of the routing table 501, the process proceeds to step S34. If they are the same, the process proceeds to step S33, and the source sequence number of the RREP message is the source sequence number of the routing table. If it is older than, this RREP message will be ignored.

【0051】

In step S33, the link quality metric registered in the RREP message is compared with the link quality metric registered in the corresponding record of the routing table. If the link quality metric information of the RREP message is superior to or similar to the link quality metric information of the routing table, the process proceeds to step S34, otherwise the current RREP message is ignored.

【0052】

Similarly, in step S34, it is determined whether or not the destination of this RREP message is the own node, and here, it is determined that the destination is the local node, and the process proceeds to step S35. In step S35, the routing information is newly registered in the routing table 501 based on the RREP message. After that, as shown in FIG. 10 (h), a route connecting the source node S and the destination node D via the relay node M is established.

【0053】

As described above, in the present embodiment, when the source node S receives the RREP message and then receives the RREP message by another route, the link quality metric registered in the previous RREP message and the current RREP message are registered. The link quality metric that was used is compared. And if the link quality metric registered in this RREP message is better, the routing table will be updated based on this RREP message.

【0054】

[Effect of the invention]

According to the present invention, the following effects are achieved. (1) At the destination node, the link quality metric of the route to which this route request message is forwarded can be known based on the link quality metric registered in the received route request message and the link quality metric of the adjacent link. .. Therefore, when a route request message is received by a plurality of routes, the excellent route of the link quality metric can be determined by comparing the respective link quality metrics. (2) A route request message including a link quality metric of the route from the source node to the own node can be transferred to the relay node. In addition, since the link quality metric of the route from the own node to the other node is registered, when a route request message destined for the other node is received, the link of the route from the own node to the destination node is received. A route response message with a registered quality metric can be returned. (3) When the source node receives a route response message on multiple routes in response to a route request message, it can select a route with an excellent link quality metric by comparing each link quality metric.

[Simple explanation of drawings]

FIG. 1 is a block diagram showing a configuration of a main part of a network terminal (node) according to the present invention.

FIG. 2 is a diagram showing a header structure of a RREQ message.

FIG. 3 is a diagram showing a header structure of an RREP message.

FIG. 4 is a diagram showing a structure of a routing table.

FIG. 5 is a diagram showing the structure of an RREQ transfer information table.

FIG. 6 is a diagram showing the structure of an adjacent link management table.

FIG. 7 is a diagram schematically showing a method of calculating a link quality metric.

FIG. 8 is a flowchart showing the operation of RREQ reception processing.

FIG. 9 is a diagram showing a transfer route of a RREQ message.

FIG. 10 is a diagram schematically showing a route selection procedure.

FIG. 11 is a flowchart showing the operation of RREQ reception processing.

FIG. 12 is a diagram schematically showing a conventional route establishment procedure.

[Explanation of codes] 1 ... Network I / F, 2 ... Link quality measurement unit, 3 ... Link quality metric calculation unit, 4 ... Routing control unit, 5 ... Database, 401 .. .RREQ generator, 402 ... RREP generator, 403 ... table management, 501 ... routing table, 502 ... RREQ forwarding information table, 503 ... adjacent link management table