The transmission problem we are facing is to transmit messages indexed by
each of size
in bits via a multiple hop wireless network. Each message has its source node
and its destination node
. Let
be an index set for the set of messages with
. With
multiple path routing each message is transmitted via several paths from its source node to its destination node. Thus, nodes can send parts of messages to many receivers and receive parts of messages from many transmitters. We denote the nodes by
with
be a finite set of nodes. At any time, each of these nodes
can map any parts of messages
onto a single link
for transmission. The set of all links is denoted by
. A wireless communication link corresponds to an edge
between two nodes
and is described by the ordered pair
such that
transmits information directly to
. Moreover, we assume that
for all
. We have that
is a directed graph with node set
and edge set
. For an arbitrary node
, denote by
and
the set of outgoing and incoming edges within
at the node
, respectively. A link represents a wireless resource characterized by a given bandwidth, time duration, space fraction, or by a given code assignment. We assume a time-slotted single frequency network for which the time is divided into equal slots of length
while all nodes occupy the same frequency band of bandwidth
. Time slots are indexed by
, with
as an index set. We take time scheduling into account by assuming that there is a given coloring of the nodes such that adjacent nodes do not have the same color (half-duplex constraint) [
4]. That is, we are given a number
and a function
such that
for all nodes
with
. Here,
is at least as large as the chromatic number of
. Computing such a coloring can be done by a Greedy approach [
7]. To take delay constraints into account we introduce
as the maximum number of time slots, a message is allowed to use for transmission from its source to its destination, that is,
. The interference model we consider includes multiple access interference caused by simultaneously active transmissions that can not be perfectly separated by, for example, code- or space division multiple access (CDMA/SDMA) techniques. Thus, let
be the set of edges interfering edge
at time
. The signal attenuation from node
to node
is
and it remains unchanged within the duration of a time slot
. We further assume perfect knowledge of
at the corresponding senders. Let
be the transmitting node and let
be the receiving node of edge
. Hence,
denotes the attenuation a signal suffers that is transmitted from
but received by node
. For link
such a signal represents multiple-access interference that is caused by link
. Furthermore, with
as the (transmit) power to be allocated to link
at time slot
, the received signal power at node
from the transmitter
is given by
. We define the signal-to-interference-plus-noise ratio (SINR) of edge
at time slot
as
with
as an additive noise power of edge
. If we only assume thermal noise to be the same for all edges, we have
with noise spectral density
. For the optimization problems to be introduced later we have the following design variables. As network flow variables we have
as the part of the message
sent along edge
in time slot
(in bits), and
as the part of the message
stored in a buffer at node
directly before the start of time slot
(in bits). Communication variable
is the transmit power allocated to edge
at time slot
to transmit the total traffic on edge
(in Watt). If we stack the different variables to vectors we obtain
,
, and
. We further use the following parameters. Let
be the size of message
(in bits) and
be the maximum total buffer size at node
(in bits). Power constraints are
as the maximum transmission power of a node (in Watt) assumed to be the same for all nodes and
as the maximum transmission power per edge (in Watt).