# Nibble-CRC for Underwater Acoustic Communication

Imtiaz Ahmed Khan, Nam-Yeol Yun, Soo-Hyun Park

► To cite this version:

Imtiaz Ahmed Khan, Nam-Yeol Yun, Soo-Hyun Park. Nibble-CRC for Underwater Acoustic Communication. 9th International Conference on Network and Parallel Computing (NPC), Sep 2012, Gwangju, South Korea. pp.550-558, 10.1007/978-3-642-35606-3_65. hal-01551338

HAL Id: hal-01551338

https://inria.hal.science/hal-01551338

Submitted on 30 Jun 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Nibble-CRC for Underwater Acoustic Communication

Imtiaz Ahmed Khan, Nam-Yeol Yun and Soo-Hyun Park

Ubiquitous System Lab., Graduate School of BIT, Kookmin University, Seoul, Korea

`{fish786, anuice, shpark21}@kookmin.ac.kr`

**Abstract.** Underwater acoustic sensor networks (UWASNs) are complex in design due to the characteristics of underwater medium. The underwater communication environment and the medium vary on time, geographical location and depth. Sensor nodes are also born with some limitations such as fixed amount of energy, small size memory and node mobility. Signals travel inside a noisy acoustic channel which required checking errors after receiving. Secure communication is one of the main characteristics of any networks. UWASNs also maintain a security protocols in each layer. Moreover, data link layer performs the main task of error check. To protect unauthorized access to our network and for a common line of defense against the errors, it requires attentions during the protocol design. Depends on the several error detection mechanisms, cyclic redundancy check (CRC) performs better than other mechanisms in respects of the different underwater factors. In this paper, we discuss about the CRC: how it is different from other mechanisms in terms of carrying functions that helps to check double error (running sum) but correct checksum. The trade-offs between error detection system designs (using a nibble size CRC) and underwater communication system designs.

**Keywords:** UWASNs; Error Detection; Network Efficiency; Energy Efficiency; CRCs

## 1 Introduction

Underwater acoustic sensor networks are attracted lots of interest because of the capabilities to solutions of underwater related applications and researches [1-5]. To monitor underwater environment and research works such as, oceanic geographic data collection, oceanic environmental monitoring, resource investigation, disaster prevention and tactical surveillance application, underwater acoustic communication is the fundamental technology for these applications [6].

Moreover, monitoring underwater quality and examining the water quality in rivers and canals for industrial water pollutions after technical disaster in different regions that could be put an effect on our fishes and underwater vegetables. Recent Japanese tsunami which destroy one nuclear power generation plant and radiated a large area of radio activity in environment as well as rivers and connecting oceans. Short term sensor network can be deployed to measure the pollution level and polluted area for
our civilians and sensor network is the only solution for this as it is economical and
easy to deploy.

The error checking is one of the vital issues as the channel is a noisy and unsecure.
Different error checking mechanisms are used depends on the system design. Accord-
ing to our previous study [7], one byte CRC performs better among checksum, parity
bit, longitudinal redundancy check (LRC), vertical redundancy check (VRC) different
FEC and ARQ mechanisms.

We realized that as our data size was much smaller than RF based terrestrial net-
works. We need to reduce the duration of communication between base stations to
sensor nodes (end-to-end delay). The nibble size CRC is our first try to integrate real
time communication in our robot fish and sensor networks. Though nibble size CRC
is not enough in terms of accuracy, it performs better than checksum or parity bits as
it works on polynomial arithmetic GF (Galois field with two elements) finite algebra
theory. In this paper, we describe our nibble size CRCs and its theoretical error detec-
tion capabilities and finally we analyze the performance of CRC-8, CRC-16, CRC-32,
and CRC-64.

## 2 Related works

The characteristics of UWASNs are different from the RF based terrestrial networks. The propagation speed of acoustic signals in the water is about $1.5 \times 10^3$ m/s and also affected by many factors such as path loss, multi path, noise and Doppler spread. For these reasons, the error rate is very high in acoustic channel. The channel also works as half duplex communication which requires long time for communication between senders to receivers usually takes tens milliseconds. The node mobility due to water current is 3-6 kilometers per hour which change the topology of the networks [8], [10]. The main problem is the limited energy. Still there is no way to recharge the power cells. The architect of UWASNs is also 2D vs. 3D [1-2].

Electromagnetic wave (EM) in radio frequencies and, conventional radio frequency
does not work well in underwater due to nature of the medium and can propagate at
short distances through conductive sea water only at extra low frequencies (30-
300Hz) which required large antenna and high transmission power [8-9]. Optical
signals are suitable for surface clean water and short distance (10-100 meters) and
high bandwidth (10-150Mps) communication [10]. Moreover, transmission of optical
signals requires high precision in pointing the narrow laser beams, which is not very
easy due to the mobility of the sensors depends on water current. For signaling,
among different physical waves (like sound, radio & optical), due to the extraordinary
characteristics of sound, acoustic wave is the only signal that can travel rapidly with
lower attenuation in underwater environment than other signals.

The communication among underwater sensors and autonomous/unmanned un-
derwater vehicle (AUV/UUV) is a great challenge. Moreover, different error checks
mechanisms are used in different layers for reliable data communication and the se-
cured data transmission. But data link layer performs the main task of error check.
Signals coming from different directions with different speeds bit by bit towards the
receiver are transferred to the data link layer. Error detection mechanisms are playing an important role as they are used every time when some data exchanges in-side networks.

## 2.1 Theory of CRC

CRCs performance is the best as it works based on polynomial arithmetic GF (2) (Galois field with two element) Finite Algebra theory. Among various error detection methods the CRC, mechanism performed well in MAC layer as an error detection mechanism. Most of the error detection mechanisms using running-sum which could make a lot of possibility for receiving wrong code words as the error is undetected due to alter double bit position. But CRC is used for detect double bit errors.

CRC works on binary field and the binary polynomials that facilitate the definition of cyclic redundancy codes. Simply, it can be said that a field is an algebraic system which the operation of addition, subtraction, multiplication and division can be performed. Fields can be finite or infinite and these finite binary fields only denoted by two numbers 0 and 1. Mathematical equation is something like if we have *k* bits messages, if we want to send it, we add some redundancy bits that is called *n* bits, and *n* bits code words always > *k*. How many redundancy bits we add in the message (*n*-*k*) bits = *r* (redundancy bits). Based on some formulas or methods, the code word created some times exclusive or operation, sometimes polynomial equations, or some block calculated method.

The selection of a code for a specific application depends on a number of factors including the amount of protections required, the overhead involved, the cost of implementation, the error control strategy employed and the nature of the errors. It is shown that *n*-*k* check bits of a code forming the overhead directly affect the error control capability of a code. In general the more check bits in a code, the greater its power of error detection is. A fix number of check bits, the relative overhead of a code can be kept low by using a large number of message blocks *k* [11].

CRC also known as polynomial codes which used such a code word by using associated polynomials are multiplies of a certain polynomials g(x) called generator polynomials. The main error detection power depends on the generator polynomials which are made of combination of prime numbers.

Let M(x) be the message polynomial, G(x) generator polynomial, G(x) is fixed for a given CRC scheme. And G(x) is known by both sender and the receiver. Now we can create a block polynomial F(x) based on M(x) and G(x) such that F(x) is divisible by G(x).

### Sending

1. Message M(x) multiply by xⁿ

2. Divide xⁿM(x) by G(x)

3. Ignore the quotient and keep the remainder C(x)

4. Make a block form and send f(x)= xⁿM(x) =C(x)
Receiving

* Receiving $F'(x)$

* Divide $F'(x)$ by $G(x)$

* Accept if remainder is 0, otherwise an error occurred rejected.

Working principle

$x^n M(x) + C(x)$ is divided by $G(X)$, so $x^n M(x) = G(x)Q(x) + C(x)$

$x^n M(x) + C(x) / G(x) = G(x)Q(x) / G(x) + C(x)+C(x) / G(x)$ { binary modular addition is equivalent to binary modular subtraction ($C(x)+C(x)=0$)}

## 2.2 Different error detection by CRC [12]

Let's think we send message $F(x)$ but it received $F'(x) = f(x) + E(x)$. $E(x)$: Error due to some noise.

### Single Bit Error

$E(x) = x^i$ If $G(x)$ has two or more terms, $G(x)$ will not divide $E(x)$.

### Two Isolated single bit errors (double errors)

$E(x) = X^{i+} X^i$, Where $i > J$, $E(x) = x^j(x^{i+j}+1)$ It was found that $G(x)$ is not divisible by $x$, a sufficient condition to detect all double error is $G(x)$ does not divide $(x^i+1)$ for any $t$ up to $i-j$ ( i.e., block length )

### Odd number of Bit Errors

If $(x+1)$ is a factor of $G(x)$ all odd number of bit errors are detected. Let's assume that an odd number of Errors has $x+1$ as a factor. then $E(x) = (x+1)T(x)$, then Evaluate $E(x)$ for $x=1$, then $E(x)= E(1)= 1$ since there are odd number of terms $(x+1) = 1+1 =0$, $(X+1)T(x)=(1+1)T(1) = 0$, $E(x)=(x+1)T(x)$

### Short Burst Errors ((Length $T<=n$, number of redundant bits),

Where $E(x) = x^j (x^{t-1}+....+1)$ length $t$, Start at bit position $J$, if $G(x)$ has an $x^0$ term $t<= n$, $G(x)$ will not divide $E(x)$. So, all errors up to length $n$ are detected.

### Long Burst Errors (Length $T=n+1$)

Undetected able only if burst error is the same as $G(x)$, $G(x) = x^n+....1$, $n-1$ bits is in a position between $x^n$ and $x^0$, $E(x) = 1+....1$, must match probability of not detecting the error is $2^{-(n-1)}$.

### Longer Burst error (length $t >n+1$)

Probability of not detecting the error is $2^{-n}$, number of redundant bits.
## 2.3 Selecting the polynomial generator

Selecting a polynomial for our communication system of limited packet size up to 23 byte is something different as there is a trade of something different between the theoretical analysis and the real field adjustment. Moreover, in real field we have to measure several factors that can impact the system. We are going to use this in our MAC board in a limited memory space and computation power. With the 4 bits long limited space we have the five prime factors $(10)_2 = (X)$, $(11)_2 = (x+1)$, $(111)_2 = x^2+x+1$, $(1011)_2 = x^3+x+1$, and $(1101)_2 = x^3+x^2+1$ that could be used as generator polynomial for our system. A good polynomial generator needs to have the following characteristics:

1. It should have at least two terms.

2. The coefficient of the term $x^0$ should be 1.

3. It should not divide $x^t+1$, for t between 2 and $n-1$.

4. It should have the factor $x+1$.

First 3 are too short and not good enough but the last one decimal value $(13)_{10}$ binary $(1101)_2$ and the polynomial $x^3+x^2+1$ is best among them. As it can detect 3 bits of burst errors and able to detect two different single bit error in a code word. A code word with two isolated errors up to 8 bits apart can be detected by this generator.

$x^3+x^2+1$ is better among others in respect of 4 bit polynomial.

# 3 Considering factor of error detection system for UWASNs

Our main issue is real time data communication in UWASNs. Due to low propagation speed of acoustic signal that causes very large end to end delay. If we can reduce the end-to-end delay then we can improve data throughput from our network. Equations used to our simulations parts.

$$ \text{Data throughput}(\tau) = \frac{\text{Number of original data packets}}{\text{time to successfully send packets}} $$

One end-to-end cycle operation time (€) = number of original data packets / time to successfully send packets. So we want to use nibble size CRC for our UWASN system. It will reduce our pay load size compared to CRC-8, CRC-12, CRC-16, and CRC-32.

## Energy Consumption

In UWASNs the energy is another important factor. The less size payload, less the energy consumes. Though it is very small, it will save small fraction of our energy in every cycle operation. Nibble-CRC consumes less energy than others.

$$ \text{Energy Consumption} = \text{total transmitting time} \times \text{Unit Power} $$
## Transmission Efficiency

In communication system this is the main factor that we pay attention in this paper. For receiving data is only very small as it collect some environmental information of water temperature of the river, P<sub>H</sub> factor and Oxygen (O<sub>2</sub>) level of some particular area.

$$ \text{Transmission Efficiency} = \frac{\text{Information bytes}}{\text{Total bytes}} $$

## High channel error probability

In UWSNs error rate is also very high due to various types of noises, multipath problem and reliable data transport is a great problem. Some recent studies show that the end-to-end approach is in feasible for sensor networks. The high error channel probability makes the probability of successfully transferring data from end to end is uncertain as too many retransmission required for successful data delivery [13-15]. Our nibble CRC will need strong error detection mechanism that can detect errors in a certain level.

Limited hardware infrastructural support likes lower data transmission speed and half duplex operation which is also a cause of slower communication [16-18]. The total time delay from base to sensor required time, usually takes tens of milliseconds [19].

# 4 Performance analysis

Our packet size is 22 byte, modem speed is 200bps and the modem consume 2watt during data transmission and during lasting 0.75watt. Simulation area is 100m by 100m. Sound speed is 1500m/s, also channel error rate 20% for small data packets and 30 to 40% for large data packets.

<figure><img src="image_2.png" /><figcaption>Fig. 1. Payload size with check bits</figcaption></figure>
Our Figure 2 shows that power consumption rate of CRC-4 is lowest among others. Which help the lifespan of the deployed sensors and AUVs.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Power consumption rate of different CRCs</figcaption></figure>

Figure 3 shows power consumption between two sensors in fixed networks. CRC-4 consumes the lowest power in networks.

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 3. Individual power consumption rate of different CRC mechanisms</figcaption></figure>
We illustrate 20 transmission with calculated transmission errors in respect of channel error rate based on small size CRC and large size. CRC32 and CRC64 3~4 times errors. And 2 times for CRC4, CRC8, CRC10 and CRC16. The performances of different type of CRC mechanisms are simulated and it was found that nibble CRC pay load size is the lowest among others. Our proposed nibble CRC, CRC-4 network efficiency rate is also better than others CRC-8 or CRC-16 or CRC-32 bit polynomial. But the error detection rate of our nibble CRC is not so good like CRC-8, CRC-16 or CRC-32 where 99.9984% error detection is possible [20]. But if we compare with RF based networks, (2010 bit: 128 bit) large size payload also ISO and IEEE declared as a standard error detection mechanism CRC-16 and CRC-32 for RF based networks. In underwater, our small size packets nibble size CRC may perform better as high channel error probability and peculiar underwater characteristics. Small amount of energy also can increase the life time of the sensor networks as we cannot recharge our battery.

# 5 Conclusion

In this paper, we try to find out a small size CRC that can be used for small size packet especially for underwater environment. CRC is well suited in the domain of error detection. Previously, we used CRC-8 for our lab experiment in our test bed and real deployment area. We observed our communication system in Han River, Seoul and other one location in Seoul and another city in Busan, Korea, in different distance and different location. We did not face any big difference though we change out location. This is first time we try to find smaller nibble size CRC and in the future we want to observe the performance of error detection rate and the performance of our nibble size CRC how it works in real fields.

# 6 References

1. I. F. Akyildiz, D. Pompili, and T. Melodia, "Challenges for Efficient Communication in Underwater Acoustic Sensor Networks," ACM SIGBED Review, vol. 1, no. 1, July 2004.

2. J.-H. Cui, J. Kong, M. Gerla, and S. Zhou, "Challenges: Building Scalable Mobile Underwater Wireless Sensor Networks for Aquatic Applications," Special Issue of IEEE Network on Wireless Sensor Networking, May 2006.

3. J. Heidemann, W. Ye, J. Wills, A. Syed, and Y. Li., "Research Challenges and Applications for Underwater Sensor Networking," in IEEE Wireless Communications and Networking Conference, Las Vegas, Nevada, USA, April 2006.

4. J. Proakis, E. Sozer, J. A. Rice, and M. Stojanovic, "Shallow Water Acoustic Networks," IEEE Communications Magazines, pp. 114–119, November 2001.

5. G. G. Xie and J. Gibson, "A Networking Protocol for Underwater Acoustic Networks," in Technical Report TR-CS-00-02, Department of Computer Science, Naval Postgraduate School, December 2000.
6. Soonchul Park, Bonggyun Jo and Dong-seog Han, "An Effective Mac Protocol for Data Collection in Underwater wireless sensor networks," Proceeding MILCOM'09 Proceedings of the 28th IEEE conference on Military communications, 2009.

7. Imtiaz Ahmed Khan, Nam-Yeol Yun, Sardorbek Muminov, and Soo-Hyun Park, "A Reliable Error Detection Mechanism in Underwater Acoustic Sensor Networks," Asia Simulation Conference 2011, November 2011.

8. Philip Koopman, Tridib Chakravarty, "Cyclic Redundancy Code (CRC) Polynomial Selection for Embedded Networks" The international Conference on Dependable Systems and Networks, DSN-2004.

9. Lanbo Liu, Shengli Zhou, and Jun-Hong Cui, "Prospects and Problems of Wireless Communication for Underwater Sensor networks," Wiley WCMC Special Issue on Underwater Sensor Networks (INVITED) 2008.

10. Davide Anguita, Davide Brizzolara, Giancarlo Parodi, "Prospects and Problems of Optical Diffuse Wireless Communication for Underwater Wireless Sensor Networks," Wireless Sensor Networks: Application-Centric Design.

11. Peng Xie, Jun-Hong Cui, "An FEC-based Reliable Data Transport Protocol for Underwater Sensor Networks," proceeding of 16th International Conference on Computer communications and networks, ICCCN-2007.

12. Forouzan, B. "Data Communications and Networking," 4th Ed., 2007.

13. L. Freitag, M. Grund, S. Singh, J. Partan, P. Koski, and K. Ball, "The WHOI Micro-Modem: An Acoustic Communications and Navigation System for Multiple Platforms," in IEEE Oceans Conference, Washington DC, 2005.

14. C.-Y. Wan, A. T. Campbell, and L. Krishnamurthy, "PSFQ: A Reliable Transport Protocol for Wireless Sensor Networks," in WSNA'02, Atlanta, Georgia, USA, September 2002.

15. S. Kim, R. Fonseca, and D. Culler, "Reliable Transfer on Wireless Sensor Networks," in Frist IEEE International Conference on Sensor and Ad Hoc Communication and Networks (SECON'04), October 2004.

16. Seung-Won Shin, Nam-Yeol Yun, Hui-Jin Cho, Ji-Eon Kim, Jin-Young Lee, Imtiaz Ahmed Khan, Soo-Hyun Park, "The UMO (Underwater Moving Object) Firmware Design and Implementation Based on Underwater Acoustic Communication", EUC 2011.

17. Nam-Yeol Yun, Yung-Pyo Kim, Sardorbek Muminov, Jin-Young Lee, Soo Young Shin, Soo-Hyun Park, "Sync MAC Protocol to Control Underwater Vehicle Based on Underwater Acoustic Communication", EUC 2011.

18. Yung-Pyo Kim, Jung-Il Namgung, Nam-Yeol Yun, Hui-Jin Cho, Imtiaz Ahmed Khan, Soo-Hyun Park, "Design and Implementation of the Test-bed for Underwater Acoustic Sensor Network Based on ARM9 Processor", EUC 2010.

19. F. Stann and J. Heidemann, "RMST: Reliable Data Transport in Sensor Networks," in First IEEE International Workshop on Sensor Net Protocols and Applications (SNPA), Anchorage, Alaska, USA, May 2003.

20. Imtiaz Ahmed Khan, Nam-Yeol Yun, Sardorbek Muminov, Soo-Hyun Park, Chang-Haw Kim, "A Standard Error Detection Mechanism for Underwater Acoustic Sensor Networks" in the 12th International Conference on Intelligent Autonomous System, (IAS-12) Jeju Island, Korea.