{'fraction_non_alphanumeric': 0.0214168039538715, 'fraction_numerical': 0.010223858901056303, 'mean_word_length': 5.041861826697892, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Mobile Agent Path-search Techniques using Genetic Algorithm

Transmission Control Protocol (TCP), the most widely used transmission protocol in the Internet, is used as a transmission protocol for various application programs such as File Transfer Protocol (FTP) and Hypertext Transfer Protocol (HTTP). TCP can transmit data reliably via congestion control techniques, which control the transmission rate according to the available bandwidth in the network, thereby preventing the network from congestion collapse. However, over a broadband wireless network, the congestion control algorithm in TCP increases the congestion window relatively slowly in comparison with the more rapid reduction that takes pace during packet loss, leading to insufficient utilization of broad bandwidth1. To solve this problem, networkadaptive transmission-rate adjustments have been proposed to transmit multimedia traffic efficiently by improving the congestion control algorithm in TCP2,3. Currently, Dijkstra’s algorithm is most commonly used to implement a shortest-path search algorithm, with proven reliability. However, due to the increasing number of network nodes and multimedia streaming transmission, which has a complex tree structure, network transmission delays have increased in proportion to the complexity of long computation time. This makes it difficult to cope dynamically with increases or decreases in receive nodes, changes in transmission amounts, and changes in transmission traffic. To resolve this issue, considerable research attention has been paid to shortest-path network configuration through the use of genetic algorithms or network configurations that imitate neural networks4,5. This paper proposes an alternative path search by dividing the network into cell units and then applying a genetic algorithm. The proposed algorithm is more advantageous than applying a genetic algorithm to an Abstract


Introduction
Transmission Control Protocol (TCP), the most widely used transmission protocol in the Internet, is used as a transmission protocol for various application programs such as File Transfer Protocol (FTP) and Hypertext Transfer Protocol (HTTP). TCP can transmit data reliably via congestion control techniques, which control the transmission rate according to the available bandwidth in the network, thereby preventing the network from congestion collapse. However, over a broadband wireless network, the congestion control algorithm in TCP increases the congestion window relatively slowly in comparison with the more rapid reduction that takes pace during packet loss, leading to insufficient utilization of broad bandwidth 1 . To solve this problem, networkadaptive transmission-rate adjustments have been proposed to transmit multimedia traffic efficiently by improving the congestion control algorithm in TCP 2,3 .
Currently, Dijkstra's algorithm is most commonly used to implement a shortest-path search algorithm, with proven reliability. However, due to the increasing number of network nodes and multimedia streaming transmission, which has a complex tree structure, network transmission delays have increased in proportion to the complexity of long computation time. This makes it difficult to cope dynamically with increases or decreases in receive nodes, changes in transmission amounts, and changes in transmission traffic. To resolve this issue, considerable research attention has been paid to shortest-path network configuration through the use of genetic algorithms or network configurations that imitate neural networks 4,5 .
This paper proposes an alternative path search by dividing the network into cell units and then applying a genetic algorithm. The proposed algorithm is more advantageous than applying a genetic algorithm to an entire network because it is able not only to shorten computation time but also to set up an alternative path that bypasses failed routers when specific routers are damaged. The proposed algorithm is able to determine directionality by using an existing shortest-distance algorithm (Dijkstra's algorithm). The study measures the level of convergence to Dijkstra's algorithm by applying a cell-unit genetic algorithm across the mobile agent environment. In addition, the study uses performance analysis to compare the delay time and cost associated with the proposed algorithm with delay time and cost for the Munetomo algorithm, an existing genetic algorithm. Finally, the study analyzes whether the proposed algorithm is better than existing genetic crossover operation-based routing algorithms in terms of alternative path setup, which may be required due to the abnormality of specific routers. Delay time and cost are measured accordingly.

Proposed Path-search Algorithm
With the mobile agent path-search technique, a genetic algorithm searches for the optimal path during routing using the directionality of the shortest-distance algorithm. A server searches routers across the pathway, using an agent controller to transmit information requested from a client, looking for the shortest distance between them. The proposed algorithm adds to this process by enabling cells that contain failed nodes to re-perform setup tasks via path modification on the client side during node failure. A server consists of services and their agent controls as well as a cell reiterate index that stores optimal paths in each cell. These are called elite groups. A client consists of a path modification module, which restores the failed nodes in a network, and a cell reiterate index, which stores the optimal paths obtained in each cell, as in the server. The selected path pays the lowest cost in clustertype cells by multiplying the cells via a specific distance of apothem inside the network. These cells are created by the proposed algorithm using C 1 , C 2 , C 3 , C 4 , ..., C n as shown in the Internet route, and C 31 , C 32 , C 33 , C 34 , ...C 3n , which are a group of routers duplicated between cells. Table 1 explains the function of each part in the structure of the proposed algorithm.

Operation Model
The basic operation of the proposed algorithm is as follows: (1) initialization is carried out; (2) cell multiplication takes Stores cells with optimal paths Stores router information duplicated within the control region between cells Stores the shortest-route information within the routers Stores the optimal paths within cells

Cell Reiterate Index
Stores cells with optimal paths Stores router information duplicated within the control region between cells Stores the shortest-route information within the routers Stores the optimal paths within cells App Program executed in the client, which has requested information from the server Responsible for receiving and utilizing requested information (application program) Sender Socket Responsible for sending the information requested from the server

Path Modification
Provides failure location tracking inside the network using the cell reiterate index place; and (3) the optimal path is calculated via a genetic algorithm inside the cells using agents located in each cell. These agents find the destination through a competition process that compares the optimal path and the adjacent cell. Figure 1 illustrates the process 6 .

Figure 1.
Flowchart of the proposed route-search algorithm.

Identifying the Shortest Distance
• Fitness function in the optimal solution The following process is carried out to evaluate the optimal solution after it has been located through the crossover process in the genetic algorithm, which is based on a single cluster.
In the proposed algorithm, the total time over the selected path is used as an evaluation criterion to find the optimal solution from the starting node to the finish node in the cluster.
The number of R n genes per unit of a single cluster is defined and the evaluation function of chromosome A, consisting of the above genes, is defined as follows: where, the Test S evaluation function evaluates the total time needed to configure a link that is contained in a single cluster; and where the Test T evaluation function refers to the total delay time in a router queue, which is contained in the link configured by generation. In addition: where, GLT refers to the time taken to form a link from the i -th chromosome (i-th node R i ) to the i+1-th node R i+1 Next: where, MD refers to the maximum delay between two nodes and RRD refers to the total sum of delay times in the intermediate routers between two nodes, which correspond to the i-th gene and i+1-th gene and the delay before the conversion into the i+2-th gene node, which corresponds to the i+1-th gene. Figure 2 compares optimal solutions obtained from the C 1 and C 2 cells through the optimal solution evaluation function from the viewpoint of the A 0 agent up to the boundary of the Cs 3 or Cs 4 cell along the optimal solution path, which comprises the dominant cells from the C 1 and C 2 cells. The above procedure is designed to increase the chance of finding the optimal solution through competition by cell region rather than following the optimal solution blindly within each cell. Within the C 1 and C 2 cells, in the region marked with deviant crease lines, which follow the optimal path reached up to the A 0 agent, the optimal solution path of each cell is calculated through the chromosome crossover process. The result is passed on to the A 0 agent, which evaluates the paths of two candidates through the optimal solution evaluation function. Based on the result, dominant paths are selected from candidate groups and the flow of the entire path is progressed up to its own cell ( A 0 ). The path defined above is then passed on to the A 1 agent of the selected cell. The A 1 agent applies the optimal path of its own cell region up to Cs 2 → Cs 4 . Using the process described above, an optimal solution is identified with the best performance among the optimal solution values in each cell through a competition process that is iteratively applied up to the destination 7 .

Setup of Alternative Paths within the Cell
The proposed algorithm sets up the optimal path within the cell through the crossover operation. In cases where the optimal path may be damaged, the path modification process stores paths by rank. The three-generation crossover result within the cell shows that althoughB3I = 2. 3, 4, 6, 7, 11, 15 is selected as the optimal path for packet transmission, an alternative path is set up where Router 6 is damaged (Figure 3). In the proposed algorithm, the next best path, bypassing Router 6, is identified through the path modification process. In Figure 3, we see that C3I = 1, 3, 4, 5, 12, 14, which is the second rank, is set up as the alternative path, which bypasses Router 6; packets are transmitted through this path. In this case, the setup can be carried out without the recalculation process, thus reducing delay time. As the existing Dijkstra's algorithm requires recalculation time whenever an alternative path is set up, the delay time in the alternative path setup process proposed in this study is more efficient.

Experimental Environment
The transmission delay and processing rate in the Munetomo genetic algorithm, and in Dijkstra's algorithm, which is the optimal path-search algorithm, were compared and analyzed in order to evaluate the performance of the genetic path-search algorithm proposed in this study. The simulation model for this experiment includes the basic elements required for configuration by taking the sensitivity of the network setup into account. Furthermore, a verified topology is extended to test the characteristics of mobile agents 9,10 .

Determination of the Cell Size Required for the Experiment
An appropriate cell size was selected for the simulation model over a hybrid topology environment with 300 routers. Four or more cells were used in the experiments with the proposed algorithm. Less than ten hops occurred if four or more cells were applied to the topology used in this experiment. With 11 or more hops, the 4 or more cells required in the experiment could not be formed, and were therefore unsuitable for the experimental environment. No overlap between cells was generated. With four hops or less, no overlap between cells could be generated and no control cells formed, again unsuitable for the experimental environment. To satisfy the needs of the experimental environment, the cell size had to include between five and ten hops. Since reliability is better when operation time is shorter, a cell size with five hops was selected. This has the shortest operation time.

Operation Delay Time
In this study, optimal solutions derived from Dijkstra's algorithm and the proposed algorithms were compared to measure optimal performance and convergence speed. The performance of the proposed genetic routing algorithm was also compared with the genetic algorithm suggested by Munetomo for use in configuring network topology. The performance analysis results are shown in Figure 4. Dijkstra's algorithm was selected as a performance analysis reference point between the two genetic algorithms analyzed in this study. As shown in Figure 4, the path setup delay was relatively longer for the proposed algorithm for up to 40 algorithm generations, which indicates that the proposed algorithm has a longer delay time than the Munetomo algorithm. After 50 generations, however, the proposed algorithm produced a significantly shorter delay time than the Munetomo algorithm, which converged closely to the routing delay produced by Dijkstra's algorithm. After 80 algorithm generations, the proposed algorithm converged to the reference path. The reason for the larger early delay time in the proposed algorithm in comparison with the Munetomo algorithm resulted from the selection of the agent groups needed to set up the initial routing path. Transmission delay was also caused by the need to identify the status of the nodes managed by each agent. Once this process was complete, the proposed algorithm had a shorter delay time than the Munetomo algorithm. Table 2 compares the performance of the routing algorithms.

Comparison of Path Processing Cost
To compare the path processing cost, an initial value was set by assigning a weight to each node from 110 to 160. The sum of weights in the existing Dijkstra's algorithm was 2.282 as a total path cost; the proposed algorithm was designed to have the optimal solution to converge at the path processing cost of Dijkstra's algorithm. The experiment results show that the total path cost for the Munetomo algorithm was 2.341, whereas that of the proposed algorithm was 2.297, which was 99.34%. The path cost of the Munetomo algorithm was 97.47%, as shown in Table 2. Thus, convergence performance in the proposed algorithm was higher than that of the Munetomo algorithm and it was also more robust.

Comparison of the Delay Time due to the Alternative Path Setup Operation
The operation time due to the alternative path setup process was compared for all three algorithms. The alternative path was set up owing to the failure Router 100 in the simulation topology. Figure 5 compares operation times due to the alternative path setup. As shown in the figure, the proposed algorithm, the Munetomo algorithm, and Dijkstra's algorithm produced an operational delay time of approximately 0.32 sec, 0.44 sec and 0.63 sec, respectively. This result indicates that the proposed algorithm is approximately twice as fast as Dijkstra's algorithm and approximately 37.5% faster than the Munetomo algorithm in terms of operation time due to the alternative path setup. This is because the proposed algorithm contains second rank path information in each cell, thereby reducing operation time when compared with the other algorithms.

Comparison of Alternative Path Processing Costs
When a specific router fails over the network path, an alternative path that bypasses the failed router needs to be set up. In this experiment, the alternative path setup in the proposed algorithm was compared with Dijkstra's and the Munetomo algorithm.
In the experiment, the alternative path was required because Router 100 failed in the simulation topology. Dijkstra's algorithm produced an alternative path of 102-168-169-177 to transmit packets. The Munetomo algorithm had the same alternative path.
The proposed algorithm set up the alternative path of 67-99-98-103. As shown in Figure 5, the number of routers that all three algorithms passed through was increased from two before the alternative path setup to three after the alternative path setup. In terms of cost, Dijkstra's and the Munetomo algorithm showed an increased cost of 146, whereas the proposed algorithm showed an increase of 115. This result means that the proposed algorithm has a cost of 31 less than Dijkstra's and the Munetomo algorithm. Therefore, based on the experiment result, the proposed algorithm is better than both the existing Munetomo algorithmand Dijkstra's algorithm, previously regarded as the optimal path setup algorithm, in terms of alternative path setup.
Total path cost after setting up the alternative path was 2,418 for the Dijkstra algorithm, 2,494 for the Munetomo algorithm, and 2,412 for the proposed algorithm. This result suggests that the proposed algorithm can reduce path setup cost, when compared with Dijkstra's algorithm, by a factor of 6 (0.63%) when an alternative path is set up. After the alternative path was set up, the proposed algorithm continued to show better optimality than Dijkstra's algorithm. In addition, the proposed algorithm reduced path setup cost by a factor 72 (3.25%) when compared with the Munetomo algorithm. This suggests that the optimality of the proposed algorithm is better  than can be achieved by this existing genetic algorithm. Thus, when an alternative path was set up to bypass failed nodes, the proposed algorithm proved its superiority over both Dijkstra's and the Munetomo algorithm in terms of optimality performance from the cost viewpoint. Figure  6 shows the alternative path setup and compares values when Router 100 failed.

Conclusion
In this paper, an existing genetic algorithm and mobile agents were analyzed. A new algorithm was built to improve the path-search function of existing genetic algorithms. The proposed path-search algorithm operates on a cell-unit basis, thereby shortening the distribution of operation processing time.
The execution process of the proposed algorithm works as follows: (1) a first cell is made, followed sequentially by a second, third, and fourth cell at the same location; (2) an agent is copied and transferred to this point; (3) each agent then calculates the shortest path of each cell; and (4) the optimal elements are identified through competition.
Since the proposed algorithm performed a cell-unit genetic operation during the setup process, it decreased delay time significantly after 50 generations when compared with the Munetomo genetic algorithm. That is, the proposed algorithm had a relatively long initial delay time during the early path search while transferring data through the TCP session connection over real network environments. However, the overall efficiency of the proposed algorithm was better than the other algorithms in terms of transmission.
Based on the performance analysis result, the proposed algorithm reduces total path cost by approximately 1.87% when compared with the Munetomo genetic algorithm. This result means that the proposed algorithm is more efficient than the Munetomo genetic algorithm. Compared with Dijkstra's algorithm, which is the current optimal path algorithm, the proposed algorithm had a longer initial operation time. However, after eight seconds, operation time converged to that of Dijkstra's algorithm. The proposed algorithm achieved 99.34% of the total path cost of Dijkstra's algorithm, which suggests a relatively successful convergence to the optimal path. In addition, path processing cost and operation time were analyzed for an alternative path setup that bypassed a failed router. The experimental results showed that the proposed algorithm reduced path processing costs caused by the alternative path setup by approximately 27% when compared with Dijkstra's and the Munetomo algorithm. Operation time for the alternative path setup was approximately twice as fast as that of Dijkstra's algorithm. These results suggest that the algorithm proposed in this paper is more efficient than either Dijkstra's or the Munetomo algorithm in terms of alternative path setup during router failure.