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

A3: A Topology Construction Algorithm for Wireless Sensor Networks   (Citations: 1)
BibTex | RIS | RefWorks Download
Topology control is a well-known 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 energy-efficient topology construction mechanism that finds a sub-optimal Connected Dominating Set (CDS) to turn unnecessary nodes off while keeping the network connected and providing complete communication coverage. A3 utilizes a weighted distance-energy-based 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 well-known 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- Rule-K algorithms, respectively. More importantly, the proposed protocol presents a low linearly bounded worst-case amount of messages per node that limits the overhead and the energy usage compared to a non-linear increase of the EECDS and CDS-Rule- 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 well-known 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 energy-efficient 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. This paper introduces A3 (a tree), a topology construction protocol that addresses the problem of finding a reduced topol- ogy. A3 finds a sub-optimal Connected Dominating Set (CDS) to turn unnecessary nodes off while keeping the network con- nected and covered. The algorithm is based on a growing-tree 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 short-live network with a larger number of nodes, and a less reliable longer-lasting 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 energy-efficient. First, the CDS tree building process is done in only one phase and the node selection process avoids the use of node contest or two-hop 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 CDS-Rule-K (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 CDS-Rule-K 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 CDS-Rule-K 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.
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.
Sort by: