Skip to main content


Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.10.2013 | Ausgabe 4/2013 Open Access

Wireless Personal Communications 4/2013

A Robust and Efficient Cross-Layer Optimal Design in Wireless Sensor Networks

Wireless Personal Communications > Ausgabe 4/2013
Mingwei Li, Yuanwei Jing, Chengtie Li

1 Introduction

A wireless sensor networks (WSNs) is a node set formed by several sink nodes and a large amount of sensor nodes, and they are deployed in wireless sensor regions. Those nodes are small, low-power, inexpensive with the capabilities of sensing, computing and wireless communication [ 1]. Such a sensor network can be random deployed in remote areas or hostile terrains, without the infrastructure support from the outside world. The tiny sensor nodes can cooperate in forming an autonomous and robust data computing and communication distributed system for distributed sensing and automated information gathering. When designing a WSN system, there are a number of challenges which can be generally classified into two significant problems [ 2].
Firstly, information management architecture has to be designed to address information conflict and interaction that occurs when gathering information from many sensors. If nodes suffers from heavier work, which will cause the packets loss or even network congestion. In [ 36], the authors develop cross-layer solutions which link capacity detection with adjusting persistence probability at the MAC layer, the flow rate control at the transport layer and the routing design at the network layer. Congestion is a difficult problem in WSNs, which not only wastes the scarce energy due to a large number of retransmissions and packet drops, but also hampers the event detection reliability. Two types of congestion could occur in sensor networks [ 7]. The first type is node-level congestion that is when the packet-arrival rate exceeds the packet service rate, buffer overflow may occur and can result in packet loss, and increased queuing delay. The second type is link-level congestion that is related to the wireless channels which are shared by several nodes. In this case, collisions could occur when multiple active sensor nodes try to seize the channel at the same time.
Secondly, since the sensor nodes in WSNs are powered by very low voltage batteries and they are deployed in the order of lots of nodes, replacing and recharging the batteries of so many nodes may realistically be considered infeasible. Hence, the other challenge for the WSNs is to design energy-efficient routing protocols [ 812] which guarantees the persistence and balances the energy consumption of the network.
Analyzing two problems jointly, we denote that there is intrinsic tradeoff between throughput maximization and energy consumption minimization in WSNs. Although both have been extensively studied in recent years, few works consider them together and study the tradeoff between them [ 13, 14].
In this paper, we study the optimal function problem in WSNs with the goal of achieving efficient resource allocation through cross-layer design. Using Lagrangean decomposition, the problem can be vertically decomposed into three subproblems: congestion control in transport layer, routing in network layer, and scheduling in link layer, which interact through congestion ratio. Data transmission optimization through WSNs is mainly done by the implementation of a distributed compressed sensing (CS) embedded algorithm in order to reduce the number of transmitted bits, thus reduce the congestion occurrence and the energy consumption. The resources can be allocated more and more to the channel in the case of not causing more severe congestion, which can avoid conservatively reducing resources allocation for eliminating congestion. That results in the low utilization rate. The stability of the resulting system is proved, and its performance is characterized with respect to an ideal reference system. In addition, the proposed algorithm should minimize communication energy which is proportional to the compressed ratio. The relative error of the CS is proved that is no more than 0.1, which indicates that the CS is competent to solve the cross-layer optimal problem.
The remainder of this paper is organized as follows. Section 2 introduces relevant background description, CS theory and network max-optimal function problem. Section 3 discusses the optimal algorithm consisting in congestion control, routing and scheduling algorithm. Section 4 presents theoretical analysis results for the above algorithms. Simulation results will be followed in Sect. 5 which evaluates the performance of the proposed algorithm. Concluding remarks are stated in Sect. 6.

2 Relate Problem

In this section, we model the optimal function in WSNs as a constrained multi-objective problem. We consider a WSNs consisting of a set \(S=\{1, 2, \ldots , s\}\) of sensor nodes and \(N=\{1, 2, \ldots , n\}\) of sink nodes. The sensor nodes can transfer their sensing data to the sink nodes over a set \(L=\{1, 2, \ldots , l\}\) of links, each of which has a fixed capacity \(c_d\) bits per second when active [ 15].
Compressed sensing (CS) is used to compact redundant data so as to reduce bits transmission, which can lessen congestion. In particular, for any \(p\)-sparse signal \(x_s(t)\in \mathfrak R ^{b \times 1}\) (i.e., \(x_s(t)\) contains only \( p \) nonzero elements), which is projected into given sensing waveform \(\varPhi \in \mathfrak R ^{r \times b}, r< p\ll b\), then measurement vector \(y=\varPhi x_s(t)\) is obtained which is far less than original transmitted bits, where \(\varPhi \) meets restricted isometry property (RIP) [ 16]. Then we can exactly recover x from y with high probability.
Definition 1
( Restricted isometry property) Let \(\varPhi \) be an \(r\times b\) matrix. If \((1-\delta _p)\Vert x_s(t)\Vert ^{2}_{2}\le \Vert \varPhi x_s(t)\Vert ^{2}_{2}\le (1+\delta _p)\Vert x_s(t)\Vert ^{2}_{2}\) holds for all \(x_s(t)\in \mathfrak R ^{b\times 1}\) with no more than \(p\) nonzero elements, the measurement matrix \(\varPhi \) is said to satisfy the restricted isometry property of order \(p\in N\) with parameter \(\delta _p \in (0,1) \), or, in shorthand, \(\varPhi \) satisfies RIP \((p,\delta _p )\).
One of the critical problems in algorithms designing for WSNs is to save energy consumption. Hence, finding a proper measurement matrix \(\varPhi \) is necessary, which satisfies the RIP. While the sampling process is simply a random linear projection, the reconstruction to find the sparsest signal from the received measurements is highly non-linear process, and the computational complexity depends on the structure of \(\varPhi \). A popularly used measurement matrix is a random matrix of i.i.d. random variables from a sub-Gaussian distribution, such as Gaussian or Bernoulli [ 17, 18]. However, they are quite costly to realize random matrices in practical sensing applications as they require very high computational complexity and huge memory buffering due to their completely unstructured nature [ 19]. For example, to process a \(512 \times 512\) image with 64 K measurements, a Bernoulli random matrix requires nearly gigabytes storage and giga-flop operations, which makes both the sampling and recovery processes very expensive and in many cases, unrealistic [ 20]. In this paper, Toeplitz matrix is to be chosen. Compared with Gaussian or Bernoulli random matrices, Toeplitz matrix has the advantage that it requires a reduced number of random numbers to be generated. More importantly, there is fast matrix-vector multiplication routines which can be exploited in recovery algorithms. Furthermore, it arises naturally in certain applications such as identifying a linear time-invariant system. In addition, in [ 21], the authors considered Toeplitz matrix as measurement matrices which naturally arise in multichannel and multidimensional filtering applications, and it is shown that the probability of exact reconstruction is also high. Therefore, Toeplitz matrix is more suitably applied to WSNs.
The aggregation transmitting capacity meets \(F\le \sum _{i=1}^{b}x_i(t)\le 2F\), and the aggregation capacity after compressed is \(\varPhi F\le \sum _{i=1}^{r}y_i(t)\le 2\varPhi F\). \(r/b\) is defined as compressed ratio. Let \(f_l\ge 0\) denote the amount of capacity allocated to link \(l\). We define the source service requirements by a linear function \(Hx_s(t)\) of the source transmitted signal \(x_s(t)\), and represent the source service capacity by a linear function \(Af\) of the link capacities \(f\), since the service requirement should not exceed the allocated service capacity, the following inequality constraint is provided \(Hx_s(t)\le Af\).
We know by Chen [ 22] that the capacity allocation, energy consumption can be associated with the optimal function so as to reach kinds of fairness and economized energy by maximizing the aggregate optimal functions. Based on the above discussion, we can formulate the fair signal allocation problem in WSNs as a network optimal maximization problem:
$$\begin{aligned} max \sum \limits _{s\in S} {Z_s (x_s(t))} \end{aligned}$$
$$\begin{aligned} \left\{ \begin{array}{l} Hx_s(t)\le Af\\ y(t)=\varPhi x_s(t)\\ \end{array}\right. \end{aligned}$$
It is difficult to solve, though the constraints are convex problems. Lagrange duality method in [ 23] is introduced to decompose the problem into several subproblems, which can be easily solved ( 1).
$$\begin{aligned} L(p,x,y,\varPhi )&= \sum _{s\in S} {Z_s (x_s(t))}+ p(t)\left[ \begin{array}{cc} H&{}0\\ -\varPhi &{} I \\ \end{array}\right] \left( \begin{array}{c} x_s(t)\\ y(t)\\ \end{array}\right) + p(t) \left( \begin{array}{c} Af\\ 0 \\ \end{array}\right) \end{aligned}$$
where \(p(t)\) denotes congestion ratio, meeting \(0\le p(t)\le I, x_s(t)\) represents transmitted signal, \(f\) is allocated capacity of the link.
Signal constraints are described at the network layer by linear inequalities in terms of user service requirements and allocated link capacities. The resource allocation of the network is then formulated as the optimal problem with schedulability and signal constraints.

3 Algorithm Design

Congestion control  Transmitted signal is adjusted by the congestion ratio \(p(t)\)
$$\begin{aligned} x_s(t)&= arg max \sum \limits _{s\in S} {Z_s (x_s(t))}- p(t)\left[ \begin{array}{c@{\quad }c} H &{} 0\\ -\varPhi &{} I \\ \end{array}\right] \left( \begin{array}{c} x_s(t)\\ y(t) \\ \end{array}\right) \end{aligned}$$
Transmitted signal \(x_s(t)\) can be transformed into \(y(t)\) by CS technique, which can reduce the bits numbers of the signal in the transmitted channel. Owing to \(p(t)\ge 0, Hx_s(t)\ge 0\),
$$\begin{aligned} x_s(t)&= \left( \varPhi \left( I+p(t) \left( \begin{array}{c} H \\ -\varPhi \end{array}\right) \right) \right) ^{-1} \left[ arg max \sum _{s\in S} {Z_s(y_s)}-\varPhi p_2(t)y(t)\right] \end{aligned}$$
Reconstruction algorithm  The transmitted signal is \(y(t)\) in the source so as to relieve the congestion and save energy, but the signal should be reverted to the original signal in the sink nodes, that is reconstruction signal. To achieve this process, the \(l_1\)-penalized optimization problem is applied, which goes by the name of Basis Pursuit Denoising [ 24] or Lasso in the statistics community after [ 25]:
$$\begin{aligned} J(\varPhi ,x_s(t))&= \frac{1}{2}\Vert y-\varPhi x_s(t)\Vert _{2}^{2}+\gamma (\varPhi )\Vert x_s(t)\Vert _{1} \end{aligned}$$
\(\gamma (\varPhi )\) is the function of \(\varPhi \). Starting with a \(\varPhi \), constructed from random independent and identically distributed columns, we apply a gradient descent method to minimize ( 6). The achieving procedure is presented as follows:
Step 1  In order to apply the proposed method to all elements of matrix \(\varPhi \), we compute the gradient of \(J\) with respect to \(\varPhi \)
$$\begin{aligned} \frac{\partial J}{\partial \varPhi }=-(y(t)-\varPhi x_s(t))x_s^{T}(t)+\frac{\partial \gamma }{\partial \varPhi }\Vert x_s(t)\Vert _{1} \end{aligned}$$
\(\varPhi \) is calculated by \(\frac{\partial J}{\partial \varPhi }=0\);
Step 2
$$\begin{aligned} \frac{\partial J}{\partial x}=-(y(t)-\varPhi x_s(t))\varPhi ^{T}+\gamma (\varPhi )\varPsi =0 \end{aligned}$$
$$\begin{aligned} \varPsi =\left( \begin{array}{c@{\quad }c@{\quad }c@{\quad }c} 1 &{} 1 &{} \ldots &{} 1 \\ 1 &{} 1 &{} \ldots &{} 1 \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ 1 &{} 1 &{} \ldots &{} 1 \\ \end{array}\right) \end{aligned}$$
In virtue of \(\varPhi \) reconstruction signal \(\hat{x}\) is obtained.
Scheduling algorithm  The transmitted data flow per second [ 23] is
$$\begin{aligned} f\in arg max~p^{T}A(f) \end{aligned}$$
But it is transmitted by a slower rate in the link \(l\), that result in resource insufficient utilization. We will improve the algorithm:
$$\begin{aligned} max \tilde{f} \in arg max~A(f);\, min \tilde{f} \in arg max~ p^{T}A(f) \end{aligned}$$
The resource allocation method can achieve that the biggish signal (that is the maximum signal transmitted rate) is transmitted if that does not lead to farther congestion when congestion exit, and the maximal signal is transmitted when congestion does not exit in the WSNs. The resources can be allocated more and more to the channel in the case of not causing more severe congestion, which can avoid conservatively reducing resources allocation for eliminating congestion. That results in the low utilization rate.
Routing algorithm Channel selection is based on scheduling algorithm. The destination would be selected if the margin of data flow, transmitted in destination from the different nodes, is maximal. Then the channel is determined. This idea makes avoidance congestion and fair allocation resource. \(f_{i,j}^{v}\) presents the aggregate capacity transmitted from link \((i,j)\) to node \(v\). Also note that the scheduling problem is solved by the following assignment,
$$\begin{aligned} \left\{ \begin{array}{l} \tilde{f}_{i,j}^{v}~,~ if~~ v \in arg max \left( \left( I-\left( p_{i}^{v}\right) ^{T}\right) A_{iv}(f)-\left( I-\left( p_{j}^{v}\right) ^{T}\right) A_{jv}(f)\right) \\ 0,~else\\ \end{array}\right. \end{aligned}$$
The algorithm motivates a joint congestion control, scheduling and routing design which sources individually adjust signal according to the local congestion ratio at the transport layer, and node \(i\) solve the scheduling ( 7) and route data flows accordingly at the network/link layer. Congestion control is not an end-to-end scheme, so there is no need to maintain end-to-end paths and no communication overhead for congestion control.
Note that there does not exist an explicit routing component in the dual decomposition. Instead, the routing is implicitly solved in ( 5) if the set of paths from which a source can choose is given, and solved in ( 7) if no path is prespecified for the source. We see that, by dual decomposition, the flow optimization problem decomposes into separate local optimization problems of transport, network and link layers respectively, and they interact through congestion ratio. In addition, node-level congestion is effectively restrained as signal is compressed by the sensing process in ( 5), from which traffic is considerably reduced. Link-level congestion is significantly relieved in ( 7).

4 Performance Analysis

4.1 Energy Consumption Analysis

Energy consumption is one of the most important consideration issues in WSNs, when kinds of network protocol are designed. In this section, minimal energy consumption of the algorithm based on CS technique is studied. The relation is obtained between the energy and congestion ratio. In WSNs, the energy consumption of each source node sending data to the sink is associated with transmission hops and transmission distance. If the optimal transmission distance and hops are found, the energy consumption will be reduced to a minimum, so that the data transmission path is energy efficient. Let the distance from the source node to the sink be \(D\) and the source node transmit a b-bit packet to the sink through \(h\) hops. The distance of the \(i\)th hop is \(d_i\), so that the total energy consumption [ 26] is
$$\begin{aligned} E=\sum \limits _{i=2}^{h}E_{RX}(b)+\sum \limits _{i=1}^{h-1}E_{TX}(b,d_{i}) \end{aligned}$$
which is not congestion occurrence. If the node receives an \(b-bit\) packet over distance \(d_i\), the energy consumption of the node is \(E_{RX}(b)=bE_{elec}\), where \(E_{elec}\) denotes the energy/bit consumed by the transmitter electronics.
If the node transmits a b-bit packet over distance \(d_i\), the energy consumption of the node is \(E_{TX}(b,d_{i})=b\epsilon d_i^{4}\), \(\epsilon \) notes the energy dissipated in the transmission amplifier.
$$\begin{aligned} E_{TX}^{\varDelta }(b,d_{i})=(1+p_i)E_{TX}(b,d_{i}) \end{aligned}$$
represents the energy consumption which the node transmits \(b-bit\) packet over distance \(d_i\), when congestion occurrence.
$$\begin{aligned} E_{RX}^{\varDelta }(b)=(1+p_i)E_{RX}(b) \end{aligned}$$
represents the energy consumption which the node receives \(b-bit\) packet over distance \(d_i\), when congestion occurrence. Let \(\displaystyle d_1=d_2=\cdots =d_n=\frac{D}{h}\). The energy consumption will be discussed when node-level and link-level congestion occur simultaneously.
Link-level congestion energy consumption
Energy consumption of transmitted data is increased if link-level congestion occurs, which will lead to data retransmission. Energy consumption of transmitted data and congestion ratio have the relationship as follow: \(E_{TX}^{\varDelta }(b,d_{i})=(1+p_i)E_{TX}(b,d_{i})\). Total energy consumption is
$$\begin{aligned} E_{link}=\sum _{i=2}^{h}E_{RX}(b)+\sum _{i=1}^{h-1}E_{TX}^{\varDelta }(b,d_{i}) \end{aligned}$$
to solve the ( 12) minimal value, let
$$\begin{aligned} E_{link}^{,}(n)=(2+p_{h-1})bE_{elec}+\sum \limits _{i=1}^{h-1}\left[ (1+p_{i})\frac{-4D^{4}b\epsilon }{h^{5}}\right] +\frac{D^{4}b\epsilon }{p_{h-1}h^{4}}=0 \end{aligned}$$
with the optimal number of hops: \(h_{opt}\), the total energy consumption for data transmission will be reduced to a minimum and the routing path is energy efficient.
Node-level congestion energy consumption
Energy consumption of received data is increased if node-level congestion occurs. Energy consumption of received data and congestion ratio have the relationship as follow: \(E_{RX}^{\varDelta }(b)=(1+p_i)E_{RX}(b)\). Total energy consumption is
$$\begin{aligned} E_{node}=\sum \limits _{i=2}^{h}E_{RX}^{\varDelta }(b) + \sum \limits _{i=1}^{h-1}E_{TX}(b,d_{i}) \end{aligned}$$
$$\begin{aligned} E_{node}^{,}(n)=(2+p_{h-1})bE_{elec}+ \frac{-3D^{4}b\epsilon }{h^{4}} +\frac{4D^{4}b\epsilon }{h^{5}}=0. \end{aligned}$$
with the optimal number of hops: \(h_{opt}\). The total energy consumption for data received will be reduced to a minimum and the routing path is energy efficient.
Two congestion energy consumption
Energy consumption of received and transmitted data is increased if node-level and link-level congestion occurs simultaneously. Energy consumption and congestion ratio have the relationship as follow:
$$\begin{aligned} E_{both}=\sum \limits _{i=2}^{h}E_{RX}^{\varDelta }(b)+\sum \limits _{i=1}^{h-1}E_{TX}^{\varDelta }(b,d_{i}) \end{aligned}$$
$$\begin{aligned} E_{both}^{,}(n)=(2+p_{h-1}+p_h)bE_{elec}+\sum _{i=1}^{h-1}\left[ (1+p_{i})\frac{-4D^{4}b\epsilon }{h^{5}}\right] +\frac{D^{4}b\epsilon }{p_{h-1}h^{4}}=0 \end{aligned}$$
with the optimal number of hops: \(h_{opt}\). The total energy consumption for data received will be reduced to a minimum and the routing path is energy efficient.
We can come to conclusion by the above analysis,
$$\begin{aligned} E~<~min(E_{node},E_{link})~<~E_{both} \end{aligned}$$
which accords with routine environmental requirements of WSNs. The case is occurred when signal is not be compressed. If we suppose energy consumption of data uncompressed \(E_{DR}=E_{both}\), then energy consumption of data compressed \(\displaystyle E_{DR}=\frac{r}{b}E\), so we can come to conclusion that
$$\begin{aligned} E_{DC}<\frac{r}{b}min(E_{node},E_{link})<\frac{r}{b}E_{both}=\frac{r}{b}E_{DR}. \end{aligned}$$
It denotes that CS technique effectively alleviate congestion and greatly reduce energy consumption.
In WSNs, energy consumption of transmission and sampling account for the main part, and computing use few part. Hence, decrease transmission and sampling by compressed signal is significant necessary, in spite of data compression and reconstruction consume a part of energy. CS is not only reduction congestion, but also decrease energy consumption.

4.2 CS Accurate Ratio

In the congestion control procedure, inspired by the theory of CS, the sparse signals are transmitted by compressed in the sources, then the transmitted signals are recovered in the sink nodes. This process can result in alleviating congestion and reducing energy consumption. However, do CS effect of data transmission accuracy? We discuss the problem. In the general case, optimal function \(Z_s (x_s(t))\) selects \(\log _{0.5}x_s(t)\), and compressed signal \(\displaystyle \frac{F\varPhi }{r}\le y_{min}\le y_{max}\le \frac{3F\varPhi }{r}\). Suppose \(p(t)\left( \begin{array}{c} H\\ -\varPhi \end{array}\right) \le \displaystyle \frac{I}{2}, -I/2\le \varPhi \le I/2, r/b\le 1/4\). CS error ratio is defined as: \(\displaystyle \eta =\frac{\Vert \hat{x}-x_s(t)\Vert }{\Vert x_s(t)\Vert }\) [ 22], then
$$\begin{aligned} \Vert \hat{x}-x_s(t)\Vert \!=\! \left\| min\Vert x_s(t)\Vert \!-\!\left( 1+p(t)\left( \begin{array}{c} H\\ -\varPhi \end{array}\right) \varPhi \right) ^{-1} \left[ argmax \sum \limits _{s}\left( Z_{s}(x_s(t)) \right. -\varPhi p_2y\right] \right\| \nonumber \\ \end{aligned}$$
Let \(Q=\left( \begin{array}{c} H\\ -\varPhi \end{array}\right) \), formulate ( 15) is transformed
$$\begin{aligned}&\left\| min\Vert x_s(t)\Vert -\varPhi ^{-1}\left( 1+p(t)Q\right) ^{-1}\left[ argmax \sum _{s}(Z_s(x_s(t))) -\varPhi p_2y\right] \right\| \\&\quad \le \left\| 2F/\omega -\varPhi ^{-1}\left( I+p(t)Q\right) ^{-1}[y^{\varDelta } -\varPhi p_2y]\right\| \end{aligned}$$
\(\omega \) is the number of \(x_i(t)\). Let \(R=\varPhi ^{-1}(I+p(t)Q)^{-1}\), substituting to \(\displaystyle \eta =\frac{\Vert \hat{x}-x_s(t)\Vert }{\Vert x_s(t)\Vert }\), obtains
$$\begin{aligned} \eta \le \frac{\Vert \frac{2R^{-1}F}{b}-y^{\varDelta } +\varPhi p_2y\Vert }{\Vert y^{\varDelta } -\varPhi p_2y\Vert }\le \frac{\Vert \frac{2R^{-1}F}{b}-\frac{F\varPhi }{r}+\varPhi p_2\frac{3F\varPhi }{r}\Vert }{\Vert \frac{F\varPhi }{r}+\varPhi p_2\frac{3F\varPhi }{r}\Vert }\le \frac{\Vert \frac{3r}{b}I-3\varPhi -I\Vert }{\Vert I-3\varPhi \Vert } \end{aligned}$$
Owing to \(r/b\le 1/4, -I/2\le \varPhi \le I/2, \eta \le 0.1\). That denotes the accurate ratio of signal transmit is higher.

4.3 Stability Analysis

If sparse signal \(x_s(t)\) satisfies the congestion control structure [as shown in Eq. ( 5)], and the corresponding measurement matrix is contaminated with noise: \(y(t)=\varPhi x_s(t)+\varepsilon \), which the sampling matrix \(\varPhi \) satisfies the RIP, then the original signal stabilize to the optimal signal \(x^{*}\).
Suppose the optimal transmitted signal described by ( 5) is \(x^{*}\). Consider Lyapunov function \(V=\Vert x_s(t)-x^{*}\Vert \), then we compute the gradient of \(V\) with respect to \(p(t)\)
$$\begin{aligned} \frac{\partial V}{\partial p}&= \displaystyle 2\frac{\partial x_s^{T}(t)}{\partial p}(x_s(t)-x^{*})\\&= 2\left[ \frac{\partial R}{\partial p} \left( arg max \sum _{s\in S} {Z_s(y_s)}-\varPhi p_2(t)y(t) \right) +R\varPhi \left( \begin{array}{c} 0\\ 1\end{array}\right) y(t)\right] \\&\times (R\times argmax \sum _{s\in S} {Z_s(y_s)}-R\varPhi p_2(t)y(t)-x^{*}) \end{aligned}$$
Owing to \(Z_s(y_s)=\log _{0.5}y_s, \displaystyle y^{*}=\frac{F\varPhi }{r}\),
$$\begin{aligned} x^{*}&= \left( \varPhi \left( I+p(t)\left( \begin{array}{c} H\\ -\varPhi \end{array}\right) \right) \right) ^{-1}\left[ arg max \sum _{s\in S} {Z_s(y_s)}-\varPhi p_2(t)y^{*}\right] \end{aligned}$$
$$\begin{aligned} \frac{\partial V}{\partial p}&= 2\left[ \frac{\partial R}{\partial p}y^{\varDelta }+\left( R\varPhi \left( \begin{array}{c} 0\\ 1\end{array}\right) -\frac{\partial R}{\partial p}\varPhi p_2(t)\right) y\right] \left( R\varPhi p_2(t)(y(t)-y^{*})\right) \end{aligned}$$
Formulation ( 16) can be regarded as the quadratic function of \(y\), then the zero solution of ( 16) is
$$\begin{aligned} y_1(t)=-\left( R\varPhi \left( \begin{array}{c} 0\\ 1 \end{array}\right) -\frac{\partial R}{\partial p}\varPhi p_2(t)\right) ^{-1}\frac{\partial R}{\partial p}y^{\varDelta }\,;\,y_2(t)=y^{*}. \end{aligned}$$
We can reach that \(y_1(t)<0, y_2(t)>0\) whereas the value of meeting conditions \(y(t)>y^{*}\), so we can conclude \(\displaystyle \frac{\partial V}{\partial p}<0\), that is the transmitted signal is stable. \(\square \)

4.4 Computational Complexity Analysis

Generally speaking, CLOD has some additional benefits compared to completely independent random CS matrices such as Gaussian random matrices. First, CLOD is more efficient to generate and store. An \(r\times b\) CLOD only requires the generation and storage of \(p\) independent realizations of a random variable and pr positions, while a fully random matrix of the same size requires the generation and storage of \(rb\) random quantities. In addition, the use of CLOD in CS applications leads to a general reduction in computational complexity. Performing a matrix-vector multiplication between a fully random \(r\times b\) matrix and an \(r\times 1\) vector requires \(rb\) operations. In contrast, the complexity of multiplication by a CLOD can be reduced to \(pr\) operations, resulting in a significant speedup of the CS reconstruction procedure. Depending on the computational resources available, this speedup can literally be the difference between intractable and solvable problems. Table 1 summarizes the computational complexity and practical advantages between CLOD and a random measurement matrix.
Table 1
Practical feature comparison
Random matrix
Storage requirement
\(+\) pr
Sensing complexity
Reconstruction complexity at each iteration
Fast computability

5 Simulation

In this section, we evaluate the performance of the proposed protocol CLOD under different scenarios by NS-2. Different aspects of CLOD are compared with EOR [ 26], LEO [ 27], MRE [ 28]. The performance of CLOD is researched with respect to energy consumption, throughput, congestion ratio and stability. Simulation results demonstrate that CLOD outperforms all the protocols considered in the research with respect to the throughput and energy consumption. The throughput is defined for comparative evaluation of the above mentioned protocols: throughput is the rate of total constant bit rate packets received at sink and total packets sent. In our simulation, we use 10–120 sensor nodes in our numerical experiments and the positions of the nodes are randomly generated in an area of size \(50 \times 50\). We consider signals of length N  \(=\) 200. The sensing matrix \(\varPhi \) of size \(100 \times 200\) was generated with independent normally distributed entries \(N(0, \sigma ^{2})\), where \(\sigma ^{2}=\) 1/1,000 (so that the expected \(l_{2}\) -norm of each column was unity). We fix compressed ratio \(r/b=1/4\) in all our simulations, even when noise is larger than the estimated one. The statistical time of the virtual TCP channel efficiency and real MAC channel efficiency is set to 0.5 s.
Figure 1 shows the average remaining energy of nodes for different routing algorithms. In the CLOD algorithm, the average remaining energy of nodes in the key region is the highest. This denotes that the CLOD algorithm consumes less energy, which attributes to decrease transmission data by CS theory. Especially is the energy consumption least at 40–60 nodes. That shows the network is optimal for the node number by the CLOD algorithm. CLOD chooses a congestion avoidance path which consumes the least energy based on the numbers of nodes. The rest algorithms consume more energy because the data superabundant transmitted.
In Fig. 2, the proposed algorithm can use the network capacity well and thus maintained a high throughput during the 40–60 nodes. However the EOR can reach the maximal throughput when the network contains 80 nodes, which is less than the CLOD. Because the required processing data too larger than the CLOD, which results in trivial congestion. The rest two algorithms can’t achieve so high throughput.
The relative reconstruction error is given in Fig. 3. It is seen from Fig. 3 that the CS error ratio is less 0.1. This denotes that reconstruction performance improves the transmission efficiency under not affecting transmission quality. In Fig. 4, the control signal of the CLOD algorithm can accurately track the desired fixed signal, and have less delay.
Figure 5 shows the packet loss rate in different algorithms is low, and almost stable, which illustrates algorithm can quickly relieve congestion. However, the scheme possesses several different property: CLOD has the lowest packet loss rate when three algorithms play a role in respective network, which demonstrates CLOD achieve a better congestion control because of signal compressed and fair routing selection.

6 Conclusion

In this paper, a more practical model by considering fairness and congestion into optimal-lifetime problem is studied. Firstly, CS technique is applied in design for reducing transmitted bits, optimize the network lifetime and decrease the consumed energy. Secondly, congestion control function, routing function and scheduling function are decomposed based on optimal maximization problem. Three functions, which are implemented respectively in transport, network and link layer, interacted and are regulated by congestion ratio so as to achieve a global optimality. Thirdly, performance and robustness of the algorithm are justified. Stability shows the necessity of using cross-layer decomposed technique. Energy economization illuminates the necessity of using CS theory.


This Work is supported by the Science and Technology Support program of Hebei Province under Grant No.12210327 and by the Science and Technology Support program of Qinhuangdao under No.2012021A104
Open AccessThis article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Über diesen Artikel

Weitere Artikel der Ausgabe 4/2013

Wireless Personal Communications 4/2013 Zur Ausgabe