We study the problem of jointly performing scheduling and congestion control in mobile ad-hoc networks so that network queues remain bounded and the resulting flow rates satisfy an associated network utility maximization problem. In recent years a number of papers have presented theoretical solutions to this problem that are based on combining differential-backlog scheduling algorithms with utility-based congestion control. However, this work typically does not address a number of issues such as how signaling should be performed and how the new algorithms interact with other wireless protocols. In this paper we address such issues. In particular: ldr We define a specific network utility maximization problem that we believe is appropriate for mobile adhoc networks. ldr We describe a wireless greedy primal dual (wGPD) algorithm for combined congestion control and scheduling that aims to solve this problem. ldr We show how the wGPD algorithm and its associated signaling can be implemented in practice with minimal disruption to existing wireless protocols. ldr We show via OPNET simulation that wGPD significantly outperforms standard protocols such as 802.11 operating in conjunction with TCP. This work was supported by the DARPA CBMANET program.

We give a model for the performance impact on wireless systems of the limitations of certain resources, namely, the base-station power amplifier and the available OVSF codes. These limitations are readily modeled in the loss model formulation as a stochastic knapsack. A simple and well-known recurrence of Kaufman and Roberts allows the predictions of the model to be efficiently calculated. We discuss the assumptions and approximations we have made that allow the use of the model. We have included the model in Ocelot, an Alcatel-Lucent tool for modeling and optimizing cellular phone systems. The model is fast to compute, differentiable with respect to the relevant parameters, and able to model broad ranges of capacity and resource use. These conditions are critical to our application of optimization.

We investigate models for uplink interference in wireless systems. Our models account for the effects of outage probabilities. Such an accounting requires a nonlinear, even nonconvex model, since increasing interference at the receiving base station increases both mobile transmit power and outage probability, and this results in a complex interaction. Our system model always has at least one solution, a fixed point, and it is provably unique under certain reasonable conditions. Our main purpose is to model real wireless systems as accurately as possible, and so we test our models on realistic scenarios using data from a sophisticated simulator. Our algorithm for finding a fixed point works very well on such scenarios, and is guaranteed to find the fixed point when we can prove it is unique. A slightly simplified model reduces the main data structure for aK-sector market to 16K2bytes of memory.

Consider the problem of decomposing a page image into text ruling lines, signatures, other line art, and other material. A fast classifier based on a skeletonization of the image and various curve-fitting techniques gives an initial labeling, followed by Baird's language-free layout analysis and a post-processor that uses the geometric layout to refine the decisions about text versus non-text.

Proper display and accurate recognition of document images are often hampered by degradations caused by poor scanning or transmission conditions. The authors propose a method to enhance such degraded document images for better display quality and recognition accuracy. The essence of the method is in finding and averaging bitmaps of the same symbol that are scattered across a text page. Outline descriptions of the symbols are then obtained that can be rendered at arbitrary solution. The paper describes details of the algorithm and an experiment to demonstrate its capabilities using fax images.

Consider the problem of generating bitmaps from character shapes given as outlines. The obvious scan-conversion process does not produce acceptable results unless important features such as stem widths are carefully controlled during the scan-conversion process. This paper describes a method for automatically extracting the necessary feature information and generating high-quality bitmaps without resorting to hand editing. Almost all of the work is done in a preprocessing step, the result of which is an intermediate form that can be quickly converted into bitmaps once the font size and device resolution are known. A heuristically defined system of linear equations describes how the ideal outlines should be distorted in order to produce the best possible results when scan converted in a straightforward manner. The Lova´sz basis reduction algorithm then reduces the system of equations to a form that makes it easy to find an approximate solution subject to the constraint that some variables must be integers. The heuristic information is of such a general nature that it applies equally well to Roman fonts and Japanese Kanji.

We give efficient, numerically-stable techniques for converting polynomial, and rational cubic curves to implicit form.We achieve numerical stability by working in a rotated coordinak system and using carefully chosen expressions for the coetlicients that appear in the implicit form.This is more practical than previously known methods which can be numerically unstable unless all computations are done in exact rational arithmetic.

We examine a class of algorithms for rasterizing algebraic curves based on an implicit form that can be evaluated cheaply in integer arithmetic using finite differences. These algorithms run fast and produce “optimal” digital output, where previously known algorithms have had serious limitations. We extend previous work on conic sections to the cubic and higher order curves, and we solve an important undersampling problem.

This paper gives a fast, linear-time algorithm for generating high-quality pixel representations of curved lines. The results are similar to what is achieved by selecting a circle whose diameter is the desired line width, and turning on all pixels covered by the circle as it moves along the desired curve. However, the circle is replaced by a carefully chosen polygon whose deviations from the circle represent subpixel corrections designed to improve the aesthetic qualities of the rasterized curve. For nonsquare pixels, equally good results are obtained when an ellipse is used in place of the circle. The class of polygons involved is introduced, an algorithm for generating them is given, and how to construct the set of pixels covered when such a polygon moves along a curve is shown. The results are analyzed in terms of a mathematical model for the uniformity and accuracy of line width in the rasterized image.