The communication network is layered in order to decompose the complex network design problems into simpler and easy to manage problems in each individual layer. However, the end-to-end performance may suffer, as the layered approach ignores the interaction among different layers. In this dissertation, we consider a particular network design algorithm, a scheduling protocol in a wireless network. We take a cross-layer approach by jointly considering the components at both the physical layer and the link layer to analyze and optimize the performance of a wireless scheduling protocol. We first propose a novel scheduling protocol for communications over time-varying wireless channels with memory. We incorporate a realistic channel model, and develop a new notion of system level fairness to study the impact of the changes in the physical layer on the performance of the scheduling protocol at the data link layer. We also consider imperfect estimation of the channel conditions, based upon which the scheduling decision is made. Secondly, we present a criterion which determines the existence of fair wireless scheduling protocols. We develop a two-tier channel model to tie the performance of the scheduling protocol directly with the physical layer parameters. We demonstrate the tradeoff between the throughput and the fairness property of the scheduling protocol, and provide guidelines to design scheduling algorithms to maximize the system throughput. We then study a mechanism of providing channel state information to the scheduler. We introduce a technique using noncoherent detection to estimate the channel state in order to avoid the overhead of a pilot-aided channel estimation scheme. We propose a two-policy scheduling rule when noncoherent detection is employed, and show that higher throughput gain can be achieved. We also show our cross-layer design philosophy by another example: incorporating an ARQ scheme to an interleaved coded system. We derive the optimal size of the interleaver when a retransmission strategy is used to meet the both delay constraint and the reliability requirement. Finally, we show our experimental findings on the packet error statistics in 802.11b networks.