JP2012147054A - Congestion notification method, congestion notification device, and congestion notification program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a congestion notification method, a congestion notification device, a congestion notification program for detecting the congestion of an ad hoc network.SOLUTION: A gateway 100 includes a storage unit 110, a communication unit 120, an increment amount calculation unit 130, a dispersion calculation unit 140, a deviation value calculation unit 150, and an alarm notification unit 160. The communication unit 120 acquires data of the number of hops included in a packet received from a connection destination node for each node, and stores the data in the storage unit 110. The increment amount calculation unit 130 calculates, with referring to the storage unit 110, the increment amount of a route length, based on the number of the hops included in the preceding and succeeding packets, which is acquired by the communication unit 120. The dispersion calculation unit 140 calculates the dispersion of the increment amount. The deviation value calculation unit 150 calculates a deviation value of dispersion. The alarm notification unit 160 outputs alarm indicating an effect that a present state is congestion, when the deviation value of the dispersion exceeds a prescribed value.

Description

  The present invention relates to a congestion notification program and the like.

  There is a communication system using an ad hoc network. An ad hoc network is a network in which a plurality of nodes are connected to each other by radio in an autonomous and distributed manner. In an ad hoc network, no access point is installed, and each node forms a communication path by relaying a packet received from an adjacent node to another adjacent node based on the communication path information.

  In an ad hoc network, communication paths frequently change due to changes in radio field strength, changes in available network capacity, communication failures, and the like. FIG. 9 is a diagram illustrating a change in the communication path of the ad hoc network. As shown in FIG. 9, this ad hoc network includes nodes 1 a to 1 k and a gateway 2.

  The left side of FIG. 9 shows the communication path of the ad hoc network during normal operation. In such normal operation, the packet addressed to the gateway reaches the gateway 2 through the shortest path. For example, a packet transmitted from the node 1a reaches the gateway 2 via the node 1b. The packet transmitted from the node 1c reaches the gateway 2 via the node 1d.

  The center of FIG. 9 shows a communication path when the network capacity approaches the limit and congestion occurs. When congestion occurs, the degenerate operation is started, and a packet addressed to the gateway 2 reaches the gateway 2 bypassing a non-communication route. For example, when communication with the node 1d is impossible, the packet transmitted from the node 1c reaches the gateway 2 via the nodes 1k, 1j, and 1h. The path length of the packet transmitted from the node 1c is longer than the path length on the left side of FIG.

  The right side of FIG. 9 shows a communication path when a system abnormality occurs. If the number of paths that cannot be communicated increases and the path for reaching the gateway 2 disappears, the packet does not reach the gateway 2 and a system abnormality occurs. For example, although packets transmitted from the nodes 1a and 1c repeat detours, communication cannot be performed between the gateway 2 and the nodes 1b, 1d, 1h, 1g, and 1f, and thus the gateway 2 cannot be reached. .

  In order to prevent the occurrence of the system abnormality as described with reference to FIG. 9, it is required to grasp a sign of the system abnormality. Conventionally, the cause of system abnormality is analyzed by performing a simulation based on the usage rate with respect to the network capacity and determining the relationship between the network capacity and the passage of time.

JP-T-2005-524311

  However, the above-described conventional technology has a problem that it is difficult to detect congestion that is a sign of system abnormality.

  When detecting congestion in an ad hoc network by simulation, network capacity is used. Since this network capacity varies greatly depending on differences in topology, the influence of hidden terminals, addition or deletion of nodes, radio wave conditions, etc., it is difficult to predict these complex factors in advance and obtain the network capacity.

  FIG. 10 is a diagram illustrating the relationship between the network capacity and the network capacity derived by simulation. Line 3 in FIG. 10 shows the actual network capacity. Line 4 shows the network capacity derived in the simulation. The actual network capacity always varies due to the various factors described above. Since all the factors cannot be predicted in advance in the simulation, for example, each time a node is added or deleted, the simulation is restarted. For example, in 4a and 4b of FIG. 10, the addition or deletion of a node occurs, and the simulation is performed again. Thus, in the simulation, the actual network capacity changes are tracked while recalculating according to the changing factors, and it is difficult to detect congestion in real time in the simulation.

  The disclosed technology has been made in view of the above, and an object thereof is to provide a congestion notification method, a congestion notification device, and a congestion notification program capable of detecting congestion in an ad hoc network.

  In the ad hoc network, the congestion notification method disclosed in the present application acquires, for each node, data on the number of hops included in a packet received from a connection destination node, and routes based on the number of hops included in previous and subsequent packets. Calculate the increase in length. Also, the congestion notification method calculates a deviation value of variance relating to the amount of increase in the path length, and notifies a warning that the congestion state is present when the deviation value exceeds a predetermined value.

  According to the congestion notification method disclosed in the present application, it is possible to detect congestion in an ad hoc network.

FIG. 1 is a diagram illustrating an example of an ad hoc network according to the present embodiment. FIG. 2 is a diagram illustrating an example of a data structure of a packet. FIG. 3 is a functional block diagram showing the configuration of the gateway. FIG. 4 is a diagram illustrating an example of the data structure of the hop number table. FIG. 5 is a diagram illustrating an example of the data structure of the increase amount table. FIG. 6 is a diagram illustrating a relationship between a deviation value of dispersion and a network abnormality. FIG. 7 is a flowchart showing the processing procedure of the gateway. FIG. 8 is a diagram illustrating a hardware configuration of a computer constituting the congestion notification device according to the embodiment. FIG. 9 is a diagram illustrating a change in the communication path of the ad hoc network. FIG. 10 is a diagram illustrating the relationship between the network capacity and the network capacity derived by simulation.

  Hereinafter, embodiments of a congestion notification method, a congestion notification device, and a congestion notification program disclosed in the present application will be described in detail with reference to the drawings. Note that the present invention is not limited to the embodiments.

  FIG. 1 is a diagram illustrating an example of an ad hoc network according to the present embodiment. As shown in FIG. 1, this ad hoc network includes nodes 10 a to 10 h and a gateway 100. The gateway 100 is assumed to be connected to another network. In the present embodiment, a case where the gateway 100 includes a function corresponding to the congestion notification device will be described as an example.

  The nodes 10a to 10h are wirelessly connected to the adjacent nodes, and transmit the packet to the destination by relaying the packet received from the adjacent node to other adjacent nodes based on the communication path information. Further, the nodes 10a to 10h update communication path information by transmitting and receiving hello packets to and from other nodes.

  In the example shown in FIG. 1, the node 10a and the node 10e are connected by radio. The node 10b and the node 10f are connected by radio. The node 10c and the node 10g are connected by radio. The node 10d and the node 10h are connected by radio. The gateway 100 is wirelessly connected to the nodes 10a to 10d.

  When the gateway 100 receives a packet from an adjacent node, the gateway 100 detects a congestion state by using the variance of the path length difference between the packet acquired this time and the packet acquired last time. The path length corresponds to the number of nodes through which the packet has reached the gateway 100. Similarly to the normal gateway, when the gateway 100 acquires a packet from an adjacent node, the gateway 100 transmits the packet to another network that is the destination of the acquired packet.

  An example of a data structure of a packet transmitted / received in an ad hoc network will be described. FIG. 2 is a diagram illustrating an example of a data structure of a packet. As shown in FIG. 2, the packet includes a control header, the number of hops, and various data. The control header includes address information of the packet transmission destination and address information of the packet transmission source. The number of hops indicates the number of nodes through which the packet has passed. Various data includes user data and the like.

  Next, an example of the configuration of the gateway 100 illustrated in FIG. 1 will be described. FIG. 3 is a functional block diagram showing the configuration of the gateway. As illustrated in FIG. 3, the gateway 100 includes a storage unit 110, a communication unit 120, an increase amount calculation unit 130, a variance calculation unit 140, a deviation value calculation unit 150, and a warning notification unit 160.

  The storage unit 110 is a storage device that stores a hop number table 111 and an increase amount table 112. The storage unit 110 corresponds to, for example, a semiconductor memory device such as a random access memory (RAM), a read only memory (ROM), or a flash memory, or a storage device such as a hard disk or an optical disk.

  The hop number table 111 is a table that sequentially stores the number of hops of a packet for each node that receives the packet. FIG. 4 is a diagram illustrating an example of the data structure of the hop number table. As shown in FIG. 4, the hop number table 111 stores node identification information and hop number information in association with each other. The node identification information is information for identifying a node. For example, nodes corresponding to the node identification information 10a to 10d are assumed to be nodes 10a to 10d. The hop number information is information in which the hop numbers of packets received from the corresponding node are arranged in time series.

  4, the number of hops included in the packet received from the node 10a is A1, A2, A3, A4,... In chronological order. 4, the number of hops included in the packet received from the node 10b is B1, B2, B3, B4,... In chronological order. 4, the number of hops included in the packet received from the node 10c is C1, C2, C3, C4,... In chronological order. 4, the number of hops included in the packet received from the node 10d is D1, D2, D3, D4,... In chronological order.

  The increase amount table 112 is a table that stores, for each node, an increase amount of the hop number of the current packet compared to the hop number of the previous packet. FIG. 5 is a diagram illustrating an example of the data structure of the increase amount table. As illustrated in FIG. 5, the increase amount table 112 stores node identification information and increase amount information in association with each other. The increase amount information is information in which the increase amounts of the hop numbers of the preceding and following packets are arranged in time series.

  As shown in the first row of FIG. 5, the amount of increase in the number of packets before and after received from the node 10a is a1, a2, a3, a4,. For example, the difference between A1 and A2 shown in FIG. 4 corresponds to a1, the difference between A2 and A3 corresponds to a2, and the difference between A3 and A4 corresponds to a3.

  As shown in the second row of FIG. 5, the increase amount of the packets before and after received from the node 10b is b1, b2, b3, b4,. For example, the difference between B1 and B2 shown in FIG. 4 corresponds to b1, the difference between B2 and B3 corresponds to b2, and the difference between B3 and B4 corresponds to b3.

  As shown in the third row of FIG. 5, the increase amount of the packets before and after received from the node 10c is c1, c2, c3, c4,. For example, the difference between C1 and C2 shown in FIG. 4 corresponds to c1, the difference between C2 and C3 corresponds to c2, and the difference between C3 and C4 corresponds to c3.

  As shown in the fourth row in FIG. 5, the amount of increase in the number of packets before and after being received from the node 10d is d1, d2, d3, d4,. For example, the difference between D1 and D2 shown in FIG. 4 corresponds to d1, the difference between D2 and D3 corresponds to d2, and the difference between D3 and D4 corresponds to d3.

  When receiving a packet from an adjacent node, the communication unit 120 registers the hop number of the received packet in the hop number table 111 in association with the node identification information. For example, when receiving a packet from the node 10a, the communication unit 120 records the hop number of the received packet in the hop number information of the hop number table 111 in association with the node identification information 10a. Further, the communication unit 120 refers to the control header of the packet and transfers the packet toward the destination.

  The increase amount calculation unit 130 is a processing unit that calculates an increase amount of the number of hops of a packet for each node when the communication unit 120 receives a packet. The increase amount calculation unit 130 acquires the hop number of the packet from the hop number table 111. The increase amount calculation unit 130 calculates the increase amount for each node by comparing the number of hops of the packets before and after received from the same node. The increase amount calculation unit 130 registers the increase amount of the number of hops in the increase amount table 112 in association with the node identification information.

  For example, when the communication unit 120 receives a packet from the node 10a and registers the hop number A3 of this packet in the hop number information, the increase amount calculation unit 130 subtracts the hop number A3 from the hop number A4. If the subtracted value is 3a, the increase amount calculation unit 130 registers the increase amount a3 in the increase amount information of the increase amount table 112 in association with the node identification information 10a.

  The variance calculation unit 140 is a processing unit that calculates the variance of the increase amount based on the increase amount table 112. The variance calculation unit 140 outputs the calculated variance to the deviation value calculation unit 150. Here, a case will be described in which a variance is calculated by paying attention to the increase in the number of hops corresponding to the nodes 10a, 10b, 10c, and 10d. Further, the increase amount information of the node identification information 10a is assumed to be “a1, a2, a3, a4” in chronological order. The increase amount information of the node identification information 10b is “b1, b2, b3, b4” in chronological order. The increase amount information of the node identification information 10c is “c1, c2, c3, c4” in chronological order. The increase amount information of the node identification information 10d is “d1, d2, d3, d4” in chronological order.

  First, the variance calculation unit 140 calculates the average value of each increase amount. For example, the variance value calculation unit 140 calculates the average value X based on Expression (1).

  Average value X = (a1 + a2 + a3 + a4 + b1 + b2 + b3 + b4 + c1 + c2 + c3 + c4 + d1 + d2 + d3 + d4) / 16 (1)

  After calculating the average value X, the variance calculation unit 140 calculates the variance at each time point by subtracting the average value of the increase amount at each time point from the average value X. In the above example, the variance 4 is calculated by the following equation (2). The variance calculation unit 140 outputs the calculated variance to the deviation value calculation unit 150. However, it is assumed that a1 to d1 are old data and a4 to d4 are the latest data.

Dispersion 4 = {(X− (a1 + b1 + c1 + d1) / 4) ² + (X− (a2 + b2 + c2 + d2) / 4) ² + (X− (a3 + b3 + c3 + d3) / 4) ² + (X− (a4 + b4 + c4 + d4) / 4) ² } / 4 ... (2)

  When a new increase amount is registered in the increase amount table 112, the variance calculating unit 140 recalculates the average value X, and calculates the variance based on the new increase amount. For example, if the increase amounts corresponding to the node identification information 10a to 10d are “a5, b5, c5, d5”, the average value X is calculated in consideration of the increase amounts. The average value X in consideration of “a5, b5, c5, d5” is obtained by Expression (3).

  Average value X = (a2 + a3 + a4 + a5 + b2 + b3 + b4 + b5 + c2 + c3 + c4 + c5 + d2 + d3 + d4 + d5) / 16 (3)

  Then, the variance calculation unit 140 calculates the variance 5 and outputs the calculated variance to the deviation value calculation unit 150. For example, the variance 5 is expressed by the following formula (4). However, the following average value X is an average value in consideration of “a5, b5, c5, d5”.

Dispersion 5 = {(X− (a2 + b2 + c2 + d2) / 4) ² + (X− (a3 + b3 + c3 + d3) / 4) ² + (X− (a4 + b4 + c4 + d4) / 4) ² + (X− (a5 + b5 + c5 + d5) / 4) ² } / 4 ... (4)

  Each time a new increase amount is registered in the increase amount table 112, the variance calculating unit 140 repeatedly executes the above processing to calculate the variance.

  The deviation value calculation unit 150 is a processing unit that calculates a deviation value of dispersion. Here, as an example, a case where a deviation value of variance 4 is calculated based on variance 1 to variance 4 will be described. First, the deviation value calculation unit 150 calculates an average value Y of variance.

  The deviation value calculation unit 150 calculates the standard deviation of the variance 4 after calculating the average value Y of the variance. For example, the number of variances is 4 and the average value Y. The deviation value calculation unit 150 obtains the average value Y by the equation (5). The deviation value calculation unit 150 obtains the standard deviation σ of variances 1 to 4 using Expression (6).

  Average value Y = (dispersion 1 + dispersion 2 + dispersion 3 + dispersion 4) / 4 (5)

Standard deviation σ = ((dispersion 1−average value Y) ² + (dispersion 2−average value Y) ² + (dispersion 3−average value Y) ² + (dispersion 4−average value Y) ² ) / 4) ^{1 / 2} ... (6)

  The deviation value calculation unit 150 calculates a standard deviation σ of variances 1 to 4 and then obtains a deviation value of variance 4. For example, the deviation value calculation unit 150 obtains the deviation value of the variance 4 by Expression (7).

  Deviation value of variance 4 = 10 × (dispersion 4−average value Y) / standard deviation σ + 50 (7)

  When the new variance is acquired from the variance calculator 140, the deviation value calculator 150 recalculates the average value Y taking into account the new variance, and calculates a new variance deviation value. Assuming that the new variance is variance 5, the deviation value calculation unit 150 obtains the average value Y by equation (8). In addition, the deviation value calculation unit 150 obtains a standard deviation taking into account the variance 5 by the equation (9). Further, the deviation value calculation unit 150 obtains the deviation value of the variance 5 by the equation (10).

  Average value Y = (dispersion 2 + dispersion 3 + dispersion 4 + dispersion 5) / 4 (8)

Standard deviation σ = ((dispersion 2−average value Y) ² + (dispersion 3−average value Y) ² + (dispersion 4−average value Y) ² + (dispersion 5−average value Y) ² ) / 4) ^{1 / 2} ... (9)

  Deviation value of variance 5 = 10 × (dispersion 5−average value Y) / standard deviation σ + 50 (10)

  The deviation value calculation unit 150 repeats the above process every time a new variance is acquired, and calculates a deviation value of a new variance. The deviation value calculation unit 150 outputs the calculated deviation value of variance to the warning notification unit 160.

  The warning notification unit 160 is a processing unit that obtains a deviation value of variance from the deviation value calculation unit 150 and notifies a warning that a congestion state exists when the deviation value of variance exceeds a predetermined value. For example, the warning notification unit 160 notifies a warning when the variance deviation value exceeds 70. The warning notification unit 160 may output a warning to a display or the like connected to the gateway 100, or may notify the warning to a management device or the like that manages the ad hoc network.

  Note that since the number of variance samples is small at the start of processing, the variance deviation value may not be stable. For this reason, the warning notification unit 160 may determine whether or not the variance deviation value exceeds a predetermined value after a predetermined time has elapsed since the start of processing. Alternatively, the warning notification unit 160 may determine whether or not the variance deviation value exceeds a predetermined value after the number of times of obtaining the variance deviation value exceeds a predetermined number.

  The communication unit 120, the increase amount calculation unit 130, the variance calculation unit 140, the deviation value calculation unit 150, and the warning notification unit 160 are integrated devices such as an ASIC (Application Specific Integrated Circuit) or an FPGA (Field Programmable Gate Array). Corresponding to The processing units 120 to 160 correspond to electronic circuits such as a CPU (Central Processing Unit) and an MPU (Micro Processing Unit), for example.

  Next, the relationship between the variance deviation value and the network abnormality will be described. FIG. 6 is a diagram illustrating a relationship between a deviation value of dispersion and a network abnormality. The horizontal axis in FIG. 6 indicates the number of packet collections and corresponds to time. The vertical axis on the left side of FIG. 6 is an axis indicating the packet arrival rate and the amount of traffic. The vertical axis on the right side of FIG. 6 is an axis indicating the magnitude of the variance deviation value. A line 5 is a trajectory showing a change in traffic volume with time. A line 6 is a trajectory showing a change in the arrival rate with time. A line 7 is a trajectory showing a change in the deviation value of the variance with time.

  As shown in FIG. 6, the amount of traffic increases as time elapses. The arrival rate is almost 100% until the number of packet collection times before T1, but after reaching T1, the arrival rate is not stable at 100% and becomes 0% when T2 is reached. The transition to T1 may cause the system to malfunction because the packet may not reach the destination.

  Here, paying attention to the line 7, it is divided into stages (1) to (7). Stage (1) is an unstable period due to the small number of samples. Step (2) corresponds to a period during which the packet is stably transferred through the shortest path. Step (3) corresponds to a period in which the degenerate operation is started and the packet is transferred while detouring. In step (4), a peak 7a of variance deviation value occurs. However, the unstable period is excluded. Step (5) corresponds to a period during which packets are stably transferred while detouring. Step (6) corresponds to a period in which the packet is transferred while further searching for a detour destination. Step (7) corresponds to a period in which a network abnormality has occurred.

  As described above, when there is a possibility that a network abnormality may occur, it is understood that a peak occurs in the deviation value of dispersion in advance. The warning notification unit 160 detects this peak value by comparing the deviation value of the variance with a predetermined value. When the warning notification unit 160 outputs a warning, a system abnormality has not yet occurred. Therefore, if a process such as reducing the network amount is performed on this warning, the system abnormality can be prevented beforehand. .

  Next, a processing procedure when the gateway 100 according to the present embodiment detects a congestion state will be described. FIG. 7 is a flowchart showing the processing procedure of the gateway. The process illustrated in FIG. 7 is executed, for example, when a new packet is acquired.

  As shown in FIG. 7, the gateway 100 determines whether or not a new packet has been received (step S101). When the gateway 100 has not received a new packet (step S101, No), the gateway 100 proceeds to step S101 again.

  When the gateway 100 receives a new packet (step S101, Yes), the gateway 100 registers the number of hops (step S102) and calculates an increase in the path length (step S103).

  The gateway 100 calculates the variance of the increase amount (Step S104), and calculates the deviation value of the variance (Step S105). The gateway 100 determines whether or not the variance exceeds a predetermined value (step S106).

  When the variance does not exceed the predetermined value (No at Step S106), the gateway 100 proceeds to Step S101. On the other hand, when the variance exceeds a predetermined value (step S106, Yes), the gateway 100 outputs a warning (step S107).

  Next, the effect of the gateway 100 according to the present embodiment will be described. The gateway apparatus 100 according to the present embodiment obtains an increase amount of the path length from the number of hops of the preceding and succeeding packets, calculates a variance of the increase amount, and detects congestion based on a deviation value of the variance. Therefore, the gateway 100 can notify a congestion state that is a sign that a system abnormality will occur. Further, according to the method of detecting congestion by the gateway 100, the calculation is repeated many times by a simple method because the difference in topology, the influence of hidden terminals, the addition or deletion of nodes, and the state of radio waves are not used as parameters. Thus, it is possible to detect a sign of system abnormality.

  By the way, each component of the gateway 100 is functionally conceptual and does not necessarily need to be physically configured as illustrated. In other words, the specific form of distribution and integration of the gateway 100 is not limited to the one shown in the figure, and all or a part thereof may be functionally or physically distributed or arbitrarily distributed in arbitrary units according to various loads or usage conditions. Can be integrated and configured. For example, the storage unit 110, the communication unit 120, the increase amount calculation unit 130, the variance calculation unit 140, the deviation value calculation unit 150, and the warning notification unit 160 may be combined into a congestion notification function unit. Further, in the present embodiment, as an example, the case where the gateway 100 has the function of the congestion notification device has been described as an example, but the present invention is not limited to this. For example, the nodes 10a to 10h may have a function of a congestion notification device and notify a congestion warning. The function of the congestion notification device corresponds to the above-described congestion notification function unit.

  Further, in the above-described embodiment, the case has been described in which the variance calculation unit 140 calculates the variance focusing on the amount of increase in the number of hops corresponding to the nodes 10a, 10b, 10c, and 10d. However, the variance calculation unit 140 may calculate the variance by paying attention to the increase in the number of hops corresponding to a single node, or pay attention to the increase in the number of hops corresponding to a set of a plurality of nodes. The variance may be calculated.

  A case will be described in which the variance calculation unit 140 calculates variance by paying attention to the increase in the number of hops corresponding to a single node. Here, as an example, attention is paid to the node 10a. The increase amount information of the node identification information 10a is “a1, a2, a3, a4” in chronological order.

  First, the variance calculation unit 140 calculates the average value X of the increase amount of packets received from the node 10a. For example, the variance calculating unit 140 calculates the average value X by the equation (11).

  Average value X = (a1 + a2 + a3 + a4) / 4 (11)

  After calculating the average value X, the variance calculating unit 140 calculates the variance at each time point by subtracting the amount of increase at each time point from the average value. In this example, the variance 4 shown below is calculated. The variance calculation unit 140 calculates the variance 4 using Equation (12). The variance calculation unit 140 outputs the calculated variance to the deviation value calculation unit 150.

Dispersion 4 = {(X−a1) ² + (X−a2) ² + (X−a3) ² + (X−a4) ² } / 4 (12)

  When a new increase amount is registered in the increase amount table 112, the variance calculating unit 140 recalculates the average value X, and calculates the variance based on the new increase amount. For example, if the increase amount newly added to the node identification information 10a is “a5”, the average value X is calculated in consideration of this increase amount. Then, the variance calculation unit 140 calculates the variance 5 and outputs the calculated variance to the deviation value calculation unit 150. For example, the variance 5 is as shown in Expression (13). However, the following average value X is an average value of “a1, a2, a3, a4, a5”.

Dispersion 5 = {(X−a2) ² + (X−a3) ² + (X−a4) ² + (X−a5) ² } / 4 (13)

  A case will be described in which the variance calculation apparatus 140 calculates variance by paying attention to the amount of increase in the number of hops corresponding to a set of a plurality of nodes. Here, as an example, attention is focused on the nodes 10a and 10b. The increase amount information of the node identification information 10a is “a1, a2, a3, a4” in chronological order. The increase amount information of the node identification information 10b is “b1, b2, b3, b4” in chronological order.

  First, the variance calculation unit 140 calculates an average value X of the increase amount of packets received from the nodes 10a and 10b. For example, the variance calculation unit 140 calculates the average value X by the equation (14).

  Average value X = (a1 + a2 + a3 + a4 + b1 + b2 + b3 + b4) / 8 (14)

  After calculating the average value X, the variance calculating unit 140 calculates the variance at each time point by subtracting the amount of increase at each time point from the average value. In this example, the variance 4 shown below is calculated. The variance calculation unit 140 calculates variance 4 according to equation (15). The variance calculation unit 140 outputs the calculated variance to the deviation value calculation unit 150.

Distributed ^{4 = {(X- (a1 +} b1) / 2) 2 + (X- (a2 + b2) / 2) 2 + (X- (a3 + b3) / 2) 2 + (X- (a4 + b4) / 2) 2} / 4 ... (15)

  When a new increase amount is registered in the increase amount table 112, the variance calculating unit 140 recalculates the average value X, and calculates the variance based on the new increase amount. For example, if the amount of increase newly added to the node identification information 10a and 10b is “a5, b5”, the average value X is calculated in consideration of the amount of increase. Then, the variance calculation unit 140 calculates the variance 5 and outputs the calculated variance to the deviation value calculation unit 150. For example, the variance 5 is expressed by the following equation (16). However, the following average value X is an average value of “a1, a2, a3, a4, a5, b1, b2, b3, b4, b5”.

Dispersion 5 = {(X− (a2 + b2) / 2) ² + (X− (a3 + b3) / 2) ² + (X− (a4 + b4) / 2) ² + (X− (a5 + b5) / 2) ² } / 4 ... (16)

  By the way, the variance calculation unit 140 may change the collection interval of the increase amount information when obtaining the variance. For example, the variance calculation unit 140 may register the increase amount information for N days in the increase amount table 112 and calculate the variance at different collection intervals. For example, the variance calculation unit 140 may calculate the variance focusing on the daily increase amount information, the variance focusing on the weekly increase amount information, and the variance focusing on the one month increase amount information. In this way, by changing the collection interval, the distribution at different collection intervals can be properly used according to the situation.

  The function of the congestion notification device included in the gateway 100 shown in the above-described embodiment is such that each function corresponding to the congestion notification device is mounted on an information processing device such as a known PC (Personal Computer) or PDA (Personal Digital Assistants). Can also be realized. FIG. 8 is a diagram illustrating a hardware configuration of a computer constituting the congestion notification device according to the embodiment.

  As illustrated in FIG. 8, the computer 200 includes a CPU 201 that executes various arithmetic processes, an input device 202 that receives data input from a user, and a display 203. The computer 200 also includes a medium reading device 204 that reads a program and the like from a storage medium, and an interface device 205 for connecting to other devices. The computer 200 also includes a wireless communication device 206 that is wirelessly connected to other devices, a RAM 207 that temporarily stores various types of information, and a hard disk device 208. Each device 201 to 208 is connected to a bus 209.

  The hard disk device 208 stores various programs such as an increase amount calculation program, a variance calculation program, a deviation value calculation program, and a warning notification program.

  The CPU 201 reads out each program stored in the hard disk device 208, develops it in the RAM 207, and performs various processes. Further, these programs can cause the computer to function as the increase amount calculation unit 130, the variance calculation unit 140, the deviation value calculation unit 150, and the warning notification unit 160 in FIG.

  The above program is not necessarily stored in the hard disk device 208. For example, the computer 200 may read and execute a program stored in a storage medium such as a CD-ROM. Each program may be stored in a storage device connected to a public line, the Internet, a LAN (Local Area Network), a WAN (Wide Area Network), or the like. In this case, the computer 200 may read and execute each program from these.

  The following supplementary notes are further disclosed with respect to the embodiments including the above examples.

(Appendix 1) A congestion notification method executed by a computer,
In an ad hoc network, based on the hop count data included in the packet received from the connected node, obtain the hop count for each node,
Based on the difference from the number of hops at the previous acquisition for each node, calculate the amount of increase in the route length,
Calculating a deviation value of variance regarding the increase in the path length;
A congestion notification method comprising: notifying a warning that a congestion state is present when the deviation value exceeds a predetermined value.

(Additional remark 2) When calculating | requiring the said dispersion | distribution, a dispersion | distribution is calculated | required for every collection interval, the deviation value of the calculated | required dispersion | distribution is calculated, and when the deviation value of dispersion | distribution exceeds a predetermined value, it is in a congestion state. The congestion notification method according to appendix 1, wherein a warning is notified.

(Supplementary Note 3) In an ad hoc network, based on data on the number of hops included in a packet received from a connection destination node, a communication unit that acquires the number of hops for each node;
An increase amount calculation unit that calculates an increase amount of the route length based on the difference from the hop count at the time of the previous acquisition for each node;
A variance calculating unit that calculates a variance related to an increase in the path length;
A deviation value calculation unit for calculating a deviation value of the variance;
A congestion notification device, comprising: a warning notification unit that outputs a warning to the effect of congestion when the variance deviation value exceeds a predetermined value.

(Additional remark 4) The said dispersion | distribution calculation part calculates | requires the dispersion | variation for every collection interval, The congestion notification apparatus of Additional remark 3 characterized by the above-mentioned.

(Appendix 5)
In an ad hoc network, based on the hop count data included in the packet received from the connected node, obtain the hop count for each node,
Based on the difference from the number of hops at the previous acquisition for each node, calculate the amount of increase in the route length,
Calculating a deviation value of variance regarding the increase in the path length;
A congestion notification program for executing a process of notifying a warning that a congestion state exists when the deviation value exceeds a predetermined value.

(Additional remark 6) When calculating | requiring the said dispersion | distribution, a dispersion | distribution value is calculated | required for every collection interval, the deviation value of the calculated | required dispersion | distribution is calculated, and when the deviation value of dispersion | distribution exceeds a predetermined value, it warns that it is in a congestion state. The congestion notification program according to appendix 5, characterized in that:

10a to 10h node 100 gateway 110 storage unit 120 communication unit 130 increase amount calculation unit 140 variance calculation unit 150 deviation value calculation unit 160 warning notification unit

Claims (4)

A congestion notification method executed by a computer,
In an ad hoc network, based on the hop count data included in the packet received from the connected node, obtain the hop count for each node,
Based on the difference from the number of hops at the previous acquisition for each node, calculate the amount of increase in the route length,
Calculating a deviation value of variance regarding the increase in the path length;
A congestion notification method comprising: notifying a warning that a congestion state is present when the deviation value exceeds a predetermined value.   When obtaining the variance, the variance is obtained at every collection interval, and the deviation value of the obtained variance is calculated. When the variance deviation value exceeds a predetermined value, a warning indicating that the state is congested is notified. The congestion notification method according to claim 1, wherein: In the ad hoc network, based on the hop count data included in the packet received from the connection destination node, a communication unit that acquires the hop count for each node;
An increase amount calculation unit that calculates the increase amount of the route length based on the difference from the hop count at the previous acquisition for each node,
A variance calculating unit that calculates a variance related to an increase in the path length;
A deviation value calculation unit for calculating a deviation value of the variance;
A congestion notification device, comprising: a warning notification unit that outputs a warning to the effect of congestion when the variance deviation value exceeds a predetermined value. On the computer,
In an ad hoc network, based on the hop count data included in the packet received from the connected node, obtain the hop count for each node,
Based on the difference from the number of hops at the previous acquisition for each node, calculate the amount of increase in the route length,
Calculating a deviation value of variance regarding the increase in the path length;
A congestion notification program for executing a process of notifying a warning that a congestion state exists when the deviation value exceeds a predetermined value.

Images