Joint per-flow scheduling and routing in wireless multihop networks

Multihop networks are used in a variety of ways, that include ad-hoc networks, wireless sensor networks, and mesh networks. These networks consist of nodes that connect over a wireless channel, and communicate over multiple links by forwarding each other´s messages. The throughput is determined by the contention among the nodes for the wireless resources. Thus routing algorithms, influence the level of contention at each location of the network, and play an important role in the network throughput. Additionally, the sequence of transmission opportunities of each node, which is determined by the scheduling algorithm, should also be carefully designed, since it affects the available resources of each node. In this paper we study the effect of routing and scheduling algorithms on the throughput of multihop networks. We propose a per-flow joint routing/scheduling algorithm that has the property of routing the flows in a way that avoids congested areas with limited availability, and also schedules links, in a way that a) slots are assigned to flows, instead of links or nodes, b) the assignment is fair c) fairness does not lead to underutilization. Simulation results showed that the proposed algorithm increases the average throughput, and the degree of satisfaction of each node, while at the same time it decreases the average delay.