Clustering and routing method and system for wireless sensor networks

Patent metadata

Field	Value
Publication number	US-12108320-B2
Application number	US-202117559708-A
Country	US
Kind code	B2
Filing date	Dec 22, 2021
Priority date	Apr 30, 2021
Publication date	Oct 1, 2024
Grant date	Oct 1, 2024

Abstract

Disclosed are a clustering and routing method and system for a wireless sensor network. The method includes: constructing an initial MECPT; constructing cluster trees and updating MECPT; calculating clustering competition coefficients of existing cluster heads relative to nodes other than a base station; determining whether the clustering competition coefficients are all −∞; if yes, enabling non-clustered nodes to communicate with the base station following paths in the initial MECPT, and selecting child nodes of the base station in the initial MECPT as relay nodes; calculating weights about energy consumption of communication between the cluster heads and the relay nodes to get communication paths between nodes and the base station; or if no, clustering nodes based on the clustering competition coefficients, and updating the MECPT and cluster trees to which the nodes are added by an iteration process.

First claim

What is claimed is:

1. A clustering and routing method for a wireless sensor network, comprising:
acquiring, by a base station, node information in a wireless sensor network, and constructing an initial minimum-energy-consumption path tree (MECPT) based on the node information, wherein the node information comprises node positions, node energy, and node IDs;
calculating first cluster head competition coefficients of nodes other than the base station in the current initial MECPT, performing a first batch of cluster head selection and node clustering, constructing a first batch of cluster trees and updating the current initial MECPT by a first iteration process, and getting a first-updated MECPT;
calculating second cluster head competition coefficients of nodes other than the base station in the first-updated MECPT, performing a second batch of cluster head selection and node clustering, constructing second batch of cluster trees and updating the first-updated MECPT by a second iteration process, and getting a second-updated MECPT;
calculating, based on the first batch of cluster trees and the second batch of cluster trees, clustering competition coefficients of an existing cluster heads relative to nodes other than the base station in the second-updated MECPT;
determining whether the clustering competition coefficients are all −∞, to obtain a first determination result;
if the first determination result indicates that the clustering competition coefficients are not all −∞, clustering the nodes in the current second-updated MECPT based on the clustering competition coefficients, and each time a node in the current second-updated MECPT is clustered, updating the current second-updated MECPT and the cluster tree to which the node in the second-updated MECPT is added, then back to the step “calculating, based on the first batch of cluster trees and the second batch of cluster trees”;
if the first determination result indicates that the clustering competition coefficients are all −∞, enabling non-clustered nodes to communicate with the base station following paths in the initial MECPT, and selecting child nodes of the base station in the initial MECPT as relay nodes;
calculating weights about energy consumption of communication between the cluster heads and the relay nodes;
calculating minimum weight paths from the cluster heads to the base station based on the weights about energy consumption of communication, using the minimum weight paths as communication paths between the cluster heads and the base station, and getting communication paths between the nodes and the base station based on the communication paths between the cluster heads and the base station; and
determining that all nodes upload the node information to the base station following the communication paths between the node and the base station.

2. The clustering and routing method for a wireless sensor network according to claim 1 , wherein the acquiring, by a base station, node information in a wireless sensor network, and constructing an initial MECPT based on the node information comprises:
calculating weights of connecting edges established by any two nodes based on the node information to generate a first weight matrix of the connecting edges;
calculating minimum weight communication paths from alive nodes to the base station based on the first weight matrix of the connecting edges; and
using next-hop nodes of the alive nodes as parent nodes of the alive nodes based on the minimum weight communication paths from the alive nodes to the base station to construct the initial MECPT with the base station as a root node.

3. The clustering and routing method for a wireless sensor network according to claim 1 , wherein the calculating first cluster head competition coefficients of nodes other than the base station in the initial MECPT, performing a first batch of cluster head selection and node clustering, constructing a first batch of cluster trees and updating the initial MECPT by a first iteration process, and getting a first-updated MECPT, every iteration comprises:
selecting, as a cluster head, a node corresponding to a maximum first cluster head competition coefficient within a cluster head competition coefficient threshold range;
using, as a cluster tree, a subtree with the cluster head as a root node, and retaining communication paths in the cluster tree; and
deleting nodes in the cluster tree and edges associated with the nodes from the current initial MECPT, and determining the first-updated MECPT.

4. The clustering and routing method for a wireless sensor network according to claim 3 , wherein after the deleting nodes in the first batch of cluster trees and edges associated with the nodes from the current initial MECPT, and determining the first-updated MECPT, the method further comprises:
if the maximum first cluster head competition coefficient is less than a lower limit of the cluster head competition coefficient threshold range, a number of selected cluster heads does not reach a cluster head number threshold, and non-clustered nodes still exists in the wireless sensor network, performing “calculating second cluster head competition coefficients of nodes other than the base station in the first-updated MECPT, performing a second batch of cluster head selection and node clustering, constructing a second batch of cluster trees and updating the current first-updated MECPT by a second iteration process, and getting a second-updated MECPT”;
if the number of selected cluster heads exceeds the cluster head number threshold and a non-clustered node still exists in the wireless sensor network, performing “calculating, based on the first batch of cluster trees and the second batch of cluster trees, clustering competition coefficients of an existing cluster heads relative to nodes other than the base station in the second-updated MECPT”; or
if only the base station remains in the first-updated MECPT, performing “selecting child nodes of the base station in the initial MECPT as relay nodes”.

5. The clustering and routing method for a wireless sensor network according to claim 1 , wherein the calculating second cluster head competition coefficients of nodes other than the base station in the first-updated MECPT, performing a second batch of cluster heads selection and nodes clustering, constructing a second batch of cluster trees and updating the current first-updated MECPT by a second iteration process, and getting a second-updated MECPT comprises, every iteration comprises:
determining whether the second cluster head competition coefficients are all 0, to obtain a second determination result;
if the second determination result indicates that not all of the second cluster head competition coefficients are 0, selecting, as the cluster head, a node corresponding to a maximum second cluster head competition coefficient in the second cluster head competition coefficients;
using, as the cluster tree, a subtree with the cluster head as a root node, and retaining communication paths in the cluster tree; and
deleting nodes in the cluster tree and edges associated with the nodes from the current first-updated MECPT, and determining the second-updated MECPT, and updating the second cluster competition coefficients then back to the step “determining whether the second cluster head competition coefficients are all 0; or
if the second determination result indicates that the second cluster head competition coefficients are all 0, performing “calculating, based on the first batch of cluster trees and the second batch of cluster trees, clustering competition coefficients of an existing cluster heads relative to nodes other than the base station in the current second-updated MECPT”.

6. The clustering and routing method for a wireless sens

Assignees

• Univ North China Electric Power

Inventors

• Fan Bing
• Xin Yanan
• Wu Runze

Classifications

• H04W84/18

  Self-organising networks, e.g. ad-hoc networks or sensor networks · CPC title

• H04W40/248

  Connectivity information update · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/46 Primary

  Cluster building · CPC title

• H04W4/38

  for collecting sensor information · CPC title