An Application-Specific Protocol Architecture for Wireless Microsensor Networks Wendi B.Heinzelman,Member,IEEE,Anantha P.Chandrakasan,Senior Member,IEEE,and
Hari Balakrishnan,Member,IEEE
Abstract—Networking together hundreds or thousands of cheap microsensor nodes allows users to accurately monitor a remote en-vironment by intelligently combining the data from the individual nodes.These networks require robust wireless communication pro-tocols that are energy efficient and provide low latency.In this paper,we develop and analyze low-energy adaptive clustering hier-archy(LEACH),a protocol architecture for microsensor networks that combines the ideas of energy-efficient cluster-based routing and media access together with application-specific data aggrega-tion to achieve good performance in terms of system lifetime,la-tency,and application-perceived quality.LEACH includes a new, distributed cluster formation technique that enables self-organiza-tion of large numbers of nodes,algorithms for adapting clusters and rotating cluster head positions to evenly distribute the energy load among all the nodes,and techniques to enable distributed signal processing to save communication resources.Our results show that LEACH can improve system lifetime by an order of mag-nitude compared with general-purpose multihop approaches. Index Terms—Data aggregation,protocol architecture,wireless microsensor networks.
I.I NTRODUCTION
A DV ANCES iN sensor technology,low-power electronics,
and low-power radio frequency(RF)design have enabled the development of small,relatively inexpensive and low-power sensors,called microsensors,that can be connected via a wire-less network.These wireless microsensor networks represent a new paradigm for extracting data from the environment and en-able the reliable monitoring of a variety of environments for ap-plications that include surveillance,machine failure diagnosis, and chemical/biological detection.An important challenge in the design of these networks is that two key resources—com-munication bandwidth and energy—are significantly more lim-ited than in a tethered network environment.These constraints require innovative design techniques to use the available band-width and energy efficiently.
Manuscript received January9,2001;revised July1,2001and August 24,2001;accepted August24,2001.The editor coordinating the review of this paper and approving it for publication is M.Zorzi.The work of W.B.Heinzelman was supported by a Kodak Fellowship.This work was supported in part by the Defense Advanced Research Project Agency(DARPA) Power Aware Computing/Communication Program and the U.S.Air Force Research Laboratory,Air Force Materiel Command,under Agreement F30602-00-2-0551.
W.B.Heinzelman was with the Massachusetts Institute of Technology,Cam-bridge,MA02139USA.She is now with the Department of Electrical and Com-puter Engineering,University of Rochester,Rochester,NY14627-0126USA (e-mail:hester.edu).
A.P.Chandrakasan and H.Balakrishnan are with the Massachusetts Insti-tute of Technology,Cambridge,MA02139USA(e-mail:anantha@mtl.mit.edu; hari@lcs.mit.edu).
Digital Object Identifier10.1109/TWC.2002.804190
In order to design good protocols for wireless microsensor networks,it is important to understand the parameters that are relevant to the sensor applications.While there are many ways in which the properties of a sensor network protocol can be eval-uated,we use the following metrics.
A.Ease of Deployment
Sensor networks may contain hundreds or thousands of nodes,and they may need to be deployed in remote or dan-gerous environments,allowing users to extract information in ways that would not have been possible otherwise.This requires that nodes be able to communicate with each other even in the absence of an established network infrastructure and predefined node locations.
B.System Lifetime
These networks should function for as long as possible.It may be inconvenient or impossible to recharge node batteries.There-fore,all aspects of the node,from the hardware to the protocols, must be designed to be extremely energy efficient.
C.Latency
Data from sensor networks are typically time sensitive,so it is important to receive the data in a timely manner.
D.Quality
上证
国债指数The notion of“quality”in a microsensor network is very different than in traditional wireless data networks.For sensor networks,the end user does not require all the data in the network because1)the data from neighboring nodes are highly correlated,making the data redundant and2)the end user cares about a higher-level description of events occurring in the environment being monitored.The quality of the network is,therefore,based on the quality of the aggregate data set, so protocols should be designed to optimize for the unique, application-specific quality of a sensor network.This paper builds on the work described in[11]by giving a detailed description and analysis of low-energy adaptive clustering hierarchy(LEACH),an application-specific protocol architecture for wireless microsensor networks.LEACH employs the following techniques to achieve the design goals stated:1)randomized,adaptive,self-configuring cluster for-mation;2)localized control for data transfers;3)low-energy media access control(MAC);and4)application-specific data processing,such as data aggregation or compression.Simula-tion results show that LEACH is able to achieve the desired properties of sensor networks.
1536-1276/02$17.00©2002IEEE
II.B ACKGROUND
原料油
Since both device and battery technology have only recently matured to the point where microsensor nodes are feasible,this is a fairly new field of study.Researchers have begun discussing not only the uses and challenges facing sensor networks[2], [7],[20],but have also been developing preliminary ideas as to how these networks should function[4],[5],[13]as well as the appropriate low-energy architecture for the sensor nodes them-selves[6],[21].
There have been some application-specific protocols devel-oped for microsensor networks.Clare et
al.developed a time-divison multiple-access(TDMA)MAC protocol for low-energy operation[5].Using a TDMA approach saves energy by al-lowing the nodes to remain in the sleep state,with radios pow-ered-down,for a long time.Intanagonwiwat et al.developed di-rected diffusion,a protocol that employs a data-driven model to achieve low-energy routing[13].
Recently,there has been much work on“power-aware”routing protocols for wireless networks[19],[25].In these protocols,optimal routes are chosen based on the energy at each node along the route.Routes that are longer,but which use nodes with more energy than the nodes along the shorter routes,are favored,helping avoid“hot spots”in the network. In LEACH,we use randomized rotation of the cluster head positions to achieve the same goal.
One method of choosing routes is to use“minimum transmis-sion energy”(MTE)routing[8],[24],where intermediate nodes are chosen such that the sum of squared distances(and,hence, the total transmit energy power loss)is
minimized.Thus,for three nodes A,B,and C,node A would transmit to node C through node B if and o
nly if
(1)
or
Fig.1.Time line showing LEACH operation.Adaptive clusters are formed during the set-up phase and data transfers occur during the steady-state phase. Fig.1.The following sections describe the cluster head selection and distributed cluster formation algorithms and the steady-state operation of LEACH.
A.Cluster Head Selection Algorithms
excoLEACH forms clusters by using a distributed algorithm, where nodes make autonomous decisions without any central-ized control.Our goal is to design a cluster formation algorithm such that there are a certain number of
clusters,
elects itself to be a cluster head at the beginning
round
.Thus,if there
are
has been a cluster head in the most recent
(
with
probability
is eligible to be a
cluster head at
time
represents the total number of nodes that are eligible to be a
cluster head at
time
based on our energy dissipation models for computation and
communication.
This choice of probability for becoming a cluster head is
based on the assumption that all nodes start with an equal
amount of energy,and that all nodes have data to send during
each frame.If nodes have different amounts of energy(or an
event-driven model is used,whereby nodes only send data
when some event occurs in the environment),the nodes with
more energy should be cluster heads more often than the nodes
with less energy,to ensure that all nodes die at approximately
the same time.This can be achieved by setting the probability
of becoming a cluster head as a function of a node’s energy
level relative to the aggregate energy remaining in the network,
rather than purely as a function of the number of times the node
has been cluster head,
Thus
(6)
where
and
.
Note that to compute the probabilities in(3)and(6)requires
that each node knows the
parameters.In this paper,
we assume these parameters are programmed into the nodes a
priori.However,this approach does not work well in dynamic
networks.As we show in Section IV-B,the optimal number of
clusters distributed
throughout
an
>(E
only need to determine
sages it receives—this is that node’s estimate for
Fig.4.Time line showing LEACH operation.Data transmissions are explicitly scheduled to avoid collisions and increase the amount of time each non-cluster head node can remain in the sleep state.
frame of data depends on the number of nodes in the cluster. Fig.4shows the time line for one round
of LEACH.We as-sume that the nodes are all time synchronized and start the set-up phase at the same time.This could be achieved,for example,by having the BS send out synchronization pulses to the nodes. To reduce energy dissipation,each non-cluster head node uses power control to set the amount of transmit power based on the received strength of the cluster head advertisement.2 Furthermore,the radio of each non-cluster head node is turned off until its allocated transmission time.Since we optimize our design for the situation when all the nodes have data to send to the cluster head,using a TDMA schedule is an efficient use of bandwidth and represents a low-latency and energy-efficient approach.
中脑边缘系统The cluster head must be awake to receive all the data from the nodes in the cluster.Once the cluster head receives all the data, it performs data aggregation to enhance the common signal and reduce the uncorrelated noise among the signals.In our anal-ysis,we assume perfect correlation such that all individual sig-nals can be combined into a single representative signal.The resultant data are sent from the cluster head to the BS.Since the BS may be far away and the data messages are large,this is a high-energy transmission. The preceding discussion describes communication within a cluster,where the MAC and routing protocols are designed to ensure low energy dissipation in the nodes and no collisions of data mess
ages within a cluster.However,radio is inherently a broadcast medium.As such,transmission in one cluster will affect(and often degrade)communication in a nearby cluster. To reduce inter-cluster interference,each cluster in LEACH communicates using direct-sequence spread spectrum(DSSS). Each cluster uses a unique spreading code;all the nodes in the cluster transmit their data to the cluster head using this spreading code and the cluster head filters all received energy using this spreading code.This is known as transmitter-based code assignment[12],since all transmitters within the cluster use the same code.The first cluster head to advertise its position is assigned the first code on a predefined list,the second cluster head to advertise its position is assigned the second code,and so on.3With enough spreading,neighboring clusters’radio signals will be filtered out as noise during decorrelation and not corrupt the transmission from nodes in the cluster.To reduce the possibility of interfering with nearby clusters and reduce its own energy dissipation,each node adjusts its transmit power. 2To ensure connectivity in a dynamic environment,the node can either set its transmit power slightly greater than the minimum needed to reach the cluster head,or the cluster head can send short feedback messages to each of the nodes telling them to increase or decrease their transmitted power,as is done in cellular systems.
3If there are more clusters than spreading codes,some clusters will use the same code,possibly cau
sing data collisions if the clusters are located close to each other.Therefore,there will be few overlapping transmissions and little spreading of the data is actually needed to ensure a low probability of collision.
Data is sent from the cluster head nodes to the BS using a fixed spreading code and CSMA.When a cluster head has data to send(at the end of its frame),it must sense the channel to see if anyone else is transmitting using the BS spreading code. If so,the cluster head waits to transmit the data.Otherwise,the cluster head sends the data using the BS spreading code. Other channelization techniques,such as having each cluster use a different frequency ,FDMA),are possible.How-ever,since the number of clusters in LEACH is not fixed,using DSSS ensures that all nodes will receive better communication channels when there are fewer clusters.It is much harder to dy-namically assign frequency bands so that all the bandwidth is utilized in a fixed channelization scheme.Of course,the draw-back of using DSSS is the need for tight timing synchronization, which may necessitate extra communication between the cluster head and the non-cluster head nodes.
D.LEACH-C:BS Cluster Formation
While there are advantages to using LEACHs distributed cluster formation algorithm,this protocol off
ers no guarantee about the placement and/or number of cluster head nodes. Since the clusters are adaptive,obtaining a poor clustering set-up during a given round will not greatly affect overall performance.However,using a central control algorithm to form the clusters may produce better clusters by dispersing the cluster head nodes throughout the network.This is the basis for LEACH-centralized(LEACH-C),a protocol that uses a centralized clustering algorithm and the same steady-state protocol as LEACH.c型卡环
During the set-up phase of LEACH-C,each node sends in-formation about its current location(possibly determined using a GPS receiver)and energy level to the BS.In addition to de-termining good clusters,the BS needs to ensure that the energy load is evenly distributed among all the nodes.To do this,the BS computes the average node energy,and whichever nodes have energy below this average cannot be cluster heads for the current round.Using the remaining nodes as possible cluster heads,the BS finds clusters using the simulated annealing algorithm[16] to solve the NP-hard problem of
finding
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议