CN105050099B - Distributed wireless sensor network boundary node recognition methods - Google Patents

Abstract

The invention provides a distributed wireless sensor network boundary node identification method, the method utilizes DSCS technology to identify the boundary nodes in the sensor network, the method can be applied to homogeneous or different non-uniform wireless sensors with the same function, sensing and communication range network. The process of this method is as follows: (1) nodes autonomously collect neighbor information in the network; (2) each node establishes a Cartesian coordinate system with itself as the center and calculates the absolute angle of its neighbor nodes; (3) arranges neighbor nodes in ascending order of absolute angle ; (4) Use DSCS to identify border nodes. The invention solves the technical problem of low identification accuracy of traditional wireless sensor network boundary nodes, decomposes the problem of wireless sensor network boundary node identification into a sensor sector edge coverage problem of a node, effectively reduces the complexity of the algorithm, reduces the running time and The communication and energy consumption between nodes in the process of border node identification improves the identification accuracy.

Description

Boundary Node Identification Method for Distributed Wireless Sensor Networks

technical field

The invention relates to a method for identifying border nodes of a distributed wireless sensor network, belonging to the technical field of wireless sensor networks.

Background technique

Wireless sensor networks are widely used in combat area monitoring, environmental monitoring, dangerous event/area detection and health monitoring applications. The wireless sensor network is composed of many low-cost, multi-functional sensor nodes capable of short-distance wireless communication. Because wireless sensors can perform monitoring tasks in dangerous areas or areas that are difficult to reach, they have become a hot research topic at home and abroad. Wireless sensors can be randomly deployed through airborne platforms or guns, which is one of the biggest advantages different from traditional networks. However, its disadvantages are also obvious. After deployment, wireless sensor nodes are easily damaged by external forces. It is difficult to be replaced so that its life cycle is affected by the battery carried by the node itself. At the same time, the failure of the node due to external force and battery energy depletion is likely to cause coverage holes in wireless sensor networks. Therefore, coverage holes are indispensable in the research and application of wireless sensor networks. evasive question.

Aiming at the problem of coverage holes, some corresponding solutions are proposed in the current wireless sensor network research. However, the existing coverage hole identification methods have the problems of high requirements on the network node degree, high energy consumption in the identification process, and low identification accuracy. Most methods realize the recognition of coverage holes by identifying the boundary nodes around the coverage holes. The existing boundary node detection and recognition technologies are divided into three categories: methods based on computational geometry, based on statistics and based on topology. The existing border node identification methods have high algorithm complexity, are susceptible to failure due to the limitation of sensor deployment areas, and also have problems such as low border node identification accuracy, high energy consumption, and poor robustness.

Contents of the invention

In order to solve the deficiencies of the prior art, the present invention provides a distributed wireless sensor network boundary node identification method, which can accurately identify the wireless sensor network by using the idea of DSCS (Distributed Sector Cover Scanning, distributed sensing sector edge coverage scanning technology) In the boundary nodes, the recognition accuracy reaches more than 90%.

The technical scheme that the present invention adopts for solving its technical problem is: a kind of distributed wireless sensor network boundary node identification method is provided, comprising the following steps:

(1) Let the communication model of each node in the distributed wireless sensor network be a disc with the location of the node as the center and the communication coverage radius CR as the radius, and the node stores the information of the 1-hop neighbor nodes within its communication range Neighbor information; each node sends a request to its 1-hop neighbor node and exchanges 1-hop neighbor information to collect neighbor information of neighbor nodes within s hops, where s is 2 to 3; for each node in the wireless sensor network in turn Execute step (2) to step (5) to judge whether this node is a boundary node;

(2) Establish a Cartesian coordinate system with the current node _v1 as the center and the sensing coverage radius SR of node _v1 as the radius, and calculate the absolute angle of the neighbor nodes within s hops of node _v1 in the coordinate system. The range of the angle is [0 °, 360 °], and the definition of the absolute angle is: in the Cartesian coordinate system established with the node v ₁ as the center of the circle, the connection line between the node v ₁ and the neighbor node is along the counterclockwise direction and x The positive angle of the axis is the absolute angle of the neighbor node of v ₁ in the coordinate system centered on node v ₁ ;

(3) If the absolute angles of more than two neighbor nodes are the same, only keep the neighbor node closest to node _v1 ;

(4) Sort the neighbor nodes according to their absolute angle from small to large;

(5) Determine in turn whether the edge of each sensing sector of node _v1 is completely covered by the sensing area of the adjacent node of the sensing sector, wherein, with the current node _v1 as the center of the circle, node _v1 In a circle whose sensing coverage radius SR is the radius, the radius of the connection line between node v ₁ and neighbor node v _j , the radius of the connection line between node v ₁ and neighbor node v _k , and the arc enclosed by them The enclosed area is the sensing sector v _j v ₁ v _k , the arc is the edge of the sensing sector v _j v ₁ v _k , the node v _j and the node v _k are the sensing sector v _j v The adjacent nodes of ₁ v _k , if the edge is completely covered by the sensing areas of neighboring nodes v _j and v _k at the same time, then the edge of the sensing sector v _j v ₁ v _k is completely covered by its adjacent nodes; if there is If the edge of a sensing sector cannot be completely covered by its adjacent nodes, then node _v1 is a boundary node, otherwise node _v1 is not a boundary node.

In step (1), each node calculates the neighbor information of its neighbor nodes within s hops by the following formula:

Among them, v _i represents the current node, v _u represents the k-1 hop neighbors of v _i , Represents the k-hop neighbor node set of v _i , Represents the k-1 hop neighbor node set of v _i , Represents the 1-hop neighbor node set of v _u , k=2,...,s.

In step (1), the neighbor information of neighbor nodes within 2 hops is collected.

The beneficial effect that the present invention has based on its technical scheme is:

(1) The present invention decomposes the boundary node identification problem of the wireless sensor network into a sensor sector edge coverage problem of a node, which effectively reduces the complexity of the algorithm and saves running time. Traditional methods such as geometry and topology need to fully consider the node The multi-hop neighbor relationship, some algorithms can only accurately judge when it reaches 8 hops. In the ideal case, this method can even identify whether it is a border node with only 2 neighbor nodes. In the worst case, it needs to consider its 2-hop neighbor information. In addition, dividing the sensing area of the entire node into different sensing sectors effectively reduces the computational complexity;

(2) The identification of border nodes depends on the neighbor information stored by the node itself. The design method of the present invention reduces the algorithm complexity and running time, and the neighbor information collection method based on neighbor information storage and neighbor table exchange calculation effectively reduces the distance between nodes. Communication consumption. Experiments show that this method can significantly reduce the energy consumption in the identification process of boundary nodes and coverage holes. 2000 sensor nodes are deployed in a monitoring area with a scale of 500* ^500M2 , and the average remaining energy of the nodes reaches more than 99.8%;

(3) The complexity of the present invention is low, and the total complexity is O((k+2+log(n))n+m).

Description of drawings

Figure 1 is a schematic diagram of a Cartesian coordinate system.

Fig. 2 is a schematic diagram of judging the coverage of a sensing sector.

Figure 3 is a schematic diagram of the deployment of 2000 nodes.

Fig. 4 is a schematic diagram of the identification results of boundary nodes.

FIG. 5 is a schematic diagram of the accuracy comparison of border node identification in wireless sensor networks of different scales according to the present invention.

FIG. 6 is a schematic diagram of the comparison of error rates of border node identification in wireless sensor networks of different scales according to the present invention.

FIG. 7 is a schematic diagram of the comparison of energy surplus for boundary node identification in wireless sensor networks of different scales according to the present invention.

Fig. 8 is a run time analysis diagram of the present invention.

Detailed ways

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

The invention provides a distributed wireless sensor network boundary node identification method, comprising the following steps:

(1) Let the communication model of each node in the distributed wireless sensor network be a disc with the location of the node as the center and the communication coverage radius CR as the radius, and the node stores the information of the 1-hop neighbor nodes within its communication range Neighbor information: Each node sends a request to its 1-hop neighbor node and exchanges 1-hop neighbor information to collect neighbor information of neighbor nodes within s hops, where s is 2 to 3; this embodiment collects neighbor nodes within 2 hops Neighborhood information is used as an example for illustration.

Each node calculates the neighbor information of its 2-hop neighbor nodes by the following formula:

Among them, v _i represents the current node, v _u represents the k-1 hop neighbors of v _i , Represents the k-hop neighbor node set of v _i , Represents the k-1 hop neighbor node set of v _i , Indicates the 1-hop neighbor node set of v _u , k=2;

Carry out step (2) to step (5) to each node in the wireless sensor network in turn to judge whether this node is a border node;

(2) Establish a Cartesian coordinate system with the current node _v1 as the center and the sensing coverage radius SR of node _v1 as the radius, and calculate the absolute angle of the neighbor nodes within s hops of node _v1 in the coordinate system. The range of the angle is [0 °, 360 °], and the definition of the absolute angle is: in the Cartesian coordinate system established with the node v ₁ as the center of the circle, the connection line between the node v ₁ and the neighbor node is along the counterclockwise direction and x The positive angle of the axis is the absolute angle of the neighbor node of v ₁ in the coordinate system centered on node v ₁ ;

Referring to Figure 1, node v is the center of the circle, node u and node n are the 1-hop neighbor nodes of node v, node m is the 2-hop neighbor node of node v, ∠u and ∠m are the distance between node u and node m and the x-axis respectively The included angle, that is, the absolute angle, the sector mvn corresponding to the central angle ∠γ _mvn is formed by the current node v and its adjacent nodes m and n, and The enclosed arc is the edge of the sector mvn, the area enclosed by the dotted line is the sensing area of node v, and the dotted line is the sensing boundary of v;

(3) If the absolute angles of more than two neighbor nodes are the same, only keep the neighbor node closest to node v ₁ ; referring to Figure 2, if the absolute angles of node v ₂ and node v ₁₈ are the same, keep v ₂ and remove v ₁₈ ;

(4) Sort the neighbor nodes according to their absolute angle from small to large; referring to Figure 2, the order of the sorted nodes is {v12, v13, v5, v14, v6, v15, v7, v16, v17, v2, v8, v9, v10, v13, v11, v4};

(5) Determine in turn whether the edge of each sensing sector of node _v1 is completely covered by the adjacent nodes of the sensing sector, wherein, with the current node _v1 as the center of the circle, the sensor coverage of node _v1 In the circle whose radius SR is the radius, it is surrounded by the radius of the connection line between node v ₁ and neighbor node v _j , the radius of the connection line between node v ₁ and neighbor node v _k , and the arc enclosed by them The area is the sensing sector v _j v ₁ v _k , the arc is the edge of the sensing sector, the node v _j and the node v _k are the adjacent nodes of the sensing sector v _j v ₁ v _k , if the The edge is completely covered by the sensing areas of neighbor nodes v _j and v _k at the same time, then the sensing sector v _j v ₁ v _k will not be at the edge of the network or coverage hole, so the edge of the sensing sector v _j v ₁ v _k is completely covered by its adjacent nodes, referring to Figure 2, the edge of sector v ₁₂ v ₁ v ₁₃ can be completely covered by node v ₁₂ and node v ₁₃ ; if there is a sensing sector edge of node v ₁ cannot be covered by its If the adjacent nodes are completely covered, the node _v1 is a boundary node, otherwise the edge of each sensing sector of the node _v1 is completely covered by its adjacent nodes, and the node _v1 is not a boundary node.

Referring to Fig. 3, deploy 2000 sensor nodes in the area of 500* ^500M2 , utilize the distributed wireless sensor network boundary node identification method of the present invention to carry out boundary node identification on it, the result is shown in Figure 4, wherein the hollow point Indicates the identified boundary nodes. It can be seen that the present invention accurately detects the border nodes of the sensor network, and there is almost no noise.

Fig. 5 has shown the correct rate comparison of the present invention when the network scale is 100, 1000 and 2000, it can be seen that under different network scales (the network densities are respectively 0.0004, 0.004, 0.008 at this time), the correct detection rate of border nodes Both remain above 90%, and with the increase of the network scale, the correct rate even reaches 100%.

Figure 6 shows the error rate comparison of the present invention when the network scale is 100, 1000 and 2000. It can be seen that under different network scales, the error detection rate of the border nodes is kept below 10%. With the increase of the network scale , the error rate even reaches 0.

The main function of the wireless sensor network is to perform monitoring tasks, so the detection of border nodes should not consume too much energy of the nodes, so as to ensure that the nodes have enough energy to perform monitoring tasks. ) status of the remaining node energy after the boundary node identification is completed, it can be clearly seen in the figure that the actual node remaining situation of the present invention fully meets the needs of the actual task, and the boundary node can be realized without consuming too much node energy Identify tasks.

Fig. 8 is the running time analysis of the present invention, it can be seen that in the process of increasing the node scale, although the running time is increasing exponentially, the increase range is not large.

The following table shows the algorithmic complexity of each sub-process of the present invention:

The algorithmic complexity of the sub-process of the present invention in table 1

In Table 1, n represents the number of nodes in the network, m represents the number of communication connections (that is, edges between nodes) that can directly communicate between nodes in the network, and k represents the average node degree of the network.

Claims (1)

1. a distributed wireless sensor network boundary node identification method, it is characterized in that comprising the following steps: (1) Let the communication model of each node in the distributed wireless sensor network be a disc with the location of the node as the center and the communication coverage radius CR as the radius, and the node stores the information of the 1-hop neighbor nodes within its communication range Neighbor information; each node sends a request to its 1-hop neighbor node and exchanges 1-hop neighbor information to collect neighbor information of neighbor nodes within 2 hops; each node calculates the neighbor information of its 2-hop neighbor node by the following formula: Among them, v _i represents the current node, v _u represents the k-1 hop neighbors of v _i , Represents the k-hop neighbor node set of v _i , Represents the k-1 hop neighbor node set of v _i , Indicates the 1-hop neighbor node set of v _u , k=2; Carry out step (2) to step (5) to each node in the wireless sensor network in turn to judge whether this node is a border node; (2) Establish a Cartesian coordinate system with the current node _v1 as the center and the sensor coverage radius SR of node _v1 as the radius, and calculate the absolute angle of the neighbor nodes within 2 hops of node _v1 in the coordinate system, and the absolute The range of the angle is [0 °, 360 °], and the definition of the absolute angle is: in the Cartesian coordinate system established with the node v ₁ as the center of the circle, the connection line between the node v ₁ and the neighbor node is along the counterclockwise direction and x The positive angle of the axis is the absolute angle of the neighbor node of v ₁ in the coordinate system centered on node v ₁ ; (3) If the absolute angles of more than two neighbor nodes are the same, only keep the neighbor node closest to node _v1 ; (4) Sort the neighbor nodes according to their absolute angle from small to large; (5) Determine in turn whether the edge of each sensing sector of node _v1 is completely covered by the sensing area of the adjacent node of the sensing sector, wherein, with the current node _v1 as the center of the circle, node _v1 In a circle whose sensing coverage radius SR is the radius, the radius of the connection line between node v ₁ and neighbor node v _j , the radius of the connection line between node v ₁ and neighbor node v _k , and the arc enclosed by them The enclosed area is the sensing sector v _j v ₁ v _k , the arc is the edge of the sensing sector v _j v ₁ v _k , the node v _j and the node v _k are the sensing sector v _j v The adjacent nodes of ₁ v _k , if the edge is completely covered by the sensing areas of neighboring nodes v _j and v _k at the same time, then the edge of the sensing sector v _j v ₁ v _k is completely covered by its adjacent nodes; if there is If the edge of a sensing sector cannot be completely covered by its adjacent nodes, then node _v1 is a boundary node, otherwise node _v1 is not a boundary node.