Volume 5 Issue 10 - October 3, 2008
Fault-Tolerant Topology with Variable-Range Transmission Power Control in Wireless Sensor Networks
Kuo-Feng Ssu*, Chiu-Wen Chen, Chun-Hao Yang

Department of Electrical Engineering, College of Electrical Engineering and Computer Science, National Cheng Kung University
*Email: ssu@ee.ncku.edu.tw

IEEE TMC, vol. 6, no. 10, pp. 1199, Oct. 2007.
IEEE PRDC, pp. 131-138, Dec. 2007.

Font Normal   Font Enlarge
In recent years, sensor networks have been pervasive in a wide range of applications such as location tracking, earthquake report, habitats monitoring, forest surveillance, and healthcare [1]. A wireless sensor network is composed of a sink node and a large number of tiny sensor nodes that can perform computation and wireless communication. In multi-hop wireless sensor networks, sink node would flood the querying data to all sensor nodes or collect the replying information from sensor nodes. The capacity of its battery is very limited so energy consumption becomes an important issue that directly affects the network lifetime.

Topology control algorithms were proposed to maintain network connectivity with lower energy consumption. To support the multi-hop communication, a connected dominating set (CDS) is selected for establishing a virtual backbone [2–4]. The CDS includes a subset of sensor nodes that enable communication in the network.

Sensor nodes may fail during operation. A failed node in the backbone would break the connection of the network. Recent study suggested that the backbone should maintain a certain degree of redundancy for fault tolerance [5,6]. Multiple disjoint paths are thus needed for connecting every pair of nodes. The design requires more nodes in the backbone so the power efficiency is affected.

A topology control protocol with both power saving and fault tolerance, named P-CDS (Power-CDS), is developed. P-CDS classifies the backbone nodes in two types, primary coordinator and backup coordinator. For failure free execution, the coordinators are responsible for data transmission while the backup coordinators remain in sleeping mode. After failed transmission is detected, some backup coordinators will be activated. The topology can be recovered by adjusting the transmission ranges of the coordinators and backup coordinators. Compared to the previous approaches, P-CDS reduces the number of active coordinators and also saves energy. In addition, the network topology built by P-CDS can survive consecutive failures with appropriate settings.
Figure 1: An example for P-CDS: (a) failure-free execution. (b) node 2 fails.

Two techniques are integrated in our mechanism, including scheduling the state of the coordinator and adjusting the transmission range of sensor nodes. For example, the ideal topology is shown as Figure 1(a). Based on our mechanism, node 1, 2, 3, and 4 are primary-coordinators; node b1, b2, and b3 are backup-coordinators and they switch to the sleep state after being selected. When node 2 fails, node b1 and b2 can be awakened for helping transmission (see Figure 1(b)). Node b1 uses the full transmission range and node b2 uses the half. In addition, node 1 can enter sleep mode. In this way, redundant active sensor nodes are not necessary during failure-free execution. When failure occurs, the network can be configured automatically and remain connected.

In experiments, P-CDS was compared with Span protocol [2] and k-Gossip protocol [5]. The simulations were implemented with the network simulator 2 (ns-2) [7]. To generate a network, n nodes were randomly placed in a 100m × 100m field to form a connected graph. The number of n in the region was varied from 100 to 500. The sensor nodes initial energy was set to 50J. The maximum communication range Rmax was set to 24m. Any two nodes with distance less than Rmax were considered neighbors. The traffic model utilized the Constant Bit Rate (CBR) and the source originated three packets per second. In 2-Gossip, pk = 0.48 was set for a high success ratio. To guarantee to construct a fault-tolerant CDS, P-CDS were evaluated with p = 1 and 2. In the experiments, the energy model followed the specifications of the TR 1000 radio transceiver from RF Monolithics [8,9].

The size of selected coordinators is shown in Figure 2. The size of P-CDS is about 57% smaller than k-Gossip; Span is about 12% better than P-CDS in sparse networks (n ≤ 200). In dense networks (such as 500 nodes in the region), the size of P-CDS is about 16.6% compared to k-Gossip. k-Gossip typically produces the larger size of CDS that spends more energy. Span and P-CDS have relatively small back-bone sizes, which increases slightly as n increases. Though Span produces the smaller average size than P-CDS, Span could not survive from sensor failures.
Figure 3: Comparison for broadcast cost.
Figure 2: Size of CDS.


Figure 3 illustrates the broadcast cost of the three protocols in terms of the transmission energy. The simulation result is quite similar to the case of CDS size. k-Gossip is still significantly higher than the other approaches because of the relatively larger size of CDS. When the number of nodes is 100, P-CDS saves about 10% of energy than k-Gossip. Moreover, P-CDS saves about 28% energy when there are 500 nodes in the region.

Based on the study and simulation results, changing transmission power on sensor nodes not only save energy consumption dramatically but improves fault tolerance with appropriate arrangements. The approach improves both network lifetime and reliability successfully.

References
  • I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A Survey on Sensor Networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, Aug. 2002.
  • B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks,” Proceedings of the ACM International Conference on Mobile Computing and Networking (MobiCom), pp. 85–96, July 2001.
  • R. Ramanathan and R. Hain, “Topology Control of Multi-hop Radio Networks Using Transmit Power Adjustment,” Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pp. 404–413, Mar. 2000.
  • T.-C. Hou and V. Li, “Transmission Range Control in Multihop Packet Radio Networks,” IEEE Transactions on Communications, vol. 34, no. 1, pp. 38–44, Jan. 1986.
  • X. Hou and D. Tipper, “Gossip-Based Sleep Protocol (GSP) for Energy Efficient Routing in Wireless Ad Hoc Networks,” Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC), pp. 21–25, Mar. 2004.
  • N. Li and J.C. Hou, “FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks,” Proceedings of the ACM International Conference on Mobile Computing and Networking (MobiCom), pp. 275–286, Sept. 2004.
  • The Network Simulator - NS-2, 2006. http://www.isi.edu/nsnam/ns/ .
  • ASH Transceiver Designer’s Guide, 2007. http://www.rfm.com/ .
  • L.M. Feeney, “An Energy Consumption Model for Performance Analysis of Routing Protocols for Mobile Ad Hoc Networks,” Mobile Networks and Applications, vol. 6, no. 3, pp. 239–249, June 2001.
< previous
Copyright National Cheng Kung University