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.     

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

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

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

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

开关电源的平均电流自动均流技术

针对多个开关电源并联时易出现负载电流在各模块间分配不均的现象,介绍了常用的负载电流自动均流法——平均电流自动均流法及其工作特性。并针对其存在母线电压降低的缺陷,提出了一种改进的平均电流自动均流方法,经试验证明均流精度比较高。     

国产风机盘管空调系统常见问题分析

分析了国产风机盘管使用中常见的问题,指出机组因风量不足、冷量风量匹配不合理以及风机盘管某些设备故障,导致了风机盘管精度低、舒适性差、能耗高等一系列问题。指出应引起空调设计和运行维护人员的注意。     

以一种新的距离度量作为反馈的相关跟踪方法

基于相关的模板匹配方法在图像跟踪中得到了广泛的应用,但是这种方法的主要缺点是对图像噪声非常敏感,而且由这种方法得出的相关曲面比较平坦。为了有效抑制噪声和局部遮挡对图像的影响,提出用鲁棒统计中的一个值代替相关值作为距离度量。它不是计算两幅图像的对应像素差值,而是计算两幅图像中差别不大的对应像素对的个数。实验证明这样得到的曲面相对　　收稿日期:2003 08 31;　修订日期:2003 10 28作者简介:张桂林(1944 ),男,天津人,教授,博士生导师,主要研究方向为自动识别、人体生物统计特征识别、图像处理算法与系统性能评估等。　　　　　　　要尖锐得多。当上述的距离度量应用于跟踪过程中时,模板的合理更新对跟踪非常重要。基于上述的距离度量方法,提出了一种新的模板更新策略。利用两幅图像中近似像素在整修匹配模板像素中所占的比例大小决定加权系数。这种加权策略可以自适应地根据图像序列的变化选择更新相关模板,同时在一定程度上减小模板漂移的危险。     

构建高扩展性的县级广电宽带数据网络

提出在县市级广电宽带数据网络的建设过程中,要着眼业务发展,突出高扩展性,构建基于标准、扩展灵活的主干网,实现网络建设的可持续性发展,并结合实际,从核心设备、端口、中继带宽、网络业务4个方面对扩展能力进行了阐述.     

新型的芯片间互连用CMOS/BiCMOS驱动器

从改善不同类型 IC芯片之间的电平匹配和驱动能力出发 ,设计了几例芯片间接口 (互连 )用 CMOS/Bi CMOS驱动电路 ,并提出了采用 0 .5 μm Bi CMOS工艺 ,制备所设计驱动器的技术要点和元器件参数。实验结果表明所设计驱动器既具有双极型电路快速、大电流驱动能力的特点 ,又具备 CMOS电路低压、低功耗的长处 ,因而它们特别适用于低电源电压、低功耗高速数字通信电路和信息处理系统。     

两个DEA的逆问题的解法的探讨

文[1]提出了两个DEA的逆问题，并用搜索法来解．而本文根据所证的定理，对每个问题一般只要解二、三个线性规划问题就能得到答案．     

交叉试验

发生了质量事故,是设备、操作等硬件的缘故,抑或药液的缘故?通过交叉试验的故事,把真相找了出来。