CN102970744B

CN102970744B - Wireless sensor network regional locating method based on node density

Info

Publication number: CN102970744B
Application number: CN201210376260.XA
Authority: CN
Inventors: 陈晓江; 韩金枝; 房鼎益; 邢天璋; 刘晨; 聂卫科; 肖云; 张远; 金梦; 赵康
Original assignee: Northwestern University
Current assignee: Northwestern University
Priority date: 2012-09-29
Filing date: 2012-09-29
Publication date: 2015-03-25
Anticipated expiration: 2032-09-29
Also published as: CN102970744A

Abstract

The invention discloses a wireless sensor network regional locating method based on node density. The method includes: boundary detection, regional division and distance calculation. The boundary detection includes that nodes in a network are divided into boundary nodes and non-boundary nodes. The regional division includes a topology discovery stage, a non-boundary node region division stage and a boundary node region division stage, wherein in the topology discovery stage, each node obtains a neighbor information table and a route information table of the node through broadcasting data, and in the boundary node region division stage, the boundary nodes and nodes with the most neighbor nodes in the neighbor non-boundary nodes of the boundary nodes are divided into the same region. The method is applied to large-scale anisotropic networks with uneven distribution of nodes and irregular signal distribution under a complex environment, can be adapt to various topology structures through region division and single hop distance calculation of an independent region, and practicality of an algorithm in a real scene is improved. By means of the method, locating precision is improved, and a locating problem of unknown nodes in the anisotropic networks is solved effectively.

Description

Wireless sensor network regional positioning method based on node density

The invention relates to a Wireless Sensor Network (WSN) positioning technology, in particular to a Wireless Sensor Network regional positioning method based on node density.

Background

As the most advanced information acquisition technology at present, WSNs are often used for environmental monitoring, target tracking, and the like to report the current state of a monitored object, and state information generally needs to be combined with position information to accurately reflect the state of the object to be measured. Users typically need to know what happens and also care about the location where the event happens, and therefore, determining the location information of the node plays a key role in the validity of the WSN application. For example, in fire monitoring, a node detects the occurrence of a fire through data acquisition, and can arrange effective rescue measures only when the node is located at the position where the fire occurs. Therefore, node self-location techniques are of great significance in WSN applications.

In the WSN, the position information can also assist other WSN technologies, and in the design of a routing protocol, the routing protocol (GEM, GPSR and the like) based on the geographic position has wide application; in the design of a data fusion algorithm, accurate position information can greatly improve the reliability of data transmission; in the node deployment strategy, the position information can influence the topological form of the network and the coverage condition of the node on the network; the importance of the position information is more obvious in position-related applications such as target tracking, real-time monitoring and the like. In the WSN, the positioning algorithm is divided into positioning based on ranging independent from distance, distributed and centralized positioning, active and passive positioning, close coupling and loose coupling positioning, and the like, according to different division criteria.

According to whether the distance between the nodes needs to be measured in the positioning process, the positioning algorithm is divided into a Range-based (Range-based) and Range-free (Range-free) based positioning algorithm. The positioning algorithm based on the distance measurement calculates the position information of the nodes by a trilateral or maximum likelihood estimation method, the algorithm can provide effective positioning accuracy, and for the WSN with limited resources, the positioning cost is higher, extra hardware facilities or software cost is required, and the algorithm is not suitable for large-scale positioning scenes; the distance-independent positioning algorithm can realize distance estimation only by network connectivity information, determines the positions of nodes, is more suitable for large-scale environment, has lower positioning cost and lower positioning precision than a positioning algorithm based on ranging because of no need of ranging, and simultaneously faces the challenges of an anisotropic network and a sparse network.

In the distance-independent positioning algorithm, the DV-Hop algorithm is widely applied to a large-scale positioning environment due to simple implementation and relatively high positioning accuracy, and becomes a hotspot for positioning research and attention at present. The DV-Hop algorithm represents the distance from an unknown node to a beacon node by the average single-Hop distance and the Hop step number multiplied by the average single-Hop distance, and positioning is carried out through trilateration after the unknown node obtains the distances from three or more beacon nodes. The process is divided into three stages:

the first stage is as follows: the positioning information transmission and the minimum skip step number calculation are carried out, the beacon nodes start data transmission, each beacon node broadcasts a positioning starting data packet outwards, the data packet comprises the position information of the beacon node and the distance skip step number, and after the neighbor nodes receive the data packet, the new data packet formed by adding 1 to the skip step number segment value in the packet is transmitted to the neighbors. The source of the data packet is marked to avoid repeated delivery of data. And if one node receives a plurality of data packets from the same beacon node, only the packet with the minimum hop value is reserved, other data packets are discarded, and the hop value from the node to the beacon node is ensured to be minimum.

And a second stage: calculating the single-hop distance, wherein the stage is carried out between the beacon nodes, and each beacon node calculates the average single-hop distance Hopsize of the beacon node according to the following formula_i，

<math> <mrow> <msub> <mi>Hopsize</mi> <mi>i</mi> </msub> <mo>=</mo> <munder> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>&NotEqual;</mo> <mi>j</mi> </mrow> </munder> <msqrt> <msup> <mrow> <mo>(</mo> <msub> <mi>x</mi> <mi>i</mi> </msub> <mo>-</mo> <msub> <mi>x</mi> <mi>j</mi> </msub> <mo>)</mo> </mrow> <mn>2</mn> </msup> <mo>+</mo> <msup> <mrow> <mo>(</mo> <msub> <mi>y</mi> <mi>i</mi> </msub> <mo>-</mo> <msub> <mi>y</mi> <mi>j</mi> </msub> <mo>)</mo> </mrow> <mn>2</mn> </msup> </msqrt> <mo>/</mo> <munder> <mi>Σ</mi> <mrow> <mi>i</mi> <mo>&NotEqual;</mo> <mi>j</mi> </mrow> </munder> <msub> <mi>hops</mi> <mi>ij</mi> </msub> </mrow> </math>

Wherein (x)_i,y_i),(x_j,y_j) Is the coordinates, hops, of beacon nodes i and j_ijIs the number of hops between nodes. After the calculation is finished, the data packet containing the average single-hop distance information is broadcasted outwards, and after the neighbor node receives the data packet, the data packet is used as the calculation of the neighbor node to the beacon nodeAnd if the node receives data of a plurality of beacon nodes, only the single-hop distance information which is far away from the first received single-hop distance is needed to be reserved, other data packets are discarded, and the received single-hop distance information is ensured to be sent by the nearest beacon node.

And a third stage: and positioning, namely calculating the coordinate position of the node by utilizing the distances from the nodes obtained by calculation in the first two stages to 3 or more than 3 beacon nodes according to the principle of trilateration ranging or maximum likelihood estimation, so as to achieve the purpose of positioning.

The DV-Hop algorithm has the advantages of simple thought, small calculated amount and easy realization, but in an actual WSN application system, the DV-Hop algorithm has the problems of low positioning precision, dependence on network topology for positioning and the like. At present, some improvements of DV-Hop algorithms are generated at home and abroad, and the essence of the DV-Hop algorithms is that the distance between a node and a beacon node is calculated by the product of a single-Hop distance and Hop step number, and then a trilateration or maximum likelihood estimation method is adopted to determine the node coordinate, so the improvements of the DV-Hop algorithms are performed from the following three aspects.

1. Distance of single jump

Pengang et al calculate the single-Hop distance in the DV-Hop algorithm, and calculate the distance from an unknown node to a beacon node by averaging the single-Hop distances calculated by each beacon node in the network as the single-Hop distances of all nodes in the whole network, thereby improving the accuracy of distance estimation and reducing the error of positioning calculation; on the basis, the Linjinchao et al further corrects the average whole network single hop distance by analyzing the error of each beacon node; zhengjungang et al uses the Cayley-Menger determinant to optimize the distance estimation of unknown nodes through the geometric constraint of Euler space, reduce the ranging error, and improve the positioning accuracy of the nodes.

2. Number of jumping steps

Liulijun et al propose an improved DV-Hop algorithm based on Cluster management, adopt the idea of clustering, through dividing the network into smaller clusters, limit the communication number of steps from unknown node to anchor node, thus improve the positioning accuracy, reduce and position the overhead; xi w. et al propose the concept of virtual number of hops in the positioning process based on the observation that nodes closer to the beacon node typically have more successors and fewer successors than nodes farther away. By maintaining two types of hop counts for each node, one is a real hop based on routing, and the other is a virtual hop count called hop by hop, the virtual hop is used for correcting the traditional hop count, so that the error caused by large difference of distance of each hop due to the rigor of the field environment is shielded in a certain sense, and the positioning accuracy is improved.

Chenkai et al have proposed an improved BNL (basic on the number of neighbor localization) positioning algorithm, which divides the network into several monitoring sub-regions, and then calculates the number of neighbors of the nodes in each sub-region to estimate the distance between the nodes, thereby reducing the influence of the node distribution on the calculation of the number of hops and improving the accuracy of the node positioning calculation to a certain extent.

3. Position solution

The method comprises the steps of correcting the proportion of different beacons participating in node positioning to improve positioning accuracy by introducing a weighted centroid algorithm into a node position calculation process, constructing a coordinate value numerical value iteration refinement algorithm based on a Taylor series expansion method aiming at the problem of large node coordinate error of trilateral positioning calculation, properly increasing the calculated amount of positioning nodes by reasonably selecting iteration threshold values, and improving the positioning accuracy and the positioning error stability.

In addition, the algorithm is improved from the aspects of selection of beacon nodes, topological structure and the like by some improved algorithms, the collinearity concept is introduced into the beacon node selection process by Liu's middle-aged people, and the reliability and robustness of the DV-Hop algorithm under the condition of low beacon node density are improved by optimizing the position relationship among the beacon nodes and the topological position relationship between the unknown nodes and the beacons.

Analyzing the above improved DV-Hop algorithm, we find:

the single-hop distance improvement method achieves the aim of improving the precision by improving the average single-hop distance of the network. For the single-hop distance, the node distribution of the whole network is close to most of the single-hop distance in the network only when the node distribution of the whole network is in a uniform state. Therefore, the improved method is more suitable for a network with uniformly distributed nodes, is not suitable for an earthen site protection wireless sensor network with non-uniform and irregular node distribution, and has limited error correction effect; the step number improving method improves an algorithm from the unknown node to the beacon node in terms of step number, is basically consistent with the method, and is also suitable for a regular network with uniformly distributed nodes; the position solution improvement method reduces errors from the angle of position calculation, is an error control technology, and does not process the root cause (non-linear errors) generated by the errors.

Disclosure of Invention

In view of the above-mentioned defects or shortcomings in the prior art, an object of the present invention is to provide a Node Density-based wireless sensor network partition location method (Node Density-based sub-regional Localization Technology in WSN, hereinafter referred to as NDL), which overcomes the defects of the existing improved DV-Hop location algorithm by partition of regions and calculation of single Hop distance of independent regions for an anisotropic network with non-uniform Node distribution and irregular signal distribution in a large-scale and complex environment, can better adapt to various topological structures, and improves the practicability of the algorithm in a real scene. Experimental results show that the positioning precision is improved by adopting the scheme of the invention, and the positioning problems under the conditions of uneven node distribution and irregular signal distribution in an anisotropic network are effectively solved.

In order to realize the technical task, the invention adopts the following technical scheme to realize:

a regional positioning method based on node density is used for positioning unknown nodes in a wireless sensor network, wherein the wireless sensor network comprises n nodes, m beacon nodes and n-m unknown nodes, the node communication radius is R, and each node has RSSI ranging capability, and the positioning method specifically comprises the following steps:

step 1, boundary detection: through boundary detection, nodes in the network are divided into boundary nodes and non-boundary nodes;

step 2, area division: the method comprises a topology discovery stage, a non-boundary node area division stage and a boundary node area division stage, wherein in the topology discovery stage, each node acquires a neighbor information table and a routing information table of the node through broadcast data; in the non-boundary node area division stage, each node carries out density area division through judgment of a neighbor RSSI value and selection judgment of the number of neighbor nodes; in the boundary node area division stage, dividing the boundary node and the node with the maximum number of neighbor nodes in the neighbor non-boundary nodes into the same area; through non-boundary node area division and boundary node area division, the whole wireless sensor network is divided into a plurality of small areas with relatively uniform node density;

step 3, distance calculation: for small areas where links between beacon nodes do not cover, selecting the single-hop distance of the area where the beacon node closest to the small area is located as the single-hop distance of the small area, obtaining the single-hop distance of each small area in the network, calculating the distances between the unknown node and three or more beacon nodes by the unknown node according to the routing information in the routing information table and the single-hop distance of the small area where the unknown node is located, and then calculating the position of the unknown node by using a least square method, so that the unknown node in the wireless network is successfully positioned.

The invention also comprises the following other technical characteristics:

the topology discovery phase in step 2 specifically includes the following steps:

step S1-1: all Beacon Nodes (BN) in the network₁,BN₂,BN₃…BN_m) Broadcasting the Preq data packet;

step S1-2: the node judges whether the Preq data packet is received, if so, the step S1-3 is executed, otherwise, the step S1-7 is executed;

step S1-3: the node judges whether the beacon node BN is received for the first time_iIf the transmitted Preq data packet is yes, executing S1-4, otherwise executing step S1-8;

step S1-4: the node updates the hop count from itself to the beacon node, namely count +1, broadcasts the updated Preq data packet outwards, and executes the step S1-5;

step S1-5: the node receiving the Preq data packet replies a Pack data packet to the node sending the Preq data packet, and confirms the receipt of the message;

step S1-6: after receiving the Pack data packet, the node sending the Preq data packet updates the neighbor information table and the routing information table of the node;

step S1-7: the node is considered as a bad node and does not participate in the positioning process;

step S1-8: node judging beacon node BN in current routing information table_iIf so, executing step S1-9, otherwise, executing step S1-4;

step S1-9: the packet is discarded.

The structure of the neighbor information table is as follows: the ID number Neighbor _ id of the Neighbor node of the node and the RSSI value Neighbor _ RSSI between the node and the Neighbor node are included.

The structure of the routing information table is as follows: the method comprises the id number Beacon _ id of the Beacon node, the coordinate of the Beacon node, the step jump information count of the node from the Beacon node and the node sequence route [ N ] passing through the path from the node to the Beacon node.

The non-boundary node region division stage specifically comprises the following steps:

step S2-1: in a networkAll Beacon Nodes (BN)₁,BN₂,BN₃…BN_m) Generating a region number area _ id by using the number of the self node, sending a region division request Pdiv data packet to all non-boundary nodes in a neighbor information table of the self node, and setting a self region division flag to be 1;

step S2-2: after receiving a Pdiv request data packet sent by a node j (i is less than n, j is less than n, i is not equal to j), a node i selects and judges a neighbor RSSI value according to a formula (1): if r_ijIf 0, the node i performs step S2-3, otherwise, performs step S2-4;

g_{i} = \frac{r_{ij} - E (R_{i})}{E (R_{i})} - - - (1)

wherein,

t_ris the threshold value of the RSSI value of the neighbor of the node i, t_rTaking (0.02-0.04), E (R)_i) Represents the mean of all neighbor RSSI values for node i,

step S2-3: deleting the node j from the neighbor node set of the node i, and simultaneously, counting the neighbor number n of the node i_iSubtracting 1 to obtain a new neighbor number value of the node i, and obtaining a vector N' ═ N after the neighbor number vector N of the node i is updated₁′,n′₂,...,n′_n]Executing the step S2-5;

step S2-4: keeping the neighbor node set of the node i unchanged, and executing the step S2-5;

step S2-5: the node i selects and judges the number of the neighbor nodes through a formula (2), if the formula (2) is established, the step S2-6 is executed, otherwise, the step S2-7 is executed;

|n′_i-n′_j|≤t_n (2)，

wherein, t_nIs the threshold value, t, in Pdiv data packet_nTaking (2-5);

step S2-6: judging that the node i belongs to a region with the region number of area _ id in the Pdiv request data packet, dividing the node i and the node j into the same density region, and setting a flag of the node i to be 1;

step S2-7: the node i judges that the node i does not belong to an area with an area number of area _ id in the Pdiv request data packet, takes the node _ id of the node i as a new area _ id, and sends the Pdiv data packet to a non-boundary node in a neighbor table of the node i, so that the node i initiates area division with the node i as the center like a beacon node.

The specific steps of the distance calculation in the step 3 are as follows:

marking small area A_iIn a single hop distance ofSetting m links among beacon nodes in the network, wherein the corresponding real distance on each link isCounting small area A passed by link between beacon nodes_iAnd hop counts hos in each cell_iEstablishing a formula:

using an optimization method to perform each small region d_iFor small areas where links between beacon nodes do not cover, selecting the single-hop distance of the area where the beacon node closest to the small area is located as the single-hop distance of the small area, and after the single-hop distance of each small area in the network is obtained, calculating the single-hop distance of the unknown node and the beacon node BN according to the routing information in the routing information table of the unknown node and the single-hop distance of the small area where the unknown node is located by the following formula_iDistance dist of_i：

After the distances between the unknown nodes and three or more beacon nodes are obtained through calculation, the positions of the unknown nodes are calculated by using a least square method.

Compared with the prior art, the invention has the following advantages:

1) improves the precision of the positioning algorithm

The invention introduces the idea of regional positioning, improves the positioning error of the DV-Hop positioning algorithm in the anisotropic network environment by independently calculating the single-Hop distance in each region and effectively improves the positioning performance of the conventional DV-Hop positioning algorithm in the anisotropic network due to the positioning error caused by the fixed single-Hop distance. The positioning problem under the conditions of uneven node distribution and irregular signal distribution in the anisotropic network is solved.

2) Has better expandability

According to the invention, through region division, the anisotropy of the whole network is converted into the isotropic network in each region, so that the problem that the DV-Hop algorithm cannot adapt to a complex network environment (anisotropic network) is solved, the dependence of the positioning algorithm on the network topology is reduced, and the method can be applied to various real environments.

Drawings

FIG. 1 is a flow chart of the NDL algorithm of the present invention.

FIG. 2 is a flow chart of the NDL algorithm topology discovery phase of the present invention.

FIG. 3 is a flow chart of the NDL algorithm non-boundary node region partition phase of the present invention.

Fig. 4-13 show the performance comparison between the NDL algorithm and DV-hop algorithm of the present invention in different application examples. Wherein:

fig. 4 is a linear network positioning diagram.

Fig. 5 is a rectangular network positioning diagram.

FIG. 6 is a graph of mean linear network positioning error.

FIG. 7 is a graph of mean square network positioning error.

Fig. 8 is a diagram of a simulated rectangular network topology.

Fig. 9 is a diagram of a simulated C-type network topology.

Fig. 10 is a communication range change diagram.

Fig. 11 is a diagram illustrating the change in the number of beacons.

Fig. 12 is a range error diagram.

Fig. 13 is a positioning error map.

The present invention will be described in further detail with reference to the accompanying drawings and specific embodiments.

Detailed Description

In the wireless sensor network, positioning refers to acquiring the physical position of a node in the network by using part of known information and mutual cooperation among nodes according to a certain algorithm by utilizing sensor nodes in the network. In a network with non-uniform distribution of network nodes, the traditional positioning algorithm cannot be applied. For example, in the application of protecting an earthen site, in order to distinguish which position of the site the collected data is the disease information, the deployment node needs to be positioned. Meanwhile, due to different degrees of the ruins, nodes need to be arranged with emphasis on the condition of the relics, so that the phenomenon of uneven distribution of the nodes of the WSN is caused, and an anisotropic sensor network is formed. The traditional DV-Hop algorithm is fixed in single-Hop distance, so that the positioning error of an anisotropic network used in an earthen archaeological site is increased, and the method cannot be applied.

In order to solve the problem, the invention introduces a node density concept, divides the anisotropic network of the whole network into the isotropic network of each region by defining the number of neighbors of the node as a region division standard, and respectively calculates the single-Hop distance of each region, thereby reducing the error accumulation of the DV-Hop algorithm under the condition of the fixed single-Hop distance of the whole network and effectively improving the positioning precision. Meanwhile, the algorithm reduces the network scale through regional division, and has good expansibility.

We present some of the terms and nouns referred to in this invention as follows:

beacon Nodes (Beacon Nodes): the node for determining the position of the node is used as a reference for assisting other nodes in positioning in the network initialization stage. The beacon node usually occupies a small proportion of the network nodes, and can be a beacon node by assisting the node to determine the position of the node through manual deployment or GPS positioning equipment.

Unknown Nodes (Unknown Nodes): nodes other than beacons. Most of the nodes are randomly deployed in the network, the position of the nodes cannot be obtained, and the nodes need to calculate the position information of the nodes by using the beacon nodes in the positioning process. The self-positioning of the node is the process of calculating the position information of the unknown node.

Neighbor Nodes (Neighbor Nodes): the node communication range is a set formed by all nodes except the node.

Hop Count (Hop Count): the sum of the number of hops experienced by the two nodes communicating.

Single hop distance (One hop size): two communications do not require the distance between one-hop reachable nodes relayed by other nodes.

Average single Hop distance (Average One Hop size): and dividing the sum of the single-hop distances of all the nodes by the hop step number. In WSNs, the network average single hop distance is unique.

Source Node (Source Node): refers to a network node that acts as a source to send the original data packet.

Destination Node (Destination Node): refers to a network node that serves as a sink to accept packets.

Intermediate Node (Intermediate Node): the network node is a network node which participates in data packet forwarding except for a source node and a destination node.

As shown in fig. 1, the method for positioning a sub-area based on node density of the present invention is designed to study the problem of positioning a wireless sensor network in an earthen site protection scenario, assuming that there are n nodes in the wireless sensor network, where m beacon nodes and n-m unknown nodes have a node communication radius of R, and each node has an RSSI ranging capability. The method specifically comprises the following steps:

1. boundary detection:

boundary detection is well-established in the research of WSN, and currently, mainstream boundary detection algorithms are divided into boundary detection based on geometric topology and boundary detection based on statistical thought. The invention adopts the boundary detection method proposed by WangY, et al to determine the boundary nodes of the anisotropic network, the algorithm does not make any assumption on the network itself, and only utilizes the node topology information to detect the inner boundary and the outer boundary by constructing the network shortest path tree on the basis of observing the irregular jump distance caused by the network cavity. And after the network boundary detection is finished, network division is carried out by adopting a node density model. After boundary detection, the nodes in the network are divided into boundary nodes and non-boundary nodes which are respectively collectedAndis shown in the formula, wherein v_eRepresenting boundary nodes, v_rAnd (4) representing non-boundary nodes, wherein t is the number of boundary nodes, and n-t is the number of non-boundary nodes.

2. Area division: the method comprises a topology discovery phase, a non-boundary node region division phase and a boundary node region division phase.

1) A topology discovery phase: the method comprises the steps of network initialization, topology discovery is achieved through broadcast data, and nodes take the topology discovery as the first step of acquiring neighbor node number points and neighbor RSSI sequences. The method specifically comprises the following steps:

step S1-8: node judging beacon node BN in current routing information table_iIf it is less than the count value of the new packet, if so, step S1-9 is performed,otherwise, executing step S1-4;

step S1-9: discarding the data packet;

as shown in table 1, the location request Preq packet structure: node _ id represents the id number of the beacon node; coordinates denotes the coordinates (x, y) of the beacon; the count represents the hop count from the beacon node to the unknown node, and the initial count value is 0; route [ N ] represents a node sequence passing through the shortest path from the beacon node to the unknown node, wherein the value of N is adjusted according to the scale of the nodes in the network, and in the experiment of the patent, the value of N is 20.

Table 1 beacon broadcasting location request Preq packet format

node_id

coordinates

count

route[N]

As shown in table 2, the structure of the Pack packet is: the node _ id represents the id number of the beacon node which receives the Preq data packet; the RSSI represents the RSSI value between the transmitting node and the receiving node.

Table 2 Pack packet format

node_id

RSSI

As shown in table 3, the structure of the neighbor information table: neighbor _ id represents the id number of the Neighbor node of the node, and Neighbor _ RSSI represents the RSSI value between the node and the Neighbor node.

Table 3 neighbor information table

Neighbor_id	Neighbor_RSSI
		v₁	RSSI₁
……	……
		v_n	RSSI_n

As shown in table 4, the structure of the routing information table: beacon _ id represents the id number of the Beacon node, coordinate represents the coordinate (x, y) of the Beacon node, count represents the hop information of the node from the Beacon node, and route [ N ] represents the sequence of nodes passing through on the path from the node to the Beacon node.

Table 4 routing information table

Beacon_id	coordinate	count	route[N]
				B₁	(x₁,y₁)	3	v₁,v₅
……	……	……	……
				B_n	(x_n,y_n)	5	v₂,v₄,v₈,v₁₃

2) Non-boundary node area division stage: considering the difference between the number of neighbors of the boundary node and the number of non-boundary nodes, the division is only performed on the non-boundary nodesIs carried out in (1). Below, we give some definitions:

we first describe the number of neighbor nodes of a node in the network: given a WSN S with n nodes, the vector is used for the number of neighbors of all nodes i in the networkN＝[n₁,n₂,...,n_n]^TIs represented by, wherein n_iRepresenting the number of neighbors of the node i; vector R for neighbor RSSI sequence of node i_i＝[r_i1,r_i2,...,r_in]^TIs shown in the formula, wherein r_ijThe RSSI value between the node i and the node j is represented, and the neighbor RSSI values of all the nodes i in the whole network can be represented by a matrix R ═ R₁,R₂,...,R_n]It is shown that the ith column of the matrix represents the neighbor RSSI sequence for node i.

All nodes are provided with a region division flag, the initial value is 0, 0 indicates that no division is performed, and if the node has already completed the region division into a certain region, the flag is 1.

step S2-1: all Beacon Nodes (BN) in the network₁,BN₂,BN₃…BN_m) Generating a region number area _ id by using the number of the self node, sending a region division request Pdiv data packet to all non-boundary nodes in a neighbor information table of the self node, and setting a self region division flag to be 1;

g_{i} = \frac{r_{ij} - E (R_{i})}{E (R_{i})} - - - (1)

wherein,

|n′_i-n′_j|≤t_n (2)，

wherein, t_nIs the threshold value, t, in Pdiv data packet_nTaking (2-5);

As shown in table 5, the structure of the zone partition request Pdiv packet is: node _ id represents the id number of the node; t is t_nRepresenting the threshold value of the number of neighbor nodes when a non-boundary node area is divided; t is t_rRepresenting the threshold value of the RSSI value of the neighbor when the non-boundary node area is divided; area _ id indicates an area number, unique.

Table 5 zone partition request Pdiv packet format

node_id

t_n

t_r

area_id

Through RSSI selection and neighbor node number selection, a node distribution density model of the whole network is constructed, and the model mainly depends on the logic topology state and the topology density of the network.

3) Boundary node area division stage: on the basis of the non-boundary node division, the boundary nodes of the network are divided, so that the increase of the number of regions and the inaccuracy of region division caused by the unstable number of the boundary neighbors are avoided. Setting boundary nodesIs marked by A'_iLine A'_i＝A_jWhereinAndmutually neighbor nodes }, i.e. boundary nodesAnd the node with the maximum number of neighbor nodes in the neighbor non-boundary nodesDividing the areas into the same area; theoretically, according to the distribution rule, the more the number of the neighbor nodes is, the farther the node is from the regional boundary is shown, and therefore, the boundary nodeSelecting the node which divides itself into the nodes with the maximum number of neighbor nodes in the neighbor non-boundary nodesIs most reasonable and thus the more accurate the division according to the above density division criterion. Therefore, the method effectively solves the problem that the boundary node is adjacent to the neighbor nodeThe number is different and the division cannot be correctly performed.

Through non-boundary node area division and boundary node area division, the whole wireless sensor network is divided into a plurality of small areas with relatively uniform node density.

3. Distance calculation

By subdividing the single-hop distances in the network, different single-hop distances are respectively calculated in each cell, and the positioning accuracy is effectively improved. Marking small area A_iIn a single hop distance ofSetting m links among beacon nodes in the network, wherein the corresponding real distance on each link isCounting small area A passed by link between beacon nodes_iAnd hop counts hos in each cell_iEstablishing a formula:

using an optimization method to perform each small region d_iFor small areas where links between beacon nodes do not cover, selecting the single-hop distance of the area where the beacon node closest to the small area is located as the single-hop distance of the small area, and after the single-hop distance of each small area in the network is obtained, calculating by the unknown node according to the routing information in the routing information table and the single-hop distance of the small area where the unknown node is located according to the following formulaThe unknown node and the beacon node BN_iDistance dist of_i：

After the distances between the unknown nodes and three or more beacon nodes are obtained, the positions of the unknown nodes are calculated by using a least square method. By adopting the node density-based regional positioning method, the regional division is not influenced by the beacon nodes, the node positioning calculation is not limited by the region, the system can work normally even under the condition of a small number of beacon nodes (not less than three), and the expandability is good.

To verify the effectiveness of the method of the present invention, the inventors give further illustrations in the following examples:

example 1:

the embodiment is carried out in a linear network with uniformly distributed nodes and segments, the network is divided into 3 segments, and the distances among the nodes in each segment are equal and are respectively 0.8m, 1.6m and 2.4 m. A total of 16 Micaz nodes are deployed, 80cm from the ground, broadcasting packets outward at a frequency of 30s and a power of-10 dBm. The farthest distance of the whole network is 56.5m, and the hop number of the two nodes with the farthest distance is 4. In the experiment, the communication radius of the node is about 13m, and the number of node neighbors in different areas in the network is 7.4,9 and 4.8(nodes) respectively.

As shown in fig. 4, the boundary nodes and the middle nodes at two ends of the network are used as 3 beacon nodes, and it can be seen from the figure that the NDL algorithm has a significant reduction in positioning error, and particularly when the node distance increases, the performance of the algorithm is improved more significantly. Meanwhile, for a node with a large positioning error, such as the node No. 4, the NDL algorithm effectively improves the positioning accuracy.

Example 2:

the embodiment is carried out in a rectangular network with uniformly distributed nodes and regions, the network is divided into 3 regions, the areas of the regions are equal, and the regions are all 30 multiplied by 10 to 300m²The number of nodes in the region is 21,10,4, respectively. Experiments were performed using 35 Micaz nodes deployed on the square, each node being 80cm from the ground. The node broadcasts the packet out at a frequency of 30s, with a power of-10 dBm. The whole network consists of 35 nodes, and the maximum hop step number is 3 hops. The number of node pairs in one-hop communication is 60, the number of node pairs in two-hop communication is 54, and the number of node pairs in three-hop communication is 10. For one-hop communications, the range varies from 4.2m to 15.7 m.

As shown in fig. 3, 3 beacon nodes are randomly selected for positioning, and the positioning errors in the diagram are arranged from large to small according to the DV-Hop algorithm, so that the NDL algorithm has improved positioning performance, and the positioning errors are significantly reduced particularly in an area where nodes are densely deployed. Compared with DV-Hop algorithm, the NDL has good processing effect on larger positioning errors, and the positioning performance of the whole network is improved.

As can be seen from fig. 6 and 7, for the analysis of the maximum, average and minimum errors, in combination with the degree of anisotropy of the network under two topologies, the NDL algorithm of the present invention has significantly improved performance under two network topologies compared with the DV-Hop algorithm; under the condition of a rectangular network topology, the positioning precision of the NDL algorithm is improved more obviously; compared with the improvement of the minimum error, the NDL algorithm has better tolerance to larger positioning error than the DV-Hop algorithm. Through practical experiments, the improvement of the NDL algorithm on the basis of regional single-Hop distance estimation on the traditional DV-Hop algorithm is verified, and the adaptability of the NDL algorithm to an anisotropic network is effectively verified.

Example 3:

the embodiment is a simulation experiment, algorithm simulation in a two-dimensional space is performed through Matlab, and a rectangular topology and a C-type topology are selected on a network topology through simulation, as shown in fig. 8 and 9. The adaptability of the NDL algorithm to the anisotropic network under different network conditions is analyzed from three aspects of node communication radius, the number of beacon nodes and the network topology form, and the positioning performance of the algorithm is simulated and evaluated.

As shown in fig. 10, we adjust the communication radius of the node from 80cm to 125m every 5m, and the positioning result shows that, compared with the DV-Hop algorithm, the NDL algorithm has better positioning performance under the condition that the communication radius of the node is increased, and the specific experimental analysis result is as follows. Under the condition that the communication radiuses of the nodes are the same, the NDL algorithm shows better positioning performance, and compared with the DV-Hop algorithm, the NDL algorithm shows that the maximum positioning accuracy is improved by 9% and 25% in rectangular and C-type networks respectively; along with the increase of the communication radius of the nodes, the positioning accuracy of the two algorithms is increased, and the increase degree of the NDL algorithm is slightly larger than that of the DV-Hop algorithm.

We increase the number of beacons participating in positioning from 3 to 14 every other. As shown in fig. 11, the positioning result shows that the NDL algorithm has higher positioning accuracy than the DV-Hop algorithm under the condition that the number of beacon nodes is increased, and the specific experimental analysis result is as follows. Under the condition that the number of beacon nodes is the same, the NDL algorithm has higher positioning accuracy than the DV-Hop algorithm, and the maximum accuracy improvement of 10% and 40% are respectively shown in a rectangular network and a C-type network; with the increase of the number of the beacon nodes, the positioning precision is obviously improved for the two algorithms. But the NDL algorithm is improved to a greater extent; as the number of beacons increases, the positioning error gradually decreases, and as the number of beacons increases to 9, the curve tends to be smooth, especially in a rectangular network.

We discuss the influence of network topology morphology on positioning results, and both network sizes are 500 x 500m². The nodes are distributed into 3 uneven density areas, and the positioning result shows that compared with a DV-Hop algorithm, the NDL algorithm has better positioning performance and higher tolerance in an anisotropic network. The specific experimental analysis results are as follows. The DV-Hop and NDL algorithms have higher positioning accuracy under the rectangular network topology than the C-type network, because the C-type network has higher anisotropy degree and is relatively more difficult to position, the positioning error is larger; from the aspect of improvement of positioning accuracy, under the condition that the radius of the node is increased or the number of the beacon nodes is increased, the accuracy of the C-type network is improved by a larger extent than that of a rectangular network, the accuracy difference of 16% and 30% is respectively achieved, and the stronger adaptability of the NDL to the anisotropic network is reflected.

We discuss the localization performance of NDL algorithm from the point of view of node error analysis. Fig. 12 and 13 reflect the accumulated graphs of the ranging and positioning errors CDF of the whole network under the above simulated rectangular topology. From the figures, we can clearly draw the following conclusions. The main improvement of the NDL in the range finding error is the larger error part in DV-Hop, and the range finding error improvement is more obvious when the range finding error is 15m-25 m. The method is mainly characterized in that when the distance between nodes is close, the corresponding Hop steps are fewer, the error accumulation caused by the single-Hop distance of the DV-Hop algorithm is not obvious, and when the distance between nodes is longer, the error of the distance measurement is obviously increased, and the advantage of the NDL algorithm is expressed; under the influence of the ranging error, the NDL algorithm also has advantages in a large positioning error part, and the positioning accuracy of the algorithm is improved by reducing the larger positioning error in the network. In simulation, the NDL algorithm has 80% node positioning error within 20m, and the DV-Hop algorithm is only about 65%.

In summary, compared with the current commonly used DV-Hop algorithm, the NDL algorithm of the present invention has the following advantages:

(1) and (3) algorithm positioning accuracy:

through region division and single-Hop distance calculation of independent regions, the NDL algorithm can obtain a relatively accurate distance measurement result in an anisotropic network environment, so that the defects of the DV-Hop algorithm are overcome, and the positioning precision is effectively improved. The positioning problem under the conditions of uneven node distribution and irregular signal distribution in the anisotropic network is solved.

(2) And (3) expandability of the algorithm:

by the regional division, the problem that the DV-Hop algorithm cannot adapt to a complex network environment (anisotropy) is solved, the dependence of the positioning algorithm on the network topology is reduced, and the method can be applied to various real environments.

Claims

1. A regional positioning method based on node density is characterized in that the method positions unknown nodes in a wireless sensor network, the wireless sensor network comprises n nodes, wherein m beacon nodes and n-m unknown nodes have a node communication radius of R, and each node has RSSI ranging capability, and the positioning method specifically comprises the following steps:

2. The method according to claim 1, wherein the topology discovery phase in step 2 specifically includes the following steps:

step S1-1: all beacon nodes BN in the network₁,BN₂,BN₃…BN_mBroadcasting the Preq data packet;

step S1-3: the node judges whether the Preq data packet sent by the beacon node BNi is received for the first time, if so, the step S1-4 is executed, otherwise, the step S1-8 is executed;

step S1-4: the node updates the hop count from the node to the beacon node, namely, count +1, broadcasts the updated Preq data packet outwards, and executes the step S1-5, wherein the count represents the hop count from the beacon node to the unknown node;

step S1-8: the node judges whether the count value of the beacon node BNi in the current routing information table is smaller than the count value of the new data packet, if so, the step S1-9 is executed, otherwise, the step S1-4 is executed;

step S1-9: the packet is discarded.

3. The method according to claim 1, wherein the neighbor information table has a structure of: the ID number Neighbor _ id of the Neighbor node of the node and the RSSI value Neighbor _ RSSI between the node and the Neighbor node are included.

4. The method according to claim 1, wherein the routing information table has a structure of: the method comprises the id number Beacon _ id of the Beacon node, the coordinate of the Beacon node, the step jump information count of the node from the Beacon node and the node sequence route [ N ] passing through the path from the node to the Beacon node.

5. The method according to claim 1, wherein the non-boundary node region partition stage comprises the following steps:

step S2-1: all beacon nodes BN in the network₁,BN₂,BN₃…BN_mGenerating area number area _ id by the number of the node, sending area division request Pdiv data packets to all non-boundary nodes in the neighbor information table, and simultaneously sending area division request Pdiv data packets to all non-boundary nodes in the neighbor information tableSetting a self region division flag to 1;

g_{i} = \frac{r_{ij} - E (R_{i})}{E (R_{i})} - - - (1)

wherein,

step S2-3: deleting the node j from the neighbor node set of the node i, and simultaneously, counting the neighbor number n of the node i_iSubtracting 1 to obtain a vector N '═ N' after the neighbor number vector N of the node i is updated, wherein the vector N 'is used as a new neighbor number value of the node i'₁,n′₂,...,n′_n]Executing the step S2-5;

|n′_i-n′_j|≤t_n (2)，

wherein, t_nIs the threshold value, t, in Pdiv data packet_nTaking (2-5);

6. The method for positioning a sub-area based on node density as claimed in claim 1, wherein the distance calculation of step 3 comprises the following steps:

Wherein k is unknown node and beacon node BN_iThe number of small areas through which the link between the small areas passes, t is a variable and represents the serial numbers of the small areas;