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.     

Attribute Allocation and Retrieval Scheme for Large-Scale Sensor Networks

Wireless sensor network is an emerging technology that enables remote monitoring of large geographical regions. In this paper, we address the problem of distributing attributes over such a large-scale sensor network so that the cost of data retrieval is minimized. The proposed scheme is a data-centric storage scheme where the attributes are distributed over the network depending on the correlations between them. The problem addressed here is similar to the Allocation Problem of distributed databases. In this paper, we have defined the Allocation Problem in the context of sensor networks and have proposed a scheme for finding a good distribution of attributes to the sensor network. We also propose an architecture for query processing given such a distribution of attributes. We analytically determine the conditions under which the proposed architecture is beneficial and present simulation results to demonstrate the same. To the best of our knowledge, this is the first attempt to determine an allocation of attributes over a sensor network based on the correlations between attributes.     

Analysis of Distributed DDQ for QoS Router

In a packet switching network, congestion is unavoidable and affects the quality of real‐time traffic with such problems as delay and packet loss. Packet fair queuing (PFQ) algorithms are well‐known solutions for quality‐of‐service (QoS) guarantee by packet scheduling. Our approach is different from previous algorithms in that it uses hardware time achieved by sampling a counter triggered by a periodic clock signal. This clock signal can be provided to all the modules of a routing system to get synchronization. In this architecture, a variant of the PFQ algorithm, called digitized delay queuing (DDQ), can be distributed on many line interface modules. We derive the delay bounds in a single processor system and in a distributed architecture. The definition of traffic contribution improves the simplicity of the mathematical models. The effect of different time between modules in a distributed architecture is the key idea for understanding the delay behavior of a routing system. The number of bins required for the DDQ algorithm is also derived to make the system configuration clear. The analytical models developed in this paper form the basis of improvement and application to a combined input and output queuing (CIOQ) router architecture for a higher speed QoS network.     

质量控制图系统的实现及在SMT中的应用

本文将控制图理论与计算机技术相结合,开发了质量控制图系统.介绍了该系统的设计方案和关键技术问题,并以电子产品制造中监控SMT机的焊膏厚度为例说明了系统的应用.     

某雷达数据处理有关问题分析

对某雷达数据处理应用中存在的一些特殊问题进行讨论分析,并就具体问题提出了解决的方法.     

几种涉密网主机系统保护及审计技术的比较

论文比较详细地阐述了涉密网主机系统所面临的安全隐患,提出了涉密网主机安全防护所要解决的几个技术问题,并就可能实现的技术方法进行了探讨和比较。     

卫星电视上行站信号自动监测系统

每个卫星电视上行站都必须对卫星转发器上的电视信号进行监测,才能及时发现卫星电视上行信号的异常变化,准确处理异常突发干扰。为实现自动、连续、实时监测,就需要建立卫星电视上行站射频信号自动监测系统。文章详细介绍了一个自动监测系统的设计及实现。     

一种基于ECDSA的USB存储设备访问控制方案

文章针对使用USB存储设备造成的内部泄密问题,提出了一种USB存储设备访问控制方案,该方案对用户的身份认证基于安全强度很高的椭圆曲线数字签名算法,同时使用过滤器驱动程序实现了USB存储设备的读写控制,因而此方案具有较好的安全性、实用性和通用性。     

动力环境集中监控系统可靠性的提高

为实现电源设备乃至通信机房的少人或无人值守和集中维护,必须建立一套完善的电信局动力环境集中监控系统。文中结合番禺区电信局的实际,讨论了提高系统运行可靠性的几点措施,包括硬件方面与软件方面的手段,关键在于加强系统的运行管理。     

浅谈DC/DC变换器控制新方法

文中针对DC/DC变换器的特点,在现有控制和建模方法的基础之上,对DC/DC变换器的现代控制方法进行了归纳和总结,简要讨论了其控制原理,并比较了各种现代控制方法的优缺点,最后对DC/DC变换器控制方法的发展作了一定的展望。