Range Assignment for Biconnectivity and k-Edge Connectivity in Wireless Ad Hoc Networks

Depending on whether bidirectional links or unidirectional links are used for communications, the network topology under a given range assignment is either an undirected graph referred to as the bidirectional topology, or a directed graph referred to as the unidirectional topology. The Min-Power Bidirectional (resp., Unidirectional) k-Node Connectivity problem seeks a range assignment of minimum total power subject to the constraint that the produced bidirectional (resp. unidirectional) topology is k-vertex connected. Similarly, the Min-Power Bidirectional (resp., Unidirectional) k-Edge Connectivity problem seeks a range assignment of minimum total power subject to the constraint the produced bidirectional (resp., unidirectional) topology is k-edge connected. The Min-Power Bidirectional Biconnectivity problem and the Min-Power Bidirectional Edge-Biconnectivity problem have been studied by Lloyd et al. [23]. They show that range assignment based the approximation algorithm of Khuller and Raghavachari [18], which we refer to as Algorithm KR, has an approximation ratio of at most 2(2 – 2/n)(2 + 1/n) for Min-Power Bidirectional Biconnectivity, and range assignment based on the approximation algorithm of Khuller and Vishkin [19], which we refer to as Algorithm KV, has an approximation ratio of at most 8(1 – 1/n) for Min-Power Bidirectional Edge-Biconnectivity. In this paper, we first establish the NP-hardness of Min-Power Bidirectional (Edge-) Biconnectivity. Then we show that Algorithm KR has an approximation ratio of at most 4 for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity, and Algorithm KV has an approximation ratio of at most 2k for both Min-Power Bidirectional k-Edge Connectivity and Min-Power Unidirectional k-Edge Connectivity. We also propose a new simple constant-approximation algorithm for both Min-Power Bidirectional Biconnectivity and Min-Power Unidirectional Biconnectivity. This new algorithm applies only to Euclidean instances, but is best suited for distributed implementation. A preliminary version of this work appeared in the proceedings of the 2nd International Conference on AD-HOC Network and Wireless (Adhoc-Now 2003). Research performed in part while visiting the Max-Plank-Institut fur Informatik. Gruia Calinescu is an Assistant Professor of Computer Science at the Illinois Institute of Technology since 2000. He held postdoc or visiting researcher positions at DIMACS, University of Waterloo, and Max-Plank Institut fur Informatik. Gruia has a Diploma from University of Bucharest and a Ph.D. from Georgia Insitute of Technology. His research interests are in the area of algorithms. Peng-Jun Wan has joined the Computer Science Department at Illinois Institute of Technology in 1997 and has been an Associate Professor since 2004. He received his Ph.D. in Computer Science from University of Minnesota in 1997, M.S. in Operations Research and Control Theory from Chinese Academy of Science in 1993, and B.S. in Applied Mathematics from Tsinghua University in 1990. His research interests include optical networks and wireless networks.     

生存能力技术及其实现案例研究

生存能力技术谋求增强系统在面临攻击、失效等灾难情况下仍能继续提供服务的能力。本文提出了以多样化分布式动态备份技术和主动漂移机制为手段，以被保护目标的机动性和隐蔽性为目的的生存能力技术模型。提出了多样化体系理论及其实现案例，基于该理论设计并实现了自适应TOM方法。最后通过模拟和测试探讨了生存能力的评价方法，并验证了本文的结果。     

分布式无线传感器网络通信协议研究

在归纳分布式无线传感器网络研究进展的基础上，给出了综合分布式无线传感器网络技术各个方面的协议体系结构，并在新的体系结构下，系统地阐述了分布式无线传感器网络通信协议研究的进展，介绍了典型的应用案例和国外相关计划的研究情况。最后，指明了这一处于发展初期的研究领域的未来发展方向。     

Implementation of RNS-Based Distributed Arithmetic Discrete Wavelet Transform Architectures Using Field-Programmable Logic

Currently there are design barriers inhibiting the implementation of high-precision digital signal processing (DSP) objects with field programmable logic (FPL) devices. This paper explores overcoming these barriers by fusing together the popular distributed arithmetic (DA) method with the residue number system (RNS) for use in FPL-centric designs. The new design paradigm is studied in the context of a high-performance filter bank and a discrete wavelet transform (DWT). The proposed design paradigm is facilitated by a new RNS accumulator structure based on a carry save adder (CSA). The reported methodology also introduces a polyphase filter structure that results in a reduced look-up table (LUT) budget. The 2C-DA and RNS-DA are compared, in the context of a FPL implementation strategy, using a discrete wavelet transform (DWT) filter bank as a common design theme. The results show that the RNS-DA, compared to a traditional 2C-DA design, enjoys a performance advantage that increases with precision (wordlength).     

分布式光纤拉曼放大器的增益平坦设计

介绍了在波分复用（WDM）系统中分布式光纤拉曼放大器（FRA）的理论分析模型。在此基础上，对增益平坦设计所需考虑的因素进行了分析；最后通过试验证明了它的有效性。     

分布式光纤喇曼放大技术及其在WDM系统中的应用

介绍了分布式光纤喇曼放大技术的原理、特点和应用 ,并从受此影响的 WDM传输系统的信噪比、噪声指数和品质因数三个方面讨论了光纤喇曼放大技术在提升光纤通信系统性能方面的重要作用。     

Inequalities for the Moments and Distribution of the Ladder Height of a Random Walk

We obtain upper bounds for the tail distribution of the first nonnegative sum of a random walk and for the moments of the overshoot over an arbitrary nonnegative level if the expectation of jumps is positive and close to zero. In addition, we find an estimate for the expectation of the first ladder epoch.     

基于EAI的多层分布式应用与实现

针对目前大型企业各类应用迅速增加但应用之间缺乏有效通信的问题,采用企业应 用集成(EAI)技术,提出了4层分布式应用体系结构,实现流程自动化和松耦合的应用集成.文中首先从EAI技术和常见解决方案出发,详细阐述了表示层、企业门户、EAI总线层和数据源层的功能及软件结构,并结合电信业务运营支撑系统的实际需求,给出了J2EE平台下的应用实例开发.利用组件和容器的技术构建企业门户,通过工作流和企业Java组件(EJB)技术实现EAI总线,借助资源适配器完成应用之间的互连互通.该系统现已投入实际运行,取得了良好的应用效果.     

电容传感器在使用中存在的几个问题及处理方法

随着电容测量技术的迅速发展，电容传感器在非电量测量和自动检测中得到广泛应用，但它在使用过程中也存在一些问题，针对在使用电容传感器过程中存在的几个问题，从电容传感器的原理和工作过程两个方面进行了讨论，并提出行之有效的处理方法。     

A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.