I Introduction
In 5G and Internet of Things, tens of billions of devices are expected to be deployed to serve our societies[al2015internet, gupta2015survey, vaezi2018multiple]. With such an enormous number of nodes, the collection of data using the conventional multiaccess schemes is impractical because this would result in excessive network latency with limited radio resources.
To solve the problem, a promising solution is computation over multiaccess channel (CoMAC). It exploits the signalsuperposition property of wireless channel by computing the desired function through concurrent node transmissions[goldenbaum2015nomographic, goldenbaum2013robust, abari2016over, goldenbaum2014channel, kortke2014analog, zhu2018over, wu2019experimental, nazer2007computation, appuswamy2014computing, erez2005lattices, wu2018experimental, nazer2011compute, jeon2014computation, Jeon2016Opportunistic, wang2015interactive, goldenbaum2014computation]. Many networks computing a class of nomographic functions of the distributed data can employ CoMAC[goldenbaum2015nomographic]. For example, wireless sensor networks can use the framework of CoMAC since it only aims to obtain a functional value of the sensor readings (e.g., arithmetic mean, polynomial or the number of active nodes) instead of requiring all readings from all sensors.
Analog CoMAC was first studied in [goldenbaum2013robust, abari2016over, goldenbaum2014channel, kortke2014analog, zhu2018over, wu2019experimental], where preprocessing at each node and postprocessing at the fusion center were used to fight fading and compute functions. The designs of preprocessing and postprocessing used to compute linear and nonlinear functions have been proposed in[abari2016over]
, and the effect of channel estimation error was characterized in
[goldenbaum2014channel]. In order to verify the feasibility of analog CoMAC in practice, software defined radio was built in [kortke2014analog]. A multifunction computation method has been presented in [zhu2018over], which utilized a multiantenna fusion center to collect data transmitted by a cluster of multiantenna multimodal sensors. Also, the authors in [wu2019experimental] studied how to compute multiple functions overtheair with antennas arrays at devices and the access point, where different linear combinations with arbitrary coefficients for the Gaussian sources were computed. In summary, the simple analog CoMAC has led to an active area focusing on the design and implementation techniques for receiving a desired function.Since analog CoMAC is not robust to noise, digital CoMAC was proposed to use joint sourcechannel coding in [nazer2007computation, appuswamy2014computing, erez2005lattices, nazer2011compute, jeon2014computation, Jeon2016Opportunistic, wang2015interactive, goldenbaum2014computation, wu2018experimental, wu2018computation] to improve equivalent signaltonoise ratio (SNR). The potential of linear source coding was discussed in [nazer2007computation], and its application was presented in [appuswamy2014computing] for CoMAC. Compared with linear source coding, nested lattice coding can approach the performance of a standard random coding[erez2005lattices]. The latticebased CoMAC was extended to a general framework in [nazer2011compute] for relay networks with linear channels and additive white Gaussian noise (AWGN). In order to combat nonuniform fading, a uniformforcing transceiver design was given in [wu2018experimental]. Achievable computation rates were given in [nazer2011compute, jeon2014computation, Jeon2016Opportunistic] for digital CoMAC through theoretical analysis.
One serious issue in digital CoMAC is the vanishing rate as the number of nodes increases when the fading MAC is considered. In order to prevent the vanishing rate, a narrowband CoMAC (NBCoMAC) with opportunistic computation has been studied in [Jeon2016Opportunistic]. A wideband CoMAC (WBCoMAC) has been extended in [wu2018computation] against both frequency selective fading and the vanishing computation rate.
To the best of our knowledge, all the aforementioned CoMAC works only considered the use of orthogonal multiple access (OMA) for functions by transmitting the function in different resource blocks (RBs), i.e, time slots or subcarriers. Nonorthogonal multiple access (NOMA) is wellknown for improving spectrum efficiency but has never been considered in CoMAC[ding2017survey, dai2018survey, wang2006comparison]. For example, the authors in [wang2006comparison] compared NOMA and OMA in the uplink, which showed that NOMA achieves higher ergodic sum rates while the fairness of nodes has been considered. NOMA based on user pairing was considered in [ding2016impact, yang2016general, sedaghat2018user] to ease successive interference cancellation (SIC) caused by the superposition transmission of too many nodes at the base station. Different from NOMA for information transmission, NOMAbased CoMAC (NOMACoMAC) superposes multiple functions instead of different bit sequences from different nodes in each RB. Also, nodes with disparate channel conditions are allowed to be served simultaneously in conventional NOMA to improve the performance, whereas the node with poor channel condition only makes the computation rate vanishing in NOMACoMAC system since the function computed by nodes requires the uniform fading. It suggests that the direct use of NOMA in CoMAC system is not suitable.
Motivated by the above observations, in this work, we propose a NOMACoMAC system through the division, superposition, SIC and reconstruction of the desired functions. Analytical expression for the achievable computation rate with subfunction superposition is derived based on nested lattice coding[jeon2014computation, Jeon2016Opportunistic, wang2015interactive, goldenbaum2014computation]. Furthermore, several limiting cases are considered to characterize the lower bound of the computation rate and the diversity order. Our contributions can be summarized as follows:

Novel NOMACoMAC. We propose a NOMACoMAC system with subfunction superposition. Unlike NOMA systems for information transmission, NOMACoMAC decomposes the desired functions into several subfunctions, superposes these subfunctions with large equivalent channel gains in each RB, executes the process of SIC and reconstructs the desired functions at the fusion center.

Improved computation rate. The analytical expression of the computation rate of NOMACoMAC is derived. Using the closedform expression, the power allocated to each node can be calculated directly with low computational complexity. Compared with the conventional CoMAC schemes, both achievable computation rate and nonvanishing rate with massive nodes are improved.

Limiting cases. We characterize the lower bound of the computation rate with an exact expression as the number of nodes goes to infinity. It provides a straightforward way to evaluate the system performance. As the power of each node goes to infinity, we obtain the diversity order of the computation rate of NOMACoMAC. It shows that the node with the worst channel gain among these subfunctions in each RB plays a dominant role.
The rest of the paper is organized as follows. Section II introduces the definitions and the existing results of NBCoMAC and WBCoMAC. The system model of NOMACoMAC is further given. In Section III, we summarize the main results of this paper and compare them with the conventional CoMAC schemes. Section IV presents the proposed NOMACoMAC with subfunction superposition in detail and analyzes the computation rate. Section V focuses on the performance of the proposed NOMACoMAC, which includes the power control and outage. Simulation results and the corresponding discussion are presented in Section VI, and conclusions are given in Section VII.
Ii System Model
We introduce two typical CoMAC frameworks in this section, and review the main results of several previous works. We define and as the ceiling function. Let denote a set and
represent the transpose of a vector or matrix. For a set
, denotes the cardinality of. Let the entropy of a random variable
be and denote the diagonal matrix of which the diagonal elements are from to . A set is written as or for short.Iia NarrowBand CoMAC
The framework of NBCoMAC is shown as Fig. 1, where each node draws data from a corresponding random source for times and obtains a length data vector. After encoding the data vector, the fusion center computes a desired function as all nodes transmit theirs data vector simultaneously.
First of all, we define the data matrix to describe the data from nodes during time slots.
Definition 1 (Data Matrix).
A data matrix represents the data from nodes during time slots. It is expressed as
(1) 
where , , is the th data of the th node from the random source , is the th data of all nodes and is the data vector of node . Each data belongs to , which means it is mapped to a number between 0 and through quantization. Let
be a random vector associated with a joint probability mass function
as is independently drawn from .A function with respect to the random source vector is called the desired function. Its definition is given as follows.
Definition 2 (Desired Function).
For all , every function
(2) 
that is computed at the fusion center is called a desired function where is independently drawn from (See Definition 1). Every function can be seen as a realization of . Thus, it has functions when each node gets data from each random source for times.
In order to be robust against noise, we use sequences of nested lattice codes[nazer2011compute] throughout this paper. Based on this coding, the definitions of encoding and decoding are given as follows.
Definition 3 (Encoding & Decoding).
Let denote the data vector for the th node whose length is (see Definition 1). Denote as the length transmitted vector for node . The received vector with length is given by at the fusion center. Assuming a block code with length , the encoding and decoding functions can be expressed as follows.

Encoding Functions: the univariate function which generates is an encoding function of node . It maps with length to a transmitted vector with length for node .

Decoding Functions: the decoding function is used to estimate the th desired function , which satisfies . It implies the fusion center obtains desired functions depending on the whole received vector with length .
Considering the block code with length , the definition of computation rate[Jeon2016Opportunistic, jeon2014computation, goldenbaum2015nomographic, goldenbaum2014computation] can be given as follows.
Definition 4 (Computation rate).
The computation rate specifies how many function values can be computed per channel use within a predefined accuracy. It can be written as where is the number of function values (see Definition 2), is the length of the block code and is the entropy of . Apart from this, is achievable only if there is a length block code so that the probability as increases.
IiB WideBand CoMAC
The framework of CoMAC was adopted to a wideband MAC which aims to improve the computation rate over NBCoMAC. The desired function as a whole cannot be allocated into several subcarriers. Thus, it divided the desired function into subfunctions transmitted as bit sequences, and allocated subfunctions to each subcarrier so as to provide a improved nonvanishing computation rate. The framework of WBCoMAC is shown in Fig. 2.
A desired function is computed through the simultaneous transmission of all nodes. If only a subset of nodes participates in the computation, the function computed by a subset of nodes is called the subfunction. The subfunction is only part of the desired function. Assuming that a subfunction is computed by chosen nodes and the number of all nodes is , the desired function is split into parts.
Definition 5 (SubFunction).
Let
(3) 
denote a set where each element is the index from the chosen nodes. Suppose that and for all , a function is said to be a subfunction if and only if there exists a function satisfying .
Remark 1 (Detachable functions).
As studied in [giridhar2005computing, wang2015interactive, goldenbaum2014computation, jeon2014computation], CoMAC can be designed to compute different types of desired function. We focus on two typical functions, the arithmetic sum function and the type function. A function is the arithmetic sum function where is the weighting factor for node . A function is regarded as the type function where denotes the indicator function and . Both arithmetic sum function and type function are detachable from Definition 5.
IiC Existing Results
The computation rates of NBCoMAC and WBCoMAC are given as follows.
Theorem 1 (Rate of NBCoMAC).
As shown in [Jeon2016Opportunistic, Theorem 1], for any satisfying , the ergodic computation rate of NBCoMAC is given by
(4) 
where is the number of nodes, is the number of the chosen nodes to compute a subfunction, is the channel gain of the th node, is the th element of the set of the ordered indexes of channel gains such that and is any random variable.
Theorem 1 considered a NBCoMAC with flat fading, [wu2018computation] expanded it to a WBCoMAC with frequency selective fading to focus on high speed transmission.
Theorem 2 (Rate of WBCoMAC).
As mentioned in [wu2018computation, Corollary 2 and Eq. (27)], for any satisfying , the ergodic computation rate of WBCoMAC over frequency selective fading MAC is given by
(5) 
where is the number of subcarriers, is the channel gain of the th node at the th subcarrier and is the th element of the set of ordered indexes of channel gains at the th subcarrier such that .
One sees that both CoMAC schemes in the above only consider the use of OMA to transmit a function in each RB. This results in low spectrum efficiency. Since NOMA can offer extra improvement in spectrum efficiency, we apply NOMA to CoMAC to improve the computation rate. Thus, we propose a NOMACoMAC system with subfunction superposition, where each subcarrier can serve these subfunctions with large equivalent channel gains simultaneously. It can not only achieve a higher computation rate, but also can provide an improved nonvanishing rate with massive nodes.
IiD Novel NOMA for WideBand MAC
The framework of WBCoMAC discussed in Section IIB will be used to transmit multiple functions simultaneously in each subcarrier using NOMA. We consider an OFDMbased system with subcarriers during OFDM symbols while the length of the block code is . In each subcarrier, functions are chosen to be transmitted. Then, the th received OFDM symbol at the fusion center can be expressed as
(6) 
where , , is the number of nodes, the power allocation matrix of node is whose diagonal element is the power allocated to compute the th function at each subcarrier, is the transmitted diagonal matrix of node to compute the th function, a diagonal matrix is the channel response matrix of which the diagonal element is the channel response of each subcarrier for node and the diagonal element of is identically and independently distributed (i.i.d.) complex Gaussian random noise following .
Assuming perfect synchronization and perfect removal of intercarrier interference, based on Eq. (6), the received signal in the th subcarrier at the th OFDM symbol can be given as
(7) 
where is the power of node allocated in the subcarrier for computing the th function, is the transmitted symbol of node for the th function in the th subcarrier from the transmitted vector (See Definition 3), is the channel response of the subcarrier for node and is i.i.d. complex Gaussian random noise following .
Iii Main Results
In the OFDMbased system, all the nodes is sorted by their channel gains in each subcarrier, and the ordered nodes are divided into parts to compute subfunctions. Only the first subfunctions with large equivalent channel gains are chosen to be superposed in a subcarrier. Then, the computation rate of NOMACoMAC is achievable with the limit of large .
Theorem 3 (Rate of NOMACoMAC).
For any satisfying and , the ergodic computation rate of NOMACoMAC over wideband MAC is given as
(8) 
where is the number of nodes, is the number of chosen nodes to compute a subfunction, is the number of chosen subfunctions in each subcarrier, is the number of subcarriers, is the number of OFDM symbols, is a set including the indexes of the chosen nodes to compute the corresponding subfunction, is the th index of the ordered indexes of nodes in the th subcarrier at the OFDM symbol, is the channel gain of the th node in the th subcarrier at the th OFDM symbol and is the power allocated to node .
Proof:
Please refer to Section IV for proof. ∎
Remark 2 (Property of NOMACoMAC).
Theorem 3 presents a general rate which can be used with power control. It shows that the rate of NOMACoMAC is determined by the subfunction with the slowest rate among the subfunctions in every subcarrier, since the desired function can not be reconstructed unless all subfunctions are received at the fusion center.
Remark 3 (Generalization of rates for NBCoMAC and WBCoMAC).
CoMAC Scheme  Achievable Rate  Limiting Rate 

NBCoMAC  [Jeon2016Opportunistic]  
WBCoMAC  [wu2018computation]  
NOMACoMAC 
In the proposed scheme, we choose the first subfunctions with large channel gains in each subcarrier. Since the superposition transmission of too many subfunctions makes SIC at the fusion center difficult, only two subfunctions () as a pair are chosen to be transmitted in a single subcarrier.
Corollary 1 (Rate of NOMACoMAC with average power control).
Considering an OFDMbased system where each subcarrier serves a subfunction pair (), the ergodic computation rate of NOMACoMAC considering the average power control, i.e, for node , can be obtained as
(9) 
where and .
Corollary 1 provides an easy way to allocate the power into each subfunction when average power control is considered, since the power allocated to each node can be calculated directly using the closedform expression with low computational complexity.
Similar to the previous works, the rate of NOMACoMAC in Corollary 1 can also prevent the rate from vanishing as the number of nodes increases. Nevertheless, the previous works only verified the nonvanishing rate through simulation and did not obtain its exact value through mathematical analysis. We characterize the lower bound of the computation rate as the limiting rate. It can be used to calculate the accurate value of the nonvanishing computation rate with given parameters.
Corollary 2 (Limiting Rate of NOMACoMAC).
As increases, the computation rate of NOMACoMAC approaches an exact value which is only determined by and can be given as
(10) 
where , , and
is the cumulative distribution function (CDF) of
. For i.i.d. Rayleigh fading,is the CDF of the exponential distribution with parameter one, i.e.,
and .Proof:
Please refer to Appendix B for proof. ∎
Note that previous works only proved that the computation rate was nonvanishing through simulation, Corollary 2 provides the lower bound of the computation rate of NOMACoMAC, which is easier to evaluate the performance. Using a similar proof of Corollary 2, we can obtain the limiting rates of WBCoMAC and NBCoMAC.
Remark 4 (Limiting Rates for NBCoMAC and WBCoMAC).
No exact lower bound of the computation rates and their limiting rates are available in previous works. Hence, we derive the exact expression of these limiting rates, which can calculate the exact values of these nonvanishing rates with given parameters. Following a similar proof, the limiting rate of WBCoMAC in Theorem 2 can be obtained easily as
(11) 
It also generalizes the limiting rate of NBCoMAC in Theorem 1 as . Unlike conventional works with respect to a series of random variables and , these limiting rates are only determined by ( or ).
In conclusion, we summarize these achievable computation rates and limiting rates in Table I.
Iv Proposed NOMACoMAC Scheme
Iva Proposed Scheme
As mentioned in Section IIC, NBCoMAC only considered the flat fading channel. In order to improve the computation rate and deal with frequency selective fading, WBCoMAC was proposed. These conventional CoMAC schemes transmit only one function (or subfunction) in each RB resulting in low spectrum utilization efficiency, hence applying NOMA design into CoMAC is a way to improve the computation rate through multiple subfunctions superposition.
As shown in Fig. 3, we provide a simplified description on the proposed scheme in a hybrid OFDMNOMA system.

SubFunction Process. In each subcarrier, we sort all the nodes depending on the corresponding channel gains. Then, every nodes in such an order computes a function which is regarded as a subfunction in Fig. LABEL:sub@fig:nomacomaca. Referring to Definition 5, denotes the set whose elements belong to these indexes of nodes to compute a subfunction . Then, let the set
(12) include all the possible subfunctions^{1}^{1}1For easy presentation, we use the element stands for the subfunction which is computed by these nodes in ., and the cardinality of is .

Superposition Process. As shown in Fig. LABEL:sub@fig:nomacomaca, let the worst channel gain in the subfunction stand for the equivalent channel gain of the subfunction. Then, we sort all the subfunctions in each subcarrier according to these equivalent channel gains. Only the first subfunctions are chosen to be simultaneously transmitted, which is seen as a superposition. Then, one possible superposition can be defined as
(13) where , and subfunctions . All the possible superpositions are in a set
(14) 
SIC Process. As shown in Fig. LABEL:sub@fig:nomacomacb, all the OFDM symbols are received at the fusion center. Each subcarrier contains a superposition with subfunctions. Through SIC given in [nazer2011compute], we can obtain all the subfunctions.

Reconstruction Process. As mentioned in Definition 5, all the subfunctions need to be reconstructed at the fusion center. The set
(15) contains all the possible combinations whose element can reconstruct a whole desired function, and the cardinality of is . After all the subfunctions are collected in Fig. LABEL:sub@fig:nomacomacb, we can recover the desired functions by using the relationship between the subfunctions and the desired functions.
IvB Computation Rate of NOMACoMAC
As shown in Fig. 3, the desired function is divided into parts, each part can be regarded as a subfunction which is computed at fusion center individually. In each subcarrier, subfunctions are chosen to be transmitted. Based on those definitions in the previous subsection, we use the following parts to derive the computation rate step by step.
Rate of SubFunction . As mentioned in Fig. LABEL:sub@fig:nomacomaca, subfunctions are chosen for the th subcarrier at the th OFDM symbol to be transmitted. The th subfunction is computed by nodes whose indexes are in the set at the fusion center. We assume the bandwidth of the hybrid OFDMNOMA system with subcarriers is the same as the mentioned conventional CoMAC system. The bandwidth that each subcarrier owns is of the total bandwidth. Then, the computation rate of the th subfunction in a subcarrier at the th OFDM symbol can be given as follows.
Lemma 1 (Computation Rate of a SubFunction).
With the limit of large and subfunctions in the th subcarrier, the instantaneous computation rate of the th subfunction at the
th OFDM symbol with AWGN whose variance is
can be express as(16) 
where is the channel gain of the th subcarrier for the node , is the power allocated to the th node in the th subcarrier and is the set including the index of the chosen nodes to compute the th subfunction (See Eq. (8)).
Proof:
As demonstrated in [nazer2011compute], CoMAC can subtract part of the contribution from the channel observation to compute several functions at the fusion center based on successive cancellation. Let denote the channel vector and denote the coefficient vector to compute the th function. From [nazer2011compute, Theorem 12], the computation rate of the th function from the channel observation with a noise variance of can be express as
(17) 
where is the scalar parameter to move the channel coefficients closer to the th desired function. By giving the optimal following [nazer2011compute, Remark 11], of the noise variance and the th element of the coefficient vector
(18) 
the computation rate of the th subfunction in single subcarrier can be given as
(19) 
Then combining Eq. (19) with [jeon2014computation, Theorem 3], the computation rate considering fading channel and power control at the th time slot is further expressed as
(20) 
Since the propagation time of a subcarrier symbol in OFDM needs time slots as mentioned in [wu2018computation, Lemma 1], for the th subfunction in the th subcarrier at the th OFDM symbol is of . In conclusion, Lemma 1 has been proved. ∎
Rate of Superposition . Compared with conventional CoMAC schemes, each subfunction in the same subcarrier has to face interfunction interference in NOMACoMAC, which causes the different computation rates of different subfunctions in the same subcarrier. Lemma 1 demonstrates the rate of the th function in the th subcarrier is a part of the sum rate of the superposition of the subfunctions in single subcarrier. From Fig. LABEL:sub@fig:nomacomaca, it shows that we need to determine the sum rate of all the subfunctions in a superposition since those subfunctions are transmitted as a whole.
Lemma 2 (Computation Rate of a Superposition).
As the limit of large , the instantaneous computation rate of the superposition of subfunctions in the th subcarrier at the th OFDM symbol with AWGN whose variance is can be express as
(21) 
Proof:
The rate of the superposition of subfunctions is determined by the minimum for all , since each subfunction is a part of the original desired function and the desired function can be reconstructed if and only if all parts have been received at the fusion center. ∎
Rate of Combination . In the hybrid OFDMNOMA system with subcarriers, the number of OFDM symbols is at least ^{2}^{2}2In order to simplify the derivation, the number of OFDM symbols in Eq. (6) is given as instead.. It also implies that the number of all the subcarriers during OFDM symbols is , and each subcarrier serves one superposition . We define a set including those subcarriers that serve the combination and a set containing the subcarriers that serve the specific superposition in the combination . Since the superpositions and the combinations in practice are random depending on channel realizations, it causes that and are stochastic. As the limit of large , the set and contain, respectively, subcarriers and subcarriers referring to [wu2018computation, Lemma 2]. Then, the transmission of the specific superposition in the combination totally occupies OFDM symbols^{3}^{3}3Although these superpositions are sent separately in different subcarrier in different OFMD symbol, we can consider that they are transmitted centrally when obtaining the achievable rate..
Lemma 3 (Computation Rate of a Combination).
The average rate for computing those subfunctions in the combination during OFDM symbols can be given as
(22) 
Proof:
According to Eqs. (6) and (7), the received signal in the th subcarrier for the superposition based on the combination can be given as
(23)  
(24) 
where , contains the indexes of the th subfunction in the superposition and is equivalent channel.
Depending on the conclusions of Lemmas 1, 2 and Eq. (24), we can obtain the average rate for computing the superposition in the combination during OFDM symbols
(25) 
Then, the average rate for computing those subfunction in the combination is expressed as
(26) 
where condition follows because of the similar result to Lemma 2 and condition follows as each average rate approaches the same value with the limit of large . ∎
With the help of Eq. (22) and the length of the transmitted vector , the length of the data vector is as the same as the number of the desired function values reconstructed by combination (See Definitions 3 and 4). is only the part of all the values of desired function , and the exact number of desired function values for all during OFDM symbols is
(27) 
V Performance of Proposed NOMACoMAC Scheme
In this section, we derive the achievable computation rate of the proposed NOMACoMAC with average power control based on the general rate in Theorem 3. We further analyze the outage performance and obtain the diversity order.
Va Power Control
We consider an average power control method where the average power of each node in each subcarrier is no more than for all , i.e., . Let represent the transmitted power in the th subcarrier at the th OFDM symbol for the node , and it can be express as
(29) 
where as a constant, can be regarded as the power factor to compute the th subfunction in the th subcarrier and the detailed derivation is given in Appendix A. By putting Eq. (29) into Eq. (16), the rate of the th subfunction in Lemma 1 can be rewritten as
(30) 
VB Problem Formulation
We work on maximizing the instantaneous rate of each OFDM symbol to improve the ergodic rate, since the rate in Theorem 3 can be regarded as the mean of the instantaneous rate. Then we formulate the following optimization.
Problem 1.
Because the superposition transmission of too many subfunctions brings the difficulty of SIC at the fusion center and makes the mathematical analysis hard, we choose two subfunctions as a pair to be transmitted in single subcarrier. By setting in Problem 1, the relationship between and can be obtained as
(31) 
where
Comments
There are no comments yet.