Name
Title | ||
|---|---|---|
Throughput Optimization in Multihop Wireless Networks with Multipacket Reception and Directional Antennas |
Abstract | ||
|---|---|---|
Recent advances in the physical layer have enabled the simultaneous reception of multiple packets by a node in wireless networks. We address the throughput optimization problem in wireless networks that support multipacket reception (MPR) capability. The problem is modeled as a joint routing and scheduling problem, which is known to be NP-hard. The scheduling subproblem deals with finding the optimal schedulable sets, which are defined as subsets of links that can be scheduled or activated simultaneously. We demonstrate that any solution of the scheduling subproblem can be built with \vert E\vert + 1 or fewer schedulable sets, where \vert E\vert is the number of links of the network. This result is in contrast with previous works that stated that a solution of the scheduling subproblem is composed of an exponential number of schedulable sets. Due to the hardness of the problem, we propose a polynomial time scheme based on a combination of linear programming and approximation algorithm paradigms. We illustrate the use of the scheme to study the impact of design parameters on the performance of MPR-capable networks, including the number of transmit interfaces, the beamwidth, and the receiver range of the antennas. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/TPDS.2010.202 | Parallel and Distributed Systems, IEEE Transactions |
Keywords | Field | DocType |
approximation theory,computational complexity,directive antennas,linear programming,radio networks,scheduling,NP-hard problem,approximation algorithm,directional antennas,linear programming,multihop wireless networks,multipacket reception,physical layer,polynomial time scheme,routing problem,scheduling problem,throughput optimization problem,NP-hard.,Wireless networks,directional antennas,multihop,multipacket reception | Approximation algorithm,Wireless network,Job shop scheduling,Computer science,Scheduling (computing),Network packet,Computer network,Linear programming,Throughput,Optimization problem,Distributed computing | Journal |
Volume | Issue | ISSN |
22 | 7 | 1045-9219 |
Citations | PageRank | References |
2 | 0.39 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jorge Crichigno | 1 | 168 | 14.41 |
| Min-you Wu | 2 | 1600 | 140.81 |
| Sudharman K. Jayaweera | 3 | 99 | 6.39 |
| Wennie Shu | 4 | 2 | 0.39 |