Tools for evaluation of social relations in mobility models

In MANET-DTN networks environment is common that mobility of nodes causes disconnection of the network into disconnected islands of the nodes. In order to simulate the real movement of nodes and network disconnections, it is appropriate to use mobility model that uses human mobility patterns. Routing protocols and forwarding techniques of MANET-DTN needs to handle those situations. The main problem is the selection of reliable and secure nodes that are responsible for transportation of messages between isolated islands with limited connectivity [1]. By using real human mobility models, movement and disconnections are not only more realistic but also the selection of the reliable and secure nodes is more effective. Therefore, it is critical to choose proper mobility model. Today there are a lot of social [9] and non-social mobility models that are used to simulate the behaviour of nodes in MANET-DTN networks. In order to choose proper one with social or non-social movement, a good and reliable evaluation tool that evaluates the social aspect of mobility models is needed. Therefore, we propose Tools for Evaluation of Social Relations in Mobility Models (TESRMM) as a new evaluation method that is able to reveal the social aspect of considered mobility model.

Another problem is, that some researchers use many different mobility models with different parameters without analysis of movement. In authors’ simulations with social movement is important to know, how strong relation ties among nodes are, how the nodes behaviour influence functionality of mobile network and how evaluations of mobility model and results of routing protocols interrelate between each other. Successful message transfer through the mobile network and other routing parameters could be misrepresented and misinterpreted without that information. With proposed evaluation method is possible to analyse mobility models based on grouping of nodes into communities and social relationships among communities and nodes in each community. This new evaluation method was created based on existing Louvain method and network parameters. We adapted those algorithms and parameters in an effort to evaluated social behaviour and relation ties among nodes from the movement of mobile nodes. Evaluation method uses the multiplicity of contacts among nodes directly from mobility models.

The innovation of the concept comes from reason, that some authors and researchers using protocol dependent and independent methods such as transmission probability, inter-contacts time, contact duration and more as evaluation methods. Those analytical and probabilistic methods do not directly exhibit the social aspect of mobility models. Our research was focused more on social aspect in order to reveal whether the mobility model is showing signs of sociality. By using adopted methods such as Louvain method for community detection, is possible to analyse grouping of nodes, how strong are relationships among nodes and also if the mobility of nodes is random or based on social or grouping patterns. Parameters of proposed method along with graphical interpretation can provide a better understanding of movement in mobility models and help with the selection of proper mobility model for considered simulations.

The article is organised as follows. Section 2 briefly described the existing evaluation methods. In Sect. 3 we propose TESRMM and Sect. 4 describes the simulation of proposed evaluation method along with other methods. Main results that are analysed and compared with random mobility models such as Random Walk mobility model and Matis model. At the end, we conclude this paper in Sect. 5.

To use evaluation method, output format from mobility model needs to be described. During the simulation of the model, x and y positions are stored for every node. To doing so, simulation time needs to divide into same time slots. Every time slot store positions of every node in simulation area. The output of the model is then the 3-dimensional matrix of positions in every time slot for every node shown in Fig. 1.

It is possible to see, that the first matrix (in front) is the matrix of positions in all time slots of node 1. The same matrix for node 2 is behind the matrix of node 1. Behind this matrices are all other matrices of all other nodes.

From this 3-dimensional matrix is calculated the Meetings matrix by the following mechanism:After step 4, Meetings matrix is created, where values in this matrix represent how many times each node met each other or how long they have been together. For example, node 1 met node 3 500 times in 1000 time slot simulation.

The process of discovering communities is provided by Louvain method [16]. Because Louvain method is the main algorithm of the evaluation method, the description of the method and its parameters are provided. The adaptation of the method is based on the fact that proper input is needed to be used. Usage of the method in order to reveal communities and relationships among nodes from mobility models is possible if Meetings matrix from the previous section is used as input. Meetings matrix is, in fact, a weighted graph. This weighted graph will be used as a social network where nodes are vertices of this graph and edges represents contact among nodes. The edge between nodes will exist if and only if nodes that are taken into consideration met each other at least once. Authors of this method use a modularity quality for communities discovering. Modularity quality measures how well a given partition of a network compartmentalises its communities. The modularity of a partition is a scalar value between − 1 and 1 that measures the density of links inside communities as compared to links between communities. The modularity can be either positive or negative. Positive values indicating that there is some community structure. To look for the best divisions of a network, it is good to have positive, and preferably large, values of the modularity. In the case of weighted graphs it is defined as [16]:where \(A_ij\) represents the weight of the edge between i and j, \(k_i=\sum _{j}A_ij\) is the sum of the weights of the edges attached to vertex i, \(c_i\) is the community to which vertex i is assigned, the \(\delta \)-function \(\delta (c_i, c_j)\) is 1 if \(c_i = c_j\) and 0 otherwise and \(m=\frac{1}{2}\sum _{i,j}A_{i,j}\). The gain in modularity Q is obtained by moving an isolated node i into a community C is computed as:where \(\sum _{in}\) is the sum of the weights of the links inside C, \(\sum _{tot}\) is the sum of the weights of the links incident to nodes in C, \(k_i\) is the sum of the weights of the links incident to node i, \(k_{i,in}\) is the sum of the weights of the links from i to nodes in C and m is the sum of the weights of all the links in the network.

The method algorithm is divided into two phases that are repeated iteratively. The input of the method is the social network as a weighted graph of N nodes. First, every node is assigned to the different community of the network. So, in the initial partition, there are as many communities as nodes. Then, for each node i is considered the neighbours j of i and the gain of modularity is evaluated in case of removing i from its community and by placing it in the community of j. The node i is then placed in the community for which this gain is maximum, but only in the case that this gain is positive. If no positive gain than i stays in its original community. This process is applied repeatedly and sequentially for all nodes until no further improvement can be achieved. Then the first phase is complete. The second phase of the algorithm is based on building a new network, which nodes are now the communities found during the first phase. The weights of the links between the new nodes are given by the sum of the weight of the links between nodes in the corresponding two communities. When the second phase is completed, resulting weighted network is reapply to the first phase for another iteration. These phases are iterated until there are no more changes and a maximum of modularity is attained. The output of the method is a number of communities, the number of nodes in each community and also modularity value. More about this method is in [16].

Mentioned Louvain method for community detection doesn’t directly reflect the social behaviour of nodes in mobility models. For example, the method was previously used on the Twitter social network to explore the problem of partitioning Online Social Networks onto different machines. This method worked with static networks. So we adapt Louvain method for detection of social communities from resulting movement of mobility models in mobile networks, not just static network.

Another parameter that could be used as metric to describe social aspect is the average weighted degree. The weighted degree of a node is like a degree. It’s based on the number of edge for a node but pondered by the weight of each edge. It’s doing the sum of the weight of the edges. In our situation, where we need to observe the whole movement of nodes from Meetings matrix, which is basically weighted graph, the average weighted degree is the better parameter than classic node degree. When Meetings matrix is used, node degree just expresses how many nodes particular node met during simulation, while average node degree express not only how many nodes particular node met, but also how often. The average weighted degree \(wd_i\) for node i is computed by formula 9.where \(w_{i,j}\) (in case of symmetric positive matrix without loops \(w_{i,j} = w_{j,i}\)) is weight between node i and j. \(\prod (i)\) is neighbourhood of node i.

Simulations are oriented on the comparison of our proposed evaluation method with some protocol independent and dependent methods. The main idea of the simulations was to analyze how the mobility models with social and non-social mobility models can affect the network performance and point out differences between them. Simulations were also designed as a comparison of proposed evaluation and other protocol dependent and independent methods.

The first set of simulations is oriented on our proposed evaluation method. Results are focused on number of communities, modularity quality and average weighted degree (see Sect. 4.5). Contacts in Meeting matrix was calculated based on nodes’ movement in Matlab software and processed by external Gephi software [20]. Gephi software provides many analyses of social networks and it also implements Louvain method with modularity quality. Obtained communities from Louvain method is also possible to render and divide by colours.

The second set of simulations is oriented on some of the protocol independent methods for mobility model evaluation. CDF and PDF were chosen for statistical evaluation of nodes’ contact multiplicity.

The third set of simulations is oriented on some of the protocol dependent methods. Average E2E delay, Message delivery ratio, average time of delivery and average number of used nodes were used as evaluation methods. Those methods were performed for four routing protocols Dynamic Source Routing (DSR), Unlimited-Dynamic Source Routing (U-DSR), Social Based Opportunistic Routing (SBOR) and Social Based Opportunistic Routing-social aspect (SBOR-sa).

First set of simulations was running based on variables, which are defined in the Table 1. Simulated area was 1500 \(\times \) 1500 m wide. Simulations were performed with a different number of nodes and radio ranges. The time of simulations was divided into time slots. In order to reveal human mobility patterns, we choose 4 weeks of 28 days. Every day was divided into 48 (half hour) time slots.

A collection of results for second set of simulations was based on variables defined on Table 2. In this setup, we excluded scenario with 300 nodes due to the similarity of results. We also change the number of time slots in order to obtain the higher multiplicity of contact for PDF and CDF.

The third set was running based on variables, which are defined in the Table 3 and it is similar to the first set. The only difference is the higher number of radio ranges because the performance of routing protocols and disconnections in MANET-DTN networks is depended on radio ranges.

Used routing protocols were chosen based on their properties. Since simulations were designed to compare social and non-social random mobility models, DSR and UDSR were chosen because of their independence from social relationships. On the other hand, SBOR with SBOR-sa were chosen because they use social aspect. Used routing protocols are briefly described in the following sections.

We decided to use random models as a comparison with SSBMM. Our SSBMM mobility model as the social model should provide better results than random models in terms of modularity quality and number of communities. In social models, it is expected that the number of communities should grow with the growing number of nodes while in random models should a number of communities remains same or a similar with the growing number of nodes. A growing number of communities is caused by the behaviour of nodes in social models. With the growing number of nodes in social model, new friendships are created so the new groups and communities are also created. In random models, nodes are moving randomly. In an ideal or pure random models, nodes should statistically cover all simulation grid the same by their mobility. In this case, it is expected that the number of communities should be 1 because statistically, every node met each other’s the same time. In real random models, nodes usually move across the same field of simulation grid and sometimes moves from one field of the simulation grid to another. A number of these fields are low so it is expected that the number of discovered communities should be also low and should remain the same with growing numbers of nodes. Only things that change is growing number of nodes in these discovered communities.

Another aspect of assumption is modularity quality. In social based mobility models it is expected that modularity quality should by higher than in random models. This is caused by stronger relationships inside communities than in outside of those communities. In graph theory, the weights of edges inside of communities are higher than in outside of those communities. In random models or ideal random models, it is expected that these weights of edges should be statistically the same inside or outside of communities.

Generally, from the assumption mentioned above, we can expect from mobility models that produced a low and almost constant number of communities with low values of modularity quality that mobility of those models are random. On the other side, models that produce bigger numbers of communities that grow with the growing number of nodes and also produce bigger numbers of modularity quality should be mobility models with a social aspect.

From average weighted degree parameter can be expected, that bigger values should represent more frequent contacts among nodes. In random mobility models, contacts among nodes are distributed almost equally, which mean that the average value of a weighted node degree remains almost same because of small standard deviation value. In social mobility models, some contacts between nodes are more often, which means that it is expected that the average number of weighted degree should be bigger due higher standard deviation value. It means that more often contacts among nodes in social models push average weighted degree into higher value.

The first set of simulation, we to know how many communities is possible to get from the mobility of each used models along with modularity quality and average weighted degree results.

In radio range of 20 m (Fig. 2) is possible to see, that SSBMM has way more communities with 200 and 100 nodes simulation. In the simulation with 50 nodes, the SSBMM has one more community than Matis model and two more than Random Walk mobility model. While SSBMM has significantly growing number of communities with growing numbers of nodes, in random models number of communities grows just slightly. Also, 20 m radio range create the sparse network in simulation area. Therefore, not many nodes are in their radio range, so in the case of SSBMM, much smaller, but stronger communities are created. The number of communities created by random models results from moving across the same field phenomena mentioned in Sect. 4.4.

On Fig. 3 we can see the graphic division of nodes into communities on 20 m radio range by Gephi software.

The SSBMM has thicker edges inside than among communities. This means, that there are stronger relationships among nodes. In the random models, edge thickness inside and among communities is comparable, thus weaker relationships among nodes are created.

The same behaviour was observed for radio range of 50 m (Fig. 4). SSBMM has bigger numbers of communities, while random models have almost same numbers of communities that grow just slightly.

The graphic division of 200 nodes into communities on 50 m radio range by Gephi software is shown on Fig. 5. It is possible to see the same behaviour of nodes than in 20 m radio range.

In radio range of 100 m on Fig. 6 is possible to see, that SSBMM still has bigger numbers of communities, but these numbers are smaller than in radio ranges of 20 and 50 m. This is because of the dense network in radio range of 100 m. Thus, Louvain algorithm must consider more edges among nodes, so fewer but stronger communities are created. On Fig. 7 is depicted the graphic division of 200 nodes into communities on 100 m radio range by Gephi software.

Different behaviour was observed in simulations of 300 m radio range on (Fig. 8). In simulations of 50 and 100 nodes, SSBMM has 2 communities. Those two communities were actually nodes divided by their origin (Dormitory, City settlement from SSBMM model [17]) that is possible to see on Fig. 9h, j, the odd nodes are from Dormitory and even nodes are from City settlement. On radio range of 300 m, the network is very dense, so it is possible to say, that only meetings in origin areas were strong enough to form communities. Therefore, many more edges among nodes than in radio range of 100 m is considered by Louvain algorithm, so the even smaller number of communities were discovered.

On Fig. 10 are depicted a modularity quality results. It is possible to see that modularity quality of SSBMM was always better than in random models. Authors in [21] declared, that nonzero values represent deviations from randomness, and in practice, it is found that a value above about 0.3 is a good indicator of significant community structure in a network. Even in radio range of 300 m, where numbers of communities were lower in the case of SSBMM in very dense network scenario, modularity quality was still better and above 0.3, which proves SSBMM deviation from randomness. We noticed that modularity with increasing radio range decreases. This is caused by increasing the density of the network, where more edges among nodes are considered by Louvain algorithm, so the decision about division nodes into communities is more difficult. In SSBMM simulation scenario of 50 nodes in radio range of 20 m is possible to see the lower value of modularity quality than expected, compared to other simulation scenarios. This is due to the other side of extreme, where 50 nodes in this small radio range are in large simulation area. Such a network is very sparse, so meetings among nodes that form the community are not so often, that means relation ties are weak. It is also possible to see that modularity quality of random models is very low. From our investigation, we observed that movement of one node in Matis model almost cover all simulation area and all grids same times. Some nodes cover just certain parts of simulation area. This problem we mentioned as moving across the same field phenomena (see Sect. 4.4) In this case, a small number of communities were produced by the mobility of Matis model, but because of random movement, small values of modularity quality were produced. Also, authors in [22] observed, that nodes move in the Random Walk mobility model are short, then the movement pattern is a random roaming pattern restricted to a small portion of the simulation area and then node does not roam far from its initial position. From this reason, nodes tend to move in their parts of simulation area, so their mobility almost looks like movement in communities. Therefore, Random Walk mobility model tends to produce the higher value of communities than the pure random model, but also smaller values of modularity quality.

Results of average weighted degree for 50 nodes are depicted on Fig. 11. The SSBMM outperform random models in all radio ranges. The frequency of contacts among some nodes in SSBMM was higher than in random models, which also push average weighted degree values higher. Therefore, it is possible to say, that social ties among nodes cause more often contacts among nodes and this behaviour affects average weighted degree values. The same behaviour is possible to see in Figs. 12 and 13 for 100 and 200 nodes.

Some statistical evaluation of mentioned mobility models was also performed. Probability density function (PDF) and cumulative probability function (CDF) of contacts were used for the second set of simulations among nodes. Contact values from Meetings matrix were used for this evaluation. Longer simulation duration (10,000 time slots) and 200 nodes were used for more accurate result. Multiple simulation runs of each mobility model were performed to obtain multiplicity of meetings of every node in radio ranges from Table 1 except 300 m.

Figure 14 describes probability density of contacts between nodes in the simulation of SSBMM, Matis model and Random Walk mobility model. In this figure is also the table with mean and standard deviation (Std) values. In all radio ranges, the mean value of SSBMM is almost four times higher than mean values of random models. This means, that SSBMM model has way more contacts and longer contacts duration between nodes in simulation duration than random models. The SSBMM also has a much higher value of Std than random models. This means, that SSBMM has the greater dispersion of contacts between nodes. Generally, we can expect, that SSBMM model will have more contacts resulting from longer duration of contacts between nodes with stronger relation ties. From our investigation, we find out, that PDF of contacts of Matis model and Random Walk mobility model closely follow the normal distribution of these contacts which is typical for randomly generated values, while SSBMM does not follow any known distribution.

CDF of contacts for all mentioned models was also evaluated and is shown on Fig. 15. It is possible to see a significant difference between random models and SSBMM. In all radio ranges, SSBMM cover much more contacts than random models. This means that SSBMM produces much more contacts that result from longer contacts time between nodes. It also means that nodes with strong relation ties tend to be together for the longer time than nodes with weak or no relation ties. Therefore, longer times that nodes spend together produce more contacts between them.

Not only statistical evaluation results but also routing evaluation results are performed because of social mobility model verification as the third set of simulations. Described mobility models (Random Walk, Matis model and SSBMM) was used for running four routing methods (DSR, U-DSR, SBOR and SBOR-sa), which are possible to use in MANET environment. Two of them (DSR and U-DSR) was based on standard MANET routing solutions and the next two of them (SBOR and SBOR-sa) was based on social opportunistic routing solutions.

In this paper are described two main simulation results for three mobility models, where was running four mentioned routing protocols.

The first results from the set of results are displayed in Table 4, which represents message delivery ratio among three types of delivery results, Full, Partial and Null. Every message was consist of packets. Results of Full received message means, that all of the sent packets of the message was received. The result, when only some packets of sent message were received, is represented by the result of Partial received message. The third result, which represents types of received message is the Null transfer of message. It means, that zero number of packets was received by the destination node.

DSR couldn’t find some path, when the networks is sparse because the nodes at the start o simulation were divided to two different subnetworks. In the case of the denser network, DSR found some paths, but they maintenance wasn’t possible.

Therefore DSR reached only Null and Partial message transfer.

U-DSR reached better results than DSR for sparse network and for the denser network was U-DSR totally successful.

Opportunistic routing SBOR and SBOR-sa got the best results from all routing protocol, especially for social mobility model SSBMM.

The second main result from routing evaluation results show combined graph for an average time of delivery and an average number of used nodes with Std for an average number of used nodes (Fig. 16). Displayed results are only for successful attempts, three mobility models and four routing protocols. DSR routing protocol newer reached full message transfer in every simulation because the nodes were divided into two separate areas without radio connection and standard DSR routing protocol couldn’t find and maintenance the path between S and D for successful transfer of the message. From this reason, the average time was infinity and number of used nods with Std was zero. This result isn’t graphically represented.

On the other hand, U-DSR routing protocol was more successful than DSR. For the lowest radio range got U-DSR infinity time of delivery, because zero attempts from all simulations were totally successful. With the increasing radio range got the decreasing average time of delivery for successful attempts. By changing of mobility model from Random Walk mobility model through Matis model to SSBMM is possible to see, that the time has to decrease characteristic. An average number of used nodes is almost the same for all mobility models.

SBOR routing protocol reached lower average times of delivery by comparison with U-DSR for every mobility model. This time had the decreasing tendency from Random Walk mobility model through Matis model to SSBMM. Based on statistical and average weighted degree results are possible to say, that Random Walk mobility model got the lower multiplicity of contacts than Matis model. Thus Std of an average number of used nodes are bigger in the case of Matis model, because of Matis model got more contact during simulation and it had opportunities to meet more and always different nodes due to random mobility pattern and use them to transfer messages. Std of SSBMM is much lower because of this social model has the similar mobility pattern through all simulations. From this reason, almost the same nodes were used to transfer messages in all simulations.

SBOR-sa routing protocol got the worse average time of delivery for random mobility models (Random Walk and Matis model) because there was applied social aspect which changes some relations among nodes. This change causes degradation of an average number of used nodes and Std results for random models, but improve results of SSBMM a little bit.

The third result is focusing on the average time of successful delivery especially on time’s Standard deviation (Fig. 17). On the graphs are displayed results for all four routing methods, which are compared by three mobility models.

DSR wasn’t successful for all mobility models and therefore the average time is infinity with zero Std. Therefore the graphical result isn’t displayed on the graph.

U-DSR wasn’t successful by sparse network and random mobility model, where reached infinity time of delivery. With the same radio range, U-DSR was successful by using SSBMM. Random Walk mobility model covered with the almost the same probability like Matis model, but with the lower number of contacts. Which means, that in Matis model are more contact among nodes during transfer of the message, stable paths between source and destination, what has the direct impact on average time of delivery and Std in positive meaning. In the environment, where SSBMM was used, the average time was the lowest from all model and the Std got low value because every movement in simulations was similar.

SBOR routing protocol got higher values of average time of delivery and Std for Matis model then Random Walk mobility model because in cases of the sparse network Matis model had more opportunities to meet other nodes, which can bring message closer to the destination. From this reason was average time higher. Because of random movement, which was different in all simulations, Matis model got higher values of Std. SSBMM had the similar pattern of movement, therefore Std values were lower and due to social behaviour of nodes, an average time of delivery is lower in cases of using the social routing protocol.

In general, an average time of delivery and Std for SBOR-sa was degraded for random mobility models, while SSBMM perform better results for the sparse network, where differences among simulations were lower than without social aspect.