基于分散式查找的Web服务器集群

随着www用户快速增加，人们对Web服务器的需求也越来越高，集群是解决这个问题的一种重要方案。但是现有的Web服务器集群还存在自适应性差、有系统瓶颈等不足。该文在分散式查找算法Pastry的基础之上，提出，一种新的Web服务器集群方案。它具有分散式查找算法的诸多优点，如可扩展、自组织、高容错和分散特性，较好地克服了传统Web服务器集群方案的不足。     

维持O(1)节点信息的资源查找算法

提出一种用于对等网络的资源查找算法。算法采用哈希函数为节点和资源分配唯一的标识符,并将标识符表示为L进制的比特串,通过对标识符进行左移附加后缀的操作来构造每个节点所维持的路由信息。实现了在维护O（1）节点信息的情况下,平均查找逻辑路由跳O（logN）内查找定位任意网络资源。     

基于非结构化对等网络的分散式桌面网格平台

描述了一个基于非结构化对等网络、可以共享网络上空闲资源的JVMs虚拟机的桌面网格平台UDDG(unstructureddecentralized desktop grid)。提出了对等实体的最小活跃邻居节点数、更新时间域值等概念,每个对等实体维护了一个最小活跃邻居数的列表,结合非结构化对等网络的网络跳数的机制,通过广播查找消息来寻找资源的虚拟机。通过构建评测环境,运行并行案例程序计算结果表明,UDDG提供了一种构建高性能的桌面网格平台的新思路。     

高效的混合式查找方案

通过整合基于服务器/客户机模式的集中式查找方案和基于对等计算模式的分散式查找方案,提出了一种混合式查找方案。该方案既有可扩展性、高容错性和自组织性等分散式查找方案的优点,又有利于集中管理和控制,安全性好等集中式查找方案的优势。仿真实验结果表明,该方案的RDP指标优于常规的分散式查找方案,实际查询时间开销更是远远少于常规的分散式查找方案。     

基于动态混合查找的WSN自适应路由算法

针对无线传感器网络(WSN)需动态调整路由请求域的问题,提出一种基于动态混合查找的WSN自适应路由算法。该算法依据路由查找的返回状态,以圆柱形路由请求域的半径作为调整参数,利用折半查找和指数查找相结合的方法对路由请求域进行动态自适应调整。仿真结果表明,该算法在数据包投递率、路由开销和数据包平均时延上的性能均优于AODVjr路由算法。     

一种基于Fibonacci数的有序线性表查找算法

在设计F ibonacci(菲波那契)查找算法的基础上定义了F ibonacci查找判定树,并利用F ibonacci数的封闭型表达式推导出此种判定树的高度计算公式;证明了在查找成功时,F ibonacci查找的一个优点是总查找长度优于折半查找,F ibonacci查找的另一优点在于访问存放在外存储器上大量的有序表数据时,只需对有序表进行加减运算分割。     

基于贝叶斯网的P2P系统路由查找算法

对等网络中的一个关键问题就是如何找到储存有期望数据的节点,因而目标资源的查询算法研究是P2P网络的关键部分,该算法决定了P2P系统的性能。在对等网络中的每一个节点都存有一张记录与之相邻的节点的路由信息表,着重讨论如何根据各节点所存储的路由表建立相应的贝叶斯网络,并分析某一节点接收到查询请求的概率,进而得出一个计算概率的数学公式。为使所得概率计算公式尽可能地符合现实情况,每一个对等点分别被赋予不同的权,随后对所赋权进行调整。最后,对每个节点的可信度提出一个设置方案,并基于可信度提出一个改进的路由算法,试验表明该算法能够一定程度上改善对等网络的性能。     

IPv6的快速路由查找算法研究

TCAM被广泛用于执行快速路由查找,不管前缀的数量和长度,它能在极短时间内解决最佳前缀问题。与基于软件解决方法相比较,TCAM能提供持续吞吐量和简单系统体系,这对IPv6路由查找来说是很有吸引力的。然而,它也有一些缺点,例如入口数量有限,价格昂贵和能源消耗。因此,本文提出一种有效、能减少所需TCAM的算法,该算法通过增加微DRAM来消除98％的TCAM入口。实验证明,该算法效果良好,可以大大提高IPv6路由查找性能。     

支持压缩和多下一跳查找的路由查找方案

TCAM(ternary content addressable memory)是目前流行的一种高速路由查找技术.TCAM具有查找速度快、操作简单的优点,但同时它也具有3个明显的缺点:成本高、功耗大和路由更新复杂.路由器为了实现负载平衡以及策略路由,在路由表中保存着相当数量的具有多个下一跳的路由表项.基于TCAM技术,提出一种支持多下一跳的高速路由查找方案.方案通过两级索引表实现了多下一跳路由的存储和快速访问.为了提高TCAM的更新效率,方案还提出了一个N子空间TCAM更新算法.该算法对目前实际网络中的路由表,可达到近似O(1)的更新复杂度.为了减少TCAM的成本和功耗,方案中还使用了有效的路由压缩技术.压缩技术基于Trie树结构,实现简单.应用压缩技术,对于实际网络中的路由表,可减少20%的路由.该查找方案可以很容易地应用到未来的IPv6网络中.     

基于P2P的简单查找算法研究

随着P2P系统的发展,它在Internet上的应用越来越广泛,尤其是对分布式数据对象的查找。为此,提出二种基于对等网络系统的简单查找方法。利用一致哈希函数把给定的关键字映射到一个虚拟标识环上的节点,在标识环中查找指定关键字的映射。这种方法能够正确高效地完成数据对象的查找。     

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem

We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an ${\mathcal {O}}(1)$ -approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent ?≥1, we obtain a randomized ${\mathcal {O}}(1)$ -approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to $\mathcal{O}(\log(n))$ bits.     

节点信息感知的非均匀分簇路由算法

无线传感器网络中,簇头选举不合理将导致节点能量消耗过快,使其过早失效,网络过早结束生命周期。对此提出一种节点信息感知的非均匀分簇路由算法:充分考虑节点邻域基数、位置感知、剩余能量,通过非均匀分簇确定最优簇头;簇的形成阶段,节点加入距自己最近的簇,通信上采用簇内单跳、簇间单跳、多跳相结合的方式。仿真实验表明,该算法与LEACH,CEBRCA相比,在网络生命周期、能量利用率和数据发送方面都具有较好的性能。     

带模糊控制的动态指针推进移动性管理策略

移动性管理是移动计算研究领域的一个挑战性课题.提出了一种带模糊控制器的动态指针推进移动性管理策略.这种策略以移动台的移动次数、指针链长度及位置管理的代价作为模糊控制器的输入,指针长度的改变量作为模糊控制器的输出,对指针长度进行动态调整.仿真实验结果表明：当移动台的呼入移动比较低时,这种策略比现行无线移动通信网络的移动性管理策略的性能更优.     

一种具有O(1/T)收敛速率的稀疏随机算法

随机梯度下降(stochastic gradient descent, SGD)是一种求解大规模优化问题的简单高效方法,近期的研究表明,在求解强凸优化问题时其收敛速率可通过α-suffix平均技巧得到有效的提升.但SGD属于黑箱方法,难以得到正则化优化问题所期望的实际结构效果.另一方面,COMID(composite objective mirror descent)是一种能保证L1正则化结构的稀疏随机算法,但对于强凸优化问题其收敛速率仅为O(logT/T).主要考虑“L1+Hinge”优化问题,首先引入L2强凸项将其转化为强凸优化问题,进而将COMID算法和α-suffix平均技巧结合得到L1MD-α算法.证明了L1MD-α具有O(1/T)的收敛速率,并且获得了比COMID更好的稀疏性.大规模数据库上的实验验证了理论分析的正确性和所提算法的有效性.     

A Parallel Deadlock Detection Algorithm with O(1) Overall Run-time Complexity

This article proposes a novel parallel, hardware-oriented deadlock detection algorithm for multiprocessor system-on-chips. The proposed algorithm takes full advantage of hardware parallelism in computation and maintains information needed by deadlock detection through classifying all resource allocation events and performing class specific operations, which together make the overall run-time complexity of the new method O(1). We implement the proposed algorithm in Verilog HDL and demonstrate in the simulation that each algorithm invocation takes at most four clock cycles in hardware.     

GPS和无线传感器网络融合定位算法研究

为了解决普适计算环境下室内外无缝定位问题,提出了一种卫星定位和无线传感器网络组合定位的算法.算法主要利用了GPS卫星定位系统伪距观测数据和无线传感器网络距离观测数据联合进行位置解算.仿真结果表明,算法与传统的GPS定位相比,增加定位的适应范围,实现少于4颗可用卫星情况下的定位;与无线传感器网络定位算法相比,提高了定位精度.     

一种基于虚拟网格位置的分簇算法

为了延长无线传感器网络生命周期, 提出一种基于虚拟网格的分簇路由算法RPLG. 该算法将监测区域划分为若干虚拟网格, 同一网格内节点自组织成簇. 根据节点所在网格位置和剩余能量启动计时器选取本地簇首, 且簇内成员可以根据局部的信息调整簇的大小, 达到节省能量的目的. 仿真实验和分析表明: 该协议能均衡网络能量, 延长网络的生存时间.     

一类应急服务设施选址问题的模拟退火算法

讨论了一类带限期约束的应急服务设施选址问题,给出了其易于实现计算机计算的罚函数表示,在温度参数、迭代策略和算法终止条件三个方面设置了适合该问题的模拟退火算法,并通过实例的计算说明该算法是有效的。     

A Branch and Bound Algorithm for An Uncapacitated Facility Location Problem with a Side Constraint

In this paper, a branch and bound algorithm for solving an uncapacitated facility location problem (UFLP) with an aggregate capacity constraint is presented. The problem arises as a subproblem when Lagrangean relaxation of the capacity constraints is used to solve capacitated facility location problems. The algorithm is an extension of a procedure used by Christofides and Beasley (A tree search algorithm for the p-median problem. European Journal of Operational Research , Vol. 10, 1982, pp. 196–204) to solve p -median problems and is based on Lagrangean relaxation in combination with subgradient optimization for lower bounding, simple Lagrangean heuristics to produce feasible solutions, and penalties to reduce the problem size. For node selection, a jump-backtracking rule is proposed, and alternative rules for choosing the branching variable are discussed. Computational experience is reported.     

A New Algorithm To Solve Vehicle Routing Problems (VRPs)

Efficient Resource management has a direct influence on business performance and profitability. Vehicle Routing Problems (VRPs) considered in this paper are resource management problems where the aim is to use the limited number of resources to a large number of jobs so that the maximum number of jobs can be completed with minimum cost. A VRP consists of a workforce of maintenance engineers and a set of geographically distributed customers requiring certain services. The problem is complicated by incorporating certain technological and temporal constraints. The objective is to maximize the amount of work done measured in terms of total number of jobs completed and to minimize the total distance travelled by all the engineers. The solution to a VRP is a list of engineers and for each engineer a tour consisting of an ordered list of services to be completed by him under the given constraints. These Problems belong to the class of NP-Complete problems. The stochastic techniques such as Hill-Climbing (HC), Tabu Search (TS), Genetic Algorithms (GA) and Simulated Annealing (SA) are found to be suitable for solving these problems efficiently. It is found empirically that out of these SA gives good results for VRPs. But in some cases it also gives poor quality results. This happens due to not allocating intelligently the unallocated jobs in SA in subsequent iterations. A new algorithm is proposed to solve VRPs in this paper. This is achieved by allocating unallocated jobs intelligently in SA. The proposed algorithm is tested empirically on a number of randomly generated VRPs. Three types of VRPs considered are over resourced, under resourced and critically resourced VRPs. In almost all cases, the proposed algorithm completes a large number of jobs with minimum cost in comparison with SA.