# Protocol Testing and Performance Evaluation for MANETs with Non-uniform Node Density Distribution

Akihito Hiromori, Takaaki Umedu, Hirozumi Yamaguchi, Teruo Higashino

► To cite this version:

Akihito Hiromori, Takaaki Umedu, Hirozumi Yamaguchi, Teruo Higashino. Protocol Testing and Performance Evaluation for MANETs with Non-uniform Node Density Distribution. 24th International Conference on Testing Software and Systems (ICTSS), Nov 2012, Aalborg, Denmark. pp.231-246, 10.1007/978-3-642-34691-0_17. hal-01482405

HAL Id: hal-01482405

https://inria.hal.science/hal-01482405

Submitted on 3 Mar 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Protocol Testing and Performance Evaluation
## for MANETs with Non-uniform
## Node Density Distribution

Akihito Hiromori, Takaaki Umedu, Hirozumi Yamaguchi, and Teruo Higashino

Graduate School of Information Science and Technology, Osaka University
Yamadaoka 1-5, Suita, Osaka 565-0871, Japan
{hiromori, umedu, h-yamagu, higashino}@ist.osaka-u.ac.jp
http://www-higashi.ist.osaka-u.ac.jp/

**Abstract.** In this paper, we focus on Mobile Ad-hoc Networks (MANETs) with non-uniform node density distribution such as Vehicular Ad-hoc Networks (VANETs) and Delay Tolerant Networks (DTNs), and propose a technique for protocol testing and performance evaluation. In such MANETs, node density varies depending on locations and time, and it dynamically changes every moment. In the proposed method, we designate node density distributions and their dynamic variations in a target area. Then, we construct a graph called *TestEnvGraph* where all node density distributions are treated as its nodes and they are connected by edges whose weights denote differences of two node density distributions. We specify a set of edges to be tested in the graph, formulate a problem for efficiently reproducing all the given node density distributions and their dynamic variations as a rural postman problem, find its solution and use it as the order of reproduction of designated node density distributions and their variations. Protocol testing is carried out by reproducing node density distributions in the derived order. We have designed and developed a method and its tool for mobility generation on MANETs, which can reproduce any designated node density distribution and its dynamic variations in a target area. From our experiments for a VANET protocol, we have shown that our method can give a similar trend in network throughput and packet loss rates compared with realistic trace based protocol testing.

**Keywords:** Protocol testing, Performance evaluation, MANET, Mobility, VANET, DTN, Rural postman problem

# 1 Introduction

With the advance of mobile wireless communication technology, recently several types of mobile wireless communication systems have been designed and developed. Smart phones and car navigation systems can be used for communicating neighboring people and vehicles, respectively. Mobile Ad-hoc Network (MANET) applications such as Vehicular Networks (VANETs) and Delay Tolerant Networks (DTNs) are becoming popular. VANET is the most promising
MANET applications. Also, several DTN systems using smart phones and car navigation systems have been proposed as emergency communication means in disaster situations. Those systems can be used as social systems and they require high reliability and sustainability. In general, sensor networks are stable and they are often used in areas with uniform node density distributions. However, unlike stable sensor networks, VANET and DTN applications are used under non-uniform node density distributions. Node density varies depending on locations and time, and it dynamically changes every moment. It is well-known that node mobility and density affect reliability and performance of MANET applications [2, 18]. In order to improve reliability and performance of MANET applications, it is important to reproduce several types of node density distributions efficiently and carry out their testing in simulation using network simulators and/or emu-lation using real mobile devices (e.g. mobile robots).

In this paper, we propose a protocol testing method for such MANET protocols and applications. In the proposed method, first we designate a set of node density distributions and their dynamic variations for a target area for which we want to carry out protocol testing and performance evaluation. For example, in VANET applications, node densities near intersections might become high when their signals are red while they might become low when the signals become green. Here, we assume that protocol designers can designate such node density distributions and their variations for a target area through simulation and real trace data. Then, we construct a graph called *TestEnvGraph* where all node density distributions are treated as its nodes and they are connected by edges whose weights denote differences of two node density distributions. The graph *TestEnvGraph* represents a testing environment and its dynamic change of node density distributions to be tested. As shown in [2], it is known that it takes time to reproduce MANET with designated mobility and make it stable. Thus, it is desirable that we can reproduce all the designated node density distributions and their variations with a small cost. In this paper we formulate a problem for efficiently reproducing all the designated density distributions and their variations as a rural postman problem [12] of the graph *TestEnvGraph*, find its solution using a heuristic algorithm and use it as an efficient order to reproduce all the designated node density distributions and their variations.

On the other hand, in [20], we have proposed a method for generating a waypoint mobility model with designated node density distributions for a target area. In this paper, we slightly extend its method and use it to reproduce designated node density distributions and their dynamic variations mechanically. Fig. 1 denotes an example of a designated node density distribution and its mobility patterns. The dark gray cells in Fig. 1 (a) denote high node density while the light gray cells denote low node density. Fig. 1 (b) denotes example mobility patterns. Using a rural postman tour for the graph *TestEnvGraph*, we reproduce a testing environment which can treat any designated node density distributions and their dynamic variations with a small cost.

In order to show effectiveness of the proposed method, we have compared network throughput and packet loss rates of VANET applications in our approach
<figure><img src="image_2.png" /></figure>

**Fig. 1.** Example of node density distribution and its mobility patterns with those obtained in real trace based (microscopic mobility based) approaches. In ITS research communities, it is known that vehicular densities strongly affect the performance of vehicle-to-vehicle (V2V) communication. Therefore, trace based data and microscopic vehicular mobility models are often used. They are useful to reproduce typical traffic patterns. Here, we have generated vehicular mobility patterns using both the proposed method and a microscopic traffic simulator VISSIM [21], and compared their performance. We have generated typical 10 patterns of node density distributions and their dynamic variations near an intersection. Then, we have evaluated the performance of a protocol. The results are shown in Section 6. Our experiments have shown that the performance based on node density distributions and their dynamic variations derived using our proposed method and tool is rather close to that based on real trace based and microscopic vehicular mobility based traffic patterns.

Real traces and those obtained from microscopic traffic simulators can reproduce typical traffic patterns easily. However, it is difficult to reproduce peculiar traffic patterns using such methods. In general, it takes much time and costs to reproduce rare cases. On the other hand, the proposed method can designate any node density distribution and its variations. It can help to improve the performance and reliability of MANET protocols and applications. As far as the authors know, it is the first approach that we can designate any node density distributions and their variations and use them for protocol testing. By finding a rural postman tour for the graph *TestEnvGraph*, we minimize the cost for reproducing the designated node density distributions and their variations.

## 2 Related Work

It has been recognized that node mobility and density affect the performance of mobile wireless networks [15, 23], and many mobility models have been proposed so far [3, 18]. Random-based mobility models such as the Random Waypoint (RWP) model and the Random Direction (RD) model are often used, and some analytical researches have revealed their properties [5, 14]. The results have shown that the node density distribution is not uniform; e.g. there is a high-density peak at the central point of the target area. There are several works for protocol testing of MANET. For example, Ref. [22] proposed a game theory based approach for formalizing testing of MANET routing protocols. Ref. [8] proposed a method for conformance testing and applied it to Dynamic Source Routing (DSR). For details, see a survey of Ref. [4].
On the other hand, if we want to design MANET applications for pedestrians with smart phones and/or running vehicles in urban districts, we need more realistic mobility. For example, in VANET application areas, Refs. [7] and [16] proposed adaptive protocols for efficient data dissemination from vehicles by considering neighboring vehicular density so that we can avoid the so-called broadcast storm problem. In [1], the authors proposed a method for estimation of vehicular density. Ref. [17] argued the need for combining a specific road traffic generator and a wireless network simulator. They need to be coupled bidirectionally when a target VANET protocol may influence the behavior of vehicles on streets. Recently, several microscopic vehicular mobilities are proposed as the means for reproducing realistic vehicular mobility [6, 13, 19, 21]. A traffic simulator VISSIM [21] adopts a microscopic vehicular mobility. Ref. [19] also proposed a microscopic vehicular mobility which can reproduce a vehicular mobility close to real traffic traces obtained from aerial photographs of Google Earth.

MANET applications for pedestrians with smart phones have similar analysis. In [9], we have shown that there are large variations for performance and packet loss rates of multi-hop communications depending on node density distributions. In DTNs, it is known that node mobility and density strongly affect the reliability and performance of DTN applications (e.g. see [23]). Especially, if there are no rely nodes, in many DTN protocols, intermediate nodes store their received data and forward them to their preceding nodes when they are found. In order to show that proposed store-and-forward mechanisms can work well, we need to check sustainability for several types of node density distributions.

All the above research works show that reproduction of node mobility and density distributions is very important. However, there are very few works about testing of MANET protocols, which consider non-uniform node density distributions and their dynamic variations. This paper is motivated to give a solution for protocol testing on such a MANET.

## 3 MANETs with Non-uniform Node Density Distribution

In general, dissemination intervals of many VANET protocols are autonomously adjusted depending on observed node density so that we can reduce the probability of packet collisions. Many of DTN protocols have store-and-forward mechanisms so that packets can reach to their destinations even if node density for a part on their routes is very low for some period. Performance of such MANET applications cannot be evaluated by general random based mobility.

In Fig.2, we show node density distributions and average speeds of moving vehicles near an intersection where we divide a target road segment between intersections into three cells of 200 meters and show their node densities with three categories: "0(low)" (white cells), "1(middle)" (gray cells) and "2(high)" (black cells). In this figure, on the horizontal road, the densities of two cells close to the intersection are "high" and the other cells are very low, while the densities of the vertical road are "middle" or "low". It is a typical situation where
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Node density and average speed at an intersection in typical conditions</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** Typical dynamic change of vehicular density distributions near an intersection</figcaption></figure>

vehicles on the horizontal road are stopping at the signal before the intersection and those on the vertical road run freely.

We have generated one hour's traffic trace data of 1 km² square area with 5×5 checked roads using the microscopic traffic simulator VISSIM [21], and analyzed their node density distributions (note that we have removed first 20 minutes' trace data in simulation since the simulated traffic has not been stable at first). In the analysis, we have made a density map like Fig. 2 at each intersection for every unit time period where the unit time period is 60 sec. Here, totally 1025 patterns of node density distributions are derived. In Fig. 3, we have shown typical 10 traffic patterns and their dynamic change representing a loop where an ID number is given for each pattern. We have classified the obtained patterns by density distribution patterns for horizontal roads, and found that the most emergent top 14 patterns can cover about 25% of traffic situations.

Fig. 4 denotes the transitions among the top 14 typical patterns. When we execute typical VANET based dissemination protocols and multi-hop communications among running vehicles, the typical variations of their node density distributions correspond to transitions (sequences of edges) whose lengths are three or four in Fig. 4. Thus, by reproducing all such transitions in Fig. 4 and carrying out protocol testing for their transitions, we can check their reliability.
<figure><img src="image_5.png" /><figcaption>Fig. 4. Transitions among top 14 typical states</figcaption></figure>

For example, in [16] we have proposed a dissemination protocol for propa-
gating preceding traffic information. This protocol can gather real-time traffic
information of 2-3 km ahead within 3 minutes with 60-80 % probability. Most of
such preceding traffic information is sent from neighboring vehicles within a few
hundred meters. Suppose that Fig. 4 shows variations of node density distribu-
tions for such a road section and that each edge corresponds to an one minute's
variation of node density distributions. Then, each sequence of three edges from
a state corresponds to dynamic change of node density distributions in the tar-
get road section for 3 minutes. Thus, by collecting all sequences of three edges
from all states and by testing their performance, packet loss rates and buffer
length, we can evaluate performance characteristic and reliability of the proto-
col. When we count the number of all sequences of three transitions from states
corresponding to typical node density distributions, it becomes rather large. In
Section 5, we will propose an efficient testing method.

We will give another example. In [10], we have proposed a protocol for realis-
tic mobility aware information gathering in disaster areas where we combine the
notion of store-and-forward mechanisms in DTNs and geographical routing on
MANETs. In the proposed protocol, if intermediate nodes cannot relay safety in-
formation to its home cells by multi-hop communication, they hold it until they
meet preceding nodes and re-transmit it as proxies. If shortest paths to home
cells are not available, detours are autonomously found. However, in [10], we
have only evaluated performance of DTN protocols for fixed disaster situations
such as Fig. 5 (b) and (c) where the white cells and gray cells represent movable
areas and obstacle areas, respectively. On the other hand, in an early stage in
disaster, obstacle cells might be small like Fig. 5 (a), and they might become
large like Fig. 5 (b) after time passes. It is desirable that we can reproduce such
dynamic extension of obstacle cells (e.g. change from Fig. 5 (a) to Fig. 5 (b)),
and carry out testing for a target DTN protocol.

As we have discussed above, it is desirable that

(a) MANETs with designated node density distributions can be mechanically generated,
<figure><img src="image_6.png" /><figcaption>Fig. 5. Expansion of obstacle cells in disaster</figcaption></figure>

(b) dynamic variations (change) of node density distributions for a given MANET can be mechanically generated, and that

(c) if multiple dynamic variations (change) of node density distributions need to be tested, the total time necessary for testing should be minimized.

In the following sections, we will propose a testing method for considering those conditions.

4 Mobility Generation with Designated Node Density Distribution

In [20], we have proposed a method for generating a waypoint mobility model with designated node density distributions for a target area where each node repeats the process of (i) choosing a destination point in the target area, (ii) moving straightly toward the destination point with a constant velocity, and (iii) staying at the point for a certain time period. The goal of this work is to synthesize mobility patterns that can capture real (or intentional) node density distributions. Fig. 6 denotes typical node density distributions where dark and thin gray colors denote high and low node densities, respectively. A target area is divided into several subregions called *cells* and we can designate a favorite node density to each cell. In order to automatically generate natural mobility patterns realizing designated node density distributions, the method determines probabilities of choosing waypoints from those cells, satisfying given node density distributions. Fig. 7 denotes example mobility traces for the four types of node density distributions. The problem is formulated as an optimization problem of minimizing errors from designated node density distributions, and probabilities of choosing waypoints at each cell are determined. Since the problem has non-linear constraints, a heuristic algorithm generates near-optimal solutions.

Here, we extend the method in [20] so that we can treat variations of node
density distributions. First, we give an outline of the method about how to
determine the probabilities of choosing waypoints from each cell, satisfying given
node density distributions. Assume that the target area is divided into m × n
square cells and these cells are numbered sequentially from top left (0) to bottom
right (m·n−1) like Fig. 8 (a). Suppose that each node in cell *i* selects a destination
cell (say *j*) with probability *p*ᵢ,ⱼ called *destination probability*. These probabilities
<figure><img src="image_7.png" /><figcaption>Fig. 6. Snapshots for four types of node density distributions</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7. Example traces for four types of node density distributions</figcaption></figure>

need to satisfy the following equation.

$$ \sum_{j=0}^{m \cdot n - 1} p_{i,j} = 1 \quad (0 \le i \le m \cdot n - 1) \qquad (1) $$

<figure><img src="image_9.png" /><figcaption>Fig. 8. Calculation of node transition probabilities</figcaption></figure>

In a steady state, the number of nodes moving from an origin cell to a destination cell per unit time is constant. We call it as a *flow rate* and denote it as $f_j$. The flow rate $f_j$ must satisfy the following equation.

$$ f_j = \sum_{i=0}^{m \cdot n - 1} f_i \cdot p_{i,j} \quad (0 \le j \le m \cdot n - 1) \qquad (2) $$

Next, we define *cell transit time* representing time necessary for traveling from cell *i* to cell *j* and *cell transit number* representing the number of nodes
moving through a cell (say, cell $k$). As shown in Fig. 8 (b), we denote an origin point in cell $i$ and a destination point in cell $j$ as $(x_i, y_i)$ and $(x_j, y_j)$, respectively. The average transit distance (denoted by $L_{i,j}$) between these two points is represented as $\sqrt{(x_j - x_i)^2 + (y_j - y_i)^2}$. Similarly, the transit distance on cell $k$ (denoted $L_{i,j,k}^{pass}$) for nodes traveling from cell $i$ to cell $j$ is shown in Fig. 8 (b). Here, $(x_{k1}, y_{k1})$ and $(x_{k2}, y_{k2})$ denote the intersection points of the line segment between $(x_i, y_i)$ and $(x_j, y_j)$ on the two sides of cell $k$. Assume that all the nodes move at the same speed (denoted as $V$) and that they stop for the same pause time $T^{pause}$ after arriving at their destination cells. Hereafter, $T_{i,j,k}^{pass}$ denotes the average cell transit time on cell $k$ for nodes moving from cell $i$ to cell $j$. $T_{i,j,k}^{pass}$ is represented by the following equation. Note that the value of $T_{i,j,k}^{pass}$ is zero if cell $k$ has no intersection with the line segment (i.e. $L_{i,j,k}^{pass} = 0$).

$$T_{i,j,k}^{pass} = \begin{cases} \frac{L_{i,j,k}^{pass}}{V} & (j \neq k) \\ \frac{L_{i,j,k}^{pass}}{V} + T^{pause} & (j = k) \end{cases} \qquad (3)$$

Hereafter, we show how to calculate the cell transit number by destination probabilities. The number of nodes moving from cell $i$ to cell $j$ per unit time can be represented as $f_i \cdot p_{i,j}$. The transit time for these nodes can be represented as $T_{i,j,k}^{pass}$. Thus the number of nodes passing cell $k$ in the nodes moving from cell $i$ to cell $j$ is calculated as $f_i \cdot p_{i,j} \cdot T_{i,j,k}^{pass}$ (see Fig. 8 (c)). Since nodes might pass through cell $k$ for different combinations of origin-destination cells, the total number of nodes at cell $k$ (cell transit number $d_k$) can be represented as follows.

$$d_k = \sum_{i=0}^{m \cdot n - 1} \sum_{j=0}^{m \cdot n - 1} f_i \cdot p_{i,j} \cdot T_{i,j,k}^{pass} \qquad (4)$$

Here, in order to treat the cell transit number for cell $k$ as the node density for cell $k$, we assume that the number of all nodes is 1 as shown in Eq.(5). By applying $f_i$ to Eq.(4), we can get the node density distribution obtained by $p_{i,j}$.

$$\sum_{k=0}^{m \cdot n - 1} d_k = 1 \qquad (5)$$

Since the problem described above has non-linear constraints, we give a heuristic algorithm to derive a solution. A trivial solution satisfying the above constraints is that all nodes move only in the first assigned cells. In [20], we give a proof to show that for any node density distribution, we can generate the corresponding non-trivial waypoint mobility satisfying designated node density distributions like Fig. 7. For details about how to solve the problem with the above non-linear constraints, see [20].

In order to treat dynamic change of node density distributions, we give the following constraint when a new (next) node density distribution is generated from the current one. Let $p_{i,j}$ and $p_{i,j}$ denote the destination probabilities from cell $i$ to cell $j$ at the current and next time slots, respectively. And, let $Diff$
denote the sum of the differences of destination probabilities at the current and next time slots for all cells. If we can minimize the value of *Diff*, the next node mobility can be generated relatively easily from the current node mobility. Then, when we find a solution satisfying the above constraints, we give the following objective function *Diff* and find a solution minimizing the value of *Diff*. From our experiences, if the value of the objective function *Diff* is small, time necessary to generate a steady next node density distribution becomes small. Thus, in this paper, from the obtained value of *Diff*, we will generate the next node density distribution by generating slightly different intermediate node density distributions sequentially from the current node density distribution. By using this method, we generate any dynamic variation of node density distributions.

$$Diff = \sum_{i=0}^{m \cdot n - 1} \sum_{j=0}^{m \cdot n - 1} \{p_{i,j} - \hat{p}_{i,j}\} \quad (6)$$

In Table 1, designated node density distributions and measured density distributions for the two mobilities are shown in the left side table and right side table, respectively. Although the derived mobility cannot reflect designated node density distributions perfectly, their errors are mostly within 0.1 % (there exist relatively larger errors for reproduction of empty node density distributions).

<table><caption>**Table 1.** Designated (left) and measured (right) density distributions (%)</caption><tbody><tr><td>3.00</td><td>4.00</td><td>3.00</td><td>4.00</td><td>3.00</td><td>3.01</td><td>3.92</td><td>2.94</td><td>4.00</td><td>3.00</td></tr><tr><td>4.00</td><td>6.00</td><td>4.00</td><td>6.00</td><td>4.00</td><td>4.14</td><td>6.04</td><td>4.07</td><td>6.07</td><td>4.03</td></tr><tr><td>3.00</td><td>4.00</td><td>3.00</td><td>4.00</td><td>3.00</td><td>2.98</td><td>3.99</td><td>3.94</td><td>4.01</td><td>2.92</td></tr><tr><td>4.00</td><td>6.00</td><td>4.00</td><td>6.00</td><td>4.00</td><td>3.94</td><td>5.99</td><td>4.02</td><td>6.01</td><td>3.91</td></tr><tr><td>3.00</td><td>4.00</td><td>3.00</td><td>4.00</td><td>3.00</td><td>3.01</td><td>3.99</td><td>3.01</td><td>4.00</td><td>3.00</td></tr><tr><td colspan="10" style="text-align: left;">(a) Checkerboard</td></tr><tr><td>4.00</td><td>4.50</td><td>5.00</td><td>4.50</td><td>4.00</td><td>3.95</td><td>4.41</td><td>4.96</td><td>4.41</td><td>3.95</td></tr><tr><td>4.50</td><td>0.00</td><td>5.50</td><td>0.00</td><td>4.50</td><td>4.39</td><td>0.41</td><td>5.34</td><td>0.41</td><td>4.39</td></tr><tr><td>5.00</td><td>5.50</td><td>6.00</td><td>5.50</td><td>5.00</td><td>5.00</td><td>5.43</td><td>5.92</td><td>5.43</td><td>5.00</td></tr><tr><td>4.50</td><td>0.00</td><td>5.50</td><td>0.00</td><td>4.50</td><td>4.39</td><td>0.41</td><td>5.34</td><td>0.41</td><td>4.39</td></tr><tr><td>4.00</td><td>4.50</td><td>5.00</td><td>4.50</td><td>4.00</td><td>3.95</td><td>4.41</td><td>4.96</td><td>4.41</td><td>3.95</td></tr><tr><td colspan="10" style="text-align: left;">(b) Manhattan1</td></tr></tbody></table>

# 5 Efficient Protocol Testing

In general, protocol testing is classified into two categories: simulation based testing and real machine based testing. Real machine based testing is not realistic for VANET applications. In such a case, using wireless network simulators and reproducing several node density distributions is one possibility. As far as the authors know, most of wireless network simulators can only reproduce random
based and trace based mobility. On the other hand, our method can reproduce
node density distributions corresponding to several types of vehicular mobility
patterns and carry out the simulation based testing. The proposed method can
be also used for real machine based testing. For example, if multiple mobile
robots can follow the mobility patterns generated by the method described in the
previous section, movement of such robots satisfies the designated node density
distribution.

Here, we construct a graph TestEnvGraph for representing the testing envi-
ronment in a target area. Let T<sub>patterns</sub> denote such typical dynamic transition
patterns of node density distributions. For example, suppose that the node den-
sity distributions of three cells vary from “201” to “211” and “222” in turn where
“0”, “1” and “2” denote low, middle and high node densities, respectively. We
want to carry out testing for variations of those node density distributions in this
order. In such a case, we give a transition pattern ID “p<sub>h</sub>” to this transition pat-
tern “201 → 211 → 222” and make their pair < p<sub>h</sub>, “201 → 211 → 222” >. We
call this pair as the transition pattern with ID “p<sub>h</sub>”. Here, we assume that the set
T<sub>patterns</sub> of transition patterns includes all the set of node density distributions
and their variations for which we want to carry out testing.

Then, we construct the following graph $G = (V, E)$ where $V$ denotes the set of all transition patterns with IDs where the node $<p_h, n_i>$ ($1 \le i \le k$) belongs to $V$ if and only if a transition pattern $<p_h, \{n_1 \to n_2 \to, \dots, \to n_k\}$ is included in $T_{\text{patterns}}$, and the edge $<p_h, n_i> \to <p_h, n_{i+1}>$ ($1 \le i \le k-1$) belongs to $E$ if and only if $<p_h, \{n_1 \to n_2 \to, \dots, \to n_k\}$ is included in $T_{\text{patterns}}$. Here, we define the difference of node density distributions. For the transition pattern “201 → 211 → 222”, we define that the difference of node density distributions between “201” to “211” is “1” since only low node density “0” of the second cell is changed to middle “1”. On the other hand, the difference of node density distributions between “211” to “222” is “2” since the node densities of the second and third cells are changed from “1” to “2”, and the sum of their differences is “2”. We treat such a difference as the weight of the corresponding edge in $E$. Since only target transition patterns are represented as the graph $G = (V, E)$, $G = (V, E)$ is not always totally connected in general. Thus, we construct the graphs $G' = (V + V', E + E')$ and $G'' = (V + V' + V'', E + E' + E'')$ as follows.

For the graph $G' = (V + V', E + E')$, let $V'$ denote the set of nodes where
$<*,n_1>$ and $<*,n_k>$ belong to $V'$ if $<p_h, \{n_1 \to n_2 \to, \dots, \to n_k\}$ is
included in $T_{\text{patterns}}$, and $<*,n_1> \to <p_h, n_1>$ and $<p_h,n_k> \to <*,n_k>$
belong to $E'$ if $<p_h, \{n_1 \to n_2 \to, \dots, \to n_k\}$ is included in $T_{\text{patterns}}$. Here, we
treat the weights for edges in $E'$ as zero. Then, we construct the graph $G'' =
(V+V'+V'', E+E'+E'')$ as follows, and treat it as the graph TestEnvGraph for
representing the testing environment. For each pair of $<*,n_i>$ and $<*,n_j>$
whose difference of node density distributions is $d$, if there does not exist a
path from $<*,n_i>$ to $<*,n_j>$ whose total sum of edges' weights is $d$ in
$G' = (V+V', E+E')$, we add $<*,n_{i1}>, \dots, <*,n_{i_{d-1}}>$ to the set of nodes
$V''$, and add (i) edge $<*,n_i> \to <*,n_{i_1}>$, (ii) $<*,n_{i_p} > \to <*,n_{i_{p+1}}>$
($1 \le p \le d-2$), and (iii) $<*,n_{i_{d-1}} > \to <*,n_j>$ to the set of edges $E''$ where
<figure><img src="image_10.png" /><figcaption>Fig. 9. Example TestEnvGraph</figcaption></figure>

(i) the difference of node density distributions $<*, n_i>$ and $<*, n_{i_1}>$, (ii) that of $<*, i_p>$ and $<*, n_{i_{p+1}}>$ ($1 \le p \le d-2$), and (iii) that of $<*, n_{i_{d-1}}>$ and $<*, n_j>$ are one. We treat the graph $G'' = (V + V' + V'', E + E' + E'')$ as the graph TestEnvGraph. Note that there might be several choices for $<*, n_{i_p}>	o<*, n_{i_{p+1}}>$ ($1 \le p \le d-2$). Here, any choice is acceptable as TestEnvGraph.

Fig. 9 denotes an example TestEnvGraph. Here, we assume $T_{patterns} = \{<p_1, "222 \to 221">, <p_2, "111 \to 121">, <p_3, "221 \to 111">\}$. In this example, there are three cells. The node density distribution "221" denotes that node density of the first two cells is "2" (high) and that of the third cell is "1" (middle). In $T_{patterns}$, three variations of node density distributions are required as those to be tested. The variation $<"222 \to 221">$ requires that the node density distribution is changed from "222" to "221". In Fig. 9, at first we construct the graph $G = (V, E)$. The nodes and edges with thick lines denote $V$ and $E$, respectively. The value of each edge denotes its weight (the difference of node density distributions). The nodes and edges with fine lines denote those belonging to $V' + V''$ and $E' + E'''$ of TestEnvGraph = $(V + V' + V'', E + E' + E''')$, respectively.

[Property of TestEnvGraph]

The graph TestEnvGraph holds the following properties.

(a) For each pair of $<*, n_i>$ and $<*, n_j>$ in TestEnvGraph = $(V + V' + V'', E + E' + E'')$ whose difference of node density distributions is $d$, there exists a path from $<*, n_i>$ to $<*, n_j>$ (also a path from $<*, n_j>$ to $<*, n_i>$) whose total sum of edges' weights is $d$ in TestEnvGraph.

(b) If we carry out testing for all edges in $E$, then we can conclude that all the transition patterns representing the designated node density distributions and their variations in $T_{patterns}$ are tested.

[Rural Postman Problem (RPP)]
For a given directed graph $G = (V, E)$ and a subset $E' \subseteq E$ of edges (here, we call $E'$ as the set of target edges to be traversed), Rural Postman Problem (RPP) is a problem to find the cheapest Hamiltonian cycle containing each of edges in the set $E'$ of target edges to be traversed (and possibly others in $E$). The problem is shown to be NP-complete [12]. We call a cheapest Hamiltonian cycle as a rural postman tour for the graph.

Note that there are several heuristic algorithms for efficiently solving Rural Postman Problem (RPP) although such heuristic algorithms might not be able to find its optimal solution [12].

### [Assumptions for protocol testing]

(a) We can generate a waypoint-based mobility model with any designated node density distribution using the method described in the previous section.

(b) It requires some cost (time) for generating the waypoint-based mobility model with a designated node density distribution.

(c) In order for changing a given node density distribution to another one whose difference of node density distributions is $d$, it requires some cost (time) in proportion to $d$.

### [Problem to find the most efficient testing order for TestEnvGraph]

For a given *TestEnvGraph* = (*V* + *V'* + *V*", *E* + *E'* + *E*") where *E* denotes the set of all the transition patterns of node density distributions and their variations belonging to *T*<sub>patterns</sub>, if the above assumptions hold, then the problem to find the most efficient testing order for *TestEnvGraph* is formulated as a problem to find a rural postman tour for *TestEnvGraph* where *E* is treated as the set of target edges to be traversed.

In order for solving Rural Postman Problem (RPP), we have used a SA-based heuristic algorithm and found an efficient testing order for *TestEnvGraph*.

For *TestEnvGraph* shown in Fig. 9, suppose that we start testing from node < *, "111" >. Then, the rural postman tour (RPP) < *, "111" > → < p2, "111" > → < p2, "121" > → < *, "121" > → < *, "221" > → < *, "222" > → < p1, "222" > → < p1, "221" > → < *, "221" > → < p3, "221" > → < p3, "111" > → < *, "111" > denotes a shortest tour for this testing and its total weights (the sum of the differences of node density distributions) is 6. If MANET designers generate variations of node density distributions in this order and carry out protocol testing, then they can carry out it with the minimum cost.

### [Problem to find the most efficient testing order]

Let $V = \{n_1, n_2, ..., n_k\}$ denote the set of all designated node density distributions for which we want to carry out testing (and/or performance evaluation). Then, we designate $< p_i, "n_i \to n_i" >$ ($1 \le i \le k$) as $T_{patterns}$. Using the above algorithm, we construct *TestEnvGraph* and find a rural postman tour where $E = \{< p_i, "n_i \to n_i" >| 1 \le i \le k\}$ is treated as the set of target edges to be traversed. This modified rural postman problem (RPP) corresponds to the problem to find the most efficient testing order for carrying out tests of all designated node density distributions.
<table><caption>**Table 2.** The number of packet losses for trace data generated by VISSIM</caption><thead><tr><th>Pattern</th><th>[1]</th><th>[2]</th><th>[3]</th><th>[4]</th><th>[5]</th><th>[6]</th><th>[7]</th><th>[8]</th><th>[9]</th><th>[10]</th><th>[11]</th><th>[12]</th><th>Total</th></tr></thead><tbody><tr><td>293</td><td>0</td><td>0</td><td>0</td><td>3</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>5</td></tr><tr><td>446</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>2</td></tr><tr><td>517</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>4</td></tr><tr><td>246</td><td>1</td><td>1</td><td>0</td><td>2</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>2</td><td>9</td><td>17</td></tr><tr><td>80</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>7</td><td>13</td><td></td></tr><tr><td>369</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>7</td><td>4</td><td>13</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>6</td><td>11</td><td></td></tr><tr><td>71</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td></tr><tr><td>45</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>6</td></tr><tr><td>152</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>3</td><td>3</td><td>10</td></tr></tbody></table>

<table><caption>**Table 3.** The number of packet losses for proposed method</caption><thead><tr><th>Pattern</th><th>[1]</th><th>[2]</th><th>[3]</th><th>[4]</th><th>[5]</th><th>[6]</th><th>[7]</th><th>[8]</th><th>[9]</th><th>[10]</th><th>[11]</th><th>[12]</th><th>Total</th></tr></thead><tbody><tr><td>293</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>6</td></tr><tr><td>446</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td></tr><tr><td>517</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>3</td></tr><tr><td>246</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>1</td><td>0</td><td>0</td><td>0</td><td>1</td><td>3</td><td>8</td><td>15</td></tr><tr><td>80</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>7</td><td>6</td><td>13</td></tr><tr><td>369</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>6</td><td>12</td></tr><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>6</td><td>10</td><td></td></tr><tr><td>71</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>2</td><td>4</td></tr><tr><td>45</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>5</td></tr><tr><td>152</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>3</td><td>3</td><td>9</td></tr></tbody></table>

# 6 Experimental Results and Analysis

Here, we show some experimental results and their analysis using a case study on VANET. Our method described in Section 4 can generate a similar node density distribution for a given traffic trace data. However, its mobility is not the same as that of real trace data. Therefore, we use the microscopic traffic simulator VISSIM and have measured node density distributions from the obtained typical trace data shown in Fig. 3. We have conducted a simulation for a trace composed of these 10 patterns to evaluate multi-hop communications by AODV protocol [11] over the intersection. We have transmitted packets from left to right through the intersection every 1 second. Table 2 shows the number of packet losses at each cell in Fig. 3 for the patterns. Each row $[n]$ denotes the number of packet losses at the cell $[n]$ on the horizontal road in Fig. 2. The routes by AODV protocol were usually constructed over cells on the horizontal road. Since the packets are transmitted from left to right and the vehicles on these cells also moved to the same direction. Thus, there are relatively few packet losses at the upside cells even though their densities are high.

We have also measured the node density distributions at those cells. Based on the obtained measured values, we have reproduced their node density distributions using the method described in Section 4 where "Manhattan1" mobility in
Fig. 6 (c) is used for generating vehicular mobility. Then, we have evaluated the packet loss rates through network simulation. Table 3 shows the packet loss rates for the corresponding 10 patterns in Fig. 3. As shown in the two tables, although the results for Table 2 and Table 3 are not the same, they show that their similarity is rather high. Therefore, our proposed mobility model with designated node density distributions can expect a similar trend in network throughput/reliability that are related to how many packet losses occurred. Note that since the packet losses happen at different timing in the two methods, it might be difficult to reproduce and evaluate time sensitive protocols with our proposed method.

In general, trace based testing can represent realistic situations more accurately. Typical traffic patterns can be obtained easily. However, it is difficult to obtain unusual traffic patterns and it takes much time and costs. In order to improve reliability and sustainability of target protocols like VANET protocols, it is very important to reproduce not only typical traffic patterns but also unusual ones and evaluate the reliability and sustainability for those situations.

# 7 Conclusion

In this paper, we have proposed a method for efficiently carrying out protocol testing for a set of designated node density distributions and their variations. The method formulates the problem for finding the most efficiently testing order as the problem to find a rural postman tour for the graph called *TestEnvGraph*. The experimental results show that our method can easily reproduce node density distributions and their variations for VANET applications and their network throughput and packet loss rates are rather similar with those based on real trace based traffic data.

One of our future work is to collect several types of real trace data and evaluate the effectiveness and applicability of the proposed method.

# References

1. Artimy, M.M., Robertson, W., Phillips W.J.: Assignment of Dynamic Transmission Range Based on Estimation of Vehicle Density. In: Proc. of 2nd ACM Int. Workshop on Vehicular Ad Hoc Networks (VANET 2005), pp.40-48 (2005)

2. Le Boudec, J. Y., Vojnovic, M.: Perfect Simulation and Stationarity of a Class of Mobility Models. In: Proc. of 24th Int. Conf. of the IEEE Computer and Communications Societies (INFOCOM 2005), pp.2743-2754 (2005)

3. Camp, T., Boleng, J., Davies, V.: A Survey of Mobility Models for Ad Hoc Network Research. Wireless Comm. and Mobile Computing, vol.2, no.5, pp.483-502 (2002)

4. Carneiro, A., Maag, S., Zaidi, F.: One Step Forward: Linking Wireless Self-Organizing Network Validation Techniques with Formal Testing Approaches. ACM Computing Surveys, vol.43, no.2 (2011)

5. Chu, T., Nikolaidis, I.: Node Density and Connectivity Properties of the Random Waypoint Model. Computer Communications, vol.27, no.10, pp.914-922 (2004)

6. Halati, A., Lieu, H., Walker, S.: CORSIM-corridor Traffic Simulation Model. Traffic Congestion and Traffic Safety in the 21st Century: Challenges, Innovations, and Opportunities, pp. 570-576 (1997)
7. Khelil, A., Becker, C., Tian, J., Rothermel, K.: An Epidemic Model for Information Diffusion in MANETs. In: Proc. of 5th ACM Int. Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems (MSWiM '02), pp.54-60 (2002)

8. Maag. S., Zaidi. F.: A Step-wise Validation Approach for a Wireless Routing Protocol. Posts, Telecomm. Inform. Tech. J., vol.1, pp.34-40 (2007)

9. Maeda, K., Uchiyama, A., Umedu, T., Yamaguchi, H., Yasumoto, K., Higashino, T.: Urban Pedestrian Mobility for Mobile Wireless Network Simulation. Ad Hoc Networks, vol.7, no.1, pp.153-170 (2009)

10. Nakamura, M., Urabe, H., Uchiyama, A., Umedu T., Higashino, T.: Realistic Mobility Aware Information Gathering in Disaster Areas. In: Proc. of IEEE Wireless Communications and Networking Conf. 2008 (WCNC 2008), pp.3267-3272 (2008)

11. Perkins, C.E., Royer, E., Das, S.: Ad Hoc On-demand Distance Vector (AODV), Request for Comments 3561 (2003)

12. Pearn, W. L., Wu, T. C.: Algorithms for the Rural Postman Problem. Computers & Operations Research, vol.22, no.8, pp.819-828 (1995)

13. Quadstone Paramics: Paramics, available: http://www.paramics-online.com/.

14. Rojas, A., Branch, P., Armitage, G.: Experimental Validation of the Random Waypoint Mobility Model through a Real World Mobility Trace for Large Geographical Areas. In: Proc. of ACM/IEEE Int. Symp. on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM???05), pp.174-177 (2005)

15. Royer, E.M., Melliar-Smith, P.M., Moser, L.E.: An Analysis of the Optimum Node Density for Ad Hoc Mobile Networks. In: Proc. of IEEE Int. Conf. on Communications (ICC 2001), pp.857-861 (2001)

16. Saito, M., Tsukamoto, J. Umedu, T., Higashino, T.: Design and Evaluation of Inter-Vehicle Dissemination Protocol for Propagation of Preceding Traffic Information. IEEE Trans. on Intelligent Transportation Systems, vol.8, no.3, pp.379-390 (2007)

17. Sommer, C., Dressler, F.: Progressing Towards Realistic Mobility Models in VANET Simulations. IEEE Comm. Magazine, vol.46, no.11, pp.132-137 (2008)

18. Tracy, T., Jeff, B., Vanessa, D.: A Survey of Mobility Models for Ad Hoc Network Research. Wireless Comm. & Mobile Computing (WCMC), vol.2, no.5 (2002)

19. Umedu, T., Isu, K., Higashino, T., Toh, C. K.: An Inter-vehicular Communication Protocol for Distributed Detection of Dangerous Vehicles. IEEE Trans. on Vehicular Technology, vol.59, no.2, pp.627-637 (2010)

20. Ueno, E., Hiromori, A., Yamaguchi, H., Higashino, T.: A Simple Mobility Model Realizing Designated Node Distributions and Natural Node Movement. In: Proc. of 8th IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (MASS 2011), pp.302-311 (2011)

21. PTV: VISSIM, available: http://www.ptv-vision.com/

22. Zakkuidin. I., Hawkins. T., Moffat. N.: Towards a Game Theoretic Understanding of Ad Hoc Routing. Electron. Notes Theoretical Computer Sciences, vol.119, no.1, pp.67-92 (2005)

23. Zhang, X., Kurose, J., Levine, B.N., Towsley, D., Zhang, H.: Study of a Bus-based Disruption-Tolerant Network: Mobility Modeling and Impact on Routing. In: Proc. of ACM Int. Conf. on Mobile Computing and Networking (MobiCom 2007), pp.195-206 (2007)