Abstract
Target tracking is a typical and important application of wireless sensor networks (WSNs). In consideration of the network scalability and energy efficiency for target tracking in large-scale WSNs, it has been employed as an effective solution by organizing the WSNs into clusters. However, tracking a moving target in cluster-based WSNs suffers a boundary problem when the target moves across or along the boundaries of clusters, as the static cluster membership prevents sensors in different clusters from sharing information. In this paper, we propose a novel mobility management protocol, called hybrid cluster-based target tracking (HCTT), which integrates on-demand dynamic clustering into a cluster-based WSN for target tracking. By constructing on-demand dynamic clusters at boundary regions, nodes from different static clusters that detect the target can temporarily share information, and the tracking task can be handed over smoothly from one static cluster to another. As the target moves, static clusters and on-demand dynamic clusters alternately manage the target tracking task. Simulation results show that the proposed protocol performs better in tracking the moving target when compared with other typical target tracking protocols.
1. Introduction
Target tracking is considered important in WSNs, as it is a base for many practical applications, such as battlefield surveillance, emergency rescue, disaster response, and patient monitoring [1]. Generally speaking, target tracking aims to detect the presence of a target and compute reliable estimates of its locations, while the target moves within an area of interest and forward these estimates to the base station in a timely manner.
It is known that the cluster structure can provide benefits for large-scale WSNs. For example, it facilitates spatial reuse of resources to increase the system capacity [2]; it also benefits local collaboration and routing [3, 4]. Recently, the cluster structure is gradually adopted for solving the target tracking problem [5–13]. Normally, nodes surrounding the target collaborate with each other to estimate the location of the target. In [5–10], dynamic clustering approaches are used that dynamically wake up a group of nodes to construct a cluster for local collaboration when the target moves into a region. Clusters are constructed dynamically, as the target moves. Dynamic clustering is obviously an efficient way for local sensor collaborations because clusters formed at each time instant change dynamically, as the target moves. However, the dynamic clustering process, repeating as the target moves, is energy costly, as it incurs much overhead for forming and dismissing clusters. Besides, dynamic clustering does not consider how to efficiently send data to the sink, which is another important aspect of target tracking.
In contrast, the target tracking in [11–13] uses the static cluster for the network scalability and energy efficiency (the term of “static cluster” does not mean that the cluster will not change during the network's entire lifetime. It means that the cluster structure will keep unchanged for a relatively longer period of time compared to a temporally formed dynamic cluster, until the next round of clustering process begins. In this way, as shown in the LEACH protocol [14], each sensor node has the probability of becoming a cluster head so as to balance the energy load). It uses a predictive mechanism to inform cluster heads about the approaching target, and then the corresponding cluster head wakes up a number of appropriate nodes right before the arrival of the target. The overhead can be saved as the tracking task is handed over from one static cluster to another without costly dynamic clustering processes. It also provides a scalable structure for coordinating and managing networks. Therefore, static cluster-based approaches are more suitable for target tracking in large-scale sensor networks. However, the static cluster membership prevents sensors in different clusters from collaborating and sharing information with each other, which causes a so-called boundary problem when the target moves across or along the boundaries of clusters. The boundary problem will result in the increase of tracking uncertainty or even the loss of the target. Therefore, a new protocol is required to solve the boundary problem and realize the tradeoff between energy consumption and local sensor collaboration for cluster-based sensor networks.
In this paper, we propose a novel distributed mobility management protocol, called hybrid cluster-based target tracking (HCTT), for efficient target tracking in a large-scale cluster-based WSN. HCTT integrates on-demand dynamic clustering into a scalable cluster-based WSN with the help of boundary nodes, which facilitates sensors' collaboration among clusters to solve the boundary problem. As shown in Figure 1, when the target is inside a static cluster, the cluster is responsible for target tracking; as the target moves close to the boundaries of clusters, an on-demand dynamic clustering process will be triggered to manage the tracking task so as to avoid the boundary problem. The on-demand dynamic cluster will dismiss soon after the target moves away from the boundaries. As shown in Figure 1, the sequential clusters for tracking the target are

Illustration of HCTT for target tracking in a cluster-based WSN.
The main contributions of this paper are summarized as follows.
We address the boundary problem for target tracking in a cluster-based WSN. We present a novel hybrid cluster-based target tracking protocol, which balances well between the energy consumption and local sensor collaboration. The proposed algorithm is scalable to multi-hop static clusters and solves the problem of tracking uncertainty due to prediction errors. We conduct simulations to show the efficiency of the proposed scheme compared with other typical target tracking solutions.
The rest of the paper is organized as follows. Section 2 reviews the related work about target tracking in WSNs. Section 3 describes the system model and the boundary problem for target tracking in a cluster-based WSN. In Section 4, we present the hybrid cluster-based target tracking protocol in detail. The analysis of HCTT is presented in Section 5. Section 6 demonstrates the performance evaluation for one-hop clusters and multi-hop clusters. Finally, we conclude the paper in Section 7.
2. Related Work
Target tracking in WSNs has received considerable attention from various angles, and a lot of protocols have been proposed. Zhao et al. proposed an information-driven dynamic sensor collaboration mechanism for target tracking [16]. Brooks et al. presented a distributed entity-tracking framework for sensor networks [17]. Chen et al. proposed distributed sensor scheduling algorithms for binary sensor networks [18] and acoustic sensor networks [19], respectively. Wang et al. proposed a novel localization algorithm for target tracking [20]. Vigilnet, an energy-efficient and real-time integrated system for target tracking, was designed and implemented in [21, 22]. A distributed TDMA scheduling algorithm for target tracking in ultrasonic sensor networks was proposed in [23]. In [24], the authors proposed a secure localization scheme to defend against some typical attacks that may affect target tracking accuracy. More target tracking protocols can be found in [25, 26].
To balance energy consumption and sensor collaboration, a lot of dynamic clustering protocols have been proposed for target tracking in WSNs. Yang et al. proposed an adaptive dynamic cluster-based tracking (ADCT) protocol that dynamically selects cluster heads and wakes up nodes to construct clusters with the help of a prediction algorithm, as the target moves in the network [6]. Zhang and Cao proposed a dynamic convoy tree-based collaboration (DCTC) framework to detect and track the mobile target [7]. The convoy tree can be considered as a cluster which is dynamically configured by adding and pruning some nodes, as the target moves. Ji et al. proposed a dynamic cluster-based structure for object detection and tracking [8]. Jin et al. also proposed a dynamic clustering mechanism for target tracking in WSNs that balances the missing rate and energy consumption [9]. Medeiros et al. proposed a dynamic clustering algorithm for target tracking in wireless camera Networks [10]. A decentralized dynamic clustering protocol for acoustic target tracking, which relies on a static backbone of sparsely placed high-capacity sensors, was proposed in [5]. As mentioned in Section 1, dynamic clustering is efficient for local sensor collaboration but incurs too much overhead for cluster construction and dismiss, as the target moves. In this paper, HCTT overcomes the clustering overhead by relying on a preexisting static cluster structure.
Several target tracking protocols are based on static cluster structure [11–13]. Sensor nodes are organized into clusters by using suitable clustering protocols, such as LEACH [14] and HEED [27]. With the cluster structure, Yang and Sikdar proposed a distributed predictive tracking (DPT) protocol that predicts the next location of the target and informs the cluster head about the approaching target. The corresponding cluster head then wakes up the closet three sensors nodes around the predicted location before the arrival of the target [11]. Wang et al. [12] proposed a hierarchical prediction strategy (HPS) that also relies on cluster structure for target tracking and implemented a real target tracking system in [13]. Compared with dynamic clustering protocols, cluster-based target tracking protocols take the advantages of underlying cluster structure, which is especially suitable for target tracking in large-scale networks. However, the static cluster membership prevents sensors in different clusters from collaborating and sharing information with each other, which causes the boundary problem when the target moves across or along the boundaries of clusters. In this paper, HCTT solves the boundary problem by integrating on-demand dynamic clustering into the scalable cluster structure.
3. System Model and Problem Statement
In this section, we first present the system model, and then we describe the boundary problem for target tracking in cluster-based WSNs.
3.1. System Model
We assume that a large-scale WSN consisting of n static sensor nodes is deployed in a two-dimensional area of interest for detecting a single moving target. The sink node is deployed at the center of the network. We assume that sensor nodes are randomly deployed following a Poisson distribution with a density of λ. That is, given an area A, the number of sensor nodes in the area,
We assume that each sensor node has an identical communication range
In general, the received signal of a sensor node about the target reduces with the increase of the distance between the sensor node and the target. An attenuated disk sensing model is adopted to capture the sensing quality as follows:
Note that the sensing region of a sensor node
Each node can operate in three states. It can transmit packets, receive packets, and sense the target in active state. In sensing state, it can only perform sensing operation. In sleep state, it sleeps for most of time and wakes up periodically to sense the target and listen to messages. Since communication operation dominates the energy consumption, we mainly consider the energy consumption for communication in this paper.
We assume that the WSN is organized as m clusters by using any suitable clustering algorithm in [28]. In this paper, we use the LEACH [14] to organize nodes into static clusters. The LEACH protocol is an energy efficient adaptive clustering protocol, which is distributed and energy balanced. Each cluster i has
To ease the description of the protocol, we adopt the following notations throughout the paper:
n: the number of sensor nodes m: the number of disjoint static clusters G: the wireless sensor network. V: the set of all sensor nodes. E: the set of edges referred to all connected links of nodes. H: the set of all cluster heads.
3.2. Boundary Problem
When tracking a target in a surveillance area, multiple nodes surrounding the target collaborate to make the collected information more complete, reliable, and accurate. There is no problem when the target is inside a cluster, as all activated sensors belong to the same cluster, and they can communicate effectively. However, when the target moves across or along the boundaries of multiple clusters, the boundary problem occurs. That is, the local node collaboration becomes incomplete and unreliable because sensor nodes that can monitor the target belong to different clusters, which increases the uncertainty of the localization of the target or even results in the loss of the target due to the insufficient sensing reports or the incorrect prediction of the target's location.
Figure 2 shows two cases of the boundary problem for target tracking in a cluster-based WSN. As the target is inside cluster A, cluster A is activated to track the target, whereas clusters B and C are in the sleep state for energy saving purpose. For the case in Figure 2(a), when the target moves close to the boundaries of clusters, nodes

The boundary problem in a cluster-based WSN: (a) high localization uncertainty due to insufficient active nodes, (b) loss of target due to incorrect prediction of the target location.
In this paper, we propose a hybrid cluster-based target tracking protocol (HCTT) for efficient target tracking in a cluster-based WSN. HCTT integrates on-demand dynamic clustering into a scalable cluster-based structure with the help of boundary nodes. That is, when the target moves inside a cluster, the static cluster is responsible for local node collaboration and target tracking; when the target approaches the boundaries of clusters, a dynamic clustering process will be triggered to form a dynamic cluster to solve the boundary problem. The on-demand dynamic cluster will disappear soon after the target moves away from the boundaries. As the target moves in the network, static clusters and on-demand dynamic clusters alternately handle the tracking task effectively.
4. Hybrid Cluster-Based Target Tracking Protocol (HCTT)
In this section, we first give a high-level overview of HCTT and then describe the protocol in detail. Figure 3 outlines the overview of the system and illustrates the flowchart of HCTT. After being deployed, sensor nodes are organized into static clusters according to any suitable clustering algorithm. Boundary nodes of each cluster are also formed. When a target is in the network, a static cluster sensing the target wakes up to track the target. When the target approaches the boundary, the boundary nodes can detect the target, and an on-demand dynamic cluster will be constructed in advance for smoothly tracking the target before the target reaches the boundary. As the target moves across the boundaries, static clusters and on-demand dynamic clusters alternately manage the tracking task. Different types of intercluster handoff (i.e., the S2DIC handoff from a static cluster to a dynamic cluster, the D2SIC handoff from a dynamic cluster to a static cluster, and the D2DIC handoff from a former dynamic cluster to a new dynamic cluster) take place between any two sequential clusters. Moreover, the dynamic cluster will dismiss after the target moves away from the boundary and enters another cluster. With the help of boundary nodes, HCTT integrates on-demand dynamic clustering into a scalable cluster-based WSN for target tracking, which facilitates the sensors' collaboration among clusters and solves the boundary problem.

Overview of hybrid cluster-based target tracking protocol.
In the following, we elaborate on the design and implementation of three major components of HCTT, including the boundary node formation, dynamic clustering, and inter-cluster handoff.
4.1. Boundary Node Formation
In HCTT, a dynamic cluster will be constructed when the target approaches the boundaries of multiple clusters. A challenging issue is how the system finds the scenario when the target is approaching the boundaries, especially in a fully distributed way. As sensor nodes are randomly deployed, static clusters are usually formed irregularly. It is difficult or even impossible to calculate the geometrical boundaries of irregular clusters. In this paper, we use boundary nodes to solve this issue in a fully distributed way.
Definition 1 1.
Boundary node of a static cluster: A node
In contrast, a node is defined as an internal node of its static cluster if it is not a boundary node. As each node is aware of its own location and its neighbor information, it checks its neighbor list to determine whether there exists a node belonging to another cluster within its sensing range. If yes, it is a boundary node; otherwise, it is an internal node. The boundary node set of a cluster
(1) (2) (3) (4) (5) (6)
After boundary nodes are identified, each cluster can be partitioned into three parts: safety region, boundary region, and alert region.
Safety Region. The safety region of a cluster
Boundary Region. The boundary region of a cluster
Alert Region. The alert region of a cluster
Figure 4 illustrates the three different regions for a circular cluster. The white region denotes the safety region, the light gray region denotes the alert region, and the dark gray region denotes the boundary region. We can observe that if the target moves from the safety region into the boundary region through the alert region, nodes belonging to different clusters will detect the target. More specifically, we have the following lemmas.

Demonstration of safety region, alert region, and boundary region for a circular cluster.
Lemma 2.
All boundary nodes lie in the boundary region.
Proof.
For any boundary node
Lemma 3.
If nodes detecting the target are all internal nodes of a cluster the target moves into the safety region of the cluster, and vice versa.
Proof.
If nodes detecting the target are all internal nodes of a cluster, which suggests that the target cannot be detected by any boundary node. According to (3), the target moves into the safety region. It is also true that if the target moves into the safety region of a cluster, obviously all nodes detecting the target are internal nodes of the cluster.
Lemma 4.
If nodes detecting the target belong to different clusters, the target moves into the boundary region of one cluster and vice versa.
Lemma 5.
If nodes detecting the target all belong to one cluster and there is at least one boundary node among them, the target moves into the alert region of the cluster and vice versa.
The proofs of Lemmas 4 and 5 are similar to that of Lemma 3.
Based on Lemmas 3, 4, and 5, a cluster head can decide which region the target locates when it receives data reports from sensor nodes.
4.2. Dynamic Clustering
Dynamic clustering is triggered on demand in order to solve the boundary problem in a cluster-based WSN. There are two cases in which a dynamic cluster is needed. The first case is shown in Figure 5(a) where the current active cluster is cluster A. When the target moves from point a to point c via point b, a dynamic cluster

Dynamic clustering and handoff between clusters: (a) one dynamic cluster, (b) two consecutive dynamic clusters.
Though the dynamic cluster must be constructed in advance before the target moves across the boundaries of clusters, it is costly if the dynamic cluster is constructed too early, which not only wastes nodes' energy consumption but also may become useless quickly. As stated in Lemma 5, if the target is detected by any boundary node, the target moves into the alert region, which means that the target is closely approaching the boundary region. It is reasonable to trigger the on-demand dynamic clustering process when the target moves into the alert region, that is, when there is at least one boundary node detecting the target. The dynamic clustering process consists of three phases: leader selection, dynamic cluster construction, and boundary node formation.
4.2.1. Leader Selection
The first step to construct a dynamic cluster is to elect a cluster head from sensor nodes. The dynamic clustering process should be triggered once the target moves into the boundary region. Therefore, the first boundary node detecting the target is supposed to be the cluster head and construct a dynamic cluster. However, sensor nodes may detect the target at the same time, so these nodes may compete to be the cluster head. Therefore, an algorithm must be proposed to guarantee only one boundary node to be the cluster head.
Once a boundary node detects a target, if it does not receive any election message from its neighbor nodes, it broadcasts an election message to its one-hop neighbor nodes. If a boundary node receives some election messages before detecting the target, it would not broadcast any message. The election message includes the ID, the received signal of the target, and the residual energy of the sensor node. After it broadcasts the election message, it waits for a predefined timeout period to receive the election message from other sensor nodes. A sensor node may or may not receive the election message during the timeout period; otherwise, if it does not receive any election message after the timeout period, it will elect itself as the cluster head. If it receives multiple election messages from its neighbors, the node with the highest received signal will be elected as the cluster head. In case some nodes have the same received signal, the residual energy can be used to break the tie.
4.2.2. Dynamic Cluster Construction
After a node is elected as the cluster, it broadcasts a recruit message asking its neighbor nodes to join in the cluster. Each node receiving the recruit message establishes a new table containing the information of the dynamic cluster, for example, the ID of the leader and the working state of the dynamic cluster, and then replies a confirm message to the leader. Upon receiving the confirm message from a node, the leader puts the node into its member list.
Note that once a dynamic cluster is constructed, a node may belong to a static cluster and a dynamic cluster at the same time. When the node generates some data, it needs to decide which cluster head it should report to. This is important for the inter-cluster handoff procedure, and we will describe the details in Section 4.3.
4.2.3. Boundary Node Formation
Boundary nodes are also necessary for dynamic clusters. It can inform the cluster head of the dynamic cluster in advance if the target is about to leave the dynamic cluster.
Definition 6.
Boundary node of a dynamic cluster. A node
The way of forming boundary nodes of a dynamic cluster is different from that of a static cluster. Each node
(1) Leader node (2) (3) (4) broadcasts its election message and waits for a predefined timeout period for election messages from neighbor nodes (5) (6) elects itself as the cluster head (7) (8) elects the node with the highest received signal as the cluster head (1) dynamic cluster set (2) (3) (4) (5) (6) (7) (1) boundary nodes set (2) (3) (4) (5)
4.3. Intercluster Handoff
Before introducing the details of inter-cluster handoff process, we first give the message reporting priority order used in our protocol.
Message Reporting Priority. Each cluster can work at one of three states: active, idle (waiting), and sleep. The active state has the highest priority for message reporting, while the sleep state has the lowest priority. If a node belongs to a static cluster and a dynamic cluster simultaneously, it always reports to the cluster head with higher priority. One exception case is that, if the node is a boundary node of a static cluster, it reports to the headers of both clusters. Table 1 illustrates different data reporting scenarios where a node belongs to a static cluster and a dynamic cluster at the same time. Here, S and D denote a static cluster and a dynamic cluster, respectively, and
Message reporting priority.
Generally, the tracking task should be handled by the most suitable cluster. As the target moves in the network, the task should be handed over from the current cluster to another more suitable one, which is taken charge of by the inter-cluster handoff process. The inter-cluster handoff occurs in three typical scenarios: handoff from a static cluster to a dynamic cluster (e.g., from cluster A to cluster
4.3.1. S2DIC Handoff
When the target locates within a cluster, it is tracked by the current active static cluster. As the target moves into the alert region, boundary nodes can detect the target. Upon detecting the target by a boundary node, a dynamic cluster is constructed in advance for the coming of the target. However, the handoff should not take place right away once the new dynamic cluster is constructed, since the movement of the target is uncertain. The target may move towards the boundary, but it may also turn around and move away from the boundary. As shown in Figure 6, when the target moves to point b in the alert region, a dynamic cluster

Different moving trajectories of the target.
To minimize unnecessary dynamic clustering and handoff, the S2DIC handoff starts when the target is confirmed to be in the boundary region. When the dynamic cluster is constructed, some boundary nodes of the current active static cluster join into the dynamic cluster. These nodes are in the waiting state, while they keep detecting the target. When any of these nodes detects the target, it sends the sensing report to the cluster head of the dynamic cluster. Once this cluster head receives the sensing report, the target is confirmed to be in the boundary region, and the handoff process starts.
The S2DIC handoff procedure is shown in Figure 7(a): the dynamic cluster head, say

Illustration of intercluster handoff processes: (a) S2DIC handoff process, (b) D2SIC handoff process, and (c) D2DIC handoff process.
If the dynamic cluster is not suitable for tracking the target, it will be dismissed. As shown in Figure 6, when the target moves to point c following the trajectory
4.3.2. D2SIC Handoff
When a dynamic cluster is currently handling the tracking task, nodes sensing the target send their sensing reports to the cluster head of active dynamic cluster. If none of these sensing nodes is a boundary node of any static cluster, the target has moved away from the boundary region and entered the safety region of a static cluster, then the D2SIC handoff process is triggered.
The procedure of D2SIC handoff is shown in Figure 7(b): the active cluster head
4.3.3. D2DIC Handoff
When a dynamic cluster is currently active for the tracking task, the handoff condition for the D2SIC handoff may not be met as the target moves into the boundary region. As shown in Figure 5(b), one dynamic cluster
The new dynamic cluster is, generally, a more preferable choice than the previous one for tracking the target, as the target is at the center of the new dynamic cluster, while it is at the boundary of the previous dynamic cluster. Therefore, the handoff takes place immediately after the new dynamic cluster is constructed. The D2DIC handoff procedure is shown in Figure 7(c): the new cluster head
5. Analysis of HCTT
In this section, we will present the computation complexity and communication complexity for proposed HCTT.
As mentioned before, we have assumed that n static sensor nodes are randomly deployed in the area of interest. The deployment of these nodes follows the Poisson distribution with density of λ. Therefore, the average number of neighbor nodes of one node is
Theorem 7.
The computation complexity and communication complexity of the boundary node formation process are both
Proof.
In the boundary node formation process, each node broadcasts a message to its one-hop neighbors, so the number of messages transmitted is proportional to the number of nodes. Therefore, the communication complexity of the boundary node formation process is
Theorem 8.
The computation complexity and communication complexity of the dynamic clustering process are both
Proof.
Dynamic clustering process consists of three phases: leader selection, dynamic cluster construction, and boundary node formation. As presented in Algorithm 2, all the messages transmitted are constrained in a one-hop cluster; that is, the number of messages transmitted is determined by λ and
Theorem 9.
The computation complexity and communication complexity of the inter-cluster handoff process are both
Proof.
Inter-cluster handoff includes three schemes: S2DIC handoff, D2SIC handoff, and D2DIC handoff. Figure 7 shows that inter-cluster handoff is a local process. The message overhead is much smaller than
Theorem 10.
The computation complexity and communication complexity of the hybrid cluster-based target tracking are both
Proof.
Hybrid cluster-based target tracking protocol consists of three major components: boundary node formation, dynamic clustering, and inter-cluster handoff. Since the computation complexity and message complexity of the boundary node formation process are
Although the computation complexity and communication complexity of HCTT are
6. Performance Evaluation
In this section, we evaluate the performance of our proposed scheme through simulations. Since our HCTT scheme is proposed to solve the boundary problem in a cluster-based WSN, we mainly compare the performance of HCTT with that of DPT [11]. Moreover, we further compare the performance of HCTT with other two typical tracking protocols, DCTC [7] and ADCT [6].
We use MATLAB to perform our simulations. The simulation environment is configured as follows. A total of 6000 sensor nodes are randomly deployed in the area of
We use the following metrics to evaluate the performance of our proposed scheme:
number of dynamic clusters: the number of dynamic clusters generated during the target tracking process; missing probability: the probability of missing the target as the target moves in the network; sensing coverage: the ratio of the number of nodes sensing the target to the number of nodes within the monitoring region; energy consumption: the energy consumed for transmitting control messages and sensing reports.
Note that, although different localization approaches affect the performance of target tracking significantly, they are not the major concern of this paper. Here, we use the metric of the sensing coverage to indicate the accuracy level of location estimates of the target, since the accuracy of localization is related to the information collected from nodes surrounding the target. It is expected that all nodes detecting the target send their sensing reports to generate reliable and accurate estimates of the target. However, many of them may not be able to sense the target successfully, as they are in the sleep state due to the prediction error or other factors. Therefore, larger sensing coverage usually means a better estimate of the target's location.
Figure 8 shows a snapshot of using our proposed HCTT scheme for target tracking. Sensor nodes are organized as static clusters. Each cluster has only one cluster head, which is denoted with the snowflake mark. The yellow points denote the boundary nodes which are close to the boundaries of static clusters. The light green line denotes the moving trajectory of the target. The blue cross marks denote the nodes sensing the target in static clusters. The small red circle marks denote the nodes sensing the target in dynamic clusters, which are denoted by the large circles. We can see that dynamic clusters are triggered on-demand when the target moves to the boundaries of clusters. All these three inter-cluster handoff procedures, S2DIC handoff, D2SIC handoff, and D2DIC handoff, are shown in this snapshot when the target moves along the boundaries of clusters.

Snapshot of target tracking using HCTT.
6.1. In One-Hop Static Clusters Scenario
In this scenario, sensor nodes are organized as one-hop static clusters, where each member node can send messages directly to the cluster head.
6.1.1. Number of Dynamic Clusters
Figure 9 shows the relationship between the number of dynamic clusters and the ratio of the transmission range to the sensing range

The number of dynamic clusters versus
6.1.2. Missing Probability
Figure 10 shows the effects of the prediction error on the missing probabilities of four approaches. We can see that the missing probability of DPT is much higher than any of other three ones. Even when the prediction error equals to zero, DPT still has the probability of missing the target. This shows the effects of the boundary problem in cluster-based sensor networks. Moreover, the missing probability of DPT increases, as the prediction error increases, which implies that the boundary problem will become worse when the prediction error increases. The same trend is also observed on DCTC. In comparison, the missing probabilities of ADCT and HCTT keep zero for all the time. As for ADCT, the missing probability is not affected by the prediction error if

The missing probability versus the prediction error for all algorithms.
6.1.3. Sensing Coverage
As shown in Figure 11, the sensing coverage of DPT and DCTC decreases when the prediction error increases, while the sensing coverage of HCTT and ADCT is not affected. It is due to the fact that increasing the prediction error results in a larger deviation of the dynamic cluster from the expected cluster, which means a large a number of nodes that should be waked up to sense the target are still staying in the sleep state. We can also see that the sensing coverage of DPT performs the worst among all approaches even when the prediction error is zero. This is the reason why DPT has the worst missing probability among all schemes. Furthermore, the sensing coverage of HCTT is nearly

The sensing coverage versus the prediction error for all algorithms.
6.1.4. Energy Consumption
To evaluate the energy efficiency of HCTT, we compare the energy consumption of HCTT to other three approaches. The energy consumption presented here does not include the energy consumed for the failure recovery.
As shown in Figure 12, the energy consumptions of DPT, DCTC, and ADCT behave some drops when the prediction error increases. Since increasing the prediction error results in the drop of the sensing coverage, the energy consumption drops accordingly as the number of nodes activated for sensing the target decreases. DCTC consumes more energy than other schemes, as it relies on a tree structure which incurs more overhead than a one-hop cluster structure. In contrast, DPT consumes the least energy among all schemes, as it does not need to construct and dismiss dynamic clusters. The energy consumptions of ADCT and HCTT stand between the ones of DPT and DCTC. HCTT is not the most energy efficient scheme, as there is a tradeoff between the energy consumption and missing probability/sensing coverage. Although DPT is the most energy efficient target tracking approach, it suffers the boundary problem which results in a high probability of missing the target.

The Energy consumption versus the prediction error for all algorithms.
Note that the performances between ADCT and HCTT are very close. However, HCTT is designed to solve the boundary problem in cluster-based networks, which implicitly takes the advantages of the cluster structure. For example, data can be easily routed from a node to the sink or another node with a low delay, which is also important for target tracking. Besides, we do not consider the energy consumption of the failure recovery of these schemes when the network loses the target. Obviously, the energy consumptions of the failure recovery of DPT, ADCT, and DCTC are much higher than that of HCTT, especially for that of DPT.
6.2. In Multihop Static Clusters Scenario
In this part, we will further evaluate the performance of HCTT in multihop cluster-based networks. Sensor nodes can be organized into multi-hop clusters via various approaches. For example, Lin and Chu [29] proposed a multi-hop clustering technique using hop distance to control the cluster structure instead of the number of nodes in a cluster. A randomized distributed multi-hop clustering algorithm for organizing the sensors into clusters is proposed in [30]. In this paper, we do not discuss how to effectively construct multi-hop cluster structure but just assume that sensor nodes are formed into multi-hop clusters. Sensor nodes are organized as grid clusters with a cluster head at the center. Each node decides the hop counts to its cluster head according to its relative distance. We use the same configurations in multi-hop cluster-based networks as those in one-hop cluster-based networks, except that the transmission range of each node is fixed to be
Since our proposed scheme is used to solve the boundary problem for cluster-based networks, we only compare the performance of HCTT to that of DPT in terms of hop count.
6.2.1. Number of Dynamic Clusters
Figure 13 shows the effects of the hop count of each static cluster on the number of dynamic clusters. We can see that the number of generated dynamic clusters decreases, as the hop count increases from

The number of dynamic clusters versus the hop count of static clusters in the HCTT algorithm.
6.2.2. Missing Probability
Figure 14 shows the performance of the missing probability versus the hop count of each static cluster. We can see that the missing probability of DPT drops slightly when the hop count increases from

The missing probability versus the hop count of static clusters.
6.2.3. Sensing Coverage
As shown in Figure 15, the sensing coverage of DPT increases, as the hop count increases from

The sensing coverage versus the hop count of static clusters.
6.2.4. Energy Consumption
Figure 16 shows the trend of the energy consumptions of DPT and HCTT in terms of hop count. Both the energy consumptions of DPT and HCTT largely increase, as the hop count increases from

The Energy consumption versus the hop count of static clusters.
Summary. From previous discussions, we can conclude that HCTT can solve the boundary problem not only for one-hop cluster-based networks, but also for multi-hop cluster-based networks. We can also conclude that, when the size of clusters increases, HCTT outperforms DPT in terms of missing probability, sensing coverage, and energy consumption. Furthermore, we find that HCTT is robust to both the prediction error and the hop count of static clusters for target tracking. Therefore, HCTT is an efficient mobility management approach for target tracking in cluster-based sensor networks.
7. Conclusions
Target tracking is a typical and important application of WSNs. However, tracking a moving target in cluster-based WSNs suffers the boundary problem when the target moves across or along the boundaries of clusters. In this paper, we propose a novel mobility management protocol for target tracking in cluster-based WSNs. The protocol integrates on-demand dynamic clustering into scalable cluster-based WSNs with the help of boundary nodes, which facilitates sensors' collaboration among clusters and their smooth target tracking from one static cluster to another. The proposed algorithm solves the boundary problem of cluster-based sensor networks and achieves a well tradeoff between energy consumption and local node collaboration. The simulation results demonstrate the efficiency of the proposed protocol in both one-hop and multi-hop cluster-based sensor networks.
Footnotes
Acknowledgments
This work was supported in part by NSFC Grants no. 61273079 and no. 61272463, Key Lab of Industrial Control Technology Grants no. ICT1206 and no. ICT1207, Hong Kong GRF Grants PolyU-524308 and PolyU-521312, HKPU Grant A-PL84, the Fundamental Research Funds for the Central Universities no. 13CX02100A, and Zhejiang Provincial Key Lab of Intelligent Processing Research of Visual Media no. 2012008.
