Justin Collins. "Communication Paradigms for Mobile Ad Hoc Networks" PhD Dissertation, UCLA. 2014. (Read Online | Slides)
Consumer implementations of mobile ad hoc networks (MANETs) are rapidly becoming possible due to the proliferation and ubiquity of smartphones, tablets, and other portable computers. However, the combination of wireless communication, device mobility, and the self-organizing nature of MANETs presents a challenging environment for developing distributed applications. Networking middleware and libraries for MANET applications typically provide adaptations of traditional distributed computing paradigms designed for wired networks. In this work we quantitatively evaluate existing projects and their fundamental underlying communication paradigms using real applications in realistic MANET environments. We then propose and evaluate a new communication paradigm specifically designed for MANETs.
Developing distributed applications for mobile ad hoc network continues to be challenging due to the dynamic and unpredictable nature of MANETs. MELON is a general purpose coordination language designed to provide flexible communication patterns for MANET applications while remaining lightweight. Based on a distributed shared message store, MELON abstracts network communication to an asynchronous exchange of persistent messages. MELON simplifies application development by supporting read-only and remove-only messages, bulk message retrieval, and per-host ordering of messages. In this paper, we review the MELON programming model, demonstrate its utility for writing MANET applications, and quantitatively compare it to traditional distributed computing paradigms in a MANET context. For a shared whiteboard application, we find MELON achieves 100% message delivery with 95% less latency than tuple spaces while also maintaining per-host message ordering.
Justin Collins and Rajive Bagrodia. "MELON: A Persistent Message-Based Communication Paradigm for MANETs." In Proc. of the 10th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous 2013).
In this paper we introduce MELON, a new communication paradigm tailored to mobile ad hoc networks, based on novel interactions with a distributed shared message store. MELON provides remove-only, read-only, and private messages, as well as bulk message operations. The dynamic nature of MANETs is addressed with persistent messages, completely distributed message storage, and flexible communication patterns. We quantitatively compare a prototype implementation of MELON to existing paradigms to show its feasibility as the basis for new MANET applications. Experiments demonstrate 40% better throughput on average than traditional paradigms, as well as 70% faster local insertion and removal operations compared to an existing tuple space library.
Justin Collins and Rajive Bagrodia. "A Quantitative Comparison of Communication Paradigms for MANETs." In Proc. of the 7th International ICST Conference on Mobile and Ubiquitous Systems: Computing, Networking and Services (MobiQuitous 2010).
Mobile ad hoc networks (MANET) present a challenging area for application development. The combination of mobile nodes and wireless communication can create highly dynamic networks with frequent disconnections and unpredictable availability. Several language paradigms have been applied to MANETs, but there has been no quantitative comparison of alternative approaches. This paper presents the first quantitative evaluation of three common communication paradigms (publish/subscribe, RPC, and tuple spaces) compared within realistic MANET environments using real applications. We investigate the application-level performance of the paradigms and present a summary of their relative strengths and weaknesses. We also demonstrate the impact of wireless and mobility on application-level metrics, the most dramatic being delivery rates dropping to nearly 25% and round trip times increasing up to 2000% in a mobile scenario.
The possibility for spontaneous ad hoc networks between mobile devices has been increasing as small devices become more capable of hosting useful networked applications. These applications face the challenges of frequenct disconnections, highly dynamic network topologies, and varying communication patterns, a combination unique to mobile ad hoc networks. This is the first survey to examine current MANET programming approaches including tuple spaces, remote objects, publish/subscribe, and code migration through analysis and experimental results. These approaches are essentially extensions to existing distributed and parallel computing concepts. We suggest that new abstractions may be necessary to fully handle the programming issues presented by MANETS.
David Joslin and Justin Collins. "Greedy transformation of evolutionary algorithm search spaces for scheduling problems." IEEE Congress on Evolutionary Computation, 2007 (CEC 2007).
Many scheduling algorithms search the space of possible solutions (schedules), but some instead search the space of permutations of the set of jobs, employing a greedy algorithm to map any such permutation to a schedule that can be evaluated by the fitness function. The search algorithm is thus simplified because knowledge about problem domain details is encapsulated in the greedy algorithm that constructs schedules, and the fitness function that evaluates them. The variety of types of algorithms for which this sort of "greedy transformation" has proven effective, and the range of successful applications, prompts us to look more closely at how such transformations may also make good solutions easier to find. In this paper we experimentally evaluate some characteristics of search spaces under greedy transformations as a first step toward understanding why this technique is effective.
Justin Collins and David Joslin. "Improving genetic algorithm performance with intelligent mappings from chromosomes to solutions." In Proc. of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO '06) (Seattle, Washington, USA, July 08 - 12, 2006).
Genetic algorithms (GA) generally use a simple, straight-forward mapping from phenotype to genotype. The map- ping is often so simple that we can think of the chromosome space and solution space as being identical. In this research, we look instead at many-to-one mappings from phenotypes to genotypes, as defined by polynomial-time domain-specific functions. These mappings may transform the search space of a particular problem so that it is easier for the GA to converge on good solutions. In order to study the effect these many-to-one mappings could have on a problem, we applied increasingly “intelligent” mappings to the problem of scheduling college courses. We looked at five different mappings, ranging from a very simple and direct mapping, to one that makes use of all hard and soft constraints in a flexible manner. Each of the mappings implement a greedy approach to scheduling the courses.