JP2002247088A - Wireless node and packet route search method thereof - Google Patents

Abstract

(57) [Summary] [PROBLEMS] When each node frequently communicates with a particular node but does not communicate with other wireless nodes very frequently, the delay until the start of communication is reduced, and The present invention relates to a wireless node and a packet route searching method for the wireless node, which eliminates unnecessary processing or communication and reduces the amount of memory used. SOLUTION: A route to a specific node is always constructed by a table drive type, and in communication from each wireless node to the specific node, a delay from the generation of a communication request to the start of packet transfer is reduced. For other communication modes, by constructing a route on demand, useless processing, communication, and memory usage at each node are reduced. It is characterized in that a specific node can be set regardless of the distance between nodes.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a wireless node which transmits and receives packets via a wireless interface and which can transmit and receive packets via a plurality of wireless nodes, and more particularly to a wireless node which also has a wired interface. The present invention relates to a wireless node configuring a wireless network in which communication with a specific node frequently occurs.
Further, the present invention relates to the packet route searching method.

[0002]

2. Description of the Related Art Conventional wireless nodes (hereinafter referred to as "nodes")
As for packet transfer between packets, there have been proposed a table driving method in which a transfer path is always established, an on-demand method in which a transfer path is established when communication becomes necessary, and a hybrid method in which these are combined.

In the table driving system, when each node periodically or when a change in topology is detected, route information is broadcast to the entire network, and based on the information, each node constantly constructs a route. Although packet transmission can be started immediately when the need arises, processing and communication for unnecessary route construction occur. In the on-demand method, a route search message is broadcast to the entire network when communication becomes necessary, and a route is constructed by returning the response from the destination node, etc., so processing and communication for route construction are not required in normal times. However, there is a delay from the necessity of communication to the start of transfer of the first data packet.

[0004] In order to make up for these drawbacks, Zygm
unt J. Hass, "A New Routing Protocol for the Re
configurable Wireless Networks ", in IEEE ICUPC '97
pp. 562-566, 1997 ".
e Routing Protocol) introduces the concept of zone radius, where each node manages routes to nodes within the zone radius using a table-driven system, and routes to nodes outside the zone radius are constructed on demand. , That is going to be.

For example, assuming that the zone radius is "2 hops", routes from a certain node to all nodes within 2 hops are always constructed. Therefore, when a communication request is issued to a node within two hops, communication can be immediately performed using the route.

On the other hand, when a communication request is issued to a destination node that does not exist within two hops, a route construction request message to the destination node is broadcast to an outer node of the zone, that is, all nodes within the range of just two hops. If the destination node is within two hops of its own node, the outer peripheral node that has received the route construction request message must always construct a route, and transmits a reply message to that effect to the requesting node. As a result, the requesting node knows that "if the packet is transferred to the source outer peripheral node of the reply message, the packet can be transmitted to the destination node", and the route is established. On the other hand, if the destination node is not within two hops of the outer peripheral node that has received the route construction request message, the route construction request message is transferred to all the nodes existing in the outer periphery of the zone of the own node, that is, exactly two hops. . By repeating this, it is possible to construct a route from the source node of the route to the destination node.

FIG. 2 is a network configuration diagram to which a hybrid type packet transfer path construction method of an on-demand system and a table driving system is applied in such a conventional wireless network. Node 500 to Node 630
The node 500 is composed of the nodes 510 and 520, and the node 510 is composed of the nodes 500 and 540.
And the node 560, the node 520 is the node 500, the node 530 and the node 550, the node 530 is the node 520, the node 540 is the node 510, and the node 550.
And node 570, node 550 is node 520 and node 540, node 560 is node 510 and node 630, and node 570 is node 540 and node 5
80 and node 580 are nodes 570 and 590
Are the nodes 630, 600 and 610, the node 600 is the node 590, and the node 610 is the node 5
90 and node 620, and node 620 is node 610
And node 630 can communicate directly with nodes 560 and 590, respectively, over a wireless link. When the zone radius is set to “2 hops”, the zone 700 is the node 500
, A zone within two hops from node 560, and zone 720 represents a zone within two hops from node 590.

At this time, since the path to the node in the zone is always constructed in the node 500, the nodes 510, 520, 530, 540, and 55
0, when a packet transmission request addressed to the node 560 occurs, transmission can be started without delay.

On the other hand, since routes to other nodes are not normally constructed, it is necessary to construct a route after a packet transmission request is generated. For example, when a packet transmission request is issued from the node 500 to the node 620, the node 500 does not exist in the zone.
Nodes 530 and 54 that are the outer nodes of the zone
0, and transmits a route construction request message addressed to the node 620 to the nodes 550 and 560.

The nodes 530, 540, 55
Since the node 620 does not exist in the zone of each node, the node 0 and the node 560 transfer the route construction request message to the outer peripheral node of each zone. For example, the node 560 transfers the data to the nodes 500, 540, and 590.

The node 500 confirms that the route construction request message has been transmitted from its own node, and discards the message. The node 540 confirms that the route construction request message has the same request source and destination as the already received message, and discards the message.

On the other hand, the node 590 unicasts the reply message to the node 560 because the node 620 exists in its own zone. The node 560 that has received the reply message constructs a route to the node 620 based on the information in the message, and transmits a reply message to the node 500. The node 500 receives the reply message, and based on the information in the message, the node 62
Build a path to zero. Thereby, packet transfer from the node 500 to the node 620 becomes possible.

As described above, by combining the table drive type and the on-demand type, the processing, communication, and memory required for constantly building a route are limited to those related to building a route to a node in a zone. In addition, the case where a route is constructed on demand is limited only to the case of communication of a node outside the zone, and the average delay until the start of communication is reduced.

[0014]

As described above, in the conventional hybrid type route construction, the table drive type and the on-demand type are switched according to the distance from the node.
When communication between nodes located at distant distances frequently occurs, a large delay occurs before communication starts, or when communication between nodes located at close distances does not occur much, unnecessary processing at each node and Communication and memory usage occur.

On the other hand, a wireless network and a wired network are connected via a gateway node which is a wireless node also having a wired interface. Many wireless nodes frequently communicate with nodes in the wired network through the gateway node. Considering the form, in such a communication form, communication from each wireless node to the gateway node occurs frequently, and communication between the other wireless nodes does not occur so frequently, regardless of the distance between the nodes. Therefore, in the conventional hybrid route construction, a large delay, wasteful processing at each node, communication, and memory use occur.

For example, in the network shown in FIG. 2, when the zone radius is 2 hops and the nodes 580 and 620 are gateway nodes, a node which is not in the zone of those nodes, for example, the node 500, transmits a wired network through the gateway node. Each time communication with a node in the network is required, a route must be established, and the delay from the occurrence of a packet transfer request to the start of packet transfer increases. Conversely, if the zone radius is increased, each node must constantly construct a route to more nodes, and the processing, communication, and memory required for that will increase.

An object of the present invention is to solve such a conventional problem. In the case where each node frequently communicates with a specific node but does not communicate with other wireless nodes very often, the communication is performed. The present invention relates to a configuration method of a wireless node that reduces delay until start, useless processing in each node, communication, and memory usage.

[0018]

According to the present invention, there is provided a wireless node having means for transmitting and receiving a packet through a wireless interface.
A packet describing "adjacent node to which the packet should be transferred to deliver the packet to a certain destination node" and "a metric which is a value indicating a property of a route through which the packet reaches the destination node through the adjacent node" A means for holding a routing table, which is a set of transfer routes, for relaying packets addressed to other nodes in accordance with the routing table, and when the wireless node itself starts up, or at regular time intervals, or between a specific node Means for broadcasting a specific node investigation message to a node within a range that can be directly communicated by a wireless link when a failure is detected in a route; and a means for transmitting to a specific node held by the wireless node when the specific node investigation message is received. Means for returning a specific node notification message describing the route to the node that transmitted the specific node investigation message; When the node notification message is received, if there is a “route to a specific node not held in the routing table” in the route described in the specific node notification message, the The route is added to the routing table, and the “route to a specific node holding the route in the routing table” exists in the route described in the specific node notification message, and the route is included in the specific node notification message. If the described route has a smaller metric than the route existing in the routing table, the route in the routing table is changed to the route described in the specific node notification message, and the route is added or changed. Means for broadcasting a specific node notification message including a route to a specific node in the routing table to nodes within a range that can be directly communicated by a wireless link; When a packet transfer request to the destination node is generated, if there is no route corresponding to the destination node in the routing table, a route request message directed to the destination node is broadcast to a node in a range that can directly communicate with the wireless link, A node that, when receiving a route response message to the route request message, adds a metric described in the route response message to the route table as a route to the route destination node, When a route request message is received from the router, a route addressed to the transmission node of the route request message is added to the route table using the information in the route request message. If the destination node is a destination node, the route response message is sent to the sending node of the route request message. Means for transmitting the route request message if the wireless node itself is not the destination node, to broadcast the route request message to nodes within a range in which the wireless node can directly communicate with the wireless link.

Further, according to the present invention, in a specific wireless node having means for transmitting and receiving a packet through a wireless interface, "an adjacent node to which the packet should be transferred to deliver the packet to a certain destination node" and "the adjacent node" A metric that is a value that represents the nature of the route through which a packet reaches the destination node through an adjacent node. "
Means for relaying packets addressed to other nodes in accordance with the path table, and a means for relaying a packet addressed to another node according to the path table. Means for broadcasting a specific node notification message indicating that the node itself is a specific node to nodes within a range that can be directly communicated via a wireless link; and checking for a specific node at regular time intervals or when a failure is detected in the path to the specific node. Means for broadcasting a message to a node in a range that can be directly communicated by a wireless link, a route to a specific node held by the wireless node itself when a specific node survey message is received, and the wireless node itself being a specific node. The specific node notification message indicating that the specific node is sent to the node that transmitted the specific node investigation message Means for transmitting, when receiving the specific node notification message, if the “path to the specific node not held in the routing table” exists in the path described in the specific node notification message, The route in the node notification message is added to the routing table, and a “route to a specific node holding a route in the routing table” exists in the routes described in the specific node notification message,
And, when the route described in the specific node notification message has a smaller metric than the route existing in the routing table, the route in the routing table is changed to the route described in the specific node notification message. Means for broadcasting a specific node notification message including a route to a specific node in the routing table to nodes within a range directly communicable by a radio link, when addition or change to the routing table occurs, When a transfer request of a packet to a node occurs, if there is no route corresponding to the destination node in the routing table, a route request message directed to the destination node is broadcast to a node in a range that can directly communicate with a wireless link, When receiving a route response message to the route request message, a transmission node of the route response message; Means for adding the metric described in the above to the route table as a route to the route destination node, and when a route request message from another node is received, using the information in the route request message, While adding the route to the sending node to the routing table,
If the wireless node itself is the destination node described in the route request message, the wireless node transmits a route response message to the transmission node of the route request message; if the wireless node itself is not the destination node, the route request message To
Means for broadcasting to nodes in a range where communication is possible directly with a wireless link.

According to another embodiment of the present invention, the metric of the route is “the number of wireless links through which the route passes” or “the reciprocal of the smallest band among the wireless links through which the route passes”. It is also preferred.

According to another embodiment of the present invention, a flag indicating ON / OFF of a route construction request is provided in a header of a data packet, and when a packet is transferred to a specific node,
A route construction request flag of a data packet transmitted first to the specific node is set to ON, and when a packet whose flag indicating a route construction request is ON is received, the route to the transmission source of the packet is determined by using information in the packet. It is also preferred to construct

According to another embodiment of the present invention, when the specific node notification message is received, the route described in the specific node notification message includes a “route to a specific node not held in the routing table”. , It is also preferable not to add the route when the metric of the route is equal to or more than a certain value.

According to another embodiment of the present invention, when a specific node notification message is received and added to the routing table, only a certain number of routes in the routing table with a smaller metric are left, The remaining routes are deleted from the routing table. As a result, when the content of the routing table changes before and after the reception of the specific node notification message, the specific node notification message including the content of the routing table is wirelessly transmitted. It is also preferable to broadcast to nodes in a range where communication is possible directly with the link.

According to another embodiment of the present invention, when the specific node notification message is received, the transmitting node which has directly transmitted the specific node notification message via the radio link, has already determined which of the routes in the routing table When the transmission node is not registered as a next node or when the transmission node is registered as a next node of any of the routes in the routing table, and the identification of the transmission node is smaller than the metric of the route in the routing table. If the metric in the node notification message is smaller, it is also preferable to make a change to the routing table.

According to the wireless network of the present invention, the wireless node is a gateway node further comprising a plurality of wireless nodes described above, further having a wired interface, and capable of communicating via the wired network.

Further, according to the present invention, in a packet route searching method of a wireless node transmitting and receiving a packet through a wireless interface, the "adjacent node to which the packet is to be transferred in order to deliver the packet to a certain destination node" and the " It holds a routing table, which is a set of packet transfer routes, describing a metric which is a value indicating the nature of a route through which a packet reaches a destination node through an adjacent node, and starts up the wireless node itself. Broadcasting a specific node investigation message to nodes within a range that can be directly communicated by a wireless link, and receiving a specific node investigation message at a time, or at regular time intervals, or when a failure is detected in a path to a specific node. When you do
Returning a specific node notification message describing the route to the specific node held by the wireless node to the node that transmitted the specific node survey message; and If there is a “route to a specific node not held in the routing table” among the routes described in, the route in the specific node notification message is added to the routing table, and the route is added to the specific node notification message. There is a “route to a specific node holding a route in the routing table” among the routes described, and the route described in the specific node notification message is more than the route existing in the routing table. Also, when the metric is small, the route in the routing table is changed to the route described in the specific node notification message, and when addition or change to the routing table occurs, Broadcasting a specific node notification message including a route to a specific node in the routing table to nodes within a range that can be directly communicated by a wireless link, and, when a packet transfer request to a certain destination node occurs, the If there is no route corresponding to the destination node, a route request message directed to the destination node is broadcast to nodes within a range that can be directly communicated via a wireless link, and if a route response message to the route request message is received, A path response message transmitting node, and a step of adding a metric described in the path response message to a path table as a path to the path destination node; and, when a path request message from another node is received, the path request message. Through the route to the transmitting node of the route request message using the information in the Add to the table, and if the wireless node itself is the destination node described in the route request message, transmit a route response message to the transmission node of the route request message, and If not, broadcasting the route request message to nodes within a range that can be directly communicated by a wireless link.

Further, according to the present invention, in a packet route searching method of a wireless node transmitting and receiving a packet through a wireless interface, the “adjacent node to which the packet should be transferred in order to deliver the packet to a certain destination node” and the “ It holds a routing table, which is a set of packet transfer routes, describing a metric which is a value indicating the nature of a route through which a packet reaches a destination node through an adjacent node, and starts up the wireless node itself. At a time or at regular intervals, a step of broadcasting a specific node notification message indicating that the wireless node itself is a specific node to nodes within a range where direct communication is possible via a wireless link; When a failure is detected, a specific node survey message is And a specific node notification message indicating that when the specific node survey message is received, the route to the specific node held by the wireless node itself and that the wireless node itself is the specific node Is returned to the node that transmitted the specific node survey message, and when the specific node notification message is received, the specific node not stored in the routing table is included in the path described in the specific node notification message. If there is a “route to”, the route in the specific node notification message is added to the routing table, and “the route is held in the routing table” in the route described in the specific node notification message. Route to a specific node "
And, when the route described in the specific node notification message has a smaller metric than the route existing in the routing table, the route in the routing table is changed to the route described in the specific node notification message. And when an addition or change to the routing table occurs, broadcasting a specific node notification message including a route to a specific node in the routing table to nodes within a range where direct communication is possible via a wireless link. When a transfer request of a packet to a node occurs, if there is no route corresponding to the destination node in the routing table, a route request message directed to the destination node is broadcast to a node in a range that can directly communicate with a wireless link, When receiving a route response message to the route request message, a transmission node of the route response message; And adding the metric described in the above to the routing table as a route to the route destination node, and when a route request message from another node is received, using the information in the route request message, While adding the route to the sending node to the routing table,
If the wireless node itself is the destination node described in the route request message, the wireless node transmits a route response message to the transmission node of the route request message; if the wireless node itself is not the destination node, the route request message To
Broadcasting to nodes within a range that can be directly communicated by a wireless link.

According to another embodiment of the present invention, the metric of the route is “the number of wireless links through which the route passes” or “the reciprocal of the smallest band among the wireless links through which the route passes”. It is also preferred.

According to another embodiment of the present invention, a flag indicating ON / OFF of a route construction request is provided in a header of a data packet, and when a packet is transferred to a specific node,
A route construction request flag of a data packet transmitted first to the specific node is set to ON, and when a packet whose flag indicating a route construction request is ON is received, the route to the transmission source of the packet is determined by using information in the packet. It is also preferred to construct

According to another embodiment of the present invention, when the specific node notification message is received, the route described in the specific node notification message includes a “route to a specific node not held in the routing table”. , It is also preferable not to add the route when the metric of the route is equal to or more than a certain value.

According to another embodiment of the present invention, when a specific node notification message is received and addition to the routing table occurs, only a fixed number of the routes in the routing table with the smaller metric are left, The remaining routes are deleted from the routing table. As a result, when the content of the routing table changes before and after the reception of the specific node notification message, the specific node notification message including the content of the routing table is wirelessly transmitted. It is also preferable to broadcast to nodes in a range where communication is possible directly with the link.

According to another embodiment of the present invention, when the specific node notification message is received, the transmitting node which has directly transmitted the specific node notification message via the radio link has already determined which of the routes in the routing table. When the transmission node is not registered as a next node or when the transmission node is registered as a next node of any of the routes in the routing table, and the identification of the transmission node is smaller than the metric of the route in the routing table. If the metric in the node notification message is smaller, it is also preferable to make a change to the routing table.

In the wireless node according to the present invention, the path from the generation of a communication request to the start of packet transfer is reduced in the communication from each wireless node to the specific node by always establishing a route to the specific node in a table-driven manner. I do. For other communication modes, by constructing a route on demand, useless processing, communication, and memory usage at each node are reduced. It differs from the prior art in that a specific node can be set regardless of the distance between nodes.

In addition, by constructing a route from a specific node to a certain wireless node at the same time as transmitting the first packet from the wireless node to the specific node, it is possible to return a packet from the specific node to the wireless node without delay. .

[0035]

Embodiments of the present invention will be described below in detail with reference to the drawings.

FIG. 1 is a flowchart for explaining a first embodiment of the present invention, which corresponds to claim 1 or 9.
In the wireless node according to the present embodiment, first, at startup,
After broadcasting the specific node survey message to the nodes that can communicate directly with the wireless link (step 200)
0), and enters an event waiting state (step 2010).

When an event occurs in the event waiting state (step 2020), the type of the event is determined.
(Step 2030). If the event type is a data transmission request, it is checked whether a route to the data destination exists in the routing table (step 2050). If the route exists, the data packet is transferred according to the route table, and the process returns to the event waiting state (step 2080).

If the route does not exist, a route request message is broadcast to a node which can directly communicate with the wireless link (step 2060), and the data is stored in a route construction waiting buffer, and then returns to an event waiting state.
(Step 2070).

On the other hand, if the event type is message reception, the message type is checked (step 2040).

If the message type is the specific node investigation message, the routes to all the specific nodes are extracted from the routing table, and the specific node notification message including the route is transmitted to the transmission source of the specific node investigation message. ,
The process returns to the event waiting state (step 2090).

If the message type is a specific node notification message, it is first checked whether or not a "route to a specific node not held in the routing table" exists in the route in the message (step 2100). If it exists, the route in the specific node notification message is added to the route table (step 2110).

Next, among the routes in the specific node notification message, there is a "route to a specific node held in the routing table and having a metric smaller than the route in the routing table". (Step 2
120). If there is, the route in the route table is replaced with the route in the specific node notification message (step 2130).

Next, step 2110 or 2130
By the operation described above, it is determined whether or not a route has been added or changed to the routing table. If no addition or change has occurred, the process returns to the event waiting state (step 2140).
If an addition or change occurs, the route to all the specific nodes is retrieved from the routing table, a specific node notification message including the route is broadcast to a node that can directly communicate with the wireless link, and an event is waited. Return to the state (step 2090).

If the message type checked in step 2040 is a route request message, a route to the source of the message is first constructed from information in the message.
(Step 2150).

Next, it is confirmed whether or not itself is the destination of the route request message. (Step 2160).

If itself is the destination of the route request message, the route response message is transmitted according to the route constructed in step 2150, and the process returns to the event waiting state (step 2180).

If the node itself is not the destination of the route request message, it broadcasts the route request message to a node which can directly communicate with the wireless link, and returns to the event waiting state (step 2170).

If the message type checked in step 2040 is a route response message, a route to the source of the message is first constructed from information in the message.
(Step 2190).

Next, by referring to the data in the route construction waiting buffer, data whose destination matches the transmission source of the route response message is transmitted based on the route constructed in step 2190, and the process returns to the event waiting state. Step 220
0).

FIG. 3 is a flowchart of another embodiment according to the present invention, which corresponds to claim 2 or 10. FIG.
And FIG. 1 are obtained by comparing step 2000 in FIG. 1 with step 2210 in FIG.
3 differs from FIG. 3 in that it is replaced by step 2220, and therefore only step 2210 and step 2220 will be described.

In the present embodiment, a specific node notification message indicating that it is a specific node at the time of startup is
The broadcast is broadcast to a node which can directly communicate with the wireless link (step 2210).

If the message type checked in step 2040 is a specific node check message, a route to all the specific nodes extracted from the routing table and a specific node notification message stating that it is a specific node are sent. Transmitting the specific node investigation message to the transmission source,
The process returns to the event waiting state (step 2220).

Further, if it is determined in step 2140 that addition / change to the routing table has occurred, a route to all the specific nodes extracted from the routing table and a specific node notification indicating that the node is a specific node are provided. The message is broadcast to a node that can directly communicate with the wireless link, and the process returns to the event waiting state (step 2220).

Next, an example of communication between wireless nodes in a network constituted by a node having the means described in claim 1 and a specific node having the means described in claim 2 will be described. These are the same as the communication between the wireless nodes in the network constituted by the node having the step described in claim 9 and the specific node having the step described in claim 10.

FIG. 4 is a configuration diagram of a network to which communication between wireless nodes is applied using the wireless nodes of the present invention.

This network is composed of a node 10, a node 20, a node 30, a specific node 40, and a specific node 50. The node 10 is connected to the nodes 20 and 11Mb.
In the bandwidth of ps, the node 20 is the node 10 and the specific node 5
In the band of 0 and 11 Mbps and the band of the node 30 and 2 Mbps, the node 30 is in the band of the node 20 and 2 Mbps and in the band of the specific node 40 and 11 Mbps, the specific node 40 is in the band of the node 30 and 11 Mbps and the specific node 50 Is node 2
Direct communication is possible over a wireless link in a band of 0 and 11 Mbps, respectively.

FIG. 5 is an explanatory diagram of a message flow when a certain node starts up in FIG. 4 and a route table to be constructed. This corresponds to the case where the metric of the route is “the reciprocal of the smallest band among the wireless links traversed by the route”. FIG. 4 shows an example of a message flow when the node 30 starts up within a range where the specific node 40 can directly communicate with the wireless link when only the specific node 40 is up, and an example of a route table to be constructed. ing. However, "the reciprocal of the smallest band among the wireless links passed by each route" is used as the metric of each route.

When the node 30 starts up, it broadcasts the specific node inquiry message 400 to nodes that can directly communicate with each other via a wireless link. In this case, the specific node 40 receives this, and the specific node 40 returns to the node 30 a specific node notification message 410 indicating that the own node is the specific node. Node 30 receives message 410
And constructs a routing table 180 according to the contents of the message and the band of the received wireless link. The contents of the routing table 180 can be communicated by designating 40 as the next node in order to communicate with the specific node 40 as a destination, and the metric of the route is 0.09, that is, 11M which is the reciprocal thereof.
It indicates that communication is possible with bps. Further, the node 30 waits for a certain time to confirm that another specific node notification message has not been transmitted. In this case, since other specific node notification messages are not transmitted, the node 30 finally broadcasts the specific node notification message 415 including the contents of the changed routing table to nodes that can directly communicate with the wireless link. The specific node 40 that has received the message 415 confirms that the content of the message 415 is a path relating to the own node, and does not perform any further processing.

As described above, each node transmits the specific node investigation message and the specific node returns the specific node notification message, thereby constructing a route to the specific node in a node which can directly communicate with the specific node via a wireless link. It is possible to

FIG. 6 is an explanatory diagram of the message flow when another node starts up and the route table constructed in FIG. When only the specific node 40 and the node 30 are in the up state, the node 20 is not in the range in which the specific node 40 can directly communicate with the wireless link, but is in the range in which the node 30 can directly communicate with the wireless link. 9 shows an example of a message flow in the case where a message is sent and a route table to be constructed.

At startup, the node 20 broadcasts a specific node investigation message 420 to nodes that can directly communicate with each other via a wireless link. In this case, the node 30 receives this, and the node 30 returns a specific node notification message 430 including the contents of the routing table of the own node to the node 20. The node 20 receives the message 430, and builds the routing table 170 according to the content of the message and the band of the received wireless link. In this case, 0.09 is described as the metric of the route addressed to the specific node 40 in the route in the specific node notification message 430, which represents the reciprocal of 11 Mbps. Since the bandwidth is 2 Mbps, the metric of this route is 0.5, which is the reciprocal of the smaller value of 2 Mbps in the bandwidth.

Therefore, the contents of the route table 170 can be communicated by specifying 30 as the next node in order to communicate with the specific node 40 as the destination, and the metric of the route is set to 0.
5 is represented. Further, the node 20 waits for a predetermined time to confirm that another specific node notification message has not been transmitted. In this case, since another specific node notification message is not transmitted, the node 20 broadcasts the specific node notification message 435 including the contents of the changed routing table to nodes that can directly communicate with each other via the wireless link. The node 30 that has received the message 435 does not perform any further processing because the specific node included in the route in the message 435 is known and its metric is larger than the metric in its own route table.

As described above, it is possible to construct a route to a specific node even in a node that cannot directly communicate with the specific node via a wireless link.

FIG. 7 is an explanatory diagram of a message flow at the time of starting a specific node and a route table constructed in FIG. Specific node 40, node 30, and node 2
When only 0 is in the up state, the specific node 5 is set within a range where only the node 20 can directly communicate with the wireless link.
10 shows an example of a message flow when 0 has risen and a routing table to be constructed.

The specific node 50 broadcasts the specific node notification message 440 to nodes that can directly communicate with each other via a wireless link. In this case, only node 20 receives this. The node 20 receives the message 440, and builds a routing table 171 according to the content of the message and the band of the received wireless link. Compared to the contents of the routing table 170, the contents of the routing table 171 can be communicated by designating 50 as the next node to communicate with the specific node 50 as the destination, and the metric of the route is 0.09. Route has been added.

Next, the node 20 broadcasts a specific node notification message 450 containing the contents of the changed routing table to nodes that can directly communicate with each other via a wireless link. Node 30 and specific node 50 that received message 450
Constructs routing tables 181 and 195 according to the content of the message and the band of the received wireless link, respectively. Then, specific node notification messages 460 and 470 including the contents of the changed routing tables are broadcast to nodes that can directly communicate.

The node 20 that has received the messages 460 and 470 confirms the contents of the message and does not need to change the routing table, so that no further processing is performed. On the other hand, the specific node 40 that has received the message 470 builds the routing table 191 according to the content of the message and the band of the received wireless link, and sends the specific node notification message 480 including the content of the changed routing table to the node that can directly communicate. Broadcast. The node 30 that has received the message 480 checks the content of the message and does not need to change the routing table, so that no further processing is performed.

As described above, each specific node transmits the specific node notification message, so that each node constructs a route to the specific node.

The specific node investigation message and the specific node notification message transmitted and received by each node are as follows.
A routing table can be constructed not only at startup but also by transmitting and receiving at regular intervals. In addition, each node transmits a specific node investigation message when a failure has occurred in the route to the specific node, that is, when communication with the node described in the next node of the routing table has become impossible, thereby reconstructing the route. Is possible.

FIG. 8 is a network configuration diagram when the specific nodes 40 and 50 in FIG. 4 are gateway nodes. This corresponds to claim 8.

In this network, the specific node 4
0, the specific node 50 is a gateway node having a wireless interface and a wired interface, and the specific node 40, the specific node 50, and the wired node 70 can communicate with each other through the wired network 60.

In such a network, as described in the above embodiment, since a path from each node to each specific node is always established, when a packet transmission request to the wired node 70 occurs at each node. In, the transmission of a packet can be started without delay toward either the specific node 40 or the specific node 50. When the specific node 40 or the specific node 50 as the gateway node receives such a packet addressed to the wired node 70 from the wireless interface, the specific node 40 and the specific node 50 may transmit the packet to the wired node 70 through the wired interface.

FIG. 9 is an explanatory diagram of FIG. 4 in which a metric according to the present invention is used as a distance and a route between each node and a specific node is constantly constructed. An example of a routing table constructed by each node at normal time after all nodes have been started is shown. This corresponds to the case where the metric of the route is “the number of wireless links through which the route passes”. That is, information of “distance”, which means “the number of wireless links through each route”, is used as the metric of each route.

The node 10 stores the routing table 110 in the node 2
0 indicates the routing table 120, and the node 30 indicates the routing table 130.
The specific node 40 stores the routing table 140 and the specific node 5
At 0, the routing table 150 is held. For example, the contents of the routing table 130 can be communicated at a distance of 1 by specifying 40 as the next node in order to communicate with the specific node 40 as a destination, that is, direct communication is possible.
To communicate with the destination, if 20 is specified as the next node, it is possible to communicate at a distance of 2. Such a routing table can always be constructed in the same manner as described in the above embodiment.

FIG. 10 is an explanatory diagram of transmission of a route request message when performing communication between nodes according to the present invention. This shows an example of a flow of a route request message and a constructed route table when performing communication from the node 30 to the node 10 in FIG. First, the node 30 refers to the routing table and determines to broadcast the route request message 300 because there is no route to the destination node 10.

FIG. 11 shows the message 30 in FIG.
7 is a configuration diagram of a header of 0. FIG. That is, the destination of the message is node 10, the source of the message is node 30, the node that sent the message on this link is node 30, and the message should be received on this link The number of wireless links through which all nodes traveled before sending this message is 0
And the type of the message is a route request, and the information that the ID of this message is 0077 appropriately given by the node 30 is included.

Specific node 4 that received message 300
0 and the node 20 determine that a route is to be constructed because the type of the message is a route request message, and the source in the message 300 can be reached by the transmission node in the message 300 by the distance +1 in the message 300. That is, by adding the fact that the node 30 can be directly reached to the routing table, the contents of the routing table 144 and the routing table 124 are constructed, respectively. Furthermore, since those nodes do not hold the route information to the node 10, the route request messages 310 and 320 are retransmitted. The messages 310 and 320 are different from the header of the message 300 in the transmitting node and the distance.

The node 30 that has received the messages 310 and 320 ignores this message because the message ID in these messages has the same value as the already transmitted message 300.

On the other hand, the node 10 and the specific node 50 that have received the message 320 decide to construct a route because the type of the message is the route request message, and send the source node in the message 320 By adding to the routing table that the node 30 can be reached at the distance +1 in the message 320 via the node 20, that is, the node 30 can be reached at the distance 2 via the node 20, the contents of the routing table 114 and the routing table 154 are respectively added. To construct. Further, since the specific node 50 does not hold the route information to the node 10, it retransmits the route request message.
That is, the specific node 50 broadcasts the message 330 to a node capable of directly communicating. Message 3
30 is different from the header of the message 320 in the values of the transmission node and the distance. The node 20 receiving the message 330 checks the message ID in the message 330
Is the same value as the already transmitted message 320, and this message is ignored.

On the other hand, since the destination in the message 320 is itself, the node 10 transmits the route response message to the node 3.
It decides to send to 0.

FIG. 12 is an explanatory diagram of transmission of a route response message when performing communication between nodes according to the present invention. This shows an example of the flow of a path response message and a path table constructed at each node at that time.

The node 10 is determined from the routing table 114 to the node 3
The message destined for 0 is transmitted to the node 20 by referring to the fact that it should be transmitted to the node 20, and the path response message 340 indicating that the message is the destination is transmitted to the node 20.

FIG. 13 shows the message 34 in FIG.
7 is a configuration diagram of a header of 0. FIG. That is, the destination of the message is node 30, the source of the message is node 10, the node that sent the message on this link is node 10, and the message should be received on this link The node 20 contains information indicating that the number of wireless links through which this message was transmitted is 0, and that the type of the message is a path response.

The node 20 that has received the message 340
Since the type of the message is a route response message, it is determined that a route is to be constructed, and the source of the message 340 can be reached at the distance +1 in the message 340 via the transmitting node in the message 340, that is, the node A routing table 126 is constructed by adding to the routing table what can be directly reached to 10.

Next, the node 20 refers to the routing table 126 that the wireless node 30 which is the destination of the message 340 is directly reachable, and the transmitting node in the message 340 is set to the node 20 and the receiving node is set to the node 30. , The message 350 with the distance rewritten to 1 is transmitted to the node 30.

Node 30 that has received message 350
Since the type of the message is the route response message, it is determined that a route is to be constructed, and the source in the message 350 can be reached by the distance +1 in the message 350 via the transmitting node in the message 350, that is, the node The route table 136 is constructed by adding to the route table that the device 10 can be reached at the distance 2 via the node 20.

As described above, the routing table 136 and the routing table 12
6, and the entry for the destination 10 and the destination 30 added to the routing table 114, the communication between the node 10 and the node 30 which are not the specific nodes becomes possible.

FIG. 14 is an explanatory diagram of data packet transfer from a certain node to a specific node according to the present invention. This shows an example of a message flow when a packet is transmitted from the node 10 to the specific node 40 in FIG. 9 and a route table to be constructed. This corresponds to claim 4 or 12.

The node 10 refers to the routing table 110 and confirms that the next node to the destination 40 is 20 and the distance is 3. Then, a message 200 including data for the specific node 40 is transmitted to the node 20.

FIG. 15 shows the message 20 in FIG.
7 is a configuration diagram of a header of 0. FIG. That is, the destination is the specific node 40, the source of the message is the node 10, the node 10 transmitted the message on this link, and the node 20 should receive the message on the link. The information includes that the number of wireless links through which this message was transmitted is 0, the type of the message is a data packet, and the route construction flag is ON.

At the node 20 that has received the message 200, the route construction flag is first turned ON, so that the source in the message 200 can be reached via the transmitting node in the message 200 by the distance +1 in the message 200. That is, the route table 122 is constructed by adding the fact that the node 10 can be directly reached to the route table.

Next, it is understood from the routing table 122 that the destination 40 should be sent to the next node 30. Therefore, the message 210 in which only the header of the received message is rewritten is transferred to the node 30.

FIG. 16 shows the message 21 in FIG.
7 is a configuration diagram of a header of 0. FIG. That is, node 20 sent this message on this link and node 3 should receive this message on this link.
It is rewritten with information indicating that the number of wireless links through which the message was transmitted is one.

At the node 30 that has received the message 210, the route construction flag is ON, so that the source of the message 210 can be reached by the distance +1 in the message 210 via the transmitting node in the message 210. That is, the route table 132 is constructed by adding to the route table that the node 10 can be reached at the distance 2 via the node 20.

Next, since it is known from the routing table 132 that direct communication is possible to the destination 40, the message 220 in which only the header of the received message is rewritten is transferred to the specific node 40.

FIG. 17 shows the message 22 in FIG.
It is a block diagram of a 0 header. That is, node 30 sent this message on this link and node 40 should receive this message on this link.
And the number of wireless links through which this message was transmitted is two.

Specific node 4 receiving message 220
At 0, the route construction flag is ON, so that the source in the message 220 can be reached by the distance +1 in the message 220 via the transmitting node in the message 220, that is, the node 10 can be reached via the node 30. The route table 142 is constructed by adding the information that can be reached with the number of via hops 3 to the route table.

Finally, since the destination in the message 220 indicates itself, the specific node 40 can process the received message, and the data transmission from the node 10 to the specific node 40 is completed. Also, the routing table 122,
By using the entry relating to the destination 10 added to the routing table 132 and the routing table 142, a reply message to the message 220 can be transmitted from the specific node 40 to the node 10 in reverse.

As described above, packets can be transmitted from each node to a specific node by using the routing table that is constantly constructed, and the route construction flag of the packet to be transmitted is set to ON.
By doing so, a route from a specific node to each node can also be constructed.

FIG. 18 is a block diagram of a network to which the method for constructing a packet transfer route in a wireless network according to the present invention is applied, which corresponds to claims 5 to 7 or 13 to 15.

This network is connected to specific nodes 800 to 8
30, the specific node 800 is the node 840, the specific node 810 is the node 840 and the node 850, the specific node 820 is the node 850 and the node 860, and the specific node 830 is the node 860. The node 840 is the specific node 800, the specific node 810 and the node 880, the node 850 is the specific node 810, the specific node 820, the node 880 and the node 890, the node 860 is the specific node 820, the specific node 830 and the node 890, Node 880 can communicate directly with nodes 840 and 850, and node 890 can communicate directly with nodes 850 and 860 via wireless links, respectively.

Here, it is assumed that a node other than the node 890 has already started up and a route to a specific node has been constructed, and the node 890 has finally started up.

FIG. 19 corresponds to claim 5 or claim 13.
FIG. 2 is an explanatory diagram of a message flow according to a packet transfer path construction method in a wireless network of the present invention and a constructed path table. An example is shown in which “distance” meaning “the number of wireless links passed by each route” is used as a route metric, and each node does not hold a route to a specific node whose distance is 3 or more in a routing table. .

The node 890 broadcasts the specific node survey message 910 to nodes that can directly communicate with each other via a wireless link. The nodes 850 and 860 that have received this transmit a specific node notification message including the path information in the path table of the own node to the node 890. For example, the node 850 has a route to the specific node 810 and the specific node 820 which are the specific nodes within the distance 2 in the route table 1000, and transmits a specific node notification message 920 including the route to the specific node. Similarly, the node 860 has the route to the specific node 820 and the specific node 830 which are the specific nodes within the distance 2 in the route table 1015, and transmits the specific node notification message 930 including the route to the specific node.

The node 890 first receives the specific node notification message 920, and since the distance to the specific nodes 810 and 820 is within two, the specific node 81
Add routes to 0 and 820. Next, the specific node notification message 930 is received, and since the distance to the specific node 830 is within 2, the route to the specific node 830 is added to the routing table, and the routing table 1010 is constructed. The route to the specific node 820 does not need to be particularly changed because the metric of the route in the routing table and the metric of the route in the message 930 are the same.

Thereafter, the node 890 waits for a certain period of time to confirm that another specific node notification message has not been transmitted, and can directly communicate the specific node notification message 940 including the updated contents of the routing table via a wireless link. Broadcast to the nodes, ie, nodes 850 and 860. For example, node 850 sends message 9
40 is received, and it is confirmed that a route relating to the unknown specific node 830 is included therein. However, since the distance is 3, this route is not added to the routing table. Therefore, no further message transmission is performed.

As described above, by restricting whether or not to hold a route by the metric “distance”,
Each node does not need to always have a route to all the specific nodes in the network, and the amount of memory can be reduced.
In addition, when the specific node notification message is received, if these restrictions are not set, the necessary processing and message transmission become unnecessary, and the processing amount and the message at the node necessary for constantly building the route to the specific node are eliminated. The traffic is also reduced.

FIG. 20 corresponds to claim 6 or claim 14.
FIG. 2 is an explanatory diagram of a message flow according to a packet transfer path construction method in a wireless network of the present invention and a constructed path table. FIG. 20 is a diagram showing a configuration of the node 8 in FIG.
Regarding the message flow and the route table to be constructed when the message 90 finally starts up, “distance”, which means “the number of wireless links through which each route passes”, is used as the route metric, and each node specifies up to three nodes. This shows an example in which a route to a node is stored in a routing table.

The node 890 broadcasts the specific node inquiry message 950 to nodes that can directly communicate with each other via a wireless link. The nodes 850 and 860 that have received this transmit a specific node notification message including the path information in the path table of the own node to the node 890. For example, the node 850 has three routes to the specific node 800, the specific node 810, and the specific node 820 in the route table 1020, and transmits a specific node notification message 960 including the routes to the specific nodes.
Similarly, the node 860 transmits the specific node notification message 9 including the paths to the specific node 820 and the specific node 830.
Send 70.

The node 890 first receives the specific node notification message 960, and specifies the specific nodes 800, 810 and 8
The route to 20 is added to the routing table. Next, the specific node notification message 970 is received, and the specific node 830 is added to the routing table.
Add a route to. However, the maximum path that can be held is 3
Therefore, the node 890 deletes the metric, that is, the route to the specific node 800 having the largest distance from the routes, and builds the route table 1030 as a result.

Next, the node 890 waits for a certain period of time to confirm that another specific node notification message has not been transmitted, and then directly communicates the specific node notification message 980 including the contents of the changed routing table via a wireless link. Broadcast to the possible nodes, namely node 850 and node 860. Node 850 sends message 980
And confirms that a route to the unknown specific node 830 is included therein, and adds the route to the route table. However, since the maximum number of routes that can be held is 3, the metric is Specific node 830, which is one of the largest routes
Remove route to. As a result, in the node 850, since the routing table is not changed before and after the reception of the specific node notification message, no further message transmission is performed.

On the other hand, the node 860 receives the specific node notification message 980, and adds a route to the unknown specific node 810 included in the message 980 to the routing table. In this case, since the number of routes does not exceed the maximum storable number of 3, the route table is changed at the node 860 before and after receiving the specific node notification message, and as a result, the route table 1040 is constructed. Further, the specific node notification message 990 including the information of the route table after the change is broadcast to the nodes that can directly communicate with each other via the wireless link, that is, the specific node 830 and the node 890.

Since the route in the message 990 is already known at the node 890, no further message transmission is performed. On the other hand, the specific node 830 constructs a route to the specific node 810 in the routing table in accordance with the content of the message 990, and broadcasts the specific node notification message 995 including the changed route information to a node that can directly communicate with the wireless link. I do. The node 860 that has received the message 995 does not perform any further message transmission since all the paths in the message 995 are known.

As described above, by limiting the number of routes held in the routing table, each node does not need to always have routes to all the specific nodes in the network, and the amount of memory can be reduced. . In addition, when the specific node notification message is received, if these restrictions are not set, the necessary processing and message transmission become unnecessary, and the processing amount and the message at the node necessary for constantly building the route to the specific node are eliminated. The traffic is also reduced.

FIG. 21 corresponds to claim 7 or 15.
FIG. 2 is an explanatory diagram of a message flow according to a packet transfer path construction method in a wireless network of the present invention and a constructed path table. FIG. 21 is a diagram showing the configuration of the node 8
Regarding the message flow and the route table to be built when the node 90 finally starts up, “distance” meaning “the number of wireless links through which each route passes” is used as the route metric, and each node “ This is an example of a case where a “route having a node” is stored in a routing table.

The node 890 broadcasts the specific node survey message 1100 to nodes that can directly communicate with each other via a wireless link. The nodes 850 and 860 that have received this transmit a specific node notification message including the path information in the path table of the own node to the node 890. For example, the node 850 has the route to the specific node 800, the specific node 810, and the specific node 820 in the route table 1200, and transmits the specific node notification message 1110 including the route to the specific node. Similarly, the node 860 has the route to the specific node 820 and the route to the specific node 830 in the route table 1220, and transmits the specific node notification message 1120 including the route to the specific node.

The node 890 first receives the specific node notification message 1110, and among the routes to the specific nodes 800, 810 and 820, the metric, that is, the route to the specific node 810, which is one of the routes with the shortest distance. Is added to the routing table. Next, specific node notification message 1
120, the route to the specific node 830, which is one of the routes having the shortest distance, among the routes to the specific nodes 820 and 830, is added to the route table. To construct.

Next, the node 890 waits for a predetermined time to confirm that another specific node notification message has not been transmitted, and broadcasts the specific node notification message including the updated contents of the routing table.

FIG. 22 shows a flow of such a message and an example of a route table to be constructed, following FIG.

The node 890 broadcasts the specific node notification message 1130 to nodes that can directly communicate with each other via a wireless link, that is, the nodes 850 and 860. The node 850 receives the message 1130, confirms that there is no route in the routing table with the node 890 being the transmitting node as the next node, adds the route, and adds the route.
Build 240. Similarly, node 860 sends message 1
130 is received, it is confirmed that there is no route in the routing table with the node 890 as the transmission node as the next node, and a route is added to construct the routing table 1250.

As a result, both the node 850 and the node 860 change the routing table. Therefore, a specific node notification message reflecting the contents of the routing table is broadcast to nodes that can directly communicate with each other via the wireless link. Specific node notification message 1140 transmitted by node 850
Are the specific nodes 810, 820, 88
0 and the node 890 receive, but since there is already a route with a smaller metric in the routing table, the node 850 being the next node, no further message transmission is performed. For example, since the specific node 820 holds a path as shown in the path table 1260, it is not necessary to construct a path with the node 850 as the next node. Similarly, the specific node notification message 1150 transmitted by the node 860 is received by the specific node 820, the specific node 830, and the node 890, but these nodes do not transmit any more messages.

In this way, by limiting one next node to construct a route to only one specific node, each node does not need to always have a route to all the specific nodes in the network. The amount of memory can be reduced. In addition, when the specific node notification message is received, if these restrictions are not set, the necessary processing and message transmission become unnecessary, and the processing amount and the message at the node necessary for constantly building the route to the specific node are eliminated. The traffic is also reduced.

[0123]

As described above, according to the present invention, as described in claim 1 or 9, even if a specific node exists at any distance from each node, a route from each node to the specific node is determined. Since the communication is always established, communication can be executed without delay. In addition, since a path from each node to a node other than a specific node is constructed when it becomes necessary, extra processing, communication, and use of memory are not required.

Further, as described in claim 4 or 12, a route from a specific node to each node is constructed simultaneously with transmission of the first data packet when communication from each node to the specific node occurs. As a result, it is possible to execute subsequent communication from the specific node to each node without delay without wasting a memory for constructing an extra route in the specific node or each node.

Further, as described in claims 5 to 7 or 13 to 15, by limiting the route to a specific node which is always held by each node, when there are many specific nodes in the wireless network, all It is possible to reduce the amount of processing, the amount of message communication, the amount of memory consumed, and the like at each node, as compared with the case where a route to a specific node is constantly constructed.

In particular, considering a gateway node which is a connection point with a wired network as a specific node, and an access network accommodating various terminals through a wireless network, a specific node transmits through a gateway node. Since access to the wired network occurs frequently, it is preferable that a route from each terminal to the gateway node is always established regardless of the distance, and communication can be started immediately when a communication request occurs.
However, it is considered that communication in other combinations of terminals is not likely to occur frequently. Therefore, it is not preferable to always establish a path for such communication because processing, communication, and memory are wasted. Also, in such a case, routes to all specific nodes are not necessarily required,
It suffices if access to the wired network can be executed through any specific node.

Therefore, the present invention accommodates many terminals in a wireless multi-hop connection through a gateway node.
In a wireless access system, this is effective when it is desired to execute a route construction in which the required processing, communication, and memory usage are reduced in each node while reducing the delay from the generation of many communication requests to the start of transfer.

[Brief description of the drawings]

FIG. 1 is a flowchart corresponding to claim 1 and illustrating a first embodiment of the present invention.

FIG. 2 is a network configuration diagram to which a conventional method is applied.

FIG. 3 is a flowchart of another embodiment according to the present invention, which corresponds to claim 2 or 10;

FIG. 4 is a configuration diagram of a network to which communication between wireless nodes is applied using the wireless nodes of the present invention.

FIG. 5 is an explanatory diagram of a message flow when a certain node starts up and a route table to be constructed in FIG. 4;

FIG. 6 is an explanatory diagram of a message flow when another node starts up and a route table constructed in FIG. 4;

FIG. 7 is an explanatory diagram of a message flow at the time of starting a specific node and a constructed route table in FIG. 4;

FIG. 8 is a network configuration diagram when a specific node is a gateway node in FIG. 4;

FIG. 9 is an explanatory diagram in which a metric according to the present invention is distance and a route between each node and a specific node is constantly constructed.

FIG. 10 is an explanatory diagram of transmission of a route request message when performing communication between nodes according to the present invention.

11 is a configuration diagram of a header of a message 300 in FIG.

FIG. 12 is an explanatory diagram of transmission of a route response message when performing communication between nodes according to the present invention.

FIG. 13 is a configuration diagram of a header of a message 340 in FIG.

FIG. 14 is an explanatory diagram of data packet transfer from a certain node to a specific node according to the present invention.

FIG. 15 is a configuration diagram of a header of a message 200 in FIG. 14;

16 is a configuration diagram of a header of a message 210 in FIG.

FIG. 17 is a configuration diagram of a message 220 header in FIG.

FIG. 18 is a configuration diagram of a network to which a method for constructing a packet transfer path in a wireless network according to the present invention is applied, which corresponds to claims 5 to 7 or 13 to 15;

FIG. 19 is an explanatory diagram of a message flow according to the packet transfer route construction method in the wireless network of the present invention and a route table to be constructed, corresponding to claim 5 or 13;

FIG. 20 is an explanatory diagram of a message flow according to a packet transfer route construction method in a wireless network according to the present invention, and a constructed route table.

FIG. 21 is an explanatory diagram of a message flow according to the method for constructing a packet transfer route in a wireless network according to the present invention and a route table to be constructed.

FIG. 22 is an explanatory view following the explanatory view of FIG. 21;

 ────────────────────────────────────────────────── ─── Continuing from the front page (72) Inventor Hiroto Suda 2-3-1 Otemachi, Chiyoda-ku, Tokyo F-term in Nippon Telegraph and Telephone Corporation (reference) 5K030 GA12 HA08 JL01 KA05 LB05 LD02 5K033 AA06 CB13 CC01 DA05 DA17

Claims (15)

[Claims] 1. A wireless node having means for transmitting and receiving a packet through a wireless interface, comprising: an "adjacent node to which the packet is to be transferred in order to deliver the packet to a destination node"; and a "packet to the destination node through the adjacent node." Means for holding a route table, which is a set of packet transfer routes, describing a metric which is a value representing the property of a route through which the packet arrives, and relaying a packet addressed to another node in accordance with the route table. Means for broadcasting a specific node survey message to a node in a range directly communicable by a wireless link, at the time of startup of the wireless node itself, at regular intervals, or when detecting a failure in a path between the specific node and When the specific node survey message is received, the route to the specific node held by the wireless node is received. Means for returning a specific node notification message describing the path to the node that transmitted the specific node investigation message; and, when the specific node notification message is received, the path included in the specific node notification message includes " If there is a “route to a specific node that is not held in the routing table”, the route in the specific node notification message is added to the routing table, and “the route described in the specific node notification message is included in the route. If there is a “route to a specific node holding a route in the routing table” and the route described in the specific node notification message has a smaller metric than the route existing in the routing table, The route in the table is changed to the route described in the specific node notification message, and when addition or change to the route table occurs, the route to the specific node in the route table is changed. Means for broadcasting a specific node notification message including a route to a node within a range in which communication is possible directly via a wireless link; and when a transfer request of a packet to a certain destination node occurs, a route corresponding to the destination node is displayed in the routing table. When there is no route request message, the node broadcasts a route request message directed to the destination node to a node within a range that can directly communicate with the wireless link, and when a route response message to the route request message is received, transmits the route response message to the node. Means for adding a metric described in the route response message to the route table as a route to the route destination node; and when a route request message from another node is received,
Using the information in the route request message, a route destined for the transmission node of the route request message is added to the routing table, and if the wireless node itself is the destination node described in the route request message, Means for transmitting a route response message to the transmission node of the route request message, and, if the wireless node itself is not the destination node, broadcasting the route request message to nodes within a range where direct communication is possible by a wireless link. A wireless node, characterized in that: 2. A wireless node having means for transmitting and receiving a packet through a wireless interface, comprising: an "adjacent node to which the packet is to be transferred in order to deliver the packet to a certain destination node"; and a "packet to the destination node through the adjacent node." Means for holding a route table, which is a set of packet transfer routes, describing a metric which is a value representing the property of a route through which the packet arrives, and relaying a packet addressed to another node in accordance with the route table. At startup of the wireless node itself or at regular intervals,
Means for broadcasting a specific node notification message indicating that the wireless node itself is a specific node to nodes within a range where direct communication is possible via a wireless link; and means for detecting a failure at regular time intervals or when a failure is detected in a route to the specific node. Means for broadcasting a node survey message to nodes within a range that can be directly communicated via a wireless link, and when a specific node survey message is received, a route to a specific node held by the wireless node itself, and the wireless node itself identifies the route. Means for returning a specific node notification message indicating that the node is a node to the node that transmitted the specific node investigation message; and a path described in the specific node notification message when the specific node notification message is received. "Route to specific node not held in routing table" exists in In this case, the route in the specific node notification message is added to the routing table, and the “route to a specific node holding the route in the routing table” is included in the route described in the specific node notification message. Exists, and when the route described in the specific node notification message has a smaller metric than the route existing in the routing table, the route in the routing table is described in the specific node notification message. When the route is changed or added to the route table, a specific node notification message including a route to a specific node in the route table is broadcast to nodes within a range where direct communication is possible via a wireless link. Means for transmitting a packet request to a destination node when there is no route corresponding to the destination node in the routing table when a packet transfer request to the destination node occurs. Broadcast to a node in a range that can be directly communicated by a wireless link, and when a route response message to the route request message is received, a transmitting node of the route response message and a metric described in the route response message are transmitted. Means for adding the route request message to the route table as a route to the route destination node; and when a route request message from another node is received, the route to the transmission node of the route request message is determined using information in the route request message. While adding to the routing table, if the wireless node itself is the destination node described in the route request message, the wireless node transmits a route response message to the transmission node of the route request message, and the wireless node itself becomes the destination node. If not, the path request message is Wireless node and having a means for casting. 3. The method according to claim 1, wherein the metric of the route is “the number of wireless links through which the route passes” or “the reciprocal of the smallest band among the wireless links through which the route passes”. Or the wireless node according to 2. 4. A flag indicating ON / OFF of a route construction request is provided in a header of a data packet, and when a packet is transferred to a particular node, a route construction request flag of a data packet transmitted first to the particular node is set to ON. 4. A packet according to claim 1, wherein when a packet indicating a route construction request flag is ON, a route to a transmission source of the packet is constructed using information in the packet. A wireless node according to claim 1. 5. When a specific node notification message is received, even if a “route to a specific node not held in the routing table” exists in the route described in the specific node notification message, The route is not added when the metric is equal to or greater than a predetermined value.
A wireless node according to any one of the preceding claims. 6. When a specific node notification message is received and added to a routing table, only a fixed number of routes having a smaller metric among routes in the routing table are left, and the remaining routes are deleted from the routing table. As a result, when the content of the routing table changes before and after the reception of the specific node notification message, the nodes within a range where the specific node notification message including the content of the routing table can be directly communicated via a wireless link. The radio node according to any one of claims 1 to 5, wherein the radio node broadcasts to the wireless node. 7. When a specific node notification message is received, and a transmitting node that has directly transmitted the specific node notification message via a wireless link is not already registered as a next node of any route in the routing table. Or the transmitting node is registered as the next node of any of the routes in the routing table, and the metric in the specific node notification message is greater than the metric of the route in the routing table. The wireless node according to any one of claims 1 to 6, wherein a change to a routing table is performed when the size is small. 8. A gateway node comprising a plurality of wireless nodes according to any one of claims 1 to 7, wherein at least one wireless node further has a wired interface and is a gateway node capable of communicating via a wired network. A wireless network, characterized by: 9. A packet search method for a wireless node transmitting and receiving a packet through a wireless interface, comprising: "an adjacent node to which the packet is to be transferred in order to deliver the packet to a certain destination node"; and "the destination node through the adjacent node." A metric that is a value indicating the nature of the route through which the packet arrives is stored in the routing table, which is a set of packet transfer routes. Or, when a failure is detected in a path between the specific node and a specific node, a step of broadcasting a specific node investigation message to a node in a range that can be directly communicated by a radio link; and A specific node notification message describing the route to the specific node held by the node Returning the specific node investigation message to the node that transmitted the specific node notification message; and when the specific node notification message is received, the path described in the specific node notification message includes the message “to a specific node not held in the routing table. Is present in the specific node notification message, the route is added to the routing table, and “the route is held in the routing table is included in the route described in the specific node notification message. If there is a “route to a specific node” and the route described in the specific node notification message has a smaller metric than the route existing in the routing table, the route in the routing table is notified to the specific node. Change to the route described in the message, when the addition or change to the routing table occurs, a specific node notification message including a route to a specific node in the routing table, A step of broadcasting to a node in a range that can be directly communicated by a line link; and a step of transmitting a packet to a certain destination node. A route request message is broadcast to a node in a range that can be directly communicated by a wireless link, and when a route response message to the route request message is received, a transmitting node of the route response message, Adding a metric to the routing table as a route to the route destination node; and when receiving a route request message from another node,
Using the information in the route request message, a route destined for the transmission node of the route request message is added to the routing table, and if the wireless node itself is the destination node described in the route request message, Transmitting a path response message to a transmission node of the path request message, and if the wireless node itself is not a destination node, broadcasting the path request message to nodes within a range where direct communication is possible via a wireless link. A method for searching for a packet path of a wireless node, characterized in that: 10. A packet search method for a wireless node transmitting and receiving a packet through a wireless interface, comprising the steps of: "an adjacent node to which the packet is to be transferred in order to deliver the packet to a certain destination node"; and "the destination node through the adjacent node." A metric that is a value indicating the nature of the route through which a packet arrives is stored in the routing table, which is a set of packet transfer routes. To
Broadcasting a specific node notification message indicating that the wireless node itself is a specific node to nodes in a range where direct communication is possible via a wireless link, and specifying a failure at regular time intervals or when a failure is detected in a route to the specific node. Broadcasting a node survey message to nodes within a range that can be directly communicated by wireless link, and upon receiving the specific node survey message, identifying the route to the specific node held by the wireless node itself and identifying the wireless node itself Returning a specific node notification message indicating that the node is a node to the node that transmitted the specific node investigation message; and, upon receiving the specific node notification message, a path described in the specific node notification message. "Route to specific node not held in routing table" exists in In this case, the route in the specific node notification message is added to the routing table, and the “route to a specific node holding the route in the routing table” is included in the route described in the specific node notification message. Exists, and when the route described in the specific node notification message has a smaller metric than the route existing in the routing table, the route in the routing table is described in the specific node notification message. When the route is changed or added to the route table, a specific node notification message including a route to a specific node in the route table is broadcast to nodes within a range where direct communication is possible via a wireless link. And when a transfer request for a packet to a certain destination node occurs, if there is no route corresponding to the destination node in the routing table, a route request message to the destination node is sent. Is broadcast to nodes in a range that can be directly communicated by a wireless link, and when a route response message to the route request message is received, a transmitting node of the route response message and a metric described in the route response message are determined. Adding a route request message to the route table as a route to the route destination node; and, when a route request message from another node is received, using the information in the route request message to determine a route to the transmission node of the route request message. While adding to the routing table, if the wireless node itself is the destination node described in the route request message, the wireless node transmits a route response message to the transmission node of the route request message, and the wireless node itself becomes the destination node. If not, the path request message is Packet route search method of a wireless node; and a step of casting. 11. The metric of the route may be “the number of wireless links through which the route passes” or “the reciprocal of the smallest band among the wireless links through which the route passes”. Or the wireless node packet route searching method according to 10. 12. A flag indicating ON / OFF of a route construction request is provided in a header of a data packet, and when a packet is transferred to a specific node, a route construction request flag of a data packet transmitted first to the specific node is set to ON. 12. A packet according to any one of claims 9 to 11, wherein when a packet whose flag indicating a route construction request is ON is received, a route to a transmission source of the packet is constructed using information in the packet. 3. The method for searching for a packet route of a wireless node according to claim 1. 13. When a specific node notification message is received, even if a “route to a specific node not held in the routing table” exists in the routes described in the specific node notification message, 13. The method according to claim 9, wherein the route is not added when the metric is not less than a predetermined value. 14. Receiving a specific node notification message,
When an addition to the routing table occurs, only a certain number of the routes in the routing table with a smaller metric is left, and the remaining routes are deleted from the routing table. As a result, before the reception of the specific node notification message, 14. The method according to claim 9, wherein when a change occurs in the contents of the routing table after the reception, a specific node notification message including the contents of the routing table is broadcast to nodes within a range where direct communication is possible via a wireless link. The method for searching for a packet path of a wireless node according to any one of the preceding claims. 15. When a specific node notification message is received, and the transmitting node that has directly transmitted the specific node notification message via a wireless link is not already registered as a next node of any route in the routing table. Or the transmitting node is registered as the next node of any of the routes in the routing table, and the metric in the specific node notification message is greater than the metric of the route in the routing table. The method according to any one of claims 9 to 14, wherein a change to a routing table is performed when the size is smaller.