Ultrashort Baseline Positioning System: Implementation and Tests at Sea（2）

The useful DFT property for correlation purposes is shown in Fig. 8. In a very simple way, we can say that it possible to ‘change’ a time domain convolution h[n]⊛x[n] for a frequency domain multiplication H[k]X[k]. This approach requires the computation of one DFT (H[k] is permanently stored in the DSP internal memory), one multiplication and one IDFT, reducing computing complexity from o(N2 ) to o(Nlog2N). When the number of samples to be convolved is suffificiently large, as it is our case, this performance improvement, together with the use of a fast DFT algorithm (FFT), is extremely important because it makes real-time convolution implementation possible. Even with the use of the above solution, convolution implementation can be further improved. As described in section 3.1 the data buffer consists of three memory blocks with same size L of the expected signal and, at the end of each acquisition cycle, just one of those blocks is renewed, being the other two just shifted. In this way it makes no sense to perform a 3L size convolution when just one third of the data is different from the previous acquisition cycle. Let’s consider the data buffer 3L length sequence {x[n]} as a sum of three L length sequences, {x₁[n]}, {x[n]2} and {x[n]3}, in the following way,

with

sequence {x_i [n]} representing the ith block of the data buffer. Replacing (14) in the matched fifilter output given by (11)

yields

where y_i [n] = (h ⊛ xi) [n] is the fifilter’s response to ith block’s data. As we can see from (16) it is possible to compute the convolution of the expected signal with the whole data buffer as a sum of the convolutions with each of the individual blocks. Thus, at each acquisition cycle we can perform a L size instead of a 3L size convolution, considerably improving time performance. This convolution method is known as overlap-add because since each h⊛xi convolution has length 2L − 1 there will be an overlap of L − 1 elements when adding h ⊛ x1 to h ⊛ x2 and h ⊛ x₂ to h ⊛ x₃

3.3 Decision

After performing the matched fifilter convolution the system has to decide if the expected signal is or not present in the data buffer. To study the decision criterion we should look back to fifigures 4a and 4b where the fifilter’s response to a DSSS signal was presented. The idea behind the decision criterion will be to compare the maximum value of the matched fifilter’s output with its average absolute value. Because of the noise, that is an unknown component of the acquired data, there will always be some degree of uncertainty. However, since having a maximum value considerably higher than the average absolute value is a characteristic associated with the fifilter’s response to the expected DSSS sigal and not to the noise, we will consider that the greatest the difference between those two values, the greatest the chance that the expected signal is present in the buffer. In this way we defifine a threshold for the system, and the expected signal is considered to be present when

When the expected signal presence is indicated the system has to wait for the next acquisition cycle and just the second consecutive detections guarantees that the signal is completely inside the buffer, as explained in section 3.1.

3.4 Position computation

Unlike acquisition, that is continually happening for all the four hydrophones, the processing of the acquired data and signal presence decision are implemented just for one of the four hydrophones. We remeber that the whole processing and decision must be performed in less time than one buffer block acquisition, being this the most critical point of implementation. For this reason it is not possible to process the data present in all the four buffers. Despite this, when the expected signal is detected in the data buffer chosen for real-time processing, acquisition is temporarily interrupted and the three left data buffers are processed in order to fifind signal TOA. Position is computed according to the study presented in section 2.2, after what acquisition is restarted.

4 At sea tests

Once the implementation was completed a series of at sea tests were conducted. Tests took place in Cidade da Horta, Acores, between June 22 and 26, 2009. Since position result is expressed in USBL array’s coordinate frame it is desirable that the array remains at rest relative to Earth’s coordinate frame, otherwise USBL array’s movement would inflfluence position computation even when emitter’s position is stationary. For this reason tests were hold inside an harbor. Like this it was possible to fifirmly fasten the array ensuring that position results were not inflfluenced by its movements. However multipath and noise presence is much stronger inside the harbor and tests results were affected by this. Tests are divided into two categories: stationaty and dynamic. In both of them results’ analysis is carried out separately for distance and direction estimation because computation methods are different, as seen in section 2.2.

4.1 Stationary tests

For stationary tests the emitter was tied to a pier that suffers negligible flfluctuations for the purpose intended and the system was left running for 20 minutes. The histogram of stationary distance results, as obtained during the test by DSP processing, is presented in Fig. 9. From Fig. 9 we see that distance results are mostly divided between two non-contiguous sub-intervals,[77.70; 77.80]m and [77.90; 78.05]m. Being the emitter and the USBL array both stationary this is an unexpected result. In order to understand the reason why it happens we should look to the data used to decide about the presence of the signal and to compute emitter’s distance. Matched fifilter convolution for two different detections is shown in Fig. 10.

Figure 9: Histogram of stationay test distance results

Figure 10: Matched fifilter convolution

As can be seen from Figures 10a and 10b matched fifilter convolution has two maximums very close in value. Because signal TOA is computed as the convolution’s peak, when the absolute maximum is the fifirst one distance will lie at the nearest sub-interval and when the absolute maximum is the second one distance will lie at the farthest sub-interval.

After a detailed analysis of convolution results of the four channels for all detections we can say that Figures 10a and 10b are representative of what happened throughout the test. In Fig. 11 it is presented an histogram of the time difference between the two convolution maximums for the different channels.

As it is clearly shown in Fig. 11 the time difference between the two convolution maximums varies from channel to channel. That difference is greater for channel 4 convolutions, smaller for channel 3 and intermediate for channels 1 and 2. Taking into account the above remarks and knowing that to channel 4 is connected the deepest hydrophone, to channel 3 the hydrophone closest to the surface and to channels 1 and 2 the hydrophones at intermediate depth, we fifind that the second maximum in the matched fifilter convolution is caused by a signal reflflection on the sea surface, being the fifirst maximum caused by direct path signal arrival.

To get round this multipath detection problem we have to modify TOA estimation method. When the decision criterion given by (17) is true, instead of estimate TOA as the absolute maximum position, we will consider TOA to be given by the position of the fifirst maximum that exceeds the decision threshold. In Fig. 12 we reproduce the results presented before in Fig. 9, obtained now post-processing the data acquired during the test with the new TOA estimation method.

Figure 12: Histogram of stationay test distance results with new TOA estimation method

As can be seen from Fig. 12, with the new TOA estimation method, distance results are no longer divided between two non-contiguous sub-intervals and distance standard deviation is reduced form 8.8 to 1.6cm. In this way system rejection to multipath is greatly improved and therefore global system performance.

If multipath effects have caused errors in the order of centimeters when computing emitter’s distance, when computing emitter’s direction those erros are in the order of tens of degree. The stationary direction results, as obtained during the test by DSP processing, are plotted in Fig. 13.

As can be seen from Fig. 13 direction computation gave very inconsistent results.

However, in order to understand the reason of this poor performance, it’s better to look to the data used to compute emitter’s direction than to the fifinal result. As described in section 2.2 direction is computed from signal TDOA to the different hydrophones. In Fig. 14 we present 3 histograms of TDOA between the 4 hydrophones.

We see that inconsistent direction results shown in Fig. 13 are justifified by inconsistent TDOA estimation presented in Figures 14a, 14b and 14c. As previously happened in distance computation (Fig. 9), TDOA results are divided between non-contiguous sub-intervals. Also the time difference between those sub-intervals, 30 to 40 samples, is similar (see Fig. 11) suggesting that the problem may be caused by signal reflflection as before. Therefore, we will try to solve the problem in the same way: modify TOA estimation method to avoid multipath detection. In Fig. 15 we reproduce the results presented in Fig. 14, obtained now post-processing the data acquired during the test with the new TOA estimation method.

As expected, new TOA estimation method greatly improves TDOA estimation, which has now a precision of about 8μs (2 samples). Emmiter’s direction computed with this TDOA data is shown in Fig. 16. Comparing it with direction obtained during the test (Fig. 13) becomes evident that system performance is drastically enhanced, being both angles estimated with a standard deviation of about 0.4 deg.

Figure 16: Stationay test direction results with new TOA estimation method

When it comes to time delay estimations there is a very common method: cross-correlation between data. With the purpose of fifinding signal TDOA to different hydrophones, cross-correlation was also employed in postprocessing analysis. Obtained results are not presented here but they revealed an interesting feature: cross correlation performance depends on the channels being processed. Similar performance is achieved for TOA1- TOA2 estimation (channels 1 and 2 are connected to hydrophones at the same depth) and inferior performance for any other two channels. This result is also justifified by signal reflflection and hydrophone placement at different depths.

Figure 14: TDOA histograms of stationary test direction results

Figure 15: TDOA histograms of stationary test direction results with new TOA estimation method

4.2 Dynamic tests

For dynamic test the emitter was installed in a boat whose position was being recorded using a GPS. The distance and angles intervals that was possible to test were very limited. Still, dynamic test was conducted inside the harbor to allow adequate fastening of USBL receiving array, like explained in the begining of the section.

Dynamic test duration was 1445 s (approximately 24 min). Since emisson frequency is one signal per second, 1445 would be the maximum number of detections. However, 203 emissions were lost (14% of total). In Fig. 17 distance results for dynamic test are shown. Lost emissions are plotted at 0 m distance.

In addition to lost emissions there are detections that lead to clearly incorrect distance results. These incorrect results are caused by direct path signal lost and correspondent multipath detection. In order to quantify these cases we consider a maximum speed of 4m.s−1 for the boat and a particular distance result is classifified as incorrect if it means a higher speeed since the last detection. In this way, from 1242 detections 1210 are classifified as correct (84% of 1445 total emissions). Given the percentages of detections and results classifified as correct, dynamic distance computation performance is considered satisfactory.

To assess system performance computing emitter’s direction we follow the same strategy. Direction results are not plotted but percentage of correct results is presented in Table 1. We compare direction results obtained with two different methods for TDOA estimation already mentioned: fifirst convolution maximum that exceeds decision threshold and data cross-correlation. Just the 1210 receptions that led to a correct distance result are used now.

Table 1: Dynamic test direction results

Both methods lead to similar performance but, unlike stationary test, cross-correlation presents slightly better results now. Also performance is very similar between longitudinal and elevation angles. This fact can be questioned since, as we said before, cross-correlation method performance depended on the channels being processed and that performance was considerably better for TOA1- TOA2 estimation, channels connected to hydrophones at the same depth and therefore suffificient to compute longitudinal angle. However, in section 2.2 we developed a least squares solution for emitter’s direction that uses all the 4 channels to compute any of the angles. Like this it is possible to increase redundancy but also the inferior performance estimating TDOA for hydrophones placed at different depths can be damaging longitudinal angle computation. To confifirm that we repeat direction computation, now without least square minimization and using channels 1 and 2 (same depth) to calculate longitudinal angle and channels 3 and 4 (different depths) for elevation angle.

Table 2: Dynamic test direction results without least squares minimization

From Table 2 we see that again cross-correlation presents slightly better results, but performance between longitudinal and elevation angles is now quite different. Longitudinal angle performance signifificantly improves, approaching 100% of correct results, and elevation angle performance remains at the same accuracy level. These results show that least square minimization was damaging system performance. Separating channels 1 and 2 from 3 and 4 we lose redundancy but the less accurate TDOA estimation from channels 3 and 4 is not damaging longitudinal angle computation. Nevertheless, least square minimization should be a good option when TDOA estimation error is similar between channels.

To give a global idea of system potential we compare in Fig. 18 emitter’s GPS tracking with USBL positioning computed from correct distance results and longitudinal angle obtained without least squares minimization.

5 Conclusions

This work presented the design, implementation, and validation at sea of an USBL acoustic positioning system.

Signal detection and TOA estimation were based on the matched fifilter response, which leads to the highest signal-to-noise-ratio. The classical acoustic pure tone pulse was compared with wide band coded spread spectrum signals, resulting on improved TOA resolution and stronger multipath and noise rejection. Emitter’s position is computed resorting to the planar approximation of the acoustic wave.

The most critical development task was digital fifilter implementation. Digital fifiltering consists of signal convolution and must be performed within practical time. Real time implementation was possible thanks to the use of a DSP and processing techniques that greatly reduce convolution time (based on DFT properties).

References

[1] A. Alcocer, P. Oliveira, and A. Pascoal. UnderwaterAcoustic Positioning System Based On Buoys With GPS. Proceedings of the Eighth European Conference on Underwater Acoustics, 8th ECUA, June 2006.
[2] Thomas C. Austin. The Application of Spread Spectrum Signaling Techniques to Underwater Acoustic Navigation. Proceedings of the 1994 Symposium on Autonomous Underwater Vehicle Technology, 1994.
[3] P. Batista. Controlo de Ve′ıculos Aut′onomos Baseado na Informac¸˜ao Directa de Sensores Ac′usticos. Relat′orio de trabalho final de curso, Universidade T′ecnica de Lisboa - Instituto Superior T′ecnico, Setembro 2005.
[4] R. Cusani. Performance of Fast Time Delay Estimators. IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37(5):757–759, May 1989.
[5] F. Gustafsson and F. Gunnarsson. Positioning Using Time-Difference Of Arrival Measurements. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, 2003.
[6] Emmanuel C. Ifeachor and Barrie W. Jervis. Digital Signal Processing. A Practical Approach. AddisonWesley Ltd., 7th edition, 1998.
[7] Sonardyne Inc. http://www.sonardyne.com/, 2009.
[8] F. Lima and C. M. Furukawa. Development and Testing of an Acoustic Positioning System - Description and Signal Processing. Proceedings of the IEEE 2002 Ultrasonics Symposium, 2002.
[9] Isabel M. G. Lourtie. Sinais e Sistemas. Escolar Editora, 2nd edition, 2007.
[10] P. H. Milne. Underwater Acoustic Positioning Systems. Gulf Publishing Company, 1983.
[11] Sanjit K. Mitra. Digital Signal Processing. A Computer-Based Approach. McGraw-Hill, 2nd edition, 2001.
[12] M. Morgado, P. Oliveira, C. Silvestre, and J. F. Vasconcelos. USBL/INS Tightly-Coupled Integration Technique for Underwater Vehicles. Proceedings
Of The 9th International Conference on Information Fusion, 2006.
[13] Marco M. Morgado. Sistema de Navegac¸˜ao Inercial com Ajuda USBL. Relat′orio de trabalho final de curso, Universidade T′ecnica de Lisboa - Instituto Superior T′ecnico, Setembro 2005.
[14] J. O. Smith and J. S. Abel. The Spherical Interpolation Method of Source Localization. IEEE Journal of Oceanic Engineering, vol. 12(1):246–252, 1987.
[15] D. Thomson and S. Elson. New Generation Acoustic Positioning Systems. Oceans 2002, vol. 3:1312–1318, Oct. 2002.
[16] Robert J. Urick. Principles of Underwater Sound. Peninsula Publishing, 3rd edition, 1983.
[17] K. Vickery. Acoustic Positioning Systems. A Pratical Overview Of Current Systems. Proceedings of the 1998 Workshop on Autonomous Underwater Vehicles, August 1998.
[18] K. Vickery. Acoustic Positioning Systems. New Concepts - The Future. Proceedings of the 1998 Workshop on Autonomous Underwater Vehicles, August 1998.
[19] J. Yli-Hietanem, K. Kalliojarvi, and J. Astola. LowComplexity Angle of Arrival Estimation of Wideband Signals Using Small Arrays. Proceedings Of The 8th IEEE Signal Processing Workshop on Statistical and Array Processing, 1996.