CN114615676B - Gateway deployment method of self-organizing network - Google Patents

Abstract

The present invention provides a gateway deployment method for a self-organizing network. The method comprises: step 1: determining all nodes located in the outermost layer of the self-organizing network, recorded as outermost nodes; connecting all the outermost nodes end to end to form a closed network area; step 2: dividing the closed network area into a plurality of quadrilateral areas; step 3: selecting four different colors, coloring all quadrilateral vertices; wherein the colors of the four vertices of the same quadrilateral should be different from each other; step 4: selecting one of the four colors, and using the node corresponding to the selected color as a gateway. The present invention can greatly reduce the gateway deployment cost and enable all nodes to be covered by the gateway, thereby improving the coverage rate of the gateway.

Description

A gateway deployment method for self-organizing network

Technical Field

The present invention relates to the technical field of self-organizing networks, and in particular to a gateway deployment method of a self-organizing network.

Background technique

A self-organizing network is a self-organizing, multi-hop, wireless communication network composed of many sensor nodes. Each node in the network can be used as both a router and a common host. In order to solve the problem of self-organizing networks accessing the Internet, gateway devices are usually used to interconnect different types of nodes. The gateway device forwards data for the nodes. Due to the limited coverage of a single gateway, a single gateway cannot provide comprehensive coverage of the entire network area, which will reduce the connectivity of the network. Therefore, whether the gateway deployment is reasonable has a great impact on network performance.

At present, there are two main methods for gateway deployment based on coverage: one is to increase the number of gateways to improve the coverage of gateways, but due to the high cost of gateway deployment, too many gateways will cause overlapping of gateway coverage and waste of resources. The other method uses the set coverage algorithm to obtain the coverage circle that can cover all nodes, and finally adjusts the radius of the maximum circle as the optimization target, but it will cause the gateway coverage radius to be too large and the network service quality to decline.

Summary of the invention

In order to solve the problems of limited coverage of a single gateway and high cost of deploying multiple gateways, the present invention provides a gateway deployment method based on coverage when the node is static, with the goal of reducing the number of gateways and maximizing the gateway coverage. The ideas of four-corner decomposition and four-coloring are used to solve the gateway deployment problem based on coverage in a self-organizing network.

The present invention provides a gateway deployment method for a self-organizing network, comprising:

Step 1: Determine all nodes in the outermost layer of the self-organizing network, which are recorded as outermost nodes; connect all outermost nodes end to end to form a closed network area;

Step 2: Divide the closed network area into a number of quadrilateral areas;

Step 3: Select four different colors and color all the vertices of the quadrilaterals. The colors of the four vertices of the same quadrilateral should be different.

Step 4: Select one of the four colors and use the node corresponding to the selected color as the gateway.

Furthermore, step 2 specifically includes:

The closed network area is regarded as a plane polygon, the outermost nodes in the self-organizing network are the vertices of the plane polygon, and the remaining nodes in the self-organizing network are located inside the plane polygon;

Taking two vertices as a group, all vertices of the planar polygon are divided into a number of vertex pairs; for each vertex pair, lines are connected between the two vertices to divide the planar polygon into a number of quadrilateral areas; wherein the lines between the vertex pairs do not intersect each other.

Furthermore, the planar polygon is a convex polygon.

Furthermore, step 4 specifically includes:

Count the number of vertices of each color, and record the sets of vertices of the first color, the second color, the third color, and the fourth color as T1, T2, T3, and T4, respectively; where T1≤T2≤T3≤T4;

Nodes in the first color set are selected as gateways, and the coverage radius of each gateway is set so that it can cover a pre-given coverage area.

Beneficial effects of the present invention:

The present invention provides a gateway deployment method for a self-organizing network, which can greatly reduce the gateway deployment cost and enable all nodes to be covered by the gateway, thereby improving the gateway coverage rate and solving the problem that nodes in the self-organizing network cannot be completely covered by the gateway or the deployment cost is high.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a flow chart of a gateway deployment method for a self-organizing network provided by an embodiment of the present invention;

FIG2 is a schematic diagram of forming a closed network area according to an embodiment of the present invention;

FIG3 is a schematic diagram of dividing a closed network area into a plurality of quadrilateral areas provided by an embodiment of the present invention;

FIG4 is a schematic diagram of dyeing four vertices of a quadrilateral with different colors according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of selecting a network node according to an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solution and advantages of the present invention clearer, the technical solution in the embodiment of the present invention will be clearly described below in conjunction with the drawings in the embodiment of the present invention. Obviously, the described embodiment is a part of the embodiment of the present invention, not all the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without making creative work are within the scope of protection of the present invention.

As shown in FIG1 , an embodiment of the present invention provides a gateway deployment method for a self-organizing network, comprising the following steps:

S101: constructing a network model, specifically: as shown in FIG2 , keeping the randomly distributed nodes in a static state, determining all nodes located in the outermost layer of the self-organizing network, and recording them as outermost nodes; connecting all the outermost nodes end to end to form a closed network area;

Specifically, assuming that the nodes are randomly distributed, each node can use node positioning technology to obtain its own location. Each node in the self-organizing network can communicate with other nodes in a multi-hop manner, so each node not only knows its own node, but also knows the location of other nodes to determine the outermost node. The node positioning technology can adopt the existing mature positioning method, which will not be repeated here.

S102: quadrangular decomposition based on the network model, specifically: dividing the closed network area into a plurality of quadrangular areas;

Specifically, as shown in Figure 3, the closed network area is regarded as a planar polygon, the outermost nodes in the self-organizing network are the vertices of the planar polygon, and the remaining nodes in the self-organizing network are located inside the planar polygon; with two vertices as a group, all the vertices of the planar polygon are divided into several groups of vertex pairs; for each group of vertex pairs, lines are connected between the two vertices to divide the planar polygon into several quadrilateral areas; wherein the lines between the several groups of vertex pairs do not intersect each other.

Preferably, the planar polygon is a convex polygon, so that the line between any two vertices is located inside or on the edge of the polygon. The quadrilateral in this embodiment refers to a convex polygon with four corners. The line between two vertices is an open line segment and falls completely inside the planar polygon.

It is understandable that triangulation, pentagonal dissection, etc. may also be performed based on the network model. In consideration of reducing the number of gateways as much as possible and achieving full coverage as much as possible, quadrangular dissection is selected in this embodiment.

S103: Four-coloring based on quadrilateral decomposition, specifically: select four different colors and color all the vertices of the quadrilateral; wherein the colors of the four vertices of the same quadrilateral should be different from each other;

As shown in FIG4 , the vertices of each quadrilateral are colored red, yellow, blue, and green respectively.

It should be noted that there is a corresponding relationship between the decomposition method of step S102 and the coloring method of step S103; for example, if triangulation is selected, three-coloring is adopted; if pentagonal decomposition is adopted, five-coloring is adopted; in this embodiment, since step S102 adopts the quadrangular decomposition method, this step adopts the four-coloring method.

S104: Gateway location selection: select one of the four colors, and use the node corresponding to the selected color as the gateway.

If the traditional gateway deployment method is adopted, N gateways need to be deployed. Then, by adopting the four-corner dissection and four-coloring method of the present application, the number of gateways has actually been reduced from N to N/4. In other words, the number of gateway deployments has been greatly reduced while ensuring full coverage, thereby saving deployment costs. Therefore, at this time, the node corresponding to any one of the four colors can be arbitrarily selected as the gateway. For example, as shown in Figure 5, in this embodiment, the node colored blue is selected as the gateway node. As can be seen from Figure 5, the gateway deployment method of the present invention can achieve full coverage of all nodes.

In addition, in order to further reduce the number of gateway deployments, as an implementable method, the following method can be used to select the gateway:

Count the number of vertices of each color, and record the sets of vertices of the first color, the second color, the third color, and the fourth color as T1, T2, T3, and T4, respectively; where T1≤T2≤T3≤T4;

Nodes in the first color set are selected as gateways, and the coverage radius of each gateway is set so that it can cover a pre-given coverage area.

For example, assuming that T1 is a set of red vertices, T2 is a set of yellow vertices, T3 is a set of blue vertices, T4 is a set of green vertices, and T1≤T2≤T3≤T4, since the network coverage of the gateway can be adjusted, the node in the color set with the least nodes can be selected as the gateway, and then the coverage radius of each gateway is combined so that it can cover the pre-given coverage area, thereby ensuring full coverage of all nodes.

Since the coverage of a single gateway is limited, a single gateway may not be able to provide full coverage of the entire network area. Increasing the number of gateways can effectively improve the connectivity of the network, but due to the high deployment cost of the gateway, the number of gateways in the actual network needs to be controlled. To this end, the solution of the present invention aims to achieve full coverage of the network area by the gateway while reducing the number of gateways.

Compared with the traditional gateway deployment method, the present invention can reduce the number of gateways from N to N/4 because: the present invention modeled the gateway deployment problem as an art gallery problem, abstracted the closed network model into a plane polygon P containing N vertices, and performed quadrilateral decomposition and quad-coloring on the plane polygon P. We chose red, yellow, blue and green to color the vertices. Assuming that T1 is the set of red vertices, T2 is the set of yellow vertices, T3 is the set of blue vertices, T4 is the set of green vertices, and T1≤T2≤T3≤T4, we chose T＝T3, which means T represents the set of gateway nodes. For any point d in P, there is a point b in the quadrilateral of P that belongs to T. Since each quadrilateral in the model is a convex polygon, the line segment /> Belongs to P, that is, the gateways are placed in the same color position, which can cover the entire area. The upper limit of the number of gateways is/> It can be seen from this that the gateway deployment method of the present invention can determine the minimum number of gateways and the optimal gateway position that meet the node coverage requirements, and can solve the problem that nodes in the self-organizing network cannot be fully covered by the gateway when using fewer gateways, thereby improving the gateway coverage rate; and, the gateway deployment method of the present invention reduces the number of gateways while meeting the full coverage of the nodes, thereby reducing the gateway deployment cost.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit it. Although the present invention has been described in detail with reference to the aforementioned embodiments, those skilled in the art should understand that they can still modify the technical solutions described in the aforementioned embodiments, or make equivalent replacements for some of the technical features therein. However, these modifications or replacements do not deviate the essence of the corresponding technical solutions from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (3)

1. A gateway deployment method for a self-organizing network, characterized by comprising: Step 1: Determine all nodes in the outermost layer of the self-organizing network, which are recorded as outermost nodes; connect all outermost nodes end to end to form a closed network area; Step 2: Divide the closed network area into a number of quadrilateral areas; specifically comprising: regarding the closed network area as a plane polygon, the outermost nodes in the self-organizing network are the vertices of the plane polygon, and the remaining nodes in the self-organizing network are located inside the plane polygon; taking two vertices as a group, all vertices of the plane polygon are divided into a number of vertex pairs; for each group of vertex pairs, connecting lines between the two vertices to divide the plane polygon into a number of quadrilateral areas; wherein the connecting lines between the groups of vertex pairs do not intersect each other; Step 3: Select four different colors and color all the vertices of the quadrilaterals. The colors of the four vertices of the same quadrilateral should be different. Step 4: Select one of the four colors and use the node corresponding to the selected color as the gateway. 2. A gateway deployment method for a self-organizing network according to claim 1, characterized in that the planar polygon is a convex polygon. 3. The gateway deployment method of a self-organizing network according to claim 1, wherein step 4 specifically comprises: Count the number of vertices of each color, and record the sets of vertices of the first color, the second color, the third color, and the fourth color as T 1, T 2, T 3, T 4, respectively; where T 1≤ T 2≤ T 3≤ T 4; Nodes in the first color set are selected as gateways, and the coverage radius of each gateway is set so that it can cover a pre-given coverage area.