A Bayesian Approach for Disconnection Managementin Mobile Ad-hoc Networks

Massimiliano de Leoni, Shah Rukh Humayoun, Massimo Mecella, Ruggero RussoDipartimento di Informatica e Sistemistica

SAPIENZA – Universita di RomaVia Ariosto, 25 - Roma (Italy)

{deleoni,humayoun,mecella,russo}@dis.uniroma1.it

Abstract

Mobile Ad-hoc Networks are used in many scenarios (e.g., emergency management) for supporting collab-orative work of operators. But this requires either (i) continuous connections, or at least (ii) the possibility toforesee that a device is going out and disconnecting. Therefore a basic problem is how to predict the possibledisconnections of devices, in order to let the upper layers appropriately address connection anomalies (e.g., eithertaking global remedial actions to maintain the network connected, or local ones to let the disconnecting deviceto go on for some time with its own work, e.g., cache important data needed for the following activities). In thispaper we present a bayesian approach to predict disconnections in MANETs, and validating experimental resultsthat show the viability of the approach.

Keywords: disconnection prediction, mobile ad hoc networks, cooperative work.

1 Introduction

A Mobile Ad hoc NETwork (MANETs) is a peer-to-peer(P2P) network of mobile nodes capable to communi-cate with each other without an underlying infrastruc-ture. Nodes can communicate with their own neighbors(i.e., nodes in radio-range) directly by wireless links.Anyway, non-neighbor nodes can anyway communicateby using other intermediate nodes as relays, which for-ward packets toward destinations. The lack of a fixedinfrastructure makes this kind of network suitable in allscenarios where it is needed to deploy quickly a networkbut the presence of access points is not guaranteed. Ex-amples are military applications, and more recently, per-vasive systems for process management [13].

In order to guarantee the coordination and data ex-change the nodes should be aware of the moment whenthey are going to disconnect from their MANETs (i.e.,there is not any neighbor – node in the radio range – towhich node is connected). Indeed, if nodes are alertedabout probable disconnections, some remedial actionscan be enacted:

local disconnection management – That is thenode can take autonomous – not requiring coordinationwith other nodes – remedial actions, e.g., to cache somedata that are needed for other tasks to be carried outwhile disconnected, or to disseminate to other nodes the

critical information it is storing that is crucial for theother nodes (so to let them working);

global disconnection management – where thenodes together coordinate, e.g., through an appropri-ate Process Management System [6] to be hosted on a“leader device”. Such a device acts as a central serverand rearranges nodes in a new configuration in whichnone is going to disconnect.

This paper introduces a new technique that permitsto predict when MANET nodes are going to disconnectfrom all of others and to become isolated. Accordingto the classification proposed in [17, 18], coordinationcan be viewed as being divided into three layers, eachdepending on those below: (i) communication, (ii) col-laboration and (iii) coordination. The lowest layer al-lows information sharing; collaboration permits partici-pants to collectively establish the shared goals; the latterensures to enact collaborative actions to achieve sharedgoals as efficiently as possible.

According to this classification, predicting discon-nections can be categorized as part of the commu-nication layer. Indeed, without predicting and han-dling disconnections, MANET communication wouldnot work and, consequently, collaboration and coordi-nation would be impossible

The rest of the paper is structured as follows. Thissection ends by illustrating an example about global

1

disconnection management where disconnection predic-tion may make sense.

Section 2 illustrates our approach: after sketchingthe assumptions and some basis of Bayesian filtering,it continues explaining how to predict when links falldown. Finally, it ends by describing the algorithm forbuilding an estimated next connection graph. Such agraph illustrates estimated MANET topology in the closefuture: nodes are MANET peers and arcs represent linksthat are estimated as active.

Section 3 describes OCTOPUS, the Virtual Environ-ment that has been used as emulation platform duringtesting. Section 4 shows some technical details of theactual implementation where Section 5 describes the ex-periments and following results. The paper concludeswith Section 7 where we report final comments in thelight of results and discuss future progression of thiswork.

1.1 A Motivating ExampleWe are currently working on an European-fundedproject, namely WORKPAD [3], that is in charge of de-signing and implementing a 2-level software infrastruc-ture to support cooperative works in disaster manage-ment scenarios. In complex emergency scenarios, dif-ferent teams, belonging to different organizations, needto collaborate. So, there exist the need of inter-team andintra-team coordination. The front-end level consists ofseveral teams, whereas the back-end is formed by theheadquarters. A single front-end community is consti-tuted by the operators of a team, equipped with mobiledevices, connected in an ad-hoc and peer-to-peer fash-ion, that carry on a process, in which the adaptivenessto connection/task anomalies is fundamental. Opera-tors may be humans or robots; therefore, teams may bemixed.

Every human team member is equipped with hand-held devices (PDAs) and communication technologies,and is in charge of specific tasks. Team includes alsospecial robots, e.g., UAVs - Unmanned Aerial Vehicles,that are intended only to ensure connectivity amongnodes, working as relays. In such a way we can seethe whole team as carrying on a process, and the dif-ferent teams (of the different organizations) collaboratethrough the exchange and integration of data. Differentdata sets are stored in the headquarters of organizationswhich are responsible for them.

Front-end operators access to the correspondingback-end server located at headquarters through privatedefined protocols. Here they can get or set informationwhich is relevant to the situation they are dealing with.At the same time, operators can query information pro-vided by other organizations. This feature is provided

by an underlying P2P network. Indeed, each and ev-ery headquarter exports data and their schema. Then,all these data sources are integrated in order to create asingle “virtual” data source. It does not make differenceto clients which servers actually provide those data.

As a more concrete example, consider a scenario ofarcheological disaster/recovery: after an earthquake, ateam is sent to the hit area to evaluate the state of arche-ological sites and of precarious buildings; the goal is todraw a situation map to schedule restructuring jobs. Atypical cooperative process to be enacted by the teamwould be as shown in Figure 1(a) (depicted as a UMLActivity Diagram).

The team leader has got installed specifichardware/software to connect to the back end to re-trieve all previously stored data details, including a mapof the site, the list of the most sensible objects locatedin the site, and precedent reports/materials, as well as toupdate the information about the emergency situation.

The team is considered as an overall MANET, inwhich the team leader’s device (requiring the most com-putational power, therefore usually a laptop) coordinatesthe other team members devices, by providing suitableinformation (e.g., maps, sensible objects, etc.) and as-signing activities.

Team members are equipped with hand-held de-vices (PDAs), which allow them to execute some op-erations but do not have too much computational power.Such operations, possibly provided through the supportof particular hardware (e.g., digital cameras, computa-tional power for image processing, main storage, clientsfor Geographic Information System, etc.), are offeredas software services to be coordinated. Team Member 1(using its device) could compile some specific question-naires (after a visual analysis of a building). This will beanalyzed by the team leader to schedule next activities,supported by specific softwares. Team Member 3 couldtake some pictures of the precarious buildings. FinallyTeam Member 2 is in charge of specific image process-ing tasks on previous and recent pictures (e.g., for firstidentification of architectural anomalies).

In this scenario, Team Member 2 is in charge at agiven point of matching the photos taken by Team Mem-ber 3 and the previous ones stored at back-end. PDAsare not so powerful that they can retrieve all photos andtemporally store. So, Team Member 3 must be con-nected to the team leader during the whole task exe-cution. Indeed, Team Leader provides a special hard-ware proxy allowing any member to connect to the backend. In theory, every member should not need to be con-nected, possibly through multi-hop paths, to any othermember at all times. But applications running on mem-ber devices have to get ensured that a connection always

Ubiquitous Computing and Communication Journal 2

(a) Process (b) Critical situation and adaptive management

Figure 1: Disconnection prediction for adaptive coordination in MANETs

exists between every couple of devices. They do nothave to be worried about disconnections: the Coordina-tion Layer will take care of them.

But in a particular scenario, as the one depicted inFigure 1(b), it could happen that the movement of theoperator/device equipped with the camera would resultin a disconnection from other devices/operators. TheTeam Leader device has got deployed a Prediction Layerbeing in charge of predicting disconnection. A Coordi-nation Layer is arranged above and is continually readyto receive disconnection alarms from the layer below. Itcould decide to instruct a possible “bridge”, a robot, togo after the disconnecting operator (i.e. his device), tomaintain the connection and to ensure a path between alldevices. Instructing a bridge device is just a way to han-dle disconnections: the coordination layer could con-sider more convenient, in some situations, to duplicaterequired data such that the going-to-disconnect node canbe performing assigned task, even if disconnected.

The example described above is a typical global dis-connection management. Indeed, actions for handlingdisconnections are centrally managed by the coordina-tion layer of the leader device. The leader device is ac-tually the “global entity” that has the knowledge aboutthe status of all operators/devices, and takes into accountidle devices, dependencies and operations that can andcannot be safely delayed, etc.

2 Bayesian Filtering for Discon-nection Prediction

Our predictive technique is based on few assumptions:

1. Each device is equipped with specific hardwarethat allows it to know its distance from the sur-rounding connected (i.e., within radio range) de-vices. This is not a very strong assumption, aseither devices are equipped with GPS or specifictechniques and methods (e.g., TDOA - time dif-ference of arrival, SNR - signal noise ratio, theCricket compass, etc.) are easily available. Pa-per [16] presents a precise technique to track mul-tiple wireless nodes simultaneously. It relies onmeasuring the position of tracked mobile nodesthrough radio interferometry. This is guaranteedto reduce significantly the error with respect toGPS. Nevertheless, the authors of paper [14] haverecently devised techniques to mitigate the errorwhen computing node position through GPS. In-deed, they performed experiments where the errorhas been reduced to 3 meters when nodes are notmoving and to 20 meters when nodes are at 80km/h.

2. At start-up, all devices are connected (i.e., foreach device there is a path - possibly multi-hop -to any other device). The reader should note thatwe are not requiring that each device is within theradio range of (i.e., one hop connection to) any

Ubiquitous Computing and Communication Journal 3

other device (tight connection), but we requireonly a loose connection (guaranteed by appropri-ate routing protocols, e.g., DSR, AODV, etc.).

3. A specific device in MANET, referred to as coor-dinator, is in charge of centrally predicting dis-connections. As all devices can communicate atstart-up and the ultimate goal of our work is tomaintain such connections through predictions, itis possible to collect centrally all the informationfrom all devices;

The predictive technique is essentially as follows: at agiven time instant ti the coordinator device collects alldistance information from other devices (for assump-tions (1) and (3)); on the basis of such information, thecoordinator builds a probable connection graph that isthe probable graph at the next time instant ti+1 in whichthe predicted connected devices are highlighted. On thebasis of such prediction, the coordinator layer will takeappropriate actions (which are no further considered inthe following of this paper).

2.1 Bayesian FilteringBayes filters [2] probabilistically estimate/predict thecurrent state of the system from noisy observations.Bayes filters represent the state at time t by a randomvariable Θt. At each point in time, a probability distri-bution Belt(θ) over Θt, called belief, represents the un-certainty. Bayes filters aim to sequentially estimate suchbeliefs over the state space conditioned on all informa-tion contained in the sensor data. To illustrate, let’s as-sume that the sensor data consists of a sequence of time-indexed sensor observations z1, z2, ...., zn . The Beli(θ)is then defined by the posterior density over the randomvariable Θt conditioned on all sensor data available attime t:

Belt(θ) = p(θ|z1, z2, ...zt) (1)

Generally speaking, the complexity of computingsuch posterior density grows exponentially over time be-cause the number of observations increases over time;the following two assumptions are needed for makingthe computation tractable:

1. The system’s dynamic is markovian, i.e., the ob-servations are statistically independent;

2. The devices are the only subjects that are capableto change the environment.

On the basis of the above two assumptions, the equa-tion in a time instant t can be expressed as the combina-tion of a prediction factor Belt−1(θ) (the equation inthe previous time instant) and an update factor that on

the basis of the observation in the time instant t, realizesthe update of the prediction factor.

In our approach, the random variable Θt belongs to[0, 1] and we use the Beta(α,β) function as a belief dis-tribution to model the behavior of the system, accordingto the following equation:

Belt(θ) = Beta(αt, βt, θ) (2)

where α and β represent the state of the system and varyaccording to the following equations:

{αt+1 = αt + zt

βt+1 = βt + zt(3)

In our approach, the observation zt represents thevariation of the relative distance between nodes (i,j) nor-malized with respect to radio range in the time period[t-1,t]. It is used to update the two parameters α and βof the Beta function according to Equation 3. The eval-uated Beta(α, β) function predicts the value of θ

(i,j)t+1

estimating the relative distance that will be covered bythe nodes (i,j) in the next time period [t,t+1].

2.2 Prediction of the DistancesOur approach relies on clock cycles whose periods areT . The pseudo-code for the coordinator is described inFigure 2. We assume the iBuffer data structure to bestored only at Team Leader and accessed only by localthreads in a synchronized way. For each ordered couple(i, j) of nodes, in the n-th cycle, the monitor stores twofloat parameters, α

(i,j)n and β

(i,j)n , and the last observed

distance d(i,j)n−1.

Let us assume a node k comes in a MANET duringthe m-th clock cycle. Then, for each MANET node j weinitialize α

(k,j)m = β

(k,j)m = 1. In such a way we get

the uniform distribution in [0, 1] and, so, every distanced(k,j)m+1 gets the same probability.

For each time period T , each generic node i sends aset of tuples (i, j, dj) to the coordinator, where j is anunique name of a neighboring node and dj is the dis-tance to j. The coordinator collects continuously suchtuples (i, j, dj) coming from the nodes in an intermedi-ate buffer. We do no assumptions about clock synchro-nization. So, every node collects and sends informationto Team Leader according to its clock, which is in gen-eral shifted with respect to the one of other nodes.

Monitor performs prediction according to the sameclock T : at the beginning of the generic n-th clock cycleupon timer expiring, it copies the tuples (i, j, dj

n) fromthe intermediate buffer to another one and, then, it emp-ties the former buffer to get ready for updated values. Inthe clock cycle, for each collected tuple (i, j, dj) moni-tor updates the parameters as follow by a bayesian filter:

Ubiquitous Computing and Communication Journal 4

timer: a timer expiring each T seconds.iBuffer[x,y]: a bi-dimensional squared matrix storing distance among couples of nodes X and Y.bayesianBuffer[x,y]: a bi-dimensional square matrix storing a triple (α, β, distance) for each couple of nodes X and Y.

UPON DELIVERING BY NODE I OF TUPLE(i, j, dist)1 iBuffer[i, j] ← dist

UPON EXPIRING OF TIMER()1 localBuffer ← iBuffer[i, j]2 /*empty intermediate buffer*/3 for (i, j) ∈ ibuffer4 do ibuffer[i, j] ← RADIO RANGE56 for (i, j) ∈ localBuffer7 do if localBuffer[i, j] ← RADIO RANGE8 then observation ← 19 else observation ← (localBuffer[i, j]− bayesianBuffer[i, j].distance)/RADIO RANGE

10 observation ← (observation + 1)/211 bayesianBuffer[i, j].distance ← localBuffer[i, j]12 bayesianBuffer[i, j].alpha ← u ∗ bayesianBuffer[i, j].alpha + observation13 bayesianBuffer[i, j].beta ← u ∗ bayesianBuffer[i, j].beta + (1− observation)

Figure 2: Pseudo-codes of the Bayesian algorithm for predicting node distances.

{α

(i,j)n+1 = u · α(i,j)

n + o(i,j)n

β(i,j)n+1 = u · β(i,j)

n + (1− o(i,j)n )

(4)

where o(i,j)n is an observation and u ∈ [0, 1] is a constant

value. Constant u aims for permitting old observationsto age. As new observations arrive, the previous getsless and less relevance. Indeed, old observations do notcapture the updated status of MANET connectivity andmotion.

The value for observation can be computed from therelative distance variation between i and j, scaled withradio-range:

∆dr(i,j)n =

d(i,j)n − d

(i,j)n−1

radio range(5)

where radio range is the maximum distance fromwhere two nodes can communicate with each other.

Possibly d(i,j)n can miss in the cycle n. The distance

between i and j could miss because i and j are not inradio-range or packets sent by i to Team Leader are lostor delivered lately.

It is straightforward to prove ∆dr(i,j)n to range in

[-1, 1] interval. This range is not suitable for Bayesianfilter since observations should be between 0 and 1. Sowe map the value in Equation 5 into the suitable range[0, 1] as follows1:

o(i,j)n =

{d(i,j)n −d

(i,j)n−1

radio range dn and dn−1 are available

1 if dn is unavailable12 if dn is available but dn−1 is not

(6)In sum, our Bayesian approach estimates the vari-

ation of the future distance between every couple of

nodes, normalized in the [0, 1] range. Values greaterthan 0.5 mean nodes to drift apart and smaller valuesto move closer. If the value is equal to 0.5, node i isestimated not to move with respect to j.

The parameters α and β are the inputs forBeta distribution Beta(α, β), where the expectationθ(i,j)n+1 = E

(Beta(α(i,j)

n+1, β(i,j)n+1)

)is the variation of the

distance between i and j in radio-range percentage thatwill be estimated at the beginning of (n + 1)-th clockcycle.

At this stage we can estimate the distance betweennodes i and j at the beginning of (n + 1)-th clock cy-cle. That can be done from Equation 6 by replacing theobservation term o

(i,j)n with the estimated value θ

(i,j)n+1 .

Hence:

ed(i,j)n+1 = d

(i,j)n + f∆d

(i,j)

n =

= d(i,j)n + (2θ(i,j) − 1) ∗ radio range

(7)

It should hold d(i,j)n = d

(j,i)n ; so, it should be

d(i,j)n+1 = d

(j,i)n+1. But we have to consider d

(i,j)n+1 6= d

(j,i)n+1.

Indeed distance sent by i about distance (i, j) can differfrom what is sent by j about the same distance. This iswhy distances are collected at beginning of clock cyclesbut these can be shifted.

Therefore, estimated distance di,jn+1 is computed

by considering both di,jn+1 and d

(i,j)n+1, through different

weights.

di,jn+1 = rel

(i,j)n+1 ∗ d

(i,j)n+1 + rel

(j,i)n+1 ∗ d

(j,i)n+1

where rel(i,j)n+1 is a factor for the estimation

reliability and it is inversely proportional to1If a node has entered in this cycle we assume o

(i,j)n = 0.5, i.e., it is not moving.

Ubiquitous Computing and Communication Journal 5

σ(i,j)n+1 =

√V ar(Beta

(α

(i,j)n+1, β

(i,j)n+1)

):

rel(i,j)n+1 =

1

σ(i,j)n+1

1

σ(i,j)n+1

+ 1

σ(j,i)n+1

=σ

(j,i)n+1

σ(i,j)n+1 + σ

(j,i)n+1

.

2.3 Connected Components ComputationDisconnection prediction depends on a parameter γ,which stands for the fraction of the radio-range forwhich the predictive technique does not signal a discon-nection anomaly2. Let be P (disc

(i,j)n+1) = P (d(i,j)

n+1 ≥γradio range); two nodes i and j are predicted goingto disconnect if and only if

rel(i,j)n+1 ∗P (disc

(i,j)n+1)+ rel

(j,i)n+1 ∗P (disc

(j,i)n+1) >

12

(8)

i.e. two nodes i and j are estimated disconnecting ifit is more probable their distance to be greater thanγradio range rather than distance to be smaller thansuch a value. We could tune more conservativeness bylowing γ (i.e. the fraction of radio-range in which dis-connections are not predicted). If we consider Equa-tion 7, then:

P (disc(i,j)n+1) = P (

˛d(i,j)n

radio range+ (2θ(i,j) − 1)

˛≥ γ)

= P`θ(i,j) ≥ 1+γ

2− d

(i,j)n

2∗radio range

´

(9)where the last term in Equation 9 is directly computablefrom the estimated beta distribution:

P (θ(i,j) > k) =∫ 1

k

Beta(α(i,j), β(i,j)

)

Once the algorithm predicts which links exist atthe next cycle, we can compute easily the connectedcomponents (i.e., sets of nodes that are predicted tobe connected). Afterwards, on the basis of the con-nected components, disconnection anomalies are iden-tified by the monitor. Finally, they are notified either tothe nodes (if a local management strategy is adopted) orto a coordination layer (if a global management strat-egy is adopted). Connected components are computablethrough “The Mobile Gamblers Ruin Algorithm” below,where an edge between couples of nodes in the connec-tion graph exists if Equation 8 is false.

2.4 The Overall TechniqueOur predictive algorithm, called as the “The MobileGambler’s Ruin” (MGR) algorithm, is taken from the

Markov chain model of the well known gambler’s ruinproblem [10, 11]. Such a study of the device move-ments and the consequent distance prediction is basedon Markov chains, because the success of a predictiondepends only on events of previous time frame units. In-stead of using a markovian process in time domain, weare going to focalize on spatial domain and we will builda matrix, which is similar to the one presented in theoriginal gambler’s ruin model but with other elements.

Let’s consider a square matrix of |E| × |E| el-ements, where |E| = m, with m, with m isthe total number of mobile devices in the MANET.We build M = (mij) as a m × m symmet-ric matrix, in which mij = 1 is the Equation 8is false or, otherwise mij = 0 if the equation istrue3. Every diagonal element mii = 1 since theP (disc

(i,j)n+1) = P (disc

(j,i)n+1) = 0. That follows for

definition: the distance of a mobile device from itself isalways equal to 0.

The matrix M = (mij) can be considered as theAdjacency matrix of an (undirected) graph where theset of nodes are devices and an arc exists between twonodes if they are foreseen as direct neighbors.

The strategy of the MGR algorithm, which is de-scribed in Figure 3, is to find the connected compo-nents of the graph (using the CCDFSG procedure),and then, by giving two devices ei and ej , to verifyif they belong to the same connected component (theTEST CONNECTION function); if it is true then ei,ej will still communicate in the next time period; elsethey will lose their connection within the next timeperiod. Using this strategy, after building the matrixM = (mij), we can verify which devices are con-nected, directly (i.e., one hop) or indirectly (i.e., multihop), and thus let decide when disconnection manage-ment techniques should be activated in order to keep theconnection between the involved devices. The aim ofsuch techniques should be to have a unique connectedcomponent in the graph.

The MGR algorithm computes the connected com-ponents starting from the matrix that represents thegraph. The output of the MGR program is the Compsarray in which for each i-th element there is an inte-ger value corresponding to the connected componentit belongs. For example, if we have a set of devicesE = {e1, ..., em} and they form a graph with k con-nected components, we will have an output vector ofthis shape:

(0 0 . . . 1 . . . 2 . . . k − 1

)(10)

2As an example, in IEEE 802.11 with 100 meters of radio-range, γ equal to 0.7 means that for a communication distance of 70 meters theprediction algorithm signals a probable disconnection.

3The matrix is of course symmetric since always there holds mij = mji

Ubiquitous Computing and Communication Journal 6

FUNCTION MGR()1 numcomps ← 02 Comps ← newArray of integer[m];3 for i ← 0 to (m− 1)4 do if Comps[i] = 05 then numcomps ← numcomps + 16 Comps[i] ← numcomps7 CCDFSG(M, i, numcomps, Comps[])8 return Comps[]

SUB CCDFSG(M, i, numcomps, Comps[])1 for i ← 0 to (m− 1)2 do if Comps[j] = 0 and M [i, j] = 13 then numcomps ← numcomps + 14 CCDFSG(M, j, numcomps, Comps[])5

FUNCTION TEST CONNECTION(i, j, Comps[])1 if Comps[i] = Comps[j]2 then TEST ← true3 else TEST ← false4 return TEST

Figure 3: Pseudo-Code of the MGR algorithm.

Thus for two different devices ei, ej we have only totest, using the TEST CONNECTION program, if theyhave the same value in the vector (10), It will give us aconfidence about the probability of being still connectedin the next time period.

3 The OCTOPUS Virtual Environ-ment

We implemented and deployed a fully-fledged versionof the algorithm, which is running on PDAs, laptops etablet PCs. The aim is to test a real implementation inorder to get realistic results, instead of having informa-tion from simulations. On the other hand, on-spot test-ing may be expensive both in terms of resources andtime: several persons are required to be arranged in awide area. That might need much time (and, thus, highcost) to prepare the whole test-bed. Furthermore, fieldtesting does not provide a controlled environment andit should be used just as the final user validation of thesystem.

Therefore, we test the implementation through em-ulation. We used OCTOPUS [4], an emulator, which wehave implemented, specifically targeted for MANETs 4.

OCTOPUS keeps a map of virtual areas, which userscan design and show by a GUI. Such a GUI enables theusers to put in that map the virtual nodes and bind eachone to a different real device. Furthermore, users canadd possible existing obstacles in a real scenario: ruins,walls and buildings.

OCTOPUS benefits are that real devices are complete

unaware of it: so when a node send packets, it believesto send them to the specified destination. But they arecaptured by OCTOPUS, playing a gateway role. OCTO-PUS analyzes the sender and receiver: the distance of thecorresponding virtual nodes in the virtual map (basicallywhether in the radio-range), the probability of losses,obstacles screening direct view5, motion speed and soon. According to such parameters, it decides whetheror not to deliver each packet to the recipient. Since thenodes are basically unaware of OCTOPUS, it is possibleto remove it and deploy finally the software with no orvery limited changes.

4 Technical Details

We implemented the Bayesian algorithm on actual de-vices. We coded in MS Visual C# .NET as it enables towrite applications once and deploy them on any devicefor which a .NET framework exists (PCs and PDAs in-cluded). In this section, we describe the technical detailsof packages and classes for implementing the Bayesianalgorithm.

We can identify two sides in the implementation asdescribed in Figure 5: the code running on the coordina-tor device, which realizes the prediction, and the one onthe generic peers sending information about neighborsto the coordinator.

The code of generic peers is conceptually easy. It isbasically composed of two modules:

it.uniroma1.dis.Octopus. We tested our algorithmby OCTOPUS. OCTOPUS is intended to emulate small

4OCTOPUS can be downloaded at www.dis.uniroma1.it/∼deleoni/Octopus5We assume whenever two nodes are not directly visible, every packet sent by the first node to the second is always dropped.

Ubiquitous Computing and Communication Journal 7

Figure 5: The components of the actual implementation.

Ethernet LAN

Laptop(Mobile Node)

PDAs(Mobile Nodes)

Laptop(Coordinator)

AccessPoint

Octopus Server

Tablet(Mobile Node)

Tablet(Mobile Node)

Figure 6: The test bed setting.

Ubiquitous Computing and Communication Journal 8

MANET and holds a virtual map of the are where nodesare arranged. Every real device is mapped to a virtualnode in the map. This module is intended to query OC-TOPUS in order to know neighbors and their distance. Itallows also to send special commands to OCTOPUS dur-ing run-time emulation. In such a way modes can vir-tually move in the virtual map. That causes topology tochange at any time and, therefore, new disconnectionsare continuously predicted.

BayesianPredClient. This module includes inter-nally two timers. The first timer has a clock T, where Tis the same as defined in Figure 2. For each clock pe-riod, it gets information about neighbors (who and howfar they are) by using the it.uniroma1.dis.Octopus mod-ule. Then, it arranges such an information in a properpacket, which is sent to coordinator. Upon expiring ofthe second timer, the client sends a command to OCTO-PUS to change the position of the node which this de-vice is mapped to. Of course, this timer uses also theit.uniroma1.dis.Octopus module.

The code of the coordinator’s implementation has asits core the BayesianPredServer module. In order to de-tail more, we have exploded it to its five classes:

DistanceServer. This module implements a TCP/IPserver to retrieve the neighboring information frompeers (sent by them through the module BayesianPred-Client). At the same time, it stores retrieved informationin the intermediate buffer, which is implemented by themodule Buffer. It corresponds to event handler for upondelivering of a tuple from a peer as defined in Figure 2.

Buffer. It implements the intermediate buffermodule, written by the DistanceServer module andread/made empty by PredictiveTimer. This moduleguarantees synchronized accesses.

PredictiveTimer. This is a timer that repeats each Tseconds. It implements the event upon expiring of timeras defined in Figure 2. Consistently to the pseudo-code,it accesses to the Buffer module to get new informationfrom other peers, as well as the BayesianBuffer module.The latter module stores the information to compute foreach couple of nodes the Equations 4 e 6. This moduleuses also the it.dis.uniroma1.Octopus module. Indeed,Team Leader is a node itself and it can lead to discon-nections. Therefore, it has to ask for neighbors to OC-TOPUS and predict distances to any other node.

BayesianBuffer, BayesianTuple. The Bayesian-Buffer class handles and stores the triple(α(i,j),β(i,j),d(i,j)

), each one represented by a

BayesianTuple object.

5 ExperimentsFigure 6 shows the testbed, which consists of ten ma-chines (PCs and PDAs). One of them hosts OCTOPUSand, hence, it does not represent a real mobile node.Each of the other machines is bound to a different virtualnode of OCTOPUS’ virtual map.

We set the testing virtual map as 400 × 300 meterswide and communication radio-range as 100 meters. Atthe beginning, nodes are located into the virtual map in arandom fashion in order to form one connected compo-nent. Afterwards, each S seconds, every node choosesa point (X ,Y ) in the map and begin heading towards ata speed of V m/s. Both S and V are Gaussian randomvariables: the mean and variance are set as, respectively,450 and 40 seconds for S and 3 and 1.5 m/s for V . Thecouple (X ,Y ) is chosen uniformly at random in the vir-tual map. Of course, devices used in tests do not moveactually: nodes move only in the virtual map. For thispurpose, devices send particular commands to a specificOCTOPUS socket for instructing node motions.

The first set of experiments has been intended to ver-ify which error in percentage is obtained for differentvalues of clock period T . The error here is defined asthe gap between the estimated distances dn at (n−1)-thclock cycle and the actual measures dn at n-th clock cy-cle. The value is scaled with respect to the radio-range:

The Figure 7(a) shows the outcome for the clockperiods equal to 15, 20, 30, and 45 seconds. We haveset the parameter u of Equation 4 to value 0.5 and per-formed ten tests per clock period. Every test was 30minutes long. The results show, of course, that the errorpercentage grows high as clock period increases. Prob-ably the most reasonable value for real scenarios is 30–45 seconds (smaller values are not practically feasiblesince MANETs would be probably overloaded by “dis-tance” messages). Please consider the greatest clock pe-riod we tested: the error ranges between 24.34% and26.8% (i.e., roughly 25 meters).

Afterwards, in a second tests set, we fixed clock pe-riod to 30 seconds, testing for u equal to 0.01, 0.05,0.1, 0.2, . . . , 0.8. We even tripled the frequency whichnodes start moving with. The outcomes are depicted inFigure 7(b), where x-axis corresponds to u values andy-axis to the error percentage. The trend is parabolic:the minimum is obtained for u = 0.3 where the erroris 17.44% and the maximum is for u = 0.8 where theerror is 21.54%. Small values for u mean that the past isscarcely considered whereas large values mean the pastis strongly taken into account. This matches our expec-tation: we get the best results for the intermediate val-ues. That is to say that the best tuning is obtained whenwe consider the past neither too little nor too much.

Concerning coordination, applications can rely on

Ubiquitous Computing and Communication Journal 9

0,00%

2,50%

5,00%

7,50%

10,00%

12,50%

15,00%

17,50%

20,00%

22,50%

25,00%

15 20 30 45

Polling time

Th

e er

ror

per

cen

tag

e

Best Case

Worst Case

(a) The smallest and largest measured error in percentage, chang-ing clock periods.

20,30%

19,55%

19,02%

18,09%

17,44%17,59%

18,28%

19,03%

19,94%

21,53%

17,00%

17,50%

18,00%

18,50%

19,00%

19,50%

20,00%

20,50%

21,00%

21,50%

22,00%

0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

u

Th

e er

ror

per

cen

tag

e

(b) The measured error in percentage, changing the weight ofpast observations.

Figure 7: Experiment results.

such predictions. Indeed, setting polling time to 30 sec-onds, we have got errors around 18% for u = 0.3. Ifrange is supposed to be 100 meters, the mean error isaround 18 meters. Considering this is a preliminary val-idation, these values are quite good. Indeed, if we setγ = 0.75 (i.e., disconnections are predicted when nodesare more than 75 far), we would be sure to predict everyactual disconnection. That means no disconnection isnot handled, although coordination layer (distributed orcentralized, local or global) will be alerted about somefalse negatives, enacting recovery actions to handle un-real disconnections.

We remark that this only a preliminary validation;we are working on more detailed experiments. In newtest sets, we will be evaluating directly disconnectionpredictions: varying γ, how many disconnections arepredicted and among them how many are real. We willbe analyzing, as well, how many actual disconnectionsare not predicted on time.

6 Related Work

Much research on mobility prediction has been carriedon (and still it is in progress) for cellular phone sys-tems [1, 8]. These approaches are based on Markovmodels, which predict the mobile user future’s locationon the basis of its current and past locations. The aim isto predict whether a mobile user is leaving a current cell(crossing the cell boundaries) and the new cell where

she is going. Such an information is then used for chan-nel reservation in the new cell. Anticipating reservationshould lower the probability of a call to be dropped dur-ing handoff 6 due to the absence of a free channel for thecall in the new cell.

The main differences with our approach are relatedto different scenarios: MANETs versus mobile phonenetworks. Indeed, peculiarities of MANETs consist inthe higher mobility compared with phone networks. InMANETs, links between couples of devices disappearvery frequently. That does not happen in phone cells,which are very big: leaving a cell and entering into anew is rare with respect to how often MANET links fallsdown.

We use a centralized approach like in cellular net-work where a coordinator collects information to allowprediction. The difference is that our approach takesinto account the knowledge of all distances among allusers. Indeed, we do not have any base station; there-fore, we do not have just to predict the distance of anymobile device to it. We are interested in the distancefrom any device to whichever else.

In the literature, several approaches predict the stateof connectivity of MANET nodes. The most common ap-proaches assume that some of nodes are aware of theirlocation through GPS systems in order to study nodemotions and predict disconnections. In [19] the authorsperform positioning in a network using range measure-ments and angle of arrival measurements. But theirmethod requires a fraction of nodes to disseminate their

6In cellular telecommunications, the term handoff refers to the process of transferring an ongoing call or data session from one channelconnected to a core network or cell to another.

Ubiquitous Computing and Communication Journal 10

location information such that other nodes can triangu-late their position. In [20] the probability that a con-nection will be continuosly available during a period oftime is computed only if at least one node knows its po-sition and its speed through GPS. Our approach is moregeneric as it does not require any specific location tech-niques: every hardware allowing to know node distancesis fine.

In [9], MANETs are considered as a combinationof clusters of nodes and it studies the impact (i.e., theperformances) of two well defined mobility predictionschemes on the temporal stability of such clusters; un-like our approach the authors use the pre-existing pre-dictive models while the novelty of our approach con-sists in the formalization of a new model based onBayesian filtering techniques. In [21] neighbor predic-tion in MANETs is enacted through a suitable particle fil-ter and it uses the information inside the routing table ofeach node. Routing table is continuously updated by theunderlying MANET protocol. The first drawback is thatit can operates only with those protocols that work byupdating routing tables. Since it is based only on rout-ing table updates, it predicts how long couples of nodesare going to be connected on the basis of how long theyhave been connected in the past. It does not considerwhether couples of nodes are moving closer or drift-ing apart, nor node motion speed. Our approach takessuch an information also into account, making predic-tion more accurate.

[7] addresses the issue of robot location estimation.For each position pi and each robot rj , the techniquegives the probability for rj to be in pi. This approachcannot be easily used to compute when nodes are goingto disconnect.

7 Conclusion and Future WorksIn this paper, we have proposed, implemented andtested a novel technique for predicting disconnectionsin MANETs. We think prediction is a basic block for anymiddleware for coordination in MANET settings.

Collaboration and coordination among MANETnodes could not take place when they cannot commu-nicate. Since MANETs are very dynamic, nodes are con-tinuously moving and that can cause several disconnec-tions. If disconnections were not handled, communica-tion could not take place and, consequently, coordina-tion. Remedial actions (either local or global) need tobe enforced in advance (i.e., predicted) against the ac-tual disconnection.

This work is the basis of the developmentof a coordination system for MANETs in emer-gency management – cfr. the WORKPAD project

(http://www.workpad-project.eu) we arecurrently involved, as our plans are to build a globalmanagement approach in which, after predicting dis-connections, the coordination middleware instructs de-vices on how to arrange differently their tasks in orderto keep the MANET connected.

We are realizing such a middleware: our first resultsconsist in a general recovery method to detect and copewith any unpredictable event (see [5]) which changesthe environment where the process is executed. Theseevent may be such that the process cannot be carried onany longer. Therefore, we plan to apply the describedprediction technique to such a middleware, as discon-nections represent unforeseeable events.

Future works include the evaluation in very unreli-able environments where information pieces could belost. We plan, as well, to distribute prediction among allnodes which participate actively to the prediction. Thisshould make the prediction layer more reliable as it doesnot have to rely on any special node (e.g., Team Lead-ers), which could crash. Moreover, distributing com-putational load among all devices permits to balancebattery consumption. Indeed, every node consumesroughly the same energy amount, instead of having onlya central node to consume its battery.

References[1] I. F. Akyildiz, J. S. M. Ho, and Y. B. Lin.

Movement-based Location Update and SelectivePaging for PCS Networks. IEEE/ACM Transac-tions on Networking, 4(4):629 - 638, 1996.

[2] J. O. Berger. Statistical Decision Theory andBayesian Analysis. Springer, 1985.

[3] T. Catarci, M. de Leoni, F. De Rosa, M. Mecella,A. Poggi, S. Dustdar, L. Juszczyk, H.L. Truong, G.Vetere. The WORKPAD P2P Service-Oriented In-frastracture for Emergency Management In Proc.of the 3rd IEEE International Workshop on Col-laborative Service-Oriented P2P System (COPS)at WETICE 2007, 2007.

[4] F. D’Aprano, M. de Leoni, and M. Mecella. Em-ulating Mobile Ad-hoc Networks of Hand-heldDevices. The OCTOPUS Virtual Environment. InProc. of the International ACM Workshop on Sys-tem Evaluation for Mobile Platforms (MobiEval),2007.

[5] M. de Leoni, M. Mecella, G. De Giacomo. HighlyDynamic Adaptation in Process Management Sys-tem through Execution Monitoring. In Proc. of

Ubiquitous Computing and Communication Journal 11

the 5th Internation Conference on Business Pro-cess Management (BPM 2007), 2007.

[6] M. de Leoni, F. De Rosa, M. Mecella. MOBIDIS:A Pervasive Architecture for Emergency Manage-ment. In Proc. of the 4th International Workshopon Distributed and Mobile Collaboration (DMC2006) (at WETICE 2006), 2006.

[7] D. Fox, J. Hightower, L. Lao, D. Schulz, and G.Borriello. Bayesian Filters for Location Estima-tion. In IEEE Pervasive Computing, 2(3):24 - 33,2003.

[8] B. Liang, and Z. J.Haas. Predictive Distance-basedMobility Management for Multidimensional PCSNetworks. IEEE/ACM Transactions on Network-ing, 11(5):718 - 732, 2003.

[9] A. Venkateswaran, V. Sarangan, N. Gautam, andR. Acharya. Impact of Mobility Prediction on theTemporal Stability of MANET Clustering Algo-rithms. In Proc. of the 2nd ACM InternationalWorkshop on Performance Evaluation of WirelessAd hoc, Sensor, and Ubiquitous Networks (PE-WASUN ’05), 114 - 151, 2005.

[10] W. Feler. An Introduction to Probability Theoryand its Applications (2nd ed.). Willey, 1966.

[11] G. Harik, E. Cantu-Paz, D. E. Goldgerg, and B. L.Miller. The Gambler’s Ruin Problem, Generic Al-gorithms, and the Sizing of Populations. In Proc.of the IEEE International Conference on Evolu-tionary Computation, 1997.

[12] A. Jardosh, E. M. BeldingRoyer, K. C. Almeroth,and S. Suri. Towards Realistic Mobility Models forMobile Ad-hoc Networks. In Proc. of MobiCom,2003.

[13] G. Hackmann, R. Sen, M. Haitjema, G. C. Roman,and C. Gill. MobiWork: Mobile Workflow forMANETs. Technical Report WUCSE-06-18, Wash-ington University, Department of Computer Sci-ence and Engineering, St. Louis, Missouri, 2006.

[14] D. Hadaller, S. Keshav, T. Brecht, and S. Agar-wal. Vehicular Opportunistic Communication Un-der the Microscope. In Proc. of the 5th Interna-tional Conference on Mobile systems, Applicationsand Services (MobiSys), 2007.

[15] R. J. Punnoose, P. V. Nikitin, and D. D. Stancil.Efficient Simulation of Ricean Fading Within aPacket Simulator. In Proc. of the 52th IEEE Ve-hicular Technology Conference, 2000.

[16] Branislav Kusy, Jnos Sallai, Gyrgy Balogh, kosLdeczi, Vladimir Protopopescu, Johnny Tolliver,Frank DeNap, and Morey Parang. Radio interfero-metric tracking of mobile wireless nodes. In Proc.of the 5th International Conference on Mobile sys-tems, Applications and Services (MobiSys), 2007.

[17] Thomas W. Malone, Kevin Crowston. The Inter-disciplinary Study of Coordination. In ACM Com-puting Surveys, Vol. 26, No.1, March 2004.

[18] Mark Klein. Coordination Science: Challengesand Directions. In Proc. of the workshop onCoordination Technology for Collaborative Appli-cations - Organizations, Processes, and Agents(ASIAN), 1996.

[19] Dragos Niculescu, Badri Nath Position and Orien-tation in ad hoc Networks In Elsevier Journal ofAd Hoc Networks, Vol. 2, No.2, April 2004.

[20] Min Qin, Roger Zimmerman, Leslie S. Liu Sup-porting Multimedia Streaming Between MobilePeers with Link Availability Prediction In Proc.the 13th annual ACM International Conference onMultimedia, 2005.

[21] Ovidiu V. Drugan, Thomas Plagemann, EllenMunthe-Kaas Non-intrusive Neighbor Predictionin Sparse MANETs In Proc. of 4th Annual IEEECommunications Society Conference on Sensor,Mesh and Ad Hoc Communications and Networks(SECON’07), 2007.

Ubiquitous Computing and Communication Journal 12