Weitere Artikel dieser Ausgabe durch Wischen aufrufen
This research is supported by Australian Research Council discovery grant, grant number: DP0877562.
Part of this paper has been published in ChinaCom’08.
In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.
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:
Grossglauser M, Kumar DNC (2002) Mobility increases the capacity of ad hoc wireless networks. IEEE/ACM Trans Netw 10:477–486 CrossRef
Foh CH, Lee BS (2004) A closed form network connectivity formula for one-dimensional manets. In: IEEE international conference on communications (ICC), pp 3739–3742
Antunes GJN, Pacheco A (2008) On the minimum hop count and connectivity in one-dimensional ad hoc wireless networks. Telecommun Syst 39(2):137–143 CrossRef
Kurlin LMV, Maskell S (2008) How many randomly distributed wireless sensors are enough to make a 1-dimensional network connected with a given probability. IEEE transactions on information theory, coRR, vol abs/0710.1001 (submitted)
Li J, Blake C, De Couto DSJ, Lee HI, Morris R (2001) Capacity of ad hoc wireless networks. In: Proceedings of the 7th ACM international conference on mobile computing and networking, Rome, Italy, July 2001, pp 61–69
Jain K, Padhye J, Padmanabhan VN, Qiu L (2003) Impact of interference on multi-hop wireless network performance. In: MobiCom ’03: proceedings of the 9th annual international conference on mobile computing and networking. ACM, New York, pp 66–80 CrossRef
Bohacek S, Wang P (2007) Toward tractable computation of the capacity of multi-hop wireless networks. In: IEEE INFOCOM 2007, pp 2099–2107
Tang J, Xue G, Chandler C, Zhang W (2006) Link scheduling with power control for throughput enhancement in multihop wireless networks. IEEE Trans Veh Technol 55(3):733–742, 0018–9545 CrossRef
Lin X, Shroff NB (2004) Joint rate control and scheduling in multihop wireless networks. In: 43rd IEEE conference on decision and control, vol 2, pp 1484–1489
Massimo F, Olivier D, David NCT, Patrick T (2007) Closing the gap in the capacity of wireless networks via percolation theory. IEEE Trans Inf Theory 53(3):1009–1018 CrossRef
Karp RM (1972) Reducibility among combinatorial problem. In: Miller R, Thatcher JW (eds) Complexity of computer computations. Springer, New York
Bollobas B (2002) Modern graph theory, 2nd edn. Springer, New York
Ta GMX, Anderson BDO (2008) Evaluation of the probability of k-hop connection in homogeneous wireless sensor networks. In: IEEE Globecom, pp 1279–1284
- The Maximum Throughput of A Wireless Multi-Hop Path
- Springer US
Neuer Inhalt/© Filograph | Getty Images | iStock