| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Channel Access-Based Self-Organized Clustering in Ad Hoc Networks
April-June 2003 (vol. 2 no. 2)
pp. 102-113
Mi Lu, IEEE Computer Society
Abstract—An ad hoc network is a self-organized and distributed entity consisting of a number of mobile stations (MSs) without the coordination of any centralized access point. Clustering is one of the fundamental problems in ad hoc networks. In this context, we describe a distributed clustering algorithm for multihop ad hoc networks. We first propose a randomized control channel broadcast access method to maximize the worst-case control channel efficiency, based on which a distributed clustering algorithm is proposed. Both theoretical analysis and simulations indicate that the proposed clustering algorithm takes much less time and overhead to cluster a given network with more stable cluster structure, while incurring very small maintenance overhead in a dynamic network resulting from the mobility of the MSs.
[1] 102 D. Newman and K. Tolly, “Wireless LANs: How Far? How Fast?” Data Comm., pp. 77-87, Mar. 1995[2] A. Elwalid and D. Mitra, “Effective Bandwidth of General Markovian Traffic Sources and Admission Control on High-Speed Networks,” IEEE/ACM Trans. Networking, vol. 1, no. 3, pp. 329-343, June 1993.[3] J.-H. Ryu and D.-H. Cho, “A New Routing Scheme Concerning Energy Conservation in Wireless Home Ad-Hoc Networks,” IEEE Trans. Consumer Electronics, vol. 47, no. 1, pp. 1-5, Feb. 2001.[4] S. Singh, “Quality of Service Guarantees in Mobile Computing,” Computer Comm., vol. 19, no. 1, pp. 359-371, Apr. 1996.[5] C.R. Lin and M. Gerla, “Adaptive Clustering in Mobile Wireless Networks,” IEEE J. Selected Areas in Communications, vol. 16, pp. 1,265–1,275, 1997.[6] Z.J. Hass, M. Gerla, D.B. Johnson, C.E. Perkins, M.B. Pursley, M. Steenstrup, C.-K. Toh, and J.F. Hayes, “Guest Editorial Wireless Ad Hoc Networks,” IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1329-1332, Aug. 1999.[7] C.V. Ramamoorthy, A. Bhide, and J. Srivastava, “Reliable Clustering Techniques for Large, Mobile Packet Radio Networks,” Proc. IEEE INFOCOM '87, pp. 218-226, 1987.[8] P. Krishna, N.H. Vaidya, M. Chatterjee, and D.K. Pradhan, “A Cluster-Based Approach for Routing in Dynamic Networks,” ACM SIGCOMM Review, vol. 27, no. 2, Apr. 1997.[9] R. Ramanathan and M. Steenstrup, “Hierarchically-Organized, Multihop Wireless Networks for Quality-of-Service Support,” Mobile Networks and Applications, vol. 3, pp. 101–119, 1998.[10] S. Banerjee and S. Khuller, “A Clustering Scheme for Hierarchical Control in Multi-Hop Wireless Networks,” Proc. IEEE INFOCOM '01, pp. 1028-1037, 2001.[11] C.E. Perkins, Ad Hoc Networking. Addison-Wesley, 2001.[12] M. Jiang, J. Li, and Y.C. Tay, “Cluster Based Routing Protocol (CBRP) Functional Specification (Internet-Draft),” Internet-Draft, Aug. 1998.[13] B. Das, E. Sivakumar, and V. Bhargavan, “Routing in Ad Hoc Networks Using a Virtual Backbone,” Proc. Sixth Int'l Conf. Computer Comm. and Networks (IC3N '97), pp. 1-20, Sept. 1997.[14] M. Joa-Ng and I.-T. Lu, “A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile Ad Hoc Networks,” IEEE J. Selected Areas in Comm., vol. 17, pp. 1415–1425, 1999.[15] Z.J. Hass and M.R. Pearlman, “The Zone Routing Protocol (ZRP) for Ad Hoc Networks (Internet-Draft),” Internet-Draft, Aug. 1998.[16] M.R. Pearlman and Z.J. Haas, Determining the Optimal Configuration for the Zone Routing Protocol IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1395-1414, Aug. 1999.[17] C.C. Chiang, M. Gerla, and L. Zhang, “Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks,” ACM/Baltzer J. Cluster Computing: Special Issue on Mobile Computing, vol. 1, no. 2, pp. 187-196, Nov. 1998.[18] A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen, “Scalable Routing Strategies for Ad hoc Networks,” IEEE J. Selected Areas in Comm., vol. 17, pp. 1,369–1,379, 1999.[19] J.-H. Ryu, S. Song, and D.-H. Cho, “Clustering Scheme for Energy Conservation in Two-Tiered Mobile Ad Hoc Networks,” Electronics Letters, vol. 37, no. 11, pp. 710-711, 2001.[20] P. Krishna, M. Chatterjee, N.H. Vaidya, and D.K. Pradhan, “A Clustered-Based Approach for Routing in Ad-Hoc Networks,” Proc. Second USENIX Symp. Mobile and Location Independent Computing, pp. 1-10, 1995.[21] T.-C. Hou and T.-J. Tsai, “An Access-Based Clustering Protocol for Multihop Wireless Ad Hoc Networks,” IEEE J. Selected Areas Comm., vol. 19, no. 7, pp. 1201-1210, July 2001.[22] A.B. McDonald and T.F. Znati, A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1466-1487, Aug. 1999.[23] D.J. Baker and A. Ephremides, “The Architectureal Organization of a Mobile Radio Network via a Distributed Algorithm,” IEEE Trans. Comm., vol. 29, no. 11, pp. 1694-1701, Nov. 1981.[24] M. Gerla and T.-C. Tsai, “Multicluster, Mobile, Multimedia Radio Network,” Wireless Networks, vol. 1, pp. 255–265, 1995.[25] Z.J. Haas and J. Deng, “Dual Busy Tone Multiple Access (DBTMA)—Performance Evaluation,” Proc. Vehicular Technology Conf. (VTC '99), vol. 1, pp. 314-319, 1999.[26] F.A. Tobagi and L. Kleinrock, “Packet Switching in Radio Channels: Part II,” IEEE Trans. Comm., vol. 23, pp. 1417-1433, 1975.[27] 3GPP Technical Specification 25.214, Physical Layer Procedures (FDD), release 5 ed. 2002.[28] K. Nakano and S. Olariu, “Randomized Initialization Protocols for Radio Networks,” IEEE Trans. Parallel and Distributed Systems, pp. 749-759 Nov. 2000[29] Understanding GPS: Principles and Applications, E.D. Kaplan, ed. Boston: Artech House, 1996.[30] B. Parkinson and S. Gilbert, “NAVSTAR: Global Positioning System—Ten Years Later,” Proc. IEEE, pp. 1177-1186, 1983.[31] P.H. Dana, “The Geographer's Craft Project,” Dept. of Geography, Univ. of Texas at Austin, Sept. 1999. http://www.utexas.edu/depts/grg/gcraf/notes/ gpsgps.html.[32] P. Clifford, http://www.jesus.ox.ac.uk/~clifford/a5/chap2 node9.html, May 2000.[33] S. Kishore, P. Agrawal, K.M. Sivalingam, and J.C. Chen, “MAC Layer Scheduling Strategies during Handoff for Wireless Mobile Multimedia Networks,” Proc. IEEE Int'l Conf. Personal Wireless Comm. (ICPWC), pp. 100-104, Dec. 1997.[34] I. Chlamtac and A. Farago, Making Transmission Schedules Immune to Topology Changes in Multihop Packet Radio Networks IEEE/ACM Trans. Networking, vol. 2, no. 1, pp. 23-29, Feb. 1994.[35] Z. Cai and M. Lu, X. Wang, “Randomized Broadcast Channel Access Algorithms for Ad Hoc Networks,” technical report, Electrical Eng. Dept., Texas A&M Univ., Nov. 2001.[36] T.-C. Hou and V.O.K. Li, Transmission Range Control in Multiple Packet Radio Networks IEEE Trans. Comm., vol. 34, no. 1, pp. 38-44, Jan. 1986.[37] L. Hu, “A Novel Topology Control for Multihop Packet Radio Networks,” Proc. IEEE INFOCOM '91, pp. 1084-1093, 1991.[38] A. Ephremides and T.V. Truong, “Scheduling Broadcasts in Multihop Radio Networks,” IEEE Trans. Comm., vol. 38, no. 4, pp. 456-460, 1990.[39] B. Hajek and G. Sasaki, “Link Scheduling in Polynomial Time,” IEEE Trans. Information Theory, vol. 34, pp. 910-917, 1988.[40] M.S. Corson and A. Ephremides, A Distributed Routing Algorithm for Mobile Wireless Networks ACM J. Wireless Networks, vol. 1, pp. 61-81, 1995.[41] C.D. Rais, R. Dube, K. Wang, and S.K. Tripathi, “Signal Stability Based on Adaptive Routing(SSA) for Ad-Hoc Mobile Networks,” technical report, Dept. of Computer Science, Univ. of Maryland, 1996.[42] Z. Cai and M. Lu, “Optimized Reparation Based on Sequenced Number Routing for Ad Hoc Networks,” Proc. Int'l Conf. Parallel and Distributed Computing and Systems (PDCS '99), pp. 1015-1020, Nov. 1999.[43] I. Chlamtac and O. Weinstein, “The Wave Expansion Approach to Broadcasting in Multihop Radio Networks,” IEEE Trans. Comm., vol. 39, pp. 426-433, Mar. 1991.[44] I. Chlamtac and S. Kutten, “On Broadcasting in Radio Networks-Problem Analysis and Protocol Design,” IEEE Trans. Comm., vol. 33, pp. 1240-1246, Dec. 1985.[45] A.B. McDonald and T.F. Znati, A Mobility-Based Framework for Adaptive Clustering in Wireless Ad Hoc Networks IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1466-1487, Aug. 1999.[46] C.R. Lin and J.S. Liu, “QoS Routing in Ad Hoc Wireless Networks,” IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1426-1438, Aug. 1999.[47] T.-C. Hou and T.-J. Tsai, “Adaptive Clustering in a Hierarchical Ad Hoc Network,” Proc. Int'l Computer Symp., pp. 171-176, Dec. 1998.
Index Terms:
Ad hoc networks, channel access, clustering, cluster leader.
Citation:
Zhijun Cai, Mi Lu, Xiaodong Wang, "Channel Access-Based Self-Organized Clustering in Ad Hoc Networks," IEEE Transactions on Mobile Computing, vol. 2, no. 2, pp. 102-113, Apr.-June 2003, doi:10.1109/TMC.2003.1217231
