Research in the area of mobile ad hoc networks (MANETS) is exploring technical solutions to enable spontaneous collaboration between mobile computing devices. Such solutions could help emergency-and-rescue personnel by providing an infrastructure for communication and information sharing. In the Ad-Hoc InfoWare project (funded by the Norwegian Research Council under the IKT-2010 Program, 2003 2007), ¹ we're investigating rescue scenarios that might benefit from wireless devices for applications such as dispatching rescue personnel and equipment, supporting context-aware medical diagnosis and treatment, and providing real-time evidence collection and management.

Information access and sharing is difficult in MANETS because of their dynamic character, scarce resources, and heterogeneous user devices. A rescue scenario further complicates matters because of requirements such as fault tolerance, survivability, real-time operations, and security. Solving these issues from scratch for every new MANETS application isn't feasible. A better solution would be a set of middleware services that support the development of applications for MANETS. The dynamic nature of MANETS makes middleware services based on synchronous communication inadequate because they're too vulnerable to communication disruptions. For example, devices might suddenly be out of reach or turned off. The classic alternative to synchronous solutions is a distributed event notification system.

We present a DENS that we're designing specifically for MANETS in emergency-and-rescue scenarios. In the Ad-Hoc InfoWare project, we're also developing four other components besides the DENS: knowledge management to handle ontologies, metadata management, integration of metadata, and information from different sources; resource management to track neighboring nodes and their resources to provide information for replication decisions; security and privacy management based on a priori gathered certificates, key management for signing and encrypting messages, and access control; and watchdogs, which we describe here along with the DENS.

The DENS should serve as a basic service that supports the mission-critical task of information sharing. Therefore, it must be highly available. Because it will most likely run on mobile devices, which could lose contact with other devices due to network partitioning or be switched off to save power, we need a distributed solution. The DENS should support information sharing in the different network partitions, and it should still work well when arbitrary devices, including DENS nodes, are switched off. Therefore, the DENS must provide a sufficient degree of redundancy through replication. Furthermore, fallback solutions are necessary in case there's a network partition without any DENS node.

DENS nodes act as mediators between a node that subscribes to some information (subscriber) and a node that publishes information (publisher). Subscribers and publishers are thus decoupled. To deliver subscriptions and notifications to their final destination, DENS nodes must maintain state information, such as which node has subscribed to which service. Ensuring high availability requires replicating this state information. However, network partitioning and network merging can easily lead to an inconsistent state. Therefore, the DENS must handle subscriptions and notifications with inconsistent state information. Furthermore, it should include maintenance protocols to again obtain a consistent state after these events. DENS nodes can also store information about undeliverable notifications.

Distributed systems designers generally implement either at-most-once or at-least-once delivery semantics. In emergency-and-rescue applications, information could be a lifesaver and must therefore not be lost. At-least-once delivery means the subscriber receives the notification at least once, making this the ideal semantic for our DENS from this standpoint. However, in an ad hoc network, it's not possible to guarantee at-least-once delivery, because network partitioning might be permanent. Therefore, we store information of undeliverable notifications to implement delivery semantics as close as possible to at-least-once delivery.

Another requirement for the DENS is a kind of content-based subscription model. Any kind of data that's storable as data structures in main memory, a file, or system internal tables could be of interest to someone. Therefore, a publisher can't decide which information to publish. This must be left to the subscribers.

The devices (the network, PDAs, laptop, mobile phone, and so on) are typically also heterogeneous with respect to available memory and disk space. Therefore, the DENS must be configurable so that small resource-weak devices run only the minimum set of protocols, while devices with sufficient resources implement perhaps all DENS components. (More general requirements for the middleware services are available elsewhere. ¹ )

Here, we present some of our design ideas for the DENS to overcome the problems imposed by ad hoc networks' heterogeneous and dynamic nature (see the " Related Work " sidebar). Figure 1 illustrates the basic elements of the DENS and watchdog (WD) components. The DENS implements a distributed service, whereas the WD component implements a local event notification service. The DENS comprises three delivery components and four management components. The delivery components implement the protocols between subscribers and DENS nodes, between DENS nodes, and between publishers and DENS nodes.

The WD component implements the interface between the DENS and the WDs, starts and stops the WDs, and maintains a list of the WDs currently running on the node. A WD is an agent whose task is to monitor within the node whether the condition specified in a subscription is fulfilled. In this case, it notifies the DENS that the event has occurred. All nodes willing to serve as a publisher in the ad hoc network—that is, to share information with others—must implement this component. DENS nodes must maintain state information about subscriptions so that the DENS can send the corresponding notifications to the proper subscribers.

The storage service stores notifications that were undeliverable—because, for example, the subscriber was in a different network partition or the subscribing device was turned off. Thus, a node that just wants to subscribe to events must run only the subscriber-DENS delivery component. Nodes that want to publish must run the publisher-DENS delivery and WD components. In the most basic configuration, DENS nodes must run the DENS-DENS delivery and state management components. The storage management component and the availability-and-scaling component are optional.

Figure 2 shows a MANETS with three nodes running the DENS. Node 1 sends a subscription message using the subscriber-DENS protocol, which locates a DENS node and sends the subscription message to this node. DENS node 2 installs a WD using the DENS-publisher protocol. The publisher-DENS protocol installs a corresponding WD on publisher node 5. The knowledge manager summarizes what information is available in the network, and the DENS uses this summary to locate the publisher node. Afterward, the DENS propagates the subscription message to the other DENS nodes using the DENS-DENS protocol (steps 2a and 2b in Figure 2 ). If an event in the realm of node 1 happens, then in step 3 the WD uses the DENS-publisher protocol to notify a known DENS node—that is, node 4. Node 4 then notifies node 1 and propagates this notification message to the other DENS nodes. ( Figure 2 doesn't illustrate this propagation.)

Bandwidth is a scarce resource in a wireless network. Therefore, the DENS nodes must cooperate so that they can most efficiently replicate data and provide a highly available service without generating a lot of traffic. Because replication can cause inconsistent states, the DENS nodes must manage this process while trying to obtain a consistent state as soon as possible. This design question affects the DENS-DENS protocol.

The two main approaches to this problem are one based on a chain-structured overlay (as in Figure 2 ) and one based on multicast groups. A combination is also possible, but we don't address that approach here. We use the hardware profile of devices to generate a resource indicator (R-IND), which acts as ordering criteria for the overlay chain; thus, the node with the most resources is the head of the chain. Another R-IND (for example, a multiply-and-accumulate address) differentiates nodes with equal R-INDs. The DENS nodes are aware of the other nodes; hence, their R-INDs are aware of the chain order. To deliver subscriptions and notifications to their destinations, our notification service first forwards these subscriptions to the head of the chain, which processes them and propagates the corresponding information through the chain to all DENS nodes.

Another solution without any logical structure on DENS nodes and without any knowledge about other DENS nodes is to let the DENS nodes be part of the same multicast group. (If the routing protocol doesn't support multicast, it's possible to distribute messages through broadcasting and pruning.) Thus, it's possible to propagate subscriptions and notifications by using the multicast address.

The state management stores information about subscriptions to send a notification to the correct subscriber. The DENS replicates this state information among all DENS nodes, so even though a node moves shortly after having sent a subscription, it can still receive the notification about the event to which it has subscribed. Replication also helps achieve fault tolerance, because if a DENS node gets disconnected, other nodes contain the same information. Thus, a node that has subscribed to some event doesn't depend on a specific DENS node. The DENS deletes a subscription from the state management component either after a subscriber has received its notification or until the subscriber unsubscribes, depending on the nature of the subscription.

Replication is thus a way to overcome some of the challenges stemming from the nodes' mobility, but it also creates some problems, such as how to detect and resolve inconsistency between the DENS nodes and how to distribute the workload of installing WDs, sending notifications, and so on. Inconsistency between the DENS state replicas could occur after events such as network partitioning and merging. For example, while a node is making a new subscription in one network partition, it's not possible to inform other DENS nodes in other partitions. The same happens when removing a subscription. Another example is if a node makes a subscription but the DENS can't start a WD on the publisher node because it's in another network partition. The DENS node receiving the subscription sends an acknowledgment after a WD is successfully installed on a publisher node, so if a subscriber doesn't receive this acknowledgment within a certain time limit it must try to resubscribe. Also, if a subscriber or a publisher moves to another network partition, the subscriber doesn't receive a notification before it's in the same partition as a DENS node that's received a notification about that event.

Having a consistent state is desirable. Therefore, the state management component comprises protocols for exchanging state information when network merging occurs. How this is achieved depends on whether we choose the chain or multicast group approach.

In the logical-chain approach, a merging process involves building a new logical chain and exchanging information about subscriptions, notifications, and DENS nodes. It's also necessary to update the state information about other DENS nodes when they're disconnected. We could use an eager or a lazy process to do this. In an eager process, the DENS nodes send update messages within fixed time intervals to one another, and any node that doesn't reply is deleted from the state information. In a lazy process, the DENS nodes discover that a DENS node is missing when they try to send a message to it and don't get a reply—for example, when they send subscription messages. If a new node starts running the DENS, we assume it broadcasts this information.

Merging between two network partitions with the multicast solution requires less coordination. The DENS nodes in the new network partition might not have the same state information—that is, information about subscriptions and undelivered notifications. The nodes might then have to send a request message for information using the multicast address if, for example, a DENS node receives a notification to which it has no corresponding subscription. If the DENS node gets a reply, it sends the notification to the subscriber and waits for an acknowledgment. If it doesn't get a reply or an acknowledgment from the subscriber, it stores the notification according to the storage policy and replicates it to the other nodes. After a while, it will try to resend this notification.

For network partitioning, situations could arise in which either no node runs the DENS or too many nodes run the DENS in the network partition. The former occurs when a node wants to send a subscription or a notification, and the delivery component discovers that it's lost its closest DENS node because it or the node running the DENS has moved. The node should then ask nodes in one-hop proximity if they're aware of any node running the DENS, and this request can propagate to their neighbors as well. If replies are only negative, some of the nodes should start running the DENS.

In the logical-chain approach, the availability and scaling component uses the summary of how many DENS nodes are in the network, and information about the network's size (number of nodes) to determine if other nodes should start running the DENS, or if too many nodes are running the DENS already. If there are too few or no DENS nodes, the nodes with the most resources should start running the DENS and inform the other proximate nodes.

In the multicast solution, each DENS node has less information about the other nodes, making it more difficult to decide whether too few or too many DENS nodes are in the network. Some sort of distributed counting is therefore necessary. A request from a subscriber or a publisher not having a DENS node in one-hop proximity could initiate this request. The DENS could distinguish counting messages from one another using a node indicator along with the number of counting messages that the initiating node has sent—for example, ID = 4, message# = 3. By distributing this message to every neighbor, and sending back replies to its sender stating how many replies it has received itself and whether it runs DENS or not, the initiator has enough information to decide what to do next. If more than one node starts counting simultaneously, the one with the higher ID wins.

The classic subscription models are channel, subject, and content based. Our application domain doesn't let publishers decide which events to publish. Therefore, we're interested in a content-based subscription model that can be extended with location-related conditions, as in the Rebeca system. ² This would allow adapting subscriptions when the subscribing node moves. The choice for a particular subscription model and its implementation is still an issue of ongoing research. However, our DENS design uses WDs to decouple the delivery components and the other DENS components from the particular subscription model used. Thus, we need to coordinate only the subscriber and the WD execution environment with respect to the subscription language for filtering the content. (The provision of functions to compare subscriptions to the DENS allows optimizations but isn't mandatory for the basic DENS currently under investigation.)

The WD filters the events on the basis of the content filter at the publisher node. The content of subscription and notification are void for the delivery components. This lets us experiment independently with different solutions for DENS components and subscription models. We also avoid the problem of filtering encrypted content on a mediator node (DENS node). However, the DENS must control access before installation of the WD so that a subscriber doesn't get a notification about changes in information to which it doesn't have access.

The WD manager registers subscriptions, checks whether the same subscription has been registered before, and, if not, starts a new WD to execute the subscription. Local applications use WDs directly to monitor their system without the overhead that the DENS introduces. Therefore, the WD manager registers for all running WDs whether the subscription has been made from the DENS or a local application to direct the message back to the proper destination.

In the case of network partitioning, the DENS might not notify some nodes about the events they've subscribed to, thus making buffer notification necessary. We can distinguish between notifications having information that's only valid now and information that could also be useful in the future. A time stamp on the notifications could indicate how long they're valid. Because of limited storage space, we need a policy to determine which notifications should be stored and for how long. One possible policy is to discard the oldest notifications, or rate the notifications according to importance or relevance and delete the least important notifications first. Some notifications might also be valid until a new notification about the same event arrives. Table 1 describes different storage approaches.

We are currently studying design alternatives for the DENS and its protocols. The next step is to implement them in a simulation environment to study the protocols' efficiency and stability and their impact on the DENS' availability. In addition, we plan to address questions of how to structure the DENS nodes to limit network traffic related to subscriptions and notifications, handle policy-based storage, and implement WDs with the proper subscription language. We're also investigating using DENS in situations other than rescue scenarios.

Katrine Stemland Skjelsvik is a PhD student in the Department of Informatics at the University of Oslo. Her research interests include middleware and quality of service. She received her masters thesis in informatics from the University of Oslo. Contact her at katrins@ifi.uio.no.

Vera Goebel is a professor in the Department of Informatics at the University of Oslo and an adjunct professor at the Computer Science Institute of the University of Tromsø. Her research interests include multimedia database systems and operating systems, multimedia middleware, quality of service, and interactive distributed multimedia applications. She received her PhD in computer science from the University of Zurich. She is a member of the ACM and the IEEE. Contact her at goebel@ifi.uio.no.

Thomas Plagemann is a professor in the Department of Informatics at the University of Oslo. His research interests include multimedia middleware, protocol architectures, quality of service, operating-system support for distributed multimedia systems, and interactive distance learning. He received his PhD in technical science from the Swiss Federal Institute of Technology in Zurich. He is a member of the ACM. Contact him at plageman@ifi.uio.no.