Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks

Several localized position based routing algorithms for wireless networks were described recently. In greedy routing algorithm (that has close performance to the shortest path algorithm, if successful), sender or node S currently holding the message m forwards m to one of its neighbors that is the closest to destination. The algorithm fails if S does not have any neighbor that is closer to destination than S. FACE algorithm guarantees the delivery of m if the network, modeled by unit graph, is connected. GFG algorithm combines greedy and FACE algorithms. Greedy algorithm is applied as long as possible, until delivery or a failure. In case of failure, the algorithm switches to FACE algorithm until a node closer to destination than last failure node is found, at which point greedy algorithm is applied again. Past traffic does not need to be memorized at nodes. In this paper we further improve the performance of GFG algorithm, by reducing its average hop count. First we improve the FACE algorithm by adding a sooner-back procedure for earlier escape from FACE mode. Then we perform a shortcut procedure at each forwarding node S. Node S uses the local information available to calculate as many hops as possible and forwards the packet to the last known hop directly instead of forwarding it to the next hop. The second improvement is based on the concept of dominating sets. Each node in the network is classified as internal or not, based on geographic position of its neighboring nodes. The network of internal nodes defines a connected dominating set, i.e., and each node must be either internal or directly connected to an internal node. In addition, internal nodes are connected. We apply several existing definitions of internal nodes, namely the concepts of intermediate, inter-gateway and gateway nodes. We propose to run GFG routing, enhanced by shortcut procedure, on the dominating set, except possibly the first and last hops. The performance of proposed algorithms is measured by comparing its average hop count with hop count of the basic GFG algorithm and the benchmark shortest path algorithm, and very significant improvements were obtained for low degree graphs. More precisely, we obtained localized routing algorithm that guarantees delivery and has very low excess in terms of hop count compared to the shortest path algorithm. The experimental data show that the length of additional path (in excess of shortest path length) can be reduced to about half of that of existing GFG algorithm.     

Multi-Hop Routing Optimization Method Based on Improved Ant Algorithm for Vehicle to Roadside Network

This paper proposes a route optimization method to improve the performance of route selection in Vehicle Ad-hoc Network （VANET）. A novel bionic swarm intelligence algorithm, which is called ant colony algorithm, was introduced into a traditional ad-hoc route algorithm named AODV. Based on the analysis of movement characteristics of vehicles and according to the spatial relationship between the vehicles and the roadside units, the parameters in ant colony system were modified to enhance the performance of the route selection probability rules. When the vehicle moves into the range of several different roadsides, it could build the route by sending some route testing packets as ants, so that the route table can be built by the reply information of test ants, and then the node can establish the optimization path to send the application packets. The simulation results indicate that the proposed algorithm has better performance than the traditional AODV algorithm, especially when the vehicle is in higher speed or the number of nodes increases.     

Self Organized Terminode Routing

We consider the problem of routing in a wide area mobile ad hoc network called Terminode Network. Routing in this network is designed with the following objectives. First, it should scale well in terms of the number of nodes and geographical coverage; second, routing should have scalable mechanisms that cope with the dynamicity in the network due to mobility; and third, nodes need to be highly collaborative and redundant, but, most of all, cannot use complex algorithms or protocols. Our routing scheme is a combination of two protocols called Terminode Local Routing (TLR) and Terminode Remote Routing (TRR). TLR is used to route packets to close destinations. TRR is used to route to remote destinations. The combination of TLR and TRR has the following features: (1) it is highly scalable because every node relies only on itself and a small number of other nodes for packet forwarding; (2) it acts and reacts well to the dynamicity of the network because as a rule multipath routing is considered; and (3) it can be implemented and run in very simple devices because the algorithms and protocols are very simple and based on high collaboration. We performed simulations of the TLR and TRR protocols using the GloMoSim simulator. The simulation results for a large, highly mobile ad hoc environment demonstrate benefits of the combination of TLR and TRR over an existing protocol that uses geographical information for packet forwarding.     

An Efficient Next Hop Selection Algorithm for Multi-Hop Body Area Networks

Body Area Networks (BANs) consist of various sensors which gather patient’s vital signs and deliver them to doctors. One of the most significant challenges faced, is the design of an energy-efficient next hop selection algorithm to satisfy Quality of Service (QoS) requirements for different healthcare applications. In this paper, a novel efficient next hop selection algorithm is proposed in multi-hop BANs. This algorithm uses the minimum hop count and a link cost function jointly in each node to choose the best next hop node. The link cost function includes the residual energy, free buffer size, and the link reliability of the neighboring nodes, which is used to balance the energy consumption and to satisfy QoS requirements in terms of end to end delay and reliability. Extensive simulation experiments were performed to evaluate the efficiency of the proposed algorithm using the NS-2 simulator. Simulation results show that our proposed algorithm provides significant improvement in terms of energy consumption, number of packets forwarded, end to end delay and packet delivery ratio compared to the existing routing protocol.     

A platform for biological sequence comparison on parallel computers

We have written two programs for searching biological sequencedatabases that run on Intel hypercube computers. PSCANLJB comparesa single sequence against a sequence library, and PCOMPLIB comparesall the entries in one sequence library against a second library.The programs provide a general framework for similarity searching;they include functions for reading in query sequences, searchparameters and library entries, and reporting the results ofa search. We have isolated the code for the specific functionthat calculates the similarity score between the query and librarysequence; alternative searching algorithms can be implementedby editing two files. We have implemented the rapid FASTA sequencecomparison algorithm and the more rigorous Smith — Watermanalgorithm within this framework. The PSCANLIB program on a 16node iPSC/2 80386-based hypercube can compare a 229 amino acidprotein sequence with a 3.4 million residue sequence libraryin {small tilde}16s with the FASTA algorithm. Using the Smith— Waterman algorithm, the same search takes 35 min. ThePCOMPUB program can compare a 0.8 millon amino acid proteinsequence library with itself in 5.3 min with FASTA on a third-generation32 node Intel iPSC/860 hypercube. Received on September 8, 1990; accepted on December 15, 1990     

HybridFlood: minimizing the effects of redundant messages and maximizing search efficiency of unstructured peer-to-peer networks

Peer-to-peer systems are important Internet applications. A major portion of Internet traffic belongs to such applications. Flooding search is a basic search scheme for unstructured peer-to-peer networks, where a node must send a query message to all its neighbors when seeking a file (in a file sharing situation). Flooding has no knowledge about network topology and files distribution, thus it offers an attractive method for file discovery in dynamic and evolving networks. Although pure flooding can achieve high coverage but it produces exponentially redundant messages in each hop. Consequently, the growth of redundant messages limits system scalability and causes unnecessary traffic in networks. Besides, flooding has no opportunity to get an advantage of node diversity of participating in unstructured P2P networks. To improve this searching scheme and reduce redundant messages, this paper proposes a novel algorithm named HybridFlood. This algorithm is divided into two steps. The first step follows the flooding with a limited number of hops. In the second step, nosey nodes are selected in each searching horizon. The nosey nodes are nodes which have the most links to other nodes. These nodes maintain the data index of all client nodes. We provided analytical studies for flooding and HybridFlood. The analytical results provided the best threshold point of hop for optimum coverage growth rate and redundant messages in flooding. It also proved in HybridFlood broadcasting messages are cut down at least an order of magnitude. Thus, the proposed algorithm extends the search efficiency by reducing redundant messages in each hop. The simulation experiments validated analytical results.     

A general mathematical performance model for wormhole-switched irregular networks

Irregular topologies are desirable network structures for building scalable cluster systems and very recently they have also been employed in SoC (system-on-chip) design. Many analytical models have been proposed in the literature to evaluate the performance of networks with different topologies such as hypercube, torus, mesh, hypermesh, Cartesian product networks, star graph, and k-ary n-cube; however, to the best of our knowledge, no mathematical model has been presented for irregular networks. Therefore, as an effort to fill this gap, this paper presents a comprehensive mathematical model for fully adaptive routing in wormhole-switched irregular networks. Moreover, since our approach holds no assumption for the network topology, the proposed analytical model covers all the aforementioned models (i.e. it covers both regular and irregular topologies). Furthermore, the model makes no preliminary assumption about the deadlock-free routing algorithm applied to the network. Finally, besides the generality of the model regarding the topology and routing algorithm, our analysis shows that the analytical model exhibits high accuracy which enables it to be used for almost all topologies with all traffic loads.     

A mobile agent model for fault-tolerant manipulation on distributed objects

In this paper, we discuss how to realize fault-tolerant applications on distributed objects. Servers supporting objects can be fault-tolerant by taking advantage of replication and checkpointing technologies. However, there is no discussion on how application programs being performed on clients are tolerant of clients faults. For example, servers might block in the two-phase commitment protocol due to the client fault. We newly discuss how to make application programs fault-tolerant by taking advantage of mobile agent technologies where a program can move from a computer to another computer in networks. An application program to be performed on a faulty computer can be performed on another operational computer by moving the program in the mobile agent model. In this paper, we discuss a transactional agent model where a reliable and efficient application for manipulating objects in multiple computers is realized in the mobile agent model. In the transactional agent model, only a small part of the application program named routing subagent moves around computers. A routing subagent autonomously finds a computer which to visit next. We discuss a hierarchical navigation map which computer should be visited price to another computer in a transactional agent. A routing subagent makes a decision on which computer visit for the hierarchical navigation map. Programs manipulating objects in a computer are loaded to the computer on arrival of the routing subagent in order to reduce the communication overhead. This part of the transactional agent is a manipulating subagent. The manipulation subagent still exists on the computer even after the routing subagent leaves the computer in order to hold objects until the commitment. We assume every computer may stop by fault while networks are reliable. There are kinds of faulty computers for a transactional agent; current, destination, and sibling computers where a transactional agent now exists, will move, and has visited, respectively. The types of faults are detected by neighbouring manipulation subagents by communicating with each other. If some of the manipulation subagents are faulty, the routing subagent has to be aborted. However, the routing subagent is still moving. We discuss how to efficiently deliver the abort message to the moving routing subagent. We evaluate the transactional agent model in terms of how long it takes to abort the routing subagent if some computer is faulty.

Vervet monkeys use paths consistent with context‐specific spatial movement heuristics

Animal foraging routes are analogous to the computationally demanding “traveling salesman problem” (TSP), where individuals must find the shortest path among several locations before returning to the start. Humans approximate solutions to TSPs using simple heuristics or “rules of thumb,” but our knowledge of how other animals solve multidestination routing problems is incomplete. Most nonhuman primate species have shown limited ability to route plan. However, captive vervets were shown to solve a TSP for six sites. These results were consistent with either planning three steps ahead or a risk‐avoidance strategy. I investigated how wild vervet monkeys (Chlorocebus pygerythrus) solved a path problem with six, equally rewarding food sites; where site arrangement allowed assessment of whether vervets found the shortest route and/or used paths consistent with one of three simple heuristics to navigate. Single vervets took the shortest possible path in fewer than half of the trials, usually in ways consistent with the most efficient heuristic (the convex hull). When in competition, vervets' paths were consistent with different, more efficient heuristics dependent on their dominance rank (a cluster strategy for dominants and the nearest neighbor rule for subordinates). These results suggest that, like humans, vervets may solve multidestination routing problems by applying simple, adaptive, context‐specific “rules of thumb.” The heuristics that were consistent with vervet paths in this study are the same as some of those asserted to be used by humans. These spatial movement strategies may have common evolutionary roots and be part of a universal mental navigational toolkit. Alternatively, they may have emerged through convergent evolution as the optimal way to solve multidestination routing problems.     

A self-healing clustering algorithm for underwater sensor networks

Underwater wireless sensor networks (UWSNs) is a novel networking paradigm to explore aqueous environments. The characteristics of mobile UWSNs, such as low communication bandwidth, large propagation delay, floating node mobility, and high error probability, are significantly different from terrestrial wireless sensor networks. Energy-efficient communication protocols are thus urgently demanded in mobile UWSNs. In this paper, we develop a novel clustering algorithm that combines the ideas of energy-efficient cluster-based routing and application-specific data aggregation to achieve good performance in terms of system lifetime, and application-perceived quality. The proposed clustering technique organizes sensor nodes into direction-sensitive clusters, with one node acting as the head of each cluster, in order to fit the unique characteristic of up/down transmission direction in UWSNs. Meanwhile, the concept of self-healing is adopted to avoid excessively frequent re-clustering owing to the disruption of individual clusters. The self-healing mechanism significantly enhances the robustness of clustered UWSNs. The experimental results verify the effectiveness and feasibility of the proposed algorithm.     

无线传感器网络中基于缠绕多路径的ReInforM路由

对缠绕多路径算法技术的基本构建方法和ReInforM路由算法技术的基本过程进行了讨论,分析了其在无线传感器网络应用中的发展方向,提出了基于缠绕多路径的ReInforM路由。     

Bayes Node Energy Polynomial Distribution to Improve Routing in Wireless Sensor Network

Wireless Sensor Network monitor and control the physical world via large number of small, low-priced sensor nodes. Existing method on Wireless Sensor Network (WSN) presented sensed data communication through continuous data collection resulting in higher delay and energy consumption. To conquer the routing issue and reduce energy drain rate, Bayes Node Energy and Polynomial Distribution (BNEPD) technique is introduced with energy aware routing in the wireless sensor network. The Bayes Node Energy Distribution initially distributes the sensor nodes that detect an object of similar event (i.e., temperature, pressure, flow) into specific regions with the application of Bayes rule. The object detection of similar events is accomplished based on the bayes probabilities and is sent to the sink node resulting in minimizing the energy consumption. Next, the Polynomial Regression Function is applied to the target object of similar events considered for different sensors are combined. They are based on the minimum and maximum value of object events and are transferred to the sink node. Finally, the Poly Distribute algorithm effectively distributes the sensor nodes. The energy efficient routing path for each sensor nodes are created by data aggregation at the sink based on polynomial regression function which reduces the energy drain rate with minimum communication overhead. Experimental performance is evaluated using Dodgers Loop Sensor Data Set from UCI repository. Simulation results show that the proposed distribution algorithm significantly reduce the node energy drain rate and ensure fairness among different users reducing the communication overhead.     

拽线法:一个构建系统发育树的新算法

这篇文章要讨论的拽线法（DL）是贪婪算法的一种。和Fitch—Margoliash（FM）一样,DL也是基于距离矩阵构建系统发育树,但是和FM算法相比,DL具有低复杂度、较高的容错性和准确度高的优点。当存在误差时,DL算法只是加大了不在同一个父节点下的基因序列的距离,但能够准确的判断序列的亲缘关系,进而得到完美的进化树拓扑结构;相比之下,FM算法让各个基因序列间的距离均摊了这种误差,从而有可能将本应该具有相同父节点的基因序列分到不同的分支。     

Route Optimization for Mobile IP

Route Optimization has been designed within the IETF to ameliorate the problem of triangle routing, a routing artifact introduced by Mobile IP's requirement to route packets destined for a mobile node by way of its home network. In this article, we describe the current protocol specification for the Route Optimization protocol, concentrating on design decisions and justifications. Once the basic mechanisms are explained, we show how they are applied to enable foreign agents to offer smooth handoffs for mobile nodes, and describe the security operations that enable reliable operation of this handoff between foreign agents with which a mobile node has no pre-existing security relationship. This revised version was published online in August 2006 with corrections to the Cover Date.     

Identification of SPAM messages using an approach inspired on the immune system

In this paper, an immune-inspired model, named innate and adaptive artificial immune system (IA-AIS) is proposed and applied to the problem of identification of unsolicited bulk e-mail messages (SPAM). It integrates entities analogous to macrophages, B and T lymphocytes, modeling both the innate and the adaptive immune systems. An implementation of the algorithm was capable of identifying more than 99% of legitimate or SPAM messages in particular parameter configurations. It was compared to an optimized version of the naïve Bayes classifier, which has been attained extremely high correct classification rates. It has been concluded that IA-AIS has a greater ability to identify SPAM messages, although the identification of legitimate messages is not as high as that of the implemented naïve Bayes classifier.     

On an improved clustering algorithm based on node density for WSN routing protocol

To better collect data in context to balance energy consumption, wireless sensor networks (WSN) need to be divided into clusters. The division of clusters makes the network become a hierarchical organizational structure, which plays the role of balancing the network load and prolonging the life cycle of the system. In clustering routing algorithm, the pros and cons of clustering algorithm directly affect the result of cluster division. In this paper, an algorithm for selecting cluster heads based on node distribution density and allocating remaining nodes is proposed for the defects of cluster head random election and uneven clustering in the traditional LEACH protocol clustering algorithm in WSN. Experiments show that the algorithm can realize the rapid selection of cluster heads and division of clusters, which is effective for node clustering and is conducive to equalizing energy consumption.

     

WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks

In this paper, we propose an on-demand distributed clustering algorithm for multi-hop packet radio networks. These types of networks, also known as ad hoc networks, are dynamic in nature due to the mobility of nodes. The association and dissociation of nodes to and from clusters perturb the stability of the network topology, and hence a reconfiguration of the system is often unavoidable. However, it is vital to keep the topology stable as long as possible. The clusterheads, form a dominant set in the network, determine the topology and its stability. The proposed weight-based distributed clustering algorithm takes into consideration the ideal degree, transmission power, mobility, and battery power of mobile nodes. The time required to identify the clusterheads depends on the diameter of the underlying graph. We try to keep the number of nodes in a cluster around a pre-defined threshold to facilitate the optimal operation of the medium access control (MAC) protocol. The non-periodic procedure for clusterhead election is invoked on-demand, and is aimed to reduce the computation and communication costs. The clusterheads, operating in dual power mode, connects the clusters which help in routing messages from a node to any other node. We observe a trade-off between the uniformity of the load handled by the clusterheads and the connectivity of the network. Simulation experiments are conducted to evaluate the performance of our algorithm in terms of the number of clusterheads, reaffiliation frequency, and dominant set updates. Results show that our algorithm performs better than existing ones and is also tunable to different kinds of network conditions.     

Efficient shared memory and RDMA based collectives on multi-rail QsNetII SMP clusters

Clusters of Symmetric Multiprocessors (SMP) are more commonplace than ever in achieving high-performance. Scientific applications running on clusters employ collective communications extensively. Shared memory communication and Remote Direct Memory Access (RDMA) over multi-rail networks are promising approaches in addressing the increasing demand on intra-node and inter-node communications, and thereby in boosting the performance of collectives in emerging multi-core SMP clusters. In this regard, this paper designs and evaluates two classes of collective communication algorithms directly at the Elan user-level over multi-rail Quadrics QsNet^II with message striping: 1) RDMA-based traditional multi-port algorithms for gather, all-gather, and all-to-all collectives for medium to large messages, and 2) RDMA-based and SMP-aware multi-port all-gather algorithms for small to medium size messages. The multi-port RDMA-based Direct algorithm for gather and all-to-all collectives gain an improvement of up to 2.15 for 4 KB messages over elan_gather(), and up to 2.26 for 2 KB messages over elan_alltoall(), respectively. For the all-gather, our SMP-aware Bruck algorithm outperforms all other all-gather algorithms including elan_gather() for 512 B to 8 KB messages, with a 1.96 improvement factor for 4 KB messages. Our multi-port Direct all-gather is the best algorithm for 16 KB to 1 MB, and outperforms elan_gather() by a factor of 1.49 for 32 KB messages. Experimentation with real applications has shown up to 1.47 communication speedup can be achieved using the proposed all-gather algorithms.

Message operators: A new expression of the information

Starting from the synaptic model proposed in a previous paper (Teodorescu, 1976b), based on the idea that, in certain condition, information may be expressed in terms of the constraints in an optimization problem, the concept of an active message is defined. This is a message conveying a certain purpose, which is able to transform an initial orderly state in a new one, subject to some constraints, by choosing the optimal way. Some examples are given to show that active messages play an important role, not only in organisms, but also in communications between individuals and/or groups in social populations. The concept of a message operator, as a mathematical expression of the active message is, then, defined. It is shown that such an operator is, in fact, a pair, having as components a certain transformation and the associate optimization problem involving some information in constraints-form. The transformation is a relationship between the joint moment hypercube, expressing the initial multivariate random process (initial orderly state), and the final orderly state expressed by the joint density hypercube. By solving the optimization problem, the optimized density hypercube (i.e. the new orderly state) is obtained. An example is given to illustrate the procedure. It follows that message operators are able to express, in mathematical form, the transition from a given orderly state (say, a biological population in a quasi-chaotic state) into a new orderly state, with a different degree of orderliness. In such a transition involving three stages i.e. initial orderly state-message-final orderly state, the information is expressed, respectively, in terms of: probabilities-constraints-probabilities. Thus, Shanon's measure of information applies only in the states, since message operators have nothing to do with probabilities. To investigate the particular manner where information is involved in the constraints of the optimization problem, some main properties of the message operators are emphasized and illustrated by an example. Thus, it is shown that message operators are powerfull tools, permitting to investigate some unknown aspects of the information. This leads to a deeper understanding of the communication problems in biological systems as well as to various applications in biology.     

STACRP: a secure trusted auction oriented clustering based routing protocol for MANET

In mobile ad hoc network?(MANET) nodes have a tendency to drop others’ packet to conserve its own energy. If most of the nodes in a network start to behave in this way, either a portion of the network would be isolated or total network functionality would be hampered. This behavior is known as selfishness. Therefore, selfishness mitigation and enforcing cooperation between nodes is very important to increase the availability of nodes and overall throughput and to achieve the robustness of the network. Both credit and reputation based mechanisms are used to attract nodes to forward others’ packets. In light of this, we propose a game theoretic routing model, Secure Trusted Auction oriented Clustering based Routing Protocol (STACRP), to provide trusted framework for MANET. Two auction mechanisms procurement and Dutch are used to determine the forwarding cost-per-hop for intermediate nodes. Our model is lightweight in terms of computational and communication requirements, yet powerful in terms of flexibility in managing trust between nodes of heterogeneous deployments. It manages trust locally with minimal overhead in terms of extra messages. STACRP organizes the network into 1-hop disjoint clusters and elects the most qualified and trustworthy nodes as Clusterhead. The trust is quantified with carefully chosen parameters having deep impact on network functionality. The trust model is analyzed using Markov chain and is proven as continuous time Markov chain. The security analysis of the model is analyzed to guarantee that the proposed approach achieves a secure reliable routing solution for MANETs. The proposed model have been evaluated with a set of simulations that show STACRP detects selfish nodes and enforces cooperation between nodes and achieves better throughput and packet delivery ratio with lees routing overhead compare to AODV.