This project uses a window based flow control and rate based scheduling algorithm for multihop wireless networks with fixed-route flows operated under a general interference model with interference degree. The proposed algorithm not only achieves a provable throughput guarantee, but also leads to explicit upper bounds on the end-to-end delay of every flow. The end-to-end delay and throughput bounds are in simple and closed forms, and they explicitly quantify the tradeoff between throughput and delay of every flow. The proposed algorithm is fully distributed and requires a low per-node complexity that does not increase with the network size. Hence, it can be easily implemented in practice.
Keywords: multihop wireless networks , rate based scheduling, throughput, window based flow control,
The joint congestion control and scheduling problem in multihop wireless networks has been extensively studied in the literature. Often, each user is associated with a non decreasing and concave utility function of its rate, and a cross-layer utility maximization important as well because, practical congestion control protocols need to set retransmission timeout values based on the packet delay, and such parameters could significantly impact the speed of recovery when packet loss occurs. Packet delay is also important for multimedia traffic, some of which have been carried on congestion-controlled sessions.There are two major issues on the delay-performance of the back-pressure algorithm. First, for long flows, the end-to-end delay may grow quadratically with the number of hops. Under the back-pressure algorithm, if a link schedules the long flow, the queue difference of the long flow must be larger than the queue length q of the competing short flow. Therefore, when the joint congestion and scheduling algorithm converges, the queue length of the long flow at each hop must be around Hq,(H-1)q,..,q and the total end-to-end backlog is of order O(H2). By Little’s law, the end-to-end delay will also be of order O(H2). Note that a packet needs at least H time-slots to reach the destination. Hence, the optimal order should have been O(H). This implies that the back-pressure algorithm may have significantly larger end-to-end delay for long flows.
Second, under the back-pressure algorithm, it is difficult to control the end-to-end delay of each flow. The main parameter to tune a joint congestion control and scheduling algorithm based on the back-pressure algorithm is the step size in the queue update. A larger step size may lead to smaller queue length. However, a smaller step size is needed to ensure that the joint congestion control and scheduling algorithm converges to close-to-optimal system throughput. Although one may use the step sizes to tune the throughput–delay tradeoff, a change of the step size on one node will likely affect all flows passing through the...