JPH11239176A - Ad-hoc network packet routing method - Google Patents

Abstract

(57) [Summary] The present invention relates to a packet routing method for an ad hoc network, in which communication between a calling terminal and a destination terminal is performed even when there are not many fixed relay terminals between the calling terminal and the destination terminal. The purpose is to enable. When a relay terminal detects deterioration of a communication state with an adjacent wireless terminal, the relay terminal sends a first signal P1 to a destination terminal 100 (J), and the destination terminal 100 (J) transmits the first signal P1. When the signal is detected, the second signal P2 is sent to the unspecified wireless terminal.
When the relay terminal detects the second signal P2, it adds the relay terminal identification information and transmits the second signal P2 to an unspecified wireless terminal, and the transmitting terminal 100 (A) transmits the second signal P2 Is detected, the communication route is recognized based on the relay terminal identification information included in the second signal P2.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a packet routing method for an ad hoc network in which a plurality of wireless terminals communicate with each other, and more particularly, to a method for transmitting a data packet between a transmitting terminal and a destination terminal. The present invention relates to control for determining a communication route in an environment where a relay terminal that can relay is movable.

[0002]

2. Description of the Related Art As a prior art of an ad hoc network in which a plurality of wireless terminals communicate with each other, for example, a "wireless data communication method and apparatus and a wireless data communication system" disclosed in JP-A-8-97821 is known.

[0003] In this type of ad hoc network, even if the originating terminal that is the source of the data packet and the destination terminal that is the destination cannot communicate directly due to the distance or the like, the communication between the originating terminal and the destination terminal is not possible. 1 that exists between
When one or a plurality of wireless terminals can be used, data transfer from the calling terminal to the destination terminal is performed by using those wireless terminals as relay terminals for relaying data.

When using a relay terminal, it is necessary to detect an available relay terminal between a calling terminal and a destination terminal and search for an available communication route before starting transmission of a data packet. is there. In Japanese Patent Application Laid-Open No. Hei 8-97821, a communication route is searched as follows. That is, a specific signal frame is transmitted (broadcasted) from an originating terminal to an unspecified wireless terminal. Any wireless terminal that has detected the signal frame transmits the detected signal frame to an unspecified wireless terminal if it is not the destination terminal.

[0005] Therefore, since the broadcast transmission using the relay terminal is repeated in a chain, the signal frame transmitted from the originating terminal reaches the destination terminal. At this time, one communication route is determined so that the wireless terminal used for relaying the signal frame is used as a relay terminal. However, when performing this type of broadcast transmission, since communication occurs in a chain between all wireless terminals that can communicate with each other, communication traffic at each wireless terminal greatly increases.
Therefore, in order to reduce traffic, broadcast transmission at each relay terminal is limited to one time.

[0006] In order to communicate between a calling terminal that cannot directly communicate and a destination terminal, it is assumed that an available communication route actually exists. Therefore, it is necessary that wireless terminals adjacent to each other overlap with each other in a communicable range, and that wireless terminals capable of relaying without interruption are arranged between the calling terminal and the destination terminal.

[0007] For example, a first terminal is located between a calling terminal and a destination terminal.
When the relay terminal and the second relay terminal are present, the communicable ranges of the calling terminal and the first relay terminal overlap, and the first and second relay terminals overlap each other.
If the communicable range of the relay terminal and the second relay terminal overlaps, and the communicable range of the second relay terminal and the destination terminal overlaps, the data transmitted from the originating terminal is transmitted to the first relay terminal. By relaying with the second relay terminal, data can be transferred to the destination terminal.

[0008] When a plurality of communication routes can be selected, even if some relay terminals cannot communicate or a failure occurs, the communication route is searched again, or By using a predetermined alternative route, a communication route can be secured. In the apparatus as described above, a memory for storing a signal frame for route search, an arithmetic unit for performing processing based on information described in the frame, and a programmed logic element or program are provided.

[0009]

In the prior art,
Broadcast transmission of a signal frame performed to secure a communication route is limited to one time. Therefore, in order to reliably relay a signal frame transmitted only once, a large number of relay terminals must be fixedly arranged between the originating terminal and the destination terminal so that the communication ranges overlap with each other.

[0010] If even one of the relay terminals for relaying between the originating terminal and the destination terminal moves out of the predetermined range due to the movement of the specific wireless terminal, the transfer of the data packet between the originating terminal and the destination terminal becomes impossible. Will be possible. In the related art, control processing of a signal frame to be transmitted and received is performed by a dedicated program or a programmed logic element.
It is necessary to construct a dedicated information processing device or application, and there is a problem that the existing wireless communication device cannot be used as it is.

[0011] The present invention relates to a packet routing method for an ad hoc network, wherein even if there are not a large number of relay terminals that are substantially fixed between the originating terminal and the destination terminal, the originating terminal and the destination cannot communicate directly. The main purpose is to enable communication with a terminal.

[0012]

According to a first aspect of the present invention, there is provided a packet routing method for an ad hoc network, wherein at least three wireless terminals each having all functions of transmitting, receiving and relaying a data packet are used to transmit a data packet. The source wireless terminal, the wireless terminal to which the data packet is to be transmitted, and the wireless terminal that relays the data packet are referred to as an originating terminal, a destination terminal, and a relay terminal, respectively, in a case where direct communication cannot be performed between the originating terminal and the destination terminal. Is
A packet routing method for an ad hoc network that specifies a communication route using one or more relay terminals and transfers a data packet using the specified communication route, wherein the relay terminal is adjacent on the specified communication route. When the deterioration of the communication state with the wireless terminal performing the communication is detected, the relay terminal sends a first signal indicating the communication interruption to the destination terminal, and the destination terminal transmits the first signal to the destination terminal.
When detecting the second signal, the destination terminal sends a second signal to the unspecified wireless terminal in order to update the communication route to be used, and the wireless terminal detecting the second signal Is not the calling terminal, the wireless terminal that has detected the second signal transmits the second signal to an unspecified wireless terminal by adding relay terminal identification information that specifies the wireless terminal. If the wireless terminal that has detected the second signal is the calling terminal, the calling terminal may update the communication route updated based on the relay terminal identification information included in the detected second signal. And transmitting the data packet to the destination terminal via the relay terminal of the updated communication route is continued.

When the communication route between the originating terminal and the destination terminal is interrupted due to the movement of the relay terminal or the like, the relay terminal that has detected the communication route sends a first signal to the destination terminal, for example, as a notification packet. In response to this first signal,
A second signal is sent from the destination terminal. That is, a search for a communication route is started from the destination terminal to the calling terminal.

Since the second signal is transmitted from the destination terminal to an unspecified wireless terminal, that is, by broadcast, if a plurality of wireless terminals exist within a communicable range, the plurality of wireless terminals are transmitted. Arrives at the second signal. Since the wireless terminal that has detected the second signal adds relay terminal identification information for identifying the wireless terminal to the second signal to be transmitted, the second terminal that reaches the calling terminal
Includes information on a group of relay terminals that can specify the transfer route of the signal. Therefore, information on available communication routes is secured.

By starting the search for the communication route from the destination terminal, a relay route that ensures that the packet arrives at the destination terminal can be secured. Further, the processing load on the calling terminal is reduced. The relay terminal can detect deterioration of the communication state by periodically monitoring the reception level of a specific radio wave from another adjacent relay terminal. The monitoring target wireless terminal is the immediately preceding relay terminal on the communication route from the calling terminal to the destination terminal.

If the reception level is lower than a predetermined level, it can be determined that the reception level does not exist within the wireless communication range. Record the status of the monitored wireless terminal on the relay terminal,
By comparing the latest reception state with the record, a change in the communication state can be identified. In the prior art, it is assumed that a terminal that relays is arranged in a wireless communication range, but in the present invention, it is assumed that the relay terminal moves freely. That is, even if the relay terminal does not always exist within the communicable range, communication is possible in the present invention.

The above-described various controls can be realized by being installed as middleware in each wireless terminal. The present invention is desirably implemented as middleware. Middleware is software that is located between hardware and application software, and is located above the data link layer in the OSI reference model, which is a hierarchical model of a communication protocol defined by the International Organization for Standardization (ISO). . A service can be realized without adding a necessary function according to a service provided in a lower layer. In addition, even higher-level applications can be realized without making changes or modifications according to the services to be provided.

By realizing the present invention as middleware, wireless packet communication compatible with a dynamic topology using existing wireless terminals becomes possible. By introducing middleware to each wireless terminal for control of the present invention and holding necessary information, the invention can be implemented not only for a specific application or wireless communication device. In addition, the middleware of the destination terminal performs control such as securing a route, so that M
Communication with reduced load on the entire network such as the AC layer and the physical layer can be performed.

According to a second aspect of the present invention, in the packet routing method for an ad hoc network according to the first aspect, the destination terminal or the wireless terminal detecting the second signal detects another wireless terminal capable of communicating under a predetermined condition. If not, the second signal is held, and the second signal is sent when another wireless terminal capable of communicating under the predetermined condition is detected.

Therefore, when there is no available communication route between the originating terminal and the destination terminal due to the movement of the wireless terminal, the second signal is held in any of the relay terminals or the destination terminals, When an available communication route appears, a second signal is transmitted to the relay terminal newly appearing on the communication route, and the search for the communication route is continued. Therefore, even a wireless terminal that moves frequently can be used as a relay terminal. This control can also be realized by the above-described middleware provided in each wireless terminal.

According to a third aspect of the present invention, in the packet routing method for an ad hoc network according to the first aspect, each time the destination terminal generates the second signal, the destination terminal assigns an individual packet identifier to the second signal. The wireless terminal that has detected the signal No. 2 stores the packet identifier given to the detected second signal, and the wireless terminal determines that the packet identifier of the detected second signal matches the stored packet identifier. Is characterized in that the detected second signal is discarded, and if they do not match, the second signal is transmitted to another wireless terminal.

In the case where the broadcast transmission of the second signal is repeated in a chain, the relay terminal and the transmitting terminal transmit the same second signal.
May be repeatedly detected many times. When there are a plurality of communication routes, the transfer time required for each communication route is different from each other. In general, a communication route with a short transfer time requires a small number of relays, a short relay distance, or good communication line quality. Therefore, when the same second signal passing through different paths is repeatedly detected, it is considered preferable to select a route through which the second signal detected first passes.

By discarding the already detected second signal, an increase in communication traffic can be suppressed. Claim 4
In the packet routing method for an ad hoc network according to claim 1, when the originating terminal detects a second signal from the destination terminal, the originating terminal partially updates the second signal. Then, the updated second signal is returned to the destination terminal via a specific wireless terminal corresponding to the relay terminal identification information included in the detected second signal.

For example, when the wireless terminal used for relaying the second signal sent from the destination terminal to the calling terminal is moving, the communication route to which the second signal has been transferred is determined by the passage of time. May not be available. By returning the second signal transferred to the calling terminal to the destination terminal, it is possible to identify whether or not the detected communication route can be continuously used at least twice. Since the calling terminal updates the second signal, the destination terminal can confirm that the second signal has reached the calling terminal.

When the originating terminal returns the second signal to the destination terminal, transmission is performed to a specific wireless terminal corresponding to the relay terminal identification information included in the second signal, that is, transmission is performed by unicast. The traffic generated is minimal. A fifth aspect of the present invention is the packet routing method for an ad hoc network according to the first aspect, wherein the second transfer is performed between the originating terminal and the destination terminal.
The communication route having the shortest time required to transfer the signal is preferentially used.

In general, a communication route having a short transfer time requires a small number of relays, a short relay distance, or good communication line quality. Therefore, when the same second signal passing through different paths is repeatedly detected, it is considered preferable to select a route through which the second signal detected first passes. By realizing the present invention with middleware, existing devices and applications can be used as they are. Further, by reducing the processing in the MAC layer and the physical layer, the load of controlling the entire network and managing routing is reduced.

According to the present invention, even when there is no available communication route, communication is possible by waiting for the relay terminal to enter a wireless communication range. Therefore,
INDUSTRIAL APPLICATION This invention can implement | achieve the communication corresponding to the dynamic topology in which the relay terminal moves freely between the terminals which cannot communicate directly. By using middleware, the present invention can be used in an existing wireless communication system without changing applications and settings, and by introducing middleware having a routing function, a MAC layer and a physical layer, which are lower layers, can be used. Since the burden on the layer can be reduced, the effect of reducing the overall burden on the wireless network environment can be obtained.

Further, according to the present invention, reliable data transmission is possible even if the terminal moves freely. Furthermore, the middleware of the destination terminal performs routing control instead of the calling terminal, so that the burden on the calling terminal can be reduced.

[0029]

DESCRIPTION OF THE PREFERRED EMBODIMENTS One embodiment of the present invention is shown in FIG.
10 to FIG. This form corresponds to all claims.

FIG. 1 is a flowchart showing the contents of control of a calling terminal executed on each wireless terminal embodying the present invention. FIG. 2 is a flowchart showing the contents of control of a relay terminal and a destination terminal executed on each wireless terminal implementing the present invention. FIG. 3 is a flowchart showing the content of the control of the destination terminal executed on each wireless terminal implementing the present invention.

FIG. 4 is a schematic diagram showing an example of a layout of each radio terminal and a packet transfer route when a search for a communication route is performed from the originating terminal to the destination terminal. FIG.
6 is a schematic diagram showing an example of a layout of each wireless terminal and a transfer route of a packet when searching for a communication route from a destination terminal to a calling terminal. FIG. 7 is a map showing the configuration of the control packets P0, P2, P3. FIG. 8 is a map showing a specific example of the control packet P0. FIG. 9 is a map showing a specific example of the control packets P2 and P3. FIG. 10 is a flowchart showing an outline of the operation of each wireless terminal implementing the present invention.

In this embodiment, the wireless terminal, the first signal, the second signal, and the relay terminal identification information in claim 1 are:
Each is embodied as a wireless terminal 100, a notification packet P1, a control packet P2, and a relay terminal identifier group IDR. In this example, since a plurality of wireless terminals 100 are used, if it is necessary to distinguish between them, a code of each wireless terminal 100 is described by adding an identification symbol to each code together with parentheses. Similarly, each wireless terminal 10
When it is necessary to distinguish a wireless packet transmitted from 0, the code of the wireless packet is described by adding the identification code of the wireless terminal 100 that has transmitted the packet together with parentheses.

In this embodiment, radio terminals 100 (A) and 1 (A)
00 (J) is assigned as the originating terminal and the destination terminal of claim 1, respectively. The relay terminal of claim 1 is changed according to the situation. The plurality of wireless terminals 100 (A) to 100 (J) used in this embodiment have all functions as a transmitting terminal that transmits data, a destination terminal that receives data, and a relay terminal that relays data.

The hardware configuration of the wireless terminal 100 is basically the same as that of a general wireless packet terminal device. That is, an antenna, a transmitter, a receiver, a data processing circuit, a display, an input device, a storage device, a digital control unit, and the like are built in the wireless terminal 100. Each wireless terminal 100 performs the processing shown in FIG. 1 and the processing shown in FIG. 2 in order to realize all functions of the calling terminal, the destination terminal, and the relay terminal.
And all of the processing shown in FIG. 3 are executed in parallel.

In this embodiment, FIGS. 1, 2 and 3
Are all implemented as the above-described middleware. If the communicable range of each wireless terminal 100 is not very wide, for example, in FIG. 4, the wireless terminal 100 (A) which is the originating terminal and the wireless terminal 100 (J) which is the destination terminal
It is assumed that data cannot be transferred directly to.

However, the wireless terminals 100 (A) and 100 (J)
Other wireless terminals 100 (B), 100 (D), 1
By using 00 (G) as a relay terminal, data can be transferred from the wireless terminal 100 (A) to the wireless terminal 100 (J). When performing data communication using a relay terminal, to specify the relay terminal to be used and the relay order,
It is necessary to search for a communication route from the calling terminal to the destination terminal in advance to secure the route.

Each radio terminal 100 monitors radio waves from other radio terminals 100 around it, and compares the reception level of the radio waves with a predetermined threshold value so that the monitored radio terminal 100 can communicate. Identify whether it is within the possible range. When recognizing that the wireless terminal 100 (A) as the originating terminal cannot directly communicate with the wireless terminal 100 (J) as the destination terminal, the process proceeds from step 12 to step 14 in FIG. To an unspecified wireless terminal 100.

In the example of FIG. 4, the control packet P0 (A) transmitted from the wireless terminal 100 (A) reaches the wireless terminals 100 (B) and 100 (C). The control packet P0 has a control packet identifier IDP and a creation terminal flag F0 as shown in FIG.
1, a transmission terminal identifier IDS, a destination terminal identifier IDD, a relay terminal identifier group IDR, and a data length LDP.

The control packet identifier IDP is information for distinguishing each control packet P0, P2, P3. The creation terminal flag F01 indicates that each control packet P0, P2, P
3 is binary information indicating either the originating terminal or the destination terminal of the wireless terminal 100 that created the third terminal. The calling terminal identifier IDS is
This is information for specifying the calling terminal. The destination terminal identifier IDD is information for specifying the destination terminal. The relay terminal identifier group IDR is information for specifying one or a plurality of wireless terminals 100 used for relay. Data length L
DP is information indicating the length of transmission data.

As for the control packet P0 (A) transmitted from the wireless terminal 100 (A), as shown in FIG. 8, the relay terminal identifier group IDR does not include any relay terminal information. It turns out to be specific. Therefore,
The wireless terminal 100 (B) receiving the control packet P0 (A)
Proceeding from step 36 to 38 shown in FIG. 2, the control packet P0 (B) is transmitted to the unspecified wireless terminal 100.

As shown in FIG. 8, the identification code "B" of the wireless terminal 100 (B) is added to the relay terminal identifier group IDR of the control packet P0 (B) transmitted by the wireless terminal 100 (B). This process is performed in step 31 of FIG. The control packet P0 (B) transmitted by the wireless terminal 100 (B) is received by the wireless terminal 100 (D) in the example of FIG. Since the next relay terminal is not indicated in the relay terminal identifier group IDR of the control packet P0 (B), the wireless terminal 100 (D) that has received the control packet P0 (B) transmits To transmit the control packet P0 (D) to the unspecified wireless terminal 100.

As shown in FIG. 8, the identification code "D" of the wireless terminal 100 (D) is added to the relay terminal identifier group IDR of the control packet P0 (D) transmitted by the wireless terminal 100 (D). This process is performed in step 31 of FIG. Since the above processing is repeated in a chain, the control packet P0 (G) reaches the wireless terminal 100 (J), which is the destination terminal, as shown in FIG. As shown in FIG. 8, the relay terminal identifier group IDR of the control packet P0 (G) includes identification codes “B, D,
G "is included.

Therefore, an available communication route can be specified from the contents of the relay terminal identifier group IDR of the control packet P0 (G). The control packet P0 including the relay terminal identifier group IDR is returned from the destination wireless terminal 100 (J) to the originating wireless terminal 100 (A). The return of the control packet P0 from the destination terminal to the originating terminal is performed in step 55 of FIG. In this case, the relay terminal that can be used for the return communication can be known from the relay terminal identifier group IDR, so that the destination terminal is a specific wireless terminal 100
Only the control packet P0 is transmitted. That is, the return is performed by unicast communication.

When the wireless terminal 100 (A), which is the originating terminal, receives the returned control packet P0, the wireless terminal 100 (A)
(A) starts transmission of a data packet as shown in FIG. 5 using the communication route indicated by the relay terminal identifier group IDR. On the other hand, the wireless terminal 100 (B), which is a relay terminal,
In step 32 shown in FIG. 2, 100 (D) and 100 (G) identify a relay terminal adjacent to the own station from the contents of the relay terminal identifier group IDR and store it.

Each wireless terminal 100, which is a relay terminal,
Monitors the radio wave from the adjacent relay terminal in step 39. Then, for example, when the reception level of the radio wave falls below a predetermined level, it is detected that communication is impossible. In FIG. 5, the distance between the wireless terminal 100 (D) and the wireless terminal 100 (G) increases due to the movement of the wireless terminal 100 (G), which is a relay terminal, and the communicable ranges of the two do not overlap. Is assumed.

In the state shown in FIG. 5, wireless terminal 100 (G) as a relay terminal detects that communication with wireless terminal 100 (D) as an adjacent relay terminal has become impossible. Therefore, the wireless terminal 100 (G) proceeds from step 40 to 41 in FIG. Therefore, the notification packet P1 is transmitted from the wireless terminal 100 (G) to the wireless terminal 100 (J) as the destination terminal.

In the example of FIG. 5, the notification packet P1 is transmitted from the wireless terminal 100 (G) to the wireless terminal 100 (J) which is the destination terminal.
However, for example, when communication is interrupted between the wireless terminal 100 (B) and the wireless terminal 100 (D), the notification packet P1 is transmitted from the wireless terminal 100 (D) via the wireless terminal 100 (G). To the wireless terminal 100 (J), which is the destination terminal. Upon receiving the notification packet P1, the wireless terminal 100 (J), which is the destination terminal, recognizes that communication has been interrupted in the communication route used so far. And FIG.
From step 56 to step 57.

In this case, since it is necessary to secure a communication route different from the previous communication route, the wireless terminal 100 (J), which is the destination terminal, transmits the control packet P2 created by itself to an unspecified wireless route. The broadcast is transmitted to the terminal 100. In the example of FIG. 5, the control packet P2 (J) is
00 (G), transmitted to the wireless terminal 100 (I). Since the control packet P2 (J) was created by the destination terminal, the creation terminal flag F01 is set to "1" as shown in FIG. Since the communication route has not been determined, the control packet P2 (J)
Of the relay terminal identifier group IDR is cleared. The data length LDP includes the wireless terminal 1 that has been the destination terminal until then.
00 (J) (in this example, “55
0 ”) is set.

The radio terminal 100 (I) that has received the control packet P2 (J) recognizes from the contents of the relay terminal identifier group IDR of the control packet P2 (J) that the communication route has not been determined. Therefore, the process proceeds from step 36 to 38 in FIG.
By executing step 38, the control packet P2 (I) is broadcast from the wireless terminal 100 (I) to the unspecified wireless terminal 100.

As shown in FIG. 9, information "I" for specifying the wireless terminal 100 (I) is added to the relay terminal identifier group IDR of the control packet P2 (I). This addition is performed in step 31 of FIG. 2 executed by the wireless terminal 100 (I).
The broadcast transmission of the control packet P2 is repeated in a chain. In the example shown in FIG. 5, the control packet P2 is
00 (I), the wireless terminal 100 (H), the wireless terminal 100 (E), and the wireless terminal 100 (C) are relayed in this order, and reach the wireless terminal 100 (A) which is the originating terminal.

Relay terminal identifier group ID of control packet P2
R, every time it is relayed, the relayed wireless terminal 10
Information specifying 0 is added. Therefore, the control packet P2 (C) received by the wireless terminal 100 (A) as the originating terminal includes "C, E, H, I" indicating all the relayed wireless terminals 100 as shown in FIG. . Therefore, the wireless terminal 100 (A) as the originating terminal can recognize a new communication route from the contents of the relay terminal identifier group IDR of the control packet P2 (C). After receiving the control packet P2 (C), the wireless terminal 100 (A), which is the calling terminal, transmits a control packet P3 in order to determine a communication route.

That is, since the creation terminal flag F01 of the control packet P2 (C) is "1", the wireless terminal 100 (A) as the originating terminal recognizes that the destination terminal is searching for a new communication route. And steps 17 to 19 in FIG.
Proceed to. In step 19, a control packet P3 (A) is created. Since the control packet P3 (A) is created by the wireless terminal 100 (A) as the originating terminal, the created terminal flag F
01 is cleared to "0". The contents of the relay terminal identifier group IDR of the control packet P3 (A)
Same as (C).

The data length L of the control packet P2 (C)
Since the data transfer of “550” length to the destination terminal has been completed by the DP, the remaining length “450” of the data of “1000” length to be transferred is equal to the control packet P3.
It is set to the data length LDP of (A). Control packet P
The transmission of No. 3 is performed by unicast. That is, since the relay terminal indicating the destination to be transmitted is specified by the relay terminal identifier group IDR of the control packet P3, the transmitting terminal and the relay terminal that has received the control packet P3 are indicated by the relay terminal identifier group IDR. Specific wireless terminal 100
Only the control packet P3 is transmitted.

In the example shown in FIG. 6, the radio terminals 100 (C),
Wireless terminal 100 (E), wireless terminal 100 (H), wireless terminal 10
The control packet P3 is relayed in the order of 0 (I) and the wireless terminal 100 (J), and the control packet P3 reaches the wireless terminal 100 (J) as the destination terminal. When the communication route is determined, the wireless terminal 100 (A), which is the originating terminal, determines the next wireless terminal 100 determined by the contents of the relay terminal identifier group IDR of the control packet P3.
To send a data packet. This data packet reaches the wireless terminal 100 (J), which is the destination terminal, via the relay terminal group indicated in the content of the relay terminal identifier group IDR.

By the way, for example, in the state shown in FIG. 5, when the wireless terminal 100 (H) moves to a position outside the communicable range of the wireless terminal 100 (I), the communication route ahead of the wireless terminal 100 (I) is changed. Since it is interrupted, a new communication route cannot be secured. In the above case, the wireless terminal 100 (I) recognizes that communication with the other wireless terminals 100 is impossible in step 33 of FIG. 2, and proceeds to step 34 via step 35. The wireless terminal 100 (I) holds the control packet P2 to be transmitted in step 34 and waits.

As time elapses, the wireless terminal 100 (I)
When another wireless terminal 100 appears within the communicable range of the terminal, the process proceeds to step 38 via steps 35 to 36.
A control packet P2 is transmitted from the wireless terminal 100 (I) to the appearing wireless terminal 100. Therefore, even in an environment where a communication route cannot be temporarily secured, if the positional relationship between the plurality of wireless terminals 100 changes over time, the available wireless terminal 100 is selected as a relay terminal. Is secured.

When there are a plurality of available communication routes, a communication route having a short transfer time of the control packet P2 is preferentially selected and used. Each wireless terminal 1
00 receives the control packet P2 and stores its control packet identifier IDP. In step 42 of FIG. 2, each wireless terminal 100 compares the stored (previously received) control packet identifier IDP with the control packet identifier IDP of the received control packet.

If the comparison results match, step 4
Go from 2 to 43. In step 43, the received control packet is discarded. That is, the control packet identifier IDP
When the same control packet is received repeatedly, only the previously received control packet P2 is received, and the control packet received later is regarded as unnecessary and is discarded. The following supplements the description of the operation when implementing the present invention.
An outline of the operation is shown in FIG.

In the above route securing process, the originating terminal is notified that the control packet P2 has reached the destination terminal and the route has been secured. In this mode, since the middleware of the relay terminal on the secured route notifies that the route has been secured, it is possible to recognize which relay terminal transmits data to the own terminal. In this mode, all wireless terminals can move freely, and there is no need to fix the wireless terminals within a specific wireless communication range.
Therefore, there is a case where the relay terminal does not exist within the wireless communication range when transmitting the data packet, and the transmission of the data packet becomes impossible.

When data packets are transferred, one-to-one unicast communication is performed between the transmitting terminal and the receiving terminal. Each wireless terminal 100 existing on the communication route
Middleware recognizes the immediately preceding relay terminal on the route. It is possible to recognize whether or not the relay terminal exists within the wireless communication range. At the time of recognition, for example, it is determined whether or not the relay terminal is within the wireless communication range by comparing the reception level of the radio wave with a predetermined threshold.

If the immediately preceding relay terminal on the route does not exist within the wireless communication range, wireless communication cannot be performed. That is, it can be determined that the data packet cannot be transmitted. The middleware recognizing this notifies the destination terminal that the data packet cannot be transmitted by using the notification packet P1. Of course, this information is transferred by a unicast route that has been secured in advance, and arrives at the destination terminal. When the destination terminal recognizes that communication cannot be performed between the relay terminals, the destination terminal transmits the control packet P2 again to the originating terminal to secure the next route.

The control bucket P2 transmitted to the originating terminal is set so that the flag F01 is a control packet generated by the destination terminal, and the data length L
The DP is updated to the data length already transmitted. This control packet allows the calling terminal to know the data length that has reached the destination terminal.

When transmitting the control packet P2 to secure a new communication route, there may be a case where the relay terminal does not exist in the wireless communication range. The control bucket P2 transmitted from the destination terminal is held by middleware. Therefore, by waiting for the relay terminal to appear within the wireless communication range and transmitting the control packet P2 held when the relay terminal appears, it is possible to secure the route again. Also, the same method can be used when transmitting the control packet P0 when the originating terminal secures a route before transmitting data. Therefore, even if the relay terminal moves freely before data transmission, it is possible to secure a route.

When the control packet P2 is successfully transmitted to the transmission terminal by holding the control packet P2 or the like, the middleware of the transmission terminal recognizes the control packet generated by the destination terminal by referring to the flag F01 and notifies the destination terminal of the control packet. The control packet P3 is transmitted again. At this time, the content of the control packet P3 is the same as that of the control packet P2. However, since the data length that has already reached the destination terminal can be known from the transmitted control packet P2, the place where the data length LDP is described is replaced with the remaining data. The value is updated to “1” and the flag “F01” is a value “1” indicating that it is a control packet P3 generated by the calling terminal.
To

Since it is known from the flag F01 that communication between the relay terminals has become impossible during data transmission,
Again, it can be seen that the originating terminal needs to transmit the control packet P3 to secure the route. When the control packet P3 transmitted from the transmission terminal is transferred to the destination terminal again, the destination terminal transmits the control packet again to the transmission terminal by unicast to notify that the route has been secured. Since it is known from the flag F01 that the control packet is generated by the originating terminal, transmission of the remaining data is started.

When the control packet is transmitted to the originating terminal, the route is not secured, and the packet is transmitted to the destination terminal again. When the control packet P2 is transmitted from the destination terminal, the relay terminal must be within the radio communication range. Otherwise, while waiting for the relay terminal to appear, there is a possibility that the relay terminal that has transmitted the control packet to the originating terminal moves and no longer exists within the range.

By transmitting the control packet P3 again from the calling terminal, it can be recognized that the route is not completely secured. The communication route that relayed the control bucket that arrived the earliest from the originating terminal at the destination terminal is the communication route with the shortest transfer delay. By selecting this communication route, data packets can always be transferred in good communication conditions. become.

Control packet P3 transmitted from destination terminal
Even if relaying becomes impossible due to the movement of the relay terminal while transmitting again by unicast from the originating terminal, the control for securing the route from the destination terminal is performed by the above route securing control method. This can be dealt with by transmitting a packet. Transmission of a control packet to a relay terminal within a wireless communication range for securing a new route (step 124 in FIG. 10) and transmission of a control packet to a relay terminal appearing within a wireless communication range (FIG. 10) In step 125), a control packet is transmitted each time a relay terminal appears within the wireless communication range. The relay terminal that has received the control packet beforehand retains the control packet identifier by the middleware in advance. And
When it is recognized that the identifier of the transmitted control packet and the held identifier are the same, the received control packet is discarded (step 128). This makes it possible to prevent waste and loops in the network.

The destination terminal and each middleware are realized by constantly and repeatedly executing the above processing. The processing performed by each middleware is described below. At the originating terminal, when the middleware receives a request for data transmission,
It requests the lower layer to add the data length and the identifier of the originating terminal / destination terminal for transmission.

When it is known from the flag F01 that the control packet transmitted from the destination terminal has been generated by the originating terminal, the middleware requests to transmit data by unicast based on the contents of the relay terminal identifier group IDR. . When the middleware recognizes that the control packet is generated by the destination terminal based on the flag F01, the flag F0
The control packet is transmitted to the destination terminal again by replacing 1 with the value generated by the originating terminal.

When a control packet is transmitted, the relay terminal adds the identifier of its own relay terminal to the control packet and transmits the control packet. At this time, the middleware holds the relay terminal identifier immediately before on the route. Each relay terminal monitors whether the immediately preceding relay terminal on the route corresponding to this information exists in the wireless communication range. If it is found that there is no relay terminal within the range, a notification packet P1 indicating that communication has been disabled is sent to the relay terminal identifier group IDR.
To the destination terminal by the route according to the content of

At the destination terminal, the middleware describes the already transmitted data length LDP in the content of the control packet P0 transmitted from the transmitting terminal and transmits the same to the transmitting terminal (the value of LDP before the start of data transmission is 0). . When a notification packet P1 informs the relay terminal that the terminal is not within the wireless communication range and communication has become impossible, the destination terminal broadcasts a control packet P2. The data length LDP of the control packet P2 is set to the data length already received, and the flag F01 is set to a value "1" indicating that the destination terminal has created the packet.

When the flag F01 is the value "0" created by the originating terminal, the data packet is transmitted by unicast according to the contents of the relay terminal identifier group IDR of the control bucket. Whether or not transmission of all data packets has been completed can be recognized based on the data length of the control packet. By transmitting the data transmission completion to the originating terminal, it is transmitted that the data transmission has been reliably performed.

According to the method described above, wireless communication can be performed using a wireless terminal that moves freely as a relay terminal. This control can be realized by simple processing based on the middleware of each terminal and the contents in the control packet.

[0075]

According to the ad hoc network packet routing method of the first aspect, it is possible to transmit between terminals that cannot directly communicate wirelessly by using a relay terminal. In particular, when realized by middleware having a routing function, the burden on the MAC layer and the physical layer is reduced, so that the burden on the entire network is reduced. Further, the present invention can be realized without using a specific application or setting.

According to the first aspect of the present invention, the second signal corresponding to the control packet is transmitted from the destination terminal even if the communication becomes impossible between the relay terminals during the transmission of the data packet. , A new communication route is secured.
Therefore, even if all the terminals are moving freely, the routing can be secured, and the routing corresponding to the dynamic topology can be supported.

According to the first aspect of the present invention, the routing control is performed by the destination terminal, so that the originating terminal can concentrate on the transmission processing of the data packet, and can surely transmit the data to the destination terminal by checking the data length and the like. Becomes possible. In addition, these controls can be realized without using complicated processing by using middleware and control packets.

According to the second aspect, when a new communication route is secured, if there is no relay terminal within the wireless communication range, the transmitted control packet is held by middleware or the like, and the wireless communication range is maintained. Therefore, a communication route can be secured even in an environment where the relay terminal moves out of the wireless communication range.

According to the third aspect, a control packet is transmitted each time a relay terminal appears within the wireless communication range. Further, the received relay terminal holds the identifier of the previously received control terminal and discards it if it is determined to be the same by comparison with the received control packet, so that it is possible to prevent network transmission waste and loops. .

[Brief description of the drawings]

FIG. 1 is a flowchart showing the contents of control of a calling terminal executed on each wireless terminal embodying the present invention.

FIG. 2 is a flowchart showing the contents of control of a relay terminal and a destination terminal executed on each wireless terminal implementing the present invention.

FIG. 3 is a flowchart showing the content of control of a destination terminal executed on each wireless terminal implementing the present invention.

FIG. 4 is a schematic diagram illustrating an example of a layout of each wireless terminal and a transfer route of a packet when a communication route is searched from a calling terminal to a destination terminal.

FIG. 5 is a schematic diagram illustrating an example of a layout of each wireless terminal and a transfer route of a packet when a communication route is searched from a destination terminal toward a calling terminal.

FIG. 6 is a schematic diagram illustrating a layout of each wireless terminal and an example of a packet transfer path when a search for a communication route is performed from a destination terminal to a calling terminal.

FIG. 7 is a map showing a configuration of control packets P0, P2, and P3.

FIG. 8 is a map showing a specific example of a control packet P0.

FIG. 9 is a map showing a specific example of control packets P2 and P3.

FIG. 10 is a flowchart showing an outline of the operation of each wireless terminal that implements the present invention.

[Explanation of symbols]

 100 Wireless terminal P0, P2, P3 Control packet P1 notification packet

 ──────────────────────────────────────────────────続 き Continuing on the front page (72) Inventor Masahiro Morikura Nippon Telegraph and Telephone Corporation, 3-9-1-2 Nishishinjuku, Shinjuku-ku, Tokyo

Claims (5)

[Claims] 1. A wireless terminal serving as a source of a data packet using at least three wireless terminals each having all functions of transmitting, receiving and relaying a data packet.
The wireless terminal to which the data packet is to be transmitted and the wireless terminal that relays the data packet are referred to as an originating terminal, a destination terminal, and a relay terminal, respectively. A packet routing method for an ad-hoc network that specifies a communication route using the relay terminal and transfers a data packet using the specified communication route, wherein the relay terminal and an adjacent wireless terminal on the specified communication route When the deterioration of the communication state between the relay terminal is detected, the relay terminal sends a first signal indicating communication interruption to the destination terminal, and when the destination terminal detects the first signal, Transmitting a second signal from the destination terminal to the unspecified wireless terminal in order to update a communication route to be used, If the issuing wireless terminal is not the calling terminal, the wireless terminal that has detected the second signal adds the relay terminal identification information that identifies the wireless terminal and adds the second signal to the unspecified wireless terminal. If the wireless terminal that has detected the second signal is the transmitting terminal, the transmitting terminal updates based on the relay terminal identification information included in the detected second signal. A packet routing method for an ad hoc network, comprising: recognizing an updated communication route; and continuing transmission of a data packet to a destination terminal via a relay terminal of the updated communication route. 2. The packet routing method for an ad hoc network according to claim 1, wherein the destination terminal or the wireless terminal detecting the second signal cannot detect another wireless terminal that can communicate under a predetermined condition. Is
A packet routing method for an ad hoc network, comprising: holding the second signal; and transmitting the held second signal when detecting another wireless terminal capable of communicating under the predetermined condition. 3. The packet routing method for an ad hoc network according to claim 1, wherein the destination terminal assigns an individual packet identifier to the second signal each time the second signal is generated, and The wireless terminal that has detected the detected second signal stores the packet identifier given to the detected second signal, and the wireless terminal detects when the detected packet identifier of the second signal matches the stored packet identifier. The second signal is discarded, and if there is no match, the second signal is discarded.
A packet routing method for an ad hoc network, wherein the signal is transmitted to another wireless terminal. 4. The packet routing method for an ad hoc network according to claim 1, wherein when the transmitting terminal detects a second signal from the destination terminal, the transmitting terminal partially converts the second signal. And updating the updated second signal back to the destination terminal via a specific wireless terminal corresponding to the relay terminal identification information included in the detected second signal. Packet routing method for ad hoc networks. 5. The packet routing method for an ad hoc network according to claim 1, wherein a communication route with the shortest transfer time of the second signal transferred between the calling terminal and the destination terminal is preferentially used. A packet routing method for an ad hoc network, wherein the method is used.