Traffic Prediction-Based Fast Rerouting Algorithm for Wireless Multimedia Sensor Networks

Abstract

Rerouting has become an important challenge to Wireless Multimedia Sensor Networks (WMSNs) due to the constraints on energy, bandwidth, and computational capabilities of sensor nodes and frequent node and link failures. In this paper, we propose a traffic prediction-based fast rerouting algorithm for use between the cluster heads and a sink node in WMSNs (TPFR). The proposed algorithm uses the autoregressive moving average (ARMA) model to predict a cluster head's network traffic. When the predicted value is greater than the predefined network traffic threshold, both adaptive retransmission trigger (ART) that contributes to switch to a better alternate path in time and trigger efficient retransmission behaviors are enabled. Performance comparison of TPFR with ant-based multi-QoS routing (AntSensNet) and power efficient multimedia routing (PEMuR) shows that they: (a) maximize the overall network lifespan by load balancing and not draining energy from some specific nodes, (b) provide high quality of service delivery for multimedia streams by switching to a better path towards a sink node in time, (c) reduce useless data retransmissions when node failures or link breaks occur, and (d) maintain lower routing overhead.

1. Introduction

Efficiently transmitting multimedia streams in wireless multimedia sensor networks (WMSNs) is a significant challenging issue, due to the limited transmission bandwidth and power resource of sensor nodes. Three recent surveys [1–3] on current trends and future directions in WMSNs show that to overcome various failures, such as node failures, link breaks, network congestion, and dynamic holes, routing has the responsibility of choosing an alternate path that is not optimal to continually deliver the multimedia streams which can cause huge rerouting overhead. These three surveys also expatiate that there is no solution focusing on addressing the rerouting problem of multimedia streaming in WMSNs. Thus, more rerouting algorithm explorations are required to adapt to topology changes caused by various failures and guarantee the quality of service of multimedia streaming delivery.

Rerouting over WMSNs is different from the existing routing protocols for scalar wireless sensor networks [2, 3]. It is a very critical and challenging issue due to the stringent quality of service (QoS) requirements of multimedia (video streaming, still images, and audio) transmission, such as $(1)$ the end-to-end delay, $(2)$ the packet delivery rate, and $(3)$ the PSNR (peak signal-to-noise ratio) level. Hence, a fast rerouting mechanism is required in order to avoid various failures resulting in service interruption.

This paper proposes a traffic prediction-based fast rerouting (TPFR) algorithm for use among the cluster heads in WMSNs. TPFR runs on the top of the uneven cluster network topology, because the uneven clustering network model may provide a valuable solution to balance the network loads and prolong the lifetime of WMSNs [4]. According to the literature [5], the intercluster multipath routing is discovered. And then, we use autoregressive moving average (ARMA) model to predict the cluster head's network traffic. When the predicted value is greater than the predefined network traffic threshold, both adaptive retransmission trigger (ART) that contributes to switch to the better alternate path and trigger efficient retransmission behaviors are enabled. In consequence, this failure area is smoothly bypassed, and multimedia streams are continually forwarded to the destination node. Finally, TPFR is implemented on the NS-2 platform. Compared with similar algorithms, TPFR can significantly improve the quality of data transmission services. Moreover, TPFR has lower energy consumption and routing overhead and can prolong the network lifetime.

The rest of the paper is organized as follows. Section 2 introduces an overview of existing related works. Section 3 provides the network architecture, the system model, and the assumptions. Section 4 presents the traffic prediction-based fast rerouting algorithm. Section 5 presents the theoretical analysis and the performance evaluation. Finally, Section 6 concludes the paper.

2. Related Work

In this section, we focus on multipath routing protocols for WMSNs that include routing and scheduling functionalities, and we summarize them in Table 1.

Table 1

Multipath routing and transmission protocols for WMSNs.

Protocol	Network architecture	Geographic routing	Operational layer	Fault-tolerant mechanism	Performance metric
MMSPEED [6]	Flat	Yes	Routing/MAC	Weak	Delay/overhead
TPGF [7]	Flat	Yes	Routing	Medium	Delay/hop count
MPMPS [8]	Flat	Yes	Routing	Medium	Distance/delay/data type
AntSensNet [5]	Hierarchical	No	Transport/routing	Medium	Delay/packet delivery ratio/overhead
PEMuR [9]	Hierarchical	No	Routing/MAC	Medium	Delay/energy consumption/PSNR

Multipath and Multi-SPEED (MMSPEED) routing protocol [6] supports probabilistic QoS guarantee by provisioning QoS in two domains, timeliness and reliability. MMSPEED adopts a differentiated priority packet delivery mechanism in which QoS differentiation in timeliness is achieved by providing multiple network-wide packet delivery speed guarantees. MMSPEED needs the support of IEEE 802.11e at the MAC layer with its inherent prioritization mechanism based on the differentiated interframe spacing (DIFS). Each speed level is mapped onto a MAC layer priority class. For supporting service reliability, probabilistic multipath forwarding is used to control the number of delivery paths based on the required end-to-end reaching probability. In the scheme, each node in the network calculates the possible reliable forwarding probability value of each of its neighbors to a destination by using the packet loss rate at the MAC layer. According to the required reliable probability of a packet, each node can forward multiple copies of packets to a group of selected neighbors in the forwarding neighbor set to achieve the desired level of reliability. MMSPEED could use its redundant path selection scheme for load balancing, which is not only for reliability enhancement, but also to improve the overall network lifetime. However, the drawback of the protocol is that it shows degraded performance in handling various holes and the sudden network congestion.

The two-phase geographical greedy forwarding (TPGF) routing protocol [7] focuses on exploring and establishing the maximum number of disjoint paths to the destination in terms of the minimization of path length, the end-to-end transmission delay, and the energy consumption of nodes. The first phase of TPGF algorithm explores the possible paths to the destination. During this phase, a step back and mark is used to bypass voids and loops until successfully a sensor node finds a next-hop node which has a routing path to the base station. The second phase is responsible for optimizing the discovered routing paths with the shortest transmission distance (i.e., choosing a path with least number of hops to reach the destination).

The MPMPS (multipriority multipath selection) routing protocol [8] is an extension of TPGF. MPMPS highlights the fact that not every path found by TPGF can be used for transmitting video because a long routing path with long end-to-end transmission delay may not be suitable for audio/video streaming. Furthermore, because in different applications, audio and video streams play different roles and the importance level may be different, it is better to split the video stream into two streams (video/image and audio). For example, video stream is more important than audio stream in fire detection because the image reflects the event; while audio stream is more important in deep ocean monitoring. Therefore, we can give more priority to the important stream depending on the final application to guarantee the using of the suitable paths.

It is worth to note that both TPGF and MPMPS are offline multipath routing protocols. However, these “offline multipath” protocols have to explore the multiple routes that may exist between the source and the destination before the actual data delivery phase. They may not be well adapted for large-scale highly dense unattended network deployments and for networks with frequent node mobility.

The literature [5] proposes a QoS routing algorithm for WMSNs based on an improved ant colony algorithm (AntSensNet). The AntSensNet algorithm introduces routing modeling with four QoS metrics associated with nodes or links. The algorithm can find a route in a WMSNs that satisfies the QoS requirements of an application, while simultaneously reducing the consumption of constrained resources as much as possible. Moreover, by using clustering, it can avoid congestion after quickly judging the average queue length and solve convergence problems, which are typical in ant colony optimization. In addition, AntSensNet is able to use an efficient multipath video packet scheduling in order to get minimum video distortion transmission.

Power efficient multimedia routing (PEMuR) [9] aims at both energy efficiency and high QoS attainment. To achieve its objectives, PEMuR proposes the combined use of an energy aware hierarchical routing protocol with an intelligent video packet scheduling algorithm. The routing protocol enables the selection of the most energy efficient routing paths and manages the network load according to the energy residues of the nodes. In this way, an outstanding level of energy efficiency is achieved. Additionally, the proposed packet scheduling algorithm enables the reduction of the video transmission rate with the minimum possible increase of distortion. In order to do so, it makes use of an analytical distortion prediction model that can accurately predict the resulted video distortion due to any error pattern. Thus, the algorithm may cope with limited available channel bandwidth by selectively dropping less significant packets prior to their transmission.

Both AntSensNet and PEMuR are “online” energy efficient hierarchical multipath routing protocols. However, these “online multipath” protocols lack fast rerouting mechanism when the various failures of nodes or links happen. Thus, the drawback of the two protocols is that the QoS of the video stream transmission rapidly degrades in handling various holes and sudden failures. In consequence, they may not be well adapted for the resource-constrained WMSNs and the stringent quality of service (QoS) requirements of multimedia transmission.

Hence, we propose a novel online fast rerouting algorithm called TPFR that $(1)$ reduces video distortion using multi-priority-level multipath transmission model, $(2)$ predicts network traffic through cluster heads using autoregressive moving average (ARMA) model, and $(3)$ fast routes packets through better alternate paths using the traffic prediction strategy for avoiding various failures.

3. System Model

The many-to-one traffic pattern results in the hot spot problem when the multihop forwarding mode is adopted in intercluster communication for WMSNs. Because the cluster heads closer to the base station are burdened with heavier relay traffic, the area near the base station becomes a hot spot. Nodes in the hot spot drain their energy and die much faster than other nodes in the network, reducing sensing coverage and causing network partitions. Although many protocols proposed in the literature reduce energy consumption on forwarding paths to increase energy efficiency, they do not necessarily extend the network lifetime due to the unbalanced energy consumption.

We divide the network into uneven clusters using our proposed protocol, called UCBCPNS [10], where each cluster is deployed with heterogeneous sensors (camera, audio, and scalar sensors) that communicate directly in a certain schedule with a cluster head and relay their sensed data to it. Moreover, these heterogeneous sensor nodes have the same radio interface and propagation range. A cluster head has more resources, and it is able to perform intensive data processing. These powerful nodes and cluster heads are deployed nonuniformly in the network, and they are wirelessly connected with the sink either directly (in case of first-level cluster heads) or through other cluster heads in multihop mode. The graphical depiction of the nonuniform clustering architecture is shown in Figure 1. Our algorithm runs on the top of the nonuniform clustering network topology.

Figure 1

Graphical depiction of the nonuniform clustering architecture adopted by TPFR.

Then, the queuing model on a multimedia sensor node is designed, which is shown in Figure 2. According to the urgency and importance of the data streams, the model sets the different priorities for the different types of data streams and allows the high priority data stream to firstly transmit on a better path. For example, there are three types of data streams to be transmitted, such as video stream, sound stream, and scalar data stream. According to different application scenarios and demands, the system may automatically set different priority levels for different types of traffic. When a cluster head receives different types of traffic from other cluster heads, the received traffic is divided into three types, namely, video stream, sound stream, and scalar data by using the classifier model in the node's inside queues. Then the system makes a decision on the forwarding sequence of different types of traffic reference to the priorities set by itself. It is worth to note that the video sequence begins with an I-frame and is followed by P-frames and B-frames. I-frame in the video streams is a key frame, and P-frames and B-frames are nonkey frames. In a group of pictures, the decoding of P-frames and B-frames depends on the I-frame. If the I-frame is lost, the P-frames and the B-frames become useless data, which not only affects the quality of the video decoding, but also will result in the waste of network resources [11]. In our scheme, I-frame is firstly delivered on a better path.

Figure 2

Queuing model on a multimedia sensor node.

The scheduler in Figure 2 has two functions which are similar to the function of routing. One is responsible for delivering the higher priority data streams to the optimal primary routing, and the other is responsible for fast rerouting the data streams to another better alternate route when various failures happen. The first function has been achieved using the AntSensNet [5], and the second function will be achieved using the TPFR proposed in this paper.

4. Traffic Prediction-Based Fast Rerouting

Internet traffic prediction plays a fundamental role in network design, management, control, and optimization [12]. Essentially, the statistics of network traffic itself determines the predictability of network traffic. Network traffic prediction for WMSNs is the process of mapping past (and present) traffic values onto future traffic values through linear or nonlinear mapping functions as shown in

$$\begin{array}{cc}& \widehat{X}\left(t+k\right)=F\left[X\left(t\right),X\left(t-1\right),\dots ,X\left(t-p+1\right)\right],\end{array}$$

(1)

where the function F maps the past p traffic values $X(t),\hspace{0.17em}X(t-1),\dots ,X(t-p+1)$ onto the k step-ahead traffic value $\widehat{X}(t+k)$ .

The design of a traffic prediction scheme mainly concerns constructing or devising the proper mapping functions.

4.1. Traffic Prediction Model Using Autoregressive Moving Average

We firstly gather enough network traffic from a gateway. The hybrid network traffic includes the multimedia data generated by the MeshEye nodes and the scalar data generated by the Mica2 nodes, which is shown in Figure 3. Assume that the time series of the collected traffic is $\{X_i\}$ . Then the time series $\{X_i\}$ is analyzed using the famous commercial statistical software named SAS, and we find that the time series $\{X_i\}$ is a stationary and non-Gaussian white noise sequence. The modeling is described as follows.

Figure 3

Original network traffic.

$(1)$ Sample autocorrelation coefficients and partial correlation coefficients: we obtain the sample autocorrelation coefficient of $X_i$ using

$$\begin{array}{cc}& {\widehat{\rho }}_k=\frac{{\sum }_{t=1}^{n-k}\left(x_t-\stackrel{-}{x}\right)\left(x_{t+k}-\stackrel{-}{x}\right)}{{\sum }_{t=1}^n{\left(x_t-\stackrel{-}{x}\right)}^2},\hspace{1em}\forall \hspace{0.17em}0<k<n.\end{array}$$

(2)

The sample partial correlation coefficient of $X_i$ is obtained by using

$$\begin{array}{cc}& {\widehat{\varphi }}_{kk}=\frac{{\widehat{D}}_k}{\widehat{D}},\hspace{1em}\forall \hspace{0.17em}0<k<n,\end{array}$$

(3)

where

$$\begin{array}{cc}& \widehat{D}=\left|\begin{array}{cccc}1& {\widehat{\rho }}_1& \cdots & {\widehat{\rho }}_{k-1}\\ {\widehat{\rho }}_1& 1& \cdots & {\widehat{\rho }}_{k-2}\\ ⋮& ⋮& & ⋮\\ {\widehat{\rho }}_{k-1}& {\widehat{\rho }}_{k-2}& \cdots & 1\end{array}\right|,\\ {\widehat{D}}_k=\left|\begin{array}{cccc}1& {\widehat{\rho }}_1& \cdots & {\widehat{\rho }}_1\\ {\widehat{\rho }}_1& 1& \cdots & {\widehat{\rho }}_2\\ ⋮& ⋮& & ⋮\\ {\widehat{\rho }}_{k-1}& {\widehat{\rho }}_{k-2}& \cdots & {\widehat{\rho }}_k\end{array}\right|.\end{array}$$

(4)

After that, we find that the two correlation coefficients ${\widehat{\rho }}_k$ and ${\widehat{\varphi }}_{kk}$ show significant tailing. Thus, we use the ARMA $(p,\hspace{0.17em}q)$ model to fit the time series $\{X_i\}$ .

$(2)$ The order p and the order q of the ARMA process: the Akaike information criterion (AIC) [13] is used to select the order p and the order q, which is shown in formula

$$\begin{array}{cc}& \text{AIC}=-2\ln \left(\widehat{\beta }\right)+2M,\end{array}$$

(5)

where M denotes the number of unknown parameters in the model and $\widehat{\beta }$ denotes the maximum likelihood estimates of β.

The logarithm likelihood function in (5) is denoted by formula

$$\begin{array}{cc}& \ln \left(\widehat{\beta };x_1,\dots ,x_n\right)=-\left[\frac{n}{2}\ln {\widehat{\sigma }}_{\epsilon }^2+\frac{n}{2}+\frac{n}{2}\ln 2\pi \right].\end{array}$$

(6)

Combine formula (5) and formula (6), and then we can get formula

$$\begin{array}{cc}& \text{AIC}\left(p,q\right)=n\ln {\widehat{\sigma }}_{\epsilon }^2+2\left(p+q+1\right).\end{array}$$

(7)

We solve the minimum value of the function AIC $(p,q)$ and obtain that the minimum of AIC occurs at the order p equals 2 and the order q equals 1. As a consequence, we use the ARMA $(\mathrm{2,1})$ model to fit the time series $\{X_i\}$ , which is shown in

$$\begin{array}{cc}& \mathrm{\Phi }\left(B\right)X_i=\mathrm{\Theta }\left(B\right)a_i,\\ \mathrm{\Phi }\left(B\right)=1-{\varphi }_{1}B-{\varphi }_2{B}^2,\\ \mathrm{\Theta }\left(B\right)=1-{\theta }_{1}B,\end{array}$$

(8)

where B is a backward shift operator, $\{a_i\}$ is a Gaussian white noise with mean zero and variance ${\sigma }^2$ , and ${\varphi }_1$ , ${\varphi }_2$ , ${\theta }_1$ , and ${\sigma }_a^2$ (white noise variance) are parameter estimation. We use the least squares estimation method to estimate the parameters ${\varphi }_1,\hspace{0.17em}{\varphi }_2,\hspace{0.17em}{\theta }_1$ , and ${\sigma }_a^2$ in time series $\{X_i\}$ due to the resource-constrained sensor nodes. We can obtain the estimated parameters ${\widehat{\varphi }}_1=-0.63703$ , ${\widehat{\varphi }}_2=0.33314$ , ${\widehat{\theta }}_1=-0.93656$ , and ${\sigma }_a^2=0.00172$ . These parameters satisfy the stationarity condition of the time series $\{X_i\}$ , namely, ${\widehat{\varphi }}_1\hspace{0.17em}+\hspace{0.17em}{\widehat{\varphi }}_2<1$ , ${\widehat{\varphi }}_2-{\widehat{\varphi }}_1<1$ , and $|{\widehat{\varphi }}_2|<1$ . Hence, we can get the ARMA fitted model which is shown in

$$\begin{array}{cc}& X_t+\mathrm{0.63703}{X}_{t-1}-\mathrm{0.33314}{X}_{t-2}=a_t+\mathrm{0.93656}{a}_{t-1}.\end{array}$$

(9)

According to the stationarity and invertibility conditions of the ARMA model, we also get

$$\begin{array}{cc}& x_t=\sum _{i=0}^{\infty }{G}_i{\epsilon }_{t-i},\\ {\epsilon }_t=\sum _{j=0}^{\infty }{I}_j{x}_{t-j},\end{array}$$

(10)

where $\{G_i\}$ denotes the Green function values and $\{I_j\}$ denotes the values of the inverse functions

$$\begin{array}{cc}& x_t=\sum _{i=0}^{\infty }\hspace{0.17em}\sum _{j=0}^{\infty }{G}_i{I}_j{x}_{t-i-j}.\end{array}$$

(11)

We refer to $x_{t+l}$ , for all $l\ge 1$ , as the l-step ahead forecast of $\{X_i\}$ . $x_{t+l}$ can be expressed as a linear function of the past p traffic values, which is shown in

$$\begin{array}{cc}& {\widehat{x}}_t\left(l\right)=\sum _{i=0}^{\infty }{D}_i{x}_{t-i},\end{array}$$

(12)

where $D_i$ is the coefficient matrix of the past traffic values and ${\widehat{x}}_t(l)$ denotes the l-step ahead forecast of the time series $\{x_t\}$ .

The forecasting error of the time series $\{x_t\}$ is shown in

$$\begin{array}{cc}& e_t\left(l\right)=x_{t+l}-{\widehat{x}}_t\left(l\right).\end{array}$$

(13)

The minimum variance of the forecasting error above is denoted by

$$\begin{array}{cc}& \text{Va}{\text{r}}_{{\widehat{x}}_t\left(l\right)}\left[e_t\left(l\right)\right]=\min \left\{\mathrm{Var}\left[e_t\left(l\right)\right]\right\}.\end{array}$$

(14)

Hence, we also get the explicit expressions of ${\widehat{x}}_t(l)$ and $e_t(l)$ , which are shown in

$$\begin{array}{cc}& {\widehat{x}}_t\left(l\right)=\sum _{i=0}^{\infty }\hspace{0.17em}\sum _{j=0}^{\infty }{G}_{l+i}{I}_j{x}_{t-i-j},\hspace{1em}\forall \hspace{0.17em}l\ge 1,\\ e_t\left(l\right)=\sum _{i=0}^{l-1}\hspace{0.17em}\sum _{j=0}^{\infty }{G}_i{I}_j{x}_{t+l-i-j}.\end{array}$$

(15)

Theoretical and experimental results show that multistep prediction may bring about much greater forecast error and complexity [13], and hence we only give 1-step ahead forecast model for the resource-constrained wireless multimedia sensor networks.

For the ARMA $(\mathrm{2,1})$ model, the 1-step ahead forecast model and its associated forecast error are shown in

$$\begin{array}{cc}& {\widehat{x}}_t\left(1\right)=\sum _{i=0}^{\infty }\hspace{0.17em}\sum _{j=0}^{\infty }{G}_{1+i}{I}_j{x}_{t-i-j},\hspace{1em}\hspace{1em}{e}_t\left(1\right)=\sum _{j=0}^{\infty }{G}_0{I}_j{x}_{t+1-j}.\end{array}$$

(16)

The model is implemented on Matlab 7.0. The comparison between the real network traffic and the prediction network traffic is shown in Figure 4. The results show that the model can accurately predict the WMSNs traffic. Furthermore, the model has some benefits, such as linear computing and low complexity.

Figure 4

1-step ahead forecast of $X_i$ .

4.2. Traffic Prediction-Based Fast Rerouting Strategy

Firstly, set a traffic threshold value denoted by Max based on the processing capability of a sensor node. Denote the network traffic at time i by $X_i$ . We refer to ${\widehat{X}}_{t+1}$ as the 1-step ahead forecast of $\{X_i\}$ at the forecast origin t, and we refer to $P_t(1)$ as the probability that ${\widehat{X}}_{t+1}$ is greater than Max:

$$\begin{array}{cc}& P_t\left(1\right)=P\left({\widehat{X}}_{t+1}>\mathrm{Max}\mid X_t,X_{t-1},X_{t-2},\dots ,X_{t-i}\right).\end{array}$$

(17)

The probability distribution of $X_i$ is subjected to the probability distribution of $a_i$ . Here $a_i$ obeys the normal distribution; therefore $X_i$ also obeys the normal distribution. According to the statistical analysis of the collected multimedia sensor traffic, we can find that $X_i$ obeys the $N({\mu }_X,{\sigma }_X^2)$ distribution, where ${\mu }_X$ and ${\sigma }_X$ denote the mean and variance of the time series $\{X_i\}$ . Then we can obtain

$$\begin{array}{ll}& P\left({\widehat{X}}_{t+1}\le \mathrm{Max}\right)=P\left(\frac{{\widehat{X}}_{t+1}-{\mu }_X}{{\sigma }_X}\le \frac{\mathrm{Max}-{\mu }_X}{{\sigma }_X}\right)\\ =\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{\left(\mathrm{Max}-{\mu }_X\right)/{\sigma }_X}{e}^{t^2/2}dt,\\ P_t\left(1\right)=1-P({\widehat{X}}_{t+1}\le \mathrm{Max})\\ =1-\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{\left(\mathrm{Max}-{\mu }_X\right)/{\sigma }_X}{e}^{t^2/2}dt.\end{array}$$

(18)

As a consequence, we can obtain a traffic prediction-based fast rerouting strategy which is shown in Theorem 1.

Theorem 1.

A sufficient condition for the adaptive path switching is that the probability of the ${\widehat{X}}_{t+1}$ value greater than the preset traffic threshold Max is equal to $1-(1/\sqrt{2\pi }){\int }_{-\infty }^{(\mathrm{Max}-{\mu }_X)/{\sigma }_X}{e}^{t^2/2}dt$ .

Let us illustrate the results of the theorem using an example. The graphical depiction of the example is shown in Figure 5.

Figure 5

Graphical depiction of fast rerouting.

In the Figure, route 1 is a primary path from a source node to the base station. Both route 2 and route 3 are alternate paths for route 1.

Case I is that we do not use traffic prediction-based fast rerouting strategy. When node B is unable to process packets from other nodes, it takes the initiative to discard the packets. However, the node A continues to transmit the rest data packets until it finds the failure of node B. Node A will send the invalid message of node B to the source node. After that, the source node will forward the rest traffic through the alternate route 2 or route 3.

Case II is that we use traffic prediction-based fast rerouting strategy. When node B discovers that it satisfies the sufficient condition of Theorem 1, it will forward the urgent message to the source node via multihop wireless links at once. When the source node receives the urgent message, the efficient retransmission behavior is triggered. Obviously, the forwarding packets may bypass the fault area in advance and are smoothly rerouted through the alternate path 2, which can greatly improve the reliability of the data transmission and reduce the transmission delay. In addition, the other advantage of the fast rerouting strategy is that the data retransmission times, the energy consumption, and the routing control overhead may also be greatly reduced.

5. Theoretical Analysis and Performance Evaluation

5.1. Theoretical Analysis

5.1.1. Performance Analysis

Retransmission is one of the greatest impact factors on network performance due to various failures, such as network congestion, coverage hole, and routing hole. Some backgrounds and the symbol definitions are introduced as follows.

We firstly introduce the first-order radio model adopted in [14]. By using this approach, an energy loss of $d^2$ due to channel transmission is assumed. The energy $E_{Tx}(k,d)$ that a node dissipates for the radio transmission of a message of k bits over a distance d is due to running both the transmitter circuitry and the transmitter amplifier and is given by

$$\begin{array}{cc}& E_{Tx}\left(k,d\right)=E_{\text{elec}}*k+{\epsilon }_{\text{amp}}*k*d^2,\end{array}$$

(19)

where $E_{\text{elec}}$ is the transmitter circuitry dissipation per bit, which is supposed to be equal to the corresponding receiver circuitry dissipation per bit, and ${\epsilon }_{\text{amp}}$ is the transmit amplifier dissipation per bit per square meter.

Similarly, the energy $E_{Rx}(k)$ dissipated by a node for the reception of a k-bit message is due to running the receiver circuitry. It is given by

$$\begin{array}{cc}& E_{Rx}\left(k\right)=E_{Rx-\text{elc}}\left(k\right)=E_{\text{elec}}*k.\end{array}$$

(20)

Secondly, we refer to $E_c$ as the communication energy consumption of a node, λ denotes the number of links from a source node to the sink, l is an average path length of a link, $T_{\text{ave}}$ is the average transmission delay from a source node to the sink node, and ρ is the packet loss rate.

The probability of data successfully retransmitted at the first time is ${(1-\rho )}^{\lambda -1}$ . Let α be equal to ${(1-\rho )}^{\lambda -1}$ , and the probability of data successfully retransmitted at the second time is $(1-\alpha )\alpha$ . Similarly, we can obtain that the probability of data successfully retransmitted at the third time is ${(1-\alpha )}^2\alpha$ . The average retransmission time T is given by

$$\begin{array}{ll}& T=\alpha +2\alpha \left(1-\alpha \right)+3\alpha {\left(1-\alpha \right)}^2+\cdots \\ =\left[\frac{\alpha }{1-\alpha }\right]\times \frac{\left(1-\alpha \right)}{{\left[1-\left(1-\alpha \right)\right]}^2}=\frac{1}{\alpha }=\frac{1}{{\left(1-\rho \right)}^{\lambda -1}}.\end{array}$$

(21)

We combine (19) and (20) with (21) to get

$$\begin{array}{cc}& E_c=E_{Tx}+E_{Rx}=\frac{k}{{\left(1-\rho \right)}^{\lambda -1}}\left[2E_{\text{elec}}+{\epsilon }_{\text{amp}}{d}^2\right].\end{array}$$

(22)

Obviously, $E_c$ is proportional to $k{d}^2/{(1-\rho )}^{\lambda }$ , in which it must be noted that the communication energy consumption $E_c$ decreases proportional to every decrease in the ρ and λ values.

The average transmission delay from a source node to the sink node is given by

$$\begin{array}{cc}& T_{\text{ave}}=\frac{DlT}{B_w},\end{array}$$

(23)

where $B_w$ denotes the average available bandwidth of a sensor and D denotes the data to be transmitted.

Obviously, $T_{\text{ave}}$ is proportional to $lT/B_w$ , in which it must be noted that the $T_{\text{ave}}$ value increases proportional to every increase in the l and T values, and it increases proportional to every decrease in $B_w$ .

Our algorithm uses the fast rerouting strategy based on traffic prediction to bypass the fault area in advance and is smoothly rerouted through better alternate path. Compared with similar routing algorithms for WMSNs [5, 9], TPFR has lower T value, λ value, and ρ value and higher $B_w$ value. These parameters play an important role in improving the network performance, such as reducing the transmission delay, network energy consumption, and prolonging the network lifetime.

5.1.2. Control Overhead Analysis

We refer to $M_d$ as the size of a datagram, $M_i$ denotes the size of a control message, and $M_d$ is greater than $M_i$ . Then we let m denote the number of the retransmitted datagrams and $T_{\max }(T_{\max }<T)$ denote the maximum number of retransmissions. Additionally, ω denotes the path length from a source node to a failure node and $E_{\epsilon }$ denotes the energy consumption of a processor on executing the traffic prediction algorithm.

In this paper, the routing algorithms without the rerouting mechanism are named non-TPFR.

For the non-TPFR algorithms, from the failure to the fault recovery, the data packets $D_1$ and the energy consumption $E_1$ generated by the algorithms are given by the following, respectively:

$$\begin{array}{cc}& D_1=m{M}_d{T}_{\max }+\omega M_i,\end{array}$$

(24)

$$\begin{array}{cc}& E_1=(E_{\text{elec}}+{\epsilon }_{\text{amp}}*d^2)\times [m{M}_d{T}_{\max }+\omega M_i]+E_{\text{elec}}\omega M_i.\end{array}$$

(25)

For our proposed algorithm, from the failure to the fault recovery, the data packets $D_2$ and the energy consumption $E_2$ generated by TPFR are given by the following, respectively:

$$\begin{array}{cc}& D_2=\omega M_i,\end{array}$$

(26)

$$\begin{array}{cc}& E_2=\left(2E_{\text{elec}}+{\epsilon }_{\text{amp}}\times d^2\right)\times \omega M_i+E_{\epsilon }.\end{array}$$

(27)

Obviously, from the failure to the fault recovery in networks, $D_1$ generated by the non-TPFR algorithms is greater than $D_2$ generated by our algorithm. In addition, the energy consumption of the processing module and the sensing module is far less than that of the wireless communication module. For example, the energy consumption of the 1 bit information transmitted 100 meters is roughly equivalent to that of the execution of the 3000 computer instructions. Thus, $E_1$ is greater than $E_2$ .

In summary, from the failure to the fault recovery, the efficiency of our algorithm with more local computations is better than the non-TPFR algorithms with more communications and retransmissions. Moreover, our algorithm has very strong practicality, and it has important implications for improving the survivability of WMSNs.

5.2. Performance Evaluation

5.2.1. Simulation Parameters Settings

In this part, we simulate our proposal using NS-2 version 2.29 which is a discrete event network simulator for over 100 experiments with various random topologies. The network size is 400 m × 400 m deployed with 400 nodes for duration of 1200 time rounds. The traffic is CBR of 600 packet/second, and the packet size is 316 bytes. The video traces come from MDC Foreman video test sequences [15] provided by a study group for the video tracking in Arizona State University. In the current video traces, there are 300 frames, and the frame rate is 30 frames/s, corresponding to a frame period equivalent to 36 ms. Additionally, we assume that the frame period is equal to the size of a transmission window. We adopt IEEE802.11 for the MAC layer as shown in Table 2 which lists the parameters we used in our simulation.

Table 2

Simulation environment and used parameters.

Simulation parameter	Value
Network size	$4\mathrm{00}\times 4\mathrm{00}$  m2
Node number	400
Link layer	LL
MAC layer	IEEE802.11
IFQ type	Queue/DropTail/PriQueue
IFQ length	10
Antenna type	Antenna/OmniAntenna
Physical type	Phy/WirelessPhy
Channel type	Channel/WirelessChannel
Energy model	EnergyModel
Initial energy of a node	0.5 J
Bandwidth	2 Mbit/s
Traffic threshold	1.7 Mbit/s

In the simulations, we focus on measuring the performance metrics after the network has set up to include the average end-to-end delay, the average packet delivery ratio, the peak signal to noise ratio, the energy consumption, the remaining alive nodes, and the communication overhead. To prove the effectiveness of TPFR, we have also implemented the AntSensNet algorithm (ant-based multi-QoS routing) [5] and PEMuR (power efficient multimedia routing) [9], and we compared the simulation results.

5.2.2. Simulation Results Evaluation

Figure 6 shows the end-to-end delay, which is one of the important QoS parameters as the real-time multimedia packets have strict playout deadlines. We compare the average end-to-end delay of our algorithm combined with the AntSensNet routing discovery technique with the other routing protocols (PEMuR and AntSensNet). As shown in the figure, the TPFR design methodology outperforms the two classical multimedia routing protocols.

Figure 6

End-to-end delay performance.

It is shown clearly that with the increase of node failure rate, our fast rerouting design has the minimum end-to-end delay and outperforms the other routing protocols because it depends on selecting a better alternate path in terms of the bandwidth, the minimum hop count, and the remaining energy before a node failure through the proposed traffic prediction mechanism. It is worth to note that PEMuR and AntSensNet only perform well at low node failure rate or link breaks, but with higher node failures and link breaks, the end-to-end delay increases exponentially due to the various failures of cluster heads which cause lost packets retransmission frequently. More importantly, the two protocols lack the rerouting mechanism.

The packet delivery ratio involves the ratio of successfully delivered data packets to the total data packets sent from the source to their destination. The average packet delivery ratio (PDR) is shown in Figure 7 where our rerouting algorithm outperforms the other algorithms, which confirms the previous theoretical analysis. We obtain this result due to the use of the traffic prediction technology that bypasses various failure areas such as network congestion, any node failure or link break, besides the selection of paths with better link quality based on the bandwidth and the remaining energy. Thus the number of lost packets significantly decreases. Such results were expected, and this investigation confirms the authors' hypotheses.

Figure 7

Packet delivery ratio.

Figure 8 shows the average PSNR of the Foreman video when a node failure rate ranges from 0 to 0.3. We can see that the perceived video quality (PSNR) was higher for the simulations using TPFR when compared to the other protocols under the nonuniform node distribution. And the simulation curve of TPFR is consistent with the original video sequence. This is because the protocols PEMuR and AntSensNet are not able to efficiently handle the retransmission of video streams when node failures or link breaks occur. They are only specialized in minimizing the video distortion under an errorless transmission environment.

Figure 8

Received video quality of Foreman video.

With respect to the average energy consumption, our proposed algorithm has less energy consumption than the AntSensNet algorithm as shown in Figure 9 with different time rounds because of the many benefits that they get from the traffic prediction-based fast rerouting. However, the PEMuR algorithm has better energy efficiency before 400 time rounds because both AntSensNet and TPFR algorithms lack sufficient information to find appropriate routes during this period. After this period, when the algorithms converge and the ants have gathered enough node and route information, the quality of routes discovered for our algorithm is superior to that found by PEMuR. In a word, with increasing time and failures, we notice that PEMuR and AntSensNet algorithms suffer from packet collisions and interferences and consume more energy for retransmitting lost packets, while TPFR exploits the benefits from the adaptive fast rerouting scheduling to prevent such problems and hence has less energy consumption.

Figure 9

Energy consumption of network.

The depletion of nodes over time is a typical metric of the energy efficiency of a routing protocol. Figure 10 shows the number of alive nodes in networks has changed over time, and the TPFR protocol is significantly better than the other routing protocols in retarding the time of node depletion. For the PEMuR protocol, the first node depletion time is at 311 rounds and the last node depletion time is at 791 rounds. For the AntSensNet protocol, the first node depletion time is at 702 rounds and the last node depletion time is at 876 rounds. For our proposed scheme, the first node depletion time is at 927 rounds and the last node depletion time is at 1129 rounds. The communication module consumes more energy than other modules in a wireless multimedia sensor. In our scheme, we use more traffic prediction computations instead of communications. Hence, our protocol has lower communicational energy consumption and can prolong the network lifetime.

Figure 10

Remaining alive nodes in network.

The extra control packets are required in order to periodically monitor and maintain path conditions. And the routing overhead is shown in Figure 11. With increasing time, the mean routing overhead is reduced for the three algorithms; however, TPFR has a lower reduction of routing overhead than other algorithms. Due to such periodic updates, they constantly require a certain amount of routing overhead. The overhead of PEMuR can be reduced by piggybacking the control information on data packets if there is traffic between a sink and cluster heads. And that of AntSensNet can be reduced by embedding data into forward ants (a specimen of data ants) and piggybacking the pheromone information on data packets. In fact, TPFR is an improved AntSensNet scheme. TPFR uses computational overhead instead of communicational overhead, and hence it has lower routing overhead. Additionally, the simulation result remains consistent in the theoretical analysis of Section 5.1.2.

Figure 11

Routing overhead.

6. Conclusions

This paper presented TPFR, a novel fast rerouting algorithm over WMSNs, which aims at both energy savings and high QoS. The innovation of our proposed algorithm lies in the combined use of ant-based hierarchical routing protocol using multiple QoS metrics along with a traffic prediction-based fast rerouting algorithm. The adopted rerouting algorithm not only proposes an energy efficient rerouting policy, but also manages the network load according to the energy residues of the nodes and prevents useless data retransmissions through the proposed use of the intelligent rerouting algorithm. In this way, an outstanding level of energy efficiency and high QoS under the node failures or link breaks network environments is achieved.

Extended simulation tests performed showed that the utilization of TPFR enables the considerable retardation of the energy depletion of the video nodes. The enhancement in energy performance metrics provided by TPFR becomes even greater in the case of a nonuniform node energy distribution. Additionally, it was shown that TPFR succeeds in maintaining high levels of the average end-to-end delay, the packet delivery ratio (PDR), the perceived video quality (PSNR), and routing overhead for a nonuniform energy distribution. These advantages of TPFR enhance the belief that this scheme is indeed capable of achieving efficient multimedia stream communication in real-life applications.

The authors of this paper have already started to study this research work under the network invasion. We plan to apply the intrusion tolerance approach to solve a new challenging problem. According to this approach, even if the network is under DDoS attack, WMSNs is still able to provide available quality of service.