Mobi-Sync: Efficient Time Synchronization for Mobile Underwater SensorNetworks

Abstract

Time synchronization is an important requirement for many services provided by distributed networks. A lot of time synchronization protocols have been proposed for terrestrial Wireless Sensor Networks (WSNs). However, none of them can be directly applied to Underwater Sensor Networks (UWSNs). A synchronization algorithm for UWSNs must consider additional factors such as long propagation delays from the use of acoustic communication and sensor node mobility. These unique challenges make the accuracy of synchronization procedures for UWSNs even more critical. Time synchronization solutions specifically designed for UWSNs are needed to satisfy these new requirements. This paper proposes Mobi-Sync, a novel time synchronization scheme for mobile underwater sensor networks. Mobi-Sync distinguishes itself from previous approaches for terrestrial WSN by considering spatial correlation among the mobility patterns of neighboring UWSNs nodes. This enables Mobi-Sync to accurately estimate the long dynamic propagation delays. Simulation results show that Mobi-Sync outperforms existing schemes in both accuracy and energy efficiency.

Microarchitecture of a Coarse-Grain Out-of-Order Superscalar Processor

Abstract

We explore the design, implementation, and evaluation of a coarse-grain superscalar processor in the context of the microarchitecture of the Control Processor (CP) of the Multilevel Computing Architecture (MLCA), a novel architecture targeted for multimedia multicore systems. The MLCA augments a traditional multicore architecture (called the lower level) with a CP (called the top-level), which automatically extracts parallelism among coarse-grain units of computation (tasks), synchronizes these tasks and schedules them for execution on processors. It does so in a fashion similar to how instruction-level parallelism is extracted by superscalar processors, i.e., using register renaming, Out-of-Order Execution (OoOE) and scheduling. The coarse-grain nature of tasks imposes challenging constraints on the direct use of these techniques, but also offers opportunities for simpler designs. We analyze the impact of these constraints and opportunities and present novel microarchitectural mechanisms for coarse-grain superscalar execution, including register renaming, task queue, dynamic out-of-order scheduling and task-issue. We design an MLCA system around our CP microarchitecture and implement it on an FPGA. We evaluate the system using multimedia applications and show good scalability for eight processors, limited by the memory bandwidth of the FPGA platform. Furthermore, we show that the CP introduces little overhead in terms of resource usage. Finally, we show scalability beyond eight processors using cycle-accurate RTL-level simulation with an idealized memory subsystem. We demonstrate that the CP poses no performance bottlenecks and is scalable up to 32 processors.

IP-Geolocation Mapping for Moderately Connected Internet Regions

Abstract

Most IP-geolocation mapping schemes [14], [16], [17], [18] take delay-measurement approach, based on the assumption of a strong correlation between networking delay and geographical distance between the targeted client and the landmarks. In this paper, however, we investigate a large region of moderately connected Internet and find the delay-distance correlation is weak. But we discover a more probable rule—with high probability the shortest delay comes from the closest distance. Based on this closest-shortest rule, we develop a simple and novel IP-geolocation mapping scheme for moderately connected Internet regions, called GeoGet. In GeoGet, we take a large number of webservers as passive landmarks and map a targeted client to the geolocation of the landmark that has the shortest delay. We further use JavaScript at targeted clients to generate HTTP/Get probing for delay measurement. To control the measurement cost, we adopt a multistep probing method to refine the geolocation of a targeted client, finally to city level. The evaluation results show that when probing about 100 landmarks, GeoGet correctly maps 35.4 percent clients to city level, which outperforms current schemes such as GeoLim [16] and GeoPing [14] by 270 and 239 percent, respectively, and the median error distance in GeoGet is around 120 km, outperforming GeoLim and GeoPing by 37 and 70 percent, respectively.

In-Network Estimation with Delay Constraints in Wireless Sensor Networks

Abstract

The use of wireless sensor networks (WSNs) for closing the loops between the cyberspace and the physical processes is more attractive and promising for future control systems. For some real-time control applications, controllers need to accurately estimate the process state within rigid delay constraints. In this paper, we propose a novel in-network estimation approach for state estimation with delay constraints in multihop WSNs. For accurately estimating a process state as well as satisfying rigid delay constraints, we address the problem through jointly designing in-network estimation operations and an aggregation scheduling algorithm. Our in-network estimation operation performed at relays not only optimally fuses the estimates obtained from the different sensors but also predicts the upper stream sensors' estimates which cannot be aggregated to the sink before deadlines. Our estimate aggregation scheduling algorithm, which is interference free, is able to aggregate as much estimate information as possible from the network to the sink within delay constraints. We proved the unbiasedness of in-network estimation, and theoretically analyzed the optimality of our approach. Our simulation results corroborate our theoretical results and show that our in-network estimation approach can obtain significant estimation accuracy gain under different network settings.

IDM: An Indirect Dissemination Mechanism for Spatial Voice Interactionin Networked Virtual Environments

Abstract

One type of Peer-to-Peer (P2P) live streaming has not yet been significantly investigated, namely topologies that provide many-to-many, interactive connectivity. Exemplar applications of such P2P systems include spatial audio services for networked virtual environments (NVEs) and distributed online games. Numerous challenging problems have to be overcome—among them providing low delay, resilience to churn, effective load balancing, and rapid convergence—in such dynamic environments. We propose a novel P2P overlay dissemination mechanism, termed IDM, that can satisfy such demanding real-time requirements. Our target application is to provide spatialized voice support in multiplayer NVEs, where each bandwidth constrained peer potentially communicates with all other peers within its area-of-interest (AoI). With IDM each peer maintains a set of partners, termed helpers, which may act as stream forwarders. We prove analytically that the system reachability is maximized when the loads of helpers are balanced proportionally to their network capacities. We then propose a game-theoretic algorithm that balances the loads of the peers in a fully distributed manner. Of practical importance in dynamic systems, we prove that our algorithm converges to an approximately balanced state from any prior state in rapid O(log log n) time, where n is the number of users. We further evaluate our technique with simulations and show that it can achieve near optimal system reachability and satisfy the tight latency constraints of interactive audio under conditions of churn, avatar mobility, and heterogeneous user access network bandwidth.

Gaussian versus Uniform Distribution for Intrusion Detection inWireless Sensor Networks

Abstract

In a Wireless Sensor Network (WSN), intrusion detection is of significant importance in many applications in detecting malicious or unexpected intruder(s). The intruder can be an enemy in a battlefield, or a malicious moving object in the area of interest. With uniform sensor deployment, the detection probability is the same for any point in a WSN. However, some applications may require different degrees of detection probability at different locations. For example, an intrusion detection application may need improved detection probability around important entities. Gaussian-distributed WSNs can provide differentiated detection capabilities at different locations but related work is limited. This paper analyzes the problem of intrusion detection in a Gaussian-distributed WSN by characterizing the detection probability with respect to the application requirements and the network parameters under both single-sensing detection and multiple-sensing detection scenarios. Effects of different network parameters on the detection probability are examined in detail. Furthermore, performance of Gaussian-distributed WSNs is compared with uniformly distributed WSNs. This work allows us to analytically formulate detection probability in a random WSN and provides guidelines in selecting an appropriate deployment strategy and determining critical network parameters.

Fast Channel Zapping with Destination-Oriented Multicast for IP VideoDelivery

Abstract

Channel zapping time is a critical quality of experience (QoE) metric for IP-based video delivery systems such as IPTV. An interesting zapping acceleration scheme based on time-shifted subchannels (TSS) was recently proposed, which can ensure a zapping delay bound as well as maintain the picture quality during zapping. However, the behaviors of the TSS-based scheme have not been fully studied yet. Furthermore, the existing TSS-based implementation adopts the traditional IP multicast, which is not scalable for a large-scale distributed system. Corresponding to such issues, this paper makes contributions in two aspects. First, we resort to theoretical analysis to understand the fundamental properties of the TSS-based service model. We show that there exists an optimal subchannel data rate which minimizes the redundant traffic transmitted over subchannels. Moreover, we reveal a start-up effect, where the existing operation pattern in the TSS-based model could violate the zapping delay bound. With a solution proposed to resolve the start-up effect, we rigorously prove that a zapping delay bound equal to the subchannel time shift is guaranteed by the updated TSS-based model. Second, we propose a destination-oriented-multicast (DOM) assisted zapping acceleration (DAZA) scheme for a scalable TSS-based implementation, where a subscriber can seamlessly migrate from a subchannel to the main channel after zapping without any control message exchange over the network. Moreover, the subchannel selection in DAZA is independent of the zapping request signaling delay, resulting in improved robustness and reduced messaging overhead in a distributed environment. We implement DAZA in ns-2 and multicast an MPEG-4 video stream over a practical network topology. Extensive simulation results are presented to demonstrate the validity of our analysis and DAZA scheme.

Exploiting Ubiquitous Data Collection for Mobile Users in WirelessSensor Networks

Abstract

We study the ubiquitous data collection for mobile users in wireless sensor networks. People with handheld devices can easily interact with the network and collect data. We propose a novel approach for mobile users to collect the network-wide data. The routing structure of data collection is additively updated with the movement of the mobile user. With this approach, we only perform a limited modification to update the routing structure while the routing performance is bounded and controlled compared to the optimal performance. The proposed protocol is easy to implement. Our analysis shows that the proposed approach is scalable in maintenance overheads, performs efficiently in the routing performance, and provides continuous data delivery during the user movement. We implement the proposed protocol in a prototype system and test its feasibility and applicability by a 49-node testbed. We further conduct extensive simulations to examine the efficiency and scalability of our protocol with varied network settings.

Dynamic Coverage of Mobile Sensor Networks

Abstract

We study the dynamic aspects of the coverage of a mobile sensor network resulting from continuous movement of sensors. As sensors move around, initially uncovered locations may be covered at a later time, and intruders that might never be detected in a stationary sensor network can now be detected by moving sensors. However, this improvement in coverage is achieved at the cost that a location is covered only part of the time, alternating between covered and not covered. We characterize area coverage at specific time instants and during time intervals, as well as the time durations that a location is covered and uncovered. We further consider the time it takes to detect a randomly located intruder and prove that the detection time is exponentially distributed with parameter 2lambda r bar{v}_s where lambda represents the sensor density, r represents the sensor's sensing range, and bar{v}_s denotes the average sensor speed. For mobile intruders, we take a game theoretic approach and derive optimal mobility strategies for both sensors and intruders. We prove that the optimal sensor strategy is to choose their directions uniformly at random between [0, 2pi ). The optimal intruder strategy is to remain stationary. This solution represents a mixed strategy which is a Nash equilibrium of the zero-sum game between mobile sensors and intruders.

Distributed k-Core Decomposition

Abstract

Several novel metrics have been proposed in recent literature in order to study the relative importance of nodes in complex networks. Among those, k-coreness has found a number of applications in areas as diverse as sociology, proteinomics, graph visualization, and distributed system analysis and design. This paper proposes new distributed algorithms for the computation of the k-coreness of a network, a process also known as k-core decomposition. This technique 1) allows the decomposition, over a set of connected machines, of very large graphs, when size does not allow storing and processing them on a single host, and 2) enables the runtime computation of k-cores in “live” distributed systems. Lower bounds on the algorithms complexity are given, and an exhaustive experimental analysis on real-world data sets is provided.

Distributed Data Replenishment

Abstract

We propose a distributed data replenishment mechanism for some distributed peer-to-peer-based storage systems that automates the process of maintaining a sufficient level of data redundancy to ensure the availability of data in presence of peer departures and failures. The dynamics of peers entering and leaving the network are modeled as a stochastic process. A novel analytical time-backward technique is proposed to bound the expected time for a piece of data to remain in P2P systems. Both theoretical and simulation results are in agreement, indicating that the data replenishment via random linear network coding (RLNC) outperforms other popular strategies. Specifically, we show that the expected time for a piece of data to remain in a P2P system, the longer the better, is exponential in the number of peers used to store the data for the RLNC-based strategy, while they are quadratic for other strategies.

Cross-Layer Design of Congestion Control and Power Control inFast-Fading Wireless Networks

Abstract

We study the cross-layer design of congestion control and power allocation with outage constraint in an interference-limited multihop wireless networks. Using a complete-convexification method, we first propose a message-passing distributed algorithm that can attain the global optimal source rate and link power allocation. Despite the attractiveness of its optimality, this algorithm requires larger message size than that of the conventional scheme, which increases network overheads. Using the bounds on outage probability, we map the outage constraint to an SIR constraint and continue developing a practical near-optimal distributed algorithm requiring only local SIR measurement at link receivers to limit the size of the message. Due to the complicated complete-convexification method, however the congestion control of both algorithms no longer preserves the existing TCP stack. To take into account the TCP stack preserving property, we propose the third algorithm using a successive convex approximation method to iteratively transform the original nonconvex problem into approximated convex problems, then the global optimal solution can converge distributively with message-passing. Thanks to the tightness of the bounds and successive approximations, numerical results show that the gap between three algorithms is almost indistinguishable. Despite the same type of the complete-convexification method, the numerical comparison shows that the second near-optimal scheme has a faster convergence rate than that of the first optimal one, which make the near-optimal scheme more favorable and applicable in practice. Meanwhile, the third optimal scheme also has a faster convergence rate than that of a previous work using logarithm successive approximation method.

Coloring-Based Inter-WBAN Scheduling for Mobile Wireless Body AreaNetworks

Abstract

In this study, random incomplete coloring (RIC) with low time-complexity and high spatial reuse is proposed to overcome in-between wireless-body-area-networks (WBAN) interference, which can cause serious throughput degradation and energy waste. Interference-avoidance scheduling of wireless networks can be modeled as a problem of graph coloring. For instance, high spatial-reuse scheduling for a dense sensor network is mapped to high spatial-reuse coloring; fast convergence scheduling for a mobile ad hoc network (MANET) is mapped to low time-complexity coloring. However, for a dense and mobile WBAN, inter-WBAN scheduling (IWS) should simultaneously satisfy both of the following requirements: 1) high spatial-reuse and 2) fast convergence, which are tradeoffs in conventional coloring. By relaxing the coloring rule, the proposed distributed coloring algorithm RIC avoids this tradeoff and satisfies both requirements. Simulation results verify that the proposed coloring algorithm effectively overcomes inter-WBAN interference and invariably supports higher system throughput in various mobile WBAN scenarios compared to conventional colorings.

Cluster-Based Certificate Revocation with Vindication Capability forMobile Ad Hoc Networks

Abstract

Mobile ad hoc networks (MANETs) have attracted much attention due to their mobility and ease of deployment. However, the wireless and dynamic natures render them more vulnerable to various types of security attacks than the wired networks. The major challenge is to guarantee secure network services. To meet this challenge, certificate revocation is an important integral component to secure network communications. In this paper, we focus on the issue of certificate revocation to isolate attackers from further participating in network activities. For quick and accurate certificate revocation, we propose the Cluster-based Certificate Revocation with Vindication Capability (CCRVC) scheme. In particular, to improve the reliability of the scheme, we recover the warned nodes to take part in the certificate revocation process; to enhance the accuracy, we propose the threshold-based mechanism to assess and vindicate warned nodes as legitimate nodes or not, before recovering them. The performances of our scheme are evaluated by both numerical and simulation analysis. Extensive results demonstrate that the proposed certificate revocation scheme is effective and efficient to guarantee secure communications in mobile ad hoc networks.

Analysis of Distance-Based Location Management in WirelessCommunication Networks

Abstract

The performance of dynamic distance-based location management schemes (DBLMS) in wireless communication networks is analyzed. A Markov chain is developed as a mobility model to describe the movement of a mobile terminal in 2D cellular structures. The paging area residence time is characterized for arbitrary cell residence time by using the Markov chain. The expected number of paging area boundary crossings and the cost of the distance-based location update method are analyzed by using the classical renewal theory for two different call handling models. For the call plus location update model, two cases are considered. In the first case, the intercall time has an arbitrary distribution and the cell residence time has an exponential distribution. In the second case, the intercall time has a hyper-Erlang distribution and the cell residence time has an arbitrary distribution. For the call without location update model, both intercall time and cell residence time can have arbitrary distributions. Our analysis makes it possible to find the optimal distance threshold that minimizes the total cost of location management in a DBLMS.