Network coding has been shown to improve various performance metrics in computer networks. However, the use of network coding, especially random linear network coding, incurs serious time delay in the decoding process and thus it is imperative to use a network coding implementation that has low decoding latency characteristics, e.g. a parallelized implementation. In this paper, we investigate the problem of parallelizing Pipeline network coding, a variant of random linear coding recently developed in order to alleviate the problems of random linear coding. We propose a novel massively parallelized decoding algorithm leveraging General Purpose Graphics Processing Unit (GPGPU) and show its performance enhancement by up to 100% compared with previous GPGPU-based parallel algorithms via experiments on real systems.

ABSTRACT A wireless mesh network has been popularly researched as a wireless backbone for Internet access. However, the deployment of wireless mesh networks in unlicensed bands of urban areas is challenging because of interference from external users such as residential access points. We have proposedUrban‐X, which is a first attempt towards multi‐radio cognitive mesh networks in industrial, scientific, and medical bands.Urban‐Xfirst controls network topology with a distributed channel assignment to avoid interference in large timescale. In such a topology, we develop a new link‐layer transmission‐scheduling algorithm together with source rate control as a small‐timescale approach, which exploits receiver diversity when receivers of multi‐flows can have different channel conditions because of varying interference. For this purpose, mesh nodes probe the channel condition of received mesh nodes using group Request to Send and group Clear to Send. In this study, we establish a mathematicalUrban‐Xmodel in a cross‐layer architecture, adopting a well‐known network utility maximization framework. We demonstrate the feasibility of our idea using a simulation on the model. Simulation results show improved network throughput from exploiting receiver diversity and distributed channel assignment under varying external user interference. Copyright © 2012 John Wiley & Sons, Ltd.

TCP over Mobile Ad-hoc Networks (MANETs) is challenging due to frequent route breaks, high random errors, and DATA-ACK interference. Network coded multipath approaches have been shown in several previous studies to be an effective transmission paradigms in disruptive networks. However, most of the previous studies either have no adaptive redundancy control or rely on theoretical models that require knowledge at all relays of the entire network state. In this paper, we propose a network coded multipath scheme for conventional TCPCodeMP that adapts to frequent link changes in MANET and requires no explicit control messages. The scheme exploits multiple-path redundancy and maintains total transparency to transport layer protocols. The proposed coding scheme is based on three components: (1) random linear coding scheme with adjustable redundancy, (2) multipath routing, (3) ACK Piggy coding. Simulation results show that in a 3-hop static scenario, the proposed multipath scheme improves TCP flows goodput by 70% compared to our previous single-path scheme. In an extreme MANET scenario where two TCP sessions co-exists and nodes are moving as fast as 25 m/s with up to 40% packet error rate (an environment in which regular TCP collapses completely), CodeMP achieves at least 700Kbps aggregate TCP goodput, with a Jain's fairness index of 0.99.

In this work-in-progress paper, we present a network coding scheme based on random linear coding (RLC), named cumulative RLC. Cumulative RLC applies RLC in a cumulative manner such that the end-to-end delay is minimized and it can be used for real-time one-to-many video distribution over wireless networks. The proposed cumulative RLC is well-suited especially for media applications with low-latency constraints such as real-time resilient video distribution for interactive service scenarios. The key property of cumulative RLC is reducing the waiting delay during the RLC encoding procedure. To verify the efficiency of the proposed cumulative RLC, we implement a real-time resilient video distribution system employing cumulative RLC over a IEEE 802.11-based wireless network. Experimental results show that in a typical setting, cumulative RLC yields reducing RLC encoding delay so it can help efficient real-time video distribution.

The Network Utility Maximization (NUM) has been extensively used in both wired and wireless networks and has been very helpful to provide insight on optimal controls of various parameters such as power, scheduling and rate control. However, the popular opportunistic scheduling mechanism, that improves the system performance by exploiting time varying channel conditions at different receivers, has not been incorporated in the framework yet. In this paper, we extend the framework and derive optimal flow control and link scheduling for wireless multihop networks with opportunistic scheduling. More precisely, we formulate the NUM problem with new resource constraints to include the benefits of opportunistic scheduling and then proceed to solve the problem. The formulation turns out to be a non-convex problem, however we propose an algorithm that approximates the optimum solution. Numerical results show that the proposed algorithm achieves significant throughput gain.

In this paper, we investigate parallel implementation techniques for network coding. It is known that network coding is useful for both wired and wireless networks and it also mitigates peer/piece selection problems in P2P file sharing systems. However, due to the decoding complexity of network coding, there have been concerns about adoption of network coding in practical network systems and to improve the decoding performance, the exploitation of parallelism has been proposed previously. In this paper, we argue that naive parallelization strategies of network coding may result in unbalanced workload distribution, and thus, limiting performance improvements. We further argue that a higher performance enhancement can be achieved through balanced partitioning methods in parallelized network coding and propose new parallelization techniques for network coding. Our experiments show that on a quad-core processor system, proposed algorithms exhibit up to 5.69 speedup which is better than the linear speedup with the influence of additional cache. Moreover, on an octal-core system, our algorithms even achieve speedup of 8.46 compared to a sequential network coding and 43.3 percent faster than an existing parallelized technique using 1 Mbytes data with 1,024 \times 1,024 coefficient matrix size.

Vehicular ad hoc networks (VANETs) are envisioned to provide us with numerous interesting services in the near future. One of the most promising applications is the dissemination of commercial advertisements via car-to-car communication. However, due to non-cooperative behavior of selfish nodes or even malicious ones in the real-world scenario, such vehicular advertisement system cannot be realized unless proper incentives and security mechanisms are taken into consideration. This paper presents Signature-Seeking Drive (SSD), a secure incentive framework for commercial ad dissemination in VANETs. Unlike currently proposed incentive systems, SSD does not rely on tamper-proof hardware or game theoretic approaches, but leverages a PKI (Public Key Infrastructure) to provide secure incentives for cooperative nodes. With a set of ad dissemination designs proposed, we demonstrate that our SSD is robust in both incentive and security perspectives.

In this paper we study multi-hop ad hoc routing in a Underwater Sensor Network (UWSN), a novel network paradigm for ad hoc underwater investigation with a large number of low cost underwater sensors. In UWSN, sensors are mobile with water current and dispersion, and use a wireless acoustic channel for communications. However, the large propagation latency and very low bandwidth of an acoustic channel could cause widespread collisions. Moreover, the mobility of sensors requires route management and causes additional traffic, thus worsening the situation. In this paper, we propose Under-Water Diffusion (UWD), a multi-hop ad hoc routing and in-network processing protocol. Since any on-demand flood or proactive exchange is considered harmful in underwater, UWD uses no proactive routing message exchange and negligible amount of ondemand floods in the environment with homogeneous GPSfree nodes and random node mobility. We validate UWD through both the mathematical analysis and simulations.

Over recent years, mobile Internet devices such as laptops, PDAs, smart phones etc, have become extremely popular and widespread. Once on board of a vehicle, these devices can automatically connect to the vehicle processor and thus greatly amplify the communications and processing capabilities available to the owner in a "pedestrian mode". We envision that this "amplification" opportunity will be one of the drivers of car to car and car to curb communications. In fact, the car communications system will not be used exclusively for mobile Internet access, but also as a distributed platform for the "opportunistic" cooperation among people with shared interests/goals. Exchanging safety messages among vehicles is a compelling example. Stretching opportunistic cooperation well beyond safety messages, we discuss in this paper the concept of virtual "flea market" over VANET called FleaNet In FleaNet, customers, either mobile (i.e., vehicles) or stationary (i.e., pedestrians, roadside shop owner), express their demands/offers, e.g., want to buy or sell an item, via radio queries. These queries are opportunistically disseminated exploiting in part the mobility of other customers in order to find the customer/vendor with matching needs/resources. In the paper we identify the key performance metrics, namely query resolution latency, scalability, and mobility. Based on the metrics, using models and simulation, we show that FleaNet can efficiently support a market place over vehicular networks

Smart antennas present a radical way to improve the capacity of wireless networks. The advantages of such antennas can be leveraged by the MAC and higher layers. In this paper, we present SPACE-MAC, a MAC protocol which enables "spatial reuse" of the medium by multiple transmit/receive pairs which are in the same collision domain. SPACE-MAC prevents interference between such pairs by selectively nulling the signals from potentially interfering transmissions. This is achieved in a totally distributed fashion utilizing channel state information (CSI) at both transmitter and receiver to adjust antennas weights for each packet transmission. SPACE-MAC can operate effectively in cluttered (e.g., indoor) environments. SPACE-MAC achieves spatial reuse without requiring a separate channel for exchanging channel state information. This allows considerably better channel utilization. We investigate performance improvements of SPACE-MAC with respect to IEEE 802.11 DCF MAC using omnidirectional antennas.

Mobile ad hoc networks (MANETs) are vulnerable to routing attacks, especially attacks launched by non-cooperative (selfish or compromised) network members and appear to be protocol compliant. For instance, since packet loss is common in mobile wireless networks, the adversary can exploit this fact by hiding its malicious intents using compliant packet losses that appear to be caused by environmental reasons.In this paper we study two routing attacks that use non-cooperative network members and disguised packet losses to deplete ad hoc network resources and to reduce ad hoc routing performance. These two routing attacks have not been fully addressed in previous research. We propose the design of "self-healing community" to counter these two attacks. Our design exploits the redundancy in deployment which is typical of most ad hoc networks; Namely, it counters non-cooperative attacks using the probabilistic presence of nearby cooperative network members.To realize the new paradigm, we devise localized simple schemes to (re-)configure self-healing communities in spite of random node mobility. We develop a general analytic model to prove the effectiveness of our design. Then we implement our secure ad hoc routing protocols in simulation to verify the cost and overhead incurred by maintaining the communities. Our study confirms that the community-based security is a cost-effective strategy to make off-the-shelf ad hoc routing protocols secure.

In this paper, we propose a swarm intelligence strategy for constructing a mobile backbone multicasting network which leads to improved scalability and connectivity compared to conventional flat networks. The strategy combines a simple clustering technique and on demand multicast protocol (ODMRP). Also we show benefits of the mobile backbone network through a simulation study.

Abstract — In wireless ad-hoc networks, unidirectional links occur for several reasons: non uniform transmit power, non uniform background noise, and external interference. Several researchers have addressed unidirectional links and the associated unidirectional routing problem. The main focus has been so far on “unicast ” routing; the consensus is that unidirectional links should be detected and avoided. In this paper, we consider the multicast case and derive a different conclusion: namely, it pays to exploit unidirectional links rather then avoid them. To prove the point, we select a popular ad hoc multicast protocol, On-Demand Multicast Routing Protocol (ODMRP) and introduce a slightly modified version, ODMRP-ASYM, that can handle unidirectional links. Specifically, ODMRP-ASYM reroutes the Join Reply packet when a unidirectional link is detected on the Join Query path. The option is invoked only when a unidirectional link is detected. The main advantages are: control overhead comparable with ODMRP even in highly asymmetric topologies; virtually no performance degradation in presence of unidirectional links (while ODMRP typically suffers up to 15 % drop in delivery performance), and; 2-connectivity maintenance even if no bidirectional path exists between sender and receiver (in this case, unidirectional link avoidance strategies fail). Extensive simulation experiments demonstrate ODMRP-ASYM robustness to unidirectional links and superiority over conventional ODMRP.

We develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of /spl Omega/(N/sup 3///spl radic/C), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.