Journal of information and
communication convergence engineering
(J. Inf. Commun. Converg. Eng.)

Wireless sensor networks (WSNs) are considered crucial technologies in the 21st century [1]. A WSN consists of sensor and sink nodes, which are small wireless sensor nodes equipped with computing and wireless communication capabilities that communicate with each other to form a network. Wireless sensor nodes typically operate on battery power, utilizing limited computing power, memory, and bandwidth to establish self-configuring networks and perform tasks such as environmental monitoring, data collection, and event detection through communication among sensor nodes. Various challenges have arisen in WSNs that affect their performance and reliability. Sensor nodes in WSNs typically operate on a limited battery lifespan, necessitating the development of technologies that consider energy efficiency [2]. Scaling up the number of nodes in a WSN for better accommodation poses challenges because optimization and autonomy can lead to overall performance degradation [3]. Research has been conducted to address issues related to inefficient network connections or overlapping ranges owing to poor sensor-node placement [4]. Numerous applications in WSNs have strong requirements for end-to-end delay and loss during data transmission, leading to ongoing research on maintaining service quality [5].

To address these issues, routing functionality is essential, and various routing protocols have been investigated [6]. Ad hoc network routing protocols cannot be directly applied to WSNs, leading to a distinction between adapted routing protocols and newly developed protocols tailored to sensor networks [7]. Sensor nodes in WSNs are typically designed to be cost-effective using low-cost devices with limited computing performance [8]. Research has been conducted to overcome the problem of low computing performance [9]. However, applying routing protocols with high routing overheads, which require substantial computing performance, is not suitable for WSNs with low computing performance in the sensor nodes. Considering the low computing performance of sensor nodes, tree routing is an appropriate routing protocol for WSNs [10]. Tree routing minimizes routing overhead, which makes transmission more energy efficient. This efficiency originates from the data following a structured tree path. In addition, it allows relatively easy adjustments when new nodes are added or removed.

In this study, we propose adaptive metric-based tree routing to address issues commonly encountered in tree routing, such as congestion stemming from selecting specific nodes as parent nodes and the difficulty of dynamically applying a uniform parent selection algorithm to network conditions. This approach utilizes tree routing while mitigating congestion by dynamically applying a uniform parent-selection algorithm to the network conditions.

Although various routing protocols exist, tree routing has been proposed as an efficient solution for network communication [11,12]. This method efficiently organizes the network and defines the delivery paths of data packets by optimizing data transmission using a tree structure [13]. Consequently, it alleviates issues such as network congestion and enables stable and rapid data delivery.

A. Traditional Tree Routing

The basic operation of the tree routing mechanism consists of the build message transmission process depicted in Fig. 1 and the parent node selection and data transmission process illustrated in Fig. 2. The detailed operation process is as follows:

Figure 1. Build message transmission process of tree routing: The process of message transmission for the formation of the tree structure in tree routing.

Figure 2. Data transmission path in tree routing: Parent nodes are selected using the parent selection algorithm, and packets are transmitted to the sink node.

i) The sink node shown in Fig. 1 broadcasts a message containing its information to the sensor nodes. Upon receiving these messages are rebroadcast by sensor nodes, exchange information with nearby nodes within one hop, and store information in tables.

ii) Sensor nodes that receive the build messages, as shown in Fig. 2, select parent nodes in the direction of the sink nodes. Using the previously exchanged table, the parent node is selected using an implemented parent selection algorithm, and this information is updated in the table. The occurrence of loops was verified during the parent selection. If a loop occurs, then the node selects an alternative parent node.

iii) The sensor nodes transmit their data and receive them from the child nodes to the selected parent node.

iv) The sink node periodically repeats the process depicted in Fig. 1 by sending newly built messages to the sensor nodes, and each sensor node updates the information and parameters from nearby sensor nodes. Each sensor node selects a new parent node using a parent-selection algorithm.

Traditional tree routing with the depicted process results in certain nodes being selected as parents by multiple nodes, causing congestion and packet loss because of the concentration of data transmission at these nodes. Traditional tree routing selects the node with the fewest hops to the sink node as the parent node, thereby exacerbating the congestion when multiple nodes select a specific node as their parent.

B. Multiple metric-based Tree Routing

Multiple-metric-based tree routing offers a potential solution to the limitations encountered in traditional tree-routing approaches. Unlike traditional methods, which rely solely on the hop count to determine parent nodes, multiple-metricbased routing considers a range of additional factors to optimize network performance and reliability [14].

One of the primary advantages of multiple-metric routing is its ability to mitigate congestion issues that commonly arises in dense sensor-network deployment. By incorporating metrics such as buffer occupancy rate and received signal strength, nodes can make more informed decisions when selecting parent nodes. This helps distribute the network load more evenly, reducing the risk of bottlenecking, and ensuring smoother data transmission throughout the network.

Moreover, multiple metric-based routing allows greater adaptability to diverse environmental conditions and network dynamics. For example, in scenarios in which energy efficiency is a priority, nodes can prioritize parent nodes with lower energy consumption rates. Conversely, in areas with fluctuating signal strengths or interference, nodes may prioritize parent nodes with stronger signal reception capabilities to maintain reliable communication links.

Another notable benefit of multiple metric-based routing is its ability to optimize network resource utilization. By considering multiple metrics simultaneously, nodes can identify parent nodes that offer reliable connectivity and have sufficient resources to handle data-forwarding tasks effectively. This optimization contributes to overall network efficiency and extends the operational lifespan of the network.

However, effectively deploying multiple metric-based routing algorithms requires careful consideration of various factors, including network topology, traffic patterns, and node capabilities. In addition, the mechanisms for the metric aggregation, data fusion, and decision-making processes must be carefully designed to ensure robust and efficient operations in dynamic network environments.

Recently, research has been conducted to evaluate the performance of multiple-metric-based routing algorithms in largescale sensor-network environments, emphasizing various topologies [15]. This study aims to address the primary limitations of tree routing, such as bottleneck issues and node concentration, by modifying the topology. Performance was evaluated by adding additional sensor nodes or incorporating more sink nodes and compared the results with those of existing studies. However, these improvements are only meaningful in environments where there is flexibility to freely add nodes, which represents a significant limitation. This study aims to resolve this issue by enhancing the algorithms rather than adding new nodes.

C. Cluster-based Tree Routing

In addition to the metric-based approach, research has been conducted to enhance performance by combining clustering and tree routing [16,17]. Cluster-based tree routing partitions a network into clusters and constructs a tree structure for each cluster to transmit data. Each cluster head node receives data from non-cluster head nodes within its cluster and forwards them to the next destination. The structure of the cluster-based tree routing is illustrated in Fig. 3.

Figure 3. Structure of Cluster-based tree routing: Each cluster transmits data to the Root node through Cluster head nodes.

By dividing the network and applying tree routing, clusterbased tree routing disperses the network load among clusters, improves network efficiency, and reduces bottlenecks. However, cluster-based tree routing exhibits certain limitations. Cluster head nodes may become overloaded because they are responsible for routing and processing data within clusters. In addition, maintaining communication between clusters and tree structures increases message exchanges, adding overhead and potentially degrading overall network performance.

In summary, cluster-based tree routing can reduce bottlenecks and improve network efficiency. However, it faces issues such as additional overhead and excessive loads on certain nodes. To address these challenges, leveraging multiple metrics and adaptive decision-making mechanisms can enhance the network performance, resilience, and scalability across various deployment scenarios.

A. Problem of Previous Tree Routing

As shown in Fig. 4, hop-count-based tree routing encounters challenges, particularly when it is closer to a sink node. In such scenarios, the number of adjacent sensor nodes available for parent selection decreases. This limitation results in specific nodes being selected as parents for multiple nodes, leading to congestion and packet loss during the data transmission. Traditional hop-count-based tree routing selects a sensor node with congestion issues when multiple sensor nodes select a specific node as their parent, resulting in performance degradation.

Figure 4. Issue with traditional hop count-based tree routing: Traditional tree routing based on hop count selects the node with the shortest hop count as the parent node. However, in this approach, a specific node may be chosen as the parent node for multiple nodes.

Multiple metric-based tree routing, using various metrics in the parent selection algorithm and applying the same algorithm to all sensor nodes, introduces another set of challenges. In a network environment in which data transmission occurs, the states of the nodes constantly change. Applying the same parent selection algorithm to all nodes limits the network’s ability to adapt to changing environments. Consequently, although better nodes may be available in a network environment, they may not be selected.

B. Metrics for Parent Selection Algorithm

To address the problem of a specific node becoming the parent node for multiple nodes and mitigate congestion and packet loss issues, several metrics were considered for the parent selection algorithm:

1) Hop (H): The hop count is essential for forming the hierarchical structure of sensor nodes towards a sink node. The proposed mechanism utilizes the hop count in the parent selection algorithm to allow each metric to be adaptively applied according to the network environment. Specifically, by utilizing the longest hop count in the network environment, denoted as H_max, and the current hop count, denoted as H_i, the metrics were adaptively applied to accommodate the network conditions.

2) Buffer occupancy (B): The buffer occupancy rate indicates the buffer size of a sensor node that assesses congestion. The buffer occupancy rate is calculated using the current buffer size (B_i) and maximum buffer size (B_max) of the sensor node.

3) Received Signal Strength Indicator (R): We use the RSSI to verify whether the sensor nodes are stable and to ensure that data are sent reliably. When the hop count and buffer occupancy are the same, the node chooses a more stable node by considering the current RSSI (R_i) and the maximum RSSI (R_max) in the network.

C. Tree Initialization and Parent Selection

To enhance both traditional hop count-based tree routing and multiple metric-based tree routing, adaptive metrics are proposed. This approach applies different weights to the hop count, buffer occupancy rate, and RSSI variation rate, based on the maximum hop count. The cost C_i in the proposed mechanism is expressed as expression Eq. (1):

The proposed mechanism aims to address issues related to a specific node being frequently chosen as the parent node, leading to increased load and frequent changes in the parent nodes and causing performance degradation.

The proposed algorithm operates as follows. If node k is identified as the sink node, it periodically broadcasts a build message (lines 1-2). The build message contains the information on H_i, B_i and R_i. Otherwise, it periodically broadcasts a hello message (line 4). Upon receiving a build message from node i, if H_i is less than or equal to H_k, the algorithm updates H_k to H_k + 1 and H_i, B_i, R_i in the neighbor information table (lines 6-9). Increment H_i by one and broadcast the build message (lines 10-11). Then, we proceed with parent selection by calling Algorithm 2 (line 12). Upon receiving a hello message from node ⁱ, the algorithm updates H_i, B_i, R_i in the neighbor information table (lines 14-15).

The proposed mechanism applies an adaptive metric based on the hop count to prevent congestion caused by selecting the same node as a parent during the parent-selection process and to enable more adaptive parent selection in the network environment. This mechanism assigns a higher weight to the buffer occupancy rate for nodes closer to the sink node to prevent congestion while providing a higher weight to the hop count for nodes farther from the sink node to facilitate faster transmission. In addition, it utilizes the RSSI to select nodes with better conditions, thereby enhancing the reliability of data transmission.

The provided algorithm operates as follows: For each node i in the neighbor information table (NT), calculate C_i using expression 1 (lines 1-2). If H_i is less than H_k and C_i is less than C_min, update C_min to C_i and P_k is set P_k to i (lines 3-5).

A. Simulation Environment Setup

Most previous studies have evaluated the performance of tree-routing algorithms through simulations, and this study also conducted performance evaluations using a Riverbed Modeler. The performance evaluation was conducted assuming an environment without additional nodes, and the parameters used for the simulation are outlined in Table 1.

Table 1 . Simulation parameters.

Parameters	Value
Number of sensor nodes	40
Number of sink nodes	1
Topology size	2,000 m × 4,000 m
Traffic type	CBR
Traffic bitrate	1,000, 3,000, 5,000 bits/s
Buffer size	100,000 bits
MAC	802.11
Transmission range	300 m

For the performance evaluation, hop-count-based traditional tree routing, multiple metric-based tree routing, and the proposed adaptive metric-based tree routing were compared.

B. Results

The performance evaluation results are presented in Figs. 5-7, respectively. In each figure, “Hop count-based” refers to hop count-based tree routing, “Multiple metric-based” refers to multiple metric tree routing considering the current hop ratio, buffer occupancy, and RSSI change rate, “Clusterbased” refers to cluster-based tree routing, and “Proposed” represents the proposed mechanism applying different weights to each metric based on the hop count.

Figure 5. Average packet delivery ratio

Figure 6. Average End-to-end Delay

Figure 7. Average throughput

Fig. 5 illustrates the packet delivery rate with varying traffic bit rates. The packet delivery rate is the ratio of the received packets to the transmitted packets. At low traffic bit rates, all mechanisms exhibited good packet delivery rates. However, as the traffic bit rate increased, the packet delivery rate decreased for all mechanisms, indicating congestion at specific sensor nodes. For the cluster-based mechanism, the packet delivery rate decreases as traffic bit rates increase owing to congestion, but the decrease is less pronounced compared to other mechanisms. The proposed mechanism exhibits better packet delivery rates than the other mechanisms, suggesting effective congestion avoidance.

Fig. 6 shows the end-to-end delay with varying traffic bit rates. The end-to-end delay represents the total time required for the data to move from a sensor node to a sink node. While hop-count-based methods outperform other mechanisms at low traffic bit rates, they exhibit poorer performance as the traffic bit rate increases. Multiple-metric-based algorithms exhibit lower performance owing to the uniform application of the algorithm to prevent congestion, even though better nodes are available at low traffic bit rates. The cluster-based method exhibited the lowest performance at low traffic bit rates because of its clustering configuration but showed better performance than the other two mechanisms as the traffic bit rates increased. The proposed mechanism showed excellent performance despite being slower than the hop count based on low traffic bit rates and with appropriate parent node selection, it outperformed other mechanisms as the traffic bit rates increased.

Fig. 7 illustrates the throughput for varying traffic bit rates. The throughput represents the amount of data processed by digital transmission per unit of time. The hopcount-based method performs well at low traffic bit rates, but poorly at higher rates owing to congestion. Multiple metric-based algorithms outperform hop-count-based algorithms but have lower performance than the proposed mechanisms that balance buffer occupancy and emphasize hop counts for fasttransmission. Cluster-based approaches exhibit better overall performance than hop-count- and multiple-metricoverall performance than hop-count and multiple-metricbased approaches. However, owing to the additional overhead required for clustering formation and maintenance, it performed slightly poorer than the proposed method. In summary, the proposed adaptive metric-based tree routing mechanism demonstrated improved performance compared with traditional hop count-based and multiple metric-based approaches in addressing congestion issues in WSNs. Additionally, it exhibits better performance in simulation environments using less overhead compared to cluster-based mechanisms, which utilize clusters to reduce network congestion and load.

The performance evaluation results confirmed the following:

(i) Hop-count-based tree routing leads to congestion when several nodes select a specific parent node.

(ii) Multiple metric-based tree routing fails to adapt to constantly changing network environments, resulting in performance degradation.

(iii) Cluster-based tree routing experiences performance degradation, even in uncongested network environments, owing to additional overhead.

(iv) The proposed mechanism appropriately addresses the issues that arise, leading to performance improvement.

In this study, we addressed the parental selection problem in a tree-routing mechanism used to build a self-configured network in a sensor-network environment. Specifically, we strive to address the problem of parental selection concentration for specific nodes and the inability to respond adequately to the network environment. To address these challenges, we proposed using the current hop ratio, buffer share, and received signal strength as parent selection metrics. We apply metricspecific weights based on the maximum hop from the sensor node to the sink node. The proposed mechanism was validated using a simulation for performance evaluation. The results indicate that the proposed tree routing outperforms hop count, multiple metrics, and cluster-based tree routing. In particular, we observed considerable differences at high traffic bit rates. This method helps address congestion issues caused by hop-count-dependent tree routing. It also alleviates the problem of ignoring the network environment in multiple-metric-based tree routing.

This research was supported by the Chungnam National University.