Abstract: The unique characteristics of the underwater acoustic communication channel, such as three dimensional volumes of the environment and the limited energy, make it necessary to design and develop new routing algorithms. In this study, we propose an innovative energy-efficient multi-hop routing scheme for three-dimensional sensor networks based on compressed sensing. During each frame, a randomly chosen subset of nodes participates in the sensing process instead of all nodes delivering their message to the Sink node. Every chosen node finds a tour to the Sink node. As the message travels through the tour, each node computes the product of its sensing data and a random weighted coefficient and adds value to the intermediate result received from the last node. Analysis and simulation results show that our proposed algorithms are able to give an accurate approximation of the monitoring field and prolong network lifetime.
INTRODUCTION
In recent years, the development and utilization of marine resources has become a trend and maritime rights and interests are paid more and more attention, in this background the Underwater Wireless Sensor Network (UWSN) has become a research hotspot. UWSN can monitor, sense and collect information of a variety of environments or monitored objects in the network distribution underwater area and then deal with the measurements to obtain detailed and accurate information about the concerned region. With the arising of Internet of Thins (IOT) and the development of UWSN, people have concerned more about the information resource from the underwater area, as well as from the terrestrial domain. 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 et al., (Heidemann et al., 2006; Cui et al., 2006). At present, there are mainly two kinds of topological structure (Akyildiz et al., 2004), namely two-dimensional underwater sensor networks and three-dimensional underwater sensor networks where sensor nodes are suspended at different depths in the ocean. In this study, we consider a 3D UWSN where node localization is essential to information collection. There are two types of underwater positioning technology (Ou et al., 2008), namely range-based positioning technology and range-free positioning technology. In this study, we assume node localization has been completed in advance and then we consider information collection problems.
A 3D region of interest to monitor a physical phenomenon is considered in this study. In the traditional case, each sensor node communicates its observations of the field to a central node. As we all know, the underwater sensor network is a typically energy-limited and bandwidth-limited system, the technical bottleneck of which is the asymmetry between the demand for large-scale information acquisition and the limited network resources. The traditional information acquisition methods can not solve the above problem radically; while the newly arising Compressed Sensing (CS) theory provides a chance for breaking through the bottleneck. The promising theory stipulates that under certain conditions, exact signal recovery is possible with a small number of random measurements (Candes et al., 2006; Donoho, 2006). In the recent few years, the researchers have attempted to utilize CS technology in the aspects of analog-to-information converter, wireless communications, image processing, compressive radar, wireless networks et al.
In view of the technical advantages of CS, we employ compressed sensing to reduce the energy consumption of the underwater sensor networks based on the fact that most natural phenomena are compressible (sparse) in an appropriate basis.
CS is envisioned as a highly promising tool for improving the performance of the resource-limited underwater sensor networks. There has been a number of works exploiting CS in wireless sensor networks dealing with space-time correlated data as in Quer et al. (2009) and Wang et al. (2010) based on the decentralized compression techniques presented in Haupt et al. (2008) and Fazel et al. (2011). Random access compressed sensing scheme is proposed for energy-efficient underwater wireless sensor networks. Each node determines to participate in sensing with a certain probability. The selected node transmits its packet to fusion center by one hop. Chou et al. (2009) proposes adaptive compressed sensing in UWSN. The authors determine the projection vector so as to optimize the information gain per energy expenditure.
However, the existing information collection algorithms in wireless sensor network using compressive sensing are aimed at two-dimension network. In this work, we consider a 3D network that measures a physical phenomenon. The proposed method based on compressed sensing results in an energy-efficient scheme referred to as Distributed Random Multi-hop Compressed Sensing (DRMCS). These randomly selected nodes find a tour with weighted coefficient as the projection vector to sink. The random coefficient values of nodes along this tour form the projection vector. We believe that this information collection scheme is particularly suitable for the energy-limited 3-D network due to the following advantages: (1) Sink reconstructs monitoring area information using a small number of observations instead of all nodes sending observed values, (2) The residual energy is considered when we decide the next-hop node. Thus, balanced energy consumption is achieved and (3) The projection vector using all sensors along a path will give more accurate information with less energy.
INFORMATION COLLECTION FRAMEWORK
Due to the generality and universality of routing, consider a 3D underwater sensor network shown in Fig. 1, which consists of N sensors randomly distributed within a three-dimensional region. The sink node is located in the middle of square water surface. Assume that the location of each node is known in advance by location algorithm. All nodes in this network have the same structure and the same parameters such as initial energy.
The 3D network is deployed to monitor a physical phenomenon and we assume that all the sensors are synchronized. A snapshot of the temporal-spatial field is considered. Each sensor makes a measurement at a particular time t. The measurement at sensor node i (where I = 1,..., N) is zi = xi+ei, where xi is the noise-free measurement of sensor node i and ei is the sensor noise.
| Fig. 1: | An area sensor network consisting of N sensor nodes |
We use x to denote the vector [x1, x2,..., xn]T,
where T denotes matrix transpose; the vectors e and z are similarly defined.
We are aimed to obtain an approximation
is used to measure the accuracy of the reconstructed data field where:
denotes the 2-norm of x.
As we all know, for a monitored field which is spatially correlated, such as
the underwater temperature or salinity, the observed natural phenomena have
a compressible representation in a certain sparse domain. In this study, we
assume that the vector x is compressible in a basis
y = Φz = Φ(x+e) |
(1) |
where, Φ is an MxN random observation matrix. For simplicity, we ignore the noise. Noting that x = Ψθ, Eq. 1 can be re-written in terms of the sparse vector θ, as shown below:
y = Φx = ΦΨθ |
(2) |
The sink node firstly tries to recover sparse vector θ as accurately as possible, then uses it to reconstruct x. Given the observations y, the random selection pattern Φ and the sparse basis Ψ, reconstruction can be performed by solving the following minimization problem:
| (3) |
According to the theory of compressed sensing, the solution to the convex optimization problem 3 is equal to θ with high probability as long as the number of randomly picked observations is greater than Ms = CKlogN. Here K is the sparsity of the original signal and C is a constant that is independent of N and K.
In this scheme, we randomly select M sensor nodes as starting nodes. Every starting node finds a path to the sink node according to a routing principle which will be stated in the following sections. The received data at the sink node from every route is shown as:
| (4) |
Each row of the observation matrix Φ namely φij = (j = 1, 2,..., N) represents a routing. The sensor nodes not contained in the ith route correspond to zero elements in the row vector φij = (j = 1, 2,..., N). In other words, the number of nonzero elements in each row vector equals to the number of sensor nodes on a corresponding path. Each column of Φ represents a sensor node.
DISTRIBUTED RANDOM MULTI-HOP COMPRESSED SENSING IN UWSN
In this section, distributed random multi-hop compressed sensing in underwater wireless sensor network is discussed. The nodes in the network decide to send data with a probability p = M/N. This can be achieved by equipping the sensors with independent, identically distributed Bernoulli random generators. Nodes that send data become the open nodes of different routes. Due to the number of network nodes N is huge, M paths are generated in statistical terms. We regard the current node that is collecting data as the source node.
The proposed Distributed Random Multi-hop Compressed Sensing (DRMCS) is summarized below:
| Step 1: | At the beginning of the information acquisition process, every node tosses a coin to determine whether it participates in sensing with probability p |
| Step 2: | The current source node I broadcasts HELLO routing information in a radius R containing the information of node location and transmission power. Node j within broadcast radius R calculates the distance dis_ij to the source node. Node j determines whether it becomes the next hop node by its own depth and distance dis_ij. The selected next node meeting our conditions relies to the sending node |
As shown in Fig. 2, let the source node be N1 and it broadcasts HELLO routing information within radius R. Figure 2 shows that there are four nodes N2, N3, N4, N5 within the radio range. Because node N5 is deeper than N1 i.e., dep_N5>dep_N1, node N5 does not make any response. The cylinder radius of node N1 is denoted by:
| (5) |
where, dis_N1 is the distance between the sink node and node N1, depth_N1 is the depth of node N1. The cylinder radiuses of other nodes are similarly calculated. As shown in Fig. 2, the depth of node N4 is less than the depth of N1 but it’s obvious that the cylinder radius r_N4 is greater than r_N1, node N4 doesn’t reply. Both N2 and N3 satisfy the conditions of depth and radial, so they send the response information to node N1, respectively, containing distance information dis_N2 and dis_N3. Node N1 chooses the best next-hop node and adjusts transmission power according to the received response information.
| Fig. 2: | Selection of the next-hop node |
| Step 3: | As mentioned above, there may be more than one node making response. The source node determines the best next hop using the following weight equation. The weight equation concerned with energy of nodes and distance is expressed as: |
| (6) |
where, ∂ is the weighting factor balancing energy and distance; dep_i and dep_j is respectively the depth of the source node and the answer node’s; dis_ij is the distance between the source node and the answer node;Er is the current energy of the answer node and E0 is the initial energy. The answer node having the maximum weight W through Eq. 6 is chosen as the next hop node.
| Step 4: | The source node measures the physical quantity of interest and multiplies it by a random data value, then encodes the result into a packet of L bits. The sensor’s location and the random data are included in the packet |
| Step 5: | The source node sends the packet to the next node. The next node generates a packet in the same way and adds it to the intermediately received result. The added result is what the next-hop node transmits |
| Step 6: | The next-hop node becomes the source node, finds the next node and transmits information according to the above method. This doesn’t end until the sink node is within the broadcast routing range of the source node |
| Step 7: | The sink node uses the received packets to reconstruct the data using l1 minimization (or other sparse recovery methods (Tropp and Wright, 2010) |
SIMULATION AND PERFORMANCE ANALYSIS
In this section, we compare the performance of DRMCS scheme with that of a conventional scheme. In the traditional case, all the sensor nodes transmit their collected information to the sink node instead of M senders in our scheme. The relay node is selected according to the scheme above. The relay node doesn’t participate in sensing process and only relays the packet of the source node. Each node’s packet is forwarded to the sink node through multi-hop transmission.
We consider a 3D sensor network model as shown in Fig. 1 in our simulation.
| Table 1: | Simulation parameters |
| Fig. 3: | The average reconstruction error versus No. of measurements |
There are 400 sensor nodes randomly distributed in a 240x240x240 region. We refer to the attenuation model of underwater acoustic signal in Ref. 13. Table 1 gives the parameter values in the attenuation model.
In our scheme based on compressed sensing, the sink node reconstructs the original information map using the received M measurements. Figure 3 shows the average reconstruction error plotted versus the number of measurements. As seen in the figure, with the increase of M, smaller reconstruction error will be achieved.
In an underwater deployment, network energy is of utmost importance since re-charging batteries is difficult. Energy consumption thus naturally emerges as a figure of merit for system performance. Consequently, one of the performance measures that we consider in this study is the average energy consumption of the network needed to sense a given area.
Figure 4 shows the total energy consumption for one field information collection versus the broadcast radius. In our DRMCS scheme, M = 50 paths are generated, that is, the sink node receives M = 50 observations. From Fig. 3, the reconstruction error is Pe = 0.095 when M = 50.
| Fig. 4: | Total network energy consumption vs. broadcast radius R, M = 50 |
| Fig. 5: | Packet success rate versus broadcast radius, M = 50 |
As seen in the figure, for the same broadcast radius, DRMCS requires less energy compared to the conventional scheme. With the broadcast radius increasing, the network consumes more energy. The reason is: finding routing consumes more energy and the source node requires more energy to transmit packets because the next-hop is more distant.
Packet success rate is related to the reliability of the algorithm. Figure 5 illustrates the probability of packet delivered successfully versus the broadcast radius R. Since nodes are randomly distributed and M paths are randomly selected, there is so little difference between the probability of the conventional scheme and DRMCS. The rate increases when the broadcast radius becomes larger. We determine the radius referring to the network size, nodes distribution density, etc.
| Fig. 6: | The total energy consumption of the network versus network monitoring rounds |
| Fig. 7: | No. of current survival nodes versus network monitoring rounds |
In the practical applications, a new information map of the monitoring field is obtained periodically. Figure 6 shows the total energy consumption versus the network monitoring rounds with the proposed DRMCS scheme. Assuming the broadcast radius is 200 m and each node participates in sensing process with probability 0.5, that is, there are M = 200 nodes sensing data in the 400 survival nodes. From Fig. 3, we can see the reconstruction error is Pe = 0.032. When the nodes are all dead, the total energy 400 J is consumed. It can be seen from Fig. 6 that, in the DRMCS scheme, the total energy of network will be exhausted after 210 rounds with the weighting factor ∂ = 0.9, while it will be exhausted after 150 rounds with the weighting factor ∂ = 0.1. As a contrary, for the conventional case, all nodes die out after 125 rounds.
| Fig. 8: | The original information map of the given region about zonal current |
| Fig. 9: | The reconstructed information map with 100 measurements, reconstruction error is 0.09521 |
Figure 7 shows the number of current survival nodes versus the network monitoring rounds under the same simulation aconditions with Fig. 6. The simulation results show that our DRMCS scheme is superior to the conventional scheme in prolonging the network lifetime and the larger the weighting factor ∂, the longer network lifetime is achieved because the energy consumption among nodes is commendably balanced.
In order to prove the feasibility of the algorithm, we employ DRMCS to sense a real field. We consider zonal current data collected at South California Bay at 3GMT on May 16, 2012 at latitudes [34.3, 34.5°] and longitudes [-122.2, -122.0°] and depth (100 600). The original information map and the reconstructed information map with 200 measurements are given in Fig. 8 and 9, respectively.
| Fig. 10: | The average reconstruction error versus the number of measurements |
The reconstruction error is 0.09521. Furthermore, Fig. 10 shows the normalized reconstruction error versus the number of measurements of the zonal current field. We can see that our scheme is suitable for 3D underwater sensor networks.
CONCLUSION
We proposed an energy-efficient multi-hop information collection scheme, DRMCS, for underwater sensor networks based on compressed sensing in this study. This scheme is suitable for 3D networks, saving network energy and prolonging the network life. The underlying condition is that the measured physical phenomenon is compressible in a sparse basis. We consider the residual energy of each node when next-hop node is determined. Thus the balanced energy consumption is ensured. Our performance evaluation with simulated data shows that our scheme gives accurate estimation of the unknown data. The performance of DRMCS was analyzed in terms of the energy consumption, the packet success rate and so on. It is obvious that our scheme is superior to the conventional scheme. This study provides a valuable reference solution for large underwater wireless sensor network. Furthermore, the proposed scheme can be easily used in other suitable scenarios of multi-hop sensor networks.
ACKNOWLEDGMENTS
This study was supported by the National Natural Science Foundation of China (Grant No. 61371100, 61001093), the Promotive Research Fund for Excellent Young and Middle-aged Scientist of Shandong Province (Grant No. BS2012DX001), the Fundamental Research Funds for the Central Universities (Grant No. HIT.NSRIF.2013136) and the Sci-Tech Development Project of Weihai (2010-3-96).