Abstract:

In a multihop wireless network,wireless interference is crucial to the multi-commodity flow problem,which studies the maximum throughput between multiple pairs of sources and sinks.Based on the observation that network coding (NC) could help to decrease the impacts of wireless interference,a framework was proposed to solve the problem for multihop wireless networks with NC.By introducing hyperarcs to model all possible (uncoded or encoded) transmissions and using the conflict graph of hyperarcs to describe the new conflict relations modified by NC (e.g.,in the protocol interference model),the problem was formulated to compute the maximum throughput of multiple unicast flows supported by the multihop wireless network with given NC settings,in which the constraints were rebuilt from the conflict graph of hyperarcs.Furthermore,a practical algorithm was proposed to collect maximal independent sets,instead of collecting all maximal independent sets in the conflict graph of hyperarcs (which is NP-hard),and some numerical results were illustrated.

Key words: multihop wireless network, multi-commodity flow problem, maximum throughput, network coding