Low-Energy Fault-Tolerant Bounded-Hop Broadcast in Wireless Networks

This paper studies asymmetric power assignments in wireless ad hoc networks. The temporary, unfixed physical topology of wireless ad hoc networks is determined by the distribution of the wireless nodes as well as the transmission power (range) assignment of each node. We consider the problem of bounded-hop broadcast under k-fault resilience criterion for linear and planar layout of nodes. The topology that results from our power assignment allows a broadcast operation from a wireless node r to any other node in at most h hops and is k -fault resistant. We develop simple approximation algorithms for the two cases and obtain the following approximation ratios: linear case-O(k); planar case-we first prove a factor of O(k ³) , which is later decreased to O(k ²) by a finer analysis. Finally, we show a trivial power assignment with a cost O(h) times the optimum. To the best of our knowledge, these are the first nontrivial results for this problem.     

McPAO: A Distributed Multi-channel Power Allocation and Optimization Algorithm for Femtocells

Efficient radio resource management is a key issue in a multi-channel femtocell system, where femtocell base stations are deployed randomly and will generate interference to each other. In this research, we formulate multi-channel power allocation as a convex optimization problem, in order to maximize the overall system throughput under complex transmit power constraint. We apply the Lagrangian duality techniques to make the problem decomposable and propose a distributed iterative subgradient algorithm, namely Multi-channel Power Allocation and Optimization (McPAO). Specifically, McPAO consists of two phases: (I) a gradient projection algorithm to solve the optimal power allocation for each channel under a fixed Lagrangian dual cost; and (II) a subgradient algorithm to update the Lagrangian dual cost by using the power allocation results from Phase I. This two-phase iteration process continues until the Lagrangian dual cost converges to the optimal value. Numerical results show that our McPAO algorithm can improve the overall system throughput by 18?%, comparing to with fixed power allocation schemes. In addition, we study the impact of errors in gradient direction estimation (Phase I), which are caused by limited or delayed information exchange among femtocells in realistic situations. These errors will be propagated into the subgradient algorithm (Phase II) and, subsequently, affect the overall performance of McPAO. A rigorous analytical approach is developed to prove that McPAO can always achieve a bounded overall throughput performance very close to the global optimum.     

N∗Nakagami: A Novel Stochastic Model for Cascaded Fading Channels

A generic and novel distribution, referred to as Nakagami, constructed as the product of N statistically independent, but not necessarily identically distributed, Nakagami-m random variables (RVs), is introduced and analyzed. The proposed distribution turns out to be a very convenient tool for modelling cascaded Nakagami-m fading channels and analyzing the performance of digital communications systems operating over such channels. The moments-generating, probability density, cumulative distribution, and moments functions of the N _*Nakagami distribution are developed in closed form using the Meijer's G -function. Using these formulas, generic closed-form expressions for the outage probability, amount of fading, and average error probabilities for several binary and multilevel modulation signals of digital communication systems operating over the N _*Nakagami fading and the additive white Gaussian noise channel are presented. Complementary numerical and computer simulation performance evaluation results verify the correctness of the proposed formulation. The suitability of the N _*Nakagami fading distribution to approximate the lognormal distribution is also being investigated. Using Kolmogorov--Smirnov tests, the rate of convergence of the central limit theorem as pertaining to the multiplication of Nakagami-m RVs is quantified.     

一种基于GNC和增广拉格朗日对偶的非凸非光滑图像恢复方法

逐步非凸方法（GNC）和增广拉格朗日对偶在非凸非光滑图像恢复中有较高的恢复性能.然而分别使用这两种方法时GNC不能够保证全局收敛,增广拉格朗日对偶不能获得有效的初始值.为克服上述缺陷,本文通过转换原始问题为等式约束优化问题推出了一种基于GNC和增广拉格朗日对偶的组合图像恢复方法,并对其收敛性严格证明.该方法不仅可以获得有效的初始值,同时不要求问题具有凸性和光滑性.更多地,一个自适应能量函数通过对偶迭代而得到.实验结果表明推出的方法可以有效地提高图像恢复质量和算法效率.     

Hydrodynamic hot-electron transport simulation based on the Monte Carlo method

A hydrodynamic hot electron model is used to study electron transport through a submicron N⁺ --- N --- N⁺ GaAs structure. This study is used to investigate improvements which the unique features of this model offer to analysis of devices operating under nonstationary transport conditions. The model is based upon semiclassical “hydrodynamic” conservation equations for the average carrier density, momentum and energy. The general model includes particle relaxation times, momentum relaxation times, energy relaxation times, electron temperature tensors and heat flow vectors as a function of average carrier energy for the Γ, X and L valleys of GaAs. For this study, we utilized a simplified single electron gas version of our model to clearly reveal the impact of the nonstationary terms in the model. Results from both a drift-diffusion model approach and a Monte Carlo analysis are used to show the relative accuracy and facility this new model offers for investigating practical submicron device structures operating under realistic conditions.     

Bandwidth-Efficient Modulation Codes Based on Nonbinary Irregular Repeat–Accumulate Codes

Using nonbinary low-density parity-check (LDPC) codes with random-coset mapping, Bennatan and Burshtein constructed bandwidth-efficient modulation codes with remarkable performance under belief propagation (BP) decoding. However, due to the random nature of LDPC codes, most of the good LDPC codes found in the literature do not have a simple encoding structure. Thus, the encoding complexity of those LDPC codes can be as high as O(N ²), where N is the codeword length. To reduce the encoding complexity, in this paper, nonbinary irregular repeat-accumulate (IRA) codes with time-varying characteristic and random-coset mapping are proposed for bandwidth-efficient modulation schemes. The time-varying characteristic and random-coset mapping result in both permutation-invariance and symmetry properties, respectively, in the densities of decoder messages. The permutation-invariance and symmetry properties of the proposed codes enable the approximations of densities of decoder messages using Gaussian distributions. Under the Gaussian approximation, extrinsic information transfer (EXIT) charts for nonbinary IRA codes are developed and several codes of different spectral efficiencies are designed based on EXIT charts. In addition, by proper selection of nonuniform signal constellations, the constructed codes are inherently capable of obtaining shaping gains, even without separate shaping codes. Simulation results indicate that the proposed codes not only have simple encoding schemes, but also have remarkable performance that is even better than that constructed using nonbinary LDPC codes.     

Uplink-downlink duality via minimax duality

The sum capacity of a Gaussian vector broadcast channel is the saddle point of a minimax Gaussian mutual information expression where the maximization is over the set of transmit covariance matrices subject to a power constraint and the minimization is over the set of noise covariance matrices subject to a diagonal constraint. This sum capacity result has been proved using two different methods, one based on decision-feedback equalization and the other based on a duality between uplink and downlink channels. This paper illustrates the connection between the two approaches by establishing that uplink-downlink duality is equivalent to Lagrangian duality in minimax optimization. This minimax Lagrangian duality relation allows the optimal transmit covariance and the least-favorable-noise covariance matrices in a Gaussian vector broadcast channel to be characterized in terms of the dual variables. In particular, it reveals that the least favorable noise is not unique. Further, the new Lagrangian interpretation of uplink-downlink duality allows the duality relation to be generalized to Gaussian vector broadcast channels with arbitrary linear constraints. However, duality depends critically on the linearity of input constraints. Duality breaks down when the input constraint is an arbitrary convex constraint. This shows that the minimax representation of the broadcast channel sum capacity is more general than the uplink-downlink duality representation     

引入D2D通信的蜂窝网上行资源分配算法

该文研究了引入Device-to-Device (D2D)通信的蜂窝网系统中的上行资源分配问题。首先将该问题建模为一个简洁的二值整数规划问题。然而整数规划仍是NP难问题。该文利用Canonical对偶理论,得到其对偶形式。该对偶问题是一个连续域内的凸问题。证明了在特定的条件下,可以通过求解对偶问题得到原问题的最优解,且对偶间隙为零。提出了一个基于Barrier方法的算法来求解对偶问题。仿真结果表明,该文的算法优于现有算法,且性能接近最优。     

Information Spectrum Approach to Second-Order Coding Rate in Channel Coding

In this paper, second-order coding rate of channel coding is discussed for general sequence of channels. The optimum second-order transmission rate with a constant error constraint epsiv is obtained by using the information spectrum method. We apply this result to the discrete memoryless case, the discrete memoryless case with a cost constraint, the additive Markovian case, and the Gaussian channel case with an energy constraint. We also clarify that the Gallager bound does not give the optimum evaluation in the second-order coding rate.     

Maximum Active Concentration of Ion-Implanted Phosphorus During Solid-Phase Epitaxial Recrystallization

In this paper, we showed that the maximum active P concentration of approximately 2 times10²⁰ cm^-3 exists during solid-phase epitaxial recrystallization (SPER). This maximum active concentration is close to the reported values for other active impurity concentrations during SPER. We introduced the concept of an isolated impurity that has no neighbor impurities with a certain lattice range. Assuming that impurities interact with three or four neighbor impurities, we can explain the activation phenomenon during SPER. According to our model, the isolated P concentration N _iso has a maximum value of approximately 2 times10²⁰ cm^-3 at a total impurity concentration of approximately 10²¹ cm^-3, and it decreases with a further increase in total impurity concentration. Deactivation occurs after the completion of SPER with increasing annealing time, and the active impurity concentration decreases with time but is always higher than the maximum diffusion concentration N _{Diff max}. We also observed that N _{Diff max} is independent of the annealing time despite nonthermal activation in the high-concentration region. We evaluated the dependence of N _{Diff max} on annealing temperatures. We think that this N _{Diff max} can be regarded as the electrical solid solubility N _Esol that the active impurity concentration reaches in thermal equilibrium. We observed the transient enhanced diffusion (TED) after the completion of SPER, and that, the deactivation process continues during and after TED, and the corresponding diffusion coefficient is still much higher than that in thermal equilibrium even after TED has finished, which suggests that the deactivation process releases point defects.     

Modeling and efficient optimization for object-based scalabilityand some related problems

MPEG-4 is the first visual coding standard that allows coding of scenes as a collection of individual audio-visual objects. We present mathematical formulations for modeling object-based scalability and some functionalities that it brings with it. Our goal is to study algorithms that aid in semi-automating the authoring and subsequent selective addition/dropping of objects from a scene to provide content scalability. We start with a simplistic model for object-based scalability using the "knapsack problem"-a problem for which the optimal object set can be found using known schemes such as dynamic programming, the branch and bound method and approximation algorithms. The above formulation is then generalized to model authoring or multiplexing of scalable objects (e.g., objects encoded at various target bit-rates) using the "multiple choice knapsack problem." We relate this model to several problems that arise in video coding, the most prominent of these being the bit allocation problem. Unlike previous approaches to solve the operational bit allocation problem using Lagrangean relaxation, we discuss an algorithm that solves linear programming (LP) relaxation of this problem. We show that for this problem the duality gap for Lagrange and LP relaxations is exactly the same. The LP relaxation is solved using strong duality with dual descent-a procedure that can be completed in "linear" time. We show that there can be at most two fractional variables in the optimal primal solution and therefore this relaxation can be justified for many practical applications. This work reduces problem complexity, guarantees similar performance, is slightly more generic, and provides an alternate LP-duality based proof for earlier work by Shoham and Gersho (1988). In addition, we show how additional constraints may be added to impose inter-dependencies among objects in a presentation and discuss how object aggregation can be exploited in reducing problem complexity. The marginal analysis approach of Fox (1966) is suggested as a method of re-allocation with incremental inputs. It helps in efficiently re-optimizing the allocation when a system has user interactivity, appearing or disappearing objects, time driven events, etc. Finally, we suggest that approximation algorithms for the multiple choice knapsack problem, which can be used to quantify complexity vs. quality tradeoff at the encoder in a tunable and universal way.     

Cross-layer optimization in TCP/IP networks

TCP-AQM can be interpreted as distributed primal-dual algorithms to maximize aggregate utility over source rates. We show that an equilibrium of TCP/IP, if exists, maximizes aggregate utility over both source rates and routes, provided congestion prices are used as link costs. An equilibrium exists if and only if this utility maximization problem and its Lagrangian dual have no duality gap. In this case, TCP/IP incurs no penalty in not splitting traffic across multiple paths. Such an equilibrium, however, can be unstable. It can be stabilized by adding a static component to link cost, but at the expense of a reduced utility in equilibrium. If link capacities are optimally provisioned, however, pure static routing, which is necessarily stable, is sufficient to maximize utility. Moreover single-path routing again achieves the same utility as multipath routing at optimality.     

Resource allocation based on dynamic hybrid overlay/underlay for heterogeneous services of cognitive radio networks

In cognitive radio networks (CRNs), hybrid overlay and underlay sharing transmission mode is an effective technique to improve the efficiency of radio spectrum. Unlike existing works in literatures where only one secondary user (SU) uses both overlay and underlay mode, the different transmission modes should dynamically be allocated to different SUs according to their different quality of services (QoS) to achieve the maximal efficiency of radio spectrum. However, dynamic sharing mode allocation for heterogeneous services is still a great challenge in CNRs. In this paper, we propose a new resource allocation method based on dynamic allocation hybrid sharing transmission mode of overlay and underlay (Dy-HySOU) to obtain extra spectrum resource for SUs without interfering with the primary users. We formulate the Dy-HySOU resource allocation problem as a mixed-integer programming to optimize the total system throughput with simultaneous heterogeneous QoS guarantee. To decrease the algorithm complexity, we divide the problem into two sub-problems: subchannel allocation and power allocation. Cutset is used to achieve the optimal subchannel allocation, and the optimal power allocation is obtained by Lagrangian dual function decomposition and subgradient algorithm. Simulation results show that the proposed algorithm further improves spectrum utilization with simultaneous fairness guarantee, and the achieved Dy-HySOU diversity gain is satisfying.     

Duality and Rate Optimization for Multiple Access and Broadcast Channels With Amplify-and-Forward Relays

In this paper, we consider multihop multiple access (MAC) and broadcast channels (BC) where communication takes place with the assistance of relays that amplify and forward (AF) their received signals. For a two-hop parallel AF relay MAC, assuming a sum power constraint across all relays we characterize optimal relay amplification factors and the resulting optimal rate regions. We find the maximum sum rate and the maximum rate for each user in closed form and express the optimal rate pair (R₁, R₂) that maximizes mu₁R₁+mu₂R₂ as the solution of a pair of simultaneous equations. We find that the parallel AF relay MAC with total transmit power of the two users P₁+P₂=P and total relay power P_R is the dual of the parallel AF relay BC where the MAC source nodes become the BC destination nodes, the MAC destination node becomes the BC source node, the dual BC source transmit power is P_R and the total transmit power of the AF relays is P. The duality means that the rate region of the AF relay MAC with a sum power constraint P on the transmitters is the same as that of the dual BC. The duality relationship is found to be useful in characterizing the rate region of the AF relay BC as the union of MAC rate regions. The duality is established for distributed multiple antenna AF relay nodes and multiple (more than 2) hops as well.     

Multi-cell uplink-downlink beamforming throughput duality based on Lagrangian duality with per-base station power constraints

Despite significant research efforts in beamforming, the maximum achievable downlink throughput with beamforming in a multi-cell environment is not available due to difficulty in finding optimal downlink beamforming. Thus, to reformulate the problem into a more solvable form, we derive dual uplink throughput optimization problem to multi-cell downlink beam- forming throughput maximization with per-base station (BS) power constraints based on Lagrangian duality. The optimal downlink beamforming is shown to be a minimum mean squared error (MMSE) beamforming in the dual uplink. It is also shown that the dual uplink problem achieves the same optimal throughput as the primal downlink problem.     

Discrete bit loading and power allocation for OFDMA downlink with minimum rate guarantee for users

Performance optimization of the communication networks with quality of service (QoS) considerations for all active users is of great practical importance in highly delay-sensitive applications like multipoint videoconferences and interactive video games. Using minimum data rate as the primary criterion for the QoS and the BER as a second one, in this paper, we provide the optimum discrete bit loading for an OFDMA downlink in which the QoS of all users are satisfied. We formulate the problem and solve the dual problem efficiently and without any suboptimality. Albeit the problem is non-convex, it has been shown that the duality gap tends zero in practical scenarios. We propose a novel approach to solve the dual problem by decomposing dual function and finding discrete rate allocation solution for practical applications. Also, we present a novel fast converging iterative algorithm to find the solution with much less complexity compared to that of well-known ellipsoid optimization algorithm. We analyze the complexity of these solutions, and using simulation results, show the superiority of our novel approach.     

Dual methods for nonconvex spectrum optimization of multicarrier systems

The design and optimization of multicarrier communications systems often involve a maximization of the total throughput subject to system resource constraints. The optimization problem is numerically difficult to solve when the problem does not have a convexity structure. This paper makes progress toward solving optimization problems of this type by showing that under a certain condition called the time-sharing condition, the duality gap of the optimization problem is always zero, regardless of the convexity of the objective function. Further, we show that the time-sharing condition is satisfied for practical multiuser spectrum optimization problems in multicarrier systems in the limit as the number of carriers goes to infinity. This result leads to efficient numerical algorithms that solve the nonconvex problem in the dual domain. We show that the recently proposed optimal spectrum balancing algorithm for digital subscriber lines can be interpreted as a dual algorithm. This new interpretation gives rise to more efficient dual update methods. It also suggests ways in which the dual objective may be evaluated approximately, further improving the numerical efficiency of the algorithm. We propose a low-complexity iterative spectrum balancing algorithm based on these ideas, and show that the new algorithm achieves near-optimal performance in many practical situations.     

Spectrum Management for Interference-Limited Multiuser Communication Systems

Consider a multiuser communication system in a frequency selective environment whereby users share a common spectrum and can interfere with each other. Assuming Gaussian signaling and no interference cancelation, we study optimal spectrum sharing strategies for the maximization of sum-rate under separate power constraints for individual users. Since the sum-rate function is nonconcave in terms of the users' power allocations, there can be multiple local maxima for the sum-rate maximization problem in general. In this paper, we show that, if the normalized crosstalk coefficients are larger than a given threshold (roughly equal to $1/2$ ), then the optimal spectrum sharing strategy is frequency division multiple access (FDMA). In case of arbitrary positive crosstalk coefficients, if each user's power budget exceeds a given threshold, then FDMA is again sum-rate optimal, at least in a local sense. In addition, we show that the problem of finding the optimal FDMA spectrum allocation is NP-hard, implying that the general problem of maximizing sum-rate is also NP-hard, even in the case of two users. We also propose several simple distributed spectrum allocation algorithms that can approximately maximize sum-rates. Numerical results indicate that these algorithms are efficient and can achieve substantially larger sum-rates than the existing Iterative Waterfilling solutions, either in an interference-rich environment or when the users' power budgets are sufficiently high.