An Error Control Method with Linear Block Code in Sensor Networks

Abstract

An error control method is investigated and obtained by combination of the modulation and linear block code in sensor networks. The constructed coding scheme is multistage decoded using a new low-complexity soft-decision decoding method in sensor networks. Computer simulations of the proposed method are presented and compared with the reunion junction technique. The proposed method shows a better performance than the reunion junction technique. The low complexity of the method allows the use of long linear block codes. It is possible to construct an efficient bandwidth multilevel code on signal set partitioning. A wide range of design tradeoffs are possible with multilevel codes. Composite codes are possible using component codes.

1. Introduction

Sensor networks are composed of battery-supplied small devices. Sensor networks suffer from errors due to random noise and fading, which may increase the bit error rate, cause several retransmissions, and consume extra energy [1]. Sensor networks require reliability of communication while keeping energy efficiency.

In view of reliable communication, many efforts have been made to improve the performance and reduce bit error probability. Zarei and Wu [2] have proposed an energy-efficient error control mechanism based on redundant residue number system for wireless sensor networks. In [3], a scheme to enhance localization in terms of accuracy and transmission overhead in wireless sensor networks has been proposed. In [4], a distributed algorithm is developed to effectively detect, locate, and isolate the Byzantine attackers in a wireless ad hoc network with random linear network coding. Park et al. [5] have suggested an enhanced approach for reliable bulk data transmission of image files, multimedia video files, and successive log files for monitoring systems over wireless sensor networks.

Linear block codes are often used in practical sensor networks to protect the signals. Error control coding is a technique where a code is combined with modulation. In this paper, the concatenation of a block encoder with a modulator containing memory is considered.

A sequential machine [6] is a module which can be modeled as a finite-state sequential circuit. In this paper, there are two cases corresponding to machine. The first one is for a continuous phase modulation signal. The case of partial response baseband channel is the second one. Matched encoding concept [7–9] is based on the observation that for number of states may correspond to the optimum receivers with two different states.

The coding scheme based on a single step partitioning of signal constellations gives an asymptotic gain [10–16] less than 3 dB. The scheme based on a two-step partitioning increases the minimum Euclidean distance by 6 dB. The expansion of the signal constellation may cause a penalty of 1.5 dB. The asymptotic coding gain cannot exceed 4.5 dB.

The purpose of this paper is to propose an error control method. For this method, the maximum number of code words considered and the error performance depend on the set of tested positions. The most likely candidate code word is chosen as decoded one. The soft-decision decoder makes use of the relative magnitudes of the receiver code symbols. For a fixed machine, the encoder corresponds to the tamed frequency modulation (TFM) scheme.

2. An Error Control Method

We consider a scheme with ${\mathrm{2}}^M$ signal point set in sensor networks. Then, the part of a sensor network channel system is expressed as an equivalent channel model based on M subchannel. It is assumed that each subchannel has binary inputs.

The individual subchannels $B_{\mathrm{0}},B_{\mathrm{1}},\dots ,B_{M-\mathrm{1}}$ are discrete channels having different bit error probabilities. The squared Euclidean distance $d_i$ between two binary symbols $y_{ia}$ and $y_{ib}$ is written as

$$\begin{array}{cc}& d_i=\delta \left(y_{ia},y_{ib}\right)·{\Delta }_i^{\mathrm{2}},\end{array}$$

(1)

where $\delta (a,b)$ equals 0 if $a=b$ and 1 if $a\ne b$ and ${\Delta }_i$ is a parameter which is determined by bit error probability in the ith subchannel [5, 8, 17]. A sensor network system uses an (N, K) binary linear block code with minimum distance $d_{\min }$ .

From the sensor network channel, we get two vectors. One is hard-decision vector $\mathbf{z}=(z_{\mathrm{1}},z_{\mathrm{2}},\dots ,z_n)$ and another is reliability information vector $\mathbf{s}=(s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_n)$ . The component $z_i$ is binary number and $s_i$ is nonnegative real number. The larger $s_i$ is, the more reliable $z_i$ is. The decoder uses z and s to determine which code word has been transmitted. The error pattern vector $\mathbf{f}=(f_{\mathrm{1}},f_{\mathrm{2}},\dots ,f_n)$ for an estimated code word $\mathbf{d}=(d_{\mathrm{1}},d_{\mathrm{2}},\dots ,d_n)$ is given by $\mathbf{f}=\mathbf{z}\oplus \mathbf{d}$ , where ⊕ denotes exclusive OR operation. The analog weight of error pattern f is defined as

$$\begin{array}{cc}& V_b\left(\mathbf{f}\right)={\displaystyle \sum }_{i=\mathrm{1}}^N{s}_i{f}_i.\end{array}$$

(2)

The decoder has to select the code word whose error pattern minimizes the analog weight. There are two sufficient conditions that an estimated code word d is optimal. The first sufficient condition of optimality is that the error pattern f for d is zero vector. The first condition is straightforward. When $\mathbf{f}=\mathbf{0}$ , the analog weight of f is 0, which is the minimum value, and it means d is optimal. When $\mathbf{f}\ne \mathbf{0}$ , to examine the second sufficient condition of optimality, we think the error pattern of any other candidate code word.

For linear code, a candidate code word is denoted as $\mathbf{d}\oplus \mathbf{c}$ , where $\mathbf{c}=(c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_n)$ is another nonzero code word. The error pattern for $\mathbf{d}\oplus \mathbf{c}$ is $\mathbf{z}\oplus \mathbf{d}\oplus \mathbf{c}$ which can be simplified as $\mathbf{f}\oplus \mathbf{c}$ because $\mathbf{z}\oplus \mathbf{d}$ is f. We want to find out the condition minimizing the analog weight of $\mathbf{f}\oplus \mathbf{c}$ . The analog weight of $\mathbf{f}\oplus \mathbf{c}$ can be expressed as

$$\begin{array}{cc}& V_b(\mathbf{f}\oplus \mathbf{c})={\displaystyle \sum }_{i=\mathrm{1}}^N{s}_i(f_i\oplus c_i).\end{array}$$

(3)

So we set $c_i=\mathrm{1}$ , for all positions i where $f_i=\mathrm{1}$ .

For linear code, the minimum Hamming distance $d_{\min }$ is also the minimum Hamming weight of any nonzero code word. Let $V_h$ (·) denote Hamming weight of a vector; then $V_h(\mathbf{c})\ge d$ and $V_h(\mathbf{f})\le d/\mathrm{2}$ . Thus, c has at least $[d-V_h(\mathbf{f})]$ 1's for positions i where $f_i=\mathrm{0}$ . So we set $c_i=\mathrm{1}$ , for least reliable $[d-V_h(\mathbf{f})]$ positions i where $f_i=\mathrm{0}$ .

Unreliable position i means small value of $s_i$ . If there exists such a code word c, $\mathbf{f}\oplus \mathbf{c}$ has the minimum analog weight among all error patterns except f. Therefore, the second sufficient condition of optimality is that $V_b(\mathbf{f})\le V_b(\mathbf{f}\oplus \mathbf{c})$ . Starting from a code word d and its error pattern f, we explore other candidate code words. Let ${\mathbf{c}}^x=(b_{\mathrm{1}}^x,b_{\mathrm{2}}^x,\dots ,b_n^x)$ be a vector whose Hamming weight is integer w.

Let $F^m$ denote the set of all binary m-tuples. The entries $(-\mathrm{1}{)}^{u·v}$ , for $u,v\in F^m$ , form a Hadamard matrix of order $n={\mathrm{2}}^m$ . If f is a mapping defined on $F^m$ , its Hadamard transform $\widehat{f}$ is given by

$$\begin{array}{cc}& \widehat{f}\left(u\right)={\displaystyle \sum }_{v\in F^m}^{}{\left(-\mathrm{1}\right)}^{u·v}f\left(v\right).\end{array}$$

(4)

As with Hadamard matrices, we can normalize C by multiplying rows and columns by −1, so that C has the form

$$\begin{array}{cc}& C=\left(\begin{array}{cc}\mathrm{0}& \mathbf{1}\\ \mathbf{1}& S\end{array}\right),\end{array}$$

(5)

where S is a square matrix of order $(n-\mathrm{1})$ satisfying

$$\begin{array}{cc}& S{S}^T=\left(n-\mathrm{1}\right)I-J,\end{array}$$

(6)

$$\begin{array}{cc}& SJ=JS=\mathrm{0}.\end{array}$$

(7)

If C exists, then n must be even. If $n=\mathrm{2}$ , then C can be made symmetric by multiplying rows and columns by −1; while if $n=\mathrm{0}$ , then C can be made skewsymmetric.

Let $C_n$ be a symmetric conference matrix of order n and let C be as in (5). Then the rows of $(S+I+J)$ form a

$$\begin{array}{cc}& \left(n-\mathrm{1,2}n,\frac{\mathrm{1}}{\mathrm{2}}(n-\mathrm{2})\right)\end{array}$$

(8)

nonlinear conference matrix code. That the minimum distance is $(n-\mathrm{1})/\mathrm{2}$ follows easily from (6).

An affine plane of order n is an $S(\mathrm{2},n,n^{\mathrm{2}})$ with $n\ge \mathrm{2}$ . In a $t-(v,k,\lambda )$ design, let $P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_t$ be any t distinct points. Let ${\lambda }_i$ be the number of blocks containing $P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_i$ , for $\mathrm{1}\le i\le t$ and let ${\lambda }_{\mathrm{0}}=b$ be the total number of blocks. Then, ${\lambda }_i$ is independent of the choice of $P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_i$ , and in fact

$$\begin{array}{cc}& {\lambda }_i=\frac{\lambda \left(\begin{array}{c}v-i\\ t-i\end{array}\right)}{\left(\begin{array}{c}k-i\\ t-i\end{array}\right)}.\end{array}$$

(9)

This implies that a $t-(v,k,\lambda )$ design is also an $i-(v,k,{\lambda }_i)$ design.

We set $b_i^x=\mathrm{1}$ , for all positions where $f_i=\mathrm{1}$ and least reliable $[w-x_H(\mathbf{f})]$ positions where $f_i=\mathrm{0}$ . The vector ${\mathbf{c}}^x$ may not be a code word. So, we hard-decision-decode ${\mathbf{c}}^x$ to obtain a code word ${\mathbf{d}}^x$ . So, we obtain a candidate code word $\mathbf{d}\oplus {\mathbf{d}}^x$ and its error pattern $\mathbf{f}\oplus {\mathbf{d}}^x$ . When $w<\lfloor (d-\mathrm{1})/\mathrm{2}\rfloor$ ( $\lfloor x\rfloor$ means the integer part of x), ${\mathbf{d}}^x$ becomes $\mathbf{0}$ . Thus, there is no need to do further decoding for $w<\lfloor (d-\mathrm{1})/\mathrm{2}\rfloor$ .

3. Computer Simulations

Computer simulations of the (64, 42) RM code, the (128, 99) extended BCH code, and the (128, 64) extended BCH code have been performed in order to evaluate their error correction properties. An AWGN channel in sensor networks was assumed for the simulation. Figures 1, 2, 3, 4, 5, and 6 depict results of the (64, 42) RM code, the (128, 99) extended BCH code, and the (128, 64) extended BCH code, respectively.

Figure 1

Bit error probability of (64, 42) RM code.

Figure 2

Bit error probability of (128, 99) extended BCH code.

Figure 3

Bit error probability rate of (128, 64) extended BCH code.

Figure 4

The calculation amount of (64, 42) RM code.

Figure 5

The calculation amount of (128, 99) extended BCH code.

Figure 6

The calculation amount of (128, 64) extended BCH code.

For each code, the simulated result of the proposed transform matching evaluation (TME) method is plotted and compared with that of the reunion junction (RJ) technique. It should be noted here that the structural conditions on the pattern of connections have been found. The structural conditions are necessary and sufficient conditions for an encoder to be matched. However, since such conditions must be individually determined for each CPM modulator and each code rate considered, their use is limited.

4. Conclusion

The construction of the transform matching evaluation method has been proposed. The proposed method shows a better performance than the reunion junction technique. The low complexity of the method allows the use of long linear block codes in sensor networks.

It should be noted here that the structural conditions on the pattern of connections have been found. The structural conditions are necessary and sufficient conditions for an encoder to be matched. Such conditions must be individually determined for each CPM modulator and each code rate in sensor networks.

For this method, the maximum number of code words considered and the error performance depend on the set of tested positions in sensor networks. The most likely candidate code word is chosen as decoded one. The soft-decision decoder makes use of the relative magnitudes of the receiver code symbols. For a fixed machine, the encoder corresponds to the tamed frequency modulation scheme.

It is possible to construct an efficient bandwidth multilevel code on signal set partitioning. A wide range of design tradeoffs are possible with multilevel codes. Composite codes are also possible by using component codes.