Improving time-efficiency in blocking expanding ring search for mobile ad hoc networks

We propose a new strategy for reducing the amount of latency and energy consumption in Blocking Expanding Ring Search (BERS) and enhanced Blocking Expanding Ring Search (BERS*) for mobile ad hoc networks (MANETs). BERS and BERS* are respectively energy and energy–time efficient route discovery protocols for MANETs as compared to conventional Expanding Ring Search (ERS). In this study, we identify unnecessary waiting time caused by a STOP/END instruction in BERS/BERS* and explore the potential of further improvement of their time efficiency. This leads to tBERS and tBERS*, the improved BERS and BERS* respectively. In tBERS/tBERS*, a route node may also issue the STOP/END instruction to terminate flooding. We implement this idea in algorithms, conduct analysis, and achieve further latency reduction in both tBERS and tBERS* as well as the energy saving in tBERS*.     

On the interrelation of the basic laws of continuum mechanics

It has been shown by the present authors in a recent paper [1] that if some conservation and balance laws of continuum mechanics are represented in a 4 × 4 form, balance of linear physical momentum (i. e., stress) and balance of mass become closely linked. This seemingly novel result was reached in a completely ad‐hoc fashion by treating time on the same level as the spatial coordinates, and not as parameter, as it is usually done. In order to place the above ad‐hoc result on a firmer foundation and since it is in the theory of relativity that space and time are considered on the same footing, an attempt is made to derive several tensors of continuum mechanics in a systematic manner as 4 × 4 invariant objects.     

Analytical Studies of Energy–Time Efficiency of Blocking Expanding Ring Search

This paper investigates the energy–time efficiency of the Blocking Expanding Ring Search algorithms (BERS) using an extended graph model. BERS is an energy efficient alternative that was developed recently based on the Expanding Ring Search (ERS). ERS is widely applied in reactive routing protocols for mobile ad hoc networks. Most studies in this area focus on minimising either energy consumption or search latency, but few look into the strong correlation between the energy saving and the increased latency incurred. We analyse, in this study, the concurrency mechanism of BERS and have developed BERS*, an enhanced scheme based on BERS. Our results show that, among the three schemes (BERS*, BERS and ERS), BERS* incurs the least latency when the hop number of the route nodes is greater than 3, and has achieved the best performance in terms of energy–time efficiency when the hop number of the route nodes is greater than 7. We have also discovered the conditions that allow collective optimisation of BERS* and ERS.     

Stock market forecasting by using a hybrid model of exponential fuzzy time series

The initial aim of this study is to propose a hybrid method based on exponential fuzzy time series and learning automata based optimization for stock market forecasting. For doing so, a two-phase approach is introduced. In the first phase, the optimal lengths of intervals are obtained by applying a conventional fuzzy time series together with learning automata swarm intelligence algorithm to tune the length of intervals properly. Subsequently, the obtained optimal lengths are applied to generate a new fuzzy time series, proposed in this study, named exponential fuzzy time series. In this final phase, due to the nature of exponential fuzzy time series, another round of optimization is required to estimate certain method parameters. Finally, this model is used for future forecasts. In order to validate the proposed hybrid method, forty-six case studies from five stock index databases are employed and the findings are compared with well-known fuzzy time series models and classic methods for time series. The proposed model has outperformed its counterparts in terms of accuracy.     

Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs

A wireless MANET is a collection of wireless mobile hosts that dynamically create a temporary network without a fixed infrastructure. The topology of the network may change unpredictably and frequently. Therefore, multicast routing in ad hoc networks is a very challenging problem. This paper proposes a multi-constrained QoS multicast routing method using the genetic algorithm. The proposal will be flooding-limited using the available resources and minimum computation time in a dynamic environment. By selecting the appropriate values for parameters such as crossover, mutation, and population size, the genetic algorithm improves and tries to optimize the routes. Simulation results indicate its better performances compared to other methods.     

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.     

A biobjective optimization model for routing in mobile ad hoc networks

In this paper, the problem of finding optimal paths in mobile ad hoc networks is addressed. More specifically, a novel bicriteria optimization model, which allows the energy consumption and the link stability of mobile nodes to be taken into account simultaneously, is presented. In order to evaluate the validity of the proposed model, a greedy approach is devised. Some preliminary computational experiments have been carried out, in a simulation environment. The numerical results are very encouraging, showing the correctness of the proposed model. Indeed, the selection of a shorter route leads to a more stable route, but to a greater energy consumption. On the other hand, if longer routes are selected the route fragility is increased, but the average energy consumption is reduced.     

Location tracking in mobile ad hoc networks using particle filters

Mobile ad hoc networks (MANETs) are dynamic networks formed on-the-fly as mobile nodes move in and out of each others' transmission ranges. In general, the mobile ad hoc networking model makes no assumption that nodes know their own locations. However, recent research shows that location-awareness can be beneficial to fundamental tasks such as routing and energy-conservation. On the other hand, the cost and limited energy resources associated with common, low-cost mobile nodes prohibits them from carrying relatively expensive and power-hungry location-sensing devices such as GPS. This paper proposes a mechanism that allows non-GPS-equipped nodes in the network to derive their approximated locations from a limited number of GPS-equipped nodes. In our method, all nodes periodically broadcast their estimated location, in terms of a compressed particle filter distribution. Non-GPS nodes estimate the distance to their neighbors by measuring the received signal strength of incoming messages. A particle filter is then used to estimate the approximated location, along with a measure of confidence, from the sequence of distance estimates. Simulation studies show that our solution is capable of producing good estimates equal or better than the existing localization methods such as APS-Euclidean for the more difficult scenario when the network connectivity is low.     

Linear-time computation of optimal subgraphs of decomposable graphs

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well-known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We suggest a general approach for constructing linear-time algorithms in the case where the graph G is defined by certain rules of composition (as are trees, series-parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a property that is “regular” with respect to these rules of composition (as do matchings, dominating sets, and independent sets for all the classes just mentioned). This approach is applied to obtain a linear-time algorithm for computing the irredundance number of a tree, a problem for which no polynomial-time algorithm was previously known.     

A fast genetic method for inducting descriptive fuzzy models

Under certain inference mechanisms, fuzzy rule bases can be regarded as extended additive models. This relationship can be applied to extend some statistical techniques to learn fuzzy models from data. The interest in this parallelism is twofold: theoretical and practical. First, extended additive models can be estimated by means of the matching pursuit algorithm, which has been related to Support Vector Machines, Boosting and Radial Basis neural networks learning; this connection can be exploited to better understand the learning of fuzzy models. In particular, the technique we propose here can be regarded as the counterpart to boosting fuzzy classifiers in the field of fuzzy modeling. Second, since matching pursuit is very efficient in time, we can expect to obtain faster algorithms to learn fuzzy rules from data. We show that the combination of a genetic algorithm and the backfitting process learns faster than ad hoc methods in certain datasets.     

Research on permutation flow shop scheduling problems with general position-dependent learning effects

Machine learning exists in many realistic scheduling situations. This study focuses on permutation flow shop scheduling problems, where the actual processing time of a job is defined by a general non-increasing function of its scheduled position, i.e., general position-dependent learning effects. The objective functions are to minimize the total completion time, the makespan, the total weighted completion time, and the total weighted discounted completion time, respectively. To solve these problems, we present approximation algorithms based on the optimal permutations for the corresponding single machine scheduling problems and analyze their worst-case error bound.     

Single machine scheduling with exponential learning functions

In this paper we consider the single machine scheduling problem with exponential learning functions. By the exponential learning functions, we mean that the actual job processing time is a function of the total normal processing times of the jobs already processed. We prove that the shortest processing time (SPT) rule is optimal for the total lateness minimization problem. For the following three objective functions, the total weighted completion time, the discounted total weighted completion time, the maximum lateness, we present heuristic algorithms according to the corresponding problems without exponential learning functions. We also analyse the worst-case bound of our heuristic algorithms. It also shows that the problems of minimizing the total tardiness and discounted total weighted completion time are polynomially solvable under some agreeable conditions on the problem parameters.     

On reductions for the Steiner Problem in Graphs

Several authors have demonstrated how reductions can be used to improve the efficiency with which the Steiner Problem in Graphs can be solved. Previous reduction algorithms have been largely ad hoc in nature. This paper uses a theory of confluence to show that, in many cases, all maximal reduction sequences are equivalent, gaining insights into the design of reduction algorithms that obtain a maximum degree of reduction.     

Multidomain spectral method for the Gauss hypergeometric function

Numerical Algorithms - Differentiation matrices are in wide use in numerical algorithms, although usually studied in an ad hoc manner. We collect here in this review paper elementary properties of...     

Toward a Reliable and Resilient Mobile Wireless Architecture

Abstract

Hybrid mobile wireless architectures that combine the advantages of ad hoc (mobile nodes) and cellular models provide “communications-on-the-move” services with enhanced flexibility and stability. In this article, we investigate the resiliency of such architectures by considering strategies for optimal deployment (number and location) of backup routers that would ensure reliable performance in such interdependent mobile systems.     

A Bayesian algorithm for global optimization

A crucial step in global optimization algorithms based on random sampling in the search domain is decision about the achievement of a prescribed accuracy. In order to overcome the difficulties related to such a decision, the Bayesian Nonparametric Approach has been introduced. The aim of this paper is to show the effectiveness of the approach when an ad hoc clustering technique is used for obtaining promising starting points for a local search algorithm. Several test problems are considered.     

A stochastic fluid model for an ad hoc mobile network

In conventional mobile telephone networks, users communicate directly with a base station, via which their call is transferred to the recipient. In an ad hoc mobile network, there is no base-station infrastructure and users need to communicate between themselves, either directly if they are close enough, or via transit nodes if they are not. A number of interesting questions immediately arise in the modeling of ad hoc mobile networks. One that has received attention in the literature concerns how to encourage users to act as transit nodes for calls that they are not partaking in. Solutions to this problem have involved each user maintaining a ‘credit balance’ which is increased by forwarding transit calls and decreased by transmitting one’s own calls. A second question concerns the ‘amount of resource’ that a network needs in order to be able to operate with a reasonable quality of service. We shall consider this question by modeling each user’s battery energy and credit balance as fluids, the rate of increase or decrease of which is modulated by the network occupancy. This results in a network of stochastic fluid models, each modulated by the same background process. In this paper, we shall assume that there is no bound on the energy or the credit that a user’s handset can accumulate. Using this model, we can calculate the critical rates of recharge that are necessary and sufficient to guarantee that no calls are lost. For recharge rates less than the critical values, we propose a reduced-load approach to the analysis of the network.     

On an expansion of nondeterministic finite automata

We consider a possible generalization of nondeterministic finite automata. The goals of this consideration are: to apply some obtained algorithms for various problems of minimization of classical nondeterministic automata; to use such automata for describing practical anytime algorithms for the same problems of minimization; to simplify some proofs for algorithms of simplification for usual nondeterministic automata.     

Performance Analysis for Mobile Ad Hoc Network in Random Graph Models with Spatial Reuse

In this paper,we present a random graph model with spatial reuse for a mobile ad hoc network(MANET) based on the dynamic source routing protocol.Many important performance parameters of theMANET are obtained,such as the average flooding distance (AFD),the probability generating function of theflooding distance,and the probability of a flooding route to be symmetric.Compared with the random graphmodel without spatial reuse,this model is much more effective because it has a smaller value of AFD and alarger probability for finding a symmetric valid route.     

A new memetic algorithm based on cellular learning automata for solving the vertex coloring problem

Vertex coloring problem is a combinatorial optimization problem in graph theory in which a color is assigned to each vertex of graph such that no two adjacent vertices have the same color. In this paper a new hybrid algorithm which is obtained from combination of cellular learning automata (CLA) and memetic algorithm (MA) is proposed for solving the vertex coloring problem. CLA is an effective probabilistic learning model combining cellular automata and learning automaton (LA). Irregular CLA (ICLA) is a generalization of CLA in which the restriction of rectangular grid structure in CLA is removed. The proposed algorithm is based on the irregular open CLA (IOCLA) that is an extension of ICLA in which the evolution of CLA is influenced by both local and global environments. Similar to other IOCLA-based algorithms, in the proposed algorithm, local environment is constituted by neighboring LAs of any cell and the global environment consists of a pool of memes in which each meme corresponds to a certain local search method. Each meme is represented by a set of LAs from which the history of the corresponding local search method can be extracted. To show the superiority of the proposed algorithm over some well-known algorithms, several computer experiments have been conducted. The results show that the proposed algorithm performs better than other methods in terms of running time of algorithm and the required number of colors.