Benefit-Based Data Caching in Ad Hoc Networks

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.     

Preference-aware coding data broadcast in delay tolerant networks

Traditional data broadcasting schemes in delay tolerant networks assume that mobile users can only retrieve one data item in each time slot. In this paper, we propose a novel data broadcasting framework in the delay tolerant networks that exploits the concept of network coding to mix the delivered data items according to the user’s stored data items. Our approach enables a user to encode multiple data items dynamically in each time slot, and allows each user with a mobile device to retrieve a data item by using locally stored data items to decode the encoding data. Specifically, we design an algorithm called Preference-Aware Coding (PAC) to select the data items to be encoded in each time slot. The objective is to serve the maximal number of mobile users with the encoding data and minimize the access time required for data broadcasting in the delay tolerant networks. The algorithm avoids encoding unnecessary data in each time slot to reduce the access delay. We empirically implement the framework in the real delay tolerant networks, and simulation results show that the PAC algorithm can reduce the access time of the traditional scheme by 42 % on average.     

Supporting cooperative caching in ad hoc networks

Most researches in ad hoc networks focus on routing and not much work has been done on data access. A common technique used to improve the performance of data access is caching. Cooperative caching, which allows the sharing and coordination of cached data among multiple nodes, can further explore the potential of the caching techniques. Due to mobility and resource constraints of ad hoc networks, cooperative caching techniques designed for wired networks may not be applicable to ad hoc networks. In this paper, we design and evaluate cooperative caching techniques to efficiently support data access in ad hoc networks. We first propose two schemes: CacheData, which caches the data, and CachePath, which caches the data path. After analyzing the performance of those two schemes, we propose a hybrid approach (HybridCache), which can further improve the performance by taking advantage of CacheData and CachePath while avoiding their weaknesses. Cache replacement policies are also studied to further improve the performance. Simulation results show that the proposed schemes can significantly reduce the query delay and message complexity when compared to other caching schemes.     

Minimum-energy all-to-all multicasting in wireless ad hoc networks

A wireless ad hoc network consists of mobile nodes that are powered by batteries. The limited battery lifetime imposes a severe constraint on the network performance, energy conservation in such a network thus is of paramount importance, and energy efficient operations are critical to prolong the lifetime of the network. All-to-all multicasting is one fundamental operation in wireless ad hoc networks, in this paper we focus on the design of energy efficient routing algorithms for this operation. Specifically, we consider the following minimum-energy all-to-all multicasting problem. Given an all-to-all multicast session consisting of a set of terminal nodes in a wireless ad hoc network, where the transmission power of each node is either fixed or adjustable, assume that each terminal node has a message to share with each other, the problem is to build a shared multicast tree spanning all terminal nodes such that the total energy consumption of realizing the all-to-all multicast session by the tree is minimized. We first show that this problem is NP-Complete. We then devise approximation algorithms with guaranteed approximation ratios. We also provide a distributed implementation of the proposed algorithm. We finally conduct experiments by simulations to evaluate the performance of the proposed algorithm. The experimental results demonstrate that the proposed algorithm significantly outperforms all the other known algorithms.     

Design and analysis of asynchronous wakeup for wireless sensor networks

In wireless sensor networks, scheduling the sleep duration of each node is one of the key elements for controlling critical performance metrics such as energy consumption and latency. Since the wakeup interval is a primary parameter for determining the sleeping schedule, how to tune the wakeup interval is crucial for the overall network performance. In this paper, we present an effective framework for tuning asynchronous wakeup intervals of IEEE 802.15.4 sensor networks from the energy consumption viewpoint. First, we derive an energy consumption model of each node as an explicit function of the wakeup interval, and empirically validate the derived model. Second, based on the proposed model, we formulate the problem of tuning the wakeup interval with the following two objectives: to minimize total energy consumption and to maximize network lifetime. We show that these two problems can be optimally solved by an iterative algorithm with global information by virtue of the convexity of the problem structure. Finally, as practical solutions, we further propose heuristic optimization algorithms that only exploit local information. In order to develop heuristic algorithms, we propose two broadcasting schemes, which are entitled as maximum wakeup interval broadcasting and efficient local maximum broadcasting. These broadcasting algorithms enable nodes in the network to have heterogeneous wakeup intervals.     

Egocentric network focused community aware multicast routing for DTNs

Multicasting for delay-tolerant networks (DTNs) in sparse social network scenarios is a challenge due to the deficiency of end-to-end paths. In social network scenarios, the behaviors of their nodes are controlled by human beings, and node mobility is the same as that of humans. To design the multicasting algorithms for DTNs, therefore, it would be promising to capture the intrinsic characteristics of relationships among these nodes. In this paper, multicasting in DTNs is regarded as a message dissemination issue in social networks, and an egocentric network focused community aware multicast routing algorithm (ENCAR) is proposed. As distinct from some social-based routing algorithms which only focus on centrality analysis, ENCAR is an utility based and hierarchical routing algorithm, its utility function is constructed on the basis of centrality analysis and destination-oriented contact probability. We take notice of clustering phenomenon in social networks, and present the community aware forwarding schemes. In addition, to simulate the mobility of individuals in social networks, a novel community based random way point mobility model is also presented. In this paper, the performance of ENCAR is theoretically analyzed and further evaluated on simulator ONE. Simulation results show that ENCAR outperforms most of the existing multicast routing algorithms in routing overhead, on condition that delivery ratio is relatively high, with other significant parameters guaranteed to perform well.     

DFMAC: DTN-Friendly Medium Access Control for Wireless Local Area Networks Supporting Voice/Data Services

In this paper, we consider a wireless communication network for both local nodes residing in densely populated hot spots and nomadic nodes roaming in a large area. Wireless local area networks (WLANs) are deployed in the hot spots, while a delay/ disruption tolerant network (DTN) provides services to nomadic nodes in the large area with low node density. We investigate the radio resource allocation for a DTN/WLAN integrated network, and propose a DTN-friendly medium access control (DFMAC) scheme for the hot spots supporting voice/data services. Analytical models are established to characterize the interactions between a DTN and WLANs under the proposed DFMAC. Numerical and simulation results demonstrate that our proposed MAC scheme can provide a deterministic delay guarantee for the voice services of local nodes, while achieving an efficient performance tradeoff for the data services between nomadic nodes and local nodes.     

Extended bridge algorithms for large networks

A network bridge is a device that operates at the ISO data link level and routes packets across extended networks, commonly composed of multiple local area networks (LANs) and bridges. A set of algorithms that greatly extends the application of the network bridge is presented. This multitree bridge algorithm allows networks of arbitrary topology and capacity to use bridge routing. The reduced broadcast bridge algorithm alleviates the problem of extraneous broadcasting in large networks built from bridges and packet switches. A method for routing to network users who change their location rapidly, as in mobile cellular radio systems, is presented. An algorithm for efficient multicasting in bridges is given. Application of this technology to the broadband integrated services digital network (BISDN) is proposed     

Metadata-guided evaluation of resource-constrained queries in content caching based wireless networks

Recent years have witnessed the emergence of data-centric storage that provides energy-efficient data dissemination and organization in mobile wireless environments. However, limited resources of wireless devices bring unique challenges to data access and information sharing. To address these challenges, we introduce the concept of content caching networks, in which the collected data will be stored by its contents in a distributed manner, while the data in the network is cached for a certain period of time before it is sent to a centralized storage space for backup. Furthermore, we propose a metadata-guided query evaluation approach to achieve query efficiency in content caching networks. By this approach, each cache node will maintain the metadata that summarizes the data content on itself. Queries will be evaluated first on the metadata before on the cached data. By ensuring that queries will only be evaluated on relevant nodes, the metadata-guided query evaluation approach can dramatically improve the performance of query evaluation. We design efficient algorithms to construct metadata for both numerical and categorical data types. Our theoretical and empirical results both show that our metadata-guided approach can accelerate query evaluation significantly, while achieving the memory requirements on wireless devices.     

Routing in intermittent networks using storage domains

In this paper, we present a routing algorithm for a class of networks where a contemporaneous end‐to‐end path may not exist at the time of data transfer due to intermittent links. Several examples of such networks exist in the context of sensor networks, mobile ad hoc networks and delay tolerant networks. The proposed routing algorithms follow a priori routing similar to source routing. Link state changes are assumed to be known ahead of time, for instance, due to planned duty cycling resulting in scheduled connectivity. The basic idea behind the proposed routing algorithms is to modify the breadth first search (BFS) algorithm to take into account link state changes and find the quickest route between source and destination nodes. We introduce the idea of time‐varying storage domains where all nodes connected for a length of time act as a single storage unit by sharing the aggregated storage capacity of the nodes. This will help situations where storage is a limited resource. We evaluate the routing algorithm with and without storage domain in an extensive simulation. The delay performance of the proposed algorithms is conceptually the same as flooding‐based algorithms but without the penalty of multiple copies. More significantly, we show that the Quickest Storage Domain (Quickest SD) algorithm distributes the storage demand across many nodes in the network topology, enabling balanced load and higher network utilization. In fact, we show that for the same level of performance, we can actually cut the storage requirement in half using the Quickest SD algorithm. Copyright © 2009 John Wiley & Sons, Ltd.     

A survey of data multicast techniques, architectures, andalgorithms

This article presents a survey of architectures, techniques, and algorithms for multicasting data in communication switching networks. We start with a broadcast architecture using a separate copy network and a routing network. A few versions of this idea using Delta and Benes networks exist. Another multicast architecture is a recycling network where internal nodes act as relay points, accept packets from the switching fabric, and recycle them back into the fabric after relabeling the packets. Next, we give an overview of a system that uses the Boolean splitting multicast algorithm. In this system a nonblocking self routing broadcast banyan copy network has been proposed. The network consists of several components including a running adder network to generate running sums of copy numbers specified in the headers of input packets. We then describe a multicasting technique presented for a different class of switching networks called deflection-routing networks. Finally, the idea of extending a nonblocking network to a three-dimensional structure consisting of multiple parallel planes is also presented. At the end of this article, we compare the efficiencies of the presented multicast architectures     

Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks

Wireless sensor networks （WSNs） consist of sensor nodes that broadcast a message within a network. Efficient broadcasting is a key requirement in sensor networks and has been a focal point of research over the last few years. There are many challenging tasks in the network, including redundancy control and sensor node localization that mainly depend on broadcasting. In this paper, we propose a broadcasting algorithm to control redundancy and improve localization （BACRIL） in WSNs. The proposed algorithm incorporates the benefits of the gossip protocol for optimizing message broadcasting within the network. Simulation results show a controlled level of redundancy, which is up to 57.6% if the number of sensor nodes deployed in a 500 m×500 m area are increased from 50 to 500.     

Virtual topologies for multicasting with multiple originators in WDM networks

In this paper, we consider the problem of multicasting with multiple originators in WDM optical networks. In this problem, we are given a set S of source nodes and a set D of destination nodes in a network. All source nodes are capable of providing data to any destination node. Our objective is to find a virtual topology in the WDM network which satisfies given constraints on available resources and is optimal with respect to minimizing the maximum hop distance. Although the corresponding decision problem is NP-complete in general, we give polynomial time algorithms for the cases of unidirectional paths and rings.     

Impairment constraint multicasting in translucent WDM networks: architecture, network design and multicasting routing

The popularity of broadband streaming applications requires communication networks to support high-performance multicasting at the optical layer. Suffering from transmission impairments in multi-hop all-optical (transparent) WDM multicasting networks, the signal may be degraded beyond the receivable margin at some multicast destinations. To guarantee the signal quality, we introduce a translucent WDM multicasting network to regenerate the degraded signals at some switching nodes with electronic 3R (reamplification, reshaping and retiming) functionality. The translucent network is built by employing three kinds of multicasting capable switching architectures: (1) all-optical multicasting capable cross connect (oMC-OXC), (2) electronic switch and (3) translucent multicasting capable cross connect (tMC-OXC). Among them both the electronic switch and tMC-OXC are capable of electronic 3R regeneration. Furthermore, we propose a multicast-capable nodes placement algorithm based on regeneration weight, and two multicasting routing algorithms called nearest hub first and nearest on tree hub first to provide signal-quality guaranteed routes for the multicasting requests. The numerical simulation on two typical mesh networks shows that it is sufficient to equip 30% of the nodes or less with signal-regeneration capability to guarantee the signal quality.     

Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks

Network wide broadcasting is a fundamental operation in ad hoc networks. In broadcasting, a source node sends a message to all the other nodes in the network. In this paper, we consider the problem of collision-free broadcasting in ad hoc networks. Our objective is to minimize the latency and the number of transmissions in the broadcast. We show that minimum latency broadcasting is NP-complete for ad hoc networks. We also present a simple distributed collision-free broadcasting algorithm for broadcasting a message. For networks with bounded node transmission ranges, our algorithm simultaneously guarantees that the latency and the number of transmissions are within $O(1)$ times their respective optimal values. Our algorithm and analysis extend to the case when multiple messages are broadcast from multiple sources. Experimental studies indicate that our algorithms perform much better in practice than the analytical guarantees provided for the worst case.      

Efficient Cache Placement in Multi-Hop Wireless Networks

In this paper, we address the problem of efficient cache placement in multi-hop wireless networks. We consider a network comprising a server with an interface to the wired network, and other nodes requiring access to the information stored at the server. In order to reduce access latency in such a communication environment, an effective strategy is caching the server information at some of the nodes distributed across the network. Caching, however, can imply a considerable overhead cost; for instance, disseminating information incurs additional energy as well as bandwidth burden. Since wireless systems are plagued by scarcity of available energy and bandwidth, we need to design caching strategies that optimally trade-off between overhead cost and access latency. We pose our problem as an integer linear program. We show that this problem is the same as a special case of the connected facility location problem, which is known to be NP-hard. We devise a polynomial time algorithm which provides a suboptimal solution. The proposed algorithm applies to any arbitrary network topology and can be implemented in a distributed and asynchronous manner. In the case of a tree topology, our algorithm gives the optimal solution. In the case of an arbitrary topology, it finds a feasible solution with an objective function value within a factor of 6 of the optimal value. This performance is very close to the best approximate solution known today, which is obtained in a centralized manner. We compare the performance of our algorithm against three candidate cache placement schemes, and show via extensive simulation that our algorithm consistently outperforms these alternative schemes.     

A foresighted strategy for greed-based multicasting algorithms in all-optical mesh networks

For abundant bandwidth, all-optical mesh networks have been more and more important in communications, and multicasting is one of the key technologies to that. The problem to find a minimum multicasting tree is NP-hard, and all the existing algorithms are heuristics. Most of them are based on the idea of being greed. A greedy idea is always shortsighted. While it could get a good local effect, it would obtain a somewhat bad global performance. In this article, we propose a foresighted strategy for greed-based multicasting algorithms. With the co-action of the greedy idea and a foresighted strategy, a multicasting algorithm can get a good local and global performance simultaneously. We introduce the strategy by embedding it in the Member-Only algorithm and investigate two indexes, the average cost of all multicasting requests and the blocking rate of the whole network. Simulation results show that, with the presence of the proposed foresighted strategy, these two targets are all obviously decreased.     

Congestion management techniques for disruption‐tolerant satellite networks

Delay and disruption‐tolerant networks are becoming an appealing solution for extending Internet boundaries toward challenged environments where end‐to‐end connectivity cannot be guaranteed. In particular, satellite networks can take advantage of a priori trajectory estimations of nodes to make efficient routing decisions. Despite this knowledge is already used in routing schemes such as contact graph routing, it might derive in congestion problems because of capacity overbooking of forthcoming connections (contacts). In this work, we initially extend contact graph routing to provide enhanced congestion mitigation capabilities by taking advantage of the local traffic information available at each node. However, since satellite networks data generation is generally managed by a mission operation center, a global view of the traffic can also be exploited to further improve the latter scheme. As a result, we present a novel strategy to avoid congestion in predictable delay‐ and disruption‐tolerant network systems by means of individual contact plans. Finally, we evaluate and compare the performance improvement of these mechanisms in a typical low Earth orbit satellite constellation.     

Dynamic group multicast routing with bandwidth reservations

Multicasting refers to the transmission of data from a source node to multiple destination nodes in a network. Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belong to the same group. The routing problem in this case involves the construction of a set of low cost multicast trees with bandwidth requirements, one for each member of the group for multicasting messages to other members of the group. In this paper, we examine this routing problem with an additional requirement that member nodes are allowed to join and leave the multicasting group anytime during a session. We call this problem, the dynamic group multicast routing problem (DGMRP). In this paper, we proposed three heuristic algorithms to generate a set of low cost multicast trees with dynamic group membership. Results from our empirical study shows that the one of the proposed algorithms, called Maximum bandwidth bottleneck path selection algorithm (MBBPS), achieves better utilization of bandwidth resources as compared with the other two algorithms which are based on a greedy approach. In addition MBBPS performs better in terms of cost when the bandwidth is not sufficient in the network. Copyright © 2002 John Wiley & Sons, Ltd.