This paper introduces heuristic approaches and a deep reinforcement learning approach to solve a joint virtual network function deployment and scheduling problem in a dynamic scenario. We formulate the problem as an optimization problem. Based on the mathematical description of the optimization problem, we introduce three heuristic approaches and a deep reinforcement learning approach to solve the problem. We define an objective to maximize the ratio of delay-satisfied requests while minimizing the average resource cost for a dynamic scenario. Our introduced two greedy approaches are named finish time greedy and computational resource greedy, respectively. In the finish time greedy approach, we make each request be finished as soon as possible despite its resource cost; in the computational resource greedy approach, we make each request occupy as few resources as possible despite its finish time. Our introduced simulated annealing approach generates feasible solutions randomly and converges to an approximate solution. In our learning-based approach, neural networks are trained to make decisions. We use a simulated environment to evaluate the performances of our introduced approaches. Numerical results show that the introduced deep reinforcement learning approach has the best performance in terms of benefit in our examined cases.

The equilibrium optimizer (EO) is a novel physics-based meta-heuristic optimization algorithm that is inspired by estimating dynamics and equilibrium states in controlled volume mass balance models. As a stochastic optimization algorithm, EO inevitably produces duplicated solutions, which is wasteful of valuable evaluation opportunities. In addition, an excessive number of duplicated solutions can increase the risk of the algorithm getting trapped in local optima. In this paper, an improved EO algorithm with a bis-population-based non-revisiting (BNR) mechanism is proposed, namely BEO. It aims to eliminate duplicate solutions generated by the population during iterations, thus avoiding wasted evaluation opportunities. Furthermore, when a revisited solution is detected, the BNR mechanism activates its unique archive population learning mechanism to assist the algorithm in generating a high-quality solution using the excellent genes in the historical information, which not only improves the algorithm's population diversity but also helps the algorithm get out of the local optimum dilemma. Experimental findings with the IEEE CEC2017 benchmark demonstrate that the proposed BEO algorithm outperforms other seven representative meta-heuristic optimization techniques, including the original EO algorithm.

It is of great significance to design a stable and reliable routing protocol for Vehicular Ad Hoc Networks (VANETs) that adopt Vehicle to Vehicle (V2V) communications in the face of frequent network topology changes. In this paper, we propose a hybrid routing algorithm, RCRIQ, based on improved Q-learning. For an established cluster structure, the cluster head is used to select the gateway vehicle according to the gateway utility function to expand the communication range of the cluster further. During the link construction stage, an improved Q-learning algorithm is adopted. The corresponding neighbor vehicle is chosen according to the maximum Q value in the neighbor list. The heuristic algorithm selects the next-hop by the maximum heuristic function value when selecting the next-hop neighbor node. The above two strategies are comprehensively evaluated to determine the next hop. This way ensures the optimal selection of the next hop in terms of reachability and other communication parameters. Simulation experiments show that the algorithm proposed in this article has better performance in terms of routing stability, throughput, and communication delay in the urban traffic scene.

We proposed a population-based metaheuristic called the spy algorithm for solving optimization problems and evaluated its performance. The design of our spy algorithm ensures the benefit of exploration and exploitation as well as cooperative and non-cooperative searches in each iteration. We compared the spy algorithm with genetic algorithm, improved harmony search, and particle swarm optimization on a set of non-convex functions that focus on accuracy, the ability of detecting many global optimum points, and computation time. From statistical analysis results, the spy algorithm outperformed the other algorithms. The spy algorithm had the best accuracy and detected more global optimum points within less computation time, indicating that our spy algorithm is more robust and faster then these other algorithms.

Sharding is a solution to the blockchain scalability problem. A sharded blockchain divides consensus nodes (validators) into groups called shards and processes transactions separately to improve throughput and latency. In this paper, we analyze the rational behavior of users in account/balance model-based sharded blockchains and identify a phenomenon in which accounts (users' wallets and smart contracts) eventually get concentrated in a few shards, making shard loads unfair. This phenomenon leads to bad user experiences, such as delays in transaction inclusions and increased transaction fees. To solve this problem, we propose two load balancing methods in account/balance model-based sharded blockchains. Both methods perform load balancing by periodically reassigning accounts: in the first method, the blockchain protocol itself performs load balancing and in the second method, wallets perform load balancing. We discuss the pros and cons of the two protocols, and apply the protocols to the execution sharding in Ethereum 2.0, an existing sharding design. Further, we analyze by simulation how the protocols behave to confirm that we can observe smaller transaction delays and fees. As a result, we released the simulation program as “Shargri-La,” a simulator designed for general-purpose user behavior analysis on the execution sharding in Ethereum 2.0.

In network function virtualization (NFV) environments, service chaining is an emerging technology that enables network operators to provide network service dynamically and flexibly by using virtual network function (VNF). In the service chaining, a service chain is expected to be constructed based on VNF performances such as dependences among VNFs and traffic changing effects in VNFs. For achieving optimal data transmission services in NFV environments, we focus on the optimal service chain construction based on VNF performances so that both the maximum amount of traffic on links and the total number of VNF instances are decreased. In this paper, at first, an optimization problem is formulated for determining placements of VNFs and a route for each service chain. The service chains can be constructed by solving this optimization problem with an optimization software or meta-heuristic algorithm. Then, for the optimization problem, we propose a heuristic service chain construction algorithm. By using our proposed algorithm, the service chains can be constructed appropriately more quickly. We evaluate the performance of the proposed heuristic algorithm with simulation, and we investigate the effectiveness of the heuristic algorithm from the performance comparison. From some numerical examples, we show that the proposed heuristic algorithm is effective to decrease the amount of traffic and the number of VNF instances. Moreover, it is shown that our proposed heuristic algorithm can construct service chains quickly.

In this paper, in order to avoid the cascading failure by increasing the number of links in the physical network in D2D-based SNS, we propose an autonomous device placement algorithm. In this method, some relay devices are placed so as to increase the number of links in the physical network. Here, relay devices can be used only for relaying data and those are not SNS users. For example, unmanned aerial vehicles (UAV) with D2D communication capability and base stations with D2D communication capability are used as the relay devices. In the proposed method, at first, an optimization problem for minimizing node resilience which is a performance metric in order to place relay devices. Then, we investigate how relay devices should be placed based on some approximate optimal solutions. From this investigation, we propose an autonomous relay device placement in the physical network. In our proposed algorithm, relay devices can be placed without the complete information on network topology. We evaluate the performance of the proposed method with simulation, and investigate the effectiveness of the proposed method. From numerical examples, we show the effectiveness of our proposed algorithm.

In this paper, we aim to develop technologies for the circuit fault diagnosis and propose a formulation of a measure of a test pattern for the circuit fault diagnosis. Given a faulty circuit, the fault diagnosis is to deduce locations of faults that had occurred in the circuit. The fault diagnosis is executed in software before the failure analysis by which engineers inspect physical defects, and helps to improve the manufacturing process which yielded faulty circuits. The heart of the fault diagnosis is to distinguish between candidate faults by using test patterns, which are applied to the circuit-under-diagnosis (CUD), and thus test patterns that can distinguish as many faults as possible need to be generated. This fact motivates us to consider the test pattern measure based on the number of fault-pairs that become distinguished by a test pattern. To the best of the authors' knowledge, that measure requires the computational time of complexity order O(NF2), where NF denotes the number of candidate faults. Since NF is generally large for real industrial circuits, the computational time of the measure is long even when a high-performance computer is used. The formulation proposed in this paper makes it possible to calculate the measure in the computational complexity of O(NF log NF), and thus that measure is useful for the test pattern selection in the fault diagnosis. In computational experiments, the effectiveness of the formulation is demonstrated as samples of computational times of the measure calculated by the traditional and the proposed formulae and thorough comparisons between several greedy heuristics which are based on the measure.

The machine-to-machine (M2M) service network platform that accommodates and controls various types of Internet of Things devices has been presented. This paper investigates program file placement strategies for the M2M service network platform that achieve low blocking ratios of new task requests and accommodate as many tasks as possible in the dynamic scenario. We present four strategies for determining program file placement, which differ in the computation method and whether the relocation of program files being used by existing tasks is allowed or not. Simulation results show that a strategy based on solving a mixed-integer linear programming model achieves the lowest blocking ratio, but a heuristic algorithm-based strategy can be an attractive option by allowing recomputation of the placement when the placement cannot be obtained at the timing of new task request arrival.

In resource-constrained network function virtualization (NFV) environments, it is expected that data throughput for service chains is maintained by using virtual network functions (VNFs) effectively. In this paper, we formulate an optimization problem for maximizing the total data throughput in resource-constrained NFV environments. Moreover, based on our formulated optimization problem, we propose a heuristic service chain construction algorithm for maximizing the total data throughput. This algorithm also determines the placement of VNFs, the amount of resources for each VNF, and the transmission route for each service chain. It is expected that the heuristic algorithm can construct service chains more quickly than the meta-heuristic algorithm. We evaluate the performance of the proposed methods with simulations, and we investigate the effectiveness of our proposed heuristic algorithm through a performance comparison. Numerical examples show that our proposed methods can construct service chains so as to maximize the total data throughput regardless of the number of service chains, the amount of traffic, and network topologies.

Virtual network embedding has been intensively studied for a decade. The time complexity of most conventional methods has been reduced to the cube of the number of links. Since customers are likely to request a dense virtual network that connects every node pair directly (|E|=O(|V|2)) based on a traffic matrix, the time complexity is actually O(|E|3=|V|6). If we were allowed to reduce this dense network to a sparse one before embedding, the time complexity could be decreased to O(|V|3); the time saving would be of the order of a million times for |V|=100. The network reduction, however, combines several virtual links into a broader link, which makes the embedding cost (solution quality) much worse. This paper analytically and empirically investigates the trade-off between the embedding time and cost for the virtual network reduction. We define two simple reduction operations and analyze them with several interesting theorems. The analysis indicates that an exponential drop in embedding time can be achieved with a linear increase in embedding cost. A rigorous numerical evaluation justifies the desirability of the trade-off.

Inspired by the efficient proof procedures discussed in Computability logic [3],[5],[6], we describe a heuristic proof procedure for first-order logic. This is a variant of Gentzen sequent system [2] and has the following features: (a) it views sequents as games between the machine and the environment, and (b) it views proofs as a winning strategy of the machine. From this game-based viewpoint, a poweful heuristic can be extracted and a fair degree of determinism in proof search can be obtained. This article proposes a new deductive system LKg with respect to first-order logic and proves its soundness and completeness.

Aircraft landing scheduling (ALS) is one of the most important challenges in air traffic management. The target of ALS is to decide a landing scheduling sequence and calculate a landing time for each aircraft in terminal areas. These landing times are within time windows, and safety separation distances between aircraft must be kept. ALS is a complex problem, especially with a large number of aircraft. In this study, we propose a novel heuristic called CGIC to solve ALS problems. The CGIC consists of four components: a chunking rule based on costs, a landing subsequence generation rule, a chunk improvement heuristic, and a connection rule. In this algorithm, we reduce the complexity of the ALS problem by breaking it down into two or more subproblems with less aircraft. First, a feasible landing sequence is generated and divided into several subsequences as chunks by a chunking rule based on aircraft cost. Second, each chunk is regenerated by a constructive heuristic, and a perturbative heuristic is applied to improve the chunks. Finally, all chunks constitute a feasible landing sequence through a connection rule, and the landing time of each aircraft is calculated on the basis of this sequence. Simulations demonstrate that (a) the chunking rule based on cost outperforms other chunking rules based on time or weight for ALS in static instances, which have a large number of aircraft; (b) the proposed CGIC can solve the ALS problem up to 500 aircraft optimally; (c) in dynamic instances, CGIC can obtain high-quality solutions, and the computation time of CGIC is low enough to enable real-time execution.

The Machine-to-Machine (M2M) service network platform accommodates M2M communications traffic efficiently by using tree-structured networks and the computation resources deployed on network nodes. In the M2M service network platform, program files required for controlling devices are placed on network nodes, which have different amounts of computation resources according to their position in the hierarchy. The program files must be dynamically repositioned in response to service quality requests from each device, such as computation power, link bandwidth, and latency. This paper proposes a Program File Placement (PFP) method for the M2M service network platform. First, the PFP problem is formulated in the Mixed-Integer Linear Programming (MILP) approach. We prove that the decision version of the PFP problem is NP-complete. Next, we present heuristic algorithms that attain sub-optimal but attractive solutions. Evaluations show that the heuristic algorithm based on the number of devices that share a program file reduces the total number of placed program files compared to the algorithm that moves program files based on their position.

The elastic optical network (EON) is a promising new optical technology that uses spectrum resources much more efficiently than does traditional wavelength division multiplexing (WDM). This paper focuses on the routing, modulation level, spectrum and transceiver allocation (RMSTA) problems of the EON. In contrast to previous works that consider only the routing and spectrum allocation (RSA) or routing, modulation level and spectrum allocation (RMSA) problems, we additionally consider the transceiver allocation problem. Because transceivers can be used to regenerate signals (by connecting two transceivers back-to-back) along a transmission path, different regeneration sites on a transmission path result in different spectrum and transceiver usage. Thus, the RMSTA problem is both more complex and more challenging than are the RSA and RMSA problems. To address this problem, we first propose an integer linear programming (ILP) model whose objective is to optimize the balance between spectrum usage and transceiver usage by tuning a weighting coefficient to minimize the cost of network operations. Then, we propose a novel virtual network-based heuristic algorithm to solve the problem and present the results of experiments on representative network topologies. The results verify that, compared to previous works, the proposed algorithm can significantly reduce both resource consumption and time complexity.

Index generation functions model content-addressable memory, and are useful in virus detectors and routers. Linear decompositions yield simpler circuits that realize index generation functions. This paper proposes a balanced decision tree based heuristic to efficiently design linear decompositions for index generation functions. The proposed heuristic finds a good linear decomposition of an index generation function by using appropriate cost functions and a constraint to construct a balanced tree. Since the proposed heuristic is fast and requires a small amount of memory, it is applicable even to large index generation functions that cannot be solved in a reasonable time by existing heuristics. This paper shows time and space complexities of the proposed heuristic, and experimental results using some large examples to show its efficiency.

This paper proposes a novel multiple chaos embedded gravitational search algorithm (MCGSA) that simultaneously utilizes multiple different chaotic maps with a manner of local search. The embedded chaotic local search can exploit a small region to refine solutions obtained by the canonical gravitational search algorithm (GSA) due to its inherent local exploitation ability. Meanwhile it also has a chance to explore a huge search space by taking advantages of the ergodicity of chaos. To fully utilize the dynamic properties of chaos, we propose three kinds of embedding strategies. The multiple chaotic maps are randomly, parallelly, or memory-selectively incorporated into GSA, respectively. To evaluate the effectiveness and efficiency of the proposed MCGSA, we compare it with GSA and twelve variants of chaotic GSA which use only a certain chaotic map on a set of 48 benchmark optimization functions. Experimental results show that MCGSA performs better than its competitors in terms of convergence speed and solution accuracy. In addition, statistical analysis based on Friedman test indicates that the parallelly embedding strategy is the most effective for improving the performance of GSA.

Particle swarm optimizer network (PSON) is one of the multi-swarm PSOs. In PSON, a population is divided into multiple sub-PSOs, each of which searches a solution space independently. Although PSON has a good solving performance, it may be trapped into a local optimum solution. In this paper, we introduce into PSON a dynamic stochastic network topology called “PSON with stochastic connection” (PSON-SC). In PSON-SC, each sub-PSO can be connected to the global best (gbest) information memory and refer to gbest stochastically. We show clearly herein that the diversity of PSON-SC is higher than that of PSON, while confirming the effectiveness of PSON-SC by many numerical simulations.

Mapping instances to the Linked Open Data (LOD) cloud plays an important role for enriching information of instances, since the LOD cloud contains abundant amounts of interlinked instances describing the instances. Consequently, many techniques have been introduced for mapping instances to a LOD data set; however, most of them merely focus on tackling with the problem of heterogeneity. Unfortunately, the problem of the large number of LOD data sets has yet to be addressed. Owing to the number of LOD data sets, mapping an instance to a LOD data set is not sufficient because an identical instance might not exist in that data set. In this article, we therefore introduce a heuristic expansion based framework for mapping instances to LOD data sets. The key idea of the framework is to gradually expand the search space from one data set to another data set in order to discover identical instances. In experiments, the framework could successfully map instances to the LOD data sets by increasing the coverage to 90.36%. Experimental results also indicate that the heuristic function in the framework could efficiently limit the expansion space to a reasonable space. Based upon the limited expansion space, the framework could effectively reduce the number of candidate pairs to 9.73% of the baseline without affecting any performances.

Linked data entity resolution is the detection of instances that reside in different repositories but co-describe the same topic. The quality of the resolution result depends on the appropriateness of the configuration, including the selected matching properties and the similarity measures. Because such configuration details are currently set differently across domains and repositories, a general resolution approach for every repository is necessary. In this paper, we present cLink, a system that can perform entity resolution on any input effectively by using a learning algorithm to find the optimal configuration. Experiments show that cLink achieves high performance even when being given only a small amount of training data. cLink also outperforms recent systems, including the ones that use the supervised learning approach.