Ant Colony Optimization Algorithms for Shortest Path Problems

We propose four variants of recently proposed multi-timescale algorithm in [1] for ant colony optimization and study their application on a multi-stage shortest path problem. We study the performance of the various algorithms in this framework. We observe, that one of the variants consistently outperforms the algorithm [1].

A shortest path tree based algorithm for relay placement in a wireless sensor network and its performance analysis

In this paper, we study a problem of designing a multi-hop wireless network for interconnecting sensors (hereafter called source nodes) to a Base Station (BS), by deploying a minimum number of relay nodes at a subset of given potential locations, while meeting a quality of service (QoS) objective specified as a hop count bound for paths from the sources to the BS. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard. For this problem, we propose a polynomial time approximation algorithm based on iteratively constructing shortest path trees and heuristically pruning away the relay nodes used until the hop count bound is violated. Results show that the algorithm performs efficiently in various randomly generated network scenarios; in over 90% of the tested scenarios, it gave solutions that were either optimal or were worse than optimal by just one relay. We then use random graph techniques to obtain, under a certain stochastic setting, an upper bound on the average case approximation ratio of a class of algorithms (including the proposed algorithm) for this problem as a function of the number of source nodes, and the hop count bound. To the best of our knowledge, the average case analysis is the first of its kind in the relay placement literature. Since the design is based on a light traffic model, we also provide simulation results (using models for the IEEE 802.15.4 physical layer and medium access control) to assess the traffic levels up to which the QoS objectives continue to be met. (C) 2014 Elsevier B.V. All rights reserved.

Neural network based optimal routing algorithm for communication networks

This paper presents the capability of the neural networks as a computational tool for solving constrained optimization problem, arising in routing algorithms for the present day communication networks. The application of neural networks in the optimum routing problem, in case of packet switched computer networks, where the goal is to minimize the average delays in the communication have been addressed. The effectiveness of neural network is shown by the results of simulation of a neural design to solve the shortest path problem. Simulation model of neural network is shown to be utilized in an optimum routing algorithm known as flow deviation algorithm. It is also shown that the model will enable the routing algorithm to be implemented in real time and also to be adaptive to changes in link costs and network topology. (C) 2002 Elsevier Science Ltd. All rights reserved.

An approximate algorithm for the minimal vertex nested polygon problem

Given two simple polygons, the Minimal Vertex Nested Polygon Problem is one of finding a polygon nested between the given polygons having the minimum number of vertices. In this paper, we suggest efficient approximate algorithms for interesting special cases of the above using the shortest-path finding graph algorithms.

Rectilinear Path Following in 3D Space

This paper addresses the problem of determining an optimal (shortest) path in three dimensional space for a constant speed and turn-rate constrained aerial vehicle, that would enable the vehicle to converge to a rectilinear path, starting from any arbitrary initial position and orientation. Based on 3D geometry, we propose an optimal and also a suboptimal path planning approach. Unlike the existing numerical methods which are computationally intensive, this optimal geometrical method generates an optimal solution in lesser time. The suboptimal solution approach is comparatively more efficient and gives a solution that is very close to the optimal one. Due to its simplicity and low computational requirements this approach can be implemented on an aerial vehicle with constrained turn radius to reach a straight line with a prescribed orientation as required in several applications. But, if the distance between the initial point and the straight line to be followed along the vertical axis is high, then the generated path may not be flyable for an aerial vehicle with limited range of flight path angle and we resort to a numerical method for obtaining the optimal solution. The numerical method used here for simulation is based on multiple shooting and is found to be comparatively more efficient than other methods for solving such two point boundary value problem.

Optimal trajectory planning for path convergence in three-dimensional space

This article addresses the problem of determining the shortest path that connects a given initial configuration (position, heading angle, and flight path angle) to a given rectilinear or a circular path in three-dimensional space for a constant speed and turn-rate constrained aerial vehicle. The final path is assumed to be located relatively far from the starting point. Due to its simplicity and low computational requirements the algorithm can be implemented on a fixed-wing type unmanned air vehicle in real time in missions where the final path may change dynamically. As wind has a very significant effect on the flight of small aerial vehicles, the method of optimal path planning is extended to meet the same objective in the presence of wind comparable to the speed of the aerial vehicles. But, if the path to be followed is closer to the initial point, an off-line method based on multiple shooting, in combination with a direct transcription technique, is used to obtain the optimal solution. Optimal paths are generated for a variety of cases to show the efficiency of the algorithm. Simulations are presented to demonstrate tracking results using a 6-degrees-of-freedom model of an unmanned air vehicle.

Optimal Trajectory Generation for Convergence to a Rectilinear Path

This paper presents a strategy to determine the shortest path of a fixed-wing Miniature Air Vehicle (MAV), constrained by a bounded turning rate, to eventually fly along a given straight line, starting from an arbitrary but known initial position and orientation. Unlike the work available in the literature that solves the problem using the Pontryagin's Minimum Principle (PMP) the trajectory generation algorithm presented here considers a geometrical approach which is intuitive and easy to understand. This also computes the explicit solution for the length of the optimal path as a function of the initial configuration. Further, using a 6-DOF model of a MAV the generated optimal path is tracked by an autopilot consisting of proportional-integral-derivative (PID) controllers. The simulation results show the path generation and tracking for different cases.

Energy-Efficient Decentralized Cooperative Routing in Wireless Networks

Wireless adhoc networks transmit information from a source to a destination via multiple hops in order to save energy and, thus, increase the lifetime of battery-operated nodes. The energy savings can be especially significant in cooperative transmission schemes, where several nodes cooperate during one hop to forward the information to the next node along a route to the destination. Finding the best multi-hop transmission policy in such a network which determines nodes that are involved in each hop, is a very important problem, but also a very difficult one especially when the physical wireless channel behavior is to be accounted for and exploited. We model the above optimization problem for randomly fading channels as a decentralized control problem - the channel observations available at each node define the information structure, while the control policy is defined by the power and phase of the signal transmitted by each node. In particular, we consider the problem of computing an energy-optimal cooperative transmission scheme in a wireless network for two different channel fading models: (i) slow fading channels, where the channel gains of the links remain the same for a large number of transmissions, and (ii) fast fading channels, where the channel gains of the links change quickly from one transmission to another. For slow fading, we consider a factored class of policies (corresponding to local cooperation between nodes), and show that the computation of an optimal policy in this class is equivalent to a shortest path computation on an induced graph, whose edge costs can be computed in a decentralized manner using only locally available channel state information (CSI). For fast fading, both CSI acquisition and data transmission consume energy. Hence, we need to jointly optimize over both these; we cast this optimization problem as a large stochastic optimization problem. We then jointly optimize over a set of CSI functions of the local channel states, and a c- - orresponding factored class of control poli.

Energy-Efficient Decentralized Routing with Localized Cooperation Suitable for Fast Fading

Wireless networks transmit information from a source to a destination via multiple hops in order to save energy and, thus, increase the lifetime of battery-operated nodes. The energy savings can be especially significant in cooperative transmission schemes, where several nodes cooperate during one hop to forward the information to the next node along a route to the destination. Finding the best multi-hop transmission policy in such a network which determines nodes that are involved in each hop, is a very important problem, but also a very difficult one especially when the physical wireless channel behavior is to be accounted for and exploited. We model the above optimization problem for randomly fading channels as a decentralized control problem – the channel observations available at each node define the information structure, while the control policy is defined by the power and phase of the signal transmitted by each node.In particular, we consider the problem of computing an energy-optimal cooperative transmission scheme in a wireless network for two different channel fading models: (i) slow fading channels, where the channel gains of the links remain the same for a large number of transmissions, and (ii) fast fading channels,where the channel gains of the links change quickly from one transmission to another. For slow fading, we consider a factored class of policies (corresponding to local cooperation between nodes), and show that the computation of an optimal policy in this class is equivalent to a shortest path computation on an induced graph, whose edge costs can be computed in a decentralized manner using only locally available channel state information(CSI). For fast fading, both CSI acquisition and data transmission consume energy. Hence, we need to jointly optimize over both these; we cast this optimization problem as a large stochastic optimization problem. We then jointly optimize over a set of CSI functions of the local channel states, and a corresponding factored class of control policies corresponding to local cooperation between nodes with a local outage constraint. The resulting optimal scheme in this class can again be computed efficiently in a decentralized manner. We demonstrate significant energy savings for both slow and fast fading channels through numerical simulations of randomly distributed networks.

Allostery in tRNA Synthetases Elucidated from MD Simulations and Protein Structure Networks

tRNA synthetases (aaRS) are enzymes crucial in the translation of genetic code. The enzyme accylates the acceptor stem of tRNA by the congnate amino acid bound at the active site, when the anti-codon is recognized by the anti-codon site of aaRS. In a typical aaRS, the distance between the anti-codon region and the amino accylation site is approximately 70 Å. We have investigated this allosteric phenomenon at molecular level by MD simulations followed by the analysis of protein structure networks (PSN) of non-covalent interactions. Specifically, we have generated conformational ensembles by performing MD simulations on different liganded states of methionyl tRNA synthetase (MetRS) from Escherichia coli and tryptophenyl tRNA synthetase (TrpRS) from Human. The correlated residues during the MD simulations are identified by cross correlation maps. We have identified the amino acids connecting the correlated residues by the shortest path between the two selected members of the PSN. The frequencies of paths have been evaluated from the MD snapshots[1]. The conformational populations in different liganded states of the protein have been beautifully captured in terms of network parameters such as hubs, cliques and communities[2]. These parameters have been associated with the rigidity and plasticity of the protein conformations and can be associated with free energy landscape. A comparison of allosteric communication in MetRS and TrpRS [3] elucidated in this study highlights diverse means adopted by different enzymes to perform a similar function. The computational method described for these two enzymes can be applied to the investigation of allostery in other systems.

Acoustic emission source location and damage detection in a metallic structure using a graph-theory-based geodesic pproach

A geodesic-based approach using Lamb waves is proposed to locate the acoustic emission (AE) source and damage in an isotropic metallic structure. In the case of the AE (passive) technique, the elastic waves take the shortest path from the source to the sensor array distributed in the structure. The geodesics are computed on the meshed surface of the structure using graph theory based on Dijkstra's algorithm. By propagating the waves in reverse virtually from these sensors along the geodesic path and by locating the first intersection point of these waves, one can get the AE source location. The same approach is extended for detection of damage in a structure. The wave response matrix of the given sensor configuration for the healthy and the damaged structure is obtained experimentally. The healthy and damage response matrix is compared and their difference gives the information about the reflection of waves from the damage. These waves are backpropagated from the sensors and the above method is used to locate the damage by finding the point where intersection of geodesics occurs. In this work, the geodesic approach is shown to be suitable to obtain a practicable source location solution in a more general set-up on any arbitrary surface containing finite discontinuities. Experiments were conducted on aluminum specimens of simple and complex geometry to validate this new method.

Quality-of-Transmission-Aware Manycasting Over Optical Burst-Switched Networks

Many next-generation distributed applications, such as grid computing, require a single source to communicate with a group of destinations. Traditionally, such applications are implemented using multicast communication. A typical multicast session requires creating the shortest-path tree to a fixed number of destinations. The fundamental issue in multicasting data to a fixed set of destinations is receiver blocking. If one of the destinations is not reachable, the entire multicast request (say, grid task request) may fail. Manycasting is a generalized variation of multicasting that provides the freedom to choose the best subset of destinations from a larger set of candidate destinations. We propose an impairment-aware algorithm to provide manycasting service in the optical layer, specifically OBS. We compare the performance of our proposed manycasting algorithm with traditional multicasting and multicast with over provisioning. Our results show a significant improvement in the blocking probability by implementing optical-layer manycasting.

Modelling and analysis of new coolstreaming for P2P IPTV

Peer to peer networks are being used extensively nowadays for file sharing, video on demand and live streaming. For IPTV, delay deadlines are more stringent compared to file sharing. Coolstreaming was the first P2P IPTV system. In this paper, we model New Coolstreaming (newer version of Coolstreaming) via a queueing network. We use two time scale decomposition of Markov chains to compute the stationary distribution of number of peers and the expected number of substreams in the overlay which are not being received at the required rate due to parent overloading. We also characterize the end-to-end delay encountered by a video packet received by a user and originated at the server. Three factors contribute towards the delay. The first factor is the mean shortest path length between any two overlay peers in terms of overlay hops of the partnership graph which is shown to be O (log n) where n is the number of peers in the overlay. The second factor is the mean number of routers between any two overlay neighbours which is seen to be at most O (log N-I) where N-I is the number of routers in the internet. Third factor is the mean delay at a router in the internet. We provide an approximation of this mean delay E W]. Thus, the mean end to end delay in New Coolstreaming is shown to be upper bounded by O (log E N]) (log N-I) E (W)] where E N] is the mean number of peers at a channel.

An approximation to the QoS aware throughput region of a tree network under IEEE 802.15.4 CSMA/CA with application to wireless sensor network design

In the context of wireless sensor networks, we are motivated by the design of a tree network spanning a set of source nodes that generate packets, a set of additional relay nodes that only forward packets from the sources, and a data sink. We assume that the paths from the sources to the sink have bounded hop count, that the nodes use the IEEE 802.15.4 CSMA/CA for medium access control, and that there are no hidden terminals. In this setting, starting with a set of simple fixed point equations, we derive explicit conditions on the packet generation rates at the sources, so that the tree network approximately provides certain quality of service (QoS) such as end-to-end delivery probability and mean delay. The structures of our conditions provide insight on the dependence of the network performance on the arrival rate vector, and the topological properties of the tree network. Our numerical experiments suggest that our approximations are able to capture a significant part of the QoS aware throughput region (of a tree network), that is adequate for many sensor network applications. Furthermore, for the special case of equal arrival rates, default backoff parameters, and for a range of values of target QoS, we show that among all path-length-bounded trees (spanning a given set of sources and the data sink) that meet the conditions derived in the paper, a shortest path tree achieves the maximum throughput. (C) 2015 Elsevier B.V. All rights reserved.

The estimation of the thermodynamic properties of ternary alloys from binary data using the shortest distance composition path

A new composition path, Xi-Xj=constant, is suggested for the semi-empirical calculation of the thermodynamic properties of ternary ‘substitutional’ solutions from binary data, when the binary systems show deviations from the regular solution model. A comparison is made between the results obtained for integral and partial properties using this composition path and those calculated employing other composition paths suggested in literature. It appears that the best estimate of the ternary properties is obtained when binary data at compositions closest to the ternary composition are used.