T DisconnectionPrediction in Mobile Ad hoc Networks for SupportingCooperative Work

(1)

N E T W O R K M A N A G E M E N T

Disconnection

Prediction in Mobile

Ad hoc Networks

for Supporting

Cooperative Work

T

he widespread availability of network-enabled handheld devices (for example, PDAs with Wi-Fi capabil- ities) has made the development of pervasive computing environments an emerging reality. MANETs (mobile ad hoc networks) are networks of mobile devices that communicate with one another via wireless links without relying on an underlying infrastructure.¹ This distinguishes them from other types of wireless networks—for example, cell networks or infrastructure- based wireless networks. To achieve communication in a MANET, each device acts as an endpoint and as a router for- warding messages to devices within radio range.

MANETs are a sound alternative to infrastructure- based networks whenever an infrastructure has never been available, is no longer available, or can’t be used, as in emergency scenarios.

People who collaborate via MANETs in emergency situations would benefit from software support for their collaboration. Such a coordination layer would let them execute sequential or concurrent sets of activities through specific applications (for example, computer-supported- cooperative-work tools²and workflow management applications³) running on handheld devices, thus supporting the execution of coop-

erative processes. All such applications typically require continuous connections (for example, for data and information sharing, and activity sched- uling and coordination) among devices. Unfor- tunately, continuous connections generally aren’t guaranteed in MANETs.

We’re investigating a specific pervasive architecture that can maintain continuous connections among MANETdevices. We’re targeting this architecture for computer-supported-cooperative- work (CSCW) and workflow management applications that would constitute the coordination layer. The basic problem of such an architecture is, how do you predict possible disconnections of devices, to let the coordination layer appropri- ately address connection anomalies? To solve this problem, we’ve developed a technique for predicting disconnections in MANETs. This technique serves as the basic layer of an innovative pervasive architecture for cooperative work and activity coordination in MANETs. We believe that in emergency scenarios, our proposed pervasive architecture can provide more effective coordination among team members.

A possible scenario

Consider a scenario of archeological disaster recovery. After an earthquake, a team equipped with mobile devices (laptops and PDAs) is sent to the disaster area to evaluate the state of arche- A prediction technique for disconnection detection serves as the basic

layer of a pervasive architecture for cooperative work and activity coordination in M^ANETs

Fabio De Rosa, Alessio Malizia, and Massimo Mecella

Università di Roma La Sapienza

(2)

ological sites and precarious buildings.

Their goal is to draw a situation map to schedule reconstruction jobs. Figure 1a shows a typical cooperative process (depicted as a Unified Modeling Lan- guage activity diagram).

Before this process starts, the team leader has stored all area details, includ- ing a site map, a list of the most impor- tant objects at the site, and previous reports and materials.

We view the team as a MANETin which the team leader’s device (which requires the most computational power, so it’s a laptop) coordinates the other team members’ PDAs by providing appropriate information (for example, maps, impor- tant objects, and so on) and assigning activities.

The team members’ PDAs let them execute some operations but don’t have much computational power. Such operations, possibly supported by particular hardware (for example, digital cameras, General Packet Radio Service connections, computational power for image processing, and main storage), are offered as software services to be coordinated.

After visual analysis of a building, team member 1 (using his or her PDA) fills out questionnaires. The team leader will ana- lyze these questionnaires, with the help of specific software, to schedule the next activities. Team member 3 takes pictures of the precarious buildings, whereas team member 2 is in charge of the image processing of older and recent photos of the site (for example, to initially identify architectural anomalies).

In this situation, matching new pictures with previous ones might be useful. So, the PDA with the high-resolution camera and the PDA with the older stored pictures must be connected.

(b) (a)

Compile questionnaire

Selected building

Go to destination

Zoom in on damaged part

Send photos Photos

Compile report

Result

Team leader

Team member 1 Team member 2

(picture storage device)

Team member 3 (camera device) Capture scene

Museum Precarious

bell tower building

Church Disaster area

Operator

Bridge Team leader

Camera

Movement needed to accomplish the task

Movement needed to maintain the network connectivity; it should be adaptively driven by the cooperative application

Matching

Selected building

Go to destination

Zoom in on damaged part

Send photos Photos

Matching

Team member 3

Team member 2 Team member 4

Capture scene

Follow team member 3 Picture storage

Select building

Select building ment, and (c) a detail of the process, Data

which has been modified to prevent the disconnection of mobile devices.

(3)

But in a scenario such as the one in figure 1b, the camera-equipped PDA’s movement might result in its disconnection from the other devices. A pervasive architecture should be able to predict such situations, to alert the coordination layer. The coordination layer, in turn, would direct a “bridge” device (team member 4’s PDA) to follow the PDA that’s going out of range, maintaining the connection and ensuring a path between the devices. In this way, the coordination layer, on the basis of the disconnection prediction, schedules the execution of new, unforeseen activities, as figure 1c shows (note the new activity for team member 4). Such an adaptive change of the process is centrally man- aged by the coordination layer, which has global knowledge about the status of all the devices and takes into account idle devices, operations that can be safely delayed, and so on.

Disconnection prediction Our predictive technique is based on four specific assumptions.

First, each device includes hardware that lets it know its communication dis- tance from the surrounding devices that are within radio range. This isn’t a very strong assumption, because specific techniques and methods are easily available—for example, TDOA (time difference of arrival), SNR (signal-to-noise ratio), and the Cricket compass.^4,5

The communication distance indicates how well two devices communicate; that is, it’s “virtual.” For example, assume

that to communicate, devices A and B use Wi-Fi, which has a maximum communication distance of approximately 100 meters. If A and B are 30 meters from each other but a wall is between them, the communication distance might be a calculated 90 meters. So, at the next time interval, the probability is high that the two devices will be out of range from each other (the same as if they were really 90 meters far away). Because we use the distance measurements only to calculate the probability of disconnections, we don’t need physical distances.

Note that even if two devices are 30 meters apart with no permanent obstacles between them, a truck could move between them, causing an unpredictable disconnection. Such an event is, in our model, analogous to a “down”—a device’s shutdown. Our research doesn’t address downs, and in the following, unless we state otherwise, we use “distance” to mean communication distance.

Second, no device in the MANEThas GPS hardware, because we’re interested in MANETs of low-profile devices, which normally aren’t equipped with GPS.

Third, at start-up, all devices are connected (that is, each device has a path—

possibly multihop—to any other device), and the pervasive architecture’s goal is to maintain these connections. Each device doesn’t have to be within range of any other device; that is, we don’t require a tight (one-hop) connection. We require only a loose connection, guar- anteed by appropriate routing protocols—for example, dynamic source rout-

ing or ad hoc on-demand distance vector routing. Figure 2a shows a tightly connected MANET. Figure 2b shows a typical start-up configuration: devices and aren’t within radio range (no line directly connects them in the figure), but they can communicate with each other through and . In the following, unless we state otherwise, “connection” means a loose connection.

Fourth, a specific device in the MANET, called the coordinator, centrally predicts disconnections. Because all devices can communicate at start-up and we aim to maintain such connections through prediction, our approach collects all information centrally from all devices. On the basis of the prediction, the coordination layer will enact specific actions to maintain the connection. The coordinator typically belongs to the team leader and hosts most of the coordination layer (for example, a blackboard for a CSCW tool or a workflow management system coordinating all activities). (Centralized control of network adaptation to maintain a connection, which is out of this article’s scope, appears feasible.⁶Such a process assumes that some devices will be idle or that some activities that devices are in charge of can be safely delayed;

that is, actions to remedy disconnection can preempt other activities.)

The predictive technique

At a given time t_i, in which all devices are connected, the coordinator collects all distance information from the other devices. (That is, given the four assumptions, each device sends the coordinator a message containing the distances to other devices within range.) On the basis of this information, the coordinator builds a probable next connection graph—that is, the probable graph at the

12 PERVASIVEcomputing www.computer.org/pervasive

(b) (a)

α

β

δ γ

Figure 2. Connections in a MANET: (a) In a tight connection, each device is one hop away from any other device. (b) In a loose connection, devices and aren’t within radio range but can communicate through and .

(4)

next time instant t_i+1highlighting the predicted connected and disconnected devices. Using the graph, the coordination layer enacts appropriate actions in the interval [t_i, t_i+1] to keep all devices connected at t_i+1.

To predict, at t_i, the next connection graph, our technique considers not only the current situation but also situations and predictions in the recent past (that is, at t_i1, t_i2, and so on). Specifically, it considers distances calculated in the recent past. So, even if the pervasive architecture guarantees that at each instant all devices are connected, our technique considers the MANET’s evolu- tion in a “free” scenario (that is, without remedial actions by the coordination layer) when predicting the next time period. The reasonable assumption is that if two devices tend to go out of range if not controlled but are connected through the coordinator’s remedial actions, this influences the next probability of going out of range.

Let’s look at our predictive technique in more detail. Given a couple of devices i, j,

is the distance between them at time t.

We can consider a time frame of h > 0 time units as the history of distances between devices i, j. Given h, we repre- sent the predicted distance between i and j at the next time unit as

(1) with k= k and

We use k/c weights to give a different importance to recent movements.

Observe that

Let S_devbe a constant representing a wireless technology’s maximum com- munication range. We assume that i and j communicate through the same tech- nology, which could be different for other pairs of devices. For example, if i is equipped with many communication channels such as infrared, Bluetooth, and Wi-Fi, it might communicate with j using Wi-Fi and with k using Bluetooth.

The estimated probability of devices (i, j) still being in range at t + 1 is

(2)

The closer two devices are (normalized by S_dev), the greater the probability of their being in range. Conversely, the more distant two devices are, the smaller the probability of their being in range.

The MGR algorithm

Our predictive algorithm, which we call the Mobile Gambler’s Ruin (MGR) algorithm (see figure 3), is based on the Markov chain model of the well-known gambler’s ruin problem. We based our study of device movement and the con- sequent distance prediction on Markov chains because a prediction’s success depends only on events in the previous time frames. Instead of using a Markov- ian process in the time domain, we focus on the spatial domain, and we build a matrix that’s similar to the one in the original gambler’s ruin model.

Consider a square matrix of |E| |E|

elements, where |E| = m, with m the total number of MANETmobile devices. We build M = (m_ij) as an m m symmetric matrix, in which

(see equation 2). The matrix is symmetric because

The diagonal elements will have the P( )( )_{i j}^t_,⁺ P_{j i}^t_,

( )( )⁺

1 = 1

m_ij =P( )( )_{i j}^t⁺

, 1

P

S

p t

p t i j

i j

i j ,

,

( ) ,

( )

+ ( ) ( )

( )+

+

=

−

1

S 1

S

dev dev

1 1

0 1

( ) ( )+

≤

>

⎧

⎨

⎪⎪

⎩

⎪⎪

( )

S

dev

S_p^t dev i j,

S_p

i j,

( ) ≥0

c=

∑

_k^h₌1^α_k

S S

p c

t k i j

t h k k

h

k k h

k i j,

,

( )

( )+ ^{− −}( )

=

=∑ = ⎛

∑

1 1

1

α α

α

⎝⎝⎜

⎞

⎠⎟

− −( )

∑= ^Si j t h k k

h 1 ,

S( )^t_{i j}_,

3 ddoo iiff Comps[i] = 0

4 tthheenn numcomps numcomps + 1 5 CCDFSG(M, i, numcomps, Comps[]) 6 rreettuurrnn Comps[]

SUB CCDFSG(M, i, numcomps, Comps [m]) 1 Comps[i] numcomps

2 ffoorr eeaacchh M[i, j] ≥ Beta 3 ddoo iiff Comps[j] = 0

4 tthheenn CCDFSG(M, j, numcomps, Comps[]) 5 rreettuurrnn NIL

PROGRAM TEST_CONNECTION(i, j, Comps[m]) 1 iiff Comps[i] = Comps[j]

2 tthheenn TEST true 3 eellssee TEST false 4 rreettuurrnn TEST

(5)

value 1 because

This is straightforward because a mobile device’s distance from itself is equal to 0.

The matrix will have this form:

(3)

We can consider M = (m_ij) as representing a graph where the set of nodes is E = {e₁, … ,e_m} and the set of arcs is A = {(i, j) | m_ij= P_{(i, j)} }, where 0 1 represents a probability threshold that should be set experimentally. Depending on the scenario, should be set to dif- ferent values, but it generally should be greater than or equal to one-half.

The MGR algorithm first finds the graph’s connected components (using the SUB CCDFSGprocedure). Then, it verifies if two devices e_iand e_jbelong to the same connected component (using the TEST_CONNECTIONprocedure). If they do, e_iand e_jwill still communicate in the next time unit; otherwise, they will lose their connection in the next time unit.

(The MGR algorithm’s output is the

Compsarray, which for each ith element has an integer value corresponding to the connected component to which it be- longs. For example, if a set of devices E = {e₁, …, e_m} form a graph with k connected components, the output vector might be of this kind: 0 0 … 1 … 2 … k 1. So, for e_iand e_j, we only have to test, using TEST_CONNECTION, whether they have the same value in the vector.)

Using this strategy, after building M = (m_ij), we can verify which devices are directly (that is, one hop) or indirectly (that is, multihop) connected to all other devices. Doing this will let the coordinator decide whether to act to maintain the connection between the involved devices. The coordination layer’s goal will be to have exactly one connected component in the graph.

For example, in figure 4, dark blue indicates the network topology before the task begins, where each device is connected with the others. The numbers close to the nodes represent the connected-component classes or values.

(Because the coordination layer was suc- cessful until this moment, all devices are in the same connected component of the graph.) Light yellow indicates the predicted topology at the next time unit, which splits into two connected components after the camera-equipped device moves. On the basis of such a matrix,

the coordinator could direct the bridge device of team member 4 in figure 1 to follow the other device.

Dealing with error

Techniques for evaluating the communication distance could introduce error. Because our model is based on a Markov chain made of communication distances between devices, and because the calculated distances could include an approximation error, this error could affect our model. Let’s assume that every

has an average error S compared to the real measure. Therefore, because our model is linear, S is spread over the measures but doesn’t depend on t; so

is actually

Indeed, the exact value of S depends on which technique we use to evaluate distance. But because this value is typically small compared to

this error only partially affects the prediction model’s average error.

Experimental results

To validate our prediction technique, we adopted the Obstacle Mobility Model,⁷which provides a mechanism for modeling movement in real-world

S_p( )^t+¹ S_p^t S

i j,

( )

( )+¹ _±_∆

S_p^t

i j,

( )

( )+¹

S( )^t_{i j}_,

1 1

1 2 1

2 1 2

1 2

P P

m m

, ,

( ) ( )

( ) ( ))

⎛

⎝

⎜⎜

⎜⎜⎜

⎞

⎠

⎟⎟

⎟⎟⎟

1 P_p^t m_ii

i i,

( )

( )+¹ ₌ ₌₁

Camera Stored pictures

Operator

Bridge

Team leader

0

0 0 0

0

1

Figure 4. The blue nodes represent the given network topology; the yellow nodes represent the predicted topology at the next time unit, which has split into two connected components after a camera- equipped device moves out of range of some of the other devices. The numbers are the connected-component classes.

(6)

environments. Such modeling includes obstacles and buildings and computes pathways connecting objects to specify the movement paths of nodes. The OMM Voronoi path computation takes as input the objects’ coordinates and then computes pathways that define regions in the simulation area. Each point in a region is closest to the same site (that is, object or building). In other words, the pathways are equidistant from the objects they lie between.

Our simulation environment area is 1,000µ 1,000µ, with µ = (1/100)Sdev. For instance, if we consider Wi-Fi technology, S_dev= 100 meters, so µ = 1 meter.

The mobility of nodes, unless we state otherwise, is randomly selected between 0 and 5 meters per second to represent walking speeds.

To evaluate characteristics of network topologies that the mobility model cre- ates, we randomly distribute nodes at the simulation’s beginning, but they’re all loosely connected. Moreover, we introduce random obstacles to make the scenario more realistic.

We developed the mobility model and the simulation environment on top of two well-known network simulators, NS and GloMoSim (figure 5 illustrates the visual simulation environment). We tested the MGR algorithm with the simulation environment implementing the OMM, under specific settings: two different sets of devices, a 5-device set and a 10-device set, with seven randomly placed obstacles (simulating damaged areas and buildings). We set a time frame of 2,000 seconds per experiment and per- formed 50 experiments, obtaining between 50,000 and 100,000 samples per experiment. Every sample was a snapshot of the device positions in the simulated environment at a given instant.

So, for every experiment, we computed the distances between devices and the

MGR predicted distances, obtaining approximately 500,000 samples. We chose time frames h of 5, 10, and 15.

Table 1 shows the aggregate results;

the worst difference between the real and predicted distances was less than 2.5µ, for both NS and GloMoSim. This means that MGR has a precision bound of 97.5 percent in predicting distances between mobile devices, for these particular settings and environments. (Because we set µ = (1/100)S_dev, the average difference represents our prediction algorithm’s percentage of error.) We obtained the best precision, approximately 99.5 per- cent, for h = 15. This is because the pre- diction’s precision increases (the error decreases) as the time frame increases.

However, in this case, the coordinator device must devote more space to maintain all the previous .

A pervasive architecture for supporting cooperation

Figure 6 shows our pervasive archi- tecture. Each device has a wireless stack consisting of a wireless network interface and the hardware for calculating distances from neighbors. On top, a network service interface offers to up- per layers the basic services for sending and receiving messages (through multihop paths) to and from other devices, by abstracting over the specific routing protocols.

Offered services (that is, specific applications supporting tasks of the devices’

human users) are accessible to other devices and can be coordinated and com- posed cooperatively. Some of these services are applications that don’t require human intervention (for example, an image-processing utility). Others act as S( )^t_{i j}_,

Table 1. The predicted distances’ average error, for three time frames h.

Avg. error

No. of devices Network simulator h = 5 h = 10 h = 15

5 NS 2.43 1.62 0.64

GloMoSim 1.94 1.01 0.51

10 NS 2.19 2.04 1.03

GloMoSim 2.54 1.67 0.76

(7)

16 PERVASIVEcomputing www.computer.org/pervasive N E T W O R K M A N A G E M E N T

Much research on mobility prediction has been for cellular phone systems.^1–6These approaches are based on Markov models, which predict a mobile user’s future on the basis of its current and past locations. The fundamental problem in these approaches is to predict whether a mobile user is leaving a cell area (that is, crossing cell boundaries) and which new cell it’s going to. Such information is useful for bandwidth reservation and for call admission control (that is, whether to let a user make or receive a call) to lower the probability of dropping a handoff during a call. To make these predictions, proposed algorithms generally include a combination of timing, speed, and movement information, and distance information between base stations and mobile users.

All communications between the backbone systems, which centrally calculate the prediction, and mobile users occur through base stations, which are the fixed centers of star topologies (see Figure A). In such systems, the wireless-network topology doesn’t change over time. Communications between a base station and all mobile users in the cell area are always one-hop, and communications between mobile users don’t occur directly but through base stations.

These assumptions don’t apply to MANETs (mobile ad hoc networks), which can have several network topologies over time and multihop communications between mobile devices. Furthermore, MANETs have no fixed devices (that is, base stations). Our approach takes into account such network peculiarities. It does employ a centralized model to predict connection and disconnection between mobile devices, but differently than approaches used in cellular-network systems. Also, it takes into account knowledge of all distances among mobile users, not only those between base stations and mobile devices. We want to always maintain exactly one connected component in the network, as in the cell area, but with several possible topologies.

William Su, Sung-Ju Lee, and Mario Gerla also propose using mobility prediction to improve ad-hoc-routing performance.⁷ Their mobility model uses GPS and an alternative method based on transmission power^8,9to estimate the link expiration time between adjacent mobile nodes. Unlike our approach, they use a local predictive algorithm that doesn’t consider global mobility and topology information. Ing-Ray Chen and Naresh Verma propose a class of autonomous, host-centric mobility prediction algorithms, in which each mobile host can predict the probability that it will move from its current location to the next location within a certain time period.¹⁰As with Su, Lee, and Gerla’s approach, prediction is local and the algorithm doesn’t take into account global topology information.

Finally, we believe that, to predict possible disconnections, future techniques could exploit not only device distances but also a mixture of time and spatial information.¹¹

REFERENCES

1. I.F. Akyildiz et al., “Mobility Management in Next-Generation Wireless Systems,” Proc. IEEE, vol. 87, no. 8, 1999, pp. 1347–1384.

2. V.W.S. Wong and V.C.M. Leung, “Location Management for Next-Gen- eration Personal Communications Networks,” IEEE Network, vol. 14, no.

5, 2000, pp. 18–24.

3. A. Bhattacharya and S.K. Das, “LeZi-Update: An Information-Theoretic Framework for Personal Mobility Tracking in PCS Networks,” Wireless Networks, vol. 8, nos. 2–3, 2002, pp. 121–135.

4. S. Choi and K.G. Shin, “Adaptive Bandwidth Reservation and Admission Control in QoS-Sensitive Cellular Networks,” IEEE Trans. Parallel and Dis- tributed Systems, vol. 13, no. 9, 2002, pp. 882–897.

5. B. Liang and Z. Haas, “Predictive Distance-Based Mobility Management for Multidimensional PCS Networks,” IEEE/ACM Trans. Networking, vol.

11, no. 5, 2003, pp. 718–732.

6. P.N. Pathirana, A.V. Savkin, and S. Jha, “Mobility Modelling and Trajec- tory Prediction for Cellular Networks with Mobile Base Stations,” Proc.

4th ACM Int’l Symp. Mobile Ad hoc Networking and Computing (MobiHoc 03), ACM Press, 2003, pp. 213–221.

7. W. Su, S.J. Lee, and M. Gerla, “Mobility Prediction and Routing in Ad hoc Wireless Networks,” Int’l J. Network Management, vol. 11, no. 1, 2001, pp. 3–30.

8. P. Agrawal, D.K. Anvekar, and B. Narendran, “Optimal Prioritization of Handovers in Mobile Cellular Networks,” Proc. 5th IEEE Int’l Symp. Per- sonal, Indoor and Mobile Radio Communications (PIMRC 94), vol. 4, IEEE Press, 1994, pp. 1393–1398.

9. B. Narendran, P. Agrawal, and D.K. Anvekar, “Minimizing Cellular Hand- over Failures without Channel Utilization Loss,” Proc. 1994 Global Com- munications Conf. (GLOBECOM94), vol. 3, IEEE Press, 1994, pp. 1679–1685.

10. R. Chen and N. Verma, “Simulation Study of a Class of Autonomous Host-Centric Mobility Prediction Algorithms for Wireless Cellular and Ad hoc Networks,” Proc. 36th Ann. Simulation Symp. (ANSS 03), IEEE CS Press, 2003, pp. 65–72.

11 R. Prakash and R. Baldoni, “Causality and the Spatial-Temporal Order- ing in Mobile Systems,” Mobile Networks and Applications, vol. 9, no. 5, 2004, pp. 507–516.

Related Work on Mobility Prediction

Mobile user Base station

Figure A. A star topology for a cellular phone network.

(8)

proxies for humans (for example, the service for instructing human users to follow a peer is a simple GUI that alerts the user by displaying a pop-up window on his or her device and emitting a signal).

On top of the network service inter- face, the coordinator presents the pre- dictive layer, which signals probable dis- connections to the coordination layer.

The predictive layer implements the technique we described earlier. The coordination layer manages situations when a peer is going to disconnect (for example, by signaling a specific device to “follow peer x”). For example, if the coordina- tion layer implements a workflow management system, then, on the basis of the current prediction, the coordination layer might restructure the workflow schema.

Our approach combines local connection management among devices with global management of both network topology and task assignment.

Local connection management consists of monitoring and checking one-hop communications between a device and its neighbors. It’s realized as special services running on handheld devices that implement techniques for estimating and calculating distances and relative positions (angle and direction) between a specific device and its direct neighbors.

Global management maintains a consis- tent state of the network and of each peer in the network. It manages the network topology (and its predicted next states) and the tasks each peer is in charge of, as well as services that peers offer (that is, it provides a service reg- istry). On the basis of that information, the coordinator applies algorithms for choosing a bridge (currently under investigation and design) and/or exe- cutes workflow task reassignment when needed. Our technique extends previous work (see the sidebar) by targeting support for cooperative work.

B

ecause our results are based on synthetic data, they’re only a preliminary validation of our approach. In the context of the Italian research project MAIS (Multi- channel Adaptive Information Systems, www.mais-project.it), we aim to further enhance our techniques. We plan to com- plete the coordination layer and validate

our approach in real scenarios. We’ll also address the issue of the approach’s fault tolerance. Our approach currently doesn’t cope with sudden downs of devices, which might be frequent in emergency scenarios and are critical if they affect the coordinator node. We also plan to evolve the coordination layer from a centralized to a distributed Coordination layer

Predictive layer

Network service interface

Wireless stack (802.11x, Bluetooth)

Mobile device j

Service 3 Service 4

the

AUTHORS

Fabio De Rosa is a PhD student in computer science in the Department of Com- puter Science and a research assistant in the Department of Systems and Computer Science at the University of Rome La Sapienza. His research interests include multi- channel and mobile adaptive information systems, cooperative information systems, workflow management, and Web Services. He received his MSc in computer science from the University of Rome La Sapienza. Contact him at the Univ. di Roma La Sapi- enza, Dipartimento di Informatica e Sistemistica, via Salaria 113 (2nd floor), 00198 Roma, Italy; derosa@dis.uniroma1.it.

Alessio Malizia is a research assistant and a PhD student in the Department of Com- puter Science at the University of Rome La Sapienza. His research interests include document analysis, computer vision and statistical pattern recognition, and mobile applications. He received his MSc in computer science from the University of Rome La Sapienza. Contact him at the Univ. di Roma La Sapienza, Dipartimento di Infor- matica, via Salaria 113 (3rd floor), 00198 Roma, Italy; malizia@di.uniroma1.it.

Massimo Mecella is a research associate and a lecturer in the Department of Sys- tems and Computer Science at the University of Rome La Sapienza. His research interests include service-oriented computing and interorganization processes, cooperative systems for e-government, mobile and adaptive information systems, and middleware technologies. He received his PhD in computer engineering from the University of Rome La Sapienza. Contact him at the Univ. di Roma La Sapienza, Di- partimento di Informatica e Sistemistica, via Salaria 113 (2nd floor), 00198 Roma, Italy; mecella@dis.uniroma1.it.

(9)

format (that is, having a subset of devices act as coordinators). This evolu- tion will be challenging; research on workflow adaptation is still in its in- fancy, even in a centralized scenario.

Clearly, the present centralized architecture might be a bottleneck, but the current dimensions of a typical MANETfor the considered scenarios (tens of devices) don’t pose critical scalability issues.

REFERENCES

1. D.P. Agrawal and Q.A. Zeng, Introduction to Wireless and Mobile Systems, Thomson Brooks/Cole, 2003.

2. J. Grudin, “Computer-Supported Cooper-

ative Work: History and Focus,” Computer, vol. 27, no. 5, 1994, pp. 19–26.

3. F. Leymann and D. Roller, Production Workflow: Concepts and Techniques, Pren- tice Hall, 2000.

4. N.B. Priyantha et al., “The Cricket Com- pass for Context-Aware Mobile Applica- tions,” Proc. 7th Ann. Int’l Conf. Mobile Computing and Networking (MobiCom 01), ACM Press, 2001, pp. 1–14.

5. D. Niculescu and B. Nath, “Error Charac- teristics of Ad hoc Positioning Systems (APS),” Proc. 5th ACM Int’l Symp. Mobile Ad hoc Networking and Computing (MobiHoc 04), ACM Press, 2004, pp.

20–30.

6. R. Müller, U. Greiner, and E. Rahm,

“AgentWork: A Workflow-System Sup- porting Rule-Based Workflow Adaptation,”

Data and Knowledge Eng., vol. 51, no. 2, 2004, pp. 223–256.

7. A. Jardosh et al., “Towards Realistic Mobil- ity Models for Mobile Ad hoc Networks,”

Proc. 9th Ann. Int’l Conf. Mobile Com- puting and Networking (MobiCom 03), ACM Press, 2003, pp. 217–229.

For more information on this or any other computing topic, please visit our Digital Library at www.

computer.org/publications/dlib.