Bin-packing with fragile objects and frequency allocation in cellular networks

We consider two related optimization problems: bin-packing with fragile objects and frequency allocation in cellular networks. The former is a generalization of the classical bin-packing problem and is motivated by the latter. The problem is as follows: each object has two attributes, weight and fragility. The goal is to pack objects into bins such that, for every bin, the sum of weights of objects in that bin is no more than the fragility of any object in that bin. We consider approximation algorithms for this problem. We provide a 2-approximation to the problem of minimizing the number of bins. We also show a lower bound of 3/2 on the approximation ratio. Unlike for the classical bin-packing problem, this lower bound holds in the asymptotic case. We then consider the approximation with respect to fragility and provide a 2-approximation algorithm (i.e., our algorithm uses the same number of bins as the optimum, but the weight of objects in a bin can exceed the fragility by a factor of 2). We then consider the frequency allocation problem (which is a special case of bin-packing with fragile objects) and give improved approximation algorithms for it. Finally, we consider a probabilistic setting and show that our algorithm for frequency allocation approaches optimality as the number of users increases.

A High-Order Temperature-Compensated Subthreshold Voltage Reference Using Channel Length Modulation Compensation Technique

The paper presents a novel high-order temperature-compensated subthreshold voltage reference that utilizes temperature characteristics of the gate-to-source voltage of subthreshold MOS transistor. The proposed high-order temperature-compensated voltage reference has been designed using two CMOS voltage references and a current subtraction circuit to achieve a low temperature coefficient over a wide temperature range. The proposed circuit offers an output reference voltage of 250.8 mV, line sensitivity of 0.0674%/V and temperature coefficient of 37.4 ppm/°C for the temperature range varying from???20 \(\mathrm{^\circ{\rm C} }\) to 140 °C at nominal conditions. The power supply rejection ratio is obtained as???46.02 dB at a frequency of 100 Hz and???41.91 dB at a frequency of 1 MHz. The proposed circuit shows an output noise of 1.86 \(\mathrm{\mu V}/\surd \mathrm{Hz}\) at 100 Hz and 259.72 \(\mathrm{nV}/\surd \mathrm{Hz}\) at 1 MHz. The proposed circuit has been designed in BSIM3V3 180 nm CMOS technology using Cadence tool. The corner analysis of the proposed circuit has also been performed to show its performance in extreme conditions. The proposed circuit occupies a small chip area of 51 \(\upmu\)m?×?75.3 \(\upmu\)m.

     

On the randomization of transmitter power levels to increase throughput in multiple access radio systems

To enhance the throughput of a slotted random access protocol in a radio communication system, we describe the use of a scheme in which multiple power levels are used at the transmitters. We first consider a situation in which n transmitters are simultaneously trying to send a packet to a central receiving station using a time‐slotted access protocol, like slotted ALOHA. Each of these transmitters randomly chooses one of m discrete power levels during each attempt to send a packet. One of the simultaneously sent packets can often be successfully received due to the power capture effect. We consider two types of capture models: (1) one in which the transmitter with the largest received power captures the channel, and (2) one in which the transmitter captures the channel only if its signal‐to‐interference ratio is above some threshold when received at the central station. In this paper, we determine the optimal transmit probabilities for the power levels as well as the optimal values of the power levels themselves, when their range is constrained and for cases both with and without Rayleigh fading. After determining the precise optimal power levels and probabilities for maximizing the capture probabilities (i.e., for a given n), we propose a less complex, but nearly optimal, approximate approach based on using logarithmically equi‐spaced levels. After demonstrating the closeness of our suboptimal results to the optimal results, we apply our approach to the problem of optimizing the throughput of the slotted ALOHA protocol for a case in which the input traffic is generated according to a Poisson process. Several numerical examples are presented along with a demonstration of how the optimal choice of power levels and probabilities can enhance throughput relative to previous ad hoc methodologies.     

Middleware benchmarking: approaches,results, experiences

The report summarizes the results of the Workshop on Middleware Benchmarking held during OOPSLA 2003. The goal of the workshop was to help advance the current practice of gathering performance characteristics of middleware implementations through benchmarking. The participants of the workshop have focused on identifying requirements of and obstacles to middleware benchmarking and forming a position on the related issues. Selected requirements and obstacles are presented, together with guidelines to adhere to when benchmarking, open issues of current practice, and perspectives on further research. Copyright © 2005 John Wiley & Sons, Ltd.