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.
展开▼
