Ad Hoc Networks

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

39

A Probabilistic Approach for Managing Mobile Ad-Hoc Networks Remi Badonnel, Radu State, Olivier Festor

Abstract— A pure management approach where all the nodes are managed at any time is too strict for mobile ad-hoc networks. Instead of addressing the management of the whole network, we propose a probabilistic scheme where only a subset of nodes is managed in order to provide a light-weight and efficient management. These nodes are determined based on their network behavior to favor subsets of well connected and network participating nodes. With respect to such a selective management scheme, we derive probabilistic guarantees on the percentage of nodes to be managed. Our contribution is centered on a distributed self-organizing management algorithm at the application layer, its efficient deployment into a management architecture and on a comprehensive simulation study. We will show how to organize the management plane by extracting spatio-temporal components and by selecting manager nodes with several election mechanisms based on degree centrality, eigenvector centrality and K-means paradigm. Index Terms— Network management, mobile ad-hoc networks, probabilistic analysis, management architecture.

I. I NTRODUCTION

A

D-HOC networks are spontaneous networks deployed without requiring a fixed network infrastructure such that localized and temporal limited network connectivity can be assured in some dedicated target deployment environments. Examples include military applications, emergency rescue teams, and other geographically challenging environments. Such networks are highly dynamic, since nodes might come and go, based on user mobility, out-of-reach conditions and energy exhaustion. These factors interact strongly with the network service, requiring new paradigms for the management of ad-hoc networks. Our paper proposes a new management approach for adhoc networks centered on a novel configuration scheme for the network management plane. This work is orthogonal to our previous work published in [1]. In that paper we addressed the issue of what to manage in an ad-hoc network, leaving beside the issue of the how-to manage it. We complete now our work with a new approach for organizing the management plane. This approach can be applied to all management scenarios where the administrators do not want to monitor and configure all the network nodes, but where they only need to manage the network in a less fine-grained manner. It can cover multiple applications including mobility, connectivity, ressource usage, quality of service, fault detection. The key idea is to relax the

Manuscript received October 20, 2006; revised February 22, 2007. The associate editor coordinating the review of this paper and approving it for publication was J. Hellerstein. The authors are with the MADYNES Research Team, LORIA-INRIA Lorraine, France (email: {badonnel, state, festor}@loria.fr). Digital Object Identifier 10.1109/TNSM.2007.030104.

requirements on the management plane: we propose a new scheme where only some spatio-temporal connected subsets of nodes are managed. Such assumptions are well suited for an ad-hoc network, where only nodes that had a more or less network presence are interesting enough to be managed. Our main contributions can be summarized in a) definition of probabilistic management, b) concept formalization with a distributed algorithmic method for organizing the management plane, c) integration of this method into a management architecture, d) extensive set of simulations to obtain quantitative and qualitative results of the method. This article is consequently structured as follow: we introduce the concept and the stakes of probabilistic management in ad-hoc networks in Section II. We present the underlying distributed algorithmic management method in Section III by describing the spatio-temporal connectivity measure, the extraction of spatio-temporal connected components and the election of manager nodes. We detail several manager election mechanisms based on degree centrality, eigenvector centrality and K-means paradigm. We show in Section V how to integrate the probabilistic approach into the ANMP management framework. Section VI presents and discusses a set of simulations performed with a common network simulator. Finally, we discuss related work in Section VII and conclude the paper with pointers to future work in Section VIII. II. P ROBABILISTIC M ANAGEMENT Monitoring and managing ad-hoc networks is challenged by several constraints which are not encountered in the common fixed networks: • Relevant management information: the challenge is to identify the essential pieces of relevant information but also to determine what management operations to be taken in this context. While we have a fair amount of understanding about what monitoring information should be collected, few have focused on what management actions to be taken and on the demonstration of their effectiveness. • Management domain related: since ad-hoc networks are dynamically formed loosely coupled entities, the notion of administrative domain, responsible for the overall management can be challenging for some application domains. Even if we consider an hybrid ad-hoc network connected to the gateway of a company, cooperative and role-based schemes should be further investigated to organize the management plane in an efficient manner. • Management node reliability and willingness to cooperate (illustrated by Fig. 1): an agent/manager node is limited

c 2007 IEEE 1932-4537/07$25.00 

40

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

•

by its inherent limits (connectivity, failures) such that the provided management data may be biased. How to improve the reliability of management data which are provided by other nodes, as well as the reliability of data provided by the node itself? Additionally, malicious nodes or non-cooperative nodes may provide false data or no data at all. The key issue is to define distributed monitoring and management paradigms, where we can reducethe impact of bias or faulty information. Cost of monitoring: resources (battery power) are already scarce in ad-hoc networks and monitoring and management actions are additional consumers in an already resource under-powered context. Defining lightweight schemes, where already available information is used and resource availability and consumption can be minimal, are the main issues.

v4

Malicious Behavior

Agent

Non Cooperative Behavior v2

v1

Reliability? Legitimity?

Manager

Agent

v3

Reliabitity?

Agent

v5

Fault behavior

Agent

Fig. 1. Management node reliability issue: an agent/manager node may provide biased management data because of its inherent limits such as connectivity and failures (node v5 ). It may also provide false data or no data at all (malicious node v4 or non-cooperative node v2 ). The key issue is to define management paradigms where we can reducethe impact of bias or faulty information.

The key assumption of the probabilistic management approach was motivated by the simple observation that adhoc network management should not comprise the totality of network elements (as it is typically the case in fixed networks). If node behavior can be better described probabilistically (a node might be on-line with a given probability), why should we preserve a deterministic framework for the network management? The first paper describing conceptual management approaches for ad-hoc networks was published by Burgess in [2], where a network model for ad-hoc networks is defined as a probability matrix, where an element in row i and column j is equal to the probability of nodes i and j to be directly connected. Our work is partially motivated by that paper: if we assume that such a matrix is known, why not restrict the network management plane to the nodes that seem to intercommunicate and have an effective network presence and

define a probabilistic management scheme? The probabilistic nature of the management plane derives from the guarantees that we can offer. Whereas in a fixed network, direct neighborhood relationships among nodes are fixed and management is defined to comprise the totality of the network nodes, it is quite natural to approach an ad-hoc network with a probabilistic framework. We will not guarantee in this framework that all nodes will be managed, but we can give probabilistic bounds on the percentage of nodes that are managed on average. Our probabilistic management is a selective scheme which consists in only managing the most interesting nodes of the network based on a statistical analysis. The notion of interesting is define with respect to relative good network presence and topology relationship. We define a spatio-temporal component to be a subset of the network nodes, such that any pair of nodes have a high adjacency probability. The term spatio-temporal is inspired by the spatial dimension – nodes are required to be adjacent – and the temporal one – nodes should have a high probability to be adjacent. Since this probability is estimated over a given time period, we identify pairs of nodes that tend to directly interconnect. Such pairs can be aggregated in spatio-temporal components. This can be done by identifying all connected components in a graph built from the original network nodes, where an edge between two nodes is constructed if and only if a significant probability of adjacency for these nodes was estimated. We restrict the management plane to the first largest and/or maybe the second largest connected component, assuming that the nodes worth to be managed are located in these components. Since these components are associated to the largest node subsets having significant network presence and frequent adjacent relationships, we consider it is a viable approach for the specifics of ad-hoc networks. The notion of spatio-temporal connectivity is related to the time averaged connectivity of network nodes and does not represent an instant snapshot connectivity view as proposed in [3]. We relate the notion of adjacency to high probabilities of observed direct neighborhood, such that our definition is broader in scope than the simple instant connectivity one. The management approach is centered around these concepts. In the following sections, we will detail a distributed management algorithmic method to estimate the adjacency matrix and to construct the spatio-temporal connected components. We will then show how this algorithmic method can be supported by extending a management architecture. III. D ISTRIBUTED A LGORITHMIC M ANAGEMENT M ETHOD The algorithmic method for probabilistic management is based on the spatio-temporal connectivity measure. A network node evaluates its spatio-temporal connectivity with its neighborhood and communicates that information to the other network nodes in order to construct the spatio-temporal connectivity matrix of the ad-hoc network. From this matrix, the node is capable to detect spatio-temporal connected components of the network and to elect its network manager. We assume a minimal cooperation among nodes, where partial control is allowed. If necessary, the cooperation could be stimulated by considering an incentive approach such as [4].

BADONNEL et al.: A PROBABILISTIC APPROACH FOR MANAGING MOBILE AD-HOC NETWORKS

A. Spatio-temporal connectivity measure An ad-hoc network is seen as a set of n mobile nodes V = {v1 , v2 , ..., vn } moving in a given surface during a time period T . The time period T is split in k measurement interval [tl , tl+1 ] with tl = l × Tk for an integer l ∈ [0, k]. The choice of optimal time period T and interval values [tl , tl+1 ] is not addressed in this paper but an excellent analysis on timescales for information flow to monitor ad-hoc networks can be found in [5]. Each node vi measures the percentage of time pij it was neighbor with a network node vj . On a time interval [tl , tl+1 ], the measurements are locally stored in a list N l (vi ) composed of tuples (vi , vj , pij ) and are subsequently exchanged and merged among network nodes. The suffix l represents the time factor and means the measure was performed during the time interval [tl , tl+1 ]. The exchange of local measurements lead conceptually to l a network spatio-temporal connectivity matrix MST C (or at least a partial view) obtained by concatenating the list of measurements performed by the network nodes. Rows/columns l stand for a network node. The i-th row of MST C represents l the list of measurements N (vi ) of a node vi . If node vi was l neighbor with node vj on [tl , tl+1 ], an entry MST C [i, j] exists and contains the percentage of time pij that the pair (vi , vj ) was directly connected on that time interval. As the goal is to highlight network nodes presenting a high probability of adjacency (and also to limit the management data), only the spatio-temporal connectivity values which are higher than a threshold value λ are considered in the matrix.

v6

Spatio-temporal components

0.45

Agent

v7 Agent

0.42

v1 Agent

41

were neighbors on the time interval [tl , tl+1 ] and the percentage of time pij is higher than the predefined threshold. The graph link is weighted by the percentage of time. Each network node vi determines the connected component (noted CCvi ) of which he is part by running through the graph. A connected component corresponds to a subset of well-connected nodes in V . The extraction of connected components in the spatiotemporal connectivity graph is described by algorithm 1. Algorithm 1: extraction of connected components l Data: spatio-temporal connectivity matrix MST C Result: connected component CCvi of node vi initialization a) initialize the set CCvi with node {vi } as the single element; // i.e. CCvi = {vi } repeat b) add to the set CCvi all the nodes connected to a node element of CCvi ; c) delete all the doubles of CCvi ; until no change in calculation of connected component CCvi

The CCvi set is initialized with a single element: the node vi itself. The key idea of the graph component extraction is to add recursively to the set CCvi the neighbor nodes of each node already part of CCvi . A node vi can extract the connected component CCvi , but can also extract the other components CCvj (j = i) he is not part of, by initializing a set CCvj with a node which is not already assigned and by following the same approach. Each element of a resulting connected component has been a neighbor of another element during at least a minimum percentage of time.

0.47

0.50

C. Manager election in a connected component v8

0.6

v5

Manager

4

0.6

Manager

2

0.

40

v10

v2

Agent

Agent

0.44

v9

0.4

2

Agent v3

v4 Agent

Percentage of time

Fig. 2. Extraction of spatio-temporal connected components: a spatiotemporal component is a subset of network nodes, such that any pair of nodes have a high adjacency probability. The term spatio-temporal is inspired by the spatial dimension nodes are required to be adjacent and the temporal one nodes should have a high probability to be adjacent.

B. Connected component extraction l The matrix MST C can be represented as a graph of n nodes as shown in Fig. 2. A graph edge exists between two nodes, if the following double condition is respected: the two nodes

A connected component, such as CCvi , represents a set of network nodes with an high value of spatio-temporal connectivity. It represents a sub-domain to be managed by one manager, or possibly by several managers if the connected component size is significant. An election mechanism is required to determine the manager nodes in each connected component. Assuming that each node in the network has an unique identifier (MAC address), the simplest way is to define an arbitrary election mechanism by electing the node with the minimal identifier. The Fig. 3 describes a spatio-temporal connected component where nodes are identified by a unique name. We could consider that the node name is the election criteria. In that case, node v1 will be elected as the manager node even if this node is relatively isolated in the connected component. This mechanism is thus not efficient, as it does neither take into account the structural properties of the connected component nor the relative importance of nodes. We will define more refined election mechanisms based on centrality and Kmeans paradigm. These mechanisms will be applied to the data set formed by the spatio-temporal connectivity measurements limited to the nodes in the connected component. This data set l is a submatrix noted SST C , where rows/columns represent the

42

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

v9

0.48

Node

Degree

Node

Eigenvector

v3

2.16

v6

0.52

v6

1.90

v3

0.47

v7

1.81

v5

0.39

v4

1.27

v4

0.37

v5

1.26

v7

0.36

v8

1.62

v2

0.17

v2

0.54

v8

0.15

v9

0.48

v1

0.14

v1

0.42

v9

0.12

v7

0.62

v8

1 0.7 v6

Eigenvector-based Manager

7

v2

0.5

54 0. v3

62

Degree-based Manager

3 0.6

0. 42

0.

v5

0.64

v4 v1

Spatio-temporal Component

Fig. 3. Degree-based and eigenvector-based elections of manager nodes in a spatio-temporal connected component: the graph on the left is a spatio-temporal connected component. The two tables synthesizes respectively the degree centrality and the eigenvector centrality measurements of the component nodes. In each of these tables, nodes are classified by order of importance, so that the first entries of a given table correspond to the nodes elected as managers. The degree-based election selects node v3 as manager, while the eigenvector-based election selects node v6 . The degree centrality is a local measure limited to the one-hop neighborhood information, whereas the eigenvector centrality takes recursively into account the importance of the neighbor nodes.

m nodes part of a connected component. Let us consider the scenario presented in Fig. 3. The spatio-temporal connected component is composed of 9 ad-hoc nodes and is associated l to ⎡ the following 9 × 9 matrix SST C: ⎤ 0

⎢ 0 ⎢0.42 ⎢ ⎢ 0 ⎢ ⎢ 0 ⎢ 0 ⎢ ⎢ 0 ⎣ 0 0

0 0 0.54 0 0 0 0 0 0

0.42 0.54 0 0.63 0 0.57 0 0 0

0 0 0.63 0 0.64 0 0 0 0

0 0 0 0.64 0 0.62 0 0 0

0 0 0.57 0 0.62 0 0.71 0 0

0 0 0 0 0 0.71 0 0.62 0.48

0 0 0 0 0 0 0.62 0 0

0 0 ⎥ 0 ⎥ ⎥ 0 ⎥ ⎥ 0 ⎥ 0 ⎥ ⎥ 0.48⎥ ⎦ 0 0

l The matrix SST C is a symmetric matrix because it represents an undirected graph. The two following election mechanisms are inspired by research work on centrality. The concept of centrality allows to quantify the relative importance of a node in a network or a graph structure. Several variants of this measure have been defined in social networking [6]. The objective is to identify the nodes having a central position in the connected component, and to elect them as manager nodes. 1) Degree-based election mechanism: A well-known centrality measure is the degree centrality. A node is central if it is directly connected to a maximal number of neighbor nodes. The degree centrality of a node is the number of links linked to this node. Each link being weighted by a percentage of time, the centrality degree measure is defined by equation 1. We calculate, for each node vi in the component, the sum of the values (in percentage of time) of each link connected to the node. Nodes having the highest centrality degree are elected as manager nodes.

cdeg (vi ) =

j=m  j=1

l SST C (i, j) f or a given node vi

(1)

We applied this election mechanism to the scenario presented in Fig. 3. The degree measure for a node vi is computed as the l sum of the elements of the ith line of matrix SST C . Results are synthesized in the first table of Fig. 3. Node v3 has the highest degree centrality with a value of 2.16. It will be elected as the manager node. The time complexity of the degree-based election mechanism is of O(N ). 2) Eigenvector-based election mechanism: The degree centrality is a local measure limited to the one-hop neighborhood information. An alternative measure is the eigenvector centrality defined by Bonacich in [7]. The key idea is to define the centrality measure in a recursive way: the more a node is directly connected to central nodes, the more the node is central. For such a non-oriented connected graph, Bonacich demonstrates that the problem can be reduced to the typical eigenvector problem defined by equation 2. l x = λ × x SST C ×

(2)

The vectors that solve this equation are called eigenvectors and are associated with corresponding eigenvalues. The principal eigenvector vpr is the solution vector which is paired with the highest eigenvalue. The eigenvector centrality ceig of node vi corresponds to the ith element of the principal eigenvector l of matrix SST C , as mentioned in equation 3. ceig (vi ) = vpr (i) f or a given node vi

(3)

We solved the eigenvector problem for the scenario defined in Fig. 3 using a symbolic mathematics software. The highest l eigenvalue of SST C is equal to 1.457 and is paired with the principal eigenvector defined in equation 4: vpr = [ 0.14 0.17 0.47 0.37 0.39 0.52 0.36 0.15 0.12 ]T (4) The elements of the principal eigenvector are ranked by order of importance, which leads to the second table of Fig. 3. Node

BADONNEL et al.: A PROBABILISTIC APPROACH FOR MANAGING MOBILE AD-HOC NETWORKS

v6 shows the highest value and is elected as manager node. The two centrality approach do not provide the same results: the degree centrality is a local measure while the eigenvector degree takes additionally into account the importance of the neighbor nodes themselves. A generalized version of the eigenvector centrality has been defined in [8] in the case of oriented connected graphs. The time complexity of the eigenvector-based election mechanism is of O(N 3 ). 3) K-means election mechanism: As some ad-hoc nodes may provide biased or false management data, a key issue is to provide a reliable election capable to out-weight or discard faulty information. We therefore propose an alternative election mechanism where the measurements performed by each node in the connected component are compared in order to provide the best trade-off. The goal of the manager election is basically to classify the connected component nodes in two populations: agent nodes and manager nodes, favoring the manager role to the nodes with the highest spatio-temporal connectivity. We use the K-means classification method [9] to divide the connected component nodes in two clusters noted {c1, c2}. A node vj in the connected component (column of matrix l SST C ) is seen as a point in a m-dimensional vector space, where a dimension corresponds to the view of a node vi (row j j l j of matrix SST C ). The coordinates (x1 , x2 , .., xm ) of a point l l l [1, j], S [2, j], ...S vj correspond then to (SST C ST C ST C [m, j]). j The coordinate xj stands for the node self-measured up-time percentage. In this vector space, the norm of a point va noted ||va || is given by equation 5 and the distance measure between two points va and vb noted ||va − vb || is given by equation 6.

k=m

 l 2 (SST ||va || =  C [k, a])

(5)

k=1



k=m

 l l 2 (SST ||va − vb || =  C [k, a] − SST C [k, b])

(6)

k=1

Intuitively, the K-means classification puts together ad-hoc nodes showing similar spatio-temporal connectivity values to form two clusters. The centroid of a cluster c corresponds basically to the point whose coordinates are the mean of the coordinates of all the points in the cluster. Assuming a cluster c composed of k nodes {v1 , v2 , ..., vk }, the coordinates of the centroid are thus given by equation 7 providing the i-th coordinate in the m-dimensional vector space. q=k q q=1 xi centroid(c) xi (7) = k The K-means clustering for electing the manager nodes is described in algorithm 2 and can be divided in two main steps. In the first step of initialization, nodes of the connected component are arbitrarily assigned to a cluster c1 or c2 and the centroid of each cluster is calculated using previous equation 7. In the second step, the algorithm reassigns iteratively each point vj to the cluster c ∈ {c1, c2} whose centroid is nearest and recalculate the centroids. The algorithm stops when the cluster centroids are fixed (the coordinates do not change between two iterations). The K-means algorithm corresponds actually to

43

Algorithm 2: election of manager nodes l Data: spatio-temporal connectivity matrix SST C Result: set of manager nodes for the connected component initialization a) select two clusters {c1, c2} arbitrarily; b) compute initial cluster centroids centroid(c1) and centroid(c2) within those two clusters; repeat c) partition by assigning or reassigning all the points vj of the connected component to their closest cluster centroid; d) compute the new cluster centroid of each cluster; until no change in cluster centroid calculation finally the manager set is the cluster (c1 or c2) whose centroid has the highest norm;

minimize the objective function defined by equation 8 where clusters c1 and c2 represent the two node populations and where ||vj − centroid(c)|| is the distance between a point vj and the centroid of its cluster c. E=

1 2





||vj − centroid(c)||2

(8)

c∈{c1 ,c2 } vj ∈c

After performing the algorithm, the two final clusters contain network nodes with close spatio-temporal connectivity. The manager nodes are located in the cluster with the centroid presenting the highest spatio-temporal connectivity norm. An illustrative example is shown in Fig. 4 with a simple connected component composed of three nodes {v1 , v2 , v3 } l (presented on the left). The submatrix SST C is a 3 x 3 matrix where rows/columns represents the three nodes in the connected component. The K-means classification is performed in a three-dimensional vector space (presented on the right) where an axis represents the view (spatio-temporal connecl tivity measure) of a given node (row of SST C ) and where l a point represents a node to be classified (column of SST C ). The K-means algorithm divides the three nodes in two clusters c1 and c2 represented by spheres in this three-dimensional vector space. Cluster c1 is composed of nodes v2 and v3 , while cluster c2 is composed of a single node v1 . A numerical calculation shows the spatio-temporal connectivity norm of centroid(c2) is higher than the norm of centroid(c1) (||centroid(c2)|| > ||centroid(c1)||). Manager nodes are located in the cluster c2 whose centroid shows the highest norm. The connected component will therefore be composed of a single manager: node v1 . This election mechanism based on Kmeans algorithm relies on the comparison of spatio-temporal connectivity measures performed by different nodes in a distributed manner. The comparison of these management data improve the election reliability by out-weighting biased/false data. The time complexity of this election algorithm is of O(2N ).

44

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

v2

Cluster c2 X v1 v1

2

0.8

0.7

3

X v2

v2 X

0.12

v3 v1

Cluster c1 X v3

Spatio-temporal Component v3

Centroids

Fig. 4. K-means election of manager nodes in a spatio-temporal connected component: a simple scenario of a connected component composed of three nodes {v1 , v2 , v3 } is presented on the left. The K-means classification method (presented on the right) divides the three nodes in two clusters c1 and c2 represented by spheres in this three-dimensional vector space. Ad-hoc nodes which will interact as managers are located in the cluster c2 whose centroid shows the highest spatio-temporal connectivity norm. A single manager (node v1 ) is elected in this simple scenario.

IV. M ONITORING OF PATHOLOGICAL M OBILITY IN A S PATIO - TEMPORAL C ONNECTED C OMPONENT An ad-hoc node measures periodically the spatio-temporal connectivity of the other network nodes. The manager nodes can monitor the spatio-temporal connectivity variations over time of nodes located in a spatio-temporal connected component in order to detect pathological mobility behavior. While normal mobility is difficult to define, in some specific target deployment (for instance military applications), unpredicted mobility patterns can seriously impact the network resilience and service level and deteriorate the management plane organization. We mean by ”pathological mobility” a mobility behavior that reveals underlying problems of ad-hoc nodes such as: •

•

•

Failures due to miss-configuration and errors at the physical layer may generate an atypical behavior, where nodes are intermittent although from a mobility point of view they did not change significantly, Routing failures which can be encountered when the routing process is affected by voluntary and malicious activity (attacks against the routing plane), errors in its configuration or at the protocol stack level, Battery breakdown: spatio-temporal connectivity may be lost for longer or shorter time periods because of battery lifetime.

Pathological mobility can be inferred by analyzing statistically the variations of the spatio-temporal connectivity measurements pij over time. Ad-hoc nodes with such a mobility can involuntary corrupt management data and report biased or faulty information because of their pathology. A key issue is to define actions that compensate for the management data provided by these problematic nodes. A possible corrective operation consists in using a weight system to estimate the reliability of agent nodes. The manager node vi assigns reliability weights {w1 , w2 , ..., wm } to agent nodes

{v1 , v2 , ..., vm }: management data reported by reliable agents will have higher weights. At the network deployment, the weight of the agents is initialized with a similar weight w1 = w2 = ... = wm , because the manager do not already know the agent nodes. When an agent vj is detected as pathological, the manager decreases the weight wj of that agent. For instance, the weight can be divided by two, each time the agent shows an pathological mobility behavior. When the manager will get management data from agents, it will more take into account in the management process the information provided by agents with high reliable weights. This corrective operation limit the propagation and the impact of biased information in the management plane. V. M ANAGEMENT F RAMEWORK We propose to integrate the probabilistic approach into the ANMP (Ad-Hoc Network Management Protocol) management framework [10] as presented in Fig. 5. ANMP defines a management protocol for ad-hoc networks, but also describes the underlying management architecture and information model. The protocol is fully compatible with SNMPv3 [11] and thus with most of current management architecture. The key idea of ANMP is to clusterize the management plane in order to reduce the management message overhead. The management plane is logically divided into a three-level hierarchy composed of a top-level manager, SNMP managers performed by cluster-head nodes (CH) and SNMP agents performed by simple nodes (SN). ANMP introduces by default two clustering algorithms at the application layer to organize the management plane: • Graph-based clustering algorithm (clusters of one hop neighbors). Each network node has a unique identifier and maintains the list of its one-hop neighbor nodes using the network layer or the MAC layer. In a neighborhood, the node with the minimum identifier is elected as the cluster-head, if it has not joined any other cluster.

BADONNEL et al.: A PROBABILISTIC APPROACH FOR MANAGING MOBILE AD-HOC NETWORKS

Geographical-based clustering algorithm (clusters of up to three-hop neighbors). This algorithm uses the global positioning system in order to evaluate node positions. Network nodes are split into rectangular clusters based on their spatial density. ANMP is defined at the application layer and draw a distinction between clusters for management and clusters for routing, as they aim at different goals (respectively organizing the management plane and maintaining routes). The authors of ANMP conclude the paper in [10] by pointing out it would be interesting to explore other way of clustering or methods to group the nodes in the network. We therefore introduce an additional clustering algorithm at the application layer to implement the probabilistic approach where clusters are defined by spatio-temporal connected components. This extension is composed of three building blocks (1) to evaluate the spatio-temporal connectivity, (2) to extract the spatio-temporal connected components and (3) to elect the spatio-temporal connected component manager(s). •

45

of mobile ad-hoc networks. As in a pure link state algorithm, each node performs two main operations: (1) it determines the list of direct-connected neighbor nodes by accomplishing link sensing through periodic emission of hello messages and (2) it exchanges this link state information with the other nodes throughout the network by flooding topology control messages. Due to the limited bandwidth of ad-hoc networks, OLSR reduces the control overhead by selecting a subset of nodes called Multi-Point Relays (MPRs) which forward broadcast messages during the flooding process. The selection of MPRs is based on an heuristic which consists in selecting for a given node the minimal subset of one-hop neighbors to reach all the two-hop neighbors, in order to reduce the number of links used for forwarding topology information. During the link sensing operation, an OLSR node uses a neighborhood base (see RFC 3626 section 4.3). and maintains the list of one-hop neighbor nodes by recording a set of tuples (N neighbor main addr, N status, N willingness) describing neighbors. The element N neighbor main addr stands for the main address of a neighbor, N status specifies the link status (symmetric or not) with the given neighbor and N willingness is an integer specifies the willingness of the neighbor to carry traffic on behalf of other nodes. We introduce an additional entry in the neighbor tuple called N connectivity time perc to maintain the percentage of time the neighbor was connected to the node. This new entry must then be integrated in the topology control (TC) messages (defined in RFC 3626 section 9) performing the advertisement of link states, so that the spatiotemporal connectivity information is propagated in the ad-hoc network. Including a sequence number, the format of a TC message describes a set of Advertised Neighbor Main Address. We define an additional field Advertised Neighbor Connectivity Time Percentage to include the percentage of time the neighbor was seen. Our spatio-temporal clustering algorithm extension, defined over a piggybacked OLSR version, gives to the ANMP architecture the capability to perform probabilistic management.

Fig. 5. Integration of the probabilistic approach into the ANMP management framework: ANMP is extensible to other clustering algorithms. In order to organize the management plane based on the spatio-temporal approach, an additional clustering algorithm is implemented over a piggybacked version of the OLSR routing protocol.

The management algorithms are executed locally by the network nodes based on information obtained from the routing plane. The consistency of information and the robustness to mobility of our management solution relies therefore on the performances of the routing protocol. The evaluation of spatio-temporal connectivity is based on the piggybacking of OLSR (Optimized Link State Routing Protocol) [12]. This routing protocol is an optimization of the classical link state algorithm adapted to the requirements

The integration of the probabilistic approach into ANMP implies to extend the management information base (MIB) of this management framework and of the OLSR routing protocol. A MIB corresponds basically to a database of objects that can be monitored and managed by the network management system [14]. We proposed an OLSR MIB module in [13] which is partially described in Fig. 6. This partial view details two groups: the first one called olsrGeneralGroup provides general information on the OLSR node, on its network interfaces compatible with OLSR (olsrInterfaceTable) and on its willingness to interact as a MultiPoint Relay. The second group olsrLocalInformationGroup describes the local information of the OLSR node including the one-hop neighborhood olsrNeighborSetTable and the two-hop neighborhood olsrTwoHopNeighborSetTable. The table olsrNeighborSetTable enumerates the one-hop neighbors and their link status. We added to this table an additional entry olsrNeighborConnectivityTimePerc (shown in grey on the figure). This entry represents the percentage of time of connectivity in order to fit with the routing protocol piggybacking.

46

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

Fig. 6. Extension of the OLSR routing protocol MIB: The figure presents a partial view of the OLSR MIB we proposed in [13]. The table olsrNeighborSetTable enumerates the one-hop neighbors and their link status. We added to this table an additional entry olsrNeighborConnectivityTimePerc (shown in grey on the figure). This entry represents the percentage of time of connectivity in order to fit with the routing protocol piggybacking.

The ANMP MIB is also extended to the probabilistic management. The anmpTopologyMaintenance group of that MIB is detailed in Fig. 7 with the grey entries corresponding to the extension. This group contains objects related to the topology information of the ad-hoc network. The anmpNeighborTable defines the list of one-hop neighbors of a node and is completed by the additional entry anmpNeighborConnectivityTimePerc to ensure coherence with the OLSR MIB extension. The anmpProtocolTable maintains an entry for each protocol which may be used for topology maintenance in the management plane. Each of the two clustering algorithms provided by default with ANMP is represented by a group: anmpGraphClustering and anmpGeographicalClustering. These groups are not detailed on the figure, but a more complete description can be found in [10]. We introduce an additional group called anmpSpatioTemporalClustering for applying the probabilistic approach to the management plane organization. This group maintains the information generated by the connected component extraction algorithm (algorithm 1) and by the manager election algorithm (algorithm 2) presented in Section III. In particular, the table anmpSTCComponentTable contains the list of spatio-temporal connected components. Each entry anmpSTCComponentEntry in the table inventories

Fig. 7. Extension of the ANMP management framework MIB: this figure details only the anmpTopologyMaintenance group of that MIB, with the grey entries corresponding to our extension. We introduce an additional group called anmpSpatioTemporalClustering for applying the probabilistic approach to the management plane organization.

the characteristics of a connected component including the list of its managers provided by the table anmpSTCComponentManagerTable and the list of its agents provided by the table anmpSTCComponentAgentTable. These MIB extensions allow to specify the management information implied by our probabilistic approach in a standardized way. VI. E XPERIMENTAL R ESULTS We describe in this section a set of simulations, in which we apply the management algorithmic method to detect the largest spatio-temporal connected components. The simulations are performed using the widely-accepted network simulator ns-2 [15]. The data link layer is based on the wireless IEEE 802.11 MAC model. The routing layer corresponds to the standardized OLSR routing protocol (NRL’s implementation [16]). We consider an ad-hoc network composed of n ∈ [5 − 30] mobile devices deployed in an urban area. The nodes are moving in a squared surface with a 1000

BADONNEL et al.: A PROBABILISTIC APPROACH FOR MANAGING MOBILE AD-HOC NETWORKS

TABLE I S IMULATION PARAMETERS

Parameter Simulator Simulation time Simulation area Number of ad-hoc nodes Mobility model Speed Pause time Physical layer MAC layer Routing layer λ value

Value ns-2 1800 s 1000 m x 1000 m 5-30 nodes random waypoint mobgen - steady state 0.5 - 10 m/s 1 - 50 s FSP / 2-RGR IEEE 802.11 NRL OLSR 40%

In a first series of experiments we analyzed the probability distribution of the ratio of the largest spatio-temporal connected component to the overall network. These results are shown in figure 8 and represent an extensive set of simulations with different mobility parameters and node sizes. For each individual setting, we performed 150 simulations to assure the non-bias of the result. On the x axis is plotted the percentage of the overall node size which is located in the largest spatio-temporal component, while the y axis stands for the percentage of cases (simulations). A point (x,y) on the graph stands for the percentage of simulations (y) such that the largest spatiotemporal component was at least x. For instance we can observe that the probability (y axis) of having at least 20% of nodes in the largest component is about 95%. We could have a best-effort type pragmatic management approach in the style: we manage around 20% of the nodes and in this case we will meet this requirement in 95% of the cases. We can assure the management of the half of the nodes within one single component with a probability close to 70%, which is a relative good result. Such a best-effort type of management could be implemented by one and only one manager station following the spatio-temporal component. A natural question is whether network mobility impacts the management framework. Intuitively, higher mobility should make things worse (ie.: smaller components sizes for the same probability), but a precise quantification of this effect is required. A second series of experiments addressed this issue, where different mobility parameters were evaluated for

110 100 90 Percentage of cases (simulations)

meters side according to the commonly-used random waypoint (RWP) model [17] (being aware of the model limits [18]): each node moves at constant speed s ∈ [0.5−10] m/s to a destination point selected uniformly in the squared surface and then waits during a pause time p ∈ [1 − 50] s before moving to a new destination. The simulation parameters which are not specified in the sum-up table I are set with the ns-2 default values. To avoid initialization discrepancy issues with the RWP model [18], we used the steady-state mobility model generator mobgen-ss where initial speeds and locations of nodes are chosen from the stationary distribution to perform an immediate convergence and provide more reliable simulations. We determined experimentally the λ value (40%) based on an initial set of simulations.

47

80 70 60 50 40 30 20 10 0 0

10

20

30

40

50

60

70

80

90

100

Minimal percentage of nodes in the largest spatio-temporal component

Fig. 8. Probability distribution for the ratio of the largest spatio-temporal connected component to the overall network: a point (x,y) on the graph indicates the percentage y of simulations such that the largest spatio-temporal component covers at least x percent of network nodes.

different node sizes. For each node size, 150 simulations were performed to avoid any bias. These results are summarized in Fig. 9. We expected to have good results for low mobility (ie.: small speeds and large pause times), where by good results we understand a high probability to have a large percentage of the network nodes in the largest spatio-temporal component. Such was the case indeed (note the case of speed = 0.5m/s and pause time = 50s) where about 90% of the nodes are located in the same component in about 90% of the cases. A rather surprising result is however the case of small pause times (speed = 0.5m/s and pause time = 1s), where 90% of the nodes are located in the same component in around 80% of the cases. If we analyze the cases with varying pause times and constant speed = 10m/s another interesting issue is that the worst results are obtained with a high pause time. This contradicts the initial hypothesis that a higher mobility implies a smaller component size. It seems that in cases of higher node speeds, the spatio-temporal connectivity is better if nodes do not rest/pause. Such a result could be summarized in one phrase Move fast but do not rest. In the previous experiments we limited the analysis to the largest spatio-temporal component. A natural extension is to consider the two largest spatio-temporal components. Figure 10 summarizes an experiment suite analogous to the one illustrated in figure 8, but where the aggregated sizes of the most important components is considered. We can observe that in the extended case, about 50% of the nodes are located in the two main components with a probability close to 90%. That is, we can manage about 50% of the nodes with a very high probability. We see that with respect to the one component scenario, we get about 20% more nodes at the same probability. If we consider in this case the requirement

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

110

110

100

100

90

90

80

80

Percentage of cases (simulations)

Percentage of cases (simulations)

48

70 60 50 (0.5, 50) (0.5, 10) (0.5, 1) (1, 50) (1, 10) (1, 1) (5, 50) (5, 10) (5, 1) (10, 50) (10, 10) (10, 1)

40 30 20 10

70 60 50 40 30 20 10

0

0 0

10

20

30

40

50

60

70

80

90

100

Minimal percentage of nodes in the largest spatio-temporal component

Fig. 9. Probability distribution for the ratio of the largest spatio-temporal connected component to the overall network according to the network mobility: each curve stands for different mobility parameters (speed, pause).

to manage at least 50% of the nodes, than we can achieve this goal in about 90% of the cases. The last series of experiments presented in this paper are illustrated in Fig. 11. Here we plotted the individual component sizes (expressed in percentage of the overall network node size) where all simulations were done as previously described. We conclude that the second largest component is relevant in about 80% of the cases, counting for around 15% of the network node size. This is relatively normal, since a small sized first component implies a small sized second component. VII. R ELATED W ORK Lots of research efforts deal with connectivity issues in ad-hoc networks. The approaches in [19], [3], [20] define how to optimize node connectivity in function of the network parameters such as power control parameters. However, they focus on node connectivity at an instant time, while we are interested in a probabilistic scheme based on the percentage of time of connectivity, and while we consider the connectivity is given as it is. An approach for organizing network nodes into clusters in which path availability can be bounded was proposed in [21], but this solution defined at the routing layer aims at ensuring end-to-end network performance. Among the pioneering approaches for managing ad-hoc networks, ANMP [10] presented in Section V proposes a management protocol and a management architecture adapted to ad-hoc network specifics. Clustering algorithms (at the application layer) are used to organize the management plane and reduce the management messages overhead. We used ANMP as a support to integrate the probabilistic approach. The GUERILLA management architecture proposed in [22] defines a self-management approach where the management

0

10

20

30

40

50

60

70

80

90

100

Minimal percentage of nodes in the two largest spatio-temporal components

Fig. 10. Probability distribution for the ratio of the two largest spatiotemporal connected components to the overall network: the curve represents the value of the aggregated ratios of the first and second spatio-temporal connected components.

intelligence is spread over the network nodes according to their capabilities. GUERILLA is organized in a two-tier architecture. The higher-tier is composed of groups of peerto-peer nomadic managers that maintain connectivity in the management plane with the other managers. The lower-tier is composed of agents and active probes (programmable scripts) which perform the localized management operations. This autonomic solution is conceptual and do not discuss the underlying clustering mechanism. However, it points out that the management role depends on the node capability. The probabilistic algorithm could take into account other factors related to node state such as battery level and node processing capability. In particular, a programmable middleware for the dynamic deployment of services and protocols in adhoc networks is proposed by [23]. In this programmable infrastructure, ad-hoc nodes can dynamically download and activate the required protocol and service software. Therefore, the platform can align the capabilities of heterogeneous adhoc nodes by using loadable plug-ins. The two management approaches ANMP and GUERILLA infers the use of n-hop clustering algorithms at the application layer. We consider that a pure and sound management approach, where all nodes are managed at any time is too strict and we therefore propose a new relaxed clustering scheme where only some spatiotemporal connected subsets of nodes are managed. Policy-based management approaches are also proposed in [24], [25], [26], [27]. For instance, Phanse in [25] elaborates a framework for policy-based management based on three key mechanisms: service location, cluster management and dynamic service redundancy. In particular, the hybrid provisioning/outsourcing policy model is decentralized using a clustering algorithm to provide an efficient and robust

BADONNEL et al.: A PROBABILISTIC APPROACH FOR MANAGING MOBILE AD-HOC NETWORKS

intermittence due to mobility and other ad-hoc specifics, while faulty behavior can generate pathological intermittence behavior. The key issue addressed was how to differentiate pathological intermittence from regular intermittence and thus identify faulty nodes from regular non-faulty ones. While fault detection in fixed wired networks is not hindered by the impossibility to observe a given node, ad-hoc networks specifics do provide major challenges with respect to this issue. We introduced in [32] an pathological intermittence measure based on information theory allowing a local node to detect pathological intermittent nodes by monitoring the routing plane. A distributed monitoring scheme, where network nodes share their local measurements, is designed in order to provide a reliable and robust detection of faulty nodes. Several distributed methods of fault detection are defined including an auto-configured detection method.

110 1st largest component 2nd largest component 100 90 Percentage of cases (simulations)

49

80 70 60 50 40 30 20 10

VIII. C ONCLUSIONS AND FUTURE WORK 0 0

10

20

30

40

50

60

70

80

90

100

Minimal percentage of nodes in the largest spatio-temporal components

Fig. 11. Probability distributions for the ratio of the first and second largest spatio-temporal connected components to the overall network: the second largest component is relevant in about 80% of the cases, counting for around 15% of the network node size.

management. The approach in [24] considers an alternative policy management scheme where the policy distribution is based on the synchronization of policy databases when two network nodes meet. A probabilistic approach for policy-based management can also be envisioned in ad-hoc networks. The DAMON architecture [28] defines a distributed monitoring system based on agents for multi-hop networks: agents perform the network monitoring and send the measurements to data repositories. DAMON supports multiple data repositories and includes an auto-discovery mechanism of data repositories by the agents. This generic architecture is not dedicated to specific network parameters and could therefore be appropriate for the storage of pathological mobility monitoring data. A multi-tier architecture for efficient monitoring and management is proposed in [29] where nodes are grouped to ensure that they can be reached via a member of its group. The approach is initially designed for sensor networks, but is applicable to ad-hoc networks, since they present the similar energy and bandwidth constraints. WANMon is a monitoring tool described in [30] to monitor the resource usage in terms of network traffic, energy, memory and CPU, but its scope is limited to the host-level monitoring. We introduced the concept of probabilistic management of ad-hoc networks in [31]. We detail further in this paper the management algorithmic scheme, describing several manager election mechanisms based on degree centrality, eigenvector centrality and K-means paradigm. The probabilistic scheme can also provide a basis for identifying the pathological behavior of nodes such as introduced in section IV. We proposed in [32] a more refined approach for detecting faulty nodes in ad-hoc networks. Faulty behavior and intermittence are closely related in ad-hoc networks: a node can have a regular

Instead of defining a pure and sound management approach, we have presented in this paper a new probabilistic scheme for configuring the management plane in an ad-hoc network. The underlying key idea is the notion of spatio-temporal connected nodes. A spatio-temporal connected component is a subset of the ad-hoc network, such that nodes within such a component have a high probability of being directly connected. The term spatial derives from this neighborhood notion, while the term temporal is related to the temporal behavior of this neighborhood. In a store and forward oriented architecture, such nodes are also capable to inter-communicate at a higher hop-count. The management plane is limited to the largest spatio-temporal connected components. We have defined the underlying management selforganizing algorithm for both extracting spatio-temporal connected components and electing manager nodes. We have detailed several manager election mechanisms based on centrality degree, eigenvector centrality and K-means paradigm and have shown how to apply them with realistic scenarios. These election mechanisms aim at selecting nodes having a structural importance in the spatio-temporal components, and at limiting the propagation of biased and faulty information in the management plane. The probabilistic approach is integrated into the ANMP management framework over a piggybacked ad-hoc routing protocol. We have subsequently shown how to extend the ANMP management information base. The management approach is called probabilistic since its behavior can only be guaranteed in a stochastic way. We can ensure that a given percentage of the overall network will be managed with a fixed apriori known probability. We have estimated these probabilities using extensive network simulations and we have performed a fine grained analysis of the mobility impact on our framework. Although network simulators present functional limits [33], the experimental methodology is generic and can be applied to other mobility scenarios. We are working on alternative mobility models including the Manhattan grid model and the reference point group mobility model. Our future work will consist in designing an information theoric framework [32] for this probabilis-

50

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT, VOL. 4, NO. 1, JUNE 2007

tic scheme, and in extending the management algorithms to take into account additional properties of nodes. R EFERENCES [1] R. Badonnel, R. State, and O. Festor, “Management of Mobile AdHoc Networks : Evaluating the Network Behavior,” in Proc. of the 9th IFIP/IEEE International Symposium on Integrated Network Management (IM’05), Nice, France, Apr. 2005, pp. 17–30. [2] M. Burgess and G. Canright, “Scalability of Peer Configuration Management in Logically Ad-Hoc Networks,” IEEE eTransactions on Network and Service Management (eTNSM), vol. 1, no. 1, Apr. 2004. [3] P. Santi and D. M. Blough, “An Evaluation of Connectivity in Mobile Wireless Ad-Hoc Networks,” in Proc. of the International Conference on Dependable Systems and Networks (DSN’02). Bethesda, MD, USA: IEEE Computer Society, June 2002. [4] L. Buttyan and J. P. Hubaux, “Stimulating Cooperation in SelfOrganizing Mobile Ad Hoc Networks,” ACM/Kluwer Mobile Networks and Applications, vol. 8, no. 5, Oct. 2003. [5] R. D’Souza, S. Ramanathan, and D. T. Land, “Measuring Performance of Ad-Hoc Networks using Timescales for Information Flow,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM’03), San Francisco, CA, USA, Apr. 2003. [6] S. Borgatti and M. Everett, “A Graph-theoric Perspective on Centrality,” Social Networks, 2006. [7] P. Bonacich, “Factoring and Weighing Approaches to Status Scores and Clique Identification,” Journal of Mathematical Sociology, vol. 2, pp. 113–120, 1972. [8] P. Bonacich and P. Lloyd, “Eigenvector-like Measures of Centrality for Asymmetric Relations,” Social Networks, vol. 23, pp. 191–201, 2001. [9] J. B. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations.” Berkeley, CA: Proc. of the 5-th Berkeley Symposium on Mathematical Statistics and Probability, 1967, pp. 281– 297. [10] W. Chen, N. Jain, and S. Singh, “ANMP: Ad-Hoc Network Management Protocol,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 17, no. 8, pp. 1506–1531, Aug. 1999. [11] W. Stallings, SNMP, SNMPv2, SNMPv3, and RMON 1 and 2. Addison Wesley Longman, 3rd edition, 1999. [12] T. Clausen and P. Jacquet, “Optimized Link State Routing Protocol (OLSR),” Oct. 2003, IETF RFC 3626. [13] R. Badonnel, R. State, and O. Festor, “Management of Mobile AdHoc Networks: Information Model and Probe-based Architecture,” ACM International Journal of Network Management (ACM IJNM), vol. 15, no. 5, Sept. 2005. [14] D. Perkins and E. McGinnis, Understanding SNMP MIBs. Upper Saddle River, NJ, USA: Prentice Hall Inc., 1997. [15] “Ns-2 network simulator,” http://www.isi.edu/nsnam/ns/. [16] “OLSR Extension for Ns-2,” Navy Research Laboratory OLSR Project, http://pf.itd.nrl.navy.mil/projects/olsr/. [17] F. Bai, N. Sadagopan, and A. Helmy, “Important: a Framework to Systematically Analyze the Impact of Mobility on Performance of Routing Protocols for Ad-Hoc Networks,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM’03), San Francisco, CA, USA, Apr. 2003. [18] J. Yoon, M. Liu, and B. Noble, “Random Waypoint Considered Harmful,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM’03), San Francisco, CA, USA, Apr. 2003, pp. 1312–1321. [19] D. M. Blough, M. Leoncini, G. Resta, and P. Santi, “The K-Neigh Protocol for Symmetric Topology Control in Ad-Hoc Networks,” in Proc. of the 4th ACM International Symposium on Mobile Ad-Hoc Networking and Computing (MOBIHOC’03), Annapolis, MD, USA, June 2003, pp. 141–152. [20] O. Dousse and P. Thiran, “Connectivity vs Capacity in Dense Ad-Hoc Networks,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM’04), Hong Kong, Mar. 2004. [21] A. B. McDonald and T. Znati, “A Mobility Based Framework for Adaptive Clustering in Wireless Ad-Hoc Networks,” IEEE Journal on Selected Areas in Communications (JSAC), vol. 17, no. 8, pp. 1466– 1487, Aug. 1999. [22] C.-C. Shen, C. Jaikaeo, C. Srisathapornphat, and Z. Huang, “The GUERILLA Management Architecture for Ad-Hoc Networks,” in Proc. of IEEE Military Communications Conference (MILCOM’02), Anaheim, CA, USA, Oct. 2002.

[23] S. Gouveris, S. Sivavakeesar, G. Pavlou, and A. Malatras, “Programmable Middleware for the Dynamic Deployment of Services and Protocols in Ad-Hoc Networks,” in Proc. of the 9th IFIP/IEEE International Symposium on Integrated Network Management (IM’05), Nice, France, Apr. 2005, pp. 3–16. [24] A. Munaretto, S. Mauro, P. Fonseca, and N. Agoulmine, “Policy-based management of ad-hoc enterprise networks,” in Proc. of HP Openview University Association 9th Annual Workshop, June 2002. [25] K. Phanse, “Policy-Based Quality of Service Management in Wireless Ad-Hoc Networks,” Ph.D. dissertation, Faculty of the Virginia Polytechnic Institute and State University, Aug. 2003. [26] R. Boutaba, Y. Iraqi, and B. Ishibashi, “Policy-Based Routing in AdHoc Networks,” in Proc. of the First Ad-Hoc Networking Workshop (Med-Hoc-Net’02), Sardegna, Italy, Sept. 2002. [27] R. Chadha, H. Cheng, Y.-H. Cheng, and J. Chiang, “Policy-based Mobile Ad-Hoc Network Management,” in Proc. of IEEE 5th International Workshop on Policies for Distributed Systems and Networks (POLICY’04), New York, USA, June 2004. [28] K. Ramachandran, E. Belding-Royer, and K. Almeroth, “DAMON: A Distributed Architecture for Monitoring Multi-hop Mobile Networks,” in Proc. of IEEE International Conference on Sensor and Ad-Hoc Communications and Networks (SECON’04), Santa Clara, CA, USA, Oct. 2004. [29] M. Younis, P. Munshi, and E. Al-Shaer, “Architecture for Efficient Monitoring and Management of Sensor Networks, Workshop on End-toEnd Monitoring Techniques and Services,” in Proc. of the 6th IFIP/IEEE International Conference on Management of Multimedia Networks and Services (MMNS’03), Belfast, Northern Ireland, UK, Sept. 2003. [30] D. Ngo and J. Wu, “WANMON: a Resource Usage Monitoring Tool for Ad-Hoc Wireless Networks,” in Proc. of the 28th Annual IEEE Conference on Local Computer Networks (LCN’03), Bonn, Germany, Oct. 2003, pp. 738–745. [31] R. Badonnel, R. State, and O. Festor, “Probabilistic Management of AdHoc Networks,” in Proc. of the 10th IEEE/IFIP Network Operations and Management Symposium (NOMS’06), Vancouver, Canada, Apr. 2006. [32] R. Badonnel, R. State, and O. Festor, “Using Information Theoric Measures for Detecting Faulty Behavior in Ad-Hoc Networks,” LORIA - INRIA Lorraine, Tech. Rep., May 2005. [33] J.-Y. L. Boudec and M. Vojnovic, “Perfect Simulation and Stationarity of a Class of Mobility Models,” in Proc. of IEEE International Conference on Computer Communications (INFOCOM’05), Miami, FL, USA, Mar. 2005. Remi Badonnel is a research assistant at INRIA, France working on network and service management. He is preparing a PhD thesis in Computer Science at Henri-Poincare University, Nancy, France. He received a Master Science Degree in Computer Engineering (2003) from ESIAL, Nancy, France. He is working on designing, validating and implementing management models and architectures for efficiently handling dynamic networks and services. His research interests are directed towards Ad-Hoc Networking, Network Management and Self-Configuration (at INRIA), but also Change Management, Service Delivery and Business Process (at IBM Research). Radu State is a permanent researcher at INRIA, France working on network and security management. He has a Ph.D. degree (2001) from Henri-Poincare University, Nancy, France and Master of Science in Engineering (1998) from the Johns Hopkins University, Baltimore, MD, USA. His research interests are in the design of management models for highly dynamic environments such as ad-hoc networks as well as in the security of the management plane. He published more than 40 papers on network and service management issues and serves in the TPC boards of several international conferences and journals, including IFIP/IEEE IM, IFIP/IEEE DSOM, SAFIR, and A-ICT. Olivier Festor is a research director at INRIA. He has a Ph.D. degree (1994) and an Habilitation degree (2001) from Henri-Poincare University, Nancy, France. His research interests are in the design of algorithms and models for automated and scalable management for highly dynamic environments. Member of the IRTF NMRG, he has published more than 70 papers in network and service management and serves in the technical program and organization committees as well as in the editorial boards of several international conferences and journals. He was the TPC Co-chair of IM2005. He is currently leading the EMANICS European Network of Excellence dedicated to Management Solutions for the Internet and Complex Services.