Modeling,analysis and simulation of ant-based network routing protocols

Using the metaphor of swarm intelligence, ant-based routing protocols deploy control packets that behave like ants to discover and optimize routes between pairs of nodes. These ant-based routing protocols provide an elegant, scalable solution to the routing problem for both wired and mobile ad hoc networks. The routing problem is highly nonlinear because the control packets alter the local routing tables as they are routed through the network. We mathematically map the local rules by which the routing tables are altered to the dynamics of the entire networks. Using dynamical systems theory, we map local protocol rules to full network performance, which helps us understand the impact of protocol parameters on network performance. In this paper, we systematically derive and analyze global models for simple ant-based routing protocols using both pheromone deposition and evaporation. In particular, we develop a stochastic model by modeling the probability density of ants over the network. The model is validated by comparing equilibrium pheromone levels produced by the global analysis to results obtained from simulation studies. We use both a Matlab simulation with ideal communications and a QualNet simulation with realistic communication models. Using these analytic and computational methods, we map out a complete phase diagram of network behavior over a small multipath network. We show the existence of both stable and unstable (inaccessible) routing solutions having varying properties of efficiency and redundancy depending upon the routing parameters. Finally, we apply these techniques to a larger 50-node network and show that the design principles acquired from studying the small model network extend to larger networks.     

AIB-OR: Improving Onion Routing Circuit Construction Using Anonymous Identity-Based Cryptosystems

The rapid growth of Internet applications has made communication anonymity an increasingly important or even indispensable security requirement. Onion routing has been employed as an infrastructure for anonymous communication over a public network, which provides anonymous connections that are strongly resistant to both eavesdropping and traffic analysis. However, existing onion routing protocols usually exhibit poor performance due to repeated encryption operations. In this paper, we first present an improved anonymous multi-receiver identity-based encryption (AMRIBE) scheme, and an improved identity-based one-way anonymous key agreement (IBOWAKE) protocol. We then propose an efficient onion routing protocol named AIB-OR that provides provable security and strong anonymity. Our main approach is to use our improved AMRIBE scheme and improved IBOWAKE protocol in onion routing circuit construction. Compared with other onion routing protocols, AIB-OR provides high efficiency, scalability, strong anonymity and fault tolerance. Performance measurements from a prototype implementation show that our proposed AIB-OR can achieve high bandwidths and low latencies when deployed over the Internet.     

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.     

Enabling richer statistical MANET simulations through cluster computing

The wide-scale adoption of modern smart phones and other multi-radio mobile devices, has begun to provide pragmatic deployment environments for non-cellular mobile ad hoc network (MANET) services (i.e., for disaster recovery scenarios, peered mobile games, social networking applications, etc.). User perceptions of the quality of such MANET services will be driven, in part, by standard network-level quality of service (QoS) metrics such as delay, jitter, throughput, etc. Much of the existing MANET literature has explored these issues, as well as MANET routing protocol design, through single computer Monte Carlo simulations (e.g., via ns-2, ns-3, OMNeT++, or OpNet). Results are then reported as the averages of these Monte Carlo runs. As is well known from probability and statistics, such averaging is only meaningful when applied across statistically ergodic data (i.e., data drawn from the same underlying distribution). But, assessing the validity of this underlying ergodic assumption requires transitioning to more rigorous cluster-based MANET simulation frameworks. This work highlights the theoretical rationale for such ergodicity testing, the developments of a cluster-based framework, the STARs framework, to support such testing, and the results and insights obtained by using this framework to evaluate the popular DYMO and OLSR MANET routing protocols. This work also discusses why the insights ergodic testing provides are of interest to potential real-world MANET deployments.     

DF++ : an adaptive buffer-aware probabilistic delegation forwarding protocol for Delay Tolerant Network

The delegated forwarding (DF) curb transmissions by forwarding the message to a node that holds high quality value seen by the message. However, DF assumes infinite buffer space that is not possible in real time applications. In addition, quality value computation considers the encountering history and does not account for additional network parameters such as aging and transitive connectivity. In this paper, we have proposed a routing protocol called as DF++ that compute quality value based on probabilistic model used in PRoPHET protocol and forwards the message to current node by adaptive computation of available buffer space. We have compared performance of DF++ with DF, Epidemic and PRoPHET routing protocols. The proposed DF++ has higher delivery probability and fewer message drop and transmissions.     

Traffic-aware routing protocol for wireless sensor networks

In wireless sensor networks, when a sensor node detects events in the surrounding environment, the sensing period for learning detailed information is likely to be short. However, the short sensing cycle increases the data traffic of the sensor nodes in a routing path. Since the high traffic load causes a data queue overflow in the sensor nodes, important information about urgent events could be lost. In addition, since the battery energy of the sensor nodes is quickly exhausted, the entire lifetime of wireless sensor networks would be shortened. In this paper, to address these problem issues, a new routing protocol is proposed based on a lightweight genetic algorithm. In the proposed method, the sensor nodes are aware of the data traffic rate to monitor the network congestion. In addition, the fitness function is designed from both the average and the standard deviation of the traffic rates of sensor nodes. Based on dominant gene sets in a genetic algorithm, the proposed method selects suitable data forwarding sensor nodes to avoid heavy traffic congestion. In experiments, the proposed method demonstrates efficient data transmission due to much less queue overflow and supports fair data transmission for all sensor nodes. From the results, it is evident that the proposed method not only enhances the reliability of data transmission but also distributes the energy consumption across wireless sensor networks.     

Slime mold inspired routing protocols for wireless sensor networks

Many biological systems are composed of unreliable components which self-organize effectively into systems that achieve a balance between efficiency and robustness. One such example is the true slime mold Physarum polycephalum which is an amoeba-like organism that seeks and connects food sources and efficiently distributes nutrients throughout its cell body. The distribution of nutrients is accomplished by a self-assembled resource distribution network of small tubes with varying diameter which can evolve with changing environmental conditions without any global control. In this paper, we exploit two different mechanisms of the slime mold??s tubular network formation process via laboratory experiments and mathematical behavior modeling to design two corresponding localized routing protocols for wireless sensor networks (WSNs) that take both efficiency and robustness into account. In the first mechanism of path growth, slime mold explores its immediate surroundings to discover and connect new food sources during its growth cycle. We adapt this mechanism for a path growth routing protocol by treating data sources and sinks as singular potentials to establish routes from the sinks to all the data sources. The second mechanism of path evolution is the temporal evolution of existing tubes through nonlinear feedback in order to distribute nutrients efficiently throughout the organism. Specifically, the diameters of tubes carrying large fluxes of nutrients grow to expand their capacities, and tubes that are not used decline and disappear entirely. We adapt the tube dynamics of the slime mold for a path evolution routing protocol. In our protocol, we identify one key adaptation parameter to adjust the tradeoff between efficiency and robustness of network routes. Through extensive realistic network simulations and ideal closed form or numerical computations, we validate the effectiveness of both protocols, as well as the efficiency and robustness of the resulting network connectivity.     

Forwarding Group Multicast Protocol (FGMP) for multihop, mobile wireless networks

In this paper we propose a new multicast protocol for multihop mobile wireless networks. Instead of forming multicast trees, a group of nodes in charge of forwarding multicast packets is designated according to members' requests. Multicast is then carried out via “scoped” flooding over such a set of nodes. The forwarding group is periodically refreshed to handle topology/membership changes. Multicast using forwarding group takes advantage of wireless broadcast transmissions and reduces channel and storage overhead, thus improving the performance and scalability. The key innovation with respect to wired multicast schemes like DVMRP is the use of flags rather than upstream/downstream link state, making the protocol more robust to mobility. The dynamic reconfiguration capability makes this protocol particularly suitable for mobile networks. The performance of the proposed scheme is evaluated via simulation and is compared to that of DVMRP and global flooding. This revised version was published online in August 2006 with corrections to the Cover Date.     

Using Trust to Establish a Secure Routing Model in Cognitive Radio Network

Specific to the selective forwarding attack on routing in cognitive radio network, this paper proposes a trust-based secure routing model. Through monitoring nodes’ forwarding behaviors, trusts of nodes are constructed to identify malicious nodes. In consideration of that routing selection-based model must be closely collaborative with spectrum allocation, a route request piggybacking available spectrum opportunities is sent to non-malicious nodes. In the routing decision phase, nodes’ trusts are used to construct available path trusts and delay measurement is combined for making routing decisions. At the same time, according to the trust classification, different responses are made specific to their service requests. By adopting stricter punishment on malicious behaviors from non-trusted nodes, the cooperation of nodes in routing can be stimulated. Simulation results and analysis indicate that this model has good performance in network throughput and end-to-end delay under the selective forwarding attack.     

Resource Management for Ad-Hoc Wireless Networks with Cluster Organization

Boosted by technology advancements, government and commercial interest, ad-hoc wireless networks are emerging as a serious platform for distributed mission-critical applications. Guaranteeing QoS in this environment is a hard problem because several applications may share the same resources in the network, and mobile ad-hoc wireless networks (MANETs) typically exhibit high variability in network topology and communication quality. In this paper we introduce DYNAMIQUE, a resource management infrastructure for MANETs. We present a resource model for multi-application admission control that optimizes the application admission utility, defined as a combination of the QoS satisfaction ratio. A method based on external adaptation (shrinking QoS for existing applications and later QoS expansion) is introduced as a way to reduce computation complexity by reducing the search space. We designed an application admission protocol that uses a greedy heuristic to improve application utility. For this, the admission control considers network topology information from the routing layer. Specifically, the admission protocol takes benefit from a cluster network organization, as defined by ad-hoc routing protocols such as CBRP and LANMAR. Information on cluster membership and cluster head elections allows the admission protocol to minimize control signaling and to improve application quality by localizing task mapping.     

Spine routing in ad hoc networks

An ad hoc network is a multihop wireless network in which mobile hosts communicate without the support of a wired backbone for routing messages. We introduce a self organizing network structure called a spine and propose a spine-based routing infrastructure for routing in ad hoc networks. We propose two spine routing algorithms: (a) Optimal Spine Routing (OSR), which uses full and up-to-date knowledge of the network topology, and (b) Partial-knowledge Spine Routing (PSR), which uses partial knowledge of the network topology. We analyze the two algorithms and identify the optimality-overhead trade-offs involved in these algorithms. This revised version was published online in August 2006 with corrections to the Cover Date.     

Energy and QoS Aware Routing in Wireless Sensor Networks

Many new routing protocols have been proposed for wireless sensor networks in recent years. Almost all of the routing protocols considered energy efficiency as the ultimate objective since energy is a very scarce resource for sensor nodes. However, the introduction imaging sensors has posed additional challenges. Transmission of imaging data requires both energy and QoS aware routing in order to ensure efficient usage of the sensors and effective access to the gathered measurements. In this paper, we propose an energy-aware QoS routing protocol for sensor networks which can also run efficiently with best-effort traffic. The protocol finds a least-cost, delay-constrained path for real-time data in terms of link cost that captures nodes energy reserve, transmission energy, error rate and other communication parameters. Moreover, the throughput for non-real-time data is maximized by adjusting the service rate for both real-time and non-real-time data at the sensor nodes. Such adjustment of service rate is done by using two different mechanisms. Simulation results have demonstrated the effectiveness of our approach for different metrics with respect to the baseline approach where same link cost function is used without any service differentiation mechanism.Kemal Akkaya received his B.S. degree in Computer Science from Bilkent University, Ankara, Turkey in 1997 and MS degree in Computer Science from Ortadogu Technical University (ODTU), Ankara, Turkey in 1999. He worked as a software developer at an automation project of Siemens and World Bank in Ankara, Turkey in 2000. He is currently a Ph.D. candidate at University of Maryland, Baltimore County (UMBC), Baltimore, MD. His research interests include energy aware routing, security and quality of service issues in ad hoc wireless networks.Mohamed F. Younis received B.S. degree in computer science and M.S. in engineering mathematics from Alexandria University in Egypt in 1987 and 1992, respectively. In 1996, he received his Ph.D. in computer science from New Jersey Institute of Technology. He is currently an assistant professor in the department of computer science and electrical engineering at the university of Maryland Baltimore County (UMBC). Before joining UMBC, he was with the Advanced Systems Technology Group, an Aerospace Electronic Systems R&D organization of Honeywell International Inc. While at Honeywell he led multiple projects for building integrated fault tolerant avionics, in which a novel architecture and an operating system were developed. This new technology has been incorporated by Honeywell in multiple products and has received worldwide recognition by both the research and the engineering communities. He also participated in the development the Redundancy Management System, which is a key component of the Vehicle and Mission Computer for NASAs X-33 space launch vehicle. Dr. Younis technical interest includes network architectures and protocols, embedded systems, fault tolerant computing and distributed real-time systems. Dr. Younis has four granted and three pending patents. He served on multiple technical committees and published over 40 technical papers in refereed conferences and journals.     

Improving peer connectivity in wide-area overlays of virtual workstations

Self-configuring virtual networks rely on structured P2P routing to provide seamless connectivity among nodes through overlay routing of virtual IP packets, support decentralized hole-punching to establish bi-directional communication links among nodes behind network address translators, and dynamic configuration of virtual IP addresses. Our experiences with deployments of virtual networks in support of wide-area overlays of virtual workstations (WOWs) reveal that connectivity constraints imposed by symmetric NATs and by Internet route outages often hinder P2P overlay structure maintenance and routability, subsequently limiting the ability of WOWs to deliver high-throughput computing through aggregation of resources in different domains. In this paper, we describe and evaluate two novel approaches which are generally applicable and fully decentralized, and show that they improve routability of structured P2P networks in such connectivity constrained environments: (1) a fault-tolerant routing algorithm based on simulated annealing from optimization theory, and (2) tunneling of connections between adjacent nodes (in the P2P identifier space) over common neighbors when direct communication is not possible. Simulation-based analyses show that (1) when pairs of nodes only have 70% chance of being able to communicate directly, the described approaches improve all-to-all routability of the network from 90% to 99%, and (2) even when only 70% of the nodes are behind NATs that include symmetric NATs, these techniques improve the all-to-all connectivity of the network from less than 95% to more than 99%. We have implemented these techniques in the IP-over-P2P (IPOP) virtual network and have conducted experiments with a 180-node WOW Condor pool, demonstrating that, at 81% probability of establishing a pair-wise connection, annealing and tunneling combined allow all nodes to be connected to the pool, compared to only 160 nodes in the absence of these techniques.

Performance analysis of ALOHA and <Emphasis Type="Italic">p</Emphasis>-persistent ALOHA for multi-hop underwater acoustic sensor networks

The extreme conditions under which multi-hop underwater acoustic sensor networks (UASNs) operate constrain the performance of medium access control (MAC) protocols. The MAC protocol employed significantly impacts the operation of the network supported, and such impacts must be carefully considered when developing protocols for networks constrained by both bandwidth and propagation delay.     

Establishing equivalence classes in preschool children with one-to-many and many-to-one training protocols

The present study set out to assess if the different probabilities reported in the literature of obtaining equivalence after baseline training with MTO and OTM protocols could be attributed to individual differences and, if so, whether equivalence formation could be facilitated by using familiar stimuli as nodes. In Experiment 1, 16 preschool children were trained on four sets of 2-choice match-to-sample tasks, eight with a OTM protocol (A-B, A-C, A-D, A-E) and eight with a MTO protocol (B-A, C-A, D-A, E-A). For four OTM and four MTO children only abstract stimuli were used. The other four OTM children and four MTO children received the same training but with familiar stimuli as nodes. All children received tests for equivalence (first) and symmetry (second). In Experiment 2, eight children who served in Experiment 1 participated again, four who had passed the equivalence test, and four who had failed that test. All children received the same baseline training as in Experiment 1 but with the opposite type of nodes (abstract instead of familiar, and vice versa) and training protocol (MTO instead of OTM, and vice versa). The results showed that (a) the children's performances (training and testing) were not affected by the training protocol; (b) equivalence formation occurred more readily when being trained with all abstract stimuli than when familiar stimuli served as nodes; and (c) most children who passed or did not pass the equivalence test in Experiment 1 repeated their performance in Experiment 2, irrespective of the conditions that were used.     

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.     

Dynamic Quality of Service Model for Improving Performance of Multimedia Real-Time Transmission in Industrial Networks

Nowadays, quality of service (QoS) is very popular in various research areas like distributed systems, multimedia real-time applications and networking. The requirements of these systems are to satisfy reliability, uptime, security constraints and throughput as well as application specific requirements. The real-time multimedia applications are commonly distributed over the network and meet various time constraints across networks without creating any intervention over control flows. In particular, video compressors make variable bit-rate streams that mismatch the constant-bit-rate channels typically provided by classical real-time protocols, severely reducing the efficiency of network utilization. Thus, it is necessary to enlarge the communication bandwidth to transfer the compressed multimedia streams using Flexible Time Triggered- Enhanced Switched Ethernet (FTT-ESE) protocol. FTT-ESE provides automation to calculate the compression level and change the bandwidth of the stream. This paper focuses on low-latency multimedia transmission over Ethernet with dynamic quality-of-service (QoS) management. This proposed framework deals with a dynamic QoS for multimedia transmission over Ethernet with FTT-ESE protocol. This paper also presents distinct QoS metrics based both on the image quality and network features. Some experiments with recorded and live video streams show the advantages of the proposed framework. To validate the solution we have designed and implemented a simulator based on the Matlab/Simulink, which is a tool to evaluate different network architecture using Simulink blocks.     

Contradictory Behavioral Biases Result from the Influence of Past Stimuli on Perception

Biases such as the preference of a particular response for no obvious reason, are an integral part of psychophysics. Such biases have been reported in the common two-alternative forced choice (2AFC) experiments, where participants are instructed to compare two consecutively presented stimuli. However, the principles underlying these biases are largely unknown and previous studies have typically used ad-hoc explanations to account for them. Here we consider human performance in the 2AFC tone frequency discrimination task, utilizing two standard protocols. In both protocols, each trial contains a reference stimulus. In one (Reference-Lower protocol), the frequency of the reference stimulus is always lower than that of the comparison stimulus, whereas in the other (Reference protocol), the frequency of the reference stimulus is either lower or higher than that of the comparison stimulus. We find substantial interval biases. Namely, participants perform better when the reference is in a specific interval. Surprisingly, the biases in the two experiments are opposite: performance is better when the reference is in the first interval in the Reference protocol, but is better when the reference is second in the Reference-Lower protocol. This inconsistency refutes previous accounts of the interval bias, and is resolved when experiments statistics is considered. Viewing perception as incorporation of sensory input with prior knowledge accumulated during the experiment accounts for the seemingly contradictory biases both qualitatively and quantitatively. The success of this account implies that even simple discriminations reflect a combination of sensory limitations, memory limitations, and the ability to utilize stimuli statistics.     

Reliable noninvasive genotyping based on excremental PCR of nuclear DNA purified with a magnetic bead protocol

A new protocol for extraction of DNA from faeces is presented. The protocol involves gentle washing of the surface of the faeces followed by a very simple DNA extraction utilizing the wash supernatant as the source of DNA. Unlike most other protocols, it does not involve the use of proteinase K and/or organic extraction, but is instead based on adsorption of the DNA to magnetic beads. The protocol was tested by microsatellite genotyping across six loci for sheep and reindeer faeces. Comparison with DNA extracted from blood demonstrated that the protocol was very reliable, even when used on material stored for a long time. The protocol was compared with another simple, solid-phase DNA-binding protocol, with the result that the bead-based protocol gave a slightly better amplification success and a lower frequency of allelic drop-outs. Furthermore, our experiments showed that the surface wash prior to DNA extraction is a crucial step, not only for our protocol, but for other solid-phase protocols as well.     

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.