CN110662182B - Clustering method, device and equipment suitable for high-dynamic large-scale Internet of vehicles - Google Patents

Abstract

Embodiments of the present application provide a clustering method, device, and device suitable for high-dynamic large-scale Internet of Vehicles. The method includes: a first node receives a communication message sent by a second node; the first node is updated according to its own The information of all neighboring nodes in the neighbor table determines all the first stable nodes; the first node calculates the cluster head cost of the first node according to the node information of all the first stable nodes; if the first node is a cluster The first node, and according to the cluster head cost of the first node, when it is determined that the first node meets the preset conditions for intra-cluster switching or the preset conditions for switching between clusters, the first node will Disband the current cluster directly or select a quasi-cluster head to form a new cluster. The method provided by the embodiment of the present application can overcome the problems of poor cluster structure stability, uneven cluster distribution, high clustering overhead, and low communication reliability between nodes caused by the existing clustering method.

Description

Clustering method, device and equipment suitable for high dynamic large-scale vehicle networking

technical field

The embodiments of the present application relate to the technical field of high-dynamic large-scale wireless ad hoc networks, and in particular, to a clustering method, apparatus, and device suitable for high-dynamic large-scale vehicle networking.

Background technique

For large-scale and highly dynamic networks, flat network (distributed structure) will cause serious hidden terminal nodes and channel contention problems. Since there is no central unit as the coordinator, the probability of packet collision will increase significantly, which will lead to increased packet loss rate and transmission delay. This adverse effect is exacerbated when the network density is higher. In this case, an infrastructure-based network (centralized structure) has great advantages over a flat network because the infrastructure (Access Point, AP, Access Point or Road Side Unit, RSU, roadside unit) can make optimal scheduling of channel access and distribution of network resources in a relatively simple manner. However, this requires a certain amount of infrastructure to be applied within the intended coverage area, which will lead to increased economic and infrastructure installation costs. To realize the advantages of infrastructure-based networks, clustering can be used as an alternative technique to generate hierarchical network topologies.

Existing clustering algorithms use a variety of metrics to design clustering algorithms, such as location, speed, direction, link lifetime, node connectivity, relative destination, final destination, communication range, relative mobility, Link quality, vehicle density, radio power, etc. In the Internet of Vehicles, the clustering algorithm is the purpose of the clustering algorithm to optimize certain realization goals, such as cluster stability, connectivity, speed of cluster formation, and minimizing overhead. One of the most important goals is to provide a good quality of experience for security and emergency services, which is closely related to good network connectivity, reliability of communication, and upper bound on maximum delay. Usually in a clustering algorithm, a variety of metrics are used to cluster nodes, and most of the clustering algorithms are aimed at increasing the stability and survival time of the cluster structure. Generally, the clustering process can be divided into three parts: cluster head selection, cluster formation and cluster maintenance. Cluster head selection allows nodes to select a CH in a distributed or centralized manner. The CH is mainly used to manage the nodes in the cluster and maintain the cluster structure of the cluster. The cluster formation process is mainly to establish the communication link between CH and CMs. Usually a stable cluster requires stable links between CHs and CMs. However, due to the dynamic nature of the network, these independent links may arise and fail unpredictably, making it difficult to establish and maintain communications between high-speed mobile nodes. The cluster maintenance process mainly solves the problem of cluster reformation and nodes rejoining the cluster. How a CH is chosen and how nodes form a particular cluster has a large impact on the stability of the cluster.

Although clustering can bring great advantages, clustering also faces some important challenges such as: node mobility, additional overhead of cluster formation and maintenance, as well as channel fading, signal occlusion, etc. Among them, the most challenging problem of clustering mobile nodes is the maintenance of clusters during node movement. Due to the high mobility of nodes, frequent changes in topology, and the fragile and time-varying nature of wireless channels, the communication link between nodes will break frequently in succession, so clustering algorithms should be able to detect and react to topology changes to maintain appropriate cluster structure. In a dynamic network environment, cluster reconfiguration and cluster head changes are unavoidable, and the process of re-clustering needs to be started periodically in the network, which usually leads to a less stable cluster structure. Therefore, we should try to design a clustering algorithm with fewer cluster head changes, which can improve the stability of the cluster structure and support reliable communication between nodes. In addition, it is also required that the algorithm can converge quickly, so that all nodes can join the network as quickly as possible, and minimize the control overhead and time overhead brought by the clustering process as much as possible.

SUMMARY OF THE INVENTION

The embodiments of the present application provide a clustering method, device and equipment suitable for high-dynamic large-scale IoV, so as to overcome the inability of existing clustering methods suitable for high-dynamic large-scale IoV to solve the problem of poor cluster structure stability and uneven cluster distribution , the clustering overhead is high, and the communication reliability between nodes is not high.

In the first aspect, the embodiments of the present application provide a clustering method suitable for high-dynamic and large-scale Internet of Vehicles, including:

The first node receives the communication message sent by the second node, and the first node updates the communication message to the neighbor table of the first node;

The first node determines all stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node are the updated stable neighbor nodes. Nodes that are mutually stable neighbors with the first node in the neighbor table of the first node;

The first node calculates the cluster head cost of the first node according to the node information of all stable neighbor nodes of the first node;

If the first node is the cluster head node, and according to the cluster head cost of the first node, it is determined that the first node meets the preset conditions for intra-cluster head switching or the preset conditions for inter-cluster head switching , then the first node determines a cluster head node to be determined, and the first node dissolves the cluster where the first node is located, wherein a new cluster is established when the cluster head node to be determined satisfies the preset conditions for the establishment of a new cluster , and when the intra-cluster head switches or the inter-cluster head switches, the cluster head that establishes a new cluster is the node with the smallest cluster head generation value within the distance threshold range;

If the first node is the cluster head node, and the sum of the number of cluster members in the cluster where the first node is located and the number of target unclustered nodes in the updated neighbor table of the first node is less than the preset cluster Dissolution scale threshold, the first node sends a message of disbanding the cluster to all cluster members in the cluster where the first node is located, and the target unclustered node is an undistributed node that is a stable neighbor to the first node. cluster node;

If the first node is a cluster member node, and according to the cluster head cost of the first node, it is determined that the first node and the cluster head nodes in the cluster where the first node is located do not satisfy the requirement that they are mutually stable neighbors. When the condition of distance or angle is satisfied, the first node changes the cluster head node corresponding to the first node;

If the first node is an unclustered node, and it is determined that the target cluster head node exists in the neighbor table of the first node, the first node sends an application join request to apply for joining the target cluster head node the cluster;

If the first node is an unclustered node, and it is confirmed that the target cluster head node does not exist in the neighbor table of the first node, it is determined whether the first node satisfies the new requirements according to the neighbor table of the first node. The preset condition for the establishment of the cluster, if the first node meets the preset condition for the establishment of the new cluster, the first node is used as the cluster head node of the new cluster.

In a second aspect, an embodiment of the present application provides a clustering device suitable for high-dynamic and large-scale Internet of Vehicles, including:

a neighbor table update module, configured to receive a communication message sent by the second node, and update the communication message to the neighbor table of the first node;

The stable neighbor node determination module is configured to determine all the stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node are the Nodes that are mutually stable neighbors with the first node in the updated neighbor table of the first node;

a cluster head cost calculation module, configured to calculate the cluster head cost of the first node according to the node information of all stable neighbor nodes of the first node;

A cluster head switching module, configured to determine that the first node complies with the preset conditions for intra-cluster switching or inter-cluster switching according to the cluster head cost of the first node when the first node is the cluster head When the preset condition of the first switch is used, a cluster head node to be determined is determined, and the first node dissolves the cluster where the first node is located, wherein a new cluster is established when the cluster head node to be determined satisfies the preset conditions for the establishment of a new cluster When the cluster head is switched within the cluster or the cluster head is switched between the clusters, the cluster head of the new cluster is the node with the smallest cluster head generation value within the distance threshold range;

A cluster disbanding module, configured to include the number of target unclustered nodes in the updated neighbor table of the first node when the first node is a cluster head node, and the number of cluster members of the cluster where the first node is located and the updated neighbor table of the first node When the sum is smaller than the preset cluster disbanding scale threshold, broadcast a message of disbanding the cluster to the first node, and the target unclustered node is an unclustered node that is a stable neighbor to the first node;

The cluster head change module is used to determine whether the first node is different from the cluster head node in the cluster where the first node is located according to the cluster head cost of the first node when the first node is a cluster member node. The first node changes the cluster head node corresponding to the first node when the condition of being a distance or an angle of mutually stable adjacent nodes is satisfied;

A cluster joining application module is used to send an application joining request to apply for joining the target cluster when the first node is an unclustered node and it is determined that the target cluster head node exists in the neighbor table of the first node The cluster where the first node is located;

The new cluster establishment module is used to determine the first node according to the neighbor table of the first node when the first node is an unclustered node and it is confirmed that the target cluster head node does not exist in the neighbor table of the first node. Whether the first node satisfies the preset condition for the establishment of a new cluster, and when the first node meets the preset condition for the establishment of the new cluster, the first node is used as the cluster head node of the new cluster.

In a third aspect, an embodiment of the present application provides a device for optimal configuration of water resources, including: at least one processor and a memory;

the memory stores computer-executable instructions;

The at least one processor executes the computer-executable instructions stored in the memory, so that the at least one processor executes the clustering method suitable for a high-dynamic large-scale Internet of Vehicles as described in the first aspect above.

In the clustering method, device, and device suitable for high-dynamic and large-scale vehicle networking provided by this embodiment, first, a first node receives a communication message sent by a second node, and the first node updates the communication message to the first node. In the neighbor table of the node; the first node determines all the stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node is a node that is a stable neighbor to the first node in the updated neighbor table of the first node; the first node calculates the first node according to the node information of all stable neighbor nodes of the first node. The cluster head cost of a node; if the first node is the cluster head node, and according to the cluster head cost of the first node, it is determined that the first node complies with the preset conditions for intra-cluster head switching or inter-cluster cluster head switching When the preset condition of the first switch is used, the first node determines a cluster head node to be determined, and the first node disbands the cluster where the first node is located, wherein the cluster head node to be determined satisfies the pre-determination for the establishment of a new cluster. When the conditions are set, a new cluster is established, and when the intra-cluster head is switched or the cluster head is switched between clusters, the cluster head of the new cluster is the node with the smallest cluster head generation value within the distance threshold; if the first node is the cluster head node, and the sum of the number of cluster members in the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node is less than the preset cluster dissolution scale threshold, then the The first node sends a message of disbanding the cluster to all cluster members in the cluster where the first node is located, and the target unclustered node is an unclustered node that is a stable neighbor to the first node; if the The first node is a cluster member node, and according to the cluster head cost of the first node, it is determined that the first node and the cluster head node in the cluster where the first node is located do not satisfy the distance or angle of mutually stable neighbor nodes When the conditions are met, the first node changes the cluster head node corresponding to the first node; if the first node is an unclustered node, and it is determined that the target cluster head node exists in the neighbor table of the first node, Then the first node sends an application join request to apply for joining the cluster where the target cluster head node is located; if the first node is an unclustered node, and confirms that there is no target in the neighbor table of the first node The cluster head node, according to the neighbor table of the first node, to determine whether the first node meets the preset conditions for the establishment of a new cluster, and if the first node meets the preset conditions for the establishment of the new cluster, then The first node is used as the cluster head node of the new cluster, thereby improving the connectivity and stability of the cluster structure. Due to the improvement of stability, switching time and times are avoided, thereby saving time and resources, and solving the problem of poor cluster structure stability. The cluster distribution is uneven, the clustering overhead is high, and the communication reliability between nodes is not high.

Description of drawings

In order to more clearly illustrate the embodiments of the present application or the technical solutions in the prior art, the following will briefly introduce the accompanying drawings used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description These are some embodiments of the present application, and for those of ordinary skill in the art, other drawings can also be obtained from these drawings without any creative effort.

1 is a schematic flowchart of a clustering method suitable for high dynamic large-scale Internet of Vehicles provided by an embodiment of the present application;

FIG. 2 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale Internet of Vehicles provided by yet another embodiment of the present application;

3 is a schematic flowchart of a clustering method suitable for highly dynamic large-scale Internet of Vehicles provided by another embodiment of the present application;

4 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale Internet of Vehicles provided by another embodiment of the present application;

5 is a schematic structural diagram of a clustering device suitable for a high-dynamic large-scale Internet of Vehicles provided by an embodiment of the present application;

FIG. 6 is a schematic structural diagram of a clustering device suitable for a high-dynamic large-scale Internet of Vehicles provided by an embodiment of the present application.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present application clearer, the technical solutions in the embodiments of the present application will be described clearly and completely below with reference to the drawings in the embodiments of the present application. Obviously, the described embodiments It is a part of the embodiments of the present application, but not all of the embodiments. Based on the embodiments in the present application, all other embodiments obtained by those of ordinary skill in the art without creative work fall within the protection scope of the present application.

The terms "first", "second", "third", "fourth", etc. (if any) in the description and claims of this application and the above-mentioned drawings are used to distinguish similar objects and are not necessarily used to Describe a particular order or sequence. It is to be understood that the data so used are interchangeable under appropriate circumstances so that the embodiments of the application described herein, for example, can be implemented in sequences other than those illustrated or described herein. Furthermore, the terms "comprising" and "having" and any variations thereof, are intended to cover non-exclusive inclusion, for example, a process, method, system, product or device comprising a series of steps or units is not necessarily limited to those expressly listed Rather, those steps or units may include other steps or units not expressly listed or inherent to these processes, methods, products or devices.

The embodiment of the present application provides a clustering method suitable for high-dynamic and large-scale IoV. In order to solve the above problems, a variety of clustering metrics are comprehensively considered, and factors such as direction, distance, speed, and connection time are used when clusters are formed. , so that only nodes with similar moving directions, distances less than the threshold, and stable connection time greater than the threshold will be divided into a cluster, avoiding the situation where nodes with short connection time are added to the cluster and then immediately leave the cluster, and the distance threshold is limited. To a certain extent, it can maintain the validity of the link, make the clustering algorithm suitable for the complex and changeable wireless channel environment, and improve the connectivity and stability of the clustering structure.

FIG. 1 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale Internet of Vehicles provided by an embodiment of the present application. The execution body of this embodiment may be a device or equipment serving as a first node, and the execution body of this embodiment is not described here. Do limit.

Referring to Fig. 1, the described clustering method suitable for high dynamic large-scale Internet of Vehicles includes:

S101. A first node receives a communication message sent by a second node, and the first node updates the communication message to a neighbor table of the first node, where the neighbor table includes at least one node corresponding to the neighbor table The nodes are the node information of each other's neighbor nodes.

In this embodiment, both the first node and the second node may be any node of the mobile node in the network formed by the Internet of Vehicles. For example, both the first node and the second node may be vehicle nodes, and the first node may work in the following Any state: Undecided Node (UN): the initial state of all nodes, indicating that the node does not belong to any cluster and has not successfully joined any cluster; Cluster Member (CM): has joined a cluster In the cluster, and can communicate directly with the cluster head, any node belongs to only one cluster; Cluster Head state (Cluster Head, CH): The manager of the cluster can communicate with all the cluster members in the cluster in one hop . Therefore, the first node may be any one of a cluster head node, a cluster member node, and an unclustered node.

Wherein, the first node continuously broadcasts messages periodically, and also continuously receives messages broadcasted by other nodes, that is, communication messages. Each node has its own neighbor table. The neighbor table may be empty or may store information about nodes that are neighbors to itself. If the first node receives the communication message sent by the second node, it indicates that the first node If a node and the second node are adjacent nodes to each other, the node information of the second node is added or updated to the neighbor table of the first node. Specifically, when the first node periodically detects its own neighbor table, it updates and deletes invalid neighbor table entries. If the first node finds that it has not received any message from the second node for three consecutive HELLO period intervals, the first node will consider that the second node and itself are no longer neighbors, and will delete the second node from the neighbor table. related articles.

S102. The first node determines all first stable nodes according to the node information of all neighboring nodes in the updated neighbor table of the first node, where the first stable node is the updated neighbor table of the first node A node that is mutually stable with the first node.

In this embodiment, in a cluster, it is stipulated that the UN node and the CH must satisfy the condition of being mutually stable neighbors when joining the cluster, and the CH and all CMs in this cluster must satisfy the direction and the direction in the mutually stable neighbors. There are two constraints on the distance, but there is an unconditional requirement between CM nodes in the same cluster. The definition of stable neighbor nodes is as follows: if the distance D _i, j between node i and node j is less than a certain threshold D _th , the relative movement direction |Δθ _i,j | between the two nodes is less than a certain threshold θ _th , the stable connection time SLT _i,j is greater than or equal to a certain threshold T _th , then node i and node j are stable neighbors to each other.

Wherein, D _th =DistanceThreshold=R*DistanceThresholdcoeff

R=TransmissonRange

V _th = Speed Threshold = 5

θ _th =Angle Threshold=π/2

T _th =Time Threshold=(RD _th )/V _th

Step S103, the first node calculates the cluster head cost of the first node according to the node information of all the first stable nodes.

Wherein, after the calculating the cluster head cost of the first node, the method further includes:

If the first node is the cluster head node, the first node obtains the number of cluster members of the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node . In this embodiment, the cluster head cost CL (Cost Level) is used to measure the gap between a node being selected as CH. The smaller the value is, the higher the qualification of the node to become CH is, the more capable it is to assume the role of CH. At the same time, it is selected as The greater the probability of CH. When choosing CH always choose the node with the smallest CL value.

Among them, the following table shows the messages transmitted between nodes during the clustering process. Except for the service data packets, other data packets are the clustering control data packets transmitted at the network layer.

S104. If the first node is a cluster head node, and according to the cluster head cost of the first node, determine that the first node complies with a preset condition for intra-cluster head switching or a preset condition for inter-cluster head switching condition, the first node determines a to-be-determined cluster head node, and the first node disbands the cluster where the first node is located, wherein a new cluster is established when the to-be-determined cluster head node satisfies the preset conditions for the establishment of a new cluster. When the cluster head is switched within the cluster or the cluster head is switched between the clusters, the cluster head of the new cluster is the node with the smallest cluster head generation value within the distance threshold range.

In this embodiment, the intra-cluster head handover refers to that when the CH is no longer an optimal CH, it will grant the role of the CH to a CM node in a local cluster. In order to avoid frequent cluster head switching, in this embodiment, the intra-cluster head switching is performed only when the CL value ranking of the CH of the current cluster is not within the top 1/4 range of the current cluster.

Among them, when a node joins a cluster or leaves a cluster, it will cause the change of the cluster size and the change of the CL value of CH in the ranking of the cluster. Therefore, when the cluster size changes, it is necessary to detect whether the cluster head switch within the cluster occurs. And even if the cluster size does not change, it may cause the CL value of CH to change in the ranking of the cluster. Therefore, in this embodiment, when the BEAT message arrives, the node is set to periodically detect whether the intra-cluster switch of the cluster head occurs.

Specifically, when detecting whether the intra-cluster head switch needs to be performed, it is first necessary to judge whether the cluster satisfies the condition of cluster suicide, that is, the sum of the current cluster size of CH and the number of UN nodes in its stable neighbors is less than half A cluster size threshold of 1/2*ClusterSizeThreshold (ie, the preset cluster size threshold). If the conditions for cluster suicide are met, CH dissolves the cluster. Otherwise, the CH will continue to judge whether to perform intra-cluster head handover. The CH node traverses all CM members in the neighbor table, obtains the CL value of the CM member, counts the number m of CM nodes whose CL value is smaller than its own, and records the CM member with the smallest CL value. If the following formula is satisfied, intra-cluster head switching occurs, that is, the preset condition for intra-cluster head switching is: m>*RankThresholdcoeff*CurrentClusterSize. Here RankThresholdcoeff=1/4.

The CM selected at this time with the smallest CL value becomes the quasi-CH (QCH). After that, the CH will change to the UN state, store the Id information of the QCH in the Id field of the target cluster head, and send a CH_HANDOVER message to broadcast the QCH information to the surrounding nodes. All CM members of the original cluster that receive the CH_HANDOVER message will change their status to UN and enter the process of initializing the UN node to join the cluster. For the QCH node, after receiving the CH_HANDOVER message, it changes its state to CH, and sends a CH_ANNOUNCE message, waiting for other nodes to join the cluster.

In addition, the switching of cluster heads between clusters can be considered as cluster fusion, and cluster fusion refers to the phenomenon that two clusters overlap to a large extent. When the first node meets the preset condition for switching between cluster heads among clusters, the CH will perform an operation of switching between cluster heads among clusters to cause two clusters to be merged into one cluster. Here, cluster fusion can be simply equivalent to switching between cluster heads. Nodes perform cluster head switching between clusters, which is the process of cluster fusion. If the CH node detected in the CH neighbor table and the node travel in the same direction and the two CHs are in a state of being close to each other, cluster fusion may occur. The mutual proximity here refers to when the detected CH node is in front of you and the driving speed is lower than yourself, or the detected CH node is behind you and the driving speed is higher than yourself, that is to say, when two CH nodes are adjacent nodes to each other And one CH may catch up with another CH. However, cluster fusion is only necessary when a CH node detects that it is traveling in the same direction as another CH node and the distance between them is less than a threshold. However, before performing cluster fusion, CH will first determine whether the conditions for cluster suicide are satisfied, and if the conditions for suicide are satisfied, the cluster will be dissolved and no cluster fusion will be performed. If the cluster suicide condition is not met, then the CH will select a node with the smallest CL value from the node sets in the two CHs and in the overlapping area of the two clusters. Each CH will traverse its own neighbor table, trying to find a node from the table that is less than Dth from both CHs and has the smallest CL value, and then compares this smallest CL value with the CL values of the two CHs to determine a node. The best quasi-CH (QCH) node. Since the nodes that satisfy the conditions must exist in the neighbor tables of the two CHs at the same time, the QCH nodes selected by the two CHs must be the same node.

If the QCH is one of the two CHs, the CH remains in the CH state, and the other CH changes to the UN state and sends a CH_DISSOLUTION message. If the QCH is a CM member of a certain CH, the CH changes to the UN state and sends a CH_HANDOVER message. At this time, the cluster fusion in this cluster is equivalent to the intra-cluster head handover. The other CH will change to the UN state and send the CH_DISSOLUTION message to dissolve the cluster. If the QCH is a UN node, then both CHs will change to the UN state and send the CH_DISSOLUTION message to dissolve the cluster.

Among them, cluster fusion occurs mainly in three cases:

1) If the QCH is one of the two CHs, the CH remains in the CH state, and the other CH changes to the UN state and sends a CH_DISSOLUTION message;

2) If the QCH is a CM member of a certain CH, the CH changes to the UN state and sends a CH_HANDOVER message. At this time, the cluster fusion in this cluster is equivalent to the intra-cluster head handover. The other CH will change to the UN state and send the CH_DISSOLUTION message to dissolve the cluster;

3) If the QCH is a UN node, then both CHs will become UN state and send the CH_DISSOLUTION message to dissolve the cluster.

In this embodiment, by updating and maintaining its own neighbor table, the first node further determines the first stable node in the neighbor table of the first node that is mutually stable with the first node, and then calculates the cluster of the first node. When the first node is the cluster head node, it is further determined whether the first node needs to be switched, that is, whether the first node complies with the preset conditions for intra-cluster switch head switching or the pre-set conditions for inter-cluster cluster head switching. If the conditions are met, the new cluster head node corresponding to the cluster where the first node is located is determined, and the new cluster head node is switched to the cluster head node of the cluster where the first node is located, thereby improving the clustering structure. Connectivity and stability, at the same time, due to the improvement of stability, it avoids switching time and times, thereby saving time and resources, solving the problem of poor cluster structure stability, uneven cluster distribution, high clustering overhead, and low communication reliability between nodes. The problem.

S105. If the first node is a cluster head node, and the sum of the number of cluster members in the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node is less than a predetermined number Set the threshold of cluster disbanding scale, then the first node sends a message of disbanding the cluster to all cluster members in the cluster where the first node is located, and the target non-clustered node is a stable neighbor node with the first node. Unclustered nodes. In practical applications, there are three situations of cluster disbanding, corresponding to three situations of cluster death: the first situation is the disbanding of small-scale clusters. If the first node is the cluster head node, the sum of the current cluster size of the CH and the number of UN nodes in the stable neighbors around the CH node is less than half of the cluster size threshold 1/2*ClusterSizeThreshold. At this time, cluster dissolution will occur. . The cluster death type of cluster dissolution due to the loss of members is cluster suicide (CD_Drain);

The second case is that the cluster in which the intra-cluster head switch occurs is disbanded. At this time, although the condition of cluster suicide is not met, the CL value of CH is not in the top 1/4 range in the current cluster, which means that the current CH is no longer the optimal CH. At this time, the cluster head switch in the cluster will occur, and the original cluster must be dissolved first when the cluster head switch is performed. The cluster death type of cluster dissolution due to member succession is cluster correction (CD_Succession).

The third case is cluster dissolution when cluster fusion occurs. Cluster fusion may occur when one CH detects the existence of another CH, that is, when the two CHs become one-hop neighbors. In order to avoid unnecessary cluster fusion as much as possible, cluster fusion does not necessarily occur even when two CH nodes are adjacent to each other. Cluster fusion occurs only when two CHs satisfy the two conditions of direction and distance in mutually stable neighbor nodes. At this time, the two clusters will merge into one cluster, and at least one cluster will be dissolved at this time, so cluster dissolution will occur. The cluster death type of the dissolved cluster due to cluster fusion is CD_Recombination.

S106. If the first node is a cluster member node, and according to the cluster head cost of the first node, it is determined that the first node and the cluster head node in the cluster where the first node is located do not satisfy each other as stable neighbors When the condition of the distance or angle of the nodes is satisfied, the first node changes the cluster head node corresponding to the first node.

In this embodiment, the process for the first node to change the cluster head node corresponding to the first node is similar to the process for the first node to apply for joining a new cluster.

Specifically, the first node changes the cluster head node corresponding to the first node, that is, the first node node leaves the cluster where the first node is located. Among them, the situation that the node leaves the cluster usually means that the CM node leaves the cluster. At this time, it can be divided into two situations: active leaving and passive leaving.

Actively leaving the cluster is usually aimed at the CM node, which means that when the CM node receives the HELLO message of its own CH, it detects that the CH and itself do not meet the direction or distance threshold conditions in the mutually stable neighbor nodes. At this time, the CM node will change its status to UN, and actively send a LEAVE message to the CH node to inform its CH. After the CH receives the LEAVE message from the CM node of the cluster, it will delete the CM node from the cluster member set ClusterMemberSet, and at the same time update the current cluster size of the cluster.

There are two cases when the CM node leaves the cluster passively: one is when it deletes the invalid neighbor table entity and finds that it has not received any messages from the CH node for three consecutive HELLO period intervals, which indicates that the link between the CH and the CM has invalid. In this case, the CM node will think that it has disconnected from the CH, and the CM node will still send a LEAVE message to inform its CH (because the CM node has not received the CH message, but the CH may still receive it. CM's message). Another possible situation is that the CM node receives the message from the CH but its own CH node is no longer in the CH state. For example, the CM node receives the JOIN message of its own CH. At this time, the CM node will not send a LEAVE message, it will directly change to the UN state, and enter the process of the UN node initializing and joining the cluster.

If the CH receives the message from the CM and finds that it and the CM members have not satisfied the direction or distance threshold condition in the mutually stable neighbor nodes. Or when deleting the invalid neighbor table entry, it is found that it has not received any message from the CM node for three consecutive HELLO period intervals. In both cases, the CH will consider that the CM has left the cluster. At this time, the CH node will delete the CM node from the ClusterMemberSet and update the current cluster size of the cluster.

S107. If the first node is an unclustered node, and it is determined that a target cluster head node exists in the neighbor table of the first node, the first node sends an application for joining request to apply for joining the target cluster The cluster where the first node is located;

S108. If the first node is an unclustered node, and it is confirmed that the target cluster head node does not exist in the neighbor table of the first node, determine whether the first node is not based on the neighbor table of the first node The preset conditions for the establishment of the new cluster are met, and if the first node meets the preset conditions for the establishment of the new cluster, the first node is used as the cluster head node of the new cluster.

Wherein, after determining, according to the neighbor table of the first node, whether the first node satisfies the preset condition for establishing a new cluster, the method further includes:

If the first node does not meet the preset conditions for the establishment of the new cluster, the first node broadcasts a beacon and waits to join the cluster where a neighboring node that is a stable neighbor to the first node is located; wherein, The preset conditions for the establishment of the new cluster are: the first node does not have any cluster head node within the distance threshold range, and all stable neighbor nodes of the first node in the updated neighbor table of the first node are included. The number of unclustered nodes is greater than the preset clustering threshold, and the first node has the smallest cluster head cost among the unclustered nodes among all the stable neighbor nodes.

In practical applications, the initial cluster formation process is as follows: at the initial stage of network establishment, all nodes are in the UN state (here, the node in the UN state is the first node that is an unclustered node), and the CL value of the node is 1, and all nodes will periodically broadcast HELLO messages at 100ms intervals. The HELLO message contains the current position, speed, direction, CL value, state and other information of the node. When a node broadcasts its own HELLO message, it also receives HELLO messages from other nodes.

Wherein, each node (that is, the first node, where the first node may be the second node, and the second node may also be the first node) will establish and maintain a neighbor table NeighborTable , and store and update the relevant information of the surrounding neighbor nodes according to the information in the received data packets. Each neighbor table entry will include the node's Id, network address (IP address), current position (in coordinate form), current speed (in coordinate form), current direction, current node state, node's cluster head Id, node target Id, CH The flag (whether it is CH), the current CL value, the current cluster size, the timestamp of the last time the node was received, and other information. Therefore, each node can continuously update the information of surrounding neighbor nodes through periodic HELLO messages.

After the nodes exchange information with each other for a period of time, they can calculate their own CL values according to the received data packets of the neighboring nodes. The node will first establish a stable neighbor node set StableNeighborSet, and then traverse all the entries in the neighbor table. For the node corresponding to each neighbor table entry, the node will determine whether it is its own stable neighbor node, and if so, add it to the StableNeighborSet. After traversing all neighbor table entries, if the set is empty, it means that there is no stable neighbor node, then the node modifies its CL value to 1. If it is not an empty node, it will calculate its own CL value according to the CL value calculation formula mentioned above. Before sending a new HELLO message, the node will fill in the updated position, speed, state, CL value and other information into the corresponding fields of the data packet, and then broadcast the latest information to the surrounding nodes.

In addition, according to the information in the neighbor table, the UN node will determine whether there are CH nodes around it that can be added. If there is no joinable CH node around the UN node, and the number of UN nodes that are stable neighbors with itself in the neighbor table is greater than ClusterSizeThreshold, and it has the smallest CL value among these UN nodes, the UN node will The status is changed to CH, and a CH_ANNOUNCE message is sent to announce the establishment of a new cluster.

In addition, the specific process for a node to join a cluster is as follows: the UN node will first try to find a joinable CH node from the neighbor table. If it exists, it will apply to join the cluster. If it does not exist, it will judge whether it can announce the establishment of a new cluster. Here, a joinable node means that the CH node and itself are stable neighbors to each other and the current cluster size is smaller than the upper limit of the cluster size. To this end, the UN node will establish a joinable CH set AvailableCHSet, and then traverse its neighbor table to check whether there is any joinable CH. If the node corresponding to the neighbor table entry is a CH, the current cluster size is smaller than the upper limit that can be accommodated, and the node is a stable neighbor with itself, this CH is added to the AvailableCHSet. After traversing all the entries, the node first determines whether the set is empty. If the set is empty and it does not meet the conditions of being declared as CH, it will continue to search for a suitable target CH in the neighbor table and try to join the network. If the UN node meets the conditions for declaring to be CH, it will change its state to CH and send a CH_ANNOUNCE message to announce the establishment of a new cluster. If there is only one joinable CH in the set, the node will set its own cluster head Id as the Id of this CH. If there are multiple such CHs, the UN node will calculate the stable connection time with the CHs that can be added, compare the stable connection time of the two, and select a CH with the longest stable connection time as its own target CH. and set its own cluster head Id to the Id of the target CH.

After determining the target CH, the UN node will send a JOIN message to request to join the cluster and start a timer. If the JOIN_ACK message from the target node is successfully received within the validity period, it means that the UN node has successfully joined the network. At this time, the UN node will change its state to the CM state, and change the cluster head Id to the Id of the target CH. If the JOIN_ACK message is not received within the validity period or the JOIN_NACK message is received within the validity period, it means that the UN node has not successfully joined the network, and the node will continue to search for a suitable target CH in the neighbor table and try to join the network.

In the clustering method suitable for the highly dynamic large-scale Internet of Vehicles provided by this embodiment, firstly the first node receives the communication message sent by the second node, and the first node updates the communication message to the neighbor table of the first node in; the first node determines all stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node are the updated Nodes that are stable neighbors with the first node in the neighbor table of the first node afterward; the first node calculates the cluster of the first node according to the node information of all stable neighbor nodes of the first node head cost; if the first node is a cluster head node, and according to the cluster head cost of the first node, it is determined that the first node complies with the preset conditions for intra-cluster head switching or the pre-condition for inter-cluster head switching When a condition is set, the first node determines a cluster head node to be determined, and the first node dissolves the cluster where the first node is located, wherein the cluster head node to be determined meets the preset conditions for the establishment of a new cluster. When a new cluster is created, and the intra-cluster head is switched or the cluster head is switched between clusters, the cluster head of the new cluster is the node with the smallest cluster head generation value within the distance threshold; if the first node is the cluster head node , and the sum of the number of cluster members of the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node is less than the preset cluster disbanding scale threshold, then the first node Send a message of disbanding the cluster to all cluster members in the cluster where the first node is located, and the target unclustered node is an unclustered node that is a stable neighbor to the first node; if the first node is A cluster member node, and according to the cluster head cost of the first node, when it is determined that the first node and the cluster head node in the cluster where the first node is located do not satisfy the condition of being a distance or angle of stable neighbor nodes to each other, The first node changes the cluster head node corresponding to the first node; if the first node is an unclustered node, and it is determined that the target cluster head node exists in the neighbor table of the first node, the first node A node sends an application join request to apply for joining the cluster where the target cluster head node is located; if the first node is an unclustered node and confirms that the target cluster head node does not exist in the neighbor table of the first node, Then, according to the neighbor table of the first node, it is determined whether the first node satisfies the preset conditions for the establishment of a new cluster, and if the first node meets the preset conditions for the establishment of the new cluster, the first node satisfies the preset conditions for the establishment of the new cluster. The node acts as the cluster head node of the new cluster, thereby improving the connectivity and stability of the cluster structure. At the same time, due to the improvement of stability, switching time and times are avoided, thereby saving time and resources, and solving the problem of poor cluster structure stability and poor cluster distribution. Evenly, the clustering overhead is large, and the communication reliability between nodes is not high.

In order to determine the first stable node that is mutually stable with the first node, FIG. 2 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale IoV provided by yet another embodiment of the present application. This embodiment is implemented in the above-mentioned implementation. On the basis of the example, for example, on the basis of the embodiment shown in FIG. 1 , the specific process of S102 is described in detail in this embodiment. The node information includes the position coordinates and velocity coordinates of the node; the first node determines all stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, including:

S201, for each adjacent node of all adjacent nodes in the updated neighbor table of the first node, determine the relative movement direction of the first node and the adjacent node according to the speed coordinates of the adjacent node;

S202. Determine the distance between the first node and the adjacent node according to the position coordinates of the adjacent node;

S203. If the relative movement direction of the first node and the adjacent node is less than or equal to a preset angle, and the distance of the adjacent node is less than or equal to the preset distance, then according to the position coordinate and velocity coordinate of the adjacent node , obtain the stable connection time between the first node and the adjacent node by calculating the preset first inequality;

S204. If the stable connection time is greater than or equal to a preset connection time, determine that the neighbor node is a stable neighbor node of the first node.

In this embodiment, the process of determining the first stable node that is mutually stable with the first node is: denoting the first node as node i, any neighbor node in the neighbor table of the first node Denoted as node j, traverse all adjacent nodes in the neighbor table of the first node, specifically: the stable connection time SLT _i,j between the node i and node j is defined as the time from the current moment to the time between the two nodes. When the distance is greater than D _th , the value of SLT _i,j can be calculated from the current velocity and position of the two nodes. Assuming that the speed and direction of the node remain unchanged in a short time, the position coordinates of node i are (P _i .x, P _i .y), and the velocity coordinates are (V _i .x, V _i .y); The position coordinates are (P _j .x, P _j .y), and the velocity coordinates are (V _j .x, V _j .y). If the distance between node i and node j is less than or equal to D _th , then:

[(P _i .x+V _i .x*t)-(P _j .x+V _j .x*t)] ² +[(P _i .y+V _i .y*t)-(P _j . y+V _j .y*t)] ² ≤D _th ²

[(P _i .xP _j .x)+(V _i .x*tV _j .x*t)] ² +[(P _i .yP _j .y)+(V _i .y*tV _j .y*t )] ² ≤D _th ²

Do the following variable substitution:

a=V _i .xV _j .x

b=P _i .xP _j .x

c=V _i .yV _j .y

d=P _i .yP _j .y

Then there are:

[b+at] ² +[d+ct] ² ≤D _th ²

It can be known from the definition that SLT _I,j = t _max , and the following formula is satisfied at this time:

[b+a*SLT _I,j ] ² +[d+c*SLT _I,j ] ² =D _th ²

Do the following variable substitution:

e=a ² +c ²

Solving the equation, the stable connection time between nodes i and j can be obtained as:

In order to calculate the cluster head cost of the first node, FIG. 3 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale Internet of Vehicles provided by another embodiment of the present application. On the basis of the above-mentioned embodiments, for example , on the basis of the embodiment shown in FIG. 1 , this embodiment describes the specific process of S103 in detail. The first node calculates the cluster head cost of the first node according to the node information of all the first stable neighbor nodes, including:

S301. The first node calculates, according to the node information of all stable neighbor nodes of the first node, the average speed of all stable neighbor nodes of the first node and the distance between the first node and the first node. Average distance of stable neighbors;

S302. The first node acquires the number of all stable neighbor nodes of the first node, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the current position behind the first node The number of stable neighbors of the first node of ;

S303. According to the average speed, average distance, the number of all first stable nodes, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the current position behind the first node The number of stable neighbor nodes of the first node, and the cluster head cost of the first node is obtained based on the preset cluster head cost formula.

In this embodiment, the first node is denoted as node i, wherein the calculation formula of the cluster head cost C _i of node i is as follows:

表示节点i的所有稳定邻节点的平均速度；V_max表示预定义的最大速度，设置为50m/s；

表示节点i与其所有稳定邻节点的平均距离，N_all表示节点i所有稳定邻节点的个数，N_front表示当前位置在节点i前方的稳定邻节点的个数，N_behind表示当前位置在节点i后方的稳定邻节点的个数，且有N_all＝N_front+N_behind，N_front-N_behind＝2*N_front-N_all。Among them, α, β, γ can be set to different values, but need to satisfy α+β+γ=1, where V _i represents the speed of node i;

Represents the average velocity of all stable neighbors of node i; _Vmax represents the predefined maximum velocity, which is set to 50m/s;

Represents the average distance between node i and all its stable neighbors, N _all represents the number of all stable neighbors of node i, N _front represents the number of stable neighbors whose current position is in front of node i, and N _behind represents the current position of node i The number of stable neighbors behind, and there are N _all =N _front +N _behind , N _front -N _behind =2*N _front -N _all .

It can be known from the above formula: when N _all is not 0, the value range of CL _i will be normalized to (0, 1). When N _all is 0, the denominator of the above formula is zero, so at this time we stipulate that when N _all is 0, the value of CL _i is 1. If the relative speed between node i and its stable neighbors is smaller, the distance is closer, the number of stable neighbors of the node is more and the distribution of stable neighbors before and after the node is more uniform, then the CL value of the node is smaller.

In order to realize the adaptive beacon mechanism, FIG. 4 is a schematic flowchart of a clustering method suitable for high-dynamic large-scale Internet of Vehicles provided by another embodiment of the present application. This embodiment is based on the above-mentioned embodiment, for example, in FIG. 1 -3 On the basis of any of the above embodiments, this embodiment describes in detail the specific process of the clustering method suitable for the high-dynamic large-scale Internet of Vehicles. The method also includes:

S401. When the first node is in an unclustered state, the first node broadcasts a beacon periodically at a first preset time interval;

S402. After the first node joins a cluster, the first node obtains the speed of the cluster head node of the cluster where the first node is located;

S403, the first node determines the beacon period for the first node to send the beacon according to the speed of the cluster head node of the cluster where the first node is located and a preset beacon period threshold table;

S404. The first node broadcasts a beacon according to the beacon period.

In this embodiment, when the network is initialized, all nodes are set to the UN state, so the nodes periodically broadcast HELLO messages at intervals of 100ms. But after the node joins the cluster and becomes a CM node, its beacon period is determined by the speed range of the CH. The greater the CH speed, the shorter the beacon period. In the present invention, 40m/s, 30m/s, 20m/s, and 10m/s are used as thresholds for dividing the beacon period, and five types of beacon periods are set. When the CH speed is greater than 40m/s, the nodes in the entire cluster send beacons at a cycle of 100ms; when the CH speed is less than or equal to 40m/s and greater than 30m/s, the nodes in the entire cluster send beacons at 200ms Periodically send beacons; when the CH speed is less than or equal to 30m/s and greater than 20m/s, the nodes in the entire cluster send beacons at a cycle of 400ms; when the CH speed is less than or equal to 20m/s and greater than 10m/ s, the nodes in the entire cluster send beacons with a cycle of 800ms; when the CH speed is less than or equal to 10m/s, the nodes in the entire cluster send beacons with a cycle of 1000ms.

In practical applications, the communication message sent by one node to another node can be any of the following: HELLO message, JOIN message, JOIN_(N)ACK message, CH_ANNOUNCE message, CH_HANDOVER message, CH_DISSOLUTION message, LEAVE message.

In the whole clustering process, each node needs to maintain and update its own state information in time. This work is mainly done through BEAT self-messages. The node will set a periodic timer, traverse its neighbor table at regular intervals, delete the invalid neighbor table entry, and then calculate its own CL value according to the existing and valid information in the neighbor table, and set the beacon message to send interval. If the node is CH, it will also judge whether to perform cluster suicide and whether to switch the cluster head. If the node is a CM, it will judge whether to change its own cluster head. If the node is UN, it will try to join a cluster or create a new cluster.

Among them, the process of processing various messages by a network node (which may be the first node or the second node) is: (the node mentioned below may be the first node)

1. The node receives the processing of the HELLO message

Regardless of the type of the message and who the source node and destination node of the message are, in this embodiment, as long as a message from a certain node is received, the information of the message sender will be recorded in the neighbor table. The receiving HELLO message is mainly divided into the following situations:

1) Update the content of the entry related to the sending node in the neighbor table.

2. The node receives the processing of the JOIN message

Receiving JOIN messages is mainly divided into the following situations:

1) If a CH node receives a JOIN message from a UN node, it needs to determine whether it and the UN node are mutually stable neighbors and whether it can accommodate the UN node. If the conditions are met, it will send a JOIN_ACK message and change its own cluster size. If the joining conditions are not met, send a JOIN_NACK message to reject the joining of the node;

2) If a CH node receives the JOIN message of the CM of this cluster, and the destination node of the message is not itself. At this time, CH will delete the CM from the ClusterMemberSet and update its own cluster size;

3) If a CM or UN node receives the JOIN message of the CH or the target CH, the CM will change to the UN state and enter the process of initializing the UN node to join the cluster, and the UN node will continue to maintain the UN state and reselect the target CH;

4) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

3. The node receives the processing of the JOIN_(N)ACK message

Receiving a JOIN_(N)ACK message is mainly divided into the following situations:

1) If a UN node does not receive the JOIN_ACK message of the target CH node within the validity period of the timer or receives the JOIN_NACK message of the target CH node within the validity period, the UN node will continue to maintain the UN state and enter the process of the UN node initially joining the cluster;

2) If a UN node receives the JOIN_ACK message of the target CH node within the validity period of the timer, the UN node will switch from the UN state to the CM state, and set the cluster head Id as the Id of the target CH.

3) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

4. The node receives the processing of the CH_ANNOUNCE message

Receiving CH_ANNOUNCE messages is mainly divided into the following situations:

1) If a CH node receives the CH_ANNOUNCE message of the CM node in the cluster, it will delete it to the CM node in the ClusterMemberSet and update its own cluster size;

2) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

5. The node receives the processing of the CH_HANDOVER message

Receiving CH_HANDOVER messages is mainly divided into the following situations:

1) If a CM node receives a CH_HANDOVER message whose destination node is itself, then the node will switch to the CH state and announce that it has become a CH;

2) If the destination node of the message is not itself, but the source node of the message is its own CH or target CH, the node will switch or continue to remain in the UN state, enter the UN node initialization and join the cluster process, and re-select the appropriate CH;

3) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

6. The node receives the processing of the CH_DISSOLUTION message

Receiving the CH_DISSOLUTION message is mainly divided into the following situations:

1) If a CM node receives the CH_DISSOLUTION message of the CH, then the node will switch to the UN state, enter the initialization process of the UN node to join the cluster, and re-select the appropriate CH;

2) If a UN node receives the CH_DISSOLUTION message of the target CH, then the node will continue to maintain the UN state, enter the UN node initialization and join the cluster process, and re-select the appropriate CH;

3) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

7. The node receives the processing of the LEAVE message

Receiving LEAVE messages is mainly divided into the following situations:

1) If a CH node receives the LEAVE message of the CM node in the cluster, it will delete the node from the ClusterMemberSet and update the current cluster size;

2) In other cases, no redundant processing is performed, and the content of the entry related to the sending node is simply updated in the neighbor table.

In the actual simulation process, the process of simulating this clustering algorithm in OMNeT++ is as follows: First, the simulation module and parameters are initialized in the network initialization function, and the self-message event is set. During the simulation time, if the node receives a message from the upper layer, it will encapsulate the message into a network layer data packet and send the encapsulated data packet to the MAC layer; if it receives a data packet from the lower layer, it will be based on The type of the message is processed differently; if a self-message is received (mainly implementing timing functions, such as HELLO message sending and periodic BEAT message sending), it will be processed according to the type of self-message. At the end of the simulation time, the receipts are collected and the relevant results are counted.

In order to realize the clustering method suitable for high-dynamic large-scale vehicle networking, this embodiment provides a clustering device suitable for high-dynamic large-scale vehicle networking. Referring to FIG. 5, FIG. 5 is a schematic structural diagram of a clustering device suitable for high-dynamic large-scale Internet of Vehicles provided by an embodiment of the application; the clustering device 50 suitable for high-dynamic large-scale Internet of Vehicles includes: a neighbor table update module 501 , for receiving the communication message sent by the second node, and updating the communication message to the neighbor table of the first node; the stable neighbor node determination module 502 is used for all neighbor nodes in the updated neighbor table of the first node according to the updated The node information of the first node is determined, and all the stable neighbor nodes of the first node are determined, and the stable neighbor nodes of the first node are the nodes in the updated neighbor table of the first node that are stable neighbors with the first node. ; the cluster head cost calculation module 503 is used to calculate the cluster head cost of the first node according to the node information of all stable neighbor nodes of the first node; the cluster head switching module 504 is used to calculate the cluster head cost of the first node is a cluster head node, and according to the cluster head cost of the first node, when it is determined that the first node complies with the preset conditions for intra-cluster switch head switching or the preset conditions for inter-cluster cluster head switching, then determine a to-be-determined The cluster head node, and the first node dissolves the cluster where the first node is located, wherein a new cluster is established when it is determined that the cluster head node satisfies the preset conditions for the establishment of a new cluster, and the intra-cluster cluster head switches or the inter-cluster cluster When the head is switched, the cluster head of a new cluster is the node with the smallest cluster head generation value within the distance threshold range; the cluster dissolution module 505 is used for the first node to be the cluster head node, and the first node When the sum of the number of cluster members of the cluster and the number of target unclustered nodes contained in the updated neighbor table of the first node is less than the preset cluster dissolution scale threshold, broadcast a message of cluster dissolution to the first node, The target unclustered node is an unclustered node that is a stable neighbor to the first node; the cluster head changing module 506 is used for the first node to be a cluster member node, and according to the first node The cluster head cost of the node, when it is determined that the first node and the cluster head node in the cluster where the first node is located do not satisfy the condition of being a distance or angle of stable neighbors to each other, the first node changes the first node. The cluster head node corresponding to the node; the joining cluster application module 507 is used to send an application joining request when the first node is an unclustered node and it is determined that the target cluster head node exists in the neighbor table of the first node, In order to apply for joining the cluster where the target cluster head node is located; the new cluster establishment module 508 is used to confirm that the first node is an unclustered node and confirm that the target cluster head node does not exist in the neighbor table of the first node When the first node meets the preset condition for the establishment of the new cluster, determine whether the first node meets the preset condition for the establishment of the new cluster according to the neighbor table of the first node, and the first node meets the preset condition for the establishment of the new cluster. A node acts as the cluster head node of the new cluster.

The apparatus provided in this embodiment can be used to implement the technical solutions of the foregoing method embodiments, and the implementation principles and technical effects thereof are similar, and details are not described herein again in this embodiment.

In a possible design, the apparatus further includes: a number acquisition module; the number acquisition module is configured to, after calculating the cluster head cost of the first node, when the first node is a cluster head node At the time, the number of cluster members of the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node are obtained.

In a possible design, the apparatus further includes: a broadcasting module; the broadcasting module is configured to determine whether the first node satisfies a preset condition for establishing a new cluster according to a neighbor table of the first node Afterwards, and when the first node does not meet the preset conditions for the establishment of the new cluster, broadcast a beacon, waiting to join the cluster where a neighboring node that is a neighboring node to the first node is located; wherein, the new The preset conditions for cluster establishment are: the first node does not have any cluster head node within the distance threshold range, and all stable neighbor nodes of the first node in the updated neighbor table of the first node are not clustered. The number of nodes is greater than the preset clustering threshold, and the first node has the smallest cluster head cost among the unclustered nodes among all the stable neighbor nodes.

In a possible design, the node information includes the position coordinates and velocity coordinates of the node; the stable neighbor node determination module is specifically used for:

For each neighbor node of all neighbor nodes in the updated neighbor table of the first node, determine the relative movement direction of the first node and the neighbor node according to the speed coordinates of the neighbor node; The position coordinates of the node to determine the distance between the first node and the adjacent node; if the relative movement direction of the first node and the adjacent node is less than or equal to the preset angle, and the distance between the adjacent nodes is less than or equal to is equal to the preset distance, then according to the position coordinates and velocity coordinates of the adjacent nodes, the stable connection time between the first node and the adjacent node is obtained by calculating the preset first inequality; if the stable connection time If it is greater than or equal to the preset connection time, it is determined that the neighbor node is a stable neighbor node of the first node.

In a possible design, the cluster head cost calculation module 403 is specifically used for:

According to the node information of all stable neighbor nodes of the first node, calculate the average speed of all stable neighbor nodes of the first node and the average distance between the first node and all stable neighbor nodes of the first node; Obtain the number of all stable neighbor nodes of the first node, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the stable neighbor nodes of the first node whose current position is behind the first node. The number of nodes; according to the average speed, average distance, the number of all first stable nodes, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the current position in the first node The number of stable neighbor nodes of the first node behind a node is based on a preset cluster head cost formula, and the cluster head cost of the first node is obtained.

In a possible design, the apparatus further includes: a beacon period update module; the beacon period update module is configured to: in a non-clustered state, the first node at a first preset time interval is a periodic broadcast beacon; after joining a cluster, the first node obtains the speed of the cluster head node of the cluster where the first node is located; according to the speed of the cluster head node of the cluster where the first node is located and the preset signal A beacon period threshold table is used to determine a beacon period during which the first node sends the beacon; the beacon is broadcast according to the beacon period.

In order to realize the clustering method suitable for high-dynamic large-scale vehicle networking, this embodiment provides a clustering device suitable for high-dynamic large-scale vehicle networking. FIG. 6 is a schematic structural diagram of a clustering suitable for a high-dynamic large-scale Internet of Vehicles provided by an embodiment of the present application. As shown in FIG. 6 , the clustering device 60 suitable for the high-dynamic large-scale Internet of Vehicles in this embodiment includes: a processor 601 and a memory 602; wherein, the memory 602 is used to store computer execution instructions; the processor 601 is used to execute The computer stored in the memory executes the instructions to implement the various steps performed in the above-described embodiments. For details, refer to the relevant descriptions in the foregoing method embodiments.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present application, but not to limit them; although the present application has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: The technical solutions described in the foregoing embodiments can still be modified, or some or all of the technical features thereof can be equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the embodiments of the present application. scope.

Claims (8)

1. a kind of clustering method suitable for high dynamic large-scale car networking, is characterized in that, comprises: The first node receives the communication message sent by the second node, and the first node updates the communication message to the neighbor table of the first node; The first node determines all stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node are the updated stable neighbor nodes. Nodes that are mutually stable neighbors with the first node in the neighbor table of the first node; The first node calculates the cluster head cost of the first node according to the node information of all stable neighbor nodes of the first node; If the first node is the cluster head node, and according to the cluster head cost of the first node, it is determined that the first node meets the preset conditions for intra-cluster head switching or the preset conditions for inter-cluster head switching , then the first node determines a cluster head node to be determined, and the first node dissolves the cluster where the first node is located, wherein a new cluster is established when the cluster head node to be determined satisfies the preset conditions for the establishment of a new cluster , and when the intra-cluster head switches or the inter-cluster head switches, the cluster head that establishes a new cluster is the node with the smallest cluster head generation value within the distance threshold range; If the first node is the cluster head node, and the sum of the number of cluster members in the cluster where the first node is located and the number of target unclustered nodes in the updated neighbor table of the first node is less than the preset cluster Dissolution scale threshold, the first node sends a message of disbanding the cluster to all cluster members in the cluster where the first node is located, and the target unclustered node is an undistributed node that is a stable neighbor to the first node. cluster node; If the first node is a cluster member node, and according to the cluster head cost of the first node, it is determined that the first node and the cluster head nodes in the cluster where the first node is located do not satisfy the requirement that they are mutually stable neighbors. When the condition of distance or angle is satisfied, the first node changes the cluster head node corresponding to the first node; If the first node is an unclustered node, and it is determined that the target cluster head node exists in the neighbor table of the first node, the first node sends an application join request to apply for joining the target cluster head node the cluster; If the first node is an unclustered node, and it is confirmed that the target cluster head node does not exist in the neighbor table of the first node, it is determined whether the first node satisfies the new requirements according to the neighbor table of the first node. The preset condition for the establishment of the cluster, if the first node meets the preset condition for the establishment of the new cluster, the first node is used as the cluster head node of the new cluster; Wherein, when the first node and the second node are adjacent nodes to each other, the first node updates the communication message to the neighbor table of the first node, including: updating the node information of the second node to the neighbor table of the first node; The node information includes the position coordinates and velocity coordinates of the node; correspondingly, the first node determines all stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node ,include: For each neighbor node of all neighbor nodes in the updated neighbor table of the first node, determine the relative movement direction of the first node and the neighbor node according to the speed coordinates of the neighbor node; Determine the distance between the first node and the adjacent node according to the position coordinates of the adjacent node; If the relative movement direction of the first node and the adjacent node is less than or equal to the preset angle, and the distance of the adjacent node is less than or equal to the preset distance, then according to the position coordinate and velocity coordinate of the adjacent node, pass Presetting the first inequality calculation to obtain the stable connection time between the first node and the adjacent node; If the stable connection time is greater than or equal to the preset connection time, determining that the neighbor node is a stable neighbor node of the first node; The calculating the cluster head cost of the first node includes: The first node calculates the average speed of all stable neighbors of the first node and the distance from the first node to all stable neighbors of the first node according to the node information of all stable neighbors of the first node. the average distance of nodes; The first node obtains the number of all stable neighbor nodes of the first node, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the number of the first node whose current position is behind the first node. The number of stable neighbors of a node; According to the average speed, average distance, the number of all first stable nodes, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the number of the first node whose current position is behind the first node The number of stable neighbor nodes of a node is based on a preset cluster head cost formula to obtain the cluster head cost of the first node; Wherein, the preset cluster head cost formula is:

Among them, i is the first node, CL _i is the cluster head cost of the first node, α, β, γ can be set to different values, but need to satisfy α+β+γ=1, where V _i represents the speed of node i;

Represents the average speed of all stable neighbors of node i; _Vmax represents the predefined maximum speed, which is set to 50m/s;

Represents the average distance between node i and all its stable neighbors, N _all represents the number of all stable neighbors of node i, N _front represents the number of stable neighbors whose current position is in front of node i, and N _behind represents the current position of node i The number of stable neighbors behind. 2. The method according to claim 1, wherein after the calculating the cluster head cost of the first node, the method further comprises: If the first node is the cluster head node, the first node obtains the number of cluster members of the cluster where the first node is located and the number of target unclustered nodes contained in the updated neighbor table of the first node . 3. The method according to claim 1, wherein after determining whether the first node satisfies a preset condition for establishing a new cluster according to the neighbor table of the first node, the method further comprises: If the first node does not meet the preset conditions for the establishment of the new cluster, the first node broadcasts a beacon and waits to join the cluster where a neighboring node that is a stable neighboring node to the first node is located; The preset conditions for the establishment of the new cluster are: the first node does not have any cluster head node within the distance threshold range, and all stable neighbors of the first node in the updated neighbor table of the first node The number of unclustered nodes in the node is greater than a preset clustering threshold, and the first node has the smallest cluster head cost among the unclustered nodes among all the stable neighbor nodes. 4. The method according to any one of claims 1-3, wherein the method further comprises: When the first node is in an unclustered state, the first node broadcasts a beacon periodically at a first preset time interval; After the first node joins a cluster, the first node obtains the speed of the cluster head node of the cluster where the first node is located; The first node determines the beacon period during which the first node sends the beacon according to the speed of the cluster head node of the cluster where the first node is located and a preset beacon period threshold table; The first node broadcasts a beacon according to the beacon period. 5. A clustering device suitable for high dynamic large-scale Internet of Vehicles, is characterized in that, comprising: a neighbor table update module, configured to receive a communication message sent by the second node, and update the communication message to the neighbor table of the first node; The stable neighbor node determination module is configured to determine all the stable neighbor nodes of the first node according to the node information of all neighbor nodes in the updated neighbor table of the first node, and the stable neighbor nodes of the first node are the Nodes that are mutually stable neighbors with the first node in the updated neighbor table of the first node; a cluster head cost calculation module, configured to calculate the cluster head cost of the first node according to the node information of all stable neighbor nodes of the first node; A cluster head switching module, configured to determine that the first node complies with the preset conditions for intra-cluster switching or inter-cluster switching according to the cluster head cost of the first node when the first node is the cluster head When the preset condition of the first switch is used, a cluster head node to be determined is determined, and the first node dissolves the cluster where the first node is located, wherein a new cluster is established when the cluster head node to be determined satisfies the preset conditions for the establishment of a new cluster When the cluster head is switched within the cluster or the cluster head is switched between the clusters, the cluster head of the new cluster is the node with the smallest cluster head generation value within the distance threshold range; A cluster disbanding module, configured to include the number of target unclustered nodes in the updated neighbor table of the first node when the first node is a cluster head node, and the number of cluster members of the cluster where the first node is located and the updated neighbor table of the first node When the sum is smaller than the preset cluster disbanding scale threshold, broadcast a message of disbanding the cluster to the first node, and the target unclustered node is an unclustered node that is a stable neighbor to the first node; The cluster head change module is used to determine whether the first node is different from the cluster head node in the cluster where the first node is located according to the cluster head cost of the first node when the first node is a cluster member node. The first node changes the cluster head node corresponding to the first node when the condition of being a distance or an angle of mutually stable adjacent nodes is satisfied; A cluster joining application module is used to send an application joining request to apply for joining the target cluster when the first node is an unclustered node and it is determined that the target cluster head node exists in the neighbor table of the first node The cluster where the first node is located; The new cluster establishment module is used to determine the first node according to the neighbor table of the first node when the first node is an unclustered node and it is confirmed that the target cluster head node does not exist in the neighbor table of the first node. Whether the first node satisfies the preset condition for the establishment of the new cluster, and when the first node meets the preset condition for the establishment of the new cluster, the first node is used as the cluster head node of the new cluster; Wherein, when the first node and the second node are adjacent nodes to each other, the neighbor table updating module is specifically used for: updating the node information of the second node to the neighbor table of the first node; The node information includes the position coordinates and velocity coordinates of the node; correspondingly, the stable neighbor node determination module is specifically used for: For each neighbor node of all neighbor nodes in the updated neighbor table of the first node, determine the relative movement direction of the first node and the neighbor node according to the speed coordinates of the neighbor node; Determine the distance between the first node and the adjacent node according to the position coordinates of the adjacent node; If the relative movement direction of the first node and the adjacent node is less than or equal to the preset angle, and the distance of the adjacent node is less than or equal to the preset distance, then according to the position coordinate and velocity coordinate of the adjacent node, pass Presetting the first inequality calculation to obtain the stable connection time between the first node and the adjacent node; If the stable connection time is greater than or equal to the preset connection time, determining that the neighbor node is a stable neighbor node of the first node; The cluster head cost calculation module is specifically configured to: according to the node information of all stable neighbor nodes of the first node, calculate the average speed of all stable neighbor nodes of the first node and the distance from the first node to the first node. The average distance of all stable neighbors of a node; The first node obtains the number of all stable neighbor nodes of the first node, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the number of the first node whose current position is behind the first node. The number of stable neighbors of a node; According to the average speed, average distance, the number of all first stable nodes, the number of stable neighbor nodes of the first node whose current position is in front of the first node, and the number of the first node whose current position is behind the first node The number of stable neighbor nodes of a node is based on a preset cluster head cost formula to obtain the cluster head cost of the first node; Wherein, the preset cluster head cost formula is:

Among them, i is the first node, CL _i is the cluster head cost of the first node, α, β, γ can be set to different values, but need to satisfy α+β+γ=1, where V _i represents the speed of node i;

Represents the average velocity of all stable neighbors of node i; _Vmax represents the predefined maximum velocity, which is set to 50m/s;

Represents the average distance between node i and all its stable neighbors, N _all represents the number of all stable neighbors of node i, N _front represents the number of stable neighbors whose current position is in front of node i, and N _behind represents the current position of node i The number of stable neighbors behind. 6. The device according to claim 5, wherein the device further comprises: a number acquisition module; The number acquisition module is configured to acquire the number of cluster members of the cluster where the first node is located and the update when the first node is a cluster head node after calculating the cluster head cost of the first node The neighbor table of the next first node contains the number of target unclustered nodes. 7. The apparatus according to claim 5, wherein the apparatus further comprises: a broadcasting module; The broadcast module is configured to determine whether the first node satisfies the preset condition for the establishment of a new cluster according to the neighbor table of the first node, and after the first node does not meet the condition for the establishment of the new cluster. When the preset condition is set, a beacon is broadcast, waiting to join the cluster where a neighbor node is mutually adjacent to the first node; The preset conditions for the establishment of the new cluster are: the first node does not have any cluster head node within the distance threshold range, and all stable neighbors of the first node in the updated neighbor table of the first node The number of unclustered nodes in the node is greater than a preset clustering threshold, and the first node has the smallest cluster head cost among the unclustered nodes among all the stable neighbor nodes. 8. A clustering device suitable for high dynamic large-scale Internet of Vehicles, characterized in that, comprising: at least one processor and a memory; the memory stores computer-executable instructions; The at least one processor executes the computer-executable instructions stored in the memory, so that the at least one processor executes the clustering method suitable for a high-dynamic large-scale Internet of Vehicles according to any one of claims 1 to 4.

Images