在無線感測網路（Wireless Sensor Networks）中，當通訊的兩個節點位於通訊範圍外時，往往會使用泛流（Flooding）的機制來傳送封包，但由於網路節點的個數很多，因此造成頻寬的浪費，進而耗費節點的電量。所以，控制網路拓樸的演算法常被利用來大量減少泛流的封包數量。
透過建立連通的網路骨幹，節點便會利用骨幹來傳遞封包。然而，當骨幹中任一節點電量耗盡或是故障時，便會導致整個網路無法連通。先前之部分研究便挑選多餘的節點以達成容錯的網路拓樸。本篇論文提出一控制網路拓樸的演算法，利用節點可調整傳輸距離以達成容錯的網路拓樸，並且在節省電量的考量下，選出的備份骨幹節點進入省電的模式。實驗結果顯示本篇論文所提出的方法能建
立一個較小且能容錯的網路拓樸，同時也能減少節點電量的耗費。

A topology control algorithm can be applied to wireless sensor networks to construct a virtual backbone for maintaining network connectivity. Energy consumption and fault tolerance are the most important issues for increasing system lifetime. Previous research typically preferred to have more redundant nodes for transmission error tolerance so the power efficiency was compromised. This thesis describes a fault-tolerant topology control mechanism, named "P-CDS". The mechanism schedules active and backup sensor nodes in the backbone. When node failure is detected, both active and backup nodes will adjust their transmission ranges to maintain connectivity. Simulation results show that P-CDS forms a smaller connected dominating set than the other fault-tolerant topology control algorithm. P-CDS also provides efficient broadcast with relatively low energy consumption.

[1] 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.
[2] G. J. Pottie and W. J. Kaiser, "Wireless Integrated Network Sensors," Communications of the ACM, vol. 43, no. 5, pp. 51-58, May 2000.
[3] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson, "Wireless
Sensor Networks for Habitat Monitoring," Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, pp. 88-97, Sept. 2002.
[4] N. Bambos, "Toward Power-Sensitive Network Architectures in Wireless Communications: Concepts, Issues, and Design Aspects," IEEE Personal Communications, vol. 5, no. 3, pp. 50-59, June 1998.
[5] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-Efficient Communication Protocol for Wireless Microsensor Networks," Proceedings of the Hawaii International Conference on System Sciences (HICSS), pp. 908-918, Jan. 2000.
[6] C. Rohl, H. Woesner, and A. Wolisz, "A Short Look on Power Saving Mechanisms in the Wireless LAN Standard Draft IEEE 802.11," Proceedings of the WINLAB Workshop on Third Generation Wireless Information Network, pp. 183-188, Mar. 1997.
[7] Xbow mica series node, 2007. http://www.xbow.com.
[8] T. He, S. Krishnamurthy, J. A. Stankovic, T. Abdelzaher, L. Luo, R. Stoleru, T. Yan, L. Gu, J. Hui, and B. Krogh, "An Energy-Efficient Surveillance System for Sensor Setworks," Proceedings of the International Conference on Mobile Systems, Applications, and Services (MobiSys), pp. 6-9, June 2004.
[9] A. Savvides, C. Han, and M. B. Strivastava, "Dynamic Fine-Grained Localization in Ad-hoc Networks of Sensors," Proceedings of the International Conference on Mobile Computing and Networking (MobiCom), pp. 166-179, July 2001.
[10] 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.
[11] K. Alzoubi, P.-J. Wan, and O. Frieder, "New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks," Proceedings of the Hawaii International Conference on System Sciences (HICSS), pp. 297-303, Jan. 2002.
[12] J.Wu and H. Li, "On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks," Proceedings of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7-14, Aug. 1999.
[13] M. Bahramgiri, M. Hajiaghayi, and V. Mirrokni, "Fault-Tolerant and 3-dimensional Distributed Topology Control Algorithms in Wireless Multi-hop Networks," Proceedings of the IEEE International Conference on Computer Communications and Networks (ICCCN), pp. 392-398, Oct. 2002.
[14] P. Basu and J. Redi, "Movement Control Algorithms for Realization of Fault Tolerant Ad Hoc Robot Networks," IEEE Network, vol. 18, no. 4, pp. 36-44, 2004.
[15] M. Jorgic, I. Stojmenovic, M. Hauspie, and D. Simplot-Ryl, "Localized Algorithms for Detection of Critical Nodes and Links for Connectivity in Ad Hoc Networks," Proceedings of the Mediterranean Ad Hoc Networking Workshop, pp. 360-371, June 2004.
[16] 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.
[17] X.-Y. Li, P.-J.Wan, Y.Wang, and C.-W. Yi, "Fault Tolerant Deployment and Topology Control in Wireless Networks," Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 117-128, June 2003.
[18] G. Lu, B. Krishnamachari, and C. Raghavendra, "Performance Evaluation of the IEEE 802.15.4 MAC for Low-Rate Low-Power Wireless Networks," Proceedings of the Workshop on Energy-Efficient Wireless Communications and Networks (EWCN),
pp. 701-706, Apr. 2004.
[19] J. Zheng and M. J. Lee, "Will IEEE 802.15.4 Make Ubiquitous Networking a Reality?: A Discussion on a Potential Low Power, Low Bit Rate Standard," IEEE Communications Magazine, vol. 42, no. 6, pp. 140-146, June 2004.
[20] I. S. Department, IEEE Standard for Information Technology – Telecommunications and Information Exchange Between Systems - Local and Metropolitan Area Networks Specifications Requirement Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs). IEEE, Oct. 2003.
[21] Y.-C. Tseng, S.-Y. Ni, Y.-S. Chen, and J.-P. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," The Special Issue of ACM Wireless Networks, vol. 8, no. 2, pp. 153-167, Mar. 2002.
[22] R. Ramanathan and R. Hain, "Topology Control of Multihop Radio Networks Using Transmit Power Adjustment," Proceedings of the IEEE Conference on Computer Communications (INFOCOM), pp. 404-413, Mar. 2000.
[23] 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.
[24] Y. Xu, J. Heidemann, and D. Estrin, "Geography-Informed Energy Conservation for Ad Hoc Routing," Proceedings of the ACM International Conference on Mobile Computing and Networking (MobiCom), pp. 70-84, July 2001.
[25] C. Schurgers, V. Tsiatsis, and M. Srivastava, "STEM: Topology Management for
Energy E±cient Sensor Networks," Proceedings of the IEEE Aerospace Conference, pp. 10-15, Mar. 2002.
[26] X.-Y. Li, W.-Z. Song, and Y. Wang, "Localized Topology Control for Heterogeneous Wireless Sensor Networks," ACM Transactions on Sensor Networks (TOSN), vol. 2, no. 1, pp. 129-153, Feb. 2006.
[27] R. Diestel, Graph Theory. Springer-Verlag, 2005.
[28] L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer, "A Cone-Based Distributed Topology-Control Algorithm for Wireless Multi-Hop Networks," IEEE/ACM Transactions on Networking (TON), vol. 13, no. 1, pp. 147-159, Feb. 2005.
[29] M. Hajiaghayi, N. Immorlica, and V. Mirrokni, "Power Optimization in Fault-Tolerant Topology Control Algorithms for Wireless Multi-hop Networks," Proceedings of the International Conference on Mobile Computing and Networking (MobiCom), pp. 300-312, Sept. 2003.
[30] 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.
[31] D. Blough, M. Leoncini, G. Resta, and P. Santi, "The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks," Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 141-152, June 2003.
[32] J. Liu and B. Li, "MobileGrid: Capacity-Aware Topology Control in Mobile Ad
Hoc Networks," Proceedings of the IEEE International Conference on Computer Communications and Networks (ICCCN), pp. 570-574, Oct. 2002.
[33] J. Wu and F. Dai, "A Generic Distributed Broadcast Scheme in Ad Hoc Wireless
Networks," IEEE Transactions on Computers, vol. 53, no. 10, pp. 1343-1354, Oct. 2004.
[34] M. Maroti, B. Kusy, G. Simon, and A. Ledeczi, "The Flooding Time Synchronization Protocol," Proceedings of the ACM Conference on Embedded Networked Sensor Systems (SenSys), pp. 39-49, Nov. 2004.
[35] Y. Wang, J. Gao, and J. Mitchell, "Boundary Recognition in Sensor Networks by Topological Methods," Proceedings of the Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 122-133, Sept. 2006.
[36] The Network Simulator - NS-2, 2006. http://www.isi.edu/nsnam/ns/.
[37] The NS Manual, 2007. http://www.isi.edu/nsnam/ns/doc/index.html.
[38] ASH Transceiver Designer's Guide, 2007. http://www.rfm.com.
[39] L. M. Feeney, "An Energy Consumption Model for Performance Anslysis of Routing Protocols for Mobile Ad Hoc Networks," Mobile Networks and Applications, vol. 6, no. 3, pp. 239-249, June 2001.