Search

KR-20260064249-A - METHOD FOR DETERMINISTIC CLUSTER ROUTING BASED ON MULTI-HOP IN WIRELESS SENSOR NETWORKS

KR20260064249AKR 20260064249 AKR20260064249 AKR 20260064249AKR-20260064249-A

Abstract

The disclosed embodiment presents a routing technique that globally searches for an optimal path in a deterministic cluster environment. Conventional routing techniques are limited to locally searching for an optimal path in a probabilistic cluster environment. In contrast, the disclosed embodiment updates the optimal path where the required energy converges to a minimum by cumulatively comparing the energy consumed when a cluster head node transmits data via other head nodes or directly to base station nodes. Thus, the disclosed embodiment possesses superior competitiveness compared to existing technologies by searching for an energy-efficient optimal path, thereby extending the lifespan of wireless sensor networks.

Inventors

  • 강상혁

Assignees

  • 서울시립대학교 산학협력단

Dates

Publication Date
20260507
Application Date
20241031

Claims (10)

  1. As a routing method in a multi-hop based deterministic cluster environment performed by base station nodes, A step of electing a head node for each cluster from K clusters generated by dividing a circular sensor field -where K is a natural number greater than or equal to 1-; A step of calculating, per cluster head, the first path energy consumed by the head node to transmit data to the base station node in a first path connecting the head node as a start node and the base station node as a destination node; A step of calculating, per cluster head, the second path energy consumed by the head node to transmit data to the base station node in a second path connecting the head node as a start node and the base station node as a terminal node; and The method includes the step of updating the first path energy or the second path energy to the optimal path energy consumed to transmit data from the head node to the base station node based on the result of comparison between the first path energy and the second path energy. A routing method in a multi-hop based deterministic cluster environment, characterized in that the first path and the second path are different paths, and at least one of them is a path that includes another head node corresponding to the head node as a passing node.
  2. In paragraph 1, A routing method in a multi-hop based deterministic cluster environment, characterized in that the optimal path energy of the head node for each cluster is set to an initial value of the energy consumed by the head node to directly transmit the data to the base station node.
  3. In paragraph 1, The above method is: As a step performed after the step of updating with the optimal path energy above, A routing method in a multi-hop based deterministic cluster environment, characterized by further including the step of updating a transit node or a terminal node of a path consuming the optimal path energy on a cluster-by-cluster basis from a predetermined next-hop head node to a next-hop node for the head node.
  4. In paragraph 1, The step of electing the head node mentioned above is, A step of dividing the above-mentioned circular sensor field into K clusters - each of the K clusters includes the same number of sensor nodes -; A step of defining a set of sensor nodes belonging to the above K clusters as a cluster; A step of assigning an index to sensor nodes belonging to each of the above clusters on a cluster-by-cluster basis; and A routing method in a multi-hop based deterministic cluster environment, characterized by including the step of electing a head node of each cluster per round based on the above index.
  5. In paragraph 1, If the above first path is a direct path that connects the head node as the starting node and the base station node as the terminal node without passing through the other head node, The step of calculating the first path energy above is, The method includes the step of calculating the transmission energy consumed by the head node to transmit data to the base station node as the first path energy. If the above second path is an indirect path connecting the other head node to the transit node, the head node to the start node, and the base station node to the terminal node, The step of calculating the second path energy above is, A routing method in a multi-hop based deterministic cluster environment, characterized by including the step of calculating the sum of the transmission energy consumed by the head node to transmit the data to the other head node, the reception energy consumed by the other head node to receive the data, and the optimal path energy consumed by the other head node to transmit the data to the base station node as the second path energy.
  6. In paragraph 1, If the above first path is a first indirect path that connects the other head node to the transit node, the head node to the start node, and the base station node to the terminal node, The step of calculating the first path energy above is, The method includes the step of calculating the first path energy by summing the transmission energy consumed by the head node to transmit data to another head node, the reception energy consumed by the other head node to receive the data, and the optimal path energy consumed by the other head node to transmit the data to the base station node. If the above second path is a second indirect path that connects the head node and another head node as the transit node, the head node as the starting node, and the base station node as the terminal node, The step of calculating the second path energy above is, A routing method in a multi-hop based deterministic cluster environment, characterized by including the step of calculating the sum of the transmission energy consumed by the head node to transmit the data to the other head node, the reception energy consumed by the other head node to receive the data, and the optimal path energy consumed by the other head node to transmit the data to the base station node as the second path energy.
  7. In paragraph 1, The step of updating the optimal path energy above is, A routing method in a multi-hop based deterministic cluster environment, characterized by including a step of terminating the comparison when the difference value changing as the optimal path energy is updated converges to less than a preset tolerance, or when the optimal path energy is no longer updated.
  8. In paragraph 1, The step of updating the optimal path energy above is, A routing method in a multi-hop based deterministic cluster environment, characterized by including the step of updating the smaller value between the first path energy and the second path energy as the optimal path energy.
  9. As a routing method in a multi-hop based deterministic cluster environment performed by base station nodes, In each of the K clusters generated by dividing the circular sensor field Step of electing a head node per cluster - the above K is a natural number greater than or equal to 1, the above is a natural number less than or equal to K-; The above A step of calculating the first energy consumed by the head node to transmit data to the k-th head node—where k is a natural number less than or equal to K—; A step of calculating a second energy, which is the optimal path energy that the k-th head node consumes minimally to transmit the data to the base station node; By combining the first energy and the second energy, the A step of calculating a third energy, which is the optimal energy that the head node consumes minimally to transmit the data to the base station node; The above A step of updating the optimal path energy of the first head node by comparing the first energy, which is the previously calculated optimal path energy of the head node, with the third energy passing through the k-th head node as the next hop node; and The above By comparing the first energy, which is the previously calculated optimal path energy of the head node, with the third energy passing through the k-th head node as the next hop node, the above The step of updating the next hop head node of the head node, and The above optimal path energy is set to an initial value of the energy consumed when the k-th head node directly transmits the data to the base station node, and The above A routing method in a multi-hop based deterministic cluster environment, characterized in that the next-hop head node of the head node has an initial value set to a base station node.
  10. In Paragraph 9, The above If the third energy passing through the k-th head node as the next hop node is smaller than the first energy, which is the previously calculated optimal path energy of the head node, The step of updating the optimal path energy of the first head node is, The method includes the step of updating the third energy to the optimal path energy of the first head node, The above The step of updating the next hop head node of the head node is, The k-th head node passing through the aforementioned third energy-consuming path is the A routing method in a multi-hop based deterministic cluster environment, characterized by including a step of updating the next hop head node of the head node.

Description

Method for Deterministic Cluster Routing Based on Multi-Hop in Wireless Sensor Networks The disclosed embodiments relate to a technique for multi-hop routing of a wireless sensor network in a deterministic cluster-based environment. Cluster routing refers to a routing method that utilizes a hierarchical structure. This method groups sensor nodes into clusters and assigns differential roles to member nodes elected by each cluster. During the real-time data transmission phase, the head node aggregates the data collected by its member nodes and transmits it to the base station nodes. Therefore, the core principle of cluster routing is that the head node communicates with the base station nodes on behalf of its member nodes. Deterministic cluster routing is a technique that presupposes cluster routing, identifies the location of sensor nodes during the path determination phase to predetermine the number of clusters and the order in which they are elected as head nodes, and searches for the optimal path. This method identifies the location of each node based on the signal strength of messages transmitted and received by different nodes prior to the real-time data transmission and reception phase, determines the number of clusters based on the identified location coordinates, and classifies each sensor node into that number of clusters. Unlike conventional probabilistic cluster routing, deterministic cluster routing has the advantage of saving energy in that it predetermines the election order of head nodes and can fix the number of clusters as a constant rather than a probabilistic variable. Furthermore, when using multi-hop paths in cluster routing, it has the advantage of discovering paths that save more energy compared to single-hop paths. Despite the above advantages, recent multi-hop path research has only focused on advanced applications in already known probabilistic cluster environments, while there is a relative lack of in-depth research on multi-hop related to the newly proposed deterministic cluster routing. Meanwhile, technology related to deterministic cluster routing is disclosed in Korean Patent Application No. 10-2023-0144038. Figure 1 is an example diagram illustrating a local multi-hop based cluster routing technology as a prior art. FIG. 2 is an exemplary diagram illustrating a routing method in a multi-hop based deterministic cluster environment according to one embodiment. FIG. 3 is a diagram illustrating an algorithm used by a routing method in a multi-hop based deterministic cluster environment according to one embodiment. FIG. 4 is a graph for comparing the performance of a routing method in a multi-hop based deterministic cluster environment according to one embodiment. FIG. 5 is a flowchart illustrating a routing method in a multi-hop based deterministic cluster environment according to one embodiment. Definition of Terms In this specification, multi-hop refers to a process of transmitting data from a head node indirectly to a base station node through another head node or directly to a base station node without passing through, and this process is optimized to minimize energy. In this specification, a deterministic cluster environment refers to an environment in which, prior to the sensor nodes starting sensing and data transmission rounds in real time, sensor nodes deployed in the sensor field are grouped according to specific criteria to form clusters, the order in which sensor nodes become head nodes in each cluster is predetermined, and the path through which the head node of each cluster reports data of member nodes directly or indirectly to the base station node is predetermined. Meanwhile, it goes without saying that terms such as first, second, etc. are used merely to distinguish various components and are not limited by the terminology. In this specification, the following symbols may be defined as shown in [Table 1]. Total number of sensor nodesNumber of clustersNumber of nodes in a clusterDiameter of the circular sensor fieldbase station nodeSensor node corresponding to index i (i = 1, 2, ?? , N)Distance between node i and node jA set of sensor nodesThe entire set including sensor nodes and base station nodes FIG. 1 is an example diagram illustrating a local multi-hop based cluster routing technology as a prior art. FIG. 1 illustrates the process of searching for routing using a local multi-hop method. The local multi-hop method searches for multiple paths to transmit data from a target head node to a base station node and finds the path that minimizes energy consumption among them. At this time, when the local multi-hop method transmits data from the target head node to the base station node, it searches for the optimal path by comparing the energy consumed in the direct path, which transmits directly to the base station node without passing through other relay head nodes, and the indirect path, which passes through other relay head nodes. However, when comparing energy con