Real-Time Localization Algorithm for Maritime Search and Rescue Wireless Sensor Network

Abstract

Maritime search and rescue (MSR), as the last defense line for the life at sea, plays a great role in shipping industry and ocean environment protection. MSR is attracting more and more attention from technical and scientific aspects which are expected to help locate the victim goals quickly, precisely, and efficiently. So far, there have been some new techniques applied to MSR, such as computer vision. However, these techniques have a common drawback that they are too dependent on the effort of the search and rescue party, so that the victim goals can only passively wait for their search. To change this kind of passive status, wireless sensor network (WSN) is the deficiencies of the current maritime search and rescue. To make WSN localization suitable for the MSR, an improved microelectromechanical systems MEMS aided algorithm on the basis of triangle and centroid algorithm is proposed to locate and track the search targets in real time and more precisely. Finally, the simulation results show that the proposed method and algorithm are feasible and efficient.

1. Introduction

With the continuous development of the entire world shipping industry and the increasing number of ships at sea, it becomes a bigger challenge for the ships to be kept safe at sea, so the accidents often happen. When the accidents happen, the first thing is to search and rescue the floating staff to protect their lives and properties. The traditional measure is mainly using a plenty of search and rescue ships and helicopters to look for the floating staff, but the result is not ideal enough and it wastes a lot of resources [1]. Although many techniques like radar and computer vision have been applied to maritime search and rescue, it still cannot change the situation that the victim goals can only passively wait for the searching of the search and rescue party. Search and rescue consists of two parts: searching and rescuing, and searching and determining the position of the floating staff is the key to success. Wireless sensor networks WSNs are a kind of networks consisting of a large number of sensor nodes that have low cost and low power and having computing power and wireless communication capacity [2]. WSNs have the features of survival ability, accuracy and reliability, self-organization ability, scalability, and so on in harsh and dynamic environment. So the use of WSN localization can adapt to the complex environment well at sea.

For the environment at sea and the target of low cost and low power, this paper merges the advantages of range based localization and nonrange localization. We take RSSI measures to achieve the distances and propose an improved triangle and centroid algorithm, and when we get the original positions of floating staff, we can use MEMS technique to optimize the position information. Then we can get more accurate position information without cost and energy consumption and duplication iterations, and the algorithm computing process has a low complexity.

The remainder of the paper is organized as follows. In Section 2, we present the related work. In Section 3, we present an improved MEMS aided localization algorithm based on the triangle and centroid algorithm. In Section 4, we evaluate the proposed method in this paper with simulation experiments. At last Section 5 concludes the paper.

2. Related Work

Huanhuan et al. [3] introduced the researches of WSN localization in and abroad. This paper analyzed the principles and methods of mobile WSN localization and 3D localization, and it can reduce the costs of beacon nodes based on mobile WSNs. But Huanhuan did not analyze the application scenarios that the algorithms suited for. Bearing in the mind the advantages and disadvantages of range-based localization and nonrange localization, Zhao and Chen [4] proposed that it can measure the point-to-point distance by correcting RSSI ranging and choosing the preferred beacon nodes, and at last used the weighed centroid algorithm to get the position. But the weighted thinking was not related to the work status of the device itself in the harsh environment. Yun et al. [5] presented a localization algorithm using expected hop progress based on non-range localization because the accuracy of distance measurement is one of the key points in localization. Thus it can calculate the distance between any two sensor nodes and expand the range and accuracy of the localization. He et al. [6] presented APIT, a novel localization algorithm that was range-free and showed that their APIT scheme performed best when an irregular radio pattern and random node placement were considered, and low communication overhead was desired. In addition, they studied the effect of location error on routing and tracking performance. Awad et al. [7] proposed several discuss-and-analyze methods using RSSI to reduce the cost as RSSI did not need additional hardware. Also they made a comparison between two distance estimations, statistical method and artificial neural network method. But the localization accuracy of the algorithm was limited. Though the cost was low, it was not appropriate to be used in maritime search and rescue that required high localization accuracy. Li et al. [8] proposed a range-based particle filtering localization method for static WSN. Firstly, the state-space function of localization in a static WSN was proposed in the paper. Secondly, important steps in a particle filter were specifically illustrated in the paper, including initialization, prediction, sequential importance sampling, and the resampling.

Cheng and Du [9] took into account that the unbelievable GPS observations may cause positioning errors, so they gave the observations different weights using weighted least square method. The observations which are nearer can get a larger weight, and it helps to achieve more accurate position information. But Cheng and Du did not elaborate the development of WSN localization. Caballero et al. [10] proposed a new idea that combined WSNs positioning technology with robots, called network robot system (NBS). It can be divided into two parts. First, they used robots to get the original estimations of localization and then refined these estimations of localization with distributed information filtering method. But the method was established in the condition that the robot moved in accordance with the predesigned route and did not consider the random movement with wind and waves at sea. Lei and Lili [11] proposed WSNs self-positioning method based on genetic algorithm. At first they had a preliminary estimation of original position information using sampling method and then used genetic algorithm to compute for more accurate results. This algorithm can locate precisely even the anchor nodes which only account for a small proportion. But Lei and Lili did not take optimization measures in obtaining the original position of the unknown nodes. Dong et al. [12] gave a new localization algorithm based on mobile beacon nodes. The algorithm used a beacon node to traverse the entire network, and the node periodically broadcast a packet that contains the location information. At last they located using maximum likelihood estimation method instead of the trilateral localization algorithm to improve the positioning stability of the algorithm. Shang and Ruml [13] proposed a new variant of the MDS-MAP (multidimensional scaling map) method using patches of relative maps, that can be executed in a distributed fashion. The main idea was to build a local map at each node of the immediate vicinity and then merges these maps together to form a global map. Jun et al. [14] presented Non-intEractive lOcation Surveying (NEOS) to address certain deficiencies in the existing approaches. The key contribution was twofold: (i) it employed a mobile beacon to introduce mobility-differentiated time-of-arrival (MDToA) observations, a special form of time difference of arrival (TDoA), at the node side, and (ii) it involved simple computation and entailed no node-to-node communication. Tang et al. [15] studied a node localization algorithm based on moving beacon node based on the classical DV hop algorithm because of the limit energy of the node.

The previous researches have a close relationship with WSN localization algorithm at sea. Because of the unique application environment at sea, it is necessary to find a localization algorithm that is easily operated and simply calculated and has low cost and low power.

3. An Improved MEMS Aided Localization Algorithm Based on the Triangle and Centroid Algorithm

3.1. Application Scenarios at Sea for WSN Localization

As one of the supporting technologies of WSN, localization can be applied to locate the floating staff. Installing the wireless sensor nodes in the ships in distress, the survival craft, lifejackets, and other survival equipments, these nodes are artificially opened or automatically start in the case of seawater when the shipwreck occurs and self-organize into a wireless sensor network through ZigBee protocol. The nodes carried on the searching targets are defined as the unknown nodes, and the ships in distress, survival craft, rescue helicopters, and tossed sensor nodes are defined as the anchor nodes, and these anchor nodes can know their positions from GPS or other devices. The unknown node can locate itself with the actual positions of anchor nodes and send its position to the rescue organization or personnel or share with the relevant departments or personnel by connecting to the internet through the satellites. We would change the situation that the maritime search and rescue targets can only passively wait for their search, thus make the position indication of the searched targets initiative.

3.2. Improved Triangle and Centroid Localization Algorithm Using RSSI

RSSI is a value that indicates the quantity of the electromagnetic energy in the current media. When the wireless signal spreads in the air, the signal strength will decease with the distance increasing because of various factors from the outdoor environment. Changes in signal strength have a sort of functional model with the spreading distance, and usually the module measuring the signal strength can be easily installed in the sensor nodes. The transmission power is known, and we measure the received power in the receiving part, so we can calculate the propagation loss and use theory or experience signal propagation model to make propagation loss into distance. RSSI mainly uses RF signal, and it is a ranging way of low power and low cost. Since the error is generated from the reflection, multipath propagation, NLOS (nonline of sight), and other factors, RSSI ranging usually uses the propagation path-loss model as the following shows [16]:

$$\begin{array}{cc}& \text{PL}\left(d\right)=\text{PL}\left(d_0\right)+\mathrm{10}n\hspace{0.17em}\text{lg}\left(\frac{d}{d_0}\right)+X_{\sigma }.\end{array}$$

(1)

In the formula, $d_{\mathrm{0}}=\mathrm{1}\hspace{0.17em}\text{m}$ is the reference distance; $\text{PL}(d_{\mathrm{0}})$ is the loss after the distance $d_{\mathrm{0}}$ ; d is the actual distance; $\text{PL}(d)$ is the loss from anchor nodes to unknown nodes; $X_{\sigma }$ is the shadowing factor whose average value is 0; n is the path-loss exponent and depends on the environment around. Change formula (1) into another form:

$$\begin{array}{cc}& d={\mathrm{10}}^{\left(\text{PL}\left(d\right)-\text{PL}\left(d_{\mathrm{0}}\right)-X_{\sigma }\right)/\mathrm{10}n}\times d_{\mathrm{0}}.\end{array}$$

(2)

In fact, in the real application environment of maritime search and rescue, it will produce ranging errors whatever kind of path-loss models you choose, and the distance calculated from anchor nodes to unknown nodes is always longer than their actual distance. As Figure 1 shows, A, B, and C are anchor nodes and D is an unknown node. So we can calculate the distance $d_{\text{A}}$ from A to D, the distance $d_{\text{B}}$ from B to D, and the distance $d_{\text{C}}$ from C to D according to the principle of RSSI ranging. Then we make circles that use A, B, C as the center and ${\mathrm{\hspace{0.17em}\hspace{0.17em}}d}_{\text{A}},\hspace{0.17em}\hspace{0.17em}{d}_{\text{B}},\hspace{0.17em}\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{d}_{\text{C}}$ as the radius and we will get the cross-area, in the figure. The basic idea of the triangle and centroid algorithm is calculating the three coordinates of the triangle in the cross-area, and the position of the unknown node is the centroid of the triangle. As Figure 2 shows, E, F, and G are vertex of the triangle, and the calculation method of E coordinate $(x_{\text{e}},y_{\text{e}})$ is as the following shows [17]:

$$\begin{array}{l}\sqrt{{\left(x_e-x_a\right)}^{\mathrm{2}}+{\left(y_e-y_a\right)}^{\mathrm{2}}}\le d_{\text{A}},\\ \sqrt{{\left(x_e-x_b\right)}^{\mathrm{2}}+{\left(y_e-y_b\right)}^{\mathrm{2}}}=d_{\text{B}},\\ \sqrt{{\left(x_e-x_c\right)}^{\mathrm{2}}+{\left(y_e-y_c\right)}^{\mathrm{2}}}=d_{\text{C}}.\end{array}$$

(3)

Similarly we can have the coordinates of F $(x_f,y_f)$ and G $(x_g,y_g)$ , so we obtain the coordinate $\text{D}((x_e+x_f+x_g)/\mathrm{3},(y_e+y_f+y_g)/\mathrm{3})$ according to the formula of triangle centroid. It is worth noting that the number of anchor nodes around the unknown node and making intersection is not exactly three. When the number of anchor nodes is less than three, it will not locate. When the number of anchor nodes is three, it locates according to the method mentioned previosly. When the number of anchor nodes is more than three, we should choose three anchor nodes nearest to the unknown node, as the closer the distance, the smaller the error.

Figure 1

Cross area of three circles.

Figure 2

The schematic of triangle and centroid algorithm.

In order to get more accurate localization information, we plan to introduce the weighted thinking into the aforementioned algorithm, in other words, we give every coordinate of the triangle a weight. The anchors in this paper are mainly divided into four categories: the ships in distress, survival craft, rescue helicopters, and tossed sensor nodes. We decide to give them each different weights to distinguish their relative weighted relationship according to the status stability in the complex and bad environment at sea. The ship in distress is the mother ship close to the searching targets and its work status is stable, so we give the ships in distress the weight $r_{\mathrm{1}}$ . The survival craft is mainly well furnished and has good work status, so the weight of the survival craft is $r_{\mathrm{2}}$ . Because of the good maneuvering performance of the rescue helicopter, we give the rescue helicopter the weight $r_{\mathrm{3}}$ . The tossed sensor node will move with the wind and waves, so its work status is not stable enough and the weight of the tossed sensor node is $r_{\mathrm{4}}$ . The specific weight value which depends on the environment at sea is unique at that time. And $r_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{r}_{\mathrm{2}},\hspace{0.17em}\hspace{0.17em}{r}_{\mathrm{3}},\hspace{0.17em}\text{and}\hspace{0.17em}\hspace{0.17em}{r}_{\mathrm{4}}$ satisfy the following conditions:

$$\begin{array}{l}{r}_{\mathrm{4}}<r_{\mathrm{3}}<r_{\mathrm{2}}<r_{\mathrm{1}},\\ r_{\mathrm{1}}+r_{\mathrm{2}}+r_{\mathrm{3}}+r_{\mathrm{4}}=1.\end{array}$$

(4)

Imagine A is the ships in distress, B is the survival craft, and C is the rescue helicopters. For example, E is decided by the circles B and C, so its weight is $(r_{\mathrm{2}}+r_3)$ . Of course, if A, B, and C are other kinds of anchor nodes, it is also applicable. At last we can get the coordinate of D according to the following principle:

$$\begin{array}{cc}& x_d=\frac{x_e\left(r_{\mathrm{2}}+r_{\mathrm{3}}\right)+x_f\left(r_1+r_{\mathrm{3}}\right)+x_g\left(r_{\mathrm{1}}+r_{\mathrm{2}}\right)}{6\left(r_{\mathrm{1}}+r_{\mathrm{2}}+r_{\mathrm{3}}\right)},\\ y_d=\frac{y_e\left(r_{\mathrm{2}}+r_{\mathrm{3}}\right)+y_f\left(r_{\mathrm{1}}+r_{\mathrm{3}}\right)+y_g\left(r_{\mathrm{1}}+r_{\mathrm{2}}\right)}{6\left(r_{\mathrm{1}}+r_{\mathrm{2}}+r_{\mathrm{3}}\right)}.\end{array}$$

(5)

After obtaining the original position information of the unknown node, it cannot avoid producing some degree of mobility taking into account the role of wind and waves. So in order to make the localization more accurate, we introduce a microelectromechanical systems (MEMS) aided method to optimize the original position of the unknown node. MEMS is a kind of microdevice or system that is available for bulk manufacture and contains miniature institutions, microsensors, microactuators and signal processing and control circuit. MEMS combines electronic technology with mechanical characteristics organically, and it can simultaneously achieve the function of physics, chemistry, biology, and so on. One of the characteristics of MEME technology is that the volume of the device is very small: the biggest is less than one centimeter and many are only several micrometers, and the thickness is even smaller. So it is suitable for the floating staff to fix in the lifejacket and carry on; the most important is that it does not affect the overall status and performance of the lifejackets.

This paper tries to integrate an acceleration sensor and a gyroscope in the unknown node with MEMS technology to monitor the state of motion of the unknown node after localization, such as speed and direction. Thus we can achieve the goal of real-time localization but only locate once and do not need to waste much cost and energy to locate again and again. As Figure 3 shows, after a period of time T, the unknown node moves to M. The speed is v, and the angle between DM and coordinate axis is θ. So the coordinate of D is

$$\begin{array}{l}{x}_M=x_d+{\int }_{\mathrm{0}}^T\left(vt\hspace{0.17em}\cos \hspace{0.17em}\theta \right)dt,\\ y_M=y_d+{\int }_{\mathrm{0}}^T\left(vt\hspace{0.17em}\cos \hspace{0.17em}\theta \right)dt.\end{array}$$

(6)

Figure 3

The schematic of MEMS localization.

3.3. Design Process of the Algorithm

• (1)

The anchor nodes periodically transmit beacon information that contains the node ID and position information.

(2)

After the unknown node receives all the beacon information, it uses formula (1) to transform the RSSI into distance.

(3)

When the number of anchor nodes that the unknown node receives is not more than prescriptive n, we will make a descending order of the anchor nodes ID, positions and distance to anchor nodes to establish three sets,

• (i)

  anchor nodes set: beacon $=\{A,B\cdots N\}$ ,

• (ii)

  distance set: distance = $\{d_A{,d}_B\cdots d_N\}$ ,

• (iii)

  positions set: position =  $\{(x_a,y_a)\cdots (x_n,y_n)\}$ .

(4)

Choose three anchor nodes whose RSSI is the biggest and use formula (3) to obtain the coordinate of the triangle. Then get the position estimation using improved triangle and centroid algorithm in formula (5).

(5)

After obtaining the original position information of the unknown node, we can observe the speed and direction of the node during the period from localization to finding the node and use formula (6) to obtain the final position information of the unknown node.

If the actual position of the unknown node is $(x,y)$ the localization error is [18],

$$\begin{array}{cc}& \text{ER}=\sqrt{{\left(x_M-x\right)}^2+{\left(y_M-y\right)}^2}.\end{array}$$

(7)

The flowchart of this localization algorithm is shown as Figure 4.

Figure 4

Algorithm flowchart.

4. Simulations and Analysis

The paper uses MATLAB 7.10 platform for computer simulation. Parameters are set as follows: in a square sensing area of $\mathrm{1000}\hspace{0.17em}\text{m}\times \mathrm{1000}\hspace{0.17em}\text{m}$ , there are 5 to 20 anchor nodes and 50 unknown nodes around. The path-loss exponent: $n=2.4,\hspace{0.17em}\hspace{0.17em}{X}_{\sigma }=7.98\hspace{0.17em}\text{dB}$ . The time from localization to finding the unknown node: $T=2\hspace{0.17em}\min$ . The weights of the anchor nodes are set like this: $r_1=2/5,\hspace{0.17em}\hspace{0.17em}{r}_{\mathrm{2}}=3/10,\hspace{0.17em}{r}_{\mathrm{3}}=1/5,\hspace{0.17em}\hspace{0.17em}{r}_{\mathrm{4}}=1/10$ . The simulation will analyze the algorithm (WTCA) in this paper, the trilateral localization algorithm (TLA), and the triangle-centroid algorithm (TCA), respectively [19].

Figure 5 shows that in the case of the same number of anchor nodes, the error of this algorithm is smaller than the trilateral localization algorithm and the triangle-centroid algorithm. The main reason is that the trilateral localization algorithm and the triangle-centroid algorithm do not think of the work status of all kinds of anchor nodes, and different kinds of anchor nodes have different weights to distinguish their relative relationship.

Figure 5

Localization error versus number of anchor nodes.

Figure 6 shows that in the case of the same RSSI ranging error, the error of the algorithm in this paper is smaller than the trilateral localization algorithm and the triangle-centroid algorithm also because the work status of different anchor nodes is different and they have different weights.

Figure 6

Localization error versus RSSI ranging error.

Figure 7 indicates that if going over the same time from localization to finding the target, compared with the trilateral localization algorithm and the triangle-centroid algorithm, our algorithm has smaller localization error and is more accurate. The reason is that this algorithm thinks of the dynamic environment at sea and uses MEMS aided method to observe the speed and direction of the maritime search and rescue target, so we can achieve more accurate position information.

Figure 7

Localization error versus time to search.

5. Conclusion

The paper has presented a new localization and tracking algorithm that is suitable for maritime search and rescue in wireless sensor networks based on many related researches. The algorithm is mainly divided into three stages: RSSI ranging, improved triangle and centroid algorithm and MEMS aided real-time localization method. This method combines the range-based localization algorithm with nonrange localization algorithm; it can achieve the goal of real-time localization and avoid repeated computation. The simulation results have indicated that the algorithm is effective. Compared with the trilateral localization algorithm and the triangle-centroid algorithm, the new algorithm has higher accuracy and is more suitable for the mobility at sea. Also the use of wireless sensor networks can achieve an initiative position indication by the searched targets themselves. So the algorithm proposed in this paper can get more accurate position information without consuming too much energy.