Underwater acoustic sensor networks (UWASNs) are composed of underwater sensors that use sound to transmit information collected in the ocean. Since the sound speed is lower than radio wave, UWASNs suffer from much lower throughput and higher delay compared with terrestrial wireless sensor networks (TWSNs). Current methods manage to alleviate the bottleneck by replacing mutual handshakes with reservation mechanisms that consume lower overhead. However, their throughput improvement and delay reduction are very limited (e.g., the throughput is only 30% of the theoretical maximum for TLohi in 8-node networks), and most of their analysis and simulations are based on single-hop communication. In this work, we tackle the above challenges by proposing a priority scheduling approach for multi-hop topologies. First, we find that the scheduling problem of UWASNs is very different from that of TWSNs, and analyze the shortest schedule for the whole UWASN. Then, we design an efficient priority scheduling protocol at the MAC layer. Our approach performs parallel transmissions and prioritizes the scheduling by allocating longer time to heavier-traffic nodes. We have conducted extensive evaluations which show that the proposed protocol not only improves the throughput and delay performance greatly, but also benefits the fairness.

Recent studies have found that using multiple channels can separate concurrent transmissions and significantly improve network throughput. However, these studies have only considered wireless nodes that are equipped with omni-directional antennas, which have high interference. On the other hand, other researchers have found that using directional antennas in wireless networks can reduce interference and improve the network performance. But their studies have only considered single channel to be used in wireless networks with directional antennas. Thus, integrating the two technologies of multiple channels and directional antennas together can potentially bring more benefits. Some previous works have studies the capacity on the multi-channel wireless networks using directional antennas. However, the channel assignment problem of such networks has not been well studied. In this paper, we study the channel assignment problem in the multi-channel wireless networks using directional antennas. In particular, we study the problem: given a set of wireless nodes equipped with directional antennas, how many channels are needed to ensure collision-free transmission? We derive the upper bounds on the number of channels, which depend on the node density. We also construct several scenarios to examine the tightness of the derived bounds. Our result can be used to estimate the number of channels required for a practical wireless network. Besides, our results can also be used to provide a suggestion on the proper node density in the node deployment when the number of channels is given for a wireless network.

Reliability of tree-like multicast overlays caused by nodes' abrupt failures is considered as one of the major problems for the Internet application-layer media streaming service. In this paper, we address this problem by designing a distributed and light-weighted protocol named the instantaneous reliability oriented protocol (IRP). Unlike most of existing empirical solutions, we first define the overlay reliability problem formally, and propose a protocol containing a node joining algorithm (IRP-Join), a node preemption algorithm (IRP-Preempt), and a node switching algorithm (IRP-Switch) for reactively constructing and repairing the overlay, as well as proactively maintaining the overlay. With the formal problem presentation, we set up a paradigm for solving the overlay reliability problem by theoretically proving the effectiveness of our algorithms. Moreover, by comparing IRP with existing solutions via simulation-based experiments and real-world deployment, we show that IRP achieves a better reliability, while incurs fewer structural adjustments on the multicast overlay, thus, providing a superior overall performance.

Contour mapping is an important technique for Wireless Sensor Networks (WSNs) in environmental monitoring to abstract the information of a monitored field. State-of-the-art approaches for contour mapping, however, are neither energy-optimized, nor capable of handling heterogeneous user requests. In this paper, we develop a novel energy-efficient On-demand Active Contour Service (OACS) for power-constrained WSNs. OACS regresses the field intensity function with kernel Support Vector Regression (SVR), a novel machine learning tool that flexibly handles both contour line and contour map requests. OACS also adaptively accommodates a wide range of contour line/map precision requirements: (1) For applications of low precision, only a minimum set of nodes are scheduled in working mode while others are sleeping for conserving energy. (2) For applications of high precision, through an active and progressive learning algorithm, OACS determines the best set of nodes that should be turned on for improving the contour line/map precision. Evaluation based on diverse realistic models demonstrates that OACS provides quality and seamless contour services for various application requirements yet significantly conserves energy.

The capacity of wireless ad hoc networks is affected by two key factors: the interference among concurrent transmissions and the number of simultaneous transmissions on a single interface. Recent studies found that using multiple channels can separate concurrent transmissions and greatly improve network throughput. However, those studies only consider that wireless nodes are equipped with only omnidirectional antennas, which cause high collisions. On the other hand, some researchers found that directional antennas bring more benefits such as reduced interference and increased spatial reuse compared with omnidirectional antennas. But, they only focused on a single-channel network which only allows finite concurrent transmissions. Thus, combining the two technologies of multiple channels and directional antennas together potentially brings more benefits. In this paper, we propose a multi-channel network architecture (called MC-MDA) that equips each wireless node with multiple directional antennas. We derive the capacity bounds of MC-MDA networks under arbitrary and random placements. We will show that deploying directional antennas to multi-channel networks can greatly improve the network capacity due to increased network connectivity and reduced interference. We have also found that even a multi-channel network with a single directional antenna only at each node can give a significant improvement on the throughput capacity. Besides, using multiple channels mitigates interference caused by directional antennas. MC-MDA networks integrate benefits from multi-channel and directional antennas and thus have significant performance improvement.

The application of directional antennas in wireless ad hoc networks brings numerous benefits, such as increased spatial reuse and mitigated interferences. Most MAC protocols with directional antennas are based on the RTS/CTS mechanism which works well in wireless ad hoc networks using omnidirectional antennas. However, RTS/CTS frames cannot mitigate the interference completely. Besides, they also contribute a lot to the performance overhead. This paper studies the problem from a new perspective. We have found that the transmission success probability under directional transmission and directional reception is quite high when the antenna beamwidth is quite narrow. Motivated by the analytical results, we design a lightweight MAC protocol without RTS/CTS frames. The preliminary results demonstrate that this new protocol performs better than MAC protocols based on the RTS/CTS mechanism. The results also show that a collision-tolerant transmission is feasible under the narrow beam configuration.

In recent years, many distributed rating systems have been proposed against the increasing misbehaviors of peers in peer-to-peer (P2P) networks. However, the low accuracy, long-response time and vulnerabilities under the adversary attacks of P2P rating systems have long been criticized and hindering the practical deployment of such a mechanism. There is also a lack of systematic analysis and evaluation for understanding the systems. In this paper, we first present a framework of stochastic analytical model for evaluating P2P rating systems. The performances of two representative designs, namely the unstructured self-managing rating (UMR) system and the structured supervising rating (SSR) system, are then studied with our model. We identify the positive features as well as the negative ones of the two designs with different design choices and under various network environments and adversary attacks. We also propose a configurable loosely supervising rating system, and show that this system works inexpensively, and could make trade-off between the false rating attack resistance of the UMR system and the accuracy, responsiveness, whitewashing attack resistance as well as a failure resilience of the SSR system, thus providing a better overall performance according to the application context.

Applying directional antennas in wireless ad hoc networks offers numerous benefits, such as extended communication range, increased spatial reuse, improved capacity and suppressed interference. However, directional antennas can cause new location-dependent carrier sensing problems, such as new hidden terminal and deafness problems, which can cause severe penalties to the performance. Recently, a few schemes have been proposed to tackle these problems. However, these methods can provide limited solutions on the hidden terminal and deafness problems. We propose a new MAC protocol, termed the busy-tone based directional medium access control (BT-DMAC) protocol. When the transmission is in progress, the sender and the receiver will turn on their omnidirectional busy tones to protect the transmission. By combining with directional network allocation vector (DNAV), the scheme almost mitigates the hidden and the deafness problems completely. The mechanism increases the probability of successful data transmission and consequently improves the network throughput. This paper describes the BT- DMAC scheme and analyzes its performance. The simulation results also demonstrate the effectiveness of the protocol.

Abstract In this paper, we present a simple mathematical model for studying the performance of the BitTorrent ( http://www.bittorrent.com ) file sharing system. We are especially interested in the distribution of peers in different states of the download job progress. With the model we find that the distribution of the download peers follows an asymmetric U‐shaped curve under the stable state, due to BitTorrent's unchoking strategies. In addition, we find that the seeds' departure rate and the download peers' abort rate will influence the peer distribution in different ways notably. We also analyze the content availability under the dying process of the BitTorrent file sharing system. We find that the system's stability deteriorates with decreasing and unevenly distributed online peers, and BitTorrent's built‐in ‘tit‐for‐tat’ unchoking strategy could not help to preserve the integrity of the file among the download peers. We propose an innovative ‘tit‐for‐tat’ unchoking strategy which enables more peers to finish the download job and prolongs the system's lifetime. By playing our innovative strategy, download peers could cooperate to improve the stability of the system by making a trade‐off between the current downloading rate and the future service availability. Finally, experimental results are presented to validate our analytical results and support our proposals. Copyright © 2007 John Wiley & Sons, Ltd.

Abstract The phenomenon of system churn degrades the lookup performance of distributed hash table (DHT) systems greatly. To handle the churn, a number of approaches have been proposed to date. However, there is a lack of theoretical analysis to direct how to make design choices under different churn rates and how to configure their parameters optimally. In this paper, we analytically study three important aspects on optimizing DHT lookup performance under churn, i.e. lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for designers to make better design choices in the future. We first compare the performance of two representative lookup strategies—recursive routing and iterative routing—and explore the existence of better alternatives. Then we study the effectiveness of lookup parallelism in systems with different churn rates and show how to select the optimal degree of parallelism. Owing to the importance of key replication on lookup performance, we also analyze the reliability of the replicated key under two different replication policies, and show how to perform proper configuration. Besides the analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis. Copyright © 2007 John Wiley & Sons, Ltd.

As a fundamental problem in DHT-based P2P systems, load balancing is important to avoid performance degradation and guarantee system fairness. In this paper, to get a better understanding about the effectiveness of migration-based load balancing approaches in DHT systems, we analytically study two representative migration-based load balancing strategies: rendezvous directory strategy (RDS) and independent searching strategy (ISS). They differ in load information management and decision making in the process of load balancing. We analyze their performance in terms of efficiency, scalability and robustness, and explore the impact of their parameter settings. Based on the analysis results, we also propose a gossip-based strategy (GBS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. Later, the effectiveness of GBS is evaluated by simulation under different workload and churn.

Previous studies show that more than 85% of the peers have joined multiple torrents in BitTorrent, but theoretical work on multiple files BitTorrent downloading is rare. In this paper, we first consider the scenario of multi-torrent downloading. We present a fluid-model based analysis on the multi-torrent concurrent downloading scheme, which is implicitly adopted in practical applications, and quantitatively compare its performance with an alternative scheme of multi-torrent sequential downloading. We also consider the scenario of multi-file torrent downloading (e.g. multiple files shared within a single torrent), and find that the scheme of multi-file torrent concurrent downloading, which is explicitly engaged in practical applications, is inefficient. A new scheme named collaborative multi-file torrent sequential downloading is proposed, and we show via numerical analysis that the download performance could be improved by collaboration among the peers in different subtorrents. Finally, we propose a self-adaptive mechanism for practically deploying our multi-file torrent downloading scheme in a distributed fashion under situations when correlation among the files and majority peers' behaviors are unknown

Abstract — In this paper, a simple mathematical model is presented for studying the performance of the BitTorrent [1] file sharing system. We are especially interested in the distribution of the peers with different states of the download job completedness. With the model we find that in the stable state the distribution of the download peers follows a U-shaped curve, and the parameters such as the departure rate of the seeds and the abort rate of the download peers will influence the peer distribution in different ways notably. We also analyze the file availability and the dying process of the BitTorrent file sharing system. We find that the system’s stability deteriorates with the clustering of the peers, and BitTorrent’s built-in “tit-for-tat ” unchoking strategy could not help to preserve the integrity of the file among the download peers when the size of the community is small. An innovative peer selection strategy which enables more peers to finish the download job and prolongs the system’s lifetime is proposed, in which the peers cooperate to improve the stability of the system by making a tradeoff between the current download rate and the future service availability. Finally, experimental results are presented to validate our analysis and findings. I.

In DHT-based P2P systems, the technique of "virtual server" is widely used to achieve load balance. To efficiently handle the workload skewness , "virtual servers" are allowed to migrate between nodes. Among existing migration-based load balancing strategies, there are two main categories: (I) rendezvous directory strategy (RDS) and (2) independent searching strategy (ISS). However, none of them can achieve resilience and efficiency at the same time. In this paper, we propose a gossip dissemination strategy (GDS) for load balancing in DHT systems, which attempts to achieve the benefits of both RDS and ISS. GDS doesn't rely on a few static rendezvous directories to perform load balancing. Instead, load information is disseminated within the formed groups via a gossip protocol, and each peer has enough information to act as the rendezvous directory and perform load balancing within its group. Besides intra-group balancing, inter-group balancing and emergent balancing are also supported by GDS. To further improve system resilience, the position of the rendezvous directory is randomized in each round. For a better understanding, we also perform analytical studies on GDS in terms of its scalability and efficiency under churn. Finally, the effectiveness of GDS is evaluated by extensive simulation under different workload and churn levels

The phenomenon of churn degrades the lookup performance of DHT-based P2P systems greatly. To date, a number of approaches have been proposed to handle it from both the system side and the client side. However, there lacks theoretical analysis to direct how to make design choices under different churn levels and how to configure their parameters optimally. In this paper, we analytically study three important aspects on improving DHT lookup performance under churn, i.e., lookup strategy, lookup parallelism and lookup key replication. Our objective is to build a theoretical basis for DHT designers to make better design choices in the future. We first compare the performance of two representative lookup strategies - recursive routing and iterative routing, and explore the existence of better alternatives. Then we show the effectiveness of parallel lookup in systems with different churn levels and how to select the optimal degree of parallelism. Due to the importance of key replication on lookup performance, we also analyze the reliability of replicated keys under two different replication policies, and discuss how to make configuration in different environments. Besides analytical study, our results are also validated by simulation, and Kad is taken as a case to show the meaningfulness of our analysis

Video transmission over error-prone channels requires techniques that are efficient in compressing the video and robust against the channel errors. The application of MPEG-4 in video communication can conform to bandwidth limitations, but, on the other hand, the highly compressed bits are more susceptible to noise errors. Therefore, many researchers have been working on error concealment techniques to recover errors caused by noise. However, the errors are always assumed to have been correctly located, which is the precondition for error concealment. We propose a novel error detection technique. This scheme can effectively and efficiently detect some errors which cannot be detected traditionally. Experimental results show that the error detection ratio (EDR) for this type of error is more than 90%, even 100% sometimes.

Error concealment is an effective method to combat channel errors for video transmission. In video coding, motion vectors (MVs) are highly significant for the matching of the missing video block. Thus, how to recover the lost MV is an important issue for error concealment in video communications. Concerning the high block loss ratio (BLR) during video transmission and the matching of edge blocks in video frames, we proposed a selective motion vector matching (SMVM) algorithm for MV recovery. It incorporates the status flags of the neighboring pixels of the missing block and constructs new MV sets for block matching. Experimental results show that it significantly outperforms other existing MV recovery methods for error concealment at different BLRs.

In this paper, we propose a novel digital watermarking to hide a trademark into a host-image such that an unintended observer will not be aware of the watermarking. By inserting the watermarking information into the random positioning location of a DCT image, the image capability against median filtering can be greatly improved. Experimental results demonstrate that the resulting proposed digital watermarking scheme has a higher peak signal-to-noise ratio and the visual quality of the digital watermarked image is indistinguishable from the original unmarked image.

Error concealment is important for video transmission over noisy channels. This paper presents a new spatial error concealment algorithm with low complexity to recover the lost information corrupted by channel errors, especially by burst errors, which are very common in noisy channels. Firstly, we detect the edge components in neighboring boundary pixels surrounding the corrupted macroblock (MB) group. Then for every MB in the corrupted MB group, we can judge which edges may have affected this MB. Finally, each pixel in this MB can be interpolated from boundary pixels according to the corresponding edges. Experimental results show that our low complexity algorithm is capable of restoring high-frequency (edge) information as well as low-frequency information corrupted by channel errors, especially by burst errors, and provides better performance compared with conventional methods

Transmission of compressed video over error-prone channels requires techniques that are efficient in compressing the video and are robust against the channel errors. The application of MPEG-4 can conform to the bandwidth limitation, but the highly compressed bits will be more susceptible to noise errors. In this paper, we present a mode-based error detection (MED) technique and a mode-based unequal error protection (M-UEP) technique to provide the robust video transmission of MPEG-4 compressed bits over error-prone channels. The MED technique can detect errors effectively and efficiently, which cannot be detected traditionally. Experimental results show that the error-detection ratio is more than 90%, and sometimes even 100%. Concerning the M-UEP, experimental results prove that it can provide better decoded video quality than the traditional unequal error protection technique does. In conclusion, the two proposed techniques are highly effective and efficient for the robust transport of MPEG-4 video over error-prone channels.

Temporal partitioning is a crucial step in the high-level synthesis (HLS) of dynamically reconfigurable systems (DRS). Much of the previous work has focused on temporal partitioning techniques that use simple cost models based solely on singular operations and fixed reconfigurable resource constraints, which often ignore the impact of the neighboring properties of operations in order to reduce the complexity of DRS design space exploration and reconfiguration overhead. In this paper we present a two-phase approach to solve temporal partitioning problems combining estimation of the properties of interconnected operations and quantitatively evaluating the communication cost between temporal partitions.

Reconfigurable Computing (RC) is a technology that attempts to increase computational power by customizing the computational platform to the specific problem at hand. This approach is favorable for handling problems like radiosity distribution computation, which consist of a fine granularity of parallel floating point multiplications. We have performed a feasibility study on using reconfigurable hardware for interactive radiosity distribution computation. We have introduced and applied techniques to convert the conventional algorithms on Radiosity Redistribution into parallel execution structures, especially in reusing patches information. Parallel Progressive Radiosity Implementation (PPR), a new system architecture with swappable area is proposed to handle Form Factor Determination and Radiosity Redistribution dynamically in RC platforms, which reduces the unresolved conflicts between the resources starvation.

Previous studies on disk scheduling for video services were usually based on computer simulation. We present analysis on disk scheduling for video services. This paper first gives a short review on the various disk scheduling algorithms. It then concentrates on the analysis of two major disk scheduling algorithms, namely, CLOOK and LOOK. The purpose of the analysis is to obtain the maximum number of simultaneous users supported by systems using these two algorithms. The results of the analysis show that the CLOOK algorithm performs slightly better than LOOK algorithm in video applications. Then, this paper discusses disk scheduling for supporting special user functions such as "forward search" and "reverse search". It is shown that the maximum number of user streams supported drops dramatically when such user functions are used. A technique called redundancy for special user functions (RESUF) is then studied. Analysis of the technique shows that it can keep the I/O demands to almost constant under all user request conditions.

No abstract available.

Cache replacement algorithms when applied in Internet systems are studied in this paper. The use of conventional replacement algorithms such as LRU and LFU is first discussed. We then present a new cache replacement algorithm called optimal cache replacement (OCR) algorithm for Internet systems. Analysis and simulation on OCR algorithm are performed. The results show that for small caches, OCR algorithm can outperform the conventional LFU algorithm by giving 50% improvement in cache hit rate. When the cache size is large, OCR algorithm still provides 18% improvement.

An execution model for AND-parallel execution of logic programs is presented. This model is designed on the basis of the Lin-Kumar-Leung model and a Backward Execution algorithm proposed by Conery. The new algorithm is applicable to non-static data dependency graphs