Energy aware proactive optimized link state routing in mobile ad-hoc networks

In this paper we develop a novel energy aware routing approach for mobile ad hoc network (MANET) problems. The approach is based on using Optimized Link State Routing Protocol. Our Energy Aware OLSR labeled as OLSR_EA measures and predicts per-interval energy consumptions using the well-known Auto-Regressive Integrated Moving Average time series method. We develop a composite energy cost, by considering transmission power consumption and residual energy of each node, and use this composite energy index as the routing metric. Our extensive ns2 simulation experiments show that OLSR_EA substantially prolongs the network lifetime and saves total energy used in MANET. In our experiments we considered different scenarios considering a variety of traffic loads, node mobilities, homogeneous power consumption, and heterogeneous power consumption. Simulation results also confirm that OLSR_EA improves the traffic balance between nodes, and packet delivery ratio in higher node speed. We further develop characteristics of OLSR_EA in power-wise heterogeneous MANET to achieve efficient energy preserving performance.     

Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods

This paper presents the investigation of an evolutionary multi-objective simulated annealing (EMOSA) algorithm with variable neighbourhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighbourhood search to find more non-dominated solutions in the Pareto front. Different neighbourhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed EMOSA algorithm with variable neighbourhoods is able to find high-quality non-dominated solutions for the problems tested. In particular, the neighbourhood structures that are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighbourhood.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

Possibility linear programming with trapezoidal fuzzy numbers

Fuzzy linear programming with trapezoidal fuzzy numbers (TrFNs) is considered and a new method is developed to solve it. In this method, TrFNs are used to capture imprecise or uncertain information for the imprecise objective coefficients and/or the imprecise technological coefficients and/or available resources. The auxiliary multi-objective programming is constructed to solve the corresponding possibility linear programming with TrFNs. The auxiliary multi-objective programming involves four objectives: minimizing the left spread, maximizing the right spread, maximizing the left endpoint of the mode and maximizing the middle point of the mode. Three approaches are proposed to solve the constructed auxiliary multi-objective programming, including optimistic approach, pessimistic approach and linear sum approach based on membership function. An investment example and a transportation problem are presented to demonstrate the implementation process of this method. The comparison analysis shows that the fuzzy linear programming with TrFNs developed in this paper generalizes the possibility linear programming with triangular fuzzy numbers.     

Heuristic solutions to the problem of routing school buses with multiple objectives

In this paper we address the problem of routing school buses in a rural area. We approach this problem with a node routing model with multiple objectives that arise from conflicting viewpoints. From the point of view of cost, it is desirable to minimise the number of buses used to transport students from their homes to school and back. From the point of view of service, it is desirable to minimise the time that a given student spends en route. The current literature deals primarily with single-objective problems and the models with multiple objectives typically employ a weighted function to combine the objectives into a single one. We develop a solution procedure that considers each objective separately and search for a set of efficient solutions instead of a single optimum. Our solution procedure is based on constructing, improving and then combining solutions within the framework of the evolutionary approach known as scatter search. Experimental testing with real data is used to assess the merit of our proposed procedure.     

Self-stabilizing algorithm for efficient topology control in Wireless Sensor Networks

Wireless Sensor Networks lifetime mainly depends on energy saving efficiency. In this paper, we propose an energy-efficient self-stabilizing topology control protocol for WSN. We reduce the transmission power of each node so as to maintain network connectivity while saving maximum energy. Besides, we propose an approximation algorithm for minimum weighted connected dominating set that builds a virtual backbone formed by sensors with maximum energy. This backbone is used for efficient routing purpose. We proved the algorithm correctness and through our simulation results, we showed the efficiency of our proposed solution.     

Optimizing the throughput,service rate,and buffer allocation in finite queueing networks

We examine the problem of maximizing the throughput of an acyclic network of general-service time queueing network while reducing the total number of buffers and the overall service rate.These are conflicting objectives and we utilize an original multi-objective genetic algorithm to tackle this problem.Promising preliminaries results show the efficacy of the approach.     

Autonomous localization based energy saving mechanism in indoor MANETs using ACO

The biggest challenge in MANETs is to find most efficient routing due to the changing topology and energy constrained battery operated computing devices. It has been found that Ant Colony Optimization (ACO) is a special kind of optimization technique having characterization of Swarm Intelligence (SI) which is highly suitable for finding the adaptive routing for such a type of volatile network. The proposed ACO routing algorithm uses position information and energy parameters as a routing metric to improve the performance and lifetime of network. Typical routing protocols have fixed transmission power irrespective of the distance between the nodes. Considering limiting factors, like small size, limited computational power and energy source, the proposed solution excludes use of GPS for identifying the distance between nodes for indoor MANETs. The distance between nodes can be determined by using Received Signal Strength Indicator (RSSI) measurements. Thus, an intelligent ACO routing algorithm with location information and energy metric is developed to adaptively adjust the transmission power and distribute the load to avoid critical nodes. Proposed Autonomous Localization based Eligible Energetic Path_with_Ant Colony Optimization (ALEEP_with_ACO) algorithm ensures that nodes in the network are not drained out of the energy beyond their threshold, as the load is shared with other nodes, when the energy of a node in the shortest path has reached its threshold. Hence, the total energy expenditure is reduced, thus prolonging the lifetime of network devices and the network. We simulated our proposal and compared it with the classical approach of AODV and other biological routing approaches. The results achieved show that ALEEP_with_ACO presents the best Packet Delivery Ratio (PDR), throughput and less packet drop specially under high mobility scenarios.     

Resource allocation in dynamic PERT networks with finite capacity

This article models the resource allocation problem in dynamic PERT networks with finite capacity of concurrent projects (COnstant Number of Projects In Process (CONPIP)), where activity durations are independent random variables with exponential distributions, and the new projects are generated according to a Poisson process. The system is represented as a queuing network with finite concurrent projects, where each activity of a project is performed at a devoted service station with one server located in a node of the network. For modeling dynamic PERT networks with CONPIP, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the completion time distribution for any particular project. Finally, we propose a multi-objective model with three conflict objectives to optimally control the resources allocated to the servers, and apply the goal attainment method to solve a discrete-time approximation of the original multi-objective problem.     

A self-tuning heuristic for a multi-objective vehicle routing problem

In this study, a heuristic free from parameter tuning is introduced to solve the vehicle routing problem (VRP) with two conflicting objectives. The problem which has been presented is the designing of optimal routes: minimizing both the number of vehicles and the maximum route length. This problem, even in the case of its single objective form, is NP-hard. The proposed self-tuning heuristic (STH) is based on local search and has two parameters which are updated dynamically throughout the search process. The most important advantage of the algorithm is the application convenience for the end-users. STH is tested on the instances of a multi-objective problem in school bus routing and classical vehicle routing. Computational experiments, when compared with the prior approaches proposed for the multi-objective routing of school buses problem, confirm the effectiveness of STH. STH also finds high-quality solutions for multi-objective VRPs.     

Reliable design of a logistics network under uncertainty: A fuzzy possibilistic-queuing model

This paper proposes a bi-objective model for designing a reliable network of bi-directional facilities in logistics network under uncertainties. For this purpose, the model utilizes an effective reliability approach to find a robust logistics network design. The objectives of the model are to minimize the total costs and the expected transportation costs after failures of bi-directional facilities of the logistics network. To solve the model, a new solution approach is proposed by combining queuing theory, fuzzy possibilistic programming and fuzzy multi-objective programming. Finally, the computational experiments are provided to illustrate the effectiveness of the proposed model and solution approach.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads

Four multi-objective meta-heuristic algorithms are presented to solve a multi-objective capacitated rural school bus routing problem with a heterogeneous fleet and mixed loads. Three objectives are considered: the total weighted traveling time of the students, the balance of routes among drivers, and the routing costs. The proposed methods were compared with one from the literature, and their performance assessed observing three multi-objective metrics: cardinality, coverage, and hyper-volume. All four devised methods outperformed the one from the literature. The algorithm with a path relinking procedure embedded during the crowding distance selection scheme had the best overall performance.     

Multi-objective vehicle routing problems

Routing problems, such as the traveling salesman problem and the vehicle routing problem, are widely studied both because of their classic academic appeal and their numerous real-life applications. Similarly, the field of multi-objective optimization is attracting more and more attention, notably because it offers new opportunities for defining problems. This article surveys the existing research related to multi-objective optimization in routing problems. It examines routing problems in terms of their definitions, their objectives, and the multi-objective algorithms proposed for solving them.     

The discrete-time queue with autoregressive inputs revisited

In this paper, we present an exact queuing analysis of a discrete-time queue whose arrival process is correlated and consists of a discrete autoregressive model of order 1 (DAR(1)). The functional equation describing this DAR(1)/D/1 queuing model, originally derived in Hwang and Sohraby (Queuing Systems 43 (2003)29–41), is manipulated and transformed into a mathematical tractable form. By using simple analytical transform techniques, we show how our proposed approach allows us to derive an equivalent (yet simpler) expression for the steady-state probability generating function (pgf) of the queue length, as originally derived in Hwang and Sohraby (Queuing Systems 43 (2003)29–41). From this pgf, we characterize the distribution of the packet delay. New numerical results related to packet loss ratio and mean delay of the DAR(1)/D/1 queue are also presented. The proposed approach outlines an alternate solution technique and a general framework under which more complex time-series based queuing models can be analyzed. AMS Subject Classifications 60K25     

A hybrid multi-objective artificial bee colony algorithm for burdening optimization of copper strip production

To achieve burdening process optimization of copper strips effectively, a nonlinear constrained multi-objective model is established on the principle of the actual burdening. The problem is formulated with two objectives of minimizing the total cost of raw materials and maximizing the amount of waste material thrown into melting furnace. In this paper, a novel approach called “hybrid multi-objective artificial bee colony” (HMOABC) to solve this model is proposed. The HMOABC algorithm is new swarm intelligence based multi-objective optimization technique inspired by the intelligent foraging behavior of honey bees, summation of normalized objective values and diversified selection (SNOV-DS) and nondominated sorting approach. Two test examples were studied and the performance of HMOABC is evaluated in comparison with other nature inspired techniques which includes nondominated sorting genetic algorithm II (NSGAII) and multi-objective particle swarm optimization (MOPSO). The numerical results demonstrate HMOABC approach is a powerful search and optimization technique for burdening optimization of copper strips.     

Exact hybrid algorithms for solving a bi-objective vehicle routing problem

The paper investigates a capacitated vehicle routing problem with two objectives: (1) minimization of total travel cost and (2) minimization of the length of the longest route. We present algorithmic variants for the exact determination of the Pareto-optimal solutions of this bi-objective problem. Our approach is based on the adaptive ε-constraint method. For solving the resulting single-objective subproblems, we apply a branch-and-cut technique, using (among others) a novel implementation of Held-Karp-type bounds. Incumbent solutions are generated by means of a single-objective genetic algorithm and, alternatively, by the multi-objective NSGA-II algorithm. Experimental results for a benchmark of 54 test instances from the TSPLIB are reported.     

Fractional Goal Programming for Fuzzy Solid Transportation Problem with Interval Cost

In this paper, we study a solid transportation problem with interval cost using fractional goal programming approach (FGP). In real life applications of the FGP problem with multiple objectives, it is difficult for the decision-maker(s) to determine the goal value of each objective precisely as the goal values are imprecise, vague, or uncertain. Therefore, a fuzzy goal programming model is developed for this purpose. The proposed model presents an application of fuzzy goal programming to the solid transportation problem. Also, we use a special type of non-linear (hyperbolic) membership functions to solve multi-objective transportation problem. It gives an optimal compromise solution. The proposed model is illustrated by using an example.     

满足路径约束的最优路算法

满足路径约束的最优路问题已被证明是NP-hard问题。本针对源点到宿点满足两个QoS(服务质量)度量的路由问题，给出一种保证时延的最小费用路由启发式算法。这个算法的优点是计算较简单、占用内存小、时间短。算法的复杂度是多项式的，表明算法是有效的。     

Robust delay-constrained routing in telecommunications

In telecommunications, operators usually use market surveys and statistical models to estimate traffic evolution in networks or to approximate queuing delay functions in routing strategies. Many research activities concentrated on handling traffic uncertainty in network design. Measurements on real world networks have shown significant errors in delay approximations, leading to weak management decisions in network planning. In this work, we introduce elements of robust optimization theory for delay modeling in routing problems. Different types of data uncertainty are considered and linked to corresponding robust models. We study a special case of constraints featuring separable additive functions. Specifically, we consider that each term of the sum is disturbed by a random parameter. These constraints are frequent in network based problems, where functions reflecting real world measurements on links are summed up over end-to-end paths. While classical robust formulations have to deal with the introduction of new variables, we show that, under specific hypotheses, the deterministic robust counterpart can be formulated in the space of original variables. This offers the possibility of constructing tractable robust models. Starting from Soyster’s conservative model, we write and compare different uncertainty sets and formulations offering each a different protection level for the delay constrained routing problem. Computational experiments are developed in order to evaluate the “price of robustness” and to assess the quality of the new formulations.