Network Coded Wireless Cooperative Multicast with Minimum Transmission Cost

Abstract

We study multicasting over wireless lossy links. Instead of downloading all the data from the source node, we allow the destination nodes themselves to locally exchange the packets, as local communication within a cluster achieves higher packet reception probability with less transmission cost. However, when shall we stop the transmission from the source node? If the source stops too early, the destination nodes locally cannot reconstruct all the original packets, while if the source stops too late, the benefit of cooperative data exchange cannot be fully exploited. In this paper, we propose a network coded hybrid source and cooperative exchange scheme to determine when to stop the source sending and start the exchange process, so as to minimize the total transmission cost. For the case when the clusters are predefined, we derive the expected total transmission cost with our hybrid scheme. Our theoretical results show that under a special condition, the source node should keep sending the packets until all the destinations get the complete information. For the case when the clusters are not predefined, we propose a cluster division algorithm such that the destination nodes within each cluster can conduct data exchange locally with energy efficiency. Finally, simulation results demonstrate the effectiveness of the proposed scheme.

1. Introduction

Over the past decades, wireless sensor networks have attracted a great deal of research attentions [1–3]. Once deployed, sensors are expected to operate for a long period of time, and it is impractical to reach these sensors physically. However, it is quite often necessary to update the software running on those sensors or add new functionalities to the sensors [4, 5], which needs to reliably multicast large data objects with energy efficiency [5, 6]. Particularly, in wireless lossy sensor networks, multicasting packets from a single source node is still a challenge problem due to the heterogeneous lossy links to the destination nodes. To satisfy all the destination nodes, the source node needs to keep sending until the destination node with the worst packet reception link successfully receives all the packets, which is inefficient for the source node.

Recently, cooperative data exchange [7–11] has become a promising approach to achieve the efficient data communications. Instead of downloading all the packets from the source node (e.g., the server) [12, 13], cooperative data exchange allows the destination nodes to cooperatively exchange their received packets among themselves, once the destination nodes collectively hold all the packets. Compared with pure source-dominated multicast, cooperative data exchange has two main benefits: (a) short-range communication among destination nodes is often more reliable and consumes less transmission cost, (b) the bandwidth saved at the source node can serve more other nodes in the system.

However, most of the existing works on cooperative data exchange problem never consider when to stop downloading the data from the source node. On the one hand, if the source node stops too early, the destination nodes themselves may be unable to collectively reconstruct the complete packets. On the other hand, if the source node stops too late, the benefit of cooperative data exchange cannot be fully utilized. In addition, although the average transmission cost with cooperative data exchange is lower than with source transmission, the sum of the transmission costs within multiple clusters may exceed the cost with pure source sending. To sum up, for wireless multicasting, it is important for us to consider when to stop the source sending and start the cooperative data exchange, so as to reduce the total transmission cost or energy consumption [1–3, 14, 15].

So far, only the work in [16] studies the hybrid source transmission and cooperative data exchange for wireless multicasting, and it stops the source sending exactly once the destination nodes within each cluster collectively hold the complete information. Although the scheme in [16] performs well in reducing the transmission delay, it is still possible that the cooperative data exchange by multiple clusters may consume more transmission cost/energy than source-dominated scheme. As discussed above, the cooperative data exchange needs to be conducted separately in each cluster, and thus the sum of their transmission costs may exceed the transmission cost with pure source transmission. In addition, the predefined clusters in [16] might not perform well, as the destination nodes in some clusters may collect the complete information more quickly than the destinations in other clusters, which may stop the source transmission too late for the other clusters.

Recent work also shows that network coding [17–19] can improve the network throughput and reliability, especially for wireless lossy networks. Instead of sending/forwarding the original packets directly, network coding allows the source/transmitting node to linearly combine multiple packets together. With this approach, each transmitted packet has almost the same contribution in reconstructing the original packets, and hence improves wireless reliability [20]. Considering the benefits of network coding, we assume that the packets sent from the source node or the packets exchanged among the destination nodes are all linear encoded at the source/transmitting nodes before sending.

In this paper, given the heterogeneous link loss probability and the transmission cost of the source transmission and data exchange among the destinations, we aim to design a hybrid source and cooperative data exchange scheme to minimize the total transmission cost consumed during multicasting. For the case when the clusters are predefined, we determine when the source should stop sending the packets to the destination nodes and the cooperative data exchange should start. For the case when the clusters are not predefined, we consider how to divide the destinations into the clusters. The main contribution of the paper can be concluded as follows. (i)

We theoretically derive the expected total transmission cost required with traditional source-dominated scheme and our hybrid transmission scheme.

(ii)

Our analysis shows that under a special condition, the source node should keep sending the packets until all the destinations get the complete information, so as to reduce the total transmission cost.

(iii)

We also propose an efficient algorithm to determine how to group the destination nodes into the clusters, so as to make sure that the destination nodes within each cluster can collectively recover all the original packets with energy efficiency.

(iv)

We compare the performance of the proposed scheme with some existing schemes. Simulation results show that the proposed scheme can significantly reduce the total transmission cost.

The rest of the papers are organized as follows. In Section 2, we introduce the background and some related works. The system model and the problem description are presented in Section 3. The expected total transmission costs with source-dominated and our scheme are discussed in Section 4. In Section 5, we consider how to group the destinations into clusters after receiving the sufficient number of packets from the source. The simulation results are presented in Section 6. We conclude the paper in Section 7.

2. Background and Related Work

In this section, we provide a brief introduction to the existing wireless network coded multicast scheme and summarize some related works.

2.1. Wireless Network Coding

Network coding was originally proposed in information theory [17] and recently has become a promising approach to improve the network performance in throughput [21, 22], reliability [19, 23], security [18, 24], and so forth. Instead of forwarding the original packets directly, network coding allows the source node/intermediate node to combine multiple packets together before sending it out. The work in [25] ensures that all the encoded packets generated by the same peer are linearly independent with a high probability, if we use linear network coding based on a sufficient large field size.

Network coding in wireless lossy networks was also considered in the literature. The work in [21] proposed a first wireless network coding architecture, named COPE. By exploiting the broadcast nature of wireless medium, each node stores the overheard packets for a while. When a node transmits a packet, it uses its knowledge of what its neighbors have overheard to perform opportunistic coding [21, 22]. After receiving an encoded packet, multiple neighbors can decode their wanted packets with their overheard packets. In other words, the sender or transmitting node can deliver “multiple packets” to different neighbors in a single transmission, which thus improves the throughput. The work in [19, 23] theoretically shows that network coding significantly reduces the expected number of retransmissions in lossy networks compared to traditional ARQ scheme. The work in [5] considers the impact of both wireless unreliable communication and sleep scheduling of sensor nodes and proposes a deterministic code design at the source node so as to accomplish the data dissemination process at the earliest time.

2.2. Reliable Multicast in Lossy Wireless Networks

Traditionally, wireless single-hop multicast mainly focuses on source-dominated transmission, where the source node keeps sending the packets until all the destination nodes in the system obtain the complete information. However, the performance of such a source-dominated transmission degrades significantly when the packet reception probabilities of the destination nodes are heterogeneous. In this case, the source node cannot stop sending the packets until the destination node with the worst link state successfully gets the packets, even if all the other destination nodes received the packets in a much earlier time.

Recently, cooperative data exchange [7] among the users (e.g., mobile users) becomes one of the most promising approaches in designing efficient data transmissions. In cooperative data exchange, each client initially holds a subset of the packets and wants all the packets that others have. In the literature, it is assumed that there is a common communication channel among the users to receive/send the packets from/to all other users. Cooperative data exchange is to make sure that each client finally can get the complete packets by exchanging packets among themselves through the common channel. Compared with source-dominated transmissions, cooperative data exchange appears ti have two benefits: (1) short-range communications among the users are often more reliable and faster, (2) the bandwidth saved at the server can serve more other clients in the system.

Most recent works on cooperative data exchange mainly focus on how to minimize the total number of packets to be exchanged/transmitted among the users [7–9], or the total transmission cost consumed at the users [10, 11], such that all the users in the system can finally recover/receive the complete packets. Current works also show that network coding can reduce the number of transmissions or the total transmission cost required for cooperative data exchange process [7–11].

However, in the literature, most of the works either focus on pure source-dominated multicast or focus on cooperative data exchange by assuming that each user initially holds a subset of packets. The only work that considers the hybrid architecture of source transmission and data exchange transmission is in [16]. Specifically, the source node is set to stop sending the packets once the destinations in each cluster can collectively reconstruct the original packets, followed by the cooperative data exchange within each cluster. The numerical results show that with this hybrid transmission, the transmission delay of the multicast can be reduced compared with pure source-dominated multicast. However, the source node may stop too early, as the sum of the energy consumed by the cooperative data exchange within multiple clusters may consume more energy, which is inefficient for wireless sensor networks.

3. System Model and Problem Description

In this section, we first introduce the system model of our problem. Then, we discuss the problem to be solved in two different cases: with predefined clusters and without predefined clusters.

3.1. System Model

In this paper, we consider a multicast application, where a source node s needs to send n packets to m destination nodes in $D = {d_{1}, d_{2}, \dots, d_{m}}$ . Before transmitting the packets, the source node may generate more than n encoded packets over the original n packets. It is typical to assume that with network coding, after receiving any n encoded packets, the destination node can recover the original n packets.

Suppose that the destination nodes are formed into multiple clusters in $𝒞 = {C_{1}, C_{2}, \dots}$ , where $C_{k} \in 𝒞$ denotes the set of destination nodes in cluster k. Without loss of generality, we assume that each pair of clusters maintain disjoint destination nodes, that is, $C_{k_{1}} ⋂_{} ‍ C_{k_{2}} = \emptyset, for all k_{1} \neq k_{2}$ and $⋃_{C_{k} \in 𝒞} ‍ C_{k} = D$ . As in cooperative data exchange, we assume that local data exchange within each cluster is conducted through a common channel.

Our multicasting process consists of two transmission stages. In the first stage, the source node sends the packets to all the destination nodes in D. In the second stage, the destination nodes within the same cluster perform the cooperative data exchange among themselves. These two stages need to make sure that each destination finally can reconstruct the original n packets. Due to unreliable wireless communications, suppose that the packet loss probability from the source node to every destination node is $l_{s}$ , and the packet loss probability between the destination nodes in cluster $C_{k}$ is $l_{k}$ . We also assume that the transmission cost of the source node is $t_{s}$ , and the transmission cost for the data exchange within cluster $C_{k}$ is $t (C_{k})$ . Without loss of generality, we assume that the transmission cost of the source node is higher than the transmission cost of the destination node, that is, $t_{s} \geq t_{C_{k}}$ for $\forall k$ , and the reception probability of the packet sent from s is lower than the reception probability of the packet exchanged within the same cluster, that is, $l_{s} \geq l_{k}$ .

In this paper, we aim to minimize the total transmission cost consumed during transmissions, while we ensure that all the destination nodes in D can successfully reconstruct the original n packets. Let $x_{h s}$ be the number of packets that the source node sends, and $x_{k}$ be the number of packets sent by the destination nodes within the cluster $C_{k}$ . Thus, the total transmission cost can be written as

\begin{matrix} x_{h s} t_{s} + \sum_{c_{k} \in 𝒞}^{} x_{k} t (C_{k}) \end{matrix}

(1)

which needs to be minimized.

An example of the system model is shown in Figure 1. The source node s needs to send three packets to the destinations in $D = {d_{1}, d_{2}, \dots, d_{7}}$ , and the original packets are generated into three encoded packets $p_{1}, p_{2}$ , and $p_{3}$ . The set of the packets received at each destination is given near the node after the source node sends three packets $p_{1}, p_{2}, p_{3}$ , for example, the set of packets received by node $d_{4}$ is ${p_{3}}$ . In the next subsections, we will discuss the problems to be considered in this example.

Figure 1

An example of system model after sending three packets in ${p_{1}, p_{2}, p_{3}}$ from source node s to receiver nodes in $D = {d_{1}, d_{2}, \dots, d_{7}}$ .

3.2. Problem Description with Predefined Clusters

In this section, we consider the case when the destination nodes in each cluster are predetermined.

Due to unreliable wireless communications, some packets may be lost at some destination nodes. So, one challenge problem is to determine when the source node s stops sending the packets such that the destination nodes within each cluster can exchange the packets among themselves, and the total transmission cost defined in (1) is minimum. (i)

If the source node s stops too early, the destination nodes in some clusters may be unable to collectively recover all the original packets.

(ii)

If the source node s stops too late, the low-cost transmission among the destination nodes themselves cannot be fully utilized, which may incur high transmission cost because of high packet loss probability and high transmission cost of the source transmission.

(iii)

The sum of the transmission costs by the data exchange by all the clusters may exceed the transmission cost by the pure source transmission. In this case, the source node should keep sending until all the destination nodes obtain the complete information.

As shown in Figure 1, if the source node s stops after sending $p_{1}, p_{2}, p_{3}$ , the destination nodes in the left cluster (within a circle) cannot collectively reconstruct the original three packets. On contrary, if the source node s sends too many packets, all the destination nodes within each cluster may obtain the complete packets, which does not utilize the low-cost cooperative data exchange. However, if the sum of the transmission costs in these two clusters are higher than the transmission cost from the source node, it is better to let the source node keep sending until all the destination nodes get the complete information.

We refer to the above problem of determining when to stop the source transmission, as minimizing the multicast transmission cost problem with predefined clusters.

3.3. Problem Description with Nonpredefined Clusters

In the above section, we assume that the destination nodes in each cluster are given. However, the predefined clusters may not perform well, as the destination nodes in some clusters may collectively hold the complete information much later than the destination nodes in other clusters, which thus delays the starting time of the cooperative data exchange in other clusters.

Still take Figure 1 as an example, if we group the destinations in ${d_{1}, d_{2}, \dots, d_{7}}$ into two clusters, that is, the destinations in the same circle belong to the same cluster. After the source node s sends three packets $p_{1}, p_{2}, p_{3}$ , the destination nodes in the left cluster cannot recover the original packets, as they collectively have received only two packets so far. However, if we move destination node $d_{4}$ into the left cluster, the destination nodes in both clusters can reconstruct all the three original packets, and then s can stop sending the packets.

Thus, after the source node sends sufficient number of packets, we need to consider how to group the destination nodes into multiple clusters such that the destination nodes within each cluster collectively can reconstruct the original packets with energy efficiency. In this case, the number of clusters in 𝒞 and the set of the destinations in each cluster $C_{k}$ need to be determined by our algorithm.

4. Minimum Multicast Transmission Cost with Predefined Clusters

In this section, we consider the case when the clusters are predefined. We first analyze the expected total transmission costs with source-dominated scheme and our hybrid transmission scheme. We then formulate the problem of minimizing the total transmission cost with our hybrid transmission scheme as an integer programming.

To ease the understanding, the main notations used in the paper are given in Table 1.

Table 1

Main notations and their descriptions.

𝒞	The set of the clusters
$C_{k}$	The kth cluster in 𝒞
D	The set of the destination nodes in the system
$d_{i}$	The ith destination node in D
$l_{s}$	Packet loss probability on the link from s to each destination
$l_{k}$	Packet loss probability of the data exchange within cluster $C_{k}$
m	The total number of destination nodes in D
n	The total number of original packets
s	The source node
$t_{s}$	The transmission cost of the source node s
$t (C_{k})$	The transmission cost of the data exchange within cluster $C_{k}$
$x_{h s}$	Number of packets sent by s in the first stage of hybrid scheme
$x_{k}$	The number of packets exchanged within cluster $C_{k}$

4.1. Transmission Cost with Source-Dominated Transmission

With source-dominated scheme, the source node s keeps sending the encoded packets that are generated based on n original packets, until all the destination nodes in D successfully decode the original n packets. With linear network coding, after receiving any n encoded packets from s, the destination node can decode the original n packets.

Suppose that $\bar{x_{s}}$ is the expected transmission cost required with the source-dominated scheme. To make sure all the destinations can recover the complete packets, the number of packets that s sends should be at least the maximum number of packets to be sent to satisfy the decoding requirement of each destination. That is

\begin{matrix} \bar{x_{s}} = \max {\bar{x_{1}^{'}}, \bar{x_{2}^{'}}, \dots, \bar{x_{m}^{'}}}, \end{matrix}

(2)

where

\bar{x_{i}^{'}}

means the expected number of packets required to be sent by s, so as to guarantee that destination

d_{i}

can decode all the n original packets. Since the packet loss probability from s to each destination node is

l_{s}

, we can derive

\bar{x_{i}^{'}}

as follows:

\begin{matrix} \bar{x_{i}^{'}} = \frac{n}{1 - l_{s}} . \end{matrix}

(3)

In other words, we have

\begin{matrix} \bar{x_{s}} = \max {\bar{x_{i}^{'}} ∣ \forall i} = \frac{n}{1 - l_{s}} . \end{matrix}

(4)

With the above equations, we can obtain the expected transmission cost as follows:

\begin{matrix} \bar{x_{s}} t_{s} = \frac{n t_{s}}{1 - l_{s}} . \end{matrix}

(5)

4.2. Transmission Cost with Hybrid Transmission Scheme

With hybrid transmission scheme, there are two stages. In the first stage, the source node s sends $x_{h s}$ encoded packets. In the second stage, the destination nodes in the same cluster cooperatively exchange the packets that they received before, until each of them can decode all the packets.

We now consider the first stage. For the success of the second stage, the number of packets sent by the source s should make sure that the destination nodes within each cluster can collectively reconstruct all the original packets. The probability that at least one of the destinations in cluster $C_{k}$ can receive the current transmission is $1 - l_{k}^{| C_{k} |}$ . Thus, to guarantee at least n transmissions of the packets are successfully received by the collection of the destination nodes in $C_{k}$ , the expected number of packets sent by the source node s, denoted as $\bar{x_{h s}}$ , should satisfy the following condition:

\begin{matrix} \bar{x_{h s}} \geq \frac{n}{1 - l_{k}^{| C_{k} |}} . \end{matrix}

(6)

When considering all the clusters, (6) can be written as

\begin{matrix} \bar{x_{h s}} \geq {\max_{}}_{C_{k} \in 𝒞} {\frac{n}{1 - l_{k}^{| C_{k} |}}} . \end{matrix}

(7)

Note that if we set

\bar{x_{h s}} = \min_{C_{k} \in 𝒞} {n / (1 - l_{k}^{| C_{k} |})}

, it means the source node s stops sending the packets exactly once the destination nodes in each cluster collectively can recover the complete packets.

We then consider the second stage. After the source node sends $\bar{x_{h s}}$ packets, the expected number of packets required by each destination in cluster $C_{k}$ is

\begin{matrix} \bar{L} = n - \bar{x_{h s}} (1 - l_{s}) . \end{matrix}

(8)

Then, the expected number of packets to be sent by other destinations through cooperative data exchange, denoted as

\bar{M_{k}}

, such that one specific destination in cluster

C_{k}

can decode, is

\begin{matrix} \bar{M_{k}} = \frac{\bar{L}}{1 - l_{k}} . \end{matrix}

(9)

According to the work in [16], the expected number of packets required to be exchanged among cluster

C_{k}

such that all the destination nodes in

C_{k}

can obtain its required

\bar{M_{k}}

packets is

\begin{matrix} \bar{x_{k}} = \frac{| C_{k} |}{| C_{k} | - 1} (\bar{M_{k}} + {\bar{W}}_{| C_{k} |} \sqrt{σ_{\bar{M_{k}}}^{2}}), \end{matrix}

(10)

where

{\bar{W}}_{| C_{k} |}

is the expectation of the

| C_{k} |

-th order statistic of a sequence of

| C_{k} |

normal random variables, and

σ_{\bar{M_{k}}}^{2}

(given in [16]) is the variance of

\bar{M_{k}}

Thus, the total transmission cost with hybrid transmission scheme can be formulated as follows:

\begin{matrix} \bar{x_{h s}} t_{s} + \sum_{C_{k} \in 𝒞}^{} t (C_{k}) \bar{x_{k}} . \end{matrix}

(11)

If we assume that the packet loss probability within each cluster is the same, that is, $l_{k} = l_{r}$ for $for all C_{k} \in 𝒞$ , and the transmission cost within each cluster is also the same, that is, $t (C_{k}) = t_{r}$ for $\forall C_{k} \in 𝒞$ , we can obtain the following theorem.

Theorem 1.

If $| 𝒞 | t_{r} (1 - l_{s}) \geq t_{s} (1 - l_{r})$ , to minimize the expected total transmission cost, it is better to let the source node keep sending the packets until all the destination nodes in D successfully obtain the original n packets, that is, $x_{k} = 0$ .

Proof.

Let $\bar{x_{h s}}$ be the number of packets sent by the source node s in a hybrid transmission scheme. Since we assume that $| C | t_{r} (1 - l_{s}) \geq t_{s} (1 - l_{r})$ , we have

\begin{matrix} t_{r} \geq \frac{t_{s} (1 - l_{r})}{| C | (1 - l_{s})} . \end{matrix}

(12)

Based on the above equation (12), we then compare the expected total transmission cost required by source-dominated scheme with that by the hybrid transmission scheme for any $x_{k} > 0$ as follows:

\begin{array}{l} \bar{x_{h s}} t_{s} + \sum_{C_{k} \in 𝒞}^{} t (C_{k}) \bar{x_{k}} - \bar{x_{s}} t_{s} \\ = \bar{x_{h s}} t_{s} + \sum_{C_{k} \in 𝒞}^{} t (C_{k}) \bar{x_{k}} - \frac{n t_{s}}{1 - l_{s}} \\ \geq \bar{x_{h s}} t_{s} + | C | t_{r} \bar{M_{k}} - \frac{n t_{s}}{1 - l_{s}} \\ = \bar{x_{h s}} t_{s} + | C | t_{r} \frac{n - \bar{x_{h s}} (1 - l_{s})}{1 - l_{r}} - \frac{n t_{s}}{1 - l_{s}} \\ \geq \bar{x_{h s}} t_{s} + | C | \frac{n - \bar{x_{h s}} (1 - l_{s})}{1 - l_{r}} \frac{t_{s} (1 - l_{r})}{| C | (1 - l_{s})} - \frac{n t_{s}}{1 - l_{s}} \\ = \bar{x_{h s}} t_{s} + \frac{(n - \bar{x_{h s}} (1 - l_{s})) t_{s}}{1 - l_{s}} - \frac{n t_{s}}{1 - l_{s}} \\ = \frac{\bar{x_{h s}} t_{s} (1 - l_{s}) + (n - \bar{x_{h s}} (1 - l_{s})) t_{s} - n t_{s}}{1 - l_{s}} \\ = 0 . \end{array}

(13)

From the above equation, we can see that the expected total transmission cost with hybrid scheme is not lower than source-dominated transmission scheme when $| C | t_{r} (1 - l_{s}) \geq t_{s} (1 - l_{r})$ . In other words, to reduce the total transmission cost, the source node should keep sending until all the destination nodes can successfully decode the complete information, that is, $x_{k} = 0$ , which thus proves the theorem.

4.3. Hybrid Transmission Scheme with Minimum Total Transmission Cost

As discussed above, in some cases, the sum of the transmission costs within all the clusters may be more than transmission cost of the source transmission. Under such circumstances, the source node should keep sending the packets until all the destination nodes get the complete information, which is a special case of our hybrid scheme, that is, $x_{h s} = x_{s}$ .

To determine $x_{h s}$ , the problem of minimizing the total transmission cost with hybrid transmission scheme can be formulated as follows:

\begin{matrix} \min \bar{x_{s}} t_{s} + \sum_{C_{k} \in 𝒞} ‍ t (C_{k}) \bar{x_{k}} \end{matrix}

(14)

subject to (7).

With the above integer formulation, we can obtain the best time to stop the source transmission and start the cooperative data exchange process.

5. Cluster Determination in Cooperative Data Exchange Stage

As discussed in Section 3.3, after the source transmissions in the first stage, the destination nodes in some clusters may be unable to reconstruct the original packets if the clusters are predefined. In this section, we consider after the source node sends $x_{h s}$ packets in the first stage, where $x_{h s} \geq n$ , how to group the destination nodes into multiple clusters so as to make sure that the destination nodes in each cluster collectively can recover all the original packets.

Assume that after the source node sends $x_{h s}$ packets, the set of the packets received by destination node $d_{i}$ is denoted as $H_{i}$ , for example, $H_{6} = {p_{2}, p_{3}}$ in Figure 1. Since the total number of packets sent by the source node s in the first stage is $x_{h s}$ , we have $H_{i} \subseteq {p_{1}, p_{2}, \dots, p_{x_{h s}}}$ . Before describing how to group the clusters, we first discuss given the exact packet reception states of the destination nodes, how many transmissions are required by the data exchange process within a local cluster.

5.1. Number of Transmissions Required for Data Exchange Process within a Local Cluster

We now discuss the number of transmissions required for data exchange within a specific cluster $C_{k}$ , given the exact packet reception sets of the destination nodes in $C_{k}$ .

Without loss of generality, we assume that after the source s sends $x_{h s}$ packets, all the destination nodes in cluster $C_{k}$ collectively can recover the original n packets. As in the above section, we assume that the packets sent by the source node s are linear independent with each other, that is, after receiving any n packets from s, the node can decode the original n packets. In other words, after the first stage, the total number of packets collectively received by the destination nodes within each cluster $C_{K}$ should satisfy

\begin{matrix} | ⋃_{d_{i} \in C_{k}} ‍ H_{i} | \geq n . \end{matrix}

(15)

Before describing the number of transmissions for data exchange process within cluster $C_{k}$ , we first introduce a useful existing result in [26].

Theorem 2 (see [26]).

Provided that the encoding field size is large enough, the minimum number of packets to be exchanged is given by

\begin{matrix} x = rank (⋃_{d_{i} \in C_{k}} ‍ H_{i}) - \min_{P} \frac{S_{R (P)} - rank (\cup_{d_{i} \in C_{k}} H_{i})}{| P | - 1}, \end{matrix}

(16)

where

P = {S_{1}, S_{2}, \dots, S_{| P |}}

denotes a disjoint partition of the node sets and

S_{j} \in P

is the subset of the nodes in

C_{k}

, where

2 \leq P \leq | C_{k} |

, and

rank (⋃_{d_{i} \in C_{k}} ‍ H_{i})

means the rank of the matrix including the encoding vectors of the packets in

⋃_{d_{i} \in C_{k}} ‍ H_{i}

S_R (P) = \sum_{S_{j} \in P} ‍ rank (⋃_{d_{i} \in S_{j}} ‍ H_{i})

Note that in our problem, the packets sent by the source node s are linear independent with each other. Thus, for a given cluster $C_{k}$ , we can obtain that

\begin{array}{l} rank (⋃_{d_{i} \in C_{k}} ‍ H_{i}) = n, \\ S_{R} (P) = \sum_{S_{j} \in P}^{} rank (⋃_{d_{i} \in S_{j}} ‍ H_{i}) \\ = \sum_{S_{j} \in P}^{} \min {| ⋃_{d_{i} \in S_{j}} ‍ H_{i} |, n} . \end{array}

(17)

Given the packets received by the destination nodes in $C_{k}$ , according to Theorem 2, we can then derive the number of packets to be exchanged among the destinations in $C_{k}$ as follows:

\begin{matrix} x_{k} = n - \min_{P} \frac{\sum_{S_{j} \in P}^{} \min {| \cup_{d_{i} \in S_{j}} H_{i} |, n} - n}{| P | - 1}, \end{matrix}

(18)

where P is a disjoint partition of the nodes in

C_{k}

and

S_{j} \in P

is the jth subset of the nodes by the partition P.

5.2. Optimal Cluster Division with Minimum Transmission Cost in the Data Exchange Process

We now consider how to divide all the destination nodes into multiple clusters, so as to minimize the total transmission cost in the second stage.

For m destination nodes in D, the maximum number of clusters that can be formed is m. The problem of minimizing the total transmission cost of the data exchange within the clusters by cluster division can be formulated as follows:

\begin{matrix} \min_{C_{k}} \sum_{k = 1}^{m} t (C_{k}) x_{k} \end{matrix}

(19)

subject to

\begin{matrix} C_{k} ⋂ ‍ C_{k'} = \emptyset, \end{matrix}

(20)

\begin{matrix} ⋃_{k = 1}^{m} ‍ C_{k} = D, \end{matrix}

(21)

\begin{matrix} | ⋃_{d_{i} \in C_{k}} ‍ H_{i} | = n . \end{matrix}

(22)

In (19),

t (C_{k})

means the transmission cost if the destination nodes in

C_{k}

form a cluster, and

x_{k}

is number of packets to be sent by the data exchange within cluster

C_{k}

, which can be calculated with (18). Thus, the objective is to minimize the total transmission cost of the data exchange within all the clusters, by determining

C_{k}

. The constraints in (20) and (21) denote that each destination node should be located in one and only one cluster. The constraint in (22) represents that the destination nodes can form a cluster if and only if these destination nodes collectively can recover all the n original packets.

Although the above formulation can derive the optimal cluster division to minimize the total transmission cost in the data exchange process, the complexity of calculating $x_{k}$ is too high, as we need to enumerate all the possible partitions of the nodes in $C_{k}$ , ${P}$ . It makes the formulation difficult to be solved. Thus, in the next subsection, we propose a suboptimal algorithm to divide the clusters.

5.3. Algorithm Design

In this section, given the packet reception state of each destination node, we consider to group all the destination nodes into multiple clusters.

Without loss of generality, we suppose that after $x_{h s}$ transmissions from source node s, all the destinations collectively can recover the original n packets. Otherwise, the source node s should send more packets before starting the second stage (i.e., cooperative data exchange). Let U be the set of all the destinations left in the system, that is, $U = D$ .

We then introduce how to select the destinations in U into the kth cluster $C_{k}$ . When adding a new destination $d_{i}$ from U into $C_{k}$ , we make the following rules. (1)

The destination $d_{i}$ should be able to contribute at least one “innovative” packet to the destination nodes that have been added to $C_{k}$ so far.

(2)

Deleting $d_{i}$ from U will not sacrifice the decoding capability of the destinations left in U, that is, (22).

(3)

The sum of the transmission costs of the new cluster $C_{k}$ (including $d_{i}$ ) and the cluster formed by the left destinations in U (excluding $d_{i}$ ) is smaller than the transmission cost of the cluster formed by $U ⋃_{} ‍ C_{k}$ .

We then describe the process of adding new destinations to $C_{k}$ as follows. (i)

We start from the destination node $d_{i} \in U$ that satisfies the above three rules and incurs the least transmission cost if it is added into $C_{k}$ . If there does not exist such a node in U, we can obtain that the destinations in U can only form one cluster, that is, $C_{k} = U$ . In this case, the algorithm terminates.

(ii)

If we can find a feasible destination $d_{i}$ , we add $d_{i}$ into $C_{k}$ and correspondingly delete $d_{i}$ from U. We then check if the destinations in $C_{k}$ can collectively recover all the original packets. If they can, we finish the cluster $C_{k}$ and repeat the above process to find the $(k + 1)$ th cluster $C_{k + 1}$ from U.

(iii)

If they still cannot recover all the original packets, we continue the above two steps.

(iv)

The algorithm continues until we cannot find a feasible node $d_{i} \in U$ that satisfies the rules (1), (2), and (3). In this case, the destination nodes left in U should be all added to the current considered cluster $C_{k}$ , that is, $C_{k} = C_{k} ⋃_{} ‍ U$ .

The detailed process of the above algorithm is shown in Algorithm 1. With the above algorithm, we can make sure that the destination nodes within each cluster $C_{k} \in C$ collectively can reconstruct all the original packets.

Algorithm 1: Algorithm design for cluster determination.

begin

//after sending $x_{h s}$ packets from the source node s

if the destinations in D cannot recover the original packets

then

The source s should send more packets before the

second stage;

end

else

$U = D$ ;

$C_{1} = \emptyset$ ;

not_finish=1;

$k = 1$ ;

while not_finish do

find a destination $d_{i} \in U$ which satisfies the rules

(1), (2), and (3) and incurs the least cost to $C_{k}$ ;

if There does not exist a feasible $d_{i} \in U$ then

$C_{k} = C_{k} ⋃ U$ ;

not_finish=0;

end

else

add $d_{i}$ into $C_{k}$ ;

delete $d_{i}$ from U;

if If the destinations in $C_{k}$ can collectively

recover the original packets then

$k = k + 1$ ;

$C_{k} = \emptyset$ ;

end

5.4. Illustration Example

We take Figure 2 as an example to illustrate how Algorithm 1 works, where five destination nodes in ${d_{1}, d_{2}, \dots, d_{5}}$ need to get three original packets. Assume that the first stage stops after the source node s sends three packets ${p_{1}, p_{2}, p_{3}}$ . The set of the packets received by each destination in the first stage is given near the node. To simplify the understanding, we define the transmission cost of the transmission within a cluster $C_{k}$ as the square of the maximum distance between every two destinations within the same cluster [25, 27], that is,

\begin{matrix} t (C_{k}) = \max_{d_{i}, d_{i^{'}} \in C_{k}} {{| d_{i} - d_{i^{'}} |}^{2}}, \end{matrix}

(23)

where

| d_{i} - d_{i^{'}} |

denotes the distance between two nodes

d_{i}

and

d_{i'}

(given on the edge between two nodes). Note that the above model is only an example, and our algorithm does not restrict the model of the transmission cost.

Figure 2

An example of five destination nodes.

According to the Algorithm 1, initially we have $U = {d_{1}, d_{2}, \dots, d_{5}}$ . We can easily check that if all the nodes in U form only one cluster, its transmission cost is $4^{2} = 16$ .

We first construct the cluster $C_{1}$ , by starting from any node $d_{1}$ . Since $d_{1}$ satisfies all the three rules defined in the above section, we add $d_{1}$ into $C_{1}$ and delete it from U, that is, $C_{1} = {d_{1}}, U = {d_{2}, d_{3}, \dots, d_{5}}$ . Since the nodes in $C_{1}$ cannot reconstruct the original three packets, we need to add more nodes to $C_{1}$ . Note that although adding $d_{3}$ incurs the least transmission cost of $C_{1}$ , $d_{3}$ violates the rule (1), as the packet it has is not innovative to the nodes in $C_{1}$ . We then find that $d_{2}$ can be added to $C_{1}$ and it incurs the least transmission cost among the nodes left in $U ∖ {d_{3}}$ , that is, $C_{1} = {d_{1}, d_{2}}, U = {d_{3}, d_{4}, d_{5}}$ . With a similar approach, $d_{4}$ will be added to $C_{1}$ , that is, $C_{1} = {d_{1}, d_{2}, d_{4}}, U = {d_{3}, d_{5}}$ . Since the destinations in $C_{1}$ now can collectively reconstruct the original three packets, the construction of cluster $C_{1}$ terminates, and the transmission cost of $C_{1}$ is $t (C_{1}) = 3^{2} = 9$ .

We then construct the cluster $C_{2}$ . We can easily check that any node in $U = {d_{3}, d_{5}}$ cannot satisfy the rule (2). Thus, the destination nodes in U cannot be divided into multiple clusters. In other words, all the destinations in U are added into $C_{2}$ , that is, $C_{2} = {d_{3}, d_{5}}$ , and the transmission cost of $C_{2}$ is $t (C_{2}) = 2 . 5^{2} = 6.25$ . With the above operation, the destination nodes in D form two clusters, $C_{1} = {d_{1}, d_{2}, d_{4}}, C_{2} = {d_{3}, d_{5}}$ . Note that, the algorithm can start from any node, for example, if starting from node $d_{2}$ , we can also get two clusters ${d_{2}, d_{4}, d_{1}}$ , ${d_{3}, d_{5}}$ .

6. Simulation Results

In the simulation, we study a connected network graph, where nodes are randomly deployed in a two-dimensional (2D) space. We use $l_{s}$ to simulate the packet loss probability on the link from the source node s to the destination nodes, and $l_{k}$ to be the packet loss probability by the data exchange within cluster $C_{k}$ . For the transmission cost, we use $t_{s}$ and $t (C_{k})$ to denote the transmission cost of the packet sent from source node and the packet exchanged within cluster $C_{k}$ , respectively. Generally, we set $l_{s} \geq l_{k}$ and $t_{s} \geq t (C_{k})$ .

To demonstrate the performance of our proposed scheme, we also conduct two baseline algorithms: source-dominated scheme, and the hybrid scheme by [16]. As introduced before, in source-dominated scheme, the source node keeps sending until all the destination nodes get the complete packets. The difference between the hybrid scheme proposed by [16] and ours is that the scheme in [16] stops the source sending exactly once the destination nodes in each cluster can collectively reconstruct the full packets.

We define cost gain, denoted as δ, as the ratio of the transmission cost difference with source-dominated scheme and the hybrid scheme (our hybrid scheme or the scheme in [16]) to the total transmission cost with source-dominated scheme, for example, the cost gain by our hybrid scheme can be written as

\begin{matrix} δ = \frac{x_{s} t_{s} - (x_{h s} t_{s} + \sum_{C_{k} \in 𝒞}^{} x (C_{k}) t_{k})}{x_{s} t_{s}} . \end{matrix}

(24)

6.1. The Impact of the Transmission Cost

In this section, we conduct the simulation to investigate the impact of the transmission cost on the cost gain. In this setting, we set $| 𝒞 | = 2$ , $l_{s} = 0.5, l_{k} = 0.2, t_{s} = 6, | C_{k} | = 5$ and vary the transmission cost of the data exchange within each cluster in $[1,6]$ .

As shown in Figure 3, the cost gain with our hybrid scheme is much better than the scheme proposed by [16]. We can observe that in some cases, for example, $t (C_{k}) \geq 3$ , the total transmission cost with the scheme [16] is even more than source-dominated scheme. This is because, when the transmission cost of the packet exchange within a cluster is high, the sum of the transmission costs in multiple clusters exceeds the cost consumed by pure source sending. In other words, the hybrid scheme in [16] stops the source transmission too early. From the figure, we can also find that when $t (C_{k})$ is no more than $3$ , the transmission cost with our hybrid scheme is better than the source-dominated scheme. However, when $t (C_{k}) \geq 4$ , it is the same as the source-dominated scheme, which verifies the results of Theorem 1. In this case, the programming used in our hybrid scheme can detect and keep the source sending until all the nodes receive the complete packets.

Figure 3

The impact of transmission cost of each cluster on the transmission cost gain ratio.

From Figure 3, we can also observe that with the increase of the transmission cost within a cluster, the cost gain decreases. This is reasonable, as when the transmission cost within a cluster increases, the sum of the total transmission costs of multiple clusters increases quickly and correspondingly reduces the gain.

6.2. The Impact of Packet Loss Probability

We now investigate the impact of packet loss probability on the performance of the total transmission cost. We fix $n = 100, l_{k} = 0.2, | 𝒞 | = 2, t_{s} = 6, t (C_{k}) = 3$ and vary the packet loss probability on the link from the source to the destination in $[0.4,0.9]$ .

As shown in Figure 4, the cost gain with our hybrid scheme is better than with the scheme in [16], and our hybrid scheme also always consumes less transmission cost compared with source-dominated transmission scheme. From the figure, we observe that with the increase of the packet loss probability from the source to the destination nodes, the transmission cost gains with both hybrid schemes increase. This is because, when the links from the source to the destinations nodes are too bad, the source node should stop sending the packet as early as possible.

Figure 4

The impact of packet loss probability on the transmission cost gain ratio.

In addition, when the packet loss probability $l_{s} \geq 0.8$ , the cost gains with both hybrid schemes are almost the same, as our hybrid scheme may stop the source transmission at almost the same time as in [16], that is, after the destination nodes in each cluster can reconstruct the complete packets.

6.3. The Impact of the Number of Clusters

We now conduct the simulation to investigate the impact of the number of the clusters on the total transmission cost of the proposed schemes. In this setting, we fix $n = 100, l_{s} = 0.6, l_{k} = 0.2, t_{s} = 6, t (C_{k}) = 2$ and the number of clusters are varied from $1$ to $7$ .

As shown in Figure 5, when the number of clusters is few, the total transmission costs with both hybrid schemes are less than with the source-dominated scheme. This is because, when the number of clusters is few, the sum of their transmission costs does not exceed the source transmission cost. However, when the number of clusters increases, for example, more than $5$ , pure source transmission is better, since the sum of the transmission costs in the clusters is more than the transmission cost from the source. However, we can observe that, the transmission cost with our scheme is not higher than with source-dominated scheme in all the cases, as our hybrid scheme always chooses the best time to stop the source transmission.

Figure 5

The impact of the number of clusters on the transmission cost gain ratio.

6.4. The Impact of the Number of Receiver Nodes within Clusters

Finally, we investigate the impact of the number of destination nodes within each cluster on the performance of our transmission scheme.

As shown in Figure 6, we fix $n = 100, t_{s} = 6, t (C_{k}) = 2, l_{k} = 0.2$ and vary the number of destination nodes within each cluster in [2, 10]. From the figure, we can see that with the increase of the number of the destination nodes within each cluster, the cost gain with our hybrid scheme increases. This is because, with more destination nodes in a cluster, it is much more earlier that the destinations in the cluster collectively can reconstruct the original n packets. Thus, the second stage of our hybrid scheme, data exchange process, can start earlier, which decreases the number of high-cost transmissions from the source node s.

Figure 6

The impact of the number of destinations within the cluster on cost gain by our scheme.

From Figure 6, we also observe that the cost gain with the setting $l_{s} = 0.8$ is much higher than with the setting $l_{s} = 0.6$ . The reason is that with source-dominated scheme, a large number of the transmissions will be wasted when the packet reception state on the links from s to the destination nodes is bad. In this case, the cooperative data exchange process in our hybrid scheme should start as early as possible, as it consumes less transmission cost. In other words, our hybrid scheme performs well especially when the packet reception from the source node is bad.

By comparing Figures 6(a) and 6(b), we can also obtain that when the number of clusters in the network increases, the cost gain of our hybrid scheme decreases. As each cluster consumes its independent transmission cost in the cooperative data exchange process, the sum of the transmission costs of the data exchange by all the clusters increases, which thus decreases the cost gain.

7. Conclusion

In this paper, we proposed a hybrid source and cooperative data exchange transmission scheme for reliable multicasting over wireless lossy links. Our hybrid scheme determines when to stop the source sending and start the cooperative data exchange, so as to minimize the total transmission cost. We theoretically derive the total transmission cost required with traditional source-dominated scheme and our hybrid scheme. We give a condition under which the source node should not stop sending the packets until all the destination nodes successfully get the complete information, so as to reduce the total transmission cost. If the clusters are predefined, we propose an efficient algorithm to divide the destination nodes into multiple clusters, such that the destination nodes within each cluster can conduct the cooperative data exchange separately with energy efficiency. Finally, simulation results demonstrate the effectiveness of the proposed scheme in reducing the total transmission cost.

Footnotes

Acknowledgments

This work was supported by the Fundamental Research Funds for the Central Universities (no. 2012HGBZ0640). It was also supported in part by National Natural Science Foundation of China under Grants no. 61202378, 61070169, Natural Science Foundation of Jiangsu Province under Grant no. BK2011376, Specialized Research Foundation for the Doctoral Program of Higher Education of China no. 20103201110018, and Application Foundation Research of Suzhou of China no. SYG201118.

References

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

2-s2.0-0037086890

10.1016/S1389-1286(01)00302-4

Bandara

H. M. N. D.

Jayasumana

A. P.

Illangasekare

T. H.

A top-down clustering and cluster-tree-based routing scheme for wireless sensor networks

International Journal of Distributed Sensor Networks 2011 17

940751

10.1155/2011/940751

Liu

Chu

Leung

Jia

Wan

General maximal lifetime Sensor-Target surveillance problem and its solution

IEEE Transactions on Parallel and Distributed Systems 2011 22 10 1757 1765

Kulkarni

S. S.

Wang

MNP: multihop network reprogramming service for sensor networks

Proceedings of the 25th IEEE International Conference on Distributed Computing Systems

June 2005

usa

7 16

2-s2.0-27944469190

Wang

Data dissemination in wireless sensor networks with network coding

Eurasip Journal on Wireless Communications and Networking 2010 2010

2-s2.0-77955368936

10.1155/2010/465915

465915

Wen

Y. F.

Liao

Minimum power multicast algorithms for wireless networks with a Lagrangian relaxation approach

Wireless Networks 2011 17 6 1401 1421

2-s2.0-79958038522

10.1007/s11276-011-0344-9

El Rouayheb

Sprintson

Sadeghi

On coding for cooperative data exchange

Proceedings of the IEEE Information Theory Workshop 2010 (ITW '10)

January 2010

1 5

2-s2.0-77954832847

10.1109/ITWKSPS.2010.5503135

Courtade

T. A.

Xie

Wesel

R. D.

Optimal exchange of packets for universal recovery in broadcast networks

Proceedings of the IEEE Military Communications Conference (MILCOM '10)

November 2010

2250 2255

2-s2.0-79951663246

10.1109/MILCOM.2010.5680380

Milosavljevic

Pawar

El-Rouayheb

Gastpar

Ramchandran

Deterministic algorithm for the cooperative data exchange problem

Proceedings of the IEEE International Symposium on Information Theory (ISIT '11)

2011

410 414

10.

Tajbakhsh

Sadeghi

Shams

A generalized model for cost and fairness analysis in coded cooperative data exchange

Proceedings of the IEEE International Symposium on Network Coding (NetCod '11)

2011

1 6

11.

Wang

Song

Yuen

J. T.

Exchanging third-party information with minimum transmission cost

Proceedings of the IEEE Global Communications Conference (Globecom '12)

2012

12.

Liu

Lee

V. C. S.

RSU-based real-time data access in dynamic vehicular networks

Proceedings of the 13th International IEEE Conference on Intelligent Transportation Systems (ITSC '10)

September 2010

1051 1056

2-s2.0-78650430555

10.1109/ITSC.2010.5625189

13.

Liu

Lee

V. C. S.

Adaptive data dissemination for timeconstrained messages in dynamic vehicular networks

Transportation Research C 2012 21 214 229

14.

Al-Ameen

Islam

S. M. R.

Kwak

Energy saving mechanisms for MAC protocols in wireless sensor networks

International Journal of Distributed Sensor Networks 2010 2010 16

2-s2.0-79952833104

10.1155/2010/163413

163413

15.

Elkin

Lando

Nutov

Segal

Shpungin

Novel algorithms for the network lifetime problem in wireless settings

Wireless Networks 2011 17 2 397 410

2-s2.0-79951509099

10.1007/s11276-010-0287-6

16.

Shrader

Royster

Cooperative multicast strategies under heterogeneous link loss rates

Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM '11)

December 2011

1 5

17.

Ahlswede

Cai

S. Y. R.

Yeung

R. W.

Network information flow

IEEE Transactions on Information Theory 2000 46 4 1204 1216

2-s2.0-0034229404

10.1109/18.850663

18.

Wang

Xiao

Optimal linear network coding design for secure unicast with multiple streams

Proceedings of the IEEE International Conference on Computer Communications (INFOCOM '10)

March 2010

1 8

2-s2.0-77953316768

10.1109/INFCOM.2010.5462049

19.

Ghaderi

Towsley

Kurose

Network coding performance for reliable multicast

>Proceedings of the Military Communications Conference (MILCOM '07)

October 2007

2-s2.0-47949132620

10.1109/MILCOM.2007.4454851

20.

Wang

CAPF: coded anycast packet forwarding for wireless mesh networks

Wireless Networks 2011 17 5 1273 1285

2-s2.0-79959493974

10.1007/s11276-011-0348-5

21.

Katti

Rahul

Katabi

Medard

Crowcroft

XORs in the air: practical wireless network coding

IEEE/ACM Transactions on Networking 2008 16 3 497 510

2-s2.0-45749150357

10.1109/TNET.2008.923722

22.

Fragouli

Le Boudec

J. Y.

Widmer

Network coding: an instant primer

ACM SIGCOMM Computer Communication Review 2006 36 1 63 68

23.

Ghaderi

Towsley

Kurose

Reliability gain of network coding in lossy wireless networks

Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08)

April 2008

2171 2179

2-s2.0-51349150827

10.1109/INFOCOM.2007.284

24.

Cai

Yeung

R. W.

Secure network coding on a wiretap network

IEEE Transactions on Information Theory 2011 57 1 424 435

2-s2.0-78650893906

10.1109/TIT.2010.2090197

25.

Wieselthier

J. E.

Nguyen

G. D.

Ephremides

On the construction of energy-efficient broadcast and multicast trees in wireless networks

Proceedings of the IEEE 19th Annual Joint Conference of Computer and Communications Societies (INFOCOM '00)

March 2000

585 594

2-s2.0-0033894011

26.

Chan

Generating secret in a network [Ph.D. dissertation] 2010

Massachusetts Institute of Technology

27.

Kim

De Veciana

Is rate adaptation beneficial for inter-session network coding?

Proceedings of the IEEE Journal on Selected Areas in Communications

2009

635 646

2-s2.0-62349101309

10.1109/MILCOM.2008.4753085