Location Algorithm for Nodes of Ship-Borne Wireless Sensor Networks

Abstract

Node location is of great significance as a supporting technology of wireless sensor network (WSN). The information without position would be greatly devalued. So this paper is about location algorithm for nodes of ship-borne WSN based on research on structure of ship and work environment of ship-borne WSN. The whole location process consists of two steps: one is location algorithm among cabins (LAAC), and the other one is location algorithm in the cabin (LAIC). LAAC refers to location with the topology of ship-borne WSN. We can learn which cabin the node lies in. LAIC refers to location based on received signal strength indication (RSSI), we can get distance relationship between nodes by RSSI, and then obtain the specific location by solving this distance relationship. In the last part, this paper verifies the designed location algorithm by experimenting on “A” ship. Experiments show that the location algorithm designed by this paper is feasible.

1. Introduction

Although WSN has been widely used in many fields, the study of ship-borne WSN is still in its infancy. At present, the research for ship-borne WSN mainly contains two aspects: first, some researchers have studied the communication of WSN on shipboard [1, 2]; second, some researchers have proposed the idea of using WSN to monitor work environment on shipboard [3–5]. For example, some researchers use WSN to monitor the temperature of the engine room.

To improve the safety of navigation and achieve the goal of early warning, we have proposed another application of WSN that is monitoring the environment and the state of cargo on shipboard, especially the dangerous cargo. Due to loading, unloading of cargo, and changing of equipments, the position of ship-borne WSN nodes is indeterminate. If crew cannot attain the position of nodes, emergency measures would be delayed in case of an alarm, so to save time in taking emergency measures, it is necessary to get the position of WSN nodes; that is to say, we should design location algorithm for ship-borne WSN and find out which cabin the node lies in and the specific position within the cabin.

So far, there have been many WSN location algorithms, among which location algorithms based on RSSI [6, 7], time of arrival (TOA), angle of arrival (AOA), and distance vector-hop (DV-hop) [8, 9] are most popular. RSSI is a measurement of the power present in a received radio signal, which would decrease with the increase of distance between the sender and the receiver. Compared with other ranging methods, it is more convenient to acquire RSSI, and we do not need to add any hardware device. For example, RSSI can be easily read from the 8-bit RSSI. RSSI_VAL register of the RF module CC2420 [7].

The WSN has different performances in different application environments, and location algorithm is related to the application environment of WSN. Ship-borne WSN has its own characteristics compared with the traditional WSN. For example, the spatial distribution of ship-borne WSN nodes is three dimensional, the variability of topology is confined, and the nodes on different decks cannot communicate directly. The detail of these characteristics would be introduced in the next part. Due to the characteristics of ship-borne WSN, the existing algorithm is not very suitable for ship-borne WSN. And, as we know, there is not any location algorithm for ship-borne WSN. In addition, the location of WSN node is very important for the safety of the ship. So it is necessary to make research on the location algorithm of ship-borne WSN.

2. Ship-Borne WSN

Ship-borne WSN consists of a large number of nodes, which can be divided into three categories based on the function of nodes. They are common nodes, repeaters, and base stations, respectively. The common node is responsible for collecting and transmitting data; the repeater is responsible for repeating the data which were transmitted to the base station by common nodes; and finally the base station is responsible for receiving the data from WSN and transmitting these data to the computer. Figure 1 shows the structure of ship-borne WSN. Compared with the traditional WSN, ship-borne WSN has its own characteristics.

Figure 1

The schematic diagram of ship-borne WSN.

The characteristics of ship-borne WSN are shown as follows.

• (1)

  The spatial distribution of ship-borne WSN nodes is three dimensional. There are many decks on ship, and many cabins on each deck. Unlike distribution of ship-borne WSN nodes, the distribution of traditional WSN nodes stays almost on the same panel. So the distribution of ship-borne WSN nodes varies greatly compared with the traditional WSN nodes.

• (2)

  The variability of topology is confined. A ship is constructed by joining many blocks together, and blocks are made of steel plates cut or welded, which means that the ship is a large structure made mainly of steel. This metallic structure shields radio signals. This will severely attenuate the transmitting of nodes. Compared with the traditional WSN, the variability of ship-borne WSN topology is confined.

• (3)

  The nodes on different decks cannot communicate directly. They mainly communicate through the repeaters located at the stairs between decks [10].

• (4)

  The nodes in the same cabin have similar route; that is to say, they would transmit data to the base station by the same repeater. It should be noted that “cabin” in this paper refers to the area in which the nodes have the similar route when they transmit data to the base station. That is to say, the division of cabins is related with the location of repeaters and the structure of the ship.

• (5)

  The nodes in the same cabin would construct a small sensor network which can be referred to as subnet, as shown in Figure 1.

With so many characteristics, it is indispensable to study ship-borne WSN and location algorithm.

3. Location Algorithm

To cope with the characteristics of ship-borne WSN, this paper has designed the location algorithm for nodes of ship-borne WSN. In the process of locating, we call the node, whose position is known, “anchor node” (AN) [11], and some anchor nodes should be prearranged in cabins before locating; we call the node waiting to be located “blind node” (BN) [12].

3.1. An Overview of Process of Location

The whole location process can be divided into two steps: the first is LAAC, and the second is LAIC.

First, we can acquire the name of cabin in which blind node is arranged, according to LAAC. And then let the blind node transmit data to the anchor nodes in the cabin and record the RSSI value. According to these RSSI values, we can build up the distance relationship between blind node and anchor nodes in the cabin. At last, we can calculate specific location by solving this distance relationship. Figure 2 shows the flow of location for ship-borne WSN. As can be seen from the figure, the location result consists of two parts: one is the name of the cabin, and the other one is the specific position in the cabin.

Figure 2

The flow diagram of location.

3.2. Location Algorithm among Cabins (LAAC)

LAAC refers to pinpointing the name of cabin in which the blind node locates by the route of packets received by the base station from the blind node. We can analyze these packets, construct the topology of ship-borne WSN, decide the route, and get the repeater nearest to the blind node. Finally, according to the repeater, we can get the name of cabin where the blind node is by looking up the relational table, which contains the IDs of repeaters and the names of cabins.

Figure 3 shows the flow of LAAC. First, we should arrange repeaters and record their positions. Because of the complicated structures of ships, it is necessary to arrange these repeaters properly. Two rules should be obeyed: one is to make sure that the ship-borne WSN can communicate normally; the other one is to try our best to let the blind nodes in one cabin transmit data to the base station by the same repeater. According to the characteristics of ship-borne WSN, repeaters should be arranged at stairs of decks. Then, we can make relational table by the location of repeaters. The table contains the ID of repeater and the name of cabin in which the blind node lies, which would transmit data to the base station by this repeater. The format of relational table is shown in Figure 3.

Figure 3

Location algorithm among cabins.

When the base station receives packets from the blind node, we can get the repeater nearest to the blind node by analyzing the route. At last, checking the relational table, we can get the name of the cabin in which the blind node lies.

The process of locating the algorithm among cabins is described as follows.

• (1)

  The base station acquires the route of packets from the blind node: $B_r=\{$ BN, Repeater_1, Repeater_2, Repeater_N,…, Base station}.

• (2)

  Analyze the route and acquire the ID of the nearest repeater to the blind node, NR_B_ID.

• (3)

  Acquire location by the relational  table:   $S=\{$ (Repeater_1_ID, cabin_number_1), (Repeater_2_ID, cabin_number_2),…, (Repeater_N_ID, cabin number_N)}.

• (4)

  According to the NR_B_ID, check the location by the relational table S and acquire the cabine_nuber_i.

• (5)

  Get the name of the cabin in which the blind node locates.

3.3. Location Algorithm in the Cabin (LAIC)

LAIC refers to geting the three-dimensional coordinates in the cabin according to RSSI values after confirming the cabin number in which the blind node lies.

In the cabin, there are some anchor nodes, which were arranged before location, and we can get the IDs and coordinates of these anchor nodes from the database. When we want to locate the blind node, we can let it transmit packets to these anchor nodes in the cabin, and then the anchor nodes are activated. In order to decide the signal transmission model, actually to decide the path loss exponent, these anchor nodes start to communicate with each other until the path loss exponent is decided. After the path loss exponent is decided, these anchor nodes just receive the packets from the blind nodes and transmit these RSSI values to the base station. RSSI is related with distance, so we can get the distance relationship between the blind node and these anchor nodes according to the path loss exponent. The following formula describes the relationship between RSSI and distance:

$$\begin{array}{cc}& P_r\left(d\right)-P_r\left(d_{\mathrm{0}}\right)=-\mathrm{10}\beta \log \left(\frac{d}{d_{\mathrm{0}}}\right)+{\text{X}}_{\text{dB}},\end{array}$$

(1)

where X_dB is a zero-mean Gaussian random variable (in dB), β is the path loss exponent, and $P_r(d_{\mathrm{0}})$ is the average of signal strength at a reference distance $d_0$ (1 m in our case) [13].

At last, we can calculate the specific coordinates of blind nodes using this distance relationship. The flow of LAIC is shown in Figure 4.

Figure 4

Location algorithm in the cabin.

According to the analysis of LAIC, we can know that there are 3 types of packets transmitted in the process of location. The first category is the packets of location transmitted by the blind nodes, and we call them packet_A. The second category is the packets transmitted among anchor nodes to decide the signal transmission model, and we call them packet_B. And the last category is the packets which contain RSSI values, and we call them packet_C. The format of packets in LAIC is shown in Figure 5. ID_A indicates the ID of the sender, and ID_B is the ID of the receiver.

Figure 5

Three types of packets in LAIC.

Assume that there are N anchor nodes in the cabin and that the coordinates of ith anchor node are ( $x_i$ , $y_i$ , $z_i$ ); the coordinates of the blind nodes are (x, y, z), and the distance from the blind node to the ith anchor node is $d_i$ , so we can get the following formula:

$$\begin{array}{cc}& {\left(x_i-x\right)}^{\mathrm{2}}+{\left(y_i-y\right)}^{\mathrm{2}}+{\left(z_i-z\right)}^{\mathrm{2}}={d_i}^{\mathrm{2}},\end{array}$$

(2)

where i is, respectively, $1,2,3,\dots ,N$ . Due to the error of distance, we cannot solve formula (2). However, it is possible to estimate a position which is close to the real position, and we call this position the “estimated position.” In order to let the estimated position and the real position to be closer, we make the quadratic sum of difference value between the distance from the estimated position to anchor nodes and the measured distance minimum, which is the least square algorithm. So we have the following formula:

$$\begin{array}{cc}& \mathrm{\Delta }d=\sum _{i=\mathrm{1}}^n{W}_i{\left(\sqrt{{\left(x-x_i\right)}^{\mathrm{2}}+{\left(y-y_i\right)}^{\mathrm{2}}+{\left(z-z_i\right)}^{\mathrm{2}}}-d_i\right)}^{\mathrm{2}},\end{array}$$

(3)

where $\mathrm{\Delta }d$ is the quadratic sum of difference between the distance from the estimated position to anchor nodes and the measured distance, and $W_i$ is the weighed factor ( $\mathrm{1}/d_i$ in our case). That is to say, the estimated position ( $\widehat{x}$ , $\widehat{y}$ , $\widehat{z}$ ) makes function $\mathrm{\Delta }d$ (x, y, z) minimum. At point ( $\widehat{x}$ , $\widehat{y}$ , $\widehat{z}$ ), the partial derivation is zero, and the partial derivation is shown as in the following formula:

$$\begin{array}{cc}& \frac{\partial \mathrm{\Delta }d\left(x,y,z\right)}{\partial x}=\mathrm{0},\\ \frac{\partial \mathrm{\Delta }d\left(x,y,z\right)}{\partial y}=\mathrm{0},\\ \frac{\partial \mathrm{\Delta }d\left(x,y,z\right)}{\partial z}=\mathrm{0}.\end{array}$$

(4)

Solving these equations, we can get the estimated position [14].

For location algorithm based on range, the location error is influenced by distance errors and geometric errors, in which geometric errors refer to the errors caused by the spatial arrangement of blind node and anchor nodes when the distance errors are constant. Geometric dilution of precision (GDOP) can describe geometric error. GDOP is shown as in the following formula:

$$\begin{array}{cc}& \text{GDOP}=\sqrt{\frac{{\sigma }_x^{\mathrm{2}}+{\sigma }_y^{\mathrm{2}}+{\sigma }_z^{\mathrm{2}}}{{\sigma }^{\mathrm{2}}},}\end{array}$$

(5)

where σ is the distance error and ${\sigma }_x$ , ${\sigma }_y$ , and ${\sigma }_z$ are the location errors in three directions. It is thus evident that geometric error is just related with spatial arrangement. The smaller the GDOP is, the smaller the geometric error is, and the better the spatial arrangement is, the bigger the GDOP is; the bigger the geometric error is, the worse the spatial arrangement is. It is proved that GDOP is inversely proportional to the volume of the shape constructed by unit vectors from the blind node to anchor nodes. The smaller the volume is, the bigger the GDOP is; the bigger the volume is, the smaller the GDOP is [15].

4. Experiments on Shipboard

In order to verify the location algorithm designed by this paper, we experimented on the “A” ship. The deckhouse of the “A” ship consists of the following decks: arranged vertically (from bottom to top): the tank top; tween deck; main deck which houses several classrooms; promenade deck; boat deck; captain deck; navigation deck; and compass deck. The eko node and the IRIS node produced by crossbow are used in the experiments. The radio frequency of ship-borne WSN is 2.4 GHz, the transmitter power output is 3 dBm, and the receive sensitivity is −101 dBm.

4.1. Experiments for LAAC

According to LAAC, we arrange the repeaters; the positions of repeaters are shown in Figure 6, and the relational table is made and shown in Table 1. After network, the topology of ship-borne WSN is shown in Figure 6.

Table 1

Relational table for LAAC.

Repeater ID	Compartment
Node 9	Boat deck
Node 6	Promenade deck
Node 7	Main deck
⋮	⋮

Figure 6

Topological structure of ship-borne WSN.

Assume that Node 4 is the blind node, by analyzing the received packets, we can acquire the route: Node 4 → Node 7 → Node 6 → Node 9 → Base 0; the black arrow in Figure 6 shows the route. Then, we can find the nearest repeater: Node 7 to Node 4. At last, by looking up the relational table, we know that the blind node is on the main deck. And Node 4 is actually at the classroom of the main deck. It is obvious that LAAC is feasible.

4.2. Experiments for LAIC

Before the experiments for LAIC, the RSSI values in different distances are measured. In Figure 7 a graph is shown for scattering every distance (1 m, 2 m, 4 m, 6 m, 8 m, 14 m, 20 m, and 26 m). And the straight line in the figure is the mean RSSI value.

Figure 7

Reading RSSI on CC2420.

The experiment for LAIC is preceded in a cabin on the main deck. The scale of the cabin is 12 m × 8 m × 3 m. Before location, we had arranged 6 IRIS nodes in the classroom as anchor nodes. In the experiment, we tested 40 times for a node located at point (5, 4, 2). And the location result is shown in Figure 8. In this figure, the green pentagram indicates the true position of the blind node; triangles indicate location results, in which the color indicates the location error (location error refers to the distance between the true position and the estimated position); the black balls indicate anchor nodes. In Figure 8, the 3D view and the projective view of location results are displayed.

Figure 8

Location results.

In the projective figures, the distribution of location results indicates the location error in this plane. And the bigger the area of the distribution is, the bigger the location error of this plane is. The relation of the location error in three planes is shown in the following formula:

$$\begin{array}{cc}& E_{X\text{-}Y}<E_{X\text{-}Z}<E_{Y\text{-}Z},\end{array}$$

(6)

where $E_{X\text{-}Y}$ , $E_{X\text{-}Z}$ , and $E_{Y\text{-}Z\mathrm{\hspace{0.17em}\hspace{0.17em}}}$ are, respectively, the location errors in $X\text{-}Y$ , $X\text{-}Z$ , and $Y\text{-}Z$ planes. The distance error in three planes is almost the same as each other. So the difference of location error in the three planes is caused by spatial arrangement of the blind node and anchor nodes, which is geometric error. According to the above paragraphs, we know that geometric error is related with the volume of the shape constructed by unit vectors from the blind node to anchor nodes. Figure 9 shows these unit vectors and the projective figure of the shape. The relation of the area is shown in the following formula:

$$\begin{array}{cc}& S_{X\text{-}Y}>S_{X\text{-}Z}>S_{Y\text{-}Z},\end{array}$$

(7)

where $S_{X\text{-}Y}$ , $S_{X\text{-}Z}$ , and $S_{Y\text{-}Z}$ are, respectively, the areas of the shape constructed by unit vectors from the blind node to anchor nodes in $X\text{-}Y$ , $X\text{-}Z$ , and $Y\text{-}Z$ planes.

Figure 9

The shape constructed by vectors from blind node to anchor nodes.

According to formulas (6) and (7), we can reach the following conclusion: the geometric error in each plane is influenced by the projected area of shape constructed by the unit vectors from the blind node to anchor nodes. The bigger the projective area is, the smaller the geometric error is; on the contrary, the geometric error is bigger.

Therefore, when we arrange these anchors, the geometric error should be fully considered.

Figure 10 shows the location error of experiment for LAIC, whose mean value is 1.5 m and RMSE (root mean square error) is 0.35 m. And the location error which is smaller than 2.0 m is 87.5 percent.

Figure 10

The error of location results.

5. Conclusions

By analyzing the characteristics of ship-borne WSN, this paper has designed and verified location algorithm for nodes of ship-borne WSN, which consists of LAAC and LAIC, and to test the location algorithm, we experimented on the “A” ship. Experimental results show that we can get the name of the cabin in which the blind node is by LAAC, and we can get the specific position by LAIC. In the cabin of 12 m × 8 m × 3 m, the precision of location is about 1.5 m.

The location algorithm can provide the position for nodes of ship-borne WSN. In case of an emergency, the algorithm can help the crew to locate the position of causes without delay and provide safeguard for life and property at sea. In addition, the location algorithm designed by this paper can also be used in the similar situation, for example, when WSN is used to monitor the condition of cargo hold and container. The reason is that it has a similar topology to the ship-borne WSN.