Directional broadcast for mobile ad hoc networks with percolation theory

For mobile ad hoc networks, network-wide broadcast is a critical network layer function supporting route discovery and maintenance in many unicast and multicast protocols. A number of broadcast schemes have been proposed; however, almost all of them assume the usage of omnidirectional antennas and focus on broadcast overhead in terms of the number of forwarding nodes. Directional antennas have narrow beams and can potentially reduce broadcast overhead in terms of the ratio of the number of received duplicate packets to the number of nodes that receive broadcast packets. In this paper, we propose to map probability-based directional and omnidirectional broadcast to bond and site percolation, respectively, and describe a collection of directional antenna-based broadcast schemes for mobile ad hoc networks. A thorough and comparative simulation study is conducted to demonstrate the efficiency of the proposed schemes.     

Discovering timely information in MANETs

Timely information refers to information whose ‘most recent’ or ‘latest’ instance is most valuable. In mobile ad hoc networks (MANETs), multiple instances of a piece of timely information may be produced by different nodes at different points in time. The problem is to discover the ‘latest’ instance among all existing instances. Within the context of MANETs, timely information discovery is fundamentally different from the existing resource/service discovery problem whose goal is to discover either any instance or a subset of instances which satisfy a local query constraint that can be specified and evaluated using only local attributes of each individual node. In contrast, the timely information discovery problem imposes the global (timeliness) constraint which should best be evaluated when all the instances are considered to determine the latest instance. The complication of discovering timely information arises from the existence of multiple instances of the information, which are produced at different points in time by different nodes in the network, and the need to collect all these instances to decide the latest instance. For MANETs, the lack of infrastructure supports, frequent topology changes, and potential packet loss in wireless communications further challenge the problem of timely information discovery. This paper describes a self-organizing, peer-to-peer based approach, termed ALADIN, to discovering timely information in MANETs. In ALADIN, nodes that produce instances of the timely information are peers who self-organize an adaptive and distributed ‘search infrastructure’ to facilitate the discovery of the latest instance. A simulation study shows that ALADIN is scalable without incurring network-wide flooding in the case of large-scale networks and popular timely information, and yields a high chance of discovering the latest instance in the presence of mobility.     

Multicast Communication in Ad Hoc Networks with Directional Antennas

This paper investigates the benefits and impacts of using directional antennas for multicast communications in ad hoc networks. In terms of signal reception, directional antennas have shown considerable improvement in the performance of all aspects over omni-directional antennas, especially over dense networks with heavy traffic load. In addition, we have found that transmitting multicast packets directionally to known neighboring group members or forwarders can help reduce the average end-to-end packet delay and increase the overall throughput. However, directional transmission of unacknowledged data transfers may result in lower performance in terms of packet delivery ratio than omni-directional transmission in any carrier sensing MAC protocols under moderate load due to the effect from the hidden terminal problem. Both analytical results and simulation results, as well as an acknowledgment mechanism to improve the successful delivery rate of multicast data packets, are presented. Prepared through collaborative participation in the Communications and Networks Consortium sponsored by the U.S. Army Research Laboratory under the Collaborative Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation thereon.     

Querying time indexed information in mobile Ad hoc networks

Time indexed information refers to information whose instance producing time is used as the search key for its access. One common scenario of querying time indexed information is to discover the information instance whose producing time is the closest to a given queried time. However, in the context of mobile ad hoc networks (MANETs), lack of infrastructure support, node mobility, and potential packet loss in wireless communications make querying time indexed information a challenging task. This paper describes a Self-Organizing Mechanism for querying Time indexed Information in MANETs, termed SOMTI. Using SOMTI, each instance producer h discovers routes to a set of instance producers whose instance producing times are the closest to a set of computed time points both before and after h’s instance producing time. These routes form a web of search indices, which allow queries received by any instance producer to be forwarded in the manner of n-ary search for the instance producer whose instance producing time is the closest to the queried time. Both mathematical analysis and simulation study show that SOMTI is scalable with the number of nodes and the query producing rate. In addition, simulations results demonstrate that the goodness, in terms of the closeness to the queried time, of the discovered instance is always better than competing approaches under various node mobility speeds, query generation rates, and the number of nodes in the network, which demonstrates the effectiveness of SOMTI.     

Ad Hoc Multicast Routing Algorithm with Swarm Intelligence

Swarm intelligence refers to complex behaviors that arise from very simple individual behaviors and interactions, which is often observed in nature, especially among social insects such as ants. Although each individual (an ant) has little intelligence and simply follows basic rules using local information obtained from the environment, such as ant's pheromone trail laying and following behavior, globally optimized behaviors, such as finding a shortest path, emerge when they work collectively as a group. In this paper, we apply this biologically inspired metaphor to the multicast routing problem in mobile ad hoc networks. Our proposed multicast protocol adapts a core-based approach which establishes multicast connectivity among members through a designated node (core). An initial multicast connection can be rapidly setup by having the core flood the network with an announcement so that nodes on the reverse paths to the core will be requested by group members to serve as forwarding nodes. In addition, each member who is not the core periodically deploys a small packet that behaves like an ant to opportunistically explore different paths to the core. This exploration mechanism enables the protocol to discover new forwarding nodes that yield lower total forwarding costs, where cost is abstract and can be used to represent any metric to suit the application. Simulations have been conducted to demonstrate the performance of the proposed approach and to compare it with certain existing multicast protocols.     

Ant-Based Distributed Topology Control Algorithms for Mobile Ad hoc Networks

By adjusting the transmission power of mobile nodes, topology control aims to reduce wireless interference, reduce energy consumption, and increase effective network capacity, subject to connectivity constraints. In this paper, we introduce the Ant-Based Topology Control (ABTC) algorithm that adapts the biological metaphor of Swarm Intelligence to control topology of mobile ad hoc networks. ABTC is a distributed algorithm where each node asynchronously collects local information from nearby nodes, via sending and receiving ant packets, to determine its appropriate transmission power. The operations of ABTC do not require any geographical location, angle-of-arrival, topology, or routing information, and are scalable. In particular, ABTC attempts to minimize the maximum power used by any node in the network, or minimize the total power used by all of the nodes in the network. By adapting swarm intelligence as an adaptive search mechanism, ABTC converges quickly to a good power assignment with respect to minimization objectives, and adapts well to mobility. In addition, ABTC may achieve common power, or properly assign power to nodes with non-uniform distribution. Results from a thorough comparative simulation study demonstrate the effectiveness of ABTC for different mobility speed, various density, and diverse node distributions.This work is supported in part by National Science Foundation under grant ANI-0240398.Chien-Chung Shen received his B.S. and M.S. degrees from National Chiao Tung University, Taiwan, and his Ph.D. degree from UCLA, all in computer science. He was a research scientist at Bellcore Applied Research working on control and management of broadband networks. He is now an assistant professor in the Department of Computer and Information Sciences of the University of Delaware, and a recipient of NSF CAREER Award. His research interests include ad hoc and sensor networks, control and management of broadband networks, distributed object and peer-to-peer computing, and simulation.Zhuochuan Huang received his B.E. degree in Computer Science and Technology from Tsinghua University, P.R. China, in 1998, and his M.S. degree in Computer Science from University of Delaware in 2000. He is currently a PhD candidate with the Department of Computer and Information Sciences at the University of Delaware. His current research interests include the design and simulation of protocols for mobile ad hoc networks.Chaiporn Jaikaeo received his B.Eng degree in computer engineering from Kasetsart University, Thailand, and his M.S. and Ph.D. degrees in computer and information sciences from the University of Delaware in 1996, 1999 and 2004, respectively. He is currently a lecturer in the Department of Computer Engineering at Kasetsart University. His research interests include unicast and multicast routing, topology control, peer-to-peer computing and network management for mobile wireless ad hoc and sensor networks.