# Secure Data Delivery with Linear Network Coding for Multiple Multicasts with Multiple Streams in Internet of Things

Authors: Lianmin Shi; Yihuai Wang; Zhengqing Wen; Tao Peng
Journal: Security and Communication Networks
 (2018)

---

## Abstract

With the rapid developments ofInternet of Things (IoT), tremendous number of sensors are deployed in the environment to monitor and collect different types of information. When a group of sensors located with the same location (or area) should deliver their data to a set of users and they have connected with the same network device, e.g., base station or access point, the data delivery between them and their users can be treated as a single source multicast in the core network from the network device connected with them to the network devices connected with their users. Generally, in such a case, multiple multicast sessions exist in the network simultaneously. In this paper, we study two major considerations,i.e., transmission throughput and information security, for multiple multicasts with multiple streams in IoT by usinglinear network coding (LNC). Specifically, we jointly consider the transmission rate allocation, transmission topology selection, and secure LNC design for multiple multicasts to maximize the totalsecure weighted throughput (SWT), which is referred to as thesecure delivery for multiple multicasts with multiple streams (SMMS) problem. To this end, we firstly consider the SMMS problem in the case that each sensor is connected with a fixed network device. We then study the SMMS problem when the source of each multicast can be selected from a set of nodes. For the first case, we formulate it to be alinear programming (LP), based on which we give the MORT algorithm to optimally solve it. On the other hand, for the second case, we first formulate it to be aninteger linear programming (ILP) and then propose an efficient MBLP algorithm based on linear programming relaxation to obtain a suboptimal solution. Finally, we conduct extensive simulations to show the effectiveness and efficiency of the proposed algorithms.


---

## Body

## 1. Introduction

Internet of Things (IoT) has been widely studied and applied in the past ten years [1, 2]. In IoT shown in Figure 1, multiple sensor nodes are allocated in different areas and they can access the core network by connecting the base station located within their communication range. To analyze and further utilize the data information collected by these sensors, the data should be transmitted from these sensors to the different users. Transmission throughput and information security are two major considerations in IoT.Figure 1
An example of IoT.Network coding (NC) is a promising technology to be used in the next-generation network because it can maximize the throughput capacity of a network [3, 4]. By using NC, nodes in the network can encode and decode the received data packets instead of only store and forward. When the encoding and decoding are linear operations on a finite field, it is calledlinear network coding (LNC) [4]. For multiple multicast, LNC has been applied to improve the transmission throughput [5, 6].Related studies have proved that LNC not only can make the multicast transmission reach the theoretical upper bound of throughput [7, 8] but also can provide information confidentiality due to its inherent characteristics [9]. Specifically, when applying LNC to multicast communication, the data information transmitted in the network is no longer the original data chunk, but the linear combination of original data chunks, which is called theencoded packet. If the attacker cannot receive enough encoded packets, it cannot obtain information about the original data chunk. In this condition, LNC becomes an effective way to resist passive attacks and provide secure data transmission without the key distribution protocols, which reduces the system complexity [10–18].In order to provide data confidentiality, existing researches mainly focus on two different security requirements:Information Theoretical Security (ITS) [14, 15, 17, 18] and Weak Security (WS) [10–13]. ITS requires that any nonzero linear combination of original data chunks cannot be obtained by attackers. In order to achieve ITS, random information must be added to encode together with original data chunks during data transmission. On the other hand, WS does not allow anymeaningful information,e.g., the coded packets that can be generated by the original data packets of the same data stream be leaked to the attacker. We note that the data stream means a data flow in which all the data are collected by the same sensor.In practice, a group of sensors with different types may be deployed at the same place to monitor the same area from different aspects [1, 2]. For example, a group of sensors, including temperature sensor, humidity sensor, PM2.5 sensor, and camera, may be placed at each place to monitor the same area and deliver their data information to a group of users,e.g., meteorological department, military department, companies, and personal devices. Since the group of sensors is located at the same place, they connect to the same network device,e.g., base station or access point. The data information sent from them must pass through the network device that they connected with;i.e., the network device can be seen as the source of data information. Similarly, the network devices can be seen as the destinations of data information requested by the users connected with it. Therefore, the data delivery from each group of sensors located in the same place to a group of users can be seen as a single source multicast which is from the network device connected with them to the group of network devices connected with their users. Moreover, multiple data streams generated by the different sensors exist in the single source multicast. With the consideration of the limitation of the bandwidth capacity of the core network, when multiple single source multicasts exist, the transmission rate should be allocated for each data stream in each multicast to maximize the total throughput. We also give each data stream a weight to reflect the different requirements or importance.In our previous study [19], we have considered the optimal transmission rate allocation and weakly secure LNC for single multicast scenario. In this paper, we will further study the multiple multicasts scenario and the source selection problem when the source of each multicast can be selected from a set of nodes. Next, we will give an example to show the differences between these two scenarios,i.e., the achievedsecure weighted throughput (SWT) in the cases of considering multiple multicasts individually and considering multiple multicasts together. In the following, we do not show the sensors and the users. Next, we give the examples to show the motivation and the importance of our research.The core networkG is given in Figure 2, in which nodes represent network devices,e.g., base stations, access points, and routers, and they are connected by a wired core network. Specifically, there are two multicasts in this network;i.e., source node s1 sends data to the destination node set T1={t1,t3} and source node s2 sends data to the destination node set T2={t2,t4}. In addition, nodes v1 and v2 are assumed to be attackers in the network. The bandwidth capacity of each link is set to 1. In Figures 3(a)–3(d), we assume that there are two data streams sent by source s1 which are denoted as x and y, and two data streams sent by source s2 which are denoted as a and b, respectively. In particular, encoding operations are only done between the data with the same source [10, 11, 13, 15, 16]. We also assign a unit weight to each data stream. We should allocate the transmission rate of each data stream and design secure LNC scheme under the transmission rate allocation to maximize the total SWT. For example, in the network, if the transmission rate of data stream x is 2, it means the source node s1 can send two packets of data stream x in one transmission round: x1 and x2. In addition, the coding coefficients of the LNC are chosen from the finite fields F2.Figure 2
The network topologyG (without showing the sensors and the users).Figure 3
An example of secure multicast for multiple data streams.
(a)
Example 1 for the 1st multicast (b)
Example 1 for the 2nd multicast (c)
Example 2 for the 1st multicast (d)
Example 2 for the 2nd multicastFirstly, in the networkG, when we consider each multicast individually, the maximum flow from source node s1 to any destination node in T1 is 3. Therefore, we can allocate the transmission rate 2 to data stream 1 and transmission rate 1 to data stream 2. The transmission topology and secure LNC of the first multicast are shown in Figure 3(a). Specifically, the destination t1 can decode and recover x1, x2=(x1+x2+y1)+(x1+y1) and y1=x1+(x1+y1). The destination t3 can decode and recover x1=(x1+x2+y1)+(x2+y1), x2=(x1+x2+y1)+(x1+y1), and y1=(x1+x2+y1)+(x1+y1)+(x2+y1). Moreover, the attacker v1 cannot obtain any nonzero coded data packet generated only by the data from the same stream, because it only receives one coded data packet x1+y1. Although the maximum flow from source node s2 to any destination node of T2 in G is 2, since each link has unit bandwidth capacity, after the first multicast occupying the set of links shown in Figure 3(a), the maximum flow from source node s2 to any destination node of T2 is 0 in the remaining network topology which is shown in Figure 3(b). In this case, the total SWT of the two multicasts is 1×3+1×0=3.Secondly, when we consider the two multicasts together to optimize the total SWT, the transmission topologies and secure LNCs of the two multicasts are shown in Figures3(c) and 3(d), respectively. Specifically, for the first multicast, we can allocate the transmission rate 1 to data stream 1 and transmission rate 1 to data stream 2. Both the destinations t1 and t3 can decode and recover x1 and y1=x1+(x1+y1). For the second multicast, we can allocate the transmission rate 1 to data stream 1 and transmission rate 1 to data stream 2. Both the destinations t2 and t4 can decode and recover a1 and b1=a1+(a1+b1). Moreover, the attackers v1 and v2 cannot obtain any nonzero coded data packet generated only by the data from the same stream. Therefore, in this case, the total SWT of the two multicasts is 1×2+1×2=4. Compared to the schemes shown in Figures 3(a) and 3(b), the SWT is improved by 33%.From the above examples, we can conclude that, to maximize the total SWT, multiple multicasts should be considered together. Therefore, in this paper, we will consider the transmission rate allocation, transmission topology selection, and the secure LNC schemes for multiple multicasts to maximize the total SWT, which is referred to as thesecure delivery for multiple multicast with multiple streams (SMMS) problem. To this end, we will firstly consider the SMMS problem in the case that each sensor is connected with a fixed network device;i.e., each multicast has a fixed source. We then study the SMMS problem when the source of each multicast can be selected from a set of nodes;i.e., multiple network devices can be selected for each sensor.The rest of the paper is organized as follows. We first introduce the network model in Section2. We then formulate the SMMS problem and design algorithms based on linear programming and its relaxations in Section 3. We then conduct extensive simulations to illustrate the performance of the proposed algorithms in Section 4. Finally, we conclude the paper in Section 5.


## 2. SMMS Problem Modeling

### 2.1. The Network Model

In this section, we first introduce the network model, important parameters, the multiple multicast network coding scheme, and the security model to be used in this paper. Secondly, we give the formal definition of the weakly secure linear multicast code. Finally, we formally define thesecure delivery for multiple multicasts with multiple streams (SMMS) problem.In this paper, we consider an IoT network consisting of sensors, network device,e.g., base station, access point and routers, and end users,e.g., departments, companies, and personal devices [1, 2]. We consider multiple groups of sensors which are deployed in different areas to monitor the environment. Each group is located at the same place and they connect to the same network device,e.g., base station or access point. The data information sent from them must pass through the network device that they connected with;i.e., the network device can be seen as the source of data information. Similarly, the network devices can be seen as the destinations of data information requested by the users connected with it. Consequently, the data delivery from each group of sensors located in the same place to a group of users can be seen as a single source multicast which is from the network device connected with them to the group of network devices connected with their users. Therefore, in the following, we only consider multicasts within the wired core network. Moreover, multiple data streams generated by the different sensors exist in the single source multicast. With the consideration of the limitation of the bandwidth capacity of the core network, when multiple single source multicasts exist, the transmission rate should be allocated for each data stream in each multicast to maximize the total throughput.We use a directed graphG=(V,E) to present the wired core network, where V is the set of nodes and E is the set of links. Firstly, we assume that there are H multicasts in G and the source node of the hth multicast is denoted as sh∈V, h∈{1,…H}. Let S={s1,⋯,sH}. The set of destinations of hth multicast is denoted as Th. Let T=⋃h=1HTh={t1,⋯,tN},T⊂V. The hth multicast session can be expressed as (sh,Th). Specifically, the source sh actually represents the group of sensors which connect to sh and has the set of destinations Th. If the number of sensors in the group is Lh, then there are a total of Lh data streams in multicast (sh,Th), each of which is generated (or sent) by a sensor node. The total transmission rates of the first lth data streams are denoted as Dlh and the transmission rate of the lth stream is Dlh-Dl-1h and D0h=0. Specifically, these Lh data streams can be sent from sh to Th at different transmission rates in each transmission round.In particular, for thelth data stream of the hth multicast, we define its weight as ωlh>0, ∀h∈{1,⋯,H}, ∀l∈{1,⋯,Lh}. The weights reflect different requirements or importance. In addition, for ∀eu,v∈E, it has a certain bandwidth capacity cu,v. For convenience, the important symbols are defined as shown in Table 1.Table 1
Symbol definition.
Symbol Definition  Bold Font Linear spaces, matrixes and vectors  SymbolT Transpose of a matrix or vector  Rank(B) The rank of a matrix or a vector setB  Fq The finite field with sizeq  eu,v Directed link from nodeu to node v  cu,v Bandwidth capacity of linkeu,v  Ai The set of global encoding vectors received by intermediate nodevi  H H = 1 , ⋯ , H  Lh L h = 1 , ⋯ , L h, ∀h∈H  Dlh The sum of the transmission rates of the firstlth data streams in the hth multicast


### 2.2. Linear Network Coding for Multiple Multicast

In this paper, the encoding operations are performed only between different data packets of streams of the same multicast [10, 11, 13, 15], which means data streams from different multicasts will not be encoded together. We define the set of original data packets sent by the source node sh as Mh=[m1,1h,m1,2h,…,m1,D1hh,m2,1h,…,mLh,1h,…,mLh,DLhh-DLh-1hh]T, ∀h∈H. Therefore, in a transmission round, the set of original data packets for the lth data stream sent from the source node sh can be defined as Mh,l=[ml,1h,ml,2h,…,ml,Dlh-Dl-1hh]T.Although multiple multicasts share the capacity of each link, only the data packets belonging to the same multicast will be encoded together. Therefore, when the transmission rate allocation and the transmission topology have been obtained, the LNC scheme for each multicast session can be designed individually.∀eu,v∈E, if there is a coded packet mh from the multicast (sh,Th) passing through it, we can use a DLhh-dimensional row vector f(eu,v,h) to represent theglobal encoding vector (GEV) of the coded packet as long as mh=f(eu,v,h)Mh. In addition, the LNC design is implemented in a finite field Fq with size q, which means all elements of the GEVs are taken from the finite field Fq. In particular, for an original data packet from multicast (sh,Th), its GEV is a row of the DLhh×DLhh-dimensional identity matrix. We denote the set of links entering node v as In(v) and the set of links leaving node v as Out(v). For the source node sh∈S,∀h∈H, it is assumed that In(sh) constitutes DLhh virtual links, and each virtual link represents an original data packet of the multicast.Therefore, for multicast(sh,Th),∀h∈H, the DLhh-dimensional linear multicast code ϕ(G,Fq,sh,Th,Lh,H) can be defined as follows.Definition 1.
∀ h ∈ H, the DLhh-dimensional linear multicast code Φ(G,Fq,sh,Th,Lh,H) exists if the following three conditions are satisfied:
( 1 ) For the source sh∈S in multicast (sh,Th), ⋃e∈In(sh){f(e,h)} consists of the basis of the vector space FqDLhh.
( 2 ) ∀ e v , w ∈ O u t ( v ), f(ev,w,h) is a linear combination of ⋃eu,v∈In(v){f(eu,v,h)},∀v∈V.
( 3 ) For each destination t,∀t∈Th in multicast (sh,Th), ⋃eu,t∈In(t){f(eu,t,h)} consists of the basis of the vector space FqDLhh.The above definition shows that(1) for sh∈S,∀h∈H, all the coded data packets transmitted in the network which related to multicast (sh,Th) can be generated by it; (2)∀v∈V, all the coded data packets sent out from it can be generated by linearly combining the coded data packets received from its incoming links; (3) for t∈Th,∀h∈H, it can decode the received coded packets for the original data of all the Lh streams. In addition, ∀h∈H, if the destination node in the multicast (sh,Th) receives DLhh linearly independent coded packets, it can decode and obtain DLhh original data packets. For example, suppose that the matrix Mh′ is composed of coded data packets as its rows and the matrix Ah is composed of the corresponding GEVs as its rows, then we have AhMh=Mh′. Therefore, the destination node can decode and obtain the original data packets by Mh=Ah-1Mh′. Additionally, ∀vi∈V, let Ah,i={f(e,h)∣e∈In(vi),h∈H}.


### 2.3. Security Model

We assume that, inG, there exists a set of inside passive attackers I¯,I¯=V-S-T⊆I, each of which tries to acquiremeaningful information of original data by collecting the data packets passing through them individually [10] (similar to the attack model considered in [11, 13–15, 19]).For the secure requirement, we consider theWeak Security (WS) [10] in this paper, which has been widely studied in the literature [11–13, 19]. Since only the data packets belonging to the same multicast can be encoded together, the WS requirements should be satisfied for each multicast. Let Bh,i be the matrix consisting of nonzero vectors in Ah,i as its row vectors. For the above-mentioned attack model and multiple multicast models with multiple data streams, the weakly secure linear multicast code can be defined as follows.Definition 2.
∀ h ∈ H, the DLhh-dimensional linear multicast code Φ(G,Fq,sh,Th,Lh,H) constructed on the finite field Fq with size q is weakly secure, if it satisfies that for any malicious node vi∈I¯:(1)HMh,l∣Bh,iMh=HMh,l,∀l∈Lh
Equation (1) shows that ∀h∈H,∀l∈Lh and ∀i, Mh,l and Bh,iMh are independent with each other. Any malicious node cannot obtain a nonzero linear combination of original data packets from the same data stream of the same multicast.Definition 3.
∀ h ∈ H, if the DLhh-dimensional linear multicast code ω(G,Fq,sh,Th,Lh,H) constructed on the finite field Fq with size q satisfies weakly secure requirements, then it is weakly secure for the multicast (sh,Th).
For the multicast(sh,Th), the LNC can achieve the requirements of WS when Lh>1. This is because the original data packets from one data stream of the multicast can be encoded with the original data packets from the other data streams of the multicast to hide the information of the original data packet of the same stream.


### 2.4. SMMS Problem Description

In this paper, we will study the problem of secure deliveryfor multiple multicasts with multiple streams (SMMS).Definition 4.
For a given networkG, a malicious node set I¯ and H multicasts, each of which has a source node sh, a set of destination node Th, and Lh data streams, secure delivery for multiple multicast with multiple streams (SMMS) problem is to consider the transmission rate allocation, transmission topology selection, and the secure LNC schemes for multiple multicasts to maximize the total SWT.


## 2.1. The Network Model

In this section, we first introduce the network model, important parameters, the multiple multicast network coding scheme, and the security model to be used in this paper. Secondly, we give the formal definition of the weakly secure linear multicast code. Finally, we formally define thesecure delivery for multiple multicasts with multiple streams (SMMS) problem.In this paper, we consider an IoT network consisting of sensors, network device,e.g., base station, access point and routers, and end users,e.g., departments, companies, and personal devices [1, 2]. We consider multiple groups of sensors which are deployed in different areas to monitor the environment. Each group is located at the same place and they connect to the same network device,e.g., base station or access point. The data information sent from them must pass through the network device that they connected with;i.e., the network device can be seen as the source of data information. Similarly, the network devices can be seen as the destinations of data information requested by the users connected with it. Consequently, the data delivery from each group of sensors located in the same place to a group of users can be seen as a single source multicast which is from the network device connected with them to the group of network devices connected with their users. Therefore, in the following, we only consider multicasts within the wired core network. Moreover, multiple data streams generated by the different sensors exist in the single source multicast. With the consideration of the limitation of the bandwidth capacity of the core network, when multiple single source multicasts exist, the transmission rate should be allocated for each data stream in each multicast to maximize the total throughput.We use a directed graphG=(V,E) to present the wired core network, where V is the set of nodes and E is the set of links. Firstly, we assume that there are H multicasts in G and the source node of the hth multicast is denoted as sh∈V, h∈{1,…H}. Let S={s1,⋯,sH}. The set of destinations of hth multicast is denoted as Th. Let T=⋃h=1HTh={t1,⋯,tN},T⊂V. The hth multicast session can be expressed as (sh,Th). Specifically, the source sh actually represents the group of sensors which connect to sh and has the set of destinations Th. If the number of sensors in the group is Lh, then there are a total of Lh data streams in multicast (sh,Th), each of which is generated (or sent) by a sensor node. The total transmission rates of the first lth data streams are denoted as Dlh and the transmission rate of the lth stream is Dlh-Dl-1h and D0h=0. Specifically, these Lh data streams can be sent from sh to Th at different transmission rates in each transmission round.In particular, for thelth data stream of the hth multicast, we define its weight as ωlh>0, ∀h∈{1,⋯,H}, ∀l∈{1,⋯,Lh}. The weights reflect different requirements or importance. In addition, for ∀eu,v∈E, it has a certain bandwidth capacity cu,v. For convenience, the important symbols are defined as shown in Table 1.Table 1
Symbol definition.
Symbol Definition  Bold Font Linear spaces, matrixes and vectors  SymbolT Transpose of a matrix or vector  Rank(B) The rank of a matrix or a vector setB  Fq The finite field with sizeq  eu,v Directed link from nodeu to node v  cu,v Bandwidth capacity of linkeu,v  Ai The set of global encoding vectors received by intermediate nodevi  H H = 1 , ⋯ , H  Lh L h = 1 , ⋯ , L h, ∀h∈H  Dlh The sum of the transmission rates of the firstlth data streams in the hth multicast


## 2.2. Linear Network Coding for Multiple Multicast

In this paper, the encoding operations are performed only between different data packets of streams of the same multicast [10, 11, 13, 15], which means data streams from different multicasts will not be encoded together. We define the set of original data packets sent by the source node sh as Mh=[m1,1h,m1,2h,…,m1,D1hh,m2,1h,…,mLh,1h,…,mLh,DLhh-DLh-1hh]T, ∀h∈H. Therefore, in a transmission round, the set of original data packets for the lth data stream sent from the source node sh can be defined as Mh,l=[ml,1h,ml,2h,…,ml,Dlh-Dl-1hh]T.Although multiple multicasts share the capacity of each link, only the data packets belonging to the same multicast will be encoded together. Therefore, when the transmission rate allocation and the transmission topology have been obtained, the LNC scheme for each multicast session can be designed individually.∀eu,v∈E, if there is a coded packet mh from the multicast (sh,Th) passing through it, we can use a DLhh-dimensional row vector f(eu,v,h) to represent theglobal encoding vector (GEV) of the coded packet as long as mh=f(eu,v,h)Mh. In addition, the LNC design is implemented in a finite field Fq with size q, which means all elements of the GEVs are taken from the finite field Fq. In particular, for an original data packet from multicast (sh,Th), its GEV is a row of the DLhh×DLhh-dimensional identity matrix. We denote the set of links entering node v as In(v) and the set of links leaving node v as Out(v). For the source node sh∈S,∀h∈H, it is assumed that In(sh) constitutes DLhh virtual links, and each virtual link represents an original data packet of the multicast.Therefore, for multicast(sh,Th),∀h∈H, the DLhh-dimensional linear multicast code ϕ(G,Fq,sh,Th,Lh,H) can be defined as follows.Definition 1.
∀ h ∈ H, the DLhh-dimensional linear multicast code Φ(G,Fq,sh,Th,Lh,H) exists if the following three conditions are satisfied:
( 1 ) For the source sh∈S in multicast (sh,Th), ⋃e∈In(sh){f(e,h)} consists of the basis of the vector space FqDLhh.
( 2 ) ∀ e v , w ∈ O u t ( v ), f(ev,w,h) is a linear combination of ⋃eu,v∈In(v){f(eu,v,h)},∀v∈V.
( 3 ) For each destination t,∀t∈Th in multicast (sh,Th), ⋃eu,t∈In(t){f(eu,t,h)} consists of the basis of the vector space FqDLhh.The above definition shows that(1) for sh∈S,∀h∈H, all the coded data packets transmitted in the network which related to multicast (sh,Th) can be generated by it; (2)∀v∈V, all the coded data packets sent out from it can be generated by linearly combining the coded data packets received from its incoming links; (3) for t∈Th,∀h∈H, it can decode the received coded packets for the original data of all the Lh streams. In addition, ∀h∈H, if the destination node in the multicast (sh,Th) receives DLhh linearly independent coded packets, it can decode and obtain DLhh original data packets. For example, suppose that the matrix Mh′ is composed of coded data packets as its rows and the matrix Ah is composed of the corresponding GEVs as its rows, then we have AhMh=Mh′. Therefore, the destination node can decode and obtain the original data packets by Mh=Ah-1Mh′. Additionally, ∀vi∈V, let Ah,i={f(e,h)∣e∈In(vi),h∈H}.


## 2.3. Security Model

We assume that, inG, there exists a set of inside passive attackers I¯,I¯=V-S-T⊆I, each of which tries to acquiremeaningful information of original data by collecting the data packets passing through them individually [10] (similar to the attack model considered in [11, 13–15, 19]).For the secure requirement, we consider theWeak Security (WS) [10] in this paper, which has been widely studied in the literature [11–13, 19]. Since only the data packets belonging to the same multicast can be encoded together, the WS requirements should be satisfied for each multicast. Let Bh,i be the matrix consisting of nonzero vectors in Ah,i as its row vectors. For the above-mentioned attack model and multiple multicast models with multiple data streams, the weakly secure linear multicast code can be defined as follows.Definition 2.
∀ h ∈ H, the DLhh-dimensional linear multicast code Φ(G,Fq,sh,Th,Lh,H) constructed on the finite field Fq with size q is weakly secure, if it satisfies that for any malicious node vi∈I¯:(1)HMh,l∣Bh,iMh=HMh,l,∀l∈Lh
Equation (1) shows that ∀h∈H,∀l∈Lh and ∀i, Mh,l and Bh,iMh are independent with each other. Any malicious node cannot obtain a nonzero linear combination of original data packets from the same data stream of the same multicast.Definition 3.
∀ h ∈ H, if the DLhh-dimensional linear multicast code ω(G,Fq,sh,Th,Lh,H) constructed on the finite field Fq with size q satisfies weakly secure requirements, then it is weakly secure for the multicast (sh,Th).
For the multicast(sh,Th), the LNC can achieve the requirements of WS when Lh>1. This is because the original data packets from one data stream of the multicast can be encoded with the original data packets from the other data streams of the multicast to hide the information of the original data packet of the same stream.


## 2.4. SMMS Problem Description

In this paper, we will study the problem of secure deliveryfor multiple multicasts with multiple streams (SMMS).Definition 4.
For a given networkG, a malicious node set I¯ and H multicasts, each of which has a source node sh, a set of destination node Th, and Lh data streams, secure delivery for multiple multicast with multiple streams (SMMS) problem is to consider the transmission rate allocation, transmission topology selection, and the secure LNC schemes for multiple multicasts to maximize the total SWT.


## 3. Problem Formulation and Algorithm Design

In this section, we will firstly study the SMMS problem for multiple multicasts scenario when each multicast has a fixed source node. We then further consider the SMMS problem for multiple multicasts when the source of each multicast can be selected from a set of nodes inG.


### 3.1. The SMMS Problem with Fixed Source

For single multicast, in our previous work [19], we have shown that the sufficient and necessary condition. Specifically, in the SMMS problem, the condition that a secure linear multicast code exists for multicast (sh,Th) is that (1) there exists a network flow Fh with capacity DLhh between sh and each destination in Th, and (2) for each malicious node vi∈I¯, the actual data flow of Fh that enters vi should not be more than DLhh-maxl∈LhDlh-Dl-1h.ForH multicasts simultaneously transmitted in the network G, we next formulate the SMMS problem when each multicast has a fixed source node. Before building a mathematical programming for the SMMS problem, we firstly define new parameters and decision variables, as shown in Table 2.Table 2
Parameters and decision variables.
Symbol Definition  J(v) the set of all the links entering nodev, J(v)=u∣eu,v∈In(v)  J¯(v) the set of all the links leaving nodev, J¯(v)=w∣ev,w∈Out(v)  xu,vh,t the data flow of multicast(sh,Th) transmitted on link eu,v heading for destination node t, ∀h∈H,∀t∈Th,∀eu,v∈E  yu,vh the actual data flow of multicast(sh,Th) transmitted on link eu,v, ∀h∈H  bvh,t The difference of data flow of multicast(sh,Th) between the data flow entering and leaving node v, which heading for destination node t, ∀h∈HWe can formulate a mathematical programming for the SMMS problem as follows:(2)MP:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1h,(3)s.t.Dlh-Dl-1h>0,∀h∈H,∀l∈Lh(4)bvh,t=∑u∈Jvxu,vh,t-∑w∈J¯vxv,wh,t,∀h∈H,∀t∈Th,∀v∈V(5)bShh,t=-DLhh,∀h∈H,∀t∈Th(6)bth,t=DLhh,∀h∈H,∀t∈Th(7)bvh,t=0,∀h∈H,∀t∈Th,∀v∈V-sh,t(8)yv,wh≥maxt∈Th⁡xv,wh,t,∀h∈H,∀v∈V,∀w∈J¯v(9)∑u∈Jvyu,vh≤DLhh-maxl∈Lh⁡Dlh-Dl-1h,∀h∈H,∀v∈I¯(10)∑h∈Hyv,wh≤cv,w,∀v∈V,∀w∈J¯v(11)xv,wh,t≥0,∀h∈H,∀t∈Th,∀v∈V,∀w∈J¯v(12)Dlh≥0,∀h∈H,∀l∈Lh(13)D0h=0,∀h∈HThe meanings of the objective and the constraints in the above mathematical programmingMP are shown in Table 3.Table 3
The meanings of objectives and constraints.
Constraint Meaning  Objective(2) Maximize the total SWT  Constraint(3) The transmission rate of any data stream transmitted in the network must be greater than 0  Constraints(4)–(7) In network topology, nodes need to follow the network flow constraints  Constraint(8) For multicast(sh,Th), the actual flow rate passing through any link in the network is no less than the flow rate passing through the link to any destination node because the coded data packets can be useful for all the destinations in Th with LNC  Constraint(9) The data flow of multicast(sh,Th) passing through any malicious node in the network should meet the requirements of WS  Constraint(10) The sum of all data flows passing through the link should be no greater than the bandwidth capacity of the link  Constraints(11)–(13) Ranges of variablesBecause of the existence of the nonlinear constraints (8)-(9) in MP, it cannot be solved directly. Therefore, next, we will equally transform the mathematical programming problem into alinear programming (LP) problem. Specifically, the nonlinear constraints (8)-(9) inMP can be replaced by the following constraints:(14)yv,wh≥xv,wh,t,∀h∈H,∀t∈Th,∀v∈V,∀w∈J¯v(15)pvh≥Dlh-Dl-1h,∀h∈H,∀l∈Lh,∀v∈I¯(16)∑u∈Jvyu,vh≤DLhh-pvh,∀h∈H,∀v∈I¯Firstly, the constraint (14) is used to replace the constraint (8). Specifically, the constraint (14) is equivalent to yv,wh≥maxt∈Txv,wh,t.Secondly, the constraint (9) can be equally transformed into constraints (15)-(16). For ∀h∈H, ∀vi∈I¯, if the constraints (15)-(16) are satisfied together, we can get ∑u∈J(v)‍yu,vh≤DLhh-pvh≤DLhh-maxl∈LhDlh-Dl-1h which means that the solution also satisfies the constraint (9). On the other hand, ∀h∈H, ∀vi∈I¯, if there is a solution of yu,vh satisfying the constraint (9), then there must be a set of values of pvh=maxl∈LhDlh-Dl-1h≥Dlh-Dl-1h which makes the value of yu,vh satisfy the constraint (16). Thus, with the linearization process, the optimal solution ofMP will not be changed.Therefore, the nonlinear programmingMP can be transformed into the followinglinear programming (LP) MP1:(17)MP1:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1hs.t.constraints  (3)–(7),(10)–(16).The above LPMP1 can be solved efficiently. The obtained solution gives the transmission rate allocation,i.e., {Dlh∣l∈Lh}, and transmission topology,i.e., {yu,vh∣eu,v∈E}, for each multicast h. Based on the transmission rate allocation and transmission topology for each multicast (sh,Th), H secure linear multicast codes can be designed individually [19] to achieve the maximum total SWT given by the objective (2). We refer to the algorithm based on LP MP1 to find the transmission rate allocation and transmission topology for H multicasts as theoptimal rate allocation and transmission topology selection for multiple multicasts (MORT) algorithm.


### 3.2. The SMMS Problem with Source Selection

In the above subsection, we have considered the SMMS problem in the case that each group of sensors is connected with a fixed network device;i.e., each multicast has a fixed source. In this subsection, we will further study the SMMS problem in the case that each group of sensors can decide to connect to a network device;i.e., the source of each multicast can be selected from a set of nodes. Specifically, it means that the source of multicast in core network is different when each group of sensors selects different network devices. Obviously, such source selection will have impacts on the total SWT when multiple multicasts exist in the network. Based on the knowledge that the set of network devices can be selected for each group of sensors, for each multicast, we will select one node as the source node of the multicast in the core network. In the following, we firstly model the problem as a mathematical programming. Then, by linearizing the mathematical programming, we haveinteger linear programming (ILP) algorithm. Finally, we design an efficientMulticast Based on LP-Relaxation (MBLP) algorithm based on linear programming relaxation. We firstly define new parameters and decision variables as shown in Table 4.Table 4
Parameters and decision variables.
Symbol Definition  skh Thekth node can be selected as source of the hth multicast, skh∈V  Kh { 1 , ⋯ , K h }, in which Kh is the number of source nodes can be selected for the hth multicast  xu,vh,k,t The data flows passing through linkeu,v, sent from source node skh to the destination node t  yu,vh,k The actual data flows passing through linkeu,v, sent from source node skh  bvh,k,t The difference between the data flows entering and leaving nodev, sent from source node skh to destination node t  π A sufficient large number  Zkh A0-1 decision variable, which denotes whether the source node skh is selected for the hth multicast or notWe can formulate the SMMS problem with source selection as follows:(18)MP′:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1h(19)s.t.Dlh-Dl-1h>0,∀h∈H,∀l∈Lh(20)bvh,k,t=∑u∈Jvxu,vh,k,t-∑w∈J¯vxv,wh,k,t,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V(21)-Zkhπ≤bskhh,k,t≤0,∀h∈H,∀k∈Kh,∀t∈Th(22)∑k∈Khbskhh,k,t=-DLhh,∀h∈H,∀t∈Th(23)0≤bth,k,t≤Zkhπ,∀h∈H,∀k∈Kh,∀t∈Th(24)∑k∈Khbth,k,t=DLhh,∀h∈H,∀t∈Th(25)bvh,k,t=0,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V-skh,t(26)yv,wh,k≥maxt∈Th⁡xv,wh,k,t,∀h∈H,∀k∈Kh,∀v∈V,∀w∈J¯v(27)∑u∈Jv∑k∈Khyu,vh,k≤DLhh-maxl∈Lh⁡Dlh-Dl-1h,∀h∈H,∀v∈I¯(28)∑h∈H∑k∈Khyv,wh,k≤cv,w,∀v∈V,∀w∈J¯v(29)xv,wh,k,t≥0,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V,∀w∈J¯v(30)Dlh≥0,∀h∈H,∀l∈Lh(31)D0h=0,∀h∈H(32)Zkh∈0,1,∀h∈H,∀k∈Kh(33)∑k∈KhZkh=1,∀h∈HThe meanings of the objective and the constraints in the above mathematical programmingMP′ are shown in Table 5.Table 5
The meanings of objectives and constraints.
Constraint Meaning  Objective (18) Maximize the total SWT  Constraint(19) The transmission rate of each data stream must be greater than0  Constraint(20)–(25) ( 1 ) Nodes in the network must follow the network flow constraints, and (2) for each multicast, only one source node can be select and send out data streams.  Constraint(26) The actual data flow sent from the source nodeskh and transmitted on each link in the network should be no less than the flow sent from the source node skh transmitted on the link to each destination node  Constraint(27) Each data flow passing through the malicious node in the network should meet the requirements of WS  Constraint(10) The sum of data flows passing through each link should not be more than the bandwidth capacity of the link  Constraint(29)–(31) The ranges of the variables  Constraint(32) Whether the nodeskh is selected as the source node of the hth multicast  Constraint(33) Only one node can be selected as the source node of each multicastSimilar to the linearization ofMP, the mathematical programming MP′ can be equivalently transformed into a LP. The following linear constraints can be used to replace constrains (26)-(27) in MP′:(34)yv,wh,k≥xv,wh,k,t,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V,w∈J¯v(35)pvh≥Dlh-Dl-1h,∀h∈H,∀l∈Lh,∀v∈I¯(36)∑u∈Jv∑k∈Khyu,vh,k≤DLhh-pvh,∀h∈H,∀v∈I¯Specifically, the constraint (34) replaces constraint (26), and constraints (35) and (36) replace constraint (27). Therefore, according to the above linearization, the SMMS problem with source selection can be formulated into the following ILP MP1′;(37)MP1′:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1hs.t.constraints  (19)–(25),(28)–(36).When the size of the SMMS problem with source selection is small, the above ILPMP1′ can be used to obtain the optimal source selection, rate allocation, and transmission topology for H multicasts. However, with the increase of the problem size, the computational complexity of the ILP will be extremely high. Therefore, we next propose an efficientMulticast Based on LP-Relaxation (MBLP) algorithm to get the approximate optimal solution. Specifically, we will firstly relax the integer linear constraints of the ILP and obtain the solution of the linear programming. We then round these real number solutions to integer solution.The MBLP algorithm mainly includes the following steps:( 1 ) Replace constraint (32) by constraint (38):(38)0≤Zkh≤1,∀h∈H,∀k∈Kh( 2 ) The objective (18), constraints (19)–(25), constraints (28)–(31), and constraints (33), (34), (35), (36), and (38) compose a new LP. We denote the optimal solution of the LP as {Z1,Z2,⋯,ZH}, in which Zh={Z1h,Z2h,⋯,ZKhh}, ∀h∈{1,⋯,H}. Zkh, ∀h∈{1,⋯,H} and ∀k∈{1,⋯,Kh}, is the optimal solution obtained by solving the LP relaxed by ILP MP1′. We note that the value of Zkh may not be an integer.( 3 ) For each multicast (sh,Th), ∀h∈H, we will select one node from the available source node set as its source node. Specifically, as shown in Algorithm 1, for each multicast (sh,Th), we select the kth node skh in the available source node set who has the biggest value in set Zh={Z1h,Z2h,⋯,ZKhh} as the source node of the hth multicast, and let the corresponding Zkh value be 1 and other values in Zh be 0.Algorithm 1:The Multicast Based onLP-Relaxation (MBLP) algorithm.
(1) Replace constraint (32) by constraint (38) in MP1′. (2) Obtain the optimal solution {Z1,Z2,⋯,ZH} by solving the LP consisting of the objective (18), constraints (19)–(25), constraints (28)–(31) and constraints (33), (34), (35), (36), and (38). (3) For the hth multicast, select the kth node who has the biggest value in set Zh as its source node, and let the correspondingZkh value be 1 and other values in Zh be 0. (4) After selecting the source node for each multicast, treat Zh, ∀h∈{1,⋯,H} as the know parameters inMP1′ and solve it to obtain the optimal transmission rate allocation and transmission topology.( 4 ) After obtaining the values of the Zkh, ∀h∈{1,⋯,H} and ∀k∈{1,⋯,Kh}, we treat them as known parameter in MP1′. Accordingly, MP1′ becomes LP and we can solve it to obtain the optimal transmission rate allocation and transmission topology. Furthermore, H secure linear multicast code can be further designed for H multicast individually [19] to achieve the throughput obtained by MP1′.


## 3.1. The SMMS Problem with Fixed Source

For single multicast, in our previous work [19], we have shown that the sufficient and necessary condition. Specifically, in the SMMS problem, the condition that a secure linear multicast code exists for multicast (sh,Th) is that (1) there exists a network flow Fh with capacity DLhh between sh and each destination in Th, and (2) for each malicious node vi∈I¯, the actual data flow of Fh that enters vi should not be more than DLhh-maxl∈LhDlh-Dl-1h.ForH multicasts simultaneously transmitted in the network G, we next formulate the SMMS problem when each multicast has a fixed source node. Before building a mathematical programming for the SMMS problem, we firstly define new parameters and decision variables, as shown in Table 2.Table 2
Parameters and decision variables.
Symbol Definition  J(v) the set of all the links entering nodev, J(v)=u∣eu,v∈In(v)  J¯(v) the set of all the links leaving nodev, J¯(v)=w∣ev,w∈Out(v)  xu,vh,t the data flow of multicast(sh,Th) transmitted on link eu,v heading for destination node t, ∀h∈H,∀t∈Th,∀eu,v∈E  yu,vh the actual data flow of multicast(sh,Th) transmitted on link eu,v, ∀h∈H  bvh,t The difference of data flow of multicast(sh,Th) between the data flow entering and leaving node v, which heading for destination node t, ∀h∈HWe can formulate a mathematical programming for the SMMS problem as follows:(2)MP:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1h,(3)s.t.Dlh-Dl-1h>0,∀h∈H,∀l∈Lh(4)bvh,t=∑u∈Jvxu,vh,t-∑w∈J¯vxv,wh,t,∀h∈H,∀t∈Th,∀v∈V(5)bShh,t=-DLhh,∀h∈H,∀t∈Th(6)bth,t=DLhh,∀h∈H,∀t∈Th(7)bvh,t=0,∀h∈H,∀t∈Th,∀v∈V-sh,t(8)yv,wh≥maxt∈Th⁡xv,wh,t,∀h∈H,∀v∈V,∀w∈J¯v(9)∑u∈Jvyu,vh≤DLhh-maxl∈Lh⁡Dlh-Dl-1h,∀h∈H,∀v∈I¯(10)∑h∈Hyv,wh≤cv,w,∀v∈V,∀w∈J¯v(11)xv,wh,t≥0,∀h∈H,∀t∈Th,∀v∈V,∀w∈J¯v(12)Dlh≥0,∀h∈H,∀l∈Lh(13)D0h=0,∀h∈HThe meanings of the objective and the constraints in the above mathematical programmingMP are shown in Table 3.Table 3
The meanings of objectives and constraints.
Constraint Meaning  Objective(2) Maximize the total SWT  Constraint(3) The transmission rate of any data stream transmitted in the network must be greater than 0  Constraints(4)–(7) In network topology, nodes need to follow the network flow constraints  Constraint(8) For multicast(sh,Th), the actual flow rate passing through any link in the network is no less than the flow rate passing through the link to any destination node because the coded data packets can be useful for all the destinations in Th with LNC  Constraint(9) The data flow of multicast(sh,Th) passing through any malicious node in the network should meet the requirements of WS  Constraint(10) The sum of all data flows passing through the link should be no greater than the bandwidth capacity of the link  Constraints(11)–(13) Ranges of variablesBecause of the existence of the nonlinear constraints (8)-(9) in MP, it cannot be solved directly. Therefore, next, we will equally transform the mathematical programming problem into alinear programming (LP) problem. Specifically, the nonlinear constraints (8)-(9) inMP can be replaced by the following constraints:(14)yv,wh≥xv,wh,t,∀h∈H,∀t∈Th,∀v∈V,∀w∈J¯v(15)pvh≥Dlh-Dl-1h,∀h∈H,∀l∈Lh,∀v∈I¯(16)∑u∈Jvyu,vh≤DLhh-pvh,∀h∈H,∀v∈I¯Firstly, the constraint (14) is used to replace the constraint (8). Specifically, the constraint (14) is equivalent to yv,wh≥maxt∈Txv,wh,t.Secondly, the constraint (9) can be equally transformed into constraints (15)-(16). For ∀h∈H, ∀vi∈I¯, if the constraints (15)-(16) are satisfied together, we can get ∑u∈J(v)‍yu,vh≤DLhh-pvh≤DLhh-maxl∈LhDlh-Dl-1h which means that the solution also satisfies the constraint (9). On the other hand, ∀h∈H, ∀vi∈I¯, if there is a solution of yu,vh satisfying the constraint (9), then there must be a set of values of pvh=maxl∈LhDlh-Dl-1h≥Dlh-Dl-1h which makes the value of yu,vh satisfy the constraint (16). Thus, with the linearization process, the optimal solution ofMP will not be changed.Therefore, the nonlinear programmingMP can be transformed into the followinglinear programming (LP) MP1:(17)MP1:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1hs.t.constraints  (3)–(7),(10)–(16).The above LPMP1 can be solved efficiently. The obtained solution gives the transmission rate allocation,i.e., {Dlh∣l∈Lh}, and transmission topology,i.e., {yu,vh∣eu,v∈E}, for each multicast h. Based on the transmission rate allocation and transmission topology for each multicast (sh,Th), H secure linear multicast codes can be designed individually [19] to achieve the maximum total SWT given by the objective (2). We refer to the algorithm based on LP MP1 to find the transmission rate allocation and transmission topology for H multicasts as theoptimal rate allocation and transmission topology selection for multiple multicasts (MORT) algorithm.


## 3.2. The SMMS Problem with Source Selection

In the above subsection, we have considered the SMMS problem in the case that each group of sensors is connected with a fixed network device;i.e., each multicast has a fixed source. In this subsection, we will further study the SMMS problem in the case that each group of sensors can decide to connect to a network device;i.e., the source of each multicast can be selected from a set of nodes. Specifically, it means that the source of multicast in core network is different when each group of sensors selects different network devices. Obviously, such source selection will have impacts on the total SWT when multiple multicasts exist in the network. Based on the knowledge that the set of network devices can be selected for each group of sensors, for each multicast, we will select one node as the source node of the multicast in the core network. In the following, we firstly model the problem as a mathematical programming. Then, by linearizing the mathematical programming, we haveinteger linear programming (ILP) algorithm. Finally, we design an efficientMulticast Based on LP-Relaxation (MBLP) algorithm based on linear programming relaxation. We firstly define new parameters and decision variables as shown in Table 4.Table 4
Parameters and decision variables.
Symbol Definition  skh Thekth node can be selected as source of the hth multicast, skh∈V  Kh { 1 , ⋯ , K h }, in which Kh is the number of source nodes can be selected for the hth multicast  xu,vh,k,t The data flows passing through linkeu,v, sent from source node skh to the destination node t  yu,vh,k The actual data flows passing through linkeu,v, sent from source node skh  bvh,k,t The difference between the data flows entering and leaving nodev, sent from source node skh to destination node t  π A sufficient large number  Zkh A0-1 decision variable, which denotes whether the source node skh is selected for the hth multicast or notWe can formulate the SMMS problem with source selection as follows:(18)MP′:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1h(19)s.t.Dlh-Dl-1h>0,∀h∈H,∀l∈Lh(20)bvh,k,t=∑u∈Jvxu,vh,k,t-∑w∈J¯vxv,wh,k,t,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V(21)-Zkhπ≤bskhh,k,t≤0,∀h∈H,∀k∈Kh,∀t∈Th(22)∑k∈Khbskhh,k,t=-DLhh,∀h∈H,∀t∈Th(23)0≤bth,k,t≤Zkhπ,∀h∈H,∀k∈Kh,∀t∈Th(24)∑k∈Khbth,k,t=DLhh,∀h∈H,∀t∈Th(25)bvh,k,t=0,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V-skh,t(26)yv,wh,k≥maxt∈Th⁡xv,wh,k,t,∀h∈H,∀k∈Kh,∀v∈V,∀w∈J¯v(27)∑u∈Jv∑k∈Khyu,vh,k≤DLhh-maxl∈Lh⁡Dlh-Dl-1h,∀h∈H,∀v∈I¯(28)∑h∈H∑k∈Khyv,wh,k≤cv,w,∀v∈V,∀w∈J¯v(29)xv,wh,k,t≥0,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V,∀w∈J¯v(30)Dlh≥0,∀h∈H,∀l∈Lh(31)D0h=0,∀h∈H(32)Zkh∈0,1,∀h∈H,∀k∈Kh(33)∑k∈KhZkh=1,∀h∈HThe meanings of the objective and the constraints in the above mathematical programmingMP′ are shown in Table 5.Table 5
The meanings of objectives and constraints.
Constraint Meaning  Objective (18) Maximize the total SWT  Constraint(19) The transmission rate of each data stream must be greater than0  Constraint(20)–(25) ( 1 ) Nodes in the network must follow the network flow constraints, and (2) for each multicast, only one source node can be select and send out data streams.  Constraint(26) The actual data flow sent from the source nodeskh and transmitted on each link in the network should be no less than the flow sent from the source node skh transmitted on the link to each destination node  Constraint(27) Each data flow passing through the malicious node in the network should meet the requirements of WS  Constraint(10) The sum of data flows passing through each link should not be more than the bandwidth capacity of the link  Constraint(29)–(31) The ranges of the variables  Constraint(32) Whether the nodeskh is selected as the source node of the hth multicast  Constraint(33) Only one node can be selected as the source node of each multicastSimilar to the linearization ofMP, the mathematical programming MP′ can be equivalently transformed into a LP. The following linear constraints can be used to replace constrains (26)-(27) in MP′:(34)yv,wh,k≥xv,wh,k,t,∀h∈H,∀k∈Kh,∀t∈Th,∀v∈V,w∈J¯v(35)pvh≥Dlh-Dl-1h,∀h∈H,∀l∈Lh,∀v∈I¯(36)∑u∈Jv∑k∈Khyu,vh,k≤DLhh-pvh,∀h∈H,∀v∈I¯Specifically, the constraint (34) replaces constraint (26), and constraints (35) and (36) replace constraint (27). Therefore, according to the above linearization, the SMMS problem with source selection can be formulated into the following ILP MP1′;(37)MP1′:Maximize:∑h∈H∑l∈LhωlhDlh-Dl-1hs.t.constraints  (19)–(25),(28)–(36).When the size of the SMMS problem with source selection is small, the above ILPMP1′ can be used to obtain the optimal source selection, rate allocation, and transmission topology for H multicasts. However, with the increase of the problem size, the computational complexity of the ILP will be extremely high. Therefore, we next propose an efficientMulticast Based on LP-Relaxation (MBLP) algorithm to get the approximate optimal solution. Specifically, we will firstly relax the integer linear constraints of the ILP and obtain the solution of the linear programming. We then round these real number solutions to integer solution.The MBLP algorithm mainly includes the following steps:( 1 ) Replace constraint (32) by constraint (38):(38)0≤Zkh≤1,∀h∈H,∀k∈Kh( 2 ) The objective (18), constraints (19)–(25), constraints (28)–(31), and constraints (33), (34), (35), (36), and (38) compose a new LP. We denote the optimal solution of the LP as {Z1,Z2,⋯,ZH}, in which Zh={Z1h,Z2h,⋯,ZKhh}, ∀h∈{1,⋯,H}. Zkh, ∀h∈{1,⋯,H} and ∀k∈{1,⋯,Kh}, is the optimal solution obtained by solving the LP relaxed by ILP MP1′. We note that the value of Zkh may not be an integer.( 3 ) For each multicast (sh,Th), ∀h∈H, we will select one node from the available source node set as its source node. Specifically, as shown in Algorithm 1, for each multicast (sh,Th), we select the kth node skh in the available source node set who has the biggest value in set Zh={Z1h,Z2h,⋯,ZKhh} as the source node of the hth multicast, and let the corresponding Zkh value be 1 and other values in Zh be 0.Algorithm 1:The Multicast Based onLP-Relaxation (MBLP) algorithm.
(1) Replace constraint (32) by constraint (38) in MP1′. (2) Obtain the optimal solution {Z1,Z2,⋯,ZH} by solving the LP consisting of the objective (18), constraints (19)–(25), constraints (28)–(31) and constraints (33), (34), (35), (36), and (38). (3) For the hth multicast, select the kth node who has the biggest value in set Zh as its source node, and let the correspondingZkh value be 1 and other values in Zh be 0. (4) After selecting the source node for each multicast, treat Zh, ∀h∈{1,⋯,H} as the know parameters inMP1′ and solve it to obtain the optimal transmission rate allocation and transmission topology.( 4 ) After obtaining the values of the Zkh, ∀h∈{1,⋯,H} and ∀k∈{1,⋯,Kh}, we treat them as known parameter in MP1′. Accordingly, MP1′ becomes LP and we can solve it to obtain the optimal transmission rate allocation and transmission topology. Furthermore, H secure linear multicast code can be further designed for H multicast individually [19] to achieve the throughput obtained by MP1′.


## 4. Simulation Results

In this section, we will conduct extensive simulations to evaluate the performance of the proposed MORT algorithm and the MBLP algorithm for the SMMS problem with fixed source and source selection, respectively.


### 4.1. Simulation Settings

We will use the Waxman model [20] to generate the random network topology G=V,E to represent the core network. Specifically, in the Waxman model, there are three parameters: λ, α, β and the size of the domain is 10×10.We randomly selectN nodes in V as the set of destination nodes T. For the hth multicast, we first randomly select the value |Th| from [1,N] and then randomly select |Th| nodes from the set of destination nodes T as the set Th. For the SMMS problem with fixed source, we randomly select one node in V-Th for the hth multicast as its source node. On the other hand, for the SMMS problem with source selection, we first randomly select the value |Kh| from [1,sn] and then randomly select |Kh| nodes from V-Th for the hth multicast as the source set Kh. In addition, ma nodes are randomly selected from the remaining nodes as passive attackers. For each link eu,v∈E, its bandwidth capacity cu,v is selected randomly from [1,cmax].For thehth multicast, the number of data streams lh is randomly selected from [1,Lmax]. Moreover, for the Lth data stream of the hth multicast, the weight ωlh is given by the following steps. Firstly, we randomly select a number ω¯lh from [1,ωmax]. Then, the weight ωlh can be calculated by ω¯lh×Lh/∑l=1Lhω¯lh, which makes sure that the total weights of a multicast with Lh streams are Lh.In the following simulations, for each set of parameters, we conduct 50 different groups of network topologies and obtain the average value of them. Moreover, for each figure shown in Figures4 and 5, the performance is evaluated when changing only one parameter. In detail, the parameters used in our simulations are shown in Table 6. The default values of related parameters are λ=0.4, α=0.2, β=0.4, H=4, cmax=30, ma=20, N=8, Lmax=4, ωmax=1, and sn=2.Table 6
Simulation parameters.
Parameter Definition  λ,α,β Parameters of the Waxman model,λ∈0.30,0.35,0.40,0.45,0.50, α∈{0.15,0.20,0.25,0.30,0.35} and β∈0.30,0.35,0.40,0.45,0.50  H The number of multicasts,H∈2,3,4,5,6  N The total number of destination nodes,i.e., N=|T|∈4,6,8,10,12  ma The number of malicious nodes,i.e., ma=|I¯|∈10,15,20,25,30  Lmax The maximum number of data streams,Lmax∈2,3,4,5,6  cmax The maximum value of the link bandwidth capacity,cmax∈20,25,30,35,40  ωmax The value to control the weight of the data stream,ωmax∈1,2,3,4,5  sn The maximum size of the source node set for the SMMS problem with source selection,sn∈1,2,3,4,5Figure 4
Simulation results for the MORT algorithm.
(a)
λ (b)
α (c)
β (d)
H (e)
N (f)
m a (g)
L m a x (h)
c m a x (i)
ω m a xFigure 5
Simulation results for the MBLP algorithm.


### 4.2. Performance of the MORT Algorithm

In order to evaluate the performance of the MORT algorithm, we will compare the MORT algorithm with anupper bound (UB). Specifically, when the constraint (15) and the constraint (16) in the LP MP1 are removed, the objective value obtained by the LP is obviously an upper bound of the MORT algorithm.We will compare the performances of the MORT algorithm with UB when the following seven sets of parameters change.


#### 4.2.1. Network Parameters:λ, α, and β

With the increase ofλ, the number of nodes in the network topology increases. When the parameter β is a constant, more links can be selected to transmit data streams. Therefore, as shown in Figure 4(a), both the MORT algorithm and the UB can achieve higher weighted throughput. However, the MORT algorithm not only guarantees the WS requirements during the transmission, but also keeps the relative gap of the upper bound weighted throughput within 10%, even when the number of nodes and links are sufficiently large in the network. Moreover, with the increase of the node density, the SWT of the MORT algorithm is closer to that of UB.As shown in Figures4(b) and 4(c), with the increase of α and β, the weighted transmission throughput of the two algorithms also increases. Since α or β becomes larger, the probability of the existence of the link between two nodes also increases. Although the node density in the network does not change, the number of links in the network increase with the increase of α or β, which directly increases the transmission throughput of the network. On the other hand, when the network is sparse, the relative gap between the SWT obtained by the MORT algorithm and weighted throughput obtained by UB is about 10%. Moreover, when the network becomes denser, the MORT algorithm is closer to UB.


#### 4.2.2. Number of MulticastsH

As shown in Figure4(d), with the increase of H multicast, both the SWT of MORT and the weighted throughput of UB increase, because more multicast leads to larger total weighted throughput. However, since the SWT of MORT is limited by the WS requirements, the gap between the MORT and the UB increases with the increase of H.


#### 4.2.3. Number of Destination NodesN

In Figure4(e), both the SWT of the MORT and the weighted throughput of UB decrease with the increase of the number of destinations. The reason is that, in each multicast, all the destinations should receive data streams with the same rate,i.e., the throughput of the multicast. Therefore, the more destinations, the lower the SWT achieved by the MORT and the weighted throughput of UB.


#### 4.2.4. Number of Malicious Nodesma

As we can see from Figure4(f), the weighted throughput of the UB remains stable with the increase of ma. The reason is that the UB does not consider the security of data transmission. On the other hand, with the increase of malicious nodes, the SWT of MORT algorithm decreases. This is because that the SWT of MORT is limited by the WS requirements on all malicious nodes. It is worth noting that, even when ma=30,i.e., 90% of intermediate nodes are malicious, the MORT algorithm also can achieve SWT 49, which also can achieve 86% weighted throughput of the UB.


#### 4.2.5. The Maximum Number of Data StreamsLmax

As shown in Figure4(g), the weighted throughput of the UB does not change with the increase of Lmax. This is because when the network topology is fixed, the increase of the number of data streams in a multicast will not affect the weighted throughput of the multicasts. On the other hand, the SWT obtained by the MORT algorithm increases with the increase of Lmax. When the number of data streams of a multicast increases, different data streams can be encoded together to satisfy the requirements of WS. It means that the constraints (15) and (16) related to the requirements of WS will be easily satisfied. Therefore, with the increase of Lmax, the SWT obtained by the MORT algorithm will be closer to the weighted throughput obtained by the UB. We note that the gap between them tends to 0 when Lmax is large enough.


#### 4.2.6. The Maximum Link Bandwidth Capacitycmax

As shown in Figure4(h), when the link bandwidth capacity becomes larger, both the SWT of the MORT and the weighted throughput of UB increase. The reason is obvious. In addition, the relative difference between the SWT obtained by the MORT algorithm and the weighted throughput obtained by the UB is no more than 10%.


#### 4.2.7.ωmax

As mentioned in the example of Section1, to maximize the total SWT, the weight of each data stream is an important parameter and it will directly affect the network weighted throughput. As shown in Figure 4(i), when the network topology is fixed, with the increase of the weight of each data stream, it will inevitably lead to a rapid increase of both the SWT of the MORT and the weighted throughput of UB. Moreover, the increase of the weight of each data stream also amplifies the gap between the SWT of the MORT and the weighted throughput of UB.


### 4.3. Performance of the MBLP Algorithm

In order to evaluate the performance of the MBLP algorithm, we will compare it with theRandom Selection (RS) algorithm. Specifically, in the RS algorithm, we randomly select a node from the node set s1h,s2h,⋯,sKhh as the source node of the hth multicast, ∀h∈{1,⋯,H}, and then obtain the maximum SWT by solving the MORT algorithm. Therefore, the SWT achieved by the RS algorithm composed a lower bound of the SMMS problem with source selection. We will compare the performances of the MBLP algorithm with the RS algorithm when the sn,i.e., the maximum size of the source node set, changes.As shown in Figure5, when the sn becomes larger, the SWT achieved by both algorithms increases significantly. The reason is that, for each multicast, the more the nodes that can be selected as the source, the higher optimization space (probability) that higher SWT can be achieved by the MBLP (RS) algorithm. Since the optimization space becomes larger with the increase of sn, the gap between the SWTs achieved by the MBLP and the RS becomes larger.


## 4.1. Simulation Settings

We will use the Waxman model [20] to generate the random network topology G=V,E to represent the core network. Specifically, in the Waxman model, there are three parameters: λ, α, β and the size of the domain is 10×10.We randomly selectN nodes in V as the set of destination nodes T. For the hth multicast, we first randomly select the value |Th| from [1,N] and then randomly select |Th| nodes from the set of destination nodes T as the set Th. For the SMMS problem with fixed source, we randomly select one node in V-Th for the hth multicast as its source node. On the other hand, for the SMMS problem with source selection, we first randomly select the value |Kh| from [1,sn] and then randomly select |Kh| nodes from V-Th for the hth multicast as the source set Kh. In addition, ma nodes are randomly selected from the remaining nodes as passive attackers. For each link eu,v∈E, its bandwidth capacity cu,v is selected randomly from [1,cmax].For thehth multicast, the number of data streams lh is randomly selected from [1,Lmax]. Moreover, for the Lth data stream of the hth multicast, the weight ωlh is given by the following steps. Firstly, we randomly select a number ω¯lh from [1,ωmax]. Then, the weight ωlh can be calculated by ω¯lh×Lh/∑l=1Lhω¯lh, which makes sure that the total weights of a multicast with Lh streams are Lh.In the following simulations, for each set of parameters, we conduct 50 different groups of network topologies and obtain the average value of them. Moreover, for each figure shown in Figures4 and 5, the performance is evaluated when changing only one parameter. In detail, the parameters used in our simulations are shown in Table 6. The default values of related parameters are λ=0.4, α=0.2, β=0.4, H=4, cmax=30, ma=20, N=8, Lmax=4, ωmax=1, and sn=2.Table 6
Simulation parameters.
Parameter Definition  λ,α,β Parameters of the Waxman model,λ∈0.30,0.35,0.40,0.45,0.50, α∈{0.15,0.20,0.25,0.30,0.35} and β∈0.30,0.35,0.40,0.45,0.50  H The number of multicasts,H∈2,3,4,5,6  N The total number of destination nodes,i.e., N=|T|∈4,6,8,10,12  ma The number of malicious nodes,i.e., ma=|I¯|∈10,15,20,25,30  Lmax The maximum number of data streams,Lmax∈2,3,4,5,6  cmax The maximum value of the link bandwidth capacity,cmax∈20,25,30,35,40  ωmax The value to control the weight of the data stream,ωmax∈1,2,3,4,5  sn The maximum size of the source node set for the SMMS problem with source selection,sn∈1,2,3,4,5Figure 4
Simulation results for the MORT algorithm.
(a)
λ (b)
α (c)
β (d)
H (e)
N (f)
m a (g)
L m a x (h)
c m a x (i)
ω m a xFigure 5
Simulation results for the MBLP algorithm.


## 4.2. Performance of the MORT Algorithm

In order to evaluate the performance of the MORT algorithm, we will compare the MORT algorithm with anupper bound (UB). Specifically, when the constraint (15) and the constraint (16) in the LP MP1 are removed, the objective value obtained by the LP is obviously an upper bound of the MORT algorithm.We will compare the performances of the MORT algorithm with UB when the following seven sets of parameters change.


### 4.2.1. Network Parameters:λ, α, and β

With the increase ofλ, the number of nodes in the network topology increases. When the parameter β is a constant, more links can be selected to transmit data streams. Therefore, as shown in Figure 4(a), both the MORT algorithm and the UB can achieve higher weighted throughput. However, the MORT algorithm not only guarantees the WS requirements during the transmission, but also keeps the relative gap of the upper bound weighted throughput within 10%, even when the number of nodes and links are sufficiently large in the network. Moreover, with the increase of the node density, the SWT of the MORT algorithm is closer to that of UB.As shown in Figures4(b) and 4(c), with the increase of α and β, the weighted transmission throughput of the two algorithms also increases. Since α or β becomes larger, the probability of the existence of the link between two nodes also increases. Although the node density in the network does not change, the number of links in the network increase with the increase of α or β, which directly increases the transmission throughput of the network. On the other hand, when the network is sparse, the relative gap between the SWT obtained by the MORT algorithm and weighted throughput obtained by UB is about 10%. Moreover, when the network becomes denser, the MORT algorithm is closer to UB.


### 4.2.2. Number of MulticastsH

As shown in Figure4(d), with the increase of H multicast, both the SWT of MORT and the weighted throughput of UB increase, because more multicast leads to larger total weighted throughput. However, since the SWT of MORT is limited by the WS requirements, the gap between the MORT and the UB increases with the increase of H.


### 4.2.3. Number of Destination NodesN

In Figure4(e), both the SWT of the MORT and the weighted throughput of UB decrease with the increase of the number of destinations. The reason is that, in each multicast, all the destinations should receive data streams with the same rate,i.e., the throughput of the multicast. Therefore, the more destinations, the lower the SWT achieved by the MORT and the weighted throughput of UB.


### 4.2.4. Number of Malicious Nodesma

As we can see from Figure4(f), the weighted throughput of the UB remains stable with the increase of ma. The reason is that the UB does not consider the security of data transmission. On the other hand, with the increase of malicious nodes, the SWT of MORT algorithm decreases. This is because that the SWT of MORT is limited by the WS requirements on all malicious nodes. It is worth noting that, even when ma=30,i.e., 90% of intermediate nodes are malicious, the MORT algorithm also can achieve SWT 49, which also can achieve 86% weighted throughput of the UB.


### 4.2.5. The Maximum Number of Data StreamsLmax

As shown in Figure4(g), the weighted throughput of the UB does not change with the increase of Lmax. This is because when the network topology is fixed, the increase of the number of data streams in a multicast will not affect the weighted throughput of the multicasts. On the other hand, the SWT obtained by the MORT algorithm increases with the increase of Lmax. When the number of data streams of a multicast increases, different data streams can be encoded together to satisfy the requirements of WS. It means that the constraints (15) and (16) related to the requirements of WS will be easily satisfied. Therefore, with the increase of Lmax, the SWT obtained by the MORT algorithm will be closer to the weighted throughput obtained by the UB. We note that the gap between them tends to 0 when Lmax is large enough.


### 4.2.6. The Maximum Link Bandwidth Capacitycmax

As shown in Figure4(h), when the link bandwidth capacity becomes larger, both the SWT of the MORT and the weighted throughput of UB increase. The reason is obvious. In addition, the relative difference between the SWT obtained by the MORT algorithm and the weighted throughput obtained by the UB is no more than 10%.


### 4.2.7.ωmax

As mentioned in the example of Section1, to maximize the total SWT, the weight of each data stream is an important parameter and it will directly affect the network weighted throughput. As shown in Figure 4(i), when the network topology is fixed, with the increase of the weight of each data stream, it will inevitably lead to a rapid increase of both the SWT of the MORT and the weighted throughput of UB. Moreover, the increase of the weight of each data stream also amplifies the gap between the SWT of the MORT and the weighted throughput of UB.


## 4.2.1. Network Parameters:λ, α, and β

With the increase ofλ, the number of nodes in the network topology increases. When the parameter β is a constant, more links can be selected to transmit data streams. Therefore, as shown in Figure 4(a), both the MORT algorithm and the UB can achieve higher weighted throughput. However, the MORT algorithm not only guarantees the WS requirements during the transmission, but also keeps the relative gap of the upper bound weighted throughput within 10%, even when the number of nodes and links are sufficiently large in the network. Moreover, with the increase of the node density, the SWT of the MORT algorithm is closer to that of UB.As shown in Figures4(b) and 4(c), with the increase of α and β, the weighted transmission throughput of the two algorithms also increases. Since α or β becomes larger, the probability of the existence of the link between two nodes also increases. Although the node density in the network does not change, the number of links in the network increase with the increase of α or β, which directly increases the transmission throughput of the network. On the other hand, when the network is sparse, the relative gap between the SWT obtained by the MORT algorithm and weighted throughput obtained by UB is about 10%. Moreover, when the network becomes denser, the MORT algorithm is closer to UB.


## 4.2.2. Number of MulticastsH

As shown in Figure4(d), with the increase of H multicast, both the SWT of MORT and the weighted throughput of UB increase, because more multicast leads to larger total weighted throughput. However, since the SWT of MORT is limited by the WS requirements, the gap between the MORT and the UB increases with the increase of H.


## 4.2.3. Number of Destination NodesN

In Figure4(e), both the SWT of the MORT and the weighted throughput of UB decrease with the increase of the number of destinations. The reason is that, in each multicast, all the destinations should receive data streams with the same rate,i.e., the throughput of the multicast. Therefore, the more destinations, the lower the SWT achieved by the MORT and the weighted throughput of UB.


## 4.2.4. Number of Malicious Nodesma

As we can see from Figure4(f), the weighted throughput of the UB remains stable with the increase of ma. The reason is that the UB does not consider the security of data transmission. On the other hand, with the increase of malicious nodes, the SWT of MORT algorithm decreases. This is because that the SWT of MORT is limited by the WS requirements on all malicious nodes. It is worth noting that, even when ma=30,i.e., 90% of intermediate nodes are malicious, the MORT algorithm also can achieve SWT 49, which also can achieve 86% weighted throughput of the UB.


## 4.2.5. The Maximum Number of Data StreamsLmax

As shown in Figure4(g), the weighted throughput of the UB does not change with the increase of Lmax. This is because when the network topology is fixed, the increase of the number of data streams in a multicast will not affect the weighted throughput of the multicasts. On the other hand, the SWT obtained by the MORT algorithm increases with the increase of Lmax. When the number of data streams of a multicast increases, different data streams can be encoded together to satisfy the requirements of WS. It means that the constraints (15) and (16) related to the requirements of WS will be easily satisfied. Therefore, with the increase of Lmax, the SWT obtained by the MORT algorithm will be closer to the weighted throughput obtained by the UB. We note that the gap between them tends to 0 when Lmax is large enough.


## 4.2.6. The Maximum Link Bandwidth Capacitycmax

As shown in Figure4(h), when the link bandwidth capacity becomes larger, both the SWT of the MORT and the weighted throughput of UB increase. The reason is obvious. In addition, the relative difference between the SWT obtained by the MORT algorithm and the weighted throughput obtained by the UB is no more than 10%.


## 4.2.7.ωmax

As mentioned in the example of Section1, to maximize the total SWT, the weight of each data stream is an important parameter and it will directly affect the network weighted throughput. As shown in Figure 4(i), when the network topology is fixed, with the increase of the weight of each data stream, it will inevitably lead to a rapid increase of both the SWT of the MORT and the weighted throughput of UB. Moreover, the increase of the weight of each data stream also amplifies the gap between the SWT of the MORT and the weighted throughput of UB.


## 4.3. Performance of the MBLP Algorithm

In order to evaluate the performance of the MBLP algorithm, we will compare it with theRandom Selection (RS) algorithm. Specifically, in the RS algorithm, we randomly select a node from the node set s1h,s2h,⋯,sKhh as the source node of the hth multicast, ∀h∈{1,⋯,H}, and then obtain the maximum SWT by solving the MORT algorithm. Therefore, the SWT achieved by the RS algorithm composed a lower bound of the SMMS problem with source selection. We will compare the performances of the MBLP algorithm with the RS algorithm when the sn,i.e., the maximum size of the source node set, changes.As shown in Figure5, when the sn becomes larger, the SWT achieved by both algorithms increases significantly. The reason is that, for each multicast, the more the nodes that can be selected as the source, the higher optimization space (probability) that higher SWT can be achieved by the MBLP (RS) algorithm. Since the optimization space becomes larger with the increase of sn, the gap between the SWTs achieved by the MBLP and the RS becomes larger.


## 5. Conclusion

In this paper, thesecure delivery for multiple multicast with multiple streams (SMMS) problem has been considered to maximize the totalsecure weighted throughput (SWT). Specifically, we considered the problem in the following cases. (1) When the source is fixed in each multicast, we firstly formulated the problem as alinear programming (LP) based on the problem model and then proposed the MORT algorithm to optimally solve the LP. (2) When the source of each multicast can be selected from a set of nodes, we firstly formulated the problem as aninteger linear programming (ILP) and then proposed a near-optimal MBLP algorithm based on LP relaxation to solve the ILP. After we proposed the MORT algorithm and the MBLP algorithm, we also designed an upper bound for the MORT algorithm and a lower bound for the MBLP algorithm, respectively. Finally, we conducted extensive simulations to evaluate the performance of the two proposed algorithms, which showed the efficiency of them. Specifically, the proposed MORT algorithm is close to the upper bound when the network size or the problem size is large, and the proposed MBLP algorithm is far away from the lower bound when the available source node set size is large.



---

*Source: 3729046-2018-06-13.xml*