RamboNodes for the Metropolitan Ad Hoc Network

We present an algorithm to store data robustly in a large, geographically distributed network by means of localized regions of data storage that move in response to changing conditions. For example, data might migrate away from failures or toward regions of high demand. The PersistentNode algorithm provides this service robustly, but with limited safety guarantees. We use the RAMBO framework to transform PersistentNode into RamboNode, an algorithm that guarantees atomic consistency in exchange for increased cost and decreased liveness. In addition, a half-life analysis of RamboNode shows that it is robust against continuous low-rate failures. Finally, we provide experimental simulations for the algorithm on 2000 nodes, demonstrating how it services requests and examining how it responds to failures.

Cluster-based Intrusion Detection (CBID) architecture for mobile ad hoc networks

The ad hoc networks are vulnerable to attacks due to distributed nature and lack of infrastructure. Intrusion detection systems (IDS) provide audit and monitoring capabilities that offer the local security to a node and help to perceive the specific trust level of other nodes. The clustering protocols can be taken as an additional advantage in these processing constrained networks to collaboratively detect intrusions with less power usage and minimal overhead. Existing clustering protocols are not suitable for intrusion detection purposes, because they are linked with the routes. The route establishment and route renewal affects the clusters and as a consequence, the processing and traffic overhead increases due to instability of clusters. The ad hoc networks are battery and power constraint, and therefore a trusted monitoring node should be available to detect and respond against intrusions in time. This can be achieved only if the clusters are stable for a long period of time. If the clusters are regularly changed due to routes, the intrusion detection will not prove to be effective. Therefore, a generalized clustering algorithm has been proposed that can run on top of any routing protocol and can monitor the intrusions constantly irrespective of the routes. The proposed simplified clustering scheme has been used to detect intrusions, resulting in high detection rates and low processing and memory overhead irrespective of the routes, connections, traffic types and mobility of nodes in the network. Clustering is also useful to detect intrusions collaboratively since an individual node can neither detect the malicious node alone nor it can take action against that node on its own.

Optimally increasing secure connectivity in multihop wireless ad hoc networks

We consider the problem of how to maximize secure connectivity of multi-hop wireless ad hoc networks after deployment. Two approaches, based on graph augmentation problems with nonlinear edge costs, are formulated. The first one is based on establishing a secret key using only the links that are already secured by secret keys. This problem is in NP-hard and does not accept polynomial time approximation scheme PTAS since minimum cutsets to be augmented do not admit constant costs. The second one is based of increasing the power level between a pair of nodes that has a secret key to enable them physically connect. This problem can be formulated as the optimal key establishment problem with interference constraints with bi-objectives: (i) maximizing the concurrent key establishment flow, (ii) minimizing the cost. We show that both problems are NP-hard and MAX-SNP (i.e., it is NP-hard to approximate them within a factor of 1 + e for e > 0 ) with a reduction to MAX3SAT problem. Thus, we design and implement a fully distributed algorithm for authenticated key establishment in wireless sensor networks where each sensor knows only its one- hop neighborhood. Our witness based approaches find witnesses in multi-hop neighborhood to authenticate the key establishment between two sensor nodes which do not share a key and which are not connected through a secure path.

An analytical approach to the study of cooperation in wireless ad hoc networks

In wireless ad hoc networks, nodes communicate with far off destinations using intermediate nodes as relays. Since wireless nodes are energy constrained, it may not be in the best interest of a node to always accept relay requests. On the other hand, if all nodes decide not to expend energy in relaying, then network throughput will drop dramatically. Both these extreme scenarios (complete cooperation and complete noncooperation) are inimical to the interests of a user. In this paper, we address the issue of user cooperation in ad hoc networks. We assume that nodes are rational, i.e., their actions are strictly determined by self interest, and that each node is associated with a minimum lifetime constraint. Given these lifetime constraints and the assumption of rational behavior, we are able to determine the optimal share of service that each node should receive. We define this to be the rational Pareto optimal operating point. We then propose a distributed and scalable acceptance algorithm called Generous TIT-FOR-TAT (GTFT). The acceptance algorithm is used by the nodes to decide whether to accept or reject a relay request. We show that GTFT results in a Nash equilibrium and prove that the system converges to the rational and optimal operating point.

An efficient pricing based protocol for broadcasting in wireless ad hoc networks

In many applications of wireless ad hoc networks, wireless nodes are owned by rational and intelligent users. In this paper, we call nodes selfish if they are owned by independent users and their only objective is to maximize their individual goals. In such situations, it may not be possible to use the existing protocols for wireless ad hoc networks as these protocols assume that nodes follow the prescribed protocol without deviation. Stimulating cooperation among these nodes is an interesting and challenging problem. Providing incentives and pricing the transactions are well known approaches to stimulate cooperation. In this paper, we present a game theoretic framework for truthful broadcast protocol and strategy proof pricing mechanism called Immediate Predecessor Node Pricing Mechanism (IPNPM). The phrase strategy proof here means that truth revelation of cost is a weakly dominant-strategy (in game theoretic terms) for each node. In order to steer our mechanism-design approach towards practical implementation, we compute the payments to nodes using a distributed algorithm. We also propose a new protocol for broadcast in wireless ad hoc network with selfish nodes based on IPNPM. The features of the proposed broadcast protocol are reliability and a significantly reduced number of packet forwards compared to the number of network nodes, which in turn leads to less system-wide power consumption to broadcast a single packet. Our simulation results show the efficacy of the proposed broadcast protocol.

Locant: A nature inspired location service for ad hoc networks

An efficient location service is a prerequisite to any robust, effective and precise location information aided Mobile Ad Hoc Network (MANET) routing protocol. Locant, presented in this paper is a nature inspired location service which derives inspiration from the insect colony framework, and it is designed to work with a host of location information aided MANET routing protocols. Using an extensive set of simulation experiments, we have compared the performance of Locant with RLS, SLS and DLS, and found that it has comparable or better performance compared to the above three location services on most metrics and has the least overhead in terms of number of bytes transmitted per location query answered.

Mermera: Non-Coherent Distributed Shared Memory for Parallel Computing

The proliferation of inexpensive workstations and networks has prompted several researchers to use such distributed systems for parallel computing. Attempts have been made to offer a shared-memory programming model on such distributed memory computers. Most systems provide a shared-memory that is coherent in that all processes that use it agree on the order of all memory events. This dissertation explores the possibility of a significant improvement in the performance of some applications when they use non-coherent memory. First, a new formal model to describe existing non-coherent memories is developed. I use this model to prove that certain problems can be solved using asynchronous iterative algorithms on shared-memory in which the coherence constraints are substantially relaxed. In the course of the development of the model I discovered a new type of non-coherent behavior called Local Consistency. Second, a programming model, Mermera, is proposed. It provides programmers with a choice of hierarchically related non-coherent behaviors along with one coherent behavior. Thus, one can trade-off the ease of programming with coherent memory for improved performance with non-coherent memory. As an example, I present a program to solve a linear system of equations using an asynchronous iterative algorithm. This program uses all the behaviors offered by Mermera. Third, I describe the implementation of Mermera on a BBN Butterfly TC2000 and on a network of workstations. The performance of a version of the equation solving program that uses all the behaviors of Mermera is compared with that of a version that uses coherent behavior only. For a system of 1000 equations the former exhibits at least a 5-fold improvement in convergence time over the latter. The version using coherent behavior only does not benefit from employing more than one workstation to solve the problem while the program using non-coherent behavior continues to achieve improved performance as the number of workstations is increased from 1 to 6. This measurement corroborates our belief that non-coherent shared memory can be a performance boon for some applications.

Joint Optimization of Area Spectral Efficiency and Delay over PPP Interfered Ad-Hoc Networks

To evaluate the performance of the co-channel transmission based communication, we propose a new metric for area spectral efficiency (ASE) of interference limited ad-hoc network by assuming that the nodes are randomly distributed according to a Poisson point processes (PPP). We introduce a utility function, U = ASE/delay and derive the optimal ALOHA transmission probability p and the SIR threshold τ that jointly maximize the ASE and minimize the local delay. Finally, numerical results have been conducted to confirm that the joint optimization based on the U metric achieves a significant performance gain compared to conventional systems.

A virtual backbone based approach for cooperative caching in mobile ad hoc networks

Cache look up is an integral part of cooperative caching in ad hoc networks. In this paper, we discuss a cooperative caching architecture with a distributed cache look up protocol which relies on a virtual backbone for locating and accessing data within a cooperate cache. Our proposal consists of two phases: (i) formation of a virtual backbone and (ii) the cache look up phase. The nodes in a Connected Dominating Set (CDS) form the virtual backbone. The cache look up protocol makes use of the nodes in the virtual backbone for effective data dissemination and discovery. The idea in this scheme is to reduce the number of nodes involved in cache look up process, by constructing a CDS that contains a small number of nodes, still having full coverage of the network. We evaluated the effect of various parameter settings on the performance metrics such as message overhead, cache hit ratio and average query delay. Compared to the previous schemes the proposed scheme not only reduces message overhead, but also improves the cache hit ratio and reduces the average delay

PEER TO PEER CACHE RESOLUTION MECHANISM FOR MOBILE AD HOC NETWORKS

In this paper we investigate the problem of cache resolution in a mobile peer to peer ad hoc network. In our vision cache resolution should satisfy the following requirements: (i) it should result in low message overhead and (ii) the information should be retrieved with minimum delay. In this paper, we show that these goals can be achieved by splitting the one hop neighbours in to two sets based on the transmission range. The proposed approach reduces the number of messages flooded in to the network to find the requested data. This scheme is fully distributed and comes at very low cost in terms of cache overhead. The experimental results gives a promising result based on the metrics of studies.

An enhanced relay-enabled medium access control protocol for wireless ad hoc networks

In this paper we propose an enhanced relay-enabled distributed coordination function (rDCF) for wireless ad hoc networks. The idea of rDCF is to use high data rate nodes to work as relays for the low data rate nodes. The relay helps to increase the throughput and lower overall blocking time of nodes due to faster dual-hop transmission. rDCF achieves higher throughput over IEEE 802.11 distributed coordination function (DCF). The protocol is further enhanced for higher throughput and reduced energy. These enhancements result from the use of a dynamic preamble (i.e. using short preamble for the relay transmission) and also by reducing unnecessary overhearing (by other nodes not involved in transmission). We have modeled the energy consumption of rDCF, showing that rDCF provides an energy efficiency of 21.7% at 50 nodes over 802.11 DCF. Compared with the existing rDCF, the enhanced rDCF (ErDCF) scheme proposed in this paper yields a throughput improvement of 16.54% (at the packet length of 1000 bytes) and an energy saving of 53% at 50 nodes.

Modelling energy consumption of relay-enabled MAC protocols in ad hoc networks

To enhance the throughput of ad hoc networks, dual-hop relay-enabled transmission schemes have recently been proposed. Since in ad hoc networks throughput is normally related to their energy consumption, it is important to examine the impact of using relay-enabled transmissions on energy consumption. In this paper, we present an analytical energy consumption model for dual-hop relay-enabled medium access control (MAC) protocols. Based on the recently reported relay-enabled distributed coordination function (rDCF), we have shown the efficacy of the proposed analytical model. This is a generalized model and can be used to predict energy consumption in saturated relay-enabled ad hoc networks via energy decomposition. This is helpful in designing MAC protocols for cooperative communications and it is shown that using a relay results not only in a better throughput but also better energy efficiency.

Modeling energy consumption of dual-hop relay based MAC protocols in ad hoc networks

Given that the next and current generation networks will coexist for a considerable period of time, it is important to improve the performance of existing networks. One such improvement recently proposed is to enhance the throughput of ad hoc networks by using dual-hop relay-based transmission schemes. Since in ad hoc networks throughput is normally related to their energy consumption, it is important to examine the impact of using relay-based transmissions on energy consumption. In this paper, we present an analytical energy consumption model for dual-hop relay-based medium access control (MAC) protocols. Based on the recently reported relay-enabled Distributed Coordination Function (rDCF), we have shown the efficacy of the proposed analytical model. This is a generalized model and can be used to predict energy consumption in saturated relay-based ad hoc networks. This model can predict energy consumption in ideal environment and with transmission errors. It is shown that using a relay results in not only better throughput but also better energy efficiency. Copyright (C) 2009 Rizwan Ahmad et al.