Search

In this paper, we consider the issue of data broadcasting in mobile social networks (MSNets). The objective is to broadcast data from a superuser to other users in the network. There are two main challenges under this paradigm, namely 1) how to represent and characterize user mobility in realistic MSNets; 2) given the knowledge of regular users' movements, how to design an efficient superuser route to broadcast data actively. We first explore several realistic data sets to reveal both geographic and social regularities of human mobility, and further propose the concepts of geocommunity and geocentrality into MSNet analysis. Then, we employ a semi-Markov process to model user mobility based on the geocommunity structure of the network. Correspondingly, the geocentrality indicating the “dynamic user density” of each geocommunity can be derived from the semi-Markov model. Finally, considering the geocentrality information, we provide different route algorithms to cater to the superuser that wants to either minimize total duration or maximize dissemination ratio. To the best of our knowledge, this work is the first to study data broadcasting in a realistic MSNet setting. Extensive trace-driven simulations show that our approach consistently outperforms other existing superuser route design algorithms in terms of dissemination ratio and energy efficiency. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the issue of efficient broadcasting in mobile ad hoc networks (MANET5) using network coding and directional antennas. Network coding-based broadcasting focuses on reducing the number of transmissions each forwarding node performs in the multiple source/multiple message broadcast application, where each forwarding node combines some of the received messages for transmission. With the help of network coding, the total number of transmissions can be reduced compared to broadcasting using the same forwarding nodes without coding. We exploit the usage of directional antennas to network coding-based broadcasting to further reduce energy consumption. A node equipped with directional antennas can divide the omnidirectional transmission range into several sectors and turn some of them on for transmission. In the proposed scheme using a directional antenna, forwarding nodes selected locally only need to transmit broadcast messages, original or coded, to restricted sectors. We also study two extensions. The first extension applies network coding to both dynamic and static forwarding node selection approaches. In the second extension, we design two approaches for the single source/single message issue in the network coding-based broadcast application. Performance analysis via simulations on the proposed algorithms using a custom simulator and ns2 is presented. [ABSTRACT FROM AUTHOR]

In this paper, we propose a family of structures, namely, κ-localized minimum spanning tree (LMSTκ) for topology control and broadcasting in wireless ad hoc networks. We give an efficient localized method to construct LMSTκ using only O(n) messages under the local-broadcast communication model, i.e., the signal sent by each node will be received by all nodes within the node's transmission range. We also analytically prove that the node degree of the structure LMSTκ is at most 6, LMSTκ is connected and planar and, more importantly, the total edge length of the LMSTk is within a constant factor of that of the minimum spanning tree when κ ≥ 2 (called low weighted hereafter). We then propose another low weighted structure, called Incident MST and RNG Graph (1MRG), that can be locally constructed using at most 13n messages under the local broadcast communication model. Test results are corroborated in the simulation study. We study the performance of our structures in terms of the total power consumption for broadcasting, the maximum node power needed to maintain the network connectivity. We theoretically prove that our structures are asymptotically the best possible for broadcasting among all locally constructed structures. Our simulations show that our new structures outperform previous locally constructed structures in terms of broadcasting and power assignment for connectivity. [ABSTRACT FROM AUTHOR]

Self-pruning is an effective scheme for efficient broadcasting in ad hoc wireless networks. In a self-pruning broadcast protocol, a node may not forward a broadcast packet if a certain self-pruning condition is satisfied based on the neighborhood information. In a static network with an ideal MAC layer, only a subset of nodes forward the broadcast packet and still guarantee the complete network delivery. Various protocols have been proposed with different self-pruning conditions. Recently, a generic self-pruning protocol was proposed by Wu and Dai [21], which combines the strength of previous conditions and is more effective. In this paper, we first propose an enhanced version of the generic protocol, which is more elegant in interpreting existing protocols and has a simpler correctness proof. Then, we evaluate the performance of the family of self-pruning protocols under various network situations with ns2. The objective is to observe the efficiency and reliability of these protocols as a function of network density, congestion, and mobility, and provide a guideline of implementation in the "real world." Our performance analysis reveals that the protocol reliability is barely affected by packet collision. However, most self-pruning protocols suffer from low delivery ratio in highly mobile networks. We further explore various techniques that improve the delivery ratio and show that both high efficiency and reliability can be achieved in highly mobile networks. [ABSTRACT FROM AUTHOR]

Our paper [1] generated a lot of interest among researchers in ad hoc networks. A number of researchers questioned, through their articles, or directly to the first author, the correctness of the described procedure, and the correctness of the claim that the procedure does not need any communication exchange between nodes, in addition to "hello" messages needed to learn information about neighboring nodes. This correspondence completes the article by providing the actual dominating set definitions used in the procedure (from which zero communication overhead follows easily), the correct procedure (the published one has few misprints at key places), and the proof that the new definitions and procedure indeed define connected dominating sets. [ABSTRACT FROM AUTHOR]

This paper presents a scalable and adaptive decentralized metadata lookup scheme for ultralarge-scale file systems (more than Petabytes or even Exabytes). Our scheme logically organizes metadata servers (MDSs) into a multilayered query hierarchy and exploits grouped Bloom filters to efficiently route metadata requests to desired MDSs through the hierarchy. This metadata lookup scheme can be executed at the network or memory speed, without being bounded by the performance of slow disks. An effective workload balance method is also developed in this paper for server reconfigurations. This scheme is evaluated through extensive trace-driven simulations and a prototype implementation in Linux. Experimental results show that this scheme can significantly improve metadata management scalability and query efficiency in ultralarge-scale storage systems. [ABSTRACT FROM AUTHOR]

Broadcast algorithms for the interlaced bypass torus networks (iBT networks) are introduced to balance the all-port bandwidth efficiency and to avoid congestion in multidimensional cases. With these algorithms, we numerically analyze the dependencies of the broadcast efficiencies on various packet-sending patterns, bypass schemes, network sizes, and dimensionalities and then strategically tune up the configurations for minimizing the broadcast steps. Leveraging on such analysis, we compare the performance of networks with one million nodes between two cases: one with an added fixed-length bypass links and the other with an added torus dimension. A case study of iBT( 1000^2 ;\schmi b =\langle 8,32\rangle) and Torus( 100^3 ) shows that the former improves the diameter, average node-to-node distance, rectangular and global broadcasts over the latter by approximately 80 percent. It is reaffirmed that strategically interlacing short bypass links and methodically utilizing these links is superior to adding dimensionalities to torus in achieving shorter diameter, average node-to-node distances and faster broadcasts. [ABSTRACT FROM PUBLISHER]

A robust group key agreement protocol (GKA) allows a set of players to establish a shared secret key, regardless of network/node failures. Current constant-round GKA protocols are either efficient and nonrobust or robust but not efficient; assuming a reliable broadcast communication medium, the standard encryption-based group key agreement protocol can be robust against arbitrary number of node faults, but the size of the messages broadcast by every player is proportional to the number of players. In contrast, nonrobust group key agreement can be achieved with each player broadcasting just constant-sized messages. We propose a novel 2-round group key agreement protocol, which tolerates up to T node failures, using O(T)-sized messages for any T. We show that the new protocol implies a fully-robust group key agreement with logarithmic-sized messages and expected round complexity close to 2, assuming random node faults. The protocol can be extended to withstand malicious insiders at small constant factor increases in bandwidth and computation. The proposed protocol is secure under the (standard) Decisional Square Diffie-Hellman assumption. [ABSTRACT FROM AUTHOR]