Efficient integration of multi-hop wireless and wired networks with QoS constraints

ABSTRACT

This work considers the problem of designing an efficient and low-cost infrastructure for connecting static multi-hop wireless networks with wired backbone, while ensuring QoS requirements such as bandwidth and delay. This infrastructure is useful for designing low cost and fast deployed access networks in rural and suburban areas. It may also be used for providing access to sensor networks or for efficient facility placement in wireless networks. In these networks some nodes are chosen as access points and function as gateways to access a wired backbone. Each access point serves a cluster of its nearby user and a spanning tree rooted at the access point is used for message delivery. The work addresses both the design optimization and the operation aspects of the system. From the design perspective, we seek for a partition of the network nodes into minimal number of disjoint clusters that satisfy multiple constraints; Each cluster is required to be a connected graph with an upper bound on its radius. We assume that each node has a weight (representing its bandwidth requirement) and the total weight of all cluster nodes is also bounded. We show that these clustering requirements can be formulated as an instance of the Capacitated Facility Location problem (CFLP) with additional constraints. By breaking the problem into two sub-problems and solving each one separately, we propose polynomial time approximation algorithms that calculate solutions within a constant factor of the optimal ones. From the operation viewpoint, we introduce an adaptive delivery mechanism that maximizes the throughput of each cluster without violating the QoS constraints.

REFERENCES

• 1: H. Bolcskei, A. J. Paulraj, K. V. S. Hari, R. Nabar and W. W. Lu. "Fixed Broadband Wireless Access: State of the Art, Challenges and future Directions". Proc. IEEE Comm. Magazine, Vol. 39, No. 1, January 2001.
• 2: O. Momtahan And H. Hashemi. "A Comparative Evaluation of DECT, PACS and PHS Standards for Wireless Local Loop Applications". Proc. IEEE Comm. Magazine, Vol. 39, No. 5, May 2001.
• 3: G. Asada, M. Dong, T. S. Lin, F. Newberg, G. Pottie, W. J. Kaiser, and H. O. Marcy. "Wireless Integrated Network Sensors: Low Power Systems on a Chip", Proc. of European Solid State Circuits Conference, 1998.
• 4: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 5: David A. Beyer , Mark D. Vestrich , J. J. Garcia-Luna-Aceves, The rooftop community network: free, high-speed network access for communities, The first 100 feet: options for Internet and broadband access, MIT Press, Cambridge, MA, 1999
• 6: "Wireless Networking Reference - Community Wireless/ Rooftop Systems", http://www.practicallynetworked.com/tools/wireless_articles_community.htm.
• 7: P.-H. Hsiao, A. Hwang, H. T. Kung and Dario Vlah. "Load Balancing Routing for Wireless Access Networks". Proc. of IEEE INFOCOM '01, 2001.
• 8: R. Krishnan, R. Ramanathan, and M. Steenstrup, "Optimization Algorithms for Large Self-Structuring Networks", Proc. of IEEE INFOCOM '99, 1999.
• 9: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Low-Diameter Graph Decomposition is in NC, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.83-93, July 08-10, 1992
• 10: N. Linial and M. Saks, "Low Diameter Graph Decompositions", Combinatorica, Vol. 13, No. 4, 1993. %%pp. 441--454, 1993.
• 11: Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Fast distributed network decompositions and covers, Journal of Parallel and Distributed Computing, v.39 n.2, p.105-114, Dec. 15, 1996 [doi>10.1006/jpdc.1996.0159]
• 12: D. J. Baker and A. Ephremides. "The Architectural Organization of a Mobile Radio Network via Distributed Algorithm ", IEEE Trans. on Comm., Vol. 29(11), pp. 1694--1701, 1981.
• 13: C. R. Lin and M. Gerla, "Adaptive Clustering for Mobile Wireless Networks", IEEE Journal of Selected Areas in Communications, Vol. 15. No. 7, 1997.
• 14: Ram Ramanathan , Martha Steenstrup, Hierarchically-organized, multihop mobile wireless networks for quality-of-service support, Mobile Networks and Applications, v.3 n.1, p.101-119, June 1998 [doi>10.1023/A:1019148009641]
• 15: A. D. Amis and R. Prakash and T. H. V. Vuong and D. T. Huynh. "Max-Min D-Cluster Formation in Wireless Ad Hoc Networks", Proc. of IEEE INFOCOM 2000 , 2000.
• 16: B. Liang and Z. J. Haas, "Virtual Backbone Generation and Maintenance in Ad Hoc Network Mobility Management", Proc. of IEEE INFOCOM, 2000.
• 17: IEEE Journal of Selected Areas in Communications, Vol. 17. No. 8, Aug. 1999.
• 18: S. Banerjee and S. Khuller. "A Clustering Scheme for Hierarchical Control in Wireless Networks". Proc. IEEE INFOCOM 2001.
• 19: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 20: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 21: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 22: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 23: Y. Bejerano, "Efficient Integration of Multi-hop Wireless and Wired Networks with QoS Constraints", Technical Memorandum, %No. 10059712-020801-20, Bell-Labs, Lucent Technologies, 2002.
• 24: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]
• 25: Brent N. Clark , Charles J. Colbourn , David S. Johnson, Unit disk graphs, Discrete Mathematics, v.86 n.1-3, p.165-177, Dec. 14, 1990 [doi>10.1016/0012-365X(90)90358-O]
• 26: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 27: V. Chvatal, "A Greedy Heuristic for the Set-Covering Problem", Math. of Operation Research, Vol. 4, No. 3, 1979.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Theory

Keywords:
approximation algorithms, clustering, facility location, sensor networks, unit disk graphs, wireless access network