Mobility-Sensitive Topology Control in Mobile Ad Hoc Networks
|
Abstract—In most existing localized topology control protocols for mobile ad hoc networks (MANETs), each node selects a few logical neighbors based on location information and uses a small transmission range to cover those logical neighbors. Transmission range reduction conserves energy and bandwidth consumption, while still maintaining network connectivity. However, the majority of these approaches assume a static network without mobility. In a mobile environment network connectivity can be compromised by two types of "bad” location information: inconsistent information, which makes a node select too few logical neighbors, and outdated information, which makes a node use too small a transmission range. In this paper, we first show some issues in existing topology control. Then, we propose a mobility-sensitive topology control method that extends many existing mobility-insensitive protocols. Two mechanisms are introduced: consistent local views that avoid inconsistent information and delay and mobility management that tolerate outdated information. The effectiveness of the proposed approach is confirmed through an extensive simulation study.
[1] 522 M. Bahramgiri, M. Hajiaghayi, and V.S. Mirrokni, “Fault-Tolerant and 3-Dimensional Distributed Topology Control Algorithms in Wireless Multi-Hop Networks,” Proc. Int'l Conf. Computer Communications and Networks, pp. 392-397, 2002.
[2] D. Blough, M. Leoncini, G. Resta, and P. Santi, “The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks,” Proc. MobiHoc, pp. 141-152, June 2003.
[3] M. Burkhart, P.V. Rickenbach, R. Wattenhofer, and A. Zollinger, “Does Topology Control Reduce Interference,” Proc. MobiHoc, May 2004.
[4] B. Burns, O. Brock, and B.N. Levine, “MV Routing and Capacity Building in Disruption Tolerant Networks,” Proc. IEEE Infocom, 2005.
[5] T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Comm. & Mobile Computing (WCMC), special issue on mobile ad hoc networking: research, trends, and applications, vol. 2, no. 5, pp. 483-502, 2002.
[6] J. Cartigny, D. Simplot, and I. Stojmenović, “Localized Minimum-Energy Broadcasting in Ad-Hoc Networks,” Proc. INFOCOM, vol. 3, pp. 2210-2217, Mar./Apr. 2003.
[7] Z. Chen, H. Kung, and D. Vlah, “Ad Hoc Relay Wireless Networks over Moving Vehicles on Highways,” Proc. ACM MobiHoc, 2001.
[8] K. Fall and K. Varadhan, “The ns Manual,” The VINT Project, UCB, LBL, USC/ISI and Xerox PARC, http://www.isi.edu/nsnam/nsdoc/, Apr. 2002.
[9] R.H. Frenkiel, B.R. Badrinath, J. Borras, and R.D. Yates, “The Infostations Challenge: Balancing Cost and Ubiquity in Delivering Wireless Data,” IEEE Personal Comm., vol. 7, no. 2, pp. 66-71, Apr. 2000.
[10] K.R. Gabriel and R.R. Sokal, “A New Statistical Approach to Geographic Variation Analysis,” Systematic Zoology, vol. 18, pp. 259-278, 1969.
[11] M. Grossglauser and D.N.C. Tse, “Mobility Increases the Capacity of Ad-Hoc Wireless Networks,” Proc. INFOCOM, pp. 1360-1369, 2001.
[12] D.B. Johnson, J. Broch, Y.-C. Hu, J. Jetcheva, and D.A. Maltz, “The CMU Monarch Project's Wireless and Mobility Extensions to NS,” Proc. 42nd Internet Eng. Task Force, Aug. 1998.
[13] L. Li and J.Y. Halpern, “Minimum Energy Mobile Wireless Networks Revisited,” Proc. Int'l Conf. Comm., pp. 278-283, June 2001.
[14] L. Li, J.Y. Halpern, V. Bahl, Y.M. Wang, and R. Wattenhofer, “Analysis of a Cone-Based Distributed Topology Control Algorithm for Wireless Multi-Hop Networks,” Proc. Conf. Principles of Distributed Computing, pp. 264-273, Aug. 2001.
[15] N. Li and J.C. Hou, “FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks,” Proc. MobiCom, pp. 275-286, Sept./Oct. 2004.
[16] N. Li, J.C. Hou, and L. Sha, “Design and Analysis of an MST-Based Topology Control Algorithm,” Proc. INFOCOM, vol. 3, pp. 1702-1712, Mar./Apr. 2003.
[17] Q. Li and D. Rus, “Sending Messages to Mobile Users in Disconnected Ad-Hoc Wireless Networks,” Proc. ACM MOBICOM, 2000.
[18] X.-Y. Li, P.-J. Wan, Y. Wang, and C.-W. Yi, “Fault Tolerant Deployment and Topology Control in Wireless Networks,” Proc. MobiHoc, pp. 117-128, June 2003.
[19] X.Y. Li, Y. Wang, P.J. Wan, W.Z. Song, and O. Frieder, “Localized Low-Weight Graph and Its Application in Wireless Ad Hoc Networks,” Proc. Infocom, 2004.
[20] J. Liu and B. Li, “Mobilegrid: Capacity-Aware Topology Control in Mobile Ad Hoc Networks,” Proc. Int'l Conf. Computer Comm. and Networks, pp. 570-574, Oct. 2002.
[21] E.L. Lloyd, R. Liu, M.V. Marathe, R. Ramanathan, and S.S. Ravi, “Algorithmic Aspects of Topology Control Problems for Ad Hoc Networks,” Proc. MobiHoc, pp. 123-134, June 2002.
[22] S. Narayanaswamy, V. Kawadia, R.S. Sreenivas, and P.R. Kumar, “Power Control in Ad-Hoc Networks: Theory, Architecture, Algorithm, and Implementation of the COMPOW Protocol,” Proc. European Wireless, pp. 156-162, Feb. 2002.
[23] R. Ramanathan and R. Rosales-Hain, “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment,” Proc. INFOCOM, pp. 404-413, Mar. 2000.
[24] V. Rodoplu and T.H. Meng, “Minimum Energy Mobile Wireless Networks,” IEEE J. Selected Areas in Comm., vol. 17, no. 8, pp. 1333-1344, Aug. 1999.
[25] M. Seddigh, J. Solano, and I. Stojmenović, “RNG and Internal Node Based Broadcasting in One-to-One Wireless Networks,” ACM Mobile Computing and Comm. Rev., vol. 5, no. 2, pp. 37-44, Apr. 2001.
[26] R. Shah, S. Roy, S. Jain, and W. Brunette, “Data MULES: Modeling a Three-Tier Architecture for Sparse Sensor Networks,” Proc. IEEE Workshop Sensor Net Protocols and Applications, 2003.
[27] T. Small and Z.J. Haas, “The Shared Wireless Infostation Model: A New Ad Hoc Networking Paradigm (or Where There Is a Whale, There Is a Way),” Proc. MobiHoc, pp. 233-244, June 2003.
[28] W.-Z. Song, Y. Wang, X.-Y. Li, and O. Frieder, “Localized Algorithms for Energy Efficient Topology in Wireless Ad Hoc Networks,” Proc. MobiHoc, May 2004.
[29] G. Toussaint, “The Relative Neighborhood Graph of Finite Planar Set,” Pattern Recognition, vol. 12, no. 4, pp. 261-268, 1980.
[30] A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad Hoc Networks,” Technical Report CS-200006, Duke Univ., Apr. 2000.
[31] Y. Wang, X. Li, P. Wan, and O. Frider, “Distributed Spanners with Bounded Degree for Wireless Ad Hoc Networks,” Int'l J. Foundations of Computer Science, vol. 14, no. 2, pp. 183-200, 2003.
[32] R. Wattenhofer, L. Li, V. Bahl, and Y.M. Wang, “Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks,” Proc. INFOCOM, pp. 1388-1397, Apr. 2001.
[33] J.E. Wieselthier, G.D. Nguyen, and A. Ephremides, “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Proc. INFOCOM, pp. 585-594, Mar. 2000.
[34] J. Wu and F. Dai, “A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks,” Proc. Int'l Conf. Distributed Computing Systems, pp. 460-468, May 2003.
[35] J. Wu and F. Dai, “Mobility Management and Its Applications in Efficient Broadcasting in Mobile Ad Hoc Networks,” Proc. INFOCOM, Mar. 2004.
[36] W. Zhao, M. Ammar, and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks,” Proc. Mobihoc, May 2004.
[37] W. Zhao, M. Ammar, and E. Zegura, “Controlling the Mobility of Multiple Data Transport Ferries in a Delay-Tolerant Network,” Proc. IEEE INFOCOM, 2005.
Index Terms:
Connectivity, mobile ad hoc networks (MANETs), mobility management, simulation, topology control, view consistency.
Citation:
Jie Wu, Fei Dai, "Mobility-Sensitive Topology Control in Mobile Ad Hoc Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 6, pp. 522-535, June 2006, doi:10.1109/TPDS.2006.73
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb