We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing solutions are using the same transmission range, the benefit in d-dimensional networks is at least . Moreover, it is shown that if the transmission range can be optimized for routing and coding individually, the benefit in 2-dimensional networks is at least 3. Our results imply that codes following a decode-and-recombine strategy are not always optimal regarding energy efficiency.
1. Introduction
Emerging applications in wireless networks, like environment monitoring in rural areas by ad hoc networks, require more and more resources. One of the most important limitations is formed by battery life. Since battery technology is not keeping up with the increasing demand from resource-consuming applications, it is imperative that more efficient use is made of the available energy. There has been significant recent attention to the problem of minimizing energy consumption in networks. Some of the topics considered are minimum cost routing [1‐3], power control algorithms [4‐6], and cross-layer protocol design for energy minimization [7]. In this work, we are interested in the use of network coding [8‐14] for reducing the energy consumption in wireless networks. We compare the reduction with traditional routing solutions. The contributions of this work are lower bounds on the energy reduction that can be achieved by using network coding for multiple unicast problems in wireless networks.
In recent years, there has been significant interest in network coding with the aim of reducing energy consumption in networks. More generally, network coding with a cost criterion has been considered. Much progress has been made in understanding the case of multicast traffic. In fact, it has been shown by Lun et al. that a minimum-cost network coding solution can be found in a distributed fashion in polynomial time [15]. The fact that the complexity of finding this solution is polynomial in time is surprising, since the corresponding routing problem is a Steiner tree problem that is known to be NP-complete [16].
Advertisement
Besides constructing minimum-cost coding solutions, it is also of interest to know what the benefits of network coding are compared to routing. In this work we, are interested in the energy benefit of network coding, which is the ratio of the minimum energy solution in a routing solution compared to the minimum energy network coding solution, maximized over all configurations. It has been shown by Goel and Khanna [17] that the energy benefit of network coding for multicast problems in wireless networks is upper bounded by a constant. The problem of reducing energy consumption for many-to-many broadcast traffic in wireless networks has been studied by Fragouli et al. in [18] and Widmer and Le Boudec in [19], providing lower bounds on the energy benefit of network coding for specific topologies. More importantly, algorithms have been presented in [18, 19] that allow to exploit these benefits in practical scenarios, that is, in a distributed fashion.
The above demonstrates that for multicast traffic and for many-to-many broadcast traffic, there is some understanding of the energy benefits of network coding and how to exploit them. In order to reduce energy consumption in practical networks, however, it is important to consider also multiple unicast traffic. Indeed, in practice a large part of the data will be generated by unicast sessions. For the case of multiple unicast traffic, contrary to multicast and broadcast, not much is known. This paper deals with the energy benefits of network coding for wireless multiple unicast. Remember from the above that for multicast, the problem of minimum-cost routing is hard, whereas minimum-cost network coding is easy. In stark contrast, the problem of minimum-cost multiple unicast routing is easy. One constructs the minimum-cost solution, that is, the shortest path, for each session individually. The minimum-cost multiple unicast network coding problem, however, seems hard and in general very little is known.
Network coding for the multiple unicast problem was first studied by Wu et al. in [20], in which it was shown that in the information exchange problem on the line network, the energy saving achieved by network coding is a factor two. The network codes that we construct in this work are in a sense a generalization of the results on one-dimensional networks [20], to higher-dimensional networks. The networks considered in this work are lattices. More specifically, the hexagonal lattice and the rectangular lattice. Effros et al. [21] and Kim et al. [22] have considered energy-efficient network codes on the hexagonal lattice. We improve the lower bounds on the energy savings of network on the hexagonal lattice given in [21]. More precisely, we improve the previously known bound of and obtain a new bound of .
Kramer and Savari have developed techniques that can be used to upper bound the achievable throughputs in a multiple unicast problem [23]. No methods are known, however, to lower bound the cost of network coding solutions for a configuration. A lower bound to the ratio of the minimum energy consumption of routing and coding solutions for a given multiple unicast configuration was provided by Keshavarz-Haddad and Riedi in [24]. For the type of configurations used in this paper, however, the results from [24] give the trivial lower bound of one. We will see, however, that network coding has large energy savings for these configurations.
Advertisement
An important class of network codes operates according to a principle that we will refer to in the remainder as decode-and-recombine. These codes satisfy the constraint that each symbol in each linear combination that is transmitted is explicitly known by the node transmitting that linear combination. Note, that this is a restriction from the general linear coding strategy, in which linear combinations of coded messages can be retransmitted. The motivation behind using decode-and-recombine codes is that it prevents information from spreading too much in the network, away from the path between source and destination, a heuristic introduced by Katti et al. [25]. The use of a decode-and-recombine strategy results in reduced complexity. However, an important question that has to be addressed is whether the use of decode-and-recombine codes leads to a higher energy consumption than is strictly necessary. We answer this question affirmatively. An upper bound of three on the energy benefit of decode-and-recombine codes has been given by Liu et al. [26]. One of the contributions of this work is to show that larger energy benefits can be obtained by considering also other types of codes.
This paper is organized as follows. In Section 2 we specify our model and problem statement more precisely. Our main results are presented in Section 3. Constructions of configurations that allow a large energy benefit for network coding and proofs of our results are given in Sections 4 and 5. In Section 6, finally, we discuss our work.
2. Model and Problem Statement
Let be the nodes of a -dimensional wireless network. We consider a wireless network model with broadcast, where all nodes within range of a transmitting node can receive, and nodes outside this range cannot. More precisely, given a transmission range , a node is broadcasting to all nodes in the set
(1)
where denotes the Euclidean norm of . The energy required to transmit one unit of information to all other nodes within range equals , where is the path loss exponent and is some constant. In analyzing the energy consumption of nodes, we will consider only the energy consumed by transmitting. Receiver energy consumption as well as energy consumed by processing are assumed to be negligible compared to transmitter energy consumption. In particular, note that little additional processing is required for network coding, compared to the processing that is performed in a traditional wireless protocol stack.
The traffic pattern that we consider is multiple unicast. All symbols are from the field , that is, they are bits and addition corresponds to the xor operation. The source of each unicast session has a sequence of source symbols that need to be delivered to the corresponding destination. Let be the set of unicast sessions. We call a wireless multiple unicast configuration.
We will compare energy consumption of routing and network coding. Our goal is to establish lower bounds on the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. We will refer to this ratio as the energy benefit of network coding. Let and be the minimum energy required for network coding and routing solutions, respectively, for a configuration . The energy consumption of a coding or routing scheme is defined as the time-average of the total energy spent by all nodes in the network to deliver one symbol for each unicast session. In analyzing coding schemes, we will ignore the energy consumption in an initial startup phase and consider only steady-state behavior.
Note that since energy consumption per transmission equals , the transmission range is an important factor in the energy consumption. Therefore, it is of particular interest to optimize the transmission range such that energy consumption is minimized. In this work, we consider two different quantities: () , denoting the energy benefit that can be obtained if the transmission range is given and fixed and () , denoting the energy benefit that can be obtained if one is allowed to optimize the transmission range. Note that the transmission range can be individually optimized for the routing and network coding scenarios. More precisely, the goal of this work is to establish lower bounds on
(2)
where the maximization is over all node locations , multiple unicast sessions , and transmission ranges , with the transmission range equal for the routing and network coding solutions, and
(3)
where the maximization is over all node locations and multiple unicast sessions , with the transmission range being optimized individually for the routing and network coding solutions. If no confusion can arise, we will omit dependency on in the notation for and .
Since in , is equal for and , the energy per transmission is equal in and and the benefit is equal to the ratio of the number of transmissions required in routing and network coding solutions.
Since we are interested in energy consumption only, we can assume that all transmissions are scheduled sequentially and/or that there is no interference. All coding and routing schemes that we consider proceed in time slots or rounds. In each time slot, all nodes are allowed to transmit one or more messages. We assume that the length of the time slot is large enough to accommodate sequential transmission of all messages in that round. Coding operations will be based on messages received in previous time slots only. Finally, we assume that all nodes have complete knowledge of the network topology and the network code that is being used.
To conclude this section, we introduce here some of the notation that will be used in the remainder of the paper. The symbol transmitted by a node in time slot is denoted by . If transmits more than one symbol in time slot , these will be distinguished by a superscript, giving, for instance, and . Nodes are represented by vectors. Given vectors and , let , , and .
Unicast sessions are denoted by , with being an integer and a vector. We will see in Sections 4 and 5 that defines the location of the source and the relative location of the destination, that is, the direction of the session. In some cases will be denoted as or similar forms. The th source symbol of a session is denoted by . The source and destination of session are denoted by and , respectively.
3. Results
We provide lower bounds on and .
Theorem 1.
The ratio of the minimum energy consumption of routing solutions and the minimum energy consumption of network coding solutions, maximized over all node locations, multiple unicast sessions, and transmission ranges, with the transmission range equal for the routing and network coding solutions, is at least , that is,
(4)
The result states that is at least , , and for -, - and -dimensional networks, respectively. The result that is at least in one-dimensional networks also follows from the results in [20]. The lower bound for -dimensional networks exceeds the previously known bound of [21]. This new lower bound is of particular interest, since it exceeds the upper bound of for decode-and-recombine type network codes [26]. Indeed, the code that we construct does not follow a decode-and-recombine strategy. This shows that energy can be saved by considering strategies other than decode-and-recombine. No lower bounds for three-dimensional networks have been previously established.
Before proving Theorem 1 in Section 5, we provide some intuition. The configuration used to proof Theorem 1 has nodes placed at a -dimensional rectangular lattice, connectivity and is parameterized by an integer controlling the size of the network. The network is given in Figure 1 for and . For , the result of Theorem 1 is obtained as follows. First consider the case of routing. Note, that the minimum-energy solution is to route all packets along the shortest path between source and destination. Therefore, all nodes in the interior of the network will need to transmit four times. Now, for the case of network coding, we will show in Section 5 that it is possible to construct a network code in which each node in the interior of the network is transmitting only once in each time slot. Therefore, by considering large and neglecting the energy consumption at the borders of the network, the obtained energy benefit is .
Figure 1
Configuration for which, with depicted here, is achievable. Nodes are located at integer coordinates in a -dimensional space, with connectivity given by , as depicted in (a). Unicast sessions are placed according to (b).
×
In Section 5 we will consider the general case of arbitrary . Again, the network coding solution will be such that each of the nodes in the interior of the network is transmitting only once in each time slot. In analyzing the routing solution, some care needs to the taken. Since , the number of hops that need to be taken on the shortest path between source and destination equals . By noting that the number of sessions is roughly equal to the number of nodes at the border of the network, that is, , and ignoring all transmission from nodes at the border of the network, we establish
(5)
Details of the configuration and a proof of Theorem 1 are given in Section 5.
The configuration and network code construction used for Theorem 1 are not useful for obtaining bounds on . Since , the cost per transmission in the network coding scheme is . One can verify, however, that the optimal transmission range under routing is . This requires hops per session, with the cost per transmission being equal to . Using the network code described above and the optimal routing solution at gives
(6)
which is at most , since . Note that it was already shown in [20] that and in [21] that .
By considering a different configuration, we show that .
Theorem 2.
For -dimensional wireless networks, the ratio of the minimum energy consumption of routing solutions and the minimum energy consumption of network coding solutions, maximized over all node locations and multiple unicast sessions, with the transmission range optimized individually for the routing and network coding solutions, is at least , that is,
Here we provide an intuitive explanation of this result; details of the configuration and a proof of Theorem 2 are provided in Section 4. The result is established using a multiple unicast configuration on a subset of the -dimensional hexagonal lattice as depicted in Figure 2. The minimum cost routing solution on this network follows shortest paths for all sessions and will require all nodes in the interior of the network to transmit three times in order to deliver one symbol for each session. In Section 4, we construct a network code in which each node in the interior is only transmitting once per delivered symbol. By making the size of the network large, the influence of the borders becomes negligible. Hence, the energy benefit is .
Figure 2
Configuration for which is achievable. Nodes are a subset of the hexagonal lattice, with connectivity as depicted in (a). Unicast sessions are placed according to (b).
×
Besides providing new lower bounds on the energy benefit of network, the network codes that are constructed in this paper are of interest by themselves. They might lead to insight in how to operate in networks with another structure. Finally, even though the case is not of any practical relevance, the bounds as well as the code constructions might lead to a better insight for lower-dimensional networks.
4. An Efficient Code on the Hexagonal Lattice
In this section, we present a multiple unicast configuration in which the nodes form a subset of the hexagonal lattice. It will be shown that the energy benefit on this configuration is , proving Theorem 2. Since the code construction used here is less involved then the construction used to prove Theorem 1, we start with the proof of Theorem 2. This section is organized as follows. In Section 4.1 we present the configuration in more detail after which we give the construction of the network code in Section 4.2. Section 4.3 is used to prove that the code is valid. Finally, in Section 4.4 we analyze the energy consumption of the network code and prove Theorem 2.
4.1. Configuration
The size of the configuration is parameterized by a positive integer . The nodes form a subset of the hexagonal lattice. We index nodes with a tuple . is given by
(7)
The location of node in is given by , where
(8)
Let denote the interior of the network, that is,
(9)
The transmission range that we are interested in is . This leads to connectivity between the six nearest neighbours. Hence, the neighbours of a node are
(10)
The nodes and the connectivity are depicted in Figure 3.
Figure 3
Nodes at a subset of the hexagonal lattice with the connectivity induced by a transmission range. The size of the network is controlled by , with in this figure.
×
There are unicast sessions, denoted by , , and , . Sources and destinations of the sessions are positioned as follows:
(11)
as depicted in Figure 4. Remember from Section 2, that session has the sequence of source symbols to be transferred.
Figure 4
The unicast sessions on the network from Figure 3.
×
4.2. Network Code
The network code is such that in each time slot a new source symbol from each session is transmitted. Also, one symbol of each session is decoded by its destination in each time slot. After successfully decoding a symbol, it is retransmitted by the destination in the next time slot. Nodes at the border will, therefore, transmit twice in each time slot. Nodes in the interior of the network transmit only once. The symbol that they transmit is a linear combination of one symbol from each of the sessions for which the shortest path between source and destination includes that node.
The operation of the network code is demonstrated in Figure 5 in which the transmissions of all nodes in the first four time slots are depicted. Different transmissions by the same node are separated by a comma. Note, moreover, that there is a startup phase, time slots to , in which not all destinations are able to decode a symbol. From time slot onwards, all destinations decode one symbol in every time slot. In analyzing the energy consumption of the coding scheme, we will ignore the startup phase.
Figure 5
Example operation of the network code of Section 4, with. The transmissions of all nodes in the time slots are depicted. Different transmissions by the same node are separated by a comma. Note, that the symbol transmitted at by the node with dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. All nodes in the interior of the network perform this simple coding operation.
×
The symbol transmitted at by the node with the dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. Indeed
(12)
This coding operation (i.e., in time slot , a node transmits the sum of what was transmitted by its top-left neighbour in time slot , by its top right-neighbour in time slot , and so forth, as visualized in Figure 5) is performed by all nodes that are in the interior of the network. The idea behind the coding operation is to cancel, by means of the XOR operation, all symbols that should not be retransmitted. In (12), for instance, we have . The exact operation of the network code is made more precise in the remainder of this subsection. The coding operation for interior nodes is given in exact form in (17).
Nodes at the border of the network operate as follows. Let . In time slot node transmits two symbols and , where
Left border:
(13)
Since is the source of session it has source symbol , available. Also, is the destination for session . It remains to be shown that symbol can be decoded by using the information obtained from its neighbours up to time slot . For notational convenience, let
Left border:
(14)
In a similar fashion, we have the following transmissions at the right and bottom borders of the network.
Right border:
(15)
Bottom border:
(16)
where , , and . Moreover, and are not symbols that are transmitted, but only notational shortcuts.
Nodes in the interior of the network transmit once in each time slot. Let . The coding operation it performs is given by
(17)
4.3. Validity of the Network Code
We need to show that destinations can decode in time in order to retransmit the required symbols according to (13), (15), and (16). In order to do so we first analyze how data propagates through the network. If we look at the nodes in the network that transmit linear combinations that contain a certain source symbol, we see that symbols propagate exactly along the shortest paths between source and destination. This is made more precise in the following two lemmas.
Lemma 1.
Let . Assume that the only nonzero source symbol transmitted in the network is by node in time slot . Then, for all and
(18)
Proof.
We use induction over time. The base case is time slot , for which it is readily verified that the statement is true. Now, for the induction step, suppose that the lemma holds for all smaller than . This implies that for all and ,
(19)
Hence,
(20)
which by the induction hypothesis is equal to if and and zero otherwise.
Lemma 2.
Let .
(21)
Proof.
From Lemma 1, the time-invariance of the system, and the symmetry of the coding operation (17) of the internal nodes.
We are now ready to prove that the destinations can correctly decode source symbols. We present the decoding procedure for nodes on the right border of the network. The decoding procedures at the other borders can be obtained by exploiting the symmetry of the system.
Lemma 3.
Consider , with , , that is, the destination of session . It can decode symbol at the end of time slot as
(22)
Proof.
From Lemma 2, (15), it follows that (22) equals
(23)
4.4. Energy Consumption
The energy consumption of the network coding scheme presented above is given in the following lemma.
Lemma 4.
.
Proof.
From (13)–(17), we have that each of the nodes at the border that are source or destination are transmitting twice in each time slot. Each of the internal nodes is transmitting once in each time slot. Since , the energy consumption per transmission is . This gives
(24)
Next, we give the minimum energy required by a routing solution.
Lemma 5.
.
Proof.
Since we consider routing, we need to take the shortest path for each session. Since the energy consumption per hop equals , the energy consumption under routing is minimized for . Now, we see that the number of transmissions required to deliver a symbol for the sessions equals . Adding the transmissions for sessions of type and gives
(25)
Using the above two lemmas, we are able to prove Theorem 2.
Proof of Theorem 2.
Remember that is defined as the maximum of over and . Hence, for any specific and will provide a lower bound to . In addition, any upper bound to will result in a lower bound to . Hence, from Lemmas 4 and 5, we have
(26)
5. An Efficient Code on the -Dimensional Rectangular Lattice
In this section, we present a multiple unicast configuration in which the nodes are placed at integer coordinates in a -dimensional space, that is, at the rectangular lattice.
5.1. Configuration
The size of the configuration is parameterized by a positive integer . We have
(27)
The interior of the network is given by
(28)
We will make use of
(29)
which corresponds to those nodes that are part of exactly one face of the network.
The transmission range that will be used is . This transmission range induces a neighbourhood consisting of all neighbours within distance . The coding operation of our network code is based on only part of the neighbourhood, that is, it uses
(30)
Note, that for , corresponds to the complete neighbourhood of . We will be using , that is, denotes the Manhattan distance from to . The network and its connectivity are depicted for in Figure 6.
Figure 6
Nodes at a subset of the-dimensional rectangular lattice, depicted in the figure, with the connectivity induced by a transmission range . The size of the network is controlled by , with in this figure.
×
A source is located at each . Therefore, there are sessions. If , we denote the session corresponding to this source by . Recall from Section 2 that denotes the dimensional vector obtained by removing the th element from . If , we denote the session by . The destination of each session is located at the other side of the network, that is, we have and . The positions of sources and destinations are depicted for in Figure 7. It can be seen that and form oppositely directed sessions.
Figure 7
The unicast sessions on the network from Figure 6.
×
5.2. Network Code
We introduce sets , , which are defined recursively as follows:
(31)
where denotes symmetric difference and . Note that irrespective of we have . As an example for we have , and .
The scheme is very similar in flavour to the scheme presented in Section 4; its operation is demonstrated in Figure 8 in which, for and , the transmissions of all nodes in the first four time slots are depicted. The operation of the scheme is such that in time slot sources transmit the th source symbol and destinations decode the th source symbol. Besides transmitting a new source symbol in each time slot, sources/destinations will also retransmit the symbol that has been decoded in that time slot, that is, they transmit two different symbols in each time slot. In the figure, different transmissions by the same node are separated by a comma. Nodes in the interior of the network transmit only once. The symbol that they transmit is a linear combination of one symbol from each of the sessions for which the shortest path between source and destination includes that node. The symbol transmitted at by the node with the dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. This coding operation is performed by all nodes that are in the interior of the network. The exact operation of the network code is made more precise in the remainder of this subsection. The coding operation for interior nodes is given in exact form in (34).
Figure 8
Example operation of the network code of Section 5, with. The transmissions of all nodes in the time slots are depicted. Different transmissions by the same node are separated by a comma. Note, that the symbol transmitted at by the node with dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. All nodes in the interior of the network perform this simple coding operation.
×
Let node . Remember that implies that there exists a unique such that . Node transmits
(32)
For notational convenience, let
(33)
The coding operation performed by an internal node is as follows:
(34)
5.3. Validity of the Network Code
The following result follows directly from the definition of the sets , but is stated here as a lemma because of its importance in the remainder of the paper.
Lemma 6.
Let be a sequence of symbols from and let . We have
(35)
Lemma 7.
Consider node . Assume that the only nonzero source symbol transmitted in the network is by node in time slot . Then
(36)
for all and .
Proof.
We use induction over . At time the lemma holds, giving us our base case. Now suppose that the lemma holds for all time slots smaller than . If , the lemma follows directly from (32)–(33). In the remainder we consider . From the induction hypothesis, it follows that for any
(37)
If , it follows from (32) and the induction hypothesis that
(38)
Now, at the coding operation performed by can be decomposed as
(39)
where
(40)
In the remainder, we show that
(41)
which proves the lemma, since by the induction hypothesis if and zero otherwise.
For we, have
(42)
where the second equality follows from Lemma 6, the third equality follows from (37)-(38), and the last equality holds because we work over .
For , we have
(43)
Lemma 8.
Let
(44)
Proof.
By linearity, time-invariance and symmetry of (34) together with Lemma 7.
We are now ready to prove that the destinations can correctly decode source symbols. We present the decoding procedure for nodes on the right border of the network, that is, for nodes of type . The decoding procedures at the other borders can be obtained by exploiting the symmetry of the system.
Lemma 9.
Consider node . At the end of time slot , it can decode symbol as
(45)
Proof.
First note that all terms in (45) correspond to symbols that have been received by before or in time slot .
Now, from Lemma 8, we have
(46)
where holds, because for , Lemma 6 gives
(47)
and
(48)
From (32) it follows that
(49)
and
(50)
The proof of the lemma follows by adding the final expressions from (46), (49) and (50) observing that the outcome is .
5.4. Energy Consumption
The energy consumption of the network coding scheme presented above provides an upper bound to .
Lemma 10.
.
Proof.
All transmissions are over distance and cost . The nodes in are transmitting twice. On each of the sides of the network, there are nodes from ; hence . This gives transmissions. In addition, there are nodes in the interior, that are all transmitting once.
Next, we give the minimum energy required by a routing solution.
Lemma 11.
.
Proof.
Since the transmission range is equal to , a routing solution requires transmissions per session. Moreover, there are sessions.
Using the above two lemmas, we are able to prove Theorem 1.
Proof of Theorem 1.
Lemmas 10 and 11 give
(51)
6. Discussion
We have given several constructions of energy-efficient network codes. These constructions serve to show that compared to plain routing, network coding has the potential of reducing energy consumption in wireless networks. Since we have provided only codes that are based on a centralized design, it remains to be shown in future work if and how this potential can be exploited using practical codes. Moreover, it would also be of interest to consider the energy-benefit in topologies in which the nodes are not positioned at a lattice, for instance, random networks.
In this work we have provided lower bounds on the energy benefit of network coding for wireless multiple unicast. Another open problem is to find upper bounds on the benefit.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
and obtain a new bound of
.
be the nodes of a
-dimensional wireless network. We consider a wireless network model with broadcast, where all nodes within range
of a transmitting node can receive, and nodes outside this range cannot. More precisely, given a transmission range
, a node
is broadcasting to all nodes in the set
denotes the Euclidean norm of
. The energy required to transmit one unit of information to all other nodes within range
equals
, where
is the path loss exponent and
is some constant. In analyzing the energy consumption of nodes, we will consider only the energy consumed by transmitting. Receiver energy consumption as well as energy consumed by processing are assumed to be negligible compared to transmitter energy consumption. In particular, note that little additional processing is required for network coding, compared to the processing that is performed in a traditional wireless protocol stack.
, that is, they are bits and addition corresponds to the xor operation. The source of each unicast session has a sequence of source symbols that need to be delivered to the corresponding destination. Let
be the set of unicast sessions. We call
a wireless multiple unicast configuration.
and
be the minimum energy required for network coding and routing solutions, respectively, for a configuration
. The energy consumption of a coding or routing scheme is defined as the time-average of the total energy spent by all nodes in the network to deliver one symbol for each unicast session. In analyzing coding schemes, we will ignore the energy consumption in an initial startup phase and consider only steady-state behavior.
, the transmission range
is an important factor in the energy consumption. Therefore, it is of particular interest to optimize the transmission range such that energy consumption is minimized. In this work, we consider two different quantities: (
)
, denoting the energy benefit that can be obtained if the transmission range is given and fixed and (
)
, denoting the energy benefit that can be obtained if one is allowed to optimize the transmission range. Note that the transmission range can be individually optimized for the routing and network coding scenarios. More precisely, the goal of this work is to establish lower bounds on
, multiple unicast sessions
, and transmission ranges
, with the transmission range equal for the routing and network coding solutions, and
and multiple unicast sessions
, with the transmission range being optimized individually for the routing and network coding solutions. If no confusion can arise, we will omit dependency on
in the notation for
and
.
,
is equal for
and
, the energy per transmission is equal in
and
and the benefit is equal to the ratio of the number of transmissions required in routing and network coding solutions.
in time slot
is denoted by
. If
transmits more than one symbol in time slot
, these will be distinguished by a superscript, giving, for instance,
and
. Nodes are represented by vectors. Given vectors
and
, let
,
, and
.
, with
being an integer and
a vector. We will see in Sections 4 and 5 that
defines the location of the source and
the relative location of the destination, that is, the direction of the session. In some cases
will be denoted as
or similar forms. The
th source symbol of a session
is denoted by
. The source and destination of session
are denoted by
and
, respectively.
and
.
, that is,
is at least
,
, and
for
-,
- and
-dimensional networks, respectively. The result that
is at least
in one-dimensional networks also follows from the results in [20]. The lower bound
for
-dimensional networks exceeds the previously known bound of
[21]. This new lower bound is of particular interest, since it exceeds the upper bound of
for decode-and-recombine type network codes [26]. Indeed, the code that we construct does not follow a decode-and-recombine strategy. This shows that energy can be saved by considering strategies other than decode-and-recombine. No lower bounds for three-dimensional networks have been previously established.
-dimensional rectangular lattice, connectivity
and is parameterized by an integer
controlling the size of the network. The network is given in Figure 1 for
and
. For
, the result of Theorem 1 is obtained as follows. First consider the case of routing. Note, that the minimum-energy solution is to route all packets along the shortest path between source and destination. Therefore, all nodes in the interior of the network will need to transmit four times. Now, for the case of network coding, we will show in Section 5 that it is possible to construct a network code in which each node in the interior of the network is transmitting only once in each time slot. Therefore, by considering large
and neglecting the energy consumption at the borders of the network, the obtained energy benefit is
.
, with
depicted here, is achievable. Nodes are located at integer coordinates in a
-dimensional space, with connectivity given by
, as depicted in (a). Unicast sessions are placed according to (b).
. Again, the network coding solution will be such that each of the
nodes in the interior of the network is transmitting only once in each time slot. In analyzing the routing solution, some care needs to the taken. Since
, the number of hops that need to be taken on the shortest path between source and destination equals
. By noting that the number of sessions is roughly equal to the number of nodes at the border of the network, that is,
, and ignoring all transmission from nodes at the border of the network, we establish
. Since
, the cost per transmission in the network coding scheme is
. One can verify, however, that the optimal transmission range under routing is
. This requires
hops per session, with the cost per transmission being equal to
. Using the network code described above and the optimal routing solution at
gives
.
-dimensional wireless networks, the ratio of the minimum energy consumption of routing solutions and the minimum energy consumption of network coding solutions, maximized over all node locations and multiple unicast sessions, with the transmission range optimized individually for the routing and network coding solutions, is at least
, that is,
-dimensional hexagonal lattice as depicted in Figure 2. The minimum cost routing solution on this network follows shortest paths for all sessions and will require all nodes in the interior of the network to transmit three times in order to deliver one symbol for each session. In Section 4, we construct a network code in which each node in the interior is only transmitting once per delivered symbol. By making the size of the network large, the influence of the borders becomes negligible. Hence, the energy benefit is
.
is achievable. Nodes are a subset of the hexagonal lattice, with connectivity as depicted in (a). Unicast sessions are placed according to (b).
is not of any practical relevance, the bounds as well as the code constructions might lead to a better insight for lower-dimensional networks.
, proving Theorem 2. Since the code construction used here is less involved then the construction used to prove Theorem 1, we start with the proof of Theorem 2. This section is organized as follows. In Section 4.1 we present the configuration in more detail after which we give the construction of the network code in Section 4.2. Section 4.3 is used to prove that the code is valid. Finally, in Section 4.4 we analyze the energy consumption of the network code and prove Theorem 2.
. The nodes
form a subset of the hexagonal lattice. We index nodes with a tuple
.
is given by
in
is given by
, where
denote the interior of the network, that is,
. This leads to connectivity between the six nearest neighbours. Hence, the neighbours of a node
are
and the connectivity are depicted in Figure 3.
. The size of the network is controlled by
, with
in this figure.
unicast sessions, denoted by
,
, and
,
. Sources and destinations of the sessions are positioned as follows:
to
, in which not all destinations are able to decode a symbol. From time slot
onwards, all destinations decode one symbol in every time slot. In analyzing the energy consumption of the coding scheme, we will ignore the startup phase.
. The transmissions of all nodes in the time slots
are depicted. Different transmissions by the same node are separated by a comma. Note, that the symbol transmitted at
by the node with dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. All nodes in the interior of the network perform this simple coding operation.
by the node with the dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. Indeed
, a node transmits the sum of what was transmitted by its top-left neighbour in time slot
, by its top right-neighbour in time slot
, and so forth, as visualized in Figure 5) is performed by all nodes that are in the interior of the network. The idea behind the coding operation is to cancel, by means of the XOR operation, all symbols that should not be retransmitted. In (12), for instance, we have
. The exact operation of the network code is made more precise in the remainder of this subsection. The coding operation for interior nodes is given in exact form in (17).
. In time slot
node
transmits two symbols
and
, where
Left border:
is the source of session
it has source symbol
, available. Also,
is the destination for session
. It remains to be shown that symbol
can be decoded by
using the information obtained from its neighbours up to time slot
. For notational convenience, let
Left border:
Right border:
Bottom border:
,
, and
. Moreover,
and
are not symbols that are transmitted, but only notational shortcuts.
. The coding operation it performs is given by
. Assume that the only nonzero source symbol transmitted in the network is
by node
in time slot
. Then, for all
and
, for which it is readily verified that the statement is true. Now, for the induction step, suppose that the lemma holds for all
smaller than
. This implies that for all
and
,
if
and
and zero otherwise.
.
, with
,
, that is, the destination of session
. It can decode symbol
at the end of time slot
as
.
nodes at the border that are source or destination are transmitting twice in each time slot. Each of the
internal nodes is transmitting once in each time slot. Since
, the energy consumption per transmission is
. This gives
.
, the energy consumption under routing is minimized for
. Now, we see that the number of transmissions required to deliver a symbol for the sessions
equals
. Adding the transmissions for sessions of type
and
gives
is defined as the maximum of
over
and
. Hence,
for any specific
and
will provide a lower bound to
. In addition, any upper bound to
will result in a lower bound to
. Hence, from Lemmas 4 and 5, we have
-Dimensional Rectangular Lattice
-dimensional space, that is, at the rectangular lattice.
. We have
. This transmission range induces a neighbourhood consisting of all neighbours within distance
. The coding operation of our network code is based on only part of the neighbourhood, that is, it uses
,
corresponds to the complete neighbourhood of
. We will be using
, that is,
denotes the Manhattan distance from
to
. The network and its connectivity are depicted for
in Figure 6.
-dimensional rectangular lattice,
depicted in the figure, with the connectivity induced by a transmission range
. The size of the network is controlled by
, with
in this figure.
. Therefore, there are
sessions. If
, we denote the session corresponding to this source by
. Recall from Section 2 that
denotes the
dimensional vector obtained by removing the
th element from
. If
, we denote the session by
. The destination of each session is located at the other side of the network, that is, we have
and
. The positions of sources and destinations are depicted for
in Figure 7. It can be seen that
and
form oppositely directed sessions.
,
, which are defined recursively as follows:
denotes symmetric difference and
. Note that irrespective of
we have
. As an example for
we have
,
and
.
and
, the transmissions of all nodes in the first four time slots are depicted. The operation of the scheme is such that in time slot
sources transmit the
th source symbol and destinations decode the
th source symbol. Besides transmitting a new source symbol in each time slot, sources/destinations will also retransmit the symbol that has been decoded in that time slot, that is, they transmit two different symbols in each time slot. In the figure, different transmissions by the same node are separated by a comma. Nodes in the interior of the network transmit only once. The symbol that they transmit is a linear combination of one symbol from each of the sessions for which the shortest path between source and destination includes that node. The symbol transmitted at
by the node with the dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. This coding operation is performed by all nodes that are in the interior of the network. The exact operation of the network code is made more precise in the remainder of this subsection. The coding operation for interior nodes is given in exact form in (34).
. The transmissions of all nodes in the time slots
are depicted. Different transmissions by the same node are separated by a comma. Note, that the symbol transmitted at
by the node with dotted border can be obtained by summing all transmissions from nodes with a dashed border in earlier time slots. All nodes in the interior of the network perform this simple coding operation.
. Remember that
implies that there exists a unique
such that
. Node
transmits
, but is stated here as a lemma because of its importance in the remainder of the paper.
be a sequence of symbols from
and let
. We have
. Assume that the only nonzero source symbol transmitted in the network is
by node
in time slot
. Then
and
.
. At time
the lemma holds, giving us our base case. Now suppose that the lemma holds for all time slots smaller than
. If
, the lemma follows directly from (32)–(33). In the remainder we consider
. From the induction hypothesis, it follows that for any
, it follows from (32) and the induction hypothesis that
the coding operation performed by
can be decomposed as
if
and zero otherwise.
we, have
.
, we have
. The decoding procedures at the other borders can be obtained by exploiting the symmetry of the system.
. At the end of time slot
, it can decode symbol
as
before or in time slot
.
holds, because for
, Lemma 6 gives
.
.
.
and cost
. The nodes in
are transmitting twice. On each of the
sides of the network, there are
nodes from
; hence
. This gives
transmissions. In addition, there are
nodes in the interior, that are all transmitting once.
.
, a routing solution requires
transmissions per session. Moreover, there are
sessions.