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.     

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.     

Distributed reformation of core-based group-shared multicast trees in mobile ad hoc networks

This paper proposes a method to reduce the cost of a core-based group-shared multicast tree, where the cost is evaluated by the total bandwidth consumption of multicasting packets among all group members. Due to the broadcast nature of radio transmissions, we find that the challenge of determining minimum cost multicast tree can be approximated by finding the multicast tree with a minimum number of non-leaves (the minimum non-leaf multicast tree problem). However, we also find that the minimum non-leaf multicast tree problem is NP-complete. Thus, a method is proposed to dynamically reduce the number of non-leaves in an existing multicast tree. Experimental results show that our method reduces the cost of the multicast tree in both geometrically and randomly distributed network models and the random waypoint mobility model.     

Self-stabilizing dynamic mutual exclusion for mobile ad hoc networks

We propose a self-stabilizing mutual exclusion algorithm for mobile ad hoc networks, in which the composition of processors that want to enter the critical section can change dynamically. Our algorithm is based on dynamic virtual rings formed by circulating tokens. The algorithm always guarantees mutual exclusion and it guarantees different levels of progress under different levels of performance of the token circulation in the presence of mobility and message loss. Rigorous proofs of correctness and performance are given.     

Space-efficient FCFS group mutual exclusion

In the group mutual exclusion problem [Y. Joung, Asynchronous group mutual exclusion, Distrib. Comput. 13 (2000) 189], which generalizes mutual exclusion [E. Dijkstra, Solution of a problem in concurrent programming control, Comm. ACM 8 (9) (1965) 569], a process chooses a session when it requests entry into the Critical Section. A group mutual exclusion algorithm must ensure that the mutual exclusion property holds: if two processes are in the Critical Section at the same time, then they request the same session. In addition to mutual exclusion, lockout freedom, bounded exit, and concurrent entering are basic properties that are desirable in any group mutual exclusion algorithm.Hadzilacos in [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106] first introduced a fairness condition, called first-come-first-served (FCFS), for group mutual exclusion. The only known FCFS group mutual exclusion algorithm is due to Hadzilacos [Proc. 20th Annual Symp. on Principles of Distributed Computing, 2001, pp. 100-106], and requires Θ(N²) bounded shared registers, where N is the number of processes. We present a FCFS group mutual exclusion algorithm that uses only Θ(N) bounded shared registers. (The existence of such an algorithm was posed as an open problem by Hadzilacos.)     

A hybrid token-based distributed mutual exclusion algorithm using wraparound two-dimensional array logical topology

In token-based distributed mutual exclusion algorithms a unique object (token) is used to grant the right to enter the critical section. For the movement of the token within the computer network, two possible methods can be considered: perpetual mobility of the token and token-asking method. This paper presents a distributed token-based algorithm scheduling mutually exclusive access to a critical resource by the processes in a distributed network. This network is composed of N nodes that communicate by message exchanges. The proposed hybrid algorithm imposes a logical structure in the form of wraparound two-dimensional array on the network. It applies the concept of perpetual mobility of the token in columns and token-asking in rows of the array. The major purpose of the algorithm is to increase the scalability property and decrease overhead due to additional communication in a system with at least one unresponded critical section request at any given time. In this status, typically, the number of message exchanges is between and under light demand and reduces to message exchanges under heavy demand. Therefore, it outperforms lots of well known algorithms in terms of number of messages exchanged. The algorithm satisfies safety and liveness properties.     

Maintaining a ring structure for mobile ad hoc computing

In a mobile ad hoc (multi-hop) wireless network, the logical structure of a ring is likely to become volatile or expensive to maintain over time due to changeable network topology. Additional adverse effects take place when a process joins or leaves the computation in the presence of mobility. This paper presents a distributed algorithm that adapts a ring among mobile nodes to the network dynamics to reflect overall communication efficiency. This is achieved by modifying the ring structure in a localized, mutual exclusive fashion, thereby allowing for concurrent segment-wise modifications to proceed. Remarkably our proposal operates without global knowledge of the logical structure and can be embodied as an underlying protocol stratum that supports transparent deployments of conventional algorithms in mobile environment. Subsequent to correctness proof, simulation results show that our proposal is promising in several regards.     

An election algorithm to ensure the high availability of leader in large mobile ad hoc networks

A fundamental problem of distributed systems, leader election, is presented in the context of mobile ad hoc networks (MANETs). In many distributed systems, the presence of a leader is necessary in order to monitor underlying computations, guarantee quality functioning, take checkpoints, generate the lost token, detect quiescence conditions, etc. Hence, several leader election algorithms have been proposed in the literature. Although, most of the algorithms focus on reducing the control message (messages that have the highest priority to deliver) count, there have been almost no attention on ensuring high availability of a leader despite various types of failures, especially, in the scenarios like rescue and warfare, where the absence of the leader, even for a short duration, may lead to havoc. We focus on this issue, particularly, for large MANETs, where a large number of applications fails to perform in the absence of a leader. We present a leader election algorithm for large MANETs. The algorithm is inspired by the concept of prevailing parliamentary democracy and elects three best-nodes – in terms of performance parameters like battery life, computing power, memory, hop distance, and mobility – as the president, leader, and vice leader. The president node works as the leader of the network, in case, the leader and the vice leader both become unavailable simultaneously. On the other hand, the leader node serves all the requests. Further, we create a house of elite nodes, which ensures the presence of an executive, i.e. a leader during re-election to restrict the message overhead as well as the election latency while executing coordination related activities.     

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.     

Building effective mutual exclusion services for grids

Taking into account the intrinsic heterogeneity of communication latency of grid environments, we propose in this article a composition approach that enables to build mutual exclusion services for grids. By using our approach, different intra and inter cluster token-based mutual exclusion algorithms can be combined easily. Performance evaluation tests were conducted on the French national grid testbed called Grid’5000, whose results show that our approach is effective and that the choice of the most suitable inter cluster algorithm depends on the behavior of the application.

(h,k)-Arbiters for h-out-of-k mutual exclusion problem

h-Out-of-k mutual exclusion is a generalization of the 1-mutual exclusion problem, where there are k units of shared resources and each process requests h (1hk) units at the same time. Though k-arbiter has been shown to be a quorum-based solution to this problem, quorums in k-arbiter are much larger than those in the 1-coterie for 1-mutual exclusion. Thus, the algorithm based on k-arbiter needs many messages. This paper introduces the new notion that each request uses different quorums depending on the number of units of its request. Based on the notion, this paper defines two (h,k)-arbiters for h-out-of-k mutual exclusion: a uniform (h,k)-arbiter and a (k+1)-cube (h,k)-arbiter. The quorums in each (h,k)-arbiter are not larger than the ones in the corresponding k-arbiter; consequently, it is more efficient to use (h,k)-arbiters than the k-arbiters. A uniform (h,k)-arbiter is a generalization of the majority coterie for 1-mutual exclusion. A (k+1)-cube (h,k)-arbiter is a generalization of square grid coterie for 1-mutual exclusion.     

Design and analysis of a fault tolerant hybrid mobile scheme

Mobile computing systems provide users with access to information regardless of their geographical location. In these systems, Mobile Support Stations (MSSs) play the role of providing reliable and uninterrupted communication and computing facilities to mobile hosts. The failure of a MSS can cause interruption of services provided by the mobile system. Two basic schemes for tolerating the failure of MSSs exist in the literature. The first scheme is based on the principle of checkpointing used in distributed systems. The second scheme is based on state information replication of mobile hosts in a number of secondary support stations. Depending on the replication scheme used, the second approach is further classified as a pessimistic or an optimistic technique. In this paper, we propose a hybrid scheme which combines the pessimistic and the optimistic replication schemes. In the proposed scheme, an attempt is made to strike a balance between the long delay caused by the pessimistic and the high memory requirements of the optimistic schemes. In order to find the best ratio between the number of pessimistic to the number of optimistic secondary stations in the proposed scheme, we used fuzzy logic. We also used simulation to compare the performance of the proposed scheme with those of the optimistic and the pessimistic schemes. Simulation results showed that the proposed scheme performs better than either schemes in terms of delay and memory requirements.     

Optimal algorithm for mutual exclusion in mesh-connected computer networks

A distributed algorithm is presented that realizes mutual exclusion among n nodes in a mesh-connected computer network. The nodes communicate by using messages only, and there is no global controller. The algorithm requires at most 3.5 √n messages per mutual exclusion invocation under light demand, and reduces to approximately four messages under heavy demand. The time required to achieve mutual exclusion is shown to be minimal under some general assumptions.     

Using an evolutionary algorithm to optimize the broadcasting methods in mobile ad hoc networks

A mobile ad hoc network (MANET) is a collection of mobile nodes communicating through wireless connections without any prior network infrastructure. In such a network the broadcasting methods are widely used for sending safety messages and routing information. To transmit a broadcast message effectively in a wide and high mobility MANET (for instance in vehicular ad hoc network) is a hard task to achieve. An efficient communication algorithm must take into account several aspects like the neighborhood density, the size and shape of the network, the use of the channel. Probabilistic strategies are often used because they do not involve additional latency. Some solutions have been proposed to make their parameters vary dynamically. For instance, the retransmission probability increases when the number of neighbors decreases. But, the authors do not optimize parameters for various environments. This article aims at determining the best communication strategies for each node according to its neighborhood density. It describes a tool combining a network simulator (ns-2) and an evolutionary algorithm (EA). Five types of context are considered. For each of them, we tackle the best behavior for each node to determine the right input parameters. The proposed EA is first compared to three EAs found in the literature: two well-known EAs (NSGA-II and SPEA2) and a more recent one (DECMOSA-SQP). Then, it is applied to the MANET broadcasting problem.     

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.     

A fast,scalable mutual exclusion algorithm

Summary This paper is concerned with synchornization under read/write atomicity in shared memory multi-processors. We present a new algorithm forN-process mutual exclusion that requires only read and write operations and that hasO(logN) time complexity, where time is measured by counting remote memory references. The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded. Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention. In fact, its performance rivals that of the fastest queue-based spin locks based on strong primitives such as compare-and-swap and fetch-and-add. We also present a modified version of our algorithm that generates onlyO(1) memory references in the absence of contention. Jae-Heon Yang received the B.S. and M. S. degrees in Computer Engineering from Seoul National University in 1985 and 1987, respectively, and the Ph.D. degree in Computer Science from the University of Maryland at College Park in 1994. Since June 1994, he has been an Assistant Professor of Computer Science at Mills College in Oakland, California. From 1987 to 1989, he was a junior researcher at the Korea Telecommunication Authority Research Center. His research interests include distributed computing and operating systems. James H. Anderson received the M. S. degree in Computer Science from Michigan State University in 1982, the M.S. degree in Computer Science from Purdue University in 1983, and the Ph.D. degree in Computer Sciences from the University of Texas at Austin in 1990. Since August 1993, he has been an Assistant Professor of Computer Science at the University of North Carolina at Chapel Hill. Prior to joining the University of North Carolina, he was an Assistant Professor of Computer Science for three years at the University of Maryland at College Park Professor Anderson's main research interests are within the area of coneurrent and distributed computing. His current interests include wait-free algorithms, scalabde synchronization mechanisms for shared-memory systems, and object-sharing strategies for hard real-time applications.Preliminary version was presented at the Twelfth Annual ACM Symposium on Principles of Distributed Computing Ithaca, New York, August 1993 [15]. Work supported, in part, by NSF Contracts CCR-9109497 and CCR-9216421 and by the Center for Excellence in Space Data and Information Sciences (CESDIS)     

改进蚁群算法在移动自组网中的研究

为了解决移动自主网移动节点快速移动导致封包遗失率高的问题,提出一种改进的跨层蚁群算法CAARM。该算法通过MAC跨层计算和预测节点距离,利用前向蚂蚁携带的封包信息进行路由查询,动态地探测移动网络中下一Qo S可靠的节点并进行节点切换,同时采用按需路由机制周期性地进行维护路由。实验结果表明,该算法通过增加一定的传输延时,有效地减少了封包遗失,并且能维持较小的节点切换开销,适合于数据可靠性要求较高的移动自组网络。     

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.     

层状 Ad Hoc 网络的信息传播路由算法研究

讨论了层状移动AdHoc网络的一个信息传播路由算法和基于半马尔可夫过程的节点移动跟踪模型,通过该路由算法可以有效地解决层状子网络间的通信和信息交换。通过路由算法得到的中继节点的移动跟踪模型和计算机仿真,分析了层状移动AdHoc网络的传播性能和路由开销,并得出:当 0≤ρ≤ 1时,层状AdHoc网络的传播性能显著地受到移动呼叫率ρ的影响,当ρ>1时,层状AdHoc网络的传播性能主要取决于移动网络的节点总数、节点移动速度和加速度的结论。