Link optimization for energy‐constrained wireless networks with packet retransmissions

With the objective to minimize the energy consumption for packet based communications in energy‐constrained wireless networks, this paper establishes a theoretical model for the joint optimization of the parameters at the physical layer and data link layer. Multilevel quadrature amplitude modulation (MQAM) and automatic repeat request (ARQ) techniques are considered in the system model. The optimization problem is formulated into a three dimensional nonlinear integer programming (NIP) problem with the modulation order, packet size, and retransmission limit as variables. For the retransmission limit, a simple search method is applied to degenerate the three dimensional problem into a two dimensional NIP problem, for which two optimization algorithms are proposed. One is the successive quadratic programming (SQP) algorithm, combining with the continuous relaxation based branch‐and‐bound method, which can obtain the global optimal solution since the continuous relaxation problem is proved to be hidden convex. The other is a low‐complexity sub‐optimal iterative algorithm, combining with the nearest‐neighboring method, which can be implemented with a polynomial complexity. Numerical examples are given to illustrate the optimization solution, which suggests that the joint optimization of the physical/data link layer parameters contributes noticeably to the energy saving in energy‐constrained wireless networks. Copyright © 2010 John Wiley & Sons, Ltd.     

Joint Optimization of Transmit Power-Time and Bit Energy Efficiency in CDMA Wireless Sensor Networks

In this paper, we address the problem of minimizing energy consumption in a CDMA-based wireless sensor network (WSN). A comprehensive energy consumption model is proposed, which accounts for both the transmit and circuit energies. Energy consumption is minimized by jointly optimizing the transmit power and transmission time for each active node in the network. The problem is formulated as a non-convex optimization. Numerical as well as closed-form approximate solutions are provided. For the numerical solution, we show that the formulation can be transformed into a convex geometric programming (GP), for which fast algorithms, such as interior point method, can be applied. For the closed-form solution, we prove that the joint power/time optimization can be decoupled into two sequential sub-problems: optimization of transmit power with transmission time serving as a parameter, and then optimization of the transmission time. We show that the first sub-problem is a linear program while the second one can be well approximated as a convex programming problem. Taking advantage of these analytical results, we further derive the per-bit energy efficiency. Our results are verified through numerical examples and simulations     

应用于非负稀疏信号重构的交替方向乘子法

非负稀疏信号在欠定线性观测条件下的重构效果不理想,仍有进一步提高的余地。文中将非负稀疏信号重构建模为线性规划问题,在交替方向乘子法的框架下得到了具有闭合解形式的优化算法,且算法复杂度较低。为了进一步增强重构信号的稀疏性,提出了迭代加权线性规划算法,通过对权值向量和重构信号交替优化提高了重构准确率。实验仿真验证了算法的有效性,针对随机生成信号和实际语音能量谱这两类非负稀疏信号均取得了较好的重构效果,重构性能优于目前一些流行的稀疏重构算法。      

Robust Explicit Solution of Multirate Predictive Control System with External Disturbances

This paper considers the problem of robust predictive control for a class of uncertain multirate systems, in which the output sampling period is several times larger than the one of input updating. By means of dynamic programming and multiparametric quadratic programming (mp-QP) techniques, this work proposes a novel robust explicit model predictive control (REMPC) algorithm such that the higher on-line updating speed of input can be attained. Firstly, the optimization problem is decomposed into several subproblems. For each subproblem, a constraint condition only involving current state and input is constructed. Then taking current state and future inputs as parameter variables we can obtain a robust explicit solution for the new reformulated optimization subproblem by mp-QP method. Especially, by choosing a maximal robust positive invariant set as the terminal constraint set of the optimization problem, closed-loop robust stability of the multirate control system subject to external disturbance can be guaranteed. Finally, a numerical simulation is given to show the effectiveness of the proposed method.     

无源时差定位方程的半定松弛解法

针对基于到达时差量测的多站无源定位系统,提出了一种基于半定松弛的时差定位方程求解方法.该方法首先将关于目标位置估计的非凸二次优化问题转换成等价的非凸半定规划问题,然后通过秩1松弛得到一个凸优化问题,最后对松弛半定规划问题的最优解进行秩1近似,从而提取出最终的目标位置估计.计算机仿真结果表明这种松弛解法可以有效求解目标位置.     

计算机通信网中路由选择和容量分配问题的遗传算法求解

计算机通信网中，对路由选择和容量分配问题进行综合优化设计时的数学模型，是一个多约束条件的非线性０－１规划。本文以遗传算法的基本思想为基础，设计了一个求解该问题的遗传寻优算法，对计算机通信网优化设计实例的计算表明，这一方法能够迅速求出问题的全局近似最优解，并具有高的计算精确度。     

生物地理学算法求解一类非线性线性双层规划

用生物地理学优化算法的实数编码来求解下层为凸规划的非线性双层规划问题。基于上层目标函数设置了一种新的适宜度函数,可以简单区分不同类型的解;对下层问题先用坐标轮换法求解,然后利用基于下层问题的KKT最优性等价条件来检验求解结果。分别运用4种不同的迁移率模型来求解问题,实验结果表明,生物地理学优化算法求解这类双层问题是稳定、有效的。     

Review of Optimal Reliability Design, Fundamentals and Applications

This reference covers the extent of the state-of-the-art in optimizing systems reliability. The book consists of fifteen chapters and an appendix. The main part of the book is organized by problem type and solution method. Some of the topics covered include: redundancy allocation methods using heuristics, dynamic programming solutions and discrete optimization methods; reliability optimization using nonlinear programming and meta-heuristic algorithms; and methods to solve reliability-redundancy optimization. The book may serve as a textbook for students or as a reference for researchers and practitioners. It is a comprehensive book that is recommended for anyone concerned with designing reliable systems.     

Design of Coupled Microstrip Lines by Optimization Methods (Short Paper)

The design of two coupled microstrip lines is converted into an optimization problem, which is then solved by two methods of nonlinear mathematical programming. New formulas for calculating the first approximation of the solution, i.e., the starting point of the optimization, are given.     

Multiple Weighted Objectives Heuristic for the Redundancy Allocation Problem

A new heuristic is proposed and tested for system reliability optimization. The multiple weighted objective heuristic is based on a transformation of the problem into a multiple objective optimization problem, and then ultimately, transformation into a different single objective problem. The multiple objectives are to simultaneously maximize the reliability of each individual subsystem. This is a logical approach because system reliability is the product of the subsystem reliabilities, so if they are maximized, the system reliability will also be high. This new formulation and associated heuristic are then based on solving a sequence of linear programming problems. It is one of the very few optimization approaches that allow for linear programming algorithms and software to be used for the redundancy allocation problem when mixing of functionally equivalent components is allowed. Thus, it represents an efficient solution method that relies on readily available optimization tools. The heuristic is tested on many example problems, and compared to competing solution approaches. Overall, the heuristic performance is observed to be very good on the tested problem, and superior to the max-min heuristic regarding both efficiency, and performance.     

A Method of Solving Redundancy Optimization Problems

The redundancy optimization problem is formulated as an integer programming problem of zero-one type variables. The solution is obtained making use of an algorithm due to Lawler and Bell. Objective function and constraints can be any arbitrary functions. Three different variations of the optimization problem are considered. The formulation is easy and the solution is convenient on a digital computer. The size of the problem that can be solved is not restricted by the number of constraints.     

Routing and wavelength assignment in optical networks

The problem of routing and wavelength assignment (RWA) is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and the required connections, the RWA problem is to select a suitable path and wavelength among the many possible choices for each connection so that no two paths sharing a link are assigned the same wavelength. In work to date, this problem has been formulated as a difficult integer programming problem that does not lend itself to efficient solution or insightful analysis. In this work, we propose several novel optimization problem formulations that offer the promise of radical improvements over the existing methods. We adopt a (quasi-)static view of the problem and propose new integer-linear programming formulations, which can be addressed with highly efficient linear (not integer) programming methods and yield optimal or near-optimal RWA policies. The fact that this is possible is surprising, and is the starting point for new and greatly improved methods for RWA. Aside from its intrinsic value, the quasi-static solution method can form the basis for suboptimal solution methods for the stochastic/dynamic settings.     

Minimax Optimization of Networks by Grazer Search

A new optimization method called grazer search has been developed. This method is suitable for nonlinear minimax optimization of network and system responses. A linear programming problem using gradient information of one or more highest ripples in the response error function to produce a downhill direction followed by a linear search to find a minimum in that direction is central to the algorithm. Unlike the razor search method due to Bandler and Macdonald, the present method overcomes the problem of discontinuous derivatives characteristic of minimax objectives without using random moves. It can fully exploit the advantages of the adjoint network method of evaluating partial derivatives of the response function with respect to the variable parameters. Sufficient details are given to enable the grazer search method to be readily programmed and used. Although the method is intended for the computer-aided solution of an extremely wide range of design problems, it is largely compared with other methods on microwave network design problems, for which the solutions are known. Its reliability and efficiency on more arbitrary problems, examples of which are also included, is thereby established.     

面向TDOA被动定位的定位节点选择方法

该文主要研究一种面向到达时间差(TDOA)被动定位的定位节点选择方法。首先,通过经典的闭式解析算法将TDOA非线性方程转化为伪线性方程,并使用位置误差的协方差矩阵来度量定位精度。其次,在可用节点数量给定的条件下,在数学上将定位节点选择问题转化为最小化位置误差协方差矩阵的迹这一非凸优化问题。然后,将非凸优化问题凸松弛并化为半正定规划问题,从而快速有效地求解出最优的定位节点组合。仿真结果表明,所提节点优选方法的性能非常接近穷尽搜索方法,而且克服了穷尽搜索方法运算复杂度高、时效性差的不足,从而验证了所提方法的有效性。     

基于双层模糊规划的电子干扰资源优化分配算法

电子干扰资源分配决策是一个双层规划问题,而且在复杂电磁环境下的作战过程中存在着大量的不确定因素。在综合考虑这些因素的条件下,建立了基于双层模糊机会约束混合整数规划的干扰资源优化分配模型。根据可能性测度理论得到双层混合整数规划模型,然后通过求解有限个混合整数线性规划问题,来获取模型的最优解。算例表明了方法的有效性。     

Resource Allocation and Adaptive Modulation in Uplink SC-FDMA Systems

In this paper, we study joint power and sub-channel allocation, and adaptive modulation in Single Carrier Frequency Division Multiple Access (SC-FDMA) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE standard. A sum-utility maximization problem is considered. Unlike OFDMA, in addition to the restriction of allocating a sub-channel to one user at most, the multiple sub-channels allocated to a user in SC-FDMA should be consecutive as well. This renders the resource allocation problem prohibitively difficult and the standard optimization tools (e.g., Lagrange dual approach widely used for OFDMA, etc.) can not help towards its optimal solution. We propose a novel optimization framework for the solution of this problem which is inspired from the recently developed canonical duality theory. We first formulate the optimization problem as binary-integer programming problem, and then transform this binary-integer programming problems into a continuous space canonical dual problem that is a concave maximization problem. Based on the solution of the continuous space dual problem, we derive joint power and sub-channel allocation algorithm whose computational complexity is polynomial. We provide conditions under which the proposed algorithms are optimal. We also propose an adaptive modulation scheme which selects an appropriate modulation strategy for each user. We compare the proposed algorithm with the existing algorithms in the literature to assess their performance. The results show a tremendous performance gain.     

A decomposition method for optimization of large-system reliability

The authors consider a decomposition approach for optimization of the reliability of a large system with a general network structure. A three-level methodology is developed for optimal allocation of available resources among subsystems in order to ensure maximization of system reliability. The decentralized nature of this methodology greatly reduces the complexity of the large problem and facilitates seeking the optimal solution. Two examples show that the complexity of a large system can be greatly reduced by solving several smaller-dimensional subproblems iteratively. Subproblems whose dimensions are small can be efficiently solved by an existing nonlinear programming method. Another important feature of the approach is the possible simplification of the objective function during the solution. This leads in some cases to an analytic solution for the lower-level optimization problems in the three-level decomposition solution     

Wordlength Optimization of Linear Time-Invariant Systems With Multiple Outputs Using Geometric Programming

This paper proposes two new methods for optimizing hardware resources in finite wordlength implementation of multiple-output (MO) linear time-invariant (LTI) systems. The hardware complexity is measured by the exact internal wordlength used for each intermediate data. The first method relaxes the wordlength from integer to real-value and formulates the design problem as a geometric programming, from which an optimal solution of the relaxed problem can be determined. The second method is based on a discrete optimization method called the marginal analysis method, and it yields the desired wordlengths in integer values. By combining these two methods, a hybrid method is also proposed, which is found to be very effective for large scale MO LTI systems. To illustrate the effectiveness of the proposed methods, wordlength optimization problems of two-channel structural perfect reconstruction filter banks and multiplier-less fast Fourier transforms are studied in detail. Design results show that the proposed algorithms offer better results and a lower design complexity than conventional methods     

非线性几何规划的几种算法

介绍了非线性规划的数学模型(即具有不等式约束条件的求解目标函数最优化解的一类优化问题)以及现今求解这类非线性规划问题时,运用最为广泛的罚函数内点算法,同时介绍了解决几何规划问题的两种算法,内点路经跟踪法和序列二次规划法。通过实例,对比了文中所介绍的内点路径跟踪法和序列二次规划法的运算结果,最终给出结论。     

A Tabu search algorithm for static routing and wavelength assignment problem

Static routing and wavelength assignment (RWA) is usually formulated as an optimization problem with the objective of minimizing wavelength usage (MWU). Existing solution methodologies for the MWU problem are usually based on a two-step approach, where routing and wavelength assignment are done independently. Though this approach can reduce computational cost, the optimality of the solution is compromised. We propose a novel tabu search (TS) algorithm, which considers routing and wavelength assignment jointly without increasing the computational complexity. The performance of the proposed TS algorithm is compared with the integer linear programming (ILP) method, which is known to solve the MWU to optimality. The results for both small and large networks show that our proposed TS algorithm works almost as well as the ILP solution and is much more computationally efficient.