ROBUST COVERAGE METHOD FOR RELAY NODES IN DOUBLE-LAYER STRUCTURE WIRELESS SENSOR NETWORK

Abstract

The present invention relates to a robust coverage method for relay nodes in a double-layer structure wireless sensor network. The present invention is a local search based relay node 2-coverage deployment algorithm which, by means of reducing the global deployment problem to a local deployment problem, achieves optimal deployment whilst ensuring robustness. The method specifically comprises two steps: first 1-coverage and second 1-coverage, wherein the first 1-coverage comprises the three steps of construction of relay node candidate deployment locations, grouping of sensor nodes and local deployment of relay nodes, wherein the sensor nodes are grouped by means of a novel grouping method, and the complexity of the algorithm is reduced whilst ensuring optimal deployment. The second 1-coverage adjusts a threshold, selects from every group the sensor nodes covered by just one relay node, and uses a 1-coverage method to re-implement 1-coverage of the sensor nodes, thereby ensuring robustness, reducing the number of relay nodes deployed, and shortening the problem-saving time.

Claims

1. A robust coverage method for relay nodes in a double-layer structure wireless sensor network, comprising the following steps: first 1-coverage: comprising a construction phase of relay node candidate locations, a grouping phase of sensor nodes and a local deployment phase; said construction phase of the relay node candidate locations is used for constructing the candidate deployment directions of all the relay nodes according to the direction information of the sensor nodes to be covered; said grouping phase of the sensor nodes is used for dividing the sensor nodes to be covered into independent groups; said local deployment phase is used for deploying the relay nodes in various independent groups, and the final deployment of the relay nodes is formed by local deployment results of various groups; second 1-coverage: implementing second 1-coverage on the sensor nodes covered by just one relay node in a first 1-coverage result; merging a second 1-coverage result and the first 1-coverage result; and outputting a final merged result.

2. The robust coverage method for the relay nodes in the double-layer structure wireless sensor network according to claim 1, wherein said construction phase of the relay node candidate locations comprises the following steps: (1) inputting location information X={x.sub.1, x.sub.2, . . . , x.sub.n} of n sensor nodes to be covered; (2) starting from 1 for i to mark x.sub.i as a searched node to construct a circle using the physical location of the x.sub.i node as a center of the circle and using a communication radius r as a radius, taking a point on the circumference every $\frac{2.Math.\pi }{k}$  radian, with a total of k points Y={y.sub.1, y.sub.2, . . . , y.sub.k} taken on one circumference; (3) from the y.sub.1 point, successively searching sensor nodes covered by the circles using the physical location of the y.sub.j point (j=1, 2 . . . k) as a center of the circle and using a communication radius r as a radius clockwise or anticlockwise; (4) taking the points which at least cover two sensor nodes from step (3) as relay node candidate locations, and marking the locations as a set P={p.sub.1, p.sub.2, . . . , p.sub.m}; (5) marking the (i+1).sub.th sensor node from X as the searched node, repeating steps (2)-(4), storing the candidate locations P=P∪P.sub.i searched each time until all sensor nodes in X are marked as the searched nodes, and outputting a search result P.

3. The robust coverage method for the relay nodes in the double-layer structure wireless sensor network according to claim 2, wherein in said step (4), if k points cover just one sensor node, the point $\arg .Math.\underset{1\le i\le k}{\min }.Math..Math.p_i-B.Math.$ closest to a base station is selected as the relay node candidate location P.sub.i, wherein p.sub.i indicates a coordinate of y.sub.i and B indicates a coordinate of the base station.

4. The robust coverage method for the relay nodes in the double-layer structure wireless sensor network according to claim 1, wherein said grouping phase of the sensor nodes comprises the following steps: (1) selecting the location P.sub.i from the set P of the relay node candidate locations: P.sub.i covers the most uncovered sensor nodes $\arg .Math.\underset{1\le i\le m}{\max }.Math..Math.P_i.Math.Z.Math.,$  wherein m indicates the number of elements in the set P and Z indicates the set of the remaining sensor nodes; marking the set formed by all the sensor nodes covered by P.sub.i as S.sub.i; (2) marking the set of the relay node candidate locations, in P, which cover the sensor nodes in S.sub.i as N.sub.i, calling the set formed by the sensor nodes covered by N.sub.i as T.sub.i and collectively calling all the sensor nodes in the set S.sub.i and the set T.sub.i as a group G.sub.i belonging to the location P.sub.i; (3) repeating steps (1)-(2), storing each grouping information G=G∪G.sub.i until all the sensor nodes are distributed to a certain group, and outputting a grouping result G.

5. The robust coverage method for the relay nodes in the double-layer structure wireless sensor network according to claim 1, wherein said local deployment phase comprises the following steps: (1) successively selecting the groups G.sub.i belonging to the location P.sub.i from G and searching all the relay node candidate locations F.sub.i that cover the sensor nodes in G.sub.i from P, thereby converting a geometric disc coverage problem into a minimum set coverage problem; (2) searching a minimum set coverage MSC.sub.i of (G.sub.i−S.sub.i) from F.sub.i by using a greedy algorithm and defining the weight of P.sub.i as w.sub.i=|C|, wherein C is the relay node candidate location uncovered by MSC.sub.i in N.sub.i; if w.sub.i>0, then selecting MSC.sub.i and P.sub.i as local deployment results; if w.sub.i=0 and P.sub.i contains sensor nodes only covered by P.sub.i, then selecting MSC.sub.i and P.sub.i as local deployment results; if w.sub.i=0 and P.sub.i contains the sensor nodes uncovered by P.sub.i, then selecting MSC.sub.i as a local deployment result; recording this local search result as Y.sub.i; (3) repeating steps (1)-(2), searching G.sub.i+1, storing the minimum set coverage of each group, i.e., Y=Y∪Y.sub.i until the sensor nodes in each group are covered, and outputting a final search result Y.

6. The robust coverage method for the relay nodes in the double-layer structure wireless sensor network according to claim 1, wherein said second 1-coverage phase comprises the following steps: (1) selecting the sensor nodes X′={x′.sub.1, x′.sub.2, . . . , x′.sub.l}, 1≦l≦n covered by just one relay node from the first 1-coverage result; (2) according to the network performance requirement of the wireless sensor network applied to different occasions, manually adjusting the threshold H of the relay node to obtain $\underset{1\le i\le m}{\max }.Math..Math.P_i.Math.\le H,$  wherein m is the total number of the relay node candidate locations outputted in the construction phase of the relay node candidate locations and the threshold H is an upper limit of the number of the sensor nodes covered by one relay node; (3) implementing 1-coverage on the sensor nodes selected in step (1) by using a local search method LSAA of 1-coverage, so that all the sensor nodes are covered by at least two relay nodes; (4) merging this coverage result D and the first 1-coverage result, i.e., T=Y∪D and outputting a final merged result T.

Description

DESCRIPTION OF THE DRAWINGS

[0034] FIG. 1 is a schematic diagram of construction of relay node candidate locations;

[0035] FIG. 2 is a schematic diagram of grouping of sensor nodes;

[0036] FIG. 3 is a schematic diagram of local deployment of relay nodes;

[0037] FIG. 4 shows influences of thresholds on deployment number of relay nodes;

[0038] FIG. 5 shows influences of thresholds on covered times of sensor nodes;

[0039] FIG. 6 shows influences of thresholds on sensor nodes covered by relay nodes;

[0040] FIG. 7 is a schematic diagram of a final output result.

DETAILED DESCRIPTION

[0041] The present invention will be further described in details below in combination with the drawings and the embodiments.

[0042] In the robust coverage method for the relay nodes in the double-layer structure wireless sensor network proposed in the present invention, the main concept is as follows: on the basis of considering the deployment number of the relay nodes, the network load balance and the network robustness, the sensor nodes to be covered are divided into different independent groups, so as to implement first 1-coverage; then, with respect to each group, after the threshold of the algorithm is adjusted, the 1-coverage algorithm is used herein for coverage, so as to ensure that the wireless sensor network satisfies the requirements for the network performance of the deployment number of the relay nodes, the load balance, the robustness, etc.

[0043] The method of the present invention comprises two steps: first 1-coverage and second 1-coverage,

[0044] wherein the step (1) of first 1-coverage comprises a construction phase of relay node candidate deployment locations, a grouping phase of sensor nodes and a local deployment phase, and specifically comprises the following steps:

[0045] (1.1) the construction phase of the relay node candidate deployment locations is shown in FIG. 1;

[0046] (1.1.1) inputting location information X={x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5, x.sub.6, x.sub.7, x.sub.8, x.sub.9} of sensor nodes to be covered;

[0047] (1.1.2) marking the sensor node x.sub.1 as a searched node;

[0048] (1.1.3) constructing a circle using x.sub.1 as a center of the circle and using a communication radius r as a radius, taking four points uniformly on the circumference of the circle, successively searching sensor nodes covered by the four points, taking the points which at least cover two sensor nodes as relay node candidate locations, and selecting a point closest to a base station as a relay node candidate location if the four points only cover one sensor node, wherein the candidate locations on x.sub.1 are respectively P2={x.sub.1, x.sub.7, x.sub.8, x.sub.9}, P3={x.sub.1, x.sub.4, x.sub.5, x.sub.6, x.sub.7} and P2={x.sub.1, x.sub.2, x.sub.3, x.sub.4};

[0049] (1.1.4) repeating steps (1.1.2)-(1.1.3) until X={x.sub.1, x.sub.2, x.sub.3, x.sub.4, x.sub.5, x.sub.6, x.sub.7, x.sub.8, x.sub.9} are fully marked as the searched nodes;

[0050] (1.2) The grouping phase of the sensor nodes is shown in FIG. 2:

[0051] (1.2.1) selecting the location P.sub.i from the relay node candidate locations: the location covers the most uncovered sensor nodes, calling the set formed by all the sensor nodes covered by the location P.sub.i as S.sub.i, and green circles in FIG. 2 being the coverage range of P.sub.i, wherein black points in the green circles are S.sub.i;

[0052] (1.2.2) marking the set of the relay node candidate locations, in P, which cover the sensor nodes in S.sub.i as N.sub.i, calling the set formed by the sensor nodes covered by N.sub.i as T.sub.i and collectively calling all the sensor nodes in the set S.sub.i and the set T.sub.i as a group G.sub.i belonging to the location P.sub.i; black circles in FIG. 2 being N.sub.i, wherein red points are T.sub.i and the black points and the red points jointly form a group G.sub.i;

[0053] (1.2.3) repeating steps (1.2.1)-(1.2.2) until all the sensor nodes are distributed to a certain group.

[0054] (1.3) The grouping phase of local deployment is shown in FIG. 3:

[0055] (1.3.1) successively (starting from 1) selecting the groups G.sub.i belonging to the location P.sub.i from G and searching all the relay node candidate locations F.sub.i that cover the sensor nodes in G.sub.i from P, thereby converting a geometric disc coverage (GDC) problem into a minimum set coverage (MSC) problem;

[0056] (1.3.2) searching a minimum set coverage MSC.sub.i of (G.sub.i−S.sub.i) from F.sub.i by using a greedy algorithm and defining the weight of P.sub.i as w.sub.i=|C|, wherein C is the relay node candidate location uncovered by MSC.sub.i in N.sub.i; if w.sub.i>0, then selecting MSC.sub.i and P.sub.i as local deployment results; if w.sub.i=0 and P.sub.i contains sensor nodes only covered by P.sub.i, then selecting MSC.sub.i and P.sub.i as local deployment results; if w.sub.i=0 and P.sub.i contains the sensor nodes uncovered by P.sub.i, then selecting MSC.sub.i as a local deployment result; recording this local search result as Y.sub.i; in FIG. 3, green circles are P.sub.i, wherein red circles indicate MSC.sub.i. It can be seen that one location in N.sub.i is not covered by MSC.sub.i, so the weight of the location is: w.sub.i=1>0. Therefore, MSC.sub.i and P.sub.i are selected as local deployment results, i.e., the red circles and the green circles are selected as the local deployment results;

[0057] (1.3.3) repeating steps (1.3.1)-(1.3.3), searching G.sub.i+1, storing the minimum set coverage of each group, i.e., Y=Y∪Y.sub.i until the sensor nodes of each group are covered, and outputting a final search result Y.

[0058] Step (2) of the second 1-coverage phase specifically comprises the following steps:

[0059] (2.1) selecting the sensor nodes X′={x′.sub.1, x′.sub.2, . . . , x′.sub.l}, 1≦l≦n covered by just one relay node from the first 1-coverage result;

[0060] (2.2) according to the network performance requirement of the wireless sensor network for the deployment number of the relay nodes, the network load balance, the network robustness, etc., manually adjusting the threshold H of the relay node to obtain max

[00005]$\underset{1\le i\le m}{\max }.Math..Math.P_i.Math.\le H,$

wherein m is the total number of the relay node candidate locations; and the threshold represents an upper limit of the number of the sensor nodes covered by each relay node candidate location. FIGS. 4-6 show influences of thresholds on the deployment number of relay nodes, influences of thresholds on the covered times of sensor nodes by the relay nodes and influences of thresholds on the number of sensor nodes covered by relay nodes; the threshold H is adjusted according to the requirement of a specific network environment for the performance, so as to ensure good network performance;

[0061] (2.3) implementing 1-coverage on the sensor nodes selected in step (2.1) by using a local search method of the first 1-coverage, so that all the sensor nodes are covered by at least two relay nodes;

[0062] (2.4) merging this coverage result D and the first 1-coverage result, i.e., T=Y∪D and outputting a final merged result T.

[0063] FIG. 7 is a schematic diagram of a final output result, wherein a blue curve indicates the grouping of the sensor nodes. It can be seen that each sensor node in the groups is covered by at least two relay nodes. Therefore, the influence of the failure of the relay nodes on the entire network is reduced, thereby improving the network robustness, wherein green circles belong to the coverage range of the relay nodes outputted by 1-coverage and red circles belong to the coverage range of the relay nodes outputted by 2-coverage. Meanwhile, the number of the sensor nodes covered by each relay node is not allowed to exceed a set threshold. Therefore, the method proposed in the present invention can further ensure the load balance on the basis of improving the robustness of the wireless sensor network.