# Compressed Sensing Based Joint Rate Allocation and Routing Design in Wireless Sensor Networks

Authors: Jie Hao; Ran Wang; Baoxian Zhang; Yi Zhuang; Bing Chen
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Compressed sensing for wireless sensor networks has attracted a lot of research attention in the last decade for its advantages in energy saving, robustness, and so on. Nevertheless, existing solutions mostly focus on the data compression performance while neglecting the energy efficiency. In this paper, we first present the joint resource allocation problem formulation based on compressed sensing. Then a distributed algorithm to compute the sampling rate and routes utilizing local network status is proposed. We conduct extensive experiments based on meteorological wireless sensor networks to verify the merit of our mechanism; it is shown that the proposed mechanism is able to achieve very high efficiency in terms of network lifetime and sensing quality compared with existing approaches.


---

## Body

## 1. Introduction

Compressed sensing (CS, also known as compressive sensing) is an efficient tool to process data as it enables sparse sampling while guaranteeing high sampling quality in wireless sensor networks. With CS, the sink node only needs to collect the compressed measurementsym×1 based on the sensing matrix Φm×n instead of the original measurements xn×1; that is, ym×1=Φm×nxn×1,m<n. Φm×n is generally a Gaussian random matrix in which no entry is zero. The compressed sensing using this kind of nonsparse sensing matrix is referred to as dense compressed sensing. Typically, collection tree is by default used for supporting compressed data collection [1, 2]. Although the network performance is improved somehow, the communication cost needed to collect the compressed measurements caused by dense compressed sensing throughout the network is overlooked.Fortunately, sparse compressed sensing whose sensing matrix is sparse itself can achieve the same compression performance theoretically and experimentally with much less sampling and communication cost [3–6]. Figure 1 shows how sparse CS can reduce the communication consumption compared with dense CS. In this figure, a sensor network consisting of n sensor nodes needs to collect all the measurements from the sensor nodes. Gaussian sensing matrix is used to compress the original measurement and we assume m<n compressed measurements are required and transmitted to sink by a routing tree. For a single compressed measurement yj, that is, the jth entry of ym×1, each node multiplies its own measurement xi with ϕij, adds it with the incoming weighted measurement, and then forwards the added measurement to its next hop until sink receives the compressed measurement yj=(ϕ1j,ϕ2j,…,ϕnj)(x1,x2,…,xn)T. As ϕij≠0, ∀1≤i≤m, 1≤j≤n, dense CS implies that each node gets involved in each single compressed measurement. As a result dense CS would generate O(mn) transmissions in total. In comparison, in sparse CS there is only a single 1 in each row of Φ and 0 elsewhere. It implies only m nodes are chosen as the source nodes and hence the total transmission count is O(mlog⁡n) as the routing tree depth is O(log⁡n). From the temporal perspective, sparse CS indicates each sensor node takes samples under different sampling schedules. Although more energy efficient than dense CS, most literature on sparse CS decouples the sampling and routing design and only concentrates on one side as it assumes either the sampling [5, 6] or the communication energy consumption with energy hungry sensors [3] is neglectable. However, in practice we observe that the sampling or routing energy consumption could not be neglected in many cases. Take the typical radio module Semtech XE1205 radio transceiver [7] and SHT7x Humidity and Temperature Sensor [8] as examples. The typical TX power is around 62 mA, and the energy consumption for one byte is roughly 22 uJ at 76 kbps. The typical power in humidity measuring status is about 0.55 mA, and it takes a maximum of 20 ms for an 8-bit measurement. Thus the energy consumption for each measurement is 33 uJ. We can see that neither energy consumption for sampling nor routing should be ignored in this case for energy efficiency optimization. Therefore, this paper considers both sampling and routing energy consumption and aims at finding a joint design mechanism based on CS entitled Distributed Sampling Rate and Routing (DSRR) mechanism to optimize the overall energy consumption. The main contributions of this paper are summarized as follows:(i)
We formulate a compressed sensing based joint design problem that tackles sampling and routing simultaneously.(ii)
We propose a distributed algorithm that only utilizes local network status to achieve prolonged network lifetime and high sensing quality.(iii)
We conduct extensive experiments based on real data set and network deployment from SensorScope [9], which demonstrate the effectiveness of the proposed joint design.Figure 1
Sparse sampling can reduce the communication cost compared with dense sampling.
(a)
Dense compressed sensing (b)
Sparse compressed sensingThe rest of this paper is organized as follows. A literature review of existing work is presented in Section2. Section 3 describes the a priori knowledge of compressed sensing followed by Section 4 that presents compressed sensing based joint design formulation and the distributed algorithm. Section 5 reports our experimental results. Finally we make a conclusion in Section 6.


## 2. Related Work

The research concerning CS can be traced back to the last decade. Shortly after its invention, CS was introduced into wireless sensor networks for its advantages in energy conservation, transmission robustness, and so on [10–13]. At the very beginning, the literature mainly focused on using CS for data compression. CDG (Compressive Data Gathering) [10] utilizes spatial correlation and uses CS for snapshot data gathering. Ji et al. [12] explore CS for both snapshot and continuous data gathering under channel interference model.Other than reducing the measurements, some research work explores the impact of routing on the CS performance. Quer et al. [1] combined geographical routing with CS and were surprised to observe that CS is not as good as expected. Luo et al. [2] explore the network throughput of tree based CS and conclude that the hybrid manner that only uses CS near the root of the tree can achieve higher throughput than pure CS. Lee et al. [4] employ CS on shortest path tree based cluster structure.In the above research work, although the collected measurements using CS are significantly reduced, all the sensor nodes must be involved in each single measurement. This kind of CS mechanism is catalogued todense CS. Dense CS focuses on minimizing the number of measurements rather than the communication cost and sampling cost. Therefore, a rich body of literature aims to address the communication cost optimization and sampling cost optimization issue with CS. Fortunately, sparse sensing matrix is proved to have the same compression performance theoretically and experimentally [3, 5, 6]. In sparse CS, each row of sensing matrix requires O(log⁡n) nonzero entries in [14] or only one nonzero entry in [3, 5, 15].In sparse CS, collection tree is usually adopted for routing to gather the sparse measurements. Wang et al. [14] choose randomly m projection nodes in charge of collecting data from nonprojection nodes and sink only needs to query the projection nodes for data reconstruction. Shen et al. [6] use ETX routing metric to determine the sampling rate of each node; that is, lower ETX nodes have more opportunity to take samples. This nonuniform sampling can achieve the same sensing accuracy with less energy consumption. Chou et al. [16] aim at finding the sensing matrix that maximizes information gain to energy expenditure. It decouples the sensing matrix setting problem into two subproblems, location of nonzero elements (i.e., the routing), and the values of the nonzero elements in the sensing matrix. Rana et al. [3] notice that the energy consumption for sampling is much higher than communication for energy hungry sensors such as wind speed sensor and thus adapts the sample rates according to the harvest energy. Though energy efficient considering sampling consumption, [3] does not consider the routing issue.From the literature review, we can see that most research works neglect either energy consumption for sampling or communication. More specifically, they focus on either sampling scheduling or routing design. In comparison, our work in this paper considers both energy consumption for sampling and communication and thus jointly optimizes both sampling and routing design.


## 3. A Priori Knowledge on CS

This section will illustrate the a priori knowledge of compressed sensing used in our paper. Given a sensor networkG(V,L), where V is the vertex set and L is the link set, respectively, n and l are the cardinalities of V and L. The data from all the nodes form a data vector x=[x1,x2,…,xn]T. If x can be projected into a sparse signal s with representation basis Ψ, that is, x=Ψs, the original data xn×1 can be compressed to ym×1,m<n by sensing matrix Φm×n; that is, we have(1)y=Φx=ΦΨs.The reconstructed data x^ is obtained by x^=Ψs^, where s^ is the optimal solution of(2)minsl0,s.t.y=ΦΨs, or alternatively(3)minsl1,s.t.y=ΦΨs, to reduce complexity.Two performance metrics involved in compressed sensing areCR (Compression Ratio), defined as CR=m/n, and thereconstruction error defined as(4)ϵ=x^-x2x2. With compressed sensing, the sensor nodes take measurements at a low sampling rate without significant information degradation. Specifically, Φm×n specifies a sampling policy: each sensor node can only take one measurement at any scheduled time slot upon actuation; if the ith measurement is taken at time slot j, Φm×n has 1 in the (i,j) position (1≤i≤m,1≤j≤n), that is, ϕij=1. The resulting sensing matrix Φ is sparse as it contains only one 1 element in any row, at most one 1 in any column, and 0 everywhere else. Given a sampling rate r for a sensor node, m=⌊nr⌋ measurements should be taken and the positions of the nonzero entries are randomly chosen.To reconstruct the original data, representation basisΨ and recovery algorithm need to be dedicatedly designed. The choice of Ψ should satisfy two main criteria. Firstly, Ψ should transform x into a sufficiently sparse signal in some domain. In the other words, s=Ψ-1x should be as sparse as possible. Secondly, Ψ should be sufficiently incoherent with Φ. A rich body of literature has provided us with many good choices. DCT, Haar, wavelet transformation, differential matrix, and so on are widely used as representation basis. In particular, DCT, Haar, and so on are superior to differential matrix in terms of sparsity while differential matrix performs better regarding incoherence with the sparse sensing matrix [15]. BP, OMP, SL0, and so on as the recovery algorithm [17, 18] are widely used. In this paper, we will choose the exact CS method based on field data in the performance evaluation in Section 5.


## 4. Joint Design of Sampling and Routing

This paper aims to present a joint design of sampling and routing that can achieve prolonged network lifetime without sacrificing sensing quality. To this end, we firstly illustrate the energy consumption model of the network in Section4.1 and present the joint design formulation in Section 4.2 and the distributed algorithm in Section 4.3.


### 4.1. Energy Consumption Model

Given a sensor network consisting ofn sensor nodes, the energy consumption of a sensor node i, eci, mainly includes the energy consumption for sampling (sensing) Espi, communication Ecommi, computation Ecompi, and status switching Eswi; that is, eci=Espi+Ecompi+Eswi+Ecommi [19]. Among all the consumption, Ecompi and Eswi can be usually neglected compared with Espi and Ecommi. Thus, the equation is rewritten as(5)eci≈Espi+Ecommi.Now we investigateEspi and Ecommi in detail. The former one Espi is proportional to the number of samples that node i takes. Ecommi is proportional to the active time of the radio for transmission, reception, and idle listening. In this paper, we assume each sensor node is fully aware of when it should be turned on to receive and transmit according to our joint optimized design. Thus, in our model, Ecommi only considers energy consumption for transmitting and receiving. Let esp be the energy consumption for sampling once. We can obtain(6)Espi=espri. Let etx and erx be the energy consumption for transmitting and receiving, respectively, F={fij,∀i∈V&j∈Ni} be the flow from node i to j belonging to i’s neighbor set Ni. We have(7)Ecommi≈etx∑j∈Nifij+erx∑j∈Nifji.


### 4.2. Problem Formulation

Before we proceed to the specifics, we list all the involved notations and their semantics in Notations. Given a sensor networkG(V,L), during its lifetime T, each node samples the target phenomenon at a low rate and transmits the samples to a sink node by multihop routing. Assume the application requires an overall sampling rate r0 to achieve desired sensing quality. Network lifetime is defined as the minimum node lifetime among all the nodes in the network. We aim at designing the sampling and routing schedule jointly to maximize the network lifetime under the desired sampling rate constraint. Therefore, the joint design problem can be formulated as(8)maxr,fT,(9)s.t.ri≤∑j∈Nifij-∑j∈Nifji,∀i∈1,n,(10)eciT≤Ei,∀i∈1,n,(11)r0n≤∑i=1nri.Condition (9) is the flow conservation constraint; (10) is the energy constraint where (12)eci=etx∑j∈Nifij+espri+erx∑j∈Nifji, and (11) guarantees that the average sampling rate is higher than r0.ReplacingT by 1/q, we create an equivalent problem(13)minr,fq2,and (10) becomes(14)eci≤Eiq,∀i∈1,n.Moreover, we also hope to maximize the fairness of the sampling rates among all the nodes; that is, the variance of the sampling rates∑i=1n‍(ri-r0)2 which is convex should be minimized. In this way, we hope to avoid the case that the optimization may lead to zero measurement for a traffic heavy node and thus incurs high data loss if spatial correlation is not sufficiently high. To this end, we add a regularization term in our joint design objective (13) as follows:(15)minr,fq2+Θ∑i=1nri-r02,where Θ is the regularization parameter that pursues performance balance between network lifetime and fairness.The optimization problem can be easily solved in a centralized way. However, a centralized algorithm in wireless sensor networks is impractical since it requires overwhelming high communication or computation overhead. In this case, in order to carry out the optimization in resource limited wireless sensor networks with lower communication/computation overhead, we propose a distributed algorithm in the following subsection.


### 4.3. Distributed Sampling Rate and Routing Mechanism

Based on the problem formulation in the last subsection, we propose a distributed algorithm entitled Distributed Sampling Rate and Routing (DSRR) mechanism that can solve the problem by using only local network status. In order to perform the optimization fully distributively, we reformulate the problem to a convex quadratic optimization problem:(16)minr,f∑i=1nqi2+Θ∑i=1nri-r02,(17)s.t.9,14,11qi=qj,∀i,j∈1,n.Now, we form the Lagrangian by introducing Lagrangian multipliers λ, η, ξ, and ρ for the constraints, respectively.(18)Lq,f,r,η,λ,ξ,ρ=∑i∈1,nqi2+Θ∑i∈1,nri-r02+∑i∈1,nγiri-∑j∈Nifij-fji+∑i∈1,n∑j∈Niλijqi-qj+∑i=1nηir0-ri+∑i=1n∑j=1nξijηi-ηj+∑i∈1,nρieci-Eiqi=∑i∈1,nqi2+qi∑j∈Niλij-λji-ρiEiqi+Θri-r02+γiri-riηi+ρiespri+∑j∈Niρietx-γifij+ρierx+γifji+ηir0+∑j∈Niξij-ξjis.t.f∈Ωf,r∈Ωr,q∈Ωq, where Ωf, Ωr, and Ωq are feasible regions. We fix dual variables and then define subproblems and master problem as follows. The subproblems include(19)min∑i∈1,nqi2+qi∑j∈Niλij-λji-ρiEiqi,s.t.q∈Ωq,(20)min∑i∈1,nΘri-r02+γiri-riηi+ρiespri,s.t.r∈Ωr,(21)min∑i∈1,n∑j∈Niρietx-γifij+ρierx+γifji,s.t.f∈Ωf,with optimal values gr(ρ),gq(ρ),gf(ρ), respectively.The master problem isgr(ρ)+gq(ρ)+gf(ρ) and ρi is updated as(22)ρit+1=max⁡ρit+αtuit,0,uit=eci-Eiqi,where αt is the update stepsize. The optimal value gq(ρ)gr(ρ) can be obtained distributively at each node with qi∗=(ρiEi-∑j∈Ni‍(λij-λji))/2 and ri∗=2Θr0+ηi-γi-ρiesp/2Θ, respectively. gf(ρ) can be solved with global (or end-to-end) network information in polynomial time. In this paper, we aim at solving (21) by building a minimum cost tree.Observe that, in order to minimize (21), the traffic flow is encouraged to be routed along the path which produces the lowest ∑i∈[1,n]‍∑j∈Ni‍(ρietx-γi)fij+(ρierx+γi)fji. With this motivation, we design the distributed routing mechanism as follows.The cost function of each link(ij) is defined as cij=(ρietx-γi)+(ρjerx+γj),∀i∈[1,n],j∈Ni. Starting from the sink node, each node i updates its cost as Ci=min⁡{cij+Cj,∀j∈Ni} and chooses the neighbor node leading to Ci as its parent node pi. This procedure continues until all nodes update their costs and decide their parents. In this way, the tree minimizing (21) is established.Please note that the other Lagrange multipliers are updated as(23)γit+1=max⁡0,γit+αtuit,λijt+1=λijt+αtvijt,ηit+1=max⁡0,ηit+αtwit,ξijt+1=ξijt+αthit,where ui(t), vij(t), wi(t), and hi(t) are the components of the subgradient of L evaluated at γi(t), λij(t), ηi(t), and ξij(t) and can be obtained by(24)uit=ri-∑j∈Nifij-fji,vijt=qi-qj,wit=r0-ri+∑j∈Niξij-ξji,hit=ηi-ηj.The overall Distributed Sampling Rate and Routing (DSRR) control mechanism is summarized in Algorithm1.Algorithm 1:Working process of DSRR.
Distributed Sampling Rate & Routing control mechanism At each iteration, do Sink broadcasts a Route Request (RREQ) message containing its cost withCsink=0 and its q, η. Upon receiving the RREQ from its neighbors within its deferring time, a sensor nodei updates its cost as Ci=min⁡{(ρietx-γi)+(ρjerx+γj)+Cj,∀j∈Ni}, chooses the neighbour node leading to Ci as its parent node. i keeps overhearing all its neighbours and updates the Lagrange multipliers η, γ, λ, ξ, ρ according to (22) (24) (23). Nodei distributively computes ri∗, qi∗. Nodei arranges its RREQ and broadcast to its neighbors. This procedure continues until all nodes determine their parent nodes, sampling rates, and update their parameters. Every sensor node executes the obtained sampling rate, routing, and recodes its input/output traffic flow. endDSRR needs to carry out message exchange for multiplier update before its convergence. The overhead of DSRR is approximately proportional to the convergence iteration and also the message exchanging overhead for each iteration. Figure2 shows the convergence time of DSRR with a Great St. Bernard Pass network whose detailed description can be found in Section 5. We can see that DSRR is able to converge in about 110 iterations which means DSRR requires about 110 rounds of network-wide information exchange before it works with the optimized sampling rate and routing decision.Figure 2
The convergence time of DSRR.In each iteration, DSRR works similar to the classic On-Demand Distance Vector (AODV) Routing and its variants [20, 21]. In a path discovery process by DSRR, a Route Request (RREQ) message needs to carry the following information: one kind is local Lagrangian multiplier updating related information to be exchanged within neighborhood, including qj needed by λij and ηj needed by ξij; the other kind is cost of the path found so far, which records the cost of the path from the sink to the sender i of the received RREQ, that is, Ci.In addition, in order to minimize the communication overhead for path discovery, we can arrange the travelling speed of RREQ message across the network by introducing intentional deferring at intermediate nodes. For this purpose, we can set the deferring time of a received RREQ at an intermediate node to be proportional to the cost of the link over which the message was received and accordingly initiates a deferred timer. Once expired, the RREQ will be rebroadcasted. In case a new RREQ received from another neighbor leads to a shorter path cost, the path cost will be updated and the timer will be shortened. The node will record the neighbor which sends it the RREQ leading to the least cost as its parent node for it to deliver sensing data to sink later. After retransmitting the RREQ, a node will not need to process any duplicate RREQs further. In this way, each intermediate node only needs to retransmit the RREQ once and thus the communication overhead for route discovery is minimized asO(n). Therefore, the communication complexity of DSRR is overall O(n).


## 4.1. Energy Consumption Model

Given a sensor network consisting ofn sensor nodes, the energy consumption of a sensor node i, eci, mainly includes the energy consumption for sampling (sensing) Espi, communication Ecommi, computation Ecompi, and status switching Eswi; that is, eci=Espi+Ecompi+Eswi+Ecommi [19]. Among all the consumption, Ecompi and Eswi can be usually neglected compared with Espi and Ecommi. Thus, the equation is rewritten as(5)eci≈Espi+Ecommi.Now we investigateEspi and Ecommi in detail. The former one Espi is proportional to the number of samples that node i takes. Ecommi is proportional to the active time of the radio for transmission, reception, and idle listening. In this paper, we assume each sensor node is fully aware of when it should be turned on to receive and transmit according to our joint optimized design. Thus, in our model, Ecommi only considers energy consumption for transmitting and receiving. Let esp be the energy consumption for sampling once. We can obtain(6)Espi=espri. Let etx and erx be the energy consumption for transmitting and receiving, respectively, F={fij,∀i∈V&j∈Ni} be the flow from node i to j belonging to i’s neighbor set Ni. We have(7)Ecommi≈etx∑j∈Nifij+erx∑j∈Nifji.


## 4.2. Problem Formulation

Before we proceed to the specifics, we list all the involved notations and their semantics in Notations. Given a sensor networkG(V,L), during its lifetime T, each node samples the target phenomenon at a low rate and transmits the samples to a sink node by multihop routing. Assume the application requires an overall sampling rate r0 to achieve desired sensing quality. Network lifetime is defined as the minimum node lifetime among all the nodes in the network. We aim at designing the sampling and routing schedule jointly to maximize the network lifetime under the desired sampling rate constraint. Therefore, the joint design problem can be formulated as(8)maxr,fT,(9)s.t.ri≤∑j∈Nifij-∑j∈Nifji,∀i∈1,n,(10)eciT≤Ei,∀i∈1,n,(11)r0n≤∑i=1nri.Condition (9) is the flow conservation constraint; (10) is the energy constraint where (12)eci=etx∑j∈Nifij+espri+erx∑j∈Nifji, and (11) guarantees that the average sampling rate is higher than r0.ReplacingT by 1/q, we create an equivalent problem(13)minr,fq2,and (10) becomes(14)eci≤Eiq,∀i∈1,n.Moreover, we also hope to maximize the fairness of the sampling rates among all the nodes; that is, the variance of the sampling rates∑i=1n‍(ri-r0)2 which is convex should be minimized. In this way, we hope to avoid the case that the optimization may lead to zero measurement for a traffic heavy node and thus incurs high data loss if spatial correlation is not sufficiently high. To this end, we add a regularization term in our joint design objective (13) as follows:(15)minr,fq2+Θ∑i=1nri-r02,where Θ is the regularization parameter that pursues performance balance between network lifetime and fairness.The optimization problem can be easily solved in a centralized way. However, a centralized algorithm in wireless sensor networks is impractical since it requires overwhelming high communication or computation overhead. In this case, in order to carry out the optimization in resource limited wireless sensor networks with lower communication/computation overhead, we propose a distributed algorithm in the following subsection.


## 4.3. Distributed Sampling Rate and Routing Mechanism

Based on the problem formulation in the last subsection, we propose a distributed algorithm entitled Distributed Sampling Rate and Routing (DSRR) mechanism that can solve the problem by using only local network status. In order to perform the optimization fully distributively, we reformulate the problem to a convex quadratic optimization problem:(16)minr,f∑i=1nqi2+Θ∑i=1nri-r02,(17)s.t.9,14,11qi=qj,∀i,j∈1,n.Now, we form the Lagrangian by introducing Lagrangian multipliers λ, η, ξ, and ρ for the constraints, respectively.(18)Lq,f,r,η,λ,ξ,ρ=∑i∈1,nqi2+Θ∑i∈1,nri-r02+∑i∈1,nγiri-∑j∈Nifij-fji+∑i∈1,n∑j∈Niλijqi-qj+∑i=1nηir0-ri+∑i=1n∑j=1nξijηi-ηj+∑i∈1,nρieci-Eiqi=∑i∈1,nqi2+qi∑j∈Niλij-λji-ρiEiqi+Θri-r02+γiri-riηi+ρiespri+∑j∈Niρietx-γifij+ρierx+γifji+ηir0+∑j∈Niξij-ξjis.t.f∈Ωf,r∈Ωr,q∈Ωq, where Ωf, Ωr, and Ωq are feasible regions. We fix dual variables and then define subproblems and master problem as follows. The subproblems include(19)min∑i∈1,nqi2+qi∑j∈Niλij-λji-ρiEiqi,s.t.q∈Ωq,(20)min∑i∈1,nΘri-r02+γiri-riηi+ρiespri,s.t.r∈Ωr,(21)min∑i∈1,n∑j∈Niρietx-γifij+ρierx+γifji,s.t.f∈Ωf,with optimal values gr(ρ),gq(ρ),gf(ρ), respectively.The master problem isgr(ρ)+gq(ρ)+gf(ρ) and ρi is updated as(22)ρit+1=max⁡ρit+αtuit,0,uit=eci-Eiqi,where αt is the update stepsize. The optimal value gq(ρ)gr(ρ) can be obtained distributively at each node with qi∗=(ρiEi-∑j∈Ni‍(λij-λji))/2 and ri∗=2Θr0+ηi-γi-ρiesp/2Θ, respectively. gf(ρ) can be solved with global (or end-to-end) network information in polynomial time. In this paper, we aim at solving (21) by building a minimum cost tree.Observe that, in order to minimize (21), the traffic flow is encouraged to be routed along the path which produces the lowest ∑i∈[1,n]‍∑j∈Ni‍(ρietx-γi)fij+(ρierx+γi)fji. With this motivation, we design the distributed routing mechanism as follows.The cost function of each link(ij) is defined as cij=(ρietx-γi)+(ρjerx+γj),∀i∈[1,n],j∈Ni. Starting from the sink node, each node i updates its cost as Ci=min⁡{cij+Cj,∀j∈Ni} and chooses the neighbor node leading to Ci as its parent node pi. This procedure continues until all nodes update their costs and decide their parents. In this way, the tree minimizing (21) is established.Please note that the other Lagrange multipliers are updated as(23)γit+1=max⁡0,γit+αtuit,λijt+1=λijt+αtvijt,ηit+1=max⁡0,ηit+αtwit,ξijt+1=ξijt+αthit,where ui(t), vij(t), wi(t), and hi(t) are the components of the subgradient of L evaluated at γi(t), λij(t), ηi(t), and ξij(t) and can be obtained by(24)uit=ri-∑j∈Nifij-fji,vijt=qi-qj,wit=r0-ri+∑j∈Niξij-ξji,hit=ηi-ηj.The overall Distributed Sampling Rate and Routing (DSRR) control mechanism is summarized in Algorithm1.Algorithm 1:Working process of DSRR.
Distributed Sampling Rate & Routing control mechanism At each iteration, do Sink broadcasts a Route Request (RREQ) message containing its cost withCsink=0 and its q, η. Upon receiving the RREQ from its neighbors within its deferring time, a sensor nodei updates its cost as Ci=min⁡{(ρietx-γi)+(ρjerx+γj)+Cj,∀j∈Ni}, chooses the neighbour node leading to Ci as its parent node. i keeps overhearing all its neighbours and updates the Lagrange multipliers η, γ, λ, ξ, ρ according to (22) (24) (23). Nodei distributively computes ri∗, qi∗. Nodei arranges its RREQ and broadcast to its neighbors. This procedure continues until all nodes determine their parent nodes, sampling rates, and update their parameters. Every sensor node executes the obtained sampling rate, routing, and recodes its input/output traffic flow. endDSRR needs to carry out message exchange for multiplier update before its convergence. The overhead of DSRR is approximately proportional to the convergence iteration and also the message exchanging overhead for each iteration. Figure2 shows the convergence time of DSRR with a Great St. Bernard Pass network whose detailed description can be found in Section 5. We can see that DSRR is able to converge in about 110 iterations which means DSRR requires about 110 rounds of network-wide information exchange before it works with the optimized sampling rate and routing decision.Figure 2
The convergence time of DSRR.In each iteration, DSRR works similar to the classic On-Demand Distance Vector (AODV) Routing and its variants [20, 21]. In a path discovery process by DSRR, a Route Request (RREQ) message needs to carry the following information: one kind is local Lagrangian multiplier updating related information to be exchanged within neighborhood, including qj needed by λij and ηj needed by ξij; the other kind is cost of the path found so far, which records the cost of the path from the sink to the sender i of the received RREQ, that is, Ci.In addition, in order to minimize the communication overhead for path discovery, we can arrange the travelling speed of RREQ message across the network by introducing intentional deferring at intermediate nodes. For this purpose, we can set the deferring time of a received RREQ at an intermediate node to be proportional to the cost of the link over which the message was received and accordingly initiates a deferred timer. Once expired, the RREQ will be rebroadcasted. In case a new RREQ received from another neighbor leads to a shorter path cost, the path cost will be updated and the timer will be shortened. The node will record the neighbor which sends it the RREQ leading to the least cost as its parent node for it to deliver sensing data to sink later. After retransmitting the RREQ, a node will not need to process any duplicate RREQs further. In this way, each intermediate node only needs to retransmit the RREQ once and thus the communication overhead for route discovery is minimized asO(n). Therefore, the communication complexity of DSRR is overall O(n).


## 5. Evaluation

We conduct experiments to evaluate the proposed joint design using field data.SensorScope [9] is a turnkey solution for environmental monitoring systems, based on a wireless sensor network and resulting from a collaboration between environmental and network researchers. The sensors periodically sample the environment and transmit their readings through the wireless network to a sink. Specifically, we use two networks for our evaluation. One is deployed in Great St. Bernard Pass between Switzerland and Italy as a typical small scale network. The other is LUCE (Lausanne Urban Canopy Experiment) as a network of medium size. The following is the detailed experimental setting.


### 5.1. Experimental Setting

Network Setting. The network topologies of Great St. Bernard and LUCE are shown in Figures 3(a) and 3(b), respectively, where we assume a virtual node sitting between nodes 4 and 32 as the sink node in Great St. Bernard Pass network and a node near 68 as the sink node in LUCE network. The initial energy of the nodes is randomly chosen in the order of 30 kJ. In addition, as we notice that the value of the objective function would be extremely trivial with the experimental setting, we rescale the initial energy of each node by multiplying 10-5 and readjust the resulting network lifetime by multiplying 105.Figure 3
Network layout.
(a)
Great St. Bernard Pass (b)
LUCEIn SensorScope, the meteorological phenomenon such as ambient temperature, surface temperature, and relative humidity are sampled every 2 minutes. Thus, we set a time slot of 2-minute length and evaluate the network lifetime in the unit of time slot. The network parameters involved are illustrated as follows.Radio Transceiver. SensorScope uses Semtech XE1205 radio transceiver [7] with a transmission rate of 76 Kbps [9]. Its transmitting/receiving power is 31 mA (at 5 dBm) and 14 mA, respectively. We assume the packet size is constantly 2 bytes so that the energy consumption for a packet transmitting and receiving is roughly 21.54uJ and 9.73uJ, respectively.Sensors. Sensirion SHT75 [8] is adopted for air temperature and humidity. Power consumption for measuring is typically 0.55 mA (we neglect the power consumption 5 μW for sleeping). It usually takes about 20 ms for an 8-bit measurement. Therefore, the energy consumed by a sample is regulated at roughly esp=36.3uJ. The values of the involving parameters regarding energy consumption are summarized in Table 1.Table 1
Network parameters.
esp e t x e r x 36.3 uJ 21.54 uJ 9.73 uJ


### 5.2. Network Configuration

In this subsection we configure the parameters involved in the design, including CS method andΘ.


#### 5.2.1. CS Method Selection

In this subsection, we will choose the CS method which is suitable for our experimental data by evaluation. We utilize the measurements sampled by one sensor node as the data input. Figure4 shows the reconstruction error with different CS methods, where the sensing matrix Φ is always the sparse matrix generated by the uniform sampling and Ψ-1 could be DCT, Haar, DFT, and Difference Matrix (DiffM in short); the recovery algorithm could be Basis Pursuit (BP) or SL0. From the experiment results we can draw the same conclusion that DiffM performs superior to the others regarding three types of meteorological data. Due to the space limitation, we only show the comparison results of DCT, DiffM and BP, SL0 combination in Figure 4 with respect to three types of meteorological data. Considering SL0 is computationally faster than BP, we choose the combination of sparse sensing matrix, DiffM and SL0 as the CS method hereafter.Figure 4
Reconstruction errorϵ under different CS methods.
(a)
Ambient temperature (b)
Surface temperature (c)
Soil moisture


#### 5.2.2. The Impact ofΘ

Our joint design aims at achieving a good balance between the lifetime and fairness among sampling rates which is tuned by the regularization parameterΘ. Please note that we use the variance of the sampling rate vector [r1,r2,…,rn] as the indicator of the fairness among sampling rates; that is, the lower the variance, the higher the fairness. Thus, we determine Θ by using the benchmark design OPT, in which the sampling rate and routing are obtained by solving the optimization (16) with CVX tool [22]. OPT works as a benchmark for evaluation and provides us with the guidance for network configuration. We observe that the setting of Θ should be relevant with the value of ∑i=1n‍qi2, where q should be proportionate to the traffic load nr0 and inversely proportional to network density D and the energy capacity order E. Thus we intuitively design Θ=θ×(nr0/(DE))2 and explore the impact of θ on the optimization problem. From Figures 5 and 6, we can observe that with higher θ the joint design prefers to pursue fairness (i.e., low variance of the sampling rates of the nodes) rather than prolonged network lifetime and DSRR degrades to uniform sampling and network maximization routing with extremely high θ. In order to achieve the performance balance, we prefer θ=10 in the following experiments.Figure 5
Performance with varyingθ of the Great St. Bernard network.
(a)
Lifetime (b)
VarianceFigure 6
Performance with varyingθ of the LUCE network.
(a)
Lifetime (b)
Variance


### 5.3. Lifetime and Sensing Quality

This subsection evaluates the lifetime and reconstruction error performance of DSRR compared with three other mechanisms.One is used in SensorScope [9] combining uniform sampling and energy-aware anypath routing, referred to asUSAR in this paper. Specifically, uniform sampling means all nodes share the same sampling rate and energy-aware anypath routing means each node in the network randomly chooses one among maximally three energy richest neighbors with less hop distance to the sink as its parent node on the routing tree. The second one is energy-aware sampling and anypath routing design referred to asEASAR in this paper where energy-aware sampling means each node adjusts its sampling rate proportional to its available energy [3] while maintaining the overall required sampling rate by CS. Although the two schemes take energy conservation into account in the sampling policy and routing design, they do not fully take advantage of the coupling of sampling and routing based on CS. The last one is the centralized design OPT as described in Section 5.2.2. The comparison results are shown in Figures 7 and 8.Figure 7
Performance with varyingr0 of the Great St. Bernard Pass network.
(a)
Lifetime (b)
Reconstruction errorϵFigure 8
Performance with varyingr0 of the LUCE network.
(a)
Lifetime (b)
Reconstruction errorϵGiven Figures7(a) and 8(a), obviously the proposed DSRR performs superior to USAR and EASAR significantly in terms of network lifetime. Both USAR and EASAR are supposed to have good performance in the scenario that esp is much higher than etx and erx. However, in our experimental setting, the energy consumption of sampling is comparable with that of communication. In this case, the joint design DSRR achieves prolonged lifetime because it jointly optimizes the sampling and routing, whereas DSRR is highly superior to USAR and EASAR at a very low sampling rate r0=0.1, and the difference among all the schemes decreases as r0 increases. This is because, with higher sampling rate, the sampling rate and route diversity generated by the schemes are becoming low so that the gain of DSRR beyond the others saturates.Figures7(b) and 8(b) show the reconstruction error with increasing r0. (As there exists data error regarding LUCE network, we remove all measurements from abnormal sensor nodes.) We can see that overall uniform sampling in USAR performs best among all the schemes. The result conforms to our expectation that uniform sampling would conserve more spatial correlation and thus lead to less reconstruction error. Although DSRR results in higher reconstruction error, the reconstruction error of DSRR stays lower than 0.01 which is sufficiently low compared with the state of the art [15, 23]. In this experiment, we only use the ambient temperature data for evaluation. Similar results based on surface temperature and soil moisture data are omitted in this paper. In summary, Figures 7 and 8 verify that DSRR can achieve prolonged network lifetime with little sensing quality degradation compared with existing work.From the evaluation for Great St. Bernard Pass network and LUCE network, we can draw a conclusion that, for both small scale networks and medium scale networks, the centralized solution OPT and the proposed DSRR perform superior to the other existing mechanisms.


## 5.1. Experimental Setting

Network Setting. The network topologies of Great St. Bernard and LUCE are shown in Figures 3(a) and 3(b), respectively, where we assume a virtual node sitting between nodes 4 and 32 as the sink node in Great St. Bernard Pass network and a node near 68 as the sink node in LUCE network. The initial energy of the nodes is randomly chosen in the order of 30 kJ. In addition, as we notice that the value of the objective function would be extremely trivial with the experimental setting, we rescale the initial energy of each node by multiplying 10-5 and readjust the resulting network lifetime by multiplying 105.Figure 3
Network layout.
(a)
Great St. Bernard Pass (b)
LUCEIn SensorScope, the meteorological phenomenon such as ambient temperature, surface temperature, and relative humidity are sampled every 2 minutes. Thus, we set a time slot of 2-minute length and evaluate the network lifetime in the unit of time slot. The network parameters involved are illustrated as follows.Radio Transceiver. SensorScope uses Semtech XE1205 radio transceiver [7] with a transmission rate of 76 Kbps [9]. Its transmitting/receiving power is 31 mA (at 5 dBm) and 14 mA, respectively. We assume the packet size is constantly 2 bytes so that the energy consumption for a packet transmitting and receiving is roughly 21.54uJ and 9.73uJ, respectively.Sensors. Sensirion SHT75 [8] is adopted for air temperature and humidity. Power consumption for measuring is typically 0.55 mA (we neglect the power consumption 5 μW for sleeping). It usually takes about 20 ms for an 8-bit measurement. Therefore, the energy consumed by a sample is regulated at roughly esp=36.3uJ. The values of the involving parameters regarding energy consumption are summarized in Table 1.Table 1
Network parameters.
esp e t x e r x 36.3 uJ 21.54 uJ 9.73 uJ


## 5.2. Network Configuration

In this subsection we configure the parameters involved in the design, including CS method andΘ.


### 5.2.1. CS Method Selection

In this subsection, we will choose the CS method which is suitable for our experimental data by evaluation. We utilize the measurements sampled by one sensor node as the data input. Figure4 shows the reconstruction error with different CS methods, where the sensing matrix Φ is always the sparse matrix generated by the uniform sampling and Ψ-1 could be DCT, Haar, DFT, and Difference Matrix (DiffM in short); the recovery algorithm could be Basis Pursuit (BP) or SL0. From the experiment results we can draw the same conclusion that DiffM performs superior to the others regarding three types of meteorological data. Due to the space limitation, we only show the comparison results of DCT, DiffM and BP, SL0 combination in Figure 4 with respect to three types of meteorological data. Considering SL0 is computationally faster than BP, we choose the combination of sparse sensing matrix, DiffM and SL0 as the CS method hereafter.Figure 4
Reconstruction errorϵ under different CS methods.
(a)
Ambient temperature (b)
Surface temperature (c)
Soil moisture


### 5.2.2. The Impact ofΘ

Our joint design aims at achieving a good balance between the lifetime and fairness among sampling rates which is tuned by the regularization parameterΘ. Please note that we use the variance of the sampling rate vector [r1,r2,…,rn] as the indicator of the fairness among sampling rates; that is, the lower the variance, the higher the fairness. Thus, we determine Θ by using the benchmark design OPT, in which the sampling rate and routing are obtained by solving the optimization (16) with CVX tool [22]. OPT works as a benchmark for evaluation and provides us with the guidance for network configuration. We observe that the setting of Θ should be relevant with the value of ∑i=1n‍qi2, where q should be proportionate to the traffic load nr0 and inversely proportional to network density D and the energy capacity order E. Thus we intuitively design Θ=θ×(nr0/(DE))2 and explore the impact of θ on the optimization problem. From Figures 5 and 6, we can observe that with higher θ the joint design prefers to pursue fairness (i.e., low variance of the sampling rates of the nodes) rather than prolonged network lifetime and DSRR degrades to uniform sampling and network maximization routing with extremely high θ. In order to achieve the performance balance, we prefer θ=10 in the following experiments.Figure 5
Performance with varyingθ of the Great St. Bernard network.
(a)
Lifetime (b)
VarianceFigure 6
Performance with varyingθ of the LUCE network.
(a)
Lifetime (b)
Variance


## 5.2.1. CS Method Selection

In this subsection, we will choose the CS method which is suitable for our experimental data by evaluation. We utilize the measurements sampled by one sensor node as the data input. Figure4 shows the reconstruction error with different CS methods, where the sensing matrix Φ is always the sparse matrix generated by the uniform sampling and Ψ-1 could be DCT, Haar, DFT, and Difference Matrix (DiffM in short); the recovery algorithm could be Basis Pursuit (BP) or SL0. From the experiment results we can draw the same conclusion that DiffM performs superior to the others regarding three types of meteorological data. Due to the space limitation, we only show the comparison results of DCT, DiffM and BP, SL0 combination in Figure 4 with respect to three types of meteorological data. Considering SL0 is computationally faster than BP, we choose the combination of sparse sensing matrix, DiffM and SL0 as the CS method hereafter.Figure 4
Reconstruction errorϵ under different CS methods.
(a)
Ambient temperature (b)
Surface temperature (c)
Soil moisture


## 5.2.2. The Impact ofΘ

Our joint design aims at achieving a good balance between the lifetime and fairness among sampling rates which is tuned by the regularization parameterΘ. Please note that we use the variance of the sampling rate vector [r1,r2,…,rn] as the indicator of the fairness among sampling rates; that is, the lower the variance, the higher the fairness. Thus, we determine Θ by using the benchmark design OPT, in which the sampling rate and routing are obtained by solving the optimization (16) with CVX tool [22]. OPT works as a benchmark for evaluation and provides us with the guidance for network configuration. We observe that the setting of Θ should be relevant with the value of ∑i=1n‍qi2, where q should be proportionate to the traffic load nr0 and inversely proportional to network density D and the energy capacity order E. Thus we intuitively design Θ=θ×(nr0/(DE))2 and explore the impact of θ on the optimization problem. From Figures 5 and 6, we can observe that with higher θ the joint design prefers to pursue fairness (i.e., low variance of the sampling rates of the nodes) rather than prolonged network lifetime and DSRR degrades to uniform sampling and network maximization routing with extremely high θ. In order to achieve the performance balance, we prefer θ=10 in the following experiments.Figure 5
Performance with varyingθ of the Great St. Bernard network.
(a)
Lifetime (b)
VarianceFigure 6
Performance with varyingθ of the LUCE network.
(a)
Lifetime (b)
Variance


## 5.3. Lifetime and Sensing Quality

This subsection evaluates the lifetime and reconstruction error performance of DSRR compared with three other mechanisms.One is used in SensorScope [9] combining uniform sampling and energy-aware anypath routing, referred to asUSAR in this paper. Specifically, uniform sampling means all nodes share the same sampling rate and energy-aware anypath routing means each node in the network randomly chooses one among maximally three energy richest neighbors with less hop distance to the sink as its parent node on the routing tree. The second one is energy-aware sampling and anypath routing design referred to asEASAR in this paper where energy-aware sampling means each node adjusts its sampling rate proportional to its available energy [3] while maintaining the overall required sampling rate by CS. Although the two schemes take energy conservation into account in the sampling policy and routing design, they do not fully take advantage of the coupling of sampling and routing based on CS. The last one is the centralized design OPT as described in Section 5.2.2. The comparison results are shown in Figures 7 and 8.Figure 7
Performance with varyingr0 of the Great St. Bernard Pass network.
(a)
Lifetime (b)
Reconstruction errorϵFigure 8
Performance with varyingr0 of the LUCE network.
(a)
Lifetime (b)
Reconstruction errorϵGiven Figures7(a) and 8(a), obviously the proposed DSRR performs superior to USAR and EASAR significantly in terms of network lifetime. Both USAR and EASAR are supposed to have good performance in the scenario that esp is much higher than etx and erx. However, in our experimental setting, the energy consumption of sampling is comparable with that of communication. In this case, the joint design DSRR achieves prolonged lifetime because it jointly optimizes the sampling and routing, whereas DSRR is highly superior to USAR and EASAR at a very low sampling rate r0=0.1, and the difference among all the schemes decreases as r0 increases. This is because, with higher sampling rate, the sampling rate and route diversity generated by the schemes are becoming low so that the gain of DSRR beyond the others saturates.Figures7(b) and 8(b) show the reconstruction error with increasing r0. (As there exists data error regarding LUCE network, we remove all measurements from abnormal sensor nodes.) We can see that overall uniform sampling in USAR performs best among all the schemes. The result conforms to our expectation that uniform sampling would conserve more spatial correlation and thus lead to less reconstruction error. Although DSRR results in higher reconstruction error, the reconstruction error of DSRR stays lower than 0.01 which is sufficiently low compared with the state of the art [15, 23]. In this experiment, we only use the ambient temperature data for evaluation. Similar results based on surface temperature and soil moisture data are omitted in this paper. In summary, Figures 7 and 8 verify that DSRR can achieve prolonged network lifetime with little sensing quality degradation compared with existing work.From the evaluation for Great St. Bernard Pass network and LUCE network, we can draw a conclusion that, for both small scale networks and medium scale networks, the centralized solution OPT and the proposed DSRR perform superior to the other existing mechanisms.


## 6. Conclusions

In this paper, we explore the advantage of CS in the joint design of sampling and routing. We formulate a CS based optimization model to prolong network lifetime and guarantee sensing quality simultaneously and then propose a distributed algorithm DSRR that only requires local network status to achieve global network performance improvement. We conduct extensive experiments based on environmental network topologies and data. The experiment results demonstrate that the centralized algorithm and the distributed algorithm can achieve prolonged network lifetime with unnoticeable sensing quality sacrifice for both small scale and medium scale sensor networks compared with existing research work. The proposed algorithm is suitable for sensor networks with data correlation, such as meteorological sensor networks of different network size. As part of our future work, we will employ energy profile prediction model to further improve the efficiency of our joint design.



---

*Source: 6261453-2018-03-27.xml*