Performance Evaluation of a Topology Control Algorithm for Wireless Sensor Networks

Abstract

A main design challenge in the area of sensor networks is energy efficiency to prolong the network operable lifetime. Since most of the energy is spent for radio communication, an effective approach for energy conservation is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. Assuming that node position information is unavailable, we present a topology control algorithm, termed OTC, for sensor networks. It uses two-hop neighborhood information to select a subset of nodes to be active among all nodes in the neighborhood. Each node in the network selects its own set of active neighbors from among its one-hop neighbors. This set is determined such that it covers all two-hop neighbors. OTC does not assume the network graph to be a Unit Disk Graph; OTC also works well on general weighted network graphs. OTC is evaluated against two well-known algorithms from the literature, namely, Span and GAF through realistic simulations using TOSSIM. In terms of operational lifetime, load balancing and Spanner property OTC shows promising results. Apart from being symmetric and connected, the resulting graph when employing OTC shows good spanner properties.

1. Introduction

Advances in miniaturization of microelectronic and mechanical structures (MEMSs) have led to battery-powered sensor nodes that have sensing, communication, and processing capabilities [1, 2]. These sensor nodes can be networked in an ad hoc fashion to perform distributed sensing and information processing in many situations. Such sensor networks are typically inexpensive and can be deployed in inhospitable terrains or in hostile environments to provide continuous monitoring. Wireless sensor networks have therefore attracted considerable attention recently [2–4]. These networks are important for a number of applications such as coordinated target detection and localization, surveillance, and environmental monitoring. In the recent years, wireless sensor networks have been deployed for a number of applications. In the spring of 2002, the Intel Research Laboratory at Berkeley initiated a collaboration with the College of the Atlantic in Bar Harbor and the University of California at Berkeley to deploy wireless sensor networks on Great Duck Island, Maine [5, 6]. These networks monitor the microclimates in and around nesting burrows used by Leach's storm Petrel. The goal of this project is to develop a habitat monitoring kit that enables researchers worldwide to engage in the nonintrusive and nondisruptive monitoring of sensitive wildlife and habitats.

A sensor network may consist of a large number of sensor nodes. A sensor node relies on wireless channel for transmitting data to and receiving data from other nodes. The maximum distance that a node can communicate with another node is characterized by the communication unit on the sensor node. For instance, the RF sensors used in the Berkeley Mote [7] have a maximum operation range of up to 150 m. The sensing area of a sensor node depends on the type of physical sensors used on that node. For example, a range sensor such as the Polaroid 6500 ultrasonic ranging module commonly used in robotics applications, is able to detect a target from 15 cm away up to a distance of 11 m [8]. The attributes of some commercially available nodes are listed in Table 1.

Table 1

Specifications of inexpensive wireless sensors.

Model	MICA2	MICA2DOT	MICAz
Battery	2× AA batteries	3 V Coin Cell	2× AA batteries
Size (mm)	58 × 32 × 7	25 × 6	58 × 32 × 7
Weight (g)	18	3	18
Data rate	38.4 Kbaud	38.4 Kbaud	250 kbps
Program flash memory	128 Kbytes	128 Kbytes	128 Kbytes
Serial flash memory	512 Kbytes	512 Kbytes	512 Kbytes
EEPROM	4 Kbytes	4 Kbytes	4 Kbytes
Frequency band (MHz)	868/916	868/916	2400/2483.5
Outdoor range	150 m	150 m	75 m to 100 m

Due to nodes limited resources, many of the methods developed for the Internet and mobile ad hoc networks cannot be directly applied to sensor networks. An important consideration here is the amount of energy required for sensing, computation, and communication. The operable lifetime of a sensor node depends to a large extent on the battery lifetime; hence, it is extremely important to adopt energy-efficient strategies to prolong the network lifetime. More specifically, if the number of sensor nodes is more than the required, some of them can be scheduled to turn off their power. These powered-off sensors can be activated later to exchange their role with some powered-on sensors. The scheduling should always guarantee a certain level of connectivity. Ensuring communication connectivity is essential when scheduling sensors' on-duty time. Connectivity normally means that there is at least one path connecting any two on-duty sensor nodes.

Topology control is an important technique in this direction. The topology control problem can be formalized as follows. Let the graph $G = (V, E)$ denote the sensor network before running a topology control algorithm, with V being the set of sensor nodes, and E representing the set of communication links. There is a link $(u, v)$ in E if and only if the two nodes u and v can communicate directly. Running the topology control algorithm will yield a sparse subgraph $G_{TC} = (V_{TC}, E_{TC})$ of G, where $V_{TC}$ is the set of remaining sensor nodes, and $E_{TC}$ is the set of remaining links. Our goal in performing topology control is to find an undirected subgraph $G_{TC}$ from the original graph G that has the following properties.

Property 1 (symmetry).

The resulting topology $G_{TC}$ should be symmetric, that is, node u is a neighbor of node v if and only if node v is a neighbor of node u. Asymmetric communication graphs are impractical, because many communication primitives become unacceptably complicated [9]. A simple ACK message confirming the receipt of a message, for example, is already a difficult proposition in an asymmetric graph [10].

Property 2 (connectivity).

Two nodes u and v are connected if there is a path from u to v, potentially through multiple hops. If two nodes are connected in G, then they should still be connected in $G_{TC}$ .

Property 3 (spanner).

For any two nodes u and v, if the optimal path between u and v in G has cost c, then the optimal path between u and v in $G_{TC}$ has cost $f (c)$ , which is bounded from above by a linear function in c. The Graph $G_{TC}$ is called a spanner. Researchers have studied a selection of cost metrics, the most popular being (1) Euclidean distance and (2) various energy metrics. The cost of a link in model (1) is the Euclidean distance of the link, in model (2) the distance is raised to a predefined power. In both models, the cost of a path is commonly defined to be the sum of the costs of all links in the path.

Property 4 (sparseness).

The remaining graph $G_{TC}$ should be sparse, that is, the number of links should be in the order of the number of nodes (i.e., $| E_{TC} | = O (| V |)$ ). This reduces interference and thus saves energy.

Property 5 (low/bounded degree).

Each node in the remaining graph $G_{TC}$ has a small number of neighbors. In particular the maximum degree in the graph $G_{TC}$ should be bounded from above by a constant [11].

Property 6 (localized construction).

This reflects the ability of each node u to build its view of the network topology based on the information of all nodes within constant hops of u, usually two or three hops away. Locality implies that the network topology can be easily reconfigured when nodes leave or join the network, and in case of mobility.

Property 7 (fully distributed).

Centralized approaches are failed to perform efficiently in realistic application scenarios. For this reason constructing the topology in a fully distributed fashion is a crucial design challenge.

Since spanner property and sparseness run against each other, topology control has been a thriving research area [9]. In addition to the above properties, one can often find secondary targets. For instance, it is popular to ask the remaining graph to be planar in order to run a geometric routing algorithm, such as GOAFR/GOAFR+ [12, 13], or GFG/GPSR [14, 15].

Another primary technique for achieving low energy consumption in energy-constrained sensor networks is duty cycling. In this approach, each sensor node periodically cycles between an awake and a sleep state. Key parameters that characterize the duty cycle include sleep time, wake time, and the energy consumed during the awake state and the sleep state. Standard MAC protocols developed for duty-cycled sensor networks can be categorized into synchronized and asynchronous approaches, along with hybrid combinations [16]. These approaches intend to reduce idle listening, which is the time that the node is awake listening to the medium even when there is no packets to be transmitted to that node. This technique and topology control are orthogonal, so their benefits could potentially be combined.

In this paper, we introduce the OTC topology control algorithm, and show that it satisfies all these desiderata. Most previous papers on topology control have restricting assumptions such as exact node location is known, which usually requires the availability of GPS at each node such as GAF [17]. Also, world is flat and without obstacles or buildings. Sensor networks are usually deployed in environments characterized by presence of obstacles (e.g., walls, buildings, lakes, rivers, etc.). The problem of obstacles avoidance in realms of wireless sensor networks is important. The impact of obstacles on the performance, and even correctness, of protocols can be significant. Several geographic routing with obstacles avoidance techniques were proposed so far in the literature [18–20], most of them are concerned mainly in guaranteeing the delivery. They try to identify the presence of the object early on the routing path and redirect the messages on a shorter path (i.e., geographic forwarding) as soon as possible.

By way of contrast, OTC is a novel topology control algorithm that increases network lifetime while maintaining connectivity, guaranteeing multihop reachability from any source to any destination with a reasonable throughput. OTC is built on the notion that when a region of a shared channel wireless sensor network has a sufficient density of nodes, significant energy saving is obtained by allowing redundant nodes to sleep. Using the two-hop neighborhood information (merely neighbor ID, and its neighbors' IDs), selected nodes sequentially select a subset of nodes to be active among all nodes in the neighborhood to ensure connectivity. Moreover, to ensure fairness, the role of active nodes is rotated periodically to ensure energy-balanced operations. Our proposed algorithm achieves and proves several properties on both Euclidean and general weighted graphs; apart from being symmetric and connected, the resulting graph also shows good spanner properties. On the average-case unit disk graphs, the resulting topology features the bounded degree property. We evaluated OTC against two well-known and comparable algorithms, namely, Span and GAF. Our results demonstrate that OTC outperforms Span and GAF due to its clever neighbor discovery mechanism.

Our evaluations are based on simulations, and we have used the TOSSIM [21, 22] sensor network simulator for this purpose. TOSSIM is a an event-driven simulation tool, where an application written in the TOSSIM environment can also work on actual sensor nodes running TinyOS [23] operating system with minor changes. This evaluation provides a more realistic account of the proposed algorithm against others in the literature. The actual limitations of sensor node hardware are captured by TOSSIM to allow a fair benchmarking of OTC against two well known schemes in the literature, namely, Span [24] and GAF [17].

The rest of the paper is organized as follows. Section 2 reviews related work. We discuss OTC in Section 3, which describes design and implementation issues in depth. We prove the algorithm properties in Section 4. Time complexity of the algorithm is determined in Section 5. The adopted methodology and simulation environment are discussed in Section 6. We present the simulation results in Section 7. Finally, we conclude the paper in Section 8.

2. Related Work

Prolonging network lifetime by minimizing per node energy consumption has been considered under various approaches: clustering, adjusting nodes' transmission power levels, balancing energy consumption among sensor nodes and topology control are among existing strategies. In this section, we give a brief survey of energy saving algorithms for wireless sensor networks.

Clustering with data aggregation is an important technique to conserve energy in sensor networks. Several clustering techniques in different context have been proposed in the literature. Most algorithms aim at generating the minimum number of clusters and transmission distance. These algorithms also distinguish themselves by how the cluster heads (CHs) are elected. Generally, clustering algorithms segment a network into clusters comprising a CH each. Non-CH nodes transmit sensed data to CHs, where the sensed data could be aggregated as these signals could be sufficiently correlated due to the nodes spatial proximity, and transmitted to the base-station (i.e., sink). Clustering algorithms may be distinguished by the way the CHs are elected.

The Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm [25] and its related extensions [26–28] use probabilistic self-election, where each sensor node has a probability p of becoming a CH in each round. It guarantees that every node becomes a CH only once in 1/p rounds. Such role rotation aims to distribute the energy usage for a more load-balanced operation. However, LEACH assumes all nodes are able to reach the sink directly, and requires position knowledge to perform a precise transceiver power control. Some of previously proposed algorithms were designed to generate stable clusters in environments with mobile nodes. In a typical sensor network, the sensor nodes are stationary, and the instability of clusters due to mobility of these nodes may not be an issue. Drawing from the wealth of clustering proposals for both MANETs and WSNs, The Hybrid Energy-Efficient Distributed (HEED) clustering is proposed in [29] to adopt real-valued weight-based clustering. It uses residual energy as the primary clustering parameter to probabilistically elect a number of tentative CHs, and then advertises to their neighbors of their intentions to become CHs. Such messages include a secondary cost measure that is a function of neighbor proximity or cluster density. This secondary cost is mainly used to avoid elected CHs to be in range of each other, and to guide the regular nodes in choosing the best cluster to join. This proposal is generally able to achieve a good CH distribution across the network.

In [30], the authors propose a simple heuristic to minimize the maximal transmission power of each node in the network. The approach basically employs a minimum spanning tree construction. However, the initial energies of all hosts were assumed to be the same. The topology control algorithm presented in [31] extends the work of [30], but computing 2-connected components is still not distributed. While the basic approach employs a minimum spanning tree construction, the result is optimal under the fixed power model. Thus, the contribution lies in extending the applicability of the work in [31] to the case where hosts' initial energies can differ. Under the variable power assumption, several sufficient conditions have been proposed to reflect when re-evaluating the network topology may be necessary.

The cone-based topology control algorithm (CBTC) [32] achieves and proves several properties. Besides being symmetric, an energy spanner and a sparse graph, there is a distributed second phase that reduces the degree of the graph. An analysis of CBTC algorithm is presented in [33] and proves that 5π/6 is a tight upper bound on the cone degree for the algorithm to preserve connectivity. Also, the authors have presented three optimizations to the basic algorithm—the shrink-back operation, asymmetric edge removal, and pairwise edge removal—and proved that these improve performance while still preserving connectivity. Finally, they showed that there is a tradeoff between using CBTC(α) with $α = 5 π / 6$ and $α = 2 π / 3$ , as using the latter allows an additional optimization, which can have a significant impact. The algorithm extends easily to deal with reconfiguration and asynchrony. Most importantly, simulation results show that it is very effective in reducing power demands.

The idea of extending the lifetime of sensor network by balancing energy consumption among sensors has been widely investigated in the literature. This problem has been studied in a setting, where the network is divided into slices and energy consumption studied at the slice level [34, 35].

In [35], a distributed algorithm is proposed. Each sensor transmits data directly to the sink or to neighbor nodes. The algorithm is inspired by the gradient based routing family of protocols from [36] and uses a local heuristic to balance out energy consumption among neighbor nodes. It is shown experimentally that the algorithm converges to an energy-balanced solution in the case of uniform distribution of events and sensors. An analytical proof of the convergence of the algorithm is also given using Markov chain theory in the restricted line model.

In [34], the authors address the problem of finding an energy-balanced solution to data propagation in sensor networks using a probabilistic algorithm. The operational lifetime of the network is maximized by ensuring that the energy consumption in each slice is the same. Sensors are assumed to be deployed uniformly at random in a circular region or, more generally, the sector of a disk. Data have to be propagated by the sensor network towards a sink located at the centre of the disk, and it is shown that energy balance can be achieved if a recurrence relation between the probabilities that a slice ejects a message to the sink is satisfied.

There are various proposals in the area of topology control, mostly validated either using theoretical analysis or simulation. Most of this work focuses on the analysis of algorithms for distributed construction of a connected dominating set (CDS) of the corresponding unit disk graph and the routing strategies using the CDS backbone. Authors in [37] describe a distributed algorithm for constructing an approximated minimum connected dominating set (MCDS) for the unit disk graph with a constant approximation ratio of the minimum CDS in linear time and message complexity. In [38], the authors proposed an algorithm to build a geometric spanner that can be implemented in a distributed manner. The node degree is bounded by a positive constant, and the resulting backbone is a spanner for both hop-count and Euclidean distance.

In [9], the authors introduced the XTC topology control algorithm. It removes an edge $(u, v)$ if, according to some path-loss model, there is a two-hop path from u to v which nevertheless requires less energy than the direct path. For the global case of the network graph being a general weighted graph, XTC computes a resulting subgraph, while maintaining connectivity. The resulting topology features the bounded degree property provided that the neighbors are ordered by Euclidean distance, since neighbors are not normally ordered and the network is a unit disk graph. Also, the authors were able to prove the planarity property for the algorithm. On average-case random unit disk graph, the resulting graph also shows good spanner properties, above all with respect to the energy metric. There is no proof that XTC has spanner properties on general weighted graph or even on unit disk graph.

Our proposal does not assume the nodes to be placed in a two-dimensional surface or the network graph to be a unit disk graph, such as [9, 33, 37–39]. However, a unit disk graph is impractical, since it assumes the signal attenuation is uniform, which implies that the world is flat and without any obstacles. Also, unit disk graphs are not realistic mainly because antennas are not uniformly multidirectional, especially in cheap sensors. In realistic sensor networks, nodes are not located in a plane and received signal strength does not solely depends on the distance to the sender [40–42]. For example, environment factors (e.g., weather and physical obstacles between sender and receiver) can severely affect radio characteristics, causing irregular, nonuniform and dynamic radio propagation patterns at different sensor nodes. We believe that sensor network algorithms should work in a more hostile environment that goes beyond this assumption.

Some other assumptions that are commonly made in the literature are the availability of additional hardware, such as dual radio or double antenna [39] at each node, or exact location information is available by the mean of GPS, such as GAF [17], which restricting the use of the algorithm. There is also a direct relationship between information quality and energy efficiency of the constructed topology: the more accurate the information available to the nodes, the more energy savings can be achieved [43]. By way of contrast, our proposed algorithm rely on a very low-quality information (merely number and identity of neighbor nodes), and can work on any hardware platform.

The details of the OTC algorithm are described next. This is then followed by its analysis.

3. The OTC Topology Control Algorithm

In this section, we describe the design and implementation issues of the proposed algorithm in depth.

3.1. Overview

In OTC, a subset of nodes forms a multihop forwarding backbone to preserve the connectivity of the underlying sensor network, while the remaining nodes are forced to sleep as they are redundant. Our proposed algorithm only keeps a node awake if it is absolutely essential for maintaining connectivity. Redundant nodes spend more time in the sleep state, as they no longer carry the burden of forwarding data at this time. OTC employs a load balancing strategy to balance energy consumption, whereby the backbone role is rotated among nodes. Figure 1 shows OTC in OSI model. This structure allows OTC to exploit the power-saving feature of the link layer protocol, while still being able to influence the routing process.

Figure 1

OTC is a protocol that operates below the network layer and above the MAC layer. The routing protocol uses OTC topology.

To support its functions, OTC includes the following three elements: (i)

a mechanism for neighbor discovery,

(ii)

a mechanism for role alternation,

(iii)

a mechanism for selecting the active nodes in the network.

These elements are described in detail further.

3.2. Discovery Mechanism

Neighbor discovery is the process through which a node discovers and detects changes to its neighborhood. This section will describe its mechanism in detail. For the sake of exposition, some terms are introduced and defined first.

3.2.1. Definitions

Node a is said to be a neighbor of another node b if there exists a direct link between the two nodes a and b, allowing data to be transmitted in both directions of the link. (i.e., communication is possible from node a to node b, that is traffic from node a can be received at node b, and from node b to node a).

Node c is said to be a two-hop neighbor of node a, if node c is not a neighbor of node a and there exists a link between node c and a node in the neighborhood of node a, with which node a has a direct link.

3.2.2. Neighbor Discovery

Our algorithm is a distributed algorithm that uses local broadcast messages to discover and react to changes in the network topology. The OTC algorithm is designed specifically for a static multihop wireless sensor network. Each node must detect the neighbor nodes with which it has a symmetric link. Each node periodically broadcasts a HELLO message (see Figure 2 for the general OTC packet format). Such a message is a packet containing the following. (i)

Source ID: it represents the sender ID.

(ii)

Type: this field is used to differentiate HELLO messages from announcement messages, where 0 refers to a Hello message and 1 refers to an announcement message. The announcement message has dual roles and depends on the Active list values. It may be interpreted as a JOIN message if the message type is 1 and the node is in the sender Active list or a WITHDRAWAL message if the message type is 1 and the node is not in the sender Active list.

(iii)

Node's status: it this field indicates whether or not a node is in active state.

(iv)

Active list: it is a list of node's current active neighbors.

(v)

Neighbor list: it is a list of node's neighbors.

Figure 2

The OTC packet format.

Upon reception of HELLO messages, a node can gather information about its neighborhood and its two-hop neighborhood. Each node extracts a list of its all neighbors and active neighbors, and for each neighbor, its active neighbors. Such information must be refreshed periodically to detect the changes in the topology. Each node updates its local knowledge about its neighbors with each received HELLO message. An update of the neighbor table entry is needed in three cases: (i)

a change in the neighborhood is detected when either a link with a neighbor has failed, or a new neighbor is discovered,

(ii)

a change in the two-hop neighbor set is detected, or

(iii)

a direct neighbor or a two-hop neighbor changed its status.

Each node maintains a neighbor table, describing the neighbors and the two-hop neighbors. Such information is considered valid for a limited period of time, and must be refreshed periodically to remain valid. Expired information is purged from the neighbor table.

3.3. Selection of Active Nodes

In this paper, we consider one generic type of applications for sensor networks, in which all nodes periodically produce relevant information by sensing an extended geographic area that is eventually transmitted through, possibly, multihop to an information sink for processing. OTC selects a group of active nodes from all nodes in the network. Active nodes stay awake continuously and perform multihop packet routing within the sensor network. Other nodes remain in power-saving mode, and periodically check if they should wake up and exchange their roles with the active node. In OTC, a node switches state from time to time to ensure that all nodes share the task of providing global connectivity roughly equally. It is apparent that the most crucial aspect of our topology control scheme is the active node selection scheme. Overall, this selection process involves two main parts. Since OTC is a distributed scheme, selection needs to be localized. The first part concerns with initiating the selection, whereby one seed (i.e., the first node to run the algorithm) nodes is chosen. The second part involves this node to recursively select their one-hop neighbors to cover the entire network, while ensuring redundant nodes are made to sleep.

Each node in the network selects a set of nodes from its one-hop neighborhood, as illustrated in Figure 3. This set of selected neighbor nodes is called its active list. This set is selected such that the node is able to reach all its two-hop neighbors via the active list. The active list of u, denoted as $A (u)$ , is then an arbitrary subset of the one-hop neighborhood of u which satisfies the following condition: every node in the two-hop neighborhood of u must have a path towards u. For the seed node, the sink randomly chooses one of its neighbors (i.e., the seed node) to initiate the selection process. The selection of active nodes then sequentially progresses in a breadth-first manner towards the rest of the network.

Figure 3

Example of the active node set selection in OTC.

The selection of the seed node depends on its available energy and node degree. A node with more residual energy and higher node degree can be selected as seed node. Once a node has its one-hop and two-hop neighbor information, it can then select a minimum number of one-hop neighbors which covers all its two-hop neighbors. To select the set of active nodes for node u, let the set of one-hop neighbors of node u be $N (u)$ , and the set of its two-hop neighbors $M (u)$ . The active node selection scheme can now be stated as: (1)

Start with an empty set $A (u)$ . The seed node is the first node u.

(2)

Order the neighbor set $N (u)$ according to node degree, a node with a higher node degree appears first as this increases the probability of choosing a smaller active list. Ties are broken by nodes providing unique reachability. For example, if node b in $M (u)$ can be reached only through a node a in $N (u)$ , then add node a to the active list $A (u)$ .

(3)

Add to $A (u)$ the first nonadded node in $N (u)$ , which is the only node to provide reachability to nodes in $M (u)$ . Remove the nodes from $M (u)$ which are now covered by nodes in $A (u)$ .

(4)

Repeat step (3) while there still exists uncovered nodes in $M (u)$ by at least one node in $A (u)$ .

(5)

Remove node u from $A (u)$ , if its all one-hop neighbors are neighbors of existing nodes in $A (u)$ . This rule ensures a smaller set is selected.

(6)

Node u announces its $A (u)$ to its neighbors with a JOIN message. Nodes in $A (u)$ repeat steps (1)–(5).

3.4. Role Alternation

In OTC, a node can be in one of three states: sleep, listen and active. Figure 4 shows the state transition diagram of a node. Initially, all nodes start out in the listen state. When in the listen state, a node turns on its radio and exchanges HELLO messages to gather information about its neighborhood. In addition, when a node enters the listen state, it sets up a timer $T_{l}$ . When $T_{l}$ expires, if the node did not receive an announcement message from its neighbor nodes, the node enters the active state. If before $T_{l}$ expires, the node receives a WITHDRAWAL message (i.e., its node ID is not found in the sender's active list) from its neighbors, then the node turns off its radio and moves into the sleep state, or if the node received a JOIN message (i.e., its node ID is found in the sender active list), then the node moves into active state and broadcast its own active set.

Figure 4

State transitions of a node in OTC.

When the node enters the active state, it sets a timeout value $T_{a}$ to determine how long it should stay active. After $T_{a}$ expires, the node moves back into the listen state. A node in the active state periodically checks if it should turn its radio off, and move into the sleep state. This decision is based on the following eligibility rule; it checks whether every pair of its neighbors can reach each other within two hops. A node delays its withdrawal announcement with a randomized backoff delay. When the backoff delay timer expires, the node reassesses its withdrawal eligibility. If the withdrawal it is still valid, it announces its withdrawal (i.e., sending an announcement message with status field value is set to nonactive) and transits to the sleep state. When transiting to the sleep state, a node cancels all timers, sets the sleep timer $T_{s}$ and turns off its radio. A node in the sleep state returns to the listen state after an application dependent sleep time $T_{s}$ .

3.5. Algorithm Description

In OTC algorithm, which is summarized in Algorithm 1, every node u in the network broadcasts its ID to all its neighbor nodes (i.e., nodes within u's transmitting range). Upon receiving broadcast messages from other nodes, every node keeps track of its neighbors. After all the initial messages (i.e., step (2)) have been sent/received, every node in the network knows its neighbor set and for each neighbor its set of neighbors.

Algorithm 1: OTC algorithm running at each node u.

OTC ALGORITHM

$N (u)$ : is the set of 1-hop neighbors of node u.

$M (u)$ : is the set of 2-hop neighbors of node u.

$F N (u)$ : is the neighbor set of node u in the final topology.

(1) Initialization:

$N (u) = \emptyset$ .

$M (u) = \emptyset$ .

$F N (u) = u$ .

(2) Neighbor discovery:

(2a) ID broadcast:

Broadcast a HELLO message.

(2b) Neighbors detection:

Upon receiving HELLO message from node v, store this information:

$N (u) = N (u) \cup {v} .$

(2c) Broadcast a HELLO message again.

Upon receiving a HELLO messages:

$M (u) = M (u) \cup N (v) - N (u) .$

(3) Determine final neighbor set:

After all the messages from neighbors have been received

(3a) Order nodes in $N (u)$ according to their node degree,

a node with a higher node degree appears first in $N (u)$ .

(3b) While ( $N (u)$ contains unprocessed neighbors) ${$

v = least unprocessed neighbor in $N (u)$ .

If v has a neighbor which is not a neighbor for any node in $F N (u)$

Add v to $F N (u)$

else

continue.

$}$

(3c) For each node v in $F N (u)$

If every neighbor of v is a neighbor of at least one of the nodes in $F N (u)$

$F N (u) = F N (u) - {v}$

else

continue.

(4) Broadcast final neighbor set:

After determining final neighbor set $F N (u)$ .

Broadcast $F N (u)$ .

(5) Receives $F N (u)$ for all neighbor nodes u:

If v is in $F N (u)$ (JOIN message received)

Transit to active state.

Determine v's final neighbor set $F N (v)$ ,

else

Transit to sleep state.

Broadcast new starus (WITHDRWAL message).

(6) Update final neighbor set:

For every selected node u

u receives all $F N (v)$ for all of its neighbors v,

If v is selected and u is not in $F N (v)$ then add u to $F N (v)$ .

(7) Generate a sparser topology (optional step):

If every pair in $N (u)$ can reach each other directly or via one

or two other nodes (rather than u) from $F N (u)$ .

Transit to sleep state.

Broadcast new status,

else

Continue.

(8) Repeat step (6):

If receives messages from step (7) repeat step (6) until no messages are received.

Algorithm 2: The modified OTC algorithm, M_OTC.

Add to the OTC algorithm step (3d)

(3d) For each node v in $M (u)$ :

If there is a node w in $F N (u)$ that provides a path to v with a cost $\leq 2$

times minimal cost.

continue.

else

add to $F N (u)$ a node w from $N (u)$ such that node w provides

a path to $v_{i}$ with a cost $\leq 2$ times minimal cost.

$F N (u) = F N (u) + {w} .$

The main step of OTC, that is, the computation of the final topology, can be done locally at each node, with no further message exchange. To compute the network topology, node u considers its neighbors in decreasing order of node degree. When considering a certain neighbor v, it checks whether v has a neighbor which is not a neighbor for any node in $F N (u)$ , which contains the neighbors of u in the constructed network topology. Note that this check can be done locally at node u, which knows v's set of neighbors (because v is a neighbor of u). If the above condition is satisfied, node v is included in the set $F N (u)$ . After all the nodes in $N (u)$ have been processed, we check for each node v in $F N (u)$ whether every neighbor of v is a neighbor of at least one of the nodes in $F N (u)$ . If this condition is satisfied, edge $(u, v)$ is discarded.

Now, set $F N (u)$ is the u's local view of the network topology produced by OTC, which we call $G_{OTC}$ . Once the final neighbor set $F N (u)$ in the resulting network topology has been computed, every node broadcasts its final neighbor set. By exchanging neighbor sets, nodes are able to determine the set of symmetric neighbors and update final neighbor sets (i.e., if v is selected by u and u is not in FN(v), then add it).

As an optional step, the OTC algorithm may decide to generate a sparser topology. Every node u in $G_{OTC}$ , periodically, checks whether it should turn off its radio and transit to sleep state; if every pair of its neighbors can reach each other via one or two other nodes (rather than u). If this condition is satisfied, the node transit to sleep state and broadcast its new status.

In the next sections, we analyze and prove the OTC algorithm main properties on Euclidean and general weighted graphs. This is followed by determining the OTC's time complexity.

4. Analysis of OTC Algorithm

The main purpose of this section is to provide illustration of the graph resulting from topology control algorithm $G_{OTC}$ . The following assumptions are made while designing and evaluating the proposed algorithm. (i)

Every node u has a unique identifier id_u.

(ii)

Nodes are able to determine the number and identity of neighbors within its radio range.

(iii)

Nodes are deployed densely enough. A dense deployment is probably necessary and provides robustness of the network.

All the aforementioned assumptions are common in the context of distributed algorithms and viable for practical sensor networks. A dense deployment approach in the area of sensor networks is also driven by the motivation of the fault tolerance approach. As the network remains unattended a redundant deployment of nodes are desirable. We adopted these assumptions in this section for the sake of illustration.

In this section, we show that OTC algorithm computes a symmetric and connected topology in general weighted graphs modeling realistic sensor networks. Strongly related to edge weights is the cost of an edge. The cost of an edge $c (u, v)$ can be considered to represent the effort an algorithm is required to expend in order to send a message over $(u, v)$ . Common definitions of edge cost metrics include the hop or link metric $c (u, v) \equiv 1$ , and the Euclidean metric $c (u, v) = | u v |$ .

In a weighted graph $G = (V, E)$ every edge $(u, v) \in E$ is attributed a weight $w_{u v}$ . When referring to a weighted graph, we assume that the weights are symmetric: $w_{u v} = w_{v u}$ . In realistic sensor networks nodes are not located in a plane and received signal strength does not solely depends on the distance to the sender [40–42]. For example, environmental impacts (e.g., physical obstacles between sender and receiver) can severely affect radio characteristics, causing irregular, nonuniform and dynamic radio propagation patterns at different sensor nodes. As one of the main properties of such real sensor networks, however, symmetry is preserved: the attenuation factor of a link between two nodes is identical to signal propagation in either direction [9]. Accordingly, a sensor network can be modeled by a weighted graph, where each edge attributed a weight representing the corresponding signal attenuation factor. More abstractly the edge weights can be considered qualities of links between node pairs.

Theorem 1 (symmetry).

Given a general weighted graph G. The edges in the resulting graph $G_{OTC}$ are symmetric. A node u includes a neighbor v in $F N (u)$ , if and only if v includes u in $F N (v)$ .

Proof.

It suffices to prove that for all v neighbors of u, $v \in F N (u) \Leftrightarrow u \in F N (v)$ .

The symmetry theorem holds since all selected nodes broadcast their FN sets to their neighbors, and they fix up their neighbor sets (see Algorithm 1, step (6)).

The following theorem proves Property 2 as defined in the Introduction that is connectivity of the topology control graph $G_{OTC}$ . Note that this theorem does not require G to be a Unit Disk Graph; G being a Euclidean Graph is sufficient.

Theorem 2 (connectivity).

Given a general weighted graph G. two nodes u and v are connected in $G_{OTC}$ if and only if they are connected in G. Consequently, the graph $G_{OTC}$ is connected if and only if G is connected.

Proof.

It is sufficient to prove that the seed node u is connected to all vertices in $G_{OTC}$ . Consider any vertex t in $G_{OTC}$ . u and t are connected in G by, possibly, several paths. Let m be the longest path length between u, $v_{o}$ . We will prove that u is connected to t by induction on m.

$m = 1$ , t is a neighbor of u, and the two nodes t and u can communicate directly. So the graph is connected.

$m = 2$ , t is a 2-hop neighbor of u, so by definition of the algorithm u must select 1-hop neighbor nodes that cover all 2-hop neighbors, including t. So t has a selected neighbor that is a neighbor of u.

Assume that the property is true for $n \leq k$ .

$m = k + 1$ , consider all paths from u to t in G. Look at all 1-hop neighbors of t, and also all 2-hop neighbors of t on those paths. The 2-hop neighbors need to be covered by some 1-hop neighbors of t (i.e., selected to be active). So, there is a selected 1-hop neighbor of t, say $t^{'}$ that is (at most) k steps away from (the selected) u. So, both u and $t'$ are in $G_{OTC}$ and they are ≤ k steps away. By induction hypothesis $t'$ is connected to u in $G_{OTC}$ .

For a General weighted graph G, if the path cost between two nodes u and v is the sum of weights of edges in the path, the spanner property does not hold. OTC algorithm does not look at the edge weights. So, it is always possible to find input graph G, which result in nonspanner output graph $G_{OTC}$ , as illustrated in Figure 5. However, we can modify the algorithm for weighted graphs in order to ensure the spanner property. The modification is given below:

Figure 5

OTC will select merely nodes u and t in its resulting graph $G_{OTC}$ , it does not include the edge $(u, w)$ in $G_{OTC}$ , but exploits that a better path from u to v exists via node w.

Theorem 3 (spanner).

If $u, v \in G_{M_OTC}$ and minimum cost path in G that connects u and v is c, then there is a path in $G_{M_OTC}$ that connects u and v with $cost \leq 2 * c$ . Moreover, if $s \notin G_{M_OTC}$ (not active/selected) then s has an active neighbor t such that the path $s \to t \to v$ , where $t \to v$ is a path in $G_{OTC}$ and the communication path cost is $\leq 2 * cost$ of minimum path connecting s and v in G.

Proof.

Let $u, v \in G$ . We prove the theorem by induction on n, the length of the minimum path in G connecting u and v. Base case: (i)

$n = 1$ and $u, v \in G_{M_OTC}$ , this implies u and v are neighbors. If $v \notin G_{M_OTC}$ , then still direct communication.

(ii)

$n = 2$ , $u, v \in G_{OTC}$ , then by definition of the algorithm we will return a path from $u \to v$ that is within a factor 2 of shortest path in G. If $v \notin G_{M_OTC}$ , still it is a two-hop neighbor of u. So, it will be covered within factor 2.

Assume that property holds for n ≤ k. We prove that it also holds for n = k + 1.

$n = k + 1$ , for $u, v \in G_{OTC}$ , look at one-hop neighbor of v on shortest path to u in G, call that node s. If s is selected then s is $\leq k$ hops away from u. So, by induction hypothesis s and u are connected in $G_{OTC}$ by a path of cost within factor 2 of minimum path, and s is a neighbor of v. If s is not selected, same argument holds by induction hypothesis.

The nodes of a Euclidean graph are assumed to be located in a Euclidean plane. Furthermore, the edge weight of an edge (u,v) is defined to be $w_{u v} = | u v |$ , where $| u v |$ is the Euclidean distance between the nodes u and v. Note that the definition of Euclidean graphs does not contain a statement on the existence of certain edges.

Theorem 4 (spanner).

There is spanner property on Euclidean graphs: If s and t are in $G_{OTC}$ , and they are ≤k hops away in G, then they are ≤k hops away in the resulting graph $G_{OTC}$ .

Proof.

By induction on K.

$K = 1$ , t and s are neighbors. Therefore they can communicate directly ⇒ one-hop away from each other.

$K = 2$ , by the definition of the algorithm, since t is a two-hop neighbor of s there will always be a one-hop neighbor that covers t, and is selected. Therefore, t is a two-hop away in $G_{OTC}$ .

$K \leq m$ , assume property is true for all $K \leq m$ .

$K = m + 1$ , let the shortest distance from s to t is m (see Figure 6). Consider all length ( $m + 1$ ) paths connecting s and t in G. Look at the one-hop and two-hop neighbors of t on those paths. There are two-hop neighbors of the selected node t. Therefore, there must be selected one-hop neighbors of t that cover all of them. So, there is a selected one-hop neighbor, $t^{'}$ of t on a path of length $m + 1$ to s. $t^{'}$ is selected and at distance at most m from s in G. By the inductive hypothesis, there is a path of length at most m, connecting $t^{'}$ and s in $G_{OTC}$ . Therefore, s and t have a path in $G_{OTC}$ of length $\leq m + 1$ .

Figure 6

OTC is a good spanner.

5. Time Complexity of OTC Algorithm

We consider three communication primitives for the understanding of this section: broadcast, send, and receive, defined as follows: Broadcast $(u, m)$ is invoked by node u to send message m; it results in all nodes in the neighborhood receives m. Receive $(u, m, v)$ is used by u to receive message m from v.

To find the time complexity of the algorithm, we discuss step (2) of the algorithm in detail: In steps (2a) and (2b), u broadcasts one message m, and receives ≤d messages (i.e., d is the maximum node degree and n is the number of nodes in the network) from one-hop neighbors. For all vertices, we have $O (n + n d)$ messages are sent/received, and the upper bound for dense graphs is $O (n^{2})$ . In step ( $2 c$ ), same number of messages as for steps (2a) and (2b). So, $n + n d = n (1 + d)$ messages sent/received in this step. Where the computation cost for this step is $O (n d)$ to update set $N (u)$ in step (2b) and the same for step ( $2 c$ ), and the upper bound is $O (n^{2})$ . For the complete OTC algorithm, number of sent and received messages is $O (n^{2})$ and the computation cost is $O (n^{3})$ .

6. Simulation Environment and System Parameters

For the evaluation, we have used the TinyOS/TOSSIM simulation platform. Our goal of implementing topology control algorithm is minimizing the total energy spent in the network to communicate the information gathered by sensor nodes to the information-processing center, which is the sink. The scenario that we have used in our experiments consists of a $300 m \times 300 m$ square area. In each run, we placed the sink in the left-corner of the simulated region. The control and data messages are fixed at 64 byte, and sensory data is generated at 10 second interval. Each active node retains its active-status for 300 seconds. To evaluate OTC in different topologies, we simulated up to 100 nodes deployed in a square terrain. We divided the area into 9 virtual grids. In each grid, we randomly uniformly deployed almost the same number of nodes, to ensure that nodes are distributed uniformly at random. To enforce the packets to go through multihops on route to the sink, we use different radio ranges varied from 60 to 200 m. Another reason to control the node's radio range is due to the limited message size in TOSSIM. The “raw” message data structure in TOSSIM contains fields for the destination address, message type (the AM handler ID), length, payload and so forth. The maximum payload size is set to 29 bytes by default, while it can be increased to 57 bytes. We cannot add more than 57 bytes (maximum payload size) into the message. Therefore, at higher node densities (a higher number of nodes within the radio range); a message may not contain all neighborhood information. Unless otherwise stated, all the following investigations adopt these values as their system parameters as summarized in Table 2. For all simulation results in this paper, each experiment is repeated 5 times.

Table 2

Details of the simulation.

Parameters	Values
Simulator	TOSSIM
Data generation rate	10 seconds
MAC-PROTOCOL	B-MAC
Bandwidth	19.2 kb/s
Message size	64 bytes
Terrain, $M \times M$	300 m × 300 m
Simulation Time	10,000 seconds
Node radio range	60

7. Simulation Results and Discussions

In this section, we present our main findings. We discuss results from an extensive simulation comparing OTC against two well known proposals, namely Span and GAF. Span is a distributed algorithm for power saving in wireless sensor networks. In Span, each node makes periodic, local decisions on whether to sleep, or join a forwarding backbone as a coordinator based on an estimate of how many of its neighbors will benefit from it being active and the amount of energy remaining on it. The following coordinator eligibility rule in Span ensures enough coordinators are elected so that every node is in the radio range of at least one coordinator. A noncoordinator node should become a coordinator if it discovers that two of its neighbors cannot communicate with each other either directly or via one or two coordinators. Announcement contention occurs when multiple nodes discover the lack of a coordinator at the same time. Span resolves any contention by delaying a coordinator announcement with a randomized backoff delay.

GAF is an energy-aware location-based topology control algorithm designed for sensor networks. GAF conserves energy by turning off redundant nodes in the network without affecting the level of routing fidelity. It divides the whole area into small “virtual grids”. A virtual grid is defined such that, for two adjacent grids A and B, all nodes in A can communicate with all nodes in B and vice versa. Thus all nodes in each grid are equivalent in the sense of packets forwarding. Each node uses its GPS-indicated location to associate itself with a point in the virtual grid. Such equivalence is exploited in maintaining a representative node in active mode for each virtual grid in order to keep the network connected, while the rest of nodes in the grid go to sleep. Thus, GAF can significantly increase the network lifetime as the number of nodes increases. We chose Span and GAF to be used for benchmarking purposes against our proposed algorithm OTC. Span, GAF and OTC follow the same design principles [44], to conserve energy and increase system lifetime by turning off redundant nodes without affecting the connectivity of the network. Therefore, we are able to make direct comparison in terms of various performance metrics discussed later in this paper.

The three algorithms are simulated using the same set-up as described in the above section, varying node density, round timer, and simulation time. By mean of simulations, we are interested in the following issues: (1)

How many nodes are selected as active nodes? How does the topology change over time? How many nodes are selected by GAF and Span?

(2)

How is the energy dissipated over time? How much can the network's operational lifetime be extended? How is the distribution of residual energy of nodes?

(3)

How is the network lifetime affected by the round timer?

To get first answers to these questions, we focus our simulations on the node's selection process, mainly responsible for energy consumption.

7.1. Network Topology Characteristics

Before comparing OTC to Span and GAF through detailed network simulations, we first examine the topology graphs that result from using each of these approaches. Figure 7 illustrates how OTC improves network topology using the results from one of the random networks. In the following figures, a filled square represents an active node, and a filled circle represents a regular node. Solid lines connect active nodes that are within radio range of each other. Figure 7(a) shows a topology graph when there is no topology control algorithm is employed. Figures 7(b) and 7(c) show the corresponding graphs produced by Span and GAF, respectively. We can see that both Span and GAF allow nodes in the dense areas to automatically transit to sleep state, but yet there are many more nodes selected than necessary. This result in high network interference. Figure 7(d) shows the graph produced by OTC before the time tuning operation (see Algorithm 1 step (7)). Figures 7(e), 7(f), 7(g) and 7(h) are obtained after time tuning step; they depict the topology graphs formation at different rounds. Such formation results in significant energy conservation by reducing network interference. We can see that the time tuning step is very effective in further reducing the number of selected nodes in the network. Compared to Span and GAF, OTC select fewer active nodes leading to more nodes that sleep and save energy. In OTC, most of the active nodes change their state to balance energy consumptions among all nodes after round timeouts. Each time the topology changes, it takes some time until the topology becomes stable. This time depends on the announcement time, the time nodes stay passive (in listen state), and on how fast nodes verify their state after neighborhood changes.

Figure 7

A scenario with 100 nodes placed randomly and uniformly on a square filed of 300 m side length, and a radio range of 60 m. The network graphs of (a) no Topology Control; (b) Span; (c) GAF; (d) OTC before time tuning operation (see Algorithm 1 step (7) and topology formed by OTC at round: (e) 1 (f) 2 (g) 10 and (h) 20.

7.2. Load Distribution

In order to observe how well OTC promotes load balancing among the nodes, we ran a simulation on periodic data collection at 10 seconds interval for 2000 seconds. At the outset, each node had 2 J battery energy. Figures 8(a) and 8(b) show relative residual energy across nodes of OTC at the end of simulation as compared to the performance with Span and GAF (shown as horizontal solid line), respectively. Each bar represents the difference of residual energy of OTC and Span or GAF divided by the residual energy in OTC. The plots are separated to avoid clutter. It is obvious that OTC achieves the best performance by maintaining a higher value of residual energy. Span did not as well mainly due to its tentative coordinators (active nodes) that do not ultimately become active. This causes the affected nodes to become uncovered, which in turn forces them to send their messages directly, possibly multihop, to the sink. As expected, GAF also did not perform as well. Since GAF keeps one node active in each grid.

Figure 8

Relative residual energy distribution of nodes after 2000 seconds simulation of OTC compared to Span and GAF. The nodes are initially equipped with 2 J battery energy.

7.3. Network Lifetime

This metric represents the time period from the instant network is deployed to the moment when the first node runs out of energy. In Figure 9, the improvement gained through OTC is further exemplified by the network lifetime graph. The three algorithms are compared against a special case where a network does not use topology control and all nodes are active. This special case used to highlight the benefits of topology control. In the plots of results given below, the special case plot is represented by “Active-case”. For this investigation, we set initial battery energy at only 0.1 J to let the nodes to die sooner. This however does not change the pattern of behavior of these algorithms. It is evident that OTC exhibits the longest lifetime with all nodes remaining fully functional. It is found that OTC achieves more than twice the lifetime of Span and GAF. It also achieves as much as five times the lifetime of the active-case.

Figure 9

Network lifetime against simulation time of OTC, Span and GAF.

It is obvious that OTC promotes good load balancing across the entire network to sustain the network for its longest possible use. Figure 9 also indicates the utility of a topology control algorithm against the active-case. All the topology control algorithms are able to sustain network lifetime at least twice the lifetime of the active-case.

7.4. Investigating Different Round Timer Values

In the last set of simulations, we investigate the impact of different round timer values (i.e., at which sleeping nodes will wake up to exchange their roles with active nodes) on energy balancing and network lifetime. Figure 10 depicts the total consumed energy by all nodes in the network versus round timer. As can be seen from the graph, the total consumed energy for all algorithms increases if nodes wake up more frequently. Although both Span and GAF rotate the role of being active among all nodes by selecting nodes with most remaining energy, GAF performs worse than OTC since it is bounded by grids. Thus, GAF balances energy consumptions among nodes in the same grid only. Even if just one node is left, the node must be active. In contrast, OTC takes all nodes into account leading to a better energy balancing. A significant amount of energy was consumed by passive active nodes in Span. Thus, reducing the wake up cycle leads to more energy savings since nodes rarely wake up and do not become passive very often. For all round timer values, we observed that OTC provides a significant amount of savings beyond Span, because OTC keeps lesser number of nodes active at any point in time. In OTC, each node is allowed to exchange messages with its neighbors only twice, and then must decide which links to keep. While in Span nodes communicate with each other continuously, they use local HELLO messages to propagate topology information, but it does not depend on them for correctness: when HELLO messages are lost (e.g., due to interference), Span elects more active nodes.

Figure 10

Total consumed energy by all nodes in the network versus round timeout factor.

7.5. Spanner Property

In order to study the spanner property of $G_{OTC}$ on randomly generated networks, we calculated the stretch factor of every pair u,v in the graph:

S F (u, v) : = \frac{| p_{OTC} (u, v) |}{| p_{} (u, v) |} .

(1)

This is the ratio between cost of the shortest path between u and v on

G_{OTC}

and the shortest path on the unit disk graph G. For each considered network density we generated five networks, and for each pair of nodes u,v we calculate SF(u, v). Edge and corresponding path costs were considered with respect to Euclidean edge length

| u v |

. Figure 11 depicts our results over the considered network size. The results show that

G_{OTC}

has a good spanner property on average graphs; the corresponding mean value of the stretch factor does not exceed 1.3, whereas even the maximum value stays below 2.8. In summary, the results show that

G_{OTC}

is a good average-case spanner with respect to the Euclidean metric. Figure 12 shows the distribution of the stretch factors of all nodes when the number of nodes in the network is 70. It is obvious that most of the values are close to the mean (i.e., 1.25 from Figure 11).

Figure 11

Stretch factors of $G_{OTC}$ with respect to Euclidean metric (solid), stretch factor of the optimal graph with respect to Euclidean metric (dashed) over number of nodes in the network. Maximum values are plotted in dotted line.

Figure 12

Number of nodes pairs in $G_{OTC}$ versus the stretch factor for a network with 70 nodes. It is obvious that most of the values are close to the mean (1.25 from Figure 11).

7.6. Bounded Degree Property

$G_{OTC}$ could not be shown to have a bounded degree. We study here its average-case behavior with respect to node degree. The results therefore were obtained similarly as for the spanner property. Figure 13 shows the computed results. Mean and maximum degree values for the unit disk graph rise in accordance with network size. The mean degree curves for $G_{OTC}$ graph increase slowly for very small networks. The low values of $G_{OTC}$ suggest its suitability to reduce interference in sensor networks.

Figure 13

Node degree of $G_{OTC}$ (solid) and unit disk graph G (dotted).

8. Conclusion

In this paper, we have presented a new topology control algorithm that adaptively elects a subset of nodes to be active from the network pool of nodes, and periodically rotates their roles. While active nodes forms the routing backbone and forward data packets toward the sink, redundant nodes transit to power saving mode by turning their radios off. OTC works in a distributed and localized fashion and is able to achieve and prove several properties on both Euclidean and general weighted graphs; apart from being symmetric and connected, the resulting graph also shows good spanner properties. On the average-case unit disk graphs, the resulting topology features the bounded degree property.

In order to evaluate OTC, it is benchmarked against a two well-known and comparable algorithms, namely, Span and GAF. To ensure realistic evaluations, the TOSSIM simulation environment is adopted. Concerning network lifetime, load distribution, and spanner and bounded degree properties, OTC outperforms Span and GAF.

References

Estrin

Govindan

Heidemann

Kumar

Next century challenges: scalable coordination in sensor networks

Proceedings of IEEE/ACM International Conference on Mobile Computing and Networking

1999

Seattle, Wash, USA

263 270

Pottie

G. J.

Kaiser

W. J.

Wireless integrated network sensors

Communications of the ACM 2000 43 5 51 58

2-s2.0-0345851235

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 105

2-s2.0-0032667848

10.1109/MCOM.2002.1024422

Bharathidasan

Ponduru

V. A. S.

Sensor networks: an overview

2002

Department of Computer Science, University of California at Davis

http://wwwcsif.cs.ucdavis.edu/~bharathi/sensor/snw.html

Mainwaring

Culler

Polastre

Szewczyk

Anderson

Wireless sensor networks for habitat monitoring

Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications

September 2002

Atlanta, Ga, USA

88 97

2-s2.0-0036986465

10.1145/570738.570751

Szewczyk

Lessons from a sensor network expedition

Proceedings of the 1st European Workshop on Wireless Sensor Networks

January 2004

Berlin, Germany

307 322

University of California at Berkeley

Mote Documentation and Development Information

http://www.cs.berkeley.edu/~awoo/smartdust

Polaroid

Technical specifications for 6500 series sonar ranging module

http://clubweb.interbaun.com/labtop/manualweb/Polaroid

Wattenhofer

Zollinger

XTC: a practical topology control algorithm for ad-hoc networks

Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS ′04)

April 2004

2969 2976

2-s2.0-12444306370

10.

X.-Y.

Calinescu

Wan

P.-J.

Distributed construction of planner spanner and routing for ad hoc wireless networks

Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′02)

June 2002

New York, NY, USA

11.

Wattenhofer

Ad-hoc and sensor networks: worst-case vs. average-case

Proceedings of the International Zurich Seminar on Communications

February 2004

156 159

2-s2.0-2442560532

12.

Kuhn

Wattenhofer

Zhang

Zollinger

Geometric ad-hoc routing: of theory and practice

Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC ′03)

July 2003

63 72

2-s2.0-1142305204

13.

Kuhn

Wattenhofer

Zollinger

Worst-case optimal and average-case efficient geometric ad-hoc routing

Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ′03)

June 2003

267 278

2-s2.0-0242696173

14.

Bose

Morin

Stojmenovic

Urrutia

Routing with guaranteed delivery in ad hoc wireless networks

Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M ′99)

1999

Seattle, Wash, USA

48 55

15.

Karp

Kung

H. T.

GPSR: greedy perimeter stateless routing for wireless networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

New York, NY, USA

243 254

2-s2.0-0034547115

16.

Buettner

Yee

G. V.

Anderson

Han

X-MAC: a short preamble MAC protocol for duty-cycled wireless sensor networks

Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys ′06)

November 2006

Boulder, Colo, USA

307 320

2-s2.0-34547480316

10.1145/1182807.1182838

17.

Heidemann

Estrin

Geography-informed energy conservation for ad hoc routing

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking

July 2001

70 84

2-s2.0-0034772133

18.

Moraru

Leone

Nikoletseas

Rolim

Geographic routing with early obstacles detection and avoidance in dense wireless sensor networks

5198

Proceedings of the 7th International Conference on Ad-hoc, Mobile and Wireless Networks (ADHOC-NOW ′08)

September 2008

Sophia-Antipolis, France

148 161 Lecture Notes in Computer Science

2-s2.0-0013163991

10.1007/978-3-540-85209-4_12

19.

Fang

Gao

Guibas

L. J.

Locating and bypassing holes in sensor networks

Mobile Networks and Applications 2006 11 2 187 200

2-s2.0-33646734122

10.1007/s11036-006-4471-y

20.

Moraru

Leone

Rolim

J. D. P.

Nikoletseas

Near optimal geographic routing with obstacle avoidance in wireless sensor networks by fast-converging trust-based algorithms

Proceedings of the 3rd ACM Workshop on Q2S and Security for Wireless and Mobile Networks (Q2SWinet ′07)

October 2007

31 38

2-s2.0-42149160056

10.1145/1298239.1298246

21.

Levis

Lee

TOSSIM: a simulator for tinyos networks

2003

University of California, Berkeley

22.

Levis

Lee

Welsh

Culler

TOSSIM: accurate and scalable simulation of entire TinyOS applications

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

Los Angeles, Calif, USA

126 137

2-s2.0-18844399081

23.

TinyOS

May 2007, http://www.tinyos.net/

24.

Chen

Jamieson

Balakrishnan

Morris

Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom ′01)

July 2001

85 96

2-s2.0-0034781549

25.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

26.

Selvakennedy

Sinnappan

A configurable time-controlled clustering algorithm for wireless sensor networks

Proceedings of the 11th International Conference on Parallel and Distributed Systems Workshops (ICPADS ′05)

July 2005

368 372

2-s2.0-23944510839

27.

Bandyopadhyay

Coyle

E. J.

An energy efficient hierarchical clustering algorithm for wireless sensor networks

Proceedings of the 22nd IEEE Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′03)

March-April 2003

San Francisco, Calif, USA

1713 1723

28.

Handy

M. J.

Haase

Timmermann

Low energy adaptive clustering hierarchy with deterministic cluster-head selection

Proceedings of the 4th International Workshop on Mobile and Wireless Communications Networks

2002

368 372

10.1109/MWCN.2002.1045790

29.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

30.

Ramanathan

Rosales-Hain

Topology control of multihop wireless networks using transmit power adjustment

Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′00)

March 2000

Tel Aviv, Israel

404 414

31.

Tseng

Y.-C.

Chang

Y.-N.

Tzeng

B.-H.

Energy-efficient topology control for wireless ad hoc sensor networks

Journal of Information Science and Engineering 2004 20 1 27 37

2-s2.0-0842312254

32.

Wattenhofer

Bahl

Wang

Y. M.

Distributed topology control for power efficient operation in multihop wireless ad hoc networks

Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM ′01)

April 2001

Anchorage, Alaska, USA

1028 1037

10.1109/INFCOM.2001.916296

33.

Halpern

J. Y.

Bahl

Wang

Y.-M.

Wattenhofer

Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks

Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing (PODC ′01)

August 2001

264 273

2-s2.0-0034772467

34.

Efthymiou

Nikoletseas

Rolim

Energy balanced data propagation in wireless sensor networks

Proceedings of the 4th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks

2004

35.

Jarry

Leone

Powell

Rolim

An optimal data propagation algorithm for maximizing the lifespan of sensor networks

Proceedings of the 2nd IEEE International Conferenceon Distributed Computing in Sensor Systems (DCOSS ′06)

June 2006

San Francisco, Calif, USA

405 421

10.1007/11776178_25

36.

Schurgers

Srivastava

M. B.

Energy efficient routing in wireless sensor networks

Proceedings of Military Communications Conference (MILCOM ′01)

October 2001

McLean, Va, USA

357 361

2-s2.0-0035728129

37.

Alzoubi

Wan

P.-J.

Frieder

Message-optimal connected-dominating-set construction for routing in mobile ad hoc networks

Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc ′02)

June 2002

Lausanne, Switzerland

157 164

38.

Wang

X.-Y.

Geometric spanners for wireless ad hoc networks

Proceedings of the 22nd International Conference on Distributed Systems (ICDCS ′02)

July 2002

171 178

2-s2.0-0036373267

39.

Halpern

J. Y.

Bahl

Wang

Y.-M.

Wattenhofer

A cone-based distributed topology-control algorithm for wireless multi-hop networks

IEEE/ACM Transactions on Networking 2005 13 1 147 159

2-s2.0-15544363212

10.1109/TNET.2004.842229

40.

Zhao

Govindan

Understanding packet delivery performance in dense wireless sensor

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

Los Angeles, Calif, USA

1 13

2-s2.0-18844411823

41.

Zhou

Krishnamurthy

Stankovic

J. A.

Impact of radio irregularity on wireless sensor networks

Proceedings of the 2nd International Conference on Mobile Systems, Applications and Services (MobiSys ′04)

June 2004

Boston, Mass, USA

125 138

2-s2.0-0001859562

42.

Zhou

Krishnamurthy

Stankovic

J. A.

Models and solutions for radio irregularity in wireless sensor networks

ACM Transactions on Sensor Networks 2006 2 2 221 262

2-s2.0-33746895103

10.1145/1149283.1149287

43.

Santi

Topology Control in Wireless Ad Hoc and Sensor Networks 2004

New York, NY, USA

John Wiley & Sons

44.

Ababneh

Selvakennedy

Topology control for wireless sensor networks: an overview

International Journal of Wireless and Optical Communications 2006 3 1 49 68