Transmission Power Controlled Localization with Topology Building for NLOS Environments

Abstract

The network which knows location of all nodes can improve the network capacity and lifetime in location-aware networks. However, localization algorithm of the network has to update its target node location due to mobility of target nodes and intermittent occurrence of interference. The update procedures cause frequent broadcasting and calculation for relocalization; therefore, maintaining the transmission power control (TPC) in the wireless sensor networks (WSNs) is valuable to the network. This paper proposes a new algorithm of transmission power controlled localization for indoor environment. Firstly, we propose minimum spanning tree (MST) based topology control with location error compensation algorithm to improve location accuracy and prevent target nodes from connecting to unstable links in non-line-of-sight (NLOS) condition. Secondly, we use TPC algorithm to improve the network lifetime. Each target node dynamically adjusts the power and the received signal strength (RSS) target by using the TPC algorithm. Experimental results show that the proposed algorithm compensates for location errors in NLOS condition while reducing the transmission power.

1. Introduction

In WSNs, information of node location is helpful for network performance, routing, and practical implementation [1]. The energy conservation is very important to utilize these merits because nodes generally are operated on small batteries as a power source. In this paper, we propose transmission power controlled localization of MST [2] based topology algorithm. To improve communication efficiency and prolong network lifetime, topology control is an efficient method. It can remove inefficient wireless links to reduce energy consumption and increase network capacity in WSN [3, 4]. Most topology control algorithms assume that all nodes know their exact location and distances between each pair of neighbor nodes. In the real networks, the distances may have a large measurement error for NLOS links. This large scale location error causes many problems in the networks. To solve the problem, we use geographical MST based topology control algorithm to compensate for location errors in NLOS conditions and adapt TPC procedure to the algorithm. In WSNs field, there are many TPC studies [5, 6] which mainly focus on improving the channel capacity. To add TPC to localization algorithm, we need TPC algorithm to be easily implemented with low complexity. The proposed TPC algorithm uses only RSS_target which is established by using the $\text{SIN}{\text{R}}_{\text{target}}$ satisfying the IEEE 802.15.4 receive-sensitivity requirements [7]. Because we reject NLOS links in advanced step, the TCP algorithm is endurable for NLOS interference.

In the next section, we explain problems which cause NLOS environments. Then, we present the proposed algorithm in Section 3. The performance evaluation is in Section 4. Finally we present conclusion in Section 5.

2. Problem Statement

In the network environments, there are many obstacles. Particularly in indoors environments, there are many obstacles such as furniture, concrete walls, doors, and objects. The obstacles create NLOS environments and degrade accuracy of locations in IEEE 802.15.4 based location-aware networks [8].

For example, we use reference data which show NLOS environments effect as shown in Figure 1 [9, 10]. This NLOS environment effect is also introduced in other papers [11, 12]. To analyze the NLOS effect, we implemented experiments in NLOS environment conditions. In the experiments, we measured the ranging distances by using received signal strength indicator (RSSI) and the data packet reception ratio (PRR) between two mobile nodes. The real distance between two mobile nodes is 10 m. To generate various NLOS environment conditions, we placed a concrete wall and furniture between two nodes for each experiment. The ranging distance is close to the real distance in the line-of-sight (LOS) condition and has large bias and irregular fluctuation in the NLOS conditions. The average ranging distance is 9.5 m, 12.9 m, and 17.5 m for each environment of LOS, NLOS with obstacle of furniture, and NLOS with obstacle of concrete wall. The average PRR is 100%, 93.5%, and 52.5% for each environment. For each measure, 1000 broadcast packets have been transmitted. The results show that NLOS environment is unreliable to communicate and increase the number of retransmissions and energy consumption. The MST based geographical topology has problems caused by the NLOS environments, because the edge cost of the topology is defined by the Euclidean distance. The NLOS environment effect makes the link of the topology inaccurate and inefficient. We describe an example topology to show the topology which connects edge of NLOS links, as shown in Figure 2. In Figure 2, we locate target nodes, $\{w,u,z\}$ , from anchor nodes, $\{\mathrm{1,2},3\}$ , without NLOS environment effect.

Figure 1

The reference data for experiment topology and RSS measurement results over time.

Figure 2

The example of topology including NLOS link.

The geographical topology algorithm connects target node “u” to “w,” by using location information. This link causes the degradation of PRR and increases the number of retransmissions. In the next section, to solve these problems, we propose the algorithm which uses two types of neighbor nodes information.

3. Proposed Algorithm

We design the transmission power controlled localization with topology building for the location-aware networks. We assume that the location-aware network consists of the anchor nodes which know their location and the target nodes which do not know their location. The proposed algorithm has the following steps: gathering data from other neighbor nodes and localization, building geographical topology, and location error correction with adjusting transmission power.

All anchor nodes periodically broadcast a packet including their location and node ID. Using the data of the packet, target node which receives a few packets from its neighbor anchor nodes measures the distances between itself and neighbor anchor nodes by using RSS. Based on the shadowing model, the received signal strength ${\text{RSS}}_{ab}$ between the nodes a and b is given as follows [13]:

$$\begin{array}{cc}& {\text{RSS}}_{ab}=P\left(d_{\mathrm{0}}\right)+\mathrm{10}\hspace{0.17em}\mu {\log }_{\mathrm{10}}\left(\frac{d_{ab}}{d_{\mathrm{0}}}\right)+X_{\sigma },\end{array}$$

(1)

where $P(d_0)$ is the known reference power value in dBm at a reference distance $d_0$ , μ is the path loss exponent at which the received power decreases with distance, $d_{ab}$ is the real distance between the nodes a and b, and $X_{\sigma }$ is the Gaussian random variable of zero mean with standard deviation ${\sigma }_d$ . Then through mathematical operations in (1), we obtain the following equation:

$$\begin{array}{cc}& {\tilde{d}}_{ab}=d_{\mathrm{0}}·{\mathrm{10}}^{\left(P_{\mathrm{0}}-P_{ab}\right)/\mathrm{10}\mu }.\end{array}$$

(2)

By (2), we measure average value of distance ${\tilde{d}}_{ab}$ between the nodes a and b. After measuring the distance, the target node estimates its location by using the distance. To estimate the location, we use the least square estimation (LSE) localization method [14, 15]. The estimated location can be obtained by the following equations:

$$\begin{array}{cc}& {\widehat{x}}_k=\underset{x\in X}{\text{argmin}}{\displaystyle \sum }_i^N{\left(\parallel x-P_i\parallel -\tilde{d}\left(i\right)\right)}^2,\end{array}$$

(3)

where ${\widehat{x}}_k$ is the estimated location of target node k, N is the number of the received anchor nodes, $P_i$ is the location of anchor node i, $\tilde{d}(i)$ is the ranging distance between the anchor node i and the target node k, X is the network area, and $\parallel \parallel$ denotes the Euclidean norm.

After estimating the location, all target nodes broadcast the packet that includes their estimated location and node ID. Each of the target nodes separates received packets into “from anchor node” and “from target node” and then constructs the neighbor information table as shown in Table 1. After constructing the table, the target nodes build the geographical topology with position by using the MST based Prims algorithm [16] (see Algorithm 1).

Table 1

Neighbor information table of node $\_\mathit{3}t$ .

	ID	RSS	Distance	Position
From anchor nodes	1a	−50 dBm	$\tilde{d}(\mathit{1}a,\_\mathit{3}t)$	$(x_{\mathit{1}a},y_{\mathit{1}a})$
	2a	−58 dBm	$\tilde{d}(\mathit{2}a,\_\mathit{3}t)$	$(x_{\mathit{2}a},y_{\mathit{2}a})$
From target nodes	_1t	−40 dBm	$\tilde{d}(\_\mathit{1}t,\_\mathit{3}t)$	$({\widehat{x}}_{\_\mathit{1}t},{\widehat{y}}_{\_\mathit{1}t})$
	_2t	−62 dBm	$\tilde{d}(\_\mathit{2}t,\_\mathit{3}t)$	$({\widehat{x}}_{\_\mathit{2}t},{\widehat{y}}_{\_\mathit{2}t})$

Algorithm 1

Input: A non-empty connected weighted graph with vertices V end edges E (the weights can be negative)

Initialize: ${\mathrm{V}}_{\text{NEW}}=\left\{{\mathrm{x}}_{\mathrm{i}}\right\}$ , where x is an arbitrary node (starting point) form $V,{\mathrm{E}}_{\text{NEW}}=\{\}$

Repeat until ${\mathrm{V}}_{\text{NEW}}=\mathrm{V}$ :

Choose an edge $\{u,v\}$ with minimal weight such that u is in ${\mathrm{V}}_{\text{NEW}}$ and v is not (if there are multiple

edges with the same weight, any of them may be picked)

Add v to ${\mathrm{V}}_{\text{NEW}}$ and $\{u,v\}$ to ${\mathrm{E}}_{\text{NEW}}$

Output: ${\mathrm{V}}_{\text{NEW}}$ and ${\mathrm{E}}_{\text{NEW}}$ describe a minimal spanning tree

The topology does not consider NLOS environment which causes the error of estimated location. Figure 3 shows the inefficient link that is caused by location error. In Figure 3, we can find that the location error causes a constrained link ( $a^{\prime }$ -c).

Figure 3

Example: inefficient link of topology.

For detecting location error, we compare ranging distance which is obtained by RSS ranging technique [17] for each other nodes and link distance which is used to build geographical topology as MST algorithm weight. If the difference of distance is longer than threshold value, ${\Delta }_{\text{th}}$ , we treat the link as inefficient link. To achieve a desired performance for the proposed approach, ${\Delta }_{\text{th}}$ should be carefully determined. In this paper, we set the value of ${\Delta }_{\text{th}}$ to 3 ${\sigma }_d$ . Since ${\sigma }_d$ means standard deviation of Gaussian noise in LOS environment, 3 ${\sigma }_d$ value limits the probability of error to be less than 1%. Now, each target node separates the link into reliable and unreliable link. Target nodes can do relocalization using only distances in LOS environment, because the reliable link means the link is in LOS environment.

After relocalization, we control transmission power of nodes which are connected with reliable link. To adjust transmission power, we need to consider proper SINR and RSS value. In [17], the relation between the SINR and the RSS is given by

$$\begin{array}{cc}& \text{SINR}=\mathrm{10}\log \frac{{\mathrm{10}}^{\text{RSS}/\mathrm{10}}-{\mathrm{10}}^{P_N/\mathrm{10}}}{{\mathrm{10}}^{P_i/\mathrm{10}}},\end{array}$$

(4)

where $P_N$ and $P_i$ are, respectively, the noise floor of the receive node and the received interference strength in dBm. If we ignore other interference, we can set $P_i=P_N$ . Through [7, 18], we set the $\text{SIN}{\text{R}}_{\text{target}}$ which satisfies the IEEE 802.15.4 receive-sensitivity requirement with 20 bytes packet size as follows:

$$\begin{array}{cc}& {\text{SINR}}_{\text{target}}\approx \mathrm{0.4021}\hspace{0.17em}\text{dBm}.\end{array}$$

(5)

By using (4) and (5), we can set RSS_target as follows:

$$\begin{array}{cc}& {\text{RSS}}_{\text{target}}\approx P_N+\mathrm{3.216}.\end{array}$$

(6)

Following the experiment results in [17], we have to consider difference between the analytical RSS target and the empirical RSS target. By using the results of [17], we redefine the RSS_target of previous equations as ${\text{RSS}}_{\text{targe}{\text{t}}_{\text{analytical}}}$ and the empirical RSS target as RSS_target:

$$\begin{array}{cc}& {\text{RSS}}_{\text{target}}={\text{RSS}}_{\text{targe}{\text{t}}_{\text{analytical}}}+\mathrm{2}=P_N+5.216.\end{array}$$

(7)

After relocalization, we obtain the geographical topology with correct location and updated neighbor information table. We can easily control transmission power through the following equation, because we know present RSS values from the new table and unstable noise floor by using ACK packet:

$$\begin{array}{cc}& {\text{TP}}_{T\mathrm{2}}={\text{TP}}_{T\mathrm{1}}+{\text{RSS}}_{\text{target}}-\text{RSS},\end{array}$$

(8)

where $\text{T}{\text{P}}_{T1}$ is transmission power at time $T1$ and $T1<T2$ . If $\text{RS}{\text{S}}_{\text{target}}$ is stronger than RSS, we can save the difference. If we follow (8), next transmission may be failed because of changeable noise floor and RSS variance. To avoid the transmission failure, we need to give margin power, $\text{mP}$ . In this paper, we set the $\text{mP}$ as a 3 dB, because the measured RSS values have around 3 dB variance on the average. After considering margin power, (8) is redefined as follows:

$$\begin{array}{cc}& {\text{TP}}_{T\mathrm{2}}={\text{TP}}_{T\mathrm{1}}+{\text{RSS}}_{\text{target}}-\text{RSS}+\text{mP}.\end{array}$$

(9)

4. Performance Results

We evaluate the performance of the proposed algorithm. This step is composed of the following phases: small scale simulation to show corrected location and large scale simulation to show saved energy. Each phase has the same simulation parameter as shown in Table 2.

Table 2

Simulation parameters.

Parameter	Description	Value
$P_{\mathit{0}}$	Path loss for $d_{\mathit{0}}$	−35 dBm
$d_{\mathit{0}}$	Reference distance	1 m
μ	Path loss exponent	2.98
$\mathrm{\sigma }$	Standard deviation of RSS	1 dB
${\mathrm{\sigma }}_d$	Standard deviation of $\tilde{\mathrm{d}}()$	0.8 m
Tr	Radio range	15 m

We conduct small scale simulation to show the procedure of localization. In this simulation, the other parameters are defined as follows: 10-meter network diameter, 4 anchor nodes, 7 target nodes, and 1 obstacle which causes NLOS environments. Figure 4(a) shows the constructed topology. In Figure 4, concrete wall is described as rectangle. Because of the concrete wall, two target nodes described as $\{2e,4e\}$ are inaccurately located and two links described as dashed line are in NLOS environment. Therefore, the first topology as shown in Figure 4(a) has large location error. The average location errors of topology “before” and “after” are 2.4 m and 0.4 m, respectively.

Figure 4

Small scale simulation: (a) topology before location error correction and (b) topology after location error correction.

We assure that the topology in Figure 4(b) has stable link and efficient network performance compared to that in Figure 4(a), because the result shows that the algorithm corrects location error and avoids NLOS link.

We conduct large scale simulation to show saved energy. In this simulation, the other parameters are defined as follows: 100-meter network diameter, 121 anchor nodes, 500 target nodes, and 30 obstacles which cause NLOS environments. Figures 5(a) and 5(b) show the constructed topology. From the topology, we calculate average location error to show that the proposed algorithm enhances location accuracy for large network. In Figure 5(b), the proposed algorithm finds unreliable links caused by obstacles and erases the link information. If the erased link has the shortest distance, the algorithm has to use longer distance link for building topology. That is why the average path length in topology after location error correction is longer than the average path length in topology before location error correction. These results are indicated in Table 3.

Table 3

Simulation results for localization.

	Before correction	After correction
Average location error	7.06 m	2.55 m
Average path length	2.94 m	3.01 m

Figure 5

Large scale simulation: (a) topology before location error correction and (b) topology after location error correction.

To evaluate saved energy, we calculate the total energy consumption for each broadcast [19]:

$$\begin{array}{cc}& E_{\text{saved}}={\displaystyle \sum }_{u\in N}E\left(u\right),\\ E\left(u\right)=R_{\text{received}}+\text{mP},\end{array}$$

(10)

where $E(u)$ depends on the transmission radius, $R_{\text{received}}$ is the received RSS value, and $\text{mP}$ is explained in Section 3. This total saved energy consumption is compared with total energy consumption for maximum transmission range:

$$\begin{array}{cc}& E_{\text{total}}={N·R_{\max }}^{\mathrm{2}},\end{array}$$

(11)

where N is the number of target nodes and $R_{\max }$ is the average RSS value to maximum transmission range.

We calculate the saved energy ratio which is defined as follows:

$$\begin{array}{cc}& \text{saved}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{energy}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{ratio}=\left(\frac{E_{\text{saved}}}{E_{\text{total}}}\right)·\mathrm{100}.\end{array}$$

(12)

We adapt TPC procedure to the topology in Figure 5(b) for calculating saved energy ratio. The result is 71.9% from (12), which shows that the proposed algorithm saves transmission energy about 30%.

5. Conclusion

This paper presents a transmission power controlled localization algorithm which builds MST based topology and saves transmission power by using a TPC algorithm. In the proposed algorithm, we avoid links which are affected by NLOS environment and build geographical topology by using information of neighbor table. After building topology, we adjust transmission power through the TPC algorithm which uses RSS_target to save surplus energy. In Section 4, the simulation results show that the proposed algorithm reduces average location error and energy consumption. The proposed algorithm is focused for the network which has to frequently update its location and overcome unstable environments, especially indoors. We expect that the proposed algorithm improves the network lifetime performance and utilizations indoors.