KR20100041003A - The vine tree formed dual path clustering tree wireless network and its constructing way - Google Patents

Abstract

Compared to the wireless disjoint node multi-path routing protocol, which seeks multiple paths from the source node to the sink node to reduce packet loss due to wireless node error, the present invention provides a Vine Tree ( The wireless communication reliability is increased by constructing a network by arranging a wireless trunk in a portion corresponding to a tree structure, that is, a tree branch.

In addition, the wireless trunk has two backbone communication paths, a primary backbone communication path and a backup backbone communication path. The sink node corresponds to the root of the tree and the branch of the tree is connected to the wireless trunk in the cluster environment, and its connection point has the primary cluster head of the primary backbone path and the backup cluster head of the backup backbone path.

In particular, the present invention manages the topology of a clustering-based wireless network. The minimized set of source nodes is bound and coordinated by the cluster heads, and the cluster heads and source nodes operate based on the master / slave model. The source node, which is considered to be a slave device, is placed in a low power consumption mode until it receives a command from the cluster head, which is the master device, and the cluster head, which is the master device, receives the value read from the source node. A feature of this technology is that it enables the construction of a large number of wireless clustering network sets that cover a wide range of overcoming the overall lack of wide area communications.

Also, in the present invention, the network system uses network clustering having two cluster heads to overcome network errors, in particular, the cluster head error. The two cluster heads are an active cluster head called a main cluster head, and a main cluster head. The backup cluster head is activated when an error occurs. Source nodes within a cluster are connected to the primary cluster head and a spare connection to the backup cluster head is established. The primary backbone tree with the sink node as the root consists of each connection of a series of primary cluster heads, and so is the backup backbone tree.

Compared with the existing technology, the present invention applies a master / slave model for managing wireless nodes in a cluster, thereby reducing the influence of hidden terminal and exposed terminal problems, It helps to reduce the power consumption on both sides of the cluster head. Especially, error correction and priority path selection greatly reduces the network congestion that increases due to the complexity and size of the network.

Description

Vine Tree formed Dual Path Clustering Tree Wireless Network and Its constructing way}

The present invention relates to wireless data networks, and particularly includes fault tolerance management to improve communication reliability of cluster-based wireless communication networks.

Wireless communication networks are expected to have a significant impact on the efficiency of many applications, such as agricultural environment monitoring and weather forecasting. In such a wireless communication system, data is gathered by a number of wireless nodes placed within the sphere of influence, and the wireless node data is sent to a processing device. When using multiple wireless nodes, clustering is a good way to facilitate configuration of the wireless node and management of the network. Wireless node clustering configuration means minimizing the set of wireless nodes managed by the cluster head. The cluster head is responsible for controlling the activation state of the wireless node and reading the value periodically as intended. The cluster head transmits the values gathered from the wireless nodes to remote sink nodes for processing.

In a clustering network, if a cluster head fails, all radio nodes in that cluster head are also considered inoperative. If the cluster head in the middle of the network fails, this causes a bigger problem. In this case, the rest of the network that does not contain the sync node is considered to be an error.

There are several ways to solve the wireless node failure problem in a wireless cluster network, one of which is to create an extra path from the source node to the sink node. Then copy the data from the source node or split it into pieces and send them through multiple paths. A common technique to which the aforementioned model is applied is the disjoint node multi-path routing protocol . However, this multipath routing model requires a lot of power to process data at the source node and also makes the protocol configuration more complicated. Another technique is to create a backup path and save it until the main path has a problem. The backup path takes over the role of the main path when the main path fails. This technique is applied according to the degree of reliability required by a particular application.

The present invention relates to a dual path clustering tree (DPCT) wireless network in the form of a Vine Tree based on a "double tree" structure in combining several wireless node clusters. The DPCT network consists of one or more optional auxiliary trees, which protect the main tree from network node failures by ensuring reliability and fault tolerance for application requests. In the present invention, an error recovery method is planned to secure higher communication reliability, and reliability can be increased by simplifying management and configuration of a wireless network.

There are two methods (steps 98 and 99) to correct errors in the event of a network failure. Each cluster head keep-alive message by using the (Keep-Alive message) to check whether there is a cluster head is operating. If the cluster head is not working properly, the tree failover mechanism works to match the backbone path to the cluster head. The operation of the mechanism is described with reference to Figs. 5A, 5B and 5C. Network error information is sent to sink nodes in the database of modified or superficially active trees.

An example of applying the present invention to an application program is as follows.

the sink node through the hops (hop-by-hop) method - a) the "nongsuro Monitoring System", a radio trunk that contains multiple cluster head with a water level sensor mounted (Wireless Trunk) collects the water level information, hop-by It is then placed over a long distance to deliver the water level through the Remote Terminal Unit and finally to the Processing Center .

     b) In a "wireless weather forecast system", a wireless trunk includes several cluster heads that collect weather information from assigned environmental sensors. The "wireless weather forecast system" can replace the existing wired weather forecast system with low installation and maintenance costs while improving the flexibility of the weather forecast system.

c) In a "power / industrial IT system", a wireless trunk includes several wireless gateways (think cluster heads). Each gateway will manage the equipment of a power IT system or an industrial IT system. With the support of wireless technology, the system provides better mobility for slave devices and reduces installation and maintenance costs.

1 illustrates a system structure of a dual path clustering tree ( DPCT ) network. In this structure, each sensing device 100 is grouped into clusters 40, 50, and 60, and has only short-range communication capability. It collects environmental information such as temperature, humidity, pressure, and more. Every cluster 40, 50, 60 has a primary cluster head (PCH: Primary Cluster Head 15, 25, 35) that manages source nodes in the cluster and includes routing tables for all source nodes in the cluster.

The path from the sink node 75 through the two cluster heads 35 and 25 to the cluster 15 is called the main backbone path. In order to increase the reliability of the network, each PCH 15, 25, 35 should be paired with its own backup cluster head (BCH: Backup Cluster Head 45, 55, 65). The source node 100 has a permanent connection with its PCH 15 and a pre-setup connection with its BCH 45. The backup backbone path to sink node 75 in FIG. 1 is made by PCH 45, PCH 55, and PCH 65. Hardware designed to detect each other's operation can operate in promiscuous receive mode for both primary and backup cluster heads in their wireless network.

Referring to FIG. 2, the PCH 15 may operate in the power down mode by stopping the active mode or the processing unit 19. Moreover, devices in idle mode can be powered off. The transmit power can be programmed according to the required range and can be powered on or off independently according to the radio transmitter 18 and the radio receiver 17 of the clusterhead 15. The clock 21 embedded in each cluster head 15 synchronizes with the clock located at the sink node 75. Clock synchronization is possible by inserting the correct source clock into the sink node 75 and exchanging synchronization messages. The table 20 consists of two tables. The forwarding table is used to manage the sensing device 100 in the cluster head 40, and the routing table is used for communication with the primary backbone path.

Clustering wireless communication nodes means increasing the role of the cluster head in configuring the wireless node and managing the network. Configuring a wireless node is to select the minimum set of wireless nodes that need to monitor environmental information and process the signal sent. Wireless node configuration is based on the characteristics of the application and the data sent in one cycle.

3 is a structural diagram of a forwarding table used to manage a sensing device of a cluster head. The Sensor ID field and the Sensor Address field are a list of 16-bit addresses allocated from the cluster head when the sensing device is attached to the cluster ( MAC address ) and the sensing device first attaches to the cluster. A data length field (Data Length field) is (bit) means the length of the sensing device has an 8-bit temperature, and humidity can have a length of 16 bits (bit). The Status field shows the connection status of the sensing device. If the sensing device is connected to the cluster head, it has a value of True. If not, it has a value of False.

4A is a structural diagram of a routing table that the cluster head 25 uses to transfer records from its sensing device to the sink node 75. The Source ID field and the Source Address field indicate the identifier and address of the sink node 75 in the DPCT network. 1, only one sink node 75 exists, but the DPCT network allows more than one sink node 75. The Next Hop ID field and the Next Hop Address field indicate the identifier and address of the next hop cluster head in the path to the sink node 75. The cluster head 25 has two next hop cluster heads 35 and 65 in its path to the sink node 75. Priority Field (Priority field) has two values, 0 and 1. It has a value of 0 if the next hop cluster head is the primary cluster head and a value of 1 if it is the backup cluster head. The cluster head 35 is the main cluster head and has a corresponding priority value of zero. The cluster head 65 has a priority value corresponding to 1 for the backup cluster head. This routing table structure is similar to the routing table structure of the main cluster heads 15 and 35.

4B is a structural diagram of a routing table that backup clusterhead 55 uses for a backup backbone path. The sink node 75 is still the destination node of the cluster head 55, and the cluster head 55 refers to two next hop clusterheads, namely the backup cluster head 65 and the primary clusterhead 35. In the routing table of the backup cluster head, the priority value is 0 if the next hop clusterhead is the backup type, and 1 otherwise. The cluster head selects the high priority as the next hop and uses the low priority as the next hop when a high priority next hop fails. The routing table is not applicable to the other backup cluster heads 45 and 65.

5A illustrates a case in which a node does not operate in a single mode . When the main node 25 does not operate due to a problem, the node 55 detects an abnormality of its own main node 25 based on the loss of the heartbeat packet. Node 55 also sends a notification message to sink node 75. Receiving this message, the sink node 75 uses the backup backbone path formed by the backup cluster heads 45, 55 and 65. The backup backbone path is used until the primary backbone path is restored.

FIG. 5B illustrates the case in which the node does not operate in the mixed mode . When the primary cluster head 25 does not operate, the backup backbone path may not replace the primary backbone path if the backup cluster 65 also does not operate. In mixed mode backup cluster head 55 is connected to primary cluster head 35 using low priority path 42 of the routing table in FIG. 4 (b). Now the main cluster head 15, the path of the backup cluster head in the cluster head 45, 55 is used for 25. This mixing path (mixed path). One can think of why the link between cluster heads 15 and 55 is unavailable, because the link between two backup clusters, 45 and 55, is the primary cluster head (15) and the backup cluster head. This is because it has higher priority than the link between 55.

5C is a diagram showing a case where the backup cluster head 45 also does not operate when the backup cluster head 65 and the main cluster head 25 do not operate. In this case the path between the primary cluster head 15 and the backup cluster head 35 is used. The source node is instructed to send the read information to its cluster head. The cluster head collects all information of all the sensing devices belonging to the cluster head, and then alternately transmits all its data to the sink node 75 in a hop-by-hop manner. The sink node then sends it to a processing center that processes and analyzes data from all cluster heads.

Referring to FIG. 6, the source node 100 may operate in an active mode and a power down mode in which power of the sensing unit 101 and the processing unit 104 is cut off according to a command received from the cluster head. In addition, the radio transmitter 103 and the radio receiver 102 of each source node 100 may be independently turned on / off. The embedded clock 106 is synchronized with the embedded clock 21 of the cluster head.

Medium Access Control (MAC) mechanisms allow wireless (source) nodes to selectively power down receivers in nodes when not needed. The cluster head modifies the scenario to turn the wireless nodes' wireless receivers and transmitters on and off. In addition, the circuitry that controls transmission and reception reduces error rates by reducing radio interference in networking and allowing wireless nodes to communicate reliably using low transmission energy.

Figure 7a shows a message exchange model that combines into a cluster of new source (wireless) nodes. The source node first sprays a detection signal 51 to find available cluster heads. Upon receiving a detection response 52 from an available cluster head, the new source node will send a join request 53 to the cluster head to join the cluster. On receiving a join request from a new source node, the cluster head checks the forwarding table to see if there is an old entry that this source node has previously joined to the cluster. If it is a new node, the cluster head adds a new entry for the new source node and sends a join response message 54 to the wireless node.

7B shows a coupling state in which a coupling response is included. If the association is accepted from the cluster head, the cluster head responds with an Association Successful signal 56. If the join is rejected due to the capacity limitation of the cluster head, a cluster head capacity response ( CH at capacity) response 57 is sent. If the join is not accepted by other conditions of the cluster head, the cluster head responds with a cluster head access denied signal 58.

One wireless node has two connections with the cluster head. One is the connection with the PCH and the other is the connection with the BCH. The connection with the BCH is called a pre-setup connection because it does not work when the BCH is in backup and PCH is in a normal state. However, from the point of view of a wireless node node, there is only one cluster head, because PCH and BCH use the same ID and address.

Referring to FIG. 8, it can be seen that the present invention constructs and manages a DPCT in a ten step process. Building a network begins with deploying the sink node (step 91). All information in the tree is stored on the sink node and the entire tree database will be added when one new cluster is installed. The next step is to determine the location of each cluster (step 92) and then place the failover clusters in each cluster. (Step 93)

Once the placement of the cluster heads is complete, a datapath is established between the cluster heads of each of the series of clusters. The data path includes a high priority path between a series of two primary cluster heads, or between a series of backup cluster heads and a low priority between one primary cluster head and one backup cluster head of two series of clusters. Deploying wireless node nodes in each cluster is the next step. (Step 95) The number of source nodes in each cluster is at least three. This means that we must adjust the concatenation of the source nodes so that there are no clusters with two source nodes with the same functionality. After the source nodes are installed in each cluster, the cluster establishes a time-slot to communicate with each source node. Setting time slots will minimize channel contention between clusters and wireless nodes and minimize network propagation disturbances. After receiving a command from the wireless node time slot of the cluster head, the wireless node obtains the peripheral information and transmits the information to the cluster head of the wireless node.

        Figure 1 illustrates a specific portion of the invention and is a distributed wireless node network architecture including cluster groups.

       2 is a block diagram of an exemplary cluster head suitable for the wireless network of FIG.

       3 is a structural diagram of a forwarding table used by a cluster head to manage its source nodes.

       4A is a structural diagram of a routing table for the primary backbone path used in the primary cluster head for the scenario of FIG. 1.

       4B is a structural diagram of a routing table for the backup backbone path used in the backup cluster head for the scenario of FIG. 1.

       FIG. 5A shows a case where a specific cluster suffers from failure of the primary backbone path and thus the backup backbone path is used.

       FIG. 5B shows a case in which both the primary backbone path and the backup backbone path cannot be used due to a problem of specific clusters.

       Fig. 5C shows the error correcting mechanism of the present invention for explaining the problem occurrence of another specific cluster in detail.

       6 is a block diagram of an exemplary source node suitable for the tree network of FIG.

       7A illustrates a process used in a cluster of wireless communication nodes.

       FIG. 7B is a summary illustrating the coupling state created by the cluster head and is summarized for response.

8 is a flowchart for developing a dual path clustering tree ( DPCT ) network according to the present invention.

Claims (6)

       As shown in FIG. 1, which is a network configuration method that simplifies configuration and maintenance of a wireless communication network and provides high stability in a wireless communication network having a tree structure.        (a) the sink node 75 corresponding to the tree root collects and stores all the information of the entire tree,        (b) The wireless communication path extending from the sink node 75 to the wireless node includes a communication path via a primary cluster head (PCH: Primary Cluster Head 15, 25, 35) and a backup cluster head (BCH: Backup Cluster Head 45). , 55, 65), and        (c) PCHs serve to relay data transmitted from the wireless nodes such as the wireless node 100 of the cluster 40 to the sink node 75,        (d) The BCH is configured to operate in place of the PCH when a failure occurs in the PCH corresponding to the BCH.        (e) PCH and BCH pairs check each other's active state using Keep-Alive messages,        (f) The use of the communication path in communication between the cluster 40 and the cluster 50           (i) The wireless main communication path 31 between the PCH 15 of the cluster 40 and the PCH 25 of the cluster 50 is used,           (ii) when the wireless communication path is blocked, the wireless auxiliary communication path 30 between the BCH 45 of the cluster 40 and the BCH 55 of the cluster 50 is used instead, (iii) If the main communication path 31 is restored while the auxiliary communication path 50 is in use, the main communication path 31 is used, so that an error occurs in the main communication path 31 in the tree-structured wireless network. The hidden terminal generated in the mesh network having multiple wireless communication paths because the communication is performed through the auxiliary communication path 30 and the wireless nodes are driven by the slave device of the PCH and the PCH is driven by the master device of the wireless nodes. Vine Tree, which greatly improves the communication failure rate due to the influence of the terminal and the exposed terminal and greatly simplifies the routing path, making it easy to manage the communication path and greatly reducing the network construction cost and management cost. Dual Path Clustering Tree (DPCT) wireless network.        The method according to claim 1, wherein the wireless node 100 located in the cluster 40 transmits data to be delivered to the sink node 75 via the PCH 15 or the BCH 45 via a communication path.           (i) Since the PCH 15 and the BCH 45 in the cluster 40 have the same network ID, from the perspective of the wireless node 100, there is only one wireless communication path to which the wireless node is connected to the PCH. ,           (ii) The communication path from the perspective of the PCH 15 and the BCH 45 is the wireless communication path 36 from the wireless node 100 to the PCH 15 and the wireless communication path from the wireless node 100 to the BCH 45. (37) exists,           (iii) the wireless node 100 operates as a slave device with respect to the PCH 15 and the BCH 45,           (iv) DPCT radios in the form of a Vine Tree that each of the wireless nodes in the cluster receive a fixed network address value from the PCH when connected to the PCH, greatly reducing the connection failure. network.        A communication path 3 (32) from the PCH (15) to the BCH (55) in addition to the main communication path (31) and the auxiliary communication path (30) and from the BCH (45) to the PCH (25). Communication path 4 (33) heading, communication path selection priority is set in order of primary communication path (31), auxiliary communication path (30), communication path 3 (32), communication path 4 (33) in order of priority If a communication path fails while using a high communication path, use a mechanism that uses the next priority communication path.           (i) By simplifying the routing protocol configuration of the tree-type wireless communication network, the wireless nodes can be more efficiently organized and managed.           (ii) Vine tree that improves communication reliability by 16 times compared to communication reliability with one backbone communication path as a mechanism that constructs a quadruple communication path with two communication paths added to the double backbone and a communication path of priority. DPCT wireless network in the form of a Vine Tree.        To configure and manage a dual path cluster tree (DPCT) wireless network in the form of a Vine Tree of FIG. 1        (a) placing the root function of the tree on the sink node (step 91),        (b) determining a connection location of each cluster by referring to the sink node (step 92);        (c) placing a failover cluster head for each cluster (step 93),           (i) the primary cluster head deployment phase,           (ii) deploying a Backup Cluster Head (BCH) in conjunction with PCH;           (iii) constructing a judgment for determining whether to operate the PCH and the BCH,        (d) constructing a wireless communication path capable of changing a communication path between PCHs (step 94),           (i) constructing a high priority communication path for communication of PCHs and BCHs between clusters,           (ii) constructing a low priority communication path for communication of PCHs and BCHs between clusters;        (e) deploying wireless nodes with error correcting capabilities in respective clusters (step 95).           (i) the wireless node requesting the PCH to assign an address.           (ii) the wireless node being assigned a network address from the response message of the PCH.        (f) In each cluster, inserting a time-slot that PCH establishes when the PCH communicates with wireless nodes to minimize channel contention that will lead to packet collisions (step 96).           (i) a time-slot at which the PCH sends a data request to each wireless node in the cluster,           (ii) a time-slot in which PCH sends a power-down request to each wireless node in the cluster,           (iii) the BCH has a network ID and address, such as PCH, to enable communication with all wireless nodes in the cluster,        (g) the wireless node generating data to be delivered to the PCH, and delivering the data generated according to the PCH request within the time slot allocated by the PCH (step 97),        (h) in operation of the DPCT network, the PCH checks the activity status of the associated BCH (step 98),           (i) Each time an error in the cluster head is detected, the DPCT network steps (step 99) a communication path excluding the cluster head in which the error is detected;           (ii) configuring a DPCT wireless network in the form of a Vine Tree with a step of resetting the data path after a cluster head failure (step 94).        In the method of claim 4, when receiving a power down request from the PCH to reduce the power consumption of the wireless nodes (Vine Tree) having the effect of shutting off the RF-chip power supply by the power-down mode command of the RF-chip, such as CC2420 How to configure DPCT wireless network of the form.        In a method of claim 4, in a dual path cluster tree (DPCT) network comprising wireless nodes such as wireless node 100.        (a) establishing / resetting the data communication path gives a set of clusters the access priority of the routing table according to the error handling mode (step 94),        (b) A Vine Tree form in which the cluster head inserts a time-slot in communication with the wireless node to minimize radio channel contention competition to facilitate communication between the cluster head and the wireless nodes (step 96). How to configure a DPCT wireless network.

Images