Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(11)
Computational Complexity
Connected Dominating Set
Energy Consumption
Energy Efficient
Energy Saving
Low Energy
Network Connectivity
Network Lifetime
Simulation Experiment
Topology Control
Wireless Sensor Network
Subscribe
Academic
Publications
A3: A Topology Construction Algorithm for Wireless Sensor Networks
A3: A Topology Construction Algorithm for Wireless Sensor Networks,10.1109/GLOCOM.2008.ECP.74,Pedro M. Wightman,Miguel A. Labrador
Edit
A3: A Topology Construction Algorithm for Wireless Sensor Networks
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Pedro M. Wightman
,
Miguel A. Labrador
Topology control
is a wellknown strategy to save energy and extend the lifetime of
wireless sensor
networks. This paper introduces the A3 (a tree) algorithm, a simple, dis tributed, and energyefficient topology construction mechanism that finds a suboptimal
Connected Dominating Set
(CDS) to turn unnecessary nodes off while keeping the network connected and providing complete communication coverage. A3 utilizes a weighted distanceenergybased metric that permits the network operator to trade off the lengths of the branches (distance) for the robustness and durability of the tree (energy). Comparisons with other wellknown topology construction mechanisms show the superiority of the proposed scheme in terms of the number of active nodes and energy efficiency. Simulation experiments show that to achieve complete communication coverage, A3 needs only 6% and 41% of the nodes active in dense and sparse scenarios, versus 8% and 43% and 5% and 43% of the EECDS and CDS RuleK algorithms, respectively. More importantly, the proposed protocol presents a low linearly bounded worstcase amount of messages per node that limits the overhead and the energy usage compared to a nonlinear increase of the EECDS and CDSRule K algorithms. I. INTRODUCTION
Wireless Sensor
Networks (WSNs) continue to be very pop ular given the large number of application domains where they can provide useful information about. Nevertheless, WSNs also continue to be very limited in terms of computational, communication, storage, and energy resources and capabilities. Of all these constraints it is wellknown that energy conserva tion is the most important aspect and that communications is the most expensive function in terms of
energy consumption
(2). Therefore, the design of energyefficient protocols and algorithms continues to be of utmost importance. One known strategy to save energy in WSNs is that of
Topology Control
(TC). TC consists of two separate compo nents: the topology construction mechanism, which finds a re duced topology while preserving important network properties, such as
network connectivity
and coverage, and the topology maintenance mechanism, which changes the reduced topology when it can't provide the requested service any longer. It is expected that these two mechanisms will work in a iterative manner until the network energy is depleted, and together will increase the
network lifetime
compared with a continuously run WSN without topology control. 1 Professor on leave from Universidad del Norte, Barranquilla, Colombia. www.uninorte.edu.co This paper introduces A3 (a tree), a topology construction protocol that addresses the problem of finding a reduced topol ogy. A3 finds a suboptimal
Connected Dominating Set
(CDS) to turn unnecessary nodes off while keeping the network con nected and covered. The algorithm is based on a growingtree technique and uses a selection metric based on the remaining energy on the nodes and distance among them. The selection metric allows the network operator to choose between a more reliable shortlive network with a larger number of nodes, and a less reliable longerlasting tree with fewer nodes. In addition, the A3 algorithm presents the following advantages: a) A3 is very scalable, as it only needs local information and operates in a completely distributed manner; b) A3 does not need location information; no GPS or any localization mechanism is necessary; c) A3 requires no synchronization scheme thanks to the ordered sequence of the tree creation; d) A3 is simple, and presents low computational complexity; and e) A3 is very energyefficient. First, the CDS tree building process is done in only one phase and the node selection process avoids the use of node contest or twohop information queries, which reduces the amount of overhead. Second, the small number of active nodes after the topology construction reduces the number of collisions considerably. Finally, A3 has a low and linearly bounded message complexity, which allows for the algorithm to be run many times as part of the
topology control
iterative cycle with very
low energy
cost. The A3 algorithm is evaluated using simulations and com pared with the
Energy Efficient
CDS (EECDS) (14) and the CDSRuleK (11) algorithms. The results demonstrate that in terms of the number of active nodes needed to build the reduced topology, the A3 protocol performs better than the EECDS and CDSRuleK mechanisms. A3 only needs 6% and 41% of the nodes active in dense and sparse scenarios while preserving
network connectivity
and communication coverage, versus 8% and 45% and 9% and 49% of the EECDS and CDSRuleK algorithms, respectively. More impressive is the significant difference in the amount of messages required for the creation of the CDS tree, where A3 presents a bounded, low, and linear message complexity compared with an non linear increase of the other two mechanisms. This low message complexity is essential to realize energy savings in topology controlled networks compared with WSNs that run continu ously without topology control.
Conference:
Global Telecommunications Conference, . GLOBECOM . IEEE  GLOBECOM
, pp. 346351, 2008
DOI:
10.1109/GLOCOM.2008.ECP.74
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
dx.doi.org
)
(
www.cse.usf.edu
)
(
www.informatik.unitrier.de
)
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(1)
...In the architectural design of WSN, the route technology has been the hot spot in the recent years [
2
]...
Yuhua Liu
,
et al.
A reliable clustering algorithm base on LEACH protocol in wireless mob...
References
(10)
Span: an EnergyEfficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks
(
Citations: 1135
)
Benjie Chen
,
Kyle Jamieson
,
Hari Balakrishnan
Journal:
Wireless Networks  WINET
, vol. 8, no. 5, pp. 481494, 2002
Approximation Algorithms for Connected Dominating Sets
(
Citations: 532
)
Sudipto Guha
,
Samir Khuller
Conference:
European Symposium on Algorithms  ESA
, pp. 179193, 1996
ESPAN: enhancedSPAN with directional antenna
(
Citations: 4
)
Vivek Kumar
,
Thenmozhi Arunan
,
N. Balakrishnan
Conference:
TENCON, IEEE Region 10 International Conference  TENCON
, 2003
Design and Analysis of an MSTBased Topology Control Algorithm
(
Citations: 380
)
Ning Li
,
Jennifer C. Hou
,
Lui Sha
Conference:
IEEE INFOCOM  INFOCOM
, vol. 3, pp. 17021712 vol.3, 2003
The longest edge of the random minimal spanning tree
(
Citations: 228
)
Mathew D. Penrose
Journal:
Annals of Applied Probability  ANN APPL PROBAB
, vol. 7, no. 1997, pp. 340361, 1997
Sort by:
Citations
(1)
A reliable clustering algorithm base on LEACH protocol in wireless mobile sensor networks
Yuhua Liu
,
Zhenrong Luo
,
Kaihua Xu
,
Lilong Chen
Conference:
International Conference on Mechanical and Electrical Technology  ICMET
, 2010