Location aware, dependable multicast for mobile ad hoc networks

This paper introduces dynamic source multicast (DSM), a new protocol for multi-hop wireless (i.e., ad hoc) networks for the multicast of a data packet from a source node to a group of mobile nodes in the network. The protocol assumes that, through the use of positioning system devices, each node knows its own geographic location and the current (global) time, and it is able to efficiently spread these measures to all other nodes. When a packet is to be multicast, the source node first locally computes a snapshot of the complete network topology from the collected node measures. A Steiner (i.e., multicast) tree for the addressed multicast group is then computed locally based on the snapshot, rather than maintained in a distributed manner. The resulting Steiner tree is then optimally encoded by using its unique Pr

Full-size image

u" height="11" width="9">fer sequence and is included in the packet header as in, and extending the length of the header by no more than, the header of packets in source routing (unicast) techniques. We show that all the local computations are executed in polynomial time. More specifically, the time complexity of the local operation of finding a Steiner tree, and the encoding/decoding procedures of the related Prüfer sequence, is proven to be O(n²), where n is the number of nodes in the network. The protocol has been simulated in ad hoc networks with 30 and 60 nodes and with different multicast group sizes. We show that DSM delivers packets to all the nodes in a destination group in more than 90% of the cases. Furthermore, compared to flooding, DSM achieves improvements of up to 50% on multicast completion delay.     

Improving routing distance for geographic multicast with Fermat points in mobile ad hoc networks

In mobile ad hoc networks (MANETs), each node has the ability to transmit, receive, and route packets, and also moves through the field either randomly or in accordance with a pre-planned route. For enhancing the performance of MANETs, reducing the routing distance is a primary concern. For either ad hoc or static networks, the problem of minimizing the overall routing distance during multicasting is NP-complete. Therefore, it is difficult to determine an optimal solution. This paper presents an efficient geographic multicast protocol, designated as GMFP, based on the use of Fermat points. The objective of GMFP is to improve the overall routing distance for multicast tasks. Through a series of simulations, it is shown that GMFP outperforms the conventional Position-Based Multicast protocol and FERMA protocol in terms of the total routing distance, the packet transmission delay, the packet delivery ratio, and the node energy consumption. The performance improvements provided by GMFP are apparent as the scale of the network topology increases.     

A fault tolerant mutual exclusion algorithm for mobile ad hoc networks

In this paper, we propose a permission-based message efficient mutual exclusion (MUTEX) algorithm for mobile ad hoc networks (MANETs). To reduce messages cost, the algorithm uses the “look-ahead” technique, which enforces MUTEX only among the hosts currently competing for the critical section. We propose mechanisms to handle dozes and disconnections of mobile hosts. The assumption of FIFO channel in the original “look-ahead” technique is also relaxed. The proposed algorithm can also tolerate link or host failures, using timeout-based mechanisms. Both analytical and simulation results show that the proposed algorithm works well under various conditions, especially when the mobility is high or load level is low. To our knowledge, this is the first permission-based MUTEX algorithm for MANETs.     

Review of multicast routing mechanisms in mobile ad hoc networks

Frequent interactions among the group members of distributed wireless network environment may be facilitated with the help of Mobile Ad Hoc NETworks (MANETs). Some of the group-oriented applications include disaster management, battlefields, audio/video conferencing, e-commerce, e-education, etc. Group communication demands dynamic construction of efficient and reliable multicast routes under user mobility and varying channel conditions. Multicast routing mechanisms in MANETs have been consistently improved by researchers considering various performance measures such as energy efficient route establishment, packet delivery ratio, quicker and faster proactive route recovery, network life time, reliability, Quality of Service (QoS) based on bandwidth, delays, jitters, and security. The paper focuses on most recent reliable and QoS based multicast routing mechanisms that helps in multimedia communication over MANETs. The mechanisms are considered under different topological routing categories such as mesh, tree, zone and hybrid. We provide an overview of existing multicast routing mechanisms based on routing categories and point to directions for future research and development.     

Performance evaluation of a mesh-evolving quality-of-service-aware multicast routing protocol for mobile ad hoc networks

The tremendous amount of multimedia applications running across the wireless communication medium makes quality of service (QoS) a fundamental requirement for mobile ad hoc networks. However, it is not easy to incorporate QoS into these networks. Moreover, the growing number of group-oriented applications also necessitates the efficient utilisation of network resources. The multicast model is a promising technique which can achieve this efficiency by facilitating the inherent broadcast capability of the wireless medium. The mesh-evolving ad hoc QoS multicast (MAQM) routing protocol is developed to address the resource efficiency and QoS problems with one, integrated solution. MAQM achieves multicast efficiency by tracking the availability of resources for each node within its neighbourhood. The QoS status is monitored continuously and announced periodically to the extent of QoS provision. Using these features, MAQM nodes can make their decisions on joining a new multicast session based on the sustainability of their perceived QoS. MAQM also evolves the initial multicast tree into a mesh during the course of an ongoing session to achieve a more robust network topology. Thus, MAQM integrates the concept of QoS-awareness into multicast routing in mobile ad hoc networks. Since ad hoc networks require the protocol control overhead to be as small as possible, we analyse the multicast session establishment process of MAQM to see its impact on the protocol performance in terms of system control overhead. We also evaluate the performance of MAQM through computer simulations using various qualitative and quantitative criteria. The simulation results validate our mathematical analysis of the control overhead and show that MAQM significantly improves multicast efficiency through its QoS-aware admission and routing decisions with an acceptably small overhead. Thus, MAQM shows that QoS is not only essential for, but also applicable to mobile ad hoc networks.     

Distributed dynamic mobile multicast

Traditional mobile multicast schemes have either high multicast tree reconfiguration cost or high packet delivery cost. The former affects service disruption time while the latter affects packet delivery delay. Although existing region-based mobile multicast schemes offer a trade-off between two costs to some extent, most of them do not determine the size of the service range, which is critical to network performance. In this paper, we propose a novel approach, called Distributed Dynamic Mobile Multicast (D²M²), to dynamically determine the optimal service range according to the mobility and service characteristics of a user. We derive an analytical model to formulate the costs of multicast tree reconfiguration and multicast packet delivery. The model is based on a Markov chain that analyzes a mobile node’s movement in a 2D mesh network. As the complexity of computing steady probability is high, we aggregate the Markov states by leveraging mobility symmetry. Simulation shows that the network performance is enhanced through D²M².     

Multicast routing in mobile ad hoc networks by using a multiagent system

Multicast routing in mobile ad hoc networks (MANETs) poses several challenges due to inherent characteristics of the network such as node mobility, reliability, scarce resources, etc. This paper proposes an Agent Based Multicast Routing Scheme (ABMRS) in MANETs, which uses a set of static and mobile agents. Five types of agents are used in the scheme: Route manager static agent, Network initiation mobile agent, Network management static agent, Multicast initiation mobile agent and Multicast management static agent. The scheme operates in the following steps: (1) to identify reliable nodes; (2) to connect reliable nodes through intermediate nodes; (3) to construct a backbone for multicasting using reliable nodes and intermediate nodes; (4) to join multicast group members to the backbone; (5) to perform backbone and group members management in case of mobility. The scheme has been simulated in various network scenarios to test operation effectiveness in terms of performance parameters such as packet delivery ratio, control overheads and group reliability. Also, a comparison of proposed scheme with MAODV (Multicast Ad hoc on-demand Distance Vector) protocol is presented. ABMRS performs better than MAODV as observed from the simulation. ABMRS offers flexible and adaptable multicast services and also supports component based software development.     

Energy efficient multicast routing in ad hoc wireless networks

In this paper, we discuss the energy efficient multicast problem in ad hoc wireless networks. Each node in the network is assumed to have a fixed level of transmission power. The problem of our concern is: given an ad hoc wireless network and a multicast request, how to find a multicast tree such that the total energy cost of the multicast tree is minimized. We first prove this problem is NP-hard and it is unlikely to have an approximation algorithm with a constant performance ratio of the number of nodes in the network. We then propose an algorithm based on the directed Steiner tree method that has a theoretically guaranteed approximation performance ratio. We also propose two efficient heuristics, node-join-tree (NJT) and tree-join-tree (TJT) algorithms. The NJT algorithm can be easily implemented in a distributed fashion. Extensive simulations have been conducted to compare with other methods and the results have shown significant improvement on energy efficiency of the proposed algorithms.     

Distributed Court System for intrusion detection in mobile ad hoc networks

Securing routing layer functions in mobile ad hoc networks is an important issue, which includes many challenges like how to enhance detection accuracy when facing the highly dynamic characteristic of such networks, and how to distinguish malicious accusations under a totally autonomous structure. In this paper, we propose Distributed Court System (DCS), a complete Intrusion Detection System that intends to solve these challenges in a low-cost and robust way. We do not deploy any centralized entity, but rely on the collaboration among the nodes neighbouring the suspected node, to integrate information, improve the detection accuracy, and reject dissemination of malicious accusation. Through mathematical analysis and simulation, the proposed DCS is proved to be effective in a highly mobile and hostile network environment.     

Cost-effective mobile ad hoc networks management

As there are more and more mobile devices in use, different mobile networking models such as ad hoc or mesh are attracting a large research interest. Self-organizing mobile ad hoc networks (MANET) allow devices to share their services and resources without any central administration or Internet support. In this respect they can become the backbone of the wireless grid or the gateway to existing grids. To achieve these goals, MANET management must be as effective as that of wired networks. This is, however, a challenging task due to network features like mobility, heterogeneity, limited resources of hosts and feeble communication. This paper presents a set of simple, cost-effective and resilient procedures for the basic tasks of MANET creation and management.     

基于链路稳定性的MANET组播路由协议

移动自组织网络环境中,选择稳定路由可以提高数据传输率并能有效降低控制信息减少网络拥塞。根据无线自组网的特点,提出了一种新颖的基于信号强度评价链路稳定性的方法,并且基于此方法构建组播路由协议。协议中节点能够根据信号强度预估链路稳定性,选择稳定路由,及时发现修复即将断开的链路。仿真结果表明,协议可以明显提高数据传输率,并且控制开销较低。     

Distributed debugging for mobile networks

Debuggers are an integral part, albeit often neglected, of the development of distributed applications. Ambient-oriented programming (AmOP) is a distributed paradigm for applications running on mobile ad hoc networks. In AmOP the complexity of programming in a distributed setting is married with the network fragility and open topology of mobile applications. To our knowledge, there is no debugging approach that tackles both these issues. In this paper we argue that a novel kind of distributed debugger that we term an ambient-oriented debugger, is required. We present REME-D (read as remedy), an online ambient-oriented debugger that integrates techniques from distributed debugging (event-based debugging, message breakpoints) and proposes facilities to deal with ad hoc, fragile networks – epidemic debugging, and support for frequent disconnections.     

Triangle-based routing for mobile ad hoc networks

Routing protocols for Mobile ad hoc networks (MANETs) have been studied extensively in the past decade. Routing protocols for MANETs can be broadly classified as reactive (on-demand), proactive, hybrid and position-based. Reactive routing protocols are attractive because a route between a source and a destination is established only when it is needed. Such protocols, unlike proactive protocols, do not have high overhead for route maintenance and are especially suitable for networks in which not all nodes communicate frequently. One problem with existing reactive routing protocols is the propagation of redundant route request messages during route discovery. In this paper, we present a low-overhead reactive routing protocol which reduces propagation of redundant route request messages. We also compare its performance with the well-known reactive routing protocol AODV.     

Acknowledged broadcasting in ad hoc radio networks

We consider ad hoc radio networks in which each node knows only its own identity but is unaware of the topology of the network, or of any bound on its size or diameter. Acknowledged broadcasting (AB) is a communication task consisting in transmitting a message from a distinguished source to all other nodes of the network and making this fact common knowledge among all nodes. To do this, the underlying directed graph must be strongly connected. Working in a model allowing all nodes to transmit spontaneously even before getting the source message, Chlebus et al. [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] proved that AB is impossible, if collision detection is not available, and gave an AB algorithm using collision detection that works in time O(nD) where n is the number of nodes and D is the eccentricity of the source. Uchida et al. [J. Uchida, W. Chen, K. Wada, Acknowledged broadcasting and gossiping in ad hoc radio networks, Theoret. Comput. Sci. 377 (2007) 43-54] showed an AB algorithm without collision detection working in time O(n4/3log10/3n) for all strongly connected networks of size at least 2. In particular, it follows that the impossibility result from [B. Chlebus, L. Ga?sieniec, A. Gibbons, A. Pelc, W. Rytter, Deterministic broadcasting in unknown radio networks, Distrib. Comput. 15 (2002) 27-38] is really caused by the singleton network for which AB amounts to realize that the source is alone. We improve those two results by presenting two generic AB algorithms using a broadcasting algorithm without acknowledgement, as a procedure. For a large class of broadcasting algorithms the resulting AB algorithm has the same time complexity. Using the currently best known broadcasting algorithms, we obtain an AB algorithm with collision detection working in time O(min{nlog²D,nlognloglogn}), for arbitrary strongly connected networks, and an AB algorithm without collision detection working in time O(nlognloglogn) for all strongly connected networks of size n?2. Moreover, we show that in the model in which only nodes that already got the source message can transmit, AB is infeasible in a strong sense: for any AB algorithm there exists an infinite family of networks for which this algorithm is incorrect.     

TCP-aware network coding with opportunistic scheduling in wireless mobile ad hoc networks

This paper presents a scheme that employs TCP-aware network coding with opportunistic scheduling to enhance TCP throughput in wireless mobile ad hoc networks. Specifically, it considers a TCP parameter, congestion window size, and wireless channel conditions simultaneously to improve TCP throughput performance. Evaluation of this scheme is carried out by using ns2 simulations in different scenarios. The results show that the proposed scheme gives approximately 35% throughput improvement in a high mobility environment and about 33% throughput increase in no or low mobility environment as compared to traditional network coding with opportunistic scheduling. This paper also proposes a new adaptive-W (i.e., adaptive Waiting time) scheme whose objective is to adaptively control waiting time of overheard packets that are stored in a buffer to achieve tradeoff between throughput and overhead.     

An evolutionary computation approach for designing mobile ad hoc networks

This paper presents the topological design of ad hoc networks in terms of distances among static nodes and speeds of mobiles nodes. Due to the complexity of the problem and the number of parameters to be considered, a genetic algorithm combined with the simulation environment NS-2 is proposed to find the optimum solution. More specifically, NS-2 provides the fitness function guiding the genetic search. The proposed framework has been tested using a railway scenario in which several static and mobile nodes are interacting. Results show the feasibility of the proposed framework and illustrate the possibility of genetic approach for solving similar application scenarios.     

Signal strength based routing for power saving in mobile ad hoc networks

The transmission bandwidth between two nodes in mobile ad hoc networks is important in terms of power consumption. However, the bandwidth between two nodes is always treated the same, regardless of what the distance is between the two nodes. If a node equips a GPS device to determine the distance between two nodes, the hardware cost and the power consumption increase. In this paper, we propose using a bandwidth-based power-aware routing protocol with signal detection instead of using GPS devices to determine the distance. In our proposed routing protocol, we use the received signal variation to predict the transmission bandwidth and the lifetime of a link. Accordingly, the possible amount of data that can be transmitted and the remaining power of nodes in the path after data transmission can be predicted. By predicting the possible amount of data that can be transmitted and the remaining power of nodes after data transmission, we can design a bandwidth-based power-aware routing protocol that has power efficiency and that prolongs network lifetime. In our simulation, we compare our proposed routing protocol with two signal-based routing protocols, SSA and ABR, and a power-aware routing protocol, MMBCR, in terms of the throughput, the average transmission bandwidth, the number of rerouting paths, the path lifetime, the power consumed when a byte is transmitted, and the network lifetime (the ratio of active nodes).     

A distributed fault identification protocol for wireless and mobile ad hoc networks

This paper considers the problem of self-diagnosis of wireless and mobile ad hoc networks (MANETs) using the comparison approach. In this approach, a network (MANET) consists of a collection of n   independent heterogeneous mobile or stationary hosts interconnected via wireless links, and it is assumed that at most σ$\sigma$ of these hosts are faulty. In order to diagnose the state of the MANET, tasks are assigned to pairs of hosts and the outcomes of these tasks are compared. The agreements and disagreements between the hosts are the basis for identifying the faulty ones. The comparison approach is believed to be one of the most practical fault identification approaches for diagnosing hard and soft faults. We develop a new distributed self-diagnosis protocol, called Dynamic-DSDP, for MANETs that identifies both hard and soft faults in a finite amount of time. The protocol is constructed on top of a reliable multi-hop architecture. Correctness and complexity proofs are provided and they show that our Dynamic-DSDP performs better, from a communication complexity viewpoint, than the existing protocols. We have also developed a simulator, that is scalable to a large number of nodes. Using the simulator, we carried out a simulation study to analyze the effectiveness of the self-diagnosis protocol and its performance with regards to the number of faulty hosts. The simulation results show that the proposed approach is an attractive and viable alternative or addition to present fault diagnosis techniques in MANET environments.     

The message delay in mobile ad hoc networks

A stochastic model is introduced that accurately models the message delay in mobile ad hoc networks where nodes relay messages and the networks are sparsely populated. The model has only two input parameters: the number of nodes and the parameter of an exponential distribution which describes the time until two random mobiles come within communication range of one another. Closed-form expressions are obtained for the Laplace–Stieltjes transform of the message delay, defined as the time needed to transfer a message between a source and a destination. From this we derive both a closed-form expression and an asymptotic approximation (as a function of the number of nodes) of the expected message delay. As an additional result, the probability distribution function is obtained for the number of copies of the message at the time the message is delivered. These calculations are carried out for two protocols: the two-hop multicopy and the unrestricted multicopy protocols. It is shown that despite its simplicity, the model accurately predicts the message delay for both relay strategies for a number of mobility models (the random waypoint, random direction and the random walker mobility models).     

Efficient implementations of all-to-all broadcasting in mobile ad hoc networks

In order to ease the challenging task of information dissemination in a MANET, we employ a legend: a data structure passed around a network to share information with all the mobile nodes. Our motivating application of the legend is sharing location information. Previous research shows that a simplistic legend performs better than other location services in the literature. To realize the full potential of legend-based location services, we propose three methods for the legend to traverse a network and compare their performance in simulation. Two of our proposed methods are novel, and the third is an improvement on an existing method. We also evaluate several general improvements to the traversal methods, and describe our way of making the legend transmission reliable. The result is a simple, lightweight location service that makes efficient use of network resources. Beyond using the legend as a location service, we discuss several implementation aspects of providing an efficient all-to-all broadcast operation, including legend reliability, preventing duplicate legends, using a legend in dynamic networks, and working with non-synchronized clocks. We also provide pseudocode for our legend traversal methods to aid implementation.