CN108418715B - Resource discovery method in wireless network virtualization environment - Google Patents

Abstract

The invention relates to the technical field of mobile communications, and in particular to a method for discovering resources in a wireless network virtualization environment, comprising: virtual network resources obtained by virtualizing underlying physical network resources, and storing the virtual network resources in a resource repository for resource discovery using the classification attribute hierarchical clustering method based on information entropy weighting to cluster virtual network resources to generate clustered virtual network resources, and the virtual network provider finds the virtual network resources required by users from the clustered virtual network resources; the present invention The qualitative analysis of virtual network resource characteristics is transformed into quantitative analysis, which can effectively reduce the resource discovery delay and improve the efficiency of virtual network configuration.

Description

Resource discovery method in wireless network virtualization environment

technical field

The present invention relates to the technical field of mobile communication, in particular to a method for discovering resources in a wireless network virtualization environment.

Background technique

After decades of development, wireless communication technology and network interconnection technology are becoming more and more mature, and the emergence of a large number of diversified mobile services has made great contributions to people's work and life. Wireless network has gradually become an important access form of the future Internet, but the existing network architecture model is a fixed design, only composed of the role of the Internet service provider, facing scalability, mobility, security, A series of problems such as service quality are prominent, and it is difficult to meet the current emerging high-quality, high-service and emerging applications. The academic circles call this series of problems that the current Internet is facing "ossification". In order to overcome the "rigidity" problem of the current Internet, wireless network virtualization technology is proposed as a new and effective technical solution.

The essence of wireless network virtualization is a resource sharing technology. It can abstract the physical network into a logical network through virtualization technology, and then decouple the complex and diverse network control functions from the hardware and extract them to the upper layer for unified coordination and management. Reduce network management and maintenance costs and improve network control and management efficiency. In a network virtualization environment, many virtual logical networks coexist on the same physical network, which are isolated from each other, independent of each other, and have complete and unique network service functions. The biggest difference between network virtualization and the current Internet is the role it plays in the business model. The current Internet is only composed of a single role, the Internet service provider (ISP). SP) and virtual network provider (Virtual network provider, VPN), different roles play different functions. The separation design mechanism of infrastructure and network service business roles in a network virtualization environment can enable a variety of heterogeneous virtual networks to share the underlying shared physical network resources, greatly reducing the maintenance and management costs of network infrastructure.

The virtual network configuration process in wireless network virtualization includes resource discovery, matching, mapping and allocation. Resource discovery is the first and indispensable step. Its main purpose is to enable VPN to find available network resources in the underlying physical infrastructure And determine the virtual network request (Virtual network request, VNR) to select the most suitable InP. Resource discovery includes two important processes: resource description and resource clustering; in wireless network virtualization environment, virtual resources need to be described in the form of attributes and functions. Resource clustering is to divide and group the network resources that have been described, using the clustering technology in the field of data mining.

Hierarchical clustering can obtain the internal characteristics of data at different levels. The structure of the network resource tree diagram generated by the hierarchical clustering results and the feature description of each layer can clearly and intuitively find the resources that VNP wants. There are also some methods in hierarchical clustering methods (such as reference: Guha, S, Rastogi, R, Kyuseok Shim. ROCK: a robustclustering algorithm for categorical attributes[J]. Information Systems, 2000, 25(5): 345 -366.) can cluster classification data, but there are still significant shortcomings, the amount of calculation is relatively large, the time complexity is high, each clustering operation needs to calculate the distance between all objects in each cluster, and a lot of time is consumed Above the operation that compares its size.

SUMMARY OF THE INVENTION

In view of the above problems, the present invention provides a resource discovery method in a wireless network virtualization environment, including:

Virtual network resources obtained by virtualizing underlying physical network resources, and storing virtual network resources in the resource repository of resource discovery;

The virtual network resources are clustered using the information entropy weighted classification attribute hierarchical clustering method to generate clustered virtual network resources. The virtual network provider finds the virtual network resources required by users from the clustered virtual network resources.

Preferably, the virtual network resource includes n objects, and each object includes m groups of attributes and attribute values of the attributes.

Preferably, the attributes include node type, operating system, virtual environment, source node, destination node, intermediate node, link protocol, link type, and interface type.

Preferably, the classification attribute hierarchical clustering method based on information entropy weighting includes:

S1, input the virtual network resource, build a tree diagram with all objects in the virtual network resource as the root node, let i=1;

S2. Calculate the similarity measure of each attribute, sort the similarity measure from high to low, and select the attribute with the highest similarity measure and its attribute value as the i-th layer of the dendrogram;

S3. Determine whether the objects of the virtual network resource all independently form a cluster or the attributes of the objects in the cluster with the highest similarity measure have the same attribute value. If so, complete the clustering and output the clustered virtual network resource, otherwise set i=i +1, go back to S2.

Preferably, the similarity measurement formula includes:

Among them, S _j represents the similarity measure of the attribute A _j , w _j represents the weight of the information entropy of the attribute A _j , r _j represents the number of times the attribute A _j appears in all objects of the virtual network resource, and p _jk represents the attribute of the attribute A _j The proportion of the value a _jk , r _jk represents the number of times the attribute value a _jk appears in all objects of the virtual network resource, and c _j represents that the attribute A _j has c _j attribute values.

Preferably, the weight w _j of the information entropy is expressed as:

Among them, H _j represents the information entropy of the attribute A _j , and m represents the number of attributes in the virtual network resource.

Preferably, the information entropy H _j of the virtual network resource A _j is expressed as:

Preferably, the proportion p _jk of the attribute value a _jk of the attribute A _j is expressed as:

Among them, n represents the number of virtual network resources.

Preferably, the virtual network resource that the virtual network provider finds from the clustered virtual network resources includes:

S11. The user initiates a resource request;

S12, determine whether there are attributes and attribute values required by the user in the repository, if not, end the query, otherwise go to S13;

S13, determine whether there is currently an object of the virtual resource type that meets the user's needs, and if there is an object of the virtual network resource type that meets the user's needs, accept the user's resource request and complete the query;

S14. If no object that satisfies the resource of the user is found after traversing all the branches of the multi-level attribute tree, end the query.

The present invention converts the qualitative analysis of the characteristics of virtual network resources into quantitative analysis, which can effectively reduce the time delay of resource discovery and improve the efficiency of virtual network configuration.

Description of drawings

1 is an architectural diagram of a resource discovery method in a wireless network virtualization environment of the present invention;

2 is a schematic diagram of virtual network resource description of the present invention;

Fig. 3 is the time delay comparison diagram of the resource discovery method of the present invention and the existing cobweb (cobweb) method;

FIG. 4 is an example diagram of the hierarchical clustering method of classification attributes based on multi-level information entropy weighting according to the present invention.

Detailed ways

The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present application.

The present invention provides a resource discovery method in a wireless network virtualization environment, including:

Virtual network resources obtained by virtualizing underlying physical network resources, and storing virtual network resources in the resource repository of resource discovery;

The virtual network resources are clustered using the information entropy weighted classification attribute hierarchical clustering method to generate clustered virtual network resources. The virtual network provider finds the virtual network resources required by users from the clustered virtual network resources.

The virtual network resource operation management process is shown in Figure 1. The infrastructure provider exposes, registers and registers virtual network resources into the resource discovery module, that is, stores the virtual resource description file of the virtual network in the resource repository, and the virtual network provider The resource discovery module performs discovery and matching to find the virtual network resource desired by the resource request.

In the resource discovery module, distributed storage is used to manage virtual network resources, infrastructure providers are divided into different management domains, and each management domain standardizes and standardizes the abstracted virtual network resources for the virtual network resource description scheme. , and finally form a virtual resource description document, and store these description documents in the external repository in the resource discovery module, and then complete the registration and release of the resource, and finally provide it to the user in the form of a service.

In the wireless network virtualization environment, the infrastructure provider is responsible for managing and providing various network resources. Their basic elements are nodes, links, interfaces and paths. According to the relevant theories of graph theory, the use of undirected weighted The graph G=(N, L) represents a network, where N represents the set of nodes, represented as N=(n ₁ , n ₂ ,...,n _i ,...); L represents the set of links, represented by is L=(l ₁ ,l ₂ ,...,l _j ,...); these network resources are divided into functional and non-functional resources according to attribute categories. The resource description used in the above scheme is the one with function Properties of the virtual network resource. A virtual network resource with functional attributes is a typical concept - the relationship between attributes. Figure 2 describes the network elements, attributes and the relationship between attributes and attributes of virtual network resources. For example, virtual network resources include nodes, Network elements such as paths, links, and interfaces, where network element nodes include attributes such as node type, operating system, and virtual environment.

Aiming at the wireless network environment, the present invention designs a hierarchical clustering algorithm based on information entropy weighted classification data for the virtual network resource clustering therein, including a resource processing module and a clustering operation module; wherein the resource processing module includes resource analysis and entropy Resource analysis mainly includes: classifying virtual network resources according to objects, and then classifying them according to their attributes; entropy weight mainly starts from the characteristics of virtual resources, examines the importance of attributes, and measures the weight of attributes with the weight of information entropy; The class operation module mainly designs a clustering criterion constructed by similarity measure for the virtual network resources processed by the resource processing module to perform the clustering operation.

In the wireless network virtualization environment, virtual network resources are composed of a series of basic network elements. The network elements include nodes, links, paths, and interfaces. These basic network elements contain various attributes and attribute values. Preferably, the attributes include nodes. Type, operating system, virtual environment, source node, destination node, intermediate node, link protocol, link type, interface type; assuming a virtual network resource, it has n objects and m attributes, and each attribute includes c _j attributes value, each object can have multiple attributes and multiple attribute values, such as one attribute value in one attribute and multiple attribute values in multiple attributes, the attributes and attribute values in this virtual network resource have weights; use O Represents a virtual network resource. If the virtual network resource includes n objects, the _n -th object is represented as On, which can be any one of the network elements of the virtual network resource. In this embodiment, the node is used as the object, and the m attributes and The representations of the c _j attribute values of the corresponding attributes are as follows:

O= _{ O ₁ ,O ₂ ,...,On },

A={A ₁ ,A ₂ ,...,A _m },

O represents the set of objects, O _i is the ith object in the virtual network resource, and i={1, 2, 3,...,n};

A represents a set of attributes, A _j is the jth attribute in the virtual network resource, and j={1,2,3,...,m};

Dom(A _j ) means that the j-th attribute A _j has c _j attribute values in total, wherein the k-th attribute value of the attribute A _j is denoted as a _jk , and let k={1,2,3,...,c _j } , then there are:

The proportion of attribute A _j is expressed as:

The proportion of the kth attribute value a _jk in the attribute A _j is expressed as:

r _j represents the number of times the attribute A _j appears in all objects of the virtual network resource, r _jk represents the number of times the attribute value a _jk appears in all the objects of the virtual network resource, and the proportion of the attribute A _j can also be expressed as:

In wireless network virtualization, the importance of each attribute of each virtual network resource is different. The present invention considers the importance of each attribute. The greater the importance, the smaller the information entropy, indicating that these objects in the data are The more concentrated it is, the more likely it is to be clustered into the same cluster.

The information entropy of the attribute A _j of the virtual network resource can be expressed as:

Important attributes should be given larger weights, and unimportant attributes should be given smaller weights; according to this principle, this patent uses a weighting method—entropy weight method.

In the process of data set clustering, the entropy weight method can weight the attributes of each object according to the information entropy of each object. Compared with the subjective weight method, it can more objectively and accurately reflect the weight of each index. The attribute A _j The weight of the information entropy is calculated as follows:

Clustering is an unsupervised learning process, which does not require sample data training. After designing a suitable similarity measurement method, the target data set can be clustered; the present invention proposes a new and For different similarity measurement methods of previous hierarchical clustering, the similarity measurement formula is:

Substituting the formulas of the weights w _j , p _jk , and r _jk of the information entropy into the above formula, we can get:

It can be known from the above formula that S _j is only related to n, m, c _j , r _j and r _jk , indicating that the metric for clustering is directly determined by the nature of the virtual network resource itself, that is, the object of clustering, the The attribute and the attribute value of the attribute are determined; S _j is the similarity measure value, based on this, the hierarchical clustering method is designed, and the objects in the virtual network resource are clustered by comparing its size.

Using the similarity measure as the clustering standard, and using the decision tree idea in supervised learning, a new hierarchical clustering method based on information entropy weighting is designed. The specific steps of the method are described as follows:

S1, input the virtual network resource, build a tree diagram with all objects in the virtual network resource as the root node, let i=1;

S2. Calculate the similarity measure of each attribute, sort the similarity measure from high to low, and select the attribute with the highest similarity measure and its attribute value as the i-th layer of the dendrogram;

S3. Determine whether the objects of the virtual network resource all independently form a cluster or the attributes of the objects in the cluster with the highest similarity measure have the same attribute value. If so, complete the clustering and output the clustered virtual network resource, otherwise set i=i +1, go back to S2.

The above-mentioned classification attribute hierarchical clustering method based on information entropy weighting classifies virtual network resources into multiple clusters, and its structural form is represented as a tree diagram. The finer the resources are divided, the more the number of clusters; the clusters of the next layer are nested in the clusters of the current layer, that is, the clusters of the current layer are clustered to form the clusters of the next layer, such as in a cluster. A certain cluster R1={{x1,x2},{x3},{x4,x5} contains another cluster R2={{x1,x2,x3},{x4,x5}}, then this is R2 nesting In R1, or R1 nests R2.

In this paper, the purity of the extrinsic method is used to measure the accuracy of the algorithm. Purity is a simple and effective evaluation method. It takes the data sample as the benchmark and compares the extrinsic method with the clustering to evaluate the clustering. , and its value is calculated for each cluster formed by clustering data objects. The number of objects in the cluster is divided by the number of objects in the total sample. The calculation of purity can be expressed as:

Among them, Λ represents the set of each cluster obtained from the clustering result, expressed as Λ={κ ₁ ,κ ₂ ,...,κ _q ,...}, κ _q represents the qth cluster, and q is the number of clusters ; C represents the set of attribute values, expressed as C={c ₁ , c ₂ , . . . , c _j }, for example, c _j means that attribute A _j has c _j attribute values.

For virtual network resource clustering, the virtual network resource clustering process includes two parts, as shown in Figure 3: Infrastructure providers virtualize and describe and disclose, register, and register the underlying physical network resources under their jurisdiction. In the resource storage library of the discovery module; the clustering method proposed by the present invention is used to perform a clustering operation on the virtual network resources, and the entire clustering operation is performed in the resource discovery module, and the finally generated clustered virtual network resources are stored in the resource storage. in the library. In the network virtualization environment, resource discovery is a continuous and continuous process. First, virtual network resources are described by resources, and then they are divided and grouped by clustering algorithm. Finally, according to the network resources requested by users, VNP is based on the first two steps in the resource discovery module. 's resource repository.

Since the method used in the present invention for clustering virtual network resources belongs to split-type hierarchical clustering, the generated clustering results are presented in the form of hierarchical, top-down dendrogram as shown in FIG. 4 , As shown in Figure 4, the number of objects in the virtual network resource is 7, which are Node1, Node2, Node3, Node4, Node5, Node6 and Node7. In this level where the attribute is the node type, the objects are classified according to the attribute value of the attribute. There are three clusters, that is, the cluster whose attribute value is composed of (Node1, Node2) is the switch, the attribute value that is composed of (Node3, Node4, Node5) is the routing cluster, and the attribute which is composed of (Node6, Node7) The value is the class cluster of the base station. For the class cluster composed of (Node3, Node4, Node5), it can also be classified according to the virtual environment, operating system and network protocol. As shown in Figure 4, the class cluster composed of (Node3) and A cluster consisting of (Node4, Node5).

If an object is classified into one category, it needs to be divided into 7 clusters. There is only one cluster in the 0th layer, which is the object of all virtual network resources. The first layer of virtual network resources is clustered into 3 clusters according to the node type. On the basis of the first layer, the second layer continues to cluster to form 5 clusters according to other attributes, and finally the third layer continues to cluster into 7 clusters on the basis of the second layer, that is, each object is a cluster. clustering.

The tree search method used for the corresponding search is a top-down query, and the process is as follows:

S11. The user initiates a resource request;

S12, determine whether there are attributes and attribute values required by the user in the repository, if not, end the query, otherwise go to S13;

S13, determine whether there is currently an object of the virtual resource type that meets the user's needs, and if there is an object of the virtual network resource type that meets the user's needs, accept the user's resource request and complete the query;

S14. If no object that satisfies the resource of the user is found after traversing all the branches of the multi-level attribute tree, end the query.

In order to verify the effectiveness of a network virtual resource hierarchical clustering method based on information entropy weighting proposed by the present invention in the resource discovery process in the wireless network virtualization environment, and use the similarity matching method to search for virtual network resources, the network node is used as the The virtual network resource search object, the search time is used to measure the effect of the resource discovery process, and finally the Cobweb method proposed by D. Fisher et al is used for comparison; Figure 3 shows that the method proposed by the present invention and the Cobweb method are applied to Comparison of the time delay for VNP to find the target resource in the process of resource discovery, it can be seen from the figure that the time for resource discovery is lower than that of Cobweb after using the method proposed by the present invention for clustering, and the method of the present invention can effectively reduce virtual The query time of network resources, thereby improving the efficiency of resource discovery.

Those of ordinary skill in the art can understand that all or part of the steps in the various methods of the above embodiments can be completed by instructing relevant hardware through a program, and the program can be stored in a computer-readable storage medium, and the storage medium can include: ROM, RAM, magnetic disk or optical disk, etc.

The above-mentioned embodiments further describe the purpose, technical solutions and advantages of the present invention in detail. It should be understood that the above-mentioned embodiments are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modification, equivalent replacement, improvement, etc. made to the present invention within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (5)

1. A resource discovery method in a wireless network virtualization environment, comprising: Virtualizing the underlying physical network resources to obtain virtual network resources, and storing the virtual network resources in a resource repository, where the virtual network resources include n objects, each object includes m groups of attributes and attribute values of the attributes, and the attributes include node types , operating system, virtual environment, source node, destination node, intermediate node, link protocol, link type, interface type; use the classification attribute hierarchical clustering method based on information entropy weighting to cluster virtual network resources to generate clusters Virtual network resources, including: S1, input the virtual network resource, build a tree diagram with all objects in the virtual network resource as the root node, let i=1; S2. Calculate the similarity measure of each attribute, and the similarity measure value is expressed as:

Sort the similarity measure from high to low, and select the attribute with the highest similarity measure and its attribute value as the i-th layer of the dendrogram; S3. Determine whether the objects of the virtual network resource all independently form a cluster or the attributes of the objects in the cluster with the highest similarity measure have the same attribute value. If so, complete the clustering and output the clustered virtual network resource, otherwise set i=i +1, return to S2; The virtual network provider finds the virtual network resources required by the user from the clustered virtual network resources; Among them, S _j represents the similarity measure of the attribute A _j , w _j represents the weight of the information entropy, r _j represents the number of times the attribute A _j appears in all objects of the virtual network resource, p _jk represents the attribute value a _jk of the attribute A _j , r _jk represents the number of times the attribute value a _jk appears in all objects of the virtual network resource, and c _j represents that the attribute A _j has c _j attribute values. 2. The resource discovery method in a wireless network virtualization environment according to claim 1, wherein the weight w _j of the information entropy is expressed as:

Among them, H _j represents the information entropy of the attribute A _j , and m represents the number of attributes in the virtual network resource. 3. The resource discovery method in a wireless network virtualization environment according to claim 2, wherein the information entropy H _j of the virtual network resource A _j is expressed as:

4. The resource discovery method in the wireless network virtualization environment according to claim 1, wherein the proportion p _jk of the attribute value a _jk of the attribute A _j is expressed as:

Among them, n represents the number of virtual network resources. 5. The resource discovery method in a wireless network virtualization environment according to claim 1, wherein the virtual network provider finding the virtual network resources required by the user from the clustered virtual network resources comprises: S11. The user initiates a resource request; S12, determine whether there are attributes and attribute values required by the user in the repository, if not, end the query, otherwise go to S13; S13, determine whether there is currently an object of the virtual resource type that meets the user's needs, and if there is an object of the virtual network resource type that meets the user's needs, accept the user's resource request and complete the query; S14. If no object that satisfies the resource of the user is found after traversing all the branches of the multi-level attribute tree, end the query.

Images