Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of ?(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.     

Protocol for Dynamic Ad-Hoc Networks Using Distributed Spanning Trees

A dynamic ad-hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based a hold-and-forward or shuttling mechanisms. We introduce the notion of connectivity-through-time and the parameter holding-time as new fundamental concepts that can be used by ad-hoc routing algorithms. For various network connectivity scenarios we evaluate the impact of these concepts on the performance of ad-hoc routing algorithms. Using simulation, we study the throughput, reachability and message–reachability ratio of the proposed schemes under various connection/disconnection rates and holding times.     

A Minimum Delay Routing Algorithm Using Distributed Computation

An algorithm is defined for establishing routing tables in the individual nodes of a data network. The routing table at a nodeispecifies, for each other nodej, what fraction of the traffic destined for nodejshould leave nodeion each of the links emanating from nodei. The algorithm is applied independently at each node and successively updates the routing table at that node based on information communicated between adjacent nodes about the marginal delay to each destination. For stationary input traffic statistics, the average delay per message through the network converges, with successive updates of the routing tables, to the minimum average delay over all routing assignments. The algorithm has the additional property that the traffic to each destination is guaranteed to be loop free at each iteration of the algorithm. In addition, a new global convergence theorem for noncontinuous iteration algorithms is developed.     

基于优先队列的最小生成树算法

本文提出一个获取连通网络是小生成树的算法。该算法采用一个优先队列组织各顶点集合，每次根据边的权值对队列头集合进行增长。由于对每个顶点的相关联边进行了按权值分级排序的预处理，算法获取具有。个预示e条边的无向连通网络的最小生成树的期望时间是O（e*loglogn）。     

图像边缘权重优化的最小生成树分割提取

针对无监督图像分割方法对噪声敏感而导致图像建模困难、分割结果准确率低等问题,该文提出一种图像边缘权重优化的最小生成树分割提取方法。首先,利用L₀梯度最小值平滑处理噪声再结合Otsu优化Canny边缘检测,得到更加准确的边缘信息;其次,重新设计权重函数,采用更加合理的色差空间构建加权图,通过改进分割准则优化物体合并与区分过程;最后,选择不同类型图片进行抗噪性、分割效果实验。实验结果表明：相对于其他算法,该文算法的抗噪性能优秀,分割精度平均提升5.15%,过分割率平均下降32.07%,欠分割率平均下降2.69%。将其运用在实际航空遥感图像的河道湖泊提取中,所得结果相比其他主流算法结构更加完整,无关信息更少,抗噪性能更好。     

An Exact Algorithm with Tight Lower Bounds for the Capacitated Minimum Spanning Tree Problem

A solution method using branch and bound technique for the CMST problem is introduced in this paper. Techniques for finding tighter lower bounds are emphasized. On the basis of a constraint relaxed MST bound, a penalty cost is added to acquire tighter bound. The correctness of the proposed bound is proved and the improvement of the efficiency coursed by the bound is demonstrated by the computational tests. A further tighter bound is also proposed considering the size of disjoint groups when establishing the penalties. Test results on benchmark problem instances are presented.     

LT Codes and the Minimum Spanning Tree Based Distributed Storage in Wireless Sensor Networks

Mobile Networks and Applications - In wireless sensor networks, sensor nodes are vulnerable due to the challenging environment and limited energy. Once a sensor node fails, the stored sensed data...     

用马尔科夫模型优化分布式最小连通支配集算法

 为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.     

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.     

基于极大权的最小连通支配集启发式算法

Ad hoc无线网络中基于最小连通支配集(MCDS)的路由是一个引人瞩目的方法,文中提出了一种基于极大权的MCDS的启发式算法,确保了性能强的主机担任网关节点的角色,能更好的协调管理网络中其他的节点,从而保持MCDS的相对稳固性并为全网中的广播和路由操作提供一个高效的通信基础.仿真结果表明,该算法能在保证生成权和极大的连通支配集的同时也确保它的极小性,因此能有效地用于基于MCDS的路由设计中.     

A Failsafe Distributed Protocol for Minimum Delay Routing

Previous distributed routing protocols in data-communication networks that achieve minimum average delay are extended to take into consideration topological changes in the network.     

最小生成树算法在城市基础建设中的应用

随着城市基础建设规模的逐步扩大,所需建设资金也大幅提高,只有对各类系统进一步优化才能提高其运行的经济效益和利用率,降低其成本。本文采用最小生成树算法对城市基础建设布局进行设计,重点以暖气供应为例进行阐述。     

基于生成树集结算子的群组AHP判断矩阵集结算法

针对现有群组AHP(Analytic Hierarchy Process)判断矩阵集结算法,偏重于专家权重的选择,而忽略判断矩阵元素之间联系的不足,提出一种基于生成树集结算子的群组AHP判断矩阵集结算法.该算法依据判断矩阵与简单无向图生成树之间的关系,采用生成树集结算子获取完全一致集结矩阵,并利用完全一致集结矩阵和群组关联集结矩阵,综合考虑判断矩阵元素之间的个体一致性和群组关联性,计算获得满足一致性约束和最优相似性的群组集结结果.通过算例分析,说明该算法的可行性与有效性.     

基于高维空间最小生成树自适应覆盖模型的可拒绝分类算法

在高维空间样本较少的情况下,基于统计模型的可拒绝分类方法难以对样本分布的复杂几何形体构建合理的覆盖模型。为此,该文提出基于高维空间最小生成树自适应覆盖模型的可拒绝分类模型。该模型采用最小生成树刻画高维空间样本点分布,将图形的边作为新增虚拟样本以提供更好的同类样本分布描述。通过将同类相近样本划分到一个连通几何覆盖区域内,将不同类的相近样本归于不同几何覆盖区域内,实现对不同训练类的覆盖。为了克服因不合理虚拟样本造成分类器拒识性能的下降,引入自适应调整覆盖半径策略,实现对训练类的紧致性覆盖。对于测试样本,根据训练类覆盖边界便可对其作出拒识或者接受的处理,针对交叉覆盖的接受样本,再根据数据场策略确定其真正归属类别。实验结果表明本文方法合理有效。     

基于生成树的无线传感器网络分布式路由协议

在无线传感器网络中,节点具有有限的电池能量,为了延长网络的生存时间,提出了一种基于生成树的分布式路由协议STRP及其具有能量意识的改进版本STRP-PA.每个传感器节点根据相邻节点与基站的距离、剩余能量等信息寻找父节点,构造一棵以基站为根的近优最小生成树,节点采集的数据沿树传输,并在树杈节点进行聚合.仿真实验结果表明:STRP-PA协议能够节省网络能量,显著延长网络稳定工作的时间,性能明显好于LEACH协议.     

Directed Graph Techniques for the Analysis of Fault Trees

Since the introduction of the fault tree method for system safety and reliability analysis more than a decade ago, the method has gained considerable acceptance for qualitative analyses. It has also gained a degree of acceptance for quantitative analyses, despite difficulties encountered in performing the probabilistic evaluations using available methods. Some of the difficulties encountered with previous evaluation methods are avoided by the methods of this paper. The new methods involve the use of directed graphs (digraphs) and related matrix methods, and solutions for paths in a manner similar to that for conventional digraphs. Most of the attractiveness stems from the fundamental philosophy of speedily transforming the graphics into corresponding matrices. This puts the bulk of the solution effort into the mathematics where it belongs. The major benefit arises because the mathematical solutions are readily performed by standard matrix techniques, which can be implemented either manually or with the aid of a computer. The new methods have been used on various hypothetical logic combinations plus actual fault trees of typical sizes.     

一种改进的分布式最大权独立集算法

能快速准确寻找给定图中的最大权独立集的分布式算法,对于解决无线网络中的资源调配、无线骨干网构建等问题具有非常重要的指导意义。该文以基于最大乘信用传播的分布式算法为框架,假设所有节点了解自己邻居节点之间的局部拓扑信息,启发式地提出一种新的相邻节点间交换消息的计算方法以及相应的分布式最大权独立集算法。仿真结果表明,所提算法摆脱了文献中已有算法对图结构必须是树或者二分图的要求,且权和性能优于已有的分布式算法。     

一种求解最小割的警示传播算法

最小割问题（minimum cut problem）是NP（Non-deterministic Polynomial）难问题,警示传播算法（warning propagation）是一种基于因子图的消息传递算法,可用于求解组合优化问题.首先,本文借助隐马尔可夫模型将无向图转换为因子图,将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后,选取了几组随机无向图实例进行数值实验,实验结果表明,该算法在求解速度上优于同类算法.     

一种基于移动Agent的分布式通信算法

本文提出了一种基于移动Agent链接寻址分布式通信算法,通过分析通信位移延迟问题,对消息传递的寻址、消息排队的过程设置,实现了移动Agent的高速通信.