# Network Scalability for Ultra-Wideband Real-Time Location Systems Based on vMISO

Authors: Qian Gao; Chong Shen; Kun Zhang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

For time-based location systems, a common time base is important for obtaining the correct position. However, wireless clock synchronization is considerably easier to deploy in certain environments, such as large areas. A single-region positioning network is often restricted to the anchor communication range. Therefore, multiple master anchors form the basis of an extensible location network and provide an effective means of adapting the system to a complex propagation environment. In this article, we consider simultaneous network scalability with the relative clock synchronization and localization. We first establish an extendable UWB location system model through intelligent response across the routing layer and physical layer. Anchors act as master or slave anchors in different cluster areas and advance the clock check packet (CCP) from an initial region to the surrounding area to achieve clock synchronization of the entire network. The intracluster CCP transmission is achieved by broadcasting, and the intercluster CCP transmissions use vMISO and are automatically driven by the broadcast arrival time for better results. Furthermore, the physical-access and clock synchronization algorithms are discussed. Finally, location tests combined with routing simulations are conducted to demonstrate the performance of the proposed scheme.


---

## Body

## 1. Introduction

Accurate localization of targets inside exhibition halls, underground parking garages, and other indoor places is commonly performed today. IEEE 802.15.4-2011-based ultra-wideband (UWB) is considered as one of the promising standards for high-accuracy indoor positioning technology [1–3]. There have been lots of considerable researches on UWB indoor positioning. Our team utilizes the time difference of arrival (TDOA) with the lower-power solution for target localization [4]; the location system is shown in Figure 1.Figure 1
UWB location system diagram.In Figure1, the localization area has a single master anchor (MA) and three slave anchors (SAs). In this study, we provide a general description of TDOA [5]. The time of arrival (TOA) is calculated based on the tag’s Blink time stamp. Due to the clock variance of each anchor, the time bases for TOA measurement are different. To obtain a meaningful TOA value, the MA periodically sends clock check packets (CCPs) as references to its SAs. For example, in Figure 1, anchor 1 can act as the MA; the other anchors act as the SAs by tracking the varying local clocks according to the references to enable the SAs to correct the local Blink TOA. Thus, the clock synchronization of the anchors is a key problem for location performance.The UWB power constraint and extremely short pulse duration affect the transmission performance and limit the propagation distance [2]. To increase the coverage area, it is important to maintain the relative clock synchronization of the main base station in each region. Therefore, routing protocol design is critical to the accuracy and reliability of large-area indoor TDOA-based localization. The emphasis of routing protocols always varies according to the application scenario. The design objectives can be summarized as high efficiency, high stability, and high-rate polymerization of network communications [3]. The number of adjacent nodes and the positions of nodes are the main factors that are considered in conventional routing protocols for improving network performance.In most wireless sensor networks (WSNs), both nodes and the base station employ single antennas. However, multiple input single output (MISO) routing algorithms, which deploy multiple antennas, have been demonstrated to improve the reliability and throughput of communications significantly without increasing the bandwidth [6]. Cooperative diversity has also been employed to realize space-time communication [7]. The introduction of virtual MISO [8], which combines an upper-layer routing algorithm with a lower-layer communication model, offers very significant energy-saving potential [9]. A number of studies have been conducted regarding cooperative transmission with routing protocols. An optimization model has been developed to determine the number of cooperative nodes and the optimal number of hops for a given delay requirement [10]. A game theoretic framework has been presented to analyze a heterogeneous cellular wireless local area network (WLAN) from a vMISO perspective to meet quality of service (QoS) requirements [11]. A new multihop vMISO communication protocol was proposed using cross-layer design to jointly improve energy efficiency, reliability, and end-to-end (ETE) QoS provisioning in WSNs [9]. Simulation results demonstrated the effectiveness of the proposed protocol for facilitating energy savings and QoS provisioning. Conventional vMISO transmission schemes principally focus on maximizing the throughput of grouped mobile terminals without taking QoS into account. A scheme that combines a time-reversed space-time block code scheme at the physical layer (PHY) and a cooperative routing protocol at the network layer has been proposed [12]. The core feature of this architecture is that the multiple routes are capable of cooperation for assisting the transmission of each route; hence, the reliability of wireless links is enhanced simultaneously by cooperative diversity. In addition, the means by which the benefits of the PHY layer of vMISO routing translate into network-level performance improvements have been investigated [13]. These past studies provide a foundation for the present work to consider an appropriate cross-layer vMISO routing scheme to facilitate the scalability of UWB-RTLSs.In this paper, we mainly propose a vMISO OR method to achieve an extensible location network based on a hop-by-hop process through cooperative diversity, which considers the network capacity and the security of the node itself. The overall design structure employs routing layers, PHY access, and a whole-network clock synchronization algorithm that is tailored to achieve cooperative diversity. The theory and primary innovations of the scheme are highlighted as follows:(i)
Improved data delivery reliability: every candidate is a potential packet forwarder. As such, vMISO links guarantee the successful transmission of data packets to the destination, even under a single-path failure condition(ii)
Reduced transmission delay: retransmission due to packet errors is the main cause of network delay and increases the contention window size, thereby resulting in an increased number of idle slots. Cooperative transmission can greatly improve the success of packet transmission by avoiding retransmission(iii)
Prolonged network lifetime: the basis of an energy-balanced routing protocol is that only anchors with relatively high residual energy forward the packets and low-energy anchors only receive packets to prolong their lifetime(iv)
Better location accuracy for large-area networks: for the TDOA location algorithm, the anchors need to be globally synchronized. Due to the diversity gain, the CCP transmission interclusters become more valid. Moreover, SA calculates the clock variance from its MA such that the tag’s time stamp is also converted into the MA’s time baseThe present study employs a similar cooperative diversity approach to that discussed in [10]. This approach is different from the approach proposed in [14], where cooperative transmission is only enabled when the first transmission attempt fails, which is highly likely in a fading environment.The remainder of this paper is organized as follows. Related work is presented in Section2. The proposed system model is discussed in Section 3, which includes a network model and a wireless communication energy consumption model. Section 4 presents the main concepts and details of the proposed energy-balanced vMISO-OR scheme, where the system is clustered into groups of different sizes according to the energy and topology. Based on this, the vMISO-OR scheme intelligently seeks the energy-balanced routing scheme. Based on this, the whole network clock synchronization algorithm is put forward. Then, the results of experiments are presented and discussed. Finally, Section 6 presents the paper’s conclusions.


## 2. Related Work

WSN clock synchronization is based on sending a group of signals with the time stamp to the sensors. The signal transmission consists of three classes: two-way message exchange between pairwise nodes, such as the timing-sync protocol for sensor networks (TPSN), tiny-sync, mini-sync, or light-weight time synchronization (LTS); one-way message dissemination, such as the flooding time synchronization protocol (FTSP); and receiver-receiver synchronization, such as reference broadcast synchronization (RBS). The details of these protocols are discussed in [15]. We use one-way message dissemination scheme in which a single master periodically broadcasts a packet that indicates its local time. This packet is received by each of the slave anchors, and the time of arrival in each of the slave clock domains is recorded.Several routing algorithms for data dissemination have been studied for WSNs [8]. Most of them use only a single node as the next hop, regardless of whether the other nodes have received the message. In a clustering routing scheme, sensor nodes with different levels are divided into clusters. Some clustering routing schemes have been widely employed, such as the lowest-ID algorithm [14], the highest-connectivity-degree algorithm [16], the distributed clustering algorithm [17], and the weighted clustering algorithm [17]. Researchers in [14] demonstrated that clustering topology can localize the arrangement of routes within a cluster to reduce the size of the routing table. Researchers in [16] showed that certain assignment levels are easier to manage than others and are more scalable in response to events. These algorithms, which operate with different degrees of emphasis on cluster head selection, are applied in different environments and provide different cluster structures. However, because these algorithms do not employ topological perception, the clustering of a mobile ad hoc network is not adaptive to the network state, and the cluster head can become the bottleneck of the network. Moreover, a lack of consideration for balancing the reduced traffic on the link can easily produce often-repeated data pathways (i.e., hot paths), which reduce network lifetime. For large-scale networks, cluster heads that are employed in a single-hop data transfer protocol will incur a greater energy cost. As shown in [18], an uneven cluster-based routing protocol can greatly reduce the occurrence of hot paths. This protocol assumes a network topology that consists of two concentric ring layers around the base station, where the inner-ring cluster heads, which are close to the base station, forward data to the outer-ring cluster heads. By reducing the cluster member energy, the consumption of cluster energy is reduced in the process of data transfer between cluster heads. However, this protocol is only appropriate for a heterogeneous network, where the distribution of cluster heads is designed in advance; therefore, it is not suitable for a randomly deployed network. In [17, 19], multihop uneven cluster-based algorithms that are based on competition all achieve satisfactory simulation results, but cluster head selection has three main disadvantages: (1) the competition process activates noncompetitive low-energy nodes that cannot win the competition, which wastes energy; (2) random activation cannot ensure that the winning node is the best possible choice; and (3) each competitor node can send, receive, and process broadcast information, which increases the network overhead.


## 3. System Model

To increase the coverage area of an IR-UWB location network, we consider the relative clock synchronization of the MA in each region, which provides distributed clock synchronization of anchors in the extended range. Cluster-based routing reduces the network routing maintenance cost. Slave anchors require no intercluster communication, because only the cluster head has the duty of routing. Moreover, the number of clusters is much smaller than the number of nodes, so the size of the routing table is greatly reduced. Clustering also makes the network more stable. Under a cluster-based network framework, the network has dynamic adaptability, and local topology changes, such as node movement and failure, have less effect on the overall routing topology. In addition, clustering can also reduce data transmission conflicts in a wireless medium and results in better extensibility. The system model is shown in Figure2. The cluster nodes satisfy the following assumptions: (1) cluster nodes aggregate data from other nodes; (2) they disseminate data to other nodes; and (3) they perform a multihop routing function.Figure 2
Clock synchronization for location area.In Figure2, the red dots are the master anchors (MA), the blue dots are the selected relay anchors (RA), and the green dots are the slave anchors (SA). MA1 sends a clock synchronization packet to each anchor. Its SAs receive the clock synchronization packet and adjust to maintain clock synchronization with the local network. The anchors in blue are the selected relays that cooperate to forward the clock packets to main anchors MA2 and MA3, which, along with other MAs, are all winners in the cluster head selection competition. After obtaining the clock packets, both MA2 and MA3 assume the role of MA3 and send clock synchronization packets to their SAs. This process leads to delay but does not influence the real-time localization accuracy of the tags in the corresponding areas. In this way, the entire system maintains relative clock synchronization.The cooperative transmission scheme of the relays is mainly designed for achieving full cooperative diversity. As Figure2 shows, each hop includes two cooperative anchors for facilitating transmission, which can improve the performance even in cases where only a single node becomes available. Cooperative diversity must be implemented by joint efforts between the PHY and routing layers [10].


## 4. Virtual-MIMO-Based Cross-Layer Routing

The vMISO-OR scheme that is proposed in this paper is primarily based on the intelligent sensing of both the broadcast time and response time. In part A, we describe the CCP network routing. We also simulate and compare the network routing performance of the vMISO scheme with those of the ExOR [20] and SISO relay schemes by NS-2. In part B, the clock synchronization algorithms further explain how the CCP time stamps can be used for clock synchronization of anchors. We also present a comparison of the relative clock offsets of one reference anchor and two reference anchors. In the last part of this section, experiments are conducted to evaluate the performance of the vMISO scheme for the clock synchronization of a large-area network.


### 4.1. Network Routing

Clock synchronization packets are distributed to the anchors for large-area location. As shown in Figure2, the area can be divided into unevenly sized clusters, and the node residual energy, average node degree, and power efficiency are taken into account to prolong the network lifetime. The routing algorithm includes two stages: uneven clustering and data transmission. The data transmission stage includes intracluster and intercluster transmission.All of the anchors broadcast the "Hello" packages including the anchor ID in a hop range, and the broadcast radii are the competition radius of themselves [19]. The cluster head anchors are those with the shortest broadcast time, which can reduce the data interaction in the cluster head selection process compared to the conventional clustering algorithms [21].The broadcast time of thejth anchor node is given by a heuristic expression:(1)tj=T0·1ζcj-m+η·lg⁡Tj+0.01/Tthr+0.01·E0j-ErjEaj+nj,where T0 is the last-round cluster head selection time; cj denotes the connectivity of anchor j, which is defined as the number of anchor nodes that are adjacent to it; m is the number of cluster members in the last round; ζ and η are positive-valued weight coefficients that satisfy ζ+η=1; Tj is the time anchor j as a cluster head; Tthr is a time threshold value, which limits the value of Tj; E0_j is the primary energy of anchor node j and Er_j is its residual energy; Ea_j is the average residual energy of the cluster with which anchor node j was associated in the previous round, where tj decreases with increasing Ea_j; and random number nj∈(0,1) is used to avoid obtaining the same value of Er_j for different anchors to avoid conflict. We note that anchor nodes with higher values of cj may have a larger probability of being a cluster head. This divides the network into smaller clusters to reduce packet transmission delay. With regard to Tj, we note that MAs consume more energy than SAs. Therefore, Tthr is employed to prevent the MAs from running out of energy prematurely. Once Tj exceeds Tthr, the possibility of a node again being an MA drops rapidly according to a log function. The small value 0.01 is added to avoid a log function argument of 0.According to the broadcast package time of flighttji from MA j, SA i can establish a heuristic expression of opportunistic probability (OP) OPji as follows:(2)OPji=Er_i·1tji·β,where Er_i represents the residual energy of SA i and β is a constant. The value of tji is affected by the relative distance and delay between nodes j and i. The value of OPji increases with increasing Er_i and decreasing tji.During cluster head selection, when anchors receive the “Hello” package, they record the information of the sender and refrain from broadcasting the “Hello” package further. The candidate then ignores all “Hello” packages that are received subsequently. After timet1, all of the cluster head candidates have been selected, which become the MAs. After cluster head selection, if an ordinary anchor receives only a single “Hello” package from MA j, it joins the jth cluster. If it receives a “Hello” package from more than a single cluster head, it selects the cluster head whose broadcast message was first heard as the maximum-received-signal-strength cluster head. Once an ordinary anchor has selected its cluster head, it forwards a JOIN_CLUSTER message to gain admission to this cluster. We note that the network lifetime depends upon the anchor nodes’ times to live.Each MA distributes clock synchronization packets to its SAs. The intercluster data transmission quality is determined by routing. In Figure3, the red circles represent the MAs, the green circles represent the SAs, and the blue circles represent the relay anchors, such as C and G, which cooperate in the vMISO-OR scheme to forward packets from the MA that is denoted as A to that denoted as D.Figure 3
Packet forwarding with vMISO-OR.At the beginning of intercluster data transmission, the MA does not need to decide the next hop, as in conventional routing; it must only broadcast its clock synchronization packets withOPjd added to the packet head. As shown in Figure 3, anchor A broadcasts with OPad=0.5. After an SA receives a packet, the received OPjd is compared with the SA’s own OP, and if its own OP is greater, the packet is stored and forwarded to a neighboring cluster head. Thus, we have the set of SAs SA={B,C,E,F} and the set of relays RAD=B,C,G. The values of OPbd(3), OPcd(1), and OPgd(2) are all greater than OPad(0.5); therefore, candidates B, C, and G will forward packets. In contrast, OPed(0) and OPfd(0) are both less than OPad(0.5), so they retain their own clock synchronizations.As shown in Figure3, we assume that intercluster routing employs two cooperative anchors at most [22, 23]. The reasons for this assumption are as follows. (i) Including more nodes in a cooperative set will certainly not save energy because; due to the increased number of cooperative nodes, more circuit energy and synchronization overhead are required. In addition, increased training overhead will also increase the energy consumption. It has been shown that two cooperative nodes are much more energy-efficient than the SISO, 3∗3 MIMO, and 4∗4 MIMO models [23]. (ii) Based on this assumption, expansion to vMISO-based routing with two cooperative nodes is superior [24]. In practice, the routing will employ more than two candidate relay nodes that can receive and forward packets, such as B, C, and G. The forwarding anchors determine their response times according to the difference between their own OP values and those of the sending anchor, which limits the required data exchange. Suppose that the OP of relay anchor R is OPrd and that of the sending anchor is OPjd. Then, the response time tre is(3)tre=fΔOP=ψOPrd-OPjd,where ψ is a time constant that is determined by the transmission distance and the density of anchors. For a given xi′,yi′ and ψ, tre decreases with increasing OPrd. The intercluster data transmission algorithm is presented as Algorithm 1.Algorithm 1:Inter-cluster data transmission.
( 1 ) MA broadcasts data with its OPm; ( 2 ) Data received by its SAs; ( 3 ) While (no copy of data relayed) (4)  {If (OPs>OPm) (5)   {Add the data to its cache; (6)  tresponse=f(ΔOP)=f(OPs-OPm); ( 7 )   If (tcurrenttime<tcurrenttime+tresponse) ( 8 )     If (the number of data copies received ≤ 1) ( 9 )     Forward the data; ( 10 )   Else ( 11 ) Delete the data; (12) } ( 13 ) Else ( 14 ) Drop the data; ( 15 ) Return; (16) }If, within its response time, R receives forwarded packets from a higher-priority anchor, it deletes its stored packet copy. Without accepting any other packets from higher-priority forwarders, R acts as a relay to forward packets. As Algorithm1 shows, under the condition OPcd>OPbd, the response time of B is greater than that of C, which means that C is forwarding the packets and B deletes its stored packet copy; otherwise, B forwards its stored packet copy.


### 4.2. Wireless Clock Synchronization

Traditionally, we model the clock time as a continuous function of the clock skew (frequency difference)γ and the clock offset (phase difference) θ [20]: (4)Cmt=t,Cst=γ·t+θwhere Cm(t) denotes a reference clock of the sending anchor and Cs(t) denotes the local clock of the receiving anchor. In digital clocks, time is recorded by counting the number of periods of a repeating clock signal. At each rising clock edge of the periodic signal, an integer time counter is incremented.The primary problem of network synchronization is to resolve the observed time in (4). The algorithms that are considered here use a one-way message dissemination approach at the level of discrete clock ticks.Suppose that the anchors all transmit and receive the CCP clock check packets with the time stamps, and the initial master anchor transmits a CCP with periodT. In the kth round of message broadcasting, MA1 broadcasts a synchronization message CCP at T1,k and SA1 records its time T2,k at the reception of that message. Let Δk denote the interval between receiving a signal and the following initial local clock tick, which is caused by the clock offset. According to [25], the timing model of the kth broadcast message is given by (5)T2,k≈γ·T1,k+θ+Xkwhere Xk is the random variable delay in the transmission.To achieve global clock synchronization, it is necessary to estimate the clock synchronization parameters of the whole network directly from the time stamps at the same time. We generalize (5) to transmission from a MA j to a slave anchor i:(6)T2mj,i=γi·T1mj+θi+Xmj,iwhere T1mj is the transmission time at master anchor MA j and Xmj,i is a zero-mean independent Gaussian random variable with variance Vji.We can treat the skew and offsets on different time scales as in [15]. That is, we can adjust the parameters γi approximately every Ts time units and adjust the parameters θi approximately every τs time units, with Ts≫τs; the absolute values of these quantities will depend on the nature of the clocks and the settings. When computing the offset, we treat the skew as constant (and known), so we can apply the theory that we presented earlier. On longer time scales, we adjust the skew using the same iterative procedure (with different variables).Assuming that only clock offsets need to be estimated, the joint probability density function ofT2mj,i is expressed as(7)fT2mj,i∣T1mj,θi=∏j,i12πVjie-T2mj,i-T1mj-θi2/2VjiDifferentiating the logarithm of (7) with respect to T1mj and θi, we can obtain two sets of equations. Their solutions are obtained by maximizing the joint probability density.(8)T1mj=∑iT2mj,i-θi/Vji∑i1/Vjifor eachj,θi=∑jT2mj,i-T1mj/Vji∑j1/Vjifor eachi.The estimated clock skewγi is obtained in the same way. Based on the estimated value, the Kalman filter algorithm [26], which has good tracking performance and low error, can be used to trace the clock skew and clock offset.The performance will significantly degrade if the line-of-sight path or first path arrival time is changed or disturbed. The multiple relays can cooperate to send the CCP to the next-hop MA. We will use an auxiliary setup with only time intervals, as shown in Figure5.In Figure5, R1 and R2 are the relays. When receiving a signal from the preceding transmitter R1, the subsequent transceiver R2 transmits after a fixed delay Δ0 to avoid interfering signals from R1 and MA2 during an epoch. As indicated by the delay lines, Δ0 can be generated independently of the local clock, and T≫Δ0>max⁡transmissionrange/c. The clock of MA2 is corrected twice in a period of T according to the improved results.The clock tracking is implemented using the Kalman filter implementation, with the main “process” function taking two inputs [5]: (1) the slave anchor CCP receiving time in its time base and (2) the master anchor CCP transmitting time in its time base and the CCP TOF.According to Figure6, the Kalman filter uses the CCP receiving time, the CCP transmitting time, and the best estimated time between the master unit and the slave unit. The CCP TOF is essentially a constant fixed offset (for any fixed-position master-slave pair of anchors) that results from the time of fight (TOF) of the CCP between the master unit and the slave unit. This constant can be calculated based on the anchors’ (X, Y, and Z) coordinates. Finally, the Kalman filter obtains the real relative clock offset and the best estimated relative clock offset between master-slave units. We select the data of a passive receiving anchor to plot in MATLAB, as shown in Figure 7.In Figure7, the green curves denote the real relative clock offset and the red curves represent the best estimated relative clock offset. We set T as 600 ms and Δ0 as 20 ms. With clock synchronization by Kalman filtering, the red curves seem to be more smooth and steady, while the green curves are volatile and are affected by the noise and temperature drift. According to Figure 7, the error is approximately 30 ns; at the speed of light, ns-level error influence is very large. Thus, the Kalman filter also smooths the error. Comparing Figure 7(a) (which corresponds to Figure 4) and Figure 7(b) (which corresponds to Figure 5), it is obvious that the estimated clock offset is steadier due to the cooperative transmission diversity. The simulations show that the clock synchronization with Kalman filtering better tracks the reference clock offset. Therefore, it obtains a better prediction for the basically identical clock between the reference-passive anchors (e.g., master-slave anchors), which is advantageous for improving the tag location accuracy.Figure 4
Space-time diagram of a reference MA and a SA.Figure 5
Space-time diagram of two relays.Figure 6
Relative clock variation with Kalman filtering.Figure 7
Relative clock offset with Kalman filtering.
(a)
With one reference anchor (b)
With two reference anchors


## 4.1. Network Routing

Clock synchronization packets are distributed to the anchors for large-area location. As shown in Figure2, the area can be divided into unevenly sized clusters, and the node residual energy, average node degree, and power efficiency are taken into account to prolong the network lifetime. The routing algorithm includes two stages: uneven clustering and data transmission. The data transmission stage includes intracluster and intercluster transmission.All of the anchors broadcast the "Hello" packages including the anchor ID in a hop range, and the broadcast radii are the competition radius of themselves [19]. The cluster head anchors are those with the shortest broadcast time, which can reduce the data interaction in the cluster head selection process compared to the conventional clustering algorithms [21].The broadcast time of thejth anchor node is given by a heuristic expression:(1)tj=T0·1ζcj-m+η·lg⁡Tj+0.01/Tthr+0.01·E0j-ErjEaj+nj,where T0 is the last-round cluster head selection time; cj denotes the connectivity of anchor j, which is defined as the number of anchor nodes that are adjacent to it; m is the number of cluster members in the last round; ζ and η are positive-valued weight coefficients that satisfy ζ+η=1; Tj is the time anchor j as a cluster head; Tthr is a time threshold value, which limits the value of Tj; E0_j is the primary energy of anchor node j and Er_j is its residual energy; Ea_j is the average residual energy of the cluster with which anchor node j was associated in the previous round, where tj decreases with increasing Ea_j; and random number nj∈(0,1) is used to avoid obtaining the same value of Er_j for different anchors to avoid conflict. We note that anchor nodes with higher values of cj may have a larger probability of being a cluster head. This divides the network into smaller clusters to reduce packet transmission delay. With regard to Tj, we note that MAs consume more energy than SAs. Therefore, Tthr is employed to prevent the MAs from running out of energy prematurely. Once Tj exceeds Tthr, the possibility of a node again being an MA drops rapidly according to a log function. The small value 0.01 is added to avoid a log function argument of 0.According to the broadcast package time of flighttji from MA j, SA i can establish a heuristic expression of opportunistic probability (OP) OPji as follows:(2)OPji=Er_i·1tji·β,where Er_i represents the residual energy of SA i and β is a constant. The value of tji is affected by the relative distance and delay between nodes j and i. The value of OPji increases with increasing Er_i and decreasing tji.During cluster head selection, when anchors receive the “Hello” package, they record the information of the sender and refrain from broadcasting the “Hello” package further. The candidate then ignores all “Hello” packages that are received subsequently. After timet1, all of the cluster head candidates have been selected, which become the MAs. After cluster head selection, if an ordinary anchor receives only a single “Hello” package from MA j, it joins the jth cluster. If it receives a “Hello” package from more than a single cluster head, it selects the cluster head whose broadcast message was first heard as the maximum-received-signal-strength cluster head. Once an ordinary anchor has selected its cluster head, it forwards a JOIN_CLUSTER message to gain admission to this cluster. We note that the network lifetime depends upon the anchor nodes’ times to live.Each MA distributes clock synchronization packets to its SAs. The intercluster data transmission quality is determined by routing. In Figure3, the red circles represent the MAs, the green circles represent the SAs, and the blue circles represent the relay anchors, such as C and G, which cooperate in the vMISO-OR scheme to forward packets from the MA that is denoted as A to that denoted as D.Figure 3
Packet forwarding with vMISO-OR.At the beginning of intercluster data transmission, the MA does not need to decide the next hop, as in conventional routing; it must only broadcast its clock synchronization packets withOPjd added to the packet head. As shown in Figure 3, anchor A broadcasts with OPad=0.5. After an SA receives a packet, the received OPjd is compared with the SA’s own OP, and if its own OP is greater, the packet is stored and forwarded to a neighboring cluster head. Thus, we have the set of SAs SA={B,C,E,F} and the set of relays RAD=B,C,G. The values of OPbd(3), OPcd(1), and OPgd(2) are all greater than OPad(0.5); therefore, candidates B, C, and G will forward packets. In contrast, OPed(0) and OPfd(0) are both less than OPad(0.5), so they retain their own clock synchronizations.As shown in Figure3, we assume that intercluster routing employs two cooperative anchors at most [22, 23]. The reasons for this assumption are as follows. (i) Including more nodes in a cooperative set will certainly not save energy because; due to the increased number of cooperative nodes, more circuit energy and synchronization overhead are required. In addition, increased training overhead will also increase the energy consumption. It has been shown that two cooperative nodes are much more energy-efficient than the SISO, 3∗3 MIMO, and 4∗4 MIMO models [23]. (ii) Based on this assumption, expansion to vMISO-based routing with two cooperative nodes is superior [24]. In practice, the routing will employ more than two candidate relay nodes that can receive and forward packets, such as B, C, and G. The forwarding anchors determine their response times according to the difference between their own OP values and those of the sending anchor, which limits the required data exchange. Suppose that the OP of relay anchor R is OPrd and that of the sending anchor is OPjd. Then, the response time tre is(3)tre=fΔOP=ψOPrd-OPjd,where ψ is a time constant that is determined by the transmission distance and the density of anchors. For a given xi′,yi′ and ψ, tre decreases with increasing OPrd. The intercluster data transmission algorithm is presented as Algorithm 1.Algorithm 1:Inter-cluster data transmission.
( 1 ) MA broadcasts data with its OPm; ( 2 ) Data received by its SAs; ( 3 ) While (no copy of data relayed) (4)  {If (OPs>OPm) (5)   {Add the data to its cache; (6)  tresponse=f(ΔOP)=f(OPs-OPm); ( 7 )   If (tcurrenttime<tcurrenttime+tresponse) ( 8 )     If (the number of data copies received ≤ 1) ( 9 )     Forward the data; ( 10 )   Else ( 11 ) Delete the data; (12) } ( 13 ) Else ( 14 ) Drop the data; ( 15 ) Return; (16) }If, within its response time, R receives forwarded packets from a higher-priority anchor, it deletes its stored packet copy. Without accepting any other packets from higher-priority forwarders, R acts as a relay to forward packets. As Algorithm1 shows, under the condition OPcd>OPbd, the response time of B is greater than that of C, which means that C is forwarding the packets and B deletes its stored packet copy; otherwise, B forwards its stored packet copy.


## 4.2. Wireless Clock Synchronization

Traditionally, we model the clock time as a continuous function of the clock skew (frequency difference)γ and the clock offset (phase difference) θ [20]: (4)Cmt=t,Cst=γ·t+θwhere Cm(t) denotes a reference clock of the sending anchor and Cs(t) denotes the local clock of the receiving anchor. In digital clocks, time is recorded by counting the number of periods of a repeating clock signal. At each rising clock edge of the periodic signal, an integer time counter is incremented.The primary problem of network synchronization is to resolve the observed time in (4). The algorithms that are considered here use a one-way message dissemination approach at the level of discrete clock ticks.Suppose that the anchors all transmit and receive the CCP clock check packets with the time stamps, and the initial master anchor transmits a CCP with periodT. In the kth round of message broadcasting, MA1 broadcasts a synchronization message CCP at T1,k and SA1 records its time T2,k at the reception of that message. Let Δk denote the interval between receiving a signal and the following initial local clock tick, which is caused by the clock offset. According to [25], the timing model of the kth broadcast message is given by (5)T2,k≈γ·T1,k+θ+Xkwhere Xk is the random variable delay in the transmission.To achieve global clock synchronization, it is necessary to estimate the clock synchronization parameters of the whole network directly from the time stamps at the same time. We generalize (5) to transmission from a MA j to a slave anchor i:(6)T2mj,i=γi·T1mj+θi+Xmj,iwhere T1mj is the transmission time at master anchor MA j and Xmj,i is a zero-mean independent Gaussian random variable with variance Vji.We can treat the skew and offsets on different time scales as in [15]. That is, we can adjust the parameters γi approximately every Ts time units and adjust the parameters θi approximately every τs time units, with Ts≫τs; the absolute values of these quantities will depend on the nature of the clocks and the settings. When computing the offset, we treat the skew as constant (and known), so we can apply the theory that we presented earlier. On longer time scales, we adjust the skew using the same iterative procedure (with different variables).Assuming that only clock offsets need to be estimated, the joint probability density function ofT2mj,i is expressed as(7)fT2mj,i∣T1mj,θi=∏j,i12πVjie-T2mj,i-T1mj-θi2/2VjiDifferentiating the logarithm of (7) with respect to T1mj and θi, we can obtain two sets of equations. Their solutions are obtained by maximizing the joint probability density.(8)T1mj=∑iT2mj,i-θi/Vji∑i1/Vjifor eachj,θi=∑jT2mj,i-T1mj/Vji∑j1/Vjifor eachi.The estimated clock skewγi is obtained in the same way. Based on the estimated value, the Kalman filter algorithm [26], which has good tracking performance and low error, can be used to trace the clock skew and clock offset.The performance will significantly degrade if the line-of-sight path or first path arrival time is changed or disturbed. The multiple relays can cooperate to send the CCP to the next-hop MA. We will use an auxiliary setup with only time intervals, as shown in Figure5.In Figure5, R1 and R2 are the relays. When receiving a signal from the preceding transmitter R1, the subsequent transceiver R2 transmits after a fixed delay Δ0 to avoid interfering signals from R1 and MA2 during an epoch. As indicated by the delay lines, Δ0 can be generated independently of the local clock, and T≫Δ0>max⁡transmissionrange/c. The clock of MA2 is corrected twice in a period of T according to the improved results.The clock tracking is implemented using the Kalman filter implementation, with the main “process” function taking two inputs [5]: (1) the slave anchor CCP receiving time in its time base and (2) the master anchor CCP transmitting time in its time base and the CCP TOF.According to Figure6, the Kalman filter uses the CCP receiving time, the CCP transmitting time, and the best estimated time between the master unit and the slave unit. The CCP TOF is essentially a constant fixed offset (for any fixed-position master-slave pair of anchors) that results from the time of fight (TOF) of the CCP between the master unit and the slave unit. This constant can be calculated based on the anchors’ (X, Y, and Z) coordinates. Finally, the Kalman filter obtains the real relative clock offset and the best estimated relative clock offset between master-slave units. We select the data of a passive receiving anchor to plot in MATLAB, as shown in Figure 7.In Figure7, the green curves denote the real relative clock offset and the red curves represent the best estimated relative clock offset. We set T as 600 ms and Δ0 as 20 ms. With clock synchronization by Kalman filtering, the red curves seem to be more smooth and steady, while the green curves are volatile and are affected by the noise and temperature drift. According to Figure 7, the error is approximately 30 ns; at the speed of light, ns-level error influence is very large. Thus, the Kalman filter also smooths the error. Comparing Figure 7(a) (which corresponds to Figure 4) and Figure 7(b) (which corresponds to Figure 5), it is obvious that the estimated clock offset is steadier due to the cooperative transmission diversity. The simulations show that the clock synchronization with Kalman filtering better tracks the reference clock offset. Therefore, it obtains a better prediction for the basically identical clock between the reference-passive anchors (e.g., master-slave anchors), which is advantageous for improving the tag location accuracy.Figure 4
Space-time diagram of a reference MA and a SA.Figure 5
Space-time diagram of two relays.Figure 6
Relative clock variation with Kalman filtering.Figure 7
Relative clock offset with Kalman filtering.
(a)
With one reference anchor (b)
With two reference anchors


## 5. Experimental Results and Performance Evaluation

Clock synchronization packets are distributed to the anchors with different routing protocols. For the lifetime optimization and energy minimization objectives, we employed simulation to compare the performance of vMISO-OR with those of two other routing schemes: SISO relay (noncooperative routing) and routing with clustering using ExOR [27] with an equivalent underlying technology. The simulation parameters are listed in Table 1.Table 1
Simulation Parameters.
Parameter Value Number of connections 1-10 Start sending data packet 30.01 Sec Stop sending data packet 4 Packets/Sec Buffer queue 50 Listening mode current 18.8 mA Transmitting mode current 17.4 mA Receiving mode current 19.7 mA Clear channel assessment 128μSec Active radio current 19.7 mA Byte transmission time 32μSecFigure8 reports the end-to-end delay performances of the three routing schemes. According to the figure, both vMISO-OR and SISO-RELAY, which are based on the response time, demonstrated better performance than the ExOR protocol. However, vMIMO-OR demonstrated worse performance than SISO-RELAY, which is due to multiple relay selection, although the difference is not typically significant.Figure 8
End-to-end average delay versus packet sending speed.Figure9 demonstrates that vMISO increasingly outperforms the noncooperative systems in terms of throughput. Moreover, we observe that as time increases, the average throughput gradually stabilizes. The throughput of ExOR remains approximately 120 kbps, while the throughput of SISO-RELAY stabilizes at approximately 250 kbps. However, the proposed vMISO-OR routing scheme attains a throughput of up to 300 kbps, which represents a significant improvement.Figure 9
Good throughput versus sending time.In the next simulation, we considered the packet loss ratio versus packet sending speed. As shown in Figure10, with increasing packet sending speed, the ExOR protocol demonstrated the highest packet loss ratio, and the vMISO-OR protocol demonstrated the lowest packet loss ratio, owing to its implementation of cooperation. Both vMISO-OR and SISO-RELAY are based on the response time, but the forwarder priority of ExOR is included in every packet header. Low packet loss ratio is frequently caused by packet congestion; thus, a time-driven OR is more robust with respect to packet sending speed.Figure 10
Packet loss ratio versus packet sending speed.Figure11 provides network lifetime curves during simulation rounds for the proposed vMISO-OR protocol and the SISO-RELAY and ExOR protocols. As the run time increases, particularly after 50 rounds, the vMISO scheme, which is based on the clustering of surviving (available) anchors and number of surviving anchors to maintain relative stability, preserves the survival of 85% of all network anchors and effectively extends the network lifetime by approximately 40% compared to SISO-RELAY.Figure 11
Anchor survival rate versus run time.The simulation results show that the routing scheme has better performance in terms of the energy balance of the whole network. In this section, experiments were conducted to evaluate the performance of the proposed vMISO protocol proposed. The experiments were based on our team’s independently developed hardware platform, and the location chip was DW1000. The monitored field was 40.8 m × 25.2 m, over which 35 anchors were evenly distributed, and the area was divided evenly into 24 grids. The location area was previously divided into four clusters, and each cluster had only one MA. All the anchors and test tags were fixed in place. The vMISO scheme was CCP transmission by two relay anchors to the next cluster, and the SISO scheme was CCP transmission by only one relay anchor; in both schemes, the MA broadcasted the CCP to the SAs for inner-cluster CCP distribution. In Figure12, the green circles represent the anchors, the purple stars indicate the actual tag positions, the purple circles represent the recovered tags, and the yellow circle represents the initial MA. Anchor 1, anchor 2, anchor 3, and anchor 4 were the anchors in the different clusters; anchor 5 was the comparison point.Figure 12
Experimental environment at Hainan University Fellowship Hall.The MA periodically broadcasted the CCP to the SAs, and the SAs maintained clock synchronization with the MA. The tags sent Blink packets to the anchors. After receiving the Blink packets, the anchors sent the data back to the location engine to calculate the precise location coordinates of all tags.To analyze the clock synchronization performance, as shown in Figure12, anchor 1 and anchor 5 were selected randomly. The tag broadcasted Blink packets and the two anchors received the Blink packets in the broadcast range. The TDOA was calculated by the location engine according to the tag’s broadcasted Blink packets; arrival times at the anchors are as follows: (9)TDOA1,5=TOA1-TOA5The calculated distance difference from the tag to anchor 1 and anchor 5 isΔd^1: (10)Δd^1=c·TDOA1,5where c is the speed of light.The real distance difference from tag to anchor 1 and anchor 5 isΔd1: (11)Δd1=d1-d5where d1 and d5 are the real distances from the tag to anchor 1 and anchor 5, respectively.Then, the calculated distance errore is defined as follows:(12)e1=Δd1-Δd^1From (9)–(12), if anchor 1 and anchor 5 are absolutely synchronized, the TDOA is only relative to the difference in the Blink packets’ flight times from the tag to anchor 1 and anchor 5, and the flight time is generally proportional to the distance of flight. Thus, the distance error e will be equal to zero in theory. If anchor 1 and anchor 5 are not well synchronized, the TDOA is also disturbed by the time base difference between anchor 1 and anchor 5. The larger the time base difference is, the larger the distance error e is.In the same way, we obtaine2, e3, and e4. The total network test configuration is shown in Table 2. For every e, 30 measurements were performed at each test point, and we obtained 30 distance errors. We tested the vMISO scheme and the SISO scheme. The cumulative distribution functions (CDF) of the distance errors for each scheme are shown in Figure 13.Table 2
Test Configuration.
Parameter Value Channel 2 Preamble 9 PRF 64 MHz Preamble length 128 Data rate 110 kbit/sFigure 13
CDFs of distance errors.
(a)
vMISO scheme (b)
SISO schemeIn both Figures13(a) and 13(b), e3, which is shown in blue, is on the left, which means that it represents the lowest distance error. e2, which is shown in green, is on the right, which means that it represents largest distance error. e1 and e4 are in the middle. Anchor 3 and anchor 5 are in the same clusters; their distance error e3 ranges from 2 cm to 15 cm, since the distance error mainly comes from other factors but not from the different time bases. Anchor 2 and anchor 5 are in different clusters, and there are some clock differences during the CCP multihop transmissions, so the different time bases mainly affect the distance errors. By comparing Figures 13(a) and 13(b), e1, e2, and e4 in vMISO scheme are lower than those in the SISO scheme, with differences of approximately 5 cm. The vMISO scheme has lower distance errors than SISO scheme because of the diversity gain of the vMISO multiple transmission. The existing distance error is caused by many factors, such as the interference error from the multiple anchors of the large area, the anchors’ coordinate measurement errors, and the non-line-of-sight transmission.


## 6. Conclusions

In this paper, we proposed a cross-layer vMISO CCP transmission protocol for facilitating the scalability of UWB indoor localization networks. The CCP transmission intracluster is based on broadcasting, and the intercluster transmissions use two vMISO relays. The protocol is modeled as the relative clock synchronization of multiple master anchors. The simulation results show that the vMISO-OR protocol can improve the network survival time and the network throughput. Although there is a delivery delay, it can be eliminated, as the clock synchronization algorithm in (6)–(9) is based on the time stamp of the CCP transmission, and the tag clock correction is based on the clock offset difference. The experimental results indicate that the vMISO scheme has better intercluster synchronization performance than the SISO scheme. The results of this analysis verify that the proposed vMISO-OR protocol can improve the routing performance, as discussed in Section 4.1, and can help improve the clock synchronization for a large-area network, as discussed in Section 5. The present work disregards the handover of mobile tags from one area to another, which will be investigated in a future study.



---

*Source: 1563704-2018-06-28.xml*