Hani Daher

Abdel Belaïd

Document Flow Segmentation for Business Applications

Keywords: Document Flow segmentation, Textual descriptors, Business flow, Continuity and rupture classification

The aim of this paper is to propose a document flow supervised segmentation approach applied to real world heterogeneous documents. Our algorithm treats the flow of documents as couples of consecutive pages and studies the relationship that exists between them. At first, sets of features are extracted from the pages where we propose an approach to model the couple of pages into a single feature vector representation. This representation will be provided to a binary classifier which classifies the relationship as either segmentation or continuity. In case of segmentation, we consider that we have a complete document and the analysis of the flow continues by starting a new document. In case of continuity, the couple of pages are assimilated to the same document and the analysis continues on the flow. If there is an uncertainty on whether the relationship between the couple of pages should be classified as a continuity or segmentation, a rejection is decided and the pages analyzed until this point are considered as a "fragment". The first classification already provides good results approaching 90% on certain documents, which is high at this level of the system.

INTRODUCTION

Various types of documents flow into organizations every day, form claims, forms, invoices, contracts and more. Handling this flow of information manually by sorting the documents is a time consuming, costly and error-prone task. One solution is to introduce page separators or machine readable marks like bar codes to indicate the end of a document.

In the case of page separators this approach is costly and intensive because they must be inserted before the scanning of pages and, if they are not to be reused, removed afterwards. In high volume operations, these costs can be staggering. In the case of bar codes they offer more accurate document identification, but also at high cost. The use of papers, ink and codes is not an easy task and it also costly. Inserting these bar codes between documents is error prone and must be inserted correctly to ensure that the correct separator sheet is used.

The objective of our work is to develop an automatic segmentation approach capable of segmenting a stream of documents, without the need of any prior knowledge on the number of pages or on the document class, and where each document may represent a set of successive well-ordered pages. Furthermore, we should take into consideration that we are dealing with a heterogeneous flow of multipage documents where the quality of pages that constitute the documents may vary, and where some information may be accessible in one document but not the other.

Literature Review

To our knowledge, very few methods have been proposed to tackle this subject and find solutions. In our research we identified three categories of approaches used in document flow processing:

 Document Segmentation: where the task is to partition a flow of documents into multiple subsets of documents.  Document Retrieval: where the task is to search a database for the closest images to a query image  Document Classification: where the task is to assign a document to one or more classes or categories We are going to illustrate in the following sections these different cases and point out the closest elements to our topic. Table 1 summarizes all the works discussed below.

Document segmentation

Collins-Thompson and Nickolov [START_REF] Collins-Thompson | A clustering-based algorithm for automatic document separation[END_REF] work on page similarity which relies on structural and textual similarities. The authors treat document separation as a bottom-up clustering problem, where every page is considered as a cluster, and then proceed in steps by merging pairs of clusters using a single-linkage criterion. In the proposed method, page numbers are considered as always located in the bottom of the page which is not always the case. If these features are not correctly localized; this will affect the classification result. Textual and visual features are also extracted from the documents. Results show that the combination of the visual and textual features produces a segmentation accuracy of 95.68% and the visual features alone an accuracy of 89.25%. The authors consider that pages in a same document contain a lot of similarities, which is not always the case; in real world applications the content of pages may bear very little similarities. The method proposed by Meilander and Belaid [START_REF] Meilender | Segmentation of continuous document flow by a modified backward-forward algorithm[END_REF] is similar to the variable horizon models (VHM) or multi-grams used in speech recognition. It consists in maximizing the flow likelihood knowing all the Markov Models of the constituent elements. As the calculation of this likelihood on all the flow is NP-complete, the solution consists in studying them in windows of reduced observations. The first results obtained on homogeneous flows of invoices reaches more than 75% of precision and 90% of recall. The method was only tested on homogeneous documents and the proposed model is only suited for the invoices class.

Document Retrieval

Rusiñol et al. [START_REF] Rusiñol | Multipage document retrieval by textual and visual representations[END_REF], study different approaches for multipage document retrieval. They propose two fusion strategies including the early and late fusion to form one document representation out of a set of pages. Two types of features extracted from the pages of documents are visual and textual. The visual features are based on the SIFT descriptors and textual features are represented by bag of words that are weighted by the tf-idf method. The results show that the textual features gave good results by using the late fusion technique with an accuracy of 74.24%. Visual features on the other hand didn't give good results with an accuracy of 47.74%, this low accuracy is due to the fact that the documents were more oriented semantic, and the structure of the document didn't offer much information. Many documents in the same class share the same subject but are physically different. Kumar et al. [START_REF] Kumar | Learning Document Structure for Retrieval and Classification[END_REF] presented a bag of words approach using a feature pooling strategy. The algorithm was tested respectively on two types of documents, forms and tables, with an accuracy of 97.4% and 98.9%. This method relies heavily on the structure of the document, and is applied on documents of single pages, which is not our case, where we have to deal with multipage documents, and where the structure yields so little information about the classes of documents. Shin et al. [START_REF] Shin | Document image retrieval based on layout structural similarity[END_REF] segment the pages into blocks that are characterized by conceptual and geometric features. The distance between the query image and the other images in the database is achieved by mapping the blocks of the images, with a retrieval accuracy of 89%. The drawback of this method is that the extracted features are very specific to a category of documents.

Document classification

Gordo et al. [START_REF] Gordo | A bag-of-pages approach to unordered multi-page document classification[END_REF] treated the problem of multipage documents classification. Every document is composed of different classes of pages including: papers, insurance, invoice, etc. By using the same principle of the bag of words, they propose a bag of pages approach where a document is represented by a histogram that includes the number of occurrences of these classes. The method was tested on two datasets of different sizes. The results show that by increasing the number of documents, the classification results decreased drastically with a difference of 21.1% between the first and the second database. Shin et al. [START_REF] Shin | Classification of document pages using structure-based feature[END_REF] proposed a document classification algorithm based on visual similarity of layout structure.

Features such as column structures, percentage of text and non-text are extracted. This method does not propose a strategy for multipage documents classification. It is well adapted for single page documents.

The previous works show that the textual features did outperform the visual features in terms of classification and retrieval accuracies. The combination of the two types of features did improve the results but it wasn't enough, computational time was added to the algorithms. Furthermore, the database that we are working on relies more on the content of documents rather on the structure, so adding an extra complexity to our approach won't help us solve the problem. The fusion techniques of features are very interesting and we inspired our method from these approaches as described in section 2.

PROPOSED APPROACH

Figure 1 illustrates the three main modules of the proposed approach which are: feature extraction, relationship modeling of a pair of pages and classification. These three modules will be explained in details in the next sections.

All images are OCR-ed and stop words have been removed, as output every page will be presented by an XML tree which is composed of a set of blocks  

Feature extraction and relationship modeling

We start by analyzing what are the elements that are found in the business documents and that might help us identify if there is a potential continuity or rupture between two consecutive pages. We only focused on textual elements and we classified them into 6 classes according to Table 2 To be generic and in order to cover all the descriptors, we reduced these features to a set of 9 main features. All dates are represented by a single feature f 1 , modeling the different date formats. The hour f 2 represents all the hour formats; the telephone f 3 is suited for all the telephone formats in France. The Zip code f 4 extracts all the French Zip codes of length 4. The alphanumeric feature f 5 extracts all the alphanumerical patterns. The numeric feature f 6 extracts all the numbers with a length greater than 5, this way the extraction algorithm won't confuse the numeric features with the Zip code. Page numbers f 7 represents the number of the page, in contrast to the other features that are extracted by value, the page number is identified by its label (like page…), then the page number located on the right is extracted. The Salutation feature f 8 combines all the French salutations. The Margin f 9 represents the width of the largest block and is computed as follow: f 9 = |right -left|.

f 2 = {}  f 3 = {}  f 4 = {67500}  f 5 = {}  f 6 = {1 56 09 67 473 316 93, 1784-111690- 0382}  f 7 = 1  f 8 = {}  f 9 = width of the largest block f 1 f 4 f 6 f 7
f 1 is composed of a set of 3 dates, f 1 = {d 1 ,…,d 3 }. The regular expression didn't find any pattern related to feature f 2 . We consider then that f 2 represents an empty set, f 2 = {}. f 7 is represented by 1, the regular expression found the label "Feuillet" and assigned the value 1 located on its right side to f 7 (See Figure 2). In order to model the relationship between two consecutive pages p i and p i+1 , and to identify the continuity and rupture, we have to find a relation R between the couple between of pages p i and p i+1  

      9 2 1 6 4 1 1 , ,..., ,..., ,..., f n n f d d f v i          9 2 1 6 14 1 1 1 , ,..., ,..., ,..., f n n f d d f v i      ) ( ci v R Figure 3, shows how ) ( ci v R
is constructed. In the case of f 1 , since at least one value from page i is equal to the value of page i+1 the first feature in ) ( ci v R is attributed the value 1. f 2 , f 3 , f 5 and f 8 are not present in both of the pages so they are attributed the value 0. For the feature f 7 that represents the page number, since the value in page i is smaller than the value in page i+1 then it is attributed the value 1.

 -1: implies that the features exist but are different, reflecting a segmentation or rupture  0: There is no correspondence between the features or the features does not exist, reflecting a potential rejection  1: implies that there are plenty of ties between the features, reflecting a continuity  For feature f 7 the comparison is done by value independently from the label which is only used to identify the page number. If

          n k f s s f d d f v n k i       / , ,..., ,..., ,..., 9 1 8 1 1
v i is a vector of vectors, every vector can be either empty or may represent a set of patterns p. Every vector may differ from the other by its dimension. For every feature vi f except features 7 f and 9 f represented by a set of extracted patterns, we compute the intersection with the same feature 1  vi f of the successive page. The intersection presents the equality between the patterns of a set. The value assigned to the intersection is an integer which takes multiple values, "1" if there is at least one pattern in vi f that intersect with another patter of 1  vi f , "-1" if there is no intersection, and "0" is both the sets of patterns or one of them in vi f and

1  vi f is empty  .   ) , ( , , ,..., ) ( 1 9 9 1 8 8 1 7 7 1 1 1 1           vi vi vi vi vi vi vi vi i i ci f f d f f f f f f v v v R                                                      1 ' ,..., ,..., 1 ' ,..., ' ,..., 0 ) ,..., ' ,..., ' ( 0 1 1 1 1 1 1 ci l j ci l j ci j j ci v o p p p p v o p p p p v p p p p v 2.

Classification

As input the classifier will take the vectors

) ( ci v R
representing the couple of pages. For the sake of clarification we replace ) ( ci v R by x. the classifier classifies each incoming couple of pages as belonging to the same document;

(continuity (1)) or not (rupture (0)). As we stated earlier, we added an extra layer to the decision of the classifier based on the class membership probabilities which reflects the uncertainty with which a given couple of pages can be assigned to any given class, and is represented by an evaluation function E working as follows:

    ) ( ˆx c P x c P x E          on segmentati Over else x E 1 0   P(c | x) is the probability of x belonging to class c. If   x E < 6 . 0  
, then we have a case of uncertainty leading to a fragment of a document. The over-segmentation choice is based on the assumption that we might end up with missing pages of a document but we will never end up with pages that belong to different classes of documents being fused into one.

EXPERIMENTS

All of our experiments were carried on databases provided by ITESOFT Company (see Figure 3). To test the stability of the approach, we used four databases containing different numbers of documents and pages. The first database contains very heterogeneous documents that can be easily separated by the classifier. The other three databases are also heterogeneous but with classes of documents that cannot be separated so easily. Some classes of documents might contain features similar to other classes in the same database. On all the databases 75% of the documents were used for training and 25% for testing.

 The classifiers produce good results on the first database, since the document classes are quite different and can be easily segmented. The precision and Recall values remained stable even when added an extra complexity presented by the increase of the number of documents and pages.

Figure 4 shows the stability of our system even after increasing the size of documents and pages in the database.

Discussion

In order to understand what caused the segmentation errors, we analyzed the cases of rupture and continuity separately on database 4 since it is the largest database. For the case where ruptures were classified as continuities we count the occurrence of descriptors indicating continuity. The same analysis was carried out on the continuity errors. Date Hour Tel Zip Alpha Num Page Margin Salut Figure 5 shows that feature f 1 , f 6 and f 9 are the ones that appear the most in the case where we have rupture errors. The same goes for the continuity errors. We also notice that extracted features favor continuity over segmentation since the rupture errors are more present than those of the continuity.

We also notice that the other features have no weight and are not discriminant. In fact discarding those features have a very little effect on the classification results (see Figure 6). When we remove the feature with the higher weight, we see that the classification accuracy drops. Figure 6. Precision after discarding specific subsets of features Figure 7 illustrates the proportion of fragments on the 4 databases on the different classifiers. The SVM and Voted perceptron produce 0 fragments; there was no uncertainty in the classification. In the 2 nd database documents are very close in semantics this why the multilayer perceptron produces 29% of fragments.

CONCLUSION

We proposed in this article a generic approach for the segmentation of a heterogeneous flow of documents. Results show the stability of our approach. The increase of the number of documents didn't affect the results. This study allowed us also to measure the effectiveness of the features and their discriminating power. The second step is the verification. The fragments obtained by this our approach represent ambiguous cases where there is probability of a segmentation error. The verification algorithm will read the sequence of fragments and assign to each fragment a class of a document (invoice, insurance etc.), if the confidence probability is less than a threshold then the classification is correct, else the fragment will be sent to the Case Based Reasoning module where its role will be to find a solution to the problem presented by the sequence of fragments. As output, this module provides a solution represented by a sequence of documents. The final objective of our study is the fusion of documents that are similar.

Table1.

  Summary of the discussed methods. S = Segmentation, C = classification, R = Retrieval, T = Textual features, V = Visual features

  i B . Every block includes a sequence of sections   n S . Every section includes a sequence of words   l k w  which are the root nodes. Every block, section and word, are given by the coordinates of their bounding boxes named (top, left), (bottom, right).

Figure 1 .

 1 Figure 1. Document segmentation flow chart, based on supervised classification. (a) training, (b) testing

Features f 1

 1 ,…,f 8 are extracted by regular expressions. All the features except f7 and f9 represent the set of all the values related to their type and are found by regular expressions.

Figure 2 .

 2 Figure 2. Example of feature extraction by regular expressions

 f 1 =

 1 Figure 3. Relationship modeling procedure

1  1 2 1 

 111 a value 1 else -For feature f 9 the Euclidean distance is used to compute the difference between the widths of the margins. If the distance is less than a threshold 12   we consider that there is a continuity between the couple of pages d(.,.) = 1, else d(.,.) =be the stream of pages. Every page p i is represented by a vector v i of dimension 9.

Figure 4 .

 4 Figure 4. Precision curve

Figure 5 .

 5 Figure 5. Continuity and rupture errors

Figure 7 .

 7 Figure 7. Proportion of fragments per Base

Table 2 .

 2 . Classes of features that were extracted from the business documents

	Fax	Page	Date	Code	Number	ID
	Date	Number	Expedition	Account	Number	Global ID
	Number	Font	Assignation	Receiver	Folder	User ID
	Page Number	Margin	Mission	Shipper	Social Security
	Fax	Item	Deadline	Immatriculation	Client
	Hour	Logo	Invoice	Zip Code	Order
		Signature	Report	Reference	Contrat
		Sequence Transaction Commercial Reference	Transaction
		Salutation	Exchange	Transaction Reference	Invoice
			sinister	TVA	Tax
			Accident	Pin	General
			Internal		Licence

Table 3 .

 3 Features representation

	Feature	Description	Type
	f 1	Date (d)	Alphanumeric String
	f 2	Hour (h)	Alphanumeric String
	f 3	Telephone (t)	Numeric string
	f 4	Zip Code (z)	Numeric string length = 4
	f 5	Alphanumeric (a)	Alphanumeric String
	f 6	Numeric (n)	Integer string length > 5
	f

7 Page Number (p) Numeric f 8 Salutation (s) String

Table 4 .

 4 Database 1 : 618 documents (2366 pages) shows the results of our segmentation approach on the 4 databases.

	 Database 2 : 1898 documents (7405 pages)
	 Database 3 : 802 documents (11759 pages)
	 Database 4: 3318 documents (21530 pages)

Table 4 .

 4 Segmentation results

	Classifier	Precision	Recall	F-measure
		Database 1
	Voted Perceptron	0.95	0.95	0.95
	SVM	0.94	0.94	0.94
	Multilayer Perceptron	0.94	0.94	0.94
	Multi-Boost	0.92	0.91	0.91
		Database 2
	Voted Perceptron	0.80	0.81	0.79
	SVM	0.80	0.80	0.75
	Multilayer Perceptron	0.80	0.79	0.79
	Multi-Boost	0.81	0.81	0.81
		Database 3
	Voted Perceptron	0.79	0.80	0.77
	SVM	0.76	0.77	0.71
	Multilayer Perceptron	0.80	0.81	0.80
	Multi-Boost	0.79	0.81	0.79
		Database 4


Ivan Nourdin
email: inourdin@gmail.com

David Nualart
email: nualart@math.ku.edu

Giovanni Peccati
email: giovanni.peccati@gmail.com

Giovanni Peccati Strong

Strong asymptotic independence on Wiener chaos

Keywords: Gaussian Fields, Independence, Limit Theorems, Malliavin calculus, Wiener Chaos. 2000 Mathematics Subject Classification: 60F05, 60H07, 60G15

come

Introduction

Overview

Let X = {X(h) : h ∈ H} be an isonormal Gaussian process over some real separable Hilbert space H (see Section 1.2 and Section 2 for relevant definitions), and let F n = (F 1,n , ...., F d,n ), n 1, be a sequence of random vectors such that, for every j = 1, ..., d, the random variable F j,n belongs the q j th Wiener chaos of X (the order q j 1 of the chaos being independent of n). The following result, proved by Nourdin and Rosiński in [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]Corollary 3.6], provides a useful criterion for the asymptotic independence of the components of F n . Theorem 1.1 (See [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]) Assume that, as n → ∞ and for every i = j,

Cov(F 2 i,n , F 2 j,n ) → 0 and F j,n law → U j , (1.1)
where each U j is a moment-determinate * random variable. Then,

F n law -→ (U 1 , . . . , U d ),
where the U j 's are assumed to be mutually stochastically independent.

In words, Theorem 1.1 allows one to deduce joint convergence from the componentwise convergence of the elements of F n , provided the limit law of each sequence {F j,n } is moment-determinate and the covariances between the squares of the distinct components of F n vanish asymptotically. This result and its generalisations have already led to some important applications, notably in connection with time-series analysis and with the asymptotic theory of homogeneous sums -see [START_REF] Bai | Multivariate limit theorems in the context of long-range dependence[END_REF][START_REF] Bourguin | Asymptotic Cramér type decomposition for Wiener and Wigner integrals[END_REF][START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]. The aim of this paper is to study the following important question, which was left open in the reference [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]: Question A. In the statement of Theorem 1.1, is it possible to remove the momentdeterminacy assumption for the random variables U 1 , ..., U d ? Question A is indeed very natural. For instance, it is a well-known fact (see [START_REF] Slud | The moment problem for polynomial forms in normal random variables[END_REF]Section 3]) that non-zero random variables living inside a fixed Wiener chaos of order q 3 are not necessarily moment-determinate, so that Theorem 1.1 cannot be applied in several contexts where the limit random variables U j have a chaotic nature. Until now, such a shortcoming has remarkably restricted the applicability of Theorem 1.1 -see for instance the discussion contained in [1, Section 3].

In what follows, we shall derive several new probabilistic estimates (stated in Section 1.3 below) for chaotic random variables, leading to a general positive answer to Question A. As opposed to the techniques applied in [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF], our proof does not make use of combinatorial arguments. Instead, we shall heavily rely on the use of Malliavin calculus and Meyer inequalities (see the forthcoming formula (2.11)). This new approach will yield several quantitative extensions of Theorem 1.1, each having its own interest. Note that, in particular, our main results immediately confirm Conjecture 3.7 in [START_REF] Bai | Multivariate limit theorems in the context of long-range dependence[END_REF].

The content of the present paper represents a further contribution to a recent and very active direction of research, revolving around the application of Malliavin-type techniques for deriving probabilistic approximations and limit theorems, with special emphasis on normal approximation results (see [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF][START_REF] Peccati | Gaussian limits for vector-valued multiple stochastic integrals[END_REF] for two seminal contributions to the field, as well as [START_REF] Nourdin | The optimal fourth moment theorem[END_REF] for recent developments).The reader is referred to the book [START_REF] Nourdin | Normal Approximations using Malliavin Calculus: from Stein's Method to the Universality[END_REF] and the survey [START_REF] Nourdin | Lectures on Gaussian approximations with Malliavin calculus[END_REF] for an overview of this area of research. One can also consult the constantly updated webpage [START_REF] Nourdin | A webpage on Stein's method and Malliavin calculus[END_REF] for literally hundreds of results related to the findings contained in [START_REF] Nualart | Central limit theorems for sequences of multiple stochastic integrals[END_REF][START_REF] Peccati | Gaussian limits for vector-valued multiple stochastic integrals[END_REF] and their many ramifications.

Let H be a real separable infinite-dimensional Hilbert space. For any integer q 1, let H ⊗q be the qth tensor product of H. Also, we denote by H ⊙q the qth symmetric tensor product. From now on, the symbol X = {X(h) : h ∈ H} will indicate an isonormal Gaussian process on H, defined on some probability space (Ω, F , P ). In particular, X is a centered Gaussian family with covariance given by E[X(h)X(g)] = h, g H . We will also assume that F is generated by X.

For every integer q 1, we let H q be the qth Wiener chaos of X, that is, H q is the closed linear subspace of L 2 (Ω) generated by the class {H q (X(h)) : h ∈ H, h H = 1}, where H q is the qth Hermite polynomial defined by

H q (x) = (-1) q q! e x 2 /2 d q dx q e -x 2 /2 .
We denote by H 0 the space of constant random variables. For any q 1, the mapping I q (h ⊗q ) = q!H q (X(h)) can be extended a linear isometry between H ⊙q (equipped with the modified norm √ q! • H ⊗q ) and H q (equipped with the L 2 (Ω) norm). For q = 0, by convention H 0 = R, and I 0 is the identity map.

It is well-known (Wiener chaos expansion) that L 2 (Ω) can be decomposed into the infinite orthogonal sum of the spaces H q , that is: any square-integrable random variable F ∈ L 2 (Ω) admits the following chaotic expansion:

F = ∞ q=0 I q (f q ), (1.2)
where f 0 = E[F ], and the f q ∈ H ⊙q , q 1, are uniquely determined by F . For every q 0, we denote by J q the orthogonal projection operator on the qth Wiener chaos. In particular, if F ∈ L 2 (Ω) is as in (1.2), then J q F = I q (f q ) for every q 0.

Main results

The main achievement of the present paper is the explicit estimate (1.3), appearing in the forthcoming Theorem 1.2. Note that, in order to obtain more readable formulae, we only consider multiple integrals with unit variance: one can deduce bounds in the general case by a standard rescaling procedure.

Remark on notation. Fix integers m, q 1. Given a smooth function ϕ : R m → R, we shall use the notation

ϕ q := ϕ ∞ + ∂ k ϕ ∂x k 1 i 1 • • • ∂x kp ip ∞
, where the sum runs over all p = 1, ..., m, all {i 1 , ..., i p } ⊂ {1, ..., m}, and all multi indices

(k 1 , ..., k p ) ∈ {1, 2, ...} p verifying k 1 + • • • + k p := k q.
Theorem 1.2 Let d 2 and let q 1 q 2 • • • q d 1 be fixed integers. There exists a constant c, uniquely depending on d and (q 1 , ..., q d ), verifying the following bound for any d-dimensional vector

F = (F 1 , ..., F d ),
such that F j = I q j (f j ), f j ∈ H ⊙q j (j = 1, ..., d) and E[F 2 j ] = 1 for j = 1, ..., d -1, and for any collection of smooth test functions ψ 1 , ..., ψ d : R → R,

E d j=1 ψ j (F j ) - d j=1 E[ψ j (F j )] c ψ ′ d ∞ d-1 j=1 ψ j q 1 1 j<ℓ d Cov(F 2 j , F 2 ℓ ). (1.3)
When applied to sequences of multiple stochastic integrals, Theorem 1.2 allows one to deduce the following strong generalization of [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]Theorem 3.4].

Theorem 1.3 Let d 2 and let q 1 q 2 • • • q d 1 be fixed integers. For every n 1, let F n = (F 1,n , ..., F d,n ) be a d-dimensional random vector such that F j,n = I q j (f j,n ), with f j,n ∈ H ⊙q j and E[F 2 j,n ] = 1
for all 1 j d and n 1. Then, the following three conditions are equivalent, as n → ∞:

(1) Cov(F 2 i,n , F 2 j,n ) → 0 for every 1 i = j d; (2) f i,n ⊗ r f j,n → 0 for every 1 i = j d and 1 r q i ∧ q j ;
(3) The random variables F 1,n , ..., F d,n are asymptotically independent, that is, for every collection of smooth bounded test functions ψ 1 , ..., ψ d : R → R,

E d j=1 ψ j (F j,n ) - d j=1 E[ψ j (F j,n )] -→ 0.
We can now state the announced extension of Theorem 1.1 (see Section 1), in which the determinacy condition for the limit random variables U j has been eventually removed.

Theorem 1.4 Let d 2 and let q 1 q 2 • • • q d 1 be fixed integers. For every n 1, let F n = (F 1,n , ..., F d,n ) be a d-dimensional random vector such that F j,n = I q j (f j,n ), with f j,n ∈ H ⊙q j and E[F 2 j,n ] = 1 for all 1 j d and n 1. Let U 1 , . . . , U d be independent random variables such that F j,n law → U j as n → ∞ for every 1 j d. Assume that either Condition (1) or Condition (2) of Theorem 1.3 holds. Then, as n → ∞, F n law → (U 1 , . . . , U d ).
By considering linear combinations, one can also prove the following straightforward generalisations of Theorem 1.3 and Theorem 1.4 (which are potentially useful for applications), where each component of the vector F n is replaced by a multidimensional object. The simple proofs are left to the reader.

Proposition 1.5 Let d 2, let q 1 q 2 • • • q d
1 and m 1 , ..., m d 1 be fixed integers, and set M := d j=1 m j . For every j = 1, ..., d, let

F j,n = (F (1) j,n , ..., F (m j ) j,n ) := I q j (f (1)
j,n ), ..., I q j (f

(m j ) j,n ) ,
where, for ℓ = 1, ..., m j , f

(ℓ) j,n ∈ H ⊙q j and E[(F (ℓ) j,n ) 2 ] = q j ! f (ℓ) j,n 2
H ⊗q j = 1.
Finally, for every n 1, write F n to indicate the M-dimensional vector (F 1,n , ..., F d,n ). Then, the following three conditions are equivalent, as n → ∞:

(1) Cov (F (ℓ) i,n ) 2 , (F (ℓ ′ ) j,n ) 2 → 0 for every 1 i = j d, every ℓ = 1, ..., m i and every ℓ ′ = 1, ..., m j ; (2) f (ℓ) i,n ⊗ r f (ℓ ′ ) j,n
→ 0 for every 1 i = j d, for every 1 r q i ∧ q j , every ℓ = 1, ..., m i and every ℓ ′ = 1, ..., m j ;

(3) The random vectors F 1,n , ..., F d,n are asymptotically independent, that is: for every collection of smooth bounded test functions ψ j : R

m j → R, j = 1, ..., d, E d j=1 ψ j (F j,n ) - d j=1 E[ψ j (F j,n )] -→ 0.
Proposition 1.6 Let the notation and assumptions of Proposition 1.5 prevail, and assume that either Condition (1) or Condition (2) therein is satisfied. Consider a collection (U 1 , ..., U d ) of independent random vectors such that, for j = 1, ..., d, U j has dimension m j . Then, if F j,n converges in distribution to U j , as n → ∞, one has also that

F n law → (U 1 , . . . , U d ).
The plan of the paper is as follows. Section 2 contains some further preliminaries related to Gaussian analysis and Malliavin calculus. The proofs of our main results are gathered in Section 3.

Further notation and results from Malliavin calculus

Let {e k , k 1} be a complete orthonormal system in H. Given f ∈ H ⊙p , g ∈ H ⊙q and r ∈ {0, . . . , p ∧ q}, the rth contraction of f and g is the element of H ⊗(p+q-2r) defined by

f ⊗ r g = ∞ i 1 ,...,ir=1
f, e i 1 ⊗ . . . ⊗ e ir H ⊗r ⊗ g, e i 1 ⊗ . . . ⊗ e ir H ⊗r .

(2.4)

Notice that f ⊗ r g is not necessarily symmetric. We denote its symmetrization by f ⊗ r g ∈ H ⊙(p+q-2r) . Moreover, f ⊗ 0 g = f ⊗ g equals the tensor product of f and g while, for p = q, f ⊗ q g = f, g H ⊗q . In the particular case H = L 2 (A, A, µ), where (A, A) is a measurable space and µ is a σ-finite and non-atomic measure, one has that H ⊙q can be identified with the space L 2 s (A q , A ⊗q , µ ⊗q ) of µ q -almost everywhere symmetric and square-integrable functions on A q . Moreover, for every f ∈ H ⊙q , I q (f ) coincides with the multiple Wiener-Itô integral of order q of f with respect to X and (2.4) can be written as

(f ⊗ r g)(t 1 , . . . , t p+q-2r ) = A r f (t 1 , . . . , t p-r , s 1 , . . . , s r )
× g(t p-r+1 , . . . , t p+q-2r , s 1 , . . . , s r )dµ(s 1 ) . . . dµ(s r ).

We will now introduce some basic elements of the Malliavin calculus with respect to the isonormal Gaussian process X (see again [START_REF] Nourdin | Normal Approximations using Malliavin Calculus: from Stein's Method to the Universality[END_REF][START_REF] Nualart | The Malliavin calculus and related topics[END_REF] for any unexplained notion or result). Let S be the set of all smooth and cylindrical random variables of the form

F = g (X(φ 1 ), . . . , X(φ n )) , (2.5)
where n 1, g : R n → R is a infinitely differentiable function with compact support, and φ i ∈ H. The Malliavin derivative of F with respect to X is the element of L 2 (Ω, H) defined as

DF = n i=1 ∂g ∂x i (X(φ 1 ), . . . , X(φ n )) φ i .
By iteration, one can define the qth derivative D q F for every q 2, which is an element of L 2 (Ω, H ⊙q ).

For q 1 and p 1, D q,p denotes the closure of S with respect to the norm • D q,p , defined by the relation

F p D q,p = E [|F | p ] + q i=1 E D i F p H ⊗i .
The Malliavin derivative D verifies the following chain rule. If ϕ : R n → R is continuously differentiable with bounded partial derivatives and if

F = (F 1 , . . . , F n ) is a vector of elements of D 1,2 , then ϕ(F ) ∈ D 1,2 and
Dϕ(F ) = n i=1 ∂ϕ ∂x i (F )DF i . (2.6)
Note also that a random variable

F as in (1.2) is in D 1,2 if and only if ∞ q=1 qq! f q 2 H ⊗q < ∞,
and, in this case, E [ DF 2 H ] = q 1 qq! f q 2 H ⊗q . If H = L 2 (A, A, µ) (with µ non-atomic), then the derivative of a random variable F as in (1.2) can be identified with the element of L 2 (A × Ω) given by

D a F = ∞ q=1 qI q-1 (f q (•, a)) , a ∈ A.
(2.7)

We denote by δ the adjoint of the operator D, also called the divergence operator. A random element u ∈ L 2 (Ω, H) belongs to the domain of δ, noted Dom δ, if and only if it verifies

E DF, u H c u E[F 2 ]
for any F ∈ D 1,2 , where c u is a constant depending only on u. If u ∈ Dom δ, then the random variable δ(u) is defined by the duality relationship (customarily called 'integration by parts formula'):

E[F δ(u)] = E DF, u H , (2.8)
which holds for every F ∈ D 1,2 . The formula (2.8) extends to the multiple Skorohod integral δ q , and we have

E [F δ q (u)] = E D q F, u H ⊗q (2.9)
for any element u in the domain of δ q and any random variable F ∈ D q,2 . Moreover, δ q (h) = I q (h) for any h ∈ H ⊙q .

The following property, corresponding to [6, Lemma 2.1], will be used in the paper. Let q 1 be an integer, suppose that F ∈ D q,2 , and let u be a symmetric element in Dom δ q . Assume that D r F, δ j (u) H ⊗r ∈ L 2 (Ω, H ⊗q-r-j ) for any 0 r + j q. Then D r F, u H ⊗r belongs to the domain of δ q-r for any r = 0, . . . , q -1, and we have

F δ q (u) = q r=0 q r δ q-r D r F, u H ⊗r . (2.10) (We use the convention that δ 0 (v) = v, v ∈ R, and D 0 F = F , F ∈ L 2 (Ω).)
For any Hilbert space V , we denote by D k,p (V ) the corresponding Sobolev space of Vvalued random variables (see [10, page 31]). The operator δ q is continuous from D k,p (H ⊗q ) to D k-q,p , for any p > 1 and any integers k ≥ q ≥ 1, and one has the estimate

δ q (u) D k-q,p c k,p u D k,p (H ⊗q ) (2.11)
for all u ∈ D k,p (H ⊗q ), and some constant c k,p > 0. These inequalities are direct consequences of the so-called Meyer inequalities (see [START_REF] Nualart | The Malliavin calculus and related topics[END_REF]Proposition 1.5.7]). In particular, these estimates imply that D q,2 (H ⊗q ) ⊂ Dom δ q for any integer q ≥ 1.

The operator L is defined on the Wiener chaos expansion as

L = ∞ q=0 -qJ q ,
and is called the infinitesimal generator of the Ornstein-Uhlenbeck semigroup. The domain of this operator in L 2 (Ω) is the set

DomL = {F ∈ L 2 (Ω) : ∞ q=1 q 2 J q F 2 L 2 (Ω) < ∞} = D 2,2 .
There is an important relationship between the operators D, δ and L. A random variable F belongs to the domain of L if and only if F ∈ Dom (δD) (i.e. F ∈ D 1,2 and DF ∈ Dom δ), and in this case δDF = -LF.

(2.12)

We also define the operator L -1 , which is the pseudo-inverse of L, as follows: for every F ∈ L 2 (Ω) with zero mean, we set L -1 F = q 1 -1 q J q (F ). We note that L -1 is an operator with values in D 2,2 and that

LL -1 F = E -E[F ] for any F ∈ L 2 (Ω).
3 Proofs of the results stated in Section 1.3

Proof of Theorem 1.2

The proof of Theorem 1.2 is based on a recursive application of the following quantitative result, whose proof has been inspired by the pioneering work of Üstünel and Zakai on the characterization of the independence on Wiener chaos (see [START_REF] Üstünel | On independence and conditioning on Wiener space[END_REF]).

Proposition 3.1 Let m 1 and p 1 , ..., p m , q be integers such that p j q for every j = 1, ..., m. There exists a constant c, uniquely depending on m and p 1 , ..., p m , q, such that one has the bound

|E[ϕ(F )ψ(G)] -E[ϕ(F )]E[ψ(G)]| ≤ c ψ ′ ∞ ϕ q m j=1 Cov(F 2 j , G 2 ),
for every vector F = (F 1 , ..., F m ) such that F j = I p j (f j ), f j ∈ H ⊙p j and E[F 2 j ] = 1 (j = 1, ..., m), for every random variable G = I q (g), g ∈ H ⊙q , and for every pair of smooth test functions ϕ : R m → R and ψ : R → R.

Proof. Throughout the proof, the symbol c will denote a positive finite constant uniquely depending on m and p 1 , ..., p m , q, whose value may change from line to line. Using the chain rule (2.6) together with the relation -DL -1 = (I -L) -1 D (see, e.g., [START_REF] Nualart | A summary of some identities of the Malliavin calculus[END_REF]), one has

ϕ(F ) -E[ϕ(F )] = LL -1 ϕ(F ) = -δ(DL -1 ϕ(F )) = m j=1 δ((I -L) -1 ∂ j ϕ(F )DF j ),
from which one deduces that

E[ϕ(F )ψ(G)] -E[ϕ(F )]E[ψ(G)] = m j=1 E[ (I -L) -1 ∂ j ϕ(F )DF j , DG H ψ ′ (G)] ≤ ψ ′ ∞ m j=1 E | (I -L) -1 ∂ j ϕ(F )DF j , DG H | .
We shall now fix j = 1, ..., m, and consider separately every addend appearing in the previous sum. As it is standard, without loss of generality, we can assume that the underlying Hilbert space H is of the form L 2 (A, A, µ), where µ is a σ-finite measure without atoms. It follows that

(I -L) -1 ∂ j ϕ(F )DF j , DG H = p j q A [(I -L) -1 ∂ j ϕ(F )I p j -1 (f j (•, θ))]I q-1 (g(•, θ))µ(dθ). (3.13)
Now we apply the formula (2.10) to u = g(•, θ) and F = (I -L) -1 ∂ j ϕ(F )I p j -1 (f j (•, θ)) and we obtain, using D r (I -L) -1 = ((r + 1)I -L) -1 D r as well (see, e.g., [START_REF] Nualart | A summary of some identities of the Malliavin calculus[END_REF]),

[(I -L) -1 ∂ j ϕ(F )I p j -1 (f j (•, θ))]I q-1 (g(•, θ)) (3.14)
= q-1 r=0 q -1 r δ q-1-r g(•, θ), D r [(I -L) -1 ∂ j ϕ(F )I p j -1 (f j (•, θ))] H ⊗r = q-1 r=0 q -1 r δ q-1-r g(•, θ), ((r + 1)I -L) -1 D r [∂ j ϕ(F )I p j -1 (f j (•, θ))] H ⊗r .
Now, substituting (3.14) into (3.13) yields

(I -L) -1 ∂ j ϕ(F )DF j , DG H = p j q q-1 r=0 q -1 r ×δ q-1-r A r+1 g(•, s r+1 )((r + 1)I -L) -1 D r s 1 ,...,sr [∂ j ϕ(F )I p j -1 (f j (•, s r+1 ))]µ(ds r+1 ) ,
where s r+1 = (s 1 , . . . , s r+1 ). We have, by the Leibniz rule,

D r s 1 ,...,sr [∂ j ϕ(F )I p j -1 (f j (•, s r+1 ))] = r α=0 r α D α s 1 ,...,sα [∂ j ϕ(F )]D r-α s α+1 ,...,sr [I p j -1 (f j (•, s r+1 ))] = r α=0 r α (p j -1)! (p j -r + α -1)! D α s 1 ,...,sα [∂ j ϕ(F )]I p j -r+α-1 (f j (•, s α+1 , . . . , s r+1 )).
Fix 0 ≤ r ≤ q -1 and 0 ≤ α ≤ r. It suffices to estimate the following expectation

E δ q-1-r A r+1 g(•, s α , t r-α+1 ) (3.15) ×((r + 1)I -L) -1 D α s α [∂ j ϕ(F )]I p j -r+α-1 (f j (•, t r-α+1
))µ(ds α )µ(dt r-α+1 ) .

Note that, in the previous formula, the symbol '•' inside the argument of the kernel g represents variables that are integrated with respect to the multiple Skorohod integral δ q-1-r , whereas the '•' inside the argument of f j stands for variables that are integrated with respect to the multiple Wiener-Itô integral I p j -r+α-1 . By Meyer's inequalities (2.11), we can estimate the expectation (3.15), up to a universal constant, by the sum over 0 β q-r-1 of the quantities

A q-r-1+β E A r+1 g(v q-r-1 , s α , t r-α+1 )D β u β ((r + 1)I -L) -1 D α s α [∂ j ϕ(F )] ×I p j -r+α-1 (f j (•, t r-α+1 )) µ(ds α )µ(dt r-α+1 ) 2 µ(dv q-r-1 )µ(du β ) 1 2 = A q-r-1+β E ((β + r + 1)I -L) -1 A r+1 g(v q-r-1 , s α , t r-α+1 )D β u β D α s α [∂ j ϕ(F )] ×I p j -r+α-1 (f j (•, t r-α+1 )) µ(ds α )µ(dt r-α+1 )) 2 µ(dv q-r-1 )µ(du β ) 1 2 ≤ c A q-r-1+β E A r+1 g(v q-r-1 , s α , t r-α+1 )D β u β D α s α [∂ j ϕ(F )]
×I p j -r+α-1 (f j (•, t r-α+1 )) µ(ds α )µ(dt r-α+1 ))

2 µ(dv q-r-1 )µ(du β )

1 2
.

Thanks to the Leibniz formula, the last bound implies that we need to estimate, for any 0 ≤ η ≤ β ≤ qr -1, the following quantity

A q-r-1+β E A r+1 g(v q-r-1 , s α , t r-α+1 )D α+η s α ,w η [∂ j ϕ(F )] ×I p j -r+α-1+η-β (f j (•, t r-α+1 , y β-η ))µ(ds α )µ(dt r-α+1 ) 2 µ(dv q-r-1 )µ(dw η )µ(dy β-η ) 1 2
.

We can rewrite this quantity as

A q-r-1-β E I p j -r+α-1+η-β (f j (•, y β-η )) ⊗ r-α+1 g(•, v q-r-1 ) ⊗ α D α+η [∂ j ϕ(F )](w η ) 2 ×µ(dy β-η )µ(dw η )µ(dv q-r-1 ) 1 2
.

Applying the Cauchy-Schwarz inequality yields that such a quantity is bounded by

E I p j -r+α-1+η-β (f j ) ⊗ r-α+1 g 2 D α+η [∂ j ϕ(F )] 2 1 2 ≤ E I p j -r+α-1+η-β (f j ) ⊗ r-α+1 g 4 1 4 E D α+η [∂ j ϕ(F )] 4 1 4 .
Set γ = α + η. Applying the generalized Faá di Bruno's formula (see, e.g., [START_REF] Mishkov | Generalization of the formula of Faa di Bruno for a composite function with a vector argument[END_REF]) we deduce that

D γ [∂ j ϕ(F )] = γ! γ i=1 i! k i γ i=1 m j=1 q ij ! ∂ k ∂ j ϕ(F ) ∂x p 1 1 • • • ∂x pm m γ∧p * i=1 (D i F 1 ) ⊗q i1 ⊗• • •⊗(D i F m ) ⊗q im ,
where p * = min{p 1 , ..., p m }, and the sum runs over all nonnegative integer solutions of the system of γ + 1 equations

k 1 + 2k 2 + • • • + γk γ = γ, q 11 + q 12 + • • • + q 1m = k 1 , q 21 + q 22 + • • • + q 2m = k 2 , • • • • • • q γ1 + q γ2 + • • • + q γm = k γ ,
and we have moreover set p j = q 1j +• • •+q γj , j = 1, ..., r, and

k = p 1 +• • •+p m = k 1 +• • •+k γ .
This expression yields immediately that

D γ [∂ j ϕ(F )] ≤ c ϕ q γ∧p * i=1 D i F 1 q i1 • • • D i F m q im
and using the facts that all D k,p norms (k, p 1) are equivalent on a fixed Wiener chaos and that the elements of the vector F have unit variance by assumption, we infer that

E D γ [∂ j ϕ(F )] 4 1 4 ≤ c ϕ q .
On the other hand, using hypercontractivity one has that

E I p j -r+α-1+η-β (f j ) ⊗ r-α+1 g 4 1 4 ≤ c E I p j -r+α-1+η-β (f j ) ⊗ r-α+1 g 2 1 2 . Since E I p j -r+α-1+η-β (f j ) ⊗ r-α+1 g 2 = (p j -r + α -1 + η -β)! f j ⊗ r-α+1 g 2 ,
and

max 1≤r≤q f j ⊗ r g Cov(F 2 j , G 2 ) (see, e.g., [9, inequality (3.26)]),
we finally obtain

E| (I -L) -1 ∂ j ϕ(F )DF j , DG H | ≤ c ϕ q Cov(F 2 j , G 2 ),
thus concluding the proof.

Proof of Theorem 1.2. Just observe that

E d j=1 ψ j (F j ) - d j=1 E[ψ j (F j )] d j=2 E[ψ 1 (F 1 ) • • • ψ j-1 (F j-1 )] E[ψ j (F j )] • • • E[ψ d (F d )] -E[ψ 1 (F 1 ) • • • ψ j (F j )] E[ψ j+1 (F j+1 )] • • • E[ψ d (F d )] ,
so that the conclusion is achieved (after some routine computations) by applying Proposition 3.1 (in the case m = j -1, p i = q i , i = 1, ..., j -1, and q = q j ) to each summand on the right-hand side of the previous estimate.

Proof of Theorem 1.3

The equivalence between (1) and ( 2) follows from [START_REF] Nourdin | Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws[END_REF]Theorem 3.4]. That (3) implies (1) would have been immediate if the square function x → x 2 were bounded. To overcome this slight difficulty, it suffices to combine the hypercontractivity property of chaotic random variables (from which it follows that our sequence (F n ) is bounded in L p (Ω) for any p 1) with a standard approximation argument. Finally, the implication (1) ⇒ (3) is a direct consequence of (1.3).

Proof of Theorem 1.4

Assume that there exists a subsequence of {F n } converging in distribution to some limit (V 1 , . . . , V d ). For any collection of smooth test functions ψ 1 , ..., ψ d : R → R, one can then write Indeed, the first equality in (3.16) is a direct consequence of Theorem 1.3, the second one follows from the fact that V j law = U j for any j by assumption, and the last one follows from the independence of the U j . Thus, we deduce from (3.16) that (U 1 , . . . , U d ) is the only possible limit in law for any converging subsequence extracted from {F n }. Since the sequence {F n } is tight (indeed, it is bounded in L 2 (Ω)), one deduces that F n law → (U 1 , . . . , U d ), which completes the proof of Theorem 1.4.

E

  [ψ j (V j )] = d j=1 E [ψ j (U j )] = E d j=1 ψ j (U j ) .(3.16)

; IN was partially supported by the ANR Grant ANR-10-BLAN-0121. ; DN was partially supported by the NSF grant DMS1208625. ; GP was partially supported by the grant F1R-MTH-PUL-12PAMP (PAMPAS), from Luxembourg University.


Bruno Astuto

Arouche Nunes

Katia Obraczka

A Framework for Modeling Spatial Node Density in Waypoint-Based Mobility

User mobility is of critical importance when designing mobile networks. In particular, "waypoint" mobility has been widely used as a simple way to describe how humans move. This paper introduces the first modeling framework to model waypoint-based mobility. The proposed framework is simple, yet general enough to model any waypoint-based mobility regimes. It employs first order ordinary differential equations to model the spatial density of participating nodes as a function of (1) the probability of moving between two locations within the geographic region under consideration, and (2) the rate at which nodes leave their current location. We validate our models against real user mobility recorded in GPS traces collected in three different scenarios. Moreover, we show that our modeling framework can be used to analyze the steady-state behavior of spatial node density resulting from a number of synthetic waypoint-based mobility regimes, including the widely used Random Waypoint (RWP) model. Another contribution of the proposed framework is to show that using the well-known preferential attachment principle to model human mobility exhibits behavior similar to random mobility, where the original spatial node density distribution is not preserved. Finally, as an example application of our framework, we discuss using it to generate steady-state node density distributions to prime mobile network simulations.

Introduction

When designing and evaluating wireless networks and their protocols, user mobility is a critical consideration. So much so that user mobility has inspired an extensive body of work both in infrastructure-based networks (e.g., wireless LANs or WLANs), as well as in infrastructure-less networks, a.k.a., wireless, self-organizing networks (WSONs). The latter include wireless mobile adhoc networks (MANETs), wireless sensor networks (WSNs), and disruptiontolerant networks (DTNs). Unlike their infrastructure-based counterparts where only end user nodes are mobile, in infrastructure-less networks, every node may move and thus mobility plays a considerable role in the performance of the network.

Synthetic mobility regimes are an important consideration on simulating, testing and conducting performance evaluation on wireless networks and their protocols. The research community have been investing quite a lot of effort in developing mobility models that would reflect more faithfully the mobility patterns and characteristics found in real mobile applications. When moving in real mobility scenarios (e.g. walking on a park, city center, university campus, etc), humans do not behave randomly, but tend to form groups and clusters, even when moving independently of each other. These clusters are formed due to the social interactions between the mobile entities, geographical restrictions in the area, the intrinsic attraction some specific locations might have towards some nodes, etc. One way to characterize and describe mobility, and study how mobile entities interact and agglomerate is through the spatial density of mobile nodes. Spatial node density can be defined as the number of nodes located in a given unit area and has significant impact on fundamental network properties, such as connectivity and capacity, as well as on core network functions, e.g., medium access and routing.

Yet, the characterization of real human mobility through spatial node density remains a challenging subject. To date, only a few efforts have focused on modeling spatial density. Notable examples include [START_REF] Gyarmati | Impact of random mobility on the inhomogeneity of spatial distributions[END_REF][START_REF] Bettstetter | The node distribution of the random waypoint mobility model for wireless ad hoc networks[END_REF][START_REF] Navidi | Stationary distributions for the random waypoint mobility model[END_REF]. However, most previous work have been focusing exclusively on synthetic mobility regimes, specially the Random Waypoint (RWP) model [START_REF] Bettstetter | Stochastic properties of the random waypoint mobility model[END_REF], since it is the most used mobility model in the literature, due to its simplicity and easy of implementation.

In this paper, we focus on modeling the spatial node density of "waypoint"based mobility. More specifically, our model describes the spatial density steadystate behavior under waypoint-based mobility which is a mobility pattern characterized by having nodes probabilistically choose the next destination, or waypoint, based on some probability density function, moving to this point with a given speed, pausing for some time, and starting the process again. We define spatial density as the percentage of subareas (or cells) containing ≥ k nodes, which can also be viewed as the probability of finding a cell with k or more nodes at a given time. We assume a Markovian property for this quantity as the count of the number of users in each cell (our state) at the next time instant only depends on the number of users in the cells in the current time instant, given the cost of making a transition (increasing or decreasing the number of users in each cell), and the rate at which transitions occur. We present an approximation by a set of Ordinary Differential Equations (ODEs) and propose a framework to mathematically model spatial node density under different "waypoint"-based mobility regimes.

We contend that waypoint-based mobility is one way to describe forms of human mobility. Therefore, we apply our model to describe the steady state of real human mobility and validate it against real user mobility recorded by GPS traces in different scenarios, comparing the results against the corresponding traces. Moreover, we present comparative results for steady-state spatial distribution analysis of a number of synthetic waypoint mobility regimes. To the best of our knowledge, this is the first node density modeling framework generic enough that it can be applied to any waypoint-based mobility regime.

As an example, we use our framework to model the well-known RWP mobility regime. Our model confirms the well-known result showing that node density's steady-state behavior under RWP mobility tends to homogeneity, as defined in [START_REF] Bettstetter | An inhomogeneous spatial node distribution and its stochastic properties[END_REF] 1 . Furthermore, several previous work on synthetic mobility modeling (discussed in more detail in the next section) apply the preferential attachment principle [START_REF] Albert | Statistical mechanics of complex networks[END_REF], in order to create and maintain the formation of clusters of mobile nodes. We also use our framework to model waypoint-based mobility regimes that apply the preferential attachment principle. We show through the application of our proposed model that using preferential attachment to model human mobility leads to undesirable steady-state behavior. More specifically, our model shows that, at steady state, the original spatial node density distribution is not preserved and exhibits behavior similar to random mobility a la Random Waypoint regime. This behavior has been observed empirically in [START_REF] Nunes | On the invariance of spatial node density for realistic mobility modeling[END_REF]. Instead, real human mobility exhibits "persistent" density heterogeneity as illustrated in Figure 1. This figure shows the spatial density distribution for one of the traces used in this paper which was collected in the Quinta da Boa Vista Park in Rio de Janeiro, Brazil.

The first 4 curves in the plot refer to the distributions at instants 300, 500, 700, and final (900 seconds), which is the end of the trace collection interval. The two other curves correspond to the node density distributions measured after 900 seconds of simulations of two synthetic waypoint-like mobility regimes, namely RWP and Natural [START_REF] Borrel | On natural mobility models[END_REF]. Each of these curves reflect the final node distribution averaged over 10 runs of simulations2 . Both mobility models and the experiments that generated these curves are discussed in detail in Section 5. The last curve shown in the graph is the initial node distribution measured from the Quinta trace and also used as the initial distribution in all simulation runs of both synthetic mobility regimes studied.

From Figure 1, we observe that the density distribution of the real trace does not vary much with time: the largest deviation from the initial distribution for any value of k at any instant is 8.3%; the average deviation from the initial distribution measured in all the instants for all values of k is 1.27%. Similar observations can be drawn from the other traces used in our work as reported in Section 4.1. Moreover, we also observe a very different behavior when applying either one of the synthetic regimes to the same scenario. They deviate significantly from the initial conditions.

However, an interesting observation here is the fact that using a preferential attachment based regime such as Natural, does not preserve the original clustering of the nodes. In fact, spatial density resulting from preferentialattachment based waypoint mobility "deteriorates", at steady state, to behavior similar to random mobility. In Section 5, we present more details on these results and apply our proposed model to study the steady-state behavior of spatial density of these mobility regimes.

Overall, the contributions of our work are many-fold: (1) we introduce the first spatial node density modeling framework for waypoint mobility regimes, (2) we apply our proposed framework to study the steady state behavior of real human mobility in three different real mobility scenarios, (3) we present results from applying the proposed framework over two different waypointbased mobility models, (4) we use our model to show that the steady-state behavior of node density under preferential-attachment based mobility does not preserve node density's original distribution and exhibits behavior similar to random mobility, and (5) as an example application of our framework, we discuss using it to generate steady-state node density distributions to prime mobile network simulations.

The remainder of this paper is organized as follows. Section 2 places our work in perspective by presenting related work in mobility modeling and characterization. Our ODE model is presented in detail in Section 3, how its parameters are set, and our implementation. Section 4 show the validation of our proposed framework towards modeling real human mobility, while Section 5 presents the applications of our work on modeling spatial density of synthetic waypoint-based mobility regimes. Finally, Section 6 concludes the paper with a discussion of future work.

Related Work

Mobility models are vital to the design, testing, and evaluation of wireless networks and their protocols. As an indication of the importance of mobility models to the study of wireless network protocols, most well-known network simulators include "mobility generators", which, following a pre-specified mobility regime, determine the position of network nodes over time during simulation runs. Synthetic mobility generators have been extensively used in the study of wireless networks [START_REF] Camp | A survey of mobility models for ad hoc network research[END_REF]. A notable example of such synthetic mobility models is the Random-Waypoint Mobility (RWP) regime [START_REF] Bettstetter | Stochastic properties of the random waypoint mobility model[END_REF].

The work by Bettstetter et al. points out that random mobility leads to homogeneous node distributions [START_REF] Bettstetter | An inhomogeneous spatial node distribution and its stochastic properties[END_REF]. They proposed a method that creates initial non-homogeneous node distributions and in [START_REF] Gyarmati | Impact of random mobility on the inhomogeneity of spatial distributions[END_REF], analyze via simulations the impact of random mobility in maintaining the non-homogeneity of spatial node density distributions. They also propose a metric for measuring such non-homogeneity as well as a variant of RWP mobility that maintains the non-homogeneity of an original node distribution.

More recently, network researchers and practitioners have been trying to use more realistic scenarios to drive the evaluation of wireless network protocols. This motivated initiatives such as the CRAWDAD [12] trace repository, which makes real traces available to the networking community. These traces can then be used to run trace-driven simulations. Even though initiatives like CRAWDAD have greatly increased availability of real traces, relying exclusively on traces to design and evaluate network protocols would not allow a broad enough exploration of the design space.

To address this problem, a number of efforts have proposed mobility models based on realistic mobility patterns [START_REF] Musolesi | Mobility models for systems evaluation[END_REF]. Notable examples include [START_REF] Balachandran | Characterizing user behavior and network performance in a public wireless lan[END_REF][START_REF] Balazinska | Characterizing mobility and network usage in a corporate wireless local-area network[END_REF]1,[START_REF] Henderson | The changing usage of a mature campus-wide wireless network[END_REF]. More recent work focuses on the "scale-free" properties observed in many real networks like the Internet, the Web, and some social networks, to name a few. The seminal work of Barabási and Albert [START_REF] Albert | Statistical mechanics of complex networks[END_REF] proposes a model that generates scale-free networks, i.e., networks whose node degrees follow a power law distribution. They demonstrate that many real-world networks are scale free, that is, the node degree in the network graph follows a power law and discuss the mechanism responsible for the emergence of scale-free networks. They argue that understanding this problem will require a shift from modeling network topology to modeling "network assembly and evolution". To this end, they de-fine the Barabási-Albert model based on growth and preferential attachment. Growth refers to the fact that the number of nodes in the network increases over time, where a new node is placed with m edges connecting it to other m nodes. Preferential attachment means that a node will choose to connect to another node i with probability Π(k i ) = ki � j kj based on the degree k i of node i and any node j connected to node i. In other words, the preferential attachment principle states that "the more connected a node is, the more likely it is to receive new links". Several recently proposed mobility models (e.g., [START_REF] Jardosh | Real-world environment models for mobile network evaluation. Selected Areas in Communications[END_REF][START_REF] Kim | Extracting a mobility model from real user traces[END_REF][START_REF] Borrel | On natural mobility models[END_REF][START_REF] Mei | Swim: A simple model to generate small mobile worlds[END_REF][START_REF] Musolesi | Designing mobility models based on social network theory[END_REF][START_REF] Lim | Clustered mobility model for scale-free wireless networks[END_REF]), try to mimic real human mobility by following the preferential attachment principle: they define attraction points, whose probabilities of attracting other nodes increase as more nodes congregate around them. The main goal of these preferential attachment based approaches is to try to maintain the non-homogeneous characteristics of spatial node density observed in real mobility traces. This calls for models that are able to create and maintain the non-homogeneous node distributions and clustering observed in real human mobility. For example, in [START_REF] Borrel | On natural mobility models[END_REF], a model based on preferential attachment has been proposed, where the choice of going towards an attraction region is weighted proportionally to the region's popularity (i.e., the number of other nodes that chose it) and inversely proportional to the distance to it. We call this model Natural and use it as one of our case of studies. More specifically, we apply our framework to model Natural's spatial node density stationary regime and show that it exhibits similar characteristics when compared to random mobility patterns such as Random Waypoint.

The work proposed in [START_REF] Lim | Clustered mobility model for scale-free wireless networks[END_REF] is another example of a model that follows Barabási-Albert's growth and preferential attachment principles. The authors even show a figure where they present their initial (after growth) and steadystate spatial distribution. It is possible to see how clusters dissipate and fade away over time. The same concept is also used in [START_REF] Mei | Swim: A simple model to generate small mobile worlds[END_REF] where nodes are also driven by pre-defined social interactions. The proposed approach is validated by showing the power-law exponential decay of inter-contact times among node communities, comparing it with measurements in real traces.

One distinguishing feature of our work is the generality of our modeling framework which can be applied to any waypoint mobility regime. Waypoint mobility follows the following basic steps: (1) a node chooses its next destination following some given probability distribution; (2) moves to that destination in a straight line and constant speed; (3) pauses for some time (also following some pre-specified rule); and (4) repeats the process. Most previous work on modeling node spatial density have focused specifically on the RWP model. In [START_REF] Bettstetter | The node distribution of the random waypoint mobility model for wireless ad hoc networks[END_REF], for example, analytical expressions are derived for the spatial density distribution that results from using the RWP model in simulations. The one-dimensional case is analyzed and an approximation for the two-dimensional case is also given. They also analyze the concept of attraction areas in a modified version of the RWP regime. One other effort that focused on modeling steady-state behavior of the RWP is described in [START_REF] Navidi | Stationary distributions for the random waypoint mobility model[END_REF]. In that work, stationary analytical expressions for node density and node speed are derived.

Our approach was inspired by classical epidemiological models [START_REF] Daley | [END_REF] which allowed us to derive a framework that is not only general but also simple when compared to analytically solving Markov chains. This is because our framework is derived directly from a transaction-by-transaction Markov process modeling. We follow the analogy with epidemiology where mobile users "infect" subareas (or cells) as they move into them, and cells are "cured" as nodes move away from them, towards other destinations (susceptible to infection).

Another distinguishing feature of our approach is that it is based on Ordinary Differential Equations (ODEs). ODEs have been used to model a wide variety of networking functions and services. For example, ODEs were applied in a similar fashion to model epidemic forwarding [34] in a DTN environment. Similarly, in [START_REF] Fawal | Selflimiting epidemic forwarding[END_REF], an ODE model to analyze the performance of self-limiting epidemic forwarding mechanisms has been proposed. Similar ODE approaches have been applied to model worm propagation on the Internet [START_REF] Staniford | How to own the internet in your spare time[END_REF][START_REF] Zou | Code red worm propagation modeling and analysis[END_REF][START_REF] Chen | Modeling the spread of active worms[END_REF], and bitTorrent file sharing [START_REF] Kesidis | Qrp03-1: An epidemiological model for file-sharing with bittorrent-like incentives: The case of a fixed peer population[END_REF].

Moreover, in [15] Partial Differential Equations (PDEs) have been used to model spatial node density of the RWP and Random Direction mobility regimes. An analysis of the transient behavior of the spatial node density under these two mobility regimes is described. While this work is another example of efforts that focus on studying random mobility, our approach is generic enough that can be used to study any waypoint-based mobility regime (including random approaches and preferential-attachment based regimes). The work described in [START_REF] Heimlicher | Globs in the primordial soup: the emergence of connected crowds in mobile wireless networks[END_REF] proposes a Markovian based mobility model with the purpose of forming and dissolving clusters of nodes. They study analytically spatial distribution of nodes, presenting results, specifically for their mobility model.

Proposed Model and Framework

Our objective is to model the spatial node density of a mobile network. We assume a waypoint-based mobility pattern, where nodes stay in a given location i for a given period of time and choose to leave i towards another location j with probability p ij . Once the node arrives at j, the process restarts.

ODE Framework

Assume a mobile network composed of m mobile nodes, where all nodes are capable of moving around inside a delimited area a. Now assume this area is divided into equally sized square subareas of size l × l, defined here as cells. The mobile nodes can then choose to move from cell to cell with a given probability. Let X(t) be the stochastic process that determines which cell a mobile node chooses at time t. We can write then p ij = P {X(t) = i | X(t + γ) = j}, as the transition probability, which is the probability that a node in cell i, at time t, is going to choose to go to cell j at time (t + γ), after some time step γ.

Thus, we are interested in the average number of nodes in each cell i, represented by the component N i (t) ∀i ∈ {1, ..., n} of the state vector N (t) ∈ R n×1 , where n is the total number of cells for the desired scenario.

The variation in the number of nodes at each cell Ṅi (t) = dNi(t) dt is simply the difference between nodes arriving in cell i and the ones departing from the same cell at time t, as expressed in Equation 1.

Ṅi (t) = λ 0 + � j p ji µ j N j (t) � �� � Arriving at cell i - � � j p ij µ i N i (t) + µ 0 N i (t) � � �� � Departing from cell i , (1)
where λ 0 is the rate at which new nodes arrive in cell i from outside the system and µ 0 the rate at which nodes decide to get disconnected and leave the system, given that they are at cell i. Also, µ i is the rate at which nodes decide to leave cell i towards another cell, which allow us to write µ ij = p ij µ i as the rate at which nodes in cell i decide to leave this cell towards cell j. We can also define the arrival rate in cell i as the sum of the departing rates of all nodes going from cell j to cell i, over all possible values of j, including j = i, since we allow transitions from a cell to another position in itself. The arrival rate is given by Equation 2.

λ i = � j p ji µ j . (2)

Parameters Choice, Discussion and Simplifications

In reality we observe that nodes prefer some cells over others and some transitions over others. The probability of choosing a destination and the rate at which nodes depart from that destination depends on how popular that destination is and what are the nodes' interests in each destination. For example, nodes moving around on a campus environment may go very often from the cafeteria to the classroom, but not so often from the cafeteria to the library. This means that p cafeteria,classroom > p cafeteria,library . Moreover, since people might tend to stay inside the library for longer than in the cafeteria, the relationship between the departure rate from this two locations might be such as µ cafeteria > µ library .

In order to simplify our model, more specifically the choice of the parameters (departure rates and transition probabilities), we define the rate µ i as the inverse of the average time spent by the nodes in cell i. We also considered the transition probabilities independent of where the transition originated. This means that the probability of going from cell j to cell i is the same probability of simply choosing cell i as the next destination for all j. We then make

p ji = P {X(t) = j | X(t + γ) = i} = P {X(t + γ) = i} = p i .
Moreover, in order to validate our model we have chosen to extract the model parameters from-and compare our results with-real live GPS traces, where the number of nodes in the system remains constant during the whole duration of the trace. For that reason, in the results we present in Section 4.3 we used a slightly simplified version of our model, where λ 0 = µ 0 = 0. Equation 3 gives this version of our ODE model.

Ṅi (t) = � j p i µ j N j (t) � �� � Arriving at cell i - � j p j µ i N i (t) � �� � Departing from cell i , (3)

Implementation

In this section we present a vectorized version of Equation 3, so that we could implement it on MATLAB [23]. We used a 4th order Runge-Kutta ODE solver, native to the platform, to do so. We start by defining a matrix A ∈ R n×n as a parameter matrix given by A = P × M . P ∈ R n×1 is a column vector containing in every ith position the probability p i of a node choosing cell i as the next destination, and M ∈ R 1×n a row vector containing in every ith position the rate µ i at which nodes choose to leave cell i. The components of matrix A, resulting from this multiplication are a ij = p i µ j .

Thus, it is possible to write Equation 3for Ṅ (t) ∈ R n×1 in its equivalent vectorized form as follows:

Ṅ(t) = A × N (t) � �� � Arriving - � (A T × 1) • N (t) � � �� � Departing , (4)
where A T is the transpose of matrix A, that we multiply by 1 ∈ R n×1 , a column vector of ones, to give us a resulting n × 1 column vector in which every component i represents the summation of all the components of the ith row of matrix A T . After that, we perform a component wise multiplication with the state vector N (t), which gives us the number of nodes departing from a given cell. That represents the second summation in the right-handed side of Equation 3.

Spatial Node Density of Human Mobility

We validate our model using real mobility traces; in other words, we show how the model can be applied to describe the steady-state behavior of spatial node density associated with human mobility. Three real GPS traces were used in our validation. These traces were collected in scenarios that are quite diverse, namely a city park, a university campus, and a state fair. We describe these traces in detail below as well as how we use information from the traces to estimate the parameters of our ODE framework.

Mobility Traces

Table 1 summarizes the GPS traces in terms of number of users, duration of the trace, and GPS sampling period.

Quinta, refers to the "Quinta da Boa Vista Park" trace, first presented in [START_REF] Azevedo | An analysis of human mobility using real traces[END_REF]. It is a GPS trace collected at a park in the city of Rio de Janeiro, Brazil. The park has many trees, lakes, caves, and trails. It houses the National Museum of Natural History and the city Zoo. The KAIST trace [30], on the other hand, is a GPS trace collected at the KAIST University campus in Daejeon, South Korea. The Statefair trace, also available at [30], is yet another mobility scenario showing daily GPS track logs collected from the NC State Fair held in North Carolina, USA.

We select sections of the raw traces where no discontinuity occurred, i.e., we use only nodes which recorded a continuous sequence of GPS fixes that were 900-, 5000-and 8000 seconds long for the Quinta, KAIST, and Statefair traces, respectively. These times were the total duration of the traces.

Parameter Estimation

We extract from the traces the distributions of speed, pause time, and node density. We use the trace's sampling period, e.g., for example, in the Quinta trace, the sampling period is T = 1 seconds. Node speed is defined as d Δt where d is the distance traveled between two consecutive entries in the GPS trace at times t 1 and t 2 and Δt = t 2t 1 . Pause time is defined as P = Δt, if d < threshold, or zero otherwise. The threshold is used to account for GPS error. We set this threshold to be 2 meters for KAIST and Statefair traces and 0.5 meter for the Quinta trace, due to jitter in GPS update frequency.

To extract spatial node density, the area covered in the trace is divided into squared cells of 140 x 140 meters. The choice of cell size was based on empirical observations, i.e., we picked a cell size that provided both adequate resolution as well as clustering. An alternate approach could be based on identifying "attraction zones", as was done in [START_REF] Kim | Extracting a mobility model from real user traces[END_REF]. This is one of the topics of future work we plan to address. At the limit, i.e., where the cell is either infinitesimal (lower limit) or the size of the whole area (upper limit), all the traces and synthetic mobility regimes would have the same relative spatial density, namely one or zero nodes per cell for the lower limit and all the nodes in the same (unique) cell for the upper limit.

After dividing the area into cells, we took a snapshot of the number of nodes at every cell every T seconds. The value of T = 10 was used since, for the size of the cells and the speeds sampled from the traces, a node could not on average change between more than two cells during T . For every cell, at every interval T we counted the number of nodes in each cell. We then averaged the number of nodes in each cell over the course of the whole duration of the trace. The result is what we refer to as Intensity Map (IM) which we use to estimate the probability a node will choose a given cell as its next destination.

In the case of real mobility, e.g., as described by GPS traces, we set the probabilities of choosing a given cell, p i of our ODE model to be the normalized value of the IM for cell i, such that p i = IM(i) � j IM(j) , where IM(i) is the intensity in cell i.

The rate µ i , as mentioned before, is computed as the inverse of the average time spent by the nodes in cell i. This time has two components. The time spent by the node moving towards or from a given point in the cell, and the time spent in pause at this point, which reflect both main basic parameters of human mobility, speed and pause time. This two components were empirically measured from the GPS traces and used to compute µ i .

Results

As highlighted in previous sections, the goal of our model is to describe the steady-state behavior of spatial node density in waypoint-like mobility regimes in which: (1) a node chooses its next destination following some given probability distribution, (2) moves to that destination, (3) pauses for some time, and (4) repeats from step (1).

Spatial node density is defined as the percentage of cells containing ≥ k nodes. It can also be expressed as the probability of finding a cell containing ≥ k nodes. It describes the degree of "clustering" exhibited by mobility regimes and can be used to evaluate how close to reality a given synthetic mobility regime is as far as its ability to mimic the degree of clustering exhibited by real mobility.

We followed the guidelines presented in Section 4.2 to estimate the parameters of our model for each of the traces studied. Figures 2, 3 and4 plot spatial node density in the Quinta, KAIST, and Statefair scenarios, respectively. Each figure shows three curves plotting the spatial density: (1) at the beginning of the trace, (2) at the end of the trace, i.e., at 900 seconds for the Quinta Trace, 500 seconds for KAIST, and 8000 seconds for the Statefair, and (3) by applying our ODE framework. Note that the plots for the KAIST and Statef air traces are zoomed into the region of interest. In those two plots, the only point not shown is k = 0, where the percentage of cells containing 0 or more nodes P [k ≥ 0] is the same for every curve and it is, of course, equal to 100%.

The largest deviation of our ODE model from the final density distribution measured from the traces, for any value of k at any instant is 5.36%, 0.58% and 7.52%; the average deviation from the initial distribution measured in all the instants for all values of k is 1.45%, 0.06% and 2.02% for the Quinta, KAIST and Statefair traces respectively.

Node Density in Synthetic Waypoint Mobility

Here we show our framework's ability to closely describe the steady-state behavior of spatial node density resulting from synthetic waypoint-like mobility. We apply our model to two different regimes, namely Random Waypoint (RWP) [START_REF] Bettstetter | Stochastic properties of the random waypoint mobility model[END_REF] and the Natural [START_REF] Borrel | On natural mobility models[END_REF] mobility. We start by briefly describing these two mobility regimes and then present the setup we used to generate mobility traces under them. Subsequently, we explain how we estimated the parameters for the model and present results comparing spatial node density distributions resulting from the synthetic mobility regimes and our model.

RWP Mobility

Random Waypoint (RWP) mobility, an example of waypoint-like mobility regime, has been widely used in the study of multi-hop ad-hoc wireless networks (MANETs). Under RWP mobility, mobile nodes are initially placed in the area being simulated according to a given distribution. Typically, a uniform distribution is used. Each node remains in its position for a given period of time, called pause time P uniformly chosen in the interval [0, P max ], where P max is a pre-specified parameter. After this period, the mobile node chooses a new destination uniformly distributed in the simulation area, and a speed, also uniformly distributed in the interval [v min , v max ], where both v min and v max are pre-specified parameters. Once the destination is reached, the node pauses again and chooses another destination and speed, as described above.

The Natural Mobility Regime

We also compare our results against mobility regimes that follow the preferential attachment principle. As representative of this family of mobility regimes, we use the Natural mobility model, or simply Natural [START_REF] Borrel | On natural mobility models[END_REF]. As discussed in Section 2, Natural is based on attraction points, where the attractiveness of each point is proportional to the attractor's popularity given by the number of nodes at or going towards it and inversely proportional to the distance to it. Thus, the probability Π(a i ) that a node z k chooses an attractor a i among all possible attractors is proportional to the portion of the total attractiveness it carries:

Π(a i ) = Aa i ,z k � j Aa j ,z k
. The attractiveness of an attractor is then defined as:

A ai,z k = (1 + � zj ∈Z,zj� =z k B(a i , z k )) � (X ai -X z k ) 2 + (Y ai -Y z k ) 2 (5)
where B(a i , z k ) is a Bernoulli variable, with B = 1 if the individual z k is going toward or staying at attractor a i and 0 otherwise, and X and Y are the coordinates of a node and an attractor. In our implementation, we divided the simulation area in equally sized squares, or cells, and consider each cell to be an attraction point. The coordinates (X ai , Y ai ) mark the center of the i-th attraction point. Once the new destination is known, the node travels towards it with a speed that is uniformly distributed in the interval [v min , v max ]. A pause time is randomly selected once arriving at the destination before choosing another destination and beginning the process again.

Generating Synthetic Waypoint Mobility Traces

Using a modified version of the Scengen [32] scenario simulator we generated mobility traces according to the RWP and the Natural mobility regimes. We setup the simulations trying to mimic the three real scenarios described in this paper, for Quinta, KAIST and Statefair. Three sets of synthetic traces were generated using the RWP and Natural mobility models. The speed range was set in a way that the average speed would match the ones measured in the GPS traces.

In order to address the decaying speed problem reported in [START_REF] Yoon | Random waypoint considered harmful[END_REF], we followed the recommendations mentioned in that work. The speed range was thus set to be ± the standard deviation measured in the real traces around the measured average speed. Thus, the speed was chosen uniformly in a range in which the lower limit was greater than zero and where the mean matches the one measured in the real traces. This is the simplest though not the optimal solution mentioned in [START_REF] Yoon | Random waypoint considered harmful[END_REF]. However, since the focus of our work is not network performance evaluation itself, we found this solution to be suitable for our purposes.

Pause time was chosen uniformly in the range [0, P max ], where the value of P max was set to an appropriate value, in a way that the average pause time would match the one measured in the real traces. The same was done for the dimensions of the rectangular simulation area, set to be the same as in the GPS traces. Moreover, in all simulation scenarios, we used the same initial positions found in the respective real traces for the same number of users. For further discussions on the actual distributions for these traces' mobility parameters, please refer to [START_REF] Azevedo | An analysis of human mobility using real traces[END_REF]30].

When applying the ODE framework to describe spatial density behavior in synthetic mobility, p i follows the probability distribution particular to the specific mobility regime used. For example, in RWP mobility, p i is the same for every value of i, since the probability of choosing the next waypoint follows a uniform distribution. For Natural, the probability of choosing a given cell is computed "on-the-fly", based on the cell's attractiveness, defined by Equation 5.

The rate µ i is computed as the inverse of the average time spent by the nodes in cell i. This time has two components. The time spent by the node moving towards or from a given point in the cell, and the time spent in pause at this point. This two components were empirically measured from long simulations (10 5 seconds), using the same parameters for each scenario, and used to compute µ i . A more generic approach to determine the value of this parameters for a given generic scenario is the subject of our future work.

Reported simulation results on density, comparing our ODE framework with simulated traces, reflect 10 runs of the simulations using each mobility regime at each scenario. Table 2 summarizes the simulation parameters.

Results

Figures 5 and6 show the results for spatial node density distribution at the Quinta scenario, for the RWP and Natural mobility regimes respectively. The plots show three curves corresponding to: 1) the initial density distribution taken from the trace and used to feed all the simulations for both mobility models, 2) the steady-state density distribution using the proposed ODE framework applied to the RWP and Natural mobility regimes, and 3) the final density distribution measured and averaged at the end of the simulations for the synthetic mobility regimes. The first obvious observation analyzing these plots is that the synthetic mobility regimes are unable to follow the long tail behavior of the density metric presented by the distribution measured in the real traces. Moreover, as we demonstrated in the previous section, the presented ODE model is able to follow this long tail characteristic when applying the parameters extracted from the real traces. In the case of the synthetic models, when applying the exit rate and probability of choosing the next cell, characteristic to each mobility regime, the proposed framework now behaves as the synthetic models do and is able to describe density distribution curves very similar to the RWP-like regimes studied.

Figures 7 and8 show the results for spatial node density distributions at the KAIST scenario, for the RWP and Natural mobility regimes respectively. Similar results can be observed in Figures 9 and10 for the Statefair scenario. Once again, the plots for the KAIST and Statef air traces are zoomed in to the region of interest.

These show not only the flexibility of the proposed ODE framework and that it is able to describe the steady-state behavior of the density distribution of real and synthetic (RWP-like) mobility, but it also show the accuracy of the proposed approach. Fig. 6 Initial spatial node density distribution for the Quinta trace, simulated final density distribution using the Natural mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the Natural mobility regime.

Application

In addition to its applications in the study of the steady-state behavior of spatial node density of waypoint-like mobility regimes, we find another very interesting application of our framework. Recall that the output of our model is a vector where each position contains the expected number of nodes encountered Fig. 8 Initial spatial node density distribution for the KAIST trace, simulated final density distribution using the Natural mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the Natural mobility regime. in the cell corresponding to that position. This vector provides node density distribution at steady-state. Consequently, we can interpret the normalized value in each cell as the probability of placing a node in that cell. In other words, the normalized output vector can be seen as the steady-state spatial distribution for the waypoint-based mobility regime of interest. In this context, following the steady-state distribution given by our model, it is possible to use a Fitness Proportionate Selection scheme, such as the Roulette-Wheel described in [START_REF] Nunes | On the invariance of spatial node density for realistic mobility modeling[END_REF] and commonly used in genetic algorithms [START_REF] Pan | [END_REF] to perform initial node placement when setting up wireless network simulations. Fig. 11 RWP simulation using initial density conditions from the trace (solid lines), and simulation using the output of the ODE framework as the initial density conditions (dashed lines).

Figure 11 illustrates this usage of our model. The solid lines in this plot reflect one simulation of the RWP regime in the Quinta scenario at instants 0 seconds (initial placement using the initial positions from the Quinta trace), 50, 500, 700 and 1500 seconds of simulation. It is possible to see how the solid lines "move away" from the initial conditions and converge to the steady-state. Another simulation with the same seed and parameters was run, using the initial node placement given by the normalized output of the ODE framework. The dashed lines correspond to this initial distribution, and the measured final distribution at 1500 seconds of the same simulation run. As we can see, these two curves are very similar, showing that the output of our model gives an accurate steady-state distribution for the studied mobility regime, where the final distribution measured at the end of the simulation does not deviate form the initial placement provided by the ODE model. These two curves (the dashed ones) are a very close match also to the final distribution of the simulation that uses the trace's initial node placement (solid line at 1500 seconds). Density results of simulations using the Natural mobility regime were also generated, with the exact same parameters and scenario. The same behavior was observed.

In conclusion, the main advantages of using the output of our framework for initial node placement in wireless network simulations are two-fold. First, as illustrated by Figure 11, by defining what the steady-state node density distribution is, the model saves considerable simulation time, which is the time it takes to get to the steady-state behavior. For instance, in the case of the RWP simulation, for this particular scenario, steady state is achieved after 700 seconds, since the 700 seconds curve and the 1500 second are almost indistinguishable. Second, this result is important, once it is very difficult to determine when a model is going to reach a steady state, since this time varies from scenario to scenario and according to the mobility model and parameters used. Using our ODE model's output to establish what the steadystate behavior is constitutes a technique that is much more scientifically sound than figuring out when steady state is achieved by inspecting the mobility model's behavior over time.

Conclusions

In this paper, we developed a framework to study waypoint mobility regimes which have been widely used in the design and evaluation of mobile networks and their protocols. With our framework, which is based on first-order ordinary differential equations, it is possible to model the stationary behavior of spatial node density resulting from waypoint-based mobility regimes as well as real mobility described by GPS traces. We validated our approach by comparing its results against real mobility recorded by GPS traces. We also presented steady-state spatial distribution for two synthetic mobility regimes in three different scenarios. To the best of our knowledge, this is the first approach to spatial node density modeling that is generic enough that can be applied to any waypoint-like mobility regime.

We also use the proposed model to show the inability of waypoint-based mobility regimes that are based on the preferential attachment principle to maintain non-homogeneous spatial node density distributions, preserving node clusters. We show that in steady-state, preferential attachment based models result in node density distributions that approach the distribution of a totally random mobility regime, such as the RWP mobility model.

As another application of our framework, we discuss how our modeling framework can be applied to derive stationary spatial node density distributions which can then be used to perform initial node placement when setting up mobile network simulations.

As part of our ongoing and future work plans, we plan on integrating our model to existing network simulation platforms in order to prime network simulations with steady-state node density distributions. Developing mobility regimes capable of reflecting the scale-free properties of real networks and generating mobility traces with density characteristics similar to what we measure in real mobility traces are also the focus of our on-going and future research.

Fig. 1

 1 Fig. 1 Node spatial density distribution at different trace collection times for mobility in a city park.

Fig. 2 Fig. 3

 23 Fig.2Initial and final spatial node density distribution for the Quinta trace, and the respective steady-state density distribution using the proposed ODE framework.

Fig. 4

 4 Fig.4Initial and final spatial node density distribution for the Quinta trace, and the respective steady-state density distribution using the proposed ODE framework.

Fig. 5

 5 Fig.5Initial spatial node density distribution for the Quinta trace, simulated final density distribution using the RWP mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the RWP mobility regime.

Fig. 9

 9 Fig.9Initial spatial node density distribution for the Statefair trace, simulated final density distribution using the RWP mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the RWP mobility regime.

Fig. 10

 10 Fig.10Initial spatial node density distribution for the Statefair trace, simulated final density distribution using the Natural mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the Natural mobility regime.

Table 1

 1 Summary of the GPS traces studied.

	Trace	# users	Duration Samples
	Quinta [3]	97	900s	1s
	KAIST [30]	78	5000s	10s
	Statefair [30]	19	8000s	10s

Table 2

 2 Simulation parameters.

	Parameter	Quinta	KAIST	Statefair
	Avg. Speed (±σ)(m/s)	1.2(±0.53)	0.72(±0.68)	0.48(±0.39)
	Avg. Pause (sec)	3.6	86	72
	Area (meters x meters)	840x840	5000x5000	1260x1260
	Duration (sec)	900	5000	8000
	# nodes	97	78	19

  Initial spatial node density distribution for the KAIST trace, simulated final density distribution using the RWP mobility regime and the respective steady-state density distribution using the proposed ODE framework applied to the RWP mobility regime.

	≥ k									KAIST Initial
	% of cells with node density	0 0 0.05 0.1 0.15	1	2	3	4	5	6	7	8 ODE Framework 9 RWP Sim	10
						Number k of nodes in a cell
	≥ k Fig. 7 0 0 0.05 0.1 0.15 % of cells with node density	1	2	3	4	5	6	7	KAIST Initial 8 9 ODE Framework Natural Sim	10
						Number k of nodes in a cell

The use of the term "homogeneous node distribution" refers here to the fact that there is no significant concentration of nodes (clusters), and should not be mistaken with uniform distribution normally used to model the choice of next destination, speed and pause time in random mobility models.

A 90% confidence level was computed. The confidence interval was too small to be seen in this scale and was omitted for clarity of the plot.

Acknowledgements This work has been partially supported by NSF through grant CCF 0916941 and by CAPES, Ministry of Education of Brazil, Caixa Postal 250, Brasilia -DF 70040-020 Brazil.