KEPPAN: بهره برداری از دانش برای شبکه های موقت برنامه ریزی فعالانه

This paper explores the idea of managing mobile ad-hoc networks (MANETs) by the communication needs of their nodes, as a means to facilitate the operation of distributed applications. Specifically, we present a middleware layer that enables reasoning about the multiple possibilities there may exist to ensure satisfiability of certain communication needs. This middleware has been explicitly devised to handle partial and changeable knowledge about the networks, and to guide the search for missing information whenever it cannot conclude whether it will be possible to satisfy some needs. These features provide the basis to implement policies with which to coordinate activities in a MANET, in quest for the configuration that best satisfies the communication needs of its nodes. We provide simulation results to show the comparative advantages of our solution, plus a report of experiments to assess its practicality and usability.

Computing is witnessing a shift from desktop machines reliant on fixed, wired networks to wireless networks of mobile devices that communicate without infrastructure support. The paradigm of mobile ad-hoc networks (MANETs) is becoming increasingly popular, with applications in diverse areas like military surveillance (Rubin and Zhang, 2003), emergency situations (Jiang et al., 2004), vehicular networks (Blum et al., 2004), sensor–actor networks (Melodia et al., 2007) and many others. The problem we address in this paper is that the physical mobility of the nodes of a MANET frequently results in sporadic and transient connectivity, which may cause an application to malfunction if it cannot communicate with the nodes that provide the services it needs. To prevent that, many authors (Basu and Redi, 2004, Chang et al., 2004 and Goldenberg et al., 2004) considered scenarios in which the nodes move purposefully to preserve static connectivity requirements, such as maintaining a biconnected network topology. Unfortunately, these tethered mobility (TM) approaches tend to over-restrict the movements of the nodes, which may be very harmful for some applications. As an alternative, the authors of Su et al. (2001), de Rosa et al. (2005) and Härri et al. (2005) opted not to ensure that disconnections do never occur, but to anticipate them using movement prediction (MP) techniques, and then warn the applications or their users about the foreseeable problems. This approach can prevent breaks between pairs of nodes that are exchanging information at a given moment; however, it cannot provide those nodes with information on how to maintain the communications, e.g. by establishing multihop routes through other nodes, migrating services onto nodes that stay within range, etc. Knowing the limitations of previous approaches, some authors have wondered about enabling proactive-planning of MANETs through knowledge exploitation (KP) (Sen et al., 2005), driven by the communication requirements of the nodes, i.e. by indications that it should be possible to communicate with certain services at specific times and places. The idea starts out by having the nodes exchange information, including whatever they know about: • The service provision plans of the different nodes: which services they are going to provide, during what time intervals, etc. • The elasticity properties of the services, i.e. whether they can migrate from one node to another, be cloned or leased for a period of time, etc. • The motion profiles of the nodes, i.e. their intended/expected movements. • Miscellaneous facts like the impossibility to make some moves (e.g. due to the presence of walls), the fact that a given service cannot be provided by certain nodes, etc. Gathering this information, any node can guess a global picture of the MANET to automatically check the satisfiability of its communication requirements, and derive possible reactions if they cannot be fulfilled. The reactions may imply moving oneself to a specific location, telling others to move, accomplishing service relocations, reconsidering the communication requirements themselves, etc. In any case, it is up to the applications or the users of the different nodes to agree on which reactions to apply and enforce the corresponding rearrangements. Research into knowledge exploitation in MANETs is still incipient. Even though we can trace back its origins to the wealthy literature of autonomous systems (Dobson et al., 2006), the idea was fully described in Handorean et al. (2004), where the authors sketched the formalisms needed to represent pieces of information about a network and to reason about the knowledge they convey. Later, Mecella et al. (2006) presented an architecture to support collaborative applications in MANETs, focusing on the coordination procedures with which to handle problems with the satisfiability of communication requirements (specifically, in emergency scenarios). Murphy et al. (2001) proposed a knowledge exchange and coordination scheme based on tuple spaces, which they proved particularly suitable to furnish the view of a shared memory for distributed applications. Also with tuple spaces, Sen et al. (2007) refined the formalisms put forward in Handorean et al. (2004) and built a database of motion profiles to deal with connectivity problems. All of the aforementioned studies assume the knowledge available about the networks to be perfect, which is rarely true in real environments. Rather the opposite, the knowledge is most often partial (i.e. incomplete) and changeable. When a node appears in a MANET, it only knows about its own location, services and movements, which yields a very limited view of the network to reason about communication requirements. That view can be augmented, progressively, with information retrieved from other nodes, but there are seldom guarantees about its completeness and freshness. Indeed, it usually happens that a node cannot expose complete information about itself; for example, although there are many cases that a node follows a fixed or predictable trajectory—e.g. nodes attached to rails, unmanned vehicles in military applications (Rubin and Zhang, 2003) or virtual nodes whose movement can be controlled at will ( Dolev et al., 2004)—complete motion profiles are generally unavailable. This problem was already pointed out in Biskupski et al. (2007), where the authors proposed an abstract agent-based model of self-organizing MANETs, with notions of partiality and changeability in the knowledge available about a network. Another conceptual model was given in Holzer et al. (2007), focusing on the formalization of autonomous and emergent behavior. The preceding discussion reveals that research into knowledge exploitation remains at a rather theoretical level, since there are no working solutions to the problem of handling imperfect knowledge. Here, we tackle this question by introducing a middleware layer that provides mechanisms for the nodes of a MANET to collaborate in making up the network that best satisfies their communication requirements. This proposal makes contributions related to the following aspects: • Analyzing what can be concluded about the possibility to satisfy communication requirements in the face of incomplete knowledge about the MANETs. • Characterizing how the conclusions are affected by changes in the knowledge bases, either additions or modifications. • Exposing the multiple possibilities there may exist to ensure satisfiability of certain requirements. • Assessing practicality of the algorithms that process the knowledge and the amount of information that a mobile device has to handle. Hereafter, we shall focus on the tasks related to knowledge exploitation, i.e. the modeling of the networks and the reasoning enabled about communication requirements. The various means that may be used to gather location information in MANETs and to ensure its trustworthiness have been surveyed in Friedman and Kliot (2006), Wu and Wu (2006) and Marias et al. (2006), respectively. Likewise, mechanisms to accomplish the dissemination of information among different nodes can be sought in Chen and Wu (2003) and Oyabu et al. (2005) or in the literature of tuple spaces (Gelernter, 1985, Freeman et al., 1999 and Xu et al., 2006). Our proposal, called KEPPAN (knowledge exploitation for proactively-planned ad-hoc networks), is described in Section 2 along with toy examples illustrating all of its features. Later on, Section 3 includes simulation results to show the comparative advantages of this scheme, plus a report of experiments to assess its practicality and usability. Finally, Section 4 provides a summary of conclusions and the motivation of future work.

We have presented a scheme to support the proactive management of mobile ad-hoc networks, with the goal of improving the stability of the communications. We have worked on the idea of knowledge exploitation, paying attention to the fact—neglected in the literature so far—that every node must handle incomplete and changeable knowledge about other nodes, about the services they provide and about their motion profiles. In this regard, KEPPAN provides the necessary modeling and reasoning mechanisms for the nodes to check their communication requirements. At the output, it informs of necessary conditions and communication routes when the requirements can be satisfied, suggests networks rearrangements if they cannot, and guides the search for more information in case of uncertainty. The multi-valued formal basis of KEPPAN guarantees the correctness of the conclusions drawn from the analysis of communication requirements, even in the face of incomplete knowledge. Thus, we tackle the problem that left previous approaches to knowledge exploitation at a theoretical level: the erroneous forecasts due to presuming negative knowledge about what is actually unknown. In addition, we have been able to implement mechanisms for the synthesis, analysis and revision tasks that proceed incrementally instead of from scratch, which sustains the viability and the scalability of the approach as regards the burden on individual nodes. In what concerns the global operation of the MANETs, the scalability of knowledge exploitation depends on the policies that may be implemented at the applications level to interact with KEPPAN and respond to its outputs. Here, there are many factors that condition the volume of traffic generated: publishing all the knowledge immediately or doing so mainly upon request from other nodes; recovering more or less information from the tuple space at any moment; negotiating the proposed rearrangements through more or less complicated procedures; etc. Since there is no optimal configuration for all settings, we leave open the question of characterizing the variables that might make one policy better than others, such as the predictability of the nodes’ movements, the bandwidth available for communication and the dense/sparse character of the networks. Also concerning future work, we have found a largely unexplored research topic in preparing software applications to autonomously interact with a scheme for knowledge exploitation. For instance, there is yet no general support to automate the formulation of knowledge about the future of the networks, to react to the interpretation of witnesses and revision suggestions, or to carry out any form of negotiation between multiple nodes. In this regard, we are looking at different ideas from the software engineering and artificial intelligence communities to create more sophisticated agents than the ones employed in the simulations of Section 3.1.