CN107318142B - A Distributed Routing Method Between Clusters of Wireless Sensor Networks - Google Patents

Abstract

The invention discloses a distributed routing method between clusters of a wireless sensor network, which belongs to the field of wireless sensor networks and effectively reduces the interference of data transmission between cluster heads of a large-scale wireless sensor network. The present invention includes exchanging the logical connection relationship and load information between the cluster heads through the Hello message, and recording it in the neighbor table; the cluster head first calculates the data transmission of the cluster head according to the number of the parent cluster heads and the traffic load of the neighboring cluster heads The interference factor of the data transmission of its neighbor cluster head; the sub-cluster head calculates the probability of each parent cluster head undertaking the next hop data transmission based on the interference factor of the parent cluster head. The invention can effectively reduce the mutual interference between the cluster heads in the data transmission process, and improve the data transmission efficiency of the network.

Description

A Distributed Routing Method Between Clusters of Wireless Sensor Networks

technical field

The invention belongs to the field of wireless sensor networks, and in particular relates to a distributed routing method among wireless sensor network clusters.

Background technique

The clustering topology is easy to manage, beneficial to the application of distributed routing algorithms, has good scalability, and is suitable for large-scale wireless sensor network applications. Clustering routing protocols usually divide the network into clusters, each cluster consists of a cluster head and multiple cluster members, the cluster head manages or controls the member nodes in the entire cluster, and data is transmitted to the sink node through multiple hops between cluster heads. Because the sensor nodes are prone to failure, the cluster structure has bottlenecks, and the high load of cluster heads increases the possibility of network segmentation, this requires the routing algorithm to have a certain fault tolerance. At the same time, wireless signal interference and channel contention are also important factors that cannot be ignored in the process of clustering routing design.

For wireless sensor network cluster routing, many WSN cluster routing algorithms are designed around the generation of cluster heads, cluster formation and cluster data transmission. "Energy-aware wireless sensor network data collection protocol", Journal of Software, 2007, 18(5): 1092-1109, authors Liu Ming, Cao Jiannong, Chen Guihai, etc., disclosed the design of cluster head election based on the residual energy of the node itself and its neighbor nodes And the cluster construction scheme, by adjusting the coverage radius of the cluster head to ensure the connectivity of the subgraph formed by the cluster head, and then construct the aggregation tree to transmit data. However, when the network load is large, data transmission between different cluster members is prone to conflict, which reduces the efficiency of data collection by the cluster head, which easily leads to network congestion. "efficient routing algorithm based on unequal clustering and connected graph in wireless sensor networks", International Journal of Wireless Information Networks, 2016,23(2):141-150, authors Xia H, Zhang R, Yu J, disclosed that by adjusting sensor nodes The communication radius of the sensor network is clustered non-uniformly, and then the routing selection algorithm is designed by using the connected graph theory. However, when clustering only considers energy hole avoidance, the topology of the cluster network changes frequently in order to save energy, resulting in excessive cost of maintaining network stability and degrading network performance. The routing algorithm between cluster heads only uses graph theory to design data transmission routes between cluster heads, ignoring the information sharing of wireless sensor network protocol stack and the characteristics of sensor node data transmission, and the optimization effect is limited.

From the above prior art, it can be seen that the existing WSN cluster structure and routing methods have unbalanced energy consumption and unstable performance; how to use the distributed characteristics of wireless sensor networks to establish a more efficient heuristic Clustering and routing through interaction and information feedback, while reducing the interference of data transmission between nodes and ensuring the network operation cycle, improving cluster stability and network data transmission performance still needs further innovation.

Contents of the invention

1. Problems to be solved

Aiming at the problem of mutual interference between cluster heads of existing large-scale wireless sensor networks, the present invention provides a distributed routing method between cluster heads of wireless sensor networks, which can effectively reduce mutual interference between cluster heads during data transmission and alleviate heavy loads Reduce network congestion, balance network load, prolong network life time, suitable for large-scale wireless sensor network applications.

2. Technical solution

In order to solve the above problems, the present invention adopts the following technical solutions.

A distributed routing method between clusters in a wireless sensor network, including using the influence of data transmission of a cluster head on its neighboring cluster heads to define an interference factor as a basis for next hop selection.

Preferably, the following steps are included:

Step A, the cluster heads exchange each other's logical connection relationship, cluster head load prediction value and their own interference factors through Hello messages, and record them in their respective neighbor tables; Formed, or based on the distance difference between the cluster network and the sink node, the parent, child, and peer relationship between cluster heads;

Step B, update and maintain the interference factor of data transmission of cluster head i on the data transmission of neighboring cluster heads;

In step C, the lower network cluster head j determines the probability that each parent cluster head is the next hop based on the interference factor of each parent cluster head calculated in the above step B.

Step D, the lower network cluster head j uses the roulette method to select the next hop from the parent cluster head.

Preferably, the calculation formula of the cluster head i load prediction value in step A is as follows,

L _i , O _j represent the load prediction value of cluster head i and its sub-cluster head j respectively, P _j represents the parent cluster head set of cluster head j, C _i represents the sub-cluster head set of cluster head i, U _i is the cluster head The set of member nodes of the cluster where i belongs to, Indicates the mathematical expectation of the amount of data reported by member node j in the cluster with i as the cluster head; || indicates the number of elements in the set.

Preferably, in step B, the update and maintenance of the data transmission interference factor of cluster head i to the data transmission of neighboring cluster heads, the calculation formula is as follows,

The first item on the right calculates the degree of interference of cluster head i’s data transmission to all its parent cluster heads; the second item calculates the interference degree of cluster head i to its data transmission of all sub-cluster heads; the third item calculates the degree of interference of cluster head i to all parent cluster heads. Interference degree of layer neighbor cluster head data transmission;

P _i , P _k are the parent cluster head sets of cluster head i and k respectively, C _j is the sub-cluster head set of cluster head j, C _i is the sub-cluster head set of cluster head i, M _i is the communication radius of cluster head i The set of cluster heads at the same level within the range, L _k represents the load prediction value of cluster head k; || represents the number of elements in the set.

Preferably, in step C, the cluster head j of the lower layer network determines the probability that each parent cluster head is the next hop based on the interference factor of its parent cluster head, and the calculation method is as follows,

P _j represents the parent cluster head set of cluster head j, IF _j,i is the interference factor of cluster head i's parent cluster head i, IF _j,k is the interference factor of cluster head j's parent cluster head k; X _j is the cluster The number of neighbor cluster heads that head j has obtained the interference factor value through the Hello message, and the interference factor value IF _i of the cluster head i that has not obtained the interference factor is 0, and the probability of being selected as the next hop is || indicates the number of elements in the set.

3. Beneficial effects

Compared with the prior art, the beneficial effects of the present invention are:

(1) The present invention defines the interference factor of the sensor node, uses the intercluster routing method of the wireless sensor network based on the interference factor, effectively reduces the mutual interference between the cluster heads in the data transmission process, alleviates the network congestion degree under the heavy load situation, prolongs the network Time to live, suitable for large-scale wireless sensor network applications;

(2) The probabilistic routing selection method used in the present invention is based on the interference factor, by distributing selection probabilities for different next-hop routing nodes of the cluster head, while improving data transmission efficiency, it can balance the network load, and avoid the single cluster head from being burdened. Excessively large transmission tasks cause energy loss too fast, resulting in unbalanced network energy distribution and a decline in stability.

Description of drawings

Fig. 1 is the interference scene of the data transmission of cluster head i to all its parent cluster heads in the specific embodiment of the present invention;

Fig. 2 is the interference scene of cluster head i to its all sub-cluster head data transmission in the specific embodiment of the present invention;

Fig. 3 is the interference scene of cluster head i data transmission to the cluster head data transmission of the same layer in the specific embodiment of the present invention;

Fig. 4 is a wireless sensor network cluster network structure diagram of building and its cluster head update method in the specific embodiment of the present invention;

A-K in the figure represents each cluster; the solid line is the first-layer cluster network; the first dotted line inside the solid line close to A and B is the zero-level cluster network; the second dotted line outside the solid line close to D, E, and F is Layer 2 cluster network; outside the second dotted line is the layer 3 cluster network;

FIG. 5 is a diagram of the communication relationship between clusters in the present invention, and the thickness of the arrows in the figure represents the probability of node traffic distribution.

In the figure, the thickness of the arrow represents the distribution probability of node traffic. According to the minimum interference factor path selection strategy proposed in the present invention, when the cluster head in cluster K selects the next hop, since the selection of the cluster head of cluster F will interfere with the inter-cluster data transmission of cluster network A, there is a high probability to select G instead of F. Similarly, when the cluster head in cluster network J selects the next hop, in order to avoid affecting the data transmission in cluster network I, it will prefer to choose E instead of D.

Detailed ways

The present invention will be described in detail below in conjunction with the accompanying drawings.

In wireless sensor networks, the state of nodes changes with time, which leads to changes in network topology. Especially in a densely distributed network of sensor nodes, ordinary nodes have limited storage and computing capabilities. Traditional sensor network routing protocols are used to centrally control route finding methods, that is, to collect information such as the entire network topology and link status, and calculate and maintain the entire route. Routing is obviously unreasonable, and the use of graph theory to construct routing has a large overhead. Therefore, it is a good choice to use hierarchical routing with good scalability and communication capabilities to play the role of energy-saving routing in wireless sensor networks.

The present invention will be further described below in conjunction with specific embodiments.

As shown in Figure 4, a multi-level cluster structure of a wireless sensor network, there are 11 cluster head structures from A to K, and the network is divided into 4 layers, which are the 0th layer cluster network, the 1st layer cluster network, and the 2nd layer cluster network. Cluster network and layer 3 cluster network; data is passed between clusters through the cluster head node until the sink node. In this cluster network, the logical connection relationship only exists between the cluster heads of adjacent layers, and there is no logical connection relationship between the cluster heads of the same layer network. Among the cluster heads with logical connection relationship, the cluster head in the upper network is called the parent cluster head, and the cluster head in the lower network is called the child cluster head.

Its construction method is mainly to complete the construction of multi-level clusters of the entire network from near to far, starting from the aggregation node;

Specifically include the following steps,

After the sensor nodes are deployed, the nodes regularly send Hello messages to collect the information of adjacent neighbor nodes, use the beacon node positioning algorithm based on RSSI ranging, and use the sink node as the beacon node to establish a relative coordinate system, and each node saves its coordinates information;

Step A, in the network initialization phase, divide the sensor nodes within the wireless communication radius of the sensor nodes into the 0th layer cluster network with the sink node as the center; divide all nodes in the network into cluster nodes according to whether the nodes have joined the cluster structure and a blank node, a cluster node is a node that has been added to the cluster structure, otherwise it is a blank node;

Step B, using the sensor node energy balance strategy method to construct the first layer cluster network;

Step B1, calculate the energy balance value of each sensor node in the 0th layer cluster network described in step A, and broadcast the cluster construction request message, the calculation method of the energy balance value of node i is as follows:

Indicates the initial energy of node i, J is the set of all neighbor nodes j of node i; || indicates the number of elements in the set; d(,) indicates the Euclidean distance between two nodes.

Step B2, after receiving the cluster construction messages of all neighbor nodes on the 0th layer, the blank node selects the neighbor node with the largest energy balance value as the cluster head, and requests to join the cluster structure by replying the cluster entry message;

Step B3, after receiving the cluster entry message from the blank node, the layer 0 node detects whether it is the target node, and if it is the target node, it broadcasts the clustering message to notify the cluster member nodes to enter the sleep state; if the node is in the cluster If the network construction time T expires and still does not receive the clustering request message of itself as the target node, then the node is a normal node and enters the sleep state; so far, the construction of the first layer cluster network is completed;

In this step, T takes 2 seconds, but T can be adjusted according to network scale, sensor distribution characteristics, sensor communication radius, etc.;

Step C, based on the cluster head capability value, sequentially establish the lower layer cluster network of the first layer cluster network, that is, establish the second, third,...N layer cluster network, N≥2; the specific steps are,

Step C1, each cluster member in the N-1 layer cluster network calculates its own cluster head capability value, and then broadcasts a cluster construction request message;

First, judge the stable value S _i of the cluster when node i assumes the role of cluster head, the calculation formula is as follows:

M _i is the set of neighbor nodes of node i in the cluster network of the same layer, r is the communication radius, d(,) represents the Euclidean distance between two nodes, and represent the remaining energy and initial energy of node j respectively;

Then, calculate the node cluster head capability value,

Z _i is the set of blank nodes within the communication radius of node i; is the mathematical expectation of the amount of data reported by each node in Z _i ; P _i is located within the communication radius of node i and belongs to the set of cluster heads in the N-2 layer cluster network; || indicates the number of elements in the set;

Step C2, after receiving the cluster construction message from the neighbor nodes on layer N-1, save the cluster head capability value in the neighbor table. After receiving the cluster construction messages of all upper neighbor cluster heads, select the cluster head with the largest cluster head capability value as its own cluster head, and reply the cluster entry message;

Step C3, after receiving the cluster entry message of the Nth layer node, the N-1 layer node detects whether it is a target node, if it is a target node, broadcasts a clustering message, and notifies the cluster member nodes to enter the sleep state; If the node has not received the clustering request message that itself is the target node after the time-out of the cluster network construction time T=2 seconds, then the node is a normal node and enters the sleep state; so far, the construction of the Nth layer cluster network is completed;

In this step, T takes 2 seconds, but T can be adjusted according to network scale, sensor distribution characteristics, sensor communication radius, etc.;

Step C4, repeat steps C1-C3 until the cluster network construction of the entire wireless sensor network is completed;

In this step, the cluster heads of layer N and the member nodes covered by these cluster heads constitute the cluster network of layer N.

The method for updating the cluster head in the multi-level cluster structure of the above-mentioned wireless sensor network specifically includes the following steps,

In step A, cluster head i uses the following formula to evaluate whether it can continue to serve as the cluster head according to the remaining energy, traffic load and other factors. If the following formula is not satisfied, go to step B for cluster update;

Indicates the remaining energy of the cluster head i, Indicates the average energy consumption of cluster head i in a round of data transmission, C _i is the set of sub-cluster heads of cluster head i, and U _i is the set of member nodes of the cluster where cluster head i is located; Taking the mathematical expectation of the amount of data reported by cluster member node j of cluster head i, L _i and L _j represent the mathematical expectation of the traffic load of cluster head i and its sub-cluster head j respectively;

Step B, the cluster head i notifies its neighbor nodes to enter the cluster head update state by broadcasting the cluster update message; then the neighbor node j according to the positions of both parties, the remaining energy of j and the neighbor cluster head information in the two adjacent layers of the level, Calculate its own cluster head capability value according to the following formula,

d(,) represents the Euclidean distance between cluster head i and node j, Represents the remaining energy of node j, C _j represents the set of cluster heads in the lower network within the communication radius of node j, P _j represents the set of cluster heads in the upper network within the communication radius of node j, P _k represents the set of cluster heads in the lower network within the communication radius of node j The parent cluster head set of the cluster head, J is the set of all neighbor nodes j of the cluster head i; || indicates the number of elements in the set;

Step C, the cluster head i selects the node with the largest cluster head capability value as the new cluster head, and then the cluster head i and the new cluster head broadcast the cluster head replacement message within their respective communication radius, and complete the role switching;

Step D, the node that has received the cluster head replacement message from cluster head i but has not received the cluster head replacement message from the new cluster head judges whether there are cluster head neighbors within its communication range according to the neighbor list, and if so, sends a report to the cluster head capability The neighbor cluster head with the largest value sends a request to join message, otherwise it enters the isolated node state. The isolated node selects the neighbor node with the largest remaining energy to relay data, and in the later stage of network operation, if it receives a new cluster head broadcast message, it joins the cluster with the largest cluster head capability value;

Step E, the isolated cluster caused by the cluster update performs steps B and C to update the cluster.

A distributed routing method among wireless sensor network clusters, obtained from the foregoing wireless sensor network multi-level cluster construction method to obtain a logically multi-connection virtual cluster head network for tree-like distributed routing. The present invention uses the interference factor as the basis for selecting the next hop node. The specific plan is as follows:

Step A, the cluster heads exchange each other's logical connection relationship, cluster head load prediction value and their own interference factors through Hello messages, and record them in their respective neighbor tables;

In the neighbor table, the parent, child, and peer relationships between cluster heads formed directly during the cluster network construction process are marked;

In this step, the calculation formula of the cluster head i load prediction value is as follows,

L _i , O _j represent the load prediction value of cluster head i and its sub-cluster head j respectively, P _j represents the parent cluster head set of cluster head j, C _i represents the sub-cluster head set of cluster head i, U _i is the cluster head The set of member nodes of the cluster where i belongs to, Indicates the mathematical expectation of the amount of data reported by member node j in the cluster with i as the cluster head; || indicates the number of elements in the set.

Step B, update and maintain the interference factor of data transmission of cluster head i on the data transmission of neighboring cluster heads;

In this step, the update and maintenance of the data transmission of cluster head i to the data transmission interference factor of neighboring cluster heads is determined, and the calculation formula is as follows,

The first item on the right calculates the interference degree of cluster head i to the data transmission of sub-cluster heads of all members in its parent cluster head set (Figure 1); the second item calculates the interference degree of cluster head i to the data transmission of all members of its sub-cluster heads degree (Figure 2); the third item calculates the interference degree of cluster head i to the data transmission of all neighbor cluster heads on the same layer (Figure 3);

P _i , P _k are the parent cluster head sets of cluster head i and k respectively, C _j is the sub-cluster head set of cluster head j, C _i is the sub-cluster head set of cluster head i, M _i is the communication radius of cluster head i The set of cluster heads at the same level within the range, L _k represents the load prediction value of cluster head k; || represents the number of elements in the set.

Step C, the cluster head j of the lower layer network determines the probability that each parent cluster head is the next hop based on the calculated interference factors of each parent cluster head;

The calculation method is as follows,

P _j represents the parent cluster head set of cluster head j, IF _j,i is the interference factor of cluster head i's parent cluster head i, IF _j,k is the interference factor of cluster head j's parent cluster head k; X _j is the cluster The number of neighbor cluster heads that head j has obtained the interference factor value through the Hello message, and the interference factor value IF _i of the cluster head i that has not obtained the interference factor is 0, and the probability of being selected as the next hop is || indicates the number of elements in the set.

The above descriptions are only examples of the present invention, and are not intended to limit the present invention. Various suitable modifications and variations are possible in the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (3)

1. distributed routing method between a kind of wireless sense network cluster characterized by comprising

Step A, between cluster head by the mutual logic connecting relation of Hello message exchange, cluster head load estimation value and itself Interference factor, and be recorded into respective neighbor table；

In neighbor table, mark what cluster network struction was directly formed in the process, or rely on range difference between cluster network and aggregation node Father, son, same layer relationship between the cluster head that isomery is built；

Step B updates and transmits the interference factor transmitted to its neighbours' cluster head data with maintenance cluster head i data；

Step C, lower layer network cluster head j determine each father's cluster using each father's cluster head interference factor calculated in above-mentioned steps B as foundation Head is the probability of next-hop；

Interference factor in the step B, calculation formula is as follows,

The right first item calculates annoyance level of the data transmission to its all father's cluster head of cluster head i；Section 2 calculates cluster head i to it The annoyance level of all submanifold head data transmission；Section 3 calculates the interference that cluster head i transmits all same layer neighbours cluster head data Degree；

P_i、P_kFather's cluster head set of respectively cluster head i and k, C_jFor the submanifold head set of cluster head j, C_iIndicate the submanifold head collection of cluster head i It closes, M_iFor same layer cluster head set within the scope of cluster head i communication radius, L_kIndicate the load estimation value of cluster head k；| | indicate member in set The number of element.

2. distributed routing method between a kind of wireless sense network cluster according to claim 1, it is characterised in that: in step A The calculation formula of cluster head i load estimation value is as follows,

L_i、O_jRespectively indicate the load estimation value of cluster head i and its submanifold head j, P_jIndicate father's cluster head set of cluster head j, C_iIndicate cluster The submanifold head set of head i, U_iThe member node set of cluster where cluster head i,It indicates using i as member node j in the cluster of cluster head The mathematic expectaion of reported data amount；| | indicate the number of element in set.

3. distributed routing method between a kind of wireless sense network cluster according to claim 1, it is characterised in that: in step C, Lower layer network cluster head j determines that each father's cluster head is the probability of next-hop, calculation method is such as using his father's cluster head interference factor as foundation Under,

P_jIndicate father's cluster head set of cluster head j, IF_j,iFor the interference factor of father's cluster head i of cluster head j, IF_j,kFor father's cluster head of cluster head j The interference factor of k；X_jNeighbours' cluster head quantity of interference factor value has been obtained by Hello message for cluster head j, have not been obtained interference because The cluster head i interference factor value IF of son_iIt is 0, and the probability for being selected as next-hop is| | indicate the number of element in set.