# Ferry Node Identification Model for the Security of Mobile Ad Hoc Network

Authors: Zhifei Wang; Gang Xu; Na Zhang; Zhihan Qi; Fengqi Wei; Liqiang He
Journal: Security and Communication Networks
 (2021)

---

## Abstract

An opportunistic network is a special type of wireless mobile ad hoc network that does not require any infrastructure, does not have stable links between nodes, and relies on node encounters to complete data forwarding. The unbalanced energy consumption of ferry nodes in an opportunistic network leads to a sharp decline in network performance. Therefore, identifying the ferry node group plays an important role in improving the performance of the opportunistic network and extending its life. Existing research studies have been unable to accurately identify ferry node clusters in opportunistic networks. In order to solve this problem, the concepts of k-core and structural holes have been combined, and a new evaluation indicator, namely, ferry importance rank, has been proposed in this study for analyzing the dynamic importance of nodes in a network. Based on this, a ferry cluster identification model has been designed for accurately identifying the ferry node clusters. The results of the simulations conducted for verifying the performance of the proposed model show that the accuracy of the model to identify the ferry node clusters is 100%.


---

## Body

## 1. Introduction

An opportunistic network is a type of wireless mobile ad hoc network, which does not require a complete link between nodes and can realize communication between disconnected subdomains [1]. In contrast to the traditional networks, in an opportunistic network, messages rely on the encounter opportunities brought about by the node movement and are sent hop-by-hop in the network until they reach the destination node. Opportunistic networks are widely used in wildlife tracking, vehicle-mounted networks, remote areas, and communications in harsh environments [2].Since the communication regions in an opportunistic network are fragmented most of the time, ferry nodes are placed between the disconnected areas in order to realize communication between the fragmented regions and enhance the overall performance of the opportunistic network. Ferry nodes moving between different regions connect to different areas. At present, research studies on ferry nodes mainly include routing algorithms based on ferry nodes [3–12], ferry node motion path planning [13–19], and ferry node network signal coverage [20–23].In the actual application scenarios of opportunistic networks, ferry nodes play a vital role in maintaining communication between the separated areas of nodes. During network operation, if a ferry node withdraws from the network service due to cyberattacks, communication between different regions might get weakened or even get cut off. Therefore, identifying a ferry node cluster from an unfamiliar network environment and protecting these nodes play an important role in maintaining network security and improving the network performance. A few research studies have been conducted on ferry node identification in opportunistic networks, and the main idea in these studies has been the use of node importance evaluation indicators in a complex network for discovering ferry nodes in an opportunistic network. The existing node importance evaluation indicators mainly include degree centrality, betweenness centrality, and k-core indicator. A study in [24] proposed using the degree centrality of a node to measure the importance of the node and to estimate the position of the node in the network according to the number of neighbors of the node. Freeman [25] and Goh et al. [26] proposed the use of the betweenness centrality indicator to evaluate the importance of nodes by using the number of shortest paths through the nodes to the rest of the network. Kitsak et al. [27] proposed a node importance evaluation indicator based on the importance of the position of the node in the entire network and used the number of cores obtained by k-core decomposition as the basis for judging the importance of the node. However, this method is only suitable for complex networks with a static topology and cannot be used in opportunistic networks with constantly changing topologies. In a dynamically changing network, the degree of nodes changes constantly, and it is difficult to find a node that is always at the center of the network using methods based on degree centrality [28]. In a network consisting of moving nodes, the number of shortest paths through the nodes to other nodes is constantly changing. In this case, the betweenness centrality indicator is unable to accurately determine the number of times a node is in the shortest path. In a network involving a single propagation source, the k-core indicator is more accurate than the degree centrality and betweenness centrality indicators in identifying nodes with greater influence in the network. However, this method is ineffective in complex networks involving multiple propagation sources. Due to the features of the opportunistic network, such as its dynamic changing topology, a constant movement of nodes, and multiple propagation sources, none of the abovementioned node importance evaluation indicators are suitable for the identification of ferry node clusters in such networks.With the aim of addressing these shortcomings of the existing methods, the concepts of structural holes of nodes and k-cores have been combined in this study, and the ferry importance rank (FIR) indicator has been proposed, which comprehensively analyzes the local and global importance of nodes in a network. In a changing and multipropagation source opportunistic network, the dynamic importance of nodes can be accurately evaluated by the proposed FIR indicator. On this basis, an FIR-based opportunistic network ferry node cluster identification model has been developed, which divides the operation information of the network over a period of time into equal-length time slices. In each time slice, the nodes that can have significant influence are calculated on the basis of the FIR indicator, and the ferry node cluster in the network is selected according to the nodes selected in the different time slices.


## 2. Related Work

Since opportunistic networks have the characteristics of unstable network topology, irregular node movement, nonfixed connections, and unpredictable encounters [29, 30], the existing key node mining methods based on static complex network analysis techniques cannot be applied to the discovery and selection of ferry nodes in opportunistic networks. In the existing key node mining algorithms of complex networks, researchers have primarily used indicators such as the degree centrality, betweenness centrality, near-centrality, and feature vector centrality for calculating the importance of nodes in complex networks from different perspectives. In opportunistic networks involving sparse nodes, the key node mining algorithms based on the degree centrality index are unable to find the bridge nodes [31]. The key node mining algorithm based on the betweenness centrality indicator has a high time complexity [32], and the feature vector centrality of a node ignores the influence of adjacent node changes on the importance of nodes. Therefore, the key node discovery algorithm based on complex networks cannot be applied to ferry node discovery in opportunistic networks.A key node mining algorithm based on the node degree centrality index analyzes the number of neighbors of a node and the local importance of key nodes but ignores the importance of nodes in the global network topology [31]. On the basis of the degree centrality indicator, Chen [33] proposed a semilocal centrality key node identification method, which partially improved the degree centrality method by calculating the sum of the degrees of all nodes within a certain number of hops. This method partially improved the situation where the degree centrality method falls into a locally optimal solution. Based on the degree centrality and node deletion method, and in combination with the local connectivity of social networks and the shortest path between nodes, Li et al. proposed a connectivity centrality index to measure the influence of nodes in a network [34]. Their method integrated the global and local importance of nodes in the network and more comprehensively described the importance of nodes. However, due to its high computational complexity, their method cannot be used for ferry node discovery in opportunistic networks under dynamic topology.The betweenness centrality index considers the importance of nodes from a global perspective and can efficiently judge the bridge nodes in a network [25]. The fast approximation algorithm based on the random sampling of the shortest path can quickly calculate the betweenness centrality and evaluation importance of all nodes in a large network [35]. A key node discovery algorithm based on the betweenness and closeness centrality for the shortest path used the closeness centrality to analyze the key nodes [36]. In an opportunistic network with social attributes, key nodes can be mined based on the fusion of the weight of the node in the social relationship and its position in the network topology [37]. However, none of the abovementioned key node mining algorithms can complete the discovery and selection of ferry nodes in an opportunity network, where the network topology changes dynamically.Kitsak et al. [27] proposed that the importance of a node depends on the position of the node in the entire network. They calculated the number of node cores based on k-shell and used the k-core index to describe the propagation ability of the node, which can accurately identify the most influential node in the network. However, this method is unsuitable for opportunistic networks with multiple propagation sources. Burt proposed the structural hole theory [38], pointing out that a node with larger structural holes plays a more important role in the communication of the surrounding nodes in the network. The structural hole theory can calculate the structural relationship between multiple nodes and solves the problem of the k-core index not being able to reflect the structural characteristics of neighbors. Zhang and Zhang [39] estimated the importance of nodes by calculating the structure between them, fully considering the influence of the network structure on the importance of nodes. Su et al. [40] combined the structural hole importance of nodes and their neighborhood, which comprehensively considered the number of neighbors of the node and the topological structure between the neighbors. In addition, their method used structure holes to determine the key node, and the calculation range was extended from the neighboring nodes to the neighboring regions. However, in these studies, the problem of falling into the local optimal solution could not be avoided.The importance of nodes in a network is affected by many factors, and the existing methods based on a single importance evaluation index cannot find the key nodes of a network accurately [41, 42]. In order to solve this problem, Zhou et al. merged the node efficiency, degree of the node, and the importance of adjacent nodes to form an importance evaluation matrix for mining key nodes in a network [43]. However, this method did not consider the impact of nonadjacent nodes having a high interdependence on the key nodes. Reference [44] combined the concepts of structural holes and the closeness centrality index for obtaining the influence matrix of the structural holes of a node and analyzed the global and local importance of nodes. However, the time complexity of calculating the node closeness centrality was relatively high. Reference [45] mined the key nodes by fusing the local, behavioral, and global characteristics of nodes and, based on the time slice method, transformed the dynamic topology in the opportunistic network into a static topology set, which provided a new method for mining the key nodes in an opportunistic network.In summary, due to the mobility of nodes in a network, the topology of the network is also in an unstable state, and a message propagates via multiple propagation sources. Thus, the existing key node mining methods based on analyzing complex networks cannot be applied to an opportunistic network directly. In order to automatically find and select the ferry nodes in opportunistic networks, the Ferry_Importance_Rank (FIR) index has been proposed in this work. This index has been used for evaluating the dynamic importance of nodes in opportunistic networks on the basis of the importance of structure holes and the k-core index. In addition, based on FIR, a ferry node cluster identification model has been designed for the opportunistic networks, using which the analysis of the opportunistic networks can perform the discovery and selection of the ferry node group in unfamiliar opportunistic networks.The remainder of this paper has been organized as follows: Section3 provides a description of the three indicators for estimating the node importance in opportunistic networks. Details of the proposed FIR-based ferry node identification model for opportunistic networks, based on the importance of structural holes and k-core index, have been given in Section 4. Section 5 presents a comprehensive set of simulation results for various opportunistic network scenarios. A detailed discussion of the analysis of the results has also been given in this section. A summary of the present work and the conclusions drawn from it have been given in Section 6.


## 3. Preliminaries

In this section, some preliminary knowledge, including the structural holes theory and k-core importance theory, has been reviewed.Definition 1.
Structural holes
“Structural holes” is a classical theory of social networks developed by Burt [38], which is often used for evaluating the importance of nodes in local networks. If nodes B and C are neighbors of node A and nodes B and C are not adjacent and can only communicate via node A, there exists a structure hole between nodes B and C, or there is a structural hole on node A. The larger the number of structural holes possessed by a node is, the stronger its communication ability is.


### 3.1. Computing Methods for Estimating the Importance of Structural Holes

Suppose that the number of nodes in a network isn; then a matrix A of dimensions n × n is established. This matrix is used for representing the connection status of the nodes in a network. aij = 0 implies that nodes i and j are disconnected, whereas aij  = 1 implies that nodes i and j are connected.Suppose thatki is the degree of node i; then ki is calculated using equation (1), where G is the set of all the nodes in the topology map.(1)ki=∑j∈Gaij,and Qi is the adjacency degree of node i. It is the sum of degrees of all the neighbors of node i, as expressed in equation (2).(2)Qi=∑ϖ∈rikϖ.In Equation2, ri is the set of neighboring nodes of node i.The network constraint coefficients of nodes are related to multiple factors such as the connection of a node with the other nodes and the structure between a node and its neighbor. Therefore, the degree and the topology structure of its neighborhood,Pij, should be taken into consideration when calculating the network constraint coefficient of nodes. Pij is calculated using the expression given in (3)Pij=Qj∑v∈riQv.The difficulty for a node to form structural holes is represented by the network constraint coefficient,RCi, of the node, which is also a measure of the size of the structural holes of the node. The network constraint coefficient of a node is inversely proportional to its degree of structural holes and is calculated using (4)RCi=∑i∈riPij+∑qPiqPqj2,where q is a node in the intersection of the neighbors of nodes i and j, which is not equal to i or j.The constraint coefficient of nodei is the structural hole importance index of the node, and the ratio of the sum of the constraint coefficients of all nodes in the network is calculated using (5)Li=1−RCi∑j=1n1−RCj.Definition 2.
Structural hole constraint coefficient
The structural hole constraint coefficient,Lni, of node i is defined as the ratio of the structural hole importance index value of node i to the sum of the structural hole importance index values of all nodes neighboring node i. Lni is used for measuring the constraints for a node when forming structural holes. It is calculated using (6)Lni=Li∑k∈riLk.
In this work, an algorithm for calculating the importance of structural holes in opportunistic networks has been developed, as shown in Algorithm1, namely, the calculate structural hole importance (CSHI) algorithm.Algorithm 1: Algorithm for calculating the importance of structural holes.
Input: node setGOutput: structural hole constraint coefficient,Lni, of all nodes in G(1)
fori∈G: //G is the node set of the opportunistic network(2)
Calculate k (i)(3)
fori∈G:(4)
Calculate Q (i)(5)
fori∈G:(6)
forj∈ri: //ri is the set of all neighboring nodes of node i(7)
CalculatePij(8)
forq∈ri∩rj:(9)
CalculatePiq and Pqj(10)
CalculateRCi(11)
fori∈G:(12)
CalculateLi(13)
fori∈G:(14)
CalculateLni(15)
return LnDefinition 3.
K-core importance
Being a classical concept in graph theory, the k-core theory calculates the influence of nodes in a network based on the degree of nodes. The steps of k-core decomposition are as follows: recursively delete the nodes having a degree ofk or less in the network and assign k-shell values to the deleted nodes. Repeat the process until all nodes in the network are assigned k-shell values. In the k-core decomposition algorithm, a large number of nodes are at the same network level, which leads to the incapability of the algorithm when further calculating their node importance.


### 3.2. Calculation of K-Core Importance

In the initial stage,kim=ki are recorded for every node, the nodes with the smallest kim value are removed from the topology map, and kim are assigned to Ksi of these nodes. Subsequently, kim of the remaining nodes are updated as kim=kir+λke, where λ is the adjustment factor and 0≤λ≤1, ke is the removed degree of the previous stage, and kir is the degree of the remaining nodes. The above process is repeated until all the nodes obtain the Ksi value. Then, Ksi is the k-core index of node i.According to the calculation method of k-core importance, this paper presents the calculation algorithm of the k-core index of nodes in an opportunistic network, as shown in Algorithm2, namely, the calculate k-core importance (CKCI) algorithm.Algorithm 2: Algorithm for calculating the k-core index.
Input: node set GOutput: K-core importance of all nodes in the set G(1)
fori∈G:(2)
kim=ki(3)
Gn=G(4)
whileGn≠∅:(5)
ke=0(6)
forj∈Gn: //Gn represents the set of the remaining nodes in the topology graph(7)
ifkjm<∀kqm: (q∈Gn,q≠j)(8)
Ksj=kjm(9)
ke=kjm(10)
Gn=Gn⧹j(11)
forl∈Gn:(12)
klm=klm+λke(13)
returnKsThe k-core importance of nodei refers to the ratio of Ksi of node i and the sum of Ksi of all nodes, which can be calculated using equation (7) after the k-core index of node i is known:(7)Mi=Ksi∑j=1nKsj.


## 3.1. Computing Methods for Estimating the Importance of Structural Holes

Suppose that the number of nodes in a network isn; then a matrix A of dimensions n × n is established. This matrix is used for representing the connection status of the nodes in a network. aij = 0 implies that nodes i and j are disconnected, whereas aij  = 1 implies that nodes i and j are connected.Suppose thatki is the degree of node i; then ki is calculated using equation (1), where G is the set of all the nodes in the topology map.(1)ki=∑j∈Gaij,and Qi is the adjacency degree of node i. It is the sum of degrees of all the neighbors of node i, as expressed in equation (2).(2)Qi=∑ϖ∈rikϖ.In Equation2, ri is the set of neighboring nodes of node i.The network constraint coefficients of nodes are related to multiple factors such as the connection of a node with the other nodes and the structure between a node and its neighbor. Therefore, the degree and the topology structure of its neighborhood,Pij, should be taken into consideration when calculating the network constraint coefficient of nodes. Pij is calculated using the expression given in (3)Pij=Qj∑v∈riQv.The difficulty for a node to form structural holes is represented by the network constraint coefficient,RCi, of the node, which is also a measure of the size of the structural holes of the node. The network constraint coefficient of a node is inversely proportional to its degree of structural holes and is calculated using (4)RCi=∑i∈riPij+∑qPiqPqj2,where q is a node in the intersection of the neighbors of nodes i and j, which is not equal to i or j.The constraint coefficient of nodei is the structural hole importance index of the node, and the ratio of the sum of the constraint coefficients of all nodes in the network is calculated using (5)Li=1−RCi∑j=1n1−RCj.Definition 2.
Structural hole constraint coefficient
The structural hole constraint coefficient,Lni, of node i is defined as the ratio of the structural hole importance index value of node i to the sum of the structural hole importance index values of all nodes neighboring node i. Lni is used for measuring the constraints for a node when forming structural holes. It is calculated using (6)Lni=Li∑k∈riLk.
In this work, an algorithm for calculating the importance of structural holes in opportunistic networks has been developed, as shown in Algorithm1, namely, the calculate structural hole importance (CSHI) algorithm.Algorithm 1: Algorithm for calculating the importance of structural holes.
Input: node setGOutput: structural hole constraint coefficient,Lni, of all nodes in G(1)
fori∈G: //G is the node set of the opportunistic network(2)
Calculate k (i)(3)
fori∈G:(4)
Calculate Q (i)(5)
fori∈G:(6)
forj∈ri: //ri is the set of all neighboring nodes of node i(7)
CalculatePij(8)
forq∈ri∩rj:(9)
CalculatePiq and Pqj(10)
CalculateRCi(11)
fori∈G:(12)
CalculateLi(13)
fori∈G:(14)
CalculateLni(15)
return LnDefinition 3.
K-core importance
Being a classical concept in graph theory, the k-core theory calculates the influence of nodes in a network based on the degree of nodes. The steps of k-core decomposition are as follows: recursively delete the nodes having a degree ofk or less in the network and assign k-shell values to the deleted nodes. Repeat the process until all nodes in the network are assigned k-shell values. In the k-core decomposition algorithm, a large number of nodes are at the same network level, which leads to the incapability of the algorithm when further calculating their node importance.


## 3.2. Calculation of K-Core Importance

In the initial stage,kim=ki are recorded for every node, the nodes with the smallest kim value are removed from the topology map, and kim are assigned to Ksi of these nodes. Subsequently, kim of the remaining nodes are updated as kim=kir+λke, where λ is the adjustment factor and 0≤λ≤1, ke is the removed degree of the previous stage, and kir is the degree of the remaining nodes. The above process is repeated until all the nodes obtain the Ksi value. Then, Ksi is the k-core index of node i.According to the calculation method of k-core importance, this paper presents the calculation algorithm of the k-core index of nodes in an opportunistic network, as shown in Algorithm2, namely, the calculate k-core importance (CKCI) algorithm.Algorithm 2: Algorithm for calculating the k-core index.
Input: node set GOutput: K-core importance of all nodes in the set G(1)
fori∈G:(2)
kim=ki(3)
Gn=G(4)
whileGn≠∅:(5)
ke=0(6)
forj∈Gn: //Gn represents the set of the remaining nodes in the topology graph(7)
ifkjm<∀kqm: (q∈Gn,q≠j)(8)
Ksj=kjm(9)
ke=kjm(10)
Gn=Gn⧹j(11)
forl∈Gn:(12)
klm=klm+λke(13)
returnKsThe k-core importance of nodei refers to the ratio of Ksi of node i and the sum of Ksi of all nodes, which can be calculated using equation (7) after the k-core index of node i is known:(7)Mi=Ksi∑j=1nKsj.


## 4. Ferry Node Identification Model Based on FIR for an Opportunistic Network

The topology of an opportunistic network changes dynamically. Therefore, the existing key node mining algorithms based on static network indicators are inapplicable in an opportunistic network. In order to solve the problem of mining the key nodes in an opportunistic network, we have divided the network into several snapshots with equal runtime, established a static topology of the opportunistic network in the snapshots, mined the key nodes in each snapshot, and determined the ferry nodes in the opportunistic network based on the frequency with which the key nodes are selected.The use of a single indicator cannot evaluate the importance of nodes accurately [41]. In order to fix the shortcomings of using a single index, the FIRi index has been proposed in this work, which is an indicator of the fusion of structural hole importance of a node and k-core importance. This index comprehensively analyzes the local and global importance of nodes based on the ferry node group in the FIRi election network.


### 4.1. Ferry Importance Rank Algorithm

The node importance evaluation model based on the FIR index has been used for measuring the importance of nodes in an opportunistic network. The model combines the k-core importance,Mi, of the node and the structural hole importance, Lni, and calculates the FIRi index. The larger the FIRi value is, the higher the importance of the node is. To enable the mining of key nodes in the dynamic topology of an opportunistic network, the FIR-based model establishes a time-slice snapshot sequence for the running opportunistic network topology, conducts key node mining on the basis of the static topology graph sequence, and counts the number of times each node is selected as a key node. The selected node is the ferry node, and the node that has been selected for the highest number of times is the most important node among all ferry nodes. The FIRi indicator is calculated using the expression given in (8)FIRi=αMi+βLni.From the analysis of the simulations performed for verifying the proposed model, it is found that whenα is 2 and β is 1, the node importance evaluation model achieves the best performance.TheFIRi index is calculated by performing the following steps: the structural hole weight, Ln, and the k-core index, Ks, of each node in the node set G are calculated using Algorithms 1 and 2. Following this, the k-core importance, Mi, of each node is calculated according to the expression given in Equation 7. Finally, the FIR importance index, FIRi, of node i in the node set G is calculated according to Equation 8. The calculation process is shown in Algorithm 3, namely, the calculate ferry importance rank (CFIR) algorithm.Algorithm 3: Algorithm for calculating the FIR importance.
Input: node set GOutput: FIR importance of all the nodes in the set G(1)
Ln = CSHI(G)(2)
Ks = CKCI(G)(3)
fori∈G:(4)
CalculateMi according to Equation 7(5)
fori∈G:(6)
FIRi=αMi+βLni(7)
return FIRTo calculate the ferry node cluster in a network, the key nodes in each snapshot should be calculated separately. First, all nodes in the topology are inputted into setG, and the FIR values of all nodes in G are calculated according to Algorithm 3. The node with the highest FIR value in the topology map, which corresponds to this time slice, is inputted into the ferry node set. All the key nodes in the snapshot are calculated using the method described above, and the final set of ferry nodes is the ferry node group in the network. The ferry node identification algorithm for an opportunistic network is shown in Algorithm 4, namely, the ferry node identification (FNI) algorithm flow of the ferry node cluster identification algorithm is shown in (Figure1)Algorithm 4: Algorithm for identification of ferry nodes.
Input: the set of time slice (T)Output: ferry nodes in the network(1)
Ferry = {∅}(2)
fort∈T:(3)
G = nodes in t(4)
FIR = CFIR(G)(5)
Ferry∩i|FIRi≥∀FIRj,i,j∈G(6)
return FerryFigure 1
Flowchart of the ferry node cluster identification algorithm.


## 4.1. Ferry Importance Rank Algorithm

The node importance evaluation model based on the FIR index has been used for measuring the importance of nodes in an opportunistic network. The model combines the k-core importance,Mi, of the node and the structural hole importance, Lni, and calculates the FIRi index. The larger the FIRi value is, the higher the importance of the node is. To enable the mining of key nodes in the dynamic topology of an opportunistic network, the FIR-based model establishes a time-slice snapshot sequence for the running opportunistic network topology, conducts key node mining on the basis of the static topology graph sequence, and counts the number of times each node is selected as a key node. The selected node is the ferry node, and the node that has been selected for the highest number of times is the most important node among all ferry nodes. The FIRi indicator is calculated using the expression given in (8)FIRi=αMi+βLni.From the analysis of the simulations performed for verifying the proposed model, it is found that whenα is 2 and β is 1, the node importance evaluation model achieves the best performance.TheFIRi index is calculated by performing the following steps: the structural hole weight, Ln, and the k-core index, Ks, of each node in the node set G are calculated using Algorithms 1 and 2. Following this, the k-core importance, Mi, of each node is calculated according to the expression given in Equation 7. Finally, the FIR importance index, FIRi, of node i in the node set G is calculated according to Equation 8. The calculation process is shown in Algorithm 3, namely, the calculate ferry importance rank (CFIR) algorithm.Algorithm 3: Algorithm for calculating the FIR importance.
Input: node set GOutput: FIR importance of all the nodes in the set G(1)
Ln = CSHI(G)(2)
Ks = CKCI(G)(3)
fori∈G:(4)
CalculateMi according to Equation 7(5)
fori∈G:(6)
FIRi=αMi+βLni(7)
return FIRTo calculate the ferry node cluster in a network, the key nodes in each snapshot should be calculated separately. First, all nodes in the topology are inputted into setG, and the FIR values of all nodes in G are calculated according to Algorithm 3. The node with the highest FIR value in the topology map, which corresponds to this time slice, is inputted into the ferry node set. All the key nodes in the snapshot are calculated using the method described above, and the final set of ferry nodes is the ferry node group in the network. The ferry node identification algorithm for an opportunistic network is shown in Algorithm 4, namely, the ferry node identification (FNI) algorithm flow of the ferry node cluster identification algorithm is shown in (Figure1)Algorithm 4: Algorithm for identification of ferry nodes.
Input: the set of time slice (T)Output: ferry nodes in the network(1)
Ferry = {∅}(2)
fort∈T:(3)
G = nodes in t(4)
FIR = CFIR(G)(5)
Ferry∩i|FIRi≥∀FIRj,i,j∈G(6)
return FerryFigure 1
Flowchart of the ferry node cluster identification algorithm.


## 5. Experiments

The opportunistic network environment (ONE) simulator is an important experimental simulation platform for studying opportunistic networks. In this study, ONE1.4.1 was used for performing simulations, and the report is ConnectivityDtnsim2Report. The parameter settings of the simulation environment are listed in Table1. In this study, three different simulation scenarios were set up and were compared with the betweenness-based algorithm (referred to as the VC model) [35]. The FIR-based model proposed in this study and the VC model were used for identifying the ferry nodes in different scenarios, and the performance of the models in identifying the nodes in different environments was analyzed.Table 1
The parameter of the simulation scenario.
CategoryParameterValuesComputer configurationCPUi7 9700KOSWindows 10 ProfessionalRAM8 GScenario settingsSimulation area size200 ∗ 200m2Simulation time24 h (86400 s)Message transmission carrierBluetooth deviceMessage transmission range50 mNodes movement model in the regionMapRouteMovement (MRM)Node movement model between regionsRandomWaypoint (RWP)Number of nodes in the region10Nodes moving speed in the region1 m/sNodes moving speed between regions5 m/sSparse multiparallel opportunistic networkNumber of experimental regions4Number of nodes between regions4Dense multiparallel opportunistic networkNumber of experimental regions6Number of nodes between regions6Star-shaped multiparallel opportunistic networkNumber of experimental regions5Number of nodes between regions4The three simulation scenarios used in this study are an opportunistic network with sparse nodes, an opportunistic network with dense nodes, and an opportunistic network with star-shaped distribution of nodes (referred to as scenarios 1, 2, and 3, respectively). Scenario 1 was used for simulating the nodes that are sparsely distributed in operating environments, for example, the opportunistic networks in scenarios such as grasslands, remote villages, or agricultural and pastoral areas. Scenario 2 was used for simulating an operating environment with densely distributed nodes, such as campus environments and opportunistic networks in urban environments. Scenario 3 was used for simulating the operating environment where the nodes are unevenly distributed, such as an opportunistic network in the mountains, forests, and other scenarios, where the terrain is more restricted. The simulation environment setup in this study covered various practical application scenarios of the opportunity network and comprehensively verified the effect of using the FIR model in an actual operating environment. The schematics of the simulation environment setups are shown in Figures2–4.Figure 2
Schematic of the sparse multiparallel ferry opportunistic network.Figure 3
Schematic of the dense multiparallel ferry opportunistic network.Figure 4
Schematic of the star-shaped multiparallel ferry opportunistic network.Figure2 shows the schematic of an opportunistic network involving a relatively sparse node distribution. In this scenario, the number of node groups is small, and the geographical distribution of the node groups is sparse. Figure 3 shows the schematic of an opportunistic network with densely distributed nodes. Compared to scenario 1, this scenario has a larger number of node groups, and the node groups are densely distributed. Figure 4 shows an opportunistic network with a star-shaped node distribution. This scenario is used for simulating a scene where the distribution of nodes is irregular due to the terrain constraints such as mountains and river valleys. Simulations were carried out using opportunistic networks with different node distributions, and the results thus obtained are shown in Figures 5–16.Figure 5
Comparison of the simulation results for mining ferry nodes in a sparse multiparallel opportunistic network.Figure 6
Comparison of the simulation results for mining ferry nodes in a dense multiparallel opportunistic network.Figure 7
Comparison of the simulation results for mining ferry nodes in a star-shaped multiparallel opportunistic network.Figure 8
Comparison of the simulation results for the discovery of the ferry nodes in scenario 1 when the time slice length is 1200 s.Figure 9
Comparison of the simulation results for the discovery of the ferry nodes in scenario 1 when the time slice length is 1800 s.Figure 10
Comparison of the simulation results of the discovery of the ferry nodes in scenario 1 when the time slice is 2400 s.Figure 11
Comparison of the simulation results for the discovery of ferry nodes in scenario 2 when the time slice is 1200 s.Figure 12
Comparison of the simulation results for the discovery of ferry nodes in scenario 2 when the time slice is 1800 s.Figure 13
Comparison of the simulation results for the discovery of ferry nodes in scenario 2 when the time slice is 2400 s.Figure 14
Comparison of the simulation results for the discovery of ferry nodes in scenario 3 when the time slice is 1200 s.Figure 15
Comparison of the simulation results for the discovery of ferry nodes in scenario 3 when the time slice is 1800 s.Figure 16
Comparison of the simulation results for the discovery of ferry nodes in scenario 3 when the time slice is 2400 s.Figures5–7 show the comparison of the results obtained from the FIR-based model developed in this work and the VC model election ferry node group in opportunistic networks in different scenarios. In Figures 5–7, the node identified in the upper right corner is the ferry node set marked in the scene, and the blue line represents the other nodes in the scene. From the analysis of the simulation results of different scenarios in the opportunistic network, it can be observed that when the time slice length is less than 200 s, the FIR-based model proposed in this work has a lower accuracy of mining ferry nodes in different scenarios. This is because when the time slice length is less than 200 s, the distribution of nodes is sparse, and the ferry nodes are ignored because they do not form effective connections between regions. The error rate is significantly reduced for time slices greater than 500 s. When the time slice length is greater than 1000 s, the accuracy rate is higher, and the rate of recognizing the ferry nodes in the opportunistic network in the above three scenarios is 100%.Further, the FIR-based model and the VC model were used for performing simulations in the above scenarios for time slices of 1200, 1800, and 2400 s, respectively. The results obtained from these simulations are shown in Figures8–16 below.Figures8–10 show the comparison results of the simulation performed for scenario 1. In this, the simulation results obtained by applying the FIR-based model and the VC model have been compared for the case of sparse multiparallel opportunistic network, when the time slice length was set to 1200, 1800, and 2400 s, respectively, and the nodes h43, g32, f21, and e10 were set as the ferry nodes. From Figure 8, it can be seen that the FIR-based model can accurately identify all ferry nodes, whereas the VC model can only identify a few of them. Thus, the analysis proves the effectiveness of the use of the FIR-based model in opportunistic networks involving sparse nodes.Figures11–13 are the simulation results for scenario 2. In this simulation, the time slice length was set to 1200, 1800, and 2400 s, respectively, and the ferry nodes were set to g10, h21, i32, j43, k54, and l65, respectively. From the simulation results, it can be seen that, in scenario 2, the FIR-based model and the VC model exhibit similar results in identifying the ferry nodes. This is because when the distribution of nodes in the opportunistic network is dense, the topology between the nodes is more stable. In this case, the VC model, which is based on the betweenness centrality indicator, can achieve better results. When the time slice of 2400 s was taken, the number of ferry nodes g10, h21, i32, j43, k54, and l65 selected by the FIR-based model was 2, 3, 13, 10, 6, and 4 and the hit rates were 5%, 8%, 34%, 26%, 16%, and 11%, respectively. Further, the higher the ferry node hit rate is, the more important its role in the ferry node group is and the greater its impact on the network is.In the opportunistic network of scenario 3, the distribution of nodes is star-shaped. The comparison of the simulation results of the FIR-based model and the VC model is shown in Figures14–16. In scenario 3, the nodes e10, f21, g32, h43, and i44 were set as the ferry nodes. The simulation results show that the FIR-based model is able to identify all ferry nodes, whereas the VC model recognizes only node i44. This indicates that the FIR algorithm can accurately find the ferry nodes groups in the opportunistic network of scenario 3.In summary, the VC model, which is based on the betweenness centrality indicator, can only identify all ferry node groups in opportunistic networks involving dense nodes, whereas the FIR-based model proposed in this work is able to find the ferry nodes groups in various common opportunistic networks. This effectively fixes the problem of omission of the existing ferry node mining algorithm based on the betweenness centrality indicator in scenarios 1 and 3. The FIR-based model exhibits a 100% success rate in identifying the ferry nodes in all three scenarios, whereas the VC model only reaches 100% identification of ferry nodes groups in scenario 2. In scenarios 1 and 3, the recognition rate of ferry nodes groups by the VC model is only 25%. Thus, it can be seen that the ferry node identification model in an opportunistic network based on FIR can find the ferry nodes in the opportunistic networks effectively and reliably.


## 6. Conclusion

Based on the importance of structural holes and k-cores, an FIR indicator has been proposed in this study for evaluating the importance of nodes in the opportunistic network. Based on this indicator, an FIR-based opportunistic network ferry node identification model has been proposed. Compared to the VC model based on the betweenness centrality index, the FIR-based model is able to accurately identify the ferry node groups in a variety of application scenarios. An analysis of the local importance of nodes has been done in this study through the structural hole constraint coefficients, and the k-core importance of nodes has been used to analyze the global importance of nodes. Further, the FIR indicators have been proposed by fusing the structural hole attributes and k-core importance of nodes, which can evaluate the importance of nodes in an opportunistic network with dynamic topology changes and then identify the ferry nodes in the opportunistic network. Results of the simulations performed for verifying the proposed model have proved that the FIR-based model proposed in this work can accurately and efficiently identify the ferry nodes in opportunistic networks under low time complexity. In addition, it solves the problem of missing ferry nodes in the VC model and provides an important research foundation for an opportunistic network to automatically identify ferry nodes, protect these nodes in a targeted manner, and maintain network security.



---

*Source: 6682311-2021-01-06.xml*