Weitere Kapitel dieses Buchs durch Wischen aufrufen
In this chapter, we explore techniques for capacity estimation and throughput maximization in multi-hop wireless networks. The specific problem we investigate is the following: how can we characterize the set of all feasible end-to-end connection throughput rate vectors which can be supported by the network (i.e., what is the network capacity), and how can we design cross-layer algorithms at the scheduling, routing, and transport layers which are guaranteed to operate the network close to its capacity? We approach this problem from three distinct perspectives which have greatly influenced research in this field: (1) throughput scaling in random geometric graphs whose nodes are distributed uniformly in space, (2) geometric packing and linear programming-based techniques for arbitrary networks, and (3) the dynamic back-pressure scheme based on queueing theoretic principles for achieving network stability. A recurring theme throughout this chapter is the role of geometric insights into the design and analysis of provably good algorithms for multi-hop wireless networks. We also include a brief survey of related developments in the field of cross-layer algorithms for multi-hop wireless networks.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
A. Agarwal and P. Kumar. Capacity bounds for ad hoc and hybrid wireless networks. In ACM SIGCOMM Computer Communications Review, volume 34(3), 2004.
R. Ahuja, R. Magnanti, and J. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
M. Alicherry, R. Bhatia, and L. E. Li. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking, pages 58–72, New York, NY, USA, 2005. ACM Press.
M. Andrews, K. Jung, and A. Stolyar. Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. In STOC, pages 145–154, 2007.
E. Anshelevich, D. Kempe, and J. M. Kleinberg. Stability of load balancing algorithms in dynamic adversarial systems. In STOC, pages 399–406, 2002.
S. Asmussen. Applied Probability and Queues. New York: Springer-Verlag, 2 edition, 1993.
B. Awerbuch, P. Berenbrink, A. Brinkmann, and C. Scheideler. Simple routing strategies for adversarial systems. In FOCS, pages 158–167, 2001.
B. Awerbuch and F. T. Leighton. A simple local-control approximation algorithm for multicommodity flow. In FOCS, pages 459–468, 1993.
B. Awerbuch and T. Leighton. Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. In STOC, pages 487–496, 1994.
D. J. Baker, J. E. Wieselthier, and A. Ephremides. A distributed algorithm for scheduling the activation of links in self-organizing mobile radio networks. In IEEE Int. Conference Communications, pages 2F6.1–2F6.5, 1982.
H. Balakrishnan, C. Barrett, A. Kumar, M. Marathe, and S. Thite. The Distance 2-Matching Problem and Its Relationship to the MAC Layer Capacity of Adhoc Wireless Networks. special issue of IEEE J. Selected Areas in Communications, 22(6):1069–1079, 2004.
N. Bansal and Z. Liu. Capacity, Delay and Mobility in Wireless Ad-Hoc Networks. In IEEE INFOCOM 2003, San Francisco, CA, April 1–3 2003.
N. Bansal and Z. Liu. Capacity, Delay and Mobility in Wireless Ad-Hoc Networks. In IEEE INFOCOM 2003, San Francisco, CA, April 1–3 2003.
C. L. Barrett, A. Marathe, M. V. Marathe, and M. Drozda. Characterizing the interaction between routing and mac protocols in ad-hoc networks. In MobiHoc, pages 92–103, 2002.
C. Buraagohain, S. Suri, C. Tóth, and Y. Zhou. Improved throughput bounds for interference-aware routing in wireless networks. In Proc. Computing and Combinatorics Conference, 2007.
D. Chafekar, V. A. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan. Approximation algorithms for computing of wireless networks with sinr constraints. In Proc. of IEEE INFOCOM, 2008.
D. Chafekar, D. Levin, V. A. Kumar, M. Marathe, S. Parthasarathy, and A. Srinivasan. Capacity of asynchronous random-access scheduling in wireless networks. In Proc. of IEEE INFOCOM, 2008.
P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in multi-hop wireless networks. In Proceedings of 43rdAnnual Allerton Conference on Communications, Control, and Computing, 2005.
L. Chen, S. H. Low, M. Chiang, and J. C. Doyle. Cross-layer congestion control, routing and scheduling design in ad hoc wireless networks. In INFOCOM, pages 1–13, 2006.
L. Chen, S. H. Low, and J. C. Doyle. Joint congestion control and media access control design for ad hoc wireless networks. In INFOCOM, pages 2212–2222, 2005.
M. Chiang, S. H. Low, A. R. Calderbank, and J. C. Doyle. Layering as optimization decomposition: A mathematical theory of network architectures. Proceedings of the IEEE, 95(1): 255–312, 2007. CrossRef
S. Cui, R. Madan, A. J. Goldsmith, and S. Lall. Cross-layer energy and delay optimization in small-scale sensor networks. IEEE Transactions on Wireless Communications, 6(10): 3688–3699, 2007. CrossRef
D. S. J. De Couto, D. Aguayo, J. Bicket, and R. Morris. A High-Throughput Path Metric for Multi-Hop Wireless Routing. In Proceedings of Mobicom, pages 134–146. ACM Press, 2003.
R. Draves, J. Padhye, and B. Zill. Routing in multi-radio, multi-hop wireless mesh networks. In MobiCom ’04: Proceedings of the 10th annual international conference on Mobile computing and networking, pages 114–128, 2004.
A. Eryilmaz and R. Srikant. Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control. In Proc. of IEEE INFOCOM, 2005.
A. E. Gamal, J. P. Mammen, B. Prabhakar, and D. Shah. Throughput-delay trade-off in wireless networks. In IEEE INFOCOM, 2004.
M. Gastpar and M. Vetterli. On The Capacity of Wireless Networks: The Relay Case. In IEEE INFOCOM 2002, New York, NY, June 23–27 2002.
L. Georgiadis, M. J. Neely, and L. Tassiulas. Resource allocation and cross-layer control in wireless networks. Found. Trends Netw., 1(1):1–144, 2006. CrossRef
M. Gerla, B. Zhou, Y.-Z. Lee, F. Soldo, U. Lee, and G. Marfia. Vehicular grid communications: the role of the internet infrastructure. In WICON ’06: Proceedings of the 2nd annual international workshop on Wireless internet, page 19, New York, NY, USA, 2006. ACM.
M. Grossglauser and D. N. C. Tse. Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans. Netw., 10(4):477–486, 2002. CrossRef
K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interference on multi-hop wireless network performance. In Proceedings of the 9th annual international conference on Mobile computing and networking, pages 66–80. ACM Press, 2003.
M. Kaufmann, J. F. Sibeyn, and T. Suel. Derandomizing algorithms for routing and sorting on meshes. In SODA ’94: Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, pages 669–679, Philadelphia, PA, USA, 1994. Society for Industrial and Applied Mathematics.
S. A. Khayam, S. Karande, M. Krappel, and H. Radha. Cross-layer protocol design for real-time multimedia applications over 802.11 b networks. In ICME ’03: Proceedings of the 2003 International Conference on Multimedia and Expo, pages 425–428, 2003.
M. Kodialam and T. Nandagopal. Characterizing achievable rates in multi-hop wireless networks: the joint routing and scheduling problem. In Proceedings of the 9th annual international conference on Mobile computing and networking, pages 42–54. ACM Press, 2003.
M. Kodialam and T. Nandagopal. Characterizing thanks, rates in multi-hop wireless mesh networks with orthogonal channels. IEEE/ACM Trans. Netw., 13(4):868–880, 2005. CrossRef
M. Kodialam and T. Nandagopal. Characterizing the capacity region in multi-radio multi-channel wireless mesh networks. In MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking, pages 73–87, New York, NY, USA, 2005. ACM Press.
U. Kozat and L. Tassiulas. Throughput capacity in random ad-hoc networks with infrastructure support. In Proc. 9th Annual ACM International Conference on Mobile computing and networking, 2003.
U. C. Kozat and L. Tassiulas. Throughput capacity of random ad hoc networks with infrastructure support. In MobiCom ’03: Proceedings of the 9th annual international conference on Mobile computing and networking, pages 55–65, New York, NY, USA, 2003. ACM Press.
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. End-to-end packet-scheduling in wireless ad-hoc networks. In SODA ’04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1021–1030, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics.
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Algorithmic aspects of capacity in wireless networks. In SIGMETRICS ’05: Proceedings of the 2005 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 133–144, 2005.
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Provable algorithms for joint optimization of transport, routing and mac layers in wireless ad hoc networks. In Proc. DialM-POMC Workshop on Foundations of Mobile Computing, 2007. Eight pages.
V. S. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. Throughput maximization in multi-channel multi-radio wireless networks. Technical report, Virginia Tech, 2009.
M. Kunde. Block gossiping on grids and tori: Deterministic sorting and routing match the bisection bound. In ESA ’93: Proceedings of the First Annual European Symposium on Algorithms, pages 272–283, London, UK, 1993. Springer-Verlag.
Q. Liang, D. Yuan, Y. Wang, and H.-H. Chen. A cross-layer transmission scheduling scheme for wireless sensor networks. Comput. Commun., 30(14-15):2987–2994, 2007. CrossRef
X. Lin and S. Rasool. A distributed and provably efficient joint channel-assignment, scheduling and routing algorithm for multi-channel multi-radio wireless mesh networks. In Proc. of IEEE INFOCOM, 2007.
X. Lin and N. B. Shroff. The impact of imperfect scheduling on cross-layer congestion control in wireless networks. IEEE/ACM Trans. Netw., 14(2):302–315, 2006. CrossRef
X. Lin, N. B. Shroff, and R. Srikant. A tutorial on cross-layer optimization in wireless networks. IEEE Journal on Selected Areas in Communications, 24(8):1452–1463, 2006. CrossRef
B. Liu, Z. Liu, and D. Towsley. On the Capacity of Hybrid Wireless Networks. In IEEE INFOCOM 2003, San Francisco, CA, April 1–3 2003.
H. Nama, M. Chiang, and N. Mandayam. Utility lifetime tradeoff in self regulating wireless sensor networks: A cross-layer design approach. In IEEE ICC, jun 2006.
M. J. Neely. Dynamic power allocation and routing for satellite and wireless networks with time varying channels. PhD thesis, Massachusetts Institute of Technology, LIDS, 2003.
M. J. Neely, E. Modiano, and C.-P. Li. Fairness and optimal stochastic control for heterogeneous networks. In INFOCOM, pages 1723–1734, 2005.
M. J. Neely, E. Modiano, and C. E. Rohrs. Tradeoffs in delay guarantees and computation complexity for n × n packet switches. In Conference on Information Sciences and Systems, 2002.
M. J. Neely, E. Modiano, and C. E. Rohrs. Dynamic power allocation and routing for time-varying wireless networks. IEEE Journal on Selected Areas in Communications, 23(1):89–103, 2005. CrossRef
S. Parthasarathy. Resource Allocation in Networked and Distributed Environments. PhD thesis, Department of Computer Science, University of Maryland at College Park, 2006.
C. Peraki and S. D. Servetto. On the maximum stable throughput problem in random networks with directional antennas. In MobiHoc ’03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 76–87, New York, NY, USA, 2003. ACM Press.
A. Rajeswaran and R. Negi. Capacity of power constrained ad-hoc networks. In INFOCOM, 2004.
S. Ramanathan and E. L. Lloyd. Scheduling algorithms for multihop radio networks. IEEE-ACM Transactions on Networking (ToN), 1:166–177, 1993.
A. Schrijver. Theory of Linear and Integer Programming. Wiley, 2001.
E. Setton, T. Yoo, X. Zhu, A. Goldsmith, and B. Girod. Cross-layer design of ad hoc networks for real-time video streaming. Wireless Communications, IEEE, 12(4):59–65, 2005. CrossRef
G. Sharma, R. R. Mazumdar, and N. B. Shroff. On the complexity of scheduling in wireless networks. In MobiCom ’06: Proceedings of the 12th annual international conference on Mobile computing and networking, pages 227–238, New York, NY, USA, 2006. ACM Press.
L. Tassiulas. Dynamic link activation scheduling in multihop radio networks with fixed or changing topology. PhD thesis, University of Maryland, College Park, 1991.
Y. Tian and E. Ekici. Cross-layer collaborative in-network processing in multihop wireless sensor networks. IEEE Transactions on Mobile Computing, 6(3):297–310, 2007. CrossRef
S. Toumpis and A. Goldsmith. Large wireless networks under fading, mobility, and delay constraints. In Proc. of the IEEE INFOCOM, 2004.
W. Wang, X.-Y. Li, O. Frieder, Y. Wang, and W.-Z. Song. Efficient interference-aware TDMA link scheduling for static wireless networks. In MobiCom ’06: Proceedings of the 12th annual international conference on Mobile computing and networking, pages 262–273, New York, NY, USA, 2006. ACM Press.
X. Wang and K. Kar. Cross-layer rate optimization for proportional fairness in multihop wireless networks with random access. IEEE Journal on Selected Areas in Communications, 24(8):1548–1559, 2006. CrossRef
X. Wu and R. Srikant. Regulated maximal matching: A distributed scheduling algorithm for multi-hop wireless networks with node-exclusive spectrum sharing. In IEEE Conf. on Decision and Control, 2005.
Y. Yang, J. Wang, and R. Kravets. Designing routing metrics for mesh networks. In First IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005.
S. Yi, Y. Pei, and S. Kalyanaraman. On the capacity improvement of ad hoc wireless networks using directional antennas. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pages 108–116, 2003.
G. Zussman, A. Brzezinski, and E. Modiano. Multihop local pooling for distributed throughput maximization in wireless networks. In Proc. of IEEE INFOCOM, 2008.
- Cross-Layer Capacity Estimation and Throughput Maximization in Wireless Networks
V. S. Anil Kumar
Madhav V. Marathe
- Springer London
- Chapter 5
Neuer Inhalt/© ITandMEDIA, Product Lifecycle Management/© Eisenhans | vege | Fotolia