Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.

Mission-Oriented Configuration Model of Aircraft Carrying Spares and Dynamic Optimization Policy

Spare parts are critical to scheduled maintenance and fault repair,and can directly affect the readiness and combat capability of equipment.Equipment′s capacity of carrying spares is influenced by its storage space and scales,so it is necessary to consider economic factors,e.g.spares cost,as well as non-economic ones,such as spares volume,mass and scale,when optimizing spares configuration.Aiming at this problem,the optimization model based on multi-constraints for carrying spares is built by METRIC theory and system analysis.Through the introduction of Lagrange factors,the spares cost is transformed to shadow price,and the optimization method for carrying spares and the dynamic adjustment policy of Lagrange factors are proposed.The result of a given example is analyzed,and demonstrates that the proposed model can be optimized with all constraints,and the research can provide a new way for carrying spares optimization.

A novel and effective multi-constrained QoS routing scheme in WMNs

Multi-constrained quality of service(QoS)routing aims at finding an optimal path that satisfies a set of QoS parameters,as an NP complete problem,which is also a big challenge for wireless mesh networks(WMNs).Heuristic algorithms with polynomial and pseudo-polynomial-time complexities are often used to deal with this problem.However,existing solutions,most of which suffered either from excessive computational complexities or from low performance,were proposed only for wired networks and cannot be used directly in wireless mesh networks.In this paper,we propose a novel routing scheme based on mean field annealing(MFA-RS)to solve this problem.MFA-RS first uses a function of two QoS parameters,wireless link’s delay and transmission success rate as the cost function,and then seeks to find a feasible path by MFA.Because MFA-RS uses a set of deterministic equations to replace the stochastic process in simulated annealing(SA)and uses saddle point approximation in the calculation of the stationary probability distribution at equilibrium,the convergence time is much less than the routing scheme based on SA(SA-RS).Simulation results demonstrate that MFA-RS is an effective algorithm and is very fit for WMNs.

Optimization and analysis of winglet configuration for solar aircraft

Installing winglets can notably improve the aerodynamic performance of solar aircraft.This paper proposes a multi-constraints optimization method of winglets for solar aircraft,aiming to enhance the corresponding uninterrupted cruising capability.An optimization objective function is formed and is separately studied in aerodynamic and structural terms.Qualitative analysis shows that the winglet design parameters are restricted by four special constraints(geometry,aerodynamics,energy and stability)of solar aircraft.The optimization process is constructed on the basis of a multi-island genetic algorithm,and carried out for a 15 m wingspan solar aircraft.Although the designed winglet is not as good as the traditional winglet in terms of drag and structural weight,the designed winglet provides a better 24 h cruising capability.The sensitivity between the objective function and the design parameters is investigated,and the winglet effects vary with respect to the wing aspect ratio(AR=10,15,19.6).The effect of the constraints is analysed quantitatively,and some basic laws are obtained.Moreover,the feasible design region and the possible optimal design parameters of winglets for different wing configurations are explored.The calculation results show that when the aspect ratio exceeds a certain value,the winglets will not benefit the aircraft.