JP3879993B2 - Ad hoc network routing method - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an ad hoc network routing method, and more particularly to an ad hoc network routing method in which bandwidth compression caused by a path connection request message broadcasted by a transmission source node toward a destination node can be minimized.
[0002]
[Prior art]
In mobile nodes adopting wireless communication technology, a network in which communication is performed by autonomously configuring a network between nodes without connecting to an existing infrastructure network such as the Internet, that is, an ad hoc network has been proposed.
[0003]
FIG. 11 is a diagram illustrating a configuration example of an ad hoc network, in which circles indicate mobile nodes Na, Nb... Ng, and concentric circles described on the outer periphery thereof indicate radio coverage of each mobile node. Each mobile node has a routing function, creates a route to a destination node, and distributes data.
[0004]
In an ad hoc network having such a configuration, in an on-demand type routing method in which a route to a destination is established when a data transmission request is generated at any node, the source node first has a route (path) to the destination node. As a control message for establishing (), a path connection request message is broadcasted (advertised). The path connection request message is propagated to the destination node by repeating the rebroadcast by each relay node that has received the message.
[0005]
[Problems to be solved by the invention]
In the above-described conventional path establishment method, each node has a function for preventing re-broadcasting when a node receives a path connection request message broadcasted by itself as a function for preventing a path connection request message from forming a loop. However, newly received messages are always rebroadcast. For this reason, as indicated by arrows in FIG. 12, when the number of nodes is large, there is a high possibility that the same path connection request message will flow on the network, and these messages will squeeze the communication band. There was a technical problem.
[0006]
SUMMARY OF THE INVENTION An object of the present invention is to provide an ad hoc network routing method that solves the above-described problems of the prior art and is less likely to cause communication band compression due to a path connection request message.
[0007]
[Means for Solving the Problems]
In order to achieve the above object, the present invention provides an ad hoc network routing method in which a plurality of wireless nodes construct a wireless network in an autonomous and distributed manner, wherein a node that relays a path connection request message broadcast from a transmission source node is provided. The following procedure is performed.
(1) Counting the number of received path connection request messages
(2) Procedure for setting the relay probability of the received path connection request message based on the counting result
(3) Procedure for selectively prohibiting relaying of each received path connection request message based on the relay probability
By providing the above features, according to the present invention, each relay node can quantitatively grasp the congestion level of the wireless node by counting the number of received path connection request messages. If the congestion level of the wireless node is high, there is a high possibility that the path connection request message will be transmitted and received in duplicate, so that each relay node prohibits rebroadcasting of a part of the received path connection request message. Thereby, compression of the communication band is suppressed without impairing the function of the path connection request message.
[0009]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the drawings. Here, in the network configuration shown in FIG. 11, a case where the node Na functions as a transmission source node, the node Nd functions as a destination node, and other nodes function as relay nodes will be described as an example.
[0010]
FIG. 1 is a flowchart showing an operation of transmitting a path connection request message in the transmission node Na. In step S101, the node Na that has received the packet transmission request from the application layer, which is an upper layer, behaves as a transmission source node. In step S102, it is determined whether or not the path to the designated destination node Nd has already been established. . If the path is not established, the process proceeds to step S103, where “1” is set as the initial value for the number of trials K as the number of transmissions of the path connection request message. In step S104, a path connection request message destined for the node Nd is broadcast.
[0011]
In step S105, it is determined whether or not a path connection response message unicast from the destination node Nd to the own node is received in response to the path connection request, and the process proceeds to step S106 until the path connection response message is received. . In step S106, it is determined whether or not an elapsed time after sending the path connection request message has passed a predetermined retry waiting time, and the process returns to step S105 until it elapses.
[0012]
Thereafter, when a retry waiting time elapses and this is detected in step S106, it is determined in step S107 whether or not the number of trials K has exceeded the retry upper limit value Kmax1, and initially it is determined not to exceed. Therefore, the number of trials K is incremented in step S112, and then the process returns to step S104 to broadcast the path connection request message again.
[0013]
Thereafter, the path connection request message is rebroadcast every time the retry waiting time elapses until reception of the path connection response message is detected in step S105. If it is determined in step S107 that the number of trials K has reached the retry upper limit Kmax1, it is determined in step S108 whether or not the number of trials K has exceeded the forced mode upper limit Kmax2. If the number of trials K is less than the forced mode upper limit value Kmax2, the operation mode is changed to the forced mode in step S111, and the process proceeds to step S112.
[0014]
On the other hand, if the number of trials K is not less than the forced mode upper limit Kmax2, the packet is discarded in step S109. In step S110, a message indicating that the packet has been discarded is notified to the upper layer.
[0015]
Next, the operation of each relay node and destination node that has received the path connection request message will be described with reference to the flowchart of FIG.
[0016]
In step S201, the node that has received the path connection request message executes a relay probability update process in step S202 for updating a relay probability that is a material for determining whether or not to relay the path connection request message.
[0017]
FIG. 3 is a flowchart showing the operation of the relay probability update process, and FIG. 4 is a diagram schematically showing the operation.
[0018]
In step S401, it is determined whether or not the Δt counter that repeatedly counts the predetermined period Δt has timed out. If not timed out, the process proceeds to step S404, and the current reception count Nj representing the number of path connection request messages received within the predetermined period Δt is incremented by “1” and updated. On the other hand, if it is determined in step S401 that the Δt counter has timed out, in step S402, the current reception count Nj is registered as the previous reception count Nj-1.
[0019]
In step S403, the current reception count Nj is reset. In step S404, as described above, the current reception count Nj is incremented by “1” and updated to “1”. As a result, as shown in FIG. 4, the number of receptions of the path connection request message within the current predetermined period Δt is registered in the current reception number Nj. Similarly, the number of receptions of the path connection request message within the previous predetermined period Δt is registered in the previous reception number Nj−1.
[0020]
In step S405, the average reception count AVE (Nj) of the path connection request message is calculated based on the following equation (1). The constant G (0 <G <1) is a coefficient for reflecting the current reception count Nj more strongly than the previous reception count Nj−1 with respect to the average reception count AVE (Nj).
AVE (Nj) = (1-G) × AVE (Nj-1) + G × Nj (1)
[0021]
In step S406, the average reception count AVE (Nj) is applied to a predetermined function f to determine the relay probability p (j) of the path connection request message received this time. The function f (j) is a simple decrease function of [0, 1] as shown in FIG. 5 and is given by the following equation (2), for example.
f (x) = 1 / (x + 1) where x ≧ 0 (2)
[0022]
Returning to FIG. 2, in step S203, it is determined whether or not the destination of the message is the local node. If the destination is other than its own node, it acts as a relay node, and in step S204, it is determined whether or not a path to the designated destination has already been established. If the path to the destination has not been established, it is determined in step S205 whether the received path connection request message is new. In this embodiment, if at least one of the transmission source node and destination node registered in the path connection request message is different from the transmission source node and destination node of the path connection request message received earlier than this, The message is judged as a new message and the process proceeds to step S206.
[0023]
In step S206, it is determined whether or not “forced mode” in which the received path connection request message is forcibly relayed regardless of the relay probability p (j) is designated. If the forced mode is designated, the relay probability p (j) updated in step S202 is increased in step S207. In step S208, as shown in FIG. 6, the adjacent node that has relayed the message and transferred it to its own node is registered in the routing table as the next hop when data is transmitted to the transmission source. That is, the node Nc that has received the path connection request message broadcast by the transmission source node Na from the node Nb registers the node Nb as the next pop of the packet destined for the node Na. In step S210, the path connection request message is rebroadcast.
[0024]
On the other hand, if it is determined in step S206 that the current mode is not the “forced mode”, the process proceeds to step S209. In step S209, based on the updated relay probability p (j), it is determined whether or not to relay the currently received message. In the present embodiment, as shown in FIG. 7, a random number R of [0, 1] is generated, and if this random number R falls below the relay probability p (j), the process proceeds to step S208 to relay the message. If the random number R exceeds the relay probability p (j), the process ends to prohibit the relay.
[0025]
In step S203, if the destination of the received path connection request message is the local node, it behaves as a destination node. In step S211, a path connection response message for the received path connection request message is unicast to the source node Na. To do. Further, as shown in FIG. 8, even when the node Nb when the path has already been established between the nodes Nb and Nd receives the path connection request message destined for the node Nd, the destination in step S204 It is determined that the path up to has already been established, and the process proceeds to step S211.
[0026]
FIG. 13 is a diagram schematically showing the relay status of the path connection request message in this embodiment, and the total number of path connection request messages is reduced compared to the prior art of FIG.
[0027]
FIG. 9 is a flowchart showing the operation of each relay node that has received the path connection response message returned from the destination node Nd.
[0028]
When the path connection response message is received in step S301, in step S302, as shown in FIG. 10, the adjacent node that relayed the path connection response message is registered in the routing table as the next hop when the packet is transmitted to the destination. To do. That is, the node Nb that has received from the node Nc the path connection response message unicast from the destination node Nd registers the node Nc as the next pop of the packet destined for the node Nd. Note that the route table of each node through which the unselected path passes is deleted after a certain time. In step S303, the path connection response message is transmitted to the next hop based on the route table.
[0029]
Next, returning to the flowchart of FIG. 1, the operation of the source node that has received the path connection response message will be described.
[0030]
When the path connection response message is received in step S105, the process proceeds to step S113, and the route information registered in the path connection response message is written in the route table of the own node. As a result, a path is established between the nodes Na and Nd. In step S114, the packet requested to be transmitted is transmitted to the destination using the established path.
[0031]
【The invention's effect】
According to the present invention, each relay node can quantitatively grasp the congestion level of the wireless node by counting the number of received path connection request messages. If the congestion level of the wireless node is high, there is a high possibility that the path connection request message will be transmitted and received in duplicate, so that each relay node prohibits rebroadcasting of a part of the received path connection request message. Thereby, it is possible to suppress the compression of the communication band without impairing the function of the path connection request message.
[Brief description of the drawings]
FIG. 1 is a flowchart showing a procedure for a transmission node to broadcast a path connection request message.
FIG. 2 is a flowchart showing operations of a relay node and a destination node that have received a path connection request message.
FIG. 3 is a flowchart showing an operation of a relay probability update process.
FIG. 4 is a diagram schematically showing the operation of a relay probability update process.
FIG. 5 is a diagram illustrating an example of a function f (j).
FIG. 6 is a diagram illustrating an example of route information registered by a relay node based on a path connection request message.
FIG. 7 is a diagram showing a method for determining whether or not to relay a path connection request message based on the relay probability p (j).
FIG. 8 is a diagram schematically showing a state in which a path requested by a path connection request message has already been established.
FIG. 9 is a flowchart showing the operation of each relay node that has received a path connection response message.
FIG. 10 is a diagram illustrating an example of route information registered by a relay node based on a path connection response message.
FIG. 11 is a diagram illustrating a configuration example of an ad hoc network.
FIG. 12 is a diagram illustrating a relay status of a path connection response message according to a conventional technique.
FIG. 13 is a diagram illustrating a relay status of a path connection response message according to the present invention.
[Explanation of symbols]
Na, Nb, Nc, Nd, Ne, Nf, Ng ... wireless node

Claims (3)

A plurality of wireless nodes construct a wireless network in an autonomous and distributed manner, a source node designates a destination node and broadcasts a path connection request message relayed by another wireless node, and the destination node connects to the path In an ad hoc network routing method for unicasting a path connection response message to the source node in response to a request message,
A node that relays the path connection request message;
A procedure for counting the number of received path connection request messages;
A procedure for setting a relay probability of the received path connection request message based on the counting result;
A procedure for selectively prohibiting relaying of each received path connection request message based on the relay probability,
The source node is
When a path connection response message cannot be received in response to the broadcast path connection request message, the method includes a step of broadcasting the path connection request message in a forced mode,
The ad hoc network routing method according to claim 1, wherein the relay node relays the path connection request message broadcast in the forced mode regardless of the relay probability. A plurality of wireless nodes construct a wireless network in an autonomous and distributed manner, a source node designates a destination node and broadcasts a path connection request message relayed by another wireless node, and the destination node connects to the path In an ad hoc network routing method for unicasting a path connection response message to the source node in response to a request message,
A node that relays the path connection request message;
A procedure for counting the number of received path connection request messages;
A procedure for setting a relay probability of the received path connection request message based on the counting result;
A procedure for selectively prohibiting relaying of each received path connection request message based on the relay probability,
The source node is
When a path connection response message cannot be received in response to the broadcast path connection request message, the method includes a step of broadcasting the path connection request message in a forced mode,
The ad hoc network routing method according to claim 1, wherein when the relay node receives a path connection request message broadcast in the forced mode, the relay node increases the relay establishment rate. The ad hoc network routing method according to claim 1 or 2 , wherein the relay node lowers the relay probability as the number of path connection request messages received per unit time increases.

Images