CN111787592B - An Opportunistic Routing Implementation Method Based on Spectral Clustering and C4.5 Algorithm - Google Patents

Abstract

The invention relates to a method for realizing opportunistic routing based on spectral clustering and C4.5 algorithm. The invention mainly includes: (1) a calculation method of intimacy weight; (2) a sub-community division method based on spectral clustering; (3) a "messenger node" identification model based on the C4.5 algorithm; (4) an intimate community-based identification model And the opportunistic routing implementation method of decision tree algorithm. The nodes are communityized through spectral clustering. When the source node and the destination node are in the same community, messages are transmitted based on simple flooding, which improves the efficiency of message transmission. When the source node and the destination node are in different communities, the "messenger node" is determined by the decision tree model, and the "messenger node" is used as a medium to transmit the message to the destination community to realize the cross-community transmission of the message.

Description

An Opportunistic Routing Implementation Method Based on Spectral Clustering and C4.5 Algorithm

technical field

The invention relates to the field of machine learning and wireless communication technology, and a method for implementing opportunistic routing based on spectral clustering and C4.5 algorithm.

Background technique

With the rise of 5G and the rapid development of wireless communication technology, more and more small-sized, low-cost, and short-range communication mobile terminal devices have been popularized on a large scale. Wireless communication networks are widely used in various extreme and challenging special environments such as underground, underwater, deep space, and hills because of their flexible communication, simple deployment, and low cost. However, in these applications, the network may not be connected most of the time due to various reasons such as node movement, node sparseness, RF shutdown, or signal attenuation caused by obstacles. In this network environment, the traditional MANET communication mode cannot be applied. The opportunistic network can effectively solve the above problems because of its special communication method "store-carry-forward", but due to the dynamic change of the topology of the opportunistic network, there is no relatively stable data transmission path between nodes. Therefore, implementing a routing protocol with good routing performance is one of the most challenging problems in opportunistic network research.

To overcome the problems caused by unpredictability and high mobility in opportunistic networks, a number of routing protocols have been proposed that attempt to use the mobility of nodes themselves to help with routing, most of them employ flooding-based methods, where messages Propagated throughout the network with a limited time-to-live (TTL). Nodes help messages reach their destination by sending replicas to other nodes during flooding. Although flooding improves delivery probability, it requires high overhead and consumes a lot of node energy. Therefore, simple flooding is impractical for mobile nodes with limited energy.

With the development of artificial intelligence, machine learning algorithms have made great progress in studying optimization problems. Therefore, it can be considered to optimize and improve by combining machine learning methods in the field of opportunistic networks, and forward messages adaptively. At present, spectral clustering (SC) is a widely used clustering algorithm. Compared with the traditional K-Means algorithm, spectral clustering has stronger adaptability to data distribution and is very effective for clustering sparse data. , and the computational complexity of clustering is also much smaller. The C4.5 algorithm is a classification decision tree algorithm in the machine learning algorithm. It is an important algorithm based on the ID3 algorithm and has a good effect on data classification. Therefore, the present invention utilizes the intimate community divided by spectral clustering and the "messenger node" identification model constructed based on the C4.5 algorithm to assist message forwarding in the opportunistic network.

SUMMARY OF THE INVENTION

The present invention proposes an opportunistic routing implementation method based on spectral clustering and C4.5 algorithm, which mainly includes four major contents:

(1) Intimacy weight calculation method;

(2) Sub-community division method based on spectral clustering;

(3) "Messenger node" identification model based on C4.5 algorithm;

(4) Implementation method of opportunistic routing based on close community and decision tree algorithm.

The details are as follows:

(1) Intimacy weight calculation method.

Definition 1 The higher the intimacy between nodes, the easier it is to communicate. In the present invention, the inverse of the average interval communication time between nodes in a unit time is taken as its intimacy. Its meaning indicates that the shorter the time two nodes wait for the next communication, the closer they are. The average interval communication time is calculated by the following formula:

Where Intervals _(i,j) represents the average interval communication time between node i and node j, delay_time _(i,j,n) represents the nth time interval between node i and node j, and count represents the unit time between node i and node j The total number of communications between j. The interval duration is equal to the current start communication time minus the last communication end time.

The intimacy between nodes can be calculated by the following formula:

where λ _(i,j) represents the intimacy between node i and node j. If there is only one communication between nodes in a unit time, it is simply considered that the intimacy between the pair of nodes is 0.

Considering the importance of node communication frequency per unit time, the final definition of intimacy will comprehensively consider the node communication frequency. The specific formula is as follows:

Intimacy _(i,j) = count*λ _(i,j)

where Intimacy _(i,j) represents the final intimacy between node i and node j. Finally, calculate the intimacy between nodes according to this formula, and use it as its weight to construct an undirected and weighted communication graph, and store the communication graph information in a matrix, so as to analyze and mine important information such as community characteristics between nodes.

(2) Sub-community division method based on spectral clustering.

Spectral Clustering (SC) is a clustering method based on graph theory. By cutting the graph composed of all nodes, the edge weights between different subgraphs after cutting the graph are as low as possible, while the subgraphs are cut. The edge weights in the graph are as high as possible, so as to achieve the purpose of clustering. The present invention uses spectral clustering to divide the communication graph to construct multiple sub-communities. Specific steps are as follows:

Adjacency matrix construction: Based on the communication graph obtained in method (1), the weight information of the edges in the graph is obtained to construct an adjacency matrix W.

Degree matrix construction: for any point v _i in the graph, its degree d _i is defined as the sum of the weights of all edges connected to it, namely

Based on the constructed adjacency matrix, use the degree of each point to obtain an n-dimensional degree matrix D, which is a diagonal matrix, only the main diagonal has a value, corresponding to the degree of the i-th point in the i-th row.

Calculate and normalize the Laplacian matrix: The definition formula of the Laplacian matrix is as follows:

L=D-W

The normalized Laplacian matrix can be calculated by the following formula:

Calculate the eigenvectors f corresponding to each of the k ₁ eigenvalues of the normalized Laplacian matrix Q: This step cleverly converts the graph cutting problem into a Laplacian matrix eigenvalue problem, and transforms the discrete clustering problem into The relaxation is a continuous eigenvector, and the smallest series eigenvector corresponds to the optimal series partitioning method of the graph.

构建多个子社区。Finally, the matrix composed of the corresponding eigenvectors f is normalized by row to form an n×k ₁ -dimensional eigenmatrix F. Take each row in F as a k ₁ -dimensional sample, with a total of n samples, and perform clustering with the input clustering method, and the clustering dimension is k ₂ . get cluster

Build multiple sub-communities.

(3) "Messenger node" identification model based on C4.5 algorithm.

In an opportunistic network, nodes in the same community often "meet" to facilitate message forwarding. When a message is forwarded to a node, the message can be forwarded to other nodes in the community where the node is located, and other nodes can be flooded in the sub-community, which can improve the efficiency of message delivery and quickly deliver the message to the destination node. After obtaining multiple sub-communities in method (2), if the source node and the destination node are in the same sub-community, simply flooding in the community can successfully deliver the message to the destination node with high probability. If the source node and the destination node are not in the same community and need to transmit messages across communities, it is necessary to find some "messenger nodes" that are separated from multiple sub-communities. Therefore, by obtaining some attribute features of the node, the C4.5 algorithm is used to construct a model that can identify the "messenger node", and the model is used to determine the "messenger node". Specific steps are as follows:

Feature selection: In opportunistic networks, the following attribute features are often meaningful for determining "messenger nodes".

1) Node Activity: Indicates the activity capability of a node. Measured by the average number of neighbor nodes over a period of time;

2) Node Centrality: Indicates the importance of a node. The number of types of other nodes connected to this node is obtained by analyzing the node encounter history. The more types, the larger the center point of the node;

3) Node recency: based on how long the node has recently established a connection with any other node;

4) Node reliability: based on the ratio of the number of successful messages delivered by the node to the total number of times in the past;

5) Node free buffer space: If there is not much or almost no free buffer space left, the chance of message transmission is relatively small;

6) Node transmission speed: The transmission speed of different nodes is often inconsistent. The faster the transmission speed, the stronger the node transmission capability;

7) Node transmission range: the larger the transmission range, the easier it is for the node to find the destination node;

8) Remaining energy of nodes: each node will consume energy, and when the energy is exhausted, the node will fall into a state of crash.

Decision tree construction: The key issues in decision tree construction are which attribute to choose as the root node, which attributes to use as the internal node and when to stop and get the target state, the leaf node. In the present invention, the C4.5 algorithm is adopted, and the information gain ratio of each attribute is calculated and compared as the feature selection criterion. Specific steps are as follows:

Training data preparation: Based on the node communication history, calculate and count the attributes of each node, the format is as follows.

Numbering Activity Centrality recency reliability free cache transfer speed Transmission range residual energy Free community 1 5 8 3 0.2 10 20 10 50 no … … … … … … … … … … n 10 8 5 0.6 50 15 10 100 Yes

Information entropy calculation: In information theory, entropy is a measure of the uncertainty of a random variable. The greater the entropy, the greater the uncertainty of the random variable. The information entropy of each node attribute can be calculated by the following formula:

where Entropy(t) represents the information entropy, and p _k|t represents the probability that node t is classified as k.

Information gain calculation: Information gain indicates the degree to which the uncertainty of class Y information is reduced by knowing the information of a certain attribute feature X, which can be calculated by the following formula:

Gain(N,i) represents the information gain, N is the parent node, _Nk is the child node, and i in Gain(N,i) is selected as the attribute of the N node.

Information gain ratio calculation: ID3 tends to select attributes with more values when calculating. In order to avoid this problem, C4.5 has been improved to select attributes by means of information gain ratio. The specific formula is as follows:

Finally, according to the calculation result, the attribute with the largest information gain ratio is selected as the root node, and the child nodes are established according to the different values of the attribute; new child nodes are generated in the same way for each child node until the information gain ratio is small or there is no Until the features can be selected, the decision tree construction is completed.

(4) Implementation method of opportunistic routing based on close community and decision tree algorithm.

The implementation method of opportunistic routing based on intimate community and decision tree algorithm can be divided into three stages, namely community division stage, decision tree model training stage and transmission stage. In the community division stage, all communication nodes are divided into multiple sub-communities based on method (2) using spectral clustering. In the decision tree model training stage, based on method (3), the C4.5 algorithm is used to collect training data, and by acquiring some attribute features of nodes, a decision tree model that can identify "messenger nodes" is trained. In the transmission phase, there are two message delivery methods: same-community message delivery and cross-community message delivery. When the source node and the destination node are in the same community, the same community message delivery method is adopted: the source node encounters a neighbor node and determines whether the neighbor node is in the same community as the destination node. If so, copy and forward the message, otherwise, the node continues to move. When the source node and the destination node are in different communities, the cross-community message transmission method is adopted: the source node encounters a neighbor node, and judges whether the neighbor node is in the same community as the destination node. If so, copy and forward the message, otherwise, judge based on the trained decision tree model. Whether the node is a "messenger node", if so, copy and forward the message, otherwise, the node continues to move.

Description of drawings

Fig. 1 is the working flow chart of the present invention.

Detailed ways

The present invention is an opportunity routing implementation method based on spectral clustering and C4.5 algorithm, and the specific steps are as follows:

Step 1: Data Preparation

Node movement often has certain regularity and periodicity. Therefore, according to the periodicity of node movement, the historical records of node communication within a specific time range are collected, and the intimacy between nodes is calculated based on the intimacy function, which is used as its weight to construct a Zhang Wuxiang has the right to communicate.

Step 2: Sub-community division

Based on the spectral clustering method, the undirected weighted communication graph is clustered and divided to obtain multiple sub-communities. Nodes in different communities are marked with different signs, and a table structure is defined for storage.

Step 3: Building a decision tree model

When transmitting messages across communities, "messenger nodes" are often needed as a medium to transmit messages to the destination community. Therefore, based on the C4.5 algorithm, training data is collected, and some attribute characteristics of nodes are obtained to train a "messenger node" that can identify the "messenger node". decision tree model.

Step 4: Messaging

When the source node and the destination node are in the same community, the same community message delivery method is adopted: the source node moves and encounters a neighbor node, and judges whether the neighbor node is in the same community as the destination node. If so, copy and forward the message, otherwise, the node continues to move. When the source node and the destination node are in different communities, the cross-community message transmission method is adopted: the source node moves and encounters a neighbor node, and judges whether the neighbor node is in the same community as the destination node. If so, copy and forward the message, otherwise, based on the trained decision tree model Determine whether the node is a "messenger node", if so, copy and forward the message, otherwise, the node continues to move.

Claims (1)

1. An opportunistic routing implementation method based on spectral clustering and a C4.5 algorithm is characterized by comprising the following steps:

(1) an intimacy weight calculation method;

(2) a sub-community partitioning method based on spectral clustering;

(3) a messenger node identification model based on a C4.5 algorithm;

(4) an opportunistic routing implementation method based on a close community and a decision tree algorithm;

the intimacy weight calculation method (1) is characterized in that: because node communication often has certain regularity and social attributes, based on historical node communication records, the intimacy degree between nodes is calculated by using a newly defined intimacy degree function and is used as the weight of the intimacy degree function, and an undirected weighted communication graph is constructed so as to analyze and mine community characteristic information between the nodes;

the method for dividing the sub-communities based on the spectral clustering is characterized in that: because nodes in the same community often meet the ground in the opportunistic network and are convenient for message forwarding, a communication graph is divided into a plurality of subgraphs based on spectral clustering, a plurality of sub-communities are constructed, when a message is forwarded to a certain node, the message can be forwarded to other nodes in the community where the node is located, and the other nodes are copied and forwarded in the community, so that the message transmission efficiency can be improved, and the message can be quickly transmitted to a target node;

the characteristics of the (3) messenger node identification model based on the C4.5 algorithm are as follows: the message transmission of the nodes in the same community is rapid and reliable, and when the message is transmitted across communities, messenger nodes which are free in a plurality of sub-communities need to be searched, so that a model capable of identifying the messenger nodes is constructed by adopting a C4.5 algorithm by acquiring the characteristics of the activity, the centrality, the recency, the reliability, the free cache space, the transmission speed, the transmission range and the residual energy attribute of the nodes, and the messenger nodes are determined by utilizing the model;

the opportunistic routing implementation method based on the intimate community and the decision tree algorithm is characterized in that: based on the divided sub-communities and the trained decision tree model, when a source node and a destination node are in the same community, the message is copied and forwarded only in the sub-communities, when the source node and the destination node are in different community, the messenger node is identified by using the decision tree model, the message is transmitted to the destination community through the messenger node, and the node in the destination community copies and forwards the message and finally transmits the message to the destination node.

Images