Multihop Wireless Networks: Opportunistic Routing

5.3 Problem Formulation

In this section we present our methodology to compute the throughput bound between two end nodes in a multiradio, multichannel, multihop wireless network when OR is available. We first study which opportunistic modules can coexist at the same time under the constraints of wireless interference and radio interface limits. We then formulate the end-to-end throughput bound as an LP problem, which solves the radio-channel assignment, transmission scheduling and forwarding candidate selection problems together. We further propose an LP approach and a heuristic algorithm to find a feasible scheduling of opportunistic forwarding priorities to achieve the capacity.

5.3.1 Concurrent Transmission Sets

In this subsection, we will discuss which opportunistic modules in the network can be activated at the same time. The set of opportunistic modules that can be activated at the same time is called the concurrent transmission set (CTS). The motivation for building a concurrent transmission set is similar that for building an independent set in Jain et al. (2003) and concurrent transmission patterns in Zhang et al. (2005)—that is, taking the benefit of time-sharing scheduling of different concurrent transmission sets, we could achieve a collection of capacity graphs, associated with capacity constraint on each link. Opportunistic routing can be performed on the underlying capacity graph to achieve the maximum throughput. However, the methodology of constructing CTS for ...