An Energy Efficient Anchor-Free Localization Algorithm for No-Identity Wireless Sensor Networks

Abstract

A wireless sensor network (WSN) model by analyzing the limitations of existing localization algorithm is proposed in this paper. Specifically, neither the anchor nor the ID is required in the proposed model, and the node function is limited. The hardware function of the node in our model is independent of the MAC protocol. Moreover, based on the proposed WSN model, we design an energy efficient anchor-free localization algorithm for no-identity WSN. Instead of multiple measurements, mathematical calculation is adopted to acquire the position information. Subsequently, the effectiveness of the algorithm is confirmed by rigid theory. The simulation results show that the proposed algorithm can improve the performance of localization and energy efficiency in WSN significantly.

1. Introduction

Wireless sensor network (WSN) is a special kind of Ad hoc network [1], and it is usually applied in the areas which are difficult for wiring or power supply, depopulated regions (e.g., pollution, environment that cannot be destroyed, or hostile areas), some other emergency circumstances (such as natural disasters and damage of the fixed communication network), and so forth. The WSN does not need the support of fixed network. Moreover, it has characteristics of easy deployment, robustness, self-organization, and so forth [2, 3]. And hence, it has attracted wide attention and has been applied widely in military, industry, traffic, environmental protection, healthcare, and other fields [4–6]. Generally, WSN is composed of numerous cheap and tiny sensor nodes whose functions are relatively weak, and it interacts with the outside world using the gateway. WSN is usually deployed in a target area in the form of multihop network, which is dynamic, wireless connected, and self-organized. The main function of WSN is to collect and monitor physical or environmental conditions in the target area and send the information through the network to the end users [7]. Normally the sensor nodes and gateway are stationary once their deployment completed, and this is the main difference between the Ad hoc network and the WSN. Sensor nodes, perceptual objects, and the end users constitute the three elements of sensor networks [8].

Different from traditional networks, the nodes of WSN are randomly distributed in the sensing area and do not have wired connection and their positions and connectivity can be managed and maintained by routers or other equipment [9–11]. The energy and computing ability of node are limited; furthermore, the direct communication distance between nodes is short, and hence the complex operation cannot be done by the sensor node [12–14]. WSN needs operations (such as neighbor relationships discovery, nodes location calculation, and dynamic routing selection) to realize the discovery of network structure. Considering the localization problems mentioned above, it is necessary for each node to obtain the following information in the initialization stage: sink node position, neighbor node ID, and the distances and angles between neighbor nodes. And then, the information is used to calculate their relative positions or absolute positions in the network.

As mentioned above, ID is usually necessary for localization method, but it limits the flexibility and scale of the network. However, there is almost no research on no-identity WSN in existing localization algorithms. In this paper, we propose a network model without setting ID information. On one hand, the node function is weakened, so that the network can complete communication and localization regardless of node ID information. On the other hand, we increase the flexibility of the entire network; that is, instead of obtaining the global information through the sink node, the local information of nodes is used to maintain the network.

In this paper, we propose an energy efficient anchor-free localization algorithm for no-identity WSN. The rest of this paper is organized as follows. In Section 2 we analyze the related researches on WSN localization problem. The proposed WSN network model is presented in Section 3; moreover, a detailed design of a localization algorithm is proposed based on this model. In Section 4, the proposed algorithm is analyzed theoretically. Then, simulations and experimental results of the algorithm are provided in Section 5. Finally, we conclude the paper in Section 6.

2. Related Work

2.1. Methods of Distance and Angle Measurement

The locations of the sensor nodes can be classified as absolute locations (i.e., the coordinate in world coordinate system) and relative locations (i.e., the coordinate within the sensing area). In general applications, the relative positions of nodes within the entire network are usually needed to distinguish nodes. The essence of localization is to obtain the position of the sensor nodes. However, the locations of the sensor nodes and the distances between each node are unknown in the initial stage, which can be obtained via measurement and calculation.

Ranging technologies include RSSI (Received Signal Strength Indication), ToA (Time of Arrival), and TDoA (Time Difference of Arrival) [15]. These methods are mainly based on the hardware implementation; that is, the hardware devices are employed to detect transmission signal and calculate distance. RSSI calculates the distance based on the energy loss of wireless signal transmission; that is, the receiver detects the signal strength after receiving the packet, and the distance between the sender and the receiver is calculated according to the degree of signal attenuation [16]. In RSSI, it is easy to implement since the hardware requirements are not high, and the measuring error is relatively small. However, the path loss coefficient has to be set in this method, which is greatly influenced by the environmental change. ToA calculates the distance between the sender and the receiver according to the signal propagation time. This approach requires the synchronization of the sender and receiver, which is difficult to achieve under the distributed environment of WSN. Then, TDoA is proposed to overcome this defect. In TDoA, the distance is calculated by the Time Difference Of Arrival, and the sender needs to send two data packets in two different frequency bands, such as radio spectrum and infrared wavelengths, and then the difference of packet arrival time is used to calculate the distance [17]. This method avoids the synchronization problem, which is easy to be deployed in a distributed environment. However, the measuring error is relatively large, and the energy consumption is huge.

Similarly, hardware is used to realize the angle measuring technologies. The basic idea is that the receiver perceives arrival direction of signal by antenna array or other devices to calculate the relative angle between the receiver and sender. Finally, the node location can be calculated through triangulation method [15, 16]. The challenge of this method is how to transform the local angle information into unified global angle information.

2.2. The Existing WSN Localization Algorithms

The existing localization algorithms can be classified into anchor-based algorithms and anchor-free algorithms. Anchor is a node with localization device. Energy, information transmission capacity, and computing power of anchor are not restricted. The core of the anchor-based algorithms is that the anchors broadcast localization information to the network, and the locations of the sensor nodes are obtained by comparing and calculating the information received from different anchors. These algorithms have the advantages of high accuracy, less energy consumption, and low computation complexity. But the biggest drawback is that the anchor nodes need to be deployed on the special location of sensing area, which limits the scale and scope of the sensing area. Furthermore, the deployment flexibility is poor and the hardware cost is high. So the research on this kind of algorithm is limited. Anchor-free algorithms are research hotspots currently, and the core idea is to replace the anchor using the sink node. The sink node sends angle information, distance information, and so on to sensor nodes, and sensor nodes use such information to calculate their locations themselves. The anchor-free algorithms overcome the inflexibility of the anchor-based algorithms, but it needs a lot of communication and computation of sensor nodes, which aggravate the nodes energy consumption. Then, the network lifespan is reduced, and the error is relatively big.

WSN localization algorithms are proposed based on the angle and distance measurement methods as mentioned in Section 2.1, and the information of neighbor node is mainly used to do localization. Čapkun et al. proposed a Self-Positioning Algorithm (SPA) in [18]. The algorithm used the distances between the nodes to build a relative coordinate system in which the node positions were computed. However, the SPA algorithm required a lot of computation and communication between nodes in the process of positioning, and the computational complexity increased with the number of nodes by exponential growth, which was not suitable for large-scale network.

Iyengar and Sikdar analyzed the defects of the SPA and proposed a Scalable and Distributed GPS Free Positioning for Sensor Networks (SDGPSN) [19]. The algorithm adopted the distributed concept, and cluster head was used to establish global coordinate system, which accelerated the execution speed and reduced the computational complexity. Therefore, SDGPSN was more suitable for large-scale network deployment. But the localization error would be accumulated during clustering, which led to low global localization accuracy. Moreover, huge communication was required in this algorithm, and this resulted in large energy consumption.

The anchor-based algorithms have been described previously. Youssef et al. proposed an Accurate Anchor-Free Localization (AAFL) algorithm based on clustering [20]. The localization efficiency was ensured without the help of anchor, and the localization error was small. However, high connectivity of the network was required in this algorithm, and hence the flexibility of the network structure would be affected. Furthermore, the communication burden of the edge nodes would be larger than other nodes, and the life span of the network would be affected since the edge nodes were exhausted earlier due to overuse.

Qu and Wicker proposed a lightweight anchor-free localization-routing algorithm on the view of a special application, which sets the sensing area as a circular form and the sink node to be located in the center point [21]. In order to realize routing selection, the neighbor node list information would be formed during localization. But the localization accuracy of the algorithm was not high, and the error would be accumulated in each node. Consequently, the algorithm had a strict application background, which was out of universality. And the routing selection was simple, which could not realize the global dynamic adjustment.

In 2008, Jordt et al. proposed an anchor-free localization algorithm which could obtain the sensing range [22], and the algorithm achieved accurate localization without using anchor. Similar to the algorithm in [21], in order to realize the global unification, the location information of sink node was used to adjust local coordinate system. Compared with the algorithm in [21], the localization of this algorithm was more accurate. However, the communication cost was high, and the energy efficiency was low since the energy consumption in positioning stage was excessive.

An algorithm named LOCOMOTE was proposed in [23] to realize data transmission and localization at the same time, which had the advantages of simplicity, high robustness, and good dynamism. However, all the nodes should communicate directly with the sink node, which limited the scale of the network significantly. Additionally, the energy consumption of flooding transmission was too large, and the energy efficiency was relatively poor.

In [24], the researchers added a few shortcuts to reduce the average energy expenditure per sensor node, and hence, energy efficiency and accurate localization have been achieved. In [25], RSSI was used to improve the localization accuracy, coverage, and robustness. References [26–28] described some methods for WSNs to self-locate in indoor environments. Moreover, mobile anchor was proposed to help localization in [29, 30]. Some improvements had been achieved, but anchor was still necessary in the proposed algorithms.

Although existing anchor-free localization algorithms can solve the localization problem without anchor node, there still exist some defects, such as high computation complexity, low localization accuracy, and lack of theoretical support. Furthermore, most of the existing researches focus on improving the localization accuracy, and hence the node energy consumption problems have been ignored, which leads to low energy efficiency in these algorithms. Therefore, how to realize fast, accurate, and energy efficient node localization based on limited information is the focus and trend of future research.

3. The Proposed Algorithm

3.1. System Model

Firstly, the characteristics of the system model are introduced in detail: (a)

All the nodes in the network are deployed randomly, so that the network can be used in any environment. The structure of the network is flexible, and the nodes can be deployed according to practical application, which is not limited by the algorithm.

(b)

The network has only one sink node, and the computing power, communications power, storage capacity, and energy of sink node are not limited. The sink node is the interactive interface of WSN with the outside world, which is the typical characteristic of WSN structure. With only one sink node, information transmission security and energy saving will be guaranteed.

(c)

The sensor nodes in the network are identical. All the nodes are not set ID and they have the same computing power and primary energy. And hence the network structure is more flexible as the nodes can be deployed randomly.

(d)

The sensor nodes in the network are not equipped with positioning device, and the coordinate systems of nodes are not uniform in initial stage. So the hardware costs will be saved, and it will be easy to deploy large-scale nodes. In addition, the flexibility of the network deployment has been improved.

(e)

The information transmission channel is symmetrical; that is, the energy consumption from A to B is the same as that from B to A, which is determined by the characteristics of wireless signal transmission.

(f)

The transmission energy can be controlled by the nodes independently in accordance with the transmission distance. This function is controlled by the system-on-a-chip of sensor node, and now some embedded systems for WSN can realize this function.

(g)

Conflict control and channel assignment are carried out by the MAC protocol, which is not considered by the localization algorithms.

3.2. An Energy Efficient Anchor-Free Localization Algorithm

Since the sink is unlimited in energy and transport capacity, we set it as the origin of the global coordinate system. The active packets are transmitted by the sink in the form of broadcasting. After receiving active packets, the distances and angles between the sensor nodes and the sink will be calculated. Equation (1) is the path loss formula in free space, where $P_{T}$ is the transmitting power, $P_{R}$ is the receiving power, $G_{T}$ denotes the transmitting antenna gain, and $G_{R}$ represents a receiving antenna gain. The distance calculation formula can be deduced by (1) as shown in (2). At the same time the angle from node to sink can be obtained by using the angle measuring device. Next, the coordinate systems of sensor node and sink will be unified with the help of sink. The active packets of the nodes will be created, and these active packets will be transmitted to the surrounding nodes. The power to transmit a single packet is fixed. As long as these nodes receive two active packets, the positions of the two active packets will be used to calculate the distances to sink via Trigonometric formula. The process above is repeated until all the nodes are activated, and then, the nodes save neighbor node lists. A list contains the relative position information from this node to all neighbor nodes. The specific format of the list is shown in Table 1, and the structure of packet is shown in Table 2. The flow chart of the algorithm is shown in Figure 1, which explains the system localization procedure. The message flow diagram is shown in Figure 2, which explains the messages exchange between nodes and between nodes and sink. Consider

\begin{matrix} P_{R} = P_{T} G_{T} G_{R} {(\frac{λ}{4 π d})}^{2}, \end{matrix}

(1)

\begin{matrix} d = λ \sqrt{\frac{P_{T} G_{T} G_{R}}{16 π^{2} P_{R}}} . \end{matrix}

(2)

The algorithm can be described as in Algorithm 1. Consider

\begin{matrix} l_{a b} = \sqrt{l_{a}^{2} + l_{b}^{2} - 2 l_{a} l_{b} \cos (α + β)}, \end{matrix}

(3)

\begin{matrix} γ = \arccos (\frac{(l_{1}^{2} + l_{2}^{2} - l_{3}^{2})}{2 l_{1} l_{2}}), \end{matrix}

(4)

\begin{matrix} l = \frac{\sin α \cdot l_{A B}}{\sin (π - α - β)}, \end{matrix}

(5)

\begin{matrix} l_{a b} = \sqrt{l_{a}^{2} + l_{b}^{2} - 2 l_{a} l_{b} \cos γ} . \end{matrix}

(6)

Table 1

Neighbor node list.

Level	The level of neighbor node

Dis	Distance to the neighbor node

Ang	Angle to the neighbor node

Table 2

The structure of packet.

Pkt-typ	The type of packet (ACT/CON)

Level	The level of packet

Dis	Distance to the sink/distance between two nodes

Ang	Angle to the sink/angle between two nodes

Pow	Transmitting power

Algorithm 1

Sink Node:

Broadcast Active Packet;

When receive a packet → measure its arrive angel A and receive power $P_{R}$ ;

If packet.ACT

reject;

If packet.CON

get $P_{T}$ = packet.Pow;

D = formula_2( $P_{T}$ , $P_{R}$ ); //Use (2)

add (D, A) to neighbor-list;

send a Confirm Packet [CON, 0, D, A, $P_{0}$ ] to (D, A);

Ordinary Node:

Set a flag F = [null, null, null, null];

When receive a packet → measure its arrive angel A and receive power $P_{R}$ ;

If packet.ACT

If my.Level == null

If packet.Level == 0

get $P_{T}$ = packet.Pow;

D = formula_2( $P_{T}$ , $P_{R}$ ); //Use (2)

send a Confirm Packet [CON, 1, D, A, $P_{0}$ ] to (D, A);

Else

If F = null;

F = packet.ACT;

get $P_{T} 1$ = packet.Pow, $A_{1}$ = A, $P_{R} 1$ = $P_{R}$ , $D_{a}$ = packet.Dis, α = packet.Ang;

$L 1$ = packet.Level, θ = $180 - A - α$ ;

rotate coordinate system the degree of θ clockwisely;

Wait for another Active packet;

Else

get $P_{T} 2$ = packet.Pow, $A_{2}$ = A, $P_{R} 2$ = $P_{R}$ , $D_{b}$ = packet.Dis;

get $L 2$ = packet.Level, β = packet.Ang;

The calculation process as shown in Table 3;

add ( $l_{1}$ , $A_{1}$ ) and ( $l_{2}$ , $A_{2}$ ) to neighbor-list;

set my.Dis = $l_{3}$ , my.Ang = $λ_{8}$ , my.Level = min( $L 1$ , $L 2$ ) + 1;

send a Confirm Packet [CON, my.Level, $l_{1}$ , $A_{1}$ , $P_{0}$ ] to ( $l_{1}$ , $A_{1}$ );

send a Confirm Packet [CON, my.Level, $l_{2}$ , $A_{2}$ , $P_{0}$ ] to ( $l_{2}$ , $A_{2}$ );

If my.Level ≠ null

If packet.Level > my.Level

reject;

Else

get $D_{a}$ = packet.Dis, α = packet.Ang, β = packet.Ang; $D_{b}$ = my.Dis;

$D_{a b}$ = formula_3( $D_{a}$ , $D_{b}$ , α, β); //Use (3)

If this ( $D_{a b}$ , A) exists in neighbor-list

do nothing;

Else

add ( $D_{a b}$ , A) to neighbor-list;

send a Confirm Packet [CON, my.Level, $D_{a b}$ , A, $P_{0}$ ] to ( $D_{a b}$ , A);

If packet.CON

If packet.Level == 0

get $D s$ = packet.Dis and $A s$ = packet.Ang;

θ = $180 - A - A s$ ; rotate coordinate system the degree of θ clockwisely;

add ( $D s$ , A) = sink to neighbor-list;

set my.Level = 1; store my.Dis = $D s$ and my.Ang = A;

begin to broadcast Active Packet [ACT, 1, $D s$ , A, $P_{0}$ ];

Else

get D = packet.Dis;

If this (D, A) exists in neighbor-list

do nothing;

Else

add (D, A) to neighbor-list;

Table 3

Calculation process in the algorithm.

Input	Formula	Output
$D_{a}, D_{b}$ , α, β	Equation (3)	$D_{a b}$
$D_{a}, D_{b}, D_{a b}$	Equation (4)	$λ_{1}$
$D_{b}, D_{a}, D_{a b}$	Equation (4)	$λ_{2}$
$A_{1}, α$	$\|A_{1} - α\|$	$λ_{3}$
$A_{2}, β$	$\|A_{2} - β\|$	$λ_{4}$
$λ_{3}, λ_{2}$	$λ_{3} - λ_{2}$	$λ_{5}$
$λ_{4}, λ_{1}$	$λ_{4} - λ_{1}$	$λ_{6}$
$λ_{6}, D_{a b}, λ_{5}$	Equation (5)	$l_{1}$
$λ_{5}, D_{a b}, λ_{6}$	Equation (5)	$l_{2}$
$l_{2}, D_{b}, λ_{4}$	Equation (6)	$l_{3}$
$l_{3}, l_{2}, D_{b}$	Equation (4)	$λ_{7}$
$λ_{7}, A_{2}$	$λ_{7} + A_{2}$	$λ_{8}$

Figure 1

The flow chart of the algorithm.

Figure 2

The message flow diagram.

As shown in Figure 3, active packets are broadcasted by the sink node periodically, and the packet structure is shown in

\begin{matrix} \begin{matrix} ACT & 0 & 0 & 0 & P_{0} \end{matrix} \end{matrix}

(7)

Node A, which receives active packet from sink, firstly measures the arrival angle β and receiving power

P_{R}

of source packet. The distance

l_{A}

from node A to the sink is calculated by (2); then a confirm packet whose structure is shown in

\begin{matrix} \begin{matrix} CON & 1 & l_{A} & β & P_{0} \end{matrix} \end{matrix}

(8)

is sent from A to the sink. After receiving the confirm packet, the sink sends a confirm packet, which is shown in

\begin{matrix} \begin{matrix} CON & 0 & l_{A} & α & P_{0} \end{matrix} \end{matrix}

(9)

to A as well, and the sink puts A in its neighbor list. After receiving the confirm package, node A calculates the angle γ using (10) and the angle in the confirm package. Then, the coordinate system of node A rotates clockwise by γ, so that the coordinate system of node A has been unified with the coordinate system of the sink. Finally, node A sets its level as 1 and puts sink into its neighbor lists. Now A has been activated. The coordinate system directions of the outer layer nodes are unified by the sink, as shown in Figure 4. Consider

\begin{matrix} α + β + γ = 180 ⟹ \\ γ = 180 - α - β . \end{matrix}

(10)

Figure 3

Neighbor discovery of sink node.

Figure 4

Outer layer node unified the direction of coordinate system.

After being activated, the sensor nodes with the same situation as node A begin to send active packets, and the packet structure is shown in

\begin{matrix} \begin{matrix} ACT & 1 & l_{A} & α & P_{0} \end{matrix} \end{matrix}

(11)

Other nodes which receive the active packets can be classified into two categories: the nodes which have been already activated and the nodes which have not been activated.

$(1)$ If node B has been activated after receiving the active packet from A, its relative position to sink node is denoted as ( $l_{B}$ , β). According to the level of active packet from A, node B finds that they are at the same layer, and the angle from A to B, which is denoted by λ, will be measured. The distance from B to A is calculated by (13). Then node B sends back a confirm packet to A, which is shown in

\begin{matrix} \begin{matrix} CON & 1 & l_{B A} & λ & P_{0} \end{matrix} \end{matrix}

(12)

Nodes A and B add each other to their neighbor node lists. Node A stores the location information of B as (

l_{A B}

, λ), and B stores the location information of A as (

l_{B A}

180 - λ

). The whole process is shown in Figure 5. One has

\begin{matrix} l_{A B} = \sqrt{l_{A}^{2} + l_{B}^{2} - 2 l_{A} l_{B} c o s (α + β)} . \end{matrix}

(13)

Figure 5

Neighbor discovery between nodes.

$(2)$ If node C has not been activated after receiving the active packet from A, then C needs to wait for other active packets. C starts the activation steps until more than two active packets from different nodes have arrived. Assume that C receives the active packets from A and B respectively, as shown in

\begin{matrix} \begin{matrix} ACT & X & l_{A} & α & P_{0} \end{matrix} \end{matrix}

(14)

\begin{matrix} \begin{matrix} ACT & Y & l_{B} & β & P_{0} \end{matrix} \end{matrix}

(15)

Then, node C will send confirm packets to node A and node B, and the process is shown in Figure 6.

Figure 6

Angle and distance calculation of outer layer nodes.

In Figure 6(a), node C can calculate the distance between A and B according to (13), since the active packets from A and B contain angles and distances of A and B to the sink, respectively. O is the direction of x-axis; then $∠ A C O$ and $∠ B C O$ can be measured by C according to the directions of the packets. And $∠ A B S$ and $∠ B A S$ can also be calculated by C using $l_{A}$ , $l_{B}$ , and $l_{A B}$ based on Trigonometric formula, which is shown as (16). With these information, node C calculates $∠ S A C$ and $∠ S B C$ according to (17) and calculates $∠ A B C$ and the $∠ C A B$ using (18). Furthermore, $l_{A C}$ and $l_{B C}$ are calculated by C based on the Trigonometric formula, as shown in (19) and (20):

\begin{matrix} ∠ A B S = \arccos (\frac{(l_{A}^{2} + l_{B C}^{2} - l_{B}^{2})}{2 l_{A} l_{B C}}), \\ ∠ B A S = \arccos (\frac{(l_{B}^{2} + l_{B C}^{2} - l_{A}^{2})}{2 l_{B} l_{B C}}), \end{matrix}

(16)

\begin{matrix} ∠ S A C = 180 - (180 - ∠ A C O) - α = |∠ A C O - α|, \\ ∠ S B C = 180 - (180 - ∠ B C O) - β = |∠ B C O - β|, \end{matrix}

(17)

\begin{matrix} ∠ B A C = ∠ S A C - ∠ B A S, \\ ∠ A B C = ∠ S B C - ∠ A B S, \end{matrix}

(18)

\begin{matrix} l_{A C} = \frac{\sin (A B C) \cdot l_{A B}}{\sin (π - A B C - B A C)}, \end{matrix}

(19)

\begin{matrix} l_{B C} = \frac{\sin (B A C) \cdot l_{A B}}{\sin (π - A B C - B A C)} . \end{matrix}

(20)

After calculating $∠ S A C$ , $∠ S B C$ , $l_{A C}$ , and $l_{B C}$ , $l_{S C}$ will be calculated as (22), and the process is shown in Figure 6(b). Node C can calculate $∠ S C B$ using (23), and then $∠ S C O$ , $l_{S C}$ , and $∠ S C O$ are calculated by (24), which is the relative location from C to the sink. C stores nodes A and B to their neighbor node lists, and the content is shown in

\begin{matrix} \begin{matrix} X & l_{A C} & ∠ A C O \end{matrix} \\ \begin{matrix} Y & l_{B C} & ∠ B C O \end{matrix} \end{matrix}

(21)

On the other hand, nodes A and B store information of C to their neighbor node lists as well. Now the activation of node C has been completed. All nodes whose level is greater than 1 use this step to activate. Consider

\begin{matrix} l_{S C} = \sqrt{l_{B}^{2} + l_{B C}^{2} - 2 l_{B} l_{B C} \cos (S B C)}, \end{matrix}

(22)

\begin{matrix} ∠ S C B = \arccos (\frac{(l_{S C}^{2} + l_{B C}^{2} - l_{B}^{2})}{2 l_{S C} l_{B C}}), \end{matrix}

(23)

\begin{matrix} ∠ S C O = ∠ S C B + ∠ B C O . \end{matrix}

(24)

4. Theoretical Analysis of the Algorithm

In order to be localized uniquely based on the known information, what attributes of vertex and edge should the nodes in WSN satisfy? This is the key issue of localization research in WSN. Existing researches use methods including rigidity and global rigidity in frameworks [31, 32], geometric constraint [19], combinatorial rigidity in frameworks [33], and coordination of formations of autonomous agents [34] to prove the unique localization problem. Based on the research of [35], considering the characteristics of transmission and structure in WSN, we analyze the unique localization of the proposed network structure on the basic of global rigid framework.

Theorem 1 (see [36]).

Let N be a WSN in $R^{D}$ consisting of m ordinary sensor nodes $V_{s} = \{1,2, \dots, m\}$ located at positions $p_{1}, p_{2}, \dots, p_{m}$ and $n - m$ anchor nodes $V_{a} = \{m + 1, m + 2, \dots, n\}$ located at $p_{m + 1}, \dots, p_{n}$ . Suppose that there are at least $D + 1$ anchors positioned at points in general position. Let $F_{p}$ denote the corresponding framework of N and let $p = (p_{1}, p_{2}, \dots, p_{n})$ . Then the WSN localization problem is solvable (i.e., has a unique solution) if and only if $F_{p}$ is globally rigid.

Hence, the WSNs unique localization problem is switched into verifying the global rigidity of corresponding framework and analyzing the localizability.

First, we provide a mathematical description to WSNs localization problem. Let sensor nodes be distributed in D ( $D \geq 1$ , usually $D = 2$ ) dimensional space; then these WSNs can be represented by an undirected connected graph $G = (V, E)$ . The elements of E are positive weights $d_{i j}$ , which are the distances between adjacent nodes.

The network structure of the algorithm's output is shown in Figure 7. The forms store the neighbor's information of each node.

Figure 7

Part of an output of the algorithm.

Definition 2 (framework [17, 37]).

Let $G = (V, E)$ be an undirected graph and V and E are vertex set and edge set, respectively. In $R^{D}$ space, each point has a position $p_{i} \in R^{D}$ . The length of edge $i j \in E$ between the points $p_{i}$ and $p_{j}$ is decided by the Euclidean distance. Then a framework $F_{p}$ is a pair $(G, p)$ , where p is a map from V to $R^{D}$ satisfying $‖p_{i} - p_{j}‖ = d_{i j}$ , and for all $i j \in E$ , $p_{i} \neq p_{j}$ .

According to Definition 2, each graph can be mapped into a framework, in which the set of edges is represented by $B \cup L$ . Length edge L is the edge satisfying distance constraint, which means that the distance of the edge between two nodes is known by both sides. Bearing edge B is the edge satisfying angle constraint, which means that the angles of the edge between two nodes are known by both sides. The intersection set between B and L is called mixed edge which satisfies both the distance constraint and angle constraint, that is, combined constraints. Apparently, the more mixed edges exist, the higher the probability of rigid network structure is, even global rigid.

The rigidity of the framework will be enhanced under combined constraints. If all of the edges in the framework satisfy combined constraints, we call the framework full combined constraints.

In our algorithm, the combined constraint edge can be regarded as communication channel between the nodes. The communication data contains distance and angle information; that is, the distance and angle between two nodes are known by both sides via measurement and calculation, as shown in Figure 7. And hence, all of the edges in the framework can be seen both as the length edge and the bearing edge; that is, $B = L$ . Thus the node distribution in our algorithm satisfies the strictest combined constraints, that is, full combined constraints. In [38], network structures in 2D are all global rigid under the condition of full combined constraints. Obviously, the WSN nodes satisfy global rigid conditions under the constraint of the proposed algorithm, and the uniqueness and accuracy of localization process can be guaranteed. The WSN structure of the proposed algorithm which satisfies the combined constraint framework is shown in Figure 8.

Figure 8

WSNs structure of this algorithm which satisfies the combined constraint framework.

5. Simulation

An energy efficient anchor-free localization algorithm for no ID WSN model is proposed in this paper. In this section, a series of experiments are designed to verify the performance of the proposed algorithm. Furthermore, the positioning accuracy, localization rate, and energy efficiency of our algorithm have been analyzed thoroughly.

5.1. Performance Evaluation Criteria

The accuracy of positioning is described as follows: the wireless channel of WSN has the characteristics of being complex and changeful. There usually exist path loss, multichannel interference, shadow effect, and so on, which may result in distortion. Generally, the radio propagation model is not ideal, which produces measurement error inevitably, and this results in further positioning error between the calculated value and the actual node location. In addition, it is inevitable that distributed computing results in cumulative effect in multihops network. With multiple use of the calculation, the scope of the position error will be enlarged. In our experiments, the error follows normal distribution $N (0.1,1)$ , and the error can be calculated using (25), where $μ = 0.1$ and $σ = 1$ :

\begin{matrix} f (x) = \frac{1}{\sqrt{2 π} σ} \exp (- \frac{{(x - μ)}^{2}}{2 σ^{2}}) . \end{matrix}

(25)

Localization Rate. In this paper, the concept of coverage rate of positioned node is used to judge the rate, and its computation formula is shown in (26), where sum_A is the number of positioned nodes and sum is the total number of all nodes:

\begin{matrix} F = \frac{{sum}_{A}}{sum} . \end{matrix}

(26)

Energy Efficiency. Energy efficiency of the algorithm means that, after positioning energy consumption of the nodes in network as low as possible, energy consumption is uniformly distributed, and obvious excessive energy consumption of the node does not exist. Since the positioning calculation requires a lot of communication between nodes, which consumes huge node energy, hence, how to reduce energy consumption mentioned above and allocate more energy for routing and information transmission is the key issue to improve the network performance. One of the standards to measure the energy efficiency of the algorithm is the average residual energy of the nodes in the entire network, as shown in (27). And it reflects the overall energy saving effect of the algorithm. Another standard is the energy difference between the maximum node and the minimum node, as shown in (28), which reflects the balance of node energy consumption in the algorithm. Consider

\begin{matrix} \bar{E} = \frac{\sum_{i}^{n} E^{'}}{n}, \end{matrix}

(27)

\begin{matrix} Δ E = E_{m a x} - E_{m i n} . \end{matrix}

(28)

5.2. Results

The proposed algorithm is simulated in MATLAB. Hardware and environment parameter settings involved in the experiments are shown in Table 4. The simulated network environment generated in our experiments is shown in Figure 9, and the neighbor link and range of each node are shown in Figure 10.

Table 4

The main parameters of the experiment.

Threshold distance ( $d_{0}$ ) (m)	15

$E_{Elec}$ (nJ/bit)	50

$ε_{f s}$ (pJ/bit/m²)	10

$ε_{m p}$ (pJ/bit/m⁴)	0.0013

Sensing area (m²)	100 ∗ 100

Figure 9

The experiment generated network simulation environment.

Figure 10

Neighbor link and range of each node.

Transmission threshold, sending, and receiving information parameters (i.e., $E_{E l e c}$ , $ε_{f s}$ , and $ε_{m p}$ ) are related to specific hardware. Common parameter values are adopted in our experiments, and the sensing area is set as a square with maximum area of 10⁴ m². Additionally, the nodes are deployed randomly in the sensing area, and hence, the sensing area can be any irregular shape.

100 nodes are deployed in the sensing area, and let each node be the sink node; the relationship of localization rate and distance from the center of the area to sink node is shown in Figure 11.

Figure 11

The relations of distance from the center of the region to each sink node and the localization rate.

In the deployed 100 nodes, the one with the highest localization rate is chosen as the sink node. The relationship between measure error and average error is shown in Figure 12.

Figure 12

The relations of the measurement error and average error.

In order to verify the energy efficiency, SPA [16], SDGPSN [19], and AAFL [20] are chosen to compare with the proposed algorithm. SPA is a classic anchor-based localization algorithm. SDGPSN adds clustering scheme on the basic of SPA and has similar structure with the proposed algorithm. AAFL is an anchor-free localization algorithm which is similar as the proposed algorithm, and it has good flexibility.

We deploy 250 nodes in the network. With the increasing of the nodes coverage rate, the change of the node average residual energy of all these four algorithms is shown in Figure 13. Figure 14 shows the node residual energy changing of these four algorithms with the increase of the node coverage rate. Obviously, the balance of SDGPSN's node energy consumption is the worst, followed by SPA and AAFL. The node energy consumption of the proposed algorithm is very balanced, and the difference of node's residual energy is no more than 30% even the coverage rate reaches 99%.

Figure 13

The relations of average residual energy and the coverage rate of nodes.

Figure 14

The relations of residual enenrgy and the coverage rate of nodes.

5.3. Experimental Analysis

In the positioning accuracy and localization rate aspects, the proposed algorithm is based on the research of global rigid framework system, which has the unique localization theoretical basis. Except the one-hop neighbor node of the sink, the location information of the rest of the nodes is all obtained by strict mathematical calculation, so that the measurement error of transmission expansion is avoided. Experiments show that the location of the sink node affects the localization rate to a certain extent. This is because the localization starts from the sink node and the positioning information is transmitted from the sink layer by layer. The localization rate will be higher if the sink node comes closer to the center of the sensing area.

In the energy efficiency aspect, it can be seen, no matter how much the coverage rate of positioned node is, the proposed algorithm has the most average residual energy of nodes. Additionally, with the increase of the coverage rate, this advantage is more and more obvious, which means good energy efficiency. Compared with the existing algorithms, instead of omnidirectional broadcast mode, the proposed algorithm adopts the method of sensor node searching for neighbor node based on directed diffusion function. And all data packets are sent by small fixed energy, rather than large energy, which narrows the search range and reduces the neighbor number of each node, and hence, energy will be saved. Furthermore, distributed discovery strategy is adopted in the proposed algorithm. Instead of directly communicating with sink node, the sensor nodes transmit the positioning information layer by layer from inside to outside. The information communication and positioning burden are similar for all nodes, which ensures the balance of the entire network node energy consumption.

5.4. Error Analysis

In the proposed algorithm, we assume that each node can measure the angle to other nodes and the power of radio waves; accordingly, accurate localization can be realized theoretically. In the simulation, we only consider the error caused by channel distortion, such as path loss, multichannel interference, and shadow effect.

In practice applications, a set of directional antennas is usually used for measuring the direction of radio wave, but the accuracy of the measured angles cannot be guaranteed.

In the proposed algorithm, however, only the first layer nodes (i.e., the one-hop nodes of sink node) are activated by the measured angle; the outer layer nodes obtain angles mainly by calculation. As a result, the error of a layer will not affect the next layer, so that the error will not accumulate layer by layer, and the accuracy of our algorithm mainly depends on hardware measurement.

6. Conclusions

In this paper, we propose an efficient anchor-free localization algorithm for wireless sensor networks (WSNs) without ID information. Making use of the positioning information transmitted by the sink node, the proposed algorithm can localize the nodes accurately without depending on the anchor node. We propose a network model that does not contain ID information, which makes the algorithm more flexible in application. The unique localization has been proved by the combined constraints based on global rigid framework. In the process of localization, the algorithm reduces radio transmission with high energy consumption. Localization of the node can be calculated mainly by mathematical calculation, and hence, the error accumulation has been reduced. Finally, the localization efficiency and accuracy have been verified by reasonable experimental design, and the algorithm has been proved with high energy efficiency on the premise of accurate positioning. In practical applications, three-dimensional localization method and theory are more close to the actual WSNs sensor node deployment. Therefore, our future research will focus on WSNs localization in three-dimensional space.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Estrin

Govindan

Heidemann

Kumar

Next century challenges: scalable coordination in sensor networks

Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ′99)

August 1999

Seattle, Wash, USA

ACM

263 270

10.1145/313451.313556

Watteyne

Molinaro

Richichi

M. G.

Dohler

From MANET to IETF ROLL standardization: a paradigm shift in WSN routing protocols

IEEE Communications Surveys and Tutorials 2011 13 4 688 707

10.1109/surv.2011.082710.00092

2-s2.0-84893270272

Anastasi

Conti

Di Francesco

Passarella

Energy conservation in wireless sensor networks: a survey

Ad Hoc Networks 2009 7 3 537 568

10.1016/j.adhoc.2008.06.003

2-s2.0-56449087483

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

10.1016/s1389-1286(01)00302-4

2-s2.0-0037086890

Wade

Mitehel

W. M.

Petter

Ten emerging technologies that will change the world

Technology Review 2003 106 1 22 49

Alemdar

Ersoy

Wireless sensor networks for healthcare: a survey

Computer Networks 2010 54 15 2688 2710

10.1016/j.comnet.2010.05.003

2-s2.0-77956882701

Oliveira

L. M. L.

Rodrigues

J. J. P. C.

Wireless sensor networks: a survey on environmental monitoring

Journal of Communications 2011 6 2 143 151

10.4304/jcm.6.2.143-151

2-s2.0-79955503480

Yick

Mukherjee

Ghosal

Wireless sensor network survey

Computer Networks 2008 52 12 2292 2330

2-s2.0-46449122114

10.1016/j.comnet.2008.04.002

Pal

Localization algorithms in wireless sensor networks: current approaches and future challenges

Network Protocols and Algorithms 2010 2 1 45 73

10.5296/npa.v2i1.279

10.

Haenggi

Opportunities and challenges in wireless sensor networks

Handbook of Sensor Networks: Compact Wireless and Wired Sensing Systems 2005

CRC Press

11.

Misra

Reisslein

Xue

A survey of multimedia streaming in wireless sensor networks

IEEE Communications Surveys and Tutorials 2008 10 4 18 39

10.1109/surv.2008.080404

2-s2.0-55849125003

12.

Wang

Sohraby

Daneshmand

A survey of transport protocols for wireless sensor networks

IEEE Network 2006 20 3 34 40

10.1109/mnet.2006.1637930

2-s2.0-33745067813

13.

Rossi

Zorzi

Rao

R. R.

Cost efficient routing strategies over virtual coordinates for wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM ′05)

December 2005

St. Louis, Mo, USA

IEEE

2975 2980

10.1109/glocom.2005.1578303

2-s2.0-33846584016

14.

Hamilton

B. R.

Baxley

R. J.

Efficient node self-localization in large ad-hoc wireless networks using interlaced particle filters

Proceedings of the IEEE Military Communications Conference (MILCOM ′11)

November 2011

Baltimore, Md, USA

780 785

10.1109/milcom.2011.6127771

2-s2.0-84856966010

15.

Mao

Fidan

Anderson

B. D. O.

Wireless sensor network localization techniques

Computer Networks 2007 51 10 2529 2553

10.1016/j.comnet.2006.11.018

ZBL1120.68021

2-s2.0-34247885928

16.

Johns

M. S.

Radio frequency (RF) interface management information base for MCNS/DOCSIS compliant RF interfaces

RFC2G70, 1999

17.

Eren

Belhumeur

P. N.

Anderson

B. D. O.

Morse

A. S.

A framework for maintaining formations based on rigidity

Proceedings of the 15th Triennial World Congress of the International Federation of Automatic Control (IFAC ′02)

July 2002

Barcelona, Spain

2752 2757

18.

Čapkun

Hamdi

Hubaux

J.-P.

GPS-free positioning in mobile ad hoc networks

Cluster Computing 2002 5 2 157 167

10.1023/a:1013933626682

19.

Iyengar

Sikdar

Scalable and distributed GPS free positioning for sensor networks

Proceedings of the 38th Annual IEEE International Conference on Communications (ICC ′03)

May 2003

Anchorage, Alaska, USA

IEEE

338 342

2-s2.0-0037715150

20.

Youssef

Agrawala

Younis

Accurate anchor-free node localization in wireless sensor networks

Proceedings of the 24th IEEE International Performance, Computing, and Communications Conference (IPCCC ′05)

April 2005

Phoenix, Ariz, USA

IEEE

465 470

10.1109/PCCC.2005.1460614

2-s2.0-28444441966

21.

Wicker

S. B.

Co-designed anchor-free localization and location-based routing algorithm for rapidly-deployed wireless sensor networks

Information Fusion 2008 9 3 425 439

10.1016/j.inffus.2007.09.002

2-s2.0-43549122840

22.

Jordt

G. J.

Baldwin

R. O.

Raquet

J. F.

Mullins

B. E.

Energy cost and error performance of range-aware, anchor-free localization algorithms

Ad Hoc Networks 2008 6 4 539 559

2-s2.0-39349116055

10.1016/j.adhoc.2007.04.004

23.

LOCOMOTE: a simple anchor-free localization scheme for wireless sensor networks

Proceedings of the Military Communications Conference (MILCOM ′07)

October 2007

Orlando, Fla, USA

IEEE

1 7

10.1109/milcom.2007.4454849

2-s2.0-47949096511

24.

Jiang

Xiao

Liu

Localization scheme for wireless sensor networks based on ‘shortcut’ constraint

Ad Hoc and Sensor Wireless Networks 2015 26 1–4 1 19

25.

Ren

A RSSI localization algorithm and implementation for indoor wireless sensor networks

Ad-Hoc and Sensor Wireless Networks 2014 22 3-4 309 337

2-s2.0-84907085752

26.

Garcia

Tomas

Boronat

Lloret

The development of two systems for indoor wireless sensors self-location

Ad-Hoc and Sensor Wireless Networks 2009 8 3-4 235 258

2-s2.0-77951445148

27.

Lloret

Tomas

Garcia

Canovas

A hybrid stochastic approach for self-location of wireless sensors in indoor environments

Sensors 2009 9 5 3695 3712

2-s2.0-70849089573

10.3390/s90503695

28.

Garcia

Martinez

Tomas

Lloret

Wireless sensors self-location in an indoor WLAN environment

Proceedings of the International Conference on Sensor Technologies and Applications (SensorComm ′07)

October 2007

Valencia, Spain

IEEE

146 151

10.1109/SENSORCOMM.2007.4394912

29.

Wen

Yao

Cui

Zhang

Mobile anchor assisted distributed localization for wireless sensor networks with holes

Proceedings of the 14th International Conference on Control, Automation and Systems (ICCAS ′14)

October 2014

Seoul, Republic of Korea

1554 1559

10.1109/iccas.2014.6987814

2-s2.0-84920141010

30.

Cui

Zhou

Meng

Hua

Mobile anchor assisted localization in wireless sensor networks with regular polygon path

Proceedings of the 4th IEEE International Conference on Software Engineering and Service Science (ICSESS ′13)

May 2013

Beijing, China

389 392

10.1109/icsess.2013.6615331

2-s2.0-84890080370

31.

Jackson

Jordán

Operations preserving global rigidity of generic direction-length frameworks

International Journal of Computational Geometry & Applications 2010 20 6 685 706

10.1142/s0218195910003487

MR2747431

ZBL1226.05241

2-s2.0-78650881491

32.

Connelly

Generic global rigidity

Discrete & Computational Geometry 2005 33 4 549 563

10.1007/s00454-004-1124-4

MR2132290

ZBL1072.52016

2-s2.0-17444406687

33.

Servatius

Whiteley

Constraining plane configurations in computer-aided design: combinatorics of directions and lengths

SIAM Journal on Discrete Mathematics 1999 12 1 136 153

10.1137/s0895480196307342

MR1666077

ZBL0916.68182

2-s2.0-0038457531

34.

Kuhn

Wattenhofer

Zollinger

Asymptotically optimal geometric mobile ad-hoc routing

Proceedings of the 6th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DialM ′02)

September 2002

Atlanta, Ga, USA

24 33

35.

Kułakowski

Vales-Alonso

Egea-López

Ludwin

García-Haro

Angle-of-arrival localization based on antenna arrays for wireless sensor networks

Computers and Electrical Engineering 2010 36 6 1181 1186

2-s2.0-77958112113

10.1016/j.compeleceng.2010.03.007

ZBL1202.94152

36.

Aspnes

Eren

Goldenberg

D. K.

Morse

A. S.

Whiteley

Yang

Anderson

B. D. O.

Belhumeur

P. N.

A theory of network localization

IEEE Transactions on Mobile Computing 2006 5 12 1663 1677

2-s2.0-33750831866

10.1109/TMC.2006.174

37.

Roth

Rigid and flexible frameworks

The American Mathematical Monthly 1981 88 1 6 21

10.2307/2320705

MR619413

ZBL0455.51012

38.

Zhang

Localization using joint distance and bearing information for wireless sensor networks [Ph.D. dissertation] 2012

Shandong University