Link Prediction and Route Selection Based on Channel State Detection in UASNs

Abstract

In Underwater Acoustic Sensor Networks (UASNs), data route is often disrupted by link interruption which will further lead to incorrect data transmission due to high propagation delay, Doppler effect, and the vulnerability of water environment in acoustic channel. So how to correctly transmit data when there are interrupted links on the data path is just the issue Delay Tolerant Networks (DTNs) aim to solve. In this paper, we propose a model to predict link interruption and route interruption in UASNs by the historical link information and channel state obtained by periodic detection. A method of decomposing and recomposing routes hop by hop in order to optimize route reselection is also presented. Moreover, we present a back-up route maintenance scheme to keep back-up routes with fresh information. In case of single route, we advance the idea to utilize the periodicity of environmental changes to help predict link interruption. In the simulation, we make comparisons on node energy consumption, end-to-end delay as well as bit error rate with and without link prediction. It can be derived that the network performance is significantly improved with our mechanism, so that our mechanism is effective and efficient while guaranteeing reliable data transmission.

1. Introduction

Wireless ad hoc network is a special kind of mobile communication networks with the characteristics of frequently changing network topology, multihop communication, and extremely limited energy [1]. In ad hoc networks, stable route is significant for reliable data transmission since it can decrease the calculation of route selecting, number of reply packets, alleviate energy loss of routers and shorten the packet propagation delay. The route stability relies on the stability of links in the route. However, links with higher stability can dramatically decrease the rerouting times and the probability of link interruption and consequently result in a long-term available route. Currently, the research in the area of wireless network is mainly based on the assumption: there exists at least one stable path between two ends. However, this assumption is not always satisfied [2]. For example, the wireless links between two different nodes could be broken as a result of natural environment, human interference, and nodes mobility. In this situation, how to make two ends restore normal communication to ensure real-time data collection and transmission is one of the challenging issues confronted by Delay Tolerant Network (DTN).

Currently, the study in DTN mainly focuses on mobile ad hoc network, wherein the topology changes strongly resulting from nodes roaming, and some links are unexpectedly broken in certain period of time. Moreover, DTN includes intermittently disconnected links with respect to the underwater acoustic network. And the model we propose here is applied in this environment.

Wireless sensor networks could be widely applied in environmental monitoring. But the intermittent link connection and topology and end-to-end variation in WSNs entails a huge challenge on how to guarantee the reliability of network operation and real-time data transmission. Compared with terrain sensor network, UASN has higher link interruption probability. The reasons of link interruption primarily include three aspects. (i) Network structure: node failures commonly exist due to energy exhaustion and topology variation that is caused by node floating. Besides, the fact the acoustic modem varies in its communication ranges has negative influence on the network topology generation. (ii) Underwater environment: ocean current, tide, and the sound-wave transmitted by mobile objects such as fish flock and ships passing by can disturb acoustic channel. (iii) Limitation of channel characteristics: underwater acoustic channel has higher transmission delay due to low transmission rate. Moreover, Doppler effect and multipath effect will lead to distinct interference at the receiver that may produce incorrect data reception.

It is widely acknowledged that there are several disadvantages in underwater communication. First, the data storage requirement is relatively high when data need to be buffered for a long time before finally dropping. Secondly, the sink node will continually transmit inquiring messages if it does not receive data from nodes along the route, and nodes in the network will passively wait for the link recovery with full power, which both introduce high energy consumption. In order to address these problems, we put forward a model of underwater DTN link prediction and route selection based on channel state detection.

Specifically, we investigate how to detect acoustic channel and environment state effectively, then estimate future link availability according to detected information, and make corresponding decisions by estimation results. In our model, nodes can sleep for a certain time or choose a new route and retransmit data stored in the buffer. This can increase the probability of successful delivery while conserving energy of underwater nodes. Moreover, under our model, nodes can predict the duration of disconnection as well as connection efficiently and optimize the decision-making by leveraging the characteristics of underwater channel and periodicity of underwater environment.

This paper presents a link prediction model of underwater DTN; it considers the characteristics of acoustic channel in UASN and makes use of channel state information by periodic channel detection. Then the prediction results are applied to multiple-route switch and route optimization. Since this model utilizes the information of real-time acoustic channel and the historical records of nodes, it has great pertinence on networks deployed in underwater environment and can take effective measures for link interruption caused by environmental factors such as nodes floating and disturbances from fish flocks. We analyze and describe the process of decision making in cases of multiple routes and single route, respectively.

The rest of this paper is organized as follows. Section 2 includes a detailed survey of related work. Section 3 describes the whole model of this algorithm and its application background. Section 4 exhibits a specification of channel detection, prediction model, and decision making. Simulation results and analysis are presented in Section 5. Section 6 concludes the paper.

2. Related Work

The research on DTN is generally focused on network structure, routing mechanism, and reliability, and most of them are related to terrain mobile adhoc network. There are some literatures centering on algorithms of route selection and route maintenance. Wherein [3] presents that a distributed algorithm makes different numbers of copies of messages sent by nodes by flooding to ensure reliable data transmission even with some broken links. Packets are divided through priorities to determine the number of copies of packets, together with redundant information and resources re-allocation. It can achieve that more important information will obtain more resources for less transmission delay, but there is no specification on how to handle route failure. In [4], a virtual network topology in mobile ad hoc network (MANET) is built using the statistical information collected by gateways to estimate future linking probability between neighbors. Unfortunately, this method uses gateway to make virtual topology and broadcast in the whole network, unsuitable for energy-limited UASNs. In [5], link stability is classified into different levels in terms of real-time measures such as signal strength. Route with the highest stability level will be chosen as main route. But it does not make prediction or analysis of future link state. So if the selected route was actually broken, this route would be invalid. Node uses the energy of received packets and the available time of links to choose the most reliable route in [6]. Route maintenance will be initiated before the link is to be broken. It is applicable to MANET with preset velocities, whereas in UASN nodes float due to environmental impacts with variable and small velocities.

Moreover, techniques of link interruption prediction and link connection prediction in ubiquitous networks have attracted considerable attention. The literature [7] proposes a probabilistic delay routing algorithm. It uses transmission delay, historical information of link connection to decide different prediction functions for future connection. It focuses on reducing delay but does not consider the impact of environmental changes on link state. In [8], it defines a probability metric-transmission prediction value, when two nodes meet, they exchange respective connection probability list and decide which node will forward data. A method to estimate link lifetime in MANET is given in [9]. It designs a mobile projection trajectory algorithm, whose input is periodically sampled noisy measurements between node pairs on a link. But the prediction precision is decided by the ratio of measurement duration to the whole link lifetime; the greater it is, the more precise the prediction will be. The literature [10] adopts the concept of link availability, it advances an algorithm of estimating continuous link availability between two mobile ad hoc nodes, which uses the distance of nodes to decide the state space of nodes and predict future distance.

The literature [11] is an improvement of [10]. It presents an approach for predicting continuous link availability between two mobile nodes, but it takes radio irregularity and quantities into consideration, better reflecting the reality. Reference [12] advances a constraint-based routing algorithm. It estimates link-state cost before prediction and makes Link-State Advertisements (LSAs) only upon topological changes for reducing communication traffic. The literature [13] proposes a method of Autonomous Underwater Vehicle (AUV) path prediction based on support vector machine, which is effective in the prediction of time sequence characterized by nonlinearity and high dimension. Nevertheless, it is sensitive to the input data and not adaptive to link state changes underwater. Reference [14] presents a model-based monitoring scheme in which each node periodically measures the characteristics of environment and sends them to gateway. When a link is interrupted, prediction of disconnection duration will be made according to historical information, though it excessively depends on gateway and aggravates the load of gateway.

The literature [15] uses local similarity indices to estimate the likelihood of the existence of links in weighted networks and emphasizes the important role of weak ties. And [16] generalizes the conception of link as the probability of interaction between node pairs in complex networks. It mainly studies how to increase the accuracy of link prediction using a reasonable similarity metric and how to find the potential information of future connection. These literatures handle issues of link prediction in complex networks such as social networks and focus on probability of new links rather than the disconnection of current links, which is not accordant with the application background of our model.

3. System Model

The system model of route selection and maintenance is shown in Figure 1. The key idea is to use channel information, such as signal strength, noise strength, nodes distance, and the historical information of link connection to predict possible link interruption for guiding node's decision.

Figure 1

System model of link prediction and route maintenance.

As UASN is usually sparsely deployed and can be supposed to be relatively static in a certain period, some simplification can be made. So we can consider it as a pseudostatic network, in which link may be intermittently disconnected due to impact of outside objects. This model makes use of channel information by periodic detection and historical information of links to predict route state, then obtains the duration of next connection, and finally makes performance evaluations. Here, for each data transmission, the historical information mainly means the channel state of the last time. In the presence of predicted results, nodes choose an optimal decision go to sleep or select a new route by comparison and judgment. Especially when there is only a single route between two nodes, more historical data is required to get the periodicity of channel changes. Thus, historical information is vital to optimized selection of routes. If there is no historical information or insufficient information, the prediction results we get will not be so precise, because only current channel information is available and further used. Obviously, the more historical information there is, the more precise the calculated periodicity will be. As a result, nodes cannot make precise evaluation of link state until they have obtained enough historical information.

To describe the basic attributes of a link, some definitions are made: $D_{a b}$ is the length of a link, $R_{a b}$ is the data transmission rate (can be taken as a constant here), $S_{a b}$ is the signal strength, $N_{a b}$ is the noise strength, $S_{R - S}$ is the signal strength threshold of receiver, and $E_{a b}$ is the residual energy.

In the prediction process, some link-state parameters should be defined: $S_{l s}$ is link state indicator, $S_{limit}$ is the threshold of link connection, $C_{L K}$ is the cost of selecting a link, $C_{P T_p t}$ is the cost of selecting a path, $P_{con}$ is the probability of connection, $f_{con}$ is actual connection flag of a link, $F_{con}$ is the predicted connection flag, and $L_{con}$ is the time needed for transmitting a packet.

After making a decision according to prediction results, some estimation parameters are defined: $w i n_l$ is the predicted duration of link connection, $R_{b}$ is the reliability of link prediction, $P_{e r}$ is the error rate of prediction, and $R_{b r}$ is the interruption rate of prediction.

4. Link Prediction and Route Selection Based on Channel Detection

Figure 2 is the flow chart of algorithm implementation on link prediction and route reselection. It mainly includes the following parts: initialization, channel detection, link prediction, and route reparation. This paper assumes that there has been an available routing protocol applied in routing discovery, and the initial route has been established in the stage of initialization. Nodes upload data to base station and detect the acoustic channel periodically.

Figure 2

Flow chart of algorithm implementation.

4.1. Channel Detection

Acoustic channel is a complex and time-varying channel, but there is some information that can be detected and used in link-state estimation, such as signal strength, noise strength, distance between two nodes, and data transmission rate. As for a deterministic network, it is reasonable to regard the data transmission rate as constant in an observation time. Therefore, the information needed for this model can be simplified as three factors: distance of two nodes, signal intensity, and noise intensity.

There are generally three technical ways for measuring distance of node pairs underwater; the first is to use the time difference of signal from the source node to the destination node; the second is to use the round trip time of signal transmission; the third is to use the Received Signal Strength Indicator (RSSI) to estimate the distance between two acoustic transceivers. The first method requires that the nodes have strict clock synchronization, but the transmission delay of acoustic signal is prone to environment, and it is difficult to reclaim and redeploy nodes for clock synchronization. The second means does not require clock synchronization, but the detection packet has to be transmitted twice, which will consume extra node energy and cause long measurement time. Although it is convenient to get the RSSI, but with the effect of multipath and Doppler shift, there is also some uncertainty and inaccuracy in estimating distances with all the three methods. Therefore, a more reasonable method has to be utilized depending on the characteristics of underwater channel. In acoustic channel, propagation loss can be expressed as

\begin{matrix} A (l, f) = A_{0} l^{k} α {(f)}^{l}, \end{matrix}

(1)

wherein, l is the distance, f is signal frequency,

A_{0}

is an attenuation constant, k is diffusion factor,

α (f)

is absorption factor [17]. The relation between receiving power and transmitting power is

\begin{matrix} P_{r} = {A (l, f) \cdot P}_{t} . \end{matrix}

(2)

In the received signal, after identifying and extracting useful information, the rest is noisy signal. By Fourier's transformation or wavelet transformation, the signal can be transformed from time domain to frequency domain, and noise strength can be calculated by signal analysis.

4.2. Link State Prediction

4.2.1. Parameters Definition

(i) Link state indicator. Let $S_{l s}$ be current link state indicator (LSI), which denotes the available signal-noise ratio (SNR).

\begin{matrix} \begin{matrix} S_{l s} = \frac{S_{a b} - S_{R - S}}{N_{a b}} \end{matrix} . \end{matrix}

(3)

(ii) Link state degeneration rate:

\begin{matrix} \begin{matrix} β (k) = \frac{{\hat{S}}_{l s} (k) - S_{l s} (k - 1)}{L_{con} (k - 1)} \end{matrix} . \end{matrix}

(4)

{\hat{S}}_{l s} (k)

is the estimated LSI of next cycle by prediction,

L_{con}

is the data transmission time in msec, and

L_{con} = L_{p k} / R_{a b}

L_{p k}

is the length of a packet;

R_{a b}

is data transmission rate which could be regarded as a constant, so data transmission time that depends on

L_{p k}

β (k)

reflects the degenerating rate or enhancing rate of a link in a sampling interval. If

β (k) < 0

, it indicates the link state is degenerating and vice versa.

Duration of connection:

\begin{matrix} w i n_l & = \frac{{\hat{S}}_{l s} (k) - S_{Limit}}{| β (k) |}, \\ {\hat{S}}_{l s} (k) - S_{Limit} > 0, β (k) < 0, \\ w i n_l & = \frac{{\hat{S}}_{l s} (k) - S_{Limit}}{S_{l s} (k - 1) - S_{Limit}} \cdot L_{c o n} (k - 1), \\ {\hat{S}}_{l s} (k) - S_{L i m i t} > 0, β (k) > 0, \\ w i n_l & = 0, {\hat{S}}_{l s} (k) - S_{Limit} < 0 . \end{matrix}

(5)

When link state is degenerating, $w i n_l$ is the time of link state changing from predicted LSI ${\hat{S}}_{l s}$ to state threshold $S_{Limit}$ , because if $S_{l s}$ is smaller than $S_{Limit}$ , link will be assumed disconnected, and $w i n_l = 0$ . When link state is enhancing, $w i n_l$ depends on the improvement level of link state and the previous $L_{con}$ . Comparing $w i n_l$ and $L_{con}$ , if $w i n_l > L_{con}$ , it indicates current link state can satisfy this data transmission and vice versa.

4.2.2. Prediction of LSI

Kalman filter is an optimized autoregressive data process algorithm, which is efficient and suitable for statistical estimation. This model applies the method of Kalman filter [18] to predict link state of nodes and gets quite accurate link state as well as relevant link attributes.

${\hat{S}}_{l s} (k)$ is the predicted LSI of next cycle by Kalman prediction, and then the connection probability of next time is

\begin{matrix} P_{con} (k) = \min (\frac{{\hat{S}}_{l s} (k)}{S_{l s} (k - 1)} \cdot \max [f_{con} (k - 1), α], 1) . \end{matrix}

(6)

α is a small positive constant to avoid the case that the link of the last cycle was broke (

f_{con}

is 0), then the successive probability of connection will always be 0.

If $0 \leq P_{con} \leq 0.4$ , it implies the link will be disconnected next time, so $F_{con} = 0$ . If $0.6 \leq P_{c o n} \leq 1$ , it denotes the link would be available in the next cycle, so $F_{con} = 0$ . If $0.4 < P_{con} < 0.6$ , it is not sufficient to determine whether link is connected or not in the next cycle, so it will inherit the connection flag of last time, which means $F_{con} (k) = F_{con} (k - 1)$ .

4.2.3. Prediction Result Evaluation

The prediction result evaluation includes two parts: link connection reliability and link state reliability.

(i) Link connection reliability: $L_{c r b} = 1 - | P_{con} (k) - f_{con} (k - 1) |, and f_{con} (k - 1)$ is the actual connection flag of time of $k - 1$ . If it is 1, then link is connected, and if it is 0, then link is disconnected. At time of k, only $f_{con} (k - 1)$ can be known, and we can get the link connection probability $P_{con} (k)$ of time k. If $P_{con} (k)$ is very similar to $f_{con} (k)$ , it means the reliability is higher and vice versa.

(ii) Link state reliability

\begin{matrix} {L s}_{r b} = \frac{\min ({\hat{S}}_{l s} (k - 1), S_{l s} (k - 1))}{\max ({\hat{S}}_{l s} (k - 1), S_{l s} (k - 1))} . \end{matrix}

(7)

LSI is the most important parameter that decides whether a link is connected. Comparing the predicted value with the actual value, the more similar they are, the more precise the prediction is.

The total prediction reliability

\begin{matrix} R_{b} = \frac{a_{1} \cdot {L c}_{r b} + a_{2} \cdot {L s}_{r b}}{a_{1} + a_{2}} . \end{matrix}

(8)

In (8)

a_{1}

and

a_{2}

are positive constants.

(iii) Error rate of link state prediction:

\begin{matrix} S_{e r} (k) = \frac{| S_{l s} (k) - {\hat{S}}_{l s} (k) |}{S_{l s} (k)} . \end{matrix}

(9)

(iv) Error rate of connection prediction:

\begin{matrix} L_{e r} (k) = | P_{con} (k) - f_{con} (k) | . \end{matrix}

(10)

The total prediction error rate of prediction:

\begin{matrix} P_{e r} (k) = \frac{a_{1} \cdot S_{e r} (k) + a_{2} \cdot L_{e r} (k)}{a_{1} + a_{2}} . \end{matrix}

(11)

(v) Interruption rate of a link:

\begin{matrix} R_{b r} = {\begin{cases} \frac{n - \sum_{i = 1}^{n} F_{con} (i)}{n}, if 0 < n \leq N \\ \frac{N - \sum_{i = 1}^{N} F_{con} (i)}{N}, if n > N . \end{cases} \end{matrix}

(12)

The maximal number of historical data recorded in each node is N . If running times are smaller than N, interruption rate of a link is calculated by data from the initial time to current time. If running times are more than N, interruption rate is calculated by data of the last N times.

(vi) Energy loss estimation:

It is assumed that input parameters are the same both with and without link prediction. When the main route is confirmed to be broken, a new route must be reselected. Since no prediction result can be used, the newly selected route may still include some broken links, which also cannot guarantee reliable data transmission. And during the time of waiting for confirmation $T_{c f m}$ , no matter whether link is broken, the source node will send inquiring packets by period of $T_{t}$ ; the energy needed of each transmission is $e_{d}$ , so the energy consumed while waiting is $T_{c f m} \cdot e_{d} / T_{t}$ . Reselecting a route consumes $e_{r t}$ . If there is a single available route when links are disconnected, nodes have to wait for link repairing.

If there is link prediction, nodes will know the approximate duration of link interruption, and they can choose to go to sleep mode while waiting for link reparation or immediately reselect an available link to substitute the old one. So we define that the power consumption in sleep mode is $P_{s l p}$ , the predicted duration of link interruption is $T_{w}$ , and the energy needed for a cycle of sleep-mode is $T_{w} \cdot P_{d}$ .

There are 4 cases concerning single route and multiple routes with or without prediction: (1)

single route without prediction

\begin{matrix} E_{g 1} = (1 - {0.5}^{l k_num}) \cdot (P_{c f m} \cdot T_{c f m} + e_{d} \cdot \frac{T_{w}}{T_{t}}), \end{matrix}

(13)

(2)

single route with prediction

\begin{matrix} E_{g 2} = (1 - P_{e r}) \cdot P_{s l p} \cdot T_{w} + P_{e r} \cdot E_{g 1}, \end{matrix}

(14)

(3)

multiple routes without prediction

\begin{matrix} E_{g 1} & = P_{c f m} \cdot T_{c f m} + e_r t + P_{b r 1} \\ \cdot (P_{c f m} \cdot T_{c f m} + e_r t), \end{matrix}

(15)

and

P_{b r 1} = {(1 - {0.5}^{l k_num})}^{r t_num - 1} + {0.5}^{l k_num} \cdot (1 - {0.5}^{l k_num})

is the probability of new route still including broken links.

(4)

multiple routes with prediction

\begin{matrix} E_{g 2} = e_{r t} + P_{b r 2} \cdot (e_{r t}), \end{matrix}

(16)

and

P_{b r 2} = {(1 - {(1 - R_{b r})}^{l k_num})}^{r t_num - 1}

is the probability of the new route still including broken links.

4.2.4. Link Prediction for Single Route

The practical application scenes probably include the following aspects. First, in the ocean, communication interruption may be caused by ships passing by, yet the time of ships passing by is not occasional but regular to some extent. Second, the tide also has impact on acoustic communication, and it has clear periodicity. Last but not the least, the probability of fish flocks that traverse an area complies with the movement regularity of fish.

If there is only one route between the source and destination with broken links, the source node has to wait for link reconnection. At this time, the model will predict the disconnection duration from current time to the next connection, which is the time that node needs to wait for. In order to make reasonable prediction and illuminated from the fact that periodic phenomena aforementioned, here we assume that link interruption is a kind of periodical events. After the first period, there will be records of link interruptions and other channel information. Then node can estimate the duration of link interruption based on the records of the last period. Therefore, the source node can resend data after a period of sleeping. This method not only reduces the energy consumption of nodes for continuous attempt of sending requiring packets but also guarantees the effectiveness and security of data transmission.

Periodic signal analysis can be carried out by differentiation analysis, polynomial fitting, Fourier's analysis, and wavelet analysis [19]. Because LSI in this model is a linear composition of each link attribute without complex trend component, Fourier transformation can directly get the frequency of signal.

Long-time Fourier transform requires the entire or a large part of time-domain signal to obtain the frequency characteristics. Consequently, this needs large storage space to save the time-domain signal. However, prediction using fewer signals may bring in large prediction error. In this case, wavelet transform or short-time Fourier transform [20] possesses inhere advantages. So short-time Fourier analysis is adopted here for nodes to find periodicity of channel changes.

4.3. Route Selection

When the source node decides to initiate the route reselection, it will have to evaluate the cost of a path. But the source node must get the state information of all nodes along the path to decide which back-up route will become the new main route. Here, we advance a concept of route decomposing and recomposing to simplify data delivery process and then choose a new route with the least cost.

4.3.1. Route Decomposing and Recomposing Hop by Hop

As Figure 3 shows, data from source S reaches sink D by 3 hops, S can communicate with node 1 and acquire its data, node 1 can acquire node 2's data, and node 2 can acquire node 3's data. Indirectly, S gets D's data, which contains the state information of link $3 \to D$ . Similarly, S can get all the other links state on the path. To decrease the communication load of S, this model innovatively decomposes a route hop by hop and then recomposes them in a reverse sequence. The detailed process is, from the sink node D in the reverse direction, in light of node 2, node 3 and D can be seen as a new node 3+; in light of node1, node 2, and 3+ can be seen as a new node 2+; similarly, node 1 and 2+ can be seen as a new node 1+. Therefore, node S only needs to communicate with the new node 1+. In this way, the process of communication in a route is simplified.

Figure 3

Data transmission of a single route.

If S cannot communicate with 1 at a time, so the data of 1+ about the link state from $1 \to D$ cannot be relayed to S, and S cannot estimate the state of the whole route. At this time, node 1 must search for other routes to S, For example, 1 finds 4 to forward data to S, and this process is called local rerouting, as Figure 4 shows.

Figure 4

Demonstration of hot links.

This model divides links into hot links and common links as shown in Figure 4. The link that is included in more than 2 routes is seen as a hot link; its interruption will lead to many routes failure. Link $3 \to D$ in Figure 4 is a hot link. If $3 \to D$ is broken, source node S has to wait for route repairing to restore normal transmission. Therefore, it is necessary to predict the duration of hot link interruption to avoid node's repeated attempt of connection.

4.3.2. Routes Reselection

When a route was interrupted, the source node selects an available and stable route from the main route and all back-up routes for data transmission. Here, we integrate all factors that influence link reliability and put them in the form of cost. Route with the smallest cost will be chosen as the main route.

Assuming that the main route is B, and B is broken at this moment (as shown in Figure 4), so it demands the steps of link prediction and route reselection. Source node will select a route with the smallest cost from the back-up routes A, C, and B for the next transmission.

The cost of a link is

\begin{matrix} C_{L K} = k 1 \cdot \frac{D_{a b}}{R_{c}} + k 2 \cdot \frac{hop_num}{hn_num}, \end{matrix}

(17)

where

R_{c}

is the communication range of a node, hn_num is the maximal hop number on a route, and hop_num is the number of hops between the link and the destination node

(D)

along a route.

k 1

and

k 2

are positive constants bolw 1 and

k 1 + k 2 = 1

. The cost of a path is

\begin{matrix} C_{P T} & = C_{L K} (1) \cdot C_{L K} (2 +) = C_{L K} (1) \cdot C_{L K} (2) \cdot C_{L K} (3 +) \\ = \dots = \prod_{i} C_{L K} (i), \end{matrix}

(18)

i is the ith link along the route. As the connectivity of a route depends on the connectivity state of links along it, so

C_{P T} = C_{P T} - \min ({\hat{S}}_{l s})

{\hat{S}}_{l s}

is the LSI set of all links on a route. If there are broken links on the route,

C_{P T}

must be multiplied by a factor α according to the number of broken links to increase the cost, which is

C_{P T} = C_{P T} \cdot α

, α is a constant greater than 1.

This can ensure that a route with more broken links will produce a higher cost. As a result, it is less impossible for a path with broken links to become the new route. If all routes have some broken links, the prediction of disconnection duration will be needed, as Section 4.2 describes.

4.3.3. Back-Up Routes Maintenance

If the main route is connected and available all the time, there will be no chance for back-up routes to transmit data, so they could not acquire the historical information of links along the route and channel characteristics. When one back-up route is selected as a new route, since it does not have any historical information, it cannot make accurate prediction of link states. Therefore, in order to get necessary historical information for back-up routes, we adopt a fresh idea of state maintenance on back-up routes. Two strategies are put forwarded. (i) Back-up routes are intermittently used to transmit data. (ii) Nodes along back-up routes are intermittently used to detect the acoustic link.

In detail, there are two techniques of intermittently using back-up routes. First, sensing data is transmitted by back-up routes once in a while. Second, less important data or data with lower delay constraint is transmitted by back-up routes. The first method is mainly applied in situations where data has similar priority or importance, and the second is suitable in situations where data packets have different priorities, especially when there are emergent event messages. At this time, their priority is higher than common data packets, so they should be transmitted via the main route, and other data packets are transmitted via back-up routes.

Also, there are two means of intermittently detecting the acoustic channel by back-up routes. First, when this back-up route is used to transmit data, nodes along the route simultaneously detect channel. Second, no matter whether the route is used, nodes along the route always periodically detect channel.

5. Simulation and Analysis

To verify the prediction model and route selection algorithm in case of link interruptions and route interruptions, two different situations are classified: prediction for multiple routes and prediction for a single route. Here we use Opnet and Matlab as the simulation platform.

Simulation setup. The channel model is flat Rayleigh fading, carrier frequency is 20 kHz, the modulation is Quadracture Amplitude Modulation (QAM), data transmission rate is set to 1000 bits/s, and the length of packet is changed from 100–400 bits. Sensor nodes gather data and transmit data to sink node in the scheme of event-driven, which means that if nodes' data satisfies the need of one transmission or nodes receive the transmission command, it will begin to find a route and transmit data.

5.1. Prediction for Multiple Routes

For simplicity, we assume a small scale network with 12 sensor nodes. There are three available routes between source node and destination node after routing discovery, and the initial main route is the red line as Figure 5 shows. The input parameters are the attributes of acoustic channel; by formula (3), they are transformed to a parameter LSI, and the actual LSI $S_{l s}$ is demonstrated in Figure 6(a).

Figure 5

Initial topology.

Figure 6

LSI prediction and link flag.

Figures 6 and 7 are predicted LSI, connection flag, error rate of prediction, reliability, interruption rate, and connection duration on a link. Figure 6(a) is the comparison of actual LSI and predicted LSI by Kalman filter. Figure 6(b) is the actual flag of link connection $f_{con}$ and predicted flag $F_{con}$ , it is evident to see that estimation results match with the real values. $P_{e r}$ in Figure 6(b) is the error between $F_{con}$ and $f_{con}$ , when LSI is near the threshold $S_{limit}$ , the predicted LSI will deviate from the actual value, because at this point connection flag $f_{con}$ suddenly changes from 1 to 0 or 0 to 1.

Figure 7

Comparison of predicted parameters.

Figure 7(a) is link interruption rate and prediction reliability; the former value is floating from 0.8 to 1.0; the latter one is varied with the changes of $F_{con}$ , while $t = 35$ –50, the link is continuously broken, $R_{b r}$ is keeping increasing, but once link reconnects, it will keep decreasing. Figure 7(b) is the comparison of predicted duration of link connection and the actual value; while LSI is high, the predicted $w i n_l$ is relatively large, but when LSI is below $S_{Limit}$ , $w i n_l$ is sharply decreased to 0. Besides, for $L_{con}$ is the actual time required for each data transmission, as long as $w i n_l > L_{con}$ , it is thought that this transmission can be completed.

Figure 8(a) is the different main routes selected by nodes after running 50 times. The numbers on the vertical axis represent three different paths. It is obvious that route 1 is most frequently used, and route 3 is scarcely used. While $t = 35$ –50, because route 1 has a broken link and route 3 is not so efficient, route 2 is chosen.

Figure 8

Route selection and energy consumption.

Figure 8(b) is the comparison of energy consumed with and without link prediction. It can be seen that the energy consumed without prediction is more than 30% higher than that with prediction. This is because when nodes estimate that the link will be disconnected, they will reselect a most potential route without broken links or with fewest broken links. And the better the link state is, the less possible broken links are to be included in this route. As a result, the energy consumption of node is significantly decreased. However, without link prediction, nodes have to select a new main route repeatedly if it still contains several broken links. This will consume much more energy and may lead to another data transmission failure.

Figure 9(a) compares the end-to-end delay with link prediction (LP) and without link prediction. With reference to Figure 6, when link state is good and there is no interruption, delay in the two cases is almost the same. And when there is link disconnection, delay with LP is a little longer than that when there is no link disconnection. This is because nodes consume some processing time when reselecting routes. But without LP, nodes can affirm link interruption after the threshold of waiting $time - T_{w}$ , which consumes a lot of time. Besides, it is possible that the reselected route is not the optimal, which means that the new route may also include disconnected links. So the end-to-end delay is much longer than that with LP. The impulse in the figure is caused because of the prediction error when link starts to be broken and reconnects. This costs some waiting time of nodes.

Figure 9

End-to-end delay and bit error rate.

From the red line in Figure 9(b), we can see that, with the changes of $S_{l s}$ , the bit error rate (BER) is changing. When $S_{l s}$ is decreasing, BER gradually increases and vice versa. When $t = 0$ –10, link state is almost the best, so BER is almost decreased to be the lowest and when 4–4.5, BER is almost increased to the greatest. Therefore, the BER we derive is accordant with the actual link state. This is the result without LP.

When there is LP, as nodes can predict link disconnection, they will choose another path to transmit data. For link interruption that is because environmental changes cause acoustic changes and make the data error rate in the receiver larger than the tolerant values (such as BER ≥ 0.02), so it is assumed that link has been broken and not suitable to transmit data. Accordingly, the receiver will obtain data with high BER in this case. But the new route reselected contains less broken links as much as possible, hence by the BER is greatly decreased than that without LP.

From the aspects of energy consumption, end-to-end delay, and bit error rate, it is obvious that the mechanism proposed in this paper is effective and efficient.

5.2. Prediction for Single Route

If there is only one route between the source and destination nodes but with disconnected links, source node has no choice but to wait for link repairing. Yet we can estimate the duration of route interruption in order to let nodes go to sleep for energy conservation. In Section 4.2.4, we have demonstrated that real environmental changes are often quasiperiodic events. Thereby, it is reasonable to suppose that actual link state has inherent periodicity. When a link interrupts, it does not know the current time but only can estimate the periodicity of link changes by historical records of LSI and find its relative position in a period.

Figure 10(a) is the simulated changes of link state, in which there are 4 periods and the periodicity is 5. Figure 10(b) is signal frequency derived from Fourier transformation, it can be seen that there is a pulse in $f = 0.2$ Hz, which denotes that the basic frequency of signal is $f = 0.2$ Hz and a multiple frequency is $f = 0.4$ Hz. So we can deduce the signal periodicity is $T = 1 / f = 5$ . Figure 11(a) is the relation between point of a link beginning to interrupt and the duration of interruption in each period, if the flag of link connection is 1, then the link is connected and vice versa. In Figure 11(b), the horizontal axis is the number of times of link interruption; the vertical axis is the length of each interruption, corresponding to the Figure 11(a).

Figure 10

Periodicity detection.

Figure 11

Periodic interruption of a link.

The two figures indicate that it is convenient to detect the periodicity of link state by simple signal transformation. And this method can improve the accuracy and efficiency in the process of link prediction.

6. Conclusion and Prospect

In this paper, we have presented a link prediction and route reselection model of DTN in UASN to facilitate the data transmission in case of link interruption. The primary contributions of this paper are summarized as follows.

(1) The characteristics of acoustic channel are taken into account in UASN, and channel state is periodically detected to derive the LSI. Depending on historical link state information and current channel information, the LSI of next time can be predicted to determine whether link will be interrupted.

(2) A method of route decomposing and recomposing hop by hop is proposed for the optimization of route selection. For the effectiveness of back-up routes, we advance a method of back-up routes maintenance to keep them with fresh channel information.

(3) With respect to multiple routes and single route, we propose a mechanism of route reselection and route maintenance. Specifically, in the case of single route, we advance the idea to utilize the periodicity of environmental changes to help predict link interruption.

The simulations compare three network performances between two cases with and without link prediction. The results prove that the method of link prediction and route reselection is valid and effective by analysis on the energy consumption of nodes, end-to-end delay of data transmission and the bit error rate of the receiver.

Although link prediction has become a research hot spot in cognitive radio, complex networks, there are still not deep explorations on the relation between algorithm performance and network structure. Moreover, no uniform standards are defined on the link characteristics. Hence, link prediction, especially in UASNs, needs continuous research effort. This paper applies link prediction into underwater pseudostatic sensor network to improve the data transmission in challenged environment, which is a typical application scene. How to further optimize and generalize the model and expand the application scope is a research direction of future work. Moreover, how to integrate link prediction into the process of route discovery is a potential aspect of next stage.

Footnotes

Acknowledgments

The authors would like to thank the reviewers for their detailed comments that have helped to improve the quality of the paper. This work was funded in part by National Basic Research Program of China (973 Program) 2011CB707106, NSF China 60972044 and the Fundamental Research Funds for the Central Universities 201121202020002.

References

Khadar

Simplot-Ryl

From theory to practice: topology control in wireless sensor networks

th 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc '09)

May 2009

347 348

2-s2.0-70450188880

10.1145/1530748.1530807

Wang

X.-Y.

Liu

Z.-J.

Zhou

Y.-H.

Analysis of link interruption characteristics in the DTN

Journal on Communications 2008 29 11 232 236

Guo

Colombi

Wang

Cui

J. H.

Maggiorinit

Rossi

G. P.

Adaptive routing in underwater delay/disruption tolerant sensor networks

the 5th Annual Conference on Wireless on Demand Network Systems and Services (WONS '08)

January 2008

31 39

2-s2.0-50049132178

10.1109/WONS.2008.4459352

Samuel

Zhuang

Preiss

DTN based dominating set routing for MANET in heterogeneous Wireless Networking

Mobile Networks and Applications 2009 14 2 154 164

2-s2.0-62249166562

10.1007/s11036-008-0131-8

Agarwal

Ahuja

Singh

J. P.

Shorey

Route-lifetime assessment based routing (RABR) protocol for mobile Ad-hoc networks

IEEE International Conference on Communications

June 2000

1697 1701

2-s2.0-0033699295

Hong

Huang

T. P.

Zou

W. X.

S. R.

Zhou

Research of AODV routing protocol based on link availability prediction

Tongxin Xuebao/Journal on Communications 2008 29 7 118 123

2-s2.0-49549125922

Yin

H. M.

Cao

Y. D.

Probabilistic delay routing for delay tolerant networks

the 10th International Conference on Advanced Communication Technology

February 2008

191 195

2-s2.0-44249107350

10.1109/ICACT.2008.4493741

Lindgren

Doria

Schelén

Probabilistic routing in intermittently connected networks

3126

Proceedings of the 1st International Workshop Service Assurance with Partial and Intermittent Resources (SAPIR '04)

August 2004

Fortaleza, Brazil

239 254 Lecture Notes in Computer Science

Haas

Z. J.

Hua

E. Y.

Residual link lifetime prediction with limited information input in mobile ad hoc networks

the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08)

April 2008

26 30

2-s2.0-51349111883

10.1109/INFOCOM.2007.250

10.

Gong

Bai

Chen

Qian

Link availability prediction in Ad Hoc Networks

the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS '08)

December 2008

423 428

2-s2.0-60649107640

10.1109/ICPADS.2008.14

11.

Bai

Gong

Link availability prediction with radio irregularity coverage for mobile multi-hop networks

IEEE Communications Letters 2010 14 6 518 520

2-s2.0-77953220271

10.1109/LCOMM.2010.06.100238

5474929

12.

Masip-Bruin

Marín-Tordera

Yannuzzi

Serral-Gracià

Sànchez-López

Reducing the effects of routing inaccuracy by means of prediction and an innovative link-state cost

IEEE Communications Letters 2010 14 5 492 494

2-s2.0-77951888467

10.1109/LCOMM.2010.05.092312

5456076

13.

Zhang

Liu

Real time path predicting for autonomous underwater vehicle using support vector regression machines

the 4th International Conference on Natural Computation (ICNC '08)

October 2008

414 416

2-s2.0-57649120071

10.1109/ICNC.2008.380

14.

Tulone

A model-based monitoring scheme for disruption-tolerant underwater sensor networks

the 6th IEEE Annual Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks

June 2009

2-s2.0-71049155374

10.1109/SAHCNW.2009.5172917

15.

Lü

Zhou

Role of weak ties in link prediction of complex networks

the 1st ACM International Workshop on Complex Networks in Information and Knowledge Management (CNIKM '09)

November 2009

55 58

2-s2.0-74049116552

10.1145/1651274.1651285

16.

Liben-Nowell

Kleinberg

The link-prediction problem for social networks

Journal of the American Society for Information Science and Technology 2007 58 7 1019 1031

2-s2.0-34249751638

10.1002/asi.20591

17.

Niu

Yang

Guo

Simulation study on time-varing multiple paths of acoustic channel

Jounal of Oceanography in Taiwan Straint 2009 28 4 586 591

18.

Xue

J. F.

H. M.

Shi

Design of DTN routing algorithm based on probabilistic delay

Transaction of Beijing Institute of Technology 2008 28 8 687 691

2-s2.0-52349116373

19.

Wen

Zhang

Detection of the periodic signal in the deformation analysis with wavelet and fourier tansformation

Bulletin of Surveying and Mapping 2004 4 14 16

20.

Zhao

Xiong

Seperation of periodic signals using variable detection step

Transactions of Sichuan University(Natural Science Edition) 1995 32 5 527 532