Increasing Network Lifetime Of An IEEE 802.15.4 Wireless Sensor Network By Energy Efficient

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

Increasing Network Lifetime Of An IEEE 802.15.4 Wireless Sensor Network By Energy Efficient Routing

Muhammad U. Ilyas

Department of Electrical & Computer Engineering

Michigan State University

East Lansing, MI – 48824, United States

ilyasmuh@egr.msu.edu

Abstract—In a multi-hop 802.15.4 Wireless Sensor Network the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on operational network lifetime of 802.15.4-based wireless sensor networks. This paper proposes the joint minimization of two network lifetime metrics, previously proposed for independent use, to more accurately characterize the degree of longevity of wireless sensor networks. The method uses the k-shortest simple path algorithm and a dynamic programming method rooted in operational rate-distortion (RD) theory to increase the operational lifetime of wireless sensor networks.

Hayder Radha

Department of Electrical & Computer Engineering

Michigan State University

East Lansing, MI – 48824, United States

radha@egr.msu.edupartition is inevitable, our work attempts to delay it by selecting a set of routes that produces more uniform, spread-out energy consumption. This is achieved by selecting suboptimal paths that reduce the traffic load on some sensors. In the context of WSNs, the capacity, congestion and compression aspects of the reachback channel have been previously investigated [2] [5]. To achieve longevity in sensor networks, energy-aware architectures and protocols have been thoroughly investigated in recent literature, see [8]-[15] and references therein. To the authors’ knowledge, this work is the first attempt at increasing the network lifetime aimed at IEEE 802.15.4 Wireless Personal Area Networks (WPAN or PAN) [1]. Different solutions make different assumptions about devices participating in a WSN. We are assuming a WSN composed of sensors compliant with the IEEE 802.15.4 PHY/MAC specifications that are ideally suited for WSN-like applications where low energy consumption is a priority.

In this paper, we address the adverse effect of the reachback problem on the lifetime of IEEE 802.15.4 WSNs by pursuing an optimization framework rooted in more fundamental disciplines such as information theory [20]. In particular, we aim at identifying the optimum WSN routing for all nodes within a given sensor network by following a joint-optimization approach that is inspired by an operational Rate-Distortion (RD) theoretical sense [22]-[25]. Under operational RD theory, an encoder effectively minimizes both the rate R and level of distortion D resulting from the representation of a random source by a distorted (quantized) version of that source. In the case of WSN routing under the reachback problem, we propose to simultaneously optimize two energy-related parameters (or network lifetime measure), which are analogous (although not identical) to the rate R and the distortion D in operational RD theory, in order to maximize the lifetime of any given sensor network. In addition to improving the lifetime of WSN networks significantly, our approach leads to important insight into optimum routing within these networks. Furthermore, one key issue that must be addressed under the proposed RD-like framework is the complexity of the overall scheme that identifies the optimum routing of every node in a WSN. For any practical WSN with a reasonable number of nodes, the complexity of finding the optimum route for every node becomes prohibitively expensive. Hence, we develop a novel dynamic programming algorithm that attempts to identify the optimum overall routing solution of a given IEEE 802.15.4 WSN that maximizes its lifetime. In particular, the proposed approach identifies a set of routes that perform close to the optimum routing while maintaining very low-complexity.

I. BACKGROUND AND MOTIVATION

Wireless Sensor Networks (WSN) consists of a large number of inexpensive, spatially distributed devices that collect sensor readings of their environment ([6], [7]). It is well known that WSNs are constrained by limited battery life and once deployed battery power cannot be replenished. In general, communication between sensor nodes and a base station can take place directly in a single hop or over multiple hops. In the multi-hop communication model sensor nodes report data to a base station and cooperate to forward data packets from other sensor nodes positioned farther away from the base station.

Such a many-to-one communication model gives rise to what is described as the reachback problem in networks in general and WSNs in particular (Servetto [2] defines the reachback channel for multi-hop WSNs with a mobile base station. Nevertheless, we refer to the multi-hop channels with both mobile and stationary base stations as reachback channels). The generalized reachback problem applies to any network obeying a many-to-one communication model. Some sensors will be situated farther away from the base station than others. Such sensors cannot communicate directly with the base stations and employ multi-hop communication to send data to the base station using the intermediary sensors. Traffic flows from the edges of the sensor network towards the base stations. Thus, the volume of traffic relayed by nodes closer to the base station is significantly higher than that of nodes farther away. Therefore, nodes located closer to the base station are consuming power at higher rates. Eventually these nodes will run out of battery power sooner than more distant nodes and die. Once all nodes within direct communication range of the base station stop functioning, the network will experience a partition ([26]) with the base station completely cut off from the rest of the WSN. Although the occurrence of the network

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

sensor nodes should be minimized. Shortest-Path First (SPF) [16] routing algorithm such as DSDV [8], DSR [9], AODV

The WSN consists of N=NFFD+NRFD sensors and one

[10] or Directed Diffusion [11] will cause the over utilization

PAN coordinator, i.e. NFFD Full Function Device (FFD) of some paths and the energy starvation of the nodes on that coordinators (numbered 1 through NFFD), and NRFD Reduced path. The problem of maximizing the operational lifetime of Function Device (RFD) devices (numbered 1 through NRFD). WSNs with respect to a metric representative of a network’s

“useful” lifetime is called the network lifetime maximization

The PAN coordinator is assigned FFD identifier 0 and fulfills

problem ([27]). Previously proposed metrics for the lifetime of

the role of the base station. The generic equivalent terms for

PAN coordinator, coordinator and device in the IEEE 802.15.4 WSNs include energy consumed per packet, time to network

partition, variance in node power levels, cost per packet,

standard are base station, clusterhead and sensor and will be

used interchangeably. The only restriction on the position of maximum node cost among others. Readers interested in the

rationale behind using these quantities as metrics are referred to

the base station is that it must be within communication range

of at least one clusterhead. It is further assumed that out of all [13][14]. As part of our work, we propose the joint use of mean

l, and the variance of energy Ethe clusterheads within communication range of a sensor, the of energy consumption rates2

sensor associates with the one that offers the lowest link cost. consumption rates σE, in the form of an ordered pair (tuple) Since we are assuming a uniform distribution for the sensors El,σ2 . We refer to this tuple as the Statistical Network E without regard to their type, i.e. FFD or RFD, each FFD will

l. have, on average, NRFD/NFFD number of RFDs associated with Lifetime Measure (SNLM). SPF algorithms only minimize E

it. RFDs are capable of communicating with FFDs only, but However, this first order statistic alone does not provide us any there are no restrictions on which devices an FFD can information about the pattern of energy consumption which is communicate with. The standard includes ranging, Link Quality the primary reason why network partition occurs. Jointly 2

Indication (LQI) and variable transmission power. Ranging minimizing σE ensures that the energy consumption rates are estimates distances to neighboring FFDs/ RFDs and permits the more uniform and that the traffic load on nodes closer to the use of local positioning methods such as Cricket [30], AhLOS base station is reduced. [31], and APS [32]. The LQI is a numerical indicator ranging

This problem can be formulated as a budget constrained between 0x00 and 0xFF on a linear scale and is implemented 2

using Energy Detection (ED). It estimates the quality of allocation problem: The minimization of σE is subject to the

l be less received signals and is recomputed on a packet-to-packet basis. constraint that the mean energy consumption rate E

lbudget (1), where E is the Adjustable transmission power allows sensors to take than some maximum budget value Ei

advantage of the information from ranging and LQI and expend energy consumption rate of node i, 1≤i≤N, and N is

FFDFFD

only as much power as is necessary for communicating with

neighbors. The standard specifies that compliant devices shall the number of coordinators. be capable of adjusting transmission power between a N

In [14] Singh, Woo and

Eminimum of -3 dBm and maximum allowed transmission ∑i

(1) Raghavendra describe the l=i=1lbudget power specified by local regulatory bodies. Since we are E=Eindependent minimization of NFFD

presenting a routing approach and since RFDs are incapable of only the variance of node performing routing, we are modeling an FFD and the power levels to extend the 2NNRFD/NFFD associated RFDs by a single node. The llifetime of a network. We (Ei E)∑(2) 2i=1transmission range of a sensor is limited by a maximum propose that instead of σE=

Ntransmission ranger. Each sensor is equipped with an omni-l (by selecting FFDminimizing E

directional antenna. We also assume an inverse exponential the shortest energy route) path loss model ([19]) for the transmitted signal. This means and σ2

Eindependently, we can obtain a better solution by

the cost assigned to a communication link is given by a link

jointly minimizing these two quantities. Baek et al [33] attempt

cost function that will be a function of sensor resources and

to minimize both probability of node failure (equivalent to

(energy) cost of communicating over Zhao et al. [28] present

lspreading factor an efficient way to code and communicate the energy map minimizing E) while minimizing the 2

making use of the fact that energy consumption rates are (equivalent to minimizing σE). Using the constraint spatially correlated in a sensor field. In [29] Mini, Loureiro formulation highlighted above, we can summarize our and Nath present a prediction based approach using a Markov optimization framework as identifying the optimum routes Model to significantly reduce the frequency of messages to the throughout a given WSN such that the following is

2PAN coordinator that are required to maintain the energy map. satisfied:lmin{σE}. This is analogous to minimizing a l

II.

NETWORK MODEL & OVERVIEW OF IEEE 802.15.4

FFDFFD

E≤Ebudget

III. PROBLEM FORMULATION

In order to significantly delay network partition and non-uniformly distributed loss of coverage, all nodes are considered

equally important. We would like to ensure that no node consumes energy at a rate significantly higher than other nodes; while simultaneously keeping the average power comsumption rate low, i.e. both variance mean of power consumption rates in

distortion measure D given a rate budget constraint R≤Rbudget under an RD framework. Consequently, our proposed NeLMUK algorithm is based on an operational RD-framework where we strive to select the SNLM operating point that offers

2l≤Elbudget. We the lowest achievable σE while maintaining E

propose the Network Lifetime Maximization Using K-Shortest Simple Paths (NeLMUK) algorithm which employs the K-

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

Shortest Simple Path algorithm together with an operational rate-distortion (or RD-like) algorithm to dramatically reduce computational complexity.

IV. NELMUK: NETWORK LIFETIME MAXIMIZATION USING

K-SHORTEST SIMPLE PATHS A. Computational Complexity of Finding Optimal Solution Similar to operational RD problems in source coding [20], our SNLM optimization can be mapped into a Lagrangian optimization framework. This formulation is feasible if there is

l,σ2 such that El=Elbudget (i.e., an an optimum tuple EE

optimal/minimal overall energy can be found such that it exactly equals the budget constraint). In this case, one can view the problem as one that allocates the overall energy budget lbudget among all nodes in the network such that the variance E2σE is minimum. This is referred to as the budget constrained allocation problem [22]. However, the computational complexity of finding the true optimal solution is staggeringly

l on the x-axis and σ2 on high. The SNLM plane consists of EE

the y-axis. The SNLM region consists of all possible SNLM operating points obtained by choosing all possible combinations of possible simple routes from each sensor node to the PAN coordinator. The desired optimal solution will lie on the hull of the SNLM region. This is very similar to the problem of finding the optimal quantizer in an operational rate-distortion (RD) sense from information theory ([20]).

We model a WSN by a graph G(V,A) consisting of a set of nodes or vertices V of cardinality NFFD+1 and a set of

2

+NFFD (we directed edges A of maximum cardinality NFFD

consider a worst case scenario in which there is no limit on the maximum transmission range of a node). Let us first consider a single coordinator. The only restriction on paths from a coordinator to the PAN coordinator is that they be simple, i.e. must not contain any loops. The number of hops in a route from a coordinator to the PAN coordinator may vary between

1 andNFFD

n 1 . There are ∑ Ni different possible () FFD∏ n=1 i=0

NFFD

complexity over an exhaustive search of all operating points,

DP has the advantage of determining optimum operating points that do not lie on the hull of the SNLM region as the Lagrangian optimization method would require, yet offer lower 2lbudget. σE within a budget constraint E

2

σE

lE

Figure 1. Selection of next optimal point in the SNLM DP algorithm.

Our DP algorithm operates on NFFD sorted lists, one for

each sensor, each containing all its paths to PAN coordinator ordered in ascending order of their path energies. The algorithm described here is greedy in nature. It is possible that

l,σ2 this algorithm does not find the optimum operational EE

point under certain scenarios. Nevertheless, the algorithm does provide the optimum operational solution under many practical scenarios. Furthermore, a set of RD variations of this algorithm are rather popular due to its simplicity and low-complexity ([23], [24], [25]). Furthermore, if the collapsed PAN consisting of only FFDs be represented by a graph G(V,A) where V is the set of vertices consisting of all coordinators and A is the set or arcs or edges, then Pj(,ik) is the i-th shortest path from the

to the FFD with IDk. Then the starting point FFD with j

El(0),σ2(0) of our algorithm is the operating point that offers the E

l and is obtained by selecting all P(1) where lowest possible Ej,0

2

j,1≤j≤NFFD and is located closest to the σE axis. The

l is usually associated minimum mean power consumption E

2(0)l,σ2(0) pair with a high σE. The algorithm then uses this E E

(0)

(0)

routes from a single coordinator to the PAN coordinator.

Hence, the number of points making up the SNLM plane is as a starting point to search for the next achievable operating

N El(1),σ2(1) N n 1 point E closest to the hull of the SNLM region that ∑ Niwhich is unmanageably large even for () ∏FFD

FFD

FFD

modest values of NFFD. This is followed by determining the

n=1 i=0

lbudget. If the pair El,σ2(0) adheres to the budget constraint E E

(0)

hull of the SNLM region. As Ortega et al. observed for the RD

problem in [21], there are two sources of complexity in this problem; 1) The computation of the vast number of possible operating points, 2) the process of finding the best possible operating point.

B. Complexity Reduction by Dynamic Pogramming

In order to reduce the computational complexity of finding the hull of the SNLM region we use a dynamic programming (DP) approach similar to the method used in the determination of the hull of the RD region for optimal quantizer design. Besides having an obvious advantage in computational

lsatisfies the specified constraint E

and

E l(0)2(0) is the optimum point l(1)2(1)

,σE does not, the pair E,σE

(0)

lbudget≤E

and the algorithm terminates. However, in general, the above

condition is not met. Rather than considering all possible route

l,σ2(i) during the combinations, at any operating point EE

(i)

(i+1)th iteration, the algorithm introduces the smallest

in energy to each route by considering increase E

i)l,σ2(i) by replacement of Pj(,0 in the set of routes used for EE

(i)

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

i+1)Pj(,0 in turn. This produces up to NFFD new possible

operating points. The exact number of alternative operating points depends on the number of routes lists that still have an alternate path left for consideration. Each of these possible alternatives is obtained by replacing one of the routes that computing the next operating point. This way we obtain up to

lNFFD different alternatives E

(i+1,j)

significantly lower than in the previous option which uses all

possible paths instead.

El(i,j),σ2(i,j) which, depending on the choice of k, can be E

l(i),σ2(i) by the next shortest available path and re-produced EE

Out of these NFFD alternatives we select the one which offers

l,σ2(i) where jthe lowest gradient λ(i,jmin) from EE min is

defined as in (5).

(5) At the i-th jmin=argmin(λ(i,j)).

iteration of the DP j

algorithm we define

2(i,jmin)2(i)(6) σ σthe lowest gradient E

λ(i,jmin)=E(i,jmin)

(i)

llas (6) and λ(i,jmin) E E

use it to determine

(i+1,j)(i,j)(7) E 2(1,)2(,)+ijijllthe next point on ,σE,σE = E the SNLM plane as

(7). This way the

algorithm iteratively determines the next point on the SNLM region’s hull. For the case shown in Figure 1,

(i)

min

min

2(i+1,j) ,σE for 1≤i≤NFFD.

l(0,1),σ2(0,1) λ(0,1)<λ(0,2)<λ(0,3)<λ(0,4). Then the point E E

(1)

l,σ2(1) . corresponding to λ(0,1) will be chosen as EE

V. SIMULATION RESULTS AND ANALYSIS

First, we compare NeLMUK’s time complexity with an exhaustive search. Due to the prohibitive complexity of the exhaustive search, we begin with an 802.15.4 WPAN small enough to allow us to generate the entire SNLM region within reasonable time. We generate a PAN with a random topology consisting of just 9 coordinators and one PAN coordinator. To prove the reduction in complexity we generate both, the SNLM region’s hull using our proposed method and the entire SNLM region based on an exhaustive search. The PAN is spread over a rectangular region of size 10m×10m. Since we have not put any limit on the maximum transmission range of sensor nodes the resulting graph-based representation of this PAN is a fully connected graph G(V,A), A being the set of all possible communication links between FFD sensor nodes and the PAN coordinator represented by the set of vertices V. The PAN coordinator is located in the center at coordinates(5,5). Figure 2.a depicts G(V,A). Figure 2.b depicts the topology of the SPF network Asp. Similarly, Figure 2.c depicts the topology of the minimum variance routes which we refer to as the minimum variance network Aminσ2.

E

C. Complexity Reduction by K-Simple Shortest Paths

In this section we describe another method to significantly reduce the complexity of the DP method described in the preceding section. The complexity of the sorting process alone is significant. This is followed by the execution of the DP. It is evident that a significant reduction in complexity could be achieved if the lists of sorted routes that are maintained for each coordinator can be shortened. This step can be justified by the fact that routes further down the list have higher path energies and that may not be of any use because they will cause l(i) to exceed Elbudget. To shorten the list of paths we map the E

problem of reducing the number of paths in each coordinator’s list to a well known variant of the class of shortest path problems in network programming. The shortest path problem is a classical network programming problem that has been extensively studied in ([16]) among hundreds of other references. The problem of determining not only the shortest but also the second, third, upto kth shortest paths is a less intensively studied problem called the K-Shortest Paths problem (KSP), ([17]). The classical k-shortest path problem allows paths to have loops. In our work we use a constrained version of this problem called the K-Shortest Simple Path problem (KSSP) ([18]) in which paths are restricted to be simple (loopless). The algorithm takes as input a graph, a source and destination. The output consists of a list of k simple paths from the coordinator to the PAN coordinator, sorted in ascending order of path costs. This way the DP step of our algorithm only has to compute NFFD NFFD k pairs of

approximately 7 hours and 12 minutes. Figure 3 is a plot of a portion of the SNLM region together with an estimate of its hull obtained by our DP method. The curve starts at the point obtained from the SPF network and is referred to as the SPF operating point. We observed that the curve follows a general parabolic shape for all simulated scenarios. The lowest point on the curve is the minimum variance point. The equivalent network that produced that point is the minimum variance network. As we can see in Figure 3 our estimate of the hull follows the actual hull unto the minimum variance point quite closely. It is crucial to observe that we are able to achieve significant reductions in the variance while maintaining very small increases in average energy spent. Here we achieve more than 74% reduction in variance (from 77 down to 20) while increasing the mean by only 32.5%, from 12 to only around 15.9. Another observation about the hull curve is that the number and magnitude of direction changes significantly

We choose k such that the number of simple paths from each coordinator ranges between 5 and 20. The running time for our algorithm on a WSN with the above parameters is less than 10 seconds. The running time for the full search that

l,σ2 determines all achievable Eoperating points is E

Figure 2. a) Full network of all available links for WSN with NFFD=9, b.) Network of links in shortest path routes, c.) Network of links offering the

minimum variance.

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

increases as the curve approaches the minimum variance point. A desired optimum solution will always lie on the curve between the shortest path and the minimum variance points on the curve. In order to study the effect of different values of k we generate hull estimates while varying k. We expect that higher values of k will yield better results and take us closer to the hull of the SNLM region obtained by plotting possible combinations of all possible routes for all coordinators. Since the PAN under consideration is only sparsely populated, the resulting hull estimates for different values of k are almost identical before reaching the minimum variance point, as shown in Figure 4. But once the minimum variance point is

crossed, the different curves start separating.

Figure 3. SNLM region plotted together with the estimate of its hull obtained by using k-shortest simple

paths and DP method.

Figure 4. Estimates of the hull of the SNLM region of the WSN with NFFD=9 for different values of k.

However, the small value of NFFD and the correspondingly small values of k do not let us draw any definite conclusions at this point. We now consider a WSN with NFFD=99, along with its shortest path network Figure 7.a, minimum variance network Figure 7.b. The corresponding hull estimate for k set to values between 10 and 500 are shown in Figure 7.c. The curve is much smoother than the one we showed in Figure 4. Also, the parabolic shape of the curve is much clearer in this curve than the previous ones we showed due to the fact that we

lhave a much greater number of alternatives E

(i,j)

choose from. Like in the previous example, the drop in

variance is significant. An insignificant increase in average power consumption rate from 4.45 to 4.75 (6.75% increase), produces a big corresponding drop in variance from 60 to 41 (32% decrease). Here it is worth highlighting a key difference between our proposed SNLM optimization framework and traditional RD schemes. The optimum RD curves are usually monotonic due to the fact that increasing the rate leads to reducing distortion. However, under the 2-D SNLM space spending more energy does not necessarily imply lower variance. Hence, under SNLM optimization, we see the existence of a minimum-variance point that, in general, separates the SNLM optimum curve into two halves: a left-half curve that is monotonically (maximally) decreasing in variance as the average-energy (minimally) increases (which is desirable), and a right-half curve that monotonically (minimally) increases in variance as the average energy increases. The corresponding hull estimates are plotted in Figure 7. As we observed earlier, the higher the value of k, the later it reaches the minimum point and the later it starts

2(i,j) ,σE to

ascending again. The hull estimates in Figure 7 give us

different minimum variance points for different values of k. As expected, the larger the value of k is the lower the variance offered by its minimum variance network. A side by side comparison of shortest path and minimum variance networks for both PAN examples reveals the capacity of the cut around the PAN coordinator is higher in the minimum variance networks compared to the shortest path networks. While this trend may not be clearly visible in the PAN with NFFD=9, the higher concentration of additional links near the PAN coordinator in the WSN with NFFD=99 is undeniable. The in-degree of the PAN coordinators in the WSNs with NFFD=9 and NFFD=99 increase from 3 to 5 and from 4 to 8 respectively.

To verify that the redistribution

of packet forwarding is indeed occurring in coordinators that need it most (nodes close to

the PAN coordinator) we plot the changes in the energy

consumption rates of sensors between SPF and Figure 5.Diffusion plot of difference in energy

consumption rates in sensors between minimum minimum

variance and SPF routing.

variance routing

in Figure 5. The blue region around the position of the base station indicates a reduction in the sensors in its immediate vicinity, while the red region indicates an increase in power consumption. Now, since we have a significantly larger WSN in the second example, we can expect the statistics derived from it to be more robust. Figure 6 depicts a histogram of the sensor nodes sorted according to the energy spent by each node when every sensor transmits one packet. The figure depicts two histograms, one for the shortest path network and one for the minimum variance network. By looking at the right-most histogram bin with a non-zero entry, we can determine the time till the first node fails. The time till first node failure is another network lifetime metric that is often used ([14]). Although we do not subscribe to the idea that time-to-first-node-failure makes a good metric for measuring a network’s lifetime, we can see that the maximum energy consumption rate of nodes has been reduced from 42 down to 32 units, a 23.8% decrease which is quite significant.

VI. CONCLUSIONS

We introduce the NeLMUK algorithm which employs 1) an operational method for reducing the complexity of finding the optimal set of routes that maximize network lifetime by jointly minimizing the mean and variance of power consumption rates, 2) the KSSP algorithm. We also show that a relatively

l can yield a significant reduction in insignificant increase in E

the volume of traffic that is processed by intermediate nodes increases considerably as data approaches the PAN coordinator. This problem is referred to as the reachback problem. In this work we focus on a more fundamental implication of reachback on opera

suitable metric for comparing the network lifetime of WSNs.

REFERENCES

2l,σ2 SNLM is a σEwhich leads us to conclude that the EE

[1] IEEE P802.15.4, Draft Standard: Low-Rate Personal Area Networks, February 2003.

[2] S. D. Servetto, “The Reachback Channel in Wireless Sensor Networks,”

DIMACS Workshop on Network Information Theory, 2003.

[3] J. Barros and S. D. Servetto, “Reachback Capacity with Non-Interfering

Nodes,” IEEE ISIT, 2003.

[4] J. Barros and S. D. Servetto, “Coding Theorems for the Sensor

Reachback Problem with Partially Cooperating Nodes,” American Mathematical Society (AMS), Discrete Mathematics and Theoretical Computer Science (DIMACS) series on Network Information Theory. [5] A. Scaglione and S. Servetto, “On the Interdependence of Routing and

Data Compression in Multi-hop Sensor Networks,” ACM Mobicom, 2002.

[6] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A

Survey on Sensor Networks,” IEEE Communications Magazine, pp. 102–114, August 2002.

[7] D. Niculescu, “Communication Paradigms for Sensor Networks,” IEEE

Communications Magazine, Vol. 43, No. 3, March, 2005. J. N. Al-Karaki and A.E. Kamal, “Routing Techniques in Wireless Sensor Networks: A Survey,” IEEE Wireless Communications Magazine, vol. 11, no. 6, December 2004.

[8] C. E. Perkins, P Bhagwat, “Highly Dynamic Destination-Sequenced

Distance-Vector Routing (DSDV) for Mobile Computers,” ACM SIGCOMM, 1944.

[9] D. B. Johnson, and D. A. Maltz, “Dynamic Source Routing in Ad Hoc

Wireless Networks,” Mobile Computing, pp 153-181, Kluwer Academic Publishing, 1996.

[10] C. E. Perkins, E. M. Belding-Royer, S. Das, “Ad-Hoc On Demand

Distance Vector Routing,” IEEE WMCSA’99, 1999.

[11] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and Fabio

Silva, “Directed Diffusion for Wireless Sensor Networking,” IEEE/ACM Transactions on Networking, vol. 11, no. 1, pp. 2–16, February 2002. [12] Q. Li, J. Aslam, and D. Rus, “Hierarchical Power-aware Routing in

Sensor Networks,” DIMACS Workshop on Pervasive Networking, 2001. [13] M. A. Youssef, M. F. Younis, K. A. Arisha, “A Constrained Shortest-Path Energy-Aware Routing Algorithm for Wireless Sensor Networks,” IEEE WCNC, 2002.

[14] S. Singh, M. Woo and C. S. Raghavendra, “Power-Aware Routing in

Mobile Ad Hoc Networks”, ACM Mobicom, 1998.

[15] Y. Yu, R. Govindan, and D. Estrin, “Geographical and Energy Aware

Networks,” UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023, May 2001.

[16] T. H. Cormen, T. E. Leiserson, R. L. Rivest, and C. Stein, “Introduction

to Algorithms, 2nd ed.,” McGraw-Hill, 2001.

[17] E. D. Q. V. Martins, M. M. B. Pascoal, and J. L. E. D. Santos, “The K

Shortest Paths Problem,” International Journal of Foundations of Computer Science, June 1998.

[18] S. Clarke, A. Krikorian and J. Rausen, “Computing the N best Loopless

Paths in a Network,” Journal Soc. Industrial Applied Math., Vol. 11, No. 4, pp. 1096-1102, 1963.

[19] T. S. Rappaport. “Wireless Communications: Principles and Practice,”

Prentice-Hall, 1996.

[20] T. M. Cover, and J. A. Thomas, “Elements of Information Theory,”

Wiley-Interscience, 1991.

[21] A. Ortega, and K. Ramchandran, “From Rate-distortion Theory To

Commercial Image and Video Compression Technology,” IEEE Signal Processing Magazine, pp. 20-22, Vol. 15, Issue 6, November, 1998.

[22] H. Everett, “Generalized Lagrange Multiplier Method for Solving

Problems of Optimum Allocation of Resources,” Operations Research, Vol. 11, pp. 399-417, 1963.

[23] H. Radha, M. Vetterli, and R. Leonardi, “Image Compression Using

Binary Space Partitioning Trees,” IEEE Transactions on Image Processing, December, 1996.

[24] G. M. Schuster, and A. K. Katsaggelos, “Rate-Distortion Based Video

Compression, Optimal Video Frame Compression and Object Boundary Encoding,” Kluwer Academic Publishers, 1997.

[25] G. Sullivan, and T. Wiegand, “Rate-Distortion Optimization for Video

Compression,” IEEE Signal Processing Magazine, pp. 74-90, Vol. 15, Issue 6, November, 1998.

[26] A. S. Tanenbaum, “Computer Networks, 4th ed,” Prentice-Hall, 2002. [27] J-H. Chang, and L. Tassiulas, “Energy Conserving Routing in Wireless

Ad-Hoc Networks,” Infocom, 2000.

[28] Y. J. Zhao, R. Govindan, and D. Estrin, “Residual Energy Scan for

Monitoring Sensor Networks,” IEEE WCNC, 2002.

[29] R. A. F. Mini, A. A. F. Loureiro, and B. Nath, “Prediction-based energy

map for wireless sensor networks,” Ad Hoc Network Journal, 2004.

[30] N.B. Priyantha, A. Chakraborty, H. Balakrishnan, “The cricket location-support system," ACM Mobicom, 2000.

[31] A. Savvides, C.-C. Han and M. Srivastava, “Dynamic fine-grained

localization in ad-hoc networks of sensors", 6th ACM Mobicom, 2001. [32] D. Niculescu and Badri Nath, “Ad hoc positioning system (APS)",

Globecom, 2001.

[33] S. J. Baek, G. de Veciana, “Spatial Energy Balancing through Proactive

Multipath Routing in Wireless Multihop Networks,” IEEE Infocom, 2005.

Figure 6. Histogram of power consumption rates of WSN

with NFFD=99.

c.

Figure 7. a.) Shortest path network, b.) Minimum variance network, c.) Estimates of the hull of

SNLM region of a WSN with NFFD=99 for different values of k.

本文来源：https://www.bwwdw.com/article/5ck4.html