基于链表的LDPC码循环检测算法

提出基于链表的低密度校验(LDPC)码循环检测算法,通过将LDPC码校验矩阵中的非零元素逐层展开,得到具有层次结构的链表.比较链表中每一层的节点和上层的节点,可以得到矩阵中的全部循环.记录检测到的循环,能够得到矩阵中各种长度循环的准确数目,进而得到矩阵的周长(最短循环长度).给出了算法的详细流程,并分析了实现复杂度.仿真结果表明,该算法可以有效的检测出矩阵中各种长度循环的准确数目,对LDPC码校验矩阵的设计和性能估计具有重要的指导意义.     

WDM网络中一种新型的波长转换器配置算法

在波分复用(WDM)光网络中,文章将经过各节点的最短路径的总长度作为权值对节点进行排序,利用优先配置最短路径总长度较长的节点的思想,对已有的"子图+ 代数决策图(ADD)"算法进行改进,得到了一种新的"子图+路径长度排序 (PLS)"算法.对两种算法进行了计算机仿真,结果显示新算法在保证结果准确的同时,较有效地降低了运算的时间复杂度.     

基于Grover搜索的多约束路由算法

寻找满足多约束条件的QoS路由是网络业务能否顺利实施的关键,在研究和分析了当前多种典型相关算法的基础上,提出了一种基于Grover量子搜索思想的多约束路由算法。算法对路径采用了非线性路径长度的度量方法,分析了Grover搜索的特点和优势,根据Grover迭代的实现过程构建了操作矩阵和概率扩散矩阵,通过选择高概率的节点进行数据转发。仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

一种公交最佳路径选择方法

通过分析最短路径算法及城市公交网络的特点提出了城市公交网络换乘的实现方法.首先,针对城市公交网络构造公交网络模型.其次,根据城市公交网络特点引入公交网络的直达矩阵,并依据该直达矩阵将城市公交网络抽象表示成一个"公交网络邻接图".再次,利用最短路径算法结合城市公交抽象网络图计算,得出最少换乘次数和可能的换乘站点.最后,利用所建立公交网络模型及所得换乘次数和可能的换乘站点进行计算,得到了综合考虑最小换乘和最短路径的最佳路径.并用一算例检验了该算法的有效性.     

有向双环网络G(N;h)的容错路由算法

针对有向双环网络G(N;h)的容错问题,研究了有向双环网络G(N;h)容错节点所对应的等价节点的分布规律,给出一种有向双环网络G(N;h)的容错路由算法. 给出了当有向双环网络任意两个节点之间的最短路径出现故障时,找出另一条最短路径的方法. 此算法的时间复杂度为O(d).     

基于入侵行为的光网络最短路径通信方案

恶意数据入侵光网络后,导致光网络最短路径通信花销高,因此,提出将入侵行为作为基础的光网络最短路径通信方案.光网络被恶意数据入侵行为攻击后,动态分布选取光网络的中继节点,选取过程中依据节点之间的欧式距离和节点损坏程度,确定中继节点的最佳位置.在此基础上,使用动态最短路径算法,通过详细的计算步骤实现最短路径通信.经过仿真分...     

一种有效的两端线网布线方法

提出了一种基于计算几何学的面向两端线网的布线算法.对于给定的布线平面,该算法首先根据障碍情况构造了包含最短路径信息的强连接图,然后引入绕障碍长度作为参数,以决定搜索走向,算法保证能找到最短布线路径,并使其时空复杂度得到了极大的改善.     

矩阵迭代和Dijkstra两种算法在交通运输路径选择中的对比

本文基于矩阵迭代算法及Dijkstra算法,对两者在最短路径问题中的差异性进行了对比。结果表明:Dijkstra算法可一次求得一点到其他各点的最小阻抗,该算法在进行最短路径的计算时,需要对相邻点进行反复搜寻,计算效率较低,收敛速度较慢。矩阵迭代算法没有严格路径次序限制迭代顺序,可实现算法并行计算,计算速度较高。在阻抗矩阵为对称矩阵时,在经过迭代后,得到的矩阵仍为对称矩阵,这样可使每次迭代的计算量得到减少。通过在重庆市路网上随机选取8个终点及起点,对起始点1点到8点的最短路径及阻抗进行计算表明,Dijkstra算法所用时间为0.673s,迭代矩阵算法所用时间为0.501s,矩阵迭代算法的计算速度更快。在矩阵4×4、6×6、8×8中,矩阵迭代算法的运算时间均比Dijkstra算法的运算时间要小,其迭代次数次数也远远小于Dijkstra算法的迭代次数,这进一步表明,矩阵迭代算法的计算效率要比Dijkstra算法的计算效率高。     

基于可视化试验的Exp-Geo算法

全局最短路径是组合优化的经典问题之一。求解最小Steiner树的可视化试验成功的在给定节点中间生成了Steiner点,但当给定节点数目增多且呈不规则分布时,试验方法形成薄膜路径困难并且不稳定。针对试验的不足,文中构建了Exp-Geo算法。在给定点数目增多时,采用该算法能够在给定节点之间生成Steiner点,得到全局最短路径,弥补试验的不足。经过多次试验、计算、对比分析,证明该算法能在多点系统中找到系统全局最短路径,为可视化试验的推广奠定了基础。     

基于最短路径树的节点删除动态路由算法

提出一种基于最短路径树的节点删除动态路由算法。算法建立一个最短路径树更新集合,该集合包括被删除节点的断裂子树所有节点和其它节点连接的边,利用子树的结构信息,对子树节点的直系子孙节点和祖先节点进行更新,采用Dijkstra算法对其它子树节点进行更新。实验结果表明,该算法能有效减少节点更新计算次数。     

The stable paths problem and interdomain routing

Dynamic routing protocols such as RIP and OSPF essentially implement distributed algorithms for solving the shortest paths problem. The border gateway protocol (BGP) is currently the only interdomain routing protocol deployed in the Internet. BGP does not solve a shortest paths problem since any interdomain protocol is required to allow policy-based metrics to override distance-based metrics and enable autonomous systems to independently define their routing policies with little or no global coordination. It is then natural to ask if BGP can be viewed as a distributed algorithm for solving some fundamental problem. We introduce the stable paths problem and show that BGP can be viewed as a distributed algorithm for solving this problem. Unlike a shortest path tree, such a solution does not represent a global optimum, but rather an equilibrium point in which each node is assigned its local optimum. We study the stable paths problem using a derived structure called a dispute wheel, representing conflicting routing policies at various nodes. We show that if no dispute wheel can be constructed, then there exists a unique solution for the stable paths problem. We define the simple path vector protocol (SPVP), a distributed algorithm for solving the stable paths problem. SPVP is intended to capture the dynamic behavior of BGP at an abstract level. If SPVP converges, then the resulting state corresponds to a stable paths solution. If there is no solution, then SPVP always diverges. In fact, SPVP can even diverge when a solution exists. We show that SPVP will converge to the unique solution of an instance of the stable paths problem if no dispute wheel exists     

A fault tolerant routing scheme for hypercubes

An efficient distributed fault‐tolerant routing algorithm for the hypercube is proposed based on the existence of a complete set of node‐disjoint paths between any two nodes. Node failure and repairs may occur dynamically provided that the total number of faulty nodes at any time is less than the node‐connectivity n of the n‐cube. Each node maintains for each possible destination which of the associated node‐disjoint paths to use. When a message is blocked by a node failure, the source node is warned and requested to switch to a different node‐disjoint path. The methods used to identify the paths, to propagate node failure information to source nodes, and to switch from one routing path to another incur little communication and computation overhead. We show that if the faults occur reasonably apart in time, then all messages will be routed on optimal or near optimal paths. In the unlikely case where many faults occur in a short period, the algorithm still delivers all messages but via possibly longer paths. An extension of the obtained algorithm to handle link failures in addition to node failures is discussed. We also show how to adapt the algorithm to n‐ary n‐cube networks. The algorithm can be similarly adapted to any interconnection network for which there exists a simple characterization of node‐disjoint paths between its nodes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Oscillations in Complex Communication Networks under Attack

In this paper we study the traffic dynamics of a scale-free complex network under an intentional attack at the node with the largest betweenness (i.e., the hub). This node is removed from the network after the attack. Consequently, the traffic load which used to go through the hub has to find other paths. A weight is defined for each node to indicate how long a packet has to wait at this node. A shortest time delay routing strategy is then applied based on the weight. We find that with different values of the capacity redundancy parameter, the traffic dynamics are quite different. When the capacity has large redundancy, then all the nodes work in a free-flow state even after the attack. If the capacity redundancy is not that large, then congestion may occur at some nodes. Due to the shortest time delay routing strategy, this congestion occurs periodically. If the capacity is very small, then the traffic dynamics become complicated, and oscillations and chaotic phenomena take place.     

An efficient pursuit automata approach for estimating stable all‐pairs shortest paths in stochastic network environments

This paper presents a new solution to the dynamic all‐pairs shortest‐path routing problem using a fast‐converging pursuit automata learning approach. The particular instance of the problem that we have investigated concerns finding the all‐pairs shortest paths in a stochastic graph, where there are continuous probabilistically based updates in edge‐weights. We present the details of the algorithm with an illustrative example. The algorithm can be used to find the all‐pairs shortest paths for the ‘statistical’ average graph, and the solution converges irrespective of whether there are new changes in edge‐weights or not. On the other hand, the existing popular algorithms will fail to exhibit such a behavior and would recalculate the affected all‐pairs shortest paths after each edge‐weight update. There are two important contributions of the proposed algorithm. The first contribution is that not all the edges in a stochastic graph are probed and, even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the final list involving all pairs of nodes in the graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. The second contribution is designing a data structure, the elements of which represent the probability that a particular edge in the graph lies in the shortest path between a pair of nodes in the graph. All the algorithms were tested in environments where edge‐weights change stochastically, and where the graph topologies undergo multiple simultaneous edge‐weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. Copyright © 2008 John Wiley & Sons, Ltd.     

基于社交网络结构的节点影响力度量方法

度量社交网络节点影响力是社交网络结构分析的关键问题之一。目前研究社交网络节点影响力的方法主要有两大类：中心度方法和节点删除方法。前者主要通过度或最短路径等因素来判断节点的影响力，不考虑网络的连通性；后者通过节点删除后对网络结构的破坏程度来判断，计算复杂性很高，不适用于较大规模的社交网络。通过结合社交网络的局部连通度及节点间的最短路径，提出了连通中心度来度量社交网络中节点的影响力，并给出了连通中心度的计算方法和一些特殊网络中节点的连通中心度的值。最后，通过实验说明该指标能很好地度量社交网络中节点的影响力。     

BlueMesh: Degree-Constrained Multi-Hop Scatternet Formation for Bluetooth Networks

In this paper we describe BlueMesh, a new protocol for the establishment of scatternets, i.e., multi-hop wireless networks of Bluetooth devices. BlueMesh defines rules for device discovery, piconet formation and piconet interconnection so to generate connected scatternets with the following desirable properties. BlueMesh forms scatternets without requiring the Bluetooth devices to be all in each other transmission range. BlueMesh scatternet topologies are meshes with multiple paths between any pair of nodes. BlueMesh piconets are made up of no more than 7 slaves. Simulation results in networks with over 200 nodes show that BlueMesh is effective in quickly generating a connected scatternet in which each node, on average, does not assume more than 2.4 roles. Moreover, the route length between any two nodes in the network is comparable to that of the shortest paths between the nodes.     

基于网络编码的双路径组播树生成算法

 为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能.     

Distributed algorithms for computing shortest pairs of disjointpaths

Distributed algorithms for finding two disjoint paths of minimum total length from each node to a destination are presented. The algorithms have both node-disjoint and link-disjoint versions and provide each node with information sufficient to forward data on the disjoint paths. It is shown that this problem can be reduced to the problem of finding a minimal shortest path from each node to the destination in a modified network, and a distributed algorithm on the original network that simulates a shortest-paths algorithm running on the modified network is presented. The algorithm has a smaller space complexity than any previous distributed algorithm for the same problem, and a method for forwarding packets is presented that does not require any additional space complexity. A synchronous implementation of the algorithm is also presented and studied     

Power and cost aware localized routing with guaranteed delivery in unit graph based ad hoc networks

In a localized routing algorithm, each node currently holding a message makes forwarding decision solely based on the position information about itself, its neighbors and destination. In a unit graph, two nodes can communicate if and only if the distance between them is no more than the transmission radius, which is the same for each node. This paper proposes localized routing algorithms, aimed at minimizing total power for routing a message or maximizing the total number of routing tasks that a network can perform before a partition. The algorithms are combinations of known greedy power and/or cost aware localized routing algorithms and an algorithm that guarantees delivery. A shortcut procedure is introduced in later algorithm to enhance its performance. Another improvement is to restrict the routing to nodes in a dominating set. These improvements require two‐hop knowledge at each node. The efficiency of proposed algorithms is verified experimentally by comparing their power savings, and the number of routing tasks a network can perform before a node loses all its energy, with the corresponding shortest weighted path algorithms and localized algorithms that use fixed transmission power at each node. Significant energy savings are obtained, and feasibility of applying power and cost‐aware localized schemes is demonstrated. Copyright © 2004 John Wiley & Sons, Ltd.     

Detection of Wormhole Attack and Secure Path Selection in Wireless Sensor Network

In Wireless Sensor Network (WSN), securable data transmission is one of the most challenges. During the transmission between the source and a destination node, routing information of the particular path may be misbehaved by the particular nodes which are known as wormhole nodes/attackers. The paths which include the wormhole nodes are known as wormhole attacked paths. For improving security in WSN, these wormhole attacked paths should be identified. To achieve this, wormhole attack detection method and optimal or secure path selection are presented in this paper. Initially, ‘K’ paths or multiple paths are generated between source and destination using Ad-hoc On demand Multipath Distance Vector (AOMDV) routing protocol. Then, the source node identifies the wormhole attacked path by verifying the Detection Packet (DP) and Feedback Packet (FP) from the destination. After detecting the wormhole attacked paths, the source node selects the optimal path among the attacker free paths using Particle Swarm Optimization (PSO) algorithm. Simulation results show that the performance of the proposed approach improves energy efficiency and network lifetime of the network.