We have developed a protocol to achieve max-min fair scheduling in wireless multihop networks. Our protocol calculates fair shares of all flows in the network in a distributed manner. Each node in the network learns the flow contention graph in the local network by exchanging local information with its neighbors. By learning the flow contention graph, nodes are able to calculate the fair shares of the flows that they serve. Nodes then enforce this share by controlling the rate at which each flow is served. Finally, each node applies the back pressure protocol to ensure that flow shares remain same throughout the path of the flow, i.e. flows receive the same share along all hops in the path. We have implemented this fair scheduling discipline on ns2 and compared its performance with FCFS scheduling discipline.

We have enhanced the upper layer scheduling protocol with a virtual time based MAC protocol. Virtual time CSMA originally proposed by Klienrock and Molle as an alternative for random access MAC protocol for packet radio network. The original protocol can be viewed as a single server serving jobs in a first in first out manner. This protocol provides fair medium access in single hop wireless networks but may lead to severe starvation if adopted as is in multihop wireless networks. In this work we have enumerated the shortcomings of the protocol in multihop networks. We have proposed a solution for the starvation problem in pure VTCSMA. Our solution is based upon the channel access mechanism of VTCSMA and we have borrowed the solution to hidden terminal from 802.11. Our solution to starvation is similar to the jamming procedure that is used in Ethernet.

We have evaluated our protocol through simulation using the popular network simulator (ns2) and have reported superior performance compared to 802.11 protocol.

• M.L. Molle and L. Klienrock, Virtual Time CSMA: Why two clocks are better than one. IEEE transactions on Communications, 1985
• Xiao Long Huang, Brahim Bensaou: On max-min fairness and scheduling in wireless ad-hoc networks: analytical framework and implementation. MobiHoc 2001
• Leandros Tassiulas, Saswati Sarkar, Max-min fair scheduling in wireless Ad hoc Networks, IEEE Journal for Selected Areas in Communications Special Issue on Ad Hoc Networks, Part I, Vol. 23, No. 1, January 2005
• Saswati Sarkar, Leandros Tassiulas, End-to-end Bandwidth Guarantees Through Fair Local Spectrum Share in Wireless Adhoc Networks Accepted for publication in IEEE Transactions on Automatic Control.

• Faculty: Samir Das
• Graduate Student: Shweta Jain

Please send all questions and comments to Shweta Jain at email.