KR101580766B1 - Method and Device for Estimating WSN Connectivity Hazard - Google Patents

Abstract

Disclosed is a device and method for estimating a connectivity weak point in a wireless sensor network including a server and a plurality of nodes. The disclosed connectivity vulnerable point estimation method includes deactivating a randomly selected selection node and a neighboring node within a predetermined number of hops from the selected node in a first cluster, which is a set of connected node-to-node identification information; Determining connectivity from a predetermined border node among nodes connected to the inactive node; Generating at least one second cluster divided from the first cluster according to the determination result; And estimating a connectivity weak point of the wireless sensor network using the first and second clusters.

Description

Technical Field [0001] The present invention relates to a method and apparatus for estimating connectivity of a wireless sensor network,

BACKGROUND OF THE INVENTION 1. Field of the Invention [0002] The present invention relates to an apparatus and method for estimating connectivity points of a wireless sensor network, and more particularly, to an apparatus and method for estimating connectivity points of a wireless sensor network including a server and a plurality of nodes.

In wireless ubiquitous environment, various methods for forming a sensor network as a connection between a sensor node and another sensor node are proposed. These various sensor network schemes have been studied as a major way of constructing a sensor network in a local form or a small form and a method of constructing a whole network in a wide form, and a wireless adhoc system or an Internet protocol : IP) network method is partially applied.

A structured tree type is widely used as a method of transmitting data to a desired sensor node by combining sensors having limited functions and limited power with the network. In this type of structured tree, the sensor node is spread and distributed to the desired application area, and the number of the upper node and the lower node is determined, and the intermediate nodes are set as links between the parent node and the child node. And a logical identifier (ID) is assigned to each node to manage the node. One such example is the IEEE 802.15.4 standard.

Meanwhile, it is an important issue to establish an accurate and efficient path for communication between nodes in a wireless sensor network environment. However, considering the limited energy of the sensor node, routing research for maximizing the lifetime of the network becomes more important . The network lifetime can be defined up to a point where a certain number of source nodes can not find the data delivery path and in the worst case can be defined up to a time when the service of the entire sensor network is impossible. For example, when 100% of all information in the target service area is transmitted, the network lifetime is up to 70% of the time when information is maintained. Therefore, research on low power consumption and network lifetime is an important task in wireless sensor networks.

In order to increase the lifetime of a wireless sensor network, information sensed by an arbitrary sensor node must be transmitted to a sink node. This means that any sensor network connectivity is ensured so that no sensor is isolated and data of the sensor itself can be transmitted correctly to the sink node. The lifetime of a wireless sensor network can be increased if a connection point is weakly estimated in advance in a wireless sensor network.

In this paper, we propose a cluster-based backbone generation algorithm considering the energy and connectivity of nodes in a wireless sensor network, Korea Internet Information Society (Oct. 5, 2009), 2009. 10

SUMMARY OF THE INVENTION The present invention is directed to a method and apparatus for estimating connectivity vulnerability points of a wireless sensor network to increase the lifetime of the wireless sensor network.

According to an aspect of the present invention, there is provided a method for estimating a weak point of a connection in a wireless sensor network including a server and a plurality of nodes, Deactivating a randomly selected node and a neighboring node within a predetermined number of hops from the selected node; Determining connectivity from a predetermined border node among nodes connected to the inactive node; Generating at least one second cluster divided from the first cluster according to the determination result; And estimating a connectivity weak point of the wireless sensor network using the first and second clusters.

According to another aspect of the present invention, there is provided a method for estimating a connection weak point in a wireless sensor network including a server and a plurality of nodes, Creating the first cluster to which the cluster identification information is assigned, the first cluster being indicative of connectivity; Deactivating, in the first cluster, a randomly selected selection node and a neighboring node within a predetermined number of hops from the selection node; Generating at least one second cluster divided from the first cluster according to the inactivation; And estimating a connectivity vulnerability point of the wireless sensor network by comparing cluster identification information of the first and second clusters, wherein the cluster identification information includes at least one of a connection weak point estimation method .

According to another aspect of the present invention, there is provided a connection weak point estimation apparatus for a wireless sensor network including a server and a plurality of nodes, A node deactivator for deactivating a randomly selected node and a neighboring node within a predetermined number of hops from the selected node; A connectivity determiner for determining connectivity from a predetermined border node among nodes connected to the deactivated node; A cluster generator for generating at least one second cluster divided from the first cluster according to the determination result; And a weak point estimating unit that estimates a weak point of connectivity of the wireless sensor network using the first and second clusters.

According to the present invention, after forming a cluster, which is a set of channel identification information between nodes connected in a wireless sensor network, deactivating a neighbor node within a predetermined number of hops from a selected node and a selected node randomly selected in the cluster, Can be estimated.

Also, according to the present invention, a cluster for estimating connectivity vulnerability points is generated using inter-node channel identification information, not a node, so that the amount of computation for estimating connectivity vulnerability points can be reduced.

FIG. 1 and FIG. 2 are views for explaining the concept of a connection weak point estimation method of a wireless sensor network according to the present invention.
3 and 4 are views for explaining a connection weak point estimation method of a wireless sensor network according to an embodiment of the present invention.
5 and 6 are views for explaining a cluster generation method according to an embodiment of the present invention.
7 is a diagram for explaining a connection vulnerability point estimation apparatus of a wireless sensor network according to an embodiment of the present invention.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that the invention is not intended to be limited to the particular embodiments, but includes all modifications, equivalents, and alternatives falling within the spirit and scope of the invention. Like reference numerals are used for like elements in describing each drawing.

Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings.

FIG. 1 and FIG. 2 are views for explaining the concept of a connection weak point estimation method of a wireless sensor network according to the present invention.

As shown in FIG. 1, a wireless sensor network includes a server 110 or a sink node and a plurality of sensor nodes 150. Each of the plurality of sensor nodes 150 transmits and receives sensed data and transmits the sensed data to the server 110 or the sink node.

At this time, the specific node 130 may be connected to the node 121 of the first node set 120 and the node 141 of the second node set 140. Therefore, if the connection between the specific node 130 and the nodes 121 and 141 is broken, not only the data of the specific node 130 but also the sensing data of the second node set 140 can be transmitted to the server 110. In other words, the specific node 130 is a weak point of connectivity of the wireless sensor network shown in FIG. 1, and the present invention estimates a weak point of connectivity such as the specific node 130. The connectivity vulnerability point may be at least one or more nodes.

As shown in FIG. 1, in the case of a sensor network in which there are not many nodes, there is not a large amount of computation required to estimate a connection vulnerability point. However, when there are a large number of sensor nodes 160 as shown in FIG. 2, Can be greatly increased.

The present invention forms a cluster which is a set of inter-node channel identification information connected in a wireless sensor network as shown in FIGS. 1 and 2, and deactivates a neighbor node within a predetermined number of hops from a selected node and a selected node randomly selected in the cluster We estimate the connectivity weak points of the wireless sensor network. It repeatedly selects a node at random and deactivates it, and judges whether there is a node whose data is not transmitted by the inactivated node, thereby estimating a connection weak point. When the selected node and the neighboring node are deactivated, the channel connected to the selected node and the neighboring node is inactivated. In the present invention, the cluster for estimating the connectivity weak point is generated using the inter- The amount of computation for estimation can be reduced.

Meanwhile, the method for estimating connectivity vulnerability points according to the present invention can be performed through simulation for a wireless sensor network, and can be performed in a terminal device including a server, a sink node or a processor storing information on a wireless sensor network have.

Hereinafter, a connection weak point estimation method performed in the server will be described as an embodiment.

3 and 4 are views for explaining a connection weak point estimation method of a wireless sensor network according to an embodiment of the present invention.

Referring to FIG. 3, in step S310, the server deactivates a neighbor node within a predetermined number of hops from a selected node and a selected node randomly selected in a first cluster, which is a set of inter-node channel identification information. In step S320, the connectivity is determined from a predetermined boundary node among the nodes connected to the deactivated node in step S320, and at least one second cluster divided from the first cluster is generated in step S330 according to the determination result. Then, the first and second clusters are used to estimate a connection vulnerability point of the wireless sensor network (S340).

4, a solid line connecting each of the server 410 and the plurality of nodes 420 in FIG. 4 represents a connected channel. Channel identification information such as e1, e2, and e3 is given to the channel, and the first cluster represents the set of channel identification information. As a result, the first cluster indicates the channel-to-channel connectivity of the server 410 and the plurality of nodes 420, respectively.

In Fig. 4, if node A is a select node and the number of hops that can be selected from 0 and natural numbers is zero, node A may be deactivated. If the predefined number of hops is one, nodes B and C may be deactivated as neighboring nodes. The deactivation of the selected node deactivates the channel associated with the selected node. When the node A is inactivated, the channels e2 and e3 are deactivated and the second cluster 421 divided from the first cluster may be generated. And the second cluster 421 may be an identification information set for the channels connected between the nodes C to G. [

At this time, the number of inactive nodes may be determined according to a predetermined level. For example, at level 1, only the selected node is deactivated. At level 2, the neighbor node with the selected node and 1 hops is deactivated, while at the level 3, the selected node and the neighbor with 2 hops are deactivated. Therefore, the number of hops can be determined according to a predetermined level. The server 410 may deactivate the selected node and the neighboring node while raising the level if the second cluster 421 is not created at the level 1.

As a result, the data of the node included in the second cluster 421 can not be transmitted to the server 410, and the server 410 can estimate the node A as a vulnerability point using the first and second clusters . For example, if there is a separate node connecting a node B and a node C, i.e., a channel exists, the data of node C can be transferred to the node B, so that the node A is not estimated as a vulnerable point.

Meanwhile, the first and second clusters may include cluster identification information, and the cluster identification information may be a selected one of the channel identification information. For example, the cluster identification information of the first cluster may be e1, and the cluster identification degree of the second cluster may be e4. The server 410 compares the cluster identification information of the first and second clusters. If the cluster identification information is different, the server 410 can confirm the existence of a new cluster. Since a new cluster is created by the inactive node A, It can be assumed that the connection is vulnerable.

5 and 6 are views for explaining a cluster generation method according to an embodiment of the present invention.

The server generates connectivity information for the channel between the connected nodes (S510). Here, the connectivity information includes channel identification information for a connected channel and node identification information for a node connected to the channel. The connectionability can be determined by transmitting / receiving data between nodes. A to G shown in Fig. 4 represent node identification information. Then, the server generates the first cluster to which the cluster identification information is allocated, indicating the inter-channel connectivity using the channel identification information (S520).

The case of the second cluster may also be generated as described above, but it may be generated from the connectivity determination of the border node connected to the deactivated node, since it is in the form of being divided from the first cluster. That is, connectivity information for the inter-node channel connected from the border node can be generated, and the second cluster can be created.

Meanwhile, the cluster identification information may be channel identification information for a channel physically closest to the server, among the channel identification information, and the border node may include a node identification information value among the nodes connected to the inactive node It may be the smallest node. Table 1 below shows a part of node information, connectivity information, and cluster information for the second cluster 421 shown in FIG. 4 as an embodiment.

Node information: {node identification information, coordinate information} {C (0,0)}, {D (0, 1)}, Connectivity information: {channel identification information, channel connection node, representative identification information} {e4, (C, E), e4}, {e5 (E, G), e4} Cluster information: {cluster identification information, channel identification information} {e4, <e4, e5, e6, e7, e8, e9, e10>

Meanwhile, FIG. 6 is a graph showing channel connectivity of the second cluster 421 shown in FIG. 4, in which channels of the second cluster 421 are connected in a tree structure as shown in FIG. 6 (a) have. As a result, since all the channels are connected, the channel-to-channel connectivity can be shown by connecting a plurality of channel identification information around one channel identification information e4 as shown in FIG. 6 (b). When the cluster is expressed as shown in FIG. 6 (b), the amount of computation can be reduced because the tree structure is simplified.

The method for estimating connectivity weak points according to another embodiment of the present invention according to the cluster generation method illustrated in FIGS. 5 and 6 is as follows. The server generates a first cluster to which the cluster identification information is allocated and represents the inter-channel connectivity using the channel identification information between the connected nodes, and in the first cluster, a randomly selected node and a neighbor within a predetermined number of hops from the selected node Disable the node. At least one second cluster divided from the first cluster is generated according to the inactivity and the cluster identification information of the first cluster and the second cluster is compared to estimate a weak point of connectivity of the wireless sensor network.

7 is a diagram for explaining a connection vulnerability point estimation apparatus of a wireless sensor network according to an embodiment of the present invention. The connectivity vulnerability point estimation apparatus may be a server of the wireless sensor network described above or a user terminal performing simulation.

7, the connectivity weak point estimation apparatus according to the present invention includes a node deactivator 710, a connectivity determiner 720, a cluster generator 730, and a weak point estimator 740.

The node deactivation unit 710 deactivates a randomly selected node and a neighboring node within a predetermined number of hops from the selected node in the first cluster, which is a set of connected node-to-node identification information. The number of hops can be selected from 0 and natural numbers.

The connectivity determining unit 720 determines connectivity from a predetermined boundary node among the nodes connected to the deactivated node, and the cluster generating unit 730 generates at least one second cluster divided from the first cluster according to the determination result do. The cluster generating unit 730 may also generate the first cluster.

The weak point estimating unit 740 estimates the weak points of connectivity of the wireless sensor network using the first and second clusters and compares the cluster identification information of one cluster and the second cluster as one embodiment, If the cluster identification information of the first and second clusters is different, it is possible to estimate the selected node and the neighboring node as a weak point of connectivity. And the cluster identification information may be selected identification information among the channel identification information.

In addition, the first and second clusters can connect the plurality of channel identification information with one channel identification information as a center to indicate the inter-channel connectivity.

The above-described technical features may be implemented in the form of program instructions that can be executed through various computer means and recorded in a computer-readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions recorded on the medium may be those specially designed and constructed for the embodiments or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. Examples of program instructions include machine language code such as those produced by a compiler, as well as high-level language code that can be executed by a computer using an interpreter or the like. The hardware device may be configured to operate as one or more software modules to perform the operations of the embodiments, and vice versa.

As described above, the present invention has been described with reference to particular embodiments, such as specific elements, and specific embodiments and drawings. However, it should be understood that the present invention is not limited to the above- And various modifications and changes may be made thereto by those skilled in the art to which the present invention pertains. Accordingly, the spirit of the present invention should not be construed as being limited to the embodiments described, and all of the equivalents or equivalents of the claims, as well as the following claims, belong to the scope of the present invention .

Claims (14)

A method for estimating a weak point in a wireless sensor network including a server and a plurality of nodes,
Deactivating a randomly selected selection node and a neighboring node within a predetermined number of hops from the selection node, in a first cluster, which is a set of connected node-to-node identification information;
Determining connectivity from a predetermined border node among nodes connected to the inactive node;
Generating at least one second cluster divided from the first cluster according to the determination result; And
Estimating a connectivity vulnerability point of the wireless sensor network using the first and second clusters
The method comprising the steps of:
The method according to claim 1,
The step of estimating the connectivity weak point
Comparing the cluster identification information of the first cluster and the second cluster to estimate the connectivity weak point,
And the cluster identification information is the identification information selected from the channel identification information
A method for estimating connectivity vulnerability points.
3. The method of claim 2,
The step of estimating the connectivity weak point
When the cluster identification information of the first and second clusters is different, the selecting node and the neighboring node are estimated to be the connectivity weak point
A method for estimating connectivity vulnerability points.
3. The method of claim 2,
Further comprising generating the first cluster,
The step of creating the first cluster
Generating connectivity information for the connected inter-node channel; And
And using the channel identification information to generate the first cluster to which the cluster identification information is assigned, the first cluster indicating the inter-channel connectivity,
Wherein the connectivity information includes the channel identification information and node identification information for a node connected to the channel
A method for estimating connectivity vulnerability points.
5. The method of claim 4,
The first cluster
A plurality of channel identification information is connected to one channel identification information,
A method for estimating connectivity vulnerability points.
5. The method of claim 4,
The cluster identification information
Among the channel identification information, channel identification information for a channel physically closest to the server
A method for estimating connectivity vulnerability points.
5. The method of claim 4,
The border node
The node having the lowest node ID value among the nodes connected to the deactivated node
A method for estimating connectivity vulnerability points.
3. The method of claim 2,
The step of creating the second cluster
Generating connectivity information for an inter-node channel connected from the border node; And
And using the channel identification information to generate the second cluster to which the cluster identification information is assigned, the second cluster indicating the inter-channel connectivity,
The connectivity information includes the channel identification information, node identification information for a node connected to the channel,
A method for estimating connectivity vulnerability points.
9. The method of claim 8,
The second cluster
A plurality of channel identification information is connected to one channel identification information,
A method for estimating connectivity vulnerability points.
A method for estimating a weak point in a wireless sensor network including a server and a plurality of nodes,
Generating a first cluster to which the cluster identification information is allocated, the first cluster indicating the inter-channel connectivity using the channel identification information between connected nodes;
Deactivating, in the first cluster, a randomly selected selection node and a neighboring node within a predetermined number of hops from the selection node;
Generating at least one second cluster divided from the first cluster according to the inactivation; And
And comparing the cluster identification information of the first and second clusters to estimate a connectivity vulnerability of the wireless sensor network,
Wherein the cluster identification information is selected identification information of the channel identification information.
1. A connection weak point estimation apparatus of a wireless sensor network including a server and a plurality of nodes,
A node deactivation unit for deactivating a randomly selected selection node and a neighboring node within a pre-set hop count from the selected node, in a first cluster, which is a set of channel identification information between connected nodes;
A connectivity determiner for determining connectivity from a predetermined border node among nodes connected to the deactivated node;
A cluster generator for generating at least one second cluster divided from the first cluster according to the determination result; And
A weak point estimating unit estimating a weak point of connectivity of the wireless sensor network using the first and second clusters,
Wherein the connection weak point estimation unit comprises:
12. The method of claim 11,
The weak point estimation unit
Comparing the cluster identification information of the first cluster and the second cluster to estimate the connectivity weak point,
And the cluster identification information is the identification information selected from the channel identification information
Connectivity weak point estimation device.
13. The method of claim 12,
The weak point estimation unit
When the cluster identification information of the first and second clusters is different, the selecting node and the neighboring node are estimated to be the connectivity weak point
Connectivity weak point estimation device.
13. The method of claim 12,
The first cluster
A plurality of channel identification information is connected to one channel identification information,
Connectivity weak point estimation device.

Images