An efficient minimizing algorithm for sum of disjoint products

This paper presents an efficient algorithm for calculating system reliability by sum of disjoint products (sdp). Abraham and his successors yield relatively short system reliability formula. This new algorithm follows the philosophy of Abraham, but uses new rules to arrange the initial ordering of minipaths in outer loop and the ordering of terms in inner loop, and adopts multiple-variable inversion. The algorithm generates a shorter system reliability formula than any known sdp algorithm.     

An all hops optimal algorithm for dynamic routing of sliding scheduled traffic demands

We consider dynamic routing of holding-time aware demands under a sliding scheduled traffic model to satisfy demands' bandwidth and timing requirements. We propose an all hops optimal routing algorithm that iteratively finds all feasible paths of at most h hops at the end of h-th iteration. We prove the correctness and analyze the time complexity of the algorithm.     

基于最小化平均分组跳的波长路由环网逻辑拓扑设计

本文提出了用混合整数线性规则（ＭＩＬＰ）进行波长路由环网的逻辑拓扑设计。对于给定的通信流量矩阵,其目标函数是最小经平均分组跳。以双向环网为例,对于不同网络结构参数的情况,进行了计算分析并给出了数值结果。对双向环网和单向环网的网络性能进行了比较分析。     

An energy efficient clustering routing algorithm for wireless sensor networks

~~An energy efficient clustering routing algorithm for wireless sensor networks1. Mainwaring A, Polastre J, Szewczyk R, et al. Wireless sensor networks for habitat monitoring. Proceedings of the ACM International Workshop on Wireless Sensor Networks and A…     

An efficient QoS routing algorithm for solving MCP in ad hoc networks

Providing guaranteed quality of service (QoS) in wireless networks is a key issue for deploying multimedia applications. To support such a QoS, an arduous problem concerning how to find a feasible end to end path to satisfy multiple QoS constraints should be studied. In general, multi-constrained path selection, with or without optimization, is an NP-complete problem that cannot be exactly solved in polynomial time. Approximation algorithms and heuristics with polynomial and pseudo-polynomial time complexities are often used to deal with this problem. However, existing solutions suffer either from excessive computational complexities that cannot be used for multimedia applications in ad hoc networks characterized by mobility and performance constraints (e.g., limited energy, wireless medium, etc.). Recently a promising heuristic algorithm H_MCOP using a non linear Lagrange relaxation path functions has demonstrated an improvement in its success rate and in finding feasible paths. However, the H_MCOP is not suitable for ad hoc networks and has not exploited the full capability that a Lagrange relaxation could offer. In this paper, we propose an efficient multi-constrained path heuristic called E_MCP, which exploits efficiently the Lagrange relaxation and enhances the path search process to be adequate to mobile ad hoc networks. Using extensive simulations on random mobile network with correlated and uncorrelated link weights, we show that the same level of computational complexity, E_MCP can achieve a higher success ratio of finding feasible paths.     

An energy efficient channel assignment and routing algorithm for multi-radio wireless mesh networks

Endowing mesh routers with multiple radios is a recent solution to improve the performance of wireless mesh networks. Solving the problem how to assign channels to radios has attracted a lot of attention in the recent years, partly because of the hardness of solving the channel assignment problem jointly with the routing problem. However, the approaches proposed in the literature so far have mainly focused on reducing interference or maximizing the throughput. Little attention has been paid to the energy consumption of wireless mesh networks, given that mesh nodes are usually connected to a power source. However, with the rising concerns about the energy consumed by communication infrastructures, it makes sense to consider the minimization of the energy consumption as an objective of the channel assignment and routing problem. Our work stems from the observation that an idle radio simply overhearing a frame consumes nearly the same power as the radio actually receiving the frame. Hence, energy may be saved by turning off a number of radios, if the performance of the network is not impaired. In this paper, we define the energy efficient channel assignment and routing problem, show that it is NP-hard and propose a heuristic algorithm. For the purpose of comparing the solution found by the proposed algorithm to the optimal solution, we also present two Mixed Integer Linear Programs (MILPs) that optimally solve the problem we address. Finally, we show the results of extensive simulation studies we conducted to assess the effectiveness of the proposed algorithm.     

An efficient routing protocol for wireless networks

We present the Wireless Routing Protocol (WRP). In WRP, routing nodes communicate the distance and secondto-last hop for each destination. WRP reduces the number of cases in which a temporary routing loop can occur, which accounts for its fast convergence properties. A detailed proof of correctness is presented and its performance is compared by simulation with the performance of the distributed Bellman-Ford Algorithm (DBF), DUAL (a loop-free distance-vector algorithm) and an Ideal Link-state Algorithm (ILS), which represent the state of the art of internet routing. The simulation results indicate that WRP is the most efficient of the alternatives analyzed.This work was supported in part by the Advanced Research Projects Agency (ARPA) under contract F19628-93-C-0175 and by the Office of Naval Research under Contract No. N-00014-92-J-1807.     

基于最优簇头数和三段路由的改进型LEACH算法

LEACH协议可延长无线传感器网络的使用寿命,提高信息传输量.但是研究发现基站距离网络区域愈远,LEACH协议的效果愈差,网络价值愈小.故本文提出了一种基于最优簇头数和三段路由的改进型LEACH算法,以克服基站位置对网络寿命和信息传输量的影响.该算法依据不同WSN的传感器节点数目,预先计算出理论上最优的簇头数目,残余能量最高的簇头将被选举为唯一的高层簇头,形成节点—簇头—高层簇头—基站的三段数据路由.实验结果表明,与LEACH协议相比,当传输距离小于距离阈值时,该算法有效提升了节点能耗的均衡性,推迟首节点死亡时间,从而提高信息传输量;当距离超过阈值后,网络寿命和信息传输量显著提高,算法优势更为明显.     

An efficient tag-based routing algorithm for the backward network of a bidirectional general shuffle-exchange network

This letter considers the problem of designing efficient routing algorithms for the backward network of a bidirectional general shuffle-exchange network (BNBGSEN for short); switch elements in the network are of size k/spl times/k. It has been shown in (Z. Chen, et al., 2003) that the algorithm in (K. Padmanabham, 1991) can be used to obtain (as many as k) backward control tags for a source j to get to a destination i in a BNBGSEN. In this letter, we show that a BNBGSEN has a wonderful property: for each destination i, there are two backward control tags associated with it such that every source j can get to i by using one of the two tags. We use this property to derive an efficient tag-based routing algorithm.     

最小化平均跳数的WDM网络逻辑拓扑优化算法

对波长路由光网络中的逻辑拓扑设计问题进行了探讨,并选择最小化平均分组跳数作为优化目标.理论分析表明:最小化平均分组跳数对于同时优化网络的拥塞率下限、拥塞概率、平均时延以及波长数下限具有一定的作用.以此为基础,结合最小跳数算法的局限性,提出一种改进的最小化平均分组跳数的启发式算法,并以NSFNET为仿真网络,比较了该算法与最短路径算法(分布式Bellman-Ford算法)、最小跳数算法(Minimum Hop)两种常用的基础算法在拓扑设计中的性能优劣.     

Deadlock free routing algorithm for minimizing congestion in a Hamiltonian connected recursive 3D-NoCs

Network on Chip (NoC) has been proposed as a solution for addressing the challenges in System on Chip (SoC) design. Designing a topology and its routing schemes are vital problems in a NoC. One of the major challenges that designers face today in 3D integration is how to route the data packets within a layer and across the layers in a scalable and efficient manner. In any 3D topology, minimizing the amount of data packet transmissions during the routing is still an open problem. Any efficient traditional routing schemes should avoid deadlocks and minimize network congestion from a source node to a destination node.     

Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithm

In IP-over-WDM networks, a logical IP network is routed on top of a physical optical fiber network. An important challenge here is to make the routing survivable. We call a routing survivable if the connectivity of the logical network is guaranteed in the case of a failure in the physical network. In this paper we describe FastSurv, a local search algorithm for survivable routing. The algorithm works in an iterative manner: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution. The algorithm can take link capacity constraints into account and can be extended to deal with multiple simultaneous link failures and node failures. In a large series of tests we compare FastSurv with current state-of-the-art algorithms for this problem. We show that it can provide better solutions in much shorter time, and that it is more scalable with respect to the number of nodes, both in terms of solution quality and run time.     

An optimal distributed routing algorithm

A distributed optimal one-level routing algorithm is presented. The algorithm is based on Newton's method. Using the variable reduction method, the Hessian matrix becomes diagonal. An example shows that the algorithm has a much faster convergence rate, more accurate results, and better transient behavior than previous work. The algorithm is shown to be convergent, stable, robust, and loop free     

Computing shortest paths for any number of hops

In this paper, we introduce and investigate a "new" path optimization problem that we denote the all hops optimal path (AHOP) problem. The problem involves identifying, for all hop counts, the optimal, i.e., minimum weight, path(s) between a given source and destination(s). The AHOP problem arises naturally in the context of quality-of-service (QoS) routing in networks, where routes (paths) need to be computed that provide services guarantees, e.g., delay or bandwidth, at the minimum possible "cost" (amount of resources required) to the network. Because service guarantees are typically provided through some form of resource allocation on the path (links) computed for a new request, the hop count, which captures the number of links over which resources are allocated, is a commonly used cost measure. As a result, a standard approach for determining the cheapest path available that meets a desired level of service guarantees is to compute a minimum hop shortest (optimal) path. Furthermore, for efficiency purposes, it is desirable to precompute such optimal minimum hop paths for all possible service requests. Providing this information gives rise to solving the AHOP problem. The paper's contributions are to investigate the computational complexity of solving the AHOP problem for two of the most prevalent cost functions (path weights) in networks, namely, additive and bottleneck weights. In particular, we establish that a solution based on the Bellman-Ford algorithm is optimal for additive weights, but show that this does not hold for bottleneck weights for which a lower complexity solution exists.     

A new Ad Hoc routing algorithm based on minimizing the channel handoff

How to improve the performance of the wireless Ad Hoc network by utilizing the spectrum resources efficiently has become a hot research topic in recent years. In this paper we propose a reactive routing algorithm that supports multiple channels to improve the performance of the Ad Hoc network based on the minimizing of the channel handoff. Our approach allocates the communication channel during the route discovery, and notifies the allocated channel information to the corresponding node in the route reply packets. Each node in the route tries its best to choose the same channel with the upstream node without interference. The simulation results show that our algorithm performs better than the K-hop distinct protocols in both average delays and network throughputs obviously     

Multi-objective fractional gravitational search algorithm for energy efficient routing in IoT

Wireless Networks - Nowadays, the Internet of Things (IoT) plays a significant role in the Internet world. The IoT is a system which integrates the computing devices, digital machines provided with...     

An efficient location and routing scheme for mobile computingenvironments

One of the most important issues affecting host mobility is the location and routing scheme that allows hosts to move seamlessly from one site to another. This paper presents a method that exploits the locality properties of a host's pattern of movement and access history. Two concepts, “local region” and “patron service” are introduced based on the locality features. For each mobile host, the local region is a set of designated subnetworks within which a mobile host often moves, and the patrons are the hosts from which the majority of traffic for the mobile host originated. These are used to confine the effects of a host moving, so location updates are sent only to its local area, and to those source hosts which are most likely to call again. Our scheme has the advantages of limiting location updates, and providing optimal routing, while increasing network and host scalability     

An efficient merging scheme for prescribed skew clock routing

In ultra-deep submicron very large-scale integration (VLSI) designs, clock network layout plays an increasingly important role on determining circuit quality indicated by timing, power consumption, cost, power-supply noise, and tolerance to process variations. In this brief, a new merging scheme is proposed for prescribed nonzero skew routings which are useful in reducing clock cycle time, suppressing power-supply noise, and improving tolerance to process variations. This technique is simple and easy to implement for practical applications. Experimental results on benchmark circuits with both buffered and unbuffered routings exhibit large improvement on wirelength and buffer cost compared with other existing works.     

混合光无线传感网络节能路由算法优化

为解决混合光无线传感网络节点因自身能量耗尽而过早消亡的问题.结合改进的蚁群算法,对一般混合光无线传感网络节能路由算法进行优化.首先给出节能路由算法的假定条件,设置算法具体应用场景,然后构建混合光无线传感器网络通信能耗模型,最后从引入路径度量,改进前向蚂蚁和返回蚂蚁的信息素更新规则着手,提高传统蚁群算法收敛速度,以减少能...