G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks

The performance of Multi-Radio Multi-Channel Wireless Mesh Networks (MRMC-WMNs) based on the IEEE 802.11 technology depends significantly on how the channels are assigned to the radios and how traffic is routed between the access points and the gateways. In this paper we propose an algorithmic approach to this problem, for which, as far as we know, no optimal polynomial time solutions have been put forward in the literature. The core of our scheme consists of a sequential divide-and-conquer technique which divides the overall Joint Channel Assignment and Routing (JCAR) problem into a number of local optimization sub-problems that are executed sequentially. We propose a generalized scheme called Generalized Partitioned Mesh network traffic and interference aware channeL Assignment (G-PaMeLA), where the number of sub-problems is equal to the maximum number of hops to the gateway, and a customized version which takes advantage of the knowledge of the topology. In both cases each sub-problem is formulated as an Integer Linear Programming (ILP) optimization problem. An optimal solution for each sub-problem can be found by using a branch-and-cut method. The final solution is obtained after a post-processing phase, which improves network connectivity. The divide-and-conquer technique significantly reduces the execution time and makes our solution feasible for an operational WMN. With the help of a detailed packet level simulation, the G-PaMeLA technique is compared with several state-of-the-art JCAR algorithms. Our results highlight that G-PaMeLA performs much better than the others in terms of packet loss rate, collision probability and fairness among traffic flows.     

Parameter estimation for crop growth model using evolutionary and bio-inspired algorithms

All dynamic crop models for growth and development have several parameters whose values are usually determined by using measurements coming from the real system. The parameter estimation problem is raised as an optimization problem and optimization algorithms are used to solve it. However, because the model generally is nonlinear the optimization problem likely is multimodal and therefore classical local search methods fail in locating the global minimum and as a consequence the model parameters could be inaccurate estimated. This paper presents a comparison of several evolutionary (EAs) and bio-inspired (BIAs) algorithms, considered as global optimization methods, such as Differential Evolution (DE), Covariance Matrix Adaptation Evolution Strategy (CMA-ES), Particle Swarm Optimization (PSO) and Artificial Bee Colony (ABC) on parameter estimation of crop growth SUCROS (a Simple and Universal CROp Growth Simulator) model. Subsequently, the SUCROS model for potential growth was applied to a husk tomato crop (Physalis ixocarpa Brot. ex Horm.) using data coming from an experiment carried out in Chapingo, Mexico. The objective was to determine which algorithm generates parameter values that give the best prediction of the model. An analysis of variance (ANOVA) was carried out to statistically evaluate the efficiency and effectiveness of the studied algorithms. Algorithm's efficiency was evaluated by counting the number of times the objective function was required to approximate an optimum. On the other hand, the effectiveness was evaluated by counting the number of times that the algorithm converged to an optimum. Simulation results showed that standard DE/rand/1/bin got the best result.     

Design of an energy-absorbing structure using topology optimization with a multimaterial model

To accommodate the dual objectives of many engineering applications, one objective to minimize the mean compliance for the stiffest structure under normal service conditions and the other objective to maximize the strain energy for energy absorption during excessive loadings, topology optimization with a multimaterial model is applied to the design of an energy-absorbing structure in this paper. The effective properties of the three-phase material are derived using a spherical microinclusion model. The dual objectives are combined in a ratio formation. Numerical examples from the proposed method are presented and discussed.     

Structural optimization based on topology optimization techniques using frame elements considering cross-sectional properties

This paper discusses a new structural optimization method, based on topology optimization techniques, using frame elements where the cross-sectional properties can be treated as design variables. For each of the frame elements, the rotational angle denoting the principal direction of the second moment of inertia is included as a design variable, and a procedure to obtain the optimal angle is derived from Karush–Kuhn–Tucker (KKT) conditions and a complementary strain energy-based approach. Based on the above, the optimal rotational angle of each frame element is obtained as a function of the balance of the internal moments. The above methodologies are applied to problems of minimizing the mean compliance and maximizing the eigen frequencies. Several examples are provided to show the utility of the presented methodology.     

Joint routing, scheduling, and power control for multichannel wireless sensor networks with physical interference

Reliability and real-time requirements bring new challenges to the energy-constrained wireless sensor networks, especially to the industrial wireless sensor networks. Meanwhile, the capacity of wireless sensor networks can be substantially increased by operating on multiple nonoverlapping channels. In this context, new routing, scheduling, and power control algorithms are required to achieve reliable and real-time communications and to fully utilize the increased bandwidth in multichannel wireless sensor networks. In this paper, we develop a distributed and online algorithm that jointly solves multipath routing, link scheduling, and power control problem, which can adapt automatically to the changes in the network topology and offered load. We particularly focus on finding the resource allocation that realizes trade-off among energy consumption, end-to-end delay, and network throughput for multichannel networks with physical interference model. Our algorithm jointly considers 1) delay and energy-aware power control for optimal transmission radius and rate with physical interference model, 2) throughput efficient multipath routing based on the given optimal transmission rate between the given source-destination pairs, and 3) reliable-aware and throughput efficient multichannel maximal link scheduling for time slots and channels based on the designated paths, and the new physical interference model that is updated by the optimal transmission radius. By proving and simulation, we show that our algorithm is provably efficient compared with the optimal centralized and offline algorithm and other comparable algorithms.     

Algorithms for multicast connection under multi-path routing model

Given a source node and a set of destination nodes in a network, multicast routing problem is usually treated as Steiner tree problem. Unlike this well-known tree based routing model, multicast routing under multi-path model is to find a set of paths rooted at the source node such that in each path at most a fixed number of destination nodes can be designated to receive the data and every destination node must be designated in a path to receive the data. The cost of routing is the total costs of paths found. In this paper we study how to construct a multicast routing of minimal cost under multi-path model. We propose two approximation algorithms for this NP-complete problem with guaranteed performance ratios.     

A cooperative approach for topology control in Wireless Sensor Networks

The choice of the transmission power levels adopted in Wireless Sensor Networks (WSNs) is critical to determine the performance of the network itself in terms of energy efficiency, connectivity and spatial reuse, since it has direct impact on the physical network topology.In this paper, a cooperative, lightweight and fully distributed approach is introduced to adaptively tune the transmission power of sensors in order to match local connectivity constraints. To accurately evaluate the topology control solution, a small-scale testbed based on MicaZ sensor nodes is deployed in indoor and outdoor scenarios. Practical measures on local and multi-hop connectivity, convergence time and emitted power are used to compare the proposed approach against previous solutions. Moreover, mathematical programming formulations of the topology (power) control problem are introduced to assess the optimality of the distributed algorithm. Finally, simulation analysis complements the experimental evaluation in large-scale static and mobile WSN scenarios, where a testbed implementation becomes unfeasible.     

Evolutionary topology optimization of continuum structures with a global displacement control

The conventional compliance minimization of load-carrying structures does not directly deal with displacements that are of practical importance. In this paper, a global displacement control is realized through topology optimization with a global constraint that sets a displacement limit on the whole structure or certain sub-domains. A volume minimization problem is solved by an extended evolutionary topology optimization approach. The local displacement sensitivities are derived following a power-law penalization material model. The global control of displacement is realized through multiple local displacement constraints on dynamically located critical nodes. Algorithms are proposed to secure the stability and convergence of the optimization process. Through numerical examples and by comparing with conventional stiffness designs, it is demonstrated that the proposed approach is capable of effectively finding optimal solutions which satisfy the global displacement control. Such solutions are of particular importance for structural designs whose deformed shapes must comply with functioning requirements such as aerodynamic performances.     

Minimum void length scale control in level set topology optimization subject to machining radii

This paper presents a minimum void length scale control method for structural topology optimization. Void length scale control has been actively investigated for decades, which intends to ensure the topology design manufacturable given the machining tool access. However, only a single lower bound has been applied in existing methods, which does not fit the multi-stage rough-to-finish machining. To fix this issue, the proposed minimum void length scale control method employs double lower bounds which corresponds to the rough and finish machining operations, respectively. This method has been implemented under the level set framework. For technical details, the rough machining lower bound is satisfied by developing a signed distance-related constraint, which ensures enough space for the rough machining tool movement and thus, guarantees the machining efficiency. The finish machining lower bound is addressed through the curvature flow control, which ensures the small features manufacturable and also a good finish dimension and surface. Through a few numerical case studies, it is proven that the minimum void length scale can be effectively controlled without sacrificing much of the structural performance.     

Target-matching test problem for multiobjective topology optimization using genetic algorithms

This paper describes the multiobjective topology optimization of continuum structures solved as a discrete optimization problem using a multiobjective genetic algorithm (GA) with proficient constraint handling. Crucial to the effectiveness of the methodology is the use of a morphological geometry representation that defines valid structural geometries that are inherently free from checkerboard patterns, disconnected segments, or poor connectivity. A graph- theoretic chromosome encoding, together with compatible reproduction operators, helps facilitate the transmission of topological/shape characteristics across generations in the evolutionary process. A multicriterion target-matching problem developed here is a novel test problem, where a predefined target geometry is the known optimum solution, and the good results obtained in solving this problem provide a convincing demonstration and a quantitative measure of how close to the true optimum the solutions achieved by GA methods can be. The methodology is then used to successfully design a path-generating compliant mechanism by solving a multicriterion structural topology optimization problem.     

Poly: A reliable and energy efficient topology control protocol for wireless sensor networks

Energy efficiency and reliability are the two important requirements for mission-critical wireless sensor networks. In the context of sensor topology control for routing and dissemination, Connected Dominating Set (CDS) based techniques proposed in prior literature provide the most promising efficiency and reliability. In a CDS-based topology control technique, a backbone - comprising a set of highly connected nodes - is formed which allows communication between any arbitrary pair of nodes in the network. In this paper, we show that formation of a polygon in the network provides a reliable and energy-efficient topology. Based on this observation, we propose Poly, a novel topology construction protocol based on the idea of polygons. We compare the performance of Poly with three prominent CDS-based topology construction protocols namely CDS-Rule K, Energy-efficient CDS (EECDS) and A3. Our simulation results demonstrate that Poly performs consistently better in terms of message overhead and other selected metrics. We also model the reliability of Poly and compare it with other CDS-based techniques to show that it achieves better connectivity under highly dynamic network topologies.     

Design of phononic materials/structures for surface wave devices using topology optimization

We develop a topology optimization approach to design two- and three-dimensional phononic (elastic) materials, focusing primarily on surface wave filters and waveguides. These utilize propagation modes that transmit elastic waves where the energy is contained near a free surface of a material. The design of surface wave devices is particularly attractive given recent advances in nano- and micromanufacturing processes, such as thin-film deposition, etching, and lithography, which make it possible to precisely place thin film materials on a substrate with submicron feature resolution. We apply our topology optimization approach to a series of three problems where the layout of two materials (silicon and aluminum) is sought to achieve a prescribed objective: (1) a grating to filter bulk waves of a prescribed frequency in two and three dimensions, (2) a surface wave device that uses a patterned thin film to filter waves of a single or range of frequencies, and (3) a fully three-dimensional structure to guide a wave generated by a harmonic input on a free surface to a specified output port on the surface. From the first to the third example, the resulting topologies increase in sophistication. The results demonstrate the power and promise of our computational framework to design sophisticated surface wave devices.     

A mathematical formulation for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks

Multicast routing is generally an efficient mechanism for delivering identical content to a group of receivers. Multicast is also deemed a key enabling service for a wealth of audio and video applications as well as data dissemination protocols over the last-mile backhaul Internet connectivity provided by multi-channel multi-radio wireless mesh networks (MCMR WMNs). Major prior art multicast protocols in these networks center around heuristic or meta-heuristic initiatives in which channel assignment and multicast routing are considered as two separate sub-problems to be solved in sequence. It might even be the cast that the solution for either of these two sub-problems is assumed to be preparatively calculated and given as input to the other. Within this perspective, however, the interplay between the two sub-problems would essentially be ruled out from the computations, resulting in sub-optimal solutions for network configuration. The work in this article is targeted at promoting the adoption of cross-layer design for joint channel assignment and multicast tree construction problem in MCMR WMNs. In the proposed scheme, contrary to the existing methods, these two sub-problems will be solved conjointly and an optimal solution is provided. In particular, a comprehensive cross-optimization framework based on the binary integer programming (BIP) formulation of the problem is presented which also addresses the hidden channel problem in MCMR WMNs. We have, as well, conducted an extensive series of simulation experiments to verify the efficacy of the proposed method. Also, experimental results demonstrate that the proposed method outperforms the genetic algorithm and the simulated annealing based methods proposed by Cheng and Yang (2011) in terms of interference.     

一种用于事件监测的传感器网络拓扑控制策略

针对事件驱动型传感器网络应用系统,基于简化的ＡＯＤＶ（ａｄｈｏｃ ｏｎｄｅｍａｎｄｄｉｓｔａｎｃｅｖｅｃｔｏｒｒｏｕｔｉｎｇ）（Ｓ-ＡＯＤＶ）算法,提出一种结合预先路由和按需路由的混合拓扑控制策略,通过随机选择一部分节点预先运行Ｓ-ＡＯＤＶ算法来减小事件发生时任务节点的初始拓扑建立时延．仿真实验表明,该策略能以较小的能耗代价换取较快的系统响应速度,满足了事件监测类应用的实时性要求．     

带有网络拓扑优化的分布式预测控制方法

通常在大系统中, 全局信息优化的系统, 其性能要高于局部信息优化系统. 全局信息优化的算法由于大系统的复杂程度往往不可行. 所以通常会用分布式算法来解决此类问题. 在分布式算法中, 为了获得更好的系统性能, 要尽可能多的采用更多的信息信息交换, 然而这样会带来信息网络的负担增大. 本文在预测控制性能指标中引入通信代价, 并提出了一种随着系统状态变化的通信网络拓扑切换方法. 文中给出了该算法在供水管网动态模型中的仿真结果, 表明本方法的可行性.     

A cross-layer optimization framework for joint channel assignment and multicast routing in multi-channel multi-radio wireless mesh networks

Existing literature on multicast routing protocols in wireless mesh networks (WMNs) from the view point of the links involved in routing are divided into two categories: schemes are aimed at multicast construction with minimal interference which is known as NP hard problem. In contrast, other methods develop network-coding-based solutions with the main objective of throughput maximization, which can effectively reduce the complexity of finding the optimal routing solution from exponential to polynomial time. The proposed framework in this paper is placed in the second category. In multi-channel multi-radio WMNs (MCMR WMNs), each node is equipped with multiple radios, each tuned on a different channel. In this paper, for the first time, we propose a cross-layer convex optimization framework for joint channel assignment and multicast throughput maximization in MCMR WMNs. The proposed method is composed of two phases: in the first phase, using cellular learning automata, channels are assigned to the links established between the radios of the nodes in a distributed fashion such that the minimal interference coefficient for each link is provided. Then, the resultant channel assignment scheme is utilized in the second phase for throughput maximization within an iterative optimization framework based on Lagrange relaxation and primal problem decomposition. We have conducted many experiments to contrast the performance of our solution against many representative approaches.     

Design of multi-component structural systems for optimal layout topology and joint locations

Present day topology optimization techniques for continuum structures consider the design of single structural components, while most real life engineering design problems involve multiple components or structures. It is therefore necessary to have a methodology that can address the design of multi-component systems and generate designs for the optimal layouts of individual structures and locations for interconnections. The interconnections include supports provided by the ground, joints and rigid connections like rivets, bolts and welds between components. While topology optimization of structures has been extensively researched, relatively little work has been done on optimizing the locations of the interconnections. In this research, a method to model and define domains for the interconnections has been developed. The optimization process redistributes material in the component design domains and locates the connections optimally based on an energy criterion. Some practical design examples are used to illustrate the capability of this method.     

A review of homogenization and topology optimization III-topology optimization using optimality criteria

This is the first part of a three-paper review of homogenization and topology optimization, viewed from an engineering standpoint and with the ultimate aim of clarifying the ideas so that interested researchers can easily implement the concepts described. In the first paper we focus on the theory of the homogenization method where we are concerned with the main concepts and derivation of the equations for computation of effective constitutive parameters of complex materials with a periodic micro structure. Such materials are described by the base cell, which is the smallest repetitive unit of material, and the evaluation of the effective constitutive parameters may be carried out by analysing the base cell alone. For simple microstructures this may be achieved analytically, whereas for more complicated systems numerical methods such as the finite element method must be employed. In the second paper, we consider numerical and analytical solutions of the homogenization equations. Topology optimization of structures is a rapidly growing research area, and as opposed to shape optimization allows the introduction of holes in structures, with consequent savings in weight and improved structural characteristics. The homogenization approach, with an emphasis on the optimality criteria method, will be the topic of the third paper in this review.     

A systematic approach to constructing incremental topology control algorithms using graph transformation

Communication networks form the backbone of our society. Topology control algorithms optimize the topology of such communication networks. Due to the importance of communication networks, a topology control algorithm should guarantee certain required consistency properties (e.g., connectivity of the topology), while achieving desired optimization properties (e.g., a bounded number of neighbors). Real-world topologies are dynamic (e.g., because nodes join, leave, or move within the network), which requires topology control algorithms to operate in an incremental way, i.e., based on the recently introduced modifications of a topology. Visual programming and specification languages are a proven means for specifying the structure as well as consistency and optimization properties of topologies. In this paper, we present a novel methodology, based on a visual graph transformation and graph constraint language, for developing incremental topology control algorithms that are guaranteed to fulfill a set of specified consistency and optimization constraints. More specifically, we model the possible modifications of a topology control algorithm and the environment using graph transformation rules, and we describe consistency and optimization properties using graph constraints. On this basis, we apply and extend a well-known constructive approach to derive refined graph transformation rules that preserve these graph constraints. We apply our methodology to re-engineer an established topology control algorithm, kTC, and evaluate it in a network simulation study to show the practical applicability of our approach.     

Bio-inspired adaptive control strategy for the highly efficient speed regulation of the DC motor under parametric uncertainty

The presence of parametric uncertainties decreases the performance in controlling dynamic systems such as the DC motor. In this work, an adaptive control strategy is proposed to deal with parametric uncertainties in the speed regulation task of the DC motor. This adaptive strategy is based on a bio-inspired optimization approach, where an optimization problem is stated and solved online by using a modification of the differential evolution optimizer. This modification includes a mechanism that promotes the exploration in the early generations and takes advantage of the exploitation power of the DE/best class in the last generations of the algorithm to find suitable optimal control parameters to control the DC motor speed efficiently. Comparative statistical analysis with other bio-inspired adaptive strategies and with linear, adaptive and robust controllers shows the effectiveness of the proposed bio-inspired adaptive control approach both in simulation and experimentation.