A Framework for Communication Planning on Mobile Devices

1 Introduction

Mobile computing is increasingly common in urban settings. Laptops, PDAs, and other small, network-capable computing devices pervade society. These devices along with the many and varied applications of mobile computing highlight an important observation: communicative actions are not free. In fact, there are a variety of associated costs, including:

• Power. On many devices, networking hardware consumes more power than all other systems combined [Vahdat et al., 2000]. Transmissions consume substantial amounts of limited battery supplies. Frequent communication significantly reduces operational lifespan, a critical obstacle against many applications.
• Bandwidth. Wireless link capacities are typically much lower. Throughput in 802.11b MANETs is often less than 50% the theoretical maximum of 11 Mbps [Xylomenos et al., 2001]. In contrast, traditional wired networks can reach upward of 100 Mbps. Communication must be sparing to conserve such limited bandwidth.

Communication resources also vary between hosts and operating context. Hardware such as 802.11 cards, Bluetooth chips, and CDMA modules possess different properties and capabilities. Routing algorithms and other software present dissimilar interfaces and sensing abilities an agent may utilize [Kopena et al., 2005]. However, it cannot necessarily know a priori which communication services will be available on its host, and must instead autonomously discover and utilize them. In addition, this set may change over time, through user actions such as undocking the host or natural events, e.g. network cards failing as power dwindles.

Consider a calendar on a PDA with cellular and wireless capabilities. As events are posted it synchronizes with a base computer, which in turn notifies family and friends. Wireless ethernet can only connect to the base computer when in range of an access point. The cellular module can always make an Internet connection to the base computer via a satellite, but consumes substantial amounts of power and charges a fee.

To post updates in all situations, the calendar must discover and utilize both interfaces. However, cellular connections should be minimized: they should not be used if wireless is available, or to post minor or far-off events. These should be collected until several may be transmitted or ethernet can be used. However, cellular connections should be used to post imminent changes so that the base computer may begin synchronizing affected friends, family, or co-workers.

3 Formalization

Utilizing available network services and intelligently, effectively conducting communications may be achieved by releasing agents and applications from fixed application-layer protocols and messages. Communicative actions are not static. An agent may plan, schedule, alter, and parameterize them, adapting and responding to conditions and events.

Even a simple agent may deliberate on when to deliver a fixed message in order to minimize communication costs. It may also plan on which network services to use based on advertised descriptions. More sophisticated agents may alter and plan on the propositional content of messages to maximize their utility: power-conscious agents may aggregate low priority messages into one burst, economizing fixed costs.

In this work, such reasoning is accomplished through utility-based planning. Services such as network interfaces are advertised and treated as plan actions with attached costs. Communication goals are modeled as utilities of doxastic states. These elements are represented within a formal situation calculus, enabling exchange of well-defined service descriptions and limited commitment to reasoning mechanisms.

Planning Framework. This work defines the above planning problem using the Process Specification Language (PSL) [Gr¨ uninger and Menzel, 2003], an ISO standard (ISO 18629) for process modeling. At its core, PSL is an extensive first-order situation calculus axiomatization. A deductive planning problem (A, I,ψ,C) → ρ is defined on top of the PSL Core, Occurrence Trees, and Discrete States theories:

• A are the activity axioms, preconditions and effects.
• I defines initial fluent state: ∀δi ·initial(δi) ⊃δi |= I.
• A chain δ is a sequence of successive legal occurrences such that initial(δ1)∧δn |= the episode delimiter ψ.
• C defines utility summands µ over occurrences, related by occ-util-summ(δi, µ).
• Occurrence utility, occ-util(δi), is defined as ∑µ over {µ |occ-util-summ(δi , µ)}.
• Utility of a chain, utility(δ), equals ∑occ-util(δi).
• A rational chain δ is a chain such that there does not exist a δ ′ such that utility(δ ′ ) > utility(δ).
• A rational plan ρ is then the sequence of activities associated with the occurrences in a rational chain.

Agents, Hosts, and Message Actions. A small theory weakly defining agents, hosts, messages, and message activities is also incorporated on top of PSL. This provides a shared ontology defining a base by which an agent may communicate about, recognize, and utilize communication resources.

Agent Beliefs. A first order theory of belief based on kaccessibility between occurrences is also included in the theory. It defines KD (see e.g. [Fagin et al., 1995]), the logic of consistent belief, within the fluent space of PSL. This enables the expression of agent interfaces in the form of doxastic activity effects, as well as an agent's communication goals. Belief, and specifically KD, was chosen due to its relatively weak commitments on agent reasoning abilities and trust.

4 Example: Calendar Agent Axiomatized

Agents and communication resources may then describe their interfaces and abilities, e.g. the base computer of Section 2:

∀o,a,s,m·occurrence of(o,a)∧legal(o) ∧ message-activity(a, s, SYNC, m) ⊃ [∀c · holds(contents(m, c), o) ⊃ holds(believes(SYNC, c), o)] .

The cellular and wireless interfaces may be described as: ∀o,a,s,d,m·occurrence of(o,a)∧legal(o)∧ sat-msg(a, s, d, m) ⊃ message-activity(a, s, d, m)∧ occ-util-summ(o, -0.5). ∀o,a,s,d,m·occurrence of(o,a)∧legal(o)∧ radio-msg(a, s, d, m) ⊃ prior(in-range(s, d), o)∧ message-activity(a, s, d, m) ∧ occ-util-summ(o, -0.1).

The agent's internal communication activities would be: activity(defer).

∀o,m,d,n ·occurrence of(o,attach(m,update(d,n)))∧

legal(o) ⊃ ∧holds(contents(m, update(d, n)), o).

The agent's behavior may then be captured as the timedependent utility of delivering updates to the base computer:

∀o, c, d, n · holds(current-day(c), o)∧ holds(believes(SYNC, update(d, n)), o) ⊃ occ-util-summ(o, 1 - ((d - c)/7)).

With the addition of an episode delimiter defined as occurrences of defer or message-activity, supporting axioms not listed above such as the definition of update, and closure axioms, a plan based on these definitions will:

• Deliver any update if a wireless connection exists.
• Use the satellite interface if warranted by an update or some collection of updates. For example, any update concerning the next 3.5 days will be posted immediately.
• Otherwise defer until new updates are posted or conditions change, e.g. wireless contact is made.

5 Summary and FutureWork

This poster presents an approach to efficiently performing communication tasks by planning on the costs and capabilities of advertised resources. In contrast with power-aware networking, this work supports application-layer preferences and mixed-infrastructure settings. Although similar to research on communication planning via epistemic goals, this work acknowledges that communicative acts have costs. In addition, this framework is oriented toward a service-based system, enabling agents to reason on internal as well as external capabilities. This work also introduces an application area of web services, along with a formalization in the situation calculus and a principled, practical representational differentiation between mental and world activity effects.

Future work includes algorithms and protocols for exchanging descriptions; accounting for the unpredictable nature of mobile networks in composing a plan; defining subclasses of the planning problem amenable to pragmatically feasible computation; techniques for integrating heterogenous and untrusted costs; and the knowledge acquisition task of evaluating preconditions involving unknown terminology.

More information, details, and citations to related work are available at http://edge.cs.drexel.edu/services/.