Qualitative Properties of a Certain Kinetic Model of a Binary Gas

We consider a system of kinetic equations with one-dimensional velocity space. The system is a simple mathematical model that describes the evolution of a two-component gas mixture at the molecular level. We study some qualitative properties of its solutions, in particular, the conservation laws and spectrum of the linearized problem. In the spatially homogeneous case we present the widest Lie algebra of admissible operators and construct some exact solutions in closed form. We indicate some methods for constructing numerical schemes conservative with respect to fulfillment of the discrete conservation laws of energy and the concentrations of the components.     

Worst case response times in a Bluetooth piconet: scheduling combining 1-RR or E-RR with FIFO or EDF

In this paper, we focus on the Bluetooth wireless network, analyzing its ability to support the Quality of Service (QoS) requirements defined by QoS sensitive applications. The QoS perceived by the application depends on the scheduling mechanisms chosen at the medium access layer. Hence, we propose to evaluate the ability of different Bluetooth scheduling algorithms (1-RR/FIFO, 1-RR/EDF, E-RR/FIFO and E-RR/EDF) to guarantee bounded transmission delays. First, we establish a bound on the worst case response time of any sporadic message using a worst case analysis. We then compare the computed bounds with the worst case response times obtained by simulation for different traffic distributions and show in which configurations our bounds are tight. We finally compare those different schedulings and show how to extend our results on worst case response times taking into account message segmentation.     

Average case analysis of DJ graphs

Sreedhar et al. [V.C. Sreedhar, G.R. Gao, Y.-F. Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Trans. Program. Lang. Syst. 20 (2) (1998) 388–435; V.C. Sreedhar, Efficient program analysis using DJ graphs, PhD thesis, School of Computer Science, McGill University, Montréal, Québec, Canada, 1995] have presented an elimination-based algorithm to solve data flow problems. A thorough analysis of the algorithm shows that the worst-case performance is at least quadratic in the number of nodes of the underlying graph. In contrast, Sreedhar reports a linear time behavior based on some practical applications.

In this paper we prove that for goto-free programs, the average case behavior is indeed linear. As a byproduct our result also applies to the average size of the so-called dominance frontier.

A thorough average case analysis based on a graph grammar is performed by studying properties of the j-edges in DJ graphs. It appears that this is the first time that a graph grammar is used in order to analyze an algorithm. The average linear time of the algorithm is obtained by classic techniques in the analysis of algorithms and data structures such as singularity analysis of generating functions and transfer lemmas.     

用数据融合理论减少壳体旋转低速误差的技术研究

在静电陀螺壳体旋转的数字方案中，采用数据融合技术处理光电编码器的两相输出，从而减少增量式光电编码器在低速或变向时受到的抖动干扰的影响和闭环反馈的测量误差。     

潘宁放电在密封电真空器件真空度测量中的应用

 密封电真空器件的可靠性尤其重要，而影响其可靠性的主要因素是真空度。对于具有两个电极的密封电真空器件由于无法利用其自身的电极结构直接测定其真空度，因此需要研究并建立一种合适的真空度测量方法。分析了利用潘宁放电来测量两个电极的密封电真空器件真空度的工作原理，设计了测试实验装置，初步建立了密封电真空器件的潘宁放电模型，给出了有关实验数据。     

Improving the Analysis of Distributed Non-Preemptive FP/DP* Scheduling with the Trajectory Approach

In this paper, we are interested in real-time flows requiring quantitative and deterministic Quality of Service (QoS) guarantees. We focus more particularly on two QoS parameters: the worst case end-to-end response time and jitter. We consider a non-preemptive scheduling of flows, called fp/dp*, combining fixed priority and dynamic priority established on the first node visited in the network. Examples of such a scheduling are fp/fifo* and fp/edf*. With any flow is associated a fixed priority denoting the importance of the flow from the user point of view. The arbritation between packets having the same fixed priority is done according to their dynamic priority. A classical approach used to compute the worst case end-to-end response time is the holistic one. We show that this approach leads to pessimistic upper bounds and propose the trajectory approach to improve the accuracy of the results. Indeed, the trajectory approach considers the worst case scenarios experienced by a flow along its trajectory. It then eliminates scenarios that cannot occur.     

Construction of quasi-periodic solutions of guaranteed accuracy by the small parameter method

Theorems on the localization of exact solutions are proved for a quasilinear mathematical model describing quasi-periodic processes. Based on these theorems, constructive algorithms are proposed for calculating quasi-periodic solutions with guaranteed accuracy. Quasi-periodic motions play an important role in engineering and physics, where they often represent determining states. Quasi-periodic motions can be found in many ecological, biological, and economic processes.     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

关于软件测试

在开发过程中，为保证软件的可靠性，开发人员使用了很多方法进行分析、设计及编码实现。但由于软件产品本身无形态，可能含有错误。软件测试代表了设计、编码的最终复审。     

Soft real‐time communications over Bluetooth under interferences from ISM devices

Bluetooth is a suitable technology to support soft real‐time applications like multimedia streams at the personal area network level. In this paper, we analytically evaluate the worst‐case deadline failure probability of Bluetooth packets under co‐channel interference as a way to provide statistical guarantees when transmitting soft real‐time traffic using ACL links. We consider the interference from independent Bluetooth devices, as well as from other devices operating in the ISM band like 802.11b/g and Zigbee. Finally, we show as an example how to use our model to obtain some results for the transmission of a voice stream. Copyright © 2006 John Wiley & Sons, Ltd.