Energy-Efficient Communication in Multi-interface Wireless Networks

We study communication problems in wireless networks supporting multiple interfaces. In such networks, two nodes can communicate if they are close enough and share a common interface. The activation of each interface has a cost reflecting the energy consumed when a node uses this interface. We distinguish between the homogeneous and heterogeneous case, depending on whether all nodes have the same activation cost for each interface or not. For the homogeneous case, we present a (3/2+?)-approximation algorithm for the problem of achieving connectivity with minimum activation cost, improving a previous bound of 2. For the heterogeneous case, we show that the connectivity problem is not approximable within a sublogarithmic factor in the number of nodes and present a logarithmic approximation algorithm for a more general problem that models group communication.     

多信道多接口混合网络容量研究

无线自组织网络有一个基本问题,即网络容量,它反映随着网络规模的增大,每个节点的数据吞吐量是如何变化的,该变化情况体现网络的可扩展性。多信道多接口混合网络的容量受到接口在信道间转换能力的影响和制约。通过建立该网络容量分析的数学模型,分别对接口固定、接口受限和接口自由转换3种情况下的网络容量进行研究,估计了它们的容量上限,构建了容量下界。理论分析结果表明接口转换能力对网络容量有重要影响。当接口可以自由转换时,网络容量没有损失。该研究结果为网络系统优化提供了重要理论参考。     

无线多接口多信道Mesh网络下多径路由协议分析

针对无线多接口多信道Mesh网络环境,对两种多径路由模型进行比较分析。根据支持多接口多信道的无线设备的特点,提出了一套较为高效的路由方式。该方案从源节点到目的节点利用提出的接口分配策略,从不同的接口和信道建立多条可同时工作的路由和多条不重叠的备份路由以大幅提升网络性能。它充分利用了多接口多信道移动设备的性能优势,更适合Mesh网络的拓扑特点。仿真测试表明,使用该方案,在端到端时延,网络吞吐量等方面提供了更佳的性能。     

一种最小化最大带宽利用率的TE路由算法

随着网络中流量的迅速增长，流量工程对于减小拥塞、提高网络资源的使用效率、满足业务的QoS要求，正在起着越来越重要的作用．提出了一种对Dijkstra算法进行改进的最小化最大带宽利用率TE路由算法．该算法在搜寻路径的过程中，将原来Dijkstra算法中的以路径代价最小为目标，更改为以最小化最大带宽利用率为目标．仿真证明，算法在一定程度上达到了均衡负载分布的作用．     

Preemption With Rerouting to Minimize Service Disruption in Connection-Oriented Networks

Resource allocation is a fundamental problem in connection-oriented networks. A preemption mechanism would provide available and reliable services to new connections with higher priority by tearing down existing connections of lower priority. However, end users of the existing connections that are preempted will suffer service disruptions. The duration spent and the work done for these connections are wasted, leading to lower useful utilization of the overall network resources. Soft preemption can alleviate this by rerouting a connection that is about to be preempted before actually tearing it down so that the interruption of ongoing service can be avoided. In this paper, we focus on minimizing the service disruptions caused as a result of preemption by proposing algorithms that incorporate the soft preemption feature. A centralized algorithm is developed to select the network links that have a high number of reroutable connections in order to minimize service disruptions. For feasible deployment, a decentralized preemption algorithm that uses local information is subsequently proposed. Simulation results indicate that these approaches not only reduce the service disruption but also lead to higher network throughput than what can be achieved by existing preemption algorithms.      

A Parallel Algorithm for Partitioning a Point Set to Minimize the Maximum of Diameters

Given a set S of n points in the plane, we consider the problem of partitioning S into two subsets such that the maximum of their diameters is minimized. We present a parallel algorithm to solve this problem that runs in time O(log n) using the CREW PRAM with 0(n²) processors.     

能量捕获传感网中吞吐量最大化的占空比方案

对于以超级电容为储能设备且工作在占空比模式下的能量捕获传感网,其节点的平均能量捕获速率和吞吐量均很大程度上取决于节点开始休眠时的电容电压和醒来工作时的电容电压。首先,通过理论分析证明传感器节点的能量捕获速率很大程度上取决于电容的即时电压值;然后,对节点的最大吞吐量问题进行建模;最后,提出一种最优化方案来确定开始休眠时的电容电压和醒来工作时的电容电压的最佳取值,从而最大化节点的吞吐量。实验表明,所提方案的吞吐量比已有占空比方案的吞吐量有明显的提高。     

无向平面单位容量网络中的最大流

无向平面单位容量网络中的最大流问题在VLSI设计等领域中有广泛的应用.针对无向平面单位容量网络的特点, 给出这类网络中一个O(n)时间的最大流算法, 比一般平面网络中O(nlog n)时间的最大流算法快log n倍.     

无线传感器网络中的最大生命期基因路由算法

无线传感器网络(wireless sensor networks,简称WSNs)由一组低功率且能量受限的传感器节点构成,设计此类网络的一个基本挑战便是最大化网络生命期的问题.在WSNs中,由于邻近传感器节点所收集的数据之间往往具有时空相关性,多采用数据聚合技术作为去除数据冗余、压缩数据大小的有效手段.合理地应用数据聚合技术,可以有效地减少数据传递量,降低网络能耗,从而延长网络生命期.研究了WSNs中结合数据聚合与节点功率控制的优化数据传递技术,提出了一种新的最大化网络生命期的路由算法.该算法采用遗传算法(genetic algorithm,简称GA)最优化数据聚合点的选择,并采用梯度算法进一步优化结果.该算法均衡节点能耗,并最大化网络生命期.仿真结果表明,该算法极大地提高了网络的生命期.     

无线传感器网络中的最大生命期基因路由算法

无线传感器网络(wireless sensor networks,简称WSNs)由一组低功率且能量受限的传感器节点构成,设计此类网络的一个基本挑战便是最大化网络生命期的问题.在WSNs中,由于邻近传感器节点所收集的数据之间往往具有时空相关性,多采用数据聚合技术作为去除数据冗余、压缩数据大小的有效手段.合理地应用数据聚合技术,可以有效地减少数据传递量,降低网络能耗,从而延长网络生命期.研究了WSNs中结合数据聚合与节点功率控制的优化数据传递技术,提出了一种新的最大化网络生命期的路由算法.该算法采用遗传算法(genetic algorithm,简称GA)最优化数据聚合点的选择,并采用梯度算法进一步优化结果.该算法均衡节点能耗,并最大化网络生命期.仿真结果表明,该算法极大地提高了网络的生命期.     

无线传感器网络动态占空比MAC协议

提出一个能量高效的传感器网络MAC协议(EMAC协议)。传感器节点在空闲时进入睡眠状态,大大减少了空闲侦听,采用可变占空比工作方式降低能量消耗。仿真实验显示EMAC协议大大降低了节点的能量消耗,明显提高了网络的生命期。     

Duty Cycling Centralized Hierarchical Routing Protocol With Content Analysis Duty Cycling Mechanism for Wireless Sensor Networks

In this paper, a Duty Cycling Centralized Hierarchical Protocol (DCCHP) has been proposed for wireless sensor networks. DCCHP is an energy efficient protocol that prolongs the lifetime of the network by applying a duty cycling mechanism named DCM that chooses the nodes that send unimportant data in a certain epoch to be candidates to be put to sleep. But if the proposed equations for choosing the cluster head nodes put any of them in a high priority it works in the active mode. When comparing DCCHP to the previously proposed LEACH-CS, LEACH-C protocols, using a simulation study, DCCHP in average extends the network lifetime 50% more than LEACH-CS and about 60% more than LEACH-C across a different number of nodes in the network scaled up to 1000 nodes. That is because DCCHP chooses the definite number of nodes of unimportant data to be switched to sleeping mode unlike LEACH-CS and unlike LEACH- C which keeps all nodes in active mode. Also an analytical study of energy consumption proves that DCCHP preserves energy consumption more than LEACH-CS and DCCHP. DCCHP has been proposed for applications with scarce resources.     

网络最大流问题求解的符号ADD增广路径算法

本文通过对网络及网络最大流问题的符号代数判定图（ADD）描述,将网络中的结点和边用ADD隐式表示,并利用Gabow的容量变尺度算法的主要思想,将一般网络最大流问题化为一系列的单位容量网络最大流问题,结合Hachtel等的单位容量网络最大流问题的求解算法,给出了网络最大流问题求解的符号ADD增广路径算法,简称为符号ADD算法.与Dinic算法、Karzanov算法相比,本文算法的空间复杂度得到了改善.实验结果表明,本文算法是切实有效的,且可处理更大规模的问题.     

The Single Machine Batching Problem with Family Setup Times to Minimize Maximum Lateness is Strongly NP-Hard

In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard.     

A Note on Scheduling Tall/Small Multiprocessor Tasks with Unit Processing Time to Minimize Maximum Tardiness

We study the scheduling situation where n tasks, subjected to release dates and due dates, have to be scheduled on m parallel processors. We show that, when tasks have unit processing times and either require 1 or m processors simultaneously, the minimum maximal tardiness can be computed in polynomial time. Two algorithms are described. The first one is based on a linear programming formulation of the problem while the second one is a combinatorial algorithm. The complexity status of this tall/small task scheduling problem P|r _i ,p _i =1, size _i {1,m}|T _max was unknown before, even for two processors.     

基于MIC的深度置信网络研究

传统的深度置信网络(DBNs)训练过程采用重构误差作为RBM网络的评价指标,它能在一定程度上反映网络对训练样本的似然度,但它并不是可靠的。而最大信息系数(MIC)能反映两个属性间的相关度,保留相关度较大的属性,且MIC较稳健,不易受异常值的影响,可作为网络评价指标。故提出一种基于最大信息系数(MIC)的深度置信网络方法,一方面用MIC对数据进行降维预处理,提高数据与网络的拟合度,降低网络分类误差;另一方面将MIC作为网络评价标准,改进重构误差的不可靠性。分别利用传统方法与基于MIC的深度置信网络方法对手写数据集MNIST和USPS进行分类实验,结果表明,基于MIC的深度置信网络方法能有效地提高识别率。     

无线Ad Hoc 网络最大生命周期路由算法的诚实机制

将已有的生命周期路由算法分成两类:普通Max-Min(GMM)算法和条件Max-Min(CMM)算法,然后为这两类算法分别提出它们的诚实机制.通过给予中继节点适当的报酬,这些诚实机制可以确保已有的算法在面对自私节点的时候也可以实现它们的设计目标.说明生命周期路由算法的本质可以使这种报酬率相对较低且比较稳定,实验结果也进一步证明了这一点.     

采用预编码的GSM网络最大互信息优化方法研究

为了提高广义空间调制(GSM)互信息的性能,提出了一种新的基于椭球算法的预编码方案。首先,为了对含有互信息的预编码器进行优化,推导出了有限字符输入下的GSM互信息解析表达式。在最大化GSM互信息的过程中,为了解决联合预编码设计的非凸耦合问题,将GMS系统转换成虚拟的多输入多输出(MIMO)系统。然后,在考虑所有子信道功率约束的条件下,使用了扩展的椭球算法。实验结果表明,提出的预编码方案大大提升了GSM互信息的性能。