# IDMA-Based Compressed Sensing for Ocean Monitoring Information Acquisition with Sensor Networks

Authors: Gongliang Liu; Wenjing Kang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The ocean monitoring sensor network is a typically energy-limited and bandwidth-limited system, and the technical bottleneck of which is the asymmetry between the demand for large-scale and high-resolution information acquisition and the limited network resources. The newly arising compressed sensing theory provides a chance for breaking through the bottleneck. In view of this and considering the potential advantages of the emerging interleave-division multiple access (IDMA) technology in underwater channels, this paper proposes an IDMA-based compressed sensing scheme in underwater sensor networks with applications to environmental monitoring information acquisition. Exploiting the sparse property of the monitored objects, only a subset of sensors is required to measure and transmit the measurements to the monitoring center for accurate information reconstruction, reducing the requirements for channel bandwidth and energy consumption significantly. Furthermore, with the aid of the semianalytical technique of IDMA, the optimal sensing probability of each sensor is determined to minimize the reconstruction error of the information map. Simulation results with real oceanic monitoring data validate the efficiency of the proposed scheme.


---

## Body

## 1. Introduction

With the ever-increasing demand for marine exploitation and the rapid development of network communication technologies, underwater sensor network (UWSN) [1] has become a new research hotspot in recent years. As the extension of wireless sensor networks (WSN) into ocean, UWSN has potential values in the wide application fields, such as oceanographic information collection, hydrological and environmental monitoring, resources exploration, disaster forecast, underwater navigation, and military defense. This paper focuses on the ocean environmental monitoring application. In this kind of UWSN, a large number of underwater sensor nodes are deployed in the concerned area, which measure the required physical, chemical, or biological phenomena and transmit the measurements to the monitoring center. Then, the monitoring center forms the information map of the monitoring area according to the measurements it received. Due to the particularity of underwater environments [2], wireless acoustic communication is believed as the most suitable physical layer transmission technology in underwater networks. However, wireless acoustic communication has some distinct disadvantages in the following aspects: (
1
) low carrier frequency leads to limited available bandwidth; (
2
) low propagation speed of sound leads to long end-to-end delay. Furthermore, considering the application environment of UWSN, the batteries of sensor nodes can hardly be replaced. According to the above analysis, UWSN is believed to be a typical energy-limited and bandwidth-limited system.In order to distinguish the measurements of different sensors from each other, the multiple access scheme is an important issue in underwater sensor networks, as well as in other communication systems with multiple users. Time-division multiple access (TDMA) is a popular scheme in the existing underwater networks, but it has some insurmountable disadvantages.(
1
) TDMA scheme is based on the accurate synchronization. The long propagation delay and large amount of sensors bring great difficulties for the timing system, especially when the system has a large number of sensors. (
2
) TDMA mechanism has feeblish capability against interference and multipath fading and cannot accommodate to the complicated and time-varying underwater environment. (
3
) The capacity of TDMA system is restricted by the factors such as frame architecture and channel rate. Hence, the network scale is difficult to be extended. In recent years, code-division multiple access (CDMA) has been regarded as the promising multiple access scheme for underwater sensor networks. With the aid of multiuser detection (MUD) technologies, CDMA outperforms TDMA in the aspects of frequency utilization, feasibility, multiple access interference (MAI) suppression capability, and immunity against multipath effects. However, most of the MUD algorithms have high-computational complexity, and the detection cost increases greatly with the amount of sensor nodes. Therefore, a simple and efficient multiple access scheme is required for the large-scale underwater sensor networks. This requirement is expected to be realized with the emergence of interleave-division multiple access (IDMA) [3] technology.IDMA is a relative new multiple access scheme, which employs random interleavers as the only method for user separation. As a particular case of CDMA, IDMA inherits many distinguished features of the well-studied CDMA. Furthermore, it allows a low-cost turbo-type chip-by-chip (CBC) multiuser detection (MUD) algorithm applicable to system with a large number of users, which is crucial for the large-scale underwater sensor networks.With applications to wide area ocean monitoring, underwater sensor networks are usually required to deploy a large amount of sensor nodes in the concerned region. Due to the rigorous limitations on bandwidth and energy of the underwater sensor networks, there is an asymmetry between the requirement for high-rate sampling and the restricted network resources. This becomes the technical bottleneck of developing a practical large-scale underwater sensor network for ocean monitoring. The traditional information acquisition methods cannot solve the above problem, while the newly arising compressed sensing (CS) technology [4–6] provides a potentially reasonable solution. Different from the traditional Nyquist sampling theory, the CS theory is concerned more with the information structure rather than the signal bandwidth. According to the CS theory, if a signal is sparse or compressible in a certain domain (e.g., spatial domain or frequency domain), it can be accurately reconstructed from a small number of nonadaptive, randomized linear projection measurements by solving an optimization problem.Fortunately, most of the nature phenomena are sparse in an appropriate basis, so the sparsity of the nature phenomena provides the feasibility to widely apply CS theory into practical engineering field. In the last few years, the researchers have attempted to utilize CS technology in the aspects of wireless communications [7], image processing [8], compressive radar [9], and so on. To the best of our knowledge, [10] is the first attempt for CS-based network data processing, which is followed by a series of influential work. References [11, 12] investigate the routing issue in wireless networks under the framework of compressed sensing. Reference [13] focuses on the CS-based target detection scheme in wireless sensor networks, where the observed signal is spatially sparse. A compressed sensing framework for on-off random access channels is provided in [14], and the theoretical bounds for channel capacity are given after thorough derivation. In [15], authors proposed an energy-efficient random access compressed sensing (RACS) scheme for underwater sensor networks, which is the most important work for applying CS theory into underwater sensor networks so far. However, the authors of [15] did not take the effect of channel error into consideration, which is in fact a crucial issue affecting the quality of reconstructed information map. Reference [16] proposed a CS-based multiple access control (MAC) scheme and provided the in-depth analysis from a physical layer perspective. However, the effects of multiple access interference (MAI) are not considered in this paper. In our previous work of [17], we have proposed a novel CS-based information collection scheme for the large-scale underwater networks, which realized accurate “information collection” for the large-scale underwater sensor network with a reduced number of measurements, instead of the traditional “data collection” methods. However, this scheme is based on the traditional TDMA technology, which has some insurmountable disadvantages as mentioned above. Moreover, [17] did not consider the issue of optimal sensing probability. These problems will be solved in this paper.Inspired by the theory of compressed sensing and the above extensive applications, in this paper, we propose an IDMA-based compressed sensing information acquisition scheme for the large-scale underwater sensor networks. After a subrate sampling step with the random selected sensor nodes, the measurements are transmitted to the monitoring center through the underwater multiple access channel (MAC) with IDMA method. Then, the monitoring center distinguishes the reduced-dimensional measurements from each other with online CBC MUD. Finally, the monitoring center reconstructs the information map according to the output of MUD. On the framework of compressed sensing and by the aid of signal-to-interference-plus-noise ratio (SINR) evolution semianalytical technique of IDMA, we further investigate the problem of optimal sensing probability at each sensor, with which the minimal reconstruction error will be achieved. To the best of our knowledge, our work introduced compressed sensing into the IDMA system for the first time, and we made the first attempt in studying the optimal sensing probability of CS-based information acquisition scheme by exploiting the advantages of the specific SINR evolution semianalytical technique of IDMA system.The remainder of this paper is organized as follows. In Section2, the system model and problem description are given. After introducing the mathematical foundations of compressed sensing and IDMA in Section 3, the CS-IDMA scheme is proposed in Section 4. Then, thorough analytical observations on reconstruction error and resource requirements of our scheme are given in Section 5. In Section 6, simulation results and performance evaluation are provided to validate the proposed scheme. Finally, the paper concludes in Section 7.


## 2. System Model and Problem Description

Consider a 2-dimensional underwater monitoring area, withL sensor nodes in x direction and Wsensor nodes in y direction, as shown in Figure 1. The sensors are regularly deployed to collect some kinds of ocean monitoring elements, such as temperature, salinity, and ocean current, and transmit the measurements to the monitoring center by one hop. The distance between two neighbor nodes is D, the both in x and y directions. The monitored plane where the sensor is located is H (meters) under the ocean surface.Figure 1
Two-dimensional underwater sensor network for ocean monitoring applications.In this paper, the simple single-path multiple access underwater channel model is taken into consideration. Suppose ideal power control is adopted and the required power of each sensor at the receiver side (sink node) isP
0, the distance between the sender and the receiver is d (km), and the carrier frequency is f (kHz). In order to achieve the required BER, the transmitted power should be P
0
·
A
(
d
,
f
), where
(1)
A
(
d
,
f
)
=
d
c
·
a
(
f
)
d
.
The constant c is usually set as 1.5, and
(2)
a
(
f
)
=
1
0
α
(
f
)
/
10
,
where α
(
f
) is the absorption coefficient, with an experiential formula as follows [18]:
(3)
α
(
f
)
=
0.11
f
2
1
+
f
2
+
44
f
2
4100
+
f
2
+
2.75
f
2
1
0
4
+
0.003
.For such an ocean monitoring application, the traditional method is to collect the measurements from all sensors to form an information map about certain characteristic, for example, temperature, salinity, or ocean current. However, with the augment of network scale, more sensors are required to measure and transmit together, leading to a burdensome energy consumption and bandwidth cost. Furthermore, in a quasi-orthogonal network, such as a CDMA or IDMA network, the performance of bit error rate (BER) and packet error rate (PER) will turn worse significantly when the number of nodes increases. Although a long spread sequence is helpful for interference suppression, it leads to higher demand for the channel bandwidth, which is severely limited in the underwater sensor networks. In view of the above facts, this paper aims to find an efficient information acquisition approach for the large-scale ocean monitoring underwater sensor networks as shown in Figure1. As an emerging information sample theory, compressed sensing provides a novel perspective to the potential solution.


## 3. Preliminaries

### 3.1. Mathematical Foundation of Compressed Sensing

The core of CS theory is briefly expressed as follows [4]: consider a discrete signal X
=
[
x
1
,
x
2
,
…
,
x
n
]
T, which is an n
×
1 vector; that is, X
∈
ℝ
n. According to the compressed sensing theory, if X is sparse or compressible in a certain transform domain, it can be accurately recovered from a compressed measurement Y
=
[
y
1
,
y
2
,
…
,
y
m
]
T, which is an m
×
1 vector, m
≪
n. The framework of compressed sensing theory mainly consists of three steps: (
1
) sparse transformation, (
2
) reduced-dimensional observation, and (
3
) signal recovery.Sparse Transformation. Suppose the original signal X
∈
ℝ
n is s-sparse (
s
≤
n
) on the orthogonal basis of  Ψ
,
Ψ
:
=
[
Ψ
1
,
Ψ
2
,
…
,
Ψ
n
], where Ψ
i
∈
ℝ
n, i
=
1
,
2
,
…
,
n. As shown in (4), X can be expressed as the linear combination of a subset of basis vector:
(4)
X
=
∑
i
=
1
n
θ
(
i
)
Ψ
i
=
∑
l
=
1
s
θ
(
i
l
)
Ψ
i
l
,
where {
i
l
} is the set of serial number with the selected basis vectors. The n
×
1 transform coefficient vector, Θ
=
Ψ
T
X, is the sparse representation of X, which has s none-zero elements.Reduced-Dimensional Observation. Design an m
×
n (m
≪
n) independent identically distributed (i.i.d.) matrix Φ, which is independent from Ψ. Using Φ, an m-length measurement vector is obtained by
(5)
Y
=
Φ
Θ
=
Φ
Ψ
T
X
=
R
X
,
where R
=
Φ
Ψ
T is the CS matrix from X to Y.Signal Reconstruction. The last step of compressed sensing is to recover the original n-length signal X from the compressed m-length measurement vector Y. Because m is smaller than n, (5) is originally undetermined and has no unique definite solution. However, the s-sparsity characteristic of X makes the signal reconstruction realizable. If the matrix R or Φ satisfies the restricted isometry property (RIP) [5], the original signal X can be recovered from the compressed measurement Y by solving the following optimization problem:
(6)
arg
min
∥
Ψ
T
X
∥
1
subject
to
Y
=
R
X
,
where ∥
Ψ
T
X
∥
1
=
∥
Θ
∥
1
=
∑
i
=
1
n
θ
i denotes the ℓ
1-norm of Θ.In the application of ocean monitoring with underwater sensor networks, the ultimate purpose is to acquire the concerned information of the monitored area by means of data collection and transmission. Because most of the ocean elements (temperature, ocean current, etc.) are sparse in an appropriate domain (such as Fourier domain), it is realizable to reconstruct the information map with reduced measurements under the theoretical framework of compressed sensing.


### 3.2. Interleave-Division Multiple Access

IDMA is a relatively new multiple access scheme, in which user-specific interleavers are adopted as the only method for user separation. Compared to CDMA, it has smaller MUD complexity and higher bandwidth utilization and power efficiency. In view of this, IDMA is a promising candidate for the resource-limited underwater sensor networks and is adopted in the uplink channels for the random selected underwater sensors in our scheme. As the background of our work, here we first elaborate on the concept of IDMA [3].


#### 3.2.1. IDMA Model and CBC Algorithm

In this study, the IDMA-CBC MUD channel model and its operational principles are confined to single-path synchronous channel and BPSK modulation. Figure2 illustrates the generic transmitter and the IDMA-CBC MUD receiver with K simultaneous users. The input data sequence of user-k is first encoded by a forward error correction (FEC) code. After spreading, the respective chips are interleaved by user-specific interleaver π
k, producing x
k
≡
[
x
k
(
1
)
,
…
,
x
k
(
j
)
,
…
,
x
k
(
J
)
]. The main difference between CDMA and IDMA at the transmitter side is the position exchange of spreader and interleaver, leading to chip-level interleaving for IDMA and bit-level interleaving for the CDMA. Compared with CDMA, the distinguished feature of IDMA is that different interleavers are used to separate signals from different users. Thus, the adjacent chips from the same users are approximately uncorrelated, which facilitates the simple chip-by-chip multiuser detection scheme discussed below.Figure 2
Transmitter and receiver structure of IDMA.As illustrated in Figure2, an iterative suboptimal receiver structure is adopted, consisting of an elementary signal estimator (ESE) and K single-user a posterioriprobability decoders (DECs). In the global turbo-type iterative process, the ESE and DECs exchange extrinsic log-likelihood ratios (LLRs) about {
x
k
(
j
)
}, defined as follows:
(7)
e
(
x
k
(
j
)
)
≡
log
(
Pr
(
y
∣
x
k
(
j
)
=
+
1
)
Pr
(
y
∣
x
k
(
j
)
=
-
1
)
)
,
∀
k
,
j
.The CBC MUD algorithm contains two parts, listed as follows [3].(1
) The basic ESE function. The j
t
h received chip from K users can be written as
(8)
r
(
j
)
=
h
k
x
k
(
j
)
+
ζ
k
(
j
)
with
(9)
ζ
k
(
j
)
=
∑
k
′
=
1
k
′
≠
k
K
h
k
′
x
k
′
(
j
)
+
n
(
j
)
,
where ζ
k
(
j
) is the distortion (including interference-plus-noise) with respect to user-k, h
k is a priori channel coefficient at the receiver side, and n
(
j
) is sample of an AWGN with variance σ
2
=
N
0
/
2.Step i.
Estimation of interference mean and variance:(10)
E
(
r
(
j
)
)
=
∑
k
=
1
K
h
k
E
(
x
k
(
j
)
)
,
∀
j
Var
(
r
(
j
)
)
=
∑
k
=
1
K
|
h
k
|
2
Var
(
x
k
(
j
)
)
+
σ
2
,
∀
j
E
(
ζ
k
(
j
)
)
=
E
(
r
(
j
)
)
-
h
k
E
(
x
k
(
j
)
)
,
∀
k
,
j
Var
(
ζ
k
(
j
)
)
=
Var
(
r
(
j
)
)
-
|
h
k
|
2
Var
(
x
k
(
j
)
)
,
∀
k
,
jStep ii. LLR generation:
(11)
e
ESE
(
x
k
(
j
)
)
=
2
h
k
·
r
(
j
)
-
E
(
ζ
k
(
j
)
)
Var
(
ζ
k
(
j
)
)
,
∀
k
,
j
.(2)The DEC Function. The DECs in Figure 2 implement APP decoding with the output of the ESE as the input. Their output is the extrinsic LLRs e
DEC
(
x
k
(
j
)
), generating the following statistics:
(12)
E
(
x
k
(
j
)
)
=
tanh
(
e
DEC
(
x
k
(
j
)
)
2
)
,
Var
(
x
k
(
j
)
)
=
1
-
(
E
(
x
k
(
j
)
)
)
2
.As discussed above,{
E
(
x
k
(
j
)
)
} and {
Var
(
x
k
(
j
)
)
} will be used in the ESE to update the interference mean and variance in the next iteration. APP decoding is a standard operation; thus, we will not discuss it in detail.The DEC cost is dominated by the APP decoding cost. Compared with CDMA, the extra cost the MUD described above is mainly related to the ESE, while it costs seven multiplications and five additions per coded bit per user in the ESE, which is very modest. Thus, the overall complexity of the multiuser detector can be roughly comparable to that of a single-user one. This is considerably lower than those of other schemes, for example, the well-known MMSE algorithm with a complexity ofO
(
K
2
) and the MAP MUD algorithm with a complexity of O
(
2
K
).


#### 3.2.2. Performance Comparison between IDMA and CDMA

It is interesting to compare the performance of IDMA and CDMA using the same detection algorithm. Figure3 illustrates such performance comparison for different number of users with the same spreading length L
=
15. For CDMA, m-sequence is employed as the spreading sequence, while for IDMA, [
+
1
,
-
1
,
+
1
,
-
1
,
…
] is adopted. The length of the information block is N
=
1500. As we can see, the performance advantage of IDMA increases with the number of users. When the number of users is small, the performance of IDMA and CDMA is almost the same. However, the performance of CDMA becomes worse when the number of users is larger than 15. IDMA can achieve near single-user performance even for K
=
24. Thus, compared with CDMA, IDMA can achieve better performance with low computational cost.Figure 3
Performance comparison between IDMA and CDMA systems.


## 3.1. Mathematical Foundation of Compressed Sensing

The core of CS theory is briefly expressed as follows [4]: consider a discrete signal X
=
[
x
1
,
x
2
,
…
,
x
n
]
T, which is an n
×
1 vector; that is, X
∈
ℝ
n. According to the compressed sensing theory, if X is sparse or compressible in a certain transform domain, it can be accurately recovered from a compressed measurement Y
=
[
y
1
,
y
2
,
…
,
y
m
]
T, which is an m
×
1 vector, m
≪
n. The framework of compressed sensing theory mainly consists of three steps: (
1
) sparse transformation, (
2
) reduced-dimensional observation, and (
3
) signal recovery.Sparse Transformation. Suppose the original signal X
∈
ℝ
n is s-sparse (
s
≤
n
) on the orthogonal basis of  Ψ
,
Ψ
:
=
[
Ψ
1
,
Ψ
2
,
…
,
Ψ
n
], where Ψ
i
∈
ℝ
n, i
=
1
,
2
,
…
,
n. As shown in (4), X can be expressed as the linear combination of a subset of basis vector:
(4)
X
=
∑
i
=
1
n
θ
(
i
)
Ψ
i
=
∑
l
=
1
s
θ
(
i
l
)
Ψ
i
l
,
where {
i
l
} is the set of serial number with the selected basis vectors. The n
×
1 transform coefficient vector, Θ
=
Ψ
T
X, is the sparse representation of X, which has s none-zero elements.Reduced-Dimensional Observation. Design an m
×
n (m
≪
n) independent identically distributed (i.i.d.) matrix Φ, which is independent from Ψ. Using Φ, an m-length measurement vector is obtained by
(5)
Y
=
Φ
Θ
=
Φ
Ψ
T
X
=
R
X
,
where R
=
Φ
Ψ
T is the CS matrix from X to Y.Signal Reconstruction. The last step of compressed sensing is to recover the original n-length signal X from the compressed m-length measurement vector Y. Because m is smaller than n, (5) is originally undetermined and has no unique definite solution. However, the s-sparsity characteristic of X makes the signal reconstruction realizable. If the matrix R or Φ satisfies the restricted isometry property (RIP) [5], the original signal X can be recovered from the compressed measurement Y by solving the following optimization problem:
(6)
arg
min
∥
Ψ
T
X
∥
1
subject
to
Y
=
R
X
,
where ∥
Ψ
T
X
∥
1
=
∥
Θ
∥
1
=
∑
i
=
1
n
θ
i denotes the ℓ
1-norm of Θ.In the application of ocean monitoring with underwater sensor networks, the ultimate purpose is to acquire the concerned information of the monitored area by means of data collection and transmission. Because most of the ocean elements (temperature, ocean current, etc.) are sparse in an appropriate domain (such as Fourier domain), it is realizable to reconstruct the information map with reduced measurements under the theoretical framework of compressed sensing.


## 3.2. Interleave-Division Multiple Access

IDMA is a relatively new multiple access scheme, in which user-specific interleavers are adopted as the only method for user separation. Compared to CDMA, it has smaller MUD complexity and higher bandwidth utilization and power efficiency. In view of this, IDMA is a promising candidate for the resource-limited underwater sensor networks and is adopted in the uplink channels for the random selected underwater sensors in our scheme. As the background of our work, here we first elaborate on the concept of IDMA [3].


### 3.2.1. IDMA Model and CBC Algorithm

In this study, the IDMA-CBC MUD channel model and its operational principles are confined to single-path synchronous channel and BPSK modulation. Figure2 illustrates the generic transmitter and the IDMA-CBC MUD receiver with K simultaneous users. The input data sequence of user-k is first encoded by a forward error correction (FEC) code. After spreading, the respective chips are interleaved by user-specific interleaver π
k, producing x
k
≡
[
x
k
(
1
)
,
…
,
x
k
(
j
)
,
…
,
x
k
(
J
)
]. The main difference between CDMA and IDMA at the transmitter side is the position exchange of spreader and interleaver, leading to chip-level interleaving for IDMA and bit-level interleaving for the CDMA. Compared with CDMA, the distinguished feature of IDMA is that different interleavers are used to separate signals from different users. Thus, the adjacent chips from the same users are approximately uncorrelated, which facilitates the simple chip-by-chip multiuser detection scheme discussed below.Figure 2
Transmitter and receiver structure of IDMA.As illustrated in Figure2, an iterative suboptimal receiver structure is adopted, consisting of an elementary signal estimator (ESE) and K single-user a posterioriprobability decoders (DECs). In the global turbo-type iterative process, the ESE and DECs exchange extrinsic log-likelihood ratios (LLRs) about {
x
k
(
j
)
}, defined as follows:
(7)
e
(
x
k
(
j
)
)
≡
log
(
Pr
(
y
∣
x
k
(
j
)
=
+
1
)
Pr
(
y
∣
x
k
(
j
)
=
-
1
)
)
,
∀
k
,
j
.The CBC MUD algorithm contains two parts, listed as follows [3].(1
) The basic ESE function. The j
t
h received chip from K users can be written as
(8)
r
(
j
)
=
h
k
x
k
(
j
)
+
ζ
k
(
j
)
with
(9)
ζ
k
(
j
)
=
∑
k
′
=
1
k
′
≠
k
K
h
k
′
x
k
′
(
j
)
+
n
(
j
)
,
where ζ
k
(
j
) is the distortion (including interference-plus-noise) with respect to user-k, h
k is a priori channel coefficient at the receiver side, and n
(
j
) is sample of an AWGN with variance σ
2
=
N
0
/
2.Step i.
Estimation of interference mean and variance:(10)
E
(
r
(
j
)
)
=
∑
k
=
1
K
h
k
E
(
x
k
(
j
)
)
,
∀
j
Var
(
r
(
j
)
)
=
∑
k
=
1
K
|
h
k
|
2
Var
(
x
k
(
j
)
)
+
σ
2
,
∀
j
E
(
ζ
k
(
j
)
)
=
E
(
r
(
j
)
)
-
h
k
E
(
x
k
(
j
)
)
,
∀
k
,
j
Var
(
ζ
k
(
j
)
)
=
Var
(
r
(
j
)
)
-
|
h
k
|
2
Var
(
x
k
(
j
)
)
,
∀
k
,
jStep ii. LLR generation:
(11)
e
ESE
(
x
k
(
j
)
)
=
2
h
k
·
r
(
j
)
-
E
(
ζ
k
(
j
)
)
Var
(
ζ
k
(
j
)
)
,
∀
k
,
j
.(2)The DEC Function. The DECs in Figure 2 implement APP decoding with the output of the ESE as the input. Their output is the extrinsic LLRs e
DEC
(
x
k
(
j
)
), generating the following statistics:
(12)
E
(
x
k
(
j
)
)
=
tanh
(
e
DEC
(
x
k
(
j
)
)
2
)
,
Var
(
x
k
(
j
)
)
=
1
-
(
E
(
x
k
(
j
)
)
)
2
.As discussed above,{
E
(
x
k
(
j
)
)
} and {
Var
(
x
k
(
j
)
)
} will be used in the ESE to update the interference mean and variance in the next iteration. APP decoding is a standard operation; thus, we will not discuss it in detail.The DEC cost is dominated by the APP decoding cost. Compared with CDMA, the extra cost the MUD described above is mainly related to the ESE, while it costs seven multiplications and five additions per coded bit per user in the ESE, which is very modest. Thus, the overall complexity of the multiuser detector can be roughly comparable to that of a single-user one. This is considerably lower than those of other schemes, for example, the well-known MMSE algorithm with a complexity ofO
(
K
2
) and the MAP MUD algorithm with a complexity of O
(
2
K
).


### 3.2.2. Performance Comparison between IDMA and CDMA

It is interesting to compare the performance of IDMA and CDMA using the same detection algorithm. Figure3 illustrates such performance comparison for different number of users with the same spreading length L
=
15. For CDMA, m-sequence is employed as the spreading sequence, while for IDMA, [
+
1
,
-
1
,
+
1
,
-
1
,
…
] is adopted. The length of the information block is N
=
1500. As we can see, the performance advantage of IDMA increases with the number of users. When the number of users is small, the performance of IDMA and CDMA is almost the same. However, the performance of CDMA becomes worse when the number of users is larger than 15. IDMA can achieve near single-user performance even for K
=
24. Thus, compared with CDMA, IDMA can achieve better performance with low computational cost.Figure 3
Performance comparison between IDMA and CDMA systems.


## 3.2.1. IDMA Model and CBC Algorithm

In this study, the IDMA-CBC MUD channel model and its operational principles are confined to single-path synchronous channel and BPSK modulation. Figure2 illustrates the generic transmitter and the IDMA-CBC MUD receiver with K simultaneous users. The input data sequence of user-k is first encoded by a forward error correction (FEC) code. After spreading, the respective chips are interleaved by user-specific interleaver π
k, producing x
k
≡
[
x
k
(
1
)
,
…
,
x
k
(
j
)
,
…
,
x
k
(
J
)
]. The main difference between CDMA and IDMA at the transmitter side is the position exchange of spreader and interleaver, leading to chip-level interleaving for IDMA and bit-level interleaving for the CDMA. Compared with CDMA, the distinguished feature of IDMA is that different interleavers are used to separate signals from different users. Thus, the adjacent chips from the same users are approximately uncorrelated, which facilitates the simple chip-by-chip multiuser detection scheme discussed below.Figure 2
Transmitter and receiver structure of IDMA.As illustrated in Figure2, an iterative suboptimal receiver structure is adopted, consisting of an elementary signal estimator (ESE) and K single-user a posterioriprobability decoders (DECs). In the global turbo-type iterative process, the ESE and DECs exchange extrinsic log-likelihood ratios (LLRs) about {
x
k
(
j
)
}, defined as follows:
(7)
e
(
x
k
(
j
)
)
≡
log
(
Pr
(
y
∣
x
k
(
j
)
=
+
1
)
Pr
(
y
∣
x
k
(
j
)
=
-
1
)
)
,
∀
k
,
j
.The CBC MUD algorithm contains two parts, listed as follows [3].(1
) The basic ESE function. The j
t
h received chip from K users can be written as
(8)
r
(
j
)
=
h
k
x
k
(
j
)
+
ζ
k
(
j
)
with
(9)
ζ
k
(
j
)
=
∑
k
′
=
1
k
′
≠
k
K
h
k
′
x
k
′
(
j
)
+
n
(
j
)
,
where ζ
k
(
j
) is the distortion (including interference-plus-noise) with respect to user-k, h
k is a priori channel coefficient at the receiver side, and n
(
j
) is sample of an AWGN with variance σ
2
=
N
0
/
2.Step i.
Estimation of interference mean and variance:(10)
E
(
r
(
j
)
)
=
∑
k
=
1
K
h
k
E
(
x
k
(
j
)
)
,
∀
j
Var
(
r
(
j
)
)
=
∑
k
=
1
K
|
h
k
|
2
Var
(
x
k
(
j
)
)
+
σ
2
,
∀
j
E
(
ζ
k
(
j
)
)
=
E
(
r
(
j
)
)
-
h
k
E
(
x
k
(
j
)
)
,
∀
k
,
j
Var
(
ζ
k
(
j
)
)
=
Var
(
r
(
j
)
)
-
|
h
k
|
2
Var
(
x
k
(
j
)
)
,
∀
k
,
jStep ii. LLR generation:
(11)
e
ESE
(
x
k
(
j
)
)
=
2
h
k
·
r
(
j
)
-
E
(
ζ
k
(
j
)
)
Var
(
ζ
k
(
j
)
)
,
∀
k
,
j
.(2)The DEC Function. The DECs in Figure 2 implement APP decoding with the output of the ESE as the input. Their output is the extrinsic LLRs e
DEC
(
x
k
(
j
)
), generating the following statistics:
(12)
E
(
x
k
(
j
)
)
=
tanh
(
e
DEC
(
x
k
(
j
)
)
2
)
,
Var
(
x
k
(
j
)
)
=
1
-
(
E
(
x
k
(
j
)
)
)
2
.As discussed above,{
E
(
x
k
(
j
)
)
} and {
Var
(
x
k
(
j
)
)
} will be used in the ESE to update the interference mean and variance in the next iteration. APP decoding is a standard operation; thus, we will not discuss it in detail.The DEC cost is dominated by the APP decoding cost. Compared with CDMA, the extra cost the MUD described above is mainly related to the ESE, while it costs seven multiplications and five additions per coded bit per user in the ESE, which is very modest. Thus, the overall complexity of the multiuser detector can be roughly comparable to that of a single-user one. This is considerably lower than those of other schemes, for example, the well-known MMSE algorithm with a complexity ofO
(
K
2
) and the MAP MUD algorithm with a complexity of O
(
2
K
).


## 3.2.2. Performance Comparison between IDMA and CDMA

It is interesting to compare the performance of IDMA and CDMA using the same detection algorithm. Figure3 illustrates such performance comparison for different number of users with the same spreading length L
=
15. For CDMA, m-sequence is employed as the spreading sequence, while for IDMA, [
+
1
,
-
1
,
+
1
,
-
1
,
…
] is adopted. The length of the information block is N
=
1500. As we can see, the performance advantage of IDMA increases with the number of users. When the number of users is small, the performance of IDMA and CDMA is almost the same. However, the performance of CDMA becomes worse when the number of users is larger than 15. IDMA can achieve near single-user performance even for K
=
24. Thus, compared with CDMA, IDMA can achieve better performance with low computational cost.Figure 3
Performance comparison between IDMA and CDMA systems.


## 4. IDMA-Based Compressed Sensing Information Acquisition Scheme

In this section, the IDMA-based compressed sensing (CS-IDMA) information acquisition scheme is proposed and illustrated for the large-scale ocean monitoring underwater sensor networks.The framework of the proposed scheme is simple and clear. As shown in Figure4, the proposed scheme consists of three main components: (
1
) data sensing with randomly selected sensors; (
2
) interleave-division multiple access to the monitoring center over noisy channels; (
3
) information recovery with the available measurements. Under the compressed sensing framework, the procedure of random sampling and the following multiple access is mapped to the mathematical operation of reduced-dimensional observation. The performance of IDMA multiuser detection determines the precision of the reconstructed information map.Figure 4
CS-IDMA framework.


### 4.1. Random Sensing at Sensor Side

In order to prolong the lifetime of the underwater sensor networks, in each monitoring round only a subset of the sensor nodes is randomly selected to make sensing and transmit the measurement to the monitoring center. The number of active nodes in one round is determined by a parameter named sensing probabilityp.According to the compressed sensing theory, in order to realize accurate recovery, the sensing matrixR should satisfy two basic conditions: the independency between R and Ψ and the RIP property. The commonly used sensing matrixes include random Gaussian matrix, random Bernoulli matrix, and partial Hadamard matrix. However, they cannot contribute to energy and bandwidth saving for the considered scenario. In view of this, a simple and efficient sensing matrix, random extractive matrix, is used in this paper. The random extractive matrix is easily formed by randomly selecting m rows from the n
×
n identity matrix, where n is the number of sensors in the monitored area and m is the number of the selected sensors in one round. The elements in the random extractive matrix have the following property:
(13)
∑
i
=
1
m
r
i
j
≤
1
,
j
=
1,2
,
…
,
n
,
∑
j
=
1
n
r
i
j
=
1
,
i
=
1,2
,
…
,
m
.


### 4.2. Interleave-Division Multiple Access over Noisy Channels

Suppose there areN underwater sensor nodes deployed in the monitoring area. In one round of information acquisition, each node performs measurement with probability p. Then, the random K
=
p
N measurements will be transmitted to the monitoring center simultaneously. In this study, IDMA is employed to distinguish the measurements from each other.Compared to CDMA, the transmitter of IDMA system exchanges the sequence of the spreader and interleaver; that is, it employs a chip-level interleaver to randomize the chip-level information. Consequently, the MAI in IDMA system can be regarded as the additive Gaussian white noise (AWGN), which is not reasonable in the traditional CDMA system. Similar to Turbo decoding, IDMA-CBC MUD is an iterative procedure with two decoding components, namely, an elementary signal estimator (ESE) andK a posteriori probability (APP) decoders (DECs). During each iteration, they exchange extrinsic log-likelihood ratios (LLRs) about x
k
(
j
), which is the j
t
h chip output from the user-k dependent permutation. From the central limited theorem, the MAI of every chip is reasonably approximated by a Gaussian distribution. Furthermore, the key principle of IDMA is that the user separation is made possible by using different interleavers invoked after the spreading, and chip-level interleaving makes MAI appear as an additive uncorrelated Gaussian process. Based on the above assumptions, the extrinsic LLRs about each chip become equivalent to the mean and variance of x
j
(
k
) upon iteration convergence. The complete computational procedure of IDMA-CBC MUD has been given in Section 3.2.1.The choice of interleaver is an important problem for the IDMA system. In theory, the user-specific interleavers can be generated independently and randomly, while for the considered underwater sensor networks, the monitoring center has to use a considerable amount of memory to store these interleavers, which may cause serious concern when the number of users is large. Furthermore, during the initial link setting-up phase, a large number of messages are changed between the sensors and the monitoring center to inform each other about their interleavers. Extra bandwidth resource will be consumed for this purpose if the interleavers used by the sensors and the monitoring center are long and randomly generated. The case will be more serious for the long-propagation-delay, bandwidth-limited, and energy-limited underwater sensor networks. In view of this, the power-interleaver method [19] is employed in our scheme as follows.Assume that we have a master interleaverϕ. Then the K interleavers for each sensor can be generated as
(14)
π
k
≡
ϕ
k
,
where ϕ
k
(
c
) is defined as
(15)
ϕ
k
(
c
)
≡
{
ϕ
(
c
)
,
k
=
1
ϕ
(
ϕ
k
-
1
(
c
)
)
,
k
=
2
,
…
,
K
.
In this way, every interleaver is a “power” of ϕ. The rationale for this method is that if ϕ is an “ideal” random permutation, so are all {
ϕ
k
}, and these permutations are also approximately independent of each other. Based on this method, we simply assume that the monitoring center assigns the power index k to each user k, and then ϕ
k will be generated at the sensor nodes for user k accordingly. Considering that the number of active sensors is usually large in the ocean monitoring sensor networks, the uplink frame will be split into several subframes and IDMA scheme is operated in each subframe. The procedure is illustrated in Figure 5. At the beginning of each monitoring round, the monitoring center broadcasts a downlink control information packet to the underwater sensors. The control information packet contains the following contents: (
1
) ID of each selected sensor according to a given sensing probability p; (
2
) subframe index assigned to each selected sensor; (
3
) power index assigned to each selected sensor. Then, the selected sensors perform sampling and transmit the measurements with the allocated interleavers at the corresponding subframes. Next, the iterative CBC MUD algorithm is carried out in the monitoring center.Figure 5
The architecture of uplink data frame.


### 4.3. Reconstructing the Information Map

The output of MUD is used for reconstructing the information map. Traditionally, if barelyK
(
K
≪
N
) measurements are obtained for the monitoring field, it is insurmountable to achieve the required monitoring resolution. Furthermore, due to the effect of MAI and AWGN, some of the measurements may be destroyed in the multiple access procedure. The packet error rate (PER) is affected by the SINR of uplink channels, the length of the uplink data packet, and the error correction code it used. Detailed analysis will be given in Section 5.However, in view of the fact that most of the monitored underwater characteristics are sparse in the spatial domain (e.g., the objective tracking information) or the frequency domain (such as the temperature, salinity, and sea currents), the CS theory provides the possibility to reconstruct a high-resolution information map of the monitoring field withN elements. For a frequency-sparse scenario, in which the Fourier coefficients of the original signal X make up an N
×
1 vector Θ with only s none-zero elements, the transform matrix Ψ consists of N orthogonal Fourier basis shown as follows:
(16)
X
=
Ψ
Θ
,
Ψ
=
[
Ψ
1
,
Ψ
2
,
…
,
Ψ
N
]
,
Ψ
i
(
k
)
=
e
-
j
2
π
i
k
/
N
,
i
=
1,2
,
…
,
N
;
k
=
1,2
,
…
,
N
.According to the CS theory, if the sensing matrix is random and independent fromΨ and the number of measurements exceeds a certain threshold N
s, the original data of X can be reconstructed by solving the problem of (6). Considering that the active sensors are selected randomly and the packet error is random in the multiple access procedure, the corresponding sensing matrix is feasible for information recovery under CS framework. Several simpler and practicable methods have been proposed to solve this problem, such as BP (Basic Pursuit) [5], OMP (Orthogonal Matching Pursuit) [20], and BCS (Bayesian Compressed Sensing) [21]. In this paper, the OMP algorithm is adopted for information recovery, by which the theoretical threshold is N
s
=
2
k
ln
(
N
) [20].


## 4.1. Random Sensing at Sensor Side

In order to prolong the lifetime of the underwater sensor networks, in each monitoring round only a subset of the sensor nodes is randomly selected to make sensing and transmit the measurement to the monitoring center. The number of active nodes in one round is determined by a parameter named sensing probabilityp.According to the compressed sensing theory, in order to realize accurate recovery, the sensing matrixR should satisfy two basic conditions: the independency between R and Ψ and the RIP property. The commonly used sensing matrixes include random Gaussian matrix, random Bernoulli matrix, and partial Hadamard matrix. However, they cannot contribute to energy and bandwidth saving for the considered scenario. In view of this, a simple and efficient sensing matrix, random extractive matrix, is used in this paper. The random extractive matrix is easily formed by randomly selecting m rows from the n
×
n identity matrix, where n is the number of sensors in the monitored area and m is the number of the selected sensors in one round. The elements in the random extractive matrix have the following property:
(13)
∑
i
=
1
m
r
i
j
≤
1
,
j
=
1,2
,
…
,
n
,
∑
j
=
1
n
r
i
j
=
1
,
i
=
1,2
,
…
,
m
.


## 4.2. Interleave-Division Multiple Access over Noisy Channels

Suppose there areN underwater sensor nodes deployed in the monitoring area. In one round of information acquisition, each node performs measurement with probability p. Then, the random K
=
p
N measurements will be transmitted to the monitoring center simultaneously. In this study, IDMA is employed to distinguish the measurements from each other.Compared to CDMA, the transmitter of IDMA system exchanges the sequence of the spreader and interleaver; that is, it employs a chip-level interleaver to randomize the chip-level information. Consequently, the MAI in IDMA system can be regarded as the additive Gaussian white noise (AWGN), which is not reasonable in the traditional CDMA system. Similar to Turbo decoding, IDMA-CBC MUD is an iterative procedure with two decoding components, namely, an elementary signal estimator (ESE) andK a posteriori probability (APP) decoders (DECs). During each iteration, they exchange extrinsic log-likelihood ratios (LLRs) about x
k
(
j
), which is the j
t
h chip output from the user-k dependent permutation. From the central limited theorem, the MAI of every chip is reasonably approximated by a Gaussian distribution. Furthermore, the key principle of IDMA is that the user separation is made possible by using different interleavers invoked after the spreading, and chip-level interleaving makes MAI appear as an additive uncorrelated Gaussian process. Based on the above assumptions, the extrinsic LLRs about each chip become equivalent to the mean and variance of x
j
(
k
) upon iteration convergence. The complete computational procedure of IDMA-CBC MUD has been given in Section 3.2.1.The choice of interleaver is an important problem for the IDMA system. In theory, the user-specific interleavers can be generated independently and randomly, while for the considered underwater sensor networks, the monitoring center has to use a considerable amount of memory to store these interleavers, which may cause serious concern when the number of users is large. Furthermore, during the initial link setting-up phase, a large number of messages are changed between the sensors and the monitoring center to inform each other about their interleavers. Extra bandwidth resource will be consumed for this purpose if the interleavers used by the sensors and the monitoring center are long and randomly generated. The case will be more serious for the long-propagation-delay, bandwidth-limited, and energy-limited underwater sensor networks. In view of this, the power-interleaver method [19] is employed in our scheme as follows.Assume that we have a master interleaverϕ. Then the K interleavers for each sensor can be generated as
(14)
π
k
≡
ϕ
k
,
where ϕ
k
(
c
) is defined as
(15)
ϕ
k
(
c
)
≡
{
ϕ
(
c
)
,
k
=
1
ϕ
(
ϕ
k
-
1
(
c
)
)
,
k
=
2
,
…
,
K
.
In this way, every interleaver is a “power” of ϕ. The rationale for this method is that if ϕ is an “ideal” random permutation, so are all {
ϕ
k
}, and these permutations are also approximately independent of each other. Based on this method, we simply assume that the monitoring center assigns the power index k to each user k, and then ϕ
k will be generated at the sensor nodes for user k accordingly. Considering that the number of active sensors is usually large in the ocean monitoring sensor networks, the uplink frame will be split into several subframes and IDMA scheme is operated in each subframe. The procedure is illustrated in Figure 5. At the beginning of each monitoring round, the monitoring center broadcasts a downlink control information packet to the underwater sensors. The control information packet contains the following contents: (
1
) ID of each selected sensor according to a given sensing probability p; (
2
) subframe index assigned to each selected sensor; (
3
) power index assigned to each selected sensor. Then, the selected sensors perform sampling and transmit the measurements with the allocated interleavers at the corresponding subframes. Next, the iterative CBC MUD algorithm is carried out in the monitoring center.Figure 5
The architecture of uplink data frame.


## 4.3. Reconstructing the Information Map

The output of MUD is used for reconstructing the information map. Traditionally, if barelyK
(
K
≪
N
) measurements are obtained for the monitoring field, it is insurmountable to achieve the required monitoring resolution. Furthermore, due to the effect of MAI and AWGN, some of the measurements may be destroyed in the multiple access procedure. The packet error rate (PER) is affected by the SINR of uplink channels, the length of the uplink data packet, and the error correction code it used. Detailed analysis will be given in Section 5.However, in view of the fact that most of the monitored underwater characteristics are sparse in the spatial domain (e.g., the objective tracking information) or the frequency domain (such as the temperature, salinity, and sea currents), the CS theory provides the possibility to reconstruct a high-resolution information map of the monitoring field withN elements. For a frequency-sparse scenario, in which the Fourier coefficients of the original signal X make up an N
×
1 vector Θ with only s none-zero elements, the transform matrix Ψ consists of N orthogonal Fourier basis shown as follows:
(16)
X
=
Ψ
Θ
,
Ψ
=
[
Ψ
1
,
Ψ
2
,
…
,
Ψ
N
]
,
Ψ
i
(
k
)
=
e
-
j
2
π
i
k
/
N
,
i
=
1,2
,
…
,
N
;
k
=
1,2
,
…
,
N
.According to the CS theory, if the sensing matrix is random and independent fromΨ and the number of measurements exceeds a certain threshold N
s, the original data of X can be reconstructed by solving the problem of (6). Considering that the active sensors are selected randomly and the packet error is random in the multiple access procedure, the corresponding sensing matrix is feasible for information recovery under CS framework. Several simpler and practicable methods have been proposed to solve this problem, such as BP (Basic Pursuit) [5], OMP (Orthogonal Matching Pursuit) [20], and BCS (Bayesian Compressed Sensing) [21]. In this paper, the OMP algorithm is adopted for information recovery, by which the theoretical threshold is N
s
=
2
k
ln
(
N
) [20].


## 5. Analytical Observations

### 5.1. Consideration of Optimal Sensing Probability

As mentioned above, among theN underwater sensor nodes deployed in the monitoring area, only K nodes are active in one monitoring round. The active nodes are selected randomly by the monitoring center according to the sensing probability p. During the multiple access phase, part of the K transmitted measurements will be dropped for packet error due to the adverse effects such as thermal noise and multiple access interference (MAI). Obviously, when the sensing probability p turns larger, the MAI will be more severe, and, consequently, the packet error rate (PER) will increase. The amount of available measurements for information reconstruction is expressed as follows:
(17)
N
avl
=
N
act
p
suc
=
p
N
(
1
-
PER
)
,
where N
act
=
p
N is the number of active sensors in one round of information gathering and p
suc
=
1
-
PER is the probability that the measurements are successfully received after noisy multiple access channel.In our compressed sensing information acquisition scheme, the performance of reconstruction errorP
e is one of the most important evaluating indicators. Let us define it as a function of the sensing probability p:
(18)
P
e
=
f
(
p
)
.Obviously,p
e decreases with larger N
avl. However, the relationship between N
avl and p is not clear. In (17), N
avl is a linearly increasing function of p, while p
suc is a decreasing function of p. Therefore, the authors wonder whether an optimal sensing probability p exists, which leads to the minimal reconstruction error under CS framework. This is a key perspective of this paper.Without loss of generality, supposing a BCH(
m
,
n
,
t
) FEC code is used in IDMA system, followed by a length-r repetition code, as shown in Figure 2, then the PER can be calculated as
(19)
PER
=
∑
s
=
t
+
1
m
C
m
s
p
b
s
(
1
-
p
b
)
m
-
s
,
where p
b is the bit error ratio after the decoding of repetition code, which is a function of the chip error ration p
c and the repletion code length r. Given p
c and r, the solution of p
b is detailed as follows:
(20)
p
b
=
∑
i
=
[
r
/
2
]
r
C
r
i
p
c
i
(
1
-
p
c
)
r
-
i
.Suppose BPSK modulation with coherent demodulation is adopted and AWGN channel is taken into consideration. Then, the channel error ration, that is, the chip error rationp
c, is theoretically expressed as
(21)
p
c
=
1
2
erfc
(
γ
)
,
where γ is the signal-to-noise ratio (SNR) of single-user system, or the signal-to-interference-plus-noise ratio (SINR) at the iteration convergence point, that is, after multiuser detection.It is usually difficult to evaluate the efficiency of MUD accurately for a quasi-orthogonal multiuser system. Fortunately, the SINR evolution technique of IDMA system provides a simple semianalytical method to solve this problem, which in turn helps to build the relationship between the reconstruction error and sensing probabilityp under CS-IDMA framework.


### 5.2. Semianalytical Method Based on SINR Evolution

We now outline a performance evaluation technique for IDMA-CBC multiuser detection algorithm. The performance of IDMA-CBC detection scheme at the iteration convergence point is concerned, which depends on the amount of cancelled MAI, equivalently, the amount of variance reduced from chip{
x
k
(
j
)
,
∀
k
,
j
} variables [21]:
(22)
V
k
=
1
-
tanh
2
(
Y
SIN
R
k
2
)
,
k
=
1
,
…
,
K
.For each user-k, a fixed received power, P
k, can be maintained under the perfect power control (PPC). Thus, the total interference power received by user-k can be estimated as
(23)
I
k
=
P
N
+
∑
i
≠
k
P
i
·
E
(
V
i
)
,
where P
N is the thermal background noise, and by (22), we define
(24)
f
(
SIN
R
k
,
r
)
=
E
(
V
k
)
=
1
-
E
[
tanh
2
(
Y
SIN
R
k
2
)
]
,
k
=
1
,
…
,
K
.It is shown in [22], for large number of chips and BPSK with repetition code (each bit is replicated r times over the symbol chips), that Y
SIN
R
kis approximately Gaussian with mean and variance 2
(
r
-
1
)
SIN
R
k and 4
(
r
-
1
)
SIN
R
k, respectively. Thus, the average variance of an arbitrary chip from user-k, f
(
SIN
R
k
,
r
), is a function of SIN
R
k, which by definition is the uncancelled percentage of the interference power introduced by user-k. The corresponding MUD efficiency in the uplink is equivalent to 1
-
f
(
SINR
,
r
). Generally, f
(
SINR
,
r
) does not have an analytical expression, but it can be easily obtained by the Monte Carlo method, which is depicted in Figure 6 as the solid curve. In the situation of perfect power control, the SINR evolution for the iterative process can be expressed as
(25)
SIN
R
k
_
new
=
1
(
K
-
1
)
f
(
SINR
k
_
old
)
+
σ
2
.Figure 6
f (SINR) and f (SINRfinal) versus chip level SINR, with r
=
16, K
=
16, and E
b/N
0 = 4 dB.At the start, we initializef
(
SIN
R
k
_
old
)
=
1 for all k. Repeating (25), SINRk will converge towards a steady value and we call it SIN
R
k
_
final. Thus, at the convergence point, we have
(26)
SIN
R
k
_
final
≈
1
(
K
-
1
)
f
(
SINR
k
_
final
)
+
σ
2
.
The above expression can be modified as
(27)
f
(
SINR
k
_
final
)
≈
(
1
SIN
R
k
_
final
-
σ
2
)
1
K
-
1
.The above function is depicted in Figure6 as the dashed curve. Obviously, the cross point of the solid curve and the dashed curve corresponds to the final SINR value after CBC iterative MUD in IDMA system, which is the required value of γ in (21). Substituting the value of γ into (21) and by using (20), (19), and (17), we can solve the number of available measurements for reconstructing an information map. Thus, based on this special semianalytical technique of IDMA system, SINR evolution, we can further optimize system performance in a simple way. Using the above method, the optimal sensing probability will be observed in Section 6.


### 5.3. Resource Requirements

In this section, we give a thorough analysis of the resource requirements for the proposed scheme. Suppose the channel rate (digital bandwidth) isR
B and a frame is divided into I subframes; in each subframe K/I measurements are distinguished by different interleavers. As mentioned above, a BCH(m,n,t) FEC code followed by a length-r repetition code is used, in which an n-bit block is coded as an m-bit block, and a corrupted packet with no more than t bit errors can be corrected after decoding. Thus, the subframe length is calculated as
(28)
T
p
=
m
r
R
B
.
And the frame length for one monitoring period is
(29)
T
f
=
RTT
+
I
·
T
p
+
(
I
-
1
)
T
g
,
where RTT is the maximal round trip time between the sink node and the sensors and T
g is the guard time between two neighboring subframes.If the monitored element has a correlation time ofT
s, equivalently, the signal is stationary during T
s, one round of information acquisition should be completed in this correlation time. So we have
(30)
T
f
≤
T
s
.Substituting (29) into (30), we get
(31)
T
p
≤
T
s
-
RTT
-
(
I
-
1
)
T
g
I
.Combining (28) and (31), we get the requirement for the digital bandwidth of the underwater channel:
(32)
R
B
≥
m
r
I
T
s
-
RTT
-
(
I
-
1
)
T
g
.Considering that the transmitted signal is shaped by a square root raised cosine filter with a roll-off factor equivalent toβ, the minimal requirement for the occupied bandwidth is as follows:
(33)
B
req
=
R
B
,
req
(
1
+
β
)
lo
g
2
M
=
m
r
I
(
1
+
β
)
[
T
s
-
RTT
-
(
I
-
1
)
T
g
]
lo
g
2
M
,
where M
=
2 for the BPSK method.Similarly, we can get the requirement for energy consumption. Supposing the consumed energy of each sensor for one round of data sampling isE
g, the average energy cost for transmitting one bit is E
t, and the average energy cost for receiving a downlink control packet is E
r, then the total energy cost of the whole network during one monitoring round is
(34)
E
=
N
E
r
+
K
(
E
g
+
m
E
t
)
.Thus, the average energy consumption per sensor per round is(35)
E
~
=
E
N
=
E
r
+
p
(
E
g
+
m
E
t
)
.According to the channel model described in Section2, we have
(36)
E
t
=
A
(
d
,
f
)
·
E
b
,
where E
b is the required energy per bit at the receiver side.


## 5.1. Consideration of Optimal Sensing Probability

As mentioned above, among theN underwater sensor nodes deployed in the monitoring area, only K nodes are active in one monitoring round. The active nodes are selected randomly by the monitoring center according to the sensing probability p. During the multiple access phase, part of the K transmitted measurements will be dropped for packet error due to the adverse effects such as thermal noise and multiple access interference (MAI). Obviously, when the sensing probability p turns larger, the MAI will be more severe, and, consequently, the packet error rate (PER) will increase. The amount of available measurements for information reconstruction is expressed as follows:
(17)
N
avl
=
N
act
p
suc
=
p
N
(
1
-
PER
)
,
where N
act
=
p
N is the number of active sensors in one round of information gathering and p
suc
=
1
-
PER is the probability that the measurements are successfully received after noisy multiple access channel.In our compressed sensing information acquisition scheme, the performance of reconstruction errorP
e is one of the most important evaluating indicators. Let us define it as a function of the sensing probability p:
(18)
P
e
=
f
(
p
)
.Obviously,p
e decreases with larger N
avl. However, the relationship between N
avl and p is not clear. In (17), N
avl is a linearly increasing function of p, while p
suc is a decreasing function of p. Therefore, the authors wonder whether an optimal sensing probability p exists, which leads to the minimal reconstruction error under CS framework. This is a key perspective of this paper.Without loss of generality, supposing a BCH(
m
,
n
,
t
) FEC code is used in IDMA system, followed by a length-r repetition code, as shown in Figure 2, then the PER can be calculated as
(19)
PER
=
∑
s
=
t
+
1
m
C
m
s
p
b
s
(
1
-
p
b
)
m
-
s
,
where p
b is the bit error ratio after the decoding of repetition code, which is a function of the chip error ration p
c and the repletion code length r. Given p
c and r, the solution of p
b is detailed as follows:
(20)
p
b
=
∑
i
=
[
r
/
2
]
r
C
r
i
p
c
i
(
1
-
p
c
)
r
-
i
.Suppose BPSK modulation with coherent demodulation is adopted and AWGN channel is taken into consideration. Then, the channel error ration, that is, the chip error rationp
c, is theoretically expressed as
(21)
p
c
=
1
2
erfc
(
γ
)
,
where γ is the signal-to-noise ratio (SNR) of single-user system, or the signal-to-interference-plus-noise ratio (SINR) at the iteration convergence point, that is, after multiuser detection.It is usually difficult to evaluate the efficiency of MUD accurately for a quasi-orthogonal multiuser system. Fortunately, the SINR evolution technique of IDMA system provides a simple semianalytical method to solve this problem, which in turn helps to build the relationship between the reconstruction error and sensing probabilityp under CS-IDMA framework.


## 5.2. Semianalytical Method Based on SINR Evolution

We now outline a performance evaluation technique for IDMA-CBC multiuser detection algorithm. The performance of IDMA-CBC detection scheme at the iteration convergence point is concerned, which depends on the amount of cancelled MAI, equivalently, the amount of variance reduced from chip{
x
k
(
j
)
,
∀
k
,
j
} variables [21]:
(22)
V
k
=
1
-
tanh
2
(
Y
SIN
R
k
2
)
,
k
=
1
,
…
,
K
.For each user-k, a fixed received power, P
k, can be maintained under the perfect power control (PPC). Thus, the total interference power received by user-k can be estimated as
(23)
I
k
=
P
N
+
∑
i
≠
k
P
i
·
E
(
V
i
)
,
where P
N is the thermal background noise, and by (22), we define
(24)
f
(
SIN
R
k
,
r
)
=
E
(
V
k
)
=
1
-
E
[
tanh
2
(
Y
SIN
R
k
2
)
]
,
k
=
1
,
…
,
K
.It is shown in [22], for large number of chips and BPSK with repetition code (each bit is replicated r times over the symbol chips), that Y
SIN
R
kis approximately Gaussian with mean and variance 2
(
r
-
1
)
SIN
R
k and 4
(
r
-
1
)
SIN
R
k, respectively. Thus, the average variance of an arbitrary chip from user-k, f
(
SIN
R
k
,
r
), is a function of SIN
R
k, which by definition is the uncancelled percentage of the interference power introduced by user-k. The corresponding MUD efficiency in the uplink is equivalent to 1
-
f
(
SINR
,
r
). Generally, f
(
SINR
,
r
) does not have an analytical expression, but it can be easily obtained by the Monte Carlo method, which is depicted in Figure 6 as the solid curve. In the situation of perfect power control, the SINR evolution for the iterative process can be expressed as
(25)
SIN
R
k
_
new
=
1
(
K
-
1
)
f
(
SINR
k
_
old
)
+
σ
2
.Figure 6
f (SINR) and f (SINRfinal) versus chip level SINR, with r
=
16, K
=
16, and E
b/N
0 = 4 dB.At the start, we initializef
(
SIN
R
k
_
old
)
=
1 for all k. Repeating (25), SINRk will converge towards a steady value and we call it SIN
R
k
_
final. Thus, at the convergence point, we have
(26)
SIN
R
k
_
final
≈
1
(
K
-
1
)
f
(
SINR
k
_
final
)
+
σ
2
.
The above expression can be modified as
(27)
f
(
SINR
k
_
final
)
≈
(
1
SIN
R
k
_
final
-
σ
2
)
1
K
-
1
.The above function is depicted in Figure6 as the dashed curve. Obviously, the cross point of the solid curve and the dashed curve corresponds to the final SINR value after CBC iterative MUD in IDMA system, which is the required value of γ in (21). Substituting the value of γ into (21) and by using (20), (19), and (17), we can solve the number of available measurements for reconstructing an information map. Thus, based on this special semianalytical technique of IDMA system, SINR evolution, we can further optimize system performance in a simple way. Using the above method, the optimal sensing probability will be observed in Section 6.


## 5.3. Resource Requirements

In this section, we give a thorough analysis of the resource requirements for the proposed scheme. Suppose the channel rate (digital bandwidth) isR
B and a frame is divided into I subframes; in each subframe K/I measurements are distinguished by different interleavers. As mentioned above, a BCH(m,n,t) FEC code followed by a length-r repetition code is used, in which an n-bit block is coded as an m-bit block, and a corrupted packet with no more than t bit errors can be corrected after decoding. Thus, the subframe length is calculated as
(28)
T
p
=
m
r
R
B
.
And the frame length for one monitoring period is
(29)
T
f
=
RTT
+
I
·
T
p
+
(
I
-
1
)
T
g
,
where RTT is the maximal round trip time between the sink node and the sensors and T
g is the guard time between two neighboring subframes.If the monitored element has a correlation time ofT
s, equivalently, the signal is stationary during T
s, one round of information acquisition should be completed in this correlation time. So we have
(30)
T
f
≤
T
s
.Substituting (29) into (30), we get
(31)
T
p
≤
T
s
-
RTT
-
(
I
-
1
)
T
g
I
.Combining (28) and (31), we get the requirement for the digital bandwidth of the underwater channel:
(32)
R
B
≥
m
r
I
T
s
-
RTT
-
(
I
-
1
)
T
g
.Considering that the transmitted signal is shaped by a square root raised cosine filter with a roll-off factor equivalent toβ, the minimal requirement for the occupied bandwidth is as follows:
(33)
B
req
=
R
B
,
req
(
1
+
β
)
lo
g
2
M
=
m
r
I
(
1
+
β
)
[
T
s
-
RTT
-
(
I
-
1
)
T
g
]
lo
g
2
M
,
where M
=
2 for the BPSK method.Similarly, we can get the requirement for energy consumption. Supposing the consumed energy of each sensor for one round of data sampling isE
g, the average energy cost for transmitting one bit is E
t, and the average energy cost for receiving a downlink control packet is E
r, then the total energy cost of the whole network during one monitoring round is
(34)
E
=
N
E
r
+
K
(
E
g
+
m
E
t
)
.Thus, the average energy consumption per sensor per round is(35)
E
~
=
E
N
=
E
r
+
p
(
E
g
+
m
E
t
)
.According to the channel model described in Section2, we have
(36)
E
t
=
A
(
d
,
f
)
·
E
b
,
where E
b is the required energy per bit at the receiver side.


## 6. Performance Evaluation and Discussion

In order to evaluate the performance of the CS-IDMA scheme in underwater sensor networks, necessary simulations are carried out in this section. The ocean environmental data is available from the website of NASA JPL (http://ourocean.jpl.nasa.gov/). In the following simulations, the simple single-path multiple access underwater channel model with ideal power control is taken into consideration.The main simulation parameters are given in Table1.Table 1
Simulation parameters.
Parameters
Value
Data packet length
16 bits
Forward error correction coding
BCH (34, 16, 3)
Repetition code length
16
Average energy cost for receiving a downlink control packet,E
r
100 nJ
Average energy cost of each sensor for one round data sampling,E
g
1000 nJ
Number of sensors in the region
400
Number of sumframes,I
20
Roll-off factor of the square root raised cosine filter,β
0.98
Correlation time of the monitored element,T
s
100 s
Maximal round trip time
10 s
Guard time,T
g
20 ms
Noise power spectral density,N
0
−100 dBm
Carrier frequency
10 kHz


### 6.1. Simulation Results on 2D Real Data

We take the real ocean meridional current data of Monterey Bay as the experimental subject. The data is obtained by the Regional Ocean Modeling System (ROMS) at 3GMT 05/13/2012. The monitored region is 100 meters below the sea surface and ranged over [−122.8°E,−122.6°E] in longitude and [36.6°N, 36.8°N] in latitude, and the required spatial resolution is 0.01° × 0.01°. In the traditional method, we should divide the concerned area into 20 × 20 grids, and, in each grid, a sensor node is deployed for data sampling in order to build an information map of the monitored region. It should be noticed that any data missing will destroy the integrality of the information map. On the contrary, the proposed CS-IDMA scheme needs much fewer measurements for reconstructing an information map of the concerned area with the same spatial resolution. Moreover, data loss is tolerable with our scheme.Figure7(a) is the original information map of the given region, with a spatial resolution of 0.01° × 0.01°; Figure 7(b) illustrates the compressed sensing measurements by the 100 random selected sensors; Figure 7(c) describes the successfully received data after CBC iterative MUD; and Figure 7(d) shows the reconstructed result with OMP algorithm. In this simulation, E
b/N
0 at the sink side is set to be 8 dB. The simulation result of packet loss rate (PER) is 0.1055. As a result, about 90 of the 100 random measurements are available for the information reconstruction procedure, leading to a reconstruction error of 0.12389. Here, the reconstruction error P
e is defined as
(37)
P
e
=
∥
X
^
-
X
∥
2
∥
X
∥
2
=
∑
i
=
1
n
(
x
^
i
-
x
i
)
2
∑
i
=
1
n
x
i
2
.Information map about ocean meridional current of the given area. (a) Original information map; (b) measurement with random selected sensor nodes; (c) successfully collected data after CBC MUD; (d) reconstructed information map with OMP algorithm.
(a)
(b)
(c)
(d)


### 6.2. Optimal Sensing Probability and Resource Requirements

As mentioned above, the relationship between the reconstruction errorP
e and the sensing probability   p is not clear originally, while by using the semianalytical method peculiar to IDMA, we can plot the relationship curve in Figure 8. An interesting phenomenon is observed where, as the sensing probability increases from 0.1 to 1, the reconstruction error declines at the beginning phase and ascends quickly after a turning point. The turning point varies with different channel conditions. The larger the value of E
b/N
0  is, the latter the turning point appears. Consequently, for a given channel condition, there exists an optimal sensing probability. This result is significant for system designing.Figure 8
Reconstruction error versus sensing probability.It can also be seen from Figure8 that the reconstruction error decreases evidently with the increase of E
b/N
0, due to the higher packet loss rate. However, higher E
b/N
0 means that more energy consumption is required, as shown in Figure 9. In system designing, the performance tradeoff between resource requirement and quality of reconstructed information map should be considered according to the simulation results.Figure 9
Average energy consumption per sensor versusE
b/N
0 at receiver side.Furthermore, we discuss the issue of bandwidth requirement of our scheme. From (33) we can find the relationship between the minimum required bandwidth and the number of subframes. Meanwhile, given the number of active sensors, the number of subframes will affect the MAI of IDMA system and hence lead to different BER performance. As a result, the relationship between the reconstructed error and the minimum required bandwidth is given in Figure 10, where E
b
/
N
0
=
8 dB and p
=
0.6. We can see from Figure 10 that, in order to reconstruct an information map with reconstruction error below 0.1, at least 0.265 kHz bandwidth is required for the uplink multiple access channel. If more bandwidth is available, the reconstruction error keeps smooth because enough measurements are already provided for information reconstruction with the minimal required bandwidth. It should be noticed that the issue of overdesigning should be considered in real applications.Figure 10
Reconstruction error versus minimum required bandwidth.


### 6.3. Comparisons with the Traditional Method

In order to illustrate the advantages of compressed sensing in resource saving, the energy and bandwidth costs of the proposed CS-based scheme and the traditional information acquisition scheme are given in Figures11 and 12, respectively. From the figures we can find that, if an information map with the reconstruction error of no more than 0.1 is needed for the tested area, the CS-based new scheme requires far less network resources than the traditional scheme, saving 65% energy and 88% bandwidth, respectively.Figure 11
Comparison on energy cost between the proposed and traditional schemes.Figure 12
Comparison on bandwidth cost between the proposed and traditional schemes.


### 6.4. Simulation Result on 3D Real Data

The above research is carried out on the two-dimensional scenario; however, the proposed scheme is also suitable for the three-dimensional environment. In order to prove it, reconstruction experiment is implemented on the zonal current data collected at South California Bay at 3 GMT on May 16, 2012, at latitude [34.3°, 34.5°], longitude [−122.2°, −122.0°], and depth[
100 m, 600 m]. The original information map and reconstructed information map with optimal sensing probability are given in Figure 13. The reconstruction error is only 0.1136, with 62% energy saving and 75% bandwidth saving, respectively.Simulation result on 3D zonal current data. (a) Original information map; (b) reconstructed result.
(a)
(b)


## 6.1. Simulation Results on 2D Real Data

We take the real ocean meridional current data of Monterey Bay as the experimental subject. The data is obtained by the Regional Ocean Modeling System (ROMS) at 3GMT 05/13/2012. The monitored region is 100 meters below the sea surface and ranged over [−122.8°E,−122.6°E] in longitude and [36.6°N, 36.8°N] in latitude, and the required spatial resolution is 0.01° × 0.01°. In the traditional method, we should divide the concerned area into 20 × 20 grids, and, in each grid, a sensor node is deployed for data sampling in order to build an information map of the monitored region. It should be noticed that any data missing will destroy the integrality of the information map. On the contrary, the proposed CS-IDMA scheme needs much fewer measurements for reconstructing an information map of the concerned area with the same spatial resolution. Moreover, data loss is tolerable with our scheme.Figure7(a) is the original information map of the given region, with a spatial resolution of 0.01° × 0.01°; Figure 7(b) illustrates the compressed sensing measurements by the 100 random selected sensors; Figure 7(c) describes the successfully received data after CBC iterative MUD; and Figure 7(d) shows the reconstructed result with OMP algorithm. In this simulation, E
b/N
0 at the sink side is set to be 8 dB. The simulation result of packet loss rate (PER) is 0.1055. As a result, about 90 of the 100 random measurements are available for the information reconstruction procedure, leading to a reconstruction error of 0.12389. Here, the reconstruction error P
e is defined as
(37)
P
e
=
∥
X
^
-
X
∥
2
∥
X
∥
2
=
∑
i
=
1
n
(
x
^
i
-
x
i
)
2
∑
i
=
1
n
x
i
2
.Information map about ocean meridional current of the given area. (a) Original information map; (b) measurement with random selected sensor nodes; (c) successfully collected data after CBC MUD; (d) reconstructed information map with OMP algorithm.
(a)
(b)
(c)
(d)


## 6.2. Optimal Sensing Probability and Resource Requirements

As mentioned above, the relationship between the reconstruction errorP
e and the sensing probability   p is not clear originally, while by using the semianalytical method peculiar to IDMA, we can plot the relationship curve in Figure 8. An interesting phenomenon is observed where, as the sensing probability increases from 0.1 to 1, the reconstruction error declines at the beginning phase and ascends quickly after a turning point. The turning point varies with different channel conditions. The larger the value of E
b/N
0  is, the latter the turning point appears. Consequently, for a given channel condition, there exists an optimal sensing probability. This result is significant for system designing.Figure 8
Reconstruction error versus sensing probability.It can also be seen from Figure8 that the reconstruction error decreases evidently with the increase of E
b/N
0, due to the higher packet loss rate. However, higher E
b/N
0 means that more energy consumption is required, as shown in Figure 9. In system designing, the performance tradeoff between resource requirement and quality of reconstructed information map should be considered according to the simulation results.Figure 9
Average energy consumption per sensor versusE
b/N
0 at receiver side.Furthermore, we discuss the issue of bandwidth requirement of our scheme. From (33) we can find the relationship between the minimum required bandwidth and the number of subframes. Meanwhile, given the number of active sensors, the number of subframes will affect the MAI of IDMA system and hence lead to different BER performance. As a result, the relationship between the reconstructed error and the minimum required bandwidth is given in Figure 10, where E
b
/
N
0
=
8 dB and p
=
0.6. We can see from Figure 10 that, in order to reconstruct an information map with reconstruction error below 0.1, at least 0.265 kHz bandwidth is required for the uplink multiple access channel. If more bandwidth is available, the reconstruction error keeps smooth because enough measurements are already provided for information reconstruction with the minimal required bandwidth. It should be noticed that the issue of overdesigning should be considered in real applications.Figure 10
Reconstruction error versus minimum required bandwidth.


## 6.3. Comparisons with the Traditional Method

In order to illustrate the advantages of compressed sensing in resource saving, the energy and bandwidth costs of the proposed CS-based scheme and the traditional information acquisition scheme are given in Figures11 and 12, respectively. From the figures we can find that, if an information map with the reconstruction error of no more than 0.1 is needed for the tested area, the CS-based new scheme requires far less network resources than the traditional scheme, saving 65% energy and 88% bandwidth, respectively.Figure 11
Comparison on energy cost between the proposed and traditional schemes.Figure 12
Comparison on bandwidth cost between the proposed and traditional schemes.


## 6.4. Simulation Result on 3D Real Data

The above research is carried out on the two-dimensional scenario; however, the proposed scheme is also suitable for the three-dimensional environment. In order to prove it, reconstruction experiment is implemented on the zonal current data collected at South California Bay at 3 GMT on May 16, 2012, at latitude [34.3°, 34.5°], longitude [−122.2°, −122.0°], and depth[
100 m, 600 m]. The original information map and reconstructed information map with optimal sensing probability are given in Figure 13. The reconstruction error is only 0.1136, with 62% energy saving and 75% bandwidth saving, respectively.Simulation result on 3D zonal current data. (a) Original information map; (b) reconstructed result.
(a)
(b)


## 7. Conclusions

In this paper, a novel information acquisition scheme, CS-IDMA, is proposed for the large-scale ocean monitoring sensor networks. Exploiting the advantages of compressed sensing in low-sampling signal reconstruction and the advantages of IDMA in low-complexity multiuser detection, the proposed scheme can realize high-resolution information reconstruction with lower network cost, and the packet error during transmission can be greatly tolerant. With the aid of the particular semianalytical method based on SINR evolution, we give elaborate analytical observations on the proposed scheme. The simulation results carried on real ocean monitoring data show that our scheme can realize accurate information map reconstruction with much fewer measurements compared to the traditional method in which all sensors should participate in data sampling and transmitting, leading to less energy consumption and bandwidth requirement. Furthermore, an interesting phenomenon is observed where an optimal sensing probability exists for a given value ofE
b/N
0 at the receiver side, with which the minimal reconstruction error is achieved. This result is significant for system designing.



---

*Source: 430275-2014-01-09.xml*