JP2010061274A - Communication method and device - Google Patents

Abstract

An optimal combination of setting values for each setting item for controlling data transmission can be found in a short time.
A transmitting device sets a set of individuals having a set value for each setting item for controlling data transmission as a gene as a first generation individual set (S1), and sets data for each individual included in the individual set. (S2), the receiver calculates the index (S2), the transmitter transmits the index value (S2), and the transmitter 1 calculates the fitness. A step (S3), a step (S4) for performing a crossover operation, a step (S5) for performing a mutation operation, and a step (S8) for replacing an individual having low fitness among individuals included in the individual set. .
[Selection] Figure 1

Description

  The present invention relates to a communication method and a communication apparatus. More specifically, the present invention relates to a communication method and a communication device for setting a setting value for each setting item for controlling data transmission in a data transmission system having a transmitting device and a receiving device using a genetic algorithm.

  In the present invention, “data” refers to packet data.

  The advanced communication function corresponding to the communication middleware has a function for guaranteeing communication service quality and a function for improving communication reliability. A plurality of setting items are prepared for these functions. Conventionally, the setting value for each setting item is determined by human judgment (Non-Patent Document 1).

Hiroyuki Yusa: Development of distributed real-time network architecture (DRNA) (Part 8)-Extension and application method of middleware for advanced communication function, Research Report R04029, November 2005

  However, the number of combinations of values that can be set for the advanced communication function is enormous. For example, when considering combinations, it is desirable to consider conditions such as the number and configuration of nodes in the communication network and the types of applications to be accommodated. In addition, these elements change in accordance with changes in equipment and business using the communication network. Therefore, if the setting values of each setting item in the advanced communication function can be automatically set, the operation management work of the advanced communication function can be made efficient.

  Therefore, the present invention provides a communication method and communication capable of quickly finding an optimal combination of setting values for each setting item for controlling data transmission in a data transmission system having a plurality of transmitting devices and at least one receiving device. An object is to provide an apparatus.

  While examining the setting method of various setting values in the communication middleware, the present inventors regard the setting value calculation problem as a combination optimization problem, and can use a genetic algorithm as a setting method of various setting values. It was found to be effective.

  Here, the combination optimization problem is a problem in which an optimal order or combination is determined from a plurality of options while satisfying various conditions (for example, the Japanese Society for Artificial Intelligence: Artificial Intelligence Dictionary, Kyoritsu Publishing, 2005). December). In general, the combinatorial optimization problem has a combinatorial increase in the number of elements that form a solution set as the problem size increases (also referred to as combinatorial explosion).

  A genetic algorithm is an algorithm that incorporates operations similar to the genetic mechanism in the evolution of organisms. In other words, considering the candidate solution as a gene, calculating the fitness to determine how well it fits the environment and conditions, crossover to combine different genes, mutations that change part of the solution, etc. It searches for the best solution for the conditions. Since the genetic algorithm itself is a well-known technique, details are omitted in this specification (see, for example, Nobuo Sannomiya et al .: Genetic Algorithm and Optimization, Asakura Shoten, 1998).

  The communication method according to claim 1 is based on original knowledge of the inventors and the like, and is a communication method for transmitting data from a plurality of transmission devices to at least one reception device, wherein the transmission device and the transmission device A step of generating a plurality of individuals having a set value for each setting item for controlling transmission of data to and from the receiving device as a gene and setting the set of individuals as a first generation individual set as an operation target individual set And a step in which the transmitting device transmits data for each combination of setting values for each setting item constituting each individual included in the operation target individual set, and the receiving device calculates an index for each individual based on the data transmission result A step in which the receiving device transmits an index value to the transmitting device, a step in which the transmitting device calculates fitness for each individual using the index value, and a transmitting device is preset. A step of performing a crossover operation on each individual included in the operation target individual set by selecting a crossing partner and a setting value to be crossed using a threshold value and fitness of the crossover probability, and a transmission device A step of performing a mutation operation based on a preset mutation occurrence probability for each new individual obtained as a result of crossover, and an individual having a low fitness among the individuals included in the operation target individual set And a step of adding a new individual as a result of the crossover and mutation operation and setting it as a new operation target individual set.

  The communication device according to claim 2 is a communication device including a plurality of transmission devices and at least one reception device that receives data from the transmission device, wherein the transmission device includes the transmission device and the reception device. Generating a plurality of individuals having a set value for each setting item for controlling transmission of data between and a set of the individuals as a first generation individual set and an operation target individual set; Means for transmitting data for each combination of setting values for each setting item constituting each individual included in the operation target individual set, and the receiving device displays an index for each individual based on the data transmission result Means for calculating, and means for transmitting an index value to the transmission device, the transmission device further calculating means for each individual using the index value, and a preset crossover probability Using threshold and fitness By selecting a crossover partner and selecting a set value for crossover, a means for performing a crossover operation on each individual included in the operation target individual set, and for each new individual as a result of crossover A means for performing a mutation operation based on a preset mutation occurrence probability, and deleting individuals with low fitness among the individuals included in the operation target individual set, and performing crossover and mutation operations. And a means for adding a new individual as a result and setting it as a new operation target individual set.

  Therefore, according to this communication method and communication apparatus, since the setting value for each setting item for controlling data transmission is determined using a genetic algorithm, for example, an optimum combination of setting values for each setting item The structure of the solution space is unknown or changes, or the number of setting items for controlling data transmission and the number or range of setting values for each setting item are large, so the setting value for each setting item is optimal. Even if it is not practical to perform a full search for a combination, an optimal combination of setting values for each setting item is efficiently searched in a short time.

  According to the communication method and the communication device of the present invention, it is possible to efficiently search for an optimal combination of setting values for each setting item in a short time by using a genetic algorithm. Therefore, it is possible to reduce the labor for setting the data transmission control and to improve the objectivity.

  Hereinafter, the configuration of the present invention will be described in detail based on the best mode shown in the drawings.

  1 to 5 show an example of an embodiment of a communication method and a communication apparatus according to the present invention. As shown in FIG. 2, the present invention is a setting item for controlling transmission of data D between a transmission device 1 and a reception device 2 in a data transmission system having a plurality of transmission devices 1 and at least one reception device 2. Each set value is determined.

  In the present invention, the calculation of the set value by the genetic algorithm is performed for each application. The present invention provides the transmitter 1 with an application that uses data transmission for system operation (hereinafter referred to as a system operation application) and an application that uses data transmission for equipment maintenance (hereinafter referred to as an equipment maintenance application). In this case, both cases are applicable. In the present invention, one set of individuals for operating the genetic algorithm is prepared for the system operation application and one for the equipment maintenance application. Further, even when the system operation application has a plurality of transmission devices, data transmission is performed using one individual set. The same applies when the equipment maintenance application has a plurality of transmission devices.

  As shown in FIG. 1, the communication method of the present invention is a communication method for transmitting data from a plurality of transmission apparatuses 1 to at least one reception apparatus 2, and the transmission apparatus 1 transmits the transmission apparatus 1 and the reception apparatus. A step of generating a plurality of individuals having a set value for each setting item for controlling transmission of data to and from the gene as a gene, and setting the set of individuals as a first generation individual set as an operation target individual set ( S1), and the transmission device 1 transmits data for each combination of setting values for each setting item constituting each individual included in the operation target individual set, and the reception device 2 uses the data transmission result to indicate an index for each individual. Calculating the index value to the transmitting apparatus 1 (S2: S2-1 to S2-4), and the transmitting apparatus 1 calculating the fitness for each individual using the index value (S3) And the transmitter Performs a crossover operation on each individual included in the operation target individual set by selecting a crossover partner and selecting a setpoint to be crossed using a preset crossover probability threshold and fitness. A step (S4: S4-1 to S4-6) and a step of performing a mutation operation based on a preset mutation occurrence probability for each new individual as a result of the crossover performed by the transmission apparatus 1 (S5) and deleting a low fitness individual among the individuals included in the operation target individual set, and adding a new individual as a result of the crossover and mutation operation and setting it as a new operation target individual set (S8: S8-1 to S8-2).

  The communication method can be realized as a communication device of the present invention. As shown in FIG. 3, the communication device 10 of the present invention is a communication device including a plurality of transmission devices 1 and at least one reception device 2 that receives data from the transmission device 1. However, a plurality of individuals having a set value for each setting item for controlling transmission of data between the transmitting device 1 and the receiving device 2 as genes are generated, and the set of the individuals is a first generation individual set. First generation setting unit 1a as means for setting as an operation target individual set, and data transmission unit as means for transmitting data for each combination of setting values for each setting item constituting each individual included in the operation target individual set 1b, and an index calculation unit 2a as a means for the reception apparatus 2 to calculate an index for each individual based on a data transmission result, and an index as a means for transmitting an index value to the transmission apparatus 1 Transmitter 2b And the transmission apparatus 1 further performs a crossover using a fitness calculation unit 1c as means for calculating the fitness for each individual using the index value, and a preset crossover probability threshold and fitness. A crossover execution unit 1d as a means for performing crossover operation on each individual included in the operation target individual set by selecting a partner and a set value to be crossover target, and a result of crossover A mutation execution unit 1e as a means for performing a mutation operation based on a mutation occurrence probability set in advance for each new individual, and an individual having a low fitness among the individuals included in the operation target individual set A next generation generation unit 1f as means for deleting and adding a new individual as a result of the crossover and mutation operation to set as a new operation target individual set.

  In executing the communication method by the communication device 10 of the present invention, first, the first generation setting unit 1a of the transmission device 1 prepares N individuals as initialization (S1).

  In the present invention, the setting values for the setting items for controlling data transmission are combined into individual sets, and the setting items for controlling the transmission of data between the transmitting device 1 and the receiving device 2 and each Ranges or candidates of values that the setting items can take as setting values are preset. Note that the number of setting items constituting an individual is not limited to a specific number, but is determined based on setting items that are considered useful for controlling data transmission.

  The setting item of the present invention is an item in which a setting value is determined when data transmission is controlled (in other words, the communication device 10 is operated), and the performance of the communication device 10 varies depending on the setting value employed. What is necessary is not limited to a specific item. Setting items for data transmission that can change the performance of the communication device 10 are roughly divided into those relating to the guarantee function of communication service quality and those relating to ensuring reliability. Specifically, for example, the following items can be considered.

I. Setting items related to the guarantee function of communication service quality 1) Aggregation Transmission is performed when a set unit time has elapsed or when an aggregation upper limit number of messages are collected. This brings about an effect of suppressing traffic as compared with the case of adding a header to an individual message. The following setting items exist for aggregation.
i) Unit time
ii) Aggregation limit (number of messages)
iii) Control unit (Choose one of the following)
-Sender application priority-Sender application type-Receiver node

2) Policing Received messages that exceed the set threshold in the set unit time are discarded. This brings about the effect of preventing the priority application from being affected by the concentration of processing loads. The following setting items exist for policing.
i) Unit time
ii) Message processing limit (number of messages)
iii) Allowable time limit
iv) Control unit (choose from one of the following)
-Sending-side application priority-Sending node and application combination-Receiving-side application type-Receiving-side template Among these, the overdue allowable time is the setting even if the processing time limit set by the sending-side application is exceeded. If it is a delay within the specified time, it is a threshold value for performing transmission. Therefore, a message that has exceeded the allowable time limit is discarded.

3) Shaping A message is transmitted within a set unit time within a range not exceeding the set upper limit. This brings about the effect of preventing the occurrence of burst traffic by leveling the message transmission timing. The following setting items exist for shaping.
i) Unit time
ii) Transmission limit (number of messages)
iii) Allowable time limit
iv) Control unit (choose from one of the following)
-Sending-side application priority-Sending-side application type-Combination of receiving node and application It should be noted that the meaning of the overdue allowable time is the same as in the case of policing.

4) Static priority control The order of processing is controlled according to the set priority. The priority once set is fixed. This has the effect of ensuring quality of service for applications that have strict requirements on delay times. Static priority control has only one priority (high / low) item.

5) Dynamic priority control The processing order is controlled so that applications set to low priority in static priority control can be executed as much as possible. The following setting items exist for dynamic priority control.
i) Threshold value used for judgment when raising priority
ii) Threshold used for judgment when lowering priority
iii) Time interval for recalculating priorities

6) Cache A function that stores a copy of data in a relay node having an advanced communication function, and passes this copy instead of the original data when the application needs the data. This brings about an effect of reducing traffic in the entire communication network. The cache has only one setting item related to the maximum data memory usage rate.

II. Setting items for ensuring reliability 1) Retransmission function with delivery confirmation In the transmission of the advanced communication function, the function of sending a message or the like to the receiving apparatus from the receiving apparatus to the transmitting side transmission is called delivery confirmation. The transmission apparatus performs retransmission when it does not receive a delivery confirmation within a waiting time after transmitting a message or the like. If the delivery confirmation cannot be received even if the maximum number of retransmissions is exceeded, a transmission error is notified to the application. The following setting items exist in the retransmission function with delivery confirmation.
i) Waiting time for receipt of delivery confirmation
ii) Maximum number of retransmissions

2) Retransmission function without delivery confirmation This function does not perform retransmission based on the above-mentioned delivery confirmation but performs retransmission based on a request from the receiving apparatus. In this case, the identifier of the missing data is sent from the receiving device to the transmitting device. The following setting items exist for the retransmission function without a delivery function.
i) Wait time until a retransmission request is made
ii) Maximum number of retransmission requests

3) Continuous transmission The continuous transmission function duplicates the same data and transmits it continuously at regular intervals. The continuous transmission function includes the following setting items in the transmission device.
i) Number of data to be copied
ii) Transmission interval

4) Two-route transmission By transmitting data through two different routes, even if a failure occurs in one of the routes, an effect that does not affect the communication of the application is brought about. In 2-route transmission, one of the following is selected for the configuration.
i) Always 2-route transmission configuration
ii) Regular and backup route configuration
iii) One route configuration

5) Late arrival discard This function is used in the receiving apparatus when the continuous transmission function or the two-route transmission function is selected in the transmitting apparatus. This function manages the sequence number of data that should always be received. Using this number and the set offset, it is classified into a number that can be received, a number that is discarded, and a number that is determined to be reset because of a large deviation. There are the following setting items in the receiving apparatus for the later arrival discard.
i) Receivable sequence number offset
ii) Sequence number offset to be discarded

6) Timeout confirmation There are two timeout confirmations, one related to method invocation and one related to transmission timeout. The time-out confirmation regarding the method call indicates the waiting time from when the method is called until the response is received because the method call in the advanced communication function is asynchronous communication. When this time is exceeded, an error is notified to the application. On the other hand, the transmission timeout is used as a timer when performing retransmission at a lower layer level. To summarize, the following setting items exist regarding timeout.
i) Remote method response waiting time
ii) Transmission timeout time

  In addition, a range of values or candidates that each setting item can take as a setting value are set. The range or candidate of the value that each setting item can take as a setting value is not limited to a specific range or value, and an operator sets an appropriate value for each setting item.

  Note that setting items for controlling data transmission between the transmission device 1 and the reception device 2 are set in advance in the first generation setting unit 1a of the transmission device 1.

  And the 1st generation setting part 1a selects a setting value at random from the setting value range or candidate of each setting item for every setting item which comprises an individual. The first generation setting unit 1a performs setting value selection processing for all setting items constituting one individual, combines the selected setting values into a set, and sets the combination of the set values as a gene. An individual having as is generated.

  The first generation setting unit 1a repeats the above-described individual generation process for the number of individuals that form an individual set to which the genetic algorithm is applied. In the present embodiment, the number of individuals forming the individual set is N. Further, an individual identifier for identifying each individual is assumed to be i (= 0, 1, 2,...).

  The number N of individuals forming the individual set is preset in the first generation setting unit 1a. Note that the number N of individuals forming the individual set is not limited to a specific number as long as it is equal to or greater than the number of setting items constituting the individual plus one.

  The first generation setting unit 1a generates as many individuals as necessary to form an individual set, and sets the formed individual set as an operation target individual set.

  Further, as initialization, a threshold (T) is set in advance for the crossover execution unit 1d of the transmission device 1. The threshold T of the crossover probability defines the crossover occurrence probability in the crossover process (S4), and is set to T∈ [0, 1] in the present embodiment.

  Next, the data transmission unit 1b of the transmission device 1 performs data transmission for each individual included in the operation target individual set using a combination of setting values for each setting item of the individual (S2: S2-1 to S2-1). S2-4).

  Specifically, the data transmission unit 1b first sets the counter of the individual identifier i to zero (that is, i = 0) (S2-1).

  Subsequently, the data transmission unit 1b determines whether or not the individual identifier i is less than the number N of individuals forming the operation target individual set (S2-2).

  When the individual identifier i is less than the number N of individuals (i.e., i <N), the data transmission unit 1b performs data transmission to obtain an index of each individual used for fitness calculation in the process of S3. In order to acquire a value, data is transmitted using a combination of setting values for each setting item constituting an individual of the individual identifier i of the operation target individual set (S2-3). In the process of S2-3, the same data is transmitted for all the combinations of setting values for each setting item constituting each individual included in the operation target individual set. Note that the data transmitted in the process of S2-3 may be test data or data that is actually transmitted and received by the application.

  In the process of S <b> 2-3, the index calculation unit 2 a of the reception device 2 calculates an index in accordance with data transmission from the transmission device 1.

In the present embodiment, based on the result of data transmission, the index calculation unit 2a of the reception device 2 includes an index in which three of the frame arrival rate f ₁ , the transmission delay time f ₂ , and the transmission delay fluctuation f ₃ are included in the objective function. Calculate as

The frame arrival rate f ₁ is a ratio of packets normally received among packets transmitted from all transmission nodes. Incidentally, in the fitness becomes higher relationship the larger the value of the frame arrival rate f _1.

The frame arrival rate f ₁ is calculated by Equation 1.
Here, Mr: number of receiving nodes, Ns: number of transmitting nodes.

The transmission delay time f ₂ is the average value of the transmission delay time in all packets transmitted in the communication network. Incidentally, as the fitness value of the transmission delay time f ₂ is small in the higher relationship.

Transmission delay time f ₂ is calculated by Equation 2.
Here, Np: the total number of transmitted packets.

The transmission delay fluctuation f ₃ is a value obtained by dividing the difference between the maximum latency and the average delay distortion at the maximum waiting time. Incidentally, as the fitness value of the transmission delay fluctuation f ₃ is smaller becomes higher relationship.

The transmission delay fluctuation f ₃ is calculated by Equation 3.

  The average delay fluctuation in Equation 3 is a value obtained by dividing an exponentially weighted moving average (expressed as Weighted Moving Average: EWMA) by the number of transmitting nodes.

The average delay fluctuation is calculated by Equation 4.
However, Jitter = EWMA _jitter (t)
= Α · | Packet arrival time-Expected value of packet arrival time |
+ (1-α) EWMA _jitter (t-1)
Here, Jitter _s : Jitter at transmission node s, Ns: number of transmission nodes, α: smoothing coefficient (0 ≦ α ≦ 1), t: measurement number (natural number).

  The EWMA at the measurement number t is calculated using the difference between the transmission delay and the expected packet arrival time and the value of the EWMA at the previous measurement number t &#8722; 1. As the expected packet arrival time value, a value obtained by dividing the packet size by the transmission band as an expected delay time and adding the time to the transmission time is used.

  In addition, the maximum waiting time in Expression 3 is a value indicating how many seconds to wait after the expected packet arrival time. For example, when the maximum waiting time is set to 1 second, it is considered that the packet is lost when the packet does not arrive at the receiving node even after 1 second has elapsed from the expected arrival time.

  Then, the index transmitting unit 2b of the receiving device 2 transmits to the transmitting device 1 a value for each index calculated by the index calculating unit 2a for each individual in accordance with data transmission from the transmitting device 1.

  Then, the data transmission unit 1b of the transmission device 1 that has received the value of each individual index of the individual identifier i from the reception device 2 adds 1 to the counter of the individual identifier i (ie, i = i + 1) (S2-4). The entire process is returned to the process of S2-2.

  When the individual identifier i is equal to or greater than the number of individuals N (i.e., i ≧ N) in the process of S2-2, the process proceeds to the process of S3, and the fitness calculation unit 1c of the transmission device 1 performs S2-3. In this process, the fitness of each individual is calculated using the value for each individual indicator included in the operation target individual set transmitted from the receiving device 2 (S3).

  The degree of fitness indicates how well the combination of setting values for each setting item that an individual has in the environment, in other words, how well the communication device 10 performs under the specific configuration and usage of the communication network. It represents what is being done.

  In the present embodiment, the relationship of “dominated / being governed” in multi-objective optimization is used for the fitness determination. Hereinafter, a fitness determination method using this relationship is referred to as a ranking method. Multi-objective optimization is generally formulated as a problem that satisfies Equation 5 when there are a plurality of indices and a plurality of constraints associated with them.

(Equation 5) Maximization: f _s (x) (s = 1, 2, 3,..., S)
However, g _t (x) ≦ 0 (t = 1, 2, 3,..., T)
However, h _u (x) = 0 (u = 1, 2, 3,..., U)
Where f _s (x): index, g _t (x) and h _u (x): constraints,
s: identifier indicating the type of index,
t and u: identifiers representing the types of constraints,
S: number of indicators, T and U: number of constraints.

Since multiple indices usually have a trade-off relationship, in multi-objective optimization, there are multiple optimal solutions (called Pareto solutions) for a given problem. A Pareto solution is a solution that is not controlled by other solutions. FIG. 4 shows an example in which there are two indicators f ₁ and f ₂ for this “dominate / dominated” relationship. In the example illustrated in FIG. 4, the indices f ₁ and f ₂ are indices that are evaluated as having higher fitness as the value is larger. In addition, I1, I2,..., I5 are individual identifiers.

As shown in FIG. 4, the individual I1 has a higher fitness than any other individual for indications f _1. At this time, it is said that the individual I1 is not controlled by other solutions. Similarly, individuals I2 is not dominated since higher fitness than any other individual for indications f _2. From the above, the individuals I1 and I2 are Pareto solutions. In contrast, individuals I3 is fitness (is namely dominated) inferior in both compared to individuals I1 index f ₁ and the index f _2. Therefore, the individual I3 is not a Pareto solution.

  In the present invention, the fitness F is calculated by Equation 6 using this “dominate / being controlled” relationship.

Where Fb = total number of individuals−number of individuals not controlled by the individual to be calculated.
d _i : Distance from the target individual to another individual i
The total number of other individuals: N _i

For example, when the fitness calculation unit 1c calculates the fitness F _I3 of the individual I3 in the case illustrated in FIG. 4, the individuals I1 and I2 are not controlled by the target individual I3. = 3 is calculated.

The fitness calculation unit 1c further calculates the sum Σd _i of the distance d _i from the target individual I3 to the other individual i. The distance here is the value obtained from the index, and the Euclidean distance between individuals when it is considered that the Euclidean space is formed. Therefore, the sum Σd _i of the distances d _i from the target individual I3 to the other individuals i is the sum of the distances d ₁ , d ₂ , d ₃ , and d ₄ shown in FIG.

Then, the fitness calculation unit 1c multiplies the variable Fb by the distance sum Σd _i . By multiplying the sum of distances Σd _i , the fitness of an individual away from other individuals is increased. Individuals with high fitness tend to remain in the next generation, and thus have the effect of maintaining the diversity of the population.

  Then, after the fitness calculation unit 1c calculates the fitness F for each individual included in the operation target individual set, the process proceeds to S4.

  Next, the crossover execution unit 1d of the transmission device 1 performs a crossover operation to generate an individual that is a descendant of each individual (S4: S4-1 to S4-6).

  Specifically, the crossover execution unit 1d first sets the counter of the individual identifier i to zero (i.e., i = 0) (S4-1).

  Further, the next generation generation unit 1f of the transmission device 1 sets the counter of the number of deleted individuals (j) to zero (that is, j = 0) (S4-1).

  Subsequently, the crossover execution unit 1d determines whether or not the individual identifier i is less than the number N of individuals forming the operation target individual set (S4-2).

  If the individual identifier i is less than the number N of individuals (i.e., i <N), the crossover execution unit 1d generates a random number (denoted k) (S4-3).

  The random number k is used to determine whether or not to perform crossover. In the present embodiment, the random number k∈ [is set in addition to the crossover probability threshold T∈ [0, 1] in the processing of S1. 0,1].

  Subsequently, the crossover execution unit 1d determines whether or not the generated random number k is equal to or smaller than the crossover probability threshold T (S4-4).

  When the random number k is equal to or less than the threshold T of the crossover probability, the crossover execution unit 1d performs crossover for the individual with the individual identifier i, and selects a partner for the individual (S4-5).

  The selection of the crossing partner when performing the crossing is performed based on the probability proportional to the fitness F calculated in the process of S3. Specifically, an individual obtained by dividing the fitness F of the individual by the sum of the fitness F of all individuals that are included in the operation target individual set and are candidates for crossover of the individual with the individual identifier i Is the probability of being selected as a crossover partner.

For the individual with the individual identifier i, all other individuals included in the operation target individual set are candidates for the crossover partner. Specifically, when the operation target individual set includes five individuals I1, I2, I3, I4, and I5, for example, the individuals I2, I3, I4, and I5 are used as crossover partners of the individual I1. Become a candidate. The cross execution unit 1d, when the fitness of individuals I2 is _{F I2,} fitness _{F I3} individuals I3, fitness _{F I4} individuals I4, fitness of individuals I5 is _{F I5,} for example The probability that the individual I2 will be the cross partner is calculated by F _I2 / (F _I2 + F _I3 + F _I4 + F _I5 ), and the probability that the individual I3 will be the cross partner is calculated by F _I3 / (F _I2 + F _I3 + F _I4 + F _I5 ) To do. Similarly, the crossover execution unit 1d calculates the probability of being a crossover partner for each individual included in the operation target individual set.

  The crossover execution unit 1d then probabilistically selects a crossover partner for each individual included in the operation target individual set based on the probability value of the crossover partner calculated for each individual for each crossover partner candidate.

  Subsequently, the crossover execution unit 1d performs crossover, that is, selection of genes to be left in the offspring between the individual with the individual identifier i and the individual selected as the crossover partner (S4-6). In the present invention, this gene selection is also performed based on the probability proportional to the fitness F for each individual calculated in the process of S3.

Specifically, the crossover execution unit 1d is the case where the crossover operation target is, for example, the individual I1 and the crossover partner is the individual I2 in the above example in which the operation target individual set includes five individuals. When the fitness of the individual I1 to be operated is F _I1 and the fitness of the individual I2 to be crossed is F _I2 , the probability that the gene of the individual I1 is selected is expressed as F _I1 / (F _I1 + F _I2 ) And the probability that the gene of the individual I2 is selected is calculated as F _I2 / (F _I1 + F _I2 ).

  The crossover method in the present invention is compared with roulette selection often used in genetic algorithms (for example, David E. Goldberg: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, January 1989). It has two characteristics.

  The first feature is that the crossing pool (ie, mating pool) of the present invention is not used. Paired pools are usually used to screen out individuals with low fitness when the number of individuals is large. However, the present invention aims to reduce the number of individuals as much as possible, and according to the method of the present invention, individuals with low fitness can be eliminated without using a pool of mating. In addition, when a pool with a small number of individuals is used, the possibility of falling into a local solution is increased, but the possibility can be lowered according to the crossover method of the present invention.

  The second feature is that only one child (that is, a new individual) is created in one crossover. Many genetic algorithms produce two children in a single crossover. In this case, since the paired pool is not used, one of the individuals as parents is selected regardless of fitness. Therefore, the probability that an individual with a low fitness level is selected is higher than when a paired pool is used. In order to prevent this effect from becoming strong, the present invention uses a single child created by one crossover.

  Next, the mutation execution unit 1e of the transmission device 1 performs a mutation operation on a new individual as a result of crossover in the process of S4-6 (S5).

  It should be noted that the mutation operation is performed only on a new individual as a result of crossover in the process of S4-6, and on an individual that has not been subjected to crossover (that is, crossover has not been performed). Is not done.

  The mutation execution unit 1e performs the determination as to whether or not each gene causes a mutation, which is an operation as a genetic algorithm, based on a fixed probability. The probability that a mutation will occur in the present invention is not limited to a specific value. Note that the value of the probability that a mutation will occur is preset in the mutation execution unit 1e.

  Then, the mutation executing unit 1e determines whether or not there is a mutation in each gene for each new individual as a result of crossover in the process of S4-6, and for the gene causing the mutation, A setting value selected from a range of possible setting values or candidates set in advance for the corresponding setting item is substituted. At this time, substitution of a set value for a gene having a mutation is randomly selected with the same probability for any set value.

  Next, the next generation generation unit 1f adds 1 to the counter of the deleted individual number j (that is, j = j + 1) (S6).

  Next, the crossover execution unit 1d adds 1 to the counter of the individual identifier i (that is, i = i + 1) (S7), and returns to the process of S4-2.

  On the other hand, if the random number k is larger than the crossover probability threshold value T in the process of S4-4, the crossover execution unit 1d proceeds to the process of S7 without performing the specific crossover process and the mutation process.

  If the individual identifier i is equal to or greater than the number of individuals N (i.e., i ≧ N) in the process of S4-2, the process proceeds to S8 (S8-1 to S8-2).

  Then, the next-generation generation unit 1f deletes the deleted individual number j of individuals included in the operation target individual set at the stage of executing the processing of S2 in order of decreasing fitness calculated in the processing of S3 ( S8-1).

  Further, the next generation generation unit 1f adds a new individual as a result of the crossover (S4-6) and mutation (S5) processing to the operation target individual set after the processing of S8-1, and after the addition Is set as a new operation target individual set (S8-2). The number of individuals added by the process of S8-2 is j. In addition, when the new operation target individual set obtained as a result of the processing up to S8-2 is made to correspond to the operation of the genetic algorithm, it becomes a next generation individual set for the operation target individual set at the stage of starting the processing of S2. Applicable.

  If necessary, the data transmission process by the communication apparatus 10 returns to the process of S2.

  It should be noted that the processing from S2 to S8 of the present invention may be executed repeatedly in succession, may be executed repeatedly at regular time intervals, or an index value is set in advance. It may be executed only when the threshold value is exceeded.

  And the communication apparatus 10 performs data transmission using the combination of the setting value for every setting item which comprises the individual | organism | solid with the highest fitness derived | led-out by the above process.

  According to the communication method and communication apparatus of the present invention having the above-described configuration, when searching for an optimal solution using a genetic algorithm, the sum of the Euclidean distances for a certain individual is large, and other individuals viewed from the index If the difference is large, the value for that individual will be small, and the next generation will be generated based on the fitness that is determined deterministically and objectively. The fitness can be calculated without doing so, and the versatility can be improved and the labor can be reduced. In addition, since a constant that is arbitrarily set is not included in the calculation of the fitness, the calculation of the fitness in the search for the optimal solution using the genetic algorithm can be performed deterministically and objectively. The stability of the solution can be improved and the reliability can be improved, and the optimum solution can be quickly obtained even for various settings.

  In addition, although the above-mentioned form is an example of the suitable form of this invention, it is not limited to this, In the range which does not deviate from the summary of this invention, various deformation | transformation implementation is possible. For example, in the present embodiment, in the calculation of fitness, a ranking method that uses the dominance relationship in multi-objective optimization is used. However, the present invention is not limited to this, and each index value calculated in the processing of S2 is used. A method of multiplying the weights and making the sum total the fitness of the individual (hereinafter referred to as a weighted sum method) may be used. That is, in this case, Expression 7 is used as an objective function for calculating the fitness F of the individual. Note that the weight ω in Equation 7 is appropriately set by increasing the weight of an index that is desired to be improved with priority on the relative importance of the index, that is, the optimization of the communication system.

Where ω: weight, f: index value,
s: identifier indicating the type of index (s = 1, 2,..., S), S: number of indices.

  In addition, in the calculation of fitness, a method using a cooperative element between applications (hereinafter referred to as an offset combination method) may be used. The cooperation in the present invention means that a certain application does not excessively optimize itself in consideration of the fitness of other applications. In this case, there is an effect of preventing adverse effects on other applications and instability of the operation of the entire system. The fitness of an individual when using a cooperative element is calculated by subtracting an offset indicating the degree of coordination from the fitness F calculated for each individual. Specifically, Formula 8 is used as the objective function.

[Equation 8] Fco = F-Offset
Here, Fco: fitness using cooperative elements, F: fitness, Offset: offset.

  The fitness F calculated by Equation 7 is used as the fitness F of Equation 8.

  Also, Offset in Equation 8 is the sum of weights multiplied by an index used when calculating the cooperation. Specifically, it is calculated using Equation 9.

Where Offset: offset, ωco _s : weight, fco _s : index value for offset calculation,
s: identifier indicating the type of index (s = 1, 2,..., S), S: number of indices.

  In this method, an index for calculating an offset used when one application X cooperates with another application Y is used. As this offset calculation index, for example, the following three indices can be considered. In calculating the value of any index, the individual index of the application X and the individual index of the application Y used for data transmission performed at the same time are used.

The first index is the difference fco ₁ in the application reach between the application Y and the application X. When the frame arrival rate of the application X is higher than that of the application Y, the offset value becomes large. In other words, the fitness level of the individual included in the application X becomes small and the individual becomes difficult to be transmitted to the offspring, so that the possibility of being used as a set value is low. This index is calculated using Equation 10.

[Expression 10] fco ₁ = f _{1, X} −f _{1, Y}
Here, f _{1, X} : Frame arrival rate of individual of application X, f _{1, Y} : Frame arrival rate of individual of application Y.

The second index is the difference fco ₂ in the ratio of the used bandwidth to the data size. In this case, the offset value becomes large when the use band of the application X is larger than the data size and the use band of the application Y is smaller than the data size. This index is calculated using Equation 11.

The third index is the difference fco ₃ in the ratio of the transmission delay time to the data size. In this case, the transmission delay time f _{2, X} application X is smaller than the data size transmission delay time f _{2, Y} application Y value of the offset becomes large when larger than the data size. This index is calculated using Equation 12.

  An embodiment of evaluation by simulation of data transmission of the communication method and communication apparatus of the present invention will be described with reference to FIGS. In this example, the simulation was performed using JNS (abbreviation of Java (registered trademark) Network Simulator; http://jns.sourceforge.net/).

  In this embodiment, the data transmission system configuration shown in FIG. 6 is assumed. Specifically, monitoring data D is transmitted from one substation T to three substations T1, T2, T3 (hereinafter, substations T1, T2, T3 are collectively referred to as substation T). Assumed. In each substation T, one substation server, which is a computer that plays a role in connection with the communication network, is arranged one by one for collecting data in the substation premises. It is assumed that one system operation and one facility maintenance application operate on a single substation server. Further, it is assumed that a single control center server is arranged in the control center C, and that one system operation application and one facility maintenance application operate on the control center server.

  In the communication network N between each substation T and the control station C, four IP routers R1, R2, R3, and R4 are connected in a loop.

  The parameters shown in Table 1 were used as parameters related to the system configuration. Of the parameters shown in Table 1, devices such as the operating frequency of the CPU and the communication band were set assuming realistic values. However, the data loss rate of the link in Ethernet (registered trademark) was set to a larger value than usual so as to affect the simulation result.

  As for applications, one typical data transmission was assumed for each of the system operation and facility maintenance applications.

  In addition, the number of message upper limit in policing and the number of message upper limit in shaping among the setting items related to the communication quality of service guarantee function, and the number of continuous transmissions and the number of transmission routes in the setting items for ensuring reliability are described in this embodiment. It was set as a setting item.

  Then, the message upper limit number in policing is 10, 20, 30, 40, 50, the message upper limit number in shaping is 10, 20, 30, 40, 50, the continuous transmission number is 1, 2, 3, 4, and the transmission For the number of routes, 1 and 2 were set as possible values for each setting item.

  Regarding the parameters related to the operation of the genetic algorithm, the number of individuals was 5, the crossover probability was 60%, and the mutation probability was 30%.

  Furthermore, the data transmission timing and the genetic algorithm operation timing of the grid operation application and facility maintenance application on one substation server are set as shown in FIG. That is, both applications of system operation and facility maintenance perform data transmission by using all the individuals (5) held once. Then, fitness calculation, crossover, and mutation, which are genetic algorithm operations, are performed using index values such as a frame arrival rate and a transmission delay time obtained as a result of data transmission when data transmission is performed five times. . Data transmission is performed again using the next-generation individuals obtained in this way. Since the transmission frequency is different between the grid operation application and the facility maintenance application, the frequency of operation of the genetic algorithm is also different. In this example, a simulation was performed in which this operation lasted for 75 minutes.

  In this embodiment, when the ranking method, which uses the dominance relationship in the multi-objective optimization, is used as the method for calculating the fitness of the individual in the process of S3, each index value is multiplied by a weight. A simulation was carried out for each of the case of using the weighted summation method, which is a method of using the summation as the fitness of the individual, and the case of using the offset combination method, which is a method of using cooperative elements between applications.

  Below, each result at the time of using said system in calculation of a fitness is demonstrated. In this embodiment, a plurality of simulations are carried out for any of the methods, and typical results among simulation results obtained by carrying out a plurality of times will be described below. In FIGS. 8 to 16 used in the following description, the horizontal axis represents the simulation time, and the vertical axis represents the magnitude of the index value. The symbol ◆ in the figure represents the result for the grid operation application, and the symbol ○ represents the result for the facility maintenance application.

(1) Results in the case of using the ranking method A simulation was performed using the ranking method in the calculation of fitness, and the results shown in FIG. 8 regarding the time transition of the frame arrival rate are shown in FIG. 9 regarding the time transition of the transmission delay time. The results shown in FIG. 10 were obtained with respect to the time transition of the transmission delay fluctuation. For the frame arrival rate shown in FIG. 8, the same simulation result is displayed with the scale of the Y-axis (frame arrival rate) scale changed.

  From the results shown in FIG. 8, it was confirmed that a frame arrival rate exceeding 99% was ensured in any application regarding the frame arrival rate.

  From the results shown in FIG. 9, it was confirmed that the transmission delay time is suppressed to a very short time if it stabilizes in any application although it takes some time until the transmission delay time is stabilized.

  From the results shown in FIG. 10, regarding transmission delay fluctuations, it was confirmed that in any application, although it took some time to stabilize, the transmission delay fluctuations were suppressed to a very short time if stabilized.

(2) Results when using the weighted summation method An individual set was provided for each individual application (system operation application and facility maintenance application). The weights of the objective function in the present embodiment are the frame arrival rate weight coefficient ω ₁ = 15, the transmission delay time weight coefficient ω ₂ = 10, and the transmission delay fluctuation weight coefficient ω ₃ = 5. In addition, the smoothing coefficient α = 0.8 used for the EWMA calculation when calculating the average delay fluctuation is set.

  In the calculation of fitness, a simulation is performed using the weighted sum method, and the results shown in FIG. 11 regarding the time transition of the frame arrival rate and the results shown in FIG. 12 regarding the time transition of the transmission delay time are the time transitions of the transmission delay fluctuation. The results shown in FIG.

  From the results shown in FIG. 11, it was confirmed that a frame arrival rate of 99.989% or more was secured in the system operation application with respect to the frame arrival rate. In addition, in equipment maintenance applications, it was confirmed that an arrival rate of 100% was secured for approximately 90% of communications, and an arrival rate of 99.985% was secured for the remaining communications.

  From the results shown in FIG. 12, it was confirmed that the transmission delay time was suppressed to about 0.165 seconds after stabilization in the grid operation application. In addition, in the equipment maintenance application, it was confirmed that the behavior was stable from the beginning and the transmission delay time was suppressed to about 0.07 to 0.13 seconds.

  From the results shown in FIG. 13, it was confirmed that the transmission delay fluctuation is almost stably changed in the system operation application. In addition, it was confirmed that the value was stable from the beginning of transmission in equipment maintenance applications.

(3) Results when using the offset combination method Similar to the case of using the weighted summation method, each individual application (system operation application and facility maintenance application) has an independent individual set. As in the case of using the weighted summation method, the weight of the objective function in this embodiment is the weight coefficient ω ₁ = 15 of the frame arrival rate, the weight coefficient ω ₂ = 10 of the transmission delay time, and the weight coefficient ω of the transmission delay fluctuation. ₃ = 5 and was. In addition, the smoothing coefficient α = 0.8 used for the EWMA calculation when calculating the average delay fluctuation is set. Further, regarding the weight used for the offset calculation, the weighting factor ωco ₁ = 10 for the difference in the frame arrival rate, the weighting factor ωco ₂ = 1 for the difference in the used bandwidth ratio, and the weighting factor ωco ₃ = 40 in the difference in the transmission delay time ratio did.

  In the calculation of fitness, a simulation is performed using the offset combination method, and the results shown in FIG. 14 for the time transition of the frame arrival rate and the results shown in FIG. 15 for the time transition of the transmission delay time are the time transitions of the transmission delay fluctuation. The results shown in FIG. 16 were obtained. For the frame arrival rate shown in FIG. 14, the same simulation result is displayed with the scale of the Y-axis (frame arrival rate) scale changed.

  From the results shown in FIG. 14, it was confirmed that a very high frame arrival rate was secured in any application regarding the frame arrival rate.

  From the results shown in FIG. 15, it was confirmed that the transmission delay time was stabilized within 10 minutes and the delay time was suppressed to a very short time in any application.

  As shown in FIG. 16, regarding the transmission delay fluctuation, it was confirmed that in any application, the transition was the same value as in the case of using the weighted summation method.

  From the above simulation results when using the ranking method, the weighted sum method, and the offset combination method in the calculation of the fitness of individuals, it is not observed that data transmission is significantly delayed with either method. According to the present invention, it was confirmed that appropriate data transmission is performed.

It is a flowchart explaining an example of embodiment of the communication method of this invention. It is a figure explaining the outline | summary of a structure of the data transmission system to which the communication method and communication apparatus of this invention are applied. It is a functional block diagram explaining an example of embodiment of the communication apparatus of this invention. It is a figure explaining the example of the dominance relationship of the multi-objective optimization in the fitness determination. It is a figure explaining the sum total of the Euclidean distance from the gene of calculation object to another gene. It is a figure explaining the outline | summary of a structure of the data transmission system of an Example. It is a figure explaining the timing of the data transmission of an Example, and the timing of the operation of a genetic algorithm. It is a figure which shows the time transition of the frame arrival rate about the simulation result using the ranking system of an Example. (A) shows the range of the frame arrival rate on the vertical axis in the range of 99.200 to 100.000 [%]. (B) shows the range of the frame arrival rate on the vertical axis in the range of 99.984 to 100.000 [%]. It is a figure which shows the time transition of the transmission delay time about the simulation result using the ranking system of an Example. It is a figure which shows the time transition of a transmission delay fluctuation about the simulation result using the ranking system of an Example. It is a figure which shows the time transition of a frame arrival rate about the simulation result using the weighted sum total system of an Example. It is a figure which shows the time transition of transmission delay time about the simulation result using the weighted sum total system of an Example. It is a figure which shows the time transition of a transmission delay fluctuation about the simulation result using the weighted sum total system of an Example. It is a figure which shows the time transition of a frame arrival rate about the simulation result using the offset combination system of an Example. (A) is the range in which the vertical axis frame arrival rate is 99.930 to 100.000 [%]. (B) shows the range of the frame arrival rate on the vertical axis in the range of 99.984 to 100.000 [%]. It is a figure which shows the time transition of transmission delay time about the simulation result using the offset combined use system of an Example. It is a figure which shows the time transition of a transmission delay fluctuation about the simulation result using the offset combination system of an Example.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Transmission apparatus 2 Reception apparatus 10 Communication apparatus

Claims (2)

  A communication method for transmitting data from a plurality of transmitting devices to at least one receiving device, wherein the transmitting device sets a setting value for each setting item that controls transmission of the data between the transmitting device and the receiving device. Generating a plurality of individuals as genes and setting the set of individuals as a first generation individual set as an operation target individual set; and the transmission apparatus configures each individual included in the operation target individual set Transmitting the data for each combination of setting values for each setting item, calculating the index for each individual based on the transmission result of the data, and receiving the device to the transmitting device A step of transmitting a value of the index, a step of calculating the fitness for each individual using the value of the index, and the transmission device being preset Performing a crossover operation on each individual included in the operation target individual set by selecting a crossover partner using the threshold value of the crossover probability and the fitness and selecting a setting value to be a crossover target; and A step of performing a mutation operation based on a mutation occurrence probability set in advance for each new individual as a result of the crossover performed by the transmission device; and among the individuals included in the operation target individual set And a step of deleting the individuals having low fitness and adding new individuals as a result of the crossover and mutation operations to be set as a new operation target individual set. .   A communication device comprising a plurality of transmission devices and at least one reception device that receives data from the transmission device, wherein the transmission device transmits the data between the transmission device and the reception device. Means for generating a plurality of individuals having a set value for each setting item to be controlled as a gene, and setting the set of individuals as a first generation individual set as an operation target individual set, and included in the operation target individual set Means for transmitting the data for each combination of setting values for each setting item constituting each individual, and the receiving device calculates an index for each individual based on the transmission result of the data And means for transmitting the value of the index to the transmission device, the transmission device further comprising means for calculating fitness for each individual using the value of the index, and a preset crossover. probability Means for performing a crossover operation on each individual included in the set of operation target individuals by selecting a crossover partner and a setting value to be crossed using a threshold and the fitness, and the crossover A means for performing a mutation operation based on a preset mutation occurrence probability for each new individual obtained as a result, and an individual having a low fitness among the individuals included in the operation target individual set. And a means for deleting and adding a new individual as a result of the operation of the crossover and the mutation and setting it as a new operation target individual set.