| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Fault-Local Self-Stabilizing Clustering Service for Wireless Ad Hoc Networks
September 2006 (vol. 17 no. 9)
pp. 912-922
Abstract—We present a fast, local clustering service, FLOC, that partitions a multihop wireless network into nonoverlapping and approximately equal-sized clusters. Each cluster has a clusterhead such that all nodes within unit distance and some nodes within distance m of the clusterhead belong to the cluster. We show that, by asserting a stretch factor m \geq 2, FLOC achieves locality of clustering and fault-local self-stabilization: The effects of cluster formation and faults/changes at any part of the network are contained within at most m+1 units. Through simulations and experiments with actual deployments, we analyze the trade-offs between clustering time and the quality of clustering and suggest suitable parameters for FLOC to achieve a fast completion time without compromising the quality of the resulting clustering.
[1] 912 A. Amis, R. Prakash, T. Vuong, and D. Huynh, “Max-Min d-Cluster Formation in Wireless Networks,” Proc. IEEE INFOCOM, pp. 32-41, Mar. 2000.[2] A. Arora, P. Dutta, S. Bapat, V. Kulathumani, H. Zhang, V. Naik, V. Mittal, H. Cao, M. Demirbas, M. Gouda, Y.-R. Choi, T. Herman, S.S. Kulkarni, U. Arumugam, M. Nesterenko, A. Vora, and M. Miyashita, “A Line in the Sand: A Wireless Sensor Network for Target Detection, Classification, and Tracking,” Computer Networks J., vol. 46, no. 5, pp. 605-634, Dec. 2004.[3] S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proc. IEEE INFOCOM, pp. 1028-1037, Apr. 2001.[4] J. Beal, “A Robust Amorphous Hierarchy from Persistent Nodes,” AI Memo 2003-011, MIT, 2003.[5] Chipcon, Cc1000 Radio Datasheet, www.chipcon.com/filesCC1000_Data_Sheet_2_2.pdf , 2004.[6] Y. Choi, M. Gouda, M.C. Kim, and A. Arora, “The Mote Connectivity Protocol,” Proc. Int'l Conf. Computer Comm. and Networks (ICCCN '03), pp. 533-538, Oct. 2003.[7] B. Dalton and M. Bov, “Audio-Based Self-Localization for Ubiquitous Sensor Networks,” Proc. Audio Eng. Soc. (AES) 118th Convention, 2005.[8] M. Demirbas, A. Arora, V. Mittal, and V. Kulathumani, “Design and Analysis of a Fast Local Clustering Service for Wireless Sensor Networks,” Proc. Broadband Wireless Networking Symp. (BroadNets), pp. 700-709, Oct. 2004.[9] W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, “Application Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Trans. Wireless Networking, vol. 1, no. 4, pp. 660-670, Oct. 2002.[10] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, “System Architecture Directions for Network Sensors,” Proc. Int'l Conf. Architectural Support for Programming Languages (ASPLOS), pp. 93-104, 2000.[11] S. Katz, “A Superimposition Control Construct for Distributed Systems,” ACM Trans. Programming Language Systems, vol. 15, no. 2, pp. 337-356, 1993.[12] V. Mittal, M. Demirbas, and A. Arora, “LOCI: Local Clustering Service for Large Scale Wireless Sensor Networks,” Technical Report OSU-CISRC-2/03-TR07, The Ohio State Univ., Feb. 2003.[13] R. Nagpal and D. Coore, “An Algorithm for Group Formation in an Amorphous Computer,” Proc. 10th Int'l Conf. Parallel and Distributed Computing Systems (PDCS), pp. 28-31, Oct. 1998.[14] D. Niculescu and B. Nath, “DV Based Positioning in Ad Hoc Networks,” J. Telecomm. Systems, vol. 22, pp. 267-280, 2003.[15] B. Parkinson and J. Spilker, “Global Positioning System: Theory and Application,” Am. Inst. of Aeronautics and Astronautics, 1996.[16] N. Priyantha, A. Chakraborty, and H. Balakrishnan, “The Cricket Location-Support System,” Proc. MOBICOM, pp. 32-43, Aug. 2000.[17] F.B. Schneider, “Byzantine Generals in Action: Implementing Fail-Stop Processors,” ACM Trans. Computer Systems, vol. 2, no. 2, 1984.[18] G. Simon, P. Volgyesi, M. Maroti, and A. Ledeczi, “Simulation-Based Optimization of Communication Protocols for Large-Scale Wireless Sensor Networks,” Proc. IEEE Aerospace Conf., Mar. 2003.[19] Crossbow Technology, Mica2, 2004, www.xbow.com/ProductsWireless_Sensor_Networks.htm .[20] A. Woo, T. Tong, and D. Culler, “Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks,” Proc. First ACM Conf. Embedded Networked Sensor Systems, pp. 14-27, 2003.[21] J. Zhao and R. Govindan, “Understanding Packet Delivery Performance in Dense Wireless Sensor Networks,” Proc. First ACM Conf. Embedded Networked Sensor Systems, pp. 1-13, 2003.
Index Terms:
Wireless sensor networks, fault tolerance, reliability, availability, and serviceability.
Citation:
Murat Demirbas, Anish Arora, Vineet Mittal, Vinodkrishnan Kulathumani, "A Fault-Local Self-Stabilizing Clustering Service for Wireless Ad Hoc Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 9, pp. 912-922, Sept. 2006, doi:10.1109/TPDS.2006.113
