Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks

We propose the minimum Wiener index spanning tree (MWST) as a routing topology that is suitable for sensor networks with multiple mobile base nodes. However, it was proved that finding a spanning tree with the minimum Wiener index from a weighted graph is NP-hard. To address this problem and analyze the effectiveness of the MWST as the routing tree on sensor networks with multiple mobile base nodes, we designed two algorithms: a branch and bound algorithm for small-scale wireless sensor networks and a simulated annealing algorithm for large-scale wireless sensor networks. The simulation results show that MWST outperforms the minimum spanning tree (MST), one of the representative spanning trees used in many routing protocols for sensor networks, in terms of energy efficiency and packet delay.     

Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the cost constrained minimum label spanning tree (CCMLST) problem is to find a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. The label constrained minimum spanning tree (LCMST) problem is closely related to the CCMLST problem. Here, we are given a threshold K on the number of labels. The goal is to find a minimum weight spanning tree that uses at most K distinct labels. Both of these problems are motivated from the design of telecommunication networks and are known to be NP-complete [15].In this paper, we present a variable neighborhood search (VNS) algorithm for the CCMLST problem. The VNS algorithm uses neighborhoods defined on the labels. We also adapt the VNS algorithm to the LCMST problem. We then test the VNS algorithm on existing data sets as well as a large-scale dataset based on TSPLIB [12] instances ranging in size from 500 to 1000 nodes. For the LCMST problem, we compare the VNS procedure to a genetic algorithm (GA) and two local search procedures suggested in [15]. For the CCMLST problem, the procedures suggested in [15] can be applied by means of a binary search procedure. Consequently, we compared our VNS algorithm to the GA and two local search procedures suggested in [15]. The overall results demonstrate that the proposed VNS algorithm is of high quality and computes solutions rapidly. On our test datasets, it obtains the optimal solution in all instances for which the optimal solution is known. Further, it significantly outperforms the GA and two local search procedures described in [15].     

An artificial bee colony algorithm for the minimum routing cost spanning tree problem

Given a connected, weighted, and undirected graph, the minimum routing cost spanning tree problem seeks a spanning tree of minimum routing cost on this graph, where routing cost of a spanning tree is defined as the sum of the costs of the paths connecting all possible pairs of distinct vertices in that spanning tree. This problem has several important applications in networks design and computational biology. In this paper, we have proposed an artificial bee colony (ABC) algorithm-based approach for this problem. We have compared our approach against four best methods reported in the literature—two genetic algorithms, a stochastic hill climber and a perturbation-based local search. Computational results show the superiority of our ABC approach over other approaches.     

Improved Heuristics for the Minimum Label Spanning Tree Problem

Given a connected, undirected graph G whose edges are labeled, the minimum label (or labeling) spanning tree (MLST) problem seeks a spanning tree on G with the minimum number of distinct labels. Maximum vertex covering algorithm (MVCA) is a well-known heuristic for the MLST problem. It is very fast and performs reasonably well. Recently, we developed a genetic algorithm (GA) for the MLST problem. The GA and MVCA are similarly fast but the GA outperforms the MVCA. In this paper, we present four modified versions of MVCA, as well as a modified GA. These modified procedures generate better results, but are more expensive computationally. The modified GA is the best performer with respect to both accuracy and running time     

Deadlock-Free Multicasting in Irregular Networks Using Prefix Routing

A deadlock-free multicast scheme called prefix multicasting in irregular networks (i.e., networks with irregular topology) is studied. In prefix routing, a compact routing table is associated with each node (processor). Basically, each outgoing channel of a node is assigned a special label and an outgoing channel is selected if its label is a prefix of the label of the destination node. Node and channel labelling in an irregular network is based on a pre-defined spanning tree which may or may not be minimum. The routing process follows a two-phase process of going up and then down along the spanning tree, with a possible cross channel between two branches of the tree between two phases. It is shown that the proposed routing scheme is deadlock- and livelock-free. The approach is extended to multicasting in which the multicast packet is first forwarded up the tree to the longest common prefix (LCP) of destinations in the multicast. The packet is then treated as a multi-head worm that can split at branches of the spanning tree as the packet is sent down the tree.     

基于剪枝的最小生成树算法在供水管网的应用

在进行供水管网网络设计时,如何使铺设的供水管网线路最短,构建的供水管网造价最低是设计者需要重点考虑的问题之一。文章就此问题提出了一种基于剪枝的最小生成树算法。算法首先将交叉点(街道的交汇处)和节点(用户)都视为图的顶点,然后求出最小生成树,最后再将最小生成树中以交叉点为末梢的枝叶剪掉。该算法简洁、快速、易于实现。对铺设公路,架设网线等一类网络问题也有实际的参考意义。     

Multicriteria path and tree problems: discussion on exact algorithms and applications

Multicriteria/multiobjective path and tree models are useful in many applications. Particularly, in Internet routing problems they seem to lead to promising approaches. In the first part of this paper, we classify and present the main exact approaches dealing with several multicriteria path problems putting in evidence the shortest path problem. In the second part, we review exact algorithms dedicated to some multicriteria tree problems, namely the minimum spanning tree and the minimum cost/minimum label spanning tree problems. Finally, the application of these models is exemplified.     

Carousel greedy: A generalized greedy algorithm with applications in optimization

In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum independent set problem, and the minimum weight vertex cover problem. In all cases, the results are very promising. Since carousel greedy is very fast, it can be used to solve very large problems. In addition, it can be combined with other approaches to create a powerful, new metaheuristic. Our goal in this paper is to motivate and explain the new approach and present extensive computational results.     

限制树宽的图的最小标记生成数算法

本文研究了图的最小标记生成树问题。首先介绍在一般图上基于搜索树的最小标记生成树的算法;然后考虑了限制树宽的图,得到了效率更高的算法。该算法在树宽为常数的情况下,时间复杂度关于图的顶点个数为多项式,从而也证明了最小标记生成树在限制树宽的图上属于确定参数可解问题。     

关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究，尤其是在最近的网络QoS路由研究中的基本问题，在以往的文献中，有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径。该文给出了一个简单的证明，指出了最大生成树与最大带宽路径之间的特殊关系，证明了可以使用修改的Kruskal算法来构建最大带宽路径，文中给出了修改的Kruskal算法，并且与已有的Kijkstra算法作了性能上的比较，尽管从理论上说，Dijstra算法和Kruskal算法的时间复杂度具有同样的阶，但在多种不同网络结构上的模拟测试结果表明，用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍，而且在实际上比Dijkstra算法更简单，灵活。     

移动自组网中一种网络生存时间最优的广播算法

移动自组网中广播操作的网络生存时间问题一直是备受关注的热点研究问题.现有的研究已经证明,基于最小生成树算法的广播算法能够最优地解决网络生存时间问题.但是,这些研究工作都是基于静止的网络拓扑,从而不适用于一些实际的网络拓扑动态变化的应用场景,如军事通信应用等.因此,针对节点移动导致的网络拓扑变化的场景,本文提出了一种移动...     

On the red/blue spanning tree problem

A geometric spanning tree of a point set S is a tree whose vertex set is S and whose edge set is a set of non-crossing straight line segments with endpoints in S. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is a minimum. If no three points are collinear, we show that the minimum number of crossing points is completely determined by the number of maximal red (or blue) chains on the convex hull of all red points and blue points. We design an optimal algorithm for constructing a geometric spanning tree of all the red points and a geometric spanning tree of all the blue points with the minimum number of crossing points. If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.     

A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs

During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic applications and such an assumption is wrong, finding the minimum spanning tree of a stochastic graph has not received the attention it merits. This is due to the fact that the minimum spanning tree problem becomes incredibly hard to solve when the edge weight is assumed to be a random variable. This becomes more difficult if we assume that the probability distribution function of the edge weight is unknown. In this paper, we propose a learning automata-based heuristic algorithm to solve the minimum spanning tree problem in stochastic graphs wherein the probability distribution function of the edge weight is unknown. The proposed algorithm taking advantage of learning automata determines the edges that must be sampled at each stage. As the presented algorithm proceeds, the sampling process is concentrated on the edges that constitute the spanning tree with the minimum expected weight. The proposed learning automata-based sampling method decreases the number of samples that need to be taken from the graph by reducing the rate of unnecessary samples. Experimental results show the superiority of the proposed algorithm over the well-known existing methods both in terms of the number of samples and the running time of algorithm.     

基于最小代价和生成树的算法研究

最小生成树问题是一类经典的组合优化问题,已有许多快速有效的算法。但是在实际中更多存在这样的网络,除边有权值外,结点也有权值,并且结点的权值有多种情况,这就产生了基于代价和最小的生成树问题。根据结点权值的取值情况,对几种最小代价和生成树问题进行分类和求解,得到了一些有价值的性质和算法,有一定的实际应用背景。     

求解度约束最小生成树问题的新算法

针对网络设计和组合优化中的度约束最小生成树问题,基于第k最小生成树的求解算法,提出了一种求解网络G关于指定节点的最小k度生成树的新算法。该算法通过对网络G的最小生成树作最优可行变换,逐步构造出指定节点的度数越来越接近度约束k的最小i度生成树,最终得到了网络G关于指定节点的最小k度生成树。给出了算法实施的具体步骤,并证明了算法的正确性。最后通过仿真结果和一个运输实例,表明了该算法在解决度约束最小生成树问题中的有效性。     

基于“最小差值法”的网络模型耗费代价研究

最小生成树算法是数据结构中,求网络模型耗费代价最优解的一个重要工具。现实生活中的连通网络模型复杂而多变,有时还需兼顾其它的目标,一棵最小生成树不足以解决问题,因此找出所有的最小生成树是很有必要的,在此提出一种新的寻找所有最小生成树的算法--最小差值法。无向连通图网络通过去掉连枝生成最小生成树,一个连枝加入最小生成树形成一个圈。这种算法是在一个圈中,用连枝的权与其它树枝的权分别作差,求最小差值。由最小差值是否为零,判断原有的最小生成树能否通过换进换出边,生成新的最小生成树。该算法能够有规律、高效率的寻找出所有的最小生成树。在找出的所有最小生成树方案中,选择符合实时情况的最小生成树方案,该方案即为网络耗费代价的最优解。     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。     

Balanced spanning trees in complete and incomplete star graphs

Efficiently solving the personalized broadcast problem in an interconnection network typically relies on finding an appropriate spanning tree in the network. In this paper, we show how to construct in a complete star graph an asymptotically balanced spanning tree, and in an incomplete star graph a near-balanced spanning tree. In both cases, the tree is shown to have the minimum height. In the literature, this problem has only been considered for the complete star graph, and the constructed tree is about 4/3 times taller than the one proposed in this paper     

Minimization of Energy Losses in Electric Power Distribution Systems by Intelligent Search Strategies

Energy is continuously dissipated in electric power systems due to electrical resistance in transmission and distribution lines. This paper addresses the problem of obtaining a network topology with minimum energy losses for electric power distribution systems. As distribution networks must operate radially, the problem can be formulated as a generalization of the minimum spanning tree problem. The generalization is due to variation in costs as network configuration changes. Nonlinear network flow techniques are teamed with search strategies borrowed from the field of artificial intelligence to overcome computation intractability.